[WebAssembly] Fix register use-def in FixIrreducibleControlFlow

[aheejin]

Summary

FixIrreducibleControlFlow pass adds dispatch blocks with a br_table
that has multiple predecessors and successors, because it serves as
something like a traffic hub for BBs. As a result of this, there can be
register uses that are not dominated by a def in every path from the
entry block. For example, suppose register %a is defined in BB1 and used
in BB2, and there is a single path from BB1 and BB2:

BB1 -> ... -> BB2

After FixIrreducibleControlFlow runs, there can be a dispatch block
between these two BBs:

BB1 -> ... -> Dispatch -> ... -> BB2

And this dispatch block has multiple predecessors, now
there is a path to BB2 that does not first visit BB1, and in that path
%a is not dominated by a def anymore.

To fix this problem, we have been adding IMPLICIT_DEFs to all
registers in PrepareForLiveInternals pass, and then remove unnecessary
ones in OptimizeLiveIntervals pass after computing LiveIntervals. But
FixIrreducibleControlFlow pass itself ends up violating register use-def
relationship, resulting in invalid code. This was OK so far because
MIR verifier apparently didn't check this in validation. But @arsenm
fixed this and it caught this bug in validation
(https://github.com/llvm/llvm-project/issues/55249).

This CL moves the IMPLICIT_DEF adding routine from
PrepareForLiveInternals to FixIrreducibleControlFlow. We only run it
when FixIrreducibleControlFlow changes the code. And then
PrepareForLiveInternals doesn't do anything other than setting
TracksLiveness property, which is a prerequisite for running
LiveIntervals analysis, which is required by the next pass
OptimizeLiveIntervals.

But in our backend we don't seem to do anything that invalidates this up
until OptimizeLiveIntervals, and I'm not sure why we are calling
invalidateLiveness in ReplacePhysRegs pass, because what that pass
does is to replace physical registers with virtual ones 1-to-1. I
deleted the invalidateLiveness call there and we don't need to set
that flag explicitly, which obviates all the need for
PrepareForLiveInternals.

(By the way, This 'Liveness' here is different from LiveIntervals
analysis. Setting this only means BBs' live-in info is correct, all uses
are dominated by defs, kill flag is conservatively correct, which
means if there is a kill flag set it should be the last use. See
https://github.com/llvm/llvm-project/blob/2a0837aab1489c88efb03784e34c4dc9f2e28302/llvm/include/llvm/CodeGen/MachineFunction.h#L125-L134
for details.)

So this CL removes PrepareForLiveInternals pass altogether. Something
similar to this was attempted by D56091 long ago but that came short of
actually removing the pass, and I couldn't land it because
FixIrreducibleControlFlow violated use-def relationship, which this CL
fixes.

This doesn't change output in any meaningful way. All test changes
except irreducible-cfg.mir are register numbering.

Also this will likely to reduce compilation time, because we have been
adding IMPLICIT_DEF for all registers every time -O2 is given, but
now we do that only when there is irreducible control flow, which is
rare.

Fixes https://github.com/llvm/llvm-project/issues/55249.

[aheejin]

llvm/lib/Target/WebAssembly/WebAssemblyReplacePhysRegs.cpp

75–77

I'm not sure why these were here. This pass replaces physical registers with virtual ones, and this is one-to-one relationship so I think this pass doesn't change anything in liveness or SSA.

[aheejin]

Remove a stray line

[dschuff]

This looks great! I guess the test for this will be when the fix for the MIR verifier lands, and it will start throwing errors if this somehow breaks, right?

llvm/lib/Target/WebAssembly/WebAssemblyReplacePhysRegs.cpp

115

Should this go in the FixIrreducibleControlFlow pass? It's that pass that sets up the implicit defs correctly and not this one, right?

[kripken]

llvm/lib/Target/WebAssembly/WebAssemblyFixIrreducibleControlFlow.cpp

533

I'm not that familiar with LLVM, but I am guessing that this code will add an implicit def for each register? That is, this is a change over all the registers used in the function, as opposed to adding definitions in specific blocks for specific registers, and at the top of the function it writes a 0 to all of them?

If so, then I wonder if this has performance implications? Specifically I worry about a very large function that has a tiny irreducible part nested in it. Would this increase live ranges in the entire function?

Even if it does, maybe other passes are smart enough to not be limited by it? fwiw, after LLVM, in Binaryen this should not be a problem (adding more local.sets at the top of the function has no effect - we already assume all wasm locals have an initial set of 0).

If this is a potential problem in LLVM, then I think the minimal thing to do here is to define all registers that pass through the dispatch block, in the dispatch block.

(Apologies if I've misunderstood the code here...)

[aheejin]

llvm/lib/Target/WebAssembly/WebAssemblyFixIrreducibleControlFlow.cpp

533

I'm not that familiar with LLVM, but I am guessing that this code will add an implicit def for each register? That is, this is a change over all the registers used in the function, as opposed to adding definitions in specific blocks for specific registers, and at the top of the function it writes a 0 to all of them?

If so, then I wonder if this has performance implications? Specifically I worry about a very large function that has a tiny irreducible part nested in it. Would this increase live ranges in the entire function?

The register number changes in our test cases stemmed from moving ARGUMENT_ instructions and not from IMPLICIT_DEF itself. We do this after adding IMPLICIT_DEFs because ARGUMENT_ insts should be before all IMPLICIT_DEFs. While doing so the order of ARGUMENT_ instructions can change and it looks it can result in register number differences later.

// Move ARGUMENT_* instructions to the top of the entry block, so that their
// liveness reflects the fact that these really are live-in values.
for (MachineInstr &MI : llvm::make_early_inc_range(Entry)) {
  if (WebAssembly::isArgument(MI.getOpcode())) {
    MI.removeFromParent();
    Entry.insert(Entry.begin(), &MI);
  }
}

I don't think number changes will affect performance in any meaningful way, especially in the optimized build. OptimizeLiveIntervals pass removes all unnecesary IMPLICIT_DEFs, so the live ranges will not be extended: https://github.com/llvm/llvm-project/blob/4205f4aba4aff74fa7681c3f991ef5fdaed48d35/llvm/lib/Target/WebAssembly/WebAssemblyOptimizeLiveIntervals.cpp#L105-L116

Even if it does, maybe other passes are smart enough to not be limited by it? fwiw, after LLVM, in Binaryen this should not be a problem (adding more local.sets at the top of the function has no effect - we already assume all wasm locals have an initial set of 0).

We have OptimizeLiveIntervals pass that removes unnecessary IMPLICIT_DEFs, and passes like RegColoring tries to reduce the number of registers used.

If this is a potential problem in LLVM, then I think the minimal thing to do here is to define all registers that pass through the dispatch block, in the dispatch block.

This can rewrite existing values, which can lead to incorrect code, I think? Also I can't think of any benefits, and we may need to do this multiple times if there are more than one dispatch block.

llvm/lib/Target/WebAssembly/WebAssemblyReplacePhysRegs.cpp

115

It can go in any pass before OptimizeLiveIntervals pass. We can put that in FixIrreducibleCFG, but I'm not sure if that pass is any special, because every pass preserves correct register def-use relationship (except for FixIrreducibleControlFlow, until now) and IMPLICIT_DEF is just a way of preserving it in that pass. Also, note that while we only add IMPLICIT_DEFs in case of irreducible CFGs, we have to set this for every function, whether or not it is irreducible.

[kripken]

llvm/lib/Target/WebAssembly/WebAssemblyFixIrreducibleControlFlow.cpp

533

Sounds good, thanks for the details!

This can rewrite existing values, which can lead to incorrect code, I think? Also I can't think of any benefits, and we may need to do this multiple times if there are more than one dispatch block.

Hmm, yeah, it's definitely not as simple as I was thinking...

[arsenm]

llvm/lib/Target/WebAssembly/WebAssemblyReplacePhysRegs.cpp

115

This should move into the pass's getSetProperties/getClearedProperties

[aheejin]

Add getRequiredProperties call to OptimizeLiveIntervals

llvm/lib/Target/WebAssembly/WebAssemblyReplacePhysRegs.cpp

115

Thanks for the info! I wasn't aware of these APIs. But come to think about it, I don't think we even need that, because I deleted invalidateLiveness call in this pass above. I'm not sure why it was there in the first place, because we don't do anything to invalidate liveness here; what this pass does is to replace physical registers with virtual ones 1-to-1, which has nothing to do with liveness.

Also I removed invalidateLiveness call in FixIrreducibleControlFlow pass; we now add IMPLICIT_DEFs there so it should be fine.

So in short we don't invalidate liveness up until CFGSort/CFGStackify, which is later than this and near the end of the pipeline, and the thing we invalidate there is kill flag and not use-def relationship. So I don't think we need to set this anywhere.

But to make things clear, I'll instead add this to WebAssemblyOptimizeLiveIntervals, the next pass, to make sure what this pass requires.

MachineFunctionProperties getRequiredProperties() const override {
  return MachineFunctionProperties().set(
      MachineFunctionProperties::Property::TracksLiveness);
}

[dschuff]

llvm/lib/Target/WebAssembly/WebAssemblyReplacePhysRegs.cpp

115

so you're saying, none of these passes now either set or clear the property, they just preserve it; so there's no need to mark it explicitly (other than ReplacePhysRegs where we actually remove the physregs). I think that makes sense.

[aheejin]

Remove getSetProperties

[aheejin]

llvm/lib/Target/WebAssembly/WebAssemblyReplacePhysRegs.cpp

115

Oh, sorry, that's not what I meant. I made the confusion because I also added getSetProperties.. That was an incorrect snippet I added while experimenting.

So you're saying, none of these passes now either set or clear the property, they just preserve it;

This is correct.

so there's no need to mark it explicitly (other than ReplacePhysRegs where we actually remove the physregs).

I believe even ReplacePhysRegs doesn't need to remove this property. Note that I deleted the call to invalidateLiveness on line 77 in this file. So we don't need to set the property again here, meaning we don't need go call getSetProperties. This was added in the diff, which made the confusion. I deleted the call.

[dschuff]

llvm/lib/Target/WebAssembly/WebAssemblyReplacePhysRegs.cpp

115

I believe even ReplacePhysRegs doesn't need to remove this property. Note that I deleted the call to invalidateLiveness on line 77 in this file. So we don't need to set the property again here, meaning we don't need go call getSetProperties. This was added in the diff, which made the confusion. I deleted the call.

Sorry I actually was seeing that in the last patch set it *added* the property. I assumed that was because it was only the physregs that may have been violating it. But yes it still makes sense that none of the passes needs to set or clear the property, and mark OptimizeLiveIntervals as requiring it.

[aheejin]

llvm/lib/Target/WebAssembly/WebAssemblyReplacePhysRegs.cpp

115

Yeah that was confusing. So these register liveins only apply to physical registers, so after we remove all physical registers here, we don't violate livein requirements for sure. But were we violating the requirements before, even if we were using physical registers before this pass? Those physical registers are sp and fp, and they are added in PrologEpilogInserter or somewhere, and I think that pass should take care of preserving that. And a brief 1 min look on that pass looks like it does. Even if it doesn't, it's surely not that we should remove the property here; we should have rather set it here. (But as I said, we didn't remove it anywhere, so we don't need to set it again)

[dschuff]

llvm/lib/Target/WebAssembly/WebAssemblyReplacePhysRegs.cpp

115

yeah, makes sense now. thanks for checking sp and fp. This patchset LGTM.

[arsenm]

llvm/lib/Target/WebAssembly/WebAssemblyReplacePhysRegs.cpp

115

sp and fp are presumably reserved registers, and thus not added to liveins lists or have tracked liveness anyway

llvm/lib/Target/WebAssembly/CMakeLists.txt

add_llvm_target(WebAssemblyCodeGen
   WebAssemblyLowerRefTypesIntPtrConv.cpp
   WebAssemblyMachineFunctionInfo.cpp
   WebAssemblyMCInstLower.cpp
   WebAssemblyMCLowerPrePass.cpp
   WebAssemblyNullifyDebugValueLists.cpp
   WebAssemblyOptimizeLiveIntervals.cpp
   WebAssemblyOptimizeReturned.cpp
   WebAssemblyPeephole.cpp
-  WebAssemblyPrepareForLiveIntervals.cpp
   WebAssemblyRegisterInfo.cpp
   WebAssemblyRegColoring.cpp
   WebAssemblyRegNumbering.cpp
   WebAssemblyRegStackify.cpp
   WebAssemblyReplacePhysRegs.cpp
   WebAssemblyRuntimeLibcallSignatures.cpp
   WebAssemblySelectionDAGInfo.cpp
   WebAssemblySetP2AlignOperands.cpp

llvm/lib/Target/WebAssembly/WebAssembly.h

 FunctionPass *createWebAssemblyISelDag(WebAssemblyTargetMachine &TM,
                                        CodeGenOpt::Level OptLevel);
 FunctionPass *createWebAssemblyArgumentMove();
 FunctionPass *createWebAssemblySetP2AlignOperands();
 
 // Late passes.
 FunctionPass *createWebAssemblyReplacePhysRegs();
 FunctionPass *createWebAssemblyNullifyDebugValueLists();
-FunctionPass *createWebAssemblyPrepareForLiveIntervals();
 FunctionPass *createWebAssemblyOptimizeLiveIntervals();
 FunctionPass *createWebAssemblyMemIntrinsicResults();
 FunctionPass *createWebAssemblyRegStackify();
 FunctionPass *createWebAssemblyRegColoring();
 FunctionPass *createWebAssemblyFixBrTableDefaults();
 FunctionPass *createWebAssemblyFixIrreducibleControlFlow();
 FunctionPass *createWebAssemblyLateEHPrepare();
 FunctionPass *createWebAssemblyCFGSort();

 void initializeWebAssemblyAddMissingPrototypesPass(PassRegistry &);
 void initializeWebAssemblyLowerEmscriptenEHSjLjPass(PassRegistry &);
 void initializeFixFunctionBitcastsPass(PassRegistry &);
 void initializeOptimizeReturnedPass(PassRegistry &);
 void initializeWebAssemblyArgumentMovePass(PassRegistry &);
 void initializeWebAssemblySetP2AlignOperandsPass(PassRegistry &);
 void initializeWebAssemblyReplacePhysRegsPass(PassRegistry &);
 void initializeWebAssemblyNullifyDebugValueListsPass(PassRegistry &);
-void initializeWebAssemblyPrepareForLiveIntervalsPass(PassRegistry &);
 void initializeWebAssemblyOptimizeLiveIntervalsPass(PassRegistry &);
 void initializeWebAssemblyMemIntrinsicResultsPass(PassRegistry &);
 void initializeWebAssemblyRegStackifyPass(PassRegistry &);
 void initializeWebAssemblyRegColoringPass(PassRegistry &);
 void initializeWebAssemblyFixBrTableDefaultsPass(PassRegistry &);
 void initializeWebAssemblyFixIrreducibleControlFlowPass(PassRegistry &);
 void initializeWebAssemblyLateEHPreparePass(PassRegistry &);
 void initializeWebAssemblyExceptionInfoPass(PassRegistry &);

llvm/lib/Target/WebAssembly/WebAssemblyFixIrreducibleControlFlow.cpp

 char WebAssemblyFixIrreducibleControlFlow::ID = 0;
 INITIALIZE_PASS(WebAssemblyFixIrreducibleControlFlow, DEBUG_TYPE,
                 "Removes irreducible control flow", false, false)
 
 FunctionPass *llvm::createWebAssemblyFixIrreducibleControlFlow() {
   return new WebAssemblyFixIrreducibleControlFlow();
 }
 
+// Test whether the given register has an ARGUMENT def.
+static bool hasArgumentDef(unsigned Reg, const MachineRegisterInfo &MRI) {
+  for (const auto &Def : MRI.def_instructions(Reg))
+    if (WebAssembly::isArgument(Def.getOpcode()))
+      return true;
+  return false;
+}
+
+// Add a register definition with IMPLICIT_DEFs for every register to cover for
+// register uses that don't have defs in every possible path.
+// TODO: This is fairly heavy-handed; find a better approach.
+static void addImplicitDefs(MachineFunction &MF) {
+  const MachineRegisterInfo &MRI = MF.getRegInfo();
+  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
+  MachineBasicBlock &Entry = *MF.begin();
+  for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; ++I) {
+    Register Reg = Register::index2VirtReg(I);
+
+    // Skip unused registers.
+    if (MRI.use_nodbg_empty(Reg))
+      continue;
+
+    // Skip registers that have an ARGUMENT definition.
+    if (hasArgumentDef(Reg, MRI))
+      continue;
+
+    BuildMI(Entry, Entry.begin(), DebugLoc(),
+            TII.get(WebAssembly::IMPLICIT_DEF), Reg);
+  }
+
+  // Move ARGUMENT_* instructions to the top of the entry block, so that their
+  // liveness reflects the fact that these really are live-in values.
+  for (MachineInstr &MI : llvm::make_early_inc_range(Entry)) {
+    if (WebAssembly::isArgument(MI.getOpcode())) {
+      MI.removeFromParent();
+      Entry.insert(Entry.begin(), &MI);
+    }
+  }
+}
+
 bool WebAssemblyFixIrreducibleControlFlow::runOnMachineFunction(
     MachineFunction &MF) {
   LLVM_DEBUG(dbgs() << "********** Fixing Irreducible Control Flow **********\n"
                        "********** Function: "
                     << MF.getName() << '\n');
 
   // Start the recursive process on the entire function body.
   BlockSet AllBlocks;
   for (auto &MBB : MF) {
     AllBlocks.insert(&MBB);
   }
 
   if (LLVM_UNLIKELY(processRegion(&*MF.begin(), AllBlocks, MF))) {
     // We rewrote part of the function; recompute relevant things.
-    MF.getRegInfo().invalidateLiveness();
     MF.RenumberBlocks();
+    // Now we've inserted dispatch blocks, some register uses can have incoming
+    // paths without a def. For example, before this pass register %a was
+    // defined in BB1 and used in BB2, and there was only one path from BB1 and
+    // BB2. But if this pass inserts a dispatch block having multiple
+    // predecessors between the two BBs, now there are paths to BB2 without
+    // visiting BB1, and %a's use in BB2 is not dominated by its def. Adding
+    // IMPLICIT_DEFs to all regs is one simple way to fix it.
+    addImplicitDefs(MF);
     return true;
   }
 
   return false;
 }

llvm/lib/Target/WebAssembly/WebAssemblyOptimizeLiveIntervals.cpp

void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addPreserved<MachineBlockFrequencyInfo>();
     AU.addPreserved<SlotIndexes>();
     AU.addPreserved<LiveIntervals>();
     AU.addPreservedID(LiveVariablesID);
     AU.addPreservedID(MachineDominatorsID);
     MachineFunctionPass::getAnalysisUsage(AU);
   }
 
+  MachineFunctionProperties getRequiredProperties() const override {
+    return MachineFunctionProperties().set(
+        MachineFunctionProperties::Property::TracksLiveness);
+  }
+
   bool runOnMachineFunction(MachineFunction &MF) override;
 
 public:
   static char ID; // Pass identification, replacement for typeid
   WebAssemblyOptimizeLiveIntervals() : MachineFunctionPass(ID) {}
 };
 } // end anonymous namespace
 
