[WebAssembly] Fix handling of COPY instructions in WebAssemblyRegStackify.

Move RegStackify after coalescing and teach it to use LiveIntervals instead
of depending on SSA form. This avoids a problem where a register in a COPY
instruction is stackified and then subsequently coalesced with a register
that is not stackified.

This also puts it after the scheduler, which allows us to simplify the
EXPR_STACK constraint, as we no longer have instructions being reordered
after stackification and before coloring.

llvm-svn: 256402

4 files changed, 64 insertions, 58 deletions

diff --git a/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp b/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp
index 6ac53662359..e9671ee07e6 100644
--- a/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp
+++ b/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp
@@ -320,11 +320,12 @@ static void PlaceBlockMarker(MachineBasicBlock &MBB, MachineFunction &MF,
     // the BLOCK needs to be above the LOOP.
     InsertPos = Header->begin();
   } else {
-    // Otherwise, insert the BLOCK as late in Header as we can, but before any
-    // existing BLOCKs.
+    // Otherwise, insert the BLOCK as late in Header as we can, but before the
+    // beginning of the local expression tree and any nested BLOCKs.
     InsertPos = Header->getFirstTerminator();
     while (InsertPos != Header->begin() &&
-           prev(InsertPos)->getOpcode() == WebAssembly::BLOCK)
+           prev(InsertPos)->definesRegister(WebAssembly::EXPR_STACK) &&
+           prev(InsertPos)->getOpcode() != WebAssembly::LOOP)
       --InsertPos;
   }
 
diff --git a/llvm/lib/Target/WebAssembly/WebAssemblyInstrControl.td b/llvm/lib/Target/WebAssembly/WebAssemblyInstrControl.td
index 9a9468bb390..05efe890341 100644
--- a/llvm/lib/Target/WebAssembly/WebAssemblyInstrControl.td
+++ b/llvm/lib/Target/WebAssembly/WebAssemblyInstrControl.td
@@ -50,9 +50,13 @@ def TABLESWITCH_I64 : I<(outs), (ins I64:$index, bb_op:$default, variable_ops),
                         "tableswitch\t$index, $default">;
 } // isTerminator = 1, hasCtrlDep = 1, isBarrier = 1
 
-// Placemarkers to indicate the start of a block or loop scope.
+// Placemarkers to indicate the start of a block or loop scope. These
+// use/clobber EXPR_STACK to prevent them from being moved into the middle of
+// an expression tree.
+let Uses = [EXPR_STACK], Defs = [EXPR_STACK] in {
 def BLOCK     : I<(outs), (ins bb_op:$dst), [], "block   \t$dst">;
 def LOOP      : I<(outs), (ins bb_op:$dst), [], "loop    \t$dst">;
+} // Uses = [EXPR_STACK], Defs = [EXPR_STACK]
 
 // No-op to indicate to the AsmPrinter that a loop ends here, so a
 // basic block label is needed even if it wouldn't otherwise appear so.
diff --git a/llvm/lib/Target/WebAssembly/WebAssemblyRegStackify.cpp b/llvm/lib/Target/WebAssembly/WebAssemblyRegStackify.cpp
index 3a58826bd76..89ef5cdb2be 100644
--- a/llvm/lib/Target/WebAssembly/WebAssemblyRegStackify.cpp
+++ b/llvm/lib/Target/WebAssembly/WebAssemblyRegStackify.cpp
@@ -24,6 +24,7 @@
 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h" // for WebAssembly::ARGUMENT_*
 #include "WebAssemblyMachineFunctionInfo.h"
 #include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/Passes.h"
@@ -42,8 +43,12 @@ class WebAssemblyRegStackify final : public MachineFunctionPass {
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
     AU.addRequired<AAResultsWrapperPass>();
+    AU.addRequired<LiveIntervals>();
     AU.addPreserved<MachineBlockFrequencyInfo>();
+    AU.addPreserved<SlotIndexes>();
+    AU.addPreserved<LiveIntervals>();
     AU.addPreservedID(MachineDominatorsID);
+    AU.addPreservedID(LiveVariablesID);
     MachineFunctionPass::getAnalysisUsage(AU);
   }
 
