Successfully identified regression in *llvm* in CI configuration
tcwg_bmk_llvm_tk1/llvm-master-arm-spec2k6-Oz_LTO. So far, this commit has
regressed CI configurations:
- tcwg_bmk_llvm_tk1/llvm-master-arm-spec2k6-Oz_LTO
Culprit:
<cut>
commit 51d334a845a082338735b0fdfc620a4b15fa26fe
Author: Max Kazantsev <mkazant...@azul.com>
Date: Thu May 27 13:20:57 2021 +0700
[NFCI] Lazily evaluate SCEVs of PHIs
Eager evaluation has cost of compile time. Only query them if they are
required for proving predicates.
</cut>
Results regressed to (for first_bad == 51d334a845a082338735b0fdfc620a4b15fa26fe)
# reset_artifacts:
-10
# build_abe binutils:
-9
# build_abe stage1 -- --set gcc_override_configure=--with-mode=thumb --set
gcc_override_configure=--disable-libsanitizer:
-8
# build_abe linux:
-7
# build_abe glibc:
-6
# build_abe stage2 -- --set gcc_override_configure=--with-mode=thumb --set
gcc_override_configure=--disable-libsanitizer:
-5
# build_llvm true:
-3
# true:
0
# benchmark -Oz_LTO_mthumb --
artifacts/build-51d334a845a082338735b0fdfc620a4b15fa26fe/results_id:
1
# 450.soplex,soplex_base.default regressed by
509909
# 473.astar,astar_base.default regressed by
4232401
# 453.povray,povray_base.default regressed by
166915
# 403.gcc,gcc_base.default regressed by
50755
from (for last_good == 59d938e649e62db0cef4903d495e838fbc6a6eb8)
# reset_artifacts:
-10
# build_abe binutils:
-9
# build_abe stage1 -- --set gcc_override_configure=--with-mode=thumb --set
gcc_override_configure=--disable-libsanitizer:
-8
# build_abe linux:
-7
# build_abe glibc:
-6
# build_abe stage2 -- --set gcc_override_configure=--with-mode=thumb --set
gcc_override_configure=--disable-libsanitizer:
-5
# build_llvm true:
-3
# true:
0
# benchmark -Oz_LTO_mthumb --
artifacts/build-59d938e649e62db0cef4903d495e838fbc6a6eb8/results_id:
1
Artifacts of last_good build:
https://ci.linaro.org/job/tcwg_bmk_ci_llvm-bisect-tcwg_bmk_tk1-llvm-master-arm-spec2k6-Oz_LTO/10/artifact/artifacts/build-59d938e649e62db0cef4903d495e838fbc6a6eb8/
Results ID of last_good:
tk1_32/tcwg_bmk_llvm_tk1/bisect-llvm-master-arm-spec2k6-Oz_LTO/1235
Artifacts of first_bad build:
https://ci.linaro.org/job/tcwg_bmk_ci_llvm-bisect-tcwg_bmk_tk1-llvm-master-arm-spec2k6-Oz_LTO/10/artifact/artifacts/build-51d334a845a082338735b0fdfc620a4b15fa26fe/
Results ID of first_bad:
tk1_32/tcwg_bmk_llvm_tk1/bisect-llvm-master-arm-spec2k6-Oz_LTO/1241
Build top page/logs:
https://ci.linaro.org/job/tcwg_bmk_ci_llvm-bisect-tcwg_bmk_tk1-llvm-master-arm-spec2k6-Oz_LTO/10/
Configuration details:
Reproduce builds:
<cut>
mkdir investigate-llvm-51d334a845a082338735b0fdfc620a4b15fa26fe
cd investigate-llvm-51d334a845a082338735b0fdfc620a4b15fa26fe
git clone https://git.linaro.org/toolchain/jenkins-scripts
mkdir -p artifacts/manifests
curl -o artifacts/manifests/build-baseline.sh
https://ci.linaro.org/job/tcwg_bmk_ci_llvm-bisect-tcwg_bmk_tk1-llvm-master-arm-spec2k6-Oz_LTO/10/artifact/artifacts/manifests/build-baseline.sh
--fail
curl -o artifacts/manifests/build-parameters.sh
https://ci.linaro.org/job/tcwg_bmk_ci_llvm-bisect-tcwg_bmk_tk1-llvm-master-arm-spec2k6-Oz_LTO/10/artifact/artifacts/manifests/build-parameters.sh
--fail
curl -o artifacts/test.sh
https://ci.linaro.org/job/tcwg_bmk_ci_llvm-bisect-tcwg_bmk_tk1-llvm-master-arm-spec2k6-Oz_LTO/10/artifact/artifacts/test.sh
--fail
chmod +x artifacts/test.sh
# Reproduce the baseline build (build all pre-requisites)
./jenkins-scripts/tcwg_bmk-build.sh @@ artifacts/manifests/build-baseline.sh
cd llvm
# Reproduce first_bad build
git checkout --detach 51d334a845a082338735b0fdfc620a4b15fa26fe
../artifacts/test.sh
# Reproduce last_good build
git checkout --detach 59d938e649e62db0cef4903d495e838fbc6a6eb8
../artifacts/test.sh
cd ..
</cut>
History of pending regressions and results:
https://git.linaro.org/toolchain/ci/base-artifacts.git/log/?h=linaro-local/ci/tcwg_bmk_llvm_tk1/llvm-master-arm-spec2k6-Oz_LTO
Artifacts:
https://ci.linaro.org/job/tcwg_bmk_ci_llvm-bisect-tcwg_bmk_tk1-llvm-master-arm-spec2k6-Oz_LTO/10/artifact/artifacts/
Build log:
https://ci.linaro.org/job/tcwg_bmk_ci_llvm-bisect-tcwg_bmk_tk1-llvm-master-arm-spec2k6-Oz_LTO/10/consoleText
Full commit (up to 1000 lines):
<cut>
commit 51d334a845a082338735b0fdfc620a4b15fa26fe
Author: Max Kazantsev <mkazant...@azul.com>
Date: Thu May 27 13:20:57 2021 +0700
[NFCI] Lazily evaluate SCEVs of PHIs
Eager evaluation has cost of compile time. Only query them if they are
required for proving predicates.
---
llvm/lib/Transforms/Scalar/LoopDeletion.cpp | 115 +++++++++++++++++-----------
1 file changed, 72 insertions(+), 43 deletions(-)
diff --git a/llvm/lib/Transforms/Scalar/LoopDeletion.cpp
b/llvm/lib/Transforms/Scalar/LoopDeletion.cpp
index cd2a3fc48e3b..ed6b078fcf8e 100644
--- a/llvm/lib/Transforms/Scalar/LoopDeletion.cpp
+++ b/llvm/lib/Transforms/Scalar/LoopDeletion.cpp
@@ -136,30 +136,88 @@ static bool isLoopNeverExecuted(Loop *L) {
return true;
}
+BasicBlock *
+getSolePredecessorOnFirstIteration(BasicBlock *BB, Loop *L,
+ const DenseSet<BasicBlockEdge> &LiveEdges) {
+ if (BB == L->getHeader())
+ return L->getLoopPredecessor();
+ BasicBlock *OnlyPred = nullptr;
+ for (auto *Pred : predecessors(BB))
+ if (OnlyPred != Pred && LiveEdges.count({ Pred, BB })) {
+ // 2 live preds.
+ if (OnlyPred)
+ return nullptr;
+ OnlyPred = Pred;
+ }
+
+ assert(OnlyPred && "No live predecessors?");
+ return OnlyPred;
+}
+
+// Forward declaration.
+static const SCEV *
+getSCEVOnFirstIteration(Value *V, Loop *L, DominatorTree &DT,
+ ScalarEvolution &SE,
+ DenseMap<Value *, const SCEV *> &FirstIterSCEV,
+ const DenseSet<BasicBlockEdge> &LiveEdges);
+
static const SCEV *
-getSCEVOnFirstIteration(Value *V, Loop *L, ScalarEvolution &SE,
- DenseMap<Value *, const SCEV *> &FirstIterSCEV) {
+getPHISCEVOnFirstIteration(PHINode *PN, Loop *L, DominatorTree &DT,
+ ScalarEvolution &SE,
+ DenseMap<Value *, const SCEV *> &FirstIterSCEV,
+ const DenseSet<BasicBlockEdge> &LiveEdges) {
+ auto *BB = PN->getParent();
+ if (!L->contains(PN))
+ return SE.getSCEV(PN);
+ // If this block has only one live pred, map its phis onto their SCEVs.
+ // Check if there is only one predecessor on 1st iteration. Note that because
+ // we iterate in RPOT, we have already visited all its (non-latch)
+ // predecessors.
+ auto *OnlyPred = getSolePredecessorOnFirstIteration(BB, L, LiveEdges);
+ if (!OnlyPred)
+ return SE.getSCEV(PN);
+ auto *Incoming = PN->getIncomingValueForBlock(OnlyPred);
+ if (DT.dominates(Incoming, BB->getTerminator()))
+ return getSCEVOnFirstIteration(Incoming, L, DT, SE, FirstIterSCEV,
+ LiveEdges);
+ return SE.getSCEV(PN);
+}
+
+static const SCEV *
+getSCEVOnFirstIteration(Value *V, Loop *L, DominatorTree &DT,
+ ScalarEvolution &SE,
+ DenseMap<Value *, const SCEV *> &FirstIterSCEV,
+ const DenseSet<BasicBlockEdge> &LiveEdges) {
// Fist, check in cache.
auto Existing = FirstIterSCEV.find(V);
if (Existing != FirstIterSCEV.end())
return Existing->second;
+
const SCEV *S = nullptr;
// TODO: Once ScalarEvolution supports getValueOnNthIteration for anything
// else but AddRecs, it's a good use case for it. So far, just consider some
// simple cases, like arithmetic operations.
Value *LHS, *RHS;
using namespace PatternMatch;
- if (match(V, m_Add(m_Value(LHS), m_Value(RHS)))) {
- const SCEV *LHSS = getSCEVOnFirstIteration(LHS, L, SE, FirstIterSCEV);
- const SCEV *RHSS = getSCEVOnFirstIteration(RHS, L, SE, FirstIterSCEV);
+ if (auto *PN = dyn_cast<PHINode>(V)) {
+ S = getPHISCEVOnFirstIteration(PN, L, DT, SE, FirstIterSCEV, LiveEdges);
+ } else if (match(V, m_Add(m_Value(LHS), m_Value(RHS)))) {
+ const SCEV *LHSS =
+ getSCEVOnFirstIteration(LHS, L, DT, SE, FirstIterSCEV, LiveEdges);
+ const SCEV *RHSS =
+ getSCEVOnFirstIteration(RHS, L, DT, SE, FirstIterSCEV, LiveEdges);
S = SE.getAddExpr(LHSS, RHSS);
} else if (match(V, m_Sub(m_Value(LHS), m_Value(RHS)))) {
- const SCEV *LHSS = getSCEVOnFirstIteration(LHS, L, SE, FirstIterSCEV);
- const SCEV *RHSS = getSCEVOnFirstIteration(RHS, L, SE, FirstIterSCEV);
+ const SCEV *LHSS =
+ getSCEVOnFirstIteration(LHS, L, DT, SE, FirstIterSCEV, LiveEdges);
+ const SCEV *RHSS =
+ getSCEVOnFirstIteration(RHS, L, DT, SE, FirstIterSCEV, LiveEdges);
S = SE.getMinusSCEV(LHSS, RHSS);
} else if (match(V, m_Mul(m_Value(LHS), m_Value(RHS)))) {
- const SCEV *LHSS = getSCEVOnFirstIteration(LHS, L, SE, FirstIterSCEV);
- const SCEV *RHSS = getSCEVOnFirstIteration(RHS, L, SE, FirstIterSCEV);
+ const SCEV *LHSS =
+ getSCEVOnFirstIteration(LHS, L, DT, SE, FirstIterSCEV, LiveEdges);
+ const SCEV *RHSS =
+ getSCEVOnFirstIteration(RHS, L, DT, SE, FirstIterSCEV, LiveEdges);
S = SE.getMulExpr(LHSS, RHSS);
} else
S = SE.getSCEV(V);
@@ -185,7 +243,7 @@ static bool canProveExitOnFirstIteration(Loop *L,
DominatorTree &DT,
SmallPtrSet<BasicBlock *, 4> LiveBlocks;
// Edges that are reachable on the 1st iteration.
DenseSet<BasicBlockEdge> LiveEdges;
- LiveBlocks.insert(L->getHeader());
+ LiveBlocks.insert(Header);
auto MarkLiveEdge = [&](BasicBlock *From, BasicBlock *To) {
assert(LiveBlocks.count(From) && "Must be live!");
@@ -198,24 +256,6 @@ static bool canProveExitOnFirstIteration(Loop *L,
DominatorTree &DT,
MarkLiveEdge(BB, Succ);
};
- // Check if there is only one predecessor on 1st iteration. Note that because
- // we iterate in RPOT, we have already visited all its (non-latch)
- // predecessors.
- auto GetSolePredecessorOnFirstIteration = [&](BasicBlock * BB)->BasicBlock *
{
- if (BB == Header)
- return L->getLoopPredecessor();
- BasicBlock *OnlyPred = nullptr;
- for (auto *Pred : predecessors(BB))
- if (OnlyPred != Pred && LiveEdges.count({ Pred, BB })) {
- // 2 live preds.
- if (OnlyPred)
- return nullptr;
- OnlyPred = Pred;
- }
-
- assert(OnlyPred && "No live predecessors?");
- return OnlyPred;
- };
DenseMap<Value *, const SCEV *> FirstIterSCEV;
SmallPtrSet<BasicBlock *, 4> Visited;
@@ -250,19 +290,6 @@ static bool canProveExitOnFirstIteration(Loop *L,
DominatorTree &DT,
if (!Visited.count(Pred))
return false;
- // If this block has only one live pred, map its phis onto their SCEVs.
- if (auto *OnlyPred = GetSolePredecessorOnFirstIteration(BB))
- for (auto &PN : BB->phis()) {
- if (!SE.isSCEVable(PN.getType()))
- continue;
- auto *Incoming = PN.getIncomingValueForBlock(OnlyPred);
- if (DT.dominates(Incoming, BB->getTerminator())) {
- const SCEV *IncSCEV =
- getSCEVOnFirstIteration(Incoming, L, SE, FirstIterSCEV);
- FirstIterSCEV[&PN] = IncSCEV;
- }
- }
-
using namespace PatternMatch;
ICmpInst::Predicate Pred;
Value *LHS, *RHS;
@@ -281,8 +308,10 @@ static bool canProveExitOnFirstIteration(Loop *L,
DominatorTree &DT,
}
// Can we prove constant true or false for this condition?
- const SCEV *LHSS = getSCEVOnFirstIteration(LHS, L, SE, FirstIterSCEV);
- const SCEV *RHSS = getSCEVOnFirstIteration(RHS, L, SE, FirstIterSCEV);
+ const SCEV *LHSS =
+ getSCEVOnFirstIteration(LHS, L, DT, SE, FirstIterSCEV, LiveEdges);
+ const SCEV *RHSS =
+ getSCEVOnFirstIteration(RHS, L, DT, SE, FirstIterSCEV, LiveEdges);
// Only query for liveness of in-loop edge if another successor is also
// in-loop.
// TODO: isKnownPredicateAt is more powerful, but it's too compile time
</cut>
_______________________________________________
linaro-toolchain mailing list
linaro-toolchain@lists.linaro.org
https://lists.linaro.org/mailman/listinfo/linaro-toolchain
