ART: Implement HSelect
This patch adds a new HIR instruction to Optimizing. HSelect returns
one of two inputs based on the outcome of a condition.
This is only initial implementation which:
- defines the new instruction,
- repurposes BooleanSimplifier to emit it,
- extends InstructionSimplifier to statically resolve it,
- updates existing code and tests accordingly.
Code generators currently emit fallback if/then/else code and will be
updated in follow-up CLs to use platform-specific conditional moves
when possible.
Change-Id: Ib61b17146487ebe6b55350c2b589f0b971dcaaee
diff --git a/test/463-checker-boolean-simplifier/src/Main.java b/test/463-checker-boolean-simplifier/src/Main.java
index 61510d8..682f126 100644
--- a/test/463-checker-boolean-simplifier/src/Main.java
+++ b/test/463-checker-boolean-simplifier/src/Main.java
@@ -37,7 +37,7 @@
* empty branches removed.
*/
- /// CHECK-START: boolean Main.BooleanNot(boolean) boolean_simplifier (before)
+ /// CHECK-START: boolean Main.BooleanNot(boolean) select_generator (before)
/// CHECK-DAG: <<Param:z\d+>> ParameterValue
/// CHECK-DAG: <<Const0:i\d+>> IntConstant 0
/// CHECK-DAG: <<Const1:i\d+>> IntConstant 1
@@ -45,23 +45,24 @@
/// CHECK-DAG: <<Phi:i\d+>> Phi [<<Const1>>,<<Const0>>]
/// CHECK-DAG: Return [<<Phi>>]
- /// CHECK-START: boolean Main.BooleanNot(boolean) boolean_simplifier (before)
+ /// CHECK-START: boolean Main.BooleanNot(boolean) select_generator (before)
/// CHECK: Goto
/// CHECK: Goto
/// CHECK: Goto
/// CHECK-NOT: Goto
- /// CHECK-START: boolean Main.BooleanNot(boolean) boolean_simplifier (after)
+ /// CHECK-START: boolean Main.BooleanNot(boolean) select_generator (after)
/// CHECK-DAG: <<Param:z\d+>> ParameterValue
/// CHECK-DAG: <<Const0:i\d+>> IntConstant 0
- /// CHECK-DAG: <<NotParam:z\d+>> BooleanNot [<<Param>>]
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1
+ /// CHECK-DAG: <<NotParam:i\d+>> Select [<<Const1>>,<<Const0>>,<<Param>>]
/// CHECK-DAG: Return [<<NotParam>>]
- /// CHECK-START: boolean Main.BooleanNot(boolean) boolean_simplifier (after)
+ /// CHECK-START: boolean Main.BooleanNot(boolean) select_generator (after)
/// CHECK-NOT: If
/// CHECK-NOT: Phi
- /// CHECK-START: boolean Main.BooleanNot(boolean) boolean_simplifier (after)
+ /// CHECK-START: boolean Main.BooleanNot(boolean) select_generator (after)
/// CHECK: Goto
/// CHECK-NOT: Goto
@@ -74,7 +75,7 @@
* and 0 when False.
*/
- /// CHECK-START: boolean Main.GreaterThan(int, int) boolean_simplifier (before)
+ /// CHECK-START: boolean Main.GreaterThan(int, int) select_generator (before)
/// CHECK-DAG: <<ParamX:i\d+>> ParameterValue
/// CHECK-DAG: <<ParamY:i\d+>> ParameterValue
/// CHECK-DAG: <<Const0:i\d+>> IntConstant 0
@@ -84,13 +85,14 @@
/// CHECK-DAG: <<Phi:i\d+>> Phi [<<Const0>>,<<Const1>>]
/// CHECK-DAG: Return [<<Phi>>]
- /// CHECK-START: boolean Main.GreaterThan(int, int) boolean_simplifier (after)
+ /// CHECK-START: boolean Main.GreaterThan(int, int) select_generator (after)
/// CHECK-DAG: <<ParamX:i\d+>> ParameterValue
/// CHECK-DAG: <<ParamY:i\d+>> ParameterValue
/// CHECK-DAG: <<Const0:i\d+>> IntConstant 0
/// CHECK-DAG: <<Const1:i\d+>> IntConstant 1
/// CHECK-DAG: <<Cond:z\d+>> GreaterThan [<<ParamX>>,<<ParamY>>]
- /// CHECK-DAG: Return [<<Cond>>]
+ /// CHECK-DAG: <<Select:i\d+>> Select [<<Const0>>,<<Const1>>,<<Cond>>]
+ /// CHECK-DAG: Return [<<Select>>]
public static boolean GreaterThan(int x, int y) {
return (x <= y) ? false : true;
@@ -101,7 +103,7 @@
* and 1 when False.
*/
- /// CHECK-START: boolean Main.LessThan(int, int) boolean_simplifier (before)
+ /// CHECK-START: boolean Main.LessThan(int, int) select_generator (before)
/// CHECK-DAG: <<ParamX:i\d+>> ParameterValue
/// CHECK-DAG: <<ParamY:i\d+>> ParameterValue
/// CHECK-DAG: <<Const0:i\d+>> IntConstant 0
@@ -111,13 +113,14 @@
/// CHECK-DAG: <<Phi:i\d+>> Phi [<<Const1>>,<<Const0>>]
/// CHECK-DAG: Return [<<Phi>>]
- /// CHECK-START: boolean Main.LessThan(int, int) boolean_simplifier (after)
+ /// CHECK-START: boolean Main.LessThan(int, int) select_generator (after)
/// CHECK-DAG: <<ParamX:i\d+>> ParameterValue
/// CHECK-DAG: <<ParamY:i\d+>> ParameterValue
/// CHECK-DAG: <<Const0:i\d+>> IntConstant 0
/// CHECK-DAG: <<Const1:i\d+>> IntConstant 1
- /// CHECK-DAG: <<Cond:z\d+>> LessThan [<<ParamX>>,<<ParamY>>]
- /// CHECK-DAG: Return [<<Cond>>]
+ /// CHECK-DAG: <<Cond:z\d+>> GreaterThanOrEqual [<<ParamX>>,<<ParamY>>]
+ /// CHECK-DAG: <<Select:i\d+>> Select [<<Const1>>,<<Const0>>,<<Cond>>]
+ /// CHECK-DAG: Return [<<Select>>]
public static boolean LessThan(int x, int y) {
return (x < y) ? true : false;
@@ -128,7 +131,7 @@
* Note that Phis are discovered retrospectively.
*/
- /// CHECK-START: boolean Main.ValuesOrdered(int, int, int) boolean_simplifier (before)
+ /// CHECK-START: boolean Main.ValuesOrdered(int, int, int) select_generator (before)
/// CHECK-DAG: <<ParamX:i\d+>> ParameterValue
/// CHECK-DAG: <<ParamY:i\d+>> ParameterValue
/// CHECK-DAG: <<ParamZ:i\d+>> ParameterValue
@@ -145,29 +148,25 @@
/// CHECK-DAG: <<PhiYZ>> Phi [<<Const1>>,<<Const0>>]
/// CHECK-DAG: <<PhiXYZ>> Phi [<<Const1>>,<<Const0>>]
- /// CHECK-START: boolean Main.ValuesOrdered(int, int, int) boolean_simplifier (after)
+ /// CHECK-START: boolean Main.ValuesOrdered(int, int, int) select_generator (after)
/// CHECK-DAG: <<ParamX:i\d+>> ParameterValue
/// CHECK-DAG: <<ParamY:i\d+>> ParameterValue
/// CHECK-DAG: <<ParamZ:i\d+>> ParameterValue
- /// CHECK-DAG: <<CmpXY:z\d+>> LessThanOrEqual [<<ParamX>>,<<ParamY>>]
- /// CHECK-DAG: <<CmpYZ:z\d+>> LessThanOrEqual [<<ParamY>>,<<ParamZ>>]
- /// CHECK-DAG: <<CmpXYZ:z\d+>> Equal [<<CmpXY>>,<<CmpYZ>>]
- /// CHECK-DAG: Return [<<CmpXYZ>>]
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1
+ /// CHECK-DAG: <<CmpXY:z\d+>> GreaterThan [<<ParamX>>,<<ParamY>>]
+ /// CHECK-DAG: <<SelXY:i\d+>> Select [<<Const1>>,<<Const0>>,<<CmpXY>>]
+ /// CHECK-DAG: <<CmpYZ:z\d+>> GreaterThan [<<ParamY>>,<<ParamZ>>]
+ /// CHECK-DAG: <<SelYZ:i\d+>> Select [<<Const1>>,<<Const0>>,<<CmpYZ>>]
+ /// CHECK-DAG: <<CmpXYZ:z\d+>> NotEqual [<<SelXY>>,<<SelYZ>>]
+ /// CHECK-DAG: <<SelXYZ:i\d+>> Select [<<Const1>>,<<Const0>>,<<CmpXYZ>>]
+ /// CHECK-DAG: Return [<<SelXYZ>>]
public static boolean ValuesOrdered(int x, int y, int z) {
return (x <= y) == (y <= z);
}
- /// CHECK-START: int Main.NegatedCondition(boolean) boolean_simplifier (before)
- /// CHECK-DAG: <<Param:z\d+>> ParameterValue
- /// CHECK-DAG: <<Const42:i\d+>> IntConstant 42
- /// CHECK-DAG: <<Const43:i\d+>> IntConstant 43
- /// CHECK-DAG: <<NotParam:z\d+>> BooleanNot [<<Param>>]
- /// CHECK-DAG: If [<<NotParam>>]
- /// CHECK-DAG: <<Phi:i\d+>> Phi [<<Const42>>,<<Const43>>]
- /// CHECK-DAG: Return [<<Phi>>]
-
- /// CHECK-START: int Main.NegatedCondition(boolean) boolean_simplifier (after)
+ /// CHECK-START: int Main.NegatedCondition(boolean) select_generator (before)
/// CHECK-DAG: <<Param:z\d+>> ParameterValue
/// CHECK-DAG: <<Const42:i\d+>> IntConstant 42
/// CHECK-DAG: <<Const43:i\d+>> IntConstant 43
@@ -175,9 +174,14 @@
/// CHECK-DAG: <<Phi:i\d+>> Phi [<<Const42>>,<<Const43>>]
/// CHECK-DAG: Return [<<Phi>>]
- // Note: The fact that branches are swapped is verified by running the test.
+ /// CHECK-START: int Main.NegatedCondition(boolean) select_generator (after)
+ /// CHECK-DAG: <<Param:z\d+>> ParameterValue
+ /// CHECK-DAG: <<Const42:i\d+>> IntConstant 42
+ /// CHECK-DAG: <<Const43:i\d+>> IntConstant 43
+ /// CHECK-DAG: <<Select:i\d+>> Select [<<Const43>>,<<Const42>>,<<Param>>]
+ /// CHECK-DAG: Return [<<Select>>]
- /// CHECK-START: int Main.NegatedCondition(boolean) boolean_simplifier (after)
+ /// CHECK-START: int Main.NegatedCondition(boolean) select_generator (after)
/// CHECK-NOT: BooleanNot
public static int NegatedCondition(boolean x) {
@@ -188,6 +192,179 @@
}
}
+ /// CHECK-START: int Main.SimpleTrueBlock(boolean, int) select_generator (after)
+ /// CHECK-DAG: <<ParamX:z\d+>> ParameterValue
+ /// CHECK-DAG: <<ParamY:i\d+>> ParameterValue
+ /// CHECK-DAG: <<Const42:i\d+>> IntConstant 42
+ /// CHECK-DAG: <<Const43:i\d+>> IntConstant 43
+ /// CHECK-DAG: <<Add:i\d+>> Add [<<ParamY>>,<<Const42>>]
+ /// CHECK-DAG: <<Select:i\d+>> Select [<<Const43>>,<<Add>>,<<ParamX>>]
+ /// CHECK-DAG: Return [<<Select>>]
+
+ /// CHECK-START: int Main.SimpleTrueBlock(boolean, int) select_generator (after)
+ /// CHECK-NOT: If
+
+ public static int SimpleTrueBlock(boolean x, int y) {
+ return x ? y + 42 : 43;
+ }
+
+ /// CHECK-START: int Main.SimpleFalseBlock(boolean, int) select_generator (after)
+ /// CHECK-DAG: <<ParamX:z\d+>> ParameterValue
+ /// CHECK-DAG: <<ParamY:i\d+>> ParameterValue
+ /// CHECK-DAG: <<Const42:i\d+>> IntConstant 42
+ /// CHECK-DAG: <<Const43:i\d+>> IntConstant 43
+ /// CHECK-DAG: <<Add:i\d+>> Add [<<ParamY>>,<<Const43>>]
+ /// CHECK-DAG: <<Select:i\d+>> Select [<<Add>>,<<Const42>>,<<ParamX>>]
+ /// CHECK-DAG: Return [<<Select>>]
+
+ /// CHECK-START: int Main.SimpleFalseBlock(boolean, int) select_generator (after)
+ /// CHECK-NOT: If
+
+ public static int SimpleFalseBlock(boolean x, int y) {
+ return x ? 42 : y + 43;
+ }
+
+ /// CHECK-START: int Main.SimpleBothBlocks(boolean, int, int) select_generator (after)
+ /// CHECK-DAG: <<ParamX:z\d+>> ParameterValue
+ /// CHECK-DAG: <<ParamY:i\d+>> ParameterValue
+ /// CHECK-DAG: <<ParamZ:i\d+>> ParameterValue
+ /// CHECK-DAG: <<Const42:i\d+>> IntConstant 42
+ /// CHECK-DAG: <<Const43:i\d+>> IntConstant 43
+ /// CHECK-DAG: <<AddTrue:i\d+>> Add [<<ParamY>>,<<Const42>>]
+ /// CHECK-DAG: <<AddFalse:i\d+>> Add [<<ParamZ>>,<<Const43>>]
+ /// CHECK-DAG: <<Select:i\d+>> Select [<<AddFalse>>,<<AddTrue>>,<<ParamX>>]
+ /// CHECK-DAG: Return [<<Select>>]
+
+ /// CHECK-START: int Main.SimpleBothBlocks(boolean, int, int) select_generator (after)
+ /// CHECK-NOT: If
+
+ public static int SimpleBothBlocks(boolean x, int y, int z) {
+ return x ? y + 42 : z + 43;
+ }
+
+ /// CHECK-START: int Main.ThreeBlocks(boolean, boolean) select_generator (after)
+ /// CHECK-DAG: <<ParamX:z\d+>> ParameterValue
+ /// CHECK-DAG: <<ParamY:z\d+>> ParameterValue
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1
+ /// CHECK-DAG: <<Const2:i\d+>> IntConstant 2
+ /// CHECK-DAG: <<Const3:i\d+>> IntConstant 3
+ /// CHECK-DAG: <<Select23:i\d+>> Select [<<Const3>>,<<Const2>>,<<ParamY>>]
+ /// CHECK-DAG: <<Select123:i\d+>> Select [<<Select23>>,<<Const1>>,<<ParamX>>]
+ /// CHECK-DAG: Return [<<Select123>>]
+
+ public static int ThreeBlocks(boolean x, boolean y) {
+ if (x) {
+ return 1;
+ } else if (y) {
+ return 2;
+ } else {
+ return 3;
+ }
+ }
+
+ /// CHECK-START: int Main.MultiplePhis() select_generator (before)
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1
+ /// CHECK-DAG: <<Const13:i\d+>> IntConstant 13
+ /// CHECK-DAG: <<Const42:i\d+>> IntConstant 42
+ /// CHECK-DAG: <<PhiX:i\d+>> Phi [<<Const0>>,<<Const13>>,<<Const42>>]
+ /// CHECK-DAG: <<PhiY:i\d+>> Phi [<<Const1>>,<<Add:i\d+>>,<<Add>>]
+ /// CHECK-DAG: <<Add>> Add [<<PhiY>>,<<Const1>>]
+ /// CHECK-DAG: <<Cond:z\d+>> LessThanOrEqual [<<Add>>,<<Const1>>]
+ /// CHECK-DAG: If [<<Cond>>]
+ /// CHECK-DAG: Return [<<PhiX>>]
+
+ /// CHECK-START: int Main.MultiplePhis() select_generator (after)
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1
+ /// CHECK-DAG: <<Const13:i\d+>> IntConstant 13
+ /// CHECK-DAG: <<Const42:i\d+>> IntConstant 42
+ /// CHECK-DAG: <<PhiX:i\d+>> Phi [<<Const0>>,<<Select:i\d+>>]
+ /// CHECK-DAG: <<PhiY:i\d+>> Phi [<<Const1>>,<<Add:i\d+>>]
+ /// CHECK-DAG: <<Add>> Add [<<PhiY>>,<<Const1>>]
+ /// CHECK-DAG: <<Cond:z\d+>> LessThanOrEqual [<<Add>>,<<Const1>>]
+ /// CHECK-DAG: <<Select>> Select [<<Const13>>,<<Const42>>,<<Cond>>]
+ /// CHECK-DAG: Return [<<PhiX>>]
+
+ public static int MultiplePhis() {
+ int x = 0;
+ int y = 1;
+ while (y++ < 10) {
+ if (y > 1) {
+ x = 13;
+ } else {
+ x = 42;
+ }
+ }
+ return x;
+ }
+
+ /// CHECK-START: int Main.TrueBlockWithTooManyInstructions(boolean) select_generator (before)
+ /// CHECK-DAG: <<This:l\d+>> ParameterValue
+ /// CHECK-DAG: <<Cond:z\d+>> ParameterValue
+ /// CHECK-DAG: <<Const2:i\d+>> IntConstant 2
+ /// CHECK-DAG: <<Const43:i\d+>> IntConstant 43
+ /// CHECK-DAG: If [<<Cond>>]
+ /// CHECK-DAG: <<Iget:i\d+>> InstanceFieldGet [<<This>>]
+ /// CHECK-DAG: <<Add:i\d+>> Add [<<Iget>>,<<Const2>>]
+ /// CHECK-DAG: Phi [<<Add>>,<<Const43>>]
+
+ /// CHECK-START: int Main.TrueBlockWithTooManyInstructions(boolean) select_generator (after)
+ /// CHECK-NOT: Select
+
+ public int TrueBlockWithTooManyInstructions(boolean x) {
+ return x ? (read_field + 2) : 43;
+ }
+
+ /// CHECK-START: int Main.FalseBlockWithTooManyInstructions(boolean) select_generator (before)
+ /// CHECK-DAG: <<This:l\d+>> ParameterValue
+ /// CHECK-DAG: <<Cond:z\d+>> ParameterValue
+ /// CHECK-DAG: <<Const3:i\d+>> IntConstant 3
+ /// CHECK-DAG: <<Const42:i\d+>> IntConstant 42
+ /// CHECK-DAG: If [<<Cond>>]
+ /// CHECK-DAG: <<Iget:i\d+>> InstanceFieldGet [<<This>>]
+ /// CHECK-DAG: <<Add:i\d+>> Add [<<Iget>>,<<Const3>>]
+ /// CHECK-DAG: Phi [<<Const42>>,<<Add>>]
+
+ /// CHECK-START: int Main.FalseBlockWithTooManyInstructions(boolean) select_generator (after)
+ /// CHECK-NOT: Select
+
+ public int FalseBlockWithTooManyInstructions(boolean x) {
+ return x ? 42 : (read_field + 3);
+ }
+
+ /// CHECK-START: int Main.TrueBlockWithSideEffects(boolean) select_generator (before)
+ /// CHECK-DAG: <<This:l\d+>> ParameterValue
+ /// CHECK-DAG: <<Cond:z\d+>> ParameterValue
+ /// CHECK-DAG: <<Const42:i\d+>> IntConstant 42
+ /// CHECK-DAG: <<Const43:i\d+>> IntConstant 43
+ /// CHECK-DAG: If [<<Cond>>]
+ /// CHECK-DAG: InstanceFieldSet [<<This>>,<<Const42>>]
+ /// CHECK-DAG: Phi [<<Const42>>,<<Const43>>]
+
+ /// CHECK-START: int Main.TrueBlockWithSideEffects(boolean) select_generator (after)
+ /// CHECK-NOT: Select
+
+ public int TrueBlockWithSideEffects(boolean x) {
+ return x ? (write_field = 42) : 43;
+ }
+
+ /// CHECK-START: int Main.FalseBlockWithSideEffects(boolean) select_generator (before)
+ /// CHECK-DAG: <<This:l\d+>> ParameterValue
+ /// CHECK-DAG: <<Cond:z\d+>> ParameterValue
+ /// CHECK-DAG: <<Const42:i\d+>> IntConstant 42
+ /// CHECK-DAG: <<Const43:i\d+>> IntConstant 43
+ /// CHECK-DAG: If [<<Cond>>]
+ /// CHECK-DAG: InstanceFieldSet [<<This>>,<<Const43>>]
+ /// CHECK-DAG: Phi [<<Const42>>,<<Const43>>]
+
+ /// CHECK-START: int Main.FalseBlockWithSideEffects(boolean) select_generator (after)
+ /// CHECK-NOT: Select
+
+ public int FalseBlockWithSideEffects(boolean x) {
+ return x ? 42 : (write_field = 43);
+ }
+
public static void main(String[] args) {
assertBoolEquals(false, BooleanNot(true));
assertBoolEquals(true, BooleanNot(false));
@@ -206,5 +383,30 @@
assertBoolEquals(false, ValuesOrdered(5, 5, 3));
assertIntEquals(42, NegatedCondition(true));
assertIntEquals(43, NegatedCondition(false));
+ assertIntEquals(46, SimpleTrueBlock(true, 4));
+ assertIntEquals(43, SimpleTrueBlock(false, 4));
+ assertIntEquals(42, SimpleFalseBlock(true, 7));
+ assertIntEquals(50, SimpleFalseBlock(false, 7));
+ assertIntEquals(48, SimpleBothBlocks(true, 6, 2));
+ assertIntEquals(45, SimpleBothBlocks(false, 6, 2));
+ assertIntEquals(1, ThreeBlocks(true, true));
+ assertIntEquals(1, ThreeBlocks(true, false));
+ assertIntEquals(2, ThreeBlocks(false, true));
+ assertIntEquals(3, ThreeBlocks(false, false));
+ assertIntEquals(13, MultiplePhis());
+
+ Main m = new Main();
+ assertIntEquals(42, m.TrueBlockWithTooManyInstructions(true));
+ assertIntEquals(43, m.TrueBlockWithTooManyInstructions(false));
+ assertIntEquals(42, m.FalseBlockWithTooManyInstructions(true));
+ assertIntEquals(43, m.FalseBlockWithTooManyInstructions(false));
+ assertIntEquals(42, m.TrueBlockWithSideEffects(true));
+ assertIntEquals(43, m.TrueBlockWithSideEffects(false));
+ assertIntEquals(42, m.FalseBlockWithSideEffects(true));
+ assertIntEquals(43, m.FalseBlockWithSideEffects(false));
}
+
+ // These need to be instance fields so as to not generate a LoadClass for iget/iput.
+ public int read_field = 40;
+ public int write_field = 42;
}