Implement class id checks as a separate instruction and add a local CSE optimization pass.

Implement class id checks as a separate instruction and add a local CSE optimization pass.

This CL contains:
A new CheckClassComp instruction. Currently it is used only for instance loads:
(LoadInstanceFieldComp)

A pass LocalCSE that performs block-local common subexpression elimination. To identify
redundant expressions I use a hash map per basic block. Computations that do not have
side effects can participate in CSE. For now, I only enabled it for CheckClass.
Any computation that participates in CSE must implement the AttributesEqual function.


Other smaller fixes:

Places where we can pass the correct initial size for GrowableArrays
that have a known size. We should consider having a FixedLengthArray for this purpose.

Made the accessors ic_data() and set_ic_data() use a const ICData*.
Committed: https://code.google.com/p/dart/source/detail?r=10948

[srdjan, 2012-08-17 22:30:22]

LGTM with comments.

Once we propagate class-id sets, we could add class checks between two nodes,
i.e., all nodes referring to the input of a class check node would now refer to
the output of that class check node, and thus we could have check elimination
across blocks. What do you think?

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

https://chromiumcodereview.appspot.com/10824349/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_optimizer.cc:373: } else {
The code below is probably going to be quite common, you may want to factor it
out in next CL, once you start applying it to other operations.

https://chromiumcodereview.appspot.com/10824349/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_optimizer.cc:375: new
CheckClassComp(comp->ArgumentAt(0)->value(), comp);
You may want to check if the CheckClassComp is needed at all by looking at
ResultCid of value.  TODO OK for now.

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

https://chromiumcodereview.appspot.com/10824349/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_optimizer.h:49: bool use_ssa_;
const, but who cares, it will go away next week.

https://chromiumcodereview.appspot.com/10824349/diff/1/runtime/vm/hash_map.h
File runtime/vm/hash_map.h (right):

https://chromiumcodereview.appspot.com/10824349/diff/1/runtime/vm/hash_map.h#...
runtime/vm/hash_map.h:9: 
Sidenote: what is your opinion of starting to use STL containers? Carl is quite
in favor of it, but we still have our doubts,

https://chromiumcodereview.appspot.com/10824349/diff/1/runtime/vm/hash_map.h#...
runtime/vm/hash_map.h:25: T* Lookup(T* value) const;
Please change specification so that DirectChainedHashMap<Name*> means that you
are storing Name* into it and not Name**.
See GrowableArray, BitField and others.

https://chromiumcodereview.appspot.com/10824349/diff/1/runtime/vm/hash_map.h#...
runtime/vm/hash_map.h:30: // A linked list of Computation* values.  Stored in
arrays.
s/Computation/T/

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

https://chromiumcodereview.appspot.com/10824349/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language.cc:34: return result;
Weird indentation.

https://chromiumcodereview.appspot.com/10824349/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language.cc:45: 
One line too much

https://chromiumcodereview.appspot.com/10824349/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language.cc:60: }
You may want to move this loop and tests into class ICData.

https://chromiumcodereview.appspot.com/10824349/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language.cc:224: ASSERT(IsBind());
Why don't you put this method in BindInstr then?

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

https://chromiumcodereview.appspot.com/10824349/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language.h:157: // Functions to support CSE.
Please document these functions briefly.

https://chromiumcodereview.appspot.com/10824349/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language.h:960: virtual bool CanDeoptimize() const {
return true; }
Should this be false if we have added a CheckClassComp in front?

https://chromiumcodereview.appspot.com/10824349/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language.h:1783: class CheckClassComp : public
TemplateComputation<1> {
Consider renaming it to CheckClassesComp since it checks a set of classes.

https://chromiumcodereview.appspot.com/10824349/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language.h:1797: virtual bool HasSideEffect() const {
return false; }
Why is CheckClassComp the only computation that does not have side effect?
Please add comment.

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

https://chromiumcodereview.appspot.com/10824349/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language_x64.cc:2158: void
CheckClassComp::EmitNativeCode(FlowGraphCompiler* compiler) {
Maybe make this code more generic so that it can handle Smi's as well (TODO is
OK for now). We should also use it for Smi checks as well, shouldn't we.

[Florian Schneider, 2012-08-20 12:09:37]

Thanks for the review.

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

