[LICM] Add a diagnostic analysis for identifying alias information

[anna]

Summary

Currently, in LICM, we use the alias set tracker to identify if the

instruction (we're interested in hoisting) aliases with instruction that
modifies that memory location.

This patch adds an LICM alias analysis diagnostic tool that checks the
mod ref info of the instruction we are interested in hoisting/sinking,
with every instruction in the loop.  Because of O(N^2) complexity this
is now only a diagnostic tool to show the limitation we have with the
alias set tracker and is OFF by default.

Test cases show the difference with the diagnostic analysis tool, where
we're able to hoist out loads and readonly + argmemonly calls from the
loop, where the alias set tracker analysis is not able to hoist these
instructions out.

[reames]

Detailed comments inline.

A couple of testing notes:

1. don't the guard tests change output as well? Or has Max's fix for that already landed?
2. we need some tests for readonly calls which are not guards or invariant.starts.

lib/Transforms/Scalar/LICM.cpp

1588 ↗

(On Diff #161062)

I don't see any reason not to merge these two functions. They can both work on memory locations. The internal behaviour can be conditional. This also extends this to read only calls.

Unrelated, but it just occurred to me this interface could be simplified with MemoryLocation. Expect to have to rebase shortly. :)

1597 ↗

(On Diff #161062)

Move to top of file

1601 ↗

(On Diff #161062)

Comment doesn't seem consistent with this being only a diagnostic mechanism. I think you need to adjust either your submission comment or this comment to be consistent.

(For those reading along, this is a port of a downstream patch. The primary *upstream* value is for finding AST deficiencies, but we do run with a small non-zero value for this.)

1634 ↗

(On Diff #161062)

You can lift the formation of the MemoryLocation out of this loop, and even out of the function.

[anna]

In D50854#1202845, @reames wrote:

Detailed comments inline.

A couple of testing notes:

1. don't the guard tests change output as well? Or has Max's fix for that already landed?

I'd tested to see if changing the default value in this patch caused any other LICM test to fail, none did other than the invariant.start case. So, I guess Max's fix has landed for guards.

2. we need some tests for readonly calls which are not guards or invariant.starts.

will do.

lib/Transforms/Scalar/LICM.cpp

1601 ↗

(On Diff #161062)

Last part of the comment talks about the complexity, which is the reason for having it as a diagnostic tool (lines 1610 to 1612). I'll add the "diagnostic mechanism" phrase at the start of this comment as well.

[anna]

addressed review comments. added more tests. Diagnostic analysis used for loads and readonly+argmemonly calls.

[reames]

LGTM

I still feel the framing comment could use some improvement, but I don't have anything specific I can suggest.

Fair warning, you've got a slightly messy rebase. We apparently miscommunicated and I landed the MemLoc refactor in the meantime.

[anna]

rebased over ToT.

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

static cl::opt<bool>
     DisablePromotion("disable-licm-promotion", cl::Hidden, cl::init(false),
                      cl::desc("Disable memory promotion in LICM pass"));
 
 static cl::opt<uint32_t> MaxNumUsesTraversed(
     "licm-max-num-uses-traversed", cl::Hidden, cl::init(8),
     cl::desc("Max num uses visited for identifying load "
              "invariance in loop using invariant start (default = 8)"));
 
+// Default value of zero implies we use the regular alias set tracker mechanism
+// instead of the cross product using AA to identify aliasing of the memory
+// location we are interested in.
+static cl::opt<int>
+LICMN2Theshold("licm-n2-threshold", cl::Hidden, cl::init(0),
+               cl::desc("How many instruction to cross product using AA"));
+
 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);
 static void hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
                   LoopSafetyInfo *SafetyInfo,
                   OptimizationRemarkEmitter *ORE);
 static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT,
                  const Loop *CurLoop, LoopSafetyInfo *SafetyInfo,
                  OptimizationRemarkEmitter *ORE, bool FreeInLoop);
 static bool isSafeToExecuteUnconditionally(Instruction &Inst,
                                            const DominatorTree *DT,
                                            const Loop *CurLoop,
                                            const LoopSafetyInfo *SafetyInfo,
                                            OptimizationRemarkEmitter *ORE,
                                            const Instruction *CtxI = nullptr);
-static bool isInvalidatedByLoop(const MemoryLocation &MemLoc,
-                                AliasSetTracker *CurAST);
+static bool pointerInvalidatedByLoop(MemoryLocation MemLoc,
+                                     AliasSetTracker *CurAST, Loop *CurLoop,
+                                     AliasAnalysis *AA);
+
 static Instruction *
 CloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN,
                             const LoopInfo *LI,
                             const LoopSafetyInfo *SafetyInfo);
 
 namespace {
 struct LoopInvariantCodeMotion {
   bool runOnLoop(Loop *L, AliasAnalysis *AA, LoopInfo *LI, DominatorTree *DT,
if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
 
     if (LI->isAtomic() && !TargetExecutesOncePerLoop)
       return false; // Don't risk duplicating unordered loads
 
     // This checks for an invariant.start dominating the load.
     if (isLoadInvariantInLoop(LI, DT, CurLoop))
       return true;
 
-    bool Invalidated = isInvalidatedByLoop(MemoryLocation::get(LI), CurAST);
+    // Don't hoist loads which have may-aliased stores in loop.
+    uint64_t Size = 0;
+    if (LI->getType()->isSized())
+      Size = I.getModule()->getDataLayout().getTypeStoreSize(LI->getType());
+
+    AAMDNodes AAInfo;
+    LI->getAAMetadata(AAInfo);
+
+    bool Invalidated = pointerInvalidatedByLoop(
+        MemoryLocation(LI->getOperand(0), Size, AAInfo), CurAST, CurLoop, AA);
     // 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";
if (Behavior == FMRB_DoesNotAccessMemory)
       return true;
     if (AliasAnalysis::onlyReadsMemory(Behavior)) {
       // A readonly argmemonly function only reads from memory pointed to by
       // it's arguments with arbitrary offsets.  If we can prove there are no
       // writes to this memory in the loop, we can hoist or sink.
       if (AliasAnalysis::onlyAccessesArgPointees(Behavior)) {
         for (Value *Op : CI->arg_operands())
           if (Op->getType()->isPointerTy() &&
-              isInvalidatedByLoop(MemoryLocation(Op,
-                                                 MemoryLocation::UnknownSize,
-                                                 AAMDNodes()),
-                                  CurAST))
+              pointerInvalidatedByLoop(
+                  MemoryLocation(Op, MemoryLocation::UnknownSize, AAMDNodes()),
+                  CurAST, CurLoop, AA))
             return false;
         return true;
       }
 
       // If this call only reads from memory and there are no writes to memory
       // in the loop, we can hoist or sink the call as appropriate.
       if (isReadOnly(CurAST))
         return true;
void LegacyLICMPass::deleteAnalysisLoop(Loop *L) {
   AliasSetTracker *AST = LICM.getLoopToAliasSetMap().lookup(L);
   if (!AST)
     return;
 
   delete AST;
   LICM.getLoopToAliasSetMap().erase(L);
 }
 
-/// Return true if the body of this loop may store into the memory
-/// location pointed to by V.
-///
-static bool isInvalidatedByLoop(const MemoryLocation &MemLoc,
-                                AliasSetTracker *CurAST) {
-  // Check to see if any of the basic blocks in CurLoop invalidate *V.
-  return CurAST->getAliasSetFor(MemLoc).isMod();
+static bool pointerInvalidatedByLoop(MemoryLocation MemLoc,
+                                     AliasSetTracker *CurAST, Loop *CurLoop,
+                                     AliasAnalysis *AA) {
+  // First check to see if any of the basic blocks in CurLoop invalidate *V.
+  bool isInvalidatedAccordingToAST = CurAST->getAliasSetFor(MemLoc).isMod();
+
+  if (!isInvalidatedAccordingToAST || !LICMN2Theshold)
+    return isInvalidatedAccordingToAST;
+
+  // Check with a diagnostic analysis if we can refine the information above.
+  // This is to identify the limitations of using the AST.
+  // The alias set mechanism used by LICM has a major weakness in that it
+  // combines all things which may alias into a single set *before* asking
+  // modref questions. As a result, a single readonly call within a loop will
+  // collapse all loads and stores into a single alias set and report
+  // invalidation if the loop contains any store. For example, readonly calls
+  // with deopt states have this form and create a general alias set with all
+  // loads and stores.  In order to get any LICM in loops containing possible
+  // deopt states we need a more precise invalidation of checking the mod ref
+  // info of each instruction within the loop and LI. This has a complexity of
+  // O(N^2), so currently, it is used only as a diagnostic tool since the
+  // default value of LICMN2Threshold is zero.
+
+  // Don't look at nested loops.
+  if (CurLoop->begin() != CurLoop->end())
+    return true;
+
+  int N = 0;
+  for (BasicBlock *BB : CurLoop->getBlocks())
+    for (Instruction &I : *BB) {
+      if (N >= LICMN2Theshold) {
+        LLVM_DEBUG(dbgs() << "Alasing N2 threshold exhausted for "
+                          << *(MemLoc.Ptr) << "\n");
+        return true;
+      }
+      N++;
+      auto Res = AA->getModRefInfo(&I, MemLoc);
+      if (isModSet(Res)) {
+        LLVM_DEBUG(dbgs() << "Aliasing failed on " << I << " for "
+                          << *(MemLoc.Ptr) << "\n");
+        return true;
+      }
+    }
+  LLVM_DEBUG(dbgs() << "Aliasing okay for " << *(MemLoc.Ptr) << "\n");
+  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/Transforms/LICM/argmemonly-call.ll

-; RUN: opt -S -basicaa -licm %s | FileCheck %s
-; RUN: opt -aa-pipeline=basic-aa -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' < %s -S | FileCheck %s
+; RUN: opt -S -basicaa -licm -licm-n2-threshold=0 %s | FileCheck %s
+; RUN: opt -licm -basicaa -licm-n2-threshold=200 < %s -S | FileCheck %s --check-prefix=ALIAS-N2
+; RUN: opt -aa-pipeline=basic-aa -licm-n2-threshold=0 -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' < %s -S | FileCheck %s
+; RUN: opt -aa-pipeline=basic-aa -licm-n2-threshold=200 -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' < %s -S | FileCheck %s --check-prefix=ALIAS-N2
+
 declare i32 @foo() readonly argmemonly nounwind
 declare i32 @foo2() readonly nounwind
 declare i32 @bar(i32* %loc2) readonly argmemonly nounwind
 
 define void @test(i32* %loc) {
 ; CHECK-LABEL: @test
 ; CHECK: @foo
 ; CHECK-LABEL: loop:

 ; CHECK: @bar
   br label %loop
 
 loop:
   %res = call i32 @bar(i32* %loc2)
   store i32 %res, i32* %loc
   br label %loop
 }
+
+declare i32 @foo_new(i32*) readonly
+; With the default AST mechanism used by LICM for alias analysis,
+; we clump foo_new with bar.
+; With the N2 Alias analysis diagnostic tool, we are able to hoist the
+; argmemonly bar call out of the loop.
+
+define void @test5(i32* %loc2, i32* noalias %loc) {
+; ALIAS-N2-LABEL: @test5
+; ALIAS-N2: @bar
+; ALIAS-N2-LABEL: loop:
+
+; CHECK-LABEL: @test5
+; CHECK-LABEL: loop:
+; CHECK:  @bar
+  br label %loop
+
+loop:
+  %res1 = call i32 @bar(i32* %loc2)
+  %res = call i32 @foo_new(i32* %loc2)
+  store volatile i32 %res1, i32* %loc
+  br label %loop
+}
+

llvm/trunk/test/Transforms/LICM/invariant.start.ll

-; RUN: opt -licm -basicaa < %s -S | FileCheck %s
-; RUN: opt -aa-pipeline=basic-aa -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' < %s -S | FileCheck %s
+; RUN: opt -licm -basicaa -licm-n2-threshold=0 < %s -S | FileCheck %s
+; RUN: opt -licm -basicaa -licm-n2-threshold=200 < %s -S | FileCheck %s --check-prefix=ALIAS-N2
+; RUN: opt -aa-pipeline=basic-aa -licm-n2-threshold=0 -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' < %s -S | FileCheck %s
+; RUN: opt -aa-pipeline=basic-aa -licm-n2-threshold=200 -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' < %s -S | FileCheck %s --check-prefix=ALIAS-N2
 
-; TODO: should be able to hoist both load and invariant.start
+; TODO: By default (without the -licm-n2-threshold value), we should be able to hoist both load and invariant.start
 define void @test1(i1 %cond, i32* %ptr) {
 ; CHECK-LABEL: @test1(
 ; CHECK-LABEL: entry:
 ; CHECK-LABEL: loop:
 ; CHECK: call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr)
 ; CHECK: %val = load i32, i32* %ptr
 
+; ALIAS-N2-LABEL: @test1(
+; ALIAS-N2-LABEL: entry:
+; ALIAS-N2:         %val = load i32, i32* %ptr
+; ALIAS-N2-LABEL: loop:
+; ALIAS-N2: call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr)
+
 entry:
   br label %loop
 
 loop:
   %x = phi i32 [ 0, %entry ], [ %x.inc, %loop ]
   call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr)
   %val = load i32, i32* %ptr
   %x.inc = add i32 %x, %val
   br label %loop
 }
 
-;; TODO: despite the loop varying invariant.start, we should be
+;; TODO: By default, despite the loop varying invariant.start, we should be
 ;; able to hoist the load
 define void @test2(i1 %cond, i32* %ptr) {
 ; CHECK-LABEL: @test2(
 ; CHECK-LABEL: entry:
 ; CHECK-LABEL: loop:
 ; CHECK: call {}* @llvm.invariant.start.p0i32(i64 4, i32* %piv)
 ; CHECK: %val = load i32, i32* %ptr
-  
+; ALIAS-N2-LABEL: @test2(
+; ALIAS-N2-LABEL: entry:
+; ALIAS-N2:         %val = load i32, i32* %ptr
+; ALIAS-N2-LABEL: loop:
+; ALIAS-N2:         call {}* @llvm.invariant.start.p0i32(i64 4, i32* %piv)
 entry:
   br label %loop
 
 loop:
   %x = phi i32 [ 0, %entry ], [ %x.inc, %loop ]
   %piv = getelementptr i32, i32* %ptr, i32 %x
   call {}* @llvm.invariant.start.p0i32(i64 4, i32* %piv)
   %val = load i32, i32* %ptr
   %x.inc = add i32 %x, %val
   br label %loop
 }
 
-; Should be able to hoist since store doesn't alias
+; By default, should be able to hoist since store doesn't alias
 define void @test3(i1 %cond, i32* %ptr) {
 ; CHECK-LABEL: @test3(
 ; CHECK-LABEL: entry:
 ; CHECK-LABEL: loop:
 ; CHECK: call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr)
 ; CHECK: %val = load i32, i32* %ptr
 
+; ALIAS-N2-LABEL: @test3(
+; ALIAS-N2-LABEL: entry:
+; ALIAS-N2:         %val = load i32, i32* %ptr
+; ALIAS-N2-LABEL: loop:
+; ALIAS-N2:         call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr)
 entry:
   br label %loop
 
 loop:
   %x = phi i32 [ 0, %entry ], [ %x.inc, %loop ]
   call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr)
   %val = load i32, i32* %ptr
   %p2 = getelementptr i32, i32* %ptr, i32 1
   store volatile i32 0, i32* %p2
   %x.inc = add i32 %x, %val
   br label %loop
 }
 
 ; can't hoist due to init in loop, only well defined if loop exits
 ; on first iteration, but we don't bother checking for that currently
 define void @test4(i1 %cond, i32* %ptr) {
 ; CHECK-LABEL: @test4(
 ; CHECK-LABEL: entry:
 ; CHECK-LABEL: loop:
 ; CHECK:   store i32 0, i32* %ptr
 ; CHECK: call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr)
 ; CHECK: %val = load i32, i32* %ptr
 
+; ALIAS-N2-LABEL: @test4(
+; ALIAS-N2-LABEL: entry:
+; ALIAS-N2-LABEL: loop:
+; ALIAS-N2:   store i32 0, i32* %ptr
+; ALIAS-N2: call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr)
+; ALIAS-N2: %val = load i32, i32* %ptr
 entry:
   br label %loop
 
 loop:
   %x = phi i32 [ 0, %entry ], [ %x.inc, %loop ]
   store i32 0, i32* %ptr
   call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr)
   %val = load i32, i32* %ptr
   %x.inc = add i32 %x, %val
   br label %loop
 }
 
 ; don't try to reason about scopes
 define void @test5(i1 %cond, i32* %ptr) {
 ; CHECK-LABEL: @test5(
 ; CHECK-LABEL: entry:
 ; CHECK-LABEL: loop:
 ; CHECK:   store i32 0, i32* %ptr
 ; CHECK: call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr)
 ; CHECK: %val = load i32, i32* %ptr
 
+; ALIAS-N2-LABEL: @test5(
+; ALIAS-N2-LABEL: entry:
+; ALIAS-N2-LABEL: loop:
+; ALIAS-N2:   store i32 0, i32* %ptr
+; ALIAS-N2: call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr)
+; ALIAS-N2: %val = load i32, i32* %ptr
 entry:
   br label %loop
 
 loop:
   %x = phi i32 [ 0, %entry ], [ %x.inc, %loop ]
   store i32 0, i32* %ptr
   %scope = call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr)
   %val = load i32, i32* %ptr
   call void @llvm.invariant.end.p0i32({}* %scope, i64 4, i32* %ptr)
   %x.inc = add i32 %x, %val
   br label %loop
 }
 
 declare {}* @llvm.invariant.start.p0i32(i64, i32*)
 declare void @llvm.invariant.end.p0i32({}*, i64, i32*)

llvm/trunk/test/Transforms/LICM/read-only-calls.ll

+; RUN: opt -S -basicaa -licm -licm-n2-threshold=0 %s | FileCheck %s
+; RUN: opt -licm -basicaa -licm-n2-threshold=200 < %s -S | FileCheck %s --check-prefix=ALIAS-N2
+; RUN: opt -aa-pipeline=basic-aa -licm-n2-threshold=0 -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' < %s -S | FileCheck %s
+; RUN: opt -aa-pipeline=basic-aa -licm-n2-threshold=200 -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' < %s -S | FileCheck %s --check-prefix=ALIAS-N2
+
+; We should be able to hoist loads in presence of read only calls and stores
+; that do not alias.
+
+; Since LICM uses the AST mechanism for alias analysis, we will clump
+; together all loads and stores in one set along with the read-only call.
+; This prevents hoisting load that doesn't alias with any other memory
+; operations.
+
+declare void @foo(i64, i32*) readonly
+
+; hoist the load out with the n2-threshold
+; since it doesn't alias with the store.
+; default AST mechanism clumps all memory locations in one set because of the
+; readonly call
+define void @test1(i32* %ptr) {
+; CHECK-LABEL: @test1(
+; CHECK-LABEL: entry:
+; CHECK-LABEL: loop:
+; CHECK: %val = load i32, i32* %ptr
+
+; ALIAS-N2-LABEL: @test1(
+; ALIAS-N2-LABEL: entry:
+; ALIAS-N2:         %val = load i32, i32* %ptr
+; ALIAS-N2-LABEL: loop:
+entry:
+  br label %loop
+
+loop:
+  %x = phi i32 [ 0, %entry ], [ %x.inc, %loop ]
+  %val = load i32, i32* %ptr
+  call void @foo(i64 4, i32* %ptr)
+  %p2 = getelementptr i32, i32* %ptr, i32 1
+  store volatile i32 0, i32* %p2
+  %x.inc = add i32 %x, %val
+  br label %loop
+}
+
+; can hoist out load with the default AST and the alias analysis mechanism.
+define void @test2(i32* %ptr) {
+; CHECK-LABEL: @test2(
+; CHECK-LABEL: entry:
+; CHECK: %val = load i32, i32* %ptr
+; CHECK-LABEL: loop:
+
+; ALIAS-N2-LABEL: @test2(
+; ALIAS-N2-LABEL: entry:
+; ALIAS-N2:         %val = load i32, i32* %ptr
+; ALIAS-N2-LABEL: loop:
+entry:
+  br label %loop
+
+loop:
+  %x = phi i32 [ 0, %entry ], [ %x.inc, %loop ]
+  %val = load i32, i32* %ptr
+  call void @foo(i64 4, i32* %ptr)
+  %x.inc = add i32 %x, %val
+  br label %loop
+}
+
+; cannot hoist load since not guaranteed to execute
+define void @test3(i32* %ptr) {
+; CHECK-LABEL: @test3(
+; CHECK-LABEL: entry:
+; CHECK-LABEL: loop:
+; CHECK: %val = load i32, i32* %ptr
+
+; ALIAS-N2-LABEL: @test3(
+; ALIAS-N2-LABEL: entry:
+; ALIAS-N2-LABEL: loop:
+; ALIAS-N2:         %val = load i32, i32* %ptr
+entry:
+  br label %loop
+
+loop:
+  %x = phi i32 [ 0, %entry ], [ %x.inc, %loop ]
+  call void @foo(i64 4, i32* %ptr)
+  %val = load i32, i32* %ptr
+  %x.inc = add i32 %x, %val
+  br label %loop
+}