1 /* 2 * Copyright (C) 2016 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 // 18 // Test on loop optimizations, in particular around geometric induction. 19 // 20 public class Main { 21 22 /// CHECK-START: int Main.geo1(int) loop_optimization (before) 23 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> 24 /// CHECK-DAG: Mul loop:<<Loop>> 25 // 26 /// CHECK-START: int Main.geo1(int) loop_optimization (after) 27 /// CHECK-DAG: <<Par:i\d+>> ParameterValue loop:none 28 /// CHECK-DAG: <<Zer:i\d+>> IntConstant 0 loop:none 29 /// CHECK-DAG: <<Int:i\d+>> IntConstant 1410065408 loop:none 30 /// CHECK-DAG: <<Mul:i\d+>> Mul [<<Par>>,<<Int>>] loop:none 31 /// CHECK-DAG: <<Add:i\d+>> Add [<<Mul>>,<<Zer>>] loop:none 32 /// CHECK-DAG: Return [<<Add>>] loop:none 33 // 34 /// CHECK-START: int Main.geo1(int) loop_optimization (after) 35 /// CHECK-NOT: Phi 36 public static int geo1(int a) { 37 for (int i = 0; i < 10; i++) { 38 a *= 10; 39 } 40 return a; 41 } 42 43 /// CHECK-START: int Main.geo2(int) loop_optimization (before) 44 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> 45 /// CHECK-DAG: Shl loop:<<Loop>> 46 // 47 /// CHECK-START: int Main.geo2(int) loop_optimization (after) 48 /// CHECK-DAG: <<Par:i\d+>> ParameterValue loop:none 49 /// CHECK-DAG: <<Zer:i\d+>> IntConstant 0 loop:none 50 /// CHECK-DAG: <<Int:i\d+>> IntConstant 1024 loop:none 51 /// CHECK-DAG: <<Mul:i\d+>> Mul [<<Par>>,<<Int>>] loop:none 52 /// CHECK-DAG: <<Add:i\d+>> Add [<<Mul>>,<<Zer>>] loop:none 53 /// CHECK-DAG: Return [<<Add>>] loop:none 54 // 55 /// CHECK-START: int Main.geo2(int) loop_optimization (after) 56 /// CHECK-NOT: Phi 57 public static int geo2(int a) { 58 for (int i = 0; i < 10; i++) { 59 a <<= 1; 60 } 61 return a; 62 } 63 64 /// CHECK-START: int Main.geo3(int) loop_optimization (before) 65 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> 66 /// CHECK-DAG: Div loop:<<Loop>> 67 // 68 /// CHECK-START: int Main.geo3(int) loop_optimization (after) 69 /// CHECK-DAG: <<Par:i\d+>> ParameterValue loop:none 70 /// CHECK-DAG: <<Zer:i\d+>> IntConstant 0 loop:none 71 /// CHECK-DAG: <<Int:i\d+>> IntConstant 59049 loop:none 72 /// CHECK-DAG: <<Div:i\d+>> Div [<<Par>>,<<Int>>] loop:none 73 /// CHECK-DAG: <<Add:i\d+>> Add [<<Div>>,<<Zer>>] loop:none 74 /// CHECK-DAG: Return [<<Add>>] loop:none 75 // 76 /// CHECK-START: int Main.geo3(int) loop_optimization (after) 77 /// CHECK-NOT: Phi 78 public static int geo3(int a) { 79 for (int i = 0; i < 10; i++) { 80 a /= 3; 81 } 82 return a; 83 } 84 85 /// CHECK-START: int Main.geo4(int) loop_optimization (before) 86 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> 87 /// CHECK-DAG: Rem loop:<<Loop>> 88 // 89 /// CHECK-START: int Main.geo4(int) loop_optimization (after) 90 /// CHECK-DAG: <<Par:i\d+>> ParameterValue loop:none 91 /// CHECK-DAG: <<Int:i\d+>> IntConstant 7 loop:none 92 /// CHECK-DAG: <<Rem:i\d+>> Rem [<<Par>>,<<Int>>] loop:none 93 /// CHECK-DAG: Return [<<Rem>>] loop:none 94 // 95 /// CHECK-START: int Main.geo4(int) loop_optimization (after) 96 /// CHECK-NOT: Phi 97 public static int geo4(int a) { 98 for (int i = 0; i < 10; i++) { 99 a %= 7; // a wrap-around induction 100 } 101 return a; 102 } 103 104 /// CHECK-START: int Main.geo5() loop_optimization (before) 105 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> 106 /// CHECK-DAG: Shr loop:<<Loop>> 107 // 108 /// CHECK-START: int Main.geo5() loop_optimization (after) 109 /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0 loop:none 110 /// CHECK-DAG: <<Int1:i\d+>> IntConstant 2147483647 loop:none 111 /// CHECK-DAG: <<Int2:i\d+>> IntConstant 1024 loop:none 112 /// CHECK-DAG: <<Div:i\d+>> Div [<<Int1>>,<<Int2>>] loop:none 113 /// CHECK-DAG: <<Add:i\d+>> Add [<<Div>>,<<Zero>>] loop:none 114 /// CHECK-DAG: Return [<<Add>>] loop:none 115 // 116 /// CHECK-START: int Main.geo5() loop_optimization (after) 117 /// CHECK-NOT: Phi 118 public static int geo5() { 119 int a = 0x7fffffff; 120 for (int i = 0; i < 10; i++) { 121 a >>= 1; 122 } 123 return a; 124 } 125 126 // TODO: someday? 127 // 128 /// CHECK-START: int Main.geo1BCE() BCE (before) 129 /// CHECK-DAG: BoundsCheck loop:none 130 /// CHECK-DAG: BoundsCheck loop:{{B\d+}} 131 // 132 /// CHECK-START: int Main.geo1BCE() BCE (after) 133 /// CHECK-DAG: BoundsCheck loop:{{B\d+}} 134 // 135 /// CHECK-START: int Main.geo1BCE() BCE (after) 136 /// CHECK-NOT: BoundsCheck loop:none 137 /// CHECK-NOT: Deoptimize 138 public static int geo1BCE() { 139 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 140 11, 12, 13, 14, 15, 16, 17, 19, 19, 20, 141 21, 22, 23, 24, 25, 26 }; 142 int a = 1; 143 int r = 0; 144 for (int i = 0; i < 3; i++) { 145 r += x[a]; 146 a *= 5; 147 } 148 return r; 149 } 150 151 // TODO: someday? 152 // 153 /// CHECK-START: int Main.geo2BCE() BCE (before) 154 /// CHECK-DAG: BoundsCheck loop:none 155 /// CHECK-DAG: BoundsCheck loop:{{B\d+}} 156 // 157 /// CHECK-START: int Main.geo2BCE() BCE (after) 158 /// CHECK-DAG: BoundsCheck loop:{{B\d+}} 159 // 160 /// CHECK-START: int Main.geo2BCE() BCE (after) 161 /// CHECK-NOT: BoundsCheck loop:none 162 /// CHECK-NOT: Deoptimize 163 public static int geo2BCE() { 164 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 165 11, 12, 13, 14, 15, 16, 17, 19, 19, 20, 166 21, 22, 23, 24, 25, 26 }; 167 int a = 1; 168 int r = 0; 169 for (int i = 0; i < 5; i++) { 170 r += x[a]; 171 a <<= 1; 172 } 173 return r; 174 } 175 176 /// CHECK-START: int Main.geo3BCE() BCE (before) 177 /// CHECK-DAG: BoundsCheck loop:none 178 /// CHECK-DAG: BoundsCheck loop:{{B\d+}} 179 // 180 /// CHECK-START: int Main.geo3BCE() BCE (after) 181 /// CHECK-NOT: BoundsCheck 182 /// CHECK-NOT: Deoptimize 183 public static int geo3BCE() { 184 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 185 11, 12, 13, 14, 15, 16, 17, 19, 19, 20, 186 21, 22, 23, 24, 25, 26 }; 187 int a = 25; 188 int r = 0; 189 for (int i = 0; i < 100; i++) { // a converges to 0 190 r += x[a]; 191 a /= 5; 192 } 193 return r; 194 } 195 196 /// CHECK-START: int Main.geo4BCE() BCE (before) 197 /// CHECK-DAG: BoundsCheck loop:none 198 /// CHECK-DAG: BoundsCheck loop:{{B\d+}} 199 // 200 /// CHECK-START: int Main.geo4BCE() BCE (after) 201 /// CHECK-NOT: BoundsCheck 202 /// CHECK-NOT: Deoptimize 203 public static int geo4BCE() { 204 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 205 11, 12, 13, 14, 15, 16, 17, 19, 19, 20, 206 21, 22, 23, 24, 25, 26 }; 207 int a = 25; 208 int r = 0; 209 for (int i = 0; i < 100; i++) { // a converges to 0 210 r += x[a]; 211 a %= 5; // a wrap-around induction 212 } 213 return r; 214 } 215 216 /// CHECK-START: int Main.geoMulBlackHole(int) loop_optimization (before) 217 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> 218 /// CHECK-DAG: Mul loop:<<Loop>> 219 // 220 /// CHECK-START: int Main.geoMulBlackHole(int) loop_optimization (after) 221 /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0 222 /// CHECK-DAG: Return [<<Zero>>] 223 // 224 /// CHECK-START: int Main.geoMulBlackHole(int) loop_optimization (after) 225 /// CHECK-NOT: Phi 226 /// CHECK-NOT: Mul 227 public static int geoMulBlackHole(int a) { 228 for (int i = 0; i < 100; i++) { 229 a *= 10; 230 } 231 return a; 232 } 233 234 /// CHECK-START: int Main.geoShlBlackHole(int) loop_optimization (before) 235 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> 236 /// CHECK-DAG: Shl loop:<<Loop>> 237 // 238 /// CHECK-START: int Main.geoShlBlackHole(int) loop_optimization (after) 239 /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0 240 /// CHECK-DAG: Return [<<Zero>>] 241 // 242 /// CHECK-START: int Main.geoShlBlackHole(int) loop_optimization (after) 243 /// CHECK-NOT: Phi 244 /// CHECK-NOT: Shl 245 public static int geoShlBlackHole(int a) { 246 for (int i = 0; i < 100; i++) { 247 a <<= 1; 248 } 249 return a; 250 } 251 252 /// CHECK-START: int Main.geoDivBlackHole(int) loop_optimization (before) 253 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> 254 /// CHECK-DAG: Div loop:<<Loop>> 255 // 256 /// CHECK-START: int Main.geoDivBlackHole(int) loop_optimization (after) 257 /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0 258 /// CHECK-DAG: Return [<<Zero>>] 259 // 260 /// CHECK-START: int Main.geoDivBlackHole(int) loop_optimization (after) 261 /// CHECK-NOT: Phi 262 /// CHECK-NOT: Div 263 public static int geoDivBlackHole(int a) { 264 for (int i = 0; i < 100; i++) { 265 a /= 10; 266 } 267 return a; 268 } 269 270 // Even though Rem is already optimized away by the time induction analysis 271 // and the loop optimizer run, the loop is optimized with a trivial 272 // wrap-around induction just as the wrap-around for REM would. 273 // 274 /// CHECK-START: int Main.geoRemBlackHole(int) loop_optimization (before) 275 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> 276 /// CHECK-DAG: Phi loop:<<Loop>> 277 // 278 /// CHECK-START: int Main.geoRemBlackHole(int) loop_optimization (after) 279 /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0 280 /// CHECK-DAG: Return [<<Zero>>] 281 // 282 /// CHECK-START: int Main.geoRemBlackHole(int) loop_optimization (after) 283 /// CHECK-NOT: Phi 284 public static int geoRemBlackHole(int a) { 285 for (int i = 0; i < 100; i++) { 286 a %= 1; 287 } 288 return a; 289 } 290 291 // 292 // Verifier. 293 // 294 295 public static void main(String[] args) { 296 int m = 1410065408; 297 for (int i = -100; i <= 100; i++) { 298 expectEquals(m * i, geo1(i)); 299 } 300 for (int i = 1; i <= 1000000000; i *= 10) { 301 expectEquals( m * i, geo1( i)); 302 expectEquals(-m * i, geo1(-i)); 303 } 304 305 for (int i = -100; i <= 100; i++) { 306 expectEquals(i << 10, geo2(i)); 307 } 308 for (int i = 0; i < 22; i++) { 309 expectEquals(1 << (i + 10), geo2(1 << i)); 310 } 311 expectEquals(0x80000400, geo2(0x00200001)); 312 expectEquals(0x00000000, geo2(0x00400000)); 313 expectEquals(0x00000400, geo2(0x00400001)); 314 315 int d = 59049; 316 for (int i = -100; i <= 100; i++) { 317 expectEquals(0, geo3(i)); 318 } 319 for (int i = 1; i <= 100; i++) { 320 expectEquals( i, geo3( i * d)); 321 expectEquals( i, geo3( i * d + 1)); 322 expectEquals(-i, geo3(-i * d)); 323 expectEquals(-i, geo3(-i * d - 1)); 324 } 325 326 for (int i = -100; i <= 100; i++) { 327 expectEquals(i % 7, geo4(i)); 328 } 329 330 expectEquals(0x1fffff, geo5()); 331 332 expectEquals(34, geo1BCE()); 333 expectEquals(36, geo2BCE()); 334 expectEquals(131, geo3BCE()); 335 expectEquals(125, geo4BCE()); 336 337 // Nothing escapes! 338 expectEquals(0, geoMulBlackHole(0)); 339 expectEquals(0, geoShlBlackHole(0)); 340 expectEquals(0, geoDivBlackHole(0)); 341 expectEquals(0, geoRemBlackHole(0)); 342 for (int i = -100; i <= 100; i++) { 343 expectEquals(0, geoMulBlackHole(i)); 344 expectEquals(0, geoShlBlackHole(i)); 345 expectEquals(0, geoDivBlackHole(i)); 346 expectEquals(0, geoRemBlackHole(i)); 347 } 348 for (int i = 0; i < 31; i++) { 349 expectEquals(0, geoMulBlackHole(1 << i)); 350 expectEquals(0, geoShlBlackHole(1 << i)); 351 expectEquals(0, geoDivBlackHole(1 << i)); 352 expectEquals(0, geoRemBlackHole(1 << i)); 353 } 354 expectEquals(0, geoMulBlackHole(0x7fffffff)); 355 expectEquals(0, geoShlBlackHole(0x7fffffff)); 356 expectEquals(0, geoDivBlackHole(0x7fffffff)); 357 expectEquals(0, geoRemBlackHole(0x7fffffff)); 358 expectEquals(0, geoMulBlackHole(0x80000000)); 359 expectEquals(0, geoShlBlackHole(0x80000000)); 360 expectEquals(0, geoDivBlackHole(0x80000000)); 361 expectEquals(0, geoRemBlackHole(0x80000000)); 362 363 System.out.println("passed"); 364 } 365 366 private static void expectEquals(int expected, int result) { 367 if (expected != result) { 368 throw new Error("Expected: " + expected + ", found: " + result); 369 } 370 } 371 } 372
