From 189efe295b6e843c53c172e9f26436f9e8434d21 Mon Sep 17 00:00:00 2001 From: Florian Hahn Date: Wed, 31 Jul 2019 09:27:54 +0000 Subject: [PATCH] Recommit "[GVN] Preserve loop related analysis/canonical forms." This fixes some pipeline tests. This reverts commit d0b6f42936bfb6d56d325c732ae79400c9c6016a. llvm-svn: 367401 --- llvm/include/llvm/Analysis/CFG.h | 2 + llvm/include/llvm/Transforms/Scalar/GVN.h | 1 + llvm/lib/Analysis/CFG.cpp | 11 ++++- llvm/lib/Transforms/Scalar/GVN.cpp | 25 ++++++++-- llvm/test/Other/opt-O2-pipeline.ll | 1 - llvm/test/Other/opt-O3-pipeline.ll | 1 - llvm/test/Other/opt-Os-pipeline.ll | 1 - .../GVN/PRE/2011-06-01-NonLocalMemdepMiscompile.ll | 10 +++- llvm/test/Transforms/GVN/preserve-analysis.ll | 56 ++++++++++++++++++++++ 9 files changed, 96 insertions(+), 12 deletions(-) create mode 100644 llvm/test/Transforms/GVN/preserve-analysis.ll diff --git a/llvm/include/llvm/Analysis/CFG.h b/llvm/include/llvm/Analysis/CFG.h index bb55e76..68f137b 100644 --- a/llvm/include/llvm/Analysis/CFG.h +++ b/llvm/include/llvm/Analysis/CFG.h @@ -46,6 +46,8 @@ unsigned GetSuccessorNumber(const BasicBlock *BB, const BasicBlock *Succ); /// bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges = false); +bool isCriticalEdge(const Instruction *TI, const BasicBlock *Succ, + bool AllowIdenticalEdges = false); /// Determine whether instruction 'To' is reachable from 'From', without passing /// through any blocks in ExclusionSet, returning true if uncertain. diff --git a/llvm/include/llvm/Transforms/Scalar/GVN.h b/llvm/include/llvm/Transforms/Scalar/GVN.h index 9fe00a9..2c9287f 100644 --- a/llvm/include/llvm/Transforms/Scalar/GVN.h +++ b/llvm/include/llvm/Transforms/Scalar/GVN.h @@ -159,6 +159,7 @@ private: SetVector DeadBlocks; OptimizationRemarkEmitter *ORE; ImplicitControlFlowTracking *ICF; + LoopInfo *LI; ValueTable VN; diff --git a/llvm/lib/Analysis/CFG.cpp b/llvm/lib/Analysis/CFG.cpp index 18b83d6..8215b4e 100644 --- a/llvm/lib/Analysis/CFG.cpp +++ b/llvm/lib/Analysis/CFG.cpp @@ -87,11 +87,18 @@ unsigned llvm::GetSuccessorNumber(const BasicBlock *BB, /// with multiple predecessors. bool llvm::isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges) { - assert(TI->isTerminator() && "Must be a terminator to have successors!"); assert(SuccNum < TI->getNumSuccessors() && "Illegal edge specification!"); + return isCriticalEdge(TI, TI->getSuccessor(SuccNum), AllowIdenticalEdges); +} + +bool llvm::isCriticalEdge(const Instruction *TI, const BasicBlock *Dest, + bool AllowIdenticalEdges) { + assert(TI->isTerminator() && "Must be a terminator to have successors!"); if (TI->getNumSuccessors() == 1) return false; - const BasicBlock *Dest = TI->getSuccessor(SuccNum); + assert(find(predecessors(Dest), TI->getParent()) != pred_end(Dest) && + "No edge between TI's block and Dest."); + const_pred_iterator I = pred_begin(Dest), E = pred_end(Dest); // If there is more than one predecessor, this is a critical edge... diff --git a/llvm/lib/Transforms/Scalar/GVN.cpp b/llvm/lib/Transforms/Scalar/GVN.cpp index 1a02e9d..29911a4 100644 --- a/llvm/lib/Transforms/Scalar/GVN.cpp +++ b/llvm/lib/Transforms/Scalar/GVN.cpp @@ -70,6 +70,7 @@ #include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Utils.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/Local.h" #include "llvm/Transforms/Utils/SSAUpdater.h" @@ -626,6 +627,8 @@ PreservedAnalyses GVN::run(Function &F, FunctionAnalysisManager &AM) { PA.preserve(); PA.preserve(); PA.preserve(); + if (LI) + PA.preserve(); return PA; } @@ -1976,6 +1979,7 @@ bool GVN::runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT, MD = RunMD; ImplicitControlFlowTracking ImplicitCFT(DT); ICF = &ImplicitCFT; + this->LI = LI; VN.setMemDep(MD); ORE = RunORE; InvalidBlockRPONumbers = true; @@ -2335,7 +2339,7 @@ bool GVN::performPRE(Function &F) { /// the block inserted to the critical edge. BasicBlock *GVN::splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ) { BasicBlock *BB = - SplitCriticalEdge(Pred, Succ, CriticalEdgeSplittingOptions(DT)); + SplitCriticalEdge(Pred, Succ, CriticalEdgeSplittingOptions(DT, LI)); if (MD) MD->invalidateCachedPredecessors(); InvalidBlockRPONumbers = true; @@ -2350,7 +2354,7 @@ bool GVN::splitCriticalEdges() { do { std::pair Edge = toSplit.pop_back_val(); SplitCriticalEdge(Edge.first, Edge.second, - CriticalEdgeSplittingOptions(DT)); + CriticalEdgeSplittingOptions(DT, LI)); } while (!toSplit.empty()); if (MD) MD->invalidateCachedPredecessors(); InvalidBlockRPONumbers = true; @@ -2456,18 +2460,26 @@ void GVN::addDeadBlock(BasicBlock *BB) { if (DeadBlocks.count(B)) continue; + // First, split the critical edges. This might also create additional blocks + // to preserve LoopSimplify form and adjust edges accordingly. SmallVector Preds(pred_begin(B), pred_end(B)); for (BasicBlock *P : Preds) { if (!DeadBlocks.count(P)) continue; - if (isCriticalEdge(P->getTerminator(), GetSuccessorNumber(P, B))) { + if (llvm::any_of(successors(P), + [B](BasicBlock *Succ) { return Succ == B; }) && + isCriticalEdge(P->getTerminator(), B)) { if (BasicBlock *S = splitCriticalEdges(P, B)) DeadBlocks.insert(P = S); } + } - for (BasicBlock::iterator II = B->begin(); isa(II); ++II) { - PHINode &Phi = cast(*II); + // Now undef the incoming values from the dead predecessors. + for (BasicBlock *P : predecessors(B)) { + if (!DeadBlocks.count(P)) + continue; + for (PHINode &Phi : B->phis()) { Phi.setIncomingValueForBlock(P, UndefValue::get(Phi.getType())); if (MD) MD->invalidateCachedPointerInfo(&Phi); @@ -2556,6 +2568,7 @@ public: AU.addRequired(); AU.addRequired(); AU.addRequired(); + AU.addRequired(); if (!NoMemDepAnalysis) AU.addRequired(); AU.addRequired(); @@ -2563,6 +2576,8 @@ public: AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); + AU.addPreserved(); + AU.addPreservedID(LoopSimplifyID); AU.addRequired(); } diff --git a/llvm/test/Other/opt-O2-pipeline.ll b/llvm/test/Other/opt-O2-pipeline.ll index 8f4d98f..ecd6b7c 100644 --- a/llvm/test/Other/opt-O2-pipeline.ll +++ b/llvm/test/Other/opt-O2-pipeline.ll @@ -141,7 +141,6 @@ ; CHECK-NEXT: Bit-Tracking Dead Code Elimination ; CHECK-NEXT: Basic Alias Analysis (stateless AA impl) ; CHECK-NEXT: Function Alias Analysis Results -; CHECK-NEXT: Natural Loop Information ; CHECK-NEXT: Lazy Branch Probability Analysis ; CHECK-NEXT: Lazy Block Frequency Analysis ; CHECK-NEXT: Optimization Remark Emitter diff --git a/llvm/test/Other/opt-O3-pipeline.ll b/llvm/test/Other/opt-O3-pipeline.ll index 07e20b8..ee5e55f 100644 --- a/llvm/test/Other/opt-O3-pipeline.ll +++ b/llvm/test/Other/opt-O3-pipeline.ll @@ -146,7 +146,6 @@ ; CHECK-NEXT: Bit-Tracking Dead Code Elimination ; CHECK-NEXT: Basic Alias Analysis (stateless AA impl) ; CHECK-NEXT: Function Alias Analysis Results -; CHECK-NEXT: Natural Loop Information ; CHECK-NEXT: Lazy Branch Probability Analysis ; CHECK-NEXT: Lazy Block Frequency Analysis ; CHECK-NEXT: Optimization Remark Emitter diff --git a/llvm/test/Other/opt-Os-pipeline.ll b/llvm/test/Other/opt-Os-pipeline.ll index bacda22..069d198 100644 --- a/llvm/test/Other/opt-Os-pipeline.ll +++ b/llvm/test/Other/opt-Os-pipeline.ll @@ -128,7 +128,6 @@ ; CHECK-NEXT: Bit-Tracking Dead Code Elimination ; CHECK-NEXT: Basic Alias Analysis (stateless AA impl) ; CHECK-NEXT: Function Alias Analysis Results -; CHECK-NEXT: Natural Loop Information ; CHECK-NEXT: Lazy Branch Probability Analysis ; CHECK-NEXT: Lazy Block Frequency Analysis ; CHECK-NEXT: Optimization Remark Emitter diff --git a/llvm/test/Transforms/GVN/PRE/2011-06-01-NonLocalMemdepMiscompile.ll b/llvm/test/Transforms/GVN/PRE/2011-06-01-NonLocalMemdepMiscompile.ll index 05dc79d..6592c69 100644 --- a/llvm/test/Transforms/GVN/PRE/2011-06-01-NonLocalMemdepMiscompile.ll +++ b/llvm/test/Transforms/GVN/PRE/2011-06-01-NonLocalMemdepMiscompile.ll @@ -50,8 +50,14 @@ bb15: %tmp18 = icmp eq i8 %tmp17, 0 br label %bb19 -; CHECK: bb15: -; CHECK: %tmp17 = phi i8 [ %tmp17.pre, %bb1.bb15_crit_edge ], [ %tmp8, %bb6 ] +; CHECK-LABEL: bb6: +; CHECK: br i1 undef, label %bb15split, label %bb10 + +; CHECK-LABEL: bb15split: ; preds = %bb6 +; CHECK-NEXT: br label %bb15 + +; CHECK-LABEL: bb15: +; CHECK: %tmp17 = phi i8 [ %tmp8, %bb15split ], [ %tmp17.pre, %bb1.bb15_crit_edge ] bb19: ; preds = %bb15 ret i1 %tmp18 diff --git a/llvm/test/Transforms/GVN/preserve-analysis.ll b/llvm/test/Transforms/GVN/preserve-analysis.ll new file mode 100644 index 0000000..2454bb1a --- /dev/null +++ b/llvm/test/Transforms/GVN/preserve-analysis.ll @@ -0,0 +1,56 @@ +; RUN: opt < %s -debug-pass=Structure -indvars -gvn -indvars 2>&1 -S | FileCheck --check-prefix=CHECK --check-prefix=IR %s +; RUN: opt < %s -debug-pass-manager -passes='require,loop(simplify-cfg),gvn,loop(indvars)' 2>&1 -S | FileCheck --check-prefix=NEW-PM --check-prefix=IR %s + +; Check CFG-only analysis are preserved by SCCP by running it between 2 +; loop-vectorize runs. + +; CHECK: Dominator Tree Construction +; CHECK: Natural Loop Information +; CHECK: Canonicalize natural loops +; CHECK: LCSSA Verifier +; CHECK: Loop-Closed SSA Form Pass +; CHECK: Global Value Numbering +; CHECK-NOT: Dominator Tree Construction +; CHECK-NOT: Natural Loop Information +; CHECK-NOT: Canonicalize natural loops + +; NEW-PM-DAG: Running analysis: LoopAnalysis on test +; NEW-PM-DAG: Running analysis: DominatorTreeAnalysis on test +; NEW-PM: Running pass: GVN on test +; NEW-PM-NOT: Running analysis: LoopAnalysis on test +; NEW-PM-NOT: Running analysis: DominatorTreeAnalysis on test + +declare i1 @cond() +declare void @dostuff() + +define i32 @test() { +; IR-LABEL: define i32 @test() +; IR-LABEL: header: +; IR: br i1 false, label %then, label %latch +; IR-LABEL: then: +; IR-NEXT: call void @dostuff() +; IR-NEXT: br label %latch +entry: + %res = add i32 1, 10 + br label %header + +header: + %iv = phi i32 [ %res, %entry ], [ 0, %latch ] + %ic = icmp eq i32 %res, 99 + br i1 %ic, label %then, label %latch + +then: + br label %then.2 + +then.2: + call void @dostuff() + br label %latch + + +latch: + %ec = call i1 @cond() + br i1 %ec, label %exit, label %header + +exit: + ret i32 %iv +} -- 2.7.4