• mtrofin's avatar
    [turbofan] Separate LiveRange and TopLevelLiveRange concepts · 0ee4b473
    mtrofin authored
    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}
    0ee4b473
register-allocator.h 35 KB