Mercurial > hg > graal-compiler
comparison graal/Compiler/src/com/sun/c1x/gen/PhiResolver.java @ 2507:9ec15d6914ca
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 } |