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