1 /*
2 * Copyright (c) 2011, 2017, 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.virtual.phases.ea;
24
25 import java.util.ArrayList;
26 import java.util.Arrays;
27 import java.util.Iterator;
28 import java.util.List;
29 import java.util.Map;
30
31 import org.graalvm.compiler.debug.DebugContext;
32 import org.graalvm.compiler.graph.Node;
33 import org.graalvm.compiler.nodes.FixedNode;
34 import org.graalvm.compiler.nodes.FixedWithNextNode;
35 import org.graalvm.compiler.nodes.StructuredGraph;
36 import org.graalvm.compiler.nodes.ValueNode;
37 import org.graalvm.compiler.nodes.calc.FloatingNode;
38 import org.graalvm.compiler.nodes.java.MonitorIdNode;
39 import org.graalvm.compiler.nodes.virtual.AllocatedObjectNode;
40 import org.graalvm.compiler.nodes.virtual.CommitAllocationNode;
41 import org.graalvm.compiler.nodes.virtual.LockState;
42 import org.graalvm.compiler.nodes.virtual.VirtualObjectNode;
43 import org.graalvm.compiler.options.OptionValues;
44 import org.graalvm.compiler.virtual.phases.ea.EffectList.Effect;
45
46 public abstract class PartialEscapeBlockState<T extends PartialEscapeBlockState<T>> extends EffectsBlockState<T> {
47
48 private static final ObjectState[] EMPTY_ARRAY = new ObjectState[0];
49
50 /**
51 * This array contains the state of all virtual objects, indexed by
52 * {@link VirtualObjectNode#getObjectId()}. Entries in this array may be null if the
53 * corresponding virtual object is not alive or reachable currently.
54 */
55 private ObjectState[] objectStates;
56
57 private static class RefCount {
58 private int refCount = 1;
59 }
60
61 /**
62 * Usage count for the objectStates array, to avoid unneessary copying.
63 */
64 private RefCount arrayRefCount;
65
66 private final OptionValues options;
67 private final DebugContext debug;
68
69 /**
70 * Final subclass of PartialEscapeBlockState, for performance and to make everything behave
71 * nicely with generics.
72 */
73 public static final class Final extends PartialEscapeBlockState<Final> {
74
75 public Final(OptionValues options, DebugContext debug) {
76 super(options, debug);
77 }
78
79 public Final(Final other) {
80 super(other);
81 }
82 }
83
84 protected PartialEscapeBlockState(OptionValues options, DebugContext debug) {
85 objectStates = EMPTY_ARRAY;
86 arrayRefCount = new RefCount();
87 this.options = options;
88 this.debug = debug;
89 }
90
91 protected PartialEscapeBlockState(PartialEscapeBlockState<T> other) {
92 super(other);
93 adoptAddObjectStates(other);
94 options = other.options;
95 debug = other.debug;
96 }
97
98 public ObjectState getObjectState(int object) {
99 ObjectState state = objectStates[object];
100 assert state != null;
101 return state;
102 }
103
104 public ObjectState getObjectStateOptional(int object) {
105 return object >= objectStates.length ? null : objectStates[object];
106 }
107
108 /**
109 * Asserts that the given virtual object is available/reachable in the current state.
110 */
111 public ObjectState getObjectState(VirtualObjectNode object) {
112 ObjectState state = objectStates[object.getObjectId()];
113 assert state != null;
114 return state;
115 }
116
117 public ObjectState getObjectStateOptional(VirtualObjectNode object) {
118 int id = object.getObjectId();
119 return id >= objectStates.length ? null : objectStates[id];
120 }
121
122 private ObjectState[] getObjectStateArrayForModification() {
123 if (arrayRefCount.refCount > 1) {
124 objectStates = objectStates.clone();
125 arrayRefCount.refCount--;
126 arrayRefCount = new RefCount();
127 }
128 return objectStates;
129 }
130
131 private ObjectState getObjectStateForModification(int object) {
132 ObjectState[] array = getObjectStateArrayForModification();
133 ObjectState objectState = array[object];
134 if (objectState.copyOnWrite) {
135 array[object] = objectState = objectState.cloneState();
136 }
137 return objectState;
138 }
139
140 public void setEntry(int object, int entryIndex, ValueNode value) {
141 if (objectStates[object].getEntry(entryIndex) != value) {
142 getObjectStateForModification(object).setEntry(entryIndex, value);
143 }
144 }
145
146 public void escape(int object, ValueNode materialized) {
147 getObjectStateForModification(object).escape(materialized);
148 }
149
150 public void addLock(int object, MonitorIdNode monitorId) {
151 getObjectStateForModification(object).addLock(monitorId);
152 }
153
154 public MonitorIdNode removeLock(int object) {
155 return getObjectStateForModification(object).removeLock();
156 }
157
158 public void setEnsureVirtualized(int object, boolean ensureVirtualized) {
159 if (objectStates[object].getEnsureVirtualized() != ensureVirtualized) {
160 getObjectStateForModification(object).setEnsureVirtualized(ensureVirtualized);
161 }
162 }
163
164 public void updateMaterializedValue(int object, ValueNode value) {
165 if (objectStates[object].getMaterializedValue() != value) {
166 getObjectStateForModification(object).updateMaterializedValue(value);
167 }
168 }
169
170 /**
171 * Materializes the given virtual object and produces the necessary effects in the effects list.
172 * This transitively also materializes all other virtual objects that are reachable from the
173 * entries.
174 */
175 public void materializeBefore(FixedNode fixed, VirtualObjectNode virtual, GraphEffectList materializeEffects) {
176 PartialEscapeClosure.COUNTER_MATERIALIZATIONS.increment(fixed.getDebug());
177 List<AllocatedObjectNode> objects = new ArrayList<>(2);
178 List<ValueNode> values = new ArrayList<>(8);
179 List<List<MonitorIdNode>> locks = new ArrayList<>();
180 List<ValueNode> otherAllocations = new ArrayList<>(2);
181 List<Boolean> ensureVirtual = new ArrayList<>(2);
182 materializeWithCommit(fixed, virtual, objects, locks, values, ensureVirtual, otherAllocations);
183
184 materializeEffects.addVirtualizationDelta(-(objects.size() + otherAllocations.size()));
185 materializeEffects.add("materializeBefore", new Effect() {
186 @Override
187 public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) {
188 for (ValueNode alloc : otherAllocations) {
189 ValueNode otherAllocation = graph.addOrUniqueWithInputs(alloc);
190 if (otherAllocation instanceof FixedWithNextNode) {
191 graph.addBeforeFixed(fixed, (FixedWithNextNode) otherAllocation);
192 } else {
193 assert otherAllocation instanceof FloatingNode;
194 }
195 }
196 if (!objects.isEmpty()) {
197 CommitAllocationNode commit;
198 if (fixed.predecessor() instanceof CommitAllocationNode) {
199 commit = (CommitAllocationNode) fixed.predecessor();
200 } else {
201 commit = graph.add(new CommitAllocationNode());
202 graph.addBeforeFixed(fixed, commit);
203 }
204 for (AllocatedObjectNode obj : objects) {
205 graph.addWithoutUnique(obj);
206 commit.getVirtualObjects().add(obj.getVirtualObject());
207 obj.setCommit(commit);
208 }
209 for (ValueNode value : values) {
210 commit.getValues().add(graph.addOrUniqueWithInputs(value));
211 }
212 for (List<MonitorIdNode> monitorIds : locks) {
213 commit.addLocks(monitorIds);
214 }
215 commit.getEnsureVirtual().addAll(ensureVirtual);
216
217 assert commit.usages().filter(AllocatedObjectNode.class).count() == commit.getUsageCount();
218 List<AllocatedObjectNode> materializedValues = commit.usages().filter(AllocatedObjectNode.class).snapshot();
219 for (int i = 0; i < commit.getValues().size(); i++) {
220 if (materializedValues.contains(commit.getValues().get(i))) {
221 commit.getValues().set(i, ((AllocatedObjectNode) commit.getValues().get(i)).getVirtualObject());
222 }
223 }
224 }
225 }
226 });
227 }
228
229 private void materializeWithCommit(FixedNode fixed, VirtualObjectNode virtual, List<AllocatedObjectNode> objects, List<List<MonitorIdNode>> locks, List<ValueNode> values,
230 List<Boolean> ensureVirtual, List<ValueNode> otherAllocations) {
231 ObjectState obj = getObjectState(virtual);
232
233 ValueNode[] entries = obj.getEntries();
234 ValueNode representation = virtual.getMaterializedRepresentation(fixed, entries, obj.getLocks());
235 escape(virtual.getObjectId(), representation);
236 obj = getObjectState(virtual);
237 PartialEscapeClosure.updateStatesForMaterialized(this, virtual, obj.getMaterializedValue());
238 if (representation instanceof AllocatedObjectNode) {
239 objects.add((AllocatedObjectNode) representation);
240 locks.add(LockState.asList(obj.getLocks()));
241 ensureVirtual.add(obj.getEnsureVirtualized());
242 int pos = values.size();
243 while (values.size() < pos + entries.length) {
244 values.add(null);
245 }
246 for (int i = 0; i < entries.length; i++) {
247 if (entries[i] instanceof VirtualObjectNode) {
248 VirtualObjectNode entryVirtual = (VirtualObjectNode) entries[i];
249 ObjectState entryObj = getObjectState(entryVirtual);
250 if (entryObj.isVirtual()) {
251 materializeWithCommit(fixed, entryVirtual, objects, locks, values, ensureVirtual, otherAllocations);
252 entryObj = getObjectState(entryVirtual);
253 }
254 values.set(pos + i, entryObj.getMaterializedValue());
255 } else {
256 values.set(pos + i, entries[i]);
257 }
258 }
259 objectMaterialized(virtual, (AllocatedObjectNode) representation, values.subList(pos, pos + entries.length));
260 } else {
261 VirtualUtil.trace(options, debug, "materialized %s as %s", virtual, representation);
262 otherAllocations.add(representation);
263 assert obj.getLocks() == null;
264 }
265 }
266
267 protected void objectMaterialized(VirtualObjectNode virtual, AllocatedObjectNode representation, List<ValueNode> values) {
268 VirtualUtil.trace(options, debug, "materialized %s as %s with values %s", virtual, representation, values);
269 }
270
271 public void addObject(int virtual, ObjectState state) {
272 ensureSize(virtual)[virtual] = state;
273 }
274
275 private ObjectState[] ensureSize(int objectId) {
276 if (objectStates.length <= objectId) {
277 objectStates = Arrays.copyOf(objectStates, Math.max(objectId * 2, 4));
278 arrayRefCount.refCount--;
279 arrayRefCount = new RefCount();
280 return objectStates;
281 } else {
282 return getObjectStateArrayForModification();
283 }
284 }
285
286 public int getStateCount() {
287 return objectStates.length;
288 }
289
290 @Override
291 public String toString() {
292 return super.toString() + ", Object States: " + Arrays.toString(objectStates);
293 }
294
295 @Override
296 public boolean equivalentTo(T other) {
297 int length = Math.max(objectStates.length, other.getStateCount());
298 for (int i = 0; i < length; i++) {
299 ObjectState left = getObjectStateOptional(i);
300 ObjectState right = other.getObjectStateOptional(i);
301 if (left != right) {
302 if (left == null || right == null) {
303 return false;
304 }
305 if (!left.equals(right)) {
306 return false;
307 }
308 }
309 }
310 return true;
311 }
312
313 protected static <K, V> boolean compareMaps(Map<K, V> left, Map<K, V> right) {
314 if (left.size() != right.size()) {
315 return false;
316 }
317 return compareMapsNoSize(left, right);
318 }
319
320 protected static <K, V> boolean compareMapsNoSize(Map<K, V> left, Map<K, V> right) {
321 if (left == right) {
322 return true;
323 }
324 for (Map.Entry<K, V> entry : right.entrySet()) {
325 K key = entry.getKey();
326 V value = entry.getValue();
327 assert value != null;
328 V otherValue = left.get(key);
329 if (otherValue != value && !value.equals(otherValue)) {
330 return false;
331 }
332 }
333 return true;
334 }
335
336 protected static <U, V> void meetMaps(Map<U, V> target, Map<U, V> source) {
337 Iterator<Map.Entry<U, V>> iter = target.entrySet().iterator();
338 while (iter.hasNext()) {
339 Map.Entry<U, V> entry = iter.next();
340 if (source.containsKey(entry.getKey())) {
341 assert source.get(entry.getKey()) == entry.getValue();
342 } else {
343 iter.remove();
344 }
345 }
346 }
347
348 public void resetObjectStates(int size) {
349 objectStates = new ObjectState[size];
350 }
351
352 public static boolean identicalObjectStates(PartialEscapeBlockState<?>[] states) {
353 for (int i = 1; i < states.length; i++) {
354 if (states[0].objectStates != states[i].objectStates) {
355 return false;
356 }
357 }
358 return true;
359 }
360
361 public static boolean identicalObjectStates(PartialEscapeBlockState<?>[] states, int object) {
362 for (int i = 1; i < states.length; i++) {
363 if (states[0].objectStates[object] != states[i].objectStates[object]) {
364 return false;
365 }
366 }
367 return true;
368 }
369
370 public void adoptAddObjectStates(PartialEscapeBlockState<?> other) {
371 if (objectStates != null) {
372 arrayRefCount.refCount--;
373 }
374 objectStates = other.objectStates;
375 arrayRefCount = other.arrayRefCount;
376
377 if (arrayRefCount.refCount == 1) {
378 for (ObjectState state : objectStates) {
379 if (state != null) {
380 state.share();
381 }
382 }
383 }
384 arrayRefCount.refCount++;
385 }
386 }