Fix PR3353, infinitely jump threading an infinite loop make from switches.
[oota-llvm.git] / lib / Transforms / Scalar / JumpThreading.cpp
1 //===- JumpThreading.cpp - Thread control through conditional blocks ------===//
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 Jump Threading pass.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #define DEBUG_TYPE "jump-threading"
15 #include "llvm/Transforms/Scalar.h"
16 #include "llvm/IntrinsicInst.h"
17 #include "llvm/Pass.h"
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/Statistic.h"
20 #include "llvm/ADT/STLExtras.h"
21 #include "llvm/Analysis/ConstantFolding.h"
22 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
23 #include "llvm/Transforms/Utils/Local.h"
24 #include "llvm/Target/TargetData.h"
25 #include "llvm/Support/CommandLine.h"
26 #include "llvm/Support/Compiler.h"
27 #include "llvm/Support/Debug.h"
28 #include "llvm/ADT/SmallPtrSet.h"
29 using namespace llvm;
30
31 STATISTIC(NumThreads, "Number of jumps threaded");
32 STATISTIC(NumFolds,   "Number of terminators folded");
33
34 static cl::opt<unsigned>
35 Threshold("jump-threading-threshold", 
36           cl::desc("Max block size to duplicate for jump threading"),
37           cl::init(6), cl::Hidden);
38
39 namespace {
40   /// This pass performs 'jump threading', which looks at blocks that have
41   /// multiple predecessors and multiple successors.  If one or more of the
42   /// predecessors of the block can be proven to always jump to one of the
43   /// successors, we forward the edge from the predecessor to the successor by
44   /// duplicating the contents of this block.
45   ///
46   /// An example of when this can occur is code like this:
47   ///
48   ///   if () { ...
49   ///     X = 4;
50   ///   }
51   ///   if (X < 3) {
52   ///
53   /// In this case, the unconditional branch at the end of the first if can be
54   /// revectored to the false side of the second if.
55   ///
56   class VISIBILITY_HIDDEN JumpThreading : public FunctionPass {
57     TargetData *TD;
58   public:
59     static char ID; // Pass identification
60     JumpThreading() : FunctionPass(&ID) {}
61
62     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
63       AU.addRequired<TargetData>();
64     }
65
66     bool runOnFunction(Function &F);
67     bool ProcessBlock(BasicBlock *BB);
68     void ThreadEdge(BasicBlock *BB, BasicBlock *PredBB, BasicBlock *SuccBB);
69     BasicBlock *FactorCommonPHIPreds(PHINode *PN, Constant *CstVal);
70     bool ProcessBranchOnDuplicateCond(BasicBlock *PredBB, BasicBlock *DestBB);
71     bool ProcessSwitchOnDuplicateCond(BasicBlock *PredBB, BasicBlock *DestBB);
72
73     bool ProcessJumpOnPHI(PHINode *PN);
74     bool ProcessBranchOnLogical(Value *V, BasicBlock *BB, bool isAnd);
75     bool ProcessBranchOnCompare(CmpInst *Cmp, BasicBlock *BB);
76     
77     bool SimplifyPartiallyRedundantLoad(LoadInst *LI);
78   };
79 }
80
81 char JumpThreading::ID = 0;
82 static RegisterPass<JumpThreading>
83 X("jump-threading", "Jump Threading");
84
85 // Public interface to the Jump Threading pass
86 FunctionPass *llvm::createJumpThreadingPass() { return new JumpThreading(); }
87
88 /// runOnFunction - Top level algorithm.
89 ///
90 bool JumpThreading::runOnFunction(Function &F) {
91   DOUT << "Jump threading on function '" << F.getNameStart() << "'\n";
92   TD = &getAnalysis<TargetData>();
93   
94   bool AnotherIteration = true, EverChanged = false;
95   while (AnotherIteration) {
96     AnotherIteration = false;
97     bool Changed = false;
98     for (Function::iterator I = F.begin(), E = F.end(); I != E;) {
99       BasicBlock *BB = I;
100       while (ProcessBlock(BB))
101         Changed = true;
102       
103       ++I;
104       
105       // If the block is trivially dead, zap it.  This eliminates the successor
106       // edges which simplifies the CFG.
107       if (pred_begin(BB) == pred_end(BB) &&
108           BB != &BB->getParent()->getEntryBlock()) {
109         DOUT << "  JT: Deleting dead block '" << BB->getNameStart()
110              << "' with terminator: " << *BB->getTerminator();
111         DeleteDeadBlock(BB);
112         Changed = true;
113       }
114     }
115     AnotherIteration = Changed;
116     EverChanged |= Changed;
117   }
118   return EverChanged;
119 }
120
121 /// FactorCommonPHIPreds - If there are multiple preds with the same incoming
122 /// value for the PHI, factor them together so we get one block to thread for
123 /// the whole group.
124 /// This is important for things like "phi i1 [true, true, false, true, x]"
125 /// where we only need to clone the block for the true blocks once.
126 ///
127 BasicBlock *JumpThreading::FactorCommonPHIPreds(PHINode *PN, Constant *CstVal) {
128   SmallVector<BasicBlock*, 16> CommonPreds;
129   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
130     if (PN->getIncomingValue(i) == CstVal)
131       CommonPreds.push_back(PN->getIncomingBlock(i));
132   
133   if (CommonPreds.size() == 1)
134     return CommonPreds[0];
135     
136   DOUT << "  Factoring out " << CommonPreds.size()
137        << " common predecessors.\n";
138   return SplitBlockPredecessors(PN->getParent(),
139                                 &CommonPreds[0], CommonPreds.size(),
140                                 ".thr_comm", this);
141 }
142   
143
144 /// getJumpThreadDuplicationCost - Return the cost of duplicating this block to
145 /// thread across it.
146 static unsigned getJumpThreadDuplicationCost(const BasicBlock *BB) {
147   /// Ignore PHI nodes, these will be flattened when duplication happens.
148   BasicBlock::const_iterator I = BB->getFirstNonPHI();
149
150   // Sum up the cost of each instruction until we get to the terminator.  Don't
151   // include the terminator because the copy won't include it.
152   unsigned Size = 0;
153   for (; !isa<TerminatorInst>(I); ++I) {
154     // Debugger intrinsics don't incur code size.
155     if (isa<DbgInfoIntrinsic>(I)) continue;
156     
157     // If this is a pointer->pointer bitcast, it is free.
158     if (isa<BitCastInst>(I) && isa<PointerType>(I->getType()))
159       continue;
160     
161     // All other instructions count for at least one unit.
162     ++Size;
163     
164     // Calls are more expensive.  If they are non-intrinsic calls, we model them
165     // as having cost of 4.  If they are a non-vector intrinsic, we model them
166     // as having cost of 2 total, and if they are a vector intrinsic, we model
167     // them as having cost 1.
168     if (const CallInst *CI = dyn_cast<CallInst>(I)) {
169       if (!isa<IntrinsicInst>(CI))
170         Size += 3;
171       else if (isa<VectorType>(CI->getType()))
172         Size += 1;
173     }
174   }
175   
176   // Threading through a switch statement is particularly profitable.  If this
177   // block ends in a switch, decrease its cost to make it more likely to happen.
178   if (isa<SwitchInst>(I))
179     Size = Size > 6 ? Size-6 : 0;
180   
181   return Size;
182 }
183
184 /// ProcessBlock - If there are any predecessors whose control can be threaded
185 /// through to a successor, transform them now.
186 bool JumpThreading::ProcessBlock(BasicBlock *BB) {
187   // If this block has a single predecessor, and if that pred has a single
188   // successor, merge the blocks.  This encourages recursive jump threading
189   // because now the condition in this block can be threaded through
190   // predecessors of our predecessor block.
191   if (BasicBlock *SinglePred = BB->getSinglePredecessor())
192     if (SinglePred->getTerminator()->getNumSuccessors() == 1 &&
193         SinglePred != BB) {
194       // Remember if SinglePred was the entry block of the function.  If so, we
195       // will need to move BB back to the entry position.
196       bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock();
197       MergeBasicBlockIntoOnlyPred(BB);
198       
199       if (isEntry && BB != &BB->getParent()->getEntryBlock())
200         BB->moveBefore(&BB->getParent()->getEntryBlock());
201       return true;
202     }
203   
204   // See if this block ends with a branch or switch.  If so, see if the
205   // condition is a phi node.  If so, and if an entry of the phi node is a
206   // constant, we can thread the block.
207   Value *Condition;
208   if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) {
209     // Can't thread an unconditional jump.
210     if (BI->isUnconditional()) return false;
211     Condition = BI->getCondition();
212   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator()))
213     Condition = SI->getCondition();
214   else
215     return false; // Must be an invoke.
216   
217   // If the terminator of this block is branching on a constant, simplify the
218   // terminator to an unconditional branch.  This can occur due to threading in
219   // other blocks.
220   if (isa<ConstantInt>(Condition)) {
221     DOUT << "  In block '" << BB->getNameStart()
222          << "' folding terminator: " << *BB->getTerminator();
223     ++NumFolds;
224     ConstantFoldTerminator(BB);
225     return true;
226   }
227   
228   // If the terminator is branching on an undef, we can pick any of the
229   // successors to branch to.  Since this is arbitrary, we pick the successor
230   // with the fewest predecessors.  This should reduce the in-degree of the
231   // others.
232   if (isa<UndefValue>(Condition)) {
233     TerminatorInst *BBTerm = BB->getTerminator();
234     unsigned MinSucc = 0;
235     BasicBlock *TestBB = BBTerm->getSuccessor(MinSucc);
236     // Compute the successor with the minimum number of predecessors.
237     unsigned MinNumPreds = std::distance(pred_begin(TestBB), pred_end(TestBB));
238     for (unsigned i = 1, e = BBTerm->getNumSuccessors(); i != e; ++i) {
239       TestBB = BBTerm->getSuccessor(i);
240       unsigned NumPreds = std::distance(pred_begin(TestBB), pred_end(TestBB));
241       if (NumPreds < MinNumPreds)
242         MinSucc = i;
243     }
244     
245     // Fold the branch/switch.
246     for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) {
247       if (i == MinSucc) continue;
248       BBTerm->getSuccessor(i)->removePredecessor(BB);
249     }
250     
251     DOUT << "  In block '" << BB->getNameStart()
252          << "' folding undef terminator: " << *BBTerm;
253     BranchInst::Create(BBTerm->getSuccessor(MinSucc), BBTerm);
254     BBTerm->eraseFromParent();
255     return true;
256   }
257   
258   Instruction *CondInst = dyn_cast<Instruction>(Condition);
259
260   // If the condition is an instruction defined in another block, see if a
261   // predecessor has the same condition:
262   //     br COND, BBX, BBY
263   //  BBX:
264   //     br COND, BBZ, BBW
265   if (!Condition->hasOneUse() && // Multiple uses.
266       (CondInst == 0 || CondInst->getParent() != BB)) { // Non-local definition.
267     pred_iterator PI = pred_begin(BB), E = pred_end(BB);
268     if (isa<BranchInst>(BB->getTerminator())) {
269       for (; PI != E; ++PI)
270         if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator()))
271           if (PBI->isConditional() && PBI->getCondition() == Condition &&
272               ProcessBranchOnDuplicateCond(*PI, BB))
273             return true;
274     } else {
275       assert(isa<SwitchInst>(BB->getTerminator()) && "Unknown jump terminator");
276       for (; PI != E; ++PI)
277         if (SwitchInst *PSI = dyn_cast<SwitchInst>((*PI)->getTerminator()))
278           if (PSI->getCondition() == Condition &&
279               ProcessSwitchOnDuplicateCond(*PI, BB))
280             return true;
281     }
282   }
283
284   // If there is only a single predecessor of this block, nothing to fold.
285   if (BB->getSinglePredecessor())
286     return false;
287   
288   // All the rest of our checks depend on the condition being an instruction.
289   if (CondInst == 0)
290     return false;
291   
292   // See if this is a phi node in the current block.
293   if (PHINode *PN = dyn_cast<PHINode>(CondInst))
294     if (PN->getParent() == BB)
295       return ProcessJumpOnPHI(PN);
296   
297   // If this is a conditional branch whose condition is and/or of a phi, try to
298   // simplify it.
299   if ((CondInst->getOpcode() == Instruction::And || 
300        CondInst->getOpcode() == Instruction::Or) &&
301       isa<BranchInst>(BB->getTerminator()) &&
302       ProcessBranchOnLogical(CondInst, BB,
303                              CondInst->getOpcode() == Instruction::And))
304     return true;
305   
306   // If we have "br (phi != 42)" and the phi node has any constant values as 
307   // operands, we can thread through this block.
308   if (CmpInst *CondCmp = dyn_cast<CmpInst>(CondInst))
309     if (isa<PHINode>(CondCmp->getOperand(0)) &&
310         isa<Constant>(CondCmp->getOperand(1)) &&
311         ProcessBranchOnCompare(CondCmp, BB))
312       return true;
313
314   // Check for some cases that are worth simplifying.  Right now we want to look
315   // for loads that are used by a switch or by the condition for the branch.  If
316   // we see one, check to see if it's partially redundant.  If so, insert a PHI
317   // which can then be used to thread the values.
318   //
319   // This is particularly important because reg2mem inserts loads and stores all
320   // over the place, and this blocks jump threading if we don't zap them.
321   Value *SimplifyValue = CondInst;
322   if (CmpInst *CondCmp = dyn_cast<CmpInst>(SimplifyValue))
323     if (isa<Constant>(CondCmp->getOperand(1)))
324       SimplifyValue = CondCmp->getOperand(0);
325   
326   if (LoadInst *LI = dyn_cast<LoadInst>(SimplifyValue))
327     if (SimplifyPartiallyRedundantLoad(LI))
328       return true;
329   
330   // TODO: If we have: "br (X > 0)"  and we have a predecessor where we know
331   // "(X == 4)" thread through this block.
332   
333   return false;
334 }
335
336 /// ProcessBranchOnDuplicateCond - We found a block and a predecessor of that
337 /// block that jump on exactly the same condition.  This means that we almost
338 /// always know the direction of the edge in the DESTBB:
339 ///  PREDBB:
340 ///     br COND, DESTBB, BBY
341 ///  DESTBB:
342 ///     br COND, BBZ, BBW
343 ///
344 /// If DESTBB has multiple predecessors, we can't just constant fold the branch
345 /// in DESTBB, we have to thread over it.
346 bool JumpThreading::ProcessBranchOnDuplicateCond(BasicBlock *PredBB,
347                                                  BasicBlock *BB) {
348   BranchInst *PredBI = cast<BranchInst>(PredBB->getTerminator());
349   
350   // If both successors of PredBB go to DESTBB, we don't know anything.  We can
351   // fold the branch to an unconditional one, which allows other recursive
352   // simplifications.
353   bool BranchDir;
354   if (PredBI->getSuccessor(1) != BB)
355     BranchDir = true;
356   else if (PredBI->getSuccessor(0) != BB)
357     BranchDir = false;
358   else {
359     DOUT << "  In block '" << PredBB->getNameStart()
360          << "' folding terminator: " << *PredBB->getTerminator();
361     ++NumFolds;
362     ConstantFoldTerminator(PredBB);
363     return true;
364   }
365    
366   BranchInst *DestBI = cast<BranchInst>(BB->getTerminator());
367
368   // If the dest block has one predecessor, just fix the branch condition to a
369   // constant and fold it.
370   if (BB->getSinglePredecessor()) {
371     DOUT << "  In block '" << BB->getNameStart()
372          << "' folding condition to '" << BranchDir << "': "
373          << *BB->getTerminator();
374     ++NumFolds;
375     DestBI->setCondition(ConstantInt::get(Type::Int1Ty, BranchDir));
376     ConstantFoldTerminator(BB);
377     return true;
378   }
379   
380   // Otherwise we need to thread from PredBB to DestBB's successor which
381   // involves code duplication.  Check to see if it is worth it.
382   unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB);
383   if (JumpThreadCost > Threshold) {
384     DOUT << "  Not threading BB '" << BB->getNameStart()
385          << "' - Cost is too high: " << JumpThreadCost << "\n";
386     return false;
387   }
388   
389   // Next, figure out which successor we are threading to.
390   BasicBlock *SuccBB = DestBI->getSuccessor(!BranchDir);
391   
392   // If threading to the same block as we come from, we would infinite loop.
393   if (SuccBB == BB) {
394     DOUT << "  Not threading BB '" << BB->getNameStart()
395          << "' - would thread to self!\n";
396     return false;
397   }
398   
399   // And finally, do it!
400   DOUT << "  Threading edge from '" << PredBB->getNameStart() << "' to '"
401        << SuccBB->getNameStart() << "' with cost: " << JumpThreadCost
402        << ", across block:\n    "
403        << *BB << "\n";
404   
405   ThreadEdge(BB, PredBB, SuccBB);
406   ++NumThreads;
407   return true;
408 }
409
410 /// ProcessSwitchOnDuplicateCond - We found a block and a predecessor of that
411 /// block that switch on exactly the same condition.  This means that we almost
412 /// always know the direction of the edge in the DESTBB:
413 ///  PREDBB:
414 ///     switch COND [... DESTBB, BBY ... ]
415 ///  DESTBB:
416 ///     switch COND [... BBZ, BBW ]
417 ///
418 /// Optimizing switches like this is very important, because simplifycfg builds
419 /// switches out of repeated 'if' conditions.
420 bool JumpThreading::ProcessSwitchOnDuplicateCond(BasicBlock *PredBB,
421                                                  BasicBlock *DestBB) {
422   // Can't thread edge to self.
423   if (PredBB == DestBB)
424     return false;
425   
426   
427   SwitchInst *PredSI = cast<SwitchInst>(PredBB->getTerminator());
428   SwitchInst *DestSI = cast<SwitchInst>(DestBB->getTerminator());
429
430   // There are a variety of optimizations that we can potentially do on these
431   // blocks: we order them from most to least preferable.
432   
433   // If DESTBB *just* contains the switch, then we can forward edges from PREDBB
434   // directly to their destination.  This does not introduce *any* code size
435   // growth.
436   
437   // FIXME: Thread if it just contains a PHI.
438   if (isa<SwitchInst>(DestBB->begin())) {
439     bool MadeChange = false;
440     // Ignore the default edge for now.
441     for (unsigned i = 1, e = DestSI->getNumSuccessors(); i != e; ++i) {
442       ConstantInt *DestVal = DestSI->getCaseValue(i);
443       BasicBlock *DestSucc = DestSI->getSuccessor(i);
444       
445       // Okay, DestSI has a case for 'DestVal' that goes to 'DestSucc'.  See if
446       // PredSI has an explicit case for it.  If so, forward.  If it is covered
447       // by the default case, we can't update PredSI.
448       unsigned PredCase = PredSI->findCaseValue(DestVal);
449       if (PredCase == 0) continue;
450       
451       // If PredSI doesn't go to DestBB on this value, then it won't reach the
452       // case on this condition.
453       if (PredSI->getSuccessor(PredCase) != DestBB &&
454           DestSI->getSuccessor(i) != DestBB)
455         continue;
456
457       // Otherwise, we're safe to make the change.  Make sure that the edge from
458       // DestSI to DestSucc is not critical and has no PHI nodes.
459       DOUT << "FORWARDING EDGE " << *DestVal << "   FROM: " << *PredSI;
460       DOUT << "THROUGH: " << *DestSI;
461
462       // If the destination has PHI nodes, just split the edge for updating
463       // simplicity.
464       if (isa<PHINode>(DestSucc->begin()) && !DestSucc->getSinglePredecessor()){
465         SplitCriticalEdge(DestSI, i, this);
466         DestSucc = DestSI->getSuccessor(i);
467       }
468       FoldSingleEntryPHINodes(DestSucc);
469       PredSI->setSuccessor(PredCase, DestSucc);
470       MadeChange = true;
471     }
472     
473     if (MadeChange)
474       return true;
475   }
476   
477   return false;
478 }
479
480
481 /// SimplifyPartiallyRedundantLoad - If LI is an obviously partially redundant
482 /// load instruction, eliminate it by replacing it with a PHI node.  This is an
483 /// important optimization that encourages jump threading, and needs to be run
484 /// interlaced with other jump threading tasks.
485 bool JumpThreading::SimplifyPartiallyRedundantLoad(LoadInst *LI) {
486   // Don't hack volatile loads.
487   if (LI->isVolatile()) return false;
488   
489   // If the load is defined in a block with exactly one predecessor, it can't be
490   // partially redundant.
491   BasicBlock *LoadBB = LI->getParent();
492   if (LoadBB->getSinglePredecessor())
493     return false;
494   
495   Value *LoadedPtr = LI->getOperand(0);
496
497   // If the loaded operand is defined in the LoadBB, it can't be available.
498   // FIXME: Could do PHI translation, that would be fun :)
499   if (Instruction *PtrOp = dyn_cast<Instruction>(LoadedPtr))
500     if (PtrOp->getParent() == LoadBB)
501       return false;
502   
503   // Scan a few instructions up from the load, to see if it is obviously live at
504   // the entry to its block.
505   BasicBlock::iterator BBIt = LI;
506
507   if (Value *AvailableVal = FindAvailableLoadedValue(LoadedPtr, LoadBB, 
508                                                      BBIt, 6)) {
509     // If the value if the load is locally available within the block, just use
510     // it.  This frequently occurs for reg2mem'd allocas.
511     //cerr << "LOAD ELIMINATED:\n" << *BBIt << *LI << "\n";
512     
513     // If the returned value is the load itself, replace with an undef. This can
514     // only happen in dead loops.
515     if (AvailableVal == LI) AvailableVal = UndefValue::get(LI->getType());
516     LI->replaceAllUsesWith(AvailableVal);
517     LI->eraseFromParent();
518     return true;
519   }
520
521   // Otherwise, if we scanned the whole block and got to the top of the block,
522   // we know the block is locally transparent to the load.  If not, something
523   // might clobber its value.
524   if (BBIt != LoadBB->begin())
525     return false;
526   
527   
528   SmallPtrSet<BasicBlock*, 8> PredsScanned;
529   typedef SmallVector<std::pair<BasicBlock*, Value*>, 8> AvailablePredsTy;
530   AvailablePredsTy AvailablePreds;
531   BasicBlock *OneUnavailablePred = 0;
532   
533   // If we got here, the loaded value is transparent through to the start of the
534   // block.  Check to see if it is available in any of the predecessor blocks.
535   for (pred_iterator PI = pred_begin(LoadBB), PE = pred_end(LoadBB);
536        PI != PE; ++PI) {
537     BasicBlock *PredBB = *PI;
538
539     // If we already scanned this predecessor, skip it.
540     if (!PredsScanned.insert(PredBB))
541       continue;
542
543     // Scan the predecessor to see if the value is available in the pred.
544     BBIt = PredBB->end();
545     Value *PredAvailable = FindAvailableLoadedValue(LoadedPtr, PredBB, BBIt, 6);
546     if (!PredAvailable) {
547       OneUnavailablePred = PredBB;
548       continue;
549     }
550     
551     // If so, this load is partially redundant.  Remember this info so that we
552     // can create a PHI node.
553     AvailablePreds.push_back(std::make_pair(PredBB, PredAvailable));
554   }
555   
556   // If the loaded value isn't available in any predecessor, it isn't partially
557   // redundant.
558   if (AvailablePreds.empty()) return false;
559   
560   // Okay, the loaded value is available in at least one (and maybe all!)
561   // predecessors.  If the value is unavailable in more than one unique
562   // predecessor, we want to insert a merge block for those common predecessors.
563   // This ensures that we only have to insert one reload, thus not increasing
564   // code size.
565   BasicBlock *UnavailablePred = 0;
566   
567   // If there is exactly one predecessor where the value is unavailable, the
568   // already computed 'OneUnavailablePred' block is it.  If it ends in an
569   // unconditional branch, we know that it isn't a critical edge.
570   if (PredsScanned.size() == AvailablePreds.size()+1 &&
571       OneUnavailablePred->getTerminator()->getNumSuccessors() == 1) {
572     UnavailablePred = OneUnavailablePred;
573   } else if (PredsScanned.size() != AvailablePreds.size()) {
574     // Otherwise, we had multiple unavailable predecessors or we had a critical
575     // edge from the one.
576     SmallVector<BasicBlock*, 8> PredsToSplit;
577     SmallPtrSet<BasicBlock*, 8> AvailablePredSet;
578
579     for (unsigned i = 0, e = AvailablePreds.size(); i != e; ++i)
580       AvailablePredSet.insert(AvailablePreds[i].first);
581
582     // Add all the unavailable predecessors to the PredsToSplit list.
583     for (pred_iterator PI = pred_begin(LoadBB), PE = pred_end(LoadBB);
584          PI != PE; ++PI)
585       if (!AvailablePredSet.count(*PI))
586         PredsToSplit.push_back(*PI);
587     
588     // Split them out to their own block.
589     UnavailablePred =
590       SplitBlockPredecessors(LoadBB, &PredsToSplit[0], PredsToSplit.size(),
591                              "thread-split", this);
592   }
593   
594   // If the value isn't available in all predecessors, then there will be
595   // exactly one where it isn't available.  Insert a load on that edge and add
596   // it to the AvailablePreds list.
597   if (UnavailablePred) {
598     assert(UnavailablePred->getTerminator()->getNumSuccessors() == 1 &&
599            "Can't handle critical edge here!");
600     Value *NewVal = new LoadInst(LoadedPtr, LI->getName()+".pr",
601                                  UnavailablePred->getTerminator());
602     AvailablePreds.push_back(std::make_pair(UnavailablePred, NewVal));
603   }
604   
605   // Now we know that each predecessor of this block has a value in
606   // AvailablePreds, sort them for efficient access as we're walking the preds.
607   array_pod_sort(AvailablePreds.begin(), AvailablePreds.end());
608   
609   // Create a PHI node at the start of the block for the PRE'd load value.
610   PHINode *PN = PHINode::Create(LI->getType(), "", LoadBB->begin());
611   PN->takeName(LI);
612   
613   // Insert new entries into the PHI for each predecessor.  A single block may
614   // have multiple entries here.
615   for (pred_iterator PI = pred_begin(LoadBB), E = pred_end(LoadBB); PI != E;
616        ++PI) {
617     AvailablePredsTy::iterator I = 
618       std::lower_bound(AvailablePreds.begin(), AvailablePreds.end(),
619                        std::make_pair(*PI, (Value*)0));
620     
621     assert(I != AvailablePreds.end() && I->first == *PI &&
622            "Didn't find entry for predecessor!");
623     
624     PN->addIncoming(I->second, I->first);
625   }
626   
627   //cerr << "PRE: " << *LI << *PN << "\n";
628   
629   LI->replaceAllUsesWith(PN);
630   LI->eraseFromParent();
631   
632   return true;
633 }
634
635
636 /// ProcessJumpOnPHI - We have a conditional branch of switch on a PHI node in
637 /// the current block.  See if there are any simplifications we can do based on
638 /// inputs to the phi node.
639 /// 
640 bool JumpThreading::ProcessJumpOnPHI(PHINode *PN) {
641   // See if the phi node has any constant values.  If so, we can determine where
642   // the corresponding predecessor will branch.
643   ConstantInt *PredCst = 0;
644   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
645     if ((PredCst = dyn_cast<ConstantInt>(PN->getIncomingValue(i))))
646       break;
647   
648   // If no incoming value has a constant, we don't know the destination of any
649   // predecessors.
650   if (PredCst == 0)
651     return false;
652   
653   // See if the cost of duplicating this block is low enough.
654   BasicBlock *BB = PN->getParent();
655   unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB);
656   if (JumpThreadCost > Threshold) {
657     DOUT << "  Not threading BB '" << BB->getNameStart()
658          << "' - Cost is too high: " << JumpThreadCost << "\n";
659     return false;
660   }
661   
662   // If so, we can actually do this threading.  Merge any common predecessors
663   // that will act the same.
664   BasicBlock *PredBB = FactorCommonPHIPreds(PN, PredCst);
665   
666   // Next, figure out which successor we are threading to.
667   BasicBlock *SuccBB;
668   if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()))
669     SuccBB = BI->getSuccessor(PredCst == ConstantInt::getFalse());
670   else {
671     SwitchInst *SI = cast<SwitchInst>(BB->getTerminator());
672     SuccBB = SI->getSuccessor(SI->findCaseValue(PredCst));
673   }
674   
675   // If threading to the same block as we come from, we would infinite loop.
676   if (SuccBB == BB) {
677     DOUT << "  Not threading BB '" << BB->getNameStart()
678          << "' - would thread to self!\n";
679     return false;
680   }
681   
682   // And finally, do it!
683   DOUT << "  Threading edge from '" << PredBB->getNameStart() << "' to '"
684        << SuccBB->getNameStart() << "' with cost: " << JumpThreadCost
685        << ", across block:\n    "
686        << *BB << "\n";
687        
688   ThreadEdge(BB, PredBB, SuccBB);
689   ++NumThreads;
690   return true;
691 }
692
693 /// ProcessJumpOnLogicalPHI - PN's basic block contains a conditional branch
694 /// whose condition is an AND/OR where one side is PN.  If PN has constant
695 /// operands that permit us to evaluate the condition for some operand, thread
696 /// through the block.  For example with:
697 ///   br (and X, phi(Y, Z, false))
698 /// the predecessor corresponding to the 'false' will always jump to the false
699 /// destination of the branch.
700 ///
701 bool JumpThreading::ProcessBranchOnLogical(Value *V, BasicBlock *BB,
702                                            bool isAnd) {
703   // If this is a binary operator tree of the same AND/OR opcode, check the
704   // LHS/RHS.
705   if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V))
706     if ((isAnd && BO->getOpcode() == Instruction::And) ||
707         (!isAnd && BO->getOpcode() == Instruction::Or)) {
708       if (ProcessBranchOnLogical(BO->getOperand(0), BB, isAnd))
709         return true;
710       if (ProcessBranchOnLogical(BO->getOperand(1), BB, isAnd))
711         return true;
712     }
713       
714   // If this isn't a PHI node, we can't handle it.
715   PHINode *PN = dyn_cast<PHINode>(V);
716   if (!PN || PN->getParent() != BB) return false;
717                                              
718   // We can only do the simplification for phi nodes of 'false' with AND or
719   // 'true' with OR.  See if we have any entries in the phi for this.
720   unsigned PredNo = ~0U;
721   ConstantInt *PredCst = ConstantInt::get(Type::Int1Ty, !isAnd);
722   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
723     if (PN->getIncomingValue(i) == PredCst) {
724       PredNo = i;
725       break;
726     }
727   }
728   
729   // If no match, bail out.
730   if (PredNo == ~0U)
731     return false;
732   
733   // See if the cost of duplicating this block is low enough.
734   unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB);
735   if (JumpThreadCost > Threshold) {
736     DOUT << "  Not threading BB '" << BB->getNameStart()
737          << "' - Cost is too high: " << JumpThreadCost << "\n";
738     return false;
739   }
740
741   // If so, we can actually do this threading.  Merge any common predecessors
742   // that will act the same.
743   BasicBlock *PredBB = FactorCommonPHIPreds(PN, PredCst);
744   
745   // Next, figure out which successor we are threading to.  If this was an AND,
746   // the constant must be FALSE, and we must be targeting the 'false' block.
747   // If this is an OR, the constant must be TRUE, and we must be targeting the
748   // 'true' block.
749   BasicBlock *SuccBB = BB->getTerminator()->getSuccessor(isAnd);
750   
751   // If threading to the same block as we come from, we would infinite loop.
752   if (SuccBB == BB) {
753     DOUT << "  Not threading BB '" << BB->getNameStart()
754     << "' - would thread to self!\n";
755     return false;
756   }
757   
758   // And finally, do it!
759   DOUT << "  Threading edge through bool from '" << PredBB->getNameStart()
760        << "' to '" << SuccBB->getNameStart() << "' with cost: "
761        << JumpThreadCost << ", across block:\n    "
762        << *BB << "\n";
763   
764   ThreadEdge(BB, PredBB, SuccBB);
765   ++NumThreads;
766   return true;
767 }
768
769 /// ProcessBranchOnCompare - We found a branch on a comparison between a phi
770 /// node and a constant.  If the PHI node contains any constants as inputs, we
771 /// can fold the compare for that edge and thread through it.
772 bool JumpThreading::ProcessBranchOnCompare(CmpInst *Cmp, BasicBlock *BB) {
773   PHINode *PN = cast<PHINode>(Cmp->getOperand(0));
774   Constant *RHS = cast<Constant>(Cmp->getOperand(1));
775   
776   // If the phi isn't in the current block, an incoming edge to this block
777   // doesn't control the destination.
778   if (PN->getParent() != BB)
779     return false;
780   
781   // We can do this simplification if any comparisons fold to true or false.
782   // See if any do.
783   Constant *PredCst = 0;
784   bool TrueDirection = false;
785   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
786     PredCst = dyn_cast<Constant>(PN->getIncomingValue(i));
787     if (PredCst == 0) continue;
788     
789     Constant *Res;
790     if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cmp))
791       Res = ConstantExpr::getICmp(ICI->getPredicate(), PredCst, RHS);
792     else
793       Res = ConstantExpr::getFCmp(cast<FCmpInst>(Cmp)->getPredicate(),
794                                   PredCst, RHS);
795     // If this folded to a constant expr, we can't do anything.
796     if (ConstantInt *ResC = dyn_cast<ConstantInt>(Res)) {
797       TrueDirection = ResC->getZExtValue();
798       break;
799     }
800     // If this folded to undef, just go the false way.
801     if (isa<UndefValue>(Res)) {
802       TrueDirection = false;
803       break;
804     }
805     
806     // Otherwise, we can't fold this input.
807     PredCst = 0;
808   }
809   
810   // If no match, bail out.
811   if (PredCst == 0)
812     return false;
813   
814   // See if the cost of duplicating this block is low enough.
815   unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB);
816   if (JumpThreadCost > Threshold) {
817     DOUT << "  Not threading BB '" << BB->getNameStart()
818          << "' - Cost is too high: " << JumpThreadCost << "\n";
819     return false;
820   }
821   
822   // If so, we can actually do this threading.  Merge any common predecessors
823   // that will act the same.
824   BasicBlock *PredBB = FactorCommonPHIPreds(PN, PredCst);
825   
826   // Next, get our successor.
827   BasicBlock *SuccBB = BB->getTerminator()->getSuccessor(!TrueDirection);
828   
829   // If threading to the same block as we come from, we would infinite loop.
830   if (SuccBB == BB) {
831     DOUT << "  Not threading BB '" << BB->getNameStart()
832     << "' - would thread to self!\n";
833     return false;
834   }
835   
836   
837   // And finally, do it!
838   DOUT << "  Threading edge through bool from '" << PredBB->getNameStart()
839        << "' to '" << SuccBB->getNameStart() << "' with cost: "
840        << JumpThreadCost << ", across block:\n    "
841        << *BB << "\n";
842   
843   ThreadEdge(BB, PredBB, SuccBB);
844   ++NumThreads;
845   return true;
846 }
847
848
849 /// ThreadEdge - We have decided that it is safe and profitable to thread an
850 /// edge from PredBB to SuccBB across BB.  Transform the IR to reflect this
851 /// change.
852 void JumpThreading::ThreadEdge(BasicBlock *BB, BasicBlock *PredBB, 
853                                BasicBlock *SuccBB) {
854
855   // Jump Threading can not update SSA properties correctly if the values
856   // defined in the duplicated block are used outside of the block itself.  For
857   // this reason, we spill all values that are used outside of BB to the stack.
858   for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) {
859     if (!I->isUsedOutsideOfBlock(BB))
860       continue;
861     
862     // We found a use of I outside of BB.  Create a new stack slot to
863     // break this inter-block usage pattern.
864     DemoteRegToStack(*I);
865   }
866  
867   // We are going to have to map operands from the original BB block to the new
868   // copy of the block 'NewBB'.  If there are PHI nodes in BB, evaluate them to
869   // account for entry from PredBB.
870   DenseMap<Instruction*, Value*> ValueMapping;
871   
872   BasicBlock *NewBB =
873     BasicBlock::Create(BB->getName()+".thread", BB->getParent(), BB);
874   NewBB->moveAfter(PredBB);
875   
876   BasicBlock::iterator BI = BB->begin();
877   for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
878     ValueMapping[PN] = PN->getIncomingValueForBlock(PredBB);
879   
880   // Clone the non-phi instructions of BB into NewBB, keeping track of the
881   // mapping and using it to remap operands in the cloned instructions.
882   for (; !isa<TerminatorInst>(BI); ++BI) {
883     Instruction *New = BI->clone();
884     New->setName(BI->getNameStart());
885     NewBB->getInstList().push_back(New);
886     ValueMapping[BI] = New;
887    
888     // Remap operands to patch up intra-block references.
889     for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
890       if (Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i)))
891         if (Value *Remapped = ValueMapping[Inst])
892           New->setOperand(i, Remapped);
893   }
894   
895   // We didn't copy the terminator from BB over to NewBB, because there is now
896   // an unconditional jump to SuccBB.  Insert the unconditional jump.
897   BranchInst::Create(SuccBB, NewBB);
898   
899   // Check to see if SuccBB has PHI nodes. If so, we need to add entries to the
900   // PHI nodes for NewBB now.
901   for (BasicBlock::iterator PNI = SuccBB->begin(); isa<PHINode>(PNI); ++PNI) {
902     PHINode *PN = cast<PHINode>(PNI);
903     // Ok, we have a PHI node.  Figure out what the incoming value was for the
904     // DestBlock.
905     Value *IV = PN->getIncomingValueForBlock(BB);
906     
907     // Remap the value if necessary.
908     if (Instruction *Inst = dyn_cast<Instruction>(IV))
909       if (Value *MappedIV = ValueMapping[Inst])
910         IV = MappedIV;
911     PN->addIncoming(IV, NewBB);
912   }
913   
914   // Ok, NewBB is good to go.  Update the terminator of PredBB to jump to
915   // NewBB instead of BB.  This eliminates predecessors from BB, which requires
916   // us to simplify any PHI nodes in BB.
917   TerminatorInst *PredTerm = PredBB->getTerminator();
918   for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i)
919     if (PredTerm->getSuccessor(i) == BB) {
920       BB->removePredecessor(PredBB);
921       PredTerm->setSuccessor(i, NewBB);
922     }
923   
924   // At this point, the IR is fully up to date and consistent.  Do a quick scan
925   // over the new instructions and zap any that are constants or dead.  This
926   // frequently happens because of phi translation.
927   BI = NewBB->begin();
928   for (BasicBlock::iterator E = NewBB->end(); BI != E; ) {
929     Instruction *Inst = BI++;
930     if (Constant *C = ConstantFoldInstruction(Inst, TD)) {
931       Inst->replaceAllUsesWith(C);
932       Inst->eraseFromParent();
933       continue;
934     }
935     
936     RecursivelyDeleteTriviallyDeadInstructions(Inst);
937   }
938 }