[WebAssembly] Fix debug_value's when registers are stackified.

[aardappel]

Summary

This is a WiP for review, missing tests etc.

[aardappel]

Uploading this for early feedback to see if this goes the right direction.

This correctly outputs a DW_AT_location of the correct type TI_OPERAND_STACK where previously there was nothing being output at all (because the debug_value referred to an orphan register). Only tested for the simplest case of one def + one use.

Besides tests, this does not update the PC range, which is currently incorrect. The range should probably just be shrunk to exactly the PC just between the def and use.

Also entirely not sure if my calls to replaceWithStackOffset are a) operating on the correct debug_values and b) have the correct stack offset. This in particular needs tests. Anyone familiar with WebAssemblyRegStackify would love to hear if you think I am capturing the various cases correctly. Also one case where we un-stackify.

[aheejin]

There are many places that calls MFI.stackifyVReg. I guess we should handle them too? Not very sure if it'll be easy to compute stack offset in all those cases though.

llvm/lib/Target/WebAssembly/WebAssemblyDebugValueManager.cpp

22

IIRC this WebAssemblyDebugValueManager class was first written when we didn't have multivalue defs, so I think this class needs to be extended to handle multivalue defs. For a multivalue instruction, in theory each of defs can have different stack status, for example,

r1, r2, r3 = some_call(...);

In this instruction, it is possible that only r1 is stackified and r2 and r3 are not. So maybe this class now needs to take not only a MachineInstr but also a def register or def index or something. Also this MachineInstr::collectDebugValues does not seem to handle multiple def registers either, so we might need to fix this first.

61

Is this function used to mark an instruction as a register before it is marked as a local in ExplicitLocals? If so maybe a comment saying this register marking is tentative would be good.

llvm/lib/Target/WebAssembly/WebAssemblyRegStackify.cpp

709

I don't think Worklist.size() is the depth of the stack. Worklist contains not MachineOperands but ranges. Each range contains multiple MachineOperands. So you have to count MachineOperands in each of ranges within Worklist.

951

I think this needs to be handled per def register (within a possibly multi-def instruction). Related to the comment in WebAssemblyDebugValueManager.

[aardappel]

@aheejin thanks for the comments! As you say, given that stackifying happens across multiple passes, it may be that the approach here is going to be too clumsy/fragile. I am going to first see if a solution that works at or just before MC lowering can work instead, that way all the stackifying changes can remain as they are.

llvm/lib/Target/WebAssembly/WebAssemblyDebugValueManager.cpp

22

Ah yes, hadn't thought of multivalue :( Though maybe its worth adding multi-value support in a separate CL.

61

No, it is used to change a register that was changed to a stack value back to a register. Hopefully its not necessary.

llvm/lib/Target/WebAssembly/WebAssemblyRegStackify.cpp

709

I did think about this and somehow thought it was equivalent. Will check if I revisit.

[aardappel]

This patch abandoned in favor of the approach in https://reviews.llvm.org/D79428

llvm/lib/Target/WebAssembly/WebAssembly.h

 void initializeWebAssemblyPeepholePass(PassRegistry &);
 
 namespace WebAssembly {
 enum TargetIndex {
   // Followed by a local index (ULEB).
   TI_LOCAL,
   // Followed by an absolute global index (ULEB). DEPRECATED.
   TI_GLOBAL_FIXED,
+  // Followed by an index relative to the bottom of the stack
+  // (for this function).
   TI_OPERAND_STACK,
   // Followed by a compilation unit relative global index (uint32_t)
   // that will have an associated relocation.
   TI_GLOBAL_RELOC
 };
 } // end namespace WebAssembly
 
 } // end namespace llvm
 
 #endif

llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

 /// WebAssembly, provided that all loops are single-entry.
 ///
 /// In case we use exceptions, this pass also fixes mismatches in unwind
 /// destinations created during transforming CFG into wasm structured format.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "WebAssembly.h"
+#include "WebAssemblyDebugValueManager.h"
 #include "WebAssemblyExceptionInfo.h"
 #include "WebAssemblyMachineFunctionInfo.h"
 #include "WebAssemblySubtarget.h"
 #include "WebAssemblyUtilities.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
