Hoist load based on alias analysis

[delena]

Summary

I use alias analysis to define whether the given instruction is a barrier for load hoisting.
When I find 2 identical loads, I check all preceding instructions in the both basic blocks.
I'll also look at sinking stores in the next patch.

[hfinkel]

As a general note, please upload patches with full context, see: http://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface

lib/Transforms/Scalar/MergedLoadStoreMotion.cpp

270

This is not really sufficient, we also need to check the other possible Load flags (atomic properties, volatile, alignment). This is easy to do:

Load0->isSameOperationAs(Load1)

(it looks like this is all guarded on a check that the load isSimple, so we know the atomic properties and volatile are a non-issue, but the alignment still needs checking ).

Also, this line has a typo, (Load0->getType() == Load0->getType()) is always true.

test/Transforms/InstMerge/ld_hoist1.ll

19

I think these checks could be more specific. I think you can explicitly match the first gep and load and then match the second get (picking up the name by regex) but specifying the form, and then making sure the second load uses that address.

64

Remove unnecessary attributes.

68

Remove unnecessary metadata.

[delena]

I followed Hal's comments and used IsIndenticalToWhenDefefined() - the same interface is used in SimplifyCFG.
isSameOperationAs() does the same with some excluded flags.
I also did all other suggested changes.

Thanks.

[Gerolf]

Does the new implementation catch any cases the old one didn't? There is extra cost by walking the range of instruction twice, and perhaps a small change would have the same effect.

lib/Transforms/Scalar/MergedLoadStoreMotion.cpp

265

Typo. Did you mean IsIdenticalToDefined()? Or IsIdendicalLoad()?

267

Are you checking the range for load0 twice? See overall comment.

371

The optimization should work when one load is used outside the block. The optimization can work when both loads are used outside but we have to deal with the PHI nodes accordingly.

[delena]

Does the new implementation catch any cases the old one didn't? There is extra cost by walking the range of instruction twice, and perhaps a small change would have the same effect.

[Demikhovsky, Elena] Exactly, not every store is a barrier for load hoisting. I check this with AliasAnalysis. I attached a test case where it works.

lib/Transforms/Scalar/MergedLoadStoreMotion.cpp

265

IsIdenticalToDefined is a standard function to compare 2 instructions.

267

No. I check only once for each load. I can't say that instruction is a barrier before I see the load itself. Because I go back from bb start to the current instruction, I do it after I see two identical loads.

371

I did not change the current behavior in this case, but I plan to work more on these optimizations. Conditional load/store are barriers for vectorizer.

[hfinkel]

lib/Transforms/Scalar/MergedLoadStoreMotion.cpp

265

The old code used AA and checked for a MustAlias result. The new code is just checking operand quality, this makes the check less powerful. Please keep the original form of the check *using MustAlias) and use isSameOperationAs as I had suggested.

The problem is that, on either side of the diamond, you could have address-equivalent but type-inequivalent GEPs. BasicAA can easily show that the resulting offset is the same, but they'll never really be hoisted (I can't say how common this is, and I presume that we don't have a regression test for it, but let's not reduce our capability to handle that situation here).

[delena]

The problem is that, on either side of the diamond, you could have address-equivalent but type-inequivalent GEPs. BasicAA can easily show that the resulting offset is the same, but they'll never really be hoisted (I can't say how common this is, and I presume that we don't have a regression test for it, but let's not reduce our capability to handle that situation here).

I checked the following code:

int *iin = (int *)in;
if (trigger[i] > 0) {

out[i] = in[i] + (float) 0.5;

}
else {

out[i] /= 3;
iout[i] += iin[i];

}
And tried to hoist loading in[i]. isSameOperationAs() filters it out because the types are different.

I uploaded the new diff anyway.

[hfinkel]

And tried to hoist loading in[i]. isSameOperationAs() filters it out because the types are different.

Understood, thanks for checking. When dealing with C++ classes, etc. there are a lot of bitcasts flying around, and I did not want to change behavior here without knowing what we might regress. We probably should handle the "one side will need a bitcast" case, but that is a separate issue.

LGTM, thanks!

[Gerolf]

