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 struct APIntUnsignedOrdering {
 411   bool operator()(const APInt &LHS, const APInt &RHS) const {
 412     return LHS.ult(RHS);
 413   }
 414 };
 415
 416 /// ProcessSwitchOnDuplicateCond - We found a block and a predecessor of that
 417 /// block that switch on exactly the same condition.  This means that we almost
 418 /// always know the direction of the edge in the DESTBB:
 419 ///  PREDBB:
 420 ///     switch COND [... DESTBB, BBY ... ]
 421 ///  DESTBB:
 422 ///     switch COND [... BBZ, BBW ]
 423 ///
 424 /// Optimizing switches like this is very important, because simplifycfg builds
 425 /// switches out of repeated 'if' conditions.
 426 bool JumpThreading::ProcessSwitchOnDuplicateCond(BasicBlock *PredBB,
 427                                                  BasicBlock *DestBB) {
 428   // Can't thread edge to self.
 429   if (PredBB == DestBB)
 430     return false;
 431
 432
 433   SwitchInst *PredSI = cast<SwitchInst>(PredBB->getTerminator());
 434   SwitchInst *DestSI = cast<SwitchInst>(DestBB->getTerminator());
 435
 436   // There are a variety of optimizations that we can potentially do on these
 437   // blocks: we order them from most to least preferable.
 438
 439   // If DESTBB *just* contains the switch, then we can forward edges from PREDBB
 440   // directly to their destination.  This does not introduce *any* code size
 441   // growth.
 442
 443   // FIXME: Thread if it just contains a PHI.
 444   if (isa<SwitchInst>(DestBB->begin())) {
 445     bool MadeChange = false;
 446     // Ignore the default edge for now.
 447     for (unsigned i = 1, e = DestSI->getNumSuccessors(); i != e; ++i) {
 448       ConstantInt *DestVal = DestSI->getCaseValue(i);
 449       BasicBlock *DestSucc = DestSI->getSuccessor(i);
 450
 451       // Okay, DestSI has a case for 'DestVal' that goes to 'DestSucc'.  See if
 452       // PredSI has an explicit case for it.  If so, forward.  If it is covered
 453       // by the default case, we can't update PredSI.
 454       unsigned PredCase = PredSI->findCaseValue(DestVal);
 455       if (PredCase == 0) continue;
 456
 457       // If PredSI doesn't go to DestBB on this value, then it won't reach the
 458       // case on this condition.
 459       if (PredSI->getSuccessor(PredCase) != DestBB &&
 460           DestSI->getSuccessor(i) != DestBB)
 461         continue;
 462
 463       // Otherwise, we're safe to make the change.  Make sure that the edge from
 464       // DestSI to DestSucc is not critical and has no PHI nodes.
 465       DOUT << "FORWARDING EDGE " << *DestVal << "   FROM: " << *PredSI;
 466       DOUT << "THROUGH: " << *DestSI;
 467
 468       // If the destination has PHI nodes, just split the edge for updating
 469       // simplicity.
 470       if (isa<PHINode>(DestSucc->begin()) && !DestSucc->getSinglePredecessor()){
 471         SplitCriticalEdge(DestSI, i, this);
 472         DestSucc = DestSI->getSuccessor(i);
 473       }
 474       FoldSingleEntryPHINodes(DestSucc);
 475       PredSI->setSuccessor(PredCase, DestSucc);
 476       MadeChange = true;
 477     }
 478
 479     if (MadeChange)
 480       return true;
 481   }
 482
 483 #if 0
 484   // Figure out on which of the condition allow us to get to DESTBB.  If DESTBB
 485   // is the default label, we compute the set of values COND is known not to be
 486   // otherwise we compute the set of options that COND could be.
 487   SmallVector<APInt, 16> KnownValues;
 488   bool DestBBIsDefault = PredSI->getSuccessor(0) == DestBB;
 489
 490   if (DestBBIsDefault) {
 491     // DestBB the default case.  Collect the values where PredBB can't branch to
 492     // DestBB.
 493     for (unsigned i = 1/*skip default*/, e = PredSI->getNumCases(); i != e; ++i)
 494       if (PredSI->getSuccessor(i) != DestBB)
 495         KnownValues.push_back(PredSI->getCaseValue(i)->getValue());
 496   } else {
 497     // Not the default case.  Collect the values where PredBB can branch to
 498     // DestBB.
 499     for (unsigned i = 1/*skip default*/, e = PredSI->getNumCases(); i != e; ++i)
 500       if (PredSI->getSuccessor(i) == DestBB)
 501         KnownValues.push_back(PredSI->getCaseValue(i)->getValue());
 502   }
 503
 504   std::sort(KnownValues.begin(), KnownValues.end(), APIntUnsignedOrdering());
 505   return false;
 506   cerr << "\nFOUND THREAD BLOCKS:\n";
 507   PredBB->dump();
 508   DestBB->dump();
 509 #endif
 510
 511   return false;
 512 }
 513
 514
 515 /// SimplifyPartiallyRedundantLoad - If LI is an obviously partially redundant
 516 /// load instruction, eliminate it by replacing it with a PHI node.  This is an
 517 /// important optimization that encourages jump threading, and needs to be run
 518 /// interlaced with other jump threading tasks.
 519 bool JumpThreading::SimplifyPartiallyRedundantLoad(LoadInst *LI) {
 520   // Don't hack volatile loads.
 521   if (LI->isVolatile()) return false;
 522
 523   // If the load is defined in a block with exactly one predecessor, it can't be
 524   // partially redundant.
 525   BasicBlock *LoadBB = LI->getParent();
 526   if (LoadBB->getSinglePredecessor())
 527     return false;
 528
 529   Value *LoadedPtr = LI->getOperand(0);
 530
 531   // If the loaded operand is defined in the LoadBB, it can't be available.
 532   // FIXME: Could do PHI translation, that would be fun :)
 533   if (Instruction *PtrOp = dyn_cast<Instruction>(LoadedPtr))
 534     if (PtrOp->getParent() == LoadBB)
 535       return false;
 536
 537   // Scan a few instructions up from the load, to see if it is obviously live at
 538   // the entry to its block.
 539   BasicBlock::iterator BBIt = LI;
 540
 541   if (Value *AvailableVal = FindAvailableLoadedValue(LoadedPtr, LoadBB,
 542                                                      BBIt, 6)) {
 543     // If the value if the load is locally available within the block, just use
 544     // it.  This frequently occurs for reg2mem'd allocas.
 545     //cerr << "LOAD ELIMINATED:\n" << *BBIt << *LI << "\n";
 546
 547     // If the returned value is the load itself, replace with an undef. This can
 548     // only happen in dead loops.
 549     if (AvailableVal == LI) AvailableVal = UndefValue::get(LI->getType());
 550     LI->replaceAllUsesWith(AvailableVal);
 551     LI->eraseFromParent();
 552     return true;
 553   }
 554
 555   // Otherwise, if we scanned the whole block and got to the top of the block,
 556   // we know the block is locally transparent to the load.  If not, something
 557   // might clobber its value.
 558   if (BBIt != LoadBB->begin())
 559     return false;
 560
 561
 562   SmallPtrSet<BasicBlock*, 8> PredsScanned;
 563   typedef SmallVector<std::pair<BasicBlock*, Value*>, 8> AvailablePredsTy;
 564   AvailablePredsTy AvailablePreds;
 565   BasicBlock *OneUnavailablePred = 0;
 566
 567   // If we got here, the loaded value is transparent through to the start of the
 568   // block.  Check to see if it is available in any of the predecessor blocks.
 569   for (pred_iterator PI = pred_begin(LoadBB), PE = pred_end(LoadBB);
 570        PI != PE; ++PI) {
 571     BasicBlock *PredBB = *PI;
 572
 573     // If we already scanned this predecessor, skip it.
 574     if (!PredsScanned.insert(PredBB))
 575       continue;
 576
 577     // Scan the predecessor to see if the value is available in the pred.
 578     BBIt = PredBB->end();
 579     Value *PredAvailable = FindAvailableLoadedValue(LoadedPtr, PredBB, BBIt, 6);
 580     if (!PredAvailable) {
 581       OneUnavailablePred = PredBB;
 582       continue;
 583     }
 584
 585     // If so, this load is partially redundant.  Remember this info so that we
 586     // can create a PHI node.
 587     AvailablePreds.push_back(std::make_pair(PredBB, PredAvailable));
 588   }
 589
 590   // If the loaded value isn't available in any predecessor, it isn't partially
 591   // redundant.
 592   if (AvailablePreds.empty()) return false;
 593
 594   // Okay, the loaded value is available in at least one (and maybe all!)
 595   // predecessors.  If the value is unavailable in more than one unique
 596   // predecessor, we want to insert a merge block for those common predecessors.
 597   // This ensures that we only have to insert one reload, thus not increasing
 598   // code size.
 599   BasicBlock *UnavailablePred = 0;
 600
 601   // If there is exactly one predecessor where the value is unavailable, the
 602   // already computed 'OneUnavailablePred' block is it.  If it ends in an
 603   // unconditional branch, we know that it isn't a critical edge.
 604   if (PredsScanned.size() == AvailablePreds.size()+1 &&
 605       OneUnavailablePred->getTerminator()->getNumSuccessors() == 1) {
 606     UnavailablePred = OneUnavailablePred;
 607   } else if (PredsScanned.size() != AvailablePreds.size()) {
 608     // Otherwise, we had multiple unavailable predecessors or we had a critical
 609     // edge from the one.
 610     SmallVector<BasicBlock*, 8> PredsToSplit;
 611     SmallPtrSet<BasicBlock*, 8> AvailablePredSet;
 612
 613     for (unsigned i = 0, e = AvailablePreds.size(); i != e; ++i)
 614       AvailablePredSet.insert(AvailablePreds[i].first);
 615
 616     // Add all the unavailable predecessors to the PredsToSplit list.
 617     for (pred_iterator PI = pred_begin(LoadBB), PE = pred_end(LoadBB);
 618          PI != PE; ++PI)
 619       if (!AvailablePredSet.count(*PI))
 620         PredsToSplit.push_back(*PI);
 621
 622     // Split them out to their own block.
 623     UnavailablePred =
 624       SplitBlockPredecessors(LoadBB, &PredsToSplit[0], PredsToSplit.size(),
 625                              "thread-split", this);
 626   }
 627
 628   // If the value isn't available in all predecessors, then there will be
 629   // exactly one where it isn't available.  Insert a load on that edge and add
 630   // it to the AvailablePreds list.
 631   if (UnavailablePred) {
 632     assert(UnavailablePred->getTerminator()->getNumSuccessors() == 1 &&
 633            "Can't handle critical edge here!");
 634     Value *NewVal = new LoadInst(LoadedPtr, LI->getName()+".pr",
 635                                  UnavailablePred->getTerminator());
 636     AvailablePreds.push_back(std::make_pair(UnavailablePred, NewVal));
 637   }
 638
 639   // Now we know that each predecessor of this block has a value in
 640   // AvailablePreds, sort them for efficient access as we're walking the preds.
 641   array_pod_sort(AvailablePreds.begin(), AvailablePreds.end());
 642
 643   // Create a PHI node at the start of the block for the PRE'd load value.
 644   PHINode *PN = PHINode::Create(LI->getType(), "", LoadBB->begin());
 645   PN->takeName(LI);
 646
 647   // Insert new entries into the PHI for each predecessor.  A single block may
 648   // have multiple entries here.
 649   for (pred_iterator PI = pred_begin(LoadBB), E = pred_end(LoadBB); PI != E;
 650        ++PI) {
 651     AvailablePredsTy::iterator I =
 652       std::lower_bound(AvailablePreds.begin(), AvailablePreds.end(),
 653                        std::make_pair(*PI, (Value*)0));
 654
 655     assert(I != AvailablePreds.end() && I->first == *PI &&
 656            "Didn't find entry for predecessor!");
 657
 658     PN->addIncoming(I->second, I->first);
 659   }
 660
 661   //cerr << "PRE: " << *LI << *PN << "\n";
 662
 663   LI->replaceAllUsesWith(PN);
 664   LI->eraseFromParent();
 665
 666   return true;
 667 }
 668
 669
 670 /// ProcessJumpOnPHI - We have a conditional branch of switch on a PHI node in
 671 /// the current block.  See if there are any simplifications we can do based on
 672 /// inputs to the phi node.
 673 ///
 674 bool JumpThreading::ProcessJumpOnPHI(PHINode *PN) {
 675   // See if the phi node has any constant values.  If so, we can determine where
 676   // the corresponding predecessor will branch.
 677   ConstantInt *PredCst = 0;
 678   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
 679     if ((PredCst = dyn_cast<ConstantInt>(PN->getIncomingValue(i))))
 680       break;
 681
 682   // If no incoming value has a constant, we don't know the destination of any
 683   // predecessors.
 684   if (PredCst == 0)
 685     return false;
 686
 687   // See if the cost of duplicating this block is low enough.
 688   BasicBlock *BB = PN->getParent();
 689   unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB);
 690   if (JumpThreadCost > Threshold) {
 691     DOUT << "  Not threading BB '" << BB->getNameStart()
 692          << "' - Cost is too high: " << JumpThreadCost << "\n";
 693     return false;
 694   }
 695
 696   // If so, we can actually do this threading.  Merge any common predecessors
 697   // that will act the same.
 698   BasicBlock *PredBB = FactorCommonPHIPreds(PN, PredCst);
 699
 700   // Next, figure out which successor we are threading to.
 701   BasicBlock *SuccBB;
 702   if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()))
 703     SuccBB = BI->getSuccessor(PredCst == ConstantInt::getFalse());
 704   else {
 705     SwitchInst *SI = cast<SwitchInst>(BB->getTerminator());
 706     SuccBB = SI->getSuccessor(SI->findCaseValue(PredCst));
 707   }
 708
 709   // If threading to the same block as we come from, we would infinite loop.
 710   if (SuccBB == BB) {
 711     DOUT << "  Not threading BB '" << BB->getNameStart()
 712          << "' - would thread to self!\n";
 713     return false;
 714   }
 715
 716   // And finally, do it!
 717   DOUT << "  Threading edge from '" << PredBB->getNameStart() << "' to '"
 718        << SuccBB->getNameStart() << "' with cost: " << JumpThreadCost
 719        << ", across block:\n    "
 720        << *BB << "\n";
 721
 722   ThreadEdge(BB, PredBB, SuccBB);
 723   ++NumThreads;
 724   return true;
 725 }
 726
 727 /// ProcessJumpOnLogicalPHI - PN's basic block contains a conditional branch
 728 /// whose condition is an AND/OR where one side is PN.  If PN has constant
 729 /// operands that permit us to evaluate the condition for some operand, thread
 730 /// through the block.  For example with:
 731 ///   br (and X, phi(Y, Z, false))
 732 /// the predecessor corresponding to the 'false' will always jump to the false
 733 /// destination of the branch.
 734 ///
 735 bool JumpThreading::ProcessBranchOnLogical(Value *V, BasicBlock *BB,
 736                                            bool isAnd) {
 737   // If this is a binary operator tree of the same AND/OR opcode, check the
 738   // LHS/RHS.
 739   if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V))
 740     if ((isAnd && BO->getOpcode() == Instruction::And) ||
 741         (!isAnd && BO->getOpcode() == Instruction::Or)) {
 742       if (ProcessBranchOnLogical(BO->getOperand(0), BB, isAnd))
 743         return true;
 744       if (ProcessBranchOnLogical(BO->getOperand(1), BB, isAnd))
 745         return true;
 746     }
 747
 748   // If this isn't a PHI node, we can't handle it.
 749   PHINode *PN = dyn_cast<PHINode>(V);
 750   if (!PN || PN->getParent() != BB) return false;
 751
 752   // We can only do the simplification for phi nodes of 'false' with AND or
 753   // 'true' with OR.  See if we have any entries in the phi for this.
 754   unsigned PredNo = ~0U;
 755   ConstantInt *PredCst = ConstantInt::get(Type::Int1Ty, !isAnd);
 756   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 757     if (PN->getIncomingValue(i) == PredCst) {
 758       PredNo = i;
 759       break;
 760     }
 761   }
 762
 763   // If no match, bail out.
 764   if (PredNo == ~0U)
 765     return false;
 766
 767   // See if the cost of duplicating this block is low enough.
 768   unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB);
 769   if (JumpThreadCost > Threshold) {
 770     DOUT << "  Not threading BB '" << BB->getNameStart()
 771          << "' - Cost is too high: " << JumpThreadCost << "\n";
 772     return false;
 773   }
 774
 775   // If so, we can actually do this threading.  Merge any common predecessors
 776   // that will act the same.
 777   BasicBlock *PredBB = FactorCommonPHIPreds(PN, PredCst);
 778
 779   // Next, figure out which successor we are threading to.  If this was an AND,
 780   // the constant must be FALSE, and we must be targeting the 'false' block.
 781   // If this is an OR, the constant must be TRUE, and we must be targeting the
 782   // 'true' block.
 783   BasicBlock *SuccBB = BB->getTerminator()->getSuccessor(isAnd);
 784
 785   // If threading to the same block as we come from, we would infinite loop.
 786   if (SuccBB == BB) {
 787     DOUT << "  Not threading BB '" << BB->getNameStart()
 788     << "' - would thread to self!\n";
 789     return false;
 790   }
 791
 792   // And finally, do it!
 793   DOUT << "  Threading edge through bool from '" << PredBB->getNameStart()
 794        << "' to '" << SuccBB->getNameStart() << "' with cost: "
 795        << JumpThreadCost << ", across block:\n    "
 796        << *BB << "\n";
 797
 798   ThreadEdge(BB, PredBB, SuccBB);
 799   ++NumThreads;
 800   return true;
 801 }
 802
 803 /// ProcessBranchOnCompare - We found a branch on a comparison between a phi
 804 /// node and a constant.  If the PHI node contains any constants as inputs, we
 805 /// can fold the compare for that edge and thread through it.
 806 bool JumpThreading::ProcessBranchOnCompare(CmpInst *Cmp, BasicBlock *BB) {
 807   PHINode *PN = cast<PHINode>(Cmp->getOperand(0));
 808   Constant *RHS = cast<Constant>(Cmp->getOperand(1));
 809
 810   // If the phi isn't in the current block, an incoming edge to this block
 811   // doesn't control the destination.
 812   if (PN->getParent() != BB)
 813     return false;
 814
 815   // We can do this simplification if any comparisons fold to true or false.
 816   // See if any do.
 817   Constant *PredCst = 0;
 818   bool TrueDirection = false;
 819   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 820     PredCst = dyn_cast<Constant>(PN->getIncomingValue(i));
 821     if (PredCst == 0) continue;
 822
 823     Constant *Res;
 824     if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cmp))
 825       Res = ConstantExpr::getICmp(ICI->getPredicate(), PredCst, RHS);
 826     else
 827       Res = ConstantExpr::getFCmp(cast<FCmpInst>(Cmp)->getPredicate(),
 828                                   PredCst, RHS);
 829     // If this folded to a constant expr, we can't do anything.
 830     if (ConstantInt *ResC = dyn_cast<ConstantInt>(Res)) {
 831       TrueDirection = ResC->getZExtValue();
 832       break;
 833     }
 834     // If this folded to undef, just go the false way.
 835     if (isa<UndefValue>(Res)) {
 836       TrueDirection = false;
 837       break;
 838     }
 839
 840     // Otherwise, we can't fold this input.
 841     PredCst = 0;
 842   }
 843
 844   // If no match, bail out.
 845   if (PredCst == 0)
 846     return false;
 847
 848   // See if the cost of duplicating this block is low enough.
 849   unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB);
 850   if (JumpThreadCost > Threshold) {
 851     DOUT << "  Not threading BB '" << BB->getNameStart()
 852          << "' - Cost is too high: " << JumpThreadCost << "\n";
 853     return false;
 854   }
 855
 856   // If so, we can actually do this threading.  Merge any common predecessors
 857   // that will act the same.
 858   BasicBlock *PredBB = FactorCommonPHIPreds(PN, PredCst);
 859
 860   // Next, get our successor.
 861   BasicBlock *SuccBB = BB->getTerminator()->getSuccessor(!TrueDirection);
 862
 863   // If threading to the same block as we come from, we would infinite loop.
 864   if (SuccBB == BB) {
 865     DOUT << "  Not threading BB '" << BB->getNameStart()
 866     << "' - would thread to self!\n";
 867     return false;
 868   }
 869
 870
 871   // And finally, do it!
 872   DOUT << "  Threading edge through bool from '" << PredBB->getNameStart()
 873        << "' to '" << SuccBB->getNameStart() << "' with cost: "
 874        << JumpThreadCost << ", across block:\n    "
 875        << *BB << "\n";
 876
 877   ThreadEdge(BB, PredBB, SuccBB);
 878   ++NumThreads;
 879   return true;
 880 }
 881
 882
 883 /// ThreadEdge - We have decided that it is safe and profitable to thread an
 884 /// edge from PredBB to SuccBB across BB.  Transform the IR to reflect this
 885 /// change.
 886 void JumpThreading::ThreadEdge(BasicBlock *BB, BasicBlock *PredBB,
 887                                BasicBlock *SuccBB) {
 888
 889   // Jump Threading can not update SSA properties correctly if the values
 890   // defined in the duplicated block are used outside of the block itself.  For
 891   // this reason, we spill all values that are used outside of BB to the stack.
 892   for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) {
 893     if (!I->isUsedOutsideOfBlock(BB))
 894       continue;
 895
 896     // We found a use of I outside of BB.  Create a new stack slot to
 897     // break this inter-block usage pattern.
 898     DemoteRegToStack(*I);
 899   }
 900
 901   // We are going to have to map operands from the original BB block to the new
 902   // copy of the block 'NewBB'.  If there are PHI nodes in BB, evaluate them to
 903   // account for entry from PredBB.
 904   DenseMap<Instruction*, Value*> ValueMapping;
 905
 906   BasicBlock *NewBB =
 907     BasicBlock::Create(BB->getName()+".thread", BB->getParent(), BB);
 908   NewBB->moveAfter(PredBB);
 909
 910   BasicBlock::iterator BI = BB->begin();
 911   for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
 912     ValueMapping[PN] = PN->getIncomingValueForBlock(PredBB);
 913
 914   // Clone the non-phi instructions of BB into NewBB, keeping track of the
 915   // mapping and using it to remap operands in the cloned instructions.
 916   for (; !isa<TerminatorInst>(BI); ++BI) {
 917     Instruction *New = BI->clone();
 918     New->setName(BI->getNameStart());
 919     NewBB->getInstList().push_back(New);
 920     ValueMapping[BI] = New;
 921
 922     // Remap operands to patch up intra-block references.
 923     for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
 924       if (Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i)))
 925         if (Value *Remapped = ValueMapping[Inst])
 926           New->setOperand(i, Remapped);
 927   }
 928
 929   // We didn't copy the terminator from BB over to NewBB, because there is now
 930   // an unconditional jump to SuccBB.  Insert the unconditional jump.
 931   BranchInst::Create(SuccBB, NewBB);
 932
 933   // Check to see if SuccBB has PHI nodes. If so, we need to add entries to the
 934   // PHI nodes for NewBB now.
 935   for (BasicBlock::iterator PNI = SuccBB->begin(); isa<PHINode>(PNI); ++PNI) {
 936     PHINode *PN = cast<PHINode>(PNI);
 937     // Ok, we have a PHI node.  Figure out what the incoming value was for the
 938     // DestBlock.
 939     Value *IV = PN->getIncomingValueForBlock(BB);
 940
 941     // Remap the value if necessary.
 942     if (Instruction *Inst = dyn_cast<Instruction>(IV))
 943       if (Value *MappedIV = ValueMapping[Inst])
 944         IV = MappedIV;
 945     PN->addIncoming(IV, NewBB);
 946   }
 947
 948   // Ok, NewBB is good to go.  Update the terminator of PredBB to jump to
 949   // NewBB instead of BB.  This eliminates predecessors from BB, which requires
 950   // us to simplify any PHI nodes in BB.
 951   TerminatorInst *PredTerm = PredBB->getTerminator();
 952   for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i)
 953     if (PredTerm->getSuccessor(i) == BB) {
 954       BB->removePredecessor(PredBB);
 955       PredTerm->setSuccessor(i, NewBB);
 956     }
 957
 958   // At this point, the IR is fully up to date and consistent.  Do a quick scan
 959   // over the new instructions and zap any that are constants or dead.  This
 960   // frequently happens because of phi translation.
 961   BI = NewBB->begin();
 962   for (BasicBlock::iterator E = NewBB->end(); BI != E; ) {
 963     Instruction *Inst = BI++;
 964     if (Constant *C = ConstantFoldInstruction(Inst, TD)) {
 965       Inst->replaceAllUsesWith(C);
 966       Inst->eraseFromParent();
 967       continue;
 968     }
 969
 970     RecursivelyDeleteTriviallyDeadInstructions(Inst);
 971   }
 972 }