Merge "ART: Blacklist CFI test for Heap Poisoning"
diff --git a/compiler/driver/compiler_driver.cc b/compiler/driver/compiler_driver.cc
index 7cb7489..5dc93ce 100644
--- a/compiler/driver/compiler_driver.cc
+++ b/compiler/driver/compiler_driver.cc
@@ -1241,7 +1241,7 @@
   mirror::Class* referrer_class;
   mirror::DexCache* dex_cache;
   {
-    StackHandleScope<3> hs(soa.Self());
+    StackHandleScope<2> hs(soa.Self());
     Handle<mirror::DexCache> dex_cache_handle(
         hs.NewHandle(mUnit->GetClassLinker()->FindDexCache(*mUnit->GetDexFile())));
     Handle<mirror::ClassLoader> class_loader_handle(
diff --git a/compiler/elf_writer_debug.cc b/compiler/elf_writer_debug.cc
index a1aabc3..f4df6c1 100644
--- a/compiler/elf_writer_debug.cc
+++ b/compiler/elf_writer_debug.cc
@@ -243,6 +243,7 @@
                         std::vector<uintptr_t>* debug_line_patches) {
   const std::vector<OatWriter::DebugInfo>& method_infos = oat_writer->GetMethodDebugInfo();
   const InstructionSet isa = compiler->GetInstructionSet();
+  const bool is64bit = Is64BitInstructionSet(isa);
 
   // Find all addresses (low_pc) which contain deduped methods.
   // The first instance of method is not marked deduped_, but the rest is.
@@ -280,7 +281,7 @@
     }
 
     size_t debug_abbrev_offset = debug_abbrev->size();
-    DebugInfoEntryWriter<> info(false /* 32 bit */, debug_abbrev);
+    DebugInfoEntryWriter<> info(is64bit, debug_abbrev);
     info.StartTag(DW_TAG_compile_unit, DW_CHILDREN_yes);
     info.WriteStrp(DW_AT_producer, "Android dex2oat", debug_str);
     info.WriteData1(DW_AT_language, DW_LANG_Java);
@@ -325,7 +326,7 @@
       case kX86_64:
         break;
     }
-    DebugLineOpCodeWriter<> opcodes(false /* 32bit */, code_factor_bits_);
+    DebugLineOpCodeWriter<> opcodes(is64bit, code_factor_bits_);
     opcodes.SetAddress(cunit_low_pc);
     if (dwarf_isa != -1) {
       opcodes.SetISA(dwarf_isa);
diff --git a/compiler/optimizing/code_generator.cc b/compiler/optimizing/code_generator.cc
index 4805cee..d71266d 100644
--- a/compiler/optimizing/code_generator.cc
+++ b/compiler/optimizing/code_generator.cc
@@ -702,8 +702,10 @@
   if (environment->GetParent() != nullptr) {
     // We emit the parent environment first.
     EmitEnvironment(environment->GetParent(), slow_path);
-    stack_map_stream_.BeginInlineInfoEntry(
-        environment->GetMethodIdx(), environment->GetDexPc(), environment->Size());
+    stack_map_stream_.BeginInlineInfoEntry(environment->GetMethodIdx(),
+                                           environment->GetDexPc(),
+                                           environment->GetInvokeType(),
+                                           environment->Size());
   }
 
   // Walk over the environment, and record the location of dex registers.
diff --git a/compiler/optimizing/inliner.cc b/compiler/optimizing/inliner.cc
index 56d868f..47c6318 100644
--- a/compiler/optimizing/inliner.cc
+++ b/compiler/optimizing/inliner.cc
@@ -193,6 +193,7 @@
       caller_dex_file,
       method_index,
       requires_ctor_barrier,
+      invoke_instruction->GetOriginalInvokeType(),
       graph_->IsDebuggable(),
       graph_->GetCurrentInstructionId());
 
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index b712e5e..12ace41 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -60,6 +60,8 @@
 static constexpr uint32_t kMaxIntShiftValue = 0x1f;
 static constexpr uint64_t kMaxLongShiftValue = 0x3f;
 
+static constexpr InvokeType kInvalidInvokeType = static_cast<InvokeType>(-1);
+
 enum IfCondition {
   kCondEQ,
   kCondNE,
@@ -121,6 +123,7 @@
          const DexFile& dex_file,
          uint32_t method_idx,
          bool should_generate_constructor_barrier,
+         InvokeType invoke_type = kInvalidInvokeType,
          bool debuggable = false,
          int start_instruction_id = 0)
       : arena_(arena),
@@ -138,6 +141,7 @@
         current_instruction_id_(start_instruction_id),
         dex_file_(dex_file),
         method_idx_(method_idx),
+        invoke_type_(invoke_type),
         should_generate_constructor_barrier_(should_generate_constructor_barrier),
         cached_null_constant_(nullptr),
         cached_int_constants_(std::less<int32_t>(), arena->Adapter()),
@@ -283,6 +287,10 @@
     return method_idx_;
   }
 
+  InvokeType GetInvokeType() const {
+    return invoke_type_;
+  }
+
  private:
   void VisitBlockForDominatorTree(HBasicBlock* block,
                                   HBasicBlock* predecessor,
@@ -365,6 +373,9 @@
   // The method index in the dex file.
   const uint32_t method_idx_;
 
+  // If inlined, this encodes how the callee is being invoked.
+  const InvokeType invoke_type_;
+
   const bool should_generate_constructor_barrier_;
 
   // Cached constants.
@@ -1101,13 +1112,15 @@
                size_t number_of_vregs,
                const DexFile& dex_file,
                uint32_t method_idx,
-               uint32_t dex_pc)
+               uint32_t dex_pc,
+               InvokeType invoke_type)
      : vregs_(arena, number_of_vregs),
        locations_(arena, number_of_vregs),
        parent_(nullptr),
        dex_file_(dex_file),
        method_idx_(method_idx),
-       dex_pc_(dex_pc) {
+       dex_pc_(dex_pc),
+       invoke_type_(invoke_type) {
     vregs_.SetSize(number_of_vregs);
     for (size_t i = 0; i < number_of_vregs; i++) {
       vregs_.Put(i, HUserRecord<HEnvironment*>());
@@ -1119,16 +1132,20 @@
     }
   }
 
+  HEnvironment(ArenaAllocator* arena, const HEnvironment& to_copy)
+      : HEnvironment(arena,
+                     to_copy.Size(),
+                     to_copy.GetDexFile(),
+                     to_copy.GetMethodIdx(),
+                     to_copy.GetDexPc(),
+                     to_copy.GetInvokeType()) {}
+
   void SetAndCopyParentChain(ArenaAllocator* allocator, HEnvironment* parent) {
-    parent_ = new (allocator) HEnvironment(allocator,
-                                           parent->Size(),
-                                           parent->GetDexFile(),
-                                           parent->GetMethodIdx(),
-                                           parent->GetDexPc());
+    parent_ = new (allocator) HEnvironment(allocator, *parent);
+    parent_->CopyFrom(parent);
     if (parent->GetParent() != nullptr) {
       parent_->SetAndCopyParentChain(allocator, parent->GetParent());
     }
-    parent_->CopyFrom(parent);
   }
 
   void CopyFrom(const GrowableArray<HInstruction*>& locals);
@@ -1169,6 +1186,10 @@
     return method_idx_;
   }
 
+  InvokeType GetInvokeType() const {
+    return invoke_type_;
+  }
+
   const DexFile& GetDexFile() const {
     return dex_file_;
   }
@@ -1188,6 +1209,7 @@
   const DexFile& dex_file_;
   const uint32_t method_idx_;
   const uint32_t dex_pc_;
+  const InvokeType invoke_type_;
 
   friend class HInstruction;
 
@@ -1401,12 +1423,7 @@
   // copying, the uses lists are being updated.
   void CopyEnvironmentFrom(HEnvironment* environment) {
     ArenaAllocator* allocator = GetBlock()->GetGraph()->GetArena();
-    environment_ = new (allocator) HEnvironment(
-        allocator,
-        environment->Size(),
-        environment->GetDexFile(),
-        environment->GetMethodIdx(),
-        environment->GetDexPc());
+    environment_ = new (allocator) HEnvironment(allocator, *environment);
     environment_->CopyFrom(environment);
     if (environment->GetParent() != nullptr) {
       environment_->SetAndCopyParentChain(allocator, environment->GetParent());
@@ -1416,16 +1433,11 @@
   void CopyEnvironmentFromWithLoopPhiAdjustment(HEnvironment* environment,
                                                 HBasicBlock* block) {
     ArenaAllocator* allocator = GetBlock()->GetGraph()->GetArena();
-    environment_ = new (allocator) HEnvironment(
-        allocator,
-        environment->Size(),
-        environment->GetDexFile(),
-        environment->GetMethodIdx(),
-        environment->GetDexPc());
+    environment_ = new (allocator) HEnvironment(allocator, *environment);
+    environment_->CopyFromWithLoopPhiAdjustment(environment, block);
     if (environment->GetParent() != nullptr) {
       environment_->SetAndCopyParentChain(allocator, environment->GetParent());
     }
-    environment_->CopyFromWithLoopPhiAdjustment(environment, block);
   }
 
   // Returns the number of entries in the environment. Typically, that is the
@@ -2376,6 +2388,8 @@
 
   uint32_t GetDexMethodIndex() const { return dex_method_index_; }
 
+  InvokeType GetOriginalInvokeType() const { return original_invoke_type_; }
+
   Intrinsics GetIntrinsic() const {
     return intrinsic_;
   }
@@ -2392,13 +2406,15 @@
           uint32_t number_of_other_inputs,
           Primitive::Type return_type,
           uint32_t dex_pc,
-          uint32_t dex_method_index)
+          uint32_t dex_method_index,
+          InvokeType original_invoke_type)
     : HInstruction(SideEffects::All()),
       number_of_arguments_(number_of_arguments),
       inputs_(arena, number_of_arguments),
       return_type_(return_type),
       dex_pc_(dex_pc),
       dex_method_index_(dex_method_index),
+      original_invoke_type_(original_invoke_type),
       intrinsic_(Intrinsics::kNone) {
     uint32_t number_of_inputs = number_of_arguments + number_of_other_inputs;
     inputs_.SetSize(number_of_inputs);
@@ -2414,6 +2430,7 @@
   const Primitive::Type return_type_;
   const uint32_t dex_pc_;
   const uint32_t dex_method_index_;
+  const InvokeType original_invoke_type_;
   Intrinsics intrinsic_;
 
  private:
@@ -2445,8 +2462,8 @@
                 clinit_check_requirement == ClinitCheckRequirement::kExplicit ? 1u : 0u,
                 return_type,
                 dex_pc,
-                dex_method_index),
-        original_invoke_type_(original_invoke_type),
+                dex_method_index,
+                original_invoke_type),
         invoke_type_(invoke_type),
         is_recursive_(is_recursive),
         clinit_check_requirement_(clinit_check_requirement),
@@ -2459,7 +2476,6 @@
     return false;
   }
 
-  InvokeType GetOriginalInvokeType() const { return original_invoke_type_; }
   InvokeType GetInvokeType() const { return invoke_type_; }
   bool IsRecursive() const { return is_recursive_; }
   bool NeedsDexCache() const OVERRIDE { return !IsRecursive(); }
@@ -2517,7 +2533,6 @@
   }
 
  private:
-  const InvokeType original_invoke_type_;
   const InvokeType invoke_type_;
   const bool is_recursive_;
   ClinitCheckRequirement clinit_check_requirement_;
@@ -2536,7 +2551,7 @@
                  uint32_t dex_pc,
                  uint32_t dex_method_index,
                  uint32_t vtable_index)
-      : HInvoke(arena, number_of_arguments, 0u, return_type, dex_pc, dex_method_index),
+      : HInvoke(arena, number_of_arguments, 0u, return_type, dex_pc, dex_method_index, kVirtual),
         vtable_index_(vtable_index) {}
 
   bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE {
@@ -2562,7 +2577,7 @@
                    uint32_t dex_pc,
                    uint32_t dex_method_index,
                    uint32_t imt_index)
-      : HInvoke(arena, number_of_arguments, 0u, return_type, dex_pc, dex_method_index),
+      : HInvoke(arena, number_of_arguments, 0u, return_type, dex_pc, dex_method_index, kInterface),
         imt_index_(imt_index) {}
 
   bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE {
diff --git a/compiler/optimizing/nodes_test.cc b/compiler/optimizing/nodes_test.cc
index 2736453..782cde4 100644
--- a/compiler/optimizing/nodes_test.cc
+++ b/compiler/optimizing/nodes_test.cc
@@ -51,7 +51,7 @@
   exit_block->AddInstruction(new (&allocator) HExit());
 
   HEnvironment* environment = new (&allocator) HEnvironment(
-      &allocator, 1, graph->GetDexFile(), graph->GetMethodIdx(), 0);
+      &allocator, 1, graph->GetDexFile(), graph->GetMethodIdx(), 0, kStatic);
   null_check->SetRawEnvironment(environment);
   environment->SetRawEnvAt(0, parameter);
   parameter->AddEnvUseAt(null_check->GetEnvironment(), 0);
@@ -132,7 +132,7 @@
   ASSERT_TRUE(parameter1->GetUses().HasOnlyOneUse());
 
   HEnvironment* environment = new (&allocator) HEnvironment(
-      &allocator, 1, graph->GetDexFile(), graph->GetMethodIdx(), 0);
+      &allocator, 1, graph->GetDexFile(), graph->GetMethodIdx(), 0, kStatic);
   GrowableArray<HInstruction*> array(&allocator, 1);
   array.Add(parameter1);
 
