Win32ExceptionPass.cpp

#include "TypeScript/Pass/Win32ExceptionPass.h"

#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Module.h"

#include "llvm/ADT/PostOrderIterator.h"

using namespace llvm;
using namespace PatternMatch;

#define DEBUG_TYPE "pass"

// see readPadTag
constexpr const char *EH_PAD_FUNC_NAME = "ts.internal.eh_pad";

//#define SAVE_STACK true

struct CatchRegion
{
    CatchRegion() = default;

    LandingPadInst *landingPad;
    llvm::SmallVector<CallBase *> calls;
    CatchPadInst *catchPad;
    CleanupPadInst *cleanupPad;
    InvokeInst *unwindInfoOp;
    Value *stack;
    bool hasAlloca;
    llvm::Instruction *cxaBeginCatch;
    llvm::Instruction *saveCatch;
    llvm::Instruction *cxaEndCatch;
    llvm::Instruction *end;
    // every invoke in the region, in order - unwindInfoOp is chosen from these once all the
    // regions are known (see chooseUnwindInfoOps)
    llvm::SmallVector<InvokeInst *> invokes;
    // index of the region this one is nested in, or -1; and the ids ts.internal.eh_pad gave
    int parent = -1;
    int padId = 0;
    // the block the landing pad began, which is what invokes unwind to - making the catchpad
    // splits the pad off into a block of its own
    BasicBlock *padBlock = nullptr;

    bool isCatch()
    {
        return landingPad->getNumClauses() > 0 && landingPad->isCatch(0) && !landingPad->isCleanup();
    }

    bool isCleanup()
    {
        if (landingPad && landingPad->isCleanup())
        {
            return true;
        }

        if (landingPad->getNumClauses() == 0)
        {
            landingPad->setCleanup(true);
            return true;
        }

        // a filter clause is the compiler's cleanup marker (see windows::LandingPadOpLowering
        // in LowerToLLVM.cpp): normally LandingPadFixPass has already canonicalized such pads
        // to clause-less cleanup landingpads before this pass runs, so this branch is a
        // defensive fallback for pads that still carry the marker (e.g. if pass ordering ever
        // changes or the inliner merges landing pads before canonicalization).
        if ((landingPad->getNumClauses() > 0 && !landingPad->isCatch(0)))
        {
            // this is filter[], treat it as cleanup
            landingPad->setCleanup(true);
            return true;
        }

        return false;
    }
};

struct Win32ExceptionPassCode
{
    llvm::StructType *ThrowInfoType;

    Win32ExceptionPassCode() : ThrowInfoType{nullptr}
    {
    }

    static bool isEndCatchCall(llvm::Instruction *I)
    {
        auto *CI = dyn_cast<CallInst>(I);
        return CI && CI->getCalledFunction() != nullptr && CI->getCalledFunction()->hasName() &&
               CI->getCalledFunction()->getName() == "__cxa_end_catch";
    }

    // The two invokes a catch region can legitimately end on: its own end-of-catch marker, or a
    // throw out of it. Either way nothing follows inside the funclet, so it needs no catchret.
    static bool isCatchEndingInvoke(llvm::Instruction *I)
    {
        auto *II = dyn_cast<InvokeInst>(I);
        if (!II || II->getCalledFunction() == nullptr || !II->getCalledFunction()->hasName())
        {
            return false;
        }

        auto name = II->getCalledFunction()->getName();
        return name == "__cxa_end_catch" || name == "_CxxThrowException";
    }

