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