Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/WinEHPrepare.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- WinEHPrepare - Prepare exception handling for code generation ---===//
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
// This pass lowers LLVM IR exception handling into something closer to what the
10
// backend wants for functions using a personality function from a runtime
11
// provided by MSVC. Functions with other personality functions are left alone
12
// and may be prepared by other passes. In particular, all supported MSVC
13
// personality functions require cleanup code to be outlined, and the C++
14
// personality requires catch handler code to be outlined.
15
//
16
//===----------------------------------------------------------------------===//
17
18
#include "llvm/ADT/DenseMap.h"
19
#include "llvm/ADT/MapVector.h"
20
#include "llvm/ADT/STLExtras.h"
21
#include "llvm/Analysis/CFG.h"
22
#include "llvm/Analysis/EHPersonalities.h"
23
#include "llvm/Transforms/Utils/Local.h"
24
#include "llvm/CodeGen/MachineBasicBlock.h"
25
#include "llvm/CodeGen/Passes.h"
26
#include "llvm/CodeGen/WinEHFuncInfo.h"
27
#include "llvm/IR/Verifier.h"
28
#include "llvm/MC/MCSymbol.h"
29
#include "llvm/Pass.h"
30
#include "llvm/Support/Debug.h"
31
#include "llvm/Support/raw_ostream.h"
32
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
33
#include "llvm/Transforms/Utils/Cloning.h"
34
#include "llvm/Transforms/Utils/SSAUpdater.h"
35
36
using namespace llvm;
37
38
#define DEBUG_TYPE "winehprepare"
39
40
static cl::opt<bool> DisableDemotion(
41
    "disable-demotion", cl::Hidden,
42
    cl::desc(
43
        "Clone multicolor basic blocks but do not demote cross scopes"),
44
    cl::init(false));
45
46
static cl::opt<bool> DisableCleanups(
47
    "disable-cleanups", cl::Hidden,
48
    cl::desc("Do not remove implausible terminators or other similar cleanups"),
49
    cl::init(false));
50
51
static cl::opt<bool> DemoteCatchSwitchPHIOnlyOpt(
52
    "demote-catchswitch-only", cl::Hidden,
53
    cl::desc("Demote catchswitch BBs only (for wasm EH)"), cl::init(false));
54
55
namespace {
56
57
class WinEHPrepare : public FunctionPass {
58
public:
59
  static char ID; // Pass identification, replacement for typeid.
60
  WinEHPrepare(bool DemoteCatchSwitchPHIOnly = false)
61
836
      : FunctionPass(ID), DemoteCatchSwitchPHIOnly(DemoteCatchSwitchPHIOnly) {}
62
63
  bool runOnFunction(Function &Fn) override;
64
65
  bool doFinalization(Module &M) override;
66
67
  void getAnalysisUsage(AnalysisUsage &AU) const override;
68
69
2.99k
  StringRef getPassName() const override {
70
2.99k
    return "Windows exception handling preparation";
71
2.99k
  }
72
73
private:
74
  void insertPHIStores(PHINode *OriginalPHI, AllocaInst *SpillSlot);
75
  void
76
  insertPHIStore(BasicBlock *PredBlock, Value *PredVal, AllocaInst *SpillSlot,
77
                 SmallVectorImpl<std::pair<BasicBlock *, Value *>> &Worklist);
78
  AllocaInst *insertPHILoads(PHINode *PN, Function &F);
79
  void replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot,
80
                          DenseMap<BasicBlock *, Value *> &Loads, Function &F);
81
  bool prepareExplicitEH(Function &F);
82
  void colorFunclets(Function &F);
83
84
  void demotePHIsOnFunclets(Function &F, bool DemoteCatchSwitchPHIOnly);
85
  void cloneCommonBlocks(Function &F);
86
  void removeImplausibleInstructions(Function &F);
87
  void cleanupPreparedFunclets(Function &F);
88
  void verifyPreparedFunclets(Function &F);
89
90
  bool DemoteCatchSwitchPHIOnly;
91
92
  // All fields are reset by runOnFunction.
93
  EHPersonality Personality = EHPersonality::Unknown;
94
95
  const DataLayout *DL = nullptr;
96
  DenseMap<BasicBlock *, ColorVector> BlockColors;
97
  MapVector<BasicBlock *, std::vector<BasicBlock *>> FuncletBlocks;
98
};
99
100
} // end anonymous namespace
101
102
char WinEHPrepare::ID = 0;
103
INITIALIZE_PASS(WinEHPrepare, DEBUG_TYPE, "Prepare Windows exceptions",
104
                false, false)
105
106
831
FunctionPass *llvm::createWinEHPass(bool DemoteCatchSwitchPHIOnly) {
107
831
  return new WinEHPrepare(DemoteCatchSwitchPHIOnly);
108
831
}
109
110
2.99k
bool WinEHPrepare::runOnFunction(Function &Fn) {
111
2.99k
  if (!Fn.hasPersonalityFn())
112
2.78k
    return false;
113
211
114
211
  // Classify the personality to see what kind of preparation we need.
115
211
  Personality = classifyEHPersonality(Fn.getPersonalityFn());
116
211
117
211
  // Do nothing if this is not a scope-based personality.
118
211
  if (!isScopedEHPersonality(Personality))
119
36
    return false;
120
175
121
175
  DL = &Fn.getParent()->getDataLayout();
122
175
  return prepareExplicitEH(Fn);
123
175
}
124
125
806
bool WinEHPrepare::doFinalization(Module &M) { return false; }
126
127
815
void WinEHPrepare::getAnalysisUsage(AnalysisUsage &AU) const {}
128
129
static int addUnwindMapEntry(WinEHFuncInfo &FuncInfo, int ToState,
130
223
                             const BasicBlock *BB) {
131
223
  CxxUnwindMapEntry UME;
132
223
  UME.ToState = ToState;
133
223
  UME.Cleanup = BB;
134
223
  FuncInfo.CxxUnwindMap.push_back(UME);
135
223
  return FuncInfo.getLastStateNumber();
136
223
}
137
138
static void addTryBlockMapEntry(WinEHFuncInfo &FuncInfo, int TryLow,
139
                                int TryHigh, int CatchHigh,
140
93
                                ArrayRef<const CatchPadInst *> Handlers) {
141
93
  WinEHTryBlockMapEntry TBME;
142
93
  TBME.TryLow = TryLow;
143
93
  TBME.TryHigh = TryHigh;
144
93
  TBME.CatchHigh = CatchHigh;
145
93
  assert(TBME.TryLow <= TBME.TryHigh);
146
101
  for (const CatchPadInst *CPI : Handlers) {
147
101
    WinEHHandlerType HT;
148
101
    Constant *TypeInfo = cast<Constant>(CPI->getArgOperand(0));
149
101
    if (TypeInfo->isNullValue())
150
68
      HT.TypeDescriptor = nullptr;
151
33
    else
152
33
      HT.TypeDescriptor = cast<GlobalVariable>(TypeInfo->stripPointerCasts());
153
101
    HT.Adjectives = cast<ConstantInt>(CPI->getArgOperand(1))->getZExtValue();
154
101
    HT.Handler = CPI->getParent();
155
101
    if (auto *AI =
156
13
            dyn_cast<AllocaInst>(CPI->getArgOperand(2)->stripPointerCasts()))
157
13
      HT.CatchObj.Alloca = AI;
158
88
    else
159
88
      HT.CatchObj.Alloca = nullptr;
160
101
    TBME.HandlerArray.push_back(HT);
161
101
  }
162
93
  FuncInfo.TryBlockMap.push_back(TBME);
163
93
}
164
165
71
static BasicBlock *getCleanupRetUnwindDest(const CleanupPadInst *CleanupPad) {
166
71
  for (const User *U : CleanupPad->users())
167
80
    if (const auto *CRI = dyn_cast<CleanupReturnInst>(U))
168
58
      return CRI->getUnwindDest();
169
71
  
return nullptr13
;
170
71
}
171
172
static void calculateStateNumbersForInvokes(const Function *Fn,
173
151
                                            WinEHFuncInfo &FuncInfo) {
174
151
  auto *F = const_cast<Function *>(Fn);
175
151
  DenseMap<BasicBlock *, ColorVector> BlockColors = colorEHFunclets(*F);
176
836
  for (BasicBlock &BB : *F) {
177
836
    auto *II = dyn_cast<InvokeInst>(BB.getTerminator());
178
836
    if (!II)
179
605
      continue;
180
231
181
231
    auto &BBColors = BlockColors[&BB];
182
231
    assert(BBColors.size() == 1 && "multi-color BB not removed by preparation");
183
231
    BasicBlock *FuncletEntryBB = BBColors.front();
184
231
185
231
    BasicBlock *FuncletUnwindDest;
186
231
    auto *FuncletPad =
187
231
        dyn_cast<FuncletPadInst>(FuncletEntryBB->getFirstNonPHI());
188
231
    assert(FuncletPad || FuncletEntryBB == &Fn->getEntryBlock());
189
231
    if (!FuncletPad)
190
187
      FuncletUnwindDest = nullptr;
191
44
    else if (auto *CatchPad = dyn_cast<CatchPadInst>(FuncletPad))
192
30
      FuncletUnwindDest = CatchPad->getCatchSwitch()->getUnwindDest();
193
14
    else if (auto *CleanupPad = dyn_cast<CleanupPadInst>(FuncletPad))
194
14
      FuncletUnwindDest = getCleanupRetUnwindDest(CleanupPad);
195
14
    else
196
14
      
llvm_unreachable0
("unexpected funclet pad!");
197
231
198
231
    BasicBlock *InvokeUnwindDest = II->getUnwindDest();
199
231
    int BaseState = -1;
200
231
    if (FuncletUnwindDest == InvokeUnwindDest) {
201
22
      auto BaseStateI = FuncInfo.FuncletBaseStateMap.find(FuncletPad);
202
22
      if (BaseStateI != FuncInfo.FuncletBaseStateMap.end())
203
14
        BaseState = BaseStateI->second;
204
22
    }
205
231
206
231
    if (BaseState != -1) {
207
14
      FuncInfo.InvokeStateMap[II] = BaseState;
208
217
    } else {
209
217
      Instruction *PadInst = InvokeUnwindDest->getFirstNonPHI();
210
217
      assert(FuncInfo.EHPadStateMap.count(PadInst) && "EH Pad has no state!");
211
217
      FuncInfo.InvokeStateMap[II] = FuncInfo.EHPadStateMap[PadInst];
212
217
    }
213
231
  }
214
151
}
215
216
// Given BB which ends in an unwind edge, return the EHPad that this BB belongs
217
// to. If the unwind edge came from an invoke, return null.
218
static const BasicBlock *getEHPadFromPredecessor(const BasicBlock *BB,
219
260
                                                 Value *ParentPad) {
220
260
  const Instruction *TI = BB->getTerminator();
221
260
  if (isa<InvokeInst>(TI))
222
212
    return nullptr;
223
48
  if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) {
224
31
    if (CatchSwitch->getParentPad() != ParentPad)
225
0
      return nullptr;
226
31
    return BB;
227
31
  }