    bool runOnFunction(Function &F)
    {
        auto MadeChange = false;

        llvm::SmallVector<CatchRegion> catchRegionsWorkSet;

        LLVM_DEBUG(llvm::dbgs() << "\n!! Function: " << F.getName(););
        LLVM_DEBUG(llvm::dbgs() << "\n!! Dump Before: ...\n" << F << "\n";);

        CatchRegion *catchRegion = nullptr;
        auto endOfCatch = false;
        auto endOfCatchIfResume = false;
        llvm::SmallVector<llvm::Instruction *> toRemoveWorkSet;

        // The regions still open, innermost last, as indexes into catchRegionsWorkSet (which
        // reallocates). A pad can be nested in a catch - a try, or a `using`, inside a catch
        // clause - and TryOpLowering says which catch in the tag after the pad (readPadTag). Its
        // code sits in the middle of the enclosing catch's, whose end only comes after it:
        // taking the new pad as the end of the old region, as this scan used to, left the catch
        // with no end at all (the pass then crashed on it), and making every pad `within none`
        // put an edge out of the catch funclet that the verifier rejects.
        llvm::SmallVector<int> openRegions;
        auto closeRegion = [&]() {
            if (!openRegions.empty())
            {
                openRegions.pop_back();
            }

            catchRegion = openRegions.empty() ? nullptr : &catchRegionsWorkSet[openRegions.back()];
        };

        for (auto &I : instructions(F))
        {
            if (auto *LPI = dyn_cast<LandingPadInst>(&I))
            {
                auto [padId, parentPadId] = readPadTag(LPI, toRemoveWorkSet);
                auto parent = findRegionByPadId(catchRegionsWorkSet, parentPadId);

                catchRegionsWorkSet.push_back(CatchRegion());
                catchRegion = &catchRegionsWorkSet.back();

                catchRegion->landingPad = LPI;
                catchRegion->parent = parent;
                catchRegion->padId = padId;
                catchRegion->padBlock = LPI->getParent();

                // leave open what encloses the new pad, and nothing that was nested deeper; a pad
                // not nested in an open region starts afresh, as every pad always did
                while (!openRegions.empty() && openRegions.back() != parent)
                {
                    openRegions.pop_back();
                }

                openRegions.push_back(catchRegionsWorkSet.size() - 1);

                endOfCatch = false;
                continue;
            }

            // it is outsize of catch/finally region
            if (!catchRegion)
            {
                // A surplus end-of-catch marker, with no region left for it to close. See the
                // note at the `endOfCatch` handling below for where they come from; either way
                // one that survives is an unresolved symbol at link time, so it goes.
                if (isEndCatchCall(&I))
                {
                    toRemoveWorkSet.push_back(&I);
                    MadeChange = true;
                }

                continue;
            }

            if (endOfCatchIfResume && dyn_cast<ResumeInst>(&I))
            {
                endOfCatch = true;
            }

            endOfCatchIfResume = false;

            if (endOfCatch)
            {
                // A second end-of-catch marker can follow the one that just closed this region,
                // and it must not become the region's `end`: `end` is where the catchret goes,
                // and leaving an `__cxa_end_catch` there keeps an Itanium marker with no Win64
                // counterpart in the emitted code - an unresolved symbol at link time.
                //
                // They arise wherever a catch clause is ended twice over. A `try/catch` written
                // inside a catch clause is the case that found this: the inner `throw` ends the
                // enclosing catch ahead of itself (§9.14), and the outer try then emits its own
                // end marker as well, so the tail carries both. Skipping past them - staying in
                // this state rather than leaving it - handles any number of them and leaves the
                // real end instruction to close the region.
                if (isEndCatchCall(&I))
                {
                    toRemoveWorkSet.push_back(&I);
                    MadeChange = true;

                    // Unless this region is nested in one still open: then the marker is the
                    // enclosing catch's own - a try inside a catch clause ends both, inner one
                    // first. The inner catch returns here, into the enclosing funclet, and the
                    // enclosing catch ends at what follows.
                    if (openRegions.size() > 1)
                    {
                        catchRegion->end = &I;
                        closeRegion();
                        catchRegion->cxaEndCatch = &I;
                    }

                    continue;
                }

                // BR, or instraction without BR
                catchRegion->end = &I;
                endOfCatch = false;

                // the region it was nested in carries on
                closeRegion();
                continue;
            }

            if (auto *II = dyn_cast<InvokeInst>(&I))
            {
                catchRegion->invokes.push_back(II);
            }

            if (dyn_cast<AllocaInst>(&I))
            {
                catchRegion->hasAlloca = true;
            }

            if (auto *CI = dyn_cast<CallInst>(&I))
            {
                if (CI->getCalledFunction() != nullptr && CI->getCalledFunction()->hasName())
                {
                    LLVM_DEBUG(llvm::dbgs() << "\n!! Call: " << CI->getCalledFunction()->getName() << "");

                    if (CI->getCalledFunction()->getName() == "__cxa_begin_catch")
                    {
                        LLVM_DEBUG(llvm::dbgs() << "\n!! __cxa_begin_catch : " << *CI << "\n";);
                        LLVM_DEBUG(llvm::dbgs() << "\n!! __cxa_begin_catch op 0 : " << *CI->getOperand(0) << "\n";);

                        toRemoveWorkSet.push_back(&I);
                        auto extractOp = cast<llvm::ExtractValueInst>(CI->getOperand(0));
                        toRemoveWorkSet.push_back(extractOp);
                        catchRegion->cxaBeginCatch = &I;
                        continue;
                    }

                    if (CI->getCalledFunction()->getName() == EH_PAD_FUNC_NAME)
                    {
                        // read at the pad by readPadTag, and removed there
                        continue;
                    }

                    if (CI->getCalledFunction()->getName() == "ts.internal.save_catch_var")
                    {
                        catchRegion->saveCatch = &I;
                        continue;
                    }

                    if (CI->getCalledFunction()->getName() == "__cxa_end_catch")
                    {
                        toRemoveWorkSet.push_back(&I);
                        catchRegion->cxaEndCatch = &I;
                        endOfCatch = true;
                        continue;
                    }

                    // possible end
                    if (CI->getCalledFunction()->getName() == "_CxxThrowException")
                    {
                        catchRegion->end = &I;

                        // For a catch, the end-of-catch handling below splits the block ahead
                        // of `end` and emits the catchret there, which leaves this call on the
                        // far side of it - outside the funclet. So it must not be collected
                        // into `calls`, which is what stamps the funclet bundle on: a bundle
                        // naming a pad the throw has already returned from is malformed IR,
                        // and it crashes the backend.
                        //
                        // The __cxa_end_catch marker above keeps the two apart for this same
                        // instruction whenever MLIRGen emitted one, by closing the region
                        // before the throw is ever reached. A throw the inliner brought in has
                        // no marker - the EndCatchOp that followed the call it replaced went
                        // with the rest of the now-unreachable code after it - so it has to be
                        // recognised on its own.
                        //
                        // Skipping the call is all that takes, though: leave the region open.
                        // This scan walks the function's instructions in order rather than by
                        // region, so after inlining a throw belonging to one catch can turn up
                        // while another is still open, and closing on it would strand the rest
                        // of that catch's calls with no bundle at all (00try_catch.ts).
                        //
                        // A cleanup region gets no catchret, so its throw stays inside the
                        // funclet and does still need the bundle; leave that path alone.
                        if (catchRegion->isCatch())
                        {
                            continue;
                        }
                    }
                    else
                    {
                        LLVM_DEBUG(llvm::dbgs() << "\n!! WARNING Must be Invoke: " << I << "\n");

                        // TODO: uncomment me
                        /*
                        llvm_unreachable("CallInst must not be used in Try/Catch/Finally block as it will cause issue with incorrect unwind "
                                        "destination when Inliner inlines body of method");
                        */
                    }
                }
            }

            if (auto *II = dyn_cast<InvokeInst>(&I))
            {
                if (II->getCalledFunction() != nullptr && II->getCalledFunction()->hasName())
                {
                    LLVM_DEBUG(llvm::dbgs() << "\n!! Invoke: " << II->getCalledFunction()->getName() << "");

                    if (II->getCalledFunction()->getName() == "__cxa_end_catch")
                    {
                        toRemoveWorkSet.push_back(&I);
                        catchRegion->cxaEndCatch = &I;
                        catchRegion->end = &I;

                        endOfCatchIfResume = true;

                        continue;
                    }

                    // possible end
                    if (II->getCalledFunction()->getName() == "_CxxThrowException")
                    {
                        // do not put continue, we need to add facelet
                        catchRegion->end = &I;
                    }
                }
            }

            if (auto *CB = dyn_cast<CallBase>(&I))
            {
                catchRegion->calls.push_back(CB);
                continue;
            }
        }

        chooseUnwindInfoOps(catchRegionsWorkSet);

        // create begin of catch block (a parent comes before the regions nested in it)
        for (auto &catchRegion : catchRegionsWorkSet)
        {
            auto *LPI = catchRegion.landingPad;
            auto *parentPad = parentPadOf(catchRegionsWorkSet, catchRegion);

            LLVM_DEBUG(llvm::dbgs() << "\n!! Processing: " << *LPI << " isKnownSentinel: " << (LPI->isKnownSentinel() ? "true" : "false")
                                    << "\n";);

            // add catchswitch & catchpad
            llvm::IRBuilder<> Builder(LPI);
            llvm::LLVMContext &Ctx = Builder.getContext();

            if (catchRegion.isCatch())
            {
                // split
                BasicBlock *CurrentBB = LPI->getParent();
                BasicBlock *ContinuationBB = CurrentBB->splitBasicBlock(LPI->getIterator(), "catch");

                CurrentBB->getTerminator()->eraseFromParent();

                auto *II = catchRegion.unwindInfoOp;
                auto *CSI = CatchSwitchInst::Create(parentPad,
                                                    II ? II->getUnwindDest() : nullptr
                                                    /*unwind to caller if null*/,
                                                    1, "catch.switch", CurrentBB);
                CSI->addHandler(ContinuationBB);

                // check what is type of catch
                auto value = LPI->getOperand(0);
                auto isNullInst = isa<ConstantPointerNull>(value);
                if (isNullInst || !catchRegion.saveCatch)
                {
                    // catch (...) as catch value is null
                    auto nullI8Ptr = ConstantPointerNull::get(PointerType::get(Ctx, 0));
                    auto iVal64 = ConstantInt::get(IntegerType::get(Ctx, 32), 64);
                    catchRegion.catchPad = CatchPadInst::Create(CSI, {nullI8Ptr, iVal64, nullI8Ptr}, "catchpad", LPI->getIterator());
                }
                else
                {
                    auto varRef = catchRegion.saveCatch->getOperand(1)->stripPointerCasts();
                    assert(varRef);
                    auto iValTypeId = ConstantInt::get(IntegerType::get(Ctx, 32), getTypeNumber(varRef->getType()));
                    catchRegion.catchPad = CatchPadInst::Create(CSI, {value, iValTypeId, varRef}, "catchpad", LPI->getIterator());
                    catchRegion.saveCatch->eraseFromParent();
                }
            }
            else
            {
                assert(catchRegion.isCleanup());

                catchRegion.cleanupPad = CleanupPadInst::Create(parentPad, {}, "cleanuppad", LPI->getIterator());
            }

            auto opBundle = getCallBundleFromCatchRegion(catchRegion);

#ifdef SAVE_STACK            
            // save stack
            if (catchRegion.hasAlloca)
            {
                // TODO: it seems I don't need opBundle here
                auto stackSaveFuncCallee = Intrinsic::getDeclaration(F.getParent(), Intrinsic::stacksave);
                auto callInst = Builder.CreateCall(stackSaveFuncCallee->getFunctionType(), stackSaveFuncCallee, {}, opBundle);
                catchRegion.stack = callInst;
            }
#endif

            // set funcset
            llvm::SmallVector<CallBase *> newCalls;
            for (auto callBase : catchRegion.calls)
            {
                auto replaceEndData = catchRegion.end == callBase;
                auto replaceUnwindInfoOp = catchRegion.unwindInfoOp == callBase;

                CallBase *newCallBase = nullptr;
                /*
                if (catchRegion.unwindInfoOp)
                {
                    if (isa<CallInst>(callBase))
                    {
                        if (auto *CI = cast<CallInst>(callBase))
                        {
                            newCallBase = ToInvoke(CI, catchRegion.unwindInfoOp->getUnwindDest(), opBundle);
                        }
                    }
                }
                */

                // default case
                if (!newCallBase)
                {
                    newCallBase = CallBase::Create(callBase, opBundle, callBase->getIterator());
                }

                callBase->replaceAllUsesWith(newCallBase);
                callBase->eraseFromParent();

                newCalls.push_back(newCallBase);

                if (replaceEndData)
                {
                    catchRegion.end = newCallBase;
                }

                if (replaceUnwindInfoOp)
                {
                    catchRegion.unwindInfoOp = cast<InvokeInst>(newCallBase);
                }
            }

            catchRegion.calls.clear();
            catchRegion.calls.append(newCalls);

            // LLVM_DEBUG(llvm::dbgs() << "\nLanding Pad - Done. Function Dump: " << F << "\n\n";);

            MadeChange = true;
        }

        // create end of catch block
        for (auto &catchRegion : catchRegionsWorkSet)
        {
            auto *I = catchRegion.end;
            assert(I);
            auto *LPI = catchRegion.landingPad;
            assert(LPI);

            llvm::BasicBlock *retBlock = nullptr;

            llvm::IRBuilder<> Builder(I);
            llvm::LLVMContext &Ctx = Builder.getContext();

            // A catch region's `end` is otherwise just the first instruction after its
            // end-of-catch marker, and that can be an ordinary invoke: once the canonicalizer
            // merges a catch block into what follows it, a second try's first call comes
            // straight after the first catch. Treated like the end marker, that invoke got no
            // catchret, so the second try ran inside the first catch's funclet and crashed.
            // It has to be split off like any other instruction instead.
            auto *endInvoke = dyn_cast<InvokeInst>(I);
            if (endInvoke && catchRegion.isCatch() && !isCatchEndingInvoke(endInvoke))
            {
                endInvoke = nullptr;
            }

            auto *BI = dyn_cast<BranchInst>(I);
            if (BI)
            {
                retBlock = BI->getSuccessor(0);
            }
            else if (endInvoke)
            {
                retBlock = endInvoke->getNormalDest();
            }
            else if (dyn_cast<ResumeInst>(I))
            {
                // nothing todo
                toRemoveWorkSet.push_back(I);
            }
            else
            {
                retBlock = Builder.GetInsertBlock()->splitBasicBlock(I, "end.of.exception");
                BI = dyn_cast<BranchInst>(&retBlock->getPrevNode()->back());
                Builder.SetInsertPoint(BI);
            }

            toRemoveWorkSet.push_back(&*LPI);

#ifdef SAVE_STACK
            if (catchRegion.hasAlloca)
            {
                // TODO: if we already have stackrestore before we do not need this stack restore, it will cause the issue for optimization and thus will not be compiled
                // TODO: it seems I don't need opBundle here

                assert(catchRegion.stack);

                // restore stack
                auto opBundle = getCallBundleFromCatchRegion(catchRegion);
                auto stackRestoreFuncCallee = Intrinsic::getDeclaration(F.getParent(), Intrinsic::stackrestore);
                Builder.CreateCall(stackRestoreFuncCallee->getFunctionType(), stackRestoreFuncCallee, {catchRegion.stack}, opBundle);
            }
#endif            

            if (catchRegion.isCatch())
            {
                if (!endInvoke)
                {
                    assert(catchRegion.catchPad);
                    auto CR = CatchReturnInst::Create(catchRegion.catchPad, retBlock, BI ? BI->getParent() : I->getParent());
                    if (BI)
                    {
                        // remove BranchInst
                        BI->replaceAllUsesWith(CR);
                        toRemoveWorkSet.push_back(&*BI);
                    }
                }

                // convert call to Invoke with the same unwind
                /*
                llvm::SmallVector<OperandBundleDef> opBundle;
                opBundle.emplace_back(OperandBundleDef("funclet", catchRegion.catchPad));
                for (auto callBase : catchRegion.calls)
                {
                    if (isa<CallInst>(callBase))
                    {
                        if (auto *CI = cast<CallInst>(callBase))
                        {
                            LLVM_DEBUG(llvm::dbgs() << "\n!! CONVERT CALL TO INVOKE(catchpad): " << *callBase << "\n");

                            auto newCallBase = ToInvoke(CI, retBlock, opBundle);
                            callBase->replaceAllUsesWith(newCallBase);
                            callBase->eraseFromParent();
                        }
                    }
                }
                */
            }
            else
            {
                // cleanup
                assert(catchRegion.cleanupPad);

                BasicBlock *emptyBlockBefore = nullptr;
                if (I->getPrevNode() == nullptr)
                {
                    emptyBlockBefore = Builder.GetInsertBlock();
                }

                BasicBlock *CurrentBB = I->getParent();
                BasicBlock *ContinuationBB = CurrentBB->splitBasicBlock(CurrentBB->getTerminator(), "catch.pad");
                BasicBlock *CSIBlock =
                    emptyBlockBefore ? emptyBlockBefore : BasicBlock::Create(Ctx, "catch.dispatch", CurrentBB->getParent(), ContinuationBB);

                CurrentBB->getTerminator()->eraseFromParent();

                if (emptyBlockBefore)
                {
                    CurrentBB = emptyBlockBefore->getPrevNode();
                }

                // A cleanup with a handler to go on to (a `using` scope, or an owning local's
                // release, inside a try with a catch) hands the exception straight to it, as clang
                // does: `cleanupret unwind label <handler>`. Through the catch-all funclet below,
                // which rethrows, the exception was lost whenever the function also allocated on
                // the stack dynamically (a two-argument `print`): the handler did not catch the
                // rethrow, and the program terminated (#457). The funclet is still built, for a
                // cleanup with no handler here, and is left unreachable otherwise.
                auto *II = catchRegion.unwindInfoOp;
                auto *handlerPad = II ? II->getUnwindDest() : nullptr;
                CleanupReturnInst::Create(catchRegion.cleanupPad, handlerPad ? handlerPad : CSIBlock, CurrentBB);

                // add rethrow code

                // beside the cleanup pad, in the same parent: cleanupret unwinds to it
                auto *CSI = CatchSwitchInst::Create(parentPadOf(catchRegionsWorkSet, catchRegion),
                                                    II ? II->getUnwindDest() : nullptr
                                                    /*unwind to caller if null*/,
                                                    1, "catchswitch", CSIBlock);

                CSI->addHandler(ContinuationBB);

                // catch (...) as catch value is null
                auto nullI8Ptr = ConstantPointerNull::get(PointerType::get(Ctx, 0));
                auto iVal64 = ConstantInt::get(IntegerType::get(Ctx, 32), 64);
                auto *CPI = CatchPadInst::Create(CSI, {nullI8Ptr, iVal64, nullI8Ptr}, "catchpad", ContinuationBB);

                // rethrow
                llvm::SmallVector<OperandBundleDef> opBundle;
                opBundle.emplace_back(OperandBundleDef("funclet", CPI));

                auto throwFunc = getThrowFn(Ctx, F.getParent());

                auto nullTI = ConstantPointerNull::get(cast<llvm::PointerType>(throwFunc.getFunctionType()->params()[1]));

                // TODO: we need to find block with unreachable first
                if (auto *unreachBlock = findUnreachableBlock(F))
                {
                    // TODO: I don't know why but we need it here
                    unreachBlock->setName("unreachable");
                    auto *BI = BranchInst::Create(unreachBlock, ContinuationBB);
                    Builder.SetInsertPoint(BI);
                }
                else
                {
                    auto *UI = new UnreachableInst(Ctx, ContinuationBB);
                    Builder.SetInsertPoint(UI);
                }

                Builder.CreateCall(throwFunc, {nullI8Ptr, nullTI}, opBundle);

                // end

                // convert call to Invoke with the same unwind
                /*
                llvm::SmallVector<OperandBundleDef> opBundleCleanup;
                opBundleCleanup.emplace_back(OperandBundleDef("funclet", catchRegion.cleanupPad));
                for (auto callBase : catchRegion.calls)
                {
                    if (isa<CallInst>(callBase))
                    {
                        if (auto *CI = cast<CallInst>(callBase))
                        {
                            LLVM_DEBUG(llvm::dbgs() << "\n!! CONVERT CALL TO INVOKE(cleanup): " << *callBase << "\n");

                            auto newCallBase = ToInvoke(CI, CSIBlock, opBundleCleanup);
                            callBase->replaceAllUsesWith(newCallBase);
                            callBase->eraseFromParent();
                        }
                    }
                }
                */

                // fix incorrect landing pad
                // inlineing messing up with landingpad, it may create landing pad with filter and catch clauses, so we are fixing
                // consequences
                llvm::SmallVector<OperandBundleDef> opBundleCleanup;
                opBundleCleanup.emplace_back(OperandBundleDef("funclet", catchRegion.cleanupPad));
                for (auto callBase : catchRegion.calls)
                {
                    if (isa<InvokeInst>(callBase))
                    {
                        if (auto *II = cast<InvokeInst>(callBase))
                        {
                            // an invoke into a pad nested in this cleanup stays as it is
                            auto *unwindTo = handlerPad ? handlerPad : CSIBlock;
                            if (II->getUnwindDest() != unwindTo &&
                                !isDescendantPad(catchRegionsWorkSet, catchRegion, II->getUnwindDest()))
                            {
                                LLVM_DEBUG(llvm::dbgs() << "\n!! FIX INVOKE(cleanup): " << *callBase << "\n");

                                auto newCallBase = ToInvoke(callBase, unwindTo, opBundleCleanup);
                                callBase->replaceAllUsesWith(newCallBase);
                                callBase->eraseFromParent();
                            }
                        }
                    }
                }
            }

            // LLVM_DEBUG(llvm::dbgs() << "\nTerminator after: " << *RI->getParent()->getTerminator() << "\n\n";);
            // LLVM_DEBUG(llvm::dbgs() << "\nResume - Done. Function Dump: " << F << "\n\n";);

            MadeChange = true;
        }

        LLVM_DEBUG(llvm::dbgs() << "\n!! Dump Before cleanup process: ...\n" << F << "\n\n";);

        // remove
        for (auto CI : toRemoveWorkSet)
        {
            // Erase every PHI-node user first (there can be more than one, e.g. after
            // inlining merges control flow through several PHIs referencing the same
            // to-be-removed value); eraseFromParent() below requires no uses remain.
            while (!CI->use_empty())
            {
                auto UI = llvm::find_if(CI->users(), [](llvm::User *U) { return isa<PHINode>(U); });
                if (UI == CI->user_end())
                {
                    break;
                }

                cast<PHINode>(*UI)->eraseFromParent();
            }

            CI->eraseFromParent();
        }

        cleanupEmptyBlocksWithoutPredecessors(F);

        // LLVM_DEBUG(llvm::dbgs() << "\nDone. Function Dump: " << F << "\n\n";);

        LLVM_DEBUG(llvm::dbgs() << "\n!! Change: " << MadeChange;);
        LLVM_DEBUG(llvm::dbgs() << "\n!! Dump After: ...\n" << F << "\n\n";);

        return MadeChange;
    }

