From b8b97695d178337736b61609220613b92f344d45 Mon Sep 17 00:00:00 2001 From: Mark Mendell Date: Fri, 22 May 2015 16:58:19 -0400 Subject: [PATCH] Fix conditional jump over jmp (X86/X86-64/ARM32) Optimize the code generation for 'if' statements to jump to the 'false' block if the next block to be generated is the 'true' block. Add an X86-64 test for this case. Note that ARM64 & MIPS64 have not been updated. Change-Id: Iebb1352feb9d3bd0142d8b0621a2e3069a708ea7 Signed-off-by: Mark Mendell --- compiler/optimizing/code_generator_arm.cc | 26 ++++++++++++---- compiler/optimizing/code_generator_utils.cc | 16 ++++++++++ compiler/optimizing/code_generator_utils.h | 9 ++++++ compiler/optimizing/code_generator_x86.cc | 33 +++++++++++++++----- compiler/optimizing/code_generator_x86_64.cc | 34 ++++++++++++++++----- test/537-checker-jump-over-jump/expected.txt | 0 test/537-checker-jump-over-jump/info.txt | 1 + test/537-checker-jump-over-jump/src/Main.java | 44 +++++++++++++++++++++++++++ 8 files changed, 142 insertions(+), 21 deletions(-) create mode 100644 test/537-checker-jump-over-jump/expected.txt create mode 100644 test/537-checker-jump-over-jump/info.txt create mode 100644 test/537-checker-jump-over-jump/src/Main.java diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc index 3dc3b7fba..6d0529327 100644 --- a/compiler/optimizing/code_generator_arm.cc +++ b/compiler/optimizing/code_generator_arm.cc @@ -1300,20 +1300,29 @@ void InstructionCodeGeneratorARM::GenerateTestAndBranch(HInstruction* instructio DCHECK_EQ(cond_value, 0); } } else { - if (!cond->IsCondition() || cond->AsCondition()->NeedsMaterialization()) { - // Condition has been materialized, compare the output to 0 + // Can we optimize the jump if we know that the next block is the true case? + HCondition* condition = cond->AsCondition(); + bool can_jump_to_false = CanReverseCondition(always_true_target, false_target, condition); + if (condition == nullptr || condition->NeedsMaterialization()) { + // Condition has been materialized, compare the output to 0. DCHECK(instruction->GetLocations()->InAt(0).IsRegister()); + if (can_jump_to_false) { + __ CompareAndBranchIfZero(instruction->GetLocations()->InAt(0).AsRegister(), + false_target); + return; + } __ CompareAndBranchIfNonZero(instruction->GetLocations()->InAt(0).AsRegister(), true_target); } else { // Condition has not been materialized, use its inputs as the // comparison and its condition as the branch condition. - Primitive::Type type = - cond->IsCondition() ? cond->InputAt(0)->GetType() : Primitive::kPrimInt; + Primitive::Type type = (condition != nullptr) + ? cond->InputAt(0)->GetType() + : Primitive::kPrimInt; // 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(), cond->AsCondition(), + GenerateCompareTestAndBranch(instruction->AsIf(), condition, true_target, false_target, always_true_target); return; } @@ -1328,7 +1337,12 @@ void InstructionCodeGeneratorARM::GenerateTestAndBranch(HInstruction* instructio DCHECK(right.IsConstant()); GenerateCompareWithImmediate(left, CodeGenerator::GetInt32ValueOf(right.GetConstant())); } - __ b(true_target, ARMCondition(cond->AsCondition()->GetCondition())); + if (can_jump_to_false) { + __ b(false_target, ARMCondition(condition->GetOppositeCondition())); + return; + } + + __ b(true_target, ARMCondition(condition->GetCondition())); } } if (false_target != nullptr) { diff --git a/compiler/optimizing/code_generator_utils.cc b/compiler/optimizing/code_generator_utils.cc index 921c1d86c..bf354e7ee 100644 --- a/compiler/optimizing/code_generator_utils.cc +++ b/compiler/optimizing/code_generator_utils.cc @@ -15,6 +15,7 @@ */ #include "code_generator_utils.h" +#include "nodes.h" #include "base/logging.h" @@ -94,4 +95,19 @@ void CalculateMagicAndShiftForDivRem(int64_t divisor, bool is_long, *shift = is_long ? p - 64 : p - 32; } +// Is it valid to reverse the condition? Uses the values supplied to +// GenerateTestAndBranch() in instruction generators. +bool CanReverseCondition(Label* always_true_target, + Label* false_target, + HCondition* condition) { + // 'always_true_target' is null when the 'true' path is to the next + // block to be generated. Check the type of the condition to ensure that + // FP conditions are not swapped. This is for future fusing of HCompare and + // HCondition. + // Note: If the condition is nullptr, then it is always okay to reverse. + return always_true_target == nullptr && false_target != nullptr && + (condition == nullptr || + !Primitive::IsFloatingPointType(condition->InputAt(0)->GetType())); +} + } // namespace art diff --git a/compiler/optimizing/code_generator_utils.h b/compiler/optimizing/code_generator_utils.h index 59b495c2c..628eee888 100644 --- a/compiler/optimizing/code_generator_utils.h +++ b/compiler/optimizing/code_generator_utils.h @@ -21,10 +21,19 @@ namespace art { +class Label; +class HCondition; + // Computes the magic number and the shift needed in the div/rem by constant algorithm, as out // arguments `magic` and `shift` void CalculateMagicAndShiftForDivRem(int64_t divisor, bool is_long, int64_t* magic, int* shift); +// Is it valid to reverse the condition? Uses the values supplied to +// GenerateTestAndBranch() in instruction generators. +bool CanReverseCondition(Label* always_true_target, + Label* false_target, + HCondition* condition); + } // namespace art #endif // ART_COMPILER_OPTIMIZING_CODE_GENERATOR_UTILS_H_ diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc index 0df7e3b30..0db5837b9 100644 --- a/compiler/optimizing/code_generator_x86.cc +++ b/compiler/optimizing/code_generator_x86.cc @@ -1216,16 +1216,21 @@ void InstructionCodeGeneratorX86::GenerateTestAndBranch(HInstruction* instructio DCHECK_EQ(cond_value, 0); } } else { + HCondition* condition = cond->AsCondition(); bool is_materialized = - !cond->IsCondition() || cond->AsCondition()->NeedsMaterialization(); + 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 long/FP conditions if they are // materialized due to the complex branching. - Primitive::Type type = cond->IsCondition() ? cond->InputAt(0)->GetType() : Primitive::kPrimInt; - bool eflags_set = cond->IsCondition() - && cond->AsCondition()->IsBeforeWhenDisregardMoves(instruction) + Primitive::Type type = (condition != nullptr) + ? cond->InputAt(0)->GetType() + : Primitive::kPrimInt; + bool eflags_set = condition != nullptr + && condition->IsBeforeWhenDisregardMoves(instruction) && (type != Primitive::kPrimLong && !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. @@ -1235,9 +1240,17 @@ void InstructionCodeGeneratorX86::GenerateTestAndBranch(HInstruction* instructio } else { __ cmpl(Address(ESP, lhs.GetStackIndex()), Immediate(0)); } + if (can_jump_to_false) { + __ j(kEqual, false_target); + return; + } __ j(kNotEqual, true_target); } else { - __ j(X86Condition(cond->AsCondition()->GetCondition()), true_target); + if (can_jump_to_false) { + __ j(X86Condition(condition->GetOppositeCondition()), false_target); + return; + } + __ j(X86Condition(condition->GetCondition()), true_target); } } else { // Condition has not been materialized, use its inputs as the @@ -1247,7 +1260,7 @@ void InstructionCodeGeneratorX86::GenerateTestAndBranch(HInstruction* instructio if (type == Primitive::kPrimLong || Primitive::IsFloatingPointType(type)) { // Generate the comparison directly. GenerateCompareTestAndBranch(instruction->AsIf(), - cond->AsCondition(), + condition, true_target, false_target, always_true_target); @@ -1270,7 +1283,13 @@ void InstructionCodeGeneratorX86::GenerateTestAndBranch(HInstruction* instructio } else { __ cmpl(lhs.AsRegister(), Address(ESP, rhs.GetStackIndex())); } - __ j(X86Condition(cond->AsCondition()->GetCondition()), true_target); + + if (can_jump_to_false) { + __ j(X86Condition(condition->GetOppositeCondition()), false_target); + return; + } + + __ j(X86Condition(condition->GetCondition()), true_target); } } if (false_target != nullptr) { diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc index 5218d7099..b5abec24d 100644 --- a/compiler/optimizing/code_generator_x86_64.cc +++ b/compiler/optimizing/code_generator_x86_64.cc @@ -1183,16 +1183,20 @@ void InstructionCodeGeneratorX86_64::GenerateTestAndBranch(HInstruction* instruc DCHECK_EQ(cond_value, 0); } } else { - bool is_materialized = - !cond->IsCondition() || cond->AsCondition()->NeedsMaterialization(); + 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 = cond->IsCondition() ? cond->InputAt(0)->GetType() : Primitive::kPrimInt; - bool eflags_set = cond->IsCondition() - && cond->AsCondition()->IsBeforeWhenDisregardMoves(instruction) + 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) { @@ -1204,9 +1208,17 @@ void InstructionCodeGeneratorX86_64::GenerateTestAndBranch(HInstruction* instruc __ cmpl(Address(CpuRegister(RSP), lhs.GetStackIndex()), Immediate(0)); } + if (can_jump_to_false) { + __ j(kEqual, false_target); + return; + } __ j(kNotEqual, true_target); } else { - __ j(X86_64IntegerCondition(cond->AsCondition()->GetCondition()), true_target); + if (can_jump_to_false) { + __ j(X86_64IntegerCondition(condition->GetOppositeCondition()), false_target); + return; + } + __ j(X86_64IntegerCondition(condition->GetCondition()), true_target); } } else { // Condition has not been materialized, use its inputs as the @@ -1215,7 +1227,7 @@ void InstructionCodeGeneratorX86_64::GenerateTestAndBranch(HInstruction* instruc // 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(), cond->AsCondition(), + GenerateCompareTestAndBranch(instruction->AsIf(), condition, true_target, false_target, always_true_target); return; } @@ -1235,7 +1247,13 @@ void InstructionCodeGeneratorX86_64::GenerateTestAndBranch(HInstruction* instruc __ cmpl(lhs.AsRegister(), Address(CpuRegister(RSP), rhs.GetStackIndex())); } - __ j(X86_64IntegerCondition(cond->AsCondition()->GetCondition()), true_target); + + if (can_jump_to_false) { + __ j(X86_64IntegerCondition(condition->GetOppositeCondition()), false_target); + return; + } + + __ j(X86_64IntegerCondition(condition->GetCondition()), true_target); } } if (false_target != nullptr) { diff --git a/test/537-checker-jump-over-jump/expected.txt b/test/537-checker-jump-over-jump/expected.txt new file mode 100644 index 000000000..e69de29bb diff --git a/test/537-checker-jump-over-jump/info.txt b/test/537-checker-jump-over-jump/info.txt new file mode 100644 index 000000000..aeb30bb90 --- /dev/null +++ b/test/537-checker-jump-over-jump/info.txt @@ -0,0 +1 @@ +Test for X86-64 elimination of jump over jump. diff --git a/test/537-checker-jump-over-jump/src/Main.java b/test/537-checker-jump-over-jump/src/Main.java new file mode 100644 index 000000000..fb666eaae --- /dev/null +++ b/test/537-checker-jump-over-jump/src/Main.java @@ -0,0 +1,44 @@ +/* + * Copyright (C) 2015 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + + +public class Main { + public static int FIBCOUNT = 64; + public static int[] fibs; + + /// CHECK-START-X86_64: int Main.test() disassembly (after) + /// CHECK: If + /// CHECK-NEXT: cmp + /// CHECK-NEXT: jnl/ge + /// CHECK-NOT: jmp + /// CHECK: ArrayGet + // Checks that there is no conditional jump over a jmp. The ArrayGet is in + // the next block. + public static int test() { + for (int i = 1; ; i++) { + if (i >= FIBCOUNT) { + return fibs[0]; + } + fibs[i] = (i + fibs[(i - 1)]); + } + } + + public static void main(String[] args) { + fibs = new int[FIBCOUNT]; + fibs[0] = 1; + test(); + } +} -- 2.11.0