[GVN LoadPRE] Add an option to disable splitting backedge

[skatkov]

Summary

GVN Load PRE can split the backedge causing breaking the loop structure where the latch
contains the conditional branch with for example induction variable.

Different optimizations expect this form of the loop, so it is better to preserve it for some time.
This CL adds an option to control an ability to split backedge.

Default value is true so technically it is NFC and current behavior is not changed.

[fhahn]

This seems reasonable. Do you plan to use this option in the default pipeline/do you think there are any benefits for the regular pipeline?

llvm/test/Transforms/GVN/PRE/load-pre-split-backedge.ll

6

nit: do we need the triple?

[skatkov]

handled nit

[skatkov]

In D89854#2344384, @fhahn wrote:

This seems reasonable. Do you plan to use this option in the default pipeline/do you think there are any benefits for the regular pipeline?

Hi Florian, to be honest I have no idea of the impact on default pipeline. I know that GVN Load PRE negatively impacts peeling, loop predication, so the passes expecting that latch has a conditional branch.
So I do not plan to update the default pipeline but if there is a volunteer to play with default pipeline, all tools will be there.

[mkazantsev]

Fine by me, but please wait some time in case anyone has cons.

[skatkov]

In D89854#2349533, @mkazantsev wrote:

Fine by me, but please wait some time in case anyone has cons.

No new cons for 4 days, so consider your comment as an approve.
Anyway we can fix any cons as follow-ups.

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

 ///      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> AllowLoadPRESplitBackedge = 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 PRE of loads in GVN.
+  GVNOptions &setLoadPRESplitBackedge(bool LoadPRESplitBackedge) {
+    AllowLoadPRESplitBackedge = LoadPRESplitBackedge;
+    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; }
   AAResults *getAliasAnalysis() const { return VN.getAliasAnalysis(); }
   MemoryDependenceResults &getMemDep() const { return *MD; }
 
   bool isPREEnabled() const;
   bool isLoadPREEnabled() const;
   bool isLoadInLoopPREEnabled() const;
+  bool isLoadPRESplitBackedgeEnabled() 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/Passes/PassBuilder.cpp

while (!Params.empty()) {
     StringRef ParamName;
     std::tie(ParamName, Params) = Params.split(';');
 
     bool Enable = !ParamName.consume_front("no-");
     if (ParamName == "pre") {
       Result.setPRE(Enable);
     } else if (ParamName == "load-pre") {
       Result.setLoadPRE(Enable);
+    } else if (ParamName == "split-backedge-load-pre") {
+      Result.setLoadPRESplitBackedge(Enable);
     } else if (ParamName == "memdep") {
       Result.setMemDep(Enable);
     } else {
       return make_error<StringError>(
           formatv("invalid GVN pass parameter '{0}' ", ParamName).str(),
           inconvertibleErrorCode());
     }
   }

llvm/lib/Transforms/Scalar/GVN.cpp

 STATISTIC(MaxBBSpeculationCutoffReachedTimes,
           "Number of times we we reached gvn-max-block-speculations cut-off "
           "preventing further exploration");
 
 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>
+GVNEnableSplitBackedgeInLoadPRE("enable-split-backedge-in-load-pre",
+                                cl::init(true));
 static cl::opt<bool> GVNEnableMemDep("enable-gvn-memdep", cl::init(true));
 
 static cl::opt<uint32_t> MaxNumDeps(
     "gvn-max-num-deps", cl::Hidden, cl::init(100), cl::ZeroOrMore,
     cl::desc("Max number of dependences to attempt Load PRE (default = 100)"));
 
 // This is based on IsValueFullyAvailableInBlockNumSpeculationsMax stat.
 static cl::opt<uint32_t> MaxBBSpeculations(

 bool GVN::isLoadPREEnabled() const {
   return Options.AllowLoadPRE.getValueOr(GVNEnableLoadPRE);
 }
 
 bool GVN::isLoadInLoopPREEnabled() const {
   return Options.AllowLoadInLoopPRE.getValueOr(GVNEnableLoadInLoopPRE);
 }
 
+bool GVN::isLoadPRESplitBackedgeEnabled() const {
+  return Options.AllowLoadPRESplitBackedge.getValueOr(
+      GVNEnableSplitBackedgeInLoadPRE);
+}
+
 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 (Pred->getTerminator()->getNumSuccessors() != 1) {
 
       if (LoadBB->isEHPad()) {
         LLVM_DEBUG(
             dbgs() << "COULD NOT PRE LOAD BECAUSE OF AN EH PAD CRITICAL EDGE '"
                    << Pred->getName() << "': " << *LI << '\n');
         return false;
       }
 
+      // Do not split backedge as it will break the canonical loop form.
+      if (!isLoadPRESplitBackedgeEnabled())
+        if (DT->dominates(LoadBB, Pred)) {
+          LLVM_DEBUG(
+              dbgs()
+              << "COULD NOT PRE LOAD BECAUSE OF A BACKEDGE CRITICAL EDGE '"
+              << Pred->getName() << "': " << *LI << '\n');
+          return false;
+        }
+
       CriticalEdgePred.push_back(Pred);
     } else {
       // Only add the predecessors that will not be split for now.
       PredLoads[Pred] = nullptr;
     }
   }
 
   // Decide whether PRE is profitable for this load.

