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