[vm] Implement gradual refinement of types

[vm] Implement gradual refinement of types

Before this CL, each invocation of FlowGraphTypePropagator discarded
(overwritten) all previously inferred types. Due to re-structuring of
the IR (for example, InstanceCall to _simpleInstanceOf may be replaced
with various IR sequences), FlowGraphTypePropagator may yield
better or worse results (for example, not all replacements of
_simpleInstanceOf are recognized by FlowGraphTypePropagator).

As the result, inferred type information could be lost at later
stages of the compilation pipeline. Code generation, which looks
at the types may not see the same types as earlier stages of
compilation pipeline, so EmitNativeCode() may generate code which is
out of sync with ComputeCanDeoptimize().

This CL introduces refinement of types: old type is no longer
blindly replaced with newly inferred type. Instead, more specific type
is selected among new and old types. Conservatively, the new type is
preferred if the types are unrelated (it could happen in certain
corner cases, such as unreachable code).

This CL also contains the following minor changes:

* Fix reaching type of the CheckSmi argument when CheckSmi is moved
  in LICM::TrySpecializeSmiPhi. It looks like it was previosuly
  unnoticed due to full recomputation of types in type propagator.

* Rename local variables to better follow style guide (follow-up
  to my previous change).

* Handle kNE along with other comparisons in AOT.

R=rmacnak@google.com, vegorov@google.com

Issue: https://github.com/dart-lang/sdk/issues/30480
Committed: https://github.com/dart-lang/sdk/commit/3cc0cea37e56bc5c590905f2da4bc5d9db9d73e6

[alexmarkov, 2017-08-29 21:35:53]

alexmarkov@google.com changed reviewers:
+ asiva@google.com, rmacnak@google.com, vegorov@google.com

[rmacnak, 2017-08-29 23:02:42]

lgtm

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

https://codereview.chromium.org/3010673002/diff/1/runtime/vm/flow_graph_type_...
runtime/vm/flow_graph_type_propagator.cc:552: const AbstractType* compile_type =
ToAbstractType();
abstract_type

https://codereview.chromium.org/3010673002/diff/1/runtime/vm/flow_graph_type_...
runtime/vm/flow_graph_type_propagator.cc:553: const AbstractType*
other_compile_type = other->ToAbstractType();
other_abstract_type

[alexmarkov, 2017-08-29 23:10:37]

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

https://codereview.chromium.org/3010673002/diff/1/runtime/vm/flow_graph_type_...
runtime/vm/flow_graph_type_propagator.cc:552: const AbstractType* compile_type =
ToAbstractType();
On 2017/08/29 23:02:42, rmacnak wrote:
> abstract_type

Done.

https://codereview.chromium.org/3010673002/diff/1/runtime/vm/flow_graph_type_...
runtime/vm/flow_graph_type_propagator.cc:553: const AbstractType*
other_compile_type = other->ToAbstractType();
On 2017/08/29 23:02:42, rmacnak wrote:
> other_abstract_type

Done.

[Vyacheslav Egorov (Google), 2017-08-30 17:11:47]

LGTM

I think this should work OK, but I need to think more about it.

https://codereview.chromium.org/3010673002/diff/20001/runtime/vm/flow_graph_t...
File runtime/vm/flow_graph_type_propagator.cc (right):

