[WebAssembly] Use LiveDebugValues analysis

[aheejin]

Summary

This enables LiveDebugValues analysis for Wasm. DBG_VALUEs expire at
the end of a BB, and this is the analysis extends their lifetime when
possible, greatly increasing the coverage of variable debug info.

Specifically, this removes the current constraint that this analysis is
only used with physical registers, which was first introduced in D18421,
because Wasm uses only virtual registers. I don't think there's anything
inherent in this analysis that only applies to physical registers; it
was just because all targets using this analysis ran this at the end of
their compiliation pipeline, at which point all their vregs had been
allocated, and Wasm's debug info infrastructure was not really set up
yet, so it was not using it.

This adds supports to Wasm-specific target-index operands, defined in
https://github.com/llvm/llvm-project/blob/2166d9529a60d1cdedb733d2e4134c971f0969ec/llvm/lib/Target/WebAssembly/WebAssembly.h#L87-L100.
Among these, TI_LOCAL, TI_LOCAL_INDIRECT, and TI_OPERAND_STACK are
used by Wasm DBG_VALUE instructions.

This does not yet handle mutable target indices, i.e., this does not
terminate a DBG_VALUE for a local index when we encounter a new
local.set or local.tee. It will be implemented as a follow-up.

(I had posted some stats but removed them because they are inaccurate at
this point, because this is not fully implemented yet)

[dschuff]

llvm/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp

693

does SpillLocation make sense when the loc is a register kind?

741

