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 // Invoke a method written in smali that implements the boolean ! operator. This method 36 // uses the if/else pattern generated by dx (while Jack generates a different pattern). 37 // Since this method is in a smali-generated class, we invoke it through reflection. SmaliBooleanNot(boolean x)38 public static boolean SmaliBooleanNot(boolean x) throws Exception { 39 Class<?> c = Class.forName("BooleanNotSmali"); 40 java.lang.reflect.Method method = c.getMethod("BooleanNot", boolean.class); 41 Object retValue = method.invoke(null, new Object[] { Boolean.valueOf(x) }); 42 return ((Boolean) retValue).booleanValue(); 43 } 44 45 /* 46 * Program which only delegates the condition, i.e. returns 1 when True 47 * and 0 when False. 48 */ 49 50 /// CHECK-START: boolean Main.GreaterThan(int, int) select_generator (before) 51 /// CHECK-DAG: <<ParamX:i\d+>> ParameterValue 52 /// CHECK-DAG: <<ParamY:i\d+>> ParameterValue 53 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 54 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 55 /// CHECK-DAG: <<Cond:z\d+>> GreaterThan [<<ParamX>>,<<ParamY>>] 56 /// CHECK-DAG: If [<<Cond>>] 57 /// CHECK-DAG: <<Phi:i\d+>> Phi [<<Const0>>,<<Const1>>] 58 /// CHECK-DAG: Return [<<Phi>>] 59 60 /// CHECK-START: boolean Main.GreaterThan(int, int) select_generator (after) 61 /// CHECK-DAG: <<ParamX:i\d+>> ParameterValue 62 /// CHECK-DAG: <<ParamY:i\d+>> ParameterValue 63 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 64 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 65 /// CHECK-DAG: <<Cond:z\d+>> GreaterThan [<<ParamX>>,<<ParamY>>] 66 /// CHECK-DAG: <<Select:i\d+>> Select [<<Const0>>,<<Const1>>,<<Cond>>] 67 /// CHECK-DAG: Return [<<Select>>] 68 GreaterThan(int x, int y)69 public static boolean GreaterThan(int x, int y) { 70 return (x <= y) ? false : true; 71 } 72 73 /* 74 * Program which negates a condition, i.e. returns 0 when True 75 * and 1 when False. 76 */ 77 78 /// CHECK-START: boolean Main.LessThan(int, int) select_generator (before) 79 /// CHECK-DAG: <<ParamX:i\d+>> ParameterValue 80 /// CHECK-DAG: <<ParamY:i\d+>> ParameterValue 81 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 82 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 83 /// CHECK-DAG: <<Cond:z\d+>> GreaterThanOrEqual [<<ParamX>>,<<ParamY>>] 84 /// CHECK-DAG: If [<<Cond>>] 85 /// CHECK-DAG: <<Phi:i\d+>> Phi [<<Const1>>,<<Const0>>] 86 /// CHECK-DAG: Return [<<Phi>>] 87 88 /// CHECK-START: boolean Main.LessThan(int, int) select_generator (after) 89 /// CHECK-DAG: <<ParamX:i\d+>> ParameterValue 90 /// CHECK-DAG: <<ParamY:i\d+>> ParameterValue 91 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 92 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 93 /// CHECK-DAG: <<Cond:z\d+>> GreaterThanOrEqual [<<ParamX>>,<<ParamY>>] 94 /// CHECK-DAG: <<Select:i\d+>> Select [<<Const1>>,<<Const0>>,<<Cond>>] 95 /// CHECK-DAG: Return [<<Select>>] 96 LessThan(int x, int y)97 public static boolean LessThan(int x, int y) { 98 return (x < y) ? true : false; 99 } 100 101 /* 102 * Program which further uses negated conditions. 103 * Note that Phis are discovered retrospectively. 104 */ 105 106 /// CHECK-START: boolean Main.ValuesOrdered(int, int, int) select_generator (before) 107 /// CHECK-DAG: <<ParamX:i\d+>> ParameterValue 108 /// CHECK-DAG: <<ParamY:i\d+>> ParameterValue 109 /// CHECK-DAG: <<ParamZ:i\d+>> ParameterValue 110 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 111 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 112 /// CHECK-DAG: <<CondXY:z\d+>> GreaterThan [<<ParamX>>,<<ParamY>>] 113 /// CHECK-DAG: If [<<CondXY>>] 114 /// CHECK-DAG: <<CondYZ:z\d+>> GreaterThan [<<ParamY>>,<<ParamZ>>] 115 /// CHECK-DAG: If [<<CondYZ>>] 116 /// CHECK-DAG: <<CondXYZ:z\d+>> NotEqual [<<PhiXY:i\d+>>,<<PhiYZ:i\d+>>] 117 /// CHECK-DAG: If [<<CondXYZ>>] 118 /// CHECK-DAG: Return [<<PhiXYZ:i\d+>>] 119 /// CHECK-DAG: <<PhiXY>> Phi [<<Const1>>,<<Const0>>] 120 /// CHECK-DAG: <<PhiYZ>> Phi [<<Const1>>,<<Const0>>] 121 /// CHECK-DAG: <<PhiXYZ>> Phi [<<Const1>>,<<Const0>>] 122 123 /// CHECK-START: boolean Main.ValuesOrdered(int, int, int) select_generator (after) 124 /// CHECK-DAG: <<ParamX:i\d+>> ParameterValue 125 /// CHECK-DAG: <<ParamY:i\d+>> ParameterValue 126 /// CHECK-DAG: <<ParamZ:i\d+>> ParameterValue 127 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 128 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 129 /// CHECK-DAG: <<CmpXY:z\d+>> GreaterThan [<<ParamX>>,<<ParamY>>] 130 /// CHECK-DAG: <<SelXY:i\d+>> Select [<<Const1>>,<<Const0>>,<<CmpXY>>] 131 /// CHECK-DAG: <<CmpYZ:z\d+>> GreaterThan [<<ParamY>>,<<ParamZ>>] 132 /// CHECK-DAG: <<SelYZ:i\d+>> Select [<<Const1>>,<<Const0>>,<<CmpYZ>>] 133 /// CHECK-DAG: <<CmpXYZ:z\d+>> NotEqual [<<SelXY>>,<<SelYZ>>] 134 /// CHECK-DAG: <<SelXYZ:i\d+>> Select [<<Const1>>,<<Const0>>,<<CmpXYZ>>] 135 /// CHECK-DAG: Return [<<SelXYZ>>] 136 ValuesOrdered(int x, int y, int z)137 public static boolean ValuesOrdered(int x, int y, int z) { 138 return (x <= y) == (y <= z); 139 } 140 141 /// CHECK-START: int Main.NegatedCondition(boolean) select_generator (before) 142 /// CHECK-DAG: <<Param:z\d+>> ParameterValue 143 /// CHECK-DAG: <<Const42:i\d+>> IntConstant 42 144 /// CHECK-DAG: <<Const43:i\d+>> IntConstant 43 145 /// CHECK-DAG: If [<<Param>>] 146 /// CHECK-DAG: <<Phi:i\d+>> Phi [<<Const42>>,<<Const43>>] 147 /// CHECK-DAG: Return [<<Phi>>] 148 149 /// CHECK-START: int Main.NegatedCondition(boolean) select_generator (after) 150 /// CHECK-DAG: <<Param:z\d+>> ParameterValue 151 /// CHECK-DAG: <<Const42:i\d+>> IntConstant 42 152 /// CHECK-DAG: <<Const43:i\d+>> IntConstant 43 153 /// CHECK-DAG: <<Select:i\d+>> Select [<<Const43>>,<<Const42>>,<<Param>>] 154 /// CHECK-DAG: Return [<<Select>>] 155 156 /// CHECK-START: int Main.NegatedCondition(boolean) select_generator (after) 157 /// CHECK-NOT: BooleanNot 158 NegatedCondition(boolean x)159 public static int NegatedCondition(boolean x) { 160 return (x != false) ? 42 : 43; 161 } 162 163 /// CHECK-START: int Main.SimpleTrueBlock(boolean, int) select_generator (after) 164 /// CHECK-DAG: <<ParamX:z\d+>> ParameterValue 165 /// CHECK-DAG: <<ParamY:i\d+>> ParameterValue 166 /// CHECK-DAG: <<Const42:i\d+>> IntConstant 42 167 /// CHECK-DAG: <<Const43:i\d+>> IntConstant 43 168 /// CHECK-DAG: <<Add:i\d+>> Add [<<ParamY>>,<<Const42>>] 169 /// CHECK-DAG: <<Select:i\d+>> Select [<<Const43>>,<<Add>>,<<ParamX>>] 170 /// CHECK-DAG: Return [<<Select>>] 171 172 /// CHECK-START: int Main.SimpleTrueBlock(boolean, int) select_generator (after) 173 /// CHECK-NOT: If 174 SimpleTrueBlock(boolean x, int y)175 public static int SimpleTrueBlock(boolean x, int y) { 176 return x ? y + 42 : 43; 177 } 178 179 /// CHECK-START: int Main.SimpleFalseBlock(boolean, int) select_generator (after) 180 /// CHECK-DAG: <<ParamX:z\d+>> ParameterValue 181 /// CHECK-DAG: <<ParamY:i\d+>> ParameterValue 182 /// CHECK-DAG: <<Const42:i\d+>> IntConstant 42 183 /// CHECK-DAG: <<Const43:i\d+>> IntConstant 43 184 /// CHECK-DAG: <<Add:i\d+>> Add [<<ParamY>>,<<Const43>>] 185 /// CHECK-DAG: <<Select:i\d+>> Select [<<Add>>,<<Const42>>,<<ParamX>>] 186 /// CHECK-DAG: Return [<<Select>>] 187 188 /// CHECK-START: int Main.SimpleFalseBlock(boolean, int) select_generator (after) 189 /// CHECK-NOT: If 190 SimpleFalseBlock(boolean x, int y)191 public static int SimpleFalseBlock(boolean x, int y) { 192 return x ? 42 : y + 43; 193 } 194 195 /// CHECK-START: int Main.SimpleBothBlocks(boolean, int, int) select_generator (after) 196 /// CHECK-DAG: <<ParamX:z\d+>> ParameterValue 197 /// CHECK-DAG: <<ParamY:i\d+>> ParameterValue 198 /// CHECK-DAG: <<ParamZ:i\d+>> ParameterValue 199 /// CHECK-DAG: <<Const42:i\d+>> IntConstant 42 200 /// CHECK-DAG: <<Const43:i\d+>> IntConstant 43 201 /// CHECK-DAG: <<AddTrue:i\d+>> Add [<<ParamY>>,<<Const42>>] 202 /// CHECK-DAG: <<AddFalse:i\d+>> Add [<<ParamZ>>,<<Const43>>] 203 /// CHECK-DAG: <<Select:i\d+>> Select [<<AddFalse>>,<<AddTrue>>,<<ParamX>>] 204 /// CHECK-DAG: Return [<<Select>>] 205 206 /// CHECK-START: int Main.SimpleBothBlocks(boolean, int, int) select_generator (after) 207 /// CHECK-NOT: If 208 SimpleBothBlocks(boolean x, int y, int z)209 public static int SimpleBothBlocks(boolean x, int y, int z) { 210 return x ? y + 42 : z + 43; 211 } 212 213 /// CHECK-START: int Main.ThreeBlocks(boolean, boolean) select_generator (after) 214 /// CHECK-DAG: <<ParamX:z\d+>> ParameterValue 215 /// CHECK-DAG: <<ParamY:z\d+>> ParameterValue 216 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 217 /// CHECK-DAG: <<Const2:i\d+>> IntConstant 2 218 /// CHECK-DAG: <<Const3:i\d+>> IntConstant 3 219 /// CHECK-DAG: <<Select23:i\d+>> Select [<<Const3>>,<<Const2>>,<<ParamY>>] 220 /// CHECK-DAG: <<Select123:i\d+>> Select [<<Select23>>,<<Const1>>,<<ParamX>>] 221 /// CHECK-DAG: Return [<<Select123>>] 222 ThreeBlocks(boolean x, boolean y)223 public static int ThreeBlocks(boolean x, boolean y) { 224 return x ? 1 : (y ? 2 : 3); 225 } 226 227 /// CHECK-START: int Main.MultiplePhis() select_generator (before) 228 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 229 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 230 /// CHECK-DAG: <<Const13:i\d+>> IntConstant 13 231 /// CHECK-DAG: <<Const42:i\d+>> IntConstant 42 232 /// CHECK-DAG: <<PhiX:i\d+>> Phi [<<Const0>>,<<Const13>>,<<Const42>>] 233 /// CHECK-DAG: <<PhiY:i\d+>> Phi [<<Const1>>,<<Add:i\d+>>,<<Add>>] 234 /// CHECK-DAG: <<Add>> Add [<<PhiY>>,<<Const1>>] 235 /// CHECK-DAG: <<Cond:z\d+>> LessThanOrEqual [<<Add>>,<<Const1>>] 236 /// CHECK-DAG: If [<<Cond>>] 237 /// CHECK-DAG: Return [<<PhiX>>] 238 239 /// CHECK-START: int Main.MultiplePhis() select_generator (after) 240 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 241 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 242 /// CHECK-DAG: <<Const13:i\d+>> IntConstant 13 243 /// CHECK-DAG: <<Const42:i\d+>> IntConstant 42 244 /// CHECK-DAG: <<PhiX:i\d+>> Phi [<<Const0>>,<<Select:i\d+>>] 245 /// CHECK-DAG: <<PhiY:i\d+>> Phi [<<Const1>>,<<Add:i\d+>>] 246 /// CHECK-DAG: <<Add>> Add [<<PhiY>>,<<Const1>>] 247 /// CHECK-DAG: <<Cond:z\d+>> LessThanOrEqual [<<Add>>,<<Const1>>] 248 /// CHECK-DAG: <<Select>> Select [<<Const13>>,<<Const42>>,<<Cond>>] 249 /// CHECK-DAG: Return [<<PhiX>>] 250 MultiplePhis()251 public static int MultiplePhis() { 252 int x = 0; 253 int y = 1; 254 while (y++ < 10) { 255 if (y > 1) { 256 x = 13; 257 continue; 258 } else { 259 x = 42; 260 continue; 261 } 262 } 263 return x; 264 } 265 266 /// CHECK-START: int Main.TrueBlockWithTooManyInstructions(boolean) select_generator (before) 267 /// CHECK-DAG: <<This:l\d+>> ParameterValue 268 /// CHECK-DAG: <<Cond:z\d+>> ParameterValue 269 /// CHECK-DAG: <<Const2:i\d+>> IntConstant 2 270 /// CHECK-DAG: <<Const43:i\d+>> IntConstant 43 271 /// CHECK-DAG: If [<<Cond>>] 272 /// CHECK-DAG: <<Iget:i\d+>> InstanceFieldGet [<<This>>] 273 /// CHECK-DAG: <<Add:i\d+>> Add [<<Iget>>,<<Const2>>] 274 /// CHECK-DAG: Phi [<<Add>>,<<Const43>>] 275 276 /// CHECK-START: int Main.TrueBlockWithTooManyInstructions(boolean) select_generator (after) 277 /// CHECK-NOT: Select 278 TrueBlockWithTooManyInstructions(boolean x)279 public int TrueBlockWithTooManyInstructions(boolean x) { 280 return x ? (read_field + 2) : 43; 281 } 282 283 /// CHECK-START: int Main.FalseBlockWithTooManyInstructions(boolean) select_generator (before) 284 /// CHECK-DAG: <<This:l\d+>> ParameterValue 285 /// CHECK-DAG: <<Cond:z\d+>> ParameterValue 286 /// CHECK-DAG: <<Const3:i\d+>> IntConstant 3 287 /// CHECK-DAG: <<Const42:i\d+>> IntConstant 42 288 /// CHECK-DAG: If [<<Cond>>] 289 /// CHECK-DAG: <<Iget:i\d+>> InstanceFieldGet [<<This>>] 290 /// CHECK-DAG: <<Add:i\d+>> Add [<<Iget>>,<<Const3>>] 291 /// CHECK-DAG: Phi [<<Const42>>,<<Add>>] 292 293 /// CHECK-START: int Main.FalseBlockWithTooManyInstructions(boolean) select_generator (after) 294 /// CHECK-NOT: Select 295 FalseBlockWithTooManyInstructions(boolean x)296 public int FalseBlockWithTooManyInstructions(boolean x) { 297 return x ? 42 : (read_field + 3); 298 } 299 300 /// CHECK-START: int Main.TrueBlockWithSideEffects(boolean) select_generator (before) 301 /// CHECK-DAG: <<This:l\d+>> ParameterValue 302 /// CHECK-DAG: <<Cond:z\d+>> ParameterValue 303 /// CHECK-DAG: <<Const42:i\d+>> IntConstant 42 304 /// CHECK-DAG: <<Const43:i\d+>> IntConstant 43 305 /// CHECK-DAG: If [<<Cond>>] 306 /// CHECK-DAG: InstanceFieldSet [<<This>>,<<Const42>>] 307 /// CHECK-DAG: Phi [<<Const42>>,<<Const43>>] 308 309 /// CHECK-START: int Main.TrueBlockWithSideEffects(boolean) select_generator (after) 310 /// CHECK-NOT: Select 311 TrueBlockWithSideEffects(boolean x)312 public int TrueBlockWithSideEffects(boolean x) { 313 return x ? (write_field = 42) : 43; 314 } 315 316 /// CHECK-START: int Main.FalseBlockWithSideEffects(boolean) select_generator (before) 317 /// CHECK-DAG: <<This:l\d+>> ParameterValue 318 /// CHECK-DAG: <<Cond:z\d+>> ParameterValue 319 /// CHECK-DAG: <<Const42:i\d+>> IntConstant 42 320 /// CHECK-DAG: <<Const43:i\d+>> IntConstant 43 321 /// CHECK-DAG: If [<<Cond>>] 322 /// CHECK-DAG: InstanceFieldSet [<<This>>,<<Const43>>] 323 /// CHECK-DAG: Phi [<<Const42>>,<<Const43>>] 324 325 /// CHECK-START: int Main.FalseBlockWithSideEffects(boolean) select_generator (after) 326 /// CHECK-NOT: Select 327 FalseBlockWithSideEffects(boolean x)328 public int FalseBlockWithSideEffects(boolean x) { 329 return x ? 42 : (write_field = 43); 330 } 331 main(String[] args)332 public static void main(String[] args) throws Exception { 333 assertBoolEquals(false, SmaliBooleanNot(true)); 334 assertBoolEquals(true, SmaliBooleanNot(false)); 335 assertBoolEquals(true, GreaterThan(10, 5)); 336 assertBoolEquals(false, GreaterThan(10, 10)); 337 assertBoolEquals(false, GreaterThan(5, 10)); 338 assertBoolEquals(true, LessThan(5, 10)); 339 assertBoolEquals(false, LessThan(10, 10)); 340 assertBoolEquals(false, LessThan(10, 5)); 341 assertBoolEquals(true, ValuesOrdered(1, 3, 5)); 342 assertBoolEquals(true, ValuesOrdered(5, 3, 1)); 343 assertBoolEquals(false, ValuesOrdered(1, 3, 2)); 344 assertBoolEquals(false, ValuesOrdered(2, 3, 1)); 345 assertBoolEquals(true, ValuesOrdered(3, 3, 3)); 346 assertBoolEquals(true, ValuesOrdered(3, 3, 5)); 347 assertBoolEquals(false, ValuesOrdered(5, 5, 3)); 348 assertIntEquals(42, NegatedCondition(true)); 349 assertIntEquals(43, NegatedCondition(false)); 350 assertIntEquals(46, SimpleTrueBlock(true, 4)); 351 assertIntEquals(43, SimpleTrueBlock(false, 4)); 352 assertIntEquals(42, SimpleFalseBlock(true, 7)); 353 assertIntEquals(50, SimpleFalseBlock(false, 7)); 354 assertIntEquals(48, SimpleBothBlocks(true, 6, 2)); 355 assertIntEquals(45, SimpleBothBlocks(false, 6, 2)); 356 assertIntEquals(1, ThreeBlocks(true, true)); 357 assertIntEquals(1, ThreeBlocks(true, false)); 358 assertIntEquals(2, ThreeBlocks(false, true)); 359 assertIntEquals(3, ThreeBlocks(false, false)); 360 assertIntEquals(13, MultiplePhis()); 361 362 Main m = new Main(); 363 assertIntEquals(42, m.TrueBlockWithTooManyInstructions(true)); 364 assertIntEquals(43, m.TrueBlockWithTooManyInstructions(false)); 365 assertIntEquals(42, m.FalseBlockWithTooManyInstructions(true)); 366 assertIntEquals(43, m.FalseBlockWithTooManyInstructions(false)); 367 assertIntEquals(42, m.TrueBlockWithSideEffects(true)); 368 assertIntEquals(43, m.TrueBlockWithSideEffects(false)); 369 assertIntEquals(42, m.FalseBlockWithSideEffects(true)); 370 assertIntEquals(43, m.FalseBlockWithSideEffects(false)); 371 } 372 373 // These need to be instance fields so as to not generate a LoadClass for iget/iput. 374 public int read_field = 40; 375 public int write_field = 42; 376 } 377