@@ -61,59 +66,68 @@ FunctionPass *llvm::createWebAssemblyRegStackify() {
 }
 
 // Decorate the given instruction with implicit operands that enforce the
-// expression stack ordering constraints needed for an instruction which is
-// consumed by an instruction using the expression stack.
-static void ImposeStackInputOrdering(MachineInstr *MI) {
+// expression stack ordering constraints for an instruction which is on
+// the expression stack.
+static void ImposeStackOrdering(MachineInstr *MI) {
   // Write the opaque EXPR_STACK register.
   if (!MI->definesRegister(WebAssembly::EXPR_STACK))
     MI->addOperand(MachineOperand::CreateReg(WebAssembly::EXPR_STACK,
                                              /*isDef=*/true,
                                              /*isImp=*/true));
-}
-
-// Decorate the given instruction with implicit operands that enforce the
-// expression stack ordering constraints for an instruction which is on
-// the expression stack.
-static void ImposeStackOrdering(MachineInstr *MI, MachineRegisterInfo &MRI) {
-  ImposeStackInputOrdering(MI);
 
   // Also read the opaque EXPR_STACK register.
   if (!MI->readsRegister(WebAssembly::EXPR_STACK))
     MI->addOperand(MachineOperand::CreateReg(WebAssembly::EXPR_STACK,
                                              /*isDef=*/false,
                                              /*isImp=*/true));
-
-  // Also, mark any inputs to this instruction as being consumed by an
-  // instruction on the expression stack.
-  // TODO: Find a lighter way to describe the appropriate constraints.
-  for (MachineOperand &MO : MI->uses()) {
-    if (!MO.isReg())
-      continue;
-    unsigned Reg = MO.getReg();
-    if (!TargetRegisterInfo::isVirtualRegister(Reg))
-      continue;
-    MachineInstr *Def = MRI.getVRegDef(Reg);
-    if (Def->getOpcode() == TargetOpcode::PHI)
-      continue;
-    ImposeStackInputOrdering(Def);
-  }
 }
 
-// Test whether it's safe to move Def to just before Insert. Note that this
-// doesn't account for physical register dependencies, because WebAssembly
-// doesn't have any (other than special ones like EXPR_STACK).
+// Test whether it's safe to move Def to just before Insert.
 // 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) {
+                         AliasAnalysis &AA, LiveIntervals &LIS,
+                         MachineRegisterInfo &MRI) {
   assert(Def->getParent() == Insert->getParent());
   bool SawStore = false, SawSideEffects = false;
   MachineBasicBlock::const_iterator D(Def), I(Insert);
+
+  // Check for register dependencies.
+  for (const MachineOperand &MO : Def->operands()) {
+    if (!MO.isReg() || MO.isUndef())
+      continue;
+    unsigned Reg = MO.getReg();
+
+    // If the register is dead here and at Insert, ignore it.
+    if (MO.isDead() && Insert->definesRegister(Reg) &&
+        !Insert->readsRegister(Reg))
+      continue;
+
+    if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
+      // If the physical register is never modified, ignore it.
+      if (!MRI.isPhysRegModified(Reg))
+        continue;
+      // Otherwise, it's a physical register with unknown liveness.
+      return false;
+    }
+
+    // Ask LiveIntervals whether moving this virtual register use or def to
+    // Insert will change value numbers are seen.
+    const LiveInterval &LI = LIS.getInterval(Reg);
+    VNInfo *DefVNI = MO.isDef() ?
+        LI.getVNInfoAt(LIS.getInstructionIndex(Def).getRegSlot()) :
+        LI.getVNInfoBefore(LIS.getInstructionIndex(Def));
+    assert(DefVNI && "Instruction input missing value number");
+    VNInfo *InsVNI = LI.getVNInfoBefore(LIS.getInstructionIndex(Insert));
+    if (InsVNI && DefVNI != InsVNI)
+      return false;
+  }
+
+  // Check for memory dependencies and side effects.
   for (--I; I != D; --I)
     SawSideEffects |= I->isSafeToMove(&AA, SawStore);
