[llvm-branch-commits] [llvm] ab326ac - [llvm][NFC] Cache FAM in InlineAdvisor
Author: Mircea Trofin
Date: 2020-06-01T12:38:53-07:00
New Revision: ab326ac96ecb0379b8fe268b43e65a9115bb634f
URL:
https://github.com/llvm/llvm-project/commit/ab326ac96ecb0379b8fe268b43e65a9115bb634f
DIFF:
https://github.com/llvm/llvm-project/commit/ab326ac96ecb0379b8fe268b43e65a9115bb634f.diff
LOG: [llvm][NFC] Cache FAM in InlineAdvisor
Summary:
This simplifies the interface by storing the function analysis manager
with the InlineAdvisor, and, thus, not requiring it be passed each time
we inquire for an advice.
Reviewers: davidxl, asbirlea
Subscribers: eraman, hiraditya, llvm-commits
Tags: #llvm
Differential Revision: https://reviews.llvm.org/D80405
Added:
Modified:
llvm/include/llvm/Analysis/InlineAdvisor.h
llvm/include/llvm/Transforms/IPO/Inliner.h
llvm/lib/Analysis/InlineAdvisor.cpp
llvm/lib/Transforms/IPO/Inliner.cpp
Removed:
diff --git a/llvm/include/llvm/Analysis/InlineAdvisor.h
b/llvm/include/llvm/Analysis/InlineAdvisor.h
index ac8e7c20429d..e9f08a69a5af 100644
--- a/llvm/include/llvm/Analysis/InlineAdvisor.h
+++ b/llvm/include/llvm/Analysis/InlineAdvisor.h
@@ -116,8 +116,7 @@ class InlineAdvisor {
/// inline or not. \p CB is assumed to be a direct call. \p FAM is assumed to
/// be up-to-date wrt previous inlining decisions.
/// Returns an InlineAdvice with the inlining recommendation.
- virtual std::unique_ptr
- getAdvice(CallBase &CB, FunctionAnalysisManager &FAM) = 0;
+ virtual std::unique_ptr getAdvice(CallBase &CB) = 0;
/// This must be called when the Inliner pass is entered, to allow the
/// InlineAdvisor update internal state, as result of function passes run
@@ -130,7 +129,9 @@ class InlineAdvisor {
virtual void onPassExit() {}
protected:
- InlineAdvisor() = default;
+ InlineAdvisor(FunctionAnalysisManager &FAM) : FAM(FAM) {}
+
+ FunctionAnalysisManager &FAM;
/// We may want to defer deleting functions to after the inlining for a whole
/// module has finished. This allows us to reliably use function pointers as
@@ -156,13 +157,14 @@ class InlineAdvisor {
/// reusable as-is for inliner pass test scenarios, as well as for regular use.
class DefaultInlineAdvisor : public InlineAdvisor {
public:
- DefaultInlineAdvisor(InlineParams Params) : Params(Params) {}
+ DefaultInlineAdvisor(FunctionAnalysisManager &FAM, InlineParams Params)
+ : InlineAdvisor(FAM), Params(Params) {}
private:
- std::unique_ptr
- getAdvice(CallBase &CB, FunctionAnalysisManager &FAM) override;
+ std::unique_ptr getAdvice(CallBase &CB) override;
void onPassExit() override { freeDeletedFunctions(); }
+
InlineParams Params;
};
@@ -173,7 +175,7 @@ class InlineAdvisorAnalysis : public
AnalysisInfoMixin {
static AnalysisKey Key;
InlineAdvisorAnalysis() = default;
struct Result {
-Result(Module &M, ModuleAnalysisManager &MAM) {}
+Result(Module &M, ModuleAnalysisManager &MAM) : M(M), MAM(MAM) {}
bool invalidate(Module &, const PreservedAnalyses &,
ModuleAnalysisManager::Invalidator &) {
// InlineAdvisor must be preserved across analysis invalidations.
@@ -184,6 +186,8 @@ class InlineAdvisorAnalysis : public
AnalysisInfoMixin {
void clear() { Advisor.reset(); }
private:
+Module &M;
+ModuleAnalysisManager &MAM;
std::unique_ptr Advisor;
};
diff --git a/llvm/include/llvm/Transforms/IPO/Inliner.h
b/llvm/include/llvm/Transforms/IPO/Inliner.h
index 447616102c0d..3454b0af0d9f 100644
--- a/llvm/include/llvm/Transforms/IPO/Inliner.h
+++ b/llvm/include/llvm/Transforms/IPO/Inliner.h
@@ -106,7 +106,7 @@ class InlinerPass : public PassInfoMixin {
private:
InlineAdvisor &getAdvisor(const ModuleAnalysisManagerCGSCCProxy::Result &MAM,
-Module &M);
+FunctionAnalysisManager &FAM, Module &M);
std::unique_ptr ImportedFunctionsStats;
Optional OwnedDefaultAdvisor;
};
diff --git a/llvm/lib/Analysis/InlineAdvisor.cpp
b/llvm/lib/Analysis/InlineAdvisor.cpp
index ac3ba451aa3f..7af8a4dffcba 100644
--- a/llvm/lib/Analysis/InlineAdvisor.cpp
+++ b/llvm/lib/Analysis/InlineAdvisor.cpp
@@ -90,8 +90,7 @@ class DefaultInlineAdvice : public InlineAdvice {
} // namespace
-std::unique_ptr
-DefaultInlineAdvisor::getAdvice(CallBase &CB, FunctionAnalysisManager &FAM) {
+std::unique_ptr DefaultInlineAdvisor::getAdvice(CallBase &CB) {
Function &Caller = *CB.getCaller();
ProfileSummaryInfo *PSI =
FAM.getResult(Caller)
@@ -149,9 +148,10 @@ AnalysisKey InlineAdvisorAnalysis::Key;
bool InlineAdvisorAnalysis::Result::tryCreate(InlineParams Params,
InliningAdvisorMode Mode) {
+ auto &FAM =
MAM.getResult(M).getManager();
switch (Mode) {
case InliningAdvisorMode::Default:
-Advisor.reset(new DefaultInlineAdvisor(Params));
+Advisor.reset(new DefaultInlineAdvisor(FA
[llvm-branch-commits] [llvm] cd6cd91 - [BrachProbablityInfo] Proportional distribution of reachable probabilities
Author: Yevgeny Rouban
Date: 2020-06-02T11:28:12+07:00
New Revision: cd6cd911352ce171253c922d7c21371068a336ce
URL:
https://github.com/llvm/llvm-project/commit/cd6cd911352ce171253c922d7c21371068a336ce
DIFF:
https://github.com/llvm/llvm-project/commit/cd6cd911352ce171253c922d7c21371068a336ce.diff
LOG: [BrachProbablityInfo] Proportional distribution of reachable probabilities
When fixing probability of unreachable edges in
BranchProbabilityInfo::calcMetadataWeights() proportionally distribute
remainder probability over the reachable edges. The old implementation
distributes the remainder probability evenly.
See examples in the fixed tests.
Reviewers: yamauchi, ebrevnov
Tags: #llvm
Differential Revision: https://reviews.llvm.org/D80611
Added:
Modified:
llvm/lib/Analysis/BranchProbabilityInfo.cpp
llvm/test/Analysis/BranchProbabilityInfo/basic.ll
Removed:
diff --git a/llvm/lib/Analysis/BranchProbabilityInfo.cpp
b/llvm/lib/Analysis/BranchProbabilityInfo.cpp
index 311ba19c727a..7f1d27abcdc1 100644
--- a/llvm/lib/Analysis/BranchProbabilityInfo.cpp
+++ b/llvm/lib/Analysis/BranchProbabilityInfo.cpp
@@ -102,7 +102,7 @@ static const uint32_t LBH_UNLIKELY_WEIGHT = 62;
///
/// This is the probability for a branch being taken to a block that terminates
/// (eventually) in unreachable. These are predicted as unlikely as possible.
-/// All reachable probability will equally share the remaining part.
+/// All reachable probability will proportionally share the remaining part.
static const BranchProbability UR_TAKEN_PROB = BranchProbability::getRaw(1);
/// Weight for a branch taken going into a cold block.
@@ -349,35 +349,69 @@ bool BranchProbabilityInfo::calcMetadataWeights(const
BasicBlock *BB) {
// Examine the metadata against unreachable heuristic.
// If the unreachable heuristic is more strong then we use it for this edge.
- if (UnreachableIdxs.size() > 0 && ReachableIdxs.size() > 0) {
-auto UnreachableProb = UR_TAKEN_PROB;
-for (auto I : UnreachableIdxs)
- if (UnreachableProb < BP[I]) {
-BP[I] = UnreachableProb;
- }
+ if (UnreachableIdxs.size() == 0 || ReachableIdxs.size() == 0) {
+setEdgeProbability(BB, BP);
+return true;
+ }
+
+ auto UnreachableProb = UR_TAKEN_PROB;
+ for (auto I : UnreachableIdxs)
+if (UnreachableProb < BP[I]) {
+ BP[I] = UnreachableProb;
+}
-// Because of possible rounding errors and the above fix up for
-// the unreachable heuristic the sum of probabilities of all edges may be
-// less than 1.0. Distribute the remaining probability (calculated as
-// 1.0 - (sum of BP[i])) evenly among all the reachable edges.
-auto ToDistribute = BranchProbability::getOne();
-for (auto &P : BP)
- ToDistribute -= P;
-
-// If we modified the probability of some edges then we must distribute
-// the
diff erence between reachable blocks.
-// TODO: This spreads ToDistribute evenly upon the reachable edges. A
better
-// distribution would be proportional. So the relation between weights of
-// the reachable edges would be kept unchanged. That is for any reachable
-// edges i and j:
-// newBP[i] / newBP[j] == oldBP[i] / oldBP[j]
-// newBP[i] / oldBP[i] == newBP[j] / oldBP[j] ==
-// == Denominator / (Denominator - ToDistribute)
-// newBP[i] = oldBP[i] * Denominator / (Denominator - ToDistribute)
-BranchProbability PerEdge = ToDistribute / ReachableIdxs.size();
-if (PerEdge > BranchProbability::getZero())
+ // Sum of all edge probabilities must be 1.0. If we modified the probability
+ // of some edges then we must distribute the introduced
diff erence over the
+ // reachable blocks.
+ //
+ // Proportional distribution: the relation between probabilities of the
+ // reachable edges is kept unchanged. That is for any reachable edges i and
j:
+ // newBP[i] / newBP[j] == oldBP[i] / oldBP[j] =>
+ // newBP[i] / oldBP[i] == newBP[j] / oldBP[j] == K
+ // Where K is independent of i,j.
+ // newBP[i] == oldBP[i] * K
+ // We need to find K.
+ // Make sum of all reachables of the left and right parts:
+ // sum_of_reachable(newBP) == K * sum_of_reachable(oldBP)
+ // Sum of newBP must be equal to 1.0:
+ // sum_of_reachable(newBP) + sum_of_unreachable(newBP) == 1.0 =>
+ // sum_of_reachable(newBP) = 1.0 - sum_of_unreachable(newBP)
+ // Where sum_of_unreachable(newBP) is what has been just changed.
+ // Finally:
+ // K == sum_of_reachable(newBP) / sum_of_reachable(oldBP) =>
+ // K == (1.0 - sum_of_unreachable(newBP)) / sum_of_reachable(oldBP)
+ BranchProbability NewUnreachableSum = BranchProbability::getZero();
+ for (auto I : UnreachableIdxs)
+NewUnreachableSum += BP[I];
+
+ BranchProbability NewReachableSum =
+ BranchProbability::getOne() - NewUnreachableSum;
+
+ BranchProbability OldReachableSum = BranchProb