228
17
  assert(!TI->isEHPad() && "unexpected EHPad!");
229
17
  auto *CleanupPad = cast<CleanupReturnInst>(TI)->getCleanupPad();
230
17
  if (CleanupPad->getParentPad() != ParentPad)
231
3
    return nullptr;
232
14
  return CleanupPad->getParent();
233
14
}
234
235
static void calculateCXXStateNumbers(WinEHFuncInfo &FuncInfo,
236
                                     const Instruction *FirstNonPHI,
237
131
                                     int ParentState) {
238
131
  const BasicBlock *BB = FirstNonPHI->getParent();
239
131
  assert(BB->isEHPad() && "not a funclet!");
240
131
241
131
  if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(FirstNonPHI)) {
242
93
    assert(FuncInfo.EHPadStateMap.count(CatchSwitch) == 0 &&
243
93
           "shouldn't revist catch funclets!");
244
93
245
93
    SmallVector<const CatchPadInst *, 2> Handlers;
246
101
    for (const BasicBlock *CatchPadBB : CatchSwitch->handlers()) {
247
101
      auto *CatchPad = cast<CatchPadInst>(CatchPadBB->getFirstNonPHI());
248
101
      Handlers.push_back(CatchPad);
249
101
    }
250
93
    int TryLow = addUnwindMapEntry(FuncInfo, ParentState, nullptr);
251
93
    FuncInfo.EHPadStateMap[CatchSwitch] = TryLow;
252
93
    for (const BasicBlock *PredBlock : predecessors(BB))
253
110
      if ((PredBlock = getEHPadFromPredecessor(PredBlock,
254
110
                                               CatchSwitch->getParentPad())))
255
16
        calculateCXXStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
256
16
                                 TryLow);
257
93
    int CatchLow = addUnwindMapEntry(FuncInfo, ParentState, nullptr);
258
93
259
93
    // catchpads are separate funclets in C++ EH due to the way rethrow works.
260
93
    int TryHigh = CatchLow - 1;
261
101
    for (const auto *CatchPad : Handlers) {
262
101
      FuncInfo.FuncletBaseStateMap[CatchPad] = CatchLow;
263
153
      for (const User *U : CatchPad->users()) {
264
153
        const auto *UserI = cast<Instruction>(U);
265
153
        if (auto *InnerCatchSwitch = dyn_cast<CatchSwitchInst>(UserI)) {
266
7
          BasicBlock *UnwindDest = InnerCatchSwitch->getUnwindDest();
267
7
          if (!UnwindDest || 
UnwindDest == CatchSwitch->getUnwindDest()1
)
268
6
            calculateCXXStateNumbers(FuncInfo, UserI, CatchLow);
269
7
        }
270
153
        if (auto *InnerCleanupPad = dyn_cast<CleanupPadInst>(UserI)) {
271
5
          BasicBlock *UnwindDest = getCleanupRetUnwindDest(InnerCleanupPad);
272
5
          // If a nested cleanup pad reports a null unwind destination and the
273
5
          // enclosing catch pad doesn't it must be post-dominated by an
274
5
          // unreachable instruction.
275
5
          if (!UnwindDest || 
UnwindDest == CatchSwitch->getUnwindDest()3
)
276
5
            calculateCXXStateNumbers(FuncInfo, UserI, CatchLow);
277
5
        }
278
153
      }
279
101
    }
280
93
    int CatchHigh = FuncInfo.getLastStateNumber();
281
93
    addTryBlockMapEntry(FuncInfo, TryLow, TryHigh, CatchHigh, Handlers);
282
93
    LLVM_DEBUG(dbgs() << "TryLow[" << BB->getName() << "]: " << TryLow << '\n');
283
93
    LLVM_DEBUG(dbgs() << "TryHigh[" << BB->getName() << "]: " << TryHigh
284
93
                      << '\n');
285
93
    LLVM_DEBUG(dbgs() << "CatchHigh[" << BB->getName() << "]: " << CatchHigh
286
93
                      << '\n');
287
93
  } else {
288
38
    auto *CleanupPad = cast<CleanupPadInst>(FirstNonPHI);
289
38
290
38
    // It's possible for a cleanup to be visited twice: it might have multiple
291
38
    // cleanupret instructions.
292
38
    if (FuncInfo.EHPadStateMap.count(CleanupPad))
293
1
      return;
294
37
295
37
    int CleanupState = addUnwindMapEntry(FuncInfo, ParentState, BB);
296
37
    FuncInfo.EHPadStateMap[CleanupPad] = CleanupState;
297
37
    LLVM_DEBUG(dbgs() << "Assigning state #" << CleanupState << " to BB "
298
37
                      << BB->getName() << '\n');
299
59
    for (const BasicBlock *PredBlock : predecessors(BB)) {
300
59
      if ((PredBlock = getEHPadFromPredecessor(PredBlock,
301
59
                                               CleanupPad->getParentPad()))) {
302
11
        calculateCXXStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
303
11
                                 CleanupState);
304
11
      }
305
59
    }
306
64
    for (const User *U : CleanupPad->users()) {
307
64
      const auto *UserI = cast<Instruction>(U);
308
64
      if (UserI->isEHPad())
309
0
        report_fatal_error("Cleanup funclets for the MSVC++ personality cannot "
310
0
                           "contain exceptional actions");
311
64
    }
312
37
  }
