[LICM] Hoist an invariant_start out of loops if there are no stores executed before it

[reames]

Summary

Once the invariant_start is reached, we know that no instruction *after* it can modify the memory. So, if we can prove the location isn't read *between entry into the loop and the execution of the invariant_start*, we can execute the invariant_start before entering the loop.

[anna]

LGTM

lib/Transforms/Scalar/LICM.cpp

for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
         I.eraseFromParent();
 
         hoist(*ReciprocalDivisor, DT, CurLoop, SafetyInfo, ORE);
         Changed = true;
         continue;
       }
 
       using namespace PatternMatch;
-      if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>()) &&
+      if (((I.use_empty() &&
+            match(&I, m_Intrinsic<Intrinsic::invariant_start>())) ||
+           match(&I, m_Intrinsic<Intrinsic::experimental_guard>())) &&
           IsMustExecute && IsMemoryNotModified &&
           CurLoop->hasLoopInvariantOperands(&I)) {
         hoist(I, DT, CurLoop, SafetyInfo, ORE);
         Changed = true;
         continue;
       }
 
       if (IsMustExecute)
if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
 
     // Don't sink calls which can throw.
     if (CI->mayThrow())
       return false;
 
     if (Function *F = CI->getCalledFunction())
         switch (F->getIntrinsicID()) {
         default: break;
-        // TODO: support invariant.start, and experimental.guard here
         case Intrinsic::assume:
           // Assumes 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)

test/Transforms/LICM/invariant.start.ll

 ; 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: 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: call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr)
 ; CHECK: %val = load i32, i32* %ptr
 ; CHECK-LABEL: loop:
-; CHECK: call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr)
 
 ; ALIAS-N2-LABEL: @test1(
 ; ALIAS-N2-LABEL: entry:
-; ALIAS-N2:         %val = load i32, i32* %ptr
+; ALIAS-N2: call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr)
+; 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
loop:
   %val = load i32, i32* %ptr
   %x.inc = add i32 %x, %val
   br label %loop
 }
 
 define void @test3(i1 %cond, i32* %ptr) {
 ; CHECK-LABEL: @test3(
 ; CHECK-LABEL: entry:
+; CHECK: call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr)
 ; CHECK: %val = load i32, i32* %ptr
 ; CHECK-LABEL: loop:
-; CHECK: call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr)
 
 ; ALIAS-N2-LABEL: @test3(
 ; ALIAS-N2-LABEL: entry:
-; ALIAS-N2:         %val = load i32, i32* %ptr
+; ALIAS-N2: call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr)
+; 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