Merge "ART: Refactor dex2oat"
diff --git a/build/Android.common.mk b/build/Android.common.mk
index 39a734d..39e78fa 100644
--- a/build/Android.common.mk
+++ b/build/Android.common.mk
@@ -42,10 +42,17 @@
     $(error Do not know what to do with this multi-target configuration!)
   endif
 else
-  ART_PHONY_TEST_TARGET_SUFFIX := 32
-  2ND_ART_PHONY_TEST_TARGET_SUFFIX :=
-  ART_TARGET_ARCH_32 := $(TARGET_ARCH)
-  ART_TARGET_ARCH_64 :=
+  ifneq ($(filter %64,$(TARGET_ARCH)),)
+    ART_PHONY_TEST_TARGET_SUFFIX := 64
+    2ND_ART_PHONY_TEST_TARGET_SUFFIX :=
+    ART_TARGET_ARCH_32 :=
+    ART_TARGET_ARCH_64 := $(TARGET_ARCH)
+  else
+    ART_PHONY_TEST_TARGET_SUFFIX := 32
+    2ND_ART_PHONY_TEST_TARGET_SUFFIX :=
+    ART_TARGET_ARCH_32 := $(TARGET_ARCH)
+    ART_TARGET_ARCH_64 :=
+  endif
 endif
 
 ART_HOST_SHLIB_EXTENSION := $(HOST_SHLIB_SUFFIX)
diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index 75665b6..56e95b8 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -76,6 +76,7 @@
   runtime/barrier_test.cc \
   runtime/base/bit_field_test.cc \
   runtime/base/bit_vector_test.cc \
+  runtime/base/hash_set_test.cc \
   runtime/base/hex_dump_test.cc \
   runtime/base/histogram_test.cc \
   runtime/base/mutex_test.cc \
diff --git a/compiler/dex/quick/arm64/int_arm64.cc b/compiler/dex/quick/arm64/int_arm64.cc
index 965759b..fc72e02 100644
--- a/compiler/dex/quick/arm64/int_arm64.cc
+++ b/compiler/dex/quick/arm64/int_arm64.cc
@@ -483,7 +483,6 @@
       } else {
         reconstructed_imm = base + 1;
       }
-      DCHECK_EQ(reconstructed_imm, magic_table[lit].magic64) << " for literal " << lit;
     }
 
     // Load the magic constant in two instructions.
diff --git a/compiler/dex/quick/arm64/utility_arm64.cc b/compiler/dex/quick/arm64/utility_arm64.cc
index 47ccc46..fcd69ec 100644
--- a/compiler/dex/quick/arm64/utility_arm64.cc
+++ b/compiler/dex/quick/arm64/utility_arm64.cc
@@ -345,7 +345,7 @@
   case Instruction::SUB_INT_2ADDR:
     // The code below is consistent with the implementation of OpRegRegImm().
     {
-      int32_t abs_value = std::abs(value);
+      uint32_t abs_value = (value == INT_MIN) ? value : std::abs(value);
       if (abs_value < 0x1000) {
         return true;
       } else if ((abs_value & UINT64_C(0xfff)) == 0 && ((abs_value >> 12) < 0x1000)) {
@@ -810,7 +810,7 @@
 LIR* Arm64Mir2Lir::OpRegRegImm64(OpKind op, RegStorage r_dest, RegStorage r_src1, int64_t value) {
   LIR* res;
   bool neg = (value < 0);
-  int64_t abs_value = (neg) ? -value : value;
+  uint64_t abs_value = (neg & !(value == LLONG_MIN)) ? -value : value;
   A64Opcode opcode = kA64Brk1d;
   A64Opcode alt_opcode = kA64Brk1d;
   bool is_logical = false;
@@ -943,7 +943,7 @@
   A64Opcode neg_opcode = kA64Brk1d;
   bool shift;
   bool neg = (value < 0);
-  uint64_t abs_value = (neg) ? -value : value;
+  uint64_t abs_value = (neg & !(value == LLONG_MIN)) ? -value : value;
 
   if (LIKELY(abs_value < 0x1000)) {
     // abs_value is a 12-bit immediate.
diff --git a/compiler/image_writer.cc b/compiler/image_writer.cc
index 6584d53..cf2cddb 100644
--- a/compiler/image_writer.cc
+++ b/compiler/image_writer.cc
@@ -324,7 +324,8 @@
 
   // Remove the undesired classes from the class roots.
   for (const std::string& it : non_image_classes) {
-    class_linker->RemoveClass(it.c_str(), NULL);
+    bool result = class_linker->RemoveClass(it.c_str(), NULL);
+    DCHECK(result);
   }
 
   // Clear references to removed classes from the DexCaches.
diff --git a/compiler/optimizing/builder.cc b/compiler/optimizing/builder.cc
index 64fb764..05213a1 100644
--- a/compiler/optimizing/builder.cc
+++ b/compiler/optimizing/builder.cc
@@ -64,10 +64,6 @@
   size_t index_;
 };
 
-static bool IsTypeSupported(Primitive::Type type) {
-  return type != Primitive::kPrimFloat && type != Primitive::kPrimDouble;
-}
-
 void HGraphBuilder::InitializeLocals(uint16_t count) {
   graph_->SetNumberOfVRegs(count);
   locals_.SetSize(count);
@@ -78,10 +74,10 @@
   }
 }
 
-bool HGraphBuilder::InitializeParameters(uint16_t number_of_parameters) {
+void HGraphBuilder::InitializeParameters(uint16_t number_of_parameters) {
   // dex_compilation_unit_ is null only when unit testing.
   if (dex_compilation_unit_ == nullptr) {
-    return true;
+    return;
   }
 
   graph_->SetNumberOfInVRegs(number_of_parameters);
@@ -116,7 +112,6 @@
       parameter_index++;
     }
   }
-  return true;
 }
 
 template<typename T>
@@ -195,9 +190,7 @@
     }
   }
 
-  if (!InitializeParameters(code_item.ins_size_)) {
-    return nullptr;
-  }
+  InitializeParameters(code_item.ins_size_);
 
   size_t dex_offset = 0;
   while (code_ptr < code_end) {
@@ -456,9 +449,6 @@
   }
 
   Primitive::Type field_type = resolved_field->GetTypeAsPrimitiveType();
-  if (!IsTypeSupported(field_type)) {
-    return false;
-  }
 
   HInstruction* object = LoadLocal(obj_reg, Primitive::kPrimNot);
   current_block_->AddInstruction(new (arena_) HNullCheck(object, dex_offset));
@@ -516,10 +506,6 @@
     return false;
   }
 
-  if (!IsTypeSupported(field_type)) {
-    return false;
-  }
-
   HLoadClass* constant = new (arena_) HLoadClass(
       storage_index, is_referrers_class, dex_offset);
   current_block_->AddInstruction(constant);
@@ -574,8 +560,6 @@
   uint8_t array_reg = instruction.VRegB_23x();
   uint8_t index_reg = instruction.VRegC_23x();
 
-  DCHECK(IsTypeSupported(anticipated_type));
-
   // We need one temporary for the null check, one for the index, and one for the length.
   Temporaries temps(graph_, 3);
 
@@ -1276,7 +1260,7 @@
         return false;
       }
       current_block_->AddInstruction(
-          new (arena_) HLoadClass(instruction.VRegB_21c(), is_referrers_class, dex_offset));
+          new (arena_) HLoadClass(type_index, is_referrers_class, dex_offset));
       UpdateLocal(instruction.VRegA_21c(), current_block_->GetLastInstruction());
       break;
     }
@@ -1298,6 +1282,29 @@
       break;
     }
 
+    case Instruction::INSTANCE_OF: {
+      uint16_t type_index = instruction.VRegC_22c();
+      bool type_known_final;
+      bool type_known_abstract;
+      bool is_referrers_class;
+      bool can_access = compiler_driver_->CanAccessTypeWithoutChecks(
+          dex_compilation_unit_->GetDexMethodIndex(), *dex_file_, type_index,
+          &type_known_final, &type_known_abstract, &is_referrers_class);
+      if (!can_access) {
+        return false;
+      }
+      HInstruction* object = LoadLocal(instruction.VRegB_22c(), Primitive::kPrimNot);
+      HLoadClass* cls = new (arena_) HLoadClass(type_index, is_referrers_class, dex_offset);
+      current_block_->AddInstruction(cls);
+      // The class needs a temporary before being used by the type check.
+      Temporaries temps(graph_, 1);
+      temps.Add(cls);
+      current_block_->AddInstruction(
+          new (arena_) HTypeCheck(object, cls, type_known_final, dex_offset));
+      UpdateLocal(instruction.VRegA_22c(), current_block_->GetLastInstruction());
+      break;
+    }
+
     default:
       return false;
   }
diff --git a/compiler/optimizing/builder.h b/compiler/optimizing/builder.h
index 030f45b..09c9a51 100644
--- a/compiler/optimizing/builder.h
+++ b/compiler/optimizing/builder.h
@@ -93,10 +93,7 @@
   void UpdateLocal(int register_index, HInstruction* instruction) const;
   HInstruction* LoadLocal(int register_index, Primitive::Type type) const;
   void PotentiallyAddSuspendCheck(int32_t target_offset, uint32_t dex_offset);
-
-  // Temporarily returns whether the compiler supports the parameters
-  // of the method.
-  bool InitializeParameters(uint16_t number_of_parameters);
+  void InitializeParameters(uint16_t number_of_parameters);
 
   template<typename T>
   void Unop_12x(const Instruction& instruction, Primitive::Type type);
diff --git a/compiler/optimizing/code_generator.cc b/compiler/optimizing/code_generator.cc
index c75980d..0dfbad2 100644
--- a/compiler/optimizing/code_generator.cc
+++ b/compiler/optimizing/code_generator.cc
@@ -281,16 +281,22 @@
       HInstruction* previous = instruction->GetPrevious();
       Location temp_location = GetTemporaryLocation(instruction->AsTemporary());
       Move(previous, temp_location, instruction);
-      previous->GetLocations()->SetOut(temp_location);
     }
     return;
   }
   AllocateRegistersLocally(instruction);
   for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) {
     Location location = instruction->GetLocations()->InAt(i);
+    HInstruction* input = instruction->InputAt(i);
     if (location.IsValid()) {
       // Move the input to the desired location.
-      Move(instruction->InputAt(i), location, instruction);
+      if (input->GetNext()->IsTemporary()) {
+        // If the input was stored in a temporary, use that temporary to
+        // perform the move.
+        Move(input->GetNext(), location, instruction);
+      } else {
+        Move(input, location, instruction);
+      }
     }
   }
 }
diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
index fef7f0e..8e6f8ea 100644
--- a/compiler/optimizing/code_generator_arm.cc
+++ b/compiler/optimizing/code_generator_arm.cc
@@ -212,8 +212,9 @@
     arm_codegen->InvokeRuntime(entry_point_offset, at_, dex_pc_);
 
     // Move the class to the desired location.
-    if (locations->Out().IsValid()) {
-      DCHECK(!locations->GetLiveRegisters()->ContainsCoreRegister(locations->Out().reg()));
+    Location out = locations->Out();
+    if (out.IsValid()) {
+      DCHECK(out.IsRegister() && !locations->GetLiveRegisters()->ContainsCoreRegister(out.reg()));
       arm_codegen->Move32(locations->Out(), Location::RegisterLocation(R0));
     }
     codegen->RestoreLiveRegisters(locations);
@@ -266,6 +267,49 @@
   DISALLOW_COPY_AND_ASSIGN(LoadStringSlowPathARM);
 };
 
+class TypeCheckSlowPathARM : public SlowPathCodeARM {
+ public:
+  explicit TypeCheckSlowPathARM(HTypeCheck* instruction, Location object_class)
+      : instruction_(instruction),
+        object_class_(object_class) {}
+
+  virtual void EmitNativeCode(CodeGenerator* codegen) OVERRIDE {
+    LocationSummary* locations = instruction_->GetLocations();
+    DCHECK(!locations->GetLiveRegisters()->ContainsCoreRegister(locations->Out().reg()));
+
+    CodeGeneratorARM* arm_codegen = down_cast<CodeGeneratorARM*>(codegen);
+    __ Bind(GetEntryLabel());
+    codegen->SaveLiveRegisters(locations);
+
+    // We're moving two locations to locations that could overlap, so we need a parallel
+    // move resolver.
+    InvokeRuntimeCallingConvention calling_convention;
+    MoveOperands move1(locations->InAt(1),
+                       Location::RegisterLocation(calling_convention.GetRegisterAt(0)),
+                       nullptr);
+    MoveOperands move2(object_class_,
+                       Location::RegisterLocation(calling_convention.GetRegisterAt(1)),
+                       nullptr);
+    HParallelMove parallel_move(codegen->GetGraph()->GetArena());
+    parallel_move.AddMove(&move1);
+    parallel_move.AddMove(&move2);
+    arm_codegen->GetMoveResolver()->EmitNativeCode(&parallel_move);
+
+    arm_codegen->InvokeRuntime(
+        QUICK_ENTRY_POINT(pInstanceofNonTrivial), instruction_, instruction_->GetDexPc());
+    arm_codegen->Move32(locations->Out(), Location::RegisterLocation(R0));
+
+    codegen->RestoreLiveRegisters(locations);
+    __ b(GetExitLabel());
+  }
+
+ private:
+  HTypeCheck* const instruction_;
+  const Location object_class_;
+
+  DISALLOW_COPY_AND_ASSIGN(TypeCheckSlowPathARM);
+};
+
 #undef __
 
 #undef __
@@ -766,6 +810,9 @@
       default:
         LOG(FATAL) << "Unexpected type " << instruction->GetType();
     }
+  } else if (instruction->IsTemporary()) {
+    Location temp_location = GetTemporaryLocation(instruction->AsTemporary());
+    Move32(location, temp_location);
   } else {
     DCHECK((instruction->GetNext() == move_for) || instruction->GetNext()->IsTemporary());
     switch (instruction->GetType()) {
@@ -1826,10 +1873,18 @@
       break;
     }
 
-    case Primitive::kPrimFloat:
-    case Primitive::kPrimDouble:
-      LOG(FATAL) << "Unimplemented register type " << field_type;
-      UNREACHABLE();
+    case Primitive::kPrimFloat: {
+      SRegister value = locations->InAt(1).As<SRegister>();
+      __ StoreSToOffset(value, obj, offset);
+      break;
+    }
+
+    case Primitive::kPrimDouble: {
+      DRegister value = FromLowSToD(locations->InAt(1).AsFpuRegisterPairLow<SRegister>());
+      __ StoreDToOffset(value, obj, offset);
+      break;
+    }
+
     case Primitive::kPrimVoid:
       LOG(FATAL) << "Unreachable type " << field_type;
       UNREACHABLE();
@@ -1887,10 +1942,18 @@
       break;
     }
 
-    case Primitive::kPrimFloat:
-    case Primitive::kPrimDouble:
-      LOG(FATAL) << "Unimplemented register type " << instruction->GetType();
-      UNREACHABLE();
+    case Primitive::kPrimFloat: {
+      SRegister out = locations->Out().As<SRegister>();
+      __ LoadSFromOffset(out, obj, offset);
+      break;
+    }
+
+    case Primitive::kPrimDouble: {
+      DRegister out = FromLowSToD(locations->Out().AsFpuRegisterPairLow<SRegister>());
+      __ LoadDFromOffset(out, obj, offset);
+      break;
+    }
+
     case Primitive::kPrimVoid:
       LOG(FATAL) << "Unreachable type " << instruction->GetType();
       UNREACHABLE();
@@ -2424,10 +2487,18 @@
       break;
     }
 
