New linear scan allocator.

New linear scan allocator.

Committed: https://code.google.com/p/dart/source/detail?r=9851

[Vyacheslav Egorov (Google), 2012-07-19 16:52:16]

I am uploading this as a preliminary draft. 

There are still some minor infrastructure pieces missing. But support for
spilling and allocation of blocked registers, connection of live ranges (linear
control flow and control flow across branches is now in place.

I need to resolve some corner cases before it will be fully ready for commit.

[srdjan, 2012-07-19 22:54:38]

Some initial comments

http://codereview.chromium.org/10800037/diff/1/runtime/vm/flow_graph_allocato...
File runtime/vm/flow_graph_allocator.cc (right):

http://codereview.chromium.org/10800037/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.cc:263: if (first_use_interval_ == NULL ||
first_use_interval_->start_ != def) {
Add parenthesis

http://codereview.chromium.org/10800037/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.cc:414: MoveOperands* move =
&(parallel_move->moves()[move_idx]);
Why make it a pointer here?

http://codereview.chromium.org/10800037/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.cc:506: Define(pos,
Seems to be able to fit in one line?

http://codereview.chromium.org/10800037/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.cc:1054: first_unallocated);
Indent 4 spaces above.

http://codereview.chromium.org/10800037/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.cc:1139: if (cpu_regs_[reg].length() == 0)
continue;
use is_empty() instead of length() == 0.

http://codereview.chromium.org/10800037/diff/1/runtime/vm/flow_graph_allocator.h
File runtime/vm/flow_graph_allocator.h (right):

http://codereview.chromium.org/10800037/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.h:253: // UseInterval* Split(intptr_t pos);
Delete dead code.

http://codereview.chromium.org/10800037/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.h:300: next_sibling_(NULL) {
, finger_() {

http://codereview.chromium.org/10800037/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.h:351: next_sibling_(next_sibling) {
, finger_() {

http://codereview.chromium.org/10800037/diff/1/runtime/vm/intermediate_langua...
File runtime/vm/intermediate_language_x64.cc (right):

http://codereview.chromium.org/10800037/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language_x64.cc:1374: summary->set_temp(0,
Location::RegisterLocation(R10));
Document why R10.

http://codereview.chromium.org/10800037/diff/1/tools/gyp/configurations_make....
File tools/gyp/configurations_make.gypi (right):

http://codereview.chromium.org/10800037/diff/1/tools/gyp/configurations_make....
tools/gyp/configurations_make.gypi:63: 'cflags': [ '-O0' ],
Remove this file from the CL

[Vyacheslav Egorov (Google), 2012-07-20 23:57:36]

I have refactored live range building routine and changed the meaning of
positions we assign to instruction. Comment included.

Please take a look at BuildLiveRanges.

[srdjan, 2012-07-22 15:09:24]

Some new and some repeated comments. Please apply the comments from my previous
reply and let me know when you have uploaded. Thanks.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
File runtime/vm/flow_graph_allocator.cc (right):

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.cc:340: BlockEntryInstr* block) {
indent 4 spaces

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.cc:385: //
I do not understand the comment above. I see you are using the format below as
well. Please explain what *, - etc means.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.cc:388:
val->AsUse()->definition()->ssa_temp_index());
4 spaces indent. 2 spaces is used only when starting a new nested block.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.cc:432: //
ditto

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
File runtime/vm/flow_graph_allocator.h (right):

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.h:66: Instruction* InstructionAt(intptr_t pos);
const

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.h:67: bool IsBlockEntry(intptr_t pos);
const

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.h:214: private:
Add DISALLOW_COPY_AND_ASSIGN

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.h:215: intptr_t pos_;
const ?

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.h:249: // UseInterval* Split(intptr_t pos);
Delete

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.h:257: };
Add DISALLOW_COPY_AND_ASSIGN

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.h:284: UsePosition* first_hinted_use_;
Add DISALLOW_COPY_AND_ASSIGN

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.h:354: AllocationFinger finger_;
Add DISALLOW_COPY_AND_ASSIGN

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/intermed...
File runtime/vm/intermediate_language_x64.cc (right):

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/intermed...
runtime/vm/intermediate_language_x64.cc:1458: summary->set_temp(0,
Location::RegisterLocation(R10));
Why R10?

