1//===--- WebAssemblyOptimizeLiveIntervals.cpp - LiveInterval processing ---===//
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/// Optimize LiveIntervals for use in a post-RA context.
11//
12/// LiveIntervals normally runs before register allocation when the code is
13/// only recently lowered out of SSA form, so it's uncommon for registers to
14/// have multiple defs, and when they do, the defs are usually closely related.
15/// Later, after coalescing, tail duplication, and other optimizations, it's
16/// more common to see registers with multiple unrelated defs. This pass
17/// updates LiveIntervals to distribute the value numbers across separate
18/// LiveIntervals.
19///
20//===----------------------------------------------------------------------===//
21
22#include "WebAssembly.h"
23#include "WebAssemblySubtarget.h"
24#include "llvm/CodeGen/LiveIntervals.h"
25#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
26#include "llvm/CodeGen/MachineRegisterInfo.h"
27#include "llvm/CodeGen/Passes.h"
28#include "llvm/Support/Debug.h"
29#include "llvm/Support/raw_ostream.h"
30using namespace llvm;
31
32#define DEBUG_TYPE "wasm-optimize-live-intervals"
33
34namespace {
35class WebAssemblyOptimizeLiveIntervals final : public MachineFunctionPass {
36  StringRef getPassName() const override {
37    return "WebAssembly Optimize Live Intervals";
38  }
39
40  void getAnalysisUsage(AnalysisUsage &AU) const override {
41    AU.setPreservesCFG();
42    AU.addRequired<LiveIntervals>();
43    AU.addPreserved<MachineBlockFrequencyInfo>();
44    AU.addPreserved<SlotIndexes>();
45    AU.addPreserved<LiveIntervals>();
46    AU.addPreservedID(LiveVariablesID);
47    AU.addPreservedID(MachineDominatorsID);
48    MachineFunctionPass::getAnalysisUsage(AU);
49  }
50
51  bool runOnMachineFunction(MachineFunction &MF) override;
52
53public:
54  static char ID; // Pass identification, replacement for typeid
55  WebAssemblyOptimizeLiveIntervals() : MachineFunctionPass(ID) {}
56};
57} // end anonymous namespace
58
59char WebAssemblyOptimizeLiveIntervals::ID = 0;
60INITIALIZE_PASS(WebAssemblyOptimizeLiveIntervals, DEBUG_TYPE,
61                "Optimize LiveIntervals for WebAssembly", false, false)
62
63FunctionPass *llvm::createWebAssemblyOptimizeLiveIntervals() {
64  return new WebAssemblyOptimizeLiveIntervals();
65}
66
67bool WebAssemblyOptimizeLiveIntervals::runOnMachineFunction(
68    MachineFunction &MF) {
69  LLVM_DEBUG(dbgs() << "********** Optimize LiveIntervals **********\n"
70                       "********** Function: "
71                    << MF.getName() << '\n');
72
73  MachineRegisterInfo &MRI = MF.getRegInfo();
74  auto &LIS = getAnalysis<LiveIntervals>();
75
76  // We don't preserve SSA form.
77  MRI.leaveSSA();
78
79  assert(MRI.tracksLiveness() && "OptimizeLiveIntervals expects liveness");
80
81  // Split multiple-VN LiveIntervals into multiple LiveIntervals.
82  SmallVector<LiveInterval *, 4> SplitLIs;
83  for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; ++I) {
84    unsigned Reg = Register::index2VirtReg(I);
85    if (MRI.reg_nodbg_empty(Reg))
86      continue;
87
88    LIS.splitSeparateComponents(LIS.getInterval(Reg), SplitLIs);
89    SplitLIs.clear();
90  }
91
92  // In PrepareForLiveIntervals, we conservatively inserted IMPLICIT_DEF
93  // instructions to satisfy LiveIntervals' requirement that all uses be
94  // dominated by defs. Now that LiveIntervals has computed which of these
95  // defs are actually needed and which are dead, remove the dead ones.
96  for (auto MII = MF.begin()->begin(), MIE = MF.begin()->end(); MII != MIE;) {
97    MachineInstr *MI = &*MII++;
98    if (MI->isImplicitDef() && MI->getOperand(0).isDead()) {
99      LiveInterval &LI = LIS.getInterval(MI->getOperand(0).getReg());
100      LIS.removeVRegDefAt(LI, LIS.getInstructionIndex(*MI).getRegSlot());
101      LIS.RemoveMachineInstrFromMaps(*MI);
102      MI->eraseFromParent();
103    }
104  }
105
106  return false;
107}
108