Source code

001/*
002 * Copyright (c) 2011, 2013, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.virtual.phases.ea;
024
025import java.util.*;
026
027import com.oracle.graal.nodes.*;
028import com.oracle.graal.nodes.calc.*;
029import com.oracle.graal.nodes.java.*;
030import com.oracle.graal.nodes.virtual.*;
031
032public abstract class PartialEscapeBlockState<T extends PartialEscapeBlockState<T>> extends EffectsBlockState<T> {
033
034    private static final ObjectState[] EMPTY_ARRAY = new ObjectState[0];
035
036    private ObjectState[] objectStates;
037
038    private static class RefCount {
039        private int refCount = 1;
040    }
041
042    private RefCount arrayRefCount;
043
044    /**
045     * Final subclass of PartialEscapeBlockState, for performance and to make everything behave
046     * nicely with generics.
047     */
048    public static final class Final extends PartialEscapeBlockState<Final> {
049
050        public Final() {
051        }
052
053        public Final(Final other) {
054            super(other);
055        }
056    }
057
058    protected PartialEscapeBlockState() {
059        objectStates = EMPTY_ARRAY;
060        arrayRefCount = new RefCount();
061    }
062
063    protected PartialEscapeBlockState(PartialEscapeBlockState<T> other) {
064        super(other);
065        adoptAddObjectStates(other);
066    }
067
068    public ObjectState getObjectState(int object) {
069        ObjectState state = objectStates[object];
070        assert state != null;
071        return state;
072    }
073
074    public ObjectState getObjectStateOptional(int object) {
075        return object >= objectStates.length ? null : objectStates[object];
076    }
077
078    public ObjectState getObjectState(VirtualObjectNode object) {
079        ObjectState state = objectStates[object.getObjectId()];
080        assert state != null;
081        return state;
082    }
083
084    public ObjectState getObjectStateOptional(VirtualObjectNode object) {
085        int id = object.getObjectId();
086        return id >= objectStates.length ? null : objectStates[id];
087    }
088
089    private ObjectState[] getObjectStateArrayForModification() {
090        if (arrayRefCount.refCount > 1) {
091            objectStates = objectStates.clone();
092            arrayRefCount = new RefCount();
093        }
094        return objectStates;
095    }
096
097    private ObjectState getObjectStateForModification(int object) {
098        ObjectState[] array = getObjectStateArrayForModification();
099        ObjectState objectState = array[object];
100        if (objectState.copyOnWrite) {
101            array[object] = objectState = objectState.cloneState();
102        }
103        return objectState;
104    }
105
106    public void setEntry(int object, int entryIndex, ValueNode value) {
107        if (objectStates[object].getEntry(entryIndex) != value) {
108            getObjectStateForModification(object).setEntry(entryIndex, value);
109        }
110    }
111
112    public void escape(int object, ValueNode materialized) {
113        getObjectStateForModification(object).escape(materialized);
114    }
115
116    public void addLock(int object, MonitorIdNode monitorId) {
117        getObjectStateForModification(object).addLock(monitorId);
118    }
119
120    public MonitorIdNode removeLock(int object) {
121        return getObjectStateForModification(object).removeLock();
122    }
123
124    public void setEnsureVirtualized(int object, boolean ensureVirtualized) {
125        if (objectStates[object].getEnsureVirtualized() != ensureVirtualized) {
126            getObjectStateForModification(object).setEnsureVirtualized(ensureVirtualized);
127        }
128    }
129
130    public void updateMaterializedValue(int object, ValueNode value) {
131        if (objectStates[object].getMaterializedValue() != value) {
132            getObjectStateForModification(object).updateMaterializedValue(value);
133        }
134    }
135
136    public void materializeBefore(FixedNode fixed, VirtualObjectNode virtual, GraphEffectList materializeEffects) {
137        PartialEscapeClosure.METRIC_MATERIALIZATIONS.increment();
138        List<AllocatedObjectNode> objects = new ArrayList<>(2);
139        List<ValueNode> values = new ArrayList<>(8);
140        List<List<MonitorIdNode>> locks = new ArrayList<>(2);
141        List<ValueNode> otherAllocations = new ArrayList<>(2);
142        List<Boolean> ensureVirtual = new ArrayList<>(2);
143        materializeWithCommit(fixed, virtual, objects, locks, values, ensureVirtual, otherAllocations);
144
145        materializeEffects.add("materializeBefore", (graph, obsoleteNodes) -> {
146            for (ValueNode otherAllocation : otherAllocations) {
147                graph.addWithoutUnique(otherAllocation);
148                if (otherAllocation instanceof FixedWithNextNode) {
149                    graph.addBeforeFixed(fixed, (FixedWithNextNode) otherAllocation);
150                } else {
151                    assert otherAllocation instanceof FloatingNode;
152                }
153            }
154            if (!objects.isEmpty()) {
155                CommitAllocationNode commit;
156                if (fixed.predecessor() instanceof CommitAllocationNode) {
157                    commit = (CommitAllocationNode) fixed.predecessor();
158                } else {
159                    commit = graph.add(new CommitAllocationNode());
160                    graph.addBeforeFixed(fixed, commit);
161                }
162                for (AllocatedObjectNode obj : objects) {
163                    graph.addWithoutUnique(obj);
164                    commit.getVirtualObjects().add(obj.getVirtualObject());
165                    obj.setCommit(commit);
166                }
167                commit.getValues().addAll(values);
168                for (List<MonitorIdNode> monitorIds : locks) {
169                    commit.addLocks(monitorIds);
170                }
171                commit.getEnsureVirtual().addAll(ensureVirtual);
172
173                assert commit.usages().filter(AllocatedObjectNode.class).count() == commit.getUsageCount();
174                List<AllocatedObjectNode> materializedValues = commit.usages().filter(AllocatedObjectNode.class).snapshot();
175                for (int i = 0; i < commit.getValues().size(); i++) {
176                    if (materializedValues.contains(commit.getValues().get(i))) {
177                        commit.getValues().set(i, ((AllocatedObjectNode) commit.getValues().get(i)).getVirtualObject());
178                    }
179                }
180            }
181        });
182    }
183
184    private void materializeWithCommit(FixedNode fixed, VirtualObjectNode virtual, List<AllocatedObjectNode> objects, List<List<MonitorIdNode>> locks, List<ValueNode> values,
185                    List<Boolean> ensureVirtual, List<ValueNode> otherAllocations) {
186        ObjectState obj = getObjectState(virtual);
187
188        ValueNode[] entries = obj.getEntries();
189        ValueNode representation = virtual.getMaterializedRepresentation(fixed, entries, obj.getLocks());
190        escape(virtual.getObjectId(), representation);
191        obj = getObjectState(virtual);
192        PartialEscapeClosure.updateStatesForMaterialized(this, virtual, obj.getMaterializedValue());
193        if (representation instanceof AllocatedObjectNode) {
194            objects.add((AllocatedObjectNode) representation);
195            locks.add(LockState.asList(obj.getLocks()));
196            ensureVirtual.add(obj.getEnsureVirtualized());
197            int pos = values.size();
198            while (values.size() < pos + entries.length) {
199                values.add(null);
200            }
201            for (int i = 0; i < entries.length; i++) {
202                if (entries[i] instanceof VirtualObjectNode) {
203                    VirtualObjectNode entryVirtual = (VirtualObjectNode) entries[i];
204                    ObjectState entryObj = getObjectState(entryVirtual);
205                    if (entryObj.isVirtual()) {
206                        materializeWithCommit(fixed, entryVirtual, objects, locks, values, ensureVirtual, otherAllocations);
207                        entryObj = getObjectState(entryVirtual);
208                    }
209                    values.set(pos + i, entryObj.getMaterializedValue());
210                } else {
211                    values.set(pos + i, entries[i]);
212                }
213            }
214            objectMaterialized(virtual, (AllocatedObjectNode) representation, values.subList(pos, pos + entries.length));
215        } else {
216            VirtualUtil.trace("materialized %s as %s", virtual, representation);
217            otherAllocations.add(representation);
218            assert obj.getLocks() == null;
219        }
220    }
221
222    protected void objectMaterialized(VirtualObjectNode virtual, AllocatedObjectNode representation, List<ValueNode> values) {
223        VirtualUtil.trace("materialized %s as %s with values %s", virtual, representation, values);
224    }
225
226    public void addObject(int virtual, ObjectState state) {
227        ensureSize(virtual)[virtual] = state;
228    }
229
230    private ObjectState[] ensureSize(int objectId) {
231        if (objectStates.length <= objectId) {
232            objectStates = Arrays.copyOf(objectStates, Math.max(objectId * 2, 4));
233            arrayRefCount.refCount--;
234            arrayRefCount = new RefCount();
235            return objectStates;
236        } else {
237            return getObjectStateArrayForModification();
238        }
239    }
240
241    public int getStateCount() {
242        return objectStates.length;
243    }
244
245    @Override
246    public String toString() {
247        return super.toString() + ", Object States: " + Arrays.toString(objectStates);
248    }
249
250    @Override
251    public boolean equivalentTo(T other) {
252        int length = Math.max(objectStates.length, other.getStateCount());
253        for (int i = 0; i < length; i++) {
254            ObjectState left = getObjectStateOptional(i);
255            ObjectState right = other.getObjectStateOptional(i);
256            if (left != right) {
257                if (left == null || right == null) {
258                    return false;
259                }
260                if (!left.equals(right)) {
261                    return false;
262                }
263            }
264        }
265        return true;
266    }
267
268    protected static <K, V> boolean compareMaps(Map<K, V> left, Map<K, V> right) {
269        if (left.size() != right.size()) {
270            return false;
271        }
272        return compareMapsNoSize(left, right);
273    }
274
275    protected static <K, V> boolean compareMapsNoSize(Map<K, V> left, Map<K, V> right) {
276        if (left == right) {
277            return true;
278        }
279        for (Map.Entry<K, V> entry : right.entrySet()) {
280            K key = entry.getKey();
281            V value = entry.getValue();
282            assert value != null;
283            V otherValue = left.get(key);
284            if (otherValue != value && !value.equals(otherValue)) {
285                return false;
286            }
287        }
288        return true;
289    }
290
291    protected static <U, V> void meetMaps(Map<U, V> target, Map<U, V> source) {
292        Iterator<Map.Entry<U, V>> iter = target.entrySet().iterator();
293        while (iter.hasNext()) {
294            Map.Entry<U, V> entry = iter.next();
295            if (source.containsKey(entry.getKey())) {
296                assert source.get(entry.getKey()) == entry.getValue();
297            } else {
298                iter.remove();
299            }
300        }
301    }
302
303    public void resetObjectStates(int size) {
304        objectStates = new ObjectState[size];
305    }
306
307    public static boolean identicalObjectStates(PartialEscapeBlockState<?>[] states) {
308        for (int i = 1; i < states.length; i++) {
309            if (states[0].objectStates != states[i].objectStates) {
310                return false;
311            }
312        }
313        return true;
314    }
315
316    public static boolean identicalObjectStates(PartialEscapeBlockState<?>[] states, int object) {
317        for (int i = 1; i < states.length; i++) {
318            if (states[0].objectStates[object] != states[i].objectStates[object]) {
319                return false;
320            }
321        }
322        return true;
323    }
324
325    public void adoptAddObjectStates(PartialEscapeBlockState<?> other) {
326        if (objectStates != null) {
327            arrayRefCount.refCount--;
328        }
329        objectStates = other.objectStates;
330        arrayRefCount = other.arrayRefCount;
331
332        if (arrayRefCount.refCount == 1) {
333            for (ObjectState state : objectStates) {
334                if (state != null) {
335                    state.share();
336                }
337            }
338        }
339        arrayRefCount.refCount++;
340    }
341}