[LoopFuse] Ensure loops are in loop simplified form under new PM

[Narutoworld]

Summary

This patch tries to fix this issue.

Loop Fusion (Function Pass) requires loops in simplified form. With legacy-pm, loop-simplify pass is added as a dependency for loop-fusion. But the new pass manager does not always ensure this format. This patch tries to invoke simplifyLoop() on loops that are not in simplified form only for new PM.

[aeubanks]

test needs a little work, otherwise lg

llvm/lib/Transforms/Scalar/LoopFuse.cpp

557

I guess DependenceInfo doesn't need to be updated because it has no state

599

LI?

llvm/test/Transforms/LoopFusion/ensure_loop_simplify_form.ll

2

2

can you use llvm/utils/update_test_checks.py?

4

remove dso_local

9

we're trying to use undef less, perhaps make this a constant true/false or a function parameter

[bjope]

llvm/lib/Transforms/Scalar/LoopFuse.cpp

599

Is this safe. Afaik simplifyLoop might create new sub-loops. So I wonder if it wouldn't be safer to simplify loops before creating the LDT, to ensure the LDT include all simplified loops (and ensure that the LDT isn't having stale entries now when the loop has been transformed (not really sure if that can happen, but if doing all simplification first I wouldn't need to bother about knowing such things)).

Another thing is that this code is shared between the Legacy PM implementation and the new PM implementation. But since the legacy PM has required LoopSimplify before the pass we do not really need to bother about it here.

So I think it could be better to take care of enforcing loop simplify form in LoopFusePass::run instead. Before creating the LoopFuser.

602

I guess you only need to recalculate if simplifyLoop returned true this iteration of the loop over LDT. The Changed variable however is the accumulated state (so that one could be true even if no loops have been simplified, but rather we fused some loops in an earlier iteration).

[Narutoworld]

Update patch based on comments.

[Narutoworld]

llvm/lib/Transforms/Scalar/LoopFuse.cpp

557

@aeubanks Thanks for the comment.

I think the DependenceInfo does not need to be updated, since it operates on instructions which are not modified by loopSimplify pass.
I remember I found an example in the codebase.

599

@bjope Thanks for your comment.
I totally agree with your suggestion, just update the patch.

[aeubanks]

llvm/lib/Transforms/Scalar/LoopFuse.cpp

2099

I believe this might be wrong because a previously cached PDT isn't going to be invalidated in the analysis manager after the simplifyLoop above. either make simplifyLoop take a PDT and update it accordingly (that wouldn't be trivial), or recalculate the PDT like in the previous iteration of this patch

[Narutoworld]

Recalculating post dominator tree for the whole function if any loops are transformed by simplifyLoop().

[Narutoworld]

llvm/lib/Transforms/Scalar/LoopFuse.cpp

2099

Thanks @aeubanks
I fixes the patch based on your comment.

[aeubanks]

lgtm

I'd make the title something along the lines of [LoopFuse] Ensure loops are in loop simplified form under new PM

llvm/lib/Transforms/Scalar/LoopFuse.cpp

 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/CodeMoverUtils.h"
 #include "llvm/Transforms/Utils/LoopPeel.h"
+#include "llvm/Transforms/Utils/LoopSimplify.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-fusion"
 
 STATISTIC(FuseCounter, "Loops fused");
 STATISTIC(NumFusionCandidates, "Number of candidates for loop fusion");
 STATISTIC(InvalidPreheader, "Loop has invalid preheader");
private:
   DependenceInfo &DI;
   ScalarEvolution &SE;
   PostDominatorTree &PDT;
   OptimizationRemarkEmitter &ORE;
   AssumptionCache ∾
   const TargetTransformInfo &TTI;
 
 public:
   LoopFuser(LoopInfo &LI, DominatorTree &DT, DependenceInfo &DI,
             ScalarEvolution &SE, PostDominatorTree &PDT,
             OptimizationRemarkEmitter &ORE, const DataLayout &DL,
             AssumptionCache &AC, const TargetTransformInfo &TTI)
       : LDT(LI), DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy), LI(LI),
         DT(DT), DI(DI), SE(SE), PDT(PDT), ORE(ORE), AC(AC), TTI(TTI) {}
 
   /// This is the main entry point for loop fusion. It will traverse the
   /// specified function and collect candidate loops to fuse, starting at the
