1 /*
2 * Copyright (c) 2011, 2018, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24
25 package org.graalvm.compiler.nodes;
26
27 import java.util.ArrayList;
28 import java.util.Collections;
29 import java.util.Iterator;
30 import java.util.List;
31 import java.util.SortedSet;
32 import java.util.TreeSet;
33 import java.util.concurrent.atomic.AtomicLong;
34 import java.util.function.Consumer;
35 import java.util.stream.Collectors;
36
37 import jdk.internal.vm.compiler.collections.EconomicMap;
38 import jdk.internal.vm.compiler.collections.EconomicSet;
39 import jdk.internal.vm.compiler.collections.Equivalence;
40 import jdk.internal.vm.compiler.collections.UnmodifiableEconomicMap;
41 import org.graalvm.compiler.api.replacements.MethodSubstitution;
42 import org.graalvm.compiler.api.replacements.Snippet;
43 import org.graalvm.compiler.core.common.CancellationBailoutException;
44 import org.graalvm.compiler.core.common.CompilationIdentifier;
45 import org.graalvm.compiler.core.common.GraalOptions;
46 import org.graalvm.compiler.core.common.cfg.BlockMap;
47 import org.graalvm.compiler.core.common.type.Stamp;
48 import org.graalvm.compiler.debug.DebugContext;
49 import org.graalvm.compiler.debug.JavaMethodContext;
50 import org.graalvm.compiler.debug.TTY;
51 import org.graalvm.compiler.graph.Graph;
52 import org.graalvm.compiler.graph.Node;
53 import org.graalvm.compiler.graph.NodeMap;
54 import org.graalvm.compiler.graph.NodeSourcePosition;
55 import org.graalvm.compiler.nodes.calc.FloatingNode;
56 import org.graalvm.compiler.nodes.cfg.Block;
57 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
58 import org.graalvm.compiler.nodes.java.MethodCallTargetNode;
59 import org.graalvm.compiler.nodes.spi.VirtualizableAllocation;
60 import org.graalvm.compiler.nodes.util.GraphUtil;
61 import org.graalvm.compiler.options.OptionValues;
62
63 import jdk.vm.ci.code.BytecodeFrame;
64 import jdk.vm.ci.meta.Assumptions;
65 import jdk.vm.ci.meta.Assumptions.Assumption;
66 import jdk.vm.ci.meta.DefaultProfilingInfo;
67 import jdk.vm.ci.meta.JavaMethod;
68 import jdk.vm.ci.meta.ProfilingInfo;
69 import jdk.vm.ci.meta.ResolvedJavaField;
70 import jdk.vm.ci.meta.ResolvedJavaMethod;
71 import jdk.vm.ci.meta.SpeculationLog;
72 import jdk.vm.ci.meta.TriState;
73 import jdk.vm.ci.runtime.JVMCICompiler;
74
75 /**
76 * A graph that contains at least one distinguished node : the {@link #start() start} node. This
77 * node is the start of the control flow of the graph.
78 */
79 public final class StructuredGraph extends Graph implements JavaMethodContext {
80
81 /**
82 * The different stages of the compilation of a {@link Graph} regarding the status of
83 * {@link GuardNode guards}, {@link DeoptimizingNode deoptimizations} and {@link FrameState
84 * framestates}. The stage of a graph progresses monotonously.
85 *
86 */
87 public enum GuardsStage {
88 /**
89 * During this stage, there can be {@link FloatingNode floating} {@link DeoptimizingNode}
90 * such as {@link GuardNode GuardNodes}. New {@link DeoptimizingNode DeoptimizingNodes} can
91 * be introduced without constraints. {@link FrameState} nodes are associated with
92 * {@link StateSplit} nodes.
93 */
94 FLOATING_GUARDS,
95 /**
96 * During this stage, all {@link DeoptimizingNode DeoptimizingNodes} must be
97 * {@link FixedNode fixed} but new {@link DeoptimizingNode DeoptimizingNodes} can still be
98 * introduced. {@link FrameState} nodes are still associated with {@link StateSplit} nodes.
99 */
100 FIXED_DEOPTS,
101 /**
102 * During this stage, all {@link DeoptimizingNode DeoptimizingNodes} must be
103 * {@link FixedNode fixed}. New {@link DeoptimizingNode DeoptimizingNodes} can not be
104 * introduced any more. {@link FrameState} nodes are now associated with
105 * {@link DeoptimizingNode} nodes.
106 */
107 AFTER_FSA;
108
109 public boolean allowsFloatingGuards() {
110 return this == FLOATING_GUARDS;
111 }
112
113 public boolean allowsGuardInsertion() {
114 return this.ordinal() <= FIXED_DEOPTS.ordinal();
115 }
116
117 public boolean areFrameStatesAtDeopts() {
118 return this == AFTER_FSA;
119 }
120
121 public boolean areFrameStatesAtSideEffects() {
122 return !this.areFrameStatesAtDeopts();
123 }
124
125 public boolean areDeoptsFixed() {
126 return this.ordinal() >= FIXED_DEOPTS.ordinal();
127 }
128 }
129
130 /**
131 * Constants denoting whether or not {@link Assumption}s can be made while processing a graph.
132 */
133 public enum AllowAssumptions {
134 YES,
135 NO;
136 public static AllowAssumptions ifTrue(boolean flag) {
137 return flag ? YES : NO;
138 }
139
140 public static AllowAssumptions ifNonNull(Assumptions assumptions) {
141 return assumptions != null ? YES : NO;
142 }
143 }
144
145 public static class ScheduleResult {
146 private final ControlFlowGraph cfg;
147 private final NodeMap<Block> nodeToBlockMap;
148 private final BlockMap<List<Node>> blockToNodesMap;
149
150 public ScheduleResult(ControlFlowGraph cfg, NodeMap<Block> nodeToBlockMap, BlockMap<List<Node>> blockToNodesMap) {
151 this.cfg = cfg;
152 this.nodeToBlockMap = nodeToBlockMap;
153 this.blockToNodesMap = blockToNodesMap;
154 }
155
156 public ControlFlowGraph getCFG() {
157 return cfg;
158 }
159
160 public NodeMap<Block> getNodeToBlockMap() {
161 return nodeToBlockMap;
162 }
163
164 public BlockMap<List<Node>> getBlockToNodesMap() {
165 return blockToNodesMap;
166 }
167
168 public List<Node> nodesFor(Block block) {
169 return blockToNodesMap.get(block);
170 }
171 }
172
173 /**
174 * Object used to create a {@link StructuredGraph}.
175 */
176 public static class Builder {
177 private String name;
178 private final Assumptions assumptions;
179 private SpeculationLog speculationLog;
180 private ResolvedJavaMethod rootMethod;
181 private CompilationIdentifier compilationId = CompilationIdentifier.INVALID_COMPILATION_ID;
182 private int entryBCI = JVMCICompiler.INVOCATION_ENTRY_BCI;
183 private boolean useProfilingInfo = true;
184 private boolean recordInlinedMethods = true;
185 private boolean trackNodeSourcePosition;
186 private final OptionValues options;
187 private Cancellable cancellable = null;
188 private final DebugContext debug;
189 private NodeSourcePosition callerContext;
190 private boolean isSubstitution;
191
192 /**
193 * Creates a builder for a graph.
194 */
195 public Builder(OptionValues options, DebugContext debug, AllowAssumptions allowAssumptions) {
196 this.options = options;
197 this.debug = debug;
198 this.assumptions = allowAssumptions == AllowAssumptions.YES ? new Assumptions() : null;
199 this.trackNodeSourcePosition = Graph.trackNodeSourcePositionDefault(options, debug);
200 }
201
202 /**
203 * Creates a builder for a graph that does not support {@link Assumptions}.
204 */
205 public Builder(OptionValues options, DebugContext debug) {
206 this.options = options;
207 this.debug = debug;
208 this.assumptions = null;
209 this.trackNodeSourcePosition = Graph.trackNodeSourcePositionDefault(options, debug);
210 }
211
212 public String getName() {
213 return name;
214 }
215
216 public Builder name(String s) {
217 this.name = s;
218 return this;
219 }
220
221 /**
222 * @see StructuredGraph#isSubstitution
223 */
224 public Builder setIsSubstitution(boolean flag) {
225 this.isSubstitution = flag;
226 return this;
227 }
228
229 public ResolvedJavaMethod getMethod() {
230 return rootMethod;
231 }
232
233 public Builder method(ResolvedJavaMethod method) {
234 this.rootMethod = method;
235 return this;
236 }
237
238 public DebugContext getDebug() {
239 return debug;
240 }
241
242 public SpeculationLog getSpeculationLog() {
243 return speculationLog;
244 }
245
246 public Builder speculationLog(SpeculationLog log) {
247 this.speculationLog = log;
248 return this;
249 }
250
251 public CompilationIdentifier getCompilationId() {
252 return compilationId;
253 }
254
255 public Builder compilationId(CompilationIdentifier id) {
256 this.compilationId = id;
257 return this;
258 }
259
260 public Cancellable getCancellable() {
261 return cancellable;
262 }
263
264 public Builder cancellable(Cancellable cancel) {
265 this.cancellable = cancel;
266 return this;
267 }
268
269 public int getEntryBCI() {
270 return entryBCI;
271 }
272
273 public Builder entryBCI(int bci) {
274 this.entryBCI = bci;
275 return this;
276 }
277
278 public boolean getUseProfilingInfo() {
279 return useProfilingInfo;
280 }
281
282 public Builder useProfilingInfo(boolean flag) {
283 this.useProfilingInfo = flag;
284 return this;
285 }
286
287 public boolean getRecordInlinedMethods() {
288 return recordInlinedMethods;
289 }
290
291 public Builder recordInlinedMethods(boolean flag) {
292 this.recordInlinedMethods = flag;
293 return this;
294 }
295
296 public Builder trackNodeSourcePosition(boolean flag) {
297 if (flag) {
298 this.trackNodeSourcePosition = true;
299 }
300 return this;
301 }
302
303 public Builder callerContext(NodeSourcePosition context) {
304 this.callerContext = context;
305 return this;
306 }
307
308 public StructuredGraph build() {
309 List<ResolvedJavaMethod> inlinedMethods = recordInlinedMethods ? new ArrayList<>() : null;
310 // @formatter:off
311 return new StructuredGraph(name,
312 rootMethod,
313 entryBCI,
314 assumptions,
315 speculationLog,
316 useProfilingInfo,
317 isSubstitution,
318 inlinedMethods,
319 trackNodeSourcePosition,
320 compilationId,
321 options,
322 debug,
323 cancellable,
324 callerContext);
325 // @formatter:on
326 }
327 }
328
329 public static final long INVALID_GRAPH_ID = -1;
330 private static final AtomicLong uniqueGraphIds = new AtomicLong();
331
332 private StartNode start;
333 private ResolvedJavaMethod rootMethod;
334 private final long graphId;
335 private final CompilationIdentifier compilationId;
336 private final int entryBCI;
337 private GuardsStage guardsStage = GuardsStage.FLOATING_GUARDS;
338 private boolean isAfterFloatingReadPhase = false;
339 private boolean isAfterFixedReadPhase = false;
340 private boolean hasValueProxies = true;
341 private boolean isAfterExpandLogic = false;
342 private final boolean useProfilingInfo;
343 private final Cancellable cancellable;
344 private final boolean isSubstitution;
345
346 /**
347 * The assumptions made while constructing and transforming this graph.
348 */
349 private final Assumptions assumptions;
350
351 private SpeculationLog speculationLog;
352
353 private ScheduleResult lastSchedule;
354
355 private final InliningLog inliningLog;
356
357 /**
358 * Call stack (context) leading to construction of this graph.
359 */
360 private final NodeSourcePosition callerContext;
361
362 /**
363 * Records the methods that were used while constructing this graph, one entry for each time a
364 * specific method is used. This will be {@code null} if recording of inlined methods is
365 * disabled for the graph.
366 */
367 private final List<ResolvedJavaMethod> methods;
368
369 /**
370 * Records the fields that were accessed while constructing this graph.
371 */
372 private EconomicSet<ResolvedJavaField> fields = null;
373
374 private enum UnsafeAccessState {
375 NO_ACCESS,
376 HAS_ACCESS,
377 DISABLED
378 }
379
380 private UnsafeAccessState hasUnsafeAccess = UnsafeAccessState.NO_ACCESS;
381
382 public static final boolean USE_PROFILING_INFO = true;
383
384 public static final boolean NO_PROFILING_INFO = false;
385
386 private StructuredGraph(String name,
387 ResolvedJavaMethod method,
388 int entryBCI,
389 Assumptions assumptions,
390 SpeculationLog speculationLog,
391 boolean useProfilingInfo,
392 boolean isSubstitution,
393 List<ResolvedJavaMethod> methods,
394 boolean trackNodeSourcePosition,
395 CompilationIdentifier compilationId,
396 OptionValues options,
397 DebugContext debug,
398 Cancellable cancellable,
399 NodeSourcePosition context) {
400 super(name, options, debug, trackNodeSourcePosition);
401 this.setStart(add(new StartNode()));
402 this.rootMethod = method;
403 this.graphId = uniqueGraphIds.incrementAndGet();
404 this.compilationId = compilationId;
405 this.entryBCI = entryBCI;
406 this.assumptions = assumptions;
407 this.methods = methods;
408 this.speculationLog = speculationLog;
409 this.useProfilingInfo = useProfilingInfo;
410 this.isSubstitution = isSubstitution;
411 assert checkIsSubstitutionInvariants(method, isSubstitution);
412 this.cancellable = cancellable;
413 this.inliningLog = new InliningLog(rootMethod, GraalOptions.TraceInlining.getValue(options));
414 this.callerContext = context;
415 }
416
417 private static boolean checkIsSubstitutionInvariants(ResolvedJavaMethod method, boolean isSubstitution) {
418 if (method != null) {
419 if (method.getAnnotation(Snippet.class) != null || method.getAnnotation(MethodSubstitution.class) != null) {
420 assert isSubstitution : "Graph for method " + method.format("%H.%n(%p)") +
421 " annotated by " + Snippet.class.getName() + " or " +
422 MethodSubstitution.class.getName() +
423 " must have its `isSubstitution` field set to true";
424 }
425 }
426 return true;
427 }
428
429 public void setLastSchedule(ScheduleResult result) {
430 lastSchedule = result;
431 }
432
433 public ScheduleResult getLastSchedule() {
434 return lastSchedule;
435 }
436
437 public void clearLastSchedule() {
438 setLastSchedule(null);
439 }
440
441 @Override
442 public boolean maybeCompress() {
443 if (super.maybeCompress()) {
444 /*
445 * The schedule contains a NodeMap which is unusable after compression.
446 */
447 clearLastSchedule();
448 return true;
449 }
450 return false;
451 }
452
453 public Stamp getReturnStamp() {
454 Stamp returnStamp = null;
455 for (ReturnNode returnNode : getNodes(ReturnNode.TYPE)) {
456 ValueNode result = returnNode.result();
457 if (result != null) {
458 if (returnStamp == null) {
459 returnStamp = result.stamp(NodeView.DEFAULT);
460 } else {
461 returnStamp = returnStamp.meet(result.stamp(NodeView.DEFAULT));
462 }
463 }
464 }
465 return returnStamp;
466 }
467
468 @Override
469 public String toString() {
470 StringBuilder buf = new StringBuilder(getClass().getSimpleName() + ":" + graphId);
471 String sep = "{";
472 if (name != null) {
473 buf.append(sep);
474 buf.append(name);
475 sep = ", ";
476 }
477 if (method() != null) {
478 buf.append(sep);
479 buf.append(method());
480 sep = ", ";
481 }
482
483 if (!sep.equals("{")) {
484 buf.append("}");
485 }
486 return buf.toString();
487 }
488
489 public StartNode start() {
490 return start;
491 }
492
493 /**
494 * Gets the root method from which this graph was built.
495 *
496 * @return null if this method was not built from a method or the method is not available
497 */
498 public ResolvedJavaMethod method() {
499 return rootMethod;
500 }
501
502 public int getEntryBCI() {
503 return entryBCI;
504 }
505
506 public Cancellable getCancellable() {
507 return cancellable;
508 }
509
510 public void checkCancellation() {
511 if (cancellable != null && cancellable.isCancelled()) {
512 CancellationBailoutException.cancelCompilation();
513 }
514 }
515
516 public boolean isOSR() {
517 return entryBCI != JVMCICompiler.INVOCATION_ENTRY_BCI;
518 }
519
520 public long graphId() {
521 return graphId;
522 }
523
524 /**
525 * @see CompilationIdentifier
526 */
527 public CompilationIdentifier compilationId() {
528 return compilationId;
529 }
530
531 public void setStart(StartNode start) {
532 this.start = start;
533 }
534
535 public InliningLog getInliningLog() {
536 return inliningLog;
537 }
538
539 public void logInliningTree() {
540 if (GraalOptions.TraceInlining.getValue(getOptions())) {
541 String formattedTree = getInliningLog().formatAsTree(true);
542 if (formattedTree != null) {
543 TTY.println(formattedTree);
544 }
545 }
546 }
547
548 /**
549 * Creates a copy of this graph.
550 *
551 * @param newName the name of the copy, used for debugging purposes (can be null)
552 * @param duplicationMapCallback consumer of the duplication map created during the copying
553 * @param debugForCopy the debug context for the graph copy. This must not be the debug for this
554 * graph if this graph can be accessed from multiple threads (e.g., it's in a cache
555 * accessed by multiple threads).
556 */
557 @Override
558 protected Graph copy(String newName, Consumer<UnmodifiableEconomicMap<Node, Node>> duplicationMapCallback, DebugContext debugForCopy) {
559 return copy(newName, duplicationMapCallback, compilationId, debugForCopy);
560 }
561
562 @SuppressWarnings("try")
563 private StructuredGraph copy(String newName, Consumer<UnmodifiableEconomicMap<Node, Node>> duplicationMapCallback, CompilationIdentifier newCompilationId, DebugContext debugForCopy) {
564 AllowAssumptions allowAssumptions = AllowAssumptions.ifNonNull(assumptions);
565 StructuredGraph copy = new StructuredGraph(newName,
566 method(),
567 entryBCI,
568 assumptions == null ? null : new Assumptions(),
569 speculationLog,
570 useProfilingInfo,
571 isSubstitution,
572 methods != null ? new ArrayList<>(methods) : null,
573 trackNodeSourcePosition,
574 newCompilationId,
575 getOptions(), debugForCopy, null, callerContext);
576 if (allowAssumptions == AllowAssumptions.YES && assumptions != null) {
577 copy.assumptions.record(assumptions);
578 }
579 copy.hasUnsafeAccess = hasUnsafeAccess;
580 copy.setGuardsStage(getGuardsStage());
581 copy.isAfterFloatingReadPhase = isAfterFloatingReadPhase;
582 copy.hasValueProxies = hasValueProxies;
583 copy.isAfterExpandLogic = isAfterExpandLogic;
584 copy.trackNodeSourcePosition = trackNodeSourcePosition;
585 if (fields != null) {
586 copy.fields = createFieldSet(fields);
587 }
588 EconomicMap<Node, Node> replacements = EconomicMap.create(Equivalence.IDENTITY);
589 replacements.put(start, copy.start);
590 UnmodifiableEconomicMap<Node, Node> duplicates;
591 try (InliningLog.UpdateScope scope = copy.getInliningLog().openDefaultUpdateScope()) {
592 duplicates = copy.addDuplicates(getNodes(), this, this.getNodeCount(), replacements);
593 if (scope != null) {
594 copy.getInliningLog().replaceLog(duplicates, this.getInliningLog());
595 }
596 }
597 if (duplicationMapCallback != null) {
598 duplicationMapCallback.accept(duplicates);
599 }
600 return copy;
601 }
602
603 /**
604 * @param debugForCopy the debug context for the graph copy. This must not be the debug for this
605 * graph if this graph can be accessed from multiple threads (e.g., it's in a cache
606 * accessed by multiple threads).
607 */
608 public StructuredGraph copyWithIdentifier(CompilationIdentifier newCompilationId, DebugContext debugForCopy) {
609 return copy(name, null, newCompilationId, debugForCopy);
610 }
611
612 public ParameterNode getParameter(int index) {
613 for (ParameterNode param : getNodes(ParameterNode.TYPE)) {
614 if (param.index() == index) {
615 return param;
616 }
617 }
618 return null;
619 }
620
621 public Iterable<Invoke> getInvokes() {
622 final Iterator<MethodCallTargetNode> callTargets = getNodes(MethodCallTargetNode.TYPE).iterator();
623 return new Iterable<Invoke>() {
624
625 private Invoke next;
626
627 @Override
628 public Iterator<Invoke> iterator() {
629 return new Iterator<Invoke>() {
630
631 @Override
632 public boolean hasNext() {
633 if (next == null) {
634 while (callTargets.hasNext()) {
635 Invoke i = callTargets.next().invoke();
636 if (i != null) {
637 next = i;
638 return true;
639 }
640 }
641 return false;
642 } else {
643 return true;
644 }
645 }
646
647 @Override
648 public Invoke next() {
649 try {
650 return next;
651 } finally {
652 next = null;
653 }
654 }
655
656 @Override
657 public void remove() {
658 throw new UnsupportedOperationException();
659 }
660 };
661 }
662 };
663 }
664
665 public boolean hasLoops() {
666 return hasNode(LoopBeginNode.TYPE);
667 }
668
669 /**
670 * Unlinks a node from all its control flow neighbors and then removes it from its graph. The
671 * node must have no {@linkplain Node#usages() usages}.
672 *
673 * @param node the node to be unlinked and removed
674 */
675 @SuppressWarnings("static-method")
676 public void removeFixed(FixedWithNextNode node) {
677 assert node != null;
678 if (node instanceof AbstractBeginNode) {
679 ((AbstractBeginNode) node).prepareDelete();
680 }
681 assert node.hasNoUsages() : node + " " + node.getUsageCount() + ", " + node.usages().first();
682 GraphUtil.unlinkFixedNode(node);
683 node.safeDelete();
684 }
685
686 public void replaceFixed(FixedWithNextNode node, Node replacement) {
687 if (replacement instanceof FixedWithNextNode) {
688 replaceFixedWithFixed(node, (FixedWithNextNode) replacement);
689 } else {
690 assert replacement != null : "cannot replace " + node + " with null";
691 assert replacement instanceof FloatingNode : "cannot replace " + node + " with " + replacement;
692 replaceFixedWithFloating(node, (FloatingNode) replacement);
693 }
694 }
695
696 public void replaceFixedWithFixed(FixedWithNextNode node, FixedWithNextNode replacement) {
697 assert node != null && replacement != null && node.isAlive() && replacement.isAlive() : "cannot replace " + node + " with " + replacement;
698 FixedNode next = node.next();
699 node.setNext(null);
700 replacement.setNext(next);
701 node.replaceAndDelete(replacement);
702 if (node == start) {
703 setStart((StartNode) replacement);
704 }
705 }
706
707 @SuppressWarnings("static-method")
708 public void replaceFixedWithFloating(FixedWithNextNode node, ValueNode replacement) {
709 assert node != null && replacement != null && node.isAlive() && replacement.isAlive() : "cannot replace " + node + " with " + replacement;
710 GraphUtil.unlinkFixedNode(node);
711 node.replaceAtUsagesAndDelete(replacement);
712 }
713
714 @SuppressWarnings("static-method")
715 public void removeSplit(ControlSplitNode node, AbstractBeginNode survivingSuccessor) {
716 assert node != null;
717 assert node.hasNoUsages();
718 assert survivingSuccessor != null;
719 node.clearSuccessors();
720 node.replaceAtPredecessor(survivingSuccessor);
721 node.safeDelete();
722 }
723
724 @SuppressWarnings("static-method")
725 public void removeSplitPropagate(ControlSplitNode node, AbstractBeginNode survivingSuccessor) {
726 assert node != null;
727 assert node.hasNoUsages();
728 assert survivingSuccessor != null;
729 List<Node> snapshot = node.successors().snapshot();
730 node.clearSuccessors();
731 node.replaceAtPredecessor(survivingSuccessor);
732 node.safeDelete();
733 for (Node successor : snapshot) {
734 if (successor != null && successor.isAlive()) {
735 if (successor != survivingSuccessor) {
736 GraphUtil.killCFG((FixedNode) successor);
737 }
738 }
739 }
740 }
741
742 public void replaceSplit(ControlSplitNode node, Node replacement, AbstractBeginNode survivingSuccessor) {
743 if (replacement instanceof FixedWithNextNode) {
744 replaceSplitWithFixed(node, (FixedWithNextNode) replacement, survivingSuccessor);
745 } else {
746 assert replacement != null : "cannot replace " + node + " with null";
747 assert replacement instanceof FloatingNode : "cannot replace " + node + " with " + replacement;
748 replaceSplitWithFloating(node, (FloatingNode) replacement, survivingSuccessor);
749 }
750 }
751
752 @SuppressWarnings("static-method")
753 public void replaceSplitWithFixed(ControlSplitNode node, FixedWithNextNode replacement, AbstractBeginNode survivingSuccessor) {
754 assert node != null && replacement != null && node.isAlive() && replacement.isAlive() : "cannot replace " + node + " with " + replacement;
755 assert survivingSuccessor != null;
756 node.clearSuccessors();
757 replacement.setNext(survivingSuccessor);
758 node.replaceAndDelete(replacement);
759 }
760
761 @SuppressWarnings("static-method")
762 public void replaceSplitWithFloating(ControlSplitNode node, FloatingNode replacement, AbstractBeginNode survivingSuccessor) {
763 assert node != null && replacement != null && node.isAlive() && replacement.isAlive() : "cannot replace " + node + " with " + replacement;
764 assert survivingSuccessor != null;
765 node.clearSuccessors();
766 node.replaceAtPredecessor(survivingSuccessor);
767 node.replaceAtUsagesAndDelete(replacement);
768 }
769
770 @SuppressWarnings("static-method")
771 public void addAfterFixed(FixedWithNextNode node, FixedNode newNode) {
772 assert node != null && newNode != null && node.isAlive() && newNode.isAlive() : "cannot add " + newNode + " after " + node;
773 FixedNode next = node.next();
774 node.setNext(newNode);
775 if (next != null) {
776 assert newNode instanceof FixedWithNextNode;
777 FixedWithNextNode newFixedWithNext = (FixedWithNextNode) newNode;
778 assert newFixedWithNext.next() == null;
779 newFixedWithNext.setNext(next);
780 }
781 }
782
783 @SuppressWarnings("static-method")
784 public void addBeforeFixed(FixedNode node, FixedWithNextNode newNode) {
785 assert node != null && newNode != null && node.isAlive() && newNode.isAlive() : "cannot add " + newNode + " before " + node;
786 assert node.predecessor() != null && node.predecessor() instanceof FixedWithNextNode : "cannot add " + newNode + " before " + node;
787 assert newNode.next() == null : newNode;
788 assert !(node instanceof AbstractMergeNode);
789 FixedWithNextNode pred = (FixedWithNextNode) node.predecessor();
790 pred.setNext(newNode);
791 newNode.setNext(node);
792 }
793
794 public void reduceDegenerateLoopBegin(LoopBeginNode begin) {
795 assert begin.loopEnds().isEmpty() : "Loop begin still has backedges";
796 if (begin.forwardEndCount() == 1) { // bypass merge and remove
797 reduceTrivialMerge(begin);
798 } else { // convert to merge
799 AbstractMergeNode merge = this.add(new MergeNode());
800 for (EndNode end : begin.forwardEnds()) {
801 merge.addForwardEnd(end);
802 }
803 this.replaceFixedWithFixed(begin, merge);
804 }
805 }
806
807 @SuppressWarnings("static-method")
808 public void reduceTrivialMerge(AbstractMergeNode merge) {
809 assert merge.forwardEndCount() == 1;
810 assert !(merge instanceof LoopBeginNode) || ((LoopBeginNode) merge).loopEnds().isEmpty();
811 for (PhiNode phi : merge.phis().snapshot()) {
812 assert phi.valueCount() == 1;
813 ValueNode singleValue = phi.valueAt(0);
814 if (phi.hasUsages()) {
815 phi.replaceAtUsagesAndDelete(singleValue);
816 } else {
817 phi.safeDelete();
818 if (singleValue != null) {
819 GraphUtil.tryKillUnused(singleValue);
820 }
821 }
822 }
823 // remove loop exits
824 if (merge instanceof LoopBeginNode) {
825 ((LoopBeginNode) merge).removeExits();
826 }
827 AbstractEndNode singleEnd = merge.forwardEndAt(0);
828 FixedNode sux = merge.next();
829 FrameState stateAfter = merge.stateAfter();
830 // evacuateGuards
831 merge.prepareDelete((FixedNode) singleEnd.predecessor());
832 merge.safeDelete();
833 if (stateAfter != null) {
834 GraphUtil.tryKillUnused(stateAfter);
835 }
836 if (sux == null) {
837 singleEnd.replaceAtPredecessor(null);
838 singleEnd.safeDelete();
839 } else {
840 singleEnd.replaceAndDelete(sux);
841 }
842 }
843
844 public GuardsStage getGuardsStage() {
845 return guardsStage;
846 }
847
848 public void setGuardsStage(GuardsStage guardsStage) {
849 assert guardsStage.ordinal() >= this.guardsStage.ordinal();
850 this.guardsStage = guardsStage;
851 }
852
853 public boolean isAfterFloatingReadPhase() {
854 return isAfterFloatingReadPhase;
855 }
856
857 public boolean isAfterFixedReadPhase() {
858 return isAfterFixedReadPhase;
859 }
860
861 public void setAfterFloatingReadPhase(boolean state) {
862 assert state : "cannot 'unapply' floating read phase on graph";
863 isAfterFloatingReadPhase = state;
864 }
865
866 public void setAfterFixReadPhase(boolean state) {
867 assert state : "cannot 'unapply' fix reads phase on graph";
868 isAfterFixedReadPhase = state;
869 }
870
871 public boolean hasValueProxies() {
872 return hasValueProxies;
873 }
874
875 public void setHasValueProxies(boolean state) {
876 assert !state : "cannot 'unapply' value proxy removal on graph";
877 hasValueProxies = state;
878 }
879
880 public boolean isAfterExpandLogic() {
881 return isAfterExpandLogic;
882 }
883
884 public void setAfterExpandLogic() {
885 isAfterExpandLogic = true;
886 }
887
888 /**
889 * Determines if {@link ProfilingInfo} is used during construction of this graph.
890 */
891 public boolean useProfilingInfo() {
892 return useProfilingInfo;
893 }
894
895 /**
896 * Returns true if this graph is built without parsing the {@linkplain #method() root method} or
897 * if the root method is annotated by {@link Snippet} or {@link MethodSubstitution}. This is
898 * preferred over querying annotations directly as querying annotations can cause class loading.
899 */
900 public boolean isSubstitution() {
901 return isSubstitution;
902 }
903
904 /**
905 * Gets the profiling info for the {@linkplain #method() root method} of this graph.
906 */
907 public ProfilingInfo getProfilingInfo() {
908 return getProfilingInfo(method());
909 }
910
911 /**
912 * Gets the profiling info for a given method that is or will be part of this graph, taking into
913 * account {@link #useProfilingInfo()}.
914 */
915 public ProfilingInfo getProfilingInfo(ResolvedJavaMethod m) {
916 if (useProfilingInfo && m != null) {
917 return m.getProfilingInfo();
918 } else {
919 return DefaultProfilingInfo.get(TriState.UNKNOWN);
920 }
921 }
922
923 /**
924 * Gets the object for recording assumptions while constructing of this graph.
925 *
926 * @return {@code null} if assumptions cannot be made for this graph
927 */
928 public Assumptions getAssumptions() {
929 return assumptions;
930 }
931
932 /**
933 * Checks that any method referenced from a {@link FrameState} is also in the set of methods
934 * parsed while building this graph.
935 */
936 private boolean checkFrameStatesAgainstInlinedMethods() {
937 for (FrameState fs : getNodes(FrameState.TYPE)) {
938 if (!BytecodeFrame.isPlaceholderBci(fs.bci)) {
939 ResolvedJavaMethod m = fs.code.getMethod();
940 if (!m.equals(rootMethod) && !methods.contains(m)) {
941 SortedSet<String> haystack = new TreeSet<>();
942 if (!methods.contains(rootMethod)) {
943 haystack.add(rootMethod.format("%H.%n(%p)"));
944 }
945 for (ResolvedJavaMethod e : methods) {
946 haystack.add(e.format("%H.%n(%p)"));
947 }
948 throw new AssertionError(String.format("Could not find %s from %s in set(%s)", m.format("%H.%n(%p)"), fs, haystack.stream().collect(Collectors.joining(System.lineSeparator()))));
949 }
950 }
951 }
952 return true;
953 }
954
955 private static EconomicSet<ResolvedJavaField> createFieldSet(EconomicSet<ResolvedJavaField> init) {
956 // Multiple ResolvedJavaField objects can represent the same field so they
957 // need to be compared with equals().
958 if (init != null) {
959 return EconomicSet.create(Equivalence.DEFAULT, init);
960 }
961 return EconomicSet.create(Equivalence.DEFAULT);
962 }
963
964 /**
965 * Gets an unmodifiable view of the methods that were inlined while constructing this graph.
966 */
967 public List<ResolvedJavaMethod> getMethods() {
968 if (methods != null) {
969 assert isSubstitution || checkFrameStatesAgainstInlinedMethods();
970 return Collections.unmodifiableList(methods);
971 }
972 return Collections.emptyList();
973 }
974
975 /**
976 * Records that {@code method} was used to build this graph.
977 */
978 public void recordMethod(ResolvedJavaMethod method) {
979 if (methods != null) {
980 methods.add(method);
981 }
982 }
983
984 /**
985 * Updates the {@linkplain #getMethods() methods} used to build this graph with the methods used
986 * to build another graph.
987 */
988 public void updateMethods(StructuredGraph other) {
989 if (methods != null) {
990 if (other.rootMethod != null) {
991 methods.add(other.rootMethod);
992 }
993 for (ResolvedJavaMethod m : other.methods) {
994 methods.add(m);
995 }
996 }
997 }
998
999 /**
1000 * Gets an unmodifiable view of the fields that were accessed while constructing this graph.
1001 *
1002 * @return {@code null} if no field accesses were recorded
1003 */
1004 public EconomicSet<ResolvedJavaField> getFields() {
1005 return fields;
1006 }
1007
1008 /**
1009 * Records that {@code field} was accessed in this graph.
1010 */
1011 public void recordField(ResolvedJavaField field) {
1012 assert GraalOptions.GeneratePIC.getValue(getOptions());
1013 if (this.fields == null) {
1014 this.fields = createFieldSet(null);
1015 }
1016 fields.add(field);
1017 }
1018
1019 /**
1020 * Updates the {@linkplain #getFields() fields} of this graph with the accessed fields of
1021 * another graph.
1022 */
1023 public void updateFields(StructuredGraph other) {
1024 assert this != other;
1025 assert GraalOptions.GeneratePIC.getValue(getOptions());
1026 if (other.fields != null) {
1027 if (this.fields == null) {
1028 this.fields = createFieldSet(null);
1029 }
1030 this.fields.addAll(other.fields);
1031 }
1032 }
1033
1034 /**
1035 * Gets the input bytecode {@linkplain ResolvedJavaMethod#getCodeSize() size} from which this
1036 * graph is constructed. This ignores how many bytecodes in each constituent method are actually
1037 * parsed (which may be none for methods whose IR is retrieved from a cache or less than the
1038 * full amount for any given method due to profile guided branch pruning).
1039 */
1040 public int getBytecodeSize() {
1041 int res = 0;
1042 if (rootMethod != null) {
1043 res += rootMethod.getCodeSize();
1044 }
1045 if (methods != null) {
1046 for (ResolvedJavaMethod e : methods) {
1047 res += e.getCodeSize();
1048 }
1049 }
1050 return res;
1051 }
1052
1053 @Override
1054 public JavaMethod asJavaMethod() {
1055 return method();
1056 }
1057
1058 public boolean hasUnsafeAccess() {
1059 return hasUnsafeAccess == UnsafeAccessState.HAS_ACCESS;
1060 }
1061
1062 public void markUnsafeAccess() {
1063 if (hasUnsafeAccess == UnsafeAccessState.DISABLED) {
1064 return;
1065 }
1066 hasUnsafeAccess = UnsafeAccessState.HAS_ACCESS;
1067 }
1068
1069 public void disableUnsafeAccessTracking() {
1070 hasUnsafeAccess = UnsafeAccessState.DISABLED;
1071 }
1072
1073 public boolean isUnsafeAccessTrackingEnabled() {
1074 return hasUnsafeAccess != UnsafeAccessState.DISABLED;
1075 }
1076
1077 public SpeculationLog getSpeculationLog() {
1078 return speculationLog;
1079 }
1080
1081 public void clearAllStateAfter() {
1082 for (Node node : getNodes()) {
1083 if (node instanceof StateSplit) {
1084 FrameState stateAfter = ((StateSplit) node).stateAfter();
1085 if (stateAfter != null) {
1086 ((StateSplit) node).setStateAfter(null);
1087 // 2 nodes referencing the same framestate
1088 if (stateAfter.isAlive()) {
1089 GraphUtil.killWithUnusedFloatingInputs(stateAfter);
1090 }
1091 }
1092 }
1093 }
1094 }
1095
1096 public boolean hasVirtualizableAllocation() {
1097 for (Node n : getNodes()) {
1098 if (n instanceof VirtualizableAllocation) {
1099 return true;
1100 }
1101 }
1102 return false;
1103 }
1104
1105 @Override
1106 protected void afterRegister(Node node) {
1107 assert hasValueProxies() || !(node instanceof ValueProxyNode);
1108 if (GraalOptions.TraceInlining.getValue(getOptions())) {
1109 if (node instanceof Invokable) {
1110 ((Invokable) node).updateInliningLogAfterRegister(this);
1111 }
1112 }
1113 }
1114
1115 public NodeSourcePosition getCallerContext() {
1116 return callerContext;
1117 }
1118 }