[LICM] Hoist guards with invariant conditions

[mkazantsev]

Summary

This patch teaches LICM to hoist guards from the loop if they are guaranteed to execute and
if there are no side effects that could prevent that.

[sanjoy]

Didn't look at the code, but this needs a test case that shows we don't hoist the second guard in

for (;;) {
  guard(loop_varying);
  gurad(loop_invariant);
}

[reames]

lib/Transforms/Scalar/LICM.cpp

461

Bug: Can only start true if a) readonly loop or b) header block.

526

hoist always returns true. Separately, change it to return void and update other caller.

[mkazantsev]

lib/Transforms/Scalar/LICM.cpp

461

Indeed. Thanks for pointing out!

[mkazantsev]

lib/Transforms/Scalar/LICM.cpp

526

Not sure if it's a good idea... What if it changes in the future? Besides, sink can actually return false, and it would be strange to have different signatures for these two.

[mkazantsev]

Fixed bug in mem-write detection, added tests to exercise guard-after-guard scenarios.

[mkazantsev]

Fixed test: underlying aliasing bug caused incorrect behavior on it.

[reames]

LGTM w/mandatory separate cleanup changes as described.

lib/Transforms/Scalar/LICM.cpp

523

Note for anyone reading: This can be trivially extended to llvm.invariant.start w/no uses. I thought about requiring that in this review, but decided a separate patch was better.

526

This was not a suggestion. Please make the change. It can be done post commit, but I want this cleanup done. At the moment, you have control flow in this patch which is never executed and introduces non-trivial reasoning complexity for no value.

In general, the person who changes code in the future has to think about the implications of their changes. Future proofing never works and just adds complexity now.

[mkazantsev]

lib/Transforms/Scalar/LICM.cpp

526

https://reviews.llvm.org/D50696

[mkazantsev]

Rebased.

lib/Transforms/Scalar/LICM.cpp

 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Metadata.h"
+#include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/PredIteratorCache.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Scalar/LoopPassManager.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
for (DomTreeNode *DTN : Worklist) {
     // subloop (which would already have been processed).
     if (inSubLoop(BB, CurLoop, LI))
       continue;
 
     // Keep track of whether the prefix of instructions visited so far are such
     // that the next instruction visited is guaranteed to execute if the loop
     // is entered.
     bool IsMustExecute = CurLoop->getHeader() == BB;
+    // Keep track of whether the prefix instructions could have written memory.
+    // TODO: This and IsMustExecute may be done smarter if we keep track of all
+    // throwing and mem-writing operations in every block, e.g. using something
+    // similar to isGuaranteedToExecute.
+    bool IsMemoryNotModified = CurLoop->getHeader() == BB;
 
     for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
       Instruction &I = *II++;
       // Try constant folding this instruction.  If all the operands are
       // constants, it is technically hoistable, but it would be better to
       // just fold it.
       if (Constant *C = ConstantFoldInstruction(
               &I, I.getModule()->getDataLayout(), TLI)) {
for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
         I.replaceAllUsesWith(Product);
         I.eraseFromParent();
 
         hoist(*ReciprocalDivisor, DT, CurLoop, SafetyInfo, ORE);
         Changed = true;
         continue;
       }
 
+      using namespace PatternMatch;
+      if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>()) &&
+          IsMustExecute && IsMemoryNotModified &&
+          CurLoop->hasLoopInvariantOperands(&I)) {
+        bool Hoisted = hoist(I, DT, CurLoop, SafetyInfo, ORE);
+        Changed |= Hoisted;
+        // If we haven't hoisted the guard, we need to update isMustExecute.
+        // TODO: in current implementation, hoist always return true. Consider
+        // making it void and inserting an unconditional continue here.
+        if (Hoisted)
+          continue;
+      }
+
       if (IsMustExecute)
         IsMustExecute = isGuaranteedToTransferExecutionToSuccessor(&I);
+      if (IsMemoryNotModified)
+        IsMemoryNotModified = !I.mayWriteToMemory();
     }
   }
 
   return Changed;
 }
 
 // Return true if LI is invariant within scope of the loop. LI is invariant if
 // CurLoop is dominated by an invariant.start representing the same memory

test/Transforms/GuardWidening/loop-schedule.ll

