GVN-hoist: compute MSSA once per function (PR28670)

[sebpop]

Summary

With this patch we compute the MemorySSA once and update it in the code generator.
Passes make check-all and test-suite on x86_64-linux.

[• dberlin]

llvm/lib/Transforms/Scalar/GVNHoist.cpp

761 ↗

(On Diff #66152)

What do you mean here?
That either sounds like a bug in memssa, or something :)

770 ↗

(On Diff #66152)

Are you guaranteed that anything that conflicted with the old store conflicts with this store by your hoist safety rules?
(if not, you should only replace inMD's and phis, not memoryuses)

it might be worth either giving an example here, or adding a testcase.

The two problems are:

1 = MemoryDef<liveOnEntry>
store
2 = MemoryDef<1>
store

later
memoryphi(2, )

If the hoist point is 1, and you simply move the store, you will now have:
1 = MemoryDef<liveOnEntry>
store
3 = MemoryDef<1>
store
2 = MemoryDef<1>
store

later
memoryphi(2, )

This is wrong. 3 is now disconnected from the graph of reaching defs.

Additionally, if the hoist point is 2, you end up with:
1 = MemoryDef<liveOnEntry>
store
2 = MemoryDef<1>
store
3 = MemoryDef<1>
store

later
memoryphi(2, )

The memoryphi is now wrong (and you disconnected 2 from the reaching graph).

[sebpop]

llvm/lib/Transforms/Scalar/GVNHoist.cpp

761 ↗

(On Diff #66152)

My first patch had both MemUses and MemDefs handled in the same way.
I had a hard time finding how to get around this, so I would rather amend the MSSA to avoid other people getting through the same problems.
Let me think how to fix this in MSSA.

770 ↗

(On Diff #66152)

I added that comment above Def to make sure it is clear that hoisting guarantees these properties:

// The definition of this ld/st will not change: ld/st hoisting is
// legal when the ld/st is not moved past its current definition.
MemoryAccess *Def = OldMemAcc->getDefiningAccess();

hoist point is 1

Cannot happen: we cannot move the store "3" past store "2" as they are on the same chain (dependent.)
This is an illegal case of hoisting and will be discarded.

hoist point is 2

Cannot happen either as there is a use of "2" (the phi node) past which "3" cannot be moved.
Again the dependence analysis will discard this hoisting as invalid.

[sebpop]

Let me think how to fix this in MSSA.

I will probably need some help in reviewing those changes, or suggestions.
Thanks!

[sebpop]

It looks like the bug is because we do not update the block of a memory access: this patch fixes a crash where we were still referring to the block that used to contain an instruction that got hoisted.

--- a/llvm/lib/Transforms/Scalar/GVNHoist.cpp
+++ b/llvm/lib/Transforms/Scalar/GVNHoist.cpp
@@ -307,7 +307,8 @@ private:
 
     for (User *U : Def->users())
       if (auto *MU = dyn_cast<MemoryUse>(U)) {
-        BasicBlock *UBB = MU->getBlock();
+        // FIXME: MU->getBlock() does not get updated when we move the instruction.
+        BasicBlock *UBB = MU->getMemoryInst()->getParent();
         // Only analyze uses in BB.
         if (BB != UBB)
           continue;

Why not having a MemoryAccess contain a reference to the instruction itself when we have one, and for MemoryPhi nodes we could reference the BB in which they occur:

--- a/llvm/include/llvm/Transforms/Utils/MemorySSA.h
+++ b/llvm/include/llvm/Transforms/Utils/MemorySSA.h
@@ -167,7 +167,7 @@ protected:
 private:
   MemoryAccess(const MemoryAccess &);
   void operator=(const MemoryAccess &);
-  BasicBlock *Block;
+  Value *InstructionOrBlock;
 };
 
 template <>

[sebpop]

Updated patch does not pass ninja check as it regresses in terms of number of hoisted instructions.
It may be because the MSSA still contains references to the BBs that used to contain ld/st and the dependence analysis is not able to move the remaining ld/st past these "ghost" ld/st that have been already hoisted.

[• dberlin]

Oh, i see what you are trying to do.

MemorySSA is not actually part of the IR right now, so you can't use moveBefore :(
It has it's own access lists, etc.

As you say, it would not be enough to simply to change what it stores, there are places we keep the BB.

For now, the right thing to do is to call removeAccess on the instruction, call moveBefore on the IR, then createMemoryAccessAfter <hoistpt's memoryaccess>.
Then replaceAllUses with the newInstruction.

The real solution to making this not messy would be to make MemorySSA part of the IR.

I will push for that.

[• dberlin]

llvm/lib/Transforms/Scalar/GVNHoist.cpp

748 ↗

(On Diff #66187)

This will not work.
You have to removeAccess(Repl), then createMemoryAccessAfter (access for hoist point).

[sebpop]

Updated the patch as I first wrote it: I think this is the natural way to update an SSA variable.

This fails because when invoking:
+ MSSA->removeMemoryAccess(OldMemAcc);

we go from:
; MemoryUse(2)

%2 = load i32, i32* %v.addr, align 4

to no annotation at all:

%2 = load i32, i32* %v.addr, align 4

This is because removeMemoryAccess calls removeFromLookups which does:

Value *MemoryInst;
if (MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(MA)) {
  MemoryInst = MUD->getMemoryInst();
} else {
  MemoryInst = MA->getBlock();
}
ValueToMemoryAccess.erase(MemoryInst);

and erase() removes both the new and old MemoryAccess'es leaving the instruction without MSSA annotation.

For loads this can be fixed by first removing the OldMemoryAccess and then creating the NewMemoryAccess.
This works for loads because there are no users of a MemoryUse.
However for a store, we need to keep both the old and new MemoryAccess'es at the same time, to be able to rename the uses of old with new.

I think the solution would be for "MSSA->removeMemoryAccess(OldMemAcc);" to only invalidate and remove "OldMemAcc" without touching "NewMemAcc" that should remain attached to the instruction.

[sebpop]

Still has some problems of merging instruction annotations, and it does not seem to have issues with MSSA.

[sebpop]

Passes ninja check and test-suite on x86_64-linux.

[sebpop]

lib/Transforms/Scalar/GVNHoist.cpp

311 ↗

(On Diff #66217)

Note that if I remove this change there are tests in the test-suite that fail. I will reduce a testcase for this.

[• dberlin]

lib/Transforms/Scalar/GVNHoist.cpp

759 ↗

(On Diff #66217)

The comment is not correct for stores.
There are other requirements.
Imagine the following case:

A

\

B

/

C

C has load %p2
B has store %p2
A has store %p2.

You will have:

A:
 1 = MemoryDef(liveOnEntry)
  store %p2
B: 
  2 = MemoryDef(1)
  store %p2
C:
  3= MemoryPhi(1, 2)
  MemoryUse(3)
  load %p2

If you hoist the store in B to A, your code will give:

A:
 1 = MemoryDef(liveOnEntry)
  store %p2
 2 = MemoryDef(1)
  store %p2
B: 
  
C:
  3= MemoryPhi(1, 2)
  MemoryUse(3)

This is not correct, it should be MemoryPhi(2, 2) at worst, and in MemorySSA, we require you kill the phi.

code to do that:

MemoryAccess *SamePhiOp = nullptr;
for (auto &Op : Phi->incoming_values()) {
  if (!SamePhiOp)
    SamePhiOp = cast<MemoryAccess>(Op.get());
  else if (SamePhiOp != Op.get()) {
    SamePhiOp = nullptr;
    break;
  }
}
// If this has some value, it means all operands of the phi are now the
// same
if (SamePhiOp) {
  Phi->replaceAllUsesWith(SamePhiOp);
  MSSA->removeMemoryAccess(Phi);
}

Please make sure this happens, and use print-memoryssa to verify memoryssa is updated properly in testcases.

[sebpop]

Updated patch addressing all comments from Danny.
Passes check and llvm test-suite on x86_64-linux.

llvm/trunk/lib/Transforms/Scalar/GVNHoist.cpp

GVNHoist(DominatorTree *Dt, AliasAnalysis *Aa, MemoryDependenceResults *Md,
            bool OptForMinSize)
       : DT(Dt), AA(Aa), MD(Md), OptForMinSize(OptForMinSize),
         HoistingGeps(OptForMinSize), HoistedCtr(0) {}
   bool run(Function &F) {
     VN.setDomTree(DT);
     VN.setAliasAnalysis(AA);
     VN.setMemDep(MD);
     bool Res = false;
-
-    // FIXME: use lazy evaluation of VN to avoid the fix-point computation.
-    while (1) {
-      // FIXME: only compute MemorySSA once. We need to update the analysis in
-      // the same time as transforming the code.
-      MemorySSA M(F, AA, DT);
-      MSSA = &M;
 
+    // FIXME: use lazy evaluation of VN to avoid the fix-point computation.
+    while (1) {
       // Perform DFS Numbering of instructions.
       unsigned I = 0;
       for (const BasicBlock *BB : depth_first(&F.getEntryBlock()))
         for (auto &Inst: *BB)
           DFSNumber.insert({&Inst, ++I});
 
       auto HoistStat = hoistExpressions(F);
-      if (HoistStat.first + HoistStat.second == 0) {
+      if (HoistStat.first + HoistStat.second == 0)
         return Res;
-      }
-      if (HoistStat.second > 0) {
+
+      if (HoistStat.second > 0)
         // To address a limitation of the current GVN, we need to rerun the
-        // hoisting after we hoisted loads in order to be able to hoist all
-        // scalars dependent on the hoisted loads. Same for stores.
+        // hoisting after we hoisted loads or stores in order to be able to
+        // hoist all scalars dependent on the hoisted ld/st.
         VN.clear();
-      }
+
       Res = true;
 
       // DFS numbers change when instructions are hoisted: clear and recompute.
       DFSNumber.clear();
     }
 
     return Res;
   }
private:
   // Return true when there are users of Def in BB.
   bool hasMemoryUseOnPath(MemoryAccess *Def, const BasicBlock *BB,
                           const Instruction *OldPt) {
     const BasicBlock *DefBB = Def->getBlock();
     const BasicBlock *OldBB = OldPt->getParent();
 
     for (User *U : Def->users())
       if (auto *MU = dyn_cast<MemoryUse>(U)) {
-        BasicBlock *UBB = MU->getBlock();
+        // FIXME: MU->getBlock() does not get updated when we move the instruction.
+        BasicBlock *UBB = MU->getMemoryInst()->getParent();
         // Only analyze uses in BB.
         if (BB != UBB)
           continue;
 
         // A use in the same block as the Def is on the path.
         if (UBB == DefBB) {
           assert(MSSA->locallyDominates(Def, MU) && "def not dominating use");
           return true;
for (const HoistingPointInfo &HP : HPL) {
         // We can move Repl in HoistPt only when all operands are available.
         // When not HoistingGeps we need to copy the GEPs now.
         // The order in which hoistings are done may influence the availability
         // of operands.
         if (!allOperandsAvailable(Repl, HoistPt) && !HoistingGeps &&
             !makeGepOperandsAvailable(Repl, HoistPt, InstructionsToHoist))
           continue;
 
+        // Move the instruction at the end of HoistPt.
         Repl->moveBefore(HoistPt->getTerminator());
       }
 
+      MemoryAccess *NewMemAcc = nullptr;
+      if (MemoryAccess *MA = MSSA->getMemoryAccess(Repl)) {
+        if (MemoryUseOrDef *OldMemAcc = dyn_cast<MemoryUseOrDef>(MA)) {
+          // The definition of this ld/st will not change: ld/st hoisting is
+          // legal when the ld/st is not moved past its current definition.
+          MemoryAccess *Def = OldMemAcc->getDefiningAccess();
+          NewMemAcc = MSSA->createMemoryAccessInBB(Repl, Def, HoistPt,
+                                                   MemorySSA::End);
+          OldMemAcc->replaceAllUsesWith(NewMemAcc);
+          MSSA->removeMemoryAccess(OldMemAcc);
+        }
+      }
+
       if (isa<LoadInst>(Repl))
         ++NL;
       else if (isa<StoreInst>(Repl))
         ++NS;
       else if (isa<CallInst>(Repl))
         ++NC;
       else // Scalar
         ++NI;
for (const HoistingPointInfo &HP : HPL) {
             ++NumStoresRemoved;
           } else if (auto *ReplacementAlloca = dyn_cast<AllocaInst>(Repl)) {
             ReplacementAlloca->setAlignment(
                 std::max(ReplacementAlloca->getAlignment(),
                          cast<AllocaInst>(I)->getAlignment()));
           } else if (isa<CallInst>(Repl)) {
             ++NumCallsRemoved;
           }
+
+          if (NewMemAcc) {
+            // Update the uses of the old MSSA access with NewMemAcc.
+            MemoryAccess *OldMA = MSSA->getMemoryAccess(I);
+            OldMA->replaceAllUsesWith(NewMemAcc);
+            MSSA->removeMemoryAccess(OldMA);
+          }
+
           Repl->intersectOptionalDataWith(I);
           combineKnownMetadata(Repl, I);
           I->replaceAllUsesWith(Repl);
           I->eraseFromParent();
         }
+
+      // Remove MemorySSA phi nodes with the same arguments.
+      if (NewMemAcc) {
+        SmallPtrSet<MemoryPhi *, 4> UsePhis;
+        for (User *U : NewMemAcc->users())
+          if (MemoryPhi *Phi = dyn_cast<MemoryPhi>(U))
+            UsePhis.insert(Phi);
+
+        for (auto *Phi : UsePhis) {
+          auto In = Phi->incoming_values();
+          if (std::all_of(In.begin(), In.end(),
+                          [&](Use &U){return U == NewMemAcc;})) {
+            Phi->replaceAllUsesWith(NewMemAcc);
+            MSSA->removeMemoryAccess(Phi);
+          }
+        }
+      }
     }
 
     NumHoisted += NL + NS + NC + NI;
     NumRemoved += NR;
     NumLoadsHoisted += NL;
     NumStoresHoisted += NS;
     NumCallsHoisted += NC;
     return {NI, NL + NC + NS};

llvm/trunk/test/Transforms/GVN/hoist-mssa.ll

+; RUN: opt -S -gvn-hoist < %s | FileCheck %s
+
+; Check that store hoisting works: there should be only one store left.
+; CHECK-LABEL: @getopt
+; CHECK: store i32
+; CHECK-NOT: store i32
+
+@optind = external global i32, align 4
+
+define void @getopt() {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb
+  br i1 undef, label %bb2, label %bb3
+
+bb2:                                              ; preds = %bb1
+  br label %bb13
+
+bb3:                                              ; preds = %bb1
+  br i1 undef, label %bb4, label %bb9
+
+bb4:                                              ; preds = %bb3
+  %tmp = load i32, i32* @optind, align 4
+  br i1 undef, label %bb5, label %bb7
+
+bb5:                                              ; preds = %bb4
+  %tmp6 = add nsw i32 %tmp, 1
+  store i32 %tmp6, i32* @optind, align 4
+  br label %bb12
+
+bb7:                                              ; preds = %bb4
+  %tmp8 = add nsw i32 %tmp, 1
+  store i32 %tmp8, i32* @optind, align 4
+  br label %bb13
+
+bb9:                                              ; preds = %bb3
+  %tmp10 = load i32, i32* @optind, align 4
+  %tmp11 = add nsw i32 %tmp10, 1
+  store i32 %tmp11, i32* @optind, align 4
+  br label %bb12
+
+bb12:                                             ; preds = %bb9, %bb5
+  br label %bb13
+
+bb13:                                             ; preds = %bb12, %bb7, %bb2
+  ret void
+}
+
+@GlobalVar = internal global float 1.000000e+00
+
+; Check that we hoist stores and remove the MSSA phi node.
+; CHECK-LABEL: @hoistStoresUpdateMSSA
+; CHECK: store float
+; CHECK-NOT: store float
+define float @hoistStoresUpdateMSSA(float %d) {
+entry:
+  store float 0.000000e+00, float* @GlobalVar
+  %cmp = fcmp oge float %d, 0.000000e+00
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  store float 0.000000e+00, float* @GlobalVar
+  br label %if.end
+
+if.end:
+  %tmp = load float, float* @GlobalVar, align 4
+  ret float %tmp
+}