313
131
}
314
315
static int addSEHExcept(WinEHFuncInfo &FuncInfo, int ParentState,
316
53
                        const Function *Filter, const BasicBlock *Handler) {
317
53
  SEHUnwindMapEntry Entry;
318
53
  Entry.ToState = ParentState;
319
53
  Entry.IsFinally = false;
320
53
  Entry.Filter = Filter;
321
53
  Entry.Handler = Handler;
322
53
  FuncInfo.SEHUnwindMap.push_back(Entry);
323
53
  return FuncInfo.SEHUnwindMap.size() - 1;
324
53
}
325
326
static int addSEHFinally(WinEHFuncInfo &FuncInfo, int ParentState,
327
20
                         const BasicBlock *Handler) {
328
20
  SEHUnwindMapEntry Entry;
329
20
  Entry.ToState = ParentState;
330
20
  Entry.IsFinally = true;
331
20
  Entry.Filter = nullptr;
332
20
  Entry.Handler = Handler;
333
20
  FuncInfo.SEHUnwindMap.push_back(Entry);
334
20
  return FuncInfo.SEHUnwindMap.size() - 1;
335
20
}
336
337
static void calculateSEHStateNumbers(WinEHFuncInfo &FuncInfo,
338
                                     const Instruction *FirstNonPHI,
339
74
                                     int ParentState) {
340
74
  const BasicBlock *BB = FirstNonPHI->getParent();
341
74
  assert(BB->isEHPad() && "no a funclet!");
342
74
343
74
  if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(FirstNonPHI)) {
344
53
    assert(FuncInfo.EHPadStateMap.count(CatchSwitch) == 0 &&
345
53
           "shouldn't revist catch funclets!");
346
53
347
53
    // Extract the filter function and the __except basic block and create a
348
53
    // state for them.
349
53
    assert(CatchSwitch->getNumHandlers() == 1 &&
350
53
           "SEH doesn't have multiple handlers per __try");
351
53
    const auto *CatchPad =
352
53
        cast<CatchPadInst>((*CatchSwitch->handler_begin())->getFirstNonPHI());
353
53
    const BasicBlock *CatchPadBB = CatchPad->getParent();
354
53
    const Constant *FilterOrNull =
355
53
        cast<Constant>(CatchPad->getArgOperand(0)->stripPointerCasts());
356
53
    const Function *Filter = dyn_cast<Function>(FilterOrNull);
357
53
    assert((Filter || FilterOrNull->isNullValue()) &&
358
53
           "unexpected filter value");
359
53
    int TryState = addSEHExcept(FuncInfo, ParentState, Filter, CatchPadBB);
360
53
361
53
    // Everything in the __try block uses TryState as its parent state.
362
53
    FuncInfo.EHPadStateMap[CatchSwitch] = TryState;
363
53
    LLVM_DEBUG(dbgs() << "Assigning state #" << TryState << " to BB "
364
53
                      << CatchPadBB->getName() << '\n');
365
53
    for (const BasicBlock *PredBlock : predecessors(BB))
366
67
      if ((PredBlock = getEHPadFromPredecessor(PredBlock,
367
67
                                               CatchSwitch->getParentPad())))
368
16
        calculateSEHStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
369
16
                                 TryState);
370
53
371
53
    // Everything in the __except block unwinds to ParentState, just like code
372
53
    // outside the __try.
373
71
    for (const User *U : CatchPad->users()) {
374
71
      const auto *UserI = cast<Instruction>(U);
375
71
      if (auto *InnerCatchSwitch = dyn_cast<CatchSwitchInst>(UserI)) {
376
0
        BasicBlock *UnwindDest = InnerCatchSwitch->getUnwindDest();
377
0
        if (!UnwindDest || UnwindDest == CatchSwitch->getUnwindDest())
378
0
          calculateSEHStateNumbers(FuncInfo, UserI, ParentState);
379
0
      }
380
71
      if (auto *InnerCleanupPad = dyn_cast<CleanupPadInst>(UserI)) {
381
1
        BasicBlock *UnwindDest = getCleanupRetUnwindDest(InnerCleanupPad);
382
1
        // If a nested cleanup pad reports a null unwind destination and the
383
1
        // enclosing catch pad doesn't it must be post-dominated by an
384
1
        // unreachable instruction.
385
1
        if (!UnwindDest || 
UnwindDest == CatchSwitch->getUnwindDest()0
)
386
1
          calculateSEHStateNumbers(FuncInfo, UserI, ParentState);
387
1
      }
388
71
    }
389
53
  } else {
390
21
    auto *CleanupPad = cast<CleanupPadInst>(FirstNonPHI);
391
21
392
21
    // It's possible for a cleanup to be visited twice: it might have multiple
393
21
    // cleanupret instructions.
394
21
    if (FuncInfo.EHPadStateMap.count(CleanupPad))
395
1
      return;
396
20
397
20
    int CleanupState = addSEHFinally(FuncInfo, ParentState, BB);
398
20
    FuncInfo.EHPadStateMap[CleanupPad] = CleanupState;
399
20
    LLVM_DEBUG(dbgs() << "Assigning state #" << CleanupState << " to BB "
400
20
                      << BB->getName() << '\n');
401
20
    for (const BasicBlock *PredBlock : predecessors(BB))
402
24
      if ((PredBlock =
403
24
               getEHPadFromPredecessor(PredBlock, CleanupPad->getParentPad())))
404
2
        calculateSEHStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
405
2
                                 CleanupState);
406
37
    for (const User *U : CleanupPad->users()) {
407
37
      const auto *UserI = cast<Instruction>(U);
408
37
      if (UserI->isEHPad())
409
0
        report_fatal_error("Cleanup funclets for the SEH personality cannot "
410
0
                           "contain exceptional actions");
411
37
    }
412
20
  }
413
74
}
414
415
357
static bool isTopLevelPadForMSVC(const Instruction *EHPad) {
416
357
  if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(EHPad))
417
146
    return isa<ConstantTokenNone>(CatchSwitch->getParentPad()) &&
418
146
           
CatchSwitch->unwindsToCaller()139
;
419
211
  if (auto *CleanupPad = dyn_cast<CleanupPadInst>(EHPad))
420
57
    return isa<ConstantTokenNone>(CleanupPad->getParentPad()) &&
421
57
           
getCleanupRetUnwindDest(CleanupPad) == nullptr51
;
422
154
  if (isa<CatchPadInst>(EHPad))
423
154
    return false;
424
0
  llvm_unreachable("unexpected EHPad!");
