← Back to branch summary

~louis/ubuntu/trusty/clamav/lp799623_fix_logrotate

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/lib/CodeGen/CodePlacementOpt.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Scott Kitterman
  • Date: 2010-03-12 11:30:04 UTC
  • mfrom: (0.41.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20100312113004-b0fop4bkycszdd0z
Tags: 0.96~rc1+dfsg-0ubuntu1
https://launchpad.net/bugs/537636
* New upstream RC - FFE (LP: #537636):
  - Add OfficialDatabaseOnly option to clamav-base.postinst.in
  - Add LocalSocketGroup option to clamav-base.postinst.in
  - Add LocalSocketMode option to clamav-base.postinst.in
  - Add CrossFilesystems option to clamav-base.postinst.in
  - Add ClamukoScannerCount option to clamav-base.postinst.in
  - Add BytecodeSecurity opiton to clamav-base.postinst.in
  - Add DetectionStatsHostID option to clamav-freshclam.postinst.in
  - Add Bytecode option to clamav-freshclam.postinst.in
  - Add MilterSocketGroup option to clamav-milter.postinst.in
  - Add MilterSocketMode option to clamav-milter.postinst.in
  - Add ReportHostname option to clamav-milter.postinst.in
  - Bump libclamav SO version to 6.1.0 in libclamav6.install
  - Drop clamdmon from clamav.examples (no longer shipped by upstream)
  - Drop libclamav.a from libclamav-dev.install (not built by upstream)
  - Update SO version for lintian override for libclamav6
  - Add new Bytecode Testing Tool, usr/bin/clambc, to clamav.install
  - Add build-depends on python and python-setuptools for new test suite
  - Update debian/copyright for the embedded copy of llvm (using the system
    llvm is not currently feasible)

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/lib/CodeGen/CodePlacementOpt.cpp
 
1
//===-- CodePlacementOpt.cpp - Code Placement pass. -----------------------===//
 
2
//
 
3
//                     The LLVM Compiler Infrastructure
 
4
//
 
5
// This file is distributed under the University of Illinois Open Source
 
6
// License. See LICENSE.TXT for details.
 
7
//
 
8
//===----------------------------------------------------------------------===//
 
9
//
 
10
// This file implements the pass that optimize code placement and align loop
 
11
// headers to target specific alignment boundary.
 
12
//
 
13
//===----------------------------------------------------------------------===//
 
14
 
 
15
#define DEBUG_TYPE "code-placement"
 
16
#include "llvm/CodeGen/MachineLoopInfo.h"
 
17
#include "llvm/CodeGen/MachineFunctionPass.h"
 
18
#include "llvm/CodeGen/Passes.h"
 
19
#include "llvm/Target/TargetInstrInfo.h"
 
20
#include "llvm/Target/TargetLowering.h"
 
21
#include "llvm/Target/TargetMachine.h"
 
22
#include "llvm/Support/Compiler.h"
 
23
#include "llvm/Support/Debug.h"
 
24
#include "llvm/ADT/Statistic.h"
 
25
using namespace llvm;
 
26
 
 
27
STATISTIC(NumLoopsAligned,  "Number of loops aligned");
 
28
STATISTIC(NumIntraElim,     "Number of intra loop branches eliminated");
 
29
STATISTIC(NumIntraMoved,    "Number of intra loop branches moved");
 
30
 
 
31
namespace {
 
32
  class CodePlacementOpt : public MachineFunctionPass {
 
33
    const MachineLoopInfo *MLI;
 
34
    const TargetInstrInfo *TII;
 
35
    const TargetLowering  *TLI;
 
36
 
 
37
  public:
 
38
    static char ID;
 
39
    CodePlacementOpt() : MachineFunctionPass(&ID) {}
 
40
 
 
41
    virtual bool runOnMachineFunction(MachineFunction &MF);
 
42
    virtual const char *getPassName() const {
 
43
      return "Code Placement Optimizater";
 
44
    }
 
45
 
 
46
    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 
47
      AU.addRequired<MachineLoopInfo>();
 
48
      AU.addPreservedID(MachineDominatorsID);
 
49
      MachineFunctionPass::getAnalysisUsage(AU);
 
50
    }
 
51
 
 
52
  private:
 
53
    bool HasFallthrough(MachineBasicBlock *MBB);
 
54
    bool HasAnalyzableTerminator(MachineBasicBlock *MBB);
 
55
    void Splice(MachineFunction &MF,
 
56
                MachineFunction::iterator InsertPt,
 
57
                MachineFunction::iterator Begin,
 
58
                MachineFunction::iterator End);
 
59
    bool EliminateUnconditionalJumpsToTop(MachineFunction &MF,
 
60
                                          MachineLoop *L);
 
61
    bool MoveDiscontiguousLoopBlocks(MachineFunction &MF,
 
62
                                     MachineLoop *L);
 
63
    bool OptimizeIntraLoopEdgesInLoopNest(MachineFunction &MF, MachineLoop *L);
 
64
    bool OptimizeIntraLoopEdges(MachineFunction &MF);
 
65
    bool AlignLoops(MachineFunction &MF);
 
66
    bool AlignLoop(MachineFunction &MF, MachineLoop *L, unsigned Align);
 
67
  };
 
68
 
 
69
  char CodePlacementOpt::ID = 0;
 
70
} // end anonymous namespace
 
71
 
 
72
FunctionPass *llvm::createCodePlacementOptPass() {
 
73
  return new CodePlacementOpt();
 
74
}
 
75
 
 
76
/// HasFallthrough - Test whether the given branch has a fallthrough, either as
 
77
/// a plain fallthrough or as a fallthrough case of a conditional branch.
 
78
///
 
79
bool CodePlacementOpt::HasFallthrough(MachineBasicBlock *MBB) {
 
80
  MachineBasicBlock *TBB = 0, *FBB = 0;
 
81
  SmallVector<MachineOperand, 4> Cond;
 
82
  if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond))
 
