[LICM] Support sinking in LNICM

[uint256_t]

Summary

Currently, LNICM pass does not support sinking instructions out of loop nest.
This patch enables LNICM to sink down as many instructions to the exit block of outermost loop as possible.

[xbolva00]

llvm/test/Transforms/LICM/lnicm-sink.ll

12

j not used? It would be better to use more “realistic” example.

[uint256_t]

llvm/test/Transforms/LICM/lnicm-sink.ll

12

I don't think j need to be used. This test shows how LNICM handles a loop nest when it does sinking. If we use j here, an instruction using it would be neither hoisted or sunk, so I think it is redundant.

[uint256_t]

Updated test to make it more readable

[uint256_t]

Fixed bug

[uint256_t]

Fixed test

[Whitney]

llvm/include/llvm/Transforms/Utils/LoopUtils.h

159

Please add description for this function.

llvm/test/Transforms/LICM/lnicm-sink.ll

16

Why y[i] = s; is needed for this test case?

[uint256_t]

llvm/include/llvm/Transforms/Utils/LoopUtils.h

159

Ok, I'll add a brief description.

llvm/test/Transforms/LICM/lnicm-sink.ll

16

It is to show that LNICM maintains perfect loop nest.
LICM sinks s = abs(i); to right before y[i] = s;, whereas LNICM doesn't do so.

[Whitney]

llvm/test/Transforms/LICM/lnicm-sink.ll

16

Why wouldn't LICM sink s = abs(i); without y[i] = s;?

[uint256_t]

llvm/test/Transforms/LICM/lnicm-sink.ll

16

LICM would hoist (not sink) s = abs(i); out of loop-j.

[Whitney]

llvm/test/Transforms/LICM/lnicm-sink.ll

16

how about

;   for (int i = 0; i < 10; i++) {
;     for (int j = 0; j < 10; j++) {
;       t = sin(x);
;       s = abs(i);
;     }
;   }
;  return t + s;

?

[uint256_t]

llvm/test/Transforms/LICM/lnicm-sink.ll

16

Oh, it is way better. I'll edit this test case. Thank you.

[uint256_t]

llvm/test/Transforms/LICM/lnicm-sink.ll

16

how about

;   for (int i = 0; i < 10; i++) {
;     for (int j = 0; j < 10; j++) {
;       t = sin(x);
;       s = abs(i);
;     }
;   }
;  return t + s;

?

I ran the test case you suggested above, but LICM didn't do what we want...
LICM transformed it into something like this:

;  int i, j;
;  for (i = 0; i < 10; i++) {
;    for (j = 0; j < 10; j++) {
;    }
;  }
;  t = sin(x);
;  s = abs(i);
;  return t + s;

I should make another better test case.

[Whitney]

llvm/test/Transforms/LICM/lnicm-sink.ll

16

I now see the point of y[i] = s;, let's see if you can make a better test case, if not, this is ok with me.

[uint256_t]

Added doc comment

[bmahjour]

llvm/include/llvm/Transforms/Utils/LoopUtils.h

157

Please name the parameters of this function and add a comment about what each parameter means. Someone reading this declaration and its comments will see two Loop * being passed and cannot figure out what they are without going through its implementation.

[uint256_t]

llvm/include/llvm/Transforms/Utils/LoopUtils.h

157

Okay, I'll name the parameter Loop * = nullptr and add a comment to explain what two Loop * are. I don't think I need to name all parameters.

[uint256_t]

Added doc comment

[uabelho]

Hi,

The following starts failing with this patch:

opt -passes='loop-mssa(lnicm)' -o /dev/null lnicm-crash.ll

I get

