Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- WebAssemblyCFGStackify.cpp - CFG Stackification -------------------===//
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 a CFG stacking pass.
11
///
12
/// This pass inserts BLOCK, LOOP, and TRY markers to mark the start of scopes,
13
/// since scope boundaries serve as the labels for WebAssembly's control
14
/// transfers.
15
///
16
/// This is sufficient to convert arbitrary CFGs into a form that works on
17
/// WebAssembly, provided that all loops are single-entry.
18
///
19
/// In case we use exceptions, this pass also fixes mismatches in unwind
20
/// destinations created during transforming CFG into wasm structured format.
21
///
22
//===----------------------------------------------------------------------===//
23
24
#include "WebAssembly.h"
25
#include "WebAssemblyExceptionInfo.h"
26
#include "WebAssemblyMachineFunctionInfo.h"
27
#include "WebAssemblySubtarget.h"
28
#include "WebAssemblyUtilities.h"
29
#include "llvm/ADT/Statistic.h"
30
#include "llvm/CodeGen/MachineDominators.h"
31
#include "llvm/CodeGen/MachineInstrBuilder.h"
32
#include "llvm/MC/MCAsmInfo.h"
33
using namespace llvm;
34
35
#define DEBUG_TYPE "wasm-cfg-stackify"
36
37
STATISTIC(NumUnwindMismatches, "Number of EH pad unwind mismatches found");
38
39
namespace {
40
class WebAssemblyCFGStackify final : public MachineFunctionPass {
41
4.88k
  StringRef getPassName() const override { return "WebAssembly CFG Stackify"; }
42
43
429
  void getAnalysisUsage(AnalysisUsage &AU) const override {
44
429
    AU.addRequired<MachineDominatorTree>();
45
429
    AU.addRequired<MachineLoopInfo>();
46
429
    AU.addRequired<WebAssemblyExceptionInfo>();
47
429
    MachineFunctionPass::getAnalysisUsage(AU);
48
429
  }
49
50
  bool runOnMachineFunction(MachineFunction &MF) override;
51
52
  // For each block whose label represents the end of a scope, record the block
53
  // which holds the beginning of the scope. This will allow us to quickly skip
54
  // over scoped regions when walking blocks.
55
  SmallVector<MachineBasicBlock *, 8> ScopeTops;
56
57
  // Placing markers.
58
  void placeMarkers(MachineFunction &MF);
59
  void placeBlockMarker(MachineBasicBlock &MBB);
60
  void placeLoopMarker(MachineBasicBlock &MBB);
61
  void placeTryMarker(MachineBasicBlock &MBB);
62
  void removeUnnecessaryInstrs(MachineFunction &MF);
63
  bool fixUnwindMismatches(MachineFunction &MF);
64
  void rewriteDepthImmediates(MachineFunction &MF);
65
  void fixEndsAtEndOfFunction(MachineFunction &MF);
66
67
  // For each BLOCK|LOOP|TRY, the corresponding END_(BLOCK|LOOP|TRY).
68
  DenseMap<const MachineInstr *, MachineInstr *> BeginToEnd;
69
  // For each END_(BLOCK|LOOP|TRY), the corresponding BLOCK|LOOP|TRY.
70
  DenseMap<const MachineInstr *, MachineInstr *> EndToBegin;
71
  // <TRY marker, EH pad> map
72
  DenseMap<const MachineInstr *, MachineBasicBlock *> TryToEHPad;
73
  // <EH pad, TRY marker> map
74
  DenseMap<const MachineBasicBlock *, MachineInstr *> EHPadToTry;
75
76
  // There can be an appendix block at the end of each function, shared for:
77
  // - creating a correct signature for fallthrough returns
78
  // - target for rethrows that need to unwind to the caller, but are trapped
79
  //   inside another try/catch
80
  MachineBasicBlock *AppendixBB = nullptr;
81
27
  MachineBasicBlock *getAppendixBlock(MachineFunction &MF) {
82
27
    if (!AppendixBB) {
83
25
      AppendixBB = MF.CreateMachineBasicBlock();
84
25
      // Give it a fake predecessor so that AsmPrinter prints its label.
85
25
      AppendixBB->addSuccessor(AppendixBB);
86
25
      MF.push_back(AppendixBB);
87
25
    }
88
27
    return AppendixBB;
89
27
  }
90
91
  // Helper functions to register / unregister scope information created by
92
  // marker instructions.
93
  void registerScope(MachineInstr *Begin, MachineInstr *End);
94
  void registerTryScope(MachineInstr *Begin, MachineInstr *End,
95
                        MachineBasicBlock *EHPad);
96
  void unregisterScope(MachineInstr *Begin);
97
98
public:
99
  static char ID; // Pass identification, replacement for typeid
100
429
  WebAssemblyCFGStackify() : MachineFunctionPass(ID) {}
101
421
  ~WebAssemblyCFGStackify() override { releaseMemory(); }
102
  void releaseMemory() override;
103
};
104
} // end anonymous namespace
105
106
char WebAssemblyCFGStackify::ID = 0;
107
INITIALIZE_PASS(WebAssemblyCFGStackify, DEBUG_TYPE,
108
                "Insert BLOCK/LOOP/TRY markers for WebAssembly scopes", false,
109
                false)
