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
29 import org.graalvm.compiler.api.replacements.Fold;
30 import org.graalvm.compiler.api.replacements.Fold.InjectedParameter;
31 import org.graalvm.compiler.api.replacements.Snippet;
32 import org.graalvm.compiler.api.replacements.Snippet.ConstantParameter;
33 import org.graalvm.compiler.api.replacements.SnippetReflectionProvider;
34 import org.graalvm.compiler.debug.DebugHandlersFactory;
35 import org.graalvm.compiler.nodes.StructuredGraph;
36 import org.graalvm.compiler.nodes.spi.LoweringTool;
37 import org.graalvm.compiler.options.OptionValues;
38 import org.graalvm.compiler.phases.util.Providers;
39 import org.graalvm.compiler.replacements.SnippetTemplate.AbstractTemplates;
40 import org.graalvm.compiler.replacements.SnippetTemplate.Arguments;
41 import org.graalvm.compiler.replacements.SnippetTemplate.SnippetInfo;
42 import org.graalvm.compiler.replacements.nodes.ExplodeLoopNode;
43
44 import jdk.vm.ci.code.TargetDescription;
45 import jdk.vm.ci.meta.JavaKind;
46 import jdk.vm.ci.meta.MetaAccessProvider;
47
48 public class ConstantStringIndexOfSnippets implements Snippets {
49 public static class Templates extends AbstractTemplates {
50
51 private final SnippetInfo indexOfConstant = snippet(ConstantStringIndexOfSnippets.class, "indexOfConstant");
52 private final SnippetInfo latin1IndexOfConstant = snippet(ConstantStringIndexOfSnippets.class, "latin1IndexOfConstant");
53 private final SnippetInfo utf16IndexOfConstant = snippet(ConstantStringIndexOfSnippets.class, "utf16IndexOfConstant");
54
55 public Templates(OptionValues options, Iterable<DebugHandlersFactory> factories, Providers providers, SnippetReflectionProvider snippetReflection, TargetDescription target) {
56 super(options, factories, providers, snippetReflection, target);
57 }
58
59 public void lower(SnippetLowerableMemoryNode stringIndexOf, LoweringTool tool) {
60 StructuredGraph graph = stringIndexOf.graph();
61 Arguments args = new Arguments(indexOfConstant, graph.getGuardsStage(), tool.getLoweringStage());
62 args.add("source", stringIndexOf.getArgument(0));
63 args.add("sourceOffset", stringIndexOf.getArgument(1));
64 args.add("sourceCount", stringIndexOf.getArgument(2));
65 args.addConst("target", stringIndexOf.getArgument(3));
66 args.add("targetOffset", stringIndexOf.getArgument(4));
67 args.add("targetCount", stringIndexOf.getArgument(5));
68 args.add("origFromIndex", stringIndexOf.getArgument(6));
140 }
141 return md2;
142 }
143
144 static long computeCache(byte[] s) {
145 int c = s.length;
146 int cache = 0;
147 int i;
148 for (i = 0; i < c - 1; i++) {
149 cache |= (1 << (s[i] & 63));
150 }
151 return cache;
152 }
153
154 static int md2Utf16(MetaAccessProvider metaAccess, byte[] target) {
155 int c = target.length / 2;
156 if (c == 0) {
157 return 0;
158 }
159 long base = metaAccess.getArrayBaseOffset(JavaKind.Byte);
160 char lastChar = UnsafeAccess.UNSAFE.getChar(target, base + (c - 1) * 2);
161 int md2 = c;
162 for (int i = 0; i < c - 1; i++) {
163 char currChar = UnsafeAccess.UNSAFE.getChar(target, base + i * 2);
164 if (currChar == lastChar) {
165 md2 = (c - 1) - i;
166 }
167 }
168 return md2;
169 }
170
171 static long computeCacheUtf16(MetaAccessProvider metaAccess, byte[] s) {
172 int c = s.length / 2;
173 int cache = 0;
174 int i;
175 long base = metaAccess.getArrayBaseOffset(JavaKind.Byte);
176 for (i = 0; i < c - 1; i++) {
177 char currChar = UnsafeAccess.UNSAFE.getChar(s, base + i * 2);
178 cache |= (1 << (currChar & 63));
179 }
180 return cache;
181 }
182
183 @Fold
184 static int byteArrayBaseOffset(@InjectedParameter MetaAccessProvider metaAccess) {
185 return metaAccess.getArrayBaseOffset(JavaKind.Byte);
186 }
187
188 @Fold
189 static int charArrayBaseOffset(@InjectedParameter MetaAccessProvider metaAccess) {
190 return metaAccess.getArrayBaseOffset(JavaKind.Char);
191 }
192
193 /** Marker value for the {@link InjectedParameter} injected parameter. */
194 static final MetaAccessProvider INJECTED = null;
195
196 @Snippet
197 public static int indexOfConstant(char[] source, int sourceOffset, int sourceCount,
198 @ConstantParameter char[] target, int targetOffset, int targetCount,
199 int origFromIndex, @ConstantParameter int md2, @ConstantParameter long cache) {
200 int fromIndex = origFromIndex;
201 if (fromIndex >= sourceCount) {
202 return (targetCount == 0 ? sourceCount : -1);
203 }
204 if (fromIndex < 0) {
205 fromIndex = 0;
206 }
207 if (targetCount == 0) {
208 return fromIndex;
209 }
210
211 int targetCountLess1 = targetCount - 1;
212 int sourceEnd = sourceCount - targetCountLess1;
213
214 long base = charArrayBaseOffset(INJECTED);
215 int lastChar = UnsafeAccess.UNSAFE.getChar(target, base + targetCountLess1 * 2);
216
217 outer_loop: for (long i = sourceOffset + fromIndex; i < sourceEnd;) {
218 int src = UnsafeAccess.UNSAFE.getChar(source, base + (i + targetCountLess1) * 2);
219 if (src == lastChar) {
220 // With random strings and a 4-character alphabet,
221 // reverse matching at this point sets up 0.8% fewer
222 // frames, but (paradoxically) makes 0.3% more probes.
223 // Since those probes are nearer the lastChar probe,
224 // there is may be a net D$ win with reverse matching.
225 // But, reversing loop inhibits unroll of inner loop
226 // for unknown reason. So, does running outer loop from
227 // (sourceOffset - targetCountLess1) to (sourceOffset + sourceCount)
228 if (targetCount <= 8) {
229 ExplodeLoopNode.explodeLoop();
230 }
231 for (long j = 0; j < targetCountLess1; j++) {
232 char sourceChar = UnsafeAccess.UNSAFE.getChar(source, base + (i + j) * 2);
233 if (UnsafeAccess.UNSAFE.getChar(target, base + (targetOffset + j) * 2) != sourceChar) {
234 if ((cache & (1 << sourceChar)) == 0) {
235 if (md2 < j + 1) {
236 i += j + 1;
237 continue outer_loop;
238 }
239 }
240 i += md2;
241 continue outer_loop;
242 }
243 }
244 return (int) (i - sourceOffset);
245 }
246 if ((cache & (1 << src)) == 0) {
247 i += targetCountLess1;
248 }
249 i++;
250 }
251 return -1;
252 }
253
254 @Snippet
255 public static int utf16IndexOfConstant(byte[] source, int sourceCount,
256 @ConstantParameter byte[] target, int targetCount,
257 int origFromIndex, @ConstantParameter int md2, @ConstantParameter long cache) {
258 int fromIndex = origFromIndex;
259 if (fromIndex >= sourceCount) {
260 return (targetCount == 0 ? sourceCount : -1);
261 }
262 if (fromIndex < 0) {
263 fromIndex = 0;
264 }
265 if (targetCount == 0) {
266 return fromIndex;
267 }
268
269 int targetCountLess1 = targetCount - 1;
270 int sourceEnd = sourceCount - targetCountLess1;
271
272 long base = byteArrayBaseOffset(INJECTED);
273 int lastChar = UnsafeAccess.UNSAFE.getChar(target, base + targetCountLess1 * 2);
274
275 outer_loop: for (long i = fromIndex; i < sourceEnd;) {
276 int src = UnsafeAccess.UNSAFE.getChar(source, base + (i + targetCountLess1) * 2);
277 if (src == lastChar) {
278 // With random strings and a 4-character alphabet,
279 // reverse matching at this point sets up 0.8% fewer
280 // frames, but (paradoxically) makes 0.3% more probes.
281 // Since those probes are nearer the lastChar probe,
282 // there is may be a net D$ win with reverse matching.
283 // But, reversing loop inhibits unroll of inner loop
284 // for unknown reason. So, does running outer loop from
285 // (sourceOffset - targetCountLess1) to (sourceOffset + sourceCount)
286 if (targetCount <= 8) {
287 ExplodeLoopNode.explodeLoop();
288 }
289 for (long j = 0; j < targetCountLess1; j++) {
290 char sourceChar = UnsafeAccess.UNSAFE.getChar(source, base + (i + j) * 2);
291 if (UnsafeAccess.UNSAFE.getChar(target, base + j * 2) != sourceChar) {
292 if ((cache & (1 << sourceChar)) == 0) {
293 if (md2 < j + 1) {
294 i += j + 1;
295 continue outer_loop;
296 }
297 }
298 i += md2;
299 continue outer_loop;
300 }
301 }
302 return (int) i;
303 }
304 if ((cache & (1 << src)) == 0) {
305 i += targetCountLess1;
306 }
307 i++;
308 }
309 return -1;
310 }
311
312 @Snippet
313 public static int latin1IndexOfConstant(byte[] source, int sourceCount,
314 @ConstantParameter byte[] target, int targetCount,
315 int origFromIndex, @ConstantParameter int md2, @ConstantParameter long cache) {
316 int fromIndex = origFromIndex;
317 if (fromIndex >= sourceCount) {
318 return (targetCount == 0 ? sourceCount : -1);
319 }
320 if (fromIndex < 0) {
321 fromIndex = 0;
322 }
323 if (targetCount == 0) {
324 return fromIndex;
325 }
326
327 int targetCountLess1 = targetCount - 1;
328 int sourceEnd = sourceCount - targetCountLess1;
329
330 long base = byteArrayBaseOffset(INJECTED);
331 int lastByte = UnsafeAccess.UNSAFE.getByte(target, base + targetCountLess1);
332
333 outer_loop: for (long i = fromIndex; i < sourceEnd;) {
334 int src = UnsafeAccess.UNSAFE.getByte(source, base + i + targetCountLess1);
335 if (src == lastByte) {
336 // With random strings and a 4-character alphabet,
337 // reverse matching at this point sets up 0.8% fewer
338 // frames, but (paradoxically) makes 0.3% more probes.
339 // Since those probes are nearer the lastByte probe,
340 // there is may be a net D$ win with reverse matching.
341 // But, reversing loop inhibits unroll of inner loop
342 // for unknown reason. So, does running outer loop from
343 // (sourceOffset - targetCountLess1) to (sourceOffset + sourceCount)
344 if (targetCount <= 8) {
345 ExplodeLoopNode.explodeLoop();
346 }
347 for (long j = 0; j < targetCountLess1; j++) {
348 byte sourceByte = UnsafeAccess.UNSAFE.getByte(source, base + i + j);
349 if (UnsafeAccess.UNSAFE.getByte(target, base + j) != sourceByte) {
350 if ((cache & (1 << sourceByte)) == 0) {
351 if (md2 < j + 1) {
352 i += j + 1;
353 continue outer_loop;
354 }
355 }
356 i += md2;
357 continue outer_loop;
358 }
359 }
360 return (int) i;
361 }
362 if ((cache & (1 << src)) == 0) {
363 i += targetCountLess1;
364 }
365 i++;
366 }
367 return -1;
368 }
369 }
|
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));
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 }
|