aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Transforms/Scalar/JumpThreading.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/Transforms/Scalar/JumpThreading.cpp')
-rw-r--r--llvm/lib/Transforms/Scalar/JumpThreading.cpp404
1 files changed, 228 insertions, 176 deletions
diff --git a/llvm/lib/Transforms/Scalar/JumpThreading.cpp b/llvm/lib/Transforms/Scalar/JumpThreading.cpp
index f41eaed2e3e7..24390f1b54f6 100644
--- a/llvm/lib/Transforms/Scalar/JumpThreading.cpp
+++ b/llvm/lib/Transforms/Scalar/JumpThreading.cpp
@@ -23,7 +23,6 @@
#include "llvm/Analysis/BranchProbabilityInfo.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/ConstantFolding.h"
-#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/GuardUtils.h"
#include "llvm/Analysis/InstructionSimplify.h"
@@ -31,6 +30,7 @@
#include "llvm/Analysis/Loads.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/MemoryLocation.h"
+#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
@@ -40,6 +40,7 @@
#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/DebugInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstrTypes.h"
@@ -57,15 +58,12 @@
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/Value.h"
-#include "llvm/InitializePasses.h"
-#include "llvm/Pass.h"
#include "llvm/Support/BlockFrequency.h"
#include "llvm/Support/BranchProbability.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
-#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/Local.h"
@@ -114,68 +112,6 @@ static cl::opt<bool> ThreadAcrossLoopHeaders(
cl::desc("Allow JumpThreading to thread across loop headers, for testing"),
cl::init(false), cl::Hidden);
-
-namespace {
-
- /// This pass performs 'jump threading', which looks at blocks that have
- /// multiple predecessors and multiple successors. If one or more of the
- /// predecessors of the block can be proven to always jump to one of the
- /// successors, we forward the edge from the predecessor to the successor by
- /// duplicating the contents of this block.
- ///
- /// An example of when this can occur is code like this:
- ///
- /// if () { ...
- /// X = 4;
- /// }
- /// if (X < 3) {
- ///
- /// In this case, the unconditional branch at the end of the first if can be
- /// revectored to the false side of the second if.
- class JumpThreading : public FunctionPass {
- JumpThreadingPass Impl;
-
- public:
- static char ID; // Pass identification
-
- JumpThreading(int T = -1) : FunctionPass(ID), Impl(T) {
- initializeJumpThreadingPass(*PassRegistry::getPassRegistry());
- }
-
- bool runOnFunction(Function &F) override;
-
- void getAnalysisUsage(AnalysisUsage &AU) const override {
- AU.addRequired<DominatorTreeWrapperPass>();
- AU.addPreserved<DominatorTreeWrapperPass>();
- AU.addRequired<AAResultsWrapperPass>();
- AU.addRequired<LazyValueInfoWrapperPass>();
- AU.addPreserved<LazyValueInfoWrapperPass>();
- AU.addPreserved<GlobalsAAWrapperPass>();
- AU.addRequired<TargetLibraryInfoWrapperPass>();
- AU.addRequired<TargetTransformInfoWrapperPass>();
- }
-
- void releaseMemory() override { Impl.releaseMemory(); }
- };
-
-} // end anonymous namespace
-
-char JumpThreading::ID = 0;
-
-INITIALIZE_PASS_BEGIN(JumpThreading, "jump-threading",
- "Jump Threading", false, false)
-INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
-INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)
-INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
-INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
-INITIALIZE_PASS_END(JumpThreading, "jump-threading",
- "Jump Threading", false, false)
-
-// Public interface to the Jump Threading pass
-FunctionPass *llvm::createJumpThreadingPass(int Threshold) {
- return new JumpThreading(Threshold);
-}
-
JumpThreadingPass::JumpThreadingPass(int T) {
DefaultBBDupThreshold = (T == -1) ? BBDuplicateThreshold : unsigned(T);
}
@@ -306,102 +242,81 @@ static void updatePredecessorProfileMetadata(PHINode *PN, BasicBlock *BB) {
}
}
-/// runOnFunction - Toplevel algorithm.
-bool JumpThreading::runOnFunction(Function &F) {
- if (skipFunction(F))
- return false;
- auto TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
- // Jump Threading has no sense for the targets with divergent CF
- if (TTI->hasBranchDivergence())
- return false;
- auto TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
- auto DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
- auto LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();
- auto AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
- DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Lazy);
- std::unique_ptr<BlockFrequencyInfo> BFI;
- std::unique_ptr<BranchProbabilityInfo> BPI;
- if (F.hasProfileData()) {
- LoopInfo LI{*DT};
- BPI.reset(new BranchProbabilityInfo(F, LI, TLI));
- BFI.reset(new BlockFrequencyInfo(F, *BPI, LI));
- }
-
- bool Changed = Impl.runImpl(F, TLI, TTI, LVI, AA, &DTU, F.hasProfileData(),
- std::move(BFI), std::move(BPI));
- if (PrintLVIAfterJumpThreading) {
- dbgs() << "LVI for function '" << F.getName() << "':\n";
- LVI->printLVI(F, DTU.getDomTree(), dbgs());
- }
- return Changed;
-}
-
PreservedAnalyses JumpThreadingPass::run(Function &F,
FunctionAnalysisManager &AM) {
auto &TTI = AM.getResult<TargetIRAnalysis>(F);
// Jump Threading has no sense for the targets with divergent CF
- if (TTI.hasBranchDivergence())
+ if (TTI.hasBranchDivergence(&F))
return PreservedAnalyses::all();
auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
- auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
auto &LVI = AM.getResult<LazyValueAnalysis>(F);
auto &AA = AM.getResult<AAManager>(F);
- DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
-
- std::unique_ptr<BlockFrequencyInfo> BFI;
- std::unique_ptr<BranchProbabilityInfo> BPI;
- if (F.hasProfileData()) {
- LoopInfo LI{DT};
- BPI.reset(new BranchProbabilityInfo(F, LI, &TLI));
- BFI.reset(new BlockFrequencyInfo(F, *BPI, LI));
- }
+ auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
- bool Changed = runImpl(F, &TLI, &TTI, &LVI, &AA, &DTU, F.hasProfileData(),
- std::move(BFI), std::move(BPI));
+ bool Changed =
+ runImpl(F, &AM, &TLI, &TTI, &LVI, &AA,
+ std::make_unique<DomTreeUpdater>(
+ &DT, nullptr, DomTreeUpdater::UpdateStrategy::Lazy),
+ std::nullopt, std::nullopt);
if (PrintLVIAfterJumpThreading) {
dbgs() << "LVI for function '" << F.getName() << "':\n";
- LVI.printLVI(F, DTU.getDomTree(), dbgs());
+ LVI.printLVI(F, getDomTreeUpdater()->getDomTree(), dbgs());
}
if (!Changed)
return PreservedAnalyses::all();
- PreservedAnalyses PA;
- PA.preserve<DominatorTreeAnalysis>();
- PA.preserve<LazyValueAnalysis>();
- return PA;
+
+
+ getDomTreeUpdater()->flush();
+
+#if defined(EXPENSIVE_CHECKS)
+ assert(getDomTreeUpdater()->getDomTree().verify(
+ DominatorTree::VerificationLevel::Full) &&
+ "DT broken after JumpThreading");
+ assert((!getDomTreeUpdater()->hasPostDomTree() ||
+ getDomTreeUpdater()->getPostDomTree().verify(
+ PostDominatorTree::VerificationLevel::Full)) &&
+ "PDT broken after JumpThreading");
+#else
+ assert(getDomTreeUpdater()->getDomTree().verify(
+ DominatorTree::VerificationLevel::Fast) &&
+ "DT broken after JumpThreading");
+ assert((!getDomTreeUpdater()->hasPostDomTree() ||
+ getDomTreeUpdater()->getPostDomTree().verify(
+ PostDominatorTree::VerificationLevel::Fast)) &&
+ "PDT broken after JumpThreading");
+#endif
+
+ return getPreservedAnalysis();
}
-bool JumpThreadingPass::runImpl(Function &F, TargetLibraryInfo *TLI_,
+bool JumpThreadingPass::runImpl(Function &F_, FunctionAnalysisManager *FAM_,
+ TargetLibraryInfo *TLI_,
TargetTransformInfo *TTI_, LazyValueInfo *LVI_,
- AliasAnalysis *AA_, DomTreeUpdater *DTU_,
- bool HasProfileData_,
- std::unique_ptr<BlockFrequencyInfo> BFI_,
- std::unique_ptr<BranchProbabilityInfo> BPI_) {
- LLVM_DEBUG(dbgs() << "Jump threading on function '" << F.getName() << "'\n");
+ AliasAnalysis *AA_,
+ std::unique_ptr<DomTreeUpdater> DTU_,
+ std::optional<BlockFrequencyInfo *> BFI_,
+ std::optional<BranchProbabilityInfo *> BPI_) {
+ LLVM_DEBUG(dbgs() << "Jump threading on function '" << F_.getName() << "'\n");
+ F = &F_;
+ FAM = FAM_;
TLI = TLI_;
TTI = TTI_;
LVI = LVI_;
AA = AA_;
- DTU = DTU_;
- BFI.reset();
- BPI.reset();
- // When profile data is available, we need to update edge weights after
- // successful jump threading, which requires both BPI and BFI being available.
- HasProfileData = HasProfileData_;
- auto *GuardDecl = F.getParent()->getFunction(
+ DTU = std::move(DTU_);
+ BFI = BFI_;
+ BPI = BPI_;
+ auto *GuardDecl = F->getParent()->getFunction(
Intrinsic::getName(Intrinsic::experimental_guard));
HasGuards = GuardDecl && !GuardDecl->use_empty();
- if (HasProfileData) {
- BPI = std::move(BPI_);
- BFI = std::move(BFI_);
- }
// Reduce the number of instructions duplicated when optimizing strictly for
// size.
if (BBDuplicateThreshold.getNumOccurrences())
BBDupThreshold = BBDuplicateThreshold;
- else if (F.hasFnAttribute(Attribute::MinSize))
+ else if (F->hasFnAttribute(Attribute::MinSize))
BBDupThreshold = 3;
else
BBDupThreshold = DefaultBBDupThreshold;
@@ -412,22 +327,22 @@ bool JumpThreadingPass::runImpl(Function &F, TargetLibraryInfo *TLI_,
assert(DTU && "DTU isn't passed into JumpThreading before using it.");
assert(DTU->hasDomTree() && "JumpThreading relies on DomTree to proceed.");
DominatorTree &DT = DTU->getDomTree();
- for (auto &BB : F)
+ for (auto &BB : *F)
if (!DT.isReachableFromEntry(&BB))
Unreachable.insert(&BB);
if (!ThreadAcrossLoopHeaders)
- findLoopHeaders(F);
+ findLoopHeaders(*F);
bool EverChanged = false;
bool Changed;
do {
Changed = false;
- for (auto &BB : F) {
+ for (auto &BB : *F) {
if (Unreachable.count(&BB))
continue;
while (processBlock(&BB)) // Thread all of the branches we can over BB.
- Changed = true;
+ Changed = ChangedSinceLastAnalysisUpdate = true;
// Jump threading may have introduced redundant debug values into BB
// which should be removed.
@@ -437,7 +352,7 @@ bool JumpThreadingPass::runImpl(Function &F, TargetLibraryInfo *TLI_,
// Stop processing BB if it's the entry or is now deleted. The following
// routines attempt to eliminate BB and locating a suitable replacement
// for the entry is non-trivial.
- if (&BB == &F.getEntryBlock() || DTU->isBBPendingDeletion(&BB))
+ if (&BB == &F->getEntryBlock() || DTU->isBBPendingDeletion(&BB))
continue;
if (pred_empty(&BB)) {
@@ -448,8 +363,8 @@ bool JumpThreadingPass::runImpl(Function &F, TargetLibraryInfo *TLI_,
<< '\n');
LoopHeaders.erase(&BB);
LVI->eraseBlock(&BB);
- DeleteDeadBlock(&BB, DTU);
- Changed = true;
+ DeleteDeadBlock(&BB, DTU.get());
+ Changed = ChangedSinceLastAnalysisUpdate = true;
continue;
}
@@ -464,12 +379,12 @@ bool JumpThreadingPass::runImpl(Function &F, TargetLibraryInfo *TLI_,
// Don't alter Loop headers and latches to ensure another pass can
// detect and transform nested loops later.
!LoopHeaders.count(&BB) && !LoopHeaders.count(Succ) &&
- TryToSimplifyUncondBranchFromEmptyBlock(&BB, DTU)) {
+ TryToSimplifyUncondBranchFromEmptyBlock(&BB, DTU.get())) {
RemoveRedundantDbgInstrs(Succ);
// BB is valid for cleanup here because we passed in DTU. F remains
// BB's parent until a DTU->getDomTree() event.
LVI->eraseBlock(&BB);
- Changed = true;
+ Changed = ChangedSinceLastAnalysisUpdate = true;
}
}
}
@@ -1140,8 +1055,8 @@ bool JumpThreadingPass::processBlock(BasicBlock *BB) {
<< "' folding terminator: " << *BB->getTerminator()
<< '\n');
++NumFolds;
- ConstantFoldTerminator(BB, true, nullptr, DTU);
- if (HasProfileData)
+ ConstantFoldTerminator(BB, true, nullptr, DTU.get());
+ if (auto *BPI = getBPI())
BPI->eraseBlock(BB);
return true;
}
@@ -1296,7 +1211,7 @@ bool JumpThreadingPass::processImpliedCondition(BasicBlock *BB) {
FICond->eraseFromParent();
DTU->applyUpdatesPermissive({{DominatorTree::Delete, BB, RemoveSucc}});
- if (HasProfileData)
+ if (auto *BPI = getBPI())
BPI->eraseBlock(BB);
return true;
}
@@ -1740,7 +1655,7 @@ bool JumpThreadingPass::processThreadableEdges(Value *Cond, BasicBlock *BB,
++NumFolds;
Term->eraseFromParent();
DTU->applyUpdatesPermissive(Updates);
- if (HasProfileData)
+ if (auto *BPI = getBPI())
BPI->eraseBlock(BB);
// If the condition is now dead due to the removal of the old terminator,
@@ -1993,7 +1908,7 @@ bool JumpThreadingPass::maybeMergeBasicBlockIntoOnlyPred(BasicBlock *BB) {
LoopHeaders.insert(BB);
LVI->eraseBlock(SinglePred);
- MergeBasicBlockIntoOnlyPred(BB, DTU);
+ MergeBasicBlockIntoOnlyPred(BB, DTU.get());
// Now that BB is merged into SinglePred (i.e. SinglePred code followed by
// BB code within one basic block `BB`), we need to invalidate the LVI
@@ -2038,6 +1953,7 @@ void JumpThreadingPass::updateSSA(
// PHI insertion, of which we are prepared to do, clean these up now.
SSAUpdater SSAUpdate;
SmallVector<Use *, 16> UsesToRename;
+ SmallVector<DbgValueInst *, 4> DbgValues;
for (Instruction &I : *BB) {
// Scan all uses of this instruction to see if it is used outside of its
@@ -2053,8 +1969,16 @@ void JumpThreadingPass::updateSSA(
UsesToRename.push_back(&U);
}
+ // Find debug values outside of the block
+ findDbgValues(DbgValues, &I);
+ DbgValues.erase(remove_if(DbgValues,
+ [&](const DbgValueInst *DbgVal) {
+ return DbgVal->getParent() == BB;
+ }),
+ DbgValues.end());
+
// If there are no uses outside the block, we're done with this instruction.
- if (UsesToRename.empty())
+ if (UsesToRename.empty() && DbgValues.empty())
continue;
LLVM_DEBUG(dbgs() << "JT: Renaming non-local uses of: " << I << "\n");
@@ -2067,6 +1991,11 @@ void JumpThreadingPass::updateSSA(
while (!UsesToRename.empty())
SSAUpdate.RewriteUse(*UsesToRename.pop_back_val());
+ if (!DbgValues.empty()) {
+ SSAUpdate.UpdateDebugValues(&I, DbgValues);
+ DbgValues.clear();
+ }
+
LLVM_DEBUG(dbgs() << "\n");
}
}
@@ -2298,6 +2227,11 @@ void JumpThreadingPass::threadThroughTwoBasicBlocks(BasicBlock *PredPredBB,
LLVM_DEBUG(dbgs() << " Threading through '" << PredBB->getName() << "' and '"
<< BB->getName() << "'\n");
+ // Build BPI/BFI before any changes are made to IR.
+ bool HasProfile = doesBlockHaveProfileData(BB);
+ auto *BFI = getOrCreateBFI(HasProfile);
+ auto *BPI = getOrCreateBPI(BFI != nullptr);
+
BranchInst *CondBr = cast<BranchInst>(BB->getTerminator());
BranchInst *PredBBBranch = cast<BranchInst>(PredBB->getTerminator());
@@ -2307,7 +2241,8 @@ void JumpThreadingPass::threadThroughTwoBasicBlocks(BasicBlock *PredPredBB,
NewBB->moveAfter(PredBB);
// Set the block frequency of NewBB.
- if (HasProfileData) {
+ if (BFI) {
+ assert(BPI && "It's expected BPI to exist along with BFI");
auto NewBBFreq = BFI->getBlockFreq(PredPredBB) *
BPI->getEdgeProbability(PredPredBB, PredBB);
BFI->setBlockFreq(NewBB, NewBBFreq.getFrequency());
@@ -2320,7 +2255,7 @@ void JumpThreadingPass::threadThroughTwoBasicBlocks(BasicBlock *PredPredBB,
cloneInstructions(PredBB->begin(), PredBB->end(), NewBB, PredPredBB);
// Copy the edge probabilities from PredBB to NewBB.
- if (HasProfileData)
+ if (BPI)
BPI->copyEdgeProbabilities(PredBB, NewBB);
// Update the terminator of PredPredBB to jump to NewBB instead of PredBB.
@@ -2404,6 +2339,11 @@ void JumpThreadingPass::threadEdge(BasicBlock *BB,
assert(!LoopHeaders.count(BB) && !LoopHeaders.count(SuccBB) &&
"Don't thread across loop headers");
+ // Build BPI/BFI before any changes are made to IR.
+ bool HasProfile = doesBlockHaveProfileData(BB);
+ auto *BFI = getOrCreateBFI(HasProfile);
+ auto *BPI = getOrCreateBPI(BFI != nullptr);
+
// And finally, do it! Start by factoring the predecessors if needed.
BasicBlock *PredBB;
if (PredBBs.size() == 1)
@@ -2427,7 +2367,8 @@ void JumpThreadingPass::threadEdge(BasicBlock *BB,
NewBB->moveAfter(PredBB);
// Set the block frequency of NewBB.
- if (HasProfileData) {
+ if (BFI) {
+ assert(BPI && "It's expected BPI to exist along with BFI");
auto NewBBFreq =
BFI->getBlockFreq(PredBB) * BPI->getEdgeProbability(PredBB, BB);
BFI->setBlockFreq(NewBB, NewBBFreq.getFrequency());
@@ -2469,7 +2410,7 @@ void JumpThreadingPass::threadEdge(BasicBlock *BB,
SimplifyInstructionsInBlock(NewBB, TLI);
// Update the edge weight from BB to SuccBB, which should be less than before.
- updateBlockFreqAndEdgeWeight(PredBB, BB, NewBB, SuccBB);
+ updateBlockFreqAndEdgeWeight(PredBB, BB, NewBB, SuccBB, BFI, BPI, HasProfile);
// Threaded an edge!
++NumThreads;
@@ -2486,10 +2427,13 @@ BasicBlock *JumpThreadingPass::splitBlockPreds(BasicBlock *BB,
// Collect the frequencies of all predecessors of BB, which will be used to
// update the edge weight of the result of splitting predecessors.
DenseMap<BasicBlock *, BlockFrequency> FreqMap;
- if (HasProfileData)
+ auto *BFI = getBFI();
+ if (BFI) {
+ auto *BPI = getOrCreateBPI(true);
for (auto *Pred : Preds)
FreqMap.insert(std::make_pair(
Pred, BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, BB)));
+ }
// In the case when BB is a LandingPad block we create 2 new predecessors
// instead of just one.
@@ -2508,10 +2452,10 @@ BasicBlock *JumpThreadingPass::splitBlockPreds(BasicBlock *BB,
for (auto *Pred : predecessors(NewBB)) {
Updates.push_back({DominatorTree::Delete, Pred, BB});
Updates.push_back({DominatorTree::Insert, Pred, NewBB});
- if (HasProfileData) // Update frequencies between Pred -> NewBB.
+ if (BFI) // Update frequencies between Pred -> NewBB.
NewBBFreq += FreqMap.lookup(Pred);
}
- if (HasProfileData) // Apply the summed frequency to NewBB.
+ if (BFI) // Apply the summed frequency to NewBB.
BFI->setBlockFreq(NewBB, NewBBFreq.getFrequency());
}
@@ -2521,7 +2465,9 @@ BasicBlock *JumpThreadingPass::splitBlockPreds(BasicBlock *BB,
bool JumpThreadingPass::doesBlockHaveProfileData(BasicBlock *BB) {
const Instruction *TI = BB->getTerminator();
- assert(TI->getNumSuccessors() > 1 && "not a split");
+ if (!TI || TI->getNumSuccessors() < 2)
+ return false;
+
return hasValidBranchWeightMD(*TI);
}
@@ -2531,11 +2477,18 @@ bool JumpThreadingPass::doesBlockHaveProfileData(BasicBlock *BB) {
void JumpThreadingPass::updateBlockFreqAndEdgeWeight(BasicBlock *PredBB,
BasicBlock *BB,
BasicBlock *NewBB,
- BasicBlock *SuccBB) {
- if (!HasProfileData)
+ BasicBlock *SuccBB,
+ BlockFrequencyInfo *BFI,
+ BranchProbabilityInfo *BPI,
+ bool HasProfile) {
+ assert(((BFI && BPI) || (!BFI && !BFI)) &&
+ "Both BFI & BPI should either be set or unset");
+
+ if (!BFI) {
+ assert(!HasProfile &&
+ "It's expected to have BFI/BPI when profile info exists");
return;
-
- assert(BFI && BPI && "BFI & BPI should have been created here");
+ }
// As the edge from PredBB to BB is deleted, we have to update the block
// frequency of BB.
@@ -2608,7 +2561,7 @@ void JumpThreadingPass::updateBlockFreqAndEdgeWeight(BasicBlock *PredBB,
// FIXME this locally as well so that BPI and BFI are consistent as well. We
// shouldn't make edges extremely likely or unlikely based solely on static
// estimation.
- if (BBSuccProbs.size() >= 2 && doesBlockHaveProfileData(BB)) {
+ if (BBSuccProbs.size() >= 2 && HasProfile) {
SmallVector<uint32_t, 4> Weights;
for (auto Prob : BBSuccProbs)
Weights.push_back(Prob.getNumerator());
@@ -2690,6 +2643,7 @@ bool JumpThreadingPass::duplicateCondBranchOnPHIIntoPred(
// mapping and using it to remap operands in the cloned instructions.
for (; BI != BB->end(); ++BI) {
Instruction *New = BI->clone();
+ New->insertInto(PredBB, OldPredBranch->getIterator());
// Remap operands to patch up intra-block references.
for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
@@ -2707,7 +2661,7 @@ bool JumpThreadingPass::duplicateCondBranchOnPHIIntoPred(
{BB->getModule()->getDataLayout(), TLI, nullptr, nullptr, New})) {
ValueMapping[&*BI] = IV;
if (!New->mayHaveSideEffects()) {
- New->deleteValue();
+ New->eraseFromParent();
New = nullptr;
}
} else {
@@ -2716,7 +2670,6 @@ bool JumpThreadingPass::duplicateCondBranchOnPHIIntoPred(
if (New) {
// Otherwise, insert the new instruction into the block.
New->setName(BI->getName());
- New->insertInto(PredBB, OldPredBranch->getIterator());
// Update Dominance from simplified New instruction operands.
for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
if (BasicBlock *SuccBB = dyn_cast<BasicBlock>(New->getOperand(i)))
@@ -2740,7 +2693,7 @@ bool JumpThreadingPass::duplicateCondBranchOnPHIIntoPred(
// Remove the unconditional branch at the end of the PredBB block.
OldPredBranch->eraseFromParent();
- if (HasProfileData)
+ if (auto *BPI = getBPI())
BPI->copyEdgeProbabilities(BB, PredBB);
DTU->applyUpdatesPermissive(Updates);
@@ -2777,21 +2730,30 @@ void JumpThreadingPass::unfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB,
BI->copyMetadata(*SI, {LLVMContext::MD_prof});
SIUse->setIncomingValue(Idx, SI->getFalseValue());
SIUse->addIncoming(SI->getTrueValue(), NewBB);
- // Set the block frequency of NewBB.
- if (HasProfileData) {
- uint64_t TrueWeight, FalseWeight;
- if (extractBranchWeights(*SI, TrueWeight, FalseWeight) &&
- (TrueWeight + FalseWeight) != 0) {
- SmallVector<BranchProbability, 2> BP;
- BP.emplace_back(BranchProbability::getBranchProbability(
- TrueWeight, TrueWeight + FalseWeight));
- BP.emplace_back(BranchProbability::getBranchProbability(
- FalseWeight, TrueWeight + FalseWeight));
+
+ uint64_t TrueWeight = 1;
+ uint64_t FalseWeight = 1;
+ // Copy probabilities from 'SI' to created conditional branch in 'Pred'.
+ if (extractBranchWeights(*SI, TrueWeight, FalseWeight) &&
+ (TrueWeight + FalseWeight) != 0) {
+ SmallVector<BranchProbability, 2> BP;
+ BP.emplace_back(BranchProbability::getBranchProbability(
+ TrueWeight, TrueWeight + FalseWeight));
+ BP.emplace_back(BranchProbability::getBranchProbability(
+ FalseWeight, TrueWeight + FalseWeight));
+ // Update BPI if exists.
+ if (auto *BPI = getBPI())
BPI->setEdgeProbability(Pred, BP);
+ }
+ // Set the block frequency of NewBB.
+ if (auto *BFI = getBFI()) {
+ if ((TrueWeight + FalseWeight) == 0) {
+ TrueWeight = 1;
+ FalseWeight = 1;
}
-
- auto NewBBFreq =
- BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, NewBB);
+ BranchProbability PredToNewBBProb = BranchProbability::getBranchProbability(
+ TrueWeight, TrueWeight + FalseWeight);
+ auto NewBBFreq = BFI->getBlockFreq(Pred) * PredToNewBBProb;
BFI->setBlockFreq(NewBB, NewBBFreq.getFrequency());
}
@@ -3112,3 +3074,93 @@ bool JumpThreadingPass::threadGuard(BasicBlock *BB, IntrinsicInst *Guard,
}
return true;
}
+
+PreservedAnalyses JumpThreadingPass::getPreservedAnalysis() const {
+ PreservedAnalyses PA;
+ PA.preserve<LazyValueAnalysis>();
+ PA.preserve<DominatorTreeAnalysis>();
+
+ // TODO: We would like to preserve BPI/BFI. Enable once all paths update them.
+ // TODO: Would be nice to verify BPI/BFI consistency as well.
+ return PA;
+}
+
+template <typename AnalysisT>
+typename AnalysisT::Result *JumpThreadingPass::runExternalAnalysis() {
+ assert(FAM && "Can't run external analysis without FunctionAnalysisManager");
+
+ // If there were no changes since last call to 'runExternalAnalysis' then all
+ // analysis is either up to date or explicitly invalidated. Just go ahead and
+ // run the "external" analysis.
+ if (!ChangedSinceLastAnalysisUpdate) {
+ assert(!DTU->hasPendingUpdates() &&
+ "Lost update of 'ChangedSinceLastAnalysisUpdate'?");
+ // Run the "external" analysis.
+ return &FAM->getResult<AnalysisT>(*F);
+ }
+ ChangedSinceLastAnalysisUpdate = false;
+
+ auto PA = getPreservedAnalysis();
+ // TODO: This shouldn't be needed once 'getPreservedAnalysis' reports BPI/BFI
+ // as preserved.
+ PA.preserve<BranchProbabilityAnalysis>();
+ PA.preserve<BlockFrequencyAnalysis>();
+ // Report everything except explicitly preserved as invalid.
+ FAM->invalidate(*F, PA);
+ // Update DT/PDT.
+ DTU->flush();
+ // Make sure DT/PDT are valid before running "external" analysis.
+ assert(DTU->getDomTree().verify(DominatorTree::VerificationLevel::Fast));
+ assert((!DTU->hasPostDomTree() ||
+ DTU->getPostDomTree().verify(
+ PostDominatorTree::VerificationLevel::Fast)));
+ // Run the "external" analysis.
+ auto *Result = &FAM->getResult<AnalysisT>(*F);
+ // Update analysis JumpThreading depends on and not explicitly preserved.
+ TTI = &FAM->getResult<TargetIRAnalysis>(*F);
+ TLI = &FAM->getResult<TargetLibraryAnalysis>(*F);
+ AA = &FAM->getResult<AAManager>(*F);
+
+ return Result;
+}
+
+BranchProbabilityInfo *JumpThreadingPass::getBPI() {
+ if (!BPI) {
+ assert(FAM && "Can't create BPI without FunctionAnalysisManager");
+ BPI = FAM->getCachedResult<BranchProbabilityAnalysis>(*F);
+ }
+ return *BPI;
+}
+
+BlockFrequencyInfo *JumpThreadingPass::getBFI() {
+ if (!BFI) {
+ assert(FAM && "Can't create BFI without FunctionAnalysisManager");
+ BFI = FAM->getCachedResult<BlockFrequencyAnalysis>(*F);
+ }
+ return *BFI;
+}
+
+// Important note on validity of BPI/BFI. JumpThreading tries to preserve
+// BPI/BFI as it goes. Thus if cached instance exists it will be updated.
+// Otherwise, new instance of BPI/BFI is created (up to date by definition).
+BranchProbabilityInfo *JumpThreadingPass::getOrCreateBPI(bool Force) {
+ auto *Res = getBPI();
+ if (Res)
+ return Res;
+
+ if (Force)
+ BPI = runExternalAnalysis<BranchProbabilityAnalysis>();
+
+ return *BPI;
+}
+
+BlockFrequencyInfo *JumpThreadingPass::getOrCreateBFI(bool Force) {
+ auto *Res = getBFI();
+ if (Res)
+ return Res;
+
+ if (Force)
+ BFI = runExternalAnalysis<BlockFrequencyAnalysis>();
+
+ return *BFI;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-10-19 05:49:34 +0000