1 //== WebAssemblyMemIntrinsicResults.cpp - Optimize memory intrinsic results ==//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 ///
10 /// \file
11 /// This file implements an optimization pass using memory intrinsic results.
12 ///
13 /// Calls to memory intrinsics (memcpy, memmove, memset) return the destination
14 /// address. They are in the form of
15 /// %dst_new = call @memcpy %dst, %src, %len
16 /// where %dst and %dst_new registers contain the same value.
17 ///
18 /// This is to enable an optimization wherein uses of the %dst register used in
19 /// the parameter can be replaced by uses of the %dst_new register used in the
20 /// result, making the %dst register more likely to be single-use, thus more
21 /// likely to be useful to register stackifying, and potentially also exposing
22 /// the call instruction itself to register stackifying. These both can reduce
23 /// local.get/local.set traffic.
24 ///
25 /// The LLVM intrinsics for these return void so they can't use the returned
26 /// attribute and consequently aren't handled by the OptimizeReturned pass.
27 ///
28 //===----------------------------------------------------------------------===//
29
30 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
31 #include "WebAssembly.h"
32 #include "WebAssemblyMachineFunctionInfo.h"
33 #include "WebAssemblySubtarget.h"
34 #include "llvm/Analysis/TargetLibraryInfo.h"
35 #include "llvm/CodeGen/LiveIntervals.h"
36 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
37 #include "llvm/CodeGen/MachineDominators.h"
38 #include "llvm/CodeGen/MachineRegisterInfo.h"
39 #include "llvm/CodeGen/Passes.h"
40 #include "llvm/Support/Debug.h"
41 #include "llvm/Support/raw_ostream.h"
42 using namespace llvm;
43
44 #define DEBUG_TYPE "wasm-mem-intrinsic-results"
45
46 namespace {
47 class WebAssemblyMemIntrinsicResults final : public MachineFunctionPass {
48 public:
49 static char ID; // Pass identification, replacement for typeid
WebAssemblyMemIntrinsicResults()50 WebAssemblyMemIntrinsicResults() : MachineFunctionPass(ID) {}
51
getPassName() const52 StringRef getPassName() const override {
53 return "WebAssembly Memory Intrinsic Results";
54 }
55
getAnalysisUsage(AnalysisUsage & AU) const56 void getAnalysisUsage(AnalysisUsage &AU) const override {
57 AU.setPreservesCFG();
58 AU.addRequired<MachineBlockFrequencyInfo>();
59 AU.addPreserved<MachineBlockFrequencyInfo>();
60 AU.addRequired<MachineDominatorTree>();
61 AU.addPreserved<MachineDominatorTree>();
62 AU.addRequired<LiveIntervals>();
63 AU.addPreserved<SlotIndexes>();
64 AU.addPreserved<LiveIntervals>();
65 AU.addRequired<TargetLibraryInfoWrapperPass>();
66 MachineFunctionPass::getAnalysisUsage(AU);
67 }
68
69 bool runOnMachineFunction(MachineFunction &MF) override;
70
71 private:
72 };
73 } // end anonymous namespace
74
75 char WebAssemblyMemIntrinsicResults::ID = 0;
76 INITIALIZE_PASS(WebAssemblyMemIntrinsicResults, DEBUG_TYPE,
77 "Optimize memory intrinsic result values for WebAssembly",
78 false, false)
79
createWebAssemblyMemIntrinsicResults()80 FunctionPass *llvm::createWebAssemblyMemIntrinsicResults() {
81 return new WebAssemblyMemIntrinsicResults();
82 }
83
84 // Replace uses of FromReg with ToReg if they are dominated by MI.
ReplaceDominatedUses(MachineBasicBlock & MBB,MachineInstr & MI,unsigned FromReg,unsigned ToReg,const MachineRegisterInfo & MRI,MachineDominatorTree & MDT,LiveIntervals & LIS)85 static bool ReplaceDominatedUses(MachineBasicBlock &MBB, MachineInstr &MI,
86 unsigned FromReg, unsigned ToReg,
87 const MachineRegisterInfo &MRI,
88 MachineDominatorTree &MDT,
89 LiveIntervals &LIS) {
90 bool Changed = false;
91
92 LiveInterval *FromLI = &LIS.getInterval(FromReg);
93 LiveInterval *ToLI = &LIS.getInterval(ToReg);
94
95 SlotIndex FromIdx = LIS.getInstructionIndex(MI).getRegSlot();
96 VNInfo *FromVNI = FromLI->getVNInfoAt(FromIdx);
97
98 SmallVector<SlotIndex, 4> Indices;
99
100 for (auto I = MRI.use_nodbg_begin(FromReg), E = MRI.use_nodbg_end();
101 I != E;) {
102 MachineOperand &O = *I++;
103 MachineInstr *Where = O.getParent();
104
105 // Check that MI dominates the instruction in the normal way.
106 if (&MI == Where || !MDT.dominates(&MI, Where))
107 continue;
108
109 // If this use gets a different value, skip it.
110 SlotIndex WhereIdx = LIS.getInstructionIndex(*Where);
111 VNInfo *WhereVNI = FromLI->getVNInfoAt(WhereIdx);
112 if (WhereVNI && WhereVNI != FromVNI)
113 continue;
114
115 // Make sure ToReg isn't clobbered before it gets there.
116 VNInfo *ToVNI = ToLI->getVNInfoAt(WhereIdx);
117 if (ToVNI && ToVNI != FromVNI)
118 continue;
119
120 Changed = true;
121 LLVM_DEBUG(dbgs() << "Setting operand " << O << " in " << *Where << " from "
122 << MI << "\n");
123 O.setReg(ToReg);
124
125 // If the store's def was previously dead, it is no longer.
126 if (!O.isUndef()) {
127 MI.getOperand(0).setIsDead(false);
128
129 Indices.push_back(WhereIdx.getRegSlot());
130 }
131 }
132
133 if (Changed) {
134 // Extend ToReg's liveness.
135 LIS.extendToIndices(*ToLI, Indices);
136
137 // Shrink FromReg's liveness.
138 LIS.shrinkToUses(FromLI);
139
140 // If we replaced all dominated uses, FromReg is now killed at MI.
141 if (!FromLI->liveAt(FromIdx.getDeadSlot()))
142 MI.addRegisterKilled(FromReg, MBB.getParent()
143 ->getSubtarget<WebAssemblySubtarget>()
144 .getRegisterInfo());
145 }
146
147 return Changed;
148 }
149
optimizeCall(MachineBasicBlock & MBB,MachineInstr & MI,const MachineRegisterInfo & MRI,MachineDominatorTree & MDT,LiveIntervals & LIS,const WebAssemblyTargetLowering & TLI,const TargetLibraryInfo & LibInfo)150 static bool optimizeCall(MachineBasicBlock &MBB, MachineInstr &MI,
151 const MachineRegisterInfo &MRI,
152 MachineDominatorTree &MDT, LiveIntervals &LIS,
153 const WebAssemblyTargetLowering &TLI,
154 const TargetLibraryInfo &LibInfo) {
155 MachineOperand &Op1 = MI.getOperand(1);
156 if (!Op1.isSymbol())
157 return false;
158
159 StringRef Name(Op1.getSymbolName());
160 bool callReturnsInput = Name == TLI.getLibcallName(RTLIB::MEMCPY) ||
161 Name == TLI.getLibcallName(RTLIB::MEMMOVE) ||
162 Name == TLI.getLibcallName(RTLIB::MEMSET);
163 if (!callReturnsInput)
164 return false;
165
166 LibFunc Func;
167 if (!LibInfo.getLibFunc(Name, Func))
168 return false;
169
170 unsigned FromReg = MI.getOperand(2).getReg();
171 unsigned ToReg = MI.getOperand(0).getReg();
172 if (MRI.getRegClass(FromReg) != MRI.getRegClass(ToReg))
173 report_fatal_error("Memory Intrinsic results: call to builtin function "
174 "with wrong signature, from/to mismatch");
175 return ReplaceDominatedUses(MBB, MI, FromReg, ToReg, MRI, MDT, LIS);
176 }
177
runOnMachineFunction(MachineFunction & MF)178 bool WebAssemblyMemIntrinsicResults::runOnMachineFunction(MachineFunction &MF) {
179 LLVM_DEBUG({
180 dbgs() << "********** Memory Intrinsic Results **********\n"
181 << "********** Function: " << MF.getName() << '\n';
182 });
183
184 MachineRegisterInfo &MRI = MF.getRegInfo();
185 MachineDominatorTree &MDT = getAnalysis<MachineDominatorTree>();
186 const WebAssemblyTargetLowering &TLI =
187 *MF.getSubtarget<WebAssemblySubtarget>().getTargetLowering();
188 const auto &LibInfo = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
189 LiveIntervals &LIS = getAnalysis<LiveIntervals>();
190 bool Changed = false;
191
192 // We don't preserve SSA form.
193 MRI.leaveSSA();
194
195 assert(MRI.tracksLiveness() &&
196 "MemIntrinsicResults expects liveness tracking");
197
198 for (auto &MBB : MF) {
199 LLVM_DEBUG(dbgs() << "Basic Block: " << MBB.getName() << '\n');
200 for (auto &MI : MBB)
201 switch (MI.getOpcode()) {
202 default:
203 break;
204 case WebAssembly::CALL_I32:
205 case WebAssembly::CALL_I64:
206 Changed |= optimizeCall(MBB, MI, MRI, MDT, LIS, TLI, LibInfo);
207 break;
208 }
209 }
210
211 return Changed;
212 }
213