Mercurial > hg > truffle

annotate graal/com.oracle.graal.java/src/com/oracle/graal/java/ComputeLoopFrequenciesClosure.java @ 18995:a2cb19764970

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Rename MergeNode to AbstractMergeNode.
author Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
date Wed, 28 Jan 2015 01:04:20 +0100
parents 480bd3b1adcd
children c5d5bbf7ec6c
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
15470
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
1 /*
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
2 * Copyright (c) 2011, 2014, Oracle and/or its affiliates. All rights reserved.
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
4 *
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
5 * This code is free software; you can redistribute it and/or modify it
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
6 * under the terms of the GNU General Public License version 2 only, as
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
7 * published by the Free Software Foundation.
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
8 *
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
9 * This code is distributed in the hope that it will be useful, but WITHOUT
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
12 * version 2 for more details (a copy is included in the LICENSE file that
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
13 * accompanied this code).
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
14 *
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
15 * You should have received a copy of the GNU General Public License version
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
16 * 2 along with this work; if not, write to the Free Software Foundation,
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
18 *
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
20 * or visit www.oracle.com if you need additional information or have any
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
21 * questions.
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
22 */
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
23 package com.oracle.graal.java;
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
24
16590
c62c1e0060cc Don't allow infinite loops to explode loop frequencies
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 15470
diff changeset
25 import static com.oracle.graal.nodes.cfg.ControlFlowGraph.*;
c62c1e0060cc Don't allow infinite loops to explode loop frequencies
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 15470
diff changeset
26
15470
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
27 import java.util.*;
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
28 import java.util.stream.*;
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
29
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
30 import com.oracle.graal.nodes.*;
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
31 import com.oracle.graal.phases.graph.*;
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
32
18163
c88ab4f1f04a re-enabled Checkstyle with the release of 6.0 that supports Java 8; fixed existing Checkstyle warnings
Doug Simon <doug.simon@oracle.com>
parents: 16838
diff changeset
33 public final class ComputeLoopFrequenciesClosure extends ReentrantNodeIterator.NodeIteratorClosure<Double> {
15470
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
34
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
35 private static final ComputeLoopFrequenciesClosure INSTANCE = new ComputeLoopFrequenciesClosure();
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
36
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
37 private ComputeLoopFrequenciesClosure() {
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
38 // nothing to do
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
39 }
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
40
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
41 @Override
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
42 protected Double processNode(FixedNode node, Double currentState) {
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
43 // normal nodes never change the probability of a path
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
44 return currentState;
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
45 }
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
46
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
47 @Override
18995
a2cb19764970 Rename MergeNode to AbstractMergeNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18993
diff changeset
48 protected Double merge(AbstractMergeNode merge, List<Double> states) {
15470
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
49 // a merge has the sum of all predecessor probabilities
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
50 return states.stream().collect(Collectors.summingDouble(d -> d));
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
51 }
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
52
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
53 @Override
18993
480bd3b1adcd Rename BeginNode => AbstractBeginNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18163
diff changeset
54 protected Double afterSplit(AbstractBeginNode node, Double oldState) {
15470
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
55 // a control split splits up the probability
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
56 ControlSplitNode split = (ControlSplitNode) node.predecessor();
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
57 return oldState * split.probability(node);
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
58 }
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
59
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
60 @Override
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
61 protected Map<LoopExitNode, Double> processLoop(LoopBeginNode loop, Double initialState) {
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
62 Map<LoopExitNode, Double> exitStates = ReentrantNodeIterator.processLoop(this, loop, 1D).exitStates;
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
63
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
64 double exitProbability = exitStates.values().stream().mapToDouble(d -> d).sum();
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
65 assert exitProbability <= 1D && exitProbability >= 0D;
16590
c62c1e0060cc Don't allow infinite loops to explode loop frequencies
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 15470
diff changeset
66 if (exitProbability < MIN_PROBABILITY) {
c62c1e0060cc Don't allow infinite loops to explode loop frequencies
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 15470
diff changeset
67 exitProbability = MIN_PROBABILITY;
15470
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
68 }
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
69 double loopFrequency = 1D / exitProbability;
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
70 loop.setLoopFrequency(loopFrequency);
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
71
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
72 double adjustmentFactor = initialState * loopFrequency;
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
73 exitStates.replaceAll((exitNode, probability) -> multiplySaturate(probability, adjustmentFactor));
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
74
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
75 return exitStates;
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
76 }
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
77
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
78 /**
16590
c62c1e0060cc Don't allow infinite loops to explode loop frequencies
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 15470
diff changeset
79 * Multiplies a and b and saturates the result to 1/{@link #MIN_PROBABILITY}.
15470
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
80 *
16590
c62c1e0060cc Don't allow infinite loops to explode loop frequencies
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 15470
diff changeset
81 * @return a times b saturated to 1/{@link #MIN_PROBABILITY}
15470
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
82 */
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
83 public static double multiplySaturate(double a, double b) {
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
84 double r = a * b;
16590
c62c1e0060cc Don't allow infinite loops to explode loop frequencies
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 15470
diff changeset
85 if (r > 1 / MIN_PROBABILITY) {
c62c1e0060cc Don't allow infinite loops to explode loop frequencies
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 15470
diff changeset
86 return 1 / MIN_PROBABILITY;
15470
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
87 }
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
88 return r;
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
89 }
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
90
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
91 /**
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
92 * Computes the frequencies of all loops in the given graph. This is done by performing a
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
93 * reverse postorder iteration and computing the probability of all fixed nodes. The combined
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
94 * probability of all exits of a loop can be used to compute the loop's expected frequency.
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
95 */
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
96 public static void compute(StructuredGraph graph) {
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
97 if (graph.hasLoops()) {
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
98 ReentrantNodeIterator.apply(INSTANCE, graph.start(), 1D);
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
99 }
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
100 }
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
101
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents:
diff changeset
102 }