1 /* 2 * Copyright (C) 2018 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 import java.lang.reflect.Method; 18 19 // 20 // Test loop optimizations, in particular scalar loop peeling and unrolling. 21 public class Main { 22 23 static final int LENGTH = 4 * 1024; 24 int[] a = new int[LENGTH]; 25 int[] b = new int[LENGTH]; 26 27 private static final int LENGTH_A = LENGTH; 28 private static final int LENGTH_B = 16; 29 private static final int RESULT_POS = 4; 30 31 double[][] mA; 32 double[][] mB; 33 double[][] mC; 34 Main()35 public Main() { 36 mA = new double[LENGTH_A][]; 37 mB = new double[LENGTH_B][]; 38 mC = new double[LENGTH_B][]; 39 for (int i = 0; i < LENGTH_A; i++) { 40 mA[i] = new double[LENGTH_B]; 41 } 42 43 for (int i = 0; i < LENGTH_B; i++) { 44 mB[i] = new double[LENGTH_A]; 45 mC[i] = new double[LENGTH_B]; 46 } 47 } 48 initMatrix(double[][] m)49 private static final void initMatrix(double[][] m) { 50 for (int i = 0; i < m.length; i++) { 51 for (int j = 0; j < m[i].length; j++) { 52 m[i][j] = (double) (i * LENGTH / (j + 1)); 53 } 54 } 55 } 56 initIntArray(int[] a)57 private static final void initIntArray(int[] a) { 58 for (int i = 0; i < a.length; i++) { 59 a[i] = i % 4; 60 } 61 } 62 initDoubleArray(double[] a)63 private static final void initDoubleArray(double[] a) { 64 for (int i = 0; i < a.length; i++) { 65 a[i] = (double)(i % 4); 66 } 67 } 68 69 /// CHECK-START: void Main.unrollingLoadStoreElimination(int[]) loop_optimization (before) 70 /// CHECK-DAG: <<Array:l\d+>> ParameterValue loop:none 71 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none 72 /// CHECK-DAG: <<Limit:i\d+>> IntConstant 4094 loop:none 73 /// CHECK-DAG: <<Phi:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 74 /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<Phi>>,<<Limit>>] loop:<<Loop>> outer_loop:none 75 /// CHECK-DAG: <<If:v\d+>> If [<<Check>>] loop:<<Loop>> outer_loop:none 76 /// CHECK-DAG: <<Get0:i\d+>> ArrayGet [<<Array>>,<<Phi>>] loop:<<Loop>> outer_loop:none 77 /// CHECK-DAG: <<IndAdd:i\d+>> Add [<<Phi>>,<<Const1>>] loop:<<Loop>> outer_loop:none 78 /// CHECK-DAG: <<Get1:i\d+>> ArrayGet [<<Array>>,<<IndAdd>>] loop:<<Loop>> outer_loop:none 79 /// CHECK-DAG: <<Add:i\d+>> Add [<<Get0>>,<<Get1>>] loop:<<Loop>> outer_loop:none 80 /// CHECK-DAG: ArraySet [<<Array>>,<<Phi>>,<<Add>>] loop:<<Loop>> outer_loop:none 81 82 /// CHECK-START: void Main.unrollingLoadStoreElimination(int[]) loop_optimization (before) 83 /// CHECK: ArrayGet 84 /// CHECK: ArrayGet 85 /// CHECK-NOT: ArrayGet 86 87 /// CHECK-START: void Main.unrollingLoadStoreElimination(int[]) loop_optimization (before) 88 /// CHECK: ArraySet 89 /// CHECK-NOT: ArraySet 90 91 /// CHECK-START: void Main.unrollingLoadStoreElimination(int[]) loop_optimization (after) 92 /// CHECK-DAG: <<Array:l\d+>> ParameterValue loop:none 93 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none 94 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none 95 /// CHECK-DAG: <<Limit:i\d+>> IntConstant 4094 loop:none 96 /// CHECK-DAG: <<Phi:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 97 /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<Phi>>,<<Limit>>] loop:<<Loop>> outer_loop:none 98 /// CHECK-DAG: <<If:v\d+>> If [<<Check>>] loop:<<Loop>> outer_loop:none 99 /// CHECK-DAG: <<Get0:i\d+>> ArrayGet [<<Array>>,<<Phi>>] loop:<<Loop>> outer_loop:none 100 /// CHECK-DAG: <<IndAdd:i\d+>> Add [<<Phi>>,<<Const1>>] loop:<<Loop>> outer_loop:none 101 /// CHECK-DAG: <<Get1:i\d+>> ArrayGet [<<Array>>,<<IndAdd>>] loop:<<Loop>> outer_loop:none 102 /// CHECK-DAG: <<Add:i\d+>> Add [<<Get0>>,<<Get1>>] loop:<<Loop>> outer_loop:none 103 /// CHECK-DAG: ArraySet [<<Array>>,<<Phi>>,<<Add>>] loop:<<Loop>> outer_loop:none 104 // 105 /// CHECK-DAG: <<CheckA:z\d+>> GreaterThanOrEqual [<<IndAdd>>,<<Limit>>] loop:<<Loop>> outer_loop:none 106 /// CHECK-DAG: <<IfA:v\d+>> If [<<Const0>>] loop:<<Loop>> outer_loop:none 107 /// CHECK-DAG: <<Get0A:i\d+>> ArrayGet [<<Array>>,<<IndAdd>>] loop:<<Loop>> outer_loop:none 108 /// CHECK-DAG: <<IndAddA:i\d+>> Add [<<IndAdd>>,<<Const1>>] loop:<<Loop>> outer_loop:none 109 /// CHECK-DAG: <<Get1A:i\d+>> ArrayGet [<<Array>>,<<IndAddA>>] loop:<<Loop>> outer_loop:none 110 /// CHECK-DAG: <<AddA:i\d+>> Add [<<Get0A>>,<<Get1A>>] loop:<<Loop>> outer_loop:none 111 /// CHECK-DAG: ArraySet [<<Array>>,<<IndAdd>>,<<AddA>>] loop:<<Loop>> outer_loop:none 112 113 /// CHECK-START: void Main.unrollingLoadStoreElimination(int[]) loop_optimization (after) 114 /// CHECK: ArrayGet 115 /// CHECK: ArrayGet 116 /// CHECK: ArrayGet 117 /// CHECK: ArrayGet 118 /// CHECK-NOT: ArrayGet 119 120 /// CHECK-START: void Main.unrollingLoadStoreElimination(int[]) loop_optimization (after) 121 /// CHECK: ArraySet 122 /// CHECK: ArraySet 123 /// CHECK-NOT: ArraySet unrollingLoadStoreElimination(int[] a)124 private static final void unrollingLoadStoreElimination(int[] a) { 125 for (int i = 0; i < LENGTH - 2; i++) { 126 a[i] += a[i + 1]; 127 } 128 } 129 130 // Simple check that loop unrolling has happened. 131 // 132 /// CHECK-START: void Main.unrollingSwitch(int[]) loop_optimization (before) 133 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none 134 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none 135 /// CHECK-DAG: <<Limit:i\d+>> IntConstant 4096 loop:none 136 /// CHECK-DAG: <<PhiI:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 137 /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<PhiI>>,<<Limit>>] loop:<<Loop>> outer_loop:none 138 /// CHECK-DAG: <<If:v\d+>> If [<<Check>>] loop:<<Loop>> outer_loop:none 139 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 140 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none 141 /// CHECK-DAG: Add [<<PhiI>>,<<Const1>>] loop:<<Loop>> outer_loop:none 142 143 /// CHECK-START: void Main.unrollingSwitch(int[]) loop_optimization (before) 144 /// CHECK: ArrayGet 145 /// CHECK-NOT: ArrayGet 146 147 /// CHECK-START: void Main.unrollingSwitch(int[]) loop_optimization (before) 148 /// CHECK: ArraySet 149 /// CHECK-NOT: ArraySet 150 151 /// CHECK-START: void Main.unrollingSwitch(int[]) loop_optimization (after) 152 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none 153 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none 154 /// CHECK-DAG: <<Limit:i\d+>> IntConstant 4096 loop:none 155 /// CHECK-DAG: <<PhiI:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 156 /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<PhiI>>,<<Limit>>] loop:<<Loop>> outer_loop:none 157 /// CHECK-DAG: <<If:v\d+>> If [<<Check>>] loop:<<Loop>> outer_loop:none 158 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 159 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none 160 /// CHECK-DAG: <<AddI:i\d+>> Add [<<PhiI>>,<<Const1>>] loop:<<Loop>> outer_loop:none 161 // 162 /// CHECK-DAG: <<CheckA:z\d+>> GreaterThanOrEqual [<<AddI>>,<<Limit>>] loop:<<Loop>> outer_loop:none 163 /// CHECK-DAG: <<IfA:v\d+>> If [<<Const0>>] loop:<<Loop>> outer_loop:none 164 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 165 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none 166 /// CHECK-DAG: Add [<<AddI>>,<<Const1>>] loop:<<Loop>> outer_loop:none 167 168 /// CHECK-START: void Main.unrollingSwitch(int[]) loop_optimization (after) 169 /// CHECK: ArrayGet 170 /// CHECK: ArrayGet 171 /// CHECK-NOT: ArrayGet 172 173 /// CHECK-START: void Main.unrollingSwitch(int[]) loop_optimization (after) 174 /// CHECK: ArraySet 175 /// CHECK: ArraySet 176 /// CHECK-NOT: ArraySet unrollingSwitch(int[] a)177 private static final void unrollingSwitch(int[] a) { 178 for (int i = 0; i < LENGTH; i++) { 179 switch (i % 3) { 180 case 2: 181 a[i]++; 182 break; 183 default: 184 break; 185 } 186 } 187 } 188 189 // Simple check that loop unrolling has happened. 190 // 191 /// CHECK-START: void Main.unrollingSwapElements(int[]) loop_optimization (before) 192 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none 193 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none 194 /// CHECK-DAG: <<Limit:i\d+>> IntConstant 4094 loop:none 195 /// CHECK-DAG: <<PhiI:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 196 /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<PhiI>>,<<Limit>>] loop:<<Loop>> outer_loop:none 197 /// CHECK-DAG: <<If:v\d+>> If [<<Check>>] loop:<<Loop>> outer_loop:none 198 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 199 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 200 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none 201 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none 202 /// CHECK-DAG: Add [<<PhiI>>,<<Const1>>] loop:<<Loop>> outer_loop:none 203 204 /// CHECK-START: void Main.unrollingSwapElements(int[]) loop_optimization (before) 205 /// CHECK: ArrayGet 206 /// CHECK: ArrayGet 207 /// CHECK-NOT: ArrayGet 208 209 /// CHECK-START: void Main.unrollingSwapElements(int[]) loop_optimization (before) 210 /// CHECK: ArraySet 211 /// CHECK: ArraySet 212 /// CHECK-NOT: ArraySet 213 214 /// CHECK-START: void Main.unrollingSwapElements(int[]) loop_optimization (after) 215 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none 216 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none 217 /// CHECK-DAG: <<Limit:i\d+>> IntConstant 4094 loop:none 218 /// CHECK-DAG: <<PhiI:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 219 /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<PhiI>>,<<Limit>>] loop:<<Loop>> outer_loop:none 220 /// CHECK-DAG: <<If:v\d+>> If [<<Check>>] loop:<<Loop>> outer_loop:none 221 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 222 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 223 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none 224 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none 225 /// CHECK-DAG: <<AddI:i\d+>> Add [<<PhiI>>,<<Const1>>] loop:<<Loop>> outer_loop:none 226 // 227 /// CHECK-DAG: <<CheckA:z\d+>> GreaterThanOrEqual [<<AddI>>,<<Limit>>] loop:<<Loop>> outer_loop:none 228 /// CHECK-DAG: <<IfA:v\d+>> If [<<Const0>>] loop:<<Loop>> outer_loop:none 229 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 230 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 231 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none 232 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none 233 /// CHECK-DAG: Add [<<AddI>>,<<Const1>>] loop:<<Loop>> outer_loop:none 234 235 /// CHECK-START: void Main.unrollingSwapElements(int[]) loop_optimization (after) 236 /// CHECK: ArrayGet 237 /// CHECK: ArrayGet 238 /// CHECK: ArrayGet 239 /// CHECK: ArrayGet 240 /// CHECK-NOT: ArrayGet 241 242 /// CHECK-START: void Main.unrollingSwapElements(int[]) loop_optimization (after) 243 /// CHECK: ArraySet 244 /// CHECK: ArraySet 245 /// CHECK: ArraySet 246 /// CHECK: ArraySet 247 /// CHECK-NOT: ArraySet unrollingSwapElements(int[] array)248 private static final void unrollingSwapElements(int[] array) { 249 for (int i = 0; i < LENGTH - 2; i++) { 250 if (array[i] > array[i + 1]) { 251 int temp = array[i + 1]; 252 array[i + 1] = array[i]; 253 array[i] = temp; 254 } 255 } 256 } 257 258 // Simple check that loop unrolling has happened. 259 // 260 /// CHECK-START: void Main.unrollingRInnerproduct(double[][], double[][], double[][], int, int) loop_optimization (before) 261 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none 262 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none 263 /// CHECK-DAG: <<Limit:i\d+>> IntConstant 16 loop:none 264 /// CHECK-DAG: <<PhiI:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 265 /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<PhiI>>,<<Limit>>] loop:<<Loop>> outer_loop:none 266 /// CHECK-DAG: <<If:v\d+>> If [<<Check>>] loop:<<Loop>> outer_loop:none 267 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 268 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 269 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 270 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 271 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none 272 /// CHECK-DAG: Add [<<PhiI>>,<<Const1>>] loop:<<Loop>> outer_loop:none 273 274 // We have two other `ArrayGet` before the `If` that appears in the CHECK-DAG above. 275 /// CHECK-START: void Main.unrollingRInnerproduct(double[][], double[][], double[][], int, int) loop_optimization (before) 276 /// CHECK: ArrayGet 277 /// CHECK: ArrayGet 278 /// CHECK: ArrayGet 279 /// CHECK: ArrayGet 280 /// CHECK: ArrayGet 281 /// CHECK: ArrayGet 282 /// CHECK-NOT: ArrayGet 283 284 /// CHECK-START: void Main.unrollingRInnerproduct(double[][], double[][], double[][], int, int) loop_optimization (before) 285 /// CHECK: ArraySet 286 /// CHECK: ArraySet 287 /// CHECK-NOT: ArraySet 288 289 /// CHECK-START: void Main.unrollingRInnerproduct(double[][], double[][], double[][], int, int) loop_optimization (after) 290 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none 291 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none 292 /// CHECK-DAG: <<Limit:i\d+>> IntConstant 16 loop:none 293 /// CHECK-DAG: <<PhiI:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 294 /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<PhiI>>,<<Limit>>] loop:<<Loop>> outer_loop:none 295 /// CHECK-DAG: <<If:v\d+>> If [<<Check>>] loop:<<Loop>> outer_loop:none 296 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 297 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 298 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 299 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 300 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none 301 /// CHECK-DAG: <<AddI:i\d+>> Add [<<PhiI>>,<<Const1>>] loop:<<Loop>> outer_loop:none 302 // 303 /// CHECK-DAG: <<CheckA:z\d+>> GreaterThanOrEqual [<<AddI>>,<<Limit>>] loop:<<Loop>> outer_loop:none 304 /// CHECK-DAG: <<IfA:v\d+>> If [<<Const0>>] loop:<<Loop>> outer_loop:none 305 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 306 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 307 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 308 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 309 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none 310 /// CHECK-DAG: Add [<<AddI>>,<<Const1>>] loop:<<Loop>> outer_loop:none 311 312 /// CHECK-START: void Main.unrollingRInnerproduct(double[][], double[][], double[][], int, int) loop_optimization (after) 313 /// CHECK: ArrayGet 314 /// CHECK: ArrayGet 315 /// CHECK: ArrayGet 316 /// CHECK: ArrayGet 317 /// CHECK: ArrayGet 318 /// CHECK: ArrayGet 319 /// CHECK: ArrayGet 320 /// CHECK: ArrayGet 321 /// CHECK: ArrayGet 322 /// CHECK: ArrayGet 323 /// CHECK-NOT: ArrayGet 324 325 /// CHECK-START: void Main.unrollingRInnerproduct(double[][], double[][], double[][], int, int) loop_optimization (after) 326 /// CHECK: ArraySet 327 /// CHECK: ArraySet 328 /// CHECK: ArraySet 329 /// CHECK-NOT: ArraySet unrollingRInnerproduct(double[][] result, double[][] a, double[][] b, int row, int column)330 private static final void unrollingRInnerproduct(double[][] result, 331 double[][] a, 332 double[][] b, 333 int row, 334 int column) { 335 // computes the inner product of A[row,*] and B[*,column] 336 int i; 337 result[row][column] = 0.0f; 338 for (i = 0; i < LENGTH_B; i++) { 339 result[row][column] = result[row][column] + a[row][i] * b[i][column]; 340 } 341 } 342 343 // nested loop 344 // [[[]]] 345 346 /// CHECK-START: void Main.unrollingInTheNest(int[], int[], int) loop_optimization (before) 347 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none 348 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none 349 /// CHECK-DAG: <<Limit:i\d+>> IntConstant 128 loop:none 350 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop1:B\d+>> outer_loop:none 351 /// CHECK-DAG: <<Phi2:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop2:B\d+>> outer_loop:<<Loop1>> 352 /// CHECK-DAG: <<Phi3:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop3:B\d+>> outer_loop:<<Loop2>> 353 /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<Phi3>>,<<Limit>>] loop:<<Loop3>> outer_loop:<<Loop2>> 354 /// CHECK-DAG: If [<<Check>>] loop:<<Loop3>> outer_loop:<<Loop2>> 355 /// CHECK-DAG: ArrayGet loop:<<Loop3>> outer_loop:<<Loop2>> 356 /// CHECK-DAG: ArraySet loop:<<Loop3>> outer_loop:<<Loop2>> 357 /// CHECK-DAG: ArrayGet loop:<<Loop3>> outer_loop:<<Loop2>> 358 /// CHECK-DAG: ArraySet loop:<<Loop3>> outer_loop:<<Loop2>> 359 /// CHECK-DAG: Add [<<Phi3>>,<<Const1>>] loop:<<Loop3>> outer_loop:<<Loop2>> 360 361 // Each one of the three `for` loops has an `if`. 362 /// CHECK-START: void Main.unrollingInTheNest(int[], int[], int) loop_optimization (before) 363 /// CHECK: If 364 /// CHECK: If 365 /// CHECK: If 366 /// CHECK-NOT: If 367 368 /// CHECK-START: void Main.unrollingInTheNest(int[], int[], int) loop_optimization (before) 369 /// CHECK: ArrayGet 370 /// CHECK: ArrayGet 371 /// CHECK-NOT: ArrayGet 372 373 /// CHECK-START: void Main.unrollingInTheNest(int[], int[], int) loop_optimization (before) 374 /// CHECK: ArraySet 375 /// CHECK: ArraySet 376 /// CHECK-NOT: ArraySet 377 378 /// CHECK-START: void Main.unrollingInTheNest(int[], int[], int) loop_optimization (after) 379 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none 380 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none 381 /// CHECK-DAG: <<Limit:i\d+>> IntConstant 128 loop:none 382 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop1:B\d+>> outer_loop:none 383 /// CHECK-DAG: <<Phi2:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop2:B\d+>> outer_loop:<<Loop1>> 384 /// CHECK-DAG: <<Phi3:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop3:B\d+>> outer_loop:<<Loop2>> 385 /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<Phi3>>,<<Limit>>] loop:<<Loop3>> outer_loop:<<Loop2>> 386 /// CHECK-DAG: If [<<Check>>] loop:<<Loop3>> outer_loop:<<Loop2>> 387 /// CHECK-DAG: ArrayGet loop:<<Loop3>> outer_loop:<<Loop2>> 388 /// CHECK-DAG: ArraySet loop:<<Loop3>> outer_loop:<<Loop2>> 389 /// CHECK-DAG: ArrayGet loop:<<Loop3>> outer_loop:<<Loop2>> 390 /// CHECK-DAG: ArraySet loop:<<Loop3>> outer_loop:<<Loop2>> 391 /// CHECK-DAG: <<AddI:i\d+>> Add [<<Phi3>>,<<Const1>>] loop:<<Loop3>> outer_loop:<<Loop2>> 392 // 393 /// CHECK-DAG: If [<<Const0>>] loop:<<Loop3>> outer_loop:<<Loop2>> 394 /// CHECK-DAG: ArrayGet loop:<<Loop3>> outer_loop:<<Loop2>> 395 /// CHECK-DAG: ArraySet loop:<<Loop3>> outer_loop:<<Loop2>> 396 /// CHECK-DAG: ArrayGet loop:<<Loop3>> outer_loop:<<Loop2>> 397 /// CHECK-DAG: ArraySet loop:<<Loop3>> outer_loop:<<Loop2>> 398 399 // Loop unrolling adds a 4th `if`. It is the one with `Const0` above. 400 /// CHECK-START: void Main.unrollingInTheNest(int[], int[], int) loop_optimization (after) 401 /// CHECK: If 402 /// CHECK: If 403 /// CHECK: If 404 /// CHECK: If 405 /// CHECK-NOT: If 406 407 /// CHECK-START: void Main.unrollingInTheNest(int[], int[], int) loop_optimization (after) 408 /// CHECK: ArrayGet 409 /// CHECK: ArrayGet 410 /// CHECK: ArrayGet 411 /// CHECK: ArrayGet 412 /// CHECK-NOT: ArrayGet 413 414 /// CHECK-START: void Main.unrollingInTheNest(int[], int[], int) loop_optimization (after) 415 /// CHECK: ArraySet 416 /// CHECK: ArraySet 417 /// CHECK: ArraySet 418 /// CHECK: ArraySet 419 /// CHECK-NOT: ArraySet unrollingInTheNest(int[] a, int[] b, int x)420 private static final void unrollingInTheNest(int[] a, int[] b, int x) { 421 for (int k = 0; k < 16; k++) { 422 for (int j = 0; j < 16; j++) { 423 for (int i = 0; i < 128; i++) { 424 b[x]++; 425 a[i] = a[i] + 1; 426 } 427 } 428 } 429 } 430 431 // nested loop: 432 // [ 433 // if [] else [] 434 // ] 435 436 /// CHECK-START: void Main.unrollingTwoLoopsInTheNest(int[], int[], int) loop_optimization (before) 437 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none 438 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none 439 /// CHECK-DAG: <<Limit:i\d+>> IntConstant 128 loop:none 440 /// CHECK-DAG: <<XThres:i\d+>> IntConstant 100 loop:none 441 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop1:B\d+>> outer_loop:none 442 // 443 /// CHECK-DAG: <<Phi2:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop2:B\d+>> outer_loop:<<Loop1>> 444 /// CHECK-DAG: <<Check2:z\d+>> GreaterThanOrEqual [<<Phi2>>,<<Limit>>] loop:<<Loop2>> outer_loop:<<Loop1>> 445 /// CHECK-DAG: If [<<Check2>>] loop:<<Loop2>> outer_loop:<<Loop1>> 446 /// CHECK-DAG: ArrayGet loop:<<Loop2>> outer_loop:<<Loop1>> 447 /// CHECK-DAG: ArraySet loop:<<Loop2>> outer_loop:<<Loop1>> 448 /// CHECK-DAG: <<AddI2:i\d+>> Add [<<Phi2>>,<<Const1>>] loop:<<Loop2>> outer_loop:<<Loop1>> 449 // 450 /// CHECK-DAG: <<Phi3:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop3:B\d+>> outer_loop:<<Loop1>> 451 /// CHECK-DAG: <<Check3:z\d+>> GreaterThanOrEqual [<<Phi3>>,<<Limit>>] loop:<<Loop3>> outer_loop:<<Loop1>> 452 /// CHECK-DAG: If [<<Check3>>] loop:<<Loop3>> outer_loop:<<Loop1>> 453 /// CHECK-DAG: ArrayGet loop:<<Loop3>> outer_loop:<<Loop1>> 454 /// CHECK-DAG: ArraySet loop:<<Loop3>> outer_loop:<<Loop1>> 455 /// CHECK-DAG: <<AddI3:i\d+>> Add [<<Phi3>>,<<Const1>>] loop:<<Loop3>> outer_loop:<<Loop1>> 456 457 // Each one of the three `for` loops has an `if`. Plus an `if` inside the outer `for`. 458 /// CHECK-START: void Main.unrollingTwoLoopsInTheNest(int[], int[], int) loop_optimization (before) 459 /// CHECK: If 460 /// CHECK: If 461 /// CHECK: If 462 /// CHECK: If 463 /// CHECK-NOT: If 464 465 /// CHECK-START: void Main.unrollingTwoLoopsInTheNest(int[], int[], int) loop_optimization (before) 466 /// CHECK: ArrayGet 467 /// CHECK: ArrayGet 468 /// CHECK-NOT: ArrayGet 469 470 /// CHECK-START: void Main.unrollingTwoLoopsInTheNest(int[], int[], int) loop_optimization (before) 471 /// CHECK: ArraySet 472 /// CHECK: ArraySet 473 /// CHECK-NOT: ArraySet 474 475 /// CHECK-START: void Main.unrollingTwoLoopsInTheNest(int[], int[], int) loop_optimization (after) 476 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none 477 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none 478 /// CHECK-DAG: <<Limit:i\d+>> IntConstant 128 loop:none 479 /// CHECK-DAG: <<XThres:i\d+>> IntConstant 100 loop:none 480 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop1:B\d+>> outer_loop:none 481 // 482 /// CHECK-DAG: <<Phi2:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop2:B\d+>> outer_loop:<<Loop1>> 483 /// CHECK-DAG: <<Check2:z\d+>> GreaterThanOrEqual [<<Phi2>>,<<Limit>>] loop:<<Loop2>> outer_loop:<<Loop1>> 484 /// CHECK-DAG: If [<<Check2>>] loop:<<Loop2>> outer_loop:<<Loop1>> 485 /// CHECK-DAG: ArrayGet loop:<<Loop2>> outer_loop:<<Loop1>> 486 /// CHECK-DAG: ArraySet loop:<<Loop2>> outer_loop:<<Loop1>> 487 /// CHECK-DAG: <<AddI2:i\d+>> Add [<<Phi2>>,<<Const1>>] loop:<<Loop2>> outer_loop:<<Loop1>> 488 /// CHECK-DAG: If [<<Const0>>] loop:<<Loop2>> outer_loop:<<Loop1>> 489 /// CHECK-DAG: ArrayGet loop:<<Loop2>> outer_loop:<<Loop1>> 490 /// CHECK-DAG: ArraySet loop:<<Loop2>> outer_loop:<<Loop1>> 491 /// CHECK-DAG: Add [<<AddI2>>,<<Const1>>] loop:<<Loop2>> outer_loop:<<Loop1>> 492 // 493 /// CHECK-DAG: <<Phi3:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop3:B\d+>> outer_loop:<<Loop1>> 494 /// CHECK-DAG: <<Check3:z\d+>> GreaterThanOrEqual [<<Phi3>>,<<Limit>>] loop:<<Loop3>> outer_loop:<<Loop1>> 495 /// CHECK-DAG: If [<<Check3>>] loop:<<Loop3>> outer_loop:<<Loop1>> 496 /// CHECK-DAG: ArrayGet loop:<<Loop3>> outer_loop:<<Loop1>> 497 /// CHECK-DAG: ArraySet loop:<<Loop3>> outer_loop:<<Loop1>> 498 /// CHECK-DAG: <<AddI3:i\d+>> Add [<<Phi3>>,<<Const1>>] loop:<<Loop3>> outer_loop:<<Loop1>> 499 /// CHECK-DAG: If [<<Const0>>] loop:<<Loop3>> outer_loop:<<Loop1>> 500 /// CHECK-DAG: ArrayGet loop:<<Loop3>> outer_loop:<<Loop1>> 501 /// CHECK-DAG: ArraySet loop:<<Loop3>> outer_loop:<<Loop1>> 502 /// CHECK-DAG: Add [<<AddI3>>,<<Const1>>] loop:<<Loop3>> outer_loop:<<Loop1>> 503 504 // LoopOptimization adds two `if`s. One for each loop unrolling. 505 /// CHECK-START: void Main.unrollingTwoLoopsInTheNest(int[], int[], int) loop_optimization (after) 506 /// CHECK: If 507 /// CHECK: If 508 /// CHECK: If 509 /// CHECK: If 510 /// CHECK: If 511 /// CHECK: If 512 /// CHECK-NOT: If 513 514 /// CHECK-START: void Main.unrollingTwoLoopsInTheNest(int[], int[], int) loop_optimization (after) 515 /// CHECK: ArrayGet 516 /// CHECK: ArrayGet 517 /// CHECK: ArrayGet 518 /// CHECK: ArrayGet 519 /// CHECK-NOT: ArrayGet 520 521 /// CHECK-START: void Main.unrollingTwoLoopsInTheNest(int[], int[], int) loop_optimization (after) 522 /// CHECK: ArraySet 523 /// CHECK: ArraySet 524 /// CHECK: ArraySet 525 /// CHECK: ArraySet 526 /// CHECK-NOT: ArraySet unrollingTwoLoopsInTheNest(int[] a, int[] b, int x)527 private static final void unrollingTwoLoopsInTheNest(int[] a, int[] b, int x) { 528 for (int k = 0; k < 128; k++) { 529 if (x > 100) { 530 for (int j = 0; j < 128; j++) { 531 a[x]++; 532 } 533 } else { 534 for (int i = 0; i < 128; i++) { 535 b[x]++; 536 } 537 } 538 } 539 } 540 541 /// CHECK-START: int Main.unrollingSimpleLiveOuts(int[]) loop_optimization (before) 542 /// CHECK-DAG: <<Array:l\d+>> ParameterValue loop:none 543 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none 544 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none 545 /// CHECK-DAG: <<Const2:i\d+>> IntConstant 2 loop:none 546 /// CHECK-DAG: <<Limit:i\d+>> IntConstant 4094 loop:none 547 /// CHECK-DAG: <<PhiS:i\d+>> Phi [<<Const1>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 548 /// CHECK-DAG: <<PhiT:i\d+>> Phi [<<Const2>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 549 /// CHECK-DAG: <<PhiI:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 550 /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<PhiI>>,<<Limit>>] loop:<<Loop>> outer_loop:none 551 /// CHECK-DAG: If [<<Check>>] loop:<<Loop>> outer_loop:none 552 /// CHECK-DAG: <<AddI:i\d+>> Add [<<PhiI>>,<<Const1>>] loop:<<Loop>> outer_loop:none 553 /// CHECK-DAG: <<Get0:i\d+>> ArrayGet [<<Array>>,<<AddI>>] loop:<<Loop>> outer_loop:none 554 /// CHECK-DAG: <<AddS:i\d+>> Add [<<PhiS>>,<<Get0>>] loop:<<Loop>> outer_loop:none 555 /// CHECK-DAG: <<AddT:i\d+>> Mul [<<PhiT>>,<<Get0>>] loop:<<Loop>> outer_loop:none 556 /// CHECK-DAG: <<Get1:i\d+>> ArrayGet [<<Array>>,<<PhiI>>] loop:<<Loop>> outer_loop:none 557 /// CHECK-DAG: <<AddArr:i\d+>> Add [<<AddS>>,<<Get1>>] loop:<<Loop>> outer_loop:none 558 /// CHECK-DAG: ArraySet [<<Array>>,<<PhiI>>,<<AddArr>>] loop:<<Loop>> outer_loop:none 559 // 560 /// CHECK-DAG: <<STAdd:i\d+>> Add [<<PhiS>>,<<PhiT>>] loop:none 561 /// CHECK-DAG: <<ZCheck:i\d+>> DivZeroCheck [<<STAdd>>] env:[[<<PhiS>>,<<PhiT>>,<<STAdd>>,<<Const1>>,_,<<Array>>]] loop:none 562 /// CHECK-DAG: <<Div:i\d+>> Div [<<Const1>>,<<ZCheck>>] loop:none 563 /// CHECK-DAG: Return [<<Div>>] loop:none 564 565 /// CHECK-START: int Main.unrollingSimpleLiveOuts(int[]) loop_optimization (before) 566 /// CHECK: ArrayGet 567 /// CHECK: ArrayGet 568 /// CHECK-NOT: ArrayGet 569 570 /// CHECK-START: int Main.unrollingSimpleLiveOuts(int[]) loop_optimization (before) 571 /// CHECK: ArraySet 572 /// CHECK-NOT: ArraySet 573 574 /// CHECK-START: int Main.unrollingSimpleLiveOuts(int[]) loop_optimization (after) 575 /// CHECK-DAG: <<Array:l\d+>> ParameterValue loop:none 576 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none 577 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none 578 /// CHECK-DAG: <<Const2:i\d+>> IntConstant 2 loop:none 579 /// CHECK-DAG: <<Limit:i\d+>> IntConstant 4094 loop:none 580 /// CHECK-DAG: <<PhiS:i\d+>> Phi [<<Const1>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 581 /// CHECK-DAG: <<PhiT:i\d+>> Phi [<<Const2>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 582 /// CHECK-DAG: <<PhiI:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 583 /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<PhiI>>,<<Limit>>] loop:<<Loop>> outer_loop:none 584 /// CHECK-DAG: If [<<Check>>] loop:<<Loop>> outer_loop:none 585 /// CHECK-DAG: <<AddI:i\d+>> Add [<<PhiI>>,<<Const1>>] loop:<<Loop>> outer_loop:none 586 /// CHECK-DAG: <<Get0:i\d+>> ArrayGet [<<Array>>,<<AddI>>] loop:<<Loop>> outer_loop:none 587 /// CHECK-DAG: <<AddS:i\d+>> Add [<<PhiS>>,<<Get0>>] loop:<<Loop>> outer_loop:none 588 /// CHECK-DAG: <<AddT:i\d+>> Mul [<<PhiT>>,<<Get0>>] loop:<<Loop>> outer_loop:none 589 /// CHECK-DAG: <<Get1:i\d+>> ArrayGet [<<Array>>,<<PhiI>>] loop:<<Loop>> outer_loop:none 590 /// CHECK-DAG: <<AddArr:i\d+>> Add [<<AddS>>,<<Get1>>] loop:<<Loop>> outer_loop:none 591 /// CHECK-DAG: ArraySet [<<Array>>,<<PhiI>>,<<AddArr>>] loop:<<Loop>> outer_loop:none 592 // 593 /// CHECK-DAG: GreaterThanOrEqual [<<AddI>>,<<Limit>>] loop:<<Loop>> outer_loop:none 594 /// CHECK-DAG: If [<<Const0>>] loop:<<Loop>> outer_loop:none 595 /// CHECK-DAG: <<AddIA:i\d+>> Add [<<AddI>>,<<Const1>>] loop:<<Loop>> outer_loop:none 596 /// CHECK-DAG: <<Get0A:i\d+>> ArrayGet [<<Array>>,<<AddIA>>] loop:<<Loop>> outer_loop:none 597 /// CHECK-DAG: <<AddSA:i\d+>> Add [<<AddS>>,<<Get0A>>] loop:<<Loop>> outer_loop:none 598 /// CHECK-DAG: <<AddTA:i\d+>> Mul [<<AddT>>,<<Get0A>>] loop:<<Loop>> outer_loop:none 599 /// CHECK-DAG: <<Get1A:i\d+>> ArrayGet [<<Array>>,<<AddI>>] loop:<<Loop>> outer_loop:none 600 /// CHECK-DAG: <<AddArrA:i\d+>> Add [<<AddSA>>,<<Get1A>>] loop:<<Loop>> outer_loop:none 601 /// CHECK-DAG: ArraySet [<<Array>>,<<AddI>>,<<AddArrA>>] loop:<<Loop>> outer_loop:none 602 // 603 /// CHECK-DAG: <<RetPhiS:i\d+>> Phi [<<PhiS>>,<<AddS>>] loop:none 604 /// CHECK-DAG: <<RetPhiT:i\d+>> Phi [<<PhiT>>,<<AddT>>] loop:none 605 /// CHECK-DAG: <<STAdd:i\d+>> Add [<<RetPhiS>>,<<RetPhiT>>] loop:none 606 /// CHECK-DAG: <<ZCheck:i\d+>> DivZeroCheck [<<STAdd>>] env:[[<<RetPhiS>>,<<RetPhiT>>,<<STAdd>>,<<Const1>>,_,<<Array>>]] loop:none 607 /// CHECK-DAG: <<Div:i\d+>> Div [<<Const1>>,<<ZCheck>>] loop:none 608 /// CHECK-DAG: Return [<<Div>>] loop:none 609 610 /// CHECK-START: int Main.unrollingSimpleLiveOuts(int[]) loop_optimization (after) 611 /// CHECK: ArrayGet 612 /// CHECK: ArrayGet 613 /// CHECK: ArrayGet 614 /// CHECK: ArrayGet 615 /// CHECK-NOT: ArrayGet 616 617 /// CHECK-START: int Main.unrollingSimpleLiveOuts(int[]) loop_optimization (after) 618 /// CHECK: ArraySet 619 /// CHECK: ArraySet 620 /// CHECK-NOT: ArraySet unrollingSimpleLiveOuts(int[] a)621 private static final int unrollingSimpleLiveOuts(int[] a) { 622 int s = 1; 623 int t = 2; 624 for (int i = 0; i < LENGTH - 2; i++) { 625 int temp = a[i + 1]; 626 s += temp; 627 t *= temp; 628 a[i] += s; 629 } 630 631 return 1 / (s + t); 632 } 633 634 /// CHECK-START: int Main.unrollingLiveOutsNested(int[]) loop_optimization (before) 635 /// CHECK-DAG: <<Array:l\d+>> ParameterValue loop:none 636 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none 637 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none 638 /// CHECK-DAG: <<Const2:i\d+>> IntConstant 2 loop:none 639 /// CHECK-DAG: <<Limit:i\d+>> IntConstant 4094 loop:none 640 // 641 /// CHECK-DAG: <<OutPhiJ:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop0:B\d+>> outer_loop:none 642 /// CHECK-DAG: <<OutPhiS:i\d+>> Phi [<<Const1>>,{{i\d+}}] loop:<<Loop0>> outer_loop:none 643 /// CHECK-DAG: <<OutPhiT:i\d+>> Phi [<<Const2>>,{{i\d+}}] loop:<<Loop0>> outer_loop:none 644 // 645 /// CHECK-DAG: <<PhiI:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop1:B\d+>> outer_loop:<<Loop0>> 646 /// CHECK-DAG: <<PhiS:i\d+>> Phi [<<OutPhiS>>,{{i\d+}}] loop:<<Loop1>> outer_loop:<<Loop0>> 647 /// CHECK-DAG: <<PhiT:i\d+>> Phi [<<OutPhiT>>,{{i\d+}}] loop:<<Loop1>> outer_loop:<<Loop0>> 648 /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<PhiI>>,<<Limit>>] loop:<<Loop1>> outer_loop:<<Loop0>> 649 /// CHECK-DAG: If [<<Check>>] loop:<<Loop1>> outer_loop:<<Loop0>> 650 /// CHECK-DAG: <<AddI:i\d+>> Add [<<PhiI>>,<<Const1>>] loop:<<Loop1>> outer_loop:<<Loop0>> 651 /// CHECK-DAG: <<Get0:i\d+>> ArrayGet [<<Array>>,<<AddI>>] loop:<<Loop1>> outer_loop:<<Loop0>> 652 /// CHECK-DAG: <<AddS:i\d+>> Add [<<PhiS>>,<<Get0>>] loop:<<Loop1>> outer_loop:<<Loop0>> 653 /// CHECK-DAG: <<AddT:i\d+>> Mul [<<PhiT>>,<<Get0>>] loop:<<Loop1>> outer_loop:<<Loop0>> 654 /// CHECK-DAG: <<Get1:i\d+>> ArrayGet [<<Array>>,<<PhiI>>] loop:<<Loop1>> outer_loop:<<Loop0>> 655 /// CHECK-DAG: <<AddArr:i\d+>> Add [<<AddS>>,<<Get1>>] loop:<<Loop1>> outer_loop:<<Loop0>> 656 /// CHECK-DAG: ArraySet [<<Array>>,<<PhiI>>,<<AddArr>>] loop:<<Loop1>> outer_loop:<<Loop0>> 657 // 658 /// CHECK-DAG: Add [<<OutPhiJ>>,<<Const1>>] loop:<<Loop0>> outer_loop:none 659 660 /// CHECK-START: int Main.unrollingLiveOutsNested(int[]) loop_optimization (before) 661 /// CHECK: ArrayGet 662 /// CHECK: ArrayGet 663 /// CHECK-NOT: ArrayGet 664 665 /// CHECK-START: int Main.unrollingLiveOutsNested(int[]) loop_optimization (before) 666 /// CHECK: ArraySet 667 /// CHECK-NOT: ArraySet 668 669 /// CHECK-START: int Main.unrollingLiveOutsNested(int[]) loop_optimization (after) 670 /// CHECK-DAG: <<Array:l\d+>> ParameterValue loop:none 671 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none 672 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none 673 /// CHECK-DAG: <<Const2:i\d+>> IntConstant 2 loop:none 674 /// CHECK-DAG: <<Limit:i\d+>> IntConstant 4094 loop:none 675 // 676 /// CHECK-DAG: <<OutPhiJ:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop0:B\d+>> outer_loop:none 677 /// CHECK-DAG: <<OutPhiS:i\d+>> Phi [<<Const1>>,{{i\d+}}] loop:<<Loop0>> outer_loop:none 678 /// CHECK-DAG: <<OutPhiT:i\d+>> Phi [<<Const2>>,{{i\d+}}] loop:<<Loop0>> outer_loop:none 679 // 680 /// CHECK-DAG: <<PhiI:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop1:B\d+>> outer_loop:<<Loop0>> 681 /// CHECK-DAG: <<PhiS:i\d+>> Phi [<<OutPhiS>>,{{i\d+}}] loop:<<Loop1>> outer_loop:<<Loop0>> 682 /// CHECK-DAG: <<PhiT:i\d+>> Phi [<<OutPhiT>>,{{i\d+}}] loop:<<Loop1>> outer_loop:<<Loop0>> 683 /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<PhiI>>,<<Limit>>] loop:<<Loop1>> outer_loop:<<Loop0>> 684 /// CHECK-DAG: If [<<Check>>] loop:<<Loop1>> outer_loop:<<Loop0>> 685 /// CHECK-DAG: <<AddI:i\d+>> Add [<<PhiI>>,<<Const1>>] loop:<<Loop1>> outer_loop:<<Loop0>> 686 /// CHECK-DAG: <<Get0:i\d+>> ArrayGet [<<Array>>,<<AddI>>] loop:<<Loop1>> outer_loop:<<Loop0>> 687 /// CHECK-DAG: <<AddS:i\d+>> Add [<<PhiS>>,<<Get0>>] loop:<<Loop1>> outer_loop:<<Loop0>> 688 /// CHECK-DAG: <<AddT:i\d+>> Mul [<<PhiT>>,<<Get0>>] loop:<<Loop1>> outer_loop:<<Loop0>> 689 /// CHECK-DAG: <<Get1:i\d+>> ArrayGet [<<Array>>,<<PhiI>>] loop:<<Loop1>> outer_loop:<<Loop0>> 690 /// CHECK-DAG: <<AddArr:i\d+>> Add [<<AddS>>,<<Get1>>] loop:<<Loop1>> outer_loop:<<Loop0>> 691 /// CHECK-DAG: ArraySet [<<Array>>,<<PhiI>>,<<AddArr>>] loop:<<Loop1>> outer_loop:<<Loop0>> 692 // 693 /// CHECK-DAG: If [<<Const0>>] loop:<<Loop1>> outer_loop:<<Loop0>> 694 /// CHECK-DAG: <<AddIA:i\d+>> Add [<<AddI>>,<<Const1>>] loop:<<Loop1>> outer_loop:<<Loop0>> 695 /// CHECK-DAG: <<Get0A:i\d+>> ArrayGet [<<Array>>,<<AddIA>>] loop:<<Loop1>> outer_loop:<<Loop0>> 696 /// CHECK-DAG: <<AddSA:i\d+>> Add [<<AddS>>,<<Get0A>>] loop:<<Loop1>> outer_loop:<<Loop0>> 697 /// CHECK-DAG: <<AddTA:i\d+>> Mul [<<AddT>>,<<Get0A>>] loop:<<Loop1>> outer_loop:<<Loop0>> 698 /// CHECK-DAG: <<Get1A:i\d+>> ArrayGet [<<Array>>,<<AddI>>] loop:<<Loop1>> outer_loop:<<Loop0>> 699 /// CHECK-DAG: <<AddArrA:i\d+>> Add [<<AddSA>>,<<Get1A>>] loop:<<Loop1>> outer_loop:<<Loop0>> 700 /// CHECK-DAG: ArraySet [<<Array>>,<<AddI>>,<<AddArrA>>] loop:<<Loop1>> outer_loop:<<Loop0>> 701 // 702 /// CHECK-DAG: <<RetPhiS:i\d+>> Phi [<<PhiS>>,<<AddS>>] loop:<<Loop0>> outer_loop:none 703 /// CHECK-DAG: <<RetPhiT:i\d+>> Phi [<<PhiT>>,<<AddT>>] loop:<<Loop0>> outer_loop:none 704 /// CHECK-DAG: Add [<<OutPhiJ>>,<<Const1>>] loop:<<Loop0>> outer_loop:none 705 // 706 /// CHECK-DAG: <<RetAdd:i\d+>> Add [<<OutPhiS>>,<<OutPhiT>>] loop:none 707 /// CHECK-DAG: Return [<<RetAdd>>] loop:none 708 709 /// CHECK-START: int Main.unrollingLiveOutsNested(int[]) loop_optimization (after) 710 /// CHECK: ArrayGet 711 /// CHECK: ArrayGet 712 /// CHECK: ArrayGet 713 /// CHECK: ArrayGet 714 /// CHECK-NOT: ArrayGet 715 716 /// CHECK-START: int Main.unrollingLiveOutsNested(int[]) loop_optimization (after) 717 /// CHECK: ArraySet 718 /// CHECK: ArraySet 719 /// CHECK-NOT: ArraySet unrollingLiveOutsNested(int[] a)720 private static final int unrollingLiveOutsNested(int[] a) { 721 int s = 1; 722 int t = 2; 723 for (int j = 0; j < 16; j++) { 724 for (int i = 0; i < LENGTH - 2; i++) { 725 int temp = a[i + 1]; 726 s += temp; 727 t *= temp; 728 a[i] += s; 729 } 730 } 731 return s + t; 732 } 733 734 /// CHECK-START: void Main.unrollingInstanceOf(int[], java.lang.Object[]) loop_optimization (before) 735 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none 736 /// CHECK-DAG: Phi [<<Const0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 737 /// CHECK-DAG: InstanceOf loop:<<Loop>> outer_loop:none 738 739 /// CHECK-START: void Main.unrollingInstanceOf(int[], java.lang.Object[]) loop_optimization (before) 740 /// CHECK: InstanceOf 741 /// CHECK-NOT: InstanceOf 742 743 /// CHECK-START: void Main.unrollingInstanceOf(int[], java.lang.Object[]) loop_optimization (after) 744 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none 745 /// CHECK-DAG: Phi [<<Const0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 746 /// CHECK-DAG: InstanceOf loop:<<Loop>> outer_loop:none 747 /// CHECK-DAG: InstanceOf loop:<<Loop>> outer_loop:none 748 749 /// CHECK-START: void Main.unrollingInstanceOf(int[], java.lang.Object[]) loop_optimization (after) 750 /// CHECK: InstanceOf 751 /// CHECK: InstanceOf 752 /// CHECK-NOT: InstanceOf unrollingInstanceOf(int[] a, Object[] obj_array)753 public void unrollingInstanceOf(int[] a, Object[] obj_array) { 754 for (int i = 0; i < LENGTH_B; i++) { 755 if (obj_array[i] instanceof Integer) { 756 a[i] += 1; 757 } 758 } 759 } 760 761 /// CHECK-START: void Main.unrollingDivZeroCheck(int[], int) loop_optimization (before) 762 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none 763 /// CHECK-DAG: Phi [<<Const0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 764 /// CHECK-DAG: DivZeroCheck loop:<<Loop>> outer_loop:none 765 766 /// CHECK-START: void Main.unrollingDivZeroCheck(int[], int) loop_optimization (before) 767 /// CHECK: DivZeroCheck 768 /// CHECK-NOT: DivZeroCheck 769 770 /// CHECK-START: void Main.unrollingDivZeroCheck(int[], int) loop_optimization (after) 771 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none 772 /// CHECK-DAG: Phi [<<Const0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 773 /// CHECK-DAG: DivZeroCheck loop:<<Loop>> outer_loop:none 774 /// CHECK-DAG: DivZeroCheck loop:<<Loop>> outer_loop:none 775 776 /// CHECK-START: void Main.unrollingDivZeroCheck(int[], int) loop_optimization (after) 777 /// CHECK: DivZeroCheck 778 /// CHECK: DivZeroCheck 779 /// CHECK-NOT: DivZeroCheck unrollingDivZeroCheck(int[] a, int r)780 public void unrollingDivZeroCheck(int[] a, int r) { 781 for (int i = 0; i < LENGTH_B; i++) { 782 a[i] += a[i] / r; 783 } 784 } 785 786 /// CHECK-START: void Main.unrollingTypeConversion(int[], double[]) loop_optimization (before) 787 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none 788 /// CHECK-DAG: Phi [<<Const0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 789 /// CHECK-DAG: TypeConversion loop:<<Loop>> outer_loop:none 790 791 /// CHECK-START: void Main.unrollingTypeConversion(int[], double[]) loop_optimization (before) 792 /// CHECK: TypeConversion 793 /// CHECK-NOT: TypeConversion 794 795 /// CHECK-START: void Main.unrollingTypeConversion(int[], double[]) loop_optimization (after) 796 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none 797 /// CHECK-DAG: Phi [<<Const0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 798 /// CHECK-DAG: TypeConversion loop:<<Loop>> outer_loop:none 799 /// CHECK-DAG: TypeConversion loop:<<Loop>> outer_loop:none 800 801 /// CHECK-START: void Main.unrollingTypeConversion(int[], double[]) loop_optimization (after) 802 /// CHECK: TypeConversion 803 /// CHECK: TypeConversion 804 /// CHECK-NOT: TypeConversion unrollingTypeConversion(int[] a, double[] b)805 public void unrollingTypeConversion(int[] a, double[] b) { 806 for (int i = 0; i < LENGTH_B; i++) { 807 a[i] = (int) b[i]; 808 } 809 } 810 811 interface Itf { 812 } 813 814 class SubMain extends Main implements Itf { 815 } 816 817 /// CHECK-START: void Main.unrollingCheckCast(int[], java.lang.Object) loop_optimization (before) 818 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none 819 /// CHECK-DAG: Phi [<<Const0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 820 /// CHECK-DAG: CheckCast loop:<<Loop>> outer_loop:none 821 822 /// CHECK-START: void Main.unrollingCheckCast(int[], java.lang.Object) loop_optimization (before) 823 /// CHECK: CheckCast 824 /// CHECK-NOT: CheckCast 825 826 /// CHECK-START: void Main.unrollingCheckCast(int[], java.lang.Object) loop_optimization (after) 827 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none 828 /// CHECK-DAG: Phi [<<Const0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 829 /// CHECK-DAG: CheckCast loop:<<Loop>> outer_loop:none 830 /// CHECK-DAG: CheckCast loop:<<Loop>> outer_loop:none 831 832 /// CHECK-START: void Main.unrollingCheckCast(int[], java.lang.Object) loop_optimization (after) 833 /// CHECK: CheckCast 834 /// CHECK: CheckCast 835 /// CHECK-NOT: CheckCast unrollingCheckCast(int[] a, Object o)836 public void unrollingCheckCast(int[] a, Object o) { 837 for (int i = 0; i < LENGTH_B; i++) { 838 if (((SubMain)o) == o) { 839 a[i] = i; 840 } 841 } 842 } 843 844 /// CHECK-START: void Main.noUnrollingOddTripCount(int[]) loop_optimization (before) 845 /// CHECK-DAG: <<Array:l\d+>> ParameterValue loop:none 846 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none 847 /// CHECK-DAG: <<Limit:i\d+>> IntConstant 4095 loop:none 848 /// CHECK-DAG: <<Phi:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 849 /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<Phi>>,<<Limit>>] loop:<<Loop>> outer_loop:none 850 /// CHECK-DAG: <<If:v\d+>> If [<<Check>>] loop:<<Loop>> outer_loop:none 851 /// CHECK-DAG: <<Get0:i\d+>> ArrayGet [<<Array>>,<<Phi>>] loop:<<Loop>> outer_loop:none 852 /// CHECK-DAG: <<IndAdd:i\d+>> Add [<<Phi>>,<<Const1>>] loop:<<Loop>> outer_loop:none 853 /// CHECK-DAG: <<Get1:i\d+>> ArrayGet [<<Array>>,<<IndAdd>>] loop:<<Loop>> outer_loop:none 854 /// CHECK-DAG: <<Add:i\d+>> Add [<<Get0>>,<<Get1>>] loop:<<Loop>> outer_loop:none 855 /// CHECK-DAG: ArraySet [<<Array>>,<<Phi>>,<<Add>>] loop:<<Loop>> outer_loop:none 856 857 /// CHECK-START: void Main.noUnrollingOddTripCount(int[]) loop_optimization (before) 858 /// CHECK: Phi 859 /// CHECK-NOT: Phi 860 861 /// CHECK-START: void Main.noUnrollingOddTripCount(int[]) loop_optimization (before) 862 /// CHECK: If 863 /// CHECK-NOT: If 864 865 /// CHECK-START: void Main.noUnrollingOddTripCount(int[]) loop_optimization (before) 866 /// CHECK: ArrayGet 867 /// CHECK: ArrayGet 868 /// CHECK-NOT: ArrayGet 869 870 /// CHECK-START: void Main.noUnrollingOddTripCount(int[]) loop_optimization (before) 871 /// CHECK: ArraySet 872 /// CHECK-NOT: ArraySet 873 874 /// CHECK-START: void Main.noUnrollingOddTripCount(int[]) loop_optimization (after) 875 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none 876 /// CHECK-DAG: If loop:<<Loop>> outer_loop:none 877 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 878 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 879 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none 880 881 /// CHECK-START: void Main.noUnrollingOddTripCount(int[]) loop_optimization (after) 882 /// CHECK: Phi 883 /// CHECK-NOT: Phi 884 885 /// CHECK-START: void Main.noUnrollingOddTripCount(int[]) loop_optimization (after) 886 /// CHECK: If 887 /// CHECK-NOT: If 888 889 /// CHECK-START: void Main.noUnrollingOddTripCount(int[]) loop_optimization (after) 890 /// CHECK: ArrayGet 891 /// CHECK: ArrayGet 892 /// CHECK-NOT: ArrayGet 893 894 /// CHECK-START: void Main.noUnrollingOddTripCount(int[]) loop_optimization (after) 895 /// CHECK: ArraySet 896 /// CHECK-NOT: ArraySet noUnrollingOddTripCount(int[] a)897 private static final void noUnrollingOddTripCount(int[] a) { 898 for (int i = 0; i < LENGTH - 1; i++) { 899 a[i] += a[i + 1]; 900 } 901 } 902 903 /// CHECK-START: void Main.noUnrollingNotKnownTripCount(int[], int) loop_optimization (before) 904 /// CHECK-DAG: <<Array:l\d+>> ParameterValue loop:none 905 /// CHECK-DAG: <<Limit:i\d+>> ParameterValue loop:none 906 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none 907 /// CHECK-DAG: <<Phi:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 908 /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<Phi>>,<<Limit>>] loop:<<Loop>> outer_loop:none 909 /// CHECK-DAG: <<If:v\d+>> If [<<Check>>] loop:<<Loop>> outer_loop:none 910 /// CHECK-DAG: <<Get0:i\d+>> ArrayGet [<<Array>>,<<Phi>>] loop:<<Loop>> outer_loop:none 911 /// CHECK-DAG: <<IndAdd:i\d+>> Add [<<Phi>>,<<Const1>>] loop:<<Loop>> outer_loop:none 912 /// CHECK-DAG: <<Get1:i\d+>> ArrayGet [<<Array>>,<<IndAdd>>] loop:<<Loop>> outer_loop:none 913 /// CHECK-DAG: <<Add:i\d+>> Add [<<Get0>>,<<Get1>>] loop:<<Loop>> outer_loop:none 914 /// CHECK-DAG: ArraySet [<<Array>>,<<Phi>>,<<Add>>] loop:<<Loop>> outer_loop:none 915 916 /// CHECK-START: void Main.noUnrollingNotKnownTripCount(int[], int) loop_optimization (before) 917 /// CHECK: Phi 918 /// CHECK-NOT: Phi 919 920 // One `if` for the `for` loop, and another one for a deoptimize. 921 /// CHECK-START: void Main.noUnrollingNotKnownTripCount(int[], int) loop_optimization (before) 922 /// CHECK: If 923 /// CHECK: If 924 /// CHECK-NOT: If 925 926 /// CHECK-START: void Main.noUnrollingNotKnownTripCount(int[], int) loop_optimization (before) 927 /// CHECK: ArrayGet 928 /// CHECK: ArrayGet 929 /// CHECK-NOT: ArrayGet 930 931 /// CHECK-START: void Main.noUnrollingNotKnownTripCount(int[], int) loop_optimization (before) 932 /// CHECK: ArraySet 933 /// CHECK-NOT: ArraySet 934 935 /// CHECK-START: void Main.noUnrollingNotKnownTripCount(int[], int) loop_optimization (after) 936 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none 937 /// CHECK-DAG: If loop:<<Loop>> outer_loop:none 938 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 939 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 940 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none 941 942 /// CHECK-START: void Main.noUnrollingNotKnownTripCount(int[], int) loop_optimization (after) 943 /// CHECK: Phi 944 /// CHECK-NOT: Phi 945 946 /// CHECK-START: void Main.noUnrollingNotKnownTripCount(int[], int) loop_optimization (after) 947 /// CHECK: If 948 /// CHECK: If 949 /// CHECK-NOT: If 950 951 /// CHECK-START: void Main.noUnrollingNotKnownTripCount(int[], int) loop_optimization (after) 952 /// CHECK: ArrayGet 953 /// CHECK: ArrayGet 954 /// CHECK-NOT: ArrayGet 955 956 /// CHECK-START: void Main.noUnrollingNotKnownTripCount(int[], int) loop_optimization (after) 957 /// CHECK: ArraySet 958 /// CHECK-NOT: ArraySet noUnrollingNotKnownTripCount(int[] a, int n)959 private static final void noUnrollingNotKnownTripCount(int[] a, int n) { 960 for (int i = 0; i < n; i++) { 961 a[i] += a[i + 1]; 962 } 963 } 964 965 /// CHECK-START: void Main.peelingSimple(int[], boolean) loop_optimization (before) 966 /// CHECK-DAG: <<Param:z\d+>> ParameterValue loop:none 967 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none 968 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none 969 /// CHECK-DAG: <<Limit:i\d+>> IntConstant 4096 loop:none 970 /// CHECK-DAG: <<Phi:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 971 /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<Phi>>,<<Limit>>] loop:<<Loop>> outer_loop:none 972 /// CHECK-DAG: If [<<Check>>] loop:<<Loop>> outer_loop:none 973 /// CHECK-DAG: If [<<Param>>] loop:<<Loop>> outer_loop:none 974 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 975 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none 976 /// CHECK-DAG: <<IndAdd:i\d+>> Add [<<Phi>>,<<Const1>>] loop:<<Loop>> outer_loop:none 977 978 /// CHECK-START: void Main.peelingSimple(int[], boolean) loop_optimization (before) 979 /// CHECK: If 980 /// CHECK: If 981 /// CHECK-NOT: If 982 983 /// CHECK-START: void Main.peelingSimple(int[], boolean) loop_optimization (before) 984 /// CHECK: ArraySet 985 /// CHECK-NOT: ArraySet 986 987 /// CHECK-START: void Main.peelingSimple(int[], boolean) loop_optimization (after) 988 /// CHECK-DAG: <<Param:z\d+>> ParameterValue loop:none 989 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none 990 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none 991 /// CHECK-DAG: <<Limit:i\d+>> IntConstant 4096 loop:none 992 /// CHECK-DAG: <<CheckA:z\d+>> GreaterThanOrEqual [<<Const0>>,<<Limit>>] loop:none 993 /// CHECK-DAG: If [<<CheckA>>] loop:none 994 /// CHECK-DAG: If [<<Param>>] loop:none 995 /// CHECK-DAG: ArrayGet loop:none 996 /// CHECK-DAG: ArraySet loop:none 997 /// CHECK-DAG: <<IndAddA:i\d+>> Add [<<Const0>>,<<Const1>>] loop:none 998 /// CHECK-DAG: <<Phi:i\d+>> Phi [<<IndAddA>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 999 /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<Phi>>,<<Limit>>] loop:<<Loop>> outer_loop:none 1000 /// CHECK-DAG: If [<<Check>>] loop:<<Loop>> outer_loop:none 1001 /// CHECK-DAG: If [<<Const0>>] loop:<<Loop>> outer_loop:none 1002 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 1003 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none 1004 /// CHECK-DAG: <<IndAdd:i\d+>> Add [<<Phi>>,<<Const1>>] loop:<<Loop>> outer_loop:none 1005 1006 /// CHECK-START: void Main.peelingSimple(int[], boolean) loop_optimization (after) 1007 /// CHECK: If 1008 /// CHECK: If 1009 /// CHECK: If 1010 /// CHECK: If 1011 /// CHECK-NOT: If 1012 1013 /// CHECK-START: void Main.peelingSimple(int[], boolean) loop_optimization (after) 1014 /// CHECK: ArraySet 1015 /// CHECK: ArraySet 1016 /// CHECK-NOT: ArraySet 1017 1018 /// CHECK-START: void Main.peelingSimple(int[], boolean) dead_code_elimination$before_codegen (after) 1019 /// CHECK-DAG: <<Param:z\d+>> ParameterValue loop:none 1020 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none 1021 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none 1022 /// CHECK-DAG: <<Limit:i\d+>> IntConstant 4096 loop:none 1023 /// CHECK-DAG: If [<<Param>>] loop:none 1024 /// CHECK-DAG: ArrayGet loop:none 1025 /// CHECK-DAG: ArraySet loop:none 1026 /// CHECK-DAG: <<Phi:i\d+>> Phi [<<Const1>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 1027 /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<Phi>>,<<Limit>>] loop:<<Loop>> outer_loop:none 1028 /// CHECK-DAG: If [<<Check>>] loop:<<Loop>> outer_loop:none 1029 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 1030 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none 1031 /// CHECK-DAG: <<IndAdd:i\d+>> Add [<<Phi>>,<<Const1>>] loop:<<Loop>> outer_loop:none 1032 1033 /// CHECK-START: void Main.peelingSimple(int[], boolean) dead_code_elimination$before_codegen (after) 1034 /// CHECK: GreaterThanOrEqual 1035 /// CHECK-NOT: GreaterThanOrEqual 1036 1037 /// CHECK-START: void Main.peelingSimple(int[], boolean) dead_code_elimination$before_codegen (after) 1038 /// CHECK: If 1039 /// CHECK: If 1040 /// CHECK-NOT: If 1041 1042 /// CHECK-START: void Main.peelingSimple(int[], boolean) dead_code_elimination$before_codegen (after) 1043 /// CHECK: ArrayGet 1044 /// CHECK: ArrayGet 1045 /// CHECK-NOT: ArrayGet 1046 1047 /// CHECK-START: void Main.peelingSimple(int[], boolean) dead_code_elimination$before_codegen (after) 1048 /// CHECK: ArraySet 1049 /// CHECK: ArraySet 1050 /// CHECK-NOT: ArraySet peelingSimple(int[] a, boolean f)1051 private static final void peelingSimple(int[] a, boolean f) { 1052 for (int i = 0; i < LENGTH; i++) { 1053 if (f) { 1054 break; 1055 } 1056 a[i] += 1; 1057 } 1058 } 1059 1060 // Often used idiom that, when not hoisted, prevents BCE and vectorization. 1061 // 1062 /// CHECK-START: void Main.peelingAddInts(int[]) loop_optimization (before) 1063 /// CHECK-DAG: <<Param:l\d+>> ParameterValue loop:none 1064 /// CHECK-DAG: <<ConstNull:l\d+>> NullConstant loop:none 1065 /// CHECK-DAG: <<Eq:z\d+>> Equal [<<Param>>,<<ConstNull>>] loop:none 1066 /// CHECK-DAG: <<Phi:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 1067 /// CHECK-DAG: If [<<Eq>>] loop:<<Loop>> outer_loop:none 1068 /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<Phi>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 1069 /// CHECK-DAG: If [<<Check>>] loop:<<Loop>> outer_loop:none 1070 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none 1071 1072 /// CHECK-START: void Main.peelingAddInts(int[]) dead_code_elimination$before_codegen (after) 1073 /// CHECK-DAG: <<Param:l\d+>> ParameterValue loop:none 1074 /// CHECK-DAG: <<ConstNull:l\d+>> NullConstant loop:none 1075 /// CHECK-DAG: <<Eq:z\d+>> Equal [<<Param>>,<<ConstNull>>] loop:none 1076 /// CHECK-DAG: If [<<Eq>>] loop:none 1077 /// CHECK-DAG: ArraySet loop:none 1078 /// CHECK-DAG: <<Phi:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 1079 /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<Phi>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 1080 /// CHECK-DAG: If [<<Check>>] loop:<<Loop>> outer_loop:none 1081 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none 1082 1083 // There's a 3rd `if` due to bounds checks. 1084 /// CHECK-START: void Main.peelingAddInts(int[]) dead_code_elimination$before_codegen (after) 1085 /// CHECK: If 1086 /// CHECK: If 1087 /// CHECK: If 1088 /// CHECK-NOT: If peelingAddInts(int[] a)1089 private static final void peelingAddInts(int[] a) { 1090 for (int i = 0; a != null && i < a.length; i++) { 1091 a[i] += 1; 1092 } 1093 } 1094 1095 /// CHECK-START: void Main.peelingBreakFromNest(int[], boolean) loop_optimization (before) 1096 /// CHECK-DAG: <<Param:z\d+>> ParameterValue loop:none 1097 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none 1098 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none 1099 /// CHECK-DAG: <<Limit:i\d+>> IntConstant 4096 loop:none 1100 /// CHECK-DAG: <<Phi0:i\d+>> Phi [<<Const1>>,{{i\d+}}] loop:<<Loop0:B\d+>> outer_loop:none 1101 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop1:B\d+>> outer_loop:<<Loop0>> 1102 /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<Phi1>>,<<Limit>>] loop:<<Loop1>> outer_loop:<<Loop0>> 1103 /// CHECK-DAG: If [<<Check>>] loop:<<Loop1>> outer_loop:<<Loop0>> 1104 /// CHECK-DAG: If [<<Param>>] loop:<<Loop1>> outer_loop:<<Loop0>> 1105 /// CHECK-DAG: ArrayGet loop:<<Loop1>> outer_loop:<<Loop0>> 1106 /// CHECK-DAG: ArraySet loop:<<Loop1>> outer_loop:<<Loop0>> 1107 /// CHECK-DAG: <<IndAdd1:i\d+>> Add [<<Phi1>>,<<Const1>>] loop:<<Loop1>> outer_loop:<<Loop0>> 1108 /// CHECK-DAG: <<IndAdd0:i\d+>> Add [<<Phi0>>,<<Const1>>] loop:<<Loop0>> outer_loop:none 1109 1110 // The two loops have an `if`. The 3rd `if` is the explicit one in the innermost loop. 1111 /// CHECK-START: void Main.peelingBreakFromNest(int[], boolean) loop_optimization (before) 1112 /// CHECK: If 1113 /// CHECK: If 1114 /// CHECK: If 1115 /// CHECK-NOT: If 1116 1117 /// CHECK-START: void Main.peelingBreakFromNest(int[], boolean) loop_optimization (before) 1118 /// CHECK: ArraySet 1119 /// CHECK-NOT: ArraySet 1120 1121 /// CHECK-START: void Main.peelingBreakFromNest(int[], boolean) dead_code_elimination$before_codegen (after) 1122 /// CHECK-DAG: <<Param:z\d+>> ParameterValue loop:none 1123 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none 1124 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none 1125 /// CHECK-DAG: <<Limit:i\d+>> IntConstant 4096 loop:none 1126 /// CHECK-DAG: <<Phi0:i\d+>> Phi [<<Const1>>,{{i\d+}}] loop:<<Loop0:B\d+>> outer_loop:none 1127 /// CHECK-DAG: If [<<Param>>] loop:<<Loop0>> outer_loop:none 1128 /// CHECK-DAG: ArrayGet loop:<<Loop0>> outer_loop:none 1129 /// CHECK-DAG: ArraySet loop:<<Loop0>> outer_loop:none 1130 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Const1>>,{{i\d+}}] loop:<<Loop1:B\d+>> outer_loop:<<Loop0>> 1131 /// CHECK-DAG: <<Check:z\d+>> GreaterThanOrEqual [<<Phi1>>,<<Limit>>] loop:<<Loop1>> outer_loop:<<Loop0>> 1132 /// CHECK-DAG: If [<<Check>>] loop:<<Loop1>> outer_loop:<<Loop0>> 1133 /// CHECK-DAG: ArrayGet loop:<<Loop1>> outer_loop:<<Loop0>> 1134 /// CHECK-DAG: ArraySet loop:<<Loop1>> outer_loop:<<Loop0>> 1135 /// CHECK-DAG: <<IndAdd1:i\d+>> Add [<<Phi1>>,<<Const1>>] loop:<<Loop1>> outer_loop:<<Loop0>> 1136 /// CHECK-DAG: <<IndAdd0:i\d+>> Add [<<Phi0>>,<<Const1>>] loop:<<Loop0>> outer_loop:none 1137 1138 /// CHECK-START: void Main.peelingBreakFromNest(int[], boolean) dead_code_elimination$before_codegen (after) 1139 /// CHECK: If 1140 /// CHECK: If 1141 /// CHECK: If 1142 /// CHECK-NOT: If 1143 1144 /// CHECK-START: void Main.peelingBreakFromNest(int[], boolean) dead_code_elimination$before_codegen (after) 1145 /// CHECK: ArraySet 1146 /// CHECK: ArraySet 1147 /// CHECK-NOT: ArraySet peelingBreakFromNest(int[] a, boolean f)1148 private static final void peelingBreakFromNest(int[] a, boolean f) { 1149 outer: 1150 for (int i = 1; i < 32; i++) { 1151 for (int j = 0; j < LENGTH; j++) { 1152 if (f) { 1153 break outer; 1154 } 1155 a[j] += 1; 1156 } 1157 } 1158 } 1159 1160 /// CHECK-START: int Main.peelingHoistOneControl(int) loop_optimization (before) 1161 /// CHECK-DAG: <<Param:i\d+>> ParameterValue loop:none 1162 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none 1163 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none 1164 /// CHECK-DAG: <<Check:z\d+>> NotEqual [<<Param>>,<<Const0>>] loop:none 1165 /// CHECK-DAG: <<Phi:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 1166 /// CHECK-DAG: If [<<Check>>] loop:<<Loop>> outer_loop:none 1167 /// CHECK-DAG: <<IndAdd:i\d+>> Add [<<Phi>>,<<Const1>>] loop:<<Loop>> outer_loop:none 1168 1169 /// CHECK-START: int Main.peelingHoistOneControl(int) loop_optimization (before) 1170 /// CHECK: If 1171 /// CHECK-NOT: If 1172 1173 /// CHECK-START: int Main.peelingHoistOneControl(int) dead_code_elimination$before_codegen (after) 1174 /// CHECK-DAG: <<Param:i\d+>> ParameterValue loop:none 1175 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none 1176 /// CHECK-DAG: <<Check:z\d+>> NotEqual [<<Param>>,<<Const0>>] loop:none 1177 /// CHECK-DAG: If [<<Check>>] loop:none 1178 /// CHECK-DAG: SuspendCheck loop:<<Loop:B\d+>> outer_loop:none 1179 /// CHECK-DAG: Goto loop:<<Loop>> outer_loop:none 1180 // 1181 // Check that the loop has no instruction except SuspendCheck and Goto (indefinite loop). 1182 /// CHECK-NOT: loop:<<Loop>> outer_loop:none 1183 1184 /// CHECK-START: int Main.peelingHoistOneControl(int) dead_code_elimination$before_codegen (after) 1185 /// CHECK: If 1186 /// CHECK-NOT: If 1187 1188 /// CHECK-START: int Main.peelingHoistOneControl(int) dead_code_elimination$before_codegen (after) 1189 /// CHECK-NOT: Phi 1190 1191 /// CHECK-START: int Main.peelingHoistOneControl(int) dead_code_elimination$before_codegen (after) 1192 /// CHECK-NOT: Add peelingHoistOneControl(int x)1193 private static final int peelingHoistOneControl(int x) { 1194 int i = 0; 1195 while (true) { 1196 if (x == 0) 1197 return 1; 1198 i++; 1199 } 1200 } 1201 1202 /// CHECK-START: int Main.peelingHoistOneControl(int, int) loop_optimization (before) 1203 /// CHECK-DAG: <<Phi:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 1204 /// CHECK-DAG: If loop:<<Loop>> outer_loop:none 1205 /// CHECK-DAG: If loop:<<Loop>> outer_loop:none 1206 1207 /// CHECK-START: int Main.peelingHoistOneControl(int, int) dead_code_elimination$before_codegen (after) 1208 /// CHECK-DAG: <<Phi:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 1209 /// CHECK-DAG: If loop:<<Loop>> outer_loop:none 1210 1211 // One `if` inside the loop (the one no longer invariant), two outside of it. 1212 /// CHECK-START: int Main.peelingHoistOneControl(int, int) dead_code_elimination$before_codegen (after) 1213 /// CHECK: If 1214 /// CHECK: If 1215 /// CHECK: If 1216 /// CHECK-NOT: If peelingHoistOneControl(int x, int y)1217 private static final int peelingHoistOneControl(int x, int y) { 1218 while (true) { 1219 if (x == 0) 1220 return 1; 1221 if (y == 0) // no longer invariant 1222 return 2; 1223 y--; 1224 } 1225 } 1226 1227 /// CHECK-START: int Main.peelingHoistTwoControl(int, int, int) loop_optimization (before) 1228 /// CHECK-DAG: <<Phi:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 1229 /// CHECK-DAG: If loop:<<Loop>> outer_loop:none 1230 /// CHECK-DAG: If loop:<<Loop>> outer_loop:none 1231 /// CHECK-DAG: If loop:<<Loop>> outer_loop:none 1232 1233 /// CHECK-START: int Main.peelingHoistTwoControl(int, int, int) dead_code_elimination$before_codegen (after) 1234 /// CHECK-DAG: <<Phi:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none 1235 /// CHECK-DAG: If loop:<<Loop>> outer_loop:none 1236 1237 // One `if` inside the loop (the one no longer invariant), three outside of it. 1238 /// CHECK-START: int Main.peelingHoistTwoControl(int, int, int) dead_code_elimination$before_codegen (after) 1239 /// CHECK: If 1240 /// CHECK: If 1241 /// CHECK: If 1242 /// CHECK: If 1243 /// CHECK-NOT: If peelingHoistTwoControl(int x, int y, int z)1244 private static final int peelingHoistTwoControl(int x, int y, int z) { 1245 while (true) { 1246 if (x == 0) 1247 return 1; 1248 if (y == 0) 1249 return 2; 1250 if (z == 0) // no longer invariant 1251 return 3; 1252 z--; 1253 } 1254 } 1255 1256 /// CHECK-START: void Main.unrollingFull(int[]) loop_optimization (before) 1257 /// CHECK-DAG: <<Param:l\d+>> ParameterValue loop:none 1258 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none 1259 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none 1260 /// CHECK-DAG: <<Limit:i\d+>> IntConstant 2 loop:none 1261 /// CHECK-DAG: <<Phi:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 1262 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 1263 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 1264 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none 1265 1266 /// CHECK-START: void Main.unrollingFull(int[]) loop_optimization (before) 1267 /// CHECK: ArrayGet 1268 /// CHECK: ArrayGet 1269 /// CHECK-NOT: ArrayGet 1270 1271 /// CHECK-START: void Main.unrollingFull(int[]) loop_optimization (before) 1272 /// CHECK: ArraySet 1273 /// CHECK-NOT: ArraySet 1274 1275 /// CHECK-START: void Main.unrollingFull(int[]) loop_optimization (after) 1276 /// CHECK-DAG: <<Param:l\d+>> ParameterValue loop:none 1277 /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none 1278 /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none 1279 /// CHECK-DAG: <<Limit:i\d+>> IntConstant 2 loop:none 1280 // Two peeled iterations 1281 /// CHECK-DAG: ArrayGet loop:none 1282 /// CHECK-DAG: ArrayGet loop:none 1283 /// CHECK-DAG: ArraySet loop:none 1284 /// CHECK-DAG: ArrayGet loop:none 1285 /// CHECK-DAG: ArrayGet loop:none 1286 /// CHECK-DAG: ArraySet loop:none 1287 // Loop 1288 /// CHECK-DAG: <<Phi:i\d+>> Phi [{{i\d+}},{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 1289 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 1290 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 1291 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none 1292 /// CHECK-DAG: If [<<Const1>>] loop:<<Loop>> outer_loop:none 1293 1294 /// CHECK-START: void Main.unrollingFull(int[]) loop_optimization (after) 1295 /// CHECK: ArrayGet 1296 /// CHECK: ArrayGet 1297 /// CHECK: ArrayGet 1298 /// CHECK: ArrayGet 1299 /// CHECK: ArrayGet 1300 /// CHECK: ArrayGet 1301 /// CHECK-NOT: ArrayGet 1302 1303 /// CHECK-START: void Main.unrollingFull(int[]) loop_optimization (after) 1304 /// CHECK: ArraySet 1305 /// CHECK: ArraySet 1306 /// CHECK: ArraySet 1307 /// CHECK-NOT: ArraySet unrollingFull(int[] a)1308 private static final void unrollingFull(int[] a) { 1309 for (int i = 0; i < 2; i++) { 1310 a[i] += a[i + 1]; 1311 } 1312 } 1313 expectEquals(int expected, int result)1314 private static void expectEquals(int expected, int result) { 1315 if (expected != result) { 1316 throw new Error("Expected: " + expected + ", found: " + result); 1317 } 1318 } 1319 verifyUnrolling()1320 public void verifyUnrolling() throws Exception { 1321 initIntArray(a); 1322 initIntArray(b); 1323 1324 initMatrix(mA); 1325 initMatrix(mB); 1326 initMatrix(mC); 1327 1328 int expected = 174291515; 1329 int found = 0; 1330 1331 double[] doubleArray = new double[LENGTH_B]; 1332 initDoubleArray(doubleArray); 1333 1334 unrollingInstanceOf(a, new Integer[LENGTH_B]); 1335 unrollingDivZeroCheck(a, 15); 1336 unrollingTypeConversion(a, doubleArray); 1337 unrollingCheckCast(a, new SubMain()); 1338 1339 // Call unrollingWhile(a); 1340 Class<?> c = Class.forName("PeelUnroll"); 1341 Method m = c.getMethod("unrollingWhile", Class.forName("[I")); 1342 Object[] arguments = { a }; 1343 m.invoke(null, arguments); 1344 1345 unrollingLoadStoreElimination(a); 1346 unrollingSwitch(a); 1347 unrollingSwapElements(a); 1348 unrollingRInnerproduct(mC, mA, mB, RESULT_POS, RESULT_POS); 1349 unrollingInTheNest(a, b, RESULT_POS); 1350 unrollingTwoLoopsInTheNest(a, b, RESULT_POS); 1351 1352 noUnrollingOddTripCount(b); 1353 noUnrollingNotKnownTripCount(b, 128); 1354 1355 for (int i = 0; i < LENGTH; i++) { 1356 found += a[i]; 1357 found += b[i]; 1358 } 1359 found += (int)mC[RESULT_POS][RESULT_POS]; 1360 1361 expectEquals(expected, found); 1362 } 1363 verifyPeeling()1364 public void verifyPeeling() throws Exception { 1365 expectEquals(1, peelingHoistOneControl(0)); // anything else loops 1366 expectEquals(1, peelingHoistOneControl(0, 0)); 1367 expectEquals(1, peelingHoistOneControl(0, 1)); 1368 expectEquals(2, peelingHoistOneControl(1, 0)); 1369 expectEquals(2, peelingHoistOneControl(1, 1)); 1370 expectEquals(1, peelingHoistTwoControl(0, 0, 0)); 1371 expectEquals(1, peelingHoistTwoControl(0, 0, 1)); 1372 expectEquals(1, peelingHoistTwoControl(0, 1, 0)); 1373 expectEquals(1, peelingHoistTwoControl(0, 1, 1)); 1374 expectEquals(2, peelingHoistTwoControl(1, 0, 0)); 1375 expectEquals(2, peelingHoistTwoControl(1, 0, 1)); 1376 expectEquals(3, peelingHoistTwoControl(1, 1, 0)); 1377 expectEquals(3, peelingHoistTwoControl(1, 1, 1)); 1378 1379 initIntArray(a); 1380 peelingSimple(a, false); 1381 peelingSimple(a, true); 1382 peelingAddInts(a); 1383 peelingAddInts(null); // okay 1384 peelingBreakFromNest(a, false); 1385 peelingBreakFromNest(a, true); 1386 1387 unrollingSimpleLiveOuts(a); 1388 1389 // Call unrollingWhileLiveOuts(a); 1390 Class<?> c = Class.forName("PeelUnroll"); 1391 Method m = c.getMethod("unrollingWhileLiveOuts", Class.forName("[I")); 1392 Object[] arguments = { a }; 1393 m.invoke(null, arguments); 1394 1395 unrollingLiveOutsNested(a); 1396 1397 int expected = 51565978; 1398 int found = 0; 1399 for (int i = 0; i < a.length; i++) { 1400 found += a[i]; 1401 } 1402 1403 expectEquals(expected, found); 1404 } 1405 main(String[] args)1406 public static void main(String[] args) throws Exception { 1407 Main obj = new Main(); 1408 1409 obj.verifyUnrolling(); 1410 obj.verifyPeeling(); 1411 1412 System.out.println("passed"); 1413 } 1414 } 1415