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 mkazantsev@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-a... 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-a... 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-a...

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-a... --fail curl -o artifacts/manifests/build-parameters.sh https://ci.linaro.org/job/tcwg_bmk_ci_llvm-bisect-tcwg_bmk_tk1-llvm-master-a... --fail curl -o artifacts/test.sh https://ci.linaro.org/job/tcwg_bmk_ci_llvm-bisect-tcwg_bmk_tk1-llvm-master-a... --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/c...

Artifacts: https://ci.linaro.org/job/tcwg_bmk_ci_llvm-bisect-tcwg_bmk_tk1-llvm-master-a... Build log: https://ci.linaro.org/job/tcwg_bmk_ci_llvm-bisect-tcwg_bmk_tk1-llvm-master-a...

Full commit (up to 1000 lines): <cut> commit 51d334a845a082338735b0fdfc620a4b15fa26fe Author: Max Kazantsev mkazantsev@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>