-    case Primitive::kPrimFloat:
-    case Primitive::kPrimDouble:
-      LOG(FATAL) << "Unimplemented register type " << instruction->GetType();
-      UNREACHABLE();
+    case Primitive::kPrimFloat: {
+      SRegister out = locations->Out().As<SRegister>();
+      __ LoadSFromOffset(out, cls, offset);
+      break;
+    }
+
+    case Primitive::kPrimDouble: {
+      DRegister out = FromLowSToD(locations->Out().AsFpuRegisterPairLow<SRegister>());
+      __ LoadDFromOffset(out, cls, offset);
+      break;
+    }
+
     case Primitive::kPrimVoid:
       LOG(FATAL) << "Unreachable type " << instruction->GetType();
       UNREACHABLE();
@@ -2486,10 +2557,18 @@
       break;
     }
 
-    case Primitive::kPrimFloat:
-    case Primitive::kPrimDouble:
-      LOG(FATAL) << "Unimplemented register type " << field_type;
-      UNREACHABLE();
+    case Primitive::kPrimFloat: {
+      SRegister value = locations->InAt(1).As<SRegister>();
+      __ StoreSToOffset(value, cls, offset);
+      break;
+    }
+
+    case Primitive::kPrimDouble: {
+      DRegister value = FromLowSToD(locations->InAt(1).AsFpuRegisterPairLow<SRegister>());
+      __ StoreDToOffset(value, cls, offset);
+      break;
+    }
+
     case Primitive::kPrimVoid:
       LOG(FATAL) << "Unreachable type " << field_type;
       UNREACHABLE();
@@ -2542,5 +2621,54 @@
       QUICK_ENTRY_POINT(pDeliverException), instruction, instruction->GetDexPc());
 }
 
+void LocationsBuilderARM::VisitTypeCheck(HTypeCheck* instruction) {
+  LocationSummary::CallKind call_kind = instruction->IsClassFinal()
+      ? LocationSummary::kNoCall
+      : LocationSummary::kCallOnSlowPath;
+  LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction, call_kind);
+  locations->SetInAt(0, Location::RequiresRegister());
+  locations->SetInAt(1, Location::RequiresRegister());
+  locations->SetOut(Location::RequiresRegister());
+}
+
+void InstructionCodeGeneratorARM::VisitTypeCheck(HTypeCheck* instruction) {
+  LocationSummary* locations = instruction->GetLocations();
+  Register obj = locations->InAt(0).As<Register>();
+  Register cls = locations->InAt(1).As<Register>();
+  Register out = locations->Out().As<Register>();
+  uint32_t class_offset = mirror::Object::ClassOffset().Int32Value();
+  Label done, zero;
+  SlowPathCodeARM* slow_path = nullptr;
+
+  // Return 0 if `obj` is null.
+  // TODO: avoid this check if we know obj is not null.
+  __ cmp(obj, ShifterOperand(0));
+  __ b(&zero, EQ);
+  // Compare the class of `obj` with `cls`.
+  __ LoadFromOffset(kLoadWord, out, obj, class_offset);
+  __ cmp(out, ShifterOperand(cls));
+  if (instruction->IsClassFinal()) {
+    // Classes must be equal for the instanceof to succeed.
+    __ b(&zero, NE);
+    __ LoadImmediate(out, 1);
+    __ b(&done);
+  } else {
+    // If the classes are not equal, we go into a slow path.
+    DCHECK(locations->OnlyCallsOnSlowPath());
+    slow_path = new (GetGraph()->GetArena()) TypeCheckSlowPathARM(
+        instruction, Location::RegisterLocation(out));
+    codegen_->AddSlowPath(slow_path);
+    __ b(slow_path->GetEntryLabel(), NE);
+    __ LoadImmediate(out, 1);
+    __ b(&done);
+  }
+  __ Bind(&zero);
+  __ LoadImmediate(out, 0);
+  if (slow_path != nullptr) {
+    __ Bind(slow_path->GetExitLabel());
+  }
+  __ Bind(&done);
+}
+
 }  // namespace arm
 }  // namespace art
diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc
index 1be5717..f37c5db 100644
--- a/compiler/optimizing/code_generator_arm64.cc
+++ b/compiler/optimizing/code_generator_arm64.cc
@@ -413,7 +413,9 @@
       __ Mov(temp, value);
       __ Str(temp, StackOperandFrom(location));
     }
-
+  } else if (instruction->IsTemporary()) {
+    Location temp_location = GetTemporaryLocation(instruction->AsTemporary());
+    MoveHelper(location, temp_location, type);
   } else if (instruction->IsLoadLocal()) {
     uint32_t stack_slot = GetStackSlot(instruction->AsLoadLocal()->GetLocal());
     switch (type) {
@@ -548,6 +550,7 @@
   M(StaticFieldGet)                                        \
   M(StaticFieldSet)                                        \
   M(Throw)                                                 \
+  M(TypeCheck)                                             \
   M(TypeConversion)                                        \
 
 #define UNIMPLEMENTED_INSTRUCTION_BREAK_CODE(name) name##UnimplementedInstructionBreakCode
@@ -582,7 +585,7 @@
     case Primitive::kPrimLong: {
       locations->SetInAt(0, Location::RequiresRegister());
       locations->SetInAt(1, Location::RegisterOrConstant(instr->InputAt(1)));
-      locations->SetOut(Location::RequiresRegister());
+      locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap);
       break;
     }
     case Primitive::kPrimBoolean:
@@ -636,7 +639,7 @@
 void LocationsBuilderARM64::VisitArrayLength(HArrayLength* instruction) {
   LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction);
   locations->SetInAt(0, Location::RequiresRegister());
-  locations->SetOut(Location::RequiresRegister());
+  locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap);
 }
 
 void InstructionCodeGeneratorARM64::VisitArrayLength(HArrayLength* instruction) {
@@ -649,7 +652,7 @@
       new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kNoCall);
   locations->SetInAt(0, Location::RequiresRegister());
   locations->SetInAt(1, Location::RegisterOrConstant(instruction->InputAt(1)));
-  locations->SetOut(Location::RequiresRegister());
+  locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap);
 }
 
 void InstructionCodeGeneratorARM64::VisitCompare(HCompare* instruction) {
@@ -679,7 +682,7 @@
   locations->SetInAt(0, Location::RequiresRegister());
   locations->SetInAt(1, Location::RegisterOrConstant(instruction->InputAt(1)));
   if (instruction->NeedsMaterialization()) {
-    locations->SetOut(Location::RequiresRegister());
+    locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap);
   }
 }
 
@@ -785,7 +788,7 @@
 void LocationsBuilderARM64::VisitInstanceFieldGet(HInstanceFieldGet* instruction) {
   LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction);
   locations->SetInAt(0, Location::RequiresRegister());
-  locations->SetOut(Location::RequiresRegister());
+  locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap);
 }
 
 void InstructionCodeGeneratorARM64::VisitInstanceFieldGet(HInstanceFieldGet* instruction) {
@@ -1003,7 +1006,7 @@
     case Primitive::kPrimLong:
       locations->SetInAt(0, Location::RequiresRegister());
       locations->SetInAt(1, Location::RequiresRegister());
-      locations->SetOut(Location::RequiresRegister());
+      locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap);
       break;
 
     case Primitive::kPrimFloat:
@@ -1059,7 +1062,7 @@
 void LocationsBuilderARM64::VisitNot(HNot* instruction) {
   LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction);
   locations->SetInAt(0, Location::RequiresRegister());
-  locations->SetOut(Location::RequiresRegister());
+  locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap);
 }
 
 void InstructionCodeGeneratorARM64::VisitNot(HNot* instruction) {
diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc
index 127ddbe..548d699 100644
--- a/compiler/optimizing/code_generator_x86.cc
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -241,10 +241,12 @@
     codegen->RecordPcInfo(at_, dex_pc_);
 
     // Move the class to the desired location.
-    if (locations->Out().IsValid()) {
-      DCHECK(!locations->GetLiveRegisters()->ContainsCoreRegister(locations->Out().reg()));
-      x86_codegen->Move32(locations->Out(), Location::RegisterLocation(EAX));
+    Location out = locations->Out();
+    if (out.IsValid()) {
+      DCHECK(out.IsRegister() && !locations->GetLiveRegisters()->ContainsCoreRegister(out.reg()));
+      x86_codegen->Move32(out, Location::RegisterLocation(EAX));
     }
+
     codegen->RestoreLiveRegisters(locations);
     __ jmp(GetExitLabel());
   }
@@ -266,6 +268,49 @@
   DISALLOW_COPY_AND_ASSIGN(LoadClassSlowPathX86);
 };
 
+class TypeCheckSlowPathX86 : public SlowPathCodeX86 {
+ public:
+  TypeCheckSlowPathX86(HTypeCheck* instruction, Location object_class)
+      : instruction_(instruction),
+        object_class_(object_class) {}
+
+  virtual void EmitNativeCode(CodeGenerator* codegen) OVERRIDE {
+    LocationSummary* locations = instruction_->GetLocations();
+    DCHECK(!locations->GetLiveRegisters()->ContainsCoreRegister(locations->Out().reg()));
+
+    CodeGeneratorX86* x86_codegen = down_cast<CodeGeneratorX86*>(codegen);
+    __ Bind(GetEntryLabel());
+    codegen->SaveLiveRegisters(locations);
+
+    // We're moving two locations to locations that could overlap, so we need a parallel
+    // move resolver.
+    InvokeRuntimeCallingConvention calling_convention;
+    MoveOperands move1(locations->InAt(1),
+                       Location::RegisterLocation(calling_convention.GetRegisterAt(0)),
+                       nullptr);
+    MoveOperands move2(object_class_,
+                       Location::RegisterLocation(calling_convention.GetRegisterAt(1)),
+                       nullptr);
+    HParallelMove parallel_move(codegen->GetGraph()->GetArena());
+    parallel_move.AddMove(&move1);
+    parallel_move.AddMove(&move2);
+    x86_codegen->GetMoveResolver()->EmitNativeCode(&parallel_move);
+
+    __ fs()->call(Address::Absolute(QUICK_ENTRYPOINT_OFFSET(kX86WordSize, pInstanceofNonTrivial)));
+    codegen->RecordPcInfo(instruction_, instruction_->GetDexPc());
+    x86_codegen->Move32(locations->Out(), Location::RegisterLocation(EAX));
+    codegen->RestoreLiveRegisters(locations);
+
+    __ jmp(GetExitLabel());
+  }
+
+ private:
+  HTypeCheck* const instruction_;
+  const Location object_class_;
+
+  DISALLOW_COPY_AND_ASSIGN(TypeCheckSlowPathX86);
+};
+
 #undef __
 #define __ reinterpret_cast<X86Assembler*>(GetAssembler())->
 
@@ -623,6 +668,9 @@
       DCHECK(location.IsConstant());
       DCHECK_EQ(location.GetConstant(), instruction);
     }
+  } else if (instruction->IsTemporary()) {
+    Location temp_location = GetTemporaryLocation(instruction->AsTemporary());
+    Move32(location, temp_location);
   } else if (instruction->IsLoadLocal()) {
     int slot = GetStackSlot(instruction->AsLoadLocal()->GetLocal());
     switch (instruction->GetType()) {
@@ -1844,10 +1892,18 @@
       break;
     }
 
-    case Primitive::kPrimFloat:
-    case Primitive::kPrimDouble:
-      LOG(FATAL) << "Unimplemented register type " << field_type;
-      UNREACHABLE();
+    case Primitive::kPrimFloat: {
+      XmmRegister value = locations->InAt(1).As<XmmRegister>();
+      __ movss(Address(obj, offset), value);
+      break;
+    }
+
+    case Primitive::kPrimDouble: {
+      XmmRegister value = locations->InAt(1).As<XmmRegister>();
+      __ movsd(Address(obj, offset), value);
+      break;
+    }
+
     case Primitive::kPrimVoid:
       LOG(FATAL) << "Unreachable type " << field_type;
       UNREACHABLE();
@@ -1917,10 +1973,18 @@
       break;
     }
 
-    case Primitive::kPrimFloat:
-    case Primitive::kPrimDouble:
-      LOG(FATAL) << "Unimplemented register type " << instruction->GetType();
-      UNREACHABLE();
+    case Primitive::kPrimFloat: {
+      XmmRegister out = locations->Out().As<XmmRegister>();
+      __ movss(out, Address(obj, offset));
+      break;
+    }
+
+    case Primitive::kPrimDouble: {
+      XmmRegister out = locations->Out().As<XmmRegister>();
+      __ movsd(out, Address(obj, offset));
+      break;
+    }
+
     case Primitive::kPrimVoid:
       LOG(FATAL) << "Unreachable type " << instruction->GetType();
       UNREACHABLE();
@@ -2508,10 +2572,18 @@
       break;
     }
 
-    case Primitive::kPrimFloat:
-    case Primitive::kPrimDouble:
-      LOG(FATAL) << "Unimplemented register type " << instruction->GetType();
-      UNREACHABLE();
+    case Primitive::kPrimFloat: {
+      XmmRegister out = locations->Out().As<XmmRegister>();
+      __ movss(out, Address(cls, offset));
+      break;
+    }
+
+    case Primitive::kPrimDouble: {
+      XmmRegister out = locations->Out().As<XmmRegister>();
+      __ movsd(out, Address(cls, offset));
+      break;
+    }
+
     case Primitive::kPrimVoid:
       LOG(FATAL) << "Unreachable type " << instruction->GetType();
       UNREACHABLE();
@@ -2583,10 +2655,18 @@
       break;
     }
 
-    case Primitive::kPrimFloat:
-    case Primitive::kPrimDouble:
-      LOG(FATAL) << "Unimplemented register type " << field_type;
-      UNREACHABLE();
+    case Primitive::kPrimFloat: {
+      XmmRegister value = locations->InAt(1).As<XmmRegister>();
+      __ movss(Address(cls, offset), value);
+      break;
+    }
+
+    case Primitive::kPrimDouble: {
+      XmmRegister value = locations->InAt(1).As<XmmRegister>();
+      __ movsd(Address(cls, offset), value);
+      break;
+    }
+
     case Primitive::kPrimVoid:
       LOG(FATAL) << "Unreachable type " << field_type;
       UNREACHABLE();
@@ -2636,5 +2716,60 @@
   codegen_->RecordPcInfo(instruction, instruction->GetDexPc());
 }
 
+void LocationsBuilderX86::VisitTypeCheck(HTypeCheck* instruction) {
+  LocationSummary::CallKind call_kind = instruction->IsClassFinal()
+      ? LocationSummary::kNoCall
+      : LocationSummary::kCallOnSlowPath;
+  LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction, call_kind);
+  locations->SetInAt(0, Location::RequiresRegister());
+  locations->SetInAt(1, Location::Any());
+  locations->SetOut(Location::RequiresRegister());
+}
+
+void InstructionCodeGeneratorX86::VisitTypeCheck(HTypeCheck* instruction) {
+  LocationSummary* locations = instruction->GetLocations();
+  Register obj = locations->InAt(0).As<Register>();
+  Location cls = locations->InAt(1);
+  Register out = locations->Out().As<Register>();
+  uint32_t class_offset = mirror::Object::ClassOffset().Int32Value();
+  Label done, zero;
+  SlowPathCodeX86* slow_path = nullptr;
+
+  // Return 0 if `obj` is null.
+  // TODO: avoid this check if we know obj is not null.
+  __ testl(obj, obj);
+  __ j(kEqual, &zero);
+  __ movl(out, Address(obj, class_offset));
+  // Compare the class of `obj` with `cls`.
+  if (cls.IsRegister()) {
+    __ cmpl(out, cls.As<Register>());
+  } else {
+    DCHECK(cls.IsStackSlot()) << cls;
+    __ cmpl(out, Address(ESP, cls.GetStackIndex()));
+  }
+
+  if (instruction->IsClassFinal()) {
+    // Classes must be equal for the instanceof to succeed.
+    __ j(kNotEqual, &zero);
+    __ movl(out, Immediate(1));
+    __ jmp(&done);
+  } else {
+    // If the classes are not equal, we go into a slow path.
+    DCHECK(locations->OnlyCallsOnSlowPath());
+    slow_path = new (GetGraph()->GetArena()) TypeCheckSlowPathX86(
+        instruction, Location::RegisterLocation(out));
+    codegen_->AddSlowPath(slow_path);
+    __ j(kNotEqual, slow_path->GetEntryLabel());
+    __ movl(out, Immediate(1));
+    __ jmp(&done);
+  }
+  __ Bind(&zero);
+  __ movl(out, Immediate(0));
+  if (slow_path != nullptr) {
+    __ Bind(slow_path->GetExitLabel());
+  }
+  __ Bind(&done);
+}
+
 }  // namespace x86
 }  // namespace art
diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc
index 8c0842c..b9891d6 100644
--- a/compiler/optimizing/code_generator_x86_64.cc
+++ b/compiler/optimizing/code_generator_x86_64.cc
@@ -224,10 +224,11 @@
           : QUICK_ENTRYPOINT_OFFSET(kX86_64WordSize, pInitializeType)) , true));
     codegen->RecordPcInfo(at_, dex_pc_);
 
+    Location out = locations->Out();
     // Move the class to the desired location.
-    if (locations->Out().IsValid()) {
-      DCHECK(!locations->GetLiveRegisters()->ContainsCoreRegister(locations->Out().reg()));
-      x64_codegen->Move(locations->Out(), Location::RegisterLocation(RAX));
+    if (out.IsValid()) {
+      DCHECK(out.IsRegister() && !locations->GetLiveRegisters()->ContainsCoreRegister(out.reg()));
+      x64_codegen->Move(out, Location::RegisterLocation(RAX));
     }
 
     codegen->RestoreLiveRegisters(locations);
@@ -281,6 +282,50 @@
   DISALLOW_COPY_AND_ASSIGN(LoadStringSlowPathX86_64);
 };
 
+class TypeCheckSlowPathX86_64 : public SlowPathCodeX86_64 {
+ public:
+  TypeCheckSlowPathX86_64(HTypeCheck* instruction, Location object_class)
+      : instruction_(instruction),
+        object_class_(object_class) {}
+
+  virtual void EmitNativeCode(CodeGenerator* codegen) OVERRIDE {
+    LocationSummary* locations = instruction_->GetLocations();
+    DCHECK(!locations->GetLiveRegisters()->ContainsCoreRegister(locations->Out().reg()));
+
+    CodeGeneratorX86_64* x64_codegen = down_cast<CodeGeneratorX86_64*>(codegen);
+    __ Bind(GetEntryLabel());
+    codegen->SaveLiveRegisters(locations);
+
+    // We're moving two locations to locations that could overlap, so we need a parallel
+    // move resolver.
+    InvokeRuntimeCallingConvention calling_convention;
+    MoveOperands move1(locations->InAt(1),
+                       Location::RegisterLocation(calling_convention.GetRegisterAt(0)),
+                       nullptr);
+    MoveOperands move2(object_class_,
+                       Location::RegisterLocation(calling_convention.GetRegisterAt(1)),
+                       nullptr);
+    HParallelMove parallel_move(codegen->GetGraph()->GetArena());
+    parallel_move.AddMove(&move1);
+    parallel_move.AddMove(&move2);
+    x64_codegen->GetMoveResolver()->EmitNativeCode(&parallel_move);
+
+    __ gs()->call(
+        Address::Absolute(QUICK_ENTRYPOINT_OFFSET(kX86_64WordSize, pInstanceofNonTrivial), true));
+    codegen->RecordPcInfo(instruction_, instruction_->GetDexPc());
+    x64_codegen->Move(locations->Out(), Location::RegisterLocation(RAX));
+
+    codegen->RestoreLiveRegisters(locations);
+    __ jmp(GetExitLabel());
+  }
+
+ private:
+  HTypeCheck* const instruction_;
+  const Location object_class_;
+
+  DISALLOW_COPY_AND_ASSIGN(TypeCheckSlowPathX86_64);
+};
+
 #undef __
 #define __ reinterpret_cast<X86_64Assembler*>(GetAssembler())->
 
@@ -559,6 +604,9 @@
       default:
         LOG(FATAL) << "Unexpected local type " << instruction->GetType();
     }