    // The tag TryOpLowering puts right after a pad on Windows (see LandingPadOpLowering):
    // ts.internal.eh_pad(this catch pad's id, id of the catch pad it is nested in). The call is
    // queued for removal. {0, 0} for an untagged pad - one at the top, as every pad used to be.
    static std::pair<int, int> readPadTag(LandingPadInst *LPI, llvm::SmallVector<llvm::Instruction *> &toRemove)
    {
        auto *CI = dyn_cast_or_null<CallInst>(LPI->getNextNode());
        if (!CI || !CI->getCalledFunction() || CI->getCalledFunction()->getName() != EH_PAD_FUNC_NAME)
        {
            return {0, 0};
        }

        toRemove.push_back(CI);
        auto id = cast<ConstantInt>(CI->getArgOperand(0))->getSExtValue();
        auto parent = cast<ConstantInt>(CI->getArgOperand(1))->getSExtValue();
        return {static_cast<int>(id), static_cast<int>(parent)};
    }

    static int findRegionByPadId(llvm::SmallVector<CatchRegion> &regions, int padId)
    {
        if (padId == 0)
        {
            return -1;
        }

        for (auto index = static_cast<int>(regions.size()) - 1; index >= 0; index--)
        {
            if (regions[index].padId == padId)
            {
                return index;
            }
        }

        return -1;
    }