83
    return false;
 
84
  // This conditional branch has no fallthrough.
 
85
  if (FBB)
 
86
    return false;
 
87
  // An unconditional branch has no fallthrough.
 
88
  if (Cond.empty() && TBB)
 
89
    return false;
 
90
  // It has a fallthrough.
 
91
  return true;
 
92
}
 
93
 
 
94
/// HasAnalyzableTerminator - Test whether AnalyzeBranch will succeed on MBB.
 
95
/// This is called before major changes are begun to test whether it will be
 
96
/// possible to complete the changes.
 
97
///
 
98
/// Target-specific code is hereby encouraged to make AnalyzeBranch succeed
 
99
/// whenever possible.
 
100
///
 
101
bool CodePlacementOpt::HasAnalyzableTerminator(MachineBasicBlock *MBB) {
 
102
  // Conservatively ignore EH landing pads.
 
103
  if (MBB->isLandingPad()) return false;
 
104
 
 
105
  // Aggressively handle return blocks and similar constructs.
 
106
  if (MBB->succ_empty()) return true;
 
107
 
 
108
  // Ask the target's AnalyzeBranch if it can handle this block.
 
109
  MachineBasicBlock *TBB = 0, *FBB = 0;
 
110
  SmallVector<MachineOperand, 4> Cond;
 
111
  // Make sure the terminator is understood.
 
112
  if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond))
 
113
    return false;
 
114
   // Ignore blocks which look like they might have EH-related control flow.
 
115
   // AnalyzeBranch thinks it knows how to analyze such things, but it doesn't
 
116
   // recognize the possibility of a control transfer through an unwind.
 
117
   // Such blocks contain EH_LABEL instructions, however they may be in the
 
118
   // middle of the block. Instead of searching for them, just check to see
 
119
   // if the CFG disagrees with AnalyzeBranch.
 
120
  if (1u + !Cond.empty() != MBB->succ_size())
 
121
    return false;
 
122
  // Make sure we have the option of reversing the condition.
 
123
  if (!Cond.empty() && TII->ReverseBranchCondition(Cond))
 
124
    return false;
 
125
  return true;
 
126
}
 
127
 
 
128
/// Splice - Move the sequence of instructions [Begin,End) to just before
 
129
/// InsertPt. Update branch instructions as needed to account for broken
 
130
/// fallthrough edges and to take advantage of newly exposed fallthrough
 
131
/// opportunities.
 
132
///
 
133
void CodePlacementOpt::Splice(MachineFunction &MF,
 
134
                              MachineFunction::iterator InsertPt,
 
135
                              MachineFunction::iterator Begin,
 
136
                              MachineFunction::iterator End) {
 
137
  assert(Begin != MF.begin() && End != MF.begin() && InsertPt != MF.begin() &&
 
138
         "Splice can't change the entry block!");
 
139
  MachineFunction::iterator OldBeginPrior = prior(Begin);
 
140
  MachineFunction::iterator OldEndPrior = prior(End);
 
141
 
 
142
  MF.splice(InsertPt, Begin, End);
 
143
 
 
144
  prior(Begin)->updateTerminator();
 
145
  OldBeginPrior->updateTerminator();
 
146
  OldEndPrior->updateTerminator();
 
147
}
 
