contrib/llvm/lib/Target/WebAssembly/WebAssemblyMemIntrinsicResults.cpp

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