Add support for fixed parameters in the register allocator.

Add support for fixed parameters in the register allocator.

This remove bailout for functions with non-zero number of non-fixed parameters and increases our coverage. 

SpillSlot location was renamed into StackSlot location and now allows to address spill slots (positive stack index) and incoming parameters (negative stack index).

Environment was reordered to match order of values on the stack (previously it was inversed).

Correctly reserve spill slots in the prologue of the code. Previously register allocator was allocating spill slots, but generated code did not reserve any space for them on the stack so they might have been overwritten by calls.

Fix off by one in DeoptimizationStub::GenerateCode - we were reserving one slot too many.

Change --optimization-filter flag to use substring search instead of prefix comparison, this is much more useful when VM prefixes function name with a path to the file.

BUG=
TEST=

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

[Vyacheslav Egorov (Google), 2012-07-25 19:06:27]

Please take a look.

[srdjan, 2012-07-26 00:33:56]

LGTM

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

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:142: // Process incomming parameters.
s/incomming/incoming/

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:411: // Process incomming parameters.
ditto

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

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_compiler_ia32.cc:964: const int stack_slot_count =
s/int/intptr_t/

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_compiler_ia32.cc:968: const int slot_base =
ditto

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_compiler_ia32.cc:969: is_ssa_ ? -2 :
parsed_function().first_stack_local_index();
Why is this needed? parsed_function().first_stack_local_index() returns -2
except for natives -- which we can leave unoptimized -- and methods with
optional parameters -- which we do not compile anyway. Magic number -2 is also
strange.

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

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_compiler_x64.cc:63: }
Sync this with Kevin's upcoming change.

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_compiler_x64.cc:990: is_ssa_ ? -2 :
parsed_function().first_stack_local_index();
ditto, not needed, I guess.

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/intermediat...
File runtime/vm/intermediate_language.cc (left):

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language.cc:959: ASSERT(VerifyValues(instance(),
value()));
Why remove this?

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/intermediat...
File runtime/vm/intermediate_language.h (right):

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language.h:2041: void set_spill_slot_count(intptr_t
count) {
ASSERT(count >= 0)

[Kevin Millikin (Google), 2012-07-26 09:29:08]

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

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:148: kill_[0]->Add(vreg);
It probably doesn't make a big difference to anything, but I don't understand
why the incoming parameters are not live at the graph entry.

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

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_builder.cc:2290: const intptr_t fixed_param_count =
fixed_parameter_count is barely longer.

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_builder.cc:2552: ParameterInstr* param = new
ParameterInstr(i - fixed_param_count);
I'm not thrilled with negative parameter indices here.  What is the index of the
leftmost parameter?

By the way, it's clearer to directly use the index you care about instead of
deriving it:

for (intptr i = fixed_parameter_count; i > 0; --i) {
  ParameterInstr* parameter = new ParameterInstr(i);
  ...
}

Value* null_value = new ConstantVal(Object::ZoneHandle());
while (start_env.length() < variable_count) {
  start_env.Add(null_value);
}

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_builder.cc:2571:
parsed_function().function().num_fixed_parameters());
Can this be just fixed_param[eter]_count?

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

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_compiler.cc:145: return
block_order_[0]->AsGraphEntry()->spill_slot_count();
I think it's a little weird that the spill slot count is in the graph entry. 
It's not really a property of the graph, but of a certain register allocation. 
It seems like it belongs in the compiler, or the register allocator.

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/intermediat...
File runtime/vm/intermediate_language.h (right):

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language.h:111: class AssignedVarsCollector;
Huh?

[Vyacheslav Egorov (Google), 2012-07-26 11:33:53]

comments addressed, new version uploaded.

rebasing with Kevin's change.

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

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:142: // Process incomming parameters.
On 2012/07/26 00:33:56, srdjan wrote:
> s/incomming/incoming/

Done.

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:148: kill_[0]->Add(vreg);
On 2012/07/26 09:29:08, kmillikin wrote:
> It probably doesn't make a big difference to anything, but I don't understand
> why the incoming parameters are not live at the graph entry.

