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.phases.common;

    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.debug.DebugCloseable;

    33 import org.graalvm.compiler.graph.Node;

    34 import org.graalvm.compiler.graph.NodeSourcePosition;

    35 import org.graalvm.compiler.graph.spi.SimplifierTool;

    36 import org.graalvm.compiler.nodeinfo.InputType;

    37 import org.graalvm.compiler.nodes.AbstractBeginNode;

    38 import org.graalvm.compiler.nodes.AbstractEndNode;

    39 import org.graalvm.compiler.nodes.AbstractMergeNode;

    40 import org.graalvm.compiler.nodes.ConstantNode;

    41 import org.graalvm.compiler.nodes.ControlSplitNode;

    42 import org.graalvm.compiler.nodes.DeoptimizeNode;

    43 import org.graalvm.compiler.nodes.EndNode;

    44 import org.graalvm.compiler.nodes.FixedGuardNode;

    45 import org.graalvm.compiler.nodes.FixedNode;

    46 import org.graalvm.compiler.nodes.FixedWithNextNode;

    47 import org.graalvm.compiler.nodes.GuardNode;

    48 import org.graalvm.compiler.nodes.IfNode;

    49 import org.graalvm.compiler.nodes.LogicNode;

    50 import org.graalvm.compiler.nodes.LoopExitNode;

    51 import org.graalvm.compiler.nodes.ProxyNode;

    52 import org.graalvm.compiler.nodes.StartNode;

    53 import org.graalvm.compiler.nodes.StaticDeoptimizingNode;

    54 import org.graalvm.compiler.nodes.StructuredGraph;

    55 import org.graalvm.compiler.nodes.ValueNode;

    56 import org.graalvm.compiler.nodes.ValuePhiNode;

    57 import org.graalvm.compiler.nodes.calc.CompareNode;

    58 import org.graalvm.compiler.nodes.spi.LoweringProvider;

    59 import org.graalvm.compiler.nodes.util.GraphUtil;

    60 import org.graalvm.compiler.phases.BasePhase;

    61 import org.graalvm.compiler.phases.tiers.PhaseContext;

    62 

    63 import jdk.vm.ci.meta.Constant;

    64 import jdk.vm.ci.meta.DeoptimizationAction;

    65 

    66 /**

    67  * This phase will find branches which always end with a {@link DeoptimizeNode} and replace their

    68  * {@link ControlSplitNode ControlSplitNodes} with {@link FixedGuardNode FixedGuardNodes}.

    69  *

    70  * This is useful because {@link FixedGuardNode FixedGuardNodes} will be lowered to {@link GuardNode

    71  * GuardNodes} which can later be optimized more aggressively than control-flow constructs.

    72  *

    73  * This is currently only done for branches that start from a {@link IfNode}. If it encounters a

    74  * branch starting at an other kind of {@link ControlSplitNode}, it will only bring the

    75  * {@link DeoptimizeNode} as close to the {@link ControlSplitNode} as possible.

    76  *

    77  */

    78 public class ConvertDeoptimizeToGuardPhase extends BasePhase<PhaseContext> {

    79     @Override

    80     @SuppressWarnings("try")

    81     protected void run(final StructuredGraph graph, PhaseContext context) {

    82         assert graph.hasValueProxies() : "ConvertDeoptimizeToGuardPhase always creates proxies";

    83         assert !graph.getGuardsStage().areFrameStatesAtDeopts() : graph.getGuardsStage();

    84 

    85         for (DeoptimizeNode d : graph.getNodes(DeoptimizeNode.TYPE)) {

    86             assert d.isAlive();

    87             if (d.getAction() == DeoptimizationAction.None) {

    88                 continue;

    89             }

    90             try (DebugCloseable closable = d.withNodeSourcePosition()) {

    91                 propagateFixed(d, d, context != null ? context.getLowerer() : null);

    92             }

    93         }

    94 

    95         if (context != null) {

    96             for (FixedGuardNode fixedGuard : graph.getNodes(FixedGuardNode.TYPE)) {

    97                 try (DebugCloseable closable = fixedGuard.withNodeSourcePosition()) {

    98                     trySplitFixedGuard(fixedGuard, context);

    99                 }

   100             }

   101         }

   102 

   103         new DeadCodeEliminationPhase(Optional).apply(graph);

   104     }

   105 

   106     private void trySplitFixedGuard(FixedGuardNode fixedGuard, PhaseContext context) {

   107         LogicNode condition = fixedGuard.condition();

   108         if (condition instanceof CompareNode) {

   109             CompareNode compare = (CompareNode) condition;

   110             ValueNode x = compare.getX();

   111             ValuePhiNode xPhi = (x instanceof ValuePhiNode) ? (ValuePhiNode) x : null;

   112             if (x instanceof ConstantNode || xPhi != null) {

   113                 ValueNode y = compare.getY();

   114                 ValuePhiNode yPhi = (y instanceof ValuePhiNode) ? (ValuePhiNode) y : null;

   115                 if (y instanceof ConstantNode || yPhi != null) {

   116                     processFixedGuardAndPhis(fixedGuard, context, compare, x, xPhi, y, yPhi);

   117                 }

   118             }

   119         }

   120     }

   121 

   122     private void processFixedGuardAndPhis(FixedGuardNode fixedGuard, PhaseContext context, CompareNode compare, ValueNode x, ValuePhiNode xPhi, ValueNode y, ValuePhiNode yPhi) {

   123         AbstractBeginNode pred = AbstractBeginNode.prevBegin(fixedGuard);

   124         if (pred instanceof AbstractMergeNode) {

   125             AbstractMergeNode merge = (AbstractMergeNode) pred;

   126             if (xPhi != null && xPhi.merge() != merge) {

   127                 return;

   128             }

   129             if (yPhi != null && yPhi.merge() != merge) {

   130                 return;

   131             }

   132 

   133             processFixedGuardAndMerge(fixedGuard, context, compare, x, xPhi, y, yPhi, merge);

   134         }

   135     }

   136 

   137     @SuppressWarnings("try")

   138     private void processFixedGuardAndMerge(FixedGuardNode fixedGuard, PhaseContext context, CompareNode compare, ValueNode x, ValuePhiNode xPhi, ValueNode y, ValuePhiNode yPhi,

   139                     AbstractMergeNode merge) {

   140         List<EndNode> mergePredecessors = merge.cfgPredecessors().snapshot();

   141         for (int i = 0; i < mergePredecessors.size(); ++i) {

   142             AbstractEndNode mergePredecessor = mergePredecessors.get(i);

   143             if (!mergePredecessor.isAlive()) {

   144                 break;

   145             }

   146             Constant xs;

   147             if (xPhi == null) {

   148                 xs = x.asConstant();

   149             } else {

   150                 xs = xPhi.valueAt(mergePredecessor).asConstant();

   151             }

   152             Constant ys;

   153             if (yPhi == null) {

   154                 ys = y.asConstant();

   155             } else {

   156                 ys = yPhi.valueAt(mergePredecessor).asConstant();

   157             }

   158             if (xs != null && ys != null && compare.condition().foldCondition(xs, ys, context.getConstantReflection(), compare.unorderedIsTrue()) == fixedGuard.isNegated()) {

   159                 try (DebugCloseable position = fixedGuard.withNodeSourcePosition()) {

   160                     propagateFixed(mergePredecessor, fixedGuard, context.getLowerer());

   161                 }

   162             }

   163         }

   164     }

   165 

   166     @SuppressWarnings("try")

   167     private void propagateFixed(FixedNode from, StaticDeoptimizingNode deopt, LoweringProvider loweringProvider) {

   168         Node current = from;

   169         while (current != null) {

   170             if (GraalOptions.GuardPriorities.getValue(from.getOptions()) && current instanceof FixedGuardNode) {

   171                 FixedGuardNode otherGuard = (FixedGuardNode) current;

   172                 if (otherGuard.computePriority().isHigherPriorityThan(deopt.computePriority())) {

   173                     moveAsDeoptAfter(otherGuard, deopt);

   174                     return;

   175                 }

   176             } else if (current instanceof AbstractBeginNode) {

   177                 if (current instanceof AbstractMergeNode) {

   178                     AbstractMergeNode mergeNode = (AbstractMergeNode) current;

   179                     FixedNode next = mergeNode.next();

   180                     while (mergeNode.isAlive()) {

   181                         AbstractEndNode end = mergeNode.forwardEnds().first();

   182                         propagateFixed(end, deopt, loweringProvider);

   183                     }

   184                     if (next.isAlive()) {

   185                         propagateFixed(next, deopt, loweringProvider);

   186                     }

   187                     return;

   188                 } else if (current.predecessor() instanceof IfNode) {

   189                     IfNode ifNode = (IfNode) current.predecessor();

   190                     // Prioritize the source position of the IfNode

   191                     try (DebugCloseable closable = ifNode.withNodeSourcePosition()) {

   192                         StructuredGraph graph = ifNode.graph();

   193                         LogicNode conditionNode = ifNode.condition();

   194                         boolean negateGuardCondition = current == ifNode.trueSuccessor();

   195                         NodeSourcePosition survivingSuccessorPosition = negateGuardCondition ? ifNode.falseSuccessor().getNodeSourcePosition() : ifNode.trueSuccessor().getNodeSourcePosition();

   196                         FixedGuardNode guard = graph.add(

   197                                         new FixedGuardNode(conditionNode, deopt.getReason(), deopt.getAction(), deopt.getSpeculation(), negateGuardCondition, survivingSuccessorPosition));

   198 

   199                         FixedWithNextNode pred = (FixedWithNextNode) ifNode.predecessor();

   200                         AbstractBeginNode survivingSuccessor;

   201                         if (negateGuardCondition) {

   202                             survivingSuccessor = ifNode.falseSuccessor();

   203                         } else {

   204                             survivingSuccessor = ifNode.trueSuccessor();

   205                         }

   206                         graph.removeSplitPropagate(ifNode, survivingSuccessor);

   207 

   208                         Node newGuard = guard;

   209                         if (survivingSuccessor instanceof LoopExitNode) {

   210                             newGuard = ProxyNode.forGuard(guard, (LoopExitNode) survivingSuccessor, graph);

   211                         }

   212                         survivingSuccessor.replaceAtUsages(InputType.Guard, newGuard);

   213 

   214                         graph.getDebug().log("Converting deopt on %-5s branch of %s to guard for remaining branch %s.", negateGuardCondition, ifNode, survivingSuccessor);

   215                         FixedNode next = pred.next();

   216                         pred.setNext(guard);

   217                         guard.setNext(next);

   218                         SimplifierTool simplifierTool = GraphUtil.getDefaultSimplifier(null, null, null, false, graph.getAssumptions(), graph.getOptions(), loweringProvider);

   219                         survivingSuccessor.simplify(simplifierTool);

   220                         return;

   221                     }

   222                 } else if (current.predecessor() == null || current.predecessor() instanceof ControlSplitNode) {

   223                     assert current.predecessor() != null || (current instanceof StartNode && current == ((AbstractBeginNode) current).graph().start());

   224                     moveAsDeoptAfter((AbstractBeginNode) current, deopt);

   225                     return;

   226                 }

   227             }

   228             current = current.predecessor();

   229         }

   230     }

   231 

   232     @SuppressWarnings("try")

   233     private static void moveAsDeoptAfter(FixedWithNextNode node, StaticDeoptimizingNode deopt) {

   234         try (DebugCloseable position = deopt.asNode().withNodeSourcePosition()) {

   235             FixedNode next = node.next();

   236             if (next != deopt.asNode()) {

   237                 node.setNext(node.graph().add(new DeoptimizeNode(deopt.getAction(), deopt.getReason(), deopt.getSpeculation())));

   238                 GraphUtil.killCFG(next);

   239             }

   240         }

   241     }

   242 }