X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;ds=sidebyside;f=lib%2FCodeGen%2FWinEHPrepare.cpp;h=86b511cfb6708f31a5822023955e7e702b5acc6d;hb=ee97a1a33b2cb1173e0b4c601ed5976e56654063;hp=a1da1aefd8f456d0a72997492e4a29d6c2d77069;hpb=173a68d4a2e92dfc1815af5d06f55ac6ec242958;p=oota-llvm.git diff --git a/lib/CodeGen/WinEHPrepare.cpp b/lib/CodeGen/WinEHPrepare.cpp index a1da1aefd8f..86b511cfb67 100644 --- a/lib/CodeGen/WinEHPrepare.cpp +++ b/lib/CodeGen/WinEHPrepare.cpp @@ -8,9 +8,11 @@ //===----------------------------------------------------------------------===// // // This pass lowers LLVM IR exception handling into something closer to what the -// backend wants. It snifs the personality function to see which kind of -// preparation is necessary. If the personality function uses the Itanium LSDA, -// this pass delegates to the DWARF EH preparation pass. +// backend wants for functions using a personality function from a runtime +// provided by MSVC. Functions with other personality functions are left alone +// and may be prepared by other passes. In particular, all supported MSVC +// personality functions require cleanup code to be outlined, and the C++ +// personality requires catch handler code to be outlined. // //===----------------------------------------------------------------------===// @@ -19,8 +21,11 @@ #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SetVector.h" +#include "llvm/ADT/Triple.h" #include "llvm/ADT/TinyPtrVector.h" +#include "llvm/Analysis/CFG.h" #include "llvm/Analysis/LibCallSemantics.h" +#include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/CodeGen/WinEHFuncInfo.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Function.h" @@ -29,14 +34,15 @@ #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/Module.h" #include "llvm/IR/PatternMatch.h" +#include "llvm/MC/MCSymbol.h" #include "llvm/Pass.h" -#include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/Cloning.h" #include "llvm/Transforms/Utils/Local.h" #include "llvm/Transforms/Utils/PromoteMemToReg.h" +#include "llvm/Transforms/Utils/SSAUpdater.h" #include using namespace llvm; @@ -44,6 +50,17 @@ using namespace llvm::PatternMatch; #define DEBUG_TYPE "winehprepare" +static cl::opt DisableDemotion( + "disable-demotion", cl::Hidden, + cl::desc( + "Clone multicolor basic blocks but do not demote cross funclet values"), + cl::init(false)); + +static cl::opt DisableCleanups( + "disable-cleanups", cl::Hidden, + cl::desc("Do not remove implausible terminators or other similar cleanups"), + cl::init(false)); + namespace { // This map is used to model frame variable usage during outlining, to @@ -71,7 +88,10 @@ class WinEHPrepare : public FunctionPass { public: static char ID; // Pass identification, replacement for typeid. WinEHPrepare(const TargetMachine *TM = nullptr) - : FunctionPass(ID), DT(nullptr) {} + : FunctionPass(ID) { + if (TM) + TheTriple = TM->getTargetTriple(); + } bool runOnFunction(Function &Fn) override; @@ -86,17 +106,26 @@ public: private: bool prepareExceptionHandlers(Function &F, SmallVectorImpl &LPads); + void identifyEHBlocks(Function &F, SmallVectorImpl &LPads); void promoteLandingPadValues(LandingPadInst *LPad); void demoteValuesLiveAcrossHandlers(Function &F, SmallVectorImpl &LPads); + void findSEHEHReturnPoints(Function &F, + SetVector &EHReturnBlocks); + void findCXXEHReturnPoints(Function &F, + SetVector &EHReturnBlocks); + void getPossibleReturnTargets(Function *ParentF, Function *HandlerF, + SetVector &Targets); void completeNestedLandingPad(Function *ParentFn, LandingPadInst *OutlinedLPad, const LandingPadInst *OriginalLPad, FrameVarInfoMap &VarInfo); + Function *createHandlerFunc(Function *ParentFn, Type *RetTy, + const Twine &Name, Module *M, Value *&ParentFP); bool outlineHandler(ActionHandler *Action, Function *SrcFn, LandingPadInst *LPad, BasicBlock *StartBB, FrameVarInfoMap &VarInfo); - void addStubInvokeToHandlerIfNeeded(Function *Handler, Value *PersonalityFn); + void addStubInvokeToHandlerIfNeeded(Function *Handler); void mapLandingPadBlocks(LandingPadInst *LPad, LandingPadActions &Actions); CatchHandler *findCatchHandler(BasicBlock *BB, BasicBlock *&NextBB, @@ -105,13 +134,40 @@ private: BasicBlock *EndBB); void processSEHCatchHandler(CatchHandler *Handler, BasicBlock *StartBB); + void insertPHIStores(PHINode *OriginalPHI, AllocaInst *SpillSlot); + void + insertPHIStore(BasicBlock *PredBlock, Value *PredVal, AllocaInst *SpillSlot, + SmallVectorImpl> &Worklist); + AllocaInst *insertPHILoads(PHINode *PN, Function &F); + void replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot, + DenseMap &Loads, Function &F); + void demoteNonlocalUses(Value *V, std::set &ColorsForBB, + Function &F); + bool prepareExplicitEH(Function &F, + SmallVectorImpl &EntryBlocks); + void replaceTerminatePadWithCleanup(Function &F); + void colorFunclets(Function &F, SmallVectorImpl &EntryBlocks); + void demotePHIsOnFunclets(Function &F); + void demoteUsesBetweenFunclets(Function &F); + void demoteArgumentUses(Function &F); + void cloneCommonBlocks(Function &F, + SmallVectorImpl &EntryBlocks); + void removeImplausibleTerminators(Function &F); + void cleanupPreparedFunclets(Function &F); + void verifyPreparedFunclets(Function &F); + + Triple TheTriple; // All fields are reset by runOnFunction. - DominatorTree *DT; - EHPersonality Personality; + DominatorTree *DT = nullptr; + const TargetLibraryInfo *LibInfo = nullptr; + EHPersonality Personality = EHPersonality::Unknown; CatchHandlerMapTy CatchHandlerMap; CleanupHandlerMapTy CleanupHandlerMap; DenseMap LPadMaps; + SmallPtrSet NormalBlocks; + SmallPtrSet EHBlocks; + SetVector EHReturnBlocks; // This maps landing pad instructions found in outlined handlers to // the landing pad instruction in the parent function from which they @@ -133,11 +189,21 @@ private: // outlined into a handler. This is done after all handlers have been // outlined but before the outlined code is pruned from the parent function. DenseMap LPadTargetBlocks; + + // Map from outlined handler to call to parent local address. Only used for + // 32-bit EH. + DenseMap HandlerToParentFP; + + AllocaInst *SEHExceptionCodeSlot = nullptr; + + std::map> BlockColors; + std::map> FuncletBlocks; + std::map> FuncletChildren; }; class WinEHFrameVariableMaterializer : public ValueMaterializer { public: - WinEHFrameVariableMaterializer(Function *OutlinedFn, + WinEHFrameVariableMaterializer(Function *OutlinedFn, Value *ParentFP, FrameVarInfoMap &FrameVarInfo); ~WinEHFrameVariableMaterializer() override {} @@ -173,16 +239,12 @@ private: class WinEHCloningDirectorBase : public CloningDirector { public: - WinEHCloningDirectorBase(Function *HandlerFn, FrameVarInfoMap &VarInfo, - LandingPadMap &LPadMap) - : Materializer(HandlerFn, VarInfo), + WinEHCloningDirectorBase(Function *HandlerFn, Value *ParentFP, + FrameVarInfoMap &VarInfo, LandingPadMap &LPadMap) + : Materializer(HandlerFn, ParentFP, VarInfo), SelectorIDType(Type::getInt32Ty(HandlerFn->getContext())), Int8PtrType(Type::getInt8PtrTy(HandlerFn->getContext())), - LPadMap(LPadMap) { - auto AI = HandlerFn->getArgumentList().begin(); - ++AI; - EstablisherFrame = AI; - } + LPadMap(LPadMap), ParentFP(ParentFP) {} CloningAction handleInstruction(ValueToValueMapTy &VMap, const Instruction *Inst, @@ -197,6 +259,9 @@ public: virtual CloningAction handleTypeIdFor(ValueToValueMapTy &VMap, const Instruction *Inst, BasicBlock *NewBB) = 0; + virtual CloningAction handleIndirectBr(ValueToValueMapTy &VMap, + const IndirectBrInst *IBr, + BasicBlock *NewBB) = 0; virtual CloningAction handleInvoke(ValueToValueMapTy &VMap, const InvokeInst *Invoke, BasicBlock *NewBB) = 0; @@ -219,18 +284,20 @@ protected: LandingPadMap &LPadMap; /// The value representing the parent frame pointer. - Value *EstablisherFrame; + Value *ParentFP; }; class WinEHCatchDirector : public WinEHCloningDirectorBase { public: WinEHCatchDirector( - Function *CatchFn, Value *Selector, FrameVarInfoMap &VarInfo, - LandingPadMap &LPadMap, - DenseMap &NestedLPads) - : WinEHCloningDirectorBase(CatchFn, VarInfo, LPadMap), + Function *CatchFn, Value *ParentFP, Value *Selector, + FrameVarInfoMap &VarInfo, LandingPadMap &LPadMap, + DenseMap &NestedLPads, + DominatorTree *DT, SmallPtrSetImpl &EHBlocks) + : WinEHCloningDirectorBase(CatchFn, ParentFP, VarInfo, LPadMap), CurrentSelector(Selector->stripPointerCasts()), - ExceptionObjectVar(nullptr), NestedLPtoOriginalLP(NestedLPads) {} + ExceptionObjectVar(nullptr), NestedLPtoOriginalLP(NestedLPads), + DT(DT), EHBlocks(EHBlocks) {} CloningAction handleBeginCatch(ValueToValueMapTy &VMap, const Instruction *Inst, @@ -240,12 +307,15 @@ public: CloningAction handleTypeIdFor(ValueToValueMapTy &VMap, const Instruction *Inst, BasicBlock *NewBB) override; + CloningAction handleIndirectBr(ValueToValueMapTy &VMap, + const IndirectBrInst *IBr, + BasicBlock *NewBB) override; CloningAction handleInvoke(ValueToValueMapTy &VMap, const InvokeInst *Invoke, BasicBlock *NewBB) override; CloningAction handleResume(ValueToValueMapTy &VMap, const ResumeInst *Resume, BasicBlock *NewBB) override; - CloningAction handleCompare(ValueToValueMapTy &VMap, - const CmpInst *Compare, BasicBlock *NewBB) override; + CloningAction handleCompare(ValueToValueMapTy &VMap, const CmpInst *Compare, + BasicBlock *NewBB) override; CloningAction handleLandingPad(ValueToValueMapTy &VMap, const LandingPadInst *LPad, BasicBlock *NewBB) override; @@ -262,13 +332,16 @@ private: // This will be a reference to the field of the same name in the WinEHPrepare // object which instantiates this WinEHCatchDirector object. DenseMap &NestedLPtoOriginalLP; + DominatorTree *DT; + SmallPtrSetImpl &EHBlocks; }; class WinEHCleanupDirector : public WinEHCloningDirectorBase { public: - WinEHCleanupDirector(Function *CleanupFn, FrameVarInfoMap &VarInfo, - LandingPadMap &LPadMap) - : WinEHCloningDirectorBase(CleanupFn, VarInfo, LPadMap) {} + WinEHCleanupDirector(Function *CleanupFn, Value *ParentFP, + FrameVarInfoMap &VarInfo, LandingPadMap &LPadMap) + : WinEHCloningDirectorBase(CleanupFn, ParentFP, VarInfo, + LPadMap) {} CloningAction handleBeginCatch(ValueToValueMapTy &VMap, const Instruction *Inst, @@ -278,12 +351,15 @@ public: CloningAction handleTypeIdFor(ValueToValueMapTy &VMap, const Instruction *Inst, BasicBlock *NewBB) override; + CloningAction handleIndirectBr(ValueToValueMapTy &VMap, + const IndirectBrInst *IBr, + BasicBlock *NewBB) override; CloningAction handleInvoke(ValueToValueMapTy &VMap, const InvokeInst *Invoke, BasicBlock *NewBB) override; CloningAction handleResume(ValueToValueMapTy &VMap, const ResumeInst *Resume, BasicBlock *NewBB) override; - CloningAction handleCompare(ValueToValueMapTy &VMap, - const CmpInst *Compare, BasicBlock *NewBB) override; + CloningAction handleCompare(ValueToValueMapTy &VMap, const CmpInst *Compare, + BasicBlock *NewBB) override; CloningAction handleLandingPad(ValueToValueMapTy &VMap, const LandingPadInst *LPad, BasicBlock *NewBB) override; @@ -323,47 +399,59 @@ FunctionPass *llvm::createWinEHPass(const TargetMachine *TM) { return new WinEHPrepare(TM); } -// FIXME: Remove this once the backend can handle the prepared IR. -static cl::opt - SEHPrepare("sehprepare", cl::Hidden, - cl::desc("Prepare functions with SEH personalities")); +static bool +findExceptionalConstructs(Function &Fn, + SmallVectorImpl &LPads, + SmallVectorImpl &Resumes, + SmallVectorImpl &EntryBlocks) { + bool ForExplicitEH = false; + for (BasicBlock &BB : Fn) { + Instruction *First = BB.getFirstNonPHI(); + if (auto *LP = dyn_cast(First)) { + LPads.push_back(LP); + } else if (First->isEHPad()) { + if (!ForExplicitEH) + EntryBlocks.push_back(&Fn.getEntryBlock()); + if (!isa(First) && !isa(First)) + EntryBlocks.push_back(&BB); + ForExplicitEH = true; + } + if (auto *Resume = dyn_cast(BB.getTerminator())) + Resumes.push_back(Resume); + } + return ForExplicitEH; +} bool WinEHPrepare::runOnFunction(Function &Fn) { + if (!Fn.hasPersonalityFn()) + return false; + // No need to prepare outlined handlers. if (Fn.hasFnAttribute("wineh-parent")) return false; + // Classify the personality to see what kind of preparation we need. + Personality = classifyEHPersonality(Fn.getPersonalityFn()); + + // Do nothing if this is not a funclet-based personality. + if (!isFuncletEHPersonality(Personality)) + return false; + SmallVector LPads; SmallVector Resumes; - for (BasicBlock &BB : Fn) { - if (auto *LP = BB.getLandingPadInst()) - LPads.push_back(LP); - if (auto *Resume = dyn_cast(BB.getTerminator())) - Resumes.push_back(Resume); - } + SmallVector EntryBlocks; + bool ForExplicitEH = + findExceptionalConstructs(Fn, LPads, Resumes, EntryBlocks); + + if (ForExplicitEH) + return prepareExplicitEH(Fn, EntryBlocks); // No need to prepare functions that lack landing pads. if (LPads.empty()) return false; - // Classify the personality to see what kind of preparation we need. - Personality = classifyEHPersonality(LPads.back()->getPersonalityFn()); - - // Do nothing if this is not an MSVC personality. - if (!isMSVCEHPersonality(Personality)) - return false; - DT = &getAnalysis().getDomTree(); - - if (isAsynchronousEHPersonality(Personality) && !SEHPrepare) { - // Replace all resume instructions with unreachable. - // FIXME: Remove this once the backend can handle the prepared IR. - for (ResumeInst *Resume : Resumes) { - IRBuilder<>(Resume).CreateUnreachable(); - Resume->eraseFromParent(); - } - return true; - } + LibInfo = &getAnalysis().getTLI(); // If there were any landing pads, prepareExceptionHandlers will make changes. prepareExceptionHandlers(Fn, LPads); @@ -374,6 +462,7 @@ bool WinEHPrepare::doFinalization(Module &M) { return false; } void WinEHPrepare::getAnalysisUsage(AnalysisUsage &AU) const { AU.addRequired(); + AU.addRequired(); } static bool isSelectorDispatch(BasicBlock *BB, BasicBlock *&CatchHandler, @@ -405,13 +494,62 @@ static void findReachableBlocks(SmallPtrSetImpl &ReachableBBs, } } +// Attempt to find an instruction where a block can be split before +// a call to llvm.eh.begincatch and its operands. If the block +// begins with the begincatch call or one of its adjacent operands +// the block will not be split. +static Instruction *findBeginCatchSplitPoint(BasicBlock *BB, + IntrinsicInst *II) { + // If the begincatch call is already the first instruction in the block, + // don't split. + Instruction *FirstNonPHI = BB->getFirstNonPHI(); + if (II == FirstNonPHI) + return nullptr; + + // If either operand is in the same basic block as the instruction and + // isn't used by another instruction before the begincatch call, include it + // in the split block. + auto *Op0 = dyn_cast(II->getOperand(0)); + auto *Op1 = dyn_cast(II->getOperand(1)); + + Instruction *I = II->getPrevNode(); + Instruction *LastI = II; + + while (I == Op0 || I == Op1) { + // If the block begins with one of the operands and there are no other + // instructions between the operand and the begincatch call, don't split. + if (I == FirstNonPHI) + return nullptr; + + LastI = I; + I = I->getPrevNode(); + } + + // If there is at least one instruction in the block before the begincatch + // call and its operands, split the block at either the begincatch or + // its operand. + return LastI; +} + /// Find all points where exceptional control rejoins normal control flow via /// llvm.eh.endcatch. Add them to the normal bb reachability worklist. -static void findCXXEHReturnPoints(Function &F, - SetVector &EHReturnBlocks) { +void WinEHPrepare::findCXXEHReturnPoints( + Function &F, SetVector &EHReturnBlocks) { for (auto BBI = F.begin(), BBE = F.end(); BBI != BBE; ++BBI) { BasicBlock *BB = BBI; for (Instruction &I : *BB) { + if (match(&I, m_Intrinsic())) { + Instruction *SplitPt = + findBeginCatchSplitPoint(BB, cast(&I)); + if (SplitPt) { + // Split the block before the llvm.eh.begincatch call to allow + // cleanup and catch code to be distinguished later. + // Do not update BBI because we still need to process the + // portion of the block that we are splitting off. + SplitBlock(BB, SplitPt, DT); + break; + } + } if (match(&I, m_Intrinsic())) { // Split the block after the call to llvm.eh.endcatch if there is // anything other than an unconditional branch, or if the successor @@ -421,7 +559,7 @@ static void findCXXEHReturnPoints(Function &F, isa(Br->getSuccessor(0)->begin())) { DEBUG(dbgs() << "splitting block " << BB->getName() << " with llvm.eh.endcatch\n"); - BBI = BB->splitBasicBlock(I.getNextNode(), "ehreturn"); + BBI = SplitBlock(BB, I.getNextNode(), DT); } // The next BB is normal control flow. EHReturnBlocks.insert(BB->getTerminator()->getSuccessor(0)); @@ -442,8 +580,8 @@ static bool isCatchAllLandingPad(const BasicBlock *BB) { /// Find all points where exceptions control rejoins normal control flow via /// selector dispatch. -static void findSEHEHReturnPoints(Function &F, - SetVector &EHReturnBlocks) { +void WinEHPrepare::findSEHEHReturnPoints( + Function &F, SetVector &EHReturnBlocks) { for (auto BBI = F.begin(), BBE = F.end(); BBI != BBE; ++BBI) { BasicBlock *BB = BBI; // If the landingpad is a catch-all, treat the whole lpad as if it is @@ -460,9 +598,9 @@ static void findSEHEHReturnPoints(Function &F, BasicBlock *NextBB; Constant *Selector; if (isSelectorDispatch(BB, CatchHandler, Selector, NextBB)) { - // Split the edge if there is a phi node. Returning from EH to a phi node - // is just as impossible as having a phi after an indirectbr. - if (isa(CatchHandler->begin())) { + // Split the edge if there are multiple predecessors. This creates a place + // where we can insert EH recovery code. + if (!CatchHandler->getSinglePredecessor()) { DEBUG(dbgs() << "splitting EH return edge from " << BB->getName() << " to " << CatchHandler->getName() << '\n'); BBI = CatchHandler = SplitCriticalEdge( @@ -473,13 +611,8 @@ static void findSEHEHReturnPoints(Function &F, } } -/// Ensure that all values live into and out of exception handlers are stored -/// in memory. -/// FIXME: This falls down when values are defined in one handler and live into -/// another handler. For example, a cleanup defines a value used only by a -/// catch handler. -void WinEHPrepare::demoteValuesLiveAcrossHandlers( - Function &F, SmallVectorImpl &LPads) { +void WinEHPrepare::identifyEHBlocks(Function &F, + SmallVectorImpl &LPads) { DEBUG(dbgs() << "Demoting values live across exception handlers in function " << F.getName() << '\n'); @@ -489,10 +622,6 @@ void WinEHPrepare::demoteValuesLiveAcrossHandlers( // - Exceptional blocks are blocks reachable from landingpads. Analysis does // not follow llvm.eh.endcatch blocks, which mark a transition from // exceptional to normal control. - SmallPtrSet NormalBlocks; - SmallPtrSet EHBlocks; - SetVector EHReturnBlocks; - SetVector Worklist; if (Personality == EHPersonality::MSVC_CXX) findCXXEHReturnPoints(F, EHReturnBlocks); @@ -505,8 +634,8 @@ void WinEHPrepare::demoteValuesLiveAcrossHandlers( dbgs() << " " << BB->getName() << '\n'; }); - // Join points should not have phis at this point, unless they are a - // landingpad, in which case we will demote their phis later. +// Join points should not have phis at this point, unless they are a +// landingpad, in which case we will demote their phis later. #ifndef NDEBUG for (BasicBlock *BB : EHReturnBlocks) assert((BB->isLandingPad() || !isa(BB->begin())) && @@ -515,6 +644,7 @@ void WinEHPrepare::demoteValuesLiveAcrossHandlers( // Normal blocks are the blocks reachable from the entry block and all EH // return points. + SetVector Worklist; Worklist = EHReturnBlocks; Worklist.insert(&F.getEntryBlock()); findReachableBlocks(NormalBlocks, Worklist, nullptr); @@ -536,6 +666,41 @@ void WinEHPrepare::demoteValuesLiveAcrossHandlers( dbgs() << " " << BB->getName() << '\n'; }); +} + +/// Ensure that all values live into and out of exception handlers are stored +/// in memory. +/// FIXME: This falls down when values are defined in one handler and live into +/// another handler. For example, a cleanup defines a value used only by a +/// catch handler. +void WinEHPrepare::demoteValuesLiveAcrossHandlers( + Function &F, SmallVectorImpl &LPads) { + DEBUG(dbgs() << "Demoting values live across exception handlers in function " + << F.getName() << '\n'); + + // identifyEHBlocks() should have been called before this function. + assert(!NormalBlocks.empty()); + + // Try to avoid demoting EH pointer and selector values. They get in the way + // of our pattern matching. + SmallPtrSet EHVals; + for (BasicBlock &BB : F) { + LandingPadInst *LP = BB.getLandingPadInst(); + if (!LP) + continue; + EHVals.insert(LP); + for (User *U : LP->users()) { + auto *EI = dyn_cast(U); + if (!EI) + continue; + EHVals.insert(EI); + for (User *U2 : EI->users()) { + if (auto *PN = dyn_cast(U2)) + EHVals.insert(PN); + } + } + } + SetVector ArgsToDemote; SetVector InstrsToDemote; for (BasicBlock &BB : F) { @@ -561,7 +726,11 @@ void WinEHPrepare::demoteValuesLiveAcrossHandlers( continue; } + // Don't demote EH values. auto *OpI = cast(Op); + if (EHVals.count(OpI)) + continue; + BasicBlock *OpBB = OpI->getParent(); // If a value is produced and consumed in the same BB, we don't need to // demote it. @@ -626,6 +795,7 @@ bool WinEHPrepare::prepareExceptionHandlers( return false; } + identifyEHBlocks(F, LPads); demoteValuesLiveAcrossHandlers(F, LPads); // These containers are used to re-map frame variables that are used in @@ -643,6 +813,31 @@ bool WinEHPrepare::prepareExceptionHandlers( Type *Int32Type = Type::getInt32Ty(Context); Function *ActionIntrin = Intrinsic::getDeclaration(M, Intrinsic::eh_actions); + if (isAsynchronousEHPersonality(Personality)) { + // FIXME: Switch the ehptr type to i32 and then switch this. + SEHExceptionCodeSlot = + new AllocaInst(Int8PtrType, nullptr, "seh_exception_code", + F.getEntryBlock().getFirstInsertionPt()); + } + + // In order to handle the case where one outlined catch handler returns + // to a block within another outlined catch handler that would otherwise + // be unreachable, we need to outline the nested landing pad before we + // outline the landing pad which encloses it. + if (!isAsynchronousEHPersonality(Personality)) + std::sort(LPads.begin(), LPads.end(), + [this](LandingPadInst *const &L, LandingPadInst *const &R) { + return DT->properlyDominates(R->getParent(), L->getParent()); + }); + + // This container stores the llvm.eh.recover and IndirectBr instructions + // that make up the body of each landing pad after it has been outlined. + // We need to defer the population of the target list for the indirectbr + // until all landing pads have been outlined so that we can handle the + // case of blocks in the target that are reached only from nested + // landing pads. + SmallVector, 4> LPadImpls; + for (LandingPadInst *LPad : LPads) { // Look for evidence that this landingpad has already been processed. bool LPadHasActionList = false; @@ -685,45 +880,55 @@ bool WinEHPrepare::prepareExceptionHandlers( outlineHandler(Action, &F, LPad, StartBB, FrameVarInfo); } - // Replace the landing pad with a new llvm.eh.action based landing pad. - BasicBlock *NewLPadBB = BasicBlock::Create(Context, "lpad", &F, LPadBB); - assert(!isa(LPadBB->begin())); - auto *NewLPad = cast(LPad->clone()); - NewLPadBB->getInstList().push_back(NewLPad); - while (!pred_empty(LPadBB)) { - auto *pred = *pred_begin(LPadBB); - InvokeInst *Invoke = cast(pred->getTerminator()); - Invoke->setUnwindDest(NewLPadBB); - } - - // Replace the mapping of any nested landing pad that previously mapped - // to this landing pad with a referenced to the cloned version. - for (auto &LPadPair : NestedLPtoOriginalLP) { - const LandingPadInst *OriginalLPad = LPadPair.second; - if (OriginalLPad == LPad) { - LPadPair.second = NewLPad; - } - } + // Split the block after the landingpad instruction so that it is just a + // call to llvm.eh.actions followed by indirectbr. + assert(!isa(LPadBB->begin()) && "lpad phi not removed"); + SplitBlock(LPadBB, LPad->getNextNode(), DT); + // Erase the branch inserted by the split so we can insert indirectbr. + LPadBB->getTerminator()->eraseFromParent(); // Replace all extracted values with undef and ultimately replace the // landingpad with undef. - // FIXME: This doesn't handle SEH GetExceptionCode(). For now, we just give - // out undef until we figure out the codegen support. - SmallVector Extracts; + SmallVector SEHCodeUses; + SmallVector EHUndefs; for (User *U : LPad->users()) { auto *E = dyn_cast(U); if (!E) continue; assert(E->getNumIndices() == 1 && "Unexpected operation: extracting both landing pad values"); - Extracts.push_back(E); + unsigned Idx = *E->idx_begin(); + assert((Idx == 0 || Idx == 1) && "unexpected index"); + if (Idx == 0 && isAsynchronousEHPersonality(Personality)) + SEHCodeUses.push_back(E); + else + EHUndefs.push_back(E); } - for (Instruction *E : Extracts) { + for (Instruction *E : EHUndefs) { E->replaceAllUsesWith(UndefValue::get(E->getType())); E->eraseFromParent(); } LPad->replaceAllUsesWith(UndefValue::get(LPad->getType())); + // Rewrite uses of the exception pointer to loads of an alloca. + while (!SEHCodeUses.empty()) { + Instruction *E = SEHCodeUses.pop_back_val(); + SmallVector Uses; + for (Use &U : E->uses()) + Uses.push_back(&U); + for (Use *U : Uses) { + auto *I = cast(U->getUser()); + if (isa(I)) + continue; + if (auto *Phi = dyn_cast(I)) + SEHCodeUses.push_back(Phi); + else + U->set(new LoadInst(SEHExceptionCodeSlot, "sehcode", false, I)); + } + E->replaceAllUsesWith(UndefValue::get(E->getType())); + E->eraseFromParent(); + } + // Add a call to describe the actions for this landing pad. std::vector ActionArgs; for (ActionHandler *Action : Actions) { @@ -748,9 +953,8 @@ bool WinEHPrepare::prepareExceptionHandlers( ActionArgs.push_back(Action->getHandlerBlockOrFunc()); } CallInst *Recover = - CallInst::Create(ActionIntrin, ActionArgs, "recover", NewLPadBB); + CallInst::Create(ActionIntrin, ActionArgs, "recover", LPadBB); - // Add an indirect branch listing possible successors of the catch handlers. SetVector ReturnTargets; for (ActionHandler *Action : Actions) { if (auto *CatchAction = dyn_cast(Action)) { @@ -759,9 +963,16 @@ bool WinEHPrepare::prepareExceptionHandlers( } } IndirectBrInst *Branch = - IndirectBrInst::Create(Recover, ReturnTargets.size(), NewLPadBB); + IndirectBrInst::Create(Recover, ReturnTargets.size(), LPadBB); for (BasicBlock *Target : ReturnTargets) Branch->addDestination(Target); + + if (!isAsynchronousEHPersonality(Personality)) { + // C++ EH must repopulate the targets later to handle the case of + // targets that are reached indirectly through nested landing pads. + LPadImpls.push_back(std::make_pair(Recover, Branch)); + } + } // End for each landingpad // If nothing got outlined, there is no more processing to be done. @@ -775,6 +986,50 @@ bool WinEHPrepare::prepareExceptionHandlers( completeNestedLandingPad(&F, LPadPair.first, LPadPair.second, FrameVarInfo); NestedLPtoOriginalLP.clear(); + // Update the indirectbr instructions' target lists if necessary. + SetVector CheckedTargets; + SmallVector, 4> ActionList; + for (auto &LPadImplPair : LPadImpls) { + IntrinsicInst *Recover = cast(LPadImplPair.first); + IndirectBrInst *Branch = LPadImplPair.second; + + // Get a list of handlers called by + parseEHActions(Recover, ActionList); + + // Add an indirect branch listing possible successors of the catch handlers. + SetVector ReturnTargets; + for (const auto &Action : ActionList) { + if (auto *CA = dyn_cast(Action.get())) { + Function *Handler = cast(CA->getHandlerBlockOrFunc()); + getPossibleReturnTargets(&F, Handler, ReturnTargets); + } + } + ActionList.clear(); + // Clear any targets we already knew about. + for (unsigned int I = 0, E = Branch->getNumDestinations(); I < E; ++I) { + BasicBlock *KnownTarget = Branch->getDestination(I); + if (ReturnTargets.count(KnownTarget)) + ReturnTargets.remove(KnownTarget); + } + for (BasicBlock *Target : ReturnTargets) { + Branch->addDestination(Target); + // The target may be a block that we excepted to get pruned. + // If it is, it may contain a call to llvm.eh.endcatch. + if (CheckedTargets.insert(Target)) { + // Earlier preparations guarantee that all calls to llvm.eh.endcatch + // will be followed by an unconditional branch. + auto *Br = dyn_cast(Target->getTerminator()); + if (Br && Br->isUnconditional() && + Br != Target->getFirstNonPHIOrDbgOrLifetime()) { + Instruction *Prev = Br->getPrevNode(); + if (match(cast(Prev), m_Intrinsic())) + Prev->eraseFromParent(); + } + } + } + } + LPadImpls.clear(); + F.addFnAttr("wineh-parent", F.getName()); // Delete any blocks that were only used by handlers that were outlined above. @@ -785,16 +1040,16 @@ bool WinEHPrepare::prepareExceptionHandlers( Builder.SetInsertPoint(Entry->getFirstInsertionPt()); Function *FrameEscapeFn = - Intrinsic::getDeclaration(M, Intrinsic::frameescape); + Intrinsic::getDeclaration(M, Intrinsic::localescape); Function *RecoverFrameFn = - Intrinsic::getDeclaration(M, Intrinsic::framerecover); + Intrinsic::getDeclaration(M, Intrinsic::localrecover); SmallVector AllocasToEscape; - // Scan the entry block for an existing call to llvm.frameescape. We need to + // Scan the entry block for an existing call to llvm.localescape. We need to // keep escaping those objects. for (Instruction &I : F.front()) { auto *II = dyn_cast(&I); - if (II && II->getIntrinsicID() == Intrinsic::frameescape) { + if (II && II->getIntrinsicID() == Intrinsic::localescape) { auto Args = II->arg_operands(); AllocasToEscape.append(Args.begin(), Args.end()); II->eraseFromParent(); @@ -803,7 +1058,7 @@ bool WinEHPrepare::prepareExceptionHandlers( } // Finally, replace all of the temporary allocas for frame variables used in - // the outlined handlers with calls to llvm.framerecover. + // the outlined handlers with calls to llvm.localrecover. for (auto &VarInfoEntry : FrameVarInfo) { Value *ParentVal = VarInfoEntry.first; TinyPtrVector &Allocas = VarInfoEntry.second; @@ -821,19 +1076,23 @@ bool WinEHPrepare::prepareExceptionHandlers( if (TempAlloca == getCatchObjectSentinel()) continue; // Skip catch parameter sentinels. Function *HandlerFn = TempAlloca->getParent()->getParent(); - // FIXME: Sink this GEP into the blocks where it is used. + llvm::Value *FP = HandlerToParentFP[HandlerFn]; + assert(FP); + + // FIXME: Sink this localrecover into the blocks where it is used. Builder.SetInsertPoint(TempAlloca); Builder.SetCurrentDebugLocation(TempAlloca->getDebugLoc()); Value *RecoverArgs[] = { - Builder.CreateBitCast(&F, Int8PtrType, ""), - &(HandlerFn->getArgumentList().back()), + Builder.CreateBitCast(&F, Int8PtrType, ""), FP, llvm::ConstantInt::get(Int32Type, AllocasToEscape.size() - 1)}; - Value *RecoveredAlloca = Builder.CreateCall(RecoverFrameFn, RecoverArgs); + Instruction *RecoveredAlloca = + Builder.CreateCall(RecoverFrameFn, RecoverArgs); + // Add a pointer bitcast if the alloca wasn't an i8. if (RecoveredAlloca->getType() != TempAlloca->getType()) { RecoveredAlloca->setName(Twine(TempAlloca->getName()) + ".i8"); - RecoveredAlloca = - Builder.CreateBitCast(RecoveredAlloca, TempAlloca->getType()); + RecoveredAlloca = cast( + Builder.CreateBitCast(RecoveredAlloca, TempAlloca->getType())); } TempAlloca->replaceAllUsesWith(RecoveredAlloca); TempAlloca->removeFromParent(); @@ -842,16 +1101,37 @@ bool WinEHPrepare::prepareExceptionHandlers( } } // End for each FrameVarInfo entry. - // Insert 'call void (...)* @llvm.frameescape(...)' at the end of the entry + // Insert 'call void (...)* @llvm.localescape(...)' at the end of the entry // block. Builder.SetInsertPoint(&F.getEntryBlock().back()); Builder.CreateCall(FrameEscapeFn, AllocasToEscape); + if (SEHExceptionCodeSlot) { + if (isAllocaPromotable(SEHExceptionCodeSlot)) { + SmallPtrSet UserBlocks; + for (User *U : SEHExceptionCodeSlot->users()) { + if (auto *Inst = dyn_cast(U)) + UserBlocks.insert(Inst->getParent()); + } + PromoteMemToReg(SEHExceptionCodeSlot, *DT); + // After the promotion, kill off dead instructions. + for (BasicBlock *BB : UserBlocks) + SimplifyInstructionsInBlock(BB, LibInfo); + } + } + // Clean up the handler action maps we created for this function DeleteContainerSeconds(CatchHandlerMap); CatchHandlerMap.clear(); DeleteContainerSeconds(CleanupHandlerMap); CleanupHandlerMap.clear(); + HandlerToParentFP.clear(); + DT = nullptr; + LibInfo = nullptr; + SEHExceptionCodeSlot = nullptr; + EHBlocks.clear(); + NormalBlocks.clear(); + EHReturnBlocks.clear(); return HandlersOutlined; } @@ -893,6 +1173,42 @@ void WinEHPrepare::promoteLandingPadValues(LandingPadInst *LPad) { RecursivelyDeleteTriviallyDeadInstructions(U); } +void WinEHPrepare::getPossibleReturnTargets(Function *ParentF, + Function *HandlerF, + SetVector &Targets) { + for (BasicBlock &BB : *HandlerF) { + // If the handler contains landing pads, check for any + // handlers that may return directly to a block in the + // parent function. + if (auto *LPI = BB.getLandingPadInst()) { + IntrinsicInst *Recover = cast(LPI->getNextNode()); + SmallVector, 4> ActionList; + parseEHActions(Recover, ActionList); + for (const auto &Action : ActionList) { + if (auto *CH = dyn_cast(Action.get())) { + Function *NestedF = cast(CH->getHandlerBlockOrFunc()); + getPossibleReturnTargets(ParentF, NestedF, Targets); + } + } + } + + auto *Ret = dyn_cast(BB.getTerminator()); + if (!Ret) + continue; + + // Handler functions must always return a block address. + BlockAddress *BA = cast(Ret->getReturnValue()); + + // If this is the handler for a nested landing pad, the + // return address may have been remapped to a block in the + // parent handler. We're not interested in those. + if (BA->getFunction() != ParentF) + continue; + + Targets.insert(BA->getBasicBlock()); + } +} + void WinEHPrepare::completeNestedLandingPad(Function *ParentFn, LandingPadInst *OutlinedLPad, const LandingPadInst *OriginalLPad, @@ -901,10 +1217,19 @@ void WinEHPrepare::completeNestedLandingPad(Function *ParentFn, // temporarily inserted as its terminator. LLVMContext &Context = ParentFn->getContext(); BasicBlock *OutlinedBB = OutlinedLPad->getParent(); - assert(isa(OutlinedBB->getTerminator())); - OutlinedBB->getTerminator()->eraseFromParent(); - // That should leave OutlinedLPad as the last instruction in its block. - assert(&OutlinedBB->back() == OutlinedLPad); + // If the nested landing pad was outlined before the landing pad that enclosed + // it, it will already be in outlined form. In that case, we just need to see + // if the returns and the enclosing branch instruction need to be updated. + IndirectBrInst *Branch = + dyn_cast(OutlinedBB->getTerminator()); + if (!Branch) { + // If the landing pad wasn't in outlined form, it should be a stub with + // an unreachable terminator. + assert(isa(OutlinedBB->getTerminator())); + OutlinedBB->getTerminator()->eraseFromParent(); + // That should leave OutlinedLPad as the last instruction in its block. + assert(&OutlinedBB->back() == OutlinedLPad); + } // The original landing pad will have already had its action intrinsic // built by the outlining loop. We need to clone that into the outlined @@ -917,16 +1242,14 @@ void WinEHPrepare::completeNestedLandingPad(Function *ParentFn, ++II; // The instruction after the landing pad should now be a call to eh.actions. const Instruction *Recover = II; - assert(match(Recover, m_Intrinsic())); - IntrinsicInst *EHActions = cast(Recover->clone()); + const IntrinsicInst *EHActions = cast(Recover); - // Remap the exception variables into the outlined function. - WinEHFrameVariableMaterializer Materializer(OutlinedHandlerFn, FrameVarInfo); + // Remap the return target in the nested handler. SmallVector ActionTargets; - SmallVector ActionList; + SmallVector, 4> ActionList; parseEHActions(EHActions, ActionList); - for (auto *Action : ActionList) { - auto *Catch = dyn_cast(Action); + for (const auto &Action : ActionList) { + auto *Catch = dyn_cast(Action.get()); if (!Catch) continue; // The dyn_cast to function here selects C++ catch handlers and skips @@ -948,7 +1271,7 @@ void WinEHPrepare::completeNestedLandingPad(Function *ParentFn, // should be a block that was outlined into OutlinedHandlerFn. assert(BA->getFunction() == ParentFn); - // Ignore targets that aren't part of OutlinedHandlerFn. + // Ignore targets that aren't part of an outlined handler function. if (!LPadTargetBlocks.count(BA->getBasicBlock())) continue; @@ -964,15 +1287,26 @@ void WinEHPrepare::completeNestedLandingPad(Function *ParentFn, ActionTargets.push_back(NewBA); } } - DeleteContainerPointers(ActionList); ActionList.clear(); - OutlinedBB->getInstList().push_back(EHActions); - // Insert an indirect branch into the outlined landing pad BB. - IndirectBrInst *IBr = IndirectBrInst::Create(EHActions, 0, OutlinedBB); - // Add the previously collected action targets. - for (auto *Target : ActionTargets) - IBr->addDestination(Target->getBasicBlock()); + if (Branch) { + // If the landing pad was already in outlined form, just update its targets. + for (unsigned int I = Branch->getNumDestinations(); I > 0; --I) + Branch->removeDestination(I); + // Add the previously collected action targets. + for (auto *Target : ActionTargets) + Branch->addDestination(Target->getBasicBlock()); + } else { + // If the landing pad was previously stubbed out, fill in its outlined form. + IntrinsicInst *NewEHActions = cast(EHActions->clone()); + OutlinedBB->getInstList().push_back(NewEHActions); + + // Insert an indirect branch into the outlined landing pad BB. + IndirectBrInst *IBr = IndirectBrInst::Create(NewEHActions, 0, OutlinedBB); + // Add the previously collected action targets. + for (auto *Target : ActionTargets) + IBr->addDestination(Target->getBasicBlock()); + } } // This function examines a block to determine whether the block ends with a @@ -1018,8 +1352,7 @@ static bool isCatchBlock(BasicBlock *BB) { return false; } -static BasicBlock *createStubLandingPad(Function *Handler, - Value *PersonalityFn) { +static BasicBlock *createStubLandingPad(Function *Handler) { // FIXME: Finish this! LLVMContext &Context = Handler->getContext(); BasicBlock *StubBB = BasicBlock::Create(Context, "stub"); @@ -1028,11 +1361,11 @@ static BasicBlock *createStubLandingPad(Function *Handler, LandingPadInst *LPad = Builder.CreateLandingPad( llvm::StructType::get(Type::getInt8PtrTy(Context), Type::getInt32Ty(Context), nullptr), - PersonalityFn, 0); + 0); // Insert a call to llvm.eh.actions so that we don't try to outline this lpad. - Function *ActionIntrin = Intrinsic::getDeclaration(Handler->getParent(), - Intrinsic::eh_actions); - Builder.CreateCall(ActionIntrin, "recover"); + Function *ActionIntrin = + Intrinsic::getDeclaration(Handler->getParent(), Intrinsic::eh_actions); + Builder.CreateCall(ActionIntrin, {}, "recover"); LPad->setCleanup(true); Builder.CreateUnreachable(); return StubBB; @@ -1043,8 +1376,7 @@ static BasicBlock *createStubLandingPad(Function *Handler, // landing pad if none is found. The code that generates the .xdata tables for // the handler needs at least one landing pad to identify the parent function's // personality. -void WinEHPrepare::addStubInvokeToHandlerIfNeeded(Function *Handler, - Value *PersonalityFn) { +void WinEHPrepare::addStubInvokeToHandlerIfNeeded(Function *Handler) { ReturnInst *Ret = nullptr; UnreachableInst *Unreached = nullptr; for (BasicBlock &BB : *Handler) { @@ -1071,46 +1403,79 @@ void WinEHPrepare::addStubInvokeToHandlerIfNeeded(Function *Handler, else Term = Unreached; BasicBlock *OldRetBB = Term->getParent(); - BasicBlock *NewRetBB = SplitBlock(OldRetBB, Term); + BasicBlock *NewRetBB = SplitBlock(OldRetBB, Term, DT); // SplitBlock adds an unconditional branch instruction at the end of the // parent block. We want to replace that with an invoke call, so we can // erase it now. OldRetBB->getTerminator()->eraseFromParent(); - BasicBlock *StubLandingPad = createStubLandingPad(Handler, PersonalityFn); + BasicBlock *StubLandingPad = createStubLandingPad(Handler); Function *F = Intrinsic::getDeclaration(Handler->getParent(), Intrinsic::donothing); InvokeInst::Create(F, NewRetBB, StubLandingPad, None, "", OldRetBB); } +// FIXME: Consider sinking this into lib/Target/X86 somehow. TargetLowering +// usually doesn't build LLVM IR, so that's probably the wrong place. +Function *WinEHPrepare::createHandlerFunc(Function *ParentFn, Type *RetTy, + const Twine &Name, Module *M, + Value *&ParentFP) { + // x64 uses a two-argument prototype where the parent FP is the second + // argument. x86 uses no arguments, just the incoming EBP value. + LLVMContext &Context = M->getContext(); + Type *Int8PtrType = Type::getInt8PtrTy(Context); + FunctionType *FnType; + if (TheTriple.getArch() == Triple::x86_64) { + Type *ArgTys[2] = {Int8PtrType, Int8PtrType}; + FnType = FunctionType::get(RetTy, ArgTys, false); + } else { + FnType = FunctionType::get(RetTy, None, false); + } + + Function *Handler = + Function::Create(FnType, GlobalVariable::InternalLinkage, Name, M); + BasicBlock *Entry = BasicBlock::Create(Context, "entry"); + Handler->getBasicBlockList().push_front(Entry); + if (TheTriple.getArch() == Triple::x86_64) { + ParentFP = &(Handler->getArgumentList().back()); + } else { + assert(M); + Function *FrameAddressFn = + Intrinsic::getDeclaration(M, Intrinsic::frameaddress); + Function *RecoverFPFn = + Intrinsic::getDeclaration(M, Intrinsic::x86_seh_recoverfp); + IRBuilder<> Builder(&Handler->getEntryBlock()); + Value *EBP = + Builder.CreateCall(FrameAddressFn, {Builder.getInt32(1)}, "ebp"); + Value *ParentI8Fn = Builder.CreateBitCast(ParentFn, Int8PtrType); + ParentFP = Builder.CreateCall(RecoverFPFn, {ParentI8Fn, EBP}); + } + return Handler; +} + bool WinEHPrepare::outlineHandler(ActionHandler *Action, Function *SrcFn, LandingPadInst *LPad, BasicBlock *StartBB, FrameVarInfoMap &VarInfo) { Module *M = SrcFn->getParent(); LLVMContext &Context = M->getContext(); + Type *Int8PtrType = Type::getInt8PtrTy(Context); // Create a new function to receive the handler contents. - Type *Int8PtrType = Type::getInt8PtrTy(Context); - std::vector ArgTys; - ArgTys.push_back(Int8PtrType); - ArgTys.push_back(Int8PtrType); + Value *ParentFP; Function *Handler; if (Action->getType() == Catch) { - FunctionType *FnType = FunctionType::get(Int8PtrType, ArgTys, false); - Handler = Function::Create(FnType, GlobalVariable::InternalLinkage, - SrcFn->getName() + ".catch", M); + Handler = createHandlerFunc(SrcFn, Int8PtrType, SrcFn->getName() + ".catch", M, + ParentFP); } else { - FunctionType *FnType = - FunctionType::get(Type::getVoidTy(Context), ArgTys, false); - Handler = Function::Create(FnType, GlobalVariable::InternalLinkage, - SrcFn->getName() + ".cleanup", M); + Handler = createHandlerFunc(SrcFn, Type::getVoidTy(Context), + SrcFn->getName() + ".cleanup", M, ParentFP); } - + Handler->setPersonalityFn(SrcFn->getPersonalityFn()); + HandlerToParentFP[Handler] = ParentFP; Handler->addFnAttr("wineh-parent", SrcFn->getName()); + BasicBlock *Entry = &Handler->getEntryBlock(); // Generate a standard prolog to setup the frame recovery structure. IRBuilder<> Builder(Context); - BasicBlock *Entry = BasicBlock::Create(Context, "entry"); - Handler->getBasicBlockList().push_front(Entry); Builder.SetInsertPoint(Entry); Builder.SetCurrentDebugLocation(LPad->getDebugLoc()); @@ -1123,12 +1488,14 @@ bool WinEHPrepare::outlineHandler(ActionHandler *Action, Function *SrcFn, LPadMap.mapLandingPad(LPad); if (auto *CatchAction = dyn_cast(Action)) { Constant *Sel = CatchAction->getSelector(); - Director.reset(new WinEHCatchDirector(Handler, Sel, VarInfo, LPadMap, - NestedLPtoOriginalLP)); + Director.reset(new WinEHCatchDirector(Handler, ParentFP, Sel, VarInfo, + LPadMap, NestedLPtoOriginalLP, DT, + EHBlocks)); LPadMap.remapEHValues(VMap, UndefValue::get(Int8PtrType), ConstantInt::get(Type::getInt32Ty(Context), 1)); } else { - Director.reset(new WinEHCleanupDirector(Handler, VarInfo, LPadMap)); + Director.reset( + new WinEHCleanupDirector(Handler, ParentFP, VarInfo, LPadMap)); LPadMap.remapEHValues(VMap, UndefValue::get(Int8PtrType), UndefValue::get(Type::getInt32Ty(Context))); } @@ -1165,13 +1532,22 @@ bool WinEHPrepare::outlineHandler(ActionHandler *Action, Function *SrcFn, /*ModuleLevelChanges=*/false, Returns, "", &OutlinedFunctionInfo, Director.get()); - // Move all the instructions in the first cloned block into our entry block. - BasicBlock *FirstClonedBB = std::next(Function::iterator(Entry)); - Entry->getInstList().splice(Entry->end(), FirstClonedBB->getInstList()); - FirstClonedBB->eraseFromParent(); + // Move all the instructions in the cloned "entry" block into our entry block. + // Depending on how the parent function was laid out, the block that will + // correspond to the outlined entry block may not be the first block in the + // list. We can recognize it, however, as the cloned block which has no + // predecessors. Any other block wouldn't have been cloned if it didn't + // have a predecessor which was also cloned. + Function::iterator ClonedIt = std::next(Function::iterator(Entry)); + while (!pred_empty(ClonedIt)) + ++ClonedIt; + BasicBlock *ClonedEntryBB = ClonedIt; + assert(ClonedEntryBB); + Entry->getInstList().splice(Entry->end(), ClonedEntryBB->getInstList()); + ClonedEntryBB->eraseFromParent(); // Make sure we can identify the handler's personality later. - addStubInvokeToHandlerIfNeeded(Handler, LPad->getPersonalityFn()); + addStubInvokeToHandlerIfNeeded(Handler); if (auto *CatchAction = dyn_cast(Action)) { WinEHCatchDirector *CatchDirector = @@ -1234,9 +1610,14 @@ void WinEHPrepare::processSEHCatchHandler(CatchHandler *CatchAction, } else { // This must be a catch-all. Split the block after the landingpad. assert(CatchAction->getSelector()->isNullValue() && "expected catch-all"); - HandlerBB = - StartBB->splitBasicBlock(StartBB->getFirstInsertionPt(), "catch.all"); + HandlerBB = SplitBlock(StartBB, StartBB->getFirstInsertionPt(), DT); } + IRBuilder<> Builder(HandlerBB->getFirstInsertionPt()); + Function *EHCodeFn = Intrinsic::getDeclaration( + StartBB->getParent()->getParent(), Intrinsic::eh_exceptioncode_old); + Value *Code = Builder.CreateCall(EHCodeFn, {}, "sehcode"); + Code = Builder.CreateIntToPtr(Code, SEHExceptionCodeSlot->getAllocatedType()); + Builder.CreateStore(Code, SEHExceptionCodeSlot); CatchAction->setHandlerBlockOrFunc(BlockAddress::get(HandlerBB)); TinyPtrVector Targets(HandlerBB); CatchAction->setReturnTargets(Targets); @@ -1301,9 +1682,8 @@ void LandingPadMap::remapEHValues(ValueToValueMapTy &VMap, Value *EHPtrValue, VMap[Extract] = SelectorValue; } -static bool isFrameAddressCall(const Value *V) { - return match(const_cast(V), - m_Intrinsic(m_SpecificInt(0))); +static bool isLocalAddressCall(const Value *V) { + return match(const_cast(V), m_Intrinsic()); } CloningDirector::CloningAction WinEHCloningDirectorBase::handleInstruction( @@ -1313,15 +1693,22 @@ CloningDirector::CloningAction WinEHCloningDirectorBase::handleInstruction( if (LPadMap.isLandingPadSpecificInst(Inst)) return CloningDirector::SkipInstruction; - // Nested landing pads will be cloned as stubs, with just the - // landingpad instruction and an unreachable instruction. When - // all landingpads have been outlined, we'll replace this with the - // llvm.eh.actions call and indirect branch created when the - // landing pad was outlined. + // Nested landing pads that have not already been outlined will be cloned as + // stubs, with just the landingpad instruction and an unreachable instruction. + // When all landingpads have been outlined, we'll replace this with the + // llvm.eh.actions call and indirect branch created when the landing pad was + // outlined. if (auto *LPad = dyn_cast(Inst)) { return handleLandingPad(VMap, LPad, NewBB); } + // Nested landing pads that have already been outlined will be cloned in their + // outlined form, but we need to intercept the ibr instruction to filter out + // targets that do not return to the handler we are outlining. + if (auto *IBr = dyn_cast(Inst)) { + return handleIndirectBr(VMap, IBr, NewBB); + } + if (auto *Invoke = dyn_cast(Inst)) return handleInvoke(VMap, Invoke, NewBB); @@ -1338,10 +1725,10 @@ CloningDirector::CloningAction WinEHCloningDirectorBase::handleInstruction( if (match(Inst, m_Intrinsic())) return handleTypeIdFor(VMap, Inst, NewBB); - // When outlining llvm.frameaddress(i32 0), remap that to the second argument, + // When outlining llvm.localaddress(), remap that to the second argument, // which is the FP of the parent. - if (isFrameAddressCall(Inst)) { - VMap[Inst] = EstablisherFrame; + if (isLocalAddressCall(Inst)) { + VMap[Inst] = ParentFP; return CloningDirector::SkipInstruction; } @@ -1351,6 +1738,20 @@ CloningDirector::CloningAction WinEHCloningDirectorBase::handleInstruction( CloningDirector::CloningAction WinEHCatchDirector::handleLandingPad( ValueToValueMapTy &VMap, const LandingPadInst *LPad, BasicBlock *NewBB) { + // If the instruction after the landing pad is a call to llvm.eh.actions + // the landing pad has already been outlined. In this case, we should + // clone it because it may return to a block in the handler we are + // outlining now that would otherwise be unreachable. The landing pads + // are sorted before outlining begins to enable this case to work + // properly. + const Instruction *NextI = LPad->getNextNode(); + if (match(NextI, m_Intrinsic())) + return CloningDirector::CloneInstruction; + + // If the landing pad hasn't been outlined yet, the landing pad we are + // outlining now does not dominate it and so it cannot return to a block + // in this handler. In that case, we can just insert a stub landing + // pad now and patch it up later. Instruction *NewInst = LPad->clone(); if (LPad->hasName()) NewInst->setName(LPad->getName()); @@ -1442,6 +1843,48 @@ CloningDirector::CloningAction WinEHCatchDirector::handleTypeIdFor( return CloningDirector::SkipInstruction; } +CloningDirector::CloningAction WinEHCatchDirector::handleIndirectBr( + ValueToValueMapTy &VMap, + const IndirectBrInst *IBr, + BasicBlock *NewBB) { + // If this indirect branch is not part of a landing pad block, just clone it. + const BasicBlock *ParentBB = IBr->getParent(); + if (!ParentBB->isLandingPad()) + return CloningDirector::CloneInstruction; + + // If it is part of a landing pad, we want to filter out target blocks + // that are not part of the handler we are outlining. + const LandingPadInst *LPad = ParentBB->getLandingPadInst(); + + // Save this correlation for later processing. + NestedLPtoOriginalLP[cast(VMap[LPad])] = LPad; + + // We should only get here for landing pads that have already been outlined. + assert(match(LPad->getNextNode(), m_Intrinsic())); + + // Copy the indirectbr, but only include targets that were previously + // identified as EH blocks and are dominated by the nested landing pad. + SetVector ReturnTargets; + for (int I = 0, E = IBr->getNumDestinations(); I < E; ++I) { + auto *TargetBB = IBr->getDestination(I); + if (EHBlocks.count(const_cast(TargetBB)) && + DT->dominates(ParentBB, TargetBB)) { + DEBUG(dbgs() << " Adding destination " << TargetBB->getName() << "\n"); + ReturnTargets.insert(TargetBB); + } + } + IndirectBrInst *NewBranch = + IndirectBrInst::Create(const_cast(IBr->getAddress()), + ReturnTargets.size(), NewBB); + for (auto *Target : ReturnTargets) + NewBranch->addDestination(const_cast(Target)); + + // The operands and targets of the branch instruction are remapped later + // because it is a terminator. Tell the cloning code to clone the + // blocks we just added to the target list. + return CloningDirector::CloneSuccessors; +} + CloningDirector::CloningAction WinEHCatchDirector::handleInvoke(ValueToValueMapTy &VMap, const InvokeInst *Invoke, BasicBlock *NewBB) { @@ -1464,7 +1907,8 @@ WinEHCatchDirector::handleCompare(ValueToValueMapTy &VMap, const IntrinsicInst *IntrinCall = nullptr; if (match(Compare->getOperand(0), m_Intrinsic())) { IntrinCall = dyn_cast(Compare->getOperand(0)); - } else if (match(Compare->getOperand(1), m_Intrinsic())) { + } else if (match(Compare->getOperand(1), + m_Intrinsic())) { IntrinCall = dyn_cast(Compare->getOperand(1)); } if (IntrinCall) { @@ -1473,8 +1917,7 @@ WinEHCatchDirector::handleCompare(ValueToValueMapTy &VMap, // on the filter function we intend to match. if (Selector == CurrentSelector->stripPointerCasts()) { VMap[Compare] = ConstantInt::get(SelectorIDType, 1); - } - else { + } else { VMap[Compare] = ConstantInt::get(SelectorIDType, 0); } return CloningDirector::SkipInstruction; @@ -1531,6 +1974,14 @@ CloningDirector::CloningAction WinEHCleanupDirector::handleTypeIdFor( return CloningDirector::SkipInstruction; } +CloningDirector::CloningAction WinEHCleanupDirector::handleIndirectBr( + ValueToValueMapTy &VMap, + const IndirectBrInst *IBr, + BasicBlock *NewBB) { + // No special handling is required for cleanup cloning. + return CloningDirector::CloneInstruction; +} + CloningDirector::CloningAction WinEHCleanupDirector::handleInvoke( ValueToValueMapTy &VMap, const InvokeInst *Invoke, BasicBlock *NewBB) { // All invokes in cleanup handlers can be replaced with calls. @@ -1577,21 +2028,26 @@ WinEHCleanupDirector::handleCompare(ValueToValueMapTy &VMap, return CloningDirector::SkipInstruction; } return CloningDirector::CloneInstruction; - } WinEHFrameVariableMaterializer::WinEHFrameVariableMaterializer( - Function *OutlinedFn, FrameVarInfoMap &FrameVarInfo) + Function *OutlinedFn, Value *ParentFP, FrameVarInfoMap &FrameVarInfo) : FrameVarInfo(FrameVarInfo), Builder(OutlinedFn->getContext()) { BasicBlock *EntryBB = &OutlinedFn->getEntryBlock(); - Builder.SetInsertPoint(EntryBB, EntryBB->getFirstInsertionPt()); + + // New allocas should be inserted in the entry block, but after the parent FP + // is established if it is an instruction. + Instruction *InsertPoint = EntryBB->getFirstInsertionPt(); + if (auto *FPInst = dyn_cast(ParentFP)) + InsertPoint = FPInst->getNextNode(); + Builder.SetInsertPoint(EntryBB, InsertPoint); } Value *WinEHFrameVariableMaterializer::materializeValueFor(Value *V) { // If we're asked to materialize a static alloca, we temporarily create an // alloca in the outlined function and add this to the FrameVarInfo map. When // all the outlining is complete, we'll replace these temporary allocas with - // calls to llvm.framerecover. + // calls to llvm.localrecover. if (auto *AV = dyn_cast(V)) { assert(AV->isStaticAlloca() && "cannot materialize un-demoted dynamic alloca"); @@ -1602,7 +2058,12 @@ Value *WinEHFrameVariableMaterializer::materializeValueFor(Value *V) { } if (isa(V) || isa(V)) { - errs() << "Failed to demote instruction used in exception handler:\n"; + Function *Parent = isa(V) + ? cast(V)->getParent()->getParent() + : cast(V)->getParent(); + errs() + << "Failed to demote instruction used in exception handler of function " + << GlobalValue::getRealLinkageName(Parent->getName()) << ":\n"; errs() << " " << *V << '\n'; report_fatal_error("WinEHPrepare failed to demote instruction"); } @@ -1616,7 +2077,7 @@ void WinEHFrameVariableMaterializer::escapeCatchObject(Value *V) { // of a catch parameter, add a sentinel to the multimap to indicate that it's // used from another handler. This will prevent us from trying to sink the // alloca into the handler and ensure that the catch parameter is present in - // the call to llvm.frameescape. + // the call to llvm.localescape. FrameVarInfo[V].push_back(getCatchObjectSentinel()); } @@ -1666,9 +2127,16 @@ void WinEHPrepare::mapLandingPadBlocks(LandingPadInst *LPad, while (HandlersFound != NumClauses) { BasicBlock *NextBB = nullptr; + // Skip over filter clauses. + if (LPad->isFilter(HandlersFound)) { + ++HandlersFound; + continue; + } + // See if the clause we're looking for is a catch-all. // If so, the catch begins immediately. - Constant *ExpectedSelector = LPad->getClause(HandlersFound)->stripPointerCasts(); + Constant *ExpectedSelector = + LPad->getClause(HandlersFound)->stripPointerCasts(); if (isa(ExpectedSelector)) { // The catch all must occur last. assert(HandlersFound == NumClauses - 1); @@ -1679,18 +2147,10 @@ void WinEHPrepare::mapLandingPadBlocks(LandingPadInst *LPad, Constant *Selector; while (BB && isSelectorDispatch(BB, CatchBlock, Selector, NextBB)) { DEBUG(dbgs() << " Found extra catch dispatch in block " - << CatchBlock->getName() << "\n"); + << CatchBlock->getName() << "\n"); BB = NextBB; } - // For C++ EH, check if there is any interesting cleanup code before we - // begin the catch. This is important because cleanups cannot rethrow - // exceptions but code called from catches can. For SEH, it isn't - // important if some finally code before a catch-all is executed out of - // line or after recovering from the exception. - if (Personality == EHPersonality::MSVC_CXX) - findCleanupHandlers(Actions, BB, BB); - // Add the catch handler to the action list. CatchHandler *Action = nullptr; if (CatchHandlerMap.count(BB) && CatchHandlerMap[BB] != nullptr) { @@ -1698,11 +2158,29 @@ void WinEHPrepare::mapLandingPadBlocks(LandingPadInst *LPad, Action = CatchHandlerMap[BB]; assert(Action->getSelector() == ExpectedSelector); } else { - // Since this is a catch-all handler, the selector won't actually appear - // in the code anywhere. ExpectedSelector here is the constant null ptr - // that we got from the landing pad instruction. - Action = new CatchHandler(BB, ExpectedSelector, nullptr); - CatchHandlerMap[BB] = Action; + // We don't expect a selector dispatch, but there may be a call to + // llvm.eh.begincatch, which separates catch handling code from + // cleanup code in the same control flow. This call looks for the + // begincatch intrinsic. + Action = findCatchHandler(BB, NextBB, VisitedBlocks); + if (Action) { + // For C++ EH, check if there is any interesting cleanup code before + // we begin the catch. This is important because cleanups cannot + // rethrow exceptions but code called from catches can. For SEH, it + // isn't important if some finally code before a catch-all is executed + // out of line or after recovering from the exception. + if (Personality == EHPersonality::MSVC_CXX) + findCleanupHandlers(Actions, BB, BB); + } else { + // If an action was not found, it means that the control flows + // directly into the catch-all handler and there is no cleanup code. + // That's an expected situation and we must create a catch action. + // Since this is a catch-all handler, the selector won't actually + // appear in the code anywhere. ExpectedSelector here is the constant + // null ptr that we got from the landing pad instruction. + Action = new CatchHandler(BB, ExpectedSelector, nullptr); + CatchHandlerMap[BB] = Action; + } } Actions.insertCatchHandler(Action); DEBUG(dbgs() << " Catch all handler at block " << BB->getName() << "\n"); @@ -1733,7 +2211,7 @@ void WinEHPrepare::mapLandingPadBlocks(LandingPadInst *LPad, // Under some circumstances optimized IR will flow unconditionally into a // handler block without checking the selector. This can only happen if // the landing pad has a catch-all handler and the handler for the - // preceeding catch clause is identical to the catch-call handler + // preceding catch clause is identical to the catch-call handler // (typically an empty catch). In this case, the handler must be shared // by all remaining clauses. if (isa( @@ -1841,16 +2319,16 @@ static void createCleanupHandler(LandingPadActions &Actions, static CallSite matchOutlinedFinallyCall(BasicBlock *BB, Instruction *MaybeCall) { // Look for finally blocks that Clang has already outlined for us. - // %fp = call i8* @llvm.frameaddress(i32 0) + // %fp = call i8* @llvm.localaddress() // call void @"fin$parent"(iN 1, i8* %fp) - if (isFrameAddressCall(MaybeCall) && MaybeCall != BB->getTerminator()) + if (isLocalAddressCall(MaybeCall) && MaybeCall != BB->getTerminator()) MaybeCall = MaybeCall->getNextNode(); CallSite FinallyCall(MaybeCall); if (!FinallyCall || FinallyCall.arg_size() != 2) return CallSite(); if (!match(FinallyCall.getArgument(0), m_SpecificInt(1))) return CallSite(); - if (!isFrameAddressCall(FinallyCall.getArgument(1))) + if (!isLocalAddressCall(FinallyCall.getArgument(1))) return CallSite(); return FinallyCall; } @@ -1900,7 +2378,7 @@ void WinEHPrepare::findCleanupHandlers(LandingPadActions &Actions, if (auto *Action = CleanupHandlerMap[BB]) { Actions.insertCleanupHandler(Action); DEBUG(dbgs() << " Found cleanup code in block " - << Action->getStartBlock()->getName() << "\n"); + << Action->getStartBlock()->getName() << "\n"); // FIXME: This cleanup might chain into another, and we need to discover // that. return; @@ -1909,7 +2387,7 @@ void WinEHPrepare::findCleanupHandlers(LandingPadActions &Actions, // value for this block but the value is a nullptr. This means that // we have previously analyzed the block and determined that it did // not contain any cleanup code. Based on the earlier analysis, we - // know the the block must end in either an unconditional branch, a + // know the block must end in either an unconditional branch, a // resume or a conditional branch that is predicated on a comparison // with a selector. Either the resume or the selector dispatch // would terminate the search for cleanup code, so the unconditional @@ -2008,36 +2486,43 @@ void WinEHPrepare::findCleanupHandlers(LandingPadActions &Actions, MaybeCall = MaybeCall->getNextNode(); } - // Look for outlined finally calls. - if (CallSite FinallyCall = matchOutlinedFinallyCall(BB, MaybeCall)) { - Function *Fin = FinallyCall.getCalledFunction(); - assert(Fin && "outlined finally call should be direct"); - auto *Action = new CleanupHandler(BB); - Action->setHandlerBlockOrFunc(Fin); - Actions.insertCleanupHandler(Action); - CleanupHandlerMap[BB] = Action; - DEBUG(dbgs() << " Found frontend-outlined finally call to " - << Fin->getName() << " in block " - << Action->getStartBlock()->getName() << "\n"); - - // Split the block if there were more interesting instructions and look - // for finally calls in the normal successor block. - BasicBlock *SuccBB = BB; - if (FinallyCall.getInstruction() != BB->getTerminator() && - FinallyCall.getInstruction()->getNextNode() != BB->getTerminator()) { - SuccBB = BB->splitBasicBlock(FinallyCall.getInstruction()->getNextNode()); - } else { - if (FinallyCall.isInvoke()) { - SuccBB = cast(FinallyCall.getInstruction())->getNormalDest(); + // Look for outlined finally calls on x64, since those happen to match the + // prototype provided by the runtime. + if (TheTriple.getArch() == Triple::x86_64) { + if (CallSite FinallyCall = matchOutlinedFinallyCall(BB, MaybeCall)) { + Function *Fin = FinallyCall.getCalledFunction(); + assert(Fin && "outlined finally call should be direct"); + auto *Action = new CleanupHandler(BB); + Action->setHandlerBlockOrFunc(Fin); + Actions.insertCleanupHandler(Action); + CleanupHandlerMap[BB] = Action; + DEBUG(dbgs() << " Found frontend-outlined finally call to " + << Fin->getName() << " in block " + << Action->getStartBlock()->getName() << "\n"); + + // Split the block if there were more interesting instructions and + // look for finally calls in the normal successor block. + BasicBlock *SuccBB = BB; + if (FinallyCall.getInstruction() != BB->getTerminator() && + FinallyCall.getInstruction()->getNextNode() != + BB->getTerminator()) { + SuccBB = + SplitBlock(BB, FinallyCall.getInstruction()->getNextNode(), DT); } else { - SuccBB = BB->getUniqueSuccessor(); - assert(SuccBB && "splitOutlinedFinallyCalls didn't insert a branch"); + if (FinallyCall.isInvoke()) { + SuccBB = cast(FinallyCall.getInstruction()) + ->getNormalDest(); + } else { + SuccBB = BB->getUniqueSuccessor(); + assert(SuccBB && + "splitOutlinedFinallyCalls didn't insert a branch"); + } } + BB = SuccBB; + if (BB == EndBB) + return; + continue; } - BB = SuccBB; - if (BB == EndBB) - return; - continue; } } @@ -2070,8 +2555,11 @@ void WinEHPrepare::findCleanupHandlers(LandingPadActions &Actions, // This is a public function, declared in WinEHFuncInfo.h and is also // referenced by WinEHNumbering in FunctionLoweringInfo.cpp. -void llvm::parseEHActions(const IntrinsicInst *II, - SmallVectorImpl &Actions) { +void llvm::parseEHActions( + const IntrinsicInst *II, + SmallVectorImpl> &Actions) { + assert(II->getIntrinsicID() == Intrinsic::eh_actions && + "attempted to parse non eh.actions intrinsic"); for (unsigned I = 0, E = II->getNumArgOperands(); I != E;) { uint64_t ActionKind = cast(II->getArgOperand(I))->getZExtValue(); @@ -2081,19 +2569,1105 @@ void llvm::parseEHActions(const IntrinsicInst *II, int64_t EHObjIndexVal = EHObjIndex->getSExtValue(); Constant *Handler = cast(II->getArgOperand(I + 3)); I += 4; - auto *CH = new CatchHandler(/*BB=*/nullptr, Selector, /*NextBB=*/nullptr); + auto CH = make_unique(/*BB=*/nullptr, Selector, + /*NextBB=*/nullptr); CH->setHandlerBlockOrFunc(Handler); CH->setExceptionVarIndex(EHObjIndexVal); - Actions.push_back(CH); + Actions.push_back(std::move(CH)); } else if (ActionKind == 0) { Constant *Handler = cast(II->getArgOperand(I + 1)); I += 2; - auto *CH = new CleanupHandler(/*BB=*/nullptr); + auto CH = make_unique(/*BB=*/nullptr); CH->setHandlerBlockOrFunc(Handler); - Actions.push_back(CH); + Actions.push_back(std::move(CH)); } else { llvm_unreachable("Expected either a catch or cleanup handler!"); } } std::reverse(Actions.begin(), Actions.end()); } + +static int addUnwindMapEntry(WinEHFuncInfo &FuncInfo, int ToState, + const Value *V) { + WinEHUnwindMapEntry UME; + UME.ToState = ToState; + UME.Cleanup = V; + FuncInfo.UnwindMap.push_back(UME); + return FuncInfo.getLastStateNumber(); +} + +static void addTryBlockMapEntry(WinEHFuncInfo &FuncInfo, int TryLow, + int TryHigh, int CatchHigh, + ArrayRef Handlers) { + WinEHTryBlockMapEntry TBME; + TBME.TryLow = TryLow; + TBME.TryHigh = TryHigh; + TBME.CatchHigh = CatchHigh; + assert(TBME.TryLow <= TBME.TryHigh); + for (const CatchPadInst *CPI : Handlers) { + WinEHHandlerType HT; + Constant *TypeInfo = cast(CPI->getArgOperand(0)); + if (TypeInfo->isNullValue()) + HT.TypeDescriptor = nullptr; + else + HT.TypeDescriptor = cast(TypeInfo->stripPointerCasts()); + HT.Adjectives = cast(CPI->getArgOperand(1))->getZExtValue(); + HT.Handler = CPI->getParent(); + HT.CatchObjRecoverIdx = -2; + if (isa(CPI->getArgOperand(2))) + HT.CatchObj.Alloca = nullptr; + else + HT.CatchObj.Alloca = cast(CPI->getArgOperand(2)); + TBME.HandlerArray.push_back(HT); + } + FuncInfo.TryBlockMap.push_back(TBME); +} + +static const CatchPadInst *getSingleCatchPadPredecessor(const BasicBlock *BB) { + for (const BasicBlock *PredBlock : predecessors(BB)) + if (auto *CPI = dyn_cast(PredBlock->getFirstNonPHI())) + return CPI; + return nullptr; +} + +/// Find all the catchpads that feed directly into the catchendpad. Frontends +/// using this personality should ensure that each catchendpad and catchpad has +/// one or zero catchpad predecessors. +/// +/// The following C++ generates the IR after it: +/// try { +/// } catch (A) { +/// } catch (B) { +/// } +/// +/// IR: +/// %catchpad.A +/// catchpad [i8* A typeinfo] +/// to label %catch.A unwind label %catchpad.B +/// %catchpad.B +/// catchpad [i8* B typeinfo] +/// to label %catch.B unwind label %endcatches +/// %endcatches +/// catchendblock unwind to caller +static void +findCatchPadsForCatchEndPad(const BasicBlock *CatchEndBB, + SmallVectorImpl &Handlers) { + const CatchPadInst *CPI = getSingleCatchPadPredecessor(CatchEndBB); + while (CPI) { + Handlers.push_back(CPI); + CPI = getSingleCatchPadPredecessor(CPI->getParent()); + } + // We've pushed these back into reverse source order. Reverse them to get + // the list back into source order. + std::reverse(Handlers.begin(), Handlers.end()); +} + +// Given BB which ends in an unwind edge, return the EHPad that this BB belongs +// to. If the unwind edge came from an invoke, return null. +static const BasicBlock *getEHPadFromPredecessor(const BasicBlock *BB) { + const TerminatorInst *TI = BB->getTerminator(); + if (isa(TI)) + return nullptr; + if (TI->isEHPad()) + return BB; + return cast(TI)->getCleanupPad()->getParent(); +} + +static void calculateExplicitCXXStateNumbers(WinEHFuncInfo &FuncInfo, + const BasicBlock &BB, + int ParentState) { + assert(BB.isEHPad()); + const Instruction *FirstNonPHI = BB.getFirstNonPHI(); + // All catchpad instructions will be handled when we process their + // respective catchendpad instruction. + if (isa(FirstNonPHI)) + return; + + if (isa(FirstNonPHI)) { + SmallVector Handlers; + findCatchPadsForCatchEndPad(&BB, Handlers); + const BasicBlock *FirstTryPad = Handlers.front()->getParent(); + int TryLow = addUnwindMapEntry(FuncInfo, ParentState, nullptr); + FuncInfo.EHPadStateMap[Handlers.front()] = TryLow; + for (const BasicBlock *PredBlock : predecessors(FirstTryPad)) + if ((PredBlock = getEHPadFromPredecessor(PredBlock))) + calculateExplicitCXXStateNumbers(FuncInfo, *PredBlock, TryLow); + int CatchLow = addUnwindMapEntry(FuncInfo, ParentState, nullptr); + + // catchpads are separate funclets in C++ EH due to the way rethrow works. + // In SEH, they aren't, so no invokes will unwind to the catchendpad. + FuncInfo.EHPadStateMap[FirstNonPHI] = CatchLow; + int TryHigh = CatchLow - 1; + for (const BasicBlock *PredBlock : predecessors(&BB)) + if ((PredBlock = getEHPadFromPredecessor(PredBlock))) + calculateExplicitCXXStateNumbers(FuncInfo, *PredBlock, CatchLow); + int CatchHigh = FuncInfo.getLastStateNumber(); + addTryBlockMapEntry(FuncInfo, TryLow, TryHigh, CatchHigh, Handlers); + DEBUG(dbgs() << "TryLow[" << FirstTryPad->getName() << "]: " << TryLow + << '\n'); + DEBUG(dbgs() << "TryHigh[" << FirstTryPad->getName() << "]: " << TryHigh + << '\n'); + DEBUG(dbgs() << "CatchHigh[" << FirstTryPad->getName() << "]: " << CatchHigh + << '\n'); + } else if (isa(FirstNonPHI)) { + int CleanupState = addUnwindMapEntry(FuncInfo, ParentState, &BB); + FuncInfo.EHPadStateMap[FirstNonPHI] = CleanupState; + DEBUG(dbgs() << "Assigning state #" << CleanupState << " to BB " + << BB.getName() << '\n'); + for (const BasicBlock *PredBlock : predecessors(&BB)) + if ((PredBlock = getEHPadFromPredecessor(PredBlock))) + calculateExplicitCXXStateNumbers(FuncInfo, *PredBlock, CleanupState); + } else if (isa(FirstNonPHI)) { + report_fatal_error("Not yet implemented!"); + } else { + llvm_unreachable("unexpected EH Pad!"); + } +} + +static int addSEHExcept(WinEHFuncInfo &FuncInfo, int ParentState, + const Function *Filter, const BasicBlock *Handler) { + SEHUnwindMapEntry Entry; + Entry.ToState = ParentState; + Entry.IsFinally = false; + Entry.Filter = Filter; + Entry.Handler = Handler; + FuncInfo.SEHUnwindMap.push_back(Entry); + return FuncInfo.SEHUnwindMap.size() - 1; +} + +static int addSEHFinally(WinEHFuncInfo &FuncInfo, int ParentState, + const BasicBlock *Handler) { + SEHUnwindMapEntry Entry; + Entry.ToState = ParentState; + Entry.IsFinally = true; + Entry.Filter = nullptr; + Entry.Handler = Handler; + FuncInfo.SEHUnwindMap.push_back(Entry); + return FuncInfo.SEHUnwindMap.size() - 1; +} + +static void calculateExplicitSEHStateNumbers(WinEHFuncInfo &FuncInfo, + const BasicBlock &BB, + int ParentState) { + assert(BB.isEHPad()); + const Instruction *FirstNonPHI = BB.getFirstNonPHI(); + // All catchpad instructions will be handled when we process their + // respective catchendpad instruction. + if (isa(FirstNonPHI)) + return; + + if (isa(FirstNonPHI)) { + // Extract the filter function and the __except basic block and create a + // state for them. + SmallVector Handlers; + findCatchPadsForCatchEndPad(&BB, Handlers); + assert(Handlers.size() == 1 && + "SEH doesn't have multiple handlers per __try"); + const CatchPadInst *CPI = Handlers.front(); + const BasicBlock *CatchPadBB = CPI->getParent(); + const Constant *FilterOrNull = + cast(CPI->getArgOperand(0)->stripPointerCasts()); + const Function *Filter = dyn_cast(FilterOrNull); + assert((Filter || FilterOrNull->isNullValue()) && + "unexpected filter value"); + int TryState = addSEHExcept(FuncInfo, ParentState, Filter, CatchPadBB); + + // Everything in the __try block uses TryState as its parent state. + FuncInfo.EHPadStateMap[CPI] = TryState; + DEBUG(dbgs() << "Assigning state #" << TryState << " to BB " + << CatchPadBB->getName() << '\n'); + for (const BasicBlock *PredBlock : predecessors(CatchPadBB)) + if ((PredBlock = getEHPadFromPredecessor(PredBlock))) + calculateExplicitSEHStateNumbers(FuncInfo, *PredBlock, TryState); + + // Everything in the __except block unwinds to ParentState, just like code + // outside the __try. + FuncInfo.EHPadStateMap[FirstNonPHI] = ParentState; + DEBUG(dbgs() << "Assigning state #" << ParentState << " to BB " + << BB.getName() << '\n'); + for (const BasicBlock *PredBlock : predecessors(&BB)) + if ((PredBlock = getEHPadFromPredecessor(PredBlock))) + calculateExplicitSEHStateNumbers(FuncInfo, *PredBlock, ParentState); + } else if (isa(FirstNonPHI)) { + int CleanupState = addSEHFinally(FuncInfo, ParentState, &BB); + FuncInfo.EHPadStateMap[FirstNonPHI] = CleanupState; + DEBUG(dbgs() << "Assigning state #" << CleanupState << " to BB " + << BB.getName() << '\n'); + for (const BasicBlock *PredBlock : predecessors(&BB)) + if ((PredBlock = getEHPadFromPredecessor(PredBlock))) + calculateExplicitSEHStateNumbers(FuncInfo, *PredBlock, CleanupState); + } else if (isa(FirstNonPHI)) { + // Anything unwinding through CleanupEndPadInst is in ParentState. + FuncInfo.EHPadStateMap[FirstNonPHI] = ParentState; + DEBUG(dbgs() << "Assigning state #" << ParentState << " to BB " + << BB.getName() << '\n'); + for (const BasicBlock *PredBlock : predecessors(&BB)) + if ((PredBlock = getEHPadFromPredecessor(PredBlock))) + calculateExplicitSEHStateNumbers(FuncInfo, *PredBlock, ParentState); + } else if (isa(FirstNonPHI)) { + report_fatal_error("Not yet implemented!"); + } else { + llvm_unreachable("unexpected EH Pad!"); + } +} + +/// Check if the EH Pad unwinds to caller. Cleanups are a little bit of a +/// special case because we have to look at the cleanupret instruction that uses +/// the cleanuppad. +static bool doesEHPadUnwindToCaller(const Instruction *EHPad) { + auto *CPI = dyn_cast(EHPad); + if (!CPI) + return EHPad->mayThrow(); + + // This cleanup does not return or unwind, so we say it unwinds to caller. + if (CPI->use_empty()) + return true; + + const Instruction *User = CPI->user_back(); + if (auto *CRI = dyn_cast(User)) + return CRI->unwindsToCaller(); + return cast(User)->unwindsToCaller(); +} + +void llvm::calculateSEHStateNumbers(const Function *Fn, + WinEHFuncInfo &FuncInfo) { + // Don't compute state numbers twice. + if (!FuncInfo.SEHUnwindMap.empty()) + return; + + for (const BasicBlock &BB : *Fn) { + if (!BB.isEHPad() || !doesEHPadUnwindToCaller(BB.getFirstNonPHI())) + continue; + calculateExplicitSEHStateNumbers(FuncInfo, BB, -1); + } +} + +void llvm::calculateWinCXXEHStateNumbers(const Function *Fn, + WinEHFuncInfo &FuncInfo) { + // Return if it's already been done. + if (!FuncInfo.EHPadStateMap.empty()) + return; + + for (const BasicBlock &BB : *Fn) { + if (!BB.isEHPad()) + continue; + if (BB.isLandingPad()) + report_fatal_error("MSVC C++ EH cannot use landingpads"); + const Instruction *FirstNonPHI = BB.getFirstNonPHI(); + // Skip cleanupendpads; they are exits, not entries. + if (isa(FirstNonPHI)) + continue; + if (!doesEHPadUnwindToCaller(FirstNonPHI)) + continue; + calculateExplicitCXXStateNumbers(FuncInfo, BB, -1); + } +} + +static int addClrEHHandler(WinEHFuncInfo &FuncInfo, int ParentState, + ClrHandlerType HandlerType, uint32_t TypeToken, + const BasicBlock *Handler) { + ClrEHUnwindMapEntry Entry; + Entry.Parent = ParentState; + Entry.Handler = Handler; + Entry.HandlerType = HandlerType; + Entry.TypeToken = TypeToken; + FuncInfo.ClrEHUnwindMap.push_back(Entry); + return FuncInfo.ClrEHUnwindMap.size() - 1; +} + +void llvm::calculateClrEHStateNumbers(const Function *Fn, + WinEHFuncInfo &FuncInfo) { + // Return if it's already been done. + if (!FuncInfo.EHPadStateMap.empty()) + return; + + SmallVector, 8> Worklist; + + // Each pad needs to be able to refer to its parent, so scan the function + // looking for top-level handlers and seed the worklist with them. + for (const BasicBlock &BB : *Fn) { + if (!BB.isEHPad()) + continue; + if (BB.isLandingPad()) + report_fatal_error("CoreCLR EH cannot use landingpads"); + const Instruction *FirstNonPHI = BB.getFirstNonPHI(); + if (!doesEHPadUnwindToCaller(FirstNonPHI)) + continue; + // queue this with sentinel parent state -1 to mean unwind to caller. + Worklist.emplace_back(FirstNonPHI, -1); + } + + while (!Worklist.empty()) { + const Instruction *Pad; + int ParentState; + std::tie(Pad, ParentState) = Worklist.pop_back_val(); + + int PredState; + if (const CleanupEndPadInst *EndPad = dyn_cast(Pad)) { + FuncInfo.EHPadStateMap[EndPad] = ParentState; + // Queue the cleanuppad, in case it doesn't have a cleanupret. + Worklist.emplace_back(EndPad->getCleanupPad(), ParentState); + // Preds of the endpad should get the parent state. + PredState = ParentState; + } else if (const CleanupPadInst *Cleanup = dyn_cast(Pad)) { + // A cleanup can have multiple exits; don't re-process after the first. + if (FuncInfo.EHPadStateMap.count(Pad)) + continue; + // CoreCLR personality uses arity to distinguish faults from finallies. + const BasicBlock *PadBlock = Cleanup->getParent(); + ClrHandlerType HandlerType = + (Cleanup->getNumOperands() ? ClrHandlerType::Fault + : ClrHandlerType::Finally); + int NewState = + addClrEHHandler(FuncInfo, ParentState, HandlerType, 0, PadBlock); + FuncInfo.EHPadStateMap[Cleanup] = NewState; + // Propagate the new state to all preds of the cleanup + PredState = NewState; + } else if (const CatchEndPadInst *EndPad = dyn_cast(Pad)) { + FuncInfo.EHPadStateMap[EndPad] = ParentState; + // Preds of the endpad should get the parent state. + PredState = ParentState; + } else if (const CatchPadInst *Catch = dyn_cast(Pad)) { + const BasicBlock *Handler = Catch->getNormalDest(); + uint32_t TypeToken = static_cast( + cast(Catch->getArgOperand(0))->getZExtValue()); + int NewState = addClrEHHandler(FuncInfo, ParentState, + ClrHandlerType::Catch, TypeToken, Handler); + FuncInfo.EHPadStateMap[Catch] = NewState; + // Preds of the catch get its state + PredState = NewState; + } else { + llvm_unreachable("Unexpected EH pad"); + } + + // Queue all predecessors with the given state + for (const BasicBlock *Pred : predecessors(Pad->getParent())) { + if ((Pred = getEHPadFromPredecessor(Pred))) + Worklist.emplace_back(Pred->getFirstNonPHI(), PredState); + } + } +} + +void WinEHPrepare::replaceTerminatePadWithCleanup(Function &F) { + if (Personality != EHPersonality::MSVC_CXX) + return; + for (BasicBlock &BB : F) { + Instruction *First = BB.getFirstNonPHI(); + auto *TPI = dyn_cast(First); + if (!TPI) + continue; + + if (TPI->getNumArgOperands() != 1) + report_fatal_error( + "Expected a unary terminatepad for MSVC C++ personalities!"); + + auto *TerminateFn = dyn_cast(TPI->getArgOperand(0)); + if (!TerminateFn) + report_fatal_error("Function operand expected in terminatepad for MSVC " + "C++ personalities!"); + + // Insert the cleanuppad instruction. + auto *CPI = CleanupPadInst::Create( + BB.getContext(), {}, Twine("terminatepad.for.", BB.getName()), &BB); + + // Insert the call to the terminate instruction. + auto *CallTerminate = CallInst::Create(TerminateFn, {}, &BB); + CallTerminate->setDoesNotThrow(); + CallTerminate->setDoesNotReturn(); + CallTerminate->setCallingConv(TerminateFn->getCallingConv()); + + // Insert a new terminator for the cleanuppad using the same successor as + // the terminatepad. + CleanupReturnInst::Create(CPI, TPI->getUnwindDest(), &BB); + + // Let's remove the terminatepad now that we've inserted the new + // instructions. + TPI->eraseFromParent(); + } +} + +static void +colorFunclets(Function &F, SmallVectorImpl &EntryBlocks, + std::map> &BlockColors, + std::map> &FuncletBlocks, + std::map> &FuncletChildren) { + SmallVector, 16> Worklist; + BasicBlock *EntryBlock = &F.getEntryBlock(); + + // Build up the color map, which maps each block to its set of 'colors'. + // For any block B, the "colors" of B are the set of funclets F (possibly + // including a root "funclet" representing the main function), such that + // F will need to directly contain B or a copy of B (where the term "directly + // contain" is used to distinguish from being "transitively contained" in + // a nested funclet). + // Use a CFG walk driven by a worklist of (block, color) pairs. The "color" + // sets attached during this processing to a block which is the entry of some + // funclet F is actually the set of F's parents -- i.e. the union of colors + // of all predecessors of F's entry. For all other blocks, the color sets + // are as defined above. A post-pass fixes up the block color map to reflect + // the same sense of "color" for funclet entries as for other blocks. + + Worklist.push_back({EntryBlock, EntryBlock}); + + while (!Worklist.empty()) { + BasicBlock *Visiting; + BasicBlock *Color; + std::tie(Visiting, Color) = Worklist.pop_back_val(); + Instruction *VisitingHead = Visiting->getFirstNonPHI(); + if (VisitingHead->isEHPad() && !isa(VisitingHead) && + !isa(VisitingHead)) { + // Mark this as a funclet head as a member of itself. + FuncletBlocks[Visiting].insert(Visiting); + // Queue exits with the parent color. + for (User *U : VisitingHead->users()) { + if (auto *Exit = dyn_cast(U)) { + for (BasicBlock *Succ : successors(Exit->getParent())) + if (BlockColors[Succ].insert(Color).second) + Worklist.push_back({Succ, Color}); + } + } + // Handle CatchPad specially since its successors need different colors. + if (CatchPadInst *CatchPad = dyn_cast(VisitingHead)) { + // Visit the normal successor with the color of the new EH pad, and + // visit the unwind successor with the color of the parent. + BasicBlock *NormalSucc = CatchPad->getNormalDest(); + if (BlockColors[NormalSucc].insert(Visiting).second) { + Worklist.push_back({NormalSucc, Visiting}); + } + BasicBlock *UnwindSucc = CatchPad->getUnwindDest(); + if (BlockColors[UnwindSucc].insert(Color).second) { + Worklist.push_back({UnwindSucc, Color}); + } + continue; + } + // Switch color to the current node, except for terminate pads which + // have no bodies and only unwind successors and so need their successors + // visited with the color of the parent. + if (!isa(VisitingHead)) + Color = Visiting; + } else { + // Note that this is a member of the given color. + FuncletBlocks[Color].insert(Visiting); + } + + TerminatorInst *Terminator = Visiting->getTerminator(); + if (isa(Terminator) || + isa(Terminator) || + isa(Terminator)) { + // These blocks' successors have already been queued with the parent + // color. + continue; + } + for (BasicBlock *Succ : successors(Visiting)) { + if (isa(Succ->getFirstNonPHI())) { + // The catchendpad needs to be visited with the parent's color, not + // the current color. This will happen in the code above that visits + // any catchpad unwind successor with the parent color, so we can + // safely skip this successor here. + continue; + } + if (BlockColors[Succ].insert(Color).second) { + Worklist.push_back({Succ, Color}); + } + } + } + + // The processing above actually accumulated the parent set for this + // funclet into the color set for its entry; use the parent set to + // populate the children map, and reset the color set to include just + // the funclet itself (no instruction can target a funclet entry except on + // that transitions to the child funclet). + for (BasicBlock *FuncletEntry : EntryBlocks) { + std::set &ColorMapItem = BlockColors[FuncletEntry]; + for (BasicBlock *Parent : ColorMapItem) + FuncletChildren[Parent].insert(FuncletEntry); + ColorMapItem.clear(); + ColorMapItem.insert(FuncletEntry); + } +} + +void WinEHPrepare::colorFunclets(Function &F, + SmallVectorImpl &EntryBlocks) { + ::colorFunclets(F, EntryBlocks, BlockColors, FuncletBlocks, FuncletChildren); +} + +void llvm::calculateCatchReturnSuccessorColors(const Function *Fn, + WinEHFuncInfo &FuncInfo) { + SmallVector LPads; + SmallVector Resumes; + SmallVector EntryBlocks; + // colorFunclets needs the set of EntryBlocks, get them using + // findExceptionalConstructs. + bool ForExplicitEH = findExceptionalConstructs(const_cast(*Fn), + LPads, Resumes, EntryBlocks); + if (!ForExplicitEH) + return; + + std::map> BlockColors; + std::map> FuncletBlocks; + std::map> FuncletChildren; + // Figure out which basic blocks belong to which funclets. + colorFunclets(const_cast(*Fn), EntryBlocks, BlockColors, + FuncletBlocks, FuncletChildren); + + // We need to find the catchret successors. To do this, we must first find + // all the catchpad funclets. + for (auto &Funclet : FuncletBlocks) { + // Figure out what kind of funclet we are looking at; We only care about + // catchpads. + BasicBlock *FuncletPadBB = Funclet.first; + Instruction *FirstNonPHI = FuncletPadBB->getFirstNonPHI(); + auto *CatchPad = dyn_cast(FirstNonPHI); + if (!CatchPad) + continue; + + // The users of a catchpad are always catchrets. + for (User *Exit : CatchPad->users()) { + auto *CatchReturn = dyn_cast(Exit); + if (!CatchReturn) + continue; + BasicBlock *CatchRetSuccessor = CatchReturn->getSuccessor(); + std::set &SuccessorColors = BlockColors[CatchRetSuccessor]; + assert(SuccessorColors.size() == 1 && "Expected BB to be monochrome!"); + BasicBlock *Color = *SuccessorColors.begin(); + if (auto *CPI = dyn_cast(Color->getFirstNonPHI())) + Color = CPI->getNormalDest(); + // Record the catchret successor's funclet membership. + FuncInfo.CatchRetSuccessorColorMap[CatchReturn] = Color; + } + } +} + +void WinEHPrepare::demotePHIsOnFunclets(Function &F) { + // Strip PHI nodes off of EH pads. + SmallVector PHINodes; + for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) { + BasicBlock *BB = FI++; + if (!BB->isEHPad()) + continue; + for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) { + Instruction *I = BI++; + auto *PN = dyn_cast(I); + // Stop at the first non-PHI. + if (!PN) + break; + + AllocaInst *SpillSlot = insertPHILoads(PN, F); + if (SpillSlot) + insertPHIStores(PN, SpillSlot); + + PHINodes.push_back(PN); + } + } + + for (auto *PN : PHINodes) { + // There may be lingering uses on other EH PHIs being removed + PN->replaceAllUsesWith(UndefValue::get(PN->getType())); + PN->eraseFromParent(); + } +} + +void WinEHPrepare::demoteUsesBetweenFunclets(Function &F) { + // Turn all inter-funclet uses of a Value into loads and stores. + for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) { + BasicBlock *BB = FI++; + std::set &ColorsForBB = BlockColors[BB]; + for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) { + Instruction *I = BI++; + // Funclets are permitted to use static allocas. + if (auto *AI = dyn_cast(I)) + if (AI->isStaticAlloca()) + continue; + + demoteNonlocalUses(I, ColorsForBB, F); + } + } +} + +void WinEHPrepare::demoteArgumentUses(Function &F) { + // Also demote function parameters used in funclets. + std::set &ColorsForEntry = BlockColors[&F.getEntryBlock()]; + for (Argument &Arg : F.args()) + demoteNonlocalUses(&Arg, ColorsForEntry, F); +} + +void WinEHPrepare::cloneCommonBlocks( + Function &F, SmallVectorImpl &EntryBlocks) { + // We need to clone all blocks which belong to multiple funclets. Values are + // remapped throughout the funclet to propogate both the new instructions + // *and* the new basic blocks themselves. + for (BasicBlock *FuncletPadBB : EntryBlocks) { + std::set &BlocksInFunclet = FuncletBlocks[FuncletPadBB]; + + std::map Orig2Clone; + ValueToValueMapTy VMap; + for (BasicBlock *BB : BlocksInFunclet) { + std::set &ColorsForBB = BlockColors[BB]; + // We don't need to do anything if the block is monochromatic. + size_t NumColorsForBB = ColorsForBB.size(); + if (NumColorsForBB == 1) + continue; + + // Create a new basic block and copy instructions into it! + BasicBlock *CBB = + CloneBasicBlock(BB, VMap, Twine(".for.", FuncletPadBB->getName())); + // Insert the clone immediately after the original to ensure determinism + // and to keep the same relative ordering of any funclet's blocks. + CBB->insertInto(&F, BB->getNextNode()); + + // Add basic block mapping. + VMap[BB] = CBB; + + // Record delta operations that we need to perform to our color mappings. + Orig2Clone[BB] = CBB; + } + + // Update our color mappings to reflect that one block has lost a color and + // another has gained a color. + for (auto &BBMapping : Orig2Clone) { + BasicBlock *OldBlock = BBMapping.first; + BasicBlock *NewBlock = BBMapping.second; + + BlocksInFunclet.insert(NewBlock); + BlockColors[NewBlock].insert(FuncletPadBB); + + BlocksInFunclet.erase(OldBlock); + BlockColors[OldBlock].erase(FuncletPadBB); + } + + // Loop over all of the instructions in the function, fixing up operand + // references as we go. This uses VMap to do all the hard work. + for (BasicBlock *BB : BlocksInFunclet) + // Loop over all instructions, fixing each one as we find it... + for (Instruction &I : *BB) + RemapInstruction(&I, VMap, RF_IgnoreMissingEntries); + + // Check to see if SuccBB has PHI nodes. If so, we need to add entries to + // the PHI nodes for NewBB now. + for (auto &BBMapping : Orig2Clone) { + BasicBlock *OldBlock = BBMapping.first; + BasicBlock *NewBlock = BBMapping.second; + for (BasicBlock *SuccBB : successors(NewBlock)) { + for (Instruction &SuccI : *SuccBB) { + auto *SuccPN = dyn_cast(&SuccI); + if (!SuccPN) + break; + + // Ok, we have a PHI node. Figure out what the incoming value was for + // the OldBlock. + int OldBlockIdx = SuccPN->getBasicBlockIndex(OldBlock); + if (OldBlockIdx == -1) + break; + Value *IV = SuccPN->getIncomingValue(OldBlockIdx); + + // Remap the value if necessary. + if (auto *Inst = dyn_cast(IV)) { + ValueToValueMapTy::iterator I = VMap.find(Inst); + if (I != VMap.end()) + IV = I->second; + } + + SuccPN->addIncoming(IV, NewBlock); + } + } + } + + for (ValueToValueMapTy::value_type VT : VMap) { + // If there were values defined in BB that are used outside the funclet, + // then we now have to update all uses of the value to use either the + // original value, the cloned value, or some PHI derived value. This can + // require arbitrary PHI insertion, of which we are prepared to do, clean + // these up now. + SmallVector UsesToRename; + + auto *OldI = dyn_cast(const_cast(VT.first)); + if (!OldI) + continue; + auto *NewI = cast(VT.second); + // Scan all uses of this instruction to see if it is used outside of its + // funclet, and if so, record them in UsesToRename. + for (Use &U : OldI->uses()) { + Instruction *UserI = cast(U.getUser()); + BasicBlock *UserBB = UserI->getParent(); + std::set &ColorsForUserBB = BlockColors[UserBB]; + assert(!ColorsForUserBB.empty()); + if (ColorsForUserBB.size() > 1 || + *ColorsForUserBB.begin() != FuncletPadBB) + UsesToRename.push_back(&U); + } + + // If there are no uses outside the block, we're done with this + // instruction. + if (UsesToRename.empty()) + continue; + + // We found a use of OldI outside of the funclet. Rename all uses of OldI + // that are outside its funclet to be uses of the appropriate PHI node + // etc. + SSAUpdater SSAUpdate; + SSAUpdate.Initialize(OldI->getType(), OldI->getName()); + SSAUpdate.AddAvailableValue(OldI->getParent(), OldI); + SSAUpdate.AddAvailableValue(NewI->getParent(), NewI); + + while (!UsesToRename.empty()) + SSAUpdate.RewriteUseAfterInsertions(*UsesToRename.pop_back_val()); + } + } +} + +void WinEHPrepare::removeImplausibleTerminators(Function &F) { + // Remove implausible terminators and replace them with UnreachableInst. + for (auto &Funclet : FuncletBlocks) { + BasicBlock *FuncletPadBB = Funclet.first; + std::set &BlocksInFunclet = Funclet.second; + Instruction *FirstNonPHI = FuncletPadBB->getFirstNonPHI(); + auto *CatchPad = dyn_cast(FirstNonPHI); + auto *CleanupPad = dyn_cast(FirstNonPHI); + + for (BasicBlock *BB : BlocksInFunclet) { + TerminatorInst *TI = BB->getTerminator(); + // CatchPadInst and CleanupPadInst can't transfer control to a ReturnInst. + bool IsUnreachableRet = isa(TI) && (CatchPad || CleanupPad); + // The token consumed by a CatchReturnInst must match the funclet token. + bool IsUnreachableCatchret = false; + if (auto *CRI = dyn_cast(TI)) + IsUnreachableCatchret = CRI->getCatchPad() != CatchPad; + // The token consumed by a CleanupReturnInst must match the funclet token. + bool IsUnreachableCleanupret = false; + if (auto *CRI = dyn_cast(TI)) + IsUnreachableCleanupret = CRI->getCleanupPad() != CleanupPad; + // The token consumed by a CleanupEndPadInst must match the funclet token. + bool IsUnreachableCleanupendpad = false; + if (auto *CEPI = dyn_cast(TI)) + IsUnreachableCleanupendpad = CEPI->getCleanupPad() != CleanupPad; + if (IsUnreachableRet || IsUnreachableCatchret || + IsUnreachableCleanupret || IsUnreachableCleanupendpad) { + // Loop through all of our successors and make sure they know that one + // of their predecessors is going away. + for (BasicBlock *SuccBB : TI->successors()) + SuccBB->removePredecessor(BB); + + if (IsUnreachableCleanupendpad) { + // We can't simply replace a cleanupendpad with unreachable, because + // its predecessor edges are EH edges and unreachable is not an EH + // pad. Change all predecessors to the "unwind to caller" form. + for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); + PI != PE;) { + BasicBlock *Pred = *PI++; + removeUnwindEdge(Pred); + } + } + + new UnreachableInst(BB->getContext(), TI); + TI->eraseFromParent(); + } + // FIXME: Check for invokes/cleanuprets/cleanupendpads which unwind to + // implausible catchendpads (i.e. catchendpad not in immediate parent + // funclet). + } + } +} + +void WinEHPrepare::cleanupPreparedFunclets(Function &F) { + // Clean-up some of the mess we made by removing useles PHI nodes, trivial + // branches, etc. + for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) { + BasicBlock *BB = FI++; + SimplifyInstructionsInBlock(BB); + ConstantFoldTerminator(BB, /*DeleteDeadConditions=*/true); + MergeBlockIntoPredecessor(BB); + } + + // We might have some unreachable blocks after cleaning up some impossible + // control flow. + removeUnreachableBlocks(F); +} + +void WinEHPrepare::verifyPreparedFunclets(Function &F) { + // Recolor the CFG to verify that all is well. + for (BasicBlock &BB : F) { + size_t NumColors = BlockColors[&BB].size(); + assert(NumColors == 1 && "Expected monochromatic BB!"); + if (NumColors == 0) + report_fatal_error("Uncolored BB!"); + if (NumColors > 1) + report_fatal_error("Multicolor BB!"); + if (!DisableDemotion) { + bool EHPadHasPHI = BB.isEHPad() && isa(BB.begin()); + assert(!EHPadHasPHI && "EH Pad still has a PHI!"); + if (EHPadHasPHI) + report_fatal_error("EH Pad still has a PHI!"); + } + } +} + +bool WinEHPrepare::prepareExplicitEH( + Function &F, SmallVectorImpl &EntryBlocks) { + // Remove unreachable blocks. It is not valuable to assign them a color and + // their existence can trick us into thinking values are alive when they are + // not. + removeUnreachableBlocks(F); + + replaceTerminatePadWithCleanup(F); + + // Determine which blocks are reachable from which funclet entries. + colorFunclets(F, EntryBlocks); + + if (!DisableDemotion) { + demotePHIsOnFunclets(F); + + demoteUsesBetweenFunclets(F); + + demoteArgumentUses(F); + } + + cloneCommonBlocks(F, EntryBlocks); + + if (!DisableCleanups) { + removeImplausibleTerminators(F); + + cleanupPreparedFunclets(F); + } + + verifyPreparedFunclets(F); + + BlockColors.clear(); + FuncletBlocks.clear(); + FuncletChildren.clear(); + + return true; +} + +// TODO: Share loads when one use dominates another, or when a catchpad exit +// dominates uses (needs dominators). +AllocaInst *WinEHPrepare::insertPHILoads(PHINode *PN, Function &F) { + BasicBlock *PHIBlock = PN->getParent(); + AllocaInst *SpillSlot = nullptr; + + if (isa(PHIBlock->getFirstNonPHI())) { + // Insert a load in place of the PHI and replace all uses. + SpillSlot = new AllocaInst(PN->getType(), nullptr, + Twine(PN->getName(), ".wineh.spillslot"), + F.getEntryBlock().begin()); + Value *V = new LoadInst(SpillSlot, Twine(PN->getName(), ".wineh.reload"), + PHIBlock->getFirstInsertionPt()); + PN->replaceAllUsesWith(V); + return SpillSlot; + } + + DenseMap Loads; + for (Value::use_iterator UI = PN->use_begin(), UE = PN->use_end(); + UI != UE;) { + Use &U = *UI++; + auto *UsingInst = cast(U.getUser()); + BasicBlock *UsingBB = UsingInst->getParent(); + if (UsingBB->isEHPad()) { + // Use is on an EH pad phi. Leave it alone; we'll insert loads and + // stores for it separately. + assert(isa(UsingInst)); + continue; + } + replaceUseWithLoad(PN, U, SpillSlot, Loads, F); + } + return SpillSlot; +} + +// TODO: improve store placement. Inserting at def is probably good, but need +// to be careful not to introduce interfering stores (needs liveness analysis). +// TODO: identify related phi nodes that can share spill slots, and share them +// (also needs liveness). +void WinEHPrepare::insertPHIStores(PHINode *OriginalPHI, + AllocaInst *SpillSlot) { + // Use a worklist of (Block, Value) pairs -- the given Value needs to be + // stored to the spill slot by the end of the given Block. + SmallVector, 4> Worklist; + + Worklist.push_back({OriginalPHI->getParent(), OriginalPHI}); + + while (!Worklist.empty()) { + BasicBlock *EHBlock; + Value *InVal; + std::tie(EHBlock, InVal) = Worklist.pop_back_val(); + + PHINode *PN = dyn_cast(InVal); + if (PN && PN->getParent() == EHBlock) { + // The value is defined by another PHI we need to remove, with no room to + // insert a store after the PHI, so each predecessor needs to store its + // incoming value. + for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i) { + Value *PredVal = PN->getIncomingValue(i); + + // Undef can safely be skipped. + if (isa(PredVal)) + continue; + + insertPHIStore(PN->getIncomingBlock(i), PredVal, SpillSlot, Worklist); + } + } else { + // We need to store InVal, which dominates EHBlock, but can't put a store + // in EHBlock, so need to put stores in each predecessor. + for (BasicBlock *PredBlock : predecessors(EHBlock)) { + insertPHIStore(PredBlock, InVal, SpillSlot, Worklist); + } + } + } +} + +void WinEHPrepare::insertPHIStore( + BasicBlock *PredBlock, Value *PredVal, AllocaInst *SpillSlot, + SmallVectorImpl> &Worklist) { + + if (PredBlock->isEHPad() && + !isa(PredBlock->getFirstNonPHI())) { + // Pred is unsplittable, so we need to queue it on the worklist. + Worklist.push_back({PredBlock, PredVal}); + return; + } + + // Otherwise, insert the store at the end of the basic block. + new StoreInst(PredVal, SpillSlot, PredBlock->getTerminator()); +} + +// TODO: Share loads for same-funclet uses (requires dominators if funclets +// aren't properly nested). +void WinEHPrepare::demoteNonlocalUses(Value *V, + std::set &ColorsForBB, + Function &F) { + // Tokens can only be used non-locally due to control flow involving + // unreachable edges. Don't try to demote the token usage, we'll simply + // delete the cloned user later. + if (isa(V) || isa(V)) + return; + + DenseMap Loads; + AllocaInst *SpillSlot = nullptr; + for (Value::use_iterator UI = V->use_begin(), UE = V->use_end(); UI != UE;) { + Use &U = *UI++; + auto *UsingInst = cast(U.getUser()); + BasicBlock *UsingBB = UsingInst->getParent(); + + // Is the Use inside a block which is colored the same as the Def? + // If so, we don't need to escape the Def because we will clone + // ourselves our own private copy. + std::set &ColorsForUsingBB = BlockColors[UsingBB]; + if (ColorsForUsingBB == ColorsForBB) + continue; + + replaceUseWithLoad(V, U, SpillSlot, Loads, F); + } + if (SpillSlot) { + // Insert stores of the computed value into the stack slot. + // We have to be careful if I is an invoke instruction, + // because we can't insert the store AFTER the terminator instruction. + BasicBlock::iterator InsertPt; + if (isa(V)) { + InsertPt = F.getEntryBlock().getTerminator(); + } else if (isa(V)) { + auto *II = cast(V); + // We cannot demote invoke instructions to the stack if their normal + // edge is critical. Therefore, split the critical edge and create a + // basic block into which the store can be inserted. + if (!II->getNormalDest()->getSinglePredecessor()) { + unsigned SuccNum = + GetSuccessorNumber(II->getParent(), II->getNormalDest()); + assert(isCriticalEdge(II, SuccNum) && "Expected a critical edge!"); + BasicBlock *NewBlock = SplitCriticalEdge(II, SuccNum); + assert(NewBlock && "Unable to split critical edge."); + // Update the color mapping for the newly split edge. + std::set &ColorsForUsingBB = BlockColors[II->getParent()]; + BlockColors[NewBlock] = ColorsForUsingBB; + for (BasicBlock *FuncletPad : ColorsForUsingBB) + FuncletBlocks[FuncletPad].insert(NewBlock); + } + InsertPt = II->getNormalDest()->getFirstInsertionPt(); + } else { + InsertPt = cast(V); + ++InsertPt; + // Don't insert before PHI nodes or EH pad instrs. + for (; isa(InsertPt) || InsertPt->isEHPad(); ++InsertPt) + ; + } + new StoreInst(V, SpillSlot, InsertPt); + } +} + +void WinEHPrepare::replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot, + DenseMap &Loads, + Function &F) { + // Lazilly create the spill slot. + if (!SpillSlot) + SpillSlot = new AllocaInst(V->getType(), nullptr, + Twine(V->getName(), ".wineh.spillslot"), + F.getEntryBlock().begin()); + + auto *UsingInst = cast(U.getUser()); + if (auto *UsingPHI = dyn_cast(UsingInst)) { + // If this is a PHI node, we can't insert a load of the value before + // the use. Instead insert the load in the predecessor block + // corresponding to the incoming value. + // + // Note that if there are multiple edges from a basic block to this + // PHI node that we cannot have multiple loads. The problem is that + // the resulting PHI node will have multiple values (from each load) + // coming in from the same block, which is illegal SSA form. + // For this reason, we keep track of and reuse loads we insert. + BasicBlock *IncomingBlock = UsingPHI->getIncomingBlock(U); + if (auto *CatchRet = + dyn_cast(IncomingBlock->getTerminator())) { + // Putting a load above a catchret and use on the phi would still leave + // a cross-funclet def/use. We need to split the edge, change the + // catchret to target the new block, and put the load there. + BasicBlock *PHIBlock = UsingInst->getParent(); + BasicBlock *NewBlock = SplitEdge(IncomingBlock, PHIBlock); + // SplitEdge gives us: + // IncomingBlock: + // ... + // br label %NewBlock + // NewBlock: + // catchret label %PHIBlock + // But we need: + // IncomingBlock: + // ... + // catchret label %NewBlock + // NewBlock: + // br label %PHIBlock + // So move the terminators to each others' blocks and swap their + // successors. + BranchInst *Goto = cast(IncomingBlock->getTerminator()); + Goto->removeFromParent(); + CatchRet->removeFromParent(); + IncomingBlock->getInstList().push_back(CatchRet); + NewBlock->getInstList().push_back(Goto); + Goto->setSuccessor(0, PHIBlock); + CatchRet->setSuccessor(NewBlock); + // Update the color mapping for the newly split edge. + std::set &ColorsForPHIBlock = BlockColors[PHIBlock]; + BlockColors[NewBlock] = ColorsForPHIBlock; + for (BasicBlock *FuncletPad : ColorsForPHIBlock) + FuncletBlocks[FuncletPad].insert(NewBlock); + // Treat the new block as incoming for load insertion. + IncomingBlock = NewBlock; + } + Value *&Load = Loads[IncomingBlock]; + // Insert the load into the predecessor block + if (!Load) + Load = new LoadInst(SpillSlot, Twine(V->getName(), ".wineh.reload"), + /*Volatile=*/false, IncomingBlock->getTerminator()); + + U.set(Load); + } else { + // Reload right before the old use. + auto *Load = new LoadInst(SpillSlot, Twine(V->getName(), ".wineh.reload"), + /*Volatile=*/false, UsingInst); + U.set(Load); + } +} + +void WinEHFuncInfo::addIPToStateRange(const BasicBlock *PadBB, + MCSymbol *InvokeBegin, + MCSymbol *InvokeEnd) { + assert(PadBB->isEHPad() && EHPadStateMap.count(PadBB->getFirstNonPHI()) && + "should get EH pad BB with precomputed state"); + InvokeToStateMap[InvokeBegin] = + std::make_pair(EHPadStateMap[PadBB->getFirstNonPHI()], InvokeEnd); +}