llvm/test/Transforms/GVN/PRE/load-pre-split-backedge.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -basic-aa -gvn -enable-split-backedge-in-load-pre=true < %s | FileCheck %s --check-prefix=ON
+; RUN: opt -S -basic-aa -gvn -enable-split-backedge-in-load-pre=false < %s | FileCheck %s --check-prefix=OFF
+
+target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128-n8:16:32"
+target triple = "i386-apple-darwin11.0.0"
+
+define i32 @test(i1 %b, i1 %c, i32* noalias %p, i32* noalias %q) {
+; ON-LABEL: @test(
+; ON-NEXT:  entry:
+; ON-NEXT:    [[Y1:%.*]] = load i32, i32* [[P:%.*]], align 4
+; ON-NEXT:    call void @use(i32 [[Y1]])
+; ON-NEXT:    br label [[HEADER:%.*]]
+; ON:       header:
+; ON-NEXT:    [[Y:%.*]] = phi i32 [ [[Y_PRE:%.*]], [[SKIP_HEADER_CRIT_EDGE:%.*]] ], [ [[Y]], [[HEADER]] ], [ [[Y1]], [[ENTRY:%.*]] ]
+; ON-NEXT:    call void @use(i32 [[Y]])
+; ON-NEXT:    br i1 [[B:%.*]], label [[SKIP:%.*]], label [[HEADER]]
+; ON:       skip:
+; ON-NEXT:    call void @clobber(i32* [[P]], i32* [[Q:%.*]])
+; ON-NEXT:    br i1 [[C:%.*]], label [[SKIP_HEADER_CRIT_EDGE]], label [[EXIT:%.*]]
+; ON:       skip.header_crit_edge:
+; ON-NEXT:    [[Y_PRE]] = load i32, i32* [[P]], align 4
+; ON-NEXT:    br label [[HEADER]]
+; ON:       exit:
+; ON-NEXT:    ret i32 [[Y]]
+;
+; OFF-LABEL: @test(
+; OFF-NEXT:  entry:
+; OFF-NEXT:    [[Y1:%.*]] = load i32, i32* [[P:%.*]], align 4
+; OFF-NEXT:    call void @use(i32 [[Y1]])
+; OFF-NEXT:    br label [[HEADER:%.*]]
+; OFF:       header:
+; OFF-NEXT:    [[Y:%.*]] = load i32, i32* [[P]], align 4
+; OFF-NEXT:    call void @use(i32 [[Y]])
+; OFF-NEXT:    br i1 [[B:%.*]], label [[SKIP:%.*]], label [[HEADER]]
+; OFF:       skip:
+; OFF-NEXT:    call void @clobber(i32* [[P]], i32* [[Q:%.*]])
+; OFF-NEXT:    br i1 [[C:%.*]], label [[HEADER]], label [[EXIT:%.*]]
+; OFF:       exit:
+; OFF-NEXT:    ret i32 [[Y]]
+;
+entry:
+  %y1 = load i32, i32* %p
+  call void @use(i32 %y1)
+  br label %header
+header:
+  %y = load i32, i32* %p
+  call void @use(i32 %y)
+  br i1 %b, label %skip, label %header
+skip:
+  call void @clobber(i32* %p, i32* %q)
+  br i1 %c, label %header, label %exit
+exit:
+  ret i32 %y
+}
+
+declare void @use(i32) readonly
+declare void @clobber(i32* %p, i32* %q)