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

runtime/vm/precompiler.cc

 // Copyright (c) 2015, 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.
 
 #include "vm/precompiler.h"
 
 #include "vm/aot_optimizer.h"
 #include "vm/assembler.h"
 #include "vm/ast_printer.h"
 #include "vm/branch_optimizer.h"
@@ skipping 183 matching lines @@
     return Error::null();
   } else {
     Thread* thread = Thread::Current();
     const Error& error = Error::Handle(thread->sticky_error());
     thread->clear_sticky_error();
     return error.raw();
   }
 }
 
 
+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),
     isolate_(thread->isolate()),
     reset_fields_(reset_fields),
     changed_(false),
     function_count_(0),
     class_count_(0),
     selector_count_(0),
     dropped_function_count_(0),
@@ skipping 26 matching lines @@
     StackZone stack_zone(T);
     zone_ = stack_zone.GetZone();
 
     { HANDLESCOPE(T);
       // Make sure class hierarchy is stable before compilation so that CHA
       // can be used. Also ensures lookup of entry points won't miss functions
       // because their class hasn't been finalized yet.
       FinalizeAllClasses();
 
       SortClasses();
+      TypeRangeCache trc(T, I->class_table()->NumCids());
 
       // Precompile static initializers to compute result type information.
       PrecompileStaticInitializers();
 
       // Precompile constructors to compute type information for final fields.
       ClearAllCode();
       PrecompileConstructors();
 
       for (intptr_t round = 0; round < FLAG_precompiler_rounds; round++) {
         if (FLAG_trace_precompiler) {
@@ skipping 2320 matching lines @@
   GrowableArray<intptr_t> inlining_black_list;
 
   while (!done) {
     const intptr_t prev_deopt_id = thread()->deopt_id();
     thread()->set_deopt_id(0);
     LongJumpScope jump;
     const intptr_t val = setjmp(*jump.Set());
     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());
 
       // TimerScope needs an isolate to be properly terminated in case of a
       // LongJump.
       {
         CSTAT_TIMER_SCOPE(thread(), graphbuilder_timer);
         ZoneGrowableArray<const ICData*>* ic_data_array =
             new(zone) ZoneGrowableArray<const ICData*>();
 #ifndef PRODUCT
         TimelineDurationScope tds(thread(),
                                   compiler_timeline,
                                   "BuildFlowGraph");
 #endif  // !PRODUCT
         flow_graph = pipeline->BuildFlowGraph(zone,
                                               parsed_function(),
                                               *ic_data_array,
                                               Compiler::kNoOSRDeoptId);
       }
 
       const bool print_flow_graph =
           (FLAG_print_flow_graph ||
            (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(),
                                   compiler_timeline,
                                   "ComputeSSA");
 #endif  // !PRODUCT
         CSTAT_TIMER_SCOPE(thread(), ssa_timer);
         // Transform to SSA (virtual register 0 and no inlining arguments).
         flow_graph->ComputeSSA(0, NULL);
         DEBUG_ASSERT(flow_graph->VerifyUseLists());
@@ skipping 104 matching lines @@
           flow_graph->Canonicalize();
         }
         DEBUG_ASSERT(flow_graph->VerifyUseLists());
 
         {
 #ifndef PRODUCT
           TimelineDurationScope tds2(thread(),
                                      compiler_timeline,
                                      "BranchSimplifier");
 #endif  // !PRODUCT
+
           BranchSimplifier::Simplify(flow_graph);
           DEBUG_ASSERT(flow_graph->VerifyUseLists());
 
           IfConverter::Simplify(flow_graph);
           DEBUG_ASSERT(flow_graph->VerifyUseLists());
         }
 
         if (FLAG_constant_propagation) {
 #ifndef PRODUCT
           TimelineDurationScope tds2(thread(),
@@ skipping 222 matching lines @@
         // Compute and store graph informations (call & instruction counts)
         // to be later used by the inliner.
         FlowGraphInliner::CollectGraphInfo(flow_graph, true);
 
         {
 #ifndef PRODUCT
           TimelineDurationScope tds2(thread(),
                                      compiler_timeline,
                                      "AllocateRegisters");
 #endif  // !PRODUCT
+
           // Perform register allocation on the SSA graph.
           FlowGraphAllocator allocator(*flow_graph);
           allocator.AllocateRegisters();
         }
 
         if (print_flow_graph) {
           FlowGraphPrinter::PrintGraph("After Optimizations", flow_graph);
         }
       }
 
@@ skipping 183 matching lines @@
 
   ASSERT(FLAG_precompiled_mode);
   const bool optimized = function.IsOptimizable();  // False for natives.
   DartPrecompilationPipeline pipeline(zone, field_type_map);
   return PrecompileFunctionHelper(&pipeline, function, optimized);
 }
 
 #endif  // DART_PRECOMPILER
 
 }  // namespace dart