Deoptimization-based bce.

A mechanism is introduced that a runtime method can be called
from code compiled with optimizing compiler to deoptimize into
interpreter. This can be used to establish invariants in the managed code
If the invariant does not hold at runtime, we will deoptimize and continue
execution in the interpreter. This allows to optimize the managed code as
if the invariant was proven during compile time. However, the exception
will be thrown according to the semantics demanded by the spec.

The invariant and optimization included in this patch are based on the
length of an array. Given a set of array accesses with constant indices
{c1, ..., cn}, we can optimize away all bounds checks iff all 0 <= min(ci) and
max(ci) < array-length. The first can be proven statically. The second can be
established with a deoptimization-based invariant. This replaces n bounds
checks with one invariant check (plus slow-path code).

Change-Id: I8c6e34b56c85d25b91074832d13dba1db0a81569

14 files changed, 481 insertions, 112 deletions

diff --git a/compiler/oat_test.cc b/compiler/oat_test.cc
index 46aed60479..3efb2dc897 100644
--- a/compiler/oat_test.cc
+++ b/compiler/oat_test.cc
@@ -175,7 +175,7 @@ TEST_F(OatTest, OatHeaderSizeCheck) {
   EXPECT_EQ(72U, sizeof(OatHeader));
   EXPECT_EQ(4U, sizeof(OatMethodOffsets));
   EXPECT_EQ(28U, sizeof(OatQuickMethodHeader));
-  EXPECT_EQ(91 * GetInstructionSetPointerSize(kRuntimeISA), sizeof(QuickEntryPoints));
+  EXPECT_EQ(92 * GetInstructionSetPointerSize(kRuntimeISA), sizeof(QuickEntryPoints));
 }
 
 TEST_F(OatTest, OatHeaderIsValid) {
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index 1d167949f4..7444f6ee94 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -443,9 +443,31 @@ class MonotonicValueRange : public ValueRange {
 
 class BCEVisitor : public HGraphVisitor {
  public:
+  // The least number of bounds checks that should be eliminated by triggering
+  // the deoptimization technique.
+  static constexpr size_t kThresholdForAddingDeoptimize = 2;
+
+  // Very large constant index is considered as an anomaly. This is a threshold
+  // beyond which we don't bother to apply the deoptimization technique since
+  // it's likely some AIOOBE will be thrown.
+  static constexpr int32_t kMaxConstantForAddingDeoptimize = INT_MAX - 1024 * 1024;
+
   explicit BCEVisitor(HGraph* graph)
       : HGraphVisitor(graph),
-        maps_(graph->GetBlocks().Size()) {}
+        maps_(graph->GetBlocks().Size()),
+        need_to_revisit_block_(false) {}
+
+  void VisitBasicBlock(HBasicBlock* block) OVERRIDE {
+    first_constant_index_bounds_check_map_.clear();
+    HGraphVisitor::VisitBasicBlock(block);
+    if (need_to_revisit_block_) {
+      AddComparesWithDeoptimization(block);
+      need_to_revisit_block_ = false;
+      first_constant_index_bounds_check_map_.clear();
+      GetValueRangeMap(block)->clear();
+      HGraphVisitor::VisitBasicBlock(block);
+    }
+  }
 
  private:
   // Return the map of proven value ranges at the beginning of a basic block.
@@ -701,9 +723,26 @@ class BCEVisitor : public HGraphVisitor {
         }
       }
 
+      if (first_constant_index_bounds_check_map_.find(array_length->GetId()) ==
+          first_constant_index_bounds_check_map_.end()) {
+        // Remember the first bounds check against array_length of a constant index.
+        // That bounds check instruction has an associated HEnvironment where we
+        // may add an HDeoptimize to eliminate bounds checks of constant indices
+        // against array_length.
+        first_constant_index_bounds_check_map_.Put(array_length->GetId(), bounds_check);
+      } else {
+        // We've seen it at least twice. It's beneficial to introduce a compare with
+        // deoptimization fallback to eliminate the bounds checks.
+        need_to_revisit_block_ = true;
+      }
+
       // Once we have an array access like 'array[5] = 1', we record array.length >= 6.
       // We currently don't do it for non-constant index since a valid array[i] can't prove
       // a valid array[i-1] yet due to the lower bound side.
+      if (constant == INT_MAX) {
+        // INT_MAX as an index will definitely throw AIOOBE.
+        return;
+      }
       ValueBound lower = ValueBound(nullptr, constant + 1);
       ValueBound upper = ValueBound::Max();
       ValueRange* range = new (GetGraph()->GetArena())
@@ -938,8 +977,90 @@ class BCEVisitor : public HGraphVisitor {
     }
   }
 
+  void VisitDeoptimize(HDeoptimize* deoptimize) {
+    // Right now it's only HLessThanOrEqual.
+    DCHECK(deoptimize->InputAt(0)->IsLessThanOrEqual());
+    HLessThanOrEqual* less_than_or_equal = deoptimize->InputAt(0)->AsLessThanOrEqual();
+    HInstruction* instruction = less_than_or_equal->InputAt(0);
+    if (instruction->IsArrayLength()) {
+      HInstruction* constant = less_than_or_equal->InputAt(1);
+      DCHECK(constant->IsIntConstant());
+      DCHECK(constant->AsIntConstant()->GetValue() != INT_MAX);
+      ValueBound lower = ValueBound(nullptr, constant->AsIntConstant()->GetValue() + 1);
+      ValueRange* range = new (GetGraph()->GetArena())
+          ValueRange(GetGraph()->GetArena(), lower, ValueBound::Max());
+      GetValueRangeMap(deoptimize->GetBlock())->Overwrite(instruction->GetId(), range);
+    }
+  }
+
+  void AddCompareWithDeoptimization(HInstruction* array_length,
+                                    HIntConstant* const_instr,
+                                    HBasicBlock* block) {
+    DCHECK(array_length->IsArrayLength());
+    ValueRange* range = LookupValueRange(array_length, block);
+    ValueBound lower_bound = range->GetLower();
+    DCHECK(lower_bound.IsConstant());
+    DCHECK(const_instr->GetValue() <= kMaxConstantForAddingDeoptimize);
+    DCHECK_EQ(lower_bound.GetConstant(), const_instr->GetValue() + 1);
+
+    // If array_length is less than lower_const, deoptimize.
+    HBoundsCheck* bounds_check = first_constant_index_bounds_check_map_.Get(
+        array_length->GetId())->AsBoundsCheck();
+    HCondition* cond = new (GetGraph()->GetArena()) HLessThanOrEqual(array_length, const_instr);
+    HDeoptimize* deoptimize = new (GetGraph()->GetArena())
+        HDeoptimize(cond, bounds_check->GetDexPc());
+    block->InsertInstructionBefore(cond, bounds_check);
+    block->InsertInstructionBefore(deoptimize, bounds_check);
+    deoptimize->SetEnvironment(bounds_check->GetEnvironment());
+  }
+
+  void AddComparesWithDeoptimization(HBasicBlock* block) {
+    for (ArenaSafeMap<int, HBoundsCheck*>::iterator it =
+             first_constant_index_bounds_check_map_.begin();
+         it != first_constant_index_bounds_check_map_.end();
+         ++it) {
+      HBoundsCheck* bounds_check = it->second;
+      HArrayLength* array_length = bounds_check->InputAt(1)->AsArrayLength();
+      HIntConstant* lower_bound_const_instr = nullptr;
+      int32_t lower_bound_const = INT_MIN;
+      size_t counter = 0;
+      // Count the constant indexing for which bounds checks haven't
+      // been removed yet.
+      for (HUseIterator<HInstruction*> it2(array_length->GetUses());
+           !it2.Done();
+           it2.Advance()) {
+        HInstruction* user = it2.Current()->GetUser();
+        if (user->GetBlock() == block &&
+            user->IsBoundsCheck() &&
+            user->AsBoundsCheck()->InputAt(0)->IsIntConstant()) {
+          DCHECK_EQ(array_length, user->AsBoundsCheck()->InputAt(1));
+          HIntConstant* const_instr = user->AsBoundsCheck()->InputAt(0)->AsIntConstant();
+          if (const_instr->GetValue() > lower_bound_const) {
+            lower_bound_const = const_instr->GetValue();
+            lower_bound_const_instr = const_instr;
+          }
+          counter++;
+        }
+      }
+      if (counter >= kThresholdForAddingDeoptimize &&
+          lower_bound_const_instr->GetValue() <= kMaxConstantForAddingDeoptimize) {
+        AddCompareWithDeoptimization(array_length, lower_bound_const_instr, block);
+      }
+    }
+  }
+
   std::vector<std::unique_ptr<ArenaSafeMap<int, ValueRange*>>> maps_;
 
+  // Map an HArrayLength instruction's id to the first HBoundsCheck instruction in
+  // a block that checks a constant index against that HArrayLength.
+  SafeMap<int, HBoundsCheck*> first_constant_index_bounds_check_map_;
+
+  // For the block, there is at least one HArrayLength instruction for which there
+  // is more than one bounds check instruction with constant indexing. And it's
+  // beneficial to add a compare instruction that has deoptimization fallback and
+  // eliminate those bounds checks.
+  bool need_to_revisit_block_;
+
   DISALLOW_COPY_AND_ASSIGN(BCEVisitor);
 };
 