    static bool isDescendantPad(llvm::SmallVector<CatchRegion> &regions, CatchRegion &region, BasicBlock *block)
    {
        auto index = static_cast<int>(&region - regions.data());
        for (auto &other : regions)
        {
            if (other.padBlock != block)
            {
                continue;
            }

            for (auto parent = other.parent; parent >= 0; parent = regions[parent].parent)
            {
                if (parent == index)
                {
                    return true;
                }
            }
        }

        return false;
    }

    // A catchswitch unwinds where exceptions leaving its region go: the first invoke of the
    // region that unwinds out of it. An invoke into a pad nested in the region is not one -
    // a catchswitch cannot unwind into its own descendants.
    static void chooseUnwindInfoOps(llvm::SmallVector<CatchRegion> &regions)
    {
        for (auto &region : regions)
        {
            for (auto *II : region.invokes)
            {
                if (!isDescendantPad(regions, region, II->getUnwindDest()))
                {
                    LLVM_DEBUG(llvm::dbgs() << "\n!! set (unwindInfoOp) : " << *II << "\n";);
                    region.unwindInfoOp = II;
                    break;
                }
            }
        }
    }

    // the pad a region's own pads are created within: its parent region's, or none
    static Value *parentPadOf(llvm::SmallVector<CatchRegion> &regions, CatchRegion &region)
    {
        if (region.parent >= 0)
        {
            auto &parent = regions[region.parent];
            if (parent.catchPad)
            {
                return parent.catchPad;
            }

            if (parent.cleanupPad)
            {
                return parent.cleanupPad;
            }
        }

        return ConstantTokenNone::get(region.landingPad->getContext());
    }

