Make special RPO computation iterative during scheduling.

Make special RPO computation iterative during scheduling.

This contains the following changes squashed together:
- Switch BasicBlock::loop_end to be a basic block instead of an RPO.
- Switch ScheduleLate to use dominator depth instead of RPO.
- Switch ScheduleEarly to use dominator depth instead of RPO.
- Push out absolute RPO ordering everywhere else in the scheduler.
- Keep linked list of blocks in RPO order while scheduling.
- Switch from RPO number to depth for dominator calculation.

R=jarin@chromium.org

Committed: https://code.google.com/p/v8/source/detail?r=25138

[Michael Starzinger, 2014-11-03 18:43:23]

Has some rough edges marked with TODOs, but should be ready for our current
use-cases.

[Michael Starzinger, 2014-11-03 21:14:39]

Some notes for my stupid future self.

https://codereview.chromium.org/696363002/diff/20001/src/compiler/scheduler.cc
File src/compiler/scheduler.cc (right):

https://codereview.chromium.org/696363002/diff/20001/src/compiler/scheduler.c...
src/compiler/scheduler.cc:519: //    => If block A dominates block B, then A
appears before B in the order.
note to self: Undo accidental indentation.

https://codereview.chromium.org/696363002/diff/20001/src/compiler/scheduler.c...
src/compiler/scheduler.cc:550: // Serialize the previously computed assembly
order (non-deferred code first,
note to self: "Serialize the previously computed order as an assembly order
numbering [...]"

https://codereview.chromium.org/696363002/diff/20001/src/compiler/scheduler.c...
src/compiler/scheduler.cc:564: // Serialize the previously computed special
reverse-post-order numbering for
note to self: "Serialize the previously computed order as a special [...]"

https://codereview.chromium.org/696363002/diff/20001/src/compiler/scheduler.c...
src/compiler/scheduler.cc:645: // We are hijacking the AO number to enumerate
loops temporarily. Note that
note to self: s/AO number/{ao_number}/ here.

https://codereview.chromium.org/696363002/diff/20001/src/compiler/scheduler.c...
src/compiler/scheduler.cc:1170: // is still post-dominates all inputs to {node}
when the queue is processed.
note to self: Drop the "is" here.

https://codereview.chromium.org/696363002/diff/20001/src/compiler/scheduler.c...
src/compiler/scheduler.cc:1401: // Compute the assembly order and
reverse-post-order numbering.
note to self: s/Compute/Serialize/ here.

[Jarin, 2014-11-04 20:58:29]

lgtm module one question. I love the linked list RPO trick - very clever!

https://codereview.chromium.org/696363002/diff/40001/src/compiler/scheduler.cc
File src/compiler/scheduler.cc (right):

https://codereview.chromium.org/696363002/diff/40001/src/compiler/scheduler.c...
src/compiler/scheduler.cc:676: BlockList* insert_tail = insert_head == NULL ?
NULL : insert_head->next;
The names are a bit confusing, I think. How about insert_after and
insert_before?

https://codereview.chromium.org/696363002/diff/40001/src/compiler/scheduler.c...
src/compiler/scheduler.cc:721: insert_head->next = insert_tail->next;
Hmm, should not it be 'insert_head->next = insert_tail;' ?

[Michael Starzinger, 2014-11-05 09:42:07]

Thanks for the review. Addressed comments. Landing.

https://codereview.chromium.org/696363002/diff/40001/src/compiler/scheduler.cc
File src/compiler/scheduler.cc (right):

https://codereview.chromium.org/696363002/diff/40001/src/compiler/scheduler.c...
src/compiler/scheduler.cc:676: BlockList* insert_tail = insert_head == NULL ?
NULL : insert_head->next;
On 2014/11/04 20:58:29, jarin wrote:
> The names are a bit confusing, I think. How about insert_after and
> insert_before?

Done.

https://codereview.chromium.org/696363002/diff/40001/src/compiler/scheduler.c...
src/compiler/scheduler.cc:721: insert_head->next = insert_tail->next;
On 2014/11/04 20:58:29, jarin wrote:
> Hmm, should not it be 'insert_head->next = insert_tail;' ?

That's because there are two list element for the "entry" block. One already in
the original list and one in the newly created sub-list. I agree this is
confusing. I added an assertion in that regard and a comment explaining it.

[Michael Starzinger, 2014-11-05 10:10:46]

Committed patchset #5 (id:80001) manually as 25138 (presubmit successful).