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 #include "llvm/Transforms/Scalar/JumpThreading.h" 15 #include "llvm/Transforms/Scalar.h" 16 #include "llvm/ADT/DenseMap.h" 17 #include "llvm/ADT/DenseSet.h" 18 #include "llvm/ADT/STLExtras.h" 19 #include "llvm/ADT/Statistic.h" 20 #include "llvm/Analysis/GlobalsModRef.h" 21 #include "llvm/Analysis/CFG.h" 22 #include "llvm/Analysis/BlockFrequencyInfoImpl.h" 23 #include "llvm/Analysis/ConstantFolding.h" 24 #include "llvm/Analysis/InstructionSimplify.h" 25 #include "llvm/Analysis/Loads.h" 26 #include "llvm/Analysis/LoopInfo.h" 27 #include "llvm/Analysis/ValueTracking.h" 28 #include "llvm/IR/DataLayout.h" 29 #include "llvm/IR/IntrinsicInst.h" 30 #include "llvm/IR/LLVMContext.h" 31 #include "llvm/IR/MDBuilder.h" 32 #include "llvm/IR/Metadata.h" 33 #include "llvm/Pass.h" 34 #include "llvm/Support/CommandLine.h" 35 #include "llvm/Support/Debug.h" 36 #include "llvm/Support/raw_ostream.h" 37 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 38 #include "llvm/Transforms/Utils/Local.h" 39 #include "llvm/Transforms/Utils/SSAUpdater.h" 40 #include <algorithm> 41 #include <memory> 42 using namespace llvm; 43 using namespace jumpthreading; 44 45 #define DEBUG_TYPE "jump-threading" 46 47 STATISTIC(NumThreads, "Number of jumps threaded"); 48 STATISTIC(NumFolds, "Number of terminators folded"); 49 STATISTIC(NumDupes, "Number of branch blocks duplicated to eliminate phi"); 50 51 static cl::opt<unsigned> 52 BBDuplicateThreshold("jump-threading-threshold", 53 cl::desc("Max block size to duplicate for jump threading"), 54 cl::init(6), cl::Hidden); 55 56 static cl::opt<unsigned> 57 ImplicationSearchThreshold( 58 "jump-threading-implication-search-threshold", 59 cl::desc("The number of predecessors to search for a stronger " 60 "condition to use to thread over a weaker condition"), 61 cl::init(3), cl::Hidden); 62 63 namespace { 64 /// This pass performs 'jump threading', which looks at blocks that have 65 /// multiple predecessors and multiple successors. If one or more of the 66 /// predecessors of the block can be proven to always jump to one of the 67 /// successors, we forward the edge from the predecessor to the successor by 68 /// duplicating the contents of this block. 69 /// 70 /// An example of when this can occur is code like this: 71 /// 72 /// if () { ... 73 /// X = 4; 74 /// } 75 /// if (X < 3) { 76 /// 77 /// In this case, the unconditional branch at the end of the first if can be 78 /// revectored to the false side of the second if. 79 /// 80 class JumpThreading : public FunctionPass { 81 JumpThreadingPass Impl; 82 83 public: 84 static char ID; // Pass identification 85 JumpThreading(int T = -1) : FunctionPass(ID), Impl(T) { 86 initializeJumpThreadingPass(*PassRegistry::getPassRegistry()); 87 } 88 89 bool runOnFunction(Function &F) override; 90 91 void getAnalysisUsage(AnalysisUsage &AU) const override { 92 AU.addRequired<LazyValueInfoWrapperPass>(); 93 AU.addPreserved<LazyValueInfoWrapperPass>(); 94 AU.addPreserved<GlobalsAAWrapperPass>(); 95 AU.addRequired<TargetLibraryInfoWrapperPass>(); 96 } 97 98 void releaseMemory() override { Impl.releaseMemory(); } 99 }; 100 } 101 102 char JumpThreading::ID = 0; 103 INITIALIZE_PASS_BEGIN(JumpThreading, "jump-threading", 104 "Jump Threading", false, false) 105 INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass) 106 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 107 INITIALIZE_PASS_END(JumpThreading, "jump-threading", 108 "Jump Threading", false, false) 109 110 // Public interface to the Jump Threading pass 111 FunctionPass *llvm::createJumpThreadingPass(int Threshold) { return new JumpThreading(Threshold); } 112 113 JumpThreadingPass::JumpThreadingPass(int T) { 114 BBDupThreshold = (T == -1) ? BBDuplicateThreshold : unsigned(T); 115 } 116 117 /// runOnFunction - Top level algorithm. 118 /// 119 bool JumpThreading::runOnFunction(Function &F) { 120 if (skipFunction(F)) 121 return false; 122 auto TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(); 123 auto LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI(); 124 std::unique_ptr<BlockFrequencyInfo> BFI; 125 std::unique_ptr<BranchProbabilityInfo> BPI; 126 bool HasProfileData = F.getEntryCount().hasValue(); 127 if (HasProfileData) { 128 LoopInfo LI{DominatorTree(F)}; 129 BPI.reset(new BranchProbabilityInfo(F, LI)); 130 BFI.reset(new BlockFrequencyInfo(F, *BPI, LI)); 131 } 132 return Impl.runImpl(F, TLI, LVI, HasProfileData, std::move(BFI), 133 std::move(BPI)); 134 } 135 136 PreservedAnalyses JumpThreadingPass::run(Function &F, 137 AnalysisManager<Function> &AM) { 138 139 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F); 140 auto &LVI = AM.getResult<LazyValueAnalysis>(F); 141 std::unique_ptr<BlockFrequencyInfo> BFI; 142 std::unique_ptr<BranchProbabilityInfo> BPI; 143 bool HasProfileData = F.getEntryCount().hasValue(); 144 if (HasProfileData) { 145 LoopInfo LI{DominatorTree(F)}; 146 BPI.reset(new BranchProbabilityInfo(F, LI)); 147 BFI.reset(new BlockFrequencyInfo(F, *BPI, LI)); 148 } 149 bool Changed = 150 runImpl(F, &TLI, &LVI, HasProfileData, std::move(BFI), std::move(BPI)); 151 152 // FIXME: We need to invalidate LVI to avoid PR28400. Is there a better 153 // solution? 154 AM.invalidate<LazyValueAnalysis>(F); 155 156 if (!Changed) 157 return PreservedAnalyses::all(); 158 PreservedAnalyses PA; 159 PA.preserve<GlobalsAA>(); 160 return PA; 161 } 162 163 bool JumpThreadingPass::runImpl(Function &F, TargetLibraryInfo *TLI_, 164 LazyValueInfo *LVI_, bool HasProfileData_, 165 std::unique_ptr<BlockFrequencyInfo> BFI_, 166 std::unique_ptr<BranchProbabilityInfo> BPI_) { 167 168 DEBUG(dbgs() << "Jump threading on function '" << F.getName() << "'\n"); 169 TLI = TLI_; 170 LVI = LVI_; 171 BFI.reset(); 172 BPI.reset(); 173 // When profile data is available, we need to update edge weights after 174 // successful jump threading, which requires both BPI and BFI being available. 175 HasProfileData = HasProfileData_; 176 if (HasProfileData) { 177 BPI = std::move(BPI_); 178 BFI = std::move(BFI_); 179 } 180 181 // Remove unreachable blocks from function as they may result in infinite 182 // loop. We do threading if we found something profitable. Jump threading a 183 // branch can create other opportunities. If these opportunities form a cycle 184 // i.e. if any jump threading is undoing previous threading in the path, then 185 // we will loop forever. We take care of this issue by not jump threading for 186 // back edges. This works for normal cases but not for unreachable blocks as 187 // they may have cycle with no back edge. 188 bool EverChanged = false; 189 EverChanged |= removeUnreachableBlocks(F, LVI); 190 191 FindLoopHeaders(F); 192 193 bool Changed; 194 do { 195 Changed = false; 196 for (Function::iterator I = F.begin(), E = F.end(); I != E;) { 197 BasicBlock *BB = &*I; 198 // Thread all of the branches we can over this block. 199 while (ProcessBlock(BB)) 200 Changed = true; 201 202 ++I; 203 204 // If the block is trivially dead, zap it. This eliminates the successor 205 // edges which simplifies the CFG. 206 if (pred_empty(BB) && 207 BB != &BB->getParent()->getEntryBlock()) { 208 DEBUG(dbgs() << " JT: Deleting dead block '" << BB->getName() 209 << "' with terminator: " << *BB->getTerminator() << '\n'); 210 LoopHeaders.erase(BB); 211 LVI->eraseBlock(BB); 212 DeleteDeadBlock(BB); 213 Changed = true; 214 continue; 215 } 216 217 BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 218 219 // Can't thread an unconditional jump, but if the block is "almost 220 // empty", we can replace uses of it with uses of the successor and make 221 // this dead. 222 // We should not eliminate the loop header either, because eliminating 223 // a loop header might later prevent LoopSimplify from transforming nested 224 // loops into simplified form. 225 if (BI && BI->isUnconditional() && 226 BB != &BB->getParent()->getEntryBlock() && 227 // If the terminator is the only non-phi instruction, try to nuke it. 228 BB->getFirstNonPHIOrDbg()->isTerminator() && !LoopHeaders.count(BB)) { 229 // Since TryToSimplifyUncondBranchFromEmptyBlock may delete the 230 // block, we have to make sure it isn't in the LoopHeaders set. We 231 // reinsert afterward if needed. 232 bool ErasedFromLoopHeaders = LoopHeaders.erase(BB); 233 BasicBlock *Succ = BI->getSuccessor(0); 234 235 // FIXME: It is always conservatively correct to drop the info 236 // for a block even if it doesn't get erased. This isn't totally 237 // awesome, but it allows us to use AssertingVH to prevent nasty 238 // dangling pointer issues within LazyValueInfo. 239 LVI->eraseBlock(BB); 240 if (TryToSimplifyUncondBranchFromEmptyBlock(BB)) { 241 Changed = true; 242 // If we deleted BB and BB was the header of a loop, then the 243 // successor is now the header of the loop. 244 BB = Succ; 245 } 246 247 if (ErasedFromLoopHeaders) 248 LoopHeaders.insert(BB); 249 } 250 } 251 EverChanged |= Changed; 252 } while (Changed); 253 254 LoopHeaders.clear(); 255 return EverChanged; 256 } 257 258 /// getJumpThreadDuplicationCost - Return the cost of duplicating this block to 259 /// thread across it. Stop scanning the block when passing the threshold. 260 static unsigned getJumpThreadDuplicationCost(const BasicBlock *BB, 261 unsigned Threshold) { 262 /// Ignore PHI nodes, these will be flattened when duplication happens. 263 BasicBlock::const_iterator I(BB->getFirstNonPHI()); 264 265 // FIXME: THREADING will delete values that are just used to compute the 266 // branch, so they shouldn't count against the duplication cost. 267 268 unsigned Bonus = 0; 269 const TerminatorInst *BBTerm = BB->getTerminator(); 270 // Threading through a switch statement is particularly profitable. If this 271 // block ends in a switch, decrease its cost to make it more likely to happen. 272 if (isa<SwitchInst>(BBTerm)) 273 Bonus = 6; 274 275 // The same holds for indirect branches, but slightly more so. 276 if (isa<IndirectBrInst>(BBTerm)) 277 Bonus = 8; 278 279 // Bump the threshold up so the early exit from the loop doesn't skip the 280 // terminator-based Size adjustment at the end. 281 Threshold += Bonus; 282 283 // Sum up the cost of each instruction until we get to the terminator. Don't 284 // include the terminator because the copy won't include it. 285 unsigned Size = 0; 286 for (; !isa<TerminatorInst>(I); ++I) { 287 288 // Stop scanning the block if we've reached the threshold. 289 if (Size > Threshold) 290 return Size; 291 292 // Debugger intrinsics don't incur code size. 293 if (isa<DbgInfoIntrinsic>(I)) continue; 294 295 // If this is a pointer->pointer bitcast, it is free. 296 if (isa<BitCastInst>(I) && I->getType()->isPointerTy()) 297 continue; 298 299 // Bail out if this instruction gives back a token type, it is not possible 300 // to duplicate it if it is used outside this BB. 301 if (I->getType()->isTokenTy() && I->isUsedOutsideOfBlock(BB)) 302 return ~0U; 303 304 // All other instructions count for at least one unit. 305 ++Size; 306 307 // Calls are more expensive. If they are non-intrinsic calls, we model them 308 // as having cost of 4. If they are a non-vector intrinsic, we model them 309 // as having cost of 2 total, and if they are a vector intrinsic, we model 310 // them as having cost 1. 311 if (const CallInst *CI = dyn_cast<CallInst>(I)) { 312 if (CI->cannotDuplicate() || CI->isConvergent()) 313 // Blocks with NoDuplicate are modelled as having infinite cost, so they 314 // are never duplicated. 315 return ~0U; 316 else if (!isa<IntrinsicInst>(CI)) 317 Size += 3; 318 else if (!CI->getType()->isVectorTy()) 319 Size += 1; 320 } 321 } 322 323 return Size > Bonus ? Size - Bonus : 0; 324 } 325 326 /// FindLoopHeaders - We do not want jump threading to turn proper loop 327 /// structures into irreducible loops. Doing this breaks up the loop nesting 328 /// hierarchy and pessimizes later transformations. To prevent this from 329 /// happening, we first have to find the loop headers. Here we approximate this 330 /// by finding targets of backedges in the CFG. 331 /// 332 /// Note that there definitely are cases when we want to allow threading of 333 /// edges across a loop header. For example, threading a jump from outside the 334 /// loop (the preheader) to an exit block of the loop is definitely profitable. 335 /// It is also almost always profitable to thread backedges from within the loop 336 /// to exit blocks, and is often profitable to thread backedges to other blocks 337 /// within the loop (forming a nested loop). This simple analysis is not rich 338 /// enough to track all of these properties and keep it up-to-date as the CFG 339 /// mutates, so we don't allow any of these transformations. 340 /// 341 void JumpThreadingPass::FindLoopHeaders(Function &F) { 342 SmallVector<std::pair<const BasicBlock*,const BasicBlock*>, 32> Edges; 343 FindFunctionBackedges(F, Edges); 344 345 for (const auto &Edge : Edges) 346 LoopHeaders.insert(Edge.second); 347 } 348 349 /// getKnownConstant - Helper method to determine if we can thread over a 350 /// terminator with the given value as its condition, and if so what value to 351 /// use for that. What kind of value this is depends on whether we want an 352 /// integer or a block address, but an undef is always accepted. 353 /// Returns null if Val is null or not an appropriate constant. 354 static Constant *getKnownConstant(Value *Val, ConstantPreference Preference) { 355 if (!Val) 356 return nullptr; 357 358 // Undef is "known" enough. 359 if (UndefValue *U = dyn_cast<UndefValue>(Val)) 360 return U; 361 362 if (Preference == WantBlockAddress) 363 return dyn_cast<BlockAddress>(Val->stripPointerCasts()); 364 365 return dyn_cast<ConstantInt>(Val); 366 } 367 368 /// ComputeValueKnownInPredecessors - Given a basic block BB and a value V, see 369 /// if we can infer that the value is a known ConstantInt/BlockAddress or undef 370 /// in any of our predecessors. If so, return the known list of value and pred 371 /// BB in the result vector. 372 /// 373 /// This returns true if there were any known values. 374 /// 375 bool JumpThreadingPass::ComputeValueKnownInPredecessors( 376 Value *V, BasicBlock *BB, PredValueInfo &Result, 377 ConstantPreference Preference, Instruction *CxtI) { 378 // This method walks up use-def chains recursively. Because of this, we could 379 // get into an infinite loop going around loops in the use-def chain. To 380 // prevent this, keep track of what (value, block) pairs we've already visited 381 // and terminate the search if we loop back to them 382 if (!RecursionSet.insert(std::make_pair(V, BB)).second) 383 return false; 384 385 // An RAII help to remove this pair from the recursion set once the recursion 386 // stack pops back out again. 387 RecursionSetRemover remover(RecursionSet, std::make_pair(V, BB)); 388 389 // If V is a constant, then it is known in all predecessors. 390 if (Constant *KC = getKnownConstant(V, Preference)) { 391 for (BasicBlock *Pred : predecessors(BB)) 392 Result.push_back(std::make_pair(KC, Pred)); 393 394 return !Result.empty(); 395 } 396 397 // If V is a non-instruction value, or an instruction in a different block, 398 // then it can't be derived from a PHI. 399 Instruction *I = dyn_cast<Instruction>(V); 400 if (!I || I->getParent() != BB) { 401 402 // Okay, if this is a live-in value, see if it has a known value at the end 403 // of any of our predecessors. 404 // 405 // FIXME: This should be an edge property, not a block end property. 406 /// TODO: Per PR2563, we could infer value range information about a 407 /// predecessor based on its terminator. 408 // 409 // FIXME: change this to use the more-rich 'getPredicateOnEdge' method if 410 // "I" is a non-local compare-with-a-constant instruction. This would be 411 // able to handle value inequalities better, for example if the compare is 412 // "X < 4" and "X < 3" is known true but "X < 4" itself is not available. 413 // Perhaps getConstantOnEdge should be smart enough to do this? 414 415 for (BasicBlock *P : predecessors(BB)) { 416 // If the value is known by LazyValueInfo to be a constant in a 417 // predecessor, use that information to try to thread this block. 418 Constant *PredCst = LVI->getConstantOnEdge(V, P, BB, CxtI); 419 if (Constant *KC = getKnownConstant(PredCst, Preference)) 420 Result.push_back(std::make_pair(KC, P)); 421 } 422 423 return !Result.empty(); 424 } 425 426 /// If I is a PHI node, then we know the incoming values for any constants. 427 if (PHINode *PN = dyn_cast<PHINode>(I)) { 428 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 429 Value *InVal = PN->getIncomingValue(i); 430 if (Constant *KC = getKnownConstant(InVal, Preference)) { 431 Result.push_back(std::make_pair(KC, PN->getIncomingBlock(i))); 432 } else { 433 Constant *CI = LVI->getConstantOnEdge(InVal, 434 PN->getIncomingBlock(i), 435 BB, CxtI); 436 if (Constant *KC = getKnownConstant(CI, Preference)) 437 Result.push_back(std::make_pair(KC, PN->getIncomingBlock(i))); 438 } 439 } 440 441 return !Result.empty(); 442 } 443 444 // Handle Cast instructions. Only see through Cast when the source operand is 445 // PHI or Cmp and the source type is i1 to save the compilation time. 446 if (CastInst *CI = dyn_cast<CastInst>(I)) { 447 Value *Source = CI->getOperand(0); 448 if (!Source->getType()->isIntegerTy(1)) 449 return false; 450 if (!isa<PHINode>(Source) && !isa<CmpInst>(Source)) 451 return false; 452 ComputeValueKnownInPredecessors(Source, BB, Result, Preference, CxtI); 453 if (Result.empty()) 454 return false; 455 456 // Convert the known values. 457 for (auto &R : Result) 458 R.first = ConstantExpr::getCast(CI->getOpcode(), R.first, CI->getType()); 459 460 return true; 461 } 462 463 PredValueInfoTy LHSVals, RHSVals; 464 465 // Handle some boolean conditions. 466 if (I->getType()->getPrimitiveSizeInBits() == 1) { 467 assert(Preference == WantInteger && "One-bit non-integer type?"); 468 // X | true -> true 469 // X & false -> false 470 if (I->getOpcode() == Instruction::Or || 471 I->getOpcode() == Instruction::And) { 472 ComputeValueKnownInPredecessors(I->getOperand(0), BB, LHSVals, 473 WantInteger, CxtI); 474 ComputeValueKnownInPredecessors(I->getOperand(1), BB, RHSVals, 475 WantInteger, CxtI); 476 477 if (LHSVals.empty() && RHSVals.empty()) 478 return false; 479 480 ConstantInt *InterestingVal; 481 if (I->getOpcode() == Instruction::Or) 482 InterestingVal = ConstantInt::getTrue(I->getContext()); 483 else 484 InterestingVal = ConstantInt::getFalse(I->getContext()); 485 486 SmallPtrSet<BasicBlock*, 4> LHSKnownBBs; 487 488 // Scan for the sentinel. If we find an undef, force it to the 489 // interesting value: x|undef -> true and x&undef -> false. 490 for (const auto &LHSVal : LHSVals) 491 if (LHSVal.first == InterestingVal || isa<UndefValue>(LHSVal.first)) { 492 Result.emplace_back(InterestingVal, LHSVal.second); 493 LHSKnownBBs.insert(LHSVal.second); 494 } 495 for (const auto &RHSVal : RHSVals) 496 if (RHSVal.first == InterestingVal || isa<UndefValue>(RHSVal.first)) { 497 // If we already inferred a value for this block on the LHS, don't 498 // re-add it. 499 if (!LHSKnownBBs.count(RHSVal.second)) 500 Result.emplace_back(InterestingVal, RHSVal.second); 501 } 502 503 return !Result.empty(); 504 } 505 506 // Handle the NOT form of XOR. 507 if (I->getOpcode() == Instruction::Xor && 508 isa<ConstantInt>(I->getOperand(1)) && 509 cast<ConstantInt>(I->getOperand(1))->isOne()) { 510 ComputeValueKnownInPredecessors(I->getOperand(0), BB, Result, 511 WantInteger, CxtI); 512 if (Result.empty()) 513 return false; 514 515 // Invert the known values. 516 for (auto &R : Result) 517 R.first = ConstantExpr::getNot(R.first); 518 519 return true; 520 } 521 522 // Try to simplify some other binary operator values. 523 } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) { 524 assert(Preference != WantBlockAddress 525 && "A binary operator creating a block address?"); 526 if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1))) { 527 PredValueInfoTy LHSVals; 528 ComputeValueKnownInPredecessors(BO->getOperand(0), BB, LHSVals, 529 WantInteger, CxtI); 530 531 // Try to use constant folding to simplify the binary operator. 532 for (const auto &LHSVal : LHSVals) { 533 Constant *V = LHSVal.first; 534 Constant *Folded = ConstantExpr::get(BO->getOpcode(), V, CI); 535 536 if (Constant *KC = getKnownConstant(Folded, WantInteger)) 537 Result.push_back(std::make_pair(KC, LHSVal.second)); 538 } 539 } 540 541 return !Result.empty(); 542 } 543 544 // Handle compare with phi operand, where the PHI is defined in this block. 545 if (CmpInst *Cmp = dyn_cast<CmpInst>(I)) { 546 assert(Preference == WantInteger && "Compares only produce integers"); 547 PHINode *PN = dyn_cast<PHINode>(Cmp->getOperand(0)); 548 if (PN && PN->getParent() == BB) { 549 const DataLayout &DL = PN->getModule()->getDataLayout(); 550 // We can do this simplification if any comparisons fold to true or false. 551 // See if any do. 552 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 553 BasicBlock *PredBB = PN->getIncomingBlock(i); 554 Value *LHS = PN->getIncomingValue(i); 555 Value *RHS = Cmp->getOperand(1)->DoPHITranslation(BB, PredBB); 556 557 Value *Res = SimplifyCmpInst(Cmp->getPredicate(), LHS, RHS, DL); 558 if (!Res) { 559 if (!isa<Constant>(RHS)) 560 continue; 561 562 LazyValueInfo::Tristate 563 ResT = LVI->getPredicateOnEdge(Cmp->getPredicate(), LHS, 564 cast<Constant>(RHS), PredBB, BB, 565 CxtI ? CxtI : Cmp); 566 if (ResT == LazyValueInfo::Unknown) 567 continue; 568 Res = ConstantInt::get(Type::getInt1Ty(LHS->getContext()), ResT); 569 } 570 571 if (Constant *KC = getKnownConstant(Res, WantInteger)) 572 Result.push_back(std::make_pair(KC, PredBB)); 573 } 574 575 return !Result.empty(); 576 } 577 578 // If comparing a live-in value against a constant, see if we know the 579 // live-in value on any predecessors. 580 if (isa<Constant>(Cmp->getOperand(1)) && Cmp->getType()->isIntegerTy()) { 581 if (!isa<Instruction>(Cmp->getOperand(0)) || 582 cast<Instruction>(Cmp->getOperand(0))->getParent() != BB) { 583 Constant *RHSCst = cast<Constant>(Cmp->getOperand(1)); 584 585 for (BasicBlock *P : predecessors(BB)) { 586 // If the value is known by LazyValueInfo to be a constant in a 587 // predecessor, use that information to try to thread this block. 588 LazyValueInfo::Tristate Res = 589 LVI->getPredicateOnEdge(Cmp->getPredicate(), Cmp->getOperand(0), 590 RHSCst, P, BB, CxtI ? CxtI : Cmp); 591 if (Res == LazyValueInfo::Unknown) 592 continue; 593 594 Constant *ResC = ConstantInt::get(Cmp->getType(), Res); 595 Result.push_back(std::make_pair(ResC, P)); 596 } 597 598 return !Result.empty(); 599 } 600 601 // Try to find a constant value for the LHS of a comparison, 602 // and evaluate it statically if we can. 603 if (Constant *CmpConst = dyn_cast<Constant>(Cmp->getOperand(1))) { 604 PredValueInfoTy LHSVals; 605 ComputeValueKnownInPredecessors(I->getOperand(0), BB, LHSVals, 606 WantInteger, CxtI); 607 608 for (const auto &LHSVal : LHSVals) { 609 Constant *V = LHSVal.first; 610 Constant *Folded = ConstantExpr::getCompare(Cmp->getPredicate(), 611 V, CmpConst); 612 if (Constant *KC = getKnownConstant(Folded, WantInteger)) 613 Result.push_back(std::make_pair(KC, LHSVal.second)); 614 } 615 616 return !Result.empty(); 617 } 618 } 619 } 620 621 if (SelectInst *SI = dyn_cast<SelectInst>(I)) { 622 // Handle select instructions where at least one operand is a known constant 623 // and we can figure out the condition value for any predecessor block. 624 Constant *TrueVal = getKnownConstant(SI->getTrueValue(), Preference); 625 Constant *FalseVal = getKnownConstant(SI->getFalseValue(), Preference); 626 PredValueInfoTy Conds; 627 if ((TrueVal || FalseVal) && 628 ComputeValueKnownInPredecessors(SI->getCondition(), BB, Conds, 629 WantInteger, CxtI)) { 630 for (auto &C : Conds) { 631 Constant *Cond = C.first; 632 633 // Figure out what value to use for the condition. 634 bool KnownCond; 635 if (ConstantInt *CI = dyn_cast<ConstantInt>(Cond)) { 636 // A known boolean. 637 KnownCond = CI->isOne(); 638 } else { 639 assert(isa<UndefValue>(Cond) && "Unexpected condition value"); 640 // Either operand will do, so be sure to pick the one that's a known 641 // constant. 642 // FIXME: Do this more cleverly if both values are known constants? 643 KnownCond = (TrueVal != nullptr); 644 } 645 646 // See if the select has a known constant value for this predecessor. 647 if (Constant *Val = KnownCond ? TrueVal : FalseVal) 648 Result.push_back(std::make_pair(Val, C.second)); 649 } 650 651 return !Result.empty(); 652 } 653 } 654 655 // If all else fails, see if LVI can figure out a constant value for us. 656 Constant *CI = LVI->getConstant(V, BB, CxtI); 657 if (Constant *KC = getKnownConstant(CI, Preference)) { 658 for (BasicBlock *Pred : predecessors(BB)) 659 Result.push_back(std::make_pair(KC, Pred)); 660 } 661 662 return !Result.empty(); 663 } 664 665 666 667 /// GetBestDestForBranchOnUndef - If we determine that the specified block ends 668 /// in an undefined jump, decide which block is best to revector to. 669 /// 670 /// Since we can pick an arbitrary destination, we pick the successor with the 671 /// fewest predecessors. This should reduce the in-degree of the others. 672 /// 673 static unsigned GetBestDestForJumpOnUndef(BasicBlock *BB) { 674 TerminatorInst *BBTerm = BB->getTerminator(); 675 unsigned MinSucc = 0; 676 BasicBlock *TestBB = BBTerm->getSuccessor(MinSucc); 677 // Compute the successor with the minimum number of predecessors. 678 unsigned MinNumPreds = std::distance(pred_begin(TestBB), pred_end(TestBB)); 679 for (unsigned i = 1, e = BBTerm->getNumSuccessors(); i != e; ++i) { 680 TestBB = BBTerm->getSuccessor(i); 681 unsigned NumPreds = std::distance(pred_begin(TestBB), pred_end(TestBB)); 682 if (NumPreds < MinNumPreds) { 683 MinSucc = i; 684 MinNumPreds = NumPreds; 685 } 686 } 687 688 return MinSucc; 689 } 690 691 static bool hasAddressTakenAndUsed(BasicBlock *BB) { 692 if (!BB->hasAddressTaken()) return false; 693 694 // If the block has its address taken, it may be a tree of dead constants 695 // hanging off of it. These shouldn't keep the block alive. 696 BlockAddress *BA = BlockAddress::get(BB); 697 BA->removeDeadConstantUsers(); 698 return !BA->use_empty(); 699 } 700 701 /// ProcessBlock - If there are any predecessors whose control can be threaded 702 /// through to a successor, transform them now. 703 bool JumpThreadingPass::ProcessBlock(BasicBlock *BB) { 704 // If the block is trivially dead, just return and let the caller nuke it. 705 // This simplifies other transformations. 706 if (pred_empty(BB) && 707 BB != &BB->getParent()->getEntryBlock()) 708 return false; 709 710 // If this block has a single predecessor, and if that pred has a single 711 // successor, merge the blocks. This encourages recursive jump threading 712 // because now the condition in this block can be threaded through 713 // predecessors of our predecessor block. 714 if (BasicBlock *SinglePred = BB->getSinglePredecessor()) { 715 const TerminatorInst *TI = SinglePred->getTerminator(); 716 if (!TI->isExceptional() && TI->getNumSuccessors() == 1 && 717 SinglePred != BB && !hasAddressTakenAndUsed(BB)) { 718 // If SinglePred was a loop header, BB becomes one. 719 if (LoopHeaders.erase(SinglePred)) 720 LoopHeaders.insert(BB); 721 722 LVI->eraseBlock(SinglePred); 723 MergeBasicBlockIntoOnlyPred(BB); 724 725 return true; 726 } 727 } 728 729 if (TryToUnfoldSelectInCurrBB(BB)) 730 return true; 731 732 // What kind of constant we're looking for. 733 ConstantPreference Preference = WantInteger; 734 735 // Look to see if the terminator is a conditional branch, switch or indirect 736 // branch, if not we can't thread it. 737 Value *Condition; 738 Instruction *Terminator = BB->getTerminator(); 739 if (BranchInst *BI = dyn_cast<BranchInst>(Terminator)) { 740 // Can't thread an unconditional jump. 741 if (BI->isUnconditional()) return false; 742 Condition = BI->getCondition(); 743 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(Terminator)) { 744 Condition = SI->getCondition(); 745 } else if (IndirectBrInst *IB = dyn_cast<IndirectBrInst>(Terminator)) { 746 // Can't thread indirect branch with no successors. 747 if (IB->getNumSuccessors() == 0) return false; 748 Condition = IB->getAddress()->stripPointerCasts(); 749 Preference = WantBlockAddress; 750 } else { 751 return false; // Must be an invoke. 752 } 753 754 // Run constant folding to see if we can reduce the condition to a simple 755 // constant. 756 if (Instruction *I = dyn_cast<Instruction>(Condition)) { 757 Value *SimpleVal = 758 ConstantFoldInstruction(I, BB->getModule()->getDataLayout(), TLI); 759 if (SimpleVal) { 760 I->replaceAllUsesWith(SimpleVal); 761 I->eraseFromParent(); 762 Condition = SimpleVal; 763 } 764 } 765 766 // If the terminator is branching on an undef, we can pick any of the 767 // successors to branch to. Let GetBestDestForJumpOnUndef decide. 768 if (isa<UndefValue>(Condition)) { 769 unsigned BestSucc = GetBestDestForJumpOnUndef(BB); 770 771 // Fold the branch/switch. 772 TerminatorInst *BBTerm = BB->getTerminator(); 773 for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) { 774 if (i == BestSucc) continue; 775 BBTerm->getSuccessor(i)->removePredecessor(BB, true); 776 } 777 778 DEBUG(dbgs() << " In block '" << BB->getName() 779 << "' folding undef terminator: " << *BBTerm << '\n'); 780 BranchInst::Create(BBTerm->getSuccessor(BestSucc), BBTerm); 781 BBTerm->eraseFromParent(); 782 return true; 783 } 784 785 // If the terminator of this block is branching on a constant, simplify the 786 // terminator to an unconditional branch. This can occur due to threading in 787 // other blocks. 788 if (getKnownConstant(Condition, Preference)) { 789 DEBUG(dbgs() << " In block '" << BB->getName() 790 << "' folding terminator: " << *BB->getTerminator() << '\n'); 791 ++NumFolds; 792 ConstantFoldTerminator(BB, true); 793 return true; 794 } 795 796 Instruction *CondInst = dyn_cast<Instruction>(Condition); 797 798 // All the rest of our checks depend on the condition being an instruction. 799 if (!CondInst) { 800 // FIXME: Unify this with code below. 801 if (ProcessThreadableEdges(Condition, BB, Preference, Terminator)) 802 return true; 803 return false; 804 } 805 806 807 if (CmpInst *CondCmp = dyn_cast<CmpInst>(CondInst)) { 808 // If we're branching on a conditional, LVI might be able to determine 809 // it's value at the branch instruction. We only handle comparisons 810 // against a constant at this time. 811 // TODO: This should be extended to handle switches as well. 812 BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator()); 813 Constant *CondConst = dyn_cast<Constant>(CondCmp->getOperand(1)); 814 if (CondBr && CondConst && CondBr->isConditional()) { 815 LazyValueInfo::Tristate Ret = 816 LVI->getPredicateAt(CondCmp->getPredicate(), CondCmp->getOperand(0), 817 CondConst, CondBr); 818 if (Ret != LazyValueInfo::Unknown) { 819 unsigned ToRemove = Ret == LazyValueInfo::True ? 1 : 0; 820 unsigned ToKeep = Ret == LazyValueInfo::True ? 0 : 1; 821 CondBr->getSuccessor(ToRemove)->removePredecessor(BB, true); 822 BranchInst::Create(CondBr->getSuccessor(ToKeep), CondBr); 823 CondBr->eraseFromParent(); 824 if (CondCmp->use_empty()) 825 CondCmp->eraseFromParent(); 826 else if (CondCmp->getParent() == BB) { 827 // If the fact we just learned is true for all uses of the 828 // condition, replace it with a constant value 829 auto *CI = Ret == LazyValueInfo::True ? 830 ConstantInt::getTrue(CondCmp->getType()) : 831 ConstantInt::getFalse(CondCmp->getType()); 832 CondCmp->replaceAllUsesWith(CI); 833 CondCmp->eraseFromParent(); 834 } 835 return true; 836 } 837 } 838 839 if (CondBr && CondConst && TryToUnfoldSelect(CondCmp, BB)) 840 return true; 841 } 842 843 // Check for some cases that are worth simplifying. Right now we want to look 844 // for loads that are used by a switch or by the condition for the branch. If 845 // we see one, check to see if it's partially redundant. If so, insert a PHI 846 // which can then be used to thread the values. 847 // 848 Value *SimplifyValue = CondInst; 849 if (CmpInst *CondCmp = dyn_cast<CmpInst>(SimplifyValue)) 850 if (isa<Constant>(CondCmp->getOperand(1))) 851 SimplifyValue = CondCmp->getOperand(0); 852 853 // TODO: There are other places where load PRE would be profitable, such as 854 // more complex comparisons. 855 if (LoadInst *LI = dyn_cast<LoadInst>(SimplifyValue)) 856 if (SimplifyPartiallyRedundantLoad(LI)) 857 return true; 858 859 860 // Handle a variety of cases where we are branching on something derived from 861 // a PHI node in the current block. If we can prove that any predecessors 862 // compute a predictable value based on a PHI node, thread those predecessors. 863 // 864 if (ProcessThreadableEdges(CondInst, BB, Preference, Terminator)) 865 return true; 866 867 // If this is an otherwise-unfoldable branch on a phi node in the current 868 // block, see if we can simplify. 869 if (PHINode *PN = dyn_cast<PHINode>(CondInst)) 870 if (PN->getParent() == BB && isa<BranchInst>(BB->getTerminator())) 871 return ProcessBranchOnPHI(PN); 872 873 874 // If this is an otherwise-unfoldable branch on a XOR, see if we can simplify. 875 if (CondInst->getOpcode() == Instruction::Xor && 876 CondInst->getParent() == BB && isa<BranchInst>(BB->getTerminator())) 877 return ProcessBranchOnXOR(cast<BinaryOperator>(CondInst)); 878 879 // Search for a stronger dominating condition that can be used to simplify a 880 // conditional branch leaving BB. 881 if (ProcessImpliedCondition(BB)) 882 return true; 883 884 return false; 885 } 886 887 bool JumpThreadingPass::ProcessImpliedCondition(BasicBlock *BB) { 888 auto *BI = dyn_cast<BranchInst>(BB->getTerminator()); 889 if (!BI || !BI->isConditional()) 890 return false; 891 892 Value *Cond = BI->getCondition(); 893 BasicBlock *CurrentBB = BB; 894 BasicBlock *CurrentPred = BB->getSinglePredecessor(); 895 unsigned Iter = 0; 896 897 auto &DL = BB->getModule()->getDataLayout(); 898 899 while (CurrentPred && Iter++ < ImplicationSearchThreshold) { 900 auto *PBI = dyn_cast<BranchInst>(CurrentPred->getTerminator()); 901 if (!PBI || !PBI->isConditional()) 902 return false; 903 if (PBI->getSuccessor(0) != CurrentBB && PBI->getSuccessor(1) != CurrentBB) 904 return false; 905 906 bool FalseDest = PBI->getSuccessor(1) == CurrentBB; 907 Optional<bool> Implication = 908 isImpliedCondition(PBI->getCondition(), Cond, DL, FalseDest); 909 if (Implication) { 910 BI->getSuccessor(*Implication ? 1 : 0)->removePredecessor(BB); 911 BranchInst::Create(BI->getSuccessor(*Implication ? 0 : 1), BI); 912 BI->eraseFromParent(); 913 return true; 914 } 915 CurrentBB = CurrentPred; 916 CurrentPred = CurrentBB->getSinglePredecessor(); 917 } 918 919 return false; 920 } 921 922 /// SimplifyPartiallyRedundantLoad - If LI is an obviously partially redundant 923 /// load instruction, eliminate it by replacing it with a PHI node. This is an 924 /// important optimization that encourages jump threading, and needs to be run 925 /// interlaced with other jump threading tasks. 926 bool JumpThreadingPass::SimplifyPartiallyRedundantLoad(LoadInst *LI) { 927 // Don't hack volatile and ordered loads. 928 if (!LI->isUnordered()) return false; 929 930 // If the load is defined in a block with exactly one predecessor, it can't be 931 // partially redundant. 932 BasicBlock *LoadBB = LI->getParent(); 933 if (LoadBB->getSinglePredecessor()) 934 return false; 935 936 // If the load is defined in an EH pad, it can't be partially redundant, 937 // because the edges between the invoke and the EH pad cannot have other 938 // instructions between them. 939 if (LoadBB->isEHPad()) 940 return false; 941 942 Value *LoadedPtr = LI->getOperand(0); 943 944 // If the loaded operand is defined in the LoadBB, it can't be available. 945 // TODO: Could do simple PHI translation, that would be fun :) 946 if (Instruction *PtrOp = dyn_cast<Instruction>(LoadedPtr)) 947 if (PtrOp->getParent() == LoadBB) 948 return false; 949 950 // Scan a few instructions up from the load, to see if it is obviously live at 951 // the entry to its block. 952 BasicBlock::iterator BBIt(LI); 953 954 if (Value *AvailableVal = 955 FindAvailableLoadedValue(LI, LoadBB, BBIt, DefMaxInstsToScan)) { 956 // If the value of the load is locally available within the block, just use 957 // it. This frequently occurs for reg2mem'd allocas. 958 959 // If the returned value is the load itself, replace with an undef. This can 960 // only happen in dead loops. 961 if (AvailableVal == LI) AvailableVal = UndefValue::get(LI->getType()); 962 if (AvailableVal->getType() != LI->getType()) 963 AvailableVal = 964 CastInst::CreateBitOrPointerCast(AvailableVal, LI->getType(), "", LI); 965 LI->replaceAllUsesWith(AvailableVal); 966 LI->eraseFromParent(); 967 return true; 968 } 969 970 // Otherwise, if we scanned the whole block and got to the top of the block, 971 // we know the block is locally transparent to the load. If not, something 972 // might clobber its value. 973 if (BBIt != LoadBB->begin()) 974 return false; 975 976 // If all of the loads and stores that feed the value have the same AA tags, 977 // then we can propagate them onto any newly inserted loads. 978 AAMDNodes AATags; 979 LI->getAAMetadata(AATags); 980 981 SmallPtrSet<BasicBlock*, 8> PredsScanned; 982 typedef SmallVector<std::pair<BasicBlock*, Value*>, 8> AvailablePredsTy; 983 AvailablePredsTy AvailablePreds; 984 BasicBlock *OneUnavailablePred = nullptr; 985 986 // If we got here, the loaded value is transparent through to the start of the 987 // block. Check to see if it is available in any of the predecessor blocks. 988 for (BasicBlock *PredBB : predecessors(LoadBB)) { 989 // If we already scanned this predecessor, skip it. 990 if (!PredsScanned.insert(PredBB).second) 991 continue; 992 993 // Scan the predecessor to see if the value is available in the pred. 994 BBIt = PredBB->end(); 995 AAMDNodes ThisAATags; 996 Value *PredAvailable = FindAvailableLoadedValue(LI, PredBB, BBIt, 997 DefMaxInstsToScan, 998 nullptr, &ThisAATags); 999 if (!PredAvailable) { 1000 OneUnavailablePred = PredBB; 1001 continue; 1002 } 1003 1004 // If AA tags disagree or are not present, forget about them. 1005 if (AATags != ThisAATags) AATags = AAMDNodes(); 1006 1007 // If so, this load is partially redundant. Remember this info so that we 1008 // can create a PHI node. 1009 AvailablePreds.push_back(std::make_pair(PredBB, PredAvailable)); 1010 } 1011 1012 // If the loaded value isn't available in any predecessor, it isn't partially 1013 // redundant. 1014 if (AvailablePreds.empty()) return false; 1015 1016 // Okay, the loaded value is available in at least one (and maybe all!) 1017 // predecessors. If the value is unavailable in more than one unique 1018 // predecessor, we want to insert a merge block for those common predecessors. 1019 // This ensures that we only have to insert one reload, thus not increasing 1020 // code size. 1021 BasicBlock *UnavailablePred = nullptr; 1022 1023 // If there is exactly one predecessor where the value is unavailable, the 1024 // already computed 'OneUnavailablePred' block is it. If it ends in an 1025 // unconditional branch, we know that it isn't a critical edge. 1026 if (PredsScanned.size() == AvailablePreds.size()+1 && 1027 OneUnavailablePred->getTerminator()->getNumSuccessors() == 1) { 1028 UnavailablePred = OneUnavailablePred; 1029 } else if (PredsScanned.size() != AvailablePreds.size()) { 1030 // Otherwise, we had multiple unavailable predecessors or we had a critical 1031 // edge from the one. 1032 SmallVector<BasicBlock*, 8> PredsToSplit; 1033 SmallPtrSet<BasicBlock*, 8> AvailablePredSet; 1034 1035 for (const auto &AvailablePred : AvailablePreds) 1036 AvailablePredSet.insert(AvailablePred.first); 1037 1038 // Add all the unavailable predecessors to the PredsToSplit list. 1039 for (BasicBlock *P : predecessors(LoadBB)) { 1040 // If the predecessor is an indirect goto, we can't split the edge. 1041 if (isa<IndirectBrInst>(P->getTerminator())) 1042 return false; 1043 1044 if (!AvailablePredSet.count(P)) 1045 PredsToSplit.push_back(P); 1046 } 1047 1048 // Split them out to their own block. 1049 UnavailablePred = SplitBlockPreds(LoadBB, PredsToSplit, "thread-pre-split"); 1050 } 1051 1052 // If the value isn't available in all predecessors, then there will be 1053 // exactly one where it isn't available. Insert a load on that edge and add 1054 // it to the AvailablePreds list. 1055 if (UnavailablePred) { 1056 assert(UnavailablePred->getTerminator()->getNumSuccessors() == 1 && 1057 "Can't handle critical edge here!"); 1058 LoadInst *NewVal = 1059 new LoadInst(LoadedPtr, LI->getName() + ".pr", false, 1060 LI->getAlignment(), LI->getOrdering(), LI->getSynchScope(), 1061 UnavailablePred->getTerminator()); 1062 NewVal->setDebugLoc(LI->getDebugLoc()); 1063 if (AATags) 1064 NewVal->setAAMetadata(AATags); 1065 1066 AvailablePreds.push_back(std::make_pair(UnavailablePred, NewVal)); 1067 } 1068 1069 // Now we know that each predecessor of this block has a value in 1070 // AvailablePreds, sort them for efficient access as we're walking the preds. 1071 array_pod_sort(AvailablePreds.begin(), AvailablePreds.end()); 1072 1073 // Create a PHI node at the start of the block for the PRE'd load value. 1074 pred_iterator PB = pred_begin(LoadBB), PE = pred_end(LoadBB); 1075 PHINode *PN = PHINode::Create(LI->getType(), std::distance(PB, PE), "", 1076 &LoadBB->front()); 1077 PN->takeName(LI); 1078 PN->setDebugLoc(LI->getDebugLoc()); 1079 1080 // Insert new entries into the PHI for each predecessor. A single block may 1081 // have multiple entries here. 1082 for (pred_iterator PI = PB; PI != PE; ++PI) { 1083 BasicBlock *P = *PI; 1084 AvailablePredsTy::iterator I = 1085 std::lower_bound(AvailablePreds.begin(), AvailablePreds.end(), 1086 std::make_pair(P, (Value*)nullptr)); 1087 1088 assert(I != AvailablePreds.end() && I->first == P && 1089 "Didn't find entry for predecessor!"); 1090 1091 // If we have an available predecessor but it requires casting, insert the 1092 // cast in the predecessor and use the cast. Note that we have to update the 1093 // AvailablePreds vector as we go so that all of the PHI entries for this 1094 // predecessor use the same bitcast. 1095 Value *&PredV = I->second; 1096 if (PredV->getType() != LI->getType()) 1097 PredV = CastInst::CreateBitOrPointerCast(PredV, LI->getType(), "", 1098 P->getTerminator()); 1099 1100 PN->addIncoming(PredV, I->first); 1101 } 1102 1103 LI->replaceAllUsesWith(PN); 1104 LI->eraseFromParent(); 1105 1106 return true; 1107 } 1108 1109 /// FindMostPopularDest - The specified list contains multiple possible 1110 /// threadable destinations. Pick the one that occurs the most frequently in 1111 /// the list. 1112 static BasicBlock * 1113 FindMostPopularDest(BasicBlock *BB, 1114 const SmallVectorImpl<std::pair<BasicBlock*, 1115 BasicBlock*> > &PredToDestList) { 1116 assert(!PredToDestList.empty()); 1117 1118 // Determine popularity. If there are multiple possible destinations, we 1119 // explicitly choose to ignore 'undef' destinations. We prefer to thread 1120 // blocks with known and real destinations to threading undef. We'll handle 1121 // them later if interesting. 1122 DenseMap<BasicBlock*, unsigned> DestPopularity; 1123 for (const auto &PredToDest : PredToDestList) 1124 if (PredToDest.second) 1125 DestPopularity[PredToDest.second]++; 1126 1127 // Find the most popular dest. 1128 DenseMap<BasicBlock*, unsigned>::iterator DPI = DestPopularity.begin(); 1129 BasicBlock *MostPopularDest = DPI->first; 1130 unsigned Popularity = DPI->second; 1131 SmallVector<BasicBlock*, 4> SamePopularity; 1132 1133 for (++DPI; DPI != DestPopularity.end(); ++DPI) { 1134 // If the popularity of this entry isn't higher than the popularity we've 1135 // seen so far, ignore it. 1136 if (DPI->second < Popularity) 1137 ; // ignore. 1138 else if (DPI->second == Popularity) { 1139 // If it is the same as what we've seen so far, keep track of it. 1140 SamePopularity.push_back(DPI->first); 1141 } else { 1142 // If it is more popular, remember it. 1143 SamePopularity.clear(); 1144 MostPopularDest = DPI->first; 1145 Popularity = DPI->second; 1146 } 1147 } 1148 1149 // Okay, now we know the most popular destination. If there is more than one 1150 // destination, we need to determine one. This is arbitrary, but we need 1151 // to make a deterministic decision. Pick the first one that appears in the 1152 // successor list. 1153 if (!SamePopularity.empty()) { 1154 SamePopularity.push_back(MostPopularDest); 1155 TerminatorInst *TI = BB->getTerminator(); 1156 for (unsigned i = 0; ; ++i) { 1157 assert(i != TI->getNumSuccessors() && "Didn't find any successor!"); 1158 1159 if (std::find(SamePopularity.begin(), SamePopularity.end(), 1160 TI->getSuccessor(i)) == SamePopularity.end()) 1161 continue; 1162 1163 MostPopularDest = TI->getSuccessor(i); 1164 break; 1165 } 1166 } 1167 1168 // Okay, we have finally picked the most popular destination. 1169 return MostPopularDest; 1170 } 1171 1172 bool JumpThreadingPass::ProcessThreadableEdges(Value *Cond, BasicBlock *BB, 1173 ConstantPreference Preference, 1174 Instruction *CxtI) { 1175 // If threading this would thread across a loop header, don't even try to 1176 // thread the edge. 1177 if (LoopHeaders.count(BB)) 1178 return false; 1179 1180 PredValueInfoTy PredValues; 1181 if (!ComputeValueKnownInPredecessors(Cond, BB, PredValues, Preference, CxtI)) 1182 return false; 1183 1184 assert(!PredValues.empty() && 1185 "ComputeValueKnownInPredecessors returned true with no values"); 1186 1187 DEBUG(dbgs() << "IN BB: " << *BB; 1188 for (const auto &PredValue : PredValues) { 1189 dbgs() << " BB '" << BB->getName() << "': FOUND condition = " 1190 << *PredValue.first 1191 << " for pred '" << PredValue.second->getName() << "'.\n"; 1192 }); 1193 1194 // Decide what we want to thread through. Convert our list of known values to 1195 // a list of known destinations for each pred. This also discards duplicate 1196 // predecessors and keeps track of the undefined inputs (which are represented 1197 // as a null dest in the PredToDestList). 1198 SmallPtrSet<BasicBlock*, 16> SeenPreds; 1199 SmallVector<std::pair<BasicBlock*, BasicBlock*>, 16> PredToDestList; 1200 1201 BasicBlock *OnlyDest = nullptr; 1202 BasicBlock *MultipleDestSentinel = (BasicBlock*)(intptr_t)~0ULL; 1203 1204 for (const auto &PredValue : PredValues) { 1205 BasicBlock *Pred = PredValue.second; 1206 if (!SeenPreds.insert(Pred).second) 1207 continue; // Duplicate predecessor entry. 1208 1209 // If the predecessor ends with an indirect goto, we can't change its 1210 // destination. 1211 if (isa<IndirectBrInst>(Pred->getTerminator())) 1212 continue; 1213 1214 Constant *Val = PredValue.first; 1215 1216 BasicBlock *DestBB; 1217 if (isa<UndefValue>(Val)) 1218 DestBB = nullptr; 1219 else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) 1220 DestBB = BI->getSuccessor(cast<ConstantInt>(Val)->isZero()); 1221 else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) { 1222 DestBB = SI->findCaseValue(cast<ConstantInt>(Val)).getCaseSuccessor(); 1223 } else { 1224 assert(isa<IndirectBrInst>(BB->getTerminator()) 1225 && "Unexpected terminator"); 1226 DestBB = cast<BlockAddress>(Val)->getBasicBlock(); 1227 } 1228 1229 // If we have exactly one destination, remember it for efficiency below. 1230 if (PredToDestList.empty()) 1231 OnlyDest = DestBB; 1232 else if (OnlyDest != DestBB) 1233 OnlyDest = MultipleDestSentinel; 1234 1235 PredToDestList.push_back(std::make_pair(Pred, DestBB)); 1236 } 1237 1238 // If all edges were unthreadable, we fail. 1239 if (PredToDestList.empty()) 1240 return false; 1241 1242 // Determine which is the most common successor. If we have many inputs and 1243 // this block is a switch, we want to start by threading the batch that goes 1244 // to the most popular destination first. If we only know about one 1245 // threadable destination (the common case) we can avoid this. 1246 BasicBlock *MostPopularDest = OnlyDest; 1247 1248 if (MostPopularDest == MultipleDestSentinel) 1249 MostPopularDest = FindMostPopularDest(BB, PredToDestList); 1250 1251 // Now that we know what the most popular destination is, factor all 1252 // predecessors that will jump to it into a single predecessor. 1253 SmallVector<BasicBlock*, 16> PredsToFactor; 1254 for (const auto &PredToDest : PredToDestList) 1255 if (PredToDest.second == MostPopularDest) { 1256 BasicBlock *Pred = PredToDest.first; 1257 1258 // This predecessor may be a switch or something else that has multiple 1259 // edges to the block. Factor each of these edges by listing them 1260 // according to # occurrences in PredsToFactor. 1261 for (BasicBlock *Succ : successors(Pred)) 1262 if (Succ == BB) 1263 PredsToFactor.push_back(Pred); 1264 } 1265 1266 // If the threadable edges are branching on an undefined value, we get to pick 1267 // the destination that these predecessors should get to. 1268 if (!MostPopularDest) 1269 MostPopularDest = BB->getTerminator()-> 1270 getSuccessor(GetBestDestForJumpOnUndef(BB)); 1271 1272 // Ok, try to thread it! 1273 return ThreadEdge(BB, PredsToFactor, MostPopularDest); 1274 } 1275 1276 /// ProcessBranchOnPHI - We have an otherwise unthreadable conditional branch on 1277 /// a PHI node in the current block. See if there are any simplifications we 1278 /// can do based on inputs to the phi node. 1279 /// 1280 bool JumpThreadingPass::ProcessBranchOnPHI(PHINode *PN) { 1281 BasicBlock *BB = PN->getParent(); 1282 1283 // TODO: We could make use of this to do it once for blocks with common PHI 1284 // values. 1285 SmallVector<BasicBlock*, 1> PredBBs; 1286 PredBBs.resize(1); 1287 1288 // If any of the predecessor blocks end in an unconditional branch, we can 1289 // *duplicate* the conditional branch into that block in order to further 1290 // encourage jump threading and to eliminate cases where we have branch on a 1291 // phi of an icmp (branch on icmp is much better). 1292 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1293 BasicBlock *PredBB = PN->getIncomingBlock(i); 1294 if (BranchInst *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator())) 1295 if (PredBr->isUnconditional()) { 1296 PredBBs[0] = PredBB; 1297 // Try to duplicate BB into PredBB. 1298 if (DuplicateCondBranchOnPHIIntoPred(BB, PredBBs)) 1299 return true; 1300 } 1301 } 1302 1303 return false; 1304 } 1305 1306 /// ProcessBranchOnXOR - We have an otherwise unthreadable conditional branch on 1307 /// a xor instruction in the current block. See if there are any 1308 /// simplifications we can do based on inputs to the xor. 1309 /// 1310 bool JumpThreadingPass::ProcessBranchOnXOR(BinaryOperator *BO) { 1311 BasicBlock *BB = BO->getParent(); 1312 1313 // If either the LHS or RHS of the xor is a constant, don't do this 1314 // optimization. 1315 if (isa<ConstantInt>(BO->getOperand(0)) || 1316 isa<ConstantInt>(BO->getOperand(1))) 1317 return false; 1318 1319 // If the first instruction in BB isn't a phi, we won't be able to infer 1320 // anything special about any particular predecessor. 1321 if (!isa<PHINode>(BB->front())) 1322 return false; 1323 1324 // If we have a xor as the branch input to this block, and we know that the 1325 // LHS or RHS of the xor in any predecessor is true/false, then we can clone 1326 // the condition into the predecessor and fix that value to true, saving some 1327 // logical ops on that path and encouraging other paths to simplify. 1328 // 1329 // This copies something like this: 1330 // 1331 // BB: 1332 // %X = phi i1 [1], [%X'] 1333 // %Y = icmp eq i32 %A, %B 1334 // %Z = xor i1 %X, %Y 1335 // br i1 %Z, ... 1336 // 1337 // Into: 1338 // BB': 1339 // %Y = icmp ne i32 %A, %B 1340 // br i1 %Y, ... 1341 1342 PredValueInfoTy XorOpValues; 1343 bool isLHS = true; 1344 if (!ComputeValueKnownInPredecessors(BO->getOperand(0), BB, XorOpValues, 1345 WantInteger, BO)) { 1346 assert(XorOpValues.empty()); 1347 if (!ComputeValueKnownInPredecessors(BO->getOperand(1), BB, XorOpValues, 1348 WantInteger, BO)) 1349 return false; 1350 isLHS = false; 1351 } 1352 1353 assert(!XorOpValues.empty() && 1354 "ComputeValueKnownInPredecessors returned true with no values"); 1355 1356 // Scan the information to see which is most popular: true or false. The 1357 // predecessors can be of the set true, false, or undef. 1358 unsigned NumTrue = 0, NumFalse = 0; 1359 for (const auto &XorOpValue : XorOpValues) { 1360 if (isa<UndefValue>(XorOpValue.first)) 1361 // Ignore undefs for the count. 1362 continue; 1363 if (cast<ConstantInt>(XorOpValue.first)->isZero()) 1364 ++NumFalse; 1365 else 1366 ++NumTrue; 1367 } 1368 1369 // Determine which value to split on, true, false, or undef if neither. 1370 ConstantInt *SplitVal = nullptr; 1371 if (NumTrue > NumFalse) 1372 SplitVal = ConstantInt::getTrue(BB->getContext()); 1373 else if (NumTrue != 0 || NumFalse != 0) 1374 SplitVal = ConstantInt::getFalse(BB->getContext()); 1375 1376 // Collect all of the blocks that this can be folded into so that we can 1377 // factor this once and clone it once. 1378 SmallVector<BasicBlock*, 8> BlocksToFoldInto; 1379 for (const auto &XorOpValue : XorOpValues) { 1380 if (XorOpValue.first != SplitVal && !isa<UndefValue>(XorOpValue.first)) 1381 continue; 1382 1383 BlocksToFoldInto.push_back(XorOpValue.second); 1384 } 1385 1386 // If we inferred a value for all of the predecessors, then duplication won't 1387 // help us. However, we can just replace the LHS or RHS with the constant. 1388 if (BlocksToFoldInto.size() == 1389 cast<PHINode>(BB->front()).getNumIncomingValues()) { 1390 if (!SplitVal) { 1391 // If all preds provide undef, just nuke the xor, because it is undef too. 1392 BO->replaceAllUsesWith(UndefValue::get(BO->getType())); 1393 BO->eraseFromParent(); 1394 } else if (SplitVal->isZero()) { 1395 // If all preds provide 0, replace the xor with the other input. 1396 BO->replaceAllUsesWith(BO->getOperand(isLHS)); 1397 BO->eraseFromParent(); 1398 } else { 1399 // If all preds provide 1, set the computed value to 1. 1400 BO->setOperand(!isLHS, SplitVal); 1401 } 1402 1403 return true; 1404 } 1405 1406 // Try to duplicate BB into PredBB. 1407 return DuplicateCondBranchOnPHIIntoPred(BB, BlocksToFoldInto); 1408 } 1409 1410 1411 /// AddPHINodeEntriesForMappedBlock - We're adding 'NewPred' as a new 1412 /// predecessor to the PHIBB block. If it has PHI nodes, add entries for 1413 /// NewPred using the entries from OldPred (suitably mapped). 1414 static void AddPHINodeEntriesForMappedBlock(BasicBlock *PHIBB, 1415 BasicBlock *OldPred, 1416 BasicBlock *NewPred, 1417 DenseMap<Instruction*, Value*> &ValueMap) { 1418 for (BasicBlock::iterator PNI = PHIBB->begin(); 1419 PHINode *PN = dyn_cast<PHINode>(PNI); ++PNI) { 1420 // Ok, we have a PHI node. Figure out what the incoming value was for the 1421 // DestBlock. 1422 Value *IV = PN->getIncomingValueForBlock(OldPred); 1423 1424 // Remap the value if necessary. 1425 if (Instruction *Inst = dyn_cast<Instruction>(IV)) { 1426 DenseMap<Instruction*, Value*>::iterator I = ValueMap.find(Inst); 1427 if (I != ValueMap.end()) 1428 IV = I->second; 1429 } 1430 1431 PN->addIncoming(IV, NewPred); 1432 } 1433 } 1434 1435 /// ThreadEdge - We have decided that it is safe and profitable to factor the 1436 /// blocks in PredBBs to one predecessor, then thread an edge from it to SuccBB 1437 /// across BB. Transform the IR to reflect this change. 1438 bool JumpThreadingPass::ThreadEdge(BasicBlock *BB, 1439 const SmallVectorImpl<BasicBlock *> &PredBBs, 1440 BasicBlock *SuccBB) { 1441 // If threading to the same block as we come from, we would infinite loop. 1442 if (SuccBB == BB) { 1443 DEBUG(dbgs() << " Not threading across BB '" << BB->getName() 1444 << "' - would thread to self!\n"); 1445 return false; 1446 } 1447 1448 // If threading this would thread across a loop header, don't thread the edge. 1449 // See the comments above FindLoopHeaders for justifications and caveats. 1450 if (LoopHeaders.count(BB)) { 1451 DEBUG(dbgs() << " Not threading across loop header BB '" << BB->getName() 1452 << "' to dest BB '" << SuccBB->getName() 1453 << "' - it might create an irreducible loop!\n"); 1454 return false; 1455 } 1456 1457 unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB, BBDupThreshold); 1458 if (JumpThreadCost > BBDupThreshold) { 1459 DEBUG(dbgs() << " Not threading BB '" << BB->getName() 1460 << "' - Cost is too high: " << JumpThreadCost << "\n"); 1461 return false; 1462 } 1463 1464 // And finally, do it! Start by factoring the predecessors if needed. 1465 BasicBlock *PredBB; 1466 if (PredBBs.size() == 1) 1467 PredBB = PredBBs[0]; 1468 else { 1469 DEBUG(dbgs() << " Factoring out " << PredBBs.size() 1470 << " common predecessors.\n"); 1471 PredBB = SplitBlockPreds(BB, PredBBs, ".thr_comm"); 1472 } 1473 1474 // And finally, do it! 1475 DEBUG(dbgs() << " Threading edge from '" << PredBB->getName() << "' to '" 1476 << SuccBB->getName() << "' with cost: " << JumpThreadCost 1477 << ", across block:\n " 1478 << *BB << "\n"); 1479 1480 LVI->threadEdge(PredBB, BB, SuccBB); 1481 1482 // We are going to have to map operands from the original BB block to the new 1483 // copy of the block 'NewBB'. If there are PHI nodes in BB, evaluate them to 1484 // account for entry from PredBB. 1485 DenseMap<Instruction*, Value*> ValueMapping; 1486 1487 BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), 1488 BB->getName()+".thread", 1489 BB->getParent(), BB); 1490 NewBB->moveAfter(PredBB); 1491 1492 // Set the block frequency of NewBB. 1493 if (HasProfileData) { 1494 auto NewBBFreq = 1495 BFI->getBlockFreq(PredBB) * BPI->getEdgeProbability(PredBB, BB); 1496 BFI->setBlockFreq(NewBB, NewBBFreq.getFrequency()); 1497 } 1498 1499 BasicBlock::iterator BI = BB->begin(); 1500 for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI) 1501 ValueMapping[PN] = PN->getIncomingValueForBlock(PredBB); 1502 1503 // Clone the non-phi instructions of BB into NewBB, keeping track of the 1504 // mapping and using it to remap operands in the cloned instructions. 1505 for (; !isa<TerminatorInst>(BI); ++BI) { 1506 Instruction *New = BI->clone(); 1507 New->setName(BI->getName()); 1508 NewBB->getInstList().push_back(New); 1509 ValueMapping[&*BI] = New; 1510 1511 // Remap operands to patch up intra-block references. 1512 for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i) 1513 if (Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) { 1514 DenseMap<Instruction*, Value*>::iterator I = ValueMapping.find(Inst); 1515 if (I != ValueMapping.end()) 1516 New->setOperand(i, I->second); 1517 } 1518 } 1519 1520 // We didn't copy the terminator from BB over to NewBB, because there is now 1521 // an unconditional jump to SuccBB. Insert the unconditional jump. 1522 BranchInst *NewBI = BranchInst::Create(SuccBB, NewBB); 1523 NewBI->setDebugLoc(BB->getTerminator()->getDebugLoc()); 1524 1525 // Check to see if SuccBB has PHI nodes. If so, we need to add entries to the 1526 // PHI nodes for NewBB now. 1527 AddPHINodeEntriesForMappedBlock(SuccBB, BB, NewBB, ValueMapping); 1528 1529 // If there were values defined in BB that are used outside the block, then we 1530 // now have to update all uses of the value to use either the original value, 1531 // the cloned value, or some PHI derived value. This can require arbitrary 1532 // PHI insertion, of which we are prepared to do, clean these up now. 1533 SSAUpdater SSAUpdate; 1534 SmallVector<Use*, 16> UsesToRename; 1535 for (Instruction &I : *BB) { 1536 // Scan all uses of this instruction to see if it is used outside of its 1537 // block, and if so, record them in UsesToRename. 1538 for (Use &U : I.uses()) { 1539 Instruction *User = cast<Instruction>(U.getUser()); 1540 if (PHINode *UserPN = dyn_cast<PHINode>(User)) { 1541 if (UserPN->getIncomingBlock(U) == BB) 1542 continue; 1543 } else if (User->getParent() == BB) 1544 continue; 1545 1546 UsesToRename.push_back(&U); 1547 } 1548 1549 // If there are no uses outside the block, we're done with this instruction. 1550 if (UsesToRename.empty()) 1551 continue; 1552 1553 DEBUG(dbgs() << "JT: Renaming non-local uses of: " << I << "\n"); 1554 1555 // We found a use of I outside of BB. Rename all uses of I that are outside 1556 // its block to be uses of the appropriate PHI node etc. See ValuesInBlocks 1557 // with the two values we know. 1558 SSAUpdate.Initialize(I.getType(), I.getName()); 1559 SSAUpdate.AddAvailableValue(BB, &I); 1560 SSAUpdate.AddAvailableValue(NewBB, ValueMapping[&I]); 1561 1562 while (!UsesToRename.empty()) 1563 SSAUpdate.RewriteUse(*UsesToRename.pop_back_val()); 1564 DEBUG(dbgs() << "\n"); 1565 } 1566 1567 1568 // Ok, NewBB is good to go. Update the terminator of PredBB to jump to 1569 // NewBB instead of BB. This eliminates predecessors from BB, which requires 1570 // us to simplify any PHI nodes in BB. 1571 TerminatorInst *PredTerm = PredBB->getTerminator(); 1572 for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i) 1573 if (PredTerm->getSuccessor(i) == BB) { 1574 BB->removePredecessor(PredBB, true); 1575 PredTerm->setSuccessor(i, NewBB); 1576 } 1577 1578 // At this point, the IR is fully up to date and consistent. Do a quick scan 1579 // over the new instructions and zap any that are constants or dead. This 1580 // frequently happens because of phi translation. 1581 SimplifyInstructionsInBlock(NewBB, TLI); 1582 1583 // Update the edge weight from BB to SuccBB, which should be less than before. 1584 UpdateBlockFreqAndEdgeWeight(PredBB, BB, NewBB, SuccBB); 1585 1586 // Threaded an edge! 1587 ++NumThreads; 1588 return true; 1589 } 1590 1591 /// Create a new basic block that will be the predecessor of BB and successor of 1592 /// all blocks in Preds. When profile data is availble, update the frequency of 1593 /// this new block. 1594 BasicBlock *JumpThreadingPass::SplitBlockPreds(BasicBlock *BB, 1595 ArrayRef<BasicBlock *> Preds, 1596 const char *Suffix) { 1597 // Collect the frequencies of all predecessors of BB, which will be used to 1598 // update the edge weight on BB->SuccBB. 1599 BlockFrequency PredBBFreq(0); 1600 if (HasProfileData) 1601 for (auto Pred : Preds) 1602 PredBBFreq += BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, BB); 1603 1604 BasicBlock *PredBB = SplitBlockPredecessors(BB, Preds, Suffix); 1605 1606 // Set the block frequency of the newly created PredBB, which is the sum of 1607 // frequencies of Preds. 1608 if (HasProfileData) 1609 BFI->setBlockFreq(PredBB, PredBBFreq.getFrequency()); 1610 return PredBB; 1611 } 1612 1613 /// Update the block frequency of BB and branch weight and the metadata on the 1614 /// edge BB->SuccBB. This is done by scaling the weight of BB->SuccBB by 1 - 1615 /// Freq(PredBB->BB) / Freq(BB->SuccBB). 1616 void JumpThreadingPass::UpdateBlockFreqAndEdgeWeight(BasicBlock *PredBB, 1617 BasicBlock *BB, 1618 BasicBlock *NewBB, 1619 BasicBlock *SuccBB) { 1620 if (!HasProfileData) 1621 return; 1622 1623 assert(BFI && BPI && "BFI & BPI should have been created here"); 1624 1625 // As the edge from PredBB to BB is deleted, we have to update the block 1626 // frequency of BB. 1627 auto BBOrigFreq = BFI->getBlockFreq(BB); 1628 auto NewBBFreq = BFI->getBlockFreq(NewBB); 1629 auto BB2SuccBBFreq = BBOrigFreq * BPI->getEdgeProbability(BB, SuccBB); 1630 auto BBNewFreq = BBOrigFreq - NewBBFreq; 1631 BFI->setBlockFreq(BB, BBNewFreq.getFrequency()); 1632 1633 // Collect updated outgoing edges' frequencies from BB and use them to update 1634 // edge probabilities. 1635 SmallVector<uint64_t, 4> BBSuccFreq; 1636 for (BasicBlock *Succ : successors(BB)) { 1637 auto SuccFreq = (Succ == SuccBB) 1638 ? BB2SuccBBFreq - NewBBFreq 1639 : BBOrigFreq * BPI->getEdgeProbability(BB, Succ); 1640 BBSuccFreq.push_back(SuccFreq.getFrequency()); 1641 } 1642 1643 uint64_t MaxBBSuccFreq = 1644 *std::max_element(BBSuccFreq.begin(), BBSuccFreq.end()); 1645 1646 SmallVector<BranchProbability, 4> BBSuccProbs; 1647 if (MaxBBSuccFreq == 0) 1648 BBSuccProbs.assign(BBSuccFreq.size(), 1649 {1, static_cast<unsigned>(BBSuccFreq.size())}); 1650 else { 1651 for (uint64_t Freq : BBSuccFreq) 1652 BBSuccProbs.push_back( 1653 BranchProbability::getBranchProbability(Freq, MaxBBSuccFreq)); 1654 // Normalize edge probabilities so that they sum up to one. 1655 BranchProbability::normalizeProbabilities(BBSuccProbs.begin(), 1656 BBSuccProbs.end()); 1657 } 1658 1659 // Update edge probabilities in BPI. 1660 for (int I = 0, E = BBSuccProbs.size(); I < E; I++) 1661 BPI->setEdgeProbability(BB, I, BBSuccProbs[I]); 1662 1663 if (BBSuccProbs.size() >= 2) { 1664 SmallVector<uint32_t, 4> Weights; 1665 for (auto Prob : BBSuccProbs) 1666 Weights.push_back(Prob.getNumerator()); 1667 1668 auto TI = BB->getTerminator(); 1669 TI->setMetadata( 1670 LLVMContext::MD_prof, 1671 MDBuilder(TI->getParent()->getContext()).createBranchWeights(Weights)); 1672 } 1673 } 1674 1675 /// DuplicateCondBranchOnPHIIntoPred - PredBB contains an unconditional branch 1676 /// to BB which contains an i1 PHI node and a conditional branch on that PHI. 1677 /// If we can duplicate the contents of BB up into PredBB do so now, this 1678 /// improves the odds that the branch will be on an analyzable instruction like 1679 /// a compare. 1680 bool JumpThreadingPass::DuplicateCondBranchOnPHIIntoPred( 1681 BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs) { 1682 assert(!PredBBs.empty() && "Can't handle an empty set"); 1683 1684 // If BB is a loop header, then duplicating this block outside the loop would 1685 // cause us to transform this into an irreducible loop, don't do this. 1686 // See the comments above FindLoopHeaders for justifications and caveats. 1687 if (LoopHeaders.count(BB)) { 1688 DEBUG(dbgs() << " Not duplicating loop header '" << BB->getName() 1689 << "' into predecessor block '" << PredBBs[0]->getName() 1690 << "' - it might create an irreducible loop!\n"); 1691 return false; 1692 } 1693 1694 unsigned DuplicationCost = getJumpThreadDuplicationCost(BB, BBDupThreshold); 1695 if (DuplicationCost > BBDupThreshold) { 1696 DEBUG(dbgs() << " Not duplicating BB '" << BB->getName() 1697 << "' - Cost is too high: " << DuplicationCost << "\n"); 1698 return false; 1699 } 1700 1701 // And finally, do it! Start by factoring the predecessors if needed. 1702 BasicBlock *PredBB; 1703 if (PredBBs.size() == 1) 1704 PredBB = PredBBs[0]; 1705 else { 1706 DEBUG(dbgs() << " Factoring out " << PredBBs.size() 1707 << " common predecessors.\n"); 1708 PredBB = SplitBlockPreds(BB, PredBBs, ".thr_comm"); 1709 } 1710 1711 // Okay, we decided to do this! Clone all the instructions in BB onto the end 1712 // of PredBB. 1713 DEBUG(dbgs() << " Duplicating block '" << BB->getName() << "' into end of '" 1714 << PredBB->getName() << "' to eliminate branch on phi. Cost: " 1715 << DuplicationCost << " block is:" << *BB << "\n"); 1716 1717 // Unless PredBB ends with an unconditional branch, split the edge so that we 1718 // can just clone the bits from BB into the end of the new PredBB. 1719 BranchInst *OldPredBranch = dyn_cast<BranchInst>(PredBB->getTerminator()); 1720 1721 if (!OldPredBranch || !OldPredBranch->isUnconditional()) { 1722 PredBB = SplitEdge(PredBB, BB); 1723 OldPredBranch = cast<BranchInst>(PredBB->getTerminator()); 1724 } 1725 1726 // We are going to have to map operands from the original BB block into the 1727 // PredBB block. Evaluate PHI nodes in BB. 1728 DenseMap<Instruction*, Value*> ValueMapping; 1729 1730 BasicBlock::iterator BI = BB->begin(); 1731 for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI) 1732 ValueMapping[PN] = PN->getIncomingValueForBlock(PredBB); 1733 // Clone the non-phi instructions of BB into PredBB, keeping track of the 1734 // mapping and using it to remap operands in the cloned instructions. 1735 for (; BI != BB->end(); ++BI) { 1736 Instruction *New = BI->clone(); 1737 1738 // Remap operands to patch up intra-block references. 1739 for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i) 1740 if (Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) { 1741 DenseMap<Instruction*, Value*>::iterator I = ValueMapping.find(Inst); 1742 if (I != ValueMapping.end()) 1743 New->setOperand(i, I->second); 1744 } 1745 1746 // If this instruction can be simplified after the operands are updated, 1747 // just use the simplified value instead. This frequently happens due to 1748 // phi translation. 1749 if (Value *IV = 1750 SimplifyInstruction(New, BB->getModule()->getDataLayout())) { 1751 ValueMapping[&*BI] = IV; 1752 if (!New->mayHaveSideEffects()) { 1753 delete New; 1754 New = nullptr; 1755 } 1756 } else { 1757 ValueMapping[&*BI] = New; 1758 } 1759 if (New) { 1760 // Otherwise, insert the new instruction into the block. 1761 New->setName(BI->getName()); 1762 PredBB->getInstList().insert(OldPredBranch->getIterator(), New); 1763 } 1764 } 1765 1766 // Check to see if the targets of the branch had PHI nodes. If so, we need to 1767 // add entries to the PHI nodes for branch from PredBB now. 1768 BranchInst *BBBranch = cast<BranchInst>(BB->getTerminator()); 1769 AddPHINodeEntriesForMappedBlock(BBBranch->getSuccessor(0), BB, PredBB, 1770 ValueMapping); 1771 AddPHINodeEntriesForMappedBlock(BBBranch->getSuccessor(1), BB, PredBB, 1772 ValueMapping); 1773 1774 // If there were values defined in BB that are used outside the block, then we 1775 // now have to update all uses of the value to use either the original value, 1776 // the cloned value, or some PHI derived value. This can require arbitrary 1777 // PHI insertion, of which we are prepared to do, clean these up now. 1778 SSAUpdater SSAUpdate; 1779 SmallVector<Use*, 16> UsesToRename; 1780 for (Instruction &I : *BB) { 1781 // Scan all uses of this instruction to see if it is used outside of its 1782 // block, and if so, record them in UsesToRename. 1783 for (Use &U : I.uses()) { 1784 Instruction *User = cast<Instruction>(U.getUser()); 1785 if (PHINode *UserPN = dyn_cast<PHINode>(User)) { 1786 if (UserPN->getIncomingBlock(U) == BB) 1787 continue; 1788 } else if (User->getParent() == BB) 1789 continue; 1790 1791 UsesToRename.push_back(&U); 1792 } 1793 1794 // If there are no uses outside the block, we're done with this instruction. 1795 if (UsesToRename.empty()) 1796 continue; 1797 1798 DEBUG(dbgs() << "JT: Renaming non-local uses of: " << I << "\n"); 1799 1800 // We found a use of I outside of BB. Rename all uses of I that are outside 1801 // its block to be uses of the appropriate PHI node etc. See ValuesInBlocks 1802 // with the two values we know. 1803 SSAUpdate.Initialize(I.getType(), I.getName()); 1804 SSAUpdate.AddAvailableValue(BB, &I); 1805 SSAUpdate.AddAvailableValue(PredBB, ValueMapping[&I]); 1806 1807 while (!UsesToRename.empty()) 1808 SSAUpdate.RewriteUse(*UsesToRename.pop_back_val()); 1809 DEBUG(dbgs() << "\n"); 1810 } 1811 1812 // PredBB no longer jumps to BB, remove entries in the PHI node for the edge 1813 // that we nuked. 1814 BB->removePredecessor(PredBB, true); 1815 1816 // Remove the unconditional branch at the end of the PredBB block. 1817 OldPredBranch->eraseFromParent(); 1818 1819 ++NumDupes; 1820 return true; 1821 } 1822 1823 /// TryToUnfoldSelect - Look for blocks of the form 1824 /// bb1: 1825 /// %a = select 1826 /// br bb 1827 /// 1828 /// bb2: 1829 /// %p = phi [%a, %bb] ... 1830 /// %c = icmp %p 1831 /// br i1 %c 1832 /// 1833 /// And expand the select into a branch structure if one of its arms allows %c 1834 /// to be folded. This later enables threading from bb1 over bb2. 1835 bool JumpThreadingPass::TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB) { 1836 BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator()); 1837 PHINode *CondLHS = dyn_cast<PHINode>(CondCmp->getOperand(0)); 1838 Constant *CondRHS = cast<Constant>(CondCmp->getOperand(1)); 1839 1840 if (!CondBr || !CondBr->isConditional() || !CondLHS || 1841 CondLHS->getParent() != BB) 1842 return false; 1843 1844 for (unsigned I = 0, E = CondLHS->getNumIncomingValues(); I != E; ++I) { 1845 BasicBlock *Pred = CondLHS->getIncomingBlock(I); 1846 SelectInst *SI = dyn_cast<SelectInst>(CondLHS->getIncomingValue(I)); 1847 1848 // Look if one of the incoming values is a select in the corresponding 1849 // predecessor. 1850 if (!SI || SI->getParent() != Pred || !SI->hasOneUse()) 1851 continue; 1852 1853 BranchInst *PredTerm = dyn_cast<BranchInst>(Pred->getTerminator()); 1854 if (!PredTerm || !PredTerm->isUnconditional()) 1855 continue; 1856 1857 // Now check if one of the select values would allow us to constant fold the 1858 // terminator in BB. We don't do the transform if both sides fold, those 1859 // cases will be threaded in any case. 1860 LazyValueInfo::Tristate LHSFolds = 1861 LVI->getPredicateOnEdge(CondCmp->getPredicate(), SI->getOperand(1), 1862 CondRHS, Pred, BB, CondCmp); 1863 LazyValueInfo::Tristate RHSFolds = 1864 LVI->getPredicateOnEdge(CondCmp->getPredicate(), SI->getOperand(2), 1865 CondRHS, Pred, BB, CondCmp); 1866 if ((LHSFolds != LazyValueInfo::Unknown || 1867 RHSFolds != LazyValueInfo::Unknown) && 1868 LHSFolds != RHSFolds) { 1869 // Expand the select. 1870 // 1871 // Pred -- 1872 // | v 1873 // | NewBB 1874 // | | 1875 // |----- 1876 // v 1877 // BB 1878 BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "select.unfold", 1879 BB->getParent(), BB); 1880 // Move the unconditional branch to NewBB. 1881 PredTerm->removeFromParent(); 1882 NewBB->getInstList().insert(NewBB->end(), PredTerm); 1883 // Create a conditional branch and update PHI nodes. 1884 BranchInst::Create(NewBB, BB, SI->getCondition(), Pred); 1885 CondLHS->setIncomingValue(I, SI->getFalseValue()); 1886 CondLHS->addIncoming(SI->getTrueValue(), NewBB); 1887 // The select is now dead. 1888 SI->eraseFromParent(); 1889 1890 // Update any other PHI nodes in BB. 1891 for (BasicBlock::iterator BI = BB->begin(); 1892 PHINode *Phi = dyn_cast<PHINode>(BI); ++BI) 1893 if (Phi != CondLHS) 1894 Phi->addIncoming(Phi->getIncomingValueForBlock(Pred), NewBB); 1895 return true; 1896 } 1897 } 1898 return false; 1899 } 1900 1901 /// TryToUnfoldSelectInCurrBB - Look for PHI/Select in the same BB of the form 1902 /// bb: 1903 /// %p = phi [false, %bb1], [true, %bb2], [false, %bb3], [true, %bb4], ... 1904 /// %s = select p, trueval, falseval 1905 /// 1906 /// And expand the select into a branch structure. This later enables 1907 /// jump-threading over bb in this pass. 1908 /// 1909 /// Using the similar approach of SimplifyCFG::FoldCondBranchOnPHI(), unfold 1910 /// select if the associated PHI has at least one constant. If the unfolded 1911 /// select is not jump-threaded, it will be folded again in the later 1912 /// optimizations. 1913 bool JumpThreadingPass::TryToUnfoldSelectInCurrBB(BasicBlock *BB) { 1914 // If threading this would thread across a loop header, don't thread the edge. 1915 // See the comments above FindLoopHeaders for justifications and caveats. 1916 if (LoopHeaders.count(BB)) 1917 return false; 1918 1919 // Look for a Phi/Select pair in the same basic block. The Phi feeds the 1920 // condition of the Select and at least one of the incoming values is a 1921 // constant. 1922 for (BasicBlock::iterator BI = BB->begin(); 1923 PHINode *PN = dyn_cast<PHINode>(BI); ++BI) { 1924 unsigned NumPHIValues = PN->getNumIncomingValues(); 1925 if (NumPHIValues == 0 || !PN->hasOneUse()) 1926 continue; 1927 1928 SelectInst *SI = dyn_cast<SelectInst>(PN->user_back()); 1929 if (!SI || SI->getParent() != BB) 1930 continue; 1931 1932 Value *Cond = SI->getCondition(); 1933 if (!Cond || Cond != PN || !Cond->getType()->isIntegerTy(1)) 1934 continue; 1935 1936 bool HasConst = false; 1937 for (unsigned i = 0; i != NumPHIValues; ++i) { 1938 if (PN->getIncomingBlock(i) == BB) 1939 return false; 1940 if (isa<ConstantInt>(PN->getIncomingValue(i))) 1941 HasConst = true; 1942 } 1943 1944 if (HasConst) { 1945 // Expand the select. 1946 TerminatorInst *Term = 1947 SplitBlockAndInsertIfThen(SI->getCondition(), SI, false); 1948 PHINode *NewPN = PHINode::Create(SI->getType(), 2, "", SI); 1949 NewPN->addIncoming(SI->getTrueValue(), Term->getParent()); 1950 NewPN->addIncoming(SI->getFalseValue(), BB); 1951 SI->replaceAllUsesWith(NewPN); 1952 SI->eraseFromParent(); 1953 return true; 1954 } 1955 } 1956 1957 return false; 1958 } 1959