[LICM] Check a heuristic case to hoist load

[jaykang10]

Summary

Let's see an example with MemorySSA.

loop.header:
; 2 = MemoryPhi({entry,liveOnEntry},{loop.body,1})
  %i.0 = phi i32 [ 0, %entry ], [ %inc, %loop.body ]
...

loop.body:
; MemoryUse(2) MayAlias
  %0 = load i32**, i32*** @a, align 8, !tbaa !8
  %idxprom = zext i32 %i.0 to i64
  %arrayidx = getelementptr inbounds i32*, i32** %0, i64 %idxprom
; 1 = MemoryDef(2)
  store i32* null, i32** %arrayidx, align 8, !tbaa !8
...

As you can see, there is a dependence with MayAlias between %0 = load of MemoryUse(2) and store of 1 = MemoryDef(2). However, it is WAR dependence at first iteration of the loop and there is no dependence at rest of iteration. In this case, we can hoist the '%0 = load` to preheader.

It fixes https://bugs.llvm.org/show_bug.cgi?id=52143.

[fhahn]

llvm/lib/Transforms/Scalar/LICM.cpp

2407

is !tbaa required here?

Also, would it be possible that @a contains the address of @a before we enter the loop? Could the first store in the loop modify @a that way?

2466

is this sufficient? An addrec could have an unknown step I think, which could be 0.

[nikic]

I don't get what you're doing here. @a can store a pointer to @a, so the store will modify @a, resulting in a different loaded value on the next iteration.

[jaykang10]

Ah... @a could contains the address of @a... Thanks for pointing out it. @fhahn @nikic

It is fundamental problem with alias between different pointer types like long **, long***... I need to find the clear background reason to distinguish them...

Let me think about it more.

llvm/lib/Transforms/Scalar/LICM.cpp

2407

is !tbaa required here?

The same !tbaa on load and store is intended to show that it causes MayAlias on TBAA.

Also, would it be possible that @a contains the address of @a before we enter the loop? Could the first store in the loop modify @a that way?

You are right! I missed it...

2466

Ah, step could be 0... Thanks for pointing out it.

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

 /// target executes at most once per execution of the loop body.  This is used
 /// to assess the legality of duplicating atomic loads.  Generally, this is
 /// true when moving out of loop and not true when moving into loops.
 /// If \p ORE is set use it to emit optimization remarks.
 bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
                         Loop *CurLoop, AliasSetTracker *CurAST,
                         MemorySSAUpdater *MSSAU, bool TargetExecutesOncePerLoop,
                         SinkAndHoistLICMFlags *LICMFlags = nullptr,
-                        OptimizationRemarkEmitter *ORE = nullptr);
+                        OptimizationRemarkEmitter *ORE = nullptr,
+                        ScalarEvolution *SE = nullptr);
 
 /// Returns the comparison predicate used when expanding a min/max reduction.
 CmpInst::Predicate getMinMaxReductionPredicate(RecurKind RK);
 
 /// See RecurrenceDescriptor::isSelectCmpPattern for a description of the
 /// pattern we are trying to match. In this pattern we are only ever selecting
 /// between two values: 1) an initial PHI start value, and 2) a loop invariant
 /// value. This function uses \p LoopExitInst to determine 2), which we then use

llvm/lib/Transforms/Scalar/LICM.cpp

 static bool pointerInvalidatedByLoop(MemoryLocation MemLoc,
                                      AliasSetTracker *CurAST, Loop *CurLoop,
                                      AAResults *AA);
 static bool pointerInvalidatedByLoopWithMSSA(MemorySSA *MSSA, MemoryUse *MU,
                                              Loop *CurLoop, Instruction &I,
                                              SinkAndHoistLICMFlags &Flags);
 static bool pointerInvalidatedByBlockWithMSSA(BasicBlock &BB, MemorySSA &MSSA,
                                               MemoryUse &MU);