425
0
}
426
427
void llvm::calculateSEHStateNumbers(const Function *Fn,
428
51
                                    WinEHFuncInfo &FuncInfo) {
429
51
  // Don't compute state numbers twice.
430
51
  if (!FuncInfo.SEHUnwindMap.empty())
431
0
    return;
432
51
433
266
  
for (const BasicBlock &BB : *Fn)51
{
434
266
    if (!BB.isEHPad())
435
140
      continue;
436
126
    const Instruction *FirstNonPHI = BB.getFirstNonPHI();
437
126
    if (!isTopLevelPadForMSVC(FirstNonPHI))
438
71
      continue;
439
55
    ::calculateSEHStateNumbers(FuncInfo, FirstNonPHI, -1);
440
55
  }
441
51
442
51
  calculateStateNumbersForInvokes(Fn, FuncInfo);
443
51
}
444
445
void llvm::calculateWinCXXEHStateNumbers(const Function *Fn,
446
93
                                         WinEHFuncInfo &FuncInfo) {
447
93
  // Return if it's already been done.
448
93
  if (!FuncInfo.EHPadStateMap.empty())
449
0
    return;
450
93
451
511
  
for (const BasicBlock &BB : *Fn)93
{
452
511
    if (!BB.isEHPad())
453
280
      continue;
454
231
    const Instruction *FirstNonPHI = BB.getFirstNonPHI();
455
231
    if (!isTopLevelPadForMSVC(FirstNonPHI))
456
138
      continue;
457
93
    calculateCXXStateNumbers(FuncInfo, FirstNonPHI, -1);
458
93
  }
459
93
460
93
  calculateStateNumbersForInvokes(Fn, FuncInfo);
461
93
}
462
463
static int addClrEHHandler(WinEHFuncInfo &FuncInfo, int HandlerParentState,
464
                           int TryParentState, ClrHandlerType HandlerType,
465
19
                           uint32_t TypeToken, const BasicBlock *Handler) {
466
19
  ClrEHUnwindMapEntry Entry;
467
19
  Entry.HandlerParentState = HandlerParentState;
468
19
  Entry.TryParentState = TryParentState;
469
19
  Entry.Handler = Handler;
470
19
  Entry.HandlerType = HandlerType;
471
19
  Entry.TypeToken = TypeToken;
472
19
  FuncInfo.ClrEHUnwindMap.push_back(Entry);
473
19
  return FuncInfo.ClrEHUnwindMap.size() - 1;
474
19
}
475
476
void llvm::calculateClrEHStateNumbers(const Function *Fn,
477
7
                                      WinEHFuncInfo &FuncInfo) {
478
7
  // Return if it's already been done.
479
7
  if (!FuncInfo.EHPadStateMap.empty())
480
0
    return;
481
7
482
7
  // This numbering assigns one state number to each catchpad and cleanuppad.
483
7
  // It also computes two tree-like relations over states:
484
7
  // 1) Each state has a "HandlerParentState", which is the state of the next
485
7
  //    outer handler enclosing this state's handler (same as nearest ancestor
486
7
  //    per the ParentPad linkage on EH pads, but skipping over catchswitches).
487
7
  // 2) Each state has a "TryParentState", which:
488
7
  //    a) for a catchpad that's not the last handler on its catchswitch, is
489
7
  //       the state of the next catchpad on that catchswitch
490
7
  //    b) for all other pads, is the state of the pad whose try region is the
491
7
  //       next outer try region enclosing this state's try region.  The "try
492
7
  //       regions are not present as such in the IR, but will be inferred
493
7
  //       based on the placement of invokes and pads which reach each other
494
7
  //       by exceptional exits
495
7
  // Catchswitches do not get their own states, but each gets mapped to the
496
7
  // state of its first catchpad.
497
7
498
7
  // Step one: walk down from outermost to innermost funclets, assigning each
499
7
  // catchpad and cleanuppad a state number.  Add an entry to the
500
7
  // ClrEHUnwindMap for each state, recording its HandlerParentState and
501
7
  // handler attributes.  Record the TryParentState as well for each catchpad
502
7
  // that's not the last on its catchswitch, but initialize all other entries'
503
7
  // TryParentStates to a sentinel -1 value that the next pass will update.
504
7
505
7
  // Seed a worklist with pads that have no parent.
506
7
  SmallVector<std::pair<const Instruction *, int>, 8> Worklist;
507
59
  for (const BasicBlock &BB : *Fn) {
508
59
    const Instruction *FirstNonPHI = BB.getFirstNonPHI();
509
59
    const Value *ParentPad;
510
59
    if (const auto *CPI = dyn_cast<CleanupPadInst>(FirstNonPHI))
511
8
      ParentPad = CPI->getParentPad();
512
51
    else if (const auto *CSI = dyn_cast<CatchSwitchInst>(FirstNonPHI))
513
10
      ParentPad = CSI->getParentPad();
514
41
    else
515
41
      continue;
516
18
    if (isa<ConstantTokenNone>(ParentPad))
517
9
      Worklist.emplace_back(FirstNonPHI, -1);
518
18
  }
519
7
520
7
  // Use the worklist to visit all pads, from outer to inner.  Record
521
7
  // HandlerParentState for all pads.  Record TryParentState only for catchpads
522
7
  // that aren't the last on their catchswitch (setting all other entries'
523
7
  // TryParentStates to an initial value of -1).  This loop is also responsible
524
7
  // for setting the EHPadStateMap entry for all catchpads, cleanuppads, and
525
7
  // catchswitches.
526
25
  while (!Worklist.empty()) {
527
18
    const Instruction *Pad;
528
18
    int HandlerParentState;
529
18
    std::tie(Pad, HandlerParentState) = Worklist.pop_back_val();
530
18
531
18
    if (const auto *Cleanup = dyn_cast<CleanupPadInst>(Pad)) {
532
8
      // Create the entry for this cleanup with the appropriate handler
533
8
      // properties.  Finally and fault handlers are distinguished by arity.
534
8
      ClrHandlerType HandlerType =
535
8
          (Cleanup->getNumArgOperands() ? 
ClrHandlerType::Fault7
536
8
                                        : 
ClrHandlerType::Finally1
);
537
8
      int CleanupState = addClrEHHandler(FuncInfo, HandlerParentState, -1,
538
8
                                         HandlerType, 0, Pad->getParent());
539
8
      // Queue any child EH pads on the worklist.
540
8
      for (const User *U : Cleanup->users())
541
19
        if (const auto *I = dyn_cast<Instruction>(U))
542
19
          if (I->isEHPad())
543
7
            Worklist.emplace_back(I, CleanupState);
544
8
      // Remember this pad's state.
545
8
      FuncInfo.EHPadStateMap[Cleanup] = CleanupState;
546
10
    } else {
547
10
      // Walk the handlers of this catchswitch in reverse order since all but
548
10
      // the last need to set the following one as its TryParentState.
549
10
      const auto *CatchSwitch = cast<CatchSwitchInst>(Pad);
550
10
      int CatchState = -1, FollowerState = -1;
551
10
      SmallVector<const BasicBlock *, 4> CatchBlocks(CatchSwitch->handlers());
552
10
      for (auto CBI = CatchBlocks.rbegin(), CBE = CatchBlocks.rend();
553
21
           CBI != CBE; 
++CBI, FollowerState = CatchState11
) {
554
11
        const BasicBlock *CatchBlock = *CBI;
555
11
        // Create the entry for this catch with the appropriate handler
556
11
        // properties.
557
11
        const auto *Catch = cast<CatchPadInst>(CatchBlock->getFirstNonPHI());
558
11
        uint32_t TypeToken = static_cast<uint32_t>(
559
11
            cast<ConstantInt>(Catch->getArgOperand(0))->getZExtValue());
560
11
        CatchState =
561
11
            addClrEHHandler(FuncInfo, HandlerParentState, FollowerState,
562
11
                            ClrHandlerType::Catch, TypeToken, CatchBlock);
563
11
        // Queue any child EH pads on the worklist.
564
11
        for (const User *U : Catch->users())
565
23
          if (const auto *I = dyn_cast<Instruction>(U))
566
23
            if (I->isEHPad())
567
2
              Worklist.emplace_back(I, CatchState);
568
11
        // Remember this catch's state.
569
11
        FuncInfo.EHPadStateMap[Catch] = CatchState;
570
11
      }
571
10
      // Associate the catchswitch with the state of its first catch.
572
10
      assert(CatchSwitch->getNumHandlers());
573
10
      FuncInfo.EHPadStateMap[CatchSwitch] = CatchState;
574
10
    }
575
18
  }
576
7
577
7
  // Step two: record the TryParentState of each state.  For cleanuppads that
578
7
  // don't have cleanuprets, we may need to infer this from their child pads,
579
7
  // so visit pads in descendant-most to ancestor-most order.
580
7
  for (auto Entry = FuncInfo.ClrEHUnwindMap.rbegin(),
581
7
            End = FuncInfo.ClrEHUnwindMap.rend();
582
26
       Entry != End; 
++Entry19
) {
583
19
    const Instruction *Pad =
584
19
        Entry->Handler.get<const BasicBlock *>()->getFirstNonPHI();
585
19
    // For most pads, the TryParentState is the state associated with the
586
19
    // unwind dest of exceptional exits from it.
587
19
    const BasicBlock *UnwindDest;
588
19
    if (const auto *Catch = dyn_cast<CatchPadInst>(Pad)) {
589
11
      // If a catch is not the last in its catchswitch, its TryParentState is
590
11
      // the state associated with the next catch in the switch, even though
591
11
      // that's not the unwind dest of exceptions escaping the catch.  Those
592
11
      // cases were already assigned a TryParentState in the first pass, so
593
11
      // skip them.
594
11
      if (Entry->TryParentState != -1)
595
1
        continue;
596
10
      // Otherwise, get the unwind dest from the catchswitch.
597
10
      UnwindDest = Catch->getCatchSwitch()->getUnwindDest();
598
10
    } else {
599
8
      const auto *Cleanup = cast<CleanupPadInst>(Pad);
600
8
      UnwindDest = nullptr;
601
12
      for (const User *U : Cleanup->users()) {
602
12
        if (auto *CleanupRet = dyn_cast<CleanupReturnInst>(U)) {
603
3
          // Common and unambiguous case -- cleanupret indicates cleanup's
604
3
          // unwind dest.
605
3
          UnwindDest = CleanupRet->getUnwindDest();
606
3
          break;
607
3
        }
608
9
609
9
        // Get an unwind dest for the user
610
9
        const BasicBlock *UserUnwindDest = nullptr;
611
9
        if (auto *Invoke = dyn_cast<InvokeInst>(U)) {
612
2
          UserUnwindDest = Invoke->getUnwindDest();
613
7
        } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(U)) {
614
3
          UserUnwindDest = CatchSwitch->getUnwindDest();
615
4
        } else if (auto *ChildCleanup = dyn_cast<CleanupPadInst>(U)) {
616
4
          int UserState = FuncInfo.EHPadStateMap[ChildCleanup];
617
4
          int UserUnwindState =
618
4
              FuncInfo.ClrEHUnwindMap[UserState].TryParentState;
619
4
          if (UserUnwindState != -1)
620
3
            UserUnwindDest = FuncInfo.ClrEHUnwindMap[UserUnwindState]
621
3
                                 .Handler.get<const BasicBlock *>();
622
4
        }
623
9
624
9
        // Not having an unwind dest for this user might indicate that it
625
9
        // doesn't unwind, so can't be taken as proof that the cleanup itself
626
9
        // may unwind to caller (see e.g. SimplifyUnreachable and
627
9
        // RemoveUnwindEdge).
628
9
        if (!UserUnwindDest)
629
2
          continue;
630
7
631
7
        // Now we have an unwind dest for the user, but we need to see if it
632
7
        // unwinds all the way out of the cleanup or if it stays within it.
633
7
        const Instruction *UserUnwindPad = UserUnwindDest->getFirstNonPHI();
634
7
        const Value *UserUnwindParent;
635
7
        if (auto *CSI = dyn_cast<CatchSwitchInst>(UserUnwindPad))
636
2
          UserUnwindParent = CSI->getParentPad();
637
5
        else
638
5
          UserUnwindParent =
639
5
              cast<CleanupPadInst>(UserUnwindPad)->getParentPad();
640
7
641
7
        // The unwind stays within the cleanup iff it targets a child of the
642
7
        // cleanup.
643
7
        if (UserUnwindParent == Cleanup)
644
3
          continue;
645
4
646
4
        // This unwind exits the cleanup, so its dest is the cleanup's dest.
647
4
        UnwindDest = UserUnwindDest;
648
4
        break;
649
4
      }
650
8
    }
651
19
652
19
    // Record the state of the unwind dest as the TryParentState.
653
19
    int UnwindDestState;
654
18
655
18
    // If UnwindDest is null at this point, either the pad in question can
656
18
    // be exited by unwind to caller, or it cannot be exited by unwind.  In
657
18
    // either case, reporting such cases as unwinding to caller is correct.
658
18
    // This can lead to EH tables that "look strange" -- if this pad's is in
659
18
    // a parent funclet which has other children that do unwind to an enclosing
660
18
    // pad, the try region for this pad will be missing the "duplicate" EH
661
18
    // clause entries that you'd expect to see covering the whole parent.  That
662
18
    // should be benign, since the unwind never actually happens.  If it were
663
18
    // an issue, we could add a subsequent pass that pushes unwind dests down
664
18
    // from parents that have them to children that appear to unwind to caller.
665
18
    if (!UnwindDest) {
666
10
      UnwindDestState = -1;
667
10
    } else {
668
8
      UnwindDestState = FuncInfo.EHPadStateMap[UnwindDest->getFirstNonPHI()];
669
8
    }
670
18
671
18
    Entry->TryParentState = UnwindDestState;
672
18
  }
