Remove SminessPropagator and FlowGraphTypePropagator and all associated infrastructure and fields.

Remove SminessPropagator and FlowGraphTypePropagator and all associated infrastructure and fields.

Replace multiple fields (result_cid_, propagated_cid_, propagated_type_, reaching_cid_) with a single field of type CompileType which represents an element of type analysis lattice and incorporates information about: value's nullability, concrete class id and abstract super type. This ensures that propagated cid and type are always in sync and complement each other 

Implement a new FlowGraphPropagator that propagates types over the CompileType-lattice. 

BUG=

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

[Vyacheslav Egorov (Google), 2013-02-11 17:31:07]

Hi Regis & Srdjan,

Please take a look.

This CL refactors our type propagation switching to a real lattice instead of
various unconnected fields and unifying SminessPropagator and
FlowGraphTypePropagator. It also enables us to track nullablity of values.

This CL implements a all important infrastructure and should keep our
performance at the same point where it was.

There are multiple improvements that would be implemented on top of this
infrastructure that are not included into this CL to limit its size (e.g.
conditional propagation of nullability from branches on comparison with null,
conditional propagation of type from branches on instanceof, etc).

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_optimiz...
File runtime/vm/flow_graph_optimizer.cc (left):

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:2775: if (FLAG_eliminate_type_checks &&
In new approach type propagator only propagates types. It does not remove any
instructions. This is left to the canonicalization pass where it belongs.

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:2852: bool val = instr->negate_result() ?
!is_instance : is_instance;
I temporary removed any constant folding for instance-of instruction.

This version could actually fold away only (null is Smth) expression so I don't
think we would miss it.

I am going to re-add folding after this change has landed.

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:2947: // TODO(regis): Once we inline
functions, the propagated type of the formal
I temporary disabled this code as well (always type check these arguments).

I will return it after this CL lands.

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_type_pr...
File runtime/vm/flow_graph_type_propagator.cc (right):

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_type_pr...
runtime/vm/flow_graph_type_propagator.cc:396: return malformed_error.IsNull() &&
*is_instance;
At the moment we treat CompileType as an upper bound for an actual type. Because
it is an upper bound we can't give a DEFINITE-NO answer.

However in some cases CompileType could be representing value type precisely
(e.g. when it is computed from the constant or when both Cid and Type are
known), in this cases it might actually be possible to give a DEFINITE-NO
answer. This is however posptoned to later CLs to keep this one of limited size.

https://codereview.chromium.org/12221119/diff/1/runtime/vm/object.cc
File runtime/vm/object.cc (right):

https://codereview.chromium.org/12221119/diff/1/runtime/vm/object.cc#newcode2188
runtime/vm/object.cc:2188: if (other_type_arguments.IsNull() ||
other_type_arguments.IsRaw(len)) {
This function should compute if result of type test for any values of type
arguments thus it is incorrect to assume that they will be replaced by dynamic.
Otherwise given a instantiated type A<int> and uninstantiated type A<T> it will
say that A<int> <: A<T> and A<int> << A<T>, while in practice T can be replaced
with for example bool.

https://codereview.chromium.org/12221119/diff/1/runtime/vm/object.cc#newcode2191
runtime/vm/object.cc:2191: if (type_arguments.IsNull() ||
type_arguments.IsRaw(len)) {
This function should compute if result of type test for any values of type
arguments thus it is incorrect to assume that they will be replaced by dynamic.
Otherwise given an instantiated type A<T> and uninstantiated type A<int> it will
say that A<T> <: A<int> and A<T> << A<int>, while in practice T can be replaced
with for example bool.

[regis, 2013-02-11 19:51:49]

LGTM

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_type_pr...
File runtime/vm/flow_graph_type_propagator.cc (right):

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_type_pr...
runtime/vm/flow_graph_type_propagator.cc:18: 
Too many blank lines.

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_type_pr...
runtime/vm/flow_graph_type_propagator.cc:285: intptr_t
CompileType::ToNullableCid() {
What is the difference between ToCid() and ToNullableCid? When to use one or the
other?
Never mind, I found the comment I was missing in intermediate_language.h.

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_type_pr...
File runtime/vm/flow_graph_type_propagator.h (right):

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_type_pr...
runtime/vm/flow_graph_type_propagator.h:12: 
We use a single blank line after namespace. Do not ask me why.

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_type_pr...
runtime/vm/flow_graph_type_propagator.h:74: 
ditto before namespace.

https://codereview.chromium.org/12221119/diff/1/runtime/vm/object.cc
File runtime/vm/object.cc (right):

https://codereview.chromium.org/12221119/diff/1/runtime/vm/object.cc#newcode2188
runtime/vm/object.cc:2188: if (other_type_arguments.IsNull() ||
other_type_arguments.IsRaw(len)) {
On 2013/02/11 17:31:07, Vyacheslav Egorov (Google) wrote:
> This function should compute if result of type test for any values of type
> arguments thus it is incorrect to assume that they will be replaced by
dynamic.
> Otherwise given a instantiated type A<int> and uninstantiated type A<T> it
will
> say that A<int> <: A<T> and A<int> << A<T>, while in practice T can be
replaced
> with for example bool.
> 

Good catch. I think the reason we were doing this was for function parameter
type tests, where the generics were not instantiated. Now, we have a separate
function (TestParameterType) calling this one after properly instantiating the
generics.

[srdjan, 2013-02-11 20:54:31]

First set of comments, still reviewing the rest.

https://codereview.chromium.org/12221119/diff/1/runtime/vm/compiler.cc
File runtime/vm/compiler.cc (right):

https://codereview.chromium.org/12221119/diff/1/runtime/vm/compiler.cc#newcod...
runtime/vm/compiler.cc:195: OS::Print("Before type propagation:\n");
Have we made decision to print diagnostics with PrintErr?

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_compile...
File runtime/vm/flow_graph_compiler_ia32.cc (right):

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_compile...
runtime/vm/flow_graph_compiler_ia32.cc:571: __ cmpl(EAX,
raw_transition_sentinel);
__ CompareObject instead?

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_compile...
File runtime/vm/flow_graph_compiler_x64.cc (right):

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_compile...
runtime/vm/flow_graph_compiler_x64.cc:570: __ cmpq(RAX,
raw_transition_sentinel);
__ CompareObject instead?

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_type_pr...
File runtime/vm/flow_graph_type_propagator.cc (right):

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_type_pr...
runtime/vm/flow_graph_type_propagator.cc:41: OS::Print("%s\n",
worklist_[i]->Type()->ToCString());
You could add UNREACHBALE here instead of ASSERT below?

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_type_pr...
File runtime/vm/flow_graph_type_propagator.h (right):

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_type_pr...
runtime/vm/flow_graph_type_propagator.h:9: #include "vm/flow_graph.h"
Order alphabetically

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_type_pr...
runtime/vm/flow_graph_type_propagator.h:57: // Do nothing. Only needed for
container.
intialize the fields nonetheless.

[srdjan, 2013-02-11 21:10:50]

LGTM

https://codereview.chromium.org/12221119/diff/1/runtime/vm/intermediate_langu...
File runtime/vm/intermediate_language.h (right):

https://codereview.chromium.org/12221119/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.h:2383: || (receiver_class_id() == kSmiCid);
Why not kBigintCid? Add a comment why or rename.

https://codereview.chromium.org/12221119/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.h:2456: || (operands_class_id() == kSmiCid);
ditto

[Vyacheslav Egorov (Google), 2013-02-18 14:05:22]

sending stale drafts

https://codereview.chromium.org/12221119/diff/1/runtime/vm/compiler.cc
File runtime/vm/compiler.cc (right):

https://codereview.chromium.org/12221119/diff/1/runtime/vm/compiler.cc#newcod...
runtime/vm/compiler.cc:195: OS::Print("Before type propagation:\n");
On 2013/02/11 20:54:31, srdjan wrote:
> Have we made decision to print diagnostics with PrintErr?

I am not sure.

FlowGraphPrinter still prints to stdout, so I'd like to keep this in sync.

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_compile...
File runtime/vm/flow_graph_compiler_ia32.cc (right):

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_compile...
runtime/vm/flow_graph_compiler_ia32.cc:571: __ cmpl(EAX,
raw_transition_sentinel);
On 2013/02/11 20:54:31, srdjan wrote:
> __ CompareObject instead?

Done.

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_compile...
File runtime/vm/flow_graph_compiler_x64.cc (right):

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_compile...
runtime/vm/flow_graph_compiler_x64.cc:570: __ cmpq(RAX,
raw_transition_sentinel);
On 2013/02/11 20:54:31, srdjan wrote:
> __ CompareObject instead?

Done.

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_type_pr...
File runtime/vm/flow_graph_type_propagator.cc (right):

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_type_pr...
runtime/vm/flow_graph_type_propagator.cc:18: 
On 2013/02/11 19:51:49, regis wrote:
> Too many blank lines.

Done.

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_type_pr...
runtime/vm/flow_graph_type_propagator.cc:41: OS::Print("%s\n",
worklist_[i]->Type()->ToCString());
On 2013/02/11 20:54:31, srdjan wrote:
> You could add UNREACHBALE here instead of ASSERT below?

This was accidental debug code. I'll revert it.

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_type_pr...
File runtime/vm/flow_graph_type_propagator.h (right):

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_type_pr...
runtime/vm/flow_graph_type_propagator.h:9: #include "vm/flow_graph.h"
On 2013/02/11 20:54:31, srdjan wrote:
> Order alphabetically

Done.

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_type_pr...
runtime/vm/flow_graph_type_propagator.h:12: 
On 2013/02/11 19:51:49, regis wrote:
> We use a single blank line after namespace. Do not ask me why.

Done.

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_type_pr...
runtime/vm/flow_graph_type_propagator.h:57: // Do nothing. Only needed for
container.
On 2013/02/11 20:54:31, srdjan wrote:
> intialize the fields nonetheless.

Done.

https://codereview.chromium.org/12221119/diff/1/runtime/vm/flow_graph_type_pr...
runtime/vm/flow_graph_type_propagator.h:74: 
On 2013/02/11 19:51:49, regis wrote:
> ditto before namespace.

Done.

https://codereview.chromium.org/12221119/diff/1/runtime/vm/intermediate_langu...
File runtime/vm/intermediate_language.h (right):

https://codereview.chromium.org/12221119/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.h:2383: || (receiver_class_id() == kSmiCid);
On 2013/02/11 21:10:50, srdjan wrote:
> Why not kBigintCid? Add a comment why or rename.

Renamed to IsInlinedNumericComparison.