ARM: Reduce the number of branches generated for HCondition and HSelect
Test: m test-art-target-run-test-570-checker-select
Change-Id: I87d2e87eb2fd30355101df07eb3754b013cedf63
diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
index caea250..cb7a60d 100644
--- a/compiler/optimizing/code_generator_arm.cc
+++ b/compiler/optimizing/code_generator_arm.cc
@@ -1602,14 +1602,20 @@
}
}
-static Condition GenerateLongTestConstant(HCondition* condition,
- bool invert,
- CodeGeneratorARM* codegen) {
+static std::pair<Condition, Condition> GenerateLongTestConstant(HCondition* condition,
+ bool invert,
+ CodeGeneratorARM* codegen) {
DCHECK_EQ(condition->GetLeft()->GetType(), Primitive::kPrimLong);
const LocationSummary* const locations = condition->GetLocations();
- IfCondition cond = invert ? condition->GetOppositeCondition() : condition->GetCondition();
- Condition ret = EQ;
+ IfCondition cond = condition->GetCondition();
+ IfCondition opposite = condition->GetOppositeCondition();
+
+ if (invert) {
+ std::swap(cond, opposite);
+ }
+
+ std::pair<Condition, Condition> ret;
const Location left = locations->InAt(0);
const Location right = locations->InAt(1);
@@ -1629,22 +1635,26 @@
__ CmpConstant(left_high, High32Bits(value));
__ it(EQ);
__ cmp(left_low, ShifterOperand(Low32Bits(value)), EQ);
- ret = ARMUnsignedCondition(cond);
+ ret = std::make_pair(ARMUnsignedCondition(cond), ARMUnsignedCondition(opposite));
break;
case kCondLE:
case kCondGT:
// Trivially true or false.
if (value == std::numeric_limits<int64_t>::max()) {
__ cmp(left_low, ShifterOperand(left_low));
- ret = cond == kCondLE ? EQ : NE;
+ ret = cond == kCondLE ? std::make_pair(EQ, NE) : std::make_pair(NE, EQ);
break;
}
if (cond == kCondLE) {
+ DCHECK_EQ(opposite, kCondGT);
cond = kCondLT;
+ opposite = kCondGE;
} else {
DCHECK_EQ(cond, kCondGT);
+ DCHECK_EQ(opposite, kCondLE);
cond = kCondGE;
+ opposite = kCondLT;
}
value++;
@@ -1653,7 +1663,7 @@
case kCondLT:
__ CmpConstant(left_low, Low32Bits(value));
__ sbcs(IP, left_high, ShifterOperand(High32Bits(value)));
- ret = ARMCondition(cond);
+ ret = std::make_pair(ARMCondition(cond), ARMCondition(opposite));
break;
default:
LOG(FATAL) << "Unreachable";
@@ -1663,14 +1673,20 @@
return ret;
}
-static Condition GenerateLongTest(HCondition* condition,
- bool invert,
- CodeGeneratorARM* codegen) {
+static std::pair<Condition, Condition> GenerateLongTest(HCondition* condition,
+ bool invert,
+ CodeGeneratorARM* codegen) {
DCHECK_EQ(condition->GetLeft()->GetType(), Primitive::kPrimLong);
const LocationSummary* const locations = condition->GetLocations();
- IfCondition cond = invert ? condition->GetOppositeCondition() : condition->GetCondition();
- Condition ret = EQ;
+ IfCondition cond = condition->GetCondition();
+ IfCondition opposite = condition->GetOppositeCondition();
+
+ if (invert) {
+ std::swap(cond, opposite);
+ }
+
+ std::pair<Condition, Condition> ret;
Location left = locations->InAt(0);
Location right = locations->InAt(1);
@@ -1689,15 +1705,19 @@
__ cmp(left.AsRegisterPairLow<Register>(),
ShifterOperand(right.AsRegisterPairLow<Register>()),
EQ);
- ret = ARMUnsignedCondition(cond);
+ ret = std::make_pair(ARMUnsignedCondition(cond), ARMUnsignedCondition(opposite));
break;
case kCondLE:
case kCondGT:
if (cond == kCondLE) {
+ DCHECK_EQ(opposite, kCondGT);
cond = kCondGE;
+ opposite = kCondLT;
} else {
DCHECK_EQ(cond, kCondGT);
+ DCHECK_EQ(opposite, kCondLE);
cond = kCondLT;
+ opposite = kCondGE;
}
std::swap(left, right);
@@ -1709,7 +1729,7 @@
__ sbcs(IP,
left.AsRegisterPairHigh<Register>(),
ShifterOperand(right.AsRegisterPairHigh<Register>()));
- ret = ARMCondition(cond);
+ ret = std::make_pair(ARMCondition(cond), ARMCondition(opposite));
break;
default:
LOG(FATAL) << "Unreachable";
@@ -1719,90 +1739,83 @@
return ret;
}
-static Condition GenerateTest(HInstruction* instruction,
- Location loc,
- bool invert,
- CodeGeneratorARM* codegen) {
- DCHECK(!instruction->IsConstant());
+static std::pair<Condition, Condition> GenerateTest(HCondition* condition,
+ bool invert,
+ CodeGeneratorARM* codegen) {
+ const LocationSummary* const locations = condition->GetLocations();
+ const Primitive::Type type = condition->GetLeft()->GetType();
+ IfCondition cond = condition->GetCondition();
+ IfCondition opposite = condition->GetOppositeCondition();
+ std::pair<Condition, Condition> ret;
+ const Location right = locations->InAt(1);
- Condition ret = invert ? EQ : NE;
+ if (invert) {
+ std::swap(cond, opposite);
+ }
- if (IsBooleanValueOrMaterializedCondition(instruction)) {
- __ CmpConstant(loc.AsRegister<Register>(), 0);
+ if (type == Primitive::kPrimLong) {
+ ret = locations->InAt(1).IsConstant()
+ ? GenerateLongTestConstant(condition, invert, codegen)
+ : GenerateLongTest(condition, invert, codegen);
+ } else if (Primitive::IsFloatingPointType(type)) {
+ GenerateVcmp(condition, codegen);
+ __ vmstat();
+ ret = std::make_pair(ARMFPCondition(cond, condition->IsGtBias()),
+ ARMFPCondition(opposite, condition->IsGtBias()));
} else {
- HCondition* const condition = instruction->AsCondition();
- const LocationSummary* const locations = condition->GetLocations();
- const Primitive::Type type = condition->GetLeft()->GetType();
- const IfCondition cond = invert ? condition->GetOppositeCondition() : condition->GetCondition();
- const Location right = locations->InAt(1);
+ DCHECK(Primitive::IsIntegralType(type) || type == Primitive::kPrimNot) << type;
- if (type == Primitive::kPrimLong) {
- ret = condition->GetLocations()->InAt(1).IsConstant()
- ? GenerateLongTestConstant(condition, invert, codegen)
- : GenerateLongTest(condition, invert, codegen);
- } else if (Primitive::IsFloatingPointType(type)) {
- GenerateVcmp(condition, codegen);
- __ vmstat();
- ret = ARMFPCondition(cond, condition->IsGtBias());
+ const Register left = locations->InAt(0).AsRegister<Register>();
+
+ if (right.IsRegister()) {
+ __ cmp(left, ShifterOperand(right.AsRegister<Register>()));
} else {
- DCHECK(Primitive::IsIntegralType(type) || type == Primitive::kPrimNot) << type;
-
- const Register left = locations->InAt(0).AsRegister<Register>();
-
- if (right.IsRegister()) {
- __ cmp(left, ShifterOperand(right.AsRegister<Register>()));
- } else {
- DCHECK(right.IsConstant());
- __ CmpConstant(left, CodeGenerator::GetInt32ValueOf(right.GetConstant()));
- }
-
- ret = ARMCondition(cond);
+ DCHECK(right.IsConstant());
+ __ CmpConstant(left, CodeGenerator::GetInt32ValueOf(right.GetConstant()));
}
+
+ ret = std::make_pair(ARMCondition(cond), ARMCondition(opposite));
}
return ret;
}
-static bool CanGenerateTest(HInstruction* condition, ArmAssembler* assembler) {
- if (!IsBooleanValueOrMaterializedCondition(condition)) {
- const HCondition* const cond = condition->AsCondition();
+static bool CanGenerateTest(HCondition* condition, ArmAssembler* assembler) {
+ if (condition->GetLeft()->GetType() == Primitive::kPrimLong) {
+ const LocationSummary* const locations = condition->GetLocations();
+ const IfCondition c = condition->GetCondition();
- if (cond->GetLeft()->GetType() == Primitive::kPrimLong) {
- const LocationSummary* const locations = cond->GetLocations();
- const IfCondition c = cond->GetCondition();
+ if (locations->InAt(1).IsConstant()) {
+ const int64_t value = locations->InAt(1).GetConstant()->AsLongConstant()->GetValue();
+ ShifterOperand so;
- if (locations->InAt(1).IsConstant()) {
- const int64_t value = locations->InAt(1).GetConstant()->AsLongConstant()->GetValue();
- ShifterOperand so;
-
- if (c < kCondLT || c > kCondGE) {
- // Since IT blocks longer than a 16-bit instruction are deprecated by ARMv8,
- // we check that the least significant half of the first input to be compared
- // is in a low register (the other half is read outside an IT block), and
- // the constant fits in an 8-bit unsigned integer, so that a 16-bit CMP
- // encoding can be used.
- if (!ArmAssembler::IsLowRegister(locations->InAt(0).AsRegisterPairLow<Register>()) ||
- !IsUint<8>(Low32Bits(value))) {
- return false;
- }
- } else if (c == kCondLE || c == kCondGT) {
- if (value < std::numeric_limits<int64_t>::max() &&
- !assembler->ShifterOperandCanHold(kNoRegister,
- kNoRegister,
- SBC,
- High32Bits(value + 1),
- kCcSet,
- &so)) {
- return false;
- }
- } else if (!assembler->ShifterOperandCanHold(kNoRegister,
- kNoRegister,
- SBC,
- High32Bits(value),
- kCcSet,
- &so)) {
+ if (c < kCondLT || c > kCondGE) {
+ // Since IT blocks longer than a 16-bit instruction are deprecated by ARMv8,
+ // we check that the least significant half of the first input to be compared
+ // is in a low register (the other half is read outside an IT block), and
+ // the constant fits in an 8-bit unsigned integer, so that a 16-bit CMP
+ // encoding can be used.
+ if (!ArmAssembler::IsLowRegister(locations->InAt(0).AsRegisterPairLow<Register>()) ||
+ !IsUint<8>(Low32Bits(value))) {
return false;
}
+ } else if (c == kCondLE || c == kCondGT) {
+ if (value < std::numeric_limits<int64_t>::max() &&
+ !assembler->ShifterOperandCanHold(kNoRegister,
+ kNoRegister,
+ SBC,
+ High32Bits(value + 1),
+ kCcSet,
+ &so)) {
+ return false;
+ }
+ } else if (!assembler->ShifterOperandCanHold(kNoRegister,
+ kNoRegister,
+ SBC,
+ High32Bits(value),
+ kCcSet,
+ &so)) {
+ return false;
}
}
}
@@ -2415,13 +2428,6 @@
void InstructionCodeGeneratorARM::VisitExit(HExit* exit ATTRIBUTE_UNUSED) {
}
-void InstructionCodeGeneratorARM::GenerateFPJumps(HCondition* cond,
- Label* true_label,
- Label* false_label ATTRIBUTE_UNUSED) {
- __ vmstat(); // transfer FP status register to ARM APSR.
- __ b(true_label, ARMFPCondition(cond->GetCondition(), cond->IsGtBias()));
-}
-
void InstructionCodeGeneratorARM::GenerateLongComparesAndJumps(HCondition* cond,
Label* true_label,
Label* false_label) {
@@ -2438,7 +2444,6 @@
// Set the conditions for the test, remembering that == needs to be
// decided using the low words.
- // TODO: consider avoiding jumps with temporary and CMP low+SBC high
switch (if_cond) {
case kCondEQ:
case kCondNE:
@@ -2509,25 +2514,38 @@
void InstructionCodeGeneratorARM::GenerateCompareTestAndBranch(HCondition* condition,
Label* true_target_in,
Label* false_target_in) {
+ if (CanGenerateTest(condition, codegen_->GetAssembler())) {
+ Label* non_fallthrough_target;
+ bool invert;
+
+ if (true_target_in == nullptr) {
+ DCHECK(false_target_in != nullptr);
+ non_fallthrough_target = false_target_in;
+ invert = true;
+ } else {
+ non_fallthrough_target = true_target_in;
+ invert = false;
+ }
+
+ const auto cond = GenerateTest(condition, invert, codegen_);
+
+ __ b(non_fallthrough_target, cond.first);
+
+ if (false_target_in != nullptr && false_target_in != non_fallthrough_target) {
+ __ b(false_target_in);
+ }
+
+ return;
+ }
+
// 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;
- Primitive::Type type = condition->InputAt(0)->GetType();
- switch (type) {
- case Primitive::kPrimLong:
- GenerateLongComparesAndJumps(condition, true_target, false_target);
- break;
- case Primitive::kPrimFloat:
- case Primitive::kPrimDouble:
- GenerateVcmp(condition, codegen_);
- GenerateFPJumps(condition, true_target, false_target);
- break;
- default:
- LOG(FATAL) << "Unexpected compare type " << type;
- }
+ DCHECK_EQ(condition->InputAt(0)->GetType(), Primitive::kPrimLong);
+ GenerateLongComparesAndJumps(condition, true_target, false_target);
if (false_target != &fallthrough_target) {
__ b(false_target);
@@ -2729,7 +2747,8 @@
}
if (!Primitive::IsFloatingPointType(type) &&
- CanGenerateTest(condition, codegen_->GetAssembler())) {
+ (IsBooleanValueOrMaterializedCondition(condition) ||
+ CanGenerateTest(condition->AsCondition(), codegen_->GetAssembler()))) {
bool invert = false;
if (out.Equals(second)) {
@@ -2753,7 +2772,14 @@
codegen_->MoveLocation(out, src.Equals(first) ? second : first, type);
}
- const Condition cond = GenerateTest(condition, locations->InAt(2), invert, codegen_);
+ std::pair<Condition, Condition> cond;
+
+ if (IsBooleanValueOrMaterializedCondition(condition)) {
+ __ CmpConstant(locations->InAt(2).AsRegister<Register>(), 0);
+ cond = invert ? std::make_pair(EQ, NE) : std::make_pair(NE, EQ);
+ } else {
+ cond = GenerateTest(condition->AsCondition(), invert, codegen_);
+ }
if (out.IsRegister()) {
ShifterOperand operand;
@@ -2765,8 +2791,8 @@
operand = ShifterOperand(src.AsRegister<Register>());
}
- __ it(cond);
- __ mov(out.AsRegister<Register>(), operand, cond);
+ __ it(cond.first);
+ __ mov(out.AsRegister<Register>(), operand, cond.first);
} else {
DCHECK(out.IsRegisterPair());
@@ -2784,10 +2810,10 @@
operand_low = ShifterOperand(src.AsRegisterPairLow<Register>());
}
- __ it(cond);
- __ mov(out.AsRegisterPairLow<Register>(), operand_low, cond);
- __ it(cond);
- __ mov(out.AsRegisterPairHigh<Register>(), operand_high, cond);
+ __ it(cond.first);
+ __ mov(out.AsRegisterPairLow<Register>(), operand_low, cond.first);
+ __ it(cond.first);
+ __ mov(out.AsRegisterPairHigh<Register>(), operand_high, cond.first);
}
return;
@@ -2840,7 +2866,7 @@
locations->SetInAt(0, Location::RequiresRegister());
locations->SetInAt(1, Location::RegisterOrConstant(cond->InputAt(1)));
if (!cond->IsEmittedAtUseSite()) {
- locations->SetOut(Location::RequiresRegister(), Location::kOutputOverlap);
+ locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap);
}
break;
@@ -2867,51 +2893,44 @@
return;
}
- LocationSummary* locations = cond->GetLocations();
- Location left = locations->InAt(0);
- Location right = locations->InAt(1);
- Register out = locations->Out().AsRegister<Register>();
- Label true_label, false_label;
+ const Register out = cond->GetLocations()->Out().AsRegister<Register>();
- switch (cond->InputAt(0)->GetType()) {
- default: {
- // Integer case.
- if (right.IsRegister()) {
- __ cmp(left.AsRegister<Register>(), ShifterOperand(right.AsRegister<Register>()));
- } else {
- DCHECK(right.IsConstant());
- __ CmpConstant(left.AsRegister<Register>(),
- CodeGenerator::GetInt32ValueOf(right.GetConstant()));
- }
- __ it(ARMCondition(cond->GetCondition()), kItElse);
- __ mov(locations->Out().AsRegister<Register>(), ShifterOperand(1),
- ARMCondition(cond->GetCondition()));
- __ mov(locations->Out().AsRegister<Register>(), ShifterOperand(0),
- ARMCondition(cond->GetOppositeCondition()));
- return;
- }
- case Primitive::kPrimLong:
- GenerateLongComparesAndJumps(cond, &true_label, &false_label);
- break;
- case Primitive::kPrimFloat:
- case Primitive::kPrimDouble:
- GenerateVcmp(cond, codegen_);
- GenerateFPJumps(cond, &true_label, &false_label);
- break;
+ if (ArmAssembler::IsLowRegister(out) && CanGenerateTest(cond, codegen_->GetAssembler())) {
+ const auto condition = GenerateTest(cond, false, codegen_);
+
+ __ it(condition.first);
+ __ mov(out, ShifterOperand(1), condition.first);
+ __ it(condition.second);
+ __ mov(out, ShifterOperand(0), condition.second);
+ return;
}
// Convert the jumps into the result.
Label done_label;
- Label* final_label = codegen_->GetFinalLabel(cond, &done_label);
+ Label* const final_label = codegen_->GetFinalLabel(cond, &done_label);
- // False case: result = 0.
- __ Bind(&false_label);
- __ LoadImmediate(out, 0);
- __ b(final_label);
+ if (cond->InputAt(0)->GetType() == Primitive::kPrimLong) {
+ Label true_label, false_label;
- // True case: result = 1.
- __ Bind(&true_label);
- __ LoadImmediate(out, 1);
+ GenerateLongComparesAndJumps(cond, &true_label, &false_label);
+
+ // False case: result = 0.
+ __ Bind(&false_label);
+ __ LoadImmediate(out, 0);
+ __ b(final_label);
+
+ // True case: result = 1.
+ __ Bind(&true_label);
+ __ LoadImmediate(out, 1);
+ } else {
+ DCHECK(CanGenerateTest(cond, codegen_->GetAssembler()));
+
+ const auto condition = GenerateTest(cond, false, codegen_);
+
+ __ mov(out, ShifterOperand(0), AL, kCcKeep);
+ __ b(final_label, condition.second);
+ __ LoadImmediate(out, 1);
+ }
if (done_label.IsLinked()) {
__ Bind(&done_label);