← 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/Transforms/Scalar/LoopUnswitch.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/Transforms/Scalar/LoopUnswitch.cpp
 
1
//===-- LoopUnswitch.cpp - Hoist loop-invariant conditionals in loop ------===//
 
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 transforms loops that contain branches on loop-invariant conditions
 
11
// to have multiple loops.  For example, it turns the left into the right code:
 
12
//
 
13
//  for (...)                  if (lic)
 
14
//    A                          for (...)
 
15
//    if (lic)                     A; B; C
 
16
//      B                      else
 
17
//    C                          for (...)
 
18
//                                 A; C
 
19
//
 
20
// This can increase the size of the code exponentially (doubling it every time
 
21
// a loop is unswitched) so we only unswitch if the resultant code will be
 
22
// smaller than a threshold.
 
23
//
 
24
// This pass expects LICM to be run before it to hoist invariant conditions out
 
25
// of the loop, to make the unswitching opportunity obvious.
 
26
//
 
27
//===----------------------------------------------------------------------===//
 
28
 
 
29
#define DEBUG_TYPE "loop-unswitch"
 
30
#include "llvm/Transforms/Scalar.h"
 
31
#include "llvm/Constants.h"
 
32
#include "llvm/DerivedTypes.h"
 
33
#include "llvm/Function.h"
 
34
#include "llvm/Instructions.h"
 
35
#include "llvm/Analysis/ConstantFolding.h"
 
36
#include "llvm/Analysis/InlineCost.h"
 
37
#include "llvm/Analysis/LoopInfo.h"
 
38
#include "llvm/Analysis/LoopPass.h"
 
39
#include "llvm/Analysis/Dominators.h"
 
40
#include "llvm/Transforms/Utils/Cloning.h"
 
41
#include "llvm/Transforms/Utils/Local.h"
 
42
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
43
#include "llvm/ADT/Statistic.h"
 
44
#include "llvm/ADT/SmallPtrSet.h"
 
45
#include "llvm/ADT/STLExtras.h"
 
46
#include "llvm/Support/CommandLine.h"
 
47
#include "llvm/Support/Debug.h"
 
48
#include "llvm/Support/raw_ostream.h"
 
49
#include <algorithm>
 
50
#include <set>
 
51
using namespace llvm;
 
52
 
 
53
STATISTIC(NumBranches, "Number of branches unswitched");
 
54
STATISTIC(NumSwitches, "Number of switches unswitched");
 
55
STATISTIC(NumSelects , "Number of selects unswitched");
 
56
STATISTIC(NumTrivial , "Number of unswitches that are trivial");
 
57
STATISTIC(NumSimplify, "Number of simplifications of unswitched code");
 
58
 
 
59
// The specific value of 50 here was chosen based only on intuition and a
 
60
// few specific examples.
 
61
static cl::opt<unsigned>
 
62
Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"),
 
63
          cl::init(50), cl::Hidden);
 
64
  
 
65
namespace {
 
66
  class LoopUnswitch : public LoopPass {
 
67
    LoopInfo *LI;  // Loop information
 
68
    LPPassManager *LPM;
 
69
 
 
70
    // LoopProcessWorklist - Used to check if second loop needs processing
 
71
    // after RewriteLoopBodyWithConditionConstant rewrites first loop.
 
72
    std::vector<Loop*> LoopProcessWorklist;
 
73
    SmallPtrSet<Value *,8> UnswitchedVals;
 
74
    
 
75
    bool OptimizeForSize;
 
76
    bool redoLoop;
 
77
 
 
78
    Loop *currentLoop;
 
79
    DominanceFrontier *DF;
 
80
    DominatorTree *DT;
 
81
    BasicBlock *loopHeader;
 
82
    BasicBlock *loopPreheader;
 
83
    
 
84
    // LoopBlocks contains all of the basic blocks of the loop, including the
 
85
    // preheader of the loop, the body of the loop, and the exit blocks of the 
 
86
    // loop, in that order.
 
87
    std::vector<BasicBlock*> LoopBlocks;
 
88
    // NewBlocks contained cloned copy of basic blocks from LoopBlocks.
 
89
    std::vector<BasicBlock*> NewBlocks;
 
90
 
 
91
  public:
 
92
    static char ID; // Pass ID, replacement for typeid
 
93
    explicit LoopUnswitch(bool Os = false) : 
 
94
      LoopPass(&ID), OptimizeForSize(Os), redoLoop(false), 
 
95
      currentLoop(NULL), DF(NULL), DT(NULL), loopHeader(NULL),
 
96
      loopPreheader(NULL) {}
 
97
 
 
98
    bool runOnLoop(Loop *L, LPPassManager &LPM);
 
99
    bool processCurrentLoop();
 
100
 
 
101
    /// This transformation requires natural loop information & requires that
 
102
    /// loop preheaders be inserted into the CFG...
 
103
    ///
 
104
    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 
105
      AU.addRequiredID(LoopSimplifyID);
 
106
      AU.addPreservedID(LoopSimplifyID);
 
107
      AU.addRequired<LoopInfo>();
 
108
      AU.addPreserved<LoopInfo>();
 
109
      AU.addRequiredID(LCSSAID);
 
110
      AU.addPreservedID(LCSSAID);
 
111
      AU.addPreserved<DominatorTree>();
 
112
      AU.addPreserved<DominanceFrontier>();
 
113
    }
 
114
 
 
115
  private:
 
116
 
 
117
    virtual void releaseMemory() {
 
118
      UnswitchedVals.clear();
 
119
    }
 
120
 
 
121
    /// RemoveLoopFromWorklist - If the specified loop is on the loop worklist,
 
122
    /// remove it.
 
123
    void RemoveLoopFromWorklist(Loop *L) {
 
124
      std::vector<Loop*>::iterator I = std::find(LoopProcessWorklist.begin(),
 
125
                                                 LoopProcessWorklist.end(), L);
 
126
      if (I != LoopProcessWorklist.end())
 
127
        LoopProcessWorklist.erase(I);
 
128
    }
 
129
 
 
130
    void initLoopData() {
 
131
      loopHeader = currentLoop->getHeader();
 
132
      loopPreheader = currentLoop->getLoopPreheader();
 
133
    }
 
134
 
 
135
    /// Split all of the edges from inside the loop to their exit blocks.
 
136
    /// Update the appropriate Phi nodes as we do so.
 
137
    void SplitExitEdges(Loop *L, const SmallVector<BasicBlock *, 8> &ExitBlocks);
 
138
 
 
139
    bool UnswitchIfProfitable(Value *LoopCond, Constant *Val);
 
140
    void UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val,
 
141
                                  BasicBlock *ExitBlock);
 
142
    void UnswitchNontrivialCondition(Value *LIC, Constant *OnVal, Loop *L);
 
143
 
 
144
    void RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC,
 
145
                                              Constant *Val, bool isEqual);
 
146
 
 
147
    void EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val,
 
148
                                        BasicBlock *TrueDest, 
 
149
                                        BasicBlock *FalseDest,
 
150
                                        Instruction *InsertPt);
 
151
 
 
152
    void SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L);
 
153
    void RemoveBlockIfDead(BasicBlock *BB,
 
154
                           std::vector<Instruction*> &Worklist, Loop *l);
 
155
    void RemoveLoopFromHierarchy(Loop *L);
 
156
    bool IsTrivialUnswitchCondition(Value *Cond, Constant **Val = 0,
 
157
                                    BasicBlock **LoopExit = 0);
 
158
 
 
159
  };
 
160
}
 
161
char LoopUnswitch::ID = 0;
 
162
static RegisterPass<LoopUnswitch> X("loop-unswitch", "Unswitch loops");
 
163
 
 
164
Pass *llvm::createLoopUnswitchPass(bool Os) { 
 
165
  return new LoopUnswitch(Os); 
 
166
}
 
167
 
 
168
/// FindLIVLoopCondition - Cond is a condition that occurs in L.  If it is
 
169
/// invariant in the loop, or has an invariant piece, return the invariant.
 
170
/// Otherwise, return null.
 
171
static Value *FindLIVLoopCondition(Value *Cond, Loop *L, bool &Changed) {
 
172
  // We can never unswitch on vector conditions.
 
173
  if (Cond->getType()->isVectorTy())
 
174
    return 0;
 
175
 
 
176
  // Constants should be folded, not unswitched on!
 
177
  if (isa<Constant>(Cond)) return 0;
 
178
 
 
179
  // TODO: Handle: br (VARIANT|INVARIANT).
 
180
 
 
181
  // Hoist simple values out.
 
182
  if (L->makeLoopInvariant(Cond, Changed))
 
183
    return Cond;
 
184
 
 
185
  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond))
 
186
    if (BO->getOpcode() == Instruction::And ||
 
187
        BO->getOpcode() == Instruction::Or) {
 
188
      // If either the left or right side is invariant, we can unswitch on this,
 
189
      // which will cause the branch to go away in one loop and the condition to
 
190
      // simplify in the other one.
 
191
      if (Value *LHS = FindLIVLoopCondition(BO->getOperand(0), L, Changed))
 
192
        return LHS;
 
193
      if (Value *RHS = FindLIVLoopCondition(BO->getOperand(1), L, Changed))
 
194
        return RHS;
 
195
    }
 
196
  
 
197
  return 0;
 
198
}
 
199
 
 
200
bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPM_Ref) {
 
201
  LI = &getAnalysis<LoopInfo>();
 
202
  LPM = &LPM_Ref;
 
203
  DF = getAnalysisIfAvailable<DominanceFrontier>();
 
204
  DT = getAnalysisIfAvailable<DominatorTree>();
 
205
  currentLoop = L;
 
206
  Function *F = currentLoop->getHeader()->getParent();
 
207
  bool Changed = false;
 
208
  do {
 
209
    assert(currentLoop->isLCSSAForm());
 
210
    redoLoop = false;
 
211
    Changed |= processCurrentLoop();
 
212
  } while(redoLoop);
 
213
 
 
214
  if (Changed) {
 
215
    // FIXME: Reconstruct dom info, because it is not preserved properly.
 
216
    if (DT)
 
217
      DT->runOnFunction(*F);
 
218
    if (DF)
 
219
      DF->runOnFunction(*F);
 
220
  }
 
221
  return Changed;
 
222
}
 
223
 
 
224
/// processCurrentLoop - Do actual work and unswitch loop if possible 
 
225
/// and profitable.
 
226
bool LoopUnswitch::processCurrentLoop() {
 
227
  bool Changed = false;
 
228
  LLVMContext &Context = currentLoop->getHeader()->getContext();
 
229
 
 
230
  // Loop over all of the basic blocks in the loop.  If we find an interior
 
231
  // block that is branching on a loop-invariant condition, we can unswitch this
 
232
  // loop.
 
233
  for (Loop::block_iterator I = currentLoop->block_begin(), 
 
234
         E = currentLoop->block_end();
 
235
       I != E; ++I) {
 
236
    TerminatorInst *TI = (*I)->getTerminator();
 
237
    if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
 
238
      // If this isn't branching on an invariant condition, we can't unswitch
 
239
      // it.
 
240
      if (BI->isConditional()) {
 
241
        // See if this, or some part of it, is loop invariant.  If so, we can
 
242
        // unswitch on it if we desire.
 
243
        Value *LoopCond = FindLIVLoopCondition(BI->getCondition(), 
 
244
                                               currentLoop, Changed);
 
245
        if (LoopCond && UnswitchIfProfitable(LoopCond, 
 
246
                                             ConstantInt::getTrue(Context))) {
 
247
          ++NumBranches;
 
248
          return true;
 
249
        }
 
250
      }      
 
251
    } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
 
252
      Value *LoopCond = FindLIVLoopCondition(SI->getCondition(), 
 
253
                                             currentLoop, Changed);
 
254
      if (LoopCond && SI->getNumCases() > 1) {
 
255
        // Find a value to unswitch on:
 
256
        // FIXME: this should chose the most expensive case!
 
257
        Constant *UnswitchVal = SI->getCaseValue(1);
 
258
        // Do not process same value again and again.
 
259
        if (!UnswitchedVals.insert(UnswitchVal))
 
260
          continue;
 
261
 
 
262
        if (UnswitchIfProfitable(LoopCond, UnswitchVal)) {
 
263
          ++NumSwitches;
 
264
          return true;
 
265
        }
 
266
      }
 
267
    }
 
268
    
 
269
    // Scan the instructions to check for unswitchable values.
 
270
    for (BasicBlock::iterator BBI = (*I)->begin(), E = (*I)->end(); 
 
271
         BBI != E; ++BBI)
 
272
      if (SelectInst *SI = dyn_cast<SelectInst>(BBI)) {
 
273
        Value *LoopCond = FindLIVLoopCondition(SI->getCondition(), 
 
274
                                               currentLoop, Changed);
 
275
        if (LoopCond && UnswitchIfProfitable(LoopCond, 
 
276
                                             ConstantInt::getTrue(Context))) {
 
277
          ++NumSelects;
 
278
          return true;
 
279
        }
 
280
      }
 
281
  }
 
282
  return Changed;
 
283
}
 
284
 
 
285
/// isTrivialLoopExitBlock - Check to see if all paths from BB either:
 
286
///   1. Exit the loop with no side effects.
 
287
///   2. Branch to the latch block with no side-effects.
 
288
///
 
289
/// If these conditions are true, we return true and set ExitBB to the block we
 
290
/// exit through.
 
291
///
 
