1 /* 2 * Copyright (C) 2016 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 // 18 // Test on loop optimizations, in particular around polynomial induction. 19 // 20 public class Main { 21 22 /// CHECK-START: int Main.poly1() loop_optimization (before) 23 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> 24 /// CHECK-DAG: Add loop:<<Loop>> 25 /// CHECK-DAG: Add loop:<<Loop>> 26 // 27 /// CHECK-START: int Main.poly1() loop_optimization (after) 28 /// CHECK-DAG: <<Zer:i\d+>> IntConstant 0 loop:none 29 /// CHECK-DAG: <<Int:i\d+>> IntConstant 55 loop:none 30 /// CHECK-DAG: <<Add:i\d+>> Add [<<Int>>,<<Zer>>] loop:none 31 /// CHECK-DAG: Return [<<Add>>] loop:none 32 // 33 /// CHECK-START: int Main.poly1() instruction_simplifier$after_bce (after) 34 /// CHECK-DAG: <<Int:i\d+>> IntConstant 55 loop:none 35 /// CHECK-DAG: Return [<<Int>>] loop:none 36 // 37 /// CHECK-START: int Main.poly1() loop_optimization (after) 38 /// CHECK-NOT: Phi poly1()39 public static int poly1() { 40 int a = 0; 41 for (int i = 0; i <= 10; i++) { 42 a += i; 43 } 44 return a; 45 } 46 47 // Multiplication in linear induction has been optimized earlier, 48 // but that does not stop the induction variable recognition 49 // and loop optimizer. 50 // 51 /// CHECK-START: int Main.poly2(int) loop_optimization (before) 52 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> 53 /// CHECK-DAG: Shl loop:<<Loop>> 54 /// CHECK-DAG: Add loop:<<Loop>> 55 /// CHECK-DAG: Add loop:<<Loop>> 56 /// CHECK-DAG: Add loop:<<Loop>> 57 /// CHECK-DAG: Add loop:<<Loop>> 58 // 59 /// CHECK-START: int Main.poly2(int) loop_optimization (after) 60 /// CHECK-DAG: <<Par:i\d+>> ParameterValue loop:none 61 /// CHECK-DAG: <<Int:i\d+>> IntConstant 185 loop:none 62 /// CHECK-DAG: <<Add:i\d+>> Add [<<Int>>,<<Par>>] loop:none 63 /// CHECK-DAG: Return [<<Add>>] loop:none 64 // 65 /// CHECK-START: int Main.poly2(int) loop_optimization (after) 66 /// CHECK-NOT: Phi poly2(int a)67 public static int poly2(int a) { 68 for (int i = 0; i < 10; i++) { 69 int k = 3 * i + 5; 70 a += k; 71 } 72 return a; 73 } 74 75 /// CHECK-START: int Main.poly3() loop_optimization (before) 76 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> 77 /// CHECK-DAG: Add loop:<<Loop>> 78 /// CHECK-DAG: Add loop:<<Loop>> 79 // 80 /// CHECK-START: int Main.poly3() loop_optimization (after) 81 /// CHECK-DAG: <<Ini:i\d+>> IntConstant 12345 loop:none 82 /// CHECK-DAG: <<Int:i\d+>> IntConstant -2146736968 loop:none 83 /// CHECK-DAG: <<Add:i\d+>> Add [<<Int>>,<<Ini>>] loop:none 84 /// CHECK-DAG: Return [<<Add>>] loop:none 85 // 86 /// CHECK-START: int Main.poly3() instruction_simplifier$after_bce (after) 87 /// CHECK-DAG: <<Int:i\d+>> IntConstant -2146724623 loop:none 88 /// CHECK-DAG: Return [<<Int>>] loop:none 89 // 90 /// CHECK-START: int Main.poly3() loop_optimization (after) 91 /// CHECK-NOT: Phi poly3()92 public static int poly3() { 93 int a = 12345; 94 for (int i = 0; i <= 10; i++) { 95 a += (2147483646 * i + 67890); 96 } 97 return a; 98 } 99 100 /// CHECK-START: int Main.polyBCE1() BCE (before) 101 /// CHECK-DAG: BoundsCheck loop:none 102 /// CHECK-DAG: BoundsCheck loop:{{B\d+}} 103 // 104 /// CHECK-START: int Main.polyBCE1() BCE (after) 105 /// CHECK-NOT: BoundsCheck 106 /// CHECK-NOT: Deoptimize polyBCE1()107 public static int polyBCE1() { 108 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 109 11, 12, 13, 14, 15, 16, 17, 19, 19, 20, 110 21, 22 }; 111 int a = 0; 112 int r = 0; 113 for (int i = 0; i < 8; i++) { 114 r += x[a]; 115 a += i; 116 } 117 return r; 118 } 119 120 /// CHECK-START: int Main.polyBCE2() BCE (before) 121 /// CHECK-DAG: BoundsCheck loop:none 122 /// CHECK-DAG: BoundsCheck loop:{{B\d+}} 123 // 124 /// CHECK-START: int Main.polyBCE2() BCE (after) 125 /// CHECK-NOT: BoundsCheck 126 /// CHECK-NOT: Deoptimize polyBCE2()127 public static int polyBCE2() { 128 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 129 11, 12, 13, 14, 15, 16, 17, 19, 19, 20, 130 21, 22, 23, 24, 25, 26, 27 }; 131 int a = 1; 132 int r = 0; 133 for (int i = 0; i < 6; i++) { 134 int k = 2 * i + 1; 135 r -= x[a]; 136 a += k; 137 } 138 return r; 139 } 140 141 /// CHECK-START: int Main.polyBCE3() BCE (before) 142 /// CHECK-DAG: BoundsCheck loop:none 143 /// CHECK-DAG: BoundsCheck loop:{{B\d+}} 144 // 145 /// CHECK-START: int Main.polyBCE3() BCE (after) 146 /// CHECK-NOT: BoundsCheck 147 /// CHECK-NOT: Deoptimize polyBCE3()148 public static int polyBCE3() { 149 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 150 11, 12, 13, 14, 15, 16, 17, 19, 19, 20, 151 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 152 31, 32, 33, 34, 35, 36, 37, 38 }; 153 int r = 0; 154 int a1 = 1; 155 int a2 = 2; 156 for (int i = 0; i < 5; i++) { 157 int t = a1 + a2; // two polynomials combined into new polynomial 158 r -= x[t]; 159 a1 += (3 * i + 1); 160 a2 += (2 * i); 161 } 162 return r; 163 } 164 165 // 166 // Verifier. 167 // 168 main(String[] args)169 public static void main(String[] args) { 170 expectEquals(55, poly1()); 171 expectEquals(185, poly2(0)); 172 expectEquals(192, poly2(7)); 173 expectEquals(-2146724623, poly3()); 174 expectEquals(64, polyBCE1()); 175 expectEquals(-68, polyBCE2()); 176 expectEquals(-80, polyBCE3()); 177 178 System.out.println("passed"); 179 } 180 expectEquals(int expected, int result)181 private static void expectEquals(int expected, int result) { 182 if (expected != result) { 183 throw new Error("Expected: " + expected + ", found: " + result); 184 } 185 } 186 } 187