001/*
002 * Copyright (c) 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.graph;
024
025import java.util.*;
026import java.util.function.*;
027
028import com.oracle.graal.debug.*;
029
030import com.oracle.graal.graph.*;
031import com.oracle.graal.nodes.*;
032
033/**
034 * Compute probabilities for fixed nodes on the fly and cache them at {@link AbstractBeginNode}s.
035 */
036public class FixedNodeProbabilityCache implements ToDoubleFunction<FixedNode> {
037
038    private static final DebugMetric metricComputeNodeProbability = Debug.metric("ComputeNodeProbability");
039
040    private final Map<FixedNode, Double> cache = Node.newIdentityMap();
041
042    /**
043     * <p>
044     * Given a {@link FixedNode} this method finds the most immediate {@link AbstractBeginNode}
045     * preceding it that either:
046     * <ul>
047     * <li>has no predecessor (ie, the begin-node is a merge, in particular a loop-begin, or the
048     * start-node)</li>
049     * <li>has a control-split predecessor</li>
050     * </ul>
051     * </p>
052     *
053     * <p>
054     * The thus found {@link AbstractBeginNode} is equi-probable with the {@link FixedNode} it was
055     * obtained from. When computed for the first time (afterwards a cache lookup returns it) that
056     * probability is computed as follows, again depending on the begin-node's predecessor:
057     * <ul>
058     * <li>No predecessor. In this case the begin-node is either:</li>
059     * <ul>
060     * <li>a merge-node, whose probability adds up those of its forward-ends</li>
061     * <li>a loop-begin, with probability as above multiplied by the loop-frequency</li>
062     * </ul>
063     * <li>Control-split predecessor: probability of the branch times that of the control-split</li>
064     * </ul>
065     * </p>
066     *
067     * <p>
068     * As an exception to all the above, a probability of 1 is assumed for a {@link FixedNode} that
069     * appears to be dead-code (ie, lacks a predecessor).
070     * </p>
071     *
072     */
073    public double applyAsDouble(FixedNode node) {
074        assert node != null;
075        metricComputeNodeProbability.increment();
076
077        FixedNode current = findBegin(node);
078        if (current == null) {
079            // this should only appear for dead code
080            return 1D;
081        }
082
083        assert current instanceof AbstractBeginNode;
084        Double cachedValue = cache.get(current);
085        if (cachedValue != null) {
086            return cachedValue;
087        }
088
089        double probability = 0.0;
090        if (current.predecessor() == null) {
091            if (current instanceof AbstractMergeNode) {
092                probability = handleMerge(current, probability);
093            } else {
094                assert current instanceof StartNode;
095                probability = 1D;
096            }
097        } else {
098            ControlSplitNode split = (ControlSplitNode) current.predecessor();
099            probability = split.probability((AbstractBeginNode) current) * applyAsDouble(split);
100        }
101        assert !Double.isNaN(probability) && !Double.isInfinite(probability) : current + " " + probability;
102        cache.put(current, probability);
103        return probability;
104    }
105
106    private double handleMerge(FixedNode current, double probability) {
107        double result = probability;
108        AbstractMergeNode currentMerge = (AbstractMergeNode) current;
109        NodeInputList<EndNode> currentForwardEnds = currentMerge.forwardEnds();
110        /*
111         * Use simple iteration instead of streams, since the stream infrastructure adds many frames
112         * which causes the recursion to overflow the stack earlier than it would otherwise.
113         */
114        for (AbstractEndNode endNode : currentForwardEnds) {
115            result += applyAsDouble(endNode);
116        }
117        if (current instanceof LoopBeginNode) {
118            result *= ((LoopBeginNode) current).loopFrequency();
119        }
120        return result;
121    }
122
123    private static FixedNode findBegin(FixedNode node) {
124        FixedNode current = node;
125        while (true) {
126            assert current != null;
127            Node predecessor = current.predecessor();
128            if (current instanceof AbstractBeginNode) {
129                if (predecessor == null) {
130                    break;
131                } else if (predecessor.successors().count() != 1) {
132                    assert predecessor instanceof ControlSplitNode : "a FixedNode with multiple successors needs to be a ControlSplitNode: " + current + " / " + predecessor;
133                    break;
134                }
135            } else if (predecessor == null) {
136                current = null;
137                break;
138            }
139            current = (FixedNode) predecessor;
140        }
141        return current;
142    }
143}