Please see below. I still think the compile-time concern needs more attention. Ignoring that the patch LGTM.

[delena]

Thank you. Committed revision 221091.

I still think the compile-time concern needs more attention.

I do this check only after I see 2 identical loads. The alternative is checking barriers for every Load0 before I know that I have a candidate for hoisting in the second block.

Btw, SimplifyCFG() does half way by hoisting identical instructions from diamond, but we do load hoisting in a separate pass. Here I have a compile-time concern.
The same about store sinking.

• Elena

lib/Transforms/Scalar/MergedLoadStoreMotion.cpp

   BasicBlock *getDiamondTail(BasicBlock *BB);
   bool isDiamondHead(BasicBlock *BB);
   // Routines for hoisting loads
-  bool isLoadHoistBarrier(Instruction *Inst);
+  bool isLoadHoistBarrierInRange(const Instruction& Start,
+                                 const Instruction& End,
+                                 LoadInst* LI);
   LoadInst *canHoistFromBlock(BasicBlock *BB, LoadInst *LI);
   void hoistInstruction(BasicBlock *BB, Instruction *HoistCand,
                         Instruction *ElseInst);

 /// being loaded or protect against the load from happening
 /// it is considered a hoist barrier.
 ///
-bool MergedLoadStoreMotion::isLoadHoistBarrier(Instruction *Inst) {
-  // FIXME: A call with no side effects should not be a barrier.
-  // Aren't all such calls covered by mayHaveSideEffects() below?
-  // Then this check can be removed.
-  if (isa<CallInst>(Inst))
-    return true;
-  if (isa<TerminatorInst>(Inst))
-    return true;
-  // FIXME: Conservatively let a store instruction block the load.
-  // Use alias analysis instead.
-  if (isa<StoreInst>(Inst))
-    return true;
-  // Note: mayHaveSideEffects covers all instructions that could
-  // trigger a change to state. Eg. in-flight stores have to be executed
-  // before ordered loads or fences, calls could invoke functions that store
-  // data to memory etc.
-  if (Inst->mayHaveSideEffects()) {
-    return true;
-  }
-  DEBUG(dbgs() << "No Hoist Barrier\n");
-  return false;
+
+bool MergedLoadStoreMotion::isLoadHoistBarrierInRange(const Instruction& Start, 
+                                                      const Instruction& End,
+                                                      LoadInst* LI) {
+  AliasAnalysis::Location Loc = AA->getLocation(LI);
+  return AA->canInstructionRangeModify(Start, End, Loc);
 }
 
 ///

 /// and it can be hoisted from \p BB, return that load.
 /// Otherwise return Null.
 ///
-LoadInst *MergedLoadStoreMotion::canHoistFromBlock(BasicBlock *BB,
-                                                   LoadInst *LI) {
-  LoadInst *I = nullptr;
-  assert(isa<LoadInst>(LI));
-  if (LI->isUsedOutsideOfBlock(LI->getParent()))
-    return nullptr;
+LoadInst *MergedLoadStoreMotion::canHoistFromBlock(BasicBlock *BB1,
+                                                   LoadInst *Load0) {
 
-  for (BasicBlock::iterator BBI = BB->begin(), BBE = BB->end(); BBI != BBE;
+  for (BasicBlock::iterator BBI = BB1->begin(), BBE = BB1->end(); BBI != BBE;
        ++BBI) {
     Instruction *Inst = BBI;
 
     // Only merge and hoist loads when their result in used only in BB
-    if (isLoadHoistBarrier(Inst))
-      break;
     if (!isa<LoadInst>(Inst))
       continue;
-    if (Inst->isUsedOutsideOfBlock(Inst->getParent()))
+    if (Inst->isUsedOutsideOfBlock(BB1))
       continue;
 
-    AliasAnalysis::Location LocLI = AA->getLocation(LI);
-    AliasAnalysis::Location LocInst = AA->getLocation((LoadInst *)Inst);
-    if (AA->isMustAlias(LocLI, LocInst) && LI->getType() == Inst->getType()) {
-      I = (LoadInst *)Inst;
-      break;
+    LoadInst *Load1 = dyn_cast<LoadInst>(Inst);
+    BasicBlock *BB0 = Load0->getParent();
+    AliasAnalysis::Location LocLoad0 = AA->getLocation(Load0);
+    AliasAnalysis::Location LocLoad1 = AA->getLocation(Load1);
+    if (AA->isMustAlias(LocLoad0, LocLoad1) &&
+        Load0->getType() == Load0->getType() &&
+        !isLoadHoistBarrierInRange(BB1->front(), *Load1, Load1) &&
+        !isLoadHoistBarrierInRange(BB0->front(), *Load0, Load0)) {
+      return Load1;
     }
   }
-  return I;
+  return nullptr;
 }
 
 ///

 
     Instruction *I = BBI;
     ++BBI;
-    if (isLoadHoistBarrier(I))
-      break;
 
     // Only move non-simple (atomic, volatile) loads.
     if (!isa<LoadInst>(I))
       continue;
 
     LoadInst *L0 = (LoadInst *)I;
-    if (!L0->isSimple())
+    if (!L0->isSimple() || L0->isUsedOutsideOfBlock(Succ0))
       continue;
 
     ++NLoads;

test/Transforms/InstMerge/ld_hoist1.ll

+; Test load hoist
+; RUN: opt -basicaa -memdep -mldst-motion -S < %s | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-pc_linux"
+
+; Function Attrs: nounwind uwtable
+define float* @_Z3fooPiPfjS_(i32* noalias nocapture readonly %in, float* noalias %out, i32 %size, i32* nocapture readonly %trigger) #0 {
+entry:
+  %cmp11 = icmp eq i32 %size, 0
+  br i1 %cmp11, label %for.end, label %for.body.lr.ph
+
+for.body.lr.ph:                                   ; preds = %entry
+  %0 = add i32 %size, -1
+  br label %for.body
+
+; CHECK-LABEL: for.body
+; CHECK load
+; CHECK getelementptr inbounds i32* %in
+; CHECK load
+for.body:                                         ; preds = %for.body.lr.ph, %for.inc
+  %indvars.iv = phi i64 [ 0, %for.body.lr.ph ], [ %indvars.iv.next, %for.inc ]
+  %arrayidx = getelementptr inbounds i32* %trigger, i64 %indvars.iv
+  %1 = load i32* %arrayidx, align 4
+  %cmp1 = icmp sgt i32 %1, 0
+  br i1 %cmp1, label %if.then, label %if.else
+
+; CHECK-LABEL: if.then
+if.then:                                          ; preds = %for.body
+; This load should be hoisted
+  %arrayidx3 = getelementptr inbounds i32* %in, i64 %indvars.iv
+  %2 = load i32* %arrayidx3, align 4
+  %conv = sitofp i32 %2 to float
+  %add = fadd float %conv, 5.000000e-01
+  %arrayidx5 = getelementptr inbounds float* %out, i64 %indvars.iv
+  store float %add, float* %arrayidx5, align 4
+  br label %for.inc
+
+if.else:                                          ; preds = %for.body
+  %arrayidx7 = getelementptr inbounds float* %out, i64 %indvars.iv
+  %3 = load float* %arrayidx7, align 4
+  %div = fdiv float %3, 3.000000e+00
+  store float %div, float* %arrayidx7, align 4
+; This load should be hoisted in spite of store 
+  %arrayidx9 = getelementptr inbounds i32* %in, i64 %indvars.iv
+  %4 = load i32* %arrayidx9, align 4
+  %conv10 = sitofp i32 %4 to float
+  %add13 = fadd float %div, %conv10
+  store float %add13, float* %arrayidx7, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.then, %if.else
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv to i32
+  %exitcond = icmp ne i32 %lftr.wideiv, %0
+  br i1 %exitcond, label %for.body, label %for.cond.for.end_crit_edge
+
+for.cond.for.end_crit_edge:                       ; preds = %for.inc
+  br label %for.end
+
+for.end:                                          ; preds = %entry, %for.cond.for.end_crit_edge
+  ret float* %out
+}
+
+attributes #0 = { nounwind uwtable "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
+
+!llvm.ident = !{!0}
+
+!0 = metadata !{metadata !"clang version 3.6.0 (219111)"}