Mercurial > hg > truffle
annotate graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/TailDuplicationPhase.java @ 6526:ee651c726397
split phases out of graal.phases project into graal.phases.common project
author | Doug Simon <doug.simon@oracle.com> |
---|---|
date | Sun, 07 Oct 2012 14:27:50 +0200 |
parents | graal/com.oracle.graal.phases/src/com/oracle/graal/phases/phases/TailDuplicationPhase.java@2c913b643422 |
children | 95a685941e10 |
rev | line source |
---|---|
5786
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
1 /* |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
2 * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
4 * |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
5 * This code is free software; you can redistribute it and/or modify it |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
6 * under the terms of the GNU General Public License version 2 only, as |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
7 * published by the Free Software Foundation. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
8 * |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
9 * This code is distributed in the hope that it will be useful, but WITHOUT |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
12 * version 2 for more details (a copy is included in the LICENSE file that |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
13 * accompanied this code). |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
14 * |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
15 * You should have received a copy of the GNU General Public License version |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
16 * 2 along with this work; if not, write to the Free Software Foundation, |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
18 * |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
20 * or visit www.oracle.com if you need additional information or have any |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
21 * questions. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
22 */ |
6526
ee651c726397
split phases out of graal.phases project into graal.phases.common project
Doug Simon <doug.simon@oracle.com>
parents:
6525
diff
changeset
|
23 package com.oracle.graal.phases.common; |
5786
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
24 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
25 import java.util.*; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
26 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
27 import com.oracle.graal.debug.*; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
28 import com.oracle.graal.graph.Graph.DuplicationReplacement; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
29 import com.oracle.graal.graph.*; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
30 import com.oracle.graal.nodes.*; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
31 import com.oracle.graal.nodes.VirtualState.NodeClosure; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
32 import com.oracle.graal.nodes.extended.*; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
33 import com.oracle.graal.nodes.java.*; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
34 import com.oracle.graal.nodes.type.*; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
35 import com.oracle.graal.nodes.util.*; |
6525
2c913b643422
rename packages in graal.phases to match project name
Doug Simon <doug.simon@oracle.com>
parents:
6522
diff
changeset
|
36 import com.oracle.graal.phases.*; |
5786
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
37 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
38 /** |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
39 * This class is a phase that looks for opportunities for tail duplication. The static method |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
40 * {@link #tailDuplicate(MergeNode, TailDuplicationDecision, List)} can also be used to drive tail duplication from |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
41 * other places, e.g., inlining. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
42 */ |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
43 public class TailDuplicationPhase extends Phase { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
44 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
45 /* |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
46 * Various metrics on the circumstances in which tail duplication was/wasn't performed. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
47 */ |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
48 private static final DebugMetric metricDuplicationMonitors = Debug.metric("DuplicationMonitors"); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
49 private static final DebugMetric metricDuplicationEnd = Debug.metric("DuplicationEnd"); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
50 private static final DebugMetric metricDuplicationEndPerformed = Debug.metric("DuplicationEndPerformed"); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
51 private static final DebugMetric metricDuplicationOther = Debug.metric("DuplicationOther"); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
52 private static final DebugMetric metricDuplicationOtherPerformed = Debug.metric("DuplicationOtherPerformed"); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
53 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
54 /** |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
55 * This interface is used by tail duplication to let clients decide if tail duplication should be performed. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
56 */ |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
57 public interface TailDuplicationDecision { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
58 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
59 /** |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
60 * Queries if tail duplication should be performed at the given merge. If this method returns true then the tail |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
61 * duplication will be performed, because all other checks have happened before. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
62 * |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
63 * @param merge The merge at which tail duplication can be performed. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
64 * @param fixedNodeCount The size of the set of fixed nodes that forms the base for the duplicated set of nodes. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
65 * @return true if the tail duplication should be performed, false otherwise. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
66 */ |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
67 boolean doTransform(MergeNode merge, int fixedNodeCount); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
68 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
69 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
70 /** |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
71 * A tail duplication decision closure that employs the default algorithm: Check if there are any phis on the merge |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
72 * whose stamps improve and that have usages within the duplicated set of fixed nodes. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
73 */ |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
74 public static final TailDuplicationDecision DEFAULT_DECISION = new TailDuplicationDecision() { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
75 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
76 public boolean doTransform(MergeNode merge, int fixedNodeCount) { |
5792
fa6ed51ac198
more aggressive tail duplication
Lukas Stadler <lukas.stadler@jku.at>
parents:
5786
diff
changeset
|
77 if (fixedNodeCount < GraalOptions.TailDuplicationTrivialSize) { |
fa6ed51ac198
more aggressive tail duplication
Lukas Stadler <lukas.stadler@jku.at>
parents:
5786
diff
changeset
|
78 return true; |
fa6ed51ac198
more aggressive tail duplication
Lukas Stadler <lukas.stadler@jku.at>
parents:
5786
diff
changeset
|
79 } |
5786
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
80 HashSet<PhiNode> improvements = new HashSet<>(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
81 for (PhiNode phi : merge.phis()) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
82 Stamp phiStamp = phi.stamp(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
83 for (ValueNode input : phi.values()) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
84 if (!input.stamp().equals(phiStamp)) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
85 improvements.add(phi); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
86 break; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
87 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
88 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
89 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
90 if (improvements.isEmpty()) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
91 return false; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
92 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
93 FixedNode current = merge; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
94 int opportunities = 0; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
95 while (current instanceof FixedWithNextNode) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
96 current = ((FixedWithNextNode) current).next(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
97 for (PhiNode phi : improvements) { |
6433
4bd8711d824a
small fix to tail duplication heuristics
Lukas Stadler <lukas.stadler@jku.at>
parents:
6411
diff
changeset
|
98 for (Node input : current.inputs()) { |
4bd8711d824a
small fix to tail duplication heuristics
Lukas Stadler <lukas.stadler@jku.at>
parents:
6411
diff
changeset
|
99 if (input == phi) { |
4bd8711d824a
small fix to tail duplication heuristics
Lukas Stadler <lukas.stadler@jku.at>
parents:
6411
diff
changeset
|
100 opportunities++; |
4bd8711d824a
small fix to tail duplication heuristics
Lukas Stadler <lukas.stadler@jku.at>
parents:
6411
diff
changeset
|
101 } |
4bd8711d824a
small fix to tail duplication heuristics
Lukas Stadler <lukas.stadler@jku.at>
parents:
6411
diff
changeset
|
102 if (input.inputs().contains(phi)) { |
4bd8711d824a
small fix to tail duplication heuristics
Lukas Stadler <lukas.stadler@jku.at>
parents:
6411
diff
changeset
|
103 opportunities++; |
4bd8711d824a
small fix to tail duplication heuristics
Lukas Stadler <lukas.stadler@jku.at>
parents:
6411
diff
changeset
|
104 } |
5786
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
105 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
106 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
107 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
108 return opportunities > 0; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
109 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
110 }; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
111 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
112 /** |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
113 * A tail duplication decision closure that always returns true. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
114 */ |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
115 public static final TailDuplicationDecision TRUE_DECISION = new TailDuplicationDecision() { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
116 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
117 @Override |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
118 public boolean doTransform(MergeNode merge, int fixedNodeCount) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
119 return true; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
120 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
121 }; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
122 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
123 @Override |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
124 protected void run(StructuredGraph graph) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
125 // A snapshot is taken here, so that new MergeNode instances aren't considered for tail duplication. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
126 for (MergeNode merge : graph.getNodes(MergeNode.class).snapshot()) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
127 if (!(merge instanceof LoopBeginNode) && merge.probability() >= GraalOptions.TailDuplicationProbability) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
128 tailDuplicate(merge, DEFAULT_DECISION, null); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
129 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
130 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
131 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
132 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
133 /** |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
134 * This method attempts to duplicate the tail of the given merge. The merge must not be a {@link LoopBeginNode}. If |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
135 * the merge is eligible for duplication (at least one fixed node in its tail, no {@link MonitorEnterNode}/ |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
136 * {@link MonitorExitNode}, non-null {@link MergeNode#stateAfter()}) then the decision callback is used to determine |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
137 * whether the tail duplication should actually be performed. If replacements is non-null, then this list of |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
138 * {@link PiNode}s is used to replace one value per merge end. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
139 * |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
140 * @param merge The merge whose tail should be duplicated. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
141 * @param decision A callback that can make the final decision if tail duplication should occur or not. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
142 * @param replacements A list of {@link PiNode}s, or null. If this list is non-null then its size needs to match the |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
143 * merge's end count. Each entry can either be null or a {@link PiNode}, and is used to replace |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
144 * {@link PiNode#object()} with the {@link PiNode} in the duplicated branch that corresponds to the |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
145 * entry. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
146 */ |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
147 public static void tailDuplicate(MergeNode merge, TailDuplicationDecision decision, List<PiNode> replacements) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
148 assert !(merge instanceof LoopBeginNode); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
149 assert replacements == null || replacements.size() == merge.forwardEndCount(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
150 FixedNode fixed = merge; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
151 int fixedCount = 0; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
152 boolean containsMonitor = false; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
153 while (fixed instanceof FixedWithNextNode) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
154 if (fixed instanceof MonitorEnterNode || fixed instanceof MonitorExitNode) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
155 containsMonitor = true; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
156 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
157 fixed = ((FixedWithNextNode) fixed).next(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
158 fixedCount++; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
159 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
160 if (containsMonitor) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
161 // cannot currently be handled |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
162 // TODO (ls) re-evaluate this limitation after changes to the lock representation and the LIR generator |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
163 metricDuplicationMonitors.increment(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
164 } else if (fixedCount > 1) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
165 if (fixed instanceof EndNode && !(((EndNode) fixed).merge() instanceof LoopBeginNode)) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
166 metricDuplicationEnd.increment(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
167 if (decision.doTransform(merge, fixedCount)) { |
5792
fa6ed51ac198
more aggressive tail duplication
Lukas Stadler <lukas.stadler@jku.at>
parents:
5786
diff
changeset
|
168 metricDuplicationEndPerformed.increment(); |
5786
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
169 new DuplicationOperation(merge, replacements).duplicate(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
170 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
171 } else if (merge.stateAfter() != null) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
172 metricDuplicationOther.increment(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
173 if (decision.doTransform(merge, fixedCount)) { |
5792
fa6ed51ac198
more aggressive tail duplication
Lukas Stadler <lukas.stadler@jku.at>
parents:
5786
diff
changeset
|
174 metricDuplicationOtherPerformed.increment(); |
5786
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
175 new DuplicationOperation(merge, replacements).duplicate(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
176 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
177 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
178 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
179 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
180 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
181 /** |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
182 * This class encapsulates one tail duplication operation on a specific {@link MergeNode}. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
183 */ |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
184 private static class DuplicationOperation { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
185 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
186 private final MergeNode merge; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
187 private final StructuredGraph graph; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
188 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
189 private final HashMap<ValueNode, PhiNode> bottomPhis = new HashMap<>(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
190 private final List<PiNode> replacements; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
191 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
192 /** |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
193 * Initializes the tail duplication operation without actually performing any work. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
194 * |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
195 * @param merge The merge whose tail should be duplicated. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
196 * @param replacements A list of replacement {@link PiNode}s, or null. If this is non-null, then the size of the |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
197 * list needs to match the number of end nodes at the merge. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
198 */ |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
199 public DuplicationOperation(MergeNode merge, List<PiNode> replacements) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
200 this.merge = merge; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
201 this.replacements = replacements; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
202 this.graph = (StructuredGraph) merge.graph(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
203 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
204 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
205 /** |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
206 * Performs the actual tail duplication: |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
207 * <ul> |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
208 * <li>Creates a new {@link ValueAnchorNode} at the beginning of the duplicated area, an transfers all |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
209 * dependencies from the merge to this anchor.</li> |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
210 * <li>Determines the set of fixed nodes to be duplicated.</li> |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
211 * <li>Creates the new merge at the bottom of the duplicated area.</li> |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
212 * <li>Determines the complete set of duplicated nodes.</li> |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
213 * <li>Performs the actual duplication.</li> |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
214 * </ul> |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
215 */ |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
216 private void duplicate() { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
217 Debug.log("tail duplication at merge %s in %s (prob %f)", merge, graph.method(), merge.probability()); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
218 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
219 ValueAnchorNode anchor = addValueAnchor(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
220 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
221 // determine the fixed nodes that should be duplicated (currently: all nodes up until the first control |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
222 // split, end node, deopt or return. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
223 ArrayList<FixedNode> fixedNodes = new ArrayList<>(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
224 FixedNode fixed = merge.next(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
225 FrameState stateAfter = merge.stateAfter(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
226 while (fixed instanceof FixedWithNextNode) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
227 fixedNodes.add(fixed); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
228 if (fixed instanceof StateSplit && ((StateSplit) fixed).stateAfter() != null) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
229 stateAfter = ((StateSplit) fixed).stateAfter(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
230 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
231 fixed = ((FixedWithNextNode) fixed).next(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
232 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
233 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
234 EndNode endAfter = createNewMerge(fixed, stateAfter); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
235 MergeNode mergeAfter = endAfter.merge(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
236 fixedNodes.add(endAfter); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
237 final HashSet<Node> duplicatedNodes = buildDuplicatedNodeSet(fixedNodes, stateAfter); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
238 mergeAfter.clearEnds(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
239 expandDuplicated(duplicatedNodes, mergeAfter); |
5861
1cb45c7dba55
retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
5792
diff
changeset
|
240 retargetDependencies(duplicatedNodes, anchor); |
5786
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
241 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
242 List<EndNode> endSnapshot = merge.forwardEnds().snapshot(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
243 List<PhiNode> phiSnapshot = merge.phis().snapshot(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
244 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
245 int endIndex = 0; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
246 for (final EndNode forwardEnd : merge.forwardEnds()) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
247 Map<Node, Node> duplicates; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
248 if (replacements == null || replacements.get(endIndex) == null) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
249 duplicates = graph.addDuplicates(duplicatedNodes, (DuplicationReplacement) null); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
250 } else { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
251 HashMap<Node, Node> replace = new HashMap<>(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
252 replace.put(replacements.get(endIndex).object(), replacements.get(endIndex)); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
253 duplicates = graph.addDuplicates(duplicatedNodes, replace); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
254 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
255 for (Map.Entry<ValueNode, PhiNode> phi : bottomPhis.entrySet()) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
256 phi.getValue().initializeValueAt(merge.forwardEndIndex(forwardEnd), (ValueNode) duplicates.get(phi.getKey())); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
257 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
258 mergeAfter.addForwardEnd((EndNode) duplicates.get(endAfter)); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
259 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
260 // re-wire the duplicated ValueAnchorNode to the predecessor of the corresponding EndNode |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
261 FixedNode anchorDuplicate = (FixedNode) duplicates.get(anchor); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
262 ((FixedWithNextNode) forwardEnd.predecessor()).setNext(anchorDuplicate); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
263 // move dependencies on the ValueAnchorNode to the previous BeginNode |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
264 BeginNode prevBegin = BeginNode.prevBegin(anchorDuplicate); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
265 anchorDuplicate.replaceAtUsages(prevBegin); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
266 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
267 // re-wire the phi duplicates to the correct input |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
268 for (PhiNode phi : phiSnapshot) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
269 PhiNode phiDuplicate = (PhiNode) duplicates.get(phi); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
270 for (Node usage : phiDuplicate.usages()) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
271 if (usage instanceof ValueNode) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
272 ((ValueNode) usage).dependencies().add(prevBegin); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
273 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
274 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
275 phiDuplicate.replaceAtUsages(phi.valueAt(forwardEnd)); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
276 phiDuplicate.safeDelete(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
277 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
278 endIndex++; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
279 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
280 GraphUtil.killCFG(merge); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
281 for (EndNode forwardEnd : endSnapshot) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
282 forwardEnd.safeDelete(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
283 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
284 for (PhiNode phi : phiSnapshot) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
285 // these phis should go away, but they still need to be anchored to a merge to be valid... |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
286 if (phi.isAlive()) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
287 phi.setMerge(mergeAfter); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
288 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
289 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
290 Debug.dump(graph, "After tail duplication at %s", merge); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
291 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
292 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
293 /** |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
294 * Inserts a new ValueAnchorNode after the merge and transfers all dependency-usages (not phis) to this |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
295 * ValueAnchorNode. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
296 * |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
297 * @return The new {@link ValueAnchorNode} that was created. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
298 */ |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
299 private ValueAnchorNode addValueAnchor() { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
300 ValueAnchorNode anchor = graph.add(new ValueAnchorNode()); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
301 graph.addAfterFixed(merge, anchor); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
302 for (Node usage : merge.usages().snapshot()) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
303 if (usage instanceof PhiNode && ((PhiNode) usage).merge() == merge) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
304 // nothing to do |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
305 } else { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
306 usage.replaceFirstInput(merge, anchor); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
307 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
308 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
309 return anchor; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
310 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
311 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
312 /** |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
313 * Given a set of fixed nodes, this method determines the set of fixed and floating nodes that needs to be |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
314 * duplicated, i.e., all nodes that due to data flow and other dependencies needs to be duplicated. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
315 * |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
316 * @param fixedNodes The set of fixed nodes that should be duplicated. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
317 * @param stateAfter The frame state of the merge that follows the set of fixed nodes. All {@link ValueNode}s |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
318 * reachable from this state are considered to be reachable from within the duplicated set of nodes. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
319 * @return The set of nodes that need to be duplicated. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
320 */ |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
321 private HashSet<Node> buildDuplicatedNodeSet(final ArrayList<FixedNode> fixedNodes, FrameState stateAfter) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
322 final NodeBitMap aboveBound = graph.createNodeBitMap(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
323 final NodeBitMap belowBound = graph.createNodeBitMap(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
324 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
325 final Deque<Node> worklist = new ArrayDeque<>(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
326 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
327 // Build the set of nodes that have (transitive) usages within the duplicatedNodes. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
328 // This is achieved by iterating all nodes that are reachable via inputs from the the fixed nodes. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
329 aboveBound.markAll(fixedNodes); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
330 worklist.addAll(fixedNodes); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
331 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
332 // the phis at the original merge should always be duplicated |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
333 for (PhiNode phi : merge.phis()) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
334 aboveBound.mark(phi); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
335 worklist.add(phi); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
336 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
337 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
338 NodeClosure<Node> aboveClosure = new NodeClosure<Node>() { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
339 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
340 @Override |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
341 public void apply(Node usage, Node node) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
342 if (node instanceof PhiNode && !fixedNodes.contains(((PhiNode) node).merge())) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
343 // stop iterating: phis belonging to outside merges are known to be outside. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
344 } else if (node instanceof FixedNode) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
345 // stop iterating: fixed nodes within the given set are traversal roots anyway, and all other |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
346 // fixed nodes are known to be outside. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
347 } else if (!aboveBound.isMarked(node)) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
348 worklist.add(node); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
349 aboveBound.mark(node); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
350 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
351 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
352 }; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
353 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
354 if (stateAfter != null) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
355 stateAfter.applyToNonVirtual(aboveClosure); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
356 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
357 while (!worklist.isEmpty()) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
358 Node current = worklist.remove(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
359 for (Node input : current.inputs()) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
360 aboveClosure.apply(current, input); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
361 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
362 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
363 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
364 // Build the set of nodes that have (transitive) inputs within the duplicatedNodes. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
365 // This is achieved by iterating all nodes that are reachable via usages from the fixed nodes. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
366 belowBound.markAll(fixedNodes); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
367 worklist.addAll(fixedNodes); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
368 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
369 // the phis at the original merge should always be duplicated |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
370 for (PhiNode phi : merge.phis()) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
371 belowBound.mark(phi); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
372 worklist.add(phi); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
373 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
374 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
375 while (!worklist.isEmpty()) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
376 Node current = worklist.remove(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
377 for (Node usage : current.usages()) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
378 if (usage instanceof PhiNode && !fixedNodes.contains(((PhiNode) usage).merge())) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
379 // stop iterating: phis belonging to outside merges are known to be outside. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
380 } else if (usage instanceof FixedNode) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
381 // stop iterating: fixed nodes within the given set are traversal roots anyway, and all other |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
382 // fixed nodes are known to be outside. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
383 } else if (!belowBound.isMarked(usage)) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
384 worklist.add(usage); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
385 belowBound.mark(usage); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
386 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
387 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
388 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
389 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
390 // build the intersection |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
391 belowBound.intersect(aboveBound); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
392 HashSet<Node> result = new HashSet<>(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
393 for (Node node : belowBound) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
394 result.add(node); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
395 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
396 return result; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
397 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
398 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
399 /** |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
400 * Creates a new merge and end node construct at the end of the duplicated area. While it is useless in itself |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
401 * (merge with only one end) it simplifies the later duplication step. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
402 * |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
403 * @param successor The successor of the duplicated set of nodes, i.e., the first node that should not be |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
404 * duplicated. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
405 * @param stateAfterMerge The frame state that should be used for the merge. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
406 * @return The newly created end node. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
407 */ |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
408 private EndNode createNewMerge(FixedNode successor, FrameState stateAfterMerge) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
409 MergeNode newBottomMerge = graph.add(new MergeNode()); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
410 newBottomMerge.setProbability(successor.probability()); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
411 EndNode newBottomEnd = graph.add(new EndNode()); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
412 newBottomMerge.addForwardEnd(newBottomEnd); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
413 newBottomMerge.setStateAfter(stateAfterMerge); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
414 ((FixedWithNextNode) successor.predecessor()).setNext(newBottomEnd); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
415 newBottomMerge.setNext(successor); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
416 return newBottomEnd; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
417 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
418 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
419 /** |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
420 * Expands the set of nodes to be duplicated by looking at a number of conditions: |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
421 * <ul> |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
422 * <li>{@link ValueNode}s that have usages on the outside need to be replaced with phis for the outside usages.</li> |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
423 * <li>Non-{@link ValueNode} nodes that have outside usages (frame states, virtual object states, ...) need to |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
424 * be cloned immediately for the outside usages.</li> |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
425 * <li>Nodes that have a {@link StampFactory#extension()} or {@link StampFactory#condition()} stamp need to be |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
426 * cloned immediately for the outside usages.</li> |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
427 * <li>Dependencies into the duplicated nodes will be replaced with dependencies on the merge.</li> |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
428 * <li>Outside non-{@link ValueNode}s with usages within the duplicated set of nodes need to also be duplicated. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
429 * </li> |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
430 * <li>Outside {@link ValueNode}s with {@link StampFactory#extension()} or {@link StampFactory#condition()} |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
431 * stamps that have usages within the duplicated set of nodes need to also be duplicated.</li> |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
432 * </ul> |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
433 * |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
434 * @param duplicatedNodes The set of duplicated nodes that will be modified (expanded). |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
435 * @param newBottomMerge The merge that follows the duplicated set of nodes. It will be used for newly created |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
436 * phis and to as a target for dependencies that pointed into the duplicated set of nodes. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
437 */ |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
438 private void expandDuplicated(HashSet<Node> duplicatedNodes, MergeNode newBottomMerge) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
439 Deque<Node> worklist = new ArrayDeque<>(duplicatedNodes); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
440 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
441 while (!worklist.isEmpty()) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
442 Node duplicated = worklist.remove(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
443 if (hasUsagesOutside(duplicated, duplicatedNodes)) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
444 boolean cloneForOutsideUsages = false; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
445 if (duplicated instanceof ValueNode) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
446 ValueNode node = (ValueNode) duplicated; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
447 if (node.stamp() == StampFactory.dependency()) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
448 // re-route dependencies to the merge |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
449 replaceUsagesOutside(node, newBottomMerge, duplicatedNodes); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
450 // TODO(ls) maybe introduce phis for dependencies |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
451 } else if (node.stamp() == StampFactory.extension() || node.stamp() == StampFactory.condition()) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
452 cloneForOutsideUsages = true; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
453 } else { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
454 // introduce a new phi |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
455 PhiNode newPhi = bottomPhis.get(node); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
456 if (newPhi == null) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
457 newPhi = graph.add(new PhiNode(node.kind(), newBottomMerge)); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
458 bottomPhis.put(node, newPhi); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
459 newPhi.addInput(node); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
460 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
461 replaceUsagesOutside(node, newPhi, duplicatedNodes); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
462 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
463 } else { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
464 cloneForOutsideUsages = true; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
465 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
466 if (cloneForOutsideUsages) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
467 // clone the offending node to the outside |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
468 Node newOutsideClone = duplicated.copyWithInputs(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
469 replaceUsagesOutside(duplicated, newOutsideClone, duplicatedNodes); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
470 // this might cause other nodes to have outside usages, we need to look at those as well |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
471 for (Node input : newOutsideClone.inputs()) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
472 if (duplicatedNodes.contains(input)) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
473 worklist.add(input); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
474 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
475 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
476 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
477 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
478 // check if this node has an input that lies outside and cannot be shared |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
479 for (Node input : duplicated.inputs()) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
480 if (!duplicatedNodes.contains(input)) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
481 boolean duplicateInput = false; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
482 if (input instanceof VirtualState) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
483 duplicateInput = true; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
484 } else if (input instanceof ValueNode) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
485 Stamp inputStamp = ((ValueNode) input).stamp(); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
486 if (inputStamp == StampFactory.extension() || inputStamp == StampFactory.condition()) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
487 duplicateInput = true; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
488 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
489 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
490 if (duplicateInput) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
491 duplicatedNodes.add(input); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
492 worklist.add(input); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
493 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
494 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
495 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
496 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
497 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
498 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
499 /** |
5861
1cb45c7dba55
retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
5792
diff
changeset
|
500 * Moves all depdendencies that point outside the duplicated area to the supplied value anchor node. |
1cb45c7dba55
retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
5792
diff
changeset
|
501 * |
1cb45c7dba55
retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
5792
diff
changeset
|
502 * @param duplicatedNodes The set of duplicated nodes. |
1cb45c7dba55
retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
5792
diff
changeset
|
503 * @param anchor The node that will be the new target for all dependencies that point outside the duplicated set of nodes. |
1cb45c7dba55
retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
5792
diff
changeset
|
504 */ |
1cb45c7dba55
retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
5792
diff
changeset
|
505 private static void retargetDependencies(HashSet<Node> duplicatedNodes, ValueAnchorNode anchor) { |
1cb45c7dba55
retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
5792
diff
changeset
|
506 for (Node node : duplicatedNodes) { |
1cb45c7dba55
retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
5792
diff
changeset
|
507 if (node instanceof ValueNode) { |
1cb45c7dba55
retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
5792
diff
changeset
|
508 NodeInputList<ValueNode> dependencies = ((ValueNode) node).dependencies(); |
1cb45c7dba55
retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
5792
diff
changeset
|
509 for (int i = 0; i < dependencies.size(); i++) { |
1cb45c7dba55
retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
5792
diff
changeset
|
510 Node dependency = dependencies.get(i); |
1cb45c7dba55
retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
5792
diff
changeset
|
511 if (dependency != null && !duplicatedNodes.contains(dependency)) { |
1cb45c7dba55
retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
5792
diff
changeset
|
512 Debug.log("retargeting dependency %s to %s on %s", dependency, anchor, node); |
1cb45c7dba55
retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
5792
diff
changeset
|
513 dependencies.set(i, anchor); |
1cb45c7dba55
retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
5792
diff
changeset
|
514 } |
1cb45c7dba55
retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
5792
diff
changeset
|
515 } |
1cb45c7dba55
retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
5792
diff
changeset
|
516 } |
1cb45c7dba55
retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
5792
diff
changeset
|
517 } |
1cb45c7dba55
retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
5792
diff
changeset
|
518 } |
1cb45c7dba55
retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
5792
diff
changeset
|
519 |
1cb45c7dba55
retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
5792
diff
changeset
|
520 /** |
5786
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
521 * Checks if the given node has usages that are not within the given set of nodes. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
522 * |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
523 * @param node The node whose usages are checked. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
524 * @param nodeSet The set of nodes that are considered to be "within". |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
525 * @return true if the given node has usages on the outside, false otherwise. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
526 */ |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
527 private static boolean hasUsagesOutside(Node node, HashSet<Node> nodeSet) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
528 for (Node usage : node.usages()) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
529 if (!nodeSet.contains(usage)) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
530 return true; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
531 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
532 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
533 return false; |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
534 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
535 |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
536 /** |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
537 * Replaces the given node with the given replacement at all usages that are not within the given set of nodes. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
538 * |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
539 * @param node The node to be replaced at outside usages. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
540 * @param replacement The node that replaced the given node at outside usages. |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
541 * @param nodeSet The set of nodes that are considered to be "within". |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
542 */ |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
543 private static void replaceUsagesOutside(Node node, Node replacement, HashSet<Node> nodeSet) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
544 for (Node usage : node.usages().snapshot()) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
545 if (!nodeSet.contains(usage)) { |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
546 usage.replaceFirstInput(node, replacement); |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
547 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
548 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
549 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
550 } |
f69a406355b2
new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
551 } |