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
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index 1d16794..7444f6e 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -443,9 +443,31 @@
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 @@
}
}
+ 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 @@
}
}
+ 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 24fa583..5632f2b 100644
--- a/compiler/optimizing/bounds_check_elimination_test.cc
+++ b/compiler/optimizing/bounds_check_elimination_test.cc
@@ -289,9 +289,9 @@
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,9 +319,20 @@
HNullCheck* null_check = new (&allocator) HNullCheck(parameter, 0);
HArrayLength* array_length = new (&allocator) HArrayLength(null_check);
+ HBoundsCheck* bounds_check6 = new (&allocator)
+ HBoundsCheck(constant_6, array_length, 0);
+ HInstruction* array_set = new (&allocator) HArraySet(
+ null_check, bounds_check6, constant_1, Primitive::kPrimInt, 0);
+ block->AddInstruction(null_check);
+ block->AddInstruction(array_length);
+ block->AddInstruction(bounds_check6);
+ block->AddInstruction(array_set);
+
+ null_check = new (&allocator) HNullCheck(parameter, 0);
+ array_length = new (&allocator) HArrayLength(null_check);
HBoundsCheck* bounds_check5 = new (&allocator)
HBoundsCheck(constant_5, array_length, 0);
- HInstruction* array_set = new (&allocator) HArraySet(
+ array_set = new (&allocator) HArraySet(
null_check, bounds_check5, constant_1, Primitive::kPrimInt, 0);
block->AddInstruction(null_check);
block->AddInstruction(array_length);
@@ -339,17 +350,6 @@
block->AddInstruction(bounds_check4);
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);
- array_set = new (&allocator) HArraySet(
- null_check, bounds_check6, constant_1, Primitive::kPrimInt, 0);
- block->AddInstruction(null_check);
- block->AddInstruction(array_length);
- block->AddInstruction(bounds_check6);
- block->AddInstruction(array_set);
-
block->AddInstruction(new (&allocator) HGoto());
HBasicBlock* exit = new (&allocator) HBasicBlock(graph);
@@ -361,9 +361,9 @@
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 0a069a7..363fbef 100644
--- a/compiler/optimizing/code_generator_arm.cc
+++ b/compiler/optimizing/code_generator_arm.cc
@@ -305,6 +305,26 @@
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 @@
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 @@
} 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 @@
__ 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 57e1d2f..946a8a5 100644
--- a/compiler/optimizing/code_generator_arm.h
+++ b/compiler/optimizing/code_generator_arm.h
@@ -169,6 +169,10 @@
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 99283a0..44bd399 100644
--- a/compiler/optimizing/code_generator_arm64.cc
+++ b/compiler/optimizing/code_generator_arm64.cc
@@ -375,6 +375,26 @@
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 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 @@
}
} 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 @@
__ 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 cbb2e5c..860b250 100644
--- a/compiler/optimizing/code_generator_arm64.h
+++ b/compiler/optimizing/code_generator_arm64.h
@@ -140,6 +140,10 @@
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 02b9b32..44bbccc 100644
--- a/compiler/optimizing/code_generator_x86.cc
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -324,6 +324,27 @@
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 @@
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 @@
// 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 @@
} 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 c5763de..7c7365f 100644
--- a/compiler/optimizing/code_generator_x86.h
+++ b/compiler/optimizing/code_generator_x86.h
@@ -157,6 +157,10 @@
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 d09c8f8..d8b9450 100644
--- a/compiler/optimizing/code_generator_x86_64.cc
+++ b/compiler/optimizing/code_generator_x86_64.cc
@@ -331,6 +331,27 @@
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 @@
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 @@
// 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 @@
__ 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 707c999..0683952 100644
--- a/compiler/optimizing/code_generator_x86_64.h
+++ b/compiler/optimizing/code_generator_x86_64.h
@@ -163,6 +163,10 @@
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 a90ebce..aeb1751 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -696,8 +696,8 @@
}
}
-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 07ff8ba..b10231e 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -616,6 +616,7 @@
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 @@
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 @@
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 2d9a2bf..01faa9d 100644
--- a/compiler/optimizing/prepare_for_register_allocation.cc
+++ b/compiler/optimizing/prepare_for_register_allocation.cc
@@ -64,7 +64,7 @@
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