[turbofan] Separate LiveRange and TopLevelLiveRange concepts

[turbofan] Separate LiveRange and TopLevelLiveRange concepts

A TopLevelLiveRange is the live range of a virtual register. Through
register allocation, it may end up being split in a succession of child
live ranges, where data flow is handled through moves from
predecessor to successor child.

Today, the concepts of "top level" and "child" live ranges are conflated
under the LiveRange class. However, a good few APIs pertain solely
to TopLevelLiveRanges. This was communicated through comments or
DCHECKs - but this makes for poor code comprehensibility and maintainability.

For example, the worklist of the register allocator (live_ranges()) needs
to only contain TopLevelLiveRanges; spill range concerns are associated
only with the top range; phi-ness; certain phases in the allocation pipeline;
APIs on LiveRange used for initial construction - before splitting;
splintering - these are all responsibilities associated to TopLevelLiveRanges,
and not child live ranges.

This change separates the concepts.

An effect of this change is that child live range allocation need not involve
RegisterAllocationData. That's "a good thing" (lower coupling), but it has
the side-effect of not having a good way to construct unique identifiers for
child live ranges, relative to a given InstructionSequence.

LiveRange Id are used primarily for tracing/output-ing, and debugging.

I propose a 2-component identifier: a virtual register (vreg) number,
uniquely identifying TopLevelLiveRanges; and a relative identifier, which
uniquely identifies children of a given TopLevelLiveRange. "0" is reserved
for the TopLevel range. The relative identifier does not necessarily
indicate order in the child chain, which is no worse than the current state
of affairs.

I believe this change should make it easier to understand a trace output
(because the virtual register number is readily available). I plan to formalize
with a small structure the notion of live range id, and consolidate tracing
around that, as part of a separate CL. (there are seemingly disparate ways
to trace - printf or stream-based APIs - so this seems like an opportune
change to consolidate that)

Committed: https://crrev.com/0ee4b473681f3059a3da303ceb6fe23eef37aed3
Cr-Commit-Position: refs/heads/master@{#30370}

[Mircea Trofin, 2015-08-25 23:11:37]

Patchset #4 (id:60001) has been deleted

[Mircea Trofin, 2015-08-25 23:11:44]

Patchset #3 (id:40001) has been deleted

[Mircea Trofin, 2015-08-25 23:11:52]

Patchset #2 (id:20001) has been deleted

[Mircea Trofin, 2015-08-25 23:11:58]

Patchset #1 (id:1) has been deleted

[Mircea Trofin, 2015-08-26 00:21:44]

mtrofin@chromium.org changed reviewers:
+ bmeurer@chromium.org, jarin@chromium.org

[Benedikt Meurer, 2015-08-26 04:31:20]

LGTM with comments.

On a related note: Please make sure that your CL description lines fit within 80
characters.

https://codereview.chromium.org/1311983002/diff/80001/src/compiler/register-a...
File src/compiler/register-allocator.cc (right):

https://codereview.chromium.org/1311983002/diff/80001/src/compiler/register-a...
src/compiler/register-allocator.cc:2027: auto range =
data()->GetOrCreateLiveRangeFor(operand_index);
Nit: please deautofy this.

https://codereview.chromium.org/1311983002/diff/80001/src/compiler/register-a...
File src/compiler/register-allocator.h (right):

https://codereview.chromium.org/1311983002/diff/80001/src/compiler/register-a...
src/compiler/register-allocator.h:285: TopLevelLiveRange* TopLevel() { return
parent_; }
parent_ should be renamed to toplevel_ (or top_level_ to keep the naming in
sync).

https://codereview.chromium.org/1311983002/diff/80001/src/compiler/register-a...
src/compiler/register-allocator.h:289: return
reinterpret_cast<LiveRange*>(parent_) == this;
The reinterpret_cast is unnecessary (and dangerous) here. Just delay the
definition of this function until after the definition of TopLevelLiveRange and
everything will be fine.

[Mircea Trofin, 2015-08-26 04:59:58]

The CQ bit was checked by mtrofin@chromium.org

[Mircea Trofin, 2015-08-26 04:59:58]

The patchset sent to the CQ was uploaded after l-g-t-m from bmeurer@chromium.org
Link to the patchset: https://codereview.chromium.org/1311983002/#ps100001
(title: " ")

[commit-bot: I haz the power, 2015-08-26 05:00:09]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1311983002/100001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1311983002/100001

[Mircea Trofin, 2015-08-26 05:00:13]

Addressed feedback.

https://codereview.chromium.org/1311983002/diff/80001/src/compiler/register-a...
File src/compiler/register-allocator.cc (right):

https://codereview.chromium.org/1311983002/diff/80001/src/compiler/register-a...
src/compiler/register-allocator.cc:2027: auto range =
data()->GetOrCreateLiveRangeFor(operand_index);
On 2015/08/26 04:31:20, Benedikt Meurer wrote:
> Nit: please deautofy this.

Done.

https://codereview.chromium.org/1311983002/diff/80001/src/compiler/register-a...
File src/compiler/register-allocator.h (right):

https://codereview.chromium.org/1311983002/diff/80001/src/compiler/register-a...
src/compiler/register-allocator.h:285: TopLevelLiveRange* TopLevel() { return
parent_; }
On 2015/08/26 04:31:20, Benedikt Meurer wrote:
> parent_ should be renamed to toplevel_ (or top_level_ to keep the naming in
> sync).

Done.

https://codereview.chromium.org/1311983002/diff/80001/src/compiler/register-a...
src/compiler/register-allocator.h:289: return
reinterpret_cast<LiveRange*>(parent_) == this;
On 2015/08/26 04:31:20, Benedikt Meurer wrote:
> The reinterpret_cast is unnecessary (and dangerous) here. Just delay the
> definition of this function until after the definition of TopLevelLiveRange
and
> everything will be fine.

Done.

[commit-bot: I haz the power, 2015-08-26 05:22:29]

Committed patchset #2 (id:100001)

[commit-bot: I haz the power, 2015-08-26 05:22:46]

Patchset 2 (id:??) landed as
https://crrev.com/0ee4b473681f3059a3da303ceb6fe23eef37aed3
Cr-Commit-Position: refs/heads/master@{#30370}