[LICM & MSSA] Limit unsafe sinking and hoisting.

[asbirlea]

Summary

The getClobberingMemoryAccess API checks for clobbering accesses in a loop by walking the backedge. This may check if a memory access is being
clobbered by the loop in a previous iteration, depending how smart AA got over the course of the updates in MemorySSA (it does not occur when built from scratch).
If no clobbering access is found inside the loop, it will optimize to an access outside the loop. This however does not mean that access is safe to sink.
Given:

for i
  load a[i]
  store a[i]

The access corresponding to the load can be optimized to outside the loop, and the load can be hoisted. But it is incorrect to sink it.
In order to sink the load, we'd need to check no Def clobbers the Use in the same iteration. With this patch we currently restrict sinking to either
Defs not existing in the loop, or Defs preceding the load in the same block. An easy extension is to ensure the load (Use) post-dominates all Defs.

Caught by PR42294.

This issue also shed light on the converse problem: hoisting stores in this same scenario would be illegal. With this patch we restrict
hoisting of stores to the case when their corresponding Defs are dominating all Uses in the loop.

[george.burgess.iv]

Thanks for this!

I realize that the original test-case is difficult to minimize and reproduce, so having a 'fails before, succeeds now' test isn't easy to make, nor would it be easy to reason about if it breaks. Still, can we please have a quick lit test that asserts e.g.

for i
  load a[i]
  store a[i]

doesn't have the load sunk?

lib/Transforms/Scalar/LICM.cpp

380 ↗

