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.Debug; 30 import org.graalvm.compiler.debug.DebugCloseable; 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 if (deoptBegin instanceof AbstractMergeNode) { 173 AbstractMergeNode mergeNode = (AbstractMergeNode) deoptBegin; 174 Debug.log("Visiting %s", mergeNode); 175 FixedNode next = mergeNode.next(); 176 while (mergeNode.isAlive()) { 177 AbstractEndNode end = mergeNode.forwardEnds().first(); 178 AbstractBeginNode newBeginNode = AbstractBeginNode.prevBegin(end); 179 visitDeoptBegin(newBeginNode, deoptAction, deoptReason, speculation, graph, loweringProvider); 180 } 181 assert next.isAlive(); 182 AbstractBeginNode newBeginNode = AbstractBeginNode.prevBegin(next); 183 visitDeoptBegin(newBeginNode, deoptAction, deoptReason, speculation, graph, loweringProvider); 184 return; 185 } else if (deoptBegin.predecessor() instanceof IfNode) { 186 IfNode ifNode = (IfNode) deoptBegin.predecessor(); 187 LogicNode conditionNode = ifNode.condition(); 188 FixedGuardNode guard = graph.add(new FixedGuardNode(conditionNode, deoptReason, deoptAction, speculation, deoptBegin == ifNode.trueSuccessor())); 189 FixedWithNextNode pred = (FixedWithNextNode) ifNode.predecessor(); 190 AbstractBeginNode survivingSuccessor; 191 if (deoptBegin == ifNode.trueSuccessor()) { 192 survivingSuccessor = ifNode.falseSuccessor(); 193 } else { 194 survivingSuccessor = ifNode.trueSuccessor(); 195 } 196 graph.removeSplitPropagate(ifNode, survivingSuccessor); 197 198 Node newGuard = guard; 199 if (survivingSuccessor instanceof LoopExitNode) { 200 newGuard = ProxyNode.forGuard(guard, (LoopExitNode) survivingSuccessor, graph); 201 } 202 survivingSuccessor.replaceAtUsages(InputType.Guard, newGuard); 203 204 Debug.log("Converting deopt on %-5s branch of %s to guard for remaining branch %s.", deoptBegin == ifNode.trueSuccessor() ? "true" : "false", ifNode, survivingSuccessor); 205 FixedNode next = pred.next(); 206 pred.setNext(guard); 207 guard.setNext(next); 208 SimplifierTool simplifierTool = GraphUtil.getDefaultSimplifier(null, null, null, false, graph.getAssumptions(), graph.getOptions(), loweringProvider); 209 survivingSuccessor.simplify(simplifierTool); 210 return; 211 } 212 213 // We could not convert the control split - at least cut off control flow after the split. 214 FixedWithNextNode deoptPred = deoptBegin; 215 FixedNode next = deoptPred.next(); 216 217 if (!(next instanceof DeoptimizeNode)) { 218 DeoptimizeNode newDeoptNode = graph.add(new DeoptimizeNode(deoptAction, deoptReason, speculation)); 219 deoptPred.setNext(newDeoptNode); 220 assert deoptPred == newDeoptNode.predecessor(); 221 GraphUtil.killCFG(next); 222 } 223 } 224 }