[LICM] Compute a must execute property for the prefix of the header as we go

[reames]

Summary

Computing this property within the existing walk ensures that the cost is linear with the size of the block. If we did this from within isGuaranteedToExecute, it would be quadratic without some very fancy caching.

This allows us to reliably catch a hoistable instruction within a header which may throw at some point *after* our hoistable instruction. It doesn't do anything for non-header cases, but given how common single block loops are, this seems very worthwhile.

(The rest of this is not part of the commit message, just recording ideas.)

Given this, we could expand in a couple of directions:

• special case a guard which is known not to be taken on the first iteration of the loop
• support hoisting of guards themselves if we compute an extra IsPrefixReadOnly property as we go.
• I'm seriously considering keeping around the set of loop blocks with implicit control flow in LoopSafetyInfo. Doing so would let us apply a variation of the exit logic combined with this prefix property to handle non-header cases as well.

[mkazantsev]

LGTM once comments are addressed.

lib/Transforms/Scalar/LICM.cpp

490

Here we create some instructions. I think all of them are fine, but doesn't it make sense to assert that each of them transfers execution to successor? Just in case this logic ever changes.

508

If hoist was successful, we don't actually need to make isGuaranteedToTransferExecutionToSuccessor check on the instruction that is no longer in this block. Maybe replace with assert in this case?

[reames]

lib/Transforms/Scalar/LICM.cpp

508

I need to add a continue after the hoist. (In theory, we hoist instructions that aren't guaranteed to transfer control to their successors - we don't today, but might.) Will fix.

[reames]

Committed revision 331557.

lib/Transforms/Scalar/LICM.cpp

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;
+
     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;) {
         auto ReciprocalDivisor = BinaryOperator::CreateFDiv(One, Divisor);
         ReciprocalDivisor->setFastMathFlags(I.getFastMathFlags());
         ReciprocalDivisor->insertBefore(&I);
 
         auto Product =
             BinaryOperator::CreateFMul(I.getOperand(0), ReciprocalDivisor);
         Product->setFastMathFlags(I.getFastMathFlags());
         Product->insertAfter(&I);
         I.replaceAllUsesWith(Product);
         I.eraseFromParent();
 
         hoist(*ReciprocalDivisor, DT, CurLoop, SafetyInfo, ORE);
         Changed = true;
         continue;
       }
 
       // 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);
+
+      if (IsMustExecute)
+        IsMustExecute = isGuaranteedToTransferExecutionToSuccessor(&I);
     }
   }
 
   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: