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