• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===-- WinEHPrepare - Prepare exception handling for code generation ---===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This pass lowers LLVM IR exception handling into something closer to what the
11 // backend wants for functions using a personality function from a runtime
12 // provided by MSVC. Functions with other personality functions are left alone
13 // and may be prepared by other passes. In particular, all supported MSVC
14 // personality functions require cleanup code to be outlined, and the C++
15 // personality requires catch handler code to be outlined.
16 //
17 //===----------------------------------------------------------------------===//
18 
19 #include "llvm/CodeGen/Passes.h"
20 #include "llvm/ADT/DenseMap.h"
21 #include "llvm/ADT/MapVector.h"
22 #include "llvm/ADT/STLExtras.h"
23 #include "llvm/Analysis/CFG.h"
24 #include "llvm/Analysis/EHPersonalities.h"
25 #include "llvm/CodeGen/MachineBasicBlock.h"
26 #include "llvm/CodeGen/WinEHFuncInfo.h"
27 #include "llvm/IR/Verifier.h"
28 #include "llvm/MC/MCSymbol.h"
29 #include "llvm/Pass.h"
30 #include "llvm/Support/Debug.h"
31 #include "llvm/Support/raw_ostream.h"
32 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
33 #include "llvm/Transforms/Utils/Cloning.h"
34 #include "llvm/Transforms/Utils/Local.h"
35 #include "llvm/Transforms/Utils/SSAUpdater.h"
36 
37 using namespace llvm;
38 
39 #define DEBUG_TYPE "winehprepare"
40 
41 static cl::opt<bool> DisableDemotion(
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 
47 static cl::opt<bool> DisableCleanups(
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.
WinEHPrepare(const TargetMachine * TM=nullptr)57   WinEHPrepare(const TargetMachine *TM = nullptr) : 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 
getPassName() const65   const char *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,
76                           DenseMap<BasicBlock *, Value *> &Loads, Function &F);
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.
87   EHPersonality Personality = EHPersonality::Unknown;
88 
89   DenseMap<BasicBlock *, ColorVector> BlockColors;
90   MapVector<BasicBlock *, std::vector<BasicBlock *>> FuncletBlocks;
91 };
92 
93 } // end anonymous namespace
94 
95 char WinEHPrepare::ID = 0;
96 INITIALIZE_TM_PASS(WinEHPrepare, "winehprepare", "Prepare Windows exceptions",
97                    false, false)
98 
createWinEHPass(const TargetMachine * TM)99 FunctionPass *llvm::createWinEHPass(const TargetMachine *TM) {
100   return new WinEHPrepare(TM);
101 }
102 
runOnFunction(Function & Fn)103 bool WinEHPrepare::runOnFunction(Function &Fn) {
104   if (!Fn.hasPersonalityFn())
105     return false;
106 
107   // Classify the personality to see what kind of preparation we need.
108   Personality = classifyEHPersonality(Fn.getPersonalityFn());
109 
110   // Do nothing if this is not a funclet-based personality.
111   if (!isFuncletEHPersonality(Personality))
112     return false;
113 
114   return prepareExplicitEH(Fn);
115 }
116 
doFinalization(Module & M)117 bool WinEHPrepare::doFinalization(Module &M) { return false; }
118 
getAnalysisUsage(AnalysisUsage & AU) const119 void WinEHPrepare::getAnalysisUsage(AnalysisUsage &AU) const {}
120 
addUnwindMapEntry(WinEHFuncInfo & FuncInfo,int ToState,const BasicBlock * BB)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 
addTryBlockMapEntry(WinEHFuncInfo & FuncInfo,int TryLow,int TryHigh,int CatchHigh,ArrayRef<const CatchPadInst * > Handlers)130 static void addTryBlockMapEntry(WinEHFuncInfo &FuncInfo, int TryLow,
131                                 int TryHigh, int CatchHigh,
132                                 ArrayRef<const CatchPadInst *> Handlers) {
133   WinEHTryBlockMapEntry TBME;
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 
getCleanupRetUnwindDest(const CleanupPadInst * CleanupPad)157 static BasicBlock *getCleanupRetUnwindDest(const CleanupPadInst *CleanupPad) {
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 
calculateStateNumbersForInvokes(const Function * Fn,WinEHFuncInfo & FuncInfo)164 static void calculateStateNumbersForInvokes(const Function *Fn,
165                                             WinEHFuncInfo &FuncInfo) {
166   auto *F = const_cast<Function *>(Fn);
167   DenseMap<BasicBlock *, ColorVector> BlockColors = colorEHFunclets(*F);
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.
getEHPadFromPredecessor(const BasicBlock * BB,Value * ParentPad)210 static const BasicBlock *getEHPadFromPredecessor(const BasicBlock *BB,
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 
calculateCXXStateNumbers(WinEHFuncInfo & FuncInfo,const Instruction * FirstNonPHI,int ParentState)227 static void calculateCXXStateNumbers(WinEHFuncInfo &FuncInfo,
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 
237     SmallVector<const CatchPadInst *, 2> Handlers;
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 
addSEHExcept(WinEHFuncInfo & FuncInfo,int ParentState,const Function * Filter,const BasicBlock * Handler)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 
addSEHFinally(WinEHFuncInfo & FuncInfo,int ParentState,const BasicBlock * Handler)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 
calculateSEHStateNumbers(WinEHFuncInfo & FuncInfo,const Instruction * FirstNonPHI,int ParentState)328 static void calculateSEHStateNumbers(WinEHFuncInfo &FuncInfo,
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 
isTopLevelPadForMSVC(const Instruction * EHPad)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 
calculateSEHStateNumbers(const Function * Fn,WinEHFuncInfo & FuncInfo)418 void llvm::calculateSEHStateNumbers(const Function *Fn,
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 
calculateWinCXXEHStateNumbers(const Function * Fn,WinEHFuncInfo & FuncInfo)436 void llvm::calculateWinCXXEHStateNumbers(const Function *Fn,
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 
addClrEHHandler(WinEHFuncInfo & FuncInfo,int HandlerParentState,int TryParentState,ClrHandlerType HandlerType,uint32_t TypeToken,const BasicBlock * Handler)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 
calculateClrEHStateNumbers(const Function * Fn,WinEHFuncInfo & FuncInfo)467 void llvm::calculateClrEHStateNumbers(const Function *Fn,
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.
497   SmallVector<std::pair<const Instruction *, int>, 8> Worklist;
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.  Finaly and fault handlers are distinguished by arity.
525       ClrHandlerType HandlerType =
526           (Cleanup->getNumArgOperands() ? ClrHandlerType::Fault
527                                         : ClrHandlerType::Finally);
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 
colorFunclets(Function & F)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 
demotePHIsOnFunclets(Function & F)680 void WinEHPrepare::demotePHIsOnFunclets(Function &F) {
681   // Strip PHI nodes off of EH pads.
682   SmallVector<PHINode *, 16> PHINodes;
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 
cloneCommonBlocks(Function & F)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 propogate 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,
790                          RF_IgnoreMissingLocals | RF_NoModuleLevelChanges);
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 
removeImplausibleInstructions(Function & F)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 =
953             dyn_cast<Function>(CS.getCalledValue()->stripPointerCasts());
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 
cleanupPreparedFunclets(Function & F)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++;
1007     SimplifyInstructionsInBlock(BB);
1008     ConstantFoldTerminator(BB, /*DeleteDeadConditions=*/true);
1009     MergeBlockIntoPredecessor(BB);
1010   }
1011 
1012   // We might have some unreachable blocks after cleaning up some impossible
1013   // control flow.
1014   removeUnreachableBlocks(F);
1015 }
1016 
verifyPreparedFunclets(Function & F)1017 void WinEHPrepare::verifyPreparedFunclets(Function &F) {
1018   for (BasicBlock &BB : F) {
1019     size_t NumColors = BlockColors[&BB].size();
1020     assert(NumColors == 1 && "Expected monochromatic BB!");
1021     if (NumColors == 0)
1022       report_fatal_error("Uncolored BB!");
1023     if (NumColors > 1)
1024       report_fatal_error("Multicolor BB!");
1025     assert((DisableDemotion || !(BB.isEHPad() && isa<PHINode>(BB.begin()))) &&
1026            "EH Pad still has a PHI!");
1027   }
1028 }
1029 
prepareExplicitEH(Function & F)1030 bool WinEHPrepare::prepareExplicitEH(Function &F) {
1031   // Remove unreachable blocks.  It is not valuable to assign them a color and
1032   // their existence can trick us into thinking values are alive when they are
1033   // not.
1034   removeUnreachableBlocks(F);
1035 
1036   // Determine which blocks are reachable from which funclet entries.
1037   colorFunclets(F);
1038 
1039   cloneCommonBlocks(F);
1040 
1041   if (!DisableDemotion)
1042     demotePHIsOnFunclets(F);
1043 
1044   if (!DisableCleanups) {
1045     DEBUG(verifyFunction(F));
1046     removeImplausibleInstructions(F);
1047 
1048     DEBUG(verifyFunction(F));
1049     cleanupPreparedFunclets(F);
1050   }
1051 
1052   DEBUG(verifyPreparedFunclets(F));
1053   // Recolor the CFG to verify that all is well.
1054   DEBUG(colorFunclets(F));
1055   DEBUG(verifyPreparedFunclets(F));
1056 
1057   BlockColors.clear();
1058   FuncletBlocks.clear();
1059 
1060   return true;
1061 }
1062 
1063 // TODO: Share loads when one use dominates another, or when a catchpad exit
1064 // dominates uses (needs dominators).
insertPHILoads(PHINode * PN,Function & F)1065 AllocaInst *WinEHPrepare::insertPHILoads(PHINode *PN, Function &F) {
1066   BasicBlock *PHIBlock = PN->getParent();
1067   AllocaInst *SpillSlot = nullptr;
1068   Instruction *EHPad = PHIBlock->getFirstNonPHI();
1069 
1070   if (!isa<TerminatorInst>(EHPad)) {
1071     // If the EHPad isn't a terminator, then we can insert a load in this block
1072     // that will dominate all uses.
1073     SpillSlot = new AllocaInst(PN->getType(), nullptr,
1074                                Twine(PN->getName(), ".wineh.spillslot"),
1075                                &F.getEntryBlock().front());
1076     Value *V = new LoadInst(SpillSlot, Twine(PN->getName(), ".wineh.reload"),
1077                             &*PHIBlock->getFirstInsertionPt());
1078     PN->replaceAllUsesWith(V);
1079     return SpillSlot;
1080   }
1081 
1082   // Otherwise, we have a PHI on a terminator EHPad, and we give up and insert
1083   // loads of the slot before every use.
1084   DenseMap<BasicBlock *, Value *> Loads;
1085   for (Value::use_iterator UI = PN->use_begin(), UE = PN->use_end();
1086        UI != UE;) {
1087     Use &U = *UI++;
1088     auto *UsingInst = cast<Instruction>(U.getUser());
1089     if (isa<PHINode>(UsingInst) && UsingInst->getParent()->isEHPad()) {
1090       // Use is on an EH pad phi.  Leave it alone; we'll insert loads and
1091       // stores for it separately.
1092       continue;
1093     }
1094     replaceUseWithLoad(PN, U, SpillSlot, Loads, F);
1095   }
1096   return SpillSlot;
1097 }
1098 
1099 // TODO: improve store placement.  Inserting at def is probably good, but need
1100 // to be careful not to introduce interfering stores (needs liveness analysis).
1101 // TODO: identify related phi nodes that can share spill slots, and share them
1102 // (also needs liveness).
insertPHIStores(PHINode * OriginalPHI,AllocaInst * SpillSlot)1103 void WinEHPrepare::insertPHIStores(PHINode *OriginalPHI,
1104                                    AllocaInst *SpillSlot) {
1105   // Use a worklist of (Block, Value) pairs -- the given Value needs to be
1106   // stored to the spill slot by the end of the given Block.
1107   SmallVector<std::pair<BasicBlock *, Value *>, 4> Worklist;
1108 
1109   Worklist.push_back({OriginalPHI->getParent(), OriginalPHI});
1110 
1111   while (!Worklist.empty()) {
1112     BasicBlock *EHBlock;
1113     Value *InVal;
1114     std::tie(EHBlock, InVal) = Worklist.pop_back_val();
1115 
1116     PHINode *PN = dyn_cast<PHINode>(InVal);
1117     if (PN && PN->getParent() == EHBlock) {
1118       // The value is defined by another PHI we need to remove, with no room to
1119       // insert a store after the PHI, so each predecessor needs to store its
1120       // incoming value.
1121       for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i) {
1122         Value *PredVal = PN->getIncomingValue(i);
1123 
1124         // Undef can safely be skipped.
1125         if (isa<UndefValue>(PredVal))
1126           continue;
1127 
1128         insertPHIStore(PN->getIncomingBlock(i), PredVal, SpillSlot, Worklist);
1129       }
1130     } else {
1131       // We need to store InVal, which dominates EHBlock, but can't put a store
1132       // in EHBlock, so need to put stores in each predecessor.
1133       for (BasicBlock *PredBlock : predecessors(EHBlock)) {
1134         insertPHIStore(PredBlock, InVal, SpillSlot, Worklist);
1135       }
1136     }
1137   }
1138 }
1139 
insertPHIStore(BasicBlock * PredBlock,Value * PredVal,AllocaInst * SpillSlot,SmallVectorImpl<std::pair<BasicBlock *,Value * >> & Worklist)1140 void WinEHPrepare::insertPHIStore(
1141     BasicBlock *PredBlock, Value *PredVal, AllocaInst *SpillSlot,
1142     SmallVectorImpl<std::pair<BasicBlock *, Value *>> &Worklist) {
1143 
1144   if (PredBlock->isEHPad() &&
1145       isa<TerminatorInst>(PredBlock->getFirstNonPHI())) {
1146     // Pred is unsplittable, so we need to queue it on the worklist.
1147     Worklist.push_back({PredBlock, PredVal});
1148     return;
1149   }
1150 
1151   // Otherwise, insert the store at the end of the basic block.
1152   new StoreInst(PredVal, SpillSlot, PredBlock->getTerminator());
1153 }
1154 
replaceUseWithLoad(Value * V,Use & U,AllocaInst * & SpillSlot,DenseMap<BasicBlock *,Value * > & Loads,Function & F)1155 void WinEHPrepare::replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot,
1156                                       DenseMap<BasicBlock *, Value *> &Loads,
1157                                       Function &F) {
1158   // Lazilly create the spill slot.
1159   if (!SpillSlot)
1160     SpillSlot = new AllocaInst(V->getType(), nullptr,
1161                                Twine(V->getName(), ".wineh.spillslot"),
1162                                &F.getEntryBlock().front());
1163 
1164   auto *UsingInst = cast<Instruction>(U.getUser());
1165   if (auto *UsingPHI = dyn_cast<PHINode>(UsingInst)) {
1166     // If this is a PHI node, we can't insert a load of the value before
1167     // the use.  Instead insert the load in the predecessor block
1168     // corresponding to the incoming value.
1169     //
1170     // Note that if there are multiple edges from a basic block to this
1171     // PHI node that we cannot have multiple loads.  The problem is that
1172     // the resulting PHI node will have multiple values (from each load)
1173     // coming in from the same block, which is illegal SSA form.
1174     // For this reason, we keep track of and reuse loads we insert.
1175     BasicBlock *IncomingBlock = UsingPHI->getIncomingBlock(U);
1176     if (auto *CatchRet =
1177             dyn_cast<CatchReturnInst>(IncomingBlock->getTerminator())) {
1178       // Putting a load above a catchret and use on the phi would still leave
1179       // a cross-funclet def/use.  We need to split the edge, change the
1180       // catchret to target the new block, and put the load there.
1181       BasicBlock *PHIBlock = UsingInst->getParent();
1182       BasicBlock *NewBlock = SplitEdge(IncomingBlock, PHIBlock);
1183       // SplitEdge gives us:
1184       //   IncomingBlock:
1185       //     ...
1186       //     br label %NewBlock
1187       //   NewBlock:
1188       //     catchret label %PHIBlock
1189       // But we need:
1190       //   IncomingBlock:
1191       //     ...
1192       //     catchret label %NewBlock
1193       //   NewBlock:
1194       //     br label %PHIBlock
1195       // So move the terminators to each others' blocks and swap their
1196       // successors.
1197       BranchInst *Goto = cast<BranchInst>(IncomingBlock->getTerminator());
1198       Goto->removeFromParent();
1199       CatchRet->removeFromParent();
1200       IncomingBlock->getInstList().push_back(CatchRet);
1201       NewBlock->getInstList().push_back(Goto);
1202       Goto->setSuccessor(0, PHIBlock);
1203       CatchRet->setSuccessor(NewBlock);
1204       // Update the color mapping for the newly split edge.
1205       ColorVector &ColorsForPHIBlock = BlockColors[PHIBlock];
1206       BlockColors[NewBlock] = ColorsForPHIBlock;
1207       for (BasicBlock *FuncletPad : ColorsForPHIBlock)
1208         FuncletBlocks[FuncletPad].push_back(NewBlock);
1209       // Treat the new block as incoming for load insertion.
1210       IncomingBlock = NewBlock;
1211     }
1212     Value *&Load = Loads[IncomingBlock];
1213     // Insert the load into the predecessor block
1214     if (!Load)
1215       Load = new LoadInst(SpillSlot, Twine(V->getName(), ".wineh.reload"),
1216                           /*Volatile=*/false, IncomingBlock->getTerminator());
1217 
1218     U.set(Load);
1219   } else {
1220     // Reload right before the old use.
1221     auto *Load = new LoadInst(SpillSlot, Twine(V->getName(), ".wineh.reload"),
1222                               /*Volatile=*/false, UsingInst);
1223     U.set(Load);
1224   }
1225 }
1226 
addIPToStateRange(const InvokeInst * II,MCSymbol * InvokeBegin,MCSymbol * InvokeEnd)1227 void WinEHFuncInfo::addIPToStateRange(const InvokeInst *II,
1228                                       MCSymbol *InvokeBegin,
1229                                       MCSymbol *InvokeEnd) {
1230   assert(InvokeStateMap.count(II) &&
1231          "should get invoke with precomputed state");
1232   LabelToStateMap[InvokeBegin] = std::make_pair(InvokeStateMap[II], InvokeEnd);
1233 }
1234 
WinEHFuncInfo()1235 WinEHFuncInfo::WinEHFuncInfo() {}
1236