diff options
author | 2018-04-18 17:27:43 +0000 | |
---|---|---|
committer | 2018-04-18 17:27:43 +0000 | |
commit | 740a50992ea1a200068eb4486a172a151c9b329c (patch) | |
tree | 398d9bbd027743a233034d4977821c0275a918e7 | |
parent | 63fe8dc454298852ae31cfc2692108488a58c650 (diff) | |
parent | 6d05700c620d2bca95fd046969753f71aa015ab4 (diff) |
Merge "Run GVN earlier."
-rw-r--r-- | compiler/optimizing/loop_optimization.cc | 5 | ||||
-rw-r--r-- | compiler/optimizing/optimizing_compiler.cc | 8 | ||||
-rw-r--r-- | compiler/optimizing/select_generator.cc | 30 | ||||
-rw-r--r-- | libartbase/base/arena_allocator.cc | 1 | ||||
-rw-r--r-- | libartbase/base/arena_allocator.h | 1 | ||||
-rw-r--r-- | test/458-checker-instruct-simplification/src/Main.java | 2 | ||||
-rw-r--r-- | test/551-checker-shifter-operand/src/Main.java | 49 | ||||
-rw-r--r-- | test/565-checker-doublenegbitwise/src/Main.java | 12 | ||||
-rw-r--r-- | test/651-checker-simd-minmax/src/ByteSimdMinMax.java | 35 | ||||
-rw-r--r-- | test/651-checker-simd-minmax/src/IntSimdMinMax.java | 38 | ||||
-rw-r--r-- | test/679-checker-minmax/src/Main.java | 130 | ||||
-rw-r--r-- | test/681-checker-abs/src/Main.java | 39 |
12 files changed, 297 insertions, 53 deletions
diff --git a/compiler/optimizing/loop_optimization.cc b/compiler/optimizing/loop_optimization.cc index c0c721de63..1462404932 100644 --- a/compiler/optimizing/loop_optimization.cc +++ b/compiler/optimizing/loop_optimization.cc @@ -1353,6 +1353,11 @@ bool HLoopOptimization::VectorizeDef(LoopNode* node, HInstruction* index = instruction->InputAt(1); HInstruction* value = instruction->InputAt(2); HInstruction* offset = nullptr; + // For narrow types, explicit type conversion may have been + // optimized way, so set the no hi bits restriction here. + if (DataType::Size(type) <= 2) { + restrictions |= kNoHiBits; + } if (TrySetVectorType(type, &restrictions) && node->loop_info->IsDefinedOutOfTheLoop(base) && induction_range_.IsUnitStride(instruction, index, graph_, &offset) && diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc index 79165826d1..cadefc3b01 100644 --- a/compiler/optimizing/optimizing_compiler.cc +++ b/compiler/optimizing/optimizing_compiler.cc @@ -643,15 +643,13 @@ void OptimizingCompiler::RunOptimizations(HGraph* graph, MaybeRunInliner(graph, codegen, dex_compilation_unit, pass_observer, handles); OptimizationDef optimizations2[] = { - // SelectGenerator depends on the InstructionSimplifier removing - // redundant suspend checks to recognize empty blocks. + OptDef(OptimizationPass::kSideEffectsAnalysis, "side_effects$before_gvn"), + OptDef(OptimizationPass::kGlobalValueNumbering), OptDef(OptimizationPass::kSelectGenerator), - // TODO: if we don't inline we can also skip fold2. OptDef(OptimizationPass::kConstantFolding, "constant_folding$after_inlining"), OptDef(OptimizationPass::kInstructionSimplifier, "instruction_simplifier$after_inlining"), OptDef(OptimizationPass::kDeadCodeElimination, "dead_code_elimination$after_inlining"), - OptDef(OptimizationPass::kSideEffectsAnalysis, "side_effects$before_gvn"), - OptDef(OptimizationPass::kGlobalValueNumbering), + OptDef(OptimizationPass::kSideEffectsAnalysis, "side_effects$before_licm"), OptDef(OptimizationPass::kInvariantCodeMotion), OptDef(OptimizationPass::kInductionVarAnalysis), OptDef(OptimizationPass::kBoundsCheckElimination), diff --git a/compiler/optimizing/select_generator.cc b/compiler/optimizing/select_generator.cc index 3f52bdd13c..f9acf5aa9a 100644 --- a/compiler/optimizing/select_generator.cc +++ b/compiler/optimizing/select_generator.cc @@ -16,6 +16,7 @@ #include "select_generator.h" +#include "base/scoped_arena_containers.h" #include "reference_type_propagation.h" namespace art { @@ -90,9 +91,13 @@ static HPhi* GetSingleChangedPhi(HBasicBlock* block, size_t index1, size_t index } void HSelectGenerator::Run() { + // Select cache with local allocator. + ScopedArenaAllocator allocator(graph_->GetArenaStack()); + ScopedArenaSafeMap<HInstruction*, HSelect*> cache( + std::less<HInstruction*>(), allocator.Adapter(kArenaAllocSelectGenerator)); + // Iterate in post order in the unlikely case that removing one occurrence of // the selection pattern empties a branch block of another occurrence. - // Otherwise the order does not matter. for (HBasicBlock* block : graph_->GetPostOrder()) { if (!block->EndsWithIf()) continue; @@ -143,7 +148,8 @@ void HSelectGenerator::Run() { DCHECK(both_successors_return || phi != nullptr); // Create the Select instruction and insert it in front of the If. - HSelect* select = new (graph_->GetAllocator()) HSelect(if_instruction->InputAt(0), + HInstruction* condition = if_instruction->InputAt(0); + HSelect* select = new (graph_->GetAllocator()) HSelect(condition, true_value, false_value, if_instruction->GetDexPc()); @@ -180,6 +186,26 @@ void HSelectGenerator::Run() { MaybeRecordStat(stats_, MethodCompilationStat::kSelectGenerated); + // Very simple way of finding common subexpressions in the generated HSelect statements + // (since this runs after GVN). Lookup by condition, and reuse latest one if possible + // (due to post order, latest select is most likely replacement). If needed, we could + // improve this by e.g. using the operands in the map as well. + auto it = cache.find(condition); + if (it == cache.end()) { + cache.Put(condition, select); + } else { + // Found cached value. See if latest can replace cached in the HIR. + HSelect* cached = it->second; + DCHECK_EQ(cached->GetCondition(), select->GetCondition()); + if (cached->GetTrueValue() == select->GetTrueValue() && + cached->GetFalseValue() == select->GetFalseValue() && + select->StrictlyDominates(cached)) { + cached->ReplaceWith(select); + cached->GetBlock()->RemoveInstruction(cached); + } + it->second = select; // always cache latest + } + // No need to update dominance information, as we are simplifying // a simple diamond shape, where the join block is merged with the // entry block. Any following blocks would have had the join block diff --git a/libartbase/base/arena_allocator.cc b/libartbase/base/arena_allocator.cc index 348a812e44..183e5c9f74 100644 --- a/libartbase/base/arena_allocator.cc +++ b/libartbase/base/arena_allocator.cc @@ -77,6 +77,7 @@ const char* const ArenaAllocatorStatsImpl<kCount>::kAllocNames[] = { "SsaLiveness ", "SsaPhiElim ", "RefTypeProp ", + "SelectGen ", "SideEffects ", "RegAllocator ", "RegAllocVldt ", diff --git a/libartbase/base/arena_allocator.h b/libartbase/base/arena_allocator.h index 3143fbac4c..4d535df1d4 100644 --- a/libartbase/base/arena_allocator.h +++ b/libartbase/base/arena_allocator.h @@ -87,6 +87,7 @@ enum ArenaAllocKind { kArenaAllocSsaLiveness, kArenaAllocSsaPhiElimination, kArenaAllocReferenceTypePropagation, + kArenaAllocSelectGenerator, kArenaAllocSideEffectsAnalysis, kArenaAllocRegisterAllocator, kArenaAllocRegisterAllocatorValidate, diff --git a/test/458-checker-instruct-simplification/src/Main.java b/test/458-checker-instruct-simplification/src/Main.java index 7797f31867..444b4557ce 100644 --- a/test/458-checker-instruct-simplification/src/Main.java +++ b/test/458-checker-instruct-simplification/src/Main.java @@ -2572,7 +2572,7 @@ public class Main { /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 /// CHECK-DAG: <<Const255:i\d+>> IntConstant 255 /// CHECK-DAG: <<Select:i\d+>> Select [<<Const0>>,<<Const1>>,<<Arg>>] - /// CHECK-DAG: <<And:i\d+>> And [<<Const255>>,<<Select>>] + /// CHECK-DAG: <<And:i\d+>> And [<<Select>>,<<Const255>>] /// CHECK-DAG: <<Conv:b\d+>> TypeConversion [<<And>>] /// CHECK-DAG: Return [<<Conv>>] diff --git a/test/551-checker-shifter-operand/src/Main.java b/test/551-checker-shifter-operand/src/Main.java index 3177ec0a3c..fb76904677 100644 --- a/test/551-checker-shifter-operand/src/Main.java +++ b/test/551-checker-shifter-operand/src/Main.java @@ -728,40 +728,9 @@ public class Main { /// CHECK: UShr /// CHECK-NOT: UShr // - // Note: simplification followed by GVN exposes the common subexpressions between shifts with larger distance - // `b << 62`, `b << 63` etc. and the equivalent smaller distances. - // - /// CHECK-START: void Main.$opt$validateShiftInt(int, int) GVN (after) - /// CHECK: Shl - /// CHECK: Shl - /// CHECK: Shl - /// CHECK: Shl - /// CHECK: Shl - /// CHECK: Shl - /// CHECK: Shl - /// CHECK: Shl - /// CHECK: Shl - /// CHECK-NOT: Shl - /// CHECK: Shr - /// CHECK: Shr - /// CHECK: Shr - /// CHECK: Shr - /// CHECK: Shr - /// CHECK: Shr - /// CHECK: Shr - /// CHECK: Shr - /// CHECK: Shr - /// CHECK-NOT: Shl - /// CHECK: UShr - /// CHECK: UShr - /// CHECK: UShr - /// CHECK: UShr - /// CHECK: UShr - /// CHECK: UShr - /// CHECK: UShr - /// CHECK: UShr - /// CHECK: UShr - /// CHECK-NOT: UShr + // Note: running extra simplification before GVN would expose the common subexpressions between + // shifts with larger distance `b << 62`, `b << 63` etc. and the equivalent smaller distances. + // TODO: b/78171933 // /// CHECK-START-ARM: void Main.$opt$validateShiftInt(int, int) instruction_simplifier_arm (after) /// CHECK: DataProcWithShifterOp @@ -791,6 +760,12 @@ public class Main { /// CHECK: DataProcWithShifterOp /// CHECK: DataProcWithShifterOp /// CHECK: DataProcWithShifterOp + /// CHECK: DataProcWithShifterOp + /// CHECK: DataProcWithShifterOp + /// CHECK: DataProcWithShifterOp + /// CHECK: DataProcWithShifterOp + /// CHECK: DataProcWithShifterOp + /// CHECK: DataProcWithShifterOp /// CHECK-NOT: DataProcWithShifterOp /// CHECK-START-ARM: void Main.$opt$validateShiftInt(int, int) instruction_simplifier_arm (after) @@ -826,6 +801,12 @@ public class Main { /// CHECK: DataProcWithShifterOp /// CHECK: DataProcWithShifterOp /// CHECK: DataProcWithShifterOp + /// CHECK: DataProcWithShifterOp + /// CHECK: DataProcWithShifterOp + /// CHECK: DataProcWithShifterOp + /// CHECK: DataProcWithShifterOp + /// CHECK: DataProcWithShifterOp + /// CHECK: DataProcWithShifterOp /// CHECK-NOT: DataProcWithShifterOp /// CHECK-START-ARM64: void Main.$opt$validateShiftInt(int, int) instruction_simplifier_arm64 (after) diff --git a/test/565-checker-doublenegbitwise/src/Main.java b/test/565-checker-doublenegbitwise/src/Main.java index 816cafc2ba..80358cd2ba 100644 --- a/test/565-checker-doublenegbitwise/src/Main.java +++ b/test/565-checker-doublenegbitwise/src/Main.java @@ -101,13 +101,13 @@ public class Main { /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 /// CHECK-DAG: <<Select1:i\d+>> Select [<<Const1>>,<<Const0>>,<<P1>>] /// CHECK-DAG: <<Select2:i\d+>> Select [<<Const1>>,<<Const0>>,<<P2>>] - /// CHECK-DAG: <<And:i\d+>> And [<<Select2>>,<<Select1>>] + /// CHECK-DAG: <<And:i\d+>> And [<<Select1>>,<<Select2>>] /// CHECK-DAG: Return [<<And>>] /// CHECK-START: boolean Main.$opt$noinline$booleanAndToOr(boolean, boolean) instruction_simplifier$after_inlining (after) /// CHECK-DAG: <<Cond1:z\d+>> ParameterValue /// CHECK-DAG: <<Cond2:z\d+>> ParameterValue - /// CHECK-DAG: <<Or:i\d+>> Or [<<Cond2>>,<<Cond1>>] + /// CHECK-DAG: <<Or:i\d+>> Or [<<Cond1>>,<<Cond2>>] /// CHECK-DAG: <<BooleanNot:z\d+>> BooleanNot [<<Or>>] /// CHECK-DAG: Return [<<BooleanNot>>] @@ -172,13 +172,13 @@ public class Main { /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 /// CHECK-DAG: <<Select1:i\d+>> Select [<<Const1>>,<<Const0>>,<<P1>>] /// CHECK-DAG: <<Select2:i\d+>> Select [<<Const1>>,<<Const0>>,<<P2>>] - /// CHECK-DAG: <<Or:i\d+>> Or [<<Select2>>,<<Select1>>] + /// CHECK-DAG: <<Or:i\d+>> Or [<<Select1>>,<<Select2>>] /// CHECK-DAG: Return [<<Or>>] /// CHECK-START: boolean Main.$opt$noinline$booleanOrToAnd(boolean, boolean) instruction_simplifier$after_inlining (after) /// CHECK-DAG: <<Cond1:z\d+>> ParameterValue /// CHECK-DAG: <<Cond2:z\d+>> ParameterValue - /// CHECK-DAG: <<And:i\d+>> And [<<Cond2>>,<<Cond1>>] + /// CHECK-DAG: <<And:i\d+>> And [<<Cond1>>,<<Cond2>>] /// CHECK-DAG: <<BooleanNot:z\d+>> BooleanNot [<<And>>] /// CHECK-DAG: Return [<<BooleanNot>>] @@ -282,13 +282,13 @@ public class Main { /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 /// CHECK-DAG: <<Select1:i\d+>> Select [<<Const1>>,<<Const0>>,<<P1>>] /// CHECK-DAG: <<Select2:i\d+>> Select [<<Const1>>,<<Const0>>,<<P2>>] - /// CHECK-DAG: <<Xor:i\d+>> Xor [<<Select2>>,<<Select1>>] + /// CHECK-DAG: <<Xor:i\d+>> Xor [<<Select1>>,<<Select2>>] /// CHECK-DAG: Return [<<Xor>>] /// CHECK-START: boolean Main.$opt$noinline$booleanNotXorToXor(boolean, boolean) instruction_simplifier$after_inlining (after) /// CHECK-DAG: <<Cond1:z\d+>> ParameterValue /// CHECK-DAG: <<Cond2:z\d+>> ParameterValue - /// CHECK-DAG: <<Xor:i\d+>> Xor [<<Cond2>>,<<Cond1>>] + /// CHECK-DAG: <<Xor:i\d+>> Xor [<<Cond1>>,<<Cond2>>] /// CHECK-DAG: Return [<<Xor>>] /// CHECK-START: boolean Main.$opt$noinline$booleanNotXorToXor(boolean, boolean) instruction_simplifier$after_bce (after) diff --git a/test/651-checker-simd-minmax/src/ByteSimdMinMax.java b/test/651-checker-simd-minmax/src/ByteSimdMinMax.java index 8dacd5d51e..fff15faeaa 100644 --- a/test/651-checker-simd-minmax/src/ByteSimdMinMax.java +++ b/test/651-checker-simd-minmax/src/ByteSimdMinMax.java @@ -174,6 +174,30 @@ public class ByteSimdMinMax { } } + /// CHECK-START-{ARM,ARM64}: void ByteSimdMinMax.doitMinAlt(byte[], byte[], byte[]) loop_optimization (after) + /// CHECK-DAG: <<Get1:d\d+>> VecLoad loop:<<Loop:B\d+>> outer_loop:none + /// CHECK-DAG: <<Get2:d\d+>> VecLoad loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<Min:d\d+>> VecMin [<<Get1>>,<<Get2>>] packed_type:Int8 loop:<<Loop>> outer_loop:none + /// CHECK-DAG: VecStore [{{l\d+}},{{i\d+}},<<Min>>] loop:<<Loop>> outer_loop:none + private static void doitMinAlt(byte[] x, byte[] y, byte[] z) { + int n = Math.min(x.length, Math.min(y.length, z.length)); + for (int i = 0; i < n; ++i) { + x[i] = y[i] < z[i] ? y[i] : z[i]; + } + } + + /// CHECK-START-{ARM,ARM64,MIPS64}: void ByteSimdMinMax.doitMaxAlt(byte[], byte[], byte[]) loop_optimization (after) + /// CHECK-DAG: <<Get1:d\d+>> VecLoad loop:<<Loop:B\d+>> outer_loop:none + /// CHECK-DAG: <<Get2:d\d+>> VecLoad loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<Max:d\d+>> VecMax [<<Get1>>,<<Get2>>] packed_type:Int8 loop:<<Loop>> outer_loop:none + /// CHECK-DAG: VecStore [{{l\d+}},{{i\d+}},<<Max>>] loop:<<Loop>> outer_loop:none + private static void doitMaxAlt(byte[] x, byte[] y, byte[] z) { + int n = Math.min(x.length, Math.min(y.length, z.length)); + for (int i = 0; i < n; ++i) { + x[i] = y[i] > z[i] ? y[i] : z[i]; + } + } + public static void main() { // Initialize cross-values for all possible values. int total = 256 * 256; @@ -228,7 +252,16 @@ public class ByteSimdMinMax { byte expected = (byte) (u < 11 ? 11 : (u > 23 ? 23 : u)); expectEquals(expected, x[i]); } - + doitMinAlt(x, y, z); + for (int i = 0; i < total; i++) { + byte expected = (byte) Math.min(y[i], z[i]); + expectEquals(expected, x[i]); + } + doitMaxAlt(x, y, z); + for (int i = 0; i < total; i++) { + byte expected = (byte) Math.max(y[i], z[i]); + expectEquals(expected, x[i]); + } System.out.println("ByteSimdMinMax passed"); } diff --git a/test/651-checker-simd-minmax/src/IntSimdMinMax.java b/test/651-checker-simd-minmax/src/IntSimdMinMax.java index 6373ae10eb..ad88843175 100644 --- a/test/651-checker-simd-minmax/src/IntSimdMinMax.java +++ b/test/651-checker-simd-minmax/src/IntSimdMinMax.java @@ -57,6 +57,38 @@ public class IntSimdMinMax { } } + /// CHECK-START-{ARM,ARM64}: int IntSimdMinMax.findMin(int[]) loop_optimization (after) + /// CHECK-DAG: <<Rep:d\d+>> VecReplicateScalar loop:none + /// CHECK-DAG: <<VPhi:d\d+>> Phi [<<Rep>>,<<Max:d\d+>>] loop:<<Loop:B\d+>> outer_loop:none + /// CHECK-DAG: <<Get:d\d+>> VecLoad [{{l\d+}},{{i\d+}}] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<Max>> VecMin [<<Get>>,<<VPhi>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<Red:d\d+>> VecReduce [<<VPhi>>] loop:none + /// CHECK-DAG: VecExtractScalar [<<Red>>] loop:none + private static int findMin(int[] a) { + int x = Integer.MAX_VALUE; + for (int i = 0; i < a.length; i++) { + if (a[i] < x) + x = a[i]; + } + return x; + } + + /// CHECK-START-{ARM,ARM64}: int IntSimdMinMax.findMax(int[]) loop_optimization (after) + /// CHECK-DAG: <<Rep:d\d+>> VecReplicateScalar loop:none + /// CHECK-DAG: <<VPhi:d\d+>> Phi [<<Rep>>,<<Max:d\d+>>] loop:<<Loop:B\d+>> outer_loop:none + /// CHECK-DAG: <<Get:d\d+>> VecLoad [{{l\d+}},{{i\d+}}] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<Max>> VecMax [<<Get>>,<<VPhi>>] loop:<<Loop>> outer_loop:none + /// CHECK-DAG: <<Red:d\d+>> VecReduce [<<VPhi>>] loop:none + /// CHECK-DAG: VecExtractScalar [<<Red>>] loop:none + private static int findMax(int[] a) { + int x = Integer.MIN_VALUE; + for (int i = 0; i < a.length; i++) { + if (a[i] > x) + x = a[i]; + } + return x; + } + public static void main() { int[] interesting = { 0x00000000, 0x00000001, 0x00007fff, 0x00008000, 0x00008001, 0x0000ffff, @@ -92,6 +124,12 @@ public class IntSimdMinMax { int expected = Math.max(y[i], z[i]); expectEquals(expected, x[i]); } + expectEquals(Integer.MIN_VALUE, findMin(x)); + expectEquals(Integer.MAX_VALUE, findMax(x)); + expectEquals(Integer.MIN_VALUE, findMin(y)); + expectEquals(Integer.MAX_VALUE, findMax(y)); + expectEquals(Integer.MIN_VALUE, findMin(z)); + expectEquals(Integer.MAX_VALUE, findMax(z)); System.out.println("IntSimdMinMax passed"); } diff --git a/test/679-checker-minmax/src/Main.java b/test/679-checker-minmax/src/Main.java index e330a5370e..48de1da291 100644 --- a/test/679-checker-minmax/src/Main.java +++ b/test/679-checker-minmax/src/Main.java @@ -309,19 +309,42 @@ public class Main { return a >= b ? a : b; } - // // Complications. // - // TODO: coming soon, under discussion + /// CHECK-START: int Main.min0(int[], int[]) instruction_simplifier$after_inlining (before) + /// CHECK-DAG: <<Ar1:i\d+>> ArrayGet [{{l\d+}},{{i\d+}}] + /// CHECK-DAG: <<Ar2:i\d+>> ArrayGet [{{l\d+}},{{i\d+}}] + /// CHECK-DAG: <<Cnd:z\d+>> GreaterThan [<<Ar1>>,<<Ar2>>] + /// CHECK-DAG: <<Sel:i\d+>> Select [<<Ar1>>,<<Ar2>>,<<Cnd>>] + /// CHECK-DAG: Return [<<Sel>>] + // + /// CHECK-START: int Main.min0(int[], int[]) instruction_simplifier$after_inlining (after) + /// CHECK-DAG: <<Min:i\d+>> Min + /// CHECK-DAG: Return [<<Min>>] + // + /// CHECK-START: int Main.min0(int[], int[]) instruction_simplifier$after_inlining (after) + /// CHECK-NOT: Select 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 + /// CHECK-START: int Main.max0(int[], int[]) instruction_simplifier$after_inlining (before) + /// CHECK-DAG: <<Ar1:i\d+>> ArrayGet [{{l\d+}},{{i\d+}}] + /// CHECK-DAG: <<Ar2:i\d+>> ArrayGet [{{l\d+}},{{i\d+}}] + /// CHECK-DAG: <<Cnd:z\d+>> LessThan [<<Ar1>>,<<Ar2>>] + /// CHECK-DAG: <<Sel:i\d+>> Select [<<Ar1>>,<<Ar2>>,<<Cnd>>] + /// CHECK-DAG: Return [<<Sel>>] + // + /// CHECK-START: int Main.max0(int[], int[]) instruction_simplifier$after_inlining (after) + /// CHECK-DAG: <<Max:i\d+>> Max + /// CHECK-DAG: Return [<<Max>>] + // + /// CHECK-START: int Main.max0(int[], int[]) instruction_simplifier$after_inlining (after) + /// CHECK-NOT: Select 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. @@ -417,8 +440,102 @@ public class Main { return (x < -100) ? -100 : ((x > 100) ? 100 : x); } + /// CHECK-START: int Main.minmaxCSEScalar(int, int) select_generator (after) + /// CHECK-DAG: <<Par1:i\d+>> ParameterValue + /// CHECK-DAG: <<Par2:i\d+>> ParameterValue + /// CHECK-DAG: <<Cnd1:z\d+>> LessThanOrEqual [<<Par1>>,<<Par2>>] + /// CHECK-DAG: <<Sel1:i\d+>> Select [<<Par1>>,<<Par2>>,<<Cnd1>>] + /// CHECK-DAG: <<Cnd2:z\d+>> GreaterThanOrEqual [<<Par1>>,<<Par2>>] + /// CHECK-DAG: <<Sel2:i\d+>> Select [<<Par1>>,<<Par2>>,<<Cnd2>>] + /// CHECK-DAG: <<Add1:i\d+>> Add [<<Sel1>>,<<Sel2>>] + /// CHECK-DAG: <<Add2:i\d+>> Add [<<Sel1>>,<<Add1>>] + /// CHECK-DAG: <<Add3:i\d+>> Add [<<Sel2>>,<<Add2>>] + /// CHECK-DAG: <<Add4:i\d+>> Add [<<Sel1>>,<<Add3>>] + /// CHECK-DAG: <<Add5:i\d+>> Add [<<Sel2>>,<<Add4>>] + /// CHECK-DAG: Return [<<Add5>>] + // + /// CHECK-START: int Main.minmaxCSEScalar(int, int) instruction_simplifier$after_inlining (after) + /// CHECK-DAG: <<Par1:i\d+>> ParameterValue + /// CHECK-DAG: <<Par2:i\d+>> ParameterValue + /// CHECK-DAG: <<Max:i\d+>> Max [<<Par1>>,<<Par2>>] + /// CHECK-DAG: <<Min:i\d+>> Min [<<Par1>>,<<Par2>>] + /// CHECK-DAG: <<Add1:i\d+>> Add [<<Max>>,<<Min>>] + /// CHECK-DAG: <<Add2:i\d+>> Add [<<Max>>,<<Add1>>] + /// CHECK-DAG: <<Add3:i\d+>> Add [<<Min>>,<<Add2>>] + /// CHECK-DAG: <<Add4:i\d+>> Add [<<Max>>,<<Add3>>] + /// CHECK-DAG: <<Add5:i\d+>> Add [<<Min>>,<<Add4>>] + /// CHECK-DAG: Return [<<Add5>>] + public static int minmaxCSEScalar(int x, int y) { + int t1 = (x > y) ? x : y; + int t2 = (x < y) ? x : y; + int t3 = (x > y) ? x : y; + int t4 = (x < y) ? x : y; + int t5 = (x > y) ? x : y; + int t6 = (x < y) ? x : y; + // Make sure min/max is CSEed. + return t1 + t2 + t3 + t4 + t5 + t6; + } + + /// CHECK-START: int Main.minmaxCSEArray(int[], int[]) select_generator (after) + /// CHECK-DAG: <<Arr1:i\d+>> ArrayGet + /// CHECK-DAG: <<Arr2:i\d+>> ArrayGet + /// CHECK-DAG: <<Cnd1:z\d+>> LessThanOrEqual [<<Arr1>>,<<Arr2>>] + /// CHECK-DAG: <<Sel1:i\d+>> Select [<<Arr1>>,<<Arr2>>,<<Cnd1>>] + /// CHECK-DAG: <<Cnd2:z\d+>> GreaterThanOrEqual [<<Arr1>>,<<Arr2>>] + /// CHECK-DAG: <<Sel2:i\d+>> Select [<<Arr1>>,<<Arr2>>,<<Cnd2>>] + /// CHECK-DAG: <<Add1:i\d+>> Add [<<Sel1>>,<<Sel2>>] + /// CHECK-DAG: <<Add2:i\d+>> Add [<<Sel1>>,<<Add1>>] + /// CHECK-DAG: <<Add3:i\d+>> Add [<<Sel2>>,<<Add2>>] + /// CHECK-DAG: <<Add4:i\d+>> Add [<<Sel1>>,<<Add3>>] + /// CHECK-DAG: <<Add5:i\d+>> Add [<<Sel2>>,<<Add4>>] + /// CHECK-DAG: Return [<<Add5>>] + // + /// CHECK-START: int Main.minmaxCSEArray(int[], int[]) instruction_simplifier$after_inlining (after) + /// CHECK-DAG: <<Arr1:i\d+>> ArrayGet + /// CHECK-DAG: <<Arr2:i\d+>> ArrayGet + /// CHECK-DAG: <<Max:i\d+>> Max [<<Arr1>>,<<Arr2>>] + /// CHECK-DAG: <<Min:i\d+>> Min [<<Arr1>>,<<Arr2>>] + /// CHECK-DAG: <<Add1:i\d+>> Add [<<Max>>,<<Min>>] + /// CHECK-DAG: <<Add2:i\d+>> Add [<<Max>>,<<Add1>>] + /// CHECK-DAG: <<Add3:i\d+>> Add [<<Min>>,<<Add2>>] + /// CHECK-DAG: <<Add4:i\d+>> Add [<<Max>>,<<Add3>>] + /// CHECK-DAG: <<Add5:i\d+>> Add [<<Min>>,<<Add4>>] + /// CHECK-DAG: Return [<<Add5>>] + public static int minmaxCSEArray(int[] x, int[] y) { + int t1 = (x[0] > y[0]) ? x[0] : y[0]; + int t2 = (x[0] < y[0]) ? x[0] : y[0]; + int t3 = (x[0] > y[0]) ? x[0] : y[0]; + int t4 = (x[0] < y[0]) ? x[0] : y[0]; + int t5 = (x[0] > y[0]) ? x[0] : y[0]; + int t6 = (x[0] < y[0]) ? x[0] : y[0]; + // Make sure min/max is CSEed. + return t1 + t2 + t3 + t4 + t5 + t6; + } + + /// CHECK-START: int Main.minmaxCSEScalarAndCond(int, int) instruction_simplifier$after_inlining (after) + /// CHECK-DAG: <<Par1:i\d+>> ParameterValue + /// CHECK-DAG: <<Par2:i\d+>> ParameterValue + /// CHECK-DAG: <<Max:i\d+>> Max [<<Par1>>,<<Par2>>] + /// CHECK-DAG: <<Min:i\d+>> Min [<<Par1>>,<<Par2>>] + /// CHECK-DAG: <<Add:i\d+>> Add [<<Max>>,<<Min>>] + /// CHECK-DAG: Return [<<Add>>] + /// CHECK-DAG: <<Add1:i\d+>> Add [<<Max>>,<<Min>>] + /// CHECK-DAG: <<Add2:i\d+>> Add [<<Max>>,<<Add1>>] + /// CHECK-DAG: <<Add3:i\d+>> Add [<<Min>>,<<Add2>>] + /// CHECK-DAG: Return [<<Add3>>] + public static int minmaxCSEScalarAndCond(int x, int y) { + int t1 = (x > y) ? x : y; + int t2 = (x < y) ? x : y; + if (x == y) + return t1 + t2; + int t3 = (x > y) ? x : y; + int t4 = (x < y) ? x : y; + // Make sure min/max is CSEed. + return t1 + t2 + t3 + t4; + } + public static void main(String[] args) { - // Types. + // Intrinsics. expectEquals(10, minI(10)); expectEquals(20, minI(25)); expectEquals(10L, minL(10L)); @@ -427,6 +544,7 @@ public class Main { expectEquals(25, maxI(25)); expectEquals(20L, maxL(10L)); expectEquals(25L, maxL(25L)); + // Types. expectEquals(10, min1(10, 20)); expectEquals(10, min2(10, 20)); expectEquals(10, min3(10, 20)); @@ -458,6 +576,10 @@ public class Main { expectEquals(-100, minmax4(-200)); expectEquals(10, minmax4(10)); expectEquals(100, minmax4(200)); + expectEquals(90, minmaxCSEScalar(10, 20)); + expectEquals(90, minmaxCSEArray(a, b)); + expectEquals(20, minmaxCSEScalarAndCond(10, 10)); + expectEquals(60, minmaxCSEScalarAndCond(10, 20)); System.out.println("passed"); } diff --git a/test/681-checker-abs/src/Main.java b/test/681-checker-abs/src/Main.java index d1ba7c6851..2b95a8d56e 100644 --- a/test/681-checker-abs/src/Main.java +++ b/test/681-checker-abs/src/Main.java @@ -19,6 +19,10 @@ */ public class Main { + // + // Intrinsics. + // + /// CHECK-START: int Main.absI(int) instruction_simplifier (before) /// CHECK-DAG: <<Par:i\d+>> ParameterValue /// CHECK-DAG: <<Abs:i\d+>> InvokeStaticOrDirect [<<Par>>] intrinsic:MathAbsInt @@ -51,6 +55,10 @@ public class Main { return Math.abs(a); } + // + // Types. + // + /// CHECK-START: int Main.abs1(int) instruction_simplifier$after_inlining (before) /// CHECK-DAG: <<Par:i\d+>> ParameterValue /// CHECK-DAG: <<Zer:i\d+>> IntConstant 0 @@ -185,6 +193,29 @@ public class Main { } // + // Complications. + // + + /// CHECK-START: int Main.abs0(int[]) instruction_simplifier$after_inlining (before) + /// CHECK-DAG: <<Zer:i\d+>> IntConstant 0 + /// CHECK-DAG: <<Arr:i\d+>> ArrayGet [{{l\d+}},{{i\d+}}] + /// CHECK-DAG: <<Cnd:z\d+>> LessThan [<<Arr>>,<<Zer>>] + /// CHECK-DAG: <<Neg:i\d+>> [<<Arr>>] + /// CHECK-DAG: <<Sel:i\d+>> Select [<<Arr>>,<<Neg>>,<<Cnd>>] + /// CHECK-DAG: Return [<<Sel>>] + // + /// CHECK-START: int Main.abs0(int[]) instruction_simplifier$after_inlining (after) + /// CHECK-DAG: <<Arr:i\d+>> ArrayGet [{{l\d+}},{{i\d+}}] + /// CHECK-DAG: <<Abs:i\d+>> Abs [<<Arr>>] + /// CHECK-DAG: Return [<<Abs>>] + // + /// CHECK-START: int Main.abs0(int[]) instruction_simplifier$after_inlining (after) + /// CHECK-NOT: Select + public static int abs0(int[] a) { + return a[0] >= 0 ? a[0] : -a[0]; + } + + // // Nop zero extension. // @@ -248,10 +279,12 @@ public class Main { } public static void main(String[] args) { + // Intrinsics. expectEquals(10, absI(-10)); expectEquals(20, absI(20)); expectEquals(10L, absL(-10L)); expectEquals(20L, absL(20L)); + // Types. expectEquals(10, abs1(-10)); expectEquals(20, abs1(20)); expectEquals(10, abs2(-10)); @@ -266,6 +299,12 @@ public class Main { expectEquals(20, abs6((byte) 20)); expectEquals(10L, abs7(-10L)); expectEquals(20L, abs7(20L)); + // Complications. + int[] a = { 13 }; + int[] b = { -11 }; + expectEquals(13, abs0(a)); + expectEquals(11, abs0(b)); + // Nop zero extension. expectEquals(1, zabs1((byte) 1)); expectEquals(0xff, zabs1((byte) -1)); expectEquals(1, zabs2((short) 1)); |