https://chromiumcodereview.appspot.com/10800037/diff/6001/tools/gyp/configura...
File tools/gyp/configurations_make.gypi (right):

https://chromiumcodereview.appspot.com/10800037/diff/6001/tools/gyp/configura...
tools/gyp/configurations_make.gypi:4: 
Remove this file from the CL.

[srdjan, 2012-07-22 23:27:33]

I would definitely recommend splitting this CL into several ones in order to
make quick progress.

http://codereview.chromium.org/10800037/diff/6001/runtime/vm/flow_graph_alloc...
File runtime/vm/flow_graph_allocator.cc (right):

http://codereview.chromium.org/10800037/diff/6001/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:234: Location* location_slot) {
Args should fit into one line.

http://codereview.chromium.org/10800037/diff/6001/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:250: if (first_use_interval_ != NULL) {
Add comment: do not add if the first_use_interval_ covers the new interval. What
about other use_intervals (linked via next_). Why add an interval when it is
already covered by an existing one? Should you traverse all intervals to figure
it out?

http://codereview.chromium.org/10800037/diff/6001/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:255: first_use_interval_->start_ = start;
Do you want to do that even if start < first_use_interval_->start, i.e., do you
allow shrinking of UseInterval?

http://codereview.chromium.org/10800037/diff/6001/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:261: if (last_use_interval_ == NULL)
last_use_interval_ = first_use_interval_;
ASSERT(last_use_interval_->next() == NULL) thus making sure that nobody else
wrote into first_use_interval_ before.

http://codereview.chromium.org/10800037/diff/6001/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:266: if (first_use_interval_ != NULL) {
I would revert, test for positive first, makes it more readable IMHO.

http://codereview.chromium.org/10800037/diff/6001/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:290: if (blocked_cpu_regs_[reg]) return;
 == NULL

http://codereview.chromium.org/10800037/diff/6001/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:344: if (goto_instr == NULL) return last;
What about branches?

http://codereview.chromium.org/10800037/diff/6001/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:351: if (parallel_move == NULL) return
last->previous();
Since last can survive here only as goto_instr, return goto_instr->previous() ?

http://codereview.chromium.org/10800037/diff/6001/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:368: ASSERT(pred_idx <
join->PredecessorCount());
class JoinInstr has a method that does the above:
intptr_t pred_idx = join->IndexOfPredecessor(block);

http://codereview.chromium.org/10800037/diff/6001/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:394: range->AddUse(pos, slot);
Rewrite: 
move->set_src(Location::Prefersregister());
range->AddUseInterval(block->start_pos(), pos);
range->AddUse(pos, move->src_slot());

http://codereview.chromium.org/10800037/diff/6001/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:408: void
FlowGraphAllocator::ConnectIncommingPhiMoves(BlockEntryInstr* block) {
s/Incomming/Incoming/

http://codereview.chromium.org/10800037/diff/6001/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:417: 
s/block/join/

http://codereview.chromium.org/10800037/diff/6001/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:444:
move_instr->AsParallelMove()->MoveOperandsAt(move_idx);
indent 4

http://codereview.chromium.org/10800037/diff/6001/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:460: Instruction* current) {
ProcessOneInstruction is not self explanatory, pelase add brief comment or
rename.

http://codereview.chromium.org/10800037/diff/6001/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:473: (locs->out().policy() ==
Location::kSameAsFirstInput);
Indent 4

http://codereview.chromium.org/10800037/diff/6001/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:527: AddMoveAt(pos - 1, *in_ref,
Location::PrefersRegister());
4 spaces

