diff options
| -rw-r--r-- | compiler/optimizing/instruction_simplifier.cc | 63 | ||||
| -rw-r--r-- | compiler/optimizing/select_generator.cc | 17 | ||||
| -rw-r--r-- | test/678-checker-simd-saturation/src/Main.java | 23 | ||||
| -rw-r--r-- | test/679-checker-minmax/src/Main.java | 130 |
4 files changed, 208 insertions, 25 deletions
diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc index 676fe6bcb7..7d0add3833 100644 --- a/compiler/optimizing/instruction_simplifier.cc +++ b/compiler/optimizing/instruction_simplifier.cc @@ -903,6 +903,30 @@ static bool AreLowerPrecisionArgs(DataType::Type to_type, HInstruction* a, HInst to_type == DataType::Type::kInt64); } +// Returns an acceptable substitution for "a" on the select +// construct "a <cmp> b ? c : .." during MIN/MAX recognition. +static HInstruction* AllowInMinMax(IfCondition cmp, + HInstruction* a, + HInstruction* b, + HInstruction* c) { + int64_t value = 0; + if (IsInt64AndGet(b, /*out*/ &value) && + (((cmp == kCondLT || cmp == kCondLE) && c->IsMax()) || + ((cmp == kCondGT || cmp == kCondGE) && c->IsMin()))) { + HConstant* other = c->AsBinaryOperation()->GetConstantRight(); + if (other != nullptr && a == c->AsBinaryOperation()->GetLeastConstantLeft()) { + int64_t other_value = Int64FromConstant(other); + bool is_max = (cmp == kCondLT || cmp == kCondLE); + // Allow the max for a < 100 ? max(a, -100) : .. + // or the min for a > -100 ? min(a, 100) : .. + if (is_max ? (value >= other_value) : (value <= other_value)) { + return c; + } + } + } + return nullptr; +} + void InstructionSimplifierVisitor::VisitSelect(HSelect* select) { HInstruction* replace_with = nullptr; HInstruction* condition = select->GetCondition(); @@ -946,9 +970,17 @@ void InstructionSimplifierVisitor::VisitSelect(HSelect* select) { DataType::Type t_type = true_value->GetType(); DataType::Type f_type = false_value->GetType(); // Here we have a <cmp> b ? true_value : false_value. - // Test if both values are compatible integral types (resulting - // MIN/MAX/ABS type will be int or long, like the condition). + // Test if both values are compatible integral types (resulting MIN/MAX/ABS + // type will be int or long, like the condition). Replacements are general, + // but assume conditions prefer constants on the right. if (DataType::IsIntegralType(t_type) && DataType::Kind(t_type) == DataType::Kind(f_type)) { + // Allow a < 100 ? max(a, -100) : .. + // or a > -100 ? min(a, 100) : .. + // to use min/max instead of a to detect nested min/max expressions. + HInstruction* new_a = AllowInMinMax(cmp, a, b, true_value); + if (new_a != nullptr) { + a = new_a; + } // Try to replace typical integral MIN/MAX/ABS constructs. if ((cmp == kCondLT || cmp == kCondLE || cmp == kCondGT || cmp == kCondGE) && ((a == true_value && b == false_value) || @@ -957,19 +989,16 @@ void InstructionSimplifierVisitor::VisitSelect(HSelect* select) { // or a > b ? a : b (MAX) or a > b ? b : a (MIN). bool is_min = (cmp == kCondLT || cmp == kCondLE) == (a == true_value); replace_with = NewIntegralMinMax(GetGraph()->GetAllocator(), a, b, select, is_min); - } else if (true_value->IsNeg()) { - HInstruction* negated = true_value->InputAt(0); - if ((cmp == kCondLT || cmp == kCondLE) && - (a == negated && a == false_value && IsInt64Value(b, 0))) { - // Found a < 0 ? -a : a which can be replaced by ABS(a). - replace_with = NewIntegralAbs(GetGraph()->GetAllocator(), false_value, select); - } - } else if (false_value->IsNeg()) { - HInstruction* negated = false_value->InputAt(0); - if ((cmp == kCondGT || cmp == kCondGE) && - (a == true_value && a == negated && IsInt64Value(b, 0))) { - // Found a > 0 ? a : -a which can be replaced by ABS(a). - replace_with = NewIntegralAbs(GetGraph()->GetAllocator(), true_value, select); + } else if (((cmp == kCondLT || cmp == kCondLE) && true_value->IsNeg()) || + ((cmp == kCondGT || cmp == kCondGE) && false_value->IsNeg())) { + bool negLeft = (cmp == kCondLT || cmp == kCondLE); + HInstruction* the_negated = negLeft ? true_value->InputAt(0) : false_value->InputAt(0); + HInstruction* not_negated = negLeft ? false_value : true_value; + if (a == the_negated && a == not_negated && IsInt64Value(b, 0)) { + // Found a < 0 ? -a : a + // or a > 0 ? a : -a + // which can be replaced by ABS(a). + replace_with = NewIntegralAbs(GetGraph()->GetAllocator(), a, select); } } else if (true_value->IsSub() && false_value->IsSub()) { HInstruction* true_sub1 = true_value->InputAt(0); @@ -981,8 +1010,8 @@ void InstructionSimplifierVisitor::VisitSelect(HSelect* select) { ((cmp == kCondLT || cmp == kCondLE) && (a == true_sub2 && b == true_sub1 && a == false_sub1 && b == false_sub2))) && AreLowerPrecisionArgs(t_type, a, b)) { - // Found a > b ? a - b : b - a or - // a < b ? b - a : a - b + // Found a > b ? a - b : b - a + // or a < b ? b - a : a - b // which can be replaced by ABS(a - b) for lower precision operands a, b. replace_with = NewIntegralAbs(GetGraph()->GetAllocator(), true_value, select); } diff --git a/compiler/optimizing/select_generator.cc b/compiler/optimizing/select_generator.cc index 66e51421ca..3f52bdd13c 100644 --- a/compiler/optimizing/select_generator.cc +++ b/compiler/optimizing/select_generator.cc @@ -43,12 +43,16 @@ static bool IsSimpleBlock(HBasicBlock* block) { for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { HInstruction* instruction = it.Current(); if (instruction->IsControlFlow()) { - if (num_instructions > kMaxInstructionsInBranch) { - return false; - } return instruction->IsGoto() || instruction->IsReturn(); } else if (instruction->CanBeMoved() && !instruction->HasSideEffects()) { - num_instructions++; + if (instruction->IsSelect() && + instruction->AsSelect()->GetCondition()->GetBlock() == block) { + // Count one HCondition and HSelect in the same block as a single instruction. + // This enables finding nested selects. + continue; + } else if (++num_instructions > kMaxInstructionsInBranch) { + return false; // bail as soon as we exceed number of allowed instructions + } } else { return false; } @@ -97,6 +101,7 @@ void HSelectGenerator::Run() { HBasicBlock* true_block = if_instruction->IfTrueSuccessor(); HBasicBlock* false_block = if_instruction->IfFalseSuccessor(); DCHECK_NE(true_block, false_block); + if (!IsSimpleBlock(true_block) || !IsSimpleBlock(false_block) || !BlocksMergeTogether(true_block, false_block)) { @@ -107,10 +112,10 @@ void HSelectGenerator::Run() { // If the branches are not empty, move instructions in front of the If. // TODO(dbrazdil): This puts an instruction between If and its condition. // Implement moving of conditions to first users if possible. - if (!true_block->IsSingleGoto() && !true_block->IsSingleReturn()) { + while (!true_block->IsSingleGoto() && !true_block->IsSingleReturn()) { true_block->GetFirstInstruction()->MoveBefore(if_instruction); } - if (!false_block->IsSingleGoto() && !false_block->IsSingleReturn()) { + while (!false_block->IsSingleGoto() && !false_block->IsSingleReturn()) { false_block->GetFirstInstruction()->MoveBefore(if_instruction); } DCHECK(true_block->IsSingleGoto() || true_block->IsSingleReturn()); diff --git a/test/678-checker-simd-saturation/src/Main.java b/test/678-checker-simd-saturation/src/Main.java index decc691789..7a22ca175d 100644 --- a/test/678-checker-simd-saturation/src/Main.java +++ b/test/678-checker-simd-saturation/src/Main.java @@ -397,7 +397,22 @@ public class Main { } } - // TODO: recognize the more common if-else too. + /// CHECK-START: void Main.satAlt2(short[], short[], short[]) loop_optimization (before) + /// CHECK-DAG: <<Clp1:i\d+>> IntConstant -32768 loop:none + /// CHECK-DAG: <<Clp2:i\d+>> IntConstant 32767 loop:none + /// CHECK-DAG: <<Get1:s\d+>> ArrayGet [{{l\d+}},<<Phi:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none + /// CHECK-DAG: <<Get2:s\d+>> ArrayGet [{{l\d+}},<<Phi>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<Add:i\d+>> Add [<<Get1>>,<<Get2>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<Max:i\d+>> Max [<<Add>>,<<Clp1>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<Min:i\d+>> Min [<<Max>>,<<Clp2>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<Conv:s\d+>> TypeConversion [<<Min>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: ArraySet [{{l\d+}},<<Phi>>,<<Conv>>] loop:<<Loop>> outer_loop:none + // + /// CHECK-START-{ARM,ARM64}: void Main.satAlt2(short[], short[], short[]) loop_optimization (after) + /// CHECK-DAG: <<Get1:d\d+>> VecLoad [{{l\d+}},<<Phi:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none + /// CHECK-DAG: <<Get2:d\d+>> VecLoad [{{l\d+}},<<Phi>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<Add:d\d+>> VecSaturationAdd [<<Get1>>,<<Get2>>] packed_type:Int16 loop:<<Loop>> outer_loop:none + /// CHECK-DAG: VecStore [{{l\d+}},<<Phi>>,<<Add>>] loop:<<Loop>> outer_loop:none public static void satAlt2(short[] a, short[] b, short[] c) { int n = Math.min(a.length, Math.min(b.length, c.length)); for (int i = 0; i < n; i++) { @@ -411,7 +426,11 @@ public class Main { } } - // TODO: recognize conditional too. + /// CHECK-START-{ARM,ARM64}: void Main.satAlt3(short[], short[], short[]) loop_optimization (after) + /// CHECK-DAG: <<Get1:d\d+>> VecLoad [{{l\d+}},<<Phi:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none + /// CHECK-DAG: <<Get2:d\d+>> VecLoad [{{l\d+}},<<Phi>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<Add:d\d+>> VecSaturationAdd [<<Get1>>,<<Get2>>] packed_type:Int16 loop:<<Loop>> outer_loop:none + /// CHECK-DAG: VecStore [{{l\d+}},<<Phi>>,<<Add>>] loop:<<Loop>> outer_loop:none public static void satAlt3(short[] a, short[] b, short[] c) { int n = Math.min(a.length, Math.min(b.length, c.length)); for (int i = 0; i < n; i++) { diff --git a/test/679-checker-minmax/src/Main.java b/test/679-checker-minmax/src/Main.java index 38085bbd7b..4f0261c0a3 100644 --- a/test/679-checker-minmax/src/Main.java +++ b/test/679-checker-minmax/src/Main.java @@ -19,6 +19,10 @@ */ public class Main { + // + // Different types. + // + /// CHECK-START: int Main.min1(int, int) instruction_simplifier$after_inlining (before) /// CHECK-DAG: <<Cnd:z\d+>> GreaterThanOrEqual [<<Op1:i\d+>>,<<Op2:i\d+>>] /// CHECK-DAG: <<Sel:i\d+>> Select [<<Op1>>,<<Op2>>,<<Cnd>>] @@ -229,7 +233,116 @@ public class Main { return a >= b ? a : b; } + + // + // Complications. + // + + // TODO: coming soon, under discussion + public static int min0(int[] a, int[] b) { + // Repeat of array references needs finding the common subexpressions + // prior to doing the select and min/max recognition. + return a[0] <= b[0] ? a[0] : b[0]; + } + + // TODO: coming soon, under discussion + public static int max0(int[] a, int[] b) { + // Repeat of array references needs finding the common subexpressions + // prior to doing the select and min/max recognition. + return a[0] >= b[0] ? a[0] : b[0]; + } + + /// CHECK-START: int Main.minmax1(int) instruction_simplifier$after_inlining (before) + /// CHECK-DAG: <<Par:i\d+>> ParameterValue + /// CHECK-DAG: <<P100:i\d+>> IntConstant 100 + /// CHECK-DAG: <<M100:i\d+>> IntConstant -100 + /// CHECK-DAG: <<Cnd1:z\d+>> LessThanOrEqual [<<Par>>,<<P100>>] + /// CHECK-DAG: <<Sel1:i\d+>> Select [<<P100>>,<<Par>>,<<Cnd1>>] + /// CHECK-DAG: <<Cnd2:z\d+>> GreaterThanOrEqual [<<Sel1>>,<<M100>>] + /// CHECK-DAG: <<Sel2:i\d+>> Select [<<M100>>,<<Sel1>>,<<Cnd2>>] + /// CHECK-DAG: Return [<<Sel2>>] + // + /// CHECK-START: int Main.minmax1(int) instruction_simplifier$after_inlining (after) + /// CHECK-DAG: <<Par:i\d+>> ParameterValue + /// CHECK-DAG: <<P100:i\d+>> IntConstant 100 + /// CHECK-DAG: <<M100:i\d+>> IntConstant -100 + /// CHECK-DAG: <<Min:i\d+>> Min [<<Par>>,<<P100>>] + /// CHECK-DAG: <<Max:i\d+>> Max [<<Min>>,<<M100>>] + /// CHECK-DAG: Return [<<Max>>] + // + /// CHECK-START: int Main.minmax1(int) instruction_simplifier$after_inlining (after) + /// CHECK-NOT: Select + public static int minmax1(int x) { + // Simple if-if gives clean select sequence. + if (x > 100) { + x = 100; + } + if (x < -100) { + x = -100; + } + return x; + } + + /// CHECK-START: int Main.minmax2(int) instruction_simplifier$after_inlining (before) + /// CHECK-DAG: <<Par:i\d+>> ParameterValue + /// CHECK-DAG: <<P100:i\d+>> IntConstant 100 + /// CHECK-DAG: <<M100:i\d+>> IntConstant -100 + /// CHECK-DAG: <<Cnd1:z\d+>> LessThanOrEqual [<<Par>>,<<P100>>] + /// CHECK-DAG: <<Cnd2:z\d+>> GreaterThanOrEqual [<<Par>>,<<M100>>] + /// CHECK-DAG: <<Sel1:i\d+>> Select [<<M100>>,<<Par>>,<<Cnd2>>] + /// CHECK-DAG: <<Sel2:i\d+>> Select [<<P100>>,<<Sel1>>,<<Cnd1>>] + /// CHECK-DAG: Return [<<Sel2>>] + // + /// CHECK-START: int Main.minmax2(int) instruction_simplifier$after_inlining (after) + /// CHECK-DAG: <<Par:i\d+>> ParameterValue + /// CHECK-DAG: <<P100:i\d+>> IntConstant 100 + /// CHECK-DAG: <<M100:i\d+>> IntConstant -100 + /// CHECK-DAG: <<Max:i\d+>> Max [<<Par>>,<<M100>>] + /// CHECK-DAG: <<Min:i\d+>> Min [<<Max>>,<<P100>>] + /// CHECK-DAG: Return [<<Min>>] + // + /// CHECK-START: int Main.minmax2(int) instruction_simplifier$after_inlining (after) + /// CHECK-NOT: Select + public static int minmax2(int x) { + // Simple if-else requires inspecting bounds of resulting selects. + if (x > 100) { + x = 100; + } else if (x < -100) { + x = -100; + } + return x; + } + + /// CHECK-START: int Main.minmax3(int) instruction_simplifier$after_inlining (after) + /// CHECK-DAG: <<Par:i\d+>> ParameterValue + /// CHECK-DAG: <<P100:i\d+>> IntConstant 100 + /// CHECK-DAG: <<M100:i\d+>> IntConstant -100 + /// CHECK-DAG: <<Max:i\d+>> Max [<<Par>>,<<M100>>] + /// CHECK-DAG: <<Min:i\d+>> Min [<<Max>>,<<P100>>] + /// CHECK-DAG: Return [<<Min>>] + // + /// CHECK-START: int Main.minmax3(int) instruction_simplifier$after_inlining (after) + /// CHECK-NOT: Select + public static int minmax3(int x) { + return (x > 100) ? 100 : ((x < -100) ? -100 : x); + } + + /// CHECK-START: int Main.minmax4(int) instruction_simplifier$after_inlining (after) + /// CHECK-DAG: <<Par:i\d+>> ParameterValue + /// CHECK-DAG: <<P100:i\d+>> IntConstant 100 + /// CHECK-DAG: <<M100:i\d+>> IntConstant -100 + /// CHECK-DAG: <<Min:i\d+>> Min [<<Par>>,<<P100>>] + /// CHECK-DAG: <<Max:i\d+>> Max [<<Min>>,<<M100>>] + /// CHECK-DAG: Return [<<Max>>] + // + /// CHECK-START: int Main.minmax4(int) instruction_simplifier$after_inlining (after) + /// CHECK-NOT: Select + public static int minmax4(int x) { + return (x < -100) ? -100 : ((x > 100) ? 100 : x); + } + public static void main(String[] args) { + // Types. expectEquals(10, min1(10, 20)); expectEquals(10, min2(10, 20)); expectEquals(10, min3(10, 20)); @@ -244,6 +357,23 @@ public class Main { expectEquals(20, max5((short) 10, (short) 20)); expectEquals(20, max6((byte) 10, (byte) 20)); expectEquals(20L, max7(10L, 20L)); + // Complications. + int[] a = { 10 }; + int[] b = { 20 }; + expectEquals(10, min0(a, b)); + expectEquals(20, max0(a, b)); + expectEquals(-100, minmax1(-200)); + expectEquals(10, minmax1(10)); + expectEquals(100, minmax1(200)); + expectEquals(-100, minmax2(-200)); + expectEquals(10, minmax2(10)); + expectEquals(100, minmax2(200)); + expectEquals(-100, minmax3(-200)); + expectEquals(10, minmax3(10)); + expectEquals(100, minmax3(200)); + expectEquals(-100, minmax4(-200)); + expectEquals(10, minmax4(10)); + expectEquals(100, minmax4(200)); System.out.println("passed"); } |