Lines Matching refs:BB
146 bool ProcessBlock(BasicBlock *BB);
147 bool ThreadEdge(BasicBlock *BB, const SmallVectorImpl<BasicBlock*> &PredBBs,
149 bool DuplicateCondBranchOnPHIIntoPred(BasicBlock *BB,
152 bool ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB,
156 bool ProcessThreadableEdges(Value *Cond, BasicBlock *BB,
162 bool ProcessImpliedCondition(BasicBlock *BB);
165 bool TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB);
168 BasicBlock *SplitBlockPreds(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,
170 void UpdateBlockFreqAndEdgeWeight(BasicBlock *PredBB, BasicBlock *BB,
221 BasicBlock *BB = &*I; in runOnFunction() local
223 while (ProcessBlock(BB)) in runOnFunction()
230 if (pred_empty(BB) && in runOnFunction()
231 BB != &BB->getParent()->getEntryBlock()) { in runOnFunction()
232 DEBUG(dbgs() << " JT: Deleting dead block '" << BB->getName() in runOnFunction()
233 << "' with terminator: " << *BB->getTerminator() << '\n'); in runOnFunction()
234 LoopHeaders.erase(BB); in runOnFunction()
235 LVI->eraseBlock(BB); in runOnFunction()
236 DeleteDeadBlock(BB); in runOnFunction()
241 BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); in runOnFunction()
247 BB != &BB->getParent()->getEntryBlock() && in runOnFunction()
249 BB->getFirstNonPHIOrDbg()->isTerminator()) { in runOnFunction()
253 bool ErasedFromLoopHeaders = LoopHeaders.erase(BB); in runOnFunction()
260 LVI->eraseBlock(BB); in runOnFunction()
261 if (TryToSimplifyUncondBranchFromEmptyBlock(BB)) { in runOnFunction()
265 BB = Succ; in runOnFunction()
269 LoopHeaders.insert(BB); in runOnFunction()
281 static unsigned getJumpThreadDuplicationCost(const BasicBlock *BB, in getJumpThreadDuplicationCost() argument
284 BasicBlock::const_iterator I(BB->getFirstNonPHI()); in getJumpThreadDuplicationCost()
307 if (I->getType()->isTokenTy() && I->isUsedOutsideOfBlock(BB)) in getJumpThreadDuplicationCost()
391 ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, PredValueInfo &Result, in ComputeValueKnownInPredecessors() argument
398 if (!RecursionSet.insert(std::make_pair(V, BB)).second) in ComputeValueKnownInPredecessors()
403 RecursionSetRemover remover(RecursionSet, std::make_pair(V, BB)); in ComputeValueKnownInPredecessors()
407 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) in ComputeValueKnownInPredecessors()
416 if (!I || I->getParent() != BB) { in ComputeValueKnownInPredecessors()
431 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { in ComputeValueKnownInPredecessors()
435 Constant *PredCst = LVI->getConstantOnEdge(V, P, BB, CxtI); in ComputeValueKnownInPredecessors()
452 BB, CxtI); in ComputeValueKnownInPredecessors()
470 ComputeValueKnownInPredecessors(I->getOperand(0), BB, LHSVals, in ComputeValueKnownInPredecessors()
472 ComputeValueKnownInPredecessors(I->getOperand(1), BB, RHSVals, in ComputeValueKnownInPredecessors()
513 ComputeValueKnownInPredecessors(I->getOperand(0), BB, Result, in ComputeValueKnownInPredecessors()
531 ComputeValueKnownInPredecessors(BO->getOperand(0), BB, LHSVals, in ComputeValueKnownInPredecessors()
551 if (PN && PN->getParent() == BB) { in ComputeValueKnownInPredecessors()
558 Value *RHS = Cmp->getOperand(1)->DoPHITranslation(BB, PredBB); in ComputeValueKnownInPredecessors()
567 cast<Constant>(RHS), PredBB, BB, in ComputeValueKnownInPredecessors()
585 cast<Instruction>(Cmp->getOperand(0))->getParent() != BB) { in ComputeValueKnownInPredecessors()
588 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB);PI != E; ++PI){ in ComputeValueKnownInPredecessors()
594 RHSCst, P, BB, CxtI ? CxtI : Cmp); in ComputeValueKnownInPredecessors()
609 ComputeValueKnownInPredecessors(I->getOperand(0), BB, LHSVals, in ComputeValueKnownInPredecessors()
632 ComputeValueKnownInPredecessors(SI->getCondition(), BB, Conds, in ComputeValueKnownInPredecessors()
660 Constant *CI = LVI->getConstant(V, BB, CxtI); in ComputeValueKnownInPredecessors()
662 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) in ComputeValueKnownInPredecessors()
677 static unsigned GetBestDestForJumpOnUndef(BasicBlock *BB) { in GetBestDestForJumpOnUndef() argument
678 TerminatorInst *BBTerm = BB->getTerminator(); in GetBestDestForJumpOnUndef()
695 static bool hasAddressTakenAndUsed(BasicBlock *BB) { in hasAddressTakenAndUsed() argument
696 if (!BB->hasAddressTaken()) return false; in hasAddressTakenAndUsed()
700 BlockAddress *BA = BlockAddress::get(BB); in hasAddressTakenAndUsed()
707 bool JumpThreading::ProcessBlock(BasicBlock *BB) { in ProcessBlock() argument
710 if (pred_empty(BB) && in ProcessBlock()
711 BB != &BB->getParent()->getEntryBlock()) in ProcessBlock()
718 if (BasicBlock *SinglePred = BB->getSinglePredecessor()) { in ProcessBlock()
721 SinglePred != BB && !hasAddressTakenAndUsed(BB)) { in ProcessBlock()
724 LoopHeaders.insert(BB); in ProcessBlock()
727 MergeBasicBlockIntoOnlyPred(BB); in ProcessBlock()
739 Instruction *Terminator = BB->getTerminator(); in ProcessBlock()
759 ConstantFoldInstruction(I, BB->getModule()->getDataLayout(), TLI); in ProcessBlock()
770 unsigned BestSucc = GetBestDestForJumpOnUndef(BB); in ProcessBlock()
773 TerminatorInst *BBTerm = BB->getTerminator(); in ProcessBlock()
776 BBTerm->getSuccessor(i)->removePredecessor(BB, true); in ProcessBlock()
779 DEBUG(dbgs() << " In block '" << BB->getName() in ProcessBlock()
790 DEBUG(dbgs() << " In block '" << BB->getName() in ProcessBlock()
791 << "' folding terminator: " << *BB->getTerminator() << '\n'); in ProcessBlock()
793 ConstantFoldTerminator(BB, true); in ProcessBlock()
802 if (ProcessThreadableEdges(Condition, BB, Preference, Terminator)) in ProcessBlock()
813 BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator()); in ProcessBlock()
822 CondBr->getSuccessor(ToRemove)->removePredecessor(BB, true); in ProcessBlock()
827 else if (CondCmp->getParent() == BB) { in ProcessBlock()
840 if (CondBr && CondConst && TryToUnfoldSelect(CondCmp, BB)) in ProcessBlock()
865 if (ProcessThreadableEdges(CondInst, BB, Preference, Terminator)) in ProcessBlock()
871 if (PN->getParent() == BB && isa<BranchInst>(BB->getTerminator())) in ProcessBlock()
877 CondInst->getParent() == BB && isa<BranchInst>(BB->getTerminator())) in ProcessBlock()
882 if (ProcessImpliedCondition(BB)) in ProcessBlock()
888 bool JumpThreading::ProcessImpliedCondition(BasicBlock *BB) { in ProcessImpliedCondition() argument
889 auto *BI = dyn_cast<BranchInst>(BB->getTerminator()); in ProcessImpliedCondition()
894 BasicBlock *CurrentBB = BB; in ProcessImpliedCondition()
895 BasicBlock *CurrentPred = BB->getSinglePredecessor(); in ProcessImpliedCondition()
898 auto &DL = BB->getModule()->getDataLayout(); in ProcessImpliedCondition()
906 BI->getSuccessor(1)->removePredecessor(BB); in ProcessImpliedCondition()
1116 FindMostPopularDest(BasicBlock *BB, in FindMostPopularDest() argument
1158 TerminatorInst *TI = BB->getTerminator(); in FindMostPopularDest()
1175 bool JumpThreading::ProcessThreadableEdges(Value *Cond, BasicBlock *BB, in ProcessThreadableEdges() argument
1180 if (LoopHeaders.count(BB)) in ProcessThreadableEdges()
1184 if (!ComputeValueKnownInPredecessors(Cond, BB, PredValues, Preference, CxtI)) in ProcessThreadableEdges()
1190 DEBUG(dbgs() << "IN BB: " << *BB; in ProcessThreadableEdges()
1192 dbgs() << " BB '" << BB->getName() << "': FOUND condition = " in ProcessThreadableEdges()
1222 else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) in ProcessThreadableEdges()
1224 else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) { in ProcessThreadableEdges()
1227 assert(isa<IndirectBrInst>(BB->getTerminator()) in ProcessThreadableEdges()
1252 MostPopularDest = FindMostPopularDest(BB, PredToDestList); in ProcessThreadableEdges()
1266 if (PredTI->getSuccessor(i) == BB) in ProcessThreadableEdges()
1273 MostPopularDest = BB->getTerminator()-> in ProcessThreadableEdges()
1274 getSuccessor(GetBestDestForJumpOnUndef(BB)); in ProcessThreadableEdges()
1277 return ThreadEdge(BB, PredsToFactor, MostPopularDest); in ProcessThreadableEdges()
1285 BasicBlock *BB = PN->getParent(); in ProcessBranchOnPHI() local
1302 if (DuplicateCondBranchOnPHIIntoPred(BB, PredBBs)) in ProcessBranchOnPHI()
1315 BasicBlock *BB = BO->getParent(); in ProcessBranchOnXOR() local
1325 if (!isa<PHINode>(BB->front())) in ProcessBranchOnXOR()
1348 if (!ComputeValueKnownInPredecessors(BO->getOperand(0), BB, XorOpValues, in ProcessBranchOnXOR()
1351 if (!ComputeValueKnownInPredecessors(BO->getOperand(1), BB, XorOpValues, in ProcessBranchOnXOR()
1376 SplitVal = ConstantInt::getTrue(BB->getContext()); in ProcessBranchOnXOR()
1378 SplitVal = ConstantInt::getFalse(BB->getContext()); in ProcessBranchOnXOR()
1394 cast<PHINode>(BB->front()).getNumIncomingValues()) { in ProcessBranchOnXOR()
1412 return DuplicateCondBranchOnPHIIntoPred(BB, BlocksToFoldInto); in ProcessBranchOnXOR()
1443 bool JumpThreading::ThreadEdge(BasicBlock *BB, in ThreadEdge() argument
1447 if (SuccBB == BB) { in ThreadEdge()
1448 DEBUG(dbgs() << " Not threading across BB '" << BB->getName() in ThreadEdge()
1455 if (LoopHeaders.count(BB)) { in ThreadEdge()
1456 DEBUG(dbgs() << " Not threading across loop header BB '" << BB->getName() in ThreadEdge()
1462 unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB, BBDupThreshold); in ThreadEdge()
1464 DEBUG(dbgs() << " Not threading BB '" << BB->getName() in ThreadEdge()
1476 PredBB = SplitBlockPreds(BB, PredBBs, ".thr_comm"); in ThreadEdge()
1483 << *BB << "\n"); in ThreadEdge()
1485 LVI->threadEdge(PredBB, BB, SuccBB); in ThreadEdge()
1492 BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), in ThreadEdge()
1493 BB->getName()+".thread", in ThreadEdge()
1494 BB->getParent(), BB); in ThreadEdge()
1500 BFI->getBlockFreq(PredBB) * BPI->getEdgeProbability(PredBB, BB); in ThreadEdge()
1504 BasicBlock::iterator BI = BB->begin(); in ThreadEdge()
1528 NewBI->setDebugLoc(BB->getTerminator()->getDebugLoc()); in ThreadEdge()
1532 AddPHINodeEntriesForMappedBlock(SuccBB, BB, NewBB, ValueMapping); in ThreadEdge()
1540 for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) { in ThreadEdge()
1546 if (UserPN->getIncomingBlock(U) == BB) in ThreadEdge()
1548 } else if (User->getParent() == BB) in ThreadEdge()
1564 SSAUpdate.AddAvailableValue(BB, &*I); in ThreadEdge()
1578 if (PredTerm->getSuccessor(i) == BB) { in ThreadEdge()
1579 BB->removePredecessor(PredBB, true); in ThreadEdge()
1589 UpdateBlockFreqAndEdgeWeight(PredBB, BB, NewBB, SuccBB); in ThreadEdge()
1599 BasicBlock *JumpThreading::SplitBlockPreds(BasicBlock *BB, in SplitBlockPreds() argument
1607 PredBBFreq += BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, BB); in SplitBlockPreds()
1609 BasicBlock *PredBB = SplitBlockPredecessors(BB, Preds, Suffix); in SplitBlockPreds()
1622 BasicBlock *BB, in UpdateBlockFreqAndEdgeWeight() argument
1632 auto BBOrigFreq = BFI->getBlockFreq(BB); in UpdateBlockFreqAndEdgeWeight()
1634 auto BB2SuccBBFreq = BBOrigFreq * BPI->getEdgeProbability(BB, SuccBB); in UpdateBlockFreqAndEdgeWeight()
1636 BFI->setBlockFreq(BB, BBNewFreq.getFrequency()); in UpdateBlockFreqAndEdgeWeight()
1641 for (auto I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { in UpdateBlockFreqAndEdgeWeight()
1644 : BBOrigFreq * BPI->getEdgeProbability(BB, *I); in UpdateBlockFreqAndEdgeWeight()
1657 BPI->setEdgeWeight(BB, I, Weights[I]); in UpdateBlockFreqAndEdgeWeight()
1660 auto TI = BB->getTerminator(); in UpdateBlockFreqAndEdgeWeight()
1672 bool JumpThreading::DuplicateCondBranchOnPHIIntoPred(BasicBlock *BB, in DuplicateCondBranchOnPHIIntoPred() argument
1679 if (LoopHeaders.count(BB)) { in DuplicateCondBranchOnPHIIntoPred()
1680 DEBUG(dbgs() << " Not duplicating loop header '" << BB->getName() in DuplicateCondBranchOnPHIIntoPred()
1686 unsigned DuplicationCost = getJumpThreadDuplicationCost(BB, BBDupThreshold); in DuplicateCondBranchOnPHIIntoPred()
1688 DEBUG(dbgs() << " Not duplicating BB '" << BB->getName() in DuplicateCondBranchOnPHIIntoPred()
1700 PredBB = SplitBlockPreds(BB, PredBBs, ".thr_comm"); in DuplicateCondBranchOnPHIIntoPred()
1705 DEBUG(dbgs() << " Duplicating block '" << BB->getName() << "' into end of '" in DuplicateCondBranchOnPHIIntoPred()
1707 << DuplicationCost << " block is:" << *BB << "\n"); in DuplicateCondBranchOnPHIIntoPred()
1714 PredBB = SplitEdge(PredBB, BB); in DuplicateCondBranchOnPHIIntoPred()
1722 BasicBlock::iterator BI = BB->begin(); in DuplicateCondBranchOnPHIIntoPred()
1727 for (; BI != BB->end(); ++BI) { in DuplicateCondBranchOnPHIIntoPred()
1742 SimplifyInstruction(New, BB->getModule()->getDataLayout())) { in DuplicateCondBranchOnPHIIntoPred()
1755 BranchInst *BBBranch = cast<BranchInst>(BB->getTerminator()); in DuplicateCondBranchOnPHIIntoPred()
1756 AddPHINodeEntriesForMappedBlock(BBBranch->getSuccessor(0), BB, PredBB, in DuplicateCondBranchOnPHIIntoPred()
1758 AddPHINodeEntriesForMappedBlock(BBBranch->getSuccessor(1), BB, PredBB, in DuplicateCondBranchOnPHIIntoPred()
1767 for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) { in DuplicateCondBranchOnPHIIntoPred()
1773 if (UserPN->getIncomingBlock(U) == BB) in DuplicateCondBranchOnPHIIntoPred()
1775 } else if (User->getParent() == BB) in DuplicateCondBranchOnPHIIntoPred()
1791 SSAUpdate.AddAvailableValue(BB, &*I); in DuplicateCondBranchOnPHIIntoPred()
1801 BB->removePredecessor(PredBB, true); in DuplicateCondBranchOnPHIIntoPred()
1822 bool JumpThreading::TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB) { in TryToUnfoldSelect() argument
1823 BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator()); in TryToUnfoldSelect()
1828 CondLHS->getParent() != BB) in TryToUnfoldSelect()
1849 CondRHS, Pred, BB, CondCmp); in TryToUnfoldSelect()
1852 CondRHS, Pred, BB, CondCmp); in TryToUnfoldSelect()
1865 BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "select.unfold", in TryToUnfoldSelect()
1866 BB->getParent(), BB); in TryToUnfoldSelect()
1871 BranchInst::Create(NewBB, BB, SI->getCondition(), Pred); in TryToUnfoldSelect()
1878 for (BasicBlock::iterator BI = BB->begin(); in TryToUnfoldSelect()