[LICM] Teach LICM to hoist conditional loads

[aemerson]

Summary

If the pointer operand of a load has been accessed by a load/store in a dominating block of the loop then it's safe to hoist.

[aemerson]

Whitespace fixes.

[mkuper]

This looks wrong.
In particular, it would break for something like:

a = *p;
free(p)
while (k) { // k is always false
 ... = *p;
}

We have llvm::isSafeToLoadUnconditionally() that does the domination check safely, but just checking that it's safe to load unconditionally in the pre-header may not be enough.

Consider something like:

a = *p;
while (k) {
  if (m) {
    free(p);
  }
  ... = *p;

}

Now, in those cases we shouldn't be hoisting regardless, because if p escapes, the value may not be loop-invariant.
But we need to make sure the patch doesn't break that, so additional tests may be needed.

[• dberlin]

lib/Transforms/Scalar/LICM.cpp

921

The DT queries are O(1), so i'm not sure what this buys you?

949

Domination does not guarantee execution.
It only guarantees that all paths that execute go through a given block before getting to another:

A
| \
B |
| /  
C

A dominates B and C, but only one of them will execute.

You want control dependence, and in particular, CDEQ sets, which divides blocks into equivalence classes where everything in the same equivalence class executes under the same set of conditions.

But you will find this is never going to be true for normal loops.

[aemerson]

In D35264#805566, @mkuper wrote:

This looks wrong.
In particular, it would break for something like:

a = *p;
free(p)
while (k) { // k is always false
 ... = *p;
}

We have llvm::isSafeToLoadUnconditionally() that does the domination check safely, but just checking that it's safe to load unconditionally in the pre-header may not be enough.

Consider something like:

a = *p;
while (k) {
  if (m) {
    free(p);
  }
  ... = *p;

}

Now, in those cases we shouldn't be hoisting regardless, because if p escapes, the value may not be loop-invariant.
But we need to make sure the patch doesn't break that, so additional tests may be needed.

Good points. The original intent of this patch was to hoist loads from more complicated loop nests, extending it to fully general conditional loads is too ambitious for the time I have so I'm going to drop this for now.

lib/Transforms/Scalar/LICM.cpp

921

According to GenericDomTree.h the dominates() routines have comments stating they're not constant time operations. Unless I'm looking in the wrong place?

949

In the context of this function checking for safety of complete unconditional execution I agree dominance isn't enough. The actual way this code seems to be used for loads is that it allows hoisting to the preheader of the loop, so not completely unconditional.

lib/Transforms/Scalar/LICM.cpp

static bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
   if (isa<LoadInst>(I))
     ++NumMovedLoads;
   else if (isa<CallInst>(I))
     ++NumMovedCalls;
   ++NumHoisted;
   return true;
 }
 
+/// Checks if the given load's pointer is dereferenceable on all paths to the
+/// loop preheader.
+static bool isLoadPtrDereferenceable(LoadInst *LI, const DominatorTree *DT,
+                                     const Loop *CurLoop) {
+  if (LI->isVolatile() || LI->isAtomic())
+    return false;
+
+  BasicBlock *PH = CurLoop->getLoopPreheader();
+  Value *Ptr = LI->getPointerOperand();
+
+  for (auto *PUser : Ptr->users()) {
+    if (isa<LoadInst>(PUser) || isa<StoreInst>(PUser)) {
+      Instruction *LSI = cast<Instruction>(PUser);
+      // For a common case of the pointer originating from the loop, avoid a DT
+      // query in favour of a densemap lookup.
+      if (CurLoop->contains(LSI->getParent()) ||
+          !DT->dominates(LSI->getParent(), PH))
+        continue;
+      // Since the block dominates the preheader, we know that execution must
+      // have transferred from the user's block to its successors.
+      return true;
+    }
+  }
+  return false;
+}
+
+
 /// Only sink or hoist an instruction if it is not a trapping instruction,
 /// or if the instruction is known not to trap when moved to the preheader.
 /// or if it is a trapping instruction and is guaranteed to execute.
 static bool isSafeToExecuteUnconditionally(Instruction &Inst,
                                            const DominatorTree *DT,
                                            const Loop *CurLoop,
                                            const LoopSafetyInfo *SafetyInfo,
                                            OptimizationRemarkEmitter *ORE,
                                            const Instruction *CtxI) {
   if (isSafeToSpeculativelyExecute(&Inst, CtxI, DT))
     return true;
 
   bool GuaranteedToExecute =
       isGuaranteedToExecute(Inst, DT, CurLoop, SafetyInfo);
 
   if (!GuaranteedToExecute) {
+    // Conditional loads may be hoisted if the address has already been accessed
+    // by a dominating block.
     auto *LI = dyn_cast<LoadInst>(&Inst);
+    if (LI && isLoadPtrDereferenceable(LI, DT, CurLoop))
+      return true;
+
     if (LI && CurLoop->isLoopInvariant(LI->getPointerOperand()))
       ORE->emit(OptimizationRemarkMissed(
                     DEBUG_TYPE, "LoadWithLoopInvariantAddressCondExecuted", LI)
                 << "failed to hoist load with loop-invariant address "
                    "because load is conditionally executed");
   }
 
   return GuaranteedToExecute;

test/Transforms/LICM/hoisting.ll

loop:
   %sum.next = add i32 %sel, %sum
   %indvar.next = add i32 %indvar, 1
   %cond = icmp slt i32 %indvar.next, %n
   br i1 %cond, label %loop, label %loopexit
 
 loopexit:
   ret i32 %sum
 }
+
+
+declare i32 @foo3(i32) nounwind readonly
+
+;; It is ok and desirable to hoist this load %B due to the load of %A.
+define i32 @test_cond_load(i1 %c, i1 %c2, i32* noalias %ptr, i32* noalias %storeptr) {
+; CHECK-LABEL: @test_cond_load(
+; CHECK: %A = load i32, i32* %ptr
+; CHECK: br label %Loop.ph
+; CHECK: %B = load i32, i32* %ptr
+; CHECK: br label %Loop
+; CHECK: Loop:
+entry:
+        %A = load i32, i32* %ptr
+        br label %Loop.ph
+
+Loop.ph:
+        br label %Loop
+
+Loop:
+        br i1 %c2, label %if.then, label %Loop.cont
+if.then:
+        %B = load i32, i32* %ptr
+        %res = call i32 @foo3(i32 %B)
+        store i32 %res, i32* %storeptr
+        br label %Loop.cont
+
+Loop.cont:
+        %res.phi = phi i32 [0, %Loop], [%res, %if.then]
+        br i1 %c, label %Loop, label %Out
+Out:
+        %C = sub i32 %A, %res.phi
+        ret i32 %C
+}