Mercurial > hg > truffle

annotate graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/walker/ComputeInliningRelevance.java @ 17450:45b45f902bed

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
removed Node generation (GRAAL-857)
author Doug Simon <doug.simon@oracle.com>
date Wed, 15 Oct 2014 15:35:33 +0200
parents 5762848171e7
children 1518c3296cc8
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
15687
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
1 /*
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
2 * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved.
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
4 *
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
5 * This code is free software; you can redistribute it and/or modify it
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
6 * under the terms of the GNU General Public License version 2 only, as
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
7 * published by the Free Software Foundation.
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
8 *
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
9 * This code is distributed in the hope that it will be useful, but WITHOUT
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
12 * version 2 for more details (a copy is included in the LICENSE file that
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
13 * accompanied this code).
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
14 *
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
15 * You should have received a copy of the GNU General Public License version
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
16 * 2 along with this work; if not, write to the Free Software Foundation,
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
18 *
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
20 * or visit www.oracle.com if you need additional information or have any
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
21 * questions.
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
22 */
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
23 package com.oracle.graal.phases.common.inlining.walker;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
24
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
25 import static com.oracle.graal.graph.util.CollectionsAccess.*;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
26
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
27 import java.util.*;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
28 import java.util.function.*;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
29
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
30 import com.oracle.graal.graph.*;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
31 import com.oracle.graal.nodes.*;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
32
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
33 import edu.umd.cs.findbugs.annotations.*;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
34
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
35 public class ComputeInliningRelevance {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
36
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
37 private static final double EPSILON = 1d / Integer.MAX_VALUE;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
38 private static final double UNINITIALIZED = -1D;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
39
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
40 private static final int EXPECTED_MIN_INVOKE_COUNT = 3;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
41 private static final int EXPECTED_INVOKE_RATIO = 20;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
42 private static final int EXPECTED_LOOP_COUNT = 3;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
43
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
44 private final StructuredGraph graph;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
45 private final ToDoubleFunction<FixedNode> nodeProbabilities;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
46
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
47 /**
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
48 * Node relevances are pre-computed for all invokes if the graph contains loops. If there are no
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
49 * loops, the computation happens lazily based on {@link #rootScope}.
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
50 */
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
51 private Map<FixedNode, Double> nodeRelevances;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
52 /**
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
53 * This scope is non-null if (and only if) there are no loops in the graph. In this case, the
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
54 * root scope is used to compute invoke relevances on the fly.
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
55 */
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
56 private Scope rootScope;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
57
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
58 public ComputeInliningRelevance(StructuredGraph graph, ToDoubleFunction<FixedNode> nodeProbabilities) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
59 this.graph = graph;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
60 this.nodeProbabilities = nodeProbabilities;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
61 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
62
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
63 /**
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
64 * Initializes or updates the relevance computation. If there are no loops within the graph,
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
65 * most computation happens lazily.
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
66 */
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
67 public void compute() {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
68 rootScope = null;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
69 if (!graph.hasLoops()) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
70 // fast path for the frequent case of no loops
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
71 rootScope = new Scope(graph.start(), null);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
72 } else {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
73 if (nodeRelevances == null) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
74 nodeRelevances = newNodeIdentityMap(EXPECTED_MIN_INVOKE_COUNT + graph.getNodeCount() / EXPECTED_INVOKE_RATIO);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
75 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
76 NodeWorkList workList = graph.createNodeWorkList();
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
77 Map<LoopBeginNode, Scope> loops = newNodeIdentityMap(EXPECTED_LOOP_COUNT);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
78
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
79 loops.put(null, new Scope(graph.start(), null));
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
80 for (LoopBeginNode loopBegin : graph.getNodes(LoopBeginNode.class)) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
81 createLoopScope(loopBegin, loops);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
82 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
83
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
84 for (Scope scope : loops.values()) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
85 scope.process(workList);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
86 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
87 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
88 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
89
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
90 public double getRelevance(Invoke invoke) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
91 if (rootScope != null) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
92 return rootScope.computeInvokeRelevance(invoke);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
93 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
94 assert nodeRelevances != null : "uninitialized relevance";
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
95 return nodeRelevances.get(invoke);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
96 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
97
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
98 /**
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
99 * Determines the parent of the given loop and creates a {@link Scope} object for each one. This
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
100 * method will call itself recursively if no {@link Scope} for the parent loop exists.
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
101 */
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
102 private Scope createLoopScope(LoopBeginNode loopBegin, Map<LoopBeginNode, Scope> loops) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
103 Scope scope = loops.get(loopBegin);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
104 if (scope == null) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
105 final Scope parent;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
106 // look for the parent scope
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
107 FixedNode current = loopBegin.forwardEnd();
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
108 while (true) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
109 if (current.predecessor() == null) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
110 if (current instanceof LoopBeginNode) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
111 // if we reach a LoopBeginNode then we're within this loop
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
112 parent = createLoopScope((LoopBeginNode) current, loops);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
113 break;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
114 } else if (current instanceof StartNode) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
115 // we're within the outermost scope
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
116 parent = loops.get(null);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
117 break;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
118 } else {
17450
45b45f902bed removed Node generation (GRAAL-857)
Doug Simon <doug.simon@oracle.com>
parents: 16982
diff changeset
119 assert current.getClass() == MergeNode.class : current;
15687
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
120 // follow any path upwards - it doesn't matter which one
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
121 current = ((MergeNode) current).forwardEndAt(0);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
122 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
123 } else if (current instanceof LoopExitNode) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
124 // if we reach a loop exit then we follow this loop and have the same parent
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
125 parent = createLoopScope(((LoopExitNode) current).loopBegin(), loops).parent;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
126 break;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
127 } else {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
128 current = (FixedNode) current.predecessor();
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
129 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
130 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
131 scope = new Scope(loopBegin, parent);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
132 loops.put(loopBegin, scope);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
133 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
134 return scope;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
135 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
136
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
137 /**
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
138 * A scope holds information for the contents of one loop or of the root of the method. It does
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
139 * not include child loops, i.e., the iteration in {@link #process(NodeWorkList)} explicitly
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
140 * excludes the nodes of child loops.
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
141 */
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
142 private class Scope {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
143 public final FixedNode start;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
144 public final Scope parent; // can be null for the outermost scope
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
145
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
146 /**
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
147 * The minimum probability along the most probable path in this scope. Computed lazily.
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
148 */
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
149 private double fastPathMinProbability = UNINITIALIZED;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
150 /**
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
151 * A measure of how important this scope is within its parent scope. Computed lazily.
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
152 */
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
153 private double scopeRelevanceWithinParent = UNINITIALIZED;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
154
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
155 public Scope(FixedNode start, Scope parent) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
156 this.start = start;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
157 this.parent = parent;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
158 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
159
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
160 @SuppressFBWarnings("FE_FLOATING_POINT_EQUALITY")
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
161 public double getFastPathMinProbability() {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
162 if (fastPathMinProbability == UNINITIALIZED) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
163 fastPathMinProbability = Math.max(EPSILON, computeFastPathMinProbability(start));
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
164 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
165 return fastPathMinProbability;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
166 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
167
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
168 /**
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
169 * Computes the ratio between the probabilities of the current scope's entry point and the
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
170 * parent scope's fastPathMinProbability.
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
171 */
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
172 @SuppressFBWarnings("FE_FLOATING_POINT_EQUALITY")
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
173 public double getScopeRelevanceWithinParent() {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
174 if (scopeRelevanceWithinParent == UNINITIALIZED) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
175 if (start instanceof LoopBeginNode) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
176 assert parent != null;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
177 double scopeEntryProbability = nodeProbabilities.applyAsDouble(((LoopBeginNode) start).forwardEnd());
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
178
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
179 scopeRelevanceWithinParent = scopeEntryProbability / parent.getFastPathMinProbability();
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
180 } else {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
181 scopeRelevanceWithinParent = 1D;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
182 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
183 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
184 return scopeRelevanceWithinParent;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
185 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
186
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
187 /**
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
188 * Processes all invokes in this scope by starting at the scope's start node and iterating
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
189 * all fixed nodes. Child loops are skipped by going from loop entries directly to the loop
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
190 * exits. Processing stops at loop exits of the current loop.
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
191 */
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
192 public void process(NodeWorkList workList) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
193 assert !(start instanceof Invoke);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
194 workList.addAll(start.successors());
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
195
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
196 for (Node current : workList) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
197 assert current.isAlive();
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
198
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
199 if (current instanceof Invoke) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
200 // process the invoke and queue its successors
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
201 nodeRelevances.put((FixedNode) current, computeInvokeRelevance((Invoke) current));
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
202 workList.addAll(current.successors());
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
203 } else if (current instanceof LoopBeginNode) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
204 // skip child loops by advancing over the loop exits
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
205 ((LoopBeginNode) current).loopExits().forEach(exit -> workList.add(exit.next()));
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
206 } else if (current instanceof LoopEndNode) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
207 // nothing to do
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
208 } else if (current instanceof LoopExitNode) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
209 // nothing to do
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
210 } else if (current instanceof FixedWithNextNode) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
211 workList.add(((FixedWithNextNode) current).next());
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
212 } else if (current instanceof EndNode) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
213 workList.add(((EndNode) current).merge());
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
214 } else if (current instanceof ControlSinkNode) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
215 // nothing to do
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
216 } else if (current instanceof ControlSplitNode) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
217 workList.addAll(current.successors());
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
218 } else {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
219 assert false : current;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
220 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
221 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
222 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
223
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
224 /**
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
225 * The relevance of an invoke is the ratio between the invoke's probability and the current
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
226 * scope's fastPathMinProbability, adjusted by scopeRelevanceWithinParent.
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
227 */
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
228 public double computeInvokeRelevance(Invoke invoke) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
229 double invokeProbability = nodeProbabilities.applyAsDouble(invoke.asNode());
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
230 assert !Double.isNaN(invokeProbability);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
231
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
232 double relevance = (invokeProbability / getFastPathMinProbability()) * Math.min(1.0, getScopeRelevanceWithinParent());
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
233 assert !Double.isNaN(relevance) : invoke + ": " + relevance + " / " + invokeProbability + " / " + getFastPathMinProbability() + " / " + getScopeRelevanceWithinParent();
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
234 return relevance;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
235 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
236 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
237
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
238 /**
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
239 * Computes the minimum probability along the most probable path within the scope. During
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
240 * iteration, the method returns immediately once a loop exit is discovered.
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
241 */
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
242 private double computeFastPathMinProbability(FixedNode scopeStart) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
243 ArrayList<FixedNode> pathBeginNodes = new ArrayList<>();
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
244 pathBeginNodes.add(scopeStart);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
245 double minPathProbability = nodeProbabilities.applyAsDouble(scopeStart);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
246 boolean isLoopScope = scopeStart instanceof LoopBeginNode;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
247
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
248 do {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
249 Node current = pathBeginNodes.remove(pathBeginNodes.size() - 1);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
250 do {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
251 if (isLoopScope && current instanceof LoopExitNode && ((LoopBeginNode) scopeStart).loopExits().contains((LoopExitNode) current)) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
252 return minPathProbability;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
253 } else if (current instanceof LoopBeginNode && current != scopeStart) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
254 current = getMaxProbabilityLoopExit((LoopBeginNode) current, pathBeginNodes);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
255 minPathProbability = getMinPathProbability((FixedNode) current, minPathProbability);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
256 } else if (current instanceof ControlSplitNode) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
257 current = getMaxProbabilitySux((ControlSplitNode) current, pathBeginNodes);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
258 minPathProbability = getMinPathProbability((FixedNode) current, minPathProbability);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
259 } else {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
260 assert current.successors().count() <= 1;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
261 current = current.successors().first();
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
262 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
263 } while (current != null);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
264 } while (!pathBeginNodes.isEmpty());
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
265
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
266 return minPathProbability;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
267 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
268
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
269 private double getMinPathProbability(FixedNode current, double minPathProbability) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
270 return current == null ? minPathProbability : Math.min(minPathProbability, nodeProbabilities.applyAsDouble(current));
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
271 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
272
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
273 /**
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
274 * Returns the most probable successor. If multiple successors share the maximum probability,
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
275 * one is returned and the others are enqueued in pathBeginNodes.
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
276 */
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
277 private static Node getMaxProbabilitySux(ControlSplitNode controlSplit, ArrayList<FixedNode> pathBeginNodes) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
278 Node maxSux = null;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
279 double maxProbability = 0.0;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
280 int pathBeginCount = pathBeginNodes.size();
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
281
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
282 for (Node sux : controlSplit.successors()) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
283 double probability = controlSplit.probability((BeginNode) sux);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
284 if (probability > maxProbability) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
285 maxProbability = probability;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
286 maxSux = sux;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
287 truncate(pathBeginNodes, pathBeginCount);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
288 } else if (probability == maxProbability) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
289 pathBeginNodes.add((FixedNode) sux);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
290 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
291 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
292
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
293 return maxSux;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
294 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
295
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
296 /**
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
297 * Returns the most probable loop exit. If multiple successors share the maximum probability,
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
298 * one is returned and the others are enqueued in pathBeginNodes.
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
299 */
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
300 private Node getMaxProbabilityLoopExit(LoopBeginNode loopBegin, ArrayList<FixedNode> pathBeginNodes) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
301 Node maxSux = null;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
302 double maxProbability = 0.0;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
303 int pathBeginCount = pathBeginNodes.size();
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
304
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
305 for (LoopExitNode sux : loopBegin.loopExits()) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
306 double probability = nodeProbabilities.applyAsDouble(sux);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
307 if (probability > maxProbability) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
308 maxProbability = probability;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
309 maxSux = sux;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
310 truncate(pathBeginNodes, pathBeginCount);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
311 } else if (probability == maxProbability) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
312 pathBeginNodes.add(sux);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
313 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
314 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
315
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
316 return maxSux;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
317 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
318
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
319 private static void truncate(ArrayList<FixedNode> pathBeginNodes, int pathBeginCount) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
320 for (int i = pathBeginNodes.size() - pathBeginCount; i > 0; i--) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
321 pathBeginNodes.remove(pathBeginNodes.size() - 1);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
322 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
323 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
324 }