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