diff options
Diffstat (limited to 'llvm/lib/CodeGen')
-rw-r--r-- | llvm/lib/CodeGen/AsmPrinter/WinException.cpp | 113 | ||||
-rw-r--r-- | llvm/lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp | 4 | ||||
-rw-r--r-- | llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp | 63 | ||||
-rw-r--r-- | llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h | 3 | ||||
-rw-r--r-- | llvm/lib/CodeGen/TargetLoweringBase.cpp | 9 | ||||
-rw-r--r-- | llvm/lib/CodeGen/WinEHPrepare.cpp | 1685 |
6 files changed, 428 insertions, 1449 deletions
diff --git a/llvm/lib/CodeGen/AsmPrinter/WinException.cpp b/llvm/lib/CodeGen/AsmPrinter/WinException.cpp index cd1f3f51bc4..e2994172415 100644 --- a/llvm/lib/CodeGen/AsmPrinter/WinException.cpp +++ b/llvm/lib/CodeGen/AsmPrinter/WinException.cpp @@ -344,42 +344,32 @@ class InvokeStateChangeIterator { InvokeStateChangeIterator(const WinEHFuncInfo &EHInfo, MachineFunction::const_iterator MFI, MachineFunction::const_iterator MFE, - MachineBasicBlock::const_iterator MBBI) - : EHInfo(EHInfo), MFI(MFI), MFE(MFE), MBBI(MBBI) { + MachineBasicBlock::const_iterator MBBI, + int BaseState) + : EHInfo(EHInfo), MFI(MFI), MFE(MFE), MBBI(MBBI), BaseState(BaseState) { LastStateChange.PreviousEndLabel = nullptr; LastStateChange.NewStartLabel = nullptr; - LastStateChange.NewState = NullState; + LastStateChange.NewState = BaseState; scan(); } public: static iterator_range<InvokeStateChangeIterator> - range(const WinEHFuncInfo &EHInfo, const MachineFunction &MF) { - // Reject empty MFs to simplify bookkeeping by ensuring that we can get the - // end of the last block. - assert(!MF.empty()); - auto FuncBegin = MF.begin(); - auto FuncEnd = MF.end(); - auto BlockBegin = FuncBegin->begin(); - auto BlockEnd = MF.back().end(); - return make_range( - InvokeStateChangeIterator(EHInfo, FuncBegin, FuncEnd, BlockBegin), - InvokeStateChangeIterator(EHInfo, FuncEnd, FuncEnd, BlockEnd)); - } - static iterator_range<InvokeStateChangeIterator> range(const WinEHFuncInfo &EHInfo, MachineFunction::const_iterator Begin, - MachineFunction::const_iterator End) { + MachineFunction::const_iterator End, int BaseState = NullState) { // Reject empty ranges to simplify bookkeeping by ensuring that we can get // the end of the last block. assert(Begin != End); auto BlockBegin = Begin->begin(); auto BlockEnd = std::prev(End)->end(); - return make_range(InvokeStateChangeIterator(EHInfo, Begin, End, BlockBegin), - InvokeStateChangeIterator(EHInfo, End, End, BlockEnd)); + return make_range( + InvokeStateChangeIterator(EHInfo, Begin, End, BlockBegin, BaseState), + InvokeStateChangeIterator(EHInfo, End, End, BlockEnd, BaseState)); } // Iterator methods. bool operator==(const InvokeStateChangeIterator &O) const { + assert(BaseState == O.BaseState); // Must be visiting same block. if (MFI != O.MFI) return false; @@ -410,6 +400,7 @@ private: MachineBasicBlock::const_iterator MBBI; InvokeStateChange LastStateChange; bool VisitingInvoke = false; + int BaseState; }; } // end anonymous namespace @@ -421,14 +412,14 @@ InvokeStateChangeIterator &InvokeStateChangeIterator::scan() { MBBI = MFI->begin(); for (auto MBBE = MFI->end(); MBBI != MBBE; ++MBBI) { const MachineInstr &MI = *MBBI; - if (!VisitingInvoke && LastStateChange.NewState != NullState && + if (!VisitingInvoke && LastStateChange.NewState != BaseState && MI.isCall() && !EHStreamer::callToNoUnwindFunction(&MI)) { // Indicate a change of state to the null state. We don't have // start/end EH labels handy but the caller won't expect them for // null state regions. LastStateChange.PreviousEndLabel = CurrentEndLabel; LastStateChange.NewStartLabel = nullptr; - LastStateChange.NewState = NullState; + LastStateChange.NewState = BaseState; CurrentEndLabel = nullptr; // Don't re-visit this instr on the next scan ++MBBI; @@ -443,18 +434,12 @@ InvokeStateChangeIterator &InvokeStateChangeIterator::scan() { VisitingInvoke = false; continue; } - auto InvokeMapIter = EHInfo.InvokeToStateMap.find(Label); + auto InvokeMapIter = EHInfo.LabelToStateMap.find(Label); // Ignore EH labels that aren't the ones inserted before an invoke - if (InvokeMapIter == EHInfo.InvokeToStateMap.end()) + if (InvokeMapIter == EHInfo.LabelToStateMap.end()) continue; auto &StateAndEnd = InvokeMapIter->second; int NewState = StateAndEnd.first; - // Ignore EH labels explicitly annotated with the null state (which - // can happen for invokes that unwind to a chain of endpads the last - // of which unwinds to caller). We'll see the subsequent invoke and - // report a transition to the null state same as we do for calls. - if (NewState == NullState) - continue; // Keep track of the fact that we're between EH start/end labels so // we know not to treat the inoke we'll see as unwinding to caller. VisitingInvoke = true; @@ -476,11 +461,11 @@ InvokeStateChangeIterator &InvokeStateChangeIterator::scan() { } } // Iteration hit the end of the block range. - if (LastStateChange.NewState != NullState) { + if (LastStateChange.NewState != BaseState) { // Report the end of the last new state LastStateChange.PreviousEndLabel = CurrentEndLabel; LastStateChange.NewStartLabel = nullptr; - LastStateChange.NewState = NullState; + LastStateChange.NewState = BaseState; // Leave CurrentEndLabel non-null to distinguish this state from end. assert(CurrentEndLabel != nullptr); return *this; @@ -775,26 +760,54 @@ void WinException::emitCXXFrameHandler3Table(const MachineFunction *MF) { void WinException::computeIP2StateTable( const MachineFunction *MF, const WinEHFuncInfo &FuncInfo, SmallVectorImpl<std::pair<const MCExpr *, int>> &IPToStateTable) { - // Indicate that all calls from the prologue to the first invoke unwind to - // caller. We handle this as a special case since other ranges starting at end - // labels need to use LtmpN+1. - MCSymbol *StartLabel = Asm->getFunctionBegin(); - assert(StartLabel && "need local function start label"); - IPToStateTable.push_back(std::make_pair(create32bitRef(StartLabel), -1)); - - // FIXME: Do we need to emit entries for funclet base states? - for (const auto &StateChange : - InvokeStateChangeIterator::range(FuncInfo, *MF)) { - // Compute the label to report as the start of this entry; use the EH start - // label for the invoke if we have one, otherwise (this is a call which may - // unwind to our caller and does not have an EH start label, so) use the - // previous end label. - const MCSymbol *ChangeLabel = StateChange.NewStartLabel; - if (!ChangeLabel) - ChangeLabel = StateChange.PreviousEndLabel; - // Emit an entry indicating that PCs after 'Label' have this EH state. + + for (MachineFunction::const_iterator FuncletStart = MF->begin(), + FuncletEnd = MF->begin(), + End = MF->end(); + FuncletStart != End; FuncletStart = FuncletEnd) { + // Find the end of the funclet + while (++FuncletEnd != End) { + if (FuncletEnd->isEHFuncletEntry()) { + break; + } + } + + // Don't emit ip2state entries for cleanup funclets. Any interesting + // exceptional actions in cleanups must be handled in a separate IR + // function. + if (FuncletStart->isCleanupFuncletEntry()) + continue; + + MCSymbol *StartLabel; + int BaseState; + if (FuncletStart == MF->begin()) { + BaseState = NullState; + StartLabel = Asm->getFunctionBegin(); + } else { + auto *FuncletPad = + cast<FuncletPadInst>(FuncletStart->getBasicBlock()->getFirstNonPHI()); + assert(FuncInfo.FuncletBaseStateMap.count(FuncletPad) != 0); + BaseState = FuncInfo.FuncletBaseStateMap.find(FuncletPad)->second; + StartLabel = getMCSymbolForMBB(Asm, &*FuncletStart); + } + assert(StartLabel && "need local function start label"); IPToStateTable.push_back( - std::make_pair(getLabelPlusOne(ChangeLabel), StateChange.NewState)); + std::make_pair(create32bitRef(StartLabel), BaseState)); + + for (const auto &StateChange : InvokeStateChangeIterator::range( + FuncInfo, FuncletStart, FuncletEnd, BaseState)) { + // Compute the label to report as the start of this entry; use the EH + // start label for the invoke if we have one, otherwise (this is a call + // which may unwind to our caller and does not have an EH start label, so) + // use the previous end label. + const MCSymbol *ChangeLabel = StateChange.NewStartLabel; + if (!ChangeLabel) + ChangeLabel = StateChange.PreviousEndLabel; + // Emit an entry indicating that PCs after 'Label' have this EH state. + IPToStateTable.push_back( + std::make_pair(getLabelPlusOne(ChangeLabel), StateChange.NewState)); + // FIXME: assert that NewState is between CatchLow and CatchHigh. + } } } diff --git a/llvm/lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp b/llvm/lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp index ff0ccd415db..6ae38d3258d 100644 --- a/llvm/lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp +++ b/llvm/lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp @@ -225,12 +225,12 @@ void FunctionLoweringInfo::set(const Function &fn, MachineFunction &mf, MMI.setHasEHFunclets(true); MF->getFrameInfo()->setHasOpaqueSPAdjustment(true); } - if (isa<CatchEndPadInst>(I) || isa<CleanupEndPadInst>(I)) { + if (isa<CatchSwitchInst>(I)) { assert(&*BB->begin() == I && "WinEHPrepare failed to remove PHIs from imaginary BBs"); continue; } - if (isa<CatchPadInst>(I) || isa<CleanupPadInst>(I)) + if (isa<FuncletPadInst>(I)) assert(&*BB->begin() == I && "WinEHPrepare failed to demote PHIs"); } diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp index dc2a57a860f..506115c7856 100644 --- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp +++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp @@ -1184,21 +1184,7 @@ void SelectionDAGBuilder::visitCatchPad(const CatchPadInst &I) { if (IsMSVCCXX || IsCoreCLR) CatchPadMBB->setIsEHFuncletEntry(); - MachineBasicBlock *NormalDestMBB = FuncInfo.MBBMap[I.getNormalDest()]; - - // Update machine-CFG edge. - FuncInfo.MBB->addSuccessor(NormalDestMBB); - - SDValue Chain = - DAG.getNode(ISD::CATCHPAD, getCurSDLoc(), MVT::Other, getControlRoot()); - - // If this is not a fall-through branch or optimizations are switched off, - // emit the branch. - if (NormalDestMBB != NextBlock(CatchPadMBB) || - TM.getOptLevel() == CodeGenOpt::None) - Chain = DAG.getNode(ISD::BR, getCurSDLoc(), MVT::Other, Chain, - DAG.getBasicBlock(NormalDestMBB)); - DAG.setRoot(Chain); + DAG.setRoot(DAG.getNode(ISD::CATCHPAD, getCurSDLoc(), MVT::Other, getControlRoot())); } void SelectionDAGBuilder::visitCatchRet(const CatchReturnInst &I) { @@ -1234,10 +1220,6 @@ void SelectionDAGBuilder::visitCatchRet(const CatchReturnInst &I) { DAG.setRoot(Ret); } -void SelectionDAGBuilder::visitCatchEndPad(const CatchEndPadInst &I) { - llvm_unreachable("should never codegen catchendpads"); -} - void SelectionDAGBuilder::visitCleanupPad(const CleanupPadInst &CPI) { // Don't emit any special code for the cleanuppad instruction. It just marks // the start of a funclet. @@ -1248,8 +1230,8 @@ void SelectionDAGBuilder::visitCleanupPad(const CleanupPadInst &CPI) { /// When an invoke or a cleanupret unwinds to the next EH pad, there are /// many places it could ultimately go. In the IR, we have a single unwind /// destination, but in the machine CFG, we enumerate all the possible blocks. -/// This function skips over imaginary basic blocks that hold catchpad, -/// terminatepad, or catchendpad instructions, and finds all the "real" machine +/// This function skips over imaginary basic blocks that hold catchswitch or +/// terminatepad instructions, and finds all the "real" machine /// basic block destinations. As those destinations may not be successors of /// EHPadBB, here we also calculate the edge probability to those destinations. /// The passed-in Prob is the edge probability to EHPadBB. @@ -1276,19 +1258,18 @@ static void findUnwindDestinations( UnwindDests.emplace_back(FuncInfo.MBBMap[EHPadBB], Prob); UnwindDests.back().first->setIsEHFuncletEntry(); break; - } else if (const auto *CPI = dyn_cast<CatchPadInst>(Pad)) { - // Add the catchpad handler to the possible destinations. - UnwindDests.emplace_back(FuncInfo.MBBMap[EHPadBB], Prob); - // In MSVC C++, catchblocks are funclets and need prologues. - if (IsMSVCCXX || IsCoreCLR) - UnwindDests.back().first->setIsEHFuncletEntry(); - NewEHPadBB = CPI->getUnwindDest(); - } else if (const auto *CEPI = dyn_cast<CatchEndPadInst>(Pad)) - NewEHPadBB = CEPI->getUnwindDest(); - else if (const auto *CEPI = dyn_cast<CleanupEndPadInst>(Pad)) - NewEHPadBB = CEPI->getUnwindDest(); - else + } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Pad)) { + // Add the catchpad handlers to the possible destinations. + for (const BasicBlock *CatchPadBB : CatchSwitch->handlers()) { + UnwindDests.emplace_back(FuncInfo.MBBMap[CatchPadBB], Prob); + // For MSVC++ and the CLR, catchblocks are funclets and need prologues. + if (IsMSVCCXX || IsCoreCLR) + UnwindDests.back().first->setIsEHFuncletEntry(); + } + NewEHPadBB = CatchSwitch->getUnwindDest(); + } else { continue; + } BranchProbabilityInfo *BPI = FuncInfo.BPI; if (BPI && NewEHPadBB) @@ -1319,14 +1300,14 @@ void SelectionDAGBuilder::visitCleanupRet(const CleanupReturnInst &I) { DAG.setRoot(Ret); } -void SelectionDAGBuilder::visitCleanupEndPad(const CleanupEndPadInst &I) { - report_fatal_error("visitCleanupEndPad not yet implemented!"); -} - void SelectionDAGBuilder::visitTerminatePad(const TerminatePadInst &TPI) { report_fatal_error("visitTerminatePad not yet implemented!"); } +void SelectionDAGBuilder::visitCatchSwitch(const CatchSwitchInst &CSI) { + report_fatal_error("visitCatchSwitch not yet implemented!"); +} + void SelectionDAGBuilder::visitRet(const ReturnInst &I) { const TargetLowering &TLI = DAG.getTargetLoweringInfo(); auto &DL = DAG.getDataLayout(); @@ -2124,8 +2105,8 @@ void SelectionDAGBuilder::visitBitTestCase(BitTestBlock &BB, void SelectionDAGBuilder::visitInvoke(const InvokeInst &I) { MachineBasicBlock *InvokeMBB = FuncInfo.MBB; - // Retrieve successors. Look through artificial IR level blocks like catchpads - // and catchendpads for successors. + // Retrieve successors. Look through artificial IR level blocks like + // catchswitch for successors. MachineBasicBlock *Return = FuncInfo.MBBMap[I.getSuccessor(0)]; const BasicBlock *EHPadBB = I.getSuccessor(1); @@ -5367,8 +5348,10 @@ SelectionDAGBuilder::lowerInvokable(TargetLowering::CallLoweringInfo &CLI, // Inform MachineModuleInfo of range. if (MMI.hasEHFunclets()) { + assert(CLI.CS); WinEHFuncInfo *EHInfo = DAG.getMachineFunction().getWinEHFuncInfo(); - EHInfo->addIPToStateRange(EHPadBB, BeginLabel, EndLabel); + EHInfo->addIPToStateRange(cast<InvokeInst>(CLI.CS->getInstruction()), + BeginLabel, EndLabel); } else { MMI.addInvoke(FuncInfo.MBBMap[EHPadBB], BeginLabel, EndLabel); } diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h index 1171f0aad00..4f8e8132c4a 100644 --- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h +++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h @@ -736,9 +736,8 @@ private: void visitSwitch(const SwitchInst &I); void visitIndirectBr(const IndirectBrInst &I); void visitUnreachable(const UnreachableInst &I); - void visitCleanupEndPad(const CleanupEndPadInst &I); void visitCleanupRet(const CleanupReturnInst &I); - void visitCatchEndPad(const CatchEndPadInst &I); + void visitCatchSwitch(const CatchSwitchInst &I); void visitCatchRet(const CatchReturnInst &I); void visitCatchPad(const CatchPadInst &I); void visitTerminatePad(const TerminatePadInst &TPI); diff --git a/llvm/lib/CodeGen/TargetLoweringBase.cpp b/llvm/lib/CodeGen/TargetLoweringBase.cpp index c5972263046..74a42f8ee34 100644 --- a/llvm/lib/CodeGen/TargetLoweringBase.cpp +++ b/llvm/lib/CodeGen/TargetLoweringBase.cpp @@ -1570,13 +1570,12 @@ int TargetLoweringBase::InstructionOpcodeToISD(unsigned Opcode) const { case Invoke: return 0; case Resume: return 0; case Unreachable: return 0; - case CleanupEndPad: return 0; case CleanupRet: return 0; - case CatchEndPad: return 0; case CatchRet: return 0; - case CatchPad: return 0; - case TerminatePad: return 0; - case CleanupPad: return 0; + case CatchPad: return 0; + case CatchSwitch: return 0; + case TerminatePad: return 0; + case CleanupPad: return 0; case Add: return ISD::ADD; case FAdd: return ISD::FADD; case Sub: return ISD::SUB; diff --git a/llvm/lib/CodeGen/WinEHPrepare.cpp b/llvm/lib/CodeGen/WinEHPrepare.cpp index dee4b870434..9f199a15718 100644 --- a/llvm/lib/CodeGen/WinEHPrepare.cpp +++ b/llvm/lib/CodeGen/WinEHPrepare.cpp @@ -17,7 +17,7 @@ //===----------------------------------------------------------------------===// #include "llvm/CodeGen/Passes.h" -#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/MapVector.h" #include "llvm/Analysis/CFG.h" #include "llvm/Analysis/EHPersonalities.h" #include "llvm/CodeGen/WinEHFuncInfo.h" @@ -69,27 +69,12 @@ private: AllocaInst *insertPHILoads(PHINode *PN, Function &F); void replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot, DenseMap<BasicBlock *, Value *> &Loads, Function &F); - bool prepareExplicitEH(Function &F, - SmallVectorImpl<BasicBlock *> &EntryBlocks); + bool prepareExplicitEH(Function &F); void replaceTerminatePadWithCleanup(Function &F); - void colorFunclets(Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks); - void resolveFuncletAncestry(Function &F, - SmallVectorImpl<BasicBlock *> &EntryBlocks); - void resolveFuncletAncestryForPath( - Function &F, SmallVectorImpl<BasicBlock *> &FuncletPath, - std::map<BasicBlock *, BasicBlock *> &IdentityMap); - void makeFuncletEdgeUnreachable(BasicBlock *Parent, BasicBlock *Child); - BasicBlock *cloneFuncletForParent(Function &F, BasicBlock *FuncletEntry, - BasicBlock *Parent); - void updateTerminatorsAfterFuncletClone( - Function &F, BasicBlock *OrigFunclet, BasicBlock *CloneFunclet, - BasicBlock *OrigBlock, BasicBlock *CloneBlock, BasicBlock *CloneParent, - ValueToValueMapTy &VMap, - std::map<BasicBlock *, BasicBlock *> &Orig2Clone); + void colorFunclets(Function &F); void demotePHIsOnFunclets(Function &F); - void cloneCommonBlocks(Function &F, - SmallVectorImpl<BasicBlock *> &EntryBlocks); + void cloneCommonBlocks(Function &F); void removeImplausibleTerminators(Function &F); void cleanupPreparedFunclets(Function &F); void verifyPreparedFunclets(Function &F); @@ -97,20 +82,8 @@ private: // All fields are reset by runOnFunction. EHPersonality Personality = EHPersonality::Unknown; - std::map<BasicBlock *, SetVector<BasicBlock *>> BlockColors; - std::map<BasicBlock *, std::set<BasicBlock *>> FuncletBlocks; - std::map<BasicBlock *, std::vector<BasicBlock *>> FuncletChildren; - std::map<BasicBlock *, std::vector<BasicBlock *>> FuncletParents; - - // This is a flag that indicates an uncommon situation where we need to - // clone funclets has been detected. - bool FuncletCloningRequired = false; - // When a funclet with multiple parents contains a catchret, the block to - // which it returns will be cloned so that there is a copy in each parent - // but one of the copies will not be properly linked to the catchret and - // in most cases will have no predecessors. This double map allows us - // to find these cloned blocks when we clone the child funclet. - std::map<BasicBlock *, std::map<BasicBlock *, BasicBlock*>> EstrangedBlocks; + DenseMap<BasicBlock *, ColorVector> BlockColors; + MapVector<BasicBlock *, std::vector<BasicBlock *>> FuncletBlocks; }; } // end anonymous namespace @@ -123,21 +96,6 @@ FunctionPass *llvm::createWinEHPass(const TargetMachine *TM) { return new WinEHPrepare(TM); } -static void findFuncletEntryPoints(Function &Fn, - SmallVectorImpl<BasicBlock *> &EntryBlocks) { - EntryBlocks.push_back(&Fn.getEntryBlock()); - for (BasicBlock &BB : Fn) { - Instruction *First = BB.getFirstNonPHI(); - if (!First->isEHPad()) - continue; - assert(!isa<LandingPadInst>(First) && - "landingpad cannot be used with funclet EH personality"); - // Find EH pad blocks that represent funclet start points. - if (!isa<CatchEndPadInst>(First) && !isa<CleanupEndPadInst>(First)) - EntryBlocks.push_back(&BB); - } -} - bool WinEHPrepare::runOnFunction(Function &Fn) { if (!Fn.hasPersonalityFn()) return false; @@ -149,14 +107,7 @@ bool WinEHPrepare::runOnFunction(Function &Fn) { if (!isFuncletEHPersonality(Personality)) return false; - // 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(Fn); - - SmallVector<BasicBlock *, 4> EntryBlocks; - findFuncletEntryPoints(Fn, EntryBlocks); - return prepareExplicitEH(Fn, EntryBlocks); + return prepareExplicitEH(Fn); } bool WinEHPrepare::doFinalization(Module &M) { return false; } @@ -198,117 +149,142 @@ static void addTryBlockMapEntry(WinEHFuncInfo &FuncInfo, int TryLow, FuncInfo.TryBlockMap.push_back(TBME); } -static const CatchPadInst *getSingleCatchPadPredecessor(const BasicBlock *BB) { - for (const BasicBlock *PredBlock : predecessors(BB)) - if (auto *CPI = dyn_cast<CatchPadInst>(PredBlock->getFirstNonPHI())) - return CPI; +static BasicBlock *getCleanupRetUnwindDest(const CleanupPadInst *CleanupPad) { + for (const User *U : CleanupPad->users()) + if (const auto *CRI = dyn_cast<CleanupReturnInst>(U)) + return CRI->getUnwindDest(); 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<const CatchPadInst *> &Handlers) { - const CatchPadInst *CPI = getSingleCatchPadPredecessor(CatchEndBB); - while (CPI) { - Handlers.push_back(CPI); - CPI = getSingleCatchPadPredecessor(CPI->getParent()); +static void calculateStateNumbersForInvokes(const Function *Fn, + WinEHFuncInfo &FuncInfo) { + auto *F = const_cast<Function *>(Fn); + DenseMap<BasicBlock *, ColorVector> BlockColors = colorEHFunclets(*F); + for (BasicBlock &BB : *F) { + auto *II = dyn_cast<InvokeInst>(BB.getTerminator()); + if (!II) + continue; + + auto &BBColors = BlockColors[&BB]; + assert(BBColors.size() == 1 && + "multi-color BB not removed by preparation"); + BasicBlock *FuncletEntryBB = BBColors.front(); + + BasicBlock *FuncletUnwindDest; + auto *FuncletPad = + dyn_cast<FuncletPadInst>(FuncletEntryBB->getFirstNonPHI()); + assert(FuncletPad || FuncletEntryBB == &Fn->getEntryBlock()); + if (!FuncletPad) + FuncletUnwindDest = nullptr; + else if (auto *CatchPad = dyn_cast<CatchPadInst>(FuncletPad)) + FuncletUnwindDest = CatchPad->getCatchSwitch()->getUnwindDest(); + else if (auto *CleanupPad = dyn_cast<CleanupPadInst>(FuncletPad)) + FuncletUnwindDest = getCleanupRetUnwindDest(CleanupPad); + else + llvm_unreachable("unexpected funclet pad!"); + + BasicBlock *InvokeUnwindDest = II->getUnwindDest(); + int BaseState = -1; + if (FuncletUnwindDest == InvokeUnwindDest) { + auto BaseStateI = FuncInfo.FuncletBaseStateMap.find(FuncletPad); + if (BaseStateI != FuncInfo.FuncletBaseStateMap.end()) + BaseState = BaseStateI->second; + } + + if (BaseState != -1) { + FuncInfo.InvokeStateMap[II] = BaseState; + } else { + Instruction *PadInst = InvokeUnwindDest->getFirstNonPHI(); + assert(FuncInfo.EHPadStateMap.count(PadInst) && "EH Pad has no state!"); + FuncInfo.InvokeStateMap[II] = FuncInfo.EHPadStateMap[PadInst]; + } } - // 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) { +static const BasicBlock *getEHPadFromPredecessor(const BasicBlock *BB, + Value *ParentPad) { const TerminatorInst *TI = BB->getTerminator(); if (isa<InvokeInst>(TI)) return nullptr; - if (TI->isEHPad()) + if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) { + if (CatchSwitch->getParentPad() != ParentPad) + return nullptr; return BB; - return cast<CleanupReturnInst>(TI)->getCleanupPad()->getParent(); + } + assert(!TI->isEHPad() && "unexpected EHPad!"); + auto *CleanupPad = cast<CleanupReturnInst>(TI)->getCleanupPad(); + if (CleanupPad->getParentPad() != ParentPad) + return nullptr; + return CleanupPad->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<CatchPadInst>(FirstNonPHI)) - return; +static void calculateCXXStateNumbers(WinEHFuncInfo &FuncInfo, + const Instruction *FirstNonPHI, + int ParentState) { + const BasicBlock *BB = FirstNonPHI->getParent(); + assert(BB->isEHPad() && "not a funclet!"); + + if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(FirstNonPHI)) { + assert(FuncInfo.EHPadStateMap.count(CatchSwitch) == 0 && + "shouldn't revist catch funclets!"); - if (isa<CatchEndPadInst>(FirstNonPHI)) { SmallVector<const CatchPadInst *, 2> Handlers; - findCatchPadsForCatchEndPad(&BB, Handlers); - const BasicBlock *FirstTryPad = Handlers.front()->getParent(); + for (const BasicBlock *CatchPadBB : CatchSwitch->handlers()) { + auto *CatchPad = cast<CatchPadInst>(CatchPadBB->getFirstNonPHI()); + Handlers.push_back(CatchPad); + } 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); + FuncInfo.EHPadStateMap[CatchSwitch] = TryLow; + for (const BasicBlock *PredBlock : predecessors(BB)) + if ((PredBlock = getEHPadFromPredecessor(PredBlock, + CatchSwitch->getParentPad()))) + calculateCXXStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(), + 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); + for (const auto *CatchPad : Handlers) { + FuncInfo.FuncletBaseStateMap[CatchPad] = CatchLow; + for (const User *U : CatchPad->users()) { + const auto *UserI = cast<Instruction>(U); + if (UserI->isEHPad()) + calculateCXXStateNumbers(FuncInfo, UserI, CatchLow); + } + } int CatchHigh = FuncInfo.getLastStateNumber(); addTryBlockMapEntry(FuncInfo, TryLow, TryHigh, CatchHigh, Handlers); - DEBUG(dbgs() << "TryLow[" << FirstTryPad->getName() << "]: " << TryLow + DEBUG(dbgs() << "TryLow[" << BB->getName() << "]: " << TryLow << '\n'); + DEBUG(dbgs() << "TryHigh[" << BB->getName() << "]: " << TryHigh << '\n'); + DEBUG(dbgs() << "CatchHigh[" << BB->getName() << "]: " << CatchHigh << '\n'); - DEBUG(dbgs() << "TryHigh[" << FirstTryPad->getName() << "]: " << TryHigh - << '\n'); - DEBUG(dbgs() << "CatchHigh[" << FirstTryPad->getName() << "]: " << CatchHigh - << '\n'); - } else if (isa<CleanupPadInst>(FirstNonPHI)) { - // A cleanup can have multiple exits; don't re-process after the first. - if (FuncInfo.EHPadStateMap.count(FirstNonPHI)) + } else { + auto *CleanupPad = cast<CleanupPadInst>(FirstNonPHI); + + // It's possible for a cleanup to be visited twice: it might have multiple + // cleanupret instructions. + if (FuncInfo.EHPadStateMap.count(CleanupPad)) return; - int CleanupState = addUnwindMapEntry(FuncInfo, ParentState, &BB); - FuncInfo.EHPadStateMap[FirstNonPHI] = CleanupState; + + int CleanupState = addUnwindMapEntry(FuncInfo, ParentState, BB); + FuncInfo.EHPadStateMap[CleanupPad] = 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 (auto *CEPI = dyn_cast<CleanupEndPadInst>(FirstNonPHI)) { - // Propagate ParentState to the cleanuppad in case it doesn't have - // any cleanuprets. - BasicBlock *CleanupBlock = CEPI->getCleanupPad()->getParent(); - calculateExplicitCXXStateNumbers(FuncInfo, *CleanupBlock, ParentState); - // Anything unwinding through CleanupEndPadInst is in ParentState. - FuncInfo.EHPadStateMap[FirstNonPHI] = ParentState; - for (const BasicBlock *PredBlock : predecessors(&BB)) - if ((PredBlock = getEHPadFromPredecessor(PredBlock))) - calculateExplicitCXXStateNumbers(FuncInfo, *PredBlock, ParentState); - } else if (isa<TerminatePadInst>(FirstNonPHI)) { - report_fatal_error("Not yet implemented!"); - } else { - llvm_unreachable("unexpected EH Pad!"); + << BB->getName() << '\n'); + for (const BasicBlock *PredBlock : predecessors(BB)) { + if ((PredBlock = getEHPadFromPredecessor(PredBlock, + CleanupPad->getParentPad()))) { + calculateCXXStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(), + CleanupState); + } + } + for (const User *U : CleanupPad->users()) { + const auto *UserI = cast<Instruction>(U); + if (UserI->isEHPad()) + report_fatal_error("Cleanup funclets for the MSVC++ personality cannot " + "contain exceptional actions"); + } } } @@ -334,94 +310,84 @@ static int addSEHFinally(WinEHFuncInfo &FuncInfo, int ParentState, 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<CatchPadInst>(FirstNonPHI)) - return; +static void calculateSEHStateNumbers(WinEHFuncInfo &FuncInfo, + const Instruction *FirstNonPHI, + int ParentState) { + const BasicBlock *BB = FirstNonPHI->getParent(); + assert(BB->isEHPad() && "no a funclet!"); + + if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(FirstNonPHI)) { + assert(FuncInfo.EHPadStateMap.count(CatchSwitch) == 0 && + "shouldn't revist catch funclets!"); - if (isa<CatchEndPadInst>(FirstNonPHI)) { // Extract the filter function and the __except basic block and create a // state for them. - SmallVector<const CatchPadInst *, 1> Handlers; - findCatchPadsForCatchEndPad(&BB, Handlers); - assert(Handlers.size() == 1 && + assert(CatchSwitch->getNumHandlers() == 1 && "SEH doesn't have multiple handlers per __try"); - const CatchPadInst *CPI = Handlers.front(); - const BasicBlock *CatchPadBB = CPI->getParent(); + const auto *CatchPad = + cast<CatchPadInst>((*CatchSwitch->handler_begin())->getFirstNonPHI()); + const BasicBlock *CatchPadBB = CatchPad->getParent(); const Constant *FilterOrNull = - cast<Constant>(CPI->getArgOperand(0)->stripPointerCasts()); + cast<Constant>(CatchPad->getArgOperand(0)->stripPointerCasts()); const Function *Filter = dyn_cast<Function>(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; + FuncInfo.EHPadStateMap[CatchSwitch] = 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); + for (const BasicBlock *PredBlock : predecessors(BB)) + if ((PredBlock = getEHPadFromPredecessor(PredBlock, + CatchSwitch->getParentPad()))) + calculateSEHStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(), + 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<CleanupPadInst>(FirstNonPHI)) { - // A cleanup can have multiple exits; don't re-process after the first. - if (FuncInfo.EHPadStateMap.count(FirstNonPHI)) + for (const User *U : CatchPad->users()) { + const auto *UserI = cast<Instruction>(U); + if (UserI->isEHPad()) { + calculateSEHStateNumbers(FuncInfo, UserI, ParentState); + } + } + } else { + auto *CleanupPad = cast<CleanupPadInst>(FirstNonPHI); + + // It's possible for a cleanup to be visited twice: it might have multiple + // cleanupret instructions. + if (FuncInfo.EHPadStateMap.count(CleanupPad)) return; - int CleanupState = addSEHFinally(FuncInfo, ParentState, &BB); - FuncInfo.EHPadStateMap[FirstNonPHI] = CleanupState; + + int CleanupState = addSEHFinally(FuncInfo, ParentState, BB); + FuncInfo.EHPadStateMap[CleanupPad] = 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 (auto *CEPI = dyn_cast<CleanupEndPadInst>(FirstNonPHI)) { - // Propagate ParentState to the cleanuppad in case it doesn't have - // any cleanuprets. - BasicBlock *CleanupBlock = CEPI->getCleanupPad()->getParent(); - calculateExplicitSEHStateNumbers(FuncInfo, *CleanupBlock, ParentState); - // 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<TerminatePadInst>(FirstNonPHI)) { - report_fatal_error("Not yet implemented!"); - } else { - llvm_unreachable("unexpected EH Pad!"); + << BB->getName() << '\n'); + for (const BasicBlock *PredBlock : predecessors(BB)) + if ((PredBlock = + getEHPadFromPredecessor(PredBlock, CleanupPad->getParentPad()))) + calculateSEHStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(), + CleanupState); + for (const User *U : CleanupPad->users()) { + const auto *UserI = cast<Instruction>(U); + if (UserI->isEHPad()) + report_fatal_error("Cleanup funclets for the SEH personality cannot " + "contain exceptional actions"); + } } } -/// 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<CleanupPadInst>(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<CleanupReturnInst>(User)) - return CRI->unwindsToCaller(); - return cast<CleanupEndPadInst>(User)->unwindsToCaller(); +static bool isTopLevelPadForMSVC(const Instruction *EHPad) { + if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(EHPad)) + return isa<ConstantTokenNone>(CatchSwitch->getParentPad()) && + CatchSwitch->unwindsToCaller(); + if (auto *CleanupPad = dyn_cast<CleanupPadInst>(EHPad)) + return isa<ConstantTokenNone>(CleanupPad->getParentPad()) && + getCleanupRetUnwindDest(CleanupPad) == nullptr; + if (isa<CatchPadInst>(EHPad)) + return false; + llvm_unreachable("unexpected EHPad!"); } void llvm::calculateSEHStateNumbers(const Function *Fn, @@ -431,10 +397,15 @@ void llvm::calculateSEHStateNumbers(const Function *Fn, return; for (const BasicBlock &BB : *Fn) { - if (!BB.isEHPad() || !doesEHPadUnwindToCaller(BB.getFirstNonPHI())) + if (!BB.isEHPad()) + continue; + const Instruction *FirstNonPHI = BB.getFirstNonPHI(); + if (!isTopLevelPadForMSVC(FirstNonPHI)) continue; - calculateExplicitSEHStateNumbers(FuncInfo, BB, -1); + ::calculateSEHStateNumbers(FuncInfo, FirstNonPHI, -1); } + + calculateStateNumbersForInvokes(Fn, FuncInfo); } void llvm::calculateWinCXXEHStateNumbers(const Function *Fn, @@ -446,13 +417,13 @@ void llvm::calculateWinCXXEHStateNumbers(const Function *Fn, 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(); - if (!doesEHPadUnwindToCaller(FirstNonPHI)) + if (!isTopLevelPadForMSVC(FirstNonPHI)) continue; - calculateExplicitCXXStateNumbers(FuncInfo, BB, -1); + calculateCXXStateNumbers(FuncInfo, FirstNonPHI, -1); } + + calculateStateNumbersForInvokes(Fn, FuncInfo); } static int addClrEHHandler(WinEHFuncInfo &FuncInfo, int ParentState, @@ -483,7 +454,7 @@ void llvm::calculateClrEHStateNumbers(const Function *Fn, if (BB.isLandingPad()) report_fatal_error("CoreCLR EH cannot use landingpads"); const Instruction *FirstNonPHI = BB.getFirstNonPHI(); - if (!doesEHPadUnwindToCaller(FirstNonPHI)) + if (!isTopLevelPadForMSVC(FirstNonPHI)) continue; // queue this with sentinel parent state -1 to mean unwind to caller. Worklist.emplace_back(FirstNonPHI, -1); @@ -494,16 +465,11 @@ void llvm::calculateClrEHStateNumbers(const Function *Fn, int ParentState; std::tie(Pad, ParentState) = Worklist.pop_back_val(); + Value *ParentPad; int PredState; - if (const CleanupEndPadInst *EndPad = dyn_cast<CleanupEndPadInst>(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<CleanupPadInst>(Pad)) { + if (const CleanupPadInst *Cleanup = dyn_cast<CleanupPadInst>(Pad)) { // A cleanup can have multiple exits; don't re-process after the first. - if (FuncInfo.EHPadStateMap.count(Pad)) + if (FuncInfo.EHPadStateMap.count(Cleanup)) continue; // CoreCLR personality uses arity to distinguish faults from finallies. const BasicBlock *PadBlock = Cleanup->getParent(); @@ -514,30 +480,47 @@ void llvm::calculateClrEHStateNumbers(const Function *Fn, addClrEHHandler(FuncInfo, ParentState, HandlerType, 0, PadBlock); FuncInfo.EHPadStateMap[Cleanup] = NewState; // Propagate the new state to all preds of the cleanup + ParentPad = Cleanup->getParentPad(); PredState = NewState; - } else if (const CatchEndPadInst *EndPad = dyn_cast<CatchEndPadInst>(Pad)) { - FuncInfo.EHPadStateMap[EndPad] = ParentState; - // Preds of the endpad should get the parent state. - PredState = ParentState; - } else if (const CatchPadInst *Catch = dyn_cast<CatchPadInst>(Pad)) { - const BasicBlock *PadBlock = Catch->getParent(); - uint32_t TypeToken = static_cast<uint32_t>( - cast<ConstantInt>(Catch->getArgOperand(0))->getZExtValue()); - int NewState = addClrEHHandler(FuncInfo, ParentState, - ClrHandlerType::Catch, TypeToken, PadBlock); - FuncInfo.EHPadStateMap[Catch] = NewState; - // Preds of the catch get its state + } else if (const auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Pad)) { + SmallVector<const CatchPadInst *, 1> Handlers; + for (const BasicBlock *CatchPadBB : CatchSwitch->handlers()) { + const auto *Catch = cast<CatchPadInst>(CatchPadBB->getFirstNonPHI()); + Handlers.push_back(Catch); + } + FuncInfo.EHPadStateMap[CatchSwitch] = ParentState; + int NewState = ParentState; + for (auto HandlerI = Handlers.rbegin(), HandlerE = Handlers.rend(); + HandlerI != HandlerE; ++HandlerI) { + const CatchPadInst *Catch = *HandlerI; + const BasicBlock *PadBlock = Catch->getParent(); + uint32_t TypeToken = static_cast<uint32_t>( + cast<ConstantInt>(Catch->getArgOperand(0))->getZExtValue()); + NewState = addClrEHHandler(FuncInfo, NewState, ClrHandlerType::Catch, + TypeToken, PadBlock); + FuncInfo.EHPadStateMap[Catch] = NewState; + } + for (const auto *CatchPad : Handlers) { + for (const User *U : CatchPad->users()) { + const auto *UserI = cast<Instruction>(U); + if (UserI->isEHPad()) + Worklist.emplace_back(UserI, ParentState); + } + } PredState = NewState; + ParentPad = CatchSwitch->getParentPad(); } else { llvm_unreachable("Unexpected EH pad"); } // Queue all predecessors with the given state for (const BasicBlock *Pred : predecessors(Pad->getParent())) { - if ((Pred = getEHPadFromPredecessor(Pred))) + if ((Pred = getEHPadFromPredecessor(Pred, ParentPad))) Worklist.emplace_back(Pred->getFirstNonPHI(), PredState); } } + + calculateStateNumbersForInvokes(Fn, FuncInfo); } void WinEHPrepare::replaceTerminatePadWithCleanup(Function &F) { @@ -559,8 +542,9 @@ void WinEHPrepare::replaceTerminatePadWithCleanup(Function &F) { "C++ personalities!"); // Insert the cleanuppad instruction. - auto *CPI = CleanupPadInst::Create( - BB.getContext(), {}, Twine("terminatepad.for.", BB.getName()), &BB); + auto *CPI = + CleanupPadInst::Create(TPI->getParentPad(), {}, + Twine("terminatepad.for.", BB.getName()), &BB); // Insert the call to the terminate instruction. auto *CallTerminate = CallInst::Create(TerminateFn, {}, &BB); @@ -578,980 +562,32 @@ void WinEHPrepare::replaceTerminatePadWithCleanup(Function &F) { } } -static void -colorFunclets(Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks, - std::map<BasicBlock *, SetVector<BasicBlock *>> &BlockColors, - std::map<BasicBlock *, std::set<BasicBlock *>> &FuncletBlocks) { - SmallVector<std::pair<BasicBlock *, BasicBlock *>, 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. - - DEBUG_WITH_TYPE("winehprepare-coloring", dbgs() << "\nColoring funclets for " - << F.getName() << "\n"); - - Worklist.push_back({EntryBlock, EntryBlock}); - - while (!Worklist.empty()) { - BasicBlock *Visiting; - BasicBlock *Color; - std::tie(Visiting, Color) = Worklist.pop_back_val(); - DEBUG_WITH_TYPE("winehprepare-coloring", - dbgs() << "Visiting " << Visiting->getName() << ", " - << Color->getName() << "\n"); - Instruction *VisitingHead = Visiting->getFirstNonPHI(); - if (VisitingHead->isEHPad() && !isa<CatchEndPadInst>(VisitingHead) && - !isa<CleanupEndPadInst>(VisitingHead)) { - // Mark this as a funclet head as a member of itself. - FuncletBlocks[Visiting].insert(Visiting); - // Queue exits (i.e. successors of rets/endpads) with the parent color. - // Skip any exits that are catchendpads, since the parent color must then - // represent one of the catches chained to that catchendpad, but the - // catchendpad should get the color of the common parent of all its - // chained catches (i.e. the grandparent color of the current pad). - // We don't need to worry abou catchendpads going unvisited, since the - // catches chained to them must have unwind edges to them by which we will - // visit them. - for (User *U : VisitingHead->users()) { - if (auto *Exit = dyn_cast<TerminatorInst>(U)) { - for (BasicBlock *Succ : successors(Exit->getParent())) - if (!isa<CatchEndPadInst>(*Succ->getFirstNonPHI())) - if (BlockColors[Succ].insert(Color)) { - DEBUG_WITH_TYPE("winehprepare-coloring", - dbgs() << " Assigned color \'" - << Color->getName() << "\' to block \'" - << Succ->getName() << "\'.\n"); - Worklist.push_back({Succ, Color}); - } - } - } - // Handle CatchPad specially since its successors need different colors. - if (CatchPadInst *CatchPad = dyn_cast<CatchPadInst>(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)) { - DEBUG_WITH_TYPE("winehprepare-coloring", - dbgs() << " Assigned color \'" << Visiting->getName() - << "\' to block \'" << NormalSucc->getName() - << "\'.\n"); - Worklist.push_back({NormalSucc, Visiting}); - } - BasicBlock *UnwindSucc = CatchPad->getUnwindDest(); - if (BlockColors[UnwindSucc].insert(Color)) { - DEBUG_WITH_TYPE("winehprepare-coloring", - dbgs() << " Assigned color \'" << Color->getName() - << "\' to block \'" << UnwindSucc->getName() - << "\'.\n"); - 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<TerminatePadInst>(VisitingHead)) - Color = Visiting; - } else { - // Note that this is a member of the given color. - FuncletBlocks[Color].insert(Visiting); - } - - TerminatorInst *Terminator = Visiting->getTerminator(); - if (isa<CleanupReturnInst>(Terminator) || - isa<CatchReturnInst>(Terminator) || - isa<CleanupEndPadInst>(Terminator)) { - // These blocks' successors have already been queued with the parent - // color. - continue; - } - for (BasicBlock *Succ : successors(Visiting)) { - if (isa<CatchEndPadInst>(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)) { - DEBUG_WITH_TYPE("winehprepare-coloring", - dbgs() << " Assigned color \'" << Color->getName() - << "\' to block \'" << Succ->getName() - << "\'.\n"); - Worklist.push_back({Succ, Color}); - } - } - } -} - -static BasicBlock *getEndPadForCatch(CatchPadInst *Catch) { - // The catch may have sibling catches. Follow the unwind chain until we get - // to the catchendpad. - BasicBlock *NextUnwindDest = Catch->getUnwindDest(); - auto *UnwindTerminator = NextUnwindDest->getTerminator(); - while (auto *NextCatch = dyn_cast<CatchPadInst>(UnwindTerminator)) { - NextUnwindDest = NextCatch->getUnwindDest(); - UnwindTerminator = NextUnwindDest->getTerminator(); - } - // The last catch in the chain must unwind to a catchendpad. - assert(isa<CatchEndPadInst>(UnwindTerminator)); - return NextUnwindDest; -} - -static void updateClonedEHPadUnwindToParent( - BasicBlock *UnwindDest, BasicBlock *OrigBlock, BasicBlock *CloneBlock, - std::vector<BasicBlock *> &OrigParents, BasicBlock *CloneParent) { - auto updateUnwindTerminator = [](BasicBlock *BB) { - auto *Terminator = BB->getTerminator(); - if (isa<CatchEndPadInst>(Terminator) || - isa<CleanupEndPadInst>(Terminator)) { - removeUnwindEdge(BB); - } else { - // If the block we're updating has a cleanupendpad or cleanupret - // terminator, we just want to replace that terminator with an - // unreachable instruction. - assert(isa<CleanupEndPadInst>(Terminator) || - isa<CleanupReturnInst>(Terminator)); - // Loop over all of the successors, removing the block's entry from any - // PHI nodes. - for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) - (*SI)->removePredecessor(BB); - // Remove the terminator and replace it with an unreachable instruction. - BB->getTerminator()->eraseFromParent(); - new UnreachableInst(BB->getContext(), BB); - } - }; - - assert(UnwindDest->isEHPad()); - // There are many places to which this EH terminator can unwind and each has - // slightly different rules for whether or not it fits with the given - // location. - auto *EHPadInst = UnwindDest->getFirstNonPHI(); - if (isa<CatchEndPadInst>(EHPadInst)) { - auto *CloneParentCatch = - dyn_cast<CatchPadInst>(CloneParent->getFirstNonPHI()); - if (!CloneParentCatch || - getEndPadForCatch(CloneParentCatch) != UnwindDest) { - DEBUG_WITH_TYPE( - "winehprepare-coloring", - dbgs() << " removing unwind destination of clone block \'" - << CloneBlock->getName() << "\'.\n"); - updateUnwindTerminator(CloneBlock); - } - // It's possible that the catch end pad is a legal match for both the clone - // and the original, so they must be checked separately. If the original - // funclet will still have multiple parents after the current clone parent - // is removed, we'll leave its unwind terminator until later. - assert(OrigParents.size() >= 2); - if (OrigParents.size() != 2) - return; - - // If the original funclet will have a single parent after the clone parent - // is removed, check that parent's unwind destination. - assert(OrigParents.front() == CloneParent || - OrigParents.back() == CloneParent); - BasicBlock *OrigParent; - if (OrigParents.front() == CloneParent) - OrigParent = OrigParents.back(); - else - OrigParent = OrigParents.front(); - - auto *OrigParentCatch = - dyn_cast<CatchPadInst>(OrigParent->getFirstNonPHI()); - if (!OrigParentCatch || getEndPadForCatch(OrigParentCatch) != UnwindDest) { - DEBUG_WITH_TYPE( - "winehprepare-coloring", - dbgs() << " removing unwind destination of original block \'" - << OrigBlock << "\'.\n"); - updateUnwindTerminator(OrigBlock); - } - } else if (auto *CleanupEnd = dyn_cast<CleanupEndPadInst>(EHPadInst)) { - // If the EH terminator unwinds to a cleanupendpad, that cleanupendpad - // must be ending a cleanuppad of either our clone parent or one - // one of the parents of the original funclet. - auto *CloneParentCP = - dyn_cast<CleanupPadInst>(CloneParent->getFirstNonPHI()); - auto *EndedCP = CleanupEnd->getCleanupPad(); - if (EndedCP == CloneParentCP) { - // If it is ending the cleanuppad of our cloned parent, then we - // want to remove the unwind destination of the EH terminator that - // we associated with the original funclet. - assert(isa<CatchEndPadInst>(OrigBlock->getFirstNonPHI())); - DEBUG_WITH_TYPE( - "winehprepare-coloring", - dbgs() << " removing unwind destination of original block \'" - << OrigBlock->getName() << "\'.\n"); - updateUnwindTerminator(OrigBlock); - } else { - // If it isn't ending the cleanuppad of our clone parent, then we - // want to remove the unwind destination of the EH terminator that - // associated with our cloned funclet. - assert(isa<CatchEndPadInst>(CloneBlock->getFirstNonPHI())); - DEBUG_WITH_TYPE( - "winehprepare-coloring", - dbgs() << " removing unwind destination of clone block \'" - << CloneBlock->getName() << "\'.\n"); - updateUnwindTerminator(CloneBlock); - } - } else { - // If the EH terminator unwinds to a catchpad, cleanuppad or - // terminatepad that EH pad must be a sibling of the funclet we're - // cloning. We'll clone it later and update one of the catchendpad - // instrunctions that unwinds to it at that time. - assert(isa<CatchPadInst>(EHPadInst) || isa<CleanupPadInst>(EHPadInst) || - isa<TerminatePadInst>(EHPadInst)); - } -} - -// If the terminator is a catchpad, we must also clone the catchendpad to which -// it unwinds and add this to the clone parent's block list. The catchendpad -// unwinds to either its caller, a sibling EH pad, a cleanup end pad in its -// parent funclet or a catch end pad in its grandparent funclet (which must be -// coupled with the parent funclet). If it has no unwind destination -// (i.e. unwind to caller), there is nothing to be done. If the unwind -// destination is a sibling EH pad, we will update the terminators later (in -// resolveFuncletAncestryForPath). If it unwinds to a cleanup end pad or a -// catch end pad and this end pad corresponds to the clone parent, we will -// remove the unwind destination in the original catchendpad. If it unwinds to -// a cleanup end pad or a catch end pad that does not correspond to the clone -// parent, we will remove the unwind destination in the cloned catchendpad. -static void updateCatchTerminators( - Function &F, CatchPadInst *OrigCatch, CatchPadInst *CloneCatch, - std::vector<BasicBlock *> &OrigParents, BasicBlock *CloneParent, - ValueToValueMapTy &VMap, - std::map<BasicBlock *, SetVector<BasicBlock *>> &BlockColors, - std::map<BasicBlock *, std::set<BasicBlock *>> &FuncletBlocks) { - // If we're cloning a catch pad that unwinds to a catchendpad, we also - // need to clone the catchendpad. The coloring algorithm associates - // the catchendpad block with the funclet's parent, so we have some work - // to do here to figure out whether the original belongs to the clone - // parent or one of the original funclets other parents (it might have - // more than one at this point). In either case, we might also need to - // remove the unwind edge if the catchendpad doesn't unwind to a block - // in the right grandparent funclet. - Instruction *I = CloneCatch->getUnwindDest()->getFirstNonPHI(); - if (auto *CEP = dyn_cast<CatchEndPadInst>(I)) { - assert(BlockColors[CEP->getParent()].size() == 1); - BasicBlock *CEPFunclet = *(BlockColors[CEP->getParent()].begin()); - BasicBlock *CEPCloneParent = nullptr; - CatchPadInst *PredCatch = nullptr; - if (CEPFunclet == CloneParent) { - // The catchendpad is in the clone parent, so we need to clone it - // and associate the clone with the original funclet's parent. If - // the original funclet had multiple parents, we'll add it to the - // first parent that isn't the clone parent. The logic in - // updateClonedEHPadUnwindToParent() will only remove the unwind edge - // if there is only one parent other than the clone parent, so we don't - // need to verify the ancestry. The catchendpad will eventually be - // cloned into the correct parent and all invalid unwind edges will be - // removed. - for (auto *Parent : OrigParents) { - if (Parent != CloneParent) { - CEPCloneParent = Parent; - break; - } - } - PredCatch = OrigCatch; - } else { - CEPCloneParent = CloneParent; - PredCatch = CloneCatch; - } - assert(CEPCloneParent && PredCatch); - DEBUG_WITH_TYPE("winehprepare-coloring", - dbgs() << " Cloning catchendpad \'" - << CEP->getParent()->getName() << "\' for funclet \'" - << CEPCloneParent->getName() << "\'.\n"); - BasicBlock *ClonedCEP = CloneBasicBlock( - CEP->getParent(), VMap, Twine(".from.", CEPCloneParent->getName())); - // Insert the clone immediately after the original to ensure determinism - // and to keep the same relative ordering of any funclet's blocks. - ClonedCEP->insertInto(&F, CEP->getParent()->getNextNode()); - PredCatch->setUnwindDest(ClonedCEP); - FuncletBlocks[CEPCloneParent].insert(ClonedCEP); - BlockColors[ClonedCEP].insert(CEPCloneParent); - DEBUG_WITH_TYPE("winehprepare-coloring", - dbgs() << " Assigning color \'" - << CEPCloneParent->getName() << "\' to block \'" - << ClonedCEP->getName() << "\'.\n"); - auto *ClonedCEPInst = cast<CatchEndPadInst>(ClonedCEP->getTerminator()); - if (auto *Dest = ClonedCEPInst->getUnwindDest()) - updateClonedEHPadUnwindToParent(Dest, OrigCatch->getUnwindDest(), - CloneCatch->getUnwindDest(), OrigParents, - CloneParent); - } -} - -// While we are cloning a funclet because it has multiple parents, we will call -// this routine to update the terminators for the original and cloned copies -// of each basic block. All blocks in the funclet have been clone by this time. -// OrigBlock and CloneBlock will be identical except for their block label. -// -// If the terminator is a catchpad, we must also clone the catchendpad to which -// it unwinds and in most cases update either the original catchendpad or the -// clone. See the updateCatchTerminators() helper routine for details. -// -// If the terminator is a catchret its successor is a block in its parent -// funclet. If the instruction returns to a block in the parent for which the -// cloned funclet was created, the terminator in the original block must be -// replaced by an unreachable instruction. Otherwise the terminator in the -// clone block must be replaced by an unreachable instruction. -// -// If the terminator is a cleanupret or cleanupendpad it either unwinds to -// caller or unwinds to a sibling EH pad, a cleanup end pad in its parent -// funclet or a catch end pad in its grandparent funclet (which must be -// coupled with the parent funclet). If it unwinds to caller there is -// nothing to be done. If the unwind destination is a sibling EH pad, we will -// update the terminators later (in resolveFuncletAncestryForPath). If it -// unwinds to a cleanup end pad or a catch end pad and this end pad corresponds -// to the clone parent, we will replace the terminator in the original block -// with an unreachable instruction. If it unwinds to a cleanup end pad or a -// catch end pad that does not correspond to the clone parent, we will replace -// the terminator in the clone block with an unreachable instruction. -// -// If the terminator is an invoke instruction, we will handle it after all -// siblings of the current funclet have been cloned. -void WinEHPrepare::updateTerminatorsAfterFuncletClone( - Function &F, BasicBlock *OrigFunclet, BasicBlock *CloneFunclet, - BasicBlock *OrigBlock, BasicBlock *CloneBlock, BasicBlock *CloneParent, - ValueToValueMapTy &VMap, std::map<BasicBlock *, BasicBlock *> &Orig2Clone) { - // If the cloned block doesn't have an exceptional terminator, there is - // nothing to be done here. - TerminatorInst *CloneTerminator = CloneBlock->getTerminator(); - if (!CloneTerminator->isExceptional()) - return; - - if (auto *CloneCatch = dyn_cast<CatchPadInst>(CloneTerminator)) { - // A cloned catch pad has a lot of wrinkles, so we'll call a helper function - // to update this case. - auto *OrigCatch = cast<CatchPadInst>(OrigBlock->getTerminator()); - updateCatchTerminators(F, OrigCatch, CloneCatch, - FuncletParents[OrigFunclet], CloneParent, VMap, - BlockColors, FuncletBlocks); - } else if (auto *CRI = dyn_cast<CatchReturnInst>(CloneTerminator)) { - if (FuncletBlocks[CloneParent].count(CRI->getSuccessor())) { - BasicBlock *OrigParent; - // The original funclet may have more than two parents, but that's OK. - // We just need to remap the original catchret to any of the parents. - // All of the parents should have an entry in the EstrangedBlocks map - // if any of them do. - if (FuncletParents[OrigFunclet].front() == CloneParent) - OrigParent = FuncletParents[OrigFunclet].back(); - else - OrigParent = FuncletParents[OrigFunclet].front(); - for (succ_iterator SI = succ_begin(OrigBlock), SE = succ_end(OrigBlock); - SI != SE; ++SI) - (*SI)->removePredecessor(OrigBlock); - BasicBlock *LostBlock = EstrangedBlocks[OrigParent][CRI->getSuccessor()]; - auto *OrigCatchRet = cast<CatchReturnInst>(OrigBlock->getTerminator()); - if (LostBlock) { - OrigCatchRet->setSuccessor(LostBlock); - } else { - OrigCatchRet->eraseFromParent(); - new UnreachableInst(OrigBlock->getContext(), OrigBlock); - } - } else { - for (succ_iterator SI = succ_begin(CloneBlock), SE = succ_end(CloneBlock); - SI != SE; ++SI) - (*SI)->removePredecessor(CloneBlock); - BasicBlock *LostBlock = EstrangedBlocks[CloneParent][CRI->getSuccessor()]; - if (LostBlock) { - CRI->setSuccessor(LostBlock); - } else { - CRI->eraseFromParent(); - new UnreachableInst(CloneBlock->getContext(), CloneBlock); - } - } - } else if (isa<CleanupReturnInst>(CloneTerminator) || - isa<CleanupEndPadInst>(CloneTerminator)) { - BasicBlock *UnwindDest = nullptr; - - // A cleanup pad can unwind through either a cleanupret or a cleanupendpad - // but both are handled the same way. - if (auto *CRI = dyn_cast<CleanupReturnInst>(CloneTerminator)) - UnwindDest = CRI->getUnwindDest(); - else if (auto *CEI = dyn_cast<CleanupEndPadInst>(CloneTerminator)) - UnwindDest = CEI->getUnwindDest(); - - // If the instruction has no local unwind destination, there is nothing - // to be done. - if (!UnwindDest) - return; - - // The unwind destination may be a sibling EH pad, a catchendpad in - // a grandparent funclet (ending a catchpad in the parent) or a cleanup - // cleanupendpad in the parent. Call a helper routine to diagnose this - // and remove either the clone or original terminator as needed. - updateClonedEHPadUnwindToParent(UnwindDest, OrigBlock, CloneBlock, - FuncletParents[OrigFunclet], CloneParent); - } -} - -// Clones all blocks used by the specified funclet to avoid the funclet having -// multiple parent funclets. All terminators in the parent that unwind to the -// original funclet are remapped to unwind to the clone. Any terminator in the -// original funclet which returned to this parent is converted to an unreachable -// instruction. Likewise, any terminator in the cloned funclet which returns to -// a parent funclet other than the specified parent is converted to an -// unreachable instruction. -BasicBlock *WinEHPrepare::cloneFuncletForParent(Function &F, - BasicBlock *FuncletEntry, - BasicBlock *Parent) { - std::set<BasicBlock *> &BlocksInFunclet = FuncletBlocks[FuncletEntry]; - - DEBUG_WITH_TYPE("winehprepare-coloring", - dbgs() << "Cloning funclet \'" << FuncletEntry->getName() - << "\' for parent \'" << Parent->getName() << "\'.\n"); - - std::map<BasicBlock *, BasicBlock *> Orig2Clone; - ValueToValueMapTy VMap; - for (BasicBlock *BB : BlocksInFunclet) { - // Create a new basic block and copy instructions into it. - BasicBlock *CBB = - CloneBasicBlock(BB, VMap, Twine(".from.", Parent->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; - } // end for (BasicBlock *BB : BlocksInFunclet) - - BasicBlock *ClonedFunclet = Orig2Clone[FuncletEntry]; - assert(ClonedFunclet); - - // Set the coloring for the blocks we just cloned. - std::set<BasicBlock *> &ClonedBlocks = FuncletBlocks[ClonedFunclet]; - for (auto &BBMapping : Orig2Clone) { - BasicBlock *NewBlock = BBMapping.second; - ClonedBlocks.insert(NewBlock); - BlockColors[NewBlock].insert(ClonedFunclet); - - DEBUG_WITH_TYPE("winehprepare-coloring", - dbgs() << " Assigning color \'" << ClonedFunclet->getName() - << "\' to block \'" << NewBlock->getName() - << "\'.\n"); - - // Use the VMap to remap the instructions in this cloned block. - for (Instruction &I : *NewBlock) - RemapInstruction(&I, VMap, RF_IgnoreMissingEntries); - } - - // All the cloned blocks have to be colored in the loop above before we can - // update the terminators because doing so can require checking the color of - // other blocks in the cloned funclet. - for (auto &BBMapping : Orig2Clone) { - BasicBlock *OldBlock = BBMapping.first; - BasicBlock *NewBlock = BBMapping.second; - - // Update the terminator, if necessary, in both the original block and the - // cloned so that the original funclet never returns to a block in the - // clone parent and the clone funclet never returns to a block in any other - // of the original funclet's parents. - updateTerminatorsAfterFuncletClone(F, FuncletEntry, ClonedFunclet, OldBlock, - NewBlock, Parent, VMap, Orig2Clone); - - // Check to see if the cloned block successor has PHI nodes. If so, we need - // to add entries to the PHI nodes for the cloned block now. - for (BasicBlock *SuccBB : successors(NewBlock)) { - for (Instruction &SuccI : *SuccBB) { - auto *SuccPN = dyn_cast<PHINode>(&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<Instruction>(IV)) { - ValueToValueMapTy::iterator I = VMap.find(Inst); - if (I != VMap.end()) - IV = I->second; - } +void WinEHPrepare::colorFunclets(Function &F) { + BlockColors = colorEHFunclets(F); - SuccPN->addIncoming(IV, NewBlock); - } - } - } - - // Erase the clone's parent from the original funclet's parent list. - std::vector<BasicBlock *> &Parents = FuncletParents[FuncletEntry]; - Parents.erase(std::remove(Parents.begin(), Parents.end(), Parent), - Parents.end()); - - // Store the cloned funclet's parent. - assert(std::find(FuncletParents[ClonedFunclet].begin(), - FuncletParents[ClonedFunclet].end(), - Parent) == std::end(FuncletParents[ClonedFunclet])); - FuncletParents[ClonedFunclet].push_back(Parent); - - // Copy any children of the original funclet to the clone. We'll either - // clone them too or make that path unreachable when we take the next step - // in resolveFuncletAncestryForPath(). - for (auto *Child : FuncletChildren[FuncletEntry]) { - assert(std::find(FuncletChildren[ClonedFunclet].begin(), - FuncletChildren[ClonedFunclet].end(), - Child) == std::end(FuncletChildren[ClonedFunclet])); - FuncletChildren[ClonedFunclet].push_back(Child); - assert(std::find(FuncletParents[Child].begin(), FuncletParents[Child].end(), - ClonedFunclet) == std::end(FuncletParents[Child])); - FuncletParents[Child].push_back(ClonedFunclet); - } - - // Find any blocks that unwound to the original funclet entry from the - // clone parent block and remap them to the clone. - for (auto *U : FuncletEntry->users()) { - auto *UT = dyn_cast<TerminatorInst>(U); - if (!UT) - continue; - BasicBlock *UBB = UT->getParent(); - assert(BlockColors[UBB].size() == 1); - BasicBlock *UFunclet = *(BlockColors[UBB].begin()); - // Funclets shouldn't be able to loop back on themselves. - assert(UFunclet != FuncletEntry); - // If this instruction unwinds to the original funclet from the clone - // parent, remap the terminator so that it unwinds to the clone instead. - // We will perform a similar transformation for siblings after all - // the siblings have been cloned. - if (UFunclet == Parent) { - // We're about to break the path from this block to the uncloned funclet - // entry, so remove it as a predeccessor to clean up the PHIs. - FuncletEntry->removePredecessor(UBB); - TerminatorInst *Terminator = UBB->getTerminator(); - RemapInstruction(Terminator, VMap, RF_IgnoreMissingEntries); - } - } - - // This asserts a condition that is relied upon inside the loop below, - // namely that no predecessors of the original funclet entry block - // are also predecessors of the cloned funclet entry block. - assert(std::all_of(pred_begin(FuncletEntry), pred_end(FuncletEntry), - [&ClonedFunclet](BasicBlock *Pred) { - return std::find(pred_begin(ClonedFunclet), - pred_end(ClonedFunclet), - Pred) == pred_end(ClonedFunclet); - })); - - // Remove any invalid PHI node entries in the cloned funclet.cl - std::vector<PHINode *> PHIsToErase; - for (Instruction &I : *ClonedFunclet) { - auto *PN = dyn_cast<PHINode>(&I); - if (!PN) - break; - - // Predecessors of the original funclet do not reach the cloned funclet, - // but the cloning process assumes they will. Remove them now. - for (auto *Pred : predecessors(FuncletEntry)) - PN->removeIncomingValue(Pred, false); - } - for (auto *PN : PHIsToErase) - PN->eraseFromParent(); - - // Replace the original funclet in the parent's children vector with the - // cloned funclet. - for (auto &It : FuncletChildren[Parent]) { - if (It == FuncletEntry) { - It = ClonedFunclet; - break; - } - } - - return ClonedFunclet; -} - -// Removes the unwind edge for any exceptional terminators within the specified -// parent funclet that previously unwound to the specified child funclet. -void WinEHPrepare::makeFuncletEdgeUnreachable(BasicBlock *Parent, - BasicBlock *Child) { - for (BasicBlock *BB : FuncletBlocks[Parent]) { - TerminatorInst *Terminator = BB->getTerminator(); - if (!Terminator->isExceptional()) - continue; - - // Look for terninators that unwind to the child funclet. - BasicBlock *UnwindDest = nullptr; - if (auto *I = dyn_cast<InvokeInst>(Terminator)) - UnwindDest = I->getUnwindDest(); - else if (auto *I = dyn_cast<CatchEndPadInst>(Terminator)) - UnwindDest = I->getUnwindDest(); - else if (auto *I = dyn_cast<TerminatePadInst>(Terminator)) - UnwindDest = I->getUnwindDest(); - // cleanupendpad, catchret and cleanupret don't represent a parent-to-child - // funclet transition, so we don't need to consider them here. - - // If the child funclet is the unwind destination, replace the terminator - // with an unreachable instruction. - if (UnwindDest == Child) - removeUnwindEdge(BB); - } - // The specified parent is no longer a parent of the specified child. - std::vector<BasicBlock *> &Children = FuncletChildren[Parent]; - Children.erase(std::remove(Children.begin(), Children.end(), Child), - Children.end()); -} - -// This routine is called after funclets with multiple parents are cloned for -// a specific parent. Here we look for children of the specified funclet that -// unwind to other children of that funclet and update the unwind destinations -// to ensure that each sibling is connected to the correct clone of the sibling -// to which it unwinds. -// -// If the terminator is an invoke instruction, it unwinds either to a child -// EH pad, a cleanup end pad in the current funclet, or a catch end pad in a -// parent funclet (which ends either the current catch pad or a sibling -// catch pad). If it unwinds to a child EH pad, the child will have multiple -// parents after this funclet is cloned and this case will be handled later in -// the resolveFuncletAncestryForPath processing. If it unwinds to a -// cleanup end pad in the current funclet, the instruction remapping during -// the cloning process should have already mapped the unwind destination to -// the cloned copy of the cleanup end pad. If it unwinds to a catch end pad -// there are two possibilities: either the catch end pad is the unwind -// destination for the catch pad we are currently cloning or it is the unwind -// destination for a sibling catch pad. If it it the unwind destination of the -// catch pad we are cloning, we need to update the cloned invoke instruction -// to unwind to the cloned catch end pad. Otherwise, we will handle this -// later (in resolveFuncletAncestryForPath). -static void updateSiblingToSiblingUnwind( - BasicBlock *CurFunclet, - std::map<BasicBlock *, SetVector<BasicBlock *>> &BlockColors, - std::map<BasicBlock *, std::set<BasicBlock *>> &FuncletBlocks, - std::map<BasicBlock *, std::vector<BasicBlock *>> &FuncletParents, - std::map<BasicBlock *, std::vector<BasicBlock *>> &FuncletChildren, - std::map<BasicBlock *, BasicBlock *> &Funclet2Orig) { - // Remap any bad sibling-to-sibling transitions for funclets that - // we just cloned. - for (BasicBlock *ChildFunclet : FuncletChildren[CurFunclet]) { - for (auto *BB : FuncletBlocks[ChildFunclet]) { - TerminatorInst *Terminator = BB->getTerminator(); - if (!Terminator->isExceptional()) - continue; - - // See if this terminator has an unwind destination. - // Note that catchendpads are handled when the associated catchpad - // is cloned. They don't fit the pattern we're looking for here. - BasicBlock *UnwindDest = nullptr; - if (auto *I = dyn_cast<CatchPadInst>(Terminator)) { - UnwindDest = I->getUnwindDest(); - // The catchendpad is not a sibling destination. This case should - // have been handled in cloneFuncletForParent(). - if (isa<CatchEndPadInst>(Terminator)) { - assert(BlockColors[UnwindDest].size() == 1 && - "Cloned catchpad unwinds to an pad with multiple parents."); - assert(FuncletParents[UnwindDest].front() == CurFunclet && - "Cloned catchpad unwinds to the wrong parent."); - continue; - } - } else { - if (auto *I = dyn_cast<CleanupReturnInst>(Terminator)) - UnwindDest = I->getUnwindDest(); - else if (auto *I = dyn_cast<CleanupEndPadInst>(Terminator)) - UnwindDest = I->getUnwindDest(); - - // If the cleanup unwinds to caller, there is nothing to be done. - if (!UnwindDest) - continue; - } - - // If the destination is not a cleanup pad, catch pad or terminate pad - // we don't need to handle it here. - Instruction *EHPad = UnwindDest->getFirstNonPHI(); - if (!isa<CleanupPadInst>(EHPad) && !isa<CatchPadInst>(EHPad) && - !isa<TerminatePadInst>(EHPad)) - continue; - - // If it is one of these, then it is either a sibling of the current - // child funclet or a clone of one of those siblings. - // If it is a sibling, no action is needed. - if (FuncletParents[UnwindDest].size() == 1 && - FuncletParents[UnwindDest].front() == CurFunclet) - continue; - - // If the unwind destination is a clone of a sibling, we need to figure - // out which sibling it is a clone of and use that sibling as the - // unwind destination. - BasicBlock *DestOrig = Funclet2Orig[UnwindDest]; - BasicBlock *TargetSibling = nullptr; - for (auto &Mapping : Funclet2Orig) { - if (Mapping.second != DestOrig) - continue; - BasicBlock *MappedFunclet = Mapping.first; - if (FuncletParents[MappedFunclet].size() == 1 && - FuncletParents[MappedFunclet].front() == CurFunclet) { - TargetSibling = MappedFunclet; - } - } - // If we didn't find the sibling we were looking for then the - // unwind destination is not a clone of one of child's siblings. - // That's unexpected. - assert(TargetSibling && "Funclet unwinds to unexpected destination."); - - // Update the terminator instruction to unwind to the correct sibling. - if (auto *I = dyn_cast<CatchPadInst>(Terminator)) - I->setUnwindDest(TargetSibling); - else if (auto *I = dyn_cast<CleanupReturnInst>(Terminator)) - I->setUnwindDest(TargetSibling); - else if (auto *I = dyn_cast<CleanupEndPadInst>(Terminator)) - I->setUnwindDest(TargetSibling); - } - } - - // Invoke remapping can't be done correctly until after all of their - // other sibling-to-sibling unwinds have been remapped. - for (BasicBlock *ChildFunclet : FuncletChildren[CurFunclet]) { - bool NeedOrigInvokeRemapping = false; - for (auto *BB : FuncletBlocks[ChildFunclet]) { - TerminatorInst *Terminator = BB->getTerminator(); - auto *II = dyn_cast<InvokeInst>(Terminator); - if (!II) - continue; - - BasicBlock *UnwindDest = II->getUnwindDest(); - assert(UnwindDest && "Invoke unwinds to a null destination."); - assert(UnwindDest->isEHPad() && "Invoke does not unwind to an EH pad."); - auto *EHPadInst = UnwindDest->getFirstNonPHI(); - if (isa<CleanupEndPadInst>(EHPadInst)) { - // An invoke that unwinds to a cleanup end pad must be in a cleanup pad. - assert(isa<CleanupPadInst>(ChildFunclet->getFirstNonPHI()) && - "Unwinding to cleanup end pad from a non cleanup pad funclet."); - // The funclet cloning should have remapped the destination to the cloned - // cleanup end pad. - assert(FuncletBlocks[ChildFunclet].count(UnwindDest) && - "Unwind destination for invoke was not updated during cloning."); - } else if (isa<CatchEndPadInst>(EHPadInst)) { - // If the invoke unwind destination is the unwind destination for - // the current child catch pad funclet, there is nothing to be done. - BasicBlock *OrigFunclet = Funclet2Orig[ChildFunclet]; - auto *CurCatch = cast<CatchPadInst>(ChildFunclet->getFirstNonPHI()); - auto *OrigCatch = cast<CatchPadInst>(OrigFunclet->getFirstNonPHI()); - if (OrigCatch->getUnwindDest() == UnwindDest) { - // If the invoke unwinds to a catch end pad that is the unwind - // destination for the original catch pad, the cloned invoke should - // unwind to the cloned catch end pad. - II->setUnwindDest(CurCatch->getUnwindDest()); - } else if (CurCatch->getUnwindDest() == UnwindDest) { - // If the invoke unwinds to a catch end pad that is the unwind - // destination for the clone catch pad, the original invoke should - // unwind to the unwind destination of the original catch pad. - // This happens when the catch end pad is matched to the clone - // parent when the catchpad instruction is cloned and the original - // invoke instruction unwinds to the original catch end pad (which - // is now the unwind destination of the cloned catch pad). - NeedOrigInvokeRemapping = true; - } else { - // Otherwise, the invoke unwinds to a catch end pad that is the unwind - // destination another catch pad in the unwind chain from either the - // current catch pad or one of its clones. If it is already the - // catch end pad at the end unwind chain from the current catch pad, - // we'll need to check the invoke instructions in the original funclet - // later. Otherwise, we need to remap this invoke now. - assert((getEndPadForCatch(OrigCatch) == UnwindDest || - getEndPadForCatch(CurCatch) == UnwindDest) && - "Invoke within catch pad unwinds to an invalid catch end pad."); - BasicBlock *CurCatchEnd = getEndPadForCatch(CurCatch); - if (CurCatchEnd == UnwindDest) - NeedOrigInvokeRemapping = true; - else - II->setUnwindDest(CurCatchEnd); - } - } - } - if (NeedOrigInvokeRemapping) { - // To properly remap invoke instructions that unwind to catch end pads - // that are not the unwind destination of the catch pad funclet in which - // the invoke appears, we must also look at the uncloned invoke in the - // original funclet. If we saw an invoke that was already properly - // unwinding to a sibling's catch end pad, we need to check the invokes - // in the original funclet. - BasicBlock *OrigFunclet = Funclet2Orig[ChildFunclet]; - for (auto *BB : FuncletBlocks[OrigFunclet]) { - auto *II = dyn_cast<InvokeInst>(BB->getTerminator()); - if (!II) - continue; - - BasicBlock *UnwindDest = II->getUnwindDest(); - assert(UnwindDest && "Invoke unwinds to a null destination."); - assert(UnwindDest->isEHPad() && "Invoke does not unwind to an EH pad."); - auto *CEP = dyn_cast<CatchEndPadInst>(UnwindDest->getFirstNonPHI()); - if (!CEP) - continue; - - // If the invoke unwind destination is the unwind destination for - // the original catch pad funclet, there is nothing to be done. - auto *OrigCatch = cast<CatchPadInst>(OrigFunclet->getFirstNonPHI()); - - // If the invoke unwinds to a catch end pad that is neither the unwind - // destination of OrigCatch or the destination another catch pad in the - // unwind chain from current catch pad, we need to remap the invoke. - BasicBlock *OrigCatchEnd = getEndPadForCatch(OrigCatch); - if (OrigCatchEnd != UnwindDest) - II->setUnwindDest(OrigCatchEnd); - } - } - } -} - -void WinEHPrepare::resolveFuncletAncestry( - Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks) { - // Most of the time this will be unnecessary. If the conditions arise that - // require this work, this flag will be set. - if (!FuncletCloningRequired) - return; - - // Funclet2Orig is used to map any cloned funclets back to the original - // funclet from which they were cloned. The map is seeded with the - // original funclets mapping to themselves. - std::map<BasicBlock *, BasicBlock *> Funclet2Orig; - for (auto *Funclet : EntryBlocks) - Funclet2Orig[Funclet] = Funclet; - - // Start with the entry funclet and walk the funclet parent-child tree. - SmallVector<BasicBlock *, 4> FuncletPath; - FuncletPath.push_back(&(F.getEntryBlock())); - resolveFuncletAncestryForPath(F, FuncletPath, Funclet2Orig); -} - -// Walks the funclet control flow, cloning any funclets that have more than one -// parent funclet and breaking any cyclic unwind chains so that the path becomes -// unreachable at the point where a funclet would have unwound to a funclet that -// was already in the chain. -void WinEHPrepare::resolveFuncletAncestryForPath( - Function &F, SmallVectorImpl<BasicBlock *> &FuncletPath, - std::map<BasicBlock *, BasicBlock *> &Funclet2Orig) { - bool ClonedAnyChildren = false; - BasicBlock *CurFunclet = FuncletPath.back(); - // Copy the children vector because we might changing it. - std::vector<BasicBlock *> Children(FuncletChildren[CurFunclet]); - for (BasicBlock *ChildFunclet : Children) { - // Don't allow the funclet chain to unwind back on itself. - // If this funclet is already in the current funclet chain, make the - // path to it through the current funclet unreachable. - bool IsCyclic = false; - BasicBlock *ChildIdentity = Funclet2Orig[ChildFunclet]; - for (BasicBlock *Ancestor : FuncletPath) { - BasicBlock *AncestorIdentity = Funclet2Orig[Ancestor]; - if (AncestorIdentity == ChildIdentity) { - IsCyclic = true; - break; - } - } - // If the unwind chain wraps back on itself, break the chain. - if (IsCyclic) { - makeFuncletEdgeUnreachable(CurFunclet, ChildFunclet); - continue; - } - // If this child funclet has other parents, clone the entire funclet. - if (FuncletParents[ChildFunclet].size() > 1) { - ChildFunclet = cloneFuncletForParent(F, ChildFunclet, CurFunclet); - Funclet2Orig[ChildFunclet] = ChildIdentity; - ClonedAnyChildren = true; - } - FuncletPath.push_back(ChildFunclet); - resolveFuncletAncestryForPath(F, FuncletPath, Funclet2Orig); - FuncletPath.pop_back(); - } - // If we didn't clone any children, we can return now. - if (!ClonedAnyChildren) - return; - - updateSiblingToSiblingUnwind(CurFunclet, BlockColors, FuncletBlocks, - FuncletParents, FuncletChildren, Funclet2Orig); -} - -void WinEHPrepare::colorFunclets(Function &F, - SmallVectorImpl<BasicBlock *> &EntryBlocks) { - ::colorFunclets(F, EntryBlocks, BlockColors, FuncletBlocks); - - // 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) { - SetVector<BasicBlock *> &ColorMapItem = BlockColors[FuncletEntry]; - // It will be rare for funclets to have multiple parents, but if any - // do we need to clone the funclet later to address that. Here we - // set a flag indicating that this case has arisen so that we don't - // have to do a lot of checking later to handle the more common case. - if (ColorMapItem.size() > 1) - FuncletCloningRequired = true; - for (BasicBlock *Parent : ColorMapItem) { - assert(std::find(FuncletChildren[Parent].begin(), - FuncletChildren[Parent].end(), - FuncletEntry) == std::end(FuncletChildren[Parent])); - FuncletChildren[Parent].push_back(FuncletEntry); - assert(std::find(FuncletParents[FuncletEntry].begin(), - FuncletParents[FuncletEntry].end(), - Parent) == std::end(FuncletParents[FuncletEntry])); - FuncletParents[FuncletEntry].push_back(Parent); - } - ColorMapItem.clear(); - ColorMapItem.insert(FuncletEntry); + // Invert the map from BB to colors to color to BBs. + for (BasicBlock &BB : F) { + ColorVector &Colors = BlockColors[&BB]; + for (BasicBlock *Color : Colors) + FuncletBlocks[Color].push_back(&BB); } } void llvm::calculateCatchReturnSuccessorColors(const Function *Fn, WinEHFuncInfo &FuncInfo) { - SmallVector<BasicBlock *, 4> EntryBlocks; - // colorFunclets needs the set of EntryBlocks, get them using - // findFuncletEntryPoints. - findFuncletEntryPoints(const_cast<Function &>(*Fn), EntryBlocks); - - std::map<BasicBlock *, SetVector<BasicBlock *>> BlockColors; - std::map<BasicBlock *, std::set<BasicBlock *>> FuncletBlocks; - // Figure out which basic blocks belong to which funclets. - colorFunclets(const_cast<Function &>(*Fn), EntryBlocks, BlockColors, - FuncletBlocks); - - // The static colorFunclets routine assigns multiple colors to funclet entries - // because that information is needed to calculate funclets' parent-child - // relationship, but we don't need those relationship here and ultimately the - // entry blocks should have the color of the funclet they begin. - for (BasicBlock *FuncletEntry : EntryBlocks) { - BlockColors[FuncletEntry].clear(); - BlockColors[FuncletEntry].insert(FuncletEntry); - } - - // 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<CatchPadInst>(FirstNonPHI); - if (!CatchPad) + for (const BasicBlock &BB : *Fn) { + const auto *CatchRet = dyn_cast<CatchReturnInst>(BB.getTerminator()); + if (!CatchRet) continue; - - // The users of a catchpad are always catchrets. - for (User *Exit : CatchPad->users()) { - auto *CatchReturn = dyn_cast<CatchReturnInst>(Exit); - if (!CatchReturn) - continue; - BasicBlock *CatchRetSuccessor = CatchReturn->getSuccessor(); - SetVector<BasicBlock *> &SuccessorColors = BlockColors[CatchRetSuccessor]; - assert(SuccessorColors.size() == 1 && "Expected BB to be monochrome!"); - BasicBlock *Color = *SuccessorColors.begin(); - // Record the catchret successor's funclet membership. - FuncInfo.CatchRetSuccessorColorMap[CatchReturn] = Color; - } + // A 'catchret' returns to the outer scope's color. + Value *ParentPad = CatchRet->getParentPad(); + const BasicBlock *Color; + if (isa<ConstantTokenNone>(ParentPad)) + Color = &Fn->getEntryBlock(); + else + Color = cast<Instruction>(ParentPad)->getParent(); + // Record the catchret successor's funclet membership. + FuncInfo.CatchRetSuccessorColorMap[CatchRet] = Color; } } @@ -1584,70 +620,23 @@ void WinEHPrepare::demotePHIsOnFunclets(Function &F) { } } -void WinEHPrepare::cloneCommonBlocks( - Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks) { +void WinEHPrepare::cloneCommonBlocks(Function &F) { // 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<BasicBlock *> &BlocksInFunclet = FuncletBlocks[FuncletPadBB]; + for (auto &Funclets : FuncletBlocks) { + BasicBlock *FuncletPadBB = Funclets.first; + std::vector<BasicBlock *> &BlocksInFunclet = Funclets.second; - std::map<BasicBlock *, BasicBlock *> Orig2Clone; + std::vector<std::pair<BasicBlock *, BasicBlock *>> Orig2Clone; ValueToValueMapTy VMap; - for (auto BlockIt = BlocksInFunclet.begin(), - BlockEnd = BlocksInFunclet.end(); - BlockIt != BlockEnd;) { - // Increment the iterator inside the loop because we might be removing - // blocks from the set. - BasicBlock *BB = *BlockIt++; - SetVector<BasicBlock *> &ColorsForBB = BlockColors[BB]; + for (BasicBlock *BB : BlocksInFunclet) { + ColorVector &ColorsForBB = BlockColors[BB]; // We don't need to do anything if the block is monochromatic. size_t NumColorsForBB = ColorsForBB.size(); if (NumColorsForBB == 1) continue; - // If this block is a catchendpad, it shouldn't be cloned. - // We will only see a catchendpad with multiple colors in the case where - // some funclet has multiple parents. In that case, the color will be - // resolved during the resolveFuncletAncestry processing. - // For now, find the catchpad that unwinds to this block and assign - // that catchpad's first parent to be the color for this block. - if (isa<CatchEndPadInst>(BB->getFirstNonPHI())) { - assert( - FuncletCloningRequired && - "Found multi-colored catchendpad with no multi-parent funclets."); - BasicBlock *CatchParent = nullptr; - // There can only be one catchpad predecessor for a catchendpad. - for (BasicBlock *PredBB : predecessors(BB)) { - if (isa<CatchPadInst>(PredBB->getTerminator())) { - CatchParent = PredBB; - break; - } - } - // There must be one catchpad predecessor for a catchendpad. - assert(CatchParent && "No catchpad found for catchendpad."); - - // If the catchpad has multiple parents, we'll clone the catchendpad - // when we clone the catchpad funclet and insert it into the correct - // funclet. For now, we just select the first parent of the catchpad - // and give the catchendpad that color. - BasicBlock *CorrectColor = FuncletParents[CatchParent].front(); - assert(FuncletBlocks[CorrectColor].count(BB)); - assert(BlockColors[BB].count(CorrectColor)); - - // Remove this block from the FuncletBlocks set of any funclet that - // isn't the funclet whose color we just selected. - for (BasicBlock *ContainingFunclet : BlockColors[BB]) - if (ContainingFunclet != CorrectColor) - FuncletBlocks[ContainingFunclet].erase(BB); - BlockColors[BB].remove_if([&](BasicBlock *ContainingFunclet) { - return ContainingFunclet != CorrectColor; - }); - // This should leave just one color for BB. - assert(BlockColors[BB].size() == 1); - continue; - } - DEBUG_WITH_TYPE("winehprepare-coloring", dbgs() << " Cloning block \'" << BB->getName() << "\' for funclet \'" << FuncletPadBB->getName() @@ -1664,7 +653,7 @@ void WinEHPrepare::cloneCommonBlocks( VMap[BB] = CBB; // Record delta operations that we need to perform to our color mappings. - Orig2Clone[BB] = CBB; + Orig2Clone.emplace_back(BB, CBB); } // If nothing was cloned, we're done cloning in this funclet. @@ -1677,55 +666,28 @@ void WinEHPrepare::cloneCommonBlocks( BasicBlock *OldBlock = BBMapping.first; BasicBlock *NewBlock = BBMapping.second; - BlocksInFunclet.insert(NewBlock); - BlockColors[NewBlock].insert(FuncletPadBB); + BlocksInFunclet.push_back(NewBlock); + ColorVector &NewColors = BlockColors[NewBlock]; + assert(NewColors.empty() && "A new block should only have one color!"); + NewColors.push_back(FuncletPadBB); DEBUG_WITH_TYPE("winehprepare-coloring", dbgs() << " Assigned color \'" << FuncletPadBB->getName() << "\' to block \'" << NewBlock->getName() << "\'.\n"); - BlocksInFunclet.erase(OldBlock); - BlockColors[OldBlock].remove(FuncletPadBB); + BlocksInFunclet.erase( + std::remove(BlocksInFunclet.begin(), BlocksInFunclet.end(), OldBlock), + BlocksInFunclet.end()); + ColorVector &OldColors = BlockColors[OldBlock]; + OldColors.erase( + std::remove(OldColors.begin(), OldColors.end(), FuncletPadBB), + OldColors.end()); DEBUG_WITH_TYPE("winehprepare-coloring", dbgs() << " Removed color \'" << FuncletPadBB->getName() << "\' from block \'" << OldBlock->getName() << "\'.\n"); - - // If we are cloning a funclet that might share a child funclet with - // another funclet, look to see if the cloned block is reached from a - // catchret instruction. If so, save this association so we can retrieve - // the possibly orphaned clone when we clone the child funclet. - if (FuncletCloningRequired) { - for (auto *Pred : predecessors(OldBlock)) { - auto *Terminator = Pred->getTerminator(); - if (!isa<CatchReturnInst>(Terminator)) - continue; - // If this block is reached from a catchret instruction in a funclet - // that has multiple parents, it will have a color for each of those - // parents. We just removed the color of one of the parents, but - // the cloned block will be unreachable until we clone the child - // funclet that contains the catchret instruction. In that case we - // need to create a mapping that will let us find the cloned block - // later and associate it with the cloned child funclet. - bool BlockWillBeEstranged = false; - for (auto *Color : BlockColors[Pred]) { - if (FuncletParents[Color].size() > 1) { - BlockWillBeEstranged = true; - break; // Breaks out of the color loop - } - } - if (BlockWillBeEstranged) { - EstrangedBlocks[FuncletPadBB][OldBlock] = NewBlock; - DEBUG_WITH_TYPE("winehprepare-coloring", - dbgs() << " Saved mapping of estranged block \'" - << NewBlock->getName() << "\' for \'" - << FuncletPadBB->getName() << "\'.\n"); - break; // Breaks out of the predecessor loop - } - } - } } // Loop over all of the instructions in this funclet, fixing up operand @@ -1736,6 +698,40 @@ void WinEHPrepare::cloneCommonBlocks( RemapInstruction(&I, VMap, RF_IgnoreMissingEntries | RF_NoModuleLevelChanges); + auto UpdatePHIOnClonedBlock = [&](PHINode *PN, bool IsForOldBlock) { + unsigned NumPreds = PN->getNumIncomingValues(); + for (unsigned PredIdx = 0, PredEnd = NumPreds; PredIdx != PredEnd; + ++PredIdx) { + BasicBlock *IncomingBlock = PN->getIncomingBlock(PredIdx); + ColorVector &IncomingColors = BlockColors[IncomingBlock]; + bool BlockInFunclet = IncomingColors.size() == 1 && + IncomingColors.front() == FuncletPadBB; + if (IsForOldBlock != BlockInFunclet) + continue; + PN->removeIncomingValue(IncomingBlock, /*DeletePHIIfEmpty=*/false); + // Revisit the next entry. + --PredIdx; + --PredEnd; + } + }; + + for (auto &BBMapping : Orig2Clone) { + BasicBlock *OldBlock = BBMapping.first; + BasicBlock *NewBlock = BBMapping.second; + for (Instruction &OldI : *OldBlock) { + auto *OldPN = dyn_cast<PHINode>(&OldI); + if (!OldPN) + break; + UpdatePHIOnClonedBlock(OldPN, /*IsForOldBlock=*/true); + } + for (Instruction &NewI : *NewBlock) { + auto *NewPN = dyn_cast<PHINode>(&NewI); + if (!NewPN) + break; + UpdatePHIOnClonedBlock(NewPN, /*IsForOldBlock=*/false); + } + } + // 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) { @@ -1783,7 +779,7 @@ void WinEHPrepare::cloneCommonBlocks( for (Use &U : OldI->uses()) { Instruction *UserI = cast<Instruction>(U.getUser()); BasicBlock *UserBB = UserI->getParent(); - SetVector<BasicBlock *> &ColorsForUserBB = BlockColors[UserBB]; + ColorVector &ColorsForUserBB = BlockColors[UserBB]; assert(!ColorsForUserBB.empty()); if (ColorsForUserBB.size() > 1 || *ColorsForUserBB.begin() != FuncletPadBB) @@ -1813,10 +809,10 @@ void WinEHPrepare::removeImplausibleTerminators(Function &F) { // Remove implausible terminators and replace them with UnreachableInst. for (auto &Funclet : FuncletBlocks) { BasicBlock *FuncletPadBB = Funclet.first; - std::set<BasicBlock *> &BlocksInFunclet = Funclet.second; - Instruction *FirstNonPHI = FuncletPadBB->getFirstNonPHI(); - auto *CatchPad = dyn_cast<CatchPadInst>(FirstNonPHI); - auto *CleanupPad = dyn_cast<CleanupPadInst>(FirstNonPHI); + std::vector<BasicBlock *> &BlocksInFunclet = Funclet.second; + Instruction *FuncletPadInst = FuncletPadBB->getFirstNonPHI(); + auto *CatchPad = dyn_cast<CatchPadInst>(FuncletPadInst); + auto *CleanupPad = dyn_cast<CleanupPadInst>(FuncletPadInst); for (BasicBlock *BB : BlocksInFunclet) { TerminatorInst *TI = BB->getTerminator(); @@ -1830,34 +826,22 @@ void WinEHPrepare::removeImplausibleTerminators(Function &F) { bool IsUnreachableCleanupret = false; if (auto *CRI = dyn_cast<CleanupReturnInst>(TI)) IsUnreachableCleanupret = CRI->getCleanupPad() != CleanupPad; - // The token consumed by a CleanupEndPadInst must match the funclet token. - bool IsUnreachableCleanupendpad = false; - if (auto *CEPI = dyn_cast<CleanupEndPadInst>(TI)) - IsUnreachableCleanupendpad = CEPI->getCleanupPad() != CleanupPad; if (IsUnreachableRet || IsUnreachableCatchret || - IsUnreachableCleanupret || IsUnreachableCleanupendpad) { + IsUnreachableCleanupret) { // 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(); + } else if (isa<InvokeInst>(TI)) { + // Invokes within a cleanuppad for the MSVC++ personality never + // transfer control to their unwind edge: the personality will + // terminate the program. + if (Personality == EHPersonality::MSVC_CXX && CleanupPad) + removeUnwindEdge(BB); } - // FIXME: Check for invokes/cleanuprets/cleanupendpads which unwind to - // implausible catchendpads (i.e. catchendpad not in immediate parent - // funclet). } } } @@ -1886,27 +870,31 @@ void WinEHPrepare::verifyPreparedFunclets(Function &F) { report_fatal_error("Uncolored BB!"); if (NumColors > 1) report_fatal_error("Multicolor BB!"); - bool EHPadHasPHI = BB.isEHPad() && isa<PHINode>(BB.begin()); - assert(!EHPadHasPHI && "EH Pad still has a PHI!"); - if (EHPadHasPHI) - report_fatal_error("EH Pad still has a PHI!"); + if (!DisableDemotion) { + bool EHPadHasPHI = BB.isEHPad() && isa<PHINode>(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<BasicBlock *> &EntryBlocks) { +bool WinEHPrepare::prepareExplicitEH(Function &F) { + // 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); + colorFunclets(F); + + cloneCommonBlocks(F); if (!DisableDemotion) demotePHIsOnFunclets(F); - cloneCommonBlocks(F, EntryBlocks); - - resolveFuncletAncestry(F, EntryBlocks); - if (!DisableCleanups) { removeImplausibleTerminators(F); @@ -1917,10 +905,6 @@ bool WinEHPrepare::prepareExplicitEH( BlockColors.clear(); FuncletBlocks.clear(); - FuncletChildren.clear(); - FuncletParents.clear(); - EstrangedBlocks.clear(); - FuncletCloningRequired = false; return true; } @@ -1930,9 +914,11 @@ bool WinEHPrepare::prepareExplicitEH( AllocaInst *WinEHPrepare::insertPHILoads(PHINode *PN, Function &F) { BasicBlock *PHIBlock = PN->getParent(); AllocaInst *SpillSlot = nullptr; + Instruction *EHPad = PHIBlock->getFirstNonPHI(); - if (isa<CleanupPadInst>(PHIBlock->getFirstNonPHI())) { - // Insert a load in place of the PHI and replace all uses. + if (!isa<TerminatorInst>(EHPad)) { + // If the EHPad isn't a terminator, then we can insert a load in this block + // that will dominate all uses. SpillSlot = new AllocaInst(PN->getType(), nullptr, Twine(PN->getName(), ".wineh.spillslot"), &F.getEntryBlock().front()); @@ -1942,16 +928,16 @@ AllocaInst *WinEHPrepare::insertPHILoads(PHINode *PN, Function &F) { return SpillSlot; } + // Otherwise, we have a PHI on a terminator EHPad, and we give up and insert + // loads of the slot before every use. DenseMap<BasicBlock *, Value *> Loads; for (Value::use_iterator UI = PN->use_begin(), UE = PN->use_end(); UI != UE;) { Use &U = *UI++; auto *UsingInst = cast<Instruction>(U.getUser()); - BasicBlock *UsingBB = UsingInst->getParent(); - if (UsingBB->isEHPad()) { + if (isa<PHINode>(UsingInst) && UsingInst->getParent()->isEHPad()) { // Use is on an EH pad phi. Leave it alone; we'll insert loads and // stores for it separately. - assert(isa<PHINode>(UsingInst)); continue; } replaceUseWithLoad(PN, U, SpillSlot, Loads, F); @@ -2005,7 +991,7 @@ void WinEHPrepare::insertPHIStore( SmallVectorImpl<std::pair<BasicBlock *, Value *>> &Worklist) { if (PredBlock->isEHPad() && - !isa<CleanupPadInst>(PredBlock->getFirstNonPHI())) { + isa<TerminatorInst>(PredBlock->getFirstNonPHI())) { // Pred is unsplittable, so we need to queue it on the worklist. Worklist.push_back({PredBlock, PredVal}); return; @@ -2065,10 +1051,10 @@ void WinEHPrepare::replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot, Goto->setSuccessor(0, PHIBlock); CatchRet->setSuccessor(NewBlock); // Update the color mapping for the newly split edge. - SetVector<BasicBlock *> &ColorsForPHIBlock = BlockColors[PHIBlock]; + ColorVector &ColorsForPHIBlock = BlockColors[PHIBlock]; BlockColors[NewBlock] = ColorsForPHIBlock; for (BasicBlock *FuncletPad : ColorsForPHIBlock) - FuncletBlocks[FuncletPad].insert(NewBlock); + FuncletBlocks[FuncletPad].push_back(NewBlock); // Treat the new block as incoming for load insertion. IncomingBlock = NewBlock; } @@ -2087,11 +1073,10 @@ void WinEHPrepare::replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot, } } -void WinEHFuncInfo::addIPToStateRange(const BasicBlock *PadBB, +void WinEHFuncInfo::addIPToStateRange(const InvokeInst *II, 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); + assert(InvokeStateMap.count(II) && + "should get invoke with precomputed state"); + LabelToStateMap[InvokeBegin] = std::make_pair(InvokeStateMap[II], InvokeEnd); } |