1 /*
2 * Copyright (c) 2009, 2015, 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 org.graalvm.compiler.lir.gen;
24
25 import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
26 import static jdk.vm.ci.code.ValueUtil.isIllegal;
27 import static jdk.vm.ci.code.ValueUtil.isLegal;
28 import static jdk.vm.ci.meta.Value.ILLEGAL;
29
30 import java.util.ArrayList;
31 import java.util.HashMap;
32 import java.util.List;
33
34 import org.graalvm.compiler.core.common.CollectionsFactory;
35 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
36 import org.graalvm.compiler.lir.LIRInsertionBuffer;
37 import org.graalvm.compiler.lir.LIRInstruction;
38 import org.graalvm.compiler.lir.gen.LIRGeneratorTool.MoveFactory;
39
40 import jdk.vm.ci.meta.AllocatableValue;
41 import jdk.vm.ci.meta.Value;
42
43 /**
44 * Converts phi instructions into moves.
45 *
46 * Resolves cycles:
47 *
48 * <pre>
49 *
50 * r1 := r2 becomes temp := r1
51 * r2 := r1 r1 := r2
52 * r2 := temp
53 * </pre>
54 *
55 * and orders moves:
56 *
57 * <pre>
58 * r2 := r3 becomes r1 := r2
59 * r1 := r2 r2 := r3
60 * </pre>
61 */
62 public class PhiResolver {
63
64 /**
65 * Tracks a data flow dependency between a source operand and any number of the destination
66 * operands.
67 */
68 static class PhiResolverNode {
69
70 /**
71 * A source operand whose value flows into the {@linkplain #destinations destination}
72 * operands.
73 */
74 final Value operand;
75
76 /**
77 * The operands whose values are defined by the {@linkplain #operand source} operand.
78 */
79 final ArrayList<PhiResolverNode> destinations;
80
81 /**
82 * Denotes if a move instruction has already been emitted to initialize the value of
83 * {@link #operand}.
84 */
85 boolean assigned;
86
87 /**
88 * Specifies if this operand been visited for the purpose of emitting a move instruction.
89 */
90 boolean visited;
91
92 /**
93 * Specifies if this is the initial definition in data flow path for a given value.
94 */
95 boolean startNode;
96
97 PhiResolverNode(Value operand) {
98 this.operand = operand;
99 destinations = new ArrayList<>(4);
100 }
101
102 @Override
103 public String toString() {
104 StringBuilder buf = new StringBuilder(operand.toString());
105 if (!destinations.isEmpty()) {
106 buf.append(" ->");
107 for (PhiResolverNode node : destinations) {
108 buf.append(' ').append(node.operand);
109 }
110 }
111 return buf.toString();
112 }
113 }
114
115 private final LIRGeneratorTool gen;
116 private final MoveFactory moveFactory;
117 private final LIRInsertionBuffer buffer;
118 private final int insertBefore;
119
120 /**
121 * The operand loop header phi for the operand currently being process in {@link #dispose()}.
122 */
123 private PhiResolverNode loop;
124
125 private Value temp;
126
127 private final ArrayList<PhiResolverNode> variableOperands = new ArrayList<>(3);
128 private final ArrayList<PhiResolverNode> otherOperands = new ArrayList<>(3);
129
130 /**
131 * Maps operands to nodes.
132 */
133 private final HashMap<Value, PhiResolverNode> operandToNodeMap = CollectionsFactory.newMap();
134
135 public static PhiResolver create(LIRGeneratorTool gen) {
136 AbstractBlockBase<?> block = gen.getCurrentBlock();
137 assert block != null;
138 List<LIRInstruction> instructions = gen.getResult().getLIR().getLIRforBlock(block);
139
140 return new PhiResolver(gen, new LIRInsertionBuffer(), instructions, instructions.size());
141 }
142
143 public static PhiResolver create(LIRGeneratorTool gen, LIRInsertionBuffer buffer, List<LIRInstruction> instructions, int insertBefore) {
144 return new PhiResolver(gen, buffer, instructions, insertBefore);
145 }
146
147 protected PhiResolver(LIRGeneratorTool gen, LIRInsertionBuffer buffer, List<LIRInstruction> instructions, int insertBefore) {
148 this.gen = gen;
149 moveFactory = gen.getSpillMoveFactory();
150 temp = ILLEGAL;
151
152 this.buffer = buffer;
153 this.buffer.init(instructions);
154 this.insertBefore = insertBefore;
155
156 }
157
158 public void dispose() {
159 // resolve any cycles in moves from and to variables
160 for (int i = variableOperands.size() - 1; i >= 0; i--) {
161 PhiResolverNode node = variableOperands.get(i);
162 if (!node.visited) {
163 loop = null;
164 move(node, null);
165 node.startNode = true;
166 assert isIllegal(temp) : "moveTempTo() call missing";
167 }
168 }
169
170 // generate move for move from non variable to arbitrary destination
171 for (int i = otherOperands.size() - 1; i >= 0; i--) {
172 PhiResolverNode node = otherOperands.get(i);
173 for (int j = node.destinations.size() - 1; j >= 0; j--) {
174 emitMove(node.destinations.get(j).operand, node.operand);
175 }
176 }
177 buffer.finish();
178 }
179
180 public void move(Value dest, Value src) {
181 assert isVariable(dest) : "destination must be virtual";
182 // tty.print("move "); src.print(); tty.print(" to "); dest.print(); tty.cr();
183 assert isLegal(src) : "source for phi move is illegal";
184 assert isLegal(dest) : "destination for phi move is illegal";
185 PhiResolverNode srcNode = sourceNode(src);
186 PhiResolverNode destNode = destinationNode(dest);
187 srcNode.destinations.add(destNode);
188 }
189
190 private PhiResolverNode createNode(Value operand, boolean source) {
191 PhiResolverNode node;
192 if (isVariable(operand)) {
193 node = operandToNodeMap.get(operand);
194 assert node == null || node.operand.equals(operand);
195 if (node == null) {
196 node = new PhiResolverNode(operand);
197 operandToNodeMap.put(operand, node);
198 }
199 // Make sure that all variables show up in the list when
200 // they are used as the source of a move.
201 if (source) {
202 if (!variableOperands.contains(node)) {
203 variableOperands.add(node);
204 }
205 }
206 } else {
207 assert source;
208 node = new PhiResolverNode(operand);
209 otherOperands.add(node);
210 }
211 return node;
212 }
213
214 private PhiResolverNode destinationNode(Value opr) {
215 return createNode(opr, false);
216 }
217
218 private void emitMove(Value dest, Value src) {
219 assert isLegal(src);
220 assert isLegal(dest);
221 LIRInstruction move = moveFactory.createMove((AllocatableValue) dest, src);
222 buffer.append(insertBefore, move);
223 }
224
225 // Traverse assignment graph in depth first order and generate moves in post order
226 // ie. two assignments: b := c, a := b start with node c:
227 // Call graph: move(c, NULL) -> move(b, c) -> move(a, b)
228 // Generates moves in this order: move b to a and move c to b
229 // ie. cycle a := b, b := a start with node a
230 // Call graph: move(a, NULL) -> move(b, a) -> move(a, b)
231 // Generates moves in this order: move b to temp, move a to b, move temp to a
232 private void move(PhiResolverNode dest, PhiResolverNode src) {
233 if (!dest.visited) {
234 dest.visited = true;
235 for (int i = dest.destinations.size() - 1; i >= 0; i--) {
236 move(dest.destinations.get(i), dest);
237 }
238 } else if (!dest.startNode) {
239 // cycle in graph detected
240 assert loop == null : "only one loop valid!";
241 loop = dest;
242 moveToTemp(src.operand);
243 return;
244 } // else dest is a start node
245
246 if (!dest.assigned) {
247 if (loop == dest) {
248 moveTempTo(dest.operand);
249 dest.assigned = true;
250 } else if (src != null) {
251 emitMove(dest.operand, src.operand);
252 dest.assigned = true;
253 }
254 }
255 }
256
257 private void moveTempTo(Value dest) {
258 assert isLegal(temp);
259 emitMove(dest, temp);
260 temp = ILLEGAL;
261 }
262
263 private void moveToTemp(Value src) {
264 assert isIllegal(temp);
265 temp = gen.newVariable(src.getValueKind());
266 emitMove(temp, src);
267 }
268
269 private PhiResolverNode sourceNode(Value opr) {
270 return createNode(opr, true);
271 }
272 }