← Back to branch summary

~ubuntu-branches/ubuntu/wily/clamav/wily-proposed

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/lib/Transforms/Utils/LoopSimplify.cpp

  • Committer: Package Import Robot
  • Author(s): Scott Kitterman, Sebastian Andrzej Siewior, Andreas Cadhalpun, Scott Kitterman, Javier Fernández-Sanguino
  • Date: 2015-01-28 00:25:13 UTC
  • mfrom: (0.48.14 sid)
  • Revision ID: package-import@ubuntu.com-20150128002513-lil2oi74cooy4lzr
Tags: 0.98.6+dfsg-1
http://bugs.debian.org/774686
http://bugs.debian.org/767350
http://bugs.debian.org/775400
http://bugs.debian.org/767353
http://bugs.debian.org/773563
[ Sebastian Andrzej Siewior ]
* update "fix-ssize_t-size_t-off_t-printf-modifier", include of misc.h was
  missing but was pulled in via the systemd patch.
* Don't leak return codes from libmspack to clamav API. (Closes: #774686).

[ Andreas Cadhalpun ]
* Add patch to avoid emitting incremental progress messages when not
  outputting to a terminal. (Closes: #767350)
* Update lintian-overrides for unused-file-paragraph-in-dep5-copyright.
* clamav-base.postinst: always chown /var/log/clamav and /var/lib/clamav
  to clamav:clamav, not only on fresh installations. (Closes: #775400)
* Adapt the clamav-daemon and clamav-freshclam logrotate scripts,
  so that they correctly work under systemd.
* Move the PidFile variable from the clamd/freshclam configuration files
  to the init scripts. This makes the init scripts more robust against
  misconfiguration and avoids error messages with systemd. (Closes: #767353)
* debian/copyright: drop files from Files-Excluded only present in github
  tarballs
* Drop Workaround-a-bug-in-libc-on-Hurd.patch, because hurd got fixed.
  (see #752237)
* debian/rules: Remove useless --with-system-tommath --without-included-ltdl
  configure options.

[ Scott Kitterman ]
* Stop stripping llvm when repacking the tarball as the system llvm on some
  releases is too old to use
* New upstream bugfix release
  - Library shared object revisions.
  - Includes a patch from Sebastian Andrzej Siewior making ClamAV pid files
    compatible with systemd.
  - Fix a heap out of bounds condition with crafted Yoda's crypter files.
    This issue was discovered by Felix Groebert of the Google Security Team.
  - Fix a heap out of bounds condition with crafted mew packer files. This
    issue was discovered by Felix Groebert of the Google Security Team.
  - Fix a heap out of bounds condition with crafted upx packer files. This
    issue was discovered by Kevin Szkudlapski of Quarkslab.
  - Fix a heap out of bounds condition with crafted upack packer files. This
    issue was discovered by Sebastian Andrzej Siewior. CVE-2014-9328.
  - Compensate a crash due to incorrect compiler optimization when handling
    crafted petite packer files. This issue was discovered by Sebastian
    Andrzej Siewior.
* Update lintian override for embedded zlib to match new so version

[ Javier Fernández-Sanguino ]
* Updated Spanish Debconf template translation (Closes: #773563)

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/lib/Transforms/Utils/LoopSimplify.cpp
 
1
//===- LoopSimplify.cpp - Loop Canonicalization 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 pass performs several transformations to transform natural loops into a
 
11
// simpler form, which makes subsequent analyses and transformations simpler and
 
12
// more effective.
 
13
//
 
14
// Loop pre-header insertion guarantees that there is a single, non-critical
 
15
// entry edge from outside of the loop to the loop header.  This simplifies a
 
16
// number of analyses and transformations, such as LICM.
 
17
//
 
18
// Loop exit-block insertion guarantees that all exit blocks from the loop
 
19
// (blocks which are outside of the loop that have predecessors inside of the
 
20
// loop) only have predecessors from inside of the loop (and are thus dominated
 
21
// by the loop header).  This simplifies transformations such as store-sinking
 
22
// that are built into LICM.
 
23
//
 
24
// This pass also guarantees that loops will have exactly one backedge.
 
25
//
 
26
// Indirectbr instructions introduce several complications. If the loop
 
27
// contains or is entered by an indirectbr instruction, it may not be possible
 
28
// to transform the loop and make these guarantees. Client code should check
 
29
// that these conditions are true before relying on them.
 
30
//
 
31
// Note that the simplifycfg pass will clean up blocks which are split out but
 
32
// end up being unnecessary, so usage of this pass should not pessimize
 
33
// generated code.
 
34
//
 
35
// This pass obviously modifies the CFG, but updates loop information and
 
36
// dominator information.
 
37
//
 
38
//===----------------------------------------------------------------------===//
 
39
 
 
40
#define DEBUG_TYPE "loopsimplify"
 
41
#include "llvm/Transforms/Scalar.h"
 
42
#include "llvm/Constants.h"
 
43
#include "llvm/Instructions.h"
 
44
#include "llvm/IntrinsicInst.h"
 
45
#include "llvm/Function.h"
 
46
#include "llvm/LLVMContext.h"
 
47
#include "llvm/Type.h"
 
48
#include "llvm/Analysis/AliasAnalysis.h"
 
49
#include "llvm/Analysis/ScalarEvolution.h"
 
50
#include "llvm/Analysis/Dominators.h"
 
51
#include "llvm/Analysis/LoopPass.h"
 
52
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
53
#include "llvm/Transforms/Utils/Local.h"
 
54
#include "llvm/Support/CFG.h"
 
55
#include "llvm/Support/Debug.h"
 
56
#include "llvm/ADT/SetOperations.h"
 
57
#include "llvm/ADT/SetVector.h"
 
58
#include "llvm/ADT/Statistic.h"
 
59
#include "llvm/ADT/DepthFirstIterator.h"
 
60
using namespace llvm;
 
61
 
 
62
STATISTIC(NumInserted, "Number of pre-header or exit blocks inserted");
 
63
STATISTIC(NumNested  , "Number of nested loops split out");
 
64
 
 
65
namespace {
 
66
  struct LoopSimplify : public LoopPass {
 
67
    static char ID; // Pass identification, replacement for typeid
 
68
    LoopSimplify() : LoopPass(ID) {}
 
69
 
 
70
    // AA - If we have an alias analysis object to update, this is it, otherwise
 
71
    // this is null.
 
72
    AliasAnalysis *AA;
 
73
    LoopInfo *LI;
 
74
    DominatorTree *DT;
 
75
    ScalarEvolution *SE;
 
76
    Loop *L;
 
77
    virtual bool runOnLoop(Loop *L, LPPassManager &LPM);
 
78
 
 
79
    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 
80
      // We need loop information to identify the loops...
 
81
      AU.addRequired<DominatorTree>();
 
82
      AU.addPreserved<DominatorTree>();
 
83
 
 
84
      AU.addRequired<LoopInfo>();
 
85
      AU.addPreserved<LoopInfo>();
 
86
 
 
87
      AU.addPreserved<AliasAnalysis>();
 
88
      AU.addPreserved<ScalarEvolution>();
 
89
      AU.addPreservedID(BreakCriticalEdgesID);  // No critical edges added.
 
90
      AU.addPreserved<DominanceFrontier>();
 
91
      AU.addPreservedID(LCSSAID);
 
92
    }
 
93
 
 
94
    /// verifyAnalysis() - Verify LoopSimplifyForm's guarantees.
 
95
    void verifyAnalysis() const;
 
96
 
 
97
  private:
 
98
    bool ProcessLoop(Loop *L, LPPassManager &LPM);
 
99
    BasicBlock *RewriteLoopExitBlock(Loop *L, BasicBlock *Exit);
 
100
    BasicBlock *InsertPreheaderForLoop(Loop *L);
 
101
    Loop *SeparateNestedLoop(Loop *L, LPPassManager &LPM);
 
102
    BasicBlock *InsertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader);
 
103
    void PlaceSplitBlockCarefully(BasicBlock *NewBB,
 
104
                                  SmallVectorImpl<BasicBlock*> &SplitPreds,
 
105
                                  Loop *L);
 
106
  };
 
107
}
 
108
 
 
109
char LoopSimplify::ID = 0;
 
110
INITIALIZE_PASS(LoopSimplify, "loopsimplify",
 
111
                "Canonicalize natural loops", true, false);
 
112
 
 
113
// Publically exposed interface to pass...
 
114
char &llvm::LoopSimplifyID = LoopSimplify::ID;
 
115
Pass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); }
 
116
 
 
117
/// runOnLoop - Run down all loops in the CFG (recursively, but we could do
 
118
/// it in any convenient order) inserting preheaders...
 
119
///
 
120
bool LoopSimplify::runOnLoop(Loop *l, LPPassManager &LPM) {
 
121
  L = l;
 
122
  bool Changed = false;
 
123
  LI = &getAnalysis<LoopInfo>();
 
124
  AA = getAnalysisIfAvailable<AliasAnalysis>();
 
125
  DT = &getAnalysis<DominatorTree>();
 
126
  SE = getAnalysisIfAvailable<ScalarEvolution>();
 
127
 
 
128
  Changed |= ProcessLoop(L, LPM);
 
129
 
 
130
  return Changed;
 
131
}
 
132
 
 
133
/// ProcessLoop - Walk the loop structure in depth first order, ensuring that
 
134
/// all loops have preheaders.
 
135
///
 
136
bool LoopSimplify::ProcessLoop(Loop *L, LPPassManager &LPM) {
 
137
  bool Changed = false;
 
138
ReprocessLoop:
 
139
 
 
140
  // Check to see that no blocks (other than the header) in this loop have
 
141
  // predecessors that are not in the loop.  This is not valid for natural
 
142
  // loops, but can occur if the blocks are unreachable.  Since they are
 
143
  // unreachable we can just shamelessly delete those CFG edges!
 
144
  for (Loop::block_iterator BB = L->block_begin(), E = L->block_end();
 
145
       BB != E; ++BB) {
 
146
    if (*BB == L->getHeader()) continue;
 
147
 
 
148
    SmallPtrSet<BasicBlock*, 4> BadPreds;
 
149
    for (pred_iterator PI = pred_begin(*BB),
 
150
         PE = pred_end(*BB); PI != PE; ++PI) {
 
151
      BasicBlock *P = *PI;
 
152
      if (!L->contains(P))
 
153
        BadPreds.insert(P);
 
154
    }
 
155
 
 
156
    // Delete each unique out-of-loop (and thus dead) predecessor.
 
157
    for (SmallPtrSet<BasicBlock*, 4>::iterator I = BadPreds.begin(),
 
158
         E = BadPreds.end(); I != E; ++I) {
 
159
 
 
160
      DEBUG(dbgs() << "LoopSimplify: Deleting edge from dead predecessor ";
 
161
            WriteAsOperand(dbgs(), *I, false);
 
162
            dbgs() << "\n");
 
163
 
 
164
      // Inform each successor of each dead pred.
 
165
      for (succ_iterator SI = succ_begin(*I), SE = succ_end(*I); SI != SE; ++SI)
 
166
        (*SI)->removePredecessor(*I);
 
167
      // Zap the dead pred's terminator and replace it with unreachable.
 
168
      TerminatorInst *TI = (*I)->getTerminator();
 
169
       TI->replaceAllUsesWith(UndefValue::get(TI->getType()));
 
170
      (*I)->getTerminator()->eraseFromParent();
 
171
      new UnreachableInst((*I)->getContext(), *I);
 
172
      Changed = true;
 
173
    }
 
174
  }
 
175
 
 
176
  // If there are exiting blocks with branches on undef, resolve the undef in
 
177
  // the direction which will exit the loop. This will help simplify loop
 
178
  // trip count computations.
 
179
  SmallVector<BasicBlock*, 8> ExitingBlocks;
 
180
  L->getExitingBlocks(ExitingBlocks);
 
181
  for (SmallVectorImpl<BasicBlock *>::iterator I = ExitingBlocks.begin(),
 
182
       E = ExitingBlocks.end(); I != E; ++I)
 
183
    if (BranchInst *BI = dyn_cast<BranchInst>((*I)->getTerminator()))
 
184
      if (BI->isConditional()) {
 
185
        if (UndefValue *Cond = dyn_cast<UndefValue>(BI->getCondition())) {
 
186
 
 
187
          DEBUG(dbgs() << "LoopSimplify: Resolving \"br i1 undef\" to exit in ";
 
188
                WriteAsOperand(dbgs(), *I, false);
 
189
                dbgs() << "\n");
 
190
 
 
191
          BI->setCondition(ConstantInt::get(Cond->getType(),
 
192
                                            !L->contains(BI->getSuccessor(0))));
 
193
          Changed = true;
 
194
        }
 
195
      }
 
196
 
 
197
  // Does the loop already have a preheader?  If so, don't insert one.
 
198
  BasicBlock *Preheader = L->getLoopPreheader();
 
199
  if (!Preheader) {
 
200
    Preheader = InsertPreheaderForLoop(L);
 
201
    if (Preheader) {
 
202
      ++NumInserted;
 
203
      Changed = true;
 
204
    }
 
205
  }
 
206
 
 
207
  // Next, check to make sure that all exit nodes of the loop only have
 
208
  // predecessors that are inside of the loop.  This check guarantees that the
 
209
  // loop preheader/header will dominate the exit blocks.  If the exit block has
 
210
  // predecessors from outside of the loop, split the edge now.
 
211
  SmallVector<BasicBlock*, 8> ExitBlocks;
 
212
  L->getExitBlocks(ExitBlocks);
 
213
    
 
214
  SmallSetVector<BasicBlock *, 8> ExitBlockSet(ExitBlocks.begin(),
 
215
                                               ExitBlocks.end());
 
216
  for (SmallSetVector<BasicBlock *, 8>::iterator I = ExitBlockSet.begin(),
 
217
         E = ExitBlockSet.end(); I != E; ++I) {
 
218
    BasicBlock *ExitBlock = *I;
 
219
    for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock);
 
220
         PI != PE; ++PI)
 
221
      // Must be exactly this loop: no subloops, parent loops, or non-loop preds
 
222
      // allowed.
 
223
      if (!L->contains(*PI)) {
 
224
        if (RewriteLoopExitBlock(L, ExitBlock)) {
 
225
          ++NumInserted;
 
226
          Changed = true;
 
227
        }
 
228
        break;
 
229
      }
 
230
  }
 
