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
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<MachineBlockFrequencyInfo>();
58     AU.addPreserved<MachineBlockFrequencyInfo>();
59     AU.addRequired<MachineDominatorTree>();
60     AU.addPreserved<MachineDominatorTree>();
61     AU.addRequired<LiveIntervals>();
62     AU.addPreserved<SlotIndexes>();
63     AU.addPreserved<LiveIntervals>();
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 
79 FunctionPass *llvm::createWebAssemblyMemIntrinsicResults() {
80   return new WebAssemblyMemIntrinsicResults();
81 }
82 
83 // Replace uses of FromReg with ToReg if they are dominated by MI.
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 
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 
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<MachineDominatorTree>();
184   const WebAssemblyTargetLowering &TLI =
185       *MF.getSubtarget<WebAssemblySubtarget>().getTargetLowering();
186   const auto &LibInfo =
187       getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(MF.getFunction());
188   auto &LIS = getAnalysis<LiveIntervals>();
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