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