Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/WebAssembly/WebAssemblyExplicitLocals.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- WebAssemblyExplicitLocals.cpp - Make Locals Explicit --------------===//
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 converts any remaining registers into WebAssembly locals.
11
///
12
/// After register stackification and register coloring, convert non-stackified
13
/// registers into locals, inserting explicit local.get and local.set
14
/// instructions.
15
///
16
//===----------------------------------------------------------------------===//
17
18
#include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
19
#include "WebAssembly.h"
20
#include "WebAssemblyMachineFunctionInfo.h"
21
#include "WebAssemblySubtarget.h"
22
#include "WebAssemblyUtilities.h"
23
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
24
#include "llvm/CodeGen/MachineInstrBuilder.h"
25
#include "llvm/CodeGen/MachineRegisterInfo.h"
26
#include "llvm/CodeGen/Passes.h"
27
#include "llvm/Support/Debug.h"
28
#include "llvm/Support/raw_ostream.h"
29
using namespace llvm;
30
31
#define DEBUG_TYPE "wasm-explicit-locals"
32
33
// A command-line option to disable this pass, and keep implicit locals
34
// for the purpose of testing with lit/llc ONLY.
35
// This produces output which is not valid WebAssembly, and is not supported
36
// by assemblers/disassemblers and other MC based tools.
37
static cl::opt<bool> WasmDisableExplicitLocals(
38
    "wasm-disable-explicit-locals", cl::Hidden,
39
    cl::desc("WebAssembly: output implicit locals in"
40
             " instruction output for test purposes only."),
41
    cl::init(false));
42
43
namespace {
44
class WebAssemblyExplicitLocals final : public MachineFunctionPass {
45
4.87k
  StringRef getPassName() const override {
46
4.87k
    return "WebAssembly Explicit Locals";
47
4.87k
  }
48
49
426
  void getAnalysisUsage(AnalysisUsage &AU) const override {
50
426
    AU.setPreservesCFG();
51
426
    AU.addPreserved<MachineBlockFrequencyInfo>();
52
426
    MachineFunctionPass::getAnalysisUsage(AU);
53
426
  }
54
55
  bool runOnMachineFunction(MachineFunction &MF) override;
56
57
public:
58
  static char ID; // Pass identification, replacement for typeid
59
427
  WebAssemblyExplicitLocals() : MachineFunctionPass(ID) {}
60
};
61
} // end anonymous namespace
62
63
char WebAssemblyExplicitLocals::ID = 0;
64
INITIALIZE_PASS(WebAssemblyExplicitLocals, DEBUG_TYPE,
65
                "Convert registers to WebAssembly locals", false, false)
