Mercurial > hg > truffle

comparison graal/Compiler/src/com/sun/c1x/gen/PhiResolver.java @ 2507:9ec15d6914ca

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