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