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 (auto I = MRI.use_nodbg_begin(FromReg), E = MRI.use_nodbg_end(); 100 I != E;) { 101 MachineOperand &O = *I++; 102 MachineInstr *Where = O.getParent(); 103 104 // Check that MI dominates the instruction in the normal way. 105 if (&MI == Where || !MDT.dominates(&MI, Where)) 106 continue; 107 108 // If this use gets a different value, skip it. 109 SlotIndex WhereIdx = LIS.getInstructionIndex(*Where); 110 VNInfo *WhereVNI = FromLI->getVNInfoAt(WhereIdx); 111 if (WhereVNI && WhereVNI != FromVNI) 112 continue; 113 114 // Make sure ToReg isn't clobbered before it gets there. 115 VNInfo *ToVNI = ToLI->getVNInfoAt(WhereIdx); 116 if (ToVNI && ToVNI != FromVNI) 117 continue; 118 119 Changed = true; 120 LLVM_DEBUG(dbgs() << "Setting operand " << O << " in " << *Where << " from " 121 << MI << "\n"); 122 O.setReg(ToReg); 123 124 // If the store's def was previously dead, it is no longer. 125 if (!O.isUndef()) { 126 MI.getOperand(0).setIsDead(false); 127 128 Indices.push_back(WhereIdx.getRegSlot()); 129 } 130 } 131 132 if (Changed) { 133 // Extend ToReg's liveness. 134 LIS.extendToIndices(*ToLI, Indices); 135 136 // Shrink FromReg's liveness. 137 LIS.shrinkToUses(FromLI); 138 139 // If we replaced all dominated uses, FromReg is now killed at MI. 140 if (!FromLI->liveAt(FromIdx.getDeadSlot())) 141 MI.addRegisterKilled(FromReg, MBB.getParent() 142 ->getSubtarget<WebAssemblySubtarget>() 143 .getRegisterInfo()); 144 } 145 146 return Changed; 147 } 148 149 static bool optimizeCall(MachineBasicBlock &MBB, MachineInstr &MI, 150 const MachineRegisterInfo &MRI, 151 MachineDominatorTree &MDT, LiveIntervals &LIS, 152 const WebAssemblyTargetLowering &TLI, 153 const TargetLibraryInfo &LibInfo) { 154 MachineOperand &Op1 = MI.getOperand(1); 155 if (!Op1.isSymbol()) 156 return false; 157 158 StringRef Name(Op1.getSymbolName()); 159 bool CallReturnsInput = Name == TLI.getLibcallName(RTLIB::MEMCPY) || 160 Name == TLI.getLibcallName(RTLIB::MEMMOVE) || 161 Name == TLI.getLibcallName(RTLIB::MEMSET); 162 if (!CallReturnsInput) 163 return false; 164 165 LibFunc Func; 166 if (!LibInfo.getLibFunc(Name, Func)) 167 return false; 168 169 unsigned FromReg = MI.getOperand(2).getReg(); 170 unsigned ToReg = MI.getOperand(0).getReg(); 171 if (MRI.getRegClass(FromReg) != MRI.getRegClass(ToReg)) 172 report_fatal_error("Memory Intrinsic results: call to builtin function " 173 "with wrong signature, from/to mismatch"); 174 return replaceDominatedUses(MBB, MI, FromReg, ToReg, MRI, MDT, LIS); 175 } 176 177 bool WebAssemblyMemIntrinsicResults::runOnMachineFunction(MachineFunction &MF) { 178 LLVM_DEBUG({ 179 dbgs() << "********** Memory Intrinsic Results **********\n" 180 << "********** Function: " << MF.getName() << '\n'; 181 }); 182 183 MachineRegisterInfo &MRI = MF.getRegInfo(); 184 auto &MDT = getAnalysis<MachineDominatorTree>(); 185 const WebAssemblyTargetLowering &TLI = 186 *MF.getSubtarget<WebAssemblySubtarget>().getTargetLowering(); 187 const auto &LibInfo = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(); 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_i32: 204 case WebAssembly::CALL_i64: 205 Changed |= optimizeCall(MBB, MI, MRI, MDT, LIS, TLI, LibInfo); 206 break; 207 } 208 } 209 210 return Changed; 211 } 212