if (Reg == TRI.getFrameRegister(MF) && SplitLIs.size() > 0) {
       // values through live-range splitting and stackification, it will have to
       // do.
       MF.getInfo<WebAssemblyFunctionInfo>()->setFrameBaseVreg(
           SplitLIs.back()->reg());
     }
     SplitLIs.clear();
   }
 
-  // In PrepareForLiveIntervals, we conservatively inserted IMPLICIT_DEF
+  // In FixIrreducibleControlFlow, we conservatively inserted IMPLICIT_DEF
   // instructions to satisfy LiveIntervals' requirement that all uses be
   // dominated by defs. Now that LiveIntervals has computed which of these
   // defs are actually needed and which are dead, remove the dead ones.
   for (MachineInstr &MI : llvm::make_early_inc_range(MF.front())) {
     if (MI.isImplicitDef() && MI.getOperand(0).isDead()) {
       LiveInterval &LI = LIS.getInterval(MI.getOperand(0).getReg());
       LIS.removeVRegDefAt(LI, LIS.getInstructionIndex(MI).getRegSlot());
       LIS.RemoveMachineInstrFromMaps(MI);
       MI.eraseFromParent();
     }
   }
 
   return true;
 }

llvm/lib/Target/WebAssembly/WebAssemblyPrepareForLiveIntervals.cpp

