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 
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.core.common.spi.ArrayOffsetProvider;
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 
48 public class ConstantStringIndexOfSnippets implements Snippets {
49     public static class Templates extends AbstractTemplates {
50 
51         private final SnippetInfo indexOfConstant = snippet(ConstantStringIndexOfSnippets.class, "indexOfConstant");
52 
Templates(OptionValues options, Iterable<DebugHandlersFactory> factories, Providers providers, SnippetReflectionProvider snippetReflection, TargetDescription target)53         public Templates(OptionValues options, Iterable<DebugHandlersFactory> factories, Providers providers, SnippetReflectionProvider snippetReflection, TargetDescription target) {
54             super(options, factories, providers, snippetReflection, target);
55         }
56 
lower(SnippetLowerableMemoryNode stringIndexOf, LoweringTool tool)57         public void lower(SnippetLowerableMemoryNode stringIndexOf, LoweringTool tool) {
58             StructuredGraph graph = stringIndexOf.graph();
59             Arguments args = new Arguments(indexOfConstant, graph.getGuardsStage(), tool.getLoweringStage());
60             args.add("source", stringIndexOf.getArgument(0));
61             args.add("sourceOffset", stringIndexOf.getArgument(1));
62             args.add("sourceCount", stringIndexOf.getArgument(2));
63             args.addConst("target", stringIndexOf.getArgument(3));
64             args.add("targetOffset", stringIndexOf.getArgument(4));
65             args.add("targetCount", stringIndexOf.getArgument(5));
66             args.add("origFromIndex", stringIndexOf.getArgument(6));
67             char[] targetCharArray = snippetReflection.asObject(char[].class, stringIndexOf.getArgument(3).asJavaConstant());
68             args.addConst("md2", md2(targetCharArray));
69             args.addConst("cache", computeCache(targetCharArray));
70             template(stringIndexOf, args).instantiate(providers.getMetaAccess(), stringIndexOf, DEFAULT_REPLACER, args);
71         }
72     }
73 
md2(char[] target)74     static int md2(char[] target) {
75         int c = target.length;
76         if (c == 0) {
77             return 0;
78         }
79         char lastChar = target[c - 1];
80         int md2 = c;
81         for (int i = 0; i < c - 1; i++) {
82             if (target[i] == lastChar) {
83                 md2 = (c - 1) - i;
84             }
85         }
86         return md2;
87     }
88 
computeCache(char[] s)89     static long computeCache(char[] s) {
90         int c = s.length;
91         int cache = 0;
92         int i;
93         for (i = 0; i < c - 1; i++) {
94             cache |= (1 << (s[i] & 63));
95         }
96         return cache;
97     }
98 
99     @Fold
charArrayBaseOffset(@njectedParameter ArrayOffsetProvider arrayOffsetProvider)100     static int charArrayBaseOffset(@InjectedParameter ArrayOffsetProvider arrayOffsetProvider) {
101         return arrayOffsetProvider.arrayBaseOffset(JavaKind.Char);
102     }
103 
104     /** Marker value for the {@link InjectedParameter} injected parameter. */
105     static final ArrayOffsetProvider INJECTED = null;
106 
107     @Snippet
indexOfConstant(char[] source, int sourceOffset, int sourceCount, @ConstantParameter char[] target, int targetOffset, int targetCount, int origFromIndex, @ConstantParameter int md2, @ConstantParameter long cache)108     public static int indexOfConstant(char[] source, int sourceOffset, int sourceCount,
109                     @ConstantParameter char[] target, int targetOffset, int targetCount,
110                     int origFromIndex, @ConstantParameter int md2, @ConstantParameter long cache) {
111         int fromIndex = origFromIndex;
112         if (fromIndex >= sourceCount) {
113             return (targetCount == 0 ? sourceCount : -1);
114         }
115         if (fromIndex < 0) {
116             fromIndex = 0;
117         }
118         if (targetCount == 0) {
119             return fromIndex;
120         }
121 
122         int targetCountLess1 = targetCount - 1;
123         int sourceEnd = sourceCount - targetCountLess1;
124 
125         long base = charArrayBaseOffset(INJECTED);
126         int lastChar = UnsafeAccess.UNSAFE.getChar(target, base + targetCountLess1 * 2);
127 
128         outer_loop: for (long i = sourceOffset + fromIndex; i < sourceEnd;) {
129             int src = UnsafeAccess.UNSAFE.getChar(source, base + (i + targetCountLess1) * 2);
130             if (src == lastChar) {
131                 // With random strings and a 4-character alphabet,
132                 // reverse matching at this point sets up 0.8% fewer
133                 // frames, but (paradoxically) makes 0.3% more probes.
134                 // Since those probes are nearer the lastChar probe,
135                 // there is may be a net D$ win with reverse matching.
136                 // But, reversing loop inhibits unroll of inner loop
137                 // for unknown reason. So, does running outer loop from
138                 // (sourceOffset - targetCountLess1) to (sourceOffset + sourceCount)
139                 if (targetCount <= 8) {
140                     ExplodeLoopNode.explodeLoop();
141                 }
142                 for (long j = 0; j < targetCountLess1; j++) {
143                     char sourceChar = UnsafeAccess.UNSAFE.getChar(source, base + (i + j) * 2);
144                     if (UnsafeAccess.UNSAFE.getChar(target, base + (targetOffset + j) * 2) != sourceChar) {
145                         if ((cache & (1 << sourceChar)) == 0) {
146                             if (md2 < j + 1) {
147                                 i += j + 1;
148                                 continue outer_loop;
149                             }
150                         }
151                         i += md2;
152                         continue outer_loop;
153                     }
154                 }
155                 return (int) (i - sourceOffset);
156             }
157             if ((cache & (1 << src)) == 0) {
158                 i += targetCountLess1;
159             }
160             i++;
161         }
162         return -1;
163     }
164 }
165