#define DEBUG_TYPE "branch-prob"
-INITIALIZE_PASS_BEGIN(BranchProbabilityInfo, "branch-prob",
+INITIALIZE_PASS_BEGIN(BranchProbabilityInfoWrapperPass, "branch-prob",
"Branch Probability Analysis", false, true)
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
-INITIALIZE_PASS_END(BranchProbabilityInfo, "branch-prob",
+INITIALIZE_PASS_END(BranchProbabilityInfoWrapperPass, "branch-prob",
"Branch Probability Analysis", false, true)
-char BranchProbabilityInfo::ID = 0;
+char BranchProbabilityInfoWrapperPass::ID = 0;
// Weights are for internal use only. They are used by heuristics to help to
// estimate edges' probability. Example:
if (TI->getNumSuccessors() == 1 || UnreachableEdges.empty())
return false;
+ // If the terminator is an InvokeInst, check only the normal destination block
+ // as the unwind edge of InvokeInst is also very unlikely taken.
+ if (auto *II = dyn_cast<InvokeInst>(TI))
+ if (PostDominatedByUnreachable.count(II->getNormalDest())) {
+ PostDominatedByUnreachable.insert(BB);
+ // Return false here so that edge weights for InvokeInst could be decided
+ // in calcInvokeHeuristics().
+ return false;
+ }
+
uint32_t UnreachableWeight =
std::max(UR_TAKEN_WEIGHT / (unsigned)UnreachableEdges.size(), MIN_WEIGHT);
for (SmallVectorImpl<unsigned>::iterator I = UnreachableEdges.begin(),
// Calculate Edge Weights using "Loop Branch Heuristics". Predict backedges
// as taken, exiting edges as not-taken.
-bool BranchProbabilityInfo::calcLoopBranchHeuristics(BasicBlock *BB) {
- Loop *L = LI->getLoopFor(BB);
+bool BranchProbabilityInfo::calcLoopBranchHeuristics(BasicBlock *BB,
+ const LoopInfo &LI) {
+ Loop *L = LI.getLoopFor(BB);
if (!L)
return false;
return true;
}
-void BranchProbabilityInfo::getAnalysisUsage(AnalysisUsage &AU) const {
- AU.addRequired<LoopInfoWrapperPass>();
- AU.setPreservesAll();
-}
-
-bool BranchProbabilityInfo::runOnFunction(Function &F) {
- DEBUG(dbgs() << "---- Branch Probability Info : " << F.getName()
- << " ----\n\n");
- LastF = &F; // Store the last function we ran on for printing.
- LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
- assert(PostDominatedByUnreachable.empty());
- assert(PostDominatedByColdCall.empty());
-
- // Walk the basic blocks in post-order so that we can build up state about
- // the successors of a block iteratively.
- for (auto BB : post_order(&F.getEntryBlock())) {
- DEBUG(dbgs() << "Computing probabilities for " << BB->getName() << "\n");
- if (calcUnreachableHeuristics(BB))
- continue;
- if (calcMetadataWeights(BB))
- continue;
- if (calcColdCallHeuristics(BB))
- continue;
- if (calcLoopBranchHeuristics(BB))
- continue;
- if (calcPointerHeuristics(BB))
- continue;
- if (calcZeroHeuristics(BB))
- continue;
- if (calcFloatingPointHeuristics(BB))
- continue;
- calcInvokeHeuristics(BB);
- }
-
- PostDominatedByUnreachable.clear();
- PostDominatedByColdCall.clear();
- return false;
-}
-
void BranchProbabilityInfo::releaseMemory() {
Weights.clear();
}
-void BranchProbabilityInfo::print(raw_ostream &OS, const Module *) const {
+void BranchProbabilityInfo::print(raw_ostream &OS) const {
OS << "---- Branch Probabilities ----\n";
// We print the probabilities from the last function the analysis ran over,
// or the function it is currently running over.
assert(LastF && "Cannot print prior to running over a function");
- for (Function::const_iterator BI = LastF->begin(), BE = LastF->end();
- BI != BE; ++BI) {
- for (succ_const_iterator SI = succ_begin(BI), SE = succ_end(BI);
- SI != SE; ++SI) {
- printEdgeProbability(OS << " ", BI, *SI);
+ for (const auto &BI : *LastF) {
+ for (succ_const_iterator SI = succ_begin(&BI), SE = succ_end(&BI); SI != SE;
+ ++SI) {
+ printEdgeProbability(OS << " ", &BI, *SI);
}
}
}
uint32_t N = getEdgeWeight(Src, IndexInSuccessors);
uint32_t D = getSumForBlock(Src);
+ // It is possible that the edge weight on the only successor edge of Src is
+ // zero, in which case we return 100%.
+ if (N == 0 && D == 0)
+ return BranchProbability::getOne();
+
return BranchProbability(N, D);
}
uint32_t N = getEdgeWeight(Src, Dst);
uint32_t D = getSumForBlock(Src);
+ // It is possible that the edge weight on the only successor edge of Src is
+ // zero, in which case we return 100%.
+ if (N == 0 && D == 0)
+ return BranchProbability::getOne();
+
return BranchProbability(N, D);
}
+BranchProbability
+BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
+ succ_const_iterator Dst) const {
+ return getEdgeProbability(Src, Dst.getSuccessorIndex());
+}
+
raw_ostream &
BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS,
const BasicBlock *Src,
return OS;
}
+
+void BranchProbabilityInfo::calculate(Function &F, const LoopInfo& LI) {
+ DEBUG(dbgs() << "---- Branch Probability Info : " << F.getName()
+ << " ----\n\n");
+ LastF = &F; // Store the last function we ran on for printing.
+ assert(PostDominatedByUnreachable.empty());
+ assert(PostDominatedByColdCall.empty());
+
+ // Walk the basic blocks in post-order so that we can build up state about
+ // the successors of a block iteratively.
+ for (auto BB : post_order(&F.getEntryBlock())) {
+ DEBUG(dbgs() << "Computing probabilities for " << BB->getName() << "\n");
+ if (calcUnreachableHeuristics(BB))
+ continue;
+ if (calcMetadataWeights(BB))
+ continue;
+ if (calcColdCallHeuristics(BB))
+ continue;
+ if (calcLoopBranchHeuristics(BB, LI))
+ continue;
+ if (calcPointerHeuristics(BB))
+ continue;
+ if (calcZeroHeuristics(BB))
+ continue;
+ if (calcFloatingPointHeuristics(BB))
+ continue;
+ calcInvokeHeuristics(BB);
+ }
+
+ PostDominatedByUnreachable.clear();
+ PostDominatedByColdCall.clear();
+}
+
+void BranchProbabilityInfoWrapperPass::getAnalysisUsage(
+ AnalysisUsage &AU) const {
+ AU.addRequired<LoopInfoWrapperPass>();
+ AU.setPreservesAll();
+}
+
+bool BranchProbabilityInfoWrapperPass::runOnFunction(Function &F) {
+ const LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+ BPI.calculate(F, LI);
+ return false;
+}
+
+void BranchProbabilityInfoWrapperPass::releaseMemory() { BPI.releaseMemory(); }
+
+void BranchProbabilityInfoWrapperPass::print(raw_ostream &OS,
+ const Module *) const {
+ BPI.print(OS);
+}
projects / oota-llvm.git / blobdiff