+static bool checkHeuristicCase(MemorySSA *MSSA, MemoryUse *MU, Loop *CurLoop,
+                               LoadInst *LI, SinkAndHoistLICMFlags &Flags,
+                               ScalarEvolution *SE);
 static Instruction *cloneInstructionInExitBlock(
     Instruction &I, BasicBlock &ExitBlock, PHINode &PN, const LoopInfo *LI,
     const LoopSafetyInfo *SafetyInfo, MemorySSAUpdater *MSSAU);
 
 static void eraseInstruction(Instruction &I, ICFLoopSafetyInfo &SafetyInfo,
                              MemorySSAUpdater *MSSAU);
 
 static void moveInstructionBefore(Instruction &I, Instruction &Dest,
for (Instruction &I : llvm::make_early_inc_range(*BB)) {
       // this if all of the operands of the instruction are loop invariant and
       // if it is safe to hoist the instruction. We also check block frequency
       // to make sure instruction only gets hoisted into colder blocks.
       // TODO: It may be safe to hoist if we are hoisting to a conditional block
       // and we have accurately duplicated the control flow from the loop header
       // to that block.
       if (CurLoop->hasLoopInvariantOperands(&I) &&
           canSinkOrHoistInst(I, AA, DT, CurLoop, /*CurAST*/ nullptr, MSSAU,
-                             true, &Flags, ORE) &&
+                             true, &Flags, ORE, SE) &&
           worthSinkOrHoistInst(I, CurLoop->getLoopPreheader(), ORE, BFI) &&
           isSafeToExecuteUnconditionally(
               I, DT, TLI, CurLoop, SafetyInfo, ORE,
               CurLoop->getLoopPreheader()->getTerminator())) {
         hoist(I, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
               MSSAU, SE, ORE);
         HoistedInstructions.push_back(&I);
         Changed = true;

 }
 }
 
 bool llvm::canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
                               Loop *CurLoop, AliasSetTracker *CurAST,
                               MemorySSAUpdater *MSSAU,
                               bool TargetExecutesOncePerLoop,
                               SinkAndHoistLICMFlags *Flags,