292
static bool isTrivialLoopExitBlockHelper(Loop *L, BasicBlock *BB,
 
293
                                         BasicBlock *&ExitBB,
 
294
                                         std::set<BasicBlock*> &Visited) {
 
295
  if (!Visited.insert(BB).second) {
 
296
    // Already visited and Ok, end of recursion.
 
297
    return true;
 
298
  } else if (!L->contains(BB)) {
 
299
    // Otherwise, this is a loop exit, this is fine so long as this is the
 
300
    // first exit.
 
301
    if (ExitBB != 0) return false;
 
302
    ExitBB = BB;
 
303
    return true;
 
304
  }
 
305
  
 
306
  // Otherwise, this is an unvisited intra-loop node.  Check all successors.
 
307
  for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) {
 
308
    // Check to see if the successor is a trivial loop exit.
 
309
    if (!isTrivialLoopExitBlockHelper(L, *SI, ExitBB, Visited))
 
310
      return false;
 
311
  }
 
312
 
 
313
  // Okay, everything after this looks good, check to make sure that this block
 
314
  // doesn't include any side effects.
 
315
  for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
 
316
    if (I->mayHaveSideEffects())
 
317
      return false;
 
318
  
 
319
  return true;
 
320
}
 
321
 
 
322
/// isTrivialLoopExitBlock - Return true if the specified block unconditionally
 
323
/// leads to an exit from the specified loop, and has no side-effects in the 
 
324
/// process.  If so, return the block that is exited to, otherwise return null.
 
325
static BasicBlock *isTrivialLoopExitBlock(Loop *L, BasicBlock *BB) {
 
326
  std::set<BasicBlock*> Visited;
 
327
  Visited.insert(L->getHeader());  // Branches to header are ok.
 
328
  BasicBlock *ExitBB = 0;
 
329
  if (isTrivialLoopExitBlockHelper(L, BB, ExitBB, Visited))
 
330
    return ExitBB;
 
331
  return 0;
 
332
}
 
333
 
 
334
/// IsTrivialUnswitchCondition - Check to see if this unswitch condition is
 
335
/// trivial: that is, that the condition controls whether or not the loop does
 
336
/// anything at all.  If this is a trivial condition, unswitching produces no
 
337
/// code duplications (equivalently, it produces a simpler loop and a new empty
 
338
/// loop, which gets deleted).
 
339
///
 
340
/// If this is a trivial condition, return true, otherwise return false.  When
 
341
/// returning true, this sets Cond and Val to the condition that controls the
 
342
/// trivial condition: when Cond dynamically equals Val, the loop is known to
 
343
/// exit.  Finally, this sets LoopExit to the BB that the loop exits to when
 
344
/// Cond == Val.
 
345
///
 
346
bool LoopUnswitch::IsTrivialUnswitchCondition(Value *Cond, Constant **Val,
 
347
                                       BasicBlock **LoopExit) {
 
348
  BasicBlock *Header = currentLoop->getHeader();
 
349
  TerminatorInst *HeaderTerm = Header->getTerminator();
 
350
  LLVMContext &Context = Header->getContext();
 
351
  
 
352
  BasicBlock *LoopExitBB = 0;
 
353
  if (BranchInst *BI = dyn_cast<BranchInst>(HeaderTerm)) {
 
354
    // If the header block doesn't end with a conditional branch on Cond, we
 
355
    // can't handle it.
 
356
    if (!BI->isConditional() || BI->getCondition() != Cond)
 
357
      return false;
 
358
  
 
359
    // Check to see if a successor of the branch is guaranteed to go to the
 
360
    // latch block or exit through a one exit block without having any 
 
361
    // side-effects.  If so, determine the value of Cond that causes it to do
 
362
    // this.
 
363
    if ((LoopExitBB = isTrivialLoopExitBlock(currentLoop, 
 
364
                                             BI->getSuccessor(0)))) {
 
365
      if (Val) *Val = ConstantInt::getTrue(Context);
 
366
    } else if ((LoopExitBB = isTrivialLoopExitBlock(currentLoop, 
 
367
                                                    BI->getSuccessor(1)))) {
 
368
      if (Val) *Val = ConstantInt::getFalse(Context);
 
369
    }
 
370
  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(HeaderTerm)) {
 
371
    // If this isn't a switch on Cond, we can't handle it.
 
372
    if (SI->getCondition() != Cond) return false;
 
373
    
 
374
    // Check to see if a successor of the switch is guaranteed to go to the
 
375
    // latch block or exit through a one exit block without having any 
 
376
    // side-effects.  If so, determine the value of Cond that causes it to do
 
377
    // this.  Note that we can't trivially unswitch on the default case.
 
378
    for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i)
 
379
      if ((LoopExitBB = isTrivialLoopExitBlock(currentLoop, 
 
380
                                               SI->getSuccessor(i)))) {
 
381
        // Okay, we found a trivial case, remember the value that is trivial.
 
382
        if (Val) *Val = SI->getCaseValue(i);
 
383
        break;
 
384
      }
 
385
  }
 
386
 
 
387
  // If we didn't find a single unique LoopExit block, or if the loop exit block
 
388
  // contains phi nodes, this isn't trivial.
 
389
  if (!LoopExitBB || isa<PHINode>(LoopExitBB->begin()))
 
390
    return false;   // Can't handle this.
 
391
  
 
392
  if (LoopExit) *LoopExit = LoopExitBB;
 
393
  
 
394
  // We already know that nothing uses any scalar values defined inside of this
 
395
  // loop.  As such, we just have to check to see if this loop will execute any
 
396
  // side-effecting instructions (e.g. stores, calls, volatile loads) in the
 
397
  // part of the loop that the code *would* execute.  We already checked the
 
398
  // tail, check the header now.
 
399
  for (BasicBlock::iterator I = Header->begin(), E = Header->end(); I != E; ++I)
 
400
    if (I->mayHaveSideEffects())
 
401
      return false;
 
402
  return true;
 
403
}
 
404
 
 
405
/// UnswitchIfProfitable - We have found that we can unswitch currentLoop when
 
406
/// LoopCond == Val to simplify the loop.  If we decide that this is profitable,
 
407
/// unswitch the loop, reprocess the pieces, then return true.
 
