[WebAssembly] Don't add IMPLICIT_DEFs in PrepareForLiveIntervals

[aheejin]

Summary

Not sure about the situation when this pass was first added, but uses
without defs are generated from IMPLICIT_DEF instructions from
instruction selection phase correctly now, and all IMPLICIT_DEFs
generated by this pass result in dead live ranges that start and end in
the same instruction. So the only thing we need to do with this pass is
to make sure we track the liveness again.

All test changes are local number changes, which are not meaningful.

[aheejin]

rebase

[dschuff]

lib/Target/WebAssembly/WebAssemblyPrepareForLiveIntervals.cpp

60

This (setting the MachineFunctionProperty) is now the only thing that this pass does. Do we really need all the pass boilerplate just to do that? e.g. can we stick it at the beginning of OptimizeLiveIntervals or RegisterColoring or wherever we actually need it?

[aheejin]

@sunfish Do you have any concerns on removing this? I am not familiar with the situation when this code was first written, so I'm not sure if there's something I'm missing.

lib/Target/WebAssembly/WebAssemblyPrepareForLiveIntervals.cpp

60

I wanted to do that, but we can't. The next pass (OptimizeLiveIntervals) requires LiveIntervals analysis, which means LiveIntervals pass will run before OptimizeLiveIntervals starts. If this precondition is not set before LiveIntervals starts, LiveIntervals pass will fail. I also thought about setting it in the pass before PrepareForLiveIntervals, but that seemed to make less sense, because the pass before it could be anything depending on the compilation pipeline.

[aheejin]

@sunfish Ping :) Do you have any concerns on this?

[aheejin]

Can we land this if no one has concerns?

[aheejin]

Ping! Can we land it? :$

[sunfish]

Sorry for the delay here. Yes, let's land this.

[aheejin]

rebase

[aheejin]

rebase

[aheejin]

Closing in favor of D125515.

lib/Target/WebAssembly/WebAssemblyOptimizeLiveIntervals.cpp

 public:
   static char ID; // Pass identification, replacement for typeid
   WebAssemblyOptimizeLiveIntervals() : MachineFunctionPass(ID) {}
 };
 } // end anonymous namespace
 
 char WebAssemblyOptimizeLiveIntervals::ID = 0;
 INITIALIZE_PASS(WebAssemblyOptimizeLiveIntervals, DEBUG_TYPE,
-                "Optimize LiveIntervals for WebAssembly", false, false)
+                "Optimize LiveIntervals for WebAssembly", true, true)
 
 FunctionPass *llvm::createWebAssemblyOptimizeLiveIntervals() {
   return new WebAssemblyOptimizeLiveIntervals();
 }
 
 bool WebAssemblyOptimizeLiveIntervals::runOnMachineFunction(
     MachineFunction &MF) {
   LLVM_DEBUG(dbgs() << "********** Optimize LiveIntervals **********\n"
for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; ++I) {
     unsigned Reg = TargetRegisterInfo::index2VirtReg(I);
     if (MRI.reg_nodbg_empty(Reg))
       continue;
 
     LIS.splitSeparateComponents(LIS.getInterval(Reg), SplitLIs);
     SplitLIs.clear();
   }
 
-  // In PrepareForLiveIntervals, 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 (auto MII = MF.begin()->begin(), MIE = MF.begin()->end(); MII != MIE;) {
-    MachineInstr *MI = &*MII++;
-    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 false;
 }

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.
+/// Re-track liveness analysis before register stackification.
 ///
-/// 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).
+/// WebAssembly runs LiveIntervals in a late pass. This pass makes sure the
+/// liveness analysis is correctly tracked again before optimizing liveness
+/// intervals and register stackification pass.
 ///
 //===----------------------------------------------------------------------===//
 
-#include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
 #include "WebAssembly.h"
-#include "WebAssemblyMachineFunctionInfo.h"
-#include "WebAssemblySubtarget.h"
-#include "WebAssemblyUtilities.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
private:
   }
 
   bool runOnMachineFunction(MachineFunction &MF) override;
 };
 } // end anonymous namespace
 
 char WebAssemblyPrepareForLiveIntervals::ID = 0;
 INITIALIZE_PASS(WebAssemblyPrepareForLiveIntervals, DEBUG_TYPE,
-                "Fix up code for LiveIntervals", false, false)
+                "Fix up code for LiveIntervals", true, true)
 
 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))
-      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) {
-    unsigned Reg = TargetRegisterInfo::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 (auto MII = Entry.begin(), MIE = Entry.end(); MII != MIE;) {
-    MachineInstr &MI = *MII++;
-    if (WebAssembly::isArgument(MI)) {
-      MI.removeFromParent();
-      Entry.insert(Entry.begin(), &MI);
-    }
-  }
-
-  // Ok, we're now ready to run the LiveIntervals analysis again.
+  // We're now ready to run the LiveIntervals analysis again.
   MF.getProperties().set(MachineFunctionProperties::Property::TracksLiveness);
 
-  return Changed;
+  return false;
 }

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   [[NUM0:[0-9]+]]{{$}}
 ; NOREGS-NEXT:  call        use_a{{$}}
-; NOREGS-NEXT:  local.get   1{{$}}
+; NOREGS-NEXT:  local.get   [[NUM0]]{{$}}
 ; 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   [[NUM0:[0-9]+]]{{$}}
+; NOREGS-NEXT:  local.get   [[NUM0]]{{$}}
 ; 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
 }

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
 

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 ${{.+}}=, 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
 }