1 cananian 1.1.2.1 // PHI.java, created Fri Aug 7 13:51:47 1998 by cananian
2 cananian 1.1.2.1 // Copyright (C) 1998 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1.2.1 package harpoon.IR.Quads;
5 cananian 1.1.2.1
6 cananian 1.1.2.9 import harpoon.ClassFile.HCodeElement;
7 cananian 1.1.2.1 import harpoon.Temp.Temp;
8 cananian 1.1.2.1 import harpoon.Temp.TempMap;
9 cananian 1.1.2.1 import harpoon.Util.Util;
10 cananian 1.1.2.3
11 cananian 1.1.2.11 import java.util.Arrays;
12 cananian 1.1.2.11 import java.util.HashSet;
13 cananian 1.1.2.11 import java.util.Set;
14 cananian 1.1.2.1 /**
15 cananian 1.1.2.6 * <code>PHI</code> objects represent blocks of phi functions.
16 cananian 1.1.2.1 *
17 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
18 cananian 1.6 * @version $Id: PHI.java,v 1.6 2002/09/01 07:34:46 cananian Exp $
19 cananian 1.1.2.1 */
20 cananian 1.1.2.1 public class PHI extends Quad {
21 cananian 1.1.2.3 /** dst[i] is the left-hand side of the i'th phi function in this block. */
22 cananian 1.1.2.3 protected Temp dst[];
23 cananian 1.1.2.3 /** src[i][j] is the j'th parameter to the i'th phi function in this
24 cananian 1.1.2.3 * block. */
25 cananian 1.1.2.3 protected Temp src[][];
26 cananian 1.1.2.3
27 cananian 1.1.2.3 /** Creates a <code>PHI</code> object representing a block of
28 cananian 1.1.2.3 * phi functions.
29 cananian 1.1.2.3 * @param dst
30 cananian 1.1.2.3 * the left hand sides of a phi function assignment block.
31 cananian 1.1.2.3 * @param src
32 cananian 1.1.2.3 * the phi function parameters in a phi function assignment block.
33 cananian 1.1.2.3 */
34 cananian 1.1.2.5 public PHI(QuadFactory qf, HCodeElement source,
35 cananian 1.1.2.1 Temp dst[], Temp src[][], int arity) {
36 cananian 1.1.2.5 super(qf, source, arity, 1);
37 cananian 1.1.2.1 this.dst = dst;
38 cananian 1.1.2.1 this.src = src;
39 cananian 1.1.2.3 // VERIFY legality of PHI function.
40 cananian 1.3.2.1 assert dst!=null && src!=null;
41 cananian 1.3.2.1 assert arity>=0;
42 cananian 1.3.2.1 assert dst.length==src.length;
43 cananian 1.1.2.3 for (int i=0; i<src.length; i++)
44 cananian 1.3.2.1 assert src[i].length==arity;
45 cananian 1.3.2.1 assert arity==arity();
46 cananian 1.1.2.1 }
47 cananian 1.1.2.3 /** Creates a <code>PHI</code> object with the specified arity.
48 cananian 1.1.2.3 * Each phi function will have <code>arity</code> arguments.
49 cananian 1.1.2.3 * @param dst
50 cananian 1.1.2.3 * the left hand sides of the phi functions.
51 cananian 1.1.2.3 * @param arity
52 cananian 1.1.2.3 * the number of predecessors of this quad.
53 cananian 1.1.2.3 */
54 cananian 1.1.2.5 public PHI(QuadFactory qf, HCodeElement source,
55 cananian 1.1.2.1 Temp dst[], int arity) {
56 cananian 1.1.2.5 this(qf, source, dst, new Temp[dst.length][arity], arity);
57 cananian 1.1.2.3 }
58 cananian 1.1.2.3 // ACCESSOR METHODS:
59 cananian 1.1.2.3 /** Returns the right hand side of the <code>nPhi</code>'th phi
60 cananian 1.1.2.3 * function assignment in the block. */
61 cananian 1.1.2.3 public Temp dst(int nPhi) { return dst[nPhi]; }
62 cananian 1.1.2.3 /** Returns the <code>nParam</code>'th argument of the
63 cananian 1.1.2.3 * <code>nPhi</code>'th phi function in the block. */
64 cananian 1.1.2.3 public Temp src(int nPhi, int nParam) { return src[nPhi][nParam]; }
65 cananian 1.1.2.3 /** Returns an array holding the arguments to the <code>nPhi</code>'th
66 cananian 1.1.2.3 * phi function in the block. */
67 cananian 1.1.2.3 public Temp[] src(int nPhi)
68 cananian 1.1.2.3 { return (Temp[]) Util.safeCopy(Temp.arrayFactory, src[nPhi]); }
69 cananian 1.1.2.3
70 cananian 1.1.2.3 /** Returns the number of phi functions in the block. */
71 cananian 1.1.2.3 public int numPhis() { return dst.length; }
72 cananian 1.1.2.3 /** Returns the number of arguments each phi function has. */
73 cananian 1.1.2.3 public int arity() { return prev.length; }
74 cananian 1.1.2.3
75 cananian 1.1.2.8 /** Removes a given phi function from the block.
76 cananian 1.1.2.8 * @deprecated does not preserve immutability. */
77 cananian 1.1.2.3 public void removePhi(int nPhi) {
78 cananian 1.3.2.1 assert 0<=nPhi && nPhi<numPhis();
79 cananian 1.1.2.3 dst = (Temp[]) Util.shrink(Temp.arrayFactory, dst, nPhi);
80 cananian 1.1.2.3 src = (Temp[][]) Util.shrink(Temp.doubleArrayFactory, src, nPhi);
81 cananian 1.1.2.1 }
82 cananian 1.1.2.1
83 cananian 1.1.2.8 /** Remove a predecessor from this phi, reducing the arity.
84 cananian 1.1.2.8 * @deprecated does not preserve immutability. */
85 cananian 1.1.2.3 public void removePred(int which_pred) {
86 cananian 1.1.2.1 prev = (Edge[]) Util.shrink(Edge.arrayFactory, prev, which_pred);
87 cananian 1.1.2.1 for (int i=0; i<dst.length; i++)
88 cananian 1.1.2.1 src[i] = (Temp[]) Util.shrink(Temp.arrayFactory,
89 cananian 1.1.2.1 src[i], which_pred);
90 cananian 1.1.2.1 // fixup edges.
91 cananian 1.1.2.1 for (int i=which_pred; i<prev.length; i++)
92 cananian 1.1.2.1 prev[i].to_index--;
93 cananian 1.1.2.1 // double-check this.
94 cananian 1.1.2.1 for (int i=0; i<prev.length; i++)
95 cananian 1.3.2.1 assert prev[i].to_index == i;
96 cananian 1.1.2.1 }
97 cananian 1.1.2.1
98 cananian 1.1.2.8 /** Shrink the arity of a PHI by replacing it.
99 cananian 1.1.2.8 * @return the new PHI.
100 cananian 1.1.2.8 */
101 cananian 1.1.2.8 public PHI shrink(int which_pred) {
102 cananian 1.1.2.8 Temp ndst[] = (Temp[]) dst.clone();
103 cananian 1.1.2.8 Temp nsrc[][] = new Temp[src.length][];
104 cananian 1.1.2.8 for (int i=0; i<nsrc.length; i++)
105 cananian 1.1.2.8 nsrc[i] = (Temp[]) Util.shrink(Temp.arrayFactory,
106 cananian 1.1.2.8 src[i], which_pred);
107 cananian 1.1.2.8 PHI p = new PHI(qf, this, ndst, nsrc, this.arity()-1);
108 cananian 1.1.2.8 // copy the edges.
109 cananian 1.1.2.8 for (int i=0, j=0; i < this.arity(); i++)// i indexes this, j indexes p
110 cananian 1.1.2.8 if (i==which_pred) continue;
111 cananian 1.1.2.8 else if (this.prevEdge(i)==null) j++;
112 cananian 1.1.2.8 else Quad.addEdge(this.prev(i), this.prevEdge(i).which_succ(),
113 cananian 1.1.2.8 p, j++);
114 cananian 1.1.2.8 if (this.nextEdge(0)!=null)
115 cananian 1.1.2.8 Quad.addEdge(p, 0, this.next(0), this.nextEdge(0).which_pred());
116 cananian 1.1.2.8 return p;
117 cananian 1.1.2.8 }
118 cananian 1.1.2.8 /** Grow the arity of a PHI by one by replacing it.
119 cananian 1.1.2.8 * @return the new PHI.
120 cananian 1.1.2.8 */
121 cananian 1.1.2.8 public PHI grow(Temp args[], int which_pred) {
122 cananian 1.1.2.8 Temp ndst[] = (Temp[]) dst.clone();
123 cananian 1.1.2.8 Temp nsrc[][] = new Temp[src.length][];
124 cananian 1.1.2.1 // add contents of src to each phi function.
125 cananian 1.1.2.8 for (int i=0; i<nsrc.length; i++)
126 cananian 1.1.2.8 nsrc[i] = (Temp[]) Util.grow(Temp.arrayFactory, src[i],
127 cananian 1.1.2.8 args[i], which_pred);
128 cananian 1.1.2.8 PHI p = new PHI(qf, this, ndst, nsrc, arity()+1);
129 cananian 1.1.2.8 // copy the edges.
130 cananian 1.1.2.8 for (int i=0, j=0; i < p.arity(); i++) {// i indexes p, j indexes this
131 cananian 1.1.2.8 if (i==which_pred) continue; // skip this edge without increasing j
132 cananian 1.1.2.8 else if (this.prevEdge(j)!=null)
133 cananian 1.1.2.8 Quad.addEdge(this.prev(j), this.prevEdge(j).which_succ(),p,i);
134 cananian 1.1.2.8 j++;
135 cananian 1.1.2.1 }
136 cananian 1.1.2.8 if (this.nextEdge(0)!=null)
137 cananian 1.1.2.8 Quad.addEdge(p, 0, this.next(0), this.nextEdge(0).which_pred());
138 cananian 1.1.2.8 return p;
139 cananian 1.1.2.1 }
140 cananian 1.1.2.8
141 cananian 1.1.2.8 /** Returns all the <code>Temp</code>s used by this <code>Quad</code>. */
142 cananian 1.1.2.1 public Temp[] use() {
143 cananian 1.1.2.1 int n=0;
144 cananian 1.1.2.1 for (int i=0; i<src.length; i++)
145 cananian 1.1.2.1 n+=src[i].length;
146 cananian 1.1.2.1 Temp[] u = new Temp[n];
147 cananian 1.1.2.1 n=0;
148 cananian 1.1.2.1 for (int i=0; i<src.length; i++) {
149 cananian 1.1.2.1 System.arraycopy(src[i], 0, u, n, src[i].length);
150 cananian 1.1.2.1 n+=src[i].length;
151 cananian 1.1.2.1 }
152 cananian 1.1.2.1 return u;
153 cananian 1.1.2.1 }
154 cananian 1.1.2.1 /** Returns all the Temps defined by this Quad. */
155 cananian 1.1.2.2 public Temp[] def()
156 cananian 1.1.2.2 { return (Temp[]) Util.safeCopy(Temp.arrayFactory, dst); }
157 cananian 1.1.2.2
158 cananian 1.1.2.4 public int kind() { return QuadKind.PHI; }
159 cananian 1.1.2.4
160 cananian 1.1.2.7 public Quad rename(QuadFactory qqf, TempMap defMap, TempMap useMap) {
161 cananian 1.1.2.7 return new PHI(qqf, this, map(defMap,dst), map(useMap,src), arity());
162 cananian 1.1.2.4 }
163 cananian 1.1.2.7 /** Rename all used variables in this Quad according to a mapping.
164 cananian 1.1.2.7 * @deprecated does not preserve immutability. */
165 cananian 1.1.2.4 void renameUses(TempMap tm) {
166 cananian 1.1.2.1 for (int i=0; i<src.length; i++) {
167 cananian 1.1.2.1 for (int j=0; j<src[i].length; j++)
168 cananian 1.1.2.1 src[i][j] = tm.tempMap(src[i][j]);
169 cananian 1.1.2.1 }
170 cananian 1.1.2.1 }
171 cananian 1.1.2.7 /** Rename all defined variables in this Quad according to a mapping.
172 cananian 1.1.2.7 * @deprecated does not preserve immutability. */
173 cananian 1.1.2.4 void renameDefs(TempMap tm) {
174 cananian 1.1.2.1 for (int i=0; i<dst.length; i++) {
175 cananian 1.1.2.1 dst[i] = tm.tempMap(dst[i]);
176 cananian 1.1.2.1 }
177 cananian 1.1.2.11 }
178 cananian 1.1.2.11 /** Returns true if any of the sources of any of the phi functions
179 cananian 1.1.2.11 * match a destination of a phi function. This case is legal,
180 cananian 1.1.2.11 * but makes translating PHI functions to MOVEs 'tricky'. */
181 cananian 1.1.2.11 public boolean hasConflicts() {
182 cananian 1.6 Set<Temp> ds = new HashSet<Temp>(Arrays.asList(dst));
183 cananian 1.1.2.11 for (int i=0; i<dst.length; i++)
184 cananian 1.1.2.11 for (int j=0; j<src[i].length; j++)
185 cananian 1.1.2.11 if (ds.contains(src[i][j]))
186 cananian 1.1.2.11 return true;
187 cananian 1.1.2.11 return false;
188 cananian 1.1.2.1 }
189 cananian 1.1.2.1
190 cananian 1.1.2.10 public void accept(QuadVisitor v) { v.visit(this); }
191 cananian 1.5 public <T> T accept(QuadValueVisitor<T> v) { return v.visit(this); }
192 cananian 1.1.2.1
193 cananian 1.1.2.1 /** Returns a human-readable representation of this Quad. */
194 cananian 1.1.2.1 public String toString() {
195 cananian 1.1.2.1 StringBuffer sb = new StringBuffer("PHI("+prev.length+"): ");
196 cananian 1.1.2.1 for (int i=0; i<dst.length; i++) {
197 cananian 1.1.2.1 sb.append(dst[i].toString() + "=(");
198 cananian 1.1.2.1 for (int j=0; j<src[i].length; j++) {
199 cananian 1.1.2.1 if (src[i][j]==null)
200 cananian 1.1.2.1 sb.append("null");
201 cananian 1.1.2.1 else
202 cananian 1.1.2.1 sb.append(src[i][j].toString());
203 cananian 1.1.2.1 if (j < src[i].length-1)
204 cananian 1.1.2.1 sb.append(",");
205 cananian 1.1.2.1 }
206 cananian 1.1.2.1 sb.append(")");
207 cananian 1.1.2.1 if (i < dst.length-1)
208 cananian 1.1.2.1 sb.append("; ");
209 cananian 1.1.2.1 }
210 cananian 1.1.2.1 return sb.toString();
211 cananian 1.1.2.1 }
212 cananian 1.2 }