    llvm::SmallVector<OperandBundleDef> getCallBundleFromCatchRegion(CatchRegion &catchRegion)
    {
        llvm::SmallVector<OperandBundleDef> opBundle;
        if (catchRegion.catchPad)
        {
            opBundle.emplace_back(OperandBundleDef("funclet", catchRegion.catchPad));
        }
        else if (catchRegion.cleanupPad)
        {
            opBundle.emplace_back(OperandBundleDef("funclet", catchRegion.cleanupPad));
        }
        else
        {
            // every CatchRegion gets exactly one of catchPad/cleanupPad set, at the same site
            // that first identifies it (both branches above set one or the other, never
            // neither) - same invariant this file already asserts elsewhere (lines 393, 426)
            // rather than crashing via llvm_unreachable; match that existing convention.
            assert(catchRegion.catchPad || catchRegion.cleanupPad);
        }

        return opBundle;
    }

    int getTypeNumber(Type *catchValType)
    {
        if (catchValType->isIntegerTy() || catchValType->isFloatTy())
        {
            return 0;
        }

        // default if char*, class etc
        return 1;
    }

    llvm::StructType *getThrowInfoType(LLVMContext &Ctx)
    {
        if (ThrowInfoType)
        {
            return ThrowInfoType;
        }

        llvm::Type *FieldTypes[] = {
            IntegerType::get(Ctx, 32),                // Flags
            PointerType::get(Ctx, 0), // CleanupFn
            PointerType::get(Ctx, 0), // ForwardCompat
            PointerType::get(Ctx, 0)  // CatchableTypeArray
        };
        ThrowInfoType = llvm::StructType::create(Ctx, FieldTypes, "eh.ThrowInfo");
        return ThrowInfoType;
    }

