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

source code of llvm/lib/CodeGen/WinEHPrepare.cpp