673
7
674
7
  // Step three: transfer information from pads to invokes.
675
7
  calculateStateNumbersForInvokes(Fn, FuncInfo);
676
7
}
677
678
175
void WinEHPrepare::colorFunclets(Function &F) {
679
175
  BlockColors = colorEHFunclets(F);
680
175
681
175
  // Invert the map from BB to colors to color to BBs.
682
1.08k
  for (BasicBlock &BB : F) {
683
1.08k
    ColorVector &Colors = BlockColors[&BB];
684
1.08k
    for (BasicBlock *Color : Colors)
685
1.11k
      FuncletBlocks[Color].push_back(&BB);
686
1.08k
  }
687
175
}
688
689
void WinEHPrepare::demotePHIsOnFunclets(Function &F,
690
172
                                        bool DemoteCatchSwitchPHIOnly) {
691
172
  // Strip PHI nodes off of EH pads.
692
172
  SmallVector<PHINode *, 16> PHINodes;
693
1.25k
  for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
694
1.08k
    BasicBlock *BB = &*FI++;
695
1.08k
    if (!BB->isEHPad())
696
626
      continue;
697
458
    if (DemoteCatchSwitchPHIOnly && 
!isa<CatchSwitchInst>(BB->getFirstNonPHI())20
)
698
12
      continue;
699
446
700
455
    
for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); 446
BI != BE;) {
701
455
      Instruction *I = &*BI++;
702
455
      auto *PN = dyn_cast<PHINode>(I);
703
455
      // Stop at the first non-PHI.
704
455
      if (!PN)
705
446
        break;
706
9
707
9
      AllocaInst *SpillSlot = insertPHILoads(PN, F);
708
9
      if (SpillSlot)
709
8
        insertPHIStores(PN, SpillSlot);
710
9
711
9
      PHINodes.push_back(PN);
712
9
    }
713
446
  }
714
172
715
172
  for (auto *PN : PHINodes) {
716
9
    // There may be lingering uses on other EH PHIs being removed
717
9
    PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
718
9
    PN->eraseFromParent();
719
9
  }
