Implement a simple register allocator that tries to keep instruction results in registers.

Implement a simple register allocator that tries to keep instruction results in registers.

Add --optimization-filter flag that allows to disbable optimizations for all function which do not match prefix. This allows to quickly localize problems with code generation.

BUG=
TEST=

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

[Vyacheslav Egorov (Google), 2012-06-18 14:08:50]

This is ready for review. 

It handles simple cases somewhat well, but gets easily confused by fixed
registers (there is no flow of information from USE with fixed register to DEF).

[srdjan, 2012-06-18 16:33:20]

LGTM

https://chromiumcodereview.appspot.com/10559035/diff/2001/runtime/vm/code_gen...
File runtime/vm/code_generator.cc (right):

https://chromiumcodereview.appspot.com/10559035/diff/2001/runtime/vm/code_gen...
runtime/vm/code_generator.cc:1349:
function.set_usage_counter(kLowInvocationCount);
Why not doing this in the compiler and "Bailout" from optimizing this function?

https://chromiumcodereview.appspot.com/10559035/diff/2001/runtime/vm/flow_gra...
File runtime/vm/flow_graph_compiler.h (right):

https://chromiumcodereview.appspot.com/10559035/diff/2001/runtime/vm/flow_gra...
runtime/vm/flow_graph_compiler.h:35: bool keep_values_in_registers)
remove explicit

https://chromiumcodereview.appspot.com/10559035/diff/2001/runtime/vm/flow_gra...
runtime/vm/flow_graph_compiler.h:90: Instruction*
registers_[kNumberOfCpuRegisters];
Consider renaming registers_to_instructions_, or just instructions_

https://chromiumcodereview.appspot.com/10559035/diff/2001/runtime/vm/flow_gra...
runtime/vm/flow_graph_compiler.h:92: bool keep_values_in_registers_;
const?

https://chromiumcodereview.appspot.com/10559035/diff/2001/runtime/vm/intermed...
File runtime/vm/intermediate_language_ia32.cc (right):

https://chromiumcodereview.appspot.com/10559035/diff/2001/runtime/vm/intermed...
runtime/vm/intermediate_language_ia32.cc:1339: // TODO(vegorov): for many binary
operations this pattern can be rearrange
rearranged

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

https://chromiumcodereview.appspot.com/10559035/diff/2001/runtime/vm/intermed...
runtime/vm/intermediate_language_x64.cc:1276: // TODO(vegorov): spilling is
required only on infrequently executed path.
A quick fix could be to use the deoptimization stub for the this kind of "stack
checks"

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

https://chromiumcodereview.appspot.com/10559035/diff/2001/runtime/vm/location...
runtime/vm/locations.h:115: ContainsCall call = kNoCall,
I am not sure having default value for 'call' is good. I think it will make the
caller more readable if we clearly state kNoCall where appropriate, so that the
differentiation is visible. 'branch' will go away, so I have no beef with it
having a default value.

[Florian Schneider, 2012-06-18 16:50:55]

lgtm

https://chromiumcodereview.appspot.com/10559035/diff/2001/runtime/vm/flow_gra...
File runtime/vm/flow_graph_compiler.h (right):

https://chromiumcodereview.appspot.com/10559035/diff/2001/runtime/vm/flow_gra...
runtime/vm/flow_graph_compiler.h:90: Instruction*
registers_[kNumberOfCpuRegisters];
Can it even be BindInstr*?

https://chromiumcodereview.appspot.com/10559035/diff/2001/runtime/vm/intermed...
File runtime/vm/intermediate_language_ia32.cc (right):

https://chromiumcodereview.appspot.com/10559035/diff/2001/runtime/vm/intermed...
runtime/vm/intermediate_language_ia32.cc:1675: // TODO(vegorov): allocate box in
the driver loop to avoid pushing and poping.
s/poping/popping/

[Vyacheslav Egorov (Google), 2012-06-18 17:51:16]

thanks for the review.

landing!

https://chromiumcodereview.appspot.com/10559035/diff/2001/runtime/vm/code_gen...
File runtime/vm/code_generator.cc (right):