-//===- WebAssemblyPrepareForLiveIntervals.cpp - Prepare for LiveIntervals -===//
-//
-// 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
-/// Fix up code to meet LiveInterval's requirements.
-///
-/// Some CodeGen passes don't preserve LiveInterval's requirements, because
-/// they run after register allocation and it isn't important. However,
-/// WebAssembly runs LiveIntervals in a late pass. This pass transforms code
-/// to meet LiveIntervals' requirements; primarily, it ensures that all
-/// virtual register uses have definitions (IMPLICIT_DEF definitions if
-/// nothing else).
-///
-//===----------------------------------------------------------------------===//
-
-#include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
-#include "Utils/WebAssemblyUtilities.h"
-#include "WebAssembly.h"
-#include "WebAssemblyMachineFunctionInfo.h"
-#include "WebAssemblySubtarget.h"
-#include "llvm/CodeGen/MachineFunctionPass.h"
-#include "llvm/CodeGen/MachineInstrBuilder.h"
-#include "llvm/CodeGen/MachineRegisterInfo.h"
-#include "llvm/CodeGen/Passes.h"
-#include "llvm/Support/Debug.h"
-#include "llvm/Support/raw_ostream.h"
-using namespace llvm;
-
-#define DEBUG_TYPE "wasm-prepare-for-live-intervals"
-
-namespace {
-class WebAssemblyPrepareForLiveIntervals final : public MachineFunctionPass {
-public:
-  static char ID; // Pass identification, replacement for typeid
-  WebAssemblyPrepareForLiveIntervals() : MachineFunctionPass(ID) {}
-
-private:
-  StringRef getPassName() const override {
-    return "WebAssembly Prepare For LiveIntervals";
-  }
-
-  void getAnalysisUsage(AnalysisUsage &AU) const override {
-    AU.setPreservesCFG();
-    MachineFunctionPass::getAnalysisUsage(AU);
-  }
-
-  bool runOnMachineFunction(MachineFunction &MF) override;
-};
-} // end anonymous namespace
-
-char WebAssemblyPrepareForLiveIntervals::ID = 0;
-INITIALIZE_PASS(WebAssemblyPrepareForLiveIntervals, DEBUG_TYPE,
-                "Fix up code for LiveIntervals", false, false)
-
-FunctionPass *llvm::createWebAssemblyPrepareForLiveIntervals() {
-  return new WebAssemblyPrepareForLiveIntervals();
-}
-
-// Test whether the given register has an ARGUMENT def.
-static bool hasArgumentDef(unsigned Reg, const MachineRegisterInfo &MRI) {
-  for (const auto &Def : MRI.def_instructions(Reg))
-    if (WebAssembly::isArgument(Def.getOpcode()))
-      return true;
-  return false;
-}
-
-bool WebAssemblyPrepareForLiveIntervals::runOnMachineFunction(
-    MachineFunction &MF) {
-  LLVM_DEBUG({
-    dbgs() << "********** Prepare For LiveIntervals **********\n"
-           << "********** Function: " << MF.getName() << '\n';
-  });
-
-  bool Changed = false;
-  MachineRegisterInfo &MRI = MF.getRegInfo();
-  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
-  MachineBasicBlock &Entry = *MF.begin();
-
-  assert(!mustPreserveAnalysisID(LiveIntervalsID) &&
-         "LiveIntervals shouldn't be active yet!");
-
-  // We don't preserve SSA form.
-  MRI.leaveSSA();
-
-  // BranchFolding and perhaps other passes don't preserve IMPLICIT_DEF
-  // instructions. LiveIntervals requires that all paths to virtual register
-  // uses provide a definition. Insert IMPLICIT_DEFs in the entry block to
-  // conservatively satisfy this.
-  //
-  // TODO: This is fairly heavy-handed; find a better approach.
-  //
-  for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; ++I) {
-    Register Reg = Register::index2VirtReg(I);
-
-    // Skip unused registers.
-    if (MRI.use_nodbg_empty(Reg))
-      continue;
-
-    // Skip registers that have an ARGUMENT definition.
-    if (hasArgumentDef(Reg, MRI))
-      continue;
-
-    BuildMI(Entry, Entry.begin(), DebugLoc(),
-            TII.get(WebAssembly::IMPLICIT_DEF), Reg);
-    Changed = true;
-  }
-
-  // Move ARGUMENT_* instructions to the top of the entry block, so that their
-  // liveness reflects the fact that these really are live-in values.
-  for (MachineInstr &MI : llvm::make_early_inc_range(Entry)) {
-    if (WebAssembly::isArgument(MI.getOpcode())) {
-      MI.removeFromParent();
-      Entry.insert(Entry.begin(), &MI);
-    }
-  }
-
-  // Ok, we're now ready to run the LiveIntervals analysis again.
-  MF.getProperties().set(MachineFunctionProperties::Property::TracksLiveness);
-
-  return Changed;
-}

