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"
41 using namespace llvm;
42
43 #define DEBUG_TYPE "wasm-mem-intrinsic-results"
44
45 namespace {
46 class WebAssemblyMemIntrinsicResults final : public MachineFunctionPass {
47 public:
48 static char ID; // Pass identification, replacement for typeid
WebAssemblyMemIntrinsicResults()49 WebAssemblyMemIntrinsicResults() : MachineFunctionPass(ID) {}
50
getPassName() const51 StringRef getPassName() const override {
52 return "WebAssembly Memory Intrinsic Results";
53 }
54
getAnalysisUsage(AnalysisUsage & AU) const55 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
70 private:
71 };
72 } // end anonymous namespace
73
74 char WebAssemblyMemIntrinsicResults::ID = 0;
75 INITIALIZE_PASS(WebAssemblyMemIntrinsicResults, DEBUG_TYPE,
76 "Optimize memory intrinsic result values for WebAssembly",
77 false, false)
78
createWebAssemblyMemIntrinsicResults()79 FunctionPass *llvm::createWebAssemblyMemIntrinsicResults() {
80 return new WebAssemblyMemIntrinsicResults();
81 }
82
83 // 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)84 static 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(FromReg);
92 LiveInterval *ToLI = &LIS.getInterval(ToReg);
93
94 SlotIndex FromIdx = LIS.getInstructionIndex(MI).getRegSlot();
95 VNInfo *FromVNI = FromLI->getVNInfoAt(FromIdx);
96
97 SmallVector<SlotIndex, 4> Indices;
98
99 for (MachineOperand &O :
100 llvm::make_early_inc_range(MRI.use_nodbg_operands(FromReg))) {
101 MachineInstr *Where = O.getParent();
102
103 // Check that MI dominates the instruction in the normal way.
104 if (&MI == Where || !MDT.dominates(&MI, Where))
105 continue;
106
107 // If this use gets a different value, skip it.
108 SlotIndex WhereIdx = LIS.getInstructionIndex(*Where);
109 VNInfo *WhereVNI = FromLI->getVNInfoAt(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(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(0).setIsDead(false);
126
127 Indices.push_back(WhereIdx.getRegSlot());
128 }
129 }
130
131 if (Changed) {
132 // Extend ToReg's liveness.
133 LIS.extendToIndices(*ToLI, Indices);
134
135 // Shrink FromReg's liveness.
136 LIS.shrinkToUses(FromLI);
137
138 // If we replaced all dominated uses, FromReg is now killed at MI.
139 if (!FromLI->liveAt(FromIdx.getDeadSlot()))
140 MI.addRegisterKilled(FromReg, MBB.getParent()
141 ->getSubtarget<WebAssemblySubtarget>()
142 .getRegisterInfo());
143 }
144
145 return Changed;
146 }
147
optimizeCall(MachineBasicBlock & MBB,MachineInstr & MI,const MachineRegisterInfo & MRI,MachineDominatorTree & MDT,LiveIntervals & LIS,const WebAssemblyTargetLowering & TLI,const TargetLibraryInfo & LibInfo)148 static 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(1);
154 if (!Op1.isSymbol())
155 return false;
156
157 StringRef Name(Op1.getSymbolName());
158 bool CallReturnsInput = Name == TLI.getLibcallName(RTLIB::MEMCPY) ||
159 Name == TLI.getLibcallName(RTLIB::MEMMOVE) ||
160 Name == TLI.getLibcallName(RTLIB::MEMSET);
161 if (!CallReturnsInput)
162 return false;
163
164 LibFunc Func;
165 if (!LibInfo.getLibFunc(Name, Func))
166 return false;
167
168 Register FromReg = MI.getOperand(2).getReg();
169 Register ToReg = MI.getOperand(0).getReg();
170 if (MRI.getRegClass(FromReg) != MRI.getRegClass(ToReg))
171 report_fatal_error("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
runOnMachineFunction(MachineFunction & MF)176 bool 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(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