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