Add SSA instructions for reified type information

pkg/compiler/lib/src/ssa/nodes.dart

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 import '../closure.dart';
 import '../common.dart';
 import '../compiler.dart' show Compiler;
 import '../constants/constant_system.dart';
 import '../constants/values.dart';
 import '../dart_types.dart';
@@ skipping 81 matching lines @@
   R visitTruncatingDivide(HTruncatingDivide node);
   R visitTry(HTry node);
   R visitTypeConversion(HTypeConversion node);
   R visitTypeKnown(HTypeKnown node);
   R visitYield(HYield node);
   R visitReadTypeVariable(HReadTypeVariable node);
   R visitFunctionType(HFunctionType node);
   R visitVoidType(HVoidType node);
   R visitInterfaceType(HInterfaceType node);
   R visitDynamicType(HDynamicType node);
+
+  R visitTypeInfoReadRaw(HTypeInfoReadRaw node);
+  R visitTypeInfoReadVariable(HTypeInfoReadVariable node);
+  R visitTypeInfoExpression(HTypeInfoExpression node);
 }
 
 abstract class HGraphVisitor {
   visitDominatorTree(HGraph graph) {
     void visitBasicBlockAndSuccessors(HBasicBlock block) {
       visitBasicBlock(block);
       List dominated = block.dominatedBlocks;
       for (int i = 0; i < dominated.length; i++) {
         visitBasicBlockAndSuccessors(dominated[i]);
       }
@@ skipping 275 matching lines @@
   visitIsViaInterceptor(HIsViaInterceptor node) => visitInstruction(node);
   visitTypeConversion(HTypeConversion node) => visitCheck(node);
   visitTypeKnown(HTypeKnown node) => visitCheck(node);
   visitReadTypeVariable(HReadTypeVariable node) => visitInstruction(node);
   visitFunctionType(HFunctionType node) => visitInstruction(node);
   visitVoidType(HVoidType node) => visitInstruction(node);
   visitInterfaceType(HInterfaceType node) => visitInstruction(node);
   visitDynamicType(HDynamicType node) => visitInstruction(node);
   visitAwait(HAwait node) => visitInstruction(node);
   visitYield(HYield node) => visitInstruction(node);
+
+  visitTypeInfoReadRaw(HTypeInfoReadRaw node) => visitInstruction(node);
+  visitTypeInfoReadVariable(HTypeInfoReadVariable node) =>
+      visitInstruction(node);
+  visitTypeInfoExpression(HTypeInfoExpression node) => visitInstruction(node);
 }
 
 class SubGraph {
   // The first and last block of the sub-graph.
   final HBasicBlock start;
   final HBasicBlock end;
 
   const SubGraph(this.start, this.end);
 
   bool contains(HBasicBlock block) {
@@ skipping 440 matching lines @@
   static const int INVOKE_DYNAMIC_TYPECODE = 29;
   static const int SHIFT_RIGHT_TYPECODE = 30;
   static const int READ_TYPE_VARIABLE_TYPECODE = 31;
   static const int FUNCTION_TYPE_TYPECODE = 32;
   static const int VOID_TYPE_TYPECODE = 33;
   static const int INTERFACE_TYPE_TYPECODE = 34;
   static const int DYNAMIC_TYPE_TYPECODE = 35;
   static const int TRUNCATING_DIVIDE_TYPECODE = 36;
   static const int IS_VIA_INTERCEPTOR_TYPECODE = 37;
 
+  static const int TYPE_INFO_READ_RAW_TYPECODE = 38;
+  static const int TYPE_INFO_READ_VARIABLE_TYPECODE = 39;
+  static const int TYPE_INFO_EXPRESSION_TYPECODE = 40;
+
   HInstruction(this.inputs, this.instructionType)
       : id = idCounter++,
         usedBy = <HInstruction>[] {
     assert(inputs.every((e) => e != null));
   }
 
   int get hashCode => id;
 
   bool useGvn() => _useGvn;
   void setUseGvn() {
@@ skipping 2308 matching lines @@
   HBasicBlock get end {
     // We don't create a switch block if there are no cases.
     assert(!statements.isEmpty);
     return statements.last.end;
   }
 
   bool accept(HStatementInformationVisitor visitor) =>
       visitor.visitSwitchInfo(this);
 }
 
+/// Reads raw reified type info from an object.
+class HTypeInfoReadRaw extends HInstruction {
+  HTypeInfoReadRaw(HInstruction receiver, TypeMask instructionType)
+      : super(<HInstruction>[receiver], instructionType) {
+    setUseGvn();
+  }
+
+  accept(HVisitor visitor) => visitor.visitTypeInfoReadRaw(this);
+
+  bool canThrow() => false;
+
+  int typeCode() => HInstruction.TYPE_INFO_READ_RAW_TYPECODE;
+  bool typeEquals(HInstruction other) => other is HTypeInfoReadRaw;
+
+  bool dataEquals(HTypeInfoReadRaw other) {
+    return true;
+  }
+}
+
+/// Reads a type variable from an object. The read may be a simple indexing of
+/// the type parameters or it may require 'substitution'.
+class HTypeInfoReadVariable extends HInstruction {
+  /// The type variable being read.
+  final TypeVariableType variable;
+
+  HTypeInfoReadVariable(
+      this.variable, HInstruction receiver, TypeMask instructionType)
+      : super(<HInstruction>[receiver], instructionType) {
+    setUseGvn();
+  }
+
+  accept(HVisitor visitor) => visitor.visitTypeInfoReadVariable(this);
+
+  bool canThrow() => false;
+
+  int typeCode() => HInstruction.TYPE_INFO_READ_VARIABLE_TYPECODE;
+  bool typeEquals(HInstruction other) => other is HTypeInfoReadVariable;
+
+  bool dataEquals(HTypeInfoReadVariable other) {
+    return variable.element == other.variable.element;
+  }
+}
+
+enum TypeInfoExpressionKind { COMPLETE, INSTANCE }
+
+/// Constructs a representation of a closed or ground-term type (that is, a type
+/// without type variables).
+///
+/// There are two forms:
+///
+/// - COMPLETE: A complete form that is self contained, used for the values of
+///   type parameters and non-raw is-checks.
+///
+/// - INSTANCE: A headless flat form for representing the sequence of values of

[Siggi Cherem (dart-lang), 2016/08/19 18:21:46]

I'm trying to understand the need for the distinction between COMPLETE and
INSTANCE. When do we expect to use each? Would you say that INSTANCE is only
used to specify the rti when calling a constructor (new Foo(), [] literals),
while the COMPLETE is used for nested type arguments that are given to the
INSTANCE type?

[sra1, 2016/08/19 18:47:44]

Correct.
This is just how it is currently done.
I hope to simplify this later.

+///   the type parameters of an instance of a generic type.
+///
+/// The COMPLETE form value is constructed from [dartType] by replacing the type
+/// variables with consecutive values from [arguments], in the order generated

[Siggi Cherem (dart-lang), 2016/08/19 18:21:46]

[arguments] => [inputs]?

[sra1, 2016/08/19 18:47:43]

Done.

+/// by [DartType.forEachTypeVariable].  The type variables in [dartType] are
+/// treated as 'holes' in the term, which means that it must be ensured at
+/// construction, that duplicate occurences of a type variable in [dartType] are
+/// assigned the same value.
+///
+/// The INSTANCE form is constructed as a list of [arguments]. This is the same

[Siggi Cherem (dart-lang), 2016/08/19 18:21:46]

ditto?

[sra1, 2016/08/19 18:47:43]

Done.

+/// as the COMPLETE form for the 'thisType', except the root term's type is
+/// missing; this is implicit as the raw type of instance.  The [dartType] of
+/// the INSTANCE form must be the thisType of some class.
+///
+/// We want to remove the constrains on the INSTANCE form. In the meantime we
+/// get by with a tree of TypeExpressions.  Consider:
+///
+///     class Foo<T> {
+///       ... new Set<List<T>>()
+///     }
+///     class Set<E1> {
+///       factory Set() => new _LinkedHashSet<E1>();
+///     }
+///     class List<E2> { ... }
+///     class _LinkedHashSet<E3> { ... }
+///
+/// After inlining the factory constructor for `Set<E1>`, the HForeignNew
+/// should have type `_LinkedHashSet<List<T>>` and the TypeExpression should be
+/// a tree:
+///
+///    HForeignNew(dartType: _LinkedHashSet<List<T>>,
+///        [], // No arguments
+///        HTypeInfoExpression(INSTANCE,
+///            dartType: _LinkedHashSet<E3>, // _LinkedHashSet's thisType
+///            HTypeInfoExpression(COMPLETE,  // E3 = List<T>
+///                dartType: List<E2>,
+///                HTypeInfoReadVariable(this, T)))) // E2 = T
+
+// TODO(sra): The INSTANCE form requires the actual instance for full
+// interpretation. If the COMPLETE form was used on instances, then we could
+// simplify HTypeInfoReadVariable without an object.
+
+class HTypeInfoExpression extends HInstruction {
+  final TypeInfoExpressionKind kind;
+  final DartType dartType;
+  HTypeInfoExpression(this.kind, this.dartType, List<HInstruction> inputs,
+      TypeMask instructionType)
+      : super(inputs, instructionType) {
+    setUseGvn();
+  }
+
+  accept(HVisitor visitor) => visitor.visitTypeInfoExpression(this);
+
+  bool canThrow() => false;
+
+  int typeCode() => HInstruction.TYPE_INFO_EXPRESSION_TYPECODE;
+  bool typeEquals(HInstruction other) => other is HTypeInfoExpression;
+
+  bool dataEquals(HTypeInfoExpression other) {
+    return kind == other.kind && dartType == other.dartType;
+  }
+
+  String toString() => 'HTypeInfoExpression $kindAsString $dartType';
+
+  String get kindAsString {
+    switch (kind) {
+      case TypeInfoExpressionKind.COMPLETE: return 'COMPLETE';
+      case TypeInfoExpressionKind.INSTANCE: return 'INSTANCE';
+    }
+  }
+}
+
+
 class HReadTypeVariable extends HInstruction {
   /// The type variable being read.
   final TypeVariableType dartType;
 
   final bool hasReceiver;
 
   HReadTypeVariable(
       this.dartType, HInstruction receiver, TypeMask instructionType)
       : hasReceiver = true,
         super(<HInstruction>[receiver], instructionType) {
@@ skipping 82 matching lines @@
 class HDynamicType extends HRuntimeType {
   HDynamicType(DynamicType dartType, TypeMask instructionType)
       : super(const <HInstruction>[], dartType, instructionType);
 
   accept(HVisitor visitor) => visitor.visitDynamicType(this);
 
   int typeCode() => HInstruction.DYNAMIC_TYPE_TYPECODE;
 
   bool typeEquals(HInstruction other) => other is HDynamicType;
 }