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