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 java.util.FormattableFlags.ALTERNATE;
26 import static org.graalvm.compiler.debug.Debug.applyFormattingFlagsAndWidth;
27 import static org.graalvm.compiler.debug.GraalDebugConfig.Options.DebugStubsAndSnippets;
28 import static org.graalvm.compiler.graph.iterators.NodePredicates.isNotA;
29 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_IGNORED;
30 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_IGNORED;
31 import static org.graalvm.compiler.phases.common.DeadCodeEliminationPhase.Optionality.Required;
32 import static org.graalvm.word.LocationIdentity.any;
33
34 import java.lang.reflect.Array;
35 import java.lang.reflect.Method;
36 import java.util.ArrayList;
37 import java.util.Arrays;
38 import java.util.Collection;
39 import java.util.Collections;
40 import java.util.Formattable;
41 import java.util.Formatter;
42 import java.util.LinkedHashMap;
43 import java.util.List;
44 import java.util.Map;
45 import java.util.concurrent.atomic.AtomicReference;
46 import java.util.function.Predicate;
47
48 import org.graalvm.compiler.api.replacements.Snippet;
49 import org.graalvm.compiler.api.replacements.Snippet.ConstantParameter;
50 import org.graalvm.compiler.api.replacements.Snippet.NonNullParameter;
51 import org.graalvm.compiler.api.replacements.Snippet.VarargsParameter;
52 import org.graalvm.compiler.api.replacements.SnippetReflectionProvider;
53 import org.graalvm.compiler.core.common.GraalOptions;
54 import org.graalvm.compiler.core.common.type.Stamp;
55 import org.graalvm.compiler.core.common.type.StampFactory;
56 import org.graalvm.compiler.core.common.type.StampPair;
57 import org.graalvm.compiler.core.common.type.TypeReference;
58 import org.graalvm.compiler.debug.Debug;
59 import org.graalvm.compiler.debug.Debug.Scope;
60 import org.graalvm.compiler.debug.internal.DebugScope;
61 import org.graalvm.compiler.debug.DebugCloseable;
62 import org.graalvm.compiler.debug.DebugConfig;
63 import org.graalvm.compiler.debug.DebugCounter;
64 import org.graalvm.compiler.debug.DebugTimer;
65 import org.graalvm.compiler.debug.GraalError;
66 import org.graalvm.compiler.graph.Graph.Mark;
67 import org.graalvm.compiler.graph.Node;
68 import org.graalvm.compiler.graph.NodeClass;
69 import org.graalvm.compiler.graph.Position;
70 import org.graalvm.compiler.loop.LoopEx;
71 import org.graalvm.compiler.loop.LoopsData;
72 import org.graalvm.compiler.loop.phases.LoopTransformations;
73 import org.graalvm.compiler.nodeinfo.InputType;
74 import org.graalvm.compiler.nodeinfo.NodeInfo;
75 import org.graalvm.compiler.nodes.AbstractBeginNode;
76 import org.graalvm.compiler.nodes.AbstractMergeNode;
77 import org.graalvm.compiler.nodes.ConstantNode;
78 import org.graalvm.compiler.nodes.ControlSinkNode;
79 import org.graalvm.compiler.nodes.DeoptimizingNode;
80 import org.graalvm.compiler.nodes.FixedNode;
81 import org.graalvm.compiler.nodes.FixedWithNextNode;
82 import org.graalvm.compiler.nodes.FrameState;
83 import org.graalvm.compiler.nodes.LoopBeginNode;
84 import org.graalvm.compiler.nodes.MergeNode;
85 import org.graalvm.compiler.nodes.ParameterNode;
210 if (localVariableTable != null) {
211 for (int i = 0; i < names.length; i++) {
212 Local local = localVariableTable.getLocal(slotIdx, 0);
213 if (local != null) {
214 names[i] = local.getName();
215 }
216 JavaKind kind = method.getSignature().getParameterKind(i);
217 slotIdx += kind.getSlotCount();
218 }
219 }
220 }
221 return true;
222 }
223 }
224
225 /**
226 * Times instantiations of all templates derived form this snippet.
227 *
228 * @see SnippetTemplate#instantiationTimer
229 */
230 private final DebugTimer instantiationTimer;
231
232 /**
233 * Counts instantiations of all templates derived from this snippet.
234 *
235 * @see SnippetTemplate#instantiationCounter
236 */
237 private final DebugCounter instantiationCounter;
238
239 protected abstract Lazy lazy();
240
241 protected SnippetInfo(ResolvedJavaMethod method, LocationIdentity[] privateLocations) {
242 this.method = method;
243 this.privateLocations = privateLocations;
244 instantiationCounter = Debug.counter("SnippetInstantiationCount[%s]", method.getName());
245 instantiationTimer = Debug.timer("SnippetInstantiationTime[%s]", method.getName());
246 assert method.isStatic() : "snippet method must be static: " + method.format("%H.%n");
247 }
248
249 public ResolvedJavaMethod getMethod() {
250 return method;
251 }
252
253 public int getParameterCount() {
254 return lazy().constantParameters.length;
255 }
256
257 public void setOriginalMethod(ResolvedJavaMethod original) {
258 this.original = original;
259 }
260
261 public boolean isConstantParameter(int paramIdx) {
262 return lazy().constantParameters[paramIdx];
263 }
264
265 public boolean isVarargsParameter(int paramIdx) {
545 if (!method.equals(other.method)) {
546 return false;
547 }
548 if (guardsStage != other.guardsStage || loweringStage != other.loweringStage) {
549 return false;
550 }
551 for (int i = 0; i < values.length; i++) {
552 if (values[i] != null && !values[i].equals(other.values[i])) {
553 return false;
554 }
555 }
556 return true;
557 }
558
559 @Override
560 public int hashCode() {
561 return hash;
562 }
563 }
564
565 private static final DebugTimer SnippetTemplateCreationTime = Debug.timer("SnippetTemplateCreationTime");
566 private static final DebugCounter SnippetTemplates = Debug.counter("SnippetTemplateCount");
567
568 static class Options {
569 @Option(help = "Use a LRU cache for snippet templates.")//
570 static final OptionKey<Boolean> UseSnippetTemplateCache = new OptionKey<>(true);
571
572 @Option(help = "")//
573 static final OptionKey<Integer> MaxTemplatesPerSnippet = new OptionKey<>(50);
574 }
575
576 /**
577 * Base class for snippet classes. It provides a cache for {@link SnippetTemplate}s.
578 */
579 public abstract static class AbstractTemplates implements org.graalvm.compiler.api.replacements.SnippetTemplateCache {
580
581 protected final OptionValues options;
582 protected final Providers providers;
583 protected final SnippetReflectionProvider snippetReflection;
584 protected final TargetDescription target;
585 private final Map<CacheKey, SnippetTemplate> templates;
586
587 protected AbstractTemplates(OptionValues options, Providers providers, SnippetReflectionProvider snippetReflection, TargetDescription target) {
588 this.options = options;
589 this.providers = providers;
590 this.snippetReflection = snippetReflection;
591 this.target = target;
592 if (Options.UseSnippetTemplateCache.getValue(options)) {
593 int size = Options.MaxTemplatesPerSnippet.getValue(options);
594 this.templates = Collections.synchronizedMap(new LRUCache<>(size, size));
595 } else {
596 this.templates = null;
597 }
598 }
599
600 public static Method findMethod(Class<? extends Snippets> declaringClass, String methodName, Method except) {
601 for (Method m : declaringClass.getDeclaredMethods()) {
602 if (m.getName().equals(methodName) && !m.equals(except)) {
603 return m;
604 }
605 }
606 return null;
607 }
608
609 /**
610 * Finds the unique method in {@code declaringClass} named {@code methodName} annotated by
611 * {@link Snippet} and returns a {@link SnippetInfo} value describing it. There must be
612 * exactly one snippet method in {@code declaringClass}.
613 */
614 protected SnippetInfo snippet(Class<? extends Snippets> declaringClass, String methodName, LocationIdentity... initialPrivateLocations) {
615 assert methodName != null;
616 Method method = findMethod(declaringClass, methodName, null);
617 assert method != null : "did not find @" + Snippet.class.getSimpleName() + " method in " + declaringClass + " named " + methodName;
618 assert method.getAnnotation(Snippet.class) != null : method + " must be annotated with @" + Snippet.class.getSimpleName();
619 assert findMethod(declaringClass, methodName, method) == null : "found more than one method named " + methodName + " in " + declaringClass;
620 ResolvedJavaMethod javaMethod = providers.getMetaAccess().lookupJavaMethod(method);
621 providers.getReplacements().registerSnippet(javaMethod);
622 LocationIdentity[] privateLocations = GraalOptions.SnippetCounters.getValue(options) ? SnippetCounterNode.addSnippetCounters(initialPrivateLocations) : initialPrivateLocations;
623 if (GraalOptions.EagerSnippets.getValue(options)) {
624 return new EagerSnippetInfo(javaMethod, privateLocations);
625 } else {
626 return new LazySnippetInfo(javaMethod, privateLocations);
627 }
628 }
629
630 /**
631 * Gets a template for a given key, creating it first if necessary.
632 */
633 @SuppressWarnings("try")
634 protected SnippetTemplate template(final Arguments args) {
635 SnippetTemplate template = Options.UseSnippetTemplateCache.getValue(options) && args.cacheable ? templates.get(args.cacheKey) : null;
636 if (template == null) {
637 SnippetTemplates.increment();
638 DebugConfig config = DebugStubsAndSnippets.getValue(options) ? DebugScope.getConfig() : Debug.silentConfig();
639 try (DebugCloseable a = SnippetTemplateCreationTime.start(); Scope s = Debug.sandbox("SnippetSpecialization", config, args.info.method)) {
640 template = new SnippetTemplate(options, providers, snippetReflection, args);
641 if (Options.UseSnippetTemplateCache.getValue(options) && args.cacheable) {
642 templates.put(args.cacheKey, template);
643 }
644 } catch (Throwable e) {
645 throw Debug.handle(e);
646 }
647 }
648 return template;
649 }
650 }
651
652 private static final class LRUCache<K, V> extends LinkedHashMap<K, V> {
653 private static final long serialVersionUID = 1L;
654 private final int maxCacheSize;
655
656 LRUCache(int initialCapacity, int maxCacheSize) {
657 super(initialCapacity, 0.75F, true);
658 this.maxCacheSize = maxCacheSize;
659 }
660
661 @Override
662 protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
663 return size() > maxCacheSize;
664 }
665 }
669 private static final Object CONSTANT_PARAMETER = "CONSTANT_PARAMETER";
670
671 /**
672 * Determines if any parameter of a given method is annotated with {@link ConstantParameter}.
673 */
674 public static boolean hasConstantParameter(ResolvedJavaMethod method) {
675 for (ConstantParameter p : method.getParameterAnnotations(ConstantParameter.class)) {
676 if (p != null) {
677 return true;
678 }
679 }
680 return false;
681 }
682
683 private final SnippetReflectionProvider snippetReflection;
684
685 /**
686 * Creates a snippet template.
687 */
688 @SuppressWarnings("try")
689 protected SnippetTemplate(OptionValues options, final Providers providers, SnippetReflectionProvider snippetReflection, Arguments args) {
690 this.snippetReflection = snippetReflection;
691 this.info = args.info;
692
693 Object[] constantArgs = getConstantArgs(args);
694 StructuredGraph snippetGraph = providers.getReplacements().getSnippet(args.info.method, args.info.original, constantArgs);
695 instantiationTimer = Debug.timer("SnippetTemplateInstantiationTime[%#s]", args);
696 instantiationCounter = Debug.counter("SnippetTemplateInstantiationCount[%#s]", args);
697
698 ResolvedJavaMethod method = snippetGraph.method();
699 Signature signature = method.getSignature();
700
701 PhaseContext phaseContext = new PhaseContext(providers);
702
703 // Copy snippet graph, replacing constant parameters with given arguments
704 final StructuredGraph snippetCopy = new StructuredGraph.Builder(options).name(snippetGraph.name).method(snippetGraph.method()).build();
705
706 try (Debug.Scope scope = Debug.scope("SpecializeSnippet", snippetCopy)) {
707 if (!snippetGraph.isUnsafeAccessTrackingEnabled()) {
708 snippetCopy.disableUnsafeAccessTracking();
709 }
710
711 EconomicMap<Node, Node> nodeReplacements = EconomicMap.create(Equivalence.IDENTITY);
712 nodeReplacements.put(snippetGraph.start(), snippetCopy.start());
713
714 MetaAccessProvider metaAccess = providers.getMetaAccess();
715 assert checkTemplate(metaAccess, args, method, signature);
716
717 int parameterCount = args.info.getParameterCount();
718 VarargsPlaceholderNode[] placeholders = new VarargsPlaceholderNode[parameterCount];
719
720 for (int i = 0; i < parameterCount; i++) {
721 ParameterNode parameter = snippetGraph.getParameter(i);
722 if (parameter != null) {
723 if (args.info.isConstantParameter(i)) {
724 Object arg = args.values[i];
725 JavaKind kind = signature.getParameterKind(i);
726 ConstantNode constantNode;
731 constantNode = ConstantNode.forConstant((JavaConstant) arg, metaAccess, snippetCopy);
732 } else {
733 constantNode = ConstantNode.forConstant(stamp, (Constant) arg, metaAccess, snippetCopy);
734 }
735 } else {
736 constantNode = ConstantNode.forConstant(snippetReflection.forBoxed(kind, arg), metaAccess, snippetCopy);
737 }
738 nodeReplacements.put(parameter, constantNode);
739 } else if (args.info.isVarargsParameter(i)) {
740 Varargs varargs = (Varargs) args.values[i];
741 VarargsPlaceholderNode placeholder = snippetCopy.unique(new VarargsPlaceholderNode(varargs, providers.getMetaAccess()));
742 nodeReplacements.put(parameter, placeholder);
743 placeholders[i] = placeholder;
744 } else if (args.info.isNonNullParameter(i)) {
745 parameter.setStamp(parameter.stamp().join(StampFactory.objectNonNull()));
746 }
747 }
748 }
749 snippetCopy.addDuplicates(snippetGraph.getNodes(), snippetGraph, snippetGraph.getNodeCount(), nodeReplacements);
750
751 Debug.dump(Debug.INFO_LEVEL, snippetCopy, "Before specialization");
752
753 // Gather the template parameters
754 parameters = new Object[parameterCount];
755 for (int i = 0; i < parameterCount; i++) {
756 if (args.info.isConstantParameter(i)) {
757 parameters[i] = CONSTANT_PARAMETER;
758 } else if (args.info.isVarargsParameter(i)) {
759 assert snippetCopy.getParameter(i) == null;
760 Varargs varargs = (Varargs) args.values[i];
761 int length = varargs.length;
762 ParameterNode[] params = new ParameterNode[length];
763 Stamp stamp = varargs.stamp;
764 for (int j = 0; j < length; j++) {
765 // Use a decimal friendly numbering make it more obvious how values map
766 assert parameterCount < 10000;
767 int idx = (i + 1) * 10000 + j;
768 assert idx >= parameterCount : "collision in parameter numbering";
769 ParameterNode local = snippetCopy.addOrUnique(new ParameterNode(idx, StampPair.createSingle(stamp)));
770 params[j] = local;
771 }
772 parameters[i] = params;
773
774 VarargsPlaceholderNode placeholder = placeholders[i];
775 if (placeholder != null) {
776 for (Node usage : placeholder.usages().snapshot()) {
777 if (usage instanceof LoadIndexedNode) {
778 LoadIndexedNode loadIndexed = (LoadIndexedNode) usage;
779 Debug.dump(Debug.INFO_LEVEL, snippetCopy, "Before replacing %s", loadIndexed);
780 LoadSnippetVarargParameterNode loadSnippetParameter = snippetCopy.add(new LoadSnippetVarargParameterNode(params, loadIndexed.index(), loadIndexed.stamp()));
781 snippetCopy.replaceFixedWithFixed(loadIndexed, loadSnippetParameter);
782 Debug.dump(Debug.INFO_LEVEL, snippetCopy, "After replacing %s", loadIndexed);
783 } else if (usage instanceof StoreIndexedNode) {
784 /*
785 * The template lowering doesn't really treat this as an array so
786 * you can't store back into the varargs. Allocate your own array if
787 * you really need this and EA should eliminate it.
788 */
789 throw new GraalError("Can't store into VarargsParameter array");
790 }
791 }
792 }
793 } else {
794 ParameterNode local = snippetCopy.getParameter(i);
795 if (local == null) {
796 // Parameter value was eliminated
797 parameters[i] = UNUSED_PARAMETER;
798 } else {
799 parameters[i] = local;
800 }
801 }
802 }
803
804 explodeLoops(snippetCopy, phaseContext);
805
806 GuardsStage guardsStage = args.cacheKey.guardsStage;
807 // Perform lowering on the snippet
808 if (!guardsStage.allowsFloatingGuards()) {
809 new GuardLoweringPhase().apply(snippetCopy, null);
810 }
811 snippetCopy.setGuardsStage(guardsStage);
812 try (Scope s = Debug.scope("LoweringSnippetTemplate", snippetCopy)) {
813 new LoweringPhase(new CanonicalizerPhase(), args.cacheKey.loweringStage).apply(snippetCopy, phaseContext);
814 } catch (Throwable e) {
815 throw Debug.handle(e);
816 }
817
818 ArrayList<StateSplit> curSideEffectNodes = new ArrayList<>();
819 ArrayList<DeoptimizingNode> curDeoptNodes = new ArrayList<>();
820 ArrayList<ValueNode> curPlaceholderStampedNodes = new ArrayList<>();
821 for (Node node : snippetCopy.getNodes()) {
822 if (node instanceof ValueNode) {
823 ValueNode valueNode = (ValueNode) node;
824 if (valueNode.stamp() == PlaceholderStamp.singleton()) {
825 curPlaceholderStampedNodes.add(valueNode);
826 }
827 }
828
829 if (node instanceof StateSplit) {
830 StateSplit stateSplit = (StateSplit) node;
831 FrameState frameState = stateSplit.stateAfter();
832 if (stateSplit.hasSideEffect()) {
833 curSideEffectNodes.add((StateSplit) node);
834 }
835 if (frameState != null) {
880 // Remove the useless memory map
881 MemoryMapNode memoryMap = null;
882 for (ReturnNode retNode : snippet.getNodes(ReturnNode.TYPE)) {
883 if (memoryMap == null) {
884 memoryMap = retNode.getMemoryMap();
885 } else {
886 assert memoryMap == retNode.getMemoryMap();
887 }
888 retNode.setMemoryMap(null);
889 }
890 memoryMap.safeDelete();
891 }
892 if (needsAnchor) {
893 snippetCopy.addAfterFixed(snippetCopy.start(), anchor);
894 this.memoryAnchor = anchor;
895 } else {
896 anchor.safeDelete();
897 this.memoryAnchor = null;
898 }
899 }
900 Debug.dump(Debug.INFO_LEVEL, snippet, "SnippetTemplate after fixing memory anchoring");
901
902 List<ReturnNode> returnNodes = snippet.getNodes(ReturnNode.TYPE).snapshot();
903 if (returnNodes.isEmpty()) {
904 this.returnNode = null;
905 } else if (returnNodes.size() == 1) {
906 this.returnNode = returnNodes.get(0);
907 } else {
908 AbstractMergeNode merge = snippet.add(new MergeNode());
909 List<MemoryMapNode> memMaps = new ArrayList<>();
910 for (ReturnNode retNode : returnNodes) {
911 MemoryMapNode memoryMapNode = retNode.getMemoryMap();
912 if (memoryMapNode != null) {
913 memMaps.add(memoryMapNode);
914 }
915 }
916
917 ValueNode returnValue = InliningUtil.mergeReturns(merge, returnNodes);
918 this.returnNode = snippet.add(new ReturnNode(returnValue));
919 if (!memMaps.isEmpty()) {
920 MemoryMapImpl mmap = FloatingReadPhase.mergeMemoryMaps(merge, memMaps);
924 if (mm != memoryMap && mm.isAlive()) {
925 assert mm.hasNoUsages();
926 GraphUtil.killWithUnusedFloatingInputs(mm);
927 }
928 }
929 }
930 merge.setNext(this.returnNode);
931 }
932
933 this.sideEffectNodes = curSideEffectNodes;
934 this.deoptNodes = curDeoptNodes;
935 this.placeholderStampedNodes = curPlaceholderStampedNodes;
936
937 nodes = new ArrayList<>(snippet.getNodeCount());
938 for (Node node : snippet.getNodes()) {
939 if (node != entryPointNode && node != entryPointNode.stateAfter()) {
940 nodes.add(node);
941 }
942 }
943
944 Debug.counter("SnippetTemplateNodeCount[%#s]", args).add(nodes.size());
945 Debug.dump(Debug.INFO_LEVEL, snippet, "SnippetTemplate final state");
946
947 } catch (Throwable ex) {
948 throw Debug.handle(ex);
949 }
950 }
951
952 public static void explodeLoops(final StructuredGraph snippetCopy, PhaseContext phaseContext) {
953 // Do any required loop explosion
954 boolean exploded = false;
955 do {
956 exploded = false;
957 ExplodeLoopNode explodeLoop = snippetCopy.getNodes().filter(ExplodeLoopNode.class).first();
958 if (explodeLoop != null) { // Earlier canonicalization may have removed the loop
959 // altogether
960 LoopBeginNode loopBegin = explodeLoop.findLoopBegin();
961 if (loopBegin != null) {
962 LoopEx loop = new LoopsData(snippetCopy).loop(loopBegin);
963 Mark mark = snippetCopy.getMark();
964 LoopTransformations.fullUnroll(loop, phaseContext, new CanonicalizerPhase());
965 new CanonicalizerPhase().applyIncremental(snippetCopy, phaseContext, mark);
966 loop.deleteUnusedNodes();
967 }
968 GraphUtil.removeFixedWithUnusedInputs(explodeLoop);
1048 * Nodes that inherit a deoptimization {@link FrameState} from the replacee during
1049 * instantiation.
1050 */
1051 private final ArrayList<DeoptimizingNode> deoptNodes;
1052
1053 /**
1054 * Nodes that have a stamp originating from a {@link Placeholder}.
1055 */
1056 private final ArrayList<ValueNode> placeholderStampedNodes;
1057
1058 /**
1059 * The nodes to be inlined when this specialization is instantiated.
1060 */
1061 private final ArrayList<Node> nodes;
1062
1063 /**
1064 * Times instantiations of this template.
1065 *
1066 * @see SnippetInfo#instantiationTimer
1067 */
1068 private final DebugTimer instantiationTimer;
1069
1070 /**
1071 * Counts instantiations of this template.
1072 *
1073 * @see SnippetInfo#instantiationCounter
1074 */
1075 private final DebugCounter instantiationCounter;
1076
1077 /**
1078 * Gets the instantiation-time bindings to this template's parameters.
1079 *
1080 * @return the map that will be used to bind arguments to parameters when inlining this template
1081 */
1082 private EconomicMap<Node, Node> bind(StructuredGraph replaceeGraph, MetaAccessProvider metaAccess, Arguments args) {
1083 EconomicMap<Node, Node> replacements = EconomicMap.create(Equivalence.IDENTITY);
1084 assert args.info.getParameterCount() == parameters.length : "number of args (" + args.info.getParameterCount() + ") != number of parameters (" + parameters.length + ")";
1085 for (int i = 0; i < parameters.length; i++) {
1086 Object parameter = parameters[i];
1087 assert parameter != null : this + " has no parameter named " + args.info.getParameterName(i);
1088 Object argument = args.values[i];
1089 if (parameter instanceof ParameterNode) {
1090 if (argument instanceof ValueNode) {
1091 replacements.put((ParameterNode) parameter, (ValueNode) argument);
1092 } else {
1093 JavaKind kind = ((ParameterNode) parameter).getStackKind();
1094 assert argument != null || kind == JavaKind.Object : this + " cannot accept null for non-object parameter named " + args.info.getParameterName(i);
1095 JavaConstant constant = forBoxed(argument, kind);
1370 * @param args the arguments to be bound to the flattened positional parameters of the snippet
1371 * @return the map of duplicated nodes (original -> duplicate)
1372 */
1373 @SuppressWarnings("try")
1374 public UnmodifiableEconomicMap<Node, Node> instantiate(MetaAccessProvider metaAccess, FixedNode replacee, UsageReplacer replacer, Arguments args) {
1375 return instantiate(metaAccess, replacee, replacer, args, true);
1376 }
1377
1378 /**
1379 * Replaces a given fixed node with this specialized snippet.
1380 *
1381 * @param metaAccess
1382 * @param replacee the node that will be replaced
1383 * @param replacer object that replaces the usages of {@code replacee}
1384 * @param args the arguments to be bound to the flattened positional parameters of the snippet
1385 * @param killReplacee is true, the replacee node is deleted
1386 * @return the map of duplicated nodes (original -> duplicate)
1387 */
1388 @SuppressWarnings("try")
1389 public UnmodifiableEconomicMap<Node, Node> instantiate(MetaAccessProvider metaAccess, FixedNode replacee, UsageReplacer replacer, Arguments args, boolean killReplacee) {
1390 assert assertSnippetKills(replacee);
1391 try (DebugCloseable a = args.info.instantiationTimer.start(); DebugCloseable b = instantiationTimer.start()) {
1392 args.info.instantiationCounter.increment();
1393 instantiationCounter.increment();
1394 // Inline the snippet nodes, replacing parameters with the given args in the process
1395 StartNode entryPointNode = snippet.start();
1396 FixedNode firstCFGNode = entryPointNode.next();
1397 StructuredGraph replaceeGraph = replacee.graph();
1398 EconomicMap<Node, Node> replacements = bind(replaceeGraph, metaAccess, args);
1399 replacements.put(entryPointNode, AbstractBeginNode.prevBegin(replacee));
1400 UnmodifiableEconomicMap<Node, Node> duplicates = replaceeGraph.addDuplicates(nodes, snippet, snippet.getNodeCount(), replacements);
1401 Debug.dump(Debug.DETAILED_LEVEL, replaceeGraph, "After inlining snippet %s", snippet.method());
1402
1403 // Re-wire the control flow graph around the replacee
1404 FixedNode firstCFGNodeDuplicate = (FixedNode) duplicates.get(firstCFGNode);
1405 replacee.replaceAtPredecessor(firstCFGNodeDuplicate);
1406
1407 rewireFrameStates(replacee, duplicates);
1408
1409 if (replacee instanceof DeoptimizingNode) {
1410 DeoptimizingNode replaceeDeopt = (DeoptimizingNode) replacee;
1411
1412 FrameState stateBefore = null;
1413 FrameState stateDuring = null;
1414 FrameState stateAfter = null;
1415 if (replaceeDeopt.canDeoptimize()) {
1416 if (replaceeDeopt instanceof DeoptimizingNode.DeoptBefore) {
1417 stateBefore = ((DeoptimizingNode.DeoptBefore) replaceeDeopt).stateBefore();
1418 }
1419 if (replaceeDeopt instanceof DeoptimizingNode.DeoptDuring) {
1420 stateDuring = ((DeoptimizingNode.DeoptDuring) replaceeDeopt).stateDuring();
1421 }
1469 } else {
1470 assert returnValue != null || replacee.hasNoUsages();
1471 replacer.replace(replacee, returnValue);
1472 }
1473 if (returnDuplicate.isAlive()) {
1474 FixedNode next = null;
1475 if (replacee instanceof FixedWithNextNode) {
1476 FixedWithNextNode fwn = (FixedWithNextNode) replacee;
1477 next = fwn.next();
1478 fwn.setNext(null);
1479 }
1480 returnDuplicate.replaceAndDelete(next);
1481 }
1482 }
1483
1484 if (killReplacee) {
1485 // Remove the replacee from its graph
1486 GraphUtil.killCFG(replacee);
1487 }
1488
1489 Debug.dump(Debug.DETAILED_LEVEL, replaceeGraph, "After lowering %s with %s", replacee, this);
1490 return duplicates;
1491 }
1492 }
1493
1494 private void propagateStamp(Node node) {
1495 if (node instanceof PhiNode) {
1496 PhiNode phi = (PhiNode) node;
1497 if (phi.inferStamp()) {
1498 for (Node usage : node.usages()) {
1499 propagateStamp(usage);
1500 }
1501 }
1502 }
1503 }
1504
1505 private void updateStamps(ValueNode replacee, UnmodifiableEconomicMap<Node, Node> duplicates) {
1506 for (ValueNode node : placeholderStampedNodes) {
1507 ValueNode dup = (ValueNode) duplicates.get(node);
1508 Stamp replaceeStamp = replacee.stamp();
1509 if (node instanceof Placeholder) {
1510 Placeholder placeholderDup = (Placeholder) dup;
1511 placeholderDup.makeReplacement(replaceeStamp);
1512 } else {
1513 dup.setStamp(replaceeStamp);
1514 }
1515 }
1516 for (ParameterNode paramNode : snippet.getNodes(ParameterNode.TYPE)) {
1517 for (Node usage : paramNode.usages()) {
1518 Node usageDup = duplicates.get(usage);
1519 propagateStamp(usageDup);
1520 }
1521 }
1522 }
1523
1524 /**
1525 * Gets a copy of the specialized graph.
1526 */
1527 public StructuredGraph copySpecializedGraph() {
1528 return (StructuredGraph) snippet.copy();
1529 }
1530
1531 /**
1532 * Replaces a given floating node with this specialized snippet.
1533 *
1534 * @param metaAccess
1535 * @param replacee the node that will be replaced
1536 * @param replacer object that replaces the usages of {@code replacee}
1537 * @param tool lowering tool used to insert the snippet into the control-flow
1538 * @param args the arguments to be bound to the flattened positional parameters of the snippet
1539 */
1540 @SuppressWarnings("try")
1541 public void instantiate(MetaAccessProvider metaAccess, FloatingNode replacee, UsageReplacer replacer, LoweringTool tool, Arguments args) {
1542 assert assertSnippetKills(replacee);
1543 try (DebugCloseable a = args.info.instantiationTimer.start()) {
1544 args.info.instantiationCounter.increment();
1545 instantiationCounter.increment();
1546
1547 // Inline the snippet nodes, replacing parameters with the given args in the process
1548 StartNode entryPointNode = snippet.start();
1549 FixedNode firstCFGNode = entryPointNode.next();
1550 StructuredGraph replaceeGraph = replacee.graph();
1551 EconomicMap<Node, Node> replacements = bind(replaceeGraph, metaAccess, args);
1552 replacements.put(entryPointNode, tool.getCurrentGuardAnchor().asNode());
1553 UnmodifiableEconomicMap<Node, Node> duplicates = replaceeGraph.addDuplicates(nodes, snippet, snippet.getNodeCount(), replacements);
1554 Debug.dump(Debug.DETAILED_LEVEL, replaceeGraph, "After inlining snippet %s", snippet.method());
1555
1556 FixedWithNextNode lastFixedNode = tool.lastFixedNode();
1557 assert lastFixedNode != null && lastFixedNode.isAlive() : replaceeGraph + " lastFixed=" + lastFixedNode;
1558 FixedNode next = lastFixedNode.next();
1559 lastFixedNode.setNext(null);
1560 FixedNode firstCFGNodeDuplicate = (FixedNode) duplicates.get(firstCFGNode);
1561 replaceeGraph.addAfterFixed(lastFixedNode, firstCFGNodeDuplicate);
1562
1563 rewireFrameStates(replacee, duplicates);
1564 updateStamps(replacee, duplicates);
1565
1566 rewireMemoryGraph(replacee, duplicates);
1567
1568 // Replace all usages of the replacee with the value returned by the snippet
1569 ReturnNode returnDuplicate = (ReturnNode) duplicates.get(returnNode);
1570 ValueNode returnValue = returnDuplicate.result();
1571 assert returnValue != null || replacee.hasNoUsages();
1572 replacer.replace(replacee, returnValue);
1573
1574 if (returnDuplicate.isAlive()) {
1575 returnDuplicate.replaceAndDelete(next);
1576 }
1577
1578 Debug.dump(Debug.DETAILED_LEVEL, replaceeGraph, "After lowering %s with %s", replacee, this);
1579 }
1580 }
1581
1582 /**
1583 * Replaces a given floating node with this specialized snippet.
1584 *
1585 * This snippet must be pure data-flow
1586 *
1587 * @param metaAccess
1588 * @param replacee the node that will be replaced
1589 * @param replacer object that replaces the usages of {@code replacee}
1590 * @param args the arguments to be bound to the flattened positional parameters of the snippet
1591 */
1592 @SuppressWarnings("try")
1593 public void instantiate(MetaAccessProvider metaAccess, FloatingNode replacee, UsageReplacer replacer, Arguments args) {
1594 assert assertSnippetKills(replacee);
1595 try (DebugCloseable a = args.info.instantiationTimer.start()) {
1596 args.info.instantiationCounter.increment();
1597 instantiationCounter.increment();
1598
1599 // Inline the snippet nodes, replacing parameters with the given args in the process
1600 StartNode entryPointNode = snippet.start();
1601 assert entryPointNode.next() == (memoryAnchor == null ? returnNode : memoryAnchor) : entryPointNode.next();
1602 StructuredGraph replaceeGraph = replacee.graph();
1603 EconomicMap<Node, Node> replacements = bind(replaceeGraph, metaAccess, args);
1604 MemoryAnchorNode anchorDuplicate = null;
1605 if (memoryAnchor != null) {
1606 anchorDuplicate = replaceeGraph.add(new MemoryAnchorNode());
1607 replacements.put(memoryAnchor, anchorDuplicate);
1608 }
1609 List<Node> floatingNodes = new ArrayList<>(nodes.size() - 2);
1610 for (Node n : nodes) {
1611 if (n != entryPointNode && n != returnNode) {
1612 floatingNodes.add(n);
1613 }
1614 }
1615 UnmodifiableEconomicMap<Node, Node> duplicates = replaceeGraph.addDuplicates(floatingNodes, snippet, floatingNodes.size(), replacements);
1616 Debug.dump(Debug.DETAILED_LEVEL, replaceeGraph, "After inlining snippet %s", snippet.method());
1617
1618 rewireFrameStates(replacee, duplicates);
1619 updateStamps(replacee, duplicates);
1620
1621 rewireMemoryGraph(replacee, duplicates);
1622 assert anchorDuplicate == null || anchorDuplicate.isDeleted();
1623
1624 // Replace all usages of the replacee with the value returned by the snippet
1625 ValueNode returnValue = (ValueNode) duplicates.get(returnNode.result());
1626 replacer.replace(replacee, returnValue);
1627
1628 Debug.dump(Debug.DETAILED_LEVEL, replaceeGraph, "After lowering %s with %s", replacee, this);
1629 }
1630 }
1631
1632 protected void rewireFrameStates(ValueNode replacee, UnmodifiableEconomicMap<Node, Node> duplicates) {
1633 if (replacee instanceof StateSplit) {
1634 for (StateSplit sideEffectNode : sideEffectNodes) {
1635 assert ((StateSplit) replacee).hasSideEffect();
1636 Node sideEffectDup = duplicates.get(sideEffectNode.asNode());
1637 ((StateSplit) sideEffectDup).setStateAfter(((StateSplit) replacee).stateAfter());
1638 }
1639 }
1640 }
1641
1642 @Override
1643 public String toString() {
1644 StringBuilder buf = new StringBuilder(snippet.toString()).append('(');
1645 String sep = "";
1646 for (int i = 0; i < parameters.length; i++) {
1647 String name = "[" + i + "]";
1648 Object value = parameters[i];
|
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 java.util.FormattableFlags.ALTERNATE;
26 import static org.graalvm.compiler.debug.DebugContext.DEFAULT_LOG_STREAM;
27 import static org.graalvm.compiler.debug.DebugContext.applyFormattingFlagsAndWidth;
28 import static org.graalvm.compiler.debug.DebugOptions.DebugStubsAndSnippets;
29 import static org.graalvm.compiler.graph.iterators.NodePredicates.isNotA;
30 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_IGNORED;
31 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_IGNORED;
32 import static org.graalvm.compiler.phases.common.DeadCodeEliminationPhase.Optionality.Required;
33 import static org.graalvm.word.LocationIdentity.any;
34
35 import java.lang.reflect.Array;
36 import java.lang.reflect.Method;
37 import java.util.ArrayList;
38 import java.util.Arrays;
39 import java.util.Collection;
40 import java.util.Collections;
41 import java.util.Formattable;
42 import java.util.Formatter;
43 import java.util.LinkedHashMap;
44 import java.util.List;
45 import java.util.Map;
46 import java.util.concurrent.atomic.AtomicInteger;
47 import java.util.concurrent.atomic.AtomicReference;
48 import java.util.function.Predicate;
49
50 import org.graalvm.compiler.api.replacements.Snippet;
51 import org.graalvm.compiler.api.replacements.Snippet.ConstantParameter;
52 import org.graalvm.compiler.api.replacements.Snippet.NonNullParameter;
53 import org.graalvm.compiler.api.replacements.Snippet.VarargsParameter;
54 import org.graalvm.compiler.api.replacements.SnippetReflectionProvider;
55 import org.graalvm.compiler.core.common.GraalOptions;
56 import org.graalvm.compiler.core.common.type.Stamp;
57 import org.graalvm.compiler.core.common.type.StampFactory;
58 import org.graalvm.compiler.core.common.type.StampPair;
59 import org.graalvm.compiler.core.common.type.TypeReference;
60 import org.graalvm.compiler.debug.CounterKey;
61 import org.graalvm.compiler.debug.DebugCloseable;
62 import org.graalvm.compiler.debug.DebugHandlersFactory;
63 import org.graalvm.compiler.debug.DebugContext;
64 import org.graalvm.compiler.debug.DebugContext.Description;
65 import org.graalvm.compiler.debug.GraalError;
66 import org.graalvm.compiler.debug.TimerKey;
67 import org.graalvm.compiler.graph.Graph.Mark;
68 import org.graalvm.compiler.graph.Node;
69 import org.graalvm.compiler.graph.NodeClass;
70 import org.graalvm.compiler.graph.Position;
71 import org.graalvm.compiler.loop.LoopEx;
72 import org.graalvm.compiler.loop.LoopsData;
73 import org.graalvm.compiler.loop.phases.LoopTransformations;
74 import org.graalvm.compiler.nodeinfo.InputType;
75 import org.graalvm.compiler.nodeinfo.NodeInfo;
76 import org.graalvm.compiler.nodes.AbstractBeginNode;
77 import org.graalvm.compiler.nodes.AbstractMergeNode;
78 import org.graalvm.compiler.nodes.ConstantNode;
79 import org.graalvm.compiler.nodes.ControlSinkNode;
80 import org.graalvm.compiler.nodes.DeoptimizingNode;
81 import org.graalvm.compiler.nodes.FixedNode;
82 import org.graalvm.compiler.nodes.FixedWithNextNode;
83 import org.graalvm.compiler.nodes.FrameState;
84 import org.graalvm.compiler.nodes.LoopBeginNode;
85 import org.graalvm.compiler.nodes.MergeNode;
86 import org.graalvm.compiler.nodes.ParameterNode;
211 if (localVariableTable != null) {
212 for (int i = 0; i < names.length; i++) {
213 Local local = localVariableTable.getLocal(slotIdx, 0);
214 if (local != null) {
215 names[i] = local.getName();
216 }
217 JavaKind kind = method.getSignature().getParameterKind(i);
218 slotIdx += kind.getSlotCount();
219 }
220 }
221 }
222 return true;
223 }
224 }
225
226 /**
227 * Times instantiations of all templates derived form this snippet.
228 *
229 * @see SnippetTemplate#instantiationTimer
230 */
231 private final TimerKey instantiationTimer;
232
233 /**
234 * Counts instantiations of all templates derived from this snippet.
235 *
236 * @see SnippetTemplate#instantiationCounter
237 */
238 private final CounterKey instantiationCounter;
239
240 protected abstract Lazy lazy();
241
242 protected SnippetInfo(ResolvedJavaMethod method, LocationIdentity[] privateLocations) {
243 this.method = method;
244 this.privateLocations = privateLocations;
245 instantiationCounter = DebugContext.counter("SnippetInstantiationCount[%s]", method.getName());
246 instantiationTimer = DebugContext.timer("SnippetInstantiationTime[%s]", method.getName());
247 assert method.isStatic() : "snippet method must be static: " + method.format("%H.%n");
248 }
249
250 public ResolvedJavaMethod getMethod() {
251 return method;
252 }
253
254 public int getParameterCount() {
255 return lazy().constantParameters.length;
256 }
257
258 public void setOriginalMethod(ResolvedJavaMethod original) {
259 this.original = original;
260 }
261
262 public boolean isConstantParameter(int paramIdx) {
263 return lazy().constantParameters[paramIdx];
264 }
265
266 public boolean isVarargsParameter(int paramIdx) {
546 if (!method.equals(other.method)) {
547 return false;
548 }
549 if (guardsStage != other.guardsStage || loweringStage != other.loweringStage) {
550 return false;
551 }
552 for (int i = 0; i < values.length; i++) {
553 if (values[i] != null && !values[i].equals(other.values[i])) {
554 return false;
555 }
556 }
557 return true;
558 }
559
560 @Override
561 public int hashCode() {
562 return hash;
563 }
564 }
565
566 private static final TimerKey SnippetTemplateCreationTime = DebugContext.timer("SnippetTemplateCreationTime");
567 private static final CounterKey SnippetTemplates = DebugContext.counter("SnippetTemplateCount");
568
569 static class Options {
570 @Option(help = "Use a LRU cache for snippet templates.")//
571 static final OptionKey<Boolean> UseSnippetTemplateCache = new OptionKey<>(true);
572
573 @Option(help = "")//
574 static final OptionKey<Integer> MaxTemplatesPerSnippet = new OptionKey<>(50);
575 }
576
577 /**
578 * Base class for snippet classes. It provides a cache for {@link SnippetTemplate}s.
579 */
580 public abstract static class AbstractTemplates implements org.graalvm.compiler.api.replacements.SnippetTemplateCache {
581
582 protected final OptionValues options;
583 protected final Providers providers;
584 protected final SnippetReflectionProvider snippetReflection;
585 protected final Iterable<DebugHandlersFactory> factories;
586 protected final TargetDescription target;
587 private final Map<CacheKey, SnippetTemplate> templates;
588
589 protected AbstractTemplates(OptionValues options, Iterable<DebugHandlersFactory> factories, Providers providers, SnippetReflectionProvider snippetReflection, TargetDescription target) {
590 this.options = options;
591 this.providers = providers;
592 this.snippetReflection = snippetReflection;
593 this.target = target;
594 this.factories = factories;
595 if (Options.UseSnippetTemplateCache.getValue(options)) {
596 int size = Options.MaxTemplatesPerSnippet.getValue(options);
597 this.templates = Collections.synchronizedMap(new LRUCache<>(size, size));
598 } else {
599 this.templates = null;
600 }
601 }
602
603 public static Method findMethod(Class<? extends Snippets> declaringClass, String methodName, Method except) {
604 for (Method m : declaringClass.getDeclaredMethods()) {
605 if (m.getName().equals(methodName) && !m.equals(except)) {
606 return m;
607 }
608 }
609 return null;
610 }
611
612 /**
613 * Finds the unique method in {@code declaringClass} named {@code methodName} annotated by
614 * {@link Snippet} and returns a {@link SnippetInfo} value describing it. There must be
615 * exactly one snippet method in {@code declaringClass}.
616 */
617 protected SnippetInfo snippet(Class<? extends Snippets> declaringClass, String methodName, LocationIdentity... initialPrivateLocations) {
618 assert methodName != null;
619 Method method = findMethod(declaringClass, methodName, null);
620 assert method != null : "did not find @" + Snippet.class.getSimpleName() + " method in " + declaringClass + " named " + methodName;
621 assert method.getAnnotation(Snippet.class) != null : method + " must be annotated with @" + Snippet.class.getSimpleName();
622 assert findMethod(declaringClass, methodName, method) == null : "found more than one method named " + methodName + " in " + declaringClass;
623 ResolvedJavaMethod javaMethod = providers.getMetaAccess().lookupJavaMethod(method);
624 providers.getReplacements().registerSnippet(javaMethod);
625 LocationIdentity[] privateLocations = GraalOptions.SnippetCounters.getValue(options) ? SnippetCounterNode.addSnippetCounters(initialPrivateLocations) : initialPrivateLocations;
626 if (GraalOptions.EagerSnippets.getValue(options)) {
627 return new EagerSnippetInfo(javaMethod, privateLocations);
628 } else {
629 return new LazySnippetInfo(javaMethod, privateLocations);
630 }
631 }
632
633 static final AtomicInteger nextSnippetTemplateId = new AtomicInteger();
634
635 private DebugContext openDebugContext(DebugContext outer, Arguments args) {
636 if (DebugStubsAndSnippets.getValue(options)) {
637 Description description = new Description(args.cacheKey.method, "SnippetTemplate_" + nextSnippetTemplateId.incrementAndGet());
638 return DebugContext.create(options, description, outer.getGlobalMetrics(), DEFAULT_LOG_STREAM, factories);
639 }
640 return DebugContext.DISABLED;
641 }
642
643 /**
644 * Gets a template for a given key, creating it first if necessary.
645 */
646 @SuppressWarnings("try")
647 protected SnippetTemplate template(DebugContext outer, final Arguments args) {
648 SnippetTemplate template = Options.UseSnippetTemplateCache.getValue(options) && args.cacheable ? templates.get(args.cacheKey) : null;
649 if (template == null) {
650 try (DebugContext debug = openDebugContext(outer, args)) {
651 try (DebugCloseable a = SnippetTemplateCreationTime.start(debug); DebugContext.Scope s = debug.scope("SnippetSpecialization", args.info.method)) {
652 SnippetTemplates.increment(debug);
653 template = new SnippetTemplate(options, debug, providers, snippetReflection, args);
654 if (Options.UseSnippetTemplateCache.getValue(options) && args.cacheable) {
655 templates.put(args.cacheKey, template);
656 }
657 } catch (Throwable e) {
658 throw debug.handle(e);
659 }
660 }
661 }
662 return template;
663 }
664 }
665
666 private static final class LRUCache<K, V> extends LinkedHashMap<K, V> {
667 private static final long serialVersionUID = 1L;
668 private final int maxCacheSize;
669
670 LRUCache(int initialCapacity, int maxCacheSize) {
671 super(initialCapacity, 0.75F, true);
672 this.maxCacheSize = maxCacheSize;
673 }
674
675 @Override
676 protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
677 return size() > maxCacheSize;
678 }
679 }
683 private static final Object CONSTANT_PARAMETER = "CONSTANT_PARAMETER";
684
685 /**
686 * Determines if any parameter of a given method is annotated with {@link ConstantParameter}.
687 */
688 public static boolean hasConstantParameter(ResolvedJavaMethod method) {
689 for (ConstantParameter p : method.getParameterAnnotations(ConstantParameter.class)) {
690 if (p != null) {
691 return true;
692 }
693 }
694 return false;
695 }
696
697 private final SnippetReflectionProvider snippetReflection;
698
699 /**
700 * Creates a snippet template.
701 */
702 @SuppressWarnings("try")
703 protected SnippetTemplate(OptionValues options, DebugContext debug, final Providers providers, SnippetReflectionProvider snippetReflection, Arguments args) {
704 this.snippetReflection = snippetReflection;
705 this.info = args.info;
706
707 Object[] constantArgs = getConstantArgs(args);
708 StructuredGraph snippetGraph = providers.getReplacements().getSnippet(args.info.method, args.info.original, constantArgs);
709 instantiationTimer = DebugContext.timer("SnippetTemplateInstantiationTime[%#s]", args);
710 instantiationCounter = DebugContext.counter("SnippetTemplateInstantiationCount[%#s]", args);
711
712 ResolvedJavaMethod method = snippetGraph.method();
713 Signature signature = method.getSignature();
714
715 PhaseContext phaseContext = new PhaseContext(providers);
716
717 // Copy snippet graph, replacing constant parameters with given arguments
718 final StructuredGraph snippetCopy = new StructuredGraph.Builder(options, debug).name(snippetGraph.name).method(snippetGraph.method()).build();
719
720 try (DebugContext.Scope scope = debug.scope("SpecializeSnippet", snippetCopy)) {
721 if (!snippetGraph.isUnsafeAccessTrackingEnabled()) {
722 snippetCopy.disableUnsafeAccessTracking();
723 }
724
725 EconomicMap<Node, Node> nodeReplacements = EconomicMap.create(Equivalence.IDENTITY);
726 nodeReplacements.put(snippetGraph.start(), snippetCopy.start());
727
728 MetaAccessProvider metaAccess = providers.getMetaAccess();
729 assert checkTemplate(metaAccess, args, method, signature);
730
731 int parameterCount = args.info.getParameterCount();
732 VarargsPlaceholderNode[] placeholders = new VarargsPlaceholderNode[parameterCount];
733
734 for (int i = 0; i < parameterCount; i++) {
735 ParameterNode parameter = snippetGraph.getParameter(i);
736 if (parameter != null) {
737 if (args.info.isConstantParameter(i)) {
738 Object arg = args.values[i];
739 JavaKind kind = signature.getParameterKind(i);
740 ConstantNode constantNode;
745 constantNode = ConstantNode.forConstant((JavaConstant) arg, metaAccess, snippetCopy);
746 } else {
747 constantNode = ConstantNode.forConstant(stamp, (Constant) arg, metaAccess, snippetCopy);
748 }
749 } else {
750 constantNode = ConstantNode.forConstant(snippetReflection.forBoxed(kind, arg), metaAccess, snippetCopy);
751 }
752 nodeReplacements.put(parameter, constantNode);
753 } else if (args.info.isVarargsParameter(i)) {
754 Varargs varargs = (Varargs) args.values[i];
755 VarargsPlaceholderNode placeholder = snippetCopy.unique(new VarargsPlaceholderNode(varargs, providers.getMetaAccess()));
756 nodeReplacements.put(parameter, placeholder);
757 placeholders[i] = placeholder;
758 } else if (args.info.isNonNullParameter(i)) {
759 parameter.setStamp(parameter.stamp().join(StampFactory.objectNonNull()));
760 }
761 }
762 }
763 snippetCopy.addDuplicates(snippetGraph.getNodes(), snippetGraph, snippetGraph.getNodeCount(), nodeReplacements);
764
765 debug.dump(DebugContext.INFO_LEVEL, snippetCopy, "Before specialization");
766
767 // Gather the template parameters
768 parameters = new Object[parameterCount];
769 for (int i = 0; i < parameterCount; i++) {
770 if (args.info.isConstantParameter(i)) {
771 parameters[i] = CONSTANT_PARAMETER;
772 } else if (args.info.isVarargsParameter(i)) {
773 assert snippetCopy.getParameter(i) == null;
774 Varargs varargs = (Varargs) args.values[i];
775 int length = varargs.length;
776 ParameterNode[] params = new ParameterNode[length];
777 Stamp stamp = varargs.stamp;
778 for (int j = 0; j < length; j++) {
779 // Use a decimal friendly numbering make it more obvious how values map
780 assert parameterCount < 10000;
781 int idx = (i + 1) * 10000 + j;
782 assert idx >= parameterCount : "collision in parameter numbering";
783 ParameterNode local = snippetCopy.addOrUnique(new ParameterNode(idx, StampPair.createSingle(stamp)));
784 params[j] = local;
785 }
786 parameters[i] = params;
787
788 VarargsPlaceholderNode placeholder = placeholders[i];
789 if (placeholder != null) {
790 for (Node usage : placeholder.usages().snapshot()) {
791 if (usage instanceof LoadIndexedNode) {
792 LoadIndexedNode loadIndexed = (LoadIndexedNode) usage;
793 debug.dump(DebugContext.INFO_LEVEL, snippetCopy, "Before replacing %s", loadIndexed);
794 LoadSnippetVarargParameterNode loadSnippetParameter = snippetCopy.add(new LoadSnippetVarargParameterNode(params, loadIndexed.index(), loadIndexed.stamp()));
795 snippetCopy.replaceFixedWithFixed(loadIndexed, loadSnippetParameter);
796 debug.dump(DebugContext.INFO_LEVEL, snippetCopy, "After replacing %s", loadIndexed);
797 } else if (usage instanceof StoreIndexedNode) {
798 /*
799 * The template lowering doesn't really treat this as an array so
800 * you can't store back into the varargs. Allocate your own array if
801 * you really need this and EA should eliminate it.
802 */
803 throw new GraalError("Can't store into VarargsParameter array");
804 }
805 }
806 }
807 } else {
808 ParameterNode local = snippetCopy.getParameter(i);
809 if (local == null) {
810 // Parameter value was eliminated
811 parameters[i] = UNUSED_PARAMETER;
812 } else {
813 parameters[i] = local;
814 }
815 }
816 }
817
818 explodeLoops(snippetCopy, phaseContext);
819
820 GuardsStage guardsStage = args.cacheKey.guardsStage;
821 // Perform lowering on the snippet
822 if (!guardsStage.allowsFloatingGuards()) {
823 new GuardLoweringPhase().apply(snippetCopy, null);
824 }
825 snippetCopy.setGuardsStage(guardsStage);
826 try (DebugContext.Scope s = debug.scope("LoweringSnippetTemplate", snippetCopy)) {
827 new LoweringPhase(new CanonicalizerPhase(), args.cacheKey.loweringStage).apply(snippetCopy, phaseContext);
828 } catch (Throwable e) {
829 throw debug.handle(e);
830 }
831
832 ArrayList<StateSplit> curSideEffectNodes = new ArrayList<>();
833 ArrayList<DeoptimizingNode> curDeoptNodes = new ArrayList<>();
834 ArrayList<ValueNode> curPlaceholderStampedNodes = new ArrayList<>();
835 for (Node node : snippetCopy.getNodes()) {
836 if (node instanceof ValueNode) {
837 ValueNode valueNode = (ValueNode) node;
838 if (valueNode.stamp() == PlaceholderStamp.singleton()) {
839 curPlaceholderStampedNodes.add(valueNode);
840 }
841 }
842
843 if (node instanceof StateSplit) {
844 StateSplit stateSplit = (StateSplit) node;
845 FrameState frameState = stateSplit.stateAfter();
846 if (stateSplit.hasSideEffect()) {
847 curSideEffectNodes.add((StateSplit) node);
848 }
849 if (frameState != null) {
894 // Remove the useless memory map
895 MemoryMapNode memoryMap = null;
896 for (ReturnNode retNode : snippet.getNodes(ReturnNode.TYPE)) {
897 if (memoryMap == null) {
898 memoryMap = retNode.getMemoryMap();
899 } else {
900 assert memoryMap == retNode.getMemoryMap();
901 }
902 retNode.setMemoryMap(null);
903 }
904 memoryMap.safeDelete();
905 }
906 if (needsAnchor) {
907 snippetCopy.addAfterFixed(snippetCopy.start(), anchor);
908 this.memoryAnchor = anchor;
909 } else {
910 anchor.safeDelete();
911 this.memoryAnchor = null;
912 }
913 }
914 debug.dump(DebugContext.INFO_LEVEL, snippet, "SnippetTemplate after fixing memory anchoring");
915
916 List<ReturnNode> returnNodes = snippet.getNodes(ReturnNode.TYPE).snapshot();
917 if (returnNodes.isEmpty()) {
918 this.returnNode = null;
919 } else if (returnNodes.size() == 1) {
920 this.returnNode = returnNodes.get(0);
921 } else {
922 AbstractMergeNode merge = snippet.add(new MergeNode());
923 List<MemoryMapNode> memMaps = new ArrayList<>();
924 for (ReturnNode retNode : returnNodes) {
925 MemoryMapNode memoryMapNode = retNode.getMemoryMap();
926 if (memoryMapNode != null) {
927 memMaps.add(memoryMapNode);
928 }
929 }
930
931 ValueNode returnValue = InliningUtil.mergeReturns(merge, returnNodes);
932 this.returnNode = snippet.add(new ReturnNode(returnValue));
933 if (!memMaps.isEmpty()) {
934 MemoryMapImpl mmap = FloatingReadPhase.mergeMemoryMaps(merge, memMaps);
938 if (mm != memoryMap && mm.isAlive()) {
939 assert mm.hasNoUsages();
940 GraphUtil.killWithUnusedFloatingInputs(mm);
941 }
942 }
943 }
944 merge.setNext(this.returnNode);
945 }
946
947 this.sideEffectNodes = curSideEffectNodes;
948 this.deoptNodes = curDeoptNodes;
949 this.placeholderStampedNodes = curPlaceholderStampedNodes;
950
951 nodes = new ArrayList<>(snippet.getNodeCount());
952 for (Node node : snippet.getNodes()) {
953 if (node != entryPointNode && node != entryPointNode.stateAfter()) {
954 nodes.add(node);
955 }
956 }
957
958 if (debug.areMetricsEnabled()) {
959 DebugContext.counter("SnippetTemplateNodeCount[%#s]", args).add(debug, nodes.size());
960 }
961 debug.dump(DebugContext.INFO_LEVEL, snippet, "SnippetTemplate final state");
962 this.snippet.freeze();
963
964 } catch (Throwable ex) {
965 throw debug.handle(ex);
966 }
967 }
968
969 public static void explodeLoops(final StructuredGraph snippetCopy, PhaseContext phaseContext) {
970 // Do any required loop explosion
971 boolean exploded = false;
972 do {
973 exploded = false;
974 ExplodeLoopNode explodeLoop = snippetCopy.getNodes().filter(ExplodeLoopNode.class).first();
975 if (explodeLoop != null) { // Earlier canonicalization may have removed the loop
976 // altogether
977 LoopBeginNode loopBegin = explodeLoop.findLoopBegin();
978 if (loopBegin != null) {
979 LoopEx loop = new LoopsData(snippetCopy).loop(loopBegin);
980 Mark mark = snippetCopy.getMark();
981 LoopTransformations.fullUnroll(loop, phaseContext, new CanonicalizerPhase());
982 new CanonicalizerPhase().applyIncremental(snippetCopy, phaseContext, mark);
983 loop.deleteUnusedNodes();
984 }
985 GraphUtil.removeFixedWithUnusedInputs(explodeLoop);
1065 * Nodes that inherit a deoptimization {@link FrameState} from the replacee during
1066 * instantiation.
1067 */
1068 private final ArrayList<DeoptimizingNode> deoptNodes;
1069
1070 /**
1071 * Nodes that have a stamp originating from a {@link Placeholder}.
1072 */
1073 private final ArrayList<ValueNode> placeholderStampedNodes;
1074
1075 /**
1076 * The nodes to be inlined when this specialization is instantiated.
1077 */
1078 private final ArrayList<Node> nodes;
1079
1080 /**
1081 * Times instantiations of this template.
1082 *
1083 * @see SnippetInfo#instantiationTimer
1084 */
1085 private final TimerKey instantiationTimer;
1086
1087 /**
1088 * Counts instantiations of this template.
1089 *
1090 * @see SnippetInfo#instantiationCounter
1091 */
1092 private final CounterKey instantiationCounter;
1093
1094 /**
1095 * Gets the instantiation-time bindings to this template's parameters.
1096 *
1097 * @return the map that will be used to bind arguments to parameters when inlining this template
1098 */
1099 private EconomicMap<Node, Node> bind(StructuredGraph replaceeGraph, MetaAccessProvider metaAccess, Arguments args) {
1100 EconomicMap<Node, Node> replacements = EconomicMap.create(Equivalence.IDENTITY);
1101 assert args.info.getParameterCount() == parameters.length : "number of args (" + args.info.getParameterCount() + ") != number of parameters (" + parameters.length + ")";
1102 for (int i = 0; i < parameters.length; i++) {
1103 Object parameter = parameters[i];
1104 assert parameter != null : this + " has no parameter named " + args.info.getParameterName(i);
1105 Object argument = args.values[i];
1106 if (parameter instanceof ParameterNode) {
1107 if (argument instanceof ValueNode) {
1108 replacements.put((ParameterNode) parameter, (ValueNode) argument);
1109 } else {
1110 JavaKind kind = ((ParameterNode) parameter).getStackKind();
1111 assert argument != null || kind == JavaKind.Object : this + " cannot accept null for non-object parameter named " + args.info.getParameterName(i);
1112 JavaConstant constant = forBoxed(argument, kind);
1387 * @param args the arguments to be bound to the flattened positional parameters of the snippet
1388 * @return the map of duplicated nodes (original -> duplicate)
1389 */
1390 @SuppressWarnings("try")
1391 public UnmodifiableEconomicMap<Node, Node> instantiate(MetaAccessProvider metaAccess, FixedNode replacee, UsageReplacer replacer, Arguments args) {
1392 return instantiate(metaAccess, replacee, replacer, args, true);
1393 }
1394
1395 /**
1396 * Replaces a given fixed node with this specialized snippet.
1397 *
1398 * @param metaAccess
1399 * @param replacee the node that will be replaced
1400 * @param replacer object that replaces the usages of {@code replacee}
1401 * @param args the arguments to be bound to the flattened positional parameters of the snippet
1402 * @param killReplacee is true, the replacee node is deleted
1403 * @return the map of duplicated nodes (original -> duplicate)
1404 */
1405 @SuppressWarnings("try")
1406 public UnmodifiableEconomicMap<Node, Node> instantiate(MetaAccessProvider metaAccess, FixedNode replacee, UsageReplacer replacer, Arguments args, boolean killReplacee) {
1407 DebugContext debug = replacee.getDebug();
1408 assert assertSnippetKills(replacee);
1409 try (DebugCloseable a = args.info.instantiationTimer.start(debug); DebugCloseable b = instantiationTimer.start(debug)) {
1410 args.info.instantiationCounter.increment(debug);
1411 instantiationCounter.increment(debug);
1412 // Inline the snippet nodes, replacing parameters with the given args in the process
1413 StartNode entryPointNode = snippet.start();
1414 FixedNode firstCFGNode = entryPointNode.next();
1415 StructuredGraph replaceeGraph = replacee.graph();
1416 EconomicMap<Node, Node> replacements = bind(replaceeGraph, metaAccess, args);
1417 replacements.put(entryPointNode, AbstractBeginNode.prevBegin(replacee));
1418 UnmodifiableEconomicMap<Node, Node> duplicates = replaceeGraph.addDuplicates(nodes, snippet, snippet.getNodeCount(), replacements);
1419 debug.dump(DebugContext.DETAILED_LEVEL, replaceeGraph, "After inlining snippet %s", snippet.method());
1420
1421 // Re-wire the control flow graph around the replacee
1422 FixedNode firstCFGNodeDuplicate = (FixedNode) duplicates.get(firstCFGNode);
1423 replacee.replaceAtPredecessor(firstCFGNodeDuplicate);
1424
1425 rewireFrameStates(replacee, duplicates);
1426
1427 if (replacee instanceof DeoptimizingNode) {
1428 DeoptimizingNode replaceeDeopt = (DeoptimizingNode) replacee;
1429
1430 FrameState stateBefore = null;
1431 FrameState stateDuring = null;
1432 FrameState stateAfter = null;
1433 if (replaceeDeopt.canDeoptimize()) {
1434 if (replaceeDeopt instanceof DeoptimizingNode.DeoptBefore) {
1435 stateBefore = ((DeoptimizingNode.DeoptBefore) replaceeDeopt).stateBefore();
1436 }
1437 if (replaceeDeopt instanceof DeoptimizingNode.DeoptDuring) {
1438 stateDuring = ((DeoptimizingNode.DeoptDuring) replaceeDeopt).stateDuring();
1439 }
1487 } else {
1488 assert returnValue != null || replacee.hasNoUsages();
1489 replacer.replace(replacee, returnValue);
1490 }
1491 if (returnDuplicate.isAlive()) {
1492 FixedNode next = null;
1493 if (replacee instanceof FixedWithNextNode) {
1494 FixedWithNextNode fwn = (FixedWithNextNode) replacee;
1495 next = fwn.next();
1496 fwn.setNext(null);
1497 }
1498 returnDuplicate.replaceAndDelete(next);
1499 }
1500 }
1501
1502 if (killReplacee) {
1503 // Remove the replacee from its graph
1504 GraphUtil.killCFG(replacee);
1505 }
1506
1507 debug.dump(DebugContext.DETAILED_LEVEL, replaceeGraph, "After lowering %s with %s", replacee, this);
1508 return duplicates;
1509 }
1510 }
1511
1512 private void propagateStamp(Node node) {
1513 if (node instanceof PhiNode) {
1514 PhiNode phi = (PhiNode) node;
1515 if (phi.inferStamp()) {
1516 for (Node usage : node.usages()) {
1517 propagateStamp(usage);
1518 }
1519 }
1520 }
1521 }
1522
1523 private void updateStamps(ValueNode replacee, UnmodifiableEconomicMap<Node, Node> duplicates) {
1524 for (ValueNode node : placeholderStampedNodes) {
1525 ValueNode dup = (ValueNode) duplicates.get(node);
1526 Stamp replaceeStamp = replacee.stamp();
1527 if (node instanceof Placeholder) {
1528 Placeholder placeholderDup = (Placeholder) dup;
1529 placeholderDup.makeReplacement(replaceeStamp);
1530 } else {
1531 dup.setStamp(replaceeStamp);
1532 }
1533 }
1534 for (ParameterNode paramNode : snippet.getNodes(ParameterNode.TYPE)) {
1535 for (Node usage : paramNode.usages()) {
1536 Node usageDup = duplicates.get(usage);
1537 propagateStamp(usageDup);
1538 }
1539 }
1540 }
1541
1542 /**
1543 * Gets a copy of the specialized graph.
1544 */
1545 public StructuredGraph copySpecializedGraph(DebugContext debugForCopy) {
1546 return (StructuredGraph) snippet.copy(debugForCopy);
1547 }
1548
1549 /**
1550 * Replaces a given floating node with this specialized snippet.
1551 *
1552 * @param metaAccess
1553 * @param replacee the node that will be replaced
1554 * @param replacer object that replaces the usages of {@code replacee}
1555 * @param tool lowering tool used to insert the snippet into the control-flow
1556 * @param args the arguments to be bound to the flattened positional parameters of the snippet
1557 */
1558 @SuppressWarnings("try")
1559 public void instantiate(MetaAccessProvider metaAccess, FloatingNode replacee, UsageReplacer replacer, LoweringTool tool, Arguments args) {
1560 DebugContext debug = replacee.getDebug();
1561 assert assertSnippetKills(replacee);
1562 try (DebugCloseable a = args.info.instantiationTimer.start(debug)) {
1563 args.info.instantiationCounter.increment(debug);
1564 instantiationCounter.increment(debug);
1565
1566 // Inline the snippet nodes, replacing parameters with the given args in the process
1567 StartNode entryPointNode = snippet.start();
1568 FixedNode firstCFGNode = entryPointNode.next();
1569 StructuredGraph replaceeGraph = replacee.graph();
1570 EconomicMap<Node, Node> replacements = bind(replaceeGraph, metaAccess, args);
1571 replacements.put(entryPointNode, tool.getCurrentGuardAnchor().asNode());
1572 UnmodifiableEconomicMap<Node, Node> duplicates = replaceeGraph.addDuplicates(nodes, snippet, snippet.getNodeCount(), replacements);
1573 debug.dump(DebugContext.DETAILED_LEVEL, replaceeGraph, "After inlining snippet %s", snippet.method());
1574
1575 FixedWithNextNode lastFixedNode = tool.lastFixedNode();
1576 assert lastFixedNode != null && lastFixedNode.isAlive() : replaceeGraph + " lastFixed=" + lastFixedNode;
1577 FixedNode next = lastFixedNode.next();
1578 lastFixedNode.setNext(null);
1579 FixedNode firstCFGNodeDuplicate = (FixedNode) duplicates.get(firstCFGNode);
1580 replaceeGraph.addAfterFixed(lastFixedNode, firstCFGNodeDuplicate);
1581
1582 rewireFrameStates(replacee, duplicates);
1583 updateStamps(replacee, duplicates);
1584
1585 rewireMemoryGraph(replacee, duplicates);
1586
1587 // Replace all usages of the replacee with the value returned by the snippet
1588 ReturnNode returnDuplicate = (ReturnNode) duplicates.get(returnNode);
1589 ValueNode returnValue = returnDuplicate.result();
1590 assert returnValue != null || replacee.hasNoUsages();
1591 replacer.replace(replacee, returnValue);
1592
1593 if (returnDuplicate.isAlive()) {
1594 returnDuplicate.replaceAndDelete(next);
1595 }
1596
1597 debug.dump(DebugContext.DETAILED_LEVEL, replaceeGraph, "After lowering %s with %s", replacee, this);
1598 }
1599 }
1600
1601 /**
1602 * Replaces a given floating node with this specialized snippet.
1603 *
1604 * This snippet must be pure data-flow
1605 *
1606 * @param metaAccess
1607 * @param replacee the node that will be replaced
1608 * @param replacer object that replaces the usages of {@code replacee}
1609 * @param args the arguments to be bound to the flattened positional parameters of the snippet
1610 */
1611 @SuppressWarnings("try")
1612 public void instantiate(MetaAccessProvider metaAccess, FloatingNode replacee, UsageReplacer replacer, Arguments args) {
1613 DebugContext debug = replacee.getDebug();
1614 assert assertSnippetKills(replacee);
1615 try (DebugCloseable a = args.info.instantiationTimer.start(debug)) {
1616 args.info.instantiationCounter.increment(debug);
1617 instantiationCounter.increment(debug);
1618
1619 // Inline the snippet nodes, replacing parameters with the given args in the process
1620 StartNode entryPointNode = snippet.start();
1621 assert entryPointNode.next() == (memoryAnchor == null ? returnNode : memoryAnchor) : entryPointNode.next();
1622 StructuredGraph replaceeGraph = replacee.graph();
1623 EconomicMap<Node, Node> replacements = bind(replaceeGraph, metaAccess, args);
1624 MemoryAnchorNode anchorDuplicate = null;
1625 if (memoryAnchor != null) {
1626 anchorDuplicate = replaceeGraph.add(new MemoryAnchorNode());
1627 replacements.put(memoryAnchor, anchorDuplicate);
1628 }
1629 List<Node> floatingNodes = new ArrayList<>(nodes.size() - 2);
1630 for (Node n : nodes) {
1631 if (n != entryPointNode && n != returnNode) {
1632 floatingNodes.add(n);
1633 }
1634 }
1635 UnmodifiableEconomicMap<Node, Node> duplicates = replaceeGraph.addDuplicates(floatingNodes, snippet, floatingNodes.size(), replacements);
1636 debug.dump(DebugContext.DETAILED_LEVEL, replaceeGraph, "After inlining snippet %s", snippet.method());
1637
1638 rewireFrameStates(replacee, duplicates);
1639 updateStamps(replacee, duplicates);
1640
1641 rewireMemoryGraph(replacee, duplicates);
1642 assert anchorDuplicate == null || anchorDuplicate.isDeleted();
1643
1644 // Replace all usages of the replacee with the value returned by the snippet
1645 ValueNode returnValue = (ValueNode) duplicates.get(returnNode.result());
1646 replacer.replace(replacee, returnValue);
1647
1648 debug.dump(DebugContext.DETAILED_LEVEL, replaceeGraph, "After lowering %s with %s", replacee, this);
1649 }
1650 }
1651
1652 protected void rewireFrameStates(ValueNode replacee, UnmodifiableEconomicMap<Node, Node> duplicates) {
1653 if (replacee instanceof StateSplit) {
1654 for (StateSplit sideEffectNode : sideEffectNodes) {
1655 assert ((StateSplit) replacee).hasSideEffect();
1656 Node sideEffectDup = duplicates.get(sideEffectNode.asNode());
1657 ((StateSplit) sideEffectDup).setStateAfter(((StateSplit) replacee).stateAfter());
1658 }
1659 }
1660 }
1661
1662 @Override
1663 public String toString() {
1664 StringBuilder buf = new StringBuilder(snippet.toString()).append('(');
1665 String sep = "";
1666 for (int i = 0; i < parameters.length; i++) {
1667 String name = "[" + i + "]";
1668 Object value = parameters[i];
|