Start work on a non-complete type inferrer. Currently only analyzes return types.

Start work on a non-complete type inferrer. Currently only analyzes return types.
Committed: https://code.google.com/p/dart/source/detail?r=18447

[ngeoffray, 2013-02-11 18:12:23]

This is now ready for review. It currently only infers return types and does not
analyze some AST nodes (like send sets, or constructor initializers), but I
wanted to keep this CL somehow at its minimum.

I measured the time of the analysis and it's currently always faster than
resolution (from 2x to 1x) and faster than SSA build (2x). I checked on swarm,
dart2js and some benchmarks.

Also note that I don't use any CHA information in this CL, I intend to use
FunctionSet for that.

[sra1, 2013-02-12 03:20:27]

Some nice wins.

I patched this CL and saw that there were some uncalled bailouts. e.g.
$.Primitives_parseInt$bailout 
Any ideas why?

https://chromiumcodereview.appspot.com/12211112/diff/8001/sdk/lib/_internal/c...
File sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart
(right):

https://chromiumcodereview.appspot.com/12211112/diff/8001/sdk/lib/_internal/c...
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:19:
final Set<E> singletons = new Set<E>();
I normally think of a singleton as a set containing one element.  Perhaps a
better name would be 'inQueue' or 'elementsInQueue'.

https://chromiumcodereview.appspot.com/12211112/diff/8001/sdk/lib/_internal/c...
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:74: *
Sentinal used by the inferrer to notify that it gave up finding a type
Sentinel

