Page MenuHomePhabricator

SplitKit: Fix liveness recomputation in some remat cases.
ClosedPublic

Authored by MatzeB on Jan 29 2018, 3:30 PM.

Details

Summary

Example situation:

BB0:
  %0 = ...
  use %0
  ; ...
  condjump BB1
  jmp BB2

BB1:
  %0 = ...   ; rematerialized def from above (from earlier split step)
  jmp BB2

BB2:
  ; ...
  use %0

%0 has a live interval with 3 value numbers (for the BB0, BB1 and
BB2 parts). Now SplitKit tries to rematerialize the value in BB2 before the use.
This can succeed if this is actually a secondary split
SplitKit can still trace it all back to a single original definition.

In case of rematerialization live ranges may become shorter and need to be recomputed.
The case that we missed before is that when the value
that is rematerialized is at a join (Phi VNI) then we also have to
recompute liveness for the predecessor VNIs.

Do you guys want a 500kb testcase (that is the size after reducing it with bugpoint) in the repository for this?

Diff Detail

Repository
rL LLVM

Event Timeline

MatzeB created this revision.Jan 29 2018, 3:30 PM
wmi added a comment.Jan 30 2018, 2:22 PM

Do you guys want a 500kb testcase (that is the size after reducing it with bugpoint) in the repository for this?

Maybe you can catch a smaller testcase by adding assert(0 && "catch a testcase") before SplitKit.cpp:1460 and then use credue to reduce the testcase? I tried that and got a 4k .ll test, and you may get a even smaller one.

This looks ok to me, just a couple of nitpicks.

lib/CodeGen/SplitKit.cpp
1458 ↗(On Diff #131888)

In the text of the assertion, should it be "value not available..."? Also there is no variable PhiVNI.

1462 ↗(On Diff #131888)

Missing space between while and (.

MatzeB added inline comments.Feb 1 2018, 10:41 AM
lib/CodeGen/SplitKit.cpp
1458 ↗(On Diff #131888)

Even though most people write an error message here that should be displayed when the assert fails.

My personal aesthetics really want me to read an assert as:
"assert that ...".

From that perspective I rather state the condition that needs to be true (in this case the value must be available in the predecessor). You are right in that I should write "VNI" instead of "PhiVNI" here. I'll change the text to "value must be available in VNI predecessor".

qcolombet accepted this revision.Feb 1 2018, 10:48 AM

LGTM with the nitpicks mentioned by Krzysztof.

Also, any luck with reducing the test case even more?

Although Wei's method may not reproduce the observed effect, it will still exercise the new code and potentially the final live-ranges are verifiable (as without this patch the verifier would have complained)

This revision is now accepted and ready to land.Feb 1 2018, 10:48 AM
qcolombet added inline comments.Feb 1 2018, 11:08 AM
lib/CodeGen/SplitKit.cpp
1458 ↗(On Diff #131888)

FWIW, the coding standard says to put error message:
To further assist with debugging, make sure to put some kind of error message in the assertion statement, which is printed if the assertion is tripped.

http://www.llvm.org/docs/CodingStandards.html#assert-liberally

Therefore, I would second Krzysztof here.

MatzeB added a comment.Feb 1 2018, 3:36 PM

Nice trick wmi, I tried it and could create a very small testcase that would hit the problematic code in question. Unfortunately those small inputs would not fail in -verify-machineinstrs mode without this patch (I suspect the liveranges didn't happen to actually be invalid even though we ignored the fact that PHIs can have inputs).

So I instead I manually beat against the test for multiple hours now and reduced it to 245 which should be good enough to check in.

This revision was automatically updated to reflect the committed changes.