#ifndef NDEBUG
           LLVM_DEBUG({
             dbgs() << "  Visit loop set (#" << LV.size() << "):\n";
             printLoopVector(LV);
           });
         }
 #endif
 
         collectFusionCandidates(LV);
         Changed |= fuseCandidates();
       }
 
       // Finished analyzing candidates at this level.
       // Descend to the next level and clear all of the candidates currently
       // collected. Note that it will not be possible to fuse any of the
       // existing candidates with new candidates because the new candidates will
       // be at a different nest level and thus not be control flow equivalent
       // with all of the candidates collected so far.
       LLVM_DEBUG(dbgs() << "Descend one level!\n");
       LDT.descend();
       FusionCandidates.clear();
PreservedAnalyses LoopFusePass::run(Function &F, FunctionAnalysisManager &AM) {
   auto &DI = AM.getResult<DependenceAnalysis>(F);
   auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
   auto &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
   auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);
   auto &AC = AM.getResult<AssumptionAnalysis>(F);
   const TargetTransformInfo &TTI = AM.getResult<TargetIRAnalysis>(F);
   const DataLayout &DL = F.getParent()->getDataLayout();
 
+  // Ensure loops are in simplifed form which is a pre-requisite for loop fusion
+  // pass. Added only for new PM since the legacy PM has already added
+  // LoopSimplify pass as a dependency.
+  bool Changed = false;
+  for (auto &L : LI) {
+    if (!L->isLoopSimplifyForm())
+      Changed |= simplifyLoop(L, &DT, &LI, &SE, &AC, nullptr,
+                              false /* PreserveLCSSA */);
+  }
+  if (Changed)
+    PDT.recalculate(F);
+
   LoopFuser LF(LI, DT, DI, SE, PDT, ORE, DL, AC, TTI);
-  bool Changed = LF.fuseLoops(F);
+  Changed |= LF.fuseLoops(F);
   if (!Changed)
     return PreservedAnalyses::all();
 
   PreservedAnalyses PA;
   PA.preserve<DominatorTreeAnalysis>();
   PA.preserve<PostDominatorTreeAnalysis>();
   PA.preserve<ScalarEvolutionAnalysis>();
   PA.preserve<LoopAnalysis>();

llvm/test/Transforms/LoopFusion/ensure_loop_simplify_form.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -passes=loop-fusion -S | FileCheck %s
+
+define void @v_5_0(i32* %dummy) {
+; CHECK-LABEL: @v_5_0(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.cond.cleanup:
+; CHECK-NEXT:    br i1 true, label [[FOR_BODY6_PREHEADER:%.*]], label [[FOR_COND_CLEANUP5:%.*]]
+; CHECK:       for.body6.preheader:
+; CHECK-NEXT:    br label [[FOR_BODY6:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    br i1 false, label [[FOR_COND_CLEANUP:%.*]], label [[FOR_BODY]]
+; CHECK:       for.cond.cleanup5:
+; CHECK-NEXT:    ret void
+; CHECK:       for.body6:
+; CHECK-NEXT:    [[V_LOOP_2_0_V_LOOP_2_0_V_LOOP_2_0_18:%.*]] = load volatile i32, i32* [[DUMMY:%.*]], align 1
+; CHECK-NEXT:    br label [[FOR_BODY6]]
+;
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body
+  br i1 true, label %for.body6, label %for.cond.cleanup5
+
+for.body:                                         ; preds = %for.body, %entry
+  br i1 false, label %for.cond.cleanup, label %for.body
+
+for.cond.cleanup5:                                ; preds = %for.cond.cleanup
+  ret void
+
+for.body6:                                        ; preds = %for.body6, %for.cond.cleanup
+  %v_loop_2.0.v_loop_2.0.v_loop_2.0.18 = load volatile i32, i32* %dummy, align 1
+  br label %for.body6
+}