148
 
 
149
/// EliminateUnconditionalJumpsToTop - Move blocks which unconditionally jump
 
150
/// to the loop top to the top of the loop so that they have a fall through.
 
151
/// This can introduce a branch on entry to the loop, but it can eliminate a
 
152
/// branch within the loop. See the @simple case in
 
153
/// test/CodeGen/X86/loop_blocks.ll for an example of this.
 
154
bool CodePlacementOpt::EliminateUnconditionalJumpsToTop(MachineFunction &MF,
 
155
                                                        MachineLoop *L) {
 
156
  bool Changed = false;
 
157
  MachineBasicBlock *TopMBB = L->getTopBlock();
 
158
 
 
159
  bool BotHasFallthrough = HasFallthrough(L->getBottomBlock());
 
160
 
 
161
  if (TopMBB == MF.begin() ||
 
162
      HasAnalyzableTerminator(prior(MachineFunction::iterator(TopMBB)))) {
 
163
  new_top:
 
164
    for (MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin(),
 
165
         PE = TopMBB->pred_end(); PI != PE; ++PI) {
 
166
      MachineBasicBlock *Pred = *PI;
 
167
      if (Pred == TopMBB) continue;
 
168
      if (HasFallthrough(Pred)) continue;
 
169
      if (!L->contains(Pred)) continue;
 
170
 
 
171
      // Verify that we can analyze all the loop entry edges before beginning
 
172
      // any changes which will require us to be able to analyze them.
 
173
      if (Pred == MF.begin())
 
174
        continue;
 
175
      if (!HasAnalyzableTerminator(Pred))
 
176
        continue;
 
177
      if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(Pred))))
 
178
        continue;
 
179
 
 
180
      // Move the block.
 
181
      Changed = true;
 
182
 
 
183
      // Move it and all the blocks that can reach it via fallthrough edges
 
184
      // exclusively, to keep existing fallthrough edges intact.
 
185
      MachineFunction::iterator Begin = Pred;
 
186
      MachineFunction::iterator End = llvm::next(Begin);
 
187
      while (Begin != MF.begin()) {
 
188
        MachineFunction::iterator Prior = prior(Begin);
 
189
        if (Prior == MF.begin())
 
190
          break;
 
191
        // Stop when a non-fallthrough edge is found.
 
192
        if (!HasFallthrough(Prior))
 
193
          break;
 
194
        // Stop if a block which could fall-through out of the loop is found.
 
195
        if (Prior->isSuccessor(End))
 
196
          break;
 
197
        // If we've reached the top, stop scanning.
 
198
        if (Prior == MachineFunction::iterator(TopMBB)) {
 
199
          // We know top currently has a fall through (because we just checked
 
200
          // it) which would be lost if we do the transformation, so it isn't
 
201
          // worthwhile to do the transformation unless it would expose a new
 
202
          // fallthrough edge.
 
203
          if (!Prior->isSuccessor(End))
 
204
            goto next_pred;
 
205
          // Otherwise we can stop scanning and procede to move the blocks.
 
206
          break;
 
207
        }
 
208
        // If we hit a switch or something complicated, don't move anything
 
209
        // for this predecessor.
 
210
        if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(Prior))))
 
211
          break;
 
212
        // Ok, the block prior to Begin will be moved along with the rest.
 
213
        // Extend the range to include it.
 
214
        Begin = Prior;
 
215
        ++NumIntraMoved;
 
216
      }
 
217
 
 
218
      // Move the blocks.
 
219
      Splice(MF, TopMBB, Begin, End);
 
220
 
 
221
      // Update TopMBB.
 
222
      TopMBB = L->getTopBlock();
 
223
 
 
224
      // We have a new loop top. Iterate on it. We shouldn't have to do this
 
225
      // too many times if BranchFolding has done a reasonable job.
 
226
      goto new_top;
 
227
    next_pred:;
 
228
    }
 
229
  }
 
230
 
 
231
  // If the loop previously didn't exit with a fall-through and it now does,
 
232
  // we eliminated a branch.
 