408
bool LoopUnswitch::UnswitchIfProfitable(Value *LoopCond, Constant *Val) {
 
409
 
 
410
  initLoopData();
 
411
 
 
412
  // If LoopSimplify was unable to form a preheader, don't do any unswitching.
 
413
  if (!loopPreheader)
 
414
    return false;
 
415
 
 
416
  Function *F = loopHeader->getParent();
 
417
 
 
418
  // If the condition is trivial, always unswitch.  There is no code growth for
 
419
  // this case.
 
420
  if (!IsTrivialUnswitchCondition(LoopCond)) {
 
421
    // Check to see if it would be profitable to unswitch current loop.
 
422
 
 
423
    // Do not do non-trivial unswitch while optimizing for size.
 
424
    if (OptimizeForSize || F->hasFnAttr(Attribute::OptimizeForSize))
 
425
      return false;
 
426
 
 
427
    // FIXME: This is overly conservative because it does not take into
 
428
    // consideration code simplification opportunities and code that can
 
429
    // be shared by the resultant unswitched loops.
 
430
    CodeMetrics Metrics;
 
431
    for (Loop::block_iterator I = currentLoop->block_begin(), 
 
432
           E = currentLoop->block_end();
 
433
         I != E; ++I)
 
434
      Metrics.analyzeBasicBlock(*I);
 
435
 
 
436
    // Limit the number of instructions to avoid causing significant code
 
437
    // expansion, and the number of basic blocks, to avoid loops with
 
438
    // large numbers of branches which cause loop unswitching to go crazy.
 
439
    // This is a very ad-hoc heuristic.
 
440
    if (Metrics.NumInsts > Threshold ||
 
441
        Metrics.NumBlocks * 5 > Threshold ||
 
442
        Metrics.NeverInline) {
 
443
      DEBUG(dbgs() << "NOT unswitching loop %"
 
444
            << currentLoop->getHeader()->getName() << ", cost too high: "
 
445
            << currentLoop->getBlocks().size() << "\n");
 
446
      return false;
 
447
    }
 
448
  }
 
449
 
 
450
  Constant *CondVal;
 
451
  BasicBlock *ExitBlock;
 
452
  if (IsTrivialUnswitchCondition(LoopCond, &CondVal, &ExitBlock)) {
 
453
    UnswitchTrivialCondition(currentLoop, LoopCond, CondVal, ExitBlock);
 
454
  } else {
 
455
    UnswitchNontrivialCondition(LoopCond, Val, currentLoop);
 
456
  }
 
457
 
 
458
  return true;
 
459
}
 
460
 
 
461
// RemapInstruction - Convert the instruction operands from referencing the
 
462
// current values into those specified by ValueMap.
 
463
//
 
464
static inline void RemapInstruction(Instruction *I,
 
465
                                    DenseMap<const Value *, Value*> &ValueMap) {
 
466
  for (unsigned op = 0, E = I->getNumOperands(); op != E; ++op) {
 
467
    Value *Op = I->getOperand(op);
 
468
    DenseMap<const Value *, Value*>::iterator It = ValueMap.find(Op);
 
469
    if (It != ValueMap.end()) Op = It->second;
 
470
    I->setOperand(op, Op);
 
471
  }
 
472
}
 
473
 
 
474
/// CloneLoop - Recursively clone the specified loop and all of its children,
 
475
/// mapping the blocks with the specified map.
 
476
static Loop *CloneLoop(Loop *L, Loop *PL, DenseMap<const Value*, Value*> &VM,
 
477
                       LoopInfo *LI, LPPassManager *LPM) {
 
478
  Loop *New = new Loop();
 
479
 
 
480
  LPM->insertLoop(New, PL);
 
481
 
 
482
  // Add all of the blocks in L to the new loop.
 
483
  for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
 
484
       I != E; ++I)
 
485
    if (LI->getLoopFor(*I) == L)
 
486
      New->addBasicBlockToLoop(cast<BasicBlock>(VM[*I]), LI->getBase());
 
487
 
 
488
  // Add all of the subloops to the new loop.
 
489
  for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
 
490
    CloneLoop(*I, New, VM, LI, LPM);
 
491
 
 
492
  return New;
 
493
}
 
494
 
 
495
/// EmitPreheaderBranchOnCondition - Emit a conditional branch on two values
 
496
/// if LIC == Val, branch to TrueDst, otherwise branch to FalseDest.  Insert the
 
497
/// code immediately before InsertPt.
 
498
void LoopUnswitch::EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val,
 
499
                                                  BasicBlock *TrueDest,
 
500
                                                  BasicBlock *FalseDest,
 
501
                                                  Instruction *InsertPt) {
 
502
  // Insert a conditional branch on LIC to the two preheaders.  The original
 
503
  // code is the true version and the new code is the false version.
 
504
  Value *BranchVal = LIC;
 
505
  if (!isa<ConstantInt>(Val) ||
 
506
      Val->getType() != Type::getInt1Ty(LIC->getContext()))
 
507
    BranchVal = new ICmpInst(InsertPt, ICmpInst::ICMP_EQ, LIC, Val, "tmp");
 
508
  else if (Val != ConstantInt::getTrue(Val->getContext()))
 
509
    // We want to enter the new loop when the condition is true.
 
510
    std::swap(TrueDest, FalseDest);
 
511
 
 
512
  // Insert the new branch.
 
513
  BranchInst *BI = BranchInst::Create(TrueDest, FalseDest, BranchVal, InsertPt);
 
514
 
 
515
  // If either edge is critical, split it. This helps preserve LoopSimplify
 
516
  // form for enclosing loops.
 
517
  SplitCriticalEdge(BI, 0, this);
 
518
  SplitCriticalEdge(BI, 1, this);
 
519
}
 
520
 
 
521
/// UnswitchTrivialCondition - Given a loop that has a trivial unswitchable
 
522
/// condition in it (a cond branch from its header block to its latch block,
 
523
/// where the path through the loop that doesn't execute its body has no 
 
524
/// side-effects), unswitch it.  This doesn't involve any code duplication, just
 
525
/// moving the conditional branch outside of the loop and updating loop info.
 
526
void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond, 
 
527
                                            Constant *Val, 
 
528
                                            BasicBlock *ExitBlock) {
 
529
  DEBUG(dbgs() << "loop-unswitch: Trivial-Unswitch loop %"
 
530
        << loopHeader->getName() << " [" << L->getBlocks().size()
 
531
        << " blocks] in Function " << L->getHeader()->getParent()->getName()
 
532
        << " on cond: " << *Val << " == " << *Cond << "\n");
 
533
  
 
534
  // First step, split the preheader, so that we know that there is a safe place
 
535
  // to insert the conditional branch.  We will change loopPreheader to have a
 
536
  // conditional branch on Cond.
 
537
  BasicBlock *NewPH = SplitEdge(loopPreheader, loopHeader, this);
 
538
 
 
539
  // Now that we have a place to insert the conditional branch, create a place
 
540
  // to branch to: this is the exit block out of the loop that we should
 
541
  // short-circuit to.
 
542
  
 
543
  // Split this block now, so that the loop maintains its exit block, and so
 
544
  // that the jump from the preheader can execute the contents of the exit block
 
545
  // without actually branching to it (the exit block should be dominated by the
 
546
  // loop header, not the preheader).
 
547
  assert(!L->contains(ExitBlock) && "Exit block is in the loop?");
 
548
  BasicBlock *NewExit = SplitBlock(ExitBlock, ExitBlock->begin(), this);
 
549
    
 
550
  // Okay, now we have a position to branch from and a position to branch to, 
 
551
  // insert the new conditional branch.
 
552
  EmitPreheaderBranchOnCondition(Cond, Val, NewExit, NewPH, 
 
553
                                 loopPreheader->getTerminator());
 
554
  LPM->deleteSimpleAnalysisValue(loopPreheader->getTerminator(), L);
 
555
  loopPreheader->getTerminator()->eraseFromParent();
 
556
 
 
557
  // We need to reprocess this loop, it could be unswitched again.
 
558
  redoLoop = true;
 
559
  
 
560
  // Now that we know that the loop is never entered when this condition is a
 
561
  // particular value, rewrite the loop with this info.  We know that this will
 
562
  // at least eliminate the old branch.
 
563
  RewriteLoopBodyWithConditionConstant(L, Cond, Val, false);
 
564
  ++NumTrivial;
 
565
}
 
