blob: cdf79374e974f875ccf13f7794f1e9da4740d0d3 [file] [log] [blame]
Andrew Kaylor1476e6d2015-02-24 20:49:35 +00001//===-- WinEHPrepare - Prepare exception handling for code generation ---===//
2//
Chandler Carruth2946cd72019-01-19 08:50:56 +00003// 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
Andrew Kaylor1476e6d2015-02-24 20:49:35 +00006//
7//===----------------------------------------------------------------------===//
8//
9// This pass lowers LLVM IR exception handling into something closer to what the
Reid Kleckner0738a9c2015-05-05 17:44:16 +000010// 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.
Andrew Kaylor1476e6d2015-02-24 20:49:35 +000015//
16//===----------------------------------------------------------------------===//
17
Joseph Tremoulet52f729a2016-01-04 16:16:01 +000018#include "llvm/ADT/DenseMap.h"
David Majnemer8a1c45d2015-12-12 05:38:55 +000019#include "llvm/ADT/MapVector.h"
Joseph Tremoulet52f729a2016-01-04 16:16:01 +000020#include "llvm/ADT/STLExtras.h"
David Majnemerfd9f4772015-08-11 01:15:26 +000021#include "llvm/Analysis/CFG.h"
David Majnemer70497c62015-12-02 23:06:39 +000022#include "llvm/Analysis/EHPersonalities.h"
David Blaikie31b98d22018-06-04 21:23:21 +000023#include "llvm/Transforms/Utils/Local.h"
Chandler Carruthe0115342015-12-29 09:24:39 +000024#include "llvm/CodeGen/MachineBasicBlock.h"
Chandler Carruth6bda14b2017-06-06 11:49:48 +000025#include "llvm/CodeGen/Passes.h"
David Majnemercde33032015-03-30 22:58:10 +000026#include "llvm/CodeGen/WinEHFuncInfo.h"
David Majnemerdbdc9c22016-01-02 09:26:36 +000027#include "llvm/IR/Verifier.h"
Chandler Carruthe0115342015-12-29 09:24:39 +000028#include "llvm/MC/MCSymbol.h"
Andrew Kaylor1476e6d2015-02-24 20:49:35 +000029#include "llvm/Pass.h"
Andrew Kaylor6b67d422015-03-11 23:22:06 +000030#include "llvm/Support/Debug.h"
Benjamin Kramera8d61b12015-03-23 18:57:17 +000031#include "llvm/Support/raw_ostream.h"
Andrew Kaylor6b67d422015-03-11 23:22:06 +000032#include "llvm/Transforms/Utils/BasicBlockUtils.h"
Andrew Kaylor1476e6d2015-02-24 20:49:35 +000033#include "llvm/Transforms/Utils/Cloning.h"
David Majnemer459a64a2015-09-16 18:40:37 +000034#include "llvm/Transforms/Utils/SSAUpdater.h"
Andrew Kaylor1476e6d2015-02-24 20:49:35 +000035
36using namespace llvm;
Andrew Kaylor1476e6d2015-02-24 20:49:35 +000037
38#define DEBUG_TYPE "winehprepare"
39
David Majnemer459a64a2015-09-16 18:40:37 +000040static cl::opt<bool> DisableDemotion(
41 "disable-demotion", cl::Hidden,
42 cl::desc(
Heejin Ahnb4be38f2018-05-17 20:52:03 +000043 "Clone multicolor basic blocks but do not demote cross scopes"),
David Majnemer459a64a2015-09-16 18:40:37 +000044 cl::init(false));
45
46static cl::opt<bool> DisableCleanups(
47 "disable-cleanups", cl::Hidden,
48 cl::desc("Do not remove implausible terminators or other similar cleanups"),
49 cl::init(false));
50
Heejin Ahn99d60e02018-05-31 22:02:34 +000051static cl::opt<bool> DemoteCatchSwitchPHIOnlyOpt(
52 "demote-catchswitch-only", cl::Hidden,
53 cl::desc("Demote catchswitch BBs only (for wasm EH)"), cl::init(false));
54
Andrew Kaylor1476e6d2015-02-24 20:49:35 +000055namespace {
Fangrui Songf78650a2018-07-30 19:41:25 +000056
Andrew Kaylor1476e6d2015-02-24 20:49:35 +000057class WinEHPrepare : public FunctionPass {
Andrew Kaylor1476e6d2015-02-24 20:49:35 +000058public:
59 static char ID; // Pass identification, replacement for typeid.
Heejin Ahn99d60e02018-05-31 22:02:34 +000060 WinEHPrepare(bool DemoteCatchSwitchPHIOnly = false)
61 : FunctionPass(ID), DemoteCatchSwitchPHIOnly(DemoteCatchSwitchPHIOnly) {}
Andrew Kaylor1476e6d2015-02-24 20:49:35 +000062
63 bool runOnFunction(Function &Fn) override;
64
65 bool doFinalization(Module &M) override;
66
67 void getAnalysisUsage(AnalysisUsage &AU) const override;
68
Mehdi Amini117296c2016-10-01 02:56:57 +000069 StringRef getPassName() const override {
Andrew Kaylor1476e6d2015-02-24 20:49:35 +000070 return "Windows exception handling preparation";
71 }
72
73private:
Joseph Tremouletc9ff9142015-08-13 14:30:10 +000074 void insertPHIStores(PHINode *OriginalPHI, AllocaInst *SpillSlot);
75 void
76 insertPHIStore(BasicBlock *PredBlock, Value *PredVal, AllocaInst *SpillSlot,
77 SmallVectorImpl<std::pair<BasicBlock *, Value *>> &Worklist);
78 AllocaInst *insertPHILoads(PHINode *PN, Function &F);
79 void replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot,
80 DenseMap<BasicBlock *, Value *> &Loads, Function &F);
David Majnemer8a1c45d2015-12-12 05:38:55 +000081 bool prepareExplicitEH(Function &F);
David Majnemer8a1c45d2015-12-12 05:38:55 +000082 void colorFunclets(Function &F);
Andrew Kaylorfdd48fa2015-11-09 19:59:02 +000083
Heejin Ahn99d60e02018-05-31 22:02:34 +000084 void demotePHIsOnFunclets(Function &F, bool DemoteCatchSwitchPHIOnly);
David Majnemer8a1c45d2015-12-12 05:38:55 +000085 void cloneCommonBlocks(Function &F);
David Majnemer3bb88c02015-12-15 21:27:27 +000086 void removeImplausibleInstructions(Function &F);
David Majnemerb3d9b962015-09-16 18:40:24 +000087 void cleanupPreparedFunclets(Function &F);
88 void verifyPreparedFunclets(Function &F);
David Majnemerfd9f4772015-08-11 01:15:26 +000089
Heejin Ahn99d60e02018-05-31 22:02:34 +000090 bool DemoteCatchSwitchPHIOnly;
91
Reid Kleckner0f9e27a2015-03-18 20:26:53 +000092 // All fields are reset by runOnFunction.
Reid Kleckner582786b2015-04-30 18:17:12 +000093 EHPersonality Personality = EHPersonality::Unknown;
David Majnemerfd9f4772015-08-11 01:15:26 +000094
Matt Arsenault3c1fc762017-04-10 22:27:50 +000095 const DataLayout *DL = nullptr;
David Majnemer8a1c45d2015-12-12 05:38:55 +000096 DenseMap<BasicBlock *, ColorVector> BlockColors;
97 MapVector<BasicBlock *, std::vector<BasicBlock *>> FuncletBlocks;
Andrew Kaylor1476e6d2015-02-24 20:49:35 +000098};
99
Andrew Kaylor1476e6d2015-02-24 20:49:35 +0000100} // end anonymous namespace
101
102char WinEHPrepare::ID = 0;
Matthias Braun1527baa2017-05-25 21:26:32 +0000103INITIALIZE_PASS(WinEHPrepare, DEBUG_TYPE, "Prepare Windows exceptions",
Francis Visoiu Mistrih8b617642017-05-18 17:21:13 +0000104 false, false)
Andrew Kaylor1476e6d2015-02-24 20:49:35 +0000105
Heejin Ahn99d60e02018-05-31 22:02:34 +0000106FunctionPass *llvm::createWinEHPass(bool DemoteCatchSwitchPHIOnly) {
107 return new WinEHPrepare(DemoteCatchSwitchPHIOnly);
108}
Andrew Kaylor1476e6d2015-02-24 20:49:35 +0000109
Andrew Kaylor1476e6d2015-02-24 20:49:35 +0000110bool WinEHPrepare::runOnFunction(Function &Fn) {
David Majnemerfd9f4772015-08-11 01:15:26 +0000111 if (!Fn.hasPersonalityFn())
Andrew Kaylor1476e6d2015-02-24 20:49:35 +0000112 return false;
113
114 // Classify the personality to see what kind of preparation we need.
David Majnemer7fddecc2015-06-17 20:52:32 +0000115 Personality = classifyEHPersonality(Fn.getPersonalityFn());
Andrew Kaylor1476e6d2015-02-24 20:49:35 +0000116
Heejin Ahnb4be38f2018-05-17 20:52:03 +0000117 // Do nothing if this is not a scope-based personality.
118 if (!isScopedEHPersonality(Personality))
Reid Kleckner47c8e7a2015-03-12 00:36:20 +0000119 return false;
Andrew Kaylor1476e6d2015-02-24 20:49:35 +0000120
Matt Arsenault3c1fc762017-04-10 22:27:50 +0000121 DL = &Fn.getParent()->getDataLayout();
David Majnemer8a1c45d2015-12-12 05:38:55 +0000122 return prepareExplicitEH(Fn);
Andrew Kaylor1476e6d2015-02-24 20:49:35 +0000123}
124
Andrew Kayloraa92ab02015-04-03 19:37:50 +0000125bool WinEHPrepare::doFinalization(Module &M) { return false; }
Andrew Kaylor1476e6d2015-02-24 20:49:35 +0000126
David Majnemere6965832015-10-16 19:59:52 +0000127void WinEHPrepare::getAnalysisUsage(AnalysisUsage &AU) const {}
Andrew Kaylor1476e6d2015-02-24 20:49:35 +0000128
David Majnemer0ad363e2015-08-18 19:07:12 +0000129static int addUnwindMapEntry(WinEHFuncInfo &FuncInfo, int ToState,
David Majnemerbfa5b982015-10-10 00:04:29 +0000130 const BasicBlock *BB) {
Reid Kleckner14e77352015-10-09 23:34:53 +0000131 CxxUnwindMapEntry UME;
Reid Klecknerfe4d4912015-05-28 22:00:24 +0000132 UME.ToState = ToState;
David Majnemerbfa5b982015-10-10 00:04:29 +0000133 UME.Cleanup = BB;
Reid Kleckner14e77352015-10-09 23:34:53 +0000134 FuncInfo.CxxUnwindMap.push_back(UME);
David Majnemer0ad363e2015-08-18 19:07:12 +0000135 return FuncInfo.getLastStateNumber();
136}
137
138static void addTryBlockMapEntry(WinEHFuncInfo &FuncInfo, int TryLow,
139 int TryHigh, int CatchHigh,
140 ArrayRef<const CatchPadInst *> Handlers) {
141 WinEHTryBlockMapEntry TBME;
142 TBME.TryLow = TryLow;
143 TBME.TryHigh = TryHigh;
144 TBME.CatchHigh = CatchHigh;
145 assert(TBME.TryLow <= TBME.TryHigh);
146 for (const CatchPadInst *CPI : Handlers) {
147 WinEHHandlerType HT;
148 Constant *TypeInfo = cast<Constant>(CPI->getArgOperand(0));
Reid Klecknerb005d282015-09-16 20:16:27 +0000149 if (TypeInfo->isNullValue())
David Majnemer0ad363e2015-08-18 19:07:12 +0000150 HT.TypeDescriptor = nullptr;
Reid Klecknerb005d282015-09-16 20:16:27 +0000151 else
152 HT.TypeDescriptor = cast<GlobalVariable>(TypeInfo->stripPointerCasts());
153 HT.Adjectives = cast<ConstantInt>(CPI->getArgOperand(1))->getZExtValue();
David Majnemer7735a6d2015-10-06 23:31:59 +0000154 HT.Handler = CPI->getParent();
David Majnemer086fec22016-01-08 08:03:55 +0000155 if (auto *AI =
156 dyn_cast<AllocaInst>(CPI->getArgOperand(2)->stripPointerCasts()))
157 HT.CatchObj.Alloca = AI;
Reid Klecknerb005d282015-09-16 20:16:27 +0000158 else
David Majnemer086fec22016-01-08 08:03:55 +0000159 HT.CatchObj.Alloca = nullptr;
David Majnemer0ad363e2015-08-18 19:07:12 +0000160 TBME.HandlerArray.push_back(HT);
161 }
162 FuncInfo.TryBlockMap.push_back(TBME);
163}
164
David Majnemer8a1c45d2015-12-12 05:38:55 +0000165static BasicBlock *getCleanupRetUnwindDest(const CleanupPadInst *CleanupPad) {
166 for (const User *U : CleanupPad->users())
167 if (const auto *CRI = dyn_cast<CleanupReturnInst>(U))
168 return CRI->getUnwindDest();
David Majnemer0ad363e2015-08-18 19:07:12 +0000169 return nullptr;
170}
171
David Majnemer8a1c45d2015-12-12 05:38:55 +0000172static void calculateStateNumbersForInvokes(const Function *Fn,
173 WinEHFuncInfo &FuncInfo) {
174 auto *F = const_cast<Function *>(Fn);
175 DenseMap<BasicBlock *, ColorVector> BlockColors = colorEHFunclets(*F);
176 for (BasicBlock &BB : *F) {
177 auto *II = dyn_cast<InvokeInst>(BB.getTerminator());
178 if (!II)
179 continue;
180
181 auto &BBColors = BlockColors[&BB];
David Majnemerc640f862015-12-23 03:59:04 +0000182 assert(BBColors.size() == 1 && "multi-color BB not removed by preparation");
David Majnemer8a1c45d2015-12-12 05:38:55 +0000183 BasicBlock *FuncletEntryBB = BBColors.front();
184
185 BasicBlock *FuncletUnwindDest;
186 auto *FuncletPad =
187 dyn_cast<FuncletPadInst>(FuncletEntryBB->getFirstNonPHI());
188 assert(FuncletPad || FuncletEntryBB == &Fn->getEntryBlock());
189 if (!FuncletPad)
190 FuncletUnwindDest = nullptr;
191 else if (auto *CatchPad = dyn_cast<CatchPadInst>(FuncletPad))
192 FuncletUnwindDest = CatchPad->getCatchSwitch()->getUnwindDest();
193 else if (auto *CleanupPad = dyn_cast<CleanupPadInst>(FuncletPad))
194 FuncletUnwindDest = getCleanupRetUnwindDest(CleanupPad);
195 else
196 llvm_unreachable("unexpected funclet pad!");
197
198 BasicBlock *InvokeUnwindDest = II->getUnwindDest();
199 int BaseState = -1;
200 if (FuncletUnwindDest == InvokeUnwindDest) {
201 auto BaseStateI = FuncInfo.FuncletBaseStateMap.find(FuncletPad);
202 if (BaseStateI != FuncInfo.FuncletBaseStateMap.end())
203 BaseState = BaseStateI->second;
204 }
205
206 if (BaseState != -1) {
207 FuncInfo.InvokeStateMap[II] = BaseState;
208 } else {
209 Instruction *PadInst = InvokeUnwindDest->getFirstNonPHI();
210 assert(FuncInfo.EHPadStateMap.count(PadInst) && "EH Pad has no state!");
211 FuncInfo.InvokeStateMap[II] = FuncInfo.EHPadStateMap[PadInst];
212 }
Reid Kleckner94b704c2015-09-09 21:10:03 +0000213 }
Reid Kleckner94b704c2015-09-09 21:10:03 +0000214}
215
David Majnemer0ad363e2015-08-18 19:07:12 +0000216// Given BB which ends in an unwind edge, return the EHPad that this BB belongs
217// to. If the unwind edge came from an invoke, return null.
David Majnemer8a1c45d2015-12-12 05:38:55 +0000218static const BasicBlock *getEHPadFromPredecessor(const BasicBlock *BB,
219 Value *ParentPad) {
Chandler Carruthedb12a82018-10-15 10:04:59 +0000220 const Instruction *TI = BB->getTerminator();
David Majnemer0ad363e2015-08-18 19:07:12 +0000221 if (isa<InvokeInst>(TI))
222 return nullptr;
David Majnemer8a1c45d2015-12-12 05:38:55 +0000223 if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) {
224 if (CatchSwitch->getParentPad() != ParentPad)
225 return nullptr;
David Majnemer0ad363e2015-08-18 19:07:12 +0000226 return BB;
David Majnemer8a1c45d2015-12-12 05:38:55 +0000227 }
228 assert(!TI->isEHPad() && "unexpected EHPad!");
229 auto *CleanupPad = cast<CleanupReturnInst>(TI)->getCleanupPad();
230 if (CleanupPad->getParentPad() != ParentPad)
231 return nullptr;
232 return CleanupPad->getParent();
David Majnemer0ad363e2015-08-18 19:07:12 +0000233}
234
David Majnemer8a1c45d2015-12-12 05:38:55 +0000235static void calculateCXXStateNumbers(WinEHFuncInfo &FuncInfo,
236 const Instruction *FirstNonPHI,
237 int ParentState) {
238 const BasicBlock *BB = FirstNonPHI->getParent();
239 assert(BB->isEHPad() && "not a funclet!");
David Majnemer0ad363e2015-08-18 19:07:12 +0000240
David Majnemer8a1c45d2015-12-12 05:38:55 +0000241 if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(FirstNonPHI)) {
242 assert(FuncInfo.EHPadStateMap.count(CatchSwitch) == 0 &&
243 "shouldn't revist catch funclets!");
244
David Majnemer0ad363e2015-08-18 19:07:12 +0000245 SmallVector<const CatchPadInst *, 2> Handlers;
David Majnemer8a1c45d2015-12-12 05:38:55 +0000246 for (const BasicBlock *CatchPadBB : CatchSwitch->handlers()) {
247 auto *CatchPad = cast<CatchPadInst>(CatchPadBB->getFirstNonPHI());
248 Handlers.push_back(CatchPad);
249 }
David Majnemer0ad363e2015-08-18 19:07:12 +0000250 int TryLow = addUnwindMapEntry(FuncInfo, ParentState, nullptr);
David Majnemer8a1c45d2015-12-12 05:38:55 +0000251 FuncInfo.EHPadStateMap[CatchSwitch] = TryLow;
252 for (const BasicBlock *PredBlock : predecessors(BB))
253 if ((PredBlock = getEHPadFromPredecessor(PredBlock,
254 CatchSwitch->getParentPad())))
255 calculateCXXStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
256 TryLow);
David Majnemer0ad363e2015-08-18 19:07:12 +0000257 int CatchLow = addUnwindMapEntry(FuncInfo, ParentState, nullptr);
Reid Kleckner94b704c2015-09-09 21:10:03 +0000258
259 // catchpads are separate funclets in C++ EH due to the way rethrow works.
David Majnemer0ad363e2015-08-18 19:07:12 +0000260 int TryHigh = CatchLow - 1;
David Majnemer8a1c45d2015-12-12 05:38:55 +0000261 for (const auto *CatchPad : Handlers) {
262 FuncInfo.FuncletBaseStateMap[CatchPad] = CatchLow;
263 for (const User *U : CatchPad->users()) {
264 const auto *UserI = cast<Instruction>(U);
David Majnemer17525ab2016-02-23 07:18:15 +0000265 if (auto *InnerCatchSwitch = dyn_cast<CatchSwitchInst>(UserI)) {
266 BasicBlock *UnwindDest = InnerCatchSwitch->getUnwindDest();
267 if (!UnwindDest || UnwindDest == CatchSwitch->getUnwindDest())
David Majnemerc640f862015-12-23 03:59:04 +0000268 calculateCXXStateNumbers(FuncInfo, UserI, CatchLow);
David Majnemer17525ab2016-02-23 07:18:15 +0000269 }
Andrew Kaylord1188dd2016-02-12 21:10:16 +0000270 if (auto *InnerCleanupPad = dyn_cast<CleanupPadInst>(UserI)) {
271 BasicBlock *UnwindDest = getCleanupRetUnwindDest(InnerCleanupPad);
272 // If a nested cleanup pad reports a null unwind destination and the
273 // enclosing catch pad doesn't it must be post-dominated by an
274 // unreachable instruction.
275 if (!UnwindDest || UnwindDest == CatchSwitch->getUnwindDest())
David Majnemerc640f862015-12-23 03:59:04 +0000276 calculateCXXStateNumbers(FuncInfo, UserI, CatchLow);
Andrew Kaylord1188dd2016-02-12 21:10:16 +0000277 }
David Majnemer8a1c45d2015-12-12 05:38:55 +0000278 }
279 }
David Majnemer0ad363e2015-08-18 19:07:12 +0000280 int CatchHigh = FuncInfo.getLastStateNumber();
281 addTryBlockMapEntry(FuncInfo, TryLow, TryHigh, CatchHigh, Handlers);
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000282 LLVM_DEBUG(dbgs() << "TryLow[" << BB->getName() << "]: " << TryLow << '\n');
283 LLVM_DEBUG(dbgs() << "TryHigh[" << BB->getName() << "]: " << TryHigh
284 << '\n');
285 LLVM_DEBUG(dbgs() << "CatchHigh[" << BB->getName() << "]: " << CatchHigh
286 << '\n');
David Majnemer0ad363e2015-08-18 19:07:12 +0000287 } else {
David Majnemer8a1c45d2015-12-12 05:38:55 +0000288 auto *CleanupPad = cast<CleanupPadInst>(FirstNonPHI);
289
290 // It's possible for a cleanup to be visited twice: it might have multiple
291 // cleanupret instructions.
292 if (FuncInfo.EHPadStateMap.count(CleanupPad))
293 return;
294
295 int CleanupState = addUnwindMapEntry(FuncInfo, ParentState, BB);
296 FuncInfo.EHPadStateMap[CleanupPad] = CleanupState;
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000297 LLVM_DEBUG(dbgs() << "Assigning state #" << CleanupState << " to BB "
298 << BB->getName() << '\n');
David Majnemer8a1c45d2015-12-12 05:38:55 +0000299 for (const BasicBlock *PredBlock : predecessors(BB)) {
300 if ((PredBlock = getEHPadFromPredecessor(PredBlock,
301 CleanupPad->getParentPad()))) {
302 calculateCXXStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
303 CleanupState);
304 }
305 }
306 for (const User *U : CleanupPad->users()) {
307 const auto *UserI = cast<Instruction>(U);
308 if (UserI->isEHPad())
309 report_fatal_error("Cleanup funclets for the MSVC++ personality cannot "
310 "contain exceptional actions");
311 }
David Majnemer0ad363e2015-08-18 19:07:12 +0000312 }
313}
314
Reid Klecknerfc64fae2015-10-01 21:38:24 +0000315static int addSEHExcept(WinEHFuncInfo &FuncInfo, int ParentState,
316 const Function *Filter, const BasicBlock *Handler) {
Reid Kleckner94b704c2015-09-09 21:10:03 +0000317 SEHUnwindMapEntry Entry;
318 Entry.ToState = ParentState;
Reid Klecknerfc64fae2015-10-01 21:38:24 +0000319 Entry.IsFinally = false;
Reid Kleckner94b704c2015-09-09 21:10:03 +0000320 Entry.Filter = Filter;
321 Entry.Handler = Handler;
322 FuncInfo.SEHUnwindMap.push_back(Entry);
323 return FuncInfo.SEHUnwindMap.size() - 1;
324}
325
Reid Klecknerfc64fae2015-10-01 21:38:24 +0000326static int addSEHFinally(WinEHFuncInfo &FuncInfo, int ParentState,
327 const BasicBlock *Handler) {
328 SEHUnwindMapEntry Entry;
329 Entry.ToState = ParentState;
330 Entry.IsFinally = true;
331 Entry.Filter = nullptr;
332 Entry.Handler = Handler;
333 FuncInfo.SEHUnwindMap.push_back(Entry);
334 return FuncInfo.SEHUnwindMap.size() - 1;
335}
336
David Majnemer8a1c45d2015-12-12 05:38:55 +0000337static void calculateSEHStateNumbers(WinEHFuncInfo &FuncInfo,
338 const Instruction *FirstNonPHI,
339 int ParentState) {
340 const BasicBlock *BB = FirstNonPHI->getParent();
341 assert(BB->isEHPad() && "no a funclet!");
Reid Kleckner94b704c2015-09-09 21:10:03 +0000342
David Majnemer8a1c45d2015-12-12 05:38:55 +0000343 if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(FirstNonPHI)) {
344 assert(FuncInfo.EHPadStateMap.count(CatchSwitch) == 0 &&
345 "shouldn't revist catch funclets!");
346
Reid Kleckner94b704c2015-09-09 21:10:03 +0000347 // Extract the filter function and the __except basic block and create a
348 // state for them.
David Majnemer8a1c45d2015-12-12 05:38:55 +0000349 assert(CatchSwitch->getNumHandlers() == 1 &&
Reid Kleckner94b704c2015-09-09 21:10:03 +0000350 "SEH doesn't have multiple handlers per __try");
David Majnemer8a1c45d2015-12-12 05:38:55 +0000351 const auto *CatchPad =
352 cast<CatchPadInst>((*CatchSwitch->handler_begin())->getFirstNonPHI());
353 const BasicBlock *CatchPadBB = CatchPad->getParent();
Reid Klecknerfc64fae2015-10-01 21:38:24 +0000354 const Constant *FilterOrNull =
David Majnemer8a1c45d2015-12-12 05:38:55 +0000355 cast<Constant>(CatchPad->getArgOperand(0)->stripPointerCasts());
Reid Klecknerfc64fae2015-10-01 21:38:24 +0000356 const Function *Filter = dyn_cast<Function>(FilterOrNull);
357 assert((Filter || FilterOrNull->isNullValue()) &&
358 "unexpected filter value");
David Majnemer7735a6d2015-10-06 23:31:59 +0000359 int TryState = addSEHExcept(FuncInfo, ParentState, Filter, CatchPadBB);
Reid Kleckner94b704c2015-09-09 21:10:03 +0000360
361 // Everything in the __try block uses TryState as its parent state.
David Majnemer8a1c45d2015-12-12 05:38:55 +0000362 FuncInfo.EHPadStateMap[CatchSwitch] = TryState;
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000363 LLVM_DEBUG(dbgs() << "Assigning state #" << TryState << " to BB "
364 << CatchPadBB->getName() << '\n');
David Majnemer8a1c45d2015-12-12 05:38:55 +0000365 for (const BasicBlock *PredBlock : predecessors(BB))
366 if ((PredBlock = getEHPadFromPredecessor(PredBlock,
367 CatchSwitch->getParentPad())))
368 calculateSEHStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
369 TryState);
Reid Kleckner94b704c2015-09-09 21:10:03 +0000370
371 // Everything in the __except block unwinds to ParentState, just like code
372 // outside the __try.
David Majnemer8a1c45d2015-12-12 05:38:55 +0000373 for (const User *U : CatchPad->users()) {
374 const auto *UserI = cast<Instruction>(U);
David Majnemer17525ab2016-02-23 07:18:15 +0000375 if (auto *InnerCatchSwitch = dyn_cast<CatchSwitchInst>(UserI)) {
376 BasicBlock *UnwindDest = InnerCatchSwitch->getUnwindDest();
377 if (!UnwindDest || UnwindDest == CatchSwitch->getUnwindDest())
David Majnemerc640f862015-12-23 03:59:04 +0000378 calculateSEHStateNumbers(FuncInfo, UserI, ParentState);
David Majnemer17525ab2016-02-23 07:18:15 +0000379 }
Andrew Kaylord1188dd2016-02-12 21:10:16 +0000380 if (auto *InnerCleanupPad = dyn_cast<CleanupPadInst>(UserI)) {
381 BasicBlock *UnwindDest = getCleanupRetUnwindDest(InnerCleanupPad);
382 // If a nested cleanup pad reports a null unwind destination and the
383 // enclosing catch pad doesn't it must be post-dominated by an
384 // unreachable instruction.
385 if (!UnwindDest || UnwindDest == CatchSwitch->getUnwindDest())
David Majnemerc640f862015-12-23 03:59:04 +0000386 calculateSEHStateNumbers(FuncInfo, UserI, ParentState);
Andrew Kaylord1188dd2016-02-12 21:10:16 +0000387 }
David Majnemer8a1c45d2015-12-12 05:38:55 +0000388 }
Reid Kleckner94b704c2015-09-09 21:10:03 +0000389 } else {
David Majnemer8a1c45d2015-12-12 05:38:55 +0000390 auto *CleanupPad = cast<CleanupPadInst>(FirstNonPHI);
391
392 // It's possible for a cleanup to be visited twice: it might have multiple
393 // cleanupret instructions.
394 if (FuncInfo.EHPadStateMap.count(CleanupPad))
395 return;
396
397 int CleanupState = addSEHFinally(FuncInfo, ParentState, BB);
398 FuncInfo.EHPadStateMap[CleanupPad] = CleanupState;
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000399 LLVM_DEBUG(dbgs() << "Assigning state #" << CleanupState << " to BB "
400 << BB->getName() << '\n');
David Majnemer8a1c45d2015-12-12 05:38:55 +0000401 for (const BasicBlock *PredBlock : predecessors(BB))
402 if ((PredBlock =
403 getEHPadFromPredecessor(PredBlock, CleanupPad->getParentPad())))
404 calculateSEHStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
405 CleanupState);
406 for (const User *U : CleanupPad->users()) {
407 const auto *UserI = cast<Instruction>(U);
408 if (UserI->isEHPad())
409 report_fatal_error("Cleanup funclets for the SEH personality cannot "
410 "contain exceptional actions");
411 }
Reid Kleckner94b704c2015-09-09 21:10:03 +0000412 }
413}
414
David Majnemer8a1c45d2015-12-12 05:38:55 +0000415static bool isTopLevelPadForMSVC(const Instruction *EHPad) {
416 if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(EHPad))
417 return isa<ConstantTokenNone>(CatchSwitch->getParentPad()) &&
418 CatchSwitch->unwindsToCaller();
419 if (auto *CleanupPad = dyn_cast<CleanupPadInst>(EHPad))
420 return isa<ConstantTokenNone>(CleanupPad->getParentPad()) &&
421 getCleanupRetUnwindDest(CleanupPad) == nullptr;
422 if (isa<CatchPadInst>(EHPad))
423 return false;
424 llvm_unreachable("unexpected EHPad!");
Reid Kleckner94b704c2015-09-09 21:10:03 +0000425}
426
Reid Kleckner813f1b62015-09-16 22:14:46 +0000427void llvm::calculateSEHStateNumbers(const Function *Fn,
Reid Kleckner94b704c2015-09-09 21:10:03 +0000428 WinEHFuncInfo &FuncInfo) {
429 // Don't compute state numbers twice.
430 if (!FuncInfo.SEHUnwindMap.empty())
431 return;
432
Reid Kleckner813f1b62015-09-16 22:14:46 +0000433 for (const BasicBlock &BB : *Fn) {
David Majnemer8a1c45d2015-12-12 05:38:55 +0000434 if (!BB.isEHPad())
Reid Kleckner94b704c2015-09-09 21:10:03 +0000435 continue;
David Majnemer8a1c45d2015-12-12 05:38:55 +0000436 const Instruction *FirstNonPHI = BB.getFirstNonPHI();
437 if (!isTopLevelPadForMSVC(FirstNonPHI))
438 continue;
439 ::calculateSEHStateNumbers(FuncInfo, FirstNonPHI, -1);
Reid Kleckner94b704c2015-09-09 21:10:03 +0000440 }
David Majnemer8a1c45d2015-12-12 05:38:55 +0000441
442 calculateStateNumbersForInvokes(Fn, FuncInfo);
Reid Kleckner94b704c2015-09-09 21:10:03 +0000443}
444
Reid Kleckner813f1b62015-09-16 22:14:46 +0000445void llvm::calculateWinCXXEHStateNumbers(const Function *Fn,
Reid Klecknerfe4d4912015-05-28 22:00:24 +0000446 WinEHFuncInfo &FuncInfo) {
447 // Return if it's already been done.
David Majnemer0ad363e2015-08-18 19:07:12 +0000448 if (!FuncInfo.EHPadStateMap.empty())
449 return;
450
Reid Kleckner813f1b62015-09-16 22:14:46 +0000451 for (const BasicBlock &BB : *Fn) {
David Majnemer0ad363e2015-08-18 19:07:12 +0000452 if (!BB.isEHPad())
453 continue;
Joseph Tremoulet9ce71f72015-09-03 09:09:43 +0000454 const Instruction *FirstNonPHI = BB.getFirstNonPHI();
David Majnemer8a1c45d2015-12-12 05:38:55 +0000455 if (!isTopLevelPadForMSVC(FirstNonPHI))
David Majnemer0ad363e2015-08-18 19:07:12 +0000456 continue;
David Majnemer8a1c45d2015-12-12 05:38:55 +0000457 calculateCXXStateNumbers(FuncInfo, FirstNonPHI, -1);
David Majnemer0ad363e2015-08-18 19:07:12 +0000458 }
David Majnemer8a1c45d2015-12-12 05:38:55 +0000459
460 calculateStateNumbersForInvokes(Fn, FuncInfo);
Reid Klecknerfe4d4912015-05-28 22:00:24 +0000461}
David Majnemerfd9f4772015-08-11 01:15:26 +0000462
Joseph Tremoulet52f729a2016-01-04 16:16:01 +0000463static int addClrEHHandler(WinEHFuncInfo &FuncInfo, int HandlerParentState,
464 int TryParentState, ClrHandlerType HandlerType,
465 uint32_t TypeToken, const BasicBlock *Handler) {
Joseph Tremoulet7f8c1162015-10-06 20:30:33 +0000466 ClrEHUnwindMapEntry Entry;
Joseph Tremoulet52f729a2016-01-04 16:16:01 +0000467 Entry.HandlerParentState = HandlerParentState;
468 Entry.TryParentState = TryParentState;
Joseph Tremoulet7f8c1162015-10-06 20:30:33 +0000469 Entry.Handler = Handler;
470 Entry.HandlerType = HandlerType;
471 Entry.TypeToken = TypeToken;
472 FuncInfo.ClrEHUnwindMap.push_back(Entry);
473 return FuncInfo.ClrEHUnwindMap.size() - 1;
474}
475
476void llvm::calculateClrEHStateNumbers(const Function *Fn,
477 WinEHFuncInfo &FuncInfo) {
478 // Return if it's already been done.
479 if (!FuncInfo.EHPadStateMap.empty())
480 return;
481
Joseph Tremoulet52f729a2016-01-04 16:16:01 +0000482 // This numbering assigns one state number to each catchpad and cleanuppad.
483 // It also computes two tree-like relations over states:
484 // 1) Each state has a "HandlerParentState", which is the state of the next
485 // outer handler enclosing this state's handler (same as nearest ancestor
486 // per the ParentPad linkage on EH pads, but skipping over catchswitches).
487 // 2) Each state has a "TryParentState", which:
488 // a) for a catchpad that's not the last handler on its catchswitch, is
489 // the state of the next catchpad on that catchswitch
490 // b) for all other pads, is the state of the pad whose try region is the
491 // next outer try region enclosing this state's try region. The "try
492 // regions are not present as such in the IR, but will be inferred
493 // based on the placement of invokes and pads which reach each other
494 // by exceptional exits
495 // Catchswitches do not get their own states, but each gets mapped to the
496 // state of its first catchpad.
Joseph Tremoulet7f8c1162015-10-06 20:30:33 +0000497
Joseph Tremoulet52f729a2016-01-04 16:16:01 +0000498 // Step one: walk down from outermost to innermost funclets, assigning each
499 // catchpad and cleanuppad a state number. Add an entry to the
500 // ClrEHUnwindMap for each state, recording its HandlerParentState and
501 // handler attributes. Record the TryParentState as well for each catchpad
502 // that's not the last on its catchswitch, but initialize all other entries'
503 // TryParentStates to a sentinel -1 value that the next pass will update.
504
505 // Seed a worklist with pads that have no parent.
506 SmallVector<std::pair<const Instruction *, int>, 8> Worklist;
Joseph Tremoulet7f8c1162015-10-06 20:30:33 +0000507 for (const BasicBlock &BB : *Fn) {
Joseph Tremoulet7f8c1162015-10-06 20:30:33 +0000508 const Instruction *FirstNonPHI = BB.getFirstNonPHI();
Joseph Tremoulet52f729a2016-01-04 16:16:01 +0000509 const Value *ParentPad;
510 if (const auto *CPI = dyn_cast<CleanupPadInst>(FirstNonPHI))
511 ParentPad = CPI->getParentPad();
512 else if (const auto *CSI = dyn_cast<CatchSwitchInst>(FirstNonPHI))
513 ParentPad = CSI->getParentPad();
514 else
Joseph Tremoulet7f8c1162015-10-06 20:30:33 +0000515 continue;
Joseph Tremoulet52f729a2016-01-04 16:16:01 +0000516 if (isa<ConstantTokenNone>(ParentPad))
517 Worklist.emplace_back(FirstNonPHI, -1);
Joseph Tremoulet7f8c1162015-10-06 20:30:33 +0000518 }
519
Joseph Tremoulet52f729a2016-01-04 16:16:01 +0000520 // Use the worklist to visit all pads, from outer to inner. Record
521 // HandlerParentState for all pads. Record TryParentState only for catchpads
522 // that aren't the last on their catchswitch (setting all other entries'
523 // TryParentStates to an initial value of -1). This loop is also responsible
524 // for setting the EHPadStateMap entry for all catchpads, cleanuppads, and
525 // catchswitches.
Joseph Tremoulet7f8c1162015-10-06 20:30:33 +0000526 while (!Worklist.empty()) {
527 const Instruction *Pad;
Joseph Tremoulet52f729a2016-01-04 16:16:01 +0000528 int HandlerParentState;
529 std::tie(Pad, HandlerParentState) = Worklist.pop_back_val();
Joseph Tremoulet7f8c1162015-10-06 20:30:33 +0000530
Joseph Tremoulet52f729a2016-01-04 16:16:01 +0000531 if (const auto *Cleanup = dyn_cast<CleanupPadInst>(Pad)) {
532 // Create the entry for this cleanup with the appropriate handler
Simon Pilgrimf2fbf432016-11-20 13:47:59 +0000533 // properties. Finally and fault handlers are distinguished by arity.
Joseph Tremoulet7f8c1162015-10-06 20:30:33 +0000534 ClrHandlerType HandlerType =
Joseph Tremoulet52f729a2016-01-04 16:16:01 +0000535 (Cleanup->getNumArgOperands() ? ClrHandlerType::Fault
536 : ClrHandlerType::Finally);
537 int CleanupState = addClrEHHandler(FuncInfo, HandlerParentState, -1,
538 HandlerType, 0, Pad->getParent());
539 // Queue any child EH pads on the worklist.
540 for (const User *U : Cleanup->users())
541 if (const auto *I = dyn_cast<Instruction>(U))
542 if (I->isEHPad())
543 Worklist.emplace_back(I, CleanupState);
544 // Remember this pad's state.
545 FuncInfo.EHPadStateMap[Cleanup] = CleanupState;
546 } else {
547 // Walk the handlers of this catchswitch in reverse order since all but
548 // the last need to set the following one as its TryParentState.
549 const auto *CatchSwitch = cast<CatchSwitchInst>(Pad);
550 int CatchState = -1, FollowerState = -1;
551 SmallVector<const BasicBlock *, 4> CatchBlocks(CatchSwitch->handlers());
552 for (auto CBI = CatchBlocks.rbegin(), CBE = CatchBlocks.rend();
553 CBI != CBE; ++CBI, FollowerState = CatchState) {
554 const BasicBlock *CatchBlock = *CBI;
555 // Create the entry for this catch with the appropriate handler
556 // properties.
557 const auto *Catch = cast<CatchPadInst>(CatchBlock->getFirstNonPHI());
David Majnemer8a1c45d2015-12-12 05:38:55 +0000558 uint32_t TypeToken = static_cast<uint32_t>(
559 cast<ConstantInt>(Catch->getArgOperand(0))->getZExtValue());
Joseph Tremoulet52f729a2016-01-04 16:16:01 +0000560 CatchState =
561 addClrEHHandler(FuncInfo, HandlerParentState, FollowerState,
562 ClrHandlerType::Catch, TypeToken, CatchBlock);
563 // Queue any child EH pads on the worklist.
564 for (const User *U : Catch->users())
565 if (const auto *I = dyn_cast<Instruction>(U))
566 if (I->isEHPad())
567 Worklist.emplace_back(I, CatchState);
568 // Remember this catch's state.
569 FuncInfo.EHPadStateMap[Catch] = CatchState;
David Majnemer8a1c45d2015-12-12 05:38:55 +0000570 }
Joseph Tremoulet52f729a2016-01-04 16:16:01 +0000571 // Associate the catchswitch with the state of its first catch.
572 assert(CatchSwitch->getNumHandlers());
573 FuncInfo.EHPadStateMap[CatchSwitch] = CatchState;
Joseph Tremoulet7f8c1162015-10-06 20:30:33 +0000574 }
575 }
David Majnemer8a1c45d2015-12-12 05:38:55 +0000576
Joseph Tremoulet52f729a2016-01-04 16:16:01 +0000577 // Step two: record the TryParentState of each state. For cleanuppads that
578 // don't have cleanuprets, we may need to infer this from their child pads,
579 // so visit pads in descendant-most to ancestor-most order.
580 for (auto Entry = FuncInfo.ClrEHUnwindMap.rbegin(),
581 End = FuncInfo.ClrEHUnwindMap.rend();
582 Entry != End; ++Entry) {
583 const Instruction *Pad =
584 Entry->Handler.get<const BasicBlock *>()->getFirstNonPHI();
585 // For most pads, the TryParentState is the state associated with the
586 // unwind dest of exceptional exits from it.
587 const BasicBlock *UnwindDest;
588 if (const auto *Catch = dyn_cast<CatchPadInst>(Pad)) {
589 // If a catch is not the last in its catchswitch, its TryParentState is
590 // the state associated with the next catch in the switch, even though
591 // that's not the unwind dest of exceptions escaping the catch. Those
592 // cases were already assigned a TryParentState in the first pass, so
593 // skip them.
594 if (Entry->TryParentState != -1)
595 continue;
596 // Otherwise, get the unwind dest from the catchswitch.
597 UnwindDest = Catch->getCatchSwitch()->getUnwindDest();
598 } else {
599 const auto *Cleanup = cast<CleanupPadInst>(Pad);
600 UnwindDest = nullptr;
601 for (const User *U : Cleanup->users()) {
602 if (auto *CleanupRet = dyn_cast<CleanupReturnInst>(U)) {
603 // Common and unambiguous case -- cleanupret indicates cleanup's
604 // unwind dest.
605 UnwindDest = CleanupRet->getUnwindDest();
606 break;
607 }
608
609 // Get an unwind dest for the user
610 const BasicBlock *UserUnwindDest = nullptr;
611 if (auto *Invoke = dyn_cast<InvokeInst>(U)) {
612 UserUnwindDest = Invoke->getUnwindDest();
613 } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(U)) {
614 UserUnwindDest = CatchSwitch->getUnwindDest();
615 } else if (auto *ChildCleanup = dyn_cast<CleanupPadInst>(U)) {
616 int UserState = FuncInfo.EHPadStateMap[ChildCleanup];
617 int UserUnwindState =
618 FuncInfo.ClrEHUnwindMap[UserState].TryParentState;
619 if (UserUnwindState != -1)
620 UserUnwindDest = FuncInfo.ClrEHUnwindMap[UserUnwindState]
621 .Handler.get<const BasicBlock *>();
622 }
623
624 // Not having an unwind dest for this user might indicate that it
625 // doesn't unwind, so can't be taken as proof that the cleanup itself
626 // may unwind to caller (see e.g. SimplifyUnreachable and
627 // RemoveUnwindEdge).
628 if (!UserUnwindDest)
629 continue;
630
631 // Now we have an unwind dest for the user, but we need to see if it
632 // unwinds all the way out of the cleanup or if it stays within it.
633 const Instruction *UserUnwindPad = UserUnwindDest->getFirstNonPHI();
634 const Value *UserUnwindParent;
635 if (auto *CSI = dyn_cast<CatchSwitchInst>(UserUnwindPad))
636 UserUnwindParent = CSI->getParentPad();
637 else
638 UserUnwindParent =
639 cast<CleanupPadInst>(UserUnwindPad)->getParentPad();
640
641 // The unwind stays within the cleanup iff it targets a child of the
642 // cleanup.
643 if (UserUnwindParent == Cleanup)
644 continue;
645
646 // This unwind exits the cleanup, so its dest is the cleanup's dest.
647 UnwindDest = UserUnwindDest;
648 break;
649 }
650 }
651
652 // Record the state of the unwind dest as the TryParentState.
653 int UnwindDestState;
654
655 // If UnwindDest is null at this point, either the pad in question can
656 // be exited by unwind to caller, or it cannot be exited by unwind. In
657 // either case, reporting such cases as unwinding to caller is correct.
658 // This can lead to EH tables that "look strange" -- if this pad's is in
659 // a parent funclet which has other children that do unwind to an enclosing
660 // pad, the try region for this pad will be missing the "duplicate" EH
661 // clause entries that you'd expect to see covering the whole parent. That
662 // should be benign, since the unwind never actually happens. If it were
663 // an issue, we could add a subsequent pass that pushes unwind dests down
664 // from parents that have them to children that appear to unwind to caller.
665 if (!UnwindDest) {
666 UnwindDestState = -1;
667 } else {
668 UnwindDestState = FuncInfo.EHPadStateMap[UnwindDest->getFirstNonPHI()];
669 }
670
671 Entry->TryParentState = UnwindDestState;
672 }
673
674 // Step three: transfer information from pads to invokes.
David Majnemer8a1c45d2015-12-12 05:38:55 +0000675 calculateStateNumbersForInvokes(Fn, FuncInfo);
Joseph Tremoulet7f8c1162015-10-06 20:30:33 +0000676}
677
David Majnemer8a1c45d2015-12-12 05:38:55 +0000678void WinEHPrepare::colorFunclets(Function &F) {
679 BlockColors = colorEHFunclets(F);
David Majnemerfd9f4772015-08-11 01:15:26 +0000680
David Majnemer8a1c45d2015-12-12 05:38:55 +0000681 // Invert the map from BB to colors to color to BBs.
682 for (BasicBlock &BB : F) {
683 ColorVector &Colors = BlockColors[&BB];
684 for (BasicBlock *Color : Colors)
685 FuncletBlocks[Color].push_back(&BB);
David Majnemerfd9f4772015-08-11 01:15:26 +0000686 }
687}
688
Heejin Ahn99d60e02018-05-31 22:02:34 +0000689void WinEHPrepare::demotePHIsOnFunclets(Function &F,
690 bool DemoteCatchSwitchPHIOnly) {
Joseph Tremouletc9ff9142015-08-13 14:30:10 +0000691 // Strip PHI nodes off of EH pads.
692 SmallVector<PHINode *, 16> PHINodes;
David Majnemerfd9f4772015-08-11 01:15:26 +0000693 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
Duncan P. N. Exon Smithf1ff53e2015-10-09 22:56:24 +0000694 BasicBlock *BB = &*FI++;
David Majnemerfd9f4772015-08-11 01:15:26 +0000695 if (!BB->isEHPad())
696 continue;
Heejin Ahn99d60e02018-05-31 22:02:34 +0000697 if (DemoteCatchSwitchPHIOnly && !isa<CatchSwitchInst>(BB->getFirstNonPHI()))
698 continue;
699
David Majnemerfd9f4772015-08-11 01:15:26 +0000700 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
Duncan P. N. Exon Smithf1ff53e2015-10-09 22:56:24 +0000701 Instruction *I = &*BI++;
David Majnemerfd9f4772015-08-11 01:15:26 +0000702 auto *PN = dyn_cast<PHINode>(I);
703 // Stop at the first non-PHI.
704 if (!PN)
705 break;
David Majnemerfd9f4772015-08-11 01:15:26 +0000706
Joseph Tremouletc9ff9142015-08-13 14:30:10 +0000707 AllocaInst *SpillSlot = insertPHILoads(PN, F);
708 if (SpillSlot)
709 insertPHIStores(PN, SpillSlot);
710
711 PHINodes.push_back(PN);
David Majnemerfd9f4772015-08-11 01:15:26 +0000712 }
713 }
714
Joseph Tremouletc9ff9142015-08-13 14:30:10 +0000715 for (auto *PN : PHINodes) {
716 // There may be lingering uses on other EH PHIs being removed
717 PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
718 PN->eraseFromParent();
David Majnemerfd9f4772015-08-11 01:15:26 +0000719 }
David Majnemerb3d9b962015-09-16 18:40:24 +0000720}
David Majnemerfd9f4772015-08-11 01:15:26 +0000721
David Majnemer8a1c45d2015-12-12 05:38:55 +0000722void WinEHPrepare::cloneCommonBlocks(Function &F) {
David Majnemerfd9f4772015-08-11 01:15:26 +0000723 // We need to clone all blocks which belong to multiple funclets. Values are
Simon Pilgrimf2fbf432016-11-20 13:47:59 +0000724 // remapped throughout the funclet to propagate both the new instructions
David Majnemerfd9f4772015-08-11 01:15:26 +0000725 // *and* the new basic blocks themselves.
David Majnemer8a1c45d2015-12-12 05:38:55 +0000726 for (auto &Funclets : FuncletBlocks) {
727 BasicBlock *FuncletPadBB = Funclets.first;
728 std::vector<BasicBlock *> &BlocksInFunclet = Funclets.second;
Joseph Tremoulet71e56762016-01-02 15:22:36 +0000729 Value *FuncletToken;
730 if (FuncletPadBB == &F.getEntryBlock())
731 FuncletToken = ConstantTokenNone::get(F.getContext());
732 else
733 FuncletToken = FuncletPadBB->getFirstNonPHI();
David Majnemerfd9f4772015-08-11 01:15:26 +0000734
David Majnemer8a1c45d2015-12-12 05:38:55 +0000735 std::vector<std::pair<BasicBlock *, BasicBlock *>> Orig2Clone;
David Majnemerfd9f4772015-08-11 01:15:26 +0000736 ValueToValueMapTy VMap;
David Majnemer8a1c45d2015-12-12 05:38:55 +0000737 for (BasicBlock *BB : BlocksInFunclet) {
738 ColorVector &ColorsForBB = BlockColors[BB];
David Majnemerfd9f4772015-08-11 01:15:26 +0000739 // We don't need to do anything if the block is monochromatic.
740 size_t NumColorsForBB = ColorsForBB.size();
741 if (NumColorsForBB == 1)
742 continue;
743
Andrew Kaylorfdd48fa2015-11-09 19:59:02 +0000744 DEBUG_WITH_TYPE("winehprepare-coloring",
745 dbgs() << " Cloning block \'" << BB->getName()
746 << "\' for funclet \'" << FuncletPadBB->getName()
747 << "\'.\n");
748
David Majnemerfd9f4772015-08-11 01:15:26 +0000749 // Create a new basic block and copy instructions into it!
Joseph Tremouletec182852015-08-28 01:12:35 +0000750 BasicBlock *CBB =
751 CloneBasicBlock(BB, VMap, Twine(".for.", FuncletPadBB->getName()));
752 // Insert the clone immediately after the original to ensure determinism
753 // and to keep the same relative ordering of any funclet's blocks.
754 CBB->insertInto(&F, BB->getNextNode());
David Majnemerfd9f4772015-08-11 01:15:26 +0000755
756 // Add basic block mapping.
757 VMap[BB] = CBB;
758
759 // Record delta operations that we need to perform to our color mappings.
David Majnemer8a1c45d2015-12-12 05:38:55 +0000760 Orig2Clone.emplace_back(BB, CBB);
David Majnemerfd9f4772015-08-11 01:15:26 +0000761 }
762
Joseph Tremoulet39234fc2015-10-07 19:29:56 +0000763 // If nothing was cloned, we're done cloning in this funclet.
764 if (Orig2Clone.empty())
765 continue;
766
David Majnemerfd9f4772015-08-11 01:15:26 +0000767 // Update our color mappings to reflect that one block has lost a color and
768 // another has gained a color.
769 for (auto &BBMapping : Orig2Clone) {
770 BasicBlock *OldBlock = BBMapping.first;
771 BasicBlock *NewBlock = BBMapping.second;
772
David Majnemer8a1c45d2015-12-12 05:38:55 +0000773 BlocksInFunclet.push_back(NewBlock);
774 ColorVector &NewColors = BlockColors[NewBlock];
775 assert(NewColors.empty() && "A new block should only have one color!");
776 NewColors.push_back(FuncletPadBB);
David Majnemerfd9f4772015-08-11 01:15:26 +0000777
Andrew Kaylorfdd48fa2015-11-09 19:59:02 +0000778 DEBUG_WITH_TYPE("winehprepare-coloring",
779 dbgs() << " Assigned color \'" << FuncletPadBB->getName()
780 << "\' to block \'" << NewBlock->getName()
781 << "\'.\n");
782
David Majnemer8a1c45d2015-12-12 05:38:55 +0000783 BlocksInFunclet.erase(
784 std::remove(BlocksInFunclet.begin(), BlocksInFunclet.end(), OldBlock),
785 BlocksInFunclet.end());
786 ColorVector &OldColors = BlockColors[OldBlock];
787 OldColors.erase(
788 std::remove(OldColors.begin(), OldColors.end(), FuncletPadBB),
789 OldColors.end());
Andrew Kaylorfdd48fa2015-11-09 19:59:02 +0000790
791 DEBUG_WITH_TYPE("winehprepare-coloring",
792 dbgs() << " Removed color \'" << FuncletPadBB->getName()
793 << "\' from block \'" << OldBlock->getName()
794 << "\'.\n");
David Majnemerfd9f4772015-08-11 01:15:26 +0000795 }
796
Joseph Tremoulet39234fc2015-10-07 19:29:56 +0000797 // Loop over all of the instructions in this funclet, fixing up operand
David Majnemerfd9f4772015-08-11 01:15:26 +0000798 // references as we go. This uses VMap to do all the hard work.
799 for (BasicBlock *BB : BlocksInFunclet)
800 // Loop over all instructions, fixing each one as we find it...
801 for (Instruction &I : *BB)
Joseph Tremoulet39234fc2015-10-07 19:29:56 +0000802 RemapInstruction(&I, VMap,
Duncan P. N. Exon Smithda68cbc2016-04-07 00:26:43 +0000803 RF_IgnoreMissingLocals | RF_NoModuleLevelChanges);
David Majnemer459a64a2015-09-16 18:40:37 +0000804
Joseph Tremoulet71e56762016-01-02 15:22:36 +0000805 // Catchrets targeting cloned blocks need to be updated separately from
806 // the loop above because they are not in the current funclet.
807 SmallVector<CatchReturnInst *, 2> FixupCatchrets;
808 for (auto &BBMapping : Orig2Clone) {
809 BasicBlock *OldBlock = BBMapping.first;
810 BasicBlock *NewBlock = BBMapping.second;
811
812 FixupCatchrets.clear();
813 for (BasicBlock *Pred : predecessors(OldBlock))
814 if (auto *CatchRet = dyn_cast<CatchReturnInst>(Pred->getTerminator()))
Joseph Tremoulet44b3f962016-01-15 21:16:19 +0000815 if (CatchRet->getCatchSwitchParentPad() == FuncletToken)
Joseph Tremoulet71e56762016-01-02 15:22:36 +0000816 FixupCatchrets.push_back(CatchRet);
817
818 for (CatchReturnInst *CatchRet : FixupCatchrets)
819 CatchRet->setSuccessor(NewBlock);
820 }
821
David Majnemer8a1c45d2015-12-12 05:38:55 +0000822 auto UpdatePHIOnClonedBlock = [&](PHINode *PN, bool IsForOldBlock) {
823 unsigned NumPreds = PN->getNumIncomingValues();
824 for (unsigned PredIdx = 0, PredEnd = NumPreds; PredIdx != PredEnd;
825 ++PredIdx) {
826 BasicBlock *IncomingBlock = PN->getIncomingBlock(PredIdx);
Joseph Tremoulet71e56762016-01-02 15:22:36 +0000827 bool EdgeTargetsFunclet;
828 if (auto *CRI =
829 dyn_cast<CatchReturnInst>(IncomingBlock->getTerminator())) {
Joseph Tremoulet44b3f962016-01-15 21:16:19 +0000830 EdgeTargetsFunclet = (CRI->getCatchSwitchParentPad() == FuncletToken);
Joseph Tremoulet71e56762016-01-02 15:22:36 +0000831 } else {
832 ColorVector &IncomingColors = BlockColors[IncomingBlock];
833 assert(!IncomingColors.empty() && "Block not colored!");
834 assert((IncomingColors.size() == 1 ||
835 llvm::all_of(IncomingColors,
836 [&](BasicBlock *Color) {
837 return Color != FuncletPadBB;
838 })) &&
839 "Cloning should leave this funclet's blocks monochromatic");
840 EdgeTargetsFunclet = (IncomingColors.front() == FuncletPadBB);
841 }
842 if (IsForOldBlock != EdgeTargetsFunclet)
David Majnemer8a1c45d2015-12-12 05:38:55 +0000843 continue;
844 PN->removeIncomingValue(IncomingBlock, /*DeletePHIIfEmpty=*/false);
845 // Revisit the next entry.
846 --PredIdx;
847 --PredEnd;
848 }
849 };
850
851 for (auto &BBMapping : Orig2Clone) {
852 BasicBlock *OldBlock = BBMapping.first;
853 BasicBlock *NewBlock = BBMapping.second;
Benjamin Kramerc7fc81e2017-12-30 15:27:33 +0000854 for (PHINode &OldPN : OldBlock->phis()) {
855 UpdatePHIOnClonedBlock(&OldPN, /*IsForOldBlock=*/true);
David Majnemer8a1c45d2015-12-12 05:38:55 +0000856 }
Benjamin Kramerc7fc81e2017-12-30 15:27:33 +0000857 for (PHINode &NewPN : NewBlock->phis()) {
858 UpdatePHIOnClonedBlock(&NewPN, /*IsForOldBlock=*/false);
David Majnemer8a1c45d2015-12-12 05:38:55 +0000859 }
860 }
861
David Majnemer459a64a2015-09-16 18:40:37 +0000862 // Check to see if SuccBB has PHI nodes. If so, we need to add entries to
863 // the PHI nodes for NewBB now.
864 for (auto &BBMapping : Orig2Clone) {
865 BasicBlock *OldBlock = BBMapping.first;
866 BasicBlock *NewBlock = BBMapping.second;
867 for (BasicBlock *SuccBB : successors(NewBlock)) {
Benjamin Kramerc7fc81e2017-12-30 15:27:33 +0000868 for (PHINode &SuccPN : SuccBB->phis()) {
David Majnemer459a64a2015-09-16 18:40:37 +0000869 // Ok, we have a PHI node. Figure out what the incoming value was for
870 // the OldBlock.
Benjamin Kramerc7fc81e2017-12-30 15:27:33 +0000871 int OldBlockIdx = SuccPN.getBasicBlockIndex(OldBlock);
David Majnemer459a64a2015-09-16 18:40:37 +0000872 if (OldBlockIdx == -1)
873 break;
Benjamin Kramerc7fc81e2017-12-30 15:27:33 +0000874 Value *IV = SuccPN.getIncomingValue(OldBlockIdx);
David Majnemer459a64a2015-09-16 18:40:37 +0000875
876 // Remap the value if necessary.
877 if (auto *Inst = dyn_cast<Instruction>(IV)) {
878 ValueToValueMapTy::iterator I = VMap.find(Inst);
879 if (I != VMap.end())
880 IV = I->second;
881 }
882
Benjamin Kramerc7fc81e2017-12-30 15:27:33 +0000883 SuccPN.addIncoming(IV, NewBlock);
David Majnemer459a64a2015-09-16 18:40:37 +0000884 }
885 }
886 }
887
888 for (ValueToValueMapTy::value_type VT : VMap) {
889 // If there were values defined in BB that are used outside the funclet,
890 // then we now have to update all uses of the value to use either the
891 // original value, the cloned value, or some PHI derived value. This can
892 // require arbitrary PHI insertion, of which we are prepared to do, clean
893 // these up now.
894 SmallVector<Use *, 16> UsesToRename;
895
896 auto *OldI = dyn_cast<Instruction>(const_cast<Value *>(VT.first));
897 if (!OldI)
898 continue;
899 auto *NewI = cast<Instruction>(VT.second);
900 // Scan all uses of this instruction to see if it is used outside of its
901 // funclet, and if so, record them in UsesToRename.
902 for (Use &U : OldI->uses()) {
903 Instruction *UserI = cast<Instruction>(U.getUser());
904 BasicBlock *UserBB = UserI->getParent();
David Majnemer8a1c45d2015-12-12 05:38:55 +0000905 ColorVector &ColorsForUserBB = BlockColors[UserBB];
David Majnemer459a64a2015-09-16 18:40:37 +0000906 assert(!ColorsForUserBB.empty());
907 if (ColorsForUserBB.size() > 1 ||
908 *ColorsForUserBB.begin() != FuncletPadBB)
909 UsesToRename.push_back(&U);
910 }
911
912 // If there are no uses outside the block, we're done with this
913 // instruction.
914 if (UsesToRename.empty())
915 continue;
916
917 // We found a use of OldI outside of the funclet. Rename all uses of OldI
918 // that are outside its funclet to be uses of the appropriate PHI node
919 // etc.
920 SSAUpdater SSAUpdate;
921 SSAUpdate.Initialize(OldI->getType(), OldI->getName());
922 SSAUpdate.AddAvailableValue(OldI->getParent(), OldI);
923 SSAUpdate.AddAvailableValue(NewI->getParent(), NewI);
924
925 while (!UsesToRename.empty())
926 SSAUpdate.RewriteUseAfterInsertions(*UsesToRename.pop_back_val());
927 }
David Majnemerfd9f4772015-08-11 01:15:26 +0000928 }
David Majnemerb3d9b962015-09-16 18:40:24 +0000929}
David Majnemerfd9f4772015-08-11 01:15:26 +0000930
David Majnemer3bb88c02015-12-15 21:27:27 +0000931void WinEHPrepare::removeImplausibleInstructions(Function &F) {
David Majnemer83f4bb22015-08-17 20:56:39 +0000932 // Remove implausible terminators and replace them with UnreachableInst.
933 for (auto &Funclet : FuncletBlocks) {
934 BasicBlock *FuncletPadBB = Funclet.first;
David Majnemer8a1c45d2015-12-12 05:38:55 +0000935 std::vector<BasicBlock *> &BlocksInFunclet = Funclet.second;
David Majnemer3bb88c02015-12-15 21:27:27 +0000936 Instruction *FirstNonPHI = FuncletPadBB->getFirstNonPHI();
937 auto *FuncletPad = dyn_cast<FuncletPadInst>(FirstNonPHI);
938 auto *CatchPad = dyn_cast_or_null<CatchPadInst>(FuncletPad);
939 auto *CleanupPad = dyn_cast_or_null<CleanupPadInst>(FuncletPad);
David Majnemer83f4bb22015-08-17 20:56:39 +0000940
941 for (BasicBlock *BB : BlocksInFunclet) {
David Majnemer3bb88c02015-12-15 21:27:27 +0000942 for (Instruction &I : *BB) {
943 CallSite CS(&I);
944 if (!CS)
945 continue;
946
947 Value *FuncletBundleOperand = nullptr;
948 if (auto BU = CS.getOperandBundle(LLVMContext::OB_funclet))
949 FuncletBundleOperand = BU->Inputs.front();
950
951 if (FuncletBundleOperand == FuncletPad)
952 continue;
953
David Majnemer08dd52dc2016-02-26 00:04:25 +0000954 // Skip call sites which are nounwind intrinsics or inline asm.
David Majnemer3bb88c02015-12-15 21:27:27 +0000955 auto *CalledFn =
956 dyn_cast<Function>(CS.getCalledValue()->stripPointerCasts());
Justin Lebar9cbc3012016-07-28 23:58:15 +0000957 if (CalledFn && ((CalledFn->isIntrinsic() && CS.doesNotThrow()) ||
958 CS.isInlineAsm()))
David Majnemer3bb88c02015-12-15 21:27:27 +0000959 continue;
960
961 // This call site was not part of this funclet, remove it.
962 if (CS.isInvoke()) {
963 // Remove the unwind edge if it was an invoke.
964 removeUnwindEdge(BB);
965 // Get a pointer to the new call.
966 BasicBlock::iterator CallI =
967 std::prev(BB->getTerminator()->getIterator());
968 auto *CI = cast<CallInst>(&*CallI);
David Majnemere14e7bc2016-06-25 08:19:55 +0000969 changeToUnreachable(CI, /*UseLLVMTrap=*/false);
David Majnemer3bb88c02015-12-15 21:27:27 +0000970 } else {
David Majnemere14e7bc2016-06-25 08:19:55 +0000971 changeToUnreachable(&I, /*UseLLVMTrap=*/false);
David Majnemer3bb88c02015-12-15 21:27:27 +0000972 }
973
974 // There are no more instructions in the block (except for unreachable),
975 // we are done.
976 break;
977 }
978
Chandler Carruthedb12a82018-10-15 10:04:59 +0000979 Instruction *TI = BB->getTerminator();
David Majnemer83f4bb22015-08-17 20:56:39 +0000980 // CatchPadInst and CleanupPadInst can't transfer control to a ReturnInst.
David Majnemer3bb88c02015-12-15 21:27:27 +0000981 bool IsUnreachableRet = isa<ReturnInst>(TI) && FuncletPad;
David Majnemer83f4bb22015-08-17 20:56:39 +0000982 // The token consumed by a CatchReturnInst must match the funclet token.
983 bool IsUnreachableCatchret = false;
984 if (auto *CRI = dyn_cast<CatchReturnInst>(TI))
Joseph Tremoulet8220bcc2015-08-23 00:26:33 +0000985 IsUnreachableCatchret = CRI->getCatchPad() != CatchPad;
Joseph Tremoulet9ce71f72015-09-03 09:09:43 +0000986 // The token consumed by a CleanupReturnInst must match the funclet token.
David Majnemer83f4bb22015-08-17 20:56:39 +0000987 bool IsUnreachableCleanupret = false;
988 if (auto *CRI = dyn_cast<CleanupReturnInst>(TI))
Joseph Tremoulet8220bcc2015-08-23 00:26:33 +0000989 IsUnreachableCleanupret = CRI->getCleanupPad() != CleanupPad;
Joseph Tremoulet9ce71f72015-09-03 09:09:43 +0000990 if (IsUnreachableRet || IsUnreachableCatchret ||
David Majnemer8a1c45d2015-12-12 05:38:55 +0000991 IsUnreachableCleanupret) {
David Majnemere14e7bc2016-06-25 08:19:55 +0000992 changeToUnreachable(TI, /*UseLLVMTrap=*/false);
David Majnemer8a1c45d2015-12-12 05:38:55 +0000993 } else if (isa<InvokeInst>(TI)) {
David Majnemer3bb88c02015-12-15 21:27:27 +0000994 if (Personality == EHPersonality::MSVC_CXX && CleanupPad) {
995 // Invokes within a cleanuppad for the MSVC++ personality never
996 // transfer control to their unwind edge: the personality will
997 // terminate the program.
David Majnemer8a1c45d2015-12-12 05:38:55 +0000998 removeUnwindEdge(BB);
David Majnemer3bb88c02015-12-15 21:27:27 +0000999 }
David Majnemer83f4bb22015-08-17 20:56:39 +00001000 }
1001 }
1002 }
David Majnemerb3d9b962015-09-16 18:40:24 +00001003}
David Majnemer83f4bb22015-08-17 20:56:39 +00001004
David Majnemerb3d9b962015-09-16 18:40:24 +00001005void WinEHPrepare::cleanupPreparedFunclets(Function &F) {
David Majnemerfd9f4772015-08-11 01:15:26 +00001006 // Clean-up some of the mess we made by removing useles PHI nodes, trivial
1007 // branches, etc.
1008 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
Duncan P. N. Exon Smithf1ff53e2015-10-09 22:56:24 +00001009 BasicBlock *BB = &*FI++;
David Majnemerfd9f4772015-08-11 01:15:26 +00001010 SimplifyInstructionsInBlock(BB);
1011 ConstantFoldTerminator(BB, /*DeleteDeadConditions=*/true);
1012 MergeBlockIntoPredecessor(BB);
1013 }
1014
David Majnemerfd9f4772015-08-11 01:15:26 +00001015 // We might have some unreachable blocks after cleaning up some impossible
1016 // control flow.
1017 removeUnreachableBlocks(F);
David Majnemerb3d9b962015-09-16 18:40:24 +00001018}
David Majnemerfd9f4772015-08-11 01:15:26 +00001019
Florian Hahn6b3216a2017-07-31 10:07:49 +00001020#ifndef NDEBUG
David Majnemerb3d9b962015-09-16 18:40:24 +00001021void WinEHPrepare::verifyPreparedFunclets(Function &F) {
David Majnemerfd9f4772015-08-11 01:15:26 +00001022 for (BasicBlock &BB : F) {
1023 size_t NumColors = BlockColors[&BB].size();
1024 assert(NumColors == 1 && "Expected monochromatic BB!");
1025 if (NumColors == 0)
1026 report_fatal_error("Uncolored BB!");
1027 if (NumColors > 1)
1028 report_fatal_error("Multicolor BB!");
NAKAMURA Takumided575e2016-01-03 01:41:00 +00001029 assert((DisableDemotion || !(BB.isEHPad() && isa<PHINode>(BB.begin()))) &&
1030 "EH Pad still has a PHI!");
David Majnemerfd9f4772015-08-11 01:15:26 +00001031 }
David Majnemerb3d9b962015-09-16 18:40:24 +00001032}
Florian Hahn6b3216a2017-07-31 10:07:49 +00001033#endif
David Majnemerb3d9b962015-09-16 18:40:24 +00001034
David Majnemer8a1c45d2015-12-12 05:38:55 +00001035bool WinEHPrepare::prepareExplicitEH(Function &F) {
1036 // Remove unreachable blocks. It is not valuable to assign them a color and
1037 // their existence can trick us into thinking values are alive when they are
1038 // not.
1039 removeUnreachableBlocks(F);
1040
David Majnemerb3d9b962015-09-16 18:40:24 +00001041 // Determine which blocks are reachable from which funclet entries.
David Majnemer8a1c45d2015-12-12 05:38:55 +00001042 colorFunclets(F);
1043
1044 cloneCommonBlocks(F);
David Majnemerb3d9b962015-09-16 18:40:24 +00001045
Reid Klecknercc2f6c32015-11-19 23:23:33 +00001046 if (!DisableDemotion)
Heejin Ahn99d60e02018-05-31 22:02:34 +00001047 demotePHIsOnFunclets(F, DemoteCatchSwitchPHIOnly ||
1048 DemoteCatchSwitchPHIOnlyOpt);
David Majnemerb3d9b962015-09-16 18:40:24 +00001049
David Majnemer459a64a2015-09-16 18:40:37 +00001050 if (!DisableCleanups) {
Nicola Zaghend34e60c2018-05-14 12:53:11 +00001051 LLVM_DEBUG(verifyFunction(F));
David Majnemer3bb88c02015-12-15 21:27:27 +00001052 removeImplausibleInstructions(F);
David Majnemerb3d9b962015-09-16 18:40:24 +00001053
Nicola Zaghend34e60c2018-05-14 12:53:11 +00001054 LLVM_DEBUG(verifyFunction(F));
David Majnemer459a64a2015-09-16 18:40:37 +00001055 cleanupPreparedFunclets(F);
1056 }
David Majnemerb3d9b962015-09-16 18:40:24 +00001057
Nicola Zaghend34e60c2018-05-14 12:53:11 +00001058 LLVM_DEBUG(verifyPreparedFunclets(F));
David Majnemerdbdc9c22016-01-02 09:26:36 +00001059 // Recolor the CFG to verify that all is well.
Nicola Zaghend34e60c2018-05-14 12:53:11 +00001060 LLVM_DEBUG(colorFunclets(F));
1061 LLVM_DEBUG(verifyPreparedFunclets(F));
David Majnemerfd9f4772015-08-11 01:15:26 +00001062
1063 BlockColors.clear();
1064 FuncletBlocks.clear();
David Majnemer0ad363e2015-08-18 19:07:12 +00001065
David Majnemerfd9f4772015-08-11 01:15:26 +00001066 return true;
1067}
Joseph Tremouletc9ff9142015-08-13 14:30:10 +00001068
1069// TODO: Share loads when one use dominates another, or when a catchpad exit
1070// dominates uses (needs dominators).
1071AllocaInst *WinEHPrepare::insertPHILoads(PHINode *PN, Function &F) {
1072 BasicBlock *PHIBlock = PN->getParent();
1073 AllocaInst *SpillSlot = nullptr;
David Majnemer8a1c45d2015-12-12 05:38:55 +00001074 Instruction *EHPad = PHIBlock->getFirstNonPHI();
Joseph Tremouletc9ff9142015-08-13 14:30:10 +00001075
Chandler Carruth9ae926b2018-08-26 09:51:22 +00001076 if (!EHPad->isTerminator()) {
David Majnemer8a1c45d2015-12-12 05:38:55 +00001077 // If the EHPad isn't a terminator, then we can insert a load in this block
1078 // that will dominate all uses.
Matt Arsenault3c1fc762017-04-10 22:27:50 +00001079 SpillSlot = new AllocaInst(PN->getType(), DL->getAllocaAddrSpace(), nullptr,
Joseph Tremouletc9ff9142015-08-13 14:30:10 +00001080 Twine(PN->getName(), ".wineh.spillslot"),
Duncan P. N. Exon Smithf1ff53e2015-10-09 22:56:24 +00001081 &F.getEntryBlock().front());
James Y Knight14359ef2019-02-01 20:44:24 +00001082 Value *V = new LoadInst(PN->getType(), SpillSlot,
1083 Twine(PN->getName(), ".wineh.reload"),
Duncan P. N. Exon Smithf1ff53e2015-10-09 22:56:24 +00001084 &*PHIBlock->getFirstInsertionPt());
Joseph Tremouletc9ff9142015-08-13 14:30:10 +00001085 PN->replaceAllUsesWith(V);
1086 return SpillSlot;
1087 }
1088
David Majnemer8a1c45d2015-12-12 05:38:55 +00001089 // Otherwise, we have a PHI on a terminator EHPad, and we give up and insert
1090 // loads of the slot before every use.
Joseph Tremouletc9ff9142015-08-13 14:30:10 +00001091 DenseMap<BasicBlock *, Value *> Loads;
1092 for (Value::use_iterator UI = PN->use_begin(), UE = PN->use_end();
1093 UI != UE;) {
1094 Use &U = *UI++;
1095 auto *UsingInst = cast<Instruction>(U.getUser());
David Majnemer8a1c45d2015-12-12 05:38:55 +00001096 if (isa<PHINode>(UsingInst) && UsingInst->getParent()->isEHPad()) {
Joseph Tremouletc9ff9142015-08-13 14:30:10 +00001097 // Use is on an EH pad phi. Leave it alone; we'll insert loads and
1098 // stores for it separately.
Joseph Tremouletc9ff9142015-08-13 14:30:10 +00001099 continue;
1100 }
1101 replaceUseWithLoad(PN, U, SpillSlot, Loads, F);
1102 }
1103 return SpillSlot;
1104}
1105
1106// TODO: improve store placement. Inserting at def is probably good, but need
1107// to be careful not to introduce interfering stores (needs liveness analysis).
1108// TODO: identify related phi nodes that can share spill slots, and share them
1109// (also needs liveness).
1110void WinEHPrepare::insertPHIStores(PHINode *OriginalPHI,
1111 AllocaInst *SpillSlot) {
1112 // Use a worklist of (Block, Value) pairs -- the given Value needs to be
1113 // stored to the spill slot by the end of the given Block.
1114 SmallVector<std::pair<BasicBlock *, Value *>, 4> Worklist;
1115
1116 Worklist.push_back({OriginalPHI->getParent(), OriginalPHI});
1117
1118 while (!Worklist.empty()) {
1119 BasicBlock *EHBlock;
1120 Value *InVal;
1121 std::tie(EHBlock, InVal) = Worklist.pop_back_val();
1122
1123 PHINode *PN = dyn_cast<PHINode>(InVal);
1124 if (PN && PN->getParent() == EHBlock) {
1125 // The value is defined by another PHI we need to remove, with no room to
1126 // insert a store after the PHI, so each predecessor needs to store its
1127 // incoming value.
1128 for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i) {
1129 Value *PredVal = PN->getIncomingValue(i);
1130
1131 // Undef can safely be skipped.
1132 if (isa<UndefValue>(PredVal))
1133 continue;
1134
1135 insertPHIStore(PN->getIncomingBlock(i), PredVal, SpillSlot, Worklist);
1136 }
1137 } else {
1138 // We need to store InVal, which dominates EHBlock, but can't put a store
1139 // in EHBlock, so need to put stores in each predecessor.
1140 for (BasicBlock *PredBlock : predecessors(EHBlock)) {
1141 insertPHIStore(PredBlock, InVal, SpillSlot, Worklist);
1142 }
1143 }
1144 }
1145}
1146
1147void WinEHPrepare::insertPHIStore(
1148 BasicBlock *PredBlock, Value *PredVal, AllocaInst *SpillSlot,
1149 SmallVectorImpl<std::pair<BasicBlock *, Value *>> &Worklist) {
1150
Chandler Carruth9ae926b2018-08-26 09:51:22 +00001151 if (PredBlock->isEHPad() && PredBlock->getFirstNonPHI()->isTerminator()) {
Joseph Tremouletc9ff9142015-08-13 14:30:10 +00001152 // Pred is unsplittable, so we need to queue it on the worklist.
1153 Worklist.push_back({PredBlock, PredVal});
1154 return;
1155 }
1156
1157 // Otherwise, insert the store at the end of the basic block.
1158 new StoreInst(PredVal, SpillSlot, PredBlock->getTerminator());
1159}
1160
Joseph Tremouletc9ff9142015-08-13 14:30:10 +00001161void WinEHPrepare::replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot,
1162 DenseMap<BasicBlock *, Value *> &Loads,
1163 Function &F) {
1164 // Lazilly create the spill slot.
1165 if (!SpillSlot)
Matt Arsenault3c1fc762017-04-10 22:27:50 +00001166 SpillSlot = new AllocaInst(V->getType(), DL->getAllocaAddrSpace(), nullptr,
Joseph Tremouletc9ff9142015-08-13 14:30:10 +00001167 Twine(V->getName(), ".wineh.spillslot"),
Duncan P. N. Exon Smithf1ff53e2015-10-09 22:56:24 +00001168 &F.getEntryBlock().front());
Joseph Tremouletc9ff9142015-08-13 14:30:10 +00001169
1170 auto *UsingInst = cast<Instruction>(U.getUser());
1171 if (auto *UsingPHI = dyn_cast<PHINode>(UsingInst)) {
1172 // If this is a PHI node, we can't insert a load of the value before
1173 // the use. Instead insert the load in the predecessor block
1174 // corresponding to the incoming value.
1175 //
1176 // Note that if there are multiple edges from a basic block to this
1177 // PHI node that we cannot have multiple loads. The problem is that
1178 // the resulting PHI node will have multiple values (from each load)
1179 // coming in from the same block, which is illegal SSA form.
1180 // For this reason, we keep track of and reuse loads we insert.
1181 BasicBlock *IncomingBlock = UsingPHI->getIncomingBlock(U);
Joseph Tremoulet7031c9f2015-08-17 13:51:37 +00001182 if (auto *CatchRet =
1183 dyn_cast<CatchReturnInst>(IncomingBlock->getTerminator())) {
1184 // Putting a load above a catchret and use on the phi would still leave
1185 // a cross-funclet def/use. We need to split the edge, change the
1186 // catchret to target the new block, and put the load there.
1187 BasicBlock *PHIBlock = UsingInst->getParent();
1188 BasicBlock *NewBlock = SplitEdge(IncomingBlock, PHIBlock);
1189 // SplitEdge gives us:
1190 // IncomingBlock:
1191 // ...
1192 // br label %NewBlock
1193 // NewBlock:
1194 // catchret label %PHIBlock
1195 // But we need:
1196 // IncomingBlock:
1197 // ...
1198 // catchret label %NewBlock
1199 // NewBlock:
1200 // br label %PHIBlock
1201 // So move the terminators to each others' blocks and swap their
1202 // successors.
1203 BranchInst *Goto = cast<BranchInst>(IncomingBlock->getTerminator());
1204 Goto->removeFromParent();
1205 CatchRet->removeFromParent();
1206 IncomingBlock->getInstList().push_back(CatchRet);
1207 NewBlock->getInstList().push_back(Goto);
1208 Goto->setSuccessor(0, PHIBlock);
1209 CatchRet->setSuccessor(NewBlock);
1210 // Update the color mapping for the newly split edge.
Andrew Kaylorce3bcae2016-12-14 19:30:18 +00001211 // Grab a reference to the ColorVector to be inserted before getting the
1212 // reference to the vector we are copying because inserting the new
1213 // element in BlockColors might cause the map to be reallocated.
1214 ColorVector &ColorsForNewBlock = BlockColors[NewBlock];
David Majnemer8a1c45d2015-12-12 05:38:55 +00001215 ColorVector &ColorsForPHIBlock = BlockColors[PHIBlock];
Andrew Kaylorce3bcae2016-12-14 19:30:18 +00001216 ColorsForNewBlock = ColorsForPHIBlock;
Joseph Tremoulet7031c9f2015-08-17 13:51:37 +00001217 for (BasicBlock *FuncletPad : ColorsForPHIBlock)
David Majnemer8a1c45d2015-12-12 05:38:55 +00001218 FuncletBlocks[FuncletPad].push_back(NewBlock);
Joseph Tremoulet7031c9f2015-08-17 13:51:37 +00001219 // Treat the new block as incoming for load insertion.
1220 IncomingBlock = NewBlock;
1221 }
Joseph Tremouletc9ff9142015-08-13 14:30:10 +00001222 Value *&Load = Loads[IncomingBlock];
1223 // Insert the load into the predecessor block
1224 if (!Load)
James Y Knight14359ef2019-02-01 20:44:24 +00001225 Load = new LoadInst(V->getType(), SpillSlot,
1226 Twine(V->getName(), ".wineh.reload"),
Rui Ueyama49a3ad22019-07-16 04:46:31 +00001227 /*isVolatile=*/false, IncomingBlock->getTerminator());
Joseph Tremouletc9ff9142015-08-13 14:30:10 +00001228
1229 U.set(Load);
1230 } else {
1231 // Reload right before the old use.
James Y Knight14359ef2019-02-01 20:44:24 +00001232 auto *Load = new LoadInst(V->getType(), SpillSlot,
1233 Twine(V->getName(), ".wineh.reload"),
Rui Ueyama49a3ad22019-07-16 04:46:31 +00001234 /*isVolatile=*/false, UsingInst);
Joseph Tremouletc9ff9142015-08-13 14:30:10 +00001235 U.set(Load);
1236 }
1237}
Reid Klecknerc71d6272015-09-28 23:56:30 +00001238
David Majnemer8a1c45d2015-12-12 05:38:55 +00001239void WinEHFuncInfo::addIPToStateRange(const InvokeInst *II,
Reid Klecknerc71d6272015-09-28 23:56:30 +00001240 MCSymbol *InvokeBegin,
1241 MCSymbol *InvokeEnd) {
David Majnemer8a1c45d2015-12-12 05:38:55 +00001242 assert(InvokeStateMap.count(II) &&
1243 "should get invoke with precomputed state");
1244 LabelToStateMap[InvokeBegin] = std::make_pair(InvokeStateMap[II], InvokeEnd);
Reid Klecknerc71d6272015-09-28 23:56:30 +00001245}
Chandler Carruthe0115342015-12-29 09:24:39 +00001246
1247WinEHFuncInfo::WinEHFuncInfo() {}