Continue work on type propagation in optimizing compiler (still WIP).

Continue work on type propagation in optimizing compiler (still WIP).
Propagated types are cached in ssa definition nodes.
Type propagation iterates until fix point is reached.
Type checks are marked as eliminated when possible.
Committed: https://code.google.com/p/dart/source/detail?r=10475

[srdjan, 2012-08-09 22:20:53]

LGTM with comments.

You are missing code to skip code for AssertAssignableComp if it is eliminated

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

https://chromiumcodereview.appspot.com/10829270/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_builder.cc:444: const bool eliminated =
value->CompileTypeIsMoreSpecificThan(dst_type);
Comment that propagated types are not set yet.

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

https://chromiumcodereview.appspot.com/10829270/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_optimizer.cc:553: (comp->value() != NULL) &&
When can comp->value() be NULL?

https://chromiumcodereview.appspot.com/10829270/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_optimizer.cc:637: } while (still_changing_);
This could be made more efficient by visiting only blocks that have changed and
not the whole graph. Please add a TODO.

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

https://chromiumcodereview.appspot.com/10829270/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language.cc:185: return PropagatedType();
As discussed in chat, check if you want to split CompiledType (returns one type)
from PropagatedTypes (returns a type set/array).

https://chromiumcodereview.appspot.com/10829270/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language.cc:201: input_type =
input->AsUse()->definition()->PropagatedType();
input_type = input->AsUse()->CompileType();, and fix comment about cycles above.

https://chromiumcodereview.appspot.com/10829270/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language.cc:228: }
How can a parameter instruction have a propagated_type ?

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

https://chromiumcodereview.appspot.com/10829270/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language.h:150: // Compile time type of the computation.
Compile time type or propagated type of the computation.

https://chromiumcodereview.appspot.com/10829270/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language.h:2290:
propagated_type_(AbstractType::ZoneHandle()) { }
This could be Handle instead of ZoneHandle (propagated_type_ will not live
longer than Definition itself.

https://chromiumcodereview.appspot.com/10829270/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language.h:2315: }
Add comment that it returns true if the type has changed.

[regis, 2012-08-09 23:51:37]

Thanks!

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

https://chromiumcodereview.appspot.com/10829270/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_builder.cc:444: const bool eliminated =
value->CompileTypeIsMoreSpecificThan(dst_type);
On 2012/08/09 22:20:53, srdjan wrote:
> Comment that propagated types are not set yet.

Done.

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

https://chromiumcodereview.appspot.com/10829270/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_optimizer.cc:553: (comp->value() != NULL) &&
On 2012/08/09 22:20:53, srdjan wrote:
> When can comp->value() be NULL?

It cannot. Code reuse error. Removed.

https://chromiumcodereview.appspot.com/10829270/diff/1/runtime/vm/flow_graph_...
runtime/vm/flow_graph_optimizer.cc:637: } while (still_changing_);
On 2012/08/09 22:20:53, srdjan wrote:
> This could be made more efficient by visiting only blocks that have changed
and
> not the whole graph. Please add a TODO.

Added TODO.
I think we would need to revisit blocks that depend on blocks that have changed,
not just those that have changed.

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

https://chromiumcodereview.appspot.com/10829270/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language.cc:185: return PropagatedType();
On 2012/08/09 22:20:53, srdjan wrote:
> As discussed in chat, check if you want to split CompiledType (returns one
type)
> from PropagatedTypes (returns a type set/array).

I will keep that question in mind for the next step introducing type sets.

https://chromiumcodereview.appspot.com/10829270/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language.cc:201: input_type =
input->AsUse()->definition()->PropagatedType();
On 2012/08/09 22:20:53, srdjan wrote:
> input_type = input->AsUse()->CompileType();, and fix comment about cycles
above.

Code and comment changed:
    input_type = InputAt(i)->CompileType();

https://chromiumcodereview.appspot.com/10829270/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language.cc:228: }
On 2012/08/09 22:20:53, srdjan wrote:
> How can a parameter instruction have a propagated_type ?

As the TODO indicates, it would be the type obtained from type feedback and not
really a "propagated", but used similarly as one.

https://chromiumcodereview.appspot.com/10829270/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language.cc:1053: if (!IsEliminated()) {
This makes sure eliminated type checks are not emitted. Do you mean something
else by "You are missing code to skip code for AssertAssignableComp if it is
eliminated"?

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

https://chromiumcodereview.appspot.com/10829270/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language.h:150: // Compile time type of the computation.
On 2012/08/09 22:20:53, srdjan wrote:
> Compile time type or propagated type of the computation.

Yes, the compile type takes the propagated types of the inputs into
consideration, but the computation itself does not cache a propagated type of
its result. The bind instruction caches the propagated type of the computation,
not the computation itself. Added comment.

https://chromiumcodereview.appspot.com/10829270/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language.h:2290:
propagated_type_(AbstractType::ZoneHandle()) { }
On 2012/08/09 22:20:53, srdjan wrote:
> This could be Handle instead of ZoneHandle (propagated_type_ will not live
> longer than Definition itself.

Done.

https://chromiumcodereview.appspot.com/10829270/diff/1/runtime/vm/intermediat...
runtime/vm/intermediate_language.h:2315: }
On 2012/08/09 22:20:53, srdjan wrote:
> Add comment that it returns true if the type has changed.

Done.