1 /*
2 * Copyright (c) 2009, 2014, 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.nodes.virtual;
24
25 import static org.graalvm.compiler.nodeinfo.InputType.Association;
26 import static org.graalvm.compiler.nodeinfo.InputType.Extension;
27 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_UNKNOWN;
28 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_UNKNOWN;
29
30 import java.util.ArrayList;
31 import java.util.Arrays;
32 import java.util.HashMap;
33 import java.util.List;
34 import java.util.Map;
35
36 import org.graalvm.compiler.core.common.type.StampFactory;
37 import org.graalvm.compiler.graph.Node;
38 import org.graalvm.compiler.graph.NodeClass;
39 import org.graalvm.compiler.graph.NodeInputList;
40 import org.graalvm.compiler.graph.spi.Simplifiable;
41 import org.graalvm.compiler.graph.spi.SimplifierTool;
42 import org.graalvm.compiler.nodeinfo.NodeInfo;
43 import org.graalvm.compiler.nodeinfo.Verbosity;
44 import org.graalvm.compiler.nodes.FixedWithNextNode;
45 import org.graalvm.compiler.nodes.ValueNode;
46 import org.graalvm.compiler.nodes.java.MonitorIdNode;
47 import org.graalvm.compiler.nodes.spi.Lowerable;
48 import org.graalvm.compiler.nodes.spi.LoweringTool;
49 import org.graalvm.compiler.nodes.spi.VirtualizableAllocation;
50 import org.graalvm.compiler.nodes.spi.VirtualizerTool;
51
52 // @formatter:off
53 @NodeInfo(nameTemplate = "Alloc {i#virtualObjects}",
54 allowedUsageTypes = Extension,
55 cycles = CYCLES_UNKNOWN,
56 cyclesRationale = "We don't know statically how many, and which, allocations are done.",
57 size = SIZE_UNKNOWN,
58 sizeRationale = "We don't know statically how much code for which allocations has to be generated."
59 )
60 // @formatter:on
61 public final class CommitAllocationNode extends FixedWithNextNode implements VirtualizableAllocation, Lowerable, Simplifiable {
62
63 public static final NodeClass<CommitAllocationNode> TYPE = NodeClass.create(CommitAllocationNode.class);
64
65 @Input NodeInputList<VirtualObjectNode> virtualObjects = new NodeInputList<>(this);
66 @Input NodeInputList<ValueNode> values = new NodeInputList<>(this);
67 @Input(Association) NodeInputList<MonitorIdNode> locks = new NodeInputList<>(this);
68 protected ArrayList<Integer> lockIndexes = new ArrayList<>(Arrays.asList(0));
69 protected ArrayList<Boolean> ensureVirtual = new ArrayList<>();
70
71 public CommitAllocationNode() {
72 super(TYPE, StampFactory.forVoid());
73 }
74
75 public List<VirtualObjectNode> getVirtualObjects() {
76 return virtualObjects;
77 }
78
79 public List<ValueNode> getValues() {
80 return values;
81 }
82
83 public List<MonitorIdNode> getLocks(int objIndex) {
84 return locks.subList(lockIndexes.get(objIndex), lockIndexes.get(objIndex + 1));
85 }
86
87 public List<Boolean> getEnsureVirtual() {
88 return ensureVirtual;
89 }
90
91 @Override
92 public boolean verify() {
93 assertTrue(virtualObjects.size() + 1 == lockIndexes.size(), "lockIndexes size doesn't match %s, %s", virtualObjects, lockIndexes);
94 assertTrue(lockIndexes.get(lockIndexes.size() - 1) == locks.size(), "locks size doesn't match %s,%s", lockIndexes, locks);
95 int valueCount = 0;
96 for (VirtualObjectNode virtual : virtualObjects) {
97 valueCount += virtual.entryCount();
98 }
99 assertTrue(values.size() == valueCount, "values size doesn't match");
100 assertTrue(virtualObjects.size() == ensureVirtual.size(), "ensureVirtual size doesn't match");
101 return super.verify();
102 }
103
104 @Override
105 public void lower(LoweringTool tool) {
106 for (int i = 0; i < virtualObjects.size(); i++) {
107 if (ensureVirtual.get(i)) {
108 EnsureVirtualizedNode.ensureVirtualFailure(this, virtualObjects.get(i).stamp());
109 }
110 }
111 tool.getLowerer().lower(this, tool);
112 }
113
114 @Override
115 public void afterClone(Node other) {
116 lockIndexes = new ArrayList<>(lockIndexes);
117 }
118
119 public void addLocks(List<MonitorIdNode> monitorIds) {
120 locks.addAll(monitorIds);
121 lockIndexes.add(locks.size());
122 }
123
124 @Override
125 public void virtualize(VirtualizerTool tool) {
126 int pos = 0;
127 for (int i = 0; i < virtualObjects.size(); i++) {
128 VirtualObjectNode virtualObject = virtualObjects.get(i);
129 int entryCount = virtualObject.entryCount();
130 tool.createVirtualObject(virtualObject, values.subList(pos, pos + entryCount).toArray(new ValueNode[entryCount]), getLocks(i), ensureVirtual.get(i));
131 pos += entryCount;
132 }
133 tool.delete();
134 }
135
136 @Override
137 public Map<Object, Object> getDebugProperties(Map<Object, Object> map) {
138 Map<Object, Object> properties = super.getDebugProperties(map);
139 int valuePos = 0;
140 for (int objIndex = 0; objIndex < virtualObjects.size(); objIndex++) {
141 VirtualObjectNode virtual = virtualObjects.get(objIndex);
142 if (virtual == null) {
143 // Could occur in invalid graphs
144 properties.put("object(" + objIndex + ")", "null");
145 continue;
146 }
147 StringBuilder s = new StringBuilder();
148 s.append(virtual.type().toJavaName(false)).append("[");
149 for (int i = 0; i < virtual.entryCount(); i++) {
150 ValueNode value = values.get(valuePos++);
151 s.append(i == 0 ? "" : ",").append(value == null ? "_" : value.toString(Verbosity.Id));
152 }
153 s.append("]");
154 if (!getLocks(objIndex).isEmpty()) {
155 s.append(" locked(").append(getLocks(objIndex)).append(")");
156 }
157 properties.put("object(" + virtual.toString(Verbosity.Id) + ")", s.toString());
158 }
159 return properties;
160 }
161
162 @Override
163 public void simplify(SimplifierTool tool) {
164 boolean[] used = new boolean[virtualObjects.size()];
165 int usedCount = 0;
166 for (Node usage : usages()) {
167 AllocatedObjectNode addObject = (AllocatedObjectNode) usage;
168 int index = virtualObjects.indexOf(addObject.getVirtualObject());
169 assert !used[index];
170 used[index] = true;
171 usedCount++;
172 }
173 if (usedCount == 0) {
174 List<Node> inputSnapshot = inputs().snapshot();
175 graph().removeFixed(this);
176 for (Node input : inputSnapshot) {
177 tool.removeIfUnused(input);
178 }
179 return;
180 }
181 boolean progress;
182 do {
183 progress = false;
184 int valuePos = 0;
185 for (int objIndex = 0; objIndex < virtualObjects.size(); objIndex++) {
186 VirtualObjectNode virtualObject = virtualObjects.get(objIndex);
187 if (used[objIndex]) {
188 for (int i = 0; i < virtualObject.entryCount(); i++) {
189 int index = virtualObjects.indexOf(values.get(valuePos + i));
190 if (index != -1 && !used[index]) {
191 progress = true;
192 used[index] = true;
193 usedCount++;
194 }
195 }
196 }
197 valuePos += virtualObject.entryCount();
198 }
199
200 } while (progress);
201
202 if (usedCount < virtualObjects.size()) {
203 List<VirtualObjectNode> newVirtualObjects = new ArrayList<>(usedCount);
204 List<MonitorIdNode> newLocks = new ArrayList<>(usedCount);
205 ArrayList<Integer> newLockIndexes = new ArrayList<>(usedCount + 1);
206 ArrayList<Boolean> newEnsureVirtual = new ArrayList<>(usedCount);
207 newLockIndexes.add(0);
208 List<ValueNode> newValues = new ArrayList<>();
209 int valuePos = 0;
210 for (int objIndex = 0; objIndex < virtualObjects.size(); objIndex++) {
211 VirtualObjectNode virtualObject = virtualObjects.get(objIndex);
212 if (used[objIndex]) {
213 newVirtualObjects.add(virtualObject);
214 newLocks.addAll(getLocks(objIndex));
215 newLockIndexes.add(newLocks.size());
216 newValues.addAll(values.subList(valuePos, valuePos + virtualObject.entryCount()));
217 newEnsureVirtual.add(ensureVirtual.get(objIndex));
218 }
219 valuePos += virtualObject.entryCount();
220 }
221 virtualObjects.clear();
222 virtualObjects.addAll(newVirtualObjects);
223 locks.clear();
224 locks.addAll(newLocks);
225 values.clear();
226 values.addAll(newValues);
227 lockIndexes = newLockIndexes;
228 ensureVirtual = newEnsureVirtual;
229 }
230 }
231
232 /**
233 * For all the virtual object nodes that depends on commit allocation, this method maps the node
234 * with its values. For example, a commit allocation could depend on a {@link VirtualArrayNode}
235 * with many {@link ValueNode}s. The map will contain the corresponding {@link VirtualArrayNode}
236 * as a key with the array of {@link ValueNode}s.
237 */
238 public HashMap<VirtualObjectNode, Object[]> getVirtualObjectsArrays() {
239 HashMap<VirtualObjectNode, Object[]> arrayValues = new HashMap<>();
240 int pos = 0;
241 for (int i = 0; i < virtualObjects.size(); i++) {
242 VirtualObjectNode virtualObject = virtualObjects.get(i);
243 int entryCount = virtualObject.entryCount();
244 ValueNode[] array = values.subList(pos, pos + entryCount).toArray(new ValueNode[entryCount]);
245 arrayValues.put(virtualObject, array);
246 pos += entryCount;
247 }
248 return arrayValues;
249 }
250
251 }