231
 
 
232
  // If the header has more than two predecessors at this point (from the
 
233
  // preheader and from multiple backedges), we must adjust the loop.
 
234
  BasicBlock *LoopLatch = L->getLoopLatch();
 
235
  if (!LoopLatch) {
 
236
    // If this is really a nested loop, rip it out into a child loop.  Don't do
 
237
    // this for loops with a giant number of backedges, just factor them into a
 
238
    // common backedge instead.
 
239
    if (L->getNumBackEdges() < 8) {
 
240
      if (SeparateNestedLoop(L, LPM)) {
 
241
        ++NumNested;
 
242
        // This is a big restructuring change, reprocess the whole loop.
 
243
        Changed = true;
 
244
        // GCC doesn't tail recursion eliminate this.
 
245
        goto ReprocessLoop;
 
246
      }
 
247
    }
 
248
 
 
249
    // If we either couldn't, or didn't want to, identify nesting of the loops,
 
250
    // insert a new block that all backedges target, then make it jump to the
 
251
    // loop header.
 
252
    LoopLatch = InsertUniqueBackedgeBlock(L, Preheader);
 
253
    if (LoopLatch) {
 
254
      ++NumInserted;
 
255
      Changed = true;
 
256
    }
 
257
  }
 
258
 
 
259
  // Scan over the PHI nodes in the loop header.  Since they now have only two
 