https://chromiumcodereview.appspot.com/12211112/diff/8001/sdk/lib/_internal/c...
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:642:
for (var type in nativeBehavior.typesInstantiated) {
Should be using typesReturned (they should be the same for JS, but may be
different for methods).

The conversion from nativeBehavior.typesReturned to the type inference
representation (ClassElement in this analysis) should be pulled out so it can be
reused for calls on native methods.

https://chromiumcodereview.appspot.com/12211112/diff/8001/sdk/lib/_internal/c...
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:648:
} else {
If the analysis assumes the types are nullable, also accept class Null.

https://chromiumcodereview.appspot.com/12211112/diff/8001/sdk/lib/_internal/c...
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:777:
if (firstType == secondType) return firstType;
Maybe abstract out leastUpperBound and

  return leastUpperBound(firstType, secondType);

[polux, 2013-02-12 08:39:49]

Hello,

if I understand correctly, this CL introduces a type inferrer akin to the one
I'm writing but which produces non-complete information in the sense that the
unions it computes are not guaranteed to be supersets of the actual concrete
types, am I right? (What leads me to think this is that I don't see any handling
of default arguments and thus the calls they might perform are not taken into
account, possibly forgetting to invalidate some stuff).

If this is the case, we could maybe try merging our efforts: right now when I
bail out, I don't erase the information obtained so far. If you're fine with
partial information, then we could 

  1. Try to simply run with --enable-concrete-type-inference, ignore the fact
that the analysis bailed out and see what we gain with the rest of the changes
in your CL.

  2. Slightly modify my inferrer such that it doesn't bail out when it
encounters an unknown construct but returns dynamic instead such that it
analyses as much as possible.

I'm slightly concerned that the two analyzers seem to be strongly overlapping
and I'm totally fine with you modifying "mine" rather than rewriting a new one.


On 2013/02/12 03:20:27, sra1 wrote:
> Some nice wins.
> 
> I patched this CL and saw that there were some uncalled bailouts. e.g.
> $.Primitives_parseInt$bailout 
> Any ideas why?
> 
>
https://chromiumcodereview.appspot.com/12211112/diff/8001/sdk/lib/_internal/c...
> File
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart
> (right):
> 
>
https://chromiumcodereview.appspot.com/12211112/diff/8001/sdk/lib/_internal/c...
> sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:19:
> final Set<E> singletons = new Set<E>();
> I normally think of a singleton as a set containing one element.  Perhaps a
> better name would be 'inQueue' or 'elementsInQueue'.
> 
>
https://chromiumcodereview.appspot.com/12211112/diff/8001/sdk/lib/_internal/c...
> sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:74:
*
> Sentinal used by the inferrer to notify that it gave up finding a type
> Sentinel
> 
>
https://chromiumcodereview.appspot.com/12211112/diff/8001/sdk/lib/_internal/c...
>
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:642:
> for (var type in nativeBehavior.typesInstantiated) {
> Should be using typesReturned (they should be the same for JS, but may be
> different for methods).
> 
> The conversion from nativeBehavior.typesReturned to the type inference
> representation (ClassElement in this analysis) should be pulled out so it can
be
> reused for calls on native methods.
> 
>
https://chromiumcodereview.appspot.com/12211112/diff/8001/sdk/lib/_internal/c...
>
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:648:
> } else {
> If the analysis assumes the types are nullable, also accept class Null.
> 
>
https://chromiumcodereview.appspot.com/12211112/diff/8001/sdk/lib/_internal/c...
>
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:777:
> if (firstType == secondType) return firstType;
> Maybe abstract out leastUpperBound and
> 
>   return leastUpperBound(firstType, secondType);

[ngeoffray, 2013-02-12 09:02:32]

Hi Paul,

On 2013/02/12 08:39:49, polux wrote:
> Hello,
> 
> if I understand correctly, this CL introduces a type inferrer akin to the one
> I'm writing but which produces non-complete information in the sense that the
> unions it computes are not guaranteed to be supersets of the actual concrete
> types, am I right?

For now it just gives up unioning types if the types are different.

> (What leads me to think this is that I don't see any handling
> of default arguments and thus the calls they might perform are not taken into
> account, possibly forgetting to invalidate some stuff).

That's correct, currently it does not analyze arguments. We will probably add it
in the future. 

> 
> If this is the case, we could maybe try merging our efforts: right now when I
> bail out, I don't erase the information obtained so far. If you're fine with
> partial information, then we could 
> 
>   1. Try to simply run with --enable-concrete-type-inference, ignore the fact
> that the analysis bailed out and see what we gain with the rest of the changes
> in your CL.
> 
>   2. Slightly modify my inferrer such that it doesn't bail out when it
> encounters an unknown construct but returns dynamic instead such that it
> analyses as much as possible.
> 
> I'm slightly concerned that the two analyzers seem to be strongly overlapping
> and I'm totally fine with you modifying "mine" rather than rewriting a new
one.

I think sharing as much code as possible will be a viable future work, but even
though the two analyzers have the same goal of inferring types, we should be
careful on how and how much they want to achieve:

- The concrete type inferrer can take as much time as it wants and needs for its
analysis. I don't see it bounded by time. And the information it returns (e.g.
union types) will always be much richer than the other analyzer.

- The simple type inferrer *will* be limited in time, and we'll have to make
tradeoffs on what's achievable in reasonable time.

So even though the two inferrers will and already do compute similar things,
there is a lot of logic in the AST visitors and in the analyzer that drives the
inference, that is different. And I'd prefer in the initial phase of this new
inferrer, to not step on each other's toes until both inferrers are useful.

For example consider the type system they're using:
- ConcreteType for the concrete type inferrer.
- ClassElement for the simple type inferrer.

I do plan on updating the type system of the simple type inferrer to use an
extended DartType, but not making it as rich as the ConcreteType. Trying to
merge the two type systems is something we can consider once both inferrers are
fairly stable and useful.

Does that sound reasonable to you?

> 
> 
> On 2013/02/12 03:20:27, sra1 wrote:
> > Some nice wins.
> > 
> > I patched this CL and saw that there were some uncalled bailouts. e.g.
> > $.Primitives_parseInt$bailout 
> > Any ideas why?
> > 
> >
>
https://chromiumcodereview.appspot.com/12211112/diff/8001/sdk/lib/_internal/c...
> > File
> sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart
> > (right):
> > 
> >
>
https://chromiumcodereview.appspot.com/12211112/diff/8001/sdk/lib/_internal/c...
> >
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:19:
> > final Set<E> singletons = new Set<E>();
> > I normally think of a singleton as a set containing one element.  Perhaps a
> > better name would be 'inQueue' or 'elementsInQueue'.
> > 
> >
>
https://chromiumcodereview.appspot.com/12211112/diff/8001/sdk/lib/_internal/c...
> >
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:74:
> *
> > Sentinal used by the inferrer to notify that it gave up finding a type
> > Sentinel
> > 
> >
>
https://chromiumcodereview.appspot.com/12211112/diff/8001/sdk/lib/_internal/c...
> >
>
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:642:
> > for (var type in nativeBehavior.typesInstantiated) {
> > Should be using typesReturned (they should be the same for JS, but may be
> > different for methods).
> > 
> > The conversion from nativeBehavior.typesReturned to the type inference
> > representation (ClassElement in this analysis) should be pulled out so it
can
> be
> > reused for calls on native methods.
> > 
> >
>
https://chromiumcodereview.appspot.com/12211112/diff/8001/sdk/lib/_internal/c...
> >
>
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:648:
> > } else {
> > If the analysis assumes the types are nullable, also accept class Null.
> > 
> >
>
https://chromiumcodereview.appspot.com/12211112/diff/8001/sdk/lib/_internal/c...
> >
>
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:777:
> > if (firstType == secondType) return firstType;
> > Maybe abstract out leastUpperBound and
> > 
> >   return leastUpperBound(firstType, secondType);

[kasperl, 2013-02-12 10:33:44]

LGTM with comments:

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
File sdk/lib/_internal/compiler/implementation/ssa/builder.dart (right):

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/ssa/builder.dart:3368: //
TODO(ngeoffray): Only do this if knowing the return type is
Move TODO to recompilation branch.

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/ssa/builder.dart:3370: HType
returnType = mapInferredType(
Maybe add a helper for getting the guaranteed HType for an element? Useful in at
least two places.

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
File sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart
(right):

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:21:
void addLast(E element) {
Maybe rename this to WorkSet (obvious that it doesn't keep duplicates) and
change addLast/removeLast to add and removeAny? Does it matter for the other
part of the algorithm in which order you do the processing (except for
performance perhaps)?

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:41:
final Map<Element, Set<Element>> callersOf =
Are all these maps being kept alive even after we're done inferring types? Maybe
you should clear them somewhere.

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:51: *
Maps a name to elements in the universe that have that name.
Long term, you probably want to map selectors to the elements they can end up
accessing? A FunctionSet should be a reasonable foundation for that.

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:65:
final SingletonWorkQueue<Element> workQueue =
workSet?

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:153:
if (selector == null || selector.isSetter() || selector.isIndexSet()) {
Isn't it easy to deal with setters and index-sets? The type of a setter
invocation is the type of the value expression node. Maybe the best idea is to
avoid ever calling this from the builder on a SendSet node -- and always call it
on the value expression node instead? In that case, you could probably keep this
code as is or assert that this is never called on a send-set.

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:159:
if (returnType == null
Share this code with the stuff in getConcreteTypeOfElement?

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:201:
for (int i = max; i >=0; i--) {
>=0 should be >= 0

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:322:
if (cls == null
Share this code with the stuff in returnTypeOfCalledSelector? Is it really a
good idea to split this into two methods? Why not just have a single
returnTypeFromSelector?

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:588:
return compiler.dynamicClass;
It seems reasonably easy to get a type for this?

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:593:
return analyzedElement.getEnclosingClass();
Isn't this broken (this may refer to a subclass or subtype in case of mixins)?
Shouldn't be easy to come up with an example where this breaks?

[ngeoffray, 2013-02-12 11:58:22]

Thanks all for the comments

@Stephen: thanks for catching the unnecessary bailouts. The problem was that the
type guard inserter was somehow not looking at the inferred type of a invoke
dynamic. By fixing this problem, I was able to get rid of more bailout methods,
as well as making others smaller.

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
File sdk/lib/_internal/compiler/implementation/ssa/builder.dart (right):

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/ssa/builder.dart:3368: //
TODO(ngeoffray): Only do this if knowing the return type is
On 2013/02/12 10:33:44, kasperl wrote:
> Move TODO to recompilation branch.

Done.

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/ssa/builder.dart:3370: HType
returnType = mapInferredType(
On 2013/02/12 10:33:44, kasperl wrote:
> Maybe add a helper for getting the guaranteed HType for an element? Useful in
at
> least two places.

Done.

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
File sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart
(right):

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:19:
final Set<E> singletons = new Set<E>();
On 2013/02/12 03:20:27, sra1 wrote:
> I normally think of a singleton as a set containing one element.  Perhaps a
> better name would be 'inQueue' or 'elementsInQueue'.

Renamed to elementsInqueue.

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:21:
void addLast(E element) {
On 2013/02/12 10:33:44, kasperl wrote:
> Maybe rename this to WorkSet (obvious that it doesn't keep duplicates) and
> change addLast/removeLast to add and removeAny? Does it matter for the other
> part of the algorithm in which order you do the processing (except for
> performance perhaps)?

Changed to add/remove (not sure about the removeAny?). Currently the order only
matters when setting up the work queue. We could think of later adding some
constraints when putting back multiple elements in the workqueue (e.g. the one
that has the least calls gets popped first, called methods of an element gets
popped first, etc).

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:41:
final Map<Element, Set<Element>> callersOf =
On 2013/02/12 10:33:44, kasperl wrote:
> Are all these maps being kept alive even after we're done inferring types?
Maybe
> you should clear them somewhere.

Done. I might have to introduce a new class to hold those temporary data
structures. Next CL.

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:51: *
Maps a name to elements in the universe that have that name.
On 2013/02/12 10:33:44, kasperl wrote:
> Long term, you probably want to map selectors to the elements they can end up
> accessing? A FunctionSet should be a reasonable foundation for that.

Yes. About that: are you thinking along the lines of one FunctionSet per
name/selector, or one FunctionSet for the entire program? One FunctionSet per
name/selector seems very expensive.

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:65:
final SingletonWorkQueue<Element> workQueue =
On 2013/02/12 10:33:44, kasperl wrote:
> workSet?

Done.

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:74: *
Sentinal used by the inferrer to notify that it gave up finding a type
On 2013/02/12 03:20:27, sra1 wrote:
> Sentinel

Done.

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:153:
if (selector == null || selector.isSetter() || selector.isIndexSet()) {
On 2013/02/12 10:33:44, kasperl wrote:
> Isn't it easy to deal with setters and index-sets? The type of a setter
> invocation is the type of the value expression node. Maybe the best idea is to
> avoid ever calling this from the builder on a SendSet node -- and always call
it
> on the value expression node instead? In that case, you could probably keep
this
> code as is or assert that this is never called on a send-set.

Problem is that ++, []=, --, += are SendSet that are being used as Send when
doing the +, [], -. I will add a TODO here to later figure out if/should we have
two selectors for such SendSet.

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:159:
if (returnType == null
On 2013/02/12 10:33:44, kasperl wrote:
> Share this code with the stuff in getConcreteTypeOfElement?

Done.

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:201:
for (int i = max; i >=0; i--) {
On 2013/02/12 10:33:44, kasperl wrote:
> >=0 should be >= 0

Done.

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:322:
if (cls == null
On 2013/02/12 10:33:44, kasperl wrote:
> Share this code with the stuff in returnTypeOfCalledSelector? Is it really a
> good idea to split this into two methods? Why not just have a single
> returnTypeFromSelector?

Done.

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:588:
return compiler.dynamicClass;
On 2013/02/12 10:33:44, kasperl wrote:
> It seems reasonably easy to get a type for this?

Not really because of []= and compound assignments. Added a TODO.

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:593:
return analyzedElement.getEnclosingClass();
On 2013/02/12 10:33:44, kasperl wrote:
> Isn't this broken (this may refer to a subclass or subtype in case of mixins)?
> Shouldn't be easy to come up with an example where this breaks?

Good catch. Changed to return dynamic, and added a test.

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:642:
for (var type in nativeBehavior.typesInstantiated) {
On 2013/02/12 03:20:27, sra1 wrote:
> Should be using typesReturned (they should be the same for JS, but may be
> different for methods).
> 
> The conversion from nativeBehavior.typesReturned to the type inference
> representation (ClassElement in this analysis) should be pulled out so it can
be
> reused for calls on native methods.

Done.

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:648:
} else {
On 2013/02/12 03:20:27, sra1 wrote:
> If the analysis assumes the types are nullable, also accept class Null.

Currently, it does not assume they are nullable. A return type will at runtime
be the exact non-null type.

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:777:
if (firstType == secondType) return firstType;
On 2013/02/12 03:20:27, sra1 wrote:
> Maybe abstract out leastUpperBound and
> 
>   return leastUpperBound(firstType, secondType);

Done.

[kasperl, 2013-02-12 12:21:19]

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
File sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart
(right):

https://codereview.chromium.org/12211112/diff/8001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/types/simple_types_inferrer.dart:51: *
Maps a name to elements in the universe that have that name.
On 2013/02/12 11:58:22, ngeoffray wrote:
> On 2013/02/12 10:33:44, kasperl wrote:
> > Long term, you probably want to map selectors to the elements they can end
up
> > accessing? A FunctionSet should be a reasonable foundation for that.
> 
> Yes. About that: are you thinking along the lines of one FunctionSet per
> name/selector, or one FunctionSet for the entire program? One FunctionSet per
> name/selector seems very expensive.

I was thinking one big FunctionSet.