JumpThreading.cpp revision 844731a7f1909f55935e3514c9e713a62d67662e
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" 25using namespace llvm; 26 27STATISTIC(NumThreads, "Number of jumps threaded"); 28STATISTIC(NumFolds, "Number of terminators folded"); 29 30static cl::opt<unsigned> 31Threshold("jump-threading-threshold", 32 cl::desc("Max block size to duplicate for jump threading"), 33 cl::init(6), cl::Hidden); 34 35namespace { 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 68char JumpThreading::ID = 0; 69static RegisterPass<JumpThreading> 70X("jump-threading", "Jump Threading"); 71 72// Public interface to the Jump Threading pass 73FunctionPass *llvm::createJumpThreadingPass() { return new JumpThreading(); } 74 75/// runOnFunction - Top level algorithm. 76/// 77bool 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/// 99BasicBlock *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. 118static 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. 160bool JumpThreading::ThreadBlock(BasicBlock *BB) { 161 // See if this block ends with a branch of 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/// 220bool 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/// 281bool 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. 352bool 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. 432void 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} 517