This is an archive of the discontinued LLVM Phabricator instance.

Differential D24117

Fix inliner funclet unwind memoization
ClosedPublic

Authored by JosephTremoulet on Aug 31 2016, 6:50 PM.

Details

Reviewers
majnemer
Commits
rGe92e0a904239: Fix inliner funclet unwind memoization
rL280610: Fix inliner funclet unwind memoization
Summary

The inliner may need to determine where a given funclet unwinds to,
and this determination may depend on other funclets throughout the
funclet tree. The code that performs this walk in getUnwindDestToken
memoizes results to avoid redundant computations. In the case that
a funclet's unwind destination is derived from its ancestor, there's
code to walk back down the tree from the ancestor updating the memo
map of its descendants to record the unwind destination. This change
fixes that code to account for the case that some descendant has a
different unwind destination, which can happen if that unwind dest
is a descendant of the EHPad being queried and thus didn't determine
its unwind destination.

Also update test inline-funclets.ll, which is supposed to cover such
scenarios, to include a case that fails an assertion without this fix
but passes with it.

Fixes PR29151.

Diff Detail

Event Timeline

JosephTremoulet updated this revision to Diff 69942.Aug 31 2016, 6:50 PM
JosephTremoulet retitled this revision from to Fix inliner funclet unwind memoization.
JosephTremoulet updated this object.
JosephTremoulet added a reviewer: majnemer.
JosephTremoulet added a subscriber: llvm-commits.
JosephTremoulet added inline comments.Aug 31 2016, 8:26 PM
lib/Transforms/Utils/InlineFunction.cpp
423–431

Oops, I think that the continue here is right but the debug check is over-zealous -- this might be a local unwind off in some cousin of EHPad in the case that EHPad has useless ancestors. I think instead that since UselessPad's parent has no information, we can assert that the unwind dest is a sibling of UselessPad (since otherwise the exiting would have needed to propagate up to the parent). Will add testcase to verify and update.

majnemer edited edge metadata.Aug 31 2016, 9:11 PM

Thanks for working on this!

lib/Transforms/Utils/InlineFunction.cpp
413

desti -> destination?

423–431

I think I reached the same conclusion wrt a continue here.

442–444

What if UselessPad is a descendent of EHPad which we never visited in getUnwindDestTokenHelper?

majnemer added inline comments.Sep 1 2016, 12:03 AM
lib/Transforms/Utils/InlineFunction.cpp
420

What if we adopted a protocol similar to the ancestor walk? We could call getUnwindDestTokenHelper for UseLessPad before we check if something is in the MemoMap. If the MemoMap didn't have an entry for UseLessPad (or that entry was nullptr), we give it LastUselessPad. Otherwise, we continue.

JosephTremoulet updated this revision to Diff 70118.Sep 1 2016, 5:57 PM
JosephTremoulet edited edge metadata.
  • fix typo
  • fix bogus assertion, add testcase covering it
JosephTremoulet marked 3 inline comments as done.Sep 1 2016, 6:55 PM
JosephTremoulet added inline comments.
lib/Transforms/Utils/InlineFunction.cpp
413

Meant to say "dest"; fixed.

420

Assuming that "give it LastUselessPad" means "map it to UnwindDestToken", that sounds correct, but I don't see why we'd want to have getUnwindDestTokenHelper duplicate its work, especially since doing so at every link in the chain would be quadratic.

423–431

Assertion updated, testcase added.

442–444

Short answer: The set of nodes that it was necessary for getUnwindDestTokenHelper to visit in order to prove LastUselessPad useless is a superset of the nodes that are sufficient for it to prove UselessPad useless.

Long answer:
Let's say a funclet/pad/node is "useless" if neither it nor its dependents have an unwind edge that escapes it (disregarding the can't-be-trusted annotations of calls-that-aren't-invokes and unwinds-to-caller catchswitches) -- i.e. a node that getUnwindDestTokenHelper should return nullptr for.

For any useless node x, define the "witnesses" of x to be the smallest set satisfying two rules:

  • x is a witness of x
  • for any useless node y which is a witness of x, all of y's children are witnesses of x