233
  if (Changed &&
 
234
      !BotHasFallthrough &&
 
235
      HasFallthrough(L->getBottomBlock())) {
 
236
    ++NumIntraElim;
 
237
  }
 
238
 
 
239
  return Changed;
 
240
}
 
241
 
 
242
/// MoveDiscontiguousLoopBlocks - Move any loop blocks that are not in the
 
243
/// portion of the loop contiguous with the header. This usually makes the loop
 
244
/// contiguous, provided that AnalyzeBranch can handle all the relevant
 
245
/// branching. See the @cfg_islands case in test/CodeGen/X86/loop_blocks.ll
 
246
/// for an example of this.
 
247
bool CodePlacementOpt::MoveDiscontiguousLoopBlocks(MachineFunction &MF,
 
248
                                                   MachineLoop *L) {
 
249
  bool Changed = false;
 
250
  MachineBasicBlock *TopMBB = L->getTopBlock();
 
251
  MachineBasicBlock *BotMBB = L->getBottomBlock();
 
252
 
 
253
  // Determine a position to move orphaned loop blocks to. If TopMBB is not
 
254
  // entered via fallthrough and BotMBB is exited via fallthrough, prepend them
 
255
  // to the top of the loop to avoid loosing that fallthrough. Otherwise append
 
256
  // them to the bottom, even if it previously had a fallthrough, on the theory
 
257
  // that it's worth an extra branch to keep the loop contiguous.
 
258
  MachineFunction::iterator InsertPt =
 
259
    llvm::next(MachineFunction::iterator(BotMBB));
 
260
  bool InsertAtTop = false;
 
261
  if (TopMBB != MF.begin() &&
 
262
      !HasFallthrough(prior(MachineFunction::iterator(TopMBB))) &&
 
263
      HasFallthrough(BotMBB)) {
 
264
    InsertPt = TopMBB;
 
265
    InsertAtTop = true;
 
266
  }
 
267
 
 
268
  // Keep a record of which blocks are in the portion of the loop contiguous
 
269
  // with the loop header.
 
270
  SmallPtrSet<MachineBasicBlock *, 8> ContiguousBlocks;
 
271
  for (MachineFunction::iterator I = TopMBB,
 
272
       E = llvm::next(MachineFunction::iterator(BotMBB)); I != E; ++I)
 
273
    ContiguousBlocks.insert(I);
 
274
 
 
275
  // Find non-contigous blocks and fix them.
 
276
  if (InsertPt != MF.begin() && HasAnalyzableTerminator(prior(InsertPt)))
 
277
    for (MachineLoop::block_iterator BI = L->block_begin(), BE = L->block_end();
 
278
         BI != BE; ++BI) {
 
279
      MachineBasicBlock *BB = *BI;
 
280
 
 
281
      // Verify that we can analyze all the loop entry edges before beginning
 
282
      // any changes which will require us to be able to analyze them.
 
283
      if (!HasAnalyzableTerminator(BB))
 
284
        continue;
 
285
      if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(BB))))
 
286
        continue;
 
287
 
 
288
      // If the layout predecessor is part of the loop, this block will be
 
289
      // processed along with it. This keeps them in their relative order.
 
290
      if (BB != MF.begin() &&
 
291
          L->contains(prior(MachineFunction::iterator(BB))))
 
292
        continue;
 
293
 
 
294
      // Check to see if this block is already contiguous with the main
 
295
      // portion of the loop.
 
296
      if (!ContiguousBlocks.insert(BB))
 
297
        continue;
 
298
 
 
299
      // Move the block.
 
300
      Changed = true;
 
301
 
 
302
      // Process this block and all loop blocks contiguous with it, to keep
 
303
      // them in their relative order.
 
304
      MachineFunction::iterator Begin = BB;
 
305
      MachineFunction::iterator End = llvm::next(MachineFunction::iterator(BB));
 
306
      for (; End != MF.end(); ++End) {
 
307
        if (!L->contains(End)) break;
 
308
        if (!HasAnalyzableTerminator(End)) break;
 
309
        ContiguousBlocks.insert(End);
 
310
        ++NumIntraMoved;
 
311
      }
 
312
 
 
313
      // If we're inserting at the bottom of the loop, and the code we're
 
314
      // moving originally had fall-through successors, bring the sucessors
 
315
      // up with the loop blocks to preserve the fall-through edges.
 
316
      if (!InsertAtTop)
 