http://codereview.chromium.org/10824349/diff/1/runtime/vm/flow_graph_optimize...
runtime/vm/flow_graph_optimizer.cc:373: } else {
On 2012/08/17 22:30:22, srdjan wrote:
> The code below is probably going to be quite common, you may want to factor it
> out in next CL, once you start applying it to other operations.

Yes, this will be similar for inserting other checks. I'll factor it out once we
have a second example.

http://codereview.chromium.org/10824349/diff/1/runtime/vm/flow_graph_optimize...
runtime/vm/flow_graph_optimizer.cc:375: new
CheckClassComp(comp->ArgumentAt(0)->value(), comp);
On 2012/08/17 22:30:22, srdjan wrote:
> You may want to check if the CheckClassComp is needed at all by looking at
> ResultCid of value.  TODO OK for now.

I'll add a TODO. The only thing required for that is that we already have
propagated cid information. Currently, we won't have propagated the info across
blocks at this point. The other possibility would be to have a separate check
elimination pass after type propagation.

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

http://codereview.chromium.org/10824349/diff/1/runtime/vm/hash_map.h#newcode9
runtime/vm/hash_map.h:9: 
On 2012/08/17 22:30:22, srdjan wrote:
> Sidenote: what is your opinion of starting to use STL containers? Carl is
quite
> in favor of it, but we still have our doubts,

I'm also mostly in favor, if we are careful with memory management performance.
If we want to support a certain operation efficiently and there is no support
for that in STL, then we can always use our own implementation. e.g. in Chromium
there is both std::list and LinkedList
(http://src.chromium.org/svn/trunk/src/base/linked_list.h)

http://codereview.chromium.org/10824349/diff/1/runtime/vm/hash_map.h#newcode25
runtime/vm/hash_map.h:25: T* Lookup(T* value) const;
On 2012/08/17 22:30:22, srdjan wrote:
> Please change specification so that DirectChainedHashMap<Name*> means that you
> are storing Name* into it and not Name**.
> See GrowableArray, BitField and others.

Done.

http://codereview.chromium.org/10824349/diff/1/runtime/vm/hash_map.h#newcode30
runtime/vm/hash_map.h:30: // A linked list of Computation* values.  Stored in
arrays.
On 2012/08/17 22:30:22, srdjan wrote:
> s/Computation/T/

Done.

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

http://codereview.chromium.org/10824349/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.cc:34: return result;
On 2012/08/17 22:30:22, srdjan wrote:
> Weird indentation.

Done.

http://codereview.chromium.org/10824349/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.cc:45: 
On 2012/08/17 22:30:22, srdjan wrote:
> One line too much

Done.

http://codereview.chromium.org/10824349/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.cc:224: ASSERT(IsBind());
On 2012/08/17 22:30:22, srdjan wrote:
> Why don't you put this method in BindInstr then?

Done.

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

http://codereview.chromium.org/10824349/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:157: // Functions to support CSE.
On 2012/08/17 22:30:22, srdjan wrote:
> Please document these functions briefly.

Done.

http://codereview.chromium.org/10824349/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:960: virtual bool CanDeoptimize() const {
return true; }
On 2012/08/17 22:30:22, srdjan wrote:
> Should this be false if we have added a CheckClassComp in front?

Yes. I'll add a TODO to change it when we remove the old register allocator.

http://codereview.chromium.org/10824349/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:1783: class CheckClassComp : public
TemplateComputation<1> {
On 2012/08/17 22:30:22, srdjan wrote:
> Consider renaming it to CheckClassesComp since it checks a set of classes.

Done.

http://codereview.chromium.org/10824349/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language.h:1797: virtual bool HasSideEffect() const {
return false; }
On 2012/08/17 22:30:22, srdjan wrote:
> Why is CheckClassComp the only computation that does not have side effect?
> Please add comment.

Currently only CheckClass participates in CSE, but I added a TODO to implement
it for all computations. By default it returns the safe default (true) for now.

http://codereview.chromium.org/10824349/diff/1/runtime/vm/intermediate_langua...
File runtime/vm/intermediate_language_x64.cc (right):

http://codereview.chromium.org/10824349/diff/1/runtime/vm/intermediate_langua...
runtime/vm/intermediate_language_x64.cc:2158: void
CheckClassComp::EmitNativeCode(FlowGraphCompiler* compiler) {
On 2012/08/17 22:30:22, srdjan wrote:
> Maybe make this code more generic so that it can handle Smi's as well (TODO is
> OK for now). We should also use it for Smi checks as well, shouldn't we.

CheckSmi would fit in here, but for CheckNonSmi we'd need a separate
instruction. So maybe we should just have a separate check that checks either
for smi or non-smi.

[Florian Schneider, 2012-08-20 12:37:04]

On 2012/08/17 22:30:22, srdjan wrote:
> LGTM with comments.
> 
> Once we propagate class-id sets, we could add class checks between two nodes,
> i.e., all nodes referring to the input of a class check node would now refer
to
> the output of that class check node, and thus we could have check elimination
> across blocks. What do you think?
> 

I think I'll start with across-basic-block elimination today. As a first step,
I'll do a traversal of the dominator tree and use the same hash map to record
redundant computations. That should already work even without having
check-instructions produce a result that is used by the depending instruction.