leave:                                            ; preds = %leave.loopexit, %entry
   ret void
 }
 
 define void @within_loop(i32 %a, i32 %b, i1* %c_p) {
 ; CHECK-LABEL @within_loop
 ; CHECK:  %cond_0 = icmp ult i32 %a, 10
 ; CHECK:  %cond_1 = icmp ult i32 %b, 10
 ; CHECK:  %wide.chk = and i1 %cond_0, %cond_1
-; CHECK-LABEL: loop:
 ; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %wide.chk) [ "deopt"() ]
+; CHECK-LABEL: loop:
 
 entry:
   br label %loop
 
 loop:                                             ; preds = %loop.preheader, %loop
   %cond_0 = icmp ult i32 %a, 10
   call void (i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
   %cond_1 = icmp ult i32 %b, 10

test/Transforms/LICM/guards.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
 
-; TODO: should be able to hoist both guard and load
+; Hoist guard and load.
 define void @test1(i1 %cond, i32* %ptr) {
 ; CHECK-LABEL: @test1(
 ; CHECK-LABEL: entry:
-; CHECK-LABEL: loop:
 ; CHECK: call void (i1, ...) @llvm.experimental.guard(i1 %cond)
 ; CHECK: %val = load i32, i32* %ptr
+; CHECK-LABEL: loop:
 
 entry:
   br label %loop
 
 loop:
   %x = phi i32 [ 0, %entry ], [ %x.inc, %loop ]
   call void (i1, ...) @llvm.experimental.guard(i1 %cond) ["deopt" (i32 0)]
   %val = load i32, i32* %ptr
loop:
   store i32 0, i32* %p2
   call void (i1, ...) @llvm.experimental.guard(i1 %cond) ["deopt" (i32 0)]
   %val = load i32, i32* %ptr
   %x.inc = add i32 %x, %val
   br label %loop
 }
 
 
-; Could hoist, but don't
+; Hoist guard. Cannot hoist load because of aliasing.
 define void @test3(i1 %cond, i32* %ptr) {
 ; CHECK-LABEL: @test3(
 ; CHECK-LABEL: entry:
-; CHECK-LABEL: loop:
 ; CHECK: call void (i1, ...) @llvm.experimental.guard(i1 %cond)
+; CHECK-LABEL: loop:
 ; CHECK: %val = load i32, i32* %ptr
+; CHECK: store i32 0, i32* %ptr
 
 entry:
   br label %loop
 
 loop:
   %x = phi i32 [ 0, %entry ], [ %x.inc, %loop ]
   call void (i1, ...) @llvm.experimental.guard(i1 %cond) ["deopt" (i32 0)]
   %val = load i32, i32* %ptr
   store i32 0, i32* %ptr
   %x.inc = add i32 %x, %val
   br label %loop
 }
 
+
+; TODO: We can also hoist this guard from mustexec non-header block.
+define void @test4(i1 %c, i32* %p) {
+
+; CHECK-LABEL: @test4(
+; CHECK-LABEL: entry:
+; CHECK:       %a = load i32, i32* %p
+; CHECK:       %invariant_cond = icmp ne i32 %a, 100
+; CHECK-LABEL: loop:
+; CHECK-LABEL: backedge:
+; CHECK:       call void (i1, ...) @llvm.experimental.guard(i1 %invariant_cond)
+
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
+  %iv.next = add i32 %iv, 1
+  br i1 %c, label %if.true, label %if.false
+
+if.true:
+  br label %backedge
+
+if.false:
+  br label %backedge
+
+backedge:
+  %a = load i32, i32* %p
+  %invariant_cond = icmp ne i32 %a, 100
+  call void (i1, ...) @llvm.experimental.guard(i1 %invariant_cond) [ "deopt"() ]
+  %loop_cond = icmp slt i32 %iv.next, 1000
+  br i1 %loop_cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; Do not hoist across a conditionally executed side effect.
+define void @test4a(i1 %c, i32* %p, i32* %q) {
+
+; CHECK-LABEL: @test4a(
+; CHECK-LABEL: entry:
+; CHECK-LABEL: loop:
+; CHECK-LABEL: if.true:
+; CHECK:       store
+; CHECK-LABEL: backedge:
+; CHECK:       %a = load i32, i32* %p
+; CHECK:       %invariant_cond = icmp ne i32 %a, 100
+; CHECK:       call void (i1, ...) @llvm.experimental.guard(i1 %invariant_cond)
+
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
+  %iv.next = add i32 %iv, 1
+  br i1 %c, label %if.true, label %if.false
+
+if.true:
+  store i32 123, i32* %q
+  br label %backedge
+
+if.false:
+  br label %backedge
+
+backedge:
+  %a = load i32, i32* %p
+  %invariant_cond = icmp ne i32 %a, 100
+  call void (i1, ...) @llvm.experimental.guard(i1 %invariant_cond) [ "deopt"() ]
+  %loop_cond = icmp slt i32 %iv.next, 1000
+  br i1 %loop_cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; Do not hoist a conditionally executed guard.
+define void @test4b(i1 %c, i32* %p, i32* %q) {
+
+; CHECK-LABEL: @test4b(
+; CHECK-LABEL: entry:
+; CHECK-LABEL: loop:
+; CHECK-LABEL: if.true:
+; CHECK:       %a = load i32, i32* %p
+; CHECK:       %invariant_cond = icmp ne i32 %a, 100
+; CHECK:       call void (i1, ...) @llvm.experimental.guard(i1 %invariant_cond)
+; CHECK-LABEL: backedge:
+
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
+  %iv.next = add i32 %iv, 1
+  br i1 %c, label %if.true, label %if.false
+
+if.true:
+  %a = load i32, i32* %p
+  %invariant_cond = icmp ne i32 %a, 100
+  call void (i1, ...) @llvm.experimental.guard(i1 %invariant_cond) [ "deopt"() ]
+  br label %backedge
+
+if.false:
+  br label %backedge
+
+backedge:
+  %loop_cond = icmp slt i32 %iv.next, 1000
+  br i1 %loop_cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; Do not hoist an invariant guard across a variant guard.
+define void @test5(i1 %c, i32* %p, i32* %q) {
+
+; CHECK-LABEL: @test5(
+; CHECK-LABEL: entry:
+; CHECK:         %a = load i32, i32* %p
+; CHECK:         %invariant_cond = icmp ne i32 %a, 100
+; CHECK-LABEL: loop:
+; CHECK:         %variant_cond = icmp ne i32 %a, %iv
+; CHECK:         call void (i1, ...) @llvm.experimental.guard(i1 %variant_cond)
+; CHECK:         call void (i1, ...) @llvm.experimental.guard(i1 %invariant_cond)
+
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
+  %iv.next = add i32 %iv, 1
+  %a = load i32, i32* %p
+  %invariant_cond = icmp ne i32 %a, 100
+  %variant_cond = icmp ne i32 %a, %iv
+  call void (i1, ...) @llvm.experimental.guard(i1 %variant_cond) [ "deopt"() ]
+  call void (i1, ...) @llvm.experimental.guard(i1 %invariant_cond) [ "deopt"() ]
+  br label %backedge
+
+backedge:
+  %loop_cond = icmp slt i32 %iv.next, 1000
+  br i1 %loop_cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; Hoist an invariant guard, leave the following variant guard in the loop.
+define void @test5a(i1 %c, i32* %p, i32* %q) {
+
+; CHECK-LABEL: @test5a(
+; CHECK-LABEL: entry:
+; CHECK:         %a = load i32, i32* %p
+; CHECK:         %invariant_cond = icmp ne i32 %a, 100
+; CHECK:         call void (i1, ...) @llvm.experimental.guard(i1 %invariant_cond)
+; CHECK-LABEL: loop:
+; CHECK:         %variant_cond = icmp ne i32 %a, %iv
+; CHECK:         call void (i1, ...) @llvm.experimental.guard(i1 %variant_cond)
+
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
+  %iv.next = add i32 %iv, 1
+  %a = load i32, i32* %p
+  %invariant_cond = icmp ne i32 %a, 100
+  %variant_cond = icmp ne i32 %a, %iv
+  call void (i1, ...) @llvm.experimental.guard(i1 %invariant_cond) [ "deopt"() ]
+  call void (i1, ...) @llvm.experimental.guard(i1 %variant_cond) [ "deopt"() ]
+  br label %backedge
+
+backedge:
+  %loop_cond = icmp slt i32 %iv.next, 1000
+  br i1 %loop_cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
 declare void @llvm.experimental.guard(i1, ...)