66
67
426
FunctionPass *llvm::createWebAssemblyExplicitLocals() {
68
426
  return new WebAssemblyExplicitLocals();
69
426
}
70
71
/// Return a local id number for the given register, assigning it a new one
72
/// if it doesn't yet have one.
73
static unsigned getLocalId(DenseMap<unsigned, unsigned> &Reg2Local,
74
4.60k
                           unsigned &CurLocal, unsigned Reg) {
75
4.60k
  auto P = Reg2Local.insert(std::make_pair(Reg, CurLocal));
76
4.60k
  if (P.second)
77
935
    ++CurLocal;
78
4.60k
  return P.first->second;
79
4.60k
}
80
81
/// Get the appropriate drop opcode for the given register class.
82
138
static unsigned getDropOpcode(const TargetRegisterClass *RC) {
83
138
  if (RC == &WebAssembly::I32RegClass)
84
102
    return WebAssembly::DROP_I32;
85
36
  if (RC == &WebAssembly::I64RegClass)
86
9
    return WebAssembly::DROP_I64;
87
27
  if (RC == &WebAssembly::F32RegClass)
88
1
    return WebAssembly::DROP_F32;
89
26
  if (RC == &WebAssembly::F64RegClass)
90
1
    return WebAssembly::DROP_F64;
91
25
  if (RC == &WebAssembly::V128RegClass)
92
24
    return WebAssembly::DROP_V128;
93
1
  if (RC == &WebAssembly::EXNREFRegClass)
94
1
    return WebAssembly::DROP_EXNREF;
95
0
  llvm_unreachable("Unexpected register class");
96
0
}
97
98
/// Get the appropriate local.get opcode for the given register class.
99
3.53k
static unsigned getLocalGetOpcode(const TargetRegisterClass *RC) {
100
3.53k
  if (RC == &WebAssembly::I32RegClass)
101
1.99k
    return WebAssembly::LOCAL_GET_I32;
102
1.54k
  if (RC == &WebAssembly::I64RegClass)
103
457
    return WebAssembly::LOCAL_GET_I64;
104
1.08k
  if (RC == &WebAssembly::F32RegClass)
105
109
    return WebAssembly::LOCAL_GET_F32;
106
975
  if (RC == &WebAssembly::F64RegClass)
107
99
    return WebAssembly::LOCAL_GET_F64;
108
876
  if (RC == &WebAssembly::V128RegClass)
109
854
    return WebAssembly::LOCAL_GET_V128;
110
22
  if (RC == &WebAssembly::EXNREFRegClass)
111
22
    return WebAssembly::LOCAL_GET_EXNREF;
112
0
  llvm_unreachable("Unexpected register class");
113
0
}
114
115
/// Get the appropriate local.set opcode for the given register class.
116
728
static unsigned getLocalSetOpcode(const TargetRegisterClass *RC) {
117
728
  if (RC == &WebAssembly::I32RegClass)
118
423
    return WebAssembly::LOCAL_SET_I32;
119
305
  if (RC == &WebAssembly::I64RegClass)
120
54
    return WebAssembly::LOCAL_SET_I64;
121
251
  if (RC == &WebAssembly::F32RegClass)
122
8
    return WebAssembly::LOCAL_SET_F32;
123
243
  if (RC == &WebAssembly::F64RegClass)
124
16
    return WebAssembly::LOCAL_SET_F64;
125
227
  if (RC == &WebAssembly::V128RegClass)
126
215
    return WebAssembly::LOCAL_SET_V128;
127
12
  if (RC == &WebAssembly::EXNREFRegClass)
128
12
    return WebAssembly::LOCAL_SET_EXNREF;
129
0
  llvm_unreachable("Unexpected register class");
130
0
}
131
132
/// Get the appropriate local.tee opcode for the given register class.
133
323
static unsigned getLocalTeeOpcode(const TargetRegisterClass *RC) {
134
323
  if (RC == &WebAssembly::I32RegClass)
135
287
    return WebAssembly::LOCAL_TEE_I32;
136
36
  if (RC == &WebAssembly::I64RegClass)
137
28
    return WebAssembly::LOCAL_TEE_I64;
138
8
  if (RC == &WebAssembly::F32RegClass)
139
0
    return WebAssembly::LOCAL_TEE_F32;
140
8
  if (RC == &WebAssembly::F64RegClass)
141
2
    return WebAssembly::LOCAL_TEE_F64;
142
6
  if (RC == &WebAssembly::V128RegClass)
143
6
    return WebAssembly::LOCAL_TEE_V128;
144
0
  if (RC == &WebAssembly::EXNREFRegClass)
145
0
    return WebAssembly::LOCAL_TEE_EXNREF;
146
0
  llvm_unreachable("Unexpected register class");
147
0
}
148
149
/// Get the type associated with the given register class.
150
935
static MVT typeForRegClass(const TargetRegisterClass *RC) {
151
935
  if (RC == &WebAssembly::I32RegClass)
152
617
    return MVT::i32;
153
318
  if (RC == &WebAssembly::I64RegClass)
154
77
    return MVT::i64;
155
241
  if (RC == &WebAssembly::F32RegClass)
156
7
    return MVT::f32;
157
234
  if (RC == &WebAssembly::F64RegClass)
158
12
    return MVT::f64;
159
222
  if (RC == &WebAssembly::V128RegClass)
160
215
    return MVT::v16i8;
161
7
  if (RC == &WebAssembly::EXNREFRegClass)
162
7
    return MVT::exnref;
163
0
  llvm_unreachable("unrecognized register class");
164
0
}
165
166
/// Given a MachineOperand of a stackified vreg, return the instruction at the
167
/// start of the expression tree.
168
static MachineInstr *findStartOfTree(MachineOperand &MO,
169
                                     MachineRegisterInfo &MRI,
170
7.62k
                                     WebAssemblyFunctionInfo &MFI) {
171
7.62k
  unsigned Reg = MO.getReg();
172
7.62k
  assert(MFI.isVRegStackified(Reg));
173
7.62k
  MachineInstr *Def = MRI.getVRegDef(Reg);
174
7.62k
175
7.62k
  // Find the first stackified use and proceed from there.
176
9.52k
  for (MachineOperand &DefMO : Def->explicit_uses()) {
177
9.52k
    if (!DefMO.isReg())
178
5.47k
      continue;
179
4.05k
    return findStartOfTree(DefMO, MRI, MFI);
180
4.05k
  }
181
7.62k
182
7.62k
  // If there were no stackified uses, we've reached the start.
183
7.62k
  
return Def3.57k
;
184
7.62k
}
185
186
4.45k
bool WebAssemblyExplicitLocals::runOnMachineFunction(MachineFunction &MF) {
187
4.45k
  LLVM_DEBUG(dbgs() << "********** Make Locals Explicit **********\n"
188
4.45k
                       "********** Function: "
189
4.45k
                    << MF.getName() << '\n');
190
4.45k
191
4.45k
  // Disable this pass if directed to do so.
192
4.45k
  if (WasmDisableExplicitLocals)
193
3.03k
    return false;
194
1.41k
195
1.41k
  bool Changed = false;
196
1.41k
  MachineRegisterInfo &MRI = MF.getRegInfo();
197
1.41k
  WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
198
1.41k
  const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
199
1.41k
200
1.41k
  // Map non-stackified virtual registers to their local ids.
201
1.41k
  DenseMap<unsigned, unsigned> Reg2Local;
202
1.41k
203
1.41k
  // Handle ARGUMENTS first to ensure that they get the designated numbers.
204
1.41k
  for (MachineBasicBlock::iterator I = MF.begin()->begin(),
205
1.41k
                                   E = MF.begin()->end();
206
2.92k
       I != E;) {
207
2.92k
    MachineInstr &MI = *I++;
208
2.92k
    if (!WebAssembly::isArgument(MI.getOpcode()))
209
1.41k
      break;
210
1.51k
    unsigned Reg = MI.getOperand(0).getReg();
211
1.51k
    assert(!MFI.isVRegStackified(Reg));
212
1.51k
    Reg2Local[Reg] = static_cast<unsigned>(MI.getOperand(1).getImm());
213
1.51k
    MI.eraseFromParent();
214
1.51k
    Changed = true;
215
1.51k
  }
216
1.41k
217
1.41k
  // Start assigning local numbers after the last parameter.
218
1.41k
  unsigned CurLocal = static_cast<unsigned>(MFI.getParams().size());
219
1.41k
220
1.41k
  // Precompute the set of registers that are unused, so that we can insert
221
1.41k
  // drops to their defs.
222
1.41k
  BitVector UseEmpty(MRI.getNumVirtRegs());
223
11.8k
  for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; 
++I10.4k
)
224
10.4k
    UseEmpty[I] = MRI.use_empty(TargetRegisterInfo::index2VirtReg(I));