260
  // incoming values (the loop is canonicalized), we may have simplified the PHI
 
261
  // down to 'X = phi [X, Y]', which should be replaced with 'Y'.
 
262
  PHINode *PN;
 
263
  for (BasicBlock::iterator I = L->getHeader()->begin();
 
264
       (PN = dyn_cast<PHINode>(I++)); )
 
265
    if (Value *V = PN->hasConstantValue(DT)) {
 
266
      if (AA) AA->deleteValue(PN);
 
267
      PN->replaceAllUsesWith(V);
 
268
      PN->eraseFromParent();
 
269
    }
 
270
 
 
271
  // If this loop has multiple exits and the exits all go to the same
 
272
  // block, attempt to merge the exits. This helps several passes, such
 
273
  // as LoopRotation, which do not support loops with multiple exits.
 
274
  // SimplifyCFG also does this (and this code uses the same utility
 
275
  // function), however this code is loop-aware, where SimplifyCFG is
 
276
  // not. That gives it the advantage of being able to hoist
 
277
  // loop-invariant instructions out of the way to open up more
 
278
  // opportunities, and the disadvantage of having the responsibility
 
279
  // to preserve dominator information.
 
280
  bool UniqueExit = true;
 
281
  if (!ExitBlocks.empty())
 
282
    for (unsigned i = 1, e = ExitBlocks.size(); i != e; ++i)
 
