Mercurial > hg > truffle

annotate graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/walker/ComputeInliningRelevance.java @ 18997:2ccaaf5a6be4

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fix class comparison statements for BeginNode and MergeNode to reflect new class hierarchy.
author Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
date Wed, 28 Jan 2015 01:11:25 +0100
parents a2cb19764970
children 61d3cb8e1280
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 java.util.*;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
26 import java.util.function.*;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
27
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
28 import com.oracle.graal.graph.*;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
29 import com.oracle.graal.nodes.*;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
30
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
31 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
32
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
33 public class ComputeInliningRelevance {
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 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
36 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
37
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
38 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
39 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
40 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
41
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
42 private final StructuredGraph graph;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
43 private final ToDoubleFunction<FixedNode> nodeProbabilities;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
44
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
45 /**
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
46 * 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
47 * 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
48 */
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
49 private Map<FixedNode, Double> nodeRelevances;
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 * 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
52 * 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
53 */
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
54 private Scope rootScope;
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 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
57 this.graph = graph;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
58 this.nodeProbabilities = nodeProbabilities;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
59 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
60
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 * 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
63 * most computation happens lazily.
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
64 */
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
65 public void compute() {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
66 rootScope = null;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
67 if (!graph.hasLoops()) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
68 // 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
69 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
70 } else {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
71 if (nodeRelevances == null) {
18383
1518c3296cc8 use deterministic iteration order Set and Map data structures when in the scope of a replay compilation context
Doug Simon <doug.simon@oracle.com>
parents: 17450
diff changeset
72 nodeRelevances = Node.newIdentityMap(EXPECTED_MIN_INVOKE_COUNT + graph.getNodeCount() / EXPECTED_INVOKE_RATIO);
15687
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
73 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
74 NodeWorkList workList = graph.createNodeWorkList();
18383
1518c3296cc8 use deterministic iteration order Set and Map data structures when in the scope of a replay compilation context
Doug Simon <doug.simon@oracle.com>
parents: 17450
diff changeset
75 Map<LoopBeginNode, Scope> loops = Node.newIdentityMap(EXPECTED_LOOP_COUNT);
15687
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
76
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
77 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
78 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
79 createLoopScope(loopBegin, loops);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
80 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
81
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
82 for (Scope scope : loops.values()) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
83 scope.process(workList);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
84 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
85 }
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 public double getRelevance(Invoke invoke) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
89 if (rootScope != null) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
90 return rootScope.computeInvokeRelevance(invoke);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
91 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
92 assert nodeRelevances != null : "uninitialized relevance";
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
93 return nodeRelevances.get(invoke);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
94 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
95
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 * 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
98 * 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
99 */
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
100 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
101 Scope scope = loops.get(loopBegin);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
102 if (scope == null) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
103 final Scope parent;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
104 // look for the parent scope
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
105 FixedNode current = loopBegin.forwardEnd();
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
106 while (true) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
107 if (current.predecessor() == null) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
108 if (current instanceof LoopBeginNode) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
109 // 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
110 parent = createLoopScope((LoopBeginNode) current, loops);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
111 break;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
112 } else if (current instanceof StartNode) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
113 // 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
114 parent = loops.get(null);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
115 break;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
116 } else {
18997
2ccaaf5a6be4 Fix class comparison statements for BeginNode and MergeNode to reflect new class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18995
diff changeset
117 assert current instanceof MergeNode : current;
15687
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
118 // follow any path upwards - it doesn't matter which one
18995
a2cb19764970 Rename MergeNode to AbstractMergeNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18993
diff changeset
119 current = ((AbstractMergeNode) current).forwardEndAt(0);
15687
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
120 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
121 } else if (current instanceof LoopExitNode) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
122 // 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
123 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
124 break;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
125 } else {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
126 current = (FixedNode) current.predecessor();
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
127 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
128 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
129 scope = new Scope(loopBegin, parent);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
130 loops.put(loopBegin, scope);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
131 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
132 return 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
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 * 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
137 * 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
138 * 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
139 */
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
140 private class Scope {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
141 public final FixedNode start;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
142 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
143
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
144 /**
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
145 * 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
146 */
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
147 private double fastPathMinProbability = UNINITIALIZED;
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 * 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
150 */
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
151 private double scopeRelevanceWithinParent = UNINITIALIZED;
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 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
154 this.start = start;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
155 this.parent = parent;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
156 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
157
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
158 @SuppressFBWarnings("FE_FLOATING_POINT_EQUALITY")
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
159 public double getFastPathMinProbability() {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
160 if (fastPathMinProbability == UNINITIALIZED) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
161 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
162 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
163 return fastPathMinProbability;
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
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 * 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
168 * parent scope's fastPathMinProbability.
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
169 */
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
170 @SuppressFBWarnings("FE_FLOATING_POINT_EQUALITY")
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
171 public double getScopeRelevanceWithinParent() {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
172 if (scopeRelevanceWithinParent == UNINITIALIZED) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
173 if (start instanceof LoopBeginNode) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
174 assert parent != null;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
175 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
176
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
177 scopeRelevanceWithinParent = scopeEntryProbability / parent.getFastPathMinProbability();
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
178 } else {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
179 scopeRelevanceWithinParent = 1D;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
180 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
181 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
182 return scopeRelevanceWithinParent;
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
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 * 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
187 * 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
188 * 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
189 */
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
190 public void process(NodeWorkList workList) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
191 assert !(start instanceof Invoke);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
192 workList.addAll(start.successors());
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
193
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
194 for (Node current : workList) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
195 assert current.isAlive();
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
196
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
197 if (current instanceof Invoke) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
198 // 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
199 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
200 workList.addAll(current.successors());
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
201 } else if (current instanceof LoopBeginNode) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
202 // 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
203 ((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
204 } else if (current instanceof LoopEndNode) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
205 // nothing to do
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
206 } else if (current instanceof LoopExitNode) {
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 FixedWithNextNode) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
209 workList.add(((FixedWithNextNode) current).next());
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
210 } else if (current instanceof EndNode) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
211 workList.add(((EndNode) current).merge());
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
212 } else if (current instanceof ControlSinkNode) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
213 // nothing to do
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
214 } else if (current instanceof ControlSplitNode) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
215 workList.addAll(current.successors());
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
216 } else {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
217 assert false : current;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
218 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
219 }
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 * 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
224 * 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
225 */
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
226 public double computeInvokeRelevance(Invoke invoke) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
227 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
228 assert !Double.isNaN(invokeProbability);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
229
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
230 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
231 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
232 return relevance;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
233 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
234 }
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 * 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
238 * 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
239 */
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
240 private double computeFastPathMinProbability(FixedNode scopeStart) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
241 ArrayList<FixedNode> pathBeginNodes = new ArrayList<>();
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
242 pathBeginNodes.add(scopeStart);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
243 double minPathProbability = nodeProbabilities.applyAsDouble(scopeStart);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
244 boolean isLoopScope = scopeStart instanceof LoopBeginNode;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
245
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
246 do {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
247 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
248 do {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
249 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
250 return minPathProbability;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
251 } 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
252 current = getMaxProbabilityLoopExit((LoopBeginNode) current, pathBeginNodes);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
253 minPathProbability = getMinPathProbability((FixedNode) current, minPathProbability);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
254 } else if (current instanceof ControlSplitNode) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
255 current = getMaxProbabilitySux((ControlSplitNode) current, pathBeginNodes);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
256 minPathProbability = getMinPathProbability((FixedNode) current, minPathProbability);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
257 } else {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
258 assert current.successors().count() <= 1;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
259 current = current.successors().first();
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
260 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
261 } while (current != null);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
262 } while (!pathBeginNodes.isEmpty());
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
263
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
264 return minPathProbability;
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
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
267 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
268 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
269 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
270
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 * 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
273 * 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
274 */
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
275 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
276 Node maxSux = null;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
277 double maxProbability = 0.0;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
278 int pathBeginCount = pathBeginNodes.size();
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
279
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
280 for (Node sux : controlSplit.successors()) {
18993
480bd3b1adcd Rename BeginNode => AbstractBeginNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18383
diff changeset
281 double probability = controlSplit.probability((AbstractBeginNode) sux);
15687
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
282 if (probability > maxProbability) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
283 maxProbability = probability;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
284 maxSux = sux;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
285 truncate(pathBeginNodes, pathBeginCount);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
286 } else if (probability == maxProbability) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
287 pathBeginNodes.add((FixedNode) sux);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
288 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
289 }
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 return maxSux;
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
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 * 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
296 * 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
297 */
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
298 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
299 Node maxSux = null;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
300 double maxProbability = 0.0;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
301 int pathBeginCount = pathBeginNodes.size();
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
302
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
303 for (LoopExitNode sux : loopBegin.loopExits()) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
304 double probability = nodeProbabilities.applyAsDouble(sux);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
305 if (probability > maxProbability) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
306 maxProbability = probability;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
307 maxSux = sux;
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
308 truncate(pathBeginNodes, pathBeginCount);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
309 } else if (probability == maxProbability) {
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
310 pathBeginNodes.add(sux);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
311 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
312 }
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 return maxSux;
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
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
317 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
318 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
319 pathBeginNodes.remove(pathBeginNodes.size() - 1);
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
320 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
321 }
ce1444862ec2 [inlining] moved ComputeInliningRelevance closer to its single user
Miguel Garcia <miguel.m.garcia@oracle.com>
parents:
diff changeset
322 }