It does not change anything. I just choose to define them at graph entry.

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_allocator.cc:411: // Process incomming parameters.
On 2012/07/26 00:33:56, srdjan wrote:
> ditto

Done.

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

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_builder.cc:2290: const intptr_t fixed_param_count =
On 2012/07/26 09:29:08, kmillikin wrote:
> fixed_parameter_count is barely longer.

Done.

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_builder.cc:2552: ParameterInstr* param = new
ParameterInstr(i - fixed_param_count);
On 2012/07/26 09:29:08, kmillikin wrote:
> I'm not thrilled with negative parameter indices here.  What is the index of
the
> leftmost parameter?
> 
> By the way, it's clearer to directly use the index you care about instead of
> deriving it:
> 
> for (intptr i = fixed_parameter_count; i > 0; --i) {
>   ParameterInstr* parameter = new ParameterInstr(i);
>   ...
> }
> 
> Value* null_value = new ConstantVal(Object::ZoneHandle());
> while (start_env.length() < variable_count) {
>   start_env.Add(null_value);
> }

The index of rightmost parameter is -1 and left most is fixed_parameter_count.

Changed to compute stack slot index in allocator.

Alternative would be to compute

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_builder.cc:2571:
parsed_function().function().num_fixed_parameters());
On 2012/07/26 09:29:08, kmillikin wrote:
> Can this be just fixed_param[eter]_count?

Done.

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

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_compiler.cc:145: return
block_order_[0]->AsGraphEntry()->spill_slot_count();
On 2012/07/26 09:29:08, kmillikin wrote:
> I think it's a little weird that the spill slot count is in the graph entry. 
> It's not really a property of the graph, but of a certain register allocation.

> It seems like it belongs in the compiler, or the register allocator.

Discussed offline. My reasoning is that each instruction in the graph already
owns locations (register and spill slots) at this point so attaching spill slot
count to the graph itself seems logical.

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

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_compiler_ia32.cc:964: const int stack_slot_count =
On 2012/07/26 00:33:56, srdjan wrote:
> s/int/intptr_t/

Done.

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_compiler_ia32.cc:968: const int slot_base =
On 2012/07/26 00:33:56, srdjan wrote:
> ditto

Done.

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_compiler_ia32.cc:969: is_ssa_ ? -2 :
parsed_function().first_stack_local_index();
On 2012/07/26 00:33:56, srdjan wrote:
> Why is this needed? parsed_function().first_stack_local_index() returns -2
> except for natives -- which we can leave unoptimized -- and methods with
> optional parameters -- which we do not compile anyway. Magic number -2 is also
> strange.

Removed.

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

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_compiler_x64.cc:63: }
On 2012/07/26 00:33:56, srdjan wrote:
> Sync this with Kevin's upcoming change.

Will do.

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_compiler_x64.cc:990: is_ssa_ ? -2 :
parsed_function().first_stack_local_index();
On 2012/07/26 00:33:56, srdjan wrote:
> ditto, not needed, I guess.

Done.

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/intermediat...
File runtime/vm/intermediate_language.cc (left):

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language.cc:959: ASSERT(VerifyValues(instance(),
value()));
On 2012/07/26 00:33:56, srdjan wrote:
> Why remove this?

Because it does not work for SSA form with phis.

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/intermediat...
File runtime/vm/intermediate_language.h (right):

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language.h:111: class AssignedVarsCollector;
On 2012/07/26 09:29:08, kmillikin wrote:
> Huh?

Artifacts :-). Removed.

https://chromiumcodereview.appspot.com/10828018/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language.h:2041: void set_spill_slot_count(intptr_t
count) {
On 2012/07/26 00:33:56, srdjan wrote:
> ASSERT(count >= 0)

Done.

[Vyacheslav Egorov (Google), 2012-07-26 13:16:23]

Rebased, fixed off by 1 in DeoptimizationStub::GenerateCode.

Going to land.