http://codereview.chromium.org/10800037/diff/6001/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:794: return instructions_[pos >> 1];
pos / 2 is clearer, IMHO.

http://codereview.chromium.org/10800037/diff/6001/runtime/vm/locations.cc
File runtime/vm/locations.cc (right):

http://codereview.chromium.org/10800037/diff/6001/runtime/vm/locations.cc#new...
runtime/vm/locations.cc:59: UNREACHABLE();
Why not default UNREACHABLE?

http://codereview.chromium.org/10800037/diff/6001/runtime/vm/locations.h
File runtime/vm/locations.h (right):

http://codereview.chromium.org/10800037/diff/6001/runtime/vm/locations.h#newc...
runtime/vm/locations.h:20: // Each location is encoded as a single word: low 2
bits denote location kind,
It seems that you are now using 3 bits with SpillSlot, however that does not
allow for merging kConstant with a handle. I see why it still works (spill slot
overlaps with kInvalid) but the comment is not clear enough. An alternative is
to merge spill-slots and registers, and a negative payload denotes spil-slot, a
positive a register.

http://codereview.chromium.org/10800037/diff/6001/runtime/vm/locations.h#newc...
runtime/vm/locations.h:27: // the same as kConstant.
Describe also what is the payload of each kind, and if it has any.

[Vyacheslav Egorov (Google), 2012-07-23 11:48:39]

I am starting to split it to pieces.

First piece:

spill locations: https://chromiumcodereview.appspot.com/10805053

so that somebody (Kevin?) can start to work on deoptimization stubs that will be
able to deoptimize from states with spill slots.

http://codereview.chromium.org/10800037/diff/6001/runtime/vm/locations.cc
File runtime/vm/locations.cc (right):

http://codereview.chromium.org/10800037/diff/6001/runtime/vm/locations.cc#new...
runtime/vm/locations.cc:59: UNREACHABLE();
On 2012/07/22 23:27:33, srdjan wrote:
> Why not default UNREACHABLE?

I prefer compilation error to the runtime error. If I don't have default: label
compiler will warn me when some enumeration member is unhandled in the switch.

http://codereview.chromium.org/10800037/diff/6001/runtime/vm/locations.h
File runtime/vm/locations.h (right):

http://codereview.chromium.org/10800037/diff/6001/runtime/vm/locations.h#newc...
runtime/vm/locations.h:20: // Each location is encoded as a single word: low 2
bits denote location kind,
On 2012/07/22 23:27:33, srdjan wrote:
> It seems that you are now using 3 bits with SpillSlot, however that does not
> allow for merging kConstant with a handle. I see why it still works (spill
slot
> overlaps with kInvalid) but the comment is not clear enough. An alternative is
> to merge spill-slots and registers, and a negative payload denotes spil-slot,
a
> positive a register.

It works because no location kind has the same lower two bits as kConstant which
is intentional and declared below.

http://codereview.chromium.org/10800037/diff/6001/runtime/vm/locations.h#newc...
runtime/vm/locations.h:27: // the same as kConstant.
On 2012/07/22 23:27:33, srdjan wrote:
> Describe also what is the payload of each kind, and if it has any.

Done.

[srdjan, 2012-07-23 17:02:50]

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/location...
File runtime/vm/locations.cc (right):

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/location...
runtime/vm/locations.cc:59: UNREACHABLE();
On 2012/07/23 11:48:39, Vyacheslav Egorov (Google) wrote:
> On 2012/07/22 23:27:33, srdjan wrote:
> > Why not default UNREACHABLE?
> 
> I prefer compilation error to the runtime error. If I don't have default:
label
> compiler will warn me when some enumeration member is unhandled in the switch.