@@ -143,13 +143,13 @@
   ASSERT_TRUE(parameter1->GetEnvUses().HasOnlyOneUse());
 
   HEnvironment* parent1 = new (&allocator) HEnvironment(
-      &allocator, 1, graph->GetDexFile(), graph->GetMethodIdx(), 0);
+      &allocator, 1, graph->GetDexFile(), graph->GetMethodIdx(), 0, kStatic);
   parent1->CopyFrom(array);
 
   ASSERT_EQ(parameter1->GetEnvUses().SizeSlow(), 2u);
 
   HEnvironment* parent2 = new (&allocator) HEnvironment(
-      &allocator, 1, graph->GetDexFile(), graph->GetMethodIdx(), 0);
+      &allocator, 1, graph->GetDexFile(), graph->GetMethodIdx(), 0, kStatic);
   parent2->CopyFrom(array);
   parent1->SetAndCopyParentChain(&allocator, parent2);
 
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index be9a424..b2e8ecd 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -518,7 +518,7 @@
                                                      dex_compilation_unit.GetClassDefIndex());
   ArenaAllocator arena(Runtime::Current()->GetArenaPool());
   HGraph* graph = new (&arena) HGraph(
-      &arena, dex_file, method_idx, requires_barrier,
+      &arena, dex_file, method_idx, requires_barrier, kInvalidInvokeType,
       compiler_driver->GetCompilerOptions().GetDebuggable());
 
   // For testing purposes, we put a special marker on method names that should be compiled
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index aac5211..c51d248 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -547,7 +547,8 @@
       current_locals_->Size(),
       GetGraph()->GetDexFile(),
       GetGraph()->GetMethodIdx(),
-      instruction->GetDexPc());
+      instruction->GetDexPc(),
+      GetGraph()->GetInvokeType());
   environment->CopyFrom(*current_locals_);
   instruction->SetRawEnvironment(environment);
 }
