Skeleton of a linear scan register allocator.

Skeleton of a linear scan register allocator.

BUG=
TEST=

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

[Vyacheslav Egorov (Google), 2012-07-10 17:56:36]

Please take a look. 

This is just a skeleton. But it can allocate registers correctly when there is
no spilling or control flow resolution involved. It also support deopts. (so if
register allocation succeeds than generated code should be fully functional).

[Vyacheslav Egorov (Google), 2012-07-10 18:02:05]

Couple of comments about code that is commented out in this CL.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_builder.cc
File runtime/vm/flow_graph_builder.cc (right):

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_builder....
runtime/vm/flow_graph_builder.cc:1077: new
CheckStackOverflowComp(node->token_pos(), owner()->try_index()));
I temporarily disabled this to test register allocation when loop is present.
Currently CheckStackOverflow is marked as call so it prevents us from carrying
_any_ values in registers across back edge, which is wrong. 

I will revert it, but we will need to handle this separately by creating an
"unlikely call" utility that allows instructions to spill all registers manually
on the slow path.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_optimize...
File runtime/vm/flow_graph_optimizer.cc (right):

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_optimize...
runtime/vm/flow_graph_optimizer.cc:531: // TODO(vegorov): land a separate CL to
fix the fusion. Now it should remove
I disabled this locally because our branch fusion confuses register allocator
(normal instruction becomes a branch).

I'll submit a separate CL tomorrow that makes our fusion register allocation
friendly (no we can remove comparison from the graph).

[srdjan, 2012-07-10 23:27:54]

LGTM with comments/questions.

