[turbofan] Deferred block spilling heuristic - first step.

[turbofan] Deferred block spilling heuristic - first step.

This is the first step to enabling optimal handling of spills in deferred blocks. Currently, the feature is limited to ranges that spill just in such a block. This avoids, at this point, complexities around connecting live ranges and control flow.

The heuristic consists of:
- a general purpose splitting heuristic - split before a call and until the first position needing a register (note: we may want to change this later to fill in a "good" place, i.e. ensure we don't fill in a loop). This is general purpose because it should provide value even in non-deferred block scenarios
- a detection of "deferred block splitting", when committing assignments.

[Mircea Trofin, 2015-07-20 15:36:14]

Patchset #2 (id:20001) has been deleted

[Mircea Trofin, 2015-07-20 15:36:21]

Patchset #1 (id:1) has been deleted

[Mircea Trofin, 2015-07-20 15:45:26]

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

[Mircea Trofin, 2015-07-20 15:46:58]

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

https://codereview.chromium.org/1242123006/diff/40001/src/compiler/register-a...
src/compiler/register-allocator.cc:356: InstructionBlock* start_block =
code->GetInstructionBlock(first_instr);
We may actually want to further restrict enabling this by requiring the end of
the spilled range is also in the same block, or at least the whole range lives
across deferred blocks.

[Jarin, 2015-07-22 12:59:36]

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

https://codereview.chromium.org/1242123006/diff/40001/src/compiler/greedy-all...
src/compiler/greedy-allocator.cc:87: auto instr =
data->code()->InstructionAt(index);
Expand 'auto', please.

https://codereview.chromium.org/1242123006/diff/40001/src/compiler/greedy-all...
src/compiler/greedy-allocator.cc:88: if (!instr->IsCall()) continue;
This does not really work because live ranges can (and  do) get indirectly
spilled by calls: If a call's position lies somewhere inside one of the live
ranges intervals, the call clobbers all registers and thus makes it impossible
for the live range to be allocated. That happens even if the call is not in the
live range's use list.

Just try this on the following example:

var f = (function() {
  "use asm"
  return function f(x, y) {
    x = x|0;
    y = y|0;
    return x+y|0;
  }
})();

%OptimizeFunctionOnNextCall(f)
f(1, 2);

Here the live range corresponding to x should not be spilled on the fast path,
but it is. (The same goes for the context that lives in rsi.)

https://codereview.chromium.org/1242123006/diff/40001/src/compiler/greedy-all...
src/compiler/greedy-allocator.cc:102: }
Why do we have the loop here? Cannot it happen that we fall off to a completely
unrelated basic block here?

https://codereview.chromium.org/1242123006/diff/40001/test/unittests/compiler...
File test/unittests/compiler/register-allocator-unittest.cc (right):

https://codereview.chromium.org/1242123006/diff/40001/test/unittests/compiler...
test/unittests/compiler/register-allocator-unittest.cc:534: int expect_1 =
FLAG_turbo_greedy_regalloc ? 3 : 1;
Could you please explain what the magic constants 1 and 3 are and link them to
the appropriate instructions?

https://codereview.chromium.org/1242123006/diff/40001/test/unittests/compiler...
test/unittests/compiler/register-allocator-unittest.cc:540: EXPECT_EQ(0,
GetMoveCount(*moves));
Please explain what you are checking here, this will be next to impossible to
understand if it fails.

[Mircea Trofin, 2015-07-23 02:20:04]

This particular patch is *not* a candidate for commit. 

I wanted to leverage the time difference and start a discussion about why we
can't seem to split immediately after a call - it leads to runtime errors. I
left comments in the code - see greedy-allocator.cc around line 102 as a reply,
and then a bit below. The purpose of this particular patch is to support the
discussion.

If anybody has an idea why this leads to runtime errors, please let me know,
otherwise my plan is to investigate tomorrow.

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