225
1.41k
226
1.41k
  // Visit each instruction in the function.
227
1.62k
  for (MachineBasicBlock &MBB : MF) {
228
10.4k
    for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E;) {
229
8.81k
      MachineInstr &MI = *I++;
230
8.81k
      assert(!WebAssembly::isArgument(MI.getOpcode()));
231
8.81k
232
8.81k
      if (MI.isDebugInstr() || 
MI.isLabel()8.78k
)
233
73
        continue;
234
8.74k
235
8.74k
      // Replace tee instructions with local.tee. The difference is that tee
236
8.74k
      // instructions have two defs, while local.tee instructions have one def
237
8.74k
      // and an index of a local to write to.
238
8.74k
      if (WebAssembly::isTee(MI.getOpcode())) {
239
323
        assert(MFI.isVRegStackified(MI.getOperand(0).getReg()));
240
323
        assert(!MFI.isVRegStackified(MI.getOperand(1).getReg()));
241
323
        unsigned OldReg = MI.getOperand(2).getReg();
242
323
        const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
243
323
244
323
        // Stackify the input if it isn't stackified yet.
245
323
        if (!MFI.isVRegStackified(OldReg)) {
246
0
          unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
247
0
          unsigned NewReg = MRI.createVirtualRegister(RC);
248
0
          unsigned Opc = getLocalGetOpcode(RC);
249
0
          BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc), NewReg)
250
0
              .addImm(LocalId);
251
0
          MI.getOperand(2).setReg(NewReg);
252
0
          MFI.stackifyVReg(NewReg);
253
0
        }
