LLVM API Documentation

JumpThreading.cpp

Go to the documentation of this file.
00001 //===- JumpThreading.cpp - Thread control through conditional blocks ------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements the Jump Threading pass.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #define DEBUG_TYPE "jump-threading"
00015 #include "llvm/Transforms/Scalar.h"
00016 #include "llvm/IntrinsicInst.h"
00017 #include "llvm/LLVMContext.h"
00018 #include "llvm/Pass.h"
00019 #include "llvm/Analysis/ConstantFolding.h"
00020 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
00021 #include "llvm/Transforms/Utils/Local.h"
00022 #include "llvm/Target/TargetData.h"
00023 #include "llvm/ADT/DenseMap.h"
00024 #include "llvm/ADT/Statistic.h"
00025 #include "llvm/ADT/STLExtras.h"
00026 #include "llvm/ADT/SmallPtrSet.h"
00027 #include "llvm/ADT/SmallSet.h"
00028 #include "llvm/Support/CommandLine.h"
00029 #include "llvm/Support/Compiler.h"
00030 #include "llvm/Support/Debug.h"
00031 #include "llvm/Support/ValueHandle.h"
00032 #include "llvm/Support/raw_ostream.h"
00033 using namespace llvm;
00034 
00035 STATISTIC(NumThreads, "Number of jumps threaded");
00036 STATISTIC(NumFolds,   "Number of terminators folded");
00037 
00038 static cl::opt<unsigned>
00039 Threshold("jump-threading-threshold", 
00040           cl::desc("Max block size to duplicate for jump threading"),
00041           cl::init(6), cl::Hidden);
00042 
00043 namespace {
00044   /// This pass performs 'jump threading', which looks at blocks that have
00045   /// multiple predecessors and multiple successors.  If one or more of the
00046   /// predecessors of the block can be proven to always jump to one of the
00047   /// successors, we forward the edge from the predecessor to the successor by
00048   /// duplicating the contents of this block.
00049   ///
00050   /// An example of when this can occur is code like this:
00051   ///
00052   ///   if () { ...
00053   ///     X = 4;
00054   ///   }
00055   ///   if (X < 3) {
00056   ///
00057   /// In this case, the unconditional branch at the end of the first if can be
00058   /// revectored to the false side of the second if.
00059   ///
00060   class VISIBILITY_HIDDEN JumpThreading : public FunctionPass {
00061     TargetData *TD;
00062 #ifdef NDEBUG
00063     SmallPtrSet<BasicBlock*, 16> LoopHeaders;
00064 #else
00065     SmallSet<AssertingVH<BasicBlock>, 16> LoopHeaders;
00066 #endif
00067   public:
00068     static char ID; // Pass identification
00069     JumpThreading() : FunctionPass(&ID) {}
00070 
00071     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00072     }
00073 
00074     bool runOnFunction(Function &F);
00075     void FindLoopHeaders(Function &F);
00076     
00077     bool ProcessBlock(BasicBlock *BB);
00078     bool ThreadEdge(BasicBlock *BB, BasicBlock *PredBB, BasicBlock *SuccBB,
00079                     unsigned JumpThreadCost);
00080     BasicBlock *FactorCommonPHIPreds(PHINode *PN, Value *Val);
00081     bool ProcessBranchOnDuplicateCond(BasicBlock *PredBB, BasicBlock *DestBB);
00082     bool ProcessSwitchOnDuplicateCond(BasicBlock *PredBB, BasicBlock *DestBB);
00083 
00084     bool ProcessJumpOnPHI(PHINode *PN);
00085     bool ProcessBranchOnLogical(Value *V, BasicBlock *BB, bool isAnd);
00086     bool ProcessBranchOnCompare(CmpInst *Cmp, BasicBlock *BB);
00087     
00088     bool SimplifyPartiallyRedundantLoad(LoadInst *LI);
00089   };
00090 }
00091 
00092 char JumpThreading::ID = 0;
00093 static RegisterPass<JumpThreading>
00094 X("jump-threading", "Jump Threading");
00095 
00096 // Public interface to the Jump Threading pass
00097 FunctionPass *llvm::createJumpThreadingPass() { return new JumpThreading(); }
00098 
00099 /// runOnFunction - Top level algorithm.
00100 ///
00101 bool JumpThreading::runOnFunction(Function &F) {
00102   DEBUG(errs() << "Jump threading on function '" << F.getName() << "'\n");
00103   TD = getAnalysisIfAvailable<TargetData>();
00104   
00105   FindLoopHeaders(F);
00106   
00107   bool AnotherIteration = true, EverChanged = false;
00108   while (AnotherIteration) {
00109     AnotherIteration = false;
00110     bool Changed = false;
00111     for (Function::iterator I = F.begin(), E = F.end(); I != E;) {
00112       BasicBlock *BB = I;
00113       while (ProcessBlock(BB))
00114         Changed = true;
00115       
00116       ++I;
00117       
00118       // If the block is trivially dead, zap it.  This eliminates the successor
00119       // edges which simplifies the CFG.
00120       if (pred_begin(BB) == pred_end(BB) &&
00121           BB != &BB->getParent()->getEntryBlock()) {
00122         DEBUG(errs() << "  JT: Deleting dead block '" << BB->getName()
00123               << "' with terminator: " << *BB->getTerminator());
00124         LoopHeaders.erase(BB);
00125         DeleteDeadBlock(BB);
00126         Changed = true;
00127       }
00128     }
00129     AnotherIteration = Changed;
00130     EverChanged |= Changed;
00131   }
00132   
00133   LoopHeaders.clear();
00134   return EverChanged;
00135 }
00136 
00137 /// FindLoopHeaders - We do not want jump threading to turn proper loop
00138 /// structures into irreducible loops.  Doing this breaks up the loop nesting
00139 /// hierarchy and pessimizes later transformations.  To prevent this from
00140 /// happening, we first have to find the loop headers.  Here we approximate this
00141 /// by finding targets of backedges in the CFG.
00142 ///
00143 /// Note that there definitely are cases when we want to allow threading of
00144 /// edges across a loop header.  For example, threading a jump from outside the
00145 /// loop (the preheader) to an exit block of the loop is definitely profitable.
00146 /// It is also almost always profitable to thread backedges from within the loop
00147 /// to exit blocks, and is often profitable to thread backedges to other blocks
00148 /// within the loop (forming a nested loop).  This simple analysis is not rich
00149 /// enough to track all of these properties and keep it up-to-date as the CFG
00150 /// mutates, so we don't allow any of these transformations.
00151 ///
00152 void JumpThreading::FindLoopHeaders(Function &F) {
00153   SmallVector<std::pair<const BasicBlock*,const BasicBlock*>, 32> Edges;
00154   FindFunctionBackedges(F, Edges);
00155   
00156   for (unsigned i = 0, e = Edges.size(); i != e; ++i)
00157     LoopHeaders.insert(const_cast<BasicBlock*>(Edges[i].second));
00158 }
00159 
00160 
00161 /// FactorCommonPHIPreds - If there are multiple preds with the same incoming
00162 /// value for the PHI, factor them together so we get one block to thread for
00163 /// the whole group.
00164 /// This is important for things like "phi i1 [true, true, false, true, x]"
00165 /// where we only need to clone the block for the true blocks once.
00166 ///
00167 BasicBlock *JumpThreading::FactorCommonPHIPreds(PHINode *PN, Value *Val) {
00168   SmallVector<BasicBlock*, 16> CommonPreds;
00169   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
00170     if (PN->getIncomingValue(i) == Val)
00171       CommonPreds.push_back(PN->getIncomingBlock(i));
00172   
00173   if (CommonPreds.size() == 1)
00174     return CommonPreds[0];
00175     
00176   DEBUG(errs() << "  Factoring out " << CommonPreds.size()
00177         << " common predecessors.\n");
00178   return SplitBlockPredecessors(PN->getParent(),
00179                                 &CommonPreds[0], CommonPreds.size(),
00180                                 ".thr_comm", this);
00181 }
00182   
00183 
00184 /// getJumpThreadDuplicationCost - Return the cost of duplicating this block to
00185 /// thread across it.
00186 static unsigned getJumpThreadDuplicationCost(const BasicBlock *BB) {
00187   /// Ignore PHI nodes, these will be flattened when duplication happens.
00188   BasicBlock::const_iterator I = BB->getFirstNonPHI();
00189 
00190   // Sum up the cost of each instruction until we get to the terminator.  Don't
00191   // include the terminator because the copy won't include it.
00192   unsigned Size = 0;
00193   for (; !isa<TerminatorInst>(I); ++I) {
00194     // Debugger intrinsics don't incur code size.
00195     if (isa<DbgInfoIntrinsic>(I)) continue;
00196     
00197     // If this is a pointer->pointer bitcast, it is free.
00198     if (isa<BitCastInst>(I) && isa<PointerType>(I->getType()))
00199       continue;
00200     
00201     // All other instructions count for at least one unit.
00202     ++Size;
00203     
00204     // Calls are more expensive.  If they are non-intrinsic calls, we model them
00205     // as having cost of 4.  If they are a non-vector intrinsic, we model them
00206     // as having cost of 2 total, and if they are a vector intrinsic, we model
00207     // them as having cost 1.
00208     if (const CallInst *CI = dyn_cast<CallInst>(I)) {
00209       if (!isa<IntrinsicInst>(CI))
00210         Size += 3;
00211       else if (!isa<VectorType>(CI->getType()))
00212         Size += 1;
00213     }
00214   }
00215   
00216   // Threading through a switch statement is particularly profitable.  If this
00217   // block ends in a switch, decrease its cost to make it more likely to happen.
00218   if (isa<SwitchInst>(I))
00219     Size = Size > 6 ? Size-6 : 0;
00220   
00221   return Size;
00222 }
00223 
00224 /// ProcessBlock - If there are any predecessors whose control can be threaded
00225 /// through to a successor, transform them now.
00226 bool JumpThreading::ProcessBlock(BasicBlock *BB) {
00227   // If this block has a single predecessor, and if that pred has a single
00228   // successor, merge the blocks.  This encourages recursive jump threading
00229   // because now the condition in this block can be threaded through
00230   // predecessors of our predecessor block.
00231   if (BasicBlock *SinglePred = BB->getSinglePredecessor())
00232     if (SinglePred->getTerminator()->getNumSuccessors() == 1 &&
00233         SinglePred != BB) {
00234       // If SinglePred was a loop header, BB becomes one.
00235       if (LoopHeaders.erase(SinglePred))
00236         LoopHeaders.insert(BB);
00237       
00238       // Remember if SinglePred was the entry block of the function.  If so, we
00239       // will need to move BB back to the entry position.
00240       bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock();
00241       MergeBasicBlockIntoOnlyPred(BB);
00242       
00243       if (isEntry && BB != &BB->getParent()->getEntryBlock())
00244         BB->moveBefore(&BB->getParent()->getEntryBlock());
00245       return true;
00246     }
00247   
00248   // See if this block ends with a branch or switch.  If so, see if the
00249   // condition is a phi node.  If so, and if an entry of the phi node is a
00250   // constant, we can thread the block.
00251   Value *Condition;
00252   if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) {
00253     // Can't thread an unconditional jump.
00254     if (BI->isUnconditional()) return false;
00255     Condition = BI->getCondition();
00256   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator()))
00257     Condition = SI->getCondition();
00258   else
00259     return false; // Must be an invoke.
00260   
00261   // If the terminator of this block is branching on a constant, simplify the
00262   // terminator to an unconditional branch.  This can occur due to threading in
00263   // other blocks.
00264   if (isa<ConstantInt>(Condition)) {
00265     DEBUG(errs() << "  In block '" << BB->getName()
00266           << "' folding terminator: " << *BB->getTerminator());
00267     ++NumFolds;
00268     ConstantFoldTerminator(BB);
00269     return true;
00270   }
00271   
00272   // If the terminator is branching on an undef, we can pick any of the
00273   // successors to branch to.  Since this is arbitrary, we pick the successor
00274   // with the fewest predecessors.  This should reduce the in-degree of the
00275   // others.
00276   if (isa<UndefValue>(Condition)) {
00277     TerminatorInst *BBTerm = BB->getTerminator();
00278     unsigned MinSucc = 0;
00279     BasicBlock *TestBB = BBTerm->getSuccessor(MinSucc);
00280     // Compute the successor with the minimum number of predecessors.
00281     unsigned MinNumPreds = std::distance(pred_begin(TestBB), pred_end(TestBB));
00282     for (unsigned i = 1, e = BBTerm->getNumSuccessors(); i != e; ++i) {
00283       TestBB = BBTerm->getSuccessor(i);
00284       unsigned NumPreds = std::distance(pred_begin(TestBB), pred_end(TestBB));
00285       if (NumPreds < MinNumPreds)
00286         MinSucc = i;
00287     }
00288     
00289     // Fold the branch/switch.
00290     for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) {
00291       if (i == MinSucc) continue;
00292       BBTerm->getSuccessor(i)->removePredecessor(BB);
00293     }
00294     
00295     DEBUG(errs() << "  In block '" << BB->getName()
00296           << "' folding undef terminator: " << *BBTerm);
00297     BranchInst::Create(BBTerm->getSuccessor(MinSucc), BBTerm);
00298     BBTerm->eraseFromParent();
00299     return true;
00300   }
00301   
00302   Instruction *CondInst = dyn_cast<Instruction>(Condition);
00303 
00304   // If the condition is an instruction defined in another block, see if a
00305   // predecessor has the same condition:
00306   //     br COND, BBX, BBY
00307   //  BBX:
00308   //     br COND, BBZ, BBW
00309   if (!Condition->hasOneUse() && // Multiple uses.
00310       (CondInst == 0 || CondInst->getParent() != BB)) { // Non-local definition.
00311     pred_iterator PI = pred_begin(BB), E = pred_end(BB);
00312     if (isa<BranchInst>(BB->getTerminator())) {
00313       for (; PI != E; ++PI)
00314         if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator()))
00315           if (PBI->isConditional() && PBI->getCondition() == Condition &&
00316               ProcessBranchOnDuplicateCond(*PI, BB))
00317             return true;
00318     } else {
00319       assert(isa<SwitchInst>(BB->getTerminator()) && "Unknown jump terminator");
00320       for (; PI != E; ++PI)
00321         if (SwitchInst *PSI = dyn_cast<SwitchInst>((*PI)->getTerminator()))
00322           if (PSI->getCondition() == Condition &&
00323               ProcessSwitchOnDuplicateCond(*PI, BB))
00324             return true;
00325     }
00326   }
00327 
00328   // All the rest of our checks depend on the condition being an instruction.
00329   if (CondInst == 0)
00330     return false;
00331   
00332   // See if this is a phi node in the current block.
00333   if (PHINode *PN = dyn_cast<PHINode>(CondInst))
00334     if (PN->getParent() == BB)
00335       return ProcessJumpOnPHI(PN);
00336   
00337   // If this is a conditional branch whose condition is and/or of a phi, try to
00338   // simplify it.
00339   if ((CondInst->getOpcode() == Instruction::And || 
00340        CondInst->getOpcode() == Instruction::Or) &&
00341       isa<BranchInst>(BB->getTerminator()) &&
00342       ProcessBranchOnLogical(CondInst, BB,
00343                              CondInst->getOpcode() == Instruction::And))
00344     return true;
00345   
00346   if (CmpInst *CondCmp = dyn_cast<CmpInst>(CondInst)) {
00347     if (isa<PHINode>(CondCmp->getOperand(0))) {
00348       // If we have "br (phi != 42)" and the phi node has any constant values
00349       // as operands, we can thread through this block.
00350       // 
00351       // If we have "br (cmp phi, x)" and the phi node contains x such that the
00352       // comparison uniquely identifies the branch target, we can thread
00353       // through this block.
00354 
00355       if (ProcessBranchOnCompare(CondCmp, BB))
00356         return true;      
00357     }
00358     
00359     // If we have a comparison, loop over the predecessors to see if there is
00360     // a condition with the same value.
00361     pred_iterator PI = pred_begin(BB), E = pred_end(BB);
00362     for (; PI != E; ++PI)
00363       if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator()))
00364         if (PBI->isConditional() && *PI != BB) {
00365           if (CmpInst *CI = dyn_cast<CmpInst>(PBI->getCondition())) {
00366             if (CI->getOperand(0) == CondCmp->getOperand(0) &&
00367                 CI->getOperand(1) == CondCmp->getOperand(1) &&
00368                 CI->getPredicate() == CondCmp->getPredicate()) {
00369               // TODO: Could handle things like (x != 4) --> (x == 17)
00370               if (ProcessBranchOnDuplicateCond(*PI, BB))
00371                 return true;
00372             }
00373           }
00374         }
00375   }
00376 
00377   // Check for some cases that are worth simplifying.  Right now we want to look
00378   // for loads that are used by a switch or by the condition for the branch.  If
00379   // we see one, check to see if it's partially redundant.  If so, insert a PHI
00380   // which can then be used to thread the values.
00381   //
00382   // This is particularly important because reg2mem inserts loads and stores all
00383   // over the place, and this blocks jump threading if we don't zap them.
00384   Value *SimplifyValue = CondInst;
00385   if (CmpInst *CondCmp = dyn_cast<CmpInst>(SimplifyValue))
00386     if (isa<Constant>(CondCmp->getOperand(1)))
00387       SimplifyValue = CondCmp->getOperand(0);
00388   
00389   if (LoadInst *LI = dyn_cast<LoadInst>(SimplifyValue))
00390     if (SimplifyPartiallyRedundantLoad(LI))
00391       return true;
00392   
00393   // TODO: If we have: "br (X > 0)"  and we have a predecessor where we know
00394   // "(X == 4)" thread through this block.
00395   
00396   return false;
00397 }
00398 
00399 /// ProcessBranchOnDuplicateCond - We found a block and a predecessor of that
00400 /// block that jump on exactly the same condition.  This means that we almost
00401 /// always know the direction of the edge in the DESTBB:
00402 ///  PREDBB:
00403 ///     br COND, DESTBB, BBY
00404 ///  DESTBB:
00405 ///     br COND, BBZ, BBW
00406 ///
00407 /// If DESTBB has multiple predecessors, we can't just constant fold the branch
00408 /// in DESTBB, we have to thread over it.
00409 bool JumpThreading::ProcessBranchOnDuplicateCond(BasicBlock *PredBB,
00410                                                  BasicBlock *BB) {
00411   BranchInst *PredBI = cast<BranchInst>(PredBB->getTerminator());
00412   
00413   // If both successors of PredBB go to DESTBB, we don't know anything.  We can
00414   // fold the branch to an unconditional one, which allows other recursive
00415   // simplifications.
00416   bool BranchDir;
00417   if (PredBI->getSuccessor(1) != BB)
00418     BranchDir = true;
00419   else if (PredBI->getSuccessor(0) != BB)
00420     BranchDir = false;
00421   else {
00422     DEBUG(errs() << "  In block '" << PredBB->getName()
00423           << "' folding terminator: " << *PredBB->getTerminator());
00424     ++NumFolds;
00425     ConstantFoldTerminator(PredBB);
00426     return true;
00427   }
00428    
00429   BranchInst *DestBI = cast<BranchInst>(BB->getTerminator());
00430 
00431   // If the dest block has one predecessor, just fix the branch condition to a
00432   // constant and fold it.
00433   if (BB->getSinglePredecessor()) {
00434     DEBUG(errs() << "  In block '" << BB->getName()
00435           << "' folding condition to '" << BranchDir << "': "
00436           << *BB->getTerminator());
00437     ++NumFolds;
00438     DestBI->setCondition(ConstantInt::get(Type::getInt1Ty(BB->getContext()),
00439                                           BranchDir));
00440     ConstantFoldTerminator(BB);
00441     return true;
00442   }
00443   
00444   // Otherwise we need to thread from PredBB to DestBB's successor which
00445   // involves code duplication.  Check to see if it is worth it.
00446   unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB);
00447   if (JumpThreadCost > Threshold) {
00448     DEBUG(errs() << "  Not threading BB '" << BB->getName()
00449           << "' - Cost is too high: " << JumpThreadCost << "\n");
00450     return false;
00451   }
00452   
00453   // Next, figure out which successor we are threading to.
00454   BasicBlock *SuccBB = DestBI->getSuccessor(!BranchDir);
00455   
00456   // Ok, try to thread it!
00457   return ThreadEdge(BB, PredBB, SuccBB, JumpThreadCost);
00458 }
00459 
00460 /// ProcessSwitchOnDuplicateCond - We found a block and a predecessor of that
00461 /// block that switch on exactly the same condition.  This means that we almost
00462 /// always know the direction of the edge in the DESTBB:
00463 ///  PREDBB:
00464 ///     switch COND [... DESTBB, BBY ... ]
00465 ///  DESTBB:
00466 ///     switch COND [... BBZ, BBW ]
00467 ///
00468 /// Optimizing switches like this is very important, because simplifycfg builds
00469 /// switches out of repeated 'if' conditions.
00470 bool JumpThreading::ProcessSwitchOnDuplicateCond(BasicBlock *PredBB,
00471                                                  BasicBlock *DestBB) {
00472   // Can't thread edge to self.
00473   if (PredBB == DestBB)
00474     return false;
00475   
00476   
00477   SwitchInst *PredSI = cast<SwitchInst>(PredBB->getTerminator());
00478   SwitchInst *DestSI = cast<SwitchInst>(DestBB->getTerminator());
00479 
00480   // There are a variety of optimizations that we can potentially do on these
00481   // blocks: we order them from most to least preferable.
00482   
00483   // If DESTBB *just* contains the switch, then we can forward edges from PREDBB
00484   // directly to their destination.  This does not introduce *any* code size
00485   // growth.  Skip debug info first.
00486   BasicBlock::iterator BBI = DestBB->begin();
00487   while (isa<DbgInfoIntrinsic>(BBI))
00488     BBI++;
00489   
00490   // FIXME: Thread if it just contains a PHI.
00491   if (isa<SwitchInst>(BBI)) {
00492     bool MadeChange = false;
00493     // Ignore the default edge for now.
00494     for (unsigned i = 1, e = DestSI->getNumSuccessors(); i != e; ++i) {
00495       ConstantInt *DestVal = DestSI->getCaseValue(i);
00496       BasicBlock *DestSucc = DestSI->getSuccessor(i);
00497       
00498       // Okay, DestSI has a case for 'DestVal' that goes to 'DestSucc'.  See if
00499       // PredSI has an explicit case for it.  If so, forward.  If it is covered
00500       // by the default case, we can't update PredSI.
00501       unsigned PredCase = PredSI->findCaseValue(DestVal);
00502       if (PredCase == 0) continue;
00503       
00504       // If PredSI doesn't go to DestBB on this value, then it won't reach the
00505       // case on this condition.
00506       if (PredSI->getSuccessor(PredCase) != DestBB &&
00507           DestSI->getSuccessor(i) != DestBB)
00508         continue;
00509 
00510       // Otherwise, we're safe to make the change.  Make sure that the edge from
00511       // DestSI to DestSucc is not critical and has no PHI nodes.
00512       DEBUG(errs() << "FORWARDING EDGE " << *DestVal << "   FROM: " << *PredSI);
00513       DEBUG(errs() << "THROUGH: " << *DestSI);
00514 
00515       // If the destination has PHI nodes, just split the edge for updating
00516       // simplicity.
00517       if (isa<PHINode>(DestSucc->begin()) && !DestSucc->getSinglePredecessor()){
00518         SplitCriticalEdge(DestSI, i, this);
00519         DestSucc = DestSI->getSuccessor(i);
00520       }
00521       FoldSingleEntryPHINodes(DestSucc);
00522       PredSI->setSuccessor(PredCase, DestSucc);
00523       MadeChange = true;
00524     }
00525     
00526     if (MadeChange)
00527       return true;
00528   }
00529   
00530   return false;
00531 }
00532 
00533 
00534 /// SimplifyPartiallyRedundantLoad - If LI is an obviously partially redundant
00535 /// load instruction, eliminate it by replacing it with a PHI node.  This is an
00536 /// important optimization that encourages jump threading, and needs to be run
00537 /// interlaced with other jump threading tasks.
00538 bool JumpThreading::SimplifyPartiallyRedundantLoad(LoadInst *LI) {
00539   // Don't hack volatile loads.
00540   if (LI->isVolatile()) return false;
00541   
00542   // If the load is defined in a block with exactly one predecessor, it can't be
00543   // partially redundant.
00544   BasicBlock *LoadBB = LI->getParent();
00545   if (LoadBB->getSinglePredecessor())
00546     return false;
00547   
00548   Value *LoadedPtr = LI->getOperand(0);
00549 
00550   // If the loaded operand is defined in the LoadBB, it can't be available.
00551   // FIXME: Could do PHI translation, that would be fun :)
00552   if (Instruction *PtrOp = dyn_cast<Instruction>(LoadedPtr))
00553     if (PtrOp->getParent() == LoadBB)
00554       return false;
00555   
00556   // Scan a few instructions up from the load, to see if it is obviously live at
00557   // the entry to its block.
00558   BasicBlock::iterator BBIt = LI;
00559 
00560   if (Value *AvailableVal = FindAvailableLoadedValue(LoadedPtr, LoadBB, 
00561                                                      BBIt, 6)) {
00562     // If the value if the load is locally available within the block, just use
00563     // it.  This frequently occurs for reg2mem'd allocas.
00564     //cerr << "LOAD ELIMINATED:\n" << *BBIt << *LI << "\n";
00565     
00566     // If the returned value is the load itself, replace with an undef. This can
00567     // only happen in dead loops.
00568     if (AvailableVal == LI) AvailableVal = UndefValue::get(LI->getType());
00569     LI->replaceAllUsesWith(AvailableVal);
00570     LI->eraseFromParent();
00571     return true;
00572   }
00573 
00574   // Otherwise, if we scanned the whole block and got to the top of the block,
00575   // we know the block is locally transparent to the load.  If not, something
00576   // might clobber its value.
00577   if (BBIt != LoadBB->begin())
00578     return false;
00579   
00580   
00581   SmallPtrSet<BasicBlock*, 8> PredsScanned;
00582   typedef SmallVector<std::pair<BasicBlock*, Value*>, 8> AvailablePredsTy;
00583   AvailablePredsTy AvailablePreds;
00584   BasicBlock *OneUnavailablePred = 0;
00585   
00586   // If we got here, the loaded value is transparent through to the start of the
00587   // block.  Check to see if it is available in any of the predecessor blocks.
00588   for (pred_iterator PI = pred_begin(LoadBB), PE = pred_end(LoadBB);
00589        PI != PE; ++PI) {
00590     BasicBlock *PredBB = *PI;
00591 
00592     // If we already scanned this predecessor, skip it.
00593     if (!PredsScanned.insert(PredBB))
00594       continue;
00595 
00596     // Scan the predecessor to see if the value is available in the pred.
00597     BBIt = PredBB->end();
00598     Value *PredAvailable = FindAvailableLoadedValue(LoadedPtr, PredBB, BBIt, 6);
00599     if (!PredAvailable) {
00600       OneUnavailablePred = PredBB;
00601       continue;
00602     }
00603     
00604     // If so, this load is partially redundant.  Remember this info so that we
00605     // can create a PHI node.
00606     AvailablePreds.push_back(std::make_pair(PredBB, PredAvailable));
00607   }
00608   
00609   // If the loaded value isn't available in any predecessor, it isn't partially
00610   // redundant.
00611   if (AvailablePreds.empty()) return false;
00612   
00613   // Okay, the loaded value is available in at least one (and maybe all!)
00614   // predecessors.  If the value is unavailable in more than one unique
00615   // predecessor, we want to insert a merge block for those common predecessors.
00616   // This ensures that we only have to insert one reload, thus not increasing
00617   // code size.
00618   BasicBlock *UnavailablePred = 0;
00619   
00620   // If there is exactly one predecessor where the value is unavailable, the
00621   // already computed 'OneUnavailablePred' block is it.  If it ends in an
00622   // unconditional branch, we know that it isn't a critical edge.
00623   if (PredsScanned.size() == AvailablePreds.size()+1 &&
00624       OneUnavailablePred->getTerminator()->getNumSuccessors() == 1) {
00625     UnavailablePred = OneUnavailablePred;
00626   } else if (PredsScanned.size() != AvailablePreds.size()) {
00627     // Otherwise, we had multiple unavailable predecessors or we had a critical
00628     // edge from the one.
00629     SmallVector<BasicBlock*, 8> PredsToSplit;
00630     SmallPtrSet<BasicBlock*, 8> AvailablePredSet;
00631 
00632     for (unsigned i = 0, e = AvailablePreds.size(); i != e; ++i)
00633       AvailablePredSet.insert(AvailablePreds[i].first);
00634 
00635     // Add all the unavailable predecessors to the PredsToSplit list.
00636     for (pred_iterator PI = pred_begin(LoadBB), PE = pred_end(LoadBB);
00637          PI != PE; ++PI)
00638       if (!AvailablePredSet.count(*PI))
00639         PredsToSplit.push_back(*PI);
00640     
00641     // Split them out to their own block.
00642     UnavailablePred =
00643       SplitBlockPredecessors(LoadBB, &PredsToSplit[0], PredsToSplit.size(),
00644                              "thread-split", this);
00645   }
00646   
00647   // If the value isn't available in all predecessors, then there will be
00648   // exactly one where it isn't available.  Insert a load on that edge and add
00649   // it to the AvailablePreds list.
00650   if (UnavailablePred) {
00651     assert(UnavailablePred->getTerminator()->getNumSuccessors() == 1 &&
00652            "Can't handle critical edge here!");
00653     Value *NewVal = new LoadInst(LoadedPtr, LI->getName()+".pr",
00654                                  UnavailablePred->getTerminator());
00655     AvailablePreds.push_back(std::make_pair(UnavailablePred, NewVal));
00656   }
00657   
00658   // Now we know that each predecessor of this block has a value in
00659   // AvailablePreds, sort them for efficient access as we're walking the preds.
00660   array_pod_sort(AvailablePreds.begin(), AvailablePreds.end());
00661   
00662   // Create a PHI node at the start of the block for the PRE'd load value.
00663   PHINode *PN = PHINode::Create(LI->getType(), "", LoadBB->begin());
00664   PN->takeName(LI);
00665   
00666   // Insert new entries into the PHI for each predecessor.  A single block may
00667   // have multiple entries here.
00668   for (pred_iterator PI = pred_begin(LoadBB), E = pred_end(LoadBB); PI != E;
00669        ++PI) {
00670     AvailablePredsTy::iterator I = 
00671       std::lower_bound(AvailablePreds.begin(), AvailablePreds.end(),
00672                        std::make_pair(*PI, (Value*)0));
00673     
00674     assert(I != AvailablePreds.end() && I->first == *PI &&
00675            "Didn't find entry for predecessor!");
00676     
00677     PN->addIncoming(I->second, I->first);
00678   }
00679   
00680   //cerr << "PRE: " << *LI << *PN << "\n";
00681   
00682   LI->replaceAllUsesWith(PN);
00683   LI->eraseFromParent();
00684   
00685   return true;
00686 }
00687 
00688 
00689 /// ProcessJumpOnPHI - We have a conditional branch of switch on a PHI node in
00690 /// the current block.  See if there are any simplifications we can do based on
00691 /// inputs to the phi node.
00692 /// 
00693 bool JumpThreading::ProcessJumpOnPHI(PHINode *PN) {
00694   // See if the phi node has any constant values.  If so, we can determine where
00695   // the corresponding predecessor will branch.
00696   ConstantInt *PredCst = 0;
00697   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
00698     if ((PredCst = dyn_cast<ConstantInt>(PN->getIncomingValue(i))))
00699       break;
00700   
00701   // If no incoming value has a constant, we don't know the destination of any
00702   // predecessors.
00703   if (PredCst == 0)
00704     return false;
00705   
00706   // See if the cost of duplicating this block is low enough.
00707   BasicBlock *BB = PN->getParent();
00708   unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB);
00709   if (JumpThreadCost > Threshold) {
00710     DEBUG(errs() << "  Not threading BB '" << BB->getName()
00711           << "' - Cost is too high: " << JumpThreadCost << "\n");
00712     return false;
00713   }
00714   
00715   // If so, we can actually do this threading.  Merge any common predecessors
00716   // that will act the same.
00717   BasicBlock *PredBB = FactorCommonPHIPreds(PN, PredCst);
00718   
00719   // Next, figure out which successor we are threading to.
00720   BasicBlock *SuccBB;
00721   if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()))
00722     SuccBB = BI->getSuccessor(PredCst ==
00723                                    ConstantInt::getFalse(PredBB->getContext()));
00724   else {
00725     SwitchInst *SI = cast<SwitchInst>(BB->getTerminator());
00726     SuccBB = SI->getSuccessor(SI->findCaseValue(PredCst));
00727   }
00728   
00729   // Ok, try to thread it!
00730   return ThreadEdge(BB, PredBB, SuccBB, JumpThreadCost);
00731 }
00732 
00733 /// ProcessJumpOnLogicalPHI - PN's basic block contains a conditional branch
00734 /// whose condition is an AND/OR where one side is PN.  If PN has constant
00735 /// operands that permit us to evaluate the condition for some operand, thread
00736 /// through the block.  For example with:
00737 ///   br (and X, phi(Y, Z, false))
00738 /// the predecessor corresponding to the 'false' will always jump to the false
00739 /// destination of the branch.
00740 ///
00741 bool JumpThreading::ProcessBranchOnLogical(Value *V, BasicBlock *BB,
00742                                            bool isAnd) {
00743   // If this is a binary operator tree of the same AND/OR opcode, check the
00744   // LHS/RHS.
00745   if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V))
00746     if ((isAnd && BO->getOpcode() == Instruction::And) ||
00747         (!isAnd && BO->getOpcode() == Instruction::Or)) {
00748       if (ProcessBranchOnLogical(BO->getOperand(0), BB, isAnd))
00749         return true;
00750       if (ProcessBranchOnLogical(BO->getOperand(1), BB, isAnd))
00751         return true;
00752     }
00753       
00754   // If this isn't a PHI node, we can't handle it.
00755   PHINode *PN = dyn_cast<PHINode>(V);
00756   if (!PN || PN->getParent() != BB) return false;
00757                                              
00758   // We can only do the simplification for phi nodes of 'false' with AND or
00759   // 'true' with OR.  See if we have any entries in the phi for this.
00760   unsigned PredNo = ~0U;
00761   ConstantInt *PredCst = ConstantInt::get(Type::getInt1Ty(BB->getContext()),
00762                                           !isAnd);
00763   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
00764     if (PN->getIncomingValue(i) == PredCst) {
00765       PredNo = i;
00766       break;
00767     }
00768   }
00769   
00770   // If no match, bail out.
00771   if (PredNo == ~0U)
00772     return false;
00773   
00774   // See if the cost of duplicating this block is low enough.
00775   unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB);
00776   if (JumpThreadCost > Threshold) {
00777     DEBUG(errs() << "  Not threading BB '" << BB->getName()
00778           << "' - Cost is too high: " << JumpThreadCost << "\n");
00779     return false;
00780   }
00781 
00782   // If so, we can actually do this threading.  Merge any common predecessors
00783   // that will act the same.
00784   BasicBlock *PredBB = FactorCommonPHIPreds(PN, PredCst);
00785   
00786   // Next, figure out which successor we are threading to.  If this was an AND,
00787   // the constant must be FALSE, and we must be targeting the 'false' block.
00788   // If this is an OR, the constant must be TRUE, and we must be targeting the
00789   // 'true' block.
00790   BasicBlock *SuccBB = BB->getTerminator()->getSuccessor(isAnd);
00791   
00792   // Ok, try to thread it!
00793   return ThreadEdge(BB, PredBB, SuccBB, JumpThreadCost);
00794 }
00795 
00796 /// GetResultOfComparison - Given an icmp/fcmp predicate and the left and right
00797 /// hand sides of the compare instruction, try to determine the result. If the
00798 /// result can not be determined, a null pointer is returned.
00799 static Constant *GetResultOfComparison(CmpInst::Predicate pred,
00800                                        Value *LHS, Value *RHS,
00801                                        LLVMContext &Context) {
00802   if (Constant *CLHS = dyn_cast<Constant>(LHS))
00803     if (Constant *CRHS = dyn_cast<Constant>(RHS))
00804       return ConstantExpr::getCompare(pred, CLHS, CRHS);
00805 
00806   if (LHS == RHS)
00807     if (isa<IntegerType>(LHS->getType()) || isa<PointerType>(LHS->getType()))
00808       return ICmpInst::isTrueWhenEqual(pred) ? 
00809                  ConstantInt::getTrue(Context) : ConstantInt::getFalse(Context);
00810 
00811   return 0;
00812 }
00813 
00814 /// ProcessBranchOnCompare - We found a branch on a comparison between a phi
00815 /// node and a value.  If we can identify when the comparison is true between
00816 /// the phi inputs and the value, we can fold the compare for that edge and
00817 /// thread through it.
00818 bool JumpThreading::ProcessBranchOnCompare(CmpInst *Cmp, BasicBlock *BB) {
00819   PHINode *PN = cast<PHINode>(Cmp->getOperand(0));
00820   Value *RHS = Cmp->getOperand(1);
00821   
00822   // If the phi isn't in the current block, an incoming edge to this block
00823   // doesn't control the destination.
00824   if (PN->getParent() != BB)
00825     return false;
00826   
00827   // We can do this simplification if any comparisons fold to true or false.
00828   // See if any do.
00829   Value *PredVal = 0;
00830   bool TrueDirection = false;
00831   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
00832     PredVal = PN->getIncomingValue(i);
00833     
00834     Constant *Res = GetResultOfComparison(Cmp->getPredicate(), PredVal,
00835                                           RHS, Cmp->getContext());
00836     if (!Res) {
00837       PredVal = 0;
00838       continue;
00839     }
00840     
00841     // If this folded to a constant expr, we can't do anything.
00842     if (ConstantInt *ResC = dyn_cast<ConstantInt>(Res)) {
00843       TrueDirection = ResC->getZExtValue();
00844       break;
00845     }
00846     // If this folded to undef, just go the false way.
00847     if (isa<UndefValue>(Res)) {
00848       TrueDirection = false;
00849       break;
00850     }
00851     
00852     // Otherwise, we can't fold this input.
00853     PredVal = 0;
00854   }
00855   
00856   // If no match, bail out.
00857   if (PredVal == 0)
00858     return false;
00859   
00860   // See if the cost of duplicating this block is low enough.
00861   unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB);
00862   if (JumpThreadCost > Threshold) {
00863     DEBUG(errs() << "  Not threading BB '" << BB->getName()
00864           << "' - Cost is too high: " << JumpThreadCost << "\n");
00865     return false;
00866   }
00867   
00868   // If so, we can actually do this threading.  Merge any common predecessors
00869   // that will act the same.
00870   BasicBlock *PredBB = FactorCommonPHIPreds(PN, PredVal);
00871   
00872   // Next, get our successor.
00873   BasicBlock *SuccBB = BB->getTerminator()->getSuccessor(!TrueDirection);
00874   
00875   // Ok, try to thread it!
00876   return ThreadEdge(BB, PredBB, SuccBB, JumpThreadCost);
00877 }
00878 
00879 
00880 /// ThreadEdge - We have decided that it is safe and profitable to thread an
00881 /// edge from PredBB to SuccBB across BB.  Transform the IR to reflect this
00882 /// change.
00883 bool JumpThreading::ThreadEdge(BasicBlock *BB, BasicBlock *PredBB, 
00884                                BasicBlock *SuccBB, unsigned JumpThreadCost) {
00885 
00886   // If threading to the same block as we come from, we would infinite loop.
00887   if (SuccBB == BB) {
00888     DEBUG(errs() << "  Not threading across BB '" << BB->getName()
00889           << "' - would thread to self!\n");
00890     return false;
00891   }
00892   
00893   // If threading this would thread across a loop header, don't thread the edge.
00894   // See the comments above FindLoopHeaders for justifications and caveats.
00895   if (LoopHeaders.count(BB)) {
00896     DEBUG(errs() << "  Not threading from '" << PredBB->getName()
00897           << "' across loop header BB '" << BB->getName()
00898           << "' to dest BB '" << SuccBB->getName()
00899           << "' - it might create an irreducible loop!\n");
00900     return false;
00901   }
00902 
00903   // And finally, do it!
00904   DEBUG(errs() << "  Threading edge from '" << PredBB->getName() << "' to '"
00905         << SuccBB->getName() << "' with cost: " << JumpThreadCost
00906         << ", across block:\n    "
00907         << *BB << "\n");
00908   
00909   // Jump Threading can not update SSA properties correctly if the values
00910   // defined in the duplicated block are used outside of the block itself.  For
00911   // this reason, we spill all values that are used outside of BB to the stack.
00912   for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) {
00913     if (!I->isUsedOutsideOfBlock(BB))
00914       continue;
00915     
00916     // We found a use of I outside of BB.  Create a new stack slot to
00917     // break this inter-block usage pattern.
00918     DemoteRegToStack(*I);
00919   }
00920  
00921   // We are going to have to map operands from the original BB block to the new
00922   // copy of the block 'NewBB'.  If there are PHI nodes in BB, evaluate them to
00923   // account for entry from PredBB.
00924   DenseMap<Instruction*, Value*> ValueMapping;
00925   
00926   BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), 
00927                                          BB->getName()+".thread", 
00928                                          BB->getParent(), BB);
00929   NewBB->moveAfter(PredBB);
00930   
00931   BasicBlock::iterator BI = BB->begin();
00932   for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
00933     ValueMapping[PN] = PN->getIncomingValueForBlock(PredBB);
00934   
00935   // Clone the non-phi instructions of BB into NewBB, keeping track of the
00936   // mapping and using it to remap operands in the cloned instructions.
00937   for (; !isa<TerminatorInst>(BI); ++BI) {
00938     Instruction *New = BI->clone(BI->getContext());
00939     New->setName(BI->getName());
00940     NewBB->getInstList().push_back(New);
00941     ValueMapping[BI] = New;
00942    
00943     // Remap operands to patch up intra-block references.
00944     for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
00945       if (Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) {
00946         DenseMap<Instruction*, Value*>::iterator I = ValueMapping.find(Inst);
00947         if (I != ValueMapping.end())
00948           New->setOperand(i, I->second);
00949       }
00950   }
00951   
00952   // We didn't copy the terminator from BB over to NewBB, because there is now
00953   // an unconditional jump to SuccBB.  Insert the unconditional jump.
00954   BranchInst::Create(SuccBB, NewBB);
00955   
00956   // Check to see if SuccBB has PHI nodes. If so, we need to add entries to the
00957   // PHI nodes for NewBB now.
00958   for (BasicBlock::iterator PNI = SuccBB->begin(); isa<PHINode>(PNI); ++PNI) {
00959     PHINode *PN = cast<PHINode>(PNI);
00960     // Ok, we have a PHI node.  Figure out what the incoming value was for the
00961     // DestBlock.
00962     Value *IV = PN->getIncomingValueForBlock(BB);
00963     
00964     // Remap the value if necessary.
00965     if (Instruction *Inst = dyn_cast<Instruction>(IV)) {
00966       DenseMap<Instruction*, Value*>::iterator I = ValueMapping.find(Inst);
00967       if (I != ValueMapping.end())
00968         IV = I->second;
00969     }
00970     PN->addIncoming(IV, NewBB);
00971   }
00972   
00973   // Ok, NewBB is good to go.  Update the terminator of PredBB to jump to
00974   // NewBB instead of BB.  This eliminates predecessors from BB, which requires
00975   // us to simplify any PHI nodes in BB.
00976   TerminatorInst *PredTerm = PredBB->getTerminator();
00977   for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i)
00978     if (PredTerm->getSuccessor(i) == BB) {
00979       BB->removePredecessor(PredBB);
00980       PredTerm->setSuccessor(i, NewBB);
00981     }
00982   
00983   // At this point, the IR is fully up to date and consistent.  Do a quick scan
00984   // over the new instructions and zap any that are constants or dead.  This
00985   // frequently happens because of phi translation.
00986   BI = NewBB->begin();
00987   for (BasicBlock::iterator E = NewBB->end(); BI != E; ) {
00988     Instruction *Inst = BI++;
00989     if (Constant *C = ConstantFoldInstruction(Inst, BB->getContext(), TD)) {
00990       Inst->replaceAllUsesWith(C);
00991       Inst->eraseFromParent();
00992       continue;
00993     }
00994     
00995     RecursivelyDeleteTriviallyDeadInstructions(Inst);
00996   }
00997   
00998   // Threaded an edge!
00999   ++NumThreads;
01000   return true;
01001 }