Page MenuHomePhabricator

[WinEH] Fix mutli-parent cloning
ClosedPublic

Authored by andrew.w.kaylor on Nov 6 2015, 10:38 AM.

Details

Summary

This fixes the bug in the earlier multi-parent cloning implementation that was leading to non-deterministic (and incorrect) output.

The problem is that while updating sibling-to-sibling unwind edges for cloned funclets, the code to handle invokes was attempting to walk the unwind edges of the cloned funclets. As a result, it was likely to walk the catch-to-catch unwind chain before that chain was properly updated. This change just creates a second loop in updateSiblingToSiblingUnwind() so that the invoke processing happens after all of the other unwind edges are updated.

I've included just the changes since the previously committed revision (as reviewed in D13274), but since that commit has been reverted, I will be committing the previous change set in addition to these modifications when the review is complete.

Diff Detail

Repository
rL LLVM

Event Timeline

andrew.w.kaylor retitled this revision from to [WinEH] Fix mutli-parent cloning.
andrew.w.kaylor updated this object.
andrew.w.kaylor set the repository for this revision to rL LLVM.
andrew.w.kaylor added a subscriber: llvm-commits.
JosephTremoulet accepted this revision.Nov 6 2015, 12:03 PM
JosephTremoulet edited edge metadata.

lgtm

This revision is now accepted and ready to land.Nov 6 2015, 12:03 PM

This still doesn't fix everything. There's a problem with the block ordering of cloned catch end pads.

The code that I added to cloneCommonBlocks for catchendpad handling finds the catchpad that unwinds to the catchendpad and assigns the catchendpad the color of that catchpad's first parent. I said in the comment that it didn't matter if the catchpad had multiple parents because we'd clone it later if it did. That's not quite true. When we clone the block later, we use its color to figure out whether to give the new catchend pad to the clone parent or the original funclet's parent. So the color we gave it in cloneCommonBlocks determines which parent funclet gets the clone and that, in turn, determines whether or not the unwind edge is removed as implausible.

For instance, test15 in wineh-multi-parent-cloning.ll has this form (with a bunch of stuff omitted):

define void @test15() personality i32 (...)* @__CxxFrameHandler3 {
left:
left.end:
  catchendpad unwind to caller
right:
right.end:
  catchendpad unwind label %left.end
inner:
  catchpad []
inner.end:
  catchendpad unwind label %left.end
}

Here %left and %right are both parents of %inner. When we see %inner.end in cloneCommonBlocks() we can set its color to either %left or %right. FuncletParents maps to a vector, trying to normalize the order of traversal, but the order is actually based on the order of the BlockColors assigned to %inner by colorFunclets.

So we set the color of %inner.end to either %left or %right. When we do the cloning, if we made it %left, it comes out like this:

inner:
  catchpad []
inner.from.right:
  catchpad []
inner.end:
  catchendpad unwind label %left.end
inner.end.from.right
  catchendpad unwind to caller

but if we made it %right, it comes out like this:

inner:
  catchpad []
inner.from.right:
  catchpad []
inner.end:
  catchendpad unwind to caller
inner.end.from.left
  catchendpad unwind label %left.end

Basically, I think I need to make the BlockColors value type a vector too.

andrew.w.kaylor edited edge metadata.

Rebasing and incorporating the previously reverted changes to establish a better baseline for the next update (which will address another determinism issue).

This fixes the additional problems with determinism. I had to change the BlockColors value type (container) from a std::set to a SetVector. I don't think that should be a problem given the expected size of the sets involved.

Looks good to me.

change the BlockColors value type (container) from a std::set to a SetVector. I don't think that should be a problem given the expected size of the sets involved

I agree. It's maybe too bad we don't have a SmallSetVector that just uses a vector when small like a SmallSet but allows deterministic iteration when large like a SetVector. (not trying to suggest you stop to add such a thing for this lone use case, just thinking "out loud"...)

This revision was automatically updated to reflect the committed changes.

Hi Andy,

The change from std::set to SetVector gains stable iteration order but
loses stable iterators...
Specifically, it invalidates BlockColors[BB].end() after every remove(), so
it should not be cached in the End variable. Even if we solve this by
testing It != BlockColors[BB].end(), after removing the last item 'It' will
be at the (new after removal) end()+1 and then compared to the (new after
removal) end() which is probably undefined behaviour for an iterator.
Finally, erasing items in a loop in a SetVector is quadratic complexity.

To solve all at once, we could split the loop into two steps:

for (BasicBlock *ContainingFunclet : BlockColors[BB])
  if (ContainingFunclet != CorrectColor)
    FuncletBlocks[ContainingFunclet].erase(BB);
BlockColors[BB].remove_if([&](BasicBlock *ContainingFunclet) {
  return ContainingFunclet != CorrectColor;
});

Please feel free to modify the attached patch and commit,

Yaron

Thanks, Yaron.

This change looks good to me. I didn’t get to it earlier, and I don’t want to commit it now in case it this late in the day, but I’ll commit this first thing tomorrow.

-Andy

From: Yaron Keren [mailto:yaron.keren@gmail.com]
Sent: Wednesday, November 11, 2015 9:03 AM
To: reviews+D14454+public+ed63114aca7e347a@reviews.llvm.org; Phabricator <reviews@reviews.llvm.org>
Cc: Kaylor, Andrew <andrew.kaylor@intel.com>; Reid Kleckner <rnk@google.com>; David Majnemer <david.majnemer@gmail.com>; jotrem@microsoft.com; llvm-commits <llvm-commits@lists.llvm.org>
Subject: Re: [PATCH] D14454: [WinEH] Fix mutli-parent cloning

Hi Andy,

The change from std::set to SetVector gains stable iteration order but loses stable iterators...
Specifically, it invalidates BlockColors[BB].end() after every remove(), so it should not be cached in the End variable. Even if we solve this by testing It != BlockColors[BB].end(), after removing the last item 'It' will be at the (new after removal) end()+1 and then compared to the (new after removal) end() which is probably undefined behaviour for an iterator. Finally, erasing items in a loop in a SetVector is quadratic complexity.

To solve all at once, we could split the loop into two steps:

for (BasicBlock *ContainingFunclet : BlockColors[BB])
  if (ContainingFunclet != CorrectColor)
    FuncletBlocks[ContainingFunclet].erase(BB);
BlockColors[BB].remove_if([&](BasicBlock *ContainingFunclet) {
  return ContainingFunclet != CorrectColor;
});

Please feel free to modify the attached patch and commit,

Yaron