[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 ↗

(On Diff #159886)

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

523 ↗

(On Diff #159886)

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

[mkazantsev]

lib/Transforms/Scalar/LICM.cpp

461 ↗

(On Diff #159886)

Indeed. Thanks for pointing out!

[mkazantsev]

lib/Transforms/Scalar/LICM.cpp

523 ↗

(On Diff #159886)

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 ↗

(On Diff #160066)

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.

523 ↗

(On Diff #159886)

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

523 ↗

(On Diff #159886)

https://reviews.llvm.org/D50696

[mkazantsev]

Rebased.

llvm/trunk/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)) {
+        hoist(I, DT, CurLoop, SafetyInfo, ORE);
+        Changed = true;
+        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

llvm/trunk/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

llvm/trunk/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

 backedge:
   %loop_cond = icmp slt i32 %iv.next, 1000
   br i1 %loop_cond, label %loop, label %exit
 
 exit:
   ret void
 }
 
-; We can hoist an invariant guard, leave the following variant guard in the loop.
+; 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 %invariant_cond)
 ; 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