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