1 //===-- WebAssemblyStoreResults.cpp - Optimize using store result values --===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 ///
10 /// \file
11 /// \brief This file implements an optimization pass using store result values.
12 ///
13 /// WebAssembly's store instructions return the stored value. This is to enable
14 /// an optimization wherein uses of the stored value can be replaced by uses of
15 /// the store's result value, making the stored value register more likely to
16 /// be single-use, thus more likely to be useful to register stackifying, and
17 /// potentially also exposing the store to register stackifying. These both can
18 /// reduce get_local/set_local traffic.
19 ///
20 /// This pass also performs this optimization for memcpy, memmove, and memset
21 /// calls, since the LLVM intrinsics for these return void so they can't use the
22 /// returned attribute and consequently aren't handled by the OptimizeReturned
23 /// pass.
24 ///
25 //===----------------------------------------------------------------------===//
26 
27 #include "WebAssembly.h"
28 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
29 #include "WebAssemblyMachineFunctionInfo.h"
30 #include "WebAssemblySubtarget.h"
31 #include "llvm/Analysis/TargetLibraryInfo.h"
32 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
33 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
34 #include "llvm/CodeGen/MachineDominators.h"
35 #include "llvm/CodeGen/MachineRegisterInfo.h"
36 #include "llvm/CodeGen/Passes.h"
37 #include "llvm/Support/Debug.h"
38 #include "llvm/Support/raw_ostream.h"
39 using namespace llvm;
40 
41 #define DEBUG_TYPE "wasm-store-results"
42 
43 namespace {
44 class WebAssemblyStoreResults final : public MachineFunctionPass {
45 public:
46   static char ID; // Pass identification, replacement for typeid
WebAssemblyStoreResults()47   WebAssemblyStoreResults() : MachineFunctionPass(ID) {}
48 
getPassName() const49   const char *getPassName() const override {
50     return "WebAssembly Store Results";
51   }
52 
getAnalysisUsage(AnalysisUsage & AU) const53   void getAnalysisUsage(AnalysisUsage &AU) const override {
54     AU.setPreservesCFG();
55     AU.addRequired<MachineBlockFrequencyInfo>();
56     AU.addPreserved<MachineBlockFrequencyInfo>();
57     AU.addRequired<MachineDominatorTree>();
58     AU.addPreserved<MachineDominatorTree>();
59     AU.addRequired<LiveIntervals>();
60     AU.addPreserved<SlotIndexes>();
61     AU.addPreserved<LiveIntervals>();
62     AU.addRequired<TargetLibraryInfoWrapperPass>();
63     MachineFunctionPass::getAnalysisUsage(AU);
64   }
65 
66   bool runOnMachineFunction(MachineFunction &MF) override;
67 
68 private:
69 };
70 } // end anonymous namespace
71 
72 char WebAssemblyStoreResults::ID = 0;
createWebAssemblyStoreResults()73 FunctionPass *llvm::createWebAssemblyStoreResults() {
74   return new WebAssemblyStoreResults();
75 }
76 
77 // 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)78 static bool ReplaceDominatedUses(MachineBasicBlock &MBB, MachineInstr &MI,
79                                  unsigned FromReg, unsigned ToReg,
80                                  const MachineRegisterInfo &MRI,
81                                  MachineDominatorTree &MDT,
82                                  LiveIntervals &LIS) {
83   bool Changed = false;
84 
85   LiveInterval *FromLI = &LIS.getInterval(FromReg);
86   LiveInterval *ToLI = &LIS.getInterval(ToReg);
87 
88   SlotIndex FromIdx = LIS.getInstructionIndex(MI).getRegSlot();
89   VNInfo *FromVNI = FromLI->getVNInfoAt(FromIdx);
90 
91   SmallVector<SlotIndex, 4> Indices;
92 
93   for (auto I = MRI.use_begin(FromReg), E = MRI.use_end(); I != E;) {
94     MachineOperand &O = *I++;
95     MachineInstr *Where = O.getParent();
96 
97     // Check that MI dominates the instruction in the normal way.
98     if (&MI == Where || !MDT.dominates(&MI, Where))
99       continue;
100 
101     // If this use gets a different value, skip it.
102     SlotIndex WhereIdx = LIS.getInstructionIndex(*Where);
103     VNInfo *WhereVNI = FromLI->getVNInfoAt(WhereIdx);
104     if (WhereVNI && WhereVNI != FromVNI)
105       continue;
106 
107     // Make sure ToReg isn't clobbered before it gets there.
108     VNInfo *ToVNI = ToLI->getVNInfoAt(WhereIdx);
109     if (ToVNI && ToVNI != FromVNI)
110       continue;
111 
112     Changed = true;
113     DEBUG(dbgs() << "Setting operand " << O << " in " << *Where << " from "
114                  << MI << "\n");
115     O.setReg(ToReg);
116 
117     // If the store's def was previously dead, it is no longer.
118     if (!O.isUndef()) {
119       MI.getOperand(0).setIsDead(false);
120 
121       Indices.push_back(WhereIdx.getRegSlot());
122     }
123   }
124 
125   if (Changed) {
126     // Extend ToReg's liveness.
127     LIS.extendToIndices(*ToLI, Indices);
128 
129     // Shrink FromReg's liveness.
130     LIS.shrinkToUses(FromLI);
131 
132     // If we replaced all dominated uses, FromReg is now killed at MI.
133     if (!FromLI->liveAt(FromIdx.getDeadSlot()))
134       MI.addRegisterKilled(FromReg,
135                            MBB.getParent()->getSubtarget<WebAssemblySubtarget>()
136                                  .getRegisterInfo());
137   }
138 
139   return Changed;
140 }
141 
optimizeStore(MachineBasicBlock & MBB,MachineInstr & MI,const MachineRegisterInfo & MRI,MachineDominatorTree & MDT,LiveIntervals & LIS)142 static bool optimizeStore(MachineBasicBlock &MBB, MachineInstr &MI,
143                           const MachineRegisterInfo &MRI,
144                           MachineDominatorTree &MDT,
145                           LiveIntervals &LIS) {
146   unsigned ToReg = MI.getOperand(0).getReg();
147   unsigned FromReg = MI.getOperand(WebAssembly::StoreValueOperandNo).getReg();
148   return ReplaceDominatedUses(MBB, MI, FromReg, ToReg, MRI, MDT, LIS);
149 }
150 
optimizeCall(MachineBasicBlock & MBB,MachineInstr & MI,const MachineRegisterInfo & MRI,MachineDominatorTree & MDT,LiveIntervals & LIS,const WebAssemblyTargetLowering & TLI,const TargetLibraryInfo & LibInfo)151 static bool optimizeCall(MachineBasicBlock &MBB, MachineInstr &MI,
152                          const MachineRegisterInfo &MRI,
153                          MachineDominatorTree &MDT,
154                          LiveIntervals &LIS,
155                          const WebAssemblyTargetLowering &TLI,
156                          const TargetLibraryInfo &LibInfo) {
157   MachineOperand &Op1 = MI.getOperand(1);
158   if (!Op1.isSymbol())
159     return false;
160 
161   StringRef Name(Op1.getSymbolName());
162   bool callReturnsInput = Name == TLI.getLibcallName(RTLIB::MEMCPY) ||
163                           Name == TLI.getLibcallName(RTLIB::MEMMOVE) ||
164                           Name == TLI.getLibcallName(RTLIB::MEMSET);
165   if (!callReturnsInput)
166     return false;
167 
168   LibFunc::Func Func;
169   if (!LibInfo.getLibFunc(Name, Func))
170     return false;
171 
172   unsigned FromReg = MI.getOperand(2).getReg();
173   unsigned ToReg = MI.getOperand(0).getReg();
174   if (MRI.getRegClass(FromReg) != MRI.getRegClass(ToReg))
175     report_fatal_error("Store results: call to builtin function with wrong "
176                        "signature, from/to mismatch");
177   return ReplaceDominatedUses(MBB, MI, FromReg, ToReg, MRI, MDT, LIS);
178 }
179 
runOnMachineFunction(MachineFunction & MF)180 bool WebAssemblyStoreResults::runOnMachineFunction(MachineFunction &MF) {
181   DEBUG({
182     dbgs() << "********** Store Results **********\n"
183            << "********** Function: " << MF.getName() << '\n';
184   });
185 
186   MachineRegisterInfo &MRI = MF.getRegInfo();
187   MachineDominatorTree &MDT = getAnalysis<MachineDominatorTree>();
188   const WebAssemblyTargetLowering &TLI =
189       *MF.getSubtarget<WebAssemblySubtarget>().getTargetLowering();
190   const auto &LibInfo = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
191   LiveIntervals &LIS = getAnalysis<LiveIntervals>();
192   bool Changed = false;
193 
194   // We don't preserve SSA form.
195   MRI.leaveSSA();
196 
197   assert(MRI.tracksLiveness() && "StoreResults expects liveness tracking");
198 
199   for (auto &MBB : MF) {
200     DEBUG(dbgs() << "Basic Block: " << MBB.getName() << '\n');
201     for (auto &MI : MBB)
202       switch (MI.getOpcode()) {
203       default:
204         break;
205       case WebAssembly::STORE8_I32:
206       case WebAssembly::STORE16_I32:
207       case WebAssembly::STORE8_I64:
208       case WebAssembly::STORE16_I64:
209       case WebAssembly::STORE32_I64:
210       case WebAssembly::STORE_F32:
211       case WebAssembly::STORE_F64:
212       case WebAssembly::STORE_I32:
213       case WebAssembly::STORE_I64:
214         Changed |= optimizeStore(MBB, MI, MRI, MDT, LIS);
215         break;
216       case WebAssembly::CALL_I32:
217       case WebAssembly::CALL_I64:
218         Changed |= optimizeCall(MBB, MI, MRI, MDT, LIS, TLI, LibInfo);
219         break;
220       }
221   }
222 
223   return Changed;
224 }
225