-                              OptimizationRemarkEmitter *ORE) {
+                              OptimizationRemarkEmitter *ORE,
+                              ScalarEvolution *SE) {
   assert(((CurAST != nullptr) ^ (MSSAU != nullptr)) &&
          "Either AliasSetTracker or MemorySSA should be initialized.");
 
   // If we don't understand the instruction, bail early.
   if (!isHoistableAndSinkableInst(I))
     return false;
 
   MemorySSA *MSSA = MSSAU ? MSSAU->getMemorySSA() : nullptr;
if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
 
     bool Invalidated;
     if (CurAST)
       Invalidated = pointerInvalidatedByLoop(MemoryLocation::get(LI), CurAST,
                                              CurLoop, AA);
     else
       Invalidated = pointerInvalidatedByLoopWithMSSA(
           MSSA, cast<MemoryUse>(MSSA->getMemoryAccess(LI)), CurLoop, I, *Flags);
+
+    if (Invalidated)
+      Invalidated =
+          checkHeuristicCase(MSSA, cast<MemoryUse>(MSSA->getMemoryAccess(LI)),
+                             CurLoop, LI, *Flags, SE);
+
     // Check loop-invariant address because this may also be a sinkable load
     // whose address is not necessarily loop-invariant.
     if (ORE && Invalidated && CurLoop->isLoopInvariant(LI->getPointerOperand()))
       ORE->emit([&]() {
         return OptimizationRemarkMissed(
                    DEBUG_TYPE, "LoadWithLoopInvariantAddressInvalidated", LI)
                << "failed to move load with loop-invariant address "
                   "because the loop may invalidate its value";
bool pointerInvalidatedByBlockWithMSSA(BasicBlock &BB, MemorySSA &MSSA,
   if (const 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;
 }
 
+bool checkHeuristicCase(MemorySSA *MSSA, MemoryUse *MU, Loop *CurLoop,
+                        LoadInst *LI, SinkAndHoistLICMFlags &Flags,
+                        ScalarEvolution *SE) {
+  // Let's see an example with MemorySSA.
+  //
+  // loop.header:
+  // ; 2 = MemoryPhi({entry,liveOnEntry},{loop.body,1})
+  //   %i.0 = phi i32 [ 0, %entry ], [ %inc, %loop.body ]
+  // ...
+  //
+  // loop.body:
+  // ; MemoryUse(2) MayAlias
+  //   %0 = load i32**, i32*** @a, align 8, !tbaa !8
+  //   %idxprom = zext i32 %i.0 to i64
+  //   %arrayidx = getelementptr inbounds i32*, i32** %0, i64 %idxprom
+  // ; 1 = MemoryDef(2)
+  //   store i32* null, i32** %arrayidx, align 8, !tbaa !8
+  // ...
+  //
+  // As we can see, there is a dependence with MayAlias between `%0 = load` of
+  // MemoryUse(2) and `store` of `1 = MemoryDef(2)`. However, it is WAR
+  // dependence at first iteration of the loop and there is no dependence at
+  // rest of iterations. In this case, we can hoist the '%0 = load` to
+  // preheader.
+
+  // Considered only hoisting load instruction.
+  if (Flags.getIsSink())
+    return true;
+
+  // Find the memory defining access of load.
+  MemoryAccess *Source = MU->getDefiningAccess();
+
+  // Considered only MemoryPhi with loop.
+  auto *MemPhi = dyn_cast<MemoryPhi>(Source);
+  if (!MemPhi)
+    return true;
+
+  // Simply, this function considers only simple MemoryPhi which has only one
+  // MemoryDef as incoming value inside loop.
+  Instruction *DefInst = nullptr;
+  for (unsigned I = 0, E = MemPhi->getNumIncomingValues(); I != E; ++I) {
+    auto *IncAcc = MemPhi->getIncomingValue(I);
+    if (CurLoop->contains(IncAcc->getBlock())) {
+      if (auto *DefMA = dyn_cast<MemoryDef>(IncAcc)) {
+        if (DefInst)
+          return true;
+        else
+          DefInst = DefMA->getMemoryInst();
+      }
+    }
+  }
+
+  if (!DefInst)
+    return true;
+
+  // Considered only store instruction as MemoryDef.
+  StoreInst *SI = dyn_cast<StoreInst>(DefInst);
+  if (!SI)
+    return true;
+
+  // Check the underlying object of store is load.
+  Value *Object = getUnderlyingObject(SI->getPointerOperand());
+  if (Object != LI)
+    return true;
+
+  // Check the ptrdiff between load and store is AddRecExpr. If it is
+  // AddRecExpr, we can say there is no dependance between load and store in the
+  // loop.
+  auto *LoadSCEV = SE->getSCEV(LI);
+  auto *StorePtrSCEV = SE->getSCEV(SI->getPointerOperand());
+  auto *PtrDiffSCEV = SE->getMinusSCEV(StorePtrSCEV, LoadSCEV);
+  if (dyn_cast<SCEVAddRecExpr>(PtrDiffSCEV))
+    return false;
+
+  return true;
+}
+
 /// 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/test/Transforms/LICM/heuristic-hoist-load.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -passes='loop-mssa(licm)' -S < %s | FileCheck %s
+
+@a = dso_local local_unnamed_addr global i32** null, align 8
+
+; The %0 should be hoisted.
+
+define void @foo(i32 %max) {
+; CHECK-LABEL: @foo(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32**, i32*** @a, align 8
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    [[I_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_BODY:%.*]] ]
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp sgt i32 [[I_0]], [[MAX:%.*]]
+; CHECK-NEXT:    br i1 [[CMP_NOT]], label [[FOR_COND_CLEANUP:%.*]], label [[FOR_BODY]]
+; CHECK:       for.cond.cleanup:
+; CHECK-NEXT:    ret void
+; CHECK:       for.body:
+; CHECK-NEXT:    [[IDXPROM:%.*]] = zext i32 [[I_0]] to i64
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32*, i32** [[TMP0]], i64 [[IDXPROM]]
+; CHECK-NEXT:    store i32* null, i32** [[ARRAYIDX]], align 8, !tbaa [[TBAA0:![0-9]+]]
+; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[I_0]], 1
+; CHECK-NEXT:    br label [[FOR_COND]], !llvm.loop [[LOOP4:![0-9]+]]
+;
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.body, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  %cmp.not = icmp sgt i32 %i.0, %max
+  br i1 %cmp.not, label %for.cond.cleanup, label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.cond
+  ret void
+
+for.body:                                         ; preds = %for.cond
+  %0 = load i32**, i32*** @a, align 8, !tbaa !8
+  %idxprom = zext i32 %i.0 to i64
+  %arrayidx = getelementptr inbounds i32*, i32** %0, i64 %idxprom
+  store i32* null, i32** %arrayidx, align 8, !tbaa !8
+  %inc = add nuw nsw i32 %i.0, 1
+  br label %for.cond, !llvm.loop !12
+}
+
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!8 = !{!9, !9, i64 0}
+!9 = !{!"any pointer", !10, i64 0}
+!10 = !{!"omnipotent char", !11, i64 0}
+!11 = !{!"Simple C/C++ TBAA"}
+!12 = distinct !{!12, !13}
+!13 = !{!"llvm.loop.mustprogress"}