I agree.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/locations.h
File runtime/vm/locations.h (right):

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/location...
runtime/vm/locations.h:20: // Each location is encoded as a single word: low 2
bits denote location kind,
On 2012/07/23 11:48:39, Vyacheslav Egorov (Google) wrote:
> On 2012/07/22 23:27:33, srdjan wrote:
> > It seems that you are now using 3 bits with SpillSlot, however that does not
> > allow for merging kConstant with a handle. I see why it still works (spill
> slot
> > overlaps with kInvalid) but the comment is not clear enough. An alternative
is
> > to merge spill-slots and registers, and a negative payload denotes
spil-slot,
> a
> > positive a register.
> 
> It works because no location kind has the same lower two bits as kConstant
which
> is intentional and declared below.

I think the improved documentation in the other split off CL is good enough.

[Vyacheslav Egorov (Google), 2012-07-24 12:26:41]

Comments addressed. Rebased. PTAL

https://chromiumcodereview.appspot.com/10800037/diff/1/runtime/vm/flow_graph_...
File runtime/vm/flow_graph_allocator.cc (right):

https://chromiumcodereview.appspot.com/10800037/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:1054: first_unallocated);
On 2012/07/19 22:54:39, srdjan wrote:
> Indent 4 spaces above.

Done.

https://chromiumcodereview.appspot.com/10800037/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:1139: if (cpu_regs_[reg].length() == 0)
continue;
On 2012/07/19 22:54:39, srdjan wrote:
> use is_empty() instead of length() == 0.

Done.

https://chromiumcodereview.appspot.com/10800037/diff/1/runtime/vm/flow_graph_...
File runtime/vm/flow_graph_allocator.h (right):

https://chromiumcodereview.appspot.com/10800037/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.h:253: // UseInterval* Split(intptr_t pos);
On 2012/07/19 22:54:39, srdjan wrote:
> Delete dead code.

Done.

