1 /*
2 * Copyright (c) 2012, 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 package org.graalvm.compiler.replacements;
24
25 import static org.graalvm.compiler.core.common.CompilationIdentifier.INVALID_COMPILATION_ID;
26 import static org.graalvm.compiler.core.common.GraalOptions.UseGraalInstrumentation;
27 import static org.graalvm.compiler.core.common.LocationIdentity.ANY_LOCATION;
28 import static org.graalvm.compiler.core.common.LocationIdentity.any;
29 import static org.graalvm.compiler.debug.Debug.applyFormattingFlagsAndWidth;
30 import static org.graalvm.compiler.graph.iterators.NodePredicates.isNotA;
31 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_IGNORED;
32 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_IGNORED;
33 import static org.graalvm.compiler.phases.common.DeadCodeEliminationPhase.Optionality.Required;
34 import static java.util.FormattableFlags.ALTERNATE;
35
36 import java.lang.reflect.Array;
37 import java.lang.reflect.Method;
38 import java.util.ArrayList;
39 import java.util.Arrays;
40 import java.util.Collection;
41 import java.util.Collections;
42 import java.util.Formattable;
43 import java.util.Formatter;
44 import java.util.HashSet;
45 import java.util.LinkedHashMap;
46 import java.util.List;
47 import java.util.Map;
48 import java.util.Objects;
49 import java.util.Set;
50 import java.util.concurrent.atomic.AtomicReference;
51 import java.util.function.Predicate;
52 import java.util.stream.Collectors;
53
54 import org.graalvm.compiler.api.replacements.Snippet;
55 import org.graalvm.compiler.api.replacements.Snippet.ConstantParameter;
56 import org.graalvm.compiler.api.replacements.Snippet.VarargsParameter;
57 import org.graalvm.compiler.api.replacements.SnippetReflectionProvider;
58 import org.graalvm.compiler.core.common.GraalOptions;
59 import org.graalvm.compiler.core.common.LocationIdentity;
60 import org.graalvm.compiler.core.common.type.Stamp;
61 import org.graalvm.compiler.core.common.type.StampFactory;
62 import org.graalvm.compiler.core.common.type.StampPair;
63 import org.graalvm.compiler.core.common.type.TypeReference;
64 import org.graalvm.compiler.debug.Debug;
65 import org.graalvm.compiler.debug.Debug.Scope;
66 import org.graalvm.compiler.debug.DebugCloseable;
67 import org.graalvm.compiler.debug.DebugCounter;
68 import org.graalvm.compiler.debug.DebugTimer;
69 import org.graalvm.compiler.debug.GraalError;
70 import org.graalvm.compiler.graph.Graph.Mark;
71 import org.graalvm.compiler.graph.Node;
72 import org.graalvm.compiler.graph.NodeClass;
73 import org.graalvm.compiler.graph.Position;
74 import org.graalvm.compiler.loop.LoopEx;
75 import org.graalvm.compiler.loop.LoopsData;
76 import org.graalvm.compiler.loop.phases.LoopTransformations;
77 import org.graalvm.compiler.nodeinfo.InputType;
78 import org.graalvm.compiler.nodeinfo.NodeInfo;
79 import org.graalvm.compiler.nodes.AbstractBeginNode;
80 import org.graalvm.compiler.nodes.AbstractMergeNode;
81 import org.graalvm.compiler.nodes.ConstantNode;
82 import org.graalvm.compiler.nodes.ControlSinkNode;
83 import org.graalvm.compiler.nodes.DeoptimizingNode;
84 import org.graalvm.compiler.nodes.FixedNode;
85 import org.graalvm.compiler.nodes.FixedWithNextNode;
86 import org.graalvm.compiler.nodes.FrameState;
87 import org.graalvm.compiler.nodes.LoopBeginNode;
88 import org.graalvm.compiler.nodes.MergeNode;
89 import org.graalvm.compiler.nodes.ParameterNode;
90 import org.graalvm.compiler.nodes.PhiNode;
91 import org.graalvm.compiler.nodes.ReturnNode;
92 import org.graalvm.compiler.nodes.StartNode;
93 import org.graalvm.compiler.nodes.StateSplit;
94 import org.graalvm.compiler.nodes.StructuredGraph;
95 import org.graalvm.compiler.nodes.StructuredGraph.AllowAssumptions;
96 import org.graalvm.compiler.nodes.StructuredGraph.GuardsStage;
97 import org.graalvm.compiler.nodes.ValueNode;
98 import org.graalvm.compiler.nodes.ValueNodeUtil;
99 import org.graalvm.compiler.nodes.calc.FloatingNode;
100 import org.graalvm.compiler.nodes.debug.instrumentation.InstrumentationNode;
101 import org.graalvm.compiler.nodes.java.LoadIndexedNode;
102 import org.graalvm.compiler.nodes.java.StoreIndexedNode;
103 import org.graalvm.compiler.nodes.memory.MemoryAccess;
104 import org.graalvm.compiler.nodes.memory.MemoryAnchorNode;
105 import org.graalvm.compiler.nodes.memory.MemoryCheckpoint;
106 import org.graalvm.compiler.nodes.memory.MemoryMap;
107 import org.graalvm.compiler.nodes.memory.MemoryMapNode;
108 import org.graalvm.compiler.nodes.memory.MemoryNode;
109 import org.graalvm.compiler.nodes.memory.MemoryPhiNode;
110 import org.graalvm.compiler.nodes.spi.ArrayLengthProvider;
111 import org.graalvm.compiler.nodes.spi.LoweringTool;
112 import org.graalvm.compiler.nodes.spi.MemoryProxy;
113 import org.graalvm.compiler.nodes.util.GraphUtil;
114 import org.graalvm.compiler.options.Option;
115 import org.graalvm.compiler.options.OptionValue;
116 import org.graalvm.compiler.phases.common.CanonicalizerPhase;
117 import org.graalvm.compiler.phases.common.DeadCodeEliminationPhase;
118 import org.graalvm.compiler.phases.common.FloatingReadPhase;
119 import org.graalvm.compiler.phases.common.FloatingReadPhase.MemoryMapImpl;
120 import org.graalvm.compiler.phases.common.GuardLoweringPhase;
121 import org.graalvm.compiler.phases.common.LoweringPhase;
122 import org.graalvm.compiler.phases.common.inlining.InliningUtil;
123 import org.graalvm.compiler.phases.tiers.PhaseContext;
124 import org.graalvm.compiler.phases.util.Providers;
125 import org.graalvm.compiler.replacements.nodes.ExplodeLoopNode;
126 import org.graalvm.compiler.replacements.nodes.LoadSnippetVarargParameterNode;
127 import org.graalvm.compiler.word.WordBase;
128
129 import jdk.vm.ci.code.TargetDescription;
130 import jdk.vm.ci.meta.Constant;
131 import jdk.vm.ci.meta.JavaConstant;
132 import jdk.vm.ci.meta.JavaKind;
133 import jdk.vm.ci.meta.Local;
134 import jdk.vm.ci.meta.LocalVariableTable;
135 import jdk.vm.ci.meta.MetaAccessProvider;
136 import jdk.vm.ci.meta.ResolvedJavaMethod;
137 import jdk.vm.ci.meta.ResolvedJavaType;
138 import jdk.vm.ci.meta.Signature;
139
140 /**
141 * A snippet template is a graph created by parsing a snippet method and then specialized by binding
142 * constants to the snippet's {@link ConstantParameter} parameters.
143 *
144 * Snippet templates can be managed in a cache maintained by {@link AbstractTemplates}.
145 */
146 public class SnippetTemplate {
147
148 private boolean mayRemoveLocation = false;
149
150 /**
151 * Holds the {@link ResolvedJavaMethod} of the snippet, together with some information about the
152 * method that needs to be computed only once. The {@link SnippetInfo} should be created once
153 * per snippet and then cached.
154 */
155 public abstract static class SnippetInfo {
156
157 protected final ResolvedJavaMethod method;
158 protected ResolvedJavaMethod original;
159 protected final LocationIdentity[] privateLocations;
160
161 /**
162 * Lazily constructed parts of {@link SnippetInfo}.
163 */
164 static class Lazy {
165 Lazy(ResolvedJavaMethod method) {
166 int count = method.getSignature().getParameterCount(false);
167 constantParameters = new boolean[count];
168 varargsParameters = new boolean[count];
169 for (int i = 0; i < count; i++) {
170 constantParameters[i] = method.getParameterAnnotation(ConstantParameter.class, i) != null;
171 varargsParameters[i] = method.getParameterAnnotation(VarargsParameter.class, i) != null;
172
173 assert !constantParameters[i] || !varargsParameters[i] : "Parameter cannot be annotated with both @" + ConstantParameter.class.getSimpleName() + " and @" +
174 VarargsParameter.class.getSimpleName();
175 }
176
177 // Retrieve the names only when assertions are turned on.
178 assert initNames(method, count);
179 }
180
181 final boolean[] constantParameters;
182 final boolean[] varargsParameters;
183
184 /**
185 * The parameter names, taken from the local variables table. Only used for assertion
186 * checking, so use only within an assert statement.
187 */
188 String[] names;
189
190 private boolean initNames(ResolvedJavaMethod method, int parameterCount) {
191 names = new String[parameterCount];
192 int slotIdx = 0;
193 LocalVariableTable localVariableTable = method.getLocalVariableTable();
194 if (localVariableTable != null) {
195 for (int i = 0; i < names.length; i++) {
196 Local local = localVariableTable.getLocal(slotIdx, 0);
197 if (local != null) {
198 names[i] = local.getName();
199 }
200 JavaKind kind = method.getSignature().getParameterKind(i);
201 slotIdx += kind.getSlotCount();
202 }
203 }
204 return true;
205 }
206
207 }
208
209 /**
210 * Times instantiations of all templates derived form this snippet.
211 *
212 * @see SnippetTemplate#instantiationTimer
213 */
214 private final DebugTimer instantiationTimer;
215
216 /**
217 * Counts instantiations of all templates derived from this snippet.
218 *
219 * @see SnippetTemplate#instantiationCounter
220 */
221 private final DebugCounter instantiationCounter;
222
223 protected abstract Lazy lazy();
224
225 protected SnippetInfo(ResolvedJavaMethod method, LocationIdentity[] privateLocations) {
226 this.method = method;
227 this.privateLocations = SnippetCounterNode.addSnippetCounters(privateLocations);
228 instantiationCounter = Debug.counter("SnippetInstantiationCount[%s]", method.getName());
229 instantiationTimer = Debug.timer("SnippetInstantiationTime[%s]", method.getName());
230 assert method.isStatic() : "snippet method must be static: " + method.format("%H.%n");
231 }
232
233 public ResolvedJavaMethod getMethod() {
234 return method;
235 }
236
237 public int getParameterCount() {
238 return lazy().constantParameters.length;
239 }
240
241 public void setOriginalMethod(ResolvedJavaMethod original) {
242 this.original = original;
243 }
244
245 public boolean isConstantParameter(int paramIdx) {
246 return lazy().constantParameters[paramIdx];
247 }
248
249 public boolean isVarargsParameter(int paramIdx) {
250 return lazy().varargsParameters[paramIdx];
251 }
252
253 public String getParameterName(int paramIdx) {
254 String[] names = lazy().names;
255 if (names != null) {
256 return names[paramIdx];
257 }
258 return null;
259 }
260
261 @Override
262 public String toString() {
263 return getClass().getSimpleName() + ":" + method.format("%h.%n");
264 }
265 }
266
267 protected static class LazySnippetInfo extends SnippetInfo {
268 protected final AtomicReference<Lazy> lazy = new AtomicReference<>(null);
269
270 protected LazySnippetInfo(ResolvedJavaMethod method, LocationIdentity[] privateLocations) {
271 super(method, privateLocations);
272 }
273
274 @Override
275 protected Lazy lazy() {
276 if (lazy.get() == null) {
277 lazy.compareAndSet(null, new Lazy(method));
278 }
279 return lazy.get();
280 }
281 }
282
283 protected static class EagerSnippetInfo extends SnippetInfo {
284 protected final Lazy lazy;
285
286 protected EagerSnippetInfo(ResolvedJavaMethod method, LocationIdentity[] privateLocations) {
287 super(method, privateLocations);
288 lazy = new Lazy(method);
289 }
290
291 @Override
292 protected Lazy lazy() {
293 return lazy;
294 }
295 }
296
297 /**
298 * Values that are bound to the snippet method parameters. The methods {@link #add},
299 * {@link #addConst}, and {@link #addVarargs} must be called in the same order as in the
300 * signature of the snippet method. The parameter name is passed to the add methods for
301 * assertion checking, i.e., to enforce that the order matches. Which method needs to be called
302 * depends on the annotation of the snippet method parameter:
303 * <ul>
304 * <li>Use {@link #add} for a parameter without an annotation. The value is bound when the
305 * {@link SnippetTemplate} is {@link SnippetTemplate#instantiate instantiated}.
306 * <li>Use {@link #addConst} for a parameter annotated with {@link ConstantParameter}. The value
307 * is bound when the {@link SnippetTemplate} is {@link SnippetTemplate#SnippetTemplate created}.
308 * <li>Use {@link #addVarargs} for an array parameter annotated with {@link VarargsParameter}. A
309 * separate {@link SnippetTemplate} is {@link SnippetTemplate#SnippetTemplate created} for every
310 * distinct array length. The actual values are bound when the {@link SnippetTemplate} is
311 * {@link SnippetTemplate#instantiate instantiated}
312 * </ul>
313 */
314 public static class Arguments implements Formattable {
315
316 protected final SnippetInfo info;
317 protected final CacheKey cacheKey;
318 protected final Object[] values;
319 protected final Stamp[] constStamps;
320 protected boolean cacheable;
321
322 protected int nextParamIdx;
323
324 public Arguments(SnippetInfo info, GuardsStage guardsStage, LoweringTool.LoweringStage loweringStage) {
325 this.info = info;
326 this.cacheKey = new CacheKey(info, guardsStage, loweringStage);
327 this.values = new Object[info.getParameterCount()];
328 this.constStamps = new Stamp[info.getParameterCount()];
329 this.cacheable = true;
330 }
331
332 public Arguments add(String name, Object value) {
333 assert check(name, false, false);
334 values[nextParamIdx] = value;
335 nextParamIdx++;
336 return this;
337 }
338
339 public Arguments addConst(String name, Object value) {
340 assert value != null;
341 return addConst(name, value, null);
342 }
343
344 public Arguments addConst(String name, Object value, Stamp stamp) {
345 assert check(name, true, false);
346 values[nextParamIdx] = value;
347 constStamps[nextParamIdx] = stamp;
348 cacheKey.setParam(nextParamIdx, value);
349 nextParamIdx++;
350 return this;
351 }
352
353 public Arguments addVarargs(String name, Class<?> componentType, Stamp argStamp, Object value) {
354 assert check(name, false, true);
355 Varargs varargs = new Varargs(componentType, argStamp, value);
356 values[nextParamIdx] = varargs;
357 // A separate template is necessary for every distinct array length
358 cacheKey.setParam(nextParamIdx, varargs.length);
359 nextParamIdx++;
360 return this;
361 }
362
363 public void setCacheable(boolean cacheable) {
364 this.cacheable = cacheable;
365 }
366
367 private boolean check(String name, boolean constParam, boolean varargsParam) {
368 assert nextParamIdx < info.getParameterCount() : "too many parameters: " + name + " " + this;
369 assert info.getParameterName(nextParamIdx) == null || info.getParameterName(nextParamIdx).equals(name) : "wrong parameter name: " + name + " " + this;
370 assert constParam == info.isConstantParameter(nextParamIdx) : "Parameter " + (constParam ? "not " : "") + "annotated with @" + ConstantParameter.class.getSimpleName() + ": " + name +
371 " " + this;
372 assert varargsParam == info.isVarargsParameter(nextParamIdx) : "Parameter " + (varargsParam ? "not " : "") + "annotated with @" + VarargsParameter.class.getSimpleName() + ": " + name +
373 " " + this;
374 return true;
375 }
376
377 @Override
378 public String toString() {
379 StringBuilder result = new StringBuilder();
380 result.append("Parameters<").append(info.method.format("%h.%n")).append(" [");
381 String sep = "";
382 for (int i = 0; i < info.getParameterCount(); i++) {
383 result.append(sep);
384 if (info.isConstantParameter(i)) {
385 result.append("const ");
386 } else if (info.isVarargsParameter(i)) {
387 result.append("varargs ");
388 }
389 result.append(info.getParameterName(i)).append(" = ").append(values[i]);
390 sep = ", ";
391 }
392 result.append(">");
393 return result.toString();
394 }
395
396 @Override
397 public void formatTo(Formatter formatter, int flags, int width, int precision) {
398 if ((flags & ALTERNATE) == 0) {
399 formatter.format(applyFormattingFlagsAndWidth(toString(), flags, width));
400 } else {
401 StringBuilder sb = new StringBuilder();
402 sb.append(info.method.getName()).append('(');
403 String sep = "";
404 for (int i = 0; i < info.getParameterCount(); i++) {
405 if (info.isConstantParameter(i)) {
406 sb.append(sep);
407 if (info.getParameterName(i) != null) {
408 sb.append(info.getParameterName(i));
409 } else {
410 sb.append(i);
411 }
412 sb.append('=').append(values[i]);
413 sep = ", ";
414 }
415 }
416 sb.append(")");
417 String string = sb.toString();
418 if (string.indexOf('%') != -1) {
419 // Quote any % signs
420 string = string.replace("%", "%%");
421 }
422 formatter.format(applyFormattingFlagsAndWidth(string, flags & ~ALTERNATE, width));
423 }
424 }
425 }
426
427 /**
428 * Wrapper for the prototype value of a {@linkplain VarargsParameter varargs} parameter.
429 */
430 static class Varargs {
431
432 protected final Class<?> componentType;
433 protected final Stamp stamp;
434 protected final Object value;
435 protected final int length;
436
437 protected Varargs(Class<?> componentType, Stamp stamp, Object value) {
438 this.componentType = componentType;
439 this.stamp = stamp;
440 this.value = value;
441 if (value instanceof List) {
442 this.length = ((List<?>) value).size();
443 } else {
444 this.length = Array.getLength(value);
445 }
446 }
447
448 @Override
449 public String toString() {
450 if (value instanceof boolean[]) {
451 return Arrays.toString((boolean[]) value);
452 }
453 if (value instanceof byte[]) {
454 return Arrays.toString((byte[]) value);
455 }
456 if (value instanceof char[]) {
457 return Arrays.toString((char[]) value);
458 }
459 if (value instanceof short[]) {
460 return Arrays.toString((short[]) value);
461 }
462 if (value instanceof int[]) {
463 return Arrays.toString((int[]) value);
464 }
465 if (value instanceof long[]) {
466 return Arrays.toString((long[]) value);
467 }
468 if (value instanceof float[]) {
469 return Arrays.toString((float[]) value);
470 }
471 if (value instanceof double[]) {
472 return Arrays.toString((double[]) value);
473 }
474 if (value instanceof Object[]) {
475 return Arrays.toString((Object[]) value);
476 }
477 return String.valueOf(value);
478 }
479 }
480
481 @NodeInfo(cycles = CYCLES_IGNORED, size = SIZE_IGNORED)
482 static final class VarargsPlaceholderNode extends FloatingNode implements ArrayLengthProvider {
483
484 public static final NodeClass<VarargsPlaceholderNode> TYPE = NodeClass.create(VarargsPlaceholderNode.class);
485 protected final Varargs varargs;
486
487 protected VarargsPlaceholderNode(Varargs varargs, MetaAccessProvider metaAccess) {
488 super(TYPE, StampFactory.objectNonNull(TypeReference.createExactTrusted(metaAccess.lookupJavaType(varargs.componentType).getArrayClass())));
489 this.varargs = varargs;
490 }
491
492 @Override
493 public ValueNode length() {
494 return ConstantNode.forInt(varargs.length);
495 }
496 }
497
498 static class CacheKey {
499
500 private final ResolvedJavaMethod method;
501 private final Object[] values;
502 private final GuardsStage guardsStage;
503 private final LoweringTool.LoweringStage loweringStage;
504 private int hash;
505
506 protected CacheKey(SnippetInfo info, GuardsStage guardsStage, LoweringTool.LoweringStage loweringStage) {
507 this.method = info.method;
508 this.guardsStage = guardsStage;
509 this.loweringStage = loweringStage;
510 this.values = new Object[info.getParameterCount()];
511 this.hash = info.method.hashCode() + 31 * guardsStage.ordinal();
512 }
513
514 protected void setParam(int paramIdx, Object value) {
515 values[paramIdx] = value;
516 hash = (hash * 31) ^ (value == null ? 0 : value.hashCode());
517 }
518
519 @Override
520 public boolean equals(Object obj) {
521 if (!(obj instanceof CacheKey)) {
522 return false;
523 }
524 CacheKey other = (CacheKey) obj;
525 if (!method.equals(other.method)) {
526 return false;
527 }
528 if (guardsStage != other.guardsStage || loweringStage != other.loweringStage) {
529 return false;
530 }
531 for (int i = 0; i < values.length; i++) {
532 if (values[i] != null && !values[i].equals(other.values[i])) {
533 return false;
534 }
535 }
536 return true;
537 }
538
539 @Override
540 public int hashCode() {
541 return hash;
542 }
543 }
544
545 private static final DebugTimer SnippetTemplateCreationTime = Debug.timer("SnippetTemplateCreationTime");
546 private static final DebugCounter SnippetTemplates = Debug.counter("SnippetTemplateCount");
547
548 static class Options {
549 @Option(help = "Use a LRU cache for snippet templates.")//
550 static final OptionValue<Boolean> UseSnippetTemplateCache = new OptionValue<>(true);
551
552 @Option(help = "")//
553 static final OptionValue<Integer> MaxTemplatesPerSnippet = new OptionValue<>(50);
554 }
555
556 /**
557 * Base class for snippet classes. It provides a cache for {@link SnippetTemplate}s.
558 */
559 public abstract static class AbstractTemplates implements org.graalvm.compiler.api.replacements.SnippetTemplateCache {
560
561 protected final Providers providers;
562 protected final SnippetReflectionProvider snippetReflection;
563 protected final TargetDescription target;
564 private final Map<CacheKey, SnippetTemplate> templates;
565
566 protected AbstractTemplates(Providers providers, SnippetReflectionProvider snippetReflection, TargetDescription target) {
567 this.providers = providers;
568 this.snippetReflection = snippetReflection;
569 this.target = target;
570 if (Options.UseSnippetTemplateCache.getValue()) {
571 int size = Options.MaxTemplatesPerSnippet.getValue();
572 this.templates = Collections.synchronizedMap(new LRUCache<>(size, size));
573 } else {
574 this.templates = null;
575 }
576 }
577
578 public static Method findMethod(Class<? extends Snippets> declaringClass, String methodName, Method except) {
579 for (Method m : declaringClass.getDeclaredMethods()) {
580 if (m.getName().equals(methodName) && !m.equals(except)) {
581 return m;
582 }
583 }
584 return null;
585 }
586
587 /**
588 * Finds the unique method in {@code declaringClass} named {@code methodName} annotated by
589 * {@link Snippet} and returns a {@link SnippetInfo} value describing it. There must be
590 * exactly one snippet method in {@code declaringClass}.
591 */
592 protected SnippetInfo snippet(Class<? extends Snippets> declaringClass, String methodName, LocationIdentity... privateLocations) {
593 assert methodName != null;
594 Method method = findMethod(declaringClass, methodName, null);
595 assert method != null : "did not find @" + Snippet.class.getSimpleName() + " method in " + declaringClass + " named " + methodName;
596 assert method.getAnnotation(Snippet.class) != null : method + " must be annotated with @" + Snippet.class.getSimpleName();
597 assert findMethod(declaringClass, methodName, method) == null : "found more than one method named " + methodName + " in " + declaringClass;
598 ResolvedJavaMethod javaMethod = providers.getMetaAccess().lookupJavaMethod(method);
599 providers.getReplacements().registerSnippet(javaMethod);
600 if (GraalOptions.EagerSnippets.getValue()) {
601 return new EagerSnippetInfo(javaMethod, privateLocations);
602 } else {
603 return new LazySnippetInfo(javaMethod, privateLocations);
604 }
605 }
606
607 /**
608 * Gets a template for a given key, creating it first if necessary.
609 */
610 @SuppressWarnings("try")
611 protected SnippetTemplate template(final Arguments args) {
612 SnippetTemplate template = Options.UseSnippetTemplateCache.getValue() && args.cacheable ? templates.get(args.cacheKey) : null;
613 if (template == null) {
614 SnippetTemplates.increment();
615 try (DebugCloseable a = SnippetTemplateCreationTime.start(); Scope s = Debug.scope("SnippetSpecialization", args.info.method)) {
616 template = new SnippetTemplate(providers, snippetReflection, args);
617 if (Options.UseSnippetTemplateCache.getValue() && args.cacheable) {
618 templates.put(args.cacheKey, template);
619 }
620 } catch (Throwable e) {
621 throw Debug.handle(e);
622 }
623 }
624 return template;
625 }
626 }
627
628 private static final class LRUCache<K, V> extends LinkedHashMap<K, V> {
629 private static final long serialVersionUID = 1L;
630 private final int maxCacheSize;
631
632 LRUCache(int initialCapacity, int maxCacheSize) {
633 super(initialCapacity, 0.75F, true);
634 this.maxCacheSize = maxCacheSize;
635 }
636
637 @Override
638 protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
639 return size() > maxCacheSize;
640 }
641 }
642
643 // These values must be compared with equals() not '==' to support replay compilation.
644 private static final Object UNUSED_PARAMETER = "UNUSED_PARAMETER";
645 private static final Object CONSTANT_PARAMETER = "CONSTANT_PARAMETER";
646
647 /**
648 * Determines if any parameter of a given method is annotated with {@link ConstantParameter}.
649 */
650 public static boolean hasConstantParameter(ResolvedJavaMethod method) {
651 for (ConstantParameter p : method.getParameterAnnotations(ConstantParameter.class)) {
652 if (p != null) {
653 return true;
654 }
655 }
656 return false;
657 }
658
659 private final SnippetReflectionProvider snippetReflection;
660
661 /**
662 * Creates a snippet template.
663 */
664 @SuppressWarnings("try")
665 protected SnippetTemplate(final Providers providers, SnippetReflectionProvider snippetReflection, Arguments args) {
666 this.snippetReflection = snippetReflection;
667 this.info = args.info;
668
669 Object[] constantArgs = getConstantArgs(args);
670 StructuredGraph snippetGraph = providers.getReplacements().getSnippet(args.info.method, args.info.original, constantArgs);
671 instantiationTimer = Debug.timer("SnippetTemplateInstantiationTime[%#s]", args);
672 instantiationCounter = Debug.counter("SnippetTemplateInstantiationCount[%#s]", args);
673
674 ResolvedJavaMethod method = snippetGraph.method();
675 Signature signature = method.getSignature();
676
677 PhaseContext phaseContext = new PhaseContext(providers);
678
679 // Copy snippet graph, replacing constant parameters with given arguments
680 final StructuredGraph snippetCopy = new StructuredGraph(snippetGraph.name, snippetGraph.method(), AllowAssumptions.NO, INVALID_COMPILATION_ID);
681
682 try (Debug.Scope scope = Debug.scope("SpecializeSnippet", snippetCopy)) {
683 if (!snippetGraph.isUnsafeAccessTrackingEnabled()) {
684 snippetCopy.disableUnsafeAccessTracking();
685 }
686
687 Map<Node, Node> nodeReplacements = Node.newIdentityMap();
688 nodeReplacements.put(snippetGraph.start(), snippetCopy.start());
689
690 MetaAccessProvider metaAccess = providers.getMetaAccess();
691 assert checkTemplate(metaAccess, args, method, signature);
692
693 int parameterCount = args.info.getParameterCount();
694 VarargsPlaceholderNode[] placeholders = new VarargsPlaceholderNode[parameterCount];
695
696 for (int i = 0; i < parameterCount; i++) {
697 if (args.info.isConstantParameter(i)) {
698 Object arg = args.values[i];
699 JavaKind kind = signature.getParameterKind(i);
700 ConstantNode constantNode;
701 if (arg instanceof Constant) {
702 Stamp stamp = args.constStamps[i];
703 if (stamp == null) {
704 assert arg instanceof JavaConstant : "could not determine type of constant " + arg;
705 constantNode = ConstantNode.forConstant((JavaConstant) arg, metaAccess, snippetCopy);
706 } else {
707 constantNode = ConstantNode.forConstant(stamp, (Constant) arg, metaAccess, snippetCopy);
708 }
709 } else {
710 constantNode = ConstantNode.forConstant(snippetReflection.forBoxed(kind, arg), metaAccess, snippetCopy);
711 }
712 nodeReplacements.put(snippetGraph.getParameter(i), constantNode);
713 } else if (args.info.isVarargsParameter(i)) {
714 Varargs varargs = (Varargs) args.values[i];
715 VarargsPlaceholderNode placeholder = snippetCopy.unique(new VarargsPlaceholderNode(varargs, providers.getMetaAccess()));
716 nodeReplacements.put(snippetGraph.getParameter(i), placeholder);
717 placeholders[i] = placeholder;
718 }
719 }
720 snippetCopy.addDuplicates(snippetGraph.getNodes(), snippetGraph, snippetGraph.getNodeCount(), nodeReplacements);
721
722 Debug.dump(Debug.INFO_LOG_LEVEL, snippetCopy, "Before specialization");
723
724 // Gather the template parameters
725 parameters = new Object[parameterCount];
726 for (int i = 0; i < parameterCount; i++) {
727 if (args.info.isConstantParameter(i)) {
728 parameters[i] = CONSTANT_PARAMETER;
729 } else if (args.info.isVarargsParameter(i)) {
730 assert snippetCopy.getParameter(i) == null;
731 Varargs varargs = (Varargs) args.values[i];
732 int length = varargs.length;
733 ParameterNode[] params = new ParameterNode[length];
734 Stamp stamp = varargs.stamp;
735 for (int j = 0; j < length; j++) {
736 // Use a decimal friendly numbering make it more obvious how values map
737 assert parameterCount < 10000;
738 int idx = (i + 1) * 10000 + j;
739 assert idx >= parameterCount : "collision in parameter numbering";
740 ParameterNode local = snippetCopy.addOrUnique(new ParameterNode(idx, StampPair.createSingle(stamp)));
741 params[j] = local;
742 }
743 parameters[i] = params;
744
745 VarargsPlaceholderNode placeholder = placeholders[i];
746 assert placeholder != null;
747 for (Node usage : placeholder.usages().snapshot()) {
748 if (usage instanceof LoadIndexedNode) {
749 LoadIndexedNode loadIndexed = (LoadIndexedNode) usage;
750 Debug.dump(Debug.INFO_LOG_LEVEL, snippetCopy, "Before replacing %s", loadIndexed);
751 LoadSnippetVarargParameterNode loadSnippetParameter = snippetCopy.add(new LoadSnippetVarargParameterNode(params, loadIndexed.index(), loadIndexed.stamp()));
752 snippetCopy.replaceFixedWithFixed(loadIndexed, loadSnippetParameter);
753 Debug.dump(Debug.INFO_LOG_LEVEL, snippetCopy, "After replacing %s", loadIndexed);
754 } else if (usage instanceof StoreIndexedNode) {
755 /*
756 * The template lowering doesn't really treat this as an array so you
757 * can't store back into the varargs. Allocate your own array if you
758 * really need this and EA should eliminate it.
759 */
760 throw new GraalError("Can't store into VarargsParameter array");
761 }
762 }
763 } else {
764 ParameterNode local = snippetCopy.getParameter(i);
765 if (local == null) {
766 // Parameter value was eliminated
767 parameters[i] = UNUSED_PARAMETER;
768 } else {
769 parameters[i] = local;
770 }
771 }
772 }
773
774 // Do any required loop explosion
775 boolean exploded = false;
776 do {
777 exploded = false;
778 ExplodeLoopNode explodeLoop = snippetCopy.getNodes().filter(ExplodeLoopNode.class).first();
779 if (explodeLoop != null) { // Earlier canonicalization may have removed the loop
780 // altogether
781 LoopBeginNode loopBegin = explodeLoop.findLoopBegin();
782 if (loopBegin != null) {
783 LoopEx loop = new LoopsData(snippetCopy).loop(loopBegin);
784 Mark mark = snippetCopy.getMark();
785 LoopTransformations.fullUnroll(loop, phaseContext, new CanonicalizerPhase());
786 new CanonicalizerPhase().applyIncremental(snippetCopy, phaseContext, mark);
787 loop.deleteUnusedNodes();
788 }
789 GraphUtil.removeFixedWithUnusedInputs(explodeLoop);
790 exploded = true;
791 }
792 } while (exploded);
793
794 GuardsStage guardsStage = args.cacheKey.guardsStage;
795 // Perform lowering on the snippet
796 if (!guardsStage.allowsFloatingGuards()) {
797 new GuardLoweringPhase().apply(snippetCopy, null);
798 }
799 snippetCopy.setGuardsStage(guardsStage);
800 try (Scope s = Debug.scope("LoweringSnippetTemplate", snippetCopy)) {
801 new LoweringPhase(new CanonicalizerPhase(), args.cacheKey.loweringStage).apply(snippetCopy, phaseContext);
802 } catch (Throwable e) {
803 throw Debug.handle(e);
804 }
805
806 ArrayList<StateSplit> curSideEffectNodes = new ArrayList<>();
807 ArrayList<DeoptimizingNode> curDeoptNodes = new ArrayList<>();
808 ArrayList<ValueNode> curStampNodes = new ArrayList<>();
809 for (Node node : snippetCopy.getNodes()) {
810 if (node instanceof ValueNode && ((ValueNode) node).stamp() == StampFactory.forNodeIntrinsic()) {
811 curStampNodes.add((ValueNode) node);
812 }
813 if (node instanceof StateSplit) {
814 StateSplit stateSplit = (StateSplit) node;
815 FrameState frameState = stateSplit.stateAfter();
816 if (stateSplit.hasSideEffect()) {
817 curSideEffectNodes.add((StateSplit) node);
818 }
819 if (frameState != null) {
820 stateSplit.setStateAfter(null);
821 }
822 }
823 if (node instanceof DeoptimizingNode) {
824 DeoptimizingNode deoptNode = (DeoptimizingNode) node;
825 if (deoptNode.canDeoptimize()) {
826 curDeoptNodes.add(deoptNode);
827 }
828 }
829 }
830
831 new DeadCodeEliminationPhase(Required).apply(snippetCopy);
832
833 assert checkAllVarargPlaceholdersAreDeleted(parameterCount, placeholders);
834
835 new FloatingReadPhase(true, true).apply(snippetCopy);
836
837 MemoryAnchorNode anchor = snippetCopy.add(new MemoryAnchorNode());
838 snippetCopy.start().replaceAtUsages(InputType.Memory, anchor);
839
840 this.snippet = snippetCopy;
841
842 StartNode entryPointNode = snippet.start();
843 if (anchor.hasNoUsages()) {
844 anchor.safeDelete();
845 this.memoryAnchor = null;
846 } else {
847 // Find out if all the return memory maps point to the anchor (i.e., there's no kill
848 // anywhere)
849 boolean needsMemoryMaps = false;
850 for (ReturnNode retNode : snippet.getNodes(ReturnNode.TYPE)) {
851 MemoryMapNode memoryMap = retNode.getMemoryMap();
852 if (memoryMap.getLocations().size() > 1 || memoryMap.getLastLocationAccess(ANY_LOCATION) != anchor) {
853 needsMemoryMaps = true;
854 break;
855 }
856 }
857 boolean needsAnchor;
858 if (needsMemoryMaps) {
859 needsAnchor = true;
860 } else {
861 // Check that all those memory maps where the only usages of the anchor
862 needsAnchor = anchor.usages().filter(isNotA(MemoryMapNode.class)).isNotEmpty();
863 // Remove the useless memory map
864 MemoryMapNode memoryMap = null;
865 for (ReturnNode retNode : snippet.getNodes(ReturnNode.TYPE)) {
866 if (memoryMap == null) {
867 memoryMap = retNode.getMemoryMap();
868 } else {
869 assert memoryMap == retNode.getMemoryMap();
870 }
871 retNode.setMemoryMap(null);
872 }
873 memoryMap.safeDelete();
874 }
875 if (needsAnchor) {
876 snippetCopy.addAfterFixed(snippetCopy.start(), anchor);
877 this.memoryAnchor = anchor;
878 } else {
879 anchor.safeDelete();
880 this.memoryAnchor = null;
881 }
882 }
883 Debug.dump(Debug.INFO_LOG_LEVEL, snippet, "SnippetTemplate after fixing memory anchoring");
884
885 List<ReturnNode> returnNodes = snippet.getNodes(ReturnNode.TYPE).snapshot();
886 if (returnNodes.isEmpty()) {
887 this.returnNode = null;
888 } else if (returnNodes.size() == 1) {
889 this.returnNode = returnNodes.get(0);
890 } else {
891 AbstractMergeNode merge = snippet.add(new MergeNode());
892 List<MemoryMapNode> memMaps = returnNodes.stream().map(ReturnNode::getMemoryMap).filter(Objects::nonNull).collect(Collectors.toList());
893 ValueNode returnValue = InliningUtil.mergeReturns(merge, returnNodes, null);
894 this.returnNode = snippet.add(new ReturnNode(returnValue));
895 if (!memMaps.isEmpty()) {
896 MemoryMapImpl mmap = FloatingReadPhase.mergeMemoryMaps(merge, memMaps);
897 MemoryMapNode memoryMap = snippet.unique(new MemoryMapNode(mmap.getMap()));
898 this.returnNode.setMemoryMap(memoryMap);
899 for (MemoryMapNode mm : memMaps) {
900 if (mm != memoryMap && mm.isAlive()) {
901 assert mm.hasNoUsages();
902 GraphUtil.killWithUnusedFloatingInputs(mm);
903 }
904 }
905 }
906 merge.setNext(this.returnNode);
907 }
908
909 this.sideEffectNodes = curSideEffectNodes;
910 this.deoptNodes = curDeoptNodes;
911 this.stampNodes = curStampNodes;
912
913 nodes = new ArrayList<>(snippet.getNodeCount());
914 for (Node node : snippet.getNodes()) {
915 if (node != entryPointNode && node != entryPointNode.stateAfter()) {
916 nodes.add(node);
917 }
918 }
919
920 Debug.counter("SnippetTemplateNodeCount[%#s]", args).add(nodes.size());
921 Debug.dump(Debug.INFO_LOG_LEVEL, snippet, "SnippetTemplate final state");
922
923 } catch (Throwable ex) {
924 throw Debug.handle(ex);
925 }
926 }
927
928 protected Object[] getConstantArgs(Arguments args) {
929 Object[] constantArgs = args.values.clone();
930 for (int i = 0; i < args.info.getParameterCount(); i++) {
931 if (!args.info.isConstantParameter(i)) {
932 constantArgs[i] = null;
933 } else {
934 assert constantArgs[i] != null : "Can't pass raw null through as argument";
935 }
936 }
937 return constantArgs;
938 }
939
940 private static boolean checkAllVarargPlaceholdersAreDeleted(int parameterCount, VarargsPlaceholderNode[] placeholders) {
941 for (int i = 0; i < parameterCount; i++) {
942 if (placeholders[i] != null) {
943 assert placeholders[i].isDeleted() : placeholders[i];
944 }
945 }
946 return true;
947 }
948
949 private static boolean checkConstantArgument(MetaAccessProvider metaAccess, final ResolvedJavaMethod method, Signature signature, int i, String name, Object arg, JavaKind kind) {
950 ResolvedJavaType type = signature.getParameterType(i, method.getDeclaringClass()).resolve(method.getDeclaringClass());
951 if (metaAccess.lookupJavaType(WordBase.class).isAssignableFrom(type)) {
952 assert arg instanceof JavaConstant : method + ": word constant parameters must be passed boxed in a Constant value: " + arg;
953 return true;
954 }
955 if (kind != JavaKind.Object) {
956 assert arg != null && kind.toBoxedJavaClass() == arg.getClass() : method + ": wrong value kind for " + name + ": expected " + kind + ", got " +
957 (arg == null ? "null" : arg.getClass().getSimpleName());
958 }
959 return true;
960 }
961
962 private static boolean checkVarargs(MetaAccessProvider metaAccess, final ResolvedJavaMethod method, Signature signature, int i, String name, Varargs varargs) {
963 ResolvedJavaType type = (ResolvedJavaType) signature.getParameterType(i, method.getDeclaringClass());
964 assert type.isArray() : "varargs parameter must be an array type";
965 assert type.getComponentType().isAssignableFrom(metaAccess.lookupJavaType(varargs.componentType)) : "componentType for " + name + " not matching " + type.toJavaName() + " instance: " +
966 varargs.componentType;
967 return true;
968 }
969
970 /**
971 * The graph built from the snippet method.
972 */
973 private final StructuredGraph snippet;
974
975 private final SnippetInfo info;
976
977 /**
978 * The named parameters of this template that must be bound to values during instantiation. For
979 * a parameter that is still live after specialization, the value in this map is either a
980 * {@link ParameterNode} instance or a {@link ParameterNode} array. For an eliminated parameter,
981 * the value is identical to the key.
982 */
983 private final Object[] parameters;
984
985 /**
986 * The return node (if any) of the snippet.
987 */
988 private final ReturnNode returnNode;
989
990 /**
991 * The memory anchor (if any) of the snippet.
992 */
993 private final MemoryAnchorNode memoryAnchor;
994
995 /**
996 * Nodes that inherit the {@link StateSplit#stateAfter()} from the replacee during
997 * instantiation.
998 */
999 private final ArrayList<StateSplit> sideEffectNodes;
1000
1001 /**
1002 * Nodes that inherit a deoptimization {@link FrameState} from the replacee during
1003 * instantiation.
1004 */
1005 private final ArrayList<DeoptimizingNode> deoptNodes;
1006
1007 /**
1008 * The nodes that inherit the {@link ValueNode#stamp()} from the replacee during instantiation.
1009 */
1010 private final ArrayList<ValueNode> stampNodes;
1011
1012 /**
1013 * The nodes to be inlined when this specialization is instantiated.
1014 */
1015 private final ArrayList<Node> nodes;
1016
1017 /**
1018 * Times instantiations of this template.
1019 *
1020 * @see SnippetInfo#instantiationTimer
1021 */
1022 private final DebugTimer instantiationTimer;
1023
1024 /**
1025 * Counts instantiations of this template.
1026 *
1027 * @see SnippetInfo#instantiationCounter
1028 */
1029 private final DebugCounter instantiationCounter;
1030
1031 /**
1032 * Gets the instantiation-time bindings to this template's parameters.
1033 *
1034 * @return the map that will be used to bind arguments to parameters when inlining this template
1035 */
1036 private Map<Node, Node> bind(StructuredGraph replaceeGraph, MetaAccessProvider metaAccess, Arguments args) {
1037 Map<Node, Node> replacements = Node.newIdentityMap();
1038 assert args.info.getParameterCount() == parameters.length : "number of args (" + args.info.getParameterCount() + ") != number of parameters (" + parameters.length + ")";
1039 for (int i = 0; i < parameters.length; i++) {
1040 Object parameter = parameters[i];
1041 assert parameter != null : this + " has no parameter named " + args.info.getParameterName(i);
1042 Object argument = args.values[i];
1043 if (parameter instanceof ParameterNode) {
1044 if (argument instanceof ValueNode) {
1045 replacements.put((ParameterNode) parameter, (ValueNode) argument);
1046 } else {
1047 JavaKind kind = ((ParameterNode) parameter).getStackKind();
1048 assert argument != null || kind == JavaKind.Object : this + " cannot accept null for non-object parameter named " + args.info.getParameterName(i);
1049 JavaConstant constant = forBoxed(argument, kind);
1050 replacements.put((ParameterNode) parameter, ConstantNode.forConstant(constant, metaAccess, replaceeGraph));
1051 }
1052 } else if (parameter instanceof ParameterNode[]) {
1053 ParameterNode[] params = (ParameterNode[]) parameter;
1054 Varargs varargs = (Varargs) argument;
1055 int length = params.length;
1056 List<?> list = null;
1057 Object array = null;
1058 if (varargs.value instanceof List) {
1059 list = (List<?>) varargs.value;
1060 assert list.size() == length : length + " != " + list.size();
1061 } else {
1062 array = varargs.value;
1063 assert array != null && array.getClass().isArray();
1064 assert Array.getLength(array) == length : length + " != " + Array.getLength(array);
1065 }
1066
1067 for (int j = 0; j < length; j++) {
1068 ParameterNode param = params[j];
1069 assert param != null;
1070 Object value = list != null ? list.get(j) : Array.get(array, j);
1071 if (value instanceof ValueNode) {
1072 replacements.put(param, (ValueNode) value);
1073 } else {
1074 JavaConstant constant = forBoxed(value, param.getStackKind());
1075 ConstantNode element = ConstantNode.forConstant(constant, metaAccess, replaceeGraph);
1076 replacements.put(param, element);
1077 }
1078 }
1079 } else {
1080 assert parameter.equals(CONSTANT_PARAMETER) || parameter.equals(UNUSED_PARAMETER) : "unexpected entry for parameter: " + args.info.getParameterName(i) + " -> " + parameter;
1081 }
1082 }
1083 return replacements;
1084 }
1085
1086 /**
1087 * Converts a Java boxed value to a {@link JavaConstant} of the right kind. This adjusts for the
1088 * limitation that a {@link Local}'s kind is a {@linkplain JavaKind#getStackKind() stack kind}
1089 * and so cannot be used for re-boxing primitives smaller than an int.
1090 *
1091 * @param argument a Java boxed value
1092 * @param localKind the kind of the {@link Local} to which {@code argument} will be bound
1093 */
1094 protected JavaConstant forBoxed(Object argument, JavaKind localKind) {
1095 assert localKind == localKind.getStackKind();
1096 if (localKind == JavaKind.Int) {
1097 return JavaConstant.forBoxedPrimitive(argument);
1098 }
1099 return snippetReflection.forBoxed(localKind, argument);
1100 }
1101
1102 /**
1103 * Logic for replacing a snippet-lowered node at its usages with the return value of the
1104 * snippet. An alternative to the {@linkplain SnippetTemplate#DEFAULT_REPLACER default}
1105 * replacement logic can be used to handle mismatches between the stamp of the node being
1106 * lowered and the stamp of the snippet's return value.
1107 */
1108 public interface UsageReplacer {
1109 /**
1110 * Replaces all usages of {@code oldNode} with direct or indirect usages of {@code newNode}.
1111 */
1112 void replace(ValueNode oldNode, ValueNode newNode);
1113 }
1114
1115 /**
1116 * Represents the default {@link UsageReplacer usage replacer} logic which simply delegates to
1117 * {@link Node#replaceAtUsages(Node)}.
1118 */
1119 public static final UsageReplacer DEFAULT_REPLACER = new UsageReplacer() {
1120
1121 @Override
1122 public void replace(ValueNode oldNode, ValueNode newNode) {
1123 if (newNode == null) {
1124 assert oldNode.hasNoUsages();
1125 } else {
1126 oldNode.replaceAtUsages(newNode);
1127 }
1128 }
1129 };
1130
1131 private boolean assertSnippetKills(ValueNode replacee) {
1132 if (!replacee.graph().isAfterFloatingReadPhase()) {
1133 // no floating reads yet, ignore locations created while lowering
1134 return true;
1135 }
1136 if (returnNode == null) {
1137 // The snippet terminates control flow
1138 return true;
1139 }
1140 MemoryMapNode memoryMap = returnNode.getMemoryMap();
1141 if (memoryMap == null || memoryMap.isEmpty()) {
1142 // there are no kills in the snippet graph
1143 return true;
1144 }
1145
1146 Set<LocationIdentity> kills = new HashSet<>(memoryMap.getLocations());
1147
1148 if (replacee instanceof MemoryCheckpoint.Single) {
1149 // check if some node in snippet graph also kills the same location
1150 LocationIdentity locationIdentity = ((MemoryCheckpoint.Single) replacee).getLocationIdentity();
1151 if (locationIdentity.isAny()) {
1152 assert !(memoryMap.getLastLocationAccess(any()) instanceof MemoryAnchorNode) : replacee + " kills ANY_LOCATION, but snippet does not";
1153 // if the replacee kills ANY_LOCATION, the snippet can kill arbitrary locations
1154 return true;
1155 }
1156 assert kills.contains(locationIdentity) : replacee + " kills " + locationIdentity + ", but snippet doesn't contain a kill to this location";
1157 kills.remove(locationIdentity);
1158 }
1159 assert !(replacee instanceof MemoryCheckpoint.Multi) : replacee + " multi not supported (yet)";
1160
1161 // remove ANY_LOCATION if it's just a kill by the start node
1162 if (memoryMap.getLastLocationAccess(any()) instanceof MemoryAnchorNode) {
1163 kills.remove(any());
1164 }
1165
1166 // node can only lower to a ANY_LOCATION kill if the replacee also kills ANY_LOCATION
1167 assert !kills.contains(any()) : "snippet graph contains a kill to ANY_LOCATION, but replacee (" + replacee + ") doesn't kill ANY_LOCATION. kills: " + kills;
1168
1169 /*
1170 * Kills to private locations are safe, since there can be no floating read to these
1171 * locations except reads that are introduced by the snippet itself or related snippets in
1172 * the same lowering round. These reads are anchored to a MemoryAnchor at the beginning of
1173 * their snippet, so they can not float above a kill in another instance of the same
1174 * snippet.
1175 */
1176 for (LocationIdentity p : this.info.privateLocations) {
1177 kills.remove(p);
1178 }
1179
1180 assert kills.isEmpty() : "snippet graph kills non-private locations " + Arrays.toString(kills.toArray()) + " that replacee (" + replacee + ") doesn't kill";
1181 return true;
1182 }
1183
1184 private static class MemoryInputMap implements MemoryMap {
1185
1186 private final LocationIdentity locationIdentity;
1187 private final MemoryNode lastLocationAccess;
1188
1189 MemoryInputMap(ValueNode replacee) {
1190 if (replacee instanceof MemoryAccess) {
1191 MemoryAccess access = (MemoryAccess) replacee;
1192 locationIdentity = access.getLocationIdentity();
1193 lastLocationAccess = access.getLastLocationAccess();
1194 } else {
1195 locationIdentity = null;
1196 lastLocationAccess = null;
1197 }
1198 }
1199
1200 @Override
1201 public MemoryNode getLastLocationAccess(LocationIdentity location) {
1202 if (locationIdentity != null && locationIdentity.equals(location)) {
1203 return lastLocationAccess;
1204 } else {
1205 return null;
1206 }
1207 }
1208
1209 @Override
1210 public Collection<LocationIdentity> getLocations() {
1211 if (locationIdentity == null) {
1212 return Collections.emptySet();
1213 } else {
1214 return Collections.singleton(locationIdentity);
1215 }
1216 }
1217 }
1218
1219 private class MemoryOutputMap extends MemoryInputMap {
1220
1221 private final Map<Node, Node> duplicates;
1222
1223 MemoryOutputMap(ValueNode replacee, Map<Node, Node> duplicates) {
1224 super(replacee);
1225 this.duplicates = duplicates;
1226 }
1227
1228 @Override
1229 public MemoryNode getLastLocationAccess(LocationIdentity locationIdentity) {
1230 MemoryMapNode memoryMap = returnNode.getMemoryMap();
1231 assert memoryMap != null : "no memory map stored for this snippet graph (snippet doesn't have a ReturnNode?)";
1232 MemoryNode lastLocationAccess = memoryMap.getLastLocationAccess(locationIdentity);
1233 assert lastLocationAccess != null : locationIdentity;
1234 if (lastLocationAccess == memoryAnchor) {
1235 return super.getLastLocationAccess(locationIdentity);
1236 } else {
1237 return (MemoryNode) duplicates.get(ValueNodeUtil.asNode(lastLocationAccess));
1238 }
1239 }
1240
1241 @Override
1242 public Collection<LocationIdentity> getLocations() {
1243 return returnNode.getMemoryMap().getLocations();
1244 }
1245 }
1246
1247 private void rewireMemoryGraph(ValueNode replacee, Map<Node, Node> duplicates) {
1248 if (replacee.graph().isAfterFloatingReadPhase()) {
1249 // rewire outgoing memory edges
1250 replaceMemoryUsages(replacee, new MemoryOutputMap(replacee, duplicates));
1251
1252 if (returnNode != null) {
1253 ReturnNode ret = (ReturnNode) duplicates.get(returnNode);
1254 if (ret != null) {
1255 MemoryMapNode memoryMap = ret.getMemoryMap();
1256 if (memoryMap != null) {
1257 ret.setMemoryMap(null);
1258 memoryMap.safeDelete();
1259 }
1260 }
1261 }
1262 if (memoryAnchor != null) {
1263 // rewire incoming memory edges
1264 MemoryAnchorNode memoryDuplicate = (MemoryAnchorNode) duplicates.get(memoryAnchor);
1265 replaceMemoryUsages(memoryDuplicate, new MemoryInputMap(replacee));
1266
1267 if (memoryDuplicate.hasNoUsages()) {
1268 if (memoryDuplicate.next() != null) {
1269 memoryDuplicate.graph().removeFixed(memoryDuplicate);
1270 } else {
1271 // this was a dummy memory node used when instantiating pure data-flow
1272 // snippets: it was not attached to the control flow.
1273 memoryDuplicate.safeDelete();
1274 }
1275 }
1276 }
1277 }
1278 }
1279
1280 private static LocationIdentity getLocationIdentity(Node node) {
1281 if (node instanceof MemoryAccess) {
1282 return ((MemoryAccess) node).getLocationIdentity();
1283 } else if (node instanceof MemoryProxy) {
1284 return ((MemoryProxy) node).getLocationIdentity();
1285 } else if (node instanceof MemoryPhiNode) {
1286 return ((MemoryPhiNode) node).getLocationIdentity();
1287 } else {
1288 return null;
1289 }
1290 }
1291
1292 private void replaceMemoryUsages(ValueNode node, MemoryMap map) {
1293 for (Node usage : node.usages().snapshot()) {
1294 if (usage instanceof MemoryMapNode) {
1295 continue;
1296 }
1297
1298 LocationIdentity location = getLocationIdentity(usage);
1299 if (location != null) {
1300 for (Position pos : usage.inputPositions()) {
1301 if (pos.getInputType() == InputType.Memory && pos.get(usage) == node) {
1302 MemoryNode replacement = map.getLastLocationAccess(location);
1303 if (replacement == null) {
1304 assert mayRemoveLocation || LocationIdentity.any().equals(location) || Arrays.stream(info.privateLocations).anyMatch(Predicate.isEqual(location)) : "Snippet " +
1305 info.method.format("%h.%n") + " contains access to the non-private location " + location + ", but replacee doesn't access this location." +
1306 map.getLocations();
1307 } else {
1308 pos.set(usage, replacement.asNode());
1309 }
1310 }
1311 }
1312 }
1313 }
1314 }
1315
1316 /**
1317 * Replaces a given fixed node with this specialized snippet.
1318 *
1319 * @param metaAccess
1320 * @param replacee the node that will be replaced
1321 * @param replacer object that replaces the usages of {@code replacee}
1322 * @param args the arguments to be bound to the flattened positional parameters of the snippet
1323 * @return the map of duplicated nodes (original -> duplicate)
1324 */
1325 @SuppressWarnings("try")
1326 public Map<Node, Node> instantiate(MetaAccessProvider metaAccess, FixedNode replacee, UsageReplacer replacer, Arguments args) {
1327 assert assertSnippetKills(replacee);
1328 try (DebugCloseable a = args.info.instantiationTimer.start(); DebugCloseable b = instantiationTimer.start()) {
1329 args.info.instantiationCounter.increment();
1330 instantiationCounter.increment();
1331 // Inline the snippet nodes, replacing parameters with the given args in the process
1332 StartNode entryPointNode = snippet.start();
1333 FixedNode firstCFGNode = entryPointNode.next();
1334 StructuredGraph replaceeGraph = replacee.graph();
1335 Map<Node, Node> replacements = bind(replaceeGraph, metaAccess, args);
1336 replacements.put(entryPointNode, AbstractBeginNode.prevBegin(replacee));
1337 Map<Node, Node> duplicates = replaceeGraph.addDuplicates(nodes, snippet, snippet.getNodeCount(), replacements);
1338 Debug.dump(Debug.INFO_LOG_LEVEL, replaceeGraph, "After inlining snippet %s", snippet.method());
1339
1340 // Re-wire the control flow graph around the replacee
1341 FixedNode firstCFGNodeDuplicate = (FixedNode) duplicates.get(firstCFGNode);
1342 replacee.replaceAtPredecessor(firstCFGNodeDuplicate);
1343
1344 rewireFrameStates(replacee, duplicates);
1345
1346 if (replacee instanceof DeoptimizingNode) {
1347 DeoptimizingNode replaceeDeopt = (DeoptimizingNode) replacee;
1348
1349 FrameState stateBefore = null;
1350 FrameState stateDuring = null;
1351 FrameState stateAfter = null;
1352 if (replaceeDeopt.canDeoptimize()) {
1353 if (replaceeDeopt instanceof DeoptimizingNode.DeoptBefore) {
1354 stateBefore = ((DeoptimizingNode.DeoptBefore) replaceeDeopt).stateBefore();
1355 }
1356 if (replaceeDeopt instanceof DeoptimizingNode.DeoptDuring) {
1357 stateDuring = ((DeoptimizingNode.DeoptDuring) replaceeDeopt).stateDuring();
1358 }
1359 if (replaceeDeopt instanceof DeoptimizingNode.DeoptAfter) {
1360 stateAfter = ((DeoptimizingNode.DeoptAfter) replaceeDeopt).stateAfter();
1361 }
1362 }
1363
1364 for (DeoptimizingNode deoptNode : deoptNodes) {
1365 DeoptimizingNode deoptDup = (DeoptimizingNode) duplicates.get(deoptNode);
1366 if (deoptDup.canDeoptimize()) {
1367 if (deoptDup instanceof DeoptimizingNode.DeoptBefore) {
1368 ((DeoptimizingNode.DeoptBefore) deoptDup).setStateBefore(stateBefore);
1369 }
1370 if (deoptDup instanceof DeoptimizingNode.DeoptDuring) {
1371 DeoptimizingNode.DeoptDuring deoptDupDuring = (DeoptimizingNode.DeoptDuring) deoptDup;
1372 if (stateDuring != null) {
1373 deoptDupDuring.setStateDuring(stateDuring);
1374 } else if (stateAfter != null) {
1375 deoptDupDuring.computeStateDuring(stateAfter);
1376 } else if (stateBefore != null) {
1377 assert !deoptDupDuring.hasSideEffect() : "can't use stateBefore as stateDuring for state split " + deoptDupDuring;
1378 deoptDupDuring.setStateDuring(stateBefore);
1379 }
1380 }
1381 if (deoptDup instanceof DeoptimizingNode.DeoptAfter) {
1382 DeoptimizingNode.DeoptAfter deoptDupAfter = (DeoptimizingNode.DeoptAfter) deoptDup;
1383 if (stateAfter != null) {
1384 deoptDupAfter.setStateAfter(stateAfter);
1385 } else {
1386 assert !deoptDupAfter.hasSideEffect() : "can't use stateBefore as stateAfter for state split " + deoptDupAfter;
1387 deoptDupAfter.setStateAfter(stateBefore);
1388 }
1389
1390 }
1391 }
1392 }
1393 }
1394
1395 updateStamps(replacee, duplicates);
1396
1397 if (UseGraalInstrumentation.getValue()) {
1398 for (InstrumentationNode instrumentation : replaceeGraph.getNodes().filter(InstrumentationNode.class)) {
1399 if (instrumentation.getTarget() == replacee) {
1400 instrumentation.replaceFirstInput(replacee, firstCFGNodeDuplicate);
1401 }
1402 }
1403 }
1404
1405 rewireMemoryGraph(replacee, duplicates);
1406
1407 // Replace all usages of the replacee with the value returned by the snippet
1408 ValueNode returnValue = null;
1409 if (returnNode != null && !(replacee instanceof ControlSinkNode)) {
1410 ReturnNode returnDuplicate = (ReturnNode) duplicates.get(returnNode);
1411 returnValue = returnDuplicate.result();
1412 if (returnValue == null && replacee.usages().isNotEmpty() && replacee instanceof MemoryCheckpoint) {
1413 replacer.replace(replacee, null);
1414 } else {
1415 assert returnValue != null || replacee.hasNoUsages();
1416 replacer.replace(replacee, returnValue);
1417 }
1418 if (returnDuplicate.isAlive()) {
1419 FixedNode next = null;
1420 if (replacee instanceof FixedWithNextNode) {
1421 FixedWithNextNode fwn = (FixedWithNextNode) replacee;
1422 next = fwn.next();
1423 fwn.setNext(null);
1424 }
1425 returnDuplicate.replaceAndDelete(next);
1426 }
1427 }
1428
1429 // Remove the replacee from its graph
1430 GraphUtil.killCFG(replacee);
1431
1432 Debug.dump(Debug.INFO_LOG_LEVEL, replaceeGraph, "After lowering %s with %s", replacee, this);
1433 return duplicates;
1434 }
1435 }
1436
1437 private void propagateStamp(Node node) {
1438 if (node instanceof PhiNode) {
1439 PhiNode phi = (PhiNode) node;
1440 if (phi.inferStamp()) {
1441 for (Node usage : node.usages()) {
1442 propagateStamp(usage);
1443 }
1444 }
1445 }
1446 }
1447
1448 private void updateStamps(ValueNode replacee, Map<Node, Node> duplicates) {
1449 for (ValueNode stampNode : stampNodes) {
1450 Node stampDup = duplicates.get(stampNode);
1451 ((ValueNode) stampDup).setStamp(replacee.stamp());
1452 }
1453 for (ParameterNode paramNode : snippet.getNodes(ParameterNode.TYPE)) {
1454 for (Node usage : paramNode.usages()) {
1455 Node usageDup = duplicates.get(usage);
1456 propagateStamp(usageDup);
1457 }
1458 }
1459 }
1460
1461 /**
1462 * Gets a copy of the specialized graph.
1463 */
1464 public StructuredGraph copySpecializedGraph() {
1465 return (StructuredGraph) snippet.copy();
1466 }
1467
1468 /**
1469 * Replaces a given floating node with this specialized snippet.
1470 *
1471 * @param metaAccess
1472 * @param replacee the node that will be replaced
1473 * @param replacer object that replaces the usages of {@code replacee}
1474 * @param tool lowering tool used to insert the snippet into the control-flow
1475 * @param args the arguments to be bound to the flattened positional parameters of the snippet
1476 */
1477 @SuppressWarnings("try")
1478 public void instantiate(MetaAccessProvider metaAccess, FloatingNode replacee, UsageReplacer replacer, LoweringTool tool, Arguments args) {
1479 assert assertSnippetKills(replacee);
1480 try (DebugCloseable a = args.info.instantiationTimer.start()) {
1481 args.info.instantiationCounter.increment();
1482 instantiationCounter.increment();
1483
1484 // Inline the snippet nodes, replacing parameters with the given args in the process
1485 StartNode entryPointNode = snippet.start();
1486 FixedNode firstCFGNode = entryPointNode.next();
1487 StructuredGraph replaceeGraph = replacee.graph();
1488 Map<Node, Node> replacements = bind(replaceeGraph, metaAccess, args);
1489 replacements.put(entryPointNode, tool.getCurrentGuardAnchor().asNode());
1490 Map<Node, Node> duplicates = replaceeGraph.addDuplicates(nodes, snippet, snippet.getNodeCount(), replacements);
1491 Debug.dump(Debug.INFO_LOG_LEVEL, replaceeGraph, "After inlining snippet %s", snippet.method());
1492
1493 FixedWithNextNode lastFixedNode = tool.lastFixedNode();
1494 assert lastFixedNode != null && lastFixedNode.isAlive() : replaceeGraph + " lastFixed=" + lastFixedNode;
1495 FixedNode next = lastFixedNode.next();
1496 lastFixedNode.setNext(null);
1497 FixedNode firstCFGNodeDuplicate = (FixedNode) duplicates.get(firstCFGNode);
1498 replaceeGraph.addAfterFixed(lastFixedNode, firstCFGNodeDuplicate);
1499
1500 rewireFrameStates(replacee, duplicates);
1501 updateStamps(replacee, duplicates);
1502
1503 rewireMemoryGraph(replacee, duplicates);
1504
1505 // Replace all usages of the replacee with the value returned by the snippet
1506 ReturnNode returnDuplicate = (ReturnNode) duplicates.get(returnNode);
1507 ValueNode returnValue = returnDuplicate.result();
1508 assert returnValue != null || replacee.hasNoUsages();
1509 replacer.replace(replacee, returnValue);
1510
1511 if (returnDuplicate.isAlive()) {
1512 returnDuplicate.replaceAndDelete(next);
1513 }
1514
1515 Debug.dump(Debug.INFO_LOG_LEVEL, replaceeGraph, "After lowering %s with %s", replacee, this);
1516 }
1517 }
1518
1519 /**
1520 * Replaces a given floating node with this specialized snippet.
1521 *
1522 * This snippet must be pure data-flow
1523 *
1524 * @param metaAccess
1525 * @param replacee the node that will be replaced
1526 * @param replacer object that replaces the usages of {@code replacee}
1527 * @param args the arguments to be bound to the flattened positional parameters of the snippet
1528 */
1529 @SuppressWarnings("try")
1530 public void instantiate(MetaAccessProvider metaAccess, FloatingNode replacee, UsageReplacer replacer, Arguments args) {
1531 assert assertSnippetKills(replacee);
1532 try (DebugCloseable a = args.info.instantiationTimer.start()) {
1533 args.info.instantiationCounter.increment();
1534 instantiationCounter.increment();
1535
1536 // Inline the snippet nodes, replacing parameters with the given args in the process
1537 StartNode entryPointNode = snippet.start();
1538 assert entryPointNode.next() == (memoryAnchor == null ? returnNode : memoryAnchor) : entryPointNode.next();
1539 StructuredGraph replaceeGraph = replacee.graph();
1540 Map<Node, Node> replacements = bind(replaceeGraph, metaAccess, args);
1541 MemoryAnchorNode anchorDuplicate = null;
1542 if (memoryAnchor != null) {
1543 anchorDuplicate = replaceeGraph.add(new MemoryAnchorNode());
1544 replacements.put(memoryAnchor, anchorDuplicate);
1545 }
1546 List<Node> floatingNodes = new ArrayList<>(nodes.size() - 2);
1547 for (Node n : nodes) {
1548 if (n != entryPointNode && n != returnNode) {
1549 floatingNodes.add(n);
1550 }
1551 }
1552 Map<Node, Node> duplicates = replaceeGraph.addDuplicates(floatingNodes, snippet, floatingNodes.size(), replacements);
1553 Debug.dump(Debug.INFO_LOG_LEVEL, replaceeGraph, "After inlining snippet %s", snippet.method());
1554
1555 rewireFrameStates(replacee, duplicates);
1556 updateStamps(replacee, duplicates);
1557
1558 rewireMemoryGraph(replacee, duplicates);
1559 assert anchorDuplicate == null || anchorDuplicate.isDeleted();
1560
1561 // Replace all usages of the replacee with the value returned by the snippet
1562 ValueNode returnValue = (ValueNode) duplicates.get(returnNode.result());
1563 replacer.replace(replacee, returnValue);
1564
1565 Debug.dump(Debug.INFO_LOG_LEVEL, replaceeGraph, "After lowering %s with %s", replacee, this);
1566 }
1567 }
1568
1569 protected void rewireFrameStates(ValueNode replacee, Map<Node, Node> duplicates) {
1570 if (replacee instanceof StateSplit) {
1571 for (StateSplit sideEffectNode : sideEffectNodes) {
1572 assert ((StateSplit) replacee).hasSideEffect();
1573 Node sideEffectDup = duplicates.get(sideEffectNode);
1574 ((StateSplit) sideEffectDup).setStateAfter(((StateSplit) replacee).stateAfter());
1575 }
1576 }
1577 }
1578
1579 @Override
1580 public String toString() {
1581 StringBuilder buf = new StringBuilder(snippet.toString()).append('(');
1582 String sep = "";
1583 for (int i = 0; i < parameters.length; i++) {
1584 String name = "[" + i + "]";
1585 Object value = parameters[i];
1586 buf.append(sep);
1587 sep = ", ";
1588 if (value == null) {
1589 buf.append("<null> ").append(name);
1590 } else if (value.equals(UNUSED_PARAMETER)) {
1591 buf.append("<unused> ").append(name);
1592 } else if (value.equals(CONSTANT_PARAMETER)) {
1593 buf.append("<constant> ").append(name);
1594 } else if (value instanceof ParameterNode) {
1595 ParameterNode param = (ParameterNode) value;
1596 buf.append(param.getStackKind().getJavaName()).append(' ').append(name);
1597 } else {
1598 ParameterNode[] params = (ParameterNode[]) value;
1599 String kind = params.length == 0 ? "?" : params[0].getStackKind().getJavaName();
1600 buf.append(kind).append('[').append(params.length).append("] ").append(name);
1601 }
1602 }
1603 return buf.append(')').toString();
1604 }
1605
1606 private static boolean checkTemplate(MetaAccessProvider metaAccess, Arguments args, ResolvedJavaMethod method, Signature signature) {
1607 for (int i = 0; i < args.info.getParameterCount(); i++) {
1608 if (args.info.isConstantParameter(i)) {
1609 JavaKind kind = signature.getParameterKind(i);
1610 assert checkConstantArgument(metaAccess, method, signature, i, args.info.getParameterName(i), args.values[i], kind);
1611
1612 } else if (args.info.isVarargsParameter(i)) {
1613 assert args.values[i] instanceof Varargs;
1614 Varargs varargs = (Varargs) args.values[i];
1615 assert checkVarargs(metaAccess, method, signature, i, args.info.getParameterName(i), varargs);
1616 }
1617 }
1618 return true;
1619 }
1620
1621 public void setMayRemoveLocation(boolean mayRemoveLocation) {
1622 this.mayRemoveLocation = mayRemoveLocation;
1623 }
1624 }