https://codereview.chromium.org/3010673002/diff/20001/runtime/vm/flow_graph_t...
runtime/vm/flow_graph_type_propagator.cc:532: CompileType*
CompileType::Refine(CompileType* other) {
Name Refine makes it sound like it mutates this, but in reality it does not. 

Maybe this can be a static method instead, e.g.:

CompileType::ComputeRefinedType(older_type, new_type)

https://codereview.chromium.org/3010673002/diff/20001/runtime/vm/flow_graph_t...
runtime/vm/flow_graph_type_propagator.cc:545: if (other->ToCid() != kDynamicCid)
{
What happens if you assert here:

// Check that cid can't change in an unpredictable way.
ASSERT(other->ToCid() == kDynamicCid || 
       this->ToCid() == kDynamicCid ||
       other->ToCid() == this->ToCid());

https://codereview.chromium.org/3010673002/diff/20001/runtime/vm/flow_graph_t...
runtime/vm/flow_graph_type_propagator.cc:555: if
(abstract_type->IsMoreSpecificThan(*other_abstract_type, NULL, NULL,
Maybe something like:

if (abstract_type->IsMoreSpecificThan(*other_abstract_type, NULL, NULL,
Heap::kOld)) {
  result = this;
} else {
  result = other;
}

// If result is nullable but either this or other is not nullable
// then clear nullability.
if (result->is_nullable() && 
    !(this->is_nullable() && other->is_nullable())) {
  result = new CompileType(result->CopyNonNullable());
}

return result;

is easier to read.

[alexmarkov, 2017-08-30 18:11:57]

https://codereview.chromium.org/3010673002/diff/20001/runtime/vm/flow_graph_t...
File runtime/vm/flow_graph_type_propagator.cc (right):

https://codereview.chromium.org/3010673002/diff/20001/runtime/vm/flow_graph_t...
runtime/vm/flow_graph_type_propagator.cc:532: CompileType*
CompileType::Refine(CompileType* other) {
On 2017/08/30 17:11:46, Vyacheslav Egorov (Google) wrote:
> Name Refine makes it sound like it mutates this, but in reality it does not. 
> 
> Maybe this can be a static method instead, e.g.:
> 
> CompileType::ComputeRefinedType(older_type, new_type)
> 

Done.

https://codereview.chromium.org/3010673002/diff/20001/runtime/vm/flow_graph_t...
runtime/vm/flow_graph_type_propagator.cc:545: if (other->ToCid() != kDynamicCid)
{
On 2017/08/30 17:11:46, Vyacheslav Egorov (Google) wrote:
> What happens if you assert here:
> 
> // Check that cid can't change in an unpredictable way.
> ASSERT(other->ToCid() == kDynamicCid || 
>        this->ToCid() == kDynamicCid ||
>        other->ToCid() == this->ToCid());

I tried to add this assertion at first :)
Unfortunately, after spending some time to debug its failure, I figured that
there is a legitimate case when it could be triggered: unreachable code.

Added more comments about it.

https://codereview.chromium.org/3010673002/diff/20001/runtime/vm/flow_graph_t...
runtime/vm/flow_graph_type_propagator.cc:555: if
(abstract_type->IsMoreSpecificThan(*other_abstract_type, NULL, NULL,
On 2017/08/30 17:11:46, Vyacheslav Egorov (Google) wrote:
> Maybe something like:
> 
> if (abstract_type->IsMoreSpecificThan(*other_abstract_type, NULL, NULL,
> Heap::kOld)) {
>   result = this;
> } else {
>   result = other;
> }
> 
> // If result is nullable but either this or other is not nullable
> // then clear nullability.
> if (result->is_nullable() && 
>     !(this->is_nullable() && other->is_nullable())) {
>   result = new CompileType(result->CopyNonNullable());
> }
> 
> return result;
> 
> is easier to read.

Thank you for the suggestion, refactored code a little bit.

[Vyacheslav Egorov (Google), 2017-08-30 18:13:56]

https://codereview.chromium.org/3010673002/diff/20001/runtime/vm/flow_graph_t...
File runtime/vm/flow_graph_type_propagator.cc (right):

https://codereview.chromium.org/3010673002/diff/20001/runtime/vm/flow_graph_t...
runtime/vm/flow_graph_type_propagator.cc:545: if (other->ToCid() != kDynamicCid)
{
On 2017/08/30 18:11:57, alexmarkov wrote:
> On 2017/08/30 17:11:46, Vyacheslav Egorov (Google) wrote:
> > What happens if you assert here:
> > 
> > // Check that cid can't change in an unpredictable way.
> > ASSERT(other->ToCid() == kDynamicCid || 
> >        this->ToCid() == kDynamicCid ||
> >        other->ToCid() == this->ToCid());
> 
> I tried to add this assertion at first :)
> Unfortunately, after spending some time to debug its failure, I figured that
> there is a legitimate case when it could be triggered: unreachable code.
> 
> Added more comments about it.

Can unreachable code become reachable by accident? 

Maybe we should prune unreachable code more aggressively?

[alexmarkov, 2017-08-30 18:29:24]

On 2017/08/30 18:13:56, Vyacheslav Egorov (Google) wrote:
>
https://codereview.chromium.org/3010673002/diff/20001/runtime/vm/flow_graph_t...
> File runtime/vm/flow_graph_type_propagator.cc (right):
> 
>
https://codereview.chromium.org/3010673002/diff/20001/runtime/vm/flow_graph_t...
> runtime/vm/flow_graph_type_propagator.cc:545: if (other->ToCid() !=
kDynamicCid)
> {
> On 2017/08/30 18:11:57, alexmarkov wrote:
> > On 2017/08/30 17:11:46, Vyacheslav Egorov (Google) wrote:
> > > What happens if you assert here:
> > > 
> > > // Check that cid can't change in an unpredictable way.
> > > ASSERT(other->ToCid() == kDynamicCid || 
> > >        this->ToCid() == kDynamicCid ||
> > >        other->ToCid() == this->ToCid());
> > 
> > I tried to add this assertion at first :)
> > Unfortunately, after spending some time to debug its failure, I figured that
> > there is a legitimate case when it could be triggered: unreachable code.
> > 
> > Added more comments about it.
> 
> Can unreachable code become reachable by accident? 
> 
> Maybe we should prune unreachable code more aggressively?

Only due to a bug in compiler :)

I think it's all about pass ordering: certain passes can yield unreachable code;
certain passes can work on unreachable code and certain don't (the latter passes
require UCE to run beforehand). It is inconvenient and inefficient to run UCE
before every single pass, so it is a desirable property for a pass to accept
unreachable code and silently ignore it (of course, if it doesn't substantially
complicate pass or somehow violates logic of a pass). It turns out that type
propagation currently runs when there could be unreachable code. It's quite easy
to keep supporting unreachable code in type propagation, so I do not see enough
motivation for inserting UCE before every call to type propagation pass.

If you feel strongly about eager removal of unreachable code, I can try to
insert more UCE passes before type propagation and then strengthen assertions in
type propagation.

[alexmarkov, 2017-08-30 19:12:21]

Description was changed from

==========
[vm] Implement gradual refinement of types

Before this CL, each invocation of FlowGraphTypePropagator discarded
(overwritten) all previously inferred types. Due to re-structuring of
the IR (for example, InstanceCall to _simpleInstanceOf may be replaced
with various IR sequences), FlowGraphTypePropagator may yield
better or worse results (for example, not all replacements of
_simpleInstanceOf are recognized by FlowGraphTypePropagator).

As the result, inferred type information could be lost at later
stages of the compilation pipeline. Code generation, which looks
at the types may not see the same types as earlier stages of
compilation pipeline, so EmitNativeCode() may generate code which is
out of sync with ComputeCanDeoptimize().

This CL introduces refinement of types: old type is no longer
blindly replaced with newly inferred type. Instead, more specific type
is selected among new and old types. Conservatively, the new type is
preferred if the types are unrelated (it could happen in certain
corner cases, such as unreachable code).

This CL also contains the following minor changes:

* Fix reaching type of the CheckSmi argument when CheckSmi is moved
  in LICM::TrySpecializeSmiPhi. It looks like it was previosuly
  unnoticed due to full recomputation of types in type propagator.

* Rename local variables to better follow style guide (follow-up
  to my previous change).

* Handle kNE along with other comparisons in AOT.

Issue: https://github.com/dart-lang/sdk/issues/30480
==========

to

==========
[vm] Implement gradual refinement of types

Before this CL, each invocation of FlowGraphTypePropagator discarded
(overwritten) all previously inferred types. Due to re-structuring of
the IR (for example, InstanceCall to _simpleInstanceOf may be replaced
with various IR sequences), FlowGraphTypePropagator may yield
better or worse results (for example, not all replacements of
_simpleInstanceOf are recognized by FlowGraphTypePropagator).

As the result, inferred type information could be lost at later
stages of the compilation pipeline. Code generation, which looks
at the types may not see the same types as earlier stages of
compilation pipeline, so EmitNativeCode() may generate code which is
out of sync with ComputeCanDeoptimize().

This CL introduces refinement of types: old type is no longer
blindly replaced with newly inferred type. Instead, more specific type
is selected among new and old types. Conservatively, the new type is
preferred if the types are unrelated (it could happen in certain
corner cases, such as unreachable code).

This CL also contains the following minor changes:

* Fix reaching type of the CheckSmi argument when CheckSmi is moved
  in LICM::TrySpecializeSmiPhi. It looks like it was previosuly
  unnoticed due to full recomputation of types in type propagator.

* Rename local variables to better follow style guide (follow-up
  to my previous change).

* Handle kNE along with other comparisons in AOT.

R=rmacnak@google.com, vegorov@google.com

Issue: https://github.com/dart-lang/sdk/issues/30480
Committed:
https://github.com/dart-lang/sdk/commit/3cc0cea37e56bc5c590905f2da4bc5d9db9d73e6
==========

[alexmarkov, 2017-08-30 19:12:23]

Committed patchset #3 (id:40001) manually as
3cc0cea37e56bc5c590905f2da4bc5d9db9d73e6 (presubmit successful).