110
111
426
FunctionPass *llvm::createWebAssemblyCFGStackify() {
112
426
  return new WebAssemblyCFGStackify();
113
426
}
114
115
/// Test whether Pred has any terminators explicitly branching to MBB, as
116
/// opposed to falling through. Note that it's possible (eg. in unoptimized
117
/// code) for a branch instruction to both branch to a block and fallthrough
118
/// to it, so we check the actual branch operands to see if there are any
119
/// explicit mentions.
120
static bool explicitlyBranchesTo(MachineBasicBlock *Pred,
121
911
                                 MachineBasicBlock *MBB) {
122
911
  for (MachineInstr &MI : Pred->terminators())
123
724
    for (MachineOperand &MO : MI.explicit_operands())
124
1.29k
      if (MO.isMBB() && 
MO.getMBB() == MBB914
)
125
424
        return true;
126
911
  
return false487
;
127
911
}
128
129
// Returns an iterator to the earliest position possible within the MBB,
130
// satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet
131
// contains instructions that should go before the marker, and AfterSet contains
132
// ones that should go after the marker. In this function, AfterSet is only
133
// used for sanity checking.
134
static MachineBasicBlock::iterator
135
getEarliestInsertPos(MachineBasicBlock *MBB,
136
                     const SmallPtrSet<const MachineInstr *, 4> &BeforeSet,
137
617
                     const SmallPtrSet<const MachineInstr *, 4> &AfterSet) {
138
617
  auto InsertPos = MBB->end();
139
2.48k
  while (InsertPos != MBB->begin()) {
140
1.94k
    if (BeforeSet.count(&*std::prev(InsertPos))) {
141
#ifndef NDEBUG
142
      // Sanity check
143
      for (auto Pos = InsertPos, E = MBB->begin(); Pos != E; --Pos)
144
        assert(!AfterSet.count(&*std::prev(Pos)));
145
#endif
146
      break;
147
82
    }
148
1.86k
    --InsertPos;
149
1.86k
  }
150
617
  return InsertPos;
151
617
}
152
153
// Returns an iterator to the latest position possible within the MBB,
154
// satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet
155
// contains instructions that should go before the marker, and AfterSet contains
156
// ones that should go after the marker. In this function, BeforeSet is only
157
// used for sanity checking.
158
static MachineBasicBlock::iterator
159
getLatestInsertPos(MachineBasicBlock *MBB,
160
                   const SmallPtrSet<const MachineInstr *, 4> &BeforeSet,
161
437
                   const SmallPtrSet<const MachineInstr *, 4> &AfterSet) {
162
437
  auto InsertPos = MBB->begin();
163
1.62k
  while (InsertPos != MBB->end()) {
164
1.62k
    if (AfterSet.count(&*InsertPos)) {
165
#ifndef NDEBUG
166
      // Sanity check
167
      for (auto Pos = InsertPos, E = MBB->end(); Pos != E; ++Pos)
168
        assert(!BeforeSet.count(&*Pos));
169
#endif
170
      break;
171
437
    }
172
1.19k
    ++InsertPos;
173
1.19k
  }
174
437
  return InsertPos;
175
437
}
176
177
void WebAssemblyCFGStackify::registerScope(MachineInstr *Begin,
178
537
                                           MachineInstr *End) {
179
537
  BeginToEnd[Begin] = End;
180
537
  EndToBegin[End] = Begin;
181
537
}
182
183
void WebAssemblyCFGStackify::registerTryScope(MachineInstr *Begin,
184
                                              MachineInstr *End,
185
81
                                              MachineBasicBlock *EHPad) {
186
81
  registerScope(Begin, End);
187
81
  TryToEHPad[Begin] = EHPad;
188
81
  EHPadToTry[EHPad] = Begin;
189
81
}
190
191
44
void WebAssemblyCFGStackify::unregisterScope(MachineInstr *Begin) {
192
44
  assert(BeginToEnd.count(Begin));
193
44
  MachineInstr *End = BeginToEnd[Begin];
194
44
  assert(EndToBegin.count(End));
195
44
  BeginToEnd.erase(Begin);
196
44
  EndToBegin.erase(End);
197
44
  MachineBasicBlock *EHPad = TryToEHPad.lookup(Begin);
198
44
  if (EHPad) {
199
0
    assert(EHPadToTry.count(EHPad));
200
0
    TryToEHPad.erase(Begin);
201
0
    EHPadToTry.erase(EHPad);
202
0
  }
203
44
}
204
205
/// Insert a BLOCK marker for branches to MBB (if needed).
206
// TODO Consider a more generalized way of handling block (and also loop and
207
// try) signatures when we implement the multi-value proposal later.
208
5.23k
void WebAssemblyCFGStackify::placeBlockMarker(MachineBasicBlock &MBB) {
209
5.23k
  assert(!MBB.isEHPad());
210
5.23k
  MachineFunction &MF = *MBB.getParent();
211
5.23k
  auto &MDT = getAnalysis<MachineDominatorTree>();
212
5.23k
  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
213
5.23k
  const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
214
5.23k
215
5.23k
  // First compute the nearest common dominator of all forward non-fallthrough
216
5.23k
  // predecessors so that we minimize the time that the BLOCK is on the stack,
217
5.23k
  // which reduces overall stack height.
218
5.23k
  MachineBasicBlock *Header = nullptr;
219
5.23k
  bool IsBranchedTo = false;
220
5.23k
  bool IsBrOnExn = false;
221
5.23k
  MachineInstr *BrOnExn = nullptr;
222
5.23k
  int MBBNumber = MBB.getNumber();
223
5.23k
  for (MachineBasicBlock *Pred : MBB.predecessors()) {
224
1.04k
    if (Pred->getNumber() < MBBNumber) {
225
911
      Header = Header ? 
MDT.findNearestCommonDominator(Header, Pred)150
:
Pred761
;
226
911
      if (explicitlyBranchesTo(Pred, &MBB)) {
227
424
        IsBranchedTo = true;
228
424
        if (Pred->getFirstTerminator()->getOpcode() == WebAssembly::BR_ON_EXN) {
229
41
          IsBrOnExn = true;
230
41
          assert(!BrOnExn && "There should be only one br_on_exn per block");
231
41
          BrOnExn = &*Pred->getFirstTerminator();
232
41
        }
233
424
      }
234
911
    }
235
1.04k
  }
236
5.23k
  if (!Header)
237
4.47k
    return;
238
758
  if (!IsBranchedTo)
239
393
    return;
240
365
241
365
  assert(&MBB != &MF.front() && "Header blocks shouldn't have predecessors");
242
365
  MachineBasicBlock *LayoutPred = MBB.getPrevNode();
243
365
244
365
  // If the nearest common dominator is inside a more deeply nested context,
245
365
  // walk out to the nearest scope which isn't more deeply nested.
246
750
  for (MachineFunction::iterator I(LayoutPred), E(Header); I != E; 
--I385
) {
247
530
    if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) {
248
260
      if (ScopeTop->getNumber() > Header->getNumber()) {
249
115
        // Skip over an intervening scope.
250
115
        I = std::next(ScopeTop->getIterator());
251
145
      } else {
252
145
        // We found a scope level at an appropriate depth.
253
145
        Header = ScopeTop;
254
145
        break;
255
145
      }
256
260
    }
257
530
  }
258
365
259
365
  // Decide where in Header to put the BLOCK.
260
365
261
365
  // Instructions that should go before the BLOCK.
262
365
  SmallPtrSet<const MachineInstr *, 4> BeforeSet;
263
365
  // Instructions that should go after the BLOCK.
264
365
  SmallPtrSet<const MachineInstr *, 4> AfterSet;
265
2.39k
  for (const auto &MI : *Header) {
266
2.39k
    // If there is a previously placed LOOP marker and the bottom block of the
267
2.39k
    // loop is above MBB, it should be after the BLOCK, because the loop is
268
2.39k
    // nested in this BLOCK. Otherwise it should be before the BLOCK.
269
2.39k
    if (MI.getOpcode() == WebAssembly::LOOP) {
270
66
      auto *LoopBottom = BeginToEnd[&MI]->getParent()->getPrevNode();
271
66
      if (MBB.getNumber() > LoopBottom->getNumber())
272
16
        AfterSet.insert(&MI);
273
#ifndef NDEBUG
274
      else
275
        BeforeSet.insert(&MI);
276
#endif
277
    }
278
2.39k
279
2.39k
    // All previously inserted BLOCK/TRY markers should be after the BLOCK
280
2.39k
    // because they are all nested blocks.
281
2.39k
    if (MI.getOpcode() == WebAssembly::BLOCK ||
282
2.39k
        
MI.getOpcode() == WebAssembly::TRY2.24k
)
283
204
      AfterSet.insert(&MI);
284
2.39k
285
#ifndef NDEBUG
286
    // All END_(BLOCK|LOOP|TRY) markers should be before the BLOCK.
287
    if (MI.getOpcode() == WebAssembly::END_BLOCK ||
288
        MI.getOpcode() == WebAssembly::END_LOOP ||
289
        MI.getOpcode() == WebAssembly::END_TRY)
290
      BeforeSet.insert(&MI);
291
#endif
292
293
2.39k
    // Terminators should go after the BLOCK.
294
2.39k
    if (MI.isTerminator())
295
360
      AfterSet.insert(&MI);
296
2.39k
  }
297
365
298
365
  // Local expression tree should go after the BLOCK.
299
974
  for (auto I = Header->getFirstTerminator(), E = Header->begin(); I != E;
300
940
       
--I609
) {
301
940
    if (std::prev(I)->isDebugInstr() || 
std::prev(I)->isPosition()935
)
302
57
      continue;
303
883
    if (WebAssembly::isChild(*std::prev(I), MFI))
304
552
      AfterSet.insert(&*std::prev(I));
305
331
    else
306
331
      break;
307
883
  }
308
365
309
365
  // Add the BLOCK.
310
365
311
365
  // 'br_on_exn' extracts exnref object and pushes variable number of values
312
365
  // depending on its tag. For C++ exception, its a single i32 value, and the
313
365
  // generated code will be in the form of:
314
365
  // block i32
315
365
  //   br_on_exn 0, $__cpp_exception
316
365
  //   rethrow
317
365
  // end_block
318
365
  WebAssembly::ExprType ReturnType = WebAssembly::ExprType::Void;
319
365
  if (IsBrOnExn) {
320
41
    const char *TagName = BrOnExn->getOperand(1).getSymbolName();
321
41
    if (std::strcmp(TagName, "__cpp_exception") != 0)
322
41
      
llvm_unreachable0
("Only C++ exception is supported");
323
41
    ReturnType = WebAssembly::ExprType::I32;
324
41
  }
325
365
326
365
  auto InsertPos = getLatestInsertPos(Header, BeforeSet, AfterSet);
327
365
  MachineInstr *Begin =
328
365
      BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos),
329
365
              TII.get(WebAssembly::BLOCK))
330
365
          .addImm(int64_t(ReturnType));
331
365
332
365
  // Decide where in Header to put the END_BLOCK.
333
365
  BeforeSet.clear();
334
365
  AfterSet.clear();
335
1.15k
  for (auto &MI : MBB) {
336
#ifndef NDEBUG
337
    // END_BLOCK should precede existing LOOP and TRY markers.
338
    if (MI.getOpcode() == WebAssembly::LOOP ||
339
        MI.getOpcode() == WebAssembly::TRY)
340
      AfterSet.insert(&MI);
341
#endif
342
343
1.15k
    // If there is a previously placed END_LOOP marker and the header of the
344
1.15k
    // loop is above this block's header, the END_LOOP should be placed after
345
1.15k
    // the BLOCK, because the loop contains this block. Otherwise the END_LOOP
346
1.15k
    // should be placed before the BLOCK. The same for END_TRY.
347
1.15k
    if (MI.getOpcode() == WebAssembly::END_LOOP ||
348
1.15k
        
MI.getOpcode() == WebAssembly::END_TRY1.12k
) {
349
91
      if (EndToBegin[&MI]->getParent()->getNumber() >= Header->getNumber())
350
89
        BeforeSet.insert(&MI);
351
#ifndef NDEBUG
352
      else
353
        AfterSet.insert(&MI);
354
#endif
355
    }
356
1.15k
  }