(On Diff #205721)

nit: please add /*IsSink=*/

1238 ↗

(On Diff #205721)

s/hoising/hoisting/

2303 ↗

(On Diff #205721)

s/dyn_cast/isa

also, isa<MemoryDef>(X) implies !isa<MemoryUse>(X), so is this check needed?

2305 ↗

(On Diff #205721)

nit: if the check is needed, no else after an if that continues, please

[asbirlea]

Address comments and add testcase.

[george.burgess.iv]

LGTM

[xiaobai]

The test pr42294.ll breaks when running the test suite on a build without asserts. Specifically, opt doesn't know about the option -debug-only. I confirmed that adding a REQUIRES: asserts to the beginning of the test fixes things. I'm not too familiar with this area, so if you have a way to make it work with non-asserts build then that would be great. Otherwise, we can just require that asserts are enabled for this test to run.

[yrouban]

llvm/trunk/test/Analysis/MemorySSA/pr42294.ll

1

I have just added REQUIRES asserts as it uses -debug-only=licm

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

 bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI,
                           ScalarEvolution *SE);
 
 struct SinkAndHoistLICMFlags {
   bool NoOfMemAccTooLarge;
   unsigned LicmMssaOptCounter;
   unsigned LicmMssaOptCap;
   unsigned LicmMssaNoAccForPromotionCap;
+  bool IsSink;
 };
 
 /// 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, AliasAnalysis, LoopInfo, DominatorTree,
 /// DataLayout, TargetLibraryInfo, Loop, AliasSet information for all

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

bool LoopInvariantCodeMotion::runOnLoop(
   // their loop, into this loop, so there is no need to process the BODIES of
   // 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.
   SinkAndHoistLICMFlags Flags = {NoOfMemAccTooLarge, LicmMssaOptCounter,
-                                 LicmMssaOptCap, LicmMssaNoAccForPromotionCap};
+                                 LicmMssaOptCap, LicmMssaNoAccForPromotionCap,
+                                 /*IsSink=*/true};
   if (L->hasDedicatedExits())
     Changed |= sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, TTI, L,
                           CurAST.get(), MSSAU.get(), &SafetyInfo, Flags, ORE);
+  Flags.IsSink = false;
   if (Preheader)
     Changed |= hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, L,
                            CurAST.get(), MSSAU.get(), &SafetyInfo, Flags, ORE);
 
   // Now that all loop invariants have been removed from the loop, promote any
   // memory references to scalars that we can.
   // Don't sink stores from loops without dedicated block exits. Exits
   // containing indirect branches are not transformed by loop simplify,
if (CurAST) {
       // Check store only if there's still "quota" to check clobber.
       if (Flags->LicmMssaOptCounter >= Flags->LicmMssaOptCap)
         return false;
       // If there are interfering Uses (i.e. their defining access is in the
       // loop), or ordered loads (stored as Defs!), don't move this store.
       // Could do better here, but this is conservatively correct.
       // TODO: Cache set of Uses on the first walk in runOnLoop, update when
       // moving accesses. Can also extend to dominating uses.
+      auto *SIMD = MSSA->getMemoryAccess(SI);
       for (auto *BB : CurLoop->getBlocks())
         if (auto *Accesses = MSSA->getBlockAccesses(BB)) {
           for (const auto &MA : *Accesses)
             if (const auto *MU = dyn_cast<MemoryUse>(&MA)) {
               auto *MD = MU->getDefiningAccess();
               if (!MSSA->isLiveOnEntryDef(MD) &&
                   CurLoop->contains(MD->getBlock()))
                 return false;
+              // Disable hoisting past potentially interfering loads. Optimized
+              // Uses may point to an access outside the loop, as getClobbering
+              // checks the previous iteration when walking the backedge.
+              // FIXME: More precise: no Uses that alias SI.
+              if (!Flags->IsSink && !MSSA->dominates(SIMD, MU))
+                return false;
             } else if (const auto *MD = dyn_cast<MemoryDef>(&MA))
               if (auto *LI = dyn_cast<LoadInst>(MD->getMemoryInst())) {
                 (void)LI; // Silence warning.
                 assert(!LI->isUnordered() && "Expected unordered load");
                 return false;
               }
         }
 
for (BasicBlock *BB : CurLoop->getBlocks())
     }
   LLVM_DEBUG(dbgs() << "Aliasing okay for " << *(MemLoc.Ptr) << "\n");
   return false;
 }
 
 static bool pointerInvalidatedByLoopWithMSSA(MemorySSA *MSSA, MemoryUse *MU,
                                              Loop *CurLoop,
                                              SinkAndHoistLICMFlags &Flags) {
+  // For hoisting, use the walker to determine safety
+  if (!Flags.IsSink) {
     MemoryAccess *Source;
     // See declaration of SetLicmMssaOptCap for usage details.
     if (Flags.LicmMssaOptCounter >= Flags.LicmMssaOptCap)
       Source = MU->getDefiningAccess();
     else {
       Source = MSSA->getSkipSelfWalker()->getClobberingMemoryAccess(MU);
       Flags.LicmMssaOptCounter++;
     }
     return !MSSA->isLiveOnEntryDef(Source) &&
            CurLoop->contains(Source->getBlock());
   }
 
+  // For sinking, we'd need to check all Defs below this use. The getClobbering
+  // call will look on the backedge of the loop, but will check aliasing with
+  // the instructions on the previous iteration.
+  // For example:
+  // for (i ... )
+  //   load a[i] ( Use (LoE)
+  //   store a[i] ( 1 = Def (2), with 2 = Phi for the loop.
+  //   i++;
+  // The load sees no clobbering inside the loop, as the backedge alias check
+  // does phi translation, and will check aliasing against store a[i-1].
+  // However sinking the load outside the loop, below the store is incorrect.
+
+  // For now, only sink if there are no Defs in the loop, and the existing ones
+  // precede the use and are in the same block.
+  // FIXME: Increase precision: Safe to sink if Use post dominates the Def;
+  // needs PostDominatorTreeAnalysis.
+  // FIXME: More precise: no Defs that alias this Use.
+  if (Flags.NoOfMemAccTooLarge)
+    return true;
+  for (auto *BB : CurLoop->getBlocks())
+    if (auto *Accesses = MSSA->getBlockDefs(BB))
+      for (const auto &MA : *Accesses)
+        if (const auto *MD = dyn_cast<MemoryDef>(&MA))
+          if (MU->getBlock() != MD->getBlock() ||
+              !MSSA->locallyDominates(MD, MU))
+            return true;
+  return false;
+}
+
 /// Little predicate that returns true if the specified basic block is in
 /// a subloop of the current one, not the current one itself.
 ///
 static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI) {
   assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop");
   return LI->getLoopFor(BB) != CurLoop;
 }

