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