283
      if (ExitBlocks[i] != ExitBlocks[0]) {
 
284
        UniqueExit = false;
 
285
        break;
 
286
      }
 
287
  if (UniqueExit) {
 
288
    for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
 
289
      BasicBlock *ExitingBlock = ExitingBlocks[i];
 
290
      if (!ExitingBlock->getSinglePredecessor()) continue;
 
291
      BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
 
292
      if (!BI || !BI->isConditional()) continue;
 
293
      CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition());
 
294
      if (!CI || CI->getParent() != ExitingBlock) continue;
 
295
 
 
296
      // Attempt to hoist out all instructions except for the
 
297
      // comparison and the branch.
 
298
      bool AllInvariant = true;
 
299
      for (BasicBlock::iterator I = ExitingBlock->begin(); &*I != BI; ) {
 
300
        Instruction *Inst = I++;
 
301
        // Skip debug info intrinsics.
 
302
        if (isa<DbgInfoIntrinsic>(Inst))
 
303
          continue;
 
304
        if (Inst == CI)
 
305
          continue;
 
306
        if (!L->makeLoopInvariant(Inst, Changed,
 
307
                                  Preheader ? Preheader->getTerminator() : 0)) {
 
308
          AllInvariant = false;
 
309
          break;
 
310
        }
 
311
      }
 
312
      if (!AllInvariant) continue;
 
313
 
 
314
      // The block has now been cleared of all instructions except for
 
315
      // a comparison and a conditional branch. SimplifyCFG may be able
 
316
      // to fold it now.
 
317
      if (!FoldBranchToCommonDest(BI)) continue;
 
318
 
 
319
      // Success. The block is now dead, so remove it from the loop,
 
320
      // update the dominator tree and dominance frontier, and delete it.
 
321
 
 
322
      DEBUG(dbgs() << "LoopSimplify: Eliminating exiting block ";
 
323
            WriteAsOperand(dbgs(), ExitingBlock, false);
 
324
            dbgs() << "\n");
 
325
 
 
326
      assert(pred_begin(ExitingBlock) == pred_end(ExitingBlock));
 
327
      Changed = true;
 
328
      LI->removeBlock(ExitingBlock);
 
329
 
 
330
      DominanceFrontier *DF = getAnalysisIfAvailable<DominanceFrontier>();
 
331
      DomTreeNode *Node = DT->getNode(ExitingBlock);
 
332
      const std::vector<DomTreeNodeBase<BasicBlock> *> &Children =
 
333
        Node->getChildren();
 
334
      while (!Children.empty()) {
 
335
        DomTreeNode *Child = Children.front();
 
336
        DT->changeImmediateDominator(Child, Node->getIDom());
 
337
        if (DF) DF->changeImmediateDominator(Child->getBlock(),
 
338
                                             Node->getIDom()->getBlock(),
 
339
                                             DT);
 
340
      }
 
341
      DT->eraseNode(ExitingBlock);
 
342
      if (DF) DF->removeBlock(ExitingBlock);
 
343
 
 
344
      BI->getSuccessor(0)->removePredecessor(ExitingBlock);
 
