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