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
  71     bool ProcessJumpOnPHI(PHINode *PN);
  72     bool ProcessBranchOnLogical(Value *V, BasicBlock *BB, bool isAnd);
  73     bool ProcessBranchOnCompare(CmpInst *Cmp, BasicBlock *BB);
  74
  75     bool SimplifyPartiallyRedundantLoad(LoadInst *LI);
  76   };
  77 }
  78
  79 char JumpThreading::ID = 0;
  80 static RegisterPass<JumpThreading>
  81 X("jump-threading", "Jump Threading");
  82
  83 // Public interface to the Jump Threading pass
  84 FunctionPass *llvm::createJumpThreadingPass() { return new JumpThreading(); }
  85
  86 /// runOnFunction - Top level algorithm.
  87 ///
  88 bool JumpThreading::runOnFunction(Function &F) {
  89   DOUT << "Jump threading on function '" << F.getNameStart() << "'\n";
  90   TD = &getAnalysis<TargetData>();
  91
  92   bool AnotherIteration = true, EverChanged = false;
  93   while (AnotherIteration) {
  94     AnotherIteration = false;
  95     bool Changed = false;
  96     for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
  97       while (ProcessBlock(I))
  98         Changed = true;
  99     AnotherIteration = Changed;
 100     EverChanged |= Changed;
 101   }
 102   return EverChanged;
 103 }
 104
 105 /// FactorCommonPHIPreds - If there are multiple preds with the same incoming
 106 /// value for the PHI, factor them together so we get one block to thread for
 107 /// the whole group.
 108 /// This is important for things like "phi i1 [true, true, false, true, x]"
 109 /// where we only need to clone the block for the true blocks once.
 110 ///
 111 BasicBlock *JumpThreading::FactorCommonPHIPreds(PHINode *PN, Constant *CstVal) {
 112   SmallVector<BasicBlock*, 16> CommonPreds;
 113   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
 114     if (PN->getIncomingValue(i) == CstVal)
 115       CommonPreds.push_back(PN->getIncomingBlock(i));
 116
 117   if (CommonPreds.size() == 1)
 118     return CommonPreds[0];
 119
 120   DOUT << "  Factoring out " << CommonPreds.size()
 121        << " common predecessors.\n";
 122   return SplitBlockPredecessors(PN->getParent(),
 123                                 &CommonPreds[0], CommonPreds.size(),
 124                                 ".thr_comm", this);
 125 }
 126
 127
 128 /// getJumpThreadDuplicationCost - Return the cost of duplicating this block to
 129 /// thread across it.
 130 static unsigned getJumpThreadDuplicationCost(const BasicBlock *BB) {
 131   /// Ignore PHI nodes, these will be flattened when duplication happens.
 132   BasicBlock::const_iterator I = BB->getFirstNonPHI();
 133
 134   // Sum up the cost of each instruction until we get to the terminator.  Don't
 135   // include the terminator because the copy won't include it.
 136   unsigned Size = 0;
 137   for (; !isa<TerminatorInst>(I); ++I) {
 138     // Debugger intrinsics don't incur code size.
 139     if (isa<DbgInfoIntrinsic>(I)) continue;
 140
 141     // If this is a pointer->pointer bitcast, it is free.
 142     if (isa<BitCastInst>(I) && isa<PointerType>(I->getType()))
 143       continue;
 144
 145     // All other instructions count for at least one unit.
 146     ++Size;
 147
 148     // Calls are more expensive.  If they are non-intrinsic calls, we model them
 149     // as having cost of 4.  If they are a non-vector intrinsic, we model them
 150     // as having cost of 2 total, and if they are a vector intrinsic, we model
 151     // them as having cost 1.
 152     if (const CallInst *CI = dyn_cast<CallInst>(I)) {
 153       if (!isa<IntrinsicInst>(CI))
 154         Size += 3;
 155       else if (isa<VectorType>(CI->getType()))
 156         Size += 1;
 157     }
 158   }
 159
 160   // Threading through a switch statement is particularly profitable.  If this
 161   // block ends in a switch, decrease its cost to make it more likely to happen.
 162   if (isa<SwitchInst>(I))
 163     Size = Size > 6 ? Size-6 : 0;
 164
 165   return Size;
 166 }
 167
 168 /// ProcessBlock - If there are any predecessors whose control can be threaded
 169 /// through to a successor, transform them now.
 170 bool JumpThreading::ProcessBlock(BasicBlock *BB) {
 171   // If this block has a single predecessor, and if that pred has a single
 172   // successor, merge the blocks.  This encourages recursive jump threading
 173   // because now the condition in this block can be threaded through
 174   // predecessors of our predecessor block.
 175   if (BasicBlock *SinglePred = BB->getSinglePredecessor())
 176     if (SinglePred->getTerminator()->getNumSuccessors() == 1 &&
 177         SinglePred != BB) {
 178       // Remember if SinglePred was the entry block of the function.  If so, we
 179       // will need to move BB back to the entry position.
 180       bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock();
 181       MergeBasicBlockIntoOnlyPred(BB);
 182
 183       if (isEntry && BB != &BB->getParent()->getEntryBlock())
 184         BB->moveBefore(&BB->getParent()->getEntryBlock());
 185       return true;
 186     }
 187
 188   // See if this block ends with a branch or switch.  If so, see if the
 189   // condition is a phi node.  If so, and if an entry of the phi node is a
 190   // constant, we can thread the block.
 191   Value *Condition;
 192   if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) {
 193     // Can't thread an unconditional jump.
 194     if (BI->isUnconditional()) return false;
 195     Condition = BI->getCondition();
 196   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator()))
 197     Condition = SI->getCondition();
 198   else
 199     return false; // Must be an invoke.
 200
 201   // If the terminator of this block is branching on a constant, simplify the
 202   // terminator to an unconditional branch.  This can occur due to threading in
 203   // other blocks.
 204   if (isa<ConstantInt>(Condition)) {
 205     DOUT << "  In block '" << BB->getNameStart()
 206          << "' folding terminator: " << *BB->getTerminator();
 207     ++NumFolds;
 208     ConstantFoldTerminator(BB);
 209     return true;
 210   }
 211
 212   // If there is only a single predecessor of this block, nothing to fold.
 213   if (BB->getSinglePredecessor())
 214     return false;
 215
 216   // See if this is a phi node in the current block.
 217   PHINode *PN = dyn_cast<PHINode>(Condition);
 218   if (PN && PN->getParent() == BB)
 219     return ProcessJumpOnPHI(PN);
 220
 221   // If this is a conditional branch whose condition is and/or of a phi, try to
 222   // simplify it.
 223   if (BinaryOperator *CondI = dyn_cast<BinaryOperator>(Condition)) {
 224     if ((CondI->getOpcode() == Instruction::And ||
 225          CondI->getOpcode() == Instruction::Or) &&
 226         isa<BranchInst>(BB->getTerminator()) &&
 227         ProcessBranchOnLogical(CondI, BB,
 228                                CondI->getOpcode() == Instruction::And))
 229       return true;
 230   }
 231
 232   // If we have "br (phi != 42)" and the phi node has any constant values as
 233   // operands, we can thread through this block.
 234   if (CmpInst *CondCmp = dyn_cast<CmpInst>(Condition))
 235     if (isa<PHINode>(CondCmp->getOperand(0)) &&
 236         isa<Constant>(CondCmp->getOperand(1)) &&
 237         ProcessBranchOnCompare(CondCmp, BB))
 238       return true;
 239
 240   // Check for some cases that are worth simplifying.  Right now we want to look
 241   // for loads that are used by a switch or by the condition for the branch.  If
 242   // we see one, check to see if it's partially redundant.  If so, insert a PHI
 243   // which can then be used to thread the values.
 244   //
 245   // This is particularly important because reg2mem inserts loads and stores all
 246   // over the place, and this blocks jump threading if we don't zap them.
 247   Value *SimplifyValue = Condition;
 248   if (CmpInst *CondCmp = dyn_cast<CmpInst>(SimplifyValue))
 249     if (isa<Constant>(CondCmp->getOperand(1)))
 250       SimplifyValue = CondCmp->getOperand(0);
 251
 252   if (LoadInst *LI = dyn_cast<LoadInst>(SimplifyValue))
 253     if (SimplifyPartiallyRedundantLoad(LI))
 254       return true;
 255
 256   // TODO: If we have: "br (X > 0)"  and we have a predecessor where we know
 257   // "(X == 4)" thread through this block.
 258
 259   return false;
 260 }
 261
 262 /// SimplifyPartiallyRedundantLoad - If LI is an obviously partially redundant
 263 /// load instruction, eliminate it by replacing it with a PHI node.  This is an
 264 /// important optimization that encourages jump threading, and needs to be run
 265 /// interlaced with other jump threading tasks.
 266 bool JumpThreading::SimplifyPartiallyRedundantLoad(LoadInst *LI) {
 267   // Don't hack volatile loads.
 268   if (LI->isVolatile()) return false;
 269
 270   // If the load is defined in a block with exactly one predecessor, it can't be
 271   // partially redundant.
 272   BasicBlock *LoadBB = LI->getParent();
 273   if (LoadBB->getSinglePredecessor())
 274     return false;
 275
 276   Value *LoadedPtr = LI->getOperand(0);
 277
 278   // If the loaded operand is defined in the LoadBB, it can't be available.
 279   // FIXME: Could do PHI translation, that would be fun :)
 280   if (Instruction *PtrOp = dyn_cast<Instruction>(LoadedPtr))
 281     if (PtrOp->getParent() == LoadBB)
 282       return false;
 283
 284   // Scan a few instructions up from the load, to see if it is obviously live at
 285   // the entry to its block.
 286   BasicBlock::iterator BBIt = LI;
 287
 288   if (Value *AvailableVal = FindAvailableLoadedValue(LoadedPtr, LoadBB,
 289                                                      BBIt, 6)) {
 290     // If the value if the load is locally available within the block, just use
 291     // it.  This frequently occurs for reg2mem'd allocas.
 292     //cerr << "LOAD ELIMINATED:\n" << *BBIt << *LI << "\n";
 293     LI->replaceAllUsesWith(AvailableVal);
 294     LI->eraseFromParent();
 295     return true;
 296   }
 297
 298   // Otherwise, if we scanned the whole block and got to the top of the block,
 299   // we know the block is locally transparent to the load.  If not, something
 300   // might clobber its value.
 301   if (BBIt != LoadBB->begin())
 302     return false;
 303
 304
 305   SmallPtrSet<BasicBlock*, 8> PredsScanned;
 306   typedef SmallVector<std::pair<BasicBlock*, Value*>, 8> AvailablePredsTy;
 307   AvailablePredsTy AvailablePreds;
 308   BasicBlock *OneUnavailablePred = 0;
 309
 310   // If we got here, the loaded value is transparent through to the start of the
 311   // block.  Check to see if it is available in any of the predecessor blocks.
 312   for (pred_iterator PI = pred_begin(LoadBB), PE = pred_end(LoadBB);
 313        PI != PE; ++PI) {
 314     BasicBlock *PredBB = *PI;
 315
 316     // If we already scanned this predecessor, skip it.
 317     if (!PredsScanned.insert(PredBB))
 318       continue;
 319
 320     // Scan the predecessor to see if the value is available in the pred.
 321     BBIt = PredBB->end();
 322     Value *PredAvailable = FindAvailableLoadedValue(LoadedPtr, PredBB, BBIt, 6);
 323     if (!PredAvailable) {
 324       OneUnavailablePred = PredBB;
 325       continue;
 326     }
 327
 328     // If so, this load is partially redundant.  Remember this info so that we
 329     // can create a PHI node.
 330     AvailablePreds.push_back(std::make_pair(PredBB, PredAvailable));
 331   }
 332
 333   // If the loaded value isn't available in any predecessor, it isn't partially
 334   // redundant.
 335   if (AvailablePreds.empty()) return false;
 336
 337   // Okay, the loaded value is available in at least one (and maybe all!)
 338   // predecessors.  If the value is unavailable in more than one unique
 339   // predecessor, we want to insert a merge block for those common predecessors.
 340   // This ensures that we only have to insert one reload, thus not increasing
 341   // code size.
 342   BasicBlock *UnavailablePred = 0;
 343
 344   // If there is exactly one predecessor where the value is unavailable, the
 345   // already computed 'OneUnavailablePred' block is it.  If it ends in an
 346   // unconditional branch, we know that it isn't a critical edge.
 347   if (PredsScanned.size() == AvailablePreds.size()+1 &&
 348       OneUnavailablePred->getTerminator()->getNumSuccessors() == 1) {
 349     UnavailablePred = OneUnavailablePred;
 350   } else if (PredsScanned.size() != AvailablePreds.size()) {
 351     // Otherwise, we had multiple unavailable predecessors or we had a critical
 352     // edge from the one.
 353     SmallVector<BasicBlock*, 8> PredsToSplit;
 354     SmallPtrSet<BasicBlock*, 8> AvailablePredSet;
 355
 356     for (unsigned i = 0, e = AvailablePreds.size(); i != e; ++i)
 357       AvailablePredSet.insert(AvailablePreds[i].first);
 358
 359     // Add all the unavailable predecessors to the PredsToSplit list.
 360     for (pred_iterator PI = pred_begin(LoadBB), PE = pred_end(LoadBB);
 361          PI != PE; ++PI)
 362       if (!AvailablePredSet.count(*PI))
 363         PredsToSplit.push_back(*PI);
 364
 365     // Split them out to their own block.
 366     UnavailablePred =
 367       SplitBlockPredecessors(LoadBB, &PredsToSplit[0], PredsToSplit.size(),
 368                              "thread-split", this);
 369   }
 370
 371   // If the value isn't available in all predecessors, then there will be
 372   // exactly one where it isn't available.  Insert a load on that edge and add
 373   // it to the AvailablePreds list.
 374   if (UnavailablePred) {
 375     assert(UnavailablePred->getTerminator()->getNumSuccessors() == 1 &&
 376            "Can't handle critical edge here!");
 377     Value *NewVal = new LoadInst(LoadedPtr, LI->getName()+".pr",
 378                                  UnavailablePred->getTerminator());
 379     AvailablePreds.push_back(std::make_pair(UnavailablePred, NewVal));
 380   }
 381
 382   // Now we know that each predecessor of this block has a value in
 383   // AvailablePreds, sort them for efficient access as we're walking the preds.
 384   array_pod_sort(AvailablePreds.begin(), AvailablePreds.end());
 385
 386   // Create a PHI node at the start of the block for the PRE'd load value.
 387   PHINode *PN = PHINode::Create(LI->getType(), "", LoadBB->begin());
 388   PN->takeName(LI);
 389
 390   // Insert new entries into the PHI for each predecessor.  A single block may
 391   // have multiple entries here.
 392   for (pred_iterator PI = pred_begin(LoadBB), E = pred_end(LoadBB); PI != E;
 393        ++PI) {
 394     AvailablePredsTy::iterator I =
 395       std::lower_bound(AvailablePreds.begin(), AvailablePreds.end(),
 396                        std::make_pair(*PI, (Value*)0));
 397
 398     assert(I != AvailablePreds.end() && I->first == *PI &&
 399            "Didn't find entry for predecessor!");
 400
 401     PN->addIncoming(I->second, I->first);
 402   }
 403
 404   //cerr << "PRE: " << *LI << *PN << "\n";
 405
 406   LI->replaceAllUsesWith(PN);
 407   LI->eraseFromParent();
 408
 409   return true;
 410 }
 411
 412
 413 /// ProcessJumpOnPHI - We have a conditional branch of switch on a PHI node in
 414 /// the current block.  See if there are any simplifications we can do based on
 415 /// inputs to the phi node.
 416 ///
 417 bool JumpThreading::ProcessJumpOnPHI(PHINode *PN) {
 418   // See if the phi node has any constant values.  If so, we can determine where
 419   // the corresponding predecessor will branch.
 420   ConstantInt *PredCst = 0;
 421   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
 422     if ((PredCst = dyn_cast<ConstantInt>(PN->getIncomingValue(i))))
 423       break;
 424
 425   // If no incoming value has a constant, we don't know the destination of any
 426   // predecessors.
 427   if (PredCst == 0)
 428     return false;
 429
 430   // See if the cost of duplicating this block is low enough.
 431   BasicBlock *BB = PN->getParent();
 432   unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB);
 433   if (JumpThreadCost > Threshold) {
 434     DOUT << "  Not threading BB '" << BB->getNameStart()
 435          << "' - Cost is too high: " << JumpThreadCost << "\n";
 436     return false;
 437   }
 438
 439   // If so, we can actually do this threading.  Merge any common predecessors
 440   // that will act the same.
 441   BasicBlock *PredBB = FactorCommonPHIPreds(PN, PredCst);
 442
 443   // Next, figure out which successor we are threading to.
 444   BasicBlock *SuccBB;
 445   if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()))
 446     SuccBB = BI->getSuccessor(PredCst == ConstantInt::getFalse());
 447   else {
 448     SwitchInst *SI = cast<SwitchInst>(BB->getTerminator());
 449     SuccBB = SI->getSuccessor(SI->findCaseValue(PredCst));
 450   }
 451
 452   // If threading to the same block as we come from, we would infinite loop.
 453   if (SuccBB == BB) {
 454     DOUT << "  Not threading BB '" << BB->getNameStart()
 455          << "' - would thread to self!\n";
 456     return false;
 457   }
 458
 459   // And finally, do it!
 460   DOUT << "  Threading edge from '" << PredBB->getNameStart() << "' to '"
 461        << SuccBB->getNameStart() << "' with cost: " << JumpThreadCost
 462        << ", across block:\n    "
 463        << *BB << "\n";
 464
 465   ThreadEdge(BB, PredBB, SuccBB);
 466   ++NumThreads;
 467   return true;
 468 }
 469
 470 /// ProcessJumpOnLogicalPHI - PN's basic block contains a conditional branch
 471 /// whose condition is an AND/OR where one side is PN.  If PN has constant
 472 /// operands that permit us to evaluate the condition for some operand, thread
 473 /// through the block.  For example with:
 474 ///   br (and X, phi(Y, Z, false))
 475 /// the predecessor corresponding to the 'false' will always jump to the false
 476 /// destination of the branch.
 477 ///
 478 bool JumpThreading::ProcessBranchOnLogical(Value *V, BasicBlock *BB,
 479                                            bool isAnd) {
 480   // If this is a binary operator tree of the same AND/OR opcode, check the
 481   // LHS/RHS.
 482   if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V))
 483     if ((isAnd && BO->getOpcode() == Instruction::And) ||
 484         (!isAnd && BO->getOpcode() == Instruction::Or)) {
 485       if (ProcessBranchOnLogical(BO->getOperand(0), BB, isAnd))
 486         return true;
 487       if (ProcessBranchOnLogical(BO->getOperand(1), BB, isAnd))
 488         return true;
 489     }
 490
 491   // If this isn't a PHI node, we can't handle it.
 492   PHINode *PN = dyn_cast<PHINode>(V);
 493   if (!PN || PN->getParent() != BB) return false;
 494
 495   // We can only do the simplification for phi nodes of 'false' with AND or
 496   // 'true' with OR.  See if we have any entries in the phi for this.
 497   unsigned PredNo = ~0U;
 498   ConstantInt *PredCst = ConstantInt::get(Type::Int1Ty, !isAnd);
 499   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 500     if (PN->getIncomingValue(i) == PredCst) {
 501       PredNo = i;
 502       break;
 503     }
 504   }
 505
 506   // If no match, bail out.
 507   if (PredNo == ~0U)
 508     return false;
 509
 510   // See if the cost of duplicating this block is low enough.
 511   unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB);
 512   if (JumpThreadCost > Threshold) {
 513     DOUT << "  Not threading BB '" << BB->getNameStart()
 514          << "' - Cost is too high: " << JumpThreadCost << "\n";
 515     return false;
 516   }
 517
 518   // If so, we can actually do this threading.  Merge any common predecessors
 519   // that will act the same.
 520   BasicBlock *PredBB = FactorCommonPHIPreds(PN, PredCst);
 521
 522   // Next, figure out which successor we are threading to.  If this was an AND,
 523   // the constant must be FALSE, and we must be targeting the 'false' block.
 524   // If this is an OR, the constant must be TRUE, and we must be targeting the
 525   // 'true' block.
 526   BasicBlock *SuccBB = BB->getTerminator()->getSuccessor(isAnd);
 527
 528   // If threading to the same block as we come from, we would infinite loop.
 529   if (SuccBB == BB) {
 530     DOUT << "  Not threading BB '" << BB->getNameStart()
 531     << "' - would thread to self!\n";
 532     return false;
 533   }
 534
 535   // And finally, do it!
 536   DOUT << "  Threading edge through bool from '" << PredBB->getNameStart()
 537        << "' to '" << SuccBB->getNameStart() << "' with cost: "
 538        << JumpThreadCost << ", across block:\n    "
 539        << *BB << "\n";
 540
 541   ThreadEdge(BB, PredBB, SuccBB);
 542   ++NumThreads;
 543   return true;
 544 }
 545
 546 /// ProcessBranchOnCompare - We found a branch on a comparison between a phi
 547 /// node and a constant.  If the PHI node contains any constants as inputs, we
 548 /// can fold the compare for that edge and thread through it.
 549 bool JumpThreading::ProcessBranchOnCompare(CmpInst *Cmp, BasicBlock *BB) {
 550   PHINode *PN = cast<PHINode>(Cmp->getOperand(0));
 551   Constant *RHS = cast<Constant>(Cmp->getOperand(1));
 552
 553   // If the phi isn't in the current block, an incoming edge to this block
 554   // doesn't control the destination.
 555   if (PN->getParent() != BB)
 556     return false;
 557
 558   // We can do this simplification if any comparisons fold to true or false.
 559   // See if any do.
 560   Constant *PredCst = 0;
 561   bool TrueDirection = false;
 562   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 563     PredCst = dyn_cast<Constant>(PN->getIncomingValue(i));
 564     if (PredCst == 0) continue;
 565
 566     Constant *Res;
 567     if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cmp))
 568       Res = ConstantExpr::getICmp(ICI->getPredicate(), PredCst, RHS);
 569     else
 570       Res = ConstantExpr::getFCmp(cast<FCmpInst>(Cmp)->getPredicate(),
 571                                   PredCst, RHS);
 572     // If this folded to a constant expr, we can't do anything.
 573     if (ConstantInt *ResC = dyn_cast<ConstantInt>(Res)) {
 574       TrueDirection = ResC->getZExtValue();
 575       break;
 576     }
 577     // If this folded to undef, just go the false way.
 578     if (isa<UndefValue>(Res)) {
 579       TrueDirection = false;
 580       break;
 581     }
 582
 583     // Otherwise, we can't fold this input.
 584     PredCst = 0;
 585   }
 586
 587   // If no match, bail out.
 588   if (PredCst == 0)
 589     return false;
 590
 591   // See if the cost of duplicating this block is low enough.
 592   unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB);
 593   if (JumpThreadCost > Threshold) {
 594     DOUT << "  Not threading BB '" << BB->getNameStart()
 595          << "' - Cost is too high: " << JumpThreadCost << "\n";
 596     return false;
 597   }
 598
 599   // If so, we can actually do this threading.  Merge any common predecessors
 600   // that will act the same.
 601   BasicBlock *PredBB = FactorCommonPHIPreds(PN, PredCst);
 602
 603   // Next, get our successor.
 604   BasicBlock *SuccBB = BB->getTerminator()->getSuccessor(!TrueDirection);
 605
 606   // If threading to the same block as we come from, we would infinite loop.
 607   if (SuccBB == BB) {
 608     DOUT << "  Not threading BB '" << BB->getNameStart()
 609     << "' - would thread to self!\n";
 610     return false;
 611   }
 612
 613
 614   // And finally, do it!
 615   DOUT << "  Threading edge through bool from '" << PredBB->getNameStart()
 616        << "' to '" << SuccBB->getNameStart() << "' with cost: "
 617        << JumpThreadCost << ", across block:\n    "
 618        << *BB << "\n";
 619
 620   ThreadEdge(BB, PredBB, SuccBB);
 621   ++NumThreads;
 622   return true;
 623 }
 624
 625
 626 /// ThreadEdge - We have decided that it is safe and profitable to thread an
 627 /// edge from PredBB to SuccBB across BB.  Transform the IR to reflect this
 628 /// change.
 629 void JumpThreading::ThreadEdge(BasicBlock *BB, BasicBlock *PredBB,
 630                                BasicBlock *SuccBB) {
 631
 632   // Jump Threading can not update SSA properties correctly if the values
 633   // defined in the duplicated block are used outside of the block itself.  For
 634   // this reason, we spill all values that are used outside of BB to the stack.
 635   for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) {
 636     if (!I->isUsedOutsideOfBlock(BB))
 637       continue;
 638
 639     // We found a use of I outside of BB.  Create a new stack slot to
 640     // break this inter-block usage pattern.
 641     DemoteRegToStack(*I);
 642   }
 643
 644   // We are going to have to map operands from the original BB block to the new
 645   // copy of the block 'NewBB'.  If there are PHI nodes in BB, evaluate them to
 646   // account for entry from PredBB.
 647   DenseMap<Instruction*, Value*> ValueMapping;
 648
 649   BasicBlock *NewBB =
 650     BasicBlock::Create(BB->getName()+".thread", BB->getParent(), BB);
 651   NewBB->moveAfter(PredBB);
 652
 653   BasicBlock::iterator BI = BB->begin();
 654   for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
 655     ValueMapping[PN] = PN->getIncomingValueForBlock(PredBB);
 656
 657   // Clone the non-phi instructions of BB into NewBB, keeping track of the
 658   // mapping and using it to remap operands in the cloned instructions.
 659   for (; !isa<TerminatorInst>(BI); ++BI) {
 660     Instruction *New = BI->clone();
 661     New->setName(BI->getNameStart());
 662     NewBB->getInstList().push_back(New);
 663     ValueMapping[BI] = New;
 664
 665     // Remap operands to patch up intra-block references.
 666     for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
 667       if (Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i)))
 668         if (Value *Remapped = ValueMapping[Inst])
 669           New->setOperand(i, Remapped);
 670   }
 671
 672   // We didn't copy the terminator from BB over to NewBB, because there is now
 673   // an unconditional jump to SuccBB.  Insert the unconditional jump.
 674   BranchInst::Create(SuccBB, NewBB);
 675
 676   // Check to see if SuccBB has PHI nodes. If so, we need to add entries to the
 677   // PHI nodes for NewBB now.
 678   for (BasicBlock::iterator PNI = SuccBB->begin(); isa<PHINode>(PNI); ++PNI) {
 679     PHINode *PN = cast<PHINode>(PNI);
 680     // Ok, we have a PHI node.  Figure out what the incoming value was for the
 681     // DestBlock.
 682     Value *IV = PN->getIncomingValueForBlock(BB);
 683
 684     // Remap the value if necessary.
 685     if (Instruction *Inst = dyn_cast<Instruction>(IV))
 686       if (Value *MappedIV = ValueMapping[Inst])
 687         IV = MappedIV;
 688     PN->addIncoming(IV, NewBB);
 689   }
 690
 691   // Ok, NewBB is good to go.  Update the terminator of PredBB to jump to
 692   // NewBB instead of BB.  This eliminates predecessors from BB, which requires
 693   // us to simplify any PHI nodes in BB.
 694   TerminatorInst *PredTerm = PredBB->getTerminator();
 695   for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i)
 696     if (PredTerm->getSuccessor(i) == BB) {
 697       BB->removePredecessor(PredBB);
 698       PredTerm->setSuccessor(i, NewBB);
 699     }
 700
 701   // At this point, the IR is fully up to date and consistent.  Do a quick scan
 702   // over the new instructions and zap any that are constants or dead.  This
 703   // frequently happens because of phi translation.
 704   BI = NewBB->begin();
 705   for (BasicBlock::iterator E = NewBB->end(); BI != E; ) {
 706     Instruction *Inst = BI++;
 707     if (Constant *C = ConstantFoldInstruction(Inst, TD)) {
 708       Inst->replaceAllUsesWith(C);
 709       Inst->eraseFromParent();
 710       continue;
 711     }
 712
 713     RecursivelyDeleteTriviallyDeadInstructions(Inst);
 714   }
 715 }