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.phases.common;
024
025import static com.oracle.graal.graph.Graph.NodeEvent.*;
026import static jdk.internal.jvmci.meta.LocationIdentity.*;
027
028import java.util.*;
029
030import jdk.internal.jvmci.meta.*;
031
032import com.oracle.graal.compiler.common.*;
033import com.oracle.graal.compiler.common.cfg.*;
034import com.oracle.graal.graph.Graph.NodeEventScope;
035import com.oracle.graal.graph.*;
036import com.oracle.graal.nodes.*;
037import com.oracle.graal.nodes.calc.*;
038import com.oracle.graal.nodes.cfg.*;
039import com.oracle.graal.nodes.extended.*;
040import com.oracle.graal.nodes.memory.*;
041import com.oracle.graal.nodes.util.*;
042import com.oracle.graal.phases.*;
043import com.oracle.graal.phases.common.util.*;
044import com.oracle.graal.phases.graph.*;
045import com.oracle.graal.phases.graph.ReentrantNodeIterator.LoopInfo;
046import com.oracle.graal.phases.graph.ReentrantNodeIterator.NodeIteratorClosure;
047
048public class FloatingReadPhase extends Phase {
049
050    private boolean createFloatingReads;
051    private boolean createMemoryMapNodes;
052
053    public static class MemoryMapImpl implements MemoryMap {
054
055        private final Map<LocationIdentity, MemoryNode> lastMemorySnapshot;
056
057        public MemoryMapImpl(MemoryMapImpl memoryMap) {
058            lastMemorySnapshot = CollectionsFactory.newMap(memoryMap.lastMemorySnapshot);
059        }
060
061        public MemoryMapImpl(StartNode start) {
062            lastMemorySnapshot = CollectionsFactory.newMap();
063            lastMemorySnapshot.put(any(), start);
064        }
065
066        public MemoryMapImpl() {
067            lastMemorySnapshot = CollectionsFactory.newMap();
068        }
069
070        @Override
071        public MemoryNode getLastLocationAccess(LocationIdentity locationIdentity) {
072            MemoryNode lastLocationAccess;
073            if (locationIdentity.isImmutable()) {
074                return null;
075            } else {
076                lastLocationAccess = lastMemorySnapshot.get(locationIdentity);
077                if (lastLocationAccess == null) {
078                    lastLocationAccess = lastMemorySnapshot.get(any());
079                    assert lastLocationAccess != null;
080                }
081                return lastLocationAccess;
082            }
083        }
084
085        @Override
086        public Collection<LocationIdentity> getLocations() {
087            return lastMemorySnapshot.keySet();
088        }
089
090        public Map<LocationIdentity, MemoryNode> getMap() {
091            return lastMemorySnapshot;
092        }
093    }
094
095    public FloatingReadPhase() {
096        this(true, false);
097    }
098
099    /**
100     * @param createFloatingReads specifies whether {@link FloatableAccessNode}s like
101     *            {@link ReadNode} should be converted into floating nodes (e.g.,
102     *            {@link FloatingReadNode}s) where possible
103     * @param createMemoryMapNodes a {@link MemoryMapNode} will be created for each return if this
104     *            is true
105     */
106    public FloatingReadPhase(boolean createFloatingReads, boolean createMemoryMapNodes) {
107        this.createFloatingReads = createFloatingReads;
108        this.createMemoryMapNodes = createMemoryMapNodes;
109    }
110
111    /**
112     * Removes nodes from a given set that (transitively) have a usage outside the set.
113     */
114    private static Set<Node> removeExternallyUsedNodes(Set<Node> set) {
115        boolean change;
116        do {
117            change = false;
118            for (Iterator<Node> iter = set.iterator(); iter.hasNext();) {
119                Node node = iter.next();
120                for (Node usage : node.usages()) {
121                    if (!set.contains(usage)) {
122                        change = true;
123                        iter.remove();
124                        break;
125                    }
126                }
127            }
128        } while (change);
129        return set;
130    }
131
132    protected void processNode(FixedNode node, Set<LocationIdentity> currentState) {
133        if (node instanceof MemoryCheckpoint.Single) {
134            currentState.add(((MemoryCheckpoint.Single) node).getLocationIdentity());
135        } else if (node instanceof MemoryCheckpoint.Multi) {
136            for (LocationIdentity identity : ((MemoryCheckpoint.Multi) node).getLocationIdentities()) {
137                currentState.add(identity);
138            }
139        }
140    }
141
142    protected void processBlock(Block b, Set<LocationIdentity> currentState) {
143        for (FixedNode n : b.getNodes()) {
144            processNode(n, currentState);
145        }
146    }
147
148    private Set<LocationIdentity> processLoop(HIRLoop loop, Map<LoopBeginNode, Set<LocationIdentity>> modifiedInLoops) {
149        LoopBeginNode loopBegin = (LoopBeginNode) loop.getHeader().getBeginNode();
150        Set<LocationIdentity> result = modifiedInLoops.get(loopBegin);
151        if (result != null) {
152            return result;
153        }
154
155        result = CollectionsFactory.newSet();
156        for (Loop<Block> inner : loop.getChildren()) {
157            result.addAll(processLoop((HIRLoop) inner, modifiedInLoops));
158        }
159
160        for (Block b : loop.getBlocks()) {
161            if (b.getLoop() == loop) {
162                processBlock(b, result);
163            }
164        }
165
166        modifiedInLoops.put(loopBegin, result);
167        return result;
168    }
169
170    @Override
171    protected void run(StructuredGraph graph) {
172        Map<LoopBeginNode, Set<LocationIdentity>> modifiedInLoops = null;
173        if (graph.hasLoops()) {
174            modifiedInLoops = new HashMap<>();
175            ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, false, false);
176            for (Loop<?> l : cfg.getLoops()) {
177                HIRLoop loop = (HIRLoop) l;
178                processLoop(loop, modifiedInLoops);
179            }
180        }
181
182        HashSetNodeEventListener listener = new HashSetNodeEventListener(EnumSet.of(NODE_ADDED, ZERO_USAGES));
183        try (NodeEventScope nes = graph.trackNodeEvents(listener)) {
184            ReentrantNodeIterator.apply(new FloatingReadClosure(modifiedInLoops, createFloatingReads, createMemoryMapNodes), graph.start(), new MemoryMapImpl(graph.start()));
185        }
186
187        for (Node n : removeExternallyUsedNodes(listener.getNodes())) {
188            if (n.isAlive() && n instanceof FloatingNode) {
189                n.replaceAtUsages(null);
190                GraphUtil.killWithUnusedFloatingInputs(n);
191            }
192        }
193        if (createFloatingReads) {
194            assert !graph.isAfterFloatingReadPhase();
195            graph.setAfterFloatingReadPhase(true);
196        }
197    }
198
199    public static MemoryMapImpl mergeMemoryMaps(AbstractMergeNode merge, List<? extends MemoryMap> states) {
200        MemoryMapImpl newState = new MemoryMapImpl();
201
202        Set<LocationIdentity> keys = CollectionsFactory.newSet();
203        for (MemoryMap other : states) {
204            keys.addAll(other.getLocations());
205        }
206        assert checkNoImmutableLocations(keys);
207
208        for (LocationIdentity key : keys) {
209            int mergedStatesCount = 0;
210            boolean isPhi = false;
211            MemoryNode merged = null;
212            for (MemoryMap state : states) {
213                MemoryNode last = state.getLastLocationAccess(key);
214                if (isPhi) {
215                    ((MemoryPhiNode) merged).addInput(ValueNodeUtil.asNode(last));
216                } else {
217                    if (merged == last) {
218                        // nothing to do
219                    } else if (merged == null) {
220                        merged = last;
221                    } else {
222                        MemoryPhiNode phi = merge.graph().addWithoutUnique(new MemoryPhiNode(merge, key));
223                        for (int j = 0; j < mergedStatesCount; j++) {
224                            phi.addInput(ValueNodeUtil.asNode(merged));
225                        }
226                        phi.addInput(ValueNodeUtil.asNode(last));
227                        merged = phi;
228                        isPhi = true;
229                    }
230                }
231                mergedStatesCount++;
232            }
233            newState.lastMemorySnapshot.put(key, merged);
234        }
235        return newState;
236
237    }
238
239    private static boolean checkNoImmutableLocations(Set<LocationIdentity> keys) {
240        keys.forEach(t -> {
241            assert !t.isImmutable();
242        });
243        return true;
244    }
245
246    public static class FloatingReadClosure extends NodeIteratorClosure<MemoryMapImpl> {
247
248        private final Map<LoopBeginNode, Set<LocationIdentity>> modifiedInLoops;
249        private boolean createFloatingReads;
250        private boolean createMemoryMapNodes;
251
252        public FloatingReadClosure(Map<LoopBeginNode, Set<LocationIdentity>> modifiedInLoops, boolean createFloatingReads, boolean createMemoryMapNodes) {
253            this.modifiedInLoops = modifiedInLoops;
254            this.createFloatingReads = createFloatingReads;
255            this.createMemoryMapNodes = createMemoryMapNodes;
256        }
257
258        @Override
259        protected MemoryMapImpl processNode(FixedNode node, MemoryMapImpl state) {
260            if (node instanceof MemoryAnchorNode) {
261                processAnchor((MemoryAnchorNode) node, state);
262                return state;
263            }
264
265            if (node instanceof MemoryAccess) {
266                processAccess((MemoryAccess) node, state);
267            }
268
269            if (createFloatingReads & node instanceof FloatableAccessNode) {
270                processFloatable((FloatableAccessNode) node, state);
271            } else if (node instanceof MemoryCheckpoint.Single) {
272                processCheckpoint((MemoryCheckpoint.Single) node, state);
273            } else if (node instanceof MemoryCheckpoint.Multi) {
274                processCheckpoint((MemoryCheckpoint.Multi) node, state);
275            }
276            assert MemoryCheckpoint.TypeAssertion.correctType(node) : node;
277
278            if (createMemoryMapNodes && node instanceof ReturnNode) {
279                ((ReturnNode) node).setMemoryMap(node.graph().unique(new MemoryMapNode(state.lastMemorySnapshot)));
280            }
281            return state;
282        }
283
284        /**
285         * Improve the memory graph by re-wiring all usages of a {@link MemoryAnchorNode} to the
286         * real last access location.
287         */
288        private static void processAnchor(MemoryAnchorNode anchor, MemoryMapImpl state) {
289            for (Node node : anchor.usages().snapshot()) {
290                if (node instanceof MemoryAccess) {
291                    MemoryAccess access = (MemoryAccess) node;
292                    if (access.getLastLocationAccess() == anchor) {
293                        MemoryNode lastLocationAccess = state.getLastLocationAccess(access.getLocationIdentity());
294                        assert lastLocationAccess != null;
295                        access.setLastLocationAccess(lastLocationAccess);
296                    }
297                }
298            }
299
300            if (anchor.hasNoUsages()) {
301                anchor.graph().removeFixed(anchor);
302            }
303        }
304
305        private static void processAccess(MemoryAccess access, MemoryMapImpl state) {
306            LocationIdentity locationIdentity = access.getLocationIdentity();
307            if (!locationIdentity.equals(LocationIdentity.any())) {
308                MemoryNode lastLocationAccess = state.getLastLocationAccess(locationIdentity);
309                access.setLastLocationAccess(lastLocationAccess);
310            }
311        }
312
313        private static void processCheckpoint(MemoryCheckpoint.Single checkpoint, MemoryMapImpl state) {
314            processIdentity(checkpoint.getLocationIdentity(), checkpoint, state);
315        }
316
317        private static void processCheckpoint(MemoryCheckpoint.Multi checkpoint, MemoryMapImpl state) {
318            for (LocationIdentity identity : checkpoint.getLocationIdentities()) {
319                processIdentity(identity, checkpoint, state);
320            }
321        }
322
323        private static void processIdentity(LocationIdentity identity, MemoryCheckpoint checkpoint, MemoryMapImpl state) {
324            if (identity.isAny()) {
325                state.lastMemorySnapshot.clear();
326            }
327            state.lastMemorySnapshot.put(identity, checkpoint);
328        }
329
330        private static void processFloatable(FloatableAccessNode accessNode, MemoryMapImpl state) {
331            StructuredGraph graph = accessNode.graph();
332            LocationIdentity locationIdentity = accessNode.getLocationIdentity();
333            if (accessNode.canFloat()) {
334                assert accessNode.getNullCheck() == false;
335                MemoryNode lastLocationAccess = state.getLastLocationAccess(locationIdentity);
336                FloatingAccessNode floatingNode = accessNode.asFloatingNode(lastLocationAccess);
337                ValueAnchorNode anchor = null;
338                GuardingNode guard = accessNode.getGuard();
339                if (guard != null) {
340                    anchor = graph.add(new ValueAnchorNode(guard.asNode()));
341                    graph.addAfterFixed(accessNode, anchor);
342                }
343                graph.replaceFixedWithFloating(accessNode, floatingNode);
344            }
345        }
346
347        @Override
348        protected MemoryMapImpl merge(AbstractMergeNode merge, List<MemoryMapImpl> states) {
349            return mergeMemoryMaps(merge, states);
350        }
351
352        @Override
353        protected MemoryMapImpl afterSplit(AbstractBeginNode node, MemoryMapImpl oldState) {
354            MemoryMapImpl result = new MemoryMapImpl(oldState);
355            if (node.predecessor() instanceof InvokeWithExceptionNode) {
356                /*
357                 * InvokeWithException cannot be the lastLocationAccess for a FloatingReadNode.
358                 * Since it is both the invoke and a control flow split, the scheduler cannot
359                 * schedule anything immediately after the invoke. It can only schedule in the
360                 * normal or exceptional successor - and we have to tell the scheduler here which
361                 * side it needs to choose by putting in the location identity on both successors.
362                 */
363                InvokeWithExceptionNode invoke = (InvokeWithExceptionNode) node.predecessor();
364                result.lastMemorySnapshot.put(invoke.getLocationIdentity(), (MemoryCheckpoint) node);
365            }
366            return result;
367        }
368
369        @Override
370        protected Map<LoopExitNode, MemoryMapImpl> processLoop(LoopBeginNode loop, MemoryMapImpl initialState) {
371            Set<LocationIdentity> modifiedLocations = modifiedInLoops.get(loop);
372            Map<LocationIdentity, MemoryPhiNode> phis = CollectionsFactory.newMap();
373            if (modifiedLocations.contains(LocationIdentity.any())) {
374                // create phis for all locations if ANY is modified in the loop
375                modifiedLocations = CollectionsFactory.newSet(modifiedLocations);
376                modifiedLocations.addAll(initialState.lastMemorySnapshot.keySet());
377            }
378
379            for (LocationIdentity location : modifiedLocations) {
380                createMemoryPhi(loop, initialState, phis, location);
381            }
382            for (Map.Entry<LocationIdentity, MemoryPhiNode> entry : phis.entrySet()) {
383                initialState.lastMemorySnapshot.put(entry.getKey(), entry.getValue());
384            }
385
386            LoopInfo<MemoryMapImpl> loopInfo = ReentrantNodeIterator.processLoop(this, loop, initialState);
387
388            for (Map.Entry<LoopEndNode, MemoryMapImpl> entry : loopInfo.endStates.entrySet()) {
389                int endIndex = loop.phiPredecessorIndex(entry.getKey());
390                for (Map.Entry<LocationIdentity, MemoryPhiNode> phiEntry : phis.entrySet()) {
391                    LocationIdentity key = phiEntry.getKey();
392                    PhiNode phi = phiEntry.getValue();
393                    phi.initializeValueAt(endIndex, ValueNodeUtil.asNode(entry.getValue().getLastLocationAccess(key)));
394                }
395            }
396            return loopInfo.exitStates;
397        }
398
399        private static void createMemoryPhi(LoopBeginNode loop, MemoryMapImpl initialState, Map<LocationIdentity, MemoryPhiNode> phis, LocationIdentity location) {
400            MemoryPhiNode phi = loop.graph().addWithoutUnique(new MemoryPhiNode(loop, location));
401            phi.addInput(ValueNodeUtil.asNode(initialState.getLastLocationAccess(location)));
402            phis.put(location, phi);
403        }
404    }
405}