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 }