254
323
255
323
        // Replace the TEE with a LOCAL_TEE.
256
323
        unsigned LocalId =
257
323
            getLocalId(Reg2Local, CurLocal, MI.getOperand(1).getReg());
258
323
        unsigned Opc = getLocalTeeOpcode(RC);
259
323
        BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc),
260
323
                MI.getOperand(0).getReg())
261
323
            .addImm(LocalId)
262
323
            .addReg(MI.getOperand(2).getReg());
263
323
264
323
        MI.eraseFromParent();
265
323
        Changed = true;
266
323
        continue;
267
323
      }
268
8.42k
269
8.42k
      // Insert local.sets for any defs that aren't stackified yet. Currently
270
8.42k
      // we handle at most one def.
271
8.42k
      assert(MI.getDesc().getNumDefs() <= 1);
272
8.42k
      if (MI.getDesc().getNumDefs() == 1) {
273
4.44k
        unsigned OldReg = MI.getOperand(0).getReg();
274
4.44k
        if (!MFI.isVRegStackified(OldReg)) {
275
866
          const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
276
866
          unsigned NewReg = MRI.createVirtualRegister(RC);
277
866
          auto InsertPt = std::next(MI.getIterator());
278
866
          if (MI.getOpcode() == WebAssembly::IMPLICIT_DEF) {
279
0
            MI.eraseFromParent();
280
0
            Changed = true;
281
0
            continue;
282
0
          }
283
866
          if (UseEmpty[TargetRegisterInfo::virtReg2Index(OldReg)]) {
284
138
            unsigned Opc = getDropOpcode(RC);
285
138
            MachineInstr *Drop =
286
138
                BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc))
287
138
                    .addReg(NewReg);
288
138
            // After the drop instruction, this reg operand will not be used
289
138
            Drop->getOperand(0).setIsKill();
290
728
          } else {
291
728
            unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
292
728
            unsigned Opc = getLocalSetOpcode(RC);
293
728
            BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc))
294
728
                .addImm(LocalId)
295
728
                .addReg(NewReg);
296
728
          }
297
866
          MI.getOperand(0).setReg(NewReg);
298
866
          // This register operand of the original instruction is now being used
299
866
          // by the inserted drop or local.set instruction, so make it not dead
300
866
          // yet.
301
866
          MI.getOperand(0).setIsDead(false);
302
866
          MFI.stackifyVReg(NewReg);
303
866
          Changed = true;
304
866
        }
305
4.44k
      }
306
8.42k
307
8.42k
      // Insert local.gets for any uses that aren't stackified yet.
308
8.42k
      MachineInstr *InsertPt = &MI;