566
 
 
567
/// SplitExitEdges - Split all of the edges from inside the loop to their exit
 
568
/// blocks.  Update the appropriate Phi nodes as we do so.
 
569
void LoopUnswitch::SplitExitEdges(Loop *L, 
 
570
                                const SmallVector<BasicBlock *, 8> &ExitBlocks) 
 
571
{
 
572
 
 
573
  for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
 
574
    BasicBlock *ExitBlock = ExitBlocks[i];
 
575
    SmallVector<BasicBlock *, 4> Preds(pred_begin(ExitBlock),
 
576
                                       pred_end(ExitBlock));
 
577
    SplitBlockPredecessors(ExitBlock, Preds.data(), Preds.size(),
 
578
                           ".us-lcssa", this);
 
579
  }
 
580
}
 
581
 
 
582
/// UnswitchNontrivialCondition - We determined that the loop is profitable 
 
583
/// to unswitch when LIC equal Val.  Split it into loop versions and test the 
 
584
/// condition outside of either loop.  Return the loops created as Out1/Out2.
 
585
void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, 
 
586
                                               Loop *L) {
 
587
  Function *F = loopHeader->getParent();
 
588
  DEBUG(dbgs() << "loop-unswitch: Unswitching loop %"
 
589
        << loopHeader->getName() << " [" << L->getBlocks().size()
 
590
        << " blocks] in Function " << F->getName()
 
591
        << " when '" << *Val << "' == " << *LIC << "\n");
 
592
 
 
593
  LoopBlocks.clear();
 
594
  NewBlocks.clear();
 
595
 
 
596
  // First step, split the preheader and exit blocks, and add these blocks to
 
597
  // the LoopBlocks list.
 
598
  BasicBlock *NewPreheader = SplitEdge(loopPreheader, loopHeader, this);
 
599
  LoopBlocks.push_back(NewPreheader);
 
600
 
 
601
  // We want the loop to come after the preheader, but before the exit blocks.
 
602
  LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end());
 
603
 
 
604
  SmallVector<BasicBlock*, 8> ExitBlocks;
 
605
  L->getUniqueExitBlocks(ExitBlocks);
 
606
 
 
607
  // Split all of the edges from inside the loop to their exit blocks.  Update
 
608
  // the appropriate Phi nodes as we do so.
 
609
  SplitExitEdges(L, ExitBlocks);
 
610
 
 
611
  // The exit blocks may have been changed due to edge splitting, recompute.
 
612
  ExitBlocks.clear();
 
613
  L->getUniqueExitBlocks(ExitBlocks);
 
614
 
 
615
  // Add exit blocks to the loop blocks.
 
616
  LoopBlocks.insert(LoopBlocks.end(), ExitBlocks.begin(), ExitBlocks.end());
 
617
 
 
618
  // Next step, clone all of the basic blocks that make up the loop (including
 
619
  // the loop preheader and exit blocks), keeping track of the mapping between
 
620
  // the instructions and blocks.
 
621
  NewBlocks.reserve(LoopBlocks.size());
 
622
  DenseMap<const Value*, Value*> ValueMap;
 
623
  for (unsigned i = 0, e = LoopBlocks.size(); i != e; ++i) {
 
624
    BasicBlock *New = CloneBasicBlock(LoopBlocks[i], ValueMap, ".us", F);
 
625
    NewBlocks.push_back(New);
 
626
    ValueMap[LoopBlocks[i]] = New;  // Keep the BB mapping.
 
627
    LPM->cloneBasicBlockSimpleAnalysis(LoopBlocks[i], New, L);
 
628
  }
 
629
 
 
630
  // Splice the newly inserted blocks into the function right before the
 
631
  // original preheader.
 
632
  F->getBasicBlockList().splice(LoopBlocks[0], F->getBasicBlockList(),
 
633
                                NewBlocks[0], F->end());
 
634
 
 
635
  // Now we create the new Loop object for the versioned loop.
 
636
  Loop *NewLoop = CloneLoop(L, L->getParentLoop(), ValueMap, LI, LPM);
 
637
  Loop *ParentLoop = L->getParentLoop();
 
638
  if (ParentLoop) {
 
639
    // Make sure to add the cloned preheader and exit blocks to the parent loop
 
640
    // as well.
 
641
    ParentLoop->addBasicBlockToLoop(NewBlocks[0], LI->getBase());
 
642
  }
 
643
  
 
644
  for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
 
645
    BasicBlock *NewExit = cast<BasicBlock>(ValueMap[ExitBlocks[i]]);
 
646
    // The new exit block should be in the same loop as the old one.
 
647
    if (Loop *ExitBBLoop = LI->getLoopFor(ExitBlocks[i]))
 
648
      ExitBBLoop->addBasicBlockToLoop(NewExit, LI->getBase());
 
649
    
 
650
    assert(NewExit->getTerminator()->getNumSuccessors() == 1 &&
 
651
           "Exit block should have been split to have one successor!");
 
652
    BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0);
 
653
 
 
654
    // If the successor of the exit block had PHI nodes, add an entry for
 
655
    // NewExit.
 
656
    PHINode *PN;
 
657
    for (BasicBlock::iterator I = ExitSucc->begin();
 
658
         (PN = dyn_cast<PHINode>(I)); ++I) {
 
659
      Value *V = PN->getIncomingValueForBlock(ExitBlocks[i]);
 
660
      DenseMap<const Value *, Value*>::iterator It = ValueMap.find(V);
 
661
      if (It != ValueMap.end()) V = It->second;
 
662
      PN->addIncoming(V, NewExit);
 
663
    }
 
664
  }
 
665
 
 
666
  // Rewrite the code to refer to itself.
 
667
  for (unsigned i = 0, e = NewBlocks.size(); i != e; ++i)
 
668
    for (BasicBlock::iterator I = NewBlocks[i]->begin(),
 
669
           E = NewBlocks[i]->end(); I != E; ++I)
 
670
      RemapInstruction(I, ValueMap);
 
671
  
 
672
  // Rewrite the original preheader to select between versions of the loop.
 
673
  BranchInst *OldBR = cast<BranchInst>(loopPreheader->getTerminator());
 
674
  assert(OldBR->isUnconditional() && OldBR->getSuccessor(0) == LoopBlocks[0] &&
 
675
         "Preheader splitting did not work correctly!");
 
676
 
 
677
  // Emit the new branch that selects between the two versions of this loop.
 
678
  EmitPreheaderBranchOnCondition(LIC, Val, NewBlocks[0], LoopBlocks[0], OldBR);
 
679
  LPM->deleteSimpleAnalysisValue(OldBR, L);
 
