1 /*
2 * Copyright (c) 2015, 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.phases.common.instrumentation;
24
25 import java.util.HashMap;
26
27 import org.graalvm.compiler.graph.Node;
28 import org.graalvm.compiler.graph.NodeFlood;
29 import org.graalvm.compiler.nodes.AbstractEndNode;
30 import org.graalvm.compiler.nodes.FixedNode;
31 import org.graalvm.compiler.nodes.FixedWithNextNode;
32 import org.graalvm.compiler.nodes.LoopEndNode;
33 import org.graalvm.compiler.nodes.StructuredGraph;
34 import org.graalvm.compiler.nodes.ValueNode;
35 import org.graalvm.compiler.nodes.debug.instrumentation.InstrumentationNode;
36 import org.graalvm.compiler.nodes.debug.instrumentation.MonitorProxyNode;
37 import org.graalvm.compiler.nodes.java.MonitorIdNode;
38 import org.graalvm.compiler.nodes.virtual.AllocatedObjectNode;
39 import org.graalvm.compiler.nodes.virtual.CommitAllocationNode;
40 import org.graalvm.compiler.nodes.virtual.VirtualObjectNode;
41 import org.graalvm.compiler.phases.Phase;
42
43 /**
44 * The {@code HighTierReconcileInstrumentationPhase} reconciles the InstrumentationNodes according
45 * to the optimizations at the high tier, e.g., the partial escape analysis. It clones the
46 * InstrumentationNode and inserts at the CommitAllocationNode that includes the allocation/lock
47 * targeted by the InstrumentationNode.
48 */
49 public class HighTierReconcileInstrumentationPhase extends Phase {
50
51 @Override
52 public boolean checkContract() {
53 return false;
54 }
55
56 @Override
57 protected void run(StructuredGraph graph) {
58 // iterate through all CommitAllocationNodes, and clone the InstrumentationNodes targeting
59 // allocation/lock held by this CommitAllocationNode
60 for (CommitAllocationNode commit : graph.getNodes().filter(CommitAllocationNode.class)) {
61 InstrumentationAggregation aggr = new InstrumentationAggregation(graph, commit);
62 // iterate through all VirtualObjectNodes held by the CommitAllocationNode, clone if any
63 // InstrumentationNode targets one of these VirtualObjectNodes
64 for (int objIndex = 0; objIndex < commit.getVirtualObjects().size(); objIndex++) {
65 VirtualObjectNode virtual = commit.getVirtualObjects().get(objIndex);
66 for (InstrumentationNode instrumentationNode : graph.getNodes().filter(InstrumentationNode.class)) {
67 if (isCFGAccessible(instrumentationNode, commit) && instrumentationNode.getTarget() == virtual) {
68 // clone InstrumentationNode when the CommitAllocationNode is accessible
69 // from the InstrumentationNode, and the InstrumentationNode's target
70 // matches the given VirtualObjectNode
71 aggr.insertClone(instrumentationNode, getAllocatedObject(graph, commit, virtual));
72 }
73 }
74 }
75 // iterate through all MonitorIdNodes held by the CommitAllocationNode, clone if any
76 // InstrumentationNode targets one of these MonitorIdNodes (via MonitorProxyNode)
77 for (int objIndex = 0; objIndex < commit.getVirtualObjects().size(); objIndex++) {
78 VirtualObjectNode virtual = commit.getVirtualObjects().get(objIndex);
79 for (MonitorIdNode monitorId : commit.getLocks(objIndex)) {
80 for (InstrumentationNode instrumentationNode : graph.getNodes().filter(InstrumentationNode.class)) {
81 if (isCFGAccessible(instrumentationNode, commit) && instrumentationNode.getTarget() instanceof MonitorProxyNode &&
82 ((MonitorProxyNode) instrumentationNode.getTarget()).getMonitorId() == monitorId) {
83 // clone InstrumentationNode when the CommitAllocationNode is accessible
84 // from the InstrumentationNode, and the InstrumentationNode's target is
85 // a MonitorProxyNode that matches the MonitorIdNode
86 aggr.insertClone(instrumentationNode, graph.addWithoutUnique(new MonitorProxyNode(getAllocatedObject(graph, commit, virtual), monitorId)));
87 }
88 }
89 }
90 }
91 }
92 // remove InstrumentationNodes that still target virtual nodes
93 for (InstrumentationNode instrumentationNode : graph.getNodes().filter(InstrumentationNode.class)) {
94 ValueNode target = instrumentationNode.getTarget();
95 if (target instanceof VirtualObjectNode) {
96 graph.removeFixed(instrumentationNode);
97 } else if (target instanceof MonitorProxyNode) {
98 MonitorProxyNode proxy = (MonitorProxyNode) target;
99 if (proxy.object() == null) {
100 graph.removeFixed(instrumentationNode);
101 }
102 }
103 }
104 }
105
106 /**
107 * The {@code InstrumentationAggregation} maintains an inserting location after
108 * CommitAllocationNode such that the cloned InstrumentationNodes would appear in the order of
109 * the allocations.
110 */
111 class InstrumentationAggregation {
112
113 private StructuredGraph graph;
114 private CommitAllocationNode commit;
115 private FixedWithNextNode insertAfter;
116
117 InstrumentationAggregation(StructuredGraph graph, CommitAllocationNode commit) {
118 this.graph = graph;
119 this.commit = commit;
120 this.insertAfter = commit;
121 }
122
123 void insertClone(InstrumentationNode instrumentationNode, ValueNode newTarget) {
124 InstrumentationNode clone = (InstrumentationNode) instrumentationNode.copyWithInputs();
125 // update the clone instrumentation node with the new target
126 clone.replaceFirstInput(clone.getTarget(), newTarget);
127 // update weak dependencies of the clone instrumentation node where the dependency
128 // is also a VirtualObjectNode. This is common when one allocation in the
129 // CommitAllocationNode depends on another allocation.
130 for (ValueNode input : clone.getWeakDependencies()) {
131 if ((input instanceof VirtualObjectNode) && (commit.getVirtualObjects().contains(input))) {
132 clone.replaceFirstInput(input, getAllocatedObject(graph, commit, (VirtualObjectNode) input));
133 }
134 }
135 graph.addAfterFixed(insertAfter, clone);
136 insertAfter = clone;
137 }
138
139 }
140
141 private final HashMap<FixedWithNextNode, NodeFlood> cachedNodeFloods = new HashMap<>();
142
143 /**
144 * @return true if there is a control flow path between {@code from} and {@code to}.
145 */
146 private boolean isCFGAccessible(FixedWithNextNode from, FixedNode to) {
147 NodeFlood flood = cachedNodeFloods.get(from);
148 if (flood == null) {
149 flood = from.graph().createNodeFlood();
150 flood.add(from);
151 for (Node current : flood) {
152 if (current instanceof LoopEndNode) {
153 continue;
154 } else if (current instanceof AbstractEndNode) {
155 flood.add(((AbstractEndNode) current).merge());
156 } else {
157 flood.addAll(current.successors());
158 }
159 }
160 cachedNodeFloods.put(from, flood);
161 }
162 return flood.isMarked(to);
163 }
164
165 /**
166 * Get/generate the AllocatedObjectNode for the given VirtualObjectNode in the given
167 * CommitAllocationNode.
168 */
169 private static AllocatedObjectNode getAllocatedObject(StructuredGraph graph, CommitAllocationNode commit, VirtualObjectNode virtual) {
170 // search if the AllocatedObjectNode already exists
171 for (AllocatedObjectNode allocatedObject : graph.getNodes().filter(AllocatedObjectNode.class)) {
172 if (allocatedObject.getCommit() == commit && allocatedObject.getVirtualObject() == virtual) {
173 return allocatedObject;
174 }
175 }
176 // create one if the AllocatedObjectNode does not exist
177 AllocatedObjectNode allocatedObject = graph.addWithoutUnique(new AllocatedObjectNode(virtual));
178 allocatedObject.setCommit(commit);
179 return allocatedObject;
180 }
181
182 }