While deleting: i40 %
Use still stuck around after Def is destroyed:  %v_299.017 = phi i40 [ <badref>, %for.body1143 ]
opt: ../lib/IR/Value.cpp:103: llvm::Value::~Value(): Assertion `materialized_use_empty() && "Uses remain when a value is destroyed!"' failed.

lnicm-crash.ll752 BDownload

[uint256_t]

Thank you for the report. I'll look into it.

[fhahn]

It looks like @uabelho may found another crash in sinkRegionForLoopNest https://github.com/llvm/llvm-project/issues/52688. Please take a look.

[uint256_t]

Thank you for your report. I'm investigating the problem and making a patch for it.

llvm/include/llvm/Transforms/Utils/LoopUtils.h

 /// Walk the specified region of the CFG (defined by all blocks
 /// dominated by the specified block, and that are in the current loop) in
 /// reverse depth first order w.r.t the DominatorTree. This allows us to visit
 /// uses before definitions, allowing us to sink a loop body in one pass without
 /// iteration. Takes DomTreeNode, AAResults, LoopInfo, DominatorTree,
 /// BlockFrequencyInfo, TargetLibraryInfo, Loop, AliasSet information for all
 /// instructions of the loop and loop safety information as
 /// arguments. Diagnostics is emitted via \p ORE. It returns changed status.
+/// \p CurLoop is a loop to do sinking on. \p OutermostLoop is used only when
+/// this function is called by \p sinkRegionForLoopNest.
 bool sinkRegion(DomTreeNode *, AAResults *, LoopInfo *, DominatorTree *,
                 BlockFrequencyInfo *, TargetLibraryInfo *,
-                TargetTransformInfo *, Loop *, AliasSetTracker *,
+                TargetTransformInfo *, Loop *CurLoop, AliasSetTracker *,
                 MemorySSAUpdater *, ICFLoopSafetyInfo *,
-                SinkAndHoistLICMFlags &, OptimizationRemarkEmitter *);
+                SinkAndHoistLICMFlags &, OptimizationRemarkEmitter *,
+                Loop *OutermostLoop = nullptr);
+
+/// Call sinkRegion on loops contained within the specified loop
+/// in order from innermost to outermost.
+bool sinkRegionForLoopNest(DomTreeNode *, AAResults *, LoopInfo *,
+                           DominatorTree *, BlockFrequencyInfo *,
+                           TargetLibraryInfo *, TargetTransformInfo *, Loop *,
+                           AliasSetTracker *, MemorySSAUpdater *,
+                           ICFLoopSafetyInfo *, SinkAndHoistLICMFlags &,
+                           OptimizationRemarkEmitter *);
 
 /// Walk the specified region of the CFG (defined by all blocks
 /// dominated by the specified block, and that are in the current loop) in depth
 /// first order w.r.t the DominatorTree.  This allows us to visit definitions
 /// before uses, allowing us to hoist a loop body in one pass without iteration.
 /// Takes DomTreeNode, AAResults, LoopInfo, DominatorTree,
 /// BlockFrequencyInfo, TargetLibraryInfo, Loop, AliasSet information for all
 /// instructions of the loop and loop safety information as arguments.

llvm/lib/Transforms/Scalar/LICM.cpp

cl::opt<unsigned> llvm::SetLicmMssaNoAccForPromotionCap(
     cl::desc("[LICM & MemorySSA] When MSSA in LICM is disabled, this has no "
              "effect. When MSSA in LICM is enabled, then this is the maximum "
              "number of accesses allowed to be present in a loop in order to "
              "enable memory promotion."));
 
 static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI);
 static bool isNotUsedOrFreeInLoop(const Instruction &I, const Loop *CurLoop,
                                   const LoopSafetyInfo *SafetyInfo,
-                                  TargetTransformInfo *TTI, bool &FreeInLoop);
+                                  TargetTransformInfo *TTI, bool &FreeInLoop,
+                                  bool LoopNestMode);
 static void hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
                   BasicBlock *Dest, ICFLoopSafetyInfo *SafetyInfo,
                   MemorySSAUpdater *MSSAU, ScalarEvolution *SE,
                   OptimizationRemarkEmitter *ORE);
 static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT,
                  BlockFrequencyInfo *BFI, const Loop *CurLoop,
                  ICFLoopSafetyInfo *SafetyInfo, MemorySSAUpdater *MSSAU,
                  OptimizationRemarkEmitter *ORE);
bool LoopInvariantCodeMotion::runOnLoop(
   // the subloops).
   //
   // Traverse the body of the loop in depth first order on the dominator tree so
   // that we are guaranteed to see definitions before we see uses.  This allows
   // us to sink instructions in one pass, without iteration.  After sinking
   // instructions, we perform another pass to hoist them out of the loop.
   if (L->hasDedicatedExits())
     Changed |=
-        sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, BFI, TLI, TTI, L,
-                   CurAST.get(), MSSAU.get(), &SafetyInfo, *Flags.get(), ORE);
+        LoopNestMode
+            ? sinkRegionForLoopNest(DT->getNode(L->getHeader()), AA, LI, DT,
+                                    BFI, TLI, TTI, L, CurAST.get(), MSSAU.get(),
+                                    &SafetyInfo, *Flags.get(), ORE)
+            : sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, BFI, TLI, TTI,
+                         L, CurAST.get(), MSSAU.get(), &SafetyInfo,
+                         *Flags.get(), ORE);
   Flags->setIsSink(false);
   if (Preheader)
     Changed |= hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, BFI, TLI, L,
                            CurAST.get(), MSSAU.get(), SE, &SafetyInfo,
                            *Flags.get(), ORE, LoopNestMode);
 
   // Now that all loop invariants have been removed from the loop, promote any
   // memory references to scalars that we can.

 /// definitions, allowing us to sink a loop body in one pass without iteration.
 ///
 bool llvm::sinkRegion(DomTreeNode *N, AAResults *AA, LoopInfo *LI,
                       DominatorTree *DT, BlockFrequencyInfo *BFI,
                       TargetLibraryInfo *TLI, TargetTransformInfo *TTI,
                       Loop *CurLoop, AliasSetTracker *CurAST,
                       MemorySSAUpdater *MSSAU, ICFLoopSafetyInfo *SafetyInfo,
                       SinkAndHoistLICMFlags &Flags,
-                      OptimizationRemarkEmitter *ORE) {
+                      OptimizationRemarkEmitter *ORE, Loop *OutermostLoop) {
 
   // Verify inputs.
   assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr &&
          CurLoop != nullptr && SafetyInfo != nullptr &&
          "Unexpected input to sinkRegion.");
   assert(((CurAST != nullptr) ^ (MSSAU != nullptr)) &&
          "Either AliasSetTracker or MemorySSA should be initialized.");
 
for (BasicBlock::iterator II = BB->end(); II != BB->begin();) {
       }
 
       // Check to see if we can sink this instruction to the exit blocks
       // of the loop.  We can do this if the all users of the instruction are
       // outside of the loop.  In this case, it doesn't even matter if the
       // operands of the instruction are loop invariant.
       //
       bool FreeInLoop = false;
+      bool LoopNestMode = OutermostLoop != nullptr;
       if (!I.mayHaveSideEffects() &&
-          isNotUsedOrFreeInLoop(I, CurLoop, SafetyInfo, TTI, FreeInLoop) &&
+          isNotUsedOrFreeInLoop(I, LoopNestMode ? OutermostLoop : CurLoop,
+                                SafetyInfo, TTI, FreeInLoop, LoopNestMode) &&
           canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, MSSAU, true, &Flags,
                              ORE)) {
         if (sink(I, LI, DT, BFI, CurLoop, SafetyInfo, MSSAU, ORE)) {
           if (!FreeInLoop) {
             ++II;
             salvageDebugInfo(I);
             eraseInstruction(I, *SafetyInfo, CurAST, MSSAU);
           }
           Changed = true;
         }
       }
     }
   }
   if (MSSAU && VerifyMemorySSA)
     MSSAU->getMemorySSA()->verifyMemorySSA();
   return Changed;
 }
 
+bool llvm::sinkRegionForLoopNest(
+    DomTreeNode *N, AAResults *AA, LoopInfo *LI, DominatorTree *DT,
+    BlockFrequencyInfo *BFI, TargetLibraryInfo *TLI, TargetTransformInfo *TTI,
+    Loop *CurLoop, AliasSetTracker *CurAST, MemorySSAUpdater *MSSAU,
+    ICFLoopSafetyInfo *SafetyInfo, SinkAndHoistLICMFlags &Flags,
+    OptimizationRemarkEmitter *ORE) {
+
+  bool Changed = false;
+  SmallPriorityWorklist<Loop *, 4> Worklist;
+  Worklist.insert(CurLoop);
+  appendLoopsToWorklist(*CurLoop, Worklist);
+  while (!Worklist.empty()) {
+    Loop *L = Worklist.pop_back_val();
+    Changed |=
+        sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, BFI, TLI, TTI, L,
+                   CurAST, MSSAU, SafetyInfo, Flags, ORE, CurLoop);
+  }
+  return Changed;
+}
+
 namespace {
 // This is a helper class for hoistRegion to make it able to hoist control flow
 // in order to be able to hoist phis. The way this works is that we initially
 // start hoisting to the loop preheader, and when we see a loop invariant branch
 // we make note of this. When we then come to hoist an instruction that's
 // conditional on such a branch we duplicate the branch and the relevant control
 // flow, then hoist the instruction into the block corresponding to its original
 // block in the duplicated control flow.

 /// Return true if the only users of this instruction are outside of
 /// the loop. If this is true, we can sink the instruction to the exit
 /// blocks of the loop.
 ///
 /// We also return true if the instruction could be folded away in lowering.
 /// (e.g.,  a GEP can be folded into a load as an addressing mode in the loop).
 static bool isNotUsedOrFreeInLoop(const Instruction &I, const Loop *CurLoop,
                                   const LoopSafetyInfo *SafetyInfo,
-                                  TargetTransformInfo *TTI, bool &FreeInLoop) {
+                                  TargetTransformInfo *TTI, bool &FreeInLoop,
+                                  bool LoopNestMode) {
   const auto &BlockColors = SafetyInfo->getBlockColors();
   bool IsFree = isFreeInLoop(I, CurLoop, TTI);
   for (const User *U : I.users()) {
     const Instruction *UI = cast<Instruction>(U);
     if (const PHINode *PN = dyn_cast<PHINode>(UI)) {
       const BasicBlock *BB = PN->getParent();
       // We cannot sink uses in catchswitches.
       if (isa<CatchSwitchInst>(BB->getTerminator()))
         return false;
 
       // We need to sink a callsite to a unique funclet.  Avoid sinking if the
       // phi use is too muddled.
       if (isa<CallInst>(I))
         if (!BlockColors.empty() &&
             BlockColors.find(const_cast<BasicBlock *>(BB))->second.size() != 1)
           return false;
+
+      if (LoopNestMode) {
+        while (isa<PHINode>(UI) && UI->hasOneUser() &&
+               UI->getNumOperands() == 1) {
+          if (!CurLoop->contains(UI))
+            break;
+          UI = cast<Instruction>(U->user_back());
+        }
+      }
     }
 
     if (CurLoop->contains(UI)) {
       if (IsFree) {
         FreeInLoop = true;
         continue;
       }
       return false;

llvm/test/Transforms/LICM/lnicm-sink.ll

+; RUN: opt -passes='loop(licm)' -S %s | FileCheck %s --check-prefixes CHECK,LICM
+; RUN: opt -passes='loop(lnicm)' -S %s | FileCheck %s --check-prefixes CHECK,LNICM
+
+; This test represents the following function:
+;
+; double sin(double);
+; int abs(int);
+; double test(double x, int y[10]) {
+;   double t = 0; int s = 0;
+;   for (int i = 0; i < 10; i++) {
+;     for (int j = 0; j < 10; j++) {
+;       t = sin(x);
+;       s = abs(i);
+;     }
+;     y[i] = s;
+;   }
+;   return t;
+; }
+;
+; We only want to sink the call of sin out of the loop nest.
+; LICM also sinks the call of abs out of j-loop, but LNICM doesn't do so
+; to try to make a perfect loop nest. (though y[i] = s; still prevents the 
+; loop nest from being a perfect loop nest in this test case)
+
+define dso_local double @test(double %x, i32* noalias %y) {
+entry:
+  br label %for.body
+
+for.body:
+  %i.02 = phi i32 [ 0, %entry ], [ %inc6, %for.end ]
+  br label %for.body3
+
+; CHECK: for.body3:
+; LNICM: call i32 @abs(i32 %i.02)
+; LICM-NOT: call i32 @abs(i32 %i.02)
+for.body3:
+  %j.01 = phi i32 [ 0, %for.body ], [ %inc, %for.body3 ]
+  %call = call double @sin(double %x)
+  %call4 = call i32 @abs(i32 %i.02)
+  %inc = add nsw i32 %j.01, 1
+  %cmp2 = icmp slt i32 %inc, 10
+  br i1 %cmp2, label %for.body3, label %for.end
+
+; CHECK: for.end:
+; LICM: call i32 @abs(i32 %i.02)
+; LNICM-NOT: call i32 @abs(i32 %i.02)
+for.end:
+  %s.1.lcssa = phi i32 [ %call4, %for.body3 ]
+  %t.1.lcssa = phi double [ %call, %for.body3 ]
+  %idxprom = sext i32 %i.02 to i64
+  %arrayidx = getelementptr inbounds i32, i32* %y, i64 %idxprom
+  store i32 %s.1.lcssa, i32* %arrayidx, align 4
+  %inc6 = add nsw i32 %i.02, 1
+  %cmp = icmp slt i32 %inc6, 10
+  br i1 %cmp, label %for.body, label %for.end7
+
+; CHECK: for.end7:
+; CHECK: call double @sin(double %x)
+for.end7:
+  %t.0.lcssa = phi double [ %t.1.lcssa, %for.end ]
+  ret double %t.0.lcssa
+}
+
+declare dso_local double @sin(double) #0
+
+declare dso_local i32 @abs(i32) #0
+
+attributes #0 = { nounwind readnone willreturn }