720
172
}
721
722
175
void WinEHPrepare::cloneCommonBlocks(Function &F) {
723
175
  // We need to clone all blocks which belong to multiple funclets.  Values are
724
175
  // remapped throughout the funclet to propagate both the new instructions
725
175
  // *and* the new basic blocks themselves.
726
641
  for (auto &Funclets : FuncletBlocks) {
727
641
    BasicBlock *FuncletPadBB = Funclets.first;
728
641
    std::vector<BasicBlock *> &BlocksInFunclet = Funclets.second;
729
641
    Value *FuncletToken;
730
641
    if (FuncletPadBB == &F.getEntryBlock())
731
175
      FuncletToken = ConstantTokenNone::get(F.getContext());
732
466
    else
733
466
      FuncletToken = FuncletPadBB->getFirstNonPHI();
734
641
735
641
    std::vector<std::pair<BasicBlock *, BasicBlock *>> Orig2Clone;
736
641
    ValueToValueMapTy VMap;
737
1.11k
    for (BasicBlock *BB : BlocksInFunclet) {
738
1.11k
      ColorVector &ColorsForBB = BlockColors[BB];
739
1.11k
      // We don't need to do anything if the block is monochromatic.
740
1.11k
      size_t NumColorsForBB = ColorsForBB.size();
741
1.11k
      if (NumColorsForBB == 1)
742
1.08k
        continue;
743
25
744
25
      DEBUG_WITH_TYPE("winehprepare-coloring",
745
25
                      dbgs() << "  Cloning block \'" << BB->getName()
746
25
                              << "\' for funclet \'" << FuncletPadBB->getName()
747
25
                              << "\'.\n");
748
25
749
25
      // Create a new basic block and copy instructions into it!
750
25
      BasicBlock *CBB =
751
25
          CloneBasicBlock(BB, VMap, Twine(".for.", FuncletPadBB->getName()));
752
25
      // Insert the clone immediately after the original to ensure determinism
753
25
      // and to keep the same relative ordering of any funclet's blocks.
754
25
      CBB->insertInto(&F, BB->getNextNode());
755
25
756
25
      // Add basic block mapping.
757
25
      VMap[BB] = CBB;
758
25
759
25
      // Record delta operations that we need to perform to our color mappings.
760
25
      Orig2Clone.emplace_back(BB, CBB);
761
25
    }
762
641
763
641
    // If nothing was cloned, we're done cloning in this funclet.
764
641
    if (Orig2Clone.empty())
765
624
      continue;
766
17
767
17
    // Update our color mappings to reflect that one block has lost a color and
768
17
    // another has gained a color.
769
25
    
for (auto &BBMapping : Orig2Clone)17
{
770
25
      BasicBlock *OldBlock = BBMapping.first;
771
25
      BasicBlock *NewBlock = BBMapping.second;
772
25
773
25
      BlocksInFunclet.push_back(NewBlock);
774
25
      ColorVector &NewColors = BlockColors[NewBlock];
775
25
      assert(NewColors.empty() && "A new block should only have one color!");
776
25
      NewColors.push_back(FuncletPadBB);
777
25
778
25
      DEBUG_WITH_TYPE("winehprepare-coloring",
779
25
                      dbgs() << "  Assigned color \'" << FuncletPadBB->getName()
780
25
                              << "\' to block \'" << NewBlock->getName()
781
25
                              << "\'.\n");
782
25
783
25
      BlocksInFunclet.erase(
784
25
          std::remove(BlocksInFunclet.begin(), BlocksInFunclet.end(), OldBlock),
785
25
          BlocksInFunclet.end());
786
25
      ColorVector &OldColors = BlockColors[OldBlock];
787
25
      OldColors.erase(
788
25
          std::remove(OldColors.begin(), OldColors.end(), FuncletPadBB),
789
25
          OldColors.end());
790
25
791
25
      DEBUG_WITH_TYPE("winehprepare-coloring",
792
25
                      dbgs() << "  Removed color \'" << FuncletPadBB->getName()
793
25
                              << "\' from block \'" << OldBlock->getName()
794
25
                              << "\'.\n");
795
25
    }
796
17
797
17
    // Loop over all of the instructions in this funclet, fixing up operand
798
17
    // references as we go.  This uses VMap to do all the hard work.
799
17
    for (BasicBlock *BB : BlocksInFunclet)
800
49
      // Loop over all instructions, fixing each one as we find it...
801
49
      for (Instruction &I : *BB)
802
82
        RemapInstruction(&I, VMap,
803
82
                         RF_IgnoreMissingLocals | RF_NoModuleLevelChanges);
804
17
805
17
    // Catchrets targeting cloned blocks need to be updated separately from
806
17
    // the loop above because they are not in the current funclet.
807
17
    SmallVector<CatchReturnInst *, 2> FixupCatchrets;
808
25
    for (auto &BBMapping : Orig2Clone) {
809
25
      BasicBlock *OldBlock = BBMapping.first;
810
25
      BasicBlock *NewBlock = BBMapping.second;
811
25
812
25
      FixupCatchrets.clear();
813
25
      for (BasicBlock *Pred : predecessors(OldBlock))
814
39
        if (auto *CatchRet = dyn_cast<CatchReturnInst>(Pred->getTerminator()))
815
8
          if (CatchRet->getCatchSwitchParentPad() == FuncletToken)
816
1
            FixupCatchrets.push_back(CatchRet);
817
25
818
25
      for (CatchReturnInst *CatchRet : FixupCatchrets)
819
1
        CatchRet->setSuccessor(NewBlock);
820
25
    }
821
17
822
17
    auto UpdatePHIOnClonedBlock = [&](PHINode *PN, bool IsForOldBlock) {
823
6
      unsigned NumPreds = PN->getNumIncomingValues();
824
20
      for (unsigned PredIdx = 0, PredEnd = NumPreds; PredIdx != PredEnd;
825
14
           ++PredIdx) {
826
14
        BasicBlock *IncomingBlock = PN->getIncomingBlock(PredIdx);
827
14
        bool EdgeTargetsFunclet;
828
14
        if (auto *CRI =
829
4
                dyn_cast<CatchReturnInst>(IncomingBlock->getTerminator())) {
830
4
          EdgeTargetsFunclet = (CRI->getCatchSwitchParentPad() == FuncletToken);
831
10
        } else {
832
10
          ColorVector &IncomingColors = BlockColors[IncomingBlock];
833
10
          assert(!IncomingColors.empty() && "Block not colored!");
834
10
          assert((IncomingColors.size() == 1 ||
835
10
                  llvm::all_of(IncomingColors,
836
10
                               [&](BasicBlock *Color) {
837
10
                                 return Color != FuncletPadBB;
838
10
                               })) &&
839
10
                 "Cloning should leave this funclet's blocks monochromatic");
840
10
          EdgeTargetsFunclet = (IncomingColors.front() == FuncletPadBB);
841
10
        }
842
14
        if (IsForOldBlock != EdgeTargetsFunclet)
843
9
          continue;
844
5
        PN->removeIncomingValue(IncomingBlock, /*DeletePHIIfEmpty=*/false);
845
5
        // Revisit the next entry.
846
5
        --PredIdx;
847
5
        --PredEnd;
848
5
      }
849
6
    };
850
17
851
25
    for (auto &BBMapping : Orig2Clone) {
852
25
      BasicBlock *OldBlock = BBMapping.first;
853
25
      BasicBlock *NewBlock = BBMapping.second;
854
25
      for (PHINode &OldPN : OldBlock->phis()) {
855
3
        UpdatePHIOnClonedBlock(&OldPN, /*IsForOldBlock=*/true);
856
3
      }
857
25
      for (PHINode &NewPN : NewBlock->phis()) {
858
3
        UpdatePHIOnClonedBlock(&NewPN, /*IsForOldBlock=*/false);
859
3
      }
860
25
    }
861
17
862
17
    // Check to see if SuccBB has PHI nodes. If so, we need to add entries to
863
17
    // the PHI nodes for NewBB now.
864
25
    for (auto &BBMapping : Orig2Clone) {
865
25
      BasicBlock *OldBlock = BBMapping.first;
866
25
      BasicBlock *NewBlock = BBMapping.second;
867
25
      for (BasicBlock *SuccBB : successors(NewBlock)) {
868
14
        for (PHINode &SuccPN : SuccBB->phis()) {
869
3
          // Ok, we have a PHI node.  Figure out what the incoming value was for
870
3
          // the OldBlock.
871
3
          int OldBlockIdx = SuccPN.getBasicBlockIndex(OldBlock);
872
3
          if (OldBlockIdx == -1)
873
2
            break;
874
1
          Value *IV = SuccPN.getIncomingValue(OldBlockIdx);
875
1
876
1
          // Remap the value if necessary.
877
1
          if (auto *Inst = dyn_cast<Instruction>(IV)) {
878
1
            ValueToValueMapTy::iterator I = VMap.find(Inst);
879
1
            if (I != VMap.end())
880
1
              IV = I->second;
881
1
          }
882
1
883
1
          SuccPN.addIncoming(IV, NewBlock);
884
1
        }
885
14
      }
886
25
    }
887
17
888
122
    for (ValueToValueMapTy::value_type VT : VMap) {
889
122
      // If there were values defined in BB that are used outside the funclet,
890
122
      // then we now have to update all uses of the value to use either the
891
122
      // original value, the cloned value, or some PHI derived value.  This can
892
122
      // require arbitrary PHI insertion, of which we are prepared to do, clean
893
122
      // these up now.
894
122
      SmallVector<Use *, 16> UsesToRename;
895
122
896
122
      auto *OldI = dyn_cast<Instruction>(const_cast<Value *>(VT.first));
897
122
      if (!OldI)
898
75
        continue;
899
47
      auto *NewI = cast<Instruction>(VT.second);
900
47
      // Scan all uses of this instruction to see if it is used outside of its
901
47
      // funclet, and if so, record them in UsesToRename.
902
47
      for (Use &U : OldI->uses()) {
903
14
        Instruction *UserI = cast<Instruction>(U.getUser());
904
14
        BasicBlock *UserBB = UserI->getParent();
905
14
        ColorVector &ColorsForUserBB = BlockColors[UserBB];
906
14
        assert(!ColorsForUserBB.empty());
907
14
        if (ColorsForUserBB.size() > 1 ||
908
14
            *ColorsForUserBB.begin() != FuncletPadBB)
909
14
          UsesToRename.push_back(&U);
910
14
      }
911
47
912
47
      // If there are no uses outside the block, we're done with this
913
47
      // instruction.
914
47
      if (UsesToRename.empty())
915
36
        continue;
916
11
917
11
      // We found a use of OldI outside of the funclet.  Rename all uses of OldI
918
11
      // that are outside its funclet to be uses of the appropriate PHI node
919
11
      // etc.
920
11
      SSAUpdater SSAUpdate;
921
11
      SSAUpdate.Initialize(OldI->getType(), OldI->getName());
922
11
      SSAUpdate.AddAvailableValue(OldI->getParent(), OldI);
923
11
      SSAUpdate.AddAvailableValue(NewI->getParent(), NewI);
924
11
925
25
      while (!UsesToRename.empty())
926
14
        SSAUpdate.RewriteUseAfterInsertions(*UsesToRename.pop_back_val());
927
11
    }
928
17
  }
929
175
}
930
931
172
void WinEHPrepare::removeImplausibleInstructions(Function &F) {
932
172
  // Remove implausible terminators and replace them with UnreachableInst.
933
630
  for (auto &Funclet : FuncletBlocks) {
934
630
    BasicBlock *FuncletPadBB = Funclet.first;
935
630
    std::vector<BasicBlock *> &BlocksInFunclet = Funclet.second;
936
630
    Instruction *FirstNonPHI = FuncletPadBB->getFirstNonPHI();
937
630
    auto *FuncletPad = dyn_cast<FuncletPadInst>(FirstNonPHI);
938
630
    auto *CatchPad = dyn_cast_or_null<CatchPadInst>(FuncletPad);
939
630
    auto *CleanupPad = dyn_cast_or_null<CleanupPadInst>(FuncletPad);
940
630
941
1.08k
    for (BasicBlock *BB : BlocksInFunclet) {
942
2.25k
      for (Instruction &I : *BB) {
943
2.25k
        CallSite CS(&I);
944
2.25k
        if (!CS)
945
1.45k
          continue;
946
806
947
806
        Value *FuncletBundleOperand = nullptr;
948
806
        if (auto BU = CS.getOperandBundle(LLVMContext::OB_funclet))
949
264
          FuncletBundleOperand = BU->Inputs.front();
950
806
951
806
        if (FuncletBundleOperand == FuncletPad)
952
614
          continue;
953
192
954
192
        // Skip call sites which are nounwind intrinsics or inline asm.
955
192
        auto *CalledFn =
956
192
            dyn_cast<Function>(CS.getCalledValue()->stripPointerCasts());
957
192
        if (CalledFn && 
(191
(191
CalledFn->isIntrinsic()191
&&
CS.doesNotThrow()186
) ||
958
191
                         
CS.isInlineAsm()5
))
959
186
          continue;
960
6
961
6
        // This call site was not part of this funclet, remove it.
962
6
        if (CS.isInvoke()) {
963
0
          // Remove the unwind edge if it was an invoke.
964
0
          removeUnwindEdge(BB);
965
0
          // Get a pointer to the new call.
966
0
          BasicBlock::iterator CallI =
967
0
              std::prev(BB->getTerminator()->getIterator());
968
0
          auto *CI = cast<CallInst>(&*CallI);
969
0
          changeToUnreachable(CI, /*UseLLVMTrap=*/false);
970
6
        } else {
971
6
          changeToUnreachable(&I, /*UseLLVMTrap=*/false);
972
6
        }
973
6
974
6
        // There are no more instructions in the block (except for unreachable),
975
6
        // we are done.
976
6
        break;
977
6
      }
978
1.08k
979
1.08k
      Instruction *TI = BB->getTerminator();
980
1.08k
      // CatchPadInst and CleanupPadInst can't transfer control to a ReturnInst.
981
1.08k
      bool IsUnreachableRet = isa<ReturnInst>(TI) && 
FuncletPad172
;
982
1.08k
      // The token consumed by a CatchReturnInst must match the funclet token.
983
1.08k
      bool IsUnreachableCatchret = false;
984
1.08k
      if (auto *CRI = dyn_cast<CatchReturnInst>(TI))
985
179
        IsUnreachableCatchret = CRI->getCatchPad() != CatchPad;
986
1.08k
      // The token consumed by a CleanupReturnInst must match the funclet token.
987
1.08k
      bool IsUnreachableCleanupret = false;
988
1.08k
      if (auto *CRI = dyn_cast<CleanupReturnInst>(TI))
989
65
        IsUnreachableCleanupret = CRI->getCleanupPad() != CleanupPad;
990
1.08k
      if (IsUnreachableRet || 
IsUnreachableCatchret1.08k
||
991
1.08k
          
IsUnreachableCleanupret1.08k
) {
992
4
        changeToUnreachable(TI, /*UseLLVMTrap=*/false);
993
1.08k
      } else if (isa<InvokeInst>(TI)) {
994
285
        if (Personality == EHPersonality::MSVC_CXX && 
CleanupPad125
) {
995
0
          // Invokes within a cleanuppad for the MSVC++ personality never
996
0
          // transfer control to their unwind edge: the personality will
997
0
          // terminate the program.
998
0
          removeUnwindEdge(BB);
999
0
        }
1000
285
      }
1001
1.08k
    }
1002
630
  }
1003
172
}
1004
1005
172
void WinEHPrepare::cleanupPreparedFunclets(Function &F) {
1006
172
  // Clean-up some of the mess we made by removing useles PHI nodes, trivial
1007
172
  // branches, etc.
1008
1.25k
  for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
1009
1.08k
    BasicBlock *BB = &*FI++;
1010
1.08k
    SimplifyInstructionsInBlock(BB);
1011
1.08k
    ConstantFoldTerminator(BB, /*DeleteDeadConditions=*/true);
1012
1.08k
    MergeBlockIntoPredecessor(BB);
1013
1.08k
  }
