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 ProcessBranchOnLogical(Value *V, BasicBlock *BB, bool isAnd);
  64     bool ProcessBranchOnCompare(CmpInst *Cmp, BasicBlock *BB);
  65   };
  66 }
  67
  68 char JumpThreading::ID = 0;
  69 static RegisterPass<JumpThreading>
  70 X("jump-threading", "Jump Threading");
  71
  72 // Public interface to the Jump Threading pass
  73 FunctionPass *llvm::createJumpThreadingPass() { return new JumpThreading(); }
  74
  75 /// runOnFunction - Top level algorithm.
  76 ///
  77 bool JumpThreading::runOnFunction(Function &F) {
  78   DOUT << "Jump threading on function '" << F.getNameStart() << "'\n";
  79
  80   bool AnotherIteration = true, EverChanged = false;
  81   while (AnotherIteration) {
  82     AnotherIteration = false;
  83     bool Changed = false;
  84     for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
  85       while (ThreadBlock(I))
  86         Changed = true;
  87     AnotherIteration = Changed;
  88     EverChanged |= Changed;
  89   }
  90   return EverChanged;
  91 }
  92
  93 /// FactorCommonPHIPreds - If there are multiple preds with the same incoming
  94 /// value for the PHI, factor them together so we get one block to thread for
  95 /// the whole group.
  96 /// This is important for things like "phi i1 [true, true, false, true, x]"
  97 /// where we only need to clone the block for the true blocks once.
  98 ///
  99 BasicBlock *JumpThreading::FactorCommonPHIPreds(PHINode *PN, Constant *CstVal) {
 100   SmallVector<BasicBlock*, 16> CommonPreds;
 101   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
 102     if (PN->getIncomingValue(i) == CstVal)
 103       CommonPreds.push_back(PN->getIncomingBlock(i));
 104
 105   if (CommonPreds.size() == 1)
 106     return CommonPreds[0];
 107
 108   DOUT << "  Factoring out " << CommonPreds.size()
 109        << " common predecessors.\n";
 110   return SplitBlockPredecessors(PN->getParent(),
 111                                 &CommonPreds[0], CommonPreds.size(),
 112                                 ".thr_comm", this);
 113 }
 114
 115
 116 /// getJumpThreadDuplicationCost - Return the cost of duplicating this block to
 117 /// thread across it.
 118 static unsigned getJumpThreadDuplicationCost(const BasicBlock *BB) {
 119   BasicBlock::const_iterator I = BB->begin();
 120   /// Ignore PHI nodes, these will be flattened when duplication happens.
 121   while (isa<PHINode>(*I)) ++I;
 122
 123   // Sum up the cost of each instruction until we get to the terminator.  Don't
 124   // include the terminator because the copy won't include it.
 125   unsigned Size = 0;
 126   for (; !isa<TerminatorInst>(I); ++I) {
 127     // Debugger intrinsics don't incur code size.
 128     if (isa<DbgInfoIntrinsic>(I)) continue;
 129
 130     // If this is a pointer->pointer bitcast, it is free.
 131     if (isa<BitCastInst>(I) && isa<PointerType>(I->getType()))
 132       continue;
 133
 134     // All other instructions count for at least one unit.
 135     ++Size;
 136
 137     // Calls are more expensive.  If they are non-intrinsic calls, we model them
 138     // as having cost of 4.  If they are a non-vector intrinsic, we model them
 139     // as having cost of 2 total, and if they are a vector intrinsic, we model
 140     // them as having cost 1.
 141     if (const CallInst *CI = dyn_cast<CallInst>(I)) {
 142       if (!isa<IntrinsicInst>(CI))
 143         Size += 3;
 144       else if (isa<VectorType>(CI->getType()))
 145         Size += 1;
 146     }
 147   }
 148
 149   // Threading through a switch statement is particularly profitable.  If this
 150   // block ends in a switch, decrease its cost to make it more likely to happen.
 151   if (isa<SwitchInst>(I))
 152     Size = Size > 6 ? Size-6 : 0;
 153
 154   return Size;
 155 }
 156
 157
 158 /// ThreadBlock - If there are any predecessors whose control can be threaded
 159 /// through to a successor, transform them now.
 160 bool JumpThreading::ThreadBlock(BasicBlock *BB) {
 161   // See if this block ends with a branch or switch.  If so, see if the
 162   // condition is a phi node.  If so, and if an entry of the phi node is a
 163   // constant, we can thread the block.
 164   Value *Condition;
 165   if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) {
 166     // Can't thread an unconditional jump.
 167     if (BI->isUnconditional()) return false;
 168     Condition = BI->getCondition();
 169   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator()))
 170     Condition = SI->getCondition();
 171   else
 172     return false; // Must be an invoke.
 173
 174   // If the terminator of this block is branching on a constant, simplify the
 175   // terminator to an unconditional branch.  This can occur due to threading in
 176   // other blocks.
 177   if (isa<ConstantInt>(Condition)) {
 178     DOUT << "  In block '" << BB->getNameStart()
 179          << "' folding terminator: " << *BB->getTerminator();
 180     ++NumFolds;
 181     ConstantFoldTerminator(BB);
 182     return true;
 183   }
 184
 185   // If there is only a single predecessor of this block, nothing to fold.
 186   if (BB->getSinglePredecessor())
 187     return false;
 188
 189   // See if this is a phi node in the current block.
 190   PHINode *PN = dyn_cast<PHINode>(Condition);
 191   if (PN && PN->getParent() == BB)
 192     return ProcessJumpOnPHI(PN);
 193
 194   // If this is a conditional branch whose condition is and/or of a phi, try to
 195   // simplify it.
 196   if (BinaryOperator *CondI = dyn_cast<BinaryOperator>(Condition)) {
 197     if ((CondI->getOpcode() == Instruction::And ||
 198          CondI->getOpcode() == Instruction::Or) &&
 199         isa<BranchInst>(BB->getTerminator()) &&
 200         ProcessBranchOnLogical(CondI, BB,
 201                                CondI->getOpcode() == Instruction::And))
 202       return true;
 203   }
 204
 205   // If we have "br (phi != 42)" and the phi node has any constant values as
 206   // operands, we can thread through this block.
 207   if (CmpInst *CondCmp = dyn_cast<CmpInst>(Condition))
 208     if (isa<PHINode>(CondCmp->getOperand(0)) &&
 209         isa<Constant>(CondCmp->getOperand(1)) &&
 210         ProcessBranchOnCompare(CondCmp, BB))
 211       return true;
 212
 213   return false;
 214 }
 215
 216 /// ProcessJumpOnPHI - We have a conditional branch of switch on a PHI node in
 217 /// the current block.  See if there are any simplifications we can do based on
 218 /// inputs to the phi node.
 219 ///
 220 bool JumpThreading::ProcessJumpOnPHI(PHINode *PN) {
 221   // See if the phi node has any constant values.  If so, we can determine where
 222   // the corresponding predecessor will branch.
 223   ConstantInt *PredCst = 0;
 224   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
 225     if ((PredCst = dyn_cast<ConstantInt>(PN->getIncomingValue(i))))
 226       break;
 227
 228   // If no incoming value has a constant, we don't know the destination of any
 229   // predecessors.
 230   if (PredCst == 0)
 231     return false;
 232
 233   // See if the cost of duplicating this block is low enough.
 234   BasicBlock *BB = PN->getParent();
 235   unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB);
 236   if (JumpThreadCost > Threshold) {
 237     DOUT << "  Not threading BB '" << BB->getNameStart()
 238          << "' - Cost is too high: " << JumpThreadCost << "\n";
 239     return false;
 240   }
 241
 242   // If so, we can actually do this threading.  Merge any common predecessors
 243   // that will act the same.
 244   BasicBlock *PredBB = FactorCommonPHIPreds(PN, PredCst);
 245
 246   // Next, figure out which successor we are threading to.
 247   BasicBlock *SuccBB;
 248   if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()))
 249     SuccBB = BI->getSuccessor(PredCst == ConstantInt::getFalse());
 250   else {
 251     SwitchInst *SI = cast<SwitchInst>(BB->getTerminator());
 252     SuccBB = SI->getSuccessor(SI->findCaseValue(PredCst));
 253   }
 254
 255   // If threading to the same block as we come from, we would infinite loop.
 256   if (SuccBB == BB) {
 257     DOUT << "  Not threading BB '" << BB->getNameStart()
 258          << "' - would thread to self!\n";
 259     return false;
 260   }
 261
 262   // And finally, do it!
 263   DOUT << "  Threading edge from '" << PredBB->getNameStart() << "' to '"
 264        << SuccBB->getNameStart() << "' with cost: " << JumpThreadCost
 265        << ", across block:\n    "
 266        << *BB << "\n";
 267
 268   ThreadEdge(BB, PredBB, SuccBB);
 269   ++NumThreads;
 270   return true;
 271 }
 272
 273 /// ProcessJumpOnLogicalPHI - PN's basic block contains a conditional branch
 274 /// whose condition is an AND/OR where one side is PN.  If PN has constant
 275 /// operands that permit us to evaluate the condition for some operand, thread
 276 /// through the block.  For example with:
 277 ///   br (and X, phi(Y, Z, false))
 278 /// the predecessor corresponding to the 'false' will always jump to the false
 279 /// destination of the branch.
 280 ///
 281 bool JumpThreading::ProcessBranchOnLogical(Value *V, BasicBlock *BB,
 282                                            bool isAnd) {
 283   // If this is a binary operator tree of the same AND/OR opcode, check the
 284   // LHS/RHS.
 285   if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V))
 286     if (isAnd && BO->getOpcode() == Instruction::And ||
 287         !isAnd && BO->getOpcode() == Instruction::Or) {
 288       if (ProcessBranchOnLogical(BO->getOperand(0), BB, isAnd))
 289         return true;
 290       if (ProcessBranchOnLogical(BO->getOperand(1), BB, isAnd))
 291         return true;
 292     }
 293
 294   // If this isn't a PHI node, we can't handle it.
 295   PHINode *PN = dyn_cast<PHINode>(V);
 296   if (!PN || PN->getParent() != BB) return false;
 297
 298   // We can only do the simplification for phi nodes of 'false' with AND or
 299   // 'true' with OR.  See if we have any entries in the phi for this.
 300   unsigned PredNo = ~0U;
 301   ConstantInt *PredCst = ConstantInt::get(Type::Int1Ty, !isAnd);
 302   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 303     if (PN->getIncomingValue(i) == PredCst) {
 304       PredNo = i;
 305       break;
 306     }
 307   }
 308
 309   // If no match, bail out.
 310   if (PredNo == ~0U)
 311     return false;
 312
 313   // See if the cost of duplicating this block is low enough.
 314   unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB);
 315   if (JumpThreadCost > Threshold) {
 316     DOUT << "  Not threading BB '" << BB->getNameStart()
 317          << "' - Cost is too high: " << JumpThreadCost << "\n";
 318     return false;
 319   }
 320
 321   // If so, we can actually do this threading.  Merge any common predecessors
 322   // that will act the same.
 323   BasicBlock *PredBB = FactorCommonPHIPreds(PN, PredCst);
 324
 325   // Next, figure out which successor we are threading to.  If this was an AND,
 326   // the constant must be FALSE, and we must be targeting the 'false' block.
 327   // If this is an OR, the constant must be TRUE, and we must be targeting the
 328   // 'true' block.
 329   BasicBlock *SuccBB = BB->getTerminator()->getSuccessor(isAnd);
 330
 331   // If threading to the same block as we come from, we would infinite loop.
 332   if (SuccBB == BB) {
 333     DOUT << "  Not threading BB '" << BB->getNameStart()
 334     << "' - would thread to self!\n";
 335     return false;
 336   }
 337
 338   // And finally, do it!
 339   DOUT << "  Threading edge through bool from '" << PredBB->getNameStart()
 340        << "' to '" << SuccBB->getNameStart() << "' with cost: "
 341        << JumpThreadCost << ", across block:\n    "
 342        << *BB << "\n";
 343
 344   ThreadEdge(BB, PredBB, SuccBB);
 345   ++NumThreads;
 346   return true;
 347 }
 348
 349 /// ProcessBranchOnCompare - We found a branch on a comparison between a phi
 350 /// node and a constant.  If the PHI node contains any constants as inputs, we
 351 /// can fold the compare for that edge and thread through it.
 352 bool JumpThreading::ProcessBranchOnCompare(CmpInst *Cmp, BasicBlock *BB) {
 353   PHINode *PN = cast<PHINode>(Cmp->getOperand(0));
 354   Constant *RHS = cast<Constant>(Cmp->getOperand(1));
 355
 356   // If the phi isn't in the current block, an incoming edge to this block
 357   // doesn't control the destination.
 358   if (PN->getParent() != BB)
 359     return false;
 360
 361   // We can do this simplification if any comparisons fold to true or false.
 362   // See if any do.
 363   Constant *PredCst = 0;
 364   bool TrueDirection = false;
 365   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 366     PredCst = dyn_cast<Constant>(PN->getIncomingValue(i));
 367     if (PredCst == 0) continue;
 368
 369     Constant *Res;
 370     if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cmp))
 371       Res = ConstantExpr::getICmp(ICI->getPredicate(), PredCst, RHS);
 372     else
 373       Res = ConstantExpr::getFCmp(cast<FCmpInst>(Cmp)->getPredicate(),
 374                                   PredCst, RHS);
 375     // If this folded to a constant expr, we can't do anything.
 376     if (ConstantInt *ResC = dyn_cast<ConstantInt>(Res)) {
 377       TrueDirection = ResC->getZExtValue();
 378       break;
 379     }
 380     // If this folded to undef, just go the false way.
 381     if (isa<UndefValue>(Res)) {
 382       TrueDirection = false;
 383       break;
 384     }
 385
 386     // Otherwise, we can't fold this input.
 387     PredCst = 0;
 388   }
 389
 390   // If no match, bail out.
 391   if (PredCst == 0)
 392     return false;
 393
 394   // See if the cost of duplicating this block is low enough.
 395   unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB);
 396   if (JumpThreadCost > Threshold) {
 397     DOUT << "  Not threading BB '" << BB->getNameStart()
 398          << "' - Cost is too high: " << JumpThreadCost << "\n";
 399     return false;
 400   }
 401
 402   // If so, we can actually do this threading.  Merge any common predecessors
 403   // that will act the same.
 404   BasicBlock *PredBB = FactorCommonPHIPreds(PN, PredCst);
 405
 406   // Next, get our successor.
 407   BasicBlock *SuccBB = BB->getTerminator()->getSuccessor(!TrueDirection);
 408
 409   // If threading to the same block as we come from, we would infinite loop.
 410   if (SuccBB == BB) {
 411     DOUT << "  Not threading BB '" << BB->getNameStart()
 412     << "' - would thread to self!\n";
 413     return false;
 414   }
 415
 416
 417   // And finally, do it!
 418   DOUT << "  Threading edge through bool from '" << PredBB->getNameStart()
 419        << "' to '" << SuccBB->getNameStart() << "' with cost: "
 420        << JumpThreadCost << ", across block:\n    "
 421        << *BB << "\n";
 422
 423   ThreadEdge(BB, PredBB, SuccBB);
 424   ++NumThreads;
 425   return true;
 426 }
 427
 428
 429 /// ThreadEdge - We have decided that it is safe and profitable to thread an
 430 /// edge from PredBB to SuccBB across BB.  Transform the IR to reflect this
 431 /// change.
 432 void JumpThreading::ThreadEdge(BasicBlock *BB, BasicBlock *PredBB,
 433                                BasicBlock *SuccBB) {
 434
 435   // Jump Threading can not update SSA properties correctly if the values
 436   // defined in the duplicated block are used outside of the block itself.  For
 437   // this reason, we spill all values that are used outside of BB to the stack.
 438   for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) {
 439     if (!I->isUsedOutsideOfBlock(BB))
 440       continue;
 441
 442     // We found a use of I outside of BB.  Create a new stack slot to
 443     // break this inter-block usage pattern.
 444     if (!isa<StructType>(I->getType())) {
 445       DemoteRegToStack(*I);
 446       continue;
 447     }
 448
 449     // Alternatively, I must be a call or invoke that returns multiple retvals.
 450     // We can't use 'DemoteRegToStack' because that will create loads and
 451     // stores of aggregates which is not valid yet.  If I is a call, we can just
 452     // pull all the getresult instructions up to this block.  If I is an invoke,
 453     // we are out of luck.
 454     BasicBlock::iterator IP = I; ++IP;
 455     for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
 456          UI != E; ++UI)
 457       cast<GetResultInst>(UI)->moveBefore(IP);
 458   }
 459
 460   // We are going to have to map operands from the original BB block to the new
 461   // copy of the block 'NewBB'.  If there are PHI nodes in BB, evaluate them to
 462   // account for entry from PredBB.
 463   DenseMap<Instruction*, Value*> ValueMapping;
 464
 465   BasicBlock *NewBB =
 466     BasicBlock::Create(BB->getName()+".thread", BB->getParent(), BB);
 467   NewBB->moveAfter(PredBB);
 468
 469   BasicBlock::iterator BI = BB->begin();
 470   for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
 471     ValueMapping[PN] = PN->getIncomingValueForBlock(PredBB);
 472
 473   // Clone the non-phi instructions of BB into NewBB, keeping track of the
 474   // mapping and using it to remap operands in the cloned instructions.
 475   for (; !isa<TerminatorInst>(BI); ++BI) {
 476     Instruction *New = BI->clone();
 477     New->setName(BI->getNameStart());
 478     NewBB->getInstList().push_back(New);
 479     ValueMapping[BI] = New;
 480
 481     // Remap operands to patch up intra-block references.
 482     for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
 483       if (Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i)))
 484         if (Value *Remapped = ValueMapping[Inst])
 485           New->setOperand(i, Remapped);
 486   }
 487
 488   // We didn't copy the terminator from BB over to NewBB, because there is now
 489   // an unconditional jump to SuccBB.  Insert the unconditional jump.
 490   BranchInst::Create(SuccBB, NewBB);
 491
 492   // Check to see if SuccBB has PHI nodes. If so, we need to add entries to the
 493   // PHI nodes for NewBB now.
 494   for (BasicBlock::iterator PNI = SuccBB->begin(); isa<PHINode>(PNI); ++PNI) {
 495     PHINode *PN = cast<PHINode>(PNI);
 496     // Ok, we have a PHI node.  Figure out what the incoming value was for the
 497     // DestBlock.
 498     Value *IV = PN->getIncomingValueForBlock(BB);
 499
 500     // Remap the value if necessary.
 501     if (Instruction *Inst = dyn_cast<Instruction>(IV))
 502       if (Value *MappedIV = ValueMapping[Inst])
 503         IV = MappedIV;
 504     PN->addIncoming(IV, NewBB);
 505   }
 506
 507   // Finally, NewBB is good to go.  Update the terminator of PredBB to jump to
 508   // NewBB instead of BB.  This eliminates predecessors from BB, which requires
 509   // us to simplify any PHI nodes in BB.
 510   TerminatorInst *PredTerm = PredBB->getTerminator();
 511   for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i)
 512     if (PredTerm->getSuccessor(i) == BB) {
 513       BB->removePredecessor(PredBB);
 514       PredTerm->setSuccessor(i, NewBB);
 515     }
 516 }