static void unstackifyVRegsUsedInSplitBB(MachineBasicBlock &MBB,
                                          MachineBasicBlock &Split,
                                          WebAssemblyFunctionInfo &MFI,
                                          MachineRegisterInfo &MRI) {
   for (auto &MI : Split) {
     for (auto &MO : MI.explicit_uses()) {
       if (!MO.isReg() || Register::isPhysicalRegister(MO.getReg()))
         continue;
       if (MachineInstr *Def = MRI.getUniqueVRegDef(MO.getReg()))
-        if (Def->getParent() == &MBB)
+        if (Def->getParent() == &MBB) {
           MFI.unstackifyVReg(MO.getReg());
+          WebAssemblyDebugValueManager(Def).replaceWithRegister(MO);
+        }
     }
   }
 }
 
 bool WebAssemblyCFGStackify::fixUnwindMismatches(MachineFunction &MF) {
   const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
   auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
   MachineRegisterInfo &MRI = MF.getRegInfo();

llvm/lib/Target/WebAssembly/WebAssemblyDebugValueManager.h

 /// manager for DebugValues associated with the specific MachineInstr.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_LIB_TARGET_WEBASSEMBLY_WEBASSEMBLYDEBUGVALUEMANAGER_H
 #define LLVM_LIB_TARGET_WEBASSEMBLY_WEBASSEMBLYDEBUGVALUEMANAGER_H
 
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/CodeGen/MachineOperand.h"
 
 namespace llvm {
 
 class MachineInstr;
 
 class WebAssemblyDebugValueManager {
   SmallVector<MachineInstr *, 2> DbgValues;
 
 public:
   WebAssemblyDebugValueManager(MachineInstr *Instr);
 
   void move(MachineInstr *Insert);
   void updateReg(unsigned Reg);
   void clone(MachineInstr *Insert, unsigned NewReg);
   void replaceWithLocal(unsigned LocalId);
+  void replaceWithStackOffset(unsigned StackOffset);
+  void replaceWithRegister(MachineOperand &MO);
 };
 
 } // end namespace llvm
 
 #endif

llvm/lib/Target/WebAssembly/WebAssemblyDebugValueManager.cpp

 //===-- WebAssemblyDebugValueManager.cpp - WebAssembly DebugValue Manager -===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
 /// This file implements the manager for MachineInstr DebugValues.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "WebAssemblyDebugValueManager.h"
 #include "WebAssembly.h"
 #include "WebAssemblyMachineFunctionInfo.h"
-#include "llvm/CodeGen/MachineInstr.h"
 
 using namespace llvm;
 
 WebAssemblyDebugValueManager::WebAssemblyDebugValueManager(
     MachineInstr *Instr) {
   Instr->collectDebugValues(DbgValues);
 }
 
 void WebAssemblyDebugValueManager::move(MachineInstr *Insert) {
   MachineBasicBlock *MBB = Insert->getParent();
   for (MachineInstr *DBI : reverse(DbgValues))
     MBB->splice(Insert, DBI->getParent(), DBI);
 }
 

 }
 
 void WebAssemblyDebugValueManager::replaceWithLocal(unsigned LocalId) {
   for (auto *DBI : DbgValues) {
     MachineOperand &Op = DBI->getOperand(0);
     Op.ChangeToTargetIndex(llvm::WebAssembly::TI_LOCAL, LocalId);
   }
 }
+
+void WebAssemblyDebugValueManager::replaceWithStackOffset(unsigned StackOffset) {
+  for (auto *DBI : DbgValues) {
+    MachineOperand &Op = DBI->getOperand(0);
+    Op.ChangeToTargetIndex(llvm::WebAssembly::TI_OPERAND_STACK, StackOffset);
+  }
+}
+
+void WebAssemblyDebugValueManager::replaceWithRegister(MachineOperand &MO) {
+  for (auto *DBI : DbgValues) {
+    MachineOperand &Op = DBI->getOperand(0);
+    Op.ChangeToRegister(MO.getReg(), MO.isDef(), MO.isImplicit(), MO.isKill(),
+                        MO.isDead(), MO.isUndef(), MO.isDebug());
+  }
+}