357
365
358
365
  // Mark the end of the block.
359
365
  InsertPos = getEarliestInsertPos(&MBB, BeforeSet, AfterSet);
360
365
  MachineInstr *End = BuildMI(MBB, InsertPos, MBB.findPrevDebugLoc(InsertPos),
361
365
                              TII.get(WebAssembly::END_BLOCK));
362
365
  registerScope(Begin, End);
363
365
364
365
  // Track the farthest-spanning scope that ends at this point.
365
365
  int Number = MBB.getNumber();
366
365
  if (!ScopeTops[Number] ||
367
365
      
ScopeTops[Number]->getNumber() > Header->getNumber()82
)
368
308
    ScopeTops[Number] = Header;
369
365
}
370
371
/// Insert a LOOP marker for a loop starting at MBB (if it's a loop header).
372
5.29k
void WebAssemblyCFGStackify::placeLoopMarker(MachineBasicBlock &MBB) {
373
5.29k
  MachineFunction &MF = *MBB.getParent();
374
5.29k
  const auto &MLI = getAnalysis<MachineLoopInfo>();
375
5.29k
  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
376
5.29k
377
5.29k
  MachineLoop *Loop = MLI.getLoopFor(&MBB);
378
5.29k
  if (!Loop || 
Loop->getHeader() != &MBB213
)
379
5.21k
    return;
380
88
381
88
  // The operand of a LOOP is the first block after the loop. If the loop is the
382
88
  // bottom of the function, insert a dummy block at the end.
383
88
  MachineBasicBlock *Bottom = WebAssembly::getBottom(Loop);
384
88
  auto Iter = std::next(Bottom->getIterator());
385
88
  if (Iter == MF.end()) {
386
21
    getAppendixBlock(MF);
387
21
    Iter = std::next(Bottom->getIterator());
388
21
  }
389
88
  MachineBasicBlock *AfterLoop = &*Iter;
390
88
391
88
  // Decide where in Header to put the LOOP.
392
88
  SmallPtrSet<const MachineInstr *, 4> BeforeSet;
393
88
  SmallPtrSet<const MachineInstr *, 4> AfterSet;
394
527
  for (const auto &MI : MBB) {
395
527
    // LOOP marker should be after any existing loop that ends here. Otherwise
396
527
    // we assume the instruction belongs to the loop.
397
527
    if (MI.getOpcode() == WebAssembly::END_LOOP)
398
0
      BeforeSet.insert(&MI);
399
#ifndef NDEBUG
400
    else
401
      AfterSet.insert(&MI);
402
#endif
403
  }
404
88
405
88
  // Mark the beginning of the loop.
406
88
  auto InsertPos = getEarliestInsertPos(&MBB, BeforeSet, AfterSet);
407
88
  MachineInstr *Begin = BuildMI(MBB, InsertPos, MBB.findDebugLoc(InsertPos),
408
88
                                TII.get(WebAssembly::LOOP))
409
88
                            .addImm(int64_t(WebAssembly::ExprType::Void));
410
88
411
88
  // Decide where in Header to put the END_LOOP.
412
88
  BeforeSet.clear();
413
88
  AfterSet.clear();
414
#ifndef NDEBUG
415
  for (const auto &MI : MBB)
416
    // Existing END_LOOP markers belong to parent loops of this loop
417
    if (MI.getOpcode() == WebAssembly::END_LOOP)
418
      AfterSet.insert(&MI);
419
#endif
420
421
88
  // Mark the end of the loop (using arbitrary debug location that branched to
422
88
  // the loop end as its location).
423
88
  InsertPos = getEarliestInsertPos(AfterLoop, BeforeSet, AfterSet);
424
88
  DebugLoc EndDL = AfterLoop->pred_empty()
425
88
                       ? 
DebugLoc()1
426
88
                       : 
(*AfterLoop->pred_rbegin())->findBranchDebugLoc()87
;
427
88
  MachineInstr *End =
428
88
      BuildMI(*AfterLoop, InsertPos, EndDL, TII.get(WebAssembly::END_LOOP));
429
88
  registerScope(Begin, End);
430
88
431
88
  assert((!ScopeTops[AfterLoop->getNumber()] ||
432
88
          ScopeTops[AfterLoop->getNumber()]->getNumber() < MBB.getNumber()) &&
433
88
         "With block sorting the outermost loop for a block should be first.");
434
88
  if (!ScopeTops[AfterLoop->getNumber()])
435
88
    ScopeTops[AfterLoop->getNumber()] = &MBB;
436
88
}
437
438
71
void WebAssemblyCFGStackify::placeTryMarker(MachineBasicBlock &MBB) {
439
71
  assert(MBB.isEHPad());
440
71
  MachineFunction &MF = *MBB.getParent();
441
71
  auto &MDT = getAnalysis<MachineDominatorTree>();
442
71
  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
443
71
  const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>();
444
71
  const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
445
71
446
71
  // Compute the nearest common dominator of all unwind predecessors
447
71
  MachineBasicBlock *Header = nullptr;
448
71
  int MBBNumber = MBB.getNumber();
449
80
  for (auto *Pred : MBB.predecessors()) {
450
80
    if (Pred->getNumber() < MBBNumber) {
451
80
      Header = Header ? 
MDT.findNearestCommonDominator(Header, Pred)9
:
Pred71
;
452
80
      assert(!explicitlyBranchesTo(Pred, &MBB) &&
453
80
             "Explicit branch to an EH pad!");
454
80
    }
455
80
  }
456
71
  if (!Header)
457
0
    return;
458
71
459
71
  // If this try is at the bottom of the function, insert a dummy block at the
460
71
  // end.
461
71
  WebAssemblyException *WE = WEI.getExceptionFor(&MBB);
462
71
  assert(WE);
463
71
  MachineBasicBlock *Bottom = WebAssembly::getBottom(WE);
464
71
465
71
  auto Iter = std::next(Bottom->getIterator());
466
71
  if (Iter == MF.end()) {
467
1
    getAppendixBlock(MF);
468
1
    Iter = std::next(Bottom->getIterator());
469
1
  }
470
71
  MachineBasicBlock *Cont = &*Iter;
471
71
472
71
  assert(Cont != &MF.front());
473
71
  MachineBasicBlock *LayoutPred = Cont->getPrevNode();
474
71
475
71
  // If the nearest common dominator is inside a more deeply nested context,
476
71
  // walk out to the nearest scope which isn't more deeply nested.
477
374
  for (MachineFunction::iterator I(LayoutPred), E(Header); I != E; 
--I303
) {
478
313
    if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) {
479
14
      if (ScopeTop->getNumber() > Header->getNumber()) {
480
4
        // Skip over an intervening scope.
481
4
        I = std::next(ScopeTop->getIterator());
482
10
      } else {
483
10
        // We found a scope level at an appropriate depth.
484
10
        Header = ScopeTop;
485
10
        break;
486
10
      }
487
14
    }
488
313
  }
489
71
490
71
  // Decide where in Header to put the TRY.
491
71
492
71
  // Instructions that should go before the TRY.
493
71
  SmallPtrSet<const MachineInstr *, 4> BeforeSet;
494
71
  // Instructions that should go after the TRY.
495
71
  SmallPtrSet<const MachineInstr *, 4> AfterSet;
496
406
  for (const auto &MI : *Header) {
497
406
    // If there is a previously placed LOOP marker and the bottom block of the
498
406
    // loop is above MBB, it should be after the TRY, because the loop is nested
499
406
    // in this TRY. Otherwise it should be before the TRY.
500
406
    if (MI.getOpcode() == WebAssembly::LOOP) {
501
7
      auto *LoopBottom = BeginToEnd[&MI]->getParent()->getPrevNode();
502
7
      if (MBB.getNumber() > LoopBottom->getNumber())
503
1
        AfterSet.insert(&MI);
504
#ifndef NDEBUG
505
      else
506
        BeforeSet.insert(&MI);
507
#endif
508
    }
509
406
510
406
    // All previously inserted BLOCK/TRY markers should be after the TRY because
511
406
    // they are all nested trys.
512
406
    if (MI.getOpcode() == WebAssembly::BLOCK ||
513
406
        
MI.getOpcode() == WebAssembly::TRY396
)
514
12
      AfterSet.insert(&MI);
515
406
516
#ifndef NDEBUG
517
    // All END_(BLOCK/LOOP/TRY) markers should be before the TRY.
518
    if (MI.getOpcode() == WebAssembly::END_BLOCK ||
519
        MI.getOpcode() == WebAssembly::END_LOOP ||
520
        MI.getOpcode() == WebAssembly::END_TRY)
521
      BeforeSet.insert(&MI);
522
#endif
523
524
406
    // Terminators should go after the TRY.
525
406
    if (MI.isTerminator())
526
63
      AfterSet.insert(&MI);
527
406
  }
