runtime: Bitstring implementation for subtype checking (4/4).
Integrate the previous CLs into ART Runtime. Subsequent CLs to add
optimizing compiler support.
Use spare 24-bits from "Class#status_" field to
implement faster subtype checking in the runtime. Does not incur any extra memory overhead,
and (when in compiled code) this is always as fast or faster than the original check.
The new subtype checking is O(1) of the form:
src <: target :=
(*src).status >> #imm_target_mask == #imm_target_shifted
Based on the original prototype CL by Zhengkai Wu:
https://android-review.googlesource.com/#/c/platform/art/+/440996/
Test: art/test.py -b -j32 --host
Bug: 64692057
Change-Id: Iec3c54af529055a7f6147eebe5611d9ecd46942b
diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc
index bee1c08..64f2e46 100644
--- a/compiler/optimizing/code_generator_arm64.cc
+++ b/compiler/optimizing/code_generator_arm64.cc
@@ -2170,9 +2170,10 @@
// Even if the initialized flag is set, we need to ensure consistent memory ordering.
// TODO(vixl): Let the MacroAssembler handle MemOperand.
__ Add(temp, class_reg, status_offset);
- __ Ldar(temp, HeapOperand(temp));
+ __ Ldarb(temp, HeapOperand(temp));
__ Cmp(temp, mirror::Class::kStatusInitialized);
- __ B(lt, slow_path->GetEntryLabel());
+ __ B(ne, slow_path->GetEntryLabel());
+ // Use Bne instead of Blt because ARM64 doesn't have Ldarsb.
__ Bind(slow_path->GetExitLabel());
}
diff --git a/compiler/optimizing/code_generator_arm_vixl.cc b/compiler/optimizing/code_generator_arm_vixl.cc
index ec50ae2..c7e2640 100644
--- a/compiler/optimizing/code_generator_arm_vixl.cc
+++ b/compiler/optimizing/code_generator_arm_vixl.cc
@@ -7254,7 +7254,7 @@
LoadClassSlowPathARMVIXL* slow_path, vixl32::Register class_reg) {
UseScratchRegisterScope temps(GetVIXLAssembler());
vixl32::Register temp = temps.Acquire();
- GetAssembler()->LoadFromOffset(kLoadWord,
+ GetAssembler()->LoadFromOffset(kLoadSignedByte,
temp,
class_reg,
mirror::Class::StatusOffset().Int32Value());
diff --git a/compiler/optimizing/code_generator_mips.cc b/compiler/optimizing/code_generator_mips.cc
index 9d0826f..8517711 100644
--- a/compiler/optimizing/code_generator_mips.cc
+++ b/compiler/optimizing/code_generator_mips.cc
@@ -1983,7 +1983,7 @@
void InstructionCodeGeneratorMIPS::GenerateClassInitializationCheck(SlowPathCodeMIPS* slow_path,
Register class_reg) {
- __ LoadFromOffset(kLoadWord, TMP, class_reg, mirror::Class::StatusOffset().Int32Value());
+ __ LoadFromOffset(kLoadSignedByte, TMP, class_reg, mirror::Class::StatusOffset().Int32Value());
__ LoadConst32(AT, mirror::Class::kStatusInitialized);
__ Blt(TMP, AT, slow_path->GetEntryLabel());
// Even if the initialized flag is set, we need to ensure consistent memory ordering.
diff --git a/compiler/optimizing/code_generator_mips64.cc b/compiler/optimizing/code_generator_mips64.cc
index 18986c7..51601a1 100644
--- a/compiler/optimizing/code_generator_mips64.cc
+++ b/compiler/optimizing/code_generator_mips64.cc
@@ -1820,7 +1820,7 @@
void InstructionCodeGeneratorMIPS64::GenerateClassInitializationCheck(SlowPathCodeMIPS64* slow_path,
GpuRegister class_reg) {
- __ LoadFromOffset(kLoadWord, TMP, class_reg, mirror::Class::StatusOffset().Int32Value());
+ __ LoadFromOffset(kLoadSignedByte, TMP, class_reg, mirror::Class::StatusOffset().Int32Value());
__ LoadConst32(AT, mirror::Class::kStatusInitialized);
__ Bltc(TMP, AT, slow_path->GetEntryLabel());
// Even if the initialized flag is set, we need to ensure consistent memory ordering.
diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc
index 9ddbf73..7fb3465 100644
--- a/compiler/optimizing/code_generator_x86.cc
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -6210,7 +6210,7 @@
void InstructionCodeGeneratorX86::GenerateClassInitializationCheck(
SlowPathCode* slow_path, Register class_reg) {
- __ cmpl(Address(class_reg, mirror::Class::StatusOffset().Int32Value()),
+ __ cmpb(Address(class_reg, mirror::Class::StatusOffset().Int32Value()),
Immediate(mirror::Class::kStatusInitialized));
__ j(kLess, slow_path->GetEntryLabel());
__ Bind(slow_path->GetExitLabel());
diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc
index 9372c67..1dd1c01 100644
--- a/compiler/optimizing/code_generator_x86_64.cc
+++ b/compiler/optimizing/code_generator_x86_64.cc
@@ -5401,7 +5401,7 @@
void InstructionCodeGeneratorX86_64::GenerateClassInitializationCheck(
SlowPathCode* slow_path, CpuRegister class_reg) {
- __ cmpl(Address(class_reg, mirror::Class::StatusOffset().Int32Value()),
+ __ cmpb(Address(class_reg, mirror::Class::StatusOffset().Int32Value()),
Immediate(mirror::Class::kStatusInitialized));
__ j(kLess, slow_path->GetEntryLabel());
__ Bind(slow_path->GetExitLabel());
diff --git a/dex2oat/linker/image_writer.cc b/dex2oat/linker/image_writer.cc
index ee568e8..68c9f80 100644
--- a/dex2oat/linker/image_writer.cc
+++ b/dex2oat/linker/image_writer.cc
@@ -51,6 +51,7 @@
#include "handle_scope-inl.h"
#include "image.h"
#include "imt_conflict_table.h"
+#include "subtype_check.h"
#include "jni_internal.h"
#include "linear_alloc.h"
#include "lock_word.h"
@@ -2359,6 +2360,27 @@
FixupClassVisitor visitor(this, copy);
ObjPtr<mirror::Object>(orig)->VisitReferences(visitor, visitor);
+ if (compile_app_image_) {
+ // When we call SubtypeCheck::EnsureInitialize, it Assigns new bitstring
+ // values to the parent of that class.
+ //
+ // Every time this happens, the parent class has to mutate to increment
+ // the "Next" value.
+ //
+ // If any of these parents are in the boot image, the changes [in the parents]
+ // would be lost when the app image is reloaded.
+ //
+ // To prevent newly loaded classes (not in the app image) from being reassigned
+ // the same bitstring value as an existing app image class, uninitialize
+ // all the classes in the app image.
+ //
+ // On startup, the class linker will then re-initialize all the app
+ // image bitstrings. See also ClassLinker::AddImageSpace.
+ MutexLock subtype_check_lock(Thread::Current(), *Locks::subtype_check_lock_);
+ // Lock every time to prevent a dcheck failure when we suspend with the lock held.
+ SubtypeCheck<mirror::Class*>::ForceUninitialize(copy);
+ }
+
// Remove the clinitThreadId. This is required for image determinism.
copy->SetClinitThreadId(static_cast<pid_t>(0));
}
diff --git a/oatdump/oatdump.cc b/oatdump/oatdump.cc
index 7064fa3..84c70bb 100644
--- a/oatdump/oatdump.cc
+++ b/oatdump/oatdump.cc
@@ -49,6 +49,7 @@
#include "image-inl.h"
#include "imtable-inl.h"
#include "indenter.h"
+#include "subtype_check.h"
#include "interpreter/unstarted_runtime.h"
#include "linker/buffered_output_stream.h"
#include "linker/elf_builder.h"
@@ -2348,6 +2349,11 @@
}
} else if (obj->IsClass()) {
mirror::Class* klass = obj->AsClass();
+
+ os << "SUBTYPE_CHECK_BITS: ";
+ SubtypeCheck<mirror::Class*>::Dump(klass, os);
+ os << "\n";
+
if (klass->NumStaticFields() != 0) {
os << "STATICS:\n";
ScopedIndentation indent2(&vios_);
diff --git a/runtime/base/bit_string.h b/runtime/base/bit_string.h
index d4197e3..1cda021 100644
--- a/runtime/base/bit_string.h
+++ b/runtime/base/bit_string.h
@@ -246,6 +246,11 @@
return !(*this == other);
}
+ // Does this bitstring contain exactly 0 characters?
+ bool IsEmpty() const {
+ return (*this) == BitString{}; // NOLINT
+ }
+
// Remove all BitStringChars starting at end.
// Returns the BitString[0..end) substring as a copy.
// See also "BitString[I..N)" in the doc header.
diff --git a/runtime/class_linker.cc b/runtime/class_linker.cc
index d3eb29b..ba5fe04 100644
--- a/runtime/class_linker.cc
+++ b/runtime/class_linker.cc
@@ -453,6 +453,19 @@
java_lang_Object->GetObjectSize(),
VoidFunctor()));
+ // Initialize the SubtypeCheck bitstring for java.lang.Object and java.lang.Class.
+ {
+ // It might seem the lock here is unnecessary, however all the SubtypeCheck
+ // functions are annotated to require locks all the way down.
+ //
+ // We take the lock here to avoid using NO_THREAD_SAFETY_ANALYSIS.
+ MutexLock subtype_check_lock(Thread::Current(), *Locks::subtype_check_lock_);
+ mirror::Class* java_lang_Object_ptr = java_lang_Object.Get();
+ SubtypeCheck<mirror::Class*>::EnsureInitialized(java_lang_Object_ptr);
+ mirror::Class* java_lang_Class_ptr = java_lang_Class.Get();
+ SubtypeCheck<mirror::Class*>::EnsureInitialized(java_lang_Class_ptr);
+ }
+
// Object[] next to hold class roots.
Handle<mirror::Class> object_array_class(hs.NewHandle(
AllocClass(self, java_lang_Class.Get(),
@@ -1806,11 +1819,32 @@
for (const ClassTable::TableSlot& root : temp_set) {
visitor(root.Read());
}
+
+ {
+ // Every class in the app image has initially SubtypeCheckInfo in the
+ // Uninitialized state.
+ //
+ // The SubtypeCheck invariants imply that a SubtypeCheckInfo is at least Initialized
+ // after class initialization is complete. The app image ClassStatus as-is
+ // are almost all ClassStatus::Initialized, and being in the
+ // SubtypeCheckInfo::kUninitialized state is violating that invariant.
+ //
+ // Force every app image class's SubtypeCheck to be at least kIninitialized.
+ //
+ // See also ImageWriter::FixupClass.
+ ScopedTrace trace("Recalculate app image SubtypeCheck bitstrings");
+ MutexLock subtype_check_lock(Thread::Current(), *Locks::subtype_check_lock_);
+ for (const ClassTable::TableSlot& root : temp_set) {
+ mirror::Class* root_klass = root.Read();
+ SubtypeCheck<mirror::Class*>::EnsureInitialized(root_klass);
+ }
+ }
}
if (!oat_file->GetBssGcRoots().empty()) {
// Insert oat file to class table for visiting .bss GC roots.
class_table->InsertOatFile(oat_file);
}
+
if (added_class_table) {
WriterMutexLock mu(self, *Locks::classlinker_classes_lock_);
class_table->AddClassSet(std::move(temp_set));
@@ -5122,11 +5156,28 @@
bool can_init_fields,
bool can_init_parents) {
DCHECK(c != nullptr);
+
if (c->IsInitialized()) {
EnsureSkipAccessChecksMethods(c, image_pointer_size_);
self->AssertNoPendingException();
return true;
}
+ // SubtypeCheckInfo::Initialized must happen-before any new-instance for that type.
+ //
+ // Ensure the bitstring is initialized before any of the class initialization
+ // logic occurs. Once a class initializer starts running, objects can
+ // escape into the heap and use the subtype checking code.
+ //
+ // Note: A class whose SubtypeCheckInfo is at least Initialized means it
+ // can be used as a source for the IsSubClass check, and that all ancestors
+ // of the class are Assigned (can be used as a target for IsSubClass check)
+ // or Overflowed (can be used as a source for IsSubClass check).
+ {
+ MutexLock subtype_check_lock(Thread::Current(), *Locks::subtype_check_lock_);
+ ObjPtr<mirror::Class> c_ptr(c.Get());
+ SubtypeCheck<ObjPtr<mirror::Class>>::EnsureInitialized(c_ptr);
+ // TODO: Avoid taking subtype_check_lock_ if SubtypeCheck is already initialized.
+ }
const bool success = InitializeClass(self, c, can_init_fields, can_init_parents);
if (!success) {
if (can_init_fields && can_init_parents) {
diff --git a/runtime/class_status.h b/runtime/class_status.h
index 0877e68..7f2ef6a 100644
--- a/runtime/class_status.h
+++ b/runtime/class_status.h
@@ -18,6 +18,7 @@
#define ART_RUNTIME_CLASS_STATUS_H_
#include <iosfwd>
+#include <stdint.h>
namespace art {
@@ -70,7 +71,7 @@
// again at runtime.
//
// TODO: Explain the other states
-enum ClassStatus {
+enum ClassStatus : int8_t {
kStatusRetired = -3, // Retired, should not be used. Use the newly cloned one instead.
kStatusErrorResolved = -2,
kStatusErrorUnresolved = -1,
diff --git a/runtime/mirror/class-inl.h b/runtime/mirror/class-inl.h
index 78f6b25..eb54f7f 100644
--- a/runtime/mirror/class-inl.h
+++ b/runtime/mirror/class-inl.h
@@ -31,6 +31,7 @@
#include "gc/heap-inl.h"
#include "iftable.h"
#include "invoke_type.h"
+#include "subtype_check.h"
#include "object-inl.h"
#include "object_array.h"
#include "read_barrier-inl.h"
@@ -56,7 +57,6 @@
return GetField32(ObjectSizeAllocFastPathOffset());
}
-
template<VerifyObjectFlags kVerifyFlags, ReadBarrierOption kReadBarrierOption>
inline Class* Class::GetSuperClass() {
// Can only get super class for loaded classes (hack for when runtime is
@@ -532,16 +532,46 @@
}
inline bool Class::IsSubClass(ObjPtr<Class> klass) {
+ // Since the SubtypeCheck::IsSubtypeOf needs to lookup the Depth,
+ // it is always O(Depth) in terms of speed to do the check.
+ //
+ // So always do the "slow" linear scan in normal release builds.
+ //
+ // Future note: If we could have the depth in O(1) we could use the 'fast'
+ // method instead as it avoids a loop and a read barrier.
+ bool result = false;
DCHECK(!IsInterface()) << PrettyClass();
DCHECK(!IsArrayClass()) << PrettyClass();
ObjPtr<Class> current = this;
do {
if (current == klass) {
- return true;
+ result = true;
+ break;
}
current = current->GetSuperClass();
} while (current != nullptr);
- return false;
+
+ if (kIsDebugBuild) {
+ ObjPtr<mirror::Class> dis(this);
+
+ SubtypeCheckInfo::Result sc_result = SubtypeCheck<ObjPtr<Class>>::IsSubtypeOf(dis, klass);
+ if (sc_result != SubtypeCheckInfo::kUnknownSubtypeOf) {
+ // Note: The "kUnknownSubTypeOf" can be avoided if and only if:
+ // SubtypeCheck::EnsureInitialized(source)
+ // happens-before source.IsSubClass(target)
+ // SubtypeCheck::EnsureAssigned(target).GetState() == Assigned
+ // happens-before source.IsSubClass(target)
+ //
+ // When code generated by optimizing compiler executes this operation, both
+ // happens-before are guaranteed, so there is no fallback code there.
+ SubtypeCheckInfo::Result expected_result =
+ result ? SubtypeCheckInfo::kSubtypeOf : SubtypeCheckInfo::kNotSubtypeOf;
+ DCHECK_EQ(expected_result, sc_result)
+ << "source: " << PrettyClass() << "target: " << klass->PrettyClass();
+ }
+ }
+
+ return result;
}
inline ArtMethod* Class::FindVirtualMethodForInterface(ArtMethod* method,
diff --git a/runtime/mirror/class.cc b/runtime/mirror/class.cc
index 40157c4..4d810db 100644
--- a/runtime/mirror/class.cc
+++ b/runtime/mirror/class.cc
@@ -29,6 +29,7 @@
#include "dex_file_annotations.h"
#include "gc/accounting/card_table-inl.h"
#include "handle_scope-inl.h"
+#include "subtype_check.h"
#include "method.h"
#include "object-inl.h"
#include "object-refvisitor-inl.h"
@@ -41,6 +42,11 @@
#include "well_known_classes.h"
namespace art {
+
+// TODO: move to own CC file?
+constexpr size_t BitString::kBitSizeAtPosition[BitString::kCapacity];
+constexpr size_t BitString::kCapacity;
+
namespace mirror {
using android::base::StringPrintf;
@@ -166,11 +172,9 @@
self->AssertPendingException();
}
- static_assert(sizeof(Status) == sizeof(uint32_t), "Size of status not equal to uint32");
- if (Runtime::Current()->IsActiveTransaction()) {
- h_this->SetField32Volatile<true>(StatusOffset(), new_status);
- } else {
- h_this->SetField32Volatile<false>(StatusOffset(), new_status);
+ {
+ ObjPtr<mirror::Class> h_this_ptr = h_this.Get();
+ SubtypeCheck<ObjPtr<mirror::Class>>::WriteStatus(h_this_ptr, new_status);
}
// Setting the object size alloc fast path needs to be after the status write so that if the
diff --git a/runtime/mirror/class.h b/runtime/mirror/class.h
index 148273b..bf49f51 100644
--- a/runtime/mirror/class.h
+++ b/runtime/mirror/class.h
@@ -101,9 +101,10 @@
template<VerifyObjectFlags kVerifyFlags = kDefaultVerifyFlags>
Status GetStatus() REQUIRES_SHARED(Locks::mutator_lock_) {
- static_assert(sizeof(Status) == sizeof(uint32_t), "Size of status not equal to uint32");
- return static_cast<Status>(
- GetField32Volatile<kVerifyFlags>(OFFSET_OF_OBJECT_MEMBER(Class, status_)));
+ // Avoid including "subtype_check_bits_and_status.h" to get the field.
+ // The ClassStatus is always in the least-significant bits of status_.
+ return static_cast<Status>(static_cast<uint8_t>(
+ static_cast<uint32_t>(GetField32Volatile<kVerifyFlags>(StatusOffset())) & 0xff));
}
// This is static because 'this' may be moved by GC.
@@ -111,7 +112,7 @@
REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!Roles::uninterruptible_);
static MemberOffset StatusOffset() {
- return OFFSET_OF_OBJECT_MEMBER(Class, status_);
+ return MemberOffset(OFFSET_OF_OBJECT_MEMBER(Class, status_));
}
// Returns true if the class has been retired.
@@ -1481,8 +1482,9 @@
// Bitmap of offsets of ifields.
uint32_t reference_instance_offsets_;
- // State of class initialization.
- Status status_;
+ // See the real definition in subtype_check_bits_and_status.h
+ // typeof(status_) is actually SubtypeCheckBitsAndStatus.
+ uint32_t status_;
// The offset of the first virtual method that is copied from an interface. This includes miranda,
// default, and default-conflict methods. Having a hard limit of ((2 << 16) - 1) for methods
diff --git a/runtime/subtype_check_info.h b/runtime/subtype_check_info.h
index f60e0ac..d10d472 100644
--- a/runtime/subtype_check_info.h
+++ b/runtime/subtype_check_info.h
@@ -260,7 +260,7 @@
// Get the current state (Uninitialized, Initialized, Assigned, or Overflowed).
// See the "SubtypeCheckInfo" documentation above which explains how a state is determined.
State GetState() const {
- if (GetBitString() == BitString{}) { // NOLINT
+ if (GetBitString().IsEmpty()) {
// Empty bitstring (all 0s) -> uninitialized.
DCHECK(!bitstring_and_of_.overflow_);
return kUninitialized;
@@ -274,7 +274,7 @@
// Either Assigned or Initialized.
BitString path_to_root = GetPathToRoot();
- DCHECK(!HasNext() || GetNext() != BitStringChar{}) // NOLINT
+ DCHECK(!HasNext() || GetNext() != 0u)
<< "Expected (Assigned|Initialized) state to have >0 Next value: "
<< GetNext() << " path: " << path_to_root;
@@ -347,7 +347,7 @@
bool did_overlap = false;
if (HasNext()) {
if (kIsDebugBuild) {
- did_overlap = (GetNext() != BitStringChar{}); // NOLINT
+ did_overlap = (GetNext() != 0u);
}
SetNext(next);
diff --git a/test/988-TooDeepClassInstanceOf/expected.txt b/test/988-TooDeepClassInstanceOf/expected.txt
new file mode 100644
index 0000000..b0aad4d
--- /dev/null
+++ b/test/988-TooDeepClassInstanceOf/expected.txt
@@ -0,0 +1 @@
+passed
diff --git a/test/988-TooDeepClassInstanceOf/info.txt b/test/988-TooDeepClassInstanceOf/info.txt
new file mode 100644
index 0000000..390b00d
--- /dev/null
+++ b/test/988-TooDeepClassInstanceOf/info.txt
@@ -0,0 +1 @@
+Test the instanceof in the case the classes are deep (depth > 6)
diff --git a/test/988-TooDeepClassInstanceOf/src/Main.java b/test/988-TooDeepClassInstanceOf/src/Main.java
new file mode 100644
index 0000000..93a41e56
--- /dev/null
+++ b/test/988-TooDeepClassInstanceOf/src/Main.java
@@ -0,0 +1,80 @@
+/*
+ * Copyright (C) 2017 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+class A {}
+class B1 extends A {}
+class B2 extends A {}
+class C1 extends B1 {}
+class C2 extends B1 {}
+class D1 extends C1 {}
+class D2 extends C2 {}
+class E1 extends D1 {}
+class E2 extends D2 {}
+class F1 extends E1 {}
+class F2 extends E2 {}
+class G1 extends F1 {}
+class G2 extends F2 {}
+
+public class Main {
+ public static void main(String[] args) {
+ String yes = "Yes";
+ String no = "No";
+
+ A a = new A();
+ A b1 = new B1();
+ A b2 = new B2();
+ A c1 = new C1();
+ A c2 = new C2();
+ A f1 = new F1();
+ A f2 = new F2();
+ A g1 = new G1();
+ A g2 = new G2();
+
+ expectFalse(b1 instanceof G1);
+ expectTrue(g1 instanceof B1);
+ expectFalse(b1 instanceof F1);
+ expectTrue(f1 instanceof B1);
+
+ expectFalse(b2 instanceof G1);
+ expectFalse(g1 instanceof B2);
+ expectFalse(b2 instanceof F1);
+ expectFalse(f1 instanceof B2);
+
+ expectFalse(g2 instanceof G1);
+ expectFalse(g1 instanceof G2);
+ expectFalse(f2 instanceof F1);
+ expectFalse(f1 instanceof F2);
+
+ expectTrue(g1 instanceof F1);
+ expectFalse(g1 instanceof F2);
+ expectFalse(g2 instanceof F1);
+ expectTrue(g2 instanceof F2);
+
+ System.out.println("passed");
+ }
+
+ private static void expectTrue(boolean value) {
+ if (!value) {
+ throw new Error("Expected True");
+ }
+ }
+
+ private static void expectFalse(boolean value) {
+ if (value) {
+ throw new Error("Expected False");
+ }
+ }
+}
diff --git a/test/988-TooWideClassInstanceOf/expected.txt b/test/988-TooWideClassInstanceOf/expected.txt
new file mode 100644
index 0000000..b0aad4d
--- /dev/null
+++ b/test/988-TooWideClassInstanceOf/expected.txt
@@ -0,0 +1 @@
+passed
diff --git a/test/988-TooWideClassInstanceOf/info.txt b/test/988-TooWideClassInstanceOf/info.txt
new file mode 100644
index 0000000..30546fe
--- /dev/null
+++ b/test/988-TooWideClassInstanceOf/info.txt
@@ -0,0 +1,2 @@
+Test the instanceof in the case the classes are too wide (> the classes each depth's bitstring can
+represent).
diff --git a/test/988-TooWideClassInstanceOf/src/Main.java b/test/988-TooWideClassInstanceOf/src/Main.java
new file mode 100644
index 0000000..332569c
--- /dev/null
+++ b/test/988-TooWideClassInstanceOf/src/Main.java
@@ -0,0 +1,1280 @@
+/*
+ * Copyright (C) 2017 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+class A {}
+class B1 extends A {}
+class B2 extends A {}
+class C1 extends B1 {}
+class C2 extends B1 {}
+class D1 extends C1 {}
+class D2 extends C2 {}
+class E1 extends D2 {}
+class E2 extends D1 {}
+class E3 extends D2 {}
+class E4 extends D1 {}
+class E5 extends D2 {}
+class E6 extends D1 {}
+class E7 extends D2 {}
+class E8 extends D1 {}
+class E9 extends D2 {}
+class E10 extends D1 {}
+class E11 extends D2 {}
+class E12 extends D1 {}
+class E13 extends D2 {}
+class E14 extends D1 {}
+class E15 extends D2 {}
+class E16 extends D1 {}
+class E17 extends D2 {}
+class E18 extends D1 {}
+class E19 extends D2 {}
+class E20 extends D1 {}
+class E21 extends D2 {}
+class E22 extends D1 {}
+class E23 extends D2 {}
+class E24 extends D1 {}
+class E25 extends D2 {}
+class E26 extends D1 {}
+class E27 extends D2 {}
+class E28 extends D1 {}
+class E29 extends D2 {}
+class E30 extends D1 {}
+class E31 extends D2 {}
+class E32 extends D1 {}
+class E33 extends D2 {}
+class E34 extends D1 {}
+class E35 extends D2 {}
+class E36 extends D1 {}
+class E37 extends D2 {}
+class E38 extends D1 {}
+class E39 extends D2 {}
+class E40 extends D1 {}
+class E41 extends D2 {}
+class E42 extends D1 {}
+class E43 extends D2 {}
+class E44 extends D1 {}
+class E45 extends D2 {}
+class E46 extends D1 {}
+class E47 extends D2 {}
+class E48 extends D1 {}
+class E49 extends D2 {}
+class E50 extends D1 {}
+class E51 extends D2 {}
+class E52 extends D1 {}
+class E53 extends D2 {}
+class E54 extends D1 {}
+class E55 extends D2 {}
+class E56 extends D1 {}
+class E57 extends D2 {}
+class E58 extends D1 {}
+class E59 extends D2 {}
+class E60 extends D1 {}
+class E61 extends D2 {}
+class E62 extends D1 {}
+class E63 extends D2 {}
+class E64 extends D1 {}
+class E65 extends D2 {}
+class E66 extends D1 {}
+class E67 extends D2 {}
+class E68 extends D1 {}
+class E69 extends D2 {}
+class E70 extends D1 {}
+class E71 extends D2 {}
+class E72 extends D1 {}
+class E73 extends D2 {}
+class E74 extends D1 {}
+class E75 extends D2 {}
+class E76 extends D1 {}
+class E77 extends D2 {}
+class E78 extends D1 {}
+class E79 extends D2 {}
+class E80 extends D1 {}
+class E81 extends D2 {}
+class E82 extends D1 {}
+class E83 extends D2 {}
+class E84 extends D1 {}
+class E85 extends D2 {}
+class E86 extends D1 {}
+class E87 extends D2 {}
+class E88 extends D1 {}
+class E89 extends D2 {}
+class E90 extends D1 {}
+class E91 extends D2 {}
+class E92 extends D1 {}
+class E93 extends D2 {}
+class E94 extends D1 {}
+class E95 extends D2 {}
+class E96 extends D1 {}
+class E97 extends D2 {}
+class E98 extends D1 {}
+class E99 extends D2 {}
+class E100 extends D1 {}
+class E101 extends D2 {}
+class E102 extends D1 {}
+class E103 extends D2 {}
+class E104 extends D1 {}
+class E105 extends D2 {}
+class E106 extends D1 {}
+class E107 extends D2 {}
+class E108 extends D1 {}
+class E109 extends D2 {}
+class E110 extends D1 {}
+class E111 extends D2 {}
+class E112 extends D1 {}
+class E113 extends D2 {}
+class E114 extends D1 {}
+class E115 extends D2 {}
+class E116 extends D1 {}
+class E117 extends D2 {}
+class E118 extends D1 {}
+class E119 extends D2 {}
+class E120 extends D1 {}
+class E121 extends D2 {}
+class E122 extends D1 {}
+class E123 extends D2 {}
+class E124 extends D1 {}
+class E125 extends D2 {}
+class E126 extends D1 {}
+class E127 extends D2 {}
+class E128 extends D1 {}
+class E129 extends D2 {}
+class E130 extends D1 {}
+class E131 extends D2 {}
+class E132 extends D1 {}
+class E133 extends D2 {}
+class E134 extends D1 {}
+class E135 extends D2 {}
+class E136 extends D1 {}
+class E137 extends D2 {}
+class E138 extends D1 {}
+class E139 extends D2 {}
+class E140 extends D1 {}
+class E141 extends D2 {}
+class E142 extends D1 {}
+class E143 extends D2 {}
+class E144 extends D1 {}
+class E145 extends D2 {}
+class E146 extends D1 {}
+class E147 extends D2 {}
+class E148 extends D1 {}
+class E149 extends D2 {}
+class E150 extends D1 {}
+class E151 extends D2 {}
+class E152 extends D1 {}
+class E153 extends D2 {}
+class E154 extends D1 {}
+class E155 extends D2 {}
+class E156 extends D1 {}
+class E157 extends D2 {}
+class E158 extends D1 {}
+class E159 extends D2 {}
+class E160 extends D1 {}
+class E161 extends D2 {}
+class E162 extends D1 {}
+class E163 extends D2 {}
+class E164 extends D1 {}
+class E165 extends D2 {}
+class E166 extends D1 {}
+class E167 extends D2 {}
+class E168 extends D1 {}
+class E169 extends D2 {}
+class E170 extends D1 {}
+class E171 extends D2 {}
+class E172 extends D1 {}
+class E173 extends D2 {}
+class E174 extends D1 {}
+class E175 extends D2 {}
+class E176 extends D1 {}
+class E177 extends D2 {}
+class E178 extends D1 {}
+class E179 extends D2 {}
+class E180 extends D1 {}
+class E181 extends D2 {}
+class E182 extends D1 {}
+class E183 extends D2 {}
+class E184 extends D1 {}
+class E185 extends D2 {}
+class E186 extends D1 {}
+class E187 extends D2 {}
+class E188 extends D1 {}
+class E189 extends D2 {}
+class E190 extends D1 {}
+class E191 extends D2 {}
+class E192 extends D1 {}
+class E193 extends D2 {}
+class E194 extends D1 {}
+class E195 extends D2 {}
+class E196 extends D1 {}
+class E197 extends D2 {}
+class E198 extends D1 {}
+class E199 extends D2 {}
+class E200 extends D1 {}
+class E201 extends D2 {}
+class E202 extends D1 {}
+class E203 extends D2 {}
+class E204 extends D1 {}
+class E205 extends D2 {}
+class E206 extends D1 {}
+class E207 extends D2 {}
+class E208 extends D1 {}
+class E209 extends D2 {}
+class E210 extends D1 {}
+class E211 extends D2 {}
+class E212 extends D1 {}
+class E213 extends D2 {}
+class E214 extends D1 {}
+class E215 extends D2 {}
+class E216 extends D1 {}
+class E217 extends D2 {}
+class E218 extends D1 {}
+class E219 extends D2 {}
+class E220 extends D1 {}
+class E221 extends D2 {}
+class E222 extends D1 {}
+class E223 extends D2 {}
+class E224 extends D1 {}
+class E225 extends D2 {}
+class E226 extends D1 {}
+class E227 extends D2 {}
+class E228 extends D1 {}
+class E229 extends D2 {}
+class E230 extends D1 {}
+class E231 extends D2 {}
+class E232 extends D1 {}
+class E233 extends D2 {}
+class E234 extends D1 {}
+class E235 extends D2 {}
+class E236 extends D1 {}
+class E237 extends D2 {}
+class E238 extends D1 {}
+class E239 extends D2 {}
+class E240 extends D1 {}
+class E241 extends D2 {}
+class E242 extends D1 {}
+class E243 extends D2 {}
+class E244 extends D1 {}
+class E245 extends D2 {}
+class E246 extends D1 {}
+class E247 extends D2 {}
+class E248 extends D1 {}
+class E249 extends D2 {}
+class E250 extends D1 {}
+class E251 extends D2 {}
+class E252 extends D1 {}
+class E253 extends D2 {}
+class E254 extends D1 {}
+class E255 extends D2 {}
+class E256 extends D1 {}
+class E257 extends D2 {}
+class E258 extends D1 {}
+class E259 extends D2 {}
+class E260 extends D1 {}
+class E261 extends D2 {}
+class E262 extends D1 {}
+class E263 extends D2 {}
+class E264 extends D1 {}
+class E265 extends D2 {}
+class E266 extends D1 {}
+class E267 extends D2 {}
+class E268 extends D1 {}
+class E269 extends D2 {}
+class E270 extends D1 {}
+class E271 extends D2 {}
+class E272 extends D1 {}
+class E273 extends D2 {}
+class E274 extends D1 {}
+class E275 extends D2 {}
+class E276 extends D1 {}
+class E277 extends D2 {}
+class E278 extends D1 {}
+class E279 extends D2 {}
+class E280 extends D1 {}
+class E281 extends D2 {}
+class E282 extends D1 {}
+class E283 extends D2 {}
+class E284 extends D1 {}
+class E285 extends D2 {}
+class E286 extends D1 {}
+class E287 extends D2 {}
+class E288 extends D1 {}
+class E289 extends D2 {}
+class E290 extends D1 {}
+class E291 extends D2 {}
+class E292 extends D1 {}
+class E293 extends D2 {}
+class E294 extends D1 {}
+class E295 extends D2 {}
+class E296 extends D1 {}
+class E297 extends D2 {}
+class E298 extends D1 {}
+class E299 extends D2 {}
+class E300 extends D1 {}
+class E301 extends D2 {}
+class E302 extends D1 {}
+class E303 extends D2 {}
+class E304 extends D1 {}
+class E305 extends D2 {}
+class E306 extends D1 {}
+class E307 extends D2 {}
+class E308 extends D1 {}
+class E309 extends D2 {}
+class E310 extends D1 {}
+class E311 extends D2 {}
+class E312 extends D1 {}
+class E313 extends D2 {}
+class E314 extends D1 {}
+class E315 extends D2 {}
+class E316 extends D1 {}
+class E317 extends D2 {}
+class E318 extends D1 {}
+class E319 extends D2 {}
+class E320 extends D1 {}
+class E321 extends D2 {}
+class E322 extends D1 {}
+class E323 extends D2 {}
+class E324 extends D1 {}
+class E325 extends D2 {}
+class E326 extends D1 {}
+class E327 extends D2 {}
+class E328 extends D1 {}
+class E329 extends D2 {}
+class E330 extends D1 {}
+class E331 extends D2 {}
+class E332 extends D1 {}
+class E333 extends D2 {}
+class E334 extends D1 {}
+class E335 extends D2 {}
+class E336 extends D1 {}
+class E337 extends D2 {}
+class E338 extends D1 {}
+class E339 extends D2 {}
+class E340 extends D1 {}
+class E341 extends D2 {}
+class E342 extends D1 {}
+class E343 extends D2 {}
+class E344 extends D1 {}
+class E345 extends D2 {}
+class E346 extends D1 {}
+class E347 extends D2 {}
+class E348 extends D1 {}
+class E349 extends D2 {}
+class E350 extends D1 {}
+class E351 extends D2 {}
+class E352 extends D1 {}
+class E353 extends D2 {}
+class E354 extends D1 {}
+class E355 extends D2 {}
+class E356 extends D1 {}
+class E357 extends D2 {}
+class E358 extends D1 {}
+class E359 extends D2 {}
+class E360 extends D1 {}
+class E361 extends D2 {}
+class E362 extends D1 {}
+class E363 extends D2 {}
+class E364 extends D1 {}
+class E365 extends D2 {}
+class E366 extends D1 {}
+class E367 extends D2 {}
+class E368 extends D1 {}
+class E369 extends D2 {}
+class E370 extends D1 {}
+class E371 extends D2 {}
+class E372 extends D1 {}
+class E373 extends D2 {}
+class E374 extends D1 {}
+class E375 extends D2 {}
+class E376 extends D1 {}
+class E377 extends D2 {}
+class E378 extends D1 {}
+class E379 extends D2 {}
+class E380 extends D1 {}
+class E381 extends D2 {}
+class E382 extends D1 {}
+class E383 extends D2 {}
+class E384 extends D1 {}
+class E385 extends D2 {}
+class E386 extends D1 {}
+class E387 extends D2 {}
+class E388 extends D1 {}
+class E389 extends D2 {}
+class E390 extends D1 {}
+class E391 extends D2 {}
+class E392 extends D1 {}
+class E393 extends D2 {}
+class E394 extends D1 {}
+class E395 extends D2 {}
+class E396 extends D1 {}
+class E397 extends D2 {}
+class E398 extends D1 {}
+class E399 extends D2 {}
+class E400 extends D1 {}
+class E401 extends D2 {}
+class E402 extends D1 {}
+class E403 extends D2 {}
+class E404 extends D1 {}
+class E405 extends D2 {}
+class E406 extends D1 {}
+class E407 extends D2 {}
+class E408 extends D1 {}
+class E409 extends D2 {}
+class E410 extends D1 {}
+class E411 extends D2 {}
+class E412 extends D1 {}
+class E413 extends D2 {}
+class E414 extends D1 {}
+class E415 extends D2 {}
+class E416 extends D1 {}
+class E417 extends D2 {}
+class E418 extends D1 {}
+class E419 extends D2 {}
+class E420 extends D1 {}
+class E421 extends D2 {}
+class E422 extends D1 {}
+class E423 extends D2 {}
+class E424 extends D1 {}
+class E425 extends D2 {}
+class E426 extends D1 {}
+class E427 extends D2 {}
+class E428 extends D1 {}
+class E429 extends D2 {}
+class E430 extends D1 {}
+class E431 extends D2 {}
+class E432 extends D1 {}
+class E433 extends D2 {}
+class E434 extends D1 {}
+class E435 extends D2 {}
+class E436 extends D1 {}
+class E437 extends D2 {}
+class E438 extends D1 {}
+class E439 extends D2 {}
+class E440 extends D1 {}
+class E441 extends D2 {}
+class E442 extends D1 {}
+class E443 extends D2 {}
+class E444 extends D1 {}
+class E445 extends D2 {}
+class E446 extends D1 {}
+class E447 extends D2 {}
+class E448 extends D1 {}
+class E449 extends D2 {}
+class E450 extends D1 {}
+class E451 extends D2 {}
+class E452 extends D1 {}
+class E453 extends D2 {}
+class E454 extends D1 {}
+class E455 extends D2 {}
+class E456 extends D1 {}
+class E457 extends D2 {}
+class E458 extends D1 {}
+class E459 extends D2 {}
+class E460 extends D1 {}
+class E461 extends D2 {}
+class E462 extends D1 {}
+class E463 extends D2 {}
+class E464 extends D1 {}
+class E465 extends D2 {}
+class E466 extends D1 {}
+class E467 extends D2 {}
+class E468 extends D1 {}
+class E469 extends D2 {}
+class E470 extends D1 {}
+class E471 extends D2 {}
+class E472 extends D1 {}
+class E473 extends D2 {}
+class E474 extends D1 {}
+class E475 extends D2 {}
+class E476 extends D1 {}
+class E477 extends D2 {}
+class E478 extends D1 {}
+class E479 extends D2 {}
+class E480 extends D1 {}
+class E481 extends D2 {}
+class E482 extends D1 {}
+class E483 extends D2 {}
+class E484 extends D1 {}
+class E485 extends D2 {}
+class E486 extends D1 {}
+class E487 extends D2 {}
+class E488 extends D1 {}
+class E489 extends D2 {}
+class E490 extends D1 {}
+class E491 extends D2 {}
+class E492 extends D1 {}
+class E493 extends D2 {}
+class E494 extends D1 {}
+class E495 extends D2 {}
+class E496 extends D1 {}
+class E497 extends D2 {}
+class E498 extends D1 {}
+class E499 extends D2 {}
+class E500 extends D1 {}
+class E501 extends D2 {}
+class E502 extends D1 {}
+class E503 extends D2 {}
+class E504 extends D1 {}
+class E505 extends D2 {}
+class E506 extends D1 {}
+class E507 extends D2 {}
+class E508 extends D1 {}
+class E509 extends D2 {}
+class E510 extends D1 {}
+class E511 extends D2 {}
+class E512 extends D1 {}
+class E513 extends D2 {}
+class E514 extends D1 {}
+class E515 extends D2 {}
+class E516 extends D1 {}
+class E517 extends D2 {}
+class E518 extends D1 {}
+class E519 extends D2 {}
+class E520 extends D1 {}
+class E521 extends D2 {}
+class E522 extends D1 {}
+class E523 extends D2 {}
+class E524 extends D1 {}
+class E525 extends D2 {}
+class E526 extends D1 {}
+class E527 extends D2 {}
+class E528 extends D1 {}
+class E529 extends D2 {}
+class E530 extends D1 {}
+class E531 extends D2 {}
+class E532 extends D1 {}
+class E533 extends D2 {}
+class E534 extends D1 {}
+class E535 extends D2 {}
+class E536 extends D1 {}
+class E537 extends D2 {}
+class E538 extends D1 {}
+class E539 extends D2 {}
+class E540 extends D1 {}
+class E541 extends D2 {}
+class E542 extends D1 {}
+class E543 extends D2 {}
+class E544 extends D1 {}
+class E545 extends D2 {}
+class E546 extends D1 {}
+class E547 extends D2 {}
+class E548 extends D1 {}
+class E549 extends D2 {}
+class E550 extends D1 {}
+class E551 extends D2 {}
+class E552 extends D1 {}
+class E553 extends D2 {}
+class E554 extends D1 {}
+class E555 extends D2 {}
+class E556 extends D1 {}
+class E557 extends D2 {}
+class E558 extends D1 {}
+class E559 extends D2 {}
+class E560 extends D1 {}
+class E561 extends D2 {}
+class E562 extends D1 {}
+class E563 extends D2 {}
+class E564 extends D1 {}
+class E565 extends D2 {}
+class E566 extends D1 {}
+class E567 extends D2 {}
+class E568 extends D1 {}
+class E569 extends D2 {}
+class E570 extends D1 {}
+class E571 extends D2 {}
+class E572 extends D1 {}
+class E573 extends D2 {}
+class E574 extends D1 {}
+class E575 extends D2 {}
+class E576 extends D1 {}
+class E577 extends D2 {}
+class E578 extends D1 {}
+class E579 extends D2 {}
+class E580 extends D1 {}
+class E581 extends D2 {}
+class E582 extends D1 {}
+class E583 extends D2 {}
+class E584 extends D1 {}
+class E585 extends D2 {}
+class E586 extends D1 {}
+class E587 extends D2 {}
+class E588 extends D1 {}
+class E589 extends D2 {}
+class E590 extends D1 {}
+class E591 extends D2 {}
+class E592 extends D1 {}
+class E593 extends D2 {}
+class E594 extends D1 {}
+class E595 extends D2 {}
+class E596 extends D1 {}
+class E597 extends D2 {}
+class E598 extends D1 {}
+class E599 extends D2 {}
+class E600 extends D1 {}
+class E601 extends D2 {}
+class E602 extends D1 {}
+class E603 extends D2 {}
+class E604 extends D1 {}
+class E605 extends D2 {}
+class E606 extends D1 {}
+class E607 extends D2 {}
+class E608 extends D1 {}
+class E609 extends D2 {}
+class E610 extends D1 {}
+class E611 extends D2 {}
+class E612 extends D1 {}
+class E613 extends D2 {}
+class E614 extends D1 {}
+class E615 extends D2 {}
+class E616 extends D1 {}
+class E617 extends D2 {}
+class E618 extends D1 {}
+class E619 extends D2 {}
+class E620 extends D1 {}
+class E621 extends D2 {}
+class E622 extends D1 {}
+class E623 extends D2 {}
+class E624 extends D1 {}
+class E625 extends D2 {}
+class E626 extends D1 {}
+class E627 extends D2 {}
+class E628 extends D1 {}
+class E629 extends D2 {}
+class E630 extends D1 {}
+class E631 extends D2 {}
+class E632 extends D1 {}
+class E633 extends D2 {}
+class E634 extends D1 {}
+class E635 extends D2 {}
+class E636 extends D1 {}
+class E637 extends D2 {}
+class E638 extends D1 {}
+class E639 extends D2 {}
+class E640 extends D1 {}
+class E641 extends D2 {}
+class E642 extends D1 {}
+class E643 extends D2 {}
+class E644 extends D1 {}
+class E645 extends D2 {}
+class E646 extends D1 {}
+class E647 extends D2 {}
+class E648 extends D1 {}
+class E649 extends D2 {}
+class E650 extends D1 {}
+class E651 extends D2 {}
+class E652 extends D1 {}
+class E653 extends D2 {}
+class E654 extends D1 {}
+class E655 extends D2 {}
+class E656 extends D1 {}
+class E657 extends D2 {}
+class E658 extends D1 {}
+class E659 extends D2 {}
+class E660 extends D1 {}
+class E661 extends D2 {}
+class E662 extends D1 {}
+class E663 extends D2 {}
+class E664 extends D1 {}
+class E665 extends D2 {}
+class E666 extends D1 {}
+class E667 extends D2 {}
+class E668 extends D1 {}
+class E669 extends D2 {}
+class E670 extends D1 {}
+class E671 extends D2 {}
+class E672 extends D1 {}
+class E673 extends D2 {}
+class E674 extends D1 {}
+class E675 extends D2 {}
+class E676 extends D1 {}
+class E677 extends D2 {}
+class E678 extends D1 {}
+class E679 extends D2 {}
+class E680 extends D1 {}
+class E681 extends D2 {}
+class E682 extends D1 {}
+class E683 extends D2 {}
+class E684 extends D1 {}
+class E685 extends D2 {}
+class E686 extends D1 {}
+class E687 extends D2 {}
+class E688 extends D1 {}
+class E689 extends D2 {}
+class E690 extends D1 {}
+class E691 extends D2 {}
+class E692 extends D1 {}
+class E693 extends D2 {}
+class E694 extends D1 {}
+class E695 extends D2 {}
+class E696 extends D1 {}
+class E697 extends D2 {}
+class E698 extends D1 {}
+class E699 extends D2 {}
+class E700 extends D1 {}
+class E701 extends D2 {}
+class E702 extends D1 {}
+class E703 extends D2 {}
+class E704 extends D1 {}
+class E705 extends D2 {}
+class E706 extends D1 {}
+class E707 extends D2 {}
+class E708 extends D1 {}
+class E709 extends D2 {}
+class E710 extends D1 {}
+class E711 extends D2 {}
+class E712 extends D1 {}
+class E713 extends D2 {}
+class E714 extends D1 {}
+class E715 extends D2 {}
+class E716 extends D1 {}
+class E717 extends D2 {}
+class E718 extends D1 {}
+class E719 extends D2 {}
+class E720 extends D1 {}
+class E721 extends D2 {}
+class E722 extends D1 {}
+class E723 extends D2 {}
+class E724 extends D1 {}
+class E725 extends D2 {}
+class E726 extends D1 {}
+class E727 extends D2 {}
+class E728 extends D1 {}
+class E729 extends D2 {}
+class E730 extends D1 {}
+class E731 extends D2 {}
+class E732 extends D1 {}
+class E733 extends D2 {}
+class E734 extends D1 {}
+class E735 extends D2 {}
+class E736 extends D1 {}
+class E737 extends D2 {}
+class E738 extends D1 {}
+class E739 extends D2 {}
+class E740 extends D1 {}
+class E741 extends D2 {}
+class E742 extends D1 {}
+class E743 extends D2 {}
+class E744 extends D1 {}
+class E745 extends D2 {}
+class E746 extends D1 {}
+class E747 extends D2 {}
+class E748 extends D1 {}
+class E749 extends D2 {}
+class E750 extends D1 {}
+class E751 extends D2 {}
+class E752 extends D1 {}
+class E753 extends D2 {}
+class E754 extends D1 {}
+class E755 extends D2 {}
+class E756 extends D1 {}
+class E757 extends D2 {}
+class E758 extends D1 {}
+class E759 extends D2 {}
+class E760 extends D1 {}
+class E761 extends D2 {}
+class E762 extends D1 {}
+class E763 extends D2 {}
+class E764 extends D1 {}
+class E765 extends D2 {}
+class E766 extends D1 {}
+class E767 extends D2 {}
+class E768 extends D1 {}
+class E769 extends D2 {}
+class E770 extends D1 {}
+class E771 extends D2 {}
+class E772 extends D1 {}
+class E773 extends D2 {}
+class E774 extends D1 {}
+class E775 extends D2 {}
+class E776 extends D1 {}
+class E777 extends D2 {}
+class E778 extends D1 {}
+class E779 extends D2 {}
+class E780 extends D1 {}
+class E781 extends D2 {}
+class E782 extends D1 {}
+class E783 extends D2 {}
+class E784 extends D1 {}
+class E785 extends D2 {}
+class E786 extends D1 {}
+class E787 extends D2 {}
+class E788 extends D1 {}
+class E789 extends D2 {}
+class E790 extends D1 {}
+class E791 extends D2 {}
+class E792 extends D1 {}
+class E793 extends D2 {}
+class E794 extends D1 {}
+class E795 extends D2 {}
+class E796 extends D1 {}
+class E797 extends D2 {}
+class E798 extends D1 {}
+class E799 extends D2 {}
+class E800 extends D1 {}
+class E801 extends D2 {}
+class E802 extends D1 {}
+class E803 extends D2 {}
+class E804 extends D1 {}
+class E805 extends D2 {}
+class E806 extends D1 {}
+class E807 extends D2 {}
+class E808 extends D1 {}
+class E809 extends D2 {}
+class E810 extends D1 {}
+class E811 extends D2 {}
+class E812 extends D1 {}
+class E813 extends D2 {}
+class E814 extends D1 {}
+class E815 extends D2 {}
+class E816 extends D1 {}
+class E817 extends D2 {}
+class E818 extends D1 {}
+class E819 extends D2 {}
+class E820 extends D1 {}
+class E821 extends D2 {}
+class E822 extends D1 {}
+class E823 extends D2 {}
+class E824 extends D1 {}
+class E825 extends D2 {}
+class E826 extends D1 {}
+class E827 extends D2 {}
+class E828 extends D1 {}
+class E829 extends D2 {}
+class E830 extends D1 {}
+class E831 extends D2 {}
+class E832 extends D1 {}
+class E833 extends D2 {}
+class E834 extends D1 {}
+class E835 extends D2 {}
+class E836 extends D1 {}
+class E837 extends D2 {}
+class E838 extends D1 {}
+class E839 extends D2 {}
+class E840 extends D1 {}
+class E841 extends D2 {}
+class E842 extends D1 {}
+class E843 extends D2 {}
+class E844 extends D1 {}
+class E845 extends D2 {}
+class E846 extends D1 {}
+class E847 extends D2 {}
+class E848 extends D1 {}
+class E849 extends D2 {}
+class E850 extends D1 {}
+class E851 extends D2 {}
+class E852 extends D1 {}
+class E853 extends D2 {}
+class E854 extends D1 {}
+class E855 extends D2 {}
+class E856 extends D1 {}
+class E857 extends D2 {}
+class E858 extends D1 {}
+class E859 extends D2 {}
+class E860 extends D1 {}
+class E861 extends D2 {}
+class E862 extends D1 {}
+class E863 extends D2 {}
+class E864 extends D1 {}
+class E865 extends D2 {}
+class E866 extends D1 {}
+class E867 extends D2 {}
+class E868 extends D1 {}
+class E869 extends D2 {}
+class E870 extends D1 {}
+class E871 extends D2 {}
+class E872 extends D1 {}
+class E873 extends D2 {}
+class E874 extends D1 {}
+class E875 extends D2 {}
+class E876 extends D1 {}
+class E877 extends D2 {}
+class E878 extends D1 {}
+class E879 extends D2 {}
+class E880 extends D1 {}
+class E881 extends D2 {}
+class E882 extends D1 {}
+class E883 extends D2 {}
+class E884 extends D1 {}
+class E885 extends D2 {}
+class E886 extends D1 {}
+class E887 extends D2 {}
+class E888 extends D1 {}
+class E889 extends D2 {}
+class E890 extends D1 {}
+class E891 extends D2 {}
+class E892 extends D1 {}
+class E893 extends D2 {}
+class E894 extends D1 {}
+class E895 extends D2 {}
+class E896 extends D1 {}
+class E897 extends D2 {}
+class E898 extends D1 {}
+class E899 extends D2 {}
+class E900 extends D1 {}
+class E901 extends D2 {}
+class E902 extends D1 {}
+class E903 extends D2 {}
+class E904 extends D1 {}
+class E905 extends D2 {}
+class E906 extends D1 {}
+class E907 extends D2 {}
+class E908 extends D1 {}
+class E909 extends D2 {}
+class E910 extends D1 {}
+class E911 extends D2 {}
+class E912 extends D1 {}
+class E913 extends D2 {}
+class E914 extends D1 {}
+class E915 extends D2 {}
+class E916 extends D1 {}
+class E917 extends D2 {}
+class E918 extends D1 {}
+class E919 extends D2 {}
+class E920 extends D1 {}
+class E921 extends D2 {}
+class E922 extends D1 {}
+class E923 extends D2 {}
+class E924 extends D1 {}
+class E925 extends D2 {}
+class E926 extends D1 {}
+class E927 extends D2 {}
+class E928 extends D1 {}
+class E929 extends D2 {}
+class E930 extends D1 {}
+class E931 extends D2 {}
+class E932 extends D1 {}
+class E933 extends D2 {}
+class E934 extends D1 {}
+class E935 extends D2 {}
+class E936 extends D1 {}
+class E937 extends D2 {}
+class E938 extends D1 {}
+class E939 extends D2 {}
+class E940 extends D1 {}
+class E941 extends D2 {}
+class E942 extends D1 {}
+class E943 extends D2 {}
+class E944 extends D1 {}
+class E945 extends D2 {}
+class E946 extends D1 {}
+class E947 extends D2 {}
+class E948 extends D1 {}
+class E949 extends D2 {}
+class E950 extends D1 {}
+class E951 extends D2 {}
+class E952 extends D1 {}
+class E953 extends D2 {}
+class E954 extends D1 {}
+class E955 extends D2 {}
+class E956 extends D1 {}
+class E957 extends D2 {}
+class E958 extends D1 {}
+class E959 extends D2 {}
+class E960 extends D1 {}
+class E961 extends D2 {}
+class E962 extends D1 {}
+class E963 extends D2 {}
+class E964 extends D1 {}
+class E965 extends D2 {}
+class E966 extends D1 {}
+class E967 extends D2 {}
+class E968 extends D1 {}
+class E969 extends D2 {}
+class E970 extends D1 {}
+class E971 extends D2 {}
+class E972 extends D1 {}
+class E973 extends D2 {}
+class E974 extends D1 {}
+class E975 extends D2 {}
+class E976 extends D1 {}
+class E977 extends D2 {}
+class E978 extends D1 {}
+class E979 extends D2 {}
+class E980 extends D1 {}
+class E981 extends D2 {}
+class E982 extends D1 {}
+class E983 extends D2 {}
+class E984 extends D1 {}
+class E985 extends D2 {}
+class E986 extends D1 {}
+class E987 extends D2 {}
+class E988 extends D1 {}
+class E989 extends D2 {}
+class E990 extends D1 {}
+class E991 extends D2 {}
+class E992 extends D1 {}
+class E993 extends D2 {}
+class E994 extends D1 {}
+class E995 extends D2 {}
+class E996 extends D1 {}
+class E997 extends D2 {}
+class E998 extends D1 {}
+class E999 extends D2 {}
+class E1000 extends D1 {}
+class E1001 extends D2 {}
+class E1002 extends D1 {}
+class E1003 extends D2 {}
+class E1004 extends D1 {}
+class E1005 extends D2 {}
+class E1006 extends D1 {}
+class E1007 extends D2 {}
+class E1008 extends D1 {}
+class E1009 extends D2 {}
+class E1010 extends D1 {}
+class E1011 extends D2 {}
+class E1012 extends D1 {}
+class E1013 extends D2 {}
+class E1014 extends D1 {}
+class E1015 extends D2 {}
+class E1016 extends D1 {}
+class E1017 extends D2 {}
+class E1018 extends D1 {}
+class E1019 extends D2 {}
+class E1020 extends D1 {}
+class E1021 extends D2 {}
+class E1022 extends D1 {}
+class E1023 extends D2 {}
+class E1024 extends D1 {}
+class E1025 extends D2 {}
+class E1026 extends D1 {}
+class E1027 extends D2 {}
+class E1028 extends D1 {}
+class E1029 extends D2 {}
+class E1030 extends D1 {}
+class E1031 extends D2 {}
+class E1032 extends D1 {}
+class E1033 extends D2 {}
+class E1034 extends D1 {}
+class E1035 extends D2 {}
+class E1036 extends D1 {}
+class E1037 extends D2 {}
+class E1038 extends D1 {}
+class E1039 extends D2 {}
+class E1040 extends D1 {}
+class E1041 extends D2 {}
+class E1042 extends D1 {}
+class E1043 extends D2 {}
+class E1044 extends D1 {}
+class E1045 extends D2 {}
+class E1046 extends D1 {}
+class E1047 extends D2 {}
+class E1048 extends D1 {}
+class E1049 extends D2 {}
+class E1050 extends D1 {}
+class E1051 extends D2 {}
+class E1052 extends D1 {}
+class E1053 extends D2 {}
+class E1054 extends D1 {}
+class E1055 extends D2 {}
+class E1056 extends D1 {}
+class E1057 extends D2 {}
+class E1058 extends D1 {}
+class E1059 extends D2 {}
+class E1060 extends D1 {}
+class E1061 extends D2 {}
+class E1062 extends D1 {}
+class E1063 extends D2 {}
+class E1064 extends D1 {}
+class E1065 extends D2 {}
+class E1066 extends D1 {}
+class E1067 extends D2 {}
+class E1068 extends D1 {}
+class E1069 extends D2 {}
+class E1070 extends D1 {}
+class E1071 extends D2 {}
+class E1072 extends D1 {}
+class E1073 extends D2 {}
+class E1074 extends D1 {}
+class E1075 extends D2 {}
+class E1076 extends D1 {}
+class E1077 extends D2 {}
+class E1078 extends D1 {}
+class E1079 extends D2 {}
+class E1080 extends D1 {}
+class E1081 extends D2 {}
+class E1082 extends D1 {}
+class E1083 extends D2 {}
+class E1084 extends D1 {}
+class E1085 extends D2 {}
+class E1086 extends D1 {}
+class E1087 extends D2 {}
+class E1088 extends D1 {}
+class E1089 extends D2 {}
+class E1090 extends D1 {}
+class E1091 extends D2 {}
+class E1092 extends D1 {}
+class E1093 extends D2 {}
+class E1094 extends D1 {}
+class E1095 extends D2 {}
+class E1096 extends D1 {}
+class E1097 extends D2 {}
+class E1098 extends D1 {}
+class E1099 extends D2 {}
+class E1100 extends D1 {}
+class E1101 extends D2 {}
+class E1102 extends D1 {}
+class E1103 extends D2 {}
+class E1104 extends D1 {}
+class E1105 extends D2 {}
+class E1106 extends D1 {}
+class E1107 extends D2 {}
+class E1108 extends D1 {}
+class E1109 extends D2 {}
+class E1110 extends D1 {}
+class E1111 extends D2 {}
+class E1112 extends D1 {}
+class E1113 extends D2 {}
+class E1114 extends D1 {}
+class E1115 extends D2 {}
+class E1116 extends D1 {}
+class E1117 extends D2 {}
+class E1118 extends D1 {}
+class E1119 extends D2 {}
+class E1120 extends D1 {}
+class E1121 extends D2 {}
+class E1122 extends D1 {}
+class E1123 extends D2 {}
+class E1124 extends D1 {}
+class E1125 extends D2 {}
+class E1126 extends D1 {}
+class E1127 extends D2 {}
+class E1128 extends D1 {}
+class E1129 extends D2 {}
+class E1130 extends D1 {}
+class E1131 extends D2 {}
+class E1132 extends D1 {}
+class E1133 extends D2 {}
+class E1134 extends D1 {}
+class E1135 extends D2 {}
+class E1136 extends D1 {}
+class E1137 extends D2 {}
+class E1138 extends D1 {}
+class E1139 extends D2 {}
+class E1140 extends D1 {}
+class E1141 extends D2 {}
+class E1142 extends D1 {}
+class E1143 extends D2 {}
+class E1144 extends D1 {}
+class E1145 extends D2 {}
+class E1146 extends D1 {}
+class E1147 extends D2 {}
+class E1148 extends D1 {}
+class E1149 extends D2 {}
+class E1150 extends D1 {}
+class E1151 extends D2 {}
+class E1152 extends D1 {}
+class E1153 extends D2 {}
+class E1154 extends D1 {}
+class E1155 extends D2 {}
+class E1156 extends D1 {}
+class E1157 extends D2 {}
+class E1158 extends D1 {}
+class E1159 extends D2 {}
+class E1160 extends D1 {}
+class E1161 extends D2 {}
+class E1162 extends D1 {}
+class E1163 extends D2 {}
+class E1164 extends D1 {}
+class E1165 extends D2 {}
+class E1166 extends D1 {}
+class E1167 extends D2 {}
+class E1168 extends D1 {}
+class E1169 extends D2 {}
+class E1170 extends D1 {}
+class E1171 extends D2 {}
+class E1172 extends D1 {}
+class E1173 extends D2 {}
+class E1174 extends D1 {}
+class E1175 extends D2 {}
+class E1176 extends D1 {}
+class E1177 extends D2 {}
+class E1178 extends D1 {}
+class E1179 extends D2 {}
+class E1180 extends D1 {}
+class E1181 extends D2 {}
+class E1182 extends D1 {}
+class E1183 extends D2 {}
+class E1184 extends D1 {}
+class E1185 extends D2 {}
+class E1186 extends D1 {}
+class E1187 extends D2 {}
+class E1188 extends D1 {}
+class E1189 extends D2 {}
+class E1190 extends D1 {}
+class E1191 extends D2 {}
+class E1192 extends D1 {}
+class E1193 extends D2 {}
+class E1194 extends D1 {}
+class E1195 extends D2 {}
+class E1196 extends D1 {}
+class E1197 extends D2 {}
+class E1198 extends D1 {}
+class E1199 extends D2 {}
+class E1200 extends D1 {}
+class F1 extends E1199 {}
+class F2 extends E1199 {}
+class F3 extends E1200 {}
+
+// Classes that are not referenced directly are required in order
+// to force their parent's class SubtypeCheck status into Assigned|Overflowed.
+//
+// TODO: manually initialize every (leaf) class to ensure SubtypeCheck are Assigned.
+
+public class Main {
+ public static void main(String[] args) {
+ String yes = "Yes";
+ String no = "No";
+
+ A a = new A();
+ A c1 = new C1();
+ A c2 = new C2();
+ A e1 = new E1199();
+ A e2 = new E1200();
+ A f1 = new F1();
+ A f2 = new F3();
+
+ expectTrue(f1 instanceof E1199);
+ expectFalse(f1 instanceof E1200);
+ expectFalse(f2 instanceof E1199);
+ expectTrue(f2 instanceof E1200);
+
+ expectFalse(e1 instanceof F1);
+ expectFalse(e1 instanceof F3);
+ expectFalse(e2 instanceof F1);
+ expectFalse(e2 instanceof F3);
+
+ expectFalse(e1 instanceof C1);
+ expectTrue(e2 instanceof C1);
+ expectTrue(e1 instanceof C2);
+ expectFalse(e2 instanceof C2);
+
+ expectFalse(c1 instanceof F1);
+ expectFalse(c1 instanceof F3);
+ expectFalse(c2 instanceof F1);
+ expectFalse(c2 instanceof F3);
+
+ System.out.println("passed");
+ }
+
+ private static void expectTrue(boolean value) {
+ if (!value) {
+ throw new Error("Expected True");
+ }
+ }
+
+ private static void expectFalse(boolean value) {
+ if (value) {
+ throw new Error("Expected False");
+ }
+ }
+}