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(MachineInstr &MI, unsigned FromReg,
107 unsigned ToReg, const MachineRegisterInfo &MRI,
108 MachineDominatorTree &MDT,
109 LiveIntervals &LIS) {
110 bool Changed = false;
111
112 LiveInterval *FromLI = &LIS.getInterval(Reg: FromReg);
113 LiveInterval *ToLI = &LIS.getInterval(Reg: ToReg);
114
115 SlotIndex FromIdx = LIS.getInstructionIndex(Instr: MI).getRegSlot();
116 VNInfo *FromVNI = FromLI->getVNInfoAt(Idx: FromIdx);
117
118 SmallVector<SlotIndex, 4> Indices;
119
120 for (MachineOperand &O :
121 llvm::make_early_inc_range(Range: MRI.use_nodbg_operands(Reg: FromReg))) {
122 MachineInstr *Where = O.getParent();
123
124 // Check that MI dominates the instruction in the normal way.
125 if (&MI == Where || !MDT.dominates(A: &MI, B: Where))
126 continue;
127
128 // If this use gets a different value, skip it.
129 SlotIndex WhereIdx = LIS.getInstructionIndex(Instr: *Where);
130 VNInfo *WhereVNI = FromLI->getVNInfoAt(Idx: WhereIdx);
131 if (WhereVNI && WhereVNI != FromVNI)
132 continue;
133
134 // Make sure ToReg isn't clobbered before it gets there.
135 VNInfo *ToVNI = ToLI->getVNInfoAt(Idx: WhereIdx);
136 if (ToVNI && ToVNI != FromVNI)
137 continue;
138
139 Changed = true;
140 LLVM_DEBUG(dbgs() << "Setting operand " << O << " in " << *Where << " from "
141 << MI << "\n");
142 O.setReg(ToReg);
143
144 // If the store's def was previously dead, it is no longer.
145 if (!O.isUndef()) {
146 MI.getOperand(i: 0).setIsDead(false);
147
148 Indices.push_back(Elt: WhereIdx.getRegSlot());
149 }
150 }
151
152 if (Changed) {
153 // Extend ToReg's liveness.
154 LIS.extendToIndices(LR&: *ToLI, Indices);
155
156 // Shrink FromReg's liveness.
157 LIS.shrinkToUses(li: FromLI);
158 }
159
160 return Changed;
161}
162
163bool WebAssemblyMemIntrinsicResultsImpl::optimizeCall(
164 MachineBasicBlock &MBB, MachineInstr &MI,
165 const MachineRegisterInfo &MRI) const {
166 MachineOperand &Op1 = MI.getOperand(i: 1);
167 if (!Op1.isSymbol())
168 return false;
169
170 StringRef Name(Op1.getSymbolName());
171
172 // TODO: Could generalize by parsing to LibcallImpl and checking signature
173 // attributes
174 bool CallReturnsInput =
175 Name == MemcpyName || Name == MemmoveName || Name == MemsetName;
176 if (!CallReturnsInput)
177 return false;
178
179 if (LibInfo->getLibFunc(funcName: Name) == NotLibFunc)
180 return false;
181
182 Register FromReg = MI.getOperand(i: 2).getReg();
183 Register ToReg = MI.getOperand(i: 0).getReg();
184 if (MRI.getRegClass(Reg: FromReg) != MRI.getRegClass(Reg: ToReg))
185 report_fatal_error(reason: "Memory Intrinsic results: call to builtin function "
186 "with wrong signature, from/to mismatch");
187 return replaceDominatedUses(MI, FromReg, ToReg, MRI, MDT&: *MDT, LIS&: *LIS);
188}
189
190bool WebAssemblyMemIntrinsicResultsImpl::runOnMachineFunction(
191 MachineFunction &MF) {
192 LLVM_DEBUG({
193 dbgs() << "********** Memory Intrinsic Results **********\n"
194 << "********** Function: " << MF.getName() << '\n';
195 });
196
197 MachineRegisterInfo &MRI = MF.getRegInfo();
198
199 MemcpyName = RTLIB::RuntimeLibcallsInfo::getLibcallImplName(
200 CallImpl: LibCalls.getLibcallImpl(Call: RTLIB::MEMCPY));
201 MemmoveName = RTLIB::RuntimeLibcallsInfo::getLibcallImplName(
202 CallImpl: LibCalls.getLibcallImpl(Call: RTLIB::MEMMOVE));
203 MemsetName = RTLIB::RuntimeLibcallsInfo::getLibcallImplName(
204 CallImpl: LibCalls.getLibcallImpl(Call: RTLIB::MEMSET));
205
206 bool Changed = false;
207
208 // We don't preserve SSA form.
209 MRI.leaveSSA();
210
211 assert(MRI.tracksLiveness() &&
212 "MemIntrinsicResults expects liveness tracking");
213
214 for (auto &MBB : MF) {
215 LLVM_DEBUG(dbgs() << "Basic Block: " << MBB.getName() << '\n');
216 for (auto &MI : MBB)
217 switch (MI.getOpcode()) {
218 default:
219 break;
220 case WebAssembly::CALL:
221 Changed |= optimizeCall(MBB, MI, MRI);
222 break;
223 }
224 }
225
226 return Changed;
227}
228
229bool WebAssemblyMemIntrinsicResultsLegacy::runOnMachineFunction(
230 MachineFunction &MF) {
231 MachineDominatorTree *MDT =
232 &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
233 LiveIntervals *LIS = &getAnalysis<LiveIntervalsWrapperPass>().getLIS();
234 const TargetLibraryInfo *LibInfo =
235 &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F: MF.getFunction());
236 const WebAssemblySubtarget &Subtarget =
237 MF.getSubtarget<WebAssemblySubtarget>();
238 const LibcallLoweringInfo &LibCalls =
239 getAnalysis<LibcallLoweringInfoWrapper>().getLibcallLowering(
240 M: *MF.getFunction().getParent(), Subtarget);
241 WebAssemblyMemIntrinsicResultsImpl Impl(MDT, LIS, LibInfo, LibCalls);
242 return Impl.runOnMachineFunction(MF);
243}
244
245PreservedAnalyses
246WebAssemblyMemIntrinsicResultsPass::run(MachineFunction &MF,
247 MachineFunctionAnalysisManager &MFAM) {
248 MachineDominatorTree *MDT = &MFAM.getResult<MachineDominatorTreeAnalysis>(IR&: MF);
249 LiveIntervals *LIS = &MFAM.getResult<LiveIntervalsAnalysis>(IR&: MF);
250 const TargetLibraryInfo *LibInfo =
251 &MFAM.getResult<FunctionAnalysisManagerMachineFunctionProxy>(IR&: MF)
252 .getManager()
253 .getResult<TargetLibraryAnalysis>(IR&: MF.getFunction());
254 const WebAssemblySubtarget &Subtarget =
255 MF.getSubtarget<WebAssemblySubtarget>();
256 const LibcallLoweringInfo &LibCalls = getLibcallLowering(
257 ModuleInfo: *MFAM.getResult<ModuleAnalysisManagerMachineFunctionProxy>(IR&: MF)
258 .getCachedResult<LibcallLoweringModuleAnalysis>(
259 IR&: *MF.getFunction().getParent()),
260 Subtarget);
261 WebAssemblyMemIntrinsicResultsImpl Impl(MDT, LIS, LibInfo, LibCalls);
262 bool Changed = Impl.runOnMachineFunction(MF);
263 if (!Changed)
264 return PreservedAnalyses::all();
265 return getMachineFunctionPassPreservedAnalyses()
266 .preserveSet<CFGAnalyses>()
267 .preserve<LiveIntervalsAnalysis>()
268 .preserve<SlotIndexesAnalysis>();
269}
270