Index: lib/Transforms/Utils/InlineFunction.cpp =================================================================== --- lib/Transforms/Utils/InlineFunction.cpp +++ lib/Transforms/Utils/InlineFunction.cpp @@ -14,6 +14,7 @@ #include "llvm/Transforms/Utils/Cloning.h" #include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringExtras.h" @@ -228,7 +229,7 @@ Instruction *ChildPad = cast(Child); auto Memo = MemoMap.find(ChildPad); if (Memo == MemoMap.end()) { - // Haven't figure out this child pad yet; queue it. + // Haven't figured out this child pad yet; queue it. Worklist.push_back(ChildPad); continue; } @@ -366,6 +367,10 @@ // search up the chain to try to find a funclet with information. Put // null entries in the memo map to avoid re-processing as we go up. MemoMap[EHPad] = nullptr; +#ifndef NDEBUG + SmallPtrSet TempMemos; + TempMemos.insert(EHPad); +#endif Instruction *LastUselessPad = EHPad; Value *AncestorToken; for (AncestorToken = getParentPad(EHPad); @@ -374,6 +379,13 @@ // Skip over catchpads since they just follow their catchswitches. if (isa(AncestorPad)) continue; + // If the MemoMap had an entry mapping AncestorPad to nullptr, since we + // haven't yet called getUnwindDestTokenHelper for AncestorPad in this + // call to getUnwindDestToken, that would mean that AncestorPad had no + // information in itself, its descendants, or its ancestors. If that + // were the case, then we should also have recorded the lack of information + // for the descendant that we're coming from. So assert that we don't + // find a null entry in the MemoMap for AncestorPad. assert(!MemoMap.count(AncestorPad) || MemoMap[AncestorPad]); auto AncestorMemo = MemoMap.find(AncestorPad); if (AncestorMemo == MemoMap.end()) { @@ -384,25 +396,85 @@ if (UnwindDestToken) break; LastUselessPad = AncestorPad; + MemoMap[LastUselessPad] = nullptr; +#ifndef NDEBUG + TempMemos.insert(LastUselessPad); +#endif } - // Since the whole tree under LastUselessPad has no information, it all must - // match UnwindDestToken; record that to avoid repeating the search. + // We know that getUnwindDestTokenHelper was called on LastUselessPad and + // returned nullptr (and likewise for EHPad and any of its ancestors up to + // LastUselessPad), so LastUselessPad has no information from below. Since + // getUnwindDestTokenHelper must investigate all downward paths through + // no-information nodes to prove that a node has no information like this, + // and since any time it finds information it records it in the MemoMap for + // not just the immediately-containing funclet but also any ancestors also + // exited, it must be the case that, walking downward from LastUselessPad, + // visiting just those nodes which have not been mapped to an unwind dest + // by getUnwindDestTokenHelper (the nullptr TempMemos notwithstanding, since + // they are just used to keep getUnwindDestTokenHelper from repeating work), + // any node visited must have been exhaustively searched with no information + // for it found. SmallVector Worklist(1, LastUselessPad); while (!Worklist.empty()) { Instruction *UselessPad = Worklist.pop_back_val(); - assert(!MemoMap.count(UselessPad) || MemoMap[UselessPad] == nullptr); + auto Memo = MemoMap.find(UselessPad); + if (Memo != MemoMap.end() && Memo->second) { + // Here the name 'UselessPad' is a bit of a misnomer, because we've found + // that it is a funclet that does have information about unwinding to + // a particular destination; its parent was a useless pad. + // Since its parent has no information, the unwind edge must not escape + // the parent, and must target a sibling of this pad. This local unwind + // gives us no information about EHPad. Leave it and the subtree rooted + // at it alone. + assert(getParentPad(Memo->second) == getParentPad(UselessPad)); + continue; + } + // We know we don't have information for UselesPad. If it has an entry in + // the MemoMap (mapping it to nullptr), it must be one of the TempMemos + // added on this invocation of getUnwindDestToken; if a previous invocation + // recorded nullptr, it would have had to prove that the ancestors of + // UselessPad, which include LastUselessPad, had no information, and that + // in turn would have required proving that the descendants of + // LastUselesPad, which include EHPad, have no information about + // LastUselessPad, which would imply that EHPad was mapped to nullptr in + // the MemoMap on that invocation, which isn't the case if we got here. + assert(!MemoMap.count(UselessPad) || TempMemos.count(UselessPad)); + // Assert as we enumerate users that 'UselessPad' doesn't have any unwind + // information that we'd be contradicting by making a map entry for it + // (which is something that getUnwindDestTokenHelper must have proved for + // us to get here). Just assert on is direct users here; the checks in + // this downward walk at its descendants will verify that they don't have + // any unwind edges that exit 'UselessPad' either (i.e. they either have no + // unwind edges or unwind to a sibling). MemoMap[UselessPad] = UnwindDestToken; if (auto *CatchSwitch = dyn_cast(UselessPad)) { - for (BasicBlock *HandlerBlock : CatchSwitch->handlers()) - for (User *U : HandlerBlock->getFirstNonPHI()->users()) + assert(CatchSwitch->getUnwindDest() == nullptr && "Expected useless pad"); + for (BasicBlock *HandlerBlock : CatchSwitch->handlers()) { + auto *CatchPad = HandlerBlock->getFirstNonPHI(); + for (User *U : CatchPad->users()) { + assert( + (!isa(U) || + (getParentPad( + cast(U)->getUnwindDest()->getFirstNonPHI()) == + CatchPad)) && + "Expected useless pad"); if (isa(U) || isa(U)) Worklist.push_back(cast(U)); + } + } } else { assert(isa(UselessPad)); - for (User *U : UselessPad->users()) + for (User *U : UselessPad->users()) { + assert(!isa(U) && "Expected useless pad"); + assert((!isa(U) || + (getParentPad( + cast(U)->getUnwindDest()->getFirstNonPHI()) == + UselessPad)) && + "Expected useless pad"); if (isa(U) || isa(U)) Worklist.push_back(cast(U)); + } } } Index: test/Transforms/Inline/inline-funclets.ll =================================================================== --- test/Transforms/Inline/inline-funclets.ll +++ test/Transforms/Inline/inline-funclets.ll @@ -409,20 +409,240 @@ ret void } +;;; Test with funclets that don't have information for themselves, but have +;;; descendants which unwind to other descendants (left.left unwinds to +;;; left.right, and right unwinds to far_right). Make sure that these local +;;; unwinds don't trip up processing of the ancestor nodes (left and root) that +;;; ultimately have no information. +;;; CHECK-LABEL: define void @test6( +define void @test6() personality void()* @ProcessCLRException { +entry: +; CHECK-NEXT: entry: + invoke void @test6_inlinee() + to label %exit unwind label %cleanup +cleanup: + %pad = cleanuppad within none [] + call void @g() [ "funclet"(token %pad) ] + cleanupret from %pad unwind to caller +exit: + ret void +} + +define void @test6_inlinee() alwaysinline personality void ()* @ProcessCLRException { +entry: + invoke void @g() + to label %exit unwind label %root + ; CHECK-NEXT: invoke void @g() + ; CHECK-NEXT: unwind label %[[root:.+]] +root: + %root.pad = cleanuppad within none [] + invoke void @g() [ "funclet"(token %root.pad) ] + to label %root.cont unwind label %left +; CHECK: [[root]]: +; CHECK-NEXT: %[[root_pad:.+]] = cleanuppad within none [] +; CHECK-NEXT: invoke void @g() [ "funclet"(token %[[root_pad]]) ] +; CHECK-NEXT: to label %[[root_cont:.+]] unwind label %[[left:.+]] + +left: + %left.cs = catchswitch within %root.pad [label %left.catch] unwind to caller +; CHECK: [[left]]: +; CHECK-NEXT: %[[left_cs:.+]] = catchswitch within %[[root_pad]] [label %[[left_catch:.+]]] unwind label %cleanup + +left.catch: + %left.cp = catchpad within %left.cs [] + call void @g() [ "funclet"(token %left.cp) ] + invoke void @g() [ "funclet"(token %left.cp) ] + to label %unreach unwind label %left.left +; CHECK: [[left_catch:.+]]: +; CHECK-NEXT: %[[left_cp:.+]] = catchpad within %[[left_cs]] [] +; CHECK-NEXT: invoke void @g() [ "funclet"(token %[[left_cp]]) ] +; CHECK-NEXT: to label %[[lc_cont:.+]] unwind label %cleanup +; CHECK: [[lc_cont]]: +; CHECK-NEXT: invoke void @g() [ "funclet"(token %[[left_cp]]) ] +; CHECK-NEXT: to label %[[unreach:.+]] unwind label %[[left_left:.+]] + +left.left: + %ll.pad = cleanuppad within %left.cp [] + cleanupret from %ll.pad unwind label %left.right +; CHECK: [[left_left]]: +; CHECK-NEXT: %[[ll_pad:.+]] = cleanuppad within %[[left_cp]] [] +; CHECK-NEXT: cleanupret from %[[ll_pad]] unwind label %[[left_right:.+]] + +left.right: + %lr.pad = cleanuppad within %left.cp [] + unreachable +; CHECK: [[left_right]]: +; CHECK-NEXT: %[[lr_pad:.+]] = cleanuppad within %[[left_cp]] [] +; CHECK-NEXT: unreachable + +root.cont: + call void @g() [ "funclet"(token %root.pad) ] + invoke void @g() [ "funclet"(token %root.pad) ] + to label %unreach unwind label %right +; CHECK: [[root_cont]]: +; CHECK-NEXT: invoke void @g() [ "funclet"(token %[[root_pad]]) ] +; CHECK-NEXT: to label %[[root_cont_cont:.+]] unwind label %cleanup +; CHECK: [[root_cont_cont]]: +; CHECK-NEXT: invoke void @g() [ "funclet"(token %[[root_pad]]) ] +; CHECK-NEXT: to label %[[unreach]] unwind label %[[right:.+]] + +right: + %right.pad = cleanuppad within %root.pad [] + invoke void @g() [ "funclet"(token %right.pad) ] + to label %unreach unwind label %right.child +; CHECK: [[right]]: +; CHECK-NEXT: %[[right_pad:.+]] = cleanuppad within %[[root_pad]] [] +; CHECK-NEXT: invoke void @g() [ "funclet"(token %[[right_pad]]) ] +; CHECK-NEXT: to label %[[unreach]] unwind label %[[right_child:.+]] + +right.child: + %rc.pad = cleanuppad within %right.pad [] + invoke void @g() [ "funclet"(token %rc.pad) ] + to label %unreach unwind label %far_right +; CHECK: [[right_child]]: +; CHECK-NEXT: %[[rc_pad:.+]] = cleanuppad within %[[right_pad]] [] +; CHECK-NEXT: invoke void @g() [ "funclet"(token %[[rc_pad]]) ] +; CHECK-NEXT: to label %[[unreach]] unwind label %[[far_right:.+]] + +far_right: + %fr.cs = catchswitch within %root.pad [label %fr.catch] unwind to caller +; CHECK: [[far_right]]: +; CHECK-NEXT: %[[fr_cs:.+]] = catchswitch within %[[root_pad]] [label %[[fr_catch:.+]]] unwind label %cleanup + +fr.catch: + %fr.cp = catchpad within %fr.cs [] + unreachable +; CHECK: [[fr_catch]]: +; CHECK-NEXT: %[[fr_cp:.+]] = catchpad within %[[fr_cs]] [] +; CHECK-NEXT: unreachable + +unreach: + unreachable +; CHECK: [[unreach]]: +; CHECK-NEXT: unreachable + +exit: + ret void +} + + +;;; Test with a no-info funclet (right) which has a cousin (left.left) that +;;; unwinds to another cousin (left.right); make sure we don't trip over this +;;; when propagating unwind destination info to "right". +;;; CHECK-LABEL: define void @test7( +define void @test7() personality void()* @ProcessCLRException { +entry: +; CHECK-NEXT: entry: + invoke void @test7_inlinee() + to label %exit unwind label %cleanup +cleanup: + %pad = cleanuppad within none [] + call void @g() [ "funclet"(token %pad) ] + cleanupret from %pad unwind to caller +exit: + ret void +} + +define void @test7_inlinee() alwaysinline personality void ()* @ProcessCLRException { +entry: + invoke void @g() + to label %exit unwind label %root +; CHECK-NEXT: invoke void @g() +; CHECK-NEXT: unwind label %[[root:.+]] + +root: + %root.cp = cleanuppad within none [] + invoke void @g() [ "funclet"(token %root.cp) ] + to label %root.cont unwind label %child +; CHECK: [[root]]: +; CHECK-NEXT: %[[root_cp:.+]] = cleanuppad within none [] +; CHECK-NEXT: invoke void @g() [ "funclet"(token %[[root_cp]]) ] +; CHECK-NEXT: to label %[[root_cont:.+]] unwind label %[[child:.+]] + +root.cont: + cleanupret from %root.cp unwind to caller +; CHECK: [[root_cont]]: +; CHECK-NEXT: cleanupret from %[[root_cp]] unwind label %cleanup + +child: + %child.cp = cleanuppad within %root.cp [] + invoke void @g() [ "funclet"(token %child.cp) ] + to label %child.cont unwind label %left +; CHECK: [[child]]: +; CHECK-NEXT: %[[child_cp:.+]] = cleanuppad within %[[root_cp]] [] +; CHECK-NEXT: invoke void @g() [ "funclet"(token %[[child_cp]]) ] +; CHECK-NEXT: to label %[[child_cont:.+]] unwind label %[[left:.+]] + +left: + %left.cp = cleanuppad within %child.cp [] + invoke void @g() [ "funclet"(token %left.cp) ] + to label %left.cont unwind label %left.left +; CHECK: [[left]]: +; CHECK-NEXT: %[[left_cp:.+]] = cleanuppad within %[[child_cp]] [] +; CHECK-NEXT: invoke void @g() [ "funclet"(token %[[left_cp]]) ] +; CHECK-NEXT: to label %[[left_cont:.+]] unwind label %[[left_left:.+]] + +left.left: + %ll.cp = cleanuppad within %left.cp [] + cleanupret from %ll.cp unwind label %left.right +; CHECK: [[left_left]]: +; CHECK-NEXT: %[[ll_cp:.+]] = cleanuppad within %[[left_cp]] [] +; CHECK-NEXT: cleanupret from %[[ll_cp]] unwind label %[[left_right:.+]] + +left.cont: + invoke void @g() [ "funclet"(token %left.cp) ] + to label %unreach unwind label %left.right +; CHECK: [[left_cont]]: +; CHECK-NEXT: invoke void @g() [ "funclet"(token %[[left_cp]]) ] +; CHECK-NEXT: to label %[[unreach:.+]] unwind label %[[left_right]] + +left.right: + %lr.cp = cleanuppad within %left.cp [] + unreachable +; CHECK: [[left_right]]: +; CHECK-NEXT: %[[lr_cp:.+]] = cleanuppad within %[[left_cp]] [] +; CHECK-NEXT: unreachable + +child.cont: + invoke void @g() [ "funclet"(token %child.cp) ] + to label %unreach unwind label %right +; CHECK: [[child_cont]]: +; CHECK-NEXT: invoke void @g() [ "funclet"(token %[[child_cp]]) ] +; CHECK-NEXT: to label %[[unreach]] unwind label %[[right:.+]] + +right: + %right.cp = cleanuppad within %child.cp [] + call void @g() [ "funclet"(token %right.cp) ] + unreachable +; CHECK: [[right]]: +; CHECK-NEXT: %[[right_cp:.+]] = cleanuppad within %[[child_cp]] +; CHECK-NEXT: invoke void @g() [ "funclet"(token %[[right_cp]]) ] +; CHECK-NEXT: to label %[[right_cont:.+]] unwind label %cleanup +; CHECK: [[right_cont]]: +; CHECK-NEXT: unreachable + +unreach: + unreachable +; CHECK: [[unreach]]: +; CHECK-NEXT: unreachable + +exit: + ret void +} declare void @ProcessCLRException() ; Make sure the logic doesn't get tripped up when the inlined invoke is ; itself within a funclet in the caller. -; CHECK-LABEL: define void @test6( -define void @test6() personality void ()* @ProcessCLRException { +; CHECK-LABEL: define void @test8( +define void @test8() personality void ()* @ProcessCLRException { entry: invoke void @g() to label %exit unwind label %callsite_parent callsite_parent: %callsite_parent.pad = cleanuppad within none [] ; CHECK: %callsite_parent.pad = cleanuppad within none - invoke void @test6_inlinee() [ "funclet"(token %callsite_parent.pad) ] + invoke void @test8_inlinee() [ "funclet"(token %callsite_parent.pad) ] to label %ret unwind label %cleanup ret: cleanupret from %callsite_parent.pad unwind label %cleanup @@ -434,7 +654,7 @@ ret void } -define void @test6_inlinee() alwaysinline personality void ()* @ProcessCLRException { +define void @test8_inlinee() alwaysinline personality void ()* @ProcessCLRException { entry: invoke void @g() to label %exit unwind label %inlinee_cleanup