001/*
002 * Copyright (c) 2013, 2013, 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 java.util.*;
026
027import com.oracle.graal.debug.*;
028
029import com.oracle.graal.graph.*;
030import com.oracle.graal.graph.iterators.*;
031import com.oracle.graal.nodes.*;
032import com.oracle.graal.nodes.cfg.*;
033import com.oracle.graal.nodes.extended.*;
034import com.oracle.graal.phases.*;
035
036public class OptimizeGuardAnchorsPhase extends Phase {
037    private static final DebugMetric metricGuardsAnchorOptimized = Debug.metric("GuardsAnchorOptimized");
038    private static final DebugMetric metricGuardsOptimizedAtSplit = Debug.metric("GuardsOptimizedAtSplit");
039
040    public static class LazyCFG {
041        private ControlFlowGraph cfg;
042        private StructuredGraph graph;
043
044        public LazyCFG(StructuredGraph graph) {
045            this.graph = graph;
046        }
047
048        public ControlFlowGraph get() {
049            if (cfg == null) {
050                cfg = ControlFlowGraph.compute(graph, true, false, true, true);
051            }
052            return cfg;
053        }
054    }
055
056    @Override
057    protected void run(StructuredGraph graph) {
058        LazyCFG cfg = new LazyCFG(graph);
059        for (AbstractBeginNode begin : graph.getNodes(AbstractBeginNode.TYPE)) {
060            if (!(begin instanceof StartNode || begin.predecessor() instanceof ControlSplitNode)) {
061                NodeIterable<GuardNode> guards = begin.guards();
062                if (guards.isNotEmpty()) {
063                    AbstractBeginNode newAnchor = computeOptimalAnchor(cfg.get(), begin);
064                    // newAnchor == begin is possible because postdominator computation assumes that
065                    // loops never end
066                    if (newAnchor != begin) {
067                        for (GuardNode guard : guards.snapshot()) {
068                            guard.setAnchor(newAnchor);
069                        }
070                        metricGuardsAnchorOptimized.increment();
071                    }
072                }
073            }
074        }
075        for (ControlSplitNode controlSplit : graph.getNodes(ControlSplitNode.TYPE)) {
076            optimizeAtControlSplit(controlSplit, cfg);
077        }
078    }
079
080    public static AbstractBeginNode getOptimalAnchor(LazyCFG cfg, AbstractBeginNode begin) {
081        if (begin instanceof StartNode || begin.predecessor() instanceof ControlSplitNode) {
082            return begin;
083        }
084        return computeOptimalAnchor(cfg.get(), begin);
085    }
086
087    private static AbstractBeginNode computeOptimalAnchor(ControlFlowGraph cfg, AbstractBeginNode begin) {
088        Block anchor = cfg.blockFor(begin);
089        while (anchor.getDominator() != null && anchor.getDominator().getPostdominator() == anchor) {
090            anchor = anchor.getDominator();
091        }
092        return anchor.getBeginNode();
093    }
094
095    private static void optimizeAtControlSplit(ControlSplitNode controlSplit, LazyCFG cfg) {
096        AbstractBeginNode successor = findMinimumUsagesSuccessor(controlSplit);
097        int successorCount = controlSplit.successors().count();
098        for (GuardNode guard : successor.guards().snapshot()) {
099            if (guard.isDeleted() || guard.condition().getUsageCount() < successorCount) {
100                continue;
101            }
102            List<GuardNode> otherGuards = new ArrayList<>(successorCount - 1);
103            HashSet<Node> successorsWithoutGuards = new HashSet<>(controlSplit.successors().count());
104            controlSplit.successors().snapshotTo(successorsWithoutGuards);
105            successorsWithoutGuards.remove(guard.getAnchor());
106            for (GuardNode conditonGuard : guard.condition().usages().filter(GuardNode.class)) {
107                if (conditonGuard != guard) {
108                    AnchoringNode conditionGuardAnchor = conditonGuard.getAnchor();
109                    if (conditionGuardAnchor.asNode().predecessor() == controlSplit && compatibleGuards(guard, conditonGuard)) {
110                        otherGuards.add(conditonGuard);
111                        successorsWithoutGuards.remove(conditionGuardAnchor);
112                    }
113                }
114            }
115
116            if (successorsWithoutGuards.isEmpty()) {
117                assert otherGuards.size() >= successorCount - 1;
118                AbstractBeginNode anchor = computeOptimalAnchor(cfg.get(), AbstractBeginNode.prevBegin(controlSplit));
119                GuardNode newGuard = controlSplit.graph().unique(new GuardNode(guard.condition(), anchor, guard.reason(), guard.action(), guard.isNegated(), guard.getSpeculation()));
120                for (GuardNode otherGuard : otherGuards) {
121                    otherGuard.replaceAndDelete(newGuard);
122                }
123                guard.replaceAndDelete(newGuard);
124                metricGuardsOptimizedAtSplit.increment();
125            }
126            otherGuards.clear();
127        }
128    }
129
130    private static boolean compatibleGuards(GuardNode guard, GuardNode conditonGuard) {
131        return conditonGuard.isNegated() == guard.isNegated() && conditonGuard.action() == guard.action() && conditonGuard.reason() == guard.reason() &&
132                        conditonGuard.getSpeculation().equals(guard.getSpeculation());
133    }
134
135    private static AbstractBeginNode findMinimumUsagesSuccessor(ControlSplitNode controlSplit) {
136        NodePosIterator successors = controlSplit.successors().iterator();
137        AbstractBeginNode min = (AbstractBeginNode) successors.next();
138        int minUsages = min.getUsageCount();
139        while (successors.hasNext()) {
140            AbstractBeginNode successor = (AbstractBeginNode) successors.next();
141            int count = successor.getUsageCount();
142            if (count < minUsages) {
143                minUsages = count;
144                min = successor;
145            }
146        }
147        return min;
148    }
149}