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