1 /*
2 * Copyright (c) 2016, 2019, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24
25 package org.graalvm.compiler.replacements;
26
27 import static org.graalvm.compiler.replacements.SnippetTemplate.DEFAULT_REPLACER;
28 import static org.graalvm.compiler.serviceprovider.GraalUnsafeAccess.getUnsafe;
29
30 import org.graalvm.compiler.api.replacements.Fold;
31 import org.graalvm.compiler.api.replacements.Fold.InjectedParameter;
32 import org.graalvm.compiler.api.replacements.Snippet;
33 import org.graalvm.compiler.api.replacements.Snippet.ConstantParameter;
34 import org.graalvm.compiler.api.replacements.SnippetReflectionProvider;
35 import org.graalvm.compiler.debug.DebugHandlersFactory;
36 import org.graalvm.compiler.nodes.StructuredGraph;
37 import org.graalvm.compiler.nodes.spi.LoweringTool;
38 import org.graalvm.compiler.options.OptionValues;
39 import org.graalvm.compiler.phases.util.Providers;
40 import org.graalvm.compiler.replacements.SnippetTemplate.AbstractTemplates;
41 import org.graalvm.compiler.replacements.SnippetTemplate.Arguments;
42 import org.graalvm.compiler.replacements.SnippetTemplate.SnippetInfo;
43 import org.graalvm.compiler.replacements.nodes.ExplodeLoopNode;
44
45 import jdk.vm.ci.code.TargetDescription;
46 import jdk.vm.ci.meta.JavaKind;
47 import jdk.vm.ci.meta.MetaAccessProvider;
48 import sun.misc.Unsafe;
49
50 public class ConstantStringIndexOfSnippets implements Snippets {
51 private static final Unsafe UNSAFE = getUnsafe();
52
53 public static class Templates extends AbstractTemplates {
54
55 private final SnippetInfo indexOfConstant = snippet(ConstantStringIndexOfSnippets.class, "indexOfConstant");
56 private final SnippetInfo latin1IndexOfConstant = snippet(ConstantStringIndexOfSnippets.class, "latin1IndexOfConstant");
57 private final SnippetInfo utf16IndexOfConstant = snippet(ConstantStringIndexOfSnippets.class, "utf16IndexOfConstant");
58
59 public Templates(OptionValues options, Iterable<DebugHandlersFactory> factories, Providers providers, SnippetReflectionProvider snippetReflection, TargetDescription target) {
60 super(options, factories, providers, snippetReflection, target);
61 }
62
63 public void lower(SnippetLowerableMemoryNode stringIndexOf, LoweringTool tool) {
64 StructuredGraph graph = stringIndexOf.graph();
65 Arguments args = new Arguments(indexOfConstant, graph.getGuardsStage(), tool.getLoweringStage());
66 args.add("source", stringIndexOf.getArgument(0));
67 args.add("sourceOffset", stringIndexOf.getArgument(1));
68 args.add("sourceCount", stringIndexOf.getArgument(2));
69 args.addConst("target", stringIndexOf.getArgument(3));
70 args.add("targetOffset", stringIndexOf.getArgument(4));
71 args.add("targetCount", stringIndexOf.getArgument(5));
72 args.add("origFromIndex", stringIndexOf.getArgument(6));
73 char[] targetCharArray = snippetReflection.asObject(char[].class, stringIndexOf.getArgument(3).asJavaConstant());
74 args.addConst("md2", md2(targetCharArray));
75 args.addConst("cache", computeCache(targetCharArray));
76 template(stringIndexOf, args).instantiate(providers.getMetaAccess(), stringIndexOf, DEFAULT_REPLACER, args);
77 }
78
79 public void lowerLatin1(SnippetLowerableMemoryNode latin1IndexOf, LoweringTool tool) {
80 StructuredGraph graph = latin1IndexOf.graph();
81 Arguments args = new Arguments(latin1IndexOfConstant, graph.getGuardsStage(), tool.getLoweringStage());
82 args.add("source", latin1IndexOf.getArgument(0));
83 args.add("sourceCount", latin1IndexOf.getArgument(1));
84 args.addConst("target", latin1IndexOf.getArgument(2));
85 args.add("targetCount", latin1IndexOf.getArgument(3));
86 args.add("origFromIndex", latin1IndexOf.getArgument(4));
87 byte[] targetByteArray = snippetReflection.asObject(byte[].class, latin1IndexOf.getArgument(2).asJavaConstant());
88 args.addConst("md2", md2(targetByteArray));
89 args.addConst("cache", computeCache(targetByteArray));
90 template(latin1IndexOf, args).instantiate(providers.getMetaAccess(), latin1IndexOf, DEFAULT_REPLACER, args);
91 }
92
93 public void lowerUTF16(SnippetLowerableMemoryNode utf16IndexOf, LoweringTool tool) {
94 StructuredGraph graph = utf16IndexOf.graph();
95 Arguments args = new Arguments(utf16IndexOfConstant, graph.getGuardsStage(), tool.getLoweringStage());
96 args.add("source", utf16IndexOf.getArgument(0));
97 args.add("sourceCount", utf16IndexOf.getArgument(1));
98 args.addConst("target", utf16IndexOf.getArgument(2));
99 args.add("targetCount", utf16IndexOf.getArgument(3));
100 args.add("origFromIndex", utf16IndexOf.getArgument(4));
101 byte[] targetByteArray = snippetReflection.asObject(byte[].class, utf16IndexOf.getArgument(2).asJavaConstant());
102 args.addConst("md2", md2Utf16(tool.getMetaAccess(), targetByteArray));
103 args.addConst("cache", computeCacheUtf16(tool.getMetaAccess(), targetByteArray));
104 template(utf16IndexOf, args).instantiate(providers.getMetaAccess(), utf16IndexOf, DEFAULT_REPLACER, args);
105 }
106 }
107
108 static int md2(char[] target) {
109 int c = target.length;
110 if (c == 0) {
111 return 0;
112 }
113 char lastChar = target[c - 1];
114 int md2 = c;
115 for (int i = 0; i < c - 1; i++) {
116 if (target[i] == lastChar) {
117 md2 = (c - 1) - i;
118 }
119 }
120 return md2;
121 }
122
123 static long computeCache(char[] s) {
124 int c = s.length;
125 int cache = 0;
126 int i;
127 for (i = 0; i < c - 1; i++) {
128 cache |= (1 << (s[i] & 63));
129 }
130 return cache;
131 }
132
133 static int md2(byte[] target) {
134 int c = target.length;
135 if (c == 0) {
136 return 0;
137 }
138 byte lastByte = target[c - 1];
139 int md2 = c;
140 for (int i = 0; i < c - 1; i++) {
141 if (target[i] == lastByte) {
142 md2 = (c - 1) - i;
143 }
144 }
145 return md2;
146 }
147
148 static long computeCache(byte[] s) {
149 int c = s.length;
150 int cache = 0;
151 int i;
152 for (i = 0; i < c - 1; i++) {
153 cache |= (1 << (s[i] & 63));
154 }
155 return cache;
156 }
157
158 static int md2Utf16(MetaAccessProvider metaAccess, byte[] target) {
159 int c = target.length / 2;
160 if (c == 0) {
161 return 0;
162 }
163 long base = metaAccess.getArrayBaseOffset(JavaKind.Byte);
164 char lastChar = UNSAFE.getChar(target, base + (c - 1) * 2);
165 int md2 = c;
166 for (int i = 0; i < c - 1; i++) {
167 char currChar = UNSAFE.getChar(target, base + i * 2);
168 if (currChar == lastChar) {
169 md2 = (c - 1) - i;
170 }
171 }
172 return md2;
173 }
174
175 static long computeCacheUtf16(MetaAccessProvider metaAccess, byte[] s) {
176 int c = s.length / 2;
177 int cache = 0;
178 int i;
179 long base = metaAccess.getArrayBaseOffset(JavaKind.Byte);
180 for (i = 0; i < c - 1; i++) {
181 char currChar = UNSAFE.getChar(s, base + i * 2);
182 cache |= (1 << (currChar & 63));
183 }
184 return cache;
185 }
186
187 @Fold
188 static int byteArrayBaseOffset(@InjectedParameter MetaAccessProvider metaAccess) {
189 return metaAccess.getArrayBaseOffset(JavaKind.Byte);
190 }
191
192 @Fold
193 static int charArrayBaseOffset(@InjectedParameter MetaAccessProvider metaAccess) {
194 return metaAccess.getArrayBaseOffset(JavaKind.Char);
195 }
196
197 /** Marker value for the {@link InjectedParameter} injected parameter. */
198 static final MetaAccessProvider INJECTED = null;
199
200 @Snippet
201 public static int indexOfConstant(char[] source, int sourceOffset, int sourceCount,
202 @ConstantParameter char[] target, int targetOffset, int targetCount,
203 int origFromIndex, @ConstantParameter int md2, @ConstantParameter long cache) {
204 int fromIndex = origFromIndex;
205 if (fromIndex >= sourceCount) {
206 return (targetCount == 0 ? sourceCount : -1);
207 }
208 if (fromIndex < 0) {
209 fromIndex = 0;
210 }
211 if (targetCount == 0) {
212 return fromIndex;
213 }
214
215 int targetCountLess1 = targetCount - 1;
216 int sourceEnd = sourceCount - targetCountLess1;
217
218 long base = charArrayBaseOffset(INJECTED);
219 int lastChar = UNSAFE.getChar(target, base + targetCountLess1 * 2);
220
221 outer_loop: for (long i = sourceOffset + fromIndex; i < sourceEnd;) {
222 int src = UNSAFE.getChar(source, base + (i + targetCountLess1) * 2);
223 if (src == lastChar) {
224 // With random strings and a 4-character alphabet,
225 // reverse matching at this point sets up 0.8% fewer
226 // frames, but (paradoxically) makes 0.3% more probes.
227 // Since those probes are nearer the lastChar probe,
228 // there is may be a net D$ win with reverse matching.
229 // But, reversing loop inhibits unroll of inner loop
230 // for unknown reason. So, does running outer loop from
231 // (sourceOffset - targetCountLess1) to (sourceOffset + sourceCount)
232 if (targetCount <= 8) {
233 ExplodeLoopNode.explodeLoop();
234 }
235 for (long j = 0; j < targetCountLess1; j++) {
236 char sourceChar = UNSAFE.getChar(source, base + (i + j) * 2);
237 if (UNSAFE.getChar(target, base + (targetOffset + j) * 2) != sourceChar) {
238 if ((cache & (1 << sourceChar)) == 0) {
239 if (md2 < j + 1) {
240 i += j + 1;
241 continue outer_loop;
242 }
243 }
244 i += md2;
245 continue outer_loop;
246 }
247 }
248 return (int) (i - sourceOffset);
249 }
250 if ((cache & (1 << src)) == 0) {
251 i += targetCountLess1;
252 }
253 i++;
254 }
255 return -1;
256 }
257
258 @Snippet
259 public static int utf16IndexOfConstant(byte[] source, int sourceCount,
260 @ConstantParameter byte[] target, int targetCount,
261 int origFromIndex, @ConstantParameter int md2, @ConstantParameter long cache) {
262 int fromIndex = origFromIndex;
263 if (fromIndex >= sourceCount) {
264 return (targetCount == 0 ? sourceCount : -1);
265 }
266 if (fromIndex < 0) {
267 fromIndex = 0;
268 }
269 if (targetCount == 0) {
270 return fromIndex;
271 }
272
273 int targetCountLess1 = targetCount - 1;
274 int sourceEnd = sourceCount - targetCountLess1;
275
276 long base = byteArrayBaseOffset(INJECTED);
277 int lastChar = UNSAFE.getChar(target, base + targetCountLess1 * 2);
278
279 outer_loop: for (long i = fromIndex; i < sourceEnd;) {
280 int src = UNSAFE.getChar(source, base + (i + targetCountLess1) * 2);
281 if (src == lastChar) {
282 // With random strings and a 4-character alphabet,
283 // reverse matching at this point sets up 0.8% fewer
284 // frames, but (paradoxically) makes 0.3% more probes.
285 // Since those probes are nearer the lastChar probe,
286 // there is may be a net D$ win with reverse matching.
287 // But, reversing loop inhibits unroll of inner loop
288 // for unknown reason. So, does running outer loop from
289 // (sourceOffset - targetCountLess1) to (sourceOffset + sourceCount)
290 if (targetCount <= 8) {
291 ExplodeLoopNode.explodeLoop();
292 }
293 for (long j = 0; j < targetCountLess1; j++) {
294 char sourceChar = UNSAFE.getChar(source, base + (i + j) * 2);
295 if (UNSAFE.getChar(target, base + j * 2) != sourceChar) {
296 if ((cache & (1 << sourceChar)) == 0) {
297 if (md2 < j + 1) {
298 i += j + 1;
299 continue outer_loop;
300 }
301 }
302 i += md2;
303 continue outer_loop;
304 }
305 }
306 return (int) i;
307 }
308 if ((cache & (1 << src)) == 0) {
309 i += targetCountLess1;
310 }
311 i++;
312 }
313 return -1;
314 }
315
316 @Snippet
317 public static int latin1IndexOfConstant(byte[] source, int sourceCount,
318 @ConstantParameter byte[] target, int targetCount,
319 int origFromIndex, @ConstantParameter int md2, @ConstantParameter long cache) {
320 int fromIndex = origFromIndex;
321 if (fromIndex >= sourceCount) {
322 return (targetCount == 0 ? sourceCount : -1);
323 }
324 if (fromIndex < 0) {
325 fromIndex = 0;
326 }
327 if (targetCount == 0) {
328 return fromIndex;
329 }
330
331 int targetCountLess1 = targetCount - 1;
332 int sourceEnd = sourceCount - targetCountLess1;
333
334 long base = byteArrayBaseOffset(INJECTED);
335 int lastByte = UNSAFE.getByte(target, base + targetCountLess1);
336
337 outer_loop: for (long i = fromIndex; i < sourceEnd;) {
338 int src = UNSAFE.getByte(source, base + i + targetCountLess1);
339 if (src == lastByte) {
340 // With random strings and a 4-character alphabet,
341 // reverse matching at this point sets up 0.8% fewer
342 // frames, but (paradoxically) makes 0.3% more probes.
343 // Since those probes are nearer the lastByte probe,
344 // there is may be a net D$ win with reverse matching.
345 // But, reversing loop inhibits unroll of inner loop
346 // for unknown reason. So, does running outer loop from
347 // (sourceOffset - targetCountLess1) to (sourceOffset + sourceCount)
348 if (targetCount <= 8) {
349 ExplodeLoopNode.explodeLoop();
350 }
351 for (long j = 0; j < targetCountLess1; j++) {
352 byte sourceByte = UNSAFE.getByte(source, base + i + j);
353 if (UNSAFE.getByte(target, base + j) != sourceByte) {
354 if ((cache & (1 << sourceByte)) == 0) {
355 if (md2 < j + 1) {
356 i += j + 1;
357 continue outer_loop;
358 }
359 }
360 i += md2;
361 continue outer_loop;
362 }
363 }
364 return (int) i;
365 }
366 if ((cache & (1 << src)) == 0) {
367 i += targetCountLess1;
368 }
369 i++;
370 }
371 return -1;
372 }
373 }