[turbofan] Stand-alone deferred block splitting - full.

Stand-alone deferred block splitting. This continues 1256313003.

BUG=

Committed: https://crrev.com/5202facf9e32eaa096aa9d1aa7165634a6dcbcd2
Cr-Commit-Position: refs/heads/master@{#30050}

[Mircea Trofin, 2015-08-03 00:08:54]

Patchset #2 (id:20001) has been deleted

[Mircea Trofin, 2015-08-03 00:09:37]

Deferred block splitting as a stand-alone stage, running independent of register
allocator.

https://codereview.chromium.org/1271703002/diff/1/src/compiler/register-alloc...
File src/compiler/register-allocator.cc (right):

https://codereview.chromium.org/1271703002/diff/1/src/compiler/register-alloc...
src/compiler/register-allocator.cc:1596: Define(curr_position, output);
I should be able to write a unit test for this one. It was caught by some tests,
when I introduced the deferred block splitting phase.

https://codereview.chromium.org/1271703002/diff/1/src/flag-definitions.h
File src/flag-definitions.h (right):

https://codereview.chromium.org/1271703002/diff/1/src/flag-definitions.h#newc...
src/flag-definitions.h:402: DEFINE_IMPLICATION(turbo_greedy_regalloc,
turbo_preprocess_ranges)
The implication is only so we can get trybot coverage with the greedy trybots,
it can be removed if we have dedicated trybots for the preprocessing feature.

[Mircea Trofin, 2015-08-03 00:10:20]

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

[Mircea Trofin, 2015-08-03 00:10:39]

(forgot to add reviewers)

[Mircea Trofin, 2015-08-04 14:28:34]

Patchset #2 (id:40001) has been deleted

[Mircea Trofin, 2015-08-04 15:15:29]

Updated this after rebasing after 1256313003.

[Jarin, 2015-08-04 19:39:43]

Unfortunately, I am quite confused about this change, so I have bunch of
questions.

https://codereview.chromium.org/1271703002/diff/60001/src/compiler/move-optim...
File src/compiler/move-optimizer.cc (right):

https://codereview.chromium.org/1271703002/diff/60001/src/compiler/move-optim...
src/compiler/move-optimizer.cc:69: if (has_only_deferred) continue;
Could you explain why we skip the optimization here?

https://codereview.chromium.org/1271703002/diff/60001/src/compiler/pipeline.cc
File src/compiler/pipeline.cc (right):

https://codereview.chromium.org/1271703002/diff/60001/src/compiler/pipeline.c...
src/compiler/pipeline.cc:1340: // TODO(mtrofin): re-enable greedy once we have
bots for range preprocessing.
Do we really want to have a bot for range preprocessing? That seems to be an
overkill.

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

https://codereview.chromium.org/1271703002/diff/60001/src/compiler/preprocess...
src/compiler/preprocess-live-ranges.cc:83: int stop) {
stop -> end

https://codereview.chromium.org/1271703002/diff/60001/src/compiler/preprocess...
src/compiler/preprocess-live-ranges.cc:91: void
SplitRangeByClobberingDeferredBlocks(LiveRange* range,
The name is a bit confusing (it sounds like it clobbers deferred blocks).
Perhaps SplitRangeAtDeferredBlocksWithCalls?

https://codereview.chromium.org/1271703002/diff/60001/src/compiler/preprocess...
src/compiler/preprocess-live-ranges.cc:112: if (last_index >=
code->InstructionCount()) {
It could be more readable if you said "if (last_index >
code->LastInstructionIndex()) last_index = code->LastInstructionIndex();". With
that, you could remove the InstructionCount method.

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

https://codereview.chromium.org/1271703002/diff/60001/src/compiler/register-a...
src/compiler/register-allocator.cc:392: move->AddMove(assigned, spill_operand);
Still confused about this - where do we actually spill the deferred block with a
call? This move seems to be only inserted for ranges that are not spilled.

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

https://codereview.chromium.org/1271703002/diff/60001/src/compiler/register-a...
src/compiler/register-allocator.h:456: bool IsSpilledInSingleDeferredBlock()
const {
I am really confused about this. The name refers to *single* deferred block, but
the TryCommitSpillInDeferredBlock method seems to set the
spilled_in_deferred_block_ flag even if there are multiple such blocks.

[Mircea Trofin, 2015-08-04 20:34:46]

https://codereview.chromium.org/1271703002/diff/60001/src/compiler/move-optim...
File src/compiler/move-optimizer.cc (right):

https://codereview.chromium.org/1271703002/diff/60001/src/compiler/move-optim...
src/compiler/move-optimizer.cc:69: if (has_only_deferred) continue;
On 2015/08/04 19:39:43, Jarin wrote:
> Could you explain why we skip the optimization here?

This would pull down common fills. If the fills occur in deferred blocks, and
the closest common successor is not deferred, we lose the optimization of
spilling/filling just in deferred blocks.

https://codereview.chromium.org/1271703002/diff/60001/src/compiler/pipeline.cc
File src/compiler/pipeline.cc (right):

https://codereview.chromium.org/1271703002/diff/60001/src/compiler/pipeline.c...
src/compiler/pipeline.cc:1340: // TODO(mtrofin): re-enable greedy once we have
bots for range preprocessing.
On 2015/08/04 19:39:43, Jarin wrote:
> Do we really want to have a bot for range preprocessing? That seems to be an
> overkill.

I don't know. I know we want to have range preprocessing enabled for linear, and
I assume we'd want to go through some fuzz testing with it. I imagined we'd do
so by having a flag and flipping it on only in certain cases - let me know how
to best stage this, though.

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

https://codereview.chromium.org/1271703002/diff/60001/src/compiler/preprocess...
src/compiler/preprocess-live-ranges.cc:83: int stop) {
On 2015/08/04 19:39:43, Jarin wrote:
> stop -> end

Done.

https://codereview.chromium.org/1271703002/diff/60001/src/compiler/preprocess...
src/compiler/preprocess-live-ranges.cc:91: void
SplitRangeByClobberingDeferredBlocks(LiveRange* range,
On 2015/08/04 19:39:43, Jarin wrote:
> The name is a bit confusing (it sounds like it clobbers deferred blocks).
> Perhaps SplitRangeAtDeferredBlocksWithCalls?

Done.

https://codereview.chromium.org/1271703002/diff/60001/src/compiler/preprocess...
src/compiler/preprocess-live-ranges.cc:112: if (last_index >=
code->InstructionCount()) {
On 2015/08/04 19:39:43, Jarin wrote:
> It could be more readable if you said "if (last_index >
> code->LastInstructionIndex()) last_index = code->LastInstructionIndex();".
With
> that, you could remove the InstructionCount method.

Done.

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

https://codereview.chromium.org/1271703002/diff/60001/src/compiler/register-a...
src/compiler/register-allocator.cc:392: move->AddMove(assigned, spill_operand);
On 2015/08/04 19:39:43, Jarin wrote:
> Still confused about this - where do we actually spill the deferred block with
a
> call? This move seems to be only inserted for ranges that are not spilled.

Correct. It sets up the stage for the register allocator. The register allocator
will make the decision of where to spill, but now it will treat the segments
over deferred ranges separately from the rest of the range.

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

https://codereview.chromium.org/1271703002/diff/60001/src/compiler/register-a...
src/compiler/register-allocator.h:456: bool IsSpilledInSingleDeferredBlock()
const {
On 2015/08/04 19:39:43, Jarin wrote:
> I am really confused about this. The name refers to *single* deferred block,
but
> the TryCommitSpillInDeferredBlock method seems to set the
> spilled_in_deferred_block_ flag even if there are multiple such blocks.

Sorry - the name was a point in time :) It's not for single at all anymore. I'll
rename.

[Mircea Trofin, 2015-08-04 20:39:04]

https://codereview.chromium.org/1271703002/diff/60001/src/compiler/move-optim...
File src/compiler/move-optimizer.cc (right):

https://codereview.chromium.org/1271703002/diff/60001/src/compiler/move-optim...
src/compiler/move-optimizer.cc:69: if (has_only_deferred) continue;
On 2015/08/04 20:34:46, Mircea Trofin wrote:
> On 2015/08/04 19:39:43, Jarin wrote:
> > Could you explain why we skip the optimization here?
> 
> This would pull down common fills. If the fills occur in deferred blocks, and
> the closest common successor is not deferred, we lose the optimization of
> spilling/filling just in deferred blocks.

Should have added: the last statement of the MultipleDeferredBlockSpills unit
test (EXPECT_EQ...) would fail without this logic.

[Jarin, 2015-08-05 14:04:16]

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

https://codereview.chromium.org/1271703002/diff/60001/src/compiler/register-a...
src/compiler/register-allocator.cc:392: move->AddMove(assigned, spill_operand);
On 2015/08/04 20:34:46, Mircea Trofin wrote:
> On 2015/08/04 19:39:43, Jarin wrote:
> > Still confused about this - where do we actually spill the deferred block
with
> a
> > call? This move seems to be only inserted for ranges that are not spilled.
> 
> Correct. It sets up the stage for the register allocator. The register
allocator
> will make the decision of where to spill, but now it will treat the segments
> over deferred ranges separately from the rest of the range.

I am sorry, that explanation did not really help me understand. As far as I
understand, CommitSpillsAtDefinition runs after the actual allocation, so I do
not see how this can setup the stage for register allocation. Could you explain?
Where exactly is the place that adds the spilling move for deferred blocks with
calls?

Or are you saying that the pre-processing phase inserts live ranges for the
deferred blocks so that the register allocator can spill those ranges (and since
those ranges begin in deferred blocks, they would get the right spill)? I cannot
see how this would work either because the pre-processing seems to only create
child ranges, so they would not really get their own definitions.

[Jarin, 2015-08-06 12:28:43]

I think I understand now how the spilling works, but it is very subtle. Once you
add explanatory comments, it will be good to go.

What are the performance numbers?

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

https://codereview.chromium.org/1271703002/diff/80001/src/compiler/register-a...
src/compiler/register-allocator.cc:408: // the range and control flow connection
mechanism instead.
Please elaborate on how this uses the control flow connection mechanism.

This incremental build-up of various moves is in my opinion the worst part of
the register allocator (in terms of understandability and maintainability), and
this CL makes it worse. It should be explained in the comments.

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

https://codereview.chromium.org/1271703002/diff/80001/src/compiler/register-a...
src/compiler/register-allocator.h:417: // in which it may be worse to spill in
it.
The comment seems to be out of date (it refers to the ranges with just one
spilled child).

[Mircea Trofin, 2015-08-06 15:37:03]

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

https://codereview.chromium.org/1271703002/diff/80001/src/compiler/register-a...
src/compiler/register-allocator.cc:408: // the range and control flow connection
mechanism instead.
On 2015/08/06 12:28:42, Jarin wrote:
> Please elaborate on how this uses the control flow connection mechanism.
> 
> This incremental build-up of various moves is in my opinion the worst part of
> the register allocator (in terms of understandability and maintainability),
and
> this CL makes it worse. It should be explained in the comments.

Added comments. I think clarifying the role of each stage should make
comprehension a bit easier. I'm not sure yet how we can improve the current
design.

One additional aid may be making the marking of deferred block-only ranges a
phase in itself - a post-process ranges phase, if you will. In the spirit of
incremental changes, though, I'll do that separately.

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

https://codereview.chromium.org/1271703002/diff/80001/src/compiler/register-a...
src/compiler/register-allocator.h:417: // in which it may be worse to spill in
it.
On 2015/08/06 12:28:42, Jarin wrote:
> The comment seems to be out of date (it refers to the ranges with just one
> spilled child).

Done.

[Mircea Trofin, 2015-08-06 15:39:03]

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

https://codereview.chromium.org/1271703002/diff/80001/src/compiler/register-a...
src/compiler/register-allocator.cc:408: // the range and control flow connection
mechanism instead.
On 2015/08/06 15:37:03, Mircea Trofin wrote:
> On 2015/08/06 12:28:42, Jarin wrote:
> > Please elaborate on how this uses the control flow connection mechanism.
> > 
> > This incremental build-up of various moves is in my opinion the worst part
of
> > the register allocator (in terms of understandability and maintainability),
> and
> > this CL makes it worse. It should be explained in the comments.
> 
> Added comments. I think clarifying the role of each stage should make
> comprehension a bit easier. I'm not sure yet how we can improve the current
> design.
> 
> One additional aid may be making the marking of deferred block-only ranges a
> phase in itself - a post-process ranges phase, if you will. In the spirit of
> incremental changes, though, I'll do that separately.

Also, moved the test away from "CommitSpillsAtDefinition", seems like better
code organization.

[Jarin, 2015-08-06 16:19:37]

lgtm

[Mircea Trofin, 2015-08-06 16:19:58]

The CQ bit was checked by mtrofin@chromium.org

[commit-bot: I haz the power, 2015-08-06 16:20:05]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1271703002/100001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1271703002/100001

[commit-bot: I haz the power, 2015-08-06 16:21:27]

Committed patchset #4 (id:100001)

[commit-bot: I haz the power, 2015-08-06 16:21:53]

Patchset 4 (id:??) landed as
https://crrev.com/5202facf9e32eaa096aa9d1aa7165634a6dcbcd2
Cr-Commit-Position: refs/heads/master@{#30050}