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