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 "WebAssemblyMachineFunctionInfo.h"
24 #include "WebAssemblySubtarget.h"
25 #include "llvm/CodeGen/LiveIntervals.h"
26 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
27 #include "llvm/CodeGen/MachineRegisterInfo.h"
28 #include "llvm/CodeGen/Passes.h"
29 #include "llvm/Support/Debug.h"
30 #include "llvm/Support/raw_ostream.h"
31 using namespace llvm;
32
33 #define DEBUG_TYPE "wasm-optimize-live-intervals"
34
35 namespace {
36 class WebAssemblyOptimizeLiveIntervals final : public MachineFunctionPass {
getPassName() const37 StringRef getPassName() const override {
38 return "WebAssembly Optimize Live Intervals";
39 }
40
getAnalysisUsage(AnalysisUsage & AU) const41 void getAnalysisUsage(AnalysisUsage &AU) const override {
42 AU.setPreservesCFG();
43 AU.addRequired<LiveIntervalsWrapperPass>();
44 AU.addPreserved<MachineBlockFrequencyInfoWrapperPass>();
45 AU.addPreserved<SlotIndexesWrapperPass>();
46 AU.addPreserved<LiveIntervalsWrapperPass>();
47 AU.addPreservedID(LiveVariablesID);
48 AU.addPreservedID(MachineDominatorsID);
49 MachineFunctionPass::getAnalysisUsage(AU);
50 }
51
getRequiredProperties() const52 MachineFunctionProperties getRequiredProperties() const override {
53 return MachineFunctionProperties().set(
54 MachineFunctionProperties::Property::TracksLiveness);
55 }
56
57 bool runOnMachineFunction(MachineFunction &MF) override;
58
59 public:
60 static char ID; // Pass identification, replacement for typeid
WebAssemblyOptimizeLiveIntervals()61 WebAssemblyOptimizeLiveIntervals() : MachineFunctionPass(ID) {}
62 };
63 } // end anonymous namespace
64
65 char WebAssemblyOptimizeLiveIntervals::ID = 0;
66 INITIALIZE_PASS(WebAssemblyOptimizeLiveIntervals, DEBUG_TYPE,
67 "Optimize LiveIntervals for WebAssembly", false, false)
68
createWebAssemblyOptimizeLiveIntervals()69 FunctionPass *llvm::createWebAssemblyOptimizeLiveIntervals() {
70 return new WebAssemblyOptimizeLiveIntervals();
71 }
72
runOnMachineFunction(MachineFunction & MF)73 bool WebAssemblyOptimizeLiveIntervals::runOnMachineFunction(
74 MachineFunction &MF) {
75 LLVM_DEBUG(dbgs() << "********** Optimize LiveIntervals **********\n"
76 "********** Function: "
77 << MF.getName() << '\n');
78
79 MachineRegisterInfo &MRI = MF.getRegInfo();
80 auto &LIS = getAnalysis<LiveIntervalsWrapperPass>().getLIS();
81
82 // We don't preserve SSA form.
83 MRI.leaveSSA();
84
85 assert(MRI.tracksLiveness() && "OptimizeLiveIntervals expects liveness");
86
87 // Split multiple-VN LiveIntervals into multiple LiveIntervals.
88 SmallVector<LiveInterval *, 4> SplitLIs;
89 for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; ++I) {
90 Register Reg = Register::index2VirtReg(I);
91 auto &TRI = *MF.getSubtarget<WebAssemblySubtarget>().getRegisterInfo();
92
93 if (MRI.reg_nodbg_empty(Reg))
94 continue;
95
96 LIS.splitSeparateComponents(LIS.getInterval(Reg), SplitLIs);
97 if (Reg == TRI.getFrameRegister(MF) && SplitLIs.size() > 0) {
98 // The live interval for the frame register was split, resulting in a new
99 // VReg. For now we only support debug info output for a single frame base
100 // value for the function, so just use the last one. It will certainly be
101 // wrong for some part of the function, but until we are able to track
102 // values through live-range splitting and stackification, it will have to
103 // do.
104 MF.getInfo<WebAssemblyFunctionInfo>()->setFrameBaseVreg(
105 SplitLIs.back()->reg());
106 }
107 SplitLIs.clear();
108 }
109
110 // In FixIrreducibleControlFlow, we conservatively inserted IMPLICIT_DEF
111 // instructions to satisfy LiveIntervals' requirement that all uses be
112 // dominated by defs. Now that LiveIntervals has computed which of these
113 // defs are actually needed and which are dead, remove the dead ones.
114 for (MachineInstr &MI : llvm::make_early_inc_range(MF.front())) {
115 if (MI.isImplicitDef() && MI.getOperand(0).isDead()) {
116 LiveInterval &LI = LIS.getInterval(MI.getOperand(0).getReg());
117 LIS.removeVRegDefAt(LI, LIS.getInstructionIndex(MI).getRegSlot());
118 LIS.RemoveMachineInstrFromMaps(MI);
119 MI.eraseFromParent();
120 }
121 }
122
123 return true;
124 }
125