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 47 WebAssemblyStoreResults() : MachineFunctionPass(ID) {} 48 49 const char *getPassName() const override { 50 return "WebAssembly Store Results"; 51 } 52 53 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; 73 FunctionPass *llvm::createWebAssemblyStoreResults() { 74 return new WebAssemblyStoreResults(); 75 } 76 77 // Replace uses of FromReg with ToReg if they are dominated by MI. 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 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 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 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