528
71
529
71
  // Local expression tree should go after the TRY.
530
142
  for (auto I = Header->getFirstTerminator(), E = Header->begin(); I != E;
531
142
       
--I71
) {
532
142
    if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition())
533
63
      continue;
534
79
    if (WebAssembly::isChild(*std::prev(I), MFI))
535
8
      AfterSet.insert(&*std::prev(I));
536
71
    else
537
71
      break;
538
79
  }
539
71
540
71
  // If Header unwinds to MBB (= Header contains 'invoke'), the try block should
541
71
  // contain the call within it. So the call should go after the TRY. The
542
71
  // exception is when the header's terminator is a rethrow instruction, in
543
71
  // which case that instruction, not a call instruction before it, is gonna
544
71
  // throw.
545
71
  if (MBB.isPredecessor(Header)) {
546
61
    auto TermPos = Header->getFirstTerminator();
547
61
    if (TermPos == Header->end() ||
548
61
        
TermPos->getOpcode() != WebAssembly::RETHROW55
) {
549
177
      for (const auto &MI : reverse(*Header)) {
550
177
        if (MI.isCall()) {
551
61
          AfterSet.insert(&MI);
552
61
          // Possibly throwing calls are usually wrapped by EH_LABEL
553
61
          // instructions. We don't want to split them and the call.
554
61
          if (MI.getIterator() != Header->begin() &&
555
61
              std::prev(MI.getIterator())->isEHLabel())
556
61
            AfterSet.insert(&*std::prev(MI.getIterator()));
557
61
          break;
558
61
        }
559
177
      }
560
61
    }
561
61
  }
562
71
563
71
  // Add the TRY.
564
71
  auto InsertPos = getLatestInsertPos(Header, BeforeSet, AfterSet);
565
71
  MachineInstr *Begin =
566
71
      BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos),
567
71
              TII.get(WebAssembly::TRY))
568
71
          .addImm(int64_t(WebAssembly::ExprType::Void));
569
71
570
71
  // Decide where in Header to put the END_TRY.
571
71
  BeforeSet.clear();
572
71
  AfterSet.clear();
573
137
  for (const auto &MI : *Cont) {
574
#ifndef NDEBUG
575
    // END_TRY should precede existing LOOP and BLOCK markers.
576
    if (MI.getOpcode() == WebAssembly::LOOP ||
577
        MI.getOpcode() == WebAssembly::BLOCK)
578
      AfterSet.insert(&MI);
579
580
    // All END_TRY markers placed earlier belong to exceptions that contains
581
    // this one.
582
    if (MI.getOpcode() == WebAssembly::END_TRY)
583
      AfterSet.insert(&MI);
584
#endif
585
586
137
    // If there is a previously placed END_LOOP marker and its header is after
587
137
    // where TRY marker is, this loop is contained within the 'catch' part, so
588
137
    // the END_TRY marker should go after that. Otherwise, the whole try-catch
589
137
    // is contained within this loop, so the END_TRY should go before that.
590
137
    if (MI.getOpcode() == WebAssembly::END_LOOP) {
591
7
      // For a LOOP to be after TRY, LOOP's BB should be after TRY's BB; if they
592
7
      // are in the same BB, LOOP is always before TRY.
593
7
      if (EndToBegin[&MI]->getParent()->getNumber() > Header->getNumber())
594
2
        BeforeSet.insert(&MI);
595
#ifndef NDEBUG
596
      else
597
        AfterSet.insert(&MI);
598
#endif
599
    }
600
137
601
137
    // It is not possible for an END_BLOCK to be already in this block.
602
137
  }
603
71
604
71
  // Mark the end of the TRY.
605
71
  InsertPos = getEarliestInsertPos(Cont, BeforeSet, AfterSet);
606
71
  MachineInstr *End =
607
71
      BuildMI(*Cont, InsertPos, Bottom->findBranchDebugLoc(),
608
71
              TII.get(WebAssembly::END_TRY));
609
71
  registerTryScope(Begin, End, &MBB);
610
71
611
71
  // Track the farthest-spanning scope that ends at this point. We create two
612
71
  // mappings: (BB with 'end_try' -> BB with 'try') and (BB with 'catch' -> BB
613
71
  // with 'try'). We need to create 'catch' -> 'try' mapping here too because
614
71
  // markers should not span across 'catch'. For example, this should not
615
71
  // happen:
616
71
  //
617
71
  // try
618
71
  //   block     --|  (X)
619
71
  // catch         |
620
71
  //   end_block --|
621
71
  // end_try
622
142
  for (int Number : {Cont->getNumber(), MBB.getNumber()}) {
623
142
    if (!ScopeTops[Number] ||
624
142
        
ScopeTops[Number]->getNumber() > Header->getNumber()13
)
625
132
      ScopeTops[Number] = Header;
626
142
  }
