1/*
2 * Copyright (c) 2015, 2016, 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 */
23package org.graalvm.compiler.phases.schedule;
24
25import java.util.List;
26
27import org.graalvm.compiler.core.common.cfg.BlockMap;
28import org.graalvm.compiler.core.common.cfg.Loop;
29import org.graalvm.compiler.debug.DebugContext;
30import org.graalvm.compiler.graph.Node;
31import org.graalvm.compiler.nodes.AbstractBeginNode;
32import org.graalvm.compiler.nodes.AbstractMergeNode;
33import org.graalvm.compiler.nodes.LoopBeginNode;
34import org.graalvm.compiler.nodes.PhiNode;
35import org.graalvm.compiler.nodes.cfg.Block;
36import org.graalvm.compiler.nodes.cfg.HIRLoop;
37import org.graalvm.compiler.nodes.memory.FloatingReadNode;
38import org.graalvm.compiler.nodes.memory.MemoryCheckpoint;
39import org.graalvm.compiler.nodes.memory.MemoryNode;
40import org.graalvm.compiler.nodes.memory.MemoryPhiNode;
41import org.graalvm.compiler.phases.graph.ReentrantBlockIterator;
42import org.graalvm.compiler.phases.graph.ReentrantBlockIterator.BlockIteratorClosure;
43import org.graalvm.util.EconomicSet;
44import org.graalvm.util.Equivalence;
45import org.graalvm.word.LocationIdentity;
46
47public final class MemoryScheduleVerification extends BlockIteratorClosure<EconomicSet<FloatingReadNode>> {
48
49    private final BlockMap<List<Node>> blockToNodesMap;
50
51    public static boolean check(Block startBlock, BlockMap<List<Node>> blockToNodesMap) {
52        ReentrantBlockIterator.apply(new MemoryScheduleVerification(blockToNodesMap), startBlock);
53        return true;
54    }
55
56    private MemoryScheduleVerification(BlockMap<List<Node>> blockToNodesMap) {
57        this.blockToNodesMap = blockToNodesMap;
58    }
59
60    @Override
61    protected EconomicSet<FloatingReadNode> getInitialState() {
62        return EconomicSet.create(Equivalence.IDENTITY);
63    }
64
65    @Override
66    protected EconomicSet<FloatingReadNode> processBlock(Block block, EconomicSet<FloatingReadNode> currentState) {
67        AbstractBeginNode beginNode = block.getBeginNode();
68        if (beginNode instanceof AbstractMergeNode) {
69            AbstractMergeNode abstractMergeNode = (AbstractMergeNode) beginNode;
70            for (PhiNode phi : abstractMergeNode.phis()) {
71                if (phi instanceof MemoryPhiNode) {
72                    MemoryPhiNode memoryPhiNode = (MemoryPhiNode) phi;
73                    addFloatingReadUsages(currentState, memoryPhiNode);
74                }
75            }
76        }
77        for (Node n : blockToNodesMap.get(block)) {
78            if (n instanceof MemoryCheckpoint) {
79                if (n instanceof MemoryCheckpoint.Single) {
80                    MemoryCheckpoint.Single single = (MemoryCheckpoint.Single) n;
81                    processLocation(n, single.getLocationIdentity(), currentState);
82                } else if (n instanceof MemoryCheckpoint.Multi) {
83                    MemoryCheckpoint.Multi multi = (MemoryCheckpoint.Multi) n;
84                    for (LocationIdentity location : multi.getLocationIdentities()) {
85                        processLocation(n, location, currentState);
86                    }
87                }
88
89                addFloatingReadUsages(currentState, n);
90            } else if (n instanceof MemoryNode) {
91                addFloatingReadUsages(currentState, n);
92            } else if (n instanceof FloatingReadNode) {
93                FloatingReadNode floatingReadNode = (FloatingReadNode) n;
94                if (floatingReadNode.getLastLocationAccess() != null && floatingReadNode.getLocationIdentity().isMutable()) {
95                    if (currentState.contains(floatingReadNode)) {
96                        // Floating read was found in the state.
97                        currentState.remove(floatingReadNode);
98                    } else {
99                        throw new RuntimeException("Floating read node " + n + " was not found in the state, i.e., it was killed by a memory check point before its place in the schedule. Block=" +
100                                        block + ", block begin: " + block.getBeginNode() + " block loop: " + block.getLoop() + ", " + blockToNodesMap.get(block).get(0));
101                    }
102                }
103
104            }
105        }
106        return currentState;
107    }
108
109    private static void addFloatingReadUsages(EconomicSet<FloatingReadNode> currentState, Node n) {
110        for (FloatingReadNode read : n.usages().filter(FloatingReadNode.class)) {
111            if (read.getLastLocationAccess() == n && read.getLocationIdentity().isMutable()) {
112                currentState.add(read);
113            }
114        }
115    }
116
117    private void processLocation(Node n, LocationIdentity location, EconomicSet<FloatingReadNode> currentState) {
118        assert n != null;
119        if (location.isImmutable()) {
120            return;
121        }
122
123        for (FloatingReadNode r : cloneState(currentState)) {
124            if (r.getLocationIdentity().overlaps(location)) {
125                // This read is killed by this location.
126                r.getDebug().log(DebugContext.VERBOSE_LEVEL, "%s removing %s from state", n, r);
127                currentState.remove(r);
128            }
129        }
130    }
131
132    @Override
133    protected EconomicSet<FloatingReadNode> merge(Block merge, List<EconomicSet<FloatingReadNode>> states) {
134        EconomicSet<FloatingReadNode> result = states.get(0);
135        for (int i = 1; i < states.size(); ++i) {
136            result.retainAll(states.get(i));
137        }
138        return result;
139    }
140
141    @Override
142    protected EconomicSet<FloatingReadNode> cloneState(EconomicSet<FloatingReadNode> oldState) {
143        EconomicSet<FloatingReadNode> result = EconomicSet.create(Equivalence.IDENTITY);
144        if (oldState != null) {
145            result.addAll(oldState);
146        }
147        return result;
148    }
149
150    @Override
151    protected List<EconomicSet<FloatingReadNode>> processLoop(Loop<Block> loop, EconomicSet<FloatingReadNode> initialState) {
152        HIRLoop l = (HIRLoop) loop;
153        for (MemoryPhiNode memoryPhi : ((LoopBeginNode) l.getHeader().getBeginNode()).memoryPhis()) {
154            for (FloatingReadNode r : cloneState(initialState)) {
155                if (r.getLocationIdentity().overlaps(memoryPhi.getLocationIdentity())) {
156                    initialState.remove(r);
157                }
158            }
159        }
160        return ReentrantBlockIterator.processLoop(this, loop, initialState).exitStates;
161    }
162}
163