[turbofan] Separate LiveRange and TopLevelLiveRange concepts
authormtrofin <mtrofin@chromium.org>
Wed, 26 Aug 2015 05:22:22 +0000 (22:22 -0700)
committerCommit bot <commit-bot@chromium.org>
Wed, 26 Aug 2015 05:22:36 +0000 (05:22 +0000)
commit0ee4b473681f3059a3da303ceb6fe23eef37aed3
treed9bff758bf76b8a5b24a233e10e940d4aed0e873
parent268420af847e5edb5c8114ad7d8c20770cb16461
[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)

Review URL: https://codereview.chromium.org/1311983002

Cr-Commit-Position: refs/heads/master@{#30370}
src/compiler/graph-visualizer.cc
src/compiler/greedy-allocator.cc
src/compiler/live-range-separator.cc
src/compiler/register-allocator.cc
src/compiler/register-allocator.h
test/unittests/compiler/coalesced-live-ranges-unittest.cc