[WIP][LICM] Hoisting of guards, assumes, and invariant_starts

[reames]

Summary

This is a WIP which is slowly being split into reviewable pieces:

• Assumes have landed under https://reviews.llvm.org/D50364.
• Guards have landed under https://reviews.llvm.org/D50501
• Invariant.Start finally landed as https://reviews.llvm.org/D51181.

Build off the approach pioneered in https://reviews.llvm.org/D46211, and apply the same reasoning to memory effects. Once we do this, we can hoist any intrinsic which has memory effects only for control flow modeling purposes (i.e. guards, assumes, invariant_start, and possibly others)

This needs a bunch of cleanup and likely some refactoring to LICM before landing. I'm posting it just so I don't forget where I was going.

[reames]

Just to note, the first piece of this has been split off in https://reviews.llvm.org/D50364. (assume handling)

Up next is invariant.start once that lands.

[reames]

All component pieces have been split and landed individually.

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"
bool llvm::hoistRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
   bool Changed = false;
   for (DomTreeNode *DTN : Worklist) {
     BasicBlock *BB = DTN->getBlock();
     // Only need to process the contents of this block if it is not part of a
     // 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;
+
+    // Similiarly, keep track of whether the prefix is readonly.  This is used
+    // when deciding to hoist a guard
+    bool IsReadOnly = 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)) {
         DEBUG(dbgs() << "LICM folding inst: " << I << "  --> " << *C << '\n');
for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
       }
 
       // Try hoisting the instruction out to the preheader.  We can only do
       // this if all of the operands of the instruction are loop invariant and
       // if it is safe to hoist the instruction.
       //
       if (CurLoop->hasLoopInvariantOperands(&I) &&
           canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, SafetyInfo, ORE) &&
+          (IsMustExecute ||
            isSafeToExecuteUnconditionally(
                I, DT, CurLoop, SafetyInfo, ORE,
-              CurLoop->getLoopPreheader()->getTerminator()))
+               CurLoop->getLoopPreheader()->getTerminator())))
+        Changed |= hoist(I, DT, CurLoop, SafetyInfo, ORE);
+
+      
+      // TODO: This really needs better factored before doing anything real
+      using namespace llvm::PatternMatch;
+      if (CurLoop->hasLoopInvariantOperands(&I) &&
+          IsMustExecute && IsReadOnly &&
+          match(&I,
+                m_Intrinsic<Intrinsic::experimental_guard>()))
         Changed |= hoist(I, DT, CurLoop, SafetyInfo, ORE);
+      if (CurLoop->hasLoopInvariantOperands(&I) &&
+          IsMustExecute && IsReadOnly &&
+          match(&I,
+                m_Intrinsic<Intrinsic::invariant_start>()) &&
+          I.use_empty())
+        Changed |= hoist(I, DT, CurLoop, SafetyInfo, ORE);
+      if (CurLoop->hasLoopInvariantOperands(&I) &&
+          IsMustExecute &&
+          match(&I,
+                m_Intrinsic<Intrinsic::assume>()))
+        Changed |= hoist(I, DT, CurLoop, SafetyInfo, ORE);
+
+      if (IsMustExecute)
+        IsMustExecute = isGuaranteedToTransferExecutionToSuccessor(&I);
+
+      if (IsReadOnly)
+        IsReadOnly = !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/LICM/preheader-safe.ll

 loop:                                         ; preds = %entry, %for.inc
   %x = load i64, i64* %xp
   %y = load i64, i64* %yp
   %div = udiv i64 %x, %y
   call void @use(i64 %div) readonly
   br label %loop
 }
 
+; Similiar to the above, but the hoistable instruction (%y in this case)
+; happens not to be the first instruction in the block.
+define void @throw_header_after_nonfirst(i64* %xp, i64* %yp, i1* %cond) {
+; CHECK-LABEL: throw_header_after_nonfirst
+; CHECK: %y = load i64, i64* %yp
+; CHECK-LABEL: loop
+; CHECK: %div = udiv i64 %x, %y
+; CHECK: call void @use(i64 %div)
+entry:
+  br label %loop
 
+loop:                                         ; preds = %entry, %for.inc
+  %iv = phi i64 [0, %entry], [%div, %loop]
+  %gep = getelementptr i64, i64* %xp, i64 %iv
+  %x = load i64, i64* %gep
+  %y = load i64, i64* %yp
+  %div = udiv i64 %x, %y
+  call void @use(i64 %div) readonly
+  br label %loop
+}
 
 ; Negative test
 define void @throw_header_before(i64 %x, i64 %y, i1* %cond) {
 ; CHECK-LABEL: throw_header_before
 ; CHECK-LABEL: loop
 ; CHECK: %div = udiv i64 %x, %y
 ; CHECK: call void @use(i64 %div)
 entry:
entry:
   br label %loop
 loop:                                         ; preds = %entry, %for.inc
   br label %loop-if
 loop-if:
   %div = udiv i64 %x, %y
   call void @use(i64 %div)
   br label %loop
 }
+
+declare void @llvm.experimental.guard(i1, ...)
+
+define void @guard_hoist(i1 %A) {
+; CHECK-LABEL: guard_hoist
+; CHECK-LABEL: loop
+; CHECK: call void @use(i64 %div)
+entry:
+  br label %loop
+
+loop:                                         ; preds = %entry, %for.inc
+  call void(i1, ...) @llvm.experimental.guard( i1 %A )[ "deopt"() ]
+  call void @use(i64 0)
+  br label %loop
+}