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