diff --git a/compiler/optimizing/bounds_check_elimination_test.cc b/compiler/optimizing/bounds_check_elimination_test.cc
index 24fa58317a..5632f2bd29 100644
--- a/compiler/optimizing/bounds_check_elimination_test.cc
+++ b/compiler/optimizing/bounds_check_elimination_test.cc
@@ -289,9 +289,9 @@ TEST(BoundsCheckEliminationTest, UnderflowArrayBoundsElimination) {
   ASSERT_FALSE(IsRemoved(bounds_check));
 }
 
-// array[5] = 1; // Can't eliminate.
-// array[4] = 1; // Can eliminate.
 // array[6] = 1; // Can't eliminate.
+// array[5] = 1; // Can eliminate.
+// array[4] = 1; // Can eliminate.
 TEST(BoundsCheckEliminationTest, ConstantArrayBoundsElimination) {
   ArenaPool pool;
   ArenaAllocator allocator(&pool);
@@ -319,35 +319,35 @@ TEST(BoundsCheckEliminationTest, ConstantArrayBoundsElimination) {
 
   HNullCheck* null_check = new (&allocator) HNullCheck(parameter, 0);
   HArrayLength* array_length = new (&allocator) HArrayLength(null_check);
-  HBoundsCheck* bounds_check5 = new (&allocator)
-      HBoundsCheck(constant_5, array_length, 0);
+  HBoundsCheck* bounds_check6 = new (&allocator)
+      HBoundsCheck(constant_6, array_length, 0);
   HInstruction* array_set = new (&allocator) HArraySet(
-    null_check, bounds_check5, constant_1, Primitive::kPrimInt, 0);
+    null_check, bounds_check6, constant_1, Primitive::kPrimInt, 0);
   block->AddInstruction(null_check);
   block->AddInstruction(array_length);
-  block->AddInstruction(bounds_check5);
+  block->AddInstruction(bounds_check6);
   block->AddInstruction(array_set);
 
   null_check = new (&allocator) HNullCheck(parameter, 0);
   array_length = new (&allocator) HArrayLength(null_check);
-  HBoundsCheck* bounds_check4 = new (&allocator)
-      HBoundsCheck(constant_4, array_length, 0);
+  HBoundsCheck* bounds_check5 = new (&allocator)
+      HBoundsCheck(constant_5, array_length, 0);
   array_set = new (&allocator) HArraySet(
-    null_check, bounds_check4, constant_1, Primitive::kPrimInt, 0);
+    null_check, bounds_check5, constant_1, Primitive::kPrimInt, 0);
   block->AddInstruction(null_check);
   block->AddInstruction(array_length);
-  block->AddInstruction(bounds_check4);
+  block->AddInstruction(bounds_check5);
   block->AddInstruction(array_set);
 
   null_check = new (&allocator) HNullCheck(parameter, 0);
   array_length = new (&allocator) HArrayLength(null_check);
