Source code

001/*
002 * Copyright (c) 2011, 2015, 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 static com.oracle.graal.nodes.NamedLocationIdentity.*;
026
027import java.util.*;
028
029import jdk.internal.jvmci.meta.*;
030
031import com.oracle.graal.compiler.common.cfg.*;
032import com.oracle.graal.graph.*;
033import com.oracle.graal.nodes.*;
034import com.oracle.graal.nodes.cfg.*;
035import com.oracle.graal.nodes.extended.*;
036import com.oracle.graal.nodes.java.*;
037import com.oracle.graal.nodes.memory.*;
038import com.oracle.graal.nodes.type.*;
039import com.oracle.graal.nodes.util.*;
040import com.oracle.graal.nodes.virtual.*;
041import com.oracle.graal.phases.schedule.*;
042import com.oracle.graal.virtual.phases.ea.PEReadEliminationBlockState.ReadCacheEntry;
043
044public class PEReadEliminationClosure extends PartialEscapeClosure<PEReadEliminationBlockState> {
045
046    private static final EnumMap<Kind, LocationIdentity> UNBOX_LOCATIONS;
047    static {
048        UNBOX_LOCATIONS = new EnumMap<>(Kind.class);
049        for (Kind kind : Kind.values()) {
050            UNBOX_LOCATIONS.put(kind, NamedLocationIdentity.immutable("PEA unbox " + kind.getJavaName()));
051        }
052    }
053
054    public PEReadEliminationClosure(SchedulePhase schedule, MetaAccessProvider metaAccess, ConstantReflectionProvider constantReflection) {
055        super(schedule, metaAccess, constantReflection);
056    }
057
058    @Override
059    protected PEReadEliminationBlockState getInitialState() {
060        return new PEReadEliminationBlockState();
061    }
062
063    @Override
064    protected boolean processNode(Node node, PEReadEliminationBlockState state, GraphEffectList effects, FixedWithNextNode lastFixedNode) {
065        if (super.processNode(node, state, effects, lastFixedNode)) {
066            return true;
067        }
068
069        if (node instanceof LoadFieldNode) {
070            return processLoadField((LoadFieldNode) node, state, effects);
071        } else if (node instanceof StoreFieldNode) {
072            return processStoreField((StoreFieldNode) node, state, effects);
073        } else if (node instanceof LoadIndexedNode) {
074            return processLoadIndexed((LoadIndexedNode) node, state, effects);
075        } else if (node instanceof StoreIndexedNode) {
076            return processStoreIndexed((StoreIndexedNode) node, state, effects);
077        } else if (node instanceof ArrayLengthNode) {
078            return processArrayLength((ArrayLengthNode) node, state, effects);
079        } else if (node instanceof UnboxNode) {
080            return processUnbox((UnboxNode) node, state, effects);
081        } else if (node instanceof UnsafeLoadNode) {
082            return processUnsafeLoad((UnsafeLoadNode) node, state, effects);
083        } else if (node instanceof UnsafeStoreNode) {
084            return processUnsafeStore((UnsafeStoreNode) node, state, effects);
085        } else if (node instanceof MemoryCheckpoint.Single) {
086            METRIC_MEMORYCHECKPOINT.increment();
087            LocationIdentity identity = ((MemoryCheckpoint.Single) node).getLocationIdentity();
088            processIdentity(state, identity);
089        } else if (node instanceof MemoryCheckpoint.Multi) {
090            METRIC_MEMORYCHECKPOINT.increment();
091            for (LocationIdentity identity : ((MemoryCheckpoint.Multi) node).getLocationIdentities()) {
092                processIdentity(state, identity);
093            }
094        }
095
096        return false;
097    }
098
099    private boolean processStore(FixedNode store, ValueNode object, LocationIdentity identity, int index, ValueNode value, PEReadEliminationBlockState state, GraphEffectList effects) {
100        ValueNode unproxiedObject = GraphUtil.unproxify(object);
101        ValueNode cachedValue = state.getReadCache(object, identity, index, this);
102
103        ValueNode finalValue = getScalarAlias(value);
104        boolean result = false;
105        if (GraphUtil.unproxify(finalValue) == GraphUtil.unproxify(cachedValue)) {
106            effects.deleteNode(store);
107            result = true;
108        }
109        state.killReadCache(identity, index);
110        state.addReadCache(unproxiedObject, identity, index, finalValue, this);
111        return result;
112    }
113
114    private boolean processLoad(FixedNode load, ValueNode object, LocationIdentity identity, int index, PEReadEliminationBlockState state, GraphEffectList effects) {
115        ValueNode unproxiedObject = GraphUtil.unproxify(object);
116        ValueNode cachedValue = state.getReadCache(unproxiedObject, identity, index, this);
117        if (cachedValue != null) {
118            effects.replaceAtUsages(load, cachedValue);
119            addScalarAlias(load, cachedValue);
120            return true;
121        } else {
122            state.addReadCache(unproxiedObject, identity, index, load, this);
123            return false;
124        }
125    }
126
127    private boolean processUnsafeLoad(UnsafeLoadNode load, PEReadEliminationBlockState state, GraphEffectList effects) {
128        if (load.offset().isConstant()) {
129            ResolvedJavaType type = StampTool.typeOrNull(load.object());
130            if (type != null && type.isArray()) {
131                long offset = load.offset().asJavaConstant().asLong();
132                int index = VirtualArrayNode.entryIndexForOffset(offset, load.accessKind(), type.getComponentType(), Integer.MAX_VALUE);
133                ValueNode object = GraphUtil.unproxify(load.object());
134                LocationIdentity location = NamedLocationIdentity.getArrayLocation(type.getComponentType().getKind());
135                ValueNode cachedValue = state.getReadCache(object, location, index, this);
136                if (cachedValue != null && load.stamp().isCompatible(cachedValue.stamp())) {
137                    effects.replaceAtUsages(load, cachedValue);
138                    addScalarAlias(load, cachedValue);
139                    return true;
140                } else {
141                    state.addReadCache(object, location, index, load, this);
142                }
143            }
144        }
145        return false;
146    }
147
148    private boolean processUnsafeStore(UnsafeStoreNode store, PEReadEliminationBlockState state, GraphEffectList effects) {
149        ResolvedJavaType type = StampTool.typeOrNull(store.object());
150        if (type != null && type.isArray()) {
151            LocationIdentity location = NamedLocationIdentity.getArrayLocation(type.getComponentType().getKind());
152            if (store.offset().isConstant()) {
153                long offset = store.offset().asJavaConstant().asLong();
154                int index = VirtualArrayNode.entryIndexForOffset(offset, store.accessKind(), type.getComponentType(), Integer.MAX_VALUE);
155                return processStore(store, store.object(), location, index, store.value(), state, effects);
156            } else {
157                processIdentity(state, location);
158            }
159        } else {
160            state.killReadCache();
161        }
162        return false;
163    }
164
165    private boolean processArrayLength(ArrayLengthNode length, PEReadEliminationBlockState state, GraphEffectList effects) {
166        return processLoad(length, length.array(), ARRAY_LENGTH_LOCATION, -1, state, effects);
167    }
168
169    private boolean processStoreField(StoreFieldNode store, PEReadEliminationBlockState state, GraphEffectList effects) {
170        if (store.isVolatile()) {
171            state.killReadCache();
172            return false;
173        }
174        return processStore(store, store.object(), store.field().getLocationIdentity(), -1, store.value(), state, effects);
175    }
176
177    private boolean processLoadField(LoadFieldNode load, PEReadEliminationBlockState state, GraphEffectList effects) {
178        if (load.isVolatile()) {
179            state.killReadCache();
180            return false;
181        }
182        return processLoad(load, load.object(), load.field().getLocationIdentity(), -1, state, effects);
183    }
184
185    private boolean processStoreIndexed(StoreIndexedNode store, PEReadEliminationBlockState state, GraphEffectList effects) {
186        LocationIdentity arrayLocation = NamedLocationIdentity.getArrayLocation(store.elementKind());
187        if (store.index().isConstant()) {
188            int index = ((JavaConstant) store.index().asConstant()).asInt();
189            return processStore(store, store.array(), arrayLocation, index, store.value(), state, effects);
190        } else {
191            state.killReadCache(arrayLocation, -1);
192        }
193        return false;
194    }
195
196    private boolean processLoadIndexed(LoadIndexedNode load, PEReadEliminationBlockState state, GraphEffectList effects) {
197        if (load.index().isConstant()) {
198            int index = ((JavaConstant) load.index().asConstant()).asInt();
199            LocationIdentity arrayLocation = NamedLocationIdentity.getArrayLocation(load.elementKind());
200            return processLoad(load, load.array(), arrayLocation, index, state, effects);
201        }
202        return false;
203    }
204
205    private boolean processUnbox(UnboxNode unbox, PEReadEliminationBlockState state, GraphEffectList effects) {
206        return processLoad(unbox, unbox.getValue(), UNBOX_LOCATIONS.get(unbox.getBoxingKind()), -1, state, effects);
207    }
208
209    private static void processIdentity(PEReadEliminationBlockState state, LocationIdentity identity) {
210        if (identity.isAny()) {
211            state.killReadCache();
212        } else {
213            state.killReadCache(identity, -1);
214        }
215    }
216
217    @Override
218    protected void processInitialLoopState(Loop<Block> loop, PEReadEliminationBlockState initialState) {
219        super.processInitialLoopState(loop, initialState);
220
221        for (PhiNode phi : ((LoopBeginNode) loop.getHeader().getBeginNode()).phis()) {
222            ValueNode firstValue = phi.valueAt(0);
223            if (firstValue != null) {
224                firstValue = GraphUtil.unproxify(firstValue);
225                for (Map.Entry<ReadCacheEntry, ValueNode> entry : new ArrayList<>(initialState.getReadCache().entrySet())) {
226                    if (entry.getKey().object == firstValue) {
227                        initialState.addReadCache(phi, entry.getKey().identity, entry.getKey().index, entry.getValue(), this);
228                    }
229                }
230            }
231        }
232    }
233
234    @Override
235    protected void processLoopExit(LoopExitNode exitNode, PEReadEliminationBlockState initialState, PEReadEliminationBlockState exitState, GraphEffectList effects) {
236        super.processLoopExit(exitNode, initialState, exitState, effects);
237
238        if (exitNode.graph().hasValueProxies()) {
239            for (Map.Entry<ReadCacheEntry, ValueNode> entry : exitState.getReadCache().entrySet()) {
240                if (initialState.getReadCache().get(entry.getKey()) != entry.getValue()) {
241                    ValueNode value = exitState.getReadCache(entry.getKey().object, entry.getKey().identity, entry.getKey().index, this);
242                    assert value != null : "Got null from read cache, entry's value:" + entry.getValue();
243                    if (!(value instanceof ProxyNode) || ((ProxyNode) value).proxyPoint() != exitNode) {
244                        ProxyNode proxy = new ValueProxyNode(value, exitNode);
245                        effects.addFloatingNode(proxy, "readCacheProxy");
246                        entry.setValue(proxy);
247                    }
248                }
249            }
250        }
251    }
252
253    @Override
254    protected PEReadEliminationBlockState cloneState(PEReadEliminationBlockState other) {
255        return new PEReadEliminationBlockState(other);
256    }
257
258    @Override
259    protected MergeProcessor createMergeProcessor(Block merge) {
260        return new ReadEliminationMergeProcessor(merge);
261    }
262
263    private class ReadEliminationMergeProcessor extends MergeProcessor {
264
265        public ReadEliminationMergeProcessor(Block mergeBlock) {
266            super(mergeBlock);
267        }
268
269        @Override
270        protected void merge(List<PEReadEliminationBlockState> states) {
271            super.merge(states);
272
273            mergeReadCache(states);
274        }
275
276        private void mergeReadCache(List<PEReadEliminationBlockState> states) {
277            for (Map.Entry<ReadCacheEntry, ValueNode> entry : states.get(0).readCache.entrySet()) {
278                ReadCacheEntry key = entry.getKey();
279                ValueNode value = entry.getValue();
280                boolean phi = false;
281                for (int i = 1; i < states.size(); i++) {
282                    ValueNode otherValue = states.get(i).readCache.get(key);
283                    if (otherValue == null) {
284                        value = null;
285                        phi = false;
286                        break;
287                    }
288                    if (!phi && otherValue != value) {
289                        phi = true;
290                    }
291                }
292                if (phi) {
293                    PhiNode phiNode = getPhi(entry, value.stamp().unrestricted());
294                    mergeEffects.addFloatingNode(phiNode, "mergeReadCache");
295                    for (int i = 0; i < states.size(); i++) {
296                        setPhiInput(phiNode, i, states.get(i).getReadCache(key.object, key.identity, key.index, PEReadEliminationClosure.this));
297                    }
298                    newState.readCache.put(key, phiNode);
299                } else if (value != null) {
300                    newState.readCache.put(key, value);
301                }
302            }
303            for (PhiNode phi : getPhis()) {
304                if (phi.getKind() == Kind.Object) {
305                    for (Map.Entry<ReadCacheEntry, ValueNode> entry : states.get(0).readCache.entrySet()) {
306                        if (entry.getKey().object == getPhiValueAt(phi, 0)) {
307                            mergeReadCachePhi(phi, entry.getKey().identity, entry.getKey().index, states);
308                        }
309                    }
310                }
311            }
312        }
313
314        private void mergeReadCachePhi(PhiNode phi, LocationIdentity identity, int index, List<PEReadEliminationBlockState> states) {
315            ValueNode[] values = new ValueNode[states.size()];
316            for (int i = 0; i < states.size(); i++) {
317                ValueNode value = states.get(i).getReadCache(getPhiValueAt(phi, i), identity, index, PEReadEliminationClosure.this);
318                if (value == null) {
319                    return;
320                }
321                values[i] = value;
322            }
323
324            PhiNode phiNode = getPhi(new ReadCacheEntry(identity, phi, index), values[0].stamp().unrestricted());
325            mergeEffects.addFloatingNode(phiNode, "mergeReadCachePhi");
326            for (int i = 0; i < values.length; i++) {
327                setPhiInput(phiNode, i, values[i]);
328            }
329            newState.readCache.put(new ReadCacheEntry(identity, phi, index), phiNode);
330        }
331    }
332}