truffle: graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/TailDuplicationPhase.java annotate

annotate graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/TailDuplicationPhase.java @ 8988:02f57662b6c4

remove monitor limitation form TailDuplicationPhase

author	Lukas Stadler <lukas.stadler@jku.at>
date	Wed, 10 Apr 2013 15:57:30 +0200
parents	43ab11ee5524
children	8e093f170343

rev	line source
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	1 /*
8988 02f57662b6c4 remove monitor limitation form TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 8558 diff changeset	2 * Copyright (c) 2012, 2013, 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
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	25 import java.util.*;
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	26
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	27 import com.oracle.graal.debug.*;
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	28 import com.oracle.graal.graph.Graph.DuplicationReplacement;
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	29 import com.oracle.graal.graph.*;
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	30 import com.oracle.graal.nodes.*;
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	31 import com.oracle.graal.nodes.VirtualState.NodeClosure;
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	32 import com.oracle.graal.nodes.extended.*;
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	33 import com.oracle.graal.nodes.java.*;
7536 1563a48b798d don't tail duplicate allocations Lukas Stadler <lukas.stadler@jku.at> parents: 7255 diff changeset	34 import com.oracle.graal.nodes.spi.*;
5786 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.*;
6525 2c913b643422 rename packages in graal.phases to match project name Doug Simon <doug.simon@oracle.com> parents: 6522 diff changeset	37 import com.oracle.graal.phases.*;
5786 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 /**
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	40 * This class is a phase that looks for opportunities for tail duplication. The static method
7530 5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	41 * {@link #tailDuplicate(MergeNode, TailDuplicationDecision, List)} can also be used to drive tail
5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	42 * duplication from other places, e.g., inlining.
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	43 */
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	44 public class TailDuplicationPhase extends Phase {
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 /*
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	47 * 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	48 */
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 /**
7530 5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	55 * 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	56 * be performed.
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	57 */
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	58 public interface TailDuplicationDecision {
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 /**
7530 5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	61 * 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	62 * 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	63 * happened before.
5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	64 *
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	65 * @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	66 * @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	67 * duplicated set of nodes.
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	68 * @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	69 */
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	70 boolean doTransform(MergeNode merge, int fixedNodeCount);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	71 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	72
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	73 /**
7530 5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	74 * 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	75 * 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	76 * fixed nodes.
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 static final TailDuplicationDecision DEFAULT_DECISION = new 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 public boolean doTransform(MergeNode merge, int fixedNodeCount) {
5792 fa6ed51ac198 more aggressive tail duplication Lukas Stadler <lukas.stadler@jku.at> parents: 5786 diff changeset	81 if (fixedNodeCount < GraalOptions.TailDuplicationTrivialSize) {
fa6ed51ac198 more aggressive tail duplication Lukas Stadler <lukas.stadler@jku.at> parents: 5786 diff changeset	82 return true;
fa6ed51ac198 more aggressive tail duplication Lukas Stadler <lukas.stadler@jku.at> parents: 5786 diff changeset	83 }
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	84 HashSet<PhiNode> improvements = new HashSet<>();
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	85 for (PhiNode phi : merge.phis()) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	86 Stamp phiStamp = phi.stamp();
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	87 for (ValueNode input : phi.values()) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	88 if (!input.stamp().equals(phiStamp)) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	89 improvements.add(phi);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	90 break;
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 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	94 if (improvements.isEmpty()) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	95 return false;
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	96 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	97 FixedNode current = merge;
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	98 int opportunities = 0;
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	99 while (current instanceof FixedWithNextNode) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	100 current = ((FixedWithNextNode) current).next();
7536 1563a48b798d don't tail duplicate allocations Lukas Stadler <lukas.stadler@jku.at> parents: 7255 diff changeset	101 if (current instanceof VirtualizableAllocation) {
1563a48b798d don't tail duplicate allocations Lukas Stadler <lukas.stadler@jku.at> parents: 7255 diff changeset	102 return false;
1563a48b798d don't tail duplicate allocations Lukas Stadler <lukas.stadler@jku.at> parents: 7255 diff changeset	103 }
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	104 for (PhiNode phi : improvements) {
6433 4bd8711d824a small fix to tail duplication heuristics Lukas Stadler <lukas.stadler@jku.at> parents: 6411 diff changeset	105 for (Node input : current.inputs()) {
4bd8711d824a small fix to tail duplication heuristics Lukas Stadler <lukas.stadler@jku.at> parents: 6411 diff changeset	106 if (input == phi) {
4bd8711d824a small fix to tail duplication heuristics Lukas Stadler <lukas.stadler@jku.at> parents: 6411 diff changeset	107 opportunities++;
4bd8711d824a small fix to tail duplication heuristics Lukas Stadler <lukas.stadler@jku.at> parents: 6411 diff changeset	108 }
4bd8711d824a small fix to tail duplication heuristics Lukas Stadler <lukas.stadler@jku.at> parents: 6411 diff changeset	109 if (input.inputs().contains(phi)) {
4bd8711d824a small fix to tail duplication heuristics Lukas Stadler <lukas.stadler@jku.at> parents: 6411 diff changeset	110 opportunities++;
4bd8711d824a small fix to tail duplication heuristics Lukas Stadler <lukas.stadler@jku.at> parents: 6411 diff changeset	111 }
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	112 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	113 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	114 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	115 return opportunities > 0;
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
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	119 /**
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	120 * A tail duplication decision closure that always returns true.
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 public static final TailDuplicationDecision TRUE_DECISION = new TailDuplicationDecision() {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	123
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	124 @Override
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	125 public boolean doTransform(MergeNode merge, int fixedNodeCount) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	126 return true;
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
8558 43ab11ee5524 counters for LoopFullUnrollPhase and TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 7539 diff changeset	130 private int tailDuplicationCount;
43ab11ee5524 counters for LoopFullUnrollPhase and TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 7539 diff changeset	131
43ab11ee5524 counters for LoopFullUnrollPhase and TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 7539 diff changeset	132 public int getTailDuplicationCount() {
43ab11ee5524 counters for LoopFullUnrollPhase and TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 7539 diff changeset	133 return tailDuplicationCount;
43ab11ee5524 counters for LoopFullUnrollPhase and TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 7539 diff changeset	134 }
43ab11ee5524 counters for LoopFullUnrollPhase and TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 7539 diff changeset	135
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	136 @Override
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	137 protected void run(StructuredGraph graph) {
7530 5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	138 // A snapshot is taken here, so that new MergeNode instances aren't considered for tail
5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	139 // duplication.
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	140 for (MergeNode merge : graph.getNodes(MergeNode.class).snapshot()) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	141 if (!(merge instanceof LoopBeginNode) && merge.probability() >= GraalOptions.TailDuplicationProbability) {
8558 43ab11ee5524 counters for LoopFullUnrollPhase and TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 7539 diff changeset	142 if (tailDuplicate(merge, DEFAULT_DECISION, null)) {
43ab11ee5524 counters for LoopFullUnrollPhase and TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 7539 diff changeset	143 tailDuplicationCount++;
43ab11ee5524 counters for LoopFullUnrollPhase and TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 7539 diff changeset	144 }
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	145 }
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 }
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 /**
7530 5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	150 * 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	151 * {@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	152 * its tail, no {@link MonitorEnterNode}/ {@link MonitorExitNode}, non-null
5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	153 * {@link MergeNode#stateAfter()}) then the decision callback is used to determine whether the
5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	154 * tail duplication should actually be performed. If replacements is non-null, then this list of
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	155 * {@link PiNode}s is used to replace one value per merge end.
7530 5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	156 *
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	157 * @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	158 * @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	159 * or not.
5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	160 * @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	161 * 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	162 * {@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	163 * {@link PiNode} in the duplicated branch that corresponds to the entry.
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	164 */
8558 43ab11ee5524 counters for LoopFullUnrollPhase and TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 7539 diff changeset	165 public static boolean tailDuplicate(MergeNode merge, TailDuplicationDecision decision, List<PiNode> replacements) {
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	166 assert !(merge instanceof LoopBeginNode);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	167 assert replacements == null \|\| replacements.size() == merge.forwardEndCount();
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	168 FixedNode fixed = merge;
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	169 int fixedCount = 0;
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	170 while (fixed instanceof FixedWithNextNode) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	171 fixed = ((FixedWithNextNode) fixed).next();
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	172 fixedCount++;
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	173 }
8988 02f57662b6c4 remove monitor limitation form TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 8558 diff changeset	174 if (fixedCount > 1) {
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	175 if (fixed instanceof EndNode && !(((EndNode) fixed).merge() instanceof LoopBeginNode)) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	176 metricDuplicationEnd.increment();
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	177 if (decision.doTransform(merge, fixedCount)) {
5792 fa6ed51ac198 more aggressive tail duplication Lukas Stadler <lukas.stadler@jku.at> parents: 5786 diff changeset	178 metricDuplicationEndPerformed.increment();
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	179 new DuplicationOperation(merge, replacements).duplicate();
8558 43ab11ee5524 counters for LoopFullUnrollPhase and TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 7539 diff changeset	180 return true;
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	181 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	182 } else if (merge.stateAfter() != null) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	183 metricDuplicationOther.increment();
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	184 if (decision.doTransform(merge, fixedCount)) {
5792 fa6ed51ac198 more aggressive tail duplication Lukas Stadler <lukas.stadler@jku.at> parents: 5786 diff changeset	185 metricDuplicationOtherPerformed.increment();
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	186 new DuplicationOperation(merge, replacements).duplicate();
8558 43ab11ee5524 counters for LoopFullUnrollPhase and TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 7539 diff changeset	187 return true;
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	188 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	189 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	190 }
8558 43ab11ee5524 counters for LoopFullUnrollPhase and TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 7539 diff changeset	191 return false;
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	192 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	193
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	194 /**
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	195 * 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	196 */
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	197 private static class DuplicationOperation {
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 private final MergeNode merge;
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	200 private final StructuredGraph graph;
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	201
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	202 private final HashMap<ValueNode, PhiNode> bottomPhis = new HashMap<>();
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	203 private final List<PiNode> replacements;
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	204
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	205 /**
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	206 * Initializes the tail duplication operation without actually performing any work.
7530 5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	207 *
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	208 * @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	209 * @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	210 * 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	211 */
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	212 public DuplicationOperation(MergeNode merge, List<PiNode> replacements) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	213 this.merge = merge;
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	214 this.replacements = replacements;
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	215 this.graph = (StructuredGraph) merge.graph();
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	216 }
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 /**
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	219 * Performs the actual tail duplication:
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	220 * <ul>
7530 5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	221 * <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	222 * 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	223 * <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	224 * <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	225 * <li>Determines the complete set of duplicated nodes.</li>
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	226 * <li>Performs the actual duplication.</li>
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	227 * </ul>
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 private void duplicate() {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	230 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	231
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	232 ValueAnchorNode anchor = addValueAnchor();
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	233
7530 5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	234 // 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	235 // the first control
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	236 // split, end node, deopt or return.
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	237 ArrayList<FixedNode> fixedNodes = new ArrayList<>();
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	238 FixedNode fixed = merge.next();
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	239 FrameState stateAfter = merge.stateAfter();
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	240 while (fixed instanceof FixedWithNextNode) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	241 fixedNodes.add(fixed);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	242 if (fixed instanceof StateSplit && ((StateSplit) fixed).stateAfter() != null) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	243 stateAfter = ((StateSplit) fixed).stateAfter();
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	244 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	245 fixed = ((FixedWithNextNode) fixed).next();
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	246 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	247
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	248 EndNode endAfter = createNewMerge(fixed, stateAfter);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	249 MergeNode mergeAfter = endAfter.merge();
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	250 fixedNodes.add(endAfter);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	251 final HashSet<Node> duplicatedNodes = buildDuplicatedNodeSet(fixedNodes, stateAfter);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	252 mergeAfter.clearEnds();
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	253 expandDuplicated(duplicatedNodes, mergeAfter);
5861 1cb45c7dba55 retarget dependencies during TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 5792 diff changeset	254 retargetDependencies(duplicatedNodes, anchor);
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	255
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	256 List<EndNode> endSnapshot = merge.forwardEnds().snapshot();
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	257 List<PhiNode> phiSnapshot = merge.phis().snapshot();
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	258
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	259 int endIndex = 0;
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	260 for (final EndNode forwardEnd : merge.forwardEnds()) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	261 Map<Node, Node> duplicates;
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	262 if (replacements == null \|\| replacements.get(endIndex) == null) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	263 duplicates = graph.addDuplicates(duplicatedNodes, (DuplicationReplacement) null);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	264 } else {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	265 HashMap<Node, Node> replace = new HashMap<>();
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	266 replace.put(replacements.get(endIndex).object(), replacements.get(endIndex));
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	267 duplicates = graph.addDuplicates(duplicatedNodes, replace);
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 for (Map.Entry<ValueNode, PhiNode> phi : bottomPhis.entrySet()) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	270 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	271 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	272 mergeAfter.addForwardEnd((EndNode) duplicates.get(endAfter));
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	273
7530 5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	274 // 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	275 // EndNode
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	276 FixedNode anchorDuplicate = (FixedNode) duplicates.get(anchor);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	277 ((FixedWithNextNode) forwardEnd.predecessor()).setNext(anchorDuplicate);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	278 // move dependencies on the ValueAnchorNode to the previous BeginNode
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	279 BeginNode prevBegin = BeginNode.prevBegin(anchorDuplicate);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	280 anchorDuplicate.replaceAtUsages(prevBegin);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	281
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	282 // re-wire the phi duplicates to the correct input
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	283 for (PhiNode phi : phiSnapshot) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	284 PhiNode phiDuplicate = (PhiNode) duplicates.get(phi);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	285 for (Node usage : phiDuplicate.usages()) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	286 if (usage instanceof ValueNode) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	287 ((ValueNode) usage).dependencies().add(prevBegin);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	288 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	289 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	290 phiDuplicate.replaceAtUsages(phi.valueAt(forwardEnd));
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	291 phiDuplicate.safeDelete();
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	292 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	293 endIndex++;
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	294 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	295 GraphUtil.killCFG(merge);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	296 for (EndNode forwardEnd : endSnapshot) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	297 forwardEnd.safeDelete();
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	298 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	299 for (PhiNode phi : phiSnapshot) {
7530 5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	300 // 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	301 // valid...
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	302 if (phi.isAlive()) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	303 phi.setMerge(mergeAfter);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	304 }
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 Debug.dump(graph, "After tail duplication at %s", merge);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	307 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	308
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	309 /**
7530 5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	310 * 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	311 * phis) to this ValueAnchorNode.
5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	312 *
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	313 * @return The new {@link ValueAnchorNode} that was created.
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 private ValueAnchorNode addValueAnchor() {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	316 ValueAnchorNode anchor = graph.add(new ValueAnchorNode());
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	317 graph.addAfterFixed(merge, anchor);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	318 for (Node usage : merge.usages().snapshot()) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	319 if (usage instanceof PhiNode && ((PhiNode) usage).merge() == merge) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	320 // nothing to do
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	321 } else {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	322 usage.replaceFirstInput(merge, anchor);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	323 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	324 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	325 return anchor;
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
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	328 /**
7530 5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	329 * 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	330 * 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	331 * needs to be duplicated.
5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	332 *
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	333 * @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	334 * @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	335 * {@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	336 * from within the duplicated set of nodes.
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	337 * @return The set of nodes that need to be duplicated.
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	338 */
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	339 private HashSet<Node> buildDuplicatedNodeSet(final ArrayList<FixedNode> fixedNodes, FrameState stateAfter) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	340 final NodeBitMap aboveBound = graph.createNodeBitMap();
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	341 final NodeBitMap belowBound = graph.createNodeBitMap();
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	342
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	343 final Deque<Node> worklist = new ArrayDeque<>();
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	344
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	345 // 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	346 // 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	347 // fixed nodes.
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	348 aboveBound.markAll(fixedNodes);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	349 worklist.addAll(fixedNodes);
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 // the phis at the original merge should always be duplicated
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	352 for (PhiNode phi : merge.phis()) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	353 aboveBound.mark(phi);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	354 worklist.add(phi);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	355 }
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 NodeClosure<Node> aboveClosure = new NodeClosure<Node>() {
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 @Override
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	360 public void apply(Node usage, Node node) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	361 if (node instanceof PhiNode && !fixedNodes.contains(((PhiNode) node).merge())) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	362 // 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	363 } else if (node instanceof FixedNode) {
7530 5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	364 // 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	365 // anyway, and all other
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	366 // fixed nodes are known to be outside.
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	367 } else if (!aboveBound.isMarked(node)) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	368 worklist.add(node);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	369 aboveBound.mark(node);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	370 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	371 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	372 };
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	373
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	374 if (stateAfter != null) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	375 stateAfter.applyToNonVirtual(aboveClosure);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	376 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	377 while (!worklist.isEmpty()) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	378 Node current = worklist.remove();
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	379 for (Node input : current.inputs()) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	380 aboveClosure.apply(current, input);
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 // 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	385 // 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	386 // nodes.
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	387 belowBound.markAll(fixedNodes);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	388 worklist.addAll(fixedNodes);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	389
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	390 // the phis at the original merge should always be duplicated
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	391 for (PhiNode phi : merge.phis()) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	392 belowBound.mark(phi);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	393 worklist.add(phi);
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 while (!worklist.isEmpty()) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	397 Node current = worklist.remove();
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	398 for (Node usage : current.usages()) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	399 if (usage instanceof PhiNode && !fixedNodes.contains(((PhiNode) usage).merge())) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	400 // 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	401 } else if (usage instanceof FixedNode) {
7530 5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	402 // 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	403 // anyway, and all other
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	404 // fixed nodes are known to be outside.
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	405 } else if (!belowBound.isMarked(usage)) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	406 worklist.add(usage);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	407 belowBound.mark(usage);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	408 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	409 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	410 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	411
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	412 // build the intersection
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	413 belowBound.intersect(aboveBound);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	414 HashSet<Node> result = new HashSet<>();
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	415 for (Node node : belowBound) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	416 result.add(node);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	417 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	418 return result;
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
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	421 /**
7530 5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	422 * 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	423 * useless in itself (merge with only one end) it simplifies the later duplication step.
5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	424 *
5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	425 * @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	426 * should not be duplicated.
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	427 * @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	428 * @return The newly created end node.
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	429 */
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	430 private EndNode createNewMerge(FixedNode successor, FrameState stateAfterMerge) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	431 MergeNode newBottomMerge = graph.add(new MergeNode());
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	432 newBottomMerge.setProbability(successor.probability());
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	433 EndNode newBottomEnd = graph.add(new EndNode());
7255 95a685941e10 fix probability in TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 6526 diff changeset	434 newBottomEnd.setProbability(successor.probability());
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	435 newBottomMerge.addForwardEnd(newBottomEnd);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	436 newBottomMerge.setStateAfter(stateAfterMerge);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	437 ((FixedWithNextNode) successor.predecessor()).setNext(newBottomEnd);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	438 newBottomMerge.setNext(successor);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	439 return newBottomEnd;
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	440 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	441
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	442 /**
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	443 * 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	444 * <ul>
7530 5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	445 * <li>{@link ValueNode}s that have usages on the outside need to be replaced with phis for
5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	446 * the outside usages.</li>
5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	447 * <li>Non-{@link ValueNode} nodes that have outside usages (frame states, virtual object
5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	448 * states, ...) need to be cloned immediately for the outside usages.</li>
5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	449 * <li>Nodes that have a {@link StampFactory#extension()} or
5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	450 * {@link StampFactory#condition()} stamp need to be cloned immediately for the outside
5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	451 * usages.</li>
5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	452 * <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	453 * merge.</li>
5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	454 * <li>Outside non-{@link ValueNode}s with usages within the duplicated set of nodes need to
5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	455 * also be duplicated.</li>
5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	456 * <li>Outside {@link ValueNode}s with {@link StampFactory#extension()} or
5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	457 * {@link StampFactory#condition()} stamps 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	458 * nodes need to also be duplicated.</li>
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	459 * </ul>
7530 5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	460 *
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	461 * @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	462 * @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	463 * 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	464 * the duplicated set of nodes.
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	465 */
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	466 private void expandDuplicated(HashSet<Node> duplicatedNodes, MergeNode newBottomMerge) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	467 Deque<Node> worklist = new ArrayDeque<>(duplicatedNodes);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	468
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	469 while (!worklist.isEmpty()) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	470 Node duplicated = worklist.remove();
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	471 if (hasUsagesOutside(duplicated, duplicatedNodes)) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	472 boolean cloneForOutsideUsages = false;
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	473 if (duplicated instanceof ValueNode) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	474 ValueNode node = (ValueNode) duplicated;
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	475 if (node.stamp() == StampFactory.dependency()) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	476 // re-route dependencies to the merge
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	477 replaceUsagesOutside(node, newBottomMerge, duplicatedNodes);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	478 // TODO(ls) maybe introduce phis for dependencies
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	479 } else if (node.stamp() == StampFactory.extension() \|\| node.stamp() == StampFactory.condition()) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	480 cloneForOutsideUsages = true;
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	481 } else {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	482 // introduce a new phi
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	483 PhiNode newPhi = bottomPhis.get(node);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	484 if (newPhi == null) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	485 newPhi = graph.add(new PhiNode(node.kind(), newBottomMerge));
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	486 bottomPhis.put(node, newPhi);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	487 newPhi.addInput(node);
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 replaceUsagesOutside(node, newPhi, duplicatedNodes);
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 } else {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	492 cloneForOutsideUsages = true;
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 if (cloneForOutsideUsages) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	495 // clone the offending node to the outside
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	496 Node newOutsideClone = duplicated.copyWithInputs();
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	497 replaceUsagesOutside(duplicated, newOutsideClone, duplicatedNodes);
7530 5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	498 // this might cause other nodes to have outside usages, we need to look at
5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	499 // those as well
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	500 for (Node input : newOutsideClone.inputs()) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	501 if (duplicatedNodes.contains(input)) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	502 worklist.add(input);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	503 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	504 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	505 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	506 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	507 // 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	508 for (Node input : duplicated.inputs()) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	509 if (!duplicatedNodes.contains(input)) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	510 boolean duplicateInput = false;
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	511 if (input instanceof VirtualState) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	512 duplicateInput = true;
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	513 } else if (input instanceof ValueNode) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	514 Stamp inputStamp = ((ValueNode) input).stamp();
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	515 if (inputStamp == StampFactory.extension() \|\| inputStamp == StampFactory.condition()) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	516 duplicateInput = true;
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 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	519 if (duplicateInput) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	520 duplicatedNodes.add(input);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	521 worklist.add(input);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	522 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	523 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	524 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	525 }
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 /**
7530 5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	529 * Moves all depdendencies that point outside the duplicated area to the supplied value
5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	530 * anchor node.
5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	531 *
5861 1cb45c7dba55 retarget dependencies during TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 5792 diff changeset	532 * @param duplicatedNodes The set of duplicated nodes.
7530 5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	533 * @param anchor The node that will be the new target for all dependencies that point
5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	534 * outside the duplicated set of nodes.
5861 1cb45c7dba55 retarget dependencies during TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 5792 diff changeset	535 */
1cb45c7dba55 retarget dependencies during TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 5792 diff changeset	536 private static void retargetDependencies(HashSet<Node> duplicatedNodes, ValueAnchorNode anchor) {
1cb45c7dba55 retarget dependencies during TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 5792 diff changeset	537 for (Node node : duplicatedNodes) {
1cb45c7dba55 retarget dependencies during TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 5792 diff changeset	538 if (node instanceof ValueNode) {
1cb45c7dba55 retarget dependencies during TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 5792 diff changeset	539 NodeInputList<ValueNode> dependencies = ((ValueNode) node).dependencies();
1cb45c7dba55 retarget dependencies during TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 5792 diff changeset	540 for (int i = 0; i < dependencies.size(); i++) {
1cb45c7dba55 retarget dependencies during TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 5792 diff changeset	541 Node dependency = dependencies.get(i);
1cb45c7dba55 retarget dependencies during TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 5792 diff changeset	542 if (dependency != null && !duplicatedNodes.contains(dependency)) {
1cb45c7dba55 retarget dependencies during TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 5792 diff changeset	543 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	544 dependencies.set(i, anchor);
1cb45c7dba55 retarget dependencies during TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 5792 diff changeset	545 }
1cb45c7dba55 retarget dependencies during TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 5792 diff changeset	546 }
1cb45c7dba55 retarget dependencies during TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 5792 diff changeset	547 }
1cb45c7dba55 retarget dependencies during TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 5792 diff changeset	548 }
1cb45c7dba55 retarget dependencies during TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 5792 diff changeset	549 }
1cb45c7dba55 retarget dependencies during TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 5792 diff changeset	550
1cb45c7dba55 retarget dependencies during TailDuplicationPhase Lukas Stadler <lukas.stadler@jku.at> parents: 5792 diff changeset	551 /**
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	552 * Checks if the given node has usages that are not within the given set of nodes.
7530 5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	553 *
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	554 * @param node The node whose usages are checked.
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	555 * @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	556 * @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	557 */
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	558 private static boolean hasUsagesOutside(Node node, HashSet<Node> nodeSet) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	559 for (Node usage : node.usages()) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	560 if (!nodeSet.contains(usage)) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	561 return true;
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	562 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	563 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	564 return false;
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	565 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	566
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	567 /**
7530 5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	568 * Replaces the given node with the given replacement at all usages that are not within the
5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	569 * given set of nodes.
5e3d1a68664e applied mx eclipseformat to all Java files Doug Simon <doug.simon@oracle.com> parents: 7255 diff changeset	570 *
5786 f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	571 * @param node The node to be replaced at outside usages.
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	572 * @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	573 * @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	574 */
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	575 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	576 for (Node usage : node.usages().snapshot()) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	577 if (!nodeSet.contains(usage)) {
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	578 usage.replaceFirstInput(node, replacement);
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	579 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	580 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	581 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	582 }
f69a406355b2 new tail duplication phase Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	583 }

Mercurial > hg > truffle

annotate graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/TailDuplicationPhase.java @ 8988:02f57662b6c4