1014
172
1015
172
  // We might have some unreachable blocks after cleaning up some impossible
1016
172
  // control flow.
1017
172
  removeUnreachableBlocks(F);
1018
172
}
1019
1020
#ifndef NDEBUG
1021
void WinEHPrepare::verifyPreparedFunclets(Function &F) {
1022
  for (BasicBlock &BB : F) {
1023
    size_t NumColors = BlockColors[&BB].size();
1024
    assert(NumColors == 1 && "Expected monochromatic BB!");
1025
    if (NumColors == 0)
1026
      report_fatal_error("Uncolored BB!");
1027
    if (NumColors > 1)
1028
      report_fatal_error("Multicolor BB!");
1029
    assert((DisableDemotion || !(BB.isEHPad() && isa<PHINode>(BB.begin()))) &&
1030
           "EH Pad still has a PHI!");
1031
  }
1032
}
1033
#endif
1034
1035
175
bool WinEHPrepare::prepareExplicitEH(Function &F) {
1036
175
  // Remove unreachable blocks.  It is not valuable to assign them a color and
1037
175
  // their existence can trick us into thinking values are alive when they are
1038
175
  // not.
1039
175
  removeUnreachableBlocks(F);
1040
175
1041
175
  // Determine which blocks are reachable from which funclet entries.
1042
175
  colorFunclets(F);
1043
175
1044
175
  cloneCommonBlocks(F);
1045
175
1046
175
  if (!DisableDemotion)
1047
172
    demotePHIsOnFunclets(F, DemoteCatchSwitchPHIOnly ||
1048
172
                                DemoteCatchSwitchPHIOnlyOpt);
1049
175
1050
175
  if (!DisableCleanups) {
1051
172
    LLVM_DEBUG(verifyFunction(F));
1052
172
    removeImplausibleInstructions(F);
1053
172
1054
172
    LLVM_DEBUG(verifyFunction(F));
1055
172
    cleanupPreparedFunclets(F);
1056
172
  }
1057
175
1058
175
  LLVM_DEBUG(verifyPreparedFunclets(F));
1059
175
  // Recolor the CFG to verify that all is well.
1060
175
  LLVM_DEBUG(colorFunclets(F));
1061
175
  LLVM_DEBUG(verifyPreparedFunclets(F));
1062
175
1063
175
  BlockColors.clear();
1064
175
  FuncletBlocks.clear();
1065
175
1066
175
  return true;
1067
175
}
1068
1069
// TODO: Share loads when one use dominates another, or when a catchpad exit
1070
// dominates uses (needs dominators).
1071
9
AllocaInst *WinEHPrepare::insertPHILoads(PHINode *PN, Function &F) {
1072
9
  BasicBlock *PHIBlock = PN->getParent();
1073
9
  AllocaInst *SpillSlot = nullptr;
1074
9
  Instruction *EHPad = PHIBlock->getFirstNonPHI();
1075
9
1076
9
  if (!EHPad->isTerminator()) {
1077
1
    // If the EHPad isn't a terminator, then we can insert a load in this block
1078
1
    // that will dominate all uses.
1079
1
    SpillSlot = new AllocaInst(PN->getType(), DL->getAllocaAddrSpace(), nullptr,
1080
1
                               Twine(PN->getName(), ".wineh.spillslot"),
1081
1
                               &F.getEntryBlock().front());
1082
1
    Value *V = new LoadInst(PN->getType(), SpillSlot,
1083
1
                            Twine(PN->getName(), ".wineh.reload"),
1084
1
                            &*PHIBlock->getFirstInsertionPt());
1085
1
    PN->replaceAllUsesWith(V);
1086
1
    return SpillSlot;
1087
1
  }
1088
8
1089
8
  // Otherwise, we have a PHI on a terminator EHPad, and we give up and insert
1090
8
  // loads of the slot before every use.
1091
8
  DenseMap<BasicBlock *, Value *> Loads;
1092
8
  for (Value::use_iterator UI = PN->use_begin(), UE = PN->use_end();
1093
17
       UI != UE;) {
1094
9
    Use &U = *UI++;
1095
9
    auto *UsingInst = cast<Instruction>(U.getUser());
1096
9
    if (isa<PHINode>(UsingInst) && 
UsingInst->getParent()->isEHPad()3
) {
1097
2
      // Use is on an EH pad phi.  Leave it alone; we'll insert loads and
1098
2
      // stores for it separately.
1099
2
      continue;
1100
2
    }
1101
7
    replaceUseWithLoad(PN, U, SpillSlot, Loads, F);
1102
7
  }
1103
8
  return SpillSlot;
1104
8
}
1105
1106
// TODO: improve store placement.  Inserting at def is probably good, but need
1107
// to be careful not to introduce interfering stores (needs liveness analysis).
1108
// TODO: identify related phi nodes that can share spill slots, and share them
1109
// (also needs liveness).
1110
void WinEHPrepare::insertPHIStores(PHINode *OriginalPHI,
1111
8
                                   AllocaInst *SpillSlot) {
1112
8
  // Use a worklist of (Block, Value) pairs -- the given Value needs to be
1113
8
  // stored to the spill slot by the end of the given Block.
1114
8
  SmallVector<std::pair<BasicBlock *, Value *>, 4> Worklist;
1115
8
1116
8
  Worklist.push_back({OriginalPHI->getParent(), OriginalPHI});
1117
8
1118
18
  while (!Worklist.empty()) {
1119
10
    BasicBlock *EHBlock;
1120
10
    Value *InVal;
1121
10
    std::tie(EHBlock, InVal) = Worklist.pop_back_val();
1122
10
1123
10
    PHINode *PN = dyn_cast<PHINode>(InVal);
1124
10
    if (PN && PN->getParent() == EHBlock) {
1125
10
      // The value is defined by another PHI we need to remove, with no room to
1126
10
      // insert a store after the PHI, so each predecessor needs to store its
1127
10
      // incoming value.
1128
30
      for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; 
++i20
) {
1129
20
        Value *PredVal = PN->getIncomingValue(i);
1130
20
1131
20
        // Undef can safely be skipped.
1132
20
        if (isa<UndefValue>(PredVal))
1133
0
          continue;
1134
20
1135
20
        insertPHIStore(PN->getIncomingBlock(i), PredVal, SpillSlot, Worklist);
1136
20
      }
1137
10
    } else {
1138
0
      // We need to store InVal, which dominates EHBlock, but can't put a store
1139
0
      // in EHBlock, so need to put stores in each predecessor.
1140
0
      for (BasicBlock *PredBlock : predecessors(EHBlock)) {
1141
0
        insertPHIStore(PredBlock, InVal, SpillSlot, Worklist);
1142
0
      }
1143
0
    }
1144
10
  }
