Allow deoptimization from states with spilled values.

Revert instruction numbering scheme to an instruction start (2*k) - instruction end (2*k + 1) one. Current instruction numbering scheme does not capture interference between temporaries and inputs correctly which in rare cases causes allocation of the same register both to the temp and to the input register.

Allow live range splitting at every position.

Don't reuse phi-resolution parallel move for connecting live ranges or meeting register constraints, this might cause conflicts between moves.

Allow deoptimization with environments containing spilled values.

R=kmillikin@google.com
BUG=

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

[Kevin Millikin (Google), 2012-07-30 11:34:40]

lgtm

[Vyacheslav Egorov (Google), 2012-07-31 00:03:14]

+srdjan

Running tests with increased coverage revealed a couple of bugs in the register
allocator. 

Please take a look.

[srdjan, 2012-07-31 00:18:11]

LGTM with comments

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

https://chromiumcodereview.appspot.com/10831070/diff/4/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:900: CreateParallelMoveBefore(last,
last->lifetime_position());
indent 4 spaces

https://chromiumcodereview.appspot.com/10831070/diff/4/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:917: instructions_[last->lifetime_position()
/ 2] = move;
Add assert that instructions_[last->lifetime_position() / 2] is Goto
instruction.

This code looks a little bit fragile to me. Would it be better to have Goto
refer to move and the logic of replacing would be in AddMoveAt?

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

https://chromiumcodereview.appspot.com/10831070/diff/4/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.h:61: // end position we can distinguish between
instructions that need value
Fix comment: "..by placing a use at the start or end the end position.."

[srdjan, 2012-07-31 00:18:12]

LGTM with comments

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

https://chromiumcodereview.appspot.com/10831070/diff/4/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:900: CreateParallelMoveBefore(last,
last->lifetime_position());
indent 4 spaces

https://chromiumcodereview.appspot.com/10831070/diff/4/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:917: instructions_[last->lifetime_position()
/ 2] = move;
Add assert that instructions_[last->lifetime_position() / 2] is Goto
instruction.

This code looks a little bit fragile to me. Would it be better to have Goto
refer to move and the logic of replacing would be in AddMoveAt?

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

https://chromiumcodereview.appspot.com/10831070/diff/4/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.h:61: // end position we can distinguish between
instructions that need value
Fix comment: "..by placing a use at the start or end the end position.."

[Vyacheslav Egorov (Google), 2012-07-31 11:17:07]

Thanks. Landing.

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

https://chromiumcodereview.appspot.com/10831070/diff/4/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:917: instructions_[last->lifetime_position()
/ 2] = move;
On 2012/07/31 00:18:15, srdjan wrote:
> Add assert that instructions_[last->lifetime_position() / 2] is Goto
> instruction.
> 
> This code looks a little bit fragile to me. Would it be better to have Goto
> refer to move and the logic of replacing would be in AddMoveAt?

Assertion added. 

I agree the code is a little bit fragile. But the problem with moving logic to
AddMoveAt is that there is no easy way to distinguish ParallelMove created for
phi-resolution from normal parallel move added by AddMoveAt.

I'll leave it like this for now, maybe later we can come up with a different
solution, e.g. I am thinking if we can just hind parallel move for
phi-resolution into Goto instruction itself.

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

https://chromiumcodereview.appspot.com/10831070/diff/4/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.h:61: // end position we can distinguish between
instructions that need value
On 2012/07/31 00:18:15, srdjan wrote:
> Fix comment: "..by placing a use at the start or end the end position.."

Done.