1//== WebAssemblyMemIntrinsicResults.cpp - Optimize memory intrinsic results ==//
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/// This file implements an optimization pass using memory intrinsic results.
11///
12/// Calls to memory intrinsics (memcpy, memmove, memset) return the destination
13/// address. They are in the form of
14/// %dst_new = call @memcpy %dst, %src, %len
15/// where %dst and %dst_new registers contain the same value.
16///
17/// This is to enable an optimization wherein uses of the %dst register used in
18/// the parameter can be replaced by uses of the %dst_new register used in the
19/// result, making the %dst register more likely to be single-use, thus more
20/// likely to be useful to register stackifying, and potentially also exposing
21/// the call instruction itself to register stackifying. These both can reduce
22/// local.get/local.set traffic.
23///
24/// The LLVM intrinsics for these return void so they can't use the returned
25/// attribute and consequently aren't handled by the OptimizeReturned pass.
26///
27//===----------------------------------------------------------------------===//
28
29#include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
30#include "WebAssembly.h"
31#include "WebAssemblyMachineFunctionInfo.h"
32#include "WebAssemblySubtarget.h"
33#include "llvm/Analysis/TargetLibraryInfo.h"
34#include "llvm/CodeGen/LibcallLoweringInfo.h"
35#include "llvm/CodeGen/LiveIntervals.h"
36#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
37#include "llvm/CodeGen/MachineDominators.h"
38#include "llvm/CodeGen/MachineFunctionAnalysisManager.h"
39#include "llvm/CodeGen/MachineFunctionPass.h"
40#include "llvm/CodeGen/MachinePassManager.h"
41#include "llvm/CodeGen/MachineRegisterInfo.h"
42#include "llvm/CodeGen/Passes.h"
43#include "llvm/CodeGen/SlotIndexes.h"
44#include "llvm/IR/Analysis.h"
45#include "llvm/Support/Debug.h"
46#include "llvm/Support/raw_ostream.h"
47using namespace llvm;
48
49#define DEBUG_TYPE "wasm-mem-intrinsic-results"
50
51namespace {
52class WebAssemblyMemIntrinsicResultsImpl {
53public:
54 WebAssemblyMemIntrinsicResultsImpl(MachineDominatorTree *MDT,
55 LiveIntervals *LIS,
56 const TargetLibraryInfo *LibInfo,
57 const LibcallLoweringInfo &LibCalls)
58 : MDT(MDT), LIS(LIS), LibInfo(LibInfo), LibCalls(LibCalls) {}
59 bool runOnMachineFunction(MachineFunction &MF);
60
61private:
62 MachineDominatorTree *MDT;
63 LiveIntervals *LIS;
64 const TargetLibraryInfo *LibInfo;
65 const LibcallLoweringInfo &LibCalls;
66
67 StringRef MemcpyName, MemmoveName, MemsetName;
68
69 bool optimizeCall(MachineBasicBlock &MBB, MachineInstr &MI,
70 const MachineRegisterInfo &MRI) const;
71};
72
73class WebAssemblyMemIntrinsicResultsLegacy final : public MachineFunctionPass {
74public:
75 static char ID; // Pass identification, replacement for typeid
76 WebAssemblyMemIntrinsicResultsLegacy() : MachineFunctionPass(ID) {}
77
78 StringRef getPassName() const override {
79 return "WebAssembly Memory Intrinsic Results";
80 }
81
82 void getAnalysisUsage(AnalysisUsage &AU) const override {
83 AU.setPreservesCFG();
84 AU.addRequired<MachineDominatorTreeWrapperPass>();
85 AU.addRequired<LiveIntervalsWrapperPass>();
86 AU.addPreserved<SlotIndexesWrapperPass>();
87 AU.addPreserved<LiveIntervalsWrapperPass>();
88 AU.addRequired<TargetLibraryInfoWrapperPass>();
89 AU.addRequired<LibcallLoweringInfoWrapper>();
90 MachineFunctionPass::getAnalysisUsage(AU);
91 }
92
93 bool runOnMachineFunction(MachineFunction &MF) override;
94};
95} // end anonymous namespace
96
97char WebAssemblyMemIntrinsicResultsLegacy::ID = 0;
98INITIALIZE_PASS(WebAssemblyMemIntrinsicResultsLegacy, DEBUG_TYPE,
99 "Optimize memory intrinsic result values for WebAssembly",
100 false, false)
101
102FunctionPass *llvm::createWebAssemblyMemIntrinsicResultsLegacyPass() {
103 return new WebAssemblyMemIntrinsicResultsLegacy();
104}
105
106// Replace uses of FromReg with ToReg if they are dominated by MI.
107static bool replaceDominatedUses(MachineBasicBlock &MBB, MachineInstr &MI,
108 unsigned FromReg, unsigned ToReg,
109 const MachineRegisterInfo &MRI,
110 MachineDominatorTree &MDT,
111 LiveIntervals &LIS) {
112 bool Changed = false;
113
114 LiveInterval *FromLI = &LIS.getInterval(Reg: FromReg);
115 LiveInterval *ToLI = &LIS.getInterval(Reg: ToReg);
116
117 SlotIndex FromIdx = LIS.getInstructionIndex(Instr: MI).getRegSlot();
118 VNInfo *FromVNI = FromLI->getVNInfoAt(Idx: FromIdx);
119
120 SmallVector<SlotIndex, 4> Indices;
121
122 for (MachineOperand &O :
123 llvm::make_early_inc_range(Range: MRI.use_nodbg_operands(Reg: FromReg))) {
124 MachineInstr *Where = O.getParent();
125
126 // Check that MI dominates the instruction in the normal way.
127 if (&MI == Where || !MDT.dominates(A: &MI, B: Where))
128 continue;
129
130 // If this use gets a different value, skip it.
131 SlotIndex WhereIdx = LIS.getInstructionIndex(Instr: *Where);
132 VNInfo *WhereVNI = FromLI->getVNInfoAt(Idx: WhereIdx);
133 if (WhereVNI && WhereVNI != FromVNI)
134 continue;
135
136 // Make sure ToReg isn't clobbered before it gets there.
137 VNInfo *ToVNI = ToLI->getVNInfoAt(Idx: WhereIdx);
138 if (ToVNI && ToVNI != FromVNI)
139 continue;
140
141 Changed = true;
142 LLVM_DEBUG(dbgs() << "Setting operand " << O << " in " << *Where << " from "
143 << MI << "\n");
144 O.setReg(ToReg);
145
146 // If the store's def was previously dead, it is no longer.
147 if (!O.isUndef()) {
148 MI.getOperand(i: 0).setIsDead(false);
149
150 Indices.push_back(Elt: WhereIdx.getRegSlot());
151 }
152 }
153
154 if (Changed) {
155 // Extend ToReg's liveness.
156 LIS.extendToIndices(LR&: *ToLI, Indices);
157
158 // Shrink FromReg's liveness.
159 LIS.shrinkToUses(li: FromLI);
160
161 // If we replaced all dominated uses, FromReg is now killed at MI.
162 if (!FromLI->liveAt(index: FromIdx.getDeadSlot()))
163 MI.addRegisterKilled(IncomingReg: FromReg, RegInfo: MBB.getParent()
164 ->getSubtarget<WebAssemblySubtarget>()
165 .getRegisterInfo());
166 }
167
168 return Changed;
169}
170
171bool WebAssemblyMemIntrinsicResultsImpl::optimizeCall(
172 MachineBasicBlock &MBB, MachineInstr &MI,
173 const MachineRegisterInfo &MRI) const {
174 MachineOperand &Op1 = MI.getOperand(i: 1);
175 if (!Op1.isSymbol())
176 return false;
177
178 StringRef Name(Op1.getSymbolName());
179
180 // TODO: Could generalize by parsing to LibcallImpl and checking signature
181 // attributes
182 bool CallReturnsInput =
183 Name == MemcpyName || Name == MemmoveName || Name == MemsetName;
184 if (!CallReturnsInput)
185 return false;
186
187 if (LibInfo->getLibFunc(funcName: Name) == NotLibFunc)
188 return false;
189
190 Register FromReg = MI.getOperand(i: 2).getReg();
191 Register ToReg = MI.getOperand(i: 0).getReg();
192 if (MRI.getRegClass(Reg: FromReg) != MRI.getRegClass(Reg: ToReg))
193 report_fatal_error(reason: "Memory Intrinsic results: call to builtin function "
194 "with wrong signature, from/to mismatch");
195 return replaceDominatedUses(MBB, MI, FromReg, ToReg, MRI, MDT&: *MDT, LIS&: *LIS);
196}
197
198bool WebAssemblyMemIntrinsicResultsImpl::runOnMachineFunction(
199 MachineFunction &MF) {
200 LLVM_DEBUG({
201 dbgs() << "********** Memory Intrinsic Results **********\n"
202 << "********** Function: " << MF.getName() << '\n';
203 });
204
205 MachineRegisterInfo &MRI = MF.getRegInfo();
206
207 MemcpyName = RTLIB::RuntimeLibcallsInfo::getLibcallImplName(
208 CallImpl: LibCalls.getLibcallImpl(Call: RTLIB::MEMCPY));
209 MemmoveName = RTLIB::RuntimeLibcallsInfo::getLibcallImplName(
210 CallImpl: LibCalls.getLibcallImpl(Call: RTLIB::MEMMOVE));
211 MemsetName = RTLIB::RuntimeLibcallsInfo::getLibcallImplName(
212 CallImpl: LibCalls.getLibcallImpl(Call: RTLIB::MEMSET));
213
214 bool Changed = false;
215
216 // We don't preserve SSA form.
217 MRI.leaveSSA();
218
219 assert(MRI.tracksLiveness() &&
220 "MemIntrinsicResults expects liveness tracking");
221
222 for (auto &MBB : MF) {
223 LLVM_DEBUG(dbgs() << "Basic Block: " << MBB.getName() << '\n');
224 for (auto &MI : MBB)
225 switch (MI.getOpcode()) {
226 default:
227 break;
228 case WebAssembly::CALL:
229 Changed |= optimizeCall(MBB, MI, MRI);
230 break;
231 }
232 }
233
234 return Changed;
235}
236
237bool WebAssemblyMemIntrinsicResultsLegacy::runOnMachineFunction(
238 MachineFunction &MF) {
239 MachineDominatorTree *MDT =
240 &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
241 LiveIntervals *LIS = &getAnalysis<LiveIntervalsWrapperPass>().getLIS();
242 const TargetLibraryInfo *LibInfo =
243 &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F: MF.getFunction());
244 const WebAssemblySubtarget &Subtarget =
245 MF.getSubtarget<WebAssemblySubtarget>();
246 const LibcallLoweringInfo &LibCalls =
247 getAnalysis<LibcallLoweringInfoWrapper>().getLibcallLowering(
248 M: *MF.getFunction().getParent(), Subtarget);
249 WebAssemblyMemIntrinsicResultsImpl Impl(MDT, LIS, LibInfo, LibCalls);
250 return Impl.runOnMachineFunction(MF);
251}
252
253PreservedAnalyses
254WebAssemblyMemIntrinsicResultsPass::run(MachineFunction &MF,
255 MachineFunctionAnalysisManager &MFAM) {
256 MachineDominatorTree *MDT = &MFAM.getResult<MachineDominatorTreeAnalysis>(IR&: MF);
257 LiveIntervals *LIS = &MFAM.getResult<LiveIntervalsAnalysis>(IR&: MF);
258 const TargetLibraryInfo *LibInfo =
259 &MFAM.getResult<FunctionAnalysisManagerMachineFunctionProxy>(IR&: MF)
260 .getManager()
261 .getResult<TargetLibraryAnalysis>(IR&: MF.getFunction());
262 const WebAssemblySubtarget &Subtarget =
263 MF.getSubtarget<WebAssemblySubtarget>();
264 const LibcallLoweringInfo &LibCalls = getLibcallLowering(
265 ModuleInfo: *MFAM.getResult<ModuleAnalysisManagerMachineFunctionProxy>(IR&: MF)
266 .getCachedResult<LibcallLoweringModuleAnalysis>(
267 IR&: *MF.getFunction().getParent()),
268 Subtarget);
269 WebAssemblyMemIntrinsicResultsImpl Impl(MDT, LIS, LibInfo, LibCalls);
270 bool Changed = Impl.runOnMachineFunction(MF);
271 if (!Changed)
272 return PreservedAnalyses::all();
273 return getMachineFunctionPassPreservedAnalyses()
274 .preserveSet<CFGAnalyses>()
275 .preserve<LiveIntervalsAnalysis>()
276 .preserve<SlotIndexesAnalysis>();
277}
278