llvm/lib/Target/WebAssembly/WebAssemblyReplacePhysRegs.cpp

StringRef getPassName() const override {
     return "WebAssembly Replace Physical Registers";
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
     MachineFunctionPass::getAnalysisUsage(AU);
   }
 
+  MachineFunctionProperties getSetProperties() const override {
+    // We replace all physical registers except ARGUMENT in this pass, so there
+    // are no other physical register liveins to track.
+    return MachineFunctionProperties().set(
+        MachineFunctionProperties::Property::TracksLiveness);
+  }
+
   bool runOnMachineFunction(MachineFunction &MF) override;
 };
 } // end anonymous namespace
 
 char WebAssemblyReplacePhysRegs::ID = 0;
 INITIALIZE_PASS(WebAssemblyReplacePhysRegs, DEBUG_TYPE,
                 "Replace physical registers with virtual registers", false,
                 false)
bool WebAssemblyReplacePhysRegs::runOnMachineFunction(MachineFunction &MF) {
   });
 
   MachineRegisterInfo &MRI = MF.getRegInfo();
   auto &TRI = *MF.getSubtarget<WebAssemblySubtarget>().getRegisterInfo();
   bool Changed = false;
 
   assert(!mustPreserveAnalysisID(LiveIntervalsID) &&
          "LiveIntervals shouldn't be active yet!");