https://codereview.chromium.org/1242123006/diff/40001/src/compiler/greedy-all...
src/compiler/greedy-allocator.cc:88: if (!instr->IsCall()) continue;
On 2015/07/22 12:59:35, jarin wrote:
> This does not really work because live ranges can (and  do) get indirectly
> spilled by calls: If a call's position lies somewhere inside one of the live
> ranges intervals, the call clobbers all registers and thus makes it impossible
> for the live range to be allocated. That happens even if the call is not in
the
> live range's use list.
> 
> Just try this on the following example:
> 
> var f = (function() {
>   "use asm"
>   return function f(x, y) {
>     x = x|0;
>     y = y|0;
>     return x+y|0;
>   }
> })();
> 
> %OptimizeFunctionOnNextCall(f)
> f(1, 2);
> 
> Here the live range corresponding to x should not be spilled on the fast path,
> but it is. (The same goes for the context that lives in rsi.)

I see. OK, so we need to iterate over each instruction then.

https://codereview.chromium.org/1242123006/diff/40001/src/compiler/greedy-all...
src/compiler/greedy-allocator.cc:102: }
On 2015/07/22 12:59:35, jarin wrote:
> Why do we have the loop here? Cannot it happen that we fall off to a
completely
> unrelated basic block here?

If we fall on to a different block, that's fine, correctness-wise, but we lose
the optimization opportunity.

The main issue here - and I'm investigating it - is why can't we just split
again at index + 1. It leads to runtime errors, and I suspect there's some
interplay with the way we handle traced pointers.

https://codereview.chromium.org/1242123006/diff/40001/test/unittests/compiler...
File test/unittests/compiler/register-allocator-unittest.cc (right):

https://codereview.chromium.org/1242123006/diff/40001/test/unittests/compiler...
test/unittests/compiler/register-allocator-unittest.cc:534: int expect_1 =
FLAG_turbo_greedy_regalloc ? 3 : 1;
On 2015/07/22 12:59:36, jarin wrote:
> Could you please explain what the magic constants 1 and 3 are and link them to
> the appropriate instructions?

Done.

https://codereview.chromium.org/1242123006/diff/40001/test/unittests/compiler...
test/unittests/compiler/register-allocator-unittest.cc:540: EXPECT_EQ(0,
GetMoveCount(*moves));
On 2015/07/22 12:59:36, jarin wrote:
> Please explain what you are checking here, this will be next to impossible to
> understand if it fails.

Done, but please let me know if, still, the comment and new var names form too
weak of a context for a developer to understand what's going on.

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

https://codereview.chromium.org/1242123006/diff/60001/src/compiler/greedy-all...
src/compiler/greedy-allocator.cc:129: index + 1;  //
next_use->pos().ToInstructionIndex();
If we change instr_to_split = next_use->pos().ToInstructionIndex(), everything
works fine. (to be clear, the current code lands on instr_to_split = index + 1
in a convoluted way, but it's simple to switch back and forth)

[Benedikt Meurer, 2015-07-28 04:57:18]

The general direction seems good. Did you investigate the test failures already?

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

https://codereview.chromium.org/1242123006/diff/80001/src/compiler/register-a...
src/compiler/register-allocator.cc:475: UsePosition*
LiveRange::NextStackPosition(LifetimePosition start) const {
Nit: I'd use NextSlotPosition as name for consistency (use type is
kRequiresSlot).

https://codereview.chromium.org/1242123006/diff/80001/src/runtime/runtime-int...
File src/runtime/runtime-internal.cc (right):

https://codereview.chromium.org/1242123006/diff/80001/src/runtime/runtime-int...
src/runtime/runtime-internal.cc:29: Object* ret = isolate->Throw(args[0]);
What is the motivation for this change?

[Mircea Trofin, 2015-07-28 23:14:15]

Patchset #6 (id:140001) has been deleted

[Mircea Trofin, 2015-07-28 23:14:28]

Patchset #5 (id:120001) has been deleted