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/Transforms/Utils/BasicBlockUtils.h"
  21 #include "llvm/Transforms/Utils/Local.h"
  22 #include "llvm/Support/CommandLine.h"
  23 #include "llvm/Support/Compiler.h"
  24 #include "llvm/Support/Debug.h"
  25 using namespace llvm;
  26
  27 STATISTIC(NumThreads, "Number of jumps threaded");
  28 STATISTIC(NumFolds,   "Number of terminators folded");
  29
  30 static cl::opt<unsigned>
  31 Threshold("jump-threading-threshold",
  32           cl::desc("Max block size to duplicate for jump threading"),
  33           cl::init(6), cl::Hidden);
  34
  35 namespace {
  36   /// This pass performs 'jump threading', which looks at blocks that have
  37   /// multiple predecessors and multiple successors.  If one or more of the
  38   /// predecessors of the block can be proven to always jump to one of the
  39   /// successors, we forward the edge from the predecessor to the successor by
  40   /// duplicating the contents of this block.
  41   ///
  42   /// An example of when this can occur is code like this:
  43   ///
  44   ///   if () { ...
  45   ///     X = 4;
  46   ///   }
  47   ///   if (X < 3) {
  48   ///
  49   /// In this case, the unconditional branch at the end of the first if can be
  50   /// revectored to the false side of the second if.
  51   ///
  52   class VISIBILITY_HIDDEN JumpThreading : public FunctionPass {
  53   public:
  54     static char ID; // Pass identification
  55     JumpThreading() : FunctionPass((intptr_t)&ID) {}
  56
  57     bool runOnFunction(Function &F);
  58     bool ThreadBlock(BasicBlock *BB);
  59     void ThreadEdge(BasicBlock *BB, BasicBlock *PredBB, BasicBlock *SuccBB);
  60     BasicBlock *FactorCommonPHIPreds(PHINode *PN, Constant *CstVal);
  61
  62     bool ProcessJumpOnPHI(PHINode *PN);
  63     bool ProcessJumpOnLogicalPHI(PHINode *PN, bool isAnd);
  64   };
  65   char JumpThreading::ID = 0;
  66   RegisterPass<JumpThreading> X("jump-threading", "Jump Threading");
  67 }
  68
  69 // Public interface to the Jump Threading pass
  70 FunctionPass *llvm::createJumpThreadingPass() { return new JumpThreading(); }
  71
  72 /// runOnFunction - Top level algorithm.
  73 ///
  74 bool JumpThreading::runOnFunction(Function &F) {
  75   DOUT << "Jump threading on function '" << F.getNameStart() << "'\n";
  76
  77   bool AnotherIteration = true, EverChanged = false;
  78   while (AnotherIteration) {
  79     AnotherIteration = false;
  80     bool Changed = false;
  81     for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
  82       while (ThreadBlock(I))
  83         Changed = true;
  84     AnotherIteration = Changed;
  85     EverChanged |= Changed;
  86   }
  87   return EverChanged;
  88 }
  89
  90 /// FactorCommonPHIPreds - If there are multiple preds with the same incoming
  91 /// value for the PHI, factor them together so we get one block to thread for
  92 /// the whole group.
  93 /// This is important for things like "phi i1 [true, true, false, true, x]"
  94 /// where we only need to clone the block for the true blocks once.
  95 ///
  96 BasicBlock *JumpThreading::FactorCommonPHIPreds(PHINode *PN, Constant *CstVal) {
  97   SmallVector<BasicBlock*, 16> CommonPreds;
  98   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
  99     if (PN->getIncomingValue(i) == CstVal)
 100       CommonPreds.push_back(PN->getIncomingBlock(i));
 101
 102   if (CommonPreds.size() == 1)
 103     return CommonPreds[0];
 104
 105   DOUT << "  Factoring out " << CommonPreds.size()
 106        << " common predecessors.\n";
 107   return SplitBlockPredecessors(PN->getParent(),
 108                                 &CommonPreds[0], CommonPreds.size(),
 109                                 ".thr_comm", this);
 110 }
 111
 112
 113 /// getJumpThreadDuplicationCost - Return the cost of duplicating this block to
 114 /// thread across it.
 115 static unsigned getJumpThreadDuplicationCost(const BasicBlock *BB) {
 116   BasicBlock::const_iterator I = BB->begin();
 117   /// Ignore PHI nodes, these will be flattened when duplication happens.
 118   while (isa<PHINode>(*I)) ++I;
 119
 120   // Sum up the cost of each instruction until we get to the terminator.  Don't
 121   // include the terminator because the copy won't include it.
 122   unsigned Size = 0;
 123   for (; !isa<TerminatorInst>(I); ++I) {
 124     // Debugger intrinsics don't incur code size.
 125     if (isa<DbgInfoIntrinsic>(I)) continue;
 126
 127     // If this is a pointer->pointer bitcast, it is free.
 128     if (isa<BitCastInst>(I) && isa<PointerType>(I->getType()))
 129       continue;
 130
 131     // All other instructions count for at least one unit.
 132     ++Size;
 133
 134     // Calls are more expensive.  If they are non-intrinsic calls, we model them
 135     // as having cost of 4.  If they are a non-vector intrinsic, we model them
 136     // as having cost of 2 total, and if they are a vector intrinsic, we model
 137     // them as having cost 1.
 138     if (const CallInst *CI = dyn_cast<CallInst>(I)) {
 139       if (!isa<IntrinsicInst>(CI))
 140         Size += 3;
 141       else if (isa<VectorType>(CI->getType()))
 142         Size += 1;
 143     }
 144   }
 145
 146   // Threading through a switch statement is particularly profitable.  If this
 147   // block ends in a switch, decrease its cost to make it more likely to happen.
 148   if (isa<SwitchInst>(I))
 149     Size = Size > 6 ? Size-6 : 0;
 150
 151   return Size;
 152 }
 153
 154
 155 /// ThreadBlock - If there are any predecessors whose control can be threaded
 156 /// through to a successor, transform them now.
 157 bool JumpThreading::ThreadBlock(BasicBlock *BB) {
 158   // See if this block ends with a branch of switch.  If so, see if the
 159   // condition is a phi node.  If so, and if an entry of the phi node is a
 160   // constant, we can thread the block.
 161   Value *Condition;
 162   if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) {
 163     // Can't thread an unconditional jump.
 164     if (BI->isUnconditional()) return false;
 165     Condition = BI->getCondition();
 166   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator()))
 167     Condition = SI->getCondition();
 168   else
 169     return false; // Must be an invoke.
 170
 171   // If the terminator of this block is branching on a constant, simplify the
 172   // terminator to an unconditional branch.  This can occur due to threading in
 173   // other blocks.
 174   if (isa<ConstantInt>(Condition)) {
 175     DOUT << "  In block '" << BB->getNameStart()
 176          << "' folding terminator: " << *BB->getTerminator();
 177     ++NumFolds;
 178     ConstantFoldTerminator(BB);
 179     return true;
 180   }
 181
 182   // If there is only a single predecessor of this block, nothing to fold.
 183   if (BB->getSinglePredecessor())
 184     return false;
 185
 186   // See if this is a phi node in the current block.
 187   PHINode *PN = dyn_cast<PHINode>(Condition);
 188   if (PN && PN->getParent() == BB)
 189     return ProcessJumpOnPHI(PN);
 190
 191   // If this is a conditional branch whose condition is and/or of a phi, try to
 192   // simplify it.
 193   if (BinaryOperator *CondI = dyn_cast<BinaryOperator>(Condition)) {
 194     if ((CondI->getOpcode() == Instruction::And ||
 195          CondI->getOpcode() == Instruction::Or) &&
 196         isa<BranchInst>(BB->getTerminator())) {
 197       if (PHINode *PN = dyn_cast<PHINode>(CondI->getOperand(0)))
 198         if (PN->getParent() == BB &&
 199             ProcessJumpOnLogicalPHI(PN, CondI->getOpcode() == Instruction::And))
 200           return true;
 201       if (PHINode *PN = dyn_cast<PHINode>(CondI->getOperand(1)))
 202         if (PN->getParent() == BB &&
 203             ProcessJumpOnLogicalPHI(PN, CondI->getOpcode() == Instruction::And))
 204           return true;
 205     }
 206   }
 207
 208   return false;
 209 }
 210
 211 /// ProcessJumpOnPHI - We have a conditional branch of switch on a PHI node in
 212 /// the current block.  See if there are any simplifications we can do based on
 213 /// inputs to the phi node.
 214 ///
 215 bool JumpThreading::ProcessJumpOnPHI(PHINode *PN) {
 216   // See if the phi node has any constant values.  If so, we can determine where
 217   // the corresponding predecessor will branch.
 218   unsigned PredNo = ~0U;
 219   ConstantInt *PredCst = 0;
 220   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 221     if ((PredCst = dyn_cast<ConstantInt>(PN->getIncomingValue(i)))) {
 222       PredNo = i;
 223       break;
 224     }
 225   }
 226
 227   // If no incoming value has a constant, we don't know the destination of any
 228   // predecessors.
 229   if (PredNo == ~0U)
 230     return false;
 231
 232   // See if the cost of duplicating this block is low enough.
 233   BasicBlock *BB = PN->getParent();
 234   unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB);
 235   if (JumpThreadCost > Threshold) {
 236     DOUT << "  Not threading BB '" << BB->getNameStart()
 237          << "' - Cost is too high: " << JumpThreadCost << "\n";
 238     return false;
 239   }
 240
 241   // If so, we can actually do this threading.  Merge any common predecessors
 242   // that will act the same.
 243   BasicBlock *PredBB = FactorCommonPHIPreds(PN, PredCst);
 244
 245   // Next, figure out which successor we are threading to.
 246   BasicBlock *SuccBB;
 247   if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()))
 248     SuccBB = BI->getSuccessor(PredCst == ConstantInt::getFalse());
 249   else {
 250     SwitchInst *SI = cast<SwitchInst>(BB->getTerminator());
 251     SuccBB = SI->getSuccessor(SI->findCaseValue(PredCst));
 252   }
 253
 254   // And finally, do it!
 255   DOUT << "  Threading edge from '" << PredBB->getNameStart() << "' to '"
 256        << SuccBB->getNameStart() << "' with cost: " << JumpThreadCost
 257        << ", across block:\n    "
 258        << *BB << "\n";
 259
 260   ThreadEdge(BB, PredBB, SuccBB);
 261   ++NumThreads;
 262   return true;
 263 }
 264
 265 /// ProcessJumpOnLogicalPHI - PN's basic block contains a conditional branch
 266 /// whose condition is an AND/OR where one side is PN.  If PN has constant
 267 /// operands that permit us to evaluate the condition for some operand, thread
 268 /// through the block.  For example with:
 269 ///   br (and X, phi(Y, Z, false))
 270 /// the predecessor corresponding to the 'false' will always jump to the false
 271 /// destination of the branch.
 272 ///
 273 bool JumpThreading::ProcessJumpOnLogicalPHI(PHINode *PN, bool isAnd) {
 274
 275   // We can only do the simplification for phi nodes of 'false' with AND or
 276   // 'true' with OR.  See if we have any entries in the phi for this.
 277   unsigned PredNo = ~0U;
 278   ConstantInt *PredCst = ConstantInt::get(Type::Int1Ty, !isAnd);
 279   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 280     if (PN->getIncomingValue(i) == PredCst) {
 281       PredNo = i;
 282       break;
 283     }
 284   }
 285
 286   // If no match, bail out.
 287   if (PredNo == ~0U)
 288     return false;
 289
 290   // See if the cost of duplicating this block is low enough.
 291   BasicBlock *BB = PN->getParent();
 292   unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB);
 293   if (JumpThreadCost > Threshold) {
 294     DOUT << "  Not threading BB '" << BB->getNameStart()
 295          << "' - Cost is too high: " << JumpThreadCost << "\n";
 296     return false;
 297   }
 298
 299   // If so, we can actually do this threading.  Merge any common predecessors
 300   // that will act the same.
 301   BasicBlock *PredBB = FactorCommonPHIPreds(PN, PredCst);
 302
 303   // Next, figure out which successor we are threading to.  If this was an AND,
 304   // the constant must be FALSE, and we must be targeting the 'false' block.
 305   // If this is an OR, the constant must be TRUE, and we must be targeting the
 306   // 'true' block.
 307   BasicBlock *SuccBB = BB->getTerminator()->getSuccessor(isAnd);
 308
 309   // And finally, do it!
 310   DOUT << "  Threading edge through bool from '" << PredBB->getNameStart()
 311        << "' to '" << SuccBB->getNameStart() << "' with cost: "
 312        << JumpThreadCost << ", across block:\n    "
 313        << *BB << "\n";
 314
 315   ThreadEdge(BB, PredBB, SuccBB);
 316   ++NumThreads;
 317   return true;
 318 }
 319
 320
 321 /// ThreadEdge - We have decided that it is safe and profitable to thread an
 322 /// edge from PredBB to SuccBB across BB.  Transform the IR to reflect this
 323 /// change.
 324 void JumpThreading::ThreadEdge(BasicBlock *BB, BasicBlock *PredBB,
 325                                BasicBlock *SuccBB) {
 326
 327   // Jump Threading can not update SSA properties correctly if the values
 328   // defined in the duplicated block are used outside of the block itself.  For
 329   // this reason, we spill all values that are used outside of BB to the stack.
 330   for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I)
 331     if (I->isUsedOutsideOfBlock(BB)) {
 332       // We found a use of I outside of BB.  Create a new stack slot to
 333       // break this inter-block usage pattern.
 334       DemoteRegToStack(*I);
 335     }
 336
 337   // We are going to have to map operands from the original BB block to the new
 338   // copy of the block 'NewBB'.  If there are PHI nodes in BB, evaluate them to
 339   // account for entry from PredBB.
 340   DenseMap<Instruction*, Value*> ValueMapping;
 341
 342   BasicBlock *NewBB =
 343     BasicBlock::Create(BB->getName()+".thread", BB->getParent(), BB);
 344   NewBB->moveAfter(PredBB);
 345
 346   BasicBlock::iterator BI = BB->begin();
 347   for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
 348     ValueMapping[PN] = PN->getIncomingValueForBlock(PredBB);
 349
 350   // Clone the non-phi instructions of BB into NewBB, keeping track of the
 351   // mapping and using it to remap operands in the cloned instructions.
 352   for (; !isa<TerminatorInst>(BI); ++BI) {
 353     Instruction *New = BI->clone();
 354     New->setName(BI->getNameStart());
 355     NewBB->getInstList().push_back(New);
 356     ValueMapping[BI] = New;
 357
 358     // Remap operands to patch up intra-block references.
 359     for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
 360       if (Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i)))
 361         if (Value *Remapped = ValueMapping[Inst])
 362           New->setOperand(i, Remapped);
 363   }
 364
 365   // We didn't copy the terminator from BB over to NewBB, because there is now
 366   // an unconditional jump to SuccBB.  Insert the unconditional jump.
 367   BranchInst::Create(SuccBB, NewBB);
 368
 369   // Check to see if SuccBB has PHI nodes. If so, we need to add entries to the
 370   // PHI nodes for NewBB now.
 371   for (BasicBlock::iterator PNI = SuccBB->begin(); isa<PHINode>(PNI); ++PNI) {
 372     PHINode *PN = cast<PHINode>(PNI);
 373     // Ok, we have a PHI node.  Figure out what the incoming value was for the
 374     // DestBlock.
 375     Value *IV = PN->getIncomingValueForBlock(BB);
 376
 377     // Remap the value if necessary.
 378     if (Instruction *Inst = dyn_cast<Instruction>(IV))
 379       if (Value *MappedIV = ValueMapping[Inst])
 380         IV = MappedIV;
 381     PN->addIncoming(IV, NewBB);
 382   }
 383
 384   // Finally, NewBB is good to go.  Update the terminator of PredBB to jump to
 385   // NewBB instead of BB.  This eliminates predecessors from BB, which requires
 386   // us to simplify any PHI nodes in BB.
 387   TerminatorInst *PredTerm = PredBB->getTerminator();
 388   for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i)
 389     if (PredTerm->getSuccessor(i) == BB) {
 390       BB->removePredecessor(PredBB);
 391       PredTerm->setSuccessor(i, NewBB);
 392     }
 393 }