Mercurial > hg > graal-compiler

annotate graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/TailDuplicationPhase.java @ 19529:8fc336a04d77

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Create TYPE fields for LIRInstruction and CompositeValue. Renaming NodeClass#get to NodeClass#create.
author Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
date Fri, 20 Feb 2015 22:22:55 +0100
parents caad3adc5fde
children
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 /*
19093
81e464d45137 Prevent duplication of ControlFlowAnchor nodes.
Roland Schatz <roland.schatz@oracle.com>
parents: 19001
diff changeset
2 * Copyright (c) 2012, 2015, Oracle and/or its affiliates. All rights reserved.
5786
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
15259
d90e5c22ba55 Move GraalOptions to graal.compiler.common.
Josef Eisl <josef.eisl@jku.at>
parents: 15198
diff changeset
25 import static com.oracle.graal.compiler.common.GraalOptions.*;
9864
063a712fe8d8 converted remaining options in GraalOptions to new system (GRAAL-27)
Doug Simon <doug.simon@oracle.com>
parents: 9643
diff changeset
26
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
27 import java.util.*;
15470
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15261
diff changeset
28 import java.util.function.*;
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
29
15193
96bb07a5d667 Spit up and move GraalInternalError.
Josef Eisl <josef.eisl@jku.at>
parents: 15145
diff changeset
30 import com.oracle.graal.compiler.common.*;
15198
2c0cfbf454b5 Move LIRTypeTool and Stamp to graal.compiler.common.
Josef Eisl <josef.eisl@jku.at>
parents: 15193
diff changeset
31 import com.oracle.graal.compiler.common.type.*;
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
32 import com.oracle.graal.debug.*;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
33 import com.oracle.graal.graph.Graph.DuplicationReplacement;
14991
64dcb92ee75a Truffle: Change signature for Truffle calls from (PackedFrame, Arguments) to (Object[]).
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 14978
diff changeset
34 import com.oracle.graal.graph.Graph.Mark;
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
35 import com.oracle.graal.graph.*;
16841
cbd42807a31f moved NodeInfo and friends into separate com.oracle.graal.nodeinfo project so that annotation processor can be applied to the base Node class
Doug Simon <doug.simon@oracle.com>
parents: 16838
diff changeset
36 import com.oracle.graal.nodeinfo.*;
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
37 import com.oracle.graal.nodes.*;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
38 import com.oracle.graal.nodes.VirtualState.NodeClosure;
19093
81e464d45137 Prevent duplication of ControlFlowAnchor nodes.
Roland Schatz <roland.schatz@oracle.com>
parents: 19001
diff changeset
39 import com.oracle.graal.nodes.debug.*;
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
40 import com.oracle.graal.nodes.extended.*;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
41 import com.oracle.graal.nodes.java.*;
7536
1563a48b798d don't tail duplicate allocations
Lukas Stadler <lukas.stadler@jku.at>
parents: 7255
diff changeset
42 import com.oracle.graal.nodes.spi.*;
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
43 import com.oracle.graal.nodes.util.*;
11875
35bdfb9ac12f don't tail duplicate object allocations
Lukas Stadler <lukas.stadler@jku.at>
parents: 11711
diff changeset
44 import com.oracle.graal.nodes.virtual.*;
6525
2c913b643422 rename packages in graal.phases to match project name
Doug Simon <doug.simon@oracle.com>
parents: 6522
diff changeset
45 import com.oracle.graal.phases.*;
9238
8f01fe16e473 refactorings and cleanups for the removal of FixedNode.probability
Christian Haeubl <haeubl@ssw.jku.at>
parents: 9234
diff changeset
46 import com.oracle.graal.phases.graph.*;
9329
fa188fbfe3fe Perform only targeted canonicalization after tail duplication.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 9238
diff changeset
47 import com.oracle.graal.phases.tiers.*;
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
48
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
49 /**
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
50 * This class is a phase that looks for opportunities for tail duplication. The static method
18995
a2cb19764970 Rename MergeNode to AbstractMergeNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18993
diff changeset
51 * {@link #tailDuplicate(AbstractMergeNode, TailDuplicationDecision, List, PhaseContext, CanonicalizerPhase)}
11573
8a3d99fc36cf Pass canonicalizer into tail duplication.
Roland Schatz <roland.schatz@oracle.com>
parents: 10706
diff changeset
52 * can also be used to drive tail duplication from other places, e.g., inlining.
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
53 */
9329
fa188fbfe3fe Perform only targeted canonicalization after tail duplication.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 9238
diff changeset
54 public class TailDuplicationPhase extends BasePhase<PhaseContext> {
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
55
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 * 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
58 */
10533
2faa1e7ef4f3 enable TailDuplication for MergeNodes without stateAfter
Lukas Stadler <lukas.stadler@jku.at>
parents: 10009
diff changeset
59 private static final DebugMetric metricDuplicationConsidered = Debug.metric("DuplicationConsidered");
2faa1e7ef4f3 enable TailDuplication for MergeNodes without stateAfter
Lukas Stadler <lukas.stadler@jku.at>
parents: 10009
diff changeset
60 private static final DebugMetric metricDuplicationPerformed = Debug.metric("DuplicationPerformed");
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
61
11573
8a3d99fc36cf Pass canonicalizer into tail duplication.
Roland Schatz <roland.schatz@oracle.com>
parents: 10706
diff changeset
62 private final CanonicalizerPhase canonicalizer;
8a3d99fc36cf Pass canonicalizer into tail duplication.
Roland Schatz <roland.schatz@oracle.com>
parents: 10706
diff changeset
63
18255
415c79fefdb3 TailDuplicationPhase.DummyAnchorNode: add allowedUsageTypes.
Josef Eisl <josef.eisl@jku.at>
parents: 18190
diff changeset
64 @NodeInfo(allowedUsageTypes = {InputType.Guard, InputType.Anchor})
19403
7e2c87dae93e Create static final NodeClass field named TYPE in Node subclasses.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19093
diff changeset
65 static final class DummyAnchorNode extends FixedWithNextNode implements GuardingNode, AnchoringNode {
19529
8fc336a04d77 Create TYPE fields for LIRInstruction and CompositeValue. Renaming NodeClass#get to NodeClass#create.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19512
diff changeset
66 public static final NodeClass<DummyAnchorNode> TYPE = NodeClass.create(DummyAnchorNode.class);
19403
7e2c87dae93e Create static final NodeClass field named TYPE in Node subclasses.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19093
diff changeset
67
18845
f57d86eb036f removed Node factory methods
Doug Simon <doug.simon@oracle.com>
parents: 18383
diff changeset
68 public DummyAnchorNode() {
19403
7e2c87dae93e Create static final NodeClass field named TYPE in Node subclasses.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19093
diff changeset
69 super(TYPE, StampFactory.forVoid());
16895
06c15e88d383 added factory method to all Node classes; replaced Node classes instantiation with calls to factory methods; replaced identity tests on Node classes with ' == <node class>.getGenClass()' idiom
Doug Simon <doug.simon@oracle.com>
parents: 16841
diff changeset
70 }
06c15e88d383 added factory method to all Node classes; replaced Node classes instantiation with calls to factory methods; replaced identity tests on Node classes with ' == <node class>.getGenClass()' idiom
Doug Simon <doug.simon@oracle.com>
parents: 16841
diff changeset
71
15001
27c04ee36dcb input types
Lukas Stadler <lukas.stadler@oracle.com>
parents: 14991
diff changeset
72 }
27c04ee36dcb input types
Lukas Stadler <lukas.stadler@oracle.com>
parents: 14991
diff changeset
73
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
74 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
75 * This interface is used by tail duplication to let clients decide if tail duplication should
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
76 * be performed.
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
77 */
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
78 public interface TailDuplicationDecision {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
79
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
80 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
81 * Queries if tail duplication should be performed at the given merge. If this method
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
82 * returns true then the tail duplication will be performed, because all other checks have
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
83 * happened before.
15001
27c04ee36dcb input types
Lukas Stadler <lukas.stadler@oracle.com>
parents: 14991
diff changeset
84 *
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
85 * @param merge The merge at which tail duplication can be performed.
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
86 * @param fixedNodeCount The size of the set of fixed nodes that forms the base for the
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
87 * duplicated set of nodes.
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
88 * @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
89 */
18995
a2cb19764970 Rename MergeNode to AbstractMergeNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18993
diff changeset
90 boolean doTransform(AbstractMergeNode merge, int fixedNodeCount);
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
91 }
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 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
94 * A tail duplication decision closure that employs the default algorithm: Check if there are
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
95 * any phis on the merge whose stamps improve and that have usages within the duplicated set of
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
96 * fixed nodes.
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
97 */
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
98 public static final TailDuplicationDecision DEFAULT_DECISION = new TailDuplicationDecision() {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
99
18995
a2cb19764970 Rename MergeNode to AbstractMergeNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18993
diff changeset
100 public boolean doTransform(AbstractMergeNode merge, int fixedNodeCount) {
9864
063a712fe8d8 converted remaining options in GraalOptions to new system (GRAAL-27)
Doug Simon <doug.simon@oracle.com>
parents: 9643
diff changeset
101 if (fixedNodeCount < TailDuplicationTrivialSize.getValue()) {
5792
fa6ed51ac198 more aggressive tail duplication
Lukas Stadler <lukas.stadler@jku.at>
parents: 5786
diff changeset
102 return true;
fa6ed51ac198 more aggressive tail duplication
Lukas Stadler <lukas.stadler@jku.at>
parents: 5786
diff changeset
103 }
13367
413040ab993e remove some usages of HashSet
Bernhard Urban <bernhard.urban@jku.at>
parents: 13320
diff changeset
104 ArrayList<PhiNode> improvements = null;
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
105 for (PhiNode phi : merge.phis()) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
106 Stamp phiStamp = phi.stamp();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
107 for (ValueNode input : phi.values()) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
108 if (!input.stamp().equals(phiStamp)) {
13367
413040ab993e remove some usages of HashSet
Bernhard Urban <bernhard.urban@jku.at>
parents: 13320
diff changeset
109 if (improvements == null) {
413040ab993e remove some usages of HashSet
Bernhard Urban <bernhard.urban@jku.at>
parents: 13320
diff changeset
110 improvements = new ArrayList<>();
413040ab993e remove some usages of HashSet
Bernhard Urban <bernhard.urban@jku.at>
parents: 13320
diff changeset
111 }
413040ab993e remove some usages of HashSet
Bernhard Urban <bernhard.urban@jku.at>
parents: 13320
diff changeset
112 if (!improvements.contains(phi)) {
413040ab993e remove some usages of HashSet
Bernhard Urban <bernhard.urban@jku.at>
parents: 13320
diff changeset
113 improvements.add(phi);
413040ab993e remove some usages of HashSet
Bernhard Urban <bernhard.urban@jku.at>
parents: 13320
diff changeset
114 }
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
115 break;
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 }
13367
413040ab993e remove some usages of HashSet
Bernhard Urban <bernhard.urban@jku.at>
parents: 13320
diff changeset
119 if (improvements == null) {
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
120 return false;
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 FixedNode current = merge;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
123 int opportunities = 0;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
124 while (current instanceof FixedWithNextNode) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
125 current = ((FixedWithNextNode) current).next();
7536
1563a48b798d don't tail duplicate allocations
Lukas Stadler <lukas.stadler@jku.at>
parents: 7255
diff changeset
126 if (current instanceof VirtualizableAllocation) {
1563a48b798d don't tail duplicate allocations
Lukas Stadler <lukas.stadler@jku.at>
parents: 7255
diff changeset
127 return false;
1563a48b798d don't tail duplicate allocations
Lukas Stadler <lukas.stadler@jku.at>
parents: 7255
diff changeset
128 }
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
129 for (PhiNode phi : improvements) {
6433
4bd8711d824a small fix to tail duplication heuristics
Lukas Stadler <lukas.stadler@jku.at>
parents: 6411
diff changeset
130 for (Node input : current.inputs()) {
4bd8711d824a small fix to tail duplication heuristics
Lukas Stadler <lukas.stadler@jku.at>
parents: 6411
diff changeset
131 if (input == phi) {
4bd8711d824a small fix to tail duplication heuristics
Lukas Stadler <lukas.stadler@jku.at>
parents: 6411
diff changeset
132 opportunities++;
4bd8711d824a small fix to tail duplication heuristics
Lukas Stadler <lukas.stadler@jku.at>
parents: 6411
diff changeset
133 }
4bd8711d824a small fix to tail duplication heuristics
Lukas Stadler <lukas.stadler@jku.at>
parents: 6411
diff changeset
134 if (input.inputs().contains(phi)) {
4bd8711d824a small fix to tail duplication heuristics
Lukas Stadler <lukas.stadler@jku.at>
parents: 6411
diff changeset
135 opportunities++;
4bd8711d824a small fix to tail duplication heuristics
Lukas Stadler <lukas.stadler@jku.at>
parents: 6411
diff changeset
136 }
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
137 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
138 }
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 return opportunities > 0;
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 };
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
143
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
144 /**
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
145 * A tail duplication decision closure that always returns true.
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 final TailDuplicationDecision TRUE_DECISION = new TailDuplicationDecision() {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
148
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
149 @Override
18995
a2cb19764970 Rename MergeNode to AbstractMergeNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18993
diff changeset
150 public boolean doTransform(AbstractMergeNode merge, int fixedNodeCount) {
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
151 return true;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
152 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
153 };
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
154
11573
8a3d99fc36cf Pass canonicalizer into tail duplication.
Roland Schatz <roland.schatz@oracle.com>
parents: 10706
diff changeset
155 public TailDuplicationPhase(CanonicalizerPhase canonicalizer) {
8a3d99fc36cf Pass canonicalizer into tail duplication.
Roland Schatz <roland.schatz@oracle.com>
parents: 10706
diff changeset
156 this.canonicalizer = canonicalizer;
8a3d99fc36cf Pass canonicalizer into tail duplication.
Roland Schatz <roland.schatz@oracle.com>
parents: 10706
diff changeset
157 }
8a3d99fc36cf Pass canonicalizer into tail duplication.
Roland Schatz <roland.schatz@oracle.com>
parents: 10706
diff changeset
158
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
159 @Override
9329
fa188fbfe3fe Perform only targeted canonicalization after tail duplication.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 9238
diff changeset
160 protected void run(StructuredGraph graph, PhaseContext phaseContext) {
19410
61d3cb8e1280 Add generic parameter to NodeClass. Change Graph#getNodes(Class) to Graph#getNodes(NodeClass).
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19403
diff changeset
161 if (graph.hasNode(AbstractMergeNode.TYPE)) {
15470
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15261
diff changeset
162 ToDoubleFunction<FixedNode> nodeProbabilities = new FixedNodeProbabilityCache();
9234
b9cf7d0b598e removal of FixedNode.probability (draft)
Christian Haeubl <haeubl@ssw.jku.at>
parents: 9051
diff changeset
163
15470
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15261
diff changeset
164 // A snapshot is taken here, so that new MergeNode instances aren't considered for tail
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15261
diff changeset
165 // duplication.
19410
61d3cb8e1280 Add generic parameter to NodeClass. Change Graph#getNodes(Class) to Graph#getNodes(NodeClass).
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19403
diff changeset
166 for (AbstractMergeNode merge : graph.getNodes(AbstractMergeNode.TYPE).snapshot()) {
15470
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15261
diff changeset
167 if (!(merge instanceof LoopBeginNode) && nodeProbabilities.applyAsDouble(merge) >= TailDuplicationProbability.getValue()) {
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15261
diff changeset
168 tailDuplicate(merge, DEFAULT_DECISION, null, phaseContext, canonicalizer);
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15261
diff changeset
169 }
5786
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 }
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 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
175 * This method attempts to duplicate the tail of the given merge. The merge must not be a
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
176 * {@link LoopBeginNode}. If the merge is eligible for duplication (at least one fixed node in
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
177 * its tail, no {@link MonitorEnterNode}/ {@link MonitorExitNode}, non-null
19001
5a79fa76b489 Run eclipse format.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18996
diff changeset
178 * {@link AbstractMergeNode#stateAfter()}) then the decision callback is used to determine
5a79fa76b489 Run eclipse format.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18996
diff changeset
179 * whether the tail duplication should actually be performed. If replacements is non-null, then
5a79fa76b489 Run eclipse format.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18996
diff changeset
180 * this list of {@link PiNode}s is used to replace one value per merge end.
15001
27c04ee36dcb input types
Lukas Stadler <lukas.stadler@oracle.com>
parents: 14991
diff changeset
181 *
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
182 * @param merge The merge whose tail should be duplicated.
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
183 * @param decision A callback that can make the final decision if tail duplication should occur
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
184 * or not.
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
185 * @param replacements A list of {@link PiNode}s, or null. If this list is non-null then its
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
186 * size needs to match the merge's end count. Each entry can either be null or a
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
187 * {@link PiNode}, and is used to replace {@link PiNode#object()} with the
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
188 * {@link PiNode} in the duplicated branch that corresponds to the entry.
9329
fa188fbfe3fe Perform only targeted canonicalization after tail duplication.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 9238
diff changeset
189 * @param phaseContext
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
190 */
18995
a2cb19764970 Rename MergeNode to AbstractMergeNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18993
diff changeset
191 public static boolean tailDuplicate(AbstractMergeNode merge, TailDuplicationDecision decision, List<GuardedValueNode> replacements, PhaseContext phaseContext, CanonicalizerPhase canonicalizer) {
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
192 assert !(merge instanceof LoopBeginNode);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
193 assert replacements == null || replacements.size() == merge.forwardEndCount();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
194 FixedNode fixed = merge;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
195 int fixedCount = 0;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
196 while (fixed instanceof FixedWithNextNode) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
197 fixed = ((FixedWithNextNode) fixed).next();
19093
81e464d45137 Prevent duplication of ControlFlowAnchor nodes.
Roland Schatz <roland.schatz@oracle.com>
parents: 19001
diff changeset
198 if (fixed instanceof CommitAllocationNode || fixed instanceof ControlFlowAnchorNode) {
11875
35bdfb9ac12f don't tail duplicate object allocations
Lukas Stadler <lukas.stadler@jku.at>
parents: 11711
diff changeset
199 return false;
35bdfb9ac12f don't tail duplicate object allocations
Lukas Stadler <lukas.stadler@jku.at>
parents: 11711
diff changeset
200 }
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
201 fixedCount++;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
202 }
8988
02f57662b6c4 remove monitor limitation form TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents: 8558
diff changeset
203 if (fixedCount > 1) {
10533
2faa1e7ef4f3 enable TailDuplication for MergeNodes without stateAfter
Lukas Stadler <lukas.stadler@jku.at>
parents: 10009
diff changeset
204 metricDuplicationConsidered.increment();
2faa1e7ef4f3 enable TailDuplication for MergeNodes without stateAfter
Lukas Stadler <lukas.stadler@jku.at>
parents: 10009
diff changeset
205 if (decision.doTransform(merge, fixedCount)) {
2faa1e7ef4f3 enable TailDuplication for MergeNodes without stateAfter
Lukas Stadler <lukas.stadler@jku.at>
parents: 10009
diff changeset
206 metricDuplicationPerformed.increment();
11573
8a3d99fc36cf Pass canonicalizer into tail duplication.
Roland Schatz <roland.schatz@oracle.com>
parents: 10706
diff changeset
207 new DuplicationOperation(merge, replacements, canonicalizer).duplicate(phaseContext);
10533
2faa1e7ef4f3 enable TailDuplication for MergeNodes without stateAfter
Lukas Stadler <lukas.stadler@jku.at>
parents: 10009
diff changeset
208 return true;
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
209 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
210 }
8558
43ab11ee5524 counters for LoopFullUnrollPhase and TailDuplicationPhase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7539
diff changeset
211 return false;
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
212 }
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 /**
19001
5a79fa76b489 Run eclipse format.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18996
diff changeset
215 * This class encapsulates one tail duplication operation on a specific
5a79fa76b489 Run eclipse format.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18996
diff changeset
216 * {@link AbstractMergeNode}.
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
217 */
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
218 private static class DuplicationOperation {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
219
18995
a2cb19764970 Rename MergeNode to AbstractMergeNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18993
diff changeset
220 private final AbstractMergeNode merge;
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
221 private final StructuredGraph graph;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
222
18383
1518c3296cc8 use deterministic iteration order Set and Map data structures when in the scope of a replay compilation context
Doug Simon <doug.simon@oracle.com>
parents: 18378
diff changeset
223 private final Map<ValueNode, PhiNode> bottomPhis = Node.newMap();
10706
8d961f93725c Use GuardedValueNode in the inlining
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 10533
diff changeset
224 private final List<GuardedValueNode> replacements;
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
225
11573
8a3d99fc36cf Pass canonicalizer into tail duplication.
Roland Schatz <roland.schatz@oracle.com>
parents: 10706
diff changeset
226 private final CanonicalizerPhase canonicalizer;
8a3d99fc36cf Pass canonicalizer into tail duplication.
Roland Schatz <roland.schatz@oracle.com>
parents: 10706
diff changeset
227
5786
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 * Initializes the tail duplication operation without actually performing any work.
15001
27c04ee36dcb input types
Lukas Stadler <lukas.stadler@oracle.com>
parents: 14991
diff changeset
230 *
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
231 * @param merge The merge whose tail should be duplicated.
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
232 * @param replacements A list of replacement {@link PiNode}s, or null. If this is non-null,
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
233 * then the size of the list needs to match the number of end nodes at the merge.
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
234 */
18995
a2cb19764970 Rename MergeNode to AbstractMergeNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18993
diff changeset
235 public DuplicationOperation(AbstractMergeNode merge, List<GuardedValueNode> replacements, CanonicalizerPhase canonicalizer) {
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
236 this.merge = merge;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
237 this.replacements = replacements;
9602
19c5a07c7843 Introduce a graph() method that returns a StructuredGraph, to make many explicit casts unnecessary
Christian Wimmer <christian.wimmer@oracle.com>
parents: 9436
diff changeset
238 this.graph = merge.graph();
11573
8a3d99fc36cf Pass canonicalizer into tail duplication.
Roland Schatz <roland.schatz@oracle.com>
parents: 10706
diff changeset
239 this.canonicalizer = canonicalizer;
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
240 }
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 /**
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
243 * Performs the actual tail duplication:
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
244 * <ul>
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
245 * <li>Creates a new {@link ValueAnchorNode} at the beginning of the duplicated area, an
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
246 * transfers all dependencies from the merge to this anchor.</li>
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
247 * <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
248 * <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
249 * <li>Determines the complete set of duplicated nodes.</li>
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
250 * <li>Performs the actual duplication.</li>
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
251 * </ul>
15001
27c04ee36dcb input types
Lukas Stadler <lukas.stadler@oracle.com>
parents: 14991
diff changeset
252 *
9329
fa188fbfe3fe Perform only targeted canonicalization after tail duplication.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 9238
diff changeset
253 * @param phaseContext
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
254 */
9329
fa188fbfe3fe Perform only targeted canonicalization after tail duplication.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 9238
diff changeset
255 private void duplicate(PhaseContext phaseContext) {
9234
b9cf7d0b598e removal of FixedNode.probability (draft)
Christian Haeubl <haeubl@ssw.jku.at>
parents: 9051
diff changeset
256 Debug.log("tail duplication at merge %s in %s", merge, graph.method());
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
257
12686
ca8ab182026f abstracted a graph mark as a Mark object (hiding the node index)
Doug Simon <doug.simon@oracle.com>
parents: 12655
diff changeset
258 Mark startMark = graph.getMark();
9329
fa188fbfe3fe Perform only targeted canonicalization after tail duplication.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 9238
diff changeset
259
15001
27c04ee36dcb input types
Lukas Stadler <lukas.stadler@oracle.com>
parents: 14991
diff changeset
260 DummyAnchorNode anchor = addValueAnchor();
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
261
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
262 // determine the fixed nodes that should be duplicated (currently: all nodes up until
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
263 // the first control
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
264 // split, end node, deopt or return.
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
265 ArrayList<FixedNode> fixedNodes = new ArrayList<>();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
266 FixedNode fixed = merge.next();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
267 FrameState stateAfter = merge.stateAfter();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
268 while (fixed instanceof FixedWithNextNode) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
269 fixedNodes.add(fixed);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
270 if (fixed instanceof StateSplit && ((StateSplit) fixed).stateAfter() != null) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
271 stateAfter = ((StateSplit) fixed).stateAfter();
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 fixed = ((FixedWithNextNode) fixed).next();
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
9434
50f02c7d1cec Rename EndNode => AbstractEndNode and make abstract class. Introduce concrete EndNode subclass.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 9329
diff changeset
276 AbstractEndNode endAfter = createNewMerge(fixed, stateAfter);
18995
a2cb19764970 Rename MergeNode to AbstractMergeNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18993
diff changeset
277 AbstractMergeNode mergeAfter = endAfter.merge();
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
278 fixedNodes.add(endAfter);
18383
1518c3296cc8 use deterministic iteration order Set and Map data structures when in the scope of a replay compilation context
Doug Simon <doug.simon@oracle.com>
parents: 18378
diff changeset
279 final Set<Node> duplicatedNodes = buildDuplicatedNodeSet(fixedNodes, stateAfter);
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
280 mergeAfter.clearEnds();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
281 expandDuplicated(duplicatedNodes, mergeAfter);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
282
19512
caad3adc5fde Change forward ends to type EndNode and not AbstractEndNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19410
diff changeset
283 List<EndNode> endSnapshot = merge.forwardEnds().snapshot();
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
284 List<PhiNode> phiSnapshot = merge.phis().snapshot();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
285
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
286 int endIndex = 0;
19512
caad3adc5fde Change forward ends to type EndNode and not AbstractEndNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19410
diff changeset
287 for (final EndNode forwardEnd : merge.forwardEnds()) {
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
288 Map<Node, Node> duplicates;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
289 if (replacements == null || replacements.get(endIndex) == null) {
11675
77d9f12797c5 Use NodeMap in inlining utility when number of nodes is high.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 11652
diff changeset
290 duplicates = graph.addDuplicates(duplicatedNodes, graph, duplicatedNodes.size(), (DuplicationReplacement) null);
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
291 } else {
18383
1518c3296cc8 use deterministic iteration order Set and Map data structures when in the scope of a replay compilation context
Doug Simon <doug.simon@oracle.com>
parents: 18378
diff changeset
292 Map<Node, Node> replace = Node.newMap();
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
293 replace.put(replacements.get(endIndex).object(), replacements.get(endIndex));
11675
77d9f12797c5 Use NodeMap in inlining utility when number of nodes is high.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 11652
diff changeset
294 duplicates = graph.addDuplicates(duplicatedNodes, graph, duplicatedNodes.size(), replace);
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
295 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
296 for (Map.Entry<ValueNode, PhiNode> phi : bottomPhis.entrySet()) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
297 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
298 }
19512
caad3adc5fde Change forward ends to type EndNode and not AbstractEndNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19410
diff changeset
299 mergeAfter.addForwardEnd((EndNode) duplicates.get(endAfter));
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
300
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
301 // re-wire the duplicated ValueAnchorNode to the predecessor of the corresponding
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
302 // EndNode
15001
27c04ee36dcb input types
Lukas Stadler <lukas.stadler@oracle.com>
parents: 14991
diff changeset
303 FixedWithNextNode anchorDuplicate = (FixedWithNextNode) duplicates.get(anchor);
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
304 // move dependencies on the ValueAnchorNode to the previous BeginNode
18993
480bd3b1adcd Rename BeginNode => AbstractBeginNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18937
diff changeset
305 AbstractBeginNode prevBegin = AbstractBeginNode.prevBegin(forwardEnd);
15001
27c04ee36dcb input types
Lukas Stadler <lukas.stadler@oracle.com>
parents: 14991
diff changeset
306 anchorDuplicate.replaceAtUsages(InputType.Guard, prevBegin);
27c04ee36dcb input types
Lukas Stadler <lukas.stadler@oracle.com>
parents: 14991
diff changeset
307 anchorDuplicate.replaceAtUsages(InputType.Anchor, prevBegin);
18937
ff232ff8d028 Add utility Node#hasNoUsages.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18845
diff changeset
308 assert anchorDuplicate.hasNoUsages();
15001
27c04ee36dcb input types
Lukas Stadler <lukas.stadler@oracle.com>
parents: 14991
diff changeset
309
27c04ee36dcb input types
Lukas Stadler <lukas.stadler@oracle.com>
parents: 14991
diff changeset
310 FixedNode next = anchorDuplicate.next();
27c04ee36dcb input types
Lukas Stadler <lukas.stadler@oracle.com>
parents: 14991
diff changeset
311 anchorDuplicate.setNext(null);
27c04ee36dcb input types
Lukas Stadler <lukas.stadler@oracle.com>
parents: 14991
diff changeset
312 ((FixedWithNextNode) forwardEnd.predecessor()).setNext(next);
27c04ee36dcb input types
Lukas Stadler <lukas.stadler@oracle.com>
parents: 14991
diff changeset
313 anchorDuplicate.safeDelete();
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
314
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
315 // re-wire the phi duplicates to the correct input
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
316 for (PhiNode phi : phiSnapshot) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
317 PhiNode phiDuplicate = (PhiNode) duplicates.get(phi);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
318 phiDuplicate.replaceAtUsages(phi.valueAt(forwardEnd));
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
319 phiDuplicate.safeDelete();
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 endIndex++;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
322 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
323 GraphUtil.killCFG(merge);
9434
50f02c7d1cec Rename EndNode => AbstractEndNode and make abstract class. Introduce concrete EndNode subclass.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 9329
diff changeset
324 for (AbstractEndNode forwardEnd : endSnapshot) {
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
325 forwardEnd.safeDelete();
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 for (PhiNode phi : phiSnapshot) {
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
328 // these phis should go away, but they still need to be anchored to a merge to be
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
329 // valid...
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
330 if (phi.isAlive()) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
331 phi.setMerge(mergeAfter);
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 }
11573
8a3d99fc36cf Pass canonicalizer into tail duplication.
Roland Schatz <roland.schatz@oracle.com>
parents: 10706
diff changeset
334 canonicalizer.applyIncremental(graph, phaseContext, startMark);
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
335 Debug.dump(graph, "After tail duplication at %s", merge);
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 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
339 * Inserts a new ValueAnchorNode after the merge and transfers all dependency-usages (not
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
340 * phis) to this ValueAnchorNode.
15001
27c04ee36dcb input types
Lukas Stadler <lukas.stadler@oracle.com>
parents: 14991
diff changeset
341 *
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
342 * @return The new {@link ValueAnchorNode} that was created.
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
343 */
15001
27c04ee36dcb input types
Lukas Stadler <lukas.stadler@oracle.com>
parents: 14991
diff changeset
344 private DummyAnchorNode addValueAnchor() {
18845
f57d86eb036f removed Node factory methods
Doug Simon <doug.simon@oracle.com>
parents: 18383
diff changeset
345 DummyAnchorNode anchor = graph.add(new DummyAnchorNode());
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
346 graph.addAfterFixed(merge, anchor);
15001
27c04ee36dcb input types
Lukas Stadler <lukas.stadler@oracle.com>
parents: 14991
diff changeset
347 merge.replaceAtUsages(InputType.Guard, anchor);
27c04ee36dcb input types
Lukas Stadler <lukas.stadler@oracle.com>
parents: 14991
diff changeset
348 merge.replaceAtUsages(InputType.Anchor, anchor);
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
349 return anchor;
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 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
353 * Given a set of fixed nodes, this method determines the set of fixed and floating nodes
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
354 * that needs to be duplicated, i.e., all nodes that due to data flow and other dependencies
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
355 * needs to be duplicated.
15001
27c04ee36dcb input types
Lukas Stadler <lukas.stadler@oracle.com>
parents: 14991
diff changeset
356 *
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
357 * @param fixedNodes The set of fixed nodes that should be duplicated.
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
358 * @param stateAfter The frame state of the merge that follows the set of fixed nodes. All
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
359 * {@link ValueNode}s reachable from this state are considered to be reachable
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
360 * from within the duplicated set of nodes.
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
361 * @return The set of nodes that need to be duplicated.
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
362 */
18383
1518c3296cc8 use deterministic iteration order Set and Map data structures when in the scope of a replay compilation context
Doug Simon <doug.simon@oracle.com>
parents: 18378
diff changeset
363 private Set<Node> buildDuplicatedNodeSet(final ArrayList<FixedNode> fixedNodes, FrameState stateAfter) {
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
364 final NodeBitMap aboveBound = graph.createNodeBitMap();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
365 final NodeBitMap belowBound = graph.createNodeBitMap();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
366
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
367 final Deque<Node> worklist = new ArrayDeque<>();
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 // Build the set of nodes that have (transitive) usages within the duplicatedNodes.
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
370 // This is achieved by iterating all nodes that are reachable via inputs from the the
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
371 // fixed nodes.
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
372 aboveBound.markAll(fixedNodes);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
373 worklist.addAll(fixedNodes);
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 // the phis at the original merge should always be duplicated
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
376 for (PhiNode phi : merge.phis()) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
377 aboveBound.mark(phi);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
378 worklist.add(phi);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
379 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
380
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
381 NodeClosure<Node> aboveClosure = new NodeClosure<Node>() {
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 @Override
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
384 public void apply(Node usage, Node node) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
385 if (node instanceof PhiNode && !fixedNodes.contains(((PhiNode) node).merge())) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
386 // 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
387 } else if (node instanceof FixedNode) {
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
388 // stop iterating: fixed nodes within the given set are traversal roots
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
389 // anyway, and all other
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
390 // fixed nodes are known to be outside.
13320
c258331fdde6 removed support for external nodes (GRAAL-508)
Doug Simon <doug.simon@oracle.com>
parents: 12686
diff changeset
391 } else if (!aboveBound.isMarked(node)) {
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
392 worklist.add(node);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
393 aboveBound.mark(node);
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 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
396 };
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 if (stateAfter != null) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
399 stateAfter.applyToNonVirtual(aboveClosure);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
400 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
401 while (!worklist.isEmpty()) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
402 Node current = worklist.remove();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
403 for (Node input : current.inputs()) {
13320
c258331fdde6 removed support for external nodes (GRAAL-508)
Doug Simon <doug.simon@oracle.com>
parents: 12686
diff changeset
404 aboveClosure.apply(current, input);
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
405 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
406 }
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 // Build the set of nodes that have (transitive) inputs within the duplicatedNodes.
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
409 // This is achieved by iterating all nodes that are reachable via usages from the fixed
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
410 // nodes.
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
411 belowBound.markAll(fixedNodes);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
412 worklist.addAll(fixedNodes);
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 // the phis at the original merge should always be duplicated
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
415 for (PhiNode phi : merge.phis()) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
416 belowBound.mark(phi);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
417 worklist.add(phi);
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 while (!worklist.isEmpty()) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
421 Node current = worklist.remove();
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
422 for (Node usage : current.usages()) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
423 if (usage instanceof PhiNode && !fixedNodes.contains(((PhiNode) usage).merge())) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
424 // 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
425 } else if (usage instanceof FixedNode) {
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
426 // stop iterating: fixed nodes within the given set are traversal roots
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
427 // anyway, and all other
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
428 // fixed nodes are known to be outside.
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
429 } else if (!belowBound.isMarked(usage)) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
430 worklist.add(usage);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
431 belowBound.mark(usage);
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 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
434 }
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 // build the intersection
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
437 belowBound.intersect(aboveBound);
18383
1518c3296cc8 use deterministic iteration order Set and Map data structures when in the scope of a replay compilation context
Doug Simon <doug.simon@oracle.com>
parents: 18378
diff changeset
438 Set<Node> result = Node.newSet();
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
439 for (Node node : belowBound) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
440 result.add(node);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
441 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
442 return result;
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
443 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
444
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
445 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
446 * Creates a new merge and end node construct at the end of the duplicated area. While it is
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
447 * useless in itself (merge with only one end) it simplifies the later duplication step.
15001
27c04ee36dcb input types
Lukas Stadler <lukas.stadler@oracle.com>
parents: 14991
diff changeset
448 *
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
449 * @param successor The successor of the duplicated set of nodes, i.e., the first node that
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
450 * should not be duplicated.
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
451 * @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
452 * @return The newly created end node.
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
453 */
9434
50f02c7d1cec Rename EndNode => AbstractEndNode and make abstract class. Introduce concrete EndNode subclass.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 9329
diff changeset
454 private AbstractEndNode createNewMerge(FixedNode successor, FrameState stateAfterMerge) {
19512
caad3adc5fde Change forward ends to type EndNode and not AbstractEndNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19410
diff changeset
455 MergeNode newBottomMerge = graph.add(new MergeNode());
caad3adc5fde Change forward ends to type EndNode and not AbstractEndNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19410
diff changeset
456 EndNode newBottomEnd = graph.add(new EndNode());
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
457 newBottomMerge.addForwardEnd(newBottomEnd);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
458 newBottomMerge.setStateAfter(stateAfterMerge);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
459 ((FixedWithNextNode) successor.predecessor()).setNext(newBottomEnd);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
460 newBottomMerge.setNext(successor);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
461 return newBottomEnd;
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
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
464 /**
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
465 * 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
466 * <ul>
15006
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
467 * <li>Inputs of type {@link InputType#Value} into the duplicated set will be rerouted to a
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
468 * new phi node.</li>
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
469 * <li>Inputs of type {@link InputType#Association}, {@link InputType#Condition} and
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
470 * {@link InputType#State} into the duplicated set will be rerouted to a duplicated version
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
471 * of the inside node.</li>
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
472 * <li>Dependencies into the duplicated nodes will be replaced with dependencies on the
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
473 * merge.</li>
15006
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
474 * <li>Inputs of type {@link InputType#Association}, {@link InputType#Condition} and
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
475 * {@link InputType#State} to outside the duplicated set will cause the outside node to be
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
476 * pulled into the duplicated set.</li>
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
477 * </ul>
15001
27c04ee36dcb input types
Lukas Stadler <lukas.stadler@oracle.com>
parents: 14991
diff changeset
478 *
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
479 * @param duplicatedNodes The set of duplicated nodes that will be modified (expanded).
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
480 * @param newBottomMerge The merge that follows the duplicated set of nodes. It will be used
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
481 * for newly created phis and to as a target for dependencies that pointed into
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7255
diff changeset
482 * the duplicated set of nodes.
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
483 */
18995
a2cb19764970 Rename MergeNode to AbstractMergeNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18993
diff changeset
484 private void expandDuplicated(Set<Node> duplicatedNodes, AbstractMergeNode newBottomMerge) {
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
485 Deque<Node> worklist = new ArrayDeque<>(duplicatedNodes);
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
486
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
487 while (!worklist.isEmpty()) {
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
488 Node duplicated = worklist.remove();
15006
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
489 processUsages(duplicated, duplicatedNodes, newBottomMerge, worklist);
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
490 processInputs(duplicated, duplicatedNodes, worklist);
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
491 }
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
492 }
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
493
18995
a2cb19764970 Rename MergeNode to AbstractMergeNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18993
diff changeset
494 private void processUsages(Node duplicated, Set<Node> duplicatedNodes, AbstractMergeNode newBottomMerge, Deque<Node> worklist) {
18383
1518c3296cc8 use deterministic iteration order Set and Map data structures when in the scope of a replay compilation context
Doug Simon <doug.simon@oracle.com>
parents: 18378
diff changeset
495 Set<Node> unique = Node.newSet();
15006
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
496 duplicated.usages().snapshotTo(unique);
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
497 Node newOutsideClone = null;
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
498 for (Node usage : unique) {
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
499 if (!duplicatedNodes.contains(usage)) {
17008
81c9a1fc9072 select generated input and successor iterators if Node.USE_GENERATED_NODES
Doug Simon <doug.simon@oracle.com>
parents: 16919
diff changeset
500 NodePosIterator iter = usage.inputs().iterator();
15006
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
501 while (iter.hasNext()) {
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
502 Position pos = iter.nextPosition();
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
503 if (pos.get(usage) == duplicated) {
17210
ef64e2682bb6 added Edges class to consolidate code operating on set of input or successor edges and to better isolate magic used to access edges
Doug Simon <doug.simon@oracle.com>
parents: 17008
diff changeset
504 switch (pos.getInputType()) {
15019
3498761a33d8 differentiate between tightly coupling edges (Extension) and loosely coupling edges (Association)
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15006
diff changeset
505 case Extension:
15006
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
506 case Condition:
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
507 case State:
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
508 // clone the offending node to the outside
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
509 if (newOutsideClone == null) {
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
510 newOutsideClone = duplicated.copyWithInputs();
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
511 // this might cause other nodes to have outside usages
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
512 for (Node input : newOutsideClone.inputs()) {
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
513 if (duplicatedNodes.contains(input)) {
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
514 worklist.add(input);
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
515 }
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
516 }
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
517 }
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
518 pos.set(usage, newOutsideClone);
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
519 break;
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
520 case Guard:
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
521 case Anchor:
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
522 // re-route dependencies to the merge
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
523 pos.set(usage, newBottomMerge);
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
524 break;
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
525 case Value:
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
526 // introduce a new phi
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
527 ValueNode node = (ValueNode) duplicated;
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
528 PhiNode newPhi = bottomPhis.get(node);
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
529 if (newPhi == null) {
18845
f57d86eb036f removed Node factory methods
Doug Simon <doug.simon@oracle.com>
parents: 18383
diff changeset
530 newPhi = graph.addWithoutUnique(new ValuePhiNode(node.stamp().unrestricted(), newBottomMerge));
15006
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
531 bottomPhis.put(node, newPhi);
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
532 newPhi.addInput(node);
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
533 }
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
534 pos.set(usage, newPhi);
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
535 break;
15019
3498761a33d8 differentiate between tightly coupling edges (Extension) and loosely coupling edges (Association)
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15006
diff changeset
536 case Association:
15006
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
537 default:
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
538 throw GraalInternalError.shouldNotReachHere();
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
539 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
540 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
541 }
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
18383
1518c3296cc8 use deterministic iteration order Set and Map data structures when in the scope of a replay compilation context
Doug Simon <doug.simon@oracle.com>
parents: 18378
diff changeset
546 private void processInputs(Node duplicated, Set<Node> duplicatedNodes, Deque<Node> worklist) {
15006
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
547 // check if this node has an input that lies outside and cannot be shared
17008
81c9a1fc9072 select generated input and successor iterators if Node.USE_GENERATED_NODES
Doug Simon <doug.simon@oracle.com>
parents: 16919
diff changeset
548 NodePosIterator iter = duplicated.inputs().iterator();
15006
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
549 while (iter.hasNext()) {
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
550 Position pos = iter.nextPosition();
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
551 Node input = pos.get(duplicated);
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
552 if (input != null && !duplicatedNodes.contains(input)) {
17210
ef64e2682bb6 added Edges class to consolidate code operating on set of input or successor edges and to better isolate magic used to access edges
Doug Simon <doug.simon@oracle.com>
parents: 17008
diff changeset
553 switch (pos.getInputType()) {
15019
3498761a33d8 differentiate between tightly coupling edges (Extension) and loosely coupling edges (Association)
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15006
diff changeset
554 case Extension:
15006
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
555 case Condition:
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
556 case State:
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
557 if (input != merge) {
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
558 duplicatedNodes.add(input);
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
559 worklist.add(input);
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
560 }
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
561 break;
15019
3498761a33d8 differentiate between tightly coupling edges (Extension) and loosely coupling edges (Association)
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15006
diff changeset
562 case Association:
15006
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
563 case Guard:
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
564 case Anchor:
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
565 case Value:
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
566 // no change needed
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
567 break;
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
568 default:
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
569 throw GraalInternalError.shouldNotReachHere();
e60ea0bf468d remove StampFactory.dependency/extension/condition
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15001
diff changeset
570 }
5786
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
571 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
572 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
573 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
574 }
f69a406355b2 new tail duplication phase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
575 }