-
   return !(SawStore && Def->mayLoad() && !Def->isInvariantLoad(&AA)) &&
          !(SawSideEffects && !Def->isSafeToMove(&AA, SawStore));
 }
@@ -127,8 +141,7 @@ bool WebAssemblyRegStackify::runOnMachineFunction(MachineFunction &MF) {
   MachineRegisterInfo &MRI = MF.getRegInfo();
   WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
   AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
-
-  assert(MRI.isSSA() && "RegStackify depends on SSA form");
+  LiveIntervals &LIS = getAnalysis<LiveIntervals>();
 
   // Walk the instructions from the bottom up. Currently we don't look past
   // block boundaries, and the blocks aren't ordered so the block visitation
@@ -154,19 +167,10 @@ bool WebAssemblyRegStackify::runOnMachineFunction(MachineFunction &MF) {
           continue;
 
         unsigned Reg = Op.getReg();
-        if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
-          // An instruction with a physical register. Conservatively mark it as
-          // an expression stack input so that it isn't reordered with anything
-          // in an expression stack which might use it (physical registers
-          // aren't in SSA form so it's not trivial to determine this).
-          // TODO: Be less conservative.
-          ImposeStackInputOrdering(Insert);
-          continue;
-        }
 
         // Only consider registers with a single definition.
         // TODO: Eventually we may relax this, to stackify phi transfers.
-        MachineInstr *Def = MRI.getVRegDef(Reg);
+        MachineInstr *Def = MRI.getUniqueVRegDef(Reg);
         if (!Def)
           continue;
 
@@ -198,26 +202,26 @@ bool WebAssemblyRegStackify::runOnMachineFunction(MachineFunction &MF) {
           continue;
 
         // For now, be conservative and don't look across block boundaries.
-        // TODO: Be more aggressive.
+        // TODO: Be more aggressive?
         if (Def->getParent() != &MBB)
           continue;
 
         // Don't move instructions that have side effects or memory dependencies
         // or other complications.
-        if (!IsSafeToMove(Def, Insert, AA))
+        if (!IsSafeToMove(Def, Insert, AA, LIS, MRI))
           continue;
 
         Changed = true;
         AnyStackified = true;
         // Move the def down and nest it in the current instruction.
-        MBB.insert(MachineBasicBlock::instr_iterator(Insert),
-                   Def->removeFromParent());
+        MBB.splice(Insert, &MBB, Def);
+        LIS.handleMove(Def);
         MFI.stackifyVReg(Reg);
-        ImposeStackOrdering(Def, MRI);
+        ImposeStackOrdering(Def);
         Insert = Def;
       }
       if (AnyStackified)
-        ImposeStackOrdering(&MI, MRI);
+        ImposeStackOrdering(&MI);
     }
   }
 
diff --git a/llvm/lib/Target/WebAssembly/WebAssemblyTargetMachine.cpp b/llvm/lib/Target/WebAssembly/WebAssemblyTargetMachine.cpp
index c774c120bb5..e31ea46de9f 100644
--- a/llvm/lib/Target/WebAssembly/WebAssemblyTargetMachine.cpp
+++ b/llvm/lib/Target/WebAssembly/WebAssemblyTargetMachine.cpp
@@ -165,12 +165,6 @@ void WebAssemblyPassConfig::addPreRegAlloc() {
 
   // Prepare store instructions for register stackifying.
   addPass(createWebAssemblyStoreResults());
-
-  // Mark registers as representing wasm's expression stack.
-  addPass(createWebAssemblyRegStackify());
-  // The register coalescing pass has a bad interaction with COPY MIs which have
-  // EXPR_STACK as an extra operand
-  // disablePass(&RegisterCoalescerID);
 }
 
 void WebAssemblyPassConfig::addPostRegAlloc() {
@@ -184,6 +178,9 @@ void WebAssemblyPassConfig::addPostRegAlloc() {
   // Fails with: should be run after register allocation.
   disablePass(&MachineCopyPropagationID);
 
+  // Mark registers as representing wasm's expression stack.
+  addPass(createWebAssemblyRegStackify());
+
   // Run the register coloring pass to reduce the total number of registers.
   addPass(createWebAssemblyRegColoring());