diff --git a/compiler/optimizing/stack_map_stream.cc b/compiler/optimizing/stack_map_stream.cc
index 89035a3..b446815 100644
--- a/compiler/optimizing/stack_map_stream.cc
+++ b/compiler/optimizing/stack_map_stream.cc
@@ -101,11 +101,13 @@
 
 void StackMapStream::BeginInlineInfoEntry(uint32_t method_index,
                                           uint32_t dex_pc,
+                                          InvokeType invoke_type,
                                           uint32_t num_dex_registers) {
   DCHECK(!in_inline_frame_);
   in_inline_frame_ = true;
   current_inline_info_.method_index = method_index;
   current_inline_info_.dex_pc = dex_pc;
+  current_inline_info_.invoke_type = invoke_type;
   current_inline_info_.num_dex_registers = num_dex_registers;
   current_inline_info_.dex_register_locations_start_index = dex_register_locations_.Size();
   if (num_dex_registers != 0) {
@@ -313,6 +315,7 @@
         InlineInfoEntry inline_entry = inline_infos_.Get(depth + entry.inline_infos_start_index);
         inline_info.SetMethodIndexAtDepth(depth, inline_entry.method_index);
         inline_info.SetDexPcAtDepth(depth, inline_entry.dex_pc);
+        inline_info.SetInvokeTypeAtDepth(depth, inline_entry.invoke_type);
         if (inline_entry.num_dex_registers == 0) {
           // No dex map available.
           inline_info.SetDexRegisterMapOffsetAtDepth(depth, StackMap::kNoDexRegisterMap);
diff --git a/compiler/optimizing/stack_map_stream.h b/compiler/optimizing/stack_map_stream.h
index 4c03f9f..0af983b 100644
--- a/compiler/optimizing/stack_map_stream.h
+++ b/compiler/optimizing/stack_map_stream.h
@@ -104,6 +104,7 @@
   struct InlineInfoEntry {
     uint32_t dex_pc;
     uint32_t method_index;
+    InvokeType invoke_type;
     uint32_t num_dex_registers;
     BitVector* live_dex_registers_mask;
     size_t dex_register_locations_start_index;
@@ -121,6 +122,7 @@
 
   void BeginInlineInfoEntry(uint32_t method_index,
                             uint32_t dex_pc,
+                            InvokeType invoke_type,
                             uint32_t num_dex_registers);
   void EndInlineInfoEntry();
 
diff --git a/compiler/optimizing/stack_map_test.cc b/compiler/optimizing/stack_map_test.cc
index e04fa98..98e14ea 100644
--- a/compiler/optimizing/stack_map_test.cc
+++ b/compiler/optimizing/stack_map_test.cc
@@ -128,9 +128,9 @@
   stream.BeginStackMapEntry(0, 64, 0x3, &sp_mask1, number_of_dex_registers, 2);
   stream.AddDexRegisterEntry(Kind::kInStack, 0);         // Short location.
   stream.AddDexRegisterEntry(Kind::kConstant, -2);       // Large location.
-  stream.BeginInlineInfoEntry(82, 3, number_of_dex_registers_in_inline_info);
+  stream.BeginInlineInfoEntry(82, 3, kDirect, number_of_dex_registers_in_inline_info);
   stream.EndInlineInfoEntry();
-  stream.BeginInlineInfoEntry(42, 2, number_of_dex_registers_in_inline_info);
+  stream.BeginInlineInfoEntry(42, 2, kStatic, number_of_dex_registers_in_inline_info);
   stream.EndInlineInfoEntry();
   stream.EndStackMapEntry();
 
@@ -218,6 +218,8 @@
     ASSERT_EQ(42u, inline_info.GetMethodIndexAtDepth(1));
     ASSERT_EQ(3u, inline_info.GetDexPcAtDepth(0));
     ASSERT_EQ(2u, inline_info.GetDexPcAtDepth(1));
+    ASSERT_EQ(kDirect, inline_info.GetInvokeTypeAtDepth(0));
+    ASSERT_EQ(kStatic, inline_info.GetInvokeTypeAtDepth(1));
   }
 
   // Second stack map.
@@ -519,10 +521,10 @@
   stream.AddDexRegisterEntry(Kind::kInStack, 0);
   stream.AddDexRegisterEntry(Kind::kConstant, 4);
 
-  stream.BeginInlineInfoEntry(42, 2, 1);
+  stream.BeginInlineInfoEntry(42, 2, kStatic, 1);
   stream.AddDexRegisterEntry(Kind::kInStack, 8);
   stream.EndInlineInfoEntry();
-  stream.BeginInlineInfoEntry(82, 3, 3);
+  stream.BeginInlineInfoEntry(82, 3, kStatic, 3);
   stream.AddDexRegisterEntry(Kind::kInStack, 16);
   stream.AddDexRegisterEntry(Kind::kConstant, 20);
   stream.AddDexRegisterEntry(Kind::kInRegister, 15);
@@ -535,15 +537,15 @@
   stream.AddDexRegisterEntry(Kind::kInStack, 56);
   stream.AddDexRegisterEntry(Kind::kConstant, 0);
 
-  stream.BeginInlineInfoEntry(42, 2, 1);
+  stream.BeginInlineInfoEntry(42, 2, kDirect, 1);
   stream.AddDexRegisterEntry(Kind::kInStack, 12);
   stream.EndInlineInfoEntry();
-  stream.BeginInlineInfoEntry(82, 3, 3);
+  stream.BeginInlineInfoEntry(82, 3, kStatic, 3);
   stream.AddDexRegisterEntry(Kind::kInStack, 80);
   stream.AddDexRegisterEntry(Kind::kConstant, 10);
   stream.AddDexRegisterEntry(Kind::kInRegister, 5);
   stream.EndInlineInfoEntry();
-  stream.BeginInlineInfoEntry(52, 5, 0);
+  stream.BeginInlineInfoEntry(52, 5, kVirtual, 0);
   stream.EndInlineInfoEntry();
 
   stream.EndStackMapEntry();
@@ -559,12 +561,12 @@
   stream.AddDexRegisterEntry(Kind::kInStack, 56);
   stream.AddDexRegisterEntry(Kind::kConstant, 0);
 
-  stream.BeginInlineInfoEntry(42, 2, 0);
+  stream.BeginInlineInfoEntry(42, 2, kVirtual, 0);
   stream.EndInlineInfoEntry();
-  stream.BeginInlineInfoEntry(52, 5, 1);
+  stream.BeginInlineInfoEntry(52, 5, kInterface, 1);
   stream.AddDexRegisterEntry(Kind::kInRegister, 2);
   stream.EndInlineInfoEntry();
-  stream.BeginInlineInfoEntry(52, 10, 2);
+  stream.BeginInlineInfoEntry(52, 10, kStatic, 2);
   stream.AddDexRegisterEntry(Kind::kNone, 0);
   stream.AddDexRegisterEntry(Kind::kInRegister, 3);
   stream.EndInlineInfoEntry();
@@ -590,8 +592,10 @@
     ASSERT_EQ(2u, if0.GetDepth());
     ASSERT_EQ(2u, if0.GetDexPcAtDepth(0));
     ASSERT_EQ(42u, if0.GetMethodIndexAtDepth(0));
+    ASSERT_EQ(kStatic, if0.GetInvokeTypeAtDepth(0));
     ASSERT_EQ(3u, if0.GetDexPcAtDepth(1));
     ASSERT_EQ(82u, if0.GetMethodIndexAtDepth(1));
+    ASSERT_EQ(kStatic, if0.GetInvokeTypeAtDepth(1));
 
     DexRegisterMap dex_registers1 = ci.GetDexRegisterMapAtDepth(0, if0, 1);
     ASSERT_EQ(8, dex_registers1.GetStackOffsetInBytes(0, 1, ci));
@@ -614,10 +618,13 @@
     ASSERT_EQ(3u, if1.GetDepth());
     ASSERT_EQ(2u, if1.GetDexPcAtDepth(0));
     ASSERT_EQ(42u, if1.GetMethodIndexAtDepth(0));
+    ASSERT_EQ(kDirect, if1.GetInvokeTypeAtDepth(0));
     ASSERT_EQ(3u, if1.GetDexPcAtDepth(1));
     ASSERT_EQ(82u, if1.GetMethodIndexAtDepth(1));
+    ASSERT_EQ(kStatic, if1.GetInvokeTypeAtDepth(1));
     ASSERT_EQ(5u, if1.GetDexPcAtDepth(2));
     ASSERT_EQ(52u, if1.GetMethodIndexAtDepth(2));
+    ASSERT_EQ(kVirtual, if1.GetInvokeTypeAtDepth(2));
 
     DexRegisterMap dex_registers1 = ci.GetDexRegisterMapAtDepth(0, if1, 1);
     ASSERT_EQ(12, dex_registers1.GetStackOffsetInBytes(0, 1, ci));
@@ -652,10 +659,13 @@
     ASSERT_EQ(3u, if2.GetDepth());
     ASSERT_EQ(2u, if2.GetDexPcAtDepth(0));
     ASSERT_EQ(42u, if2.GetMethodIndexAtDepth(0));
+    ASSERT_EQ(kVirtual, if2.GetInvokeTypeAtDepth(0));
     ASSERT_EQ(5u, if2.GetDexPcAtDepth(1));
     ASSERT_EQ(52u, if2.GetMethodIndexAtDepth(1));
+    ASSERT_EQ(kInterface, if2.GetInvokeTypeAtDepth(1));
     ASSERT_EQ(10u, if2.GetDexPcAtDepth(2));
     ASSERT_EQ(52u, if2.GetMethodIndexAtDepth(2));
+    ASSERT_EQ(kStatic, if2.GetInvokeTypeAtDepth(2));
 
     ASSERT_FALSE(if2.HasDexRegisterMapAtDepth(0));
 
diff --git a/runtime/debugger.cc b/runtime/debugger.cc
index 852ba49..0eb7f2b 100644
--- a/runtime/debugger.cc
+++ b/runtime/debugger.cc
@@ -3974,7 +3974,8 @@
 
   CHECK_EQ(sizeof(jvalue), sizeof(uint64_t));
 
-  JValue result = InvokeWithJValues(soa, pReq->receiver.Read(), soa.EncodeMethod(m.Get()),
+  ScopedLocalRef<jobject> ref(soa.Env(), soa.AddLocalReference<jobject>(pReq->receiver.Read()));
+  JValue result = InvokeWithJValues(soa, ref.get(), soa.EncodeMethod(m.Get()),
                                     reinterpret_cast<jvalue*>(pReq->arg_values));
 
   pReq->result_tag = BasicTagFromDescriptor(m.Get()->GetShorty());
diff --git a/runtime/indirect_reference_table-inl.h b/runtime/indirect_reference_table-inl.h
index 639be51..39d850f 100644
--- a/runtime/indirect_reference_table-inl.h
+++ b/runtime/indirect_reference_table-inl.h
@@ -82,6 +82,15 @@
   return obj;
 }
 
+inline void IndirectReferenceTable::Update(IndirectRef iref, mirror::Object* obj) {
+  if (!GetChecked(iref)) {
+    LOG(WARNING) << "IndirectReferenceTable Update failed to find reference " << iref;
+    return;
+  }
+  uint32_t idx = ExtractIndex(iref);
+  table_[idx].SetReference(obj);
+}
+
 }  // namespace art
 
 #endif  // ART_RUNTIME_INDIRECT_REFERENCE_TABLE_INL_H_
diff --git a/runtime/indirect_reference_table.h b/runtime/indirect_reference_table.h
index a0e53af..dea5dfd 100644
--- a/runtime/indirect_reference_table.h
+++ b/runtime/indirect_reference_table.h
@@ -213,6 +213,10 @@
   uint32_t GetSerial() const {
     return serial_;
   }
+  void SetReference(mirror::Object* obj) {
+    DCHECK_LT(serial_, kIRTPrevCount);
+    references_[serial_] = GcRoot<mirror::Object>(obj);
+  }
 
  private:
   uint32_t serial_;
@@ -294,6 +298,13 @@
   }
 
   /*
+   * Update an existing entry.
+   *
+   * Updates an existing indirect reference to point to a new object.
+   */
+  void Update(IndirectRef iref, mirror::Object* obj) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+
+  /*
    * Remove an existing entry.
    *
    * If the entry is not between the current top index and the bottom index
diff --git a/runtime/jni_internal.cc b/runtime/jni_internal.cc
index ca45f76..f435467 100644
--- a/runtime/jni_internal.cc
+++ b/runtime/jni_internal.cc
@@ -706,8 +706,7 @@
     CHECK_NON_NULL_ARGUMENT(obj);
     CHECK_NON_NULL_ARGUMENT(mid);
     ScopedObjectAccess soa(env);
-    JValue result(InvokeVirtualOrInterfaceWithJValues(soa, soa.Decode<mirror::Object*>(obj), mid,
-                                                      args));
+    JValue result(InvokeVirtualOrInterfaceWithJValues(soa, obj, mid, args));
     return soa.AddLocalReference<jobject>(result.GetL());
   }
 
@@ -733,8 +732,7 @@
     CHECK_NON_NULL_ARGUMENT_RETURN_ZERO(obj);
     CHECK_NON_NULL_ARGUMENT_RETURN_ZERO(mid);
     ScopedObjectAccess soa(env);
-    return InvokeVirtualOrInterfaceWithJValues(soa, soa.Decode<mirror::Object*>(obj), mid,
-                                               args).GetZ();
+    return InvokeVirtualOrInterfaceWithJValues(soa, obj, mid, args).GetZ();
   }
 
   static jbyte CallByteMethod(JNIEnv* env, jobject obj, jmethodID mid, ...) {
@@ -759,8 +757,7 @@
     CHECK_NON_NULL_ARGUMENT_RETURN_ZERO(obj);
     CHECK_NON_NULL_ARGUMENT_RETURN_ZERO(mid);
     ScopedObjectAccess soa(env);
-    return InvokeVirtualOrInterfaceWithJValues(soa, soa.Decode<mirror::Object*>(obj), mid,
-                                               args).GetB();
+    return InvokeVirtualOrInterfaceWithJValues(soa, obj, mid, args).GetB();
   }
 
   static jchar CallCharMethod(JNIEnv* env, jobject obj, jmethodID mid, ...) {
@@ -785,8 +782,7 @@
     CHECK_NON_NULL_ARGUMENT_RETURN_ZERO(obj);
     CHECK_NON_NULL_ARGUMENT_RETURN_ZERO(mid);
     ScopedObjectAccess soa(env);
-    return InvokeVirtualOrInterfaceWithJValues(soa, soa.Decode<mirror::Object*>(obj), mid,
-                                               args).GetC();
+    return InvokeVirtualOrInterfaceWithJValues(soa, obj, mid, args).GetC();
   }
 
   static jdouble CallDoubleMethod(JNIEnv* env, jobject obj, jmethodID mid, ...) {
@@ -811,8 +807,7 @@
     CHECK_NON_NULL_ARGUMENT_RETURN_ZERO(obj);
     CHECK_NON_NULL_ARGUMENT_RETURN_ZERO(mid);
     ScopedObjectAccess soa(env);
-    return InvokeVirtualOrInterfaceWithJValues(soa, soa.Decode<mirror::Object*>(obj), mid,
-                                               args).GetD();
+    return InvokeVirtualOrInterfaceWithJValues(soa, obj, mid, args).GetD();
   }
 
   static jfloat CallFloatMethod(JNIEnv* env, jobject obj, jmethodID mid, ...) {
@@ -837,8 +832,7 @@
     CHECK_NON_NULL_ARGUMENT_RETURN_ZERO(obj);
     CHECK_NON_NULL_ARGUMENT_RETURN_ZERO(mid);
     ScopedObjectAccess soa(env);
-    return InvokeVirtualOrInterfaceWithJValues(soa, soa.Decode<mirror::Object*>(obj), mid,
-                                               args).GetF();
+    return InvokeVirtualOrInterfaceWithJValues(soa, obj, mid, args).GetF();
   }
 
   static jint CallIntMethod(JNIEnv* env, jobject obj, jmethodID mid, ...) {
@@ -863,8 +857,7 @@
     CHECK_NON_NULL_ARGUMENT_RETURN_ZERO(obj);
     CHECK_NON_NULL_ARGUMENT_RETURN_ZERO(mid);
     ScopedObjectAccess soa(env);
-    return InvokeVirtualOrInterfaceWithJValues(soa, soa.Decode<mirror::Object*>(obj), mid,
-                                               args).GetI();
+    return InvokeVirtualOrInterfaceWithJValues(soa, obj, mid, args).GetI();
   }
 
   static jlong CallLongMethod(JNIEnv* env, jobject obj, jmethodID mid, ...) {
@@ -889,8 +882,7 @@
     CHECK_NON_NULL_ARGUMENT_RETURN_ZERO(obj);
     CHECK_NON_NULL_ARGUMENT_RETURN_ZERO(mid);
     ScopedObjectAccess soa(env);
-    return InvokeVirtualOrInterfaceWithJValues(soa, soa.Decode<mirror::Object*>(obj), mid,
-                                               args).GetJ();
+    return InvokeVirtualOrInterfaceWithJValues(soa, obj, mid, args).GetJ();
   }
 
   static jshort CallShortMethod(JNIEnv* env, jobject obj, jmethodID mid, ...) {
@@ -915,8 +907,7 @@
     CHECK_NON_NULL_ARGUMENT_RETURN_ZERO(obj);
     CHECK_NON_NULL_ARGUMENT_RETURN_ZERO(mid);
     ScopedObjectAccess soa(env);
-    return InvokeVirtualOrInterfaceWithJValues(soa, soa.Decode<mirror::Object*>(obj), mid,
-                                               args).GetS();
+    return InvokeVirtualOrInterfaceWithJValues(soa, obj, mid, args).GetS();
   }
 
   static void CallVoidMethod(JNIEnv* env, jobject obj, jmethodID mid, ...) {
@@ -940,7 +931,7 @@
     CHECK_NON_NULL_ARGUMENT_RETURN_VOID(obj);
     CHECK_NON_NULL_ARGUMENT_RETURN_VOID(mid);
     ScopedObjectAccess soa(env);
-    InvokeVirtualOrInterfaceWithJValues(soa, soa.Decode<mirror::Object*>(obj), mid, args);
+    InvokeVirtualOrInterfaceWithJValues(soa, obj, mid, args);
   }
 
   static jobject CallNonvirtualObjectMethod(JNIEnv* env, jobject obj, jclass, jmethodID mid, ...) {
@@ -969,7 +960,7 @@
     CHECK_NON_NULL_ARGUMENT(obj);
     CHECK_NON_NULL_ARGUMENT(mid);
     ScopedObjectAccess soa(env);
-    JValue result(InvokeWithJValues(soa, soa.Decode<mirror::Object*>(obj), mid, args));
+    JValue result(InvokeWithJValues(soa, obj, mid, args));
     return soa.AddLocalReference<jobject>(result.GetL());
   }
 
@@ -998,7 +989,7 @@
     CHECK_NON_NULL_ARGUMENT_RETURN_ZERO(obj);
     CHECK_NON_NULL_ARGUMENT_RETURN_ZERO(mid);
     ScopedObjectAccess soa(env);
-    return InvokeWithJValues(soa, soa.Decode<mirror::Object*>(obj), mid, args).GetZ();
+    return InvokeWithJValues(soa, obj, mid, args).GetZ();
   }
 
   static jbyte CallNonvirtualByteMethod(JNIEnv* env, jobject obj, jclass, jmethodID mid, ...) {
@@ -1025,7 +1016,7 @@
     CHECK_NON_NULL_ARGUMENT_RETURN_ZERO(obj);
     CHECK_NON_NULL_ARGUMENT_RETURN_ZERO(mid);
     ScopedObjectAccess soa(env);
-    return InvokeWithJValues(soa, soa.Decode<mirror::Object*>(obj), mid, args).GetB();
+    return InvokeWithJValues(soa, obj, mid, args).GetB();
   }
 
   static jchar CallNonvirtualCharMethod(JNIEnv* env, jobject obj, jclass, jmethodID mid, ...) {
@@ -1052,7 +1043,7 @@
     CHECK_NON_NULL_ARGUMENT_RETURN_ZERO(obj);
     CHECK_NON_NULL_ARGUMENT_RETURN_ZERO(mid);
     ScopedObjectAccess soa(env);
-    return InvokeWithJValues(soa, soa.Decode<mirror::Object*>(obj), mid, args).GetC();
+    return InvokeWithJValues(soa, obj, mid, args).GetC();
   }
 
   static jshort CallNonvirtualShortMethod(JNIEnv* env, jobject obj, jclass, jmethodID mid, ...) {
@@ -1079,7 +1070,7 @@
     CHECK_NON_NULL_ARGUMENT_RETURN_ZERO(obj);
     CHECK_NON_NULL_ARGUMENT_RETURN_ZERO(mid);
     ScopedObjectAccess soa(env);
-    return InvokeWithJValues(soa, soa.Decode<mirror::Object*>(obj), mid, args).GetS();
+    return InvokeWithJValues(soa, obj, mid, args).GetS();
   }
 
   static jint CallNonvirtualIntMethod(JNIEnv* env, jobject obj, jclass, jmethodID mid, ...) {
@@ -1106,7 +1097,7 @@
     CHECK_NON_NULL_ARGUMENT_RETURN_ZERO(obj);
     CHECK_NON_NULL_ARGUMENT_RETURN_ZERO(mid);
     ScopedObjectAccess soa(env);
-    return InvokeWithJValues(soa, soa.Decode<mirror::Object*>(obj), mid, args).GetI();
+    return InvokeWithJValues(soa, obj, mid, args).GetI();
   }
 
   static jlong CallNonvirtualLongMethod(JNIEnv* env, jobject obj, jclass, jmethodID mid, ...) {
@@ -1133,7 +1124,7 @@
     CHECK_NON_NULL_ARGUMENT_RETURN_ZERO(obj);
     CHECK_NON_NULL_ARGUMENT_RETURN_ZERO(mid);
     ScopedObjectAccess soa(env);
-    return InvokeWithJValues(soa, soa.Decode<mirror::Object*>(obj), mid, args).GetJ();
+    return InvokeWithJValues(soa, obj, mid, args).GetJ();
   }
 
   static jfloat CallNonvirtualFloatMethod(JNIEnv* env, jobject obj, jclass, jmethodID mid, ...) {
@@ -1160,7 +1151,7 @@
     CHECK_NON_NULL_ARGUMENT_RETURN_ZERO(obj);
     CHECK_NON_NULL_ARGUMENT_RETURN_ZERO(mid);
     ScopedObjectAccess soa(env);
-    return InvokeWithJValues(soa, soa.Decode<mirror::Object*>(obj), mid, args).GetF();
+    return InvokeWithJValues(soa, obj, mid, args).GetF();
   }
 
   static jdouble CallNonvirtualDoubleMethod(JNIEnv* env, jobject obj, jclass, jmethodID mid, ...) {
@@ -1187,7 +1178,7 @@
     CHECK_NON_NULL_ARGUMENT_RETURN_ZERO(obj);
     CHECK_NON_NULL_ARGUMENT_RETURN_ZERO(mid);
     ScopedObjectAccess soa(env);
-    return InvokeWithJValues(soa, soa.Decode<mirror::Object*>(obj), mid, args).GetD();
+    return InvokeWithJValues(soa, obj, mid, args).GetD();
   }
 
   static void CallNonvirtualVoidMethod(JNIEnv* env, jobject obj, jclass, jmethodID mid, ...) {
@@ -1213,7 +1204,7 @@
     CHECK_NON_NULL_ARGUMENT_RETURN_VOID(obj);
     CHECK_NON_NULL_ARGUMENT_RETURN_VOID(mid);
     ScopedObjectAccess soa(env);
-    InvokeWithJValues(soa, soa.Decode<mirror::Object*>(obj), mid, args);
+    InvokeWithJValues(soa, obj, mid, args);
   }
 
   static jfieldID GetFieldID(JNIEnv* env, jclass java_class, const char* name, const char* sig) {
diff --git a/runtime/jni_internal_test.cc b/runtime/jni_internal_test.cc
index 3d14a4e..581ef0e 100644
--- a/runtime/jni_internal_test.cc
+++ b/runtime/jni_internal_test.cc
@@ -858,8 +858,7 @@
   jstring s = reinterpret_cast<jstring>(env_->AllocObject(c));
   ASSERT_NE(s, nullptr);
   env_->CallVoidMethod(s, mid2);
-  // With the string change, this should now throw an UnsupportedOperationException.
-  ASSERT_EQ(JNI_TRUE, env_->ExceptionCheck());
+  ASSERT_EQ(JNI_FALSE, env_->ExceptionCheck());
   env_->ExceptionClear();
 
   mid = env_->GetMethodID(c, "length", "()I");
diff --git a/runtime/reflection.cc b/runtime/reflection.cc
index 49e1b8e..d321d27 100644
--- a/runtime/reflection.cc
+++ b/runtime/reflection.cc
@@ -21,6 +21,7 @@
 #include "common_throws.h"
 #include "dex_file-inl.h"
 #include "entrypoints/entrypoint_utils.h"
+#include "indirect_reference_table-inl.h"
 #include "jni_internal.h"
 #include "mirror/abstract_method.h"
 #include "mirror/art_method-inl.h"
@@ -449,6 +450,11 @@
   }
 
   mirror::ArtMethod* method = soa.DecodeMethod(mid);
+  bool is_string_init = method->GetDeclaringClass()->IsStringClass() && method->IsConstructor();
+  if (is_string_init) {
+    // Replace calls to String.<init> with equivalent StringFactory call.
+    method = soa.DecodeMethod(WellKnownClasses::StringInitToStringFactoryMethodID(mid));
+  }
   mirror::Object* receiver = method->IsStatic() ? nullptr : soa.Decode<mirror::Object*>(obj);
   uint32_t shorty_len = 0;
   const char* shorty = method->GetShorty(&shorty_len);
@@ -456,11 +462,15 @@
   ArgArray arg_array(shorty, shorty_len);
   arg_array.BuildArgArrayFromVarArgs(soa, receiver, args);
   InvokeWithArgArray(soa, method, &arg_array, &result, shorty);
+  if (is_string_init) {
+    // For string init, remap original receiver to StringFactory result.
+    soa.Self()->GetJniEnv()->locals.Update(obj, result.GetL());
+  }
   return result;
 }
 
-JValue InvokeWithJValues(const ScopedObjectAccessAlreadyRunnable& soa, mirror::Object* receiver,
-                         jmethodID mid, jvalue* args) {
+JValue InvokeWithJValues(const ScopedObjectAccessAlreadyRunnable& soa, jobject obj, jmethodID mid,
+                         jvalue* args) {
   // We want to make sure that the stack is not within a small distance from the
   // protected region in case we are calling into a leaf function whose stack
   // check has been elided.
@@ -470,17 +480,27 @@
   }
 
   mirror::ArtMethod* method = soa.DecodeMethod(mid);
+  bool is_string_init = method->GetDeclaringClass()->IsStringClass() && method->IsConstructor();
+  if (is_string_init) {
+    // Replace calls to String.<init> with equivalent StringFactory call.
+    method = soa.DecodeMethod(WellKnownClasses::StringInitToStringFactoryMethodID(mid));
+  }
+  mirror::Object* receiver = method->IsStatic() ? nullptr : soa.Decode<mirror::Object*>(obj);
   uint32_t shorty_len = 0;
   const char* shorty = method->GetShorty(&shorty_len);
   JValue result;
   ArgArray arg_array(shorty, shorty_len);
   arg_array.BuildArgArrayFromJValues(soa, receiver, args);
   InvokeWithArgArray(soa, method, &arg_array, &result, shorty);
+  if (is_string_init) {
+    // For string init, remap original receiver to StringFactory result.
+    soa.Self()->GetJniEnv()->locals.Update(obj, result.GetL());
+  }
   return result;
 }
 
 JValue InvokeVirtualOrInterfaceWithJValues(const ScopedObjectAccessAlreadyRunnable& soa,
-                                           mirror::Object* receiver, jmethodID mid, jvalue* args) {
+                                           jobject obj, jmethodID mid, jvalue* args) {
   // We want to make sure that the stack is not within a small distance from the
   // protected region in case we are calling into a leaf function whose stack
   // check has been elided.
@@ -489,13 +509,24 @@
     return JValue();
   }
 
+  mirror::Object* receiver = soa.Decode<mirror::Object*>(obj);
   mirror::ArtMethod* method = FindVirtualMethod(receiver, soa.DecodeMethod(mid));
+  bool is_string_init = method->GetDeclaringClass()->IsStringClass() && method->IsConstructor();
+  if (is_string_init) {
+    // Replace calls to String.<init> with equivalent StringFactory call.
+    method = soa.DecodeMethod(WellKnownClasses::StringInitToStringFactoryMethodID(mid));
+    receiver = nullptr;
+  }
   uint32_t shorty_len = 0;
   const char* shorty = method->GetShorty(&shorty_len);
   JValue result;
   ArgArray arg_array(shorty, shorty_len);
   arg_array.BuildArgArrayFromJValues(soa, receiver, args);
   InvokeWithArgArray(soa, method, &arg_array, &result, shorty);
+  if (is_string_init) {
+    // For string init, remap original receiver to StringFactory result.
+    soa.Self()->GetJniEnv()->locals.Update(obj, result.GetL());
+  }
   return result;
 }
 
@@ -511,12 +542,22 @@
 
   mirror::Object* receiver = soa.Decode<mirror::Object*>(obj);
   mirror::ArtMethod* method = FindVirtualMethod(receiver, soa.DecodeMethod(mid));
+  bool is_string_init = method->GetDeclaringClass()->IsStringClass() && method->IsConstructor();
+  if (is_string_init) {
+    // Replace calls to String.<init> with equivalent StringFactory call.
+    method = soa.DecodeMethod(WellKnownClasses::StringInitToStringFactoryMethodID(mid));
+    receiver = nullptr;
+  }
   uint32_t shorty_len = 0;
   const char* shorty = method->GetShorty(&shorty_len);
   JValue result;
   ArgArray arg_array(shorty, shorty_len);
   arg_array.BuildArgArrayFromVarArgs(soa, receiver, args);
   InvokeWithArgArray(soa, method, &arg_array, &result, shorty);
+  if (is_string_init) {
+    // For string init, remap original receiver to StringFactory result.
+    soa.Self()->GetJniEnv()->locals.Update(obj, result.GetL());
+  }
   return result;
 }
 
diff --git a/runtime/reflection.h b/runtime/reflection.h
index 37f8a6a..6b5ffc7 100644
--- a/runtime/reflection.h
+++ b/runtime/reflection.h
@@ -49,12 +49,12 @@
                          va_list args)
     SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
-JValue InvokeWithJValues(const ScopedObjectAccessAlreadyRunnable& soa, mirror::Object* receiver,
-                         jmethodID mid, jvalue* args)
+JValue InvokeWithJValues(const ScopedObjectAccessAlreadyRunnable& soa, jobject obj, jmethodID mid,
+                         jvalue* args)
     SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
 JValue InvokeVirtualOrInterfaceWithJValues(const ScopedObjectAccessAlreadyRunnable& soa,
-                                           mirror::Object* receiver, jmethodID mid, jvalue* args)
+                                           jobject obj, jmethodID mid, jvalue* args)
     SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
 JValue InvokeVirtualOrInterfaceWithVarArgs(const ScopedObjectAccessAlreadyRunnable& soa,
diff --git a/runtime/reflection_test.cc b/runtime/reflection_test.cc
index a62bc5e..36e444a 100644
--- a/runtime/reflection_test.cc
+++ b/runtime/reflection_test.cc
@@ -133,7 +133,8 @@
     mirror::ArtMethod* method;
     mirror::Object* receiver;
     ReflectionTestMakeExecutable(&method, &receiver, is_static, "nop", "()V");
-    InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), nullptr);
+    ScopedLocalRef<jobject> receiver_ref(soa.Env(), soa.AddLocalReference<jobject>(receiver));
+    InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), nullptr);
   }
 
   void InvokeIdentityByteMethod(bool is_static) {
@@ -141,22 +142,23 @@
     mirror::ArtMethod* method;
     mirror::Object* receiver;
     ReflectionTestMakeExecutable(&method, &receiver, is_static, "identity", "(B)B");
+    ScopedLocalRef<jobject> receiver_ref(soa.Env(), soa.AddLocalReference<jobject>(receiver));
     jvalue args[1];
 
     args[0].b = 0;
-    JValue result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    JValue result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_EQ(0, result.GetB());
 
     args[0].b = -1;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_EQ(-1, result.GetB());
 
     args[0].b = SCHAR_MAX;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_EQ(SCHAR_MAX, result.GetB());
 
     args[0].b = (SCHAR_MIN << 24) >> 24;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_EQ(SCHAR_MIN, result.GetB());
   }
 
@@ -165,22 +167,23 @@
     mirror::ArtMethod* method;
     mirror::Object* receiver;
     ReflectionTestMakeExecutable(&method, &receiver, is_static, "identity", "(I)I");
+    ScopedLocalRef<jobject> receiver_ref(soa.Env(), soa.AddLocalReference<jobject>(receiver));
     jvalue args[1];
 
     args[0].i = 0;
-    JValue result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    JValue result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_EQ(0, result.GetI());
 
     args[0].i = -1;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_EQ(-1, result.GetI());
 
     args[0].i = INT_MAX;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_EQ(INT_MAX, result.GetI());
 
     args[0].i = INT_MIN;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_EQ(INT_MIN, result.GetI());
   }
 
@@ -189,22 +192,23 @@
     mirror::ArtMethod* method;
     mirror::Object* receiver;
     ReflectionTestMakeExecutable(&method, &receiver, is_static, "identity", "(D)D");
+    ScopedLocalRef<jobject> receiver_ref(soa.Env(), soa.AddLocalReference<jobject>(receiver));
     jvalue args[1];
 
     args[0].d = 0.0;
-    JValue result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    JValue result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_DOUBLE_EQ(0.0, result.GetD());
 
     args[0].d = -1.0;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_DOUBLE_EQ(-1.0, result.GetD());
 
     args[0].d = DBL_MAX;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_DOUBLE_EQ(DBL_MAX, result.GetD());
 
     args[0].d = DBL_MIN;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_DOUBLE_EQ(DBL_MIN, result.GetD());
   }
 
@@ -213,26 +217,27 @@
     mirror::ArtMethod* method;
     mirror::Object* receiver;
     ReflectionTestMakeExecutable(&method, &receiver, is_static, "sum", "(II)I");
+    ScopedLocalRef<jobject> receiver_ref(soa.Env(), soa.AddLocalReference<jobject>(receiver));
     jvalue args[2];
 
     args[0].i = 1;
     args[1].i = 2;
-    JValue result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    JValue result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_EQ(3, result.GetI());
 
     args[0].i = -2;
     args[1].i = 5;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_EQ(3, result.GetI());
 
     args[0].i = INT_MAX;
     args[1].i = INT_MIN;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_EQ(-1, result.GetI());
 
     args[0].i = INT_MAX;
     args[1].i = INT_MAX;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_EQ(-2, result.GetI());
   }
 
@@ -241,36 +246,37 @@
     mirror::ArtMethod* method;
     mirror::Object* receiver;
     ReflectionTestMakeExecutable(&method, &receiver, is_static, "sum", "(III)I");
+    ScopedLocalRef<jobject> receiver_ref(soa.Env(), soa.AddLocalReference<jobject>(receiver));
     jvalue args[3];
 
     args[0].i = 0;
     args[1].i = 0;
     args[2].i = 0;
-    JValue result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    JValue result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_EQ(0, result.GetI());
 
     args[0].i = 1;
     args[1].i = 2;
     args[2].i = 3;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_EQ(6, result.GetI());
 
     args[0].i = -1;
     args[1].i = 2;
     args[2].i = -3;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_EQ(-2, result.GetI());
 
     args[0].i = INT_MAX;
     args[1].i = INT_MIN;
     args[2].i = INT_MAX;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_EQ(2147483646, result.GetI());
 
     args[0].i = INT_MAX;
     args[1].i = INT_MAX;
     args[2].i = INT_MAX;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_EQ(2147483645, result.GetI());
   }
 
@@ -279,41 +285,42 @@
     mirror::ArtMethod* method;
     mirror::Object* receiver;
     ReflectionTestMakeExecutable(&method, &receiver, is_static, "sum", "(IIII)I");
+    ScopedLocalRef<jobject> receiver_ref(soa.Env(), soa.AddLocalReference<jobject>(receiver));
     jvalue args[4];
 
     args[0].i = 0;
     args[1].i = 0;
     args[2].i = 0;
     args[3].i = 0;
-    JValue result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    JValue result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_EQ(0, result.GetI());
 
     args[0].i = 1;
     args[1].i = 2;
     args[2].i = 3;
     args[3].i = 4;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_EQ(10, result.GetI());
 
     args[0].i = -1;
     args[1].i = 2;
     args[2].i = -3;
     args[3].i = 4;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_EQ(2, result.GetI());
 
     args[0].i = INT_MAX;
     args[1].i = INT_MIN;
     args[2].i = INT_MAX;
     args[3].i = INT_MIN;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_EQ(-2, result.GetI());
 
     args[0].i = INT_MAX;
     args[1].i = INT_MAX;
     args[2].i = INT_MAX;
     args[3].i = INT_MAX;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_EQ(-4, result.GetI());
   }
 
@@ -322,6 +329,7 @@
     mirror::ArtMethod* method;
     mirror::Object* receiver;
     ReflectionTestMakeExecutable(&method, &receiver, is_static, "sum", "(IIIII)I");
+    ScopedLocalRef<jobject> receiver_ref(soa.Env(), soa.AddLocalReference<jobject>(receiver));
     jvalue args[5];
 
     args[0].i = 0;
@@ -329,7 +337,7 @@
     args[2].i = 0;
     args[3].i = 0;
     args[4].i = 0;
-    JValue result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    JValue result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_EQ(0, result.GetI());
 
     args[0].i = 1;
@@ -337,7 +345,7 @@
     args[2].i = 3;
     args[3].i = 4;
     args[4].i = 5;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_EQ(15, result.GetI());
 
     args[0].i = -1;
@@ -345,7 +353,7 @@
     args[2].i = -3;
     args[3].i = 4;
     args[4].i = -5;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_EQ(-3, result.GetI());
 
     args[0].i = INT_MAX;
@@ -353,7 +361,7 @@
     args[2].i = INT_MAX;
     args[3].i = INT_MIN;
     args[4].i = INT_MAX;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_EQ(2147483645, result.GetI());
 
     args[0].i = INT_MAX;
@@ -361,7 +369,7 @@
     args[2].i = INT_MAX;
     args[3].i = INT_MAX;
     args[4].i = INT_MAX;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_EQ(2147483643, result.GetI());
   }
 
@@ -370,31 +378,32 @@
     mirror::ArtMethod* method;
     mirror::Object* receiver;
     ReflectionTestMakeExecutable(&method, &receiver, is_static, "sum", "(DD)D");
+    ScopedLocalRef<jobject> receiver_ref(soa.Env(), soa.AddLocalReference<jobject>(receiver));
     jvalue args[2];
 
     args[0].d = 0.0;
     args[1].d = 0.0;
-    JValue result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    JValue result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_DOUBLE_EQ(0.0, result.GetD());
 
     args[0].d = 1.0;
     args[1].d = 2.0;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_DOUBLE_EQ(3.0, result.GetD());
 
     args[0].d = 1.0;
     args[1].d = -2.0;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_DOUBLE_EQ(-1.0, result.GetD());
 
     args[0].d = DBL_MAX;
     args[1].d = DBL_MIN;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_DOUBLE_EQ(1.7976931348623157e308, result.GetD());
 
     args[0].d = DBL_MAX;
     args[1].d = DBL_MAX;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_DOUBLE_EQ(INFINITY, result.GetD());
   }
 
@@ -403,24 +412,25 @@
     mirror::ArtMethod* method;
     mirror::Object* receiver;
     ReflectionTestMakeExecutable(&method, &receiver, is_static, "sum", "(DDD)D");
+    ScopedLocalRef<jobject> receiver_ref(soa.Env(), soa.AddLocalReference<jobject>(receiver));
     jvalue args[3];
 
     args[0].d = 0.0;
     args[1].d = 0.0;
     args[2].d = 0.0;
-    JValue result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    JValue result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_DOUBLE_EQ(0.0, result.GetD());
 
     args[0].d = 1.0;
     args[1].d = 2.0;
     args[2].d = 3.0;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_DOUBLE_EQ(6.0, result.GetD());
 
     args[0].d = 1.0;
     args[1].d = -2.0;
     args[2].d = 3.0;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_DOUBLE_EQ(2.0, result.GetD());
   }
 
@@ -429,27 +439,28 @@
     mirror::ArtMethod* method;
     mirror::Object* receiver;
     ReflectionTestMakeExecutable(&method, &receiver, is_static, "sum", "(DDDD)D");
+    ScopedLocalRef<jobject> receiver_ref(soa.Env(), soa.AddLocalReference<jobject>(receiver));
     jvalue args[4];
 
     args[0].d = 0.0;
     args[1].d = 0.0;
     args[2].d = 0.0;
     args[3].d = 0.0;
-    JValue result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    JValue result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_DOUBLE_EQ(0.0, result.GetD());
 
     args[0].d = 1.0;
     args[1].d = 2.0;
     args[2].d = 3.0;
     args[3].d = 4.0;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_DOUBLE_EQ(10.0, result.GetD());
 
     args[0].d = 1.0;
     args[1].d = -2.0;
     args[2].d = 3.0;
     args[3].d = -4.0;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_DOUBLE_EQ(-2.0, result.GetD());
   }
 
@@ -458,6 +469,7 @@
     mirror::ArtMethod* method;
     mirror::Object* receiver;
     ReflectionTestMakeExecutable(&method, &receiver, is_static, "sum", "(DDDDD)D");
+    ScopedLocalRef<jobject> receiver_ref(soa.Env(), soa.AddLocalReference<jobject>(receiver));
     jvalue args[5];
 
     args[0].d = 0.0;
@@ -465,7 +477,7 @@
     args[2].d = 0.0;
     args[3].d = 0.0;
     args[4].d = 0.0;
-    JValue result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    JValue result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_DOUBLE_EQ(0.0, result.GetD());
 
     args[0].d = 1.0;
@@ -473,7 +485,7 @@
     args[2].d = 3.0;
     args[3].d = 4.0;
     args[4].d = 5.0;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_DOUBLE_EQ(15.0, result.GetD());
 
     args[0].d = 1.0;
@@ -481,7 +493,7 @@
     args[2].d = 3.0;
     args[3].d = -4.0;
     args[4].d = 5.0;
-    result = InvokeWithJValues(soa, receiver, soa.EncodeMethod(method), args);
+    result = InvokeWithJValues(soa, receiver_ref.get(), soa.EncodeMethod(method), args);
     EXPECT_DOUBLE_EQ(3.0, result.GetD());
   }
 
diff --git a/runtime/stack_map.h b/runtime/stack_map.h
index 16ae772..f07fb74 100644
--- a/runtime/stack_map.h
+++ b/runtime/stack_map.h
@@ -735,31 +735,43 @@
   }
 
   uint32_t GetMethodIndexAtDepth(uint8_t depth) const {
-    return region_.LoadUnaligned<uint32_t>(kFixedSize + depth * SingleEntrySize());
+    return region_.LoadUnaligned<uint32_t>(
+        kFixedSize + depth * SingleEntrySize() + kMethodIndexOffset);
   }
 
   void SetMethodIndexAtDepth(uint8_t depth, uint32_t index) {
-    region_.StoreUnaligned<uint32_t>(kFixedSize + depth * SingleEntrySize(), index);
+    region_.StoreUnaligned<uint32_t>(
+        kFixedSize + depth * SingleEntrySize() + kMethodIndexOffset, index);
   }
 
   uint32_t GetDexPcAtDepth(uint8_t depth) const {
     return region_.LoadUnaligned<uint32_t>(
-        kFixedSize + depth * SingleEntrySize() + sizeof(uint32_t));
+        kFixedSize + depth * SingleEntrySize() + kDexPcOffset);
   }
 
   void SetDexPcAtDepth(uint8_t depth, uint32_t dex_pc) {
     region_.StoreUnaligned<uint32_t>(
-        kFixedSize + depth * SingleEntrySize() + sizeof(uint32_t), dex_pc);
+        kFixedSize + depth * SingleEntrySize() + kDexPcOffset, dex_pc);
+  }
+
+  uint8_t GetInvokeTypeAtDepth(uint8_t depth) const {
+    return region_.LoadUnaligned<uint8_t>(
+        kFixedSize + depth * SingleEntrySize() + kInvokeTypeOffset);
+  }
+
+  void SetInvokeTypeAtDepth(uint8_t depth, uint8_t invoke_type) {
+    region_.StoreUnaligned<uint8_t>(
+        kFixedSize + depth * SingleEntrySize() + kInvokeTypeOffset, invoke_type);
   }
 
   uint32_t GetDexRegisterMapOffsetAtDepth(uint8_t depth) const {
     return region_.LoadUnaligned<uint32_t>(
-        kFixedSize + depth * SingleEntrySize() + sizeof(uint32_t) + sizeof(uint32_t));
+        kFixedSize + depth * SingleEntrySize() + kDexRegisterMapOffset);
   }
 
   void SetDexRegisterMapOffsetAtDepth(uint8_t depth, uint32_t offset) {
     region_.StoreUnaligned<uint32_t>(
-        kFixedSize + depth * SingleEntrySize() + sizeof(uint32_t) + sizeof(uint32_t), offset);
+        kFixedSize + depth * SingleEntrySize() + kDexRegisterMapOffset, offset);
   }
 
   bool HasDexRegisterMapAtDepth(uint8_t depth) const {
@@ -767,7 +779,7 @@
   }
 
   static size_t SingleEntrySize() {
-    return sizeof(uint32_t) + sizeof(uint32_t) + sizeof(uint32_t);
+    return kFixedEntrySize;
   }
 
   void Dump(std::ostream& os, const CodeInfo& info, uint16_t* number_of_dex_registers) const;
@@ -778,6 +790,12 @@
   static constexpr int kDepthOffset = 0;
   static constexpr int kFixedSize = kDepthOffset + sizeof(uint8_t);
 
+  static constexpr int kMethodIndexOffset = 0;
+  static constexpr int kDexPcOffset = kMethodIndexOffset + sizeof(uint32_t);
+  static constexpr int kInvokeTypeOffset = kDexPcOffset + sizeof(uint32_t);
+  static constexpr int kDexRegisterMapOffset = kInvokeTypeOffset + sizeof(uint8_t);
+  static constexpr int kFixedEntrySize = kDexRegisterMapOffset + sizeof(uint32_t);
+
   MemoryRegion region_;
 
   friend class CodeInfo;
diff --git a/runtime/thread.cc b/runtime/thread.cc
index 148bb6d..2145c9c 100644
--- a/runtime/thread.cc
+++ b/runtime/thread.cc
@@ -216,7 +216,8 @@
     // Invoke the 'run' method of our java.lang.Thread.
     mirror::Object* receiver = self->tlsPtr_.opeer;
     jmethodID mid = WellKnownClasses::java_lang_Thread_run;
-    InvokeVirtualOrInterfaceWithJValues(soa, receiver, mid, nullptr);
+    ScopedLocalRef<jobject> ref(soa.Env(), soa.AddLocalReference<jobject>(receiver));
+    InvokeVirtualOrInterfaceWithJValues(soa, ref.get(), mid, nullptr);
   }
   // Detach and delete self.
   Runtime::Current()->GetThreadList()->Unregister(self);
@@ -1886,7 +1887,8 @@
       jv_args[i].l = cause.get();
       ++i;
     }
-    InvokeWithJValues(soa, exception.Get(), soa.EncodeMethod(exception_init_method), jv_args);
+    ScopedLocalRef<jobject> ref(soa.Env(), soa.AddLocalReference<jobject>(exception.Get()));
+    InvokeWithJValues(soa, ref.get(), soa.EncodeMethod(exception_init_method), jv_args);
     if (LIKELY(!IsExceptionPending())) {
       SetException(exception.Get());
     }
diff --git a/test/004-JniTest/jni_test.cc b/test/004-JniTest/jni_test.cc
index cdc5461..1ec0cf2 100644
--- a/test/004-JniTest/jni_test.cc
+++ b/test/004-JniTest/jni_test.cc
@@ -550,21 +550,58 @@
 }
 
 extern "C" JNIEXPORT void JNICALL Java_Main_testNewStringObject(JNIEnv* env, jclass) {
-  const char* string = "Test";
-  int length = strlen(string);
   jclass c = env->FindClass("java/lang/String");
-  assert(c != NULL);
-  jmethodID method = env->GetMethodID(c, "<init>", "([B)V");
-  assert(method != NULL);
+  assert(c != nullptr);
+
+  jmethodID mid1 = env->GetMethodID(c, "<init>", "()V");
+  assert(mid1 != nullptr);
   assert(!env->ExceptionCheck());
-  jbyteArray array = env->NewByteArray(length);
-  env->SetByteArrayRegion(array, 0, length, reinterpret_cast<const jbyte*>(string));
-  jobject o = env->NewObject(c, method, array);
-  assert(o != NULL);
-  jstring s = reinterpret_cast<jstring>(o);
-  assert(env->GetStringLength(s) == length);
-  assert(env->GetStringUTFLength(s) == length);
+  jmethodID mid2 = env->GetMethodID(c, "<init>", "([B)V");
+  assert(mid2 != nullptr);
+  assert(!env->ExceptionCheck());
+  jmethodID mid3 = env->GetMethodID(c, "<init>", "([C)V");
+  assert(mid3 != nullptr);
+  assert(!env->ExceptionCheck());
+  jmethodID mid4 = env->GetMethodID(c, "<init>", "(Ljava/lang/String;)V");
+  assert(mid4 != nullptr);
+  assert(!env->ExceptionCheck());
+
+  const char* test_array = "Test";
+  int byte_array_length = strlen(test_array);
+  jbyteArray byte_array = env->NewByteArray(byte_array_length);
+  env->SetByteArrayRegion(byte_array, 0, byte_array_length, reinterpret_cast<const jbyte*>(test_array));
+
+  // Test NewObject
+  jstring s = reinterpret_cast<jstring>(env->NewObject(c, mid2, byte_array));
+  assert(s != nullptr);
+  assert(env->GetStringLength(s) == byte_array_length);
+  assert(env->GetStringUTFLength(s) == byte_array_length);
   const char* chars = env->GetStringUTFChars(s, nullptr);
-  assert(strcmp(string, chars) == 0);
+  assert(strcmp(test_array, chars) == 0);
   env->ReleaseStringUTFChars(s, chars);
+
+  // Test AllocObject and Call(Nonvirtual)VoidMethod
+  jstring s1 = reinterpret_cast<jstring>(env->AllocObject(c));
+  assert(s1 != nullptr);
+  jstring s2 = reinterpret_cast<jstring>(env->AllocObject(c));
+  assert(s2 != nullptr);
+  jstring s3 = reinterpret_cast<jstring>(env->AllocObject(c));
+  assert(s3 != nullptr);
+  jstring s4 = reinterpret_cast<jstring>(env->AllocObject(c));
+  assert(s4 != nullptr);
+
+  jcharArray char_array = env->NewCharArray(5);
+  jstring string_arg = env->NewStringUTF("helloworld");
+
+  // With Var Args
+  env->CallVoidMethod(s1, mid1);
+  env->CallNonvirtualVoidMethod(s2, c, mid2, byte_array);
+
+  // With JValues
+  jvalue args3[1];
+  args3[0].l = char_array;
+  jvalue args4[1];
+  args4[0].l = string_arg;
+  env->CallVoidMethodA(s3, mid3, args3);
+  env->CallNonvirtualVoidMethodA(s4, c, mid4, args4);
 }
diff --git a/test/020-string/src/Main.java b/test/020-string/src/Main.java
index bb8ce1f..b876e6a 100644
--- a/test/020-string/src/Main.java
+++ b/test/020-string/src/Main.java
@@ -14,6 +14,9 @@
  * limitations under the License.
  */
 
+import java.nio.charset.Charset;
+import java.io.UnsupportedEncodingException;
+
 /**
  * Simple string test.
  */
@@ -21,6 +24,7 @@
     public static void main(String args[]) {
         basicTest();
         indexTest();
+        constructorTest();
     }
 
     public static void basicTest() {
@@ -81,4 +85,36 @@
             subStr.indexOf('&') + ":" +
             baseStr.indexOf(0x12341234));
     }