-  HBoundsCheck* bounds_check6 = new (&allocator)
-      HBoundsCheck(constant_6, array_length, 0);
+  HBoundsCheck* bounds_check4 = new (&allocator)
+      HBoundsCheck(constant_4, array_length, 0);
   array_set = new (&allocator) HArraySet(
-    null_check, bounds_check6, constant_1, Primitive::kPrimInt, 0);
+    null_check, bounds_check4, constant_1, Primitive::kPrimInt, 0);
   block->AddInstruction(null_check);
   block->AddInstruction(array_length);
-  block->AddInstruction(bounds_check6);
+  block->AddInstruction(bounds_check4);
   block->AddInstruction(array_set);
 
   block->AddInstruction(new (&allocator) HGoto());
@@ -361,9 +361,9 @@ TEST(BoundsCheckEliminationTest, ConstantArrayBoundsElimination) {
   RunSimplifierAndGvn(graph);
   BoundsCheckElimination bounds_check_elimination(graph);
   bounds_check_elimination.Run();
-  ASSERT_FALSE(IsRemoved(bounds_check5));
-  ASSERT_TRUE(IsRemoved(bounds_check4));
   ASSERT_FALSE(IsRemoved(bounds_check6));
+  ASSERT_TRUE(IsRemoved(bounds_check5));
+  ASSERT_TRUE(IsRemoved(bounds_check4));
 }
 
 // for (int i=initial; i<array.length; i+=increment) { array[i] = 10; }
diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
index 0a069a75ef..363fbeffb6 100644
--- a/compiler/optimizing/code_generator_arm.cc
+++ b/compiler/optimizing/code_generator_arm.cc
@@ -305,6 +305,26 @@ class TypeCheckSlowPathARM : public SlowPathCodeARM {
   DISALLOW_COPY_AND_ASSIGN(TypeCheckSlowPathARM);
 };
 
+class DeoptimizationSlowPathARM : public SlowPathCodeARM {
+ public:
+  explicit DeoptimizationSlowPathARM(HInstruction* instruction)
+    : instruction_(instruction) {}
+
+  void EmitNativeCode(CodeGenerator* codegen) OVERRIDE {
+    __ Bind(GetEntryLabel());
+    SaveLiveRegisters(codegen, instruction_->GetLocations());
+    DCHECK(instruction_->IsDeoptimize());
+    HDeoptimize* deoptimize = instruction_->AsDeoptimize();
+    uint32_t dex_pc = deoptimize->GetDexPc();
+    CodeGeneratorARM* arm_codegen = down_cast<CodeGeneratorARM*>(codegen);
+    arm_codegen->InvokeRuntime(QUICK_ENTRY_POINT(pDeoptimize), instruction_, dex_pc, this);
+  }
+
+ private:
+  HInstruction* const instruction_;
+  DISALLOW_COPY_AND_ASSIGN(DeoptimizationSlowPathARM);
+};
+
 #undef __
 
 #undef __
@@ -905,24 +925,17 @@ void InstructionCodeGeneratorARM::VisitExit(HExit* exit) {
   UNUSED(exit);
 }
 
