Mercurial > hg > truffle
annotate graal/GraalCompiler/src/com/sun/c1x/gen/PhiResolver.java @ 2738:88123130ede6
Moved phi simplifier.
author | Thomas Wuerthinger <thomas@wuerthinger.net> |
---|---|
date | Fri, 20 May 2011 10:46:15 +0200 |
parents | 16b9a8b5ad39 |
children |
rev | line source |
---|---|
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
1 /* |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
2 * Copyright (c) 2009, 2010, Oracle and/or its affiliates. All rights reserved. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
4 * |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
5 * This code is free software; you can redistribute it and/or modify it |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
6 * under the terms of the GNU General Public License version 2 only, as |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
7 * published by the Free Software Foundation. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
8 * |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
9 * This code is distributed in the hope that it will be useful, but WITHOUT |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
12 * version 2 for more details (a copy is included in the LICENSE file that |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
13 * accompanied this code). |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
14 * |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
15 * You should have received a copy of the GNU General Public License version |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
16 * 2 along with this work; if not, write to the Free Software Foundation, |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
18 * |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
20 * or visit www.oracle.com if you need additional information or have any |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
21 * questions. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
22 */ |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
23 package com.sun.c1x.gen; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
24 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
25 import static com.sun.cri.ci.CiValue.*; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
26 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
27 import java.util.*; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
28 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
29 import com.sun.c1x.ir.*; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
30 import com.sun.cri.ci.*; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
31 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
32 /** |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
33 * Converts {@link Phi} instructions into moves. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
34 * |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
35 * Resolves cycles: |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
36 * <pre> |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
37 * |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
38 * r1 := r2 becomes temp := r1 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
39 * r2 := r1 r1 := r2 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
40 * r2 := temp |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
41 * </pre> |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
42 * |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
43 * and orders moves: |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
44 * |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
45 * <pre> |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
46 * r2 := r3 becomes r1 := r2 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
47 * r1 := r2 r2 := r3 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
48 * </pre> |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
49 * |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
50 * @author Marcelo Cintra |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
51 * @author Thomas Wuerthinger |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
52 * @author Doug Simon |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
53 */ |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
54 public class PhiResolver { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
55 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
56 /** |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
57 * Tracks a data flow dependency between a source operand and any number of the destination operands. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
58 */ |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
59 static class Node { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
60 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
61 /** |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
62 * A source operand whose value flows into the {@linkplain #destinations destination} operands. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
63 */ |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
64 final CiValue operand; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
65 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
66 /** |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
67 * The operands whose values are defined by the {@linkplain #operand source} operand. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
68 */ |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
69 final ArrayList<Node> destinations; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
70 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
71 /** |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
72 * Denotes if a move instruction has already been emitted to initialize the value of {@link #operand}. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
73 */ |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
74 boolean assigned; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
75 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
76 /** |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
77 * Specifies if this operand been visited for the purpose of emitting a move instruction. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
78 */ |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
79 boolean visited; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
80 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
81 /** |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
82 * Specifies if this is the initial definition in data flow path for a given value. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
83 */ |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
84 boolean startNode; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
85 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
86 Node(CiValue operand) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
87 this.operand = operand; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
88 destinations = new ArrayList<Node>(4); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
89 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
90 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
91 @Override |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
92 public String toString() { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
93 StringBuilder buf = new StringBuilder(operand.toString()); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
94 if (!destinations.isEmpty()) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
95 buf.append(" ->"); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
96 for (Node node : destinations) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
97 buf.append(' ').append(node.operand); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
98 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
99 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
100 return buf.toString(); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
101 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
102 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
103 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
104 private final LIRGenerator gen; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
105 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
106 /** |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
107 * The operand loop header phi for the operand currently being process in {@link #dispose()}. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
108 */ |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
109 private Node loop; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
110 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
111 private CiValue temp; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
112 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
113 private final ArrayList<Node> variableOperands = new ArrayList<Node>(3); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
114 private final ArrayList<Node> otherOperands = new ArrayList<Node>(3); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
115 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
116 /** |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
117 * Maps operands to nodes. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
118 */ |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
119 private final HashMap<CiValue, Node> operandToNodeMap = new HashMap<CiValue, Node>(); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
120 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
121 public PhiResolver(LIRGenerator gen) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
122 this.gen = gen; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
123 temp = IllegalValue; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
124 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
125 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
126 public void dispose() { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
127 // resolve any cycles in moves from and to variables |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
128 for (int i = variableOperands.size() - 1; i >= 0; i--) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
129 Node node = variableOperands.get(i); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
130 if (!node.visited) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
131 loop = null; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
132 move(null, node); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
133 node.startNode = true; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
134 assert temp.isIllegal() : "moveTempTo() call missing"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
135 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
136 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
137 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
138 // generate move for move from non variable to arbitrary destination |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
139 for (int i = otherOperands.size() - 1; i >= 0; i--) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
140 Node node = otherOperands.get(i); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
141 for (int j = node.destinations.size() - 1; j >= 0; j--) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
142 emitMove(node.operand, node.destinations.get(j).operand); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
143 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
144 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
145 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
146 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
147 public void move(CiValue src, CiValue dest) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
148 assert dest.isVariable() : "destination must be virtual"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
149 // tty.print("move "); src.print(); tty.print(" to "); dest.print(); tty.cr(); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
150 assert src.isLegal() : "source for phi move is illegal"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
151 assert dest.isLegal() : "destination for phi move is illegal"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
152 Node srcNode = sourceNode(src); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
153 Node destNode = destinationNode(dest); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
154 srcNode.destinations.add(destNode); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
155 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
156 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
157 private Node createNode(CiValue operand, boolean source) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
158 Node node; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
159 if (operand.isVariable()) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
160 node = operandToNodeMap.get(operand); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
161 assert node == null || node.operand.equals(operand); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
162 if (node == null) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
163 node = new Node(operand); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
164 operandToNodeMap.put(operand, node); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
165 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
166 // Make sure that all variables show up in the list when |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
167 // they are used as the source of a move. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
168 if (source) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
169 if (!variableOperands.contains(node)) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
170 variableOperands.add(node); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
171 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
172 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
173 } else { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
174 assert source; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
175 node = new Node(operand); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
176 otherOperands.add(node); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
177 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
178 return node; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
179 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
180 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
181 private Node destinationNode(CiValue opr) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
182 return createNode(opr, false); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
183 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
184 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
185 private void emitMove(CiValue src, CiValue dest) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
186 assert src.isLegal(); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
187 assert dest.isLegal(); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
188 gen.lir.move(src, dest); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
189 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
190 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
191 // Traverse assignment graph in depth first order and generate moves in post order |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
192 // ie. two assignments: b := c, a := b start with node c: |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
193 // Call graph: move(NULL, c) -> move(c, b) -> move(b, a) |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
194 // Generates moves in this order: move b to a and move c to b |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
195 // ie. cycle a := b, b := a start with node a |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
196 // Call graph: move(NULL, a) -> move(a, b) -> move(b, a) |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
197 // Generates moves in this order: move b to temp, move a to b, move temp to a |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
198 private void move(Node src, Node dest) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
199 if (!dest.visited) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
200 dest.visited = true; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
201 for (int i = dest.destinations.size() - 1; i >= 0; i--) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
202 move(dest, dest.destinations.get(i)); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
203 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
204 } else if (!dest.startNode) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
205 // cycle in graph detected |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
206 assert loop == null : "only one loop valid!"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
207 loop = dest; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
208 moveToTemp(src.operand); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
209 return; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
210 } // else dest is a start node |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
211 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
212 if (!dest.assigned) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
213 if (loop == dest) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
214 moveTempTo(dest.operand); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
215 dest.assigned = true; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
216 } else if (src != null) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
217 emitMove(src.operand, dest.operand); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
218 dest.assigned = true; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
219 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
220 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
221 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
222 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
223 private void moveTempTo(CiValue dest) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
224 assert temp.isLegal(); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
225 emitMove(temp, dest); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
226 temp = IllegalValue; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
227 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
228 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
229 private void moveToTemp(CiValue src) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
230 assert temp.isIllegal(); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
231 temp = gen.newVariable(src.kind); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
232 emitMove(src, temp); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
233 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
234 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
235 private Node sourceNode(CiValue opr) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
236 return createNode(opr, true); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
237 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
238 } |