• mtrofin's avatar
    [turbofan] Greedy allocator refactoring. · 1cd60451
    mtrofin authored
    Separated core greedy allocator concepts, exposing the APIs we would want to continue working with. In particular, this change completely reworks CoalescedLiveRanges to reflect the fact that we expect more than one possible conflict, scrapping the initial design of the structure. Since this is a critical part of the design, this change may be thought of as a full rewrite of the algorithm.
    
    Reduced all heuristics to just 2 essential ones: split "somewhere", which we'll still need when all other heuristics fail; and spill.
    
    Introduced a simple primitive for splitting - at GapPosition::START. The goal is to use such primitives to quickly and reliably author heuristics.
    
    I expected this primitive to "just work" for any arbitrary instruction index within a live range - e.g. its middle. That's not the case, it seems to upset execution in certain scenarios. Restricting to either before/after use positions seems to work. I'm still investigating what the source of failures is in the case of "arbitrary instruction in the range" case.
    
    I intended to document the rationale and prove the soundness of always using START for splits, but I will postpone to after this last remaining issue is resolved.
    
    Review URL: https://codereview.chromium.org/1205173002
    
    Cr-Commit-Position: refs/heads/master@{#29352}
    1cd60451
coalesced-live-ranges.cc 4.89 KB