+
+    public static void constructorTest() {
+        byte[] byteArray = "byteArray".getBytes();
+        char[] charArray = new char[] { 'c', 'h', 'a', 'r', 'A', 'r', 'r', 'a', 'y' };
+        String charsetName = "US-ASCII";
+        Charset charset = Charset.forName("UTF-8");
+        String string = "string";
+        StringBuffer stringBuffer = new StringBuffer("stringBuffer");
+        int [] codePoints = new int[] { 65, 66, 67, 68, 69 };
+        StringBuilder stringBuilder = new StringBuilder("stringBuilder");
+
+        String s1 = new String();
+        String s2 = new String(byteArray);
+        String s3 = new String(byteArray, 1);
+        String s4 = new String(byteArray, 0, 4);
+        String s5 = new String(byteArray, 2, 4, 5);
+
+        try {
+            String s6 = new String(byteArray, 2, 4, charsetName);
+            String s7 = new String(byteArray, charsetName);
+        } catch (UnsupportedEncodingException e) {
+            System.out.println("Got unexpected UnsupportedEncodingException");
+        }
+        String s8 = new String(byteArray, 3, 3, charset);
+        String s9 = new String(byteArray, charset);
+        String s10 = new String(charArray);
+        String s11 = new String(charArray, 0, 4);
+        String s12 = new String(string);
+        String s13 = new String(stringBuffer);
+        String s14 = new String(codePoints, 1, 3);
+        String s15 = new String(stringBuilder);
+    }
 }
