1 /* 2 * Copyright (c) 2011, 2019, 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 }