Page MenuHomePhabricator

[RegisterCoalescer] Only look at main ranges in valuesIdentical/followCopyChain
Needs ReviewPublic

Authored by tpr on Sep 13 2018, 2:41 PM.

Details

Summary

valuesIdentical is called to determine whether a def can be considered
an "identical erase" because following copy chains proves that the value
being copied is the same value as the value of the other register.

The tests show up problems where the main range decides that a def is
an "identical erase" but a subrange disagrees, because following the
copy chain leads to a def that does not define all subregs in the
subrange (in the case of one test) or a different def to that found in
the main range (in the case of the other test).

The fix here is to only detect an "identical erase" in the main range.
If it is found, it is automatically inherited by the corresponding def
in any subrange, without further analysis of that subrange value.

This fix supersedes D49535/rL338070 and D51848.

Change-Id: I059b5b2273ed6f186d134b98c118fef0494e02f8

Diff Detail

Event Timeline

tpr created this revision.Sep 13 2018, 2:41 PM

Hi,

The fix here is to only detect an "identical erase" in the main range.

Conceptually, the fix doesn't make sense to me.
If one of the subrange disagrees, wouldn't that mean the main live-range is not an identical erase?

Cheers,
-Quentin

tpr added a comment.Sep 15 2018, 10:00 AM

Hi Quentin

Firstly, it seems I now do not have a test case for this. The test that previously failed with the D51848 fix but passed with this fix now seems to pass all the time. I don't know what changed.

Anyway, the situation I used to have with that test was something like this:

100B %23:sub0 = ...
110B %23:sub1 = ...
120B %23:sub2 = ...
130B %42 = COPY %23
140B %51 = COPY %23

Are %42:130r and %51:140r identical?

In the main range, following the copy chain for both ends up at the 120r def of %23, so the values are identical. Now suppose that (due to other code) one of %42 or %51 has a subrange that is L00000003. Trying to follow the copy chain for either %42 or %51 in L00000003 ends up at 100r for sub0 or 110r for sub1. The old code before %D49535 arbitrarily chose whichever one it found first in the subranges, which is bad.

With D49535, as fixed by D51848, it wants to find the same def for each subrange of %23 that contributes to L00000003, and it fails because it finds 100r and 110r.

Now, this probably could be fixed by something like followCopyChain returning what lanes it found a def in, and then valuesIdentical spotting that it didn't get all the lanes it wanted and retrying with the remaining ones, and coping with that being different.

But I still believe that trying to spot the identical case in subranges is pointless because we have already proved that the values are identical in main ranges. It is impossible for the values to be not identical in subranges; it's just a bit tricky to fix up the code to demonstrate that.

So (if one accepts that argument) I guess the two options are:

  1. land this anyway instead of D51848, even though there is currently no test that fails on D51848 but passes with this fix (we still have the test from D51848 that fails if you have neither fix); or
  1. land D51848 for now, and revisit this fix if I find a test that still fails for this reason later on.

What do you think?

But I still believe that trying to spot the identical case in subranges is pointless because we have already proved that the values are identical in main ranges. It is impossible for the values to be not identical in subranges; it's just a bit tricky to fix up the code to demonstrate that.

Essentially what you're saying is that the live-ranges are the same at the main live-range level but we fail to prove it at the subrange level.

What would happen in a situation like this:

100B %23:sub0 = ...
110B %23:sub1 = ...
120B %23:sub2 = ...
130B %42 = COPY %23
135B %23:sub2 = ... <-- redefine only a sublane
140B %51 = COPY %23

In particular, are the main live-range correctly identified as being different?

Basically, I am trying to check that we do prove that the main live-range are indeed identical (i.e., that part "we have already proved that the values are identical in main ranges.").

Cheers,
-Quentin