1 /* 2 * Copyright (C) 2017 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 * Tests for simple integral reductions: same type for accumulator and data. 19 */ 20 public class Main { 21 22 static final int N = 500; 23 static final int M = 100; 24 25 // 26 // Basic reductions in loops. 27 // 28 29 // TODO: vectorize these (second step of b/64091002 plan) 30 reductionByte(byte[] x)31 private static byte reductionByte(byte[] x) { 32 byte sum = 0; 33 for (int i = 0; i < x.length; i++) { 34 sum += x[i]; 35 } 36 return sum; 37 } 38 reductionShort(short[] x)39 private static short reductionShort(short[] x) { 40 short sum = 0; 41 for (int i = 0; i < x.length; i++) { 42 sum += x[i]; 43 } 44 return sum; 45 } 46 reductionChar(char[] x)47 private static char reductionChar(char[] x) { 48 char sum = 0; 49 for (int i = 0; i < x.length; i++) { 50 sum += x[i]; 51 } 52 return sum; 53 } 54 55 /// CHECK-START: int Main.reductionInt(int[]) loop_optimization (before) 56 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 57 /// CHECK-DAG: <<Cons1:i\d+>> IntConstant 1 loop:none 58 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 59 /// CHECK-DAG: <<Phi2:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 60 /// CHECK-DAG: <<Get:i\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 61 /// CHECK-DAG: Add [<<Phi2>>,<<Get>>] loop:<<Loop>> outer_loop:none 62 /// CHECK-DAG: Add [<<Phi1>>,<<Cons1>>] loop:<<Loop>> outer_loop:none 63 /// CHECK-DAG: Return [<<Phi2>>] loop:none 64 // 65 /// CHECK-START-{ARM,ARM64,MIPS64}: int Main.reductionInt(int[]) loop_optimization (after) 66 /// CHECK-DAG: <<Cons:i\d+>> IntConstant {{2|4}} loop:none 67 /// CHECK-DAG: <<Set:d\d+>> VecSetScalars [{{i\d+}}] loop:none 68 /// CHECK-DAG: <<Phi:d\d+>> Phi [<<Set>>,{{d\d+}}] loop:<<Loop:B\d+>> outer_loop:none 69 /// CHECK-DAG: <<Load:d\d+>> VecLoad [{{l\d+}},<<I:i\d+>>] loop:<<Loop>> outer_loop:none 70 /// CHECK-DAG: VecAdd [<<Phi>>,<<Load>>] loop:<<Loop>> outer_loop:none 71 /// CHECK-DAG: Add [<<I>>,<<Cons>>] loop:<<Loop>> outer_loop:none 72 /// CHECK-DAG: <<Red:d\d+>> VecReduce [<<Phi>>] loop:none 73 /// CHECK-DAG: <<Extr:i\d+>> VecExtractScalar [<<Red>>] loop:none reductionInt(int[] x)74 private static int reductionInt(int[] x) { 75 int sum = 0; 76 for (int i = 0; i < x.length; i++) { 77 sum += x[i]; 78 } 79 return sum; 80 } 81 82 /// CHECK-START: int Main.reductionIntChain() loop_optimization (before) 83 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 84 /// CHECK-DAG: <<Cons1:i\d+>> IntConstant 1 loop:none 85 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons1>>,{{i\d+}}] loop:<<Loop1:B\d+>> outer_loop:none 86 /// CHECK-DAG: <<Phi2:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop1>> outer_loop:none 87 /// CHECK-DAG: <<Get1:i\d+>> ArrayGet [{{l\d+}},<<Phi2>>] loop:<<Loop1>> outer_loop:none 88 /// CHECK-DAG: Add [<<Phi1>>,<<Get1>>] loop:<<Loop1>> outer_loop:none 89 /// CHECK-DAG: Add [<<Phi2>>,<<Cons1>>] loop:<<Loop1>> outer_loop:none 90 /// CHECK-DAG: <<Phi3:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop2:B\d+>> outer_loop:none 91 /// CHECK-DAG: <<Phi4:i\d+>> Phi [<<Phi1>>,{{i\d+}}] loop:<<Loop2>> outer_loop:none 92 /// CHECK-DAG: <<Get2:i\d+>> ArrayGet [{{l\d+}},<<Phi3>>] loop:<<Loop2>> outer_loop:none 93 /// CHECK-DAG: Add [<<Phi4>>,<<Get2>>] loop:<<Loop2>> outer_loop:none 94 /// CHECK-DAG: Add [<<Phi3>>,<<Cons1>>] loop:<<Loop2>> outer_loop:none 95 /// CHECK-DAG: Return [<<Phi4>>] loop:none 96 // 97 /// CHECK-EVAL: "<<Loop1>>" != "<<Loop2>>" 98 // 99 /// CHECK-START-{ARM,ARM64,MIPS64}: int Main.reductionIntChain() loop_optimization (after) 100 /// CHECK-DAG: <<Set1:d\d+>> VecSetScalars [{{i\d+}}] loop:none 101 /// CHECK-DAG: <<Phi1:d\d+>> Phi [<<Set1>>,{{d\d+}}] loop:<<Loop1:B\d+>> outer_loop:none 102 /// CHECK-DAG: <<Load1:d\d+>> VecLoad [{{l\d+}},<<I1:i\d+>>] loop:<<Loop1>> outer_loop:none 103 /// CHECK-DAG: VecAdd [<<Phi1>>,<<Load1>>] loop:<<Loop1>> outer_loop:none 104 /// CHECK-DAG: Add [<<I1>>,{{i\d+}}] loop:<<Loop1>> outer_loop:none 105 /// CHECK-DAG: <<Red1:d\d+>> VecReduce [<<Phi1>>] loop:none 106 /// CHECK-DAG: <<Extr1:i\d+>> VecExtractScalar [<<Red1>>] loop:none 107 /// CHECK-DAG: <<Set2:d\d+>> VecSetScalars [{{i\d+}}] loop:none 108 /// CHECK-DAG: <<Phi2:d\d+>> Phi [<<Set2>>,{{d\d+}}] loop:<<Loop2:B\d+>> outer_loop:none 109 /// CHECK-DAG: <<Load2:d\d+>> VecLoad [{{l\d+}},<<I2:i\d+>>] loop:<<Loop2>> outer_loop:none 110 /// CHECK-DAG: VecAdd [<<Phi2>>,<<Load2>>] loop:<<Loop2>> outer_loop:none 111 /// CHECK-DAG: Add [<<I2>>,{{i\d+}}] loop:<<Loop2>> outer_loop:none 112 /// CHECK-DAG: <<Red2:d\d+>> VecReduce [<<Phi2>>] loop:none 113 /// CHECK-DAG: <<Extr2:i\d+>> VecExtractScalar [<<Red2>>] loop:none 114 // 115 /// CHECK-EVAL: "<<Loop1>>" != "<<Loop2>>" 116 // 117 // NOTE: pattern is robust with respect to vector loop unrolling and peeling. reductionIntChain()118 private static int reductionIntChain() { 119 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 }; 120 int r = 1; 121 for (int i = 0; i < 16; i++) { 122 r += x[i]; 123 } 124 for (int i = 0; i < 16; i++) { 125 r += x[i]; 126 } 127 return r; 128 } 129 130 /// CHECK-START: int Main.reductionIntToLoop(int[]) loop_optimization (before) 131 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 132 /// CHECK-DAG: <<Cons1:i\d+>> IntConstant 1 loop:none 133 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop1:B\d+>> outer_loop:none 134 /// CHECK-DAG: <<Phi2:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop1>> outer_loop:none 135 /// CHECK-DAG: <<Get:i\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop1>> outer_loop:none 136 /// CHECK-DAG: Add [<<Phi2>>,<<Get>>] loop:<<Loop1>> outer_loop:none 137 /// CHECK-DAG: Add [<<Phi1>>,<<Cons1>>] loop:<<Loop1>> outer_loop:none 138 /// CHECK-DAG: <<Phi3:i\d+>> Phi [<<Phi2>>,{{i\d+}}] loop:<<Loop2:B\d+>> outer_loop:none 139 /// CHECK-DAG: <<Phi4:i\d+>> Phi [<<Phi2>>,{{i\d+}}] loop:<<Loop2>> outer_loop:none 140 // 141 /// CHECK-EVAL: "<<Loop1>>" != "<<Loop2>>" 142 // 143 /// CHECK-START-{ARM,ARM64,MIPS64}: int Main.reductionIntToLoop(int[]) loop_optimization (after) 144 /// CHECK-DAG: <<Cons:i\d+>> IntConstant {{2|4}} loop:none 145 /// CHECK-DAG: <<Set:d\d+>> VecSetScalars [{{i\d+}}] loop:none 146 /// CHECK-DAG: <<Phi:d\d+>> Phi [<<Set>>,{{d\d+}}] loop:<<Loop1:B\d+>> outer_loop:none 147 /// CHECK-DAG: <<Load:d\d+>> VecLoad [{{l\d+}},<<I:i\d+>>] loop:<<Loop1>> outer_loop:none 148 /// CHECK-DAG: VecAdd [<<Phi>>,<<Load>>] loop:<<Loop1>> outer_loop:none 149 /// CHECK-DAG: Add [<<I>>,<<Cons>>] loop:<<Loop1>> outer_loop:none 150 /// CHECK-DAG: <<Red:d\d+>> VecReduce [<<Phi>>] loop:none 151 /// CHECK-DAG: <<Extr:i\d+>> VecExtractScalar [<<Red>>] loop:none reductionIntToLoop(int[] x)152 private static int reductionIntToLoop(int[] x) { 153 int r = 0; 154 for (int i = 0; i < 8; i++) { 155 r += x[i]; 156 } 157 for (int i = r; i < 16; i++) { 158 r += i; 159 } 160 return r; 161 } 162 163 /// CHECK-START: long Main.reductionLong(long[]) loop_optimization (before) 164 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 165 /// CHECK-DAG: <<Long0:j\d+>> LongConstant 0 loop:none 166 /// CHECK-DAG: <<Cons1:i\d+>> IntConstant 1 loop:none 167 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 168 /// CHECK-DAG: <<Phi2:j\d+>> Phi [<<Long0>>,{{j\d+}}] loop:<<Loop>> outer_loop:none 169 /// CHECK-DAG: <<Get:j\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 170 /// CHECK-DAG: Add [<<Phi2>>,<<Get>>] loop:<<Loop>> outer_loop:none 171 /// CHECK-DAG: Add [<<Phi1>>,<<Cons1>>] loop:<<Loop>> outer_loop:none 172 /// CHECK-DAG: Return [<<Phi2>>] loop:none 173 // 174 /// CHECK-START-{ARM64,MIPS64}: long Main.reductionLong(long[]) loop_optimization (after) 175 /// CHECK-DAG: <<Cons2:i\d+>> IntConstant 2 loop:none 176 /// CHECK-DAG: <<Set:d\d+>> VecSetScalars [{{j\d+}}] loop:none 177 /// CHECK-DAG: <<Phi:d\d+>> Phi [<<Set>>,{{d\d+}}] loop:<<Loop:B\d+>> outer_loop:none 178 /// CHECK-DAG: <<Load:d\d+>> VecLoad [{{l\d+}},<<I:i\d+>>] loop:<<Loop>> outer_loop:none 179 /// CHECK-DAG: VecAdd [<<Phi>>,<<Load>>] loop:<<Loop>> outer_loop:none 180 /// CHECK-DAG: Add [<<I>>,<<Cons2>>] loop:<<Loop>> outer_loop:none 181 /// CHECK-DAG: <<Red:d\d+>> VecReduce [<<Phi>>] loop:none 182 /// CHECK-DAG: <<Extr:j\d+>> VecExtractScalar [<<Red>>] loop:none reductionLong(long[] x)183 private static long reductionLong(long[] x) { 184 long sum = 0; 185 for (int i = 0; i < x.length; i++) { 186 sum += x[i]; 187 } 188 return sum; 189 } 190 reductionByteM1(byte[] x)191 private static byte reductionByteM1(byte[] x) { 192 byte sum = -1; 193 for (int i = 0; i < x.length; i++) { 194 sum += x[i]; 195 } 196 return sum; 197 } 198 reductionShortM1(short[] x)199 private static short reductionShortM1(short[] x) { 200 short sum = -1; 201 for (int i = 0; i < x.length; i++) { 202 sum += x[i]; 203 } 204 return sum; 205 } 206 reductionCharM1(char[] x)207 private static char reductionCharM1(char[] x) { 208 char sum = 0xffff; 209 for (int i = 0; i < x.length; i++) { 210 sum += x[i]; 211 } 212 return sum; 213 } 214 215 /// CHECK-START: int Main.reductionIntM1(int[]) loop_optimization (before) 216 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 217 /// CHECK-DAG: <<Cons1:i\d+>> IntConstant 1 loop:none 218 /// CHECK-DAG: <<ConsM1:i\d+>> IntConstant -1 loop:none 219 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 220 /// CHECK-DAG: <<Phi2:i\d+>> Phi [<<ConsM1>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 221 /// CHECK-DAG: <<Get:i\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 222 /// CHECK-DAG: Add [<<Phi2>>,<<Get>>] loop:<<Loop>> outer_loop:none 223 /// CHECK-DAG: Add [<<Phi1>>,<<Cons1>>] loop:<<Loop>> outer_loop:none 224 /// CHECK-DAG: Return [<<Phi2>>] loop:none 225 // 226 /// CHECK-START-{ARM,ARM64,MIPS64}: int Main.reductionIntM1(int[]) loop_optimization (after) 227 /// CHECK-DAG: <<Cons:i\d+>> IntConstant {{2|4}} loop:none 228 /// CHECK-DAG: <<Set:d\d+>> VecSetScalars [{{i\d+}}] loop:none 229 /// CHECK-DAG: <<Phi:d\d+>> Phi [<<Set>>,{{d\d+}}] loop:<<Loop:B\d+>> outer_loop:none 230 /// CHECK-DAG: <<Load:d\d+>> VecLoad [{{l\d+}},<<I:i\d+>>] loop:<<Loop>> outer_loop:none 231 /// CHECK-DAG: VecAdd [<<Phi>>,<<Load>>] loop:<<Loop>> outer_loop:none 232 /// CHECK-DAG: Add [<<I>>,<<Cons>>] loop:<<Loop>> outer_loop:none 233 /// CHECK-DAG: <<Red:d\d+>> VecReduce [<<Phi>>] loop:none 234 /// CHECK-DAG: <<Extr:i\d+>> VecExtractScalar [<<Red>>] loop:none reductionIntM1(int[] x)235 private static int reductionIntM1(int[] x) { 236 int sum = -1; 237 for (int i = 0; i < x.length; i++) { 238 sum += x[i]; 239 } 240 return sum; 241 } 242 243 /// CHECK-START: long Main.reductionLongM1(long[]) loop_optimization (before) 244 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 245 /// CHECK-DAG: <<LongM1:j\d+>> LongConstant -1 loop:none 246 /// CHECK-DAG: <<Cons1:i\d+>> IntConstant 1 loop:none 247 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 248 /// CHECK-DAG: <<Phi2:j\d+>> Phi [<<LongM1>>,{{j\d+}}] loop:<<Loop>> outer_loop:none 249 /// CHECK-DAG: <<Get:j\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 250 /// CHECK-DAG: Add [<<Phi2>>,<<Get>>] loop:<<Loop>> outer_loop:none 251 /// CHECK-DAG: Add [<<Phi1>>,<<Cons1>>] loop:<<Loop>> outer_loop:none 252 /// CHECK-DAG: Return [<<Phi2>>] loop:none 253 // 254 /// CHECK-START-{ARM64,MIPS64}: long Main.reductionLongM1(long[]) loop_optimization (after) 255 /// CHECK-DAG: <<Cons2:i\d+>> IntConstant 2 loop:none 256 /// CHECK-DAG: <<Set:d\d+>> VecSetScalars [{{j\d+}}] loop:none 257 /// CHECK-DAG: <<Phi:d\d+>> Phi [<<Set>>,{{d\d+}}] loop:<<Loop:B\d+>> outer_loop:none 258 /// CHECK-DAG: <<Load:d\d+>> VecLoad [{{l\d+}},<<I:i\d+>>] loop:<<Loop>> outer_loop:none 259 /// CHECK-DAG: VecAdd [<<Phi>>,<<Load>>] loop:<<Loop>> outer_loop:none 260 /// CHECK-DAG: Add [<<I>>,<<Cons2>>] loop:<<Loop>> outer_loop:none 261 /// CHECK-DAG: <<Red:d\d+>> VecReduce [<<Phi>>] loop:none 262 /// CHECK-DAG: <<Extr:j\d+>> VecExtractScalar [<<Red>>] loop:none reductionLongM1(long[] x)263 private static long reductionLongM1(long[] x) { 264 long sum = -1L; 265 for (int i = 0; i < x.length; i++) { 266 sum += x[i]; 267 } 268 return sum; 269 } 270 reductionMinusByte(byte[] x)271 private static byte reductionMinusByte(byte[] x) { 272 byte sum = 0; 273 for (int i = 0; i < x.length; i++) { 274 sum -= x[i]; 275 } 276 return sum; 277 } 278 reductionMinusShort(short[] x)279 private static short reductionMinusShort(short[] x) { 280 short sum = 0; 281 for (int i = 0; i < x.length; i++) { 282 sum -= x[i]; 283 } 284 return sum; 285 } 286 reductionMinusChar(char[] x)287 private static char reductionMinusChar(char[] x) { 288 char sum = 0; 289 for (int i = 0; i < x.length; i++) { 290 sum -= x[i]; 291 } 292 return sum; 293 } 294 295 /// CHECK-START: int Main.reductionMinusInt(int[]) loop_optimization (before) 296 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 297 /// CHECK-DAG: <<Cons1:i\d+>> IntConstant 1 loop:none 298 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 299 /// CHECK-DAG: <<Phi2:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 300 /// CHECK-DAG: <<Get:i\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 301 /// CHECK-DAG: Sub [<<Phi2>>,<<Get>>] loop:<<Loop>> outer_loop:none 302 /// CHECK-DAG: Add [<<Phi1>>,<<Cons1>>] loop:<<Loop>> outer_loop:none 303 /// CHECK-DAG: Return [<<Phi2>>] loop:none 304 // 305 /// CHECK-START-{ARM,ARM64,MIPS64}: int Main.reductionMinusInt(int[]) loop_optimization (after) 306 /// CHECK-DAG: <<Cons:i\d+>> IntConstant {{2|4}} loop:none 307 /// CHECK-DAG: <<Set:d\d+>> VecSetScalars [{{i\d+}}] loop:none 308 /// CHECK-DAG: <<Phi:d\d+>> Phi [<<Set>>,{{d\d+}}] loop:<<Loop:B\d+>> outer_loop:none 309 /// CHECK-DAG: <<Load:d\d+>> VecLoad [{{l\d+}},<<I:i\d+>>] loop:<<Loop>> outer_loop:none 310 /// CHECK-DAG: VecSub [<<Phi>>,<<Load>>] loop:<<Loop>> outer_loop:none 311 /// CHECK-DAG: Add [<<I>>,<<Cons>>] loop:<<Loop>> outer_loop:none 312 /// CHECK-DAG: <<Red:d\d+>> VecReduce [<<Phi>>] loop:none 313 /// CHECK-DAG: <<Extr:i\d+>> VecExtractScalar [<<Red>>] loop:none reductionMinusInt(int[] x)314 private static int reductionMinusInt(int[] x) { 315 int sum = 0; 316 for (int i = 0; i < x.length; i++) { 317 sum -= x[i]; 318 } 319 return sum; 320 } 321 322 /// CHECK-START: long Main.reductionMinusLong(long[]) loop_optimization (before) 323 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 324 /// CHECK-DAG: <<Long0:j\d+>> LongConstant 0 loop:none 325 /// CHECK-DAG: <<Cons1:i\d+>> IntConstant 1 loop:none 326 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 327 /// CHECK-DAG: <<Phi2:j\d+>> Phi [<<Long0>>,{{j\d+}}] loop:<<Loop>> outer_loop:none 328 /// CHECK-DAG: <<Get:j\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 329 /// CHECK-DAG: Sub [<<Phi2>>,<<Get>>] loop:<<Loop>> outer_loop:none 330 /// CHECK-DAG: Add [<<Phi1>>,<<Cons1>>] loop:<<Loop>> outer_loop:none 331 /// CHECK-DAG: Return [<<Phi2>>] loop:none 332 // 333 /// CHECK-START-{ARM64,MIPS64}: long Main.reductionMinusLong(long[]) loop_optimization (after) 334 /// CHECK-DAG: <<Cons2:i\d+>> IntConstant 2 loop:none 335 /// CHECK-DAG: <<Set:d\d+>> VecSetScalars [{{j\d+}}] loop:none 336 /// CHECK-DAG: <<Phi:d\d+>> Phi [<<Set>>,{{d\d+}}] loop:<<Loop:B\d+>> outer_loop:none 337 /// CHECK-DAG: <<Load:d\d+>> VecLoad [{{l\d+}},<<I:i\d+>>] loop:<<Loop>> outer_loop:none 338 /// CHECK-DAG: VecSub [<<Phi>>,<<Load>>] loop:<<Loop>> outer_loop:none 339 /// CHECK-DAG: Add [<<I>>,<<Cons2>>] loop:<<Loop>> outer_loop:none 340 /// CHECK-DAG: <<Red:d\d+>> VecReduce [<<Phi>>] loop:none 341 /// CHECK-DAG: <<Extr:j\d+>> VecExtractScalar [<<Red>>] loop:none reductionMinusLong(long[] x)342 private static long reductionMinusLong(long[] x) { 343 long sum = 0; 344 for (int i = 0; i < x.length; i++) { 345 sum -= x[i]; 346 } 347 return sum; 348 } 349 reductionMinByte(byte[] x)350 private static byte reductionMinByte(byte[] x) { 351 byte min = Byte.MAX_VALUE; 352 for (int i = 0; i < x.length; i++) { 353 min = (byte) Math.min(min, x[i]); 354 } 355 return min; 356 } 357 reductionMinShort(short[] x)358 private static short reductionMinShort(short[] x) { 359 short min = Short.MAX_VALUE; 360 for (int i = 0; i < x.length; i++) { 361 min = (short) Math.min(min, x[i]); 362 } 363 return min; 364 } 365 reductionMinChar(char[] x)366 private static char reductionMinChar(char[] x) { 367 char min = Character.MAX_VALUE; 368 for (int i = 0; i < x.length; i++) { 369 min = (char) Math.min(min, x[i]); 370 } 371 return min; 372 } 373 374 /// CHECK-START: int Main.reductionMinInt(int[]) loop_optimization (before) 375 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 376 /// CHECK-DAG: <<Cons1:i\d+>> IntConstant 1 loop:none 377 /// CHECK-DAG: <<ConsM:i\d+>> IntConstant 2147483647 loop:none 378 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 379 /// CHECK-DAG: <<Phi2:i\d+>> Phi [<<ConsM>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 380 /// CHECK-DAG: <<Get:i\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 381 /// CHECK-DAG: InvokeStaticOrDirect [<<Phi2>>,<<Get>>] intrinsic:MathMinIntInt loop:<<Loop>> outer_loop:none 382 /// CHECK-DAG: Add [<<Phi1>>,<<Cons1>>] loop:<<Loop>> outer_loop:none 383 /// CHECK-DAG: Return [<<Phi2>>] loop:none 384 // 385 /// CHECK-START-{ARM,ARM64,MIPS64}: int Main.reductionMinInt(int[]) loop_optimization (after) 386 /// CHECK-DAG: <<Cons:i\d+>> IntConstant {{2|4}} loop:none 387 /// CHECK-DAG: <<Set:d\d+>> VecReplicateScalar [{{i\d+}}] loop:none 388 /// CHECK-DAG: <<Phi:d\d+>> Phi [<<Set>>,{{d\d+}}] loop:<<Loop:B\d+>> outer_loop:none 389 /// CHECK-DAG: <<Load:d\d+>> VecLoad [{{l\d+}},<<I:i\d+>>] loop:<<Loop>> outer_loop:none 390 /// CHECK-DAG: VecMin [<<Phi>>,<<Load>>] loop:<<Loop>> outer_loop:none 391 /// CHECK-DAG: Add [<<I>>,<<Cons>>] loop:<<Loop>> outer_loop:none 392 /// CHECK-DAG: <<Red:d\d+>> VecReduce [<<Phi>>] loop:none 393 /// CHECK-DAG: <<Extr:i\d+>> VecExtractScalar [<<Red>>] loop:none reductionMinInt(int[] x)394 private static int reductionMinInt(int[] x) { 395 int min = Integer.MAX_VALUE; 396 for (int i = 0; i < x.length; i++) { 397 min = Math.min(min, x[i]); 398 } 399 return min; 400 } 401 reductionMinLong(long[] x)402 private static long reductionMinLong(long[] x) { 403 long min = Long.MAX_VALUE; 404 for (int i = 0; i < x.length; i++) { 405 min = Math.min(min, x[i]); 406 } 407 return min; 408 } 409 reductionMaxByte(byte[] x)410 private static byte reductionMaxByte(byte[] x) { 411 byte max = Byte.MIN_VALUE; 412 for (int i = 0; i < x.length; i++) { 413 max = (byte) Math.max(max, x[i]); 414 } 415 return max; 416 } 417 reductionMaxShort(short[] x)418 private static short reductionMaxShort(short[] x) { 419 short max = Short.MIN_VALUE; 420 for (int i = 0; i < x.length; i++) { 421 max = (short) Math.max(max, x[i]); 422 } 423 return max; 424 } 425 reductionMaxChar(char[] x)426 private static char reductionMaxChar(char[] x) { 427 char max = Character.MIN_VALUE; 428 for (int i = 0; i < x.length; i++) { 429 max = (char) Math.max(max, x[i]); 430 } 431 return max; 432 } 433 434 /// CHECK-START: int Main.reductionMaxInt(int[]) loop_optimization (before) 435 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 436 /// CHECK-DAG: <<Cons1:i\d+>> IntConstant 1 loop:none 437 /// CHECK-DAG: <<ConsM:i\d+>> IntConstant -2147483648 loop:none 438 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 439 /// CHECK-DAG: <<Phi2:i\d+>> Phi [<<ConsM>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 440 /// CHECK-DAG: <<Get:i\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 441 /// CHECK-DAG: InvokeStaticOrDirect [<<Phi2>>,<<Get>>] intrinsic:MathMaxIntInt loop:<<Loop>> outer_loop:none 442 /// CHECK-DAG: Add [<<Phi1>>,<<Cons1>>] loop:<<Loop>> outer_loop:none 443 /// CHECK-DAG: Return [<<Phi2>>] loop:none 444 // 445 /// CHECK-START-{ARM,ARM64,MIPS64}: int Main.reductionMaxInt(int[]) loop_optimization (after) 446 /// CHECK-DAG: <<Cons:i\d+>> IntConstant {{2|4}} loop:none 447 /// CHECK-DAG: <<Set:d\d+>> VecReplicateScalar [{{i\d+}}] loop:none 448 /// CHECK-DAG: <<Phi:d\d+>> Phi [<<Set>>,{{d\d+}}] loop:<<Loop:B\d+>> outer_loop:none 449 /// CHECK-DAG: <<Load:d\d+>> VecLoad [{{l\d+}},<<I:i\d+>>] loop:<<Loop>> outer_loop:none 450 /// CHECK-DAG: VecMax [<<Phi>>,<<Load>>] loop:<<Loop>> outer_loop:none 451 /// CHECK-DAG: Add [<<I>>,<<Cons>>] loop:<<Loop>> outer_loop:none 452 /// CHECK-DAG: <<Red:d\d+>> VecReduce [<<Phi>>] loop:none 453 /// CHECK-DAG: <<Extr:i\d+>> VecExtractScalar [<<Red>>] loop:none reductionMaxInt(int[] x)454 private static int reductionMaxInt(int[] x) { 455 int max = Integer.MIN_VALUE; 456 for (int i = 0; i < x.length; i++) { 457 max = Math.max(max, x[i]); 458 } 459 return max; 460 } 461 reductionMaxLong(long[] x)462 private static long reductionMaxLong(long[] x) { 463 long max = Long.MIN_VALUE; 464 for (int i = 0; i < x.length; i++) { 465 max = Math.max(max, x[i]); 466 } 467 return max; 468 } 469 470 // 471 // A few special cases. 472 // 473 474 // TODO: consider unrolling 475 reductionInt10(int[] x)476 private static int reductionInt10(int[] x) { 477 int sum = 0; 478 // Amenable to complete unrolling. 479 for (int i = 10; i <= 10; i++) { 480 sum += x[i]; 481 } 482 return sum; 483 } 484 reductionMinusInt10(int[] x)485 private static int reductionMinusInt10(int[] x) { 486 int sum = 0; 487 // Amenable to complete unrolling. 488 for (int i = 10; i <= 10; i++) { 489 sum -= x[i]; 490 } 491 return sum; 492 } 493 reductionMinInt10(int[] x)494 private static int reductionMinInt10(int[] x) { 495 int min = Integer.MAX_VALUE; 496 // Amenable to complete unrolling. 497 for (int i = 10; i <= 10; i++) { 498 min = Math.min(min, x[i]); 499 } 500 return min; 501 } 502 reductionMaxInt10(int[] x)503 private static int reductionMaxInt10(int[] x) { 504 int max = Integer.MIN_VALUE; 505 // Amenable to complete unrolling. 506 for (int i = 10; i <= 10; i++) { 507 max = Math.max(max, x[i]); 508 } 509 return max; 510 } 511 512 // 513 // Main driver. 514 // 515 main(String[] args)516 public static void main(String[] args) { 517 byte[] xb = new byte[N]; 518 short[] xs = new short[N]; 519 char[] xc = new char[N]; 520 int[] xi = new int[N]; 521 long[] xl = new long[N]; 522 for (int i = 0, k = -17; i < N; i++, k += 3) { 523 xb[i] = (byte) k; 524 xs[i] = (short) k; 525 xc[i] = (char) k; 526 xi[i] = k; 527 xl[i] = k; 528 } 529 530 // Arrays with all positive elements. 531 byte[] xpb = new byte[M]; 532 short[] xps = new short[M]; 533 char[] xpc = new char[M]; 534 int[] xpi = new int[M]; 535 long[] xpl = new long[M]; 536 for (int i = 0, k = 3; i < M; i++, k++) { 537 xpb[i] = (byte) k; 538 xps[i] = (short) k; 539 xpc[i] = (char) k; 540 xpi[i] = k; 541 xpl[i] = k; 542 } 543 544 // Arrays with all negative elements. 545 byte[] xnb = new byte[M]; 546 short[] xns = new short[M]; 547 int[] xni = new int[M]; 548 long[] xnl = new long[M]; 549 for (int i = 0, k = -103; i < M; i++, k++) { 550 xnb[i] = (byte) k; 551 xns[i] = (short) k; 552 xni[i] = k; 553 xnl[i] = k; 554 } 555 556 // Test various reductions in loops. 557 int[] x0 = { 0, 0, 0, 0, 0, 0, 0, 0 }; 558 int[] x1 = { 0, 0, 0, 1, 0, 0, 0, 0 }; 559 int[] x2 = { 1, 1, 1, 1, 0, 0, 0, 0 }; 560 expectEquals(-74, reductionByte(xb)); 561 expectEquals(-27466, reductionShort(xs)); 562 expectEquals(38070, reductionChar(xc)); 563 expectEquals(365750, reductionInt(xi)); 564 expectEquals(273, reductionIntChain()); 565 expectEquals(120, reductionIntToLoop(x0)); 566 expectEquals(121, reductionIntToLoop(x1)); 567 expectEquals(118, reductionIntToLoop(x2)); 568 expectEquals(-1310, reductionIntToLoop(xi)); 569 expectEquals(365750L, reductionLong(xl)); 570 expectEquals(-75, reductionByteM1(xb)); 571 expectEquals(-27467, reductionShortM1(xs)); 572 expectEquals(38069, reductionCharM1(xc)); 573 expectEquals(365749, reductionIntM1(xi)); 574 expectEquals(365749L, reductionLongM1(xl)); 575 expectEquals(74, reductionMinusByte(xb)); 576 expectEquals(27466, reductionMinusShort(xs)); 577 expectEquals(27466, reductionMinusChar(xc)); 578 expectEquals(-365750, reductionMinusInt(xi)); 579 expectEquals(365750L, reductionLong(xl)); 580 expectEquals(-75, reductionByteM1(xb)); 581 expectEquals(-27467, reductionShortM1(xs)); 582 expectEquals(38069, reductionCharM1(xc)); 583 expectEquals(365749, reductionIntM1(xi)); 584 expectEquals(365749L, reductionLongM1(xl)); 585 expectEquals(74, reductionMinusByte(xb)); 586 expectEquals(27466, reductionMinusShort(xs)); 587 expectEquals(27466, reductionMinusChar(xc)); 588 expectEquals(-365750, reductionMinusInt(xi)); 589 expectEquals(-365750L, reductionMinusLong(xl)); 590 expectEquals(-128, reductionMinByte(xb)); 591 expectEquals(-17, reductionMinShort(xs)); 592 expectEquals(1, reductionMinChar(xc)); 593 expectEquals(-17, reductionMinInt(xi)); 594 expectEquals(-17L, reductionMinLong(xl)); 595 expectEquals(3, reductionMinByte(xpb)); 596 expectEquals(3, reductionMinShort(xps)); 597 expectEquals(3, reductionMinChar(xpc)); 598 expectEquals(3, reductionMinInt(xpi)); 599 expectEquals(3L, reductionMinLong(xpl)); 600 expectEquals(-103, reductionMinByte(xnb)); 601 expectEquals(-103, reductionMinShort(xns)); 602 expectEquals(-103, reductionMinInt(xni)); 603 expectEquals(-103L, reductionMinLong(xnl)); 604 expectEquals(127, reductionMaxByte(xb)); 605 expectEquals(1480, reductionMaxShort(xs)); 606 expectEquals(65534, reductionMaxChar(xc)); 607 expectEquals(1480, reductionMaxInt(xi)); 608 expectEquals(1480L, reductionMaxLong(xl)); 609 expectEquals(102, reductionMaxByte(xpb)); 610 expectEquals(102, reductionMaxShort(xps)); 611 expectEquals(102, reductionMaxChar(xpc)); 612 expectEquals(102, reductionMaxInt(xpi)); 613 expectEquals(102L, reductionMaxLong(xpl)); 614 expectEquals(-4, reductionMaxByte(xnb)); 615 expectEquals(-4, reductionMaxShort(xns)); 616 expectEquals(-4, reductionMaxInt(xni)); 617 expectEquals(-4L, reductionMaxLong(xnl)); 618 619 // Test special cases. 620 expectEquals(13, reductionInt10(xi)); 621 expectEquals(-13, reductionMinusInt10(xi)); 622 expectEquals(13, reductionMinInt10(xi)); 623 expectEquals(13, reductionMaxInt10(xi)); 624 625 System.out.println("passed"); 626 } 627 expectEquals(int expected, int result)628 private static void expectEquals(int expected, int result) { 629 if (expected != result) { 630 throw new Error("Expected: " + expected + ", found: " + result); 631 } 632 } 633 expectEquals(long expected, long result)634 private static void expectEquals(long expected, long result) { 635 if (expected != result) { 636 throw new Error("Expected: " + expected + ", found: " + result); 637 } 638 } 639 } 640