1 /* 2 * Copyright (c) 2020, 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.common; 26 27 import java.util.List; 28 29 import jdk.internal.vm.compiler.collections.EconomicMap; 30 import jdk.internal.vm.compiler.collections.MapCursor; 31 import org.graalvm.compiler.api.replacements.Snippet; 32 import org.graalvm.compiler.debug.DebugContext; 33 import org.graalvm.compiler.debug.GraalError; 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.FixedNode; 39 import org.graalvm.compiler.nodes.LoopBeginNode; 40 import org.graalvm.compiler.nodes.LoopEndNode; 41 import org.graalvm.compiler.nodes.LoopExitNode; 42 import org.graalvm.compiler.nodes.StartNode; 43 import org.graalvm.compiler.nodes.StateSplit; 44 import org.graalvm.compiler.nodes.StructuredGraph; 45 import org.graalvm.compiler.nodes.util.GraphUtil; 46 import org.graalvm.compiler.phases.graph.ReentrantNodeIterator.LoopInfo; 47 import org.graalvm.compiler.phases.graph.ReentrantNodeIterator; 48 import org.graalvm.compiler.phases.graph.ReentrantNodeIterator.NodeIteratorClosure; 49 50 /** 51 * Utility class for snippet lowering. 52 * 53 * Certain nodes in Graal IR can be lowered to a (sub) graph of nodes by a process called snippet 54 * lowering. For details see {@linkplain Snippet}. 55 * 56 * For example, a snippet lowering can create a merge node without a frame state. Any deoptimization 57 * point dominated by this merge will be missing frame state information since we cannot decide 58 * which frame state to use for the deoptimization point. See {@link GraphUtil#mayRemoveSplit} for 59 * more details. The same applies for loop exit nodes. 60 * 61 * This utility determines which frame state can be assigned to each node in a snippet graph. 62 * 63 * During lowering a node is replaced with the snippet which means there are only 2 possible states 64 * that can be used inside the snippet graph: the before frame state of the snippet lowered node and 65 * the after state. Generally, if a side-effect is happening inside a snippet all code after that 66 * particular side-effect must not deopt to the before state but only to the after state. All code 67 * before the side-effect is allowed to use the before state 68 */ 69 public class SnippetFrameStateAssignment { 70 71 /** 72 * Possible states to be used inside a snippet. 73 */ 74 public enum NodeStateAssignment { 75 /** 76 * The frame state before the snippet replacee. 77 */ 78 BEFORE_BCI, 79 /** 80 * The frame state after the snippet replacee. 81 */ 82 AFTER_BCI, 83 /** 84 * An invalid state setup (e.g. multiple subsequent effects inside a snippet)for a 85 * side-effecting node inside a snippet. 86 */ 87 INVALID 88 } 89 90 /** 91 * The iterator below visits a compiler graph in reverse post order and, based on the 92 * side-effecting nodes, decides which state can be used after snippet lowering for a merge or 93 * loop exit node. 94 */ 95 public static class SnippetFrameStateAssignmentClosure extends NodeIteratorClosure<NodeStateAssignment> { 96 97 private final NodeMap<NodeStateAssignment> stateMapping; 98 getStateMapping()99 public NodeMap<NodeStateAssignment> getStateMapping() { 100 return stateMapping; 101 } 102 103 /** 104 * Debugging flag to run the phase again on error to find specific invalid nodes. 105 */ 106 private static final boolean RUN_WITH_LOG_ON_ERROR = false; 107 verify()108 public boolean verify() { 109 MapCursor<Node, NodeStateAssignment> stateAssignments = stateMapping.getEntries(); 110 while (stateAssignments.advance()) { 111 Node nodeWithState = stateAssignments.getKey(); 112 NodeStateAssignment fsRequirements = stateAssignments.getValue(); 113 switch (fsRequirements) { 114 case INVALID: 115 if (RUN_WITH_LOG_ON_ERROR) { 116 ReentrantNodeIterator.apply(new SnippetFrameStateAssignmentClosure((StructuredGraph) nodeWithState.graph(), true), 117 ((StructuredGraph) nodeWithState.graph()).start(), NodeStateAssignment.BEFORE_BCI); 118 } 119 throw GraalError.shouldNotReachHere( 120 "Invalid snippet replacing a node before FS assignment with node " + nodeWithState + " for graph " + nodeWithState.graph() + " other assignments=" + 121 stateMapping); 122 default: 123 break; 124 } 125 } 126 return true; 127 } 128 129 /** 130 * Flag to enable logging of invalid state assignments during processing. 131 */ 132 private final boolean logOnInvalid; 133 SnippetFrameStateAssignmentClosure(StructuredGraph graph)134 public SnippetFrameStateAssignmentClosure(StructuredGraph graph) { 135 this(graph, false); 136 } 137 SnippetFrameStateAssignmentClosure(StructuredGraph graph, boolean logOnInvalid)138 public SnippetFrameStateAssignmentClosure(StructuredGraph graph, boolean logOnInvalid) { 139 stateMapping = new NodeMap<>(graph); 140 this.logOnInvalid = logOnInvalid; 141 } 142 143 @Override processNode(FixedNode node, NodeStateAssignment stateAssignment)144 protected NodeStateAssignment processNode(FixedNode node, NodeStateAssignment stateAssignment) { 145 NodeStateAssignment nextStateAssignment = stateAssignment; 146 if (node instanceof LoopExitNode) { 147 stateMapping.put(node, stateAssignment); 148 } 149 if (node instanceof StateSplit && ((StateSplit) node).hasSideEffect() && !(node instanceof StartNode || node instanceof AbstractMergeNode)) { 150 if (stateAssignment == NodeStateAssignment.BEFORE_BCI) { 151 nextStateAssignment = NodeStateAssignment.AFTER_BCI; 152 } else { 153 if (logOnInvalid) { 154 node.getDebug().log(DebugContext.VERY_DETAILED_LEVEL, "Node %s creating invalid assignment", node); 155 } 156 nextStateAssignment = NodeStateAssignment.INVALID; 157 } 158 } 159 return nextStateAssignment; 160 } 161 162 @Override merge(AbstractMergeNode merge, List<NodeStateAssignment> states)163 protected NodeStateAssignment merge(AbstractMergeNode merge, List<NodeStateAssignment> states) { 164 /* 165 * The state at a merge is either the before or after state, but if multiple effects 166 * exist preceding a merge we must have a merged state, and this state can only differ 167 * in its return values. If such a snippet is encountered the subsequent logic will 168 * assign an invalid state to the merge. 169 */ 170 int beforeCount = 0; 171 int afterCount = 0; 172 int invalidCount = 0; 173 174 for (int i = 0; i < states.size(); i++) { 175 if (states.get(i) == NodeStateAssignment.BEFORE_BCI) { 176 beforeCount++; 177 } else if (states.get(i) == NodeStateAssignment.AFTER_BCI) { 178 afterCount++; 179 } else { 180 invalidCount++; 181 } 182 } 183 if (invalidCount > 0) { 184 stateMapping.put(merge, NodeStateAssignment.INVALID); 185 return NodeStateAssignment.INVALID; 186 } else { 187 if (afterCount == 0) { 188 // only before states 189 assert beforeCount == states.size(); 190 stateMapping.put(merge, NodeStateAssignment.BEFORE_BCI); 191 return NodeStateAssignment.BEFORE_BCI; 192 } else { 193 // some before, and at least one after 194 assert afterCount > 0; 195 stateMapping.put(merge, NodeStateAssignment.AFTER_BCI); 196 return NodeStateAssignment.AFTER_BCI; 197 } 198 } 199 200 } 201 202 @Override afterSplit(AbstractBeginNode node, NodeStateAssignment oldState)203 protected NodeStateAssignment afterSplit(AbstractBeginNode node, NodeStateAssignment oldState) { 204 return oldState; 205 } 206 207 @Override processLoop(LoopBeginNode loop, NodeStateAssignment initialState)208 protected EconomicMap<LoopExitNode, NodeStateAssignment> processLoop(LoopBeginNode loop, NodeStateAssignment initialState) { 209 LoopInfo<NodeStateAssignment> loopInfo = ReentrantNodeIterator.processLoop(this, loop, initialState); 210 int afterCount = 0; 211 int invalidCount = 0; 212 for (LoopEndNode loopEnd : loop.loopEnds()) { 213 if (loopInfo.endStates.get(loopEnd) == NodeStateAssignment.INVALID) { 214 invalidCount++; 215 } else if (loopInfo.endStates.get(loopEnd) == NodeStateAssignment.AFTER_BCI) { 216 afterCount++; 217 } 218 } 219 NodeStateAssignment selected = null; 220 if (invalidCount > 0) { 221 selected = NodeStateAssignment.INVALID; 222 } else { 223 if (afterCount > 0) { 224 selected = NodeStateAssignment.AFTER_BCI; 225 } else { 226 selected = NodeStateAssignment.BEFORE_BCI; 227 } 228 } 229 stateMapping.put(loop, selected); 230 if (selected != initialState) { 231 for (LoopExitNode exit : loop.loopExits()) { 232 loopInfo.exitStates.put(exit, selected); 233 } 234 } 235 return loopInfo.exitStates; 236 } 237 238 } 239 } 240