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:StringBuilderAppend
140   /// CHECK-DAG: <<String2:l\d+>> LoadString
141   /// CHECK-DAG: <<Append2:l\d+>> InvokeVirtual [{{l\d+}},<<String2>>] intrinsic:StringBuilderAppend
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:StringBuilderAppend
148   /// CHECK-DAG: <<String2:l\d+>> LoadString
149   /// CHECK-DAG: <<Append2:l\d+>> InvokeVirtual [<<New>>,<<String2>>] intrinsic:StringBuilderAppend
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:StringBuilderAppend loop:<<Loop>>
207   /// CHECK-DAG: <<String2:l\d+>> LoadString                                                          loop:<<Loop>>
208   /// CHECK-DAG: <<Append2:l\d+>> InvokeVirtual [{{l\d+}},<<String2>>]  intrinsic:StringBuilderAppend loop:<<Loop>>
209   /// CHECK-DAG: <<String3:l\d+>> LoadString                                                          loop:<<Loop>>
210   /// CHECK-DAG: <<Append3:l\d+>> InvokeVirtual [{{l\d+}},<<String3>>]  intrinsic:StringBuilderAppend 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:StringBuilderAppend loop:<<Loop>>
217   /// CHECK-DAG: <<String2:l\d+>> LoadString                                                        loop:<<Loop>>
218   /// CHECK-DAG: <<Append2:l\d+>> InvokeVirtual [<<New>>,<<String2>>] intrinsic:StringBuilderAppend loop:<<Loop>>
219   /// CHECK-DAG: <<String3:l\d+>> LoadString                                                        loop:<<Loop>>
220   /// CHECK-DAG: <<Append3:l\d+>> InvokeVirtual [<<New>>,<<String3>>] intrinsic:StringBuilderAppend 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