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