-  // We don't preserve SSA or liveness.
-  MRI.leaveSSA();
-  MRI.invalidateLiveness();
 
   for (unsigned PReg = WebAssembly::NoRegister + 1;
        PReg < WebAssembly::NUM_TARGET_REGS; ++PReg) {
     // Skip fake registers that are never used explicitly.
     if (PReg == WebAssembly::VALUE_STACK || PReg == WebAssembly::ARGUMENTS)
       continue;
 
     // Replace explicit uses of the physical register with a virtual register.
for (MachineOperand &MO :
         }
         MO.setReg(VReg);
         Changed = true;
       }
     }
   }
 
   return Changed;
 }

llvm/lib/Target/WebAssembly/WebAssemblyTargetMachine.cpp

extern "C" LLVM_EXTERNAL_VISIBILITY void LLVMInitializeWebAssemblyTarget() {
   initializeWebAssemblyAddMissingPrototypesPass(PR);
   initializeWebAssemblyLowerEmscriptenEHSjLjPass(PR);
   initializeLowerGlobalDtorsLegacyPassPass(PR);
   initializeFixFunctionBitcastsPass(PR);
   initializeOptimizeReturnedPass(PR);
   initializeWebAssemblyArgumentMovePass(PR);
   initializeWebAssemblySetP2AlignOperandsPass(PR);
   initializeWebAssemblyReplacePhysRegsPass(PR);
-  initializeWebAssemblyPrepareForLiveIntervalsPass(PR);
   initializeWebAssemblyOptimizeLiveIntervalsPass(PR);
   initializeWebAssemblyMemIntrinsicResultsPass(PR);
   initializeWebAssemblyRegStackifyPass(PR);
   initializeWebAssemblyRegColoringPass(PR);
   initializeWebAssemblyNullifyDebugValueListsPass(PR);
   initializeWebAssemblyFixIrreducibleControlFlowPass(PR);
   initializeWebAssemblyLateEHPreparePass(PR);
   initializeWebAssemblyExceptionInfoPass(PR);
void WebAssemblyPassConfig::addPreEmitPass() {
 
   // Now that we have a prologue and epilogue and all frame indices are
   // rewritten, eliminate SP and FP. This allows them to be stackified,
   // colored, and numbered with the rest of the registers.
   addPass(createWebAssemblyReplacePhysRegs());
 
   // Preparations and optimizations related to register stackification.
   if (getOptLevel() != CodeGenOpt::None) {
-    // LiveIntervals isn't commonly run this late. Re-establish preconditions.
-    addPass(createWebAssemblyPrepareForLiveIntervals());
-
     // Depend on LiveIntervals and perform some optimizations on it.
     addPass(createWebAssemblyOptimizeLiveIntervals());
 
     // Prepare memory intrinsic calls for register stackifying.
     addPass(createWebAssemblyMemIntrinsicResults());
 
     // Mark registers as representing wasm's value stack. This is a key
     // code-compression technique in WebAssembly. We run this pass (and

llvm/test/CodeGen/WebAssembly/irreducible-cfg.mir

liveins:
   - { reg: '$arguments' }
 body: |
   bb.0.pred0:
     successors: %bb.1, %bb.2
     liveins: $arguments
     %0:i32 = CONST_I32 100, implicit-def $arguments
     BR_IF %bb.2, %0:i32, implicit-def $arguments
   ; CHECK: bb.0.pred0:
+    ; CHECK:      %1:i32 = IMPLICIT_DEF
+    ; CHECK-NEXT: %0:i32 = IMPLICIT_DEF
     ; CHECK:      BR_IF %bb.2, %0, implicit-def $arguments
 
   bb.1.pred1:
   ; predecessors: %bb.1
     successors: %bb.2, %bb.3
     BR_IF %bb.3, %0:i32, implicit-def $arguments
   ; CHECK: bb.1.pred1:
     ; CHECK:      BR_IF %bb.7, %0, implicit-def $arguments

llvm/test/CodeGen/WebAssembly/reg-stackify.ll

 ; CHECK-NEXT:  call        use_a, $pop[[NUM1]]{{$}}
 ; CHECK-NEXT:  call        use_b, $[[NUM2]]{{$}}
 ; CHECK-NEXT:  return{{$}}
 ; NOREGS-LABEL: simple_multiple_use:
 ; NOREGS:       .functype simple_multiple_use (i32, i32) -> (){{$}}
 ; NOREGS-NEXT:  local.get 1{{$}}
 ; NOREGS-NEXT:  local.get 0{{$}}
 ; NOREGS-NEXT:  i32.mul
-; NOREGS-NEXT:  local.tee   1{{$}}
+; NOREGS-NEXT:  local.tee   0{{$}}
 ; NOREGS-NEXT:  call        use_a{{$}}
-; NOREGS-NEXT:  local.get   1{{$}}
+; NOREGS-NEXT:  local.get   0{{$}}
 ; NOREGS-NEXT:  call        use_b{{$}}
 ; NOREGS-NEXT:  return{{$}}
 declare void @use_a(i32)
 declare void @use_b(i32)
 define void @simple_multiple_use(i32 %x, i32 %y) {
   %mul = mul i32 %y, %x
   call void @use_a(i32 %mul)
   call void @use_b(i32 %mul)
   ret void
 }
 
 ; Multiple uses of the same value in one instruction.
 
 ; CHECK-LABEL: multiple_uses_in_same_insn:
 ; CHECK:       .functype multiple_uses_in_same_insn (i32, i32) -> (){{$}}
 ; CHECK-NEXT:  i32.mul     $push[[NUM0:[0-9]+]]=, $1, $0{{$}}
 ; CHECK-NEXT:  local.tee   $push[[NUM1:[0-9]+]]=, $[[NUM2:[0-9]+]]=, $pop[[NUM0]]{{$}}
 ; CHECK-NEXT:  call        use_2, $pop[[NUM1]], $[[NUM2]]{{$}}
 ; CHECK-NEXT:  return{{$}}
 ; NOREGS-LABEL: multiple_uses_in_same_insn:
 ; NOREGS:       .functype multiple_uses_in_same_insn (i32, i32) -> (){{$}}
 ; NOREGS-NEXT:  local.get 1{{$}}
 ; NOREGS-NEXT:  local.get 0{{$}}
 ; NOREGS-NEXT:  i32.mul
-; NOREGS-NEXT:  local.tee   1{{$}}
-; NOREGS-NEXT:  local.get   1{{$}}
+; NOREGS-NEXT:  local.tee   0{{$}}
+; NOREGS-NEXT:  local.get   0{{$}}
 ; NOREGS-NEXT:  call        use_2{{$}}
 ; NOREGS-NEXT:  return{{$}}
 declare void @use_2(i32, i32)
 define void @multiple_uses_in_same_insn(i32 %x, i32 %y) {
   %mul = mul i32 %y, %x
   call void @use_2(i32 %mul, i32 %mul)
   ret void
 }

llvm/test/CodeGen/WebAssembly/umulo-128-legalisation-lowering.ll

 ; WASM32: local.get       $push50=, 5
 ; WASM32: i64.load        $push1=, 32($pop50)
 ; WASM32: i64.store       0($pop51), $pop1
 ; WASM32: local.get       $push55=, 0
 ; WASM32: local.get       $push52=, 5
 ; WASM32: i32.const       $push5=, 40
 ; WASM32: i32.add         $push6=, $pop52, $pop5
 ; WASM32: i64.load        $push33=, 0($pop6)
-; WASM32: local.tee       $push32=, 1, $pop33
+; WASM32: local.tee       $push32=, 3, $pop33
 ; WASM32: local.get       $push53=, 5
 ; WASM32: i64.load        $push3=, 0($pop53)
 ; WASM32: local.get       $push54=, 5
 ; WASM32: i64.load        $push2=, 16($pop54)
 ; WASM32: i64.add         $push4=, $pop3, $pop2
 ; WASM32: i64.add         $push31=, $pop32, $pop4
-; WASM32: local.tee       $push30=, 3, $pop31
+; WASM32: local.tee       $push30=, 1, $pop31
 ; WASM32: i64.store       8($pop55), $pop30
 ; WASM32: local.get       $push62=, 0
 ; WASM32: local.get       $push56=, 2
 ; WASM32: i64.const       $push29=, 0
 ; WASM32: i64.ne          $push8=, $pop56, $pop29
 ; WASM32: local.get       $push57=, 4
 ; WASM32: i64.const       $push28=, 0
 ; WASM32: i64.ne          $push7=, $pop57, $pop28
 ; WASM32: i32.and         $push9=, $pop8, $pop7
 ; WASM32: local.get       $push58=, 5
 ; WASM32: i64.load        $push10=, 8($pop58)
 ; WASM32: i64.const       $push27=, 0
 ; WASM32: i64.ne          $push11=, $pop10, $pop27
 ; WASM32: i32.or          $push12=, $pop9, $pop11
 ; WASM32: local.get       $push59=, 5
 ; WASM32: i64.load        $push13=, 24($pop59)
 ; WASM32: i64.const       $push26=, 0
 ; WASM32: i64.ne          $push14=, $pop13, $pop26
 ; WASM32: i32.or          $push15=, $pop12, $pop14
-; WASM32: local.get       $push61=, 3
-; WASM32: local.get       $push60=, 1
+; WASM32: local.get       $push61=, 1
+; WASM32: local.get       $push60=, 3
 ; WASM32: i64.lt_u        $push16=, $pop61, $pop60
 ; WASM32: i32.or          $push17=, $pop15, $pop16
 ; WASM32: i32.store8      16($pop62), $pop17
 ; WASM32: local.get       $push63=, 5
 ; WASM32: i32.const       $push20=, 48
 ; WASM32: i32.add         $push21=, $pop63, $pop20
 ; WASM32: global.set      __stack_pointer, $pop21
 

llvm/test/CodeGen/WebAssembly/umulo-i64.ll

 ; Function Attrs: nounwind readnone speculatable
 declare { i64, i1 } @llvm.umul.with.overflow.i64(i64, i64) #1
 
 attributes #0 = { inlinehint }
 attributes #1 = { nounwind readnone speculatable }
 
 ; CHECK-LABEL: wut:
 ; CHECK: call     __multi3, $2, $0, $pop0, $1, $pop7
-; CHECK: i64.load $0=, 8($2)
+; CHECK: i64.load $1=, 8($2)
 define i1 @wut(i64, i64) {
 start:
   %2 = call { i64, i1 } @llvm.umul.with.overflow.i64(i64 %0, i64 %1)
   %3 = extractvalue { i64, i1 } %2, 1
   ret i1 %3
 }

llvm/utils/gn/secondary/llvm/lib/Target/WebAssembly/BUILD.gn

sources = [
     "WebAssemblyMCInstLower.cpp",
     "WebAssemblyMCLowerPrePass.cpp",
     "WebAssemblyMachineFunctionInfo.cpp",
     "WebAssemblyMemIntrinsicResults.cpp",
     "WebAssemblyNullifyDebugValueLists.cpp",
     "WebAssemblyOptimizeLiveIntervals.cpp",
     "WebAssemblyOptimizeReturned.cpp",
     "WebAssemblyPeephole.cpp",
-    "WebAssemblyPrepareForLiveIntervals.cpp",
     "WebAssemblyRegColoring.cpp",
     "WebAssemblyRegNumbering.cpp",
     "WebAssemblyRegStackify.cpp",
     "WebAssemblyRegisterInfo.cpp",
     "WebAssemblyReplacePhysRegs.cpp",
     "WebAssemblyRuntimeLibcallSignatures.cpp",
     "WebAssemblySelectionDAGInfo.cpp",
     "WebAssemblySetP2AlignOperands.cpp",