-void LocationsBuilderARM::VisitIf(HIf* if_instr) {
-  LocationSummary* locations =
-      new (GetGraph()->GetArena()) LocationSummary(if_instr, LocationSummary::kNoCall);
-  HInstruction* cond = if_instr->InputAt(0);
-  if (!cond->IsCondition() || cond->AsCondition()->NeedsMaterialization()) {
-    locations->SetInAt(0, Location::RequiresRegister());
-  }
-}
-
-void InstructionCodeGeneratorARM::VisitIf(HIf* if_instr) {
-  HInstruction* cond = if_instr->InputAt(0);
+void InstructionCodeGeneratorARM::GenerateTestAndBranch(HInstruction* instruction,
+                                                        Label* true_target,
+                                                        Label* false_target,
+                                                        Label* always_true_target) {
+  HInstruction* cond = instruction->InputAt(0);
   if (cond->IsIntConstant()) {
     // Constant condition, statically compared against 1.
     int32_t cond_value = cond->AsIntConstant()->GetValue();
     if (cond_value == 1) {
-      if (!codegen_->GoesToNextBlock(if_instr->GetBlock(),
-                                     if_instr->IfTrueSuccessor())) {
-        __ b(codegen_->GetLabelOf(if_instr->IfTrueSuccessor()));
+      if (always_true_target != nullptr) {
+        __ b(always_true_target);
       }
       return;
     } else {
@@ -931,10 +944,10 @@ void InstructionCodeGeneratorARM::VisitIf(HIf* if_instr) {
   } else {
     if (!cond->IsCondition() || cond->AsCondition()->NeedsMaterialization()) {
       // Condition has been materialized, compare the output to 0
-      DCHECK(if_instr->GetLocations()->InAt(0).IsRegister());
-      __ cmp(if_instr->GetLocations()->InAt(0).AsRegister<Register>(),
+      DCHECK(instruction->GetLocations()->InAt(0).IsRegister());
+      __ cmp(instruction->GetLocations()->InAt(0).AsRegister<Register>(),
              ShifterOperand(0));
-      __ b(codegen_->GetLabelOf(if_instr->IfTrueSuccessor()), NE);
+      __ b(true_target, NE);
     } else {
       // Condition has not been materialized, use its inputs as the
       // comparison and its condition as the branch condition.
@@ -956,16 +969,55 @@ void InstructionCodeGeneratorARM::VisitIf(HIf* if_instr) {
           __ cmp(left, ShifterOperand(temp));
         }
       }
-      __ b(codegen_->GetLabelOf(if_instr->IfTrueSuccessor()),
-           ARMCondition(cond->AsCondition()->GetCondition()));
+      __ b(true_target);
     }
   }
-  if (!codegen_->GoesToNextBlock(if_instr->GetBlock(),
-                                 if_instr->IfFalseSuccessor())) {
-    __ b(codegen_->GetLabelOf(if_instr->IfFalseSuccessor()));
+  if (false_target != nullptr) {
+    __ b(false_target);
   }
 }
 
+void LocationsBuilderARM::VisitIf(HIf* if_instr) {
+  LocationSummary* locations =
+      new (GetGraph()->GetArena()) LocationSummary(if_instr, LocationSummary::kNoCall);
+  HInstruction* cond = if_instr->InputAt(0);
+  if (!cond->IsCondition() || cond->AsCondition()->NeedsMaterialization()) {
+    locations->SetInAt(0, Location::RequiresRegister());
+  }
+}
+
+void InstructionCodeGeneratorARM::VisitIf(HIf* if_instr) {
+  Label* true_target = codegen_->GetLabelOf(if_instr->IfTrueSuccessor());
+  Label* false_target = codegen_->GetLabelOf(if_instr->IfFalseSuccessor());
+  Label* always_true_target = true_target;
+  if (codegen_->GoesToNextBlock(if_instr->GetBlock(),
+                                if_instr->IfTrueSuccessor())) {
+    always_true_target = nullptr;
+  }
+  if (codegen_->GoesToNextBlock(if_instr->GetBlock(),
+                                if_instr->IfFalseSuccessor())) {
+    false_target = nullptr;
+  }
+  GenerateTestAndBranch(if_instr, true_target, false_target, always_true_target);
+}
+
+void LocationsBuilderARM::VisitDeoptimize(HDeoptimize* deoptimize) {
+  LocationSummary* locations = new (GetGraph()->GetArena())
+      LocationSummary(deoptimize, LocationSummary::kCallOnSlowPath);
+  HInstruction* cond = deoptimize->InputAt(0);
+  DCHECK(cond->IsCondition());
+  if (cond->AsCondition()->NeedsMaterialization()) {
+    locations->SetInAt(0, Location::RequiresRegister());
+  }
+}
+
+void InstructionCodeGeneratorARM::VisitDeoptimize(HDeoptimize* deoptimize) {
+  SlowPathCodeARM* slow_path = new (GetGraph()->GetArena())
+      DeoptimizationSlowPathARM(deoptimize);
+  codegen_->AddSlowPath(slow_path);
+  Label* slow_path_entry = slow_path->GetEntryLabel();
+  GenerateTestAndBranch(deoptimize, slow_path_entry, nullptr, slow_path_entry);
+}
 
 void LocationsBuilderARM::VisitCondition(HCondition* comp) {
   LocationSummary* locations =
diff --git a/compiler/optimizing/code_generator_arm.h b/compiler/optimizing/code_generator_arm.h
index 57e1d2f2f5..946a8a5c1b 100644
--- a/compiler/optimizing/code_generator_arm.h
+++ b/compiler/optimizing/code_generator_arm.h
@@ -169,6 +169,10 @@ class InstructionCodeGeneratorARM : public HGraphVisitor {
   void HandleFieldGet(HInstruction* instruction, const FieldInfo& field_info);
   void GenerateImplicitNullCheck(HNullCheck* instruction);
   void GenerateExplicitNullCheck(HNullCheck* instruction);
+  void GenerateTestAndBranch(HInstruction* instruction,
+                             Label* true_target,
+                             Label* false_target,
+                             Label* always_true_target);
 
   ArmAssembler* const assembler_;
   CodeGeneratorARM* const codegen_;
diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc
index 99283a0056..44bd399127 100644
--- a/compiler/optimizing/code_generator_arm64.cc
+++ b/compiler/optimizing/code_generator_arm64.cc
@@ -375,6 +375,26 @@ class TypeCheckSlowPathARM64 : public SlowPathCodeARM64 {
   DISALLOW_COPY_AND_ASSIGN(TypeCheckSlowPathARM64);
 };
 
+class DeoptimizationSlowPathARM64 : public SlowPathCodeARM64 {
+ public:
+  explicit DeoptimizationSlowPathARM64(HInstruction* instruction)
+    : instruction_(instruction) {}
+
+  void EmitNativeCode(CodeGenerator* codegen) OVERRIDE {
+    __ Bind(GetEntryLabel());
+    SaveLiveRegisters(codegen, instruction_->GetLocations());
+    DCHECK(instruction_->IsDeoptimize());
+    HDeoptimize* deoptimize = instruction_->AsDeoptimize();
+    uint32_t dex_pc = deoptimize->GetDexPc();
+    CodeGeneratorARM64* arm64_codegen = down_cast<CodeGeneratorARM64*>(codegen);
+    arm64_codegen->InvokeRuntime(QUICK_ENTRY_POINT(pDeoptimize), instruction_, dex_pc, this);
+  }
+
+ private:
+  HInstruction* const instruction_;
+  DISALLOW_COPY_AND_ASSIGN(DeoptimizationSlowPathARM64);
+};
+
 #undef __
 
 Location InvokeDexCallingConventionVisitor::GetNextLocation(Primitive::Type type) {
@@ -1634,25 +1654,18 @@ void InstructionCodeGeneratorARM64::VisitGoto(HGoto* got) {
   }
 }
 
-void LocationsBuilderARM64::VisitIf(HIf* if_instr) {
-  LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(if_instr);
-  HInstruction* cond = if_instr->InputAt(0);
-  if (!cond->IsCondition() || cond->AsCondition()->NeedsMaterialization()) {
-    locations->SetInAt(0, Location::RequiresRegister());
-  }
-}
-
-void InstructionCodeGeneratorARM64::VisitIf(HIf* if_instr) {
-  HInstruction* cond = if_instr->InputAt(0);
+void InstructionCodeGeneratorARM64::GenerateTestAndBranch(HInstruction* instruction,
+                                                          vixl::Label* true_target,
+                                                          vixl::Label* false_target,
+                                                          vixl::Label* always_true_target) {
+  HInstruction* cond = instruction->InputAt(0);
   HCondition* condition = cond->AsCondition();
-  vixl::Label* true_target = codegen_->GetLabelOf(if_instr->IfTrueSuccessor());
-  vixl::Label* false_target = codegen_->GetLabelOf(if_instr->IfFalseSuccessor());
 
   if (cond->IsIntConstant()) {
     int32_t cond_value = cond->AsIntConstant()->GetValue();
     if (cond_value == 1) {
-      if (!codegen_->GoesToNextBlock(if_instr->GetBlock(), if_instr->IfTrueSuccessor())) {
-        __ B(true_target);
+      if (always_true_target != nullptr) {
+        __ B(always_true_target);
       }
       return;
     } else {
@@ -1660,9 +1673,9 @@ void InstructionCodeGeneratorARM64::VisitIf(HIf* if_instr) {
     }
   } else if (!cond->IsCondition() || condition->NeedsMaterialization()) {
     // The condition instruction has been materialized, compare the output to 0.
-    Location cond_val = if_instr->GetLocations()->InAt(0);
+    Location cond_val = instruction->GetLocations()->InAt(0);
     DCHECK(cond_val.IsRegister());
-    __ Cbnz(InputRegisterAt(if_instr, 0), true_target);
+    __ Cbnz(InputRegisterAt(instruction, 0), true_target);
   } else {
     // The condition instruction has not been materialized, use its inputs as
     // the comparison and its condition as the branch condition.
@@ -1680,11 +1693,52 @@ void InstructionCodeGeneratorARM64::VisitIf(HIf* if_instr) {
       __ B(arm64_cond, true_target);
     }
   }
-  if (!codegen_->GoesToNextBlock(if_instr->GetBlock(), if_instr->IfFalseSuccessor())) {
+  if (false_target != nullptr) {
     __ B(false_target);
   }
 }
 
+void LocationsBuilderARM64::VisitIf(HIf* if_instr) {
+  LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(if_instr);
+  HInstruction* cond = if_instr->InputAt(0);
+  if (!cond->IsCondition() || cond->AsCondition()->NeedsMaterialization()) {
+    locations->SetInAt(0, Location::RequiresRegister());
+  }
+}
+
+void InstructionCodeGeneratorARM64::VisitIf(HIf* if_instr) {
+  vixl::Label* true_target = codegen_->GetLabelOf(if_instr->IfTrueSuccessor());
+  vixl::Label* false_target = codegen_->GetLabelOf(if_instr->IfFalseSuccessor());
+  vixl::Label* always_true_target = true_target;
+  if (codegen_->GoesToNextBlock(if_instr->GetBlock(),
+                                if_instr->IfTrueSuccessor())) {
+    always_true_target = nullptr;
+  }
+  if (codegen_->GoesToNextBlock(if_instr->GetBlock(),
+                                if_instr->IfFalseSuccessor())) {
+    false_target = nullptr;
+  }
+  GenerateTestAndBranch(if_instr, true_target, false_target, always_true_target);
+}
+
+void LocationsBuilderARM64::VisitDeoptimize(HDeoptimize* deoptimize) {
+  LocationSummary* locations = new (GetGraph()->GetArena())
+      LocationSummary(deoptimize, LocationSummary::kCallOnSlowPath);
+  HInstruction* cond = deoptimize->InputAt(0);
+  DCHECK(cond->IsCondition());
+  if (cond->AsCondition()->NeedsMaterialization()) {
+    locations->SetInAt(0, Location::RequiresRegister());
+  }
+}
+
+void InstructionCodeGeneratorARM64::VisitDeoptimize(HDeoptimize* deoptimize) {
+  SlowPathCodeARM64* slow_path = new (GetGraph()->GetArena())
+      DeoptimizationSlowPathARM64(deoptimize);
+  codegen_->AddSlowPath(slow_path);
+  vixl::Label* slow_path_entry = slow_path->GetEntryLabel();
+  GenerateTestAndBranch(deoptimize, slow_path_entry, nullptr, slow_path_entry);
+}
+
 void LocationsBuilderARM64::VisitInstanceFieldGet(HInstanceFieldGet* instruction) {
   LocationSummary* locations =
       new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kNoCall);
diff --git a/compiler/optimizing/code_generator_arm64.h b/compiler/optimizing/code_generator_arm64.h
index cbb2e5c749..860b25005b 100644
--- a/compiler/optimizing/code_generator_arm64.h
+++ b/compiler/optimizing/code_generator_arm64.h
@@ -140,6 +140,10 @@ class InstructionCodeGeneratorARM64 : public HGraphVisitor {
   void HandleShift(HBinaryOperation* instr);
   void GenerateImplicitNullCheck(HNullCheck* instruction);
   void GenerateExplicitNullCheck(HNullCheck* instruction);
+  void GenerateTestAndBranch(HInstruction* instruction,
+                             vixl::Label* true_target,
+                             vixl::Label* false_target,
+                             vixl::Label* always_true_target);
 
   Arm64Assembler* const assembler_;
   CodeGeneratorARM64* const codegen_;
diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc
index 02b9b3294c..44bbccce0f 100644
--- a/compiler/optimizing/code_generator_x86.cc
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -324,6 +324,27 @@ class TypeCheckSlowPathX86 : public SlowPathCodeX86 {
   DISALLOW_COPY_AND_ASSIGN(TypeCheckSlowPathX86);
 };
 
+class DeoptimizationSlowPathX86 : public SlowPathCodeX86 {
+ public:
+  explicit DeoptimizationSlowPathX86(HInstruction* instruction)
+    : instruction_(instruction) {}
+
+  void EmitNativeCode(CodeGenerator* codegen) OVERRIDE {
+    __ Bind(GetEntryLabel());
+    SaveLiveRegisters(codegen, instruction_->GetLocations());
+    __ fs()->call(Address::Absolute(QUICK_ENTRYPOINT_OFFSET(kX86WordSize, pDeoptimize)));
+    // No need to restore live registers.
+    DCHECK(instruction_->IsDeoptimize());
+    HDeoptimize* deoptimize = instruction_->AsDeoptimize();
+    uint32_t dex_pc = deoptimize->GetDexPc();
+    codegen->RecordPcInfo(instruction_, dex_pc, this);
+  }
+
+ private:
+  HInstruction* const instruction_;
+  DISALLOW_COPY_AND_ASSIGN(DeoptimizationSlowPathX86);
+};
+
 #undef __
 #define __ reinterpret_cast<X86Assembler*>(GetAssembler())->
 
@@ -814,24 +835,17 @@ void InstructionCodeGeneratorX86::VisitExit(HExit* exit) {
   UNUSED(exit);
 }
 
-void LocationsBuilderX86::VisitIf(HIf* if_instr) {
-  LocationSummary* locations =
-      new (GetGraph()->GetArena()) LocationSummary(if_instr, LocationSummary::kNoCall);
-  HInstruction* cond = if_instr->InputAt(0);
-  if (!cond->IsCondition() || cond->AsCondition()->NeedsMaterialization()) {
-    locations->SetInAt(0, Location::Any());
-  }
-}
-
-void InstructionCodeGeneratorX86::VisitIf(HIf* if_instr) {
-  HInstruction* cond = if_instr->InputAt(0);
+void InstructionCodeGeneratorX86::GenerateTestAndBranch(HInstruction* instruction,
+                                                        Label* true_target,
+                                                        Label* false_target,
+                                                        Label* always_true_target) {
+  HInstruction* cond = instruction->InputAt(0);
   if (cond->IsIntConstant()) {
     // Constant condition, statically compared against 1.
     int32_t cond_value = cond->AsIntConstant()->GetValue();
     if (cond_value == 1) {
-      if (!codegen_->GoesToNextBlock(if_instr->GetBlock(),
-                                     if_instr->IfTrueSuccessor())) {
-        __ jmp(codegen_->GetLabelOf(if_instr->IfTrueSuccessor()));
+      if (always_true_target != nullptr) {
+        __ jmp(always_true_target);
       }
       return;
     } else {
@@ -844,20 +858,19 @@ void InstructionCodeGeneratorX86::VisitIf(HIf* if_instr) {
     // evaluated just before the if, we don't need to evaluate it
     // again.
     bool eflags_set = cond->IsCondition()
-        && cond->AsCondition()->IsBeforeWhenDisregardMoves(if_instr);
+        && cond->AsCondition()->IsBeforeWhenDisregardMoves(instruction);
     if (materialized) {
       if (!eflags_set) {
         // Materialized condition, compare against 0.
-        Location lhs = if_instr->GetLocations()->InAt(0);
+        Location lhs = instruction->GetLocations()->InAt(0);
         if (lhs.IsRegister()) {
           __ testl(lhs.AsRegister<Register>(), lhs.AsRegister<Register>());
         } else {
           __ cmpl(Address(ESP, lhs.GetStackIndex()), Immediate(0));
         }
-        __ j(kNotEqual,  codegen_->GetLabelOf(if_instr->IfTrueSuccessor()));
+        __ j(kNotEqual, true_target);
       } else {
-        __ j(X86Condition(cond->AsCondition()->GetCondition()),
-             codegen_->GetLabelOf(if_instr->IfTrueSuccessor()));
+        __ j(X86Condition(cond->AsCondition()->GetCondition()), true_target);
       }
     } else {
       Location lhs = cond->GetLocations()->InAt(0);
@@ -876,16 +889,56 @@ void InstructionCodeGeneratorX86::VisitIf(HIf* if_instr) {
       } else {
         __ cmpl(lhs.AsRegister<Register>(), Address(ESP, rhs.GetStackIndex()));
       }
-      __ j(X86Condition(cond->AsCondition()->GetCondition()),
-           codegen_->GetLabelOf(if_instr->IfTrueSuccessor()));
+      __ j(X86Condition(cond->AsCondition()->GetCondition()), true_target);
     }
   }
-  if (!codegen_->GoesToNextBlock(if_instr->GetBlock(),
-                                 if_instr->IfFalseSuccessor())) {
-    __ jmp(codegen_->GetLabelOf(if_instr->IfFalseSuccessor()));
+  if (false_target != nullptr) {
+    __ jmp(false_target);
   }
 }
 
+void LocationsBuilderX86::VisitIf(HIf* if_instr) {
+  LocationSummary* locations =
+      new (GetGraph()->GetArena()) LocationSummary(if_instr, LocationSummary::kNoCall);
+  HInstruction* cond = if_instr->InputAt(0);
+  if (!cond->IsCondition() || cond->AsCondition()->NeedsMaterialization()) {
+    locations->SetInAt(0, Location::Any());
+  }
+}
+
+void InstructionCodeGeneratorX86::VisitIf(HIf* if_instr) {
+  Label* true_target = codegen_->GetLabelOf(if_instr->IfTrueSuccessor());
+  Label* false_target = codegen_->GetLabelOf(if_instr->IfFalseSuccessor());
+  Label* always_true_target = true_target;
+  if (codegen_->GoesToNextBlock(if_instr->GetBlock(),
+                                if_instr->IfTrueSuccessor())) {
+    always_true_target = nullptr;
+  }
+  if (codegen_->GoesToNextBlock(if_instr->GetBlock(),
+                                if_instr->IfFalseSuccessor())) {
+    false_target = nullptr;
+  }
+  GenerateTestAndBranch(if_instr, true_target, false_target, always_true_target);
+}
+
+void LocationsBuilderX86::VisitDeoptimize(HDeoptimize* deoptimize) {
+  LocationSummary* locations = new (GetGraph()->GetArena())
+      LocationSummary(deoptimize, LocationSummary::kCallOnSlowPath);
+  HInstruction* cond = deoptimize->InputAt(0);
+  DCHECK(cond->IsCondition());
+  if (cond->AsCondition()->NeedsMaterialization()) {
+    locations->SetInAt(0, Location::Any());
+  }
+}
+
+void InstructionCodeGeneratorX86::VisitDeoptimize(HDeoptimize* deoptimize) {
+  SlowPathCodeX86* slow_path = new (GetGraph()->GetArena())
+      DeoptimizationSlowPathX86(deoptimize);
+  codegen_->AddSlowPath(slow_path);
+  Label* slow_path_entry = slow_path->GetEntryLabel();
+  GenerateTestAndBranch(deoptimize, slow_path_entry, nullptr, slow_path_entry);
+}
+
 void LocationsBuilderX86::VisitLocal(HLocal* local) {
   local->SetLocations(nullptr);
 }
diff --git a/compiler/optimizing/code_generator_x86.h b/compiler/optimizing/code_generator_x86.h
index c5763de05e..7c7365f29f 100644
--- a/compiler/optimizing/code_generator_x86.h
+++ b/compiler/optimizing/code_generator_x86.h
@@ -157,6 +157,10 @@ class InstructionCodeGeneratorX86 : public HGraphVisitor {
 
   void GenerateImplicitNullCheck(HNullCheck* instruction);
   void GenerateExplicitNullCheck(HNullCheck* instruction);
+  void GenerateTestAndBranch(HInstruction* instruction,
+                             Label* true_target,
+                             Label* false_target,
+                             Label* always_true_target);
 
   X86Assembler* const assembler_;
   CodeGeneratorX86* const codegen_;
diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc
index d09c8f8e51..d8b9450cc2 100644
--- a/compiler/optimizing/code_generator_x86_64.cc
+++ b/compiler/optimizing/code_generator_x86_64.cc
@@ -331,6 +331,27 @@ class TypeCheckSlowPathX86_64 : public SlowPathCodeX86_64 {
   DISALLOW_COPY_AND_ASSIGN(TypeCheckSlowPathX86_64);
 };
 
+class DeoptimizationSlowPathX86_64 : public SlowPathCodeX86_64 {
+ public:
+  explicit DeoptimizationSlowPathX86_64(HInstruction* instruction)
+      : instruction_(instruction) {}
+
+  void EmitNativeCode(CodeGenerator* codegen) OVERRIDE {
+    __ Bind(GetEntryLabel());
+    SaveLiveRegisters(codegen, instruction_->GetLocations());
+    __ gs()->call(
+        Address::Absolute(QUICK_ENTRYPOINT_OFFSET(kX86_64WordSize, pDeoptimize), true));
+    DCHECK(instruction_->IsDeoptimize());
+    HDeoptimize* deoptimize = instruction_->AsDeoptimize();
+    uint32_t dex_pc = deoptimize->GetDexPc();
+    codegen->RecordPcInfo(instruction_, dex_pc, this);
+  }
+
+ private:
+  HInstruction* const instruction_;
+  DISALLOW_COPY_AND_ASSIGN(DeoptimizationSlowPathX86_64);
+};
+
 #undef __
 #define __ reinterpret_cast<X86_64Assembler*>(GetAssembler())->
 
@@ -751,24 +772,17 @@ void InstructionCodeGeneratorX86_64::VisitExit(HExit* exit) {
   UNUSED(exit);
 }
 
-void LocationsBuilderX86_64::VisitIf(HIf* if_instr) {
-  LocationSummary* locations =
-      new (GetGraph()->GetArena()) LocationSummary(if_instr, LocationSummary::kNoCall);
-  HInstruction* cond = if_instr->InputAt(0);
-  if (!cond->IsCondition() || cond->AsCondition()->NeedsMaterialization()) {
-    locations->SetInAt(0, Location::Any());
-  }
-}
-
-void InstructionCodeGeneratorX86_64::VisitIf(HIf* if_instr) {
-  HInstruction* cond = if_instr->InputAt(0);
+void InstructionCodeGeneratorX86_64::GenerateTestAndBranch(HInstruction* instruction,
+                                                           Label* true_target,
+                                                           Label* false_target,
+                                                           Label* always_true_target) {
+  HInstruction* cond = instruction->InputAt(0);
   if (cond->IsIntConstant()) {
     // Constant condition, statically compared against 1.
     int32_t cond_value = cond->AsIntConstant()->GetValue();
     if (cond_value == 1) {
-      if (!codegen_->GoesToNextBlock(if_instr->GetBlock(),
-                                     if_instr->IfTrueSuccessor())) {
-        __ jmp(codegen_->GetLabelOf(if_instr->IfTrueSuccessor()));
+      if (always_true_target != nullptr) {
+        __ jmp(always_true_target);
       }
       return;
     } else {
@@ -781,21 +795,20 @@ void InstructionCodeGeneratorX86_64::VisitIf(HIf* if_instr) {
     // evaluated just before the if, we don't need to evaluate it
     // again.
     bool eflags_set = cond->IsCondition()
-        && cond->AsCondition()->IsBeforeWhenDisregardMoves(if_instr);
+        && cond->AsCondition()->IsBeforeWhenDisregardMoves(instruction);
     if (materialized) {
       if (!eflags_set) {
         // Materialized condition, compare against 0.
-        Location lhs = if_instr->GetLocations()->InAt(0);
+        Location lhs = instruction->GetLocations()->InAt(0);
         if (lhs.IsRegister()) {
           __ testl(lhs.AsRegister<CpuRegister>(), lhs.AsRegister<CpuRegister>());
         } else {
           __ cmpl(Address(CpuRegister(RSP), lhs.GetStackIndex()),
                   Immediate(0));
         }
-        __ j(kNotEqual, codegen_->GetLabelOf(if_instr->IfTrueSuccessor()));
+        __ j(kNotEqual, true_target);
       } else {
-        __ j(X86_64Condition(cond->AsCondition()->GetCondition()),
-             codegen_->GetLabelOf(if_instr->IfTrueSuccessor()));
+        __ j(X86_64Condition(cond->AsCondition()->GetCondition()), true_target);
       }
     } else {
       Location lhs = cond->GetLocations()->InAt(0);
@@ -813,16 +826,56 @@ void InstructionCodeGeneratorX86_64::VisitIf(HIf* if_instr) {
         __ cmpl(lhs.AsRegister<CpuRegister>(),
                 Address(CpuRegister(RSP), rhs.GetStackIndex()));
       }
-      __ j(X86_64Condition(cond->AsCondition()->GetCondition()),
-           codegen_->GetLabelOf(if_instr->IfTrueSuccessor()));
+      __ j(X86_64Condition(cond->AsCondition()->GetCondition()), true_target);
     }
   }
-  if (!codegen_->GoesToNextBlock(if_instr->GetBlock(),
-                                 if_instr->IfFalseSuccessor())) {
-    __ jmp(codegen_->GetLabelOf(if_instr->IfFalseSuccessor()));
+  if (false_target != nullptr) {
+    __ jmp(false_target);
+  }
+}
+
+void LocationsBuilderX86_64::VisitIf(HIf* if_instr) {
+  LocationSummary* locations =
+      new (GetGraph()->GetArena()) LocationSummary(if_instr, LocationSummary::kNoCall);
+  HInstruction* cond = if_instr->InputAt(0);
+  if (!cond->IsCondition() || cond->AsCondition()->NeedsMaterialization()) {
+    locations->SetInAt(0, Location::Any());
+  }
+}
+
+void InstructionCodeGeneratorX86_64::VisitIf(HIf* if_instr) {
+  Label* true_target = codegen_->GetLabelOf(if_instr->IfTrueSuccessor());
+  Label* false_target = codegen_->GetLabelOf(if_instr->IfFalseSuccessor());
+  Label* always_true_target = true_target;
+  if (codegen_->GoesToNextBlock(if_instr->GetBlock(),
+                                if_instr->IfTrueSuccessor())) {
+    always_true_target = nullptr;
+  }
+  if (codegen_->GoesToNextBlock(if_instr->GetBlock(),
+                                if_instr->IfFalseSuccessor())) {
+    false_target = nullptr;
+  }
+  GenerateTestAndBranch(if_instr, true_target, false_target, always_true_target);
+}
+
+void LocationsBuilderX86_64::VisitDeoptimize(HDeoptimize* deoptimize) {
+  LocationSummary* locations = new (GetGraph()->GetArena())
+      LocationSummary(deoptimize, LocationSummary::kCallOnSlowPath);
+  HInstruction* cond = deoptimize->InputAt(0);
+  DCHECK(cond->IsCondition());
+  if (cond->AsCondition()->NeedsMaterialization()) {
+    locations->SetInAt(0, Location::Any());
   }
 }
 
+void InstructionCodeGeneratorX86_64::VisitDeoptimize(HDeoptimize* deoptimize) {
+  SlowPathCodeX86_64* slow_path = new (GetGraph()->GetArena())
+      DeoptimizationSlowPathX86_64(deoptimize);
+  codegen_->AddSlowPath(slow_path);
+  Label* slow_path_entry = slow_path->GetEntryLabel();
+  GenerateTestAndBranch(deoptimize, slow_path_entry, nullptr, slow_path_entry);
+}
+
 void LocationsBuilderX86_64::VisitLocal(HLocal* local) {
   local->SetLocations(nullptr);
 }
diff --git a/compiler/optimizing/code_generator_x86_64.h b/compiler/optimizing/code_generator_x86_64.h
index 707c9992c0..0683952973 100644
--- a/compiler/optimizing/code_generator_x86_64.h
+++ b/compiler/optimizing/code_generator_x86_64.h
@@ -163,6 +163,10 @@ class InstructionCodeGeneratorX86_64 : public HGraphVisitor {
   void GenerateExplicitNullCheck(HNullCheck* instruction);
   void PushOntoFPStack(Location source, uint32_t temp_offset,
                        uint32_t stack_adjustment, bool is_float);
+  void GenerateTestAndBranch(HInstruction* instruction,
+                             Label* true_target,
+                             Label* false_target,
+                             Label* always_true_target);
 
   X86_64Assembler* const assembler_;
   CodeGeneratorX86_64* const codegen_;
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index a90ebced69..aeb1751f24 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -696,8 +696,8 @@ HInstruction* HBinaryOperation::GetLeastConstantLeft() const {
   }
 }
 
-bool HCondition::IsBeforeWhenDisregardMoves(HIf* if_) const {
-  return this == if_->GetPreviousDisregardingMoves();
+bool HCondition::IsBeforeWhenDisregardMoves(HInstruction* instruction) const {
+  return this == instruction->GetPreviousDisregardingMoves();
 }
 
 HConstant* HConstant::NewConstant(ArenaAllocator* allocator, Primitive::Type type, int64_t val) {
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 07ff8ba010..b10231e0c6 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -616,6 +616,7 @@ class HBasicBlock : public ArenaObject<kArenaAllocMisc> {
   M(ClinitCheck, Instruction)                                           \
   M(Compare, BinaryOperation)                                           \
   M(Condition, BinaryOperation)                                         \
+  M(Deoptimize, Instruction)                                            \
   M(Div, BinaryOperation)                                               \
   M(DivZeroCheck, Instruction)                                          \
   M(DoubleConstant, Constant)                                           \
@@ -1478,12 +1479,31 @@ class HIf : public HTemplateInstruction<1> {
 
   DECLARE_INSTRUCTION(If);
 
-  virtual bool IsIfInstruction() const { return true; }
-
  private:
   DISALLOW_COPY_AND_ASSIGN(HIf);
 };
 
+// Deoptimize to interpreter, upon checking a condition.
+class HDeoptimize : public HTemplateInstruction<1> {
+ public:
+  HDeoptimize(HInstruction* cond, uint32_t dex_pc)
+      : HTemplateInstruction(SideEffects::None()),
+        dex_pc_(dex_pc) {
+    SetRawInputAt(0, cond);
+  }
+
+  bool NeedsEnvironment() const OVERRIDE { return true; }
+  bool CanThrow() const OVERRIDE { return true; }
+  uint32_t GetDexPc() const { return dex_pc_; }
+
+  DECLARE_INSTRUCTION(Deoptimize);
+
+ private:
+  uint32_t dex_pc_;
+
+  DISALLOW_COPY_AND_ASSIGN(HDeoptimize);
+};
+
 class HUnaryOperation : public HExpression<1> {
  public:
   HUnaryOperation(Primitive::Type result_type, HInstruction* input)
@@ -1601,8 +1621,8 @@ class HCondition : public HBinaryOperation {
   void ClearNeedsMaterialization() { needs_materialization_ = false; }
 
   // For code generation purposes, returns whether this instruction is just before
-  // `if_`, and disregard moves in between.
-  bool IsBeforeWhenDisregardMoves(HIf* if_) const;
+  // `instruction`, and disregard moves in between.
+  bool IsBeforeWhenDisregardMoves(HInstruction* instruction) const;
 
   DECLARE_INSTRUCTION(Condition);
 
diff --git a/compiler/optimizing/prepare_for_register_allocation.cc b/compiler/optimizing/prepare_for_register_allocation.cc
index 2d9a2bf330..01faa9dc25 100644
--- a/compiler/optimizing/prepare_for_register_allocation.cc
+++ b/compiler/optimizing/prepare_for_register_allocation.cc
@@ -64,7 +64,7 @@ void PrepareForRegisterAllocation::VisitCondition(HCondition* condition) {
     needs_materialization = true;
   } else {
     HInstruction* user = condition->GetUses().GetFirst()->GetUser();
-    if (!user->IsIf()) {
+    if (!user->IsIf() && !user->IsDeoptimize()) {
       needs_materialization = true;
     } else {
       // TODO: if there is no intervening instructions with side-effect between this condition