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