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