+  } else if (instruction->IsTemporary()) {
+    Location temp_location = GetTemporaryLocation(instruction->AsTemporary());
+    Move(location, temp_location);
   } else {
     DCHECK((instruction->GetNext() == move_for) || instruction->GetNext()->IsTemporary());
     switch (instruction->GetType()) {
@@ -1692,25 +1740,27 @@
 void InstructionCodeGeneratorX86_64::VisitInstanceFieldSet(HInstanceFieldSet* instruction) {
   LocationSummary* locations = instruction->GetLocations();
   CpuRegister obj = locations->InAt(0).As<CpuRegister>();
-  CpuRegister value = locations->InAt(1).As<CpuRegister>();
   size_t offset = instruction->GetFieldOffset().SizeValue();
   Primitive::Type field_type = instruction->GetFieldType();
 
   switch (field_type) {
     case Primitive::kPrimBoolean:
     case Primitive::kPrimByte: {
+      CpuRegister value = locations->InAt(1).As<CpuRegister>();
       __ movb(Address(obj, offset), value);
       break;
     }
 
     case Primitive::kPrimShort:
     case Primitive::kPrimChar: {
+      CpuRegister value = locations->InAt(1).As<CpuRegister>();
       __ movw(Address(obj, offset), value);
       break;
     }
 
     case Primitive::kPrimInt:
     case Primitive::kPrimNot: {
+      CpuRegister value = locations->InAt(1).As<CpuRegister>();
       __ movl(Address(obj, offset), value);
       if (field_type == Primitive::kPrimNot) {
         CpuRegister temp = locations->GetTemp(0).As<CpuRegister>();
@@ -1721,14 +1771,23 @@
     }
 
     case Primitive::kPrimLong: {
+      CpuRegister value = locations->InAt(1).As<CpuRegister>();
       __ movq(Address(obj, offset), value);
       break;
     }
 
-    case Primitive::kPrimFloat:
-    case Primitive::kPrimDouble:
-      LOG(FATAL) << "Unimplemented register type " << field_type;
-      UNREACHABLE();
+    case Primitive::kPrimFloat: {
+      XmmRegister value = locations->InAt(1).As<XmmRegister>();
+      __ movss(Address(obj, offset), value);
+      break;
+    }
+
+    case Primitive::kPrimDouble: {
+      XmmRegister value = locations->InAt(1).As<XmmRegister>();
+      __ movsd(Address(obj, offset), value);
+      break;
+    }
+
     case Primitive::kPrimVoid:
       LOG(FATAL) << "Unreachable type " << field_type;
       UNREACHABLE();
@@ -1745,45 +1804,58 @@
 void InstructionCodeGeneratorX86_64::VisitInstanceFieldGet(HInstanceFieldGet* instruction) {
   LocationSummary* locations = instruction->GetLocations();
   CpuRegister obj = locations->InAt(0).As<CpuRegister>();
-  CpuRegister out = locations->Out().As<CpuRegister>();
   size_t offset = instruction->GetFieldOffset().SizeValue();
 
   switch (instruction->GetType()) {
     case Primitive::kPrimBoolean: {
+      CpuRegister out = locations->Out().As<CpuRegister>();
       __ movzxb(out, Address(obj, offset));
       break;
     }
 
     case Primitive::kPrimByte: {
+      CpuRegister out = locations->Out().As<CpuRegister>();
       __ movsxb(out, Address(obj, offset));
       break;
     }
 
     case Primitive::kPrimShort: {
+      CpuRegister out = locations->Out().As<CpuRegister>();
       __ movsxw(out, Address(obj, offset));
       break;
     }
 
     case Primitive::kPrimChar: {
+      CpuRegister out = locations->Out().As<CpuRegister>();
       __ movzxw(out, Address(obj, offset));
       break;
     }
 
     case Primitive::kPrimInt:
     case Primitive::kPrimNot: {
+      CpuRegister out = locations->Out().As<CpuRegister>();
       __ movl(out, Address(obj, offset));
       break;
     }
 
     case Primitive::kPrimLong: {
+      CpuRegister out = locations->Out().As<CpuRegister>();
       __ movq(out, Address(obj, offset));
       break;
     }
 
-    case Primitive::kPrimFloat:
-    case Primitive::kPrimDouble:
-      LOG(FATAL) << "Unimplemented register type " << instruction->GetType();
-      UNREACHABLE();
+    case Primitive::kPrimFloat: {
+      XmmRegister out = locations->Out().As<XmmRegister>();
+      __ movss(out, Address(obj, offset));
+      break;
+    }
+
+    case Primitive::kPrimDouble: {
+      XmmRegister out = locations->Out().As<XmmRegister>();
+      __ movsd(out, Address(obj, offset));
+      break;
+    }
+
     case Primitive::kPrimVoid:
       LOG(FATAL) << "Unreachable type " << instruction->GetType();
       UNREACHABLE();
@@ -2460,45 +2532,58 @@
 void InstructionCodeGeneratorX86_64::VisitStaticFieldGet(HStaticFieldGet* instruction) {
   LocationSummary* locations = instruction->GetLocations();
   CpuRegister cls = locations->InAt(0).As<CpuRegister>();
-  CpuRegister out = locations->Out().As<CpuRegister>();
   size_t offset = instruction->GetFieldOffset().SizeValue();
 
   switch (instruction->GetType()) {
     case Primitive::kPrimBoolean: {
+      CpuRegister out = locations->Out().As<CpuRegister>();
       __ movzxb(out, Address(cls, offset));
       break;
     }
 
     case Primitive::kPrimByte: {
+      CpuRegister out = locations->Out().As<CpuRegister>();
       __ movsxb(out, Address(cls, offset));
       break;
     }
 
     case Primitive::kPrimShort: {
+      CpuRegister out = locations->Out().As<CpuRegister>();
       __ movsxw(out, Address(cls, offset));
       break;
     }
 
     case Primitive::kPrimChar: {
+      CpuRegister out = locations->Out().As<CpuRegister>();
       __ movzxw(out, Address(cls, offset));
       break;
     }
 
     case Primitive::kPrimInt:
     case Primitive::kPrimNot: {
+      CpuRegister out = locations->Out().As<CpuRegister>();
       __ movl(out, Address(cls, offset));
       break;
     }
 
     case Primitive::kPrimLong: {
+      CpuRegister out = locations->Out().As<CpuRegister>();
       __ movq(out, Address(cls, offset));
       break;
     }
 
-    case Primitive::kPrimFloat:
-    case Primitive::kPrimDouble:
-      LOG(FATAL) << "Unimplemented register type " << instruction->GetType();
-      UNREACHABLE();
+    case Primitive::kPrimFloat: {
+      XmmRegister out = locations->Out().As<XmmRegister>();
+      __ movss(out, Address(cls, offset));
+      break;
+    }
+
+    case Primitive::kPrimDouble: {
+      XmmRegister out = locations->Out().As<XmmRegister>();
+      __ movsd(out, Address(cls, offset));
+      break;
+    }
+
     case Primitive::kPrimVoid:
       LOG(FATAL) << "Unreachable type " << instruction->GetType();
       UNREACHABLE();
@@ -2522,25 +2607,27 @@
 void InstructionCodeGeneratorX86_64::VisitStaticFieldSet(HStaticFieldSet* instruction) {
   LocationSummary* locations = instruction->GetLocations();
   CpuRegister cls = locations->InAt(0).As<CpuRegister>();
-  CpuRegister value = locations->InAt(1).As<CpuRegister>();
   size_t offset = instruction->GetFieldOffset().SizeValue();
   Primitive::Type field_type = instruction->GetFieldType();
 
   switch (field_type) {
     case Primitive::kPrimBoolean:
     case Primitive::kPrimByte: {
+      CpuRegister value = locations->InAt(1).As<CpuRegister>();
       __ movb(Address(cls, offset), value);
       break;
     }
 
     case Primitive::kPrimShort:
     case Primitive::kPrimChar: {
+      CpuRegister value = locations->InAt(1).As<CpuRegister>();
       __ movw(Address(cls, offset), value);
       break;
     }
 
     case Primitive::kPrimInt:
     case Primitive::kPrimNot: {
+      CpuRegister value = locations->InAt(1).As<CpuRegister>();
       __ movl(Address(cls, offset), value);
       if (field_type == Primitive::kPrimNot) {
         CpuRegister temp = locations->GetTemp(0).As<CpuRegister>();
@@ -2551,14 +2638,23 @@
     }
 
     case Primitive::kPrimLong: {
+      CpuRegister value = locations->InAt(1).As<CpuRegister>();
       __ movq(Address(cls, offset), value);
       break;
     }
 
-    case Primitive::kPrimFloat:
-    case Primitive::kPrimDouble:
-      LOG(FATAL) << "Unimplemented register type " << field_type;
-      UNREACHABLE();
+    case Primitive::kPrimFloat: {
+      XmmRegister value = locations->InAt(1).As<XmmRegister>();
+      __ movss(Address(cls, offset), value);
+      break;
+    }
+
+    case Primitive::kPrimDouble: {
+      XmmRegister value = locations->InAt(1).As<XmmRegister>();
+      __ movsd(Address(cls, offset), value);
+      break;
+    }
+
     case Primitive::kPrimVoid:
       LOG(FATAL) << "Unreachable type " << field_type;
       UNREACHABLE();
@@ -2610,5 +2706,59 @@
   codegen_->RecordPcInfo(instruction, instruction->GetDexPc());
 }
 
+void LocationsBuilderX86_64::VisitTypeCheck(HTypeCheck* instruction) {
+  LocationSummary::CallKind call_kind = instruction->IsClassFinal()
+      ? LocationSummary::kNoCall
+      : LocationSummary::kCallOnSlowPath;
+  LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction, call_kind);
+  locations->SetInAt(0, Location::RequiresRegister());
+  locations->SetInAt(1, Location::Any());
+  locations->SetOut(Location::RequiresRegister());
+}
+
+void InstructionCodeGeneratorX86_64::VisitTypeCheck(HTypeCheck* instruction) {
+  LocationSummary* locations = instruction->GetLocations();
+  CpuRegister obj = locations->InAt(0).As<CpuRegister>();
+  Location cls = locations->InAt(1);
+  CpuRegister out = locations->Out().As<CpuRegister>();
+  uint32_t class_offset = mirror::Object::ClassOffset().Int32Value();
+  Label done, zero;
+  SlowPathCodeX86_64* slow_path = nullptr;
+
+  // Return 0 if `obj` is null.
+  // TODO: avoid this check if we know obj is not null.
+  __ testl(obj, obj);
+  __ j(kEqual, &zero);
+  // Compare the class of `obj` with `cls`.
+  __ movl(out, Address(obj, class_offset));
+  if (cls.IsRegister()) {
+    __ cmpl(out, cls.As<CpuRegister>());
+  } else {
+    DCHECK(cls.IsStackSlot()) << cls;
+    __ cmpl(out, Address(CpuRegister(RSP), cls.GetStackIndex()));
+  }
+  if (instruction->IsClassFinal()) {
+    // Classes must be equal for the instanceof to succeed.
+    __ j(kNotEqual, &zero);
+    __ movl(out, Immediate(1));
+    __ jmp(&done);
+  } else {
+    // If the classes are not equal, we go into a slow path.
+    DCHECK(locations->OnlyCallsOnSlowPath());
+    slow_path = new (GetGraph()->GetArena()) TypeCheckSlowPathX86_64(
+        instruction, Location::RegisterLocation(out.AsRegister()));
+    codegen_->AddSlowPath(slow_path);
+    __ j(kNotEqual, slow_path->GetEntryLabel());
+    __ movl(out, Immediate(1));
+    __ jmp(&done);
+  }
+  __ Bind(&zero);
+  __ movl(out, Immediate(0));
+  if (slow_path != nullptr) {
+    __ Bind(slow_path->GetExitLabel());
+  }
+  __ Bind(&done);
+}
+
 }  // namespace x86_64
 }  // namespace art
diff --git a/compiler/optimizing/locations.h b/compiler/optimizing/locations.h
index bed688b..d1555d4 100644
--- a/compiler/optimizing/locations.h
+++ b/compiler/optimizing/locations.h
@@ -417,6 +417,7 @@
   LocationSummary(HInstruction* instruction, CallKind call_kind = kNoCall);
 
   void SetInAt(uint32_t at, Location location) {
+    DCHECK(inputs_.Get(at).IsUnallocated() || inputs_.Get(at).IsInvalid());
     inputs_.Put(at, location);
   }
 
@@ -429,8 +430,17 @@
   }
 
   void SetOut(Location location, bool overlaps = true) {
+    DCHECK(output_.IsUnallocated() || output_.IsInvalid());
     output_overlaps_ = overlaps;
-    output_ = Location(location);
+    output_ = location;
+  }
+
+  void UpdateOut(Location location) {
+    // The only reason for updating an output is for parameters where
+    // we only know the exact stack slot after doing full register
+    // allocation.
+    DCHECK(output_.IsStackSlot() || output_.IsDoubleStackSlot());
+    output_ = location;
   }
 
   void AddTemp(Location location) {
@@ -442,6 +452,7 @@
   }
 
   void SetTempAt(uint32_t at, Location location) {
+    DCHECK(temps_.Get(at).IsUnallocated() || temps_.Get(at).IsInvalid());
     temps_.Put(at, location);
   }
 
@@ -528,6 +539,8 @@
   // Registers that are in use at this position.
   RegisterSet live_registers_;
 
+  ART_FRIEND_TEST(RegisterAllocatorTest, ExpectedInRegisterHint);
+  ART_FRIEND_TEST(RegisterAllocatorTest, SameAsFirstInputHint);
   DISALLOW_COPY_AND_ASSIGN(LocationSummary);
 };
 
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 37e5e6b..ecf8c37 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -524,6 +524,7 @@
   M(SuspendCheck, Instruction)                                          \
   M(Temporary, Instruction)                                             \
   M(Throw, Instruction)                                                 \
+  M(TypeCheck, Instruction)                                             \
   M(TypeConversion, Instruction)                                        \
 
 #define FOR_EACH_INSTRUCTION(M)                                         \
@@ -2088,6 +2089,8 @@
 
   size_t GetIndex() const { return index_; }
 
+  Primitive::Type GetType() const OVERRIDE { return GetPrevious()->GetType(); }
+
   DECLARE_INSTRUCTION(Temporary);
 
  private:
@@ -2323,6 +2326,45 @@
   DISALLOW_COPY_AND_ASSIGN(HThrow);
 };
 
+class HTypeCheck : public HExpression<2> {
+ public:
+  explicit HTypeCheck(HInstruction* object,
+                      HLoadClass* constant,
+                      bool class_is_final,
+                      uint32_t dex_pc)
+      : HExpression(Primitive::kPrimBoolean, SideEffects::None()),
+        class_is_final_(class_is_final),
+        dex_pc_(dex_pc) {
+    SetRawInputAt(0, object);
+    SetRawInputAt(1, constant);
+  }
+
+  bool CanBeMoved() const OVERRIDE { return true; }
+
+  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
+    UNUSED(other);
+    return true;
+  }
+
+  bool NeedsEnvironment() const OVERRIDE {
+    // TODO: Can we debug when doing a runtime instanceof check?
+    return false;
+  }
+
+  uint32_t GetDexPc() const { return dex_pc_; }
+
+  bool IsClassFinal() const { return class_is_final_; }
+
+  DECLARE_INSTRUCTION(TypeCheck);
+
+ private:
+  const bool class_is_final_;
+  const uint32_t dex_pc_;
+
+  DISALLOW_COPY_AND_ASSIGN(HTypeCheck);
+};
+
+
 class MoveOperands : public ArenaObject<kArenaAllocMisc> {
  public:
   MoveOperands(Location source, Location destination, HInstruction* instruction)
diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index 0745f9c..4a9deea 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -1164,11 +1164,11 @@
       if (location.IsStackSlot()) {
         location = Location::StackSlot(location.GetStackIndex() + codegen_->GetFrameSize());
         current->SetSpillSlot(location.GetStackIndex());
-        locations->SetOut(location);
+        locations->UpdateOut(location);
       } else if (location.IsDoubleStackSlot()) {
         location = Location::DoubleStackSlot(location.GetStackIndex() + codegen_->GetFrameSize());
         current->SetSpillSlot(location.GetStackIndex());
-        locations->SetOut(location);
+        locations->UpdateOut(location);
       } else if (current->HasSpillSlot()) {
         current->SetSpillSlot(current->GetSpillSlot() + codegen_->GetFrameSize());
       }
diff --git a/compiler/optimizing/register_allocator_test.cc b/compiler/optimizing/register_allocator_test.cc
index 9b1a121..3d81362 100644
--- a/compiler/optimizing/register_allocator_test.cc
+++ b/compiler/optimizing/register_allocator_test.cc
@@ -622,7 +622,8 @@
     liveness.Analyze();
 
     // Check that the field gets put in the register expected by its use.
-    ret->GetLocations()->SetInAt(0, Location::RegisterLocation(2));
+    // Don't use SetInAt because we are overriding an already allocated location.
+    ret->GetLocations()->inputs_.Put(0, Location::RegisterLocation(2));
 
     RegisterAllocator register_allocator(&allocator, &codegen, liveness);
     register_allocator.AllocateRegisters();
@@ -684,7 +685,8 @@
     liveness.Analyze();
 
     // check that both adds get the same register.
-    first_add->InputAt(0)->GetLocations()->SetOut(Location::RegisterLocation(2));
+    // Don't use SetOutput because output is already allocated.
+    first_add->InputAt(0)->GetLocations()->output_ = Location::RegisterLocation(2);
     ASSERT_EQ(first_add->GetLocations()->Out().GetPolicy(), Location::kSameAsFirstInput);
     ASSERT_EQ(second_add->GetLocations()->Out().GetPolicy(), Location::kSameAsFirstInput);
 
diff --git a/runtime/base/allocator.h b/runtime/base/allocator.h
index 30f7f12..5a09c96 100644
--- a/runtime/base/allocator.h
+++ b/runtime/base/allocator.h
@@ -101,7 +101,7 @@
 
 // Tracking allocator for use with STL types, tracks how much memory is used.
 template<class T, AllocatorTag kTag>
-class TrackingAllocatorImpl {
+class TrackingAllocatorImpl : public std::allocator<T> {
  public:
   typedef typename std::allocator<T>::value_type value_type;
   typedef typename std::allocator<T>::size_type size_type;
diff --git a/runtime/base/hash_set.h b/runtime/base/hash_set.h
new file mode 100644
index 0000000..992e5b1
--- /dev/null
+++ b/runtime/base/hash_set.h
@@ -0,0 +1,407 @@
+/*
+ * Copyright (C) 2014 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.
+ */
+
+#ifndef ART_RUNTIME_BASE_HASH_SET_H_
+#define ART_RUNTIME_BASE_HASH_SET_H_
+
+#include <functional>
+#include <memory>
+#include <stdint.h>
+#include <utility>
+
+#include "logging.h"
+
+namespace art {
+
+// Returns true if an item is empty.
+template <class T>
+class DefaultEmptyFn {
+ public:
+  void MakeEmpty(T& item) const {
+    item = T();
+  }
+  bool IsEmpty(const T& item) const {
+    return item == T();
+  }
+};
+
+template <class T>
+class DefaultEmptyFn<T*> {
+ public:
+  void MakeEmpty(T*& item) const {
+    item = nullptr;
+  }
+  bool IsEmpty(const T*& item) const {
+    return item == nullptr;
+  }
+};
+
+// Low memory version of a hash set, uses less memory than std::unordered_set since elements aren't
+// boxed. Uses linear probing.
+// EmptyFn needs to implement two functions MakeEmpty(T& item) and IsEmpty(const T& item)
+template <class T, class EmptyFn = DefaultEmptyFn<T>, class HashFn = std::hash<T>,
+    class Pred = std::equal_to<T>, class Alloc = std::allocator<T>>
+class HashSet {
+ public:
+  static constexpr double kDefaultMinLoadFactor = 0.5;
+  static constexpr double kDefaultMaxLoadFactor = 0.9;
+  static constexpr size_t kMinBuckets = 1000;
+
+  class Iterator {
+   public:
+    Iterator(const Iterator&) = default;
+    Iterator(HashSet* hash_set, size_t index) : hash_set_(hash_set), index_(index) {
+    }
+    Iterator& operator=(const Iterator&) = default;
+    bool operator==(const Iterator& other) const {
+      return hash_set_ == other.hash_set_ && index_ == other.index_;
+    }
+    bool operator!=(const Iterator& other) const {
+      return !(*this == other);
+    }
+    Iterator operator++() {  // Value after modification.
+      index_ = NextNonEmptySlot(index_);
+      return *this;
+    }
+    Iterator operator++(int) {
+      Iterator temp = *this;
+      index_ = NextNonEmptySlot(index_);
+      return temp;
+    }
+    T& operator*() {
+      DCHECK(!hash_set_->IsFreeSlot(GetIndex()));
+      return hash_set_->ElementForIndex(index_);
+    }
+    const T& operator*() const {
+      DCHECK(!hash_set_->IsFreeSlot(GetIndex()));
+      return hash_set_->ElementForIndex(index_);
+    }
+    T* operator->() {
+      return &**this;
+    }
+    const T* operator->() const {
+      return &**this;
+    }
+    // TODO: Operator -- --(int)
+
+   private:
+    HashSet* hash_set_;
+    size_t index_;
+
+    size_t GetIndex() const {
+      return index_;
+    }
+    size_t NextNonEmptySlot(size_t index) const {
+      const size_t num_buckets = hash_set_->NumBuckets();
+      DCHECK_LT(index, num_buckets);
+      do {
+        ++index;
+      } while (index < num_buckets && hash_set_->IsFreeSlot(index));
+      return index;
+    }
+
+    friend class HashSet;
+  };
+
+  void Clear() {
+    DeallocateStorage();
+    AllocateStorage(1);
+    num_elements_ = 0;
+    elements_until_expand_ = 0;
+  }
+  HashSet() : num_elements_(0), num_buckets_(0), data_(nullptr),
+      min_load_factor_(kDefaultMinLoadFactor), max_load_factor_(kDefaultMaxLoadFactor) {
+    Clear();
+  }
+  HashSet(const HashSet& other) : num_elements_(0), num_buckets_(0), data_(nullptr) {
+    *this = other;
+  }
+  HashSet(HashSet&& other) : num_elements_(0), num_buckets_(0), data_(nullptr) {
+    *this = std::move(other);
+  }
+  ~HashSet() {
+    DeallocateStorage();
+  }
+  HashSet& operator=(HashSet&& other) {
+    std::swap(data_, other.data_);
+    std::swap(num_buckets_, other.num_buckets_);
+    std::swap(num_elements_, other.num_elements_);
+    std::swap(elements_until_expand_, other.elements_until_expand_);
+    std::swap(min_load_factor_, other.min_load_factor_);
+    std::swap(max_load_factor_, other.max_load_factor_);
+    return *this;
+  }
+  HashSet& operator=(const HashSet& other) {
+    DeallocateStorage();
+    AllocateStorage(other.NumBuckets());
+    for (size_t i = 0; i < num_buckets_; ++i) {
+      ElementForIndex(i) = other.data_[i];
+    }
+    num_elements_ = other.num_elements_;
+    elements_until_expand_ = other.elements_until_expand_;
+    min_load_factor_ = other.min_load_factor_;
+    max_load_factor_ = other.max_load_factor_;
+    return *this;
+  }
+  // Lower case for c++11 for each.
+  Iterator begin() {
+    Iterator ret(this, 0);
+    if (num_buckets_ != 0 && IsFreeSlot(ret.GetIndex())) {
+      ++ret;  // Skip all the empty slots.
+    }
+    return ret;
+  }
+  // Lower case for c++11 for each.
+  Iterator end() {
+    return Iterator(this, NumBuckets());
+  }
+  bool Empty() {
+    return begin() == end();
+  }
+  // Erase algorithm:
+  // Make an empty slot where the iterator is pointing.
+  // Scan fowards until we hit another empty slot.
+  // If an element inbetween doesn't rehash to the range from the current empty slot to the
+  // iterator. It must be before the empty slot, in that case we can move it to the empty slot
+  // and set the empty slot to be the location we just moved from.
+  // Relies on maintaining the invariant that there's no empty slots from the 'ideal' index of an
+  // element to its actual location/index.
+  Iterator Erase(Iterator it) {
+    // empty_index is the index that will become empty.
+    size_t empty_index = it.GetIndex();
+    DCHECK(!IsFreeSlot(empty_index));
+    size_t next_index = empty_index;
+    bool filled = false;  // True if we filled the empty index.
+    while (true) {
+      next_index = NextIndex(next_index);
+      T& next_element = ElementForIndex(next_index);
+      // If the next element is empty, we are done. Make sure to clear the current empty index.
+      if (emptyfn_.IsEmpty(next_element)) {
+        emptyfn_.MakeEmpty(ElementForIndex(empty_index));
+        break;
+      }
+      // Otherwise try to see if the next element can fill the current empty index.
+      const size_t next_hash = hashfn_(next_element);
+      // Calculate the ideal index, if it is within empty_index + 1 to next_index then there is
+      // nothing we can do.
+      size_t next_ideal_index = IndexForHash(next_hash);
+      // Loop around if needed for our check.
+      size_t unwrapped_next_index = next_index;
+      if (unwrapped_next_index < empty_index) {
+        unwrapped_next_index += NumBuckets();
+      }
+      // Loop around if needed for our check.
+      size_t unwrapped_next_ideal_index = next_ideal_index;
+      if (unwrapped_next_ideal_index < empty_index) {
+        unwrapped_next_ideal_index += NumBuckets();
+      }
+      if (unwrapped_next_ideal_index <= empty_index ||
+          unwrapped_next_ideal_index > unwrapped_next_index) {
+        // If the target index isn't within our current range it must have been probed from before
+        // the empty index.
+        ElementForIndex(empty_index) = std::move(next_element);
+        filled = true;  // TODO: Optimize
+        empty_index = next_index;
+      }
+    }
+    --num_elements_;
+    // If we didn't fill the slot then we need go to the next non free slot.
+    if (!filled) {
+      ++it;
+    }
+    return it;
+  }
+  // Find an element, returns end() if not found.
+  // Allows custom K types, example of when this is useful.
+  // Set of Class* sorted by name, want to find a class with a name but can't allocate a dummy
+  // object in the heap for performance solution.
+  template <typename K>
+  Iterator Find(const K& element) {
+    return FindWithHash(element, hashfn_(element));
+  }
+  template <typename K>
+  Iterator FindWithHash(const K& element, size_t hash) {
+    DCHECK_EQ(hashfn_(element), hash);
+    size_t index = IndexForHash(hash);
+    while (true) {
+      T& slot = ElementForIndex(index);
+      if (emptyfn_.IsEmpty(slot)) {
+        return end();
+      }
+      if (pred_(slot, element)) {
+        return Iterator(this, index);
+      }
+      index = NextIndex(index);
+    }
+  }
+  // Insert an element, allows duplicates.
+  void Insert(const T& element) {
+    InsertWithHash(element, hashfn_(element));
+  }
+  void InsertWithHash(const T& element, size_t hash) {
+    DCHECK_EQ(hash, hashfn_(element));
+    if (num_elements_ >= elements_until_expand_) {
+      Expand();
+      DCHECK_LT(num_elements_, elements_until_expand_);
+    }
+    const size_t index = FirstAvailableSlot(IndexForHash(hash));
+    data_[index] = element;
+    ++num_elements_;
+  }
+  size_t Size() const {
+    return num_elements_;
+  }
+  void ShrinkToMaximumLoad() {
+    Resize(Size() / max_load_factor_);
+  }
+  // To distance that inserted elements were probed. Used for measuring how good hash functions
+  // are.
+  size_t TotalProbeDistance() const {
+    size_t total = 0;
+    for (size_t i = 0; i < NumBuckets(); ++i) {
+      const T& element = ElementForIndex(i);
+      if (!emptyfn_.IsEmpty(element)) {
+        size_t ideal_location = IndexForHash(hashfn_(element));
+        if (ideal_location > i) {
+          total += i + NumBuckets() - ideal_location;
+        } else {
+          total += i - ideal_location;
+        }
+      }
+    }
+    return total;
+  }
+  // Calculate the current load factor and return it.
+  double CalculateLoadFactor() const {
+    return static_cast<double>(Size()) / static_cast<double>(NumBuckets());
+  }
+  // Make sure that everything reinserts in the right spot. Returns the number of errors.
+  size_t Verify() {
+    size_t errors = 0;
+    for (size_t i = 0; i < num_buckets_; ++i) {
+      T& element = data_[i];
+      if (!emptyfn_.IsEmpty(element)) {
+        T temp;
+        emptyfn_.MakeEmpty(temp);
+        std::swap(temp, element);
+        size_t first_slot = FirstAvailableSlot(IndexForHash(hashfn_(temp)));
+        if (i != first_slot) {
+          LOG(ERROR) << "Element " << i << " should be in slot " << first_slot;
+          ++errors;
+        }
+        std::swap(temp, element);
+      }
+    }
+    return errors;
+  }
+
+ private:
+  T& ElementForIndex(size_t index) {
+    DCHECK_LT(index, NumBuckets());
+    DCHECK(data_ != nullptr);
+    return data_[index];
+  }
+  const T& ElementForIndex(size_t index) const {
+    DCHECK_LT(index, NumBuckets());
+    DCHECK(data_ != nullptr);
+    return data_[index];
+  }
+  size_t IndexForHash(size_t hash) const {
+    return hash % num_buckets_;
+  }
+  size_t NextIndex(size_t index) const {
+    if (UNLIKELY(++index >= num_buckets_)) {
+      DCHECK_EQ(index, NumBuckets());
+      return 0;
+    }
+    return index;
+  }
+  bool IsFreeSlot(size_t index) const {
+    return emptyfn_.IsEmpty(ElementForIndex(index));
+  }
+  size_t NumBuckets() const {
+    return num_buckets_;
+  }
+  // Allocate a number of buckets.
+  void AllocateStorage(size_t num_buckets) {
+    num_buckets_ = num_buckets;
+    data_ = allocfn_.allocate(num_buckets_);
+    for (size_t i = 0; i < num_buckets_; ++i) {
+      allocfn_.construct(allocfn_.address(data_[i]));
+      emptyfn_.MakeEmpty(data_[i]);
+    }
+  }
+  void DeallocateStorage() {
+    if (num_buckets_ != 0) {
+      for (size_t i = 0; i < NumBuckets(); ++i) {
+        allocfn_.destroy(allocfn_.address(data_[i]));
+      }
+      allocfn_.deallocate(data_, NumBuckets());
+      data_ = nullptr;
+      num_buckets_ = 0;
+    }
+  }
+  // Expand the set based on the load factors.
+  void Expand() {
+    size_t min_index = static_cast<size_t>(Size() / min_load_factor_);
+    if (min_index < kMinBuckets) {
+      min_index = kMinBuckets;
+    }
+    // Resize based on the minimum load factor.
+    Resize(min_index);
+    // When we hit elements_until_expand_, we are at the max load factor and must expand again.
+    elements_until_expand_ = NumBuckets() * max_load_factor_;
+  }
+  // Expand / shrink the table to the new specified size.
+  void Resize(size_t new_size) {
+    DCHECK_GE(new_size, Size());
+    T* old_data = data_;
+    size_t old_num_buckets = num_buckets_;
+    // Reinsert all of the old elements.
+    AllocateStorage(new_size);
+    for (size_t i = 0; i < old_num_buckets; ++i) {
+      T& element = old_data[i];
+      if (!emptyfn_.IsEmpty(element)) {
+        data_[FirstAvailableSlot(IndexForHash(hashfn_(element)))] = std::move(element);
+      }
+      allocfn_.destroy(allocfn_.address(element));
+    }
+    allocfn_.deallocate(old_data, old_num_buckets);
+  }
+  ALWAYS_INLINE size_t FirstAvailableSlot(size_t index) const {
+    while (!emptyfn_.IsEmpty(data_[index])) {
+      index = NextIndex(index);
+    }
+    return index;
+  }
+
+  Alloc allocfn_;  // Allocator function.
+  HashFn hashfn_;  // Hashing function.
+  EmptyFn emptyfn_;  // IsEmpty/SetEmpty function.
+  Pred pred_;  // Equals function.
+  size_t num_elements_;  // Number of inserted elements.
+  size_t num_buckets_;  // Number of hash table buckets.
+  size_t elements_until_expand_;  // Maxmimum number of elements until we expand the table.
+  T* data_;  // Backing storage.
+  double min_load_factor_;
+  double max_load_factor_;
+
+  friend class Iterator;
+};
+
+}  // namespace art
+
+#endif  // ART_RUNTIME_BASE_HASH_SET_H_
diff --git a/runtime/base/hash_set_test.cc b/runtime/base/hash_set_test.cc
new file mode 100644
index 0000000..885fc06
--- /dev/null
+++ b/runtime/base/hash_set_test.cc
@@ -0,0 +1,203 @@
+/*
+ * Copyright (C) 2014 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.
+ */
+
+#include "hash_set.h"
+
+#include <map>
+#include <sstream>
+#include <string>
+#include <unordered_set>
+
+#include "common_runtime_test.h"
+#include "utils.h"
+
+namespace art {
+
+class IsEmptyFnString {
+ public:
+  void MakeEmpty(std::string& item) const {
+    item.clear();
+  }
+  bool IsEmpty(const std::string& item) const {
+    return item.empty();
+  }
+};
+
+class HashSetTest : public CommonRuntimeTest {
+ public:
+  HashSetTest() : seed_(97421), unique_number_(0) {
+  }
+  std::string RandomString(size_t len) {
+    std::ostringstream oss;
+    for (size_t i = 0; i < len; ++i) {
+      oss << static_cast<char>('A' + PRand() % 64);
+    }
+    static_assert(' ' < 'A', "space must be less than a");
+    oss << " " << unique_number_++;  // Relies on ' ' < 'A'
+    return oss.str();
+  }
+  void SetSeed(size_t seed) {
+    seed_ = seed;
+  }
+  size_t PRand() {  // Pseudo random.
+    seed_ = seed_ * 1103515245 + 12345;
+    return seed_;
+  }
+
+ private:
+  size_t seed_;
+  size_t unique_number_;
+};
+
+TEST_F(HashSetTest, TestSmoke) {
+  HashSet<std::string, IsEmptyFnString> hash_set;
+  const std::string test_string = "hello world 1234";
+  ASSERT_TRUE(hash_set.Empty());
+  ASSERT_EQ(hash_set.Size(), 0U);
+  hash_set.Insert(test_string);
+  auto it = hash_set.Find(test_string);
+  ASSERT_EQ(*it, test_string);
+  auto after_it = hash_set.Erase(it);
+  ASSERT_TRUE(after_it == hash_set.end());
+  ASSERT_TRUE(hash_set.Empty());
+  ASSERT_EQ(hash_set.Size(), 0U);
+  it = hash_set.Find(test_string);
+  ASSERT_TRUE(it == hash_set.end());
+}
+
+TEST_F(HashSetTest, TestInsertAndErase) {
+  HashSet<std::string, IsEmptyFnString> hash_set;
+  static constexpr size_t count = 1000;
+  std::vector<std::string> strings;
+  for (size_t i = 0; i < count; ++i) {
+    // Insert a bunch of elements and make sure we can find them.
+    strings.push_back(RandomString(10));
+    hash_set.Insert(strings[i]);
+    auto it = hash_set.Find(strings[i]);
+    ASSERT_TRUE(it != hash_set.end());
+    ASSERT_EQ(*it, strings[i]);
+  }
+  ASSERT_EQ(strings.size(), hash_set.Size());
+  // Try to erase the odd strings.
+  for (size_t i = 1; i < count; i += 2) {
+    auto it = hash_set.Find(strings[i]);
+    ASSERT_TRUE(it != hash_set.end());
+    ASSERT_EQ(*it, strings[i]);
+    hash_set.Erase(it);
+  }
+  // Test removed.
+  for (size_t i = 1; i < count; i += 2) {
+    auto it = hash_set.Find(strings[i]);
+    ASSERT_TRUE(it == hash_set.end());
+  }
+  for (size_t i = 0; i < count; i += 2) {
+    auto it = hash_set.Find(strings[i]);
+    ASSERT_TRUE(it != hash_set.end());
+    ASSERT_EQ(*it, strings[i]);
+  }
+}
+
+TEST_F(HashSetTest, TestIterator) {
+  HashSet<std::string, IsEmptyFnString> hash_set;
+  ASSERT_TRUE(hash_set.begin() == hash_set.end());
+  static constexpr size_t count = 1000;
+  std::vector<std::string> strings;
+  for (size_t i = 0; i < count; ++i) {
+    // Insert a bunch of elements and make sure we can find them.
+    strings.push_back(RandomString(10));
+    hash_set.Insert(strings[i]);
+  }
+  // Make sure we visit each string exactly once.
+  std::map<std::string, size_t> found_count;
+  for (const std::string& s : hash_set) {
+    ++found_count[s];
+  }
+  for (size_t i = 0; i < count; ++i) {
+    ASSERT_EQ(found_count[strings[i]], 1U);
+  }
+  found_count.clear();
+  // Remove all the elements with iterator erase.
+  for (auto it = hash_set.begin(); it != hash_set.end();) {
+    ++found_count[*it];
+    it = hash_set.Erase(it);
+    ASSERT_EQ(hash_set.Verify(), 0U);
+  }
+  for (size_t i = 0; i < count; ++i) {
+    ASSERT_EQ(found_count[strings[i]], 1U);
+  }
+}
+
+TEST_F(HashSetTest, TestSwap) {
+  HashSet<std::string, IsEmptyFnString> hash_seta, hash_setb;
+  std::vector<std::string> strings;
+  static constexpr size_t count = 1000;
+  for (size_t i = 0; i < count; ++i) {
+    strings.push_back(RandomString(10));
+    hash_seta.Insert(strings[i]);
+  }
+  std::swap(hash_seta, hash_setb);
+  hash_seta.Insert("TEST");
+  hash_setb.Insert("TEST2");
+  for (size_t i = 0; i < count; ++i) {
+    strings.push_back(RandomString(10));
+    hash_seta.Insert(strings[i]);
+  }
+}
+
+TEST_F(HashSetTest, TestStress) {
+  HashSet<std::string, IsEmptyFnString> hash_set;
+  std::unordered_multiset<std::string> std_set;
+  std::vector<std::string> strings;
+  static constexpr size_t string_count = 2000;
+  static constexpr size_t operations = 100000;
+  static constexpr size_t target_size = 5000;
+  for (size_t i = 0; i < string_count; ++i) {
+    strings.push_back(RandomString(i % 10 + 1));
+  }
+  const size_t seed = time(nullptr);
+  SetSeed(seed);
+  LOG(INFO) << "Starting stress test with seed " << seed;
+  for (size_t i = 0; i < operations; ++i) {
+    ASSERT_EQ(hash_set.Size(), std_set.size());
+    size_t delta = std::abs(static_cast<ssize_t>(target_size) -
+                            static_cast<ssize_t>(hash_set.Size()));
+    size_t n = PRand();
+    if (n % target_size == 0) {
+      hash_set.Clear();
+      std_set.clear();
+      ASSERT_TRUE(hash_set.Empty());
+      ASSERT_TRUE(std_set.empty());
+    } else  if (n % target_size < delta) {
+      // Skew towards adding elements until we are at the desired size.
+      const std::string& s = strings[PRand() % string_count];
+      hash_set.Insert(s);
+      std_set.insert(s);
+      ASSERT_EQ(*hash_set.Find(s), *std_set.find(s));
+    } else {
+      const std::string& s = strings[PRand() % string_count];
+      auto it1 = hash_set.Find(s);
+      auto it2 = std_set.find(s);
+      ASSERT_EQ(it1 == hash_set.end(), it2 == std_set.end());
+      if (it1 != hash_set.end()) {
+        ASSERT_EQ(*it1, *it2);
+        hash_set.Erase(it1);
+        std_set.erase(it2);
+      }
+    }
+  }
+}
+
+}  // namespace art
diff --git a/runtime/class_linker.cc b/runtime/class_linker.cc
index eeb65f9..fecea89 100644
--- a/runtime/class_linker.cc
+++ b/runtime/class_linker.cc
@@ -1730,25 +1730,24 @@
 void ClassLinker::VisitClassRoots(RootCallback* callback, void* arg, VisitRootFlags flags) {
   WriterMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
   if ((flags & kVisitRootFlagAllRoots) != 0) {
-    for (std::pair<const size_t, GcRoot<mirror::Class> >& it : class_table_) {
-      it.second.VisitRoot(callback, arg, 0, kRootStickyClass);
+    for (GcRoot<mirror::Class>& root : class_table_) {
+      root.VisitRoot(callback, arg, 0, kRootStickyClass);
+    }
+    for (GcRoot<mirror::Class>& root : pre_zygote_class_table_) {
+      root.VisitRoot(callback, arg, 0, kRootStickyClass);
     }
   } else if ((flags & kVisitRootFlagNewRoots) != 0) {
-    for (auto& pair : new_class_roots_) {
-      mirror::Class* old_ref = pair.second.Read<kWithoutReadBarrier>();
-      pair.second.VisitRoot(callback, arg, 0, kRootStickyClass);
-      mirror::Class* new_ref = pair.second.Read<kWithoutReadBarrier>();
+    for (auto& root : new_class_roots_) {
+      mirror::Class* old_ref = root.Read<kWithoutReadBarrier>();
+      root.VisitRoot(callback, arg, 0, kRootStickyClass);
+      mirror::Class* new_ref = root.Read<kWithoutReadBarrier>();
       if (UNLIKELY(new_ref != old_ref)) {
         // Uh ohes, GC moved a root in the log. Need to search the class_table and update the
         // corresponding object. This is slow, but luckily for us, this may only happen with a
         // concurrent moving GC.
-        for (auto it = class_table_.lower_bound(pair.first), end = class_table_.end();
-            it != end && it->first == pair.first; ++it) {
-          // If the class stored matches the old class, update it to the new value.
-          if (old_ref == it->second.Read<kWithoutReadBarrier>()) {
-            it->second = GcRoot<mirror::Class>(new_ref);
-          }
-        }
+        auto it = class_table_.Find(GcRoot<mirror::Class>(old_ref));
+        class_table_.Erase(it);
+        class_table_.Insert(GcRoot<mirror::Class>(new_ref));
       }
     }
   }
@@ -1806,9 +1805,13 @@
   }
   // TODO: why isn't this a ReaderMutexLock?
   WriterMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
-  for (std::pair<const size_t, GcRoot<mirror::Class> >& it : class_table_) {
-    mirror::Class* c = it.second.Read();
-    if (!visitor(c, arg)) {
+  for (GcRoot<mirror::Class>& root : class_table_) {
+    if (!visitor(root.Read(), arg)) {
+      return;
+    }
+  }
+  for (GcRoot<mirror::Class>& root : pre_zygote_class_table_) {
+    if (!visitor(root.Read(), arg)) {
       return;
     }
   }
@@ -1864,7 +1867,7 @@
       size_t class_table_size;
       {
         ReaderMutexLock mu(self, *Locks::classlinker_classes_lock_);
-        class_table_size = class_table_.size();
+        class_table_size = class_table_.Size() + pre_zygote_class_table_.Size();
       }
       mirror::Class* class_type = mirror::Class::GetJavaLangClass();
       mirror::Class* array_of_class = FindArrayClass(self, &class_type);
@@ -3303,8 +3306,7 @@
     LOG(INFO) << "Loaded class " << descriptor << source;
   }
   WriterMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
-  mirror::Class* existing =
-      LookupClassFromTableLocked(descriptor, klass->GetClassLoader(), hash);
+  mirror::Class* existing = LookupClassFromTableLocked(descriptor, klass->GetClassLoader(), hash);
   if (existing != nullptr) {
     return existing;
   }
@@ -3314,13 +3316,13 @@
     // is in the image.
     existing = LookupClassFromImage(descriptor);
     if (existing != nullptr) {
-      CHECK(klass == existing);
+      CHECK_EQ(klass, existing);
     }
   }
   VerifyObject(klass);
-  class_table_.insert(std::make_pair(hash, GcRoot<mirror::Class>(klass)));
+  class_table_.InsertWithHash(GcRoot<mirror::Class>(klass), hash);
   if (log_new_class_table_roots_) {
-    new_class_roots_.push_back(std::make_pair(hash, GcRoot<mirror::Class>(klass)));
+    new_class_roots_.push_back(GcRoot<mirror::Class>(klass));
   }
   return nullptr;
 }
@@ -3340,14 +3342,8 @@
   CHECK(!existing->IsResolved()) << descriptor;
   CHECK_EQ(klass->GetStatus(), mirror::Class::kStatusResolving) << descriptor;
 
-  for (auto it = class_table_.lower_bound(hash), end = class_table_.end();
-       it != end && it->first == hash; ++it) {
-    mirror::Class* klass_from_table = it->second.Read();
-    if (klass_from_table == existing) {
-      class_table_.erase(it);
-      break;
-    }
-  }
+  auto it = class_table_.FindWithHash(GcRoot<mirror::Class>(klass), hash);
+  CHECK(it != class_table_.end());
 
   CHECK(!klass->IsTemp()) << descriptor;
   if (kIsDebugBuild && klass->GetClassLoader() == nullptr &&
@@ -3356,36 +3352,38 @@
     // is in the image.
     existing = LookupClassFromImage(descriptor);
     if (existing != nullptr) {
-      CHECK(klass == existing) << descriptor;
+      CHECK_EQ(klass, existing) << descriptor;
     }
   }
   VerifyObject(klass);
 
-  class_table_.insert(std::make_pair(hash, GcRoot<mirror::Class>(klass)));
+  // Update the element in the hash set.
+  *it = GcRoot<mirror::Class>(klass);
   if (log_new_class_table_roots_) {
-    new_class_roots_.push_back(std::make_pair(hash, GcRoot<mirror::Class>(klass)));
+    new_class_roots_.push_back(GcRoot<mirror::Class>(klass));
   }
 
   return existing;
 }
 
-bool ClassLinker::RemoveClass(const char* descriptor, const mirror::ClassLoader* class_loader) {
-  size_t hash = Hash(descriptor);
+bool ClassLinker::RemoveClass(const char* descriptor, mirror::ClassLoader* class_loader) {
   WriterMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
-  for (auto it = class_table_.lower_bound(hash), end = class_table_.end();
-       it != end && it->first == hash;
-       ++it) {
-    mirror::Class* klass = it->second.Read();
-    if (klass->GetClassLoader() == class_loader && klass->DescriptorEquals(descriptor)) {
-      class_table_.erase(it);
-      return true;
-    }
+  auto pair = std::make_pair(descriptor, class_loader);
+  auto it = class_table_.Find(pair);
+  if (it != class_table_.end()) {
+    class_table_.Erase(it);
+    return true;
+  }
+  it = pre_zygote_class_table_.Find(pair);
+  if (it != pre_zygote_class_table_.end()) {
+    pre_zygote_class_table_.Erase(it);
+    return true;
   }
   return false;
 }
 
 mirror::Class* ClassLinker::LookupClass(Thread* self, const char* descriptor,
-                                        const mirror::ClassLoader* class_loader) {
+                                        mirror::ClassLoader* class_loader) {
   size_t hash = Hash(descriptor);
   {
     ReaderMutexLock mu(self, *Locks::classlinker_classes_lock_);
@@ -3415,26 +3413,17 @@
 }
 
 mirror::Class* ClassLinker::LookupClassFromTableLocked(const char* descriptor,
-                                                       const mirror::ClassLoader* class_loader,
+                                                       mirror::ClassLoader* class_loader,
                                                        size_t hash) {
-  auto end = class_table_.end();
-  for (auto it = class_table_.lower_bound(hash); it != end && it->first == hash; ++it) {
-    mirror::Class* klass = it->second.Read();
-    if (klass->GetClassLoader() == class_loader && klass->DescriptorEquals(descriptor)) {
-      if (kIsDebugBuild) {
-        // Check for duplicates in the table.
-        for (++it; it != end && it->first == hash; ++it) {
-          mirror::Class* klass2 = it->second.Read();
-          CHECK(!(klass2->GetClassLoader() == class_loader &&
-              klass2->DescriptorEquals(descriptor)))
-              << PrettyClass(klass) << " " << klass << " " << klass->GetClassLoader() << " "
-              << PrettyClass(klass2) << " " << klass2 << " " << klass2->GetClassLoader();
-        }
-      }
-      return klass;
+  auto descriptor_pair = std::make_pair(descriptor, class_loader);
+  auto it = pre_zygote_class_table_.FindWithHash(descriptor_pair, hash);
+  if (it == pre_zygote_class_table_.end()) {
+    it = class_table_.FindWithHash(descriptor_pair, hash);
+    if (it == class_table_.end()) {
+      return nullptr;
     }
   }
-  return nullptr;
+  return it->Read();
 }
 
 static mirror::ObjectArray<mirror::DexCache>* GetImageDexCaches()
@@ -3465,12 +3454,12 @@
         size_t hash = Hash(descriptor);
         mirror::Class* existing = LookupClassFromTableLocked(descriptor, nullptr, hash);
         if (existing != nullptr) {
-          CHECK(existing == klass) << PrettyClassAndClassLoader(existing) << " != "
+          CHECK_EQ(existing, klass) << PrettyClassAndClassLoader(existing) << " != "
               << PrettyClassAndClassLoader(klass);
         } else {
-          class_table_.insert(std::make_pair(hash, GcRoot<mirror::Class>(klass)));
+          class_table_.Insert(GcRoot<mirror::Class>(klass));
           if (log_new_class_table_roots_) {
-            new_class_roots_.push_back(std::make_pair(hash, GcRoot<mirror::Class>(klass)));
+            new_class_roots_.push_back(GcRoot<mirror::Class>(klass));
           }
         }
       }
@@ -3479,6 +3468,13 @@
   dex_cache_image_class_lookup_required_ = false;
 }
 
+void ClassLinker::MoveClassTableToPreZygote() {
+  WriterMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
+  DCHECK(pre_zygote_class_table_.Empty());
+  pre_zygote_class_table_ = std::move(class_table_);
+  class_table_.Clear();
+}
+
 mirror::Class* ClassLinker::LookupClassFromImage(const char* descriptor) {
   ScopedAssertNoThreadSuspension ants(Thread::Current(), "Image class lookup");
   mirror::ObjectArray<mirror::DexCache>* dex_caches = GetImageDexCaches();
@@ -3507,14 +3503,32 @@
   if (dex_cache_image_class_lookup_required_) {
     MoveImageClassesToClassTable();
   }
-  size_t hash = Hash(descriptor);
-  ReaderMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
-  for (auto it = class_table_.lower_bound(hash), end = class_table_.end();
-      it != end && it->first == hash; ++it) {
-    mirror::Class* klass = it->second.Read();
-    if (klass->DescriptorEquals(descriptor)) {
-      result.push_back(klass);
+  WriterMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
+  while (true) {
+    auto it = class_table_.Find(descriptor);
+    if (it == class_table_.end()) {
+      break;
     }
+    result.push_back(it->Read());
+    class_table_.Erase(it);
+  }
+  for (mirror::Class* k : result) {
+    class_table_.Insert(GcRoot<mirror::Class>(k));
+  }
+  size_t pre_zygote_start = result.size();
+  // Now handle the pre zygote table.
+  // Note: This dirties the pre-zygote table but shouldn't be an issue since LookupClasses is only
+  // called from the debugger.
+  while (true) {
+    auto it = pre_zygote_class_table_.Find(descriptor);
+    if (it == pre_zygote_class_table_.end()) {
+      break;
+    }
+    result.push_back(it->Read());
+    pre_zygote_class_table_.Erase(it);
+  }
+  for (size_t i = pre_zygote_start; i < result.size(); ++i) {
+    pre_zygote_class_table_.Insert(GcRoot<mirror::Class>(result[i]));
   }
 }
 
@@ -5697,9 +5711,8 @@
   std::vector<mirror::Class*> all_classes;
   {
     ReaderMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
-    for (std::pair<const size_t, GcRoot<mirror::Class> >& it : class_table_) {
-      mirror::Class* klass = it.second.Read();
-      all_classes.push_back(klass);
+    for (GcRoot<mirror::Class>& it : class_table_) {
+      all_classes.push_back(it.Read());
     }
   }
 
@@ -5793,7 +5806,8 @@
     MoveImageClassesToClassTable();
   }
   ReaderMutexLock mu(self, *Locks::classlinker_classes_lock_);
-  os << "Loaded classes: " << class_table_.size() << " allocated classes\n";
+  os << "Zygote loaded classes=" << pre_zygote_class_table_.Size() << " post zygote classes="
+     << class_table_.Size() << "\n";
 }
 
 size_t ClassLinker::NumLoadedClasses() {
@@ -5801,7 +5815,8 @@
     MoveImageClassesToClassTable();
   }
   ReaderMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
-  return class_table_.size();
+  // Only return non zygote classes since these are the ones which apps which care about.
+  return class_table_.Size();
 }
 
 pid_t ClassLinker::GetClassesLockOwner() {
@@ -5870,4 +5885,41 @@
   return descriptor;
 }
 
+std::size_t ClassLinker::ClassDescriptorHashEquals::operator()(const GcRoot<mirror::Class>& root)
+    const {
+  std::string temp;
+  return Hash(root.Read()->GetDescriptor(&temp));
+}
+
+bool ClassLinker::ClassDescriptorHashEquals::operator()(const GcRoot<mirror::Class>& a,
+                                                        const GcRoot<mirror::Class>& b) {
+  if (a.Read()->GetClassLoader() != b.Read()->GetClassLoader()) {
+    return false;
+  }
+  std::string temp;
+  return a.Read()->DescriptorEquals(b.Read()->GetDescriptor(&temp));
+}
+
+std::size_t ClassLinker::ClassDescriptorHashEquals::operator()(
+    const std::pair<const char*, mirror::ClassLoader*>& element) const {
+  return Hash(element.first);
+}
+
+bool ClassLinker::ClassDescriptorHashEquals::operator()(
+    const GcRoot<mirror::Class>& a, const std::pair<const char*, mirror::ClassLoader*>& b) {
+  if (a.Read()->GetClassLoader() != b.second) {
+    return false;
+  }
+  return a.Read()->DescriptorEquals(b.first);
+}
+
+bool ClassLinker::ClassDescriptorHashEquals::operator()(const GcRoot<mirror::Class>& a,
+                                                        const char* descriptor) {
+  return a.Read()->DescriptorEquals(descriptor);
+}
+
+std::size_t ClassLinker::ClassDescriptorHashEquals::operator()(const char* descriptor) const {
+  return Hash(descriptor);
+}
+
 }  // namespace art
diff --git a/runtime/class_linker.h b/runtime/class_linker.h
index a1cae4d..7b2ba43 100644
--- a/runtime/class_linker.h
+++ b/runtime/class_linker.h
@@ -23,6 +23,7 @@
 #include <vector>
 
 #include "base/allocator.h"
+#include "base/hash_set.h"
 #include "base/macros.h"
 #include "base/mutex.h"
 #include "dex_file.h"
@@ -145,7 +146,7 @@
   // Finds a class by its descriptor, returning NULL if it isn't wasn't loaded
   // by the given 'class_loader'.
   mirror::Class* LookupClass(Thread* self, const char* descriptor,
-                             const mirror::ClassLoader* class_loader)
+                             mirror::ClassLoader* class_loader)
       LOCKS_EXCLUDED(Locks::classlinker_classes_lock_)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
@@ -158,7 +159,7 @@
 
   // General class unloading is not supported, this is used to prune
   // unwanted classes during image writing.
-  bool RemoveClass(const char* descriptor, const mirror::ClassLoader* class_loader)
+  bool RemoveClass(const char* descriptor, mirror::ClassLoader* class_loader)
       LOCKS_EXCLUDED(Locks::classlinker_classes_lock_)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
@@ -458,6 +459,17 @@
     return class_roots;
   }
 
+  // Move all of the image classes into the class table for faster lookups.
+  void MoveImageClassesToClassTable()
+      LOCKS_EXCLUDED(Locks::classlinker_classes_lock_)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  // Move the class table to the pre-zygote table to reduce memory usage. This works by ensuring
+  // that no more classes are ever added to the pre zygote table which makes it that the pages
+  // always remain shared dirty instead of private dirty.
+  void MoveClassTableToPreZygote()
+      LOCKS_EXCLUDED(Locks::classlinker_classes_lock_)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+
  private:
   const OatFile::OatMethod FindOatMethodFor(mirror::ArtMethod* method, bool* found)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
@@ -685,7 +697,7 @@
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
   mirror::Class* LookupClassFromTableLocked(const char* descriptor,
-                                            const mirror::ClassLoader* class_loader,
+                                            mirror::ClassLoader* class_loader,
                                             size_t hash)
       SHARED_LOCKS_REQUIRED(Locks::classlinker_classes_lock_, Locks::mutator_lock_);
 
@@ -693,9 +705,6 @@
       LOCKS_EXCLUDED(Locks::classlinker_classes_lock_)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
-  void MoveImageClassesToClassTable() LOCKS_EXCLUDED(Locks::classlinker_classes_lock_)
-      LOCKS_EXCLUDED(Locks::classlinker_classes_lock_)
-      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
   mirror::Class* LookupClassFromImage(const char* descriptor)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
@@ -724,15 +733,43 @@
   std::vector<GcRoot<mirror::DexCache>> dex_caches_ GUARDED_BY(dex_lock_);
   std::vector<const OatFile*> oat_files_ GUARDED_BY(dex_lock_);
 
+  class ClassDescriptorHashEquals {
+   public:
+    // Same class loader and descriptor.
+    std::size_t operator()(const GcRoot<mirror::Class>& root) const NO_THREAD_SAFETY_ANALYSIS;
+    bool operator()(const GcRoot<mirror::Class>& a, const GcRoot<mirror::Class>& b)
+        NO_THREAD_SAFETY_ANALYSIS;
+    // Same class loader and descriptor.
+    std::size_t operator()(const std::pair<const char*, mirror::ClassLoader*>& element) const
+        NO_THREAD_SAFETY_ANALYSIS;
+    bool operator()(const GcRoot<mirror::Class>& a,
+                    const std::pair<const char*, mirror::ClassLoader*>& b)
+        NO_THREAD_SAFETY_ANALYSIS;
+    // Same descriptor.
+    bool operator()(const GcRoot<mirror::Class>& a, const char* descriptor)
+        NO_THREAD_SAFETY_ANALYSIS;
+    std::size_t operator()(const char* descriptor) const NO_THREAD_SAFETY_ANALYSIS;
+  };
+  class GcRootEmptyFn {
+   public:
+    void MakeEmpty(GcRoot<mirror::Class>& item) const {
+      item = GcRoot<mirror::Class>();
+    }
+    bool IsEmpty(const GcRoot<mirror::Class>& item) const {
+      return item.IsNull();
+    }
+  };
 
-  // multimap from a string hash code of a class descriptor to
-  // mirror::Class* instances. Results should be compared for a matching
-  // Class::descriptor_ and Class::class_loader_.
-  typedef AllocationTrackingMultiMap<size_t, GcRoot<mirror::Class>, kAllocatorTagClassTable> Table;
+  // hash set which hashes class descriptor, and compares descriptors nad class loaders. Results
+  // should be compared for a matching Class descriptor and class loader.
+  typedef HashSet<GcRoot<mirror::Class>, GcRootEmptyFn, ClassDescriptorHashEquals,
+      ClassDescriptorHashEquals, TrackingAllocator<GcRoot<mirror::Class>, kAllocatorTagClassTable>>
+      Table;
   // This contains strong roots. To enable concurrent root scanning of
   // the class table, be careful to use a read barrier when accessing this.
   Table class_table_ GUARDED_BY(Locks::classlinker_classes_lock_);
-  std::vector<std::pair<size_t, GcRoot<mirror::Class>>> new_class_roots_;
+  Table pre_zygote_class_table_ GUARDED_BY(Locks::classlinker_classes_lock_);
+  std::vector<GcRoot<mirror::Class>> new_class_roots_;
 
   // Do we need to search dex caches to find image classes?
   bool dex_cache_image_class_lookup_required_;
diff --git a/runtime/gc/heap.cc b/runtime/gc/heap.cc
index 06cd326..0e67978 100644
--- a/runtime/gc/heap.cc
+++ b/runtime/gc/heap.cc
@@ -1899,6 +1899,7 @@
     return;
   }
   Runtime::Current()->GetInternTable()->SwapPostZygoteWithPreZygote();
+  Runtime::Current()->GetClassLinker()->MoveClassTableToPreZygote();
   VLOG(heap) << "Starting PreZygoteFork";
   // Trim the pages at the end of the non moving space.
   non_moving_space_->Trim();
diff --git a/runtime/gc_root-inl.h b/runtime/gc_root-inl.h
index 482f7bc..a42ec08 100644
--- a/runtime/gc_root-inl.h
+++ b/runtime/gc_root-inl.h
@@ -25,7 +25,7 @@
 
 template<class MirrorType>
 template<ReadBarrierOption kReadBarrierOption>
-inline MirrorType* GcRoot<MirrorType>::Read() {
+inline MirrorType* GcRoot<MirrorType>::Read() const {
   return ReadBarrier::BarrierForRoot<MirrorType, kReadBarrierOption>(&root_);
 }
 
diff --git a/runtime/gc_root.h b/runtime/gc_root.h
index a347622..aee5586 100644
--- a/runtime/gc_root.h
+++ b/runtime/gc_root.h
@@ -27,9 +27,9 @@
 class PACKED(4) GcRoot {
  public:
   template<ReadBarrierOption kReadBarrierOption = kWithReadBarrier>
-  ALWAYS_INLINE MirrorType* Read() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  ALWAYS_INLINE MirrorType* Read() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
-  void VisitRoot(RootCallback* callback, void* arg, uint32_t thread_id, RootType root_type) {
+  void VisitRoot(RootCallback* callback, void* arg, uint32_t thread_id, RootType root_type) const {
     DCHECK(!IsNull());
     callback(reinterpret_cast<mirror::Object**>(&root_), arg, thread_id, root_type);
     DCHECK(!IsNull());
@@ -53,7 +53,7 @@
   }
 
  private:
-  MirrorType* root_;
+  mutable MirrorType* root_;
 };
 
 }  // namespace art
diff --git a/runtime/intern_table.cc b/runtime/intern_table.cc
index 95186c6..56a6d2c 100644
--- a/runtime/intern_table.cc
+++ b/runtime/intern_table.cc
@@ -56,13 +56,13 @@
 void InternTable::VisitRoots(RootCallback* callback, void* arg, VisitRootFlags flags) {
   MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
   if ((flags & kVisitRootFlagAllRoots) != 0) {
-    strong_interns_.VisitRoots(callback, arg, flags);
+    strong_interns_.VisitRoots(callback, arg);
   } else if ((flags & kVisitRootFlagNewRoots) != 0) {
     for (auto& root : new_strong_intern_roots_) {
       mirror::String* old_ref = root.Read<kWithoutReadBarrier>();
       root.VisitRoot(callback, arg, 0, kRootInternedString);
       mirror::String* new_ref = root.Read<kWithoutReadBarrier>();
-      if (UNLIKELY(new_ref != old_ref)) {
+      if (new_ref != old_ref) {
         // The GC moved a root in the log. Need to search the strong interns and update the
         // corresponding object. This is slow, but luckily for us, this may only happen with a
         // concurrent moving GC.
@@ -71,7 +71,6 @@
       }
     }
   }
-
   if ((flags & kVisitRootFlagClearRootLog) != 0) {
     new_strong_intern_roots_.clear();
   }
@@ -190,7 +189,7 @@
     const DexFile* dex_file = dex_cache->GetDexFile();
     // Binary search the dex file for the string index.
     const DexFile::StringId* string_id = dex_file->FindStringId(utf8.c_str());
-    if (string_id != NULL) {
+    if (string_id != nullptr) {
       uint32_t string_idx = dex_file->GetIndexForStringId(*string_id);
       mirror::String* image_string = dex_cache->GetResolvedString(string_idx);
       if (image_string != NULL) {
@@ -198,7 +197,7 @@
       }
     }
   }
-  return NULL;
+  return nullptr;
 }
 
 void InternTable::AllowNewInterns() {
@@ -215,58 +214,36 @@
 }
 
 mirror::String* InternTable::Insert(mirror::String* s, bool is_strong) {
+  if (s == nullptr) {
+    return nullptr;
+  }
   Thread* self = Thread::Current();
   MutexLock mu(self, *Locks::intern_table_lock_);
-
-  DCHECK(s != NULL);
-
   while (UNLIKELY(!allow_new_interns_)) {
     new_intern_condition_.WaitHoldingLocks(self);
   }
-
-  if (is_strong) {
-    // Check the strong table for a match.
-    mirror::String* strong = LookupStrong(s);
-    if (strong != NULL) {
-      return strong;
-    }
-
-    // Check the image for a match.
-    mirror::String* image = LookupStringFromImage(s);
-    if (image != NULL) {
-      return InsertStrong(image);
-    }
-
-    // There is no match in the strong table, check the weak table.
-    mirror::String* weak = LookupWeak(s);
-    if (weak != NULL) {
-      // A match was found in the weak table. Promote to the strong table.
-      RemoveWeak(weak);
-      return InsertStrong(weak);
-    }
-
-    // No match in the strong table or the weak table. Insert into the strong
-    // table.
-    return InsertStrong(s);
-  }
-
   // Check the strong table for a match.
   mirror::String* strong = LookupStrong(s);
-  if (strong != NULL) {
+  if (strong != nullptr) {
     return strong;
   }
   // Check the image for a match.
   mirror::String* image = LookupStringFromImage(s);
-  if (image != NULL) {
-    return InsertWeak(image);
+  if (image != nullptr) {
+    return is_strong ? InsertStrong(image) : InsertWeak(image);
   }
-  // Check the weak table for a match.
+  // There is no match in the strong table, check the weak table.
   mirror::String* weak = LookupWeak(s);
-  if (weak != NULL) {
+  if (weak != nullptr) {
+    if (is_strong) {
+      // A match was found in the weak table. Promote to the strong table.
+      RemoveWeak(weak);
+      return InsertStrong(weak);
+    }
     return weak;
   }
-  // Insert into the weak table.
-  return InsertWeak(s);
+  // No match in the strong table or the weak table. Insert into the strong / weak table.
+  return is_strong ? InsertStrong(s) : InsertWeak(s);
 }
 
 mirror::String* InternTable::InternStrong(int32_t utf16_length, const char* utf8_data) {
@@ -281,16 +258,10 @@
 }
 
 mirror::String* InternTable::InternStrong(mirror::String* s) {
-  if (s == nullptr) {
-    return nullptr;
-  }
   return Insert(s, true);
 }
 
 mirror::String* InternTable::InternWeak(mirror::String* s) {
-  if (s == nullptr) {
-    return nullptr;
-  }
   return Insert(s, false);
 }
 
@@ -304,64 +275,63 @@
   weak_interns_.SweepWeaks(callback, arg);
 }
 
-std::size_t InternTable::StringHashEquals::operator()(const GcRoot<mirror::String>& root) {
+std::size_t InternTable::StringHashEquals::operator()(const GcRoot<mirror::String>& root) const {
   if (kIsDebugBuild) {
     Locks::mutator_lock_->AssertSharedHeld(Thread::Current());
   }
-  return static_cast<size_t>(const_cast<GcRoot<mirror::String>&>(root).Read()->GetHashCode());
+  return static_cast<size_t>(root.Read()->GetHashCode());
 }
 
 bool InternTable::StringHashEquals::operator()(const GcRoot<mirror::String>& a,
-                                               const GcRoot<mirror::String>& b) {
+                                               const GcRoot<mirror::String>& b) const {
   if (kIsDebugBuild) {
     Locks::mutator_lock_->AssertSharedHeld(Thread::Current());
   }
-  return const_cast<GcRoot<mirror::String>&>(a).Read()->Equals(
-      const_cast<GcRoot<mirror::String>&>(b).Read());
+  return a.Read()->Equals(b.Read());
 }
 
 void InternTable::Table::Remove(mirror::String* s) {
-  auto it = post_zygote_table_.find(GcRoot<mirror::String>(s));
+  auto it = post_zygote_table_.Find(GcRoot<mirror::String>(s));
   if (it != post_zygote_table_.end()) {
-    post_zygote_table_.erase(it);
+    post_zygote_table_.Erase(it);
   } else {
-    it = pre_zygote_table_.find(GcRoot<mirror::String>(s));
+    it = pre_zygote_table_.Find(GcRoot<mirror::String>(s));
     DCHECK(it != pre_zygote_table_.end());
-    pre_zygote_table_.erase(it);
+    pre_zygote_table_.Erase(it);
   }
 }
 
 mirror::String* InternTable::Table::Find(mirror::String* s) {
   Locks::intern_table_lock_->AssertHeld(Thread::Current());
-  auto it = pre_zygote_table_.find(GcRoot<mirror::String>(s));
-  if (LIKELY(it != pre_zygote_table_.end())) {
-    return const_cast<GcRoot<mirror::String>&>(*it).Read();
+  auto it = pre_zygote_table_.Find(GcRoot<mirror::String>(s));
+  if (it != pre_zygote_table_.end()) {
+    return it->Read();
   }
-  it = post_zygote_table_.find(GcRoot<mirror::String>(s));
-  if (LIKELY(it != post_zygote_table_.end())) {
-    return const_cast<GcRoot<mirror::String>&>(*it).Read();
+  it = post_zygote_table_.Find(GcRoot<mirror::String>(s));
+  if (it != post_zygote_table_.end()) {
+    return it->Read();
   }
   return nullptr;
 }
 
 void InternTable::Table::SwapPostZygoteWithPreZygote() {
-  CHECK(pre_zygote_table_.empty());
+  CHECK(pre_zygote_table_.Empty());
   std::swap(pre_zygote_table_, post_zygote_table_);
+  VLOG(heap) << "Swapping " << pre_zygote_table_.Size() << " interns to the pre zygote table";
 }
 
 void InternTable::Table::Insert(mirror::String* s) {
   // Always insert the post zygote table, this gets swapped when we create the zygote to be the
   // pre zygote table.
-  post_zygote_table_.insert(GcRoot<mirror::String>(s));
+  post_zygote_table_.Insert(GcRoot<mirror::String>(s));
 }
 
-void InternTable::Table::VisitRoots(RootCallback* callback, void* arg,
-                                    VisitRootFlags flags ATTRIBUTE_UNUSED) {
+void InternTable::Table::VisitRoots(RootCallback* callback, void* arg) {
   for (auto& intern : pre_zygote_table_) {
-    const_cast<GcRoot<mirror::String>&>(intern).VisitRoot(callback, arg, 0, kRootInternedString);
+    intern.VisitRoot(callback, arg, 0, kRootInternedString);
   }
   for (auto& intern : post_zygote_table_) {
-    const_cast<GcRoot<mirror::String>&>(intern).VisitRoot(callback, arg, 0, kRootInternedString);
+    intern.VisitRoot(callback, arg, 0, kRootInternedString);
   }
 }
 
@@ -373,16 +343,19 @@
 void InternTable::Table::SweepWeaks(UnorderedSet* set, IsMarkedCallback* callback, void* arg) {
   for (auto it = set->begin(), end = set->end(); it != end;) {
     // This does not need a read barrier because this is called by GC.
-    GcRoot<mirror::String>& root = const_cast<GcRoot<mirror::String>&>(*it);
-    mirror::Object* object = root.Read<kWithoutReadBarrier>();
+    mirror::Object* object = it->Read<kWithoutReadBarrier>();
     mirror::Object* new_object = callback(object, arg);
     if (new_object == nullptr) {
-      it = set->erase(it);
+      it = set->Erase(it);
     } else {
-      root = GcRoot<mirror::String>(new_object->AsString());
+      *it = GcRoot<mirror::String>(new_object->AsString());
       ++it;
     }
   }
 }
 
+size_t InternTable::Table::Size() const {
+  return pre_zygote_table_.Size() + post_zygote_table_.Size();
+}
+
 }  // namespace art
diff --git a/runtime/intern_table.h b/runtime/intern_table.h
index 0bff7b9..371d3f7 100644
--- a/runtime/intern_table.h
+++ b/runtime/intern_table.h
@@ -20,6 +20,7 @@
 #include <unordered_set>
 
 #include "base/allocator.h"
+#include "base/hash_set.h"
 #include "base/mutex.h"
 #include "gc_root.h"
 #include "object_callbacks.h"
@@ -98,10 +99,19 @@
  private:
   class StringHashEquals {
    public:
-    std::size_t operator()(const GcRoot<mirror::String>& root) NO_THREAD_SAFETY_ANALYSIS;
-    bool operator()(const GcRoot<mirror::String>& a, const GcRoot<mirror::String>& b)
+    std::size_t operator()(const GcRoot<mirror::String>& root) const NO_THREAD_SAFETY_ANALYSIS;
+    bool operator()(const GcRoot<mirror::String>& a, const GcRoot<mirror::String>& b) const
         NO_THREAD_SAFETY_ANALYSIS;
   };
+  class GcRootEmptyFn {
+   public:
+    void MakeEmpty(GcRoot<mirror::String>& item) const {
+      item = GcRoot<mirror::String>();
+    }
+    bool IsEmpty(const GcRoot<mirror::String>& item) const {
+      return item.IsNull();
+    }
+  };
 
   // Table which holds pre zygote and post zygote interned strings. There is one instance for
   // weak interns and strong interns.
@@ -114,19 +124,17 @@
     void Remove(mirror::String* s)
         SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
         EXCLUSIVE_LOCKS_REQUIRED(Locks::intern_table_lock_);
-    void VisitRoots(RootCallback* callback, void* arg, VisitRootFlags flags)
+    void VisitRoots(RootCallback* callback, void* arg)
         SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
         EXCLUSIVE_LOCKS_REQUIRED(Locks::intern_table_lock_);
     void SweepWeaks(IsMarkedCallback* callback, void* arg)
         SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
         EXCLUSIVE_LOCKS_REQUIRED(Locks::intern_table_lock_);
     void SwapPostZygoteWithPreZygote() EXCLUSIVE_LOCKS_REQUIRED(Locks::intern_table_lock_);
-    size_t Size() const EXCLUSIVE_LOCKS_REQUIRED(Locks::intern_table_lock_) {
-      return pre_zygote_table_.size() + post_zygote_table_.size();
-    }
+    size_t Size() const EXCLUSIVE_LOCKS_REQUIRED(Locks::intern_table_lock_);
 
    private:
-    typedef std::unordered_set<GcRoot<mirror::String>, StringHashEquals, StringHashEquals,
+    typedef HashSet<GcRoot<mirror::String>, GcRootEmptyFn, StringHashEquals, StringHashEquals,
         TrackingAllocator<GcRoot<mirror::String>, kAllocatorTagInternTable>> UnorderedSet;
 
     void SweepWeaks(UnorderedSet* set, IsMarkedCallback* callback, void* arg)
@@ -141,6 +149,7 @@
     UnorderedSet post_zygote_table_;
   };
 
+  // Insert if non null, otherwise return nullptr.
   mirror::String* Insert(mirror::String* s, bool is_strong)
       LOCKS_EXCLUDED(Locks::intern_table_lock_)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
diff --git a/runtime/jni_internal.cc b/runtime/jni_internal.cc
index 67e52cb..3b0656e 100644
--- a/runtime/jni_internal.cc
+++ b/runtime/jni_internal.cc
@@ -45,6 +45,7 @@
 #include "mirror/object_array-inl.h"
 #include "mirror/string-inl.h"
 #include "mirror/throwable.h"
+#include "nativebridge/native_bridge.h"
 #include "parsed_options.h"
 #include "reflection.h"
 #include "runtime.h"
diff --git a/runtime/monitor.cc b/runtime/monitor.cc
index 0439428..6445b88 100644
--- a/runtime/monitor.cc
+++ b/runtime/monitor.cc
@@ -36,6 +36,8 @@
 
 namespace art {
 
+static constexpr uint64_t kLongWaitMs = 100;
+
 /*
  * Every Object has a monitor associated with it, but not every Object is actually locked.  Even
  * the ones that are locked do not need a full-fledged monitor until a) there is actual contention
@@ -242,6 +244,7 @@
     mirror::ArtMethod* owners_method = locking_method_;
     uint32_t owners_dex_pc = locking_dex_pc_;
     // Do this before releasing the lock so that we don't get deflated.
+    size_t num_waiters = num_waiters_;
     ++num_waiters_;
     monitor_lock_.Unlock(self);  // Let go of locks in order.
     self->SetMonitorEnterObject(GetObject());
@@ -263,6 +266,12 @@
             const char* owners_filename;
             uint32_t owners_line_number;
             TranslateLocation(owners_method, owners_dex_pc, &owners_filename, &owners_line_number);
+            if (wait_ms > kLongWaitMs && owners_method != nullptr) {
+              LOG(WARNING) << "Long monitor contention event with owner method="
+                  << PrettyMethod(owners_method) << " from " << owners_filename << ":"
+                  << owners_line_number << " waiters=" << num_waiters << " for "
+                  << PrettyDuration(MsToNs(wait_ms));
+            }
             LogContentionEvent(self, wait_ms, sample_percent, owners_filename, owners_line_number);
           }
         }
diff --git a/runtime/runtime.cc b/runtime/runtime.cc
index 1cda29b..d338ad7 100644
--- a/runtime/runtime.cc
+++ b/runtime/runtime.cc
@@ -440,6 +440,7 @@
   if (IsZygote()) {
     ScopedObjectAccess soa(self);
     Runtime::Current()->GetInternTable()->AddImageStringsToTable(heap_->GetImageSpace());
+    Runtime::Current()->GetClassLinker()->MoveImageClassesToClassTable();
   }
 
   if (!IsImageDex2OatEnabled() || !Runtime::Current()->GetHeap()->HasImageSpace()) {
diff --git a/runtime/thread.cc b/runtime/thread.cc
index 7d24562..2c44f27 100644
--- a/runtime/thread.cc
+++ b/runtime/thread.cc
@@ -170,6 +170,9 @@
     self->GetJniEnv()->DeleteGlobalRef(self->tlsPtr_.jpeer);
     self->tlsPtr_.jpeer = nullptr;
     self->SetThreadName(self->GetThreadName(soa)->ToModifiedUtf8().c_str());
+
+    mirror::ArtField* priorityField = soa.DecodeField(WellKnownClasses::java_lang_Thread_priority);
+    self->SetNativePriority(priorityField->GetInt(self->tlsPtr_.opeer));
     Dbg::PostThreadStart(self);
 
     // Invoke the 'run' method of our java.lang.Thread.
diff --git a/runtime/thread_android.cc b/runtime/thread_android.cc
index 73a9e54..d5db983 100644
--- a/runtime/thread_android.cc
+++ b/runtime/thread_android.cc
@@ -55,6 +55,13 @@
   int newNice = kNiceValues[newPriority-1];
   pid_t tid = GetTid();
 
+  // TODO: b/18249098 The code below is broken. It uses getpriority() as a proxy for whether a
+  // thread is already in the SP_FOREGROUND cgroup. This is not necessarily true for background
+  // processes, where all threads are in the SP_BACKGROUND cgroup. This means that callers will
+  // have to call setPriority twice to do what they want :
+  //
+  //     Thread.setPriority(Thread.MIN_PRIORITY);  // no-op wrt to cgroups
+  //     Thread.setPriority(Thread.MAX_PRIORITY);  // will actually change cgroups.
   if (newNice >= ANDROID_PRIORITY_BACKGROUND) {
     set_sched_policy(tid, SP_BACKGROUND);
   } else if (getpriority(PRIO_PROCESS, tid) >= ANDROID_PRIORITY_BACKGROUND) {
diff --git a/test/051-thread/expected.txt b/test/051-thread/expected.txt
index 943d1df..54e34af 100644
--- a/test/051-thread/expected.txt
+++ b/test/051-thread/expected.txt
@@ -9,4 +9,6 @@
 testSetName starting
 testSetName running
 testSetName finished
+testThreadPriorities starting
+testThreadPriorities finished
 thread test done
diff --git a/test/051-thread/src/Main.java b/test/051-thread/src/Main.java
index 390685d..b81273e 100644
--- a/test/051-thread/src/Main.java
+++ b/test/051-thread/src/Main.java
@@ -20,12 +20,17 @@
  * Test some basic thread stuff.
  */
 public class Main {
+    static {
+        System.loadLibrary("arttest");
+    }
+
     public static void main(String[] args) throws Exception {
         System.out.println("thread test starting");
         testThreadCapacity();
         testThreadDaemons();
         testSleepZero();
         testSetName();
+        testThreadPriorities();
         System.out.println("thread test done");
     }
 
@@ -133,4 +138,53 @@
         }
         System.out.print("testSetName finished\n");
     }
+
+    private static void testThreadPriorities() throws Exception {
+        System.out.print("testThreadPriorities starting\n");
+
+        PriorityStoringThread t1 = new PriorityStoringThread(false);
+        t1.setPriority(Thread.MAX_PRIORITY);
+        t1.start();
+        t1.join();
+        if (supportsThreadPriorities() && (t1.getNativePriority() != Thread.MAX_PRIORITY)) {
+            System.out.print("thread priority for t1 was " + t1.getNativePriority() +
+                " [expected Thread.MAX_PRIORITY]\n");
+        }
+
+        PriorityStoringThread t2 = new PriorityStoringThread(true);
+        t2.start();
+        t2.join();
+        if (supportsThreadPriorities() && (t2.getNativePriority() != Thread.MAX_PRIORITY)) {
+            System.out.print("thread priority for t2 was " + t2.getNativePriority() +
+                " [expected Thread.MAX_PRIORITY]\n");
+        }
+
+        System.out.print("testThreadPriorities finished\n");
+    }
+
+    private static native int getNativePriority();
+    private static native boolean supportsThreadPriorities();
+
+    static class PriorityStoringThread extends Thread {
+        private final boolean setPriority;
+        private volatile int nativePriority;
+
+        public PriorityStoringThread(boolean setPriority) {
+            this.setPriority = setPriority;
+            this.nativePriority = -1;
+        }
+
+        @Override
+        public void run() {
+            if (setPriority) {
+                setPriority(Thread.MAX_PRIORITY);
+            }
+
+            nativePriority = Main.getNativePriority();
+        }
+
+        public int getNativePriority() {
+            return nativePriority;
+        }
+    }
 }
diff --git a/test/051-thread/thread_test.cc b/test/051-thread/thread_test.cc
new file mode 100644
index 0000000..2b8e675
--- /dev/null
+++ b/test/051-thread/thread_test.cc
@@ -0,0 +1,38 @@
+/*
+ * Copyright (C) 2014 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.
+ */
+
+#include "base/macros.h"
+#include "jni.h"
+#include "thread-inl.h"
+
+namespace art {
+
+extern "C" JNIEXPORT jint JNICALL Java_Main_getNativePriority(JNIEnv* env,
+                                                              jclass clazz ATTRIBUTE_UNUSED) {
+  return ThreadForEnv(env)->GetNativePriority();
+}
+
+extern "C" JNIEXPORT jboolean JNICALL Java_Main_supportsThreadPriorities(
+    JNIEnv* env ATTRIBUTE_UNUSED,
+    jclass clazz ATTRIBUTE_UNUSED) {
+#if defined(HAVE_ANDROID_OS)
+  return JNI_TRUE;
+#else
+  return JNI_FALSE;
+#endif
+}
+
+}  // namespace art
diff --git a/test/083-compiler-regressions/expected.txt b/test/083-compiler-regressions/expected.txt
index c43d1f7..51bf847 100644
--- a/test/083-compiler-regressions/expected.txt
+++ b/test/083-compiler-regressions/expected.txt
@@ -1,3 +1,4 @@
+b17630605 passes
 b17411468 passes
 b2296099 passes
 b2302318 passes
diff --git a/test/083-compiler-regressions/src/Main.java b/test/083-compiler-regressions/src/Main.java
index 9c772b9..9ad8ea7 100644
--- a/test/083-compiler-regressions/src/Main.java
+++ b/test/083-compiler-regressions/src/Main.java
@@ -30,6 +30,7 @@
     }
 
     public static void main(String args[]) throws Exception {
+        b17630605();
         b17411468();
         b2296099Test();
         b2302318Test();
@@ -63,6 +64,18 @@
         minDoubleWith3ConstsTest();
     }
 
+    public static void b17630605() {
+      // b/17630605 - failure to properly handle min long immediates.
+      long a1 = 40455547223404749L;
+      long a2 = Long.MIN_VALUE;
+      long answer = a1 + a2;
+      if (answer == -9182916489631371059L) {
+          System.out.println("b17630605 passes");
+      } else {
+          System.out.println("b17630605 fails: " + answer);
+      }
+    }
+
     public static void b17411468() {
       // b/17411468 - inline Math.round failure.
       double d1 = 1.0;
diff --git a/test/406-fields/src/Main.java b/test/406-fields/src/Main.java
index 3e94e42..768a784 100644
--- a/test/406-fields/src/Main.java
+++ b/test/406-fields/src/Main.java
@@ -30,6 +30,8 @@
     assertEquals(0, fields.iI);
     assertEquals(0, fields.iJ);
     assertEquals(0, fields.iS);
+    assertEquals(0.0f, fields.iF);
+    assertEquals(0.0, fields.iD);
     assertNull(fields.iObject);
 
     long longValue = -1122198787987987987L;
@@ -40,6 +42,8 @@
     fields.iJ = longValue;
     fields.iS = 68;
     fields.iObject = fields;
+    fields.iF = 2.3f;
+    fields.iD = 5.3;
 
     assertEquals(true, fields.iZ);
     assertEquals(-2, fields.iB);
@@ -48,6 +52,8 @@
     assertEquals(longValue, fields.iJ);
     assertEquals(68, fields.iS);
     assertEquals(fields, fields.iObject);
+    assertEquals(2.3f, fields.iF);
+    assertEquals(5.3, fields.iD);
   }
 
   static class AllFields {
diff --git a/test/414-static-fields/src/Main.java b/test/414-static-fields/src/Main.java
index 9c5cf13..3403772 100644
--- a/test/414-static-fields/src/Main.java
+++ b/test/414-static-fields/src/Main.java
@@ -59,6 +59,8 @@
     assertEquals(0, sI);
     assertEquals(0, sJ);
     assertEquals(0, sS);
+    assertEquals(0.0f, sF);
+    assertEquals(0.0, sD);
     assertNull(sObject);
 
     long longValue = -1122198787987987987L;
@@ -70,6 +72,8 @@
     sJ = longValue;
     sS = 68;
     sObject = o;
+    sF = 2.3f;
+    sD = 5.3;
 
     assertEquals(true, sZ);
     assertEquals(-2, sB);
@@ -78,6 +82,8 @@
     assertEquals(longValue, sJ);
     assertEquals(68, sS);
     assertEquals(o, sObject);
+    assertEquals(2.3f, sF);
+    assertEquals(5.3, sD);
   }
 
   static boolean sZ;
diff --git a/test/422-instanceof/expected.txt b/test/422-instanceof/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/422-instanceof/expected.txt
diff --git a/test/422-instanceof/info.txt b/test/422-instanceof/info.txt
new file mode 100644
index 0000000..b2f7ff1
--- /dev/null
+++ b/test/422-instanceof/info.txt
@@ -0,0 +1 @@
+Tests for instanceof bytecode.
diff --git a/test/422-instanceof/src/Main.java b/test/422-instanceof/src/Main.java
new file mode 100644
index 0000000..307c987
--- /dev/null
+++ b/test/422-instanceof/src/Main.java
@@ -0,0 +1,70 @@
+/*
+ * Copyright (C) 2014 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.
+ */
+
+public class Main {
+  public static Object a;
+
+  public static void assertTrue(boolean value) {
+    if (!value) {
+      throw new Error("Wrong result");
+    }
+  }
+
+  public static void assertFalse(boolean value) {
+    if (value) {
+      throw new Error("Wrong result");
+    }
+  }
+
+  public static boolean $opt$InstanceOfMain() {
+    return a instanceof Main;
+  }
+
+  public static boolean $opt$InstanceOfFinalClass() {
+    return a instanceof FinalClass;
+  }
+
+  public static void main(String[] args) {
+    $opt$TestMain();
+    $opt$TestFinalClass();
+  }
+
+  public static void $opt$TestMain() {
+    a = new Main();
+    assertTrue($opt$InstanceOfMain());
+    a = null;
+    assertFalse($opt$InstanceOfMain());
+    a = new MainChild();
+    assertTrue($opt$InstanceOfMain());
+    a = new Object();
+    assertFalse($opt$InstanceOfMain());
+  }
+
+  public static void $opt$TestFinalClass() {
+    a = new FinalClass();
+    assertTrue($opt$InstanceOfFinalClass());
+    a = null;
+    assertFalse($opt$InstanceOfFinalClass());
+    a = new Main();
+    assertFalse($opt$InstanceOfFinalClass());
+    a = new Object();
+    assertFalse($opt$InstanceOfFinalClass());
+  }
+
+  static class MainChild extends Main {}
+
+  static final class FinalClass {}
+}
diff --git a/test/Android.libarttest.mk b/test/Android.libarttest.mk
index 55de1f3..c9c0475 100644
--- a/test/Android.libarttest.mk
+++ b/test/Android.libarttest.mk
@@ -24,6 +24,7 @@
   004-ReferenceMap/stack_walk_refmap_jni.cc \
   004-StackWalk/stack_walk_jni.cc \
   004-UnsafeTest/unsafe_test.cc \
+  051-thread/thread_test.cc \
   116-nodex2oat/nodex2oat.cc \
   117-nopatchoat/nopatchoat.cc \
   118-noimage-dex2oat/noimage-dex2oat.cc
diff --git a/test/Android.run-test.mk b/test/Android.run-test.mk
index e460f39..ae8ff5e 100644
--- a/test/Android.run-test.mk
+++ b/test/Android.run-test.mk
@@ -279,6 +279,7 @@
   004-SignalTest \
   004-StackWalk \
   004-UnsafeTest \
+  051-thread \
   115-native-bridge \
   116-nodex2oat \
   117-nopatchoat \
@@ -439,6 +440,7 @@
   420-const-class \
   421-exceptions \
   421-large-frame \
+  422-instanceof \
   422-type-conversion \
   700-LoadArgRegs \
   701-easy-div-rem \