309
11.8k
      for (MachineOperand &MO : reverse(MI.explicit_uses())) {
310
11.8k
        if (!MO.isReg())
311
4.69k
          continue;
312
7.12k
313
7.12k
        unsigned OldReg = MO.getReg();
314
7.12k
315
7.12k
        // Inline asm may have a def in the middle of the operands. Our contract
316
7.12k
        // with inline asm register operands is to provide local indices as
317
7.12k
        // immediates.
318
7.12k
        if (MO.isDef()) {
319
8
          assert(MI.isInlineAsm());
320
8
          unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
321
8
          // If this register operand is tied to another operand, we can't
322
8
          // change it to an immediate. Untie it first.
323
8
          MI.untieRegOperand(MI.getOperandNo(&MO));
324
8
          MO.ChangeToImmediate(LocalId);
325
8
          continue;
326
8
        }
327
7.12k
328
7.12k
        // If we see a stackified register, prepare to insert subsequent
329
7.12k
        // local.gets before the start of its tree.
330
7.12k
        if (MFI.isVRegStackified(OldReg)) {
331
3.57k
          InsertPt = findStartOfTree(MO, MRI, MFI);
332
3.57k
          continue;
333
3.57k
        }
334
3.54k
335
3.54k
        // Our contract with inline asm register operands is to provide local
336
3.54k
        // indices as immediates.
337
3.54k
        if (MI.isInlineAsm()) {
338
8
          unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
339
8
          // Untie it first if this reg operand is tied to another operand.
340
8
          MI.untieRegOperand(MI.getOperandNo(&MO));
341
8
          MO.ChangeToImmediate(LocalId);
342
8
          continue;
343
8
        }
344
3.53k
345
3.53k
        // Insert a local.get.
346
3.53k
        unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
347
3.53k
        const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
348
3.53k
        unsigned NewReg = MRI.createVirtualRegister(RC);
349
3.53k
        unsigned Opc = getLocalGetOpcode(RC);
350
3.53k
        InsertPt =
351
3.53k
            BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc), NewReg)
352
3.53k
                .addImm(LocalId);
353
3.53k
        MO.setReg(NewReg);
354
3.53k
        MFI.stackifyVReg(NewReg);
355
3.53k
        Changed = true;
356
3.53k
      }
357
8.42k
358
8.42k
      // Coalesce and eliminate COPY instructions.
359
8.42k
      if (WebAssembly::isCopy(MI.getOpcode())) {
360
42
        MRI.replaceRegWith(MI.getOperand(1).getReg(),
361
42
                           MI.getOperand(0).getReg());
362
42
        MI.eraseFromParent();
363
42
        Changed = true;
364
42
      }
365
8.42k
    }
366
1.62k
  }
367
1.41k
368
1.41k
  // Define the locals.
369
1.41k
  // TODO: Sort the locals for better compression.
370
1.41k
  MFI.setNumLocals(CurLocal - MFI.getParams().size());
371
16.2k
  for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; 
++I14.8k
) {
372
14.8k
    unsigned Reg = TargetRegisterInfo::index2VirtReg(I);
373
14.8k
    auto RL = Reg2Local.find(Reg);
374
14.8k
    if (RL == Reg2Local.end() || 
RL->second < MFI.getParams().size()2.44k
)
375
13.9k
      continue;
376
935
377
935
    MFI.setLocal(RL->second - MFI.getParams().size(),
378
935
                 typeForRegClass(MRI.getRegClass(Reg)));
379
935
    Changed = true;
380
935
  }
381
1.41k
382
#ifndef NDEBUG
383
  // Assert that all registers have been stackified at this point.
384
  for (const MachineBasicBlock &MBB : MF) {
385
    for (const MachineInstr &MI : MBB) {
386
      if (MI.isDebugInstr() || MI.isLabel())
387
        continue;
388
      for (const MachineOperand &MO : MI.explicit_operands()) {
389
        assert(
390
            (!MO.isReg() || MRI.use_empty(MO.getReg()) ||
391
             MFI.isVRegStackified(MO.getReg())) &&
392
            "WebAssemblyExplicitLocals failed to stackify a register operand");
393
      }
394
    }
395
  }
396
#endif
397
398
1.41k
  return Changed;
399
1.41k
}