[WebAssembly] Fix dominance check for PHIs in the StoreResult pass

[sunfish]

Summary

When a block has no terminator instructions, getFirstTerminator() returns end(), which can't be used in dominance checks. Check dominance for phi operands separately.

Also, remove some bits from WebAssemblyRegStackify.cpp that were causing trouble on the same testcase; they were left behind from an earlier experiment.

[dschuff]

otherwise LGTM

lib/Target/WebAssembly/WebAssemblyStoreResults.cpp

95 ↗

(On Diff #41805)

I don't really understand what this arithmetic on the MachineOperands actually means.
I guess it's just trying to find which operand on Where is the use of MI.

Actually there's also nothing that explicitly says what the pass even does.
IIUC we are attempting to find uses of the stored value and make them uses of the result of the store instead (which we can do if the store dominates the use), so maybe it should say that somewhere.

test/CodeGen/WebAssembly/store-results.ll

26 ↗

(On Diff #41805)

could this maybe say what the nature of the corner case is for each of these functions?

[sunfish]

Thanks!

lib/Target/WebAssembly/WebAssemblyStoreResults.cpp

95 ↗

(On Diff #41805)

Yes, it's computing the block paired with a use in the phi. I expanded the comment.

The comment at the top of the file describes what this pass does, but it was pretty terse. I expanded it now.

test/CodeGen/WebAssembly/store-results.ll

26 ↗

(On Diff #41805)

I expanded the comment describing these tests.

llvm/trunk/lib/Target/WebAssembly/WebAssemblyRegStackify.cpp

 // doesn't account for physical register dependencies, because WebAssembly
 // doesn't have any (other than special ones like EXPR_STACK).
 // TODO: Compute memory dependencies in a way that doesn't require always
 // walking the block.
 // TODO: Compute memory dependencies in a way that uses AliasAnalysis to be
 // more precise.
 static bool IsSafeToMove(const MachineInstr *Def, const MachineInstr *Insert,
                          AliasAnalysis &AA) {
+  assert(Def->getParent() == Insert->getParent());
   bool SawStore = false, SawSideEffects = false;
   MachineBasicBlock::const_iterator D(Def), I(Insert);
   for (--I; I != D; --I)
     SawSideEffects |= I->isSafeToMove(&AA, SawStore);
 
   return !(SawStore && Def->mayLoad() && !Def->isInvariantLoad(&AA)) &&
          !(SawSideEffects && !Def->isSafeToMove(&AA, SawStore));
 }
for (MachineInstr &MI : reverse(MBB)) {
         // Argument instructions represent live-in registers and not real
         // instructions.
         if (Def->getOpcode() == WebAssembly::ARGUMENT_I32 ||
             Def->getOpcode() == WebAssembly::ARGUMENT_I64 ||
             Def->getOpcode() == WebAssembly::ARGUMENT_F32 ||
             Def->getOpcode() == WebAssembly::ARGUMENT_F64)
           continue;
 
-        // Single-use expression trees require defs that have one use, or that
-        // they be trivially clonable.
+        // Single-use expression trees require defs that have one use.
         // TODO: Eventually we'll relax this, to take advantage of set_local
         // returning its result.
         if (!MRI.hasOneUse(Reg))
           continue;
 
-        // For now, be conservative and don't look across block boundaries,
-        // unless we have something trivially clonable.
+        // For now, be conservative and don't look across block boundaries.
         // TODO: Be more aggressive.
-        if (Def->getParent() != &MBB && !Def->isMoveImmediate())
+        if (Def->getParent() != &MBB)
           continue;
 
         // Don't move instructions that have side effects or memory dependencies
         // or other complications.
         if (!IsSafeToMove(Def, Insert, AA))
           continue;
 
         Changed = true;

llvm/trunk/lib/Target/WebAssembly/WebAssemblyStoreResults.cpp

 //===-- WebAssemblyStoreResults.cpp - Optimize using store result values --===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
 /// \brief This file implements an optimization pass using store result values.
 ///
-/// WebAssembly's store instructions return the stored value, specifically to
-/// enable the optimization of reducing get_local/set_local traffic, which is
-/// what we're doing here.
+/// WebAssembly's store instructions return the stored value. This is to enable
+/// an optimization wherein uses of the stored value can be replaced by uses of
+/// the store's result value, making the stored value register more likely to
+/// be single-use, thus more likely to be useful to register stackifying, and
+/// potentially also exposing the store to register stackifying. These both can
+/// reduce get_local/set_local traffic.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "WebAssembly.h"
 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
 #include "WebAssemblyMachineFunctionInfo.h"
 #include "WebAssemblySubtarget.h"
 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
for (auto &MI : MBB)
       case WebAssembly::STORE_F64:
       case WebAssembly::STORE_I32:
       case WebAssembly::STORE_I64:
         unsigned ToReg = MI.getOperand(0).getReg();
         unsigned FromReg = MI.getOperand(2).getReg();
         for (auto I = MRI.use_begin(FromReg), E = MRI.use_end(); I != E;) {
           MachineOperand &O = *I++;
           MachineInstr *Where = O.getParent();
-          if (Where->getOpcode() == TargetOpcode::PHI)
-            Where = Where->getOperand(&O - &Where->getOperand(0) + 1)
-                        .getMBB()
-                        ->getFirstTerminator();
+          if (Where->getOpcode() == TargetOpcode::PHI) {
+            // PHIs use their operands on their incoming CFG edges rather than
+            // in their parent blocks. Get the basic block paired with this use
+            // of FromReg and check that MI's block dominates it.
+            MachineBasicBlock *Pred =
+                Where->getOperand(&O - &Where->getOperand(0) + 1).getMBB();
+            if (!MDT.dominates(&MBB, Pred))
+              continue;
+          } else {
+            // For a non-PHI, check that MI dominates the instruction in the
+            // normal way.
             if (&MI == Where || !MDT.dominates(&MI, Where))
               continue;
-          DEBUG(dbgs() << "Setting operand " << O << " in " << *Where <<
-                " from " << MI <<"\n");
+          }
+          DEBUG(dbgs() << "Setting operand " << O << " in " << *Where
+                       << " from " << MI << "\n");
           O.setReg(ToReg);
         }
       }
   }
 
   return true;
 }

llvm/trunk/test/CodeGen/WebAssembly/store-results.ll

 ; CHECK: i32.const $push{{[0-9]+}}=, 0
 ; CHECK: i32.store $push[[STORE:[0-9]+]]=, $0, $pop{{[0-9]+}}
 ; CHECK: return $pop[[STORE]]{{$}}
 define i32 @single_block(i32* %p) {
 entry:
   store i32 0, i32* %p
   ret i32 0
 }
+
+; Test interesting corner cases for wasm-store-results, in which the operand of
+; a store ends up getting used by a phi, which needs special handling in the
+; dominance test, since phis use their operands on their incoming edges.
+
+%class.Vec3 = type { float, float, float }
+
+@pos = global %class.Vec3 zeroinitializer, align 4
+
+; CHECK-LABEL: foo:
+; CHECK: i32.store $discard=, $pop0, $0
+define void @foo() {
+for.body.i:
+  br label %for.body5.i
+
+for.body5.i:
+  %i.0168.i = phi i32 [ 0, %for.body.i ], [ %inc.i, %for.body5.i ]
+  %conv6.i = sitofp i32 %i.0168.i to float
+  store volatile float 0.0, float* getelementptr inbounds (%class.Vec3, %class.Vec3* @pos, i32 0, i32 0)
+  %inc.i = add nuw nsw i32 %i.0168.i, 1
+  %exitcond.i = icmp eq i32 %inc.i, 256
+  br i1 %exitcond.i, label %for.cond.cleanup4.i, label %for.body5.i
+
+for.cond.cleanup4.i:
+  ret void
+}
+
+; CHECK-LABEL: bar:
+; CHECK: i32.store $discard=, $0, $pop0
+define void @bar() {
+for.body.i:
+  br label %for.body5.i
+
+for.body5.i:
+  %i.0168.i = phi float [ 0.0, %for.body.i ], [ %inc.i, %for.body5.i ]
+  store volatile float 0.0, float* getelementptr inbounds (%class.Vec3, %class.Vec3* @pos, i32 0, i32 0)
+  %inc.i = fadd float %i.0168.i, 1.0
+  %exitcond.i = fcmp oeq float %inc.i, 256.0
+  br i1 %exitcond.i, label %for.cond.cleanup4.i, label %for.body5.i
+
+for.cond.cleanup4.i:
+  ret void
+}