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 import java.lang.reflect.Method; 17 18 /** 19 * Tests properties of some string operations represented by intrinsics. 20 */ 21 public class Main { 22 23 static final String ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; 24 static final String XYZ = "XYZ"; 25 26 // 27 // Variant intrinsics remain in the loop, but invariant references are hoisted out of the loop. 28 // 29 /// CHECK-START: int Main.liveIndexOf() licm (before) 30 /// CHECK-DAG: InvokeVirtual intrinsic:StringIndexOf loop:{{B\d+}} outer_loop:none 31 /// CHECK-DAG: InvokeVirtual intrinsic:StringIndexOfAfter loop:{{B\d+}} outer_loop:none 32 /// CHECK-DAG: InvokeVirtual intrinsic:StringStringIndexOf loop:{{B\d+}} outer_loop:none 33 /// CHECK-DAG: InvokeVirtual intrinsic:StringStringIndexOfAfter loop:{{B\d+}} outer_loop:none 34 // 35 /// CHECK-START: int Main.liveIndexOf() licm (after) 36 /// CHECK-DAG: InvokeVirtual intrinsic:StringIndexOf loop:{{B\d+}} outer_loop:none 37 /// CHECK-DAG: InvokeVirtual intrinsic:StringIndexOfAfter loop:{{B\d+}} outer_loop:none 38 /// CHECK-DAG: InvokeVirtual intrinsic:StringStringIndexOf loop:none 39 /// CHECK-DAG: InvokeVirtual intrinsic:StringStringIndexOfAfter loop:none liveIndexOf()40 static int liveIndexOf() { 41 int k = ABC.length() + XYZ.length(); // does LoadString before loops 42 for (char c = 'A'; c <= 'Z'; c++) { 43 k += ABC.indexOf(c); 44 } 45 for (char c = 'A'; c <= 'Z'; c++) { 46 k += ABC.indexOf(c, 4); 47 } 48 for (char c = 'A'; c <= 'Z'; c++) { 49 k += ABC.indexOf(XYZ); 50 } 51 for (char c = 'A'; c <= 'Z'; c++) { 52 k += ABC.indexOf(XYZ, 2); 53 } 54 return k; 55 } 56 57 // 58 // All dead intrinsics can be removed completely. 59 // 60 /// CHECK-START: int Main.deadIndexOf() dead_code_elimination$initial (before) 61 /// CHECK-DAG: InvokeVirtual intrinsic:StringIndexOf loop:{{B\d+}} outer_loop:none 62 /// CHECK-DAG: InvokeVirtual intrinsic:StringIndexOfAfter loop:{{B\d+}} outer_loop:none 63 /// CHECK-DAG: InvokeVirtual intrinsic:StringStringIndexOf loop:{{B\d+}} outer_loop:none 64 /// CHECK-DAG: InvokeVirtual intrinsic:StringStringIndexOfAfter loop:{{B\d+}} outer_loop:none 65 // 66 /// CHECK-START: int Main.deadIndexOf() dead_code_elimination$initial (after) 67 /// CHECK-NOT: InvokeVirtual intrinsic:StringIndexOf 68 /// CHECK-NOT: InvokeVirtual intrinsic:StringIndexOfAfter 69 /// CHECK-NOT: InvokeVirtual intrinsic:StringStringIndexOf 70 /// CHECK-NOT: InvokeVirtual intrinsic:StringStringIndexOfAfter deadIndexOf()71 static int deadIndexOf() { 72 int k = ABC.length() + XYZ.length(); // does LoadString before loops 73 for (char c = 'A'; c <= 'Z'; c++) { 74 int d = ABC.indexOf(c); 75 } 76 for (char c = 'A'; c <= 'Z'; c++) { 77 int d = ABC.indexOf(c, 4); 78 } 79 for (char c = 'A'; c <= 'Z'; c++) { 80 int d = ABC.indexOf(XYZ); 81 } 82 for (char c = 'A'; c <= 'Z'; c++) { 83 int d = ABC.indexOf(XYZ, 2); 84 } 85 return k; 86 } 87 88 // 89 // Explicit null check on receiver, implicit null check on argument prevents hoisting. 90 // 91 /// CHECK-START: int Main.indexOfExceptions(java.lang.String, java.lang.String) licm (after) 92 /// CHECK-DAG: <<String:l\d+>> NullCheck loop:<<Loop:B\d+>> outer_loop:none 93 /// CHECK-DAG: InvokeVirtual [<<String>>,{{l\d+}}] intrinsic:StringStringIndexOf loop:<<Loop>> outer_loop:none indexOfExceptions(String s, String t)94 static int indexOfExceptions(String s, String t) { 95 int k = 0; 96 for (char c = 'A'; c <= 'Z'; c++) { 97 k += s.indexOf(t); 98 } 99 return k; 100 } 101 102 // 103 // Allows combining of returned "this". Also ensures that similar looking append() calls 104 // are not combined somehow through returned result. 105 // 106 /// CHECK-START: int Main.bufferLen2() instruction_simplifier (before) 107 /// CHECK-DAG: <<New:l\d+>> NewInstance 108 /// CHECK-DAG: <<String1:l\d+>> LoadString 109 /// CHECK-DAG: <<Append1:l\d+>> InvokeVirtual [<<New>>,<<String1>>] intrinsic:StringBufferAppend 110 /// CHECK-DAG: <<String2:l\d+>> LoadString 111 /// CHECK-DAG: <<Append2:l\d+>> InvokeVirtual [{{l\d+}},<<String2>>] intrinsic:StringBufferAppend 112 /// CHECK-DAG: InvokeVirtual [{{l\d+}}] intrinsic:StringBufferLength 113 // 114 /// CHECK-START: int Main.bufferLen2() instruction_simplifier (after) 115 /// CHECK-DAG: <<New:l\d+>> NewInstance 116 /// CHECK-DAG: <<String1:l\d+>> LoadString 117 /// CHECK-DAG: <<Append1:l\d+>> InvokeVirtual [<<New>>,<<String1>>] intrinsic:StringBufferAppend 118 /// CHECK-DAG: <<String2:l\d+>> LoadString 119 /// CHECK-DAG: <<Append2:l\d+>> InvokeVirtual [<<New>>,<<String2>>] intrinsic:StringBufferAppend 120 /// CHECK-DAG: InvokeVirtual [<<New>>] intrinsic:StringBufferLength bufferLen2()121 static int bufferLen2() { 122 StringBuffer s = new StringBuffer(); 123 return s.append("x").append("y").length(); 124 } 125 bufferLen2Smali()126 static int bufferLen2Smali() throws Exception { 127 Class<?> c = Class.forName("Smali"); 128 Method m = c.getMethod("bufferLen2"); 129 return (Integer) m.invoke(null); 130 } 131 132 // 133 // Allows combining of returned "this". Also ensures that similar looking append() calls 134 // are not combined somehow through returned result. 135 // 136 /// CHECK-START: int Main.builderLen2() instruction_simplifier (before) 137 /// CHECK-DAG: <<New:l\d+>> NewInstance 138 /// CHECK-DAG: <<String1:l\d+>> LoadString 139 /// CHECK-DAG: <<Append1:l\d+>> InvokeVirtual [<<New>>,<<String1>>] intrinsic:StringBuilderAppendString 140 /// CHECK-DAG: <<String2:l\d+>> LoadString 141 /// CHECK-DAG: <<Append2:l\d+>> InvokeVirtual [{{l\d+}},<<String2>>] intrinsic:StringBuilderAppendString 142 /// CHECK-DAG: InvokeVirtual [{{l\d+}}] intrinsic:StringBuilderLength 143 // 144 /// CHECK-START: int Main.builderLen2() instruction_simplifier (after) 145 /// CHECK-DAG: <<New:l\d+>> NewInstance 146 /// CHECK-DAG: <<String1:l\d+>> LoadString 147 /// CHECK-DAG: <<Append1:l\d+>> InvokeVirtual [<<New>>,<<String1>>] intrinsic:StringBuilderAppendString 148 /// CHECK-DAG: <<String2:l\d+>> LoadString 149 /// CHECK-DAG: <<Append2:l\d+>> InvokeVirtual [<<New>>,<<String2>>] intrinsic:StringBuilderAppendString 150 /// CHECK-DAG: InvokeVirtual [<<New>>] intrinsic:StringBuilderLength builderLen2()151 static int builderLen2() { 152 StringBuilder s = new StringBuilder(); 153 return s.append("x").append("y").length(); 154 } 155 builderLen2Smali()156 static int builderLen2Smali() throws Exception { 157 Class<?> c = Class.forName("Smali"); 158 Method m = c.getMethod("builderLen2"); 159 return (Integer) m.invoke(null); 160 } 161 162 // 163 // Similar situation in a loop. 164 // 165 /// CHECK-START: int Main.bufferLoopAppender() instruction_simplifier (before) 166 /// CHECK-DAG: <<New:l\d+>> NewInstance loop:none 167 /// CHECK-DAG: <<String1:l\d+>> LoadString loop:<<Loop:B\d+>> 168 /// CHECK-DAG: <<Null1:l\d+>> NullCheck [<<New>>] loop:<<Loop>> 169 /// CHECK-DAG: <<Append1:l\d+>> InvokeVirtual [<<Null1>>,<<String1>>] intrinsic:StringBufferAppend loop:<<Loop>> 170 /// CHECK-DAG: <<String2:l\d+>> LoadString loop:<<Loop>> 171 /// CHECK-DAG: <<Append2:l\d+>> InvokeVirtual [{{l\d+}},<<String2>>] intrinsic:StringBufferAppend loop:<<Loop>> 172 /// CHECK-DAG: <<String3:l\d+>> LoadString loop:<<Loop>> 173 /// CHECK-DAG: <<Append3:l\d+>> InvokeVirtual [{{l\d+}},<<String3>>] intrinsic:StringBufferAppend loop:<<Loop>> 174 /// CHECK-DAG: InvokeVirtual [{{l\d+}}] intrinsic:StringBufferLength loop:none 175 // 176 /// CHECK-START: int Main.bufferLoopAppender() instruction_simplifier (after) 177 /// CHECK-DAG: <<New:l\d+>> NewInstance loop:none 178 /// CHECK-DAG: <<String1:l\d+>> LoadString loop:<<Loop:B\d+>> 179 /// CHECK-DAG: <<Append1:l\d+>> InvokeVirtual [<<New>>,<<String1>>] intrinsic:StringBufferAppend loop:<<Loop>> 180 /// CHECK-DAG: <<String2:l\d+>> LoadString loop:<<Loop>> 181 /// CHECK-DAG: <<Append2:l\d+>> InvokeVirtual [<<New>>,<<String2>>] intrinsic:StringBufferAppend loop:<<Loop>> 182 /// CHECK-DAG: <<String3:l\d+>> LoadString loop:<<Loop>> 183 /// CHECK-DAG: <<Append3:l\d+>> InvokeVirtual [<<New>>,<<String3>>] intrinsic:StringBufferAppend loop:<<Loop>> 184 /// CHECK-DAG: InvokeVirtual [<<New>>] intrinsic:StringBufferLength loop:none bufferLoopAppender()185 static int bufferLoopAppender() { 186 StringBuffer b = new StringBuffer(); 187 for (int i = 0; i < 10; i++) { 188 b.append("x").append("y").append("z"); 189 } 190 return b.length(); 191 } 192 bufferLoopAppenderSmali()193 static int bufferLoopAppenderSmali() throws Exception { 194 Class<?> c = Class.forName("Smali"); 195 Method m = c.getMethod("bufferLoopAppender"); 196 return (Integer) m.invoke(null); 197 } 198 199 // 200 // Similar situation in a loop. 201 // 202 /// CHECK-START: int Main.builderLoopAppender() instruction_simplifier (before) 203 /// CHECK-DAG: <<New:l\d+>> NewInstance loop:none 204 /// CHECK-DAG: <<String1:l\d+>> LoadString loop:<<Loop:B\d+>> 205 /// CHECK-DAG: <<Null1:l\d+>> NullCheck [<<New>>] loop:<<Loop>> 206 /// CHECK-DAG: <<Append1:l\d+>> InvokeVirtual [<<Null1>>,<<String1>>] intrinsic:StringBuilderAppendString loop:<<Loop>> 207 /// CHECK-DAG: <<String2:l\d+>> LoadString loop:<<Loop>> 208 /// CHECK-DAG: <<Append2:l\d+>> InvokeVirtual [{{l\d+}},<<String2>>] intrinsic:StringBuilderAppendString loop:<<Loop>> 209 /// CHECK-DAG: <<String3:l\d+>> LoadString loop:<<Loop>> 210 /// CHECK-DAG: <<Append3:l\d+>> InvokeVirtual [{{l\d+}},<<String3>>] intrinsic:StringBuilderAppendString loop:<<Loop>> 211 /// CHECK-DAG: InvokeVirtual [{{l\d+}}] intrinsic:StringBuilderLength loop:none 212 // 213 /// CHECK-START: int Main.builderLoopAppender() instruction_simplifier (after) 214 /// CHECK-DAG: <<New:l\d+>> NewInstance loop:none 215 /// CHECK-DAG: <<String1:l\d+>> LoadString loop:<<Loop:B\d+>> 216 /// CHECK-DAG: <<Append1:l\d+>> InvokeVirtual [<<New>>,<<String1>>] intrinsic:StringBuilderAppendString loop:<<Loop>> 217 /// CHECK-DAG: <<String2:l\d+>> LoadString loop:<<Loop>> 218 /// CHECK-DAG: <<Append2:l\d+>> InvokeVirtual [<<New>>,<<String2>>] intrinsic:StringBuilderAppendString loop:<<Loop>> 219 /// CHECK-DAG: <<String3:l\d+>> LoadString loop:<<Loop>> 220 /// CHECK-DAG: <<Append3:l\d+>> InvokeVirtual [<<New>>,<<String3>>] intrinsic:StringBuilderAppendString loop:<<Loop>> 221 /// CHECK-DAG: InvokeVirtual [<<New>>] intrinsic:StringBuilderLength loop:none builderLoopAppender()222 static int builderLoopAppender() { 223 StringBuilder b = new StringBuilder(); 224 for (int i = 0; i < 10; i++) { 225 b.append("x").append("y").append("z"); 226 } 227 return b.length(); 228 } 229 builderLoopAppenderSmali()230 static int builderLoopAppenderSmali() throws Exception { 231 Class<?> c = Class.forName("Smali"); 232 Method m = c.getMethod("bufferLoopAppender"); 233 return (Integer) m.invoke(null); 234 } 235 236 // 237 // All calls in the loop-body and thus loop can be eliminated. 238 // 239 /// CHECK-START: int Main.bufferDeadLoop() instruction_simplifier (before) 240 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> 241 /// CHECK-DAG: InvokeVirtual intrinsic:StringBufferToString loop:<<Loop>> 242 /// CHECK-DAG: InvokeVirtual intrinsic:StringStringIndexOfAfter loop:<<Loop>> 243 // 244 /// CHECK-START: int Main.bufferDeadLoop() loop_optimization (after) 245 /// CHECK-NOT: Phi 246 /// CHECK-NOT: InvokeVirtual intrinsic:StringBufferToString 247 /// CHECK-NOT: InvokeVirtual intrinsic:StringStringIndexOfAfter bufferDeadLoop()248 static int bufferDeadLoop() { 249 StringBuffer b = new StringBuffer(); 250 String x = "x"; 251 for (int i = 0; i < 10; i++) { 252 int d = b.toString().indexOf(x, 1); 253 } 254 return b.length(); 255 } 256 257 // 258 // All calls in the loop-body and thus loop can be eliminated. 259 // 260 /// CHECK-START: int Main.builderDeadLoop() instruction_simplifier (before) 261 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> 262 /// CHECK-DAG: InvokeVirtual intrinsic:StringBuilderToString loop:<<Loop>> 263 /// CHECK-DAG: InvokeVirtual intrinsic:StringStringIndexOfAfter loop:<<Loop>> 264 // 265 /// CHECK-START: int Main.builderDeadLoop() loop_optimization (after) 266 /// CHECK-NOT: Phi 267 /// CHECK-NOT: InvokeVirtual intrinsic:StringBuilderToString 268 /// CHECK-NOT: InvokeVirtual intrinsic:StringStringIndexOfAfter builderDeadLoop()269 static int builderDeadLoop() { 270 StringBuilder b = new StringBuilder(); 271 String x = "x"; 272 for (int i = 0; i < 10; i++) { 273 int d = b.toString().indexOf(x, 1); 274 } 275 return b.length(); 276 } 277 278 // Regression b/33656359: StringBuffer x is passed to constructor of String 279 // (this caused old code to crash due to missing nullptr check). 280 // 281 /// CHECK-START: void Main.doesNothing() instruction_simplifier (before) 282 /// CHECK-DAG: InvokeVirtual intrinsic:StringBufferToString 283 // 284 /// CHECK-START: void Main.doesNothing() instruction_simplifier (after) 285 /// CHECK-DAG: InvokeVirtual intrinsic:StringBufferToString doesNothing()286 static void doesNothing() { 287 StringBuffer x = new StringBuffer(); 288 String y = new String(x); 289 x.toString(); 290 } 291 main(String[] args)292 public static void main(String[] args) throws Exception { 293 expectEquals(1865, liveIndexOf()); 294 expectEquals(29, deadIndexOf()); 295 296 try { 297 indexOfExceptions(null, XYZ); 298 throw new Error("Expected: NPE"); 299 } catch (NullPointerException e) { 300 } 301 try { 302 indexOfExceptions(ABC, null); 303 throw new Error("Expected: NPE"); 304 } catch (NullPointerException e) { 305 } 306 expectEquals(598, indexOfExceptions(ABC, XYZ)); 307 308 expectEquals(2, bufferLen2()); 309 expectEquals(2, bufferLen2Smali()); 310 expectEquals(2, builderLen2()); 311 expectEquals(2, builderLen2Smali()); 312 expectEquals(30, bufferLoopAppender()); 313 expectEquals(30, bufferLoopAppenderSmali()); 314 expectEquals(30, builderLoopAppender()); 315 expectEquals(30, builderLoopAppenderSmali()); 316 expectEquals(0, bufferDeadLoop()); 317 expectEquals(0, builderDeadLoop()); 318 319 doesNothing(); 320 321 System.out.println("passed"); 322 } 323 expectEquals(int expected, int result)324 private static void expectEquals(int expected, int result) { 325 if (expected != result) { 326 throw new Error("Expected: " + expected + ", found: " + result); 327 } 328 } 329 } 330