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 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)); 69 char[] targetCharArray = snippetReflection.asObject(char[].class, stringIndexOf.getArgument(3).asJavaConstant()); 70 args.addConst("md2", md2(targetCharArray)); 71 args.addConst("cache", computeCache(targetCharArray)); 72 template(stringIndexOf, args).instantiate(providers.getMetaAccess(), stringIndexOf, DEFAULT_REPLACER, args); 73 } 74 75 public void lowerLatin1(SnippetLowerableMemoryNode latin1IndexOf, LoweringTool tool) { 76 StructuredGraph graph = latin1IndexOf.graph(); 77 Arguments args = new Arguments(latin1IndexOfConstant, graph.getGuardsStage(), tool.getLoweringStage()); 78 args.add("source", latin1IndexOf.getArgument(0)); 79 args.add("sourceCount", latin1IndexOf.getArgument(1)); 80 args.addConst("target", latin1IndexOf.getArgument(2)); 81 args.add("targetCount", latin1IndexOf.getArgument(3)); 82 args.add("origFromIndex", latin1IndexOf.getArgument(4)); 83 byte[] targetByteArray = snippetReflection.asObject(byte[].class, latin1IndexOf.getArgument(2).asJavaConstant()); 84 args.addConst("md2", md2(targetByteArray)); 85 args.addConst("cache", computeCache(targetByteArray)); 86 template(latin1IndexOf, args).instantiate(providers.getMetaAccess(), latin1IndexOf, DEFAULT_REPLACER, args); 87 } 88 89 public void lowerUTF16(SnippetLowerableMemoryNode utf16IndexOf, LoweringTool tool) { 90 StructuredGraph graph = utf16IndexOf.graph(); 91 Arguments args = new Arguments(utf16IndexOfConstant, graph.getGuardsStage(), tool.getLoweringStage()); 92 args.add("source", utf16IndexOf.getArgument(0)); 93 args.add("sourceCount", utf16IndexOf.getArgument(1)); 94 args.addConst("target", utf16IndexOf.getArgument(2)); 95 args.add("targetCount", utf16IndexOf.getArgument(3)); 96 args.add("origFromIndex", utf16IndexOf.getArgument(4)); 97 byte[] targetByteArray = snippetReflection.asObject(byte[].class, utf16IndexOf.getArgument(2).asJavaConstant()); 98 args.addConst("md2", md2Utf16(targetByteArray)); 99 args.addConst("cache", computeCacheUtf16(targetByteArray)); 100 template(utf16IndexOf, args).instantiate(providers.getMetaAccess(), utf16IndexOf, DEFAULT_REPLACER, args); 101 } 102 } 103 104 static int md2(char[] target) { 105 int c = target.length; 106 if (c == 0) { 107 return 0; 108 } 109 char lastChar = target[c - 1]; 110 int md2 = c; 111 for (int i = 0; i < c - 1; i++) { 112 if (target[i] == lastChar) { 113 md2 = (c - 1) - i; 114 } 115 } 116 return md2; 117 } 118 119 static long computeCache(char[] s) { 120 int c = s.length; 121 int cache = 0; 122 int i; 123 for (i = 0; i < c - 1; i++) { 124 cache |= (1 << (s[i] & 63)); 125 } 126 return cache; 127 } 128 129 static int md2(byte[] target) { 130 int c = target.length; 131 if (c == 0) { 132 return 0; 133 } 134 byte lastByte = target[c - 1]; 135 int md2 = c; 136 for (int i = 0; i < c - 1; i++) { 137 if (target[i] == lastByte) { 138 md2 = (c - 1) - i; 139 } 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(byte[] target) { 155 int c = target.length / 2; 156 if (c == 0) { 157 return 0; 158 } 159 long base = UnsafeAccess.UNSAFE.arrayBaseOffset(byte[].class); 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(byte[] s) { 172 int c = s.length / 2; 173 int cache = 0; 174 int i; 175 long base = UnsafeAccess.UNSAFE.arrayBaseOffset(byte[].class); 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 ArrayOffsetProvider arrayOffsetProvider) { 185 return arrayOffsetProvider.arrayBaseOffset(JavaKind.Byte); 186 } 187 188 @Fold 189 static int charArrayBaseOffset(@InjectedParameter ArrayOffsetProvider arrayOffsetProvider) { 190 return arrayOffsetProvider.arrayBaseOffset(JavaKind.Char); 191 } 192 193 /** Marker value for the {@link InjectedParameter} injected parameter. */ 194 static final ArrayOffsetProvider 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 }