Lines Matching full:bb
102 cl::desc("Max PHIs in BB to duplicate for jump threading"), cl::init(76),
127 // [Block BB]
149 static void updatePredecessorProfileMetadata(PHINode *PN, BasicBlock *BB) { in updatePredecessorProfileMetadata() argument
150 BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator()); in updatePredecessorProfileMetadata()
204 auto PredOutEdge = GetPredOutEdge(PN->getIncomingBlock(i), BB); in updatePredecessorProfileMetadata()
318 for (auto &BB : *F) in runImpl()
319 if (!DT.isReachableFromEntry(&BB)) in runImpl()
320 Unreachable.insert(&BB); in runImpl()
329 for (auto &BB : *F) { in runImpl()
330 if (Unreachable.count(&BB)) in runImpl()
332 while (processBlock(&BB)) // Thread all of the branches we can over BB. in runImpl()
335 // Jump threading may have introduced redundant debug values into BB in runImpl()
338 RemoveRedundantDbgInstrs(&BB); in runImpl()
340 // Stop processing BB if it's the entry or is now deleted. The following in runImpl()
341 // routines attempt to eliminate BB and locating a suitable replacement in runImpl()
343 if (&BB == &F->getEntryBlock() || DTU->isBBPendingDeletion(&BB)) in runImpl()
346 if (pred_empty(&BB)) { in runImpl()
347 // When processBlock makes BB unreachable it doesn't bother to fix up in runImpl()
348 // the instructions in it. We must remove BB to prevent invalid IR. in runImpl()
349 LLVM_DEBUG(dbgs() << " JT: Deleting dead block '" << BB.getName() in runImpl()
350 << "' with terminator: " << *BB.getTerminator() in runImpl()
352 LoopHeaders.erase(&BB); in runImpl()
353 LVI->eraseBlock(&BB); in runImpl()
354 DeleteDeadBlock(&BB, DTU.get()); in runImpl()
359 // processBlock doesn't thread BBs with unconditional TIs. However, if BB in runImpl()
360 // is "almost empty", we attempt to merge BB with its sole successor. in runImpl()
361 auto *BI = dyn_cast<BranchInst>(BB.getTerminator()); in runImpl()
365 // The terminator must be the only non-phi instruction in BB. in runImpl()
366 BB.getFirstNonPHIOrDbg(true)->isTerminator() && in runImpl()
369 !LoopHeaders.count(&BB) && !LoopHeaders.count(Succ) && in runImpl()
370 TryToSimplifyUncondBranchFromEmptyBlock(&BB, DTU.get())) { in runImpl()
372 // BB is valid for cleanup here because we passed in DTU. F remains in runImpl()
373 // BB's parent until a DTU->getDomTree() event. in runImpl()
374 LVI->eraseBlock(&BB); in runImpl()
398 // strictly dominated by BB), since LVI information is true from the in replaceFoldableUses()
399 // terminator of BB. in replaceFoldableUses()
412 // of BB, where we know Cond is ToVal. in replaceFoldableUses()
428 BasicBlock *BB, in getJumpThreadDuplicationCost() argument
431 assert(StopAt->getParent() == BB && "Not an instruction from proper BB?"); in getJumpThreadDuplicationCost()
433 // Do not duplicate the BB if it has a lot of PHI nodes. in getJumpThreadDuplicationCost()
438 for (Instruction &I : *BB) { in getJumpThreadDuplicationCost()
454 if (BB->getTerminator() == StopAt) { in getJumpThreadDuplicationCost()
480 // to duplicate it if it is used outside this BB. in getJumpThreadDuplicationCost()
481 if (I->getType()->isTokenTy() && I->isUsedOutsideOfBlock(BB)) in getJumpThreadDuplicationCost()
553 /// computeValueKnownInPredecessors - Given a basic block BB and a value V, see
556 /// BB in the result vector.
560 Value *V, BasicBlock *BB, PredValueInfo &Result, in computeValueKnownInPredecessorsImpl() argument
563 const DataLayout &DL = BB->getDataLayout(); in computeValueKnownInPredecessorsImpl()
574 for (BasicBlock *Pred : predecessors(BB)) in computeValueKnownInPredecessorsImpl()
583 if (!I || I->getParent() != BB) { in computeValueKnownInPredecessorsImpl()
587 for (BasicBlock *P : predecessors(BB)) { in computeValueKnownInPredecessorsImpl()
591 Constant *PredCst = LVI->getConstantOnEdge(V, P, BB, CxtI); in computeValueKnownInPredecessorsImpl()
600 PredCst = LVI->getPredicateOnEdge(Pred, Val, Cst, P, BB, CxtI); in computeValueKnownInPredecessorsImpl()
617 BB, CxtI); in computeValueKnownInPredecessorsImpl()
630 computeValueKnownInPredecessorsImpl(Source, BB, Vals, Preference, in computeValueKnownInPredecessorsImpl()
646 computeValueKnownInPredecessorsImpl(Source, BB, Result, Preference, in computeValueKnownInPredecessorsImpl()
668 computeValueKnownInPredecessorsImpl(Op0, BB, LHSVals, WantInteger, in computeValueKnownInPredecessorsImpl()
670 computeValueKnownInPredecessorsImpl(Op1, BB, RHSVals, WantInteger, in computeValueKnownInPredecessorsImpl()
706 computeValueKnownInPredecessorsImpl(I->getOperand(0), BB, Result, in computeValueKnownInPredecessorsImpl()
724 computeValueKnownInPredecessorsImpl(BO->getOperand(0), BB, LHSVals, in computeValueKnownInPredecessorsImpl()
756 if (PN && PN->getParent() == BB && !LoopHeaders.contains(BB)) { in computeValueKnownInPredecessorsImpl()
765 RHS = CmpRHS->DoPHITranslation(BB, PredBB); in computeValueKnownInPredecessorsImpl()
767 LHS = CmpLHS->DoPHITranslation(BB, PredBB); in computeValueKnownInPredecessorsImpl()
775 // getPredicateOnEdge call will make no sense if LHS is defined in BB. in computeValueKnownInPredecessorsImpl()
777 if (LHSInst && LHSInst->getParent() == BB) in computeValueKnownInPredecessorsImpl()
781 BB, CxtI ? CxtI : Cmp); in computeValueKnownInPredecessorsImpl()
797 cast<Instruction>(CmpLHS)->getParent() != BB) { in computeValueKnownInPredecessorsImpl()
798 for (BasicBlock *P : predecessors(BB)) { in computeValueKnownInPredecessorsImpl()
801 Constant *Res = LVI->getPredicateOnEdge(Pred, CmpLHS, CmpConst, P, BB, in computeValueKnownInPredecessorsImpl()
821 cast<Instruction>(AddLHS)->getParent() != BB) { in computeValueKnownInPredecessorsImpl()
822 for (BasicBlock *P : predecessors(BB)) { in computeValueKnownInPredecessorsImpl()
827 AddLHS, P, BB, CxtI ? CxtI : cast<Instruction>(CmpLHS)); in computeValueKnownInPredecessorsImpl()
854 computeValueKnownInPredecessorsImpl(I->getOperand(0), BB, LHSVals, in computeValueKnownInPredecessorsImpl()
876 computeValueKnownInPredecessorsImpl(SI->getCondition(), BB, Conds, in computeValueKnownInPredecessorsImpl()
904 assert(CxtI->getParent() == BB && "CxtI should be in BB"); in computeValueKnownInPredecessorsImpl()
907 for (BasicBlock *Pred : predecessors(BB)) in computeValueKnownInPredecessorsImpl()
919 static unsigned getBestDestForJumpOnUndef(BasicBlock *BB) { in getBestDestForJumpOnUndef() argument
920 Instruction *BBTerm = BB->getTerminator(); in getBestDestForJumpOnUndef()
937 static bool hasAddressTakenAndUsed(BasicBlock *BB) { in hasAddressTakenAndUsed() argument
938 if (!BB->hasAddressTaken()) return false; in hasAddressTakenAndUsed()
942 BlockAddress *BA = BlockAddress::get(BB); in hasAddressTakenAndUsed()
949 bool JumpThreadingPass::processBlock(BasicBlock *BB) { in processBlock() argument
952 if (DTU->isBBPendingDeletion(BB) || in processBlock()
953 (pred_empty(BB) && BB != &BB->getParent()->getEntryBlock())) in processBlock()
960 if (maybeMergeBasicBlockIntoOnlyPred(BB)) in processBlock()
963 if (tryToUnfoldSelectInCurrBB(BB)) in processBlock()
967 if (HasGuards && processGuards(BB)) in processBlock()
976 Instruction *Terminator = BB->getTerminator(); in processBlock()
999 ConstantFoldInstruction(I, BB->getDataLayout(), TLI); in processBlock()
1014 unsigned BestSucc = getBestDestForJumpOnUndef(BB); in processBlock()
1018 Instruction *BBTerm = BB->getTerminator(); in processBlock()
1023 Succ->removePredecessor(BB, true); in processBlock()
1024 Updates.push_back({DominatorTree::Delete, BB, Succ}); in processBlock()
1027 LLVM_DEBUG(dbgs() << " In block '" << BB->getName() in processBlock()
1043 LLVM_DEBUG(dbgs() << " In block '" << BB->getName() in processBlock()
1044 << "' folding terminator: " << *BB->getTerminator() in processBlock()
1047 ConstantFoldTerminator(BB, true, nullptr, DTU.get()); in processBlock()
1049 BPI->eraseBlock(BB); in processBlock()
1058 if (processThreadableEdges(Condition, BB, Preference, Terminator)) in processBlock()
1075 CondConst, BB->getTerminator(), in processBlock()
1085 if (replaceFoldableUses(CondCmp, Res, BB)) in processBlock()
1091 if (tryToUnfoldSelect(CondCmp, BB)) in processBlock()
1096 if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) in processBlock()
1097 if (tryToUnfoldSelect(SI, BB)) in processBlock()
1118 if (PN->getParent() == BB && isa<BranchInst>(BB->getTerminator())) in processBlock()
1119 updatePredecessorProfileMetadata(PN, BB); in processBlock()
1124 if (processThreadableEdges(CondInst, BB, Preference, Terminator)) in processBlock()
1130 if (PN && PN->getParent() == BB && isa<BranchInst>(BB->getTerminator())) in processBlock()
1135 CondInst->getParent() == BB && isa<BranchInst>(BB->getTerminator())) in processBlock()
1139 // conditional branch leaving BB. in processBlock()
1140 if (processImpliedCondition(BB)) in processBlock()
1146 bool JumpThreadingPass::processImpliedCondition(BasicBlock *BB) { in processImpliedCondition() argument
1147 auto *BI = dyn_cast<BranchInst>(BB->getTerminator()); in processImpliedCondition()
1163 BasicBlock *CurrentBB = BB; in processImpliedCondition()
1164 BasicBlock *CurrentPred = BB->getSinglePredecessor(); in processImpliedCondition()
1167 auto &DL = BB->getDataLayout(); in processImpliedCondition()
1180 // If the branch condition of BB (which is Cond) and CurrentPred are in processImpliedCondition()
1191 RemoveSucc->removePredecessor(BB); in processImpliedCondition()
1199 DTU->applyUpdatesPermissive({{DominatorTree::Delete, BB, RemoveSucc}}); in processImpliedCondition()
1201 BPI->eraseBlock(BB); in processImpliedCondition()
1212 static bool isOpDefinedInBlock(Value *Op, BasicBlock *BB) { in isOpDefinedInBlock() argument
1214 if (OpInst->getParent() == BB) in isOpDefinedInBlock()
1467 findMostPopularDest(BasicBlock *BB, in findMostPopularDest() argument
1483 for (auto *SuccBB : successors(BB)) in findMostPopularDest()
1498 // BB->getSinglePredecessor() and then on to BB.
1499 Constant *JumpThreadingPass::evaluateOnPredecessorEdge(BasicBlock *BB, in evaluateOnPredecessorEdge() argument
1503 BasicBlock *PredBB = BB->getSinglePredecessor(); in evaluateOnPredecessorEdge()
1510 // Consult LVI if V is not an instruction in BB or PredBB. in evaluateOnPredecessorEdge()
1512 if (!I || (I->getParent() != BB && I->getParent() != PredBB)) { in evaluateOnPredecessorEdge()
1525 if (CondCmp->getParent() == BB) { in evaluateOnPredecessorEdge()
1527 evaluateOnPredecessorEdge(BB, PredPredBB, CondCmp->getOperand(0), DL); in evaluateOnPredecessorEdge()
1529 evaluateOnPredecessorEdge(BB, PredPredBB, CondCmp->getOperand(1), DL); in evaluateOnPredecessorEdge()
1541 bool JumpThreadingPass::processThreadableEdges(Value *Cond, BasicBlock *BB, in processThreadableEdges() argument
1546 if (LoopHeaders.count(BB)) in processThreadableEdges()
1550 if (!computeValueKnownInPredecessors(Cond, BB, PredValues, Preference, in processThreadableEdges()
1553 // BB and its sole predecessor. in processThreadableEdges()
1554 return maybethreadThroughTwoBasicBlocks(BB, Cond); in processThreadableEdges()
1560 LLVM_DEBUG(dbgs() << "IN BB: " << *BB; in processThreadableEdges()
1562 dbgs() << " BB '" << BB->getName() in processThreadableEdges()
1589 else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) { in processThreadableEdges()
1592 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) { in processThreadableEdges()
1596 assert(isa<IndirectBrInst>(BB->getTerminator()) in processThreadableEdges()
1631 if (BB->hasNPredecessors(PredToDestList.size())) { in processThreadableEdges()
1634 Updates.reserve(BB->getTerminator()->getNumSuccessors() - 1); in processThreadableEdges()
1635 for (BasicBlock *SuccBB : successors(BB)) { in processThreadableEdges()
1639 SuccBB->removePredecessor(BB, true); // This is unreachable successor. in processThreadableEdges()
1640 Updates.push_back({DominatorTree::Delete, BB, SuccBB}); in processThreadableEdges()
1645 Instruction *Term = BB->getTerminator(); in processThreadableEdges()
1652 BPI->eraseBlock(BB); in processThreadableEdges()
1667 replaceFoldableUses(CondInst, OnlyVal, BB); in processThreadableEdges()
1691 MostPopularDest = findMostPopularDest(BB, PredToDestList); in processThreadableEdges()
1705 if (Succ == BB) in processThreadableEdges()
1712 MostPopularDest = BB->getTerminator()-> in processThreadableEdges()
1713 getSuccessor(getBestDestForJumpOnUndef(BB)); in processThreadableEdges()
1716 return tryThreadEdge(BB, PredsToFactor, MostPopularDest); in processThreadableEdges()
1723 BasicBlock *BB = PN->getParent(); in processBranchOnPHI() local
1742 // Try to duplicate BB into PredBB. in processBranchOnPHI()
1743 if (duplicateCondBranchOnPHIIntoPred(BB, PredBBs)) in processBranchOnPHI()
1755 BasicBlock *BB = BO->getParent(); in processBranchOnXOR() local
1763 // If the first instruction in BB isn't a phi, we won't be able to infer in processBranchOnXOR()
1765 if (!isa<PHINode>(BB->front())) in processBranchOnXOR()
1768 // If this BB is a landing pad, we won't be able to split the edge into it. in processBranchOnXOR()
1769 if (BB->isEHPad()) in processBranchOnXOR()
1779 // BB: in processBranchOnXOR()
1786 // BB': in processBranchOnXOR()
1792 if (!computeValueKnownInPredecessors(BO->getOperand(0), BB, XorOpValues, in processBranchOnXOR()
1795 if (!computeValueKnownInPredecessors(BO->getOperand(1), BB, XorOpValues, in processBranchOnXOR()
1820 SplitVal = ConstantInt::getTrue(BB->getContext()); in processBranchOnXOR()
1822 SplitVal = ConstantInt::getFalse(BB->getContext()); in processBranchOnXOR()
1837 cast<PHINode>(BB->front()).getNumIncomingValues()) { in processBranchOnXOR()
1861 // Try to duplicate BB into PredBB. in processBranchOnXOR()
1862 return duplicateCondBranchOnPHIIntoPred(BB, BlocksToFoldInto); in processBranchOnXOR()
1888 /// Merge basic block BB into its sole predecessor if possible.
1889 bool JumpThreadingPass::maybeMergeBasicBlockIntoOnlyPred(BasicBlock *BB) { in maybeMergeBasicBlockIntoOnlyPred() argument
1890 BasicBlock *SinglePred = BB->getSinglePredecessor(); in maybeMergeBasicBlockIntoOnlyPred()
1896 SinglePred == BB || hasAddressTakenAndUsed(BB)) in maybeMergeBasicBlockIntoOnlyPred()
1899 // If SinglePred was a loop header, BB becomes one. in maybeMergeBasicBlockIntoOnlyPred()
1901 LoopHeaders.insert(BB); in maybeMergeBasicBlockIntoOnlyPred()
1904 MergeBasicBlockIntoOnlyPred(BB, DTU.get()); in maybeMergeBasicBlockIntoOnlyPred()
1906 // Now that BB is merged into SinglePred (i.e. SinglePred code followed by in maybeMergeBasicBlockIntoOnlyPred()
1907 // BB code within one basic block `BB`), we need to invalidate the LVI in maybeMergeBasicBlockIntoOnlyPred()
1908 // information associated with BB, because the LVI information need not be in maybeMergeBasicBlockIntoOnlyPred()
1909 // true for all of BB after the merge. For example, in maybeMergeBasicBlockIntoOnlyPred()
1915 // br label %BB in maybeMergeBasicBlockIntoOnlyPred()
1916 // BB: <LVI info2 for %p val, i.e. %p is true> in maybeMergeBasicBlockIntoOnlyPred()
1920 // Note that this LVI info for blocks BB and SinglPred is correct for %p in maybeMergeBasicBlockIntoOnlyPred()
1923 // BB: <LVI info2 for %p val> in maybeMergeBasicBlockIntoOnlyPred()
1929 // LVI info2 for BB is incorrect at the beginning of BB. in maybeMergeBasicBlockIntoOnlyPred()
1931 // Invalidate LVI information for BB if the LVI is not provably true for in maybeMergeBasicBlockIntoOnlyPred()
1932 // all of BB. in maybeMergeBasicBlockIntoOnlyPred()
1933 if (!isGuaranteedToTransferExecutionToSuccessor(BB)) in maybeMergeBasicBlockIntoOnlyPred()
1934 LVI->eraseBlock(BB); in maybeMergeBasicBlockIntoOnlyPred()
1938 /// Update the SSA form. NewBB contains instructions that are copied from BB.
1939 /// ValueMapping maps old values in BB to new ones in NewBB.
1940 void JumpThreadingPass::updateSSA(BasicBlock *BB, BasicBlock *NewBB, in updateSSA() argument
1942 // If there were values defined in BB that are used outside the block, then we in updateSSA()
1951 for (Instruction &I : *BB) { in updateSSA()
1957 if (UserPN->getIncomingBlock(U) == BB) in updateSSA()
1959 } else if (User->getParent() == BB) in updateSSA()
1968 return DbgVal->getParent() == BB; in updateSSA()
1971 return DbgVarRec->getParent() == BB; in updateSSA()
1979 // We found a use of I outside of BB. Rename all uses of I that are outside in updateSSA()
1983 SSAUpdate.AddAvailableValue(BB, &I); in updateSSA()
2119 bool JumpThreadingPass::maybethreadThroughTwoBasicBlocks(BasicBlock *BB, in maybethreadThroughTwoBasicBlocks() argument
2126 // br i1 %tobool, label %BB, label ... in maybethreadThroughTwoBasicBlocks()
2128 // BB: in maybethreadThroughTwoBasicBlocks()
2132 // We don't know the value of %var at BB even if we know which incoming edge in maybethreadThroughTwoBasicBlocks()
2133 // we take to BB. However, once we duplicate PredBB for each of its incoming in maybethreadThroughTwoBasicBlocks()
2135 // PredBB. Then we can thread edges PredBB1->BB and PredBB2->BB through BB. in maybethreadThroughTwoBasicBlocks()
2137 // Require that BB end with a Branch for simplicity. in maybethreadThroughTwoBasicBlocks()
2138 BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator()); in maybethreadThroughTwoBasicBlocks()
2142 // BB must have exactly one predecessor. in maybethreadThroughTwoBasicBlocks()
2143 BasicBlock *PredBB = BB->getSinglePredecessor(); in maybethreadThroughTwoBasicBlocks()
2148 // unconditional branch, we should be merging PredBB and BB instead. For in maybethreadThroughTwoBasicBlocks()
2161 // PredPredBB through PredBB and BB to SuccBB with PredBB containing a in maybethreadThroughTwoBasicBlocks()
2163 // could duplicate PredBB and BB as, say, PredBB.thread and BB.thread. Since in maybethreadThroughTwoBasicBlocks()
2166 // and BB to SuccBB. This jump threading would repeatedly occur. That is, we in maybethreadThroughTwoBasicBlocks()
2180 // successor edge out of BB to which we thread exactly one incoming edge into in maybethreadThroughTwoBasicBlocks()
2186 const DataLayout &DL = BB->getDataLayout(); in maybethreadThroughTwoBasicBlocks()
2192 evaluateOnPredecessorEdge(BB, P, Cond, DL))) { in maybethreadThroughTwoBasicBlocks()
2216 if (SuccBB == BB) { in maybethreadThroughTwoBasicBlocks()
2217 LLVM_DEBUG(dbgs() << " Not threading across BB '" << BB->getName() in maybethreadThroughTwoBasicBlocks()
2224 if (LoopHeaders.count(BB) || LoopHeaders.count(SuccBB)) { in maybethreadThroughTwoBasicBlocks()
2226 bool BBIsHeader = LoopHeaders.count(BB); in maybethreadThroughTwoBasicBlocks()
2229 << (BBIsHeader ? "loop header BB '" : "block BB '") in maybethreadThroughTwoBasicBlocks()
2230 << BB->getName() << "' to dest " in maybethreadThroughTwoBasicBlocks()
2231 << (SuccIsHeader ? "loop header BB '" : "block BB '") in maybethreadThroughTwoBasicBlocks()
2238 // Compute the cost of duplicating BB and PredBB. in maybethreadThroughTwoBasicBlocks()
2240 TTI, BB, BB->getTerminator(), BBDupThreshold); in maybethreadThroughTwoBasicBlocks()
2249 LLVM_DEBUG(dbgs() << " Not threading BB '" << BB->getName() in maybethreadThroughTwoBasicBlocks()
2251 << " for PredBB, " << BBCost << "for BB\n"); in maybethreadThroughTwoBasicBlocks()
2256 threadThroughTwoBasicBlocks(PredPredBB, PredBB, BB, SuccBB); in maybethreadThroughTwoBasicBlocks()
2262 BasicBlock *BB, in threadThroughTwoBasicBlocks() argument
2265 << BB->getName() << "'\n"); in threadThroughTwoBasicBlocks()
2268 bool HasProfile = doesBlockHaveProfileData(BB); in threadThroughTwoBasicBlocks()
2272 BranchInst *CondBr = cast<BranchInst>(BB->getTerminator()); in threadThroughTwoBasicBlocks()
2288 // We are going to have to map operands from the original BB block to the new in threadThroughTwoBasicBlocks()
2329 threadEdge(BB, PredsToFactor, SuccBB); in threadThroughTwoBasicBlocks()
2334 BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs, in tryThreadEdge() argument
2337 if (SuccBB == BB) { in tryThreadEdge()
2338 LLVM_DEBUG(dbgs() << " Not threading across BB '" << BB->getName() in tryThreadEdge()
2345 if (LoopHeaders.count(BB) || LoopHeaders.count(SuccBB)) { in tryThreadEdge()
2347 bool BBIsHeader = LoopHeaders.count(BB); in tryThreadEdge()
2350 << (BBIsHeader ? "loop header BB '" : "block BB '") << BB->getName() in tryThreadEdge()
2351 << "' to dest " << (SuccIsHeader ? "loop header BB '" : "block BB '") in tryThreadEdge()
2358 TTI, BB, BB->getTerminator(), BBDupThreshold); in tryThreadEdge()
2360 LLVM_DEBUG(dbgs() << " Not threading BB '" << BB->getName() in tryThreadEdge()
2365 threadEdge(BB, PredBBs, SuccBB); in tryThreadEdge()
2371 /// across BB. Transform the IR to reflect this change.
2372 void JumpThreadingPass::threadEdge(BasicBlock *BB, in threadEdge() argument
2375 assert(SuccBB != BB && "Don't create an infinite loop"); in threadEdge()
2377 assert(!LoopHeaders.count(BB) && !LoopHeaders.count(SuccBB) && in threadEdge()
2381 bool HasProfile = doesBlockHaveProfileData(BB); in threadEdge()
2392 PredBB = splitBlockPreds(BB, PredBBs, ".thr_comm"); in threadEdge()
2398 << ", across block:\n " << *BB << "\n"); in threadEdge()
2400 LVI->threadEdge(PredBB, BB, SuccBB); in threadEdge()
2402 BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), in threadEdge()
2403 BB->getName()+".thread", in threadEdge()
2404 BB->getParent(), BB); in threadEdge()
2411 BFI->getBlockFreq(PredBB) * BPI->getEdgeProbability(PredBB, BB); in threadEdge()
2415 // Copy all the instructions from BB to NewBB except the terminator. in threadEdge()
2417 cloneInstructions(ValueMapping, BB->begin(), std::prev(BB->end()), NewBB, in threadEdge()
2420 // We didn't copy the terminator from BB over to NewBB, because there is now in threadEdge()
2423 NewBI->setDebugLoc(BB->getTerminator()->getDebugLoc()); in threadEdge()
2427 addPHINodeEntriesForMappedBlock(SuccBB, BB, NewBB, ValueMapping); in threadEdge()
2429 // Update the terminator of PredBB to jump to NewBB instead of BB. This in threadEdge()
2430 // eliminates predecessors from BB, which requires us to simplify any PHI in threadEdge()
2431 // nodes in BB. in threadEdge()
2434 if (PredTerm->getSuccessor(i) == BB) { in threadEdge()
2435 BB->removePredecessor(PredBB, true); in threadEdge()
2442 {DominatorTree::Delete, PredBB, BB}}); in threadEdge()
2444 updateSSA(BB, NewBB, ValueMapping); in threadEdge()
2451 // Update the edge weight from BB to SuccBB, which should be less than before. in threadEdge()
2452 updateBlockFreqAndEdgeWeight(PredBB, BB, NewBB, SuccBB, BFI, BPI, HasProfile); in threadEdge()
2458 /// Create a new basic block that will be the predecessor of BB and successor of
2461 BasicBlock *JumpThreadingPass::splitBlockPreds(BasicBlock *BB, in splitBlockPreds() argument
2466 // Collect the frequencies of all predecessors of BB, which will be used to in splitBlockPreds()
2474 Pred, BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, BB))); in splitBlockPreds()
2477 // In the case when BB is a LandingPad block we create 2 new predecessors in splitBlockPreds()
2479 if (BB->isLandingPad()) { in splitBlockPreds()
2481 SplitLandingPadPredecessors(BB, Preds, Suffix, NewName.c_str(), NewBBs); in splitBlockPreds()
2483 NewBBs.push_back(SplitBlockPredecessors(BB, Preds, Suffix)); in splitBlockPreds()
2490 Updates.push_back({DominatorTree::Insert, NewBB, BB}); in splitBlockPreds()
2492 Updates.push_back({DominatorTree::Delete, Pred, BB}); in splitBlockPreds()
2505 bool JumpThreadingPass::doesBlockHaveProfileData(BasicBlock *BB) { in doesBlockHaveProfileData() argument
2506 const Instruction *TI = BB->getTerminator(); in doesBlockHaveProfileData()
2513 /// Update the block frequency of BB and branch weight and the metadata on the
2514 /// edge BB->SuccBB. This is done by scaling the weight of BB->SuccBB by 1 -
2515 /// Freq(PredBB->BB) / Freq(BB->SuccBB).
2517 BasicBlock *BB, in updateBlockFreqAndEdgeWeight() argument
2532 // As the edge from PredBB to BB is deleted, we have to update the block in updateBlockFreqAndEdgeWeight()
2533 // frequency of BB. in updateBlockFreqAndEdgeWeight()
2534 auto BBOrigFreq = BFI->getBlockFreq(BB); in updateBlockFreqAndEdgeWeight()
2536 auto BB2SuccBBFreq = BBOrigFreq * BPI->getEdgeProbability(BB, SuccBB); in updateBlockFreqAndEdgeWeight()
2538 BFI->setBlockFreq(BB, BBNewFreq); in updateBlockFreqAndEdgeWeight()
2540 // Collect updated outgoing edges' frequencies from BB and use them to update in updateBlockFreqAndEdgeWeight()
2543 for (BasicBlock *Succ : successors(BB)) { in updateBlockFreqAndEdgeWeight()
2546 : BBOrigFreq * BPI->getEdgeProbability(BB, Succ); in updateBlockFreqAndEdgeWeight()
2566 BPI->setEdgeProbability(BB, BBSuccProbs); in updateBlockFreqAndEdgeWeight()
2607 auto TI = BB->getTerminator(); in updateBlockFreqAndEdgeWeight()
2613 /// to BB which contains an i1 PHI node and a conditional branch on that PHI.
2614 /// If we can duplicate the contents of BB up into PredBB do so now, this
2618 BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs) { in duplicateCondBranchOnPHIIntoPred() argument
2621 // If BB is a loop header, then duplicating this block outside the loop would in duplicateCondBranchOnPHIIntoPred()
2624 if (LoopHeaders.count(BB)) { in duplicateCondBranchOnPHIIntoPred()
2625 LLVM_DEBUG(dbgs() << " Not duplicating loop header '" << BB->getName() in duplicateCondBranchOnPHIIntoPred()
2632 TTI, BB, BB->getTerminator(), BBDupThreshold); in duplicateCondBranchOnPHIIntoPred()
2634 LLVM_DEBUG(dbgs() << " Not duplicating BB '" << BB->getName() in duplicateCondBranchOnPHIIntoPred()
2647 PredBB = splitBlockPreds(BB, PredBBs, ".thr_comm"); in duplicateCondBranchOnPHIIntoPred()
2649 Updates.push_back({DominatorTree::Delete, PredBB, BB}); in duplicateCondBranchOnPHIIntoPred()
2651 // Okay, we decided to do this! Clone all the instructions in BB onto the end in duplicateCondBranchOnPHIIntoPred()
2653 LLVM_DEBUG(dbgs() << " Duplicating block '" << BB->getName() in duplicateCondBranchOnPHIIntoPred()
2656 << DuplicationCost << " block is:" << *BB << "\n"); in duplicateCondBranchOnPHIIntoPred()
2659 // can just clone the bits from BB into the end of the new PredBB. in duplicateCondBranchOnPHIIntoPred()
2664 PredBB = SplitEdge(OldPredBB, BB); in duplicateCondBranchOnPHIIntoPred()
2666 Updates.push_back({DominatorTree::Insert, PredBB, BB}); in duplicateCondBranchOnPHIIntoPred()
2667 Updates.push_back({DominatorTree::Delete, OldPredBB, BB}); in duplicateCondBranchOnPHIIntoPred()
2671 // We are going to have to map operands from the original BB block into the in duplicateCondBranchOnPHIIntoPred()
2672 // PredBB block. Evaluate PHI nodes in BB. in duplicateCondBranchOnPHIIntoPred()
2675 BasicBlock::iterator BI = BB->begin(); in duplicateCondBranchOnPHIIntoPred()
2678 // Clone the non-phi instructions of BB into PredBB, keeping track of the in duplicateCondBranchOnPHIIntoPred()
2680 for (; BI != BB->end(); ++BI) { in duplicateCondBranchOnPHIIntoPred()
2700 {BB->getDataLayout(), TLI, nullptr, nullptr, New})) { in duplicateCondBranchOnPHIIntoPred()
2726 BranchInst *BBBranch = cast<BranchInst>(BB->getTerminator()); in duplicateCondBranchOnPHIIntoPred()
2727 addPHINodeEntriesForMappedBlock(BBBranch->getSuccessor(0), BB, PredBB, in duplicateCondBranchOnPHIIntoPred()
2729 addPHINodeEntriesForMappedBlock(BBBranch->getSuccessor(1), BB, PredBB, in duplicateCondBranchOnPHIIntoPred()
2732 updateSSA(BB, PredBB, ValueMapping); in duplicateCondBranchOnPHIIntoPred()
2734 // PredBB no longer jumps to BB, remove entries in the PHI node for the edge in duplicateCondBranchOnPHIIntoPred()
2736 BB->removePredecessor(PredBB, true); in duplicateCondBranchOnPHIIntoPred()
2741 BPI->copyEdgeProbabilities(BB, PredBB); in duplicateCondBranchOnPHIIntoPred()
2748 // Pred is a predecessor of BB with an unconditional branch to BB. SI is
2749 // a Select instruction in Pred. BB has other predecessors and SI is used in
2750 // a PHI node in BB. SI has no other use.
2753 void JumpThreadingPass::unfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB, in unfoldSelectInstr() argument
2764 // BB in unfoldSelectInstr()
2766 BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "select.unfold", in unfoldSelectInstr()
2767 BB->getParent(), BB); in unfoldSelectInstr()
2772 auto *BI = BranchInst::Create(NewBB, BB, SI->getCondition(), Pred); in unfoldSelectInstr()
2806 DTU->applyUpdatesPermissive({{DominatorTree::Insert, NewBB, BB}, in unfoldSelectInstr()
2809 // Update any other PHI nodes in BB. in unfoldSelectInstr()
2810 for (BasicBlock::iterator BI = BB->begin(); in unfoldSelectInstr()
2816 bool JumpThreadingPass::tryToUnfoldSelect(SwitchInst *SI, BasicBlock *BB) { in tryToUnfoldSelect() argument
2819 if (!CondPHI || CondPHI->getParent() != BB) in tryToUnfoldSelect()
2836 unfoldSelectInstr(Pred, BB, PredSI, CondPHI, I); in tryToUnfoldSelect()
2854 bool JumpThreadingPass::tryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB) { in tryToUnfoldSelect() argument
2855 BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator()); in tryToUnfoldSelect()
2860 CondLHS->getParent() != BB) in tryToUnfoldSelect()
2877 // terminator in BB. We don't do the transform if both sides fold, those in tryToUnfoldSelect()
2881 CondRHS, Pred, BB, CondCmp); in tryToUnfoldSelect()
2884 CondRHS, Pred, BB, CondCmp); in tryToUnfoldSelect()
2886 unfoldSelectInstr(Pred, BB, SI, CondLHS, I); in tryToUnfoldSelect()
2894 /// same BB in the form
2895 /// bb:
2901 /// bb:
2907 /// jump-threading over bb in this pass.
2913 bool JumpThreadingPass::tryToUnfoldSelectInCurrBB(BasicBlock *BB) { in tryToUnfoldSelectInCurrBB() argument
2916 if (BB->getParent()->hasFnAttribute(Attribute::SanitizeMemory)) in tryToUnfoldSelectInCurrBB()
2921 if (LoopHeaders.count(BB)) in tryToUnfoldSelectInCurrBB()
2924 for (BasicBlock::iterator BI = BB->begin(); in tryToUnfoldSelectInCurrBB()
2931 auto isUnfoldCandidate = [BB](SelectInst *SI, Value *V) { in tryToUnfoldSelectInCurrBB()
2934 // Check if SI is in BB and use V as condition. in tryToUnfoldSelectInCurrBB()
2935 if (SI->getParent() != BB) in tryToUnfoldSelectInCurrBB()
2945 // Look for a ICmp in BB that compares PN with a constant and is the in tryToUnfoldSelectInCurrBB()
2947 if (Cmp->getParent() == BB && Cmp->hasOneUse() && in tryToUnfoldSelectInCurrBB()
2955 // Look for a Select in BB that uses PN as condition. in tryToUnfoldSelectInCurrBB()
2976 NewPN->addIncoming(SI->getFalseValue(), BB); in tryToUnfoldSelectInCurrBB()
2983 Updates.push_back({DominatorTree::Insert, BB, SplitBB}); in tryToUnfoldSelectInCurrBB()
2984 Updates.push_back({DominatorTree::Insert, BB, NewBB}); in tryToUnfoldSelectInCurrBB()
2986 // BB's successors were moved to SplitBB, update DTU accordingly. in tryToUnfoldSelectInCurrBB()
2988 Updates.push_back({DominatorTree::Delete, BB, Succ}); in tryToUnfoldSelectInCurrBB()
2997 /// Try to propagate a guard from the current BB into one of its predecessors
3016 bool JumpThreadingPass::processGuards(BasicBlock *BB) { in processGuards() argument
3021 auto PI = pred_begin(BB), PE = pred_end(BB); in processGuards()
3040 for (auto &I : *BB) in processGuards()
3041 if (isGuard(&I) && threadGuard(BB, cast<IntrinsicInst>(&I), BI)) in processGuards()
3047 /// Try to propagate the guard from BB which is the lower block of a diamond
3050 bool JumpThreadingPass::threadGuard(BasicBlock *BB, IntrinsicInst *Guard, in threadGuard() argument
3059 auto &DL = BB->getDataLayout(); in threadGuard()
3083 getJumpThreadDuplicationCost(TTI, BB, AfterGuard, BBDupThreshold); in threadGuard()
3089 BB, PredGuardedBlock, AfterGuard, GuardedMapping, *DTU); in threadGuard()
3095 BB, PredUnguardedBlock, Guard, UnguardedMapping, *DTU); in threadGuard()
3103 for (auto BI = BB->begin(); &*BI != AfterGuard; ++BI) in threadGuard()
3107 BasicBlock::iterator InsertionPoint = BB->getFirstInsertionPt(); in threadGuard()
3108 assert(InsertionPoint != BB->end() && "Empty block?"); in threadGuard()