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

   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   StringRef getPassName() const override { return "WebAssembly Store Results"; }
  50
  51   void getAnalysisUsage(AnalysisUsage &AU) const override {
  52     AU.setPreservesCFG();
  53     AU.addRequired<MachineBlockFrequencyInfo>();
  54     AU.addPreserved<MachineBlockFrequencyInfo>();
  55     AU.addRequired<MachineDominatorTree>();
  56     AU.addPreserved<MachineDominatorTree>();
  57     AU.addRequired<LiveIntervals>();
  58     AU.addPreserved<SlotIndexes>();
  59     AU.addPreserved<LiveIntervals>();
  60     AU.addRequired<TargetLibraryInfoWrapperPass>();
  61     MachineFunctionPass::getAnalysisUsage(AU);
  62   }
  63
  64   bool runOnMachineFunction(MachineFunction &MF) override;
  65
  66 private:
  67 };
  68 } // end anonymous namespace
  69
  70 char WebAssemblyStoreResults::ID = 0;
  71 FunctionPass *llvm::createWebAssemblyStoreResults() {
  72   return new WebAssemblyStoreResults();
  73 }
  74
  75 // Replace uses of FromReg with ToReg if they are dominated by MI.
  76 static bool ReplaceDominatedUses(MachineBasicBlock &MBB, MachineInstr &MI,
  77                                  unsigned FromReg, unsigned ToReg,
  78                                  const MachineRegisterInfo &MRI,
  79                                  MachineDominatorTree &MDT,
  80                                  LiveIntervals &LIS) {
  81   bool Changed = false;
  82
  83   LiveInterval *FromLI = &LIS.getInterval(FromReg);
  84   LiveInterval *ToLI = &LIS.getInterval(ToReg);
  85
  86   SlotIndex FromIdx = LIS.getInstructionIndex(MI).getRegSlot();
  87   VNInfo *FromVNI = FromLI->getVNInfoAt(FromIdx);
  88
  89   SmallVector<SlotIndex, 4> Indices;
  90
  91   for (auto I = MRI.use_nodbg_begin(FromReg), E = MRI.use_nodbg_end(); I != E;) {
  92     MachineOperand &O = *I++;
  93     MachineInstr *Where = O.getParent();
  94
  95     // Check that MI dominates the instruction in the normal way.
  96     if (&MI == Where || !MDT.dominates(&MI, Where))
  97       continue;
  98
  99     // If this use gets a different value, skip it.
 100     SlotIndex WhereIdx = LIS.getInstructionIndex(*Where);
 101     VNInfo *WhereVNI = FromLI->getVNInfoAt(WhereIdx);
 102     if (WhereVNI && WhereVNI != FromVNI)
 103       continue;
 104
 105     // Make sure ToReg isn't clobbered before it gets there.
 106     VNInfo *ToVNI = ToLI->getVNInfoAt(WhereIdx);
 107     if (ToVNI && ToVNI != FromVNI)
 108       continue;
 109
 110     Changed = true;
 111     DEBUG(dbgs() << "Setting operand " << O << " in " << *Where << " from "
 112                  << MI << "\n");
 113     O.setReg(ToReg);
 114
 115     // If the store's def was previously dead, it is no longer.
 116     if (!O.isUndef()) {
 117       MI.getOperand(0).setIsDead(false);
 118
 119       Indices.push_back(WhereIdx.getRegSlot());
 120     }
 121   }
 122
 123   if (Changed) {
 124     // Extend ToReg's liveness.
 125     LIS.extendToIndices(*ToLI, Indices);
 126
 127     // Shrink FromReg's liveness.
 128     LIS.shrinkToUses(FromLI);
 129
 130     // If we replaced all dominated uses, FromReg is now killed at MI.
 131     if (!FromLI->liveAt(FromIdx.getDeadSlot()))
 132       MI.addRegisterKilled(FromReg,
 133                            MBB.getParent()->getSubtarget<WebAssemblySubtarget>()
 134                                  .getRegisterInfo());
 135   }
 136
 137   return Changed;
 138 }
 139
 140 static bool optimizeCall(MachineBasicBlock &MBB, MachineInstr &MI,
 141                          const MachineRegisterInfo &MRI,
 142                          MachineDominatorTree &MDT,
 143                          LiveIntervals &LIS,
 144                          const WebAssemblyTargetLowering &TLI,
 145                          const TargetLibraryInfo &LibInfo) {
 146   MachineOperand &Op1 = MI.getOperand(1);
 147   if (!Op1.isSymbol())
 148     return false;
 149
 150   StringRef Name(Op1.getSymbolName());
 151   bool callReturnsInput = Name == TLI.getLibcallName(RTLIB::MEMCPY) ||
 152                           Name == TLI.getLibcallName(RTLIB::MEMMOVE) ||
 153                           Name == TLI.getLibcallName(RTLIB::MEMSET);
 154   if (!callReturnsInput)
 155     return false;
 156
 157   LibFunc Func;
 158   if (!LibInfo.getLibFunc(Name, Func))
 159     return false;
 160
 161   unsigned FromReg = MI.getOperand(2).getReg();
 162   unsigned ToReg = MI.getOperand(0).getReg();
 163   if (MRI.getRegClass(FromReg) != MRI.getRegClass(ToReg))
 164     report_fatal_error("Store results: call to builtin function with wrong "
 165                        "signature, from/to mismatch");
 166   return ReplaceDominatedUses(MBB, MI, FromReg, ToReg, MRI, MDT, LIS);
 167 }
 168
 169 bool WebAssemblyStoreResults::runOnMachineFunction(MachineFunction &MF) {
 170   DEBUG({
 171     dbgs() << "********** Store Results **********\n"
 172            << "********** Function: " << MF.getName() << '\n';
 173   });
 174
 175   MachineRegisterInfo &MRI = MF.getRegInfo();
 176   MachineDominatorTree &MDT = getAnalysis<MachineDominatorTree>();
 177   const WebAssemblyTargetLowering &TLI =
 178       *MF.getSubtarget<WebAssemblySubtarget>().getTargetLowering();
 179   const auto &LibInfo = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
 180   LiveIntervals &LIS = getAnalysis<LiveIntervals>();
 181   bool Changed = false;
 182
 183   // We don't preserve SSA form.
 184   MRI.leaveSSA();
 185
 186   assert(MRI.tracksLiveness() && "StoreResults expects liveness tracking");
 187
 188   for (auto &MBB : MF) {
 189     DEBUG(dbgs() << "Basic Block: " << MBB.getName() << '\n');
 190     for (auto &MI : MBB)
 191       switch (MI.getOpcode()) {
 192       default:
 193         break;
 194       case WebAssembly::CALL_I32:
 195       case WebAssembly::CALL_I64:
 196         Changed |= optimizeCall(MBB, MI, MRI, MDT, LIS, TLI, LibInfo);
 197         break;
 198       }
 199   }
 200
 201   return Changed;
 202 }