llvm/trunk/test/Analysis/MemorySSA/pr42294.ll

+; RUN: opt -loop-rotate -licm %s -disable-output -enable-mssa-loop-dependency=true -debug-only=licm 2>&1 | FileCheck %s -check-prefix=LICM
+; RUN: opt -loop-rotate -licm %s -disable-output -enable-mssa-loop-dependency=false -debug-only=licm 2>&1 | FileCheck %s -check-prefix=LICM
+; RUN: opt -loop-rotate -licm %s -S -enable-mssa-loop-dependency=true  | FileCheck %s
+; RUN: opt -loop-rotate -licm %s -S -enable-mssa-loop-dependency=false | FileCheck %s
+
+; LICM: Using
+; LICM-NOT: LICM sinking instruction:   %.pre = load i8, i8* %arrayidx.phi.trans.insert
+
+; CHECK-LABEL: @fn1
+; CHECK-LABEL: entry:
+; CHECK:    br i1 true, label %[[END:.*]], label %[[PH:.*]]
+; CHECK: [[PH]]:
+; CHECK:    br label %[[CRIT:.*]]
+; CHECK: [[CRIT]]:
+; CHECK:    load i8
+; CHECK:    store i8
+; CHECK:    br i1 true, label %[[ENDCRIT:.*]], label %[[CRIT]]
+; CHECK: [[ENDCRIT]]:
+; CHECK-NOT: load i8
+; CHECK:    br label %[[END]]
+
+target datalayout = "E-m:e-i1:8:16-i8:8:16-i64:64-f128:64-a:8:16-n32:64"
+target triple = "s390x-unknown-linux-gnu"
+
+define void @fn1() {
+entry:
+  %g = alloca [9 x i8], align 1
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.for.body_crit_edge, %entry
+  %0 = phi i64 [ 0, %entry ], [ %phitmp, %for.body.for.body_crit_edge ]
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body.for.body_crit_edge ]
+  %arrayidx = getelementptr inbounds [9 x i8], [9 x i8]* %g, i64 0, i64 %indvars.iv
+  store i8 2, i8* %arrayidx, align 1
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br i1 undef, label %for.end18, label %for.body.for.body_crit_edge
+
+for.body.for.body_crit_edge:                      ; preds = %for.body
+  %arrayidx.phi.trans.insert = getelementptr inbounds [9 x i8], [9 x i8]* %g, i64 0, i64 %indvars.iv.next
+  %.pre = load i8, i8* %arrayidx.phi.trans.insert, align 1
+  %phitmp = zext i8 %.pre to i64
+  br label %for.body
+
+for.end18:                                        ; preds = %for.body
+  store i64 %0, i64* undef, align 8
+  ret void
+}
+

llvm/trunk/test/Transforms/LICM/store-hoisting.ll

 exit:
   ret void
 }
 
 ; TODO: could validly hoist the store here since we know what value
 ; the load must observe.
 define i32 @test_dominated_read(i32* %loc) {
 ; CHECK-LABEL: @test_dominated_read
-; CHECK-LABEL: exit:
-; CHECK: store i32 0, i32* %loc
+; MSSA-LABEL: entry:
+; MSSA: store i32 0, i32* %loc
+; MSSA-LABEL: loop:
+; AST-LABEL: exit:
+; AST:  store i32 0, i32* %loc
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [0, %entry], [%iv.next, %loop]
   store i32 0, i32* %loc
   %reload = load i32, i32* %loc
   %iv.next = add i32 %iv, 1