Nicolas Geoffray | 82091da | 2015-01-26 10:02:45 +0000 | [diff] [blame] | 1 | /* |
Roland Levillain | 6a92a03 | 2015-07-23 12:15:01 +0100 | [diff] [blame] | 2 | * Copyright (C) 2015 The Android Open Source Project |
| 3 | * |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
Nicolas Geoffray | 82091da | 2015-01-26 10:02:45 +0000 | [diff] [blame] | 16 | |
| 17 | public class Main { |
Mingyao Yang | 217eb06 | 2017-12-11 15:20:07 -0800 | [diff] [blame] | 18 | static class Dummy { |
| 19 | static int getValue() { |
| 20 | return 1; |
| 21 | } |
| 22 | } |
Nicolas Geoffray | 82091da | 2015-01-26 10:02:45 +0000 | [diff] [blame] | 23 | |
David Brazdil | a06d66a | 2015-05-28 11:14:54 +0100 | [diff] [blame] | 24 | /// CHECK-START: int Main.div() licm (before) |
| 25 | /// CHECK-DAG: Div loop:{{B\d+}} |
Nicolas Geoffray | 82091da | 2015-01-26 10:02:45 +0000 | [diff] [blame] | 26 | |
David Brazdil | a06d66a | 2015-05-28 11:14:54 +0100 | [diff] [blame] | 27 | /// CHECK-START: int Main.div() licm (after) |
| 28 | /// CHECK-NOT: Div loop:{{B\d+}} |
Nicolas Geoffray | 82091da | 2015-01-26 10:02:45 +0000 | [diff] [blame] | 29 | |
David Brazdil | a06d66a | 2015-05-28 11:14:54 +0100 | [diff] [blame] | 30 | /// CHECK-START: int Main.div() licm (after) |
| 31 | /// CHECK-DAG: Div loop:none |
Nicolas Geoffray | 82091da | 2015-01-26 10:02:45 +0000 | [diff] [blame] | 32 | |
| 33 | public static int div() { |
| 34 | int result = 0; |
| 35 | for (int i = 0; i < 10; ++i) { |
| 36 | result += staticField / 42; |
| 37 | } |
| 38 | return result; |
| 39 | } |
| 40 | |
David Brazdil | a06d66a | 2015-05-28 11:14:54 +0100 | [diff] [blame] | 41 | /// CHECK-START: int Main.innerDiv() licm (before) |
| 42 | /// CHECK-DAG: Div loop:{{B\d+}} |
Nicolas Geoffray | 82091da | 2015-01-26 10:02:45 +0000 | [diff] [blame] | 43 | |
David Brazdil | a06d66a | 2015-05-28 11:14:54 +0100 | [diff] [blame] | 44 | /// CHECK-START: int Main.innerDiv() licm (after) |
| 45 | /// CHECK-NOT: Div loop:{{B\d+}} |
Nicolas Geoffray | 82091da | 2015-01-26 10:02:45 +0000 | [diff] [blame] | 46 | |
David Brazdil | a06d66a | 2015-05-28 11:14:54 +0100 | [diff] [blame] | 47 | /// CHECK-START: int Main.innerDiv() licm (after) |
| 48 | /// CHECK-DAG: Div loop:none |
Nicolas Geoffray | 82091da | 2015-01-26 10:02:45 +0000 | [diff] [blame] | 49 | |
| 50 | public static int innerDiv() { |
| 51 | int result = 0; |
| 52 | for (int i = 0; i < 10; ++i) { |
| 53 | for (int j = 0; j < 10; ++j) { |
| 54 | result += staticField / 42; |
| 55 | } |
| 56 | } |
| 57 | return result; |
| 58 | } |
| 59 | |
Aart Bik | 5d75afe | 2015-12-14 11:57:01 -0800 | [diff] [blame] | 60 | /// CHECK-START: int Main.innerMul() licm (before) |
David Brazdil | a06d66a | 2015-05-28 11:14:54 +0100 | [diff] [blame] | 61 | /// CHECK-DAG: Mul loop:B4 |
Nicolas Geoffray | 82091da | 2015-01-26 10:02:45 +0000 | [diff] [blame] | 62 | |
Aart Bik | 5d75afe | 2015-12-14 11:57:01 -0800 | [diff] [blame] | 63 | /// CHECK-START: int Main.innerMul() licm (after) |
David Brazdil | a06d66a | 2015-05-28 11:14:54 +0100 | [diff] [blame] | 64 | /// CHECK-DAG: Mul loop:B2 |
Nicolas Geoffray | 82091da | 2015-01-26 10:02:45 +0000 | [diff] [blame] | 65 | |
Aart Bik | 5d75afe | 2015-12-14 11:57:01 -0800 | [diff] [blame] | 66 | public static int innerMul() { |
Nicolas Geoffray | 82091da | 2015-01-26 10:02:45 +0000 | [diff] [blame] | 67 | int result = 0; |
| 68 | for (int i = 0; i < 10; ++i) { |
| 69 | for (int j = 0; j < 10; ++j) { |
| 70 | // The operation has been hoisted out of the inner loop. |
| 71 | // Note that we depend on the compiler's block numbering to |
| 72 | // check if it has been moved. |
| 73 | result += staticField * i; |
| 74 | } |
| 75 | } |
| 76 | return result; |
| 77 | } |
| 78 | |
Aart Bik | 5d75afe | 2015-12-14 11:57:01 -0800 | [diff] [blame] | 79 | /// CHECK-START: int Main.divByA(int, int) licm (before) |
David Brazdil | a06d66a | 2015-05-28 11:14:54 +0100 | [diff] [blame] | 80 | /// CHECK-DAG: Div loop:{{B\d+}} |
Nicolas Geoffray | 82091da | 2015-01-26 10:02:45 +0000 | [diff] [blame] | 81 | |
Aart Bik | 5d75afe | 2015-12-14 11:57:01 -0800 | [diff] [blame] | 82 | /// CHECK-START: int Main.divByA(int, int) licm (after) |
David Brazdil | a06d66a | 2015-05-28 11:14:54 +0100 | [diff] [blame] | 83 | /// CHECK-DAG: Div loop:{{B\d+}} |
Nicolas Geoffray | 82091da | 2015-01-26 10:02:45 +0000 | [diff] [blame] | 84 | |
Aart Bik | 5d75afe | 2015-12-14 11:57:01 -0800 | [diff] [blame] | 85 | public static int divByA(int a, int b) { |
Nicolas Geoffray | 82091da | 2015-01-26 10:02:45 +0000 | [diff] [blame] | 86 | int result = 0; |
| 87 | while (b < 5) { |
| 88 | // a might be null, so we can't hoist the operation. |
| 89 | result += staticField / a; |
| 90 | b++; |
| 91 | } |
| 92 | return result; |
| 93 | } |
| 94 | |
David Brazdil | a06d66a | 2015-05-28 11:14:54 +0100 | [diff] [blame] | 95 | /// CHECK-START: int Main.arrayLength(int[]) licm (before) |
| 96 | /// CHECK-DAG: <<NullCheck:l\d+>> NullCheck loop:{{B\d+}} |
| 97 | /// CHECK-DAG: ArrayLength [<<NullCheck>>] loop:{{B\d+}} |
Nicolas Geoffray | 82091da | 2015-01-26 10:02:45 +0000 | [diff] [blame] | 98 | |
David Brazdil | a06d66a | 2015-05-28 11:14:54 +0100 | [diff] [blame] | 99 | /// CHECK-START: int Main.arrayLength(int[]) licm (after) |
| 100 | /// CHECK-NOT: NullCheck loop:{{B\d+}} |
| 101 | /// CHECK-NOT: ArrayLength loop:{{B\d+}} |
Nicolas Geoffray | 82091da | 2015-01-26 10:02:45 +0000 | [diff] [blame] | 102 | |
David Brazdil | a06d66a | 2015-05-28 11:14:54 +0100 | [diff] [blame] | 103 | /// CHECK-START: int Main.arrayLength(int[]) licm (after) |
| 104 | /// CHECK-DAG: <<NullCheck:l\d+>> NullCheck loop:none |
| 105 | /// CHECK-DAG: ArrayLength [<<NullCheck>>] loop:none |
Nicolas Geoffray | 82091da | 2015-01-26 10:02:45 +0000 | [diff] [blame] | 106 | |
| 107 | public static int arrayLength(int[] array) { |
| 108 | int result = 0; |
| 109 | for (int i = 0; i < array.length; ++i) { |
| 110 | result += array[i]; |
| 111 | } |
| 112 | return result; |
| 113 | } |
| 114 | |
Mingyao Yang | 217eb06 | 2017-12-11 15:20:07 -0800 | [diff] [blame] | 115 | /// CHECK-START: int Main.clinitCheck() licm (before) |
| 116 | /// CHECK-DAG: <<LoadClass:l\d+>> LoadClass loop:<<Loop:B\d+>> |
| 117 | /// CHECK-DAG: ClinitCheck [<<LoadClass>>] loop:<<Loop>> |
| 118 | |
| 119 | /// CHECK-START: int Main.clinitCheck() licm (after) |
| 120 | /// CHECK-NOT: LoadClass loop:{{B\d+}} |
| 121 | /// CHECK-NOT: ClinitCheck loop:{{B\d+}} |
| 122 | |
| 123 | /// CHECK-START: int Main.clinitCheck() licm (after) |
| 124 | /// CHECK-DAG: <<LoadClass:l\d+>> LoadClass loop:none |
| 125 | /// CHECK-DAG: ClinitCheck [<<LoadClass>>] loop:none |
| 126 | |
| 127 | public static int clinitCheck() { |
| 128 | int i = 0; |
| 129 | int sum = 0; |
| 130 | do { |
| 131 | sum += Dummy.getValue(); |
| 132 | i++; |
| 133 | } while (i < 10); |
| 134 | return sum; |
| 135 | } |
| 136 | |
Aart Bik | 5d75afe | 2015-12-14 11:57:01 -0800 | [diff] [blame] | 137 | /// CHECK-START: int Main.divAndIntrinsic(int[]) licm (before) |
| 138 | /// CHECK-DAG: Div loop:{{B\d+}} |
| 139 | |
| 140 | /// CHECK-START: int Main.divAndIntrinsic(int[]) licm (after) |
| 141 | /// CHECK-NOT: Div loop:{{B\d+}} |
| 142 | |
| 143 | /// CHECK-START: int Main.divAndIntrinsic(int[]) licm (after) |
| 144 | /// CHECK-DAG: Div loop:none |
| 145 | |
| 146 | public static int divAndIntrinsic(int[] array) { |
| 147 | int result = 0; |
| 148 | for (int i = 0; i < array.length; i++) { |
| 149 | // An intrinsic call, unlike a general method call, cannot modify the field value. |
| 150 | // As a result, the invariant division on the field can be moved out of the loop. |
| 151 | result += (staticField / 42) + Math.abs(array[i]); |
| 152 | } |
| 153 | return result; |
| 154 | } |
| 155 | |
Aart Bik | 3dad341 | 2018-02-28 12:01:46 -0800 | [diff] [blame^] | 156 | |
| 157 | /// CHECK-START: int Main.invariantBoundIntrinsic(int) instruction_simplifier (before) |
Aart Bik | 5d75afe | 2015-12-14 11:57:01 -0800 | [diff] [blame] | 158 | /// CHECK-DAG: InvokeStaticOrDirect loop:{{B\d+}} |
Aart Bik | 3dad341 | 2018-02-28 12:01:46 -0800 | [diff] [blame^] | 159 | // |
| 160 | /// CHECK-START: int Main.invariantBoundIntrinsic(int) licm (before) |
| 161 | /// CHECK-DAG: Abs loop:{{B\d+}} |
Aart Bik | 5d75afe | 2015-12-14 11:57:01 -0800 | [diff] [blame] | 162 | |
| 163 | /// CHECK-START: int Main.invariantBoundIntrinsic(int) licm (after) |
Aart Bik | 3dad341 | 2018-02-28 12:01:46 -0800 | [diff] [blame^] | 164 | /// CHECK-NOT: Abs loop:{{B\d+}} |
Aart Bik | 5d75afe | 2015-12-14 11:57:01 -0800 | [diff] [blame] | 165 | |
| 166 | /// CHECK-START: int Main.invariantBoundIntrinsic(int) licm (after) |
Aart Bik | 3dad341 | 2018-02-28 12:01:46 -0800 | [diff] [blame^] | 167 | /// CHECK-DAG: Abs loop:none |
Aart Bik | 5d75afe | 2015-12-14 11:57:01 -0800 | [diff] [blame] | 168 | |
| 169 | public static int invariantBoundIntrinsic(int x) { |
| 170 | int result = 0; |
| 171 | // The intrinsic call to abs used as loop bound is invariant. |
| 172 | // As a result, the call itself can be moved out of the loop header. |
| 173 | for (int i = 0; i < Math.abs(x); i++) { |
| 174 | result += i; |
| 175 | } |
| 176 | return result; |
| 177 | } |
| 178 | |
| 179 | /// CHECK-START: int Main.invariantBodyIntrinsic(int, int) licm (before) |
| 180 | /// CHECK-DAG: InvokeStaticOrDirect loop:{{B\d+}} |
| 181 | |
| 182 | /// CHECK-START: int Main.invariantBodyIntrinsic(int, int) licm (after) |
| 183 | /// CHECK-NOT: InvokeStaticOrDirect loop:{{B\d+}} |
| 184 | |
| 185 | /// CHECK-START: int Main.invariantBodyIntrinsic(int, int) licm (after) |
| 186 | /// CHECK-DAG: InvokeStaticOrDirect loop:none |
| 187 | |
| 188 | public static int invariantBodyIntrinsic(int x, int y) { |
| 189 | int result = 0; |
| 190 | for (int i = 0; i < 10; i++) { |
| 191 | // The intrinsic call to max used inside the loop is invariant. |
| 192 | // As a result, the call itself can be moved out of the loop body. |
| 193 | result += Math.max(x, y); |
| 194 | } |
| 195 | return result; |
| 196 | } |
| 197 | |
Aart Bik | c5d1b4b | 2016-11-09 15:30:03 -0800 | [diff] [blame] | 198 | // |
| 199 | // All operations up to the null check can be hoisted out of the |
| 200 | // loop. The null check itself sees the induction in its environment. |
| 201 | // |
| 202 | /// CHECK-START: int Main.doWhile(int) licm (before) |
| 203 | /// CHECK-DAG: <<Add:i\d+>> Add loop:<<Loop:B\d+>> outer_loop:none |
| 204 | /// CHECK-DAG: LoadClass loop:<<Loop>> outer_loop:none |
| 205 | /// CHECK-DAG: <<Get:l\d+>> StaticFieldGet loop:<<Loop>> outer_loop:none |
| 206 | /// CHECK-DAG: NullCheck [<<Get>>] env:[[<<Add>>,<<Get>>,{{i\d+}}]] loop:<<Loop>> outer_loop:none |
| 207 | /// CHECK-DAG: ArrayLength loop:<<Loop>> outer_loop:none |
| 208 | /// CHECK-DAG: BoundsCheck loop:<<Loop>> outer_loop:none |
| 209 | /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none |
| 210 | // |
| 211 | /// CHECK-START: int Main.doWhile(int) licm (after) |
| 212 | /// CHECK-NOT: LoadClass loop:{{B\d+}} |
| 213 | /// CHECK-NOT: StaticFieldGet loop:{{B\d+}} |
| 214 | // |
| 215 | /// CHECK-START: int Main.doWhile(int) licm (after) |
| 216 | /// CHECK-DAG: LoadClass loop:none |
| 217 | /// CHECK-DAG: <<Get:l\d+>> StaticFieldGet loop:none |
| 218 | /// CHECK-DAG: <<Add:i\d+>> Add loop:<<Loop:B\d+>> outer_loop:none |
| 219 | /// CHECK-DAG: NullCheck [<<Get>>] env:[[<<Add>>,<<Get>>,{{i\d+}}]] loop:<<Loop>> outer_loop:none |
| 220 | /// CHECK-DAG: ArrayLength loop:<<Loop>> outer_loop:none |
| 221 | /// CHECK-DAG: BoundsCheck loop:<<Loop>> outer_loop:none |
| 222 | /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none |
| 223 | public static int doWhile(int k) { |
| 224 | int i = k; |
| 225 | do { |
| 226 | i += 2; |
| 227 | } while (staticArray[i] == 0); |
| 228 | return i; |
| 229 | } |
| 230 | |
Nicolas Geoffray | 82091da | 2015-01-26 10:02:45 +0000 | [diff] [blame] | 231 | public static int staticField = 42; |
| 232 | |
Aart Bik | c5d1b4b | 2016-11-09 15:30:03 -0800 | [diff] [blame] | 233 | public static int[] staticArray = null; |
| 234 | |
Nicolas Geoffray | 82091da | 2015-01-26 10:02:45 +0000 | [diff] [blame] | 235 | public static void assertEquals(int expected, int actual) { |
| 236 | if (expected != actual) { |
| 237 | throw new Error("Expected " + expected + ", got " + actual); |
| 238 | } |
| 239 | } |
| 240 | |
| 241 | public static void main(String[] args) { |
| 242 | assertEquals(10, div()); |
| 243 | assertEquals(100, innerDiv()); |
Aart Bik | 5d75afe | 2015-12-14 11:57:01 -0800 | [diff] [blame] | 244 | assertEquals(18900, innerMul()); |
| 245 | assertEquals(105, divByA(2, 0)); |
Nicolas Geoffray | 82091da | 2015-01-26 10:02:45 +0000 | [diff] [blame] | 246 | assertEquals(12, arrayLength(new int[] { 4, 8 })); |
Mingyao Yang | 217eb06 | 2017-12-11 15:20:07 -0800 | [diff] [blame] | 247 | assertEquals(10, clinitCheck()); |
Aart Bik | 5d75afe | 2015-12-14 11:57:01 -0800 | [diff] [blame] | 248 | assertEquals(21, divAndIntrinsic(new int[] { 4, -2, 8, -3 })); |
| 249 | assertEquals(45, invariantBoundIntrinsic(-10)); |
| 250 | assertEquals(30, invariantBodyIntrinsic(2, 3)); |
Aart Bik | c5d1b4b | 2016-11-09 15:30:03 -0800 | [diff] [blame] | 251 | |
| 252 | staticArray = null; |
| 253 | try { |
| 254 | doWhile(0); |
| 255 | throw new Error("Expected NPE"); |
| 256 | } catch (NullPointerException e) { |
| 257 | } |
| 258 | staticArray = new int[5]; |
| 259 | staticArray[4] = 1; |
| 260 | assertEquals(4, doWhile(-2)); |
| 261 | assertEquals(4, doWhile(0)); |
| 262 | assertEquals(4, doWhile(2)); |
| 263 | try { |
| 264 | doWhile(1); |
| 265 | throw new Error("Expected IOOBE"); |
| 266 | } catch (IndexOutOfBoundsException e) { |
| 267 | } |
| 268 | |
| 269 | System.out.println("passed"); |
Nicolas Geoffray | 82091da | 2015-01-26 10:02:45 +0000 | [diff] [blame] | 270 | } |
| 271 | } |