345
      BI->getSuccessor(1)->removePredecessor(ExitingBlock);
 
346
      ExitingBlock->eraseFromParent();
 
347
    }
 
348
  }
 
349
 
 
350
  return Changed;
 
351
}
 
352
 
 
353
/// InsertPreheaderForLoop - Once we discover that a loop doesn't have a
 
354
/// preheader, this method is called to insert one.  This method has two phases:
 
355
/// preheader insertion and analysis updating.
 
356
///
 
357
BasicBlock *LoopSimplify::InsertPreheaderForLoop(Loop *L) {
 
358
  BasicBlock *Header = L->getHeader();
 
359
 
 
360
  // Compute the set of predecessors of the loop that are not in the loop.
 
361
  SmallVector<BasicBlock*, 8> OutsideBlocks;
 
362
  for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header);
 
363
       PI != PE; ++PI) {
 
364
    BasicBlock *P = *PI;
 
365
    if (!L->contains(P)) {         // Coming in from outside the loop?
 
366
      // If the loop is branched to from an indirect branch, we won't
 
367
      // be able to fully transform the loop, because it prohibits
 
368
      // edge splitting.
 
369
      if (isa<IndirectBrInst>(P->getTerminator())) return 0;
 
370
 
 
371
      // Keep track of it.
 
372
      OutsideBlocks.push_back(P);
 
373
    }
 
374
  }
 
375
 
 
376
  // Split out the loop pre-header.
 
377
  BasicBlock *NewBB =
 
378
    SplitBlockPredecessors(Header, &OutsideBlocks[0], OutsideBlocks.size(),
 
379
                           ".preheader", this);
 
380
 
 
381
  DEBUG(dbgs() << "LoopSimplify: Creating pre-header ";
 
382
        WriteAsOperand(dbgs(), NewBB, false);
 
383
        dbgs() << "\n");
 
384
 
 
385
  // Make sure that NewBB is put someplace intelligent, which doesn't mess up
 
386
  // code layout too horribly.
 
387
  PlaceSplitBlockCarefully(NewBB, OutsideBlocks, L);
 
388
 
 
389
  return NewBB;
 
390
}
 
391
 
 
392
/// RewriteLoopExitBlock - Ensure that the loop preheader dominates all exit
 
393
/// blocks.  This method is used to split exit blocks that have predecessors
 
394
/// outside of the loop.
 
395
BasicBlock *LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) {
 
396
  SmallVector<BasicBlock*, 8> LoopBlocks;
 
397
  for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) {
 
398
    BasicBlock *P = *I;
 
399
    if (L->contains(P)) {
 
400
      // Don't do this if the loop is exited via an indirect branch.
 
401
      if (isa<IndirectBrInst>(P->getTerminator())) return 0;
 
402
 
 
403
      LoopBlocks.push_back(P);
 
404
    }
 
405
  }
 
406
 
 
407
  assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?");
 
408
  BasicBlock *NewBB = SplitBlockPredecessors(Exit, &LoopBlocks[0], 
 
409
                                             LoopBlocks.size(), ".loopexit",
 
410
                                             this);
 
411
 
 
412
  DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block ";
 
413
        WriteAsOperand(dbgs(), NewBB, false);
 
414
        dbgs() << "\n");
 
415
 
 
416
  return NewBB;
 
417
}
 
418
 
 
419
/// AddBlockAndPredsToSet - Add the specified block, and all of its
 
420
/// predecessors, to the specified set, if it's not already in there.  Stop
 
421
/// predecessor traversal when we reach StopBlock.
 
422
static void AddBlockAndPredsToSet(BasicBlock *InputBB, BasicBlock *StopBlock,
 
423
                                  std::set<BasicBlock*> &Blocks) {
 
424
  std::vector<BasicBlock *> WorkList;
 
425
  WorkList.push_back(InputBB);
 
426
  do {
 
427
    BasicBlock *BB = WorkList.back(); WorkList.pop_back();
 
428
    if (Blocks.insert(BB).second && BB != StopBlock)
 
429
      // If BB is not already processed and it is not a stop block then
 
430
      // insert its predecessor in the work list
 
431
      for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) {
 
432
        BasicBlock *WBB = *I;
 
433
        WorkList.push_back(WBB);
 
434
      }
 
435
  } while(!WorkList.empty());
 
436
}
 
437
 
 
438
/// FindPHIToPartitionLoops - The first part of loop-nestification is to find a
 
439
/// PHI node that tells us how to partition the loops.
 
440
static PHINode *FindPHIToPartitionLoops(Loop *L, DominatorTree *DT,
 
441
                                        AliasAnalysis *AA) {
 
442
  for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ) {
 
443
    PHINode *PN = cast<PHINode>(I);
 
444
    ++I;
 
445
    if (Value *V = PN->hasConstantValue(DT)) {
 
446
      // This is a degenerate PHI already, don't modify it!
 
447
      PN->replaceAllUsesWith(V);
 
448
      if (AA) AA->deleteValue(PN);
 
449
      PN->eraseFromParent();
 
450
      continue;
 
451
    }
 
452
 
 
453
    // Scan this PHI node looking for a use of the PHI node by itself.
 
454
    for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
 
455
      if (PN->getIncomingValue(i) == PN &&
 
456
          L->contains(PN->getIncomingBlock(i)))
 
457
        // We found something tasty to remove.
 
458
        return PN;
 
459
  }
 
