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"
41using namespace llvm;
42
43#define DEBUG_TYPE "wasm-mem-intrinsic-results"
44
45namespace {
46class WebAssemblyMemIntrinsicResults final : public MachineFunctionPass {
47public:
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
70private:
71};
72} // end anonymous namespace
73
74char WebAssemblyMemIntrinsicResults::ID = 0;
75INITIALIZE_PASS(WebAssemblyMemIntrinsicResults, DEBUG_TYPE,
76                "Optimize memory intrinsic result values for WebAssembly",
77                false, false)
78
79FunctionPass *llvm::createWebAssemblyMemIntrinsicResults() {
80  return new WebAssemblyMemIntrinsicResults();
81}
82
83// Replace uses of FromReg with ToReg if they are dominated by MI.
84static 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
149static 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  Register FromReg = MI.getOperand(2).getReg();
170  Register 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
177bool 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 =
188      getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(MF.getFunction());
189  auto &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}
213