    llvm::FunctionCallee getThrowFn(LLVMContext &Ctx, llvm::Module *module)
    {
        auto globalFunc = module->getNamedValue("_CxxThrowException");
        if (globalFunc)
        {
            return cast<llvm::Function>(globalFunc);
        }

        // _CxxThrowException is passed an exception object and a ThrowInfo object
        // which describes the exception.
        llvm::Type *Args[] = {PointerType::get(Ctx, 0), PointerType::get(Ctx, 0)};
        auto *FTy = llvm::FunctionType::get(Type::getVoidTy(Ctx), Args, /*isVarArg=*/false);
        auto Throw = Function::Create(FTy, llvm::GlobalValue::LinkageTypes::ExternalLinkage, "_CxxThrowException", module);
        // On 32-bit x86 this is __stdcall; CxxThrowCallingConvPass sets that on it and its call sites.

        return Throw;
    }

    InvokeInst *ToInvoke(CallBase *CB, BasicBlock *unwind, llvm::SmallVector<OperandBundleDef> &opBundle)
    {
        // An invoke already ends its block and already names a normal destination, so all it
        // needs is its unwind edge redirected and the bundle added - not a block of its own.
        // Splitting at one puts it alone in the continuation block, and every caller erases it
        // immediately afterwards, which leaves that block empty and without a terminator while
        // the real continuation is left with no predecessors at all. A `using` in a nested
        // scope inside a try body produced exactly that, and the empty block crashed the
        // inliner. Cloning it in place is what the funclet-bundle loop above already does.
        if (auto *II = dyn_cast<InvokeInst>(CB))
        {
            auto *newInvoke = cast<InvokeInst>(CallBase::Create(II, opBundle, II->getIterator()));
            newInvoke->setUnwindDest(unwind);
            return newInvoke;
        }

        BasicBlock *CurrentBB = CB->getParent();
        BasicBlock *ContinuationBB = CurrentBB->splitBasicBlock(CB->getIterator(), "invoke.cont");

        CurrentBB->getTerminator()->eraseFromParent();

        SmallVector<Value *> args;
        for (auto &arg : CB->args())
        {
            args.push_back(CB->getArgOperand(arg.getOperandNo()));
        }

        auto newInvoke =
            InvokeInst::Create(CB->getFunctionType(), CB->getCalledOperand(), ContinuationBB, unwind, args, opBundle, "invoke", CurrentBB);

        return newInvoke;
    }