I think you should have split the CL into smaller ones, especially the changes
addressing simple cleanups (e.g., Location::IsUnallocated(), IsRegister())

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

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.cc:30:
live_out_(builder->postorder_block_entries().length()),
builder->postorder_block_entries().length() can be replaced with
block_order.length(), which is shorter.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.cc:209: ASSERT((start_ <= pos) && (pos <=
end_));  // TODO(vegorov) uses inclusion?
In comment you wrote [start, end) ?

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.cc:234: if (head_ != NULL && (head_->start_ ==
end)) {
parenthesis

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.cc:508: pos -= 2;
Why -2?

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.cc:548: 
Add comment, something like: Computes positions of each instructions and
initialized ParallelMoves with empty moves.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.cc:566: pos += 2;
Why +2?

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.cc:572: if (block->IsJoinEntry() &&
block->AsJoinEntry()->phi_count() > 0) {
parenthesis

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.cc:907: cpu_regs_[RBP] = kPermanentlyBlocked;
Use SPREG and FPREG instead of RSP and RBP.

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

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.h:49: FlowGraphBuilder* builder_;
Move all instance fields together, to the end. The builder is used only to be
able to call Bailout, isn't it? Maybe add a TODO to remove builder once Bailouts
are removed.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.h:118: static const intptr_t kInstructionTagMask
= 0x3;
If you make the upper three enum, you could use types instead of intptr_t.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.h:121: static intptr_t FlagForUse(Location* loc)
{
const Location&

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.h:125: loc->policy() ==
Location::kSameAsFirstInput) {
Add parenthesis

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.h:138: : pos_(pos << kPositionShift),
This shift is wasted if instr != NULL. Maybe set it to -1, and do the shift if
instr == NULL

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.h:196: // single list (and not split between
UseIntervals).
Please describe what are start and end values (what is position?).

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.h:217: bool Contains(intptr_t pos) {
const

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_compiler.cc
File runtime/vm/flow_graph_compiler.cc (right):

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_compiler...
runtime/vm/flow_graph_compiler.cc:56: ASSERT(assembler != NULL);
You could also ASSERT(is_optimizing_ || !is_ssa_);

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_compiler...
File runtime/vm/flow_graph_compiler_x64.cc (right):

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_compiler...
runtime/vm/flow_graph_compiler_x64.cc:42: Address(RBP,
ParsedFunction::kFirstLocalSlotIndex * kWordSize));
How do you handle incoming parameters and incoming optional arguments which are
copied? I assume the following code handles only non-parameter locals.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_compiler...
runtime/vm/flow_graph_compiler_x64.cc:1107: : compiler_(compiler), moves_(32) {}
Some methods should be shared, I guess.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_compiler...
runtime/vm/flow_graph_compiler_x64.cc:1136: ParallelMoveInstr* parallel_move) {
indent 4 spaces

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_compiler...
runtime/vm/flow_graph_compiler_x64.cc:1215: #undef __
One undef too many.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_compiler...
runtime/vm/flow_graph_compiler_x64.cc:1224: __ movq(destination.reg(),
source.reg());
indent

http://codereview.chromium.org/10696151/diff/1/runtime/vm/il_printer.cc
File runtime/vm/il_printer.cc (right):

http://codereview.chromium.org/10696151/diff/1/runtime/vm/il_printer.cc#newco...
runtime/vm/il_printer.cc:67: if (print_locations_ && instr->locs() != NULL) {
Add parenthesis.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/il_printer.cc#newco...
runtime/vm/il_printer.cc:679: f->Print(" [%s]", locations_[i].Name());
Add parenthesis, fix indent.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/intermediate_langua...
File runtime/vm/intermediate_language.h (right):

http://codereview.chromium.org/10696151/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:1844: intptr_t pos_;
Please add comments:
cid_;   // Computation id.
pos_;  // ??

http://codereview.chromium.org/10696151/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:1937: intptr_t end_pos_;
Please add comment what the two fields are good for.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:2345: MoveOperands(Location dest, Location
src) : dest_(dest), src_(src) { }
Should you ASSERT which types of Location's are allowed?

http://codereview.chromium.org/10696151/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:2351: Location* dest_slot() { return &dest_;
}
Why are those called slots? Since src() and dest(), I would rather call the
getters src_ptr and dest_ptr.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:2360: return dest;
Wouldn't it be much simpler to use a field bool is_pending_?  Should it be
called MarkInProgress instead? I would read Pending as something that has to
happen yet, maybe has not started yet or is in progress.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:2372: // True if this move a move into the
given destination location.
Fix comment.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:2385: }
This means that every IsPending is also IsIgnored?

http://codereview.chromium.org/10696151/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:2390: ASSERT(!src_.IsInvalid() ||
dest_.IsInvalid());
Can you add this assert to MarkPending, ClearPending as well?