680
  OldBR->eraseFromParent();
 
681
 
 
682
  LoopProcessWorklist.push_back(NewLoop);
 
683
  redoLoop = true;
 
684
 
 
685
  // Now we rewrite the original code to know that the condition is true and the
 
686
  // new code to know that the condition is false.
 
687
  RewriteLoopBodyWithConditionConstant(L      , LIC, Val, false);
 
688
  
 
689
  // It's possible that simplifying one loop could cause the other to be
 
690
  // deleted.  If so, don't simplify it.
 
691
  if (!LoopProcessWorklist.empty() && LoopProcessWorklist.back() == NewLoop)
 
692
    RewriteLoopBodyWithConditionConstant(NewLoop, LIC, Val, true);
 
693
 
 
694
}
 
695
 
 
696
/// RemoveFromWorklist - Remove all instances of I from the worklist vector
 
697
/// specified.
 
698
static void RemoveFromWorklist(Instruction *I, 
 
699
                               std::vector<Instruction*> &Worklist) {
 
700
  std::vector<Instruction*>::iterator WI = std::find(Worklist.begin(),
 
701
                                                     Worklist.end(), I);
 
702
  while (WI != Worklist.end()) {
 
703
    unsigned Offset = WI-Worklist.begin();
 
704
    Worklist.erase(WI);
 
705
    WI = std::find(Worklist.begin()+Offset, Worklist.end(), I);
 
706
  }
 
707
}
 
708
 
 
709
/// ReplaceUsesOfWith - When we find that I really equals V, remove I from the
 
710
/// program, replacing all uses with V and update the worklist.
 
711
static void ReplaceUsesOfWith(Instruction *I, Value *V, 
 
712
                              std::vector<Instruction*> &Worklist,
 
713
                              Loop *L, LPPassManager *LPM) {
 
714
  DEBUG(dbgs() << "Replace with '" << *V << "': " << *I);
 
715
 
 
716
  // Add uses to the worklist, which may be dead now.
 
717
  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
 
718
    if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i)))
 
719
      Worklist.push_back(Use);
 
720
 
 
721
  // Add users to the worklist which may be simplified now.
 
722
  for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
 
723
       UI != E; ++UI)
 
724
    Worklist.push_back(cast<Instruction>(*UI));
 
725
  LPM->deleteSimpleAnalysisValue(I, L);
 
726
  RemoveFromWorklist(I, Worklist);
 
727
  I->replaceAllUsesWith(V);
 
728
  I->eraseFromParent();
 
729
  ++NumSimplify;
 
730
}
 
731
 
 
732
/// RemoveBlockIfDead - If the specified block is dead, remove it, update loop
 
733
/// information, and remove any dead successors it has.
 
734
///
 
735
void LoopUnswitch::RemoveBlockIfDead(BasicBlock *BB,
 
736
                                     std::vector<Instruction*> &Worklist,
 
737
                                     Loop *L) {
 
738
  if (pred_begin(BB) != pred_end(BB)) {
 
739
    // This block isn't dead, since an edge to BB was just removed, see if there
 
740
    // are any easy simplifications we can do now.
 
741
    if (BasicBlock *Pred = BB->getSinglePredecessor()) {
 
742
      // If it has one pred, fold phi nodes in BB.
 
743
      while (isa<PHINode>(BB->begin()))
 
744
        ReplaceUsesOfWith(BB->begin(), 
 
745
                          cast<PHINode>(BB->begin())->getIncomingValue(0), 
 
746
                          Worklist, L, LPM);
 
747
      
 
748
      // If this is the header of a loop and the only pred is the latch, we now
 
749
      // have an unreachable loop.
 
750
      if (Loop *L = LI->getLoopFor(BB))
 
751
        if (loopHeader == BB && L->contains(Pred)) {
 
752
          // Remove the branch from the latch to the header block, this makes
 
753
          // the header dead, which will make the latch dead (because the header
 
754
          // dominates the latch).
 
755
          LPM->deleteSimpleAnalysisValue(Pred->getTerminator(), L);
 
756
          Pred->getTerminator()->eraseFromParent();
 
757
          new UnreachableInst(BB->getContext(), Pred);
 
758
          
 
759
          // The loop is now broken, remove it from LI.
 
760
          RemoveLoopFromHierarchy(L);
 
761
          
 
762
          // Reprocess the header, which now IS dead.
 
763
          RemoveBlockIfDead(BB, Worklist, L);
 
764
          return;
 
765
        }
 
766
      
 
767
      // If pred ends in a uncond branch, add uncond branch to worklist so that
 
768
      // the two blocks will get merged.
 
769
      if (BranchInst *BI = dyn_cast<BranchInst>(Pred->getTerminator()))
 
770
        if (BI->isUnconditional())
 
771
          Worklist.push_back(BI);
 
772
    }
 
773
    return;
 
774
  }
 
775
 
 
776
  DEBUG(dbgs() << "Nuking dead block: " << *BB);
 
777
  
 
778
  // Remove the instructions in the basic block from the worklist.
 
779
  for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
 
780
    RemoveFromWorklist(I, Worklist);
 
781
    
 
782
    // Anything that uses the instructions in this basic block should have their
 
783
    // uses replaced with undefs.
 
784
    // If I is not void type then replaceAllUsesWith undef.
 
785
    // This allows ValueHandlers and custom metadata to adjust itself.
 
786
    if (!I->getType()->isVoidTy())
 
787
      I->replaceAllUsesWith(UndefValue::get(I->getType()));
 
788
  }
 
789
  
 
790
  // If this is the edge to the header block for a loop, remove the loop and
 
791
  // promote all subloops.
 
792
  if (Loop *BBLoop = LI->getLoopFor(BB)) {
 
793
    if (BBLoop->getLoopLatch() == BB)
 
794
      RemoveLoopFromHierarchy(BBLoop);
 
795
  }
 
796
 
 
797
  // Remove the block from the loop info, which removes it from any loops it
 
798
  // was in.
 
799
  LI->removeBlock(BB);
 
800
  
 
801
  
 
802
  // Remove phi node entries in successors for this block.
 
803
  TerminatorInst *TI = BB->getTerminator();
 
804
  SmallVector<BasicBlock*, 4> Succs;
 
805
  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
 
806
    Succs.push_back(TI->getSuccessor(i));
 
807
    TI->getSuccessor(i)->removePredecessor(BB);
 
808
  }
 
809
  
 
810
  // Unique the successors, remove anything with multiple uses.
 
811
  array_pod_sort(Succs.begin(), Succs.end());
 
812
  Succs.erase(std::unique(Succs.begin(), Succs.end()), Succs.end());
 
813
  
 
814
  // Remove the basic block, including all of the instructions contained in it.
 
815
  LPM->deleteSimpleAnalysisValue(BB, L);  
 
816
  BB->eraseFromParent();
 
817
  // Remove successor blocks here that are not dead, so that we know we only
 
