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