Page MenuHomePhabricator

[SimpleLoopUnswitch] Do not delete DT edge when a duplicate exists.
AbandonedPublic

Authored by asbirlea on Apr 6 2020, 7:01 PM.

Details

Reviewers
chandlerc
uabelho
Summary

For the unswitched blocks that were split, there may be a duplicate edge
that was kept. Check this when updating the DominatorTree.
Resolves PR45355.

Diff Detail

Unit TestsFailed

TimeTest
170 mslldb-unit.Host/_/HostTests::ConnectionFileDescriptorTest.TCPGetURIv6
Note: Google Test filter = ConnectionFileDescriptorTest.TCPGetURIv6 [==========] Running 1 test from 1 test case. [----------] Global test environment set-up.

Event Timeline

asbirlea created this revision.Apr 6 2020, 7:01 PM
Herald added a project: Restricted Project. · View Herald TranscriptApr 6 2020, 7:01 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
asbirlea updated this revision to Diff 255566.Apr 6 2020, 7:05 PM

Nit in test.

I don't really know this code but at least the fix avoids the crash I saw. Thanks!

uabelho accepted this revision.Apr 15 2020, 11:19 PM

I've run quite a number of tests with this without problems.

This revision is now accepted and ready to land.Apr 15 2020, 11:19 PM
asbirlea planned changes to this revision.Apr 16 2020, 12:11 AM

While this solution does solve the problem, there's an underlying bug that this is hiding. I've talking with Chandler about this and I'll send a couple of patches that are aiming to fix the underlying problem instead.
Apologies for the delay in getting you a fix.

While this solution does solve the problem, there's an underlying bug that this is hiding. I've talking with Chandler about this and I'll send a couple of patches that are aiming to fix the underlying problem instead.
Apologies for the delay in getting you a fix.

Sounds good!

chandlerc added inline comments.Apr 21 2020, 7:22 PM
llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
830

(mostly summarizing our video chat discussion for the list and so I don't forget it)

The raw llvm::successors API is somewhat inefficient (switches over the instruction op-code).... And no matter what, this ends up being quadratic in the weird edge case where we unswitch half of the edges. For each unswitched edge that we split we'll walk every not-unswitched edge here.

But all of this I think is unnecessary. We shouldn't ever be leaving edges from the *switch instruction* to a basic block that we are unswitching. The split case is only intended to cover when there are edges to the basic block from other parts of the loop.

The way you get here is really fun: it uses a basic block ending in unreachable. Such blocks are special cased above in this routine, but only for the *default* destination. That's how we end up with there still being an edge: its the default edge to an unreachable-terminated block where we unswitch a case edge to that block.

So I think we need to make the handling of unreachable-terminated blocks uniform between defaults and cases, even though we don't *need* to special case them for cases (because we can delete cases entirely). Otherwise we will keep having surprises where they behave differently here.

But to do that, I think we need to *narrow* the special case significantly: currently it just checks that the block is terminated by unreachable. I think it should *also* ensure that is the only instruction in the block. For all such exiting edges of the loop, we don't need to both unswitching them. Notably, the case edges should be cleaned up by SimplifyCFG by deleting them, so there is no real need to do anything here IMO.

So I think that leaves two steps here:

  1. Narrow the special case to blocks containing *just* unreachable.
  2. Apply in consistently to cases as well as the default destination.

I'm fine to do it in a single patch if it isn't too disruptive. Or we can do something vaguely similar to this patch as a temporary workaround that is easier to backport and then do #1 and #2 in to follow-up patches and remove the workaround.

asbirlea marked an inline comment as done.Apr 21 2020, 10:42 PM
asbirlea added inline comments.
llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
830

Thanks a lot for the summary, this is great to have in writing!

I sent out D78277 and D78279 last week as a replacement for this patch. My apologies for forgetting to update the discussion here.

asbirlea abandoned this revision.Thu, May 7, 1:55 PM

Superseded by D78277 and D78279.