[GVN] Preserve loop related analysis/canonical forms.

[fhahn]

Summary

LoopInfo can be easily preserved by passing it to the functions that
modify the CFG (SplitCriticalEdge and MergeBlockIntoPredecessor.
SplitCriticalEdge also preserves LoopSimplify and LCSSA form when when passing in
LoopInfo. The test case shows that we preserve LoopSimplify and
LoopInfo. Adding addPreservedID(LCSSAID) did not preserve LCSSA for some
reason.

Also I am not sure if it is possible to preserve those in the new pass
manager, as they aren't analysis passes.

[jdoerfert]

Minor comments.

llvm/lib/Transforms/Scalar/GVN.cpp

2478 ↗

(On Diff #211270)

These changes, incl. the isCriticalEdge modifications above, seem unrelated to the loop info issue, are they?

llvm/test/Transforms/GVN/preserve-analysis.ll

50 ↗

(On Diff #211270)

You should check that GVN did something as well.

[fhahn]

Address Johannes' comments

[fhahn]

llvm/lib/Transforms/Scalar/GVN.cpp

2478 ↗

(On Diff #211270)

They do, but I should have made that clear. SplitCiriticalEdge will insert additional blocks to preserve LoopSimplify form, if LI is passed. Such a block might be inserted between B and one of its predecessors, which would cause GetNumSuccessor to assert. It is safer to just do it in 2 steps.

[jdoerfert]

LGTM.

Thanks for the code comment, that will help the next person as well :)

[fhahn]

Thanks!

Compile time numbers on X86 with -O3 look promising as well

Metric: compile_time

Program master patch diff
test-suite...000/183.equake/183.equake.test 0.39 0.39 -0.9%
test-suite...:: CTMark/sqlite3/sqlite3.test 11.07 11.01 -0.5%
test-suite...T2000/300.twolf/300.twolf.test 5.68 5.66 -0.4%
test-suite...SPEC/CINT95/099.go/099.go.test 3.84 3.82 -0.4%
test-suite...C/CFP2000/179.art/179.art.test 0.39 0.39 -0.4%
test-suite...129.compress/129.compress.test 0.18 0.18 -0.3%
test-suite...000/197.parser/197.parser.test 2.39 2.38 -0.3%
test-suite...6/464.h264ref/464.h264ref.test 14.67 14.63 -0.3%
test-suite :: CTMark/SPASS/SPASS.test 11.88 11.85 -0.3%
test-suite...nal/skidmarks10/skidmarks.test 1.86 1.85 -0.2%
test-suite.../CINT2000/175.vpr/175.vpr.test 2.76 2.76 -0.2%
test-suite...T2006/456.hmmer/456.hmmer.test 6.45 6.43 -0.2%
test-suite...TMark/7zip/7zip-benchmark.test 39.82 39.73 -0.2%
test-suite...CFP2000/188.ammp/188.ammp.test 2.65 2.64 -0.2%
test-suite.../CINT2000/252.eon/252.eon.test 55.19 55.31 0.2%
test-suite...T2006/458.sjeng/458.sjeng.test 2.11 2.10 -0.2%
test-suite :: CTMark/Bullet/bullet.test 25.51 25.46 -0.2%
test-suite...006/447.dealII/447.dealII.test 117.87 117.67 -0.2%
test-suite...Mark/mafft/pairlocalalign.test 8.77 8.76 -0.2%
test-suite...6/482.sphinx3/482.sphinx3.test 3.90 3.89 -0.2%
test-suite.../CINT2000/176.gcc/176.gcc.test 23.03 22.99 -0.2%
test-suite.../CINT2000/254.gap/254.gap.test 9.72 9.70 -0.2%
test-suite.../CINT95/134.perl/134.perl.test 4.83 4.83 -0.2%
test-suite...T2006/401.bzip2/401.bzip2.test 1.85 1.85 -0.2%
test-suite...CFP2000/177.mesa/177.mesa.test 9.97 9.95 -0.2%
test-suite.../CINT2000/181.mcf/181.mcf.test 0.52 0.52 -0.2%
test-suite...INT95/132.ijpeg/132.ijpeg.test 4.69 4.69 -0.1%
test-suite...006/453.povray/453.povray.test 27.30 27.27 -0.1%
test-suite...0/253.perlbmk/253.perlbmk.test 9.86 9.85 -0.1%
test-suite...:: External/Povray/povray.test 12.34 12.32 -0.1%
test-suite...SPEC/CINT95/130.li/130.li.test 1.57 1.57 -0.1%
test-suite...CFP2006/433.milc/433.milc.test 3.19 3.18 -0.1%
test-suite...INT2000/164.gzip/164.gzip.test 1.21 1.20 -0.1%
test-suite...-typeset/consumer-typeset.test 9.50 9.48 -0.1%
test-suite...ternal/HMMER/hmmcalibrate.test 6.42 6.42 -0.1%
test-suite...T2006/445.gobmk/445.gobmk.test 14.04 14.03 -0.1%
test-suite...T95/147.vortex/147.vortex.test 6.79 6.78 -0.1%
test-suite...5/124.m88ksim/124.m88ksim.test 4.03 4.02 -0.1%
test-suite :: External/Nurbs/nurbs.test 2.14 2.13 -0.1%
test-suite...ark/tramp3d-v4/tramp3d-v4.test 20.79 20.77 -0.1%
test-suite :: CTMark/lencod/lencod.test 15.30 15.29 -0.1%
test-suite...3.xalancbmk/483.xalancbmk.test 181.02 180.88 -0.1%
test-suite...006/450.soplex/450.soplex.test 29.88 29.90 0.1%
test-suite...:: CTMark/ClamAV/clamscan.test 14.01 14.00 -0.1%
test-suite...000/186.crafty/186.crafty.test 3.20 3.20 -0.1%
test-suite...T2006/473.astar/473.astar.test 1.36 1.36 -0.1%
test-suite.../CINT2006/429.mcf/429.mcf.test 0.52 0.52 -0.1%
test-suite...T2000/256.bzip2/256.bzip2.test 0.72 0.72 -0.1%
test-suite...C/CFP2006/470.lbm/470.lbm.test 0.22 0.22 -0.0%
test-suite...6/471.omnetpp/471.omnetpp.test 36.50 36.51 0.0%
test-suite...CFP2006/444.namd/444.namd.test 6.37 6.37 -0.0%
test-suite...000/255.vortex/255.vortex.test 6.79 6.79 -0.0%
test-suite...libquantum/462.libquantum.test 0.86 0.86 -0.0%
test-suite...0.perlbench/400.perlbench.test 19.05 19.05 0.0%
test-suite.../CINT2006/403.gcc/403.gcc.test 51.13 51.12 -0.0%
test-suite :: CTMark/kimwitu++/kc.test 14.78 14.79 0.0%
Geomean difference -0.2%

llvm/trunk/include/llvm/Analysis/CFG.h

 unsigned GetSuccessorNumber(const BasicBlock *BB, const BasicBlock *Succ);
 
 /// Return true if the specified edge is a critical edge. Critical edges are
 /// edges from a block with multiple successors to a block with multiple
 /// predecessors.
 ///
 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.
 ///
 /// Determine whether there is a path from From to To within a single function.
 /// Returns false only if we can prove that once 'From' has been executed then
 /// 'To' can not be executed. Conservatively returns true.
 ///

llvm/trunk/include/llvm/Transforms/Scalar/GVN.h

private:
 
   MemoryDependenceResults *MD;
   DominatorTree *DT;
   const TargetLibraryInfo *TLI;
   AssumptionCache *AC;
   SetVector<BasicBlock *> DeadBlocks;
   OptimizationRemarkEmitter *ORE;
   ImplicitControlFlowTracking *ICF;
+  LoopInfo *LI;
 
   ValueTable VN;
 
   /// A mapping from value numbers to lists of Value*'s that
   /// have that value number.  Use findLeader to query it.
   struct LeaderTableEntry {
     Value *Val;
     const BasicBlock *BB;

llvm/trunk/lib/Analysis/CFG.cpp

#endif
   }
 }
 
 /// isCriticalEdge - Return true if the specified edge is a critical edge.
 /// Critical edges are edges from a block with multiple successors to a block
 /// 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...
   assert(I != E && "No preds, but we have an edge to the block?");
   const BasicBlock *FirstPred = *I;
   ++I;        // Skip one edge due to the incoming arc from TI.
   if (!AllowIdenticalEdges)
     return I != E;

llvm/trunk/lib/Transforms/Scalar/GVN.cpp

 #include "llvm/IR/Use.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #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"
 #include "llvm/Transforms/Utils/VNCoercion.h"
 #include <algorithm>
 #include <cassert>
 #include <cstdint>
 #include <utility>
PreservedAnalyses GVN::run(Function &F, FunctionAnalysisManager &AM) {
   auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);
   bool Changed = runImpl(F, AC, DT, TLI, AA, &MemDep, LI, &ORE);
   if (!Changed)
     return PreservedAnalyses::all();
   PreservedAnalyses PA;
   PA.preserve<DominatorTreeAnalysis>();
   PA.preserve<GlobalsAA>();
   PA.preserve<TargetLibraryAnalysis>();
+  if (LI)
+    PA.preserve<LoopAnalysis>();
   return PA;
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void GVN::dump(DenseMap<uint32_t, Value*>& d) const {
   errs() << "{\n";
   for (DenseMap<uint32_t, Value*>::iterator I = d.begin(),
        E = d.end(); I != E; ++I) {
bool GVN::runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
   AC = &RunAC;
   DT = &RunDT;
   VN.setDomTree(DT);
   TLI = &RunTLI;
   VN.setAliasAnalysis(&RunAA);
   MD = RunMD;
   ImplicitControlFlowTracking ImplicitCFT(DT);
   ICF = &ImplicitCFT;
+  this->LI = LI;
   VN.setMemDep(MD);
   ORE = RunORE;
   InvalidBlockRPONumbers = true;
 
   bool Changed = false;
   bool ShouldContinue = true;
 
   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
bool GVN::performPRE(Function &F) {
 
   return Changed;
 }
 
 /// Split the critical edge connecting the given two blocks, and return
 /// 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;
   return BB;
 }
 
 /// Split critical edges found during the previous
 /// iteration that may enable further optimization.
 bool GVN::splitCriticalEdges() {
   if (toSplit.empty())
     return false;
   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;
   return true;
 }
 
 /// Executes one iteration of GVN
 bool GVN::iterateOnFunction(Function &F) {
void GVN::addDeadBlock(BasicBlock *BB) {
   // For the dead blocks' live successors, update their phi nodes by replacing
   // the operands corresponding to dead blocks with UndefVal.
   for(SmallSetVector<BasicBlock *, 4>::iterator I = DF.begin(), E = DF.end();
         I != E; I++) {
     BasicBlock *B = *I;
     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);
       }
     }
   }
 }
 
return Impl.runImpl(
         LIWP ? &LIWP->getLoopInfo() : nullptr,
         &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE());
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<AssumptionCacheTracker>();
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<TargetLibraryInfoWrapperPass>();
+    AU.addRequired<LoopInfoWrapperPass>();
     if (!NoMemDepAnalysis)
       AU.addRequired<MemoryDependenceWrapperPass>();
     AU.addRequired<AAResultsWrapperPass>();
 
     AU.addPreserved<DominatorTreeWrapperPass>();
     AU.addPreserved<GlobalsAAWrapperPass>();
     AU.addPreserved<TargetLibraryInfoWrapperPass>();
+    AU.addPreserved<LoopInfoWrapperPass>();
+    AU.addPreservedID(LoopSimplifyID);
     AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
   }
 
 private:
   bool NoMemDepAnalysis;
   GVN Impl;
 };
 

llvm/trunk/test/Transforms/GVN/PRE/2011-06-01-NonLocalMemdepMiscompile.ll

bb10:
   br label %bb1
 
 bb15:
   %tmp16 = load i8*, i8** %tmp, align 8
   %tmp17 = load i8, i8* %tmp16, align 1
   %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
 }
 
 declare void @isalnum() nounwind inlinehint ssp

llvm/trunk/test/Transforms/GVN/preserve-analysis.ll

+; 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
+}