Claim: getUnwindDestToken visited all witnesses of LastUselessPad, and put entries in MemoMap for all its non-useless witnesses.
Proof:

  1. Note that getUnwindDestTokenHelper only returns nullptr when it exhausts its worklist, and that it was called and returned nullptr for LastUselessPad, so we can assume it exhausted its worklist when called for LastUelessPad.
  1. Note that whenever getUnwindDestTokenHelper pulls a useless node off its worklist and processes it, there's no cleanupret/invoke/non-UnwindToCaller-catchswitch to find, so it will put all of that node's children on the worklist (unless there's an entry in the MemoMap mapping that node to nullptr, which only happens if a previous invocation returned nullptr for that node, in which case the previous invocation put the children on the worklsit and exhausted the worklist, so the same argument applies).
  1. Since getUnwindDestTokenHelper exhausted its worklist, and the children of each processed useless node got queued, the children of each processed useless node got processed as well.
  1. The witnesses of LastUselessPad are LastUselessPad itself (which was the first node processed by getUnwindDestTokenHelper) and the children of useless witnesses of LastUselessPad (which are processed by induction using #3 above), so all the witnesses are visited.
  1. The witnesses of LastUselessPad which are not themselves useless must have non-null MemoMap entries. Consider the path from such a pad (let's call it UsefulWitness) to the topmost self-or-descendant with an unwind edge exiting UsefulWitness.

    5a. If UsefulWitness itself has an exiting unwind edge, it would be discovered when UsefulWitness is processed (and we know it's processed by #4).

    5b. If UsefulWitness itself has no such exiting edge, its children will be queued, and since we know the worklist will be exhausted, those children will also be processed.

    5c. Since UsefulWitness is not useless, it must have some descendant with an edge that exits it, so by repeated iteration of the logic in 5a/5b, we'll process such a node. When we do process it, we'll create MemoMap entries for all exited pads, which must include UsefulWitness

qed

Now, this walk pushing UnwindDestToken down through useless nodes must visit exactly the witnesses of LastUselessPad (the structure of the walk follows the definition of witness, and from the Claim above we know that the witnesses aren't missing MemoMap entries), so UselessPad must really be useless.

Right?

majnemer added inline comments.Sep 2 2016, 8:37 AM
lib/Transforms/Utils/InlineFunction.cpp
442–444

Would that imply that if UnwindDestToken is nullptr that we can assert that the catchswitch/cleanuppad both unwind to caller? Would it also imply that if UnwindDestToken is not null that it matches the unwind destination of the catchswitch/cleanuppad?

If so, could we have asserts to that effect?

JosephTremoulet marked an inline comment as done.Sep 2 2016, 10:04 AM
JosephTremoulet added inline comments.
lib/Transforms/Utils/InlineFunction.cpp
442–444

If you're talking specifically about getting here with a UselessPad that has no entry in the MemoMap or is mapped to nullptr, then we can assume that if it is a catchswitch it's marked unwind-to-caller, that if it is a cleanuppad it has no cleanupret, and that in either case it has no invoke users, all of this regardless of the value of UnwindDestToken. Should I add assertions to that effect?

majnemer added inline comments.Sep 2 2016, 10:14 AM
lib/Transforms/Utils/InlineFunction.cpp
442–444

I think it would make it clear that it is safe to propagate UnwindDestToken downwards.

JosephTremoulet updated this revision to Diff 70260.Sep 2 2016, 6:04 PM
  • Add assertions guarding against over-propagation of unwind dest token
JosephTremoulet marked an inline comment as done.Sep 2 2016, 6:08 PM
JosephTremoulet added inline comments.
lib/Transforms/Utils/InlineFunction.cpp
442–444

I think it would make it clear that it is safe to propagate UnwindDestToken downwards.

I agree. Writing it up, I noticed that while the assert just looks at the current pad's users (avoiding the quadratic behavior of re-calling getUnwindDestTokenHelper), the fact that this walk keeps going and makes the same assertion at each level (plus the assertion that any unwind we do find targets a sibling) means that cumulatively the assertions are made throughout the tree, so I think it's pretty solid.

The one wrinkle was that when I said "in either case [UselessPad] has no invoke users", I was wrong -- what's actually true is "in either case, if UselessPad has any invoke users, they unwind to a child of UselessPad, rather than unwinding out of UselessPad"

Updated.

majnemer accepted this revision.Sep 2 2016, 10:15 PM
majnemer edited edge metadata.

LGTM, this is awesome! Thanks again!

This revision is now accepted and ready to land.Sep 2 2016, 10:15 PM
JosephTremoulet closed this revision.Sep 3 2016, 6:31 PM

Revision Contents

PathSize
lib/
Transforms/
Utils/
86 lines
test/
Transforms/
Inline/
228 lines

Diff 70260

lib/Transforms/Utils/InlineFunction.cpp

//===- InlineFunction.cpp - Code to perform function inlining -------------===// //===- InlineFunction.cpp - Code to perform function inlining -------------===//
// //
// The LLVM Compiler Infrastructure // The LLVM Compiler Infrastructure
// //
// This file is distributed under the University of Illinois Open Source // This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details. // License. See LICENSE.TXT for details.
// //
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
// //
// This file implements inlining of a function into a call site, resolving // This file implements inlining of a function into a call site, resolving
// parameters and the return value as appropriate. // parameters and the return value as appropriate.
// //
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
#include "llvm/Transforms/Utils/Cloning.h" #include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/ADT/SetVector.h" #include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h" #include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringExtras.h" #include "llvm/ADT/StringExtras.h"
#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/CallGraph.h" #include "llvm/Analysis/CallGraph.h"
#include "llvm/Analysis/CaptureTracking.h" #include "llvm/Analysis/CaptureTracking.h"
#include "llvm/Analysis/EHPersonalities.h" #include "llvm/Analysis/EHPersonalities.h"
▲ Show 20 Lines • Show All 198 Lines • ▼ Show 20 Lines if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(CurrentPad)) {
// contained an invoke which unwinds out of it, so any invoke we'd // contained an invoke which unwinds out of it, so any invoke we'd
// encounter must unwind to some child of the catch. // encounter must unwind to some child of the catch.
if (!isa<CleanupPadInst>(Child) && !isa<CatchSwitchInst>(Child)) if (!isa<CleanupPadInst>(Child) && !isa<CatchSwitchInst>(Child))
continue; continue;
Instruction *ChildPad = cast<Instruction>(Child); Instruction *ChildPad = cast<Instruction>(Child);
auto Memo = MemoMap.find(ChildPad); auto Memo = MemoMap.find(ChildPad);
if (Memo == MemoMap.end()) { 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); Worklist.push_back(ChildPad);
continue; continue;
} }
// We've already checked this child, but might have found that // We've already checked this child, but might have found that
// it offers no proof either way. // it offers no proof either way.
Value *ChildUnwindDestToken = Memo->second; Value *ChildUnwindDestToken = Memo->second;
if (!ChildUnwindDestToken) if (!ChildUnwindDestToken)
continue; continue;
▲ Show 20 Lines • Show All 121 Lines • ▼ Show 20 Lines if (UnwindDestToken)
return UnwindDestToken; return UnwindDestToken;
// No information is available for this EHPad from itself or any of its // No information is available for this EHPad from itself or any of its
// descendants. An unwind all the way out to a pad in the caller would // descendants. An unwind all the way out to a pad in the caller would
// need also to agree with the unwind dest of the parent funclet, so // need also to agree with the unwind dest of the parent funclet, so
// search up the chain to try to find a funclet with information. Put // 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. // null entries in the memo map to avoid re-processing as we go up.
MemoMap[EHPad] = nullptr; MemoMap[EHPad] = nullptr;
#ifndef NDEBUG
SmallPtrSet<Instruction *, 4> TempMemos;
TempMemos.insert(EHPad);
#endif
Instruction *LastUselessPad = EHPad; Instruction *LastUselessPad = EHPad;
Value *AncestorToken; Value *AncestorToken;
for (AncestorToken = getParentPad(EHPad); for (AncestorToken = getParentPad(EHPad);
auto *AncestorPad = dyn_cast<Instruction>(AncestorToken); auto *AncestorPad = dyn_cast<Instruction>(AncestorToken);
AncestorToken = getParentPad(AncestorToken)) { AncestorToken = getParentPad(AncestorToken)) {
// Skip over catchpads since they just follow their catchswitches. // Skip over catchpads since they just follow their catchswitches.
if (isa<CatchPadInst>(AncestorPad)) if (isa<CatchPadInst>(AncestorPad))
continue; 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]); assert(!MemoMap.count(AncestorPad) || MemoMap[AncestorPad]);
auto AncestorMemo = MemoMap.find(AncestorPad); auto AncestorMemo = MemoMap.find(AncestorPad);
if (AncestorMemo == MemoMap.end()) { if (AncestorMemo == MemoMap.end()) {
UnwindDestToken = getUnwindDestTokenHelper(AncestorPad, MemoMap); UnwindDestToken = getUnwindDestTokenHelper(AncestorPad, MemoMap);
} else { } else {
UnwindDestToken = AncestorMemo->second; UnwindDestToken = AncestorMemo->second;
} }
if (UnwindDestToken) if (UnwindDestToken)
break; break;
LastUselessPad = AncestorPad; LastUselessPad = AncestorPad;
MemoMap[LastUselessPad] = nullptr;
#ifndef NDEBUG
TempMemos.insert(LastUselessPad);
#endif
} }
// Since the whole tree under LastUselessPad has no information, it all must // We know that getUnwindDestTokenHelper was called on LastUselessPad and
// match UnwindDestToken; record that to avoid repeating the search. // 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
majnemerUnsubmitted
Done
ReplyInline Actions

desti -> destination?

majnemer: desti -> destination?
JosephTremouletAuthorUnsubmitted
Not Done
ReplyInline Actions

Meant to say "dest"; fixed.

JosephTremoulet: Meant to say "dest"; fixed.
// 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<Instruction *, 8> Worklist(1, LastUselessPad); SmallVector<Instruction *, 8> Worklist(1, LastUselessPad);
while (!Worklist.empty()) { while (!Worklist.empty()) {
Instruction *UselessPad = Worklist.pop_back_val(); Instruction *UselessPad = Worklist.pop_back_val();
majnemerUnsubmitted
Not Done
ReplyInline Actions

What if we adopted a protocol similar to the ancestor walk? We could call getUnwindDestTokenHelper for UseLessPad before we check if something is in the MemoMap. If the MemoMap didn't have an entry for UseLessPad (or that entry was nullptr), we give it LastUselessPad. Otherwise, we continue.

majnemer: What if we adopted a protocol similar to the ancestor walk? We could call…
JosephTremouletAuthorUnsubmitted
Not Done
ReplyInline Actions

Assuming that "give it LastUselessPad" means "map it to UnwindDestToken", that sounds correct, but I don't see why we'd want to have getUnwindDestTokenHelper duplicate its work, especially since doing so at every link in the chain would be quadratic.

JosephTremoulet: Assuming that "give it `LastUselessPad`" means "map it to `UnwindDestToken`", that sounds…
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;
JosephTremouletAuthorUnsubmitted
Done
ReplyInline Actions

Oops, I think that the continue here is right but the debug check is over-zealous -- this might be a local unwind off in some cousin of EHPad in the case that EHPad has useless ancestors. I think instead that since UselessPad's parent has no information, we can assert that the unwind dest is a sibling of UselessPad (since otherwise the exiting would have needed to propagate up to the parent). Will add testcase to verify and update.

JosephTremoulet: Oops, I think that the `continue` here is right but the debug check is over-zealous -- this…
majnemerUnsubmitted
Done
ReplyInline Actions

I think I reached the same conclusion wrt a continue here.

majnemer: I think I reached the same conclusion wrt a `continue` here.
JosephTremouletAuthorUnsubmitted
Not Done
ReplyInline Actions

Assertion updated, testcase added.

JosephTremoulet: Assertion updated, testcase added.
}
// 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
majnemerUnsubmitted
Not Done
ReplyInline Actions

What if UselessPad is a descendent of EHPad which we never visited in getUnwindDestTokenHelper?

majnemer: What if `UselessPad` is a descendent of `EHPad` which we never visited in…
JosephTremouletAuthorUnsubmitted
Not Done
ReplyInline Actions

Short answer: The set of nodes that it was necessary for getUnwindDestTokenHelper to visit in order to prove LastUselessPad useless is a superset of the nodes that are sufficient for it to prove UselessPad useless.

Long answer:
Let's say a funclet/pad/node is "useless" if neither it nor its dependents have an unwind edge that escapes it (disregarding the can't-be-trusted annotations of calls-that-aren't-invokes and unwinds-to-caller catchswitches) -- i.e. a node that getUnwindDestTokenHelper should return nullptr for.

For any useless node x, define the "witnesses" of x to be the smallest set satisfying two rules:

  • x is a witness of x
  • for any useless node y which is a witness of x, all of y's children are witnesses of x

Claim: getUnwindDestToken visited all witnesses of LastUselessPad, and put entries in MemoMap for all its non-useless witnesses.
Proof:

  1. Note that getUnwindDestTokenHelper only returns nullptr when it exhausts its worklist, and that it was called and returned nullptr for LastUselessPad, so we can assume it exhausted its worklist when called for LastUelessPad.
  1. Note that whenever getUnwindDestTokenHelper pulls a useless node off its worklist and processes it, there's no cleanupret/invoke/non-UnwindToCaller-catchswitch to find, so it will put all of that node's children on the worklist (unless there's an entry in the MemoMap mapping that node to nullptr, which only happens if a previous invocation returned nullptr for that node, in which case the previous invocation put the children on the worklsit and exhausted the worklist, so the same argument applies).
  1. Since getUnwindDestTokenHelper exhausted its worklist, and the children of each processed useless node got queued, the children of each processed useless node got processed as well.
  1. The witnesses of LastUselessPad are LastUselessPad itself (which was the first node processed by getUnwindDestTokenHelper) and the children of useless witnesses of LastUselessPad (which are processed by induction using #3 above), so all the witnesses are visited.
  1. The witnesses of LastUselessPad which are not themselves useless must have non-null MemoMap entries. Consider the path from such a pad (let's call it UsefulWitness) to the topmost self-or-descendant with an unwind edge exiting UsefulWitness.

    5a. If UsefulWitness itself has an exiting unwind edge, it would be discovered when UsefulWitness is processed (and we know it's processed by #4).

    5b. If UsefulWitness itself has no such exiting edge, its children will be queued, and since we know the worklist will be exhausted, those children will also be processed.

    5c. Since UsefulWitness is not useless, it must have some descendant with an edge that exits it, so by repeated iteration of the logic in 5a/5b, we'll process such a node. When we do process it, we'll create MemoMap entries for all exited pads, which must include UsefulWitness

qed

Now, this walk pushing UnwindDestToken down through useless nodes must visit exactly the witnesses of LastUselessPad (the structure of the walk follows the definition of witness, and from the Claim above we know that the witnesses aren't missing MemoMap entries), so UselessPad must really be useless.

Right?

JosephTremoulet: Short answer: The set of nodes that it was necessary for `getUnwindDestTokenHelper` to visit in…
majnemerUnsubmitted
Done
ReplyInline Actions

Would that imply that if UnwindDestToken is nullptr that we can assert that the catchswitch/cleanuppad both unwind to caller? Would it also imply that if UnwindDestToken is not null that it matches the unwind destination of the catchswitch/cleanuppad?

If so, could we have asserts to that effect?

majnemer: Would that imply that if `UnwindDestToken` is `nullptr` that we can assert that the…
JosephTremouletAuthorUnsubmitted
Not Done
ReplyInline Actions

If you're talking specifically about getting here with a UselessPad that has no entry in the MemoMap or is mapped to nullptr, then we can assume that if it is a catchswitch it's marked unwind-to-caller, that if it is a cleanuppad it has no cleanupret, and that in either case it has no invoke users, all of this regardless of the value of UnwindDestToken. Should I add assertions to that effect?

JosephTremoulet: If you're talking specifically about getting here with a `UselessPad` that has no entry in the…
majnemerUnsubmitted
Not Done
ReplyInline Actions

I think it would make it clear that it is safe to propagate UnwindDestToken downwards.

majnemer: I think it would make it clear that it is safe to propagate `UnwindDestToken` downwards.
JosephTremouletAuthorUnsubmitted
Not Done
ReplyInline Actions

I think it would make it clear that it is safe to propagate UnwindDestToken downwards.

I agree. Writing it up, I noticed that while the assert just looks at the current pad's users (avoiding the quadratic behavior of re-calling getUnwindDestTokenHelper), the fact that this walk keeps going and makes the same assertion at each level (plus the assertion that any unwind we do find targets a sibling) means that cumulatively the assertions are made throughout the tree, so I think it's pretty solid.

The one wrinkle was that when I said "in either case [UselessPad] has no invoke users", I was wrong -- what's actually true is "in either case, if UselessPad has any invoke users, they unwind to a child of UselessPad, rather than unwinding out of UselessPad"

Updated.

JosephTremoulet: > I think it would make it clear that it is safe to propagate UnwindDestToken downwards. I…
// (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; MemoMap[UselessPad] = UnwindDestToken;
if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(UselessPad)) { if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(UselessPad)) {
for (BasicBlock *HandlerBlock : CatchSwitch->handlers()) assert(CatchSwitch->getUnwindDest() == nullptr && "Expected useless pad");
for (User *U : HandlerBlock->getFirstNonPHI()->users()) for (BasicBlock *HandlerBlock : CatchSwitch->handlers()) {
auto *CatchPad = HandlerBlock->getFirstNonPHI();
for (User *U : CatchPad->users()) {
assert(
(!isa<InvokeInst>(U) ||
(getParentPad(
cast<InvokeInst>(U)->getUnwindDest()->getFirstNonPHI()) ==
CatchPad)) &&
"Expected useless pad");
if (isa<CatchSwitchInst>(U) || isa<CleanupPadInst>(U)) if (isa<CatchSwitchInst>(U) || isa<CleanupPadInst>(U))
Worklist.push_back(cast<Instruction>(U)); Worklist.push_back(cast<Instruction>(U));
}
}
} else { } else {
assert(isa<CleanupPadInst>(UselessPad)); assert(isa<CleanupPadInst>(UselessPad));
for (User *U : UselessPad->users()) for (User *U : UselessPad->users()) {
assert(!isa<CleanupReturnInst>(U) && "Expected useless pad");
assert((!isa<InvokeInst>(U) ||
(getParentPad(
cast<InvokeInst>(U)->getUnwindDest()->getFirstNonPHI()) ==
UselessPad)) &&
"Expected useless pad");
if (isa<CatchSwitchInst>(U) || isa<CleanupPadInst>(U)) if (isa<CatchSwitchInst>(U) || isa<CleanupPadInst>(U))
Worklist.push_back(cast<Instruction>(U)); Worklist.push_back(cast<Instruction>(U));
} }
} }
}
return UnwindDestToken; return UnwindDestToken;
} }
/// When we inline a basic block into an invoke, /// When we inline a basic block into an invoke,
/// we have to turn all of the calls that can throw into invokes. /// we have to turn all of the calls that can throw into invokes.
/// This function analyze BB to see if there are any calls, and if so, /// This function analyze BB to see if there are any calls, and if so,
/// it rewrites them to be invokes that jump to InvokeDest and fills in the PHI /// it rewrites them to be invokes that jump to InvokeDest and fills in the PHI
▲ Show 20 Lines • Show All 1,737 Lines • Show Last 20 Lines

test/Transforms/Inline/inline-funclets.ll

Show First 20 Lines • Show All 403 Lines • ▼ Show 20 Lines
; CHECK-NEXT: cleanupret from %[[internal_pad]] unwind label %cleanup{{$}} ; CHECK-NEXT: cleanupret from %[[internal_pad]] unwind label %cleanup{{$}}
unreachable: unreachable:
unreachable unreachable
exit: exit:
ret void 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() declare void @ProcessCLRException()
; Make sure the logic doesn't get tripped up when the inlined invoke is ; Make sure the logic doesn't get tripped up when the inlined invoke is
; itself within a funclet in the caller. ; itself within a funclet in the caller.
; CHECK-LABEL: define void @test6( ; CHECK-LABEL: define void @test8(
define void @test6() personality void ()* @ProcessCLRException { define void @test8() personality void ()* @ProcessCLRException {
entry: entry:
invoke void @g() invoke void @g()
to label %exit unwind label %callsite_parent to label %exit unwind label %callsite_parent
callsite_parent: callsite_parent:
%callsite_parent.pad = cleanuppad within none [] %callsite_parent.pad = cleanuppad within none []
; CHECK: %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 to label %ret unwind label %cleanup
ret: ret:
cleanupret from %callsite_parent.pad unwind label %cleanup cleanupret from %callsite_parent.pad unwind label %cleanup
cleanup: cleanup:
%pad = cleanuppad within none [] %pad = cleanuppad within none []
call void @g() [ "funclet"(token %pad) ] call void @g() [ "funclet"(token %pad) ]
cleanupret from %pad unwind to caller cleanupret from %pad unwind to caller
exit: exit:
ret void ret void
} }
define void @test6_inlinee() alwaysinline personality void ()* @ProcessCLRException { define void @test8_inlinee() alwaysinline personality void ()* @ProcessCLRException {
entry: entry:
invoke void @g() invoke void @g()
to label %exit unwind label %inlinee_cleanup to label %exit unwind label %inlinee_cleanup
; CHECK-NEXT: invoke void @g() [ "funclet"(token %callsite_parent.pad) ] ; CHECK-NEXT: invoke void @g() [ "funclet"(token %callsite_parent.pad) ]
; CHECK-NEXT: unwind label %[[inlinee_cleanup:.+]] ; CHECK-NEXT: unwind label %[[inlinee_cleanup:.+]]
inlinee_cleanup: inlinee_cleanup:
%inlinee.pad = cleanuppad within none [] %inlinee.pad = cleanuppad within none []
Show All 10 Lines