http://codereview.chromium.org/10696151/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:2402: explicit ParallelMoveInstr(intptr_t
move_count) : moves_(move_count) {
I think passing the move_count for optimization purposes does not bring much,
instead you could give it default value of 4 or similar.  Unless you want to
check that we do not emit more moves than move_count, in which case I would add
an ASSERT to AddMove (and which would require to add a capacity getter to
GrowableArray). Maybe we could add a limited GrowableArray that cannot grow past
its capacity?

http://codereview.chromium.org/10696151/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:2414: GrowableArray<MoveOperands> moves_;
Why is this not MoveOperands* ?

http://codereview.chromium.org/10696151/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:2438: const GrowableArray<Location>*
locations() const {
Is it really necessary to have const overloaded getters?

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

http://codereview.chromium.org/10696151/diff/1/runtime/vm/locations.cc#newcode38
runtime/vm/locations.cc:38: #endif
Move cpu_reg_names to constants_<arch>.h

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

http://codereview.chromium.org/10696151/diff/1/runtime/vm/locations.h#newcode49
runtime/vm/locations.h:49: return value_ == 0;
s/0/kInvalidLocation/

http://codereview.chromium.org/10696151/diff/1/runtime/vm/locations.h#newcode53
runtime/vm/locations.h:53: static const intptr_t kConstantMask = 0x3;
Eventually move this definition between the comment and enum Kind.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/locations.h#newcode60
runtime/vm/locations.h:60: Location loc(reinterpret_cast<intptr_t>(&obj) |
kConstant);
Why no uword instead of intptr_t?

http://codereview.chromium.org/10696151/diff/1/runtime/vm/locations.h#newcode122
runtime/vm/locations.h:122: return value_ == other.value_;
This does not work for kConstant. Should two constants with two identical
RawObjects, but different handles be the same? Please add comment.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/locations.h#newcode126
runtime/vm/locations.h:126: explicit Location(intptr_t value) : value_(value) {
}
Why not uword value?

http://codereview.chromium.org/10696151/diff/1/runtime/vm/locations.h#newcode148
runtime/vm/locations.h:148: uword value_;
Explain that this can be Kind or an encoded Object handle

[Vyacheslav Egorov (Google), 2012-07-11 13:27:58]

please take another look

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

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.cc:30:
live_out_(builder->postorder_block_entries().length()),
On 2012/07/10 23:27:54, srdjan wrote:
> builder->postorder_block_entries().length() can be replaced with
> block_order.length(), which is shorter.

Done.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.cc:209: ASSERT((start_ <= pos) && (pos <=
end_));  // TODO(vegorov) uses inclusion?
On 2012/07/10 23:27:54, srdjan wrote:
> In comment you wrote [start, end) ?

Last use is still attributed to the UseInterval because if use interval gets a
location L then value stays at this location from start and until the end (and
it will be moved to somewhere else or "die" at end) so use that has position
equal to end has to take it from the L, that's why <=. I agree it might be a bit
confusing.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.cc:234: if (head_ != NULL && (head_->start_ ==
end)) {
On 2012/07/10 23:27:54, srdjan wrote:
> parenthesis

Done.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.cc:508: pos -= 2;
On 2012/07/10 23:27:54, srdjan wrote:
> Why -2?

Each instruction occupies two positions. See comment for NumberInstructions() in
the header.

I added a comment, but I am a bit hesitant to make a constant (e.g.
kPositionsPerInstruction), because then I would have to express constant 1 in
some cases as kPositionsPerInstruction / 2 which makes very little sense.

In V8 I solved the problem by ecapsulating this into LifetimePosition class that
had methods like

LifetimePosition NextInstruction() const;
LifetimePosition PrevInstruction() const;
LifetimePosition InstructionStart() const;
LifetimePosition InstructionEnd() const;
intptr_t Value();

so pos - 1 could be expressed as

pos.PrevInstruction().InstructionEnd() which is more readable if one is not
familiar with how positions are calculated but a bit wordy.

Also operator overloading is forbiden so we had to compare positions like

pos.Value() == other.Value()

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.cc:548: 
On 2012/07/10 23:27:54, srdjan wrote:
> Add comment, something like: Computes positions of each instructions and
> initialized ParallelMoves with empty moves.

Added comment in the header file.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.cc:566: pos += 2;
On 2012/07/10 23:27:54, srdjan wrote:
> Why +2?

see above.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.cc:572: if (block->IsJoinEntry() &&
block->AsJoinEntry()->phi_count() > 0) {
On 2012/07/10 23:27:54, srdjan wrote:
> parenthesis

Done.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.cc:907: cpu_regs_[RBP] = kPermanentlyBlocked;
On 2012/07/10 23:27:54, srdjan wrote:
> Use SPREG and FPREG instead of RSP and RBP.

Done.

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

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.h:49: FlowGraphBuilder* builder_;
On 2012/07/10 23:27:54, srdjan wrote:
> Move all instance fields together, to the end. The builder is used only to be
> able to call Bailout, isn't it? Maybe add a TODO to remove builder once
Bailouts
> are removed.

Done. Moved fields down. Added comments to each new field.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.h:118: static const intptr_t kInstructionTagMask
= 0x3;
On 2012/07/10 23:27:54, srdjan wrote:
> If you make the upper three enum, you could use types instead of intptr_t.

Switched to enum. 

This is a pretty ugly place. I'll try to clean it up in upcoming CLs.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.h:121: static intptr_t FlagForUse(Location* loc)
{
On 2012/07/10 23:27:54, srdjan wrote:
> const Location&

Done.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.h:125: loc->policy() ==
Location::kSameAsFirstInput) {
On 2012/07/10 23:27:54, srdjan wrote:
> Add parenthesis

Done.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.h:138: : pos_(pos << kPositionShift),
On 2012/07/10 23:27:54, srdjan wrote:
> This shift is wasted if instr != NULL. Maybe set it to -1, and do the shift if
> instr == NULL

instr != NULL is considered an unlikely occasion that is why I decided to do
shift ahead of time.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.h:196: // single list (and not split between
UseIntervals).
On 2012/07/10 23:27:54, srdjan wrote:
> Please describe what are start and end values (what is position?).

Expanded comment. Added comment to NumberInstructions to describe how positions
are assigned.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.h:217: bool Contains(intptr_t pos) {
On 2012/07/10 23:27:54, srdjan wrote:
> const

Done.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_compiler.cc
File runtime/vm/flow_graph_compiler.cc (right):

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_compiler...
runtime/vm/flow_graph_compiler.cc:56: ASSERT(assembler != NULL);
On 2012/07/10 23:27:54, srdjan wrote:
> You could also ASSERT(is_optimizing_ || !is_ssa_);

Done.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_compiler...
File runtime/vm/flow_graph_compiler_x64.cc (right):

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_compiler...
runtime/vm/flow_graph_compiler_x64.cc:42: Address(RBP,
ParsedFunction::kFirstLocalSlotIndex * kWordSize));
On 2012/07/10 23:27:54, srdjan wrote:
> How do you handle incoming parameters and incoming optional arguments which
are
> copied? I assume the following code handles only non-parameter locals.

Positional parameters are in the environment as well, so it should work.
(however regalloc will bailout because this parameters do not have definitions
in the graph; I am planning to address this once we land skeleton).

SSA building will bailout if function has optional arguments.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_compiler...
runtime/vm/flow_graph_compiler_x64.cc:1107: : compiler_(compiler), moves_(32) {}
On 2012/07/10 23:27:54, srdjan wrote:
> Some methods should be shared, I guess.

Yes this is the intent. Done when porting to ia32.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_compiler...
runtime/vm/flow_graph_compiler_x64.cc:1136: ParallelMoveInstr* parallel_move) {
On 2012/07/10 23:27:54, srdjan wrote:
> indent 4 spaces

Done.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_compiler...
runtime/vm/flow_graph_compiler_x64.cc:1215: #undef __
On 2012/07/10 23:27:54, srdjan wrote:
> One undef too many.

Done.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_compiler...
runtime/vm/flow_graph_compiler_x64.cc:1224: __ movq(destination.reg(),
source.reg());
On 2012/07/10 23:27:54, srdjan wrote:
> indent

Done.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_compiler...
runtime/vm/flow_graph_compiler_x64.cc:1228: if (value.IsSmi()) {
This is apparently not needed assembler does the same internally.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/il_printer.cc
File runtime/vm/il_printer.cc (right):

http://codereview.chromium.org/10696151/diff/1/runtime/vm/il_printer.cc#newco...
runtime/vm/il_printer.cc:67: if (print_locations_ && instr->locs() != NULL) {
On 2012/07/10 23:27:54, srdjan wrote:
> Add parenthesis.

Done.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/il_printer.cc#newco...
runtime/vm/il_printer.cc:679: f->Print(" [%s]", locations_[i].Name());
On 2012/07/10 23:27:54, srdjan wrote:
> Add parenthesis, fix indent.

Done.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/intermediate_langua...
File runtime/vm/intermediate_language.h (right):

http://codereview.chromium.org/10696151/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:1844: intptr_t pos_;
On 2012/07/10 23:27:54, srdjan wrote:
> Please add comments:
> cid_;   // Computation id.
> pos_;  // ??

Done. Actually currently this positions are rarely needed. 
So we might eliminate them entirely instead of making every instructions one
word bigger.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:1937: intptr_t end_pos_;
On 2012/07/10 23:27:54, srdjan wrote:
> Please add comment what the two fields are good for.

Done.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:2345: MoveOperands(Location dest, Location
src) : dest_(dest), src_(src) { }
On 2012/07/10 23:27:54, srdjan wrote:
> Should you ASSERT which types of Location's are allowed?

It's pretty hard because register allocator fills most of it incrementally.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:2351: Location* dest_slot() { return &dest_;
}
On 2012/07/10 23:27:54, srdjan wrote:
> Why are those called slots? Since src() and dest(), I would rather call the
> getters src_ptr and dest_ptr.

I called them _ptr before but then changed to slot to better convey semantics:
return a place where a real location will be placed by the allocator hence
"slot".

http://codereview.chromium.org/10696151/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:2360: return dest;
On 2012/07/10 23:27:54, srdjan wrote:
> Wouldn't it be much simpler to use a field bool is_pending_?  Should it be
> called MarkInProgress instead? I would read Pending as something that has to
> happen yet, maybe has not started yet or is in progress.

I suspect it will be simpler, but bool will waste a word in every parallel move.


(implementation of parallel move resolution is copied from V8 keeping names sans
differences between Dart VM Location and V8's LOperands).

http://codereview.chromium.org/10696151/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:2372: // True if this move a move into the
given destination location.
On 2012/07/10 23:27:54, srdjan wrote:
> Fix comment.

Oh, yeah, this cost me some pain in debugging. Initially I implemented the
method based on the comment, which did not work, but once I fixed implementation
I forgot to fix the comment.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:2385: }
On 2012/07/10 23:27:54, srdjan wrote:
> This means that every IsPending is also IsIgnored?

yes.

removed IsIgnored, it was only used from IsRedundant which is used only to form
list of initial moves.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:2390: ASSERT(!src_.IsInvalid() ||
dest_.IsInvalid());
On 2012/07/10 23:27:54, srdjan wrote:
> Can you add this assert to MarkPending, ClearPending as well?

Done.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:2402: explicit ParallelMoveInstr(intptr_t
move_count) : moves_(move_count) {
On 2012/07/10 23:27:54, srdjan wrote:
> I think passing the move_count for optimization purposes does not bring much,
> instead you could give it default value of 4 or similar.  Unless you want to
> check that we do not emit more moves than move_count, in which case I would
add
> an ASSERT to AddMove (and which would require to add a capacity getter to
> GrowableArray). Maybe we could add a limited GrowableArray that cannot grow
past
> its capacity?

Changed to 4 for now. Can optimize memory usage later.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:2414: GrowableArray<MoveOperands> moves_;
On 2012/07/10 23:27:54, srdjan wrote:
> Why is this not MoveOperands* ?

I am not sure what additional indirection buys us here.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:2438: const GrowableArray<Location>*
locations() const {
On 2012/07/10 23:27:54, srdjan wrote:
> Is it really necessary to have const overloaded getters?

Deoptimization stub references const Environment* so I need a const version of
this getter. I can't remove non-const getter because register allocator want to
get hold of non-const slots inside the array.

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

http://codereview.chromium.org/10696151/diff/1/runtime/vm/locations.cc#newcode38
runtime/vm/locations.cc:38: #endif
On 2012/07/10 23:27:54, srdjan wrote:
> Move cpu_reg_names to constants_<arch>.h

Do we really want to have arrays declarations in the header file?

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

http://codereview.chromium.org/10696151/diff/1/runtime/vm/locations.h#newcode49
runtime/vm/locations.h:49: return value_ == 0;
On 2012/07/10 23:27:54, srdjan wrote:
> s/0/kInvalidLocation/

Done.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/locations.h#newcode53
runtime/vm/locations.h:53: static const intptr_t kConstantMask = 0x3;
On 2012/07/10 23:27:54, srdjan wrote:
> Eventually move this definition between the comment and enum Kind.

Done.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/locations.h#newcode60
runtime/vm/locations.h:60: Location loc(reinterpret_cast<intptr_t>(&obj) |
kConstant);
On 2012/07/10 23:27:54, srdjan wrote:
> Why no uword instead of intptr_t?

Fixed! Thanks.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/locations.h#newcode122
runtime/vm/locations.h:122: return value_ == other.value_;
On 2012/07/10 23:27:54, srdjan wrote:
> This does not work for kConstant. Should two constants with two identical
> RawObjects, but different handles be the same? Please add comment.

Added a comment and assertion. Constants are really encoded into locations only
because we need to have them as sources in parallel moves. Alternative would be
to leave locations for real locations and somehow fit constants into
MoveOperands instead. [might be a cleaner solution actually].

http://codereview.chromium.org/10696151/diff/1/runtime/vm/locations.h#newcode126
runtime/vm/locations.h:126: explicit Location(intptr_t value) : value_(value) {
}
On 2012/07/10 23:27:54, srdjan wrote:
> Why not uword value?

Mea culpa! Compiler did not complain and I already forgot that value_ is uword.

Fixed.

http://codereview.chromium.org/10696151/diff/1/runtime/vm/locations.h#newcode148
runtime/vm/locations.h:148: uword value_;
On 2012/07/10 23:27:54, srdjan wrote:
> Explain that this can be Kind or an encoded Object handle

Done.

[srdjan, 2012-07-11 17:22:31]

LGTM

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

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.cc:508: pos -= 2;
On 2012/07/11 13:27:58, Vyacheslav Egorov (Google) wrote:
> On 2012/07/10 23:27:54, srdjan wrote:
> > Why -2?
> 
> Each instruction occupies two positions. See comment for NumberInstructions()
in
> the header.
> 
> I added a comment, but I am a bit hesitant to make a constant (e.g.
> kPositionsPerInstruction), because then I would have to express constant 1 in
> some cases as kPositionsPerInstruction / 2 which makes very little sense.
> 
> In V8 I solved the problem by ecapsulating this into LifetimePosition class
that
> had methods like
> 
> LifetimePosition NextInstruction() const;
> LifetimePosition PrevInstruction() const;
> LifetimePosition InstructionStart() const;
> LifetimePosition InstructionEnd() const;
> intptr_t Value();
> 
> so pos - 1 could be expressed as
> 
> pos.PrevInstruction().InstructionEnd() which is more readable if one is not
> familiar with how positions are calculated but a bit wordy.
> 
> Also operator overloading is forbiden so we had to compare positions like
> 
> pos.Value() == other.Value() 
> 
> 
> 
>  

Using -2, -1 is more readable in this case.

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

http://codereview.chromium.org/10696151/diff/1/runtime/vm/flow_graph_allocato...
runtime/vm/flow_graph_allocator.h:138: : pos_(pos << kPositionShift),
On 2012/07/11 13:27:58, Vyacheslav Egorov (Google) wrote:
> On 2012/07/10 23:27:54, srdjan wrote:
> > This shift is wasted if instr != NULL. Maybe set it to -1, and do the shift
if
> > instr == NULL
> 
> instr != NULL is considered an unlikely occasion that is why I decided to do
> shift ahead of time.

Add comment, otherwise 'somebody' may clean it up accidentally ;-).

http://codereview.chromium.org/10696151/diff/1/runtime/vm/intermediate_langua...
File runtime/vm/intermediate_language.h (right):

http://codereview.chromium.org/10696151/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:2360: return dest;
On 2012/07/11 13:27:58, Vyacheslav Egorov (Google) wrote:
> On 2012/07/10 23:27:54, srdjan wrote:
> > Wouldn't it be much simpler to use a field bool is_pending_?  Should it be
> > called MarkInProgress instead? I would read Pending as something that has to
> > happen yet, maybe has not started yet or is in progress.
> 
> I suspect it will be simpler, but bool will waste a word in every parallel
move.
> 
> 
> (implementation of parallel move resolution is copied from V8 keeping names
sans
> differences between Dart VM Location and V8's LOperands).

OK

http://codereview.chromium.org/10696151/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:2414: GrowableArray<MoveOperands> moves_;
On 2012/07/11 13:27:58, Vyacheslav Egorov (Google) wrote:
> On 2012/07/10 23:27:54, srdjan wrote:
> > Why is this not MoveOperands* ?
> 
> I am not sure what additional indirection buys us here.

It is more fragile, since it can get suddenly really slow if somebody adds
fields to MoveOperands. How about adding a comment/warning to MoveOperands?

http://codereview.chromium.org/10696151/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:2438: const GrowableArray<Location>*
locations() const {
On 2012/07/11 13:27:58, Vyacheslav Egorov (Google) wrote:
> On 2012/07/10 23:27:54, srdjan wrote:
> > Is it really necessary to have const overloaded getters?
> 
> Deoptimization stub references const Environment* so I need a const version of
> this getter. I can't remove non-const getter because register allocator want
to
> get hold of non-const slots inside the array.

How about renaming it to const_locations() then ?

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

http://codereview.chromium.org/10696151/diff/1/runtime/vm/locations.cc#newcode38
runtime/vm/locations.cc:38: #endif
On 2012/07/11 13:27:58, Vyacheslav Egorov (Google) wrote:
> On 2012/07/10 23:27:54, srdjan wrote:
> > Move cpu_reg_names to constants_<arch>.h
> 
> Do we really want to have arrays declarations in the header file?

We do not want to have if def targets in shared code.

You could define a functions in constants_arch.h that converts register to
string. (similar to assembler-x64.h in v8)

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

http://codereview.chromium.org/10696151/diff/9001/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.cc:39: for (intptr_t i = 0; i < vreg_count_;
i++) live_ranges_.Add(NULL);
Initialize cpu_regs_ elements to NULL

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

http://codereview.chromium.org/10696151/diff/9001/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.h:73: intptr_t use,
Please describe what are def and use. intptr_t sometime represents a virtual
register sometimes a position. Maybe we should use value types for those in
order to eliminate confusion (later CL)?

http://codereview.chromium.org/10696151/diff/9001/runtime/vm/flow_graph_alloc...
runtime/vm/flow_graph_allocator.h:91: // TODO(vegorov): this field is used only
to call Bailout. remove when
s/remove/Remove/

http://codereview.chromium.org/10696151/diff/9001/runtime/vm/flow_graph_build...
File runtime/vm/flow_graph_builder.cc (right):

http://codereview.chromium.org/10696151/diff/9001/runtime/vm/flow_graph_build...
runtime/vm/flow_graph_builder.cc:1075: #if 0
Enable stack overflow check before submitting

http://codereview.chromium.org/10696151/diff/9001/runtime/vm/flow_graph_compi...
File runtime/vm/flow_graph_compiler_ia32.cc (right):

http://codereview.chromium.org/10696151/diff/9001/runtime/vm/flow_graph_compi...
runtime/vm/flow_graph_compiler_ia32.cc:32: if (deoptimization_env_ == NULL) {
ASSERT in ia32 that deoptimization_env_ == NULL (since else not implemented)

http://codereview.chromium.org/10696151/diff/9001/runtime/vm/flow_graph_optim...
File runtime/vm/flow_graph_optimizer.cc (right):

http://codereview.chromium.org/10696151/diff/9001/runtime/vm/flow_graph_optim...
runtime/vm/flow_graph_optimizer.cc:588: #if 0
Enable once synced with branch fusion fix