https://chromiumcodereview.appspot.com/10800037/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.h:300: next_sibling_(NULL) {
On 2012/07/19 22:54:39, srdjan wrote:
> , finger_() {

Done.

https://chromiumcodereview.appspot.com/10800037/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.h:351: next_sibling_(next_sibling) {
On 2012/07/19 22:54:39, srdjan wrote:
> , finger_() {

Done.

https://chromiumcodereview.appspot.com/10800037/diff/1/runtime/vm/intermediat...
File runtime/vm/intermediate_language_x64.cc (right):

https://chromiumcodereview.appspot.com/10800037/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language_x64.cc:1374: summary->set_temp(0,
Location::RegisterLocation(R10));
On 2012/07/19 22:54:39, srdjan wrote:
> Document why R10.

Done.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
File runtime/vm/flow_graph_allocator.cc (right):

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.cc:234: Location* location_slot) {
On 2012/07/22 23:27:33, srdjan wrote:
> Args should fit into one line.

Done.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.cc:250: if (first_use_interval_ != NULL) {
On 2012/07/22 23:27:33, srdjan wrote:
> Add comment: do not add if the first_use_interval_ covers the new interval.
What
> about other use_intervals (linked via next_). Why add an interval when it is
> already covered by an existing one? Should you traverse all intervals to
figure
> it out?

Added comment.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.cc:255: first_use_interval_->start_ = start;
On 2012/07/22 23:27:33, srdjan wrote:
> Do you want to do that even if start < first_use_interval_->start, i.e., do
you
> allow shrinking of UseInterval?

This is not shrinking this is expansion. UseIntervals are being built in a
monotonically decreasing order.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.cc:261: if (last_use_interval_ == NULL)
last_use_interval_ = first_use_interval_;
On 2012/07/22 23:27:33, srdjan wrote:
> ASSERT(last_use_interval_->next() == NULL) thus making sure that nobody else
> wrote into first_use_interval_ before.

Done.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.cc:266: if (first_use_interval_ != NULL) {
On 2012/07/22 23:27:33, srdjan wrote:
> I would revert, test for positive first, makes it more readable IMHO.

Done.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.cc:290: if (blocked_cpu_regs_[reg]) return;
On 2012/07/22 23:27:33, srdjan wrote:
>  == NULL

blocked_cpu_regs_[reg] is a bool value.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.cc:340: BlockEntryInstr* block) {
On 2012/07/22 15:09:24, srdjan wrote:
> indent 4 spaces

Done.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.cc:344: if (goto_instr == NULL) return last;
On 2012/07/22 23:27:33, srdjan wrote:
> What about branches?

Branches cannot have outgoing phi moves this violates edge split form.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.cc:351: if (parallel_move == NULL) return
last->previous();
On 2012/07/22 23:27:33, srdjan wrote:
> Since last can survive here only as goto_instr, return goto_instr->previous()
?

Done.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.cc:368: ASSERT(pred_idx <
join->PredecessorCount());
On 2012/07/22 23:27:33, srdjan wrote:
> class JoinInstr has a method that does the above:
> intptr_t pred_idx = join->IndexOfPredecessor(block);

I guess this code predates the method. Thanks.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.cc:385: //
On 2012/07/22 15:09:24, srdjan wrote:
> I do not understand the comment above. I see you are using the format below as
> well. Please explain what *, - etc means.

Done.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.cc:388:
val->AsUse()->definition()->ssa_temp_index());
On 2012/07/22 15:09:24, srdjan wrote:
> 4 spaces indent. 2 spaces is used only when starting a new nested block.

Done.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.cc:394: range->AddUse(pos, slot);
On 2012/07/22 23:27:33, srdjan wrote:
> Rewrite: 
> move->set_src(Location::Prefersregister());
> range->AddUseInterval(block->start_pos(), pos);
> range->AddUse(pos, move->src_slot());

Done.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.cc:408: void
FlowGraphAllocator::ConnectIncommingPhiMoves(BlockEntryInstr* block) {
On 2012/07/22 23:27:33, srdjan wrote:
> s/Incomming/Incoming/

Done.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.cc:417: 
On 2012/07/22 23:27:33, srdjan wrote:
> s/block/join/

Done.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.cc:432: //
On 2012/07/22 15:09:24, srdjan wrote:
> ditto

Done.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.cc:444:
move_instr->AsParallelMove()->MoveOperandsAt(move_idx);
On 2012/07/22 23:27:33, srdjan wrote:
> indent 4

Done.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.cc:460: Instruction* current) {
On 2012/07/22 23:27:33, srdjan wrote:
> ProcessOneInstruction is not self explanatory, pelase add brief comment or
> rename.

Done.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.cc:473: (locs->out().policy() ==
Location::kSameAsFirstInput);
On 2012/07/22 23:27:33, srdjan wrote:
> Indent 4

Done.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.cc:527: AddMoveAt(pos - 1, *in_ref,
Location::PrefersRegister());
On 2012/07/22 23:27:33, srdjan wrote:
> 4 spaces

Done.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.cc:794: return instructions_[pos >> 1];
On 2012/07/22 23:27:33, srdjan wrote:
> pos / 2 is clearer, IMHO.

Done.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
File runtime/vm/flow_graph_allocator.h (right):

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.h:66: Instruction* InstructionAt(intptr_t pos);
On 2012/07/22 15:09:24, srdjan wrote:
> const

Done.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.h:67: bool IsBlockEntry(intptr_t pos);
On 2012/07/22 15:09:24, srdjan wrote:
> const

Done.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.h:214: private:
On 2012/07/22 15:09:24, srdjan wrote:
> Add DISALLOW_COPY_AND_ASSIGN

Done.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.h:215: intptr_t pos_;
On 2012/07/22 15:09:24, srdjan wrote:
> const ?

Done.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.h:249: // UseInterval* Split(intptr_t pos);
On 2012/07/22 15:09:24, srdjan wrote:
> Delete

Done.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.h:257: };
On 2012/07/22 15:09:24, srdjan wrote:
> Add DISALLOW_COPY_AND_ASSIGN

Done.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.h:284: UsePosition* first_hinted_use_;
On 2012/07/22 15:09:24, srdjan wrote:
> Add DISALLOW_COPY_AND_ASSIGN

Done.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/flow_gra...
runtime/vm/flow_graph_allocator.h:354: AllocationFinger finger_;
On 2012/07/22 15:09:24, srdjan wrote:
> Add DISALLOW_COPY_AND_ASSIGN

Done.

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/intermed...
File runtime/vm/intermediate_language_x64.cc (right):

https://chromiumcodereview.appspot.com/10800037/diff/6001/runtime/vm/intermed...
runtime/vm/intermediate_language_x64.cc:1458: summary->set_temp(0,
Location::RegisterLocation(R10));
On 2012/07/22 15:09:24, srdjan wrote:
> Why R10?

It should be any fixed register. Replaced with RAX.

https://chromiumcodereview.appspot.com/10800037/diff/6001/tools/gyp/configura...
File tools/gyp/configurations_make.gypi (right):

https://chromiumcodereview.appspot.com/10800037/diff/6001/tools/gyp/configura...
tools/gyp/configurations_make.gypi:4: 
On 2012/07/22 15:09:24, srdjan wrote:
> Remove this file from the CL.

Will be done at the last stage. Unfortunately I could not find an easy way to
customize the build to compile Debug build without optimizations. Which
seriously impacts debugging experience.

[srdjan, 2012-07-24 15:11:19]

LGTM

https://chromiumcodereview.appspot.com/10800037/diff/6001/tools/gyp/configura...
File tools/gyp/configurations_make.gypi (right):

https://chromiumcodereview.appspot.com/10800037/diff/6001/tools/gyp/configura...
tools/gyp/configurations_make.gypi:4: 
On 2012/07/24 12:26:42, Vyacheslav Egorov (Google) wrote:
> On 2012/07/22 15:09:24, srdjan wrote:
> > Remove this file from the CL.
> 
> Will be done at the last stage. Unfortunately I could not find an easy way to
> customize the build to compile Debug build without optimizations. Which
> seriously impacts debugging experience. 

I have the same issue. Two solutions:
a) Create CL in dart/runtime, then it does not include anything outside runtime
directory
b) Manually modify the CL to move the file outside the CL.