https://chromiumcodereview.appspot.com/10559035/diff/2001/runtime/vm/code_gen...
runtime/vm/code_generator.cc:1349:
function.set_usage_counter(kLowInvocationCount);
On 2012/06/18 16:33:20, srdjan wrote:
> Why not doing this in the compiler and "Bailout" from optimizing this
function?

I don't see any profit in bailing out so late in the pipeline compared to
bailing out later. This is a purely debug flag.

https://chromiumcodereview.appspot.com/10559035/diff/2001/runtime/vm/flow_gra...
File runtime/vm/flow_graph_compiler.h (right):

https://chromiumcodereview.appspot.com/10559035/diff/2001/runtime/vm/flow_gra...
runtime/vm/flow_graph_compiler.h:35: bool keep_values_in_registers)
On 2012/06/18 16:33:20, srdjan wrote:
> remove explicit

Done.

https://chromiumcodereview.appspot.com/10559035/diff/2001/runtime/vm/flow_gra...
runtime/vm/flow_graph_compiler.h:90: Instruction*
registers_[kNumberOfCpuRegisters];
On 2012/06/18 16:50:55, Florian Schneider wrote:
> Can it even be BindInstr*?

Done.

https://chromiumcodereview.appspot.com/10559035/diff/2001/runtime/vm/flow_gra...
runtime/vm/flow_graph_compiler.h:90: Instruction*
registers_[kNumberOfCpuRegisters];
On 2012/06/18 16:33:20, srdjan wrote:
> Consider renaming registers_to_instructions_, or just instructions_

I am not sure instructions_ reflects the purpose: it tracks registers' state,
not instrucitons' state.

I'll leave it registers for now. We can rename it later.

https://chromiumcodereview.appspot.com/10559035/diff/2001/runtime/vm/flow_gra...
runtime/vm/flow_graph_compiler.h:92: bool keep_values_in_registers_;
On 2012/06/18 16:33:20, srdjan wrote:
> const?

Done.

https://chromiumcodereview.appspot.com/10559035/diff/2001/runtime/vm/flow_gra...
runtime/vm/flow_graph_compiler.h:92: bool keep_values_in_registers_;
On 2012/06/18 16:33:20, srdjan wrote:
> const?

Done.

https://chromiumcodereview.appspot.com/10559035/diff/2001/runtime/vm/intermed...
File runtime/vm/intermediate_language_ia32.cc (right):

https://chromiumcodereview.appspot.com/10559035/diff/2001/runtime/vm/intermed...
runtime/vm/intermediate_language_ia32.cc:1339: // TODO(vegorov): for many binary
operations this pattern can be rearrange
On 2012/06/18 16:33:20, srdjan wrote:
> rearranged

Done.

https://chromiumcodereview.appspot.com/10559035/diff/2001/runtime/vm/intermed...
runtime/vm/intermediate_language_ia32.cc:1675: // TODO(vegorov): allocate box in
the driver loop to avoid pushing and poping.
On 2012/06/18 16:50:55, Florian Schneider wrote:
> s/poping/popping/

Done.

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

https://chromiumcodereview.appspot.com/10559035/diff/2001/runtime/vm/intermed...
runtime/vm/intermediate_language_x64.cc:1276: // TODO(vegorov): spilling is
required only on infrequently executed path.
On 2012/06/18 16:33:20, srdjan wrote:
> A quick fix could be to use the deoptimization stub for the this kind of
"stack
> checks"

Yes, I agree. 

In V8 we have a generic "deferred code facility for this kind of stuff (calls to
runtime from deferred code are surrounded by register spilling). Call to the
stack overflow runtime routine is done from this deferred code.

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

https://chromiumcodereview.appspot.com/10559035/diff/2001/runtime/vm/location...
runtime/vm/locations.h:115: ContainsCall call = kNoCall,
On 2012/06/18 16:33:20, srdjan wrote:
> I am not sure having default value for 'call' is good. I think it will make
the
> caller more readable if we clearly state kNoCall where appropriate, so that
the
> differentiation is visible. 'branch' will go away, so I have no beef with it
> having a default value.

Having default value is definitely less safe than not having one. We can
eliminate it. I am adding todo.