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/LiveIntervals.h"
35#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
36#include "llvm/CodeGen/MachineDominators.h"
37#include "llvm/CodeGen/MachineRegisterInfo.h"
38#include "llvm/CodeGen/Passes.h"
39#include "llvm/Support/Debug.h"
40#include "llvm/Support/raw_ostream.h"
41using namespace llvm;
42
43#define DEBUG_TYPE "wasm-mem-intrinsic-results"
44
45namespace {
46class WebAssemblyMemIntrinsicResults final : public MachineFunctionPass {
47public:
48 static char ID; // Pass identification, replacement for typeid
49 WebAssemblyMemIntrinsicResults() : MachineFunctionPass(ID) {}
50
51 StringRef getPassName() const override {
52 return "WebAssembly Memory Intrinsic Results";
53 }
54
55 void getAnalysisUsage(AnalysisUsage &AU) const override {
56 AU.setPreservesCFG();
57 AU.addRequired<MachineBlockFrequencyInfoWrapperPass>();
58 AU.addPreserved<MachineBlockFrequencyInfoWrapperPass>();
59 AU.addRequired<MachineDominatorTreeWrapperPass>();
60 AU.addPreserved<MachineDominatorTreeWrapperPass>();
61 AU.addRequired<LiveIntervalsWrapperPass>();
62 AU.addPreserved<SlotIndexesWrapperPass>();
63 AU.addPreserved<LiveIntervalsWrapperPass>();
64 AU.addRequired<TargetLibraryInfoWrapperPass>();
65 MachineFunctionPass::getAnalysisUsage(AU);
66 }
67
68 bool runOnMachineFunction(MachineFunction &MF) override;
69
70private:
71};
72} // end anonymous namespace
73
74char WebAssemblyMemIntrinsicResults::ID = 0;
75INITIALIZE_PASS(WebAssemblyMemIntrinsicResults, DEBUG_TYPE,
76 "Optimize memory intrinsic result values for WebAssembly",
77 false, false)
78
79FunctionPass *llvm::createWebAssemblyMemIntrinsicResults() {
80 return new WebAssemblyMemIntrinsicResults();
81}
82
83// Replace uses of FromReg with ToReg if they are dominated by MI.
84static bool replaceDominatedUses(MachineBasicBlock &MBB, MachineInstr &MI,
85 unsigned FromReg, unsigned ToReg,
86 const MachineRegisterInfo &MRI,
87 MachineDominatorTree &MDT,
88 LiveIntervals &LIS) {
89 bool Changed = false;
90
91 LiveInterval *FromLI = &LIS.getInterval(Reg: FromReg);
92 LiveInterval *ToLI = &LIS.getInterval(Reg: ToReg);
93
94 SlotIndex FromIdx = LIS.getInstructionIndex(Instr: MI).getRegSlot();
95 VNInfo *FromVNI = FromLI->getVNInfoAt(Idx: FromIdx);
96
97 SmallVector<SlotIndex, 4> Indices;
98
99 for (MachineOperand &O :
100 llvm::make_early_inc_range(Range: MRI.use_nodbg_operands(Reg: FromReg))) {
101 MachineInstr *Where = O.getParent();
102
103 // Check that MI dominates the instruction in the normal way.
104 if (&MI == Where || !MDT.dominates(A: &MI, B: Where))
105 continue;
106
107 // If this use gets a different value, skip it.
108 SlotIndex WhereIdx = LIS.getInstructionIndex(Instr: *Where);
109 VNInfo *WhereVNI = FromLI->getVNInfoAt(Idx: WhereIdx);
110 if (WhereVNI && WhereVNI != FromVNI)
111 continue;
112
113 // Make sure ToReg isn't clobbered before it gets there.
114 VNInfo *ToVNI = ToLI->getVNInfoAt(Idx: WhereIdx);
115 if (ToVNI && ToVNI != FromVNI)
116 continue;
117
118 Changed = true;
119 LLVM_DEBUG(dbgs() << "Setting operand " << O << " in " << *Where << " from "
120 << MI << "\n");
121 O.setReg(ToReg);
122
123 // If the store's def was previously dead, it is no longer.
124 if (!O.isUndef()) {
125 MI.getOperand(i: 0).setIsDead(false);
126
127 Indices.push_back(Elt: WhereIdx.getRegSlot());
128 }
129 }
130
131 if (Changed) {
132 // Extend ToReg's liveness.
133 LIS.extendToIndices(LR&: *ToLI, Indices);
134
135 // Shrink FromReg's liveness.
136 LIS.shrinkToUses(li: FromLI);
137
138 // If we replaced all dominated uses, FromReg is now killed at MI.
139 if (!FromLI->liveAt(index: FromIdx.getDeadSlot()))
140 MI.addRegisterKilled(IncomingReg: FromReg, RegInfo: MBB.getParent()
141 ->getSubtarget<WebAssemblySubtarget>()
142 .getRegisterInfo());
143 }
144
145 return Changed;
146}
147
148static bool optimizeCall(MachineBasicBlock &MBB, MachineInstr &MI,
149 const MachineRegisterInfo &MRI,
150 MachineDominatorTree &MDT, LiveIntervals &LIS,
151 const WebAssemblyTargetLowering &TLI,
152 const TargetLibraryInfo &LibInfo) {
153 MachineOperand &Op1 = MI.getOperand(i: 1);
154 if (!Op1.isSymbol())
155 return false;
156
157 StringRef Name(Op1.getSymbolName());
158 bool CallReturnsInput = Name == TLI.getLibcallName(Call: RTLIB::MEMCPY) ||
159 Name == TLI.getLibcallName(Call: RTLIB::MEMMOVE) ||
160 Name == TLI.getLibcallName(Call: RTLIB::MEMSET);
161 if (!CallReturnsInput)
162 return false;
163
164 LibFunc Func;
165 if (!LibInfo.getLibFunc(funcName: Name, F&: Func))
166 return false;
167
168 Register FromReg = MI.getOperand(i: 2).getReg();
169 Register ToReg = MI.getOperand(i: 0).getReg();
170 if (MRI.getRegClass(Reg: FromReg) != MRI.getRegClass(Reg: ToReg))
171 report_fatal_error(reason: "Memory Intrinsic results: call to builtin function "
172 "with wrong signature, from/to mismatch");
173 return replaceDominatedUses(MBB, MI, FromReg, ToReg, MRI, MDT, LIS);
174}
175
176bool WebAssemblyMemIntrinsicResults::runOnMachineFunction(MachineFunction &MF) {
177 LLVM_DEBUG({
178 dbgs() << "********** Memory Intrinsic Results **********\n"
179 << "********** Function: " << MF.getName() << '\n';
180 });
181
182 MachineRegisterInfo &MRI = MF.getRegInfo();
183 auto &MDT = getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
184 const WebAssemblyTargetLowering &TLI =
185 *MF.getSubtarget<WebAssemblySubtarget>().getTargetLowering();
186 const auto &LibInfo =
187 getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F: MF.getFunction());
188 auto &LIS = getAnalysis<LiveIntervalsWrapperPass>().getLIS();
189 bool Changed = false;
190
191 // We don't preserve SSA form.
192 MRI.leaveSSA();
193
194 assert(MRI.tracksLiveness() &&
195 "MemIntrinsicResults expects liveness tracking");
196
197 for (auto &MBB : MF) {
198 LLVM_DEBUG(dbgs() << "Basic Block: " << MBB.getName() << '\n');
199 for (auto &MI : MBB)
200 switch (MI.getOpcode()) {
201 default:
202 break;
203 case WebAssembly::CALL:
204 Changed |= optimizeCall(MBB, MI, MRI, MDT, LIS, TLI, LibInfo);
205 break;
206 }
207 }
208
209 return Changed;
210}
211