460
  return 0;
 
461
}
 
462
 
 
463
// PlaceSplitBlockCarefully - If the block isn't already, move the new block to
 
464
// right after some 'outside block' block.  This prevents the preheader from
 
465
// being placed inside the loop body, e.g. when the loop hasn't been rotated.
 
466
void LoopSimplify::PlaceSplitBlockCarefully(BasicBlock *NewBB,
 
467
                                       SmallVectorImpl<BasicBlock*> &SplitPreds,
 
468
                                            Loop *L) {
 
469
  // Check to see if NewBB is already well placed.
 
470
  Function::iterator BBI = NewBB; --BBI;
 
471
  for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) {
 
472
    if (&*BBI == SplitPreds[i])
 
473
      return;
 
474
  }
 
475
  
 
476
  // If it isn't already after an outside block, move it after one.  This is
 
477
  // always good as it makes the uncond branch from the outside block into a
 
478
  // fall-through.
 
479
  
 
480
  // Figure out *which* outside block to put this after.  Prefer an outside
 
481
  // block that neighbors a BB actually in the loop.
 
482
  BasicBlock *FoundBB = 0;
 
483
  for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) {
 
484
    Function::iterator BBI = SplitPreds[i];
 
485
    if (++BBI != NewBB->getParent()->end() && 
 
486
        L->contains(BBI)) {
 
487
      FoundBB = SplitPreds[i];
 
488
      break;
 
489
    }
 
490
  }
 
491
  
 
492
  // If our heuristic for a *good* bb to place this after doesn't find
 
493
  // anything, just pick something.  It's likely better than leaving it within
 
494
  // the loop.
 
495
  if (!FoundBB)
 
496
    FoundBB = SplitPreds[0];
 
497
  NewBB->moveAfter(FoundBB);
 
498
}
 
499
 
 
500
 
 
501
/// SeparateNestedLoop - If this loop has multiple backedges, try to pull one of
 
502
/// them out into a nested loop.  This is important for code that looks like
 
503
/// this:
 
504
///
 
505
///  Loop:
 
506
///     ...
 
507
///     br cond, Loop, Next
 
508
///     ...
 
509
///     br cond2, Loop, Out
 
510
///
 
511
/// To identify this common case, we look at the PHI nodes in the header of the
 
512
/// loop.  PHI nodes with unchanging values on one backedge correspond to values
 
513
/// that change in the "outer" loop, but not in the "inner" loop.
 
514
///
 
515
/// If we are able to separate out a loop, return the new outer loop that was
 
516
/// created.
 
517
///
 
518
Loop *LoopSimplify::SeparateNestedLoop(Loop *L, LPPassManager &LPM) {
 
519
  PHINode *PN = FindPHIToPartitionLoops(L, DT, AA);
 
520
  if (PN == 0) return 0;  // No known way to partition.
 
521
 
 
522
  // Pull out all predecessors that have varying values in the loop.  This
 
523
  // handles the case when a PHI node has multiple instances of itself as
 
524
  // arguments.
 
525
  SmallVector<BasicBlock*, 8> OuterLoopPreds;
 
526
  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
 
527
    if (PN->getIncomingValue(i) != PN ||
 
528
        !L->contains(PN->getIncomingBlock(i))) {
 
529
      // We can't split indirectbr edges.
 
530
      if (isa<IndirectBrInst>(PN->getIncomingBlock(i)->getTerminator()))
 
531
        return 0;
 
532
 
 
533
      OuterLoopPreds.push_back(PN->getIncomingBlock(i));
 
534
    }
 
535
 
 
536
  DEBUG(dbgs() << "LoopSimplify: Splitting out a new outer loop\n");
 
537
 
 
538
  // If ScalarEvolution is around and knows anything about values in
 
539
  // this loop, tell it to forget them, because we're about to
 
540
  // substantially change it.
 
541
  if (SE)
 
542
    SE->forgetLoop(L);
 
543
 
 
544
  BasicBlock *Header = L->getHeader();
 
545
  BasicBlock *NewBB = SplitBlockPredecessors(Header, &OuterLoopPreds[0],
 
546
                                             OuterLoopPreds.size(),
 
547
                                             ".outer", this);
 
548
 
 
549
  // Make sure that NewBB is put someplace intelligent, which doesn't mess up
 
550
  // code layout too horribly.
 
551
  PlaceSplitBlockCarefully(NewBB, OuterLoopPreds, L);
 
552
  
 
553
  // Create the new outer loop.
 
554
  Loop *NewOuter = new Loop();
 
555
 
 
556
  // Change the parent loop to use the outer loop as its child now.
 
557
  if (Loop *Parent = L->getParentLoop())
 
558
    Parent->replaceChildLoopWith(L, NewOuter);
 
559
  else
 
560
    LI->changeTopLevelLoop(L, NewOuter);
 
561
 
 
562
  // L is now a subloop of our outer loop.
 
563
  NewOuter->addChildLoop(L);
 
564
 
 
565
  // Add the new loop to the pass manager queue.
 
566
  LPM.insertLoopIntoQueue(NewOuter);
 
567
 
 
568
  for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
 
569
       I != E; ++I)
 