627
71
}
628
629
42
void WebAssemblyCFGStackify::removeUnnecessaryInstrs(MachineFunction &MF) {
630
42
  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
631
42
632
42
  // When there is an unconditional branch right before a catch instruction and
633
42
  // it branches to the end of end_try marker, we don't need the branch, because
634
42
  // it there is no exception, the control flow transfers to that point anyway.
635
42
  // bb0:
636
42
  //   try
637
42
  //     ...
638
42
  //     br bb2      <- Not necessary
639
42
  // bb1:
640
42
  //   catch
641
42
  //     ...
642
42
  // bb2:
643
42
  //   end
644
365
  for (auto &MBB : MF) {
645
365
    if (!MBB.isEHPad())
646
284
      continue;
647
81
648
81
    MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
649
81
    SmallVector<MachineOperand, 4> Cond;
650
81
    MachineBasicBlock *EHPadLayoutPred = MBB.getPrevNode();
651
81
    MachineBasicBlock *Cont = BeginToEnd[EHPadToTry[&MBB]]->getParent();
652
81
    bool Analyzable = !TII.analyzeBranch(*EHPadLayoutPred, TBB, FBB, Cond);
653
81
    if (Analyzable && 
(73
(73
Cond.empty()73
&&
TBB73
&&
TBB == Cont63
) ||
654
73
                       
(24
!Cond.empty()24
&&
FBB0
&&
FBB == Cont0
)))
655
49
      TII.removeBranch(*EHPadLayoutPred);
656
81
  }
657
42
658
42
  // When there are block / end_block markers that overlap with try / end_try
659
42
  // markers, and the block and try markers' return types are the same, the
660
42
  // block /end_block markers are not necessary, because try / end_try markers
661
42
  // also can serve as boundaries for branches.
662
42
  // block         <- Not necessary
663
42
  //   try
664
42
  //     ...
665
42
  //   catch
666
42
  //     ...
667
42
  //   end
668
42
  // end           <- Not necessary
669
42
  SmallVector<MachineInstr *, 32> ToDelete;
670
365
  for (auto &MBB : MF) {
671
1.63k
    for (auto &MI : MBB) {
672
1.63k
      if (MI.getOpcode() != WebAssembly::TRY)
673
1.55k
        continue;
674
81
675
81
      MachineInstr *Try = &MI, *EndTry = BeginToEnd[Try];
676
81
      MachineBasicBlock *TryBB = Try->getParent();
677
81
      MachineBasicBlock *Cont = EndTry->getParent();
678
81
      int64_t RetType = Try->getOperand(0).getImm();
679
81
      for (auto B = Try->getIterator(), E = std::next(EndTry->getIterator());
680
125
           B != TryBB->begin() && 
E != Cont->end()112
&&
681
125
           
std::prev(B)->getOpcode() == WebAssembly::BLOCK110
&&
682
125
           
E->getOpcode() == WebAssembly::END_BLOCK52
&&
683
125
           
std::prev(B)->getOperand(0).getImm() == RetType44
;
684
81
           
--B, ++E44
) {
685
44
        ToDelete.push_back(&*std::prev(B));
686
44
        ToDelete.push_back(&*E);
687
44
      }
688
81
    }
689
365
  }
690
88
  for (auto *MI : ToDelete) {
691
88
    if (MI->getOpcode() == WebAssembly::BLOCK)
692
44
      unregisterScope(MI);
693
88
    MI->eraseFromParent();
694
88
  }
695
42
}
696
697
4.45k
bool WebAssemblyCFGStackify::fixUnwindMismatches(MachineFunction &MF) {
698
4.45k
  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
699
4.45k
  MachineRegisterInfo &MRI = MF.getRegInfo();
700
4.45k
701
4.45k
  // Linearizing the control flow by placing TRY / END_TRY markers can create
702
4.45k
  // mismatches in unwind destinations. There are two kinds of mismatches we
703
4.45k
  // try to solve here.
704
4.45k
705
4.45k
  // 1. When an instruction may throw, but the EH pad it will unwind to can be
706
4.45k
  //    different from the original CFG.
707
4.45k
  //
708
4.45k
  // Example: we have the following CFG:
709
4.45k
  // bb0:
710
4.45k
  //   call @foo (if it throws, unwind to bb2)
711
4.45k
  // bb1:
712
4.45k
  //   call @bar (if it throws, unwind to bb3)
713
4.45k
  // bb2 (ehpad):
714
4.45k
  //   catch
715
4.45k
  //   ...
716
4.45k
  // bb3 (ehpad)
717
4.45k
  //   catch
718
4.45k
  //   handler body
719
4.45k
  //
720
4.45k
  // And the CFG is sorted in this order. Then after placing TRY markers, it
721
4.45k
  // will look like: (BB markers are omitted)
722
4.45k
  // try $label1
723
4.45k
  //   try
724
4.45k
  //     call @foo
725
4.45k
  //     call @bar   (if it throws, unwind to bb3)
726
4.45k
  //   catch         <- ehpad (bb2)
727
4.45k
  //     ...
728
4.45k
  //   end_try
729
4.45k
  // catch           <- ehpad (bb3)
730
4.45k
  //   handler body
731
4.45k
  // end_try
732
4.45k
  //
733
4.45k
  // Now if bar() throws, it is going to end up ip in bb2, not bb3, where it
734
4.45k
  // is supposed to end up. We solve this problem by
735
4.45k
  // a. Split the target unwind EH pad (here bb3) so that the handler body is
736
4.45k
  //    right after 'end_try', which means we extract the handler body out of
737
4.45k
  //    the catch block. We do this because this handler body should be
738
4.45k
  //    somewhere branch-eable from the inner scope.
739
4.45k
  // b. Wrap the call that has an incorrect unwind destination ('call @bar'
740
4.45k
  //    here) with a nested try/catch/end_try scope, and within the new catch
741
4.45k
  //    block, branches to the handler body.
742
4.45k
  // c. Place a branch after the newly inserted nested end_try so it can bypass
743
4.45k
  //    the handler body, which is now outside of a catch block.
744
4.45k
  //
745
4.45k
  // The result will like as follows. (new: a) means this instruction is newly
746
4.45k
  // created in the process of doing 'a' above.
747
4.45k
  //
748
4.45k
  // block $label0                 (new: placeBlockMarker)
749
4.45k
  //   try $label1
750
4.45k
  //     try
751
4.45k
  //       call @foo
752
4.45k
  //       try                     (new: b)
753
4.45k
  //         call @bar
754
4.45k
  //       catch                   (new: b)
755
4.45k
  //         local.set n / drop    (new: b)
756
4.45k
  //         br $label1            (new: b)
757
4.45k
  //       end_try                 (new: b)
758
4.45k
  //     catch                     <- ehpad (bb2)
759
4.45k
  //     end_try
760
4.45k
  //     br $label0                (new: c)
761
4.45k
  //   catch                       <- ehpad (bb3)
762
4.45k
  //   end_try                     (hoisted: a)
763
4.45k
  //   handler body
764
4.45k
  // end_block                     (new: placeBlockMarker)
765
4.45k
  //
766
4.45k
  // Note that the new wrapping block/end_block will be generated later in
767
4.45k
  // placeBlockMarker.
768
4.45k
  //
769
4.45k
  // TODO Currently local.set and local.gets are generated to move exnref value
770
4.45k
  // created by catches. That's because we don't support yielding values from a
771
4.45k
  // block in LLVM machine IR yet, even though it is supported by wasm. Delete
772
4.45k
  // unnecessary local.get/local.sets once yielding values from a block is
773
4.45k
  // supported. The full EH spec requires multi-value support to do this, but
774
4.45k
  // for C++ we don't yet need it because we only throw a single i32.
775
4.45k
  //
776
4.45k
  // ---
777
4.45k
  // 2. The same as 1, but in this case an instruction unwinds to a caller
778
4.45k
  //    function and not another EH pad.
779
4.45k
  //
780
4.45k
  // Example: we have the following CFG:
781
4.45k
  // bb0:
782
4.45k
  //   call @foo (if it throws, unwind to bb2)
783
4.45k
  // bb1:
784
4.45k
  //   call @bar (if it throws, unwind to caller)
785
4.45k
  // bb2 (ehpad):
786
4.45k
  //   catch
787
4.45k
  //   ...
788
4.45k
  //
789
4.45k
  // And the CFG is sorted in this order. Then after placing TRY markers, it
790
4.45k
  // will look like:
791
4.45k
  // try
792
4.45k
  //   call @foo
793
4.45k
  //   call @bar   (if it throws, unwind to caller)
794
4.45k
  // catch         <- ehpad (bb2)
795
4.45k
  //   ...
796
4.45k
  // end_try
797
4.45k
  //
798
4.45k
  // Now if bar() throws, it is going to end up ip in bb2, when it is supposed
799
4.45k
  // throw up to the caller.
800
4.45k
  // We solve this problem by
801
4.45k
  // a. Create a new 'appendix' BB at the end of the function and put a single
802
4.45k
  //    'rethrow' instruction (+ local.get) in there.
803
4.45k
  // b. Wrap the call that has an incorrect unwind destination ('call @bar'
804
4.45k
  //    here) with a nested try/catch/end_try scope, and within the new catch
805
4.45k
  //    block, branches to the new appendix block.
806
4.45k
  //
807
4.45k
  // block $label0          (new: placeBlockMarker)
808
4.45k
  //   try
809
4.45k
  //     call @foo
810
4.45k
  //     try                (new: b)
811
4.45k
  //       call @bar
812
4.45k
  //     catch              (new: b)
813
4.45k
  //       local.set n      (new: b)
814
4.45k
  //       br $label0       (new: b)
815
4.45k
  //     end_try            (new: b)
816
4.45k
  //   catch                <- ehpad (bb2)
817
4.45k
  //     ...
818
4.45k
  //   end_try
819
4.45k
  // ...
820
4.45k
  // end_block              (new: placeBlockMarker)
821
4.45k
  // local.get n            (new: a)  <- appendix block
822
4.45k
  // rethrow                (new: a)
823
4.45k
  //
824
4.45k
  // In case there are multiple calls in a BB that may throw to the caller, they
825
4.45k
  // can be wrapped together in one nested try scope. (In 1, this couldn't
826
4.45k
  // happen, because may-throwing instruction there had an unwind destination,
827
4.45k
  // i.e., it was an invoke before, and there could be only one invoke within a
828
4.45k
  // BB.)
829
4.45k
830
4.45k
  SmallVector<const MachineBasicBlock *, 8> EHPadStack;
831
4.45k
  // Range of intructions to be wrapped in a new nested try/catch
832
4.45k
  using TryRange = std::pair<MachineInstr *, MachineInstr *>;
833
4.45k
  // In original CFG, <unwind destionation BB, a vector of try ranges>
834
4.45k
  DenseMap<MachineBasicBlock *, SmallVector<TryRange, 4>> UnwindDestToTryRanges;
835
4.45k
  // In new CFG, <destination to branch to, a vector of try ranges>
836
4.45k
  DenseMap<MachineBasicBlock *, SmallVector<TryRange, 4>> BrDestToTryRanges;
837
4.45k
  // In new CFG, <destination to branch to, register containing exnref>
838
4.45k
  DenseMap<MachineBasicBlock *, unsigned> BrDestToExnReg;
839
4.45k
840
4.45k
  // Gather possibly throwing calls (i.e., previously invokes) whose current
841
4.45k
  // unwind destination is not the same as the original CFG.
842
5.30k
  for (auto &MBB : reverse(MF)) {
843
5.30k
    bool SeenThrowableInstInBB = false;
844
50.9k
    for (auto &MI : reverse(MBB)) {
845
50.9k
      if (MI.getOpcode() == WebAssembly::TRY)
846
71
        EHPadStack.pop_back();
847
50.8k
      else if (MI.getOpcode() == WebAssembly::CATCH)
848
71
        EHPadStack.push_back(MI.getParent());
849
50.9k
850
50.9k
      // In this loop we only gather calls that have an EH pad to unwind. So
851
50.9k
      // there will be at most 1 such call (= invoke) in a BB, so after we've
852
50.9k
      // seen one, we can skip the rest of BB. Also if MBB has no EH pad
853
50.9k
      // successor or MI does not throw, this is not an invoke.
854
50.9k
      if (SeenThrowableInstInBB || 
!MBB.hasEHPadSuccessor()50.6k
||
855
50.9k
          
!WebAssembly::mayThrow(MI)214
)
856
50.8k
        continue;
857
80
      SeenThrowableInstInBB = true;
858
80
859
80
      // If the EH pad on the stack top is where this instruction should unwind
860
80
      // next, we're good.
861
80
      MachineBasicBlock *UnwindDest = nullptr;
862
150
      for (auto *Succ : MBB.successors()) {
863
150
        if (Succ->isEHPad()) {
864
80
          UnwindDest = Succ;
865
80
          break;
866
80
        }
867
150
      }
868
80
      if (EHPadStack.back() == UnwindDest)
869
77
        continue;
870
3
871
3
      // If not, record the range.
872
3
      UnwindDestToTryRanges[UnwindDest].push_back(TryRange(&MI, &MI));
873
3
    }
874
5.30k
  }
875
4.45k
876
4.45k
  assert(EHPadStack.empty());
877
4.45k
878
4.45k
  // Gather possibly throwing calls that are supposed to unwind up to the caller
879
4.45k
  // if they throw, but currently unwind to an incorrect destination. Unlike the
880
4.45k
  // loop above, there can be multiple calls within a BB that unwind to the
881
4.45k
  // caller, which we should group together in a range.
882
4.45k
  bool NeedAppendixBlock = false;
883
5.30k
  for (auto &MBB : reverse(MF)) {
884
5.30k
    MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr; // inclusive
885
50.9k
    for (auto &MI : reverse(MBB)) {
886
50.9k
      if (MI.getOpcode() == WebAssembly::TRY)
887
71
        EHPadStack.pop_back();
888
50.8k
      else if (MI.getOpcode() == WebAssembly::CATCH)
889
71
        EHPadStack.push_back(MI.getParent());
890
50.9k
891
50.9k
      // If MBB has an EH pad successor, this inst does not unwind to caller.
892
50.9k
      if (MBB.hasEHPadSuccessor())
893
529
        continue;
894
50.4k
895
50.4k
      // We wrap up the current range when we see a marker even if we haven't
896
50.4k
      // finished a BB.
897
50.4k
      if (RangeEnd && 
WebAssembly::isMarker(MI.getOpcode())6
) {
898
2
        NeedAppendixBlock = true;
899
2
        // Record the range. nullptr here means the unwind destination is the
900
2
        // caller.
901
2
        UnwindDestToTryRanges[nullptr].push_back(
902
2
            TryRange(RangeBegin, RangeEnd));
903
2
        RangeBegin = RangeEnd = nullptr; // Reset range pointers
904
2
      }
905
50.4k
906
50.4k
      // If EHPadStack is empty, that means it is correctly unwind to caller if
907
50.4k
      // it throws, so we're good. If MI does not throw, we're good too.
908
50.4k
      if (EHPadStack.empty() || 
!WebAssembly::mayThrow(MI)226
)
909
50.4k
        continue;
910
10
911
10
      // We found an instruction that unwinds to the caller but currently has an
912
10
      // incorrect unwind destination. Create a new range or increment the
913
10
      // currently existing range.
914
10
      if (!RangeEnd)
915
7
        RangeBegin = RangeEnd = &MI;
916
3
      else
917
3
        RangeBegin = &MI;
918
10
    }
919
5.30k
920
5.30k
    if (RangeEnd) {
921
5
      NeedAppendixBlock = true;
922
5
      // Record the range. nullptr here means the unwind destination is the
923
5
      // caller.
924
5
      UnwindDestToTryRanges[nullptr].push_back(TryRange(RangeBegin, RangeEnd));
925
5
      RangeBegin = RangeEnd = nullptr; // Reset range pointers
926
5
    }
927
5.30k
  }
928
4.45k
929
4.45k
  assert(EHPadStack.empty());
930
4.45k
  // We don't have any unwind destination mismatches to resolve.
931
4.45k
  if (UnwindDestToTryRanges.empty())
932
4.44k
    return false;
933
6
934
6
  // If we found instructions that should unwind to the caller but currently
935
6
  // have incorrect unwind destination, we create an appendix block at the end
936
6
  // of the function with a local.get and a rethrow instruction.
937
6
  if (NeedAppendixBlock) {
938
5
    auto *AppendixBB = getAppendixBlock(MF);
939
5
    unsigned ExnReg = MRI.createVirtualRegister(&WebAssembly::EXNREFRegClass);
940
5
    BuildMI(AppendixBB, DebugLoc(), TII.get(WebAssembly::RETHROW))
941
5
        .addReg(ExnReg);
942
5
    // These instruction ranges should branch to this appendix BB.
943
5
    for (auto Range : UnwindDestToTryRanges[nullptr])
944
7
      BrDestToTryRanges[AppendixBB].push_back(Range);
945
5
    BrDestToExnReg[AppendixBB] = ExnReg;
946
5
  }
947
6
948
6
  // We loop through unwind destination EH pads that are targeted from some
949
6
  // inner scopes. Because these EH pads are destination of more than one scope
950
6
  // now, we split them so that the handler body is after 'end_try'.
951
6
  // - Before
952
6
  // ehpad:
953
6
  //   catch
954
6
  //   local.set n / drop
955
6
  //   handler body
956
6
  // ...
957
6
  // cont:
958
6
  //   end_try
959
6
  //
960
6
  // - After
961
6
  // ehpad:
962
6
  //   catch
963
6
  //   local.set n / drop
964
6
  // brdest:               (new)
965
6
  //   end_try             (hoisted from 'cont' BB)
966
6
  //   handler body        (taken from 'ehpad')
967
6
  // ...
968
6
  // cont:
969
8
  for (auto &P : UnwindDestToTryRanges) {
970
8
    NumUnwindMismatches++;
971
8
972
8
    // This means the destination is the appendix BB, which was separately
973
8
    // handled above.
974
8
    if (!P.first)
975
5
      continue;
976
3
977
3
    MachineBasicBlock *EHPad = P.first;
978
3
979
3
    // Find 'catch' and 'local.set' or 'drop' instruction that follows the
980
3
    // 'catch'. If -wasm-disable-explicit-locals is not set, 'catch' should be
981
3
    // always followed by either 'local.set' or a 'drop', because 'br_on_exn' is
982
3
    // generated after 'catch' in LateEHPrepare and we don't support blocks
983
3
    // taking values yet.
984
3
    MachineInstr *Catch = nullptr;
985
3
    unsigned ExnReg = 0;
986
16
    for (auto &MI : *EHPad) {
987
16
      switch (MI.getOpcode()) {
988
16
      case WebAssembly::CATCH:
989
3
        Catch = &MI;
990
3
        ExnReg = Catch->getOperand(0).getReg();
991
3
        break;
992
16
      }
993
16
    }
994
3
    assert(Catch && "EH pad does not have a catch");
995
3
    assert(ExnReg != 0 && "Invalid register");
996
3
997
3
    auto SplitPos = std::next(Catch->getIterator());
998
3
999
3
    // Create a new BB that's gonna be the destination for branches from the
1000
3
    // inner mismatched scope.
1001
3
    MachineInstr *BeginTry = EHPadToTry[EHPad];
1002
3
    MachineInstr *EndTry = BeginToEnd[BeginTry];
1003
3
    MachineBasicBlock *Cont = EndTry->getParent();
1004
3
    auto *BrDest = MF.CreateMachineBasicBlock();
1005
3
    MF.insert(std::next(EHPad->getIterator()), BrDest);
1006
3
    // Hoist up the existing 'end_try'.
1007
3
    BrDest->insert(BrDest->end(), EndTry->removeFromParent());
1008
3
    // Take out the handler body from EH pad to the new branch destination BB.
1009
3
    BrDest->splice(BrDest->end(), EHPad, SplitPos, EHPad->end());
1010
3
    // Fix predecessor-successor relationship.
1011
3
    BrDest->transferSuccessors(EHPad);
1012
3
    EHPad->addSuccessor(BrDest);
1013
3
1014
3
    // All try ranges that were supposed to unwind to this EH pad now have to
1015
3
    // branch to this new branch dest BB.
1016
3
    for (auto Range : UnwindDestToTryRanges[EHPad])
1017
3
      BrDestToTryRanges[BrDest].push_back(Range);
1018
3
    BrDestToExnReg[BrDest] = ExnReg;
1019
3
1020
3
    // In case we fall through to the continuation BB after the catch block, we
1021
3
    // now have to add a branch to it.
1022
3
    // - Before
1023
3
    // try
1024
3
    //   ...
1025
3
    //   (falls through to 'cont')
1026
3
    // catch
1027
3
    //   handler body
1028
3
    // end
1029
3
    //               <-- cont
1030
3
    //
1031
3
    // - After
1032
3
    // try
1033
3
    //   ...
1034
3
    //   br %cont    (new)
1035
3
    // catch
1036
3
    // end
1037
3
    // handler body
1038
3
    //               <-- cont
1039
3
    MachineBasicBlock *EHPadLayoutPred = &*std::prev(EHPad->getIterator());
1040
3
    MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1041
3
    SmallVector<MachineOperand, 4> Cond;
1042
3
    bool Analyzable = !TII.analyzeBranch(*EHPadLayoutPred, TBB, FBB, Cond);
1043
3
    if (Analyzable && 
!TBB2
&&
!FBB0
) {
1044
0
      DebugLoc DL = EHPadLayoutPred->empty()
1045
0
                        ? DebugLoc()
1046
0
                        : EHPadLayoutPred->rbegin()->getDebugLoc();
1047
0
      BuildMI(EHPadLayoutPred, DL, TII.get(WebAssembly::BR)).addMBB(Cont);
1048
0
    }
1049
3
  }
1050
6
1051
6
  // For possibly throwing calls whose unwind destinations are currently
1052
6
  // incorrect because of CFG linearization, we wrap them with a nested
1053
6
  // try/catch/end_try, and within the new catch block, we branch to the correct
1054
6
  // handler.
1055
6
  // - Before
1056
6
  // mbb:
1057
6
  //   call @foo       <- Unwind destination mismatch!
1058
6
  // ehpad:
1059
6
  //   ...
1060
6
  //
1061
6
  // - After
1062
6
  // mbb:
1063
6
  //   try                (new)
1064
6
  //   call @foo
1065
6
  // nested-ehpad:        (new)
1066
6
  //   catch              (new)
1067
6
  //   local.set n / drop (new)
1068
6
  //   br %brdest         (new)
1069
6
  // nested-end:          (new)
1070
6
  //   end_try            (new)
1071
6
  // ehpad:
1072
6
  //   ...
1073
8
  
for (auto &P : BrDestToTryRanges)6
{
1074
8
    MachineBasicBlock *BrDest = P.first;
1075
8
    auto &TryRanges = P.second;
1076
8
    unsigned ExnReg = BrDestToExnReg[BrDest];
1077
8
1078
10
    for (auto Range : TryRanges) {
1079
10
      MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr;
1080
10
      std::tie(RangeBegin, RangeEnd) = Range;
1081
10
      auto *MBB = RangeBegin->getParent();
1082
10
1083
10
      // Include possible EH_LABELs in the range
1084
10
      if (RangeBegin->getIterator() != MBB->begin() &&
1085
10
          
std::prev(RangeBegin->getIterator())->isEHLabel()5
)
1086
2
        RangeBegin = &*std::prev(RangeBegin->getIterator());
1087
10
      if (std::next(RangeEnd->getIterator()) != MBB->end() &&
1088
10
          
std::next(RangeEnd->getIterator())->isEHLabel()7
)
1089
2
        RangeEnd = &*std::next(RangeEnd->getIterator());
1090
10
1091
10
      MachineBasicBlock *EHPad = nullptr;
1092
10
      for (auto *Succ : MBB->successors()) {
1093
8
        if (Succ->isEHPad()) {
1094
3
          EHPad = Succ;
1095
3
          break;
1096
3
        }
1097
8
      }
1098
10
1099
10
      // Create the nested try instruction.
1100
10
      MachineInstr *NestedTry =
1101
10
          BuildMI(*MBB, *RangeBegin, RangeBegin->getDebugLoc(),
1102
10
                  TII.get(WebAssembly::TRY))
1103
10
              .addImm(int64_t(WebAssembly::ExprType::Void));
1104
10
1105
10
      // Create the nested EH pad and fill instructions in.
1106
10
      MachineBasicBlock *NestedEHPad = MF.CreateMachineBasicBlock();
1107
10
      MF.insert(std::next(MBB->getIterator()), NestedEHPad);
1108
10
      NestedEHPad->setIsEHPad();
1109
10
      NestedEHPad->setIsEHScopeEntry();
1110
10
      BuildMI(NestedEHPad, RangeEnd->getDebugLoc(), TII.get(WebAssembly::CATCH),
1111
10
              ExnReg);
1112
10
      BuildMI(NestedEHPad, RangeEnd->getDebugLoc(), TII.get(WebAssembly::BR))
1113
10
          .addMBB(BrDest);
1114
10
1115
10
      // Create the nested continuation BB and end_try instruction.
1116
10
      MachineBasicBlock *NestedCont = MF.CreateMachineBasicBlock();
1117
10
      MF.insert(std::next(NestedEHPad->getIterator()), NestedCont);
1118
10
      MachineInstr *NestedEndTry =
1119
10
          BuildMI(*NestedCont, NestedCont->begin(), RangeEnd->getDebugLoc(),
1120
10
                  TII.get(WebAssembly::END_TRY));
1121
10
      // In case MBB has more instructions after the try range, move them to the
1122
10
      // new nested continuation BB.
1123
10
      NestedCont->splice(NestedCont->end(), MBB,
1124
10
                         std::next(RangeEnd->getIterator()), MBB->end());
1125
10
      registerTryScope(NestedTry, NestedEndTry, NestedEHPad);
1126
10
1127
10
      // Fix predecessor-successor relationship.
1128
10
      NestedCont->transferSuccessors(MBB);
1129
10
      if (EHPad)
1130
3
        NestedCont->removeSuccessor(EHPad);
1131
10
      MBB->addSuccessor(NestedEHPad);
1132
10
      MBB->addSuccessor(NestedCont);
1133
10
      NestedEHPad->addSuccessor(BrDest);
1134
10
    }
1135
8
  }
1136
6
1137
6
  // Renumber BBs and recalculate ScopeTop info because new BBs might have been
1138
6
  // created and inserted above.
1139
6
  MF.RenumberBlocks();
1140
6
  ScopeTops.clear();
1141
6
  ScopeTops.resize(MF.getNumBlockIDs());
1142
80
  for (auto &MBB : reverse(MF)) {
1143
272
    for (auto &MI : reverse(MBB)) {
1144
272
      if (ScopeTops[MBB.getNumber()])
1145
18
        break;
1146
254
      switch (MI.getOpcode()) {
1147
254
      case WebAssembly::END_BLOCK:
1148
29
      case WebAssembly::END_LOOP:
1149
29
      case WebAssembly::END_TRY:
1150
29
        ScopeTops[MBB.getNumber()] = EndToBegin[&MI]->getParent();
1151
29
        break;
1152
29
      case WebAssembly::CATCH:
1153
23
        ScopeTops[MBB.getNumber()] = EHPadToTry[&MBB]->getParent();
1154
23
        break;
1155
254
      }
1156
254
    }
1157
80
  }
1158
6
1159
6
  // Recompute the dominator tree.
1160
6
  getAnalysis<MachineDominatorTree>().runOnMachineFunction(MF);
1161
6
1162
6
  // Place block markers for newly added branches.
1163
6
  SmallVector <MachineBasicBlock *, 8> BrDests;
1164
6
  for (auto &P : BrDestToTryRanges)
1165
8
    BrDests.push_back(P.first);
1166
6
  llvm::sort(BrDests,
1167
6
             [&](const MachineBasicBlock *A, const MachineBasicBlock *B) {
1168
2
               auto ANum = A->getNumber();
1169
2
               auto BNum = B->getNumber();
1170
2
               return ANum < BNum;
1171
2
             });
1172
6
  for (auto *Dest : BrDests)
1173
8
    placeBlockMarker(*Dest);
1174
6
1175
6
  return true;
1176
6
}
1177
1178
static unsigned
1179
getDepth(const SmallVectorImpl<const MachineBasicBlock *> &Stack,
1180
546
         const MachineBasicBlock *MBB) {
1181
546
  unsigned Depth = 0;
1182
879
  for (auto X : reverse(Stack)) {
1183
879
    if (X == MBB)
1184
546
      break;
1185
333
    ++Depth;
1186
333
  }
1187
546
  assert(Depth < Stack.size() && "Branch destination should be in scope");
1188
546
  return Depth;
1189
546
}
1190
1191
/// In normal assembly languages, when the end of a function is unreachable,
1192
/// because the function ends in an infinite loop or a noreturn call or similar,
1193
/// it isn't necessary to worry about the function return type at the end of
1194
/// the function, because it's never reached. However, in WebAssembly, blocks
1195
/// that end at the function end need to have a return type signature that
1196
/// matches the function signature, even though it's unreachable. This function
1197
/// checks for such cases and fixes up the signatures.
1198
4.45k
void WebAssemblyCFGStackify::fixEndsAtEndOfFunction(MachineFunction &MF) {
1199
4.45k
  const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
1200
4.45k
  assert(MFI.getResults().size() <= 1);
1201
4.45k
1202
4.45k
  if (MFI.getResults().empty())
1203
1.58k
    return;
1204
2.86k
1205
2.86k
  WebAssembly::ExprType RetType;
1206
2.86k
  switch (MFI.getResults().front().SimpleTy) {
1207
2.86k
  case MVT::i32:
1208
1.12k
    RetType = WebAssembly::ExprType::I32;
1209
1.12k
    break;
1210
2.86k
  case MVT::i64:
1211
327
    RetType = WebAssembly::ExprType::I64;
1212
327
    break;
1213
2.86k
  case MVT::f32:
1214
78
    RetType = WebAssembly::ExprType::F32;
1215
78
    break;
1216
2.86k
  case MVT::f64:
1217
67
    RetType = WebAssembly::ExprType::F64;
1218
67
    break;
1219
2.86k
  case MVT::v16i8:
1220
1.27k
  case MVT::v8i16:
1221
1.27k
  case MVT::v4i32:
1222
1.27k
  case MVT::v2i64:
1223
1.27k
  case MVT::v4f32:
1224
1.27k
  case MVT::v2f64:
1225
1.27k
    RetType = WebAssembly::ExprType::V128;
1226
1.27k
    break;
1227
1.27k
  case MVT::exnref:
1228
0
    RetType = WebAssembly::ExprType::Exnref;
1229
0
    break;
1230
1.27k
  default:
1231
0
    llvm_unreachable("unexpected return type");
1232
2.86k
  }
1233
2.86k
1234
2.87k
  
for (MachineBasicBlock &MBB : reverse(MF))2.86k
{
1235
2.87k
    for (MachineInstr &MI : reverse(MBB)) {
1236
2.87k
      if (MI.isPosition() || MI.isDebugInstr())
1237
0
        continue;
1238
2.87k
      if (MI.getOpcode() == WebAssembly::END_BLOCK) {
1239
0
        EndToBegin[&MI]->getOperand(0).setImm(int32_t(RetType));
1240
0
        continue;
1241
0
      }
1242
2.87k
      if (MI.getOpcode() == WebAssembly::END_LOOP) {
1243
5
        EndToBegin[&MI]->getOperand(0).setImm(int32_t(RetType));
1244
5
        continue;
1245
5
      }
1246
2.86k
      // Something other than an `end`. We're done.
1247
2.86k
      return;
1248
2.86k
    }
1249
2.87k
  }
1250
2.86k
}
1251
1252
// WebAssembly functions end with an end instruction, as if the function body
1253
// were a block.
1254
static void appendEndToFunction(MachineFunction &MF,
1255
4.45k
                                const WebAssemblyInstrInfo &TII) {
1256
4.45k
  BuildMI(MF.back(), MF.back().end(),
1257
4.45k
          MF.back().findPrevDebugLoc(MF.back().end()),
1258
4.45k
          TII.get(WebAssembly::END_FUNCTION));
1259
4.45k
}
1260
1261
/// Insert LOOP/TRY/BLOCK markers at appropriate places.
1262
4.45k
void WebAssemblyCFGStackify::placeMarkers(MachineFunction &MF) {
1263
4.45k
  // We allocate one more than the number of blocks in the function to
1264
4.45k
  // accommodate for the possible fake block we may insert at the end.
1265
4.45k
  ScopeTops.resize(MF.getNumBlockIDs() + 1);
1266
4.45k
  // Place the LOOP for MBB if MBB is the header of a loop.
1267
4.45k
  for (auto &MBB : MF)
1268
5.30k
    placeLoopMarker(MBB);
1269
4.45k
1270
4.45k
  const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo();
1271
5.30k
  for (auto &MBB : MF) {
1272
5.30k
    if (MBB.isEHPad()) {
1273
71
      // Place the TRY for MBB if MBB is the EH pad of an exception.
1274
71
      if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm &&
1275
71
          MF.getFunction().hasPersonalityFn())
1276
71
        placeTryMarker(MBB);
1277
5.23k
    } else {
1278
5.23k
      // Place the BLOCK for MBB if MBB is branched to from above.
1279
5.23k
      placeBlockMarker(MBB);
1280
5.23k
    }
1281
5.30k
  }
