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