317
        for (; End != MF.end(); ++End) {
 
318
          if (L->contains(End)) break;
 
319
          if (!HasAnalyzableTerminator(End)) break;
 
320
          if (!HasFallthrough(prior(End))) break;
 
321
        }
 
322
 
 
323
      // Move the blocks. This may invalidate TopMBB and/or BotMBB, but
 
324
      // we don't need them anymore at this point.
 
325
      Splice(MF, InsertPt, Begin, End);
 
326
    }
 
327
 
 
328
  return Changed;
 
329
}
 
330
 
 
331
/// OptimizeIntraLoopEdgesInLoopNest - Reposition loop blocks to minimize
 
332
/// intra-loop branching and to form contiguous loops.
 
333
///
 
334
/// This code takes the approach of making minor changes to the existing
 
335
/// layout to fix specific loop-oriented problems. Also, it depends on
 
336
/// AnalyzeBranch, which can't understand complex control instructions.
 
337
///
 
338
bool CodePlacementOpt::OptimizeIntraLoopEdgesInLoopNest(MachineFunction &MF,
 
339
                                                        MachineLoop *L) {
 
340
  bool Changed = false;
 
341
 
 
342
  // Do optimization for nested loops.
 
343
  for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
 
344
    Changed |= OptimizeIntraLoopEdgesInLoopNest(MF, *I);
 
345
 
 
346
  // Do optimization for this loop.
 
347
  Changed |= EliminateUnconditionalJumpsToTop(MF, L);
 
348
  Changed |= MoveDiscontiguousLoopBlocks(MF, L);
 
349
 
 
350
  return Changed;
 
351
}
 
352
 
 
353
/// OptimizeIntraLoopEdges - Reposition loop blocks to minimize
 
354
/// intra-loop branching and to form contiguous loops.
 
355
///
 
356
bool CodePlacementOpt::OptimizeIntraLoopEdges(MachineFunction &MF) {
 
357
  bool Changed = false;
 
358
 
 
359
  if (!TLI->shouldOptimizeCodePlacement())
 
360
    return Changed;
 
361
 
 
362
  // Do optimization for each loop in the function.
 
363
  for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end();
 
364
       I != E; ++I)
 
365
    if (!(*I)->getParentLoop())
 
366
      Changed |= OptimizeIntraLoopEdgesInLoopNest(MF, *I);
 
367
 
 
368
  return Changed;
 
369
}
 
370
 
 
371
/// AlignLoops - Align loop headers to target preferred alignments.
 
372
///
 
373
bool CodePlacementOpt::AlignLoops(MachineFunction &MF) {
 
374
  const Function *F = MF.getFunction();
 
375
  if (F->hasFnAttr(Attribute::OptimizeForSize))
 
376
    return false;
 
377
 
 
378
  unsigned Align = TLI->getPrefLoopAlignment();
 
379
  if (!Align)
 
380
    return false;  // Don't care about loop alignment.
 
381
 
 
382
  bool Changed = false;
 
383
 
 
384
  for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end();
 
385
       I != E; ++I)
 
386
    Changed |= AlignLoop(MF, *I, Align);
 
387
 
 
388
  return Changed;
 
389
}
 
390
 
 
391
/// AlignLoop - Align loop headers to target preferred alignments.
 
392
///
 
393
bool CodePlacementOpt::AlignLoop(MachineFunction &MF, MachineLoop *L,
 
394
                                 unsigned Align) {
 
395
  bool Changed = false;
 
396
 
 
397
  // Do alignment for nested loops.
 
398
  for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
 
399
    Changed |= AlignLoop(MF, *I, Align);
 
400
 
 
401
  L->getTopBlock()->setAlignment(Align);
 
402
  Changed = true;
 
403
  ++NumLoopsAligned;
 
404
 
 
405
  return Changed;
 
406
}
 
407
 
 
408
bool CodePlacementOpt::runOnMachineFunction(MachineFunction &MF) {
 
409
  MLI = &getAnalysis<MachineLoopInfo>();
 
410
  if (MLI->empty())
 
411
    return false;  // No loops.
 
412
 
 
413
  TLI = MF.getTarget().getTargetLowering();
 
414
  TII = MF.getTarget().getInstrInfo();
 
415
 
 
416
  bool Changed = OptimizeIntraLoopEdges(MF);
 
417
 
 
418
  Changed |= AlignLoops(MF);
 
419
 
 
420
  return Changed;
 
421
}