570
    NewOuter->addBlockEntry(*I);
 
571
 
 
572
  // Now reset the header in L, which had been moved by
 
573
  // SplitBlockPredecessors for the outer loop.
 
574
  L->moveToHeader(Header);
 
575
 
 
576
  // Determine which blocks should stay in L and which should be moved out to
 
577
  // the Outer loop now.
 
578
  std::set<BasicBlock*> BlocksInL;
 
579
  for (pred_iterator PI=pred_begin(Header), E = pred_end(Header); PI!=E; ++PI) {
 
580
    BasicBlock *P = *PI;
 
581
    if (DT->dominates(Header, P))
 
582
      AddBlockAndPredsToSet(P, Header, BlocksInL);
 
583
  }
 
584
 
 
585
  // Scan all of the loop children of L, moving them to OuterLoop if they are
 
586
  // not part of the inner loop.
 
587
  const std::vector<Loop*> &SubLoops = L->getSubLoops();
 
588
  for (size_t I = 0; I != SubLoops.size(); )
 
589
    if (BlocksInL.count(SubLoops[I]->getHeader()))
 
590
      ++I;   // Loop remains in L
 
591
    else
 
592
      NewOuter->addChildLoop(L->removeChildLoop(SubLoops.begin() + I));
 
593
 
 
594
  // Now that we know which blocks are in L and which need to be moved to
 
595
  // OuterLoop, move any blocks that need it.
 
596
  for (unsigned i = 0; i != L->getBlocks().size(); ++i) {
 
597
    BasicBlock *BB = L->getBlocks()[i];
 
598
    if (!BlocksInL.count(BB)) {
 
599
      // Move this block to the parent, updating the exit blocks sets
 
600
      L->removeBlockFromLoop(BB);
 
601
      if ((*LI)[BB] == L)
 
602
        LI->changeLoopFor(BB, NewOuter);
 
603
      --i;
 
604
    }
 
605
  }
 
606
 
 
607
  return NewOuter;
 
608
}
 
609
 
 
610
 
 
611
 
 
612
/// InsertUniqueBackedgeBlock - This method is called when the specified loop
 
613
/// has more than one backedge in it.  If this occurs, revector all of these
 
614
/// backedges to target a new basic block and have that block branch to the loop
 
615
/// header.  This ensures that loops have exactly one backedge.
 
616
///
 
617
BasicBlock *
 
618
LoopSimplify::InsertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader) {
 
619
  assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!");
 
620
 
 
621
  // Get information about the loop
 
622
  BasicBlock *Header = L->getHeader();
 
623
  Function *F = Header->getParent();
 
624
 
 
625
  // Unique backedge insertion currently depends on having a preheader.
 
626
  if (!Preheader)
 
627
    return 0;
 
628
 
 
629
  // Figure out which basic blocks contain back-edges to the loop header.
 
630
  std::vector<BasicBlock*> BackedgeBlocks;
 
631
  for (pred_iterator I = pred_begin(Header), E = pred_end(Header); I != E; ++I){
 
632
    BasicBlock *P = *I;
 
633
 
 
634
    // Indirectbr edges cannot be split, so we must fail if we find one.
 
635
    if (isa<IndirectBrInst>(P->getTerminator()))
 
636
      return 0;
 
637
 
 
638
    if (P != Preheader) BackedgeBlocks.push_back(P);
 
639
  }
 
640
 
 
641
  // Create and insert the new backedge block...
 
642
  BasicBlock *BEBlock = BasicBlock::Create(Header->getContext(),
 
643
                                           Header->getName()+".backedge", F);
 
644
  BranchInst *BETerminator = BranchInst::Create(Header, BEBlock);
 
645
 
 
646
  DEBUG(dbgs() << "LoopSimplify: Inserting unique backedge block ";
 
647
        WriteAsOperand(dbgs(), BEBlock, false);
 
648
        dbgs() << "\n");
 
649
 
 
650
  // Move the new backedge block to right after the last backedge block.
 
651
  Function::iterator InsertPos = BackedgeBlocks.back(); ++InsertPos;
 
652
  F->getBasicBlockList().splice(InsertPos, F->getBasicBlockList(), BEBlock);
 
653
 
 
654
  // Now that the block has been inserted into the function, create PHI nodes in
 
655
  // the backedge block which correspond to any PHI nodes in the header block.
 
656
  for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
 
657
    PHINode *PN = cast<PHINode>(I);
 
658
    PHINode *NewPN = PHINode::Create(PN->getType(), PN->getName()+".be",
 
659
                                     BETerminator);
 
660
    NewPN->reserveOperandSpace(BackedgeBlocks.size());
 
661
    if (AA) AA->copyValue(PN, NewPN);
 
662
 
 
663
    // Loop over the PHI node, moving all entries except the one for the
 
664
    // preheader over to the new PHI node.
 
665
    unsigned PreheaderIdx = ~0U;
 
666
    bool HasUniqueIncomingValue = true;
 
667
    Value *UniqueValue = 0;
 
668
    for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 
669
      BasicBlock *IBB = PN->getIncomingBlock(i);
 
670
      Value *IV = PN->getIncomingValue(i);
 
671
      if (IBB == Preheader) {
 
672
        PreheaderIdx = i;
 
673
      } else {
 
674
        NewPN->addIncoming(IV, IBB);
 
675
        if (HasUniqueIncomingValue) {
 
676
          if (UniqueValue == 0)
 
677
            UniqueValue = IV;
 
678
          else if (UniqueValue != IV)
 
679
            HasUniqueIncomingValue = false;
 
680
        }
 
681
      }
 
682
    }
 