    void cleanupEmptyBlocksWithoutPredecessors(Function &F)
    {
        auto any = false;
        do
        {
            any = false;
            SmallPtrSet<BasicBlock *, 16> workSet;
            for (auto &regionBlock : F)
            {

                if (regionBlock.isEntryBlock())
                {
                    continue;
                }

                if (regionBlock.hasNPredecessors(0))
                {
                    auto count = std::distance(regionBlock.begin(), regionBlock.end());
                    if (count == 0 || (count == 1 && (isa<BranchInst>(regionBlock.begin()) || isa<UnreachableInst>(regionBlock.begin()))))
                    {
                        LLVM_DEBUG(llvm::dbgs() << "\n!! REMOVING EMPTY BLOCK: ..." << regionBlock << "\n";);
                        workSet.insert(&regionBlock);
                    }
                }
            }

            for (auto blockPtr : workSet)
            {
                blockPtr->eraseFromParent();
                any = true;
            }
        } while (any);
    }

    BasicBlock *findUnreachableBlock(Function &F)
    {
        SmallPtrSet<BasicBlock *, 16> workSet;
        for (auto &regionBlock : F)
        {
            auto count = std::distance(regionBlock.begin(), regionBlock.end());
            if (count == 1 && isa<UnreachableInst>(regionBlock.begin()))
            {
                return &regionBlock;
            }
        }

        return nullptr;
    }
};

namespace ts
{
    bool verifyFunction(llvm::Function &F) 
    {
        llvm::ReversePostOrderTraversal<llvm::Function *> RPOT(&F);

        for (llvm::BasicBlock *BI : RPOT) 
        {
            for (BasicBlock::iterator II = BI->begin(), IE = BI->end(); II != IE;)
            {
                assert(II->getParent() == &*BI && "Moved to a different block!");
                ++II;
            }
        }

        return true;            
    }

    llvm::PreservedAnalyses Win32ExceptionPass::run(llvm::Function &F, llvm::FunctionAnalysisManager &AM)
    {
        Win32ExceptionPassCode TSEP{};
        if (!TSEP.runOnFunction(F))
        {
            LLVM_DEBUG(verifyFunction(F););

            return llvm::PreservedAnalyses::all();
        }

        return llvm::PreservedAnalyses::none();
    }
}