[Kevin Millikin (Google), 2012-07-24 15:20:51]

It looks OK.

http://codereview.chromium.org/10800037/diff/9016/runtime/vm/flow_graph_alloc...
File runtime/vm/flow_graph_allocator.cc (right):

http://codereview.chromium.org/10800037/diff/9016/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:50: static intptr_t ToParallelMove(intptr_t
pos) {
I prefer ToPreviousParallelMove.

http://codereview.chromium.org/10800037/diff/9016/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:68: blocked_cpu_regs_[reg] = false;
blocked_cpu_regs_ will be zero initialized if you put it in the intializer list
:)

http://codereview.chromium.org/10800037/diff/9016/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:251: // Live ranges are being build by
visiting instructions in post-order.
That doesn't have anything to do with postorder.  It's just because they are
visited in reverse of the instruction order (whatever that is).

I don't know what perpend is, either.

http://codereview.chromium.org/10800037/diff/9016/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:342: next_sibling()->Print();
Ha ha.  Cute.  Should probably just use the while loop instead of tail
recursion, even for a printing routine.

http://codereview.chromium.org/10800037/diff/9016/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:385: while (current != block) {
You can use the backward instruction iterator if you teach ProcessOneInstruction
to ignore Goto.

http://codereview.chromium.org/10800037/diff/9016/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:435: // All uses are recorded at the position
of parallel move preceding goto.
I have a feeling that the implicit and explicit parallel moves are going to get
messy.  We should come up with different terminology to describe this one used
to resolve phis.

Or if we want to be really cute, fold it into the goto.