683
 
 
684
    // Delete all of the incoming values from the old PN except the preheader's
 
685
    assert(PreheaderIdx != ~0U && "PHI has no preheader entry??");
 
686
    if (PreheaderIdx != 0) {
 
687
      PN->setIncomingValue(0, PN->getIncomingValue(PreheaderIdx));
 
688
      PN->setIncomingBlock(0, PN->getIncomingBlock(PreheaderIdx));
 
689
    }
 
690
    // Nuke all entries except the zero'th.
 
691
    for (unsigned i = 0, e = PN->getNumIncomingValues()-1; i != e; ++i)
 
692
      PN->removeIncomingValue(e-i, false);
 
693
 
 
694
    // Finally, add the newly constructed PHI node as the entry for the BEBlock.
 
695
    PN->addIncoming(NewPN, BEBlock);
 
696
 
 
697
    // As an optimization, if all incoming values in the new PhiNode (which is a
 
698
    // subset of the incoming values of the old PHI node) have the same value,
 
699
    // eliminate the PHI Node.
 
700
    if (HasUniqueIncomingValue) {
 
701
      NewPN->replaceAllUsesWith(UniqueValue);
 
702
      if (AA) AA->deleteValue(NewPN);
 
703
      BEBlock->getInstList().erase(NewPN);
 
704
    }
 
705
  }
 
706
 
 
707
  // Now that all of the PHI nodes have been inserted and adjusted, modify the
 
708
  // backedge blocks to just to the BEBlock instead of the header.
 
709
  for (unsigned i = 0, e = BackedgeBlocks.size(); i != e; ++i) {
 
710
    TerminatorInst *TI = BackedgeBlocks[i]->getTerminator();
 
711
    for (unsigned Op = 0, e = TI->getNumSuccessors(); Op != e; ++Op)
 
712
      if (TI->getSuccessor(Op) == Header)
 
713
        TI->setSuccessor(Op, BEBlock);
 
714
  }
 
715
 
 
716
  //===--- Update all analyses which we must preserve now -----------------===//
 
717
 
 
718
  // Update Loop Information - we know that this block is now in the current
 
719
  // loop and all parent loops.
 
720
  L->addBasicBlockToLoop(BEBlock, LI->getBase());
 
721
 
 
722
  // Update dominator information
 
723
  DT->splitBlock(BEBlock);
 
724
  if (DominanceFrontier *DF = getAnalysisIfAvailable<DominanceFrontier>())
 
725
    DF->splitBlock(BEBlock);
 
726
 
 
727
  return BEBlock;
 
728
}
 
729
 
 
730
void LoopSimplify::verifyAnalysis() const {
 
731
  // It used to be possible to just assert L->isLoopSimplifyForm(), however
 
732
  // with the introduction of indirectbr, there are now cases where it's
 
733
  // not possible to transform a loop as necessary. We can at least check
 
734
  // that there is an indirectbr near any time there's trouble.
 
735
 
 
736
  // Indirectbr can interfere with preheader and unique backedge insertion.
 
737
  if (!L->getLoopPreheader() || !L->getLoopLatch()) {
 
738
    bool HasIndBrPred = false;
 
739
    for (pred_iterator PI = pred_begin(L->getHeader()),
 
740
         PE = pred_end(L->getHeader()); PI != PE; ++PI)
 
741
      if (isa<IndirectBrInst>((*PI)->getTerminator())) {
 
742
        HasIndBrPred = true;
 
743
        break;
 
744
      }
 
745
    assert(HasIndBrPred &&
 
746
           "LoopSimplify has no excuse for missing loop header info!");
 
747
  }
 
748
 
 
749
  // Indirectbr can interfere with exit block canonicalization.
 
750
  if (!L->hasDedicatedExits()) {
 
751
    bool HasIndBrExiting = false;
 
752
    SmallVector<BasicBlock*, 8> ExitingBlocks;
 
753
    L->getExitingBlocks(ExitingBlocks);
 
754
    for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i)
 
755
      if (isa<IndirectBrInst>((ExitingBlocks[i])->getTerminator())) {
 
756
        HasIndBrExiting = true;
 
757
        break;
 
758
      }
 
759
    assert(HasIndBrExiting &&
 
760
           "LoopSimplify has no excuse for missing exit block info!");
 
761
  }
 
762
}