818
  // have dead blocks in this list.  Nondead blocks have a way of becoming dead,
 
819
  // then getting removed before we revisit them, which is badness.
 
820
  //
 
821
  for (unsigned i = 0; i != Succs.size(); ++i)
 
822
    if (pred_begin(Succs[i]) != pred_end(Succs[i])) {
 
823
      // One exception is loop headers.  If this block was the preheader for a
 
824
      // loop, then we DO want to visit the loop so the loop gets deleted.
 
825
      // We know that if the successor is a loop header, that this loop had to
 
826
      // be the preheader: the case where this was the latch block was handled
 
827
      // above and headers can only have two predecessors.
 
828
      if (!LI->isLoopHeader(Succs[i])) {
 
829
        Succs.erase(Succs.begin()+i);
 
830
        --i;
 
831
      }
 
832
    }
 
833
  
 
834
  for (unsigned i = 0, e = Succs.size(); i != e; ++i)
 
835
    RemoveBlockIfDead(Succs[i], Worklist, L);
 
836
}
 
837
 
 
838
/// RemoveLoopFromHierarchy - We have discovered that the specified loop has
 
839
/// become unwrapped, either because the backedge was deleted, or because the
 
840
/// edge into the header was removed.  If the edge into the header from the
 
841
/// latch block was removed, the loop is unwrapped but subloops are still alive,
 
842
/// so they just reparent loops.  If the loops are actually dead, they will be
 
843
/// removed later.
 
844
void LoopUnswitch::RemoveLoopFromHierarchy(Loop *L) {
 
845
  LPM->deleteLoopFromQueue(L);
 
846
  RemoveLoopFromWorklist(L);
 
847
}
 
848
 
 
849
// RewriteLoopBodyWithConditionConstant - We know either that the value LIC has
 
850
// the value specified by Val in the specified loop, or we know it does NOT have
 
851
// that value.  Rewrite any uses of LIC or of properties correlated to it.
 
852
void LoopUnswitch::RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC,
 
853
                                                        Constant *Val,
 
854
                                                        bool IsEqual) {
 
855
  assert(!isa<Constant>(LIC) && "Why are we unswitching on a constant?");
 
856
  
 
857
  // FIXME: Support correlated properties, like:
 
858
  //  for (...)
 
859
  //    if (li1 < li2)
 
860
  //      ...
 
861
  //    if (li1 > li2)
 
862
  //      ...
 
863
  
 
864
  // FOLD boolean conditions (X|LIC), (X&LIC).  Fold conditional branches,
 
865
  // selects, switches.
 
866
  std::vector<User*> Users(LIC->use_begin(), LIC->use_end());
 
867
  std::vector<Instruction*> Worklist;
 
868
  LLVMContext &Context = Val->getContext();
 
869
 
 
870
 
 
871
  // If we know that LIC == Val, or that LIC == NotVal, just replace uses of LIC
 
872
  // in the loop with the appropriate one directly.
 
873
  if (IsEqual || (isa<ConstantInt>(Val) &&
 
874
      Val->getType()->isIntegerTy(1))) {
 
875
    Value *Replacement;
 
876
    if (IsEqual)
 
877
      Replacement = Val;
 
878
    else
 
879
      Replacement = ConstantInt::get(Type::getInt1Ty(Val->getContext()), 
 
880
                                     !cast<ConstantInt>(Val)->getZExtValue());
 
881
    
 
882
    for (unsigned i = 0, e = Users.size(); i != e; ++i)
 
883
      if (Instruction *U = cast<Instruction>(Users[i])) {
 
884
        if (!L->contains(U))
 
885
          continue;
 
886
        U->replaceUsesOfWith(LIC, Replacement);
 
887
        Worklist.push_back(U);
 
888
      }
 
889
  } else {
 
890
    // Otherwise, we don't know the precise value of LIC, but we do know that it
 
891
    // is certainly NOT "Val".  As such, simplify any uses in the loop that we
 
892
    // can.  This case occurs when we unswitch switch statements.
 
893
    for (unsigned i = 0, e = Users.size(); i != e; ++i)
 
894
      if (Instruction *U = cast<Instruction>(Users[i])) {
 
895
        if (!L->contains(U))
 
896
          continue;
 
897
 
 
898
        Worklist.push_back(U);
 
899
 
 
900
        // If we know that LIC is not Val, use this info to simplify code.
 
901
        if (SwitchInst *SI = dyn_cast<SwitchInst>(U)) {
 
902
          for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) {
 
903
            if (SI->getCaseValue(i) == Val) {
 
904
              // Found a dead case value.  Don't remove PHI nodes in the 
 
905
              // successor if they become single-entry, those PHI nodes may
 
906
              // be in the Users list.
 
907
              
 
908
              // FIXME: This is a hack.  We need to keep the successor around
 
909
              // and hooked up so as to preserve the loop structure, because
 
910
              // trying to update it is complicated.  So instead we preserve the
 
911
              // loop structure and put the block on a dead code path.
 
912
              BasicBlock *Switch = SI->getParent();
 
913
              SplitEdge(Switch, SI->getSuccessor(i), this);
 
914
              // Compute the successors instead of relying on the return value
 
915
              // of SplitEdge, since it may have split the switch successor
 
916
              // after PHI nodes.
 
917
              BasicBlock *NewSISucc = SI->getSuccessor(i);
 
918
              BasicBlock *OldSISucc = *succ_begin(NewSISucc);
 
919
              // Create an "unreachable" destination.
 
920
              BasicBlock *Abort = BasicBlock::Create(Context, "us-unreachable",
 
921
                                                     Switch->getParent(),
 
922
                                                     OldSISucc);
 
923
              new UnreachableInst(Context, Abort);
 
924
              // Force the new case destination to branch to the "unreachable"
 
925
              // block while maintaining a (dead) CFG edge to the old block.
 
926
              NewSISucc->getTerminator()->eraseFromParent();
 
927
              BranchInst::Create(Abort, OldSISucc,
 
928
                                 ConstantInt::getTrue(Context), NewSISucc);
 
929
              // Release the PHI operands for this edge.
 
930
              for (BasicBlock::iterator II = NewSISucc->begin();
 
931
                   PHINode *PN = dyn_cast<PHINode>(II); ++II)
 
932
                PN->setIncomingValue(PN->getBasicBlockIndex(Switch),
 
933
                                     UndefValue::get(PN->getType()));
 
934
              // Tell the domtree about the new block. We don't fully update the
 
935
              // domtree here -- instead we force it to do a full recomputation
 
936
              // after the pass is complete -- but we do need to inform it of
 
937
              // new blocks.
 
938
              if (DT)
 
939
                DT->addNewBlock(Abort, NewSISucc);
 
940
              break;
 
941
            }
 
942
          }
 
943
        }
 
944
        
 
945
        // TODO: We could do other simplifications, for example, turning 
 
946
        // LIC == Val -> false.
 
947
      }
 
948
  }
 
949
  
 
950
  SimplifyCode(Worklist, L);
 
