From 4bf7c62ec4e8337dacb3dc46d421ff702fca32cb Mon Sep 17 00:00:00 2001 From: Geoff Berry Date: Wed, 1 Nov 2017 15:16:50 +0000 Subject: [BranchProbabilityInfo] Handle irreducible loops. Summary: Compute the strongly connected components of the CFG and fall back to use these for blocks that are in loops that are not detected by LoopInfo when computing loop back-edge and exit branch probabilities. Reviewers: dexonsmith, davidxl Subscribers: mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D39385 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@317094 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/BranchProbabilityInfo.h | 12 +++++++++++- 1 file changed, 11 insertions(+), 1 deletion(-) (limited to 'include') diff --git a/include/llvm/Analysis/BranchProbabilityInfo.h b/include/llvm/Analysis/BranchProbabilityInfo.h index 88ce6b4bd94..417b6497881 100644 --- a/include/llvm/Analysis/BranchProbabilityInfo.h +++ b/include/llvm/Analysis/BranchProbabilityInfo.h @@ -137,6 +137,15 @@ public: /// Forget analysis results for the given basic block. void eraseBlock(const BasicBlock *BB); + // Use to track SCCs for handling irreducible loops. + using SccMap = DenseMap; + using SccHeaderMap = DenseMap; + using SccHeaderMaps = std::vector; + struct SccInfo { + SccMap SccNums; + SccHeaderMaps SccHeaders; + }; + private: // We need to store CallbackVH's in order to correctly handle basic block // removal. @@ -185,7 +194,8 @@ private: bool calcMetadataWeights(const BasicBlock *BB); bool calcColdCallHeuristics(const BasicBlock *BB); bool calcPointerHeuristics(const BasicBlock *BB); - bool calcLoopBranchHeuristics(const BasicBlock *BB, const LoopInfo &LI); + bool calcLoopBranchHeuristics(const BasicBlock *BB, const LoopInfo &LI, + SccInfo &SccI); bool calcZeroHeuristics(const BasicBlock *BB, const TargetLibraryInfo *TLI); bool calcFloatingPointHeuristics(const BasicBlock *BB); bool calcInvokeHeuristics(const BasicBlock *BB); -- cgit v1.2.3