So I assume this is being removed because we are using VRegs instead of physregs, and VRegs have arbitrary large unsigned values (greater than 1 << 30).
Looking at what that might mean: It seems that LocIndex is relying on this in some way.
Aside from there, the other place register values are checked against kFirstInvalidRegLocation is in getUsedRegs, where it seems to only collect values in the valid physreg range. so it seems that getUsedRegs will never return VRegs. It seems that `getUsedRegs is only used in the case of RegMask machine operand (which IIRC wasm doesn't use and which only make sense for physregs anyway).

So... I guess this seems like overall it should work? It does seem odd that we are using LocIndex but violating one of its primary assumptions. Is there anything else that could potentially go wrong?

2109

would it also be correct to condition this on MO.getReg() being a physical rather than a virtual reg? If so, I think something like that would be clearer than the more general condition that there can't be any vregs at all.

[aheejin]

Address a few comments first

[aheejin]

llvm/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp

693

OMG, I copy-pasted this from SpillLocKind by mistake. Nevermind.

741

I deleted this thinking simply like 1. this assertion failed on Wasm and 2. Wasm used virtual registers, so the assertion failure made sense. But yeah, this doesn't feel very satisfactory after all.

I don't think this will cause any functional problems in other archs. They are all using all physical registers after all. (This analysis runs at the very end of the backend pipeline.) But the funny thing is, Wasm is NOT supposed use RegisterKind at all. What does it even mean when debug info resides within a virtual register (which doesn't really exist in Wasm physically) at the end of compilation? All usable debug info should be either in a local or a stack location, or an immediate. So encountering a (virtual) register here in Wasm basically means it is a dangling debug info, which will be ignored when written to binary.

I'm not sure we can consider this kind of dangling DBG_VALUE hanging around a critical bug to fix. While it is a bug, it can happen quite often, when a pass does not handle its corresponding DBG_VALUE when transforming/deleting/splitting a normal instruction. Preserving as much as DBG_VALUE is more like an optimization problem; not preserving some of them doesn't mean the program should crash.

So in short, I had to disable this to make it run on many Wasm programs, which have some dangling DBG_VALUEs at the end. I think maybe more tidy solution here would be to make the pass ignore register-based DBG_VALUE in case of Wasm, and re-enable this assertion..? But to do that we have to check the architecture at some point, which feels a little ugly to me, but maybe that's better than this.

WDYT?

2109

Makes sense. Changed to check the register itself.

[dschuff]

llvm/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp

741

Ah, I had forgotten that we aren't using VRegs here either (I guess I didn't realize that this pass runs after explicit locals). I think in that case it does make more sense to just say that this pass should not encounter register values with wasm at all, so the register code doesn't need to handle VRegs. Probably we should have some comment to that effect somewhere.

I guess it's a bit unfortunate that we'll have dangling register locations anyway. Is there a straightforward way to either ignore them explicitly or maybe drop them before or at the beginning of this pass?

[aheejin]

llvm/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp

741

How about dropping all of them at the end of WebAssemblyDebugFixup pass? It runs at the very end, and it also does tasks related to debug info, so adding something there doesn't seem like a stretch. Or we can add a new pass, but that pass will be tiny.

If you think doing that in WebAssemblyDebugFixup is a good idea, I'll make a CL that does that separately and will land it first before landing this, and re-enable the assertion here.

[dschuff]

llvm/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp

741

If I'm understanding you right, any DBG_VALUEs that have Register operands after explicit locals are dead and can't be encoded into the binary anyway, right? So I think it makes sense to drop them, and WebAssemblyDebugFixup seems like a reasonable place to me.

[jmorse]

I see from the inline comments that virtual registers in WASM at this stage may or may not be meaningful -- if we can avoid LiveDebugValues having to encounter virtual registers, that's highly preferred, as it avoids considering a whole load of scenarios that LiveDebugValues isn't designed for. The number space for LocIndex is designed only for physregs and spill slots (physregs from 1 to 2^30, spill slots from 2^30+1 to 2^31-1). Adding the number range for virtual registers would require more testing.

Stepping back a bit: as ever I'm not very familiar with WASM, but are the "target index" locations mutable? The test added covers a few scenarios that more or less amount to SSA construction, i.e. propagation of the variable locations to successor blocks and merging of locations at PHI points. The main purpose of LiveDebugValues however is to track variable locations/values as they move between phyregs and stack slots, and go out of liveness. If the target index locations are immutable, then you can just get away with using existing SSA construction tools in LLVM to work out how to propagate locations. If they're mutable though, you'll need to put logic in transferRegisterDef and similar to identify when the target-index locations are modified, so that variable locations are terminated correctly.

llvm/lib/CodeGen/LiveDebugValues/LiveDebugValues.cpp

75–79

Doing this makes sense for WASM, but check that there are no virtual registers remains an important sanity check for other targets -- mixing vregs and physregs would definitely generate broken results. Would you be able to add an assertion somewhere else for everything but WASM? (I don't think this method can know what the target arch is).

[aheejin]

Address comments + disable LiveDebugValues analysis by default

llvm/lib/CodeGen/LiveDebugValues/LiveDebugValues.cpp

75–79

Added an assertion in the beginning of LiveDebugValues::runOnMachineFunction.

llvm/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp

741

Nullified the dangling register-based DBG_VALUEs in D139675, and revived this assertion.

[aheejin]

@jmorse Thanks for your review, and sorry for the late reply!

In D138943#3960663, @jmorse wrote:

I see from the inline comments that virtual registers in WASM at this stage may or may not be meaningful -- if we can avoid LiveDebugValues having to encounter virtual registers, that's highly preferred, as it avoids considering a whole load of scenarios that LiveDebugValues isn't designed for. The number space for LocIndex is designed only for physregs and spill slots (physregs from 1 to 2^30, spill slots from 2^30+1 to 2^31-1). Adding the number range for virtual registers would require more testing.

I removed all register-based (= dangling) DBG_VALUEs for Wasm in D139675; WebAssemblyDebugFixup runs right before this analysis. So now we don't have any virtual registers participating here, and I re-enabled the physical register assertion, so we can maintain LocIndex only deals with physical registers.

Stepping back a bit: as ever I'm not very familiar with WASM, but are the "target index" locations mutable? The test added covers a few scenarios that more or less amount to SSA construction, i.e. propagation of the variable locations to successor blocks and merging of locations at PHI points. The main purpose of LiveDebugValues however is to track variable locations/values as they move between phyregs and stack slots, and go out of liveness. If the target index locations are immutable, then you can just get away with using existing SSA construction tools in LLVM to work out how to propagate locations. If they're mutable though, you'll need to put logic in transferRegisterDef and similar to identify when the target-index locations are modified, so that variable locations are terminated correctly.

Thanks for pointing this out. They are mutable, so I should have handled this. There are two kinds of target indices: local indices and stack operands.

1. Locals are something similar to registers in Wasm-land. For local indices, I think we can check for local-defining instructions (local.set or local.tee).
2. Wasm is a stack machine, so we have a value in certain Wasm value stack location, which changes whenever Wasm instructions produce or consume values. So basically any value-producing instrucion, i.e., instruction with defs, can change values in Wasm stack. But I think we don't need to worry about this here, because WebAssemblyDebugFixup, which runs right before this analysis, makes sure to insert terminating DBG_VALUE $noreg instructions whenever a stack value gets popped.

I'm working on (1) now. Would you mind if I address it as a follow-up child CL? I disabled LiveDebugValues analysis here so this not-yet-fully-implemented analysis doesn't run on Wasm pipeline, and we only check for my basic test cases here.

---

By the way, may I ask a separate question? How should I handle defs in memory locations? Should I use SpillLocs? (They currently can have only registers as their base though) But looking at this code, it looks not every store instruction qualifies as a spill. Also you can access the same memory address even with a different register + offset, so it kind of looks all stores can terminate any indirect DBG_VALUEs. How do other targets handle defs in indirect DBG_VALUE locations?

For Wasm, it looks we have a very small number of indirect DBG_VALUEs anyway, so maybe I can start with nullifying them and not dealing with them, as I did for DBG_VALUE_LISTs a while ago in D102999. But I'm generally curious about how memory locations should be handled. Sorry for many questions 😅

[dschuff]

llvm/lib/CodeGen/LiveDebugValues/LiveDebugValues.cpp

75–79

I wonder if the ExplicitLocals pass should actually set the NoVRegs property? It should hold true after that pass runs, and I don't think we add any ourselves after that?

llvm/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp

2109

This change can be reverted now that we've removed the VRegs, right?

[aheejin]

llvm/lib/CodeGen/LiveDebugValues/LiveDebugValues.cpp

75–79

I don't think setting NoVRegswill affect the functionality or make the compiler crash or anything, but in the MIR sense, we still have virtual registers after ExplicitLocals, no? We just insert local.get/sets so that they can be translated to stack machine Wasm instructions later.

Before ExplicitLocals:

%0 = i32.const 3
...
use %0

After ExplicitLocals:

%0 = i32.const 3
local.set 5
...
%1 = local.get 5
use %1

So the MIR after ExplicitLocals still contains %0 and %1, which are virtual registers, even though they will not be materialized in the final Wasm code. So I'm not sure if we should set NoVRegs after that.

llvm/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp

2109

Not really, at least not without touching other parts. This function is called on all instructions, not only DBG_VALUEs, so our virtual registers enter here. They will not play any role in the rest of the pass though. Apparently DefinedRegs which are collected in this function is only used in recordEntryValue function, and we don't use entry values. But anyway without this if we will crash.

On the other hand, the other assertion I had removed and revived, is in VarLoc::insert, and only runs on registers in DBG_VALUEs, which we removed, so we can have that assertion.

[dschuff]

This looks good to me overall with the plan for followup. Maybe we can wait to land for a bit to see if @jmorse has any followup comments.

llvm/lib/CodeGen/LiveDebugValues/LiveDebugValues.cpp

75–79

Ah, right I had forgotten that the register operands aren't removed until MCInstLower. I guess any code that runs after explicit locals just has to be careful not to mess up the relationship between the local gets/sets and their associated operands.

[aheejin]

Test function name changes

[jmorse]

I removed all register-based (= dangling) DBG_VALUEs for Wasm in D139675; WebAssemblyDebugFixup runs right before this analysis. So now we don't have any virtual registers participating here, and I re-enabled the physical register assertion, so we can maintain LocIndex only deals with physical registers.

Excellent, that keeps the pass nice and simple,

I'm working on (1) now. Would you mind if I address it as a follow-up child CL? I disabled LiveDebugValues analysis here so this not-yet-fully-implemented analysis doesn't run on Wasm pipeline, and we only check for my basic test cases here.

SGTM -- to state the obvious, it means that the analysis won't realise that over-written locals means the variable location should terminate, and they might be propagated into successor blocks. (And it should be fixed by the follow up).

In terms of this patch, I think it wants metadata node-number-capturing (see inline comment on test) but otherwise LGTM.

By the way, may I ask a separate question? How should I handle defs in memory locations? Should I use SpillLocs? (They currently can have only registers as their base though) But looking at this code, it looks not every store instruction qualifies as a spill. Also you can access the same memory address even with a different register + offset, so it kind of looks all stores can terminate any indirect DBG_VALUEs. How do other targets handle defs in indirect DBG_VALUE locations?

For Wasm, it looks we have a very small number of indirect DBG_VALUEs anyway, so maybe I can start with nullifying them and not dealing with them, as I did for DBG_VALUE_LISTs a while ago in D102999. But I'm generally curious about how memory locations should be handled. Sorry for many questions 😅

I'm very glad to answer debug-info questions -- by "defs in memory locations" do you mean that an instruction produces a value, not in a register, but at a memory location? There are some situations where this can be tracked on other targets, but it's messy, and we don't try to do it for heap memory because any pointer can alias it. There are two situations where memory transfers are tracked:

• For local stack spill slots, the LiveDebugVariables pass receives information during register allocation indicating where variable values are going, and indirect DBG_VALUEs are inserted whenever spills/restores occur.
• LiveDebugValues can recognise spill-and-restores instructions and transfer variables locations into spill slots, and back out, in case there are spills not recognised by LiveDebugVariables

As far as I understand it, the situation that LLVM handles very well is where (on x86 for example) a definition happens in a register that is then spilled, and then the spill is fused into the instruction, for example:

$rax = addrr64 $rax, $rdx           <---- Some arithmetic instruction,
MOV64mr $rsp, ???, 16, killed $rax  <---- A stack spill
DBG_VALUE %stack.0, 0               <---- indirect DBG_VALUE inserted by LiveDebugVariables

Is fused into:

addmr64 $rsp, ???, 16, killed $rdx  <---- Arithmetic adding into a stack slot,
DBG_VALUE %stack.0, 0               <---- indirect DBG_VALUE inserted by LiveDebugVariables

I'm not aware of any other situation that LLVM can handle where a definition happens in memory -- and critically, the above code sequence is one where the memory location used to explicitly come from a spill instruction, but is then optimised further, so it's not a piece of information that is explicitly tracked. If that fusing happens during instruction selection and the value is defined into a regular local variable on the stack, then today it isn't be tracked.

Seeing how you've got a lot of control of the wasm pipeline, I imagine it's possible to add instrumentation and (perhaps) identify scenarios where definitions to stack-like memory happen and produce indirect DBG_VALUEs. That might be prohibitively complicated though.

This might be the point where I need to plug my re-designed variable tracking scheme, a summary is in this talk: https://www.youtube.com/watch?v=yxuwfNnp064 , you can find references to "instruction referencing" on the mailing list / discourse. The core idea is to number each instruction, and each operand of that instruction, connect variable information with those numbers and leave variable information in SSA form. Then at the end of compilation to re-analyse the code and find the machine locations for values. This means that you can describe a value as "The memory operand of instruction number $n" such as in this test [0]. The analysis at the end of codegen relies on being able to "see" all memory writes, so it too only works for stack slots. If there's something analogous in wasm then perhaps it could be fitted to that.

[0] https://github.com/llvm/llvm-project/blob/416fd03708d49b66900ef629c733fbbad2a602e2/llvm/test/DebugInfo/MIR/InstrRef/memory-operand-folding.mir

llvm/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp

2109

This change won't hinder other targets, however you mention that virtual register don't participate in LiveDebugValues, so they don't need to be in the defined register collection AFAIUI. It might be cleaner to add the isPhysicalRegister condition to the if so that virtual registers are completely ignored.

llvm/test/DebugInfo/WebAssembly/live-debug-values.mir

2–3

Could you make the CHECK lines a bit more robust by capturing the metadata number and comparing against that -- if you look at other debug-info tests for dbg.values you'll see they usually capture like:

![[VAR:[0-9+]]] = DILocalVariable(name: "foo"
CHECK: dbg.value({{.*}}, ![[VAR]]...

or something. This saves us bother in the future if the IR module gets auto-upgraded, the metadata renumbers, and then the metadata node numbers don't match what's in the CHECK lines.

[aheejin]

Address comments

llvm/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp

2109

Hoisted the isPhysicalRegister condition so that it's now this

for (const MachineOperand &MO : MI.operands())
  if (MO.isReg() && MO.isDef() && MO.getReg() &&
      Register::isPhysicalRegister(MO.getReg())) {

[aheejin]

@jmorse Thanks for the answer for the spill location tracking! Will check your dev meeting talk too. I saw x86 is using an alternative implementation of LDV that uses DBG_INSTR_REF, but hasn't had a chance to catch up on that in detail.

[aheejin]

Add braces

[aheejin]

@jmorse Do you have any remaining concerns for landing this patch? (which will be followed up by D140373)

[aheejin]

@jmorse Oh, I found you suggested to add comments here in D140373.

In D140373#4016029, @jmorse wrote:

Thanks for assurance about the stack-popping being addressed elsewhere -- it might be worth putting a comment in D138943 next to the definition of struct WasmLoc about that being a deliberate non-objective, to enlighten future readers.

I tried that, but I'm not sure if this is the best location to put this kind of target-specific comment. This is what I've tried:

--- a/llvm/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp
+++ b/llvm/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp
@@ -306,7 +306,12 @@ private:
 
     // Target indices used for wasm-specific locations.
     struct WasmLoc {
-      int Index; // One of TargetIndex values defined in WebAssembly.h
+      // One of TargetIndex values defined in WebAssembly.h. We deal with
+      // local-related TargetIndex in this analysis (TI_LOCAL and
+      // TI_LOCAL_INDIRECT). Stack operands (TI_OPERAND_STACK) will be handled
+      // separately WebAssemblyDebugFixup pass, and we don't associate debug
+      // info with values in global operands (TI_GLOBAL_RELOC) at the moment.
+      int Index;
       int64_t Offset;
       bool operator==(const WasmLoc &Other) const {
         return Index == Other.Index && Offset == Other.Offset;

This is basically the copy of what I said in WebAssemblyInstrInfo.cpp in D140373. That file is within lib/Target/WebAssembly, so I feel like I can elaborate on as many target-specific things as I want. But I'm not so sure about VarLocBasedImpl.cpp, which is target-independent, and especially when we don't need to distinguish anything about local and stack operands within that file. (We treat all target indices in the same way in the file; the part that handles the difference is encapsulated within

if (!TII->isExplicitTargetIndexDef(MI, Index, Offset))                         
  return;

which has its own detailed comments in WebAssemblyInstrInfo.cpp. This part is added in D140373; it's not here yet.

I haven't committed this diff yet, because of this concern. Please let me know if you think this is a good idea there.

[aheejin]

@jmorse I would like to land this soon because we have waiting users. If you have remaining comments, I'll address them as follow-ups. Thank you!

[jmorse]

This all LGTM; if you're happy with the comments for struct WasmLoc then that's fine too.

llvm/lib/CodeGen/LiveDebugValues/LiveDebugValues.cpp

 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
 #include "llvm/PassRegistry.h"
 #include "llvm/Support/CommandLine.h"
+#include "llvm/Target/TargetMachine.h"
 
 /// \file LiveDebugValues.cpp
 ///
 /// The LiveDebugValues pass extends the range of variable locations
 /// (specified by DBG_VALUE instructions) from single blocks to successors
 /// and any other code locations where the variable location is valid.
 /// There are currently two implementations: the "VarLoc" implementation
 /// explicitly tracks the location of a variable, while the "InstrRef"
public:
   static char ID;
 
   LiveDebugValues();
   ~LiveDebugValues() = default;
 
   /// Calculate the liveness information for the given machine function.
   bool runOnMachineFunction(MachineFunction &MF) override;
 
-  MachineFunctionProperties getRequiredProperties() const override {
-    return MachineFunctionProperties().set(
-        MachineFunctionProperties::Property::NoVRegs);
-  }
-
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
     MachineFunctionPass::getAnalysisUsage(AU);
   }
 
 private:
   std::unique_ptr<LDVImpl> InstrRefImpl;
   std::unique_ptr<LDVImpl> VarLocImpl;

 LiveDebugValues::LiveDebugValues() : MachineFunctionPass(ID) {
   initializeLiveDebugValuesPass(*PassRegistry::getPassRegistry());
   InstrRefImpl =
       std::unique_ptr<LDVImpl>(llvm::makeInstrRefBasedLiveDebugValues());
   VarLocImpl = std::unique_ptr<LDVImpl>(llvm::makeVarLocBasedLiveDebugValues());
 }
 
 bool LiveDebugValues::runOnMachineFunction(MachineFunction &MF) {
+  // Except for Wasm, all targets should be only using physical register at this
+  // point. Wasm only use virtual registers throught its pipeline, but its
+  // virtual registers don't participate  in this LiveDebugValues analysis; only
+  // its target indices do.
+  assert(MF.getTarget().getTargetTriple().isWasm() ||
+         MF.getProperties().hasProperty(
+             MachineFunctionProperties::Property::NoVRegs));
+
   bool InstrRefBased = MF.useDebugInstrRef();
   // Allow the user to force selection of InstrRef LDV.
   InstrRefBased |= ForceInstrRefLDV;
 
   TPC = getAnalysisIfAvailable<TargetPassConfig>();
   LDVImpl *TheImpl = &*VarLocImpl;
 
   MachineDominatorTree *DomTree = nullptr;

llvm/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp

struct SpillLoc {
       bool operator==(const SpillLoc &Other) const {
         return SpillBase == Other.SpillBase && SpillOffset == Other.SpillOffset;
       }
       bool operator!=(const SpillLoc &Other) const {
         return !(*this == Other);
       }
     };
 
+    // Target indices used for wasm-specific locations.
+    struct WasmLoc {
+      int Index; // One of TargetIndex values defined in WebAssembly.h
+      int64_t Offset;
+      bool operator==(const WasmLoc &Other) const {
+        return Index == Other.Index && Offset == Other.Offset;
+      }
+      bool operator!=(const WasmLoc &Other) const { return !(*this == Other); }
+    };
+
     /// Identity of the variable at this location.
     const DebugVariable Var;
 
     /// The expression applied to this location.
     const DIExpression *Expr;
 
     /// DBG_VALUE to clone var/expr information from if this location
     /// is moved.
     const MachineInstr &MI;
 
     enum class MachineLocKind {
       InvalidKind = 0,
       RegisterKind,
       SpillLocKind,
-      ImmediateKind
+      ImmediateKind,
+      WasmLocKind
     };
 
     enum class EntryValueLocKind {
       NonEntryValueKind = 0,
       EntryValueKind,
       EntryValueBackupKind,
       EntryValueCopyBackupKind
     } EVKind = EntryValueLocKind::NonEntryValueKind;
 
     /// The value location. Stored separately to avoid repeatedly
     /// extracting it from MI.
     union MachineLocValue {
       uint64_t RegNo;
       SpillLoc SpillLocation;
       uint64_t Hash;
       int64_t Immediate;
       const ConstantFP *FPImm;
       const ConstantInt *CImm;
+      WasmLoc WasmLocation;
       MachineLocValue() : Hash(0) {}
     };
 
     /// A single machine location; its Kind is either a register, spill
     /// location, or immediate value.
     /// If the VarLoc is not a NonEntryValueKind, then it will use only a
     /// single MachineLoc of RegisterKind.
     struct MachineLoc {
       MachineLocKind Kind;
       MachineLocValue Value;
       bool operator==(const MachineLoc &Other) const {
         if (Kind != Other.Kind)
           return false;
         switch (Kind) {
         case MachineLocKind::SpillLocKind:
           return Value.SpillLocation == Other.Value.SpillLocation;
+        case MachineLocKind::WasmLocKind:
+          return Value.WasmLocation == Other.Value.WasmLocation;
         case MachineLocKind::RegisterKind:
         case MachineLocKind::ImmediateKind:
           return Value.Hash == Other.Value.Hash;
         default:
           llvm_unreachable("Invalid kind");
         }
       }
       bool operator<(const MachineLoc &Other) const {
         switch (Kind) {
         case MachineLocKind::SpillLocKind:
           return std::make_tuple(
                      Kind, Value.SpillLocation.SpillBase,
                      Value.SpillLocation.SpillOffset.getFixed(),
                      Value.SpillLocation.SpillOffset.getScalable()) <
                  std::make_tuple(
                      Other.Kind, Other.Value.SpillLocation.SpillBase,
                      Other.Value.SpillLocation.SpillOffset.getFixed(),
                      Other.Value.SpillLocation.SpillOffset.getScalable());
+        case MachineLocKind::WasmLocKind:
+          return std::make_tuple(Kind, Value.WasmLocation.Index,
+                                 Value.WasmLocation.Offset) <
+                 std::make_tuple(Other.Kind, Other.Value.WasmLocation.Index,
+                                 Other.Value.WasmLocation.Offset);
         case MachineLocKind::RegisterKind:
         case MachineLocKind::ImmediateKind:
           return std::tie(Kind, Value.Hash) <
                  std::tie(Other.Kind, Other.Value.Hash);
         default:
           llvm_unreachable("Invalid kind");
         }
       }
static MachineLoc GetLocForOp(const MachineOperand &Op) {
         Kind = MachineLocKind::ImmediateKind;
         Loc.Immediate = Op.getImm();
       } else if (Op.isFPImm()) {
         Kind = MachineLocKind::ImmediateKind;
         Loc.FPImm = Op.getFPImm();
       } else if (Op.isCImm()) {
         Kind = MachineLocKind::ImmediateKind;
         Loc.CImm = Op.getCImm();
+      } else if (Op.isTargetIndex()) {
+        Kind = MachineLocKind::WasmLocKind;
+        Loc.WasmLocation = {Op.getIndex(), Op.getOffset()};
       } else
         llvm_unreachable("Invalid Op kind for MachineLoc.");
       return {Kind, Loc};
     }
 
     /// Take the variable and machine-location in DBG_VALUE MI, and build an
     /// entry location using the given expression.
     static VarLoc CreateEntryLoc(const MachineInstr &MI,
MachineInstr *BuildDbgValue(MachineFunction &MF) const {
           }
           MOs.push_back(MachineOperand::CreateReg(Base, false));
           break;
         }
         case MachineLocKind::ImmediateKind: {
           MOs.push_back(Orig);
           break;
         }
+        case MachineLocKind::WasmLocKind: {
+          MOs.push_back(Orig);
+          break;
+        }
         case MachineLocKind::InvalidKind:
           llvm_unreachable("Tried to produce DBG_VALUE for invalid VarLoc");
         }
       }
       return BuildMI(MF, DbgLoc, IID, Indirect, MOs, Var, DIExpr);
     }
 
     /// Is the Loc field a constant or constant object?
struct VarLoc {
 
     /// Determine whether the lexical scope of this value's debug location
     /// dominates MBB.
     bool dominates(LexicalScopes &LS, MachineBasicBlock &MBB) const {
       return LS.dominates(MI.getDebugLoc().get(), &MBB);
     }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
-    // TRI can be null.
-    void dump(const TargetRegisterInfo *TRI, raw_ostream &Out = dbgs()) const {
+    // TRI and TII can be null.
+    void dump(const TargetRegisterInfo *TRI, const TargetInstrInfo *TII,
+              raw_ostream &Out = dbgs()) const {
       Out << "VarLoc(";
       for (const MachineLoc &MLoc : Locs) {
         if (Locs.begin() != &MLoc)
           Out << ", ";
         switch (MLoc.Kind) {
         case MachineLocKind::RegisterKind:
           Out << printReg(MLoc.Value.RegNo, TRI);
           break;
         case MachineLocKind::SpillLocKind:
           Out << printReg(MLoc.Value.SpillLocation.SpillBase, TRI);
           Out << "[" << MLoc.Value.SpillLocation.SpillOffset.getFixed() << " + "
               << MLoc.Value.SpillLocation.SpillOffset.getScalable()
               << "x vscale"
               << "]";
           break;
         case MachineLocKind::ImmediateKind:
           Out << MLoc.Value.Immediate;
           break;
+        case MachineLocKind::WasmLocKind: {
+          if (TII) {
+            auto Indices = TII->getSerializableTargetIndices();
+            auto Found =
+                find_if(Indices, [&](const std::pair<int, const char *> &I) {
+                  return I.first == MLoc.Value.WasmLocation.Index;
+                });
+            assert(Found != Indices.end());
+            Out << Found->second;
+            if (MLoc.Value.WasmLocation.Offset > 0)
+              Out << " + " << MLoc.Value.WasmLocation.Offset;
+          } else {
+            Out << "WasmLoc";
+          }
+          break;
+        }
         case MachineLocKind::InvalidKind:
           llvm_unreachable("Invalid VarLoc in dump method");
         }
       }
 
       Out << ", \"" << Var.getVariable()->getName() << "\", " << *Expr << ", ";
       if (Var.getInlinedAt())
         Out << "!" << Var.getInlinedAt()->getMetadataID() << ")\n";
LocIndices insert(const VarLoc &VL) {
       // unique location, while all SpillLocs use a single bucket, and any EV
       // VarLocs use only the Backup bucket or none at all (except the
       // compulsory entry at the universal location index). LocIndices will
       // always have an index at the universal location index as the last index.
       if (VL.EVKind == VarLoc::EntryValueLocKind::NonEntryValueKind) {
         VL.getDescribingRegs(Locations);
         assert(all_of(Locations,
                       [](auto RegNo) {
                         return RegNo < LocIndex::kFirstInvalidRegLocation;
                       }) &&
                "Physreg out of range?");
         if (VL.containsSpillLocs()) {
           LocIndex::u32_location_t Loc = LocIndex::kSpillLocation;
           Locations.push_back(Loc);
         }
       } else if (VL.EVKind != VarLoc::EntryValueLocKind::EntryValueKind) {
         LocIndex::u32_location_t Loc = LocIndex::kEntryValueBackupLocation;
for (const MachineBasicBlock &BB : MF) {
     if (L.empty())
       continue;
     SmallVector<VarLoc, 32> VarLocs;
     collectAllVarLocs(VarLocs, L, VarLocIDs);
     Out << "MBB: " << BB.getNumber() << ":\n";
     for (const VarLoc &VL : VarLocs) {
       Out << " Var: " << VL.Var.getVariable()->getName();
       Out << " MI: ";
-      VL.dump(TRI, Out);
+      VL.dump(TRI, TII, Out);
     }
   }
   Out << "\n";
 }
 #endif
 
 VarLocBasedLDV::VarLoc::SpillLoc
 VarLocBasedLDV::extractSpillBaseRegAndOffset(const MachineInstr &MI) {
void VarLocBasedLDV::transferDebugValue(const MachineInstr &MI,
   if (Var->isParameter() && EntryValBackupID) {
     const VarLoc &EntryVL = VarLocIDs[EntryValBackupID->back()];
     removeEntryValue(MI, OpenRanges, VarLocIDs, EntryVL, EntryValTransfers,
                      RegSetInstrs);
   }
 
   if (all_of(MI.debug_operands(), [](const MachineOperand &MO) {
         return (MO.isReg() && MO.getReg()) || MO.isImm() || MO.isFPImm() ||
-               MO.isCImm();
+               MO.isCImm() || MO.isTargetIndex();
       })) {
     // Use normal VarLoc constructor for registers and immediates.
     VarLoc VL(MI);
     // End all previous ranges of VL.Var.
     OpenRanges.erase(VL);
 
     LocIndices IDs = VarLocIDs.insert(VL);
     // Add the VarLoc to OpenRanges from this DBG_VALUE.
case TransferKind::TransferCopy: {
     assert(NewReg &&
            "No register supplied when handling a copy of a debug value");
     // Create a DBG_VALUE instruction to describe the Var in its new
     // register location.
     VarLoc VL = VarLoc::CreateCopyLoc(OldVarLoc, OldLoc, NewReg);
     ProcessVarLoc(VL);
     LLVM_DEBUG({
       dbgs() << "Creating VarLoc for register copy:";
-      VL.dump(TRI);
+      VL.dump(TRI, TII);
     });
     return;
   }
   case TransferKind::TransferSpill: {
     // Create a DBG_VALUE instruction to describe the Var in its spilled
     // location.
     VarLoc::SpillLoc SpillLocation = extractSpillBaseRegAndOffset(MI);
     VarLoc VL = VarLoc::CreateSpillLoc(
         OldVarLoc, OldLoc, SpillLocation.SpillBase, SpillLocation.SpillOffset);
     ProcessVarLoc(VL);
     LLVM_DEBUG({
       dbgs() << "Creating VarLoc for spill:";
-      VL.dump(TRI);
+      VL.dump(TRI, TII);
     });
     return;
   }
   case TransferKind::TransferRestore: {
     assert(NewReg &&
            "No register supplied when handling a restore of a debug value");
     // DebugInstr refers to the pre-spill location, therefore we can reuse
     // its expression.
     VarLoc VL = VarLoc::CreateCopyLoc(OldVarLoc, OldLoc, NewReg);
     ProcessVarLoc(VL);
     LLVM_DEBUG({
       dbgs() << "Creating VarLoc for restore:";
-      VL.dump(TRI);
+      VL.dump(TRI, TII);
     });
     return;
   }
   }
   llvm_unreachable("Invalid transfer kind");
 }
 
 /// A definition of a register may mark the end of a range.
bool VarLocBasedLDV::transferTerminator(MachineBasicBlock *CurMBB,
                                          const VarLocMap &VarLocIDs) {
   bool Changed = false;
   LLVM_DEBUG({
     VarVec VarLocs;
     OpenRanges.getUniqueVarLocs(VarLocs, VarLocIDs);
     for (VarLoc &VL : VarLocs) {
       // Copy OpenRanges to OutLocs, if not already present.
       dbgs() << "Add to OutLocs in MBB #" << CurMBB->getNumber() << ":  ";
-      VL.dump(TRI);
+      VL.dump(TRI, TII);
     }
   });
   VarLocSet &VLS = getVarLocsInMBB(CurMBB, OutLocs);
   Changed = VLS != OpenRanges.getVarLocs();
   // New OutLocs set may be different due to spill, restore or register
   // copy instruction processing.
   if (Changed)
     VLS = OpenRanges.getVarLocs();
if (MI.getDebugExpression()->getNumElements() > 0)
     return false;
 
   return true;
 }
 
 /// Collect all register defines (including aliases) for the given instruction.
 static void collectRegDefs(const MachineInstr &MI, DefinedRegsSet &Regs,
                            const TargetRegisterInfo *TRI) {
-  for (const MachineOperand &MO : MI.operands())
-    if (MO.isReg() && MO.isDef() && MO.getReg())
+  for (const MachineOperand &MO : MI.operands()) {
+    if (MO.isReg() && MO.isDef() && MO.getReg() &&
+        Register::isPhysicalRegister(MO.getReg())) {
+      Regs.insert(MO.getReg());
       for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI)
         Regs.insert(*AI);
     }
+  }
+}
 
 /// This routine records the entry values of function parameters. The values
 /// could be used as backup values. If we loose the track of some unmodified
 /// parameters, the backup values will be used as a primary locations.
 void VarLocBasedLDV::recordEntryValue(const MachineInstr &MI,
                                        const DefinedRegsSet &DefinedRegs,
                                        OpenRangesSet &OpenRanges,
                                        VarLocMap &VarLocIDs) {

 
 /// Calculate the liveness information for the given machine function and
 /// extend ranges across basic blocks.
 bool VarLocBasedLDV::ExtendRanges(MachineFunction &MF,
                                   MachineDominatorTree *DomTree,
                                   TargetPassConfig *TPC, unsigned InputBBLimit,
                                   unsigned InputDbgValLimit) {
   (void)DomTree;
-  LLVM_DEBUG(dbgs() << "\nDebug Range Extension\n");
+  LLVM_DEBUG(dbgs() << "\nDebug Range Extension: " << MF.getName() << "\n");
 
   if (!MF.getFunction().getSubprogram())
     // VarLocBaseLDV will already have removed all DBG_VALUEs.
     return false;
 
   // Skip functions from NoDebug compilation units.
   if (MF.getFunction().getSubprogram()->getUnit()->getEmissionKind() ==
       DICompileUnit::NoDebug)

llvm/test/DebugInfo/WebAssembly/live-debug-values.mir

+# RUN: llc -run-pass livedebugvalues %s -o - | FileCheck %s
+
+# Test if LiveDebugValue analysis works on Wasm.
+
+--- |
+  target triple = "wasm32-unknown-unknown"
+
+  define void @test_consts() !dbg !5 {
+    call void @llvm.dbg.value(metadata i32 0, metadata !9, metadata !DIExpression()), !dbg !10
+    call void @llvm.dbg.value(metadata i32 0, metadata !11, metadata !DIExpression()), !dbg !10
+    call void @llvm.dbg.value(metadata i32 0, metadata !12, metadata !DIExpression()), !dbg !10
+    call void @llvm.dbg.value(metadata i32 0, metadata !13, metadata !DIExpression()), !dbg !10
+    ret void
+  }
+
+  define void @test_target_indices() !dbg !14 {
+    call void @llvm.dbg.value(metadata i32 0, metadata !15, metadata !DIExpression()), !dbg !16
+    call void @llvm.dbg.value(metadata i32 0, metadata !17, metadata !DIExpression()), !dbg !16
+    call void @llvm.dbg.value(metadata i32 0, metadata !18, metadata !DIExpression()), !dbg !16
+    call void @llvm.dbg.value(metadata i32 0, metadata !19, metadata !DIExpression()), !dbg !16
+    call void @llvm.dbg.value(metadata i32 0, metadata !20, metadata !DIExpression()), !dbg !16
+    ret void
+  }
+
+  declare void @llvm.dbg.value(metadata, metadata, metadata)
+
+  !llvm.dbg.cu = !{!0}
+  !llvm.module.flags = !{!2, !3, !4}
+
+  !0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, emissionKind: FullDebug)
+  !1 = !DIFile(filename: "test.c", directory: "")
+  !2 = !{i32 7, !"Dwarf Version", i32 5}
+  !3 = !{i32 2, !"Debug Info Version", i32 3}
+  !4 = !{i32 1, !"wchar_size", i32 4}
+  !5 = distinct !DISubprogram(name: "test_consts", scope: !1, file: !1, line: 1, type: !6, scopeLine: 1, unit: !0)
+  ; CHECK: ![[T0_SP:[0-9]+]] = distinct !DISubprogram(name: "test_consts"
+  !6 = !DISubroutineType(types: !7)
+  !7 = !{!8}
+  !8 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+  !9 = !DILocalVariable(name: "var0", scope: !5, file: !1, line: 2, type: !8)
+  ; CHECK: ![[T0_VAR0:[0-9]+]] = !DILocalVariable(name: "var0", scope: ![[T0_SP]]
+  !10 = !DILocation(line: 0, scope: !5)
+  !11 = !DILocalVariable(name: "var1", scope: !5, file: !1, line: 2, type: !8)
+  ; CHECK: ![[T0_VAR1:[0-9]+]] = !DILocalVariable(name: "var1", scope: ![[T0_SP]]
+  !12 = !DILocalVariable(name: "var2", scope: !5, file: !1, line: 2, type: !8)
+  ; CHECK: ![[T0_VAR2:[0-9]+]] = !DILocalVariable(name: "var2", scope: ![[T0_SP]]
+  !13 = !DILocalVariable(name: "var3", scope: !5, file: !1, line: 2, type: !8)
+  ; CHECK: ![[T0_VAR3:[0-9]+]] = !DILocalVariable(name: "var3", scope: ![[T0_SP]]
+  !14 = distinct !DISubprogram(name: "test_target_indices", scope: !1, file: !1, line: 10, type: !6, scopeLine: 1, unit: !0)
+  ; CHECK: ![[T1_SP:[0-9]+]] = distinct !DISubprogram(name: "test_target_indices"
+  !15 = !DILocalVariable(name: "var0", scope: !14, file: !1, line: 11, type: !8)
+  ; CHECK: ![[T1_VAR0:[0-9]+]] = !DILocalVariable(name: "var0", scope: ![[T1_SP]]
+  !16 = !DILocation(line: 10, scope: !14)
+  !17 = !DILocalVariable(name: "var1", scope: !14, file: !1, line: 11, type: !8)
+  ; CHECK: ![[T1_VAR1:[0-9]+]] = !DILocalVariable(name: "var1", scope: ![[T1_SP]]
+  !18 = !DILocalVariable(name: "var2", scope: !14, file: !1, line: 11, type: !8)
+  ; CHECK: ![[T1_VAR2:[0-9]+]] = !DILocalVariable(name: "var2", scope: ![[T1_SP]]
+  !19 = !DILocalVariable(name: "var3", scope: !14, file: !1, line: 11, type: !8)
+  ; CHECK: ![[T1_VAR3:[0-9]+]] = !DILocalVariable(name: "var3", scope: ![[T1_SP]]
+  !20 = !DILocalVariable(name: "var4", scope: !14, file: !1, line: 11, type: !8)
+  ; CHECK: ![[T1_VAR4:[0-9]+]] = !DILocalVariable(name: "var4", scope: ![[T1_SP]]
+...
+
+---
+# var0: Its debug value is set once in bb.0 and valid throughout the function.
+#       So a new DBG_VALUE will be added to the beginnings of all other BBs
+#       (bb.1, bb.2, and bb.3).
+# var1: Its debug value is set in bb.0, but is reset to no info in bb.1. So a
+#       new DBG_VALUE will be added in the beginning of bb.1 and bb.2, but bb.3
+#       will not, because its two predecesors (bb.1 and bb.2) have different
+#       debug values.
+# var2: Its debug value is set both in bb.1 and bb.2 with the same value. bb.3
+#       will have a new DBG_VALUE representing that value.
+# var3: Its debug value is set both in bb.1 and bb.2 but with different values.
+#       bb.3 will NOT have a new DBG_VALUE instruction because its predecessors
+#       don't agree on a value.
+# CHECK-LABEL: name: test_consts
+name: test_consts
+liveins:
+  - { reg: '$arguments' }
+body: |
+  bb.0:
+    successors: %bb.1, %bb.2
+    liveins: $arguments
+    DBG_VALUE 10, $noreg, !9, !DIExpression(), debug-location !10
+    DBG_VALUE 20, $noreg, !11, !DIExpression(), debug-location !10
+    %0:i32 = CONST_I32 1, implicit-def $arguments
+    BR_IF %bb.2, %0:i32, implicit-def $arguments
+
+  ; CHECK: bb.1:
+  ; CHECK-DAG: DBG_VALUE 10, $noreg, ![[T0_VAR0]]
+  ; CHECK-DAG: DBG_VALUE 20, $noreg, ![[T0_VAR1]]
+  bb.1:
+  ; predecessors: %bb.0
+    successors: %bb.3
+    DBG_VALUE $noreg, $noreg, !11, !DIExpression(), debug-location !10
+    DBG_VALUE 30, $noreg, !12, !DIExpression(), debug-location !10
+    DBG_VALUE 30, $noreg, !13, !DIExpression(), debug-location !10
+    BR %bb.3, implicit-def $arguments
+
+  ; CHECK: bb.2:
+  ; CHECK-DAG: DBG_VALUE 10, $noreg, ![[T0_VAR0]]
+  ; CHECK-DAG: DBG_VALUE 20, $noreg, ![[T0_VAR1]]
+  bb.2:
+  ; predecessors: %bb.0
+    successors: %bb.3
+    DBG_VALUE 30, $noreg, !12, !DIExpression(), debug-location !10
+    DBG_VALUE 40, $noreg, !13, !DIExpression(), debug-location !10
+    BR %bb.3, implicit-def $arguments
+
+  ; CHECK: bb.3:
+  ; CHECK-DAG: DBG_VALUE 10, $noreg, ![[T0_VAR0]]
+  ; CHECK-DAG: DBG_VALUE 30, $noreg, ![[T0_VAR2]]
+  ; CHECK-NOT: DBG_VALUE {{[0-9]+}}, $noreg, ![[T0_VAR1]]
+  ; CHECK-NOT: DBG_VALUE {{[0-9]+}}, $noreg, ![[T0_VAR3]]
+  bb.3:
+  ; predecessors: %bb.1, %bb.2
+    RETURN implicit-def dead $arguments
+...
+
+---
+# var0: Its debug value is set once in bb.0 and valid throughout the function.
+#       So a new DBG_VALUE will be added to the beginnings of all other BBs
+#       (bb.1, bb.2, and bb.3).
+# var1: Its debug value is set in bb.0, but is reset to no info back later in
+#       bb.0. So no DBG_VALUEs will be added in other BBs.
+# var2: Its debug value is set both in bb.1 and bb.2 with the same value (The
+#       same kind (local) and same local index). bb.3 will have a new DBG_VALUE
+#       representing that value.
+# var3: Its debug value is set both in bb.1 and bb.2 but with different values.
+#       Both are locals, but their indices are different. bb.3 will NOT have a
+#       new DBG_VALUE instruction because its predecessors don't agree on a
+#       value.
+# var4: Its debug value is set both in bb.1 and bb.2 but with different values.
+#       They have different kinds; one is a local and the other is a stack
+#       operand. (Their index is the same, but it doesn't matter.) bb.3 will NOT
+#       have a new DBG_VALUE instruction because its predecessors don't agree on
+#       a value.
+# CHECK-LABEL: name: test_target_indices
+name: test_target_indices
+liveins:
+  - { reg: '$arguments' }
+body: |
+  bb.0:
+    successors: %bb.1, %bb.2
+    liveins: $arguments
+    DBG_VALUE target-index(wasm-local), $noreg, !15, !DIExpression(), debug-location !16
+    DBG_VALUE target-index(wasm-operand-stack) + 2, $noreg, !17, !DIExpression(), debug-location !16
+    %0:i32 = CONST_I32 1, implicit-def $arguments
+    DBG_VALUE $noreg, $noreg, !17, !DIExpression(), debug-location !16
+    BR_IF %bb.2, %0:i32, implicit-def $arguments
+
+  ; CHECK: bb.1:
+  ; CHECK: DBG_VALUE target-index(wasm-local), $noreg, ![[T1_VAR0]]
+  bb.1:
+  ; predecessors: %bb.0
+    successors: %bb.3
+    DBG_VALUE target-index(wasm-local) + 2, $noreg, !18, !DIExpression(), debug-location !16
+    DBG_VALUE target-index(wasm-local) + 3, $noreg, !19, !DIExpression(), debug-location !16
+    DBG_VALUE target-index(wasm-operand-stack) + 3, $noreg, !20, !DIExpression(), debug-location !16
+    BR %bb.3, implicit-def $arguments
+
+  ; CHECK: bb.2:
+  ; CHECK: DBG_VALUE target-index(wasm-local), $noreg, ![[T1_VAR0]]
+  bb.2:
+  ; predecessors: %bb.0
+    successors: %bb.3
+    DBG_VALUE target-index(wasm-local) + 2, $noreg, !18, !DIExpression(), debug-location !16
+    DBG_VALUE target-index(wasm-local) + 5, $noreg, !19, !DIExpression(), debug-location !16
+    DBG_VALUE target-index(wasm-local) + 3, $noreg, !20, !DIExpression(), debug-location !16
+    BR %bb.3, implicit-def $arguments
+
+  ; CHECK: bb.3:
+  ; CHECK-DAG: DBG_VALUE target-index(wasm-local), $noreg, ![[T1_VAR0]]
+  ; CHECK-DAG: DBG_VALUE target-index(wasm-local) + 2, $noreg, ![[T1_VAR2]]
+  ; CHECK-NOT: DBG_VALUE target-index(wasm-local){{.*}}, $noreg, ![[T1_VAR3]]
+  ; CHECK-NOT: DBG_VALUE target-index(wasm-local){{.*}}, $noreg, ![[T1_VAR4]]
+  bb.3:
+  ; predecessors: %bb.1, %bb.2
+    RETURN implicit-def dead $arguments
+...