summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--llvm/include/llvm/Analysis/CFG.h2
-rw-r--r--llvm/include/llvm/Transforms/Scalar/GVN.h1
-rw-r--r--llvm/lib/Analysis/CFG.cpp11
-rw-r--r--llvm/lib/Transforms/Scalar/GVN.cpp25
-rw-r--r--llvm/test/Transforms/GVN/PRE/2011-06-01-NonLocalMemdepMiscompile.ll10
-rw-r--r--llvm/test/Transforms/GVN/preserve-analysis.ll56
6 files changed, 96 insertions, 9 deletions
diff --git a/llvm/include/llvm/Analysis/CFG.h b/llvm/include/llvm/Analysis/CFG.h
index bb55e76ac86..68f137ba622 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 9fe00a9e7f2..2c9287f86cd 100644
--- a/llvm/include/llvm/Transforms/Scalar/GVN.h
+++ b/llvm/include/llvm/Transforms/Scalar/GVN.h
@@ -159,6 +159,7 @@ private:
SetVector<BasicBlock *> DeadBlocks;
OptimizationRemarkEmitter *ORE;
ImplicitControlFlowTracking *ICF;
+ LoopInfo *LI;
ValueTable VN;
diff --git a/llvm/lib/Analysis/CFG.cpp b/llvm/lib/Analysis/CFG.cpp
index 18b83d6838c..8215b4ecbb0 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 1a02e9d33f4..29911a4ed28 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<DominatorTreeAnalysis>();
PA.preserve<GlobalsAA>();
PA.preserve<TargetLibraryAnalysis>();
+ if (LI)
+ PA.preserve<LoopAnalysis>();
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<Instruction *, unsigned> 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<BasicBlock *, 4> 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<PHINode>(II); ++II) {
- PHINode &Phi = cast<PHINode>(*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<AssumptionCacheTracker>();
AU.addRequired<DominatorTreeWrapperPass>();
AU.addRequired<TargetLibraryInfoWrapperPass>();
+ AU.addRequired<LoopInfoWrapperPass>();
if (!NoMemDepAnalysis)
AU.addRequired<MemoryDependenceWrapperPass>();
AU.addRequired<AAResultsWrapperPass>();
@@ -2563,6 +2576,8 @@ public:
AU.addPreserved<DominatorTreeWrapperPass>();
AU.addPreserved<GlobalsAAWrapperPass>();
AU.addPreserved<TargetLibraryInfoWrapperPass>();
+ AU.addPreserved<LoopInfoWrapperPass>();
+ AU.addPreservedID(LoopSimplifyID);
AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
}
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 05dc79db95a..6592c69b027 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 00000000000..2454bb1a63d
--- /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<domtree>,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
+}
OpenPOWER on IntegriCloud