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 optimizations of break-loops, i.e. loops that break 19 * out of a while-true loop when the end condition is satisfied. 20 * In particular, the tests focus on break-loops that can be 21 * rewritten into regular countable loops (this may improve certain 22 * loops generated by the Kotlin compiler for inclusive ranges). 23 */ 24 public class Main { 25 26 /// CHECK-START: int Main.breakLoop(int[]) induction_var_analysis (before) 27 /// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none 28 /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0 loop:none 29 /// CHECK-DAG: <<One:i\d+>> IntConstant 1 loop:none 30 /// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:none 31 /// CHECK-DAG: <<Phi:i\d+>> Phi [<<Zero>>,<<AddI:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none 32 /// CHECK-DAG: <<Bnd:i\d+>> BoundsCheck [<<Phi>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 33 /// CHECK-DAG: ArraySet [<<Nil>>,<<Bnd>>,<<One>>] loop:<<Loop>> outer_loop:none 34 /// CHECK-DAG: <<NE:z\d+>> NotEqual [{{i\d+}},<<Phi>>] loop:<<Loop>> outer_loop:none 35 /// CHECK-DAG: If [<<NE>>] loop:<<Loop>> outer_loop:none 36 /// CHECK-DAG: <<AddI>> Add [<<Phi>>,<<One>>] loop:<<Loop>> outer_loop:none 37 // 38 /// CHECK-START: int Main.breakLoop(int[]) induction_var_analysis (after) 39 /// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none 40 /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0 loop:none 41 /// CHECK-DAG: <<One:i\d+>> IntConstant 1 loop:none 42 /// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:none 43 /// CHECK-DAG: <<Phi:i\d+>> Phi [<<Zero>>,<<AddI:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none 44 /// CHECK-DAG: <<LE:z\d+>> LessThanOrEqual [<<Phi>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 45 /// CHECK-DAG: If [<<LE>>] loop:<<Loop>> outer_loop:none 46 /// CHECK-DAG: <<Bnd:i\d+>> BoundsCheck [<<Phi>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 47 /// CHECK-DAG: ArraySet [<<Nil>>,<<Bnd>>,<<One>>] loop:<<Loop>> outer_loop:none 48 /// CHECK-DAG: <<AddI>> Add [<<Phi>>,<<One>>] loop:<<Loop>> outer_loop:none 49 // 50 /// CHECK-START-ARM64: int Main.breakLoop(int[]) loop_optimization (after) 51 /// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none 52 /// CHECK-DAG: <<One:i\d+>> IntConstant 1 loop:none 53 /// CHECK-DAG: <<Four:i\d+>> IntConstant 4 loop:none 54 /// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:none 55 /// CHECK-DAG: <<Rep:d\d+>> VecReplicateScalar [<<One>>] loop:none 56 /// CHECK-DAG: VecStore [<<Nil>>,<<Phi:i\d+>>,<<Rep>>] loop:<<Loop:B\d+>> outer_loop:none 57 /// CHECK-DAG: Add [<<Phi>>,<<Four>>] loop:<<Loop>> outer_loop:none breakLoop(int[] a)58 static int breakLoop(int[] a) { 59 int l = 0; 60 int u = a.length - 1; 61 int i = l; 62 if (l <= u) { 63 while (true) { 64 a[i] = 1; 65 if (i == u) break; 66 i++; 67 } 68 } 69 return i; 70 } 71 72 /// CHECK-START: int Main.breakLoopDown(int[]) induction_var_analysis (before) 73 /// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none 74 /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0 loop:none 75 /// CHECK-DAG: <<MOne:i\d+>> IntConstant -1 loop:none 76 /// CHECK-DAG: <<Two:i\d+>> IntConstant 2 loop:none 77 /// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:none 78 /// CHECK-DAG: <<Phi:i\d+>> Phi [{{i\d+}},<<AddI:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none 79 /// CHECK-DAG: <<Bnd:i\d+>> BoundsCheck [<<Phi>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 80 /// CHECK-DAG: ArraySet [<<Nil>>,<<Bnd>>,<<Two>>] loop:<<Loop>> outer_loop:none 81 /// CHECK-DAG: <<NE:z\d+>> NotEqual [<<Phi>>,<<Zero>>] loop:<<Loop>> outer_loop:none 82 /// CHECK-DAG: If [<<NE>>] loop:<<Loop>> outer_loop:none 83 /// CHECK-DAG: <<AddI>> Add [<<Phi>>,<<MOne>>] loop:<<Loop>> outer_loop:none 84 // 85 /// CHECK-START: int Main.breakLoopDown(int[]) induction_var_analysis (after) 86 /// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none 87 /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0 loop:none 88 /// CHECK-DAG: <<MOne:i\d+>> IntConstant -1 loop:none 89 /// CHECK-DAG: <<Two:i\d+>> IntConstant 2 loop:none 90 /// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:none 91 /// CHECK-DAG: <<Phi:i\d+>> Phi [{{i\d+}},<<AddI:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none 92 /// CHECK-DAG: <<GE:z\d+>> GreaterThanOrEqual [<<Phi>>,<<Zero>>] loop:<<Loop>> outer_loop:none 93 /// CHECK-DAG: If [<<GE>>] loop:<<Loop>> outer_loop:none 94 /// CHECK-DAG: <<Bnd:i\d+>> BoundsCheck [<<Phi>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 95 /// CHECK-DAG: ArraySet [<<Nil>>,<<Bnd>>,<<Two>>] loop:<<Loop>> outer_loop:none 96 /// CHECK-DAG: <<AddI>> Add [<<Phi>>,<<MOne>>] loop:<<Loop>> outer_loop:none breakLoopDown(int[] a)97 static int breakLoopDown(int[] a) { 98 int l = 0; 99 int u = a.length - 1; 100 int i = u; 101 if (u >= l) { 102 while (true) { 103 a[i] = 2; 104 if (i == l) break; 105 i--; 106 } 107 } 108 return i; 109 } 110 111 /// CHECK-START: int Main.breakLoopSafeConst(int[]) induction_var_analysis (before) 112 /// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none 113 /// CHECK-DAG: <<One:i\d+>> IntConstant 1 loop:none 114 /// CHECK-DAG: <<Three:i\d+>> IntConstant 3 loop:none 115 /// CHECK-DAG: <<L1:i\d+>> IntConstant 2147483631 loop:none 116 /// CHECK-DAG: <<L2:i\d+>> IntConstant 2147483646 loop:none 117 /// CHECK-DAG: <<Phi:i\d+>> Phi [<<L1>>,<<AddI:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none 118 /// CHECK-DAG: <<Sub:i\d+>> Sub [<<Phi>>,<<L1>>] loop:<<Loop>> outer_loop:none 119 /// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:<<Loop>> outer_loop:none 120 /// CHECK-DAG: <<Bnd:i\d+>> BoundsCheck [<<Sub>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 121 /// CHECK-DAG: ArraySet [<<Nil>>,<<Bnd>>,<<Three>>] loop:<<Loop>> outer_loop:none 122 /// CHECK-DAG: <<NE:z\d+>> NotEqual [<<Phi>>,<<L2>>] loop:<<Loop>> outer_loop:none 123 /// CHECK-DAG: If [<<NE>>] loop:<<Loop>> outer_loop:none 124 /// CHECK-DAG: <<AddI>> Add [<<Phi>>,<<One>>] loop:<<Loop>> outer_loop:none 125 // 126 /// CHECK-START: int Main.breakLoopSafeConst(int[]) induction_var_analysis (after) 127 /// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none 128 /// CHECK-DAG: <<One:i\d+>> IntConstant 1 loop:none 129 /// CHECK-DAG: <<Three:i\d+>> IntConstant 3 loop:none 130 /// CHECK-DAG: <<L1:i\d+>> IntConstant 2147483631 loop:none 131 /// CHECK-DAG: <<L2:i\d+>> IntConstant 2147483646 loop:none 132 /// CHECK-DAG: <<Phi:i\d+>> Phi [<<L1>>,<<AddI:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none 133 /// CHECK-DAG: <<LE:z\d+>> LessThanOrEqual [<<Phi>>,<<L2>>] loop:<<Loop>> outer_loop:none 134 /// CHECK-DAG: <<Sub:i\d+>> Sub [<<Phi>>,<<L1>>] loop:<<Loop>> outer_loop:none 135 /// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:<<Loop>> outer_loop:none 136 /// CHECK-DAG: <<Bnd:i\d+>> BoundsCheck [<<Sub>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 137 /// CHECK-DAG: ArraySet [<<Nil>>,<<Bnd>>,<<Three>>] loop:<<Loop>> outer_loop:none 138 /// CHECK-DAG: <<AddI>> Add [<<Phi>>,<<One>>] loop:<<Loop>> outer_loop:none 139 // 140 /// CHECK-START-ARM64: int Main.breakLoopSafeConst(int[]) loop_optimization (after) 141 /// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none 142 /// CHECK-DAG: <<One:i\d+>> IntConstant 1 loop:none 143 /// CHECK-DAG: <<Three:i\d+>> IntConstant 3 loop:none 144 /// CHECK-DAG: <<Four:i\d+>> IntConstant 4 loop:none 145 /// CHECK-DAG: <<Rep:d\d+>> VecReplicateScalar [<<Three>>] loop:none 146 /// CHECK-DAG: VecStore [<<Par>>,<<Phi:i\d+>>,<<Rep>>] loop:<<Loop:B\d+>> outer_loop:none 147 /// CHECK-DAG: Add [<<Phi>>,<<Four>>] loop:<<Loop>> outer_loop:none breakLoopSafeConst(int[] a)148 static int breakLoopSafeConst(int[] a) { 149 int l = Integer.MAX_VALUE - 16; 150 int u = Integer.MAX_VALUE - 1; 151 int i = l; 152 if (l <= u) { // will be removed by simplifier 153 while (true) { 154 a[i - l] = 3; 155 if (i == u) break; 156 i++; 157 } 158 } 159 return i; 160 } 161 162 /// CHECK-START: int Main.breakLoopUnsafeConst(int[]) induction_var_analysis (before) 163 /// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none 164 /// CHECK-DAG: <<One:i\d+>> IntConstant 1 loop:none 165 /// CHECK-DAG: <<Four:i\d+>> IntConstant 4 loop:none 166 /// CHECK-DAG: <<L1:i\d+>> IntConstant 2147483632 loop:none 167 /// CHECK-DAG: <<L2:i\d+>> IntConstant 2147483647 loop:none 168 /// CHECK-DAG: <<Phi:i\d+>> Phi [<<L1>>,<<AddI:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none 169 /// CHECK-DAG: <<Sub:i\d+>> Sub [<<Phi>>,<<L1>>] loop:<<Loop>> outer_loop:none 170 /// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:<<Loop>> outer_loop:none 171 /// CHECK-DAG: <<Bnd:i\d+>> BoundsCheck [<<Sub>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 172 /// CHECK-DAG: ArraySet [<<Nil>>,<<Bnd>>,<<Four>>] loop:<<Loop>> outer_loop:none 173 /// CHECK-DAG: <<NE:z\d+>> NotEqual [<<Phi>>,<<L2>>] loop:<<Loop>> outer_loop:none 174 /// CHECK-DAG: If [<<NE>>] loop:<<Loop>> outer_loop:none 175 /// CHECK-DAG: <<AddI>> Add [<<Phi>>,<<One>>] loop:<<Loop>> outer_loop:none 176 // 177 /// CHECK-START: int Main.breakLoopUnsafeConst(int[]) induction_var_analysis (after) 178 /// CHECK-DAG: NotEqual 179 /// CHECK-NOT: LessThanOrEqual breakLoopUnsafeConst(int[] a)180 static int breakLoopUnsafeConst(int[] a) { 181 int l = Integer.MAX_VALUE - 15; 182 int u = Integer.MAX_VALUE; 183 int i = l; 184 if (l <= u) { // will be removed by simplifier 185 while (true) { 186 a[i - l] = 4; 187 if (i == u) break; // rewriting exit not safe! 188 i++; 189 } 190 } 191 return i; 192 } 193 194 /// CHECK-START: int Main.breakLoopNastyPhi(int[]) induction_var_analysis (before) 195 /// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none 196 /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0 loop:none 197 /// CHECK-DAG: <<One:i\d+>> IntConstant 1 loop:none 198 /// CHECK-DAG: <<Five:i\d+>> IntConstant 5 loop:none 199 /// CHECK-DAG: <<M123:i\d+>> IntConstant -123 loop:none 200 /// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:none 201 /// CHECK-DAG: <<Phi:i\d+>> Phi [<<Zero>>,<<AddI:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none 202 /// CHECK-DAG: <<Wrap:i\d+>> Phi [<<M123>>,<<Phi>>] loop:<<Loop>> outer_loop:none 203 /// CHECK-DAG: <<Bnd:i\d+>> BoundsCheck [<<Phi>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 204 /// CHECK-DAG: ArraySet [<<Nil>>,<<Bnd>>,<<Five>>] loop:<<Loop>> outer_loop:none 205 /// CHECK-DAG: <<NE:z\d+>> NotEqual [{{i\d+}},<<Phi>>] loop:<<Loop>> outer_loop:none 206 /// CHECK-DAG: If [<<NE>>] loop:<<Loop>> outer_loop:none 207 /// CHECK-DAG: <<AddI>> Add [<<Phi>>,<<One>>] loop:<<Loop>> outer_loop:none 208 /// CHECK-DAG: <<Comb:i\d+>> Phi [<<M123>>,<<Wrap>>] loop:none 209 /// CHECK-DAG: Return [<<Comb>>] loop:none 210 // 211 /// CHECK-START: int Main.breakLoopNastyPhi(int[]) induction_var_analysis (after) 212 /// CHECK-DAG: NotEqual 213 /// CHECK-NOT: LessThanOrEqual breakLoopNastyPhi(int[] a)214 static int breakLoopNastyPhi(int[] a) { 215 int l = 0; 216 int u = a.length - 1; 217 int x = -123; 218 if (l <= u) { 219 int i = l; 220 while (true) { 221 a[i] = 5; 222 if (i == u) break; 223 x = i; 224 i++; 225 } 226 } 227 return x; // keep another phi live 228 } 229 230 /// CHECK-START: int Main.breakLoopReduction(int[]) induction_var_analysis (before) 231 /// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none 232 /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0 loop:none 233 /// CHECK-DAG: <<One:i\d+>> IntConstant 1 loop:none 234 /// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:none 235 /// CHECK-DAG: <<Red:i\d+>> Phi [<<Zero>>,<<RedI:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none 236 /// CHECK-DAG: <<Phi:i\d+>> Phi [<<Zero>>,<<AddI:i\d+>>] loop:<<Loop>> outer_loop:none 237 /// CHECK-DAG: <<Bnd:i\d+>> BoundsCheck [<<Phi>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 238 /// CHECK-DAG: <<Get:i\d+>> ArrayGet [<<Nil>>,<<Bnd>>] loop:<<Loop>> outer_loop:none 239 /// CHECK-DAG: <<RedI>> Add [<<Red>>,<<Get>>] loop:<<Loop>> outer_loop:none 240 /// CHECK-DAG: <<NE:z\d+>> NotEqual [{{i\d+}},<<Phi>>] loop:<<Loop>> outer_loop:none 241 /// CHECK-DAG: If [<<NE>>] loop:<<Loop>> outer_loop:none 242 /// CHECK-DAG: <<AddI>> Add [<<Phi>>,<<One>>] loop:<<Loop>> outer_loop:none 243 /// CHECK-DAG: <<Comb:i\d+>> Phi [<<Zero>>,<<RedI>>] loop:none 244 /// CHECK-DAG: Return [<<Comb>>] loop:none 245 // 246 /// CHECK-START: int Main.breakLoopReduction(int[]) induction_var_analysis (after) 247 /// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none 248 /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0 loop:none 249 /// CHECK-DAG: <<One:i\d+>> IntConstant 1 loop:none 250 /// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:none 251 /// CHECK-DAG: <<Red:i\d+>> Phi [<<Zero>>,<<RedI:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none 252 /// CHECK-DAG: <<Phi:i\d+>> Phi [<<Zero>>,<<AddI:i\d+>>] loop:<<Loop>> outer_loop:none 253 /// CHECK-DAG: <<LE:z\d+>> LessThanOrEqual [<<Phi>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 254 /// CHECK-DAG: If [<<LE>>] loop:<<Loop>> outer_loop:none 255 /// CHECK-DAG: <<Bnd:i\d+>> BoundsCheck [<<Phi>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 256 /// CHECK-DAG: <<Get:i\d+>> ArrayGet [<<Nil>>,<<Bnd>>] loop:<<Loop>> outer_loop:none 257 /// CHECK-DAG: <<RedI>> Add [<<Red>>,<<Get>>] loop:<<Loop>> outer_loop:none 258 /// CHECK-DAG: <<AddI>> Add [<<Phi>>,<<One>>] loop:<<Loop>> outer_loop:none 259 /// CHECK-DAG: <<Comb:i\d+>> Phi [<<Zero>>,<<Red>>] loop:none 260 /// CHECK-DAG: Return [<<Comb>>] loop:none 261 // 262 /// CHECK-START-ARM64: int Main.breakLoopReduction(int[]) loop_optimization (after) 263 /// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none 264 /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0 loop:none 265 /// CHECK-DAG: <<Exp:d\d+>> VecSetScalars [<<Zero>>] loop:none 266 /// CHECK-DAG: <<VPhi:d\d+>> Phi [<<Exp>>,<<VAdd:d\d+>>] loop:<<Loop:B\d+>> outer_loop:none 267 /// CHECK-DAG: <<VLoad:d\d+>> VecLoad loop:<<Loop>> outer_loop:none 268 /// CHECK-DAG: <<VAdd>> VecAdd [<<VPhi>>,<<VLoad>>] loop:<<Loop>> outer_loop:none breakLoopReduction(int[] a)269 static int breakLoopReduction(int[] a) { 270 int l = 0; 271 int u = a.length - 1; 272 int x = 0; 273 if (l <= u) { 274 int i = l; 275 while (true) { 276 x += a[i]; 277 if (i == u) break; 278 i++; 279 } 280 } 281 return x; 282 } 283 284 // 285 // Test driver. 286 // 287 main(String[] args)288 public static void main(String[] args) { 289 int[] a = new int[100]; 290 291 expectEquals(99, breakLoop(a)); 292 for (int i = 0; i < a.length; i++) { 293 expectEquals(1, a[i]); 294 } 295 296 expectEquals(0, breakLoopDown(a)); 297 for (int i = 0; i < a.length; i++) { 298 expectEquals(2, a[i]); 299 } 300 301 expectEquals(Integer.MAX_VALUE - 1, breakLoopSafeConst(a)); 302 for (int i = 0; i < a.length; i++) { 303 int e = i < 16 ? 3 : 2; 304 expectEquals(e, a[i]); 305 } 306 307 expectEquals(Integer.MAX_VALUE, breakLoopUnsafeConst(a)); 308 for (int i = 0; i < a.length; i++) { 309 int e = i < 16 ? 4 : 2; 310 expectEquals(e, a[i]); 311 } 312 313 expectEquals(98, breakLoopNastyPhi(a)); 314 for (int i = 0; i < a.length; i++) { 315 expectEquals(5, a[i]); 316 } 317 318 expectEquals(500, breakLoopReduction(a)); 319 320 System.out.println("passed"); 321 } 322 323 private static void expectEquals(int expected, int result) { 324 if (expected != result) { 325 throw new Error("Expected: " + expected + ", found: " + result); 326 } 327 } 328 } 329