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 }