1282
4.45k
  // Fix mismatches in unwind destinations induced by linearizing the code.
1283
4.45k
  fixUnwindMismatches(MF);
1284
4.45k
}
1285
1286
4.45k
void WebAssemblyCFGStackify::rewriteDepthImmediates(MachineFunction &MF) {
1287
4.45k
  // Now rewrite references to basic blocks to be depth immediates.
1288
4.45k
  SmallVector<const MachineBasicBlock *, 8> Stack;
1289
5.32k
  for (auto &MBB : reverse(MF)) {
1290
56.2k
    for (auto I = MBB.rbegin(), E = MBB.rend(); I != E; 
++I50.8k
) {
1291
50.8k
      MachineInstr &MI = *I;
1292
50.8k
      switch (MI.getOpcode()) {
1293
50.8k
      case WebAssembly::BLOCK:
1294
403
      case WebAssembly::TRY:
1295
403
        assert(ScopeTops[Stack.back()->getNumber()]->getNumber() <=
1296
403
                   MBB.getNumber() &&
1297
403
               "Block/try marker should be balanced");
1298
403
        Stack.pop_back();
1299
403
        break;
1300
403
1301
403
      case WebAssembly::LOOP:
1302
90
        assert(Stack.back() == &MBB && "Loop top should be balanced");
1303
90
        Stack.pop_back();
1304
90
        break;
1305
403
1306
403
      case WebAssembly::END_BLOCK:
1307
403
      case WebAssembly::END_TRY:
1308
403
        Stack.push_back(&MBB);
1309
403
        break;
1310
403
1311
403
      case WebAssembly::END_LOOP:
1312
90
        Stack.push_back(EndToBegin[&MI]->getParent());
1313
90
        break;
1314
403
1315
49.8k
      default:
1316
49.8k
        if (MI.isTerminator()) {
1317
5.06k
          // Rewrite MBB operands to be depth immediates.
1318
5.06k
          SmallVector<MachineOperand, 4> Ops(MI.operands());
1319
19.2k
          while (MI.getNumOperands() > 0)
1320
14.1k
            MI.RemoveOperand(MI.getNumOperands() - 1);
1321
14.1k
          for (auto MO : Ops) {
1322
14.1k
            if (MO.isMBB())
1323
546
              MO = MachineOperand::CreateImm(getDepth(Stack, MO.getMBB()));
1324
14.1k
            MI.addOperand(MF, MO);
1325
14.1k
          }
1326
5.06k
        }
1327
49.8k
        break;
1328
50.8k
      }
1329
50.8k
    }
1330
5.32k
  }
1331
4.45k
  assert(Stack.empty() && "Control flow should be balanced");
1332
4.45k
}
1333
1334
9.33k
void WebAssemblyCFGStackify::releaseMemory() {
1335
9.33k
  ScopeTops.clear();
1336
9.33k
  BeginToEnd.clear();
1337
9.33k
  EndToBegin.clear();
1338
9.33k
  TryToEHPad.clear();
1339
9.33k
  EHPadToTry.clear();
1340
9.33k
  AppendixBB = nullptr;
1341
9.33k
}
1342
1343
4.45k
bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) {
1344
4.45k
  LLVM_DEBUG(dbgs() << "********** CFG Stackifying **********\n"
1345
4.45k
                       "********** Function: "
1346
4.45k
                    << MF.getName() << '\n');
1347
4.45k
  const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo();
1348
4.45k
1349
4.45k
  releaseMemory();
1350
4.45k
1351
4.45k
  // Liveness is not tracked for VALUE_STACK physreg.
1352
4.45k
  MF.getRegInfo().invalidateLiveness();
1353
4.45k
1354
4.45k
  // Place the BLOCK/LOOP/TRY markers to indicate the beginnings of scopes.
1355
4.45k
  placeMarkers(MF);
1356
4.45k
1357
4.45k
  // Remove unnecessary instructions possibly introduced by try/end_trys.
1358
4.45k
  if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm &&
1359
4.45k
      
MF.getFunction().hasPersonalityFn()53
)
1360
42
    removeUnnecessaryInstrs(MF);
1361
4.45k
1362
4.45k
  // Convert MBB operands in terminators to relative depth immediates.
1363
4.45k
  rewriteDepthImmediates(MF);
1364
4.45k
1365
4.45k
  // Fix up block/loop/try signatures at the end of the function to conform to
1366
4.45k
  // WebAssembly's rules.
1367
4.45k
  fixEndsAtEndOfFunction(MF);
1368
4.45k
1369
4.45k
  // Add an end instruction at the end of the function body.
1370
4.45k
  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
1371
4.45k
  if (!MF.getSubtarget<WebAssemblySubtarget>()
1372
4.45k
           .getTargetTriple()
1373
4.45k
           .isOSBinFormatELF())
1374
4.45k
    appendEndToFunction(MF, TII);
1375
4.45k
1376
4.45k
  MF.getInfo<WebAssemblyFunctionInfo>()->setCFGStackified();
1377
4.45k
  return true;
1378
4.45k
}