llvm/lib/Target/WebAssembly/WebAssemblyRegStackify.cpp

 }
 
 /// A single-use def in the same block with no intervening memory or register
 /// dependencies; move the def down and nest it with the current instruction.
 static MachineInstr *moveForSingleUse(unsigned Reg, MachineOperand &Op,
                                       MachineInstr *Def, MachineBasicBlock &MBB,
                                       MachineInstr *Insert, LiveIntervals &LIS,
                                       WebAssemblyFunctionInfo &MFI,
-                                      MachineRegisterInfo &MRI) {
+                                      MachineRegisterInfo &MRI,
+                                      unsigned StackDepth) {
   LLVM_DEBUG(dbgs() << "Move for single use: "; Def->dump());
 
   WebAssemblyDebugValueManager DefDIs(Def);
   MBB.splice(Insert, &MBB, Def);
   DefDIs.move(Insert);
   LIS.handleMove(*Def);
 
   if (MRI.hasOneDef(Reg) && MRI.hasOneUse(Reg)) {
if (MRI.hasOneDef(Reg) && MRI.hasOneUse(Reg)) {
 
     MFI.stackifyVReg(NewReg);
 
     DefDIs.updateReg(NewReg);
 
     LLVM_DEBUG(dbgs() << " - Replaced register: "; Def->dump());
   }
 
+  DefDIs.replaceWithStackOffset(StackDepth);
   imposeStackOrdering(Def);
   return Def;
 }
 
 /// A trivially cloneable instruction; clone it and nest the new copy with the
 /// current instruction.
 static MachineInstr *rematerializeCheapDef(
     unsigned Reg, MachineOperand &Op, MachineInstr &Def, MachineBasicBlock &MBB,
     MachineBasicBlock::instr_iterator Insert, LiveIntervals &LIS,
     WebAssemblyFunctionInfo &MFI, MachineRegisterInfo &MRI,
-    const WebAssemblyInstrInfo *TII, const WebAssemblyRegisterInfo *TRI) {
+    const WebAssemblyInstrInfo *TII, const WebAssemblyRegisterInfo *TRI,
+    unsigned StackDepth) {
   LLVM_DEBUG(dbgs() << "Rematerializing cheap def: "; Def.dump());
   LLVM_DEBUG(dbgs() << " - for use in "; Op.getParent()->dump());
 
   WebAssemblyDebugValueManager DefDIs(&Def);
 
   Register NewReg = MRI.createVirtualRegister(MRI.getRegClass(Reg));
   TII->reMaterialize(MBB, Insert, NewReg, 0, Def, *TRI);
   Op.setReg(NewReg);
if (IsDead) {
     LIS.RemoveMachineInstrFromMaps(Def);
     Def.eraseFromParent();
 
     DefDIs.move(&*Insert);
     DefDIs.updateReg(NewReg);
   } else {
     DefDIs.clone(&*Insert, NewReg);
   }
+  // DefDIs points to old def, so create a new one.
+  WebAssemblyDebugValueManager(&*Insert).replaceWithStackOffset(StackDepth);
 
   return Clone;
 }
 
 /// A multiple-use def in the same block with no intervening memory or register
 /// dependencies; move the def down, nest it with the current instruction, and
 /// insert a tee to satisfy the rest of the uses. As an illustration, rewrite
 /// this:
 ///
 ///    Reg = INST ...        // Def
 ///    INST ..., Reg, ...    // Insert
 ///    INST ..., Reg, ...
 ///    INST ..., Reg, ...
 ///
 /// to this:
 ///
 ///    DefReg = INST ...     // Def (to become the new Insert)
 ///    TeeReg, Reg = TEE_... DefReg
 ///    INST ..., TeeReg, ... // Insert
 ///    INST ..., Reg, ...
 ///    INST ..., Reg, ...
 ///
 /// with DefReg and TeeReg stackified. This eliminates a local.get from the
 /// resulting code.
 static MachineInstr *moveAndTeeForMultiUse(
     unsigned Reg, MachineOperand &Op, MachineInstr *Def, MachineBasicBlock &MBB,
     MachineInstr *Insert, LiveIntervals &LIS, WebAssemblyFunctionInfo &MFI,
-    MachineRegisterInfo &MRI, const WebAssemblyInstrInfo *TII) {
+    MachineRegisterInfo &MRI, const WebAssemblyInstrInfo *TII,
+    unsigned StackDepth) {
   LLVM_DEBUG(dbgs() << "Move and tee for multi-use:"; Def->dump());
 
   WebAssemblyDebugValueManager DefDIs(Def);
 
   // Move Def into place.
   MBB.splice(Insert, &MBB, Def);
   LIS.handleMove(*Def);
 
static MachineInstr *moveAndTeeForMultiUse(
   LIS.createAndComputeVirtRegInterval(DefReg);
   MFI.stackifyVReg(DefReg);
   MFI.stackifyVReg(TeeReg);
   imposeStackOrdering(Def);
   imposeStackOrdering(Tee);
 
   DefDIs.clone(Tee, DefReg);
   DefDIs.clone(Insert, TeeReg);
+  // DefDIs points to old def, so create a new one.
+  WebAssemblyDebugValueManager(&*Insert).replaceWithStackOffset(StackDepth);
 
   LLVM_DEBUG(dbgs() << " - Replaced register: "; Def->dump());
   LLVM_DEBUG(dbgs() << " - Tee instruction: "; Tee->dump());
   return Def;
 }
 
 namespace {
 /// A stack for walking the tree of instructions being built, visiting the
 /// MachineOperands in DFS order.
 class TreeWalkerState {
   using mop_iterator = MachineInstr::mop_iterator;
   using mop_reverse_iterator = std::reverse_iterator<mop_iterator>;
   using RangeTy = iterator_range<mop_reverse_iterator>;
   SmallVector<RangeTy, 4> Worklist;
 
 public:
   explicit TreeWalkerState(MachineInstr *Insert) {
     const iterator_range<mop_iterator> &Range = Insert->explicit_uses();
     if (Range.begin() != Range.end())
       Worklist.push_back(reverse(Range));
   }
 
   bool done() const { return Worklist.empty(); }
 
+  unsigned stackDepth() { return static_cast<unsigned>(Worklist.size()); }
+
   MachineOperand &pop() {
     RangeTy &Range = Worklist.back();
     MachineOperand &Op = *Range.begin();
     Range = drop_begin(Range, 1);
     if (Range.begin() == Range.end())
       Worklist.pop_back();
     assert((Worklist.empty() ||
             Worklist.back().begin() != Worklist.back().end()) &&
for (auto MII = MBB.rbegin(); MII != MBB.rend(); ++MII) {
         // this makes things simpler (LiveIntervals' handleMove function only
         // supports intra-block moves) and it's MachineSink's job to catch all
         // the sinking opportunities anyway.
         bool SameBlock = DefI->getParent() == &MBB;
         bool CanMove = SameBlock &&
                        isSafeToMove(Def, &Use, Insert, AA, MFI, MRI) &&
                        !TreeWalker.isOnStack(Reg);
         if (CanMove && hasOneUse(Reg, DefI, MRI, MDT, LIS)) {
-          Insert = moveForSingleUse(Reg, Use, DefI, MBB, Insert, LIS, MFI, MRI);
+          Insert = moveForSingleUse(Reg, Use, DefI, MBB, Insert, LIS, MFI, MRI,
+                                    TreeWalker.stackDepth());
 
           // If we are removing the frame base reg completely, remove the debug
           // info as well.
           // TODO: Encode this properly as a stackified value.
           if (MFI.isFrameBaseVirtual() && MFI.getFrameBaseVreg() == Reg)
             MFI.clearFrameBaseVreg();
         } else if (shouldRematerialize(*DefI, AA, TII)) {
           Insert =
               rematerializeCheapDef(Reg, Use, *DefI, MBB, Insert->getIterator(),
-                                    LIS, MFI, MRI, TII, TRI);
+                                    LIS, MFI, MRI, TII, TRI,
+                                    TreeWalker.stackDepth());
         } else if (CanMove && oneUseDominatesOtherUses(Reg, Use, MBB, MRI, MDT,
                                                        LIS, MFI)) {
           Insert = moveAndTeeForMultiUse(Reg, Use, DefI, MBB, Insert, LIS, MFI,
-                                         MRI, TII);
+                                         MRI, TII, TreeWalker.stackDepth());
         } else {
           // We failed to stackify the operand. If the problem was ordering
           // constraints, Commuting may be able to help.
           if (!CanMove && SameBlock)
             Commuting.maybeCommute(Insert, TreeWalker, TII);
           // Proceed to the next operand.
           continue;
         }
 
         // Stackifying a multivalue def may unlock in-place stackification of
         // subsequent defs. TODO: Handle the case where the consecutive uses are
         // not all in the same instruction.
         auto *SubsequentDef = Insert->defs().begin();
         auto *SubsequentUse = &Use;
         while (SubsequentDef != Insert->defs().end() &&
                SubsequentUse != Use.getParent()->uses().end()) {
           if (!SubsequentDef->isReg() || !SubsequentUse->isReg())
             break;
           unsigned DefReg = SubsequentDef->getReg();
           unsigned UseReg = SubsequentUse->getReg();
           // TODO: This single-use restriction could be relaxed by using tees
           if (DefReg != UseReg || !MRI.hasOneUse(DefReg))
             break;
           MFI.stackifyVReg(DefReg);
+          WebAssemblyDebugValueManager(&*Insert).replaceWithStackOffset(
+                                                    TreeWalker.stackDepth());
           ++SubsequentDef;
           ++SubsequentUse;
         }
 
         // If the instruction we just stackified is an IMPLICIT_DEF, convert it
         // to a constant 0 so that the def is explicit, and the push/pop
         // correspondence is maintained.
         if (Insert->getOpcode() == TargetOpcode::IMPLICIT_DEF)