Mercurial > hg > truffle

annotate graal/GraalCompiler/src/com/sun/c1x/gen/PhiResolver.java @ 2738:88123130ede6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Moved phi simplifier.
author Thomas Wuerthinger <thomas@wuerthinger.net>
date Fri, 20 May 2011 10:46:15 +0200
parents 16b9a8b5ad39
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
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 }