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