type_testing_stubs.cc

Go to the documentation of this file.

// Copyright (c) 2018, 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 <functional>
 
#include "platform/globals.h"
#include "vm/class_id.h"
#include "vm/compiler/assembler/disassembler.h"
#include "vm/compiler/runtime_api.h"
#include "vm/hash_map.h"
#include "vm/longjump.h"
#include "vm/object_store.h"
#include "vm/stub_code.h"
#include "vm/timeline.h"
#include "vm/type_testing_stubs.h"
#include "vm/zone_text_buffer.h"
 
#if !defined(DART_PRECOMPILED_RUNTIME)
#include "vm/compiler/backend/flow_graph_compiler.h"
#include "vm/compiler/backend/il_printer.h"
#endif  // !defined(DART_PRECOMPILED_RUNTIME)
 
#define __ assembler->
 
namespace dart {
 
TypeTestingStubNamer::TypeTestingStubNamer()
    : lib_(Library::Handle()),
      klass_(Class::Handle()),
      type_(AbstractType::Handle()),
      string_(String::Handle()) {}
 
const char* TypeTestingStubNamer::StubNameForType(
    const AbstractType& type) const {
  ZoneTextBuffer buffer(Thread::Current()->zone());
  WriteStubNameForTypeTo(&buffer, type);
  return buffer.buffer();
}
 
void TypeTestingStubNamer::WriteStubNameForTypeTo(
    BaseTextBuffer* buffer,
    const AbstractType& type) const {
  buffer->AddString("TypeTestingStub_");
  StringifyTypeTo(buffer, type);
}
 
void TypeTestingStubNamer::StringifyTypeTo(BaseTextBuffer* buffer,
                                           const AbstractType& type) const {
  NoSafepointScope no_safepoint;
  if (type.IsType()) {
    const intptr_t cid = Type::Cast(type).type_class_id();
    ClassTable* class_table = IsolateGroup::Current()->class_table();
    klass_ = class_table->At(cid);
    ASSERT(!klass_.IsNull());
 
    lib_ = klass_.library();
    if (!lib_.IsNull()) {
      string_ = lib_.url();
      buffer->AddString(string_.ToCString());
    } else {
      buffer->Printf("nolib%" Pd "_", nonce_++);
    }
 
    buffer->AddString("_");
    buffer->AddString(klass_.ScrubbedNameCString());
 
    auto& type_arguments = TypeArguments::Handle(Type::Cast(type).arguments());
    if (!type_arguments.IsNull()) {
      for (intptr_t i = 0, n = type_arguments.Length(); i < n; ++i) {
        type_ = type_arguments.TypeAt(i);
        buffer->AddString("__");
        StringifyTypeTo(buffer, type_);
      }
    }
  } else if (type.IsTypeParameter()) {
    buffer->AddString(TypeParameter::Cast(type).CanonicalNameCString());
  } else if (type.IsRecordType()) {
    const RecordType& rec = RecordType::Cast(type);
    buffer->AddString("Record");
    const intptr_t num_fields = rec.NumFields();
    const auto& field_names =
        Array::Handle(rec.GetFieldNames(Thread::Current()));
    const intptr_t num_positional_fields = num_fields - field_names.Length();
    const auto& field_types = Array::Handle(rec.field_types());
    for (intptr_t i = 0; i < num_fields; ++i) {
      buffer->AddString("__");
      type_ ^= field_types.At(i);
      StringifyTypeTo(buffer, type_);
      if (i >= num_positional_fields) {
        buffer->AddString("_");
        string_ ^= field_names.At(i - num_positional_fields);
        buffer->AddString(string_.ToCString());
      }
    }
  } else {
    buffer->AddString(type.ToCString());
  }
  MakeNameAssemblerSafe(buffer);
}
 
void TypeTestingStubNamer::MakeNameAssemblerSafe(BaseTextBuffer* buffer) {
  char* cursor = buffer->buffer();
  while (*cursor != '\0') {
    char c = *cursor;
    if (!((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') ||
          (c >= '0' && c <= '9') || (c == '_'))) {
      *cursor = '_';
    }
    cursor++;
  }
}
 
CodePtr TypeTestingStubGenerator::DefaultCodeForType(
    const AbstractType& type,
    bool lazy_specialize /* = true */) {
  // During bootstrapping we have no access to stubs yet, so we'll just return
  // `null` and patch these later in `Object::FinishInit()`.
  if (!StubCode::HasBeenInitialized()) {
    ASSERT(type.IsType());
    const classid_t cid = type.type_class_id();
    ASSERT(cid == kDynamicCid || cid == kVoidCid);
    return Code::null();
  }
 
  if (type.IsTopTypeForSubtyping()) {
    return StubCode::TopTypeTypeTest().ptr();
  }
  if (type.IsTypeParameter()) {
    const bool nullable = Instance::NullIsAssignableTo(type);
    if (nullable) {
      return StubCode::NullableTypeParameterTypeTest().ptr();
    } else {
      return StubCode::TypeParameterTypeTest().ptr();
    }
  }
 
  if (type.IsFunctionType()) {
    const bool nullable = Instance::NullIsAssignableTo(type);
    return nullable ? StubCode::DefaultNullableTypeTest().ptr()
                    : StubCode::DefaultTypeTest().ptr();
  }
 
  if (type.IsType() || type.IsRecordType()) {
    const bool should_specialize = !FLAG_precompiled_mode && lazy_specialize;
    const bool nullable = Instance::NullIsAssignableTo(type);
    if (should_specialize) {
      return nullable ? StubCode::LazySpecializeNullableTypeTest().ptr()
                      : StubCode::LazySpecializeTypeTest().ptr();
    } else {
      return nullable ? StubCode::DefaultNullableTypeTest().ptr()
                      : StubCode::DefaultTypeTest().ptr();
    }
  }
 
  return StubCode::UnreachableTypeTest().ptr();
}
 
#if !defined(DART_PRECOMPILED_RUNTIME)
CodePtr TypeTestingStubGenerator::SpecializeStubFor(Thread* thread,
                                                    const AbstractType& type) {
  HierarchyInfo hi(thread);
  TypeTestingStubGenerator generator;
  return generator.OptimizedCodeForType(type);
}
#endif
 
TypeTestingStubGenerator::TypeTestingStubGenerator()
    : object_store_(IsolateGroup::Current()->object_store()) {}
 
CodePtr TypeTestingStubGenerator::OptimizedCodeForType(
    const AbstractType& type) {
#if !defined(TARGET_ARCH_IA32)
  ASSERT(StubCode::HasBeenInitialized());
 
  if (type.IsTypeParameter()) {
    return TypeTestingStubGenerator::DefaultCodeForType(
        type, /*lazy_specialize=*/false);
  }
 
  if (type.IsTopTypeForSubtyping()) {
    return StubCode::TopTypeTypeTest().ptr();
  }
 
  if (type.IsCanonical()) {
    // When adding any new types that can have specialized TTSes, also update
    // CollectTypes::VisitObject appropriately.
    if (type.IsType() || type.IsRecordType()) {
#if !defined(DART_PRECOMPILED_RUNTIME)
      const Code& code =
          Code::Handle(TypeTestingStubGenerator::BuildCodeForType(type));
      if (!code.IsNull()) {
        return code.ptr();
      }
      const Error& error = Error::Handle(Thread::Current()->StealStickyError());
      if (!error.IsNull()) {
        if (error.ptr() == Object::out_of_memory_error().ptr()) {
          Exceptions::ThrowOOM();
        } else {
          UNREACHABLE();
        }
      }
 
      // Fall back to default.
#else
      // In the precompiled runtime we cannot lazily create new optimized type
      // testing stubs, so if we cannot find one, we'll just return the default
      // one.
#endif  // !defined(DART_PRECOMPILED_RUNTIME)
    }
  }
#endif  // !defined(TARGET_ARCH_IA32)
  return TypeTestingStubGenerator::DefaultCodeForType(
      type, /*lazy_specialize=*/false);
}
 
#if !defined(TARGET_ARCH_IA32)
#if !defined(DART_PRECOMPILED_RUNTIME)
 
static CodePtr RetryCompilationWithFarBranches(
    Thread* thread,
    std::function<CodePtr(compiler::Assembler&)> fun) {
  volatile intptr_t far_branch_level = 0;
  while (true) {
    LongJumpScope jump;
    if (setjmp(*jump.Set()) == 0) {
      // To use the already-defined __ Macro !
      compiler::Assembler assembler(nullptr, far_branch_level);
      return fun(assembler);
    } else {
      // We bailed out or we encountered an error.
      const Error& error = Error::Handle(thread->StealStickyError());
      if (error.ptr() == Object::branch_offset_error().ptr()) {
        ASSERT(far_branch_level < 2);
        far_branch_level++;
      } else if (error.ptr() == Object::out_of_memory_error().ptr()) {
        thread->set_sticky_error(error);
        return Code::null();
      } else {
        UNREACHABLE();
      }
    }
  }
}
 
CodePtr TypeTestingStubGenerator::BuildCodeForType(const AbstractType& type) {
  auto thread = Thread::Current();
  auto zone = thread->zone();
  HierarchyInfo* hi = thread->hierarchy_info();
  ASSERT(hi != nullptr);
 
  if (!hi->CanUseSubtypeRangeCheckFor(type) &&
      !hi->CanUseGenericSubtypeRangeCheckFor(type) &&
      !hi->CanUseRecordSubtypeRangeCheckFor(type)) {
    return Code::null();
  }
 
  auto& slow_tts_stub = Code::ZoneHandle(zone);
  if (FLAG_precompiled_mode) {
    slow_tts_stub = thread->isolate_group()->object_store()->slow_tts_stub();
  }
 
  CompilerState compiler_state(thread, /*is_aot=*/FLAG_precompiled_mode,
                               /*is_optimizing=*/false);
 
  const Code& code = Code::Handle(
      thread->zone(),
      RetryCompilationWithFarBranches(
          thread, [&](compiler::Assembler& assembler) {
            compiler::UnresolvedPcRelativeCalls unresolved_calls;
            BuildOptimizedTypeTestStub(&assembler, &unresolved_calls,
                                       slow_tts_stub, hi, type);
 
            const auto& static_calls_table = Array::Handle(
                zone, compiler::StubCodeCompiler::BuildStaticCallsTable(
                          zone, &unresolved_calls));
 
            const char* name = namer_.StubNameForType(type);
            const auto pool_attachment =
                FLAG_precompiled_mode ? Code::PoolAttachment::kNotAttachPool
                                      : Code::PoolAttachment::kAttachPool;
 
            Code& code = Code::Handle(thread->zone());
            auto install_code_fun = [&]() {
              code = Code::FinalizeCode(nullptr, &assembler, pool_attachment,
                                        /*optimized=*/false, /*stats=*/nullptr);
              if (!static_calls_table.IsNull()) {
                code.set_static_calls_target_table(static_calls_table);
              }
            };
 
            // We have to ensure no mutators are running, because:
            //
            //   a) We allocate an instructions object, which might cause us to
            //      temporarily flip page protections from (RX -> RW -> RX).
            //
            SafepointWriteRwLocker ml(thread,
                                      thread->isolate_group()->program_lock());
            thread->isolate_group()->RunWithStoppedMutators(
                install_code_fun,
                /*use_force_growth=*/true);
 
            Code::NotifyCodeObservers(name, code, /*optimized=*/false);
 
            code.set_owner(type);
#ifndef PRODUCT
            if (FLAG_support_disassembler && FLAG_disassemble_stubs) {
              LogBlock lb;
              THR_Print("Code for stub '%s' (type = %s): {\n", name,
                        type.ToCString());
              DisassembleToStdout formatter;
              code.Disassemble(&formatter);
              THR_Print("}\n");
              const ObjectPool& object_pool =
                  ObjectPool::Handle(code.object_pool());
              if (!object_pool.IsNull()) {
                object_pool.DebugPrint();
              }
            }
#endif  // !PRODUCT
            return code.ptr();
          }));
 
  return code.ptr();
}
 
void TypeTestingStubGenerator::BuildOptimizedTypeTestStub(
    compiler::Assembler* assembler,
    compiler::UnresolvedPcRelativeCalls* unresolved_calls,
    const Code& slow_type_test_stub,
    HierarchyInfo* hi,
    const AbstractType& type) {
  BuildOptimizedTypeTestStubFastCases(assembler, hi, type);
  __ Jump(compiler::Address(
      THR, compiler::target::Thread::slow_type_test_entry_point_offset()));
}
 
void TypeTestingStubGenerator::BuildOptimizedTypeTestStubFastCases(
    compiler::Assembler* assembler,
    HierarchyInfo* hi,
    const AbstractType& type) {
  // These are handled via the TopTypeTypeTestStub!
  ASSERT(!type.IsTopTypeForSubtyping());
 
  if (type.IsObjectType()) {
    ASSERT(type.IsNonNullable());
    compiler::Label is_null;
    __ CompareObject(TypeTestABI::kInstanceReg, Object::null_object());
    __ BranchIf(EQUAL, &is_null, compiler::Assembler::kNearJump);
    __ Ret();
    __ Bind(&is_null);
    return;  // No further checks needed.
  }
 
  // Fast case for 'int' and '_Smi' (which can appear in core libraries).
  if (type.IsIntType() || type.IsSmiType()) {
    compiler::Label non_smi_value;
    __ BranchIfNotSmi(TypeTestABI::kInstanceReg, &non_smi_value,
                      compiler::Assembler::kNearJump);
    __ Ret();
    __ Bind(&non_smi_value);
  } else {
    // TODO(kustermann): Make more fast cases, e.g. Type::Number()
    // is implemented by Smi.
  }
 
  // Check the cid ranges which are a subtype of [type].
  if (hi->CanUseSubtypeRangeCheckFor(type)) {
    const Class& type_class = Class::Handle(type.type_class());
    ASSERT(!type_class.IsNull());
    const CidRangeVector& ranges = hi->SubtypeRangesForClass(
        type_class,
        /*include_abstract=*/false,
        /*exclude_null=*/!Instance::NullIsAssignableTo(type));
 
    compiler::Label is_subtype, is_not_subtype;
    const bool smi_is_ok =
        Type::Handle(Type::SmiType()).IsSubtypeOf(type, Heap::kNew);
    if (smi_is_ok) {
      __ LoadClassIdMayBeSmi(TTSInternalRegs::kScratchReg,
                             TypeTestABI::kInstanceReg);
    } else {
      __ BranchIfSmi(TypeTestABI::kInstanceReg, &is_not_subtype);
      __ LoadClassId(TTSInternalRegs::kScratchReg, TypeTestABI::kInstanceReg);
    }
    BuildOptimizedSubtypeRangeCheck(assembler, ranges,
                                    TTSInternalRegs::kScratchReg, &is_subtype,
                                    &is_not_subtype);
    __ Bind(&is_subtype);
    __ Ret();
    __ Bind(&is_not_subtype);
  } else if (hi->CanUseGenericSubtypeRangeCheckFor(type)) {
    const Class& type_class = Class::Handle(type.type_class());
    ASSERT(!type_class.IsNull());
    BuildOptimizedSubclassRangeCheckWithTypeArguments(
        assembler, hi, Type::Cast(type), type_class);
  } else if (hi->CanUseRecordSubtypeRangeCheckFor(type)) {
    BuildOptimizedRecordSubtypeRangeCheck(assembler, hi,
                                          RecordType::Cast(type));
  } else {
    UNREACHABLE();
  }
 
  if (Instance::NullIsAssignableTo(type)) {
    // Fast case for 'null'.
    compiler::Label non_null;
    __ CompareObject(TypeTestABI::kInstanceReg, Object::null_object());
    __ BranchIf(NOT_EQUAL, &non_null, compiler::Assembler::kNearJump);
    __ Ret();
    __ Bind(&non_null);
  }
}
 
static void CommentCheckedClasses(compiler::Assembler* assembler,
                                  const CidRangeVector& ranges) {
  if (!assembler->EmittingComments()) return;
  Thread* const thread = Thread::Current();
  ClassTable* const class_table = thread->isolate_group()->class_table();
  Zone* const zone = thread->zone();
  if (ranges.is_empty()) {
    __ Comment("No valid cids to check");
    return;
  }
  if ((ranges.length() == 1) && ranges[0].IsSingleCid()) {
    const auto& cls = Class::Handle(zone, class_table->At(ranges[0].cid_start));
    __ Comment("Checking for cid %" Pd " (%s)", cls.id(),
               cls.ScrubbedNameCString());
    return;
  }
  __ Comment("Checking for concrete finalized classes:");
  auto& cls = Class::Handle(zone);
  for (const auto& range : ranges) {
    ASSERT(!range.IsIllegalRange());
    for (classid_t cid = range.cid_start; cid <= range.cid_end; cid++) {
      // Invalid entries can be included to keep range count low.
      if (!class_table->HasValidClassAt(cid)) continue;
      cls = class_table->At(cid);
      if (cls.is_abstract()) continue;  // Only output concrete classes.
      __ Comment(" * %" Pd32 " (%s)", cid, cls.ScrubbedNameCString());
    }
  }
}
 
// Represents the following needs for runtime checks to see if an instance of
// [cls] is a subtype of [type] that has type class [type_class]:
//
// * kCannotBeChecked: Instances of [cls] cannot be checked with any of the
//   currently implemented runtime checks, so must fall back on the runtime.
//
// * kNotSubtype: A [cls] instance is guaranteed to not be a subtype of [type]
//   regardless of any instance type arguments.
//
// * kCidCheckOnly: A [cls] instance is guaranteed to be a subtype of [type]
//   regardless of any instance type arguments.
//
// * kNeedsFinalization: Checking that an instance of [cls] is a subtype of
//   [type] requires instance type arguments, but [cls] is not finalized, and
//   so the appropriate type arguments field offset cannot be determined.
//
// * kInstanceTypeArgumentsAreSubtypes: [cls] implements a fully uninstantiated
//   type with type class [type_class] which can be directly instantiated with
//   the instance type arguments. Thus, each type argument of [type] should be
//   compared with the corresponding (index-wise) instance type argument.
enum class CheckType {
  kCannotBeChecked,
  kNotSubtype,
  kCidCheckOnly,
  kNeedsFinalization,
  kInstanceTypeArgumentsAreSubtypes,
};
 
// Returns a CheckType describing how to check instances of [to_check] as
// subtypes of [type].
static CheckType SubtypeChecksForClass(Zone* zone,
                                       const Type& type,
                                       const Class& type_class,
                                       const Class& to_check) {
  ASSERT_EQUAL(type.type_class_id(), type_class.id());
  ASSERT(type_class.is_type_finalized());
  ASSERT(!to_check.is_abstract());
  ASSERT(to_check.is_type_finalized());
  ASSERT(AbstractType::Handle(zone, to_check.RareType())
             .IsSubtypeOf(AbstractType::Handle(zone, type_class.RareType()),
                          Heap::kNew));
  if (!type_class.IsGeneric()) {
    // All instances of [to_check] are subtypes of [type].
    return CheckType::kCidCheckOnly;
  }
  if (to_check.FindInstantiationOf(zone, type_class,
                                   /*only_super_classes=*/true)) {
    // No need to check for type argument consistency, as [to_check] is the same
    // as or a subclass of [type_class].
    return to_check.is_finalized()
               ? CheckType::kInstanceTypeArgumentsAreSubtypes
               : CheckType::kCannotBeChecked;
  }
  auto& calculated_type =
      Type::Handle(zone, to_check.GetInstantiationOf(zone, type_class));
  if (calculated_type.IsInstantiated()) {
    if (type.IsInstantiated()) {
      return calculated_type.IsSubtypeOf(type, Heap::kNew)
                 ? CheckType::kCidCheckOnly
                 : CheckType::kNotSubtype;
    }
    // TODO(dartbug.com/46920): Requires walking both types, checking
    // corresponding instantiated parts at compile time (assuming uninstantiated
    // parts check successfully) and then creating appropriate runtime checks
    // for uninstantiated parts of [type].
    return CheckType::kCannotBeChecked;
  }
  if (!to_check.is_finalized()) {
    return CheckType::kNeedsFinalization;
  }
  ASSERT(to_check.NumTypeArguments() > 0);
  ASSERT(compiler::target::Class::TypeArgumentsFieldOffset(to_check) !=
         compiler::target::Class::kNoTypeArguments);
  // If the calculated type arguments are a prefix of the declaration type
  // arguments, then we can just treat the instance type arguments as if they
  // were used to instantiate the type class during checking.
  const auto& decl_type_args = TypeArguments::Handle(
      zone, to_check.GetDeclarationInstanceTypeArguments());
  const auto& calculated_type_args = TypeArguments::Handle(
      zone, calculated_type.GetInstanceTypeArguments(Thread::Current(),
                                                     /*canonicalize=*/false));
  const bool type_args_consistent = calculated_type_args.IsSubvectorEquivalent(
      decl_type_args, 0, type_class.NumTypeArguments(),
      TypeEquality::kCanonical);
  // TODO(dartbug.com/46920): Currently we require subtyping to be checkable
  // by comparing the instance type arguments against the type arguments of
  // [type] piecewise, but we could check other cases as well.
  return type_args_consistent ? CheckType::kInstanceTypeArgumentsAreSubtypes
                              : CheckType::kCannotBeChecked;
}
 
static void CommentSkippedClasses(compiler::Assembler* assembler,
                                  const Type& type,
                                  const Class& type_class,
                                  const CidRangeVector& ranges) {
  if (!assembler->EmittingComments() || ranges.is_empty()) return;
  if (ranges.is_empty()) return;
  ASSERT(type_class.is_implemented());
  __ Comment("Not checking the following concrete implementors of %s:",
             type_class.ScrubbedNameCString());
  Thread* const thread = Thread::Current();
  auto* const class_table = thread->isolate_group()->class_table();
  Zone* const zone = thread->zone();
  auto& cls = Class::Handle(zone);
  auto& calculated_type = Type::Handle(zone);
  for (const auto& range : ranges) {
    ASSERT(!range.IsIllegalRange());
    for (classid_t cid = range.cid_start; cid <= range.cid_end; cid++) {
      // Invalid entries can be included to keep range count low.
      if (!class_table->HasValidClassAt(cid)) continue;
      cls = class_table->At(cid);
      if (cls.is_abstract()) continue;  // Only output concrete classes.
      ASSERT(cls.is_type_finalized());
      TextBuffer buffer(128);
      buffer.Printf(" * %" Pd32 "(%s): ", cid, cls.ScrubbedNameCString());
      switch (SubtypeChecksForClass(zone, type, type_class, cls)) {
        case CheckType::kCannotBeChecked:
          calculated_type = cls.GetInstantiationOf(zone, type_class);
          buffer.AddString("cannot check that ");
          calculated_type.PrintName(Object::kScrubbedName, &buffer);
          buffer.AddString(" is a subtype of ");
          type.PrintName(Object::kScrubbedName, &buffer);
          break;
        case CheckType::kNotSubtype:
          calculated_type = cls.GetInstantiationOf(zone, type_class);
          calculated_type.PrintName(Object::kScrubbedName, &buffer);
          buffer.AddString(" is not a subtype of ");
          type.PrintName(Object::kScrubbedName, &buffer);
          break;
        case CheckType::kNeedsFinalization:
          buffer.AddString("is not finalized");
          break;
        case CheckType::kInstanceTypeArgumentsAreSubtypes:
          buffer.AddString("was not finalized during class splitting");
          break;
        default:
          // Either the CheckType was kCidCheckOnly, which should never happen
          // since it only requires type finalization, or a new CheckType has
          // been added.
          UNREACHABLE();
          break;
      }
      __ Comment("%s", buffer.buffer());
    }
  }
}
 
// Builds a cid range check for the concrete subclasses and implementors of
// type. Falls through or jumps to check_succeeded if the range contains the
// cid, else jumps to check_failed.
//
// Returns whether class_id_reg is clobbered.
bool TypeTestingStubGenerator::BuildOptimizedSubtypeRangeCheck(
    compiler::Assembler* assembler,
    const CidRangeVector& ranges,
    Register class_id_reg,
    compiler::Label* check_succeeded,
    compiler::Label* check_failed) {
  CommentCheckedClasses(assembler, ranges);
  return FlowGraphCompiler::GenerateCidRangesCheck(
      assembler, class_id_reg, ranges, check_succeeded, check_failed, true);
}
 
void TypeTestingStubGenerator::
    BuildOptimizedSubclassRangeCheckWithTypeArguments(
        compiler::Assembler* assembler,
        HierarchyInfo* hi,
        const Type& type,
        const Class& type_class) {
  ASSERT(hi->CanUseGenericSubtypeRangeCheckFor(type));
  compiler::Label check_failed, load_succeeded;
  // a) First we perform subtype cid-range checks and load the instance type
  // arguments based on which check succeeded.
  if (BuildLoadInstanceTypeArguments(assembler, hi, type, type_class,
                                     TTSInternalRegs::kScratchReg,
                                     TTSInternalRegs::kInstanceTypeArgumentsReg,
                                     &load_succeeded, &check_failed)) {
    // Only build type argument checking if any checked cid ranges require it.
    __ Bind(&load_succeeded);
 
    // The rare type of the class is guaranteed to be a supertype of the
    // runtime type of any instance..
    const Type& rare_type = Type::Handle(type_class.RareType());
    // If the rare type is a subtype of the type being checked, then the runtime
    // type of the instance is also a subtype and we shouldn't need to perform
    // checks for the instance type arguments.
    ASSERT(!rare_type.IsSubtypeOf(type, Heap::kNew));
    // b) We check if the type arguments of the rare type are all dynamic
    // (that is, the type arguments vector is null).
    if (rare_type.arguments() == TypeArguments::null()) {
      // If it is, then the instance could have a null instance TAV. However,
      // if the instance TAV is null, then the runtime type of the instance is
      // the rare type, which means it cannot be a subtype of the checked type.
      __ CompareObject(TTSInternalRegs::kInstanceTypeArgumentsReg,
                       Object::null_object());
      __ BranchIf(EQUAL, &check_failed);
    } else {
      // If the TAV of the rare type is not null, at least one type argument
      // of the rare type is a non-top type. This means no instance can have
      // a null instance TAV, as the dynamic type cannot be a subtype of
      // a non-top type and each type argument of an instance must be
      // a subtype of the corresponding type argument for the rare type.
#if defined(DEBUG)
      // Add the check for null in DEBUG mode, but instead of failing, create a
      // breakpoint to make it obvious that the assumption above has failed.
      __ CompareObject(TTSInternalRegs::kInstanceTypeArgumentsReg,
                       Object::null_object());
      compiler::Label check_instance_tav;
      __ BranchIf(NOT_EQUAL, &check_instance_tav,
                  compiler::Assembler::kNearJump);
      __ Breakpoint();
      __ Bind(&check_instance_tav);
#endif
    }
 
    // c) Then we'll check each value of the type argument.
    compiler::Label pop_saved_registers_on_failure;
    const RegisterSet saved_registers(
        TTSInternalRegs::kSavedTypeArgumentRegisters, /*fpu_registers=*/0);
    __ PushRegisters(saved_registers);
 
    AbstractType& type_arg = AbstractType::Handle();
    const TypeArguments& ta = TypeArguments::Handle(type.arguments());
    const intptr_t num_type_parameters = type_class.NumTypeParameters();
    const intptr_t num_type_arguments = type_class.NumTypeArguments();
    ASSERT(ta.Length() == num_type_parameters);
    for (intptr_t i = 0; i < num_type_parameters; ++i) {
      const intptr_t type_param_value_offset_i =
          num_type_arguments - num_type_parameters + i;
 
      type_arg = ta.TypeAt(i);
      ASSERT(type_arg.IsTypeParameter() ||
             hi->CanUseSubtypeRangeCheckFor(type_arg));
 
      if (type_arg.IsTypeParameter()) {
        BuildOptimizedTypeParameterArgumentValueCheck(
            assembler, hi, TypeParameter::Cast(type_arg),
            type_param_value_offset_i, &pop_saved_registers_on_failure);
      } else {
        BuildOptimizedTypeArgumentValueCheck(
            assembler, hi, Type::Cast(type_arg), type_param_value_offset_i,
            &pop_saved_registers_on_failure);
      }
    }
    __ PopRegisters(saved_registers);
    __ Ret();
    __ Bind(&pop_saved_registers_on_failure);
    __ PopRegisters(saved_registers);
  }
 
  // If anything fails.
  __ Bind(&check_failed);
}
 
void TypeTestingStubGenerator::BuildOptimizedRecordSubtypeRangeCheck(
    compiler::Assembler* assembler,
    HierarchyInfo* hi,
    const RecordType& type) {
  compiler::Label is_subtype, is_not_subtype;
  Zone* zone = Thread::Current()->zone();
 
  __ BranchIfSmi(TypeTestABI::kInstanceReg, &is_not_subtype);
  __ LoadClassId(TTSInternalRegs::kScratchReg, TypeTestABI::kInstanceReg);
 
  if (Instance::NullIsAssignableTo(type)) {
    __ CompareImmediate(TTSInternalRegs::kScratchReg, kNullCid);
    __ BranchIf(EQUAL, &is_subtype);
  }
  __ CompareImmediate(TTSInternalRegs::kScratchReg, kRecordCid);
  __ BranchIf(NOT_EQUAL, &is_not_subtype);
 
  __ LoadCompressedSmi(
      TTSInternalRegs::kScratchReg,
      compiler::FieldAddress(TypeTestABI::kInstanceReg,
                             compiler::target::Record::shape_offset()));
  __ CompareImmediate(TTSInternalRegs::kScratchReg,
                      Smi::RawValue(type.shape().AsInt()));
  __ BranchIf(NOT_EQUAL, &is_not_subtype);
 
  auto& field_type = AbstractType::Handle(zone);
  auto& field_type_class = Class::Handle(zone);
  const auto& smi_type = Type::Handle(zone, Type::SmiType());
  for (intptr_t i = 0, n = type.NumFields(); i < n; ++i) {
    compiler::Label next;
 
    field_type = type.FieldTypeAt(i);
    ASSERT(hi->CanUseSubtypeRangeCheckFor(field_type));
 
    __ LoadCompressedFieldFromOffset(TTSInternalRegs::kScratchReg,
                                     TypeTestABI::kInstanceReg,
                                     compiler::target::Record::field_offset(i));
 
    field_type_class = field_type.type_class();
    ASSERT(!field_type_class.IsNull());
 
    const CidRangeVector& ranges = hi->SubtypeRangesForClass(
        field_type_class,
        /*include_abstract=*/false,
        /*exclude_null=*/!Instance::NullIsAssignableTo(field_type));
 
    const bool smi_is_ok = smi_type.IsSubtypeOf(field_type, Heap::kNew);
    __ BranchIfSmi(TTSInternalRegs::kScratchReg,
                   smi_is_ok ? &next : &is_not_subtype);
    __ LoadClassId(TTSInternalRegs::kScratchReg, TTSInternalRegs::kScratchReg);
 
    BuildOptimizedSubtypeRangeCheck(assembler, ranges,
                                    TTSInternalRegs::kScratchReg, &next,
                                    &is_not_subtype);
    __ Bind(&next);
  }
 
  __ Bind(&is_subtype);
  __ Ret();
  __ Bind(&is_not_subtype);
}
 
// Splits [ranges] into multiple ranges in [output], where the concrete,
// finalized classes in each range share the same type arguments field offset.
//
// The first range in [output] contains [type_class], if any do, and otherwise
// prioritizes ranges that include predefined cids before ranges that only
// contain user-defined classes.
//
// Any cids that do not have valid class table entries, correspond to abstract
// or unfinalized classes, or have no TAV field offset are treated as don't
// cares, in that the cid may appear in any of the CidRangeVectors as needed to
// reduce the number of ranges.
//
// Note that CidRangeVectors are MallocGrowableArrays, so the elements in
// output must be freed after use!
static void SplitByTypeArgumentsFieldOffset(
    Thread* T,
    const Class& type_class,
    const CidRangeVector& ranges,
    GrowableArray<CidRangeVector*>* output) {
  ASSERT(output != nullptr);
  ASSERT(!ranges.is_empty());
 
  Zone* const Z = T->zone();
  ClassTable* const class_table = T->isolate_group()->class_table();
  IntMap<CidRangeVector*> offset_map(Z);
  IntMap<intptr_t> predefined_offsets(Z);
  IntMap<intptr_t> user_defined_offsets(Z);
 
  auto add_to_vector = [&](intptr_t tav_offset, const CidRange& range) {
    if (range.cid_start == -1) return;
    ASSERT(tav_offset != compiler::target::Class::kNoTypeArguments);
    if (CidRangeVector* vector = offset_map.Lookup(tav_offset)) {
      vector->Add(range);
    } else {
      vector = new CidRangeVector(1);
      vector->Add(range);
      offset_map.Insert(tav_offset, vector);
    }
  };
 
  auto increment_count = [&](intptr_t cid, intptr_t tav_offset) {
    if (cid <= kNumPredefinedCids) {
      predefined_offsets.Update(
          {tav_offset, predefined_offsets.Lookup(tav_offset) + 1});
    } else if (auto* const kv = predefined_offsets.LookupPair(tav_offset)) {
      predefined_offsets.Update({kv->key, kv->value + 1});
    } else {
      user_defined_offsets.Update(
          {tav_offset, user_defined_offsets.Lookup(tav_offset) + 1});
    }
  };
 
  // First populate offset_map.
  auto& cls = Class::Handle(Z);
  for (const auto& range : ranges) {
    intptr_t last_offset = compiler::target::Class::kNoTypeArguments;
    intptr_t cid_start = -1;
    intptr_t cid_end = -1;
    for (intptr_t cid = range.cid_start; cid <= range.cid_end; cid++) {
      if (!class_table->HasValidClassAt(cid)) continue;
      cls = class_table->At(cid);
      if (cls.is_abstract()) continue;
      // Only finalized concrete classes are present due to the conditions on
      // returning kInstanceTypeArgumentsAreSubtypes in SubtypeChecksForClass.
      ASSERT(cls.is_finalized());
      const intptr_t tav_offset =
          compiler::target::Class::TypeArgumentsFieldOffset(cls);
      if (tav_offset == compiler::target::Class::kNoTypeArguments) continue;
      if (tav_offset == last_offset && cid_start >= 0) {
        cid_end = cid;
        increment_count(cid, tav_offset);
        continue;
      }
      add_to_vector(last_offset, {cid_start, cid_end});
      last_offset = tav_offset;
      cid_start = cid_end = cid;
      increment_count(cid, tav_offset);
    }
    add_to_vector(last_offset, {cid_start, cid_end});
  }
 
  ASSERT(!offset_map.IsEmpty());
 
  // Add the CidRangeVector for the type_class's offset, if it has one.
  if (!type_class.is_abstract() && type_class.is_finalized()) {
    const intptr_t type_class_offset =
        compiler::target::Class::TypeArgumentsFieldOffset(type_class);
    ASSERT(predefined_offsets.LookupPair(type_class_offset) != nullptr ||
           user_defined_offsets.LookupPair(type_class_offset) != nullptr);
    CidRangeVector* const vector = offset_map.Lookup(type_class_offset);
    ASSERT(vector != nullptr);
    output->Add(vector);
    // Remove this CidRangeVector from consideration in the following loops.
    predefined_offsets.Remove(type_class_offset);
    user_defined_offsets.Remove(type_class_offset);
  }
  // Now add CidRangeVectors that include predefined cids.
  // For now, we do this in an arbitrary order, but we could use the counts
  // to prioritize offsets that are more shared if desired.
  auto predefined_it = predefined_offsets.GetIterator();
  while (auto* const kv = predefined_it.Next()) {
    CidRangeVector* const vector = offset_map.Lookup(kv->key);
    ASSERT(vector != nullptr);
    output->Add(vector);
  }
  // Finally, add CidRangeVectors that only include user-defined cids.
  // For now, we do this in an arbitrary order, but we could use the counts
  // to prioritize offsets that are more shared if desired.
  auto user_defined_it = user_defined_offsets.GetIterator();
  while (auto* const kv = user_defined_it.Next()) {
    CidRangeVector* const vector = offset_map.Lookup(kv->key);
    ASSERT(vector != nullptr);
    output->Add(vector);
  }
  ASSERT(output->length() > 0);
}
 
// Given [type], its type class [type_class], and a CidRangeVector [ranges],
// populates the output CidRangeVectors from cids in [ranges], based on what
// runtime checks are needed to determine whether the runtime type of
// an instance is a subtype of [type].
//
// Concrete, type finalized classes whose cids are added to [cid_check_only]
// implement a particular instantiation of [type_class] that is guaranteed to
// be a subtype of [type]. Thus, these instances do not require any checking
// of type arguments.
//
// Concrete, finalized classes whose cids are added to [type_argument_checks]
// implement a fully uninstantiated version of [type_class] that can be directly
// instantiated with the type arguments of the class's instance. Thus, each
// type argument of [type] should be checked against the corresponding
// instance type argument.
//
// Classes whose cids are in [not_checked]:
// * Instances of the class are guaranteed to not be a subtype of [type].
// * The class is not finalized.
// * The subtype relation cannot be checked with our current approach and
//   thus the stub must fall back to the STC/VM runtime.
//
// Any cids that do not have valid class table entries or correspond to
// abstract classes are treated as don't cares, in that the cid may or may not
// appear as needed to reduce the number of ranges.
static void SplitOnTypeArgumentTests(HierarchyInfo* hi,
                                     const Type& type,
                                     const Class& type_class,
                                     const CidRangeVector& ranges,
                                     CidRangeVector* cid_check_only,
                                     CidRangeVector* type_argument_checks,
                                     CidRangeVector* not_checked) {
  ASSERT(type_class.is_implemented());  // No need to split if not implemented.
  ASSERT(cid_check_only->is_empty());
  ASSERT(type_argument_checks->is_empty());
  ASSERT(not_checked->is_empty());
  ClassTable* const class_table = hi->thread()->isolate_group()->class_table();
  Zone* const zone = hi->thread()->zone();
  auto& to_check = Class::Handle(zone);
  auto add_cid_range = [&](CheckType check, const CidRange& range) {
    if (range.cid_start == -1) return;
    switch (check) {
      case CheckType::kCidCheckOnly:
        cid_check_only->Add(range);
        break;
      case CheckType::kInstanceTypeArgumentsAreSubtypes:
        type_argument_checks->Add(range);
        break;
      default:
        not_checked->Add(range);
    }
  };
  for (const auto& range : ranges) {
    CheckType last_check = CheckType::kCannotBeChecked;
    classid_t cid_start = -1, cid_end = -1;
    for (classid_t cid = range.cid_start; cid <= range.cid_end; cid++) {
      // Invalid entries can be included to keep range count low.
      if (!class_table->HasValidClassAt(cid)) continue;
      to_check = class_table->At(cid);
      if (to_check.is_abstract()) continue;
      const CheckType current_check =
          SubtypeChecksForClass(zone, type, type_class, to_check);
      ASSERT(current_check != CheckType::kInstanceTypeArgumentsAreSubtypes ||
             to_check.is_finalized());
      if (last_check == current_check && cid_start >= 0) {
        cid_end = cid;
        continue;
      }
      add_cid_range(last_check, {cid_start, cid_end});
      last_check = current_check;
      cid_start = cid_end = cid;
    }
    add_cid_range(last_check, {cid_start, cid_end});
  }
}
 
bool TypeTestingStubGenerator::BuildLoadInstanceTypeArguments(
    compiler::Assembler* assembler,
    HierarchyInfo* hi,
    const Type& type,
    const Class& type_class,
    const Register class_id_reg,
    const Register instance_type_args_reg,
    compiler::Label* load_succeeded,
    compiler::Label* load_failed) {
  const CidRangeVector& ranges =
      hi->SubtypeRangesForClass(type_class, /*include_abstract=*/false,
                                !Instance::NullIsAssignableTo(type));
  if (ranges.is_empty()) {
    // Fall through and signal type argument checks should not be generated.
    CommentCheckedClasses(assembler, ranges);
    return false;
  }
  if (!type_class.is_implemented()) {
    ASSERT(type_class.is_finalized());
    const intptr_t tav_offset =
        compiler::target::Class::TypeArgumentsFieldOffset(type_class);
    compiler::Label is_subtype;
    __ LoadClassIdMayBeSmi(class_id_reg, TypeTestABI::kInstanceReg);
    BuildOptimizedSubtypeRangeCheck(assembler, ranges, class_id_reg,
                                    &is_subtype, load_failed);
    __ Bind(&is_subtype);
    if (tav_offset != compiler::target::Class::kNoTypeArguments) {
      // The class and its subclasses have trivially consistent type arguments.
      __ LoadCompressedFieldFromOffset(instance_type_args_reg,
                                       TypeTestABI::kInstanceReg, tav_offset);
      return true;
    } else {
      // Not a generic type, so cid checks are sufficient.
      __ Ret();
      return false;
    }
  }
  Thread* const T = hi->thread();
  Zone* const Z = T->zone();
  CidRangeVector cid_checks_only, type_argument_checks, not_checked;
  SplitOnTypeArgumentTests(hi, type, type_class, ranges, &cid_checks_only,
                           &type_argument_checks, &not_checked);
  ASSERT(!CidRangeVectorUtils::ContainsCid(type_argument_checks, kSmiCid));
  const bool smi_valid =
      CidRangeVectorUtils::ContainsCid(cid_checks_only, kSmiCid);
  // If we'll generate any cid checks and Smi isn't a valid subtype, then
  // do a single Smi check here, since each generated check requires a fresh
  // load of the class id. Otherwise, we'll generate the Smi check as part of
  // the cid checks only block.
  if (!smi_valid &&
      (!cid_checks_only.is_empty() || !type_argument_checks.is_empty())) {
    __ BranchIfSmi(TypeTestABI::kInstanceReg, load_failed);
  }
  // Ensure that if the cid checks only block is skipped, the first iteration
  // of the type arguments check will generate a cid load.
  bool cid_needs_reload = true;
  if (!cid_checks_only.is_empty()) {
    compiler::Label is_subtype, keep_looking;
    compiler::Label* check_failed =
        type_argument_checks.is_empty() ? load_failed : &keep_looking;
    if (smi_valid) {
      __ LoadClassIdMayBeSmi(class_id_reg, TypeTestABI::kInstanceReg);
    } else {
      __ LoadClassId(class_id_reg, TypeTestABI::kInstanceReg);
    }
    cid_needs_reload = BuildOptimizedSubtypeRangeCheck(
        assembler, cid_checks_only, class_id_reg, &is_subtype, check_failed);
    __ Bind(&is_subtype);
    __ Ret();
    __ Bind(&keep_looking);
  }
  if (!type_argument_checks.is_empty()) {
    GrowableArray<CidRangeVector*> vectors;
    SplitByTypeArgumentsFieldOffset(T, type_class, type_argument_checks,
                                    &vectors);
    ASSERT(vectors.length() > 0);
    ClassTable* const class_table = T->isolate_group()->class_table();
    auto& cls = Class::Handle(Z);
    for (intptr_t i = 0; i < vectors.length(); i++) {
      CidRangeVector* const vector = vectors[i];
      ASSERT(!vector->is_empty());
      const intptr_t first_cid = vector->At(0).cid_start;
      ASSERT(class_table->HasValidClassAt(first_cid));
      cls = class_table->At(first_cid);
      ASSERT(cls.is_finalized());
      const intptr_t tav_offset =
          compiler::target::Class::TypeArgumentsFieldOffset(cls);
      compiler::Label load_tav, keep_looking;
      // For the last vector, just jump to load_failed if the check fails
      // and avoid emitting a jump to load_succeeded.
      compiler::Label* check_failed =
          i < vectors.length() - 1 ? &keep_looking : load_failed;
      if (cid_needs_reload) {
        __ LoadClassId(class_id_reg, TypeTestABI::kInstanceReg);
      }
      cid_needs_reload = BuildOptimizedSubtypeRangeCheck(
          assembler, *vector, class_id_reg, &load_tav, check_failed);
      __ Bind(&load_tav);
      __ LoadCompressedFieldFromOffset(instance_type_args_reg,
                                       TypeTestABI::kInstanceReg, tav_offset);
      if (i < vectors.length() - 1) {
        __ Jump(load_succeeded);
        __ Bind(&keep_looking);
      }
      // Free the CidRangeVector allocated by SplitByTypeArgumentsFieldOffset.
      delete vector;
    }
  }
  if (!not_checked.is_empty()) {
    CommentSkippedClasses(assembler, type, type_class, not_checked);
  }
  return !type_argument_checks.is_empty();
}
 
void TypeTestingStubGenerator::BuildOptimizedTypeParameterArgumentValueCheck(
    compiler::Assembler* assembler,
    HierarchyInfo* hi,
    const TypeParameter& type_param,
    intptr_t type_param_value_offset_i,
    compiler::Label* check_failed) {
  if (assembler->EmittingComments()) {
    TextBuffer buffer(128);
    buffer.Printf("Generating check for type argument %" Pd ": ",
                  type_param_value_offset_i);
    type_param.PrintName(Object::kScrubbedName, &buffer);
    __ Comment("%s", buffer.buffer());
  }
 
  const Register kTypeArgumentsReg =
      type_param.IsClassTypeParameter()
          ? TypeTestABI::kInstantiatorTypeArgumentsReg
          : TypeTestABI::kFunctionTypeArgumentsReg;
 
  compiler::Label is_subtype;
  // TODO(dartbug.com/46920): Currently only canonical equality (identity)
  // and some top and bottom types are checked.
  __ CompareObject(kTypeArgumentsReg, Object::null_object());
  __ BranchIf(EQUAL, &is_subtype);
 
  __ LoadCompressedFieldFromOffset(
      TTSInternalRegs::kSuperTypeArgumentReg, kTypeArgumentsReg,
      compiler::target::TypeArguments::type_at_offset(type_param.index()));
  __ LoadCompressedFieldFromOffset(
      TTSInternalRegs::kSubTypeArgumentReg,
      TTSInternalRegs::kInstanceTypeArgumentsReg,
      compiler::target::TypeArguments::type_at_offset(
          type_param_value_offset_i));
  __ CompareRegisters(TTSInternalRegs::kSuperTypeArgumentReg,
                      TTSInternalRegs::kSubTypeArgumentReg);
  __ BranchIf(EQUAL, &is_subtype);
 
  __ Comment("Checking instantiated type parameter for possible top types");
  compiler::Label check_subtype_type_class_ids;
  __ LoadClassId(TTSInternalRegs::kScratchReg,
                 TTSInternalRegs::kSuperTypeArgumentReg);
  __ CompareImmediate(TTSInternalRegs::kScratchReg, kTypeCid);
  __ BranchIf(NOT_EQUAL, &check_subtype_type_class_ids);
  __ LoadTypeClassId(TTSInternalRegs::kScratchReg,
                     TTSInternalRegs::kSuperTypeArgumentReg);
  __ CompareImmediate(TTSInternalRegs::kScratchReg, kDynamicCid);
  __ BranchIf(EQUAL, &is_subtype);
  __ CompareImmediate(TTSInternalRegs::kScratchReg, kVoidCid);
  __ BranchIf(EQUAL, &is_subtype);
  __ CompareImmediate(TTSInternalRegs::kScratchReg, kInstanceCid);
  __ BranchIf(NOT_EQUAL, &check_subtype_type_class_ids);
  // If non-nullable Object, then the subtype must be legacy or non-nullable.
  __ CompareAbstractTypeNullabilityWith(
      TTSInternalRegs::kSuperTypeArgumentReg,
      static_cast<int8_t>(Nullability::kNonNullable),
      TTSInternalRegs::kScratchReg);
  __ BranchIf(NOT_EQUAL, &is_subtype);
  __ Comment("Checking for legacy or non-nullable instance type argument");
  __ CompareAbstractTypeNullabilityWith(
      TTSInternalRegs::kSubTypeArgumentReg,
      static_cast<int8_t>(Nullability::kNullable),
      TTSInternalRegs::kScratchReg);
  __ BranchIf(EQUAL, check_failed);
  __ Jump(&is_subtype);
 
  __ Bind(&check_subtype_type_class_ids);
  __ Comment("Checking instance type argument for possible bottom types");
  // Nothing else to check for non-Types, so fall back to the slow stub.
  __ LoadClassId(TTSInternalRegs::kScratchReg,
                 TTSInternalRegs::kSubTypeArgumentReg);
  __ CompareImmediate(TTSInternalRegs::kScratchReg, kTypeCid);
  __ BranchIf(NOT_EQUAL, check_failed);
  __ LoadTypeClassId(TTSInternalRegs::kScratchReg,
                     TTSInternalRegs::kSubTypeArgumentReg);
  __ CompareImmediate(TTSInternalRegs::kScratchReg, kNeverCid);
  __ BranchIf(EQUAL, &is_subtype);
  __ CompareImmediate(TTSInternalRegs::kScratchReg, kNullCid);
  // Last possible check, so fall back to slow stub on failure.
  __ BranchIf(NOT_EQUAL, check_failed);
  // Only nullable or legacy types can be a supertype of Null.
  __ Comment("Checking for legacy or nullable instantiated type parameter");
  __ CompareAbstractTypeNullabilityWith(
      TTSInternalRegs::kSuperTypeArgumentReg,
      static_cast<int8_t>(Nullability::kNonNullable),
      TTSInternalRegs::kScratchReg);
  __ BranchIf(EQUAL, check_failed);
 
  __ Bind(&is_subtype);
}
 
// Generate code to verify that instance's type argument is a subtype of
// 'type_arg'.
void TypeTestingStubGenerator::BuildOptimizedTypeArgumentValueCheck(
    compiler::Assembler* assembler,
    HierarchyInfo* hi,
    const Type& type,
    intptr_t type_param_value_offset_i,
    compiler::Label* check_failed) {
  ASSERT(type.IsInstantiated());
  if (type.IsTopTypeForSubtyping()) {
    return;
  }
 
  ASSERT(!type.IsObjectType() || type.IsNonNullable());
 
  if (assembler->EmittingComments()) {
    TextBuffer buffer(128);
    buffer.Printf("Generating check for type argument %" Pd ": ",
                  type_param_value_offset_i);
    type.PrintName(Object::kScrubbedName, &buffer);
    __ Comment("%s", buffer.buffer());
  }
 
  compiler::Label is_subtype, sub_is_type;
  __ LoadCompressedFieldFromOffset(
      TTSInternalRegs::kSubTypeArgumentReg,
      TTSInternalRegs::kInstanceTypeArgumentsReg,
      compiler::target::TypeArguments::type_at_offset(
          type_param_value_offset_i));
  __ LoadClassId(TTSInternalRegs::kScratchReg,
                 TTSInternalRegs::kSubTypeArgumentReg);
  if (type.IsObjectType() || type.IsDartFunctionType() ||
      type.IsDartRecordType()) {
    __ CompareImmediate(TTSInternalRegs::kScratchReg, kTypeCid);
    __ BranchIf(EQUAL, &sub_is_type);
    if (type.IsDartFunctionType()) {
      __ Comment("Checks for Function type");
      __ CompareImmediate(TTSInternalRegs::kScratchReg, kFunctionTypeCid);
      __ BranchIf(NOT_EQUAL, check_failed);
    } else if (type.IsDartRecordType()) {
      __ Comment("Checks for Record type");
      __ CompareImmediate(TTSInternalRegs::kScratchReg, kRecordTypeCid);
      __ BranchIf(NOT_EQUAL, check_failed);
    } else {
      __ Comment("Checks for Object type");
    }
    if (type.IsNonNullable()) {
      // Nullable types cannot be a subtype of a non-nullable type.
      __ CompareAbstractTypeNullabilityWith(
          TTSInternalRegs::kSubTypeArgumentReg,
          static_cast<int8_t>(Nullability::kNullable),
          TTSInternalRegs::kScratchReg);
      __ BranchIf(EQUAL, check_failed);
    }
    // No further checks needed for non-nullable Object, Function or Record.
    __ Jump(&is_subtype, compiler::Assembler::kNearJump);
  } else {
    // Don't fall back to cid tests for record and function types. Instead,
    // just let the STC/runtime handle any possible false negatives here.
    __ CompareImmediate(TTSInternalRegs::kScratchReg, kTypeCid);
    __ BranchIf(NOT_EQUAL, check_failed);
  }
 
  __ Comment("Checks for Type");
  __ Bind(&sub_is_type);
  if (type.IsNonNullable()) {
    // Nullable types cannot be a subtype of a non-nullable type in strict mode.
    __ CompareAbstractTypeNullabilityWith(
        TTSInternalRegs::kSubTypeArgumentReg,
        static_cast<int8_t>(Nullability::kNullable),
        TTSInternalRegs::kScratchReg);
    __ BranchIf(EQUAL, check_failed);
    // Fall through to bottom type checks.
  }
 
  // No further checks needed for non-nullable object.
  if (!type.IsObjectType()) {
    __ LoadTypeClassId(TTSInternalRegs::kScratchReg,
                       TTSInternalRegs::kSubTypeArgumentReg);
 
    const bool null_is_assignable = Instance::NullIsAssignableTo(type);
    // Check bottom types.
    __ CompareImmediate(TTSInternalRegs::kScratchReg, kNeverCid);
    __ BranchIf(EQUAL, &is_subtype);
    if (null_is_assignable) {
      __ CompareImmediate(TTSInternalRegs::kScratchReg, kNullCid);
      __ BranchIf(EQUAL, &is_subtype);
    }
 
    // Not a bottom type, so check cid ranges.
    const Class& type_class = Class::Handle(type.type_class());
    const CidRangeVector& ranges =
        hi->SubtypeRangesForClass(type_class,
                                  /*include_abstract=*/true,
                                  /*exclude_null=*/!null_is_assignable);
    BuildOptimizedSubtypeRangeCheck(assembler, ranges,
                                    TTSInternalRegs::kScratchReg, &is_subtype,
                                    check_failed);
  }
 
  __ Bind(&is_subtype);
}
 
void RegisterTypeArgumentsUse(const Function& function,
                              TypeUsageInfo* type_usage_info,
                              const Class& klass,
                              Definition* type_arguments) {
  // The [type_arguments] can, in the general case, be any kind of [Definition]
  // but generally (in order of expected frequency)
  //
  //   Case a)
  //      type_arguments <- Constant(#null)
  //      type_arguments <- Constant(#TypeArguments: [ ... ])
  //
  //   Case b)
  //      type_arguments <- InstantiateTypeArguments(ita, fta, uta)
  //      (where uta may not be a constant non-null TypeArguments object)
  //
  //   Case c)
  //      type_arguments <- LoadField(vx)
  //      type_arguments <- LoadField(vx T{_ABC})
  //      type_arguments <- LoadField(vx T{Type: class: '_ABC'})
  //
  //   Case d, e)
  //      type_arguments <- LoadIndexedUnsafe(rbp[vx + 16]))
  //      type_arguments <- Parameter(0)
 
  if (ConstantInstr* constant = type_arguments->AsConstant()) {
    const Object& object = constant->value();
    ASSERT(object.IsNull() || object.IsTypeArguments());
    const TypeArguments& type_arguments =
        TypeArguments::Handle(TypeArguments::RawCast(object.ptr()));
    type_usage_info->UseTypeArgumentsInInstanceCreation(klass, type_arguments);
  } else if (InstantiateTypeArgumentsInstr* instantiate =
                 type_arguments->AsInstantiateTypeArguments()) {
    if (instantiate->type_arguments()->BindsToConstant() &&
        !instantiate->type_arguments()->BoundConstant().IsNull()) {
      const auto& ta =
          TypeArguments::Cast(instantiate->type_arguments()->BoundConstant());
      type_usage_info->UseTypeArgumentsInInstanceCreation(klass, ta);
    }
  } else if (LoadFieldInstr* load_field = type_arguments->AsLoadField()) {
    Definition* instance = load_field->instance()->definition();
    intptr_t cid = instance->Type()->ToNullableCid();
    if (cid == kDynamicCid) {
      // This is an approximation: If we only know the type, but not the cid, we
      // might have a this-dispatch where we know it's either this class or any
      // subclass.
      // We try to strengthen this assumption further down by checking the
      // offset of the type argument vector, but generally speaking this could
      // be a false-positive, which is still ok!
      const AbstractType& type = *instance->Type()->ToAbstractType();
      if (type.IsType()) {
        const Class& type_class = Class::Handle(type.type_class());
        if (type_class.NumTypeArguments() >= klass.NumTypeArguments()) {
          cid = type_class.id();
        }
      }
    }
    if (cid != kDynamicCid) {
      const Class& instance_klass =
          Class::Handle(IsolateGroup::Current()->class_table()->At(cid));
      if (load_field->slot().IsTypeArguments() && instance_klass.IsGeneric() &&
          compiler::target::Class::TypeArgumentsFieldOffset(instance_klass) ==
              load_field->slot().offset_in_bytes()) {
        // This is a subset of Case c) above, namely forwarding the type
        // argument vector.
        //
        // We use the declaration type arguments for the instance creation,
        // which is a non-instantiated, expanded, type arguments vector.
        TypeArguments& declaration_type_args = TypeArguments::Handle(
            instance_klass.GetDeclarationInstanceTypeArguments());
        type_usage_info->UseTypeArgumentsInInstanceCreation(
            klass, declaration_type_args);
      }
    }
  } else if (type_arguments->IsParameter() ||
             type_arguments->IsLoadIndexedUnsafe()) {
    // This happens in constructors with non-optional/optional parameters
    // where we forward the type argument vector to object allocation.
    //
    // Theoretically this could be a false-positive, which is still ok, but
    // practically it's guaranteed that this is a forward of a type argument
    // vector passed in by the caller.
    if (function.IsFactory()) {
      const Class& enclosing_class = Class::Handle(function.Owner());
      TypeArguments& declaration_type_args = TypeArguments::Handle(
          enclosing_class.GetDeclarationInstanceTypeArguments());
      type_usage_info->UseTypeArgumentsInInstanceCreation(
          klass, declaration_type_args);
    }
  } else {
    // It can also be a phi node where the inputs are any of the above,
    // or it could be the result of _prependTypeArguments call.
    ASSERT(type_arguments->IsPhi() || type_arguments->IsStaticCall());
  }
}
 
#endif  // !defined(DART_PRECOMPILED_RUNTIME)
 
#else  // !defined(TARGET_ARCH_IA32)
 
#if !defined(DART_PRECOMPILED_RUNTIME)
void RegisterTypeArgumentsUse(const Function& function,
                              TypeUsageInfo* type_usage_info,
                              const Class& klass,
                              Definition* type_arguments) {
  // We only have a [TypeUsageInfo] object available durin AOT compilation.
  UNREACHABLE();
}
#endif  // !defined(DART_PRECOMPILED_RUNTIME)
 
#endif  // !defined(TARGET_ARCH_IA32)
 
#undef __
 
TypeUsageInfo::TypeUsageInfo(Thread* thread)
    : ThreadStackResource(thread),
      zone_(thread->zone()),
      assert_assignable_types_(),
      instance_creation_arguments_(
          new TypeArgumentsSet
              [thread->isolate_group()->class_table()->NumCids()]),
      klass_(Class::Handle(zone_)) {
  thread->set_type_usage_info(this);
}
 
TypeUsageInfo::~TypeUsageInfo() {
  thread()->set_type_usage_info(nullptr);
  delete[] instance_creation_arguments_;
}
 
void TypeUsageInfo::UseTypeInAssertAssignable(const AbstractType& type) {
  if (!assert_assignable_types_.HasKey(&type)) {
    AddTypeToSet(&assert_assignable_types_, &type);
  }
}
 
void TypeUsageInfo::UseTypeArgumentsInInstanceCreation(
    const Class& klass,
    const TypeArguments& ta) {
  if (ta.IsNull() || ta.IsCanonical()) {
    // The Dart VM performs an optimization where it re-uses type argument
    // vectors if the use-site needs a prefix of an already-existent type
    // arguments vector.
    //
    // For example:
    //
    //    class Foo<K, V> {
    //      foo() => new Bar<K>();
    //    }
    //
    // So the length of the type arguments vector can be longer than the number
    // of type arguments the class expects.
    ASSERT(ta.IsNull() || klass.NumTypeArguments() <= ta.Length());
 
    // If this is a non-instantiated [TypeArguments] object, then it refers to
    // type parameters.  We need to ensure the type parameters in [ta] only
    // refer to type parameters in the class.
    if (!ta.IsNull() && !ta.IsInstantiated()) {
      return;
    }
 
    klass_ = klass.ptr();
    while (klass_.NumTypeArguments() > 0) {
      const intptr_t cid = klass_.id();
      TypeArgumentsSet& set = instance_creation_arguments_[cid];
      if (!set.HasKey(&ta)) {
        set.Insert(&TypeArguments::ZoneHandle(zone_, ta.ptr()));
      }
      klass_ = klass_.SuperClass();
    }
  }
}
 
void TypeUsageInfo::BuildTypeUsageInformation() {
  ClassTable* class_table = thread()->isolate_group()->class_table();
  const intptr_t cid_count = class_table->NumCids();
 
  // Step 1) Collect the type parameters we're interested in.
  TypeParameterSet parameters_tested_against;
  CollectTypeParametersUsedInAssertAssignable(&parameters_tested_against);
 
  // Step 2) Add all types which flow into a type parameter we test against to
  // the set of types tested against.
  UpdateAssertAssignableTypes(class_table, cid_count,
                              &parameters_tested_against);
}
 
void TypeUsageInfo::CollectTypeParametersUsedInAssertAssignable(
    TypeParameterSet* set) {
  TypeParameter& param = TypeParameter::Handle(zone_);
  auto it = assert_assignable_types_.GetIterator();
  for (const AbstractType** type = it.Next(); type != nullptr;
       type = it.Next()) {
    AddToSetIfParameter(set, *type, &param);
  }
}
 
void TypeUsageInfo::UpdateAssertAssignableTypes(
    ClassTable* class_table,
    intptr_t cid_count,
    TypeParameterSet* parameters_tested_against) {
  Class& klass = Class::Handle(zone_);
  TypeParameter& param = TypeParameter::Handle(zone_);
  AbstractType& type = AbstractType::Handle(zone_);
 
  // Because Object/dynamic are common values for type parameters, we add them
  // eagerly and avoid doing it down inside the loop.
  type = Type::DynamicType();
  UseTypeInAssertAssignable(type);
  type = Type::ObjectType();  // TODO(regis): Add nullable Object?
  UseTypeInAssertAssignable(type);
 
  for (intptr_t cid = 0; cid < cid_count; ++cid) {
    if (!class_table->IsValidIndex(cid) || !class_table->HasValidClassAt(cid)) {
      continue;
    }
    klass = class_table->At(cid);
    if (klass.NumTypeArguments() <= 0) {
      continue;
    }
 
    const intptr_t num_parameters = klass.NumTypeParameters();
    for (intptr_t i = 0; i < num_parameters; ++i) {
      param = klass.TypeParameterAt(i);
      if (parameters_tested_against->HasKey(&param)) {
        TypeArgumentsSet& ta_set = instance_creation_arguments_[cid];
        auto it = ta_set.GetIterator();
        for (const TypeArguments** ta = it.Next(); ta != nullptr;
             ta = it.Next()) {
          // We only add instantiated types to the set (and dynamic/Object were
          // already handled above).
          if (!(*ta)->IsNull()) {
            type = (*ta)->TypeAt(i);
            if (type.IsInstantiated()) {
              UseTypeInAssertAssignable(type);
            }
          }
        }
      }
    }
  }
}
 
void TypeUsageInfo::AddToSetIfParameter(TypeParameterSet* set,
                                        const AbstractType* type,
                                        TypeParameter* param) {
  if (type->IsTypeParameter()) {
    *param ^= type->ptr();
    if (!param->IsNull() && !set->HasKey(param)) {
      set->Insert(&TypeParameter::Handle(zone_, param->ptr()));
    }
  }
}
 
void TypeUsageInfo::AddTypeToSet(TypeSet* set, const AbstractType* type) {
  if (!set->HasKey(type)) {
    set->Insert(&AbstractType::ZoneHandle(zone_, type->ptr()));
  }
}
 
bool TypeUsageInfo::IsUsedInTypeTest(const AbstractType& type) {
  if (type.IsFinalized()) {
    return assert_assignable_types_.HasKey(&type);
  }
  return false;
}
 
#if !defined(PRODUCT) && !defined(DART_PRECOMPILED_RUNTIME)
 
void DeoptimizeTypeTestingStubs() {
  class CollectTypes : public ObjectVisitor {
   public:
    CollectTypes(Zone* zone, GrowableArray<AbstractType*>* types)
        : zone_(zone), types_(types), cache_(SubtypeTestCache::Handle(zone)) {}
 
    void VisitObject(ObjectPtr object) {
      // Only types and record types may have optimized TTSes,
      // see TypeTestingStubGenerator::OptimizedCodeForType.
      if (object->IsType() || object->IsRecordType()) {
        types_->Add(&AbstractType::CheckedHandle(zone_, object));
      } else if (object->IsSubtypeTestCache()) {
        cache_ ^= object;
        cache_.Reset();
      }
    }
 
   private:
    Zone* const zone_;
    GrowableArray<AbstractType*>* const types_;
    TypeTestingStubGenerator generator_;
    SubtypeTestCache& cache_;
  };
 
  Thread* thread = Thread::Current();
  TIMELINE_DURATION(thread, Isolate, "DeoptimizeTypeTestingStubs");
  HANDLESCOPE(thread);
  Zone* zone = thread->zone();
  GrowableArray<AbstractType*> types(zone, 0);
  {
    HeapIterationScope iter(thread);
    CollectTypes visitor(zone, &types);
    iter.IterateObjects(&visitor);
  }
  auto& stub = Code::Handle(zone);
  for (auto* const type : types) {
    stub = TypeTestingStubGenerator::DefaultCodeForType(*type);
    type->SetTypeTestingStub(stub);
  }
}
 
#endif  // !defined(PRODUCT) && !defined(DART_PRECOMPILED_RUNTIME)
 
}  // namespace dart