AOT: Use a cid range check when possible to implement type tests.

runtime/vm/precompiler.cc

Index: runtime/vm/precompiler.cc
diff --git a/runtime/vm/precompiler.cc b/runtime/vm/precompiler.cc
index 7579680c7f5a3185facd5268bb27924c24bc9981..5950e3deee8d602f66f68e5aaf3c01acbfea63f7 100644
--- a/runtime/vm/precompiler.cc
+++ b/runtime/vm/precompiler.cc
@@ -201,6 +201,85 @@ RawError* Precompiler::CompileAll(
 }
 
 
+bool TypeRangeCache::InstanceOfHasClassRange(const AbstractType& type,
+                                             intptr_t* lower_limit,
+                                             intptr_t* upper_limit) {
+  ASSERT(type.IsFinalized() && !type.IsMalformedOrMalbounded());
+
+  if (!type.IsInstantiated()) return false;
+  if (type.IsFunctionType()) return false;
+
+  const TypeArguments& type_arguments =
+      TypeArguments::Handle(type.arguments());
+  if (!type_arguments.IsNull() &&
+      !type_arguments.IsRaw(0, type_arguments.Length())) return false;
+
+
+  intptr_t type_cid = type.type_class_id();
+  if (lower_limits_[type_cid] == kNotContiguous) return false;
+  if (lower_limits_[type_cid] != kNotComputed) {
+    *lower_limit = lower_limits_[type_cid];
+    *upper_limit = upper_limits_[type_cid];
+    return true;
+  }
+
+
+  *lower_limit = -1;
+  *upper_limit = -1;
+  intptr_t last_matching_cid = -1;
+
+  ClassTable* table = thread_->isolate()->class_table();
+  Class& cls = Class::Handle();
+  AbstractType& cls_type = AbstractType::Handle();
+  for (intptr_t cid = kInstanceCid; cid < table->NumCids(); cid++) {
+    if (!table->HasValidClassAt(cid)) continue;
+    if (cid == kVoidCid) continue;
+    if (cid == kDynamicCid) continue;
+    cls = table->At(cid);
+    if (cls.is_abstract()) continue;
+    if (cls.is_patch()) continue;
+    if (cls.IsTopLevel()) continue;
+
+    cls_type = cls.DeclarationType();

[rmacnak, 2016/09/07 01:20:27]

Regis, should I used DeclarationType or RareType?

[regis, 2016/09/07 17:06:07]

RareType, because DeclarationType would yield an uninstantiated type for a
generic class. And you cannot have a left-hand side uninstantiated type in a
type test.

[rmacnak, 2016/09/07 22:21:28]

Done.

+    if (cls_type.IsSubtypeOf(type, NULL, NULL, Heap::kOld)) {
+      last_matching_cid = cid;
+      if (*lower_limit == -1) {
+        // Found beginning of range.
+        *lower_limit = cid;
+      } else if (*upper_limit == -1) {
+        // Expanding range.
+      } else {
+        // Found a second range.
+        lower_limits_[type_cid] = kNotContiguous;
+        return false;
+      }
+    } else {
+      if (*lower_limit == -1) {
+        // Still before range.
+      } else if (*upper_limit == -1) {
+        // Found end of range.
+        *upper_limit = last_matching_cid;
+      } else {
+        // After range.
+      }
+    }
+  }
+  ASSERT(*lower_limit != -1);  // Class is at least a subtype of itself.
+
+  if (*upper_limit == -1) {
+    ASSERT(last_matching_cid != -1);
+    *upper_limit = last_matching_cid;
+  }
+
+  OS::Print("Type check for is %s is cid range [%" Pd ", %" Pd "]\n",
+            type.ToCString(), *lower_limit, *upper_limit);
+
+  lower_limits_[type_cid] = *lower_limit;
+  upper_limits_[type_cid] = *upper_limit;
+  return true;
+}
+
+
 Precompiler::Precompiler(Thread* thread, bool reset_fields) :
     thread_(thread),
     zone_(NULL),
@@ -247,6 +326,7 @@ void Precompiler::DoCompileAll(
       FinalizeAllClasses();
 
       SortClasses();
+      TypeRangeCache trc(T, I->class_table()->NumCids());
 
       // Precompile static initializers to compute result type information.
       PrecompileStaticInitializers();
@@ -2587,7 +2667,7 @@ bool PrecompileParsedFunctionHelper::Compile(CompilationPipeline* pipeline) {
     if (val == 0) {
       FlowGraph* flow_graph = NULL;
 
-      // Class hierarchy analysis is registered with the isolate in the
+      // Class hierarchy analysis is registered with the thread in the
       // constructor and unregisters itself upon destruction.
       CHA cha(thread());
 
@@ -2613,10 +2693,6 @@ bool PrecompileParsedFunctionHelper::Compile(CompilationPipeline* pipeline) {
            (optimized() && FLAG_print_flow_graph_optimized)) &&
           FlowGraphPrinter::ShouldPrint(function);
 
-      if (print_flow_graph) {
-        FlowGraphPrinter::PrintGraph("Before Optimizations", flow_graph);
-      }
-
       if (optimized()) {
 #ifndef PRODUCT
         TimelineDurationScope tds(thread(),
@@ -2741,6 +2817,7 @@ bool PrecompileParsedFunctionHelper::Compile(CompilationPipeline* pipeline) {
                                      compiler_timeline,
                                      "BranchSimplifier");
 #endif  // !PRODUCT
+
           BranchSimplifier::Simplify(flow_graph);
           DEBUG_ASSERT(flow_graph->VerifyUseLists());
 
@@ -2983,6 +3060,7 @@ bool PrecompileParsedFunctionHelper::Compile(CompilationPipeline* pipeline) {
                                      compiler_timeline,
                                      "AllocateRegisters");
 #endif  // !PRODUCT
+
           // Perform register allocation on the SSA graph.
           FlowGraphAllocator allocator(*flow_graph);
           allocator.AllocateRegisters();