http://codereview.chromium.org/10800037/diff/9016/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:495: for (intptr_t j = 0; j < phis->length();
j++) {
j?  How about something like phi_idx or phi_index.

http://codereview.chromium.org/10800037/diff/9016/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:508: range->DefineAt(pos);  // Shorten live
range.
Is this really shortening it, or is pos == the assumed value?

http://codereview.chromium.org/10800037/diff/9016/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:510: for (intptr_t k = 0; k <
phi->InputCount(); k++) {
k?  How about pred_idx or something.

http://codereview.chromium.org/10800037/diff/9016/runtime/vm/flow_graph_alloc...
File runtime/vm/flow_graph_allocator.h (right):

http://codereview.chromium.org/10800037/diff/9016/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.h:114: // parts of interfering live ranges. 
Place non-spilled parts into
'spliting' -> 'splitting'.  Last sentence is a fragment.

[Vyacheslav Egorov (Google), 2012-07-24 16:01:00]

Thanks. Addressed almost all of comments.

http://codereview.chromium.org/10800037/diff/9016/runtime/vm/flow_graph_alloc...
File runtime/vm/flow_graph_allocator.cc (right):

http://codereview.chromium.org/10800037/diff/9016/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:50: static intptr_t ToParallelMove(intptr_t
pos) {
On 2012/07/24 15:20:51, kmillikin wrote:
> I prefer ToPreviousParallelMove.

This would be confusing: if position is the parallel move then result is the
same parallel move, not the one before it.

[this might change if we decide to allow splitting in every position]

http://codereview.chromium.org/10800037/diff/9016/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:68: blocked_cpu_regs_[reg] = false;
On 2012/07/24 15:20:51, kmillikin wrote:
> blocked_cpu_regs_ will be zero initialized if you put it in the intializer
list
> :)

Done.

http://codereview.chromium.org/10800037/diff/9016/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:251: // Live ranges are being build by
visiting instructions in post-order.
On 2012/07/24 15:20:51, kmillikin wrote:
> That doesn't have anything to do with postorder.  It's just because they are
> visited in reverse of the instruction order (whatever that is).
> 
> I don't know what perpend is, either.

Well we are visiting blocks in post order (and instruction order is actually a
reverse post-order). So I am not sure why you say that this has nothing to do
with post order.

http://codereview.chromium.org/10800037/diff/9016/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:435: // All uses are recorded at the position
of parallel move preceding goto.
On 2012/07/24 15:20:51, kmillikin wrote:
> I have a feeling that the implicit and explicit parallel moves are going to
get
> messy.  We should come up with different terminology to describe this one used
> to resolve phis.
> 
> Or if we want to be really cute, fold it into the goto.

There is not distinction between implicit and explicit parallel moves right now.
Every parallel move has a position (even one).

http://codereview.chromium.org/10800037/diff/9016/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:495: for (intptr_t j = 0; j < phis->length();
j++) {
On 2012/07/24 15:20:51, kmillikin wrote:
> j?  How about something like phi_idx or phi_index.

Done.

http://codereview.chromium.org/10800037/diff/9016/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:508: range->DefineAt(pos);  // Shorten live
range.
On 2012/07/24 15:20:51, kmillikin wrote:
> Is this really shortening it, or is pos == the assumed value?

Actually since pos is equal to start of the block there is no shortening. It's
here just to keep it uniform.

http://codereview.chromium.org/10800037/diff/9016/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:510: for (intptr_t k = 0; k <
phi->InputCount(); k++) {
On 2012/07/24 15:20:51, kmillikin wrote:
> k?  How about pred_idx or something.

Done.

http://codereview.chromium.org/10800037/diff/9016/runtime/vm/flow_graph_alloc...
File runtime/vm/flow_graph_allocator.h (right):

http://codereview.chromium.org/10800037/diff/9016/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.h:114: // parts of interfering live ranges. 
Place non-spilled parts into
On 2012/07/24 15:20:51, kmillikin wrote:
> 'spliting' -> 'splitting'.  Last sentence is a fragment.

Done.