1 /*
2 * Copyright (C) 2015 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16 
17 public class Main {
18 
19   // Note #1: `javac` flips the conditions of If statements.
20   // Note #2: In the optimizing compiler, the first input of Phi is always
21   //          the fall-through path, i.e. the false branch.
22 
assertBoolEquals(boolean expected, boolean result)23   public static void assertBoolEquals(boolean expected, boolean result) {
24     if (expected != result) {
25       throw new Error("Expected: " + expected + ", found: " + result);
26     }
27   }
28 
assertIntEquals(int expected, int result)29   public static void assertIntEquals(int expected, int result) {
30     if (expected != result) {
31       throw new Error("Expected: " + expected + ", found: " + result);
32     }
33   }
34 
35   /*
36    * Elementary test negating a boolean. Verifies that blocks are merged and
37    * empty branches removed.
38    */
39 
40   // CHECK-START: boolean Main.BooleanNot(boolean) boolean_simplifier (before)
41   // CHECK-DAG:     [[Param:z\d+]]    ParameterValue
42   // CHECK-DAG:     [[Const0:i\d+]]   IntConstant 0
43   // CHECK-DAG:     [[Const1:i\d+]]   IntConstant 1
44   // CHECK-DAG:                       If [ [[Param]] ]
45   // CHECK-DAG:     [[Phi:i\d+]]      Phi [ [[Const1]] [[Const0]] ]
46   // CHECK-DAG:                       Return [ [[Phi]] ]
47 
48   // CHECK-START: boolean Main.BooleanNot(boolean) boolean_simplifier (before)
49   // CHECK:                           Goto
50   // CHECK:                           Goto
51   // CHECK:                           Goto
52   // CHECK-NOT:                       Goto
53 
54   // CHECK-START: boolean Main.BooleanNot(boolean) boolean_simplifier (after)
55   // CHECK-DAG:     [[Param:z\d+]]    ParameterValue
56   // CHECK-DAG:     [[Const0:i\d+]]   IntConstant 0
57   // CHECK-DAG:     [[NotParam:z\d+]] BooleanNot [ [[Param]] ]
58   // CHECK-DAG:                       Return [ [[NotParam]] ]
59 
60   // CHECK-START: boolean Main.BooleanNot(boolean) boolean_simplifier (after)
61   // CHECK-NOT:                       If
62   // CHECK-NOT:                       Phi
63 
64   // CHECK-START: boolean Main.BooleanNot(boolean) boolean_simplifier (after)
65   // CHECK:                           Goto
66   // CHECK-NOT:                       Goto
67 
BooleanNot(boolean x)68   public static boolean BooleanNot(boolean x) {
69     return !x;
70   }
71 
72   /*
73    * Program which only delegates the condition, i.e. returns 1 when True
74    * and 0 when False.
75    */
76 
77   // CHECK-START: boolean Main.GreaterThan(int, int) boolean_simplifier (before)
78   // CHECK-DAG:     [[ParamX:i\d+]]   ParameterValue
79   // CHECK-DAG:     [[ParamY:i\d+]]   ParameterValue
80   // CHECK-DAG:     [[Const0:i\d+]]   IntConstant 0
81   // CHECK-DAG:     [[Const1:i\d+]]   IntConstant 1
82   // CHECK-DAG:     [[Cond:z\d+]]     GreaterThan [ [[ParamX]] [[ParamY]] ]
83   // CHECK-DAG:                       If [ [[Cond]] ]
84   // CHECK-DAG:     [[Phi:i\d+]]      Phi [ [[Const0]] [[Const1]] ]
85   // CHECK-DAG:                       Return [ [[Phi]] ]
86 
87   // CHECK-START: boolean Main.GreaterThan(int, int) boolean_simplifier (after)
88   // CHECK-DAG:     [[ParamX:i\d+]]   ParameterValue
89   // CHECK-DAG:     [[ParamY:i\d+]]   ParameterValue
90   // CHECK-DAG:     [[Const0:i\d+]]   IntConstant 0
91   // CHECK-DAG:     [[Const1:i\d+]]   IntConstant 1
92   // CHECK-DAG:     [[Cond:z\d+]]     GreaterThan [ [[ParamX]] [[ParamY]] ]
93   // CHECK-DAG:                       Return [ [[Cond]] ]
94 
GreaterThan(int x, int y)95   public static boolean GreaterThan(int x, int y) {
96     return (x <= y) ? false : true;
97   }
98 
99   /*
100    * Program which negates a condition, i.e. returns 0 when True
101    * and 1 when False.
102    */
103 
104   // CHECK-START: boolean Main.LessThan(int, int) boolean_simplifier (before)
105   // CHECK-DAG:     [[ParamX:i\d+]]   ParameterValue
106   // CHECK-DAG:     [[ParamY:i\d+]]   ParameterValue
107   // CHECK-DAG:     [[Const0:i\d+]]   IntConstant 0
108   // CHECK-DAG:     [[Const1:i\d+]]   IntConstant 1
109   // CHECK-DAG:     [[Cond:z\d+]]     GreaterThanOrEqual [ [[ParamX]] [[ParamY]] ]
110   // CHECK-DAG:                       If [ [[Cond]] ]
111   // CHECK-DAG:     [[Phi:i\d+]]      Phi [ [[Const1]] [[Const0]] ]
112   // CHECK-DAG:                       Return [ [[Phi]] ]
113 
114   // CHECK-START: boolean Main.LessThan(int, int) boolean_simplifier (after)
115   // CHECK-DAG:     [[ParamX:i\d+]]   ParameterValue
116   // CHECK-DAG:     [[ParamY:i\d+]]   ParameterValue
117   // CHECK-DAG:     [[Const0:i\d+]]   IntConstant 0
118   // CHECK-DAG:     [[Const1:i\d+]]   IntConstant 1
119   // CHECK-DAG:     [[Cond:z\d+]]     LessThan [ [[ParamX]] [[ParamY]] ]
120   // CHECK-DAG:                       Return [ [[Cond]] ]
121 
LessThan(int x, int y)122   public static boolean LessThan(int x, int y) {
123     return (x < y) ? true : false;
124   }
125 
126   /*
127    * Program which further uses negated conditions.
128    * Note that Phis are discovered retrospectively.
129    */
130 
131   // CHECK-START: boolean Main.ValuesOrdered(int, int, int) boolean_simplifier (before)
132   // CHECK-DAG:     [[ParamX:i\d+]]   ParameterValue
133   // CHECK-DAG:     [[ParamY:i\d+]]   ParameterValue
134   // CHECK-DAG:     [[ParamZ:i\d+]]   ParameterValue
135   // CHECK-DAG:     [[Const0:i\d+]]   IntConstant 0
136   // CHECK-DAG:     [[Const1:i\d+]]   IntConstant 1
137   // CHECK-DAG:     [[CondXY:z\d+]]   GreaterThan [ [[ParamX]] [[ParamY]] ]
138   // CHECK-DAG:                       If [ [[CondXY]] ]
139   // CHECK-DAG:     [[CondYZ:z\d+]]   GreaterThan [ [[ParamY]] [[ParamZ]] ]
140   // CHECK-DAG:                       If [ [[CondYZ]] ]
141   // CHECK-DAG:     [[CondXYZ:z\d+]]  NotEqual [ [[PhiXY:i\d+]] [[PhiYZ:i\d+]] ]
142   // CHECK-DAG:                       If [ [[CondXYZ]] ]
143   // CHECK-DAG:                       Return [ [[PhiXYZ:i\d+]] ]
144   // CHECK-DAG:     [[PhiXY]]         Phi [ [[Const1]] [[Const0]] ]
145   // CHECK-DAG:     [[PhiYZ]]         Phi [ [[Const1]] [[Const0]] ]
146   // CHECK-DAG:     [[PhiXYZ]]        Phi [ [[Const1]] [[Const0]] ]
147 
148   // CHECK-START: boolean Main.ValuesOrdered(int, int, int) boolean_simplifier (after)
149   // CHECK-DAG:     [[ParamX:i\d+]]   ParameterValue
150   // CHECK-DAG:     [[ParamY:i\d+]]   ParameterValue
151   // CHECK-DAG:     [[ParamZ:i\d+]]   ParameterValue
152   // CHECK-DAG:     [[CmpXY:z\d+]]    LessThanOrEqual [ [[ParamX]] [[ParamY]] ]
153   // CHECK-DAG:     [[CmpYZ:z\d+]]    LessThanOrEqual [ [[ParamY]] [[ParamZ]] ]
154   // CHECK-DAG:     [[CmpXYZ:z\d+]]   Equal [ [[CmpXY]] [[CmpYZ]] ]
155   // CHECK-DAG:                       Return [ [[CmpXYZ]] ]
156 
ValuesOrdered(int x, int y, int z)157   public static boolean ValuesOrdered(int x, int y, int z) {
158     return (x <= y) == (y <= z);
159   }
160 
161   // CHECK-START: int Main.NegatedCondition(boolean) boolean_simplifier (before)
162   // CHECK-DAG:     [[Param:z\d+]]    ParameterValue
163   // CHECK-DAG:     [[Const42:i\d+]]  IntConstant 42
164   // CHECK-DAG:     [[Const43:i\d+]]  IntConstant 43
165   // CHECK-DAG:     [[NotParam:z\d+]] BooleanNot [ [[Param]] ]
166   // CHECK-DAG:                       If [ [[NotParam]] ]
167   // CHECK-DAG:     [[Phi:i\d+]]      Phi [ [[Const42]] [[Const43]] ]
168   // CHECK-DAG:                       Return [ [[Phi]] ]
169 
170   // CHECK-START: int Main.NegatedCondition(boolean) boolean_simplifier (after)
171   // CHECK-DAG:     [[Param:z\d+]]    ParameterValue
172   // CHECK-DAG:     [[Const42:i\d+]]  IntConstant 42
173   // CHECK-DAG:     [[Const43:i\d+]]  IntConstant 43
174   // CHECK-DAG:                       If [ [[Param]] ]
175   // CHECK-DAG:     [[Phi:i\d+]]      Phi [ [[Const42]] [[Const43]] ]
176   // CHECK-DAG:                       Return [ [[Phi]] ]
177 
178   // Note: The fact that branches are swapped is verified by running the test.
179 
180   // CHECK-START: int Main.NegatedCondition(boolean) boolean_simplifier (after)
181   // CHECK-NOT:                       BooleanNot
182 
NegatedCondition(boolean x)183   public static int NegatedCondition(boolean x) {
184     if (x != false) {
185       return 42;
186     } else {
187       return 43;
188     }
189   }
190 
main(String[] args)191   public static void main(String[] args) {
192     assertBoolEquals(false, BooleanNot(true));
193     assertBoolEquals(true, BooleanNot(false));
194     assertBoolEquals(true, GreaterThan(10, 5));
195     assertBoolEquals(false, GreaterThan(10, 10));
196     assertBoolEquals(false, GreaterThan(5, 10));
197     assertBoolEquals(true, LessThan(5, 10));
198     assertBoolEquals(false, LessThan(10, 10));
199     assertBoolEquals(false, LessThan(10, 5));
200     assertBoolEquals(true, ValuesOrdered(1, 3, 5));
201     assertBoolEquals(true, ValuesOrdered(5, 3, 1));
202     assertBoolEquals(false, ValuesOrdered(1, 3, 2));
203     assertBoolEquals(false, ValuesOrdered(2, 3, 1));
204     assertBoolEquals(true, ValuesOrdered(3, 3, 3));
205     assertBoolEquals(true, ValuesOrdered(3, 3, 5));
206     assertBoolEquals(false, ValuesOrdered(5, 5, 3));
207     assertIntEquals(42, NegatedCondition(true));
208     assertIntEquals(43, NegatedCondition(false));
209   }
210 }
211