[GVN] Add GVNOption to control load-pre more fine-grained.

[hgreving]

Summary

Adds the global (cl::opt) GVNOption enable-load-in-loop-pre in order
to control whether the optimization will be performed if the load
is part of a loop.

Adds the lit test Transforms/GVN/PRE/pre-load-in-loop.ll.

[hgreving]

Hello, this switch intends to help our backend to software pipeline single basic block loops. The suppressed GVN opt is creating control flow in loops which we like to avoid. Thanks in advance for looking at the patch.

[asbirlea]

lgtm.

[fhahn]

llvm/lib/Transforms/Scalar/GVN.cpp

1406

nit: drop unnecessary this-> ?

[hgreving]

llvm/lib/Transforms/Scalar/GVN.cpp

1406

This is testing the LoopInfo, not the LoadInst. Having said that, I considered changing the this->LI name into sth else since LI shadows LI in GVN::runImpl as well, but thought this is an unrelated change. Happy to submit this as well.

[fhahn]

llvm/lib/Transforms/Scalar/GVN.cpp

1406

Ah right, I didn't look carefully enough. It seems a very unfortunate name clash, but I guess this->LI is fine.

[asbirlea]

llvm/lib/Transforms/Scalar/GVN.cpp

1406

I thought to suggest renaming of either the LoopInfo or LoadInst instances in a separate cleanup patch, but thought that's more than you intended to do.

Happy to look over the patch, if you do send it out. Sadly, LoopInfo has only a couple uses here, but it's traditionally named LI (I found a single declaration called LF), and LoadInst has a very large number of uses here, and can be named L, I, LI, LoadI etc.
So, *shrug* use your best judgment if either of renamings is worth doing.

[skatkov]

May I ask you to add a support for new pass manager to specify new introduced option in command line?

For details, see PassRgistry.def and PassBuilder.cpp:parseGVNOptions.

[fedor.sergeev]

llvm/test/Transforms/GVN/PRE/pre-load-in-loop.ll

2

It makes sense to add both positive - checking that load-pre is performed when enabled, and negative - checking that load-pre does not happen when disabled
(say, to catch a case when load-pre is not performed due to some bug or change in other defaults).

[fedor.sergeev]

In D73804#1852503, @hgreving wrote:

Hello, this switch intends to help our backend to software pipeline single basic block loops. The suppressed GVN opt is creating control flow in loops which we like to avoid. Thanks in advance for looking at the patch.

Curiously, just recently we had a similar case in our downstream pipeline, though we had a GVN splitting loop backedge and leading to a loss of a loop form (by making a non-exiting latch).
Solved by disabling load-pre in a separate responsible GVN instance, though this control looks more appropriate.

I wonder whether this change needs to be extended into "not doing questionable control flow modifications when loop-pre'ing in loops" and enabled unconditionally?
It will require properly defining this "questionable" part.

[hgreving]

llvm/test/Transforms/GVN/PRE/pre-load-in-loop.ll

2

The positive case is checked in load-pre.ll. Does this suffice? WDYT?

[fedor.sergeev]

llvm/test/Transforms/GVN/PRE/pre-load-in-loop.ll

2

Shouldnt then -enable-load-in-loop-pre=true be added explicitly to load-pre.ll, to avoid its behavior being dependant on default setting?

38

Correct the comment to match behavior.

[hgreving]

llvm/test/Transforms/GVN/PRE/pre-load-in-loop.ll

2

I think it _should_ depend on the default setting, as this should be considered a switch that explicitly diverts from the default IMO. I _can_ add this to loop-pre.ll, do you really want this? Either way ok with me.

[hgreving]

llvm/test/Transforms/GVN/PRE/pre-load-in-loop.ll:
s/Should only be one load in the loop./Both loads should remain in the loop./

[hgreving]

llvm/test/Transforms/GVN/PRE/pre-load-in-loop.ll

38

Done, thanks!

[fedor.sergeev]

llvm/test/Transforms/GVN/PRE/pre-load-in-loop.ll

2

The point is that defaults do change.
And I do see some variation of load-pre-in-loop restriction being quite useful by default.
(see my earlier comment on possibly enabling this unconditionally).

So it is quite normal to have a test that explicitly tests both true and false, just to avoid a hassle of updating tests upon a toggle of default value.

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

 ///      true - enabling the transformation.
 ///      false - disabling the transformation.
 ///      None - relying on a global default.
 /// Intended use is to create a default object, modify parameters with
 /// additional setters and then pass it to GVN.
 struct GVNOptions {
   Optional<bool> AllowPRE = None;
   Optional<bool> AllowLoadPRE = None;
+  Optional<bool> AllowLoadInLoopPRE = None;
   Optional<bool> AllowMemDep = None;
 
   GVNOptions() = default;
 
   /// Enables or disables PRE in GVN.
   GVNOptions &setPRE(bool PRE) {
     AllowPRE = PRE;
     return *this;
   }
 
   /// Enables or disables PRE of loads in GVN.
   GVNOptions &setLoadPRE(bool LoadPRE) {
     AllowLoadPRE = LoadPRE;
     return *this;
   }
 
+  GVNOptions &setLoadInLoopPRE(bool LoadInLoopPRE) {
+    AllowLoadInLoopPRE = LoadInLoopPRE;
+    return *this;
+  }
+
   /// Enables or disables use of MemDepAnalysis.
   GVNOptions &setMemDep(bool MemDep) {
     AllowMemDep = MemDep;
     return *this;
   }
 };
 
 /// The core GVN pass object.
