Mercurial > hg > truffle

annotate graal/com.oracle.graal.compiler.phases/src/com/oracle/graal/compiler/phases/TailDuplicationPhase.java @ 6411:c5afcc2ebd3d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
change of project structure: separate compiler and LIR, put EA into separate project
author Lukas Stadler <lukas.stadler@jku.at>
date Mon, 17 Sep 2012 16:08:46 +0200
parents graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/TailDuplicationPhase.java@1cb45c7dba55
children 4bd8711d824a
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
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 */
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
23 package com.oracle.graal.compiler.phases;
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.compiler.*;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
28 import com.oracle.graal.debug.*;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
29 import com.oracle.graal.graph.Graph.DuplicationReplacement;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
30 import com.oracle.graal.graph.*;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
31 import com.oracle.graal.nodes.*;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
32 import com.oracle.graal.nodes.VirtualState.NodeClosure;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
33 import com.oracle.graal.nodes.extended.*;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
34 import com.oracle.graal.nodes.java.*;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
35 import com.oracle.graal.nodes.type.*;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
36 import com.oracle.graal.nodes.util.*;
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) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
98 if (current.inputs().contains(phi)) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
99 opportunities++;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
100 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
101 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
102 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
103 return opportunities > 0;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
104 }
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 * A tail duplication decision closure that always returns true.
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 public static final TailDuplicationDecision TRUE_DECISION = new TailDuplicationDecision() {
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 @Override
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
113 public boolean doTransform(MergeNode merge, int fixedNodeCount) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
114 return true;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
115 }
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
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
118 @Override
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
119 protected void run(StructuredGraph graph) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
120 // 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
121 for (MergeNode merge : graph.getNodes(MergeNode.class).snapshot()) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
122 if (!(merge instanceof LoopBeginNode) && merge.probability() >= GraalOptions.TailDuplicationProbability) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
123 tailDuplicate(merge, DEFAULT_DECISION, null);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
124 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
125 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
126 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
127
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
128 /**
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
129 * 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
130 * 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
131 * {@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
132 * 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
133 * {@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
134 *
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
135 * @param merge The merge whose tail should be duplicated.
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
136 * @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
137 * @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
138 * 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
139 * {@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
140 * entry.
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
141 */
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
142 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
143 assert !(merge instanceof LoopBeginNode);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
144 assert replacements == null || replacements.size() == merge.forwardEndCount();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
145 FixedNode fixed = merge;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
146 int fixedCount = 0;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
147 boolean containsMonitor = false;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
148 while (fixed instanceof FixedWithNextNode) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
149 if (fixed instanceof MonitorEnterNode || fixed instanceof MonitorExitNode) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
150 containsMonitor = true;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
151 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
152 fixed = ((FixedWithNextNode) fixed).next();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
153 fixedCount++;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
154 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
155 if (containsMonitor) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
156 // cannot currently be handled
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
157 // 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
158 metricDuplicationMonitors.increment();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
159 } else if (fixedCount > 1) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
160 if (fixed instanceof EndNode && !(((EndNode) fixed).merge() instanceof LoopBeginNode)) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
161 metricDuplicationEnd.increment();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
162 if (decision.doTransform(merge, fixedCount)) {
5792
fa6ed51ac198 more aggressive tail duplication
Lukas Stadler <lukas.stadler@jku.at>
parents: 5786
diff changeset
163 metricDuplicationEndPerformed.increment();
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
164 new DuplicationOperation(merge, replacements).duplicate();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
165 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
166 } else if (merge.stateAfter() != null) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
167 metricDuplicationOther.increment();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
168 if (decision.doTransform(merge, fixedCount)) {
5792
fa6ed51ac198 more aggressive tail duplication
Lukas Stadler <lukas.stadler@jku.at>
parents: 5786
diff changeset
169 metricDuplicationOtherPerformed.increment();
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
170 new DuplicationOperation(merge, replacements).duplicate();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
171 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
172 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
173 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
174 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
175
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 * 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
178 */
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
179 private static class DuplicationOperation {
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 private final MergeNode merge;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
182 private final StructuredGraph graph;
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 final HashMap<ValueNode, PhiNode> bottomPhis = new HashMap<>();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
185 private final List<PiNode> replacements;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
186
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
187 /**
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
188 * Initializes the tail duplication operation without actually performing any work.
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
189 *
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
190 * @param merge The merge whose tail should be duplicated.
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
191 * @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
192 * 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
193 */
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
194 public DuplicationOperation(MergeNode merge, List<PiNode> replacements) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
195 this.merge = merge;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
196 this.replacements = replacements;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
197 this.graph = (StructuredGraph) merge.graph();
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
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
200 /**
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
201 * Performs the actual tail duplication:
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
202 * <ul>
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
203 * <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
204 * dependencies from the merge to this anchor.</li>
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
205 * <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
206 * <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
207 * <li>Determines the complete set of duplicated nodes.</li>
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
208 * <li>Performs the actual duplication.</li>
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
209 * </ul>
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
210 */
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
211 private void duplicate() {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
212 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
213
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
214 ValueAnchorNode anchor = addValueAnchor();
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 // 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
217 // split, end node, deopt or return.
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
218 ArrayList<FixedNode> fixedNodes = new ArrayList<>();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
219 FixedNode fixed = merge.next();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
220 FrameState stateAfter = merge.stateAfter();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
221 while (fixed instanceof FixedWithNextNode) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
222 fixedNodes.add(fixed);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
223 if (fixed instanceof StateSplit && ((StateSplit) fixed).stateAfter() != null) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
224 stateAfter = ((StateSplit) fixed).stateAfter();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
225 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
226 fixed = ((FixedWithNextNode) fixed).next();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
227 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
228
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
229 EndNode endAfter = createNewMerge(fixed, stateAfter);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
230 MergeNode mergeAfter = endAfter.merge();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
231 fixedNodes.add(endAfter);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
232 final HashSet<Node> duplicatedNodes = buildDuplicatedNodeSet(fixedNodes, stateAfter);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
233 mergeAfter.clearEnds();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
234 expandDuplicated(duplicatedNodes, mergeAfter);
5861
1cb45c7dba55 retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents: 5792
diff changeset
235 retargetDependencies(duplicatedNodes, anchor);
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
236
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
237 List<EndNode> endSnapshot = merge.forwardEnds().snapshot();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
238 List<PhiNode> phiSnapshot = merge.phis().snapshot();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
239
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
240 int endIndex = 0;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
241 for (final EndNode forwardEnd : merge.forwardEnds()) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
242 Map<Node, Node> duplicates;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
243 if (replacements == null || replacements.get(endIndex) == null) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
244 duplicates = graph.addDuplicates(duplicatedNodes, (DuplicationReplacement) null);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
245 } else {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
246 HashMap<Node, Node> replace = new HashMap<>();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
247 replace.put(replacements.get(endIndex).object(), replacements.get(endIndex));
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
248 duplicates = graph.addDuplicates(duplicatedNodes, replace);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
249 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
250 for (Map.Entry<ValueNode, PhiNode> phi : bottomPhis.entrySet()) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
251 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
252 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
253 mergeAfter.addForwardEnd((EndNode) duplicates.get(endAfter));
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 // 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
256 FixedNode anchorDuplicate = (FixedNode) duplicates.get(anchor);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
257 ((FixedWithNextNode) forwardEnd.predecessor()).setNext(anchorDuplicate);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
258 // move dependencies on the ValueAnchorNode to the previous BeginNode
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
259 BeginNode prevBegin = BeginNode.prevBegin(anchorDuplicate);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
260 anchorDuplicate.replaceAtUsages(prevBegin);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
261
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
262 // re-wire the phi duplicates to the correct input
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
263 for (PhiNode phi : phiSnapshot) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
264 PhiNode phiDuplicate = (PhiNode) duplicates.get(phi);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
265 for (Node usage : phiDuplicate.usages()) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
266 if (usage instanceof ValueNode) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
267 ((ValueNode) usage).dependencies().add(prevBegin);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
268 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
269 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
270 phiDuplicate.replaceAtUsages(phi.valueAt(forwardEnd));
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
271 phiDuplicate.safeDelete();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
272 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
273 endIndex++;
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 GraphUtil.killCFG(merge);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
276 for (EndNode forwardEnd : endSnapshot) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
277 forwardEnd.safeDelete();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
278 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
279 for (PhiNode phi : phiSnapshot) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
280 // 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
281 if (phi.isAlive()) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
282 phi.setMerge(mergeAfter);
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 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
285 Debug.dump(graph, "After tail duplication at %s", merge);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
286 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
287
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 * 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
290 * ValueAnchorNode.
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 * @return The new {@link ValueAnchorNode} that was created.
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 private ValueAnchorNode addValueAnchor() {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
295 ValueAnchorNode anchor = graph.add(new ValueAnchorNode());
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
296 graph.addAfterFixed(merge, anchor);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
297 for (Node usage : merge.usages().snapshot()) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
298 if (usage instanceof PhiNode && ((PhiNode) usage).merge() == merge) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
299 // nothing to do
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
300 } else {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
301 usage.replaceFirstInput(merge, anchor);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
302 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
303 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
304 return anchor;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
305 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
306
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 * 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
309 * 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
310 *
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
311 * @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
312 * @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
313 * 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
314 * @return The set of nodes that need 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 private HashSet<Node> buildDuplicatedNodeSet(final ArrayList<FixedNode> fixedNodes, FrameState stateAfter) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
317 final NodeBitMap aboveBound = graph.createNodeBitMap();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
318 final NodeBitMap belowBound = graph.createNodeBitMap();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
319
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
320 final Deque<Node> worklist = new ArrayDeque<>();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
321
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
322 // 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
323 // 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
324 aboveBound.markAll(fixedNodes);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
325 worklist.addAll(fixedNodes);
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 // the phis at the original merge should always be duplicated
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
328 for (PhiNode phi : merge.phis()) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
329 aboveBound.mark(phi);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
330 worklist.add(phi);
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
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
333 NodeClosure<Node> aboveClosure = new NodeClosure<Node>() {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
334
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
335 @Override
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
336 public void apply(Node usage, Node node) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
337 if (node instanceof PhiNode && !fixedNodes.contains(((PhiNode) node).merge())) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
338 // 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
339 } else if (node instanceof FixedNode) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
340 // 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
341 // fixed nodes are known to be outside.
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
342 } else if (!aboveBound.isMarked(node)) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
343 worklist.add(node);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
344 aboveBound.mark(node);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
345 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
346 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
347 };
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
348
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
349 if (stateAfter != null) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
350 stateAfter.applyToNonVirtual(aboveClosure);
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 while (!worklist.isEmpty()) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
353 Node current = worklist.remove();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
354 for (Node input : current.inputs()) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
355 aboveClosure.apply(current, input);
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 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
358
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
359 // 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
360 // 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
361 belowBound.markAll(fixedNodes);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
362 worklist.addAll(fixedNodes);
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 // the phis at the original merge should always be duplicated
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
365 for (PhiNode phi : merge.phis()) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
366 belowBound.mark(phi);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
367 worklist.add(phi);
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
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
370 while (!worklist.isEmpty()) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
371 Node current = worklist.remove();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
372 for (Node usage : current.usages()) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
373 if (usage instanceof PhiNode && !fixedNodes.contains(((PhiNode) usage).merge())) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
374 // 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
375 } else if (usage instanceof FixedNode) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
376 // 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
377 // fixed nodes are known to be outside.
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
378 } else if (!belowBound.isMarked(usage)) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
379 worklist.add(usage);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
380 belowBound.mark(usage);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
381 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
382 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
383 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
384
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
385 // build the intersection
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
386 belowBound.intersect(aboveBound);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
387 HashSet<Node> result = new HashSet<>();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
388 for (Node node : belowBound) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
389 result.add(node);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
390 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
391 return result;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
392 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
393
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
394 /**
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
395 * 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
396 * (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
397 *
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
398 * @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
399 * duplicated.
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
400 * @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
401 * @return The newly created end node.
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 private EndNode createNewMerge(FixedNode successor, FrameState stateAfterMerge) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
404 MergeNode newBottomMerge = graph.add(new MergeNode());
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
405 newBottomMerge.setProbability(successor.probability());
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
406 EndNode newBottomEnd = graph.add(new EndNode());
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
407 newBottomMerge.addForwardEnd(newBottomEnd);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
408 newBottomMerge.setStateAfter(stateAfterMerge);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
409 ((FixedWithNextNode) successor.predecessor()).setNext(newBottomEnd);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
410 newBottomMerge.setNext(successor);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
411 return newBottomEnd;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
412 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
413
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
414 /**
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
415 * 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
416 * <ul>
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
417 * <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
418 * <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
419 * be cloned immediately for the outside usages.</li>
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
420 * <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
421 * cloned immediately for the outside usages.</li>
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
422 * <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
423 * <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
424 * </li>
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
425 * <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
426 * 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
427 * </ul>
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
428 *
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
429 * @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
430 * @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
431 * 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
432 */
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
433 private void expandDuplicated(HashSet<Node> duplicatedNodes, MergeNode newBottomMerge) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
434 Deque<Node> worklist = new ArrayDeque<>(duplicatedNodes);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
435
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
436 while (!worklist.isEmpty()) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
437 Node duplicated = worklist.remove();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
438 if (hasUsagesOutside(duplicated, duplicatedNodes)) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
439 boolean cloneForOutsideUsages = false;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
440 if (duplicated instanceof ValueNode) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
441 ValueNode node = (ValueNode) duplicated;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
442 if (node.stamp() == StampFactory.dependency()) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
443 // re-route dependencies to the merge
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
444 replaceUsagesOutside(node, newBottomMerge, duplicatedNodes);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
445 // TODO(ls) maybe introduce phis for dependencies
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
446 } else if (node.stamp() == StampFactory.extension() || node.stamp() == StampFactory.condition()) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
447 cloneForOutsideUsages = true;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
448 } else {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
449 // introduce a new phi
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
450 PhiNode newPhi = bottomPhis.get(node);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
451 if (newPhi == null) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
452 newPhi = graph.add(new PhiNode(node.kind(), newBottomMerge));
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
453 bottomPhis.put(node, newPhi);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
454 newPhi.addInput(node);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
455 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
456 replaceUsagesOutside(node, newPhi, duplicatedNodes);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
457 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
458 } else {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
459 cloneForOutsideUsages = true;
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 if (cloneForOutsideUsages) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
462 // clone the offending node to the outside
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
463 Node newOutsideClone = duplicated.copyWithInputs();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
464 replaceUsagesOutside(duplicated, newOutsideClone, duplicatedNodes);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
465 // 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
466 for (Node input : newOutsideClone.inputs()) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
467 if (duplicatedNodes.contains(input)) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
468 worklist.add(input);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
469 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
470 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
471 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
472 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
473 // 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
474 for (Node input : duplicated.inputs()) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
475 if (!duplicatedNodes.contains(input)) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
476 boolean duplicateInput = false;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
477 if (input instanceof VirtualState) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
478 duplicateInput = true;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
479 } else if (input instanceof ValueNode) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
480 Stamp inputStamp = ((ValueNode) input).stamp();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
481 if (inputStamp == StampFactory.extension() || inputStamp == StampFactory.condition()) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
482 duplicateInput = true;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
483 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
484 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
485 if (duplicateInput) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
486 duplicatedNodes.add(input);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
487 worklist.add(input);
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 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
491 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
492 }
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 /**
5861
1cb45c7dba55 retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents: 5792
diff changeset
495 * 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
496 *
1cb45c7dba55 retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents: 5792
diff changeset
497 * @param duplicatedNodes The set of duplicated nodes.
1cb45c7dba55 retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents: 5792
diff changeset
498 * @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
499 */
1cb45c7dba55 retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents: 5792
diff changeset
500 private static void retargetDependencies(HashSet<Node> duplicatedNodes, ValueAnchorNode anchor) {
1cb45c7dba55 retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents: 5792
diff changeset
501 for (Node node : duplicatedNodes) {
1cb45c7dba55 retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents: 5792
diff changeset
502 if (node instanceof ValueNode) {
1cb45c7dba55 retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents: 5792
diff changeset
503 NodeInputList<ValueNode> dependencies = ((ValueNode) node).dependencies();
1cb45c7dba55 retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents: 5792
diff changeset
504 for (int i = 0; i < dependencies.size(); i++) {
1cb45c7dba55 retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents: 5792
diff changeset
505 Node dependency = dependencies.get(i);
1cb45c7dba55 retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents: 5792
diff changeset
506 if (dependency != null && !duplicatedNodes.contains(dependency)) {
1cb45c7dba55 retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents: 5792
diff changeset
507 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
508 dependencies.set(i, anchor);
1cb45c7dba55 retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents: 5792
diff changeset
509 }
1cb45c7dba55 retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents: 5792
diff changeset
510 }
1cb45c7dba55 retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents: 5792
diff changeset
511 }
1cb45c7dba55 retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents: 5792
diff changeset
512 }
1cb45c7dba55 retarget dependencies during TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents: 5792
diff changeset
513 }
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 /**
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
516 * 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
517 *
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
518 * @param node The node whose usages are checked.
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
519 * @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
520 * @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
521 */
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
522 private static boolean hasUsagesOutside(Node node, HashSet<Node> nodeSet) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
523 for (Node usage : node.usages()) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
524 if (!nodeSet.contains(usage)) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
525 return true;
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 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
528 return false;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
529 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
530
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 * 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
533 *
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
534 * @param node The node to be replaced at outside usages.
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
535 * @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
536 * @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
537 */
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
538 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
539 for (Node usage : node.usages().snapshot()) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
540 if (!nodeSet.contains(usage)) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
541 usage.replaceFirstInput(node, replacement);
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 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
544 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
545 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
546 }