1//===- WebAssemblyPrepareForLiveIntervals.cpp - Prepare for LiveIntervals -===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
10/// Fix up code to meet LiveInterval's requirements.
11///
12/// Some CodeGen passes don't preserve LiveInterval's requirements, because
13/// they run after register allocation and it isn't important. However,
14/// WebAssembly runs LiveIntervals in a late pass. This pass transforms code
15/// to meet LiveIntervals' requirements; primarily, it ensures that all
16/// virtual register uses have definitions (IMPLICIT_DEF definitions if
17/// nothing else).
18///
19//===----------------------------------------------------------------------===//
20
21#include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
22#include "WebAssembly.h"
23#include "WebAssemblyMachineFunctionInfo.h"
24#include "WebAssemblySubtarget.h"
25#include "WebAssemblyUtilities.h"
26#include "llvm/CodeGen/MachineFunctionPass.h"
27#include "llvm/CodeGen/MachineInstrBuilder.h"
28#include "llvm/CodeGen/MachineRegisterInfo.h"
29#include "llvm/CodeGen/Passes.h"
30#include "llvm/Support/Debug.h"
31#include "llvm/Support/raw_ostream.h"
32using namespace llvm;
33
34#define DEBUG_TYPE "wasm-prepare-for-live-intervals"
35
36namespace {
37class WebAssemblyPrepareForLiveIntervals final : public MachineFunctionPass {
38public:
39  static char ID; // Pass identification, replacement for typeid
40  WebAssemblyPrepareForLiveIntervals() : MachineFunctionPass(ID) {}
41
42private:
43  StringRef getPassName() const override {
44    return "WebAssembly Prepare For LiveIntervals";
45  }
46
47  void getAnalysisUsage(AnalysisUsage &AU) const override {
48    AU.setPreservesCFG();
49    MachineFunctionPass::getAnalysisUsage(AU);
50  }
51
52  bool runOnMachineFunction(MachineFunction &MF) override;
53};
54} // end anonymous namespace
55
56char WebAssemblyPrepareForLiveIntervals::ID = 0;
57INITIALIZE_PASS(WebAssemblyPrepareForLiveIntervals, DEBUG_TYPE,
58                "Fix up code for LiveIntervals", false, false)
59
60FunctionPass *llvm::createWebAssemblyPrepareForLiveIntervals() {
61  return new WebAssemblyPrepareForLiveIntervals();
62}
63
64// Test whether the given register has an ARGUMENT def.
65static bool hasArgumentDef(unsigned Reg, const MachineRegisterInfo &MRI) {
66  for (const auto &Def : MRI.def_instructions(Reg))
67    if (WebAssembly::isArgument(Def.getOpcode()))
68      return true;
69  return false;
70}
71
72bool WebAssemblyPrepareForLiveIntervals::runOnMachineFunction(
73    MachineFunction &MF) {
74  LLVM_DEBUG({
75    dbgs() << "********** Prepare For LiveIntervals **********\n"
76           << "********** Function: " << MF.getName() << '\n';
77  });
78
79  bool Changed = false;
80  MachineRegisterInfo &MRI = MF.getRegInfo();
81  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
82  MachineBasicBlock &Entry = *MF.begin();
83
84  assert(!mustPreserveAnalysisID(LiveIntervalsID) &&
85         "LiveIntervals shouldn't be active yet!");
86
87  // We don't preserve SSA form.
88  MRI.leaveSSA();
89
90  // BranchFolding and perhaps other passes don't preserve IMPLICIT_DEF
91  // instructions. LiveIntervals requires that all paths to virtual register
92  // uses provide a definition. Insert IMPLICIT_DEFs in the entry block to
93  // conservatively satisfy this.
94  //
95  // TODO: This is fairly heavy-handed; find a better approach.
96  //
97  for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; ++I) {
98    unsigned Reg = Register::index2VirtReg(I);
99
100    // Skip unused registers.
101    if (MRI.use_nodbg_empty(Reg))
102      continue;
103
104    // Skip registers that have an ARGUMENT definition.
105    if (hasArgumentDef(Reg, MRI))
106      continue;
107
108    BuildMI(Entry, Entry.begin(), DebugLoc(),
109            TII.get(WebAssembly::IMPLICIT_DEF), Reg);
110    Changed = true;
111  }
112
113  // Move ARGUMENT_* instructions to the top of the entry block, so that their
114  // liveness reflects the fact that these really are live-in values.
115  for (auto MII = Entry.begin(), MIE = Entry.end(); MII != MIE;) {
116    MachineInstr &MI = *MII++;
117    if (WebAssembly::isArgument(MI.getOpcode())) {
118      MI.removeFromParent();
119      Entry.insert(Entry.begin(), &MI);
120    }
121  }
122
123  // Ok, we're now ready to run the LiveIntervals analysis again.
124  MF.getProperties().set(MachineFunctionProperties::Property::TracksLiveness);
125
126  return Changed;
127}
128