public:
   }
 
   DominatorTree &getDominatorTree() const { return *DT; }
   AliasAnalysis *getAliasAnalysis() const { return VN.getAliasAnalysis(); }
   MemoryDependenceResults &getMemDep() const { return *MD; }
 
   bool isPREEnabled() const;
   bool isLoadPREEnabled() const;
+  bool isLoadInLoopPREEnabled() const;
   bool isMemDepEnabled() const;
 
   /// This class holds the mapping between values and value numbers.  It is used
   /// as an efficient mechanism to determine the expression-wise equivalence of
   /// two values.
   class ValueTable {
     DenseMap<Value *, uint32_t> valueNumbering;
     DenseMap<Expression, uint32_t> expressionNumbering;

llvm/lib/Transforms/Scalar/GVN.cpp

 STATISTIC(NumGVNPRE,    "Number of instructions PRE'd");
 STATISTIC(NumGVNBlocks, "Number of blocks merged");
 STATISTIC(NumGVNSimpl,  "Number of instructions simplified");
 STATISTIC(NumGVNEqProp, "Number of equalities propagated");
 STATISTIC(NumPRELoad,   "Number of loads PRE'd");
 
 static cl::opt<bool> GVNEnablePRE("enable-pre", cl::init(true), cl::Hidden);
 static cl::opt<bool> GVNEnableLoadPRE("enable-load-pre", cl::init(true));
+static cl::opt<bool> GVNEnableLoadInLoopPRE("enable-load-in-loop-pre",
+                                            cl::init(true));
 static cl::opt<bool> GVNEnableMemDep("enable-gvn-memdep", cl::init(true));
 
 // Maximum allowed recursion depth.
 static cl::opt<uint32_t>
 MaxRecurseDepth("gvn-max-recurse-depth", cl::Hidden, cl::init(1000), cl::ZeroOrMore,
                 cl::desc("Max recurse depth in GVN (default = 1000)"));
 
 static cl::opt<uint32_t> MaxNumDeps(

 
 bool GVN::isPREEnabled() const {
   return Options.AllowPRE.getValueOr(GVNEnablePRE);
 }
 
 bool GVN::isLoadPREEnabled() const {
   return Options.AllowLoadPRE.getValueOr(GVNEnableLoadPRE);
 }
+
+bool GVN::isLoadInLoopPREEnabled() const {
+  return Options.AllowLoadInLoopPRE.getValueOr(GVNEnableLoadInLoopPRE);
+}
+
 bool GVN::isMemDepEnabled() const {
   return Options.AllowMemDep.getValueOr(GVNEnableMemDep);
 }
 
 PreservedAnalyses GVN::run(Function &F, FunctionAnalysisManager &AM) {
   // FIXME: The order of evaluation of these 'getResult' calls is very
   // significant! Re-ordering these variables will cause GVN when run alone to
   // be less effective! We should fix memdep and basic-aa to not exhibit this
if (UnavailableBlocks.empty()) {
     ++NumGVNLoad;
     reportLoadElim(LI, V, ORE);
     return true;
   }
 
   // Step 4: Eliminate partial redundancy.
   if (!isPREEnabled() || !isLoadPREEnabled())
     return false;
+  if (!isLoadInLoopPREEnabled() && this->LI &&
+      this->LI->getLoopFor(LI->getParent()))
+    return false;
 
   return PerformLoadPRE(LI, ValuesPerBlock, UnavailableBlocks);
 }
 
 static bool impliesEquivalanceIfTrue(CmpInst* Cmp) {
   if (Cmp->getPredicate() == CmpInst::Predicate::ICMP_EQ)
     return true;
 

llvm/test/Transforms/GVN/PRE/pre-load-in-loop.ll

+; RUN: opt < %s -basicaa -gvn -enable-load-in-loop-pre=false -S | FileCheck %s
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
+
+;void test1(int N, double *G) {
+;  int j;
+;  for (j = 0; j < N - 1; j++)
+;    G[j] = G[j] + G[j+1];
+;}
+
+define void @test1(i32 %N, double* nocapture %G) nounwind ssp {
+; CHECK-LABEL: @test1(
+entry:
+  %0 = add i32 %N, -1
+  %1 = icmp sgt i32 %0, 0
+  br i1 %1, label %bb.nph, label %return
+
+bb.nph:
+  %tmp = zext i32 %0 to i64
+  br label %bb
+
+; CHECK: bb.nph:
+; CHECK-NOT: load double, double*
+; CHECK: br label %bb
+
+bb:
+  %indvar = phi i64 [ 0, %bb.nph ], [ %tmp6, %bb ]
+  %tmp6 = add i64 %indvar, 1
+  %scevgep = getelementptr double, double* %G, i64 %tmp6
+  %scevgep7 = getelementptr double, double* %G, i64 %indvar
+  %2 = load double, double* %scevgep7, align 8
+  %3 = load double, double* %scevgep, align 8
+  %4 = fadd double %2, %3
+  store double %4, double* %scevgep7, align 8
+  %exitcond = icmp eq i64 %tmp6, %tmp
+  br i1 %exitcond, label %return, label %bb
+
+; Both loads should remain in the loop.
+; CHECK: bb:
+; CHECK: load double, double*
+; CHECK: load double, double*
+; CHECK: br i1 %exitcond
+
+return:
+  ret void
+}