ART: Refactor GenerateTestAndBranch
Each code generator implements a method for generating condition
evaluation and branching to arbitrary labels. This patch refactors
it for better clarity but also to generate fewer jumps when the true
branch is the fallthrough successor.
This is preliminary work for implementing HSelect.
Change-Id: Iaa545a5ecbacb761c5aa241fa69140cf6eb5952f
diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc
index d55c084..4088160 100644
--- a/compiler/optimizing/code_generator_x86_64.cc
+++ b/compiler/optimizing/code_generator_x86_64.cc
@@ -1304,26 +1304,19 @@
__ j(X86_64FPCondition(cond->GetCondition()), true_label);
}
-void InstructionCodeGeneratorX86_64::GenerateCompareTestAndBranch(HIf* if_instr,
- HCondition* condition,
- Label* true_target,
- Label* false_target,
- Label* always_true_target) {
+void InstructionCodeGeneratorX86_64::GenerateCompareTestAndBranch(HCondition* condition,
+ Label* true_target_in,
+ Label* false_target_in) {
+ // Generated branching requires both targets to be explicit. If either of the
+ // targets is nullptr (fallthrough) use and bind `fallthrough_target` instead.
+ Label fallthrough_target;
+ Label* true_target = true_target_in == nullptr ? &fallthrough_target : true_target_in;
+ Label* false_target = false_target_in == nullptr ? &fallthrough_target : false_target_in;
+
LocationSummary* locations = condition->GetLocations();
Location left = locations->InAt(0);
Location right = locations->InAt(1);
- // We don't want true_target as a nullptr.
- if (true_target == nullptr) {
- true_target = always_true_target;
- }
- bool falls_through = (false_target == nullptr);
-
- // FP compares don't like null false_targets.
- if (false_target == nullptr) {
- false_target = codegen_->GetLabelOf(if_instr->IfFalseSuccessor());
- }
-
Primitive::Type type = condition->InputAt(0)->GetType();
switch (type) {
case Primitive::kPrimLong: {
@@ -1382,135 +1375,140 @@
LOG(FATAL) << "Unexpected condition type " << type;
}
- if (!falls_through) {
+ if (false_target != &fallthrough_target) {
__ jmp(false_target);
}
+
+ if (fallthrough_target.IsLinked()) {
+ __ Bind(&fallthrough_target);
+ }
}
+static bool AreEflagsSetFrom(HInstruction* cond, HInstruction* branch) {
+ // Moves may affect the eflags register (move zero uses xorl), so the EFLAGS
+ // are set only strictly before `branch`. We can't use the eflags on long
+ // conditions if they are materialized due to the complex branching.
+ return cond->IsCondition() &&
+ cond->GetNext() == branch &&
+ !Primitive::IsFloatingPointType(cond->InputAt(0)->GetType());
+}
+
void InstructionCodeGeneratorX86_64::GenerateTestAndBranch(HInstruction* instruction,
+ size_t condition_input_index,
Label* true_target,
- Label* false_target,
- Label* always_true_target) {
- HInstruction* cond = instruction->InputAt(0);
- if (cond->IsIntConstant()) {
+ Label* false_target) {
+ HInstruction* cond = instruction->InputAt(condition_input_index);
+
+ if (true_target == nullptr && false_target == nullptr) {
+ // Nothing to do. The code always falls through.
+ return;
+ } else if (cond->IsIntConstant()) {
// Constant condition, statically compared against 1.
- int32_t cond_value = cond->AsIntConstant()->GetValue();
- if (cond_value == 1) {
- if (always_true_target != nullptr) {
- __ jmp(always_true_target);
+ if (cond->AsIntConstant()->IsOne()) {
+ if (true_target != nullptr) {
+ __ jmp(true_target);
}
- return;
} else {
- DCHECK_EQ(cond_value, 0);
+ DCHECK(cond->AsIntConstant()->IsZero());
+ if (false_target != nullptr) {
+ __ jmp(false_target);
+ }
+ }
+ return;
+ }
+
+ // The following code generates these patterns:
+ // (1) true_target == nullptr && false_target != nullptr
+ // - opposite condition true => branch to false_target
+ // (2) true_target != nullptr && false_target == nullptr
+ // - condition true => branch to true_target
+ // (3) true_target != nullptr && false_target != nullptr
+ // - condition true => branch to true_target
+ // - branch to false_target
+ if (IsBooleanValueOrMaterializedCondition(cond)) {
+ if (AreEflagsSetFrom(cond, instruction)) {
+ if (true_target == nullptr) {
+ __ j(X86_64IntegerCondition(cond->AsCondition()->GetOppositeCondition()), false_target);
+ } else {
+ __ j(X86_64IntegerCondition(cond->AsCondition()->GetCondition()), true_target);
+ }
+ } else {
+ // Materialized condition, compare against 0.
+ Location lhs = instruction->GetLocations()->InAt(condition_input_index);
+ if (lhs.IsRegister()) {
+ __ testl(lhs.AsRegister<CpuRegister>(), lhs.AsRegister<CpuRegister>());
+ } else {
+ __ cmpl(Address(CpuRegister(RSP), lhs.GetStackIndex()), Immediate(0));
+ }
+ if (true_target == nullptr) {
+ __ j(kEqual, false_target);
+ } else {
+ __ j(kNotEqual, true_target);
+ }
}
} else {
+ // Condition has not been materialized, use its inputs as the
+ // comparison and its condition as the branch condition.
HCondition* condition = cond->AsCondition();
- bool is_materialized = condition == nullptr || condition->NeedsMaterialization();
- // Moves do not affect the eflags register, so if the condition is
- // evaluated just before the if, we don't need to evaluate it
- // again. We can't use the eflags on FP conditions if they are
- // materialized due to the complex branching.
- Primitive::Type type = (condition != nullptr)
- ? cond->InputAt(0)->GetType()
- : Primitive::kPrimInt;
- bool eflags_set = condition != nullptr
- && condition->IsBeforeWhenDisregardMoves(instruction)
- && !Primitive::IsFloatingPointType(type);
- // Can we optimize the jump if we know that the next block is the true case?
- bool can_jump_to_false = CanReverseCondition(always_true_target, false_target, condition);
- if (is_materialized) {
- if (!eflags_set) {
- // Materialized condition, compare against 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));
- }
- if (can_jump_to_false) {
- __ j(kEqual, false_target);
- return;
- }
- __ j(kNotEqual, true_target);
+ // If this is a long or FP comparison that has been folded into
+ // the HCondition, generate the comparison directly.
+ Primitive::Type type = condition->InputAt(0)->GetType();
+ if (type == Primitive::kPrimLong || Primitive::IsFloatingPointType(type)) {
+ GenerateCompareTestAndBranch(condition, true_target, false_target);
+ return;
+ }
+
+ Location lhs = condition->GetLocations()->InAt(0);
+ Location rhs = condition->GetLocations()->InAt(1);
+ if (rhs.IsRegister()) {
+ __ cmpl(lhs.AsRegister<CpuRegister>(), rhs.AsRegister<CpuRegister>());
+ } else if (rhs.IsConstant()) {
+ int32_t constant = CodeGenerator::GetInt32ValueOf(rhs.GetConstant());
+ if (constant == 0) {
+ __ testl(lhs.AsRegister<CpuRegister>(), lhs.AsRegister<CpuRegister>());
} else {
- if (can_jump_to_false) {
- __ j(X86_64IntegerCondition(condition->GetOppositeCondition()), false_target);
- return;
- }
- __ j(X86_64IntegerCondition(condition->GetCondition()), true_target);
+ __ cmpl(lhs.AsRegister<CpuRegister>(), Immediate(constant));
}
} else {
- // Condition has not been materialized, use its inputs as the
- // comparison and its condition as the branch condition.
-
- // Is this a long or FP comparison that has been folded into the HCondition?
- if (type == Primitive::kPrimLong || Primitive::IsFloatingPointType(type)) {
- // Generate the comparison directly.
- GenerateCompareTestAndBranch(instruction->AsIf(), condition,
- true_target, false_target, always_true_target);
- return;
- }
-
- Location lhs = cond->GetLocations()->InAt(0);
- Location rhs = cond->GetLocations()->InAt(1);
- if (rhs.IsRegister()) {
- __ cmpl(lhs.AsRegister<CpuRegister>(), rhs.AsRegister<CpuRegister>());
- } else if (rhs.IsConstant()) {
- int32_t constant = CodeGenerator::GetInt32ValueOf(rhs.GetConstant());
- if (constant == 0) {
- __ testl(lhs.AsRegister<CpuRegister>(), lhs.AsRegister<CpuRegister>());
- } else {
- __ cmpl(lhs.AsRegister<CpuRegister>(), Immediate(constant));
- }
- } else {
- __ cmpl(lhs.AsRegister<CpuRegister>(),
- Address(CpuRegister(RSP), rhs.GetStackIndex()));
- }
-
- if (can_jump_to_false) {
- __ j(X86_64IntegerCondition(condition->GetOppositeCondition()), false_target);
- return;
- }
-
+ __ cmpl(lhs.AsRegister<CpuRegister>(),
+ Address(CpuRegister(RSP), rhs.GetStackIndex()));
+ }
+ if (true_target == nullptr) {
+ __ j(X86_64IntegerCondition(condition->GetOppositeCondition()), false_target);
+ } else {
__ j(X86_64IntegerCondition(condition->GetCondition()), true_target);
}
}
- if (false_target != nullptr) {
+
+ // If neither branch falls through (case 3), the conditional branch to `true_target`
+ // was already emitted (case 2) and we need to emit a jump to `false_target`.
+ if (true_target != nullptr && 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()) {
+ LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(if_instr);
+ if (IsBooleanValueOrMaterializedCondition(if_instr->InputAt(0))) {
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);
+ HBasicBlock* true_successor = if_instr->IfTrueSuccessor();
+ HBasicBlock* false_successor = if_instr->IfFalseSuccessor();
+ Label* true_target = codegen_->GoesToNextBlock(if_instr->GetBlock(), true_successor) ?
+ nullptr : codegen_->GetLabelOf(true_successor);
+ Label* false_target = codegen_->GoesToNextBlock(if_instr->GetBlock(), false_successor) ?
+ nullptr : codegen_->GetLabelOf(false_successor);
+ GenerateTestAndBranch(if_instr, /* condition_input_index */ 0, true_target, false_target);
}
void LocationsBuilderX86_64::VisitDeoptimize(HDeoptimize* deoptimize) {
LocationSummary* locations = new (GetGraph()->GetArena())
LocationSummary(deoptimize, LocationSummary::kCallOnSlowPath);
- HInstruction* cond = deoptimize->InputAt(0);
- if (!cond->IsCondition() || cond->AsCondition()->NeedsMaterialization()) {
+ if (IsBooleanValueOrMaterializedCondition(deoptimize->InputAt(0))) {
locations->SetInAt(0, Location::Any());
}
}
@@ -1519,8 +1517,10 @@
SlowPathCode* 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);
+ GenerateTestAndBranch(deoptimize,
+ /* condition_input_index */ 0,
+ slow_path->GetEntryLabel(),
+ /* false_target */ nullptr);
}
void LocationsBuilderX86_64::VisitLocal(HLocal* local) {