951
}
 
952
 
 
953
/// SimplifyCode - Okay, now that we have simplified some instructions in the
 
954
/// loop, walk over it and constant prop, dce, and fold control flow where
 
955
/// possible.  Note that this is effectively a very simple loop-structure-aware
 
956
/// optimizer.  During processing of this loop, L could very well be deleted, so
 
957
/// it must not be used.
 
958
///
 
959
/// FIXME: When the loop optimizer is more mature, separate this out to a new
 
960
/// pass.
 
961
///
 
962
void LoopUnswitch::SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L) {
 
963
  while (!Worklist.empty()) {
 
964
    Instruction *I = Worklist.back();
 
965
    Worklist.pop_back();
 
966
    
 
967
    // Simple constant folding.
 
968
    if (Constant *C = ConstantFoldInstruction(I)) {
 
969
      ReplaceUsesOfWith(I, C, Worklist, L, LPM);
 
970
      continue;
 
971
    }
 
972
    
 
973
    // Simple DCE.
 
974
    if (isInstructionTriviallyDead(I)) {
 
975
      DEBUG(dbgs() << "Remove dead instruction '" << *I);
 
976
      
 
977
      // Add uses to the worklist, which may be dead now.
 
978
      for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
 
979
        if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i)))
 
980
          Worklist.push_back(Use);
 
981
      LPM->deleteSimpleAnalysisValue(I, L);
 
982
      RemoveFromWorklist(I, Worklist);
 
983
      I->eraseFromParent();
 
984
      ++NumSimplify;
 
985
      continue;
 
986
    }
 
987
    
 
988
    // Special case hacks that appear commonly in unswitched code.
 
989
    switch (I->getOpcode()) {
 
990
    case Instruction::Select:
 
991
      if (ConstantInt *CB = dyn_cast<ConstantInt>(I->getOperand(0))) {
 
992
        ReplaceUsesOfWith(I, I->getOperand(!CB->getZExtValue()+1), Worklist, L,
 
993
                          LPM);
 
994
        continue;
 
995
      }
 
996
      break;
 
997
    case Instruction::And:
 
998
      if (isa<ConstantInt>(I->getOperand(0)) && 
 
999
          // constant -> RHS
 
1000
          I->getOperand(0)->getType()->isIntegerTy(1))
 
1001
        cast<BinaryOperator>(I)->swapOperands();
 
1002
      if (ConstantInt *CB = dyn_cast<ConstantInt>(I->getOperand(1))) 
 
1003
        if (CB->getType()->isIntegerTy(1)) {
 
1004
          if (CB->isOne())      // X & 1 -> X
 
1005
            ReplaceUsesOfWith(I, I->getOperand(0), Worklist, L, LPM);
 
1006
          else                  // X & 0 -> 0
 
1007
            ReplaceUsesOfWith(I, I->getOperand(1), Worklist, L, LPM);
 
1008
          continue;
 
1009
        }
 
1010
      break;
 
1011
    case Instruction::Or:
 
1012
      if (isa<ConstantInt>(I->getOperand(0)) &&
 
1013
          // constant -> RHS
 
1014
          I->getOperand(0)->getType()->isIntegerTy(1))
 
1015
        cast<BinaryOperator>(I)->swapOperands();
 
1016
      if (ConstantInt *CB = dyn_cast<ConstantInt>(I->getOperand(1)))
 
1017
        if (CB->getType()->isIntegerTy(1)) {
 
1018
          if (CB->isOne())   // X | 1 -> 1
 
1019
            ReplaceUsesOfWith(I, I->getOperand(1), Worklist, L, LPM);
 
1020
          else                  // X | 0 -> X
 
1021
            ReplaceUsesOfWith(I, I->getOperand(0), Worklist, L, LPM);
 
1022
          continue;
 
1023
        }
 
1024
      break;
 
1025
    case Instruction::Br: {
 
1026
      BranchInst *BI = cast<BranchInst>(I);
 
1027
      if (BI->isUnconditional()) {
 
1028
        // If BI's parent is the only pred of the successor, fold the two blocks
 
1029
        // together.
 
1030
        BasicBlock *Pred = BI->getParent();
 
1031
        BasicBlock *Succ = BI->getSuccessor(0);
 
1032
        BasicBlock *SinglePred = Succ->getSinglePredecessor();
 
1033
        if (!SinglePred) continue;  // Nothing to do.
 
1034
        assert(SinglePred == Pred && "CFG broken");
 
1035
 
 
1036
        DEBUG(dbgs() << "Merging blocks: " << Pred->getName() << " <- " 
 
1037
              << Succ->getName() << "\n");
 
1038
        
 
1039
        // Resolve any single entry PHI nodes in Succ.
 
1040
        while (PHINode *PN = dyn_cast<PHINode>(Succ->begin()))
 
1041
          ReplaceUsesOfWith(PN, PN->getIncomingValue(0), Worklist, L, LPM);
 
1042
        
 
1043
        // Move all of the successor contents from Succ to Pred.
 
1044
        Pred->getInstList().splice(BI, Succ->getInstList(), Succ->begin(),
 
1045
                                   Succ->end());
 
1046
        LPM->deleteSimpleAnalysisValue(BI, L);
 
1047
        BI->eraseFromParent();
 
1048
        RemoveFromWorklist(BI, Worklist);
 
1049
        
 
1050
        // If Succ has any successors with PHI nodes, update them to have
 
1051
        // entries coming from Pred instead of Succ.
 
1052
        Succ->replaceAllUsesWith(Pred);
 
1053
        
 
1054
        // Remove Succ from the loop tree.
 
1055
        LI->removeBlock(Succ);
 
1056
        LPM->deleteSimpleAnalysisValue(Succ, L);
 
1057
        Succ->eraseFromParent();
 
1058
        ++NumSimplify;
 
1059
      } else if (ConstantInt *CB = dyn_cast<ConstantInt>(BI->getCondition())){
 
1060
        // Conditional branch.  Turn it into an unconditional branch, then
 
1061
        // remove dead blocks.
 
1062
        break;  // FIXME: Enable.
 
1063
 
 
1064
        DEBUG(dbgs() << "Folded branch: " << *BI);
 
1065
        BasicBlock *DeadSucc = BI->getSuccessor(CB->getZExtValue());
 
1066
        BasicBlock *LiveSucc = BI->getSuccessor(!CB->getZExtValue());
 
1067
        DeadSucc->removePredecessor(BI->getParent(), true);
 
1068
        Worklist.push_back(BranchInst::Create(LiveSucc, BI));
 
1069
        LPM->deleteSimpleAnalysisValue(BI, L);
 
1070
        BI->eraseFromParent();
 
1071
        RemoveFromWorklist(BI, Worklist);
 
1072
        ++NumSimplify;
 
1073
 
 
1074
        RemoveBlockIfDead(DeadSucc, Worklist, L);
 
1075
      }
 
1076
      break;
 
1077
    }
 
1078
    }
 
1079
  }
 
1080
}