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 jdk.internal.jvmci.meta.LocationIdentity.*;
026
027import java.util.*;
028
029import jdk.internal.jvmci.meta.*;
030
031import com.oracle.graal.compiler.common.*;
032import com.oracle.graal.compiler.common.type.*;
033import com.oracle.graal.graph.*;
034import com.oracle.graal.nodes.*;
035import com.oracle.graal.nodes.cfg.*;
036import com.oracle.graal.nodes.extended.*;
037import com.oracle.graal.nodes.java.*;
038import com.oracle.graal.nodes.memory.*;
039import com.oracle.graal.nodes.memory.address.*;
040import com.oracle.graal.nodes.util.*;
041import com.oracle.graal.virtual.phases.ea.ReadEliminationBlockState.CacheEntry;
042import com.oracle.graal.virtual.phases.ea.ReadEliminationBlockState.LoadCacheEntry;
043import com.oracle.graal.virtual.phases.ea.ReadEliminationBlockState.ReadCacheEntry;
044import com.oracle.graal.virtual.phases.ea.ReadEliminationBlockState.UnsafeLoadCacheEntry;
045
046public class ReadEliminationClosure extends EffectsClosure<ReadEliminationBlockState> {
047
048    public ReadEliminationClosure(ControlFlowGraph cfg) {
049        super(null, cfg);
050    }
051
052    @Override
053    protected ReadEliminationBlockState getInitialState() {
054        return new ReadEliminationBlockState();
055    }
056
057    @Override
058    protected boolean processNode(Node node, ReadEliminationBlockState state, GraphEffectList effects, FixedWithNextNode lastFixedNode) {
059        boolean deleted = false;
060        if (node instanceof AccessFieldNode) {
061            AccessFieldNode access = (AccessFieldNode) node;
062            if (access.isVolatile()) {
063                processIdentity(state, any());
064            } else {
065                ValueNode object = GraphUtil.unproxify(access.object());
066                LoadCacheEntry identifier = new LoadCacheEntry(object, access.field().getLocationIdentity());
067                ValueNode cachedValue = state.getCacheEntry(identifier);
068                if (node instanceof LoadFieldNode) {
069                    if (cachedValue != null && access.stamp().isCompatible(cachedValue.stamp())) {
070                        effects.replaceAtUsages(access, cachedValue);
071                        addScalarAlias(access, cachedValue);
072                        deleted = true;
073                    } else {
074                        state.addCacheEntry(identifier, access);
075                    }
076                } else {
077                    assert node instanceof StoreFieldNode;
078                    StoreFieldNode store = (StoreFieldNode) node;
079                    ValueNode value = getScalarAlias(store.value());
080                    if (GraphUtil.unproxify(value) == GraphUtil.unproxify(cachedValue)) {
081                        effects.deleteNode(store);
082                        deleted = true;
083                    }
084                    state.killReadCache(store.field().getLocationIdentity());
085                    state.addCacheEntry(identifier, value);
086                }
087            }
088        } else if (node instanceof ReadNode) {
089            ReadNode read = (ReadNode) node;
090            if (read.getAddress() instanceof OffsetAddressNode) {
091                OffsetAddressNode address = (OffsetAddressNode) read.getAddress();
092                if (address.getOffset().isConstant()) {
093                    ValueNode object = GraphUtil.unproxify(address.getBase());
094                    ReadCacheEntry identifier = new ReadCacheEntry(object, address.getOffset(), read.getLocationIdentity());
095                    ValueNode cachedValue = state.getCacheEntry(identifier);
096                    if (cachedValue != null && read.stamp().isCompatible(cachedValue.stamp())) {
097                        // Anchor guard if it is not fixed and different from cachedValue's guard
098                        if (read.getGuard() != null && !(read.getGuard() instanceof FixedNode)) {
099                            if (!(cachedValue instanceof GuardedNode) || ((GuardedNode) cachedValue).getGuard() != read.getGuard()) {
100                                effects.addFixedNodeBefore(new ValueAnchorNode((ValueNode) read.getGuard()), read);
101                            }
102                        }
103                    }
104                }
105            }
106        } else if (node instanceof WriteNode) {
107            WriteNode write = (WriteNode) node;
108            if (write.getAddress() instanceof OffsetAddressNode) {
109                OffsetAddressNode address = (OffsetAddressNode) write.getAddress();
110                if (address.getOffset().isConstant()) {
111                    ValueNode object = GraphUtil.unproxify(address.getBase());
112                    ReadCacheEntry identifier = new ReadCacheEntry(object, address.getOffset(), write.getLocationIdentity());
113                    ValueNode cachedValue = state.getCacheEntry(identifier);
114
115                    ValueNode value = getScalarAlias(write.value());
116                    if (GraphUtil.unproxify(value) == GraphUtil.unproxify(cachedValue)) {
117                        effects.deleteNode(write);
118                        deleted = true;
119                    }
120                    processIdentity(state, write.getLocationIdentity());
121                    state.addCacheEntry(identifier, value);
122                } else {
123                    processIdentity(state, write.getLocationIdentity());
124                }
125            }
126        } else if (node instanceof UnsafeAccessNode) {
127            if (node instanceof UnsafeLoadNode) {
128                UnsafeLoadNode load = (UnsafeLoadNode) node;
129                if (load.offset().isConstant() && !load.getLocationIdentity().equals(LocationIdentity.any())) {
130                    ValueNode object = GraphUtil.unproxify(load.object());
131                    UnsafeLoadCacheEntry identifier = new UnsafeLoadCacheEntry(object, load.offset(), load.getLocationIdentity());
132                    ValueNode cachedValue = state.getCacheEntry(identifier);
133                    if (cachedValue != null && load.stamp().isCompatible(cachedValue.stamp())) {
134                        effects.replaceAtUsages(load, cachedValue);
135                        addScalarAlias(load, cachedValue);
136                        deleted = true;
137                    } else {
138                        state.addCacheEntry(identifier, load);
139                    }
140                }
141            } else {
142                assert node instanceof UnsafeStoreNode;
143                UnsafeStoreNode write = (UnsafeStoreNode) node;
144                if (write.offset().isConstant() && !write.getLocationIdentity().equals(LocationIdentity.any())) {
145                    ValueNode object = GraphUtil.unproxify(write.object());
146                    UnsafeLoadCacheEntry identifier = new UnsafeLoadCacheEntry(object, write.offset(), write.getLocationIdentity());
147                    ValueNode cachedValue = state.getCacheEntry(identifier);
148
149                    ValueNode value = getScalarAlias(write.value());
150                    if (GraphUtil.unproxify(value) == GraphUtil.unproxify(cachedValue)) {
151                        effects.deleteNode(write);
152                        deleted = true;
153                    }
154                    processIdentity(state, write.getLocationIdentity());
155                    state.addCacheEntry(identifier, value);
156                } else {
157                    processIdentity(state, write.getLocationIdentity());
158                }
159            }
160        } else if (node instanceof MemoryCheckpoint.Single) {
161            LocationIdentity identity = ((MemoryCheckpoint.Single) node).getLocationIdentity();
162            processIdentity(state, identity);
163        } else if (node instanceof MemoryCheckpoint.Multi) {
164            for (LocationIdentity identity : ((MemoryCheckpoint.Multi) node).getLocationIdentities()) {
165                processIdentity(state, identity);
166            }
167        }
168        return deleted;
169    }
170
171    private static void processIdentity(ReadEliminationBlockState state, LocationIdentity identity) {
172        if (identity.isAny()) {
173            state.killReadCache();
174            return;
175        }
176        state.killReadCache(identity);
177    }
178
179    @Override
180    protected void processLoopExit(LoopExitNode exitNode, ReadEliminationBlockState initialState, ReadEliminationBlockState exitState, GraphEffectList effects) {
181        if (exitNode.graph().hasValueProxies()) {
182            for (Map.Entry<CacheEntry<?>, ValueNode> entry : exitState.getReadCache().entrySet()) {
183                if (initialState.getReadCache().get(entry.getKey()) != entry.getValue()) {
184                    ProxyNode proxy = new ValueProxyNode(exitState.getCacheEntry(entry.getKey()), exitNode);
185                    effects.addFloatingNode(proxy, "readCacheProxy");
186                    entry.setValue(proxy);
187                }
188            }
189        }
190    }
191
192    @Override
193    protected ReadEliminationBlockState cloneState(ReadEliminationBlockState other) {
194        return new ReadEliminationBlockState(other);
195    }
196
197    @Override
198    protected MergeProcessor createMergeProcessor(Block merge) {
199        return new ReadEliminationMergeProcessor(merge);
200    }
201
202    private class ReadEliminationMergeProcessor extends EffectsClosure<ReadEliminationBlockState>.MergeProcessor {
203
204        private final HashMap<Object, ValuePhiNode> materializedPhis = CollectionsFactory.newMap();
205
206        public ReadEliminationMergeProcessor(Block mergeBlock) {
207            super(mergeBlock);
208        }
209
210        protected <T> PhiNode getCachedPhi(T virtual, Stamp stamp) {
211            ValuePhiNode result = materializedPhis.get(virtual);
212            if (result == null) {
213                result = createValuePhi(stamp);
214                materializedPhis.put(virtual, result);
215            }
216            return result;
217        }
218
219        @Override
220        protected void merge(List<ReadEliminationBlockState> states) {
221            super.merge(states);
222
223            mergeReadCache(states);
224        }
225
226        private void mergeReadCache(List<ReadEliminationBlockState> states) {
227            for (Map.Entry<CacheEntry<?>, ValueNode> entry : states.get(0).readCache.entrySet()) {
228                CacheEntry<?> key = entry.getKey();
229                ValueNode value = entry.getValue();
230                boolean phi = false;
231                for (int i = 1; i < states.size(); i++) {
232                    ValueNode otherValue = states.get(i).readCache.get(key);
233                    if (otherValue == null) {
234                        value = null;
235                        phi = false;
236                        break;
237                    }
238                    if (!phi && otherValue != value) {
239                        phi = true;
240                    }
241                }
242                if (phi) {
243                    PhiNode phiNode = getCachedPhi(entry, value.stamp().unrestricted());
244                    mergeEffects.addFloatingNode(phiNode, "mergeReadCache");
245                    for (int i = 0; i < states.size(); i++) {
246                        setPhiInput(phiNode, i, states.get(i).getCacheEntry(key));
247                    }
248                    newState.addCacheEntry(key, phiNode);
249                } else if (value != null) {
250                    newState.addCacheEntry(key, value);
251                }
252            }
253            for (PhiNode phi : getPhis()) {
254                if (phi.getKind() == Kind.Object) {
255                    for (Map.Entry<CacheEntry<?>, ValueNode> entry : states.get(0).readCache.entrySet()) {
256                        if (entry.getKey().object == getPhiValueAt(phi, 0)) {
257                            mergeReadCachePhi(phi, entry.getKey(), states);
258                        }
259                    }
260
261                }
262            }
263        }
264
265        private void mergeReadCachePhi(PhiNode phi, CacheEntry<?> identifier, List<ReadEliminationBlockState> states) {
266            ValueNode[] values = new ValueNode[states.size()];
267            for (int i = 0; i < states.size(); i++) {
268                ValueNode value = states.get(i).getCacheEntry(identifier.duplicateWithObject(getPhiValueAt(phi, i)));
269                if (value == null) {
270                    return;
271                }
272                values[i] = value;
273            }
274
275            CacheEntry<?> newIdentifier = identifier.duplicateWithObject(phi);
276            PhiNode phiNode = getCachedPhi(newIdentifier, values[0].stamp().unrestricted());
277            mergeEffects.addFloatingNode(phiNode, "mergeReadCachePhi");
278            for (int i = 0; i < values.length; i++) {
279                setPhiInput(phiNode, i, values[i]);
280            }
281            newState.addCacheEntry(newIdentifier, phiNode);
282        }
283    }
284}