This is an archive of the discontinued LLVM Phabricator instance.

LiveIntervalAnalysis: Support moving of subregister defs in handleMove
ClosedPublic

Authored by MatzeB on Apr 16 2015, 7:14 PM.

Details

Summary

If two definitions write to independent subregisters then they can be
put in any order. LiveIntervalAnalysis::handleMove() did not support
this previously because it looks like moving a definition of a vreg past
another one.

This is a modified version of a patch proposed (two years ago) by
Vincent Lejeune! This version does not touch the read-undef flags and is
extended for the case of moving a subregister def behind all uses - this
can happen for subregister defs that are completely unused.

Diff Detail

Repository
rL LLVM

Event Timeline

MatzeB updated this revision to Diff 23892.Apr 16 2015, 7:14 PM
MatzeB retitled this revision from to LiveIntervalAnalysis: Support moving of subregister defs in handleMove.
MatzeB updated this object.
MatzeB edited the test plan for this revision. (Show Details)
MatzeB added reviewers: qcolombet, atrick.
MatzeB set the repository for this revision to rL LLVM.
MatzeB added subscribers: Unknown Object (MLST), tstellarAMD.
MatzeB updated this revision to Diff 24078.Apr 20 2015, 4:47 PM

Thanks for your feedback in D9069 Tom. Your testcase exposed an issue when moving a killing use across (an unrelated) subregister def. This updated version passes your testcase.

MatzeB updated this revision to Diff 24086.Apr 20 2015, 5:56 PM

Another revision which fixes some regressions introduced by the previous revision here.

qcolombet edited edge metadata.Sep 8 2015, 4:40 PM

Hi Matthias,

You mentioned that you found and fixed several regressions. Yet, this patch does not have any test cases added. Am I correctly assuming this is because the related test cases are already in the repository?
If not, could you please add them.

You also have a couple of missing period at the end of the comments. I’ve highlighted the first few ones. Please double check.

