diff options
author | Diego Novillo <dnovillo@google.com> | 2013-05-24 12:26:52 +0000 |
---|---|---|
committer | Diego Novillo <dnovillo@google.com> | 2013-05-24 12:26:52 +0000 |
commit | 77226a03dca98e6237c1068f2652fe41bea7b687 (patch) | |
tree | 3a8cb78a478d9e82735484091ae29647e3ec9002 /lib/Analysis | |
parent | 49a6a8d8f2994249c81b7914b07015714748a55c (diff) | |
download | external_llvm-77226a03dca98e6237c1068f2652fe41bea7b687.zip external_llvm-77226a03dca98e6237c1068f2652fe41bea7b687.tar.gz external_llvm-77226a03dca98e6237c1068f2652fe41bea7b687.tar.bz2 |
Add a new function attribute 'cold' to functions.
Other than recognizing the attribute, the patch does little else.
It changes the branch probability analyzer so that edges into
blocks postdominated by a cold function are given low weight.
Added analysis and code generation tests. Added documentation for the
new attribute.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@182638 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/Analysis')
-rw-r--r-- | lib/Analysis/BranchProbabilityInfo.cpp | 81 |
1 files changed, 81 insertions, 0 deletions
diff --git a/lib/Analysis/BranchProbabilityInfo.cpp b/lib/Analysis/BranchProbabilityInfo.cpp index 6c58856..54c148e 100644 --- a/lib/Analysis/BranchProbabilityInfo.cpp +++ b/lib/Analysis/BranchProbabilityInfo.cpp @@ -69,6 +69,20 @@ static const uint32_t UR_TAKEN_WEIGHT = 1; /// easily subsume it. static const uint32_t UR_NONTAKEN_WEIGHT = 1024*1024 - 1; +/// \brief Weight for a branch taken going into a cold block. +/// +/// This is the weight for a branch taken toward a block marked +/// cold. A block is marked cold if it's postdominated by a +/// block containing a call to a cold function. Cold functions +/// are those marked with attribute 'cold'. +static const uint32_t CC_TAKEN_WEIGHT = 4; + +/// \brief Weight for a branch not-taken into a cold block. +/// +/// This is the weight for a branch not taken toward a block marked +/// cold. +static const uint32_t CC_NONTAKEN_WEIGHT = 64; + static const uint32_t PH_TAKEN_WEIGHT = 20; static const uint32_t PH_NONTAKEN_WEIGHT = 12; @@ -193,6 +207,69 @@ bool BranchProbabilityInfo::calcMetadataWeights(BasicBlock *BB) { return true; } +/// \brief Calculate edge weights for edges leading to cold blocks. +/// +/// A cold block is one post-dominated by a block with a call to a +/// cold function. Those edges are unlikely to be taken, so we give +/// them relatively low weight. +/// +/// Return true if we could compute the weights for cold edges. +/// Return false, otherwise. +bool BranchProbabilityInfo::calcColdCallHeuristics(BasicBlock *BB) { + TerminatorInst *TI = BB->getTerminator(); + if (TI->getNumSuccessors() == 0) + return false; + + // Determine which successors are post-dominated by a cold block. + SmallVector<unsigned, 4> ColdEdges; + ColdEdges.reserve(TI->getNumSuccessors()); + SmallVector<unsigned, 4> NormalEdges; + NormalEdges.reserve(TI->getNumSuccessors()); + for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) + if (PostDominatedByColdCall.count(*I)) + ColdEdges.push_back(I.getSuccessorIndex()); + else + NormalEdges.push_back(I.getSuccessorIndex()); + + // If all successors are in the set of blocks post-dominated by cold calls, + // this block is in the set post-dominated by cold calls. + if (ColdEdges.size() == TI->getNumSuccessors()) + PostDominatedByColdCall.insert(BB); + else { + // Otherwise, if the block itself contains a cold function, add it to the + // set of blocks postdominated by a cold call. + assert(!PostDominatedByColdCall.count(BB)); + for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) + if (CallInst *CI = dyn_cast<CallInst>(I)) + if (CI->hasFnAttr(Attribute::Cold)) { + PostDominatedByColdCall.insert(BB); + break; + } + } + + // Skip probabilities if this block has a single successor. + if (TI->getNumSuccessors() == 1 || ColdEdges.empty()) + return false; + + uint32_t ColdWeight = + std::max(CC_TAKEN_WEIGHT / (unsigned) ColdEdges.size(), MIN_WEIGHT); + for (SmallVector<unsigned, 4>::iterator I = ColdEdges.begin(), + E = ColdEdges.end(); + I != E; ++I) + setEdgeWeight(BB, *I, ColdWeight); + + if (NormalEdges.empty()) + return true; + uint32_t NormalWeight = std::max( + CC_NONTAKEN_WEIGHT / (unsigned) NormalEdges.size(), NORMAL_WEIGHT); + for (SmallVector<unsigned, 4>::iterator I = NormalEdges.begin(), + E = NormalEdges.end(); + I != E; ++I) + setEdgeWeight(BB, *I, NormalWeight); + + return true; +} + // Calculate Edge Weights using "Pointer Heuristics". Predict a comparsion // between two pointer or pointer and NULL will fail. bool BranchProbabilityInfo::calcPointerHeuristics(BasicBlock *BB) { @@ -397,6 +474,7 @@ bool BranchProbabilityInfo::runOnFunction(Function &F) { LastF = &F; // Store the last function we ran on for printing. LI = &getAnalysis<LoopInfo>(); 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. @@ -408,6 +486,8 @@ bool BranchProbabilityInfo::runOnFunction(Function &F) { continue; if (calcMetadataWeights(*I)) continue; + if (calcColdCallHeuristics(*I)) + continue; if (calcLoopBranchHeuristics(*I)) continue; if (calcPointerHeuristics(*I)) @@ -420,6 +500,7 @@ bool BranchProbabilityInfo::runOnFunction(Function &F) { } PostDominatedByUnreachable.clear(); + PostDominatedByColdCall.clear(); return false; } |