Implement loop invariant code motion for check instructions.

Implement loop invariant code motion for check instructions.

This CL adds a new optimization pass that hoist loop invariant
instructions upwards out of loops.

I'm adding a deoptimzation point at every Goto so that we
can move deoptimizing instructions like checks out of loops.
As a result there may be multiple deoptimization descriptors
with the same PC. The corresponding assert are removed.
Committed: https://code.google.com/p/dart/source/detail?r=11946

[Kevin Millikin (Google), 2012-09-06 12:42:41]

LGTM with small comments.

https://chromiumcodereview.appspot.com/10909094/diff/1/runtime/vm/code_genera...
File runtime/vm/code_generator.cc (right):

https://chromiumcodereview.appspot.com/10909094/diff/1/runtime/vm/code_genera...
runtime/vm/code_generator.cc:1632: ASSERT(continue_at_pc != 0);
Thank you.

https://chromiumcodereview.appspot.com/10909094/diff/1/runtime/vm/flow_graph.cc
File runtime/vm/flow_graph.cc (right):

https://chromiumcodereview.appspot.com/10909094/diff/1/runtime/vm/flow_graph....
runtime/vm/flow_graph.cc:674: ZoneGrowableArray<BlockEntryInstr*>* loop =
Consider a bit vector indexed by preorder block number to make Contains constant
time.

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

https://chromiumcodereview.appspot.com/10909094/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_optimizer.cc:1150: BlockEntryInstr*  candidate =
header->PredecessorAt(j);
Extra space!

https://chromiumcodereview.appspot.com/10909094/diff/1/runtime/vm/growable_ar...
File runtime/vm/growable_array.h (right):

https://chromiumcodereview.appspot.com/10909094/diff/1/runtime/vm/growable_ar...
runtime/vm/growable_array.h:92: bool Contains(const T& value) {
I actually like not having this function defined :)

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

https://chromiumcodereview.appspot.com/10909094/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language.cc:601: ASSERT(other != NULL);
Add a TODO to make this faster :)

[Florian Schneider, 2012-09-06 13:05:53]

https://chromiumcodereview.appspot.com/10909094/diff/1/runtime/vm/code_genera...
File runtime/vm/code_generator.cc (right):

https://chromiumcodereview.appspot.com/10909094/diff/1/runtime/vm/code_genera...
runtime/vm/code_generator.cc:1632: ASSERT(continue_at_pc != 0);
On 2012/09/06 12:42:42, kmillikin wrote:
> Thank you.

You're welcome!

https://chromiumcodereview.appspot.com/10909094/diff/1/runtime/vm/flow_graph.cc
File runtime/vm/flow_graph.cc (right):

https://chromiumcodereview.appspot.com/10909094/diff/1/runtime/vm/flow_graph....
runtime/vm/flow_graph.cc:674: ZoneGrowableArray<BlockEntryInstr*>* loop =
On 2012/09/06 12:42:42, kmillikin wrote:
> Consider a bit vector indexed by preorder block number to make Contains
constant
> time.

Done.

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

https://chromiumcodereview.appspot.com/10909094/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_optimizer.cc:1150: BlockEntryInstr*  candidate =
header->PredecessorAt(j);
On 2012/09/06 12:42:42, kmillikin wrote:
> Extra space!

Done.

https://chromiumcodereview.appspot.com/10909094/diff/1/runtime/vm/growable_ar...
File runtime/vm/growable_array.h (right):

https://chromiumcodereview.appspot.com/10909094/diff/1/runtime/vm/growable_ar...
runtime/vm/growable_array.h:92: bool Contains(const T& value) {
On 2012/09/06 12:42:42, kmillikin wrote:
> I actually like not having this function defined :)

Done.

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

https://chromiumcodereview.appspot.com/10909094/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language.cc:601: ASSERT(other != NULL);
On 2012/09/06 12:42:42, kmillikin wrote:
> Add a TODO to make this faster :)

Done.

[srdjan, 2012-09-06 13:44:26]

DBC

https://chromiumcodereview.appspot.com/10909094/diff/1/runtime/vm/flow_graph.cc
File runtime/vm/flow_graph.cc (right):

https://chromiumcodereview.appspot.com/10909094/diff/1/runtime/vm/flow_graph....
runtime/vm/flow_graph.cc:672: static void FindLoop(BlockEntryInstr* m,
BlockEntryInstr* n) {
There is also FlowGraphAllocator::DiscoverLoops, how do they differ, are they
both necessary?

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

https://chromiumcodereview.appspot.com/10909094/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language.h:431: friend class LICM;
Please add why, or move the comment if it is valid for both.

https://chromiumcodereview.appspot.com/10909094/diff/1/runtime/vm/object.cc
File runtime/vm/object.cc (right):

https://chromiumcodereview.appspot.com/10909094/diff/1/runtime/vm/object.cc#n...
runtime/vm/object.cc:6731: // A function without unique ids is marked as
non-optimizable (e.g., because of
Maybe replace removed comment with what you said in the CL.

[Florian Schneider, 2012-09-06 13:49:30]

I'll address you comments in a new CL.

https://chromiumcodereview.appspot.com/10909094/diff/1/runtime/vm/flow_graph.cc
File runtime/vm/flow_graph.cc (right):

https://chromiumcodereview.appspot.com/10909094/diff/1/runtime/vm/flow_graph....
runtime/vm/flow_graph.cc:672: static void FindLoop(BlockEntryInstr* m,
BlockEntryInstr* n) {
On 2012/09/06 13:44:26, srdjan wrote:
> There is also FlowGraphAllocator::DiscoverLoops, how do they differ, are they
> both necessary?

Good point. I didn't remember that we have such a thing. Mine is more generic,
so I'll replace the old one.

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

https://chromiumcodereview.appspot.com/10909094/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language.h:431: friend class LICM;
On 2012/09/06 13:44:26, srdjan wrote:
> Please add why, or move the comment if it is valid for both.
 Moved it to below where the comment applies.

https://chromiumcodereview.appspot.com/10909094/diff/1/runtime/vm/object.cc
File runtime/vm/object.cc (right):

https://chromiumcodereview.appspot.com/10909094/diff/1/runtime/vm/object.cc#n...
runtime/vm/object.cc:6731: // A function without unique ids is marked as
non-optimizable (e.g., because of
On 2012/09/06 13:44:26, srdjan wrote:
> Maybe replace removed comment with what you said in the CL.

Done.