Page MenuHomePhabricator

[HotColdSplitting] Ensure PHIs have unique incoming values

Authored by vsk on Nov 6 2018, 4:33 PM.



Do not add a block to the outlining region if doing so would mean that
a PHI outside of the region would have incompatible incoming values from
the code replacer block.

Test case by Jun Bum Lim!

Fixes, rdar://45718012.

Depends on

Diff Detail

Event Timeline

vsk created this revision.Nov 6 2018, 4:33 PM
hiraditya added inline comments.Nov 6 2018, 5:03 PM

Can we outline this function to have better readability?


When can we have a case where PHI does not have incoming value from immediate predecessor?

vsk added inline comments.Nov 6 2018, 5:14 PM

When the successor block has no uses of values defined in the predecessor. A special case of this is when the successor block just contains a terminator:

  %sink = ...
  br label %bar
  br label %baz
vsk added inline comments.Nov 6 2018, 5:20 PM

Sorry, that example is incorrect because there isn't a phi there at all. How about:

  %sink = ...
  br label %bar
  %phi = phi [ 0, %p1 ], [ 1, %p2 ]
  br i1 undef, label %p1, label %p2
  br i1 undef, label %bar, %p1
  br i1 undef, label %bar, %p2

I think foo dominates bar here, but bar has a phi without an incoming value from foo.

vsk updated this revision to Diff 172996.Nov 7 2018, 11:52 AM
vsk marked 4 inline comments as done.
  • Address review feedback from Aditya.

No, my example is wrong again. A phi has to have an incoming value from each of its parent's predecessor blocks.

vsk updated this revision to Diff 173039.Nov 7 2018, 2:48 PM
  • Do not add duplicate blocks to the outlining region. The test for this is 'forward-dfs-reaches-marked-block.ll'.
hiraditya added inline comments.Nov 13 2018, 5:42 AM


vsk added a comment.Nov 14 2018, 12:22 PM

Friendly ping.

vsk planned changes to this revision.Nov 14 2018, 4:10 PM

Actually, when I defined “IsCold” as “has more than one predecessor” to stress-test the pass, I found another instance of this assert firing while building a stage2 clang.

vsk updated this revision to Diff 175528.Nov 27 2018, 10:34 AM
  • Use an iterative approach to remove blocks from the outlining region, if they would cause PHIs outside of the region to become invalid (i.e. have more than one distinct incoming value from the codeRepl block).

This successfully builds a stage2 clang compiler, which passes the test suite without regressions. I had to disable stack coloring due to To stress the splitting pass, I replaced the definition of "unlikelyExecuted" with "BB->hasNPredecessorsOrMore(2)", and rejected outlining regions which would mark the whole function cold.

At this point, I'm confident in and this patch.

vsk added a comment.Nov 29 2018, 9:57 AM

While this patch is correct, it might make sense to abandon it in favor of, which solves the underlying issue more comprehensively.

vsk abandoned this revision.Dec 3 2018, 1:16 PM

I'll abandon this in favor of D55018 and fold some of the tests from this patch into D53887.