Page MenuHomePhabricator

[HotColdSplitting] Ensure PHIs have unique incoming values
AbandonedPublic

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

Details

Summary

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 llvm.org/PR39564, rdar://45718012.

Depends on https://reviews.llvm.org/D53887.

Diff Detail

Event Timeline

vsk created this revision.Nov 6 2018, 4:33 PM
hiraditya added inline comments.Nov 6 2018, 5:03 PM
llvm/lib/Transforms/IPO/HotColdSplitting.cpp
406

Can we outline this function to have better readability?

416

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
llvm/lib/Transforms/IPO/HotColdSplitting.cpp
416

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:

foo:
  %sink = ...
  br label %bar
bar:
  br label %baz
vsk added inline comments.Nov 6 2018, 5:20 PM
llvm/lib/Transforms/IPO/HotColdSplitting.cpp
416

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

foo:
  %sink = ...
  br label %bar
bar:
  %phi = phi [ 0, %p1 ], [ 1, %p2 ]
  br i1 undef, label %p1, label %p2
p1:
  br i1 undef, label %bar, %p1
p2:
  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.
llvm/lib/Transforms/IPO/HotColdSplitting.cpp
416

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
llvm/lib/Transforms/IPO/HotColdSplitting.cpp
416

:)

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 llvm.org/PR39671. 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 https://reviews.llvm.org/D53887 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 https://reviews.llvm.org/D55018, 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.