001/*
002 * Copyright (c) 2011, 2014, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.phases.common;
024
025import static com.oracle.graal.phases.common.DeadCodeEliminationPhase.Optionality.*;
026
027import java.util.*;
028
029import com.oracle.graal.debug.*;
030import jdk.internal.jvmci.meta.*;
031
032import com.oracle.graal.graph.*;
033import com.oracle.graal.graph.spi.*;
034import com.oracle.graal.nodeinfo.*;
035import com.oracle.graal.nodes.*;
036import com.oracle.graal.nodes.calc.*;
037import com.oracle.graal.nodes.util.*;
038import com.oracle.graal.phases.*;
039import com.oracle.graal.phases.tiers.*;
040
041/**
042 * This phase will find branches which always end with a {@link DeoptimizeNode} and replace their
043 * {@link ControlSplitNode ControlSplitNodes} with {@link FixedGuardNode FixedGuardNodes}.
044 *
045 * This is useful because {@link FixedGuardNode FixedGuardNodes} will be lowered to
046 * {@link GuardNode GuardNodes} which can later be optimized more aggressively than control-flow
047 * constructs.
048 *
049 * This is currently only done for branches that start from a {@link IfNode}. If it encounters a
050 * branch starting at an other kind of {@link ControlSplitNode}, it will only bring the
051 * {@link DeoptimizeNode} as close to the {@link ControlSplitNode} as possible.
052 *
053 */
054public class ConvertDeoptimizeToGuardPhase extends BasePhase<PhaseContext> {
055    private SimplifierTool simplifierTool = GraphUtil.getDefaultSimplifier(null, null, false);
056
057    private static AbstractBeginNode findBeginNode(FixedNode startNode) {
058        return GraphUtil.predecessorIterable(startNode).filter(AbstractBeginNode.class).first();
059    }
060
061    @Override
062    protected void run(final StructuredGraph graph, PhaseContext context) {
063        assert graph.hasValueProxies() : "ConvertDeoptimizeToGuardPhase always creates proxies";
064        if (graph.getNodes(DeoptimizeNode.TYPE).isEmpty()) {
065            return;
066        }
067        for (DeoptimizeNode d : graph.getNodes(DeoptimizeNode.TYPE)) {
068            assert d.isAlive();
069            visitDeoptBegin(AbstractBeginNode.prevBegin(d), d.action(), d.reason(), d.getSpeculation(), graph);
070        }
071
072        if (context != null) {
073            for (FixedGuardNode fixedGuard : graph.getNodes(FixedGuardNode.TYPE)) {
074                trySplitFixedGuard(fixedGuard, context);
075            }
076        }
077
078        new DeadCodeEliminationPhase(Optional).apply(graph);
079    }
080
081    private void trySplitFixedGuard(FixedGuardNode fixedGuard, PhaseContext context) {
082        LogicNode condition = fixedGuard.condition();
083        if (condition instanceof CompareNode) {
084            CompareNode compare = (CompareNode) condition;
085            ValueNode x = compare.getX();
086            ValuePhiNode xPhi = (x instanceof ValuePhiNode) ? (ValuePhiNode) x : null;
087            if (x instanceof ConstantNode || xPhi != null) {
088                ValueNode y = compare.getY();
089                ValuePhiNode yPhi = (y instanceof ValuePhiNode) ? (ValuePhiNode) y : null;
090                if (y instanceof ConstantNode || yPhi != null) {
091                    processFixedGuardAndPhis(fixedGuard, context, compare, x, xPhi, y, yPhi);
092                }
093            }
094        }
095    }
096
097    private void processFixedGuardAndPhis(FixedGuardNode fixedGuard, PhaseContext context, CompareNode compare, ValueNode x, ValuePhiNode xPhi, ValueNode y, ValuePhiNode yPhi) {
098        AbstractBeginNode pred = AbstractBeginNode.prevBegin(fixedGuard);
099        if (pred instanceof AbstractMergeNode) {
100            AbstractMergeNode merge = (AbstractMergeNode) pred;
101            if (xPhi != null && xPhi.merge() != merge) {
102                return;
103            }
104            if (yPhi != null && yPhi.merge() != merge) {
105                return;
106            }
107
108            processFixedGuardAndMerge(fixedGuard, context, compare, x, xPhi, y, yPhi, merge);
109        }
110    }
111
112    private void processFixedGuardAndMerge(FixedGuardNode fixedGuard, PhaseContext context, CompareNode compare, ValueNode x, ValuePhiNode xPhi, ValueNode y, ValuePhiNode yPhi, AbstractMergeNode merge) {
113        List<EndNode> mergePredecessors = merge.cfgPredecessors().snapshot();
114        for (int i = 0; i < mergePredecessors.size(); ++i) {
115            AbstractEndNode mergePredecessor = mergePredecessors.get(i);
116            if (!mergePredecessor.isAlive()) {
117                break;
118            }
119            Constant xs;
120            if (xPhi == null) {
121                xs = x.asConstant();
122            } else {
123                xs = xPhi.valueAt(mergePredecessor).asConstant();
124            }
125            Constant ys;
126            if (yPhi == null) {
127                ys = y.asConstant();
128            } else {
129                ys = yPhi.valueAt(mergePredecessor).asConstant();
130            }
131            if (xs != null && ys != null && compare.condition().foldCondition(xs, ys, context.getConstantReflection(), compare.unorderedIsTrue()) == fixedGuard.isNegated()) {
132                visitDeoptBegin(AbstractBeginNode.prevBegin(mergePredecessor), fixedGuard.getAction(), fixedGuard.getReason(), fixedGuard.getSpeculation(), fixedGuard.graph());
133            }
134        }
135    }
136
137    private void visitDeoptBegin(AbstractBeginNode deoptBegin, DeoptimizationAction deoptAction, DeoptimizationReason deoptReason, JavaConstant speculation, StructuredGraph graph) {
138        if (deoptBegin instanceof AbstractMergeNode) {
139            AbstractMergeNode mergeNode = (AbstractMergeNode) deoptBegin;
140            Debug.log("Visiting %s", mergeNode);
141            FixedNode next = mergeNode.next();
142            while (mergeNode.isAlive()) {
143                AbstractEndNode end = mergeNode.forwardEnds().first();
144                AbstractBeginNode newBeginNode = findBeginNode(end);
145                visitDeoptBegin(newBeginNode, deoptAction, deoptReason, speculation, graph);
146            }
147            assert next.isAlive();
148            AbstractBeginNode newBeginNode = findBeginNode(next);
149            visitDeoptBegin(newBeginNode, deoptAction, deoptReason, speculation, graph);
150            return;
151        } else if (deoptBegin.predecessor() instanceof IfNode) {
152            IfNode ifNode = (IfNode) deoptBegin.predecessor();
153            AbstractBeginNode otherBegin = ifNode.trueSuccessor();
154            LogicNode conditionNode = ifNode.condition();
155            FixedGuardNode guard = graph.add(new FixedGuardNode(conditionNode, deoptReason, deoptAction, speculation, deoptBegin == ifNode.trueSuccessor()));
156            FixedWithNextNode pred = (FixedWithNextNode) ifNode.predecessor();
157            AbstractBeginNode survivingSuccessor;
158            if (deoptBegin == ifNode.trueSuccessor()) {
159                survivingSuccessor = ifNode.falseSuccessor();
160            } else {
161                survivingSuccessor = ifNode.trueSuccessor();
162            }
163            graph.removeSplitPropagate(ifNode, survivingSuccessor);
164
165            Node newGuard = guard;
166            if (survivingSuccessor instanceof LoopExitNode) {
167                newGuard = ProxyNode.forGuard(guard, survivingSuccessor, graph);
168            }
169            survivingSuccessor.replaceAtUsages(InputType.Guard, newGuard);
170
171            Debug.log("Converting deopt on %-5s branch of %s to guard for remaining branch %s.", deoptBegin == ifNode.trueSuccessor() ? "true" : "false", ifNode, otherBegin);
172            FixedNode next = pred.next();
173            pred.setNext(guard);
174            guard.setNext(next);
175            survivingSuccessor.simplify(simplifierTool);
176            return;
177        }
178
179        // We could not convert the control split - at least cut off control flow after the split.
180        FixedWithNextNode deoptPred = deoptBegin;
181        FixedNode next = deoptPred.next();
182
183        if (!(next instanceof DeoptimizeNode)) {
184            DeoptimizeNode newDeoptNode = graph.add(new DeoptimizeNode(deoptAction, deoptReason));
185            deoptPred.setNext(newDeoptNode);
186            assert deoptPred == newDeoptNode.predecessor();
187            GraphUtil.killCFG(next);
188        }
189    }
190}