The patch mostly LGTM, though the comments would benefits from more examples (like you did with “ where I = [xi…”). Please double check the potential overlapping issue I pointed out.

Thanks,
-Quentin

lib/CodeGen/LiveIntervalAnalysis.cpp
1016 ↗(On Diff #24086)

Period.

1033 ↗(On Diff #24086)

The phrasing does not make sense.
I am guessing we want something like:
If <…>, check <…>.
This happens <….>.

1033 ↗(On Diff #24086)

Period.

1041 ↗(On Diff #24086)

At this point, NewI must be NewIdx, right?
So, this will create an overlap from base index to reg slot, right?

What I am missing?

1077 ↗(On Diff #24086)

Period.

1089 ↗(On Diff #24086)

Period.

1096 ↗(On Diff #24086)

Period.

1099 ↗(On Diff #24086)

Period.

1099 ↗(On Diff #24086)

Assert on Next.

1175 ↗(On Diff #24086)

Period.

1230 ↗(On Diff #24086)

Period.

1233 ↗(On Diff #24086)

Period.

1240 ↗(On Diff #24086)

Period.

MatzeB added a comment.Sep 8 2015, 5:08 PM

Hi Matthias,

You mentioned that you found and fixed several regressions. Yet, this patch does not have any test cases added. Am I correctly assuming this is because the related test cases are already in the repository?
If not, could you please add them.

You also have a couple of missing period at the end of the comments. I’ve highlighted the first few ones. Please double check.

The patch mostly LGTM, though the comments would benefits from more examples (like you did with “ where I = [xi…”). Please double check the potential overlapping issue I pointed out.

Thanks,
-Quentin

This patch was part of a series of 4 related changes (see dependencies). This patch alone does not regress anything but simply introduces new capabilities to handleMove(). All patches combined regressed some existing testcases so no need for additional ones. Anyway I plan to only commit this change after the other 3 patches are reworked.

MatzeB updated this revision to Diff 41082.Nov 24 2015, 1:59 PM
MatzeB edited edge metadata.

New version which handles a case that was missed in the previous version of the patch (moving a subregister def above unrelated definitions into a lifetime hole).

atrick edited edge metadata.Nov 29 2015, 10:02 PM

I'm just commenting here, not blocking the commit.

After staring for a long time, I basically understand what you're fixing.
But I can't review your changes without critiquing the code as a whole--it's too hard to reason about.

First off--and I realize you're not in a position to fix this--the API is not general enough. A repairIntervalsInRange-like API is what's needed. The design should strive to reuse the interval construction logic, rather than stringing together a number of special cases. I imagine scanning an range of instructions rebuilding live intervals along the way, with a filter that ignores "untouched" virtual registers.

Given that we're stuck at present with a string of special cases, it's good that each case to be handled is listed in the function comment. But those comments do not specify precisely the conditions that need to be checked and aren't obvisouly associated with the implementation in the function body. At a particular point in the function, it isn't clear what assumptions are being made.

For example, these are the kind of questions I have when examining handleMoveDown:

  • What conditions are associated with cases 1-6. How can we reason about the completeness?
  • Where exactly are cases 1-6 handled inside the function body?
  • When subregisters are involved how to you know whether the moved instruction is a use or def?
  • How do you know the extended live interval should end at RegSlot? What about early clobber, dead register?

The new code that directly updates start, end, valno is too low-level in the context of handleMoveDown.

Could we have some update on this patch ?

The fix is very welcome and fixes some crash issues when changing the order of instructions several times.

Could we have some update on this patch ?

The fix is very welcome and fixes some crash issues when changing the order of instructions several times.

This is surprising, I would have expected this patch to only have an effect for http://reviews.llvm.org/D14969. Do you have out-of-tree code which reschedules independent subregister definitions? Apart from that this patch is not accepted yet, I wanted to not apply this until the rest of the subreg scheduling patches is accepted.

This is surprising, I would have expected this patch to only have an effect for http://reviews.llvm.org/D14969. Do you have out-of-tree code which reschedules independent subregister definitions? Apart from that this patch is not accepted yet, I wanted to not apply this until the rest of the subreg scheduling patches is accepted.

Improvements to http://reviews.llvm.org/D11885 needs this patch (see the part "#if 0 // To enable when handleMove fix lands").

Note that this patch doesn't solve all handleMove bug.
I have a part "// Restore old ordering (which prevents a LIS->handleMove bug)." which cannot be removed either with this patch.

This is surprising, I would have expected this patch to only have an effect for http://reviews.llvm.org/D14969. Do you have out-of-tree code which reschedules independent subregister definitions? Apart from that this patch is not accepted yet, I wanted to not apply this until the rest of the subreg scheduling patches is accepted.

Improvements to http://reviews.llvm.org/D11885 needs this patch (see the part "#if 0 // To enable when handleMove fix lands").

Note that this patch doesn't solve all handleMove bug.
I have a part "// Restore old ordering (which prevents a LIS->handleMove bug)." which cannot be removed either with this patch.

I didn't read all the code in that patch. As long as you respect all the dependencies generated by ScheduleDAGInstructions today you should not run into any situations where handleMove fails, The changes here should only be necessary if subregister definitions become independent of each other. If you still require this patch then we may have an unrelated bug in handleMove(). Would be interesting to see the liveinterval before and for a handleMove() that fails for you.

I didn't read all the code in that patch. As long as you respect all the dependencies generated by ScheduleDAGInstructions today you should not run into any situations where handleMove fails, The changes here should only be necessary if subregister definitions become independent of each other. If you still require this patch then we may have an unrelated bug in handleMove(). Would be interesting to see the liveinterval before and for a handleMove() that fails for you.

The ordering constraints of ScheduleDAGInstructions are definitely preserved.

The scheduler does make blocks of instructions, and does a first schedule such that instructions inside a block are all consecutive (handleMove is used first there).
Then the blocks order is changed, and that results in second handleMove for the final schedule.

The first problem I face is that if before the second handleMove I don't restore the original ordering, then the second handleMove will crash.
With or without your patch, it is needed.

Step 1) Order instructions by blocks
Step 1 bis) Restore old ordering
Step 2) Put final instruction order

That works with and without your patch (bis step required, else it crashes)

The second problem I face is that as improvement to the scheduler, I want it to try other strategies if the previous result was not satisfying enough.
So this becomes:
Step 1) Order instructions by blocks
Step 1 bis) Restore old ordering
Step 2) Order instructions by blocks (different blocks)
Step 2 bis) Restore old ordering
Step 3) Put final instruction order

Without your patch, Step 2 crashes. Your patch makes the whole work.
The bis steps are still required.

MatzeB updated this revision to Diff 45753.Jan 22 2016, 2:44 PM
MatzeB edited edge metadata.

New revision based on http://reviews.llvm.org/D16379 which hopefully makes the changes here more comprehensible.

qcolombet accepted this revision.Feb 10 2016, 3:02 PM
qcolombet edited edge metadata.

Hi Matthias,

LGTM.
Few nitpicks inlined.

Cheers,
-Quentin

lib/CodeGen/LiveIntervalAnalysis.cpp
1052 ↗(On Diff #45753)

s/we//

1112 ↗(On Diff #45753)

Period.

1263 ↗(On Diff #45753)

Period.

This revision is now accepted and ready to land.Feb 10 2016, 3:02 PM
This revision was automatically updated to reflect the committed changes.