1 /*
2 * Copyright (c) 2011, 2018, 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 static org.graalvm.compiler.phases.common.DeadCodeEliminationPhase.Optionality.Optional;
28
29 import java.util.List;
30
31 import org.graalvm.compiler.core.common.GraalOptions;
32 import org.graalvm.compiler.debug.DebugCloseable;
33 import org.graalvm.compiler.graph.Node;
34 import org.graalvm.compiler.graph.NodeSourcePosition;
35 import org.graalvm.compiler.graph.spi.SimplifierTool;
36 import org.graalvm.compiler.nodeinfo.InputType;
37 import org.graalvm.compiler.nodes.AbstractBeginNode;
38 import org.graalvm.compiler.nodes.AbstractEndNode;
39 import org.graalvm.compiler.nodes.AbstractMergeNode;
40 import org.graalvm.compiler.nodes.ConstantNode;
41 import org.graalvm.compiler.nodes.ControlSplitNode;
42 import org.graalvm.compiler.nodes.DeoptimizeNode;
43 import org.graalvm.compiler.nodes.EndNode;
44 import org.graalvm.compiler.nodes.FixedGuardNode;
45 import org.graalvm.compiler.nodes.FixedNode;
46 import org.graalvm.compiler.nodes.FixedWithNextNode;
47 import org.graalvm.compiler.nodes.GuardNode;
48 import org.graalvm.compiler.nodes.IfNode;
49 import org.graalvm.compiler.nodes.LogicNode;
50 import org.graalvm.compiler.nodes.LoopExitNode;
51 import org.graalvm.compiler.nodes.ProxyNode;
52 import org.graalvm.compiler.nodes.StartNode;
53 import org.graalvm.compiler.nodes.StaticDeoptimizingNode;
54 import org.graalvm.compiler.nodes.StructuredGraph;
55 import org.graalvm.compiler.nodes.ValueNode;
56 import org.graalvm.compiler.nodes.ValuePhiNode;
57 import org.graalvm.compiler.nodes.calc.CompareNode;
58 import org.graalvm.compiler.nodes.spi.LoweringProvider;
59 import org.graalvm.compiler.nodes.util.GraphUtil;
60 import org.graalvm.compiler.phases.BasePhase;
61 import org.graalvm.compiler.phases.tiers.PhaseContext;
62
63 import jdk.vm.ci.meta.Constant;
64 import jdk.vm.ci.meta.DeoptimizationAction;
65
66 /**
67 * This phase will find branches which always end with a {@link DeoptimizeNode} and replace their
68 * {@link ControlSplitNode ControlSplitNodes} with {@link FixedGuardNode FixedGuardNodes}.
69 *
70 * This is useful because {@link FixedGuardNode FixedGuardNodes} will be lowered to {@link GuardNode
71 * GuardNodes} which can later be optimized more aggressively than control-flow constructs.
72 *
73 * This is currently only done for branches that start from a {@link IfNode}. If it encounters a
74 * branch starting at an other kind of {@link ControlSplitNode}, it will only bring the
75 * {@link DeoptimizeNode} as close to the {@link ControlSplitNode} as possible.
76 *
77 */
78 public class ConvertDeoptimizeToGuardPhase extends BasePhase<PhaseContext> {
79 @Override
80 @SuppressWarnings("try")
81 protected void run(final StructuredGraph graph, PhaseContext context) {
82 assert graph.hasValueProxies() : "ConvertDeoptimizeToGuardPhase always creates proxies";
83 assert !graph.getGuardsStage().areFrameStatesAtDeopts() : graph.getGuardsStage();
84
85 for (DeoptimizeNode d : graph.getNodes(DeoptimizeNode.TYPE)) {
86 assert d.isAlive();
87 if (d.getAction() == DeoptimizationAction.None) {
88 continue;
89 }
90 try (DebugCloseable closable = d.withNodeSourcePosition()) {
91 propagateFixed(d, d, context != null ? context.getLowerer() : null);
92 }
93 }
94
95 if (context != null) {
96 for (FixedGuardNode fixedGuard : graph.getNodes(FixedGuardNode.TYPE)) {
97 try (DebugCloseable closable = fixedGuard.withNodeSourcePosition()) {
98 trySplitFixedGuard(fixedGuard, context);
99 }
100 }
101 }
102
103 new DeadCodeEliminationPhase(Optional).apply(graph);
104 }
105
106 private void trySplitFixedGuard(FixedGuardNode fixedGuard, PhaseContext context) {
107 LogicNode condition = fixedGuard.condition();
108 if (condition instanceof CompareNode) {
109 CompareNode compare = (CompareNode) condition;
110 ValueNode x = compare.getX();
111 ValuePhiNode xPhi = (x instanceof ValuePhiNode) ? (ValuePhiNode) x : null;
112 if (x instanceof ConstantNode || xPhi != null) {
113 ValueNode y = compare.getY();
114 ValuePhiNode yPhi = (y instanceof ValuePhiNode) ? (ValuePhiNode) y : null;
115 if (y instanceof ConstantNode || yPhi != null) {
116 processFixedGuardAndPhis(fixedGuard, context, compare, x, xPhi, y, yPhi);
117 }
118 }
119 }
120 }
121
122 private void processFixedGuardAndPhis(FixedGuardNode fixedGuard, PhaseContext context, CompareNode compare, ValueNode x, ValuePhiNode xPhi, ValueNode y, ValuePhiNode yPhi) {
123 AbstractBeginNode pred = AbstractBeginNode.prevBegin(fixedGuard);
124 if (pred instanceof AbstractMergeNode) {
125 AbstractMergeNode merge = (AbstractMergeNode) pred;
126 if (xPhi != null && xPhi.merge() != merge) {
127 return;
128 }
129 if (yPhi != null && yPhi.merge() != merge) {
130 return;
131 }
132
133 processFixedGuardAndMerge(fixedGuard, context, compare, x, xPhi, y, yPhi, merge);
134 }
135 }
136
137 @SuppressWarnings("try")
138 private void processFixedGuardAndMerge(FixedGuardNode fixedGuard, PhaseContext context, CompareNode compare, ValueNode x, ValuePhiNode xPhi, ValueNode y, ValuePhiNode yPhi,
139 AbstractMergeNode merge) {
140 List<EndNode> mergePredecessors = merge.cfgPredecessors().snapshot();
141 for (int i = 0; i < mergePredecessors.size(); ++i) {
142 AbstractEndNode mergePredecessor = mergePredecessors.get(i);
143 if (!mergePredecessor.isAlive()) {
144 break;
145 }
146 Constant xs;
147 if (xPhi == null) {
148 xs = x.asConstant();
149 } else {
150 xs = xPhi.valueAt(mergePredecessor).asConstant();
151 }
152 Constant ys;
153 if (yPhi == null) {
154 ys = y.asConstant();
155 } else {
156 ys = yPhi.valueAt(mergePredecessor).asConstant();
157 }
158 if (xs != null && ys != null && compare.condition().foldCondition(xs, ys, context.getConstantReflection(), compare.unorderedIsTrue()) == fixedGuard.isNegated()) {
159 try (DebugCloseable position = fixedGuard.withNodeSourcePosition()) {
160 propagateFixed(mergePredecessor, fixedGuard, context.getLowerer());
161 }
162 }
163 }
164 }
165
166 @SuppressWarnings("try")
167 private void propagateFixed(FixedNode from, StaticDeoptimizingNode deopt, LoweringProvider loweringProvider) {
168 Node current = from;
169 while (current != null) {
170 if (GraalOptions.GuardPriorities.getValue(from.getOptions()) && current instanceof FixedGuardNode) {
171 FixedGuardNode otherGuard = (FixedGuardNode) current;
172 if (otherGuard.computePriority().isHigherPriorityThan(deopt.computePriority())) {
173 moveAsDeoptAfter(otherGuard, deopt);
174 return;
175 }
176 } else if (current instanceof AbstractBeginNode) {
177 if (current instanceof AbstractMergeNode) {
178 AbstractMergeNode mergeNode = (AbstractMergeNode) current;
179 FixedNode next = mergeNode.next();
180 while (mergeNode.isAlive()) {
181 AbstractEndNode end = mergeNode.forwardEnds().first();
182 propagateFixed(end, deopt, loweringProvider);
183 }
184 if (next.isAlive()) {
185 propagateFixed(next, deopt, loweringProvider);
186 }
187 return;
188 } else if (current.predecessor() instanceof IfNode) {
189 IfNode ifNode = (IfNode) current.predecessor();
190 // Prioritize the source position of the IfNode
191 try (DebugCloseable closable = ifNode.withNodeSourcePosition()) {
192 StructuredGraph graph = ifNode.graph();
193 LogicNode conditionNode = ifNode.condition();
194 boolean negateGuardCondition = current == ifNode.trueSuccessor();
195 NodeSourcePosition survivingSuccessorPosition = negateGuardCondition ? ifNode.falseSuccessor().getNodeSourcePosition() : ifNode.trueSuccessor().getNodeSourcePosition();
196 FixedGuardNode guard = graph.add(
197 new FixedGuardNode(conditionNode, deopt.getReason(), deopt.getAction(), deopt.getSpeculation(), negateGuardCondition, survivingSuccessorPosition));
198
199 FixedWithNextNode pred = (FixedWithNextNode) ifNode.predecessor();
200 AbstractBeginNode survivingSuccessor;
201 if (negateGuardCondition) {
202 survivingSuccessor = ifNode.falseSuccessor();
203 } else {
204 survivingSuccessor = ifNode.trueSuccessor();
205 }
206 graph.removeSplitPropagate(ifNode, survivingSuccessor);
207
208 Node newGuard = guard;
209 if (survivingSuccessor instanceof LoopExitNode) {
210 newGuard = ProxyNode.forGuard(guard, (LoopExitNode) survivingSuccessor, graph);
211 }
212 survivingSuccessor.replaceAtUsages(InputType.Guard, newGuard);
213
214 graph.getDebug().log("Converting deopt on %-5s branch of %s to guard for remaining branch %s.", negateGuardCondition, ifNode, survivingSuccessor);
215 FixedNode next = pred.next();
216 pred.setNext(guard);
217 guard.setNext(next);
218 SimplifierTool simplifierTool = GraphUtil.getDefaultSimplifier(null, null, null, false, graph.getAssumptions(), graph.getOptions(), loweringProvider);
219 survivingSuccessor.simplify(simplifierTool);
220 return;
221 }
222 } else if (current.predecessor() == null || current.predecessor() instanceof ControlSplitNode) {
223 assert current.predecessor() != null || (current instanceof StartNode && current == ((AbstractBeginNode) current).graph().start());
224 moveAsDeoptAfter((AbstractBeginNode) current, deopt);
225 return;
226 }
227 }
228 current = current.predecessor();
229 }
230 }
231
232 @SuppressWarnings("try")
233 private static void moveAsDeoptAfter(FixedWithNextNode node, StaticDeoptimizingNode deopt) {
234 try (DebugCloseable position = deopt.asNode().withNodeSourcePosition()) {
235 FixedNode next = node.next();
236 if (next != deopt.asNode()) {
237 node.setNext(node.graph().add(new DeoptimizeNode(deopt.getAction(), deopt.getReason(), deopt.getSpeculation())));
238 GraphUtil.killCFG(next);
239 }
240 }
241 }
242 }