1 /* 2 * Copyright (c) 2015, 2019, 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 */ 23 24 25 package org.graalvm.compiler.phases.schedule; 26 27 import java.util.List; 28 29 import jdk.internal.vm.compiler.collections.EconomicSet; 30 import jdk.internal.vm.compiler.collections.Equivalence; 31 import org.graalvm.compiler.core.common.cfg.BlockMap; 32 import org.graalvm.compiler.core.common.cfg.Loop; 33 import org.graalvm.compiler.debug.DebugContext; 34 import org.graalvm.compiler.graph.Node; 35 import org.graalvm.compiler.graph.NodeMap; 36 import org.graalvm.compiler.nodes.AbstractBeginNode; 37 import org.graalvm.compiler.nodes.AbstractMergeNode; 38 import org.graalvm.compiler.nodes.LoopBeginNode; 39 import org.graalvm.compiler.nodes.LoopExitNode; 40 import org.graalvm.compiler.nodes.MemoryProxyNode; 41 import org.graalvm.compiler.nodes.PhiNode; 42 import org.graalvm.compiler.nodes.ProxyNode; 43 import org.graalvm.compiler.nodes.StructuredGraph; 44 import org.graalvm.compiler.nodes.VirtualState; 45 import org.graalvm.compiler.nodes.cfg.Block; 46 import org.graalvm.compiler.nodes.cfg.HIRLoop; 47 import org.graalvm.compiler.nodes.memory.FloatingReadNode; 48 import org.graalvm.compiler.nodes.memory.MemoryCheckpoint; 49 import org.graalvm.compiler.nodes.memory.MemoryNode; 50 import org.graalvm.compiler.nodes.memory.MemoryPhiNode; 51 import org.graalvm.compiler.phases.graph.ReentrantBlockIterator; 52 import org.graalvm.compiler.phases.graph.ReentrantBlockIterator.BlockIteratorClosure; 53 import jdk.internal.vm.compiler.word.LocationIdentity; 54 55 /** 56 * Verifies that the schedule of the graph is correct. Checks that floating reads are not killed 57 * between definition and usage. Also checks that there are no usages spanning loop exits without a 58 * proper proxy node. 59 */ 60 public final class ScheduleVerification extends BlockIteratorClosure<EconomicSet<FloatingReadNode>> { 61 62 private final BlockMap<List<Node>> blockToNodesMap; 63 private final NodeMap<Block> nodeMap; 64 private final StructuredGraph graph; 65 check(Block startBlock, BlockMap<List<Node>> blockToNodesMap, NodeMap<Block> nodeMap)66 public static boolean check(Block startBlock, BlockMap<List<Node>> blockToNodesMap, NodeMap<Block> nodeMap) { 67 ReentrantBlockIterator.apply(new ScheduleVerification(blockToNodesMap, nodeMap, startBlock.getBeginNode().graph()), startBlock); 68 return true; 69 } 70 ScheduleVerification(BlockMap<List<Node>> blockToNodesMap, NodeMap<Block> nodeMap, StructuredGraph graph)71 private ScheduleVerification(BlockMap<List<Node>> blockToNodesMap, NodeMap<Block> nodeMap, StructuredGraph graph) { 72 this.blockToNodesMap = blockToNodesMap; 73 this.nodeMap = nodeMap; 74 this.graph = graph; 75 } 76 77 @Override getInitialState()78 protected EconomicSet<FloatingReadNode> getInitialState() { 79 return EconomicSet.create(Equivalence.IDENTITY); 80 } 81 82 @Override processBlock(Block block, EconomicSet<FloatingReadNode> currentState)83 protected EconomicSet<FloatingReadNode> processBlock(Block block, EconomicSet<FloatingReadNode> currentState) { 84 AbstractBeginNode beginNode = block.getBeginNode(); 85 if (beginNode instanceof AbstractMergeNode) { 86 AbstractMergeNode abstractMergeNode = (AbstractMergeNode) beginNode; 87 for (PhiNode phi : abstractMergeNode.phis()) { 88 if (phi instanceof MemoryPhiNode) { 89 MemoryPhiNode memoryPhiNode = (MemoryPhiNode) phi; 90 addFloatingReadUsages(currentState, memoryPhiNode); 91 } 92 } 93 } 94 if (beginNode instanceof LoopExitNode) { 95 LoopExitNode loopExitNode = (LoopExitNode) beginNode; 96 for (ProxyNode proxy : loopExitNode.proxies()) { 97 if (proxy instanceof MemoryProxyNode) { 98 MemoryProxyNode memoryProxyNode = (MemoryProxyNode) proxy; 99 addFloatingReadUsages(currentState, memoryProxyNode); 100 } 101 } 102 } 103 for (Node n : blockToNodesMap.get(block)) { 104 if (n instanceof MemoryCheckpoint) { 105 if (n instanceof MemoryCheckpoint.Single) { 106 MemoryCheckpoint.Single single = (MemoryCheckpoint.Single) n; 107 processLocation(n, single.getKilledLocationIdentity(), currentState); 108 } else if (n instanceof MemoryCheckpoint.Multi) { 109 MemoryCheckpoint.Multi multi = (MemoryCheckpoint.Multi) n; 110 for (LocationIdentity location : multi.getKilledLocationIdentities()) { 111 processLocation(n, location, currentState); 112 } 113 } 114 115 addFloatingReadUsages(currentState, n); 116 } else if (n instanceof MemoryNode) { 117 addFloatingReadUsages(currentState, n); 118 } else if (n instanceof FloatingReadNode) { 119 FloatingReadNode floatingReadNode = (FloatingReadNode) n; 120 if (floatingReadNode.getLastLocationAccess() != null && floatingReadNode.getLocationIdentity().isMutable()) { 121 if (currentState.contains(floatingReadNode)) { 122 // Floating read was found in the state. 123 currentState.remove(floatingReadNode); 124 } else { 125 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=" + 126 block + ", block begin: " + block.getBeginNode() + " block loop: " + block.getLoop() + ", " + blockToNodesMap.get(block).get(0)); 127 } 128 } 129 } 130 assert nodeMap.get(n) == block; 131 if (graph.hasValueProxies() && block.getLoop() != null && !(n instanceof VirtualState)) { 132 for (Node usage : n.usages()) { 133 Node usageNode = usage; 134 135 if (usageNode instanceof PhiNode) { 136 PhiNode phiNode = (PhiNode) usage; 137 usageNode = phiNode.merge(); 138 } 139 140 if (usageNode instanceof LoopExitNode) { 141 LoopExitNode loopExitNode = (LoopExitNode) usageNode; 142 if (loopExitNode.loopBegin() == n || loopExitNode.stateAfter() == n) { 143 continue; 144 } 145 } 146 Block usageBlock = nodeMap.get(usageNode); 147 148 Loop<Block> usageLoop = null; 149 if (usageNode instanceof ProxyNode) { 150 ProxyNode proxyNode = (ProxyNode) usageNode; 151 usageLoop = nodeMap.get(proxyNode.proxyPoint().loopBegin()).getLoop(); 152 } else { 153 if (usageBlock.getBeginNode() instanceof LoopExitNode) { 154 // For nodes in the loop exit node block, we don't know for sure 155 // whether they are "in the loop" or not. It depends on whether 156 // one of their transient usages is a loop proxy node. 157 // For now, let's just assume those nodes are OK, i.e., "in the loop". 158 LoopExitNode loopExitNode = (LoopExitNode) usageBlock.getBeginNode(); 159 usageLoop = nodeMap.get(loopExitNode.loopBegin()).getLoop(); 160 } else { 161 usageLoop = usageBlock.getLoop(); 162 } 163 } 164 165 assert usageLoop != null : n + ", " + nodeMap.get(n) + " / " + usageNode + ", " + nodeMap.get(usageNode); 166 while (usageLoop != block.getLoop() && usageLoop != null) { 167 usageLoop = usageLoop.getParent(); 168 } 169 assert usageLoop != null : n + ", " + usageNode + ", " + usageBlock + ", " + usageBlock.getLoop() + ", " + block + ", " + block.getLoop(); 170 } 171 } 172 } 173 return currentState; 174 } 175 addFloatingReadUsages(EconomicSet<FloatingReadNode> currentState, Node n)176 private static void addFloatingReadUsages(EconomicSet<FloatingReadNode> currentState, Node n) { 177 for (FloatingReadNode read : n.usages().filter(FloatingReadNode.class)) { 178 if (read.getLastLocationAccess() == n && read.getLocationIdentity().isMutable()) { 179 currentState.add(read); 180 } 181 } 182 } 183 processLocation(Node n, LocationIdentity location, EconomicSet<FloatingReadNode> currentState)184 private void processLocation(Node n, LocationIdentity location, EconomicSet<FloatingReadNode> currentState) { 185 assert n != null; 186 if (location.isImmutable()) { 187 return; 188 } 189 190 for (FloatingReadNode r : cloneState(currentState)) { 191 if (r.getLocationIdentity().overlaps(location)) { 192 // This read is killed by this location. 193 r.getDebug().log(DebugContext.VERBOSE_LEVEL, "%s removing %s from state", n, r); 194 currentState.remove(r); 195 } 196 } 197 } 198 199 @Override merge(Block merge, List<EconomicSet<FloatingReadNode>> states)200 protected EconomicSet<FloatingReadNode> merge(Block merge, List<EconomicSet<FloatingReadNode>> states) { 201 EconomicSet<FloatingReadNode> result = states.get(0); 202 for (int i = 1; i < states.size(); ++i) { 203 result.retainAll(states.get(i)); 204 } 205 return result; 206 } 207 208 @Override cloneState(EconomicSet<FloatingReadNode> oldState)209 protected EconomicSet<FloatingReadNode> cloneState(EconomicSet<FloatingReadNode> oldState) { 210 EconomicSet<FloatingReadNode> result = EconomicSet.create(Equivalence.IDENTITY); 211 if (oldState != null) { 212 result.addAll(oldState); 213 } 214 return result; 215 } 216 217 @Override processLoop(Loop<Block> loop, EconomicSet<FloatingReadNode> initialState)218 protected List<EconomicSet<FloatingReadNode>> processLoop(Loop<Block> loop, EconomicSet<FloatingReadNode> initialState) { 219 HIRLoop l = (HIRLoop) loop; 220 for (MemoryPhiNode memoryPhi : ((LoopBeginNode) l.getHeader().getBeginNode()).memoryPhis()) { 221 for (FloatingReadNode r : cloneState(initialState)) { 222 if (r.getLocationIdentity().overlaps(memoryPhi.getLocationIdentity())) { 223 initialState.remove(r); 224 } 225 } 226 } 227 return ReentrantBlockIterator.processLoop(this, loop, initialState).exitStates; 228 } 229 } 230