[LICM] Hoist stores of invariant values to invariant addresses out of loops

[reames]

Summary

(now ready for review)

Teach LICM to hoist stores out of loops when the store writes to a location otherwise unused in the loop, writes a value which is invariant, and is guaranteed to execute if the loop is entered.

Worth noting is that this transformation is partially overlapping with the existing promotion transformation. Reasons this is worthwhile anyway include:

1. For multi-exit loops, this doesn't require duplication of the store.
2. It kicks in for case where we can't prove we exit through a normal exit (i.e. we may throw), but can prove the store executes before that possible side exit.

[reames]

Rebase on top of tests, with test updates.

Still not quite ready for review. I want to remove the writeonly call stuff into it's own patch.

[reames]

Strip out the call hoisting bits until a future patch.

[mkazantsev]

I'm generally fine with the patch once all nits are addressed. It needs more extended testing for conditionally executed stores (we should show that they don't get hoisted).

At the first glance, AliasSetTracker looks independent, but I may be missing something. If possible, please split it into a separate patch and add some dedicated testing on it (my guess is that a unit test can be written on this change).

include/llvm/Analysis/AliasSetTracker.h

223 ↗

(On Diff #161826)

This function is growing bigger, maybe it makes sense to move it to cpp file. Just a suggestion.

227 ↗

(On Diff #161826)

Isn't it the same as !empty()?
Do you mind adding a clarifying comment on what is being proved here?

230 ↗

(On Diff #161826)

Unneeded ;

lib/Transforms/Scalar/LICM.cpp

706 ↗

(On Diff #161826)

Can it go separately?

719 ↗

(On Diff #161826)

No need for that.

745 ↗

(On Diff #161826)

We can hoist stores to locations that are read within the loop if we can prove that no read may happen before the store. It doesn't matter if this location is then stored again or not in this case.

Please add it as a TODO item, may be interesting in the future.

test/Transforms/LICM/store-hoisting.ll

47 ↗

(On Diff #161826)

I don't see any tests exercising conditionally executed stores in this file. Please add some (with control flow and with potentially throwing calls before the store).

[reames]

include/llvm/Analysis/AliasSetTracker.h

223 ↗

(On Diff #161826)

Fair, mind if I do that post commit?

lib/Transforms/Scalar/LICM.cpp

706 ↗

(On Diff #161826)

As in, land the TODO by itself? Sure, if you prefer.

745 ↗

(On Diff #161826)

The particular case mentioned could be done, but the motivating case you described offline w/a readonly call in the loop is much harder than it first sounds. The basic problem is the AST doesn't actually keep track of the *instructions* it only tracks memory locations. So, for a large read set, we don't have an efficient way to determine if there's a single mod.

I think the transform you're looking for is probably better done w/MemorySSA once we get around to that (larger) rewrite.

I'd prefer not to put a todo here if you don't mind.

test/Transforms/LICM/store-hoisting.ll

47 ↗

(On Diff #161826)

Will do before next round of review.

[reames]

Address first couple comments, another update to come before re-review justified.

Max, I can't test the unique instruction bit through AST printer at the moment. I could add printer support for the unique instruction helper, but I'm starting to seriously wonder if this belongs in AST at all. If you don't mind, I'd prefer to exercise through LICM at the moment so splitting/moving the API is easy.

[reames]

Adding requested tests, ready for review.

[anna]

I'll take a closer look at the patch, but at first glance it looks like some cases of invariant store that's preventing the vectorizer (because LICM wasn't hoisting/sinking the store) may be handled by running LICM before vectorization: testcases in D50665 maybe worth trying here - note that those test cases are running LICM before vectorization.

There are 3 kinds of tests worth adding:

1. predicated invariant stores, i.e. the block containing the store itself is predicated and not guaranteed to execute (cannot be handled by LICM)
2. invariant store value is a phi containing invariant incoming values and the phi result depends on an invariant condition (can be handled by LICM. This patch handles?)
3. invariant store value is a phi containing invariant incoming values and the phi result depends on a variant condition (cannot be handled by LICM safely)

[anna]

lib/Transforms/Scalar/LICM.cpp

748 ↗

(On Diff #161979)

I might be missing something. Here we're only checking for the address we're storing into is invariant. Where's the check for the stored value is invariant? That decides if we should hoist or sink the store right?

Also, could you pls add test cases where the stored value is variant while the store address is invariant.

[reames]

In D50925#1211015, @anna wrote:

There are 3 kinds of tests worth adding:

1. predicated invariant stores, i.e. the block containing the store itself is predicated and not guaranteed to execute (cannot be handled by LICM)

Covered by existing early exit test.

2. invariant store value is a phi containing invariant incoming values and the phi result depends on an invariant condition (can be handled by LICM. This patch handles?)

Unclear what you mean here.

3. invariant store value is a phi containing invariant incoming values and the phi result depends on a variant condition (cannot be handled by LICM safely)

Again, I don't know what you mean by this. If the value is a phi in the loop, it's by definition not invariant.

lib/Transforms/Scalar/LICM.cpp

748 ↗

(On Diff #161979)

This is handled in the caller. See conditional logic before call to hoist. We check that *all* operands are loop invariant.

As for the test, see the existing neg_lv_value.

[anna]

In D50925#1211359, @reames wrote:

In D50925#1211015, @anna wrote:

There are 3 kinds of tests worth adding:

1. predicated invariant stores, i.e. the block containing the store itself is predicated and not guaranteed to execute (cannot be handled by LICM)

Covered by existing early exit test.

2. invariant store value is a phi containing invariant incoming values and the phi result depends on an invariant condition (can be handled by LICM. This patch handles?)

Unclear what you mean here.

Added example:

define void @inv_val_store_to_inv_address_conditional_inv(i32* %a, i64 %n, i32* %b, i32 %k) {
entry:
  %ntrunc = trunc i64 %n to i32
  %cmp = icmp eq i32 %ntrunc, %k
  br label %for.body

for.body:                                         ; preds = %for.body, %entry
  %i = phi i64 [ %i.next, %latch ], [ 0, %entry ]
  %tmp1 = getelementptr inbounds i32, i32* %b, i64 %i
  %tmp2 = load i32, i32* %tmp1, align 8
  store i32 %ntrunc, i32* %tmp1
  br i1 %cmp, label %cond_store, label %cond_store_k

cond_store:
  br label %latch

cond_store_k:
  br label %latch

latch:
  %storeval = phi i32 [ %ntrunc, %cond_store ], [ %k, %cond_store_k ]
  store i32 %storeval, i32* %a <-- this store can be hoisted by LICM (the stored value is invariant in the loop). 
  %i.next = add nuw nsw i64 %i, 1
  %cond = icmp slt i64 %i.next, %n
  br i1 %cond, label %for.body, label %for.end

for.end:                                          ; preds = %for.body
  ret void

3. invariant store value is a phi containing invariant incoming values and the phi result depends on a variant condition (cannot be handled by LICM safely)

Again, I don't know what you mean by this. If the value is a phi in the loop, it's by definition not invariant.

yes, that's why I stated it "cannot be handled by LICM safely", in the sense it is not correct :)

[reames]

In D50925#1211383, @anna wrote:

Added example:

(snipped example for length)

This is a really interesting example, but it's out of scope for this patch. The critical bit in your example is not the store, it's the phi. You're pointing out that when we have a diamond which exists only to select between two loop invariant values, we can do phi-to-select transform and then hoist the resulting select out of the loop. I have some questions on your example, let's discuss offline. This is definitely off topic for this review, so let's move further discussion of this one to a bug or another review thread if we get that far.

[mkazantsev]

Looks fine for me, except for I think that we should not give up improvement opportunities just because AST is not strong enough to do it. We may use other data structures for that.
I'm OK with concerns I had. If Anna is OK with her concerns, I think we can have it merged.

lib/Transforms/Scalar/LICM.cpp

745 ↗

(On Diff #161826)

It only means that we might want to give up using AST here. The mention that it can be generalized still makes sense.

[reames]

lib/Transforms/Scalar/LICM.cpp

745 ↗

(On Diff #161826)

Add the todo and corresponding tests:
Sending lib/Transforms/Scalar/LICM.cpp
Sending test/Transforms/LICM/store-hoisting.ll
Transmitting file data ..done
Committing transaction...
Committed revision 340978.

When writing the tests, I realized we can handle a lot of common cases, just not the alias set collapse one. Most of tests can be implemented easily.

llvm/trunk/lib/Analysis/AliasSetTracker.cpp

bool AliasSet::aliasesUnknownInst(const Instruction *Inst,
 
   return false;
 }
 
 Instruction* AliasSet::getUniqueInstruction() {
   if (AliasAny)
     // May have collapses alias set
     return nullptr;
-  if (size() != 0)
-    // Can't track source of pointer, might be many instruction
+  if (begin() != end()) {
+    if (!UnknownInsts.empty())
+      // Another instruction found
       return nullptr;
+    if (std::next(begin()) != end())
+      // Another instruction found
+      return nullptr;
+    Value *Addr = begin()->getValue();
+    assert(!Addr->user_empty() &&
+           "where's the instruction which added this pointer?");
+    if (std::next(Addr->user_begin()) != Addr->user_end())
+      // Another instruction found -- this is really restrictive
+      // TODO: generalize!
+      return nullptr;
+    return cast<Instruction>(*(Addr->user_begin()));
+  }
   if (1 != UnknownInsts.size())
     return nullptr;
   return cast<Instruction>(UnknownInsts[0]);
 }
 
 void AliasSetTracker::clear() {
   // Delete all the PointerRec entries.
   for (PointerMapType::iterator I = PointerMap.begin(), E = PointerMap.end();

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

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;
       if (isNotUsedOrFreeInLoop(I, CurLoop, SafetyInfo, TTI, FreeInLoop) &&
-          canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, true, ORE)) {
+          canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, true, ORE) &&
+          !I.mayHaveSideEffects()) {
         if (sink(I, LI, DT, CurLoop, SafetyInfo, ORE, FreeInLoop)) {
           if (!FreeInLoop) {
             ++II;
             CurAST->deleteValue(&I);
             I.eraseFromParent();
           }
           Changed = true;
         }

 }
 
 namespace {
 /// Return true if-and-only-if we know how to (mechanically) both hoist and
 /// sink a given instruction out of a loop.  Does not address legality
 /// concerns such as aliasing or speculation safety.  
 bool isHoistableAndSinkableInst(Instruction &I) {
   // Only these instructions are hoistable/sinkable.
-  return (isa<LoadInst>(I) || isa<CallInst>(I) ||
-          isa<FenceInst>(I) ||
+  return (isa<LoadInst>(I) || isa<StoreInst>(I) ||
+          isa<CallInst>(I) || isa<FenceInst>(I) || 
           isa<BinaryOperator>(I) || isa<CastInst>(I) ||
           isa<SelectInst>(I) || isa<GetElementPtrInst>(I) ||
           isa<CmpInst>(I) || isa<InsertElementInst>(I) ||
           isa<ExtractElementInst>(I) || isa<ShuffleVectorInst>(I) ||
           isa<ExtractValueInst>(I) || isa<InsertValueInst>(I));
 }
 /// Return true if all of the alias sets within this AST are known not to
 /// contain a Mod.
if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
     FunctionModRefBehavior Behavior = AA->getModRefBehavior(CI);
     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)) {
+        // TODO: expand to writeable arguments
         for (Value *Op : CI->arg_operands())
           if (Op->getType()->isPointerTy() &&
               pointerInvalidatedByLoop(
                   MemoryLocation(Op, MemoryLocation::UnknownSize, AAMDNodes()),
                   CurAST, CurLoop, AA))
             return false;
         return true;
       }
if (std::next(Begin) != CurAST->end())
       return false;
     auto *UniqueI = Begin->getUniqueInstruction();
     if (!UniqueI)
       // other memory op, give up
       return false;
     (void)FI; //suppress unused variable warning
     assert(UniqueI == FI && "AS must contain FI");
     return true;
+  } else if (auto *SI = dyn_cast<StoreInst>(&I)) {
+    if (!SI->isUnordered())
+      return false; // Don't sink/hoist volatile or ordered atomic store!
+
+    // We can only hoist a store that we can prove writes a value which is not
+    // read or overwritten within the loop.  For those cases, we fallback to
+    // load store promotion instead.
+    auto &AS = CurAST->getAliasSetFor(MemoryLocation::get(SI));
+
+    if (AS.isRef() || !AS.isMustAlias())
+      // Quick exit test, handled by the full path below as well.
+      return false;
+    auto *UniqueI = AS.getUniqueInstruction();
+    if (!UniqueI)
+      // other memory op, give up
+      return false;
+    assert(UniqueI == SI && "AS must contain SI");
+    return true;
   }
 
   assert(!I.mayReadOrWriteMemory() && "unhandled aliasing");
 
   // We've established mechanical ability and aliasing, it's up to the caller
   // to check fault safety
   return true;
 }

llvm/trunk/test/Transforms/LICM/atomics.ll

loop:
   %vala = load atomic i32, i32* %y monotonic, align 4
   store atomic i32 %vala, i32* %z unordered, align 4
   %exitcond = icmp ne i32 %vala, 0
   br i1 %exitcond, label %end, label %loop
 
 end:
   ret i32 %vala
 ; CHECK-LABEL: define i32 @test7b(
+; CHECK-LABEL: entry:
+; CHECK: store i32 5, i32* %x
+; CHECK-LABEL: loop:
 ; CHECK: load atomic i32, i32* %y monotonic
-
 ; CHECK-LABEL: end:
-; CHECK: store i32 5, i32* %x
 ; CHECK: store atomic i32 %{{.+}}, i32* %z unordered, align 4
 }
 
 
 define i32 @test8(i32* nocapture noalias %x, i32* nocapture %y) {
 entry:
   br label %loop
 

llvm/trunk/test/Transforms/LICM/funclet.ll

invoke void @may_throw()
           to label %postinvoke unwind label %catch.dispatch
 
 else:                                             ; preds = %postinvoke
   invoke void @may_throw()
           to label %forcond.backedge unwind label %catch.dispatch
 }
 
 ; CHECK-LABEL: define void @test3(
-; CHECK:      catchswitch within none
+; CHECK-LABEL: forbody.preheader:
 ; CHECK:      store i32 1, i32* %bc, align 4
 ; CHECK:      store i32 2, i32* %bc2, align 4
+; CHECK:      catchswitch within none
+; CHECK-LABEL: forbody:
 
 declare void @may_throw()
 
 declare i32 @pure_computation() nounwind argmemonly readonly
 
 declare i32 @__CxxFrameHandler3(...)

llvm/trunk/test/Transforms/LICM/promote-order.ll

 ; RUN: opt -tbaa -basicaa -licm -S < %s | FileCheck %s
 ; RUN: opt -aa-pipeline=type-based-aa,basic-aa -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' -S %s | FileCheck %s
 
 ; LICM should keep the stores in their original order when it sinks/promotes them.
 ; rdar://12045203
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.8.0"
 
 @p = external global i8*
 
 define i32* @_Z4doiti(i32 %n, float* %tmp1, i32* %tmp3) nounwind {
+; CHECK-LABEL: for.body.lr.ph:
+; CHECK: store float 1.000000e+00, float* %tmp1
+; CHECK-LABEL: for.cond.for.end_crit_edge:
+; CHECK: store i32 1, i32* %tmp3
+
 entry:
   %cmp1 = icmp slt i32 0, %n
   br i1 %cmp1, label %for.body.lr.ph, label %for.end
 
 for.body.lr.ph:                                   ; preds = %entry
   br label %for.body
 
 for.body:                                         ; preds = %for.body, %for.body.lr.ph
   %i.02 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.body ]
   store float 1.000000e+00, float* %tmp1, align 4, !tbaa !1
   store i32 1, i32* %tmp3, align 4, !tbaa !2
   %inc = add nsw i32 %i.02, 1
   %cmp = icmp slt i32 %inc, %n
   br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge
 
-; CHECK: for.cond.for.end_crit_edge:
-; CHECK: store float 1.000000e+00, float* %tmp1
-; CHECK: store i32 1, i32* %tmp3
 for.cond.for.end_crit_edge:                       ; preds = %for.body
   %split = phi i32* [ %tmp3, %for.body ]
   br label %for.end
 
 for.end:                                          ; preds = %for.cond.for.end_crit_edge, %entry
   %r.0.lcssa = phi i32* [ %split, %for.cond.for.end_crit_edge ], [ undef, %entry ]
   ret i32* %r.0.lcssa
 }
 
 !0 = !{!"minimal TBAA"}
 !1 = !{!3, !3, i64 0}
 !2 = !{!4, !4, i64 0}
 !3 = !{!"float", !0}
 !4 = !{!"int", !0}

llvm/trunk/test/Transforms/LICM/store-hoisting.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
 
 define void @test(i32* %loc) {
 ; CHECK-LABEL: @test
-; CHECK-LABEL: exit:
+; CHECK-LABEL: entry:
 ; CHECK: store i32 0, i32* %loc
+; CHECK-LABEL: loop:
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [0, %entry], [%iv.next, %loop]
   store i32 0, i32* %loc
   %iv.next = add i32 %iv, 1
   %cmp = icmp slt i32 %iv, 200
   br i1 %cmp, label %loop, label %exit
 
 exit:
   ret void
 }
 
 define void @test_multiexit(i32* %loc, i1 %earlycnd) {
 ; CHECK-LABEL: @test_multiexit
-; CHECK-LABEL: exit1:
-; CHECK: store i32 0, i32* %loc
-; CHECK-LABEL: exit2:
+; CHECK-LABEL: entry:
 ; CHECK: store i32 0, i32* %loc
+; CHECK-LABEL: loop:
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [0, %entry], [%iv.next, %backedge]
   store i32 0, i32* %loc
   %iv.next = add i32 %iv, 1
   br i1 %earlycnd, label %exit1, label %backedge
   
 backedge:
   %cmp = icmp slt i32 %iv, 200
   br i1 %cmp, label %loop, label %exit2
 
 exit1:
   ret void
 exit2:
   ret void
 }
 
+define i32* @false_negative_2use(i32* %loc) {
+; CHECK-LABEL: @false_negative_2use
+; CHECK-LABEL: exit:
+; CHECK: store i32 0, i32* %loc
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [0, %entry], [%iv.next, %loop]
+  store i32 0, i32* %loc
+  %iv.next = add i32 %iv, 1
+  %cmp = icmp slt i32 %iv, 200
+  br i1 %cmp, label %loop, label %exit
+
+exit:
+  ret i32* %loc
+}
+
 define void @neg_lv_value(i32* %loc) {
 ; CHECK-LABEL: @neg_lv_value
 ; CHECK-LABEL: exit:
 ; CHECK: store i32 %iv.lcssa, i32* %loc
 entry:
   br label %loop
 
 loop:
loop:
   %iv.next = add i32 %iv, 1
   %cmp = icmp slt i32 %iv, 200
   br i1 %cmp, label %loop, label %exit
 
 exit:
   ret void
 }
 
+declare void @maythrow() inaccessiblememonly
+
+define void @neg_early_exit(i32* %loc) {
+; CHECK-LABEL: @neg_early_exit
+; CHECK-LABEL: body:
+; CHECK: store i32 0, i32* %loc
+; CHECK-LABEL: exit:
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [0, %entry], [%iv.next, %body]
+  %is_null = icmp eq i32* %loc, null
+  br i1 %is_null, label %exit, label %body
+body:
+  call void @maythrow()
+  store i32 0, i32* %loc
+  %iv.next = add i32 %iv, 1
+  %cmp = icmp slt i32 %iv, 200
+  br i1 %cmp, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+define void @neg_early_throw(i32* %loc) {
+; CHECK-LABEL: @neg_early_throw
+; CHECK-LABEL: loop:
+; CHECK: store i32 0, i32* %loc
+; CHECK-LABEL: exit:
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [0, %entry], [%iv.next, %loop]
+  call void @maythrow()
+  store i32 0, i32* %loc
+  %iv.next = add i32 %iv, 1
+  %cmp = icmp slt i32 %iv, 200
+  br i1 %cmp, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+define void @test_late_throw(i32* %loc) {
+; CHECK-LABEL: @test_late_throw
+; CHECK-LABEL: entry:
+; CHECK: store i32 0, i32* %loc
+; CHECK-LABEL: loop:
+entry:
+  br label %loop
 
+loop:
+  %iv = phi i32 [0, %entry], [%iv.next, %loop]
+  store i32 0, i32* %loc
+  call void @maythrow()
+  %iv.next = add i32 %iv, 1
+  %cmp = icmp slt i32 %iv, 200
+  br i1 %cmp, label %loop, label %exit
+
+exit:
+  ret void
+}