diff --git a/test/476-checker-ctor-memory-barrier/src/Main.java b/test/476-checker-ctor-memory-barrier/src/Main.java
index 75cb1d7..f24dc4a 100644
--- a/test/476-checker-ctor-memory-barrier/src/Main.java
+++ b/test/476-checker-ctor-memory-barrier/src/Main.java
@@ -27,9 +27,8 @@
   public ClassWithFinals obj;
 
   // CHECK-START: void ClassWithFinals.<init>(boolean) register (after)
-  // CHECK:     MemoryBarrier kind:StoreStore
-  // CHECK-NOT: {{.*}}
-  // CHECK:     ReturnVoid
+  // CHECK:      MemoryBarrier kind:StoreStore
+  // CHECK-NEXT: ReturnVoid
   public ClassWithFinals(boolean cond) {
     x = 0;
     if (cond) {
@@ -39,18 +38,16 @@
   }
 
   // CHECK-START: void ClassWithFinals.<init>() register (after)
-  // CHECK:     MemoryBarrier kind:StoreStore
-  // CHECK-NOT: {{.*}}
-  // CHECK:     ReturnVoid
+  // CHECK:      MemoryBarrier kind:StoreStore
+  // CHECK-NEXT: ReturnVoid
   public ClassWithFinals() {
     x = 0;
   }
 
   // CHECK-START: void ClassWithFinals.<init>(int) register (after)
-  // CHECK:     MemoryBarrier kind:StoreStore
-  // CHECK:     MemoryBarrier kind:StoreStore
-  // CHECK-NOT: {{.*}}
-  // CHECK:     ReturnVoid
+  // CHECK:      MemoryBarrier kind:StoreStore
+  // CHECK:      MemoryBarrier kind:StoreStore
+  // CHECK-NEXT: ReturnVoid
   public ClassWithFinals(int x) {
     // This should have two barriers:
     //   - one for the constructor
@@ -62,33 +59,32 @@
 
 class InheritFromClassWithFinals extends ClassWithFinals {
   // CHECK-START: void InheritFromClassWithFinals.<init>() register (after)
-  // CHECK:     MemoryBarrier kind:StoreStore
-  // CHECK-NOT: {{.*}}
-  // CHECK:     ReturnVoid
+  // CHECK:      MemoryBarrier kind:StoreStore
+  // CHECK-NEXT: ReturnVoid
 
   // CHECK-START: void InheritFromClassWithFinals.<init>() register (after)
-  // CHECK-NOT: InvokeStaticOrDirect
+  // CHECK-NOT:  InvokeStaticOrDirect
   public InheritFromClassWithFinals() {
     // Should inline the super constructor.
   }
 
   // CHECK-START: void InheritFromClassWithFinals.<init>(boolean) register (after)
-  // CHECK:     InvokeStaticOrDirect
+  // CHECK:      InvokeStaticOrDirect
 
   // CHECK-START: void InheritFromClassWithFinals.<init>(boolean) register (after)
-  // CHECK-NOT: MemoryBarrier kind:StoreStore
+  // CHECK-NOT:  MemoryBarrier kind:StoreStore
   public InheritFromClassWithFinals(boolean cond) {
     super(cond);
     // should not inline the super constructor
   }
 
   // CHECK-START: void InheritFromClassWithFinals.<init>(int) register (after)
-  // CHECK:     MemoryBarrier kind:StoreStore
-  // CHECK:     MemoryBarrier kind:StoreStore
-  // CHECK:     ReturnVoid
+  // CHECK:      MemoryBarrier kind:StoreStore
+  // CHECK:      MemoryBarrier kind:StoreStore
+  // CHECK:      ReturnVoid
 
   // CHECK-START: void InheritFromClassWithFinals.<init>(int) register (after)
-  // CHECK-NOT: InvokeStaticOrDirect
+  // CHECK-NOT:  InvokeStaticOrDirect
   public InheritFromClassWithFinals(int unused) {
     // Should inline the super constructor and insert a memory barrier.
 
@@ -101,9 +97,8 @@
   final int y;
 
   // CHECK-START: void HaveFinalsAndInheritFromClassWithFinals.<init>() register (after)
-  // CHECK:     MemoryBarrier kind:StoreStore
-  // CHECK-NOT: {{.*}}
-  // CHECK:     ReturnVoid
+  // CHECK:      MemoryBarrier kind:StoreStore
+  // CHECK-NEXT: ReturnVoid
 
   // CHECK-START: void HaveFinalsAndInheritFromClassWithFinals.<init>() register (after)
   // CHECK-NOT: InvokeStaticOrDirect
@@ -113,10 +108,9 @@
   }
 
   // CHECK-START: void HaveFinalsAndInheritFromClassWithFinals.<init>(boolean) register (after)
-  // CHECK:     InvokeStaticOrDirect
-  // CHECK:     MemoryBarrier kind:StoreStore
-  // CHECK-NOT: {{.*}}
-  // CHECK:     ReturnVoid
+  // CHECK:      InvokeStaticOrDirect
+  // CHECK:      MemoryBarrier kind:StoreStore
+  // CHECK-NEXT: ReturnVoid
   public HaveFinalsAndInheritFromClassWithFinals(boolean cond) {
     super(cond);
     // should not inline the super constructor
@@ -124,14 +118,13 @@
   }
 
   // CHECK-START: void HaveFinalsAndInheritFromClassWithFinals.<init>(int) register (after)
-  // CHECK:     MemoryBarrier kind:StoreStore
-  // CHECK:     MemoryBarrier kind:StoreStore
-  // CHECK:     MemoryBarrier kind:StoreStore
-  // CHECK-NOT: {{.*}}
-  // CHECK:     ReturnVoid
+  // CHECK:      MemoryBarrier kind:StoreStore
+  // CHECK:      MemoryBarrier kind:StoreStore
+  // CHECK:      MemoryBarrier kind:StoreStore
+  // CHECK-NEXT: ReturnVoid
 
   // CHECK-START: void HaveFinalsAndInheritFromClassWithFinals.<init>(int) register (after)
-  // CHECK-NOT: InvokeStaticOrDirect
+  // CHECK-NOT:  InvokeStaticOrDirect
   public HaveFinalsAndInheritFromClassWithFinals(int unused) {
     // Should inline the super constructor and keep just one memory barrier.
     y = 0;
@@ -146,55 +139,51 @@
 public class Main {
 
   // CHECK-START: ClassWithFinals Main.noInlineNoConstructorBarrier() register (after)
-  // CHECK:     InvokeStaticOrDirect
+  // CHECK:      InvokeStaticOrDirect
 
   // CHECK-START: ClassWithFinals Main.noInlineNoConstructorBarrier() register (after)
-  // CHECK-NOT: MemoryBarrier kind:StoreStore
+  // CHECK-NOT:  MemoryBarrier kind:StoreStore
   public static ClassWithFinals noInlineNoConstructorBarrier() {
     return new ClassWithFinals(false);
   }
 
   // CHECK-START: void Main.inlineNew() register (after)
-  // CHECK:     MemoryBarrier kind:StoreStore
-  // CHECK-NOT: {{.*}}
-  // CHECK:     ReturnVoid
+  // CHECK:      MemoryBarrier kind:StoreStore
+  // CHECK-NEXT: ReturnVoid
 
   // CHECK-START: void Main.inlineNew() register (after)
-  // CHECK-NOT: InvokeStaticOrDirect
+  // CHECK-NOT:  InvokeStaticOrDirect
   public static void inlineNew() {
     new ClassWithFinals();
   }
 
   // CHECK-START: void Main.inlineNew1() register (after)
-  // CHECK:     MemoryBarrier kind:StoreStore
-  // CHECK-NOT: {{.*}}
-  // CHECK:     ReturnVoid
+  // CHECK:      MemoryBarrier kind:StoreStore
+  // CHECK-NEXT: ReturnVoid
 
   // CHECK-START: void Main.inlineNew1() register (after)
-  // CHECK-NOT: InvokeStaticOrDirect
+  // CHECK-NOT:  InvokeStaticOrDirect
   public static void inlineNew1() {
     new InheritFromClassWithFinals();
   }
 
   // CHECK-START: void Main.inlineNew2() register (after)
-  // CHECK:     MemoryBarrier kind:StoreStore
-  // CHECK-NOT: {{.*}}
-  // CHECK:     ReturnVoid
+  // CHECK:      MemoryBarrier kind:StoreStore
+  // CHECK-NEXT: ReturnVoid
 
   // CHECK-START: void Main.inlineNew2() register (after)
-  // CHECK-NOT: InvokeStaticOrDirect
+  // CHECK-NOT:  InvokeStaticOrDirect
   public static void inlineNew2() {
     new HaveFinalsAndInheritFromClassWithFinals();
   }
 
   // CHECK-START: void Main.inlineNew3() register (after)
-  // CHECK:     MemoryBarrier kind:StoreStore
-  // CHECK:     MemoryBarrier kind:StoreStore
-  // CHECK-NOT: {{.*}}
-  // CHECK:     ReturnVoid
+  // CHECK:      MemoryBarrier kind:StoreStore
+  // CHECK:      MemoryBarrier kind:StoreStore
+  // CHECK-NEXT: ReturnVoid
 
   // CHECK-START: void Main.inlineNew3() register (after)
-  // CHECK-NOT: InvokeStaticOrDirect
+  // CHECK-NOT:  InvokeStaticOrDirect
   public static void inlineNew3() {
     new HaveFinalsAndInheritFromClassWithFinals();
     new HaveFinalsAndInheritFromClassWithFinals();
diff --git a/test/run-test b/test/run-test
index 12b743d..ed33099 100755
--- a/test/run-test
+++ b/test/run-test
@@ -75,7 +75,7 @@
 check_cmd="check"
 output="output.txt"
 build_output="build-output.txt"
-cfg_output="cfg-output.txt"
+cfg_output="graph.cfg"
 lib="libartd.so"
 run_args="--quiet"
 build_args=""
diff --git a/tools/checker/file_format/checker/parser.py b/tools/checker/file_format/checker/parser.py
index d7a38da..4eed391 100644
--- a/tools/checker/file_format/checker/parser.py
+++ b/tools/checker/file_format/checker/parser.py
@@ -54,6 +54,11 @@
   if plainLine is not None:
     return (plainLine, TestAssertion.Variant.InOrder, lineNo), None
 
+  # 'CHECK-NEXT' lines are in-order but must match the very next line.
+  nextLine = __extractLine(prefix + "-NEXT", line)
+  if nextLine is not None:
+    return (nextLine, TestAssertion.Variant.NextLine, lineNo), None
+
   # 'CHECK-DAG' lines are no-order assertions.
   dagLine = __extractLine(prefix + "-DAG", line)
   if dagLine is not None:
diff --git a/tools/checker/file_format/checker/struct.py b/tools/checker/file_format/checker/struct.py
index 381c92b..6a54142 100644
--- a/tools/checker/file_format/checker/struct.py
+++ b/tools/checker/file_format/checker/struct.py
@@ -42,7 +42,7 @@
     self.startLineNo = startLineNo
 
     if not self.name:
-      Logger.fail("Test case does not have a name", self.parent.fileName, self.startLineNo)
+      Logger.fail("Test case does not have a name", self.fileName, self.startLineNo)
 
     self.parent.addTestCase(self)
 
@@ -51,6 +51,13 @@
     return self.parent.fileName
 
   def addAssertion(self, new_assertion):
+    if new_assertion.variant == TestAssertion.Variant.NextLine:
+      if not self.assertions or \
+         (self.assertions[-1].variant != TestAssertion.Variant.InOrder and \
+          self.assertions[-1].variant != TestAssertion.Variant.NextLine):
+        Logger.fail("A next-line assertion can only be placed after an "
+                    "in-order assertion or another next-line assertion.",
+                    new_assertion.fileName, new_assertion.lineNo)
     self.assertions.append(new_assertion)
 
   def __eq__(self, other):
@@ -63,7 +70,7 @@
 
   class Variant(object):
     """Supported types of assertions."""
-    InOrder, DAG, Not = range(3)
+    InOrder, NextLine, DAG, Not = range(4)
 
   def __init__(self, parent, variant, originalText, lineNo):
     assert isinstance(parent, TestCase)
diff --git a/tools/checker/file_format/checker/test.py b/tools/checker/file_format/checker/test.py
index 475e8c3..453deed 100644
--- a/tools/checker/file_format/checker/test.py
+++ b/tools/checker/file_format/checker/test.py
@@ -192,9 +192,12 @@
 
   def assertParsesTo(self, checkerText, expectedData):
     expectedFile = self.createFile(expectedData)
-    actualFile = ParseCheckerStream("<test_file>", "CHECK", io.StringIO(ToUnicode(checkerText)))
+    actualFile = self.parse(checkerText)
     return self.assertEqual(expectedFile, actualFile)
 
+  def parse(self, checkerText):
+    return ParseCheckerStream("<test_file>", "CHECK", io.StringIO(ToUnicode(checkerText)))
+
   def test_EmptyFile(self):
     self.assertParsesTo("", [])
 
@@ -227,12 +230,40 @@
     self.assertParsesTo(
       """
         // CHECK-START: Example Group
-        // CHECK:     foo
-        // CHECK-NOT: bar
-        // CHECK-DAG: abc
-        // CHECK-DAG: def
+        // CHECK:      foo1
+        // CHECK:      foo2
+        // CHECK-NEXT: foo3
+        // CHECK-NEXT: foo4
+        // CHECK-NOT:  bar
+        // CHECK-DAG:  abc
+        // CHECK-DAG:  def
       """,
-      [ ( "Example Group", [ ("foo", TestAssertion.Variant.InOrder),
+      [ ( "Example Group", [ ("foo1", TestAssertion.Variant.InOrder),
+                             ("foo2", TestAssertion.Variant.InOrder),
+                             ("foo3", TestAssertion.Variant.NextLine),
+                             ("foo4", TestAssertion.Variant.NextLine),
                              ("bar", TestAssertion.Variant.Not),
                              ("abc", TestAssertion.Variant.DAG),
                              ("def", TestAssertion.Variant.DAG) ] ) ])
+
+  def test_MisplacedNext(self):
+    with self.assertRaises(CheckerException):
+      self.parse(
+        """
+          // CHECK-START: Example Group
+          // CHECK-DAG:  foo
+          // CHECK-NEXT: bar
+        """)
+    with self.assertRaises(CheckerException):
+      self.parse(
+        """
+          // CHECK-START: Example Group
+          // CHECK-NOT:  foo
+          // CHECK-NEXT: bar
+        """)
+    with self.assertRaises(CheckerException):
+      self.parse(
+        """
+          // CHECK-START: Example Group
+          // CHECK-NEXT: bar
+        """)
diff --git a/tools/checker/match/file.py b/tools/checker/match/file.py
index 116fe9a..b22211a 100644
--- a/tools/checker/match/file.py
+++ b/tools/checker/match/file.py
@@ -12,127 +12,143 @@
 # See the License for the specific language governing permissions and
 # limitations under the License.
 
+from collections                      import namedtuple
 from common.immutables                import ImmutableDict
 from common.logger                    import Logger
 from file_format.c1visualizer.struct  import C1visualizerFile, C1visualizerPass
 from file_format.checker.struct       import CheckerFile, TestCase, TestAssertion
 from match.line                       import MatchLines
 
-def __headAndTail(list):
-  return list[0], list[1:]
+MatchScope = namedtuple("MatchScope", ["start", "end"])
+MatchInfo = namedtuple("MatchInfo", ["scope", "variables"])
 
-def __splitByVariant(lines, variant):
-  """ Splits a list of check lines at index 'i' such that lines[i] is the first
-      element whose variant is not equal to the given parameter.
+class MatchFailedException(Exception):
+  def __init__(self, assertion, lineNo):
+    self.assertion = assertion
+    self.lineNo = lineNo
+
+def splitIntoGroups(assertions):
+  """ Breaks up a list of assertions, grouping instructions which should be
+      tested in the same scope (consecutive DAG and NOT instructions).
+   """
+  splitAssertions = []
+  lastVariant = None
+  for assertion in assertions:
+    if (assertion.variant == lastVariant and
+        assertion.variant in [TestAssertion.Variant.DAG, TestAssertion.Variant.Not]):
+      splitAssertions[-1].append(assertion)
+    else:
+      splitAssertions.append([assertion])
+      lastVariant = assertion.variant
+  return splitAssertions
+
+def findMatchingLine(assertion, c1Pass, scope, variables, excludeLines=[]):
+  """ Finds the first line in `c1Pass` which matches `assertion`.
+
+  Scan only lines numbered between `scope.start` and `scope.end` and not on the
+  `excludeLines` list.
+
+  Returns the index of the `c1Pass` line matching the assertion and variables
+  values after the match.
+
+  Raises MatchFailedException if no such `c1Pass` line can be found.
   """
-  i = 0
-  while i < len(lines) and lines[i].variant == variant:
-    i += 1
-  return lines[:i], lines[i:]
+  for i in range(scope.start, scope.end):
+    if i in excludeLines: continue
+    newVariables = MatchLines(assertion, c1Pass.body[i], variables)
+    if newVariables is not None:
+      return MatchInfo(MatchScope(i, i), newVariables)
+  raise MatchFailedException(assertion, scope.start)
 
-def __nextIndependentChecks(checkLines):
-  """ Extracts the first sequence of check lines which are independent of each
-      other's match location, i.e. either consecutive DAG lines or a single
-      InOrder line. Any Not lines preceeding this sequence are also extracted.
+def matchDagGroup(assertions, c1Pass, scope, variables):
+  """ Attempts to find matching `c1Pass` lines for a group of DAG assertions.
+
+  Assertions are matched in the list order and variable values propagated. Only
+  lines in `scope` are scanned and each line can only match one assertion.
+
+  Returns the range of `c1Pass` lines covered by this group (min/max of matching
+  line numbers) and the variable values after the match of the last assertion.
+
+  Raises MatchFailedException when an assertion cannot be satisfied.
   """
-  notChecks, checkLines = __splitByVariant(checkLines, TestAssertion.Variant.Not)
-  if not checkLines:
-    return notChecks, [], []
-
-  head, tail = __headAndTail(checkLines)
-  if head.variant == TestAssertion.Variant.InOrder:
-    return notChecks, [head], tail
-  else:
-    assert head.variant == TestAssertion.Variant.DAG
-    independentChecks, checkLines = __splitByVariant(checkLines, TestAssertion.Variant.DAG)
-    return notChecks, independentChecks, checkLines
-
-def __findFirstMatch(checkLine, outputLines, startLineNo, lineFilter, varState):
-  """ If successful, returns the line number of the first output line matching
-      the check line and the updated variable state. Otherwise returns -1 and
-      None, respectively. The 'lineFilter' parameter can be used to supply a
-      list of line numbers (counting from 1) which should be skipped.
-  """
-  matchLineNo = startLineNo
-  for outputLine in outputLines:
-    if matchLineNo not in lineFilter:
-      newVarState = MatchLines(checkLine, outputLine, varState)
-      if newVarState is not None:
-        return matchLineNo, newVarState
-    matchLineNo += 1
-  return -1, None
-
-def __matchIndependentChecks(checkLines, outputLines, startLineNo, varState):
-  """ Matches the given positive check lines against the output in order of
-      appearance. Variable state is propagated but the scope of the search
-      remains the same for all checks. Each output line can only be matched
-      once. If all check lines are matched, the resulting variable state is
-      returned together with the remaining output. The function also returns
-      output lines which appear before either of the matched lines so they can
-      be tested against Not checks.
-  """
-  # If no checks are provided, skip over the entire output.
-  if not checkLines:
-    return outputLines, [], startLineNo + len(outputLines), varState
-
-  # Keep track of which lines have been matched.
   matchedLines = []
+  for assertion in assertions:
+    assert assertion.variant == TestAssertion.Variant.DAG
+    match = findMatchingLine(assertion, c1Pass, scope, variables, matchedLines)
+    variables = match.variables
+    assert match.scope.start == match.scope.end
+    assert match.scope.start not in matchedLines
+    matchedLines.append(match.scope.start)
+  return MatchInfo(MatchScope(min(matchedLines), max(matchedLines)), variables)
 
-  # Find first unused output line which matches each check line.
-  for checkLine in checkLines:
-    matchLineNo, varState = \
-      __findFirstMatch(checkLine, outputLines, startLineNo, matchedLines, varState)
-    if varState is None:
-      Logger.testFailed("Could not match check line \"" + checkLine.originalText + "\" " +
-                        "starting from output line " + str(startLineNo),
-                        checkLine.fileName, checkLine.lineNo)
-    matchedLines.append(matchLineNo)
+def testNotGroup(assertions, c1Pass, scope, variables):
+  """ Verifies that none of the given NOT assertions matches a line inside
+      the given `scope` of `c1Pass` lines.
 
-  # Return new variable state and the output lines which lie outside the
-  # match locations of this independent group.
-  minMatchLineNo = min(matchedLines)
-  maxMatchLineNo = max(matchedLines)
-  preceedingLines = outputLines[:minMatchLineNo - startLineNo]
-  remainingLines = outputLines[maxMatchLineNo - startLineNo + 1:]
-  return preceedingLines, remainingLines, maxMatchLineNo + 1, varState
-
-def __matchNotLines(checkLines, outputLines, startLineNo, varState):
-  """ Makes sure that the given check lines do not match any of the given output
-      lines. Variable state does not change.
+  Raises MatchFailedException if an assertion matches a line in the scope.
   """
-  for checkLine in checkLines:
-    assert checkLine.variant == TestAssertion.Variant.Not
-    matchLineNo, matchVarState = \
-      __findFirstMatch(checkLine, outputLines, startLineNo, [], varState)
-    if matchVarState is not None:
-      Logger.testFailed("CHECK-NOT line \"" + checkLine.originalText + "\" matches output line " + \
-                        str(matchLineNo), checkLine.fileName, checkLine.lineNo)
+  for i in range(scope.start, scope.end):
+    line = c1Pass.body[i]
+    for assertion in assertions:
+      assert assertion.variant == TestAssertion.Variant.Not
+      if MatchLines(assertion, line, variables) is not None:
+        raise MatchFailedException(assertion, i)
 
-def __matchGroups(checkGroup, outputGroup):
-  """ Matches the check lines in this group against an output group. It is
-      responsible for running the checks in the right order and scope, and
-      for propagating the variable state between the check lines.
+def MatchTestCase(testCase, c1Pass):
+  """ Runs a test case against a C1visualizer graph dump.
+
+  Raises MatchFailedException when an assertion cannot be satisfied.
   """
-  varState = ImmutableDict()
-  checkLines = checkGroup.assertions
-  outputLines = outputGroup.body
-  startLineNo = outputGroup.startLineNo
+  assert testCase.name == c1Pass.name
 
-  while checkLines:
-    # Extract the next sequence of location-independent checks to be matched.
-    notChecks, independentChecks, checkLines = __nextIndependentChecks(checkLines)
+  matchFrom = 0
+  variables = ImmutableDict()
+  c1Length = len(c1Pass.body)
 
-    # Match the independent checks.
-    notOutput, outputLines, newStartLineNo, newVarState = \
-      __matchIndependentChecks(independentChecks, outputLines, startLineNo, varState)
+  # NOT assertions are verified retrospectively, once the scope is known.
+  pendingNotAssertions = None
 
-    # Run the Not checks against the output lines which lie between the last
-    # two independent groups or the bounds of the output.
-    __matchNotLines(notChecks, notOutput, startLineNo, varState)
+  # Prepare assertions by grouping those that are verified in the same scope.
+  # We also add None as an EOF assertion that will set scope for NOTs.
+  assertionGroups = splitIntoGroups(testCase.assertions)
+  assertionGroups.append(None)
 
-    # Update variable state.
-    startLineNo = newStartLineNo
-    varState = newVarState
+  for assertionGroup in assertionGroups:
+    if assertionGroup is None:
+      # EOF marker always matches the last+1 line of c1Pass.
+      match = MatchInfo(MatchScope(c1Length, c1Length), None)
+    elif assertionGroup[0].variant == TestAssertion.Variant.Not:
+      # NOT assertions will be tested together with the next group.
+      assert not pendingNotAssertions
+      pendingNotAssertions = assertionGroup
+      continue
+    elif assertionGroup[0].variant == TestAssertion.Variant.InOrder:
+      # Single in-order assertion. Find the first line that matches.
+      assert len(assertionGroup) == 1
+      scope = MatchScope(matchFrom, c1Length)
+      match = findMatchingLine(assertionGroup[0], c1Pass, scope, variables)
+    elif assertionGroup[0].variant == TestAssertion.Variant.NextLine:
+      # Single next-line assertion. Test if the current line matches.
+      assert len(assertionGroup) == 1
+      scope = MatchScope(matchFrom, matchFrom + 1)
+      match = findMatchingLine(assertionGroup[0], c1Pass, scope, variables)
+    else:
+      # A group of DAG assertions. Match them all starting from the same point.
+      assert assertionGroup[0].variant == TestAssertion.Variant.DAG
+      scope = MatchScope(matchFrom, c1Length)
+      match = matchDagGroup(assertionGroup, c1Pass, scope, variables)
+
+    if pendingNotAssertions:
+      # Previous group were NOT assertions. Make sure they don't match any lines
+      # in the [matchFrom, match.start) scope.
+      scope = MatchScope(matchFrom, match.scope.start)
+      testNotGroup(pendingNotAssertions, c1Pass, scope, variables)
+      pendingNotAssertions = None
+
+    # Update state.
+    assert matchFrom <= match.scope.end
+    matchFrom = match.scope.end + 1
+    variables = match.variables
 
 def MatchFiles(checkerFile, c1File):
   for testCase in checkerFile.testCases:
@@ -141,8 +157,18 @@
     # match a check group against the first output group of the same name.
     c1Pass = c1File.findPass(testCase.name)
     if c1Pass is None:
-      Logger.fail("Test case \"" + testCase.name + "\" not found in the C1visualizer output",
+      Logger.fail("Test case \"{}\" not found in the CFG file".format(testCase.name),
                   testCase.fileName, testCase.startLineNo)
+
     Logger.startTest(testCase.name)
-    __matchGroups(testCase, c1Pass)
-    Logger.testPassed()
+    try:
+      MatchTestCase(testCase, c1Pass)
+      Logger.testPassed()
+    except MatchFailedException as e:
+      lineNo = c1Pass.startLineNo + e.lineNo
+      if e.assertion.variant == TestAssertion.Variant.Not:
+        Logger.testFailed("NOT assertion matched line {}".format(lineNo),
+                          e.assertion.fileName, e.assertion.lineNo)
+      else:
+        Logger.testFailed("Assertion could not be matched starting from line {}".format(lineNo),
+                          e.assertion.fileName, e.assertion.lineNo)
diff --git a/tools/checker/match/test.py b/tools/checker/match/test.py
index 97725ad..348c1d2 100644
--- a/tools/checker/match/test.py
+++ b/tools/checker/match/test.py
@@ -18,7 +18,7 @@
 from file_format.c1visualizer.struct import C1visualizerFile, C1visualizerPass
 from file_format.checker.parser      import ParseCheckerStream, ParseCheckerAssertion
 from file_format.checker.struct      import CheckerFile, TestCase, TestAssertion, RegexExpression
-from match.file                      import MatchFiles
+from match.file                      import MatchTestCase, MatchFailedException
 from match.line                      import MatchLines
 
 import io
@@ -38,68 +38,71 @@
                       ToUnicode(c1String),
                       ImmutableDict(varState))
 
-  def matches(self, checkerString, c1String, varState={}):
-    return self.tryMatch(checkerString, c1String, varState) is not None
+  def assertMatches(self, checkerString, c1String, varState={}):
+    self.assertIsNotNone(self.tryMatch(checkerString, c1String, varState))
+
+  def assertDoesNotMatch(self, checkerString, c1String, varState={}):
+    self.assertIsNone(self.tryMatch(checkerString, c1String, varState))
 
   def test_TextAndWhitespace(self):
-    self.assertTrue(self.matches("foo", "foo"))
-    self.assertTrue(self.matches("foo", "  foo  "))
-    self.assertTrue(self.matches("foo", "foo bar"))
-    self.assertFalse(self.matches("foo", "XfooX"))
-    self.assertFalse(self.matches("foo", "zoo"))
+    self.assertMatches("foo", "foo")
+    self.assertMatches("foo", "  foo  ")
+    self.assertMatches("foo", "foo bar")
+    self.assertDoesNotMatch("foo", "XfooX")
+    self.assertDoesNotMatch("foo", "zoo")
 
-    self.assertTrue(self.matches("foo bar", "foo   bar"))
-    self.assertTrue(self.matches("foo bar", "abc foo bar def"))
-    self.assertTrue(self.matches("foo bar", "foo foo bar bar"))
+    self.assertMatches("foo bar", "foo   bar")
+    self.assertMatches("foo bar", "abc foo bar def")
+    self.assertMatches("foo bar", "foo foo bar bar")
 
-    self.assertTrue(self.matches("foo bar", "foo X bar"))
-    self.assertFalse(self.matches("foo bar", "foo Xbar"))
+    self.assertMatches("foo bar", "foo X bar")
+    self.assertDoesNotMatch("foo bar", "foo Xbar")
 
   def test_Pattern(self):
-    self.assertTrue(self.matches("foo{{A|B}}bar", "fooAbar"))
-    self.assertTrue(self.matches("foo{{A|B}}bar", "fooBbar"))
-    self.assertFalse(self.matches("foo{{A|B}}bar", "fooCbar"))
+    self.assertMatches("foo{{A|B}}bar", "fooAbar")
+    self.assertMatches("foo{{A|B}}bar", "fooBbar")
+    self.assertDoesNotMatch("foo{{A|B}}bar", "fooCbar")
 
   def test_VariableReference(self):
-    self.assertTrue(self.matches("foo<<X>>bar", "foobar", {"X": ""}))
-    self.assertTrue(self.matches("foo<<X>>bar", "fooAbar", {"X": "A"}))
-    self.assertTrue(self.matches("foo<<X>>bar", "fooBbar", {"X": "B"}))
-    self.assertFalse(self.matches("foo<<X>>bar", "foobar", {"X": "A"}))
-    self.assertFalse(self.matches("foo<<X>>bar", "foo bar", {"X": "A"}))
+    self.assertMatches("foo<<X>>bar", "foobar", {"X": ""})
+    self.assertMatches("foo<<X>>bar", "fooAbar", {"X": "A"})
+    self.assertMatches("foo<<X>>bar", "fooBbar", {"X": "B"})
+    self.assertDoesNotMatch("foo<<X>>bar", "foobar", {"X": "A"})
+    self.assertDoesNotMatch("foo<<X>>bar", "foo bar", {"X": "A"})
     with self.assertRaises(CheckerException):
-      self.assertTrue(self.matches("foo<<X>>bar", "foobar", {}))
+      self.tryMatch("foo<<X>>bar", "foobar", {})
 
   def test_VariableDefinition(self):
-    self.assertTrue(self.matches("foo<<X:A|B>>bar", "fooAbar"))
-    self.assertTrue(self.matches("foo<<X:A|B>>bar", "fooBbar"))
-    self.assertFalse(self.matches("foo<<X:A|B>>bar", "fooCbar"))
+    self.assertMatches("foo<<X:A|B>>bar", "fooAbar")
+    self.assertMatches("foo<<X:A|B>>bar", "fooBbar")
+    self.assertDoesNotMatch("foo<<X:A|B>>bar", "fooCbar")
 
     env = self.tryMatch("foo<<X:A.*B>>bar", "fooABbar", {})
     self.assertEqual(env, {"X": "AB"})
     env = self.tryMatch("foo<<X:A.*B>>bar", "fooAxxBbar", {})
     self.assertEqual(env, {"X": "AxxB"})
 
-    self.assertTrue(self.matches("foo<<X:A|B>>bar<<X>>baz", "fooAbarAbaz"))
-    self.assertTrue(self.matches("foo<<X:A|B>>bar<<X>>baz", "fooBbarBbaz"))
-    self.assertFalse(self.matches("foo<<X:A|B>>bar<<X>>baz", "fooAbarBbaz"))
+    self.assertMatches("foo<<X:A|B>>bar<<X>>baz", "fooAbarAbaz")
+    self.assertMatches("foo<<X:A|B>>bar<<X>>baz", "fooBbarBbaz")
+    self.assertDoesNotMatch("foo<<X:A|B>>bar<<X>>baz", "fooAbarBbaz")
 
   def test_NoVariableRedefinition(self):
     with self.assertRaises(CheckerException):
-      self.matches("<<X:...>><<X>><<X:...>><<X>>", "foofoobarbar")
+      self.tryMatch("<<X:...>><<X>><<X:...>><<X>>", "foofoobarbar")
 
   def test_EnvNotChangedOnPartialMatch(self):
     env = {"Y": "foo"}
-    self.assertFalse(self.matches("<<X:A>>bar", "Abaz", env))
+    self.assertDoesNotMatch("<<X:A>>bar", "Abaz", env)
     self.assertFalse("X" in env.keys())
 
   def test_VariableContentEscaped(self):
-    self.assertTrue(self.matches("<<X:..>>foo<<X>>", ".*foo.*"))
-    self.assertFalse(self.matches("<<X:..>>foo<<X>>", ".*fooAAAA"))
+    self.assertMatches("<<X:..>>foo<<X>>", ".*foo.*")
+    self.assertDoesNotMatch("<<X:..>>foo<<X>>", ".*fooAAAA")
 
 
 class MatchFiles_Test(unittest.TestCase):
 
-  def matches(self, checkerString, c1String):
+  def assertMatches(self, checkerString, c1String):
     checkerString = \
       """
         // CHECK-START: MyMethod MyPass
@@ -119,22 +122,24 @@
       """
     checkerFile = ParseCheckerStream("<test-file>", "CHECK", io.StringIO(ToUnicode(checkerString)))
     c1File = ParseC1visualizerStream("<c1-file>", io.StringIO(ToUnicode(c1String)))
-    try:
-      MatchFiles(checkerFile, c1File)
-      return True
-    except CheckerException:
-      return False
+    assert len(checkerFile.testCases) == 1
+    assert len(c1File.passes) == 1
+    MatchTestCase(checkerFile.testCases[0], c1File.passes[0])
+
+  def assertDoesNotMatch(self, checkerString, c1String):
+    with self.assertRaises(MatchFailedException):
+      self.assertMatches(checkerString, c1String)
 
   def test_Text(self):
-    self.assertTrue(self.matches( "// CHECK: foo bar", "foo bar"))
-    self.assertFalse(self.matches("// CHECK: foo bar", "abc def"))
+    self.assertMatches("// CHECK: foo bar", "foo bar")
+    self.assertDoesNotMatch("// CHECK: foo bar", "abc def")
 
   def test_Pattern(self):
-    self.assertTrue(self.matches( "// CHECK: abc {{de.}}", "abc de#"))
-    self.assertFalse(self.matches("// CHECK: abc {{de.}}", "abc d#f"))
+    self.assertMatches("// CHECK: abc {{de.}}", "abc de#")
+    self.assertDoesNotMatch("// CHECK: abc {{de.}}", "abc d#f")
 
   def test_Variables(self):
-    self.assertTrue(self.matches(
+    self.assertMatches(
     """
       // CHECK: foo<<X:.>>bar
       // CHECK: abc<<X>>def
@@ -142,8 +147,8 @@
     """
       foo0bar
       abc0def
-    """))
-    self.assertTrue(self.matches(
+    """)
+    self.assertMatches(
     """
       // CHECK: foo<<X:([0-9]+)>>bar
       // CHECK: abc<<X>>def
@@ -153,8 +158,8 @@
       foo1234bar
       abc1234def
       ### 1234 ###
-    """))
-    self.assertFalse(self.matches(
+    """)
+    self.assertDoesNotMatch(
     """
       // CHECK: foo<<X:([0-9]+)>>bar
       // CHECK: abc<<X>>def
@@ -162,16 +167,16 @@
     """
       foo1234bar
       abc1235def
-    """))
+    """)
 
   def test_WholeWordMustMatch(self):
-    self.assertTrue(self.matches( "// CHECK: b{{.}}r", "abc bar def"))
-    self.assertFalse(self.matches( "// CHECK: b{{.}}r", "abc Xbar def"))
-    self.assertFalse(self.matches( "// CHECK: b{{.}}r", "abc barX def"))
-    self.assertFalse(self.matches( "// CHECK: b{{.}}r", "abc b r def"))
+    self.assertMatches("// CHECK: b{{.}}r", "abc bar def")
+    self.assertDoesNotMatch("// CHECK: b{{.}}r", "abc Xbar def")
+    self.assertDoesNotMatch("// CHECK: b{{.}}r", "abc barX def")
+    self.assertDoesNotMatch("// CHECK: b{{.}}r", "abc b r def")
 
   def test_InOrderAssertions(self):
-    self.assertTrue(self.matches(
+    self.assertMatches(
     """
       // CHECK: foo
       // CHECK: bar
@@ -179,8 +184,8 @@
     """
       foo
       bar
-    """))
-    self.assertFalse(self.matches(
+    """)
+    self.assertDoesNotMatch(
     """
       // CHECK: foo
       // CHECK: bar
@@ -188,10 +193,58 @@
     """
       bar
       foo
-    """))
+    """)
+
+  def test_NextLineAssertions(self):
+    self.assertMatches(
+    """
+      // CHECK:      foo
+      // CHECK-NEXT: bar
+      // CHECK-NEXT: abc
+      // CHECK:      def
+    """,
+    """
+      foo
+      bar
+      abc
+      def
+    """)
+    self.assertMatches(
+    """
+      // CHECK:      foo
+      // CHECK-NEXT: bar
+      // CHECK:      def
+    """,
+    """
+      foo
+      bar
+      abc
+      def
+    """)
+    self.assertDoesNotMatch(
+    """
+      // CHECK:      foo
+      // CHECK-NEXT: bar
+    """,
+    """
+      foo
+      abc
+      bar
+    """)
+
+    self.assertDoesNotMatch(
+    """
+      // CHECK:      foo
+      // CHECK-NEXT: bar
+    """,
+    """
+      bar
+      foo
+      abc
+    """)
 
   def test_DagAssertions(self):
-    self.assertTrue(self.matches(
+    self.assertMatches(
     """
       // CHECK-DAG: foo
       // CHECK-DAG: bar
@@ -199,8 +252,8 @@
     """
       foo
       bar
-    """))
-    self.assertTrue(self.matches(
+    """)
+    self.assertMatches(
     """
       // CHECK-DAG: foo
       // CHECK-DAG: bar
@@ -208,10 +261,10 @@
     """
       bar
       foo
-    """))
+    """)
 
   def test_DagAssertionsScope(self):
-    self.assertTrue(self.matches(
+    self.assertMatches(
     """
       // CHECK:     foo
       // CHECK-DAG: abc
@@ -223,8 +276,8 @@
       def
       abc
       bar
-    """))
-    self.assertFalse(self.matches(
+    """)
+    self.assertDoesNotMatch(
     """
       // CHECK:     foo
       // CHECK-DAG: abc
@@ -236,8 +289,8 @@
       abc
       bar
       def
-    """))
-    self.assertFalse(self.matches(
+    """)
+    self.assertDoesNotMatch(
     """
       // CHECK:     foo
       // CHECK-DAG: abc
@@ -249,26 +302,26 @@
       def
       bar
       abc
-    """))
+    """)
 
   def test_NotAssertions(self):
-    self.assertTrue(self.matches(
+    self.assertMatches(
     """
       // CHECK-NOT: foo
     """,
     """
       abc
       def
-    """))
-    self.assertFalse(self.matches(
+    """)
+    self.assertDoesNotMatch(
     """
       // CHECK-NOT: foo
     """,
     """
       abc foo
       def
-    """))
-    self.assertFalse(self.matches(
+    """)
+    self.assertDoesNotMatch(
     """
       // CHECK-NOT: foo
       // CHECK-NOT: bar
@@ -276,10 +329,10 @@
     """
       abc
       def bar
-    """))
+    """)
 
   def test_NotAssertionsScope(self):
-    self.assertTrue(self.matches(
+    self.assertMatches(
     """
       // CHECK:     abc
       // CHECK-NOT: foo
@@ -288,8 +341,8 @@
     """
       abc
       def
-    """))
-    self.assertTrue(self.matches(
+    """)
+    self.assertMatches(
     """
       // CHECK:     abc
       // CHECK-NOT: foo
@@ -299,8 +352,8 @@
       abc
       def
       foo
-    """))
-    self.assertFalse(self.matches(
+    """)
+    self.assertDoesNotMatch(
     """
       // CHECK:     abc
       // CHECK-NOT: foo
@@ -310,10 +363,10 @@
       abc
       foo
       def
-    """))
+    """)
 
   def test_LineOnlyMatchesOnce(self):
-    self.assertTrue(self.matches(
+    self.assertMatches(
     """
       // CHECK-DAG: foo
       // CHECK-DAG: foo
@@ -322,8 +375,8 @@
       foo
       abc
       foo
-    """))
-    self.assertFalse(self.matches(
+    """)
+    self.assertDoesNotMatch(
     """
       // CHECK-DAG: foo
       // CHECK-DAG: foo
@@ -332,4 +385,4 @@
       foo
       abc
       bar
-    """))
+    """)
diff --git a/tools/libcore_failures.txt b/tools/libcore_failures.txt
index a8bc4e1..de45c49 100644
--- a/tools/libcore_failures.txt
+++ b/tools/libcore_failures.txt
@@ -21,28 +21,19 @@
   name: "libcore.java.lang.SystemTest#testSystemProperties_mutable"
 },
 {
-  description: "Differences between vogar and cts",
+  description: "Differences between vogar and cts. Passes with --mode activity",
   result: EXEC_FAILED,
   modes: [device],
-  names: ["libcore.java.lang.OldSystemTest#test_getProperties",
-          "org.apache.harmony.tests.java.lang.Process2Test#test_getErrorStream",
-          "org.apache.harmony.tests.java.lang.ProcessTest#test_exitValue"]
+  names: ["libcore.java.lang.OldSystemTest#test_getProperties"]
 },
 {
-  description: "Failures needing investigation",
+  description: "Differences between vogar and cts. EACCESS when run with vogar.
+                Passes on host, passes with cts. Passes with vogar with su
+                (--invoke-with \"su root\"). Does not pass after setting chmod
+                777 all directories on path to socket (on device without su).",
   result: EXEC_FAILED,
   modes: [device],
-  names: ["libcore.java.util.TimeZoneTest#testDisplayNames",
-          "libcore.java.util.TimeZoneTest#test_useDaylightTime_Taiwan",
-          "libcore.java.util.TimeZoneTest#testAllDisplayNames",
-          "libcore.io.OsTest#testUnixDomainSockets_in_file_system",
-          "org.apache.harmony.luni.tests.java.net.URLConnectionTest#test_setReadTimeoutI",
-          "org.apache.harmony.tests.java.util.DateTest#test_Constructor",
-          "org.apache.harmony.tests.java.util.ScannerTest#test_Constructor_LReadableByteChannel",
-          "org.apache.harmony.tests.java.util.TimeZoneTest#test_hasSameRules_Ljava_util_TimeZone",
-          "org.apache.harmony.tests.java.text.ChoiceFormatTest#testEscapedPatternWithConsecutiveQuotes",
-          "org.apache.harmony.tests.java.text.ChoiceFormatTest#testToPatternWithInfinities",
-          "org.apache.harmony.tests.java.text.MessageFormatTest#test19011159"]
+  names: ["libcore.io.OsTest#testUnixDomainSockets_in_file_system"]
 },
 {
   description: "Failing due to a locale problem on hammerhead.",