[turbofan] Greedy allocator refactoring.

[turbofan] Greedy allocator refactoring.

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.

Committed: https://crrev.com/1cd60451de667199d6195b54f0ea7a1d9f206557
Cr-Commit-Position: refs/heads/master@{#29352}

[titzer, 2015-06-24 23:00:07]

titzer@chromium.org changed reviewers:
+ titzer@chromium.org

[titzer, 2015-06-24 23:00:08]

https://codereview.chromium.org/1205173002/diff/20001/src/compiler/coalesced-...
File src/compiler/coalesced-live-ranges.h (right):

https://codereview.chromium.org/1205173002/diff/20001/src/compiler/coalesced-...
src/compiler/coalesced-live-ranges.h:18: struct AllocatedRange {
WeightedLiveRange? Should be a class if it has private members.

[titzer, 2015-06-24 23:05:44]

https://codereview.chromium.org/1205173002/diff/20001/src/compiler/greedy-all...
File src/compiler/greedy-allocator.h (right):

https://codereview.chromium.org/1205173002/diff/20001/src/compiler/greedy-all...
src/compiler/greedy-allocator.h:68: void InitializeAllocations();
Why not just name the method after what it does? InsertFixedRanges()?

https://codereview.chromium.org/1205173002/diff/20001/src/compiler/greedy-all...
src/compiler/greedy-allocator.h:72: void InitializeScheduler();
Same here.

https://codereview.chromium.org/1205173002/diff/20001/src/compiler/greedy-all...
src/compiler/greedy-allocator.h:76: void HandleRangesDefinedByMemoryOperand();
"handle" is too general. Please name the method after what it does. This doesn't
return anything, so it obviously has some side effects.

https://codereview.chromium.org/1205173002/diff/20001/src/compiler/greedy-all...
src/compiler/greedy-allocator.h:78: void ProcessCandidate(const
AllocationCandidate& candidate);
What does Process mean?

https://codereview.chromium.org/1205173002/diff/20001/src/compiler/greedy-all...
src/compiler/greedy-allocator.h:86: float GetCandidateRangeWeight(LiveRange*
range, unsigned size);
Even though this is camel case (and thus CouldPerformCalculations), it might be
better to avoid naming things with the Get prefix if they compute something.

https://codereview.chromium.org/1205173002/diff/20001/src/compiler/greedy-all...
src/compiler/greedy-allocator.h:93: bool HandleSpillOperands(LiveRange* range);
Again, no idea what "Handle" means here.

[Benedikt Meurer, 2015-06-25 04:41:06]

bmeurer@chromium.org changed reviewers:
+ bmeurer@chromium.org

[Benedikt Meurer, 2015-06-25 04:41:07]

https://codereview.chromium.org/1205173002/diff/20001/src/compiler/coalesced-...
File src/compiler/coalesced-live-ranges.h (right):

https://codereview.chromium.org/1205173002/diff/20001/src/compiler/coalesced-...
src/compiler/coalesced-live-ranges.h:16: // TODO(mtrofin): we may be calculating
the weight multiple times. Consider
I'd prefer to have it on the LiveRange instead. This utility class doesn't seem
to make things easier for now.

https://codereview.chromium.org/1205173002/diff/20001/src/compiler/greedy-all...
File src/compiler/greedy-allocator.h (right):

https://codereview.chromium.org/1205173002/diff/20001/src/compiler/greedy-all...
src/compiler/greedy-allocator.h:25: }
Nit: Please add an appropriate operator> if you decide to overload operator<,
even if it's currently unused.

[Mircea Trofin, 2015-06-25 18:07:35]

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

[Mircea Trofin, 2015-06-25 23:06:23]

https://codereview.chromium.org/1205173002/diff/20001/src/compiler/coalesced-...
File src/compiler/coalesced-live-ranges.h (right):

https://codereview.chromium.org/1205173002/diff/20001/src/compiler/coalesced-...
src/compiler/coalesced-live-ranges.h:16: // TODO(mtrofin): we may be calculating
the weight multiple times. Consider
On 2015/06/25 04:41:06, Benedikt Meurer wrote:
> I'd prefer to have it on the LiveRange instead. This utility class doesn't
seem
> to make things easier for now.

Done.

https://codereview.chromium.org/1205173002/diff/20001/src/compiler/coalesced-...
src/compiler/coalesced-live-ranges.h:18: struct AllocatedRange {
On 2015/06/24 23:00:07, titzer wrote:
> WeightedLiveRange? Should be a class if it has private members.

Removed the type, by virtue of moving weight to LiveRange.

https://codereview.chromium.org/1205173002/diff/20001/src/compiler/greedy-all...
File src/compiler/greedy-allocator.h (right):

https://codereview.chromium.org/1205173002/diff/20001/src/compiler/greedy-all...
src/compiler/greedy-allocator.h:25: }
On 2015/06/25 04:41:06, Benedikt Meurer wrote:
> Nit: Please add an appropriate operator> if you decide to overload operator<,
> even if it's currently unused.

Done.

https://codereview.chromium.org/1205173002/diff/20001/src/compiler/greedy-all...
src/compiler/greedy-allocator.h:68: void InitializeAllocations();
On 2015/06/24 23:05:44, titzer wrote:
> Why not just name the method after what it does? InsertFixedRanges()?

Good suggestion. I'm proposing PreallocateFixedRanges.

https://codereview.chromium.org/1205173002/diff/20001/src/compiler/greedy-all...
src/compiler/greedy-allocator.h:72: void InitializeScheduler();
On 2015/06/24 23:05:44, titzer wrote:
> Same here.

Done.

https://codereview.chromium.org/1205173002/diff/20001/src/compiler/greedy-all...
src/compiler/greedy-allocator.h:78: void ProcessCandidate(const
AllocationCandidate& candidate);
On 2015/06/24 23:05:44, titzer wrote:
> What does Process mean?

Done.

https://codereview.chromium.org/1205173002/diff/20001/src/compiler/greedy-all...
src/compiler/greedy-allocator.h:86: float GetCandidateRangeWeight(LiveRange*
range, unsigned size);
On 2015/06/24 23:05:44, titzer wrote:
> Even though this is camel case (and thus CouldPerformCalculations), it might
be
> better to avoid naming things with the Get prefix if they compute something.

Done by virtue of having had changed a bit more on the API.

https://codereview.chromium.org/1205173002/diff/20001/src/compiler/greedy-all...
src/compiler/greedy-allocator.h:93: bool HandleSpillOperands(LiveRange* range);
On 2015/06/24 23:05:44, titzer wrote:
> Again, no idea what "Handle" means here.

Done.

https://codereview.chromium.org/1205173002/diff/40001/tools/gyp/v8.gyp
File tools/gyp/v8.gyp (right):

https://codereview.chromium.org/1205173002/diff/40001/tools/gyp/v8.gyp#newcod...
tools/gyp/v8.gyp:572: '../../src/compiler/simplified-operator-reducer.h',
I rebased before resubmitting.

[Jarin, 2015-06-29 05:25:16]

I really like this. If my nits are addressed/answered, it is good to go.

It is still not clear to me why coalesced live ranges live in a different file
(greedy-allocator.h still includes coalesced-live-ranges.h, so not compilation
time will still be mostly the same or worse), but I have only slight preference
to keep the greedy allocator in one file.

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/coalesced-...
File src/compiler/coalesced-live-ranges.cc (right):

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/coalesced-...
src/compiler/coalesced-live-ranges.cc:70: for (;
QueryIntersectsAllocatedInterval(query, conflict);) {
Why is this not a while loop?

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/greedy-all...
File src/compiler/greedy-allocator.cc (right):

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/greedy-all...
src/compiler/greedy-allocator.cc:37: auto result =
data->NewChildRangeFor(range);
auto -> LiveRange*

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/greedy-all...
src/compiler/greedy-allocator.cc:74: if (range->first_interval()->next() !=
nullptr)
Since the return is on a new line, please add the braces.

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/greedy-all...
src/compiler/greedy-allocator.cc:79: auto last = GetLastGapIndex(interval);
Replace autos with real types here and below.

auto should be only used for really long template types or if it is completely
clear what the type is (e.g., 'T x = new T()' can be written as 'auto x = new
T()' if T is a long type name).

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/greedy-all...
src/compiler/greedy-allocator.cc:107: auto ret = storage_.top();
auto -> AllocationCandidate

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/greedy-all...
src/compiler/greedy-allocator.cc:163: if (range->spilled()) continue;
Perhaps favour ordinary ifs to continues? That is, how about the loop body
below?

if (CanProcessRange(range) && !range->spilled()) {
  scheduler().Schedule(range);
}

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/greedy-all...
src/compiler/greedy-allocator.cc:197: if (range->weight() <=
max_conflict_weight) continue;
Perhaps fold this if into the next if and get rid of the continue?

I.e. something like

if (max_conflict_weight < range->weight() &&
    max_conflict_weight < smallest_weight) {
  smallest_weight = max_conflict_weight;
  evictable_reg = i;
}

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/greedy-all...
src/compiler/greedy-allocator.cc:235: auto start = range->Start();
Real type, please.

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/greedy-all...
src/compiler/greedy-allocator.cc:282: if (!CanProcessRange(range)) continue;
Get rid of the continue?

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/greedy-all...
src/compiler/greedy-allocator.cc:333: // TODO(mtrofin): replace GLRSP with the
entry point selecting heuristics,
What is GLRSP?

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/greedy-all...
src/compiler/greedy-allocator.cc:337: auto tail = Split(range, data(), pos);
auto -> LiveRange*

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/greedy-all...
File src/compiler/greedy-allocator.h (right):

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/greedy-all...
src/compiler/greedy-allocator.h:48: typedef
ZonePriorityQueue<AllocationCandidate> ScheduleStorage;
ScheduleStorage -> ScheduleQueue

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/greedy-all...
src/compiler/greedy-allocator.h:49: ScheduleStorage storage_;
storage_ -> queue_

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/greedy-all...
src/compiler/greedy-allocator.h:96: void HandleBlockedRange(LiveRange* range);
HandleBlockedRange -> SplitOrSpillBlockedRange?

[titzer, 2015-06-29 11:17:57]

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

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/register-a...
src/compiler/register-allocator.h:481: int size_;
Can you add a only liner explaining what "size" means? Even better, a more
descriptive name.
// greedy: the number of

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/register-a...
src/compiler/register-allocator.h:482: float weight_;
Is this the spill weight or the priority for allocation, or both? A comment
could help here.

[Mircea Trofin, 2015-06-29 13:19:53]

Patchset #5 (id:80001) has been deleted

[Mircea Trofin, 2015-06-29 13:20:16]

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/coalesced-...
File src/compiler/coalesced-live-ranges.cc (right):

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/coalesced-...
src/compiler/coalesced-live-ranges.cc:70: for (;
QueryIntersectsAllocatedInterval(query, conflict);) {
On 2015/06/29 05:25:15, jarin wrote:
> Why is this not a while loop?

Done.

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/greedy-all...
File src/compiler/greedy-allocator.cc (right):

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/greedy-all...
src/compiler/greedy-allocator.cc:37: auto result =
data->NewChildRangeFor(range);
On 2015/06/29 05:25:16, jarin wrote:
> auto -> LiveRange*

Done.

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/greedy-all...
src/compiler/greedy-allocator.cc:74: if (range->first_interval()->next() !=
nullptr)
On 2015/06/29 05:25:16, jarin wrote:
> Since the return is on a new line, please add the braces.

Must be the effects of git cl format; fixed.

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/greedy-all...
src/compiler/greedy-allocator.cc:79: auto last = GetLastGapIndex(interval);
On 2015/06/29 05:25:16, jarin wrote:
> Replace autos with real types here and below.
> 
> auto should be only used for really long template types or if it is completely
> clear what the type is (e.g., 'T x = new T()' can be written as 'auto x = new
> T()' if T is a long type name).

Done.

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/greedy-all...
src/compiler/greedy-allocator.cc:107: auto ret = storage_.top();
On 2015/06/29 05:25:16, jarin wrote:
> auto -> AllocationCandidate

Done.

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/greedy-all...
src/compiler/greedy-allocator.cc:163: if (range->spilled()) continue;
On 2015/06/29 05:25:16, jarin wrote:
> Perhaps favour ordinary ifs to continues? That is, how about the loop body
> below?
> 
> if (CanProcessRange(range) && !range->spilled()) {
>   scheduler().Schedule(range);
> }

Done.

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/greedy-all...
src/compiler/greedy-allocator.cc:197: if (range->weight() <=
max_conflict_weight) continue;
On 2015/06/29 05:25:16, jarin wrote:
> Perhaps fold this if into the next if and get rid of the continue?
> 
> I.e. something like
> 
> if (max_conflict_weight < range->weight() &&
>     max_conflict_weight < smallest_weight) {
>   smallest_weight = max_conflict_weight;
>   evictable_reg = i;
> }

Done.

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/greedy-all...
src/compiler/greedy-allocator.cc:235: auto start = range->Start();
On 2015/06/29 05:25:16, jarin wrote:
> Real type, please.

Done.

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/greedy-all...
src/compiler/greedy-allocator.cc:282: if (!CanProcessRange(range)) continue;
On 2015/06/29 05:25:16, jarin wrote:
> Get rid of the continue?

Done.

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/greedy-all...
src/compiler/greedy-allocator.cc:333: // TODO(mtrofin): replace GLRSP with the
entry point selecting heuristics,
On 2015/06/29 05:25:16, jarin wrote:
> What is GLRSP?

Done.

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/greedy-all...
src/compiler/greedy-allocator.cc:337: auto tail = Split(range, data(), pos);
On 2015/06/29 05:25:15, jarin wrote:
> auto -> LiveRange*

Done.

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/greedy-all...
File src/compiler/greedy-allocator.h (right):

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/greedy-all...
src/compiler/greedy-allocator.h:48: typedef
ZonePriorityQueue<AllocationCandidate> ScheduleStorage;
On 2015/06/29 05:25:16, jarin wrote:
> ScheduleStorage -> ScheduleQueue

Done.

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/greedy-all...
src/compiler/greedy-allocator.h:49: ScheduleStorage storage_;
On 2015/06/29 05:25:16, jarin wrote:
> storage_ -> queue_

Done.

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/greedy-all...
src/compiler/greedy-allocator.h:96: void HandleBlockedRange(LiveRange* range);
On 2015/06/29 05:25:16, jarin wrote:
> HandleBlockedRange -> SplitOrSpillBlockedRange?

Done.

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

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/register-a...
src/compiler/register-allocator.h:481: int size_;
On 2015/06/29 11:17:57, titzer wrote:
> Can you add a only liner explaining what "size" means? Even better, a more
> descriptive name.
> // greedy: the number of 

Done.

https://codereview.chromium.org/1205173002/diff/60001/src/compiler/register-a...
src/compiler/register-allocator.h:482: float weight_;
On 2015/06/29 11:17:57, titzer wrote:
> Is this the spill weight or the priority for allocation, or both? A comment
> could help here.

Done.

[Jarin, 2015-06-29 13:38:03]

lgtm from my side.

[Mircea Trofin, 2015-06-29 15:22:04]

The CQ bit was checked by mtrofin@chromium.org

[Mircea Trofin, 2015-06-29 15:22:05]

The patchset sent to the CQ was uploaded after l-g-t-m from jarin@chromium.org
Link to the patchset: https://codereview.chromium.org/1205173002/#ps120001
(title: "minor fix on splitting at interval boundaries")

[commit-bot: I haz the power, 2015-06-29 15:22:17]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1205173002/120001

[commit-bot: I haz the power, 2015-06-29 15:56:31]

Committed patchset #6 (id:120001)

[commit-bot: I haz the power, 2015-06-29 15:56:40]

Patchset 6 (id:??) landed as
https://crrev.com/1cd60451de667199d6195b54f0ea7a1d9f206557
Cr-Commit-Position: refs/heads/master@{#29352}