Mercurial > hg > truffle

annotate graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/ComputeProbabilityPhase.java @ 4706:a59fe7906f0b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
additional LoopFrequencyPropagationPolicy versions
author Lukas Stadler <lukas.stadler@jku.at>
date Mon, 27 Feb 2012 19:41:14 +0100
parents a9181b59a6bf
children c4a0a220e0f3
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1 /*
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
2 * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved.
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
4 *
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
5 * This code is free software; you can redistribute it and/or modify it
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
6 * under the terms of the GNU General Public License version 2 only, as
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
7 * published by the Free Software Foundation.
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
8 *
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
9 * This code is distributed in the hope that it will be useful, but WITHOUT
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
12 * version 2 for more details (a copy is included in the LICENSE file that
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
13 * accompanied this code).
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
14 *
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
15 * You should have received a copy of the GNU General Public License version
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
16 * 2 along with this work; if not, write to the Free Software Foundation,
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
18 *
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
20 * or visit www.oracle.com if you need additional information or have any
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
21 * questions.
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
22 */
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
23 package com.oracle.max.graal.compiler.phases;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
24
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
25 import java.util.*;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
26
4706
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
27 import com.oracle.max.criutils.*;
4569
333ce00358f4 added another inlining policy, added option to disable propagation of loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4399
diff changeset
28 import com.oracle.max.graal.compiler.*;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
29 import com.oracle.max.graal.compiler.graph.*;
4352
5a84f5548fc4 More work on new debug infrastructure.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 4142
diff changeset
30 import com.oracle.max.graal.debug.*;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
31 import com.oracle.max.graal.graph.*;
4706
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
32 import com.oracle.max.graal.lir.cfg.*;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
33 import com.oracle.max.graal.nodes.*;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
34
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
35 public class ComputeProbabilityPhase extends Phase {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
36 private static final double EPSILON = 1d / Integer.MAX_VALUE;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
37
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
38 /*
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
39 * The computation of absolute probabilities works in three steps:
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
40 *
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
41 * - The first step, "PropagateProbability", traverses the graph in post order (merges after their ends, ...) and keeps track of the "probability state".
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
42 * Whenever it encounters a ControlSplit it uses the split's probability information to divide the probability upon the successors.
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
43 * Whenever it encounters an Invoke it assumes that the exception edge is unlikely and propagates the whole probability to the normal successor.
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
44 * Whenever it encounters a Merge it sums up the probability of all predecessors.
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
45 * It also maintains a set of active loops (whose LoopBegin has been visited) and builds def/use information for the second step.
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
46 *
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
47 * - The third step propagates the loop frequencies and multiplies each FixedNode's probability with its loop frequency.
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
48 *
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
49 * TODO: add exception probability information to Invokes
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
50 */
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
51
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
52 @Override
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
53 protected void run(StructuredGraph graph) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
54 new PropagateProbability(graph.start()).apply();
4352
5a84f5548fc4 More work on new debug infrastructure.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 4142
diff changeset
55 Debug.dump(graph, "After PropagateProbability");
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
56 computeLoopFactors();
4352
5a84f5548fc4 More work on new debug infrastructure.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 4142
diff changeset
57 Debug.dump(graph, "After computeLoopFactors");
4638
a9181b59a6bf added another variant for propagating loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4614
diff changeset
58 new PropagateLoopFrequency(graph.start()).apply();
4706
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
59
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
60 ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, false, false);
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
61
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
62 if (GraalOptions.LoopFrequencyPropagationPolicy < 0) {
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
63 for (Loop loop : cfg.getLoops()) {
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
64 if (loop.parent == null) {
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
65 correctLoopFrequencies(loop);
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
66 }
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
67 }
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
68 }
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
69 }
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
70
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
71 private void correctLoopFrequencies(Loop loop) {
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
72 double frequency = ((LoopBeginNode) loop.header.getBeginNode()).loopFrequency();
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
73
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
74 double factor;
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
75 switch (GraalOptions.LoopFrequencyPropagationPolicy) {
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
76 case -1:
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
77 factor = 1 / frequency;
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
78 break;
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
79 case -2:
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
80 factor = (1 / frequency) * (Math.log(Math.E + frequency) - 1);
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
81 break;
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
82 default: throw GraalInternalError.shouldNotReachHere();
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
83 }
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
84
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
85 for (Block block : loop.blocks) {
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
86 FixedNode node = block.getBeginNode();
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
87
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
88 while (node != block.getEndNode()) {
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
89 node.setProbability(node.probability() * factor);
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
90 node = ((FixedWithNextNode) node).next();
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
91 }
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
92 }
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
93
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
94 for (Loop child : loop.children) {
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
95 correctLoopFrequencies(child);
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
96 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
97 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
98
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
99 private void computeLoopFactors() {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
100 for (LoopInfo info : loopInfos) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
101 double frequency = info.loopFrequency();
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
102 assert frequency != -1;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
103 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
104 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
105
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
106 private static boolean isRelativeProbability(double prob) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
107 // 1.01 to allow for some rounding errors
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
108 return prob >= 0 && prob <= 1.01;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
109 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
110
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
111 public static class LoopInfo {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
112 public final LoopBeginNode loopBegin;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
113
4614
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4569
diff changeset
114 public final NodeMap<Set<LoopInfo>> requires;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
115
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
116 private double loopFrequency = -1;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
117 public boolean ended = false;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
118
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
119 public LoopInfo(LoopBeginNode loopBegin) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
120 this.loopBegin = loopBegin;
4614
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4569
diff changeset
121 this.requires = loopBegin.graph().createNodeMap();
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
122 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
123
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
124 public double loopFrequency() {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
125 if (loopFrequency == -1 && ended) {
4614
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4569
diff changeset
126 double backEdgeProb = 0.0;
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4569
diff changeset
127 for (LoopEndNode le : loopBegin.loopEnds()) {
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4569
diff changeset
128 double factor = 1;
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4569
diff changeset
129 Set<LoopInfo> requireds = requires.get(le);
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4569
diff changeset
130 for (LoopInfo required : requireds) {
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4569
diff changeset
131 double t = required.loopFrequency();
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4569
diff changeset
132 if (t == -1) {
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4569
diff changeset
133 return -1;
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4569
diff changeset
134 }
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4569
diff changeset
135 factor *= t;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
136 }
4614
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4569
diff changeset
137 backEdgeProb += le.probability() * factor;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
138 }
4614
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4569
diff changeset
139 double d = backEdgeProb;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
140 if (d < EPSILON) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
141 d = EPSILON;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
142 } else if (d > loopBegin.probability() - EPSILON) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
143 d = loopBegin.probability() - EPSILON;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
144 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
145 loopFrequency = loopBegin.probability() / (loopBegin.probability() - d);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
146 loopBegin.setLoopFrequency(loopFrequency);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
147 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
148 return loopFrequency;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
149 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
150 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
151
4142
bc8527f3071c Adjust code base to new level of warnings.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 3733
diff changeset
152 public Set<LoopInfo> loopInfos = new HashSet<>();
bc8527f3071c Adjust code base to new level of warnings.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 3733
diff changeset
153 public Map<MergeNode, Set<LoopInfo>> mergeLoops = new IdentityHashMap<>();
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
154
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
155 private class Probability implements MergeableState<Probability> {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
156 public double probability;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
157 public HashSet<LoopInfo> loops;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
158 public LoopInfo loopInfo;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
159
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
160 public Probability(double probability, HashSet<LoopInfo> loops) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
161 this.probability = probability;
4142
bc8527f3071c Adjust code base to new level of warnings.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 3733
diff changeset
162 this.loops = new HashSet<>(4);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
163 if (loops != null) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
164 this.loops.addAll(loops);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
165 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
166 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
167
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
168 @Override
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
169 public Probability clone() {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
170 return new Probability(probability, loops);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
171 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
172
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
173 @Override
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
174 public boolean merge(MergeNode merge, Collection<Probability> withStates) {
4614
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4569
diff changeset
175 if (merge.forwardEndCount() > 1) {
4142
bc8527f3071c Adjust code base to new level of warnings.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 3733
diff changeset
176 HashSet<LoopInfo> intersection = new HashSet<>(loops);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
177 for (Probability other : withStates) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
178 intersection.retainAll(other.loops);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
179 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
180 for (LoopInfo info : loops) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
181 if (!intersection.contains(info)) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
182 double loopFrequency = info.loopFrequency();
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
183 if (loopFrequency == -1) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
184 return false;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
185 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
186 probability *= loopFrequency;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
187 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
188 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
189 for (Probability other : withStates) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
190 double prob = other.probability;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
191 for (LoopInfo info : other.loops) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
192 if (!intersection.contains(info)) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
193 double loopFrequency = info.loopFrequency();
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
194 if (loopFrequency == -1) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
195 return false;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
196 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
197 prob *= loopFrequency;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
198 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
199 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
200 probability += prob;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
201 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
202 loops = intersection;
4142
bc8527f3071c Adjust code base to new level of warnings.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 3733
diff changeset
203 mergeLoops.put(merge, new HashSet<>(intersection));
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
204 assert isRelativeProbability(probability) : probability;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
205 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
206 return true;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
207 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
208
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
209 @Override
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
210 public void loopBegin(LoopBeginNode loopBegin) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
211 loopInfo = new LoopInfo(loopBegin);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
212 loopInfos.add(loopInfo);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
213 loops.add(loopInfo);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
214 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
215
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
216 @Override
4614
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4569
diff changeset
217 public void loopEnds(LoopBeginNode loopBegin, Collection<Probability> loopEndStates) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
218 assert loopInfo != null;
4614
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4569
diff changeset
219 List<LoopEndNode> loopEnds = loopBegin.orderedLoopEnds();
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4569
diff changeset
220 int i = 0;
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4569
diff changeset
221 for (Probability proba : loopEndStates) {
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4569
diff changeset
222 LoopEndNode loopEnd = loopEnds.get(i++);
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4569
diff changeset
223 Set<LoopInfo> requires = loopInfo.requires.get(loopEnd);
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4569
diff changeset
224 if (requires == null) {
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4569
diff changeset
225 requires = new HashSet<>();
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4569
diff changeset
226 loopInfo.requires.set(loopEnd, requires);
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4569
diff changeset
227 }
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4569
diff changeset
228 for (LoopInfo innerLoop : proba.loops) {
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4569
diff changeset
229 if (innerLoop != loopInfo && !this.loops.contains(innerLoop)) {
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4569
diff changeset
230 requires.add(innerLoop);
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4569
diff changeset
231 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
232 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
233 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
234 loopInfo.ended = true;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
235 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
236
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
237 @Override
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
238 public void afterSplit(FixedNode node) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
239 assert node.predecessor() != null;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
240 Node pred = node.predecessor();
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
241 if (pred instanceof Invoke) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
242 Invoke x = (Invoke) pred;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
243 if (x.next() != node) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
244 probability = 0;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
245 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
246 } else {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
247 assert pred instanceof ControlSplitNode;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
248 ControlSplitNode x = (ControlSplitNode) pred;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
249 double sum = 0;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
250 for (int i = 0; i < x.blockSuccessorCount(); i++) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
251 if (x.blockSuccessor(i) == node) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
252 sum += x.probability(i);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
253 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
254 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
255 probability *= sum;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
256 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
257 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
258 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
259
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
260 private class PropagateProbability extends PostOrderNodeIterator<Probability> {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
261
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
262 public PropagateProbability(FixedNode start) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
263 super(start, new Probability(1d, null));
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
264 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
265
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
266 @Override
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
267 protected void node(FixedNode node) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
268 node.setProbability(state.probability);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
269 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
270 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
271
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
272 private class LoopCount implements MergeableState<LoopCount> {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
273 public double count;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
274
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
275 public LoopCount(double count) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
276 this.count = count;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
277 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
278
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
279 @Override
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
280 public LoopCount clone() {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
281 return new LoopCount(count);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
282 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
283
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
284 @Override
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
285 public boolean merge(MergeNode merge, Collection<LoopCount> withStates) {
4614
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4569
diff changeset
286 assert merge.forwardEndCount() == withStates.size() + 1;
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4569
diff changeset
287 if (merge.forwardEndCount() > 1) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
288 Set<LoopInfo> loops = mergeLoops.get(merge);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
289 assert loops != null;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
290 double countProd = 1;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
291 for (LoopInfo loop : loops) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
292 countProd *= loop.loopFrequency();
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
293 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
294 count = countProd;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
295 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
296 return true;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
297 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
298
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
299 @Override
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
300 public void loopBegin(LoopBeginNode loopBegin) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
301 count *= loopBegin.loopFrequency();
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
302 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
303
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
304 @Override
4614
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4569
diff changeset
305 public void loopEnds(LoopBeginNode loopBegin, Collection<LoopCount> loopEndStates) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
306 // nothing to do...
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
307 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
308
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
309 @Override
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
310 public void afterSplit(FixedNode node) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
311 // nothing to do...
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
312 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
313 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
314
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
315 private class PropagateLoopFrequency extends PostOrderNodeIterator<LoopCount> {
4706
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
316
4638
a9181b59a6bf added another variant for propagating loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4614
diff changeset
317 private final FrequencyPropagationPolicy policy;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
318
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
319 public PropagateLoopFrequency(FixedNode start) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
320 super(start, new LoopCount(1d));
4638
a9181b59a6bf added another variant for propagating loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4614
diff changeset
321 this.policy = createFrequencyPropagationPolicy();
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
322 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
323
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
324 @Override
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
325 protected void node(FixedNode node) {
4638
a9181b59a6bf added another variant for propagating loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4614
diff changeset
326 node.setProbability(policy.compute(node.probability(), state.count));
a9181b59a6bf added another variant for propagating loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4614
diff changeset
327 }
a9181b59a6bf added another variant for propagating loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4614
diff changeset
328
4706
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
329 }
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
330
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
331 private static FrequencyPropagationPolicy createFrequencyPropagationPolicy() {
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
332 switch (GraalOptions.LoopFrequencyPropagationPolicy) {
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
333 case -1:
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
334 case -2:
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
335 case 0:
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
336 return new FullFrequencyPropagation();
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
337 case 1:
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
338 return new NoFrequencyPropagation();
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
339 case 2:
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
340 return new LogarithmicFrequencyPropagation();
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
341 default:
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
342 throw GraalInternalError.shouldNotReachHere();
4638
a9181b59a6bf added another variant for propagating loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4614
diff changeset
343 }
a9181b59a6bf added another variant for propagating loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4614
diff changeset
344 }
a9181b59a6bf added another variant for propagating loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4614
diff changeset
345
a9181b59a6bf added another variant for propagating loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4614
diff changeset
346 private interface FrequencyPropagationPolicy {
4706
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
347
4638
a9181b59a6bf added another variant for propagating loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4614
diff changeset
348 double compute(double probability, double frequency);
a9181b59a6bf added another variant for propagating loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4614
diff changeset
349 }
a9181b59a6bf added another variant for propagating loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4614
diff changeset
350
a9181b59a6bf added another variant for propagating loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4614
diff changeset
351 private static class FullFrequencyPropagation implements FrequencyPropagationPolicy {
4706
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
352
4638
a9181b59a6bf added another variant for propagating loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4614
diff changeset
353 @Override
a9181b59a6bf added another variant for propagating loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4614
diff changeset
354 public double compute(double probability, double frequency) {
a9181b59a6bf added another variant for propagating loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4614
diff changeset
355 return probability * frequency;
a9181b59a6bf added another variant for propagating loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4614
diff changeset
356 }
a9181b59a6bf added another variant for propagating loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4614
diff changeset
357 }
a9181b59a6bf added another variant for propagating loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4614
diff changeset
358
a9181b59a6bf added another variant for propagating loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4614
diff changeset
359 private static class NoFrequencyPropagation implements FrequencyPropagationPolicy {
4706
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
360
4638
a9181b59a6bf added another variant for propagating loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4614
diff changeset
361 @Override
a9181b59a6bf added another variant for propagating loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4614
diff changeset
362 public double compute(double probability, double frequency) {
a9181b59a6bf added another variant for propagating loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4614
diff changeset
363 return probability;
a9181b59a6bf added another variant for propagating loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4614
diff changeset
364 }
a9181b59a6bf added another variant for propagating loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4614
diff changeset
365 }
a9181b59a6bf added another variant for propagating loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4614
diff changeset
366
a9181b59a6bf added another variant for propagating loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4614
diff changeset
367 private static class LogarithmicFrequencyPropagation implements FrequencyPropagationPolicy {
4706
a59fe7906f0b additional LoopFrequencyPropagationPolicy versions
Lukas Stadler <lukas.stadler@jku.at>
parents: 4638
diff changeset
368
4638
a9181b59a6bf added another variant for propagating loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4614
diff changeset
369 @Override
a9181b59a6bf added another variant for propagating loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4614
diff changeset
370 public double compute(double probability, double frequency) {
a9181b59a6bf added another variant for propagating loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4614
diff changeset
371 double result = Math.pow(probability, 1.5) * Math.log(frequency);
a9181b59a6bf added another variant for propagating loop frequencies
Christian Haeubl <christian.haeubl@oracle.com>
parents: 4614
diff changeset
372 return Math.max(probability, result);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
373 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
374 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
375 }