1145
8
}
1146
1147
void WinEHPrepare::insertPHIStore(
1148
    BasicBlock *PredBlock, Value *PredVal, AllocaInst *SpillSlot,
1149
20
    SmallVectorImpl<std::pair<BasicBlock *, Value *>> &Worklist) {
1150
20
1151
20
  if (PredBlock->isEHPad() && 
PredBlock->getFirstNonPHI()->isTerminator()3
) {
1152
2
    // Pred is unsplittable, so we need to queue it on the worklist.
1153
2
    Worklist.push_back({PredBlock, PredVal});
1154
2
    return;
1155
2
  }
1156
18
1157
18
  // Otherwise, insert the store at the end of the basic block.
1158
18
  new StoreInst(PredVal, SpillSlot, PredBlock->getTerminator());
1159
18
}
1160
1161
void WinEHPrepare::replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot,
1162
                                      DenseMap<BasicBlock *, Value *> &Loads,
1163
7
                                      Function &F) {
1164
7
  // Lazilly create the spill slot.
1165
7
  if (!SpillSlot)
1166
7
    SpillSlot = new AllocaInst(V->getType(), DL->getAllocaAddrSpace(), nullptr,
1167
7
                               Twine(V->getName(), ".wineh.spillslot"),
1168
7
                               &F.getEntryBlock().front());
1169
7
1170
7
  auto *UsingInst = cast<Instruction>(U.getUser());
1171
7
  if (auto *UsingPHI = dyn_cast<PHINode>(UsingInst)) {
1172
1
    // If this is a PHI node, we can't insert a load of the value before
1173
1
    // the use.  Instead insert the load in the predecessor block
1174
1
    // corresponding to the incoming value.
1175
1
    //
1176
1
    // Note that if there are multiple edges from a basic block to this
1177
1
    // PHI node that we cannot have multiple loads.  The problem is that
1178
1
    // the resulting PHI node will have multiple values (from each load)
1179
1
    // coming in from the same block, which is illegal SSA form.
1180
1
    // For this reason, we keep track of and reuse loads we insert.
1181
1
    BasicBlock *IncomingBlock = UsingPHI->getIncomingBlock(U);
1182
1
    if (auto *CatchRet =
1183
1
            dyn_cast<CatchReturnInst>(IncomingBlock->getTerminator())) {
1184
1
      // Putting a load above a catchret and use on the phi would still leave
1185
1
      // a cross-funclet def/use.  We need to split the edge, change the
1186
1
      // catchret to target the new block, and put the load there.
1187
1
      BasicBlock *PHIBlock = UsingInst->getParent();
1188
1
      BasicBlock *NewBlock = SplitEdge(IncomingBlock, PHIBlock);
1189
1
      // SplitEdge gives us:
1190
1
      //   IncomingBlock:
1191
1
      //     ...
1192
1
      //     br label %NewBlock
1193
1
      //   NewBlock:
1194
1
      //     catchret label %PHIBlock
1195
1
      // But we need:
1196
1
      //   IncomingBlock:
1197
1
      //     ...
1198
1
      //     catchret label %NewBlock
1199
1
      //   NewBlock:
1200
1
      //     br label %PHIBlock
1201
1
      // So move the terminators to each others' blocks and swap their
1202
1
      // successors.
1203
1
      BranchInst *Goto = cast<BranchInst>(IncomingBlock->getTerminator());
1204
1
      Goto->removeFromParent();
1205
1
      CatchRet->removeFromParent();
1206
1
      IncomingBlock->getInstList().push_back(CatchRet);
1207
1
      NewBlock->getInstList().push_back(Goto);
1208
1
      Goto->setSuccessor(0, PHIBlock);
1209
1
      CatchRet->setSuccessor(NewBlock);
1210
1
      // Update the color mapping for the newly split edge.
1211
1
      // Grab a reference to the ColorVector to be inserted before getting the
1212
1
      // reference to the vector we are copying because inserting the new
1213
1
      // element in BlockColors might cause the map to be reallocated.
1214
1
      ColorVector &ColorsForNewBlock = BlockColors[NewBlock];
1215
1
      ColorVector &ColorsForPHIBlock = BlockColors[PHIBlock];
1216
1
      ColorsForNewBlock = ColorsForPHIBlock;
1217
1
      for (BasicBlock *FuncletPad : ColorsForPHIBlock)
1218
1
        FuncletBlocks[FuncletPad].push_back(NewBlock);
1219
1
      // Treat the new block as incoming for load insertion.
1220
1
      IncomingBlock = NewBlock;
1221
1
    }
1222
1
    Value *&Load = Loads[IncomingBlock];
1223
1
    // Insert the load into the predecessor block
1224
1
    if (!Load)
1225
1
      Load = new LoadInst(V->getType(), SpillSlot,
1226
1
                          Twine(V->getName(), ".wineh.reload"),
1227
1
                          /*isVolatile=*/false, IncomingBlock->getTerminator());
1228
1
1229
1
    U.set(Load);
1230
6
  } else {
1231
6
    // Reload right before the old use.
1232
6
    auto *Load = new LoadInst(V->getType(), SpillSlot,
1233
6
                              Twine(V->getName(), ".wineh.reload"),
1234
6
                              /*isVolatile=*/false, UsingInst);
1235
6
    U.set(Load);
1236
6
  }
1237
7
}
1238
1239
void WinEHFuncInfo::addIPToStateRange(const InvokeInst *II,
1240
                                      MCSymbol *InvokeBegin,
1241
166
                                      MCSymbol *InvokeEnd) {
1242
166
  assert(InvokeStateMap.count(II) &&
1243
166
         "should get invoke with precomputed state");
1244
166
  LabelToStateMap[InvokeBegin] = std::make_pair(InvokeStateMap[II], InvokeEnd);
1245
166
}
1246
1247
151
WinEHFuncInfo::WinEHFuncInfo() {}