[LICM] Allow movement of non-aliasing calls that at most only write to memory

[ddcc]

Summary

This patch allows readnone/writeonly calls that at most only write to non-aliasing memory to be moved.

[asbirlea]

Please check failing tests.

The idea does not seem right. If a call can only write and not read, it cannot necessarily be moved.

Your test2() example looks incorrect. If foo2b writes to str and foo2c reads from it and writes to it, then foo2c should read the value written inside the loop, which can be overwritten on different iterations.

Example:

• foo2b writes value 2 to str.
• foo2c reads value from str, increments by 1 and writes back.
• loop runs 3 times.

With foo2b inside the loop, final value in str is 3.
With foo2b outside the loop, final value in str is 5.

I did not look at test1().

llvm/lib/Transforms/Scalar/LICM.cpp

1173

No reason to add the else when the if returns.

[ddcc]

Check aliasing on arguments, update tests

[ddcc]

In D80319#2048052, @asbirlea wrote:

The idea does not seem right. If a call can only write and not read, it cannot necessarily be moved.

Your test2() example looks incorrect. If foo2b writes to str and foo2c reads from it and writes to it, then foo2c should read the value written inside the loop, which can be overwritten on different iterations.

Example:

• foo2b writes value 2 to str.
• foo2c reads value from str, increments by 1 and writes back.
• loop runs 3 times.

With foo2b inside the loop, final value in str is 3.
With foo2b outside the loop, final value in str is 5.

The intention is that given a function which only writes the values of its inputs elsewhere in memory without aliasing, calls to that function can be hoisted because they will still execute at least once. But, I was missing some noalias checks on the arguments, which are now fixed, because not reading through the argument doesn't mean that the underlying memory can't be otherwise accessed.

In this testcase, foo2c (now foo2d) may only write to str because of the writeonly attribute, but it can't be hoisted because it may read elsewhere from memory.

[ddcc]

Drop ineffective loop aliasing check

[asbirlea]

Let's take the examples below, same scenario.

If @foo2e writes 2 to str, and @foo2f reads, increments by 1 and writes back, and the loop runs 3 times.
Code below gives result 3. When @foo2e is hoisted, the result is 5.
At the very least you need to check pointerInvalidatedByLoop for all call args.

declare void @foo2e(i8*) argmemonly writeonly nounwind
declare void @foo2f(i8*) nounwind

entry:
  %mem = call noalias i8* @malloc()
  %str = getelementptr inbounds [4 x i8], [4 x i8]* @str, i64 0, i64 0
  br label %loop
loop:
  call void @foo2e(i8* %mem)
  call void @foo2f(i8* %mem)
  br i1 %c, label %loop, label %out
out:
  ret void

For inaccessible memory, if two of the calls inside the loop write to that same inaccessible memory location, and one meets the condition to hoist, while the other also reads, then it's legal to hoist one of them?
@foo2e always writes 2 to that location.
@foo2f reads that location, increments by 1 and writes it back.
With an iteration count of 3, the original code will hold 3 at that location. After hoisting it will hold 5.

declare void @foo2e() inaccessiblemem writeonly nounwind
declare void @foo2f() nounwind

entry:
  %mem = call noalias i8* @malloc()
  %str = getelementptr inbounds [4 x i8], [4 x i8]* @str, i64 0, i64 0
  br label %loop
loop:
  call void @foo2e()
  call void @foo2f()
  br i1 %c, label %loop, label %out
out:
  ret void

[ddcc]

Thanks for the feedback!

If @foo2e writes 2 to str, and @foo2f reads, increments by 1 and writes back, and the loop runs 3 times.
Code below gives result 3. When @foo2e is hoisted, the result is 5.
At the very least you need to check pointerInvalidatedByLoop for all call args.

I am missing a check on noalias arguments, but wouldn't it need to be for reference instead of modification (as implemented by pointerInvalidatedByLoop*)? For example, if the increment call (foo2f) occurred before the write call (foo2e), then it is no longer correct to hoist out the write either. I'm also not sure what to do with the MemorySSA variant when the AliasSetTracker is not available; MemorySSA seems to generate only a single MemoryDef for a call, which doesn't distinguish between definitions of arguments or other memory.

Instead, perhaps it'd be easier if I just limited this case to inaccessiblememonly calls with readnone arguments? That is my primary use case, anyway.

For inaccessible memory, if two of the calls inside the loop write to that same inaccessible memory location, and one meets the condition to hoist, while the other also reads, then it's legal to hoist one of them?
@foo2e always writes 2 to that location.
@foo2f reads that location, increments by 1 and writes it back.
With an iteration count of 3, the original code will hold 3 at that location. After hoisting it will hold 5.

That's a good point. The inaccessible memory that I'm interested in is memory-mapped from a hardware peripheral, so I know it doesn't alias, but I don't see a good way to express that with the existing function attributes. Even with LTO, there's no guarantee that an inaccessiblememonly function can't alias against another regular external function. The closest relevant attribute would be noalias, but that only applies to memory derived from input arguments, which would mean nothing on a readnone argument. I suppose what I'm looking for is some sort of exclusive attribute, which would indicate that the inaccessible memory can't be accessed in any other way.

Another potential issue is whether writeonly must be deterministic? readonly is guaranteed to be pure, but writeonly is only guaranteed to not read from memory or have other side-effects. For example, can a writeonly function access the timestamp counter and write only if the result is even?

[asbirlea]

Would this kind of support be helpful: D69542?
http://lists.llvm.org/pipermail/llvm-dev/2019-November/136705.html

[ddcc]

Thanks for mentioning it; yeah, I think restrict support would be useful for functions that do access arguments, but it wouldn't cover aliasing in the second case between external functions with attributes that don't access arguments.

llvm/lib/Transforms/Scalar/LICM.cpp

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),
+    LICMN2Threshold("licm-n2-threshold", cl::Hidden, cl::init(0),
                     cl::desc("How many instruction to cross product using AA"));
 
 // Experimental option to allow imprecision in LICM in pathological cases, in
 // exchange for faster compile. This is to be removed if MemorySSA starts to
 // address the same issue. This flag applies only when LICM uses MemorySSA
 // instead on AliasSetTracker. LICM calls MemorySSAWalker's
 // getClobberingMemoryAccess, up to the value of the Cap, getting perfect
 // accuracy. Afterwards, LICM will call into MemorySSA's getDefiningAccess,
 // which may not be precise, since optimizeUses is capped. The result is
static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT,
                  const Loop *CurLoop, ICFLoopSafetyInfo *SafetyInfo,
                  MemorySSAUpdater *MSSAU, OptimizationRemarkEmitter *ORE);
 static bool isSafeToExecuteUnconditionally(Instruction &Inst,
                                            const DominatorTree *DT,
                                            const Loop *CurLoop,
                                            const LoopSafetyInfo *SafetyInfo,
                                            OptimizationRemarkEmitter *ORE,
                                            const Instruction *CtxI = nullptr);
-static bool pointerInvalidatedByLoop(MemoryLocation MemLoc,
-                                     AliasSetTracker *CurAST, Loop *CurLoop,
-                                     AliasAnalysis *AA);
+static bool pointerAccessedByLoop(MemoryLocation MemLoc,
+                                  AliasAnalysis *AA, bool Invalidate);
 static bool pointerInvalidatedByLoopWithMSSA(MemorySSA *MSSA, MemoryUse *MU,
                                              Loop *CurLoop,
                                              SinkAndHoistLICMFlags &Flags);
 static Instruction *CloneInstructionInExitBlock(
     Instruction &I, BasicBlock &ExitBlock, PHINode &PN, const LoopInfo *LI,
     const LoopSafetyInfo *SafetyInfo, MemorySSAUpdater *MSSAU);
 
 static void eraseInstruction(Instruction &I, ICFLoopSafetyInfo &SafetyInfo,
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;
     if (CurAST)
-      Invalidated = pointerInvalidatedByLoop(MemoryLocation::get(LI), CurAST,
-                                             CurLoop, AA);
+      Invalidated = pointerAccessedByLoop(MemoryLocation::get(LI), CurAST,
+                                          CurLoop, AA, true);
     else
       Invalidated = pointerInvalidatedByLoopWithMSSA(
           MSSA, cast<MemoryUse>(MSSA->getMemoryAccess(LI)), CurLoop, *Flags);
     // 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(
if (match(CI, m_Intrinsic<Intrinsic::assume>()))
       return true;
 
     if (match(CI, m_Intrinsic<Intrinsic::experimental_widenable_condition>()))
       // Widenable conditions don't actually alias anything or throw
       return true;
 
     // Handle simple cases by querying alias analysis.
     FunctionModRefBehavior Behavior = AA->getModRefBehavior(CI);
-    if (Behavior == FMRB_DoesNotAccessMemory)
+    if (AliasAnalysis::doesNotReadMemory(Behavior)) {
+      // A readnone/writeonly function can be moved if it does not access
+      // arguments, or it does and the arguments do not alias in the loop.
+      if (!AliasAnalysis::onlyAccessesInaccessibleOrArgMem(Behavior))
+        return false;
+      if (AliasAnalysis::doesAccessArgPointees(Behavior)) {
+        for (Value *Op : CI->arg_operands()) {
+          if (CurAST &&
+              pointerAccessedByLoop(
+                  MemoryLocation(Op, LocationSize::unknown(), AAMDNodes()),
+                  CurAST, CurLoop, AA, false))
+            return false;
+          else if (!isNoAliasArgument(Op) && !isNoAliasCall(Op))
+            return false;
+        }
+      }
+
       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
+      // its 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)) {
         // TODO: expand to writeable arguments
         for (Value *Op : CI->arg_operands())
           if (Op->getType()->isPointerTy()) {
             bool Invalidated;
             if (CurAST)
-              Invalidated = pointerInvalidatedByLoop(
+              Invalidated = pointerAccessedByLoop(
                   MemoryLocation(Op, LocationSize::unknown(), AAMDNodes()),
-                  CurAST, CurLoop, AA);
+                  CurAST, CurLoop, AA, true);
             else
               Invalidated = pointerInvalidatedByLoopWithMSSA(
                   MSSA, cast<MemoryUse>(MSSA->getMemoryAccess(CI)), CurLoop,
                   *Flags);
             if (Invalidated)
               return false;
           }
         return true;
for (User *U : ASIV->users()) {
         unsigned InstAlignment = Load->getAlignment();
         if (!InstAlignment)
           InstAlignment =
               MDL.getABITypeAlignment(Load->getType());
 
         // Note that proving a load safe to speculate requires proving
         // sufficient alignment at the target location.  Proving it guaranteed
         // to execute does as well.  Thus we can increase our guaranteed
-        // alignment as well. 
+        // alignment as well.
         if (!DereferenceableInPH || (InstAlignment > Alignment))
           if (isSafeToExecuteUnconditionally(*Load, DT, CurLoop, SafetyInfo,
                                              ORE, Preheader->getTerminator())) {
             DereferenceableInPH = true;
             Alignment = std::max(Alignment, InstAlignment);
           }
       } else if (const StoreInst *Store = dyn_cast<StoreInst>(UI)) {
         // Stores *of* the pointer are not interesting, only stores *to* the

 ///
 void LegacyLICMPass::deleteAnalysisLoop(Loop *L) {
   if (!LICM.getLoopToAliasSetMap().count(L))
     return;
 
   LICM.getLoopToAliasSetMap().erase(L);
 }
 
-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();
+static bool pointerAccessedByLoop(MemoryLocation MemLoc,
+                                  AliasAnalysis *AA, bool Invalidate) {
+  // First check to see if any of the basic blocks in CurLoop access *V.
+  auto &AS = CurAST->getAliasSetFor(MemLoc);
+  auto isAccesssedAccordingToAST = Invalidate ? AS.isMod() : AS.isRef();
 
-  if (!isInvalidatedAccordingToAST || !LICMN2Theshold)
-    return isInvalidatedAccordingToAST;
+  if (!isAccesssedAccordingToAST || !LICMN2Threshold)
+    return isAccesssedAccordingToAST;
 
   // 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) {
+      if (N >= LICMN2Threshold) {
         LLVM_DEBUG(dbgs() << "Alasing N2 threshold exhausted for "
                           << *(MemLoc.Ptr) << "\n");
         return true;
       }
       N++;
       auto Res = AA->getModRefInfo(&I, MemLoc);
-      if (isModSet(Res)) {
+      if (Invalidate ? isModSet(Res) : isRefSet(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;
 }

llvm/test/Transforms/LICM/hoist-attributes.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S < %s -licm | FileCheck %s
+
+declare i32 @foo1a() readnone nounwind
+declare i32 @foo1b(i8* readnone) readnone nounwind
+declare i32 @foo1c(i8* readnone) nounwind
+
+declare void @foo2a() inaccessiblememonly writeonly nounwind
+declare void @foo2b(i8*) inaccessiblemem_or_argmemonly writeonly nounwind
+declare void @foo2c(i8* readnone) inaccessiblememonly writeonly nounwind
+declare void @foo2d(i8* writeonly) nounwind
+
+@str = internal global [4 x i8] c"foo\00", align 1
+
+declare noalias i8* @malloc()
+
+; Functions that are nounwind and readnone (foo1a, foo1b) can be hoisted
+define i32 @test1(i1 %c) {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[STR:%.*]] = getelementptr inbounds [4 x i8], [4 x i8]* @str, i64 0, i64 0
+; CHECK-NEXT:    [[RET1A:%.*]] = call i32 @foo1a()
+; CHECK-NEXT:    [[RET1B:%.*]] = call i32 @foo1b(i8* [[STR]])
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[ADD1C:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[ADD1A:%.*]] = add nuw i32 [[SUM]], [[RET1A]]
+; CHECK-NEXT:    [[ADD1B:%.*]] = add nuw i32 [[ADD1A]], [[RET1B]]
+; CHECK-NEXT:    [[RET1C:%.*]] = call i32 @foo1c(i8* [[STR]])
+; CHECK-NEXT:    [[ADD1C]] = add nuw i32 [[ADD1B]], [[RET1C]]
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[LOOP]], label [[OUT:%.*]]
+; CHECK:       out:
+; CHECK-NEXT:    [[ADD1C_LCSSA:%.*]] = phi i32 [ [[ADD1C]], [[LOOP]] ]
+; CHECK-NEXT:    ret i32 [[ADD1C_LCSSA]]
+;
+entry:
+  %str = getelementptr inbounds [4 x i8], [4 x i8]* @str, i64 0, i64 0
+  br label %loop
+loop:
+  %sum = phi i32 [ 0, %entry ], [ %add1c, %loop ]
+  %ret1a = call i32 @foo1a()
+  %add1a = add nuw i32 %sum, %ret1a
+  %ret1b = call i32 @foo1b(i8* %str)
+  %add1b = add nuw i32 %add1a, %ret1b
+  %ret1c = call i32 @foo1c(i8* %str)
+  %add1c = add nuw i32 %add1b, %ret1c
+  br i1 %c, label %loop, label %out
+out:
+  ret i32 %add1c
+}
+
+; Only writes to inaccessible or argument memory (foo2a, foo2b, foo2c), can all
+; be hoisted since arguments don't alias or aren't accessed
+define void @test2abc(i1 %c) {
+; CHECK-LABEL: @test2abc(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[MEM:%.*]] = call noalias i8* @malloc()
+; CHECK-NEXT:    [[STR:%.*]] = getelementptr inbounds [4 x i8], [4 x i8]* @str, i64 0, i64 0
+; CHECK-NEXT:    call void @foo2a()
+; CHECK-NEXT:    call void @foo2b(i8* [[MEM]])
+; CHECK-NEXT:    call void @foo2c(i8* [[STR]])
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[LOOP]], label [[OUT:%.*]]
+; CHECK:       out:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %mem = call noalias i8* @malloc()
+  %str = getelementptr inbounds [4 x i8], [4 x i8]* @str, i64 0, i64 0
+  br label %loop
+loop:
+  call void @foo2a()
+  call void @foo2b(i8* %mem)
+  call void @foo2c(i8* %str)
+  br i1 %c, label %loop, label %out
+out:
+  ret void
+}
+
+; May read/write memory that could alias (foo2d), can't be hoisted
+define void @test2d(i1 %c) {
+; CHECK-LABEL: @test2d(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[STR:%.*]] = getelementptr inbounds [4 x i8], [4 x i8]* @str, i64 0, i64 0
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    call void @foo2d(i8* [[STR]])
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[LOOP]], label [[OUT:%.*]]
+; CHECK:       out:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %str = getelementptr inbounds [4 x i8], [4 x i8]* @str, i64 0, i64 0
+  br label %loop
+loop:
+  call void @foo2d(i8* %str)
+  br i1 %c, label %loop, label %out
+out:
+  ret void
+}