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