1 /*
2 * Copyright (c) 2016, 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 package org.graalvm.compiler.replacements;
24
25 import static org.graalvm.compiler.replacements.SnippetTemplate.DEFAULT_REPLACER;
26
27 import org.graalvm.compiler.api.replacements.Snippet;
28 import org.graalvm.compiler.api.replacements.Snippet.ConstantParameter;
29 import org.graalvm.compiler.debug.DebugHandlersFactory;
30 import org.graalvm.compiler.api.replacements.SnippetReflectionProvider;
31 import org.graalvm.compiler.nodes.StructuredGraph;
32 import org.graalvm.compiler.nodes.spi.LoweringTool;
33 import org.graalvm.compiler.options.OptionValues;
34 import org.graalvm.compiler.phases.util.Providers;
35 import org.graalvm.compiler.replacements.SnippetTemplate.AbstractTemplates;
36 import org.graalvm.compiler.replacements.SnippetTemplate.Arguments;
37 import org.graalvm.compiler.replacements.SnippetTemplate.SnippetInfo;
38 import org.graalvm.compiler.replacements.nodes.ExplodeLoopNode;
39
40 import jdk.vm.ci.code.TargetDescription;
41 import sun.misc.Unsafe;
42
43 public class ConstantStringIndexOfSnippets implements Snippets {
44 public static class Templates extends AbstractTemplates {
45
46 private final SnippetInfo indexOfConstant = snippet(ConstantStringIndexOfSnippets.class, "indexOfConstant");
47
48 public Templates(OptionValues options, Iterable<DebugHandlersFactory> factories, Providers providers, SnippetReflectionProvider snippetReflection, TargetDescription target) {
49 super(options, factories, providers, snippetReflection, target);
50 }
51
52 public void lower(SnippetLowerableMemoryNode stringIndexOf, LoweringTool tool) {
53 StructuredGraph graph = stringIndexOf.graph();
54 Arguments args = new Arguments(indexOfConstant, graph.getGuardsStage(), tool.getLoweringStage());
55 args.add("source", stringIndexOf.getArgument(0));
56 args.add("sourceOffset", stringIndexOf.getArgument(1));
57 args.add("sourceCount", stringIndexOf.getArgument(2));
58 args.addConst("target", stringIndexOf.getArgument(3));
59 args.add("targetOffset", stringIndexOf.getArgument(4));
60 args.add("targetCount", stringIndexOf.getArgument(5));
61 args.add("origFromIndex", stringIndexOf.getArgument(6));
62 char[] targetCharArray = snippetReflection.asObject(char[].class, stringIndexOf.getArgument(3).asJavaConstant());
63 args.addConst("md2", md2(targetCharArray));
64 args.addConst("cache", computeCache(targetCharArray));
65 template(graph.getDebug(), args).instantiate(providers.getMetaAccess(), stringIndexOf, DEFAULT_REPLACER, args);
66 }
67 }
68
69 static int md2(char[] target) {
70 int c = target.length;
71 if (c == 0) {
72 return 0;
73 }
74 char lastChar = target[c - 1];
75 int md2 = c;
76 for (int i = 0; i < c - 1; i++) {
77 if (target[i] == lastChar) {
78 md2 = (c - 1) - i;
79 }
80 }
81 return md2;
82 }
83
84 static long computeCache(char[] s) {
85 int c = s.length;
86 int cache = 0;
87 int i;
88 for (i = 0; i < c - 1; i++) {
89 cache |= (1 << (s[i] & 63));
90 }
91 return cache;
92 }
93
94 @Snippet
95 public static int indexOfConstant(char[] source, int sourceOffset, int sourceCount,
96 @ConstantParameter char[] target, int targetOffset, int targetCount,
97 int origFromIndex, @ConstantParameter int md2, @ConstantParameter long cache) {
98 int fromIndex = origFromIndex;
99 if (fromIndex >= sourceCount) {
100 return (targetCount == 0 ? sourceCount : -1);
101 }
102 if (fromIndex < 0) {
103 fromIndex = 0;
104 }
105 if (targetCount == 0) {
106 return fromIndex;
107 }
108
109 int targetCountLess1 = targetCount - 1;
110 int sourceEnd = sourceCount - targetCountLess1;
111
112 long base = Unsafe.ARRAY_CHAR_BASE_OFFSET;
113 int lastChar = UnsafeAccess.UNSAFE.getChar(target, base + targetCountLess1 * 2);
114
115 outer_loop: for (long i = sourceOffset + fromIndex; i < sourceEnd;) {
116 int src = UnsafeAccess.UNSAFE.getChar(source, base + (i + targetCountLess1) * 2);
117 if (src == lastChar) {
118 // With random strings and a 4-character alphabet,
119 // reverse matching at this point sets up 0.8% fewer
120 // frames, but (paradoxically) makes 0.3% more probes.
121 // Since those probes are nearer the lastChar probe,
122 // there is may be a net D$ win with reverse matching.
123 // But, reversing loop inhibits unroll of inner loop
124 // for unknown reason. So, does running outer loop from
125 // (sourceOffset - targetCountLess1) to (sourceOffset + sourceCount)
126 if (targetCount <= 8) {
127 ExplodeLoopNode.explodeLoop();
128 }
129 for (long j = 0; j < targetCountLess1; j++) {
130 char sourceChar = UnsafeAccess.UNSAFE.getChar(source, base + (i + j) * 2);
131 if (UnsafeAccess.UNSAFE.getChar(target, base + (targetOffset + j) * 2) != sourceChar) {
132 if ((cache & (1 << sourceChar)) == 0) {
133 if (md2 < j + 1) {
134 i += j + 1;
135 continue outer_loop;
136 }
137 }
138 i += md2;
139 continue outer_loop;
140 }
141 }
142 return (int) (i - sourceOffset);
143 }
144 if ((cache & (1 << src)) == 0) {
145 i += targetCountLess1;
146 }
147 i++;
148 }
149 return -1;
150 }
151 }