1 cananian 1.1.2.22 // Quad.java, created Tue Dec 1 7:36:43 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.39 import harpoon.ClassFile.HCodeAndMaps; 7 cananian 1.1.2.12 import harpoon.ClassFile.HCodeElement; 8 duncan 1.1.2.30 import harpoon.IR.Properties.CFGEdge; 9 cananian 1.1.2.14 import harpoon.Temp.CloningTempMap; 10 cananian 1.1.2.1 import harpoon.Temp.Temp; 11 cananian 1.1.2.1 import harpoon.Temp.TempMap; 12 cananian 1.1.2.1 import harpoon.Util.ArrayFactory; 13 sportbilly 1.1.2.20 import harpoon.Util.ArrayIterator; 14 cananian 1.6 import harpoon.Util.Collections.WorkSet; 15 cananian 1.12 import net.cscott.jutil.CombineIterator; 16 cananian 1.1.2.40 import harpoon.Util.EnumerationIterator; 17 sportbilly 1.1.2.20 import harpoon.Util.Util; 18 cananian 1.1.2.1 19 sportbilly 1.1.2.20 import java.util.AbstractCollection; 20 cananian 1.11 import java.util.AbstractList; 21 cananian 1.1.2.40 import java.util.ArrayList; 22 sportbilly 1.1.2.20 import java.util.Arrays; 23 sportbilly 1.1.2.20 import java.util.Collection; 24 sportbilly 1.1.2.20 import java.util.Collections; 25 cananian 1.1.2.21 import java.util.HashMap; 26 sportbilly 1.1.2.20 import java.util.Iterator; 27 cananian 1.1.2.40 import java.util.List; 28 cananian 1.1.2.21 import java.util.Map; 29 cananian 1.1.2.1 /** 30 cananian 1.1.2.1 * <code>Quad</code> is the base class for the quadruple representation.<p> 31 cananian 1.1.2.1 * 32 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu> 33 cananian 1.13 * @version $Id: Quad.java,v 1.13 2004/02/08 03:21:24 cananian Exp $ 34 cananian 1.1.2.1 */ 35 cananian 1.1.2.1 public abstract class Quad 36 cananian 1.1.2.1 implements harpoon.ClassFile.HCodeElement, 37 cananian 1.1.2.47 harpoon.IR.Properties.UseDefable, 38 cananian 1.9 harpoon.IR.Properties.CFGraphable<Quad,Edge>, 39 cananian 1.3.2.2 Cloneable, Comparable<Quad>, java.io.Serializable 40 cananian 1.1.2.1 { 41 cananian 1.1.2.35 final QuadFactory qf; 42 cananian 1.1.2.35 final String source_file; 43 cananian 1.1.2.35 final int source_line; 44 cananian 1.1.2.35 final int id; 45 cananian 1.1.2.4 // cached. 46 cananian 1.1.2.35 final private int hashCode; 47 cananian 1.1.2.4 48 cananian 1.1.2.35 /** Initializes a quad with <code>prev_arity</code> input edges and 49 cananian 1.1.2.35 * <code>next_arity</code> output edges. */ 50 cananian 1.1.2.4 protected Quad(QuadFactory qf, HCodeElement source, 51 cananian 1.1.2.1 int prev_arity, int next_arity) { 52 cananian 1.3.2.1 assert qf!=null; // QuadFactory must be valid. 53 cananian 1.1.2.2 this.source_file = (source!=null)?source.getSourceFile():"unknown"; 54 cananian 1.1.2.2 this.source_line = (source!=null)?source.getLineNumber(): 0; 55 cananian 1.1.2.4 this.id = qf.getUniqueID(); 56 cananian 1.1.2.4 this.qf = qf; 57 cananian 1.1.2.4 58 cananian 1.1.2.1 this.prev = new Edge[prev_arity]; 59 cananian 1.1.2.1 this.next = new Edge[next_arity]; 60 cananian 1.1.2.4 61 cananian 1.1.2.5 this.hashCode = (id<<5) ^ kind() ^ 62 cananian 1.1.2.10 qf.getParent().getName().hashCode() ^ qf.getMethod().hashCode(); 63 cananian 1.1.2.1 } 64 cananian 1.1.2.35 /** Initializes a quad with exactly one input edge and exactly one 65 cananian 1.1.2.35 * output edge. */ 66 cananian 1.1.2.4 protected Quad(QuadFactory qf, HCodeElement source) { 67 cananian 1.1.2.8 this(qf, source, 1, 1); 68 cananian 1.1.2.1 } 69 cananian 1.1.2.4 public int hashCode() { return hashCode; } 70 cananian 1.1.2.1 71 cananian 1.1.2.4 /** Returns the <code>QuadFactory</code> that generated this 72 cananian 1.1.2.4 * <code>Quad</code>. */ 73 cananian 1.1.2.4 public QuadFactory getFactory() { return qf; } 74 cananian 1.1.2.1 /** Returns the original source file name that this <code>Quad</code> 75 cananian 1.1.2.1 * is derived from. */ 76 cananian 1.1.2.2 public String getSourceFile() { return source_file; } 77 cananian 1.1.2.1 /** Returns the line in the original source file that this 78 cananian 1.1.2.1 * <code>Quad</code> is derived from. */ 79 cananian 1.1.2.2 public int getLineNumber() { return source_line; } 80 cananian 1.1.2.1 /** Returns a unique numeric identifier for this <code>Quad</code>. */ 81 cananian 1.1.2.1 public int getID() { return id; } 82 cananian 1.1.2.1 /** Force everyone to reimplement toString() */ 83 cananian 1.1.2.1 public abstract String toString(); 84 cananian 1.1.2.1 85 cananian 1.1.2.1 /** Accept a visitor. */ 86 cananian 1.1.2.24 public abstract void accept(QuadVisitor v); 87 cananian 1.5 public abstract <T> T accept(QuadValueVisitor<T> v); 88 cananian 1.1.2.1 89 cananian 1.1.2.3 /** Return an integer enumeration of the kind of this 90 cananian 1.1.2.3 * <code>Quad</code>. The enumerated values are defined in 91 cananian 1.1.2.3 * <code>QuadKind</code>. */ 92 cananian 1.1.2.3 public abstract int kind(); 93 cananian 1.1.2.3 94 cananian 1.1.2.3 /** Create a new <code>Quad</code> identical to the receiver, but 95 cananian 1.1.2.3 * with all <code>Temp</code>s renamed according to a mapping. 96 cananian 1.1.2.4 * The new <code>Quad</code> will have no edges. <p> 97 cananian 1.1.2.4 * The new <code>Quad</code> will come from the specified 98 cananian 1.1.2.4 * <code>QuadFactory</code>. 99 cananian 1.1.2.4 */ 100 cananian 1.1.2.6 public abstract Quad rename(QuadFactory qf, TempMap defMap,TempMap useMap); 101 cananian 1.1.2.35 /** Create a new <code>Quad</code> identical to the receiver, but 102 cananian 1.1.2.35 * with all <code>Temp</code>s renamed according to a mapping. 103 cananian 1.1.2.35 * The new <code>Quad</code> will have no edges. <p> 104 cananian 1.1.2.35 * The new <code>Quad</code> will come from the same 105 cananian 1.1.2.35 * <code>QuadFactory</code> as the receiver. 106 cananian 1.1.2.35 */ 107 cananian 1.1.2.35 public final Quad rename(TempMap defMap,TempMap useMap) { 108 cananian 1.1.2.13 return rename(this.qf, defMap, useMap); 109 cananian 1.1.2.13 } 110 cananian 1.1.2.3 111 cananian 1.1.2.1 /*----------------------------------------------------------*/ 112 cananian 1.1.2.1 /** Return all the Temps used by this Quad. */ 113 cananian 1.1.2.1 public Temp[] use() { return new Temp[0]; } 114 cananian 1.1.2.1 /** Return all the Temps defined by this Quad. */ 115 cananian 1.1.2.1 public Temp[] def() { return new Temp[0]; } 116 cananian 1.3.2.2 public Collection<Temp> useC() { return Arrays.asList(use()); } 117 cananian 1.3.2.2 public Collection<Temp> defC() { return Arrays.asList(def()); } 118 cananian 1.1.2.1 /*----------------------------------------------------------*/ 119 cananian 1.1.2.1 /** Array factory: returns <code>Quad[]</code>s */ 120 cananian 1.3.2.2 public static final ArrayFactory<Quad> arrayFactory = 121 cananian 1.3.2.2 new ArrayFactory<Quad>() { 122 cananian 1.3.2.2 public Quad[] newArray(int len) { return new Quad[len]; } 123 cananian 1.1.2.1 }; 124 cananian 1.1.2.1 125 cananian 1.1.2.1 /*----------------------------------------------------------*/ 126 cananian 1.1.2.1 // Graph structure. 127 cananian 1.1.2.1 // Can modify links, but not *number of links*. 128 cananian 1.1.2.1 Edge next[], prev[]; 129 cananian 1.1.2.1 130 cananian 1.1.2.1 /** Returns the <code>i</code>th successor of this quad. */ 131 cananian 1.1.2.1 public Quad next(int i) { return (Quad) next[i].to(); } 132 cananian 1.1.2.1 /** Returns the <code>i</code>th predecessor of this quad. */ 133 cananian 1.1.2.1 public Quad prev(int i) { return (Quad) prev[i].from(); } 134 cananian 1.1.2.18 /** Return the number of successors of this quad. */ 135 cananian 1.1.2.18 public int nextLength() { return next.length; } 136 cananian 1.1.2.18 /** Return the number of predecessors of this quad. */ 137 cananian 1.1.2.18 public int prevLength() { return prev.length; } 138 cananian 1.1.2.1 139 cananian 1.1.2.1 /** Returns an array containing all the successors of this quad, 140 cananian 1.1.2.1 * in order. */ 141 cananian 1.1.2.1 public Quad[] next() { 142 cananian 1.1.2.1 Quad[] r = new Quad[next.length]; 143 cananian 1.1.2.1 for (int i=0; i<r.length; i++) 144 cananian 1.1.2.1 r[i] = (next[i]==null)?null:(Quad)next[i].to(); 145 cananian 1.1.2.1 return r; 146 cananian 1.1.2.1 } 147 cananian 1.1.2.1 /** Returns an array containing all the predecessors of this quad, 148 cananian 1.1.2.1 * in order. */ 149 cananian 1.1.2.1 public Quad[] prev() { 150 cananian 1.1.2.1 Quad[] r = new Quad[prev.length]; 151 cananian 1.1.2.1 for (int i=0; i<r.length; i++) 152 cananian 1.1.2.1 r[i] = (prev[i]==null)?null:(Quad)prev[i].from(); 153 cananian 1.1.2.1 return r; 154 cananian 1.1.2.1 } 155 cananian 1.1.2.1 156 cananian 1.1.2.1 /** Returns an array containing all the outgoing edges from this quad. */ 157 cananian 1.1.2.1 public Edge[] nextEdge() 158 cananian 1.3.2.2 { return Util.safeCopy(Edge.arrayFactory, next); } 159 cananian 1.1.2.1 /** Returns an array containing all the incoming edges of this quad. */ 160 cananian 1.1.2.1 public Edge[] prevEdge() 161 cananian 1.3.2.2 { return Util.safeCopy(Edge.arrayFactory, prev); } 162 cananian 1.1.2.1 /** Returns the <code>i</code>th outgoing edge for this quad. */ 163 cananian 1.1.2.1 public Edge nextEdge(int i) { return next[i]; } 164 cananian 1.1.2.1 /** Returns the <code>i</code>th incoming edge of this quad. */ 165 cananian 1.1.2.1 public Edge prevEdge(int i) { return prev[i]; } 166 cananian 1.1.2.1 167 cananian 1.3.2.2 // from CFGraphable<Quad>: 168 cananian 1.3.2.2 public Edge[] edges() { 169 cananian 1.1.2.1 Edge[] e = new Edge[next.length+prev.length]; 170 cananian 1.1.2.1 System.arraycopy(next,0,e,0,next.length); 171 cananian 1.1.2.1 System.arraycopy(prev,0,e,next.length,prev.length); 172 cananian 1.3.2.2 return e; 173 cananian 1.1.2.1 } 174 cananian 1.3.2.2 public Edge[] pred() { return prevEdge(); } 175 cananian 1.3.2.2 public Edge[] succ() { return nextEdge(); } 176 sportbilly 1.1.2.20 177 cananian 1.11 public List<Edge> edgeC() { 178 cananian 1.11 return new AbstractList<Edge>() { 179 sportbilly 1.1.2.20 public int size() { return next.length + prev.length; } 180 cananian 1.11 public Edge get(int index) { 181 cananian 1.11 return (index < next.length) ? 182 cananian 1.11 next[index] : 183 cananian 1.11 prev[index - next.length]; 184 sportbilly 1.1.2.20 } 185 sportbilly 1.1.2.20 }; 186 sportbilly 1.1.2.20 } 187 cananian 1.11 public List<Edge> predC() { // unmodifiable list 188 cananian 1.11 return new AbstractList<Edge>() { 189 cananian 1.11 public int size() { return prev.length; } 190 cananian 1.11 public Edge get(int i) { return prev[i]; } 191 cananian 1.11 }; 192 sportbilly 1.1.2.20 } 193 cananian 1.11 public List<Edge> succC() { // unmodifiable list 194 cananian 1.11 return new AbstractList<Edge>() { 195 cananian 1.11 public int size() { return next.length; } 196 cananian 1.11 public Edge get(int i) { return next[i]; } 197 cananian 1.11 }; 198 cananian 1.10 } 199 cananian 1.10 public boolean isSucc(Quad q) { 200 cananian 1.10 for (int i=0;i<next.length; i++) 201 cananian 1.10 if (next[i].equals(q)) return true; 202 cananian 1.10 return false; 203 cananian 1.10 } 204 cananian 1.10 public boolean isPred(Quad q) { 205 cananian 1.10 for (int i=0;i<prev.length; i++) 206 cananian 1.10 if (prev[i].equals(q)) return true; 207 cananian 1.10 return false; 208 sportbilly 1.1.2.20 } 209 cananian 1.1.2.1 210 cananian 1.1.2.1 /** Adds an edge between two Quads. The <code>from_index</code>ed 211 cananian 1.1.2.1 * outgoing edge of <code>from</code> is connected to the 212 cananian 1.1.2.1 * <code>to_index</code>ed incoming edge of <code>to</code>. 213 cananian 1.1.2.1 * @return the added <code>Edge</code>.*/ 214 cananian 1.1.2.1 public static Edge addEdge(Quad from, int from_index, 215 cananian 1.1.2.1 Quad to, int to_index) { 216 cananian 1.1.2.4 // assert validity 217 cananian 1.3.2.1 assert from.qf == to.qf : "QuadFactories should always be same"; 218 cananian 1.1.2.4 // [HEADERs connect only to FOOTER and METHOD] 219 cananian 1.1.2.4 if (from instanceof HEADER) 220 cananian 1.3.2.1 assert (to instanceof FOOTER && from_index==0) || 221 cananian 1.3.2.1 (to instanceof METHOD && from_index==1); 222 cananian 1.1.2.4 // [METHOD connects to HANDLERs on all but first edge] 223 cananian 1.1.2.4 if (from instanceof METHOD && from_index > 0) 224 cananian 1.3.2.1 assert to instanceof HANDLER; 225 cananian 1.1.2.4 // [ONLY HEADER, THROW and RETURN connects to FOOTER] 226 cananian 1.1.2.4 if (to instanceof FOOTER) 227 cananian 1.3.2.1 assert (from instanceof HEADER && to_index==0) || 228 cananian 1.1.2.4 (from instanceof THROW && to_index >0) || 229 cananian 1.3.2.1 (from instanceof RETURN && to_index >0); 230 cananian 1.7 // increment parent's modification count (for fail-fast iterator) 231 cananian 1.7 from.qf.getParent().modCount++; 232 cananian 1.1.2.4 // OK, add the edge. 233 cananian 1.1.2.1 Edge e = new Edge(from, from_index, to, to_index); 234 cananian 1.1.2.1 from.next[from_index] = e; 235 cananian 1.1.2.1 to.prev[to_index] = e; 236 cananian 1.1.2.1 return e; 237 cananian 1.1.2.1 } 238 cananian 1.1.2.1 /** Add edges between a string of Quads. The first outgoing edge 239 cananian 1.1.2.1 * is connected to the first incoming edge for all edges added. 240 cananian 1.1.2.1 * The same as multiple <code>addEdge(q[i], 0, q[i+1], 0)</code> 241 cananian 1.1.2.1 * calls. */ 242 cananian 1.1.2.1 public static void addEdges(Quad[] quadlist) { 243 cananian 1.1.2.1 for (int i=0; i<quadlist.length-1; i++) 244 cananian 1.1.2.1 addEdge(quadlist[i], 0, quadlist[i+1], 0); 245 cananian 1.1.2.1 } 246 cananian 1.1.2.5 /** Replace one quad with another. The number of in and out edges of 247 cananian 1.1.2.5 * the new and old quads must match exactly. */ 248 cananian 1.1.2.3 public static void replace(Quad oldQ, Quad newQ) { 249 cananian 1.3.2.1 assert oldQ.next.length == newQ.next.length; 250 cananian 1.3.2.1 assert oldQ.prev.length == newQ.prev.length; 251 cananian 1.1.2.3 for (int i=0; i<oldQ.next.length; i++) { 252 cananian 1.1.2.3 Edge e = oldQ.next[i]; 253 pnkfelix 1.1.2.26 Quad to = (Quad) e.to(); 254 cananian 1.1.2.27 if (to == oldQ) to = newQ;// detect & fixup self-loops 255 pnkfelix 1.1.2.26 addEdge(newQ, i, to, e.which_pred()); 256 cananian 1.1.2.3 oldQ.next[i] = null; 257 cananian 1.1.2.3 } 258 cananian 1.1.2.3 for (int i=0; i<oldQ.prev.length; i++) { 259 cananian 1.1.2.3 Edge e = oldQ.prev[i]; 260 pnkfelix 1.1.2.26 Quad from = (Quad) e.from(); 261 cananian 1.1.2.27 if (from == oldQ) from = newQ;// detect & fixup self-loops 262 pnkfelix 1.1.2.26 addEdge(from, e.which_succ(), newQ, i); 263 cananian 1.1.2.3 oldQ.prev[i] = null; 264 cananian 1.1.2.3 } 265 cananian 1.1.2.44 } 266 cananian 1.1.2.44 /** Remove this quad from the graph. The given quad must have 267 cananian 1.1.2.44 * exactly one predecessor and one successor. Also removes the 268 cananian 1.1.2.48 * quad from any handler sets it may belong to. Returns the 269 cananian 1.1.2.48 * new edge which replaces this quad. */ 270 cananian 1.1.2.48 public Edge remove() { 271 cananian 1.3.2.1 assert this.next.length == 1; 272 cananian 1.3.2.1 assert this.prev.length == 1; 273 cananian 1.1.2.44 this.removeHandlers(this.handlers()); 274 cananian 1.1.2.44 Edge in = this.prev[0], out = this.next[0]; 275 cananian 1.1.2.48 Edge result = addEdge((Quad)in.from(), in.which_succ(), 276 cananian 1.1.2.48 (Quad)out.to(), out.which_pred()); 277 cananian 1.1.2.44 this.prev[0] = this.next[0] = null; 278 cananian 1.1.2.48 return result; 279 cananian 1.1.2.27 } 280 cananian 1.1.2.27 /** Update the handlers for newQ to match the handlers for oldQ, 281 cananian 1.1.2.27 * removing handlers from oldQ in the process. 282 cananian 1.1.2.27 */ 283 cananian 1.1.2.27 public static void transferHandlers(Quad oldQ, Quad newQ) { 284 cananian 1.1.2.9 // replace in HANDLERs. 285 cananian 1.1.2.43 HandlerSet hs = oldQ.handlers(); 286 cananian 1.1.2.43 oldQ.removeHandlers(hs); 287 cananian 1.1.2.43 newQ.addHandlers(hs); 288 cananian 1.1.2.42 } 289 cananian 1.1.2.42 /** Add this quad to the given handler sets. */ 290 cananian 1.1.2.42 public final void addHandlers(HandlerSet handlers) { 291 cananian 1.1.2.42 for (HandlerSet hs=handlers; hs!=null; hs=hs.next) 292 cananian 1.1.2.42 hs.h.protectedSet.insert(this); 293 cananian 1.1.2.43 } 294 cananian 1.1.2.43 /** Remove this quad from the given handler sets. */ 295 cananian 1.1.2.43 public final void removeHandlers(HandlerSet handlers) { 296 cananian 1.1.2.43 for (HandlerSet hs=handlers; hs!=null; hs=hs.next) 297 cananian 1.1.2.43 hs.h.protectedSet.remove(this); 298 cananian 1.1.2.9 } 299 cananian 1.1.2.32 /** Return a set of all the handlers guarding this <code>Quad</code>. */ 300 cananian 1.1.2.9 public final HandlerSet handlers() { 301 cananian 1.1.2.9 METHOD Qm = (METHOD)qf.getParent().quads.next(1); 302 cananian 1.1.2.9 HandlerSet hs=null; 303 cananian 1.1.2.9 Quad ql[] = Qm.next(); 304 cananian 1.1.2.9 for (int i=ql.length-1; i > 0; i--) // next(0) is not a HANDLER 305 cananian 1.1.2.9 if (((HANDLER)ql[i]).isProtected(this)) 306 cananian 1.1.2.9 hs=new HandlerSet((HANDLER)ql[i], hs); 307 cananian 1.1.2.9 return hs; 308 cananian 1.1.2.17 } 309 cananian 1.1.2.17 //----------------------------------------------------- 310 cananian 1.1.2.17 // Comparable interface. 311 cananian 1.3.2.2 public int compareTo(Quad o) { 312 cananian 1.3.2.2 int cmp = o.getID() - this.getID(); 313 cananian 1.1.2.17 if (cmp==0 && !this.equals(o)) 314 cananian 1.1.2.17 throw new ClassCastException("Comparing uncomparable Quads."); 315 cananian 1.1.2.17 return cmp; 316 cananian 1.1.2.3 } 317 cananian 1.1.2.1 //----------------------------------------------------- 318 cananian 1.1.2.1 // support cloning. The pred/succ quads are not cloned, but the 319 cananian 1.1.2.1 // array holding them is. 320 cananian 1.8 public final Quad clone() { return rename(this.qf, null, null); } 321 cananian 1.1.2.35 /** Clone a quad into a new quad factory, renaming all of the temps 322 cananian 1.1.2.35 * according to <code>tm</code> (which ought to ensure that all 323 cananian 1.1.2.35 * the new temps belong to the <code>TempFactory</code> of the 324 cananian 1.1.2.35 * new <code>QuadFactory</code>). */ 325 cananian 1.8 public final Quad clone(QuadFactory qf, CloningTempMap tm) { 326 cananian 1.1.2.13 Quad qc = rename(qf, tm, tm); 327 cananian 1.1.2.13 // verify that cloning is legit. 328 cananian 1.1.2.13 for (int j=0; j<2; j++) { 329 cananian 1.1.2.13 Temp[] ta = (j==0)?qc.use():qc.def(); 330 cananian 1.1.2.13 for (int i=0; i<ta.length; i++) 331 cananian 1.3.2.1 assert ta[i].tempFactory()==qf.tempFactory() : "TempFactories should be same"; 332 cananian 1.1.2.13 } 333 cananian 1.1.2.13 return qc; 334 cananian 1.1.2.13 } 335 cananian 1.1.2.1 336 cananian 1.1.2.1 //----------------------------------------------------- 337 cananian 1.1.2.1 /** Create a new copy of a string of <code>Quad</code>s starting at 338 cananian 1.1.2.8 * the given header using <code>QuadFactory</code>. */ 339 cananian 1.1.2.8 public static Quad clone(QuadFactory qf, Quad header) 340 cananian 1.1.2.1 { 341 cananian 1.3.2.1 assert header instanceof HEADER : "Argument to Quad.clone() should be a HEADER."; 342 cananian 1.8 return copyone(qf, header, new HashMap<Quad,Quad>(), 343 cananian 1.1.2.13 new CloningTempMap(header.qf.tempFactory(), 344 cananian 1.1.2.13 qf.tempFactory())); 345 cananian 1.1.2.1 } 346 cananian 1.1.2.21 /** Create a new copy of a string of <code>Quad</code>s starting 347 cananian 1.1.2.21 * at the given header using the specified 348 cananian 1.1.2.39 * <code>QuadFactory</code>, and returns a set 349 cananian 1.1.2.39 * of mappings. The cloned quads will be rooted at 350 cananian 1.1.2.39 * <code>elementMap().get(header)</code>. 351 cananian 1.1.2.21 */ 352 cananian 1.8 static HCodeAndMaps<Quad> cloneWithMaps(QuadFactory qf, Quad header) 353 cananian 1.1.2.21 { 354 cananian 1.3.2.1 assert header instanceof HEADER : "Argument to Quad.clone() should be a HEADER."; 355 cananian 1.8 Map<Quad,Quad> qm = new HashMap<Quad,Quad>(); 356 cananian 1.1.2.21 CloningTempMap ctm = new CloningTempMap(header.qf.tempFactory(), 357 cananian 1.1.2.21 qf.tempFactory()); 358 cananian 1.1.2.21 copyone(qf, header, qm, ctm); 359 cananian 1.1.2.39 // make new-to-old mappings from old-to-new mappings. 360 cananian 1.8 final Map<Quad,Quad> n2oQuad = new HashMap<Quad,Quad>(); 361 cananian 1.8 final Map<Temp,Temp> n2oTemp = new HashMap<Temp,Temp>(); 362 cananian 1.13 for (Map.Entry<Quad,Quad> me : qm.entrySet()) { 363 cananian 1.8 Quad qO = me.getKey(), qN = me.getValue(); 364 cananian 1.1.2.39 n2oQuad.put(qN, qO); 365 cananian 1.1.2.38 } 366 cananian 1.13 for (Map.Entry<Temp,Temp> me : ctm.asMap().entrySet()) { 367 cananian 1.8 Temp tO = me.getKey(), tN = me.getValue(); 368 cananian 1.1.2.39 n2oTemp.put(tN, tO); 369 cananian 1.1.2.38 } 370 cananian 1.1.2.39 // make type-safe tuple of immutable maps to return. 371 cananian 1.1.2.46 // NOTE THE NULLS: THIS IS NOT A FULL RESULT: YOU SHOULD BE 372 cananian 1.1.2.46 // USING HCode.clone() or Code.cloneHelper() IF YOU WANT A 373 cananian 1.1.2.46 // VALID HCODEANDMAPS! 374 cananian 1.8 return new HCodeAndMaps<Quad>(null, 375 cananian 1.1.2.39 Collections.unmodifiableMap(qm), 376 cananian 1.1.2.39 ctm.unmodifiable(), 377 cananian 1.1.2.46 null, 378 cananian 1.1.2.39 Collections.unmodifiableMap(n2oQuad), 379 cananian 1.1.2.39 new TempMap() { 380 cananian 1.8 public Temp tempMap(Temp t) { return n2oTemp.get(t); } 381 cananian 1.1.2.39 }); 382 cananian 1.1.2.21 } 383 cananian 1.8 private static Quad copyone(QuadFactory qf, Quad q, Map<Quad,Quad> old2new, 384 cananian 1.6 CloningTempMap ctm) { 385 cananian 1.6 // we split copyone in half and used an explicit worklist to 386 cananian 1.6 // avoid deep recursion which was crashing the JVM. 387 cananian 1.6 WorkSet<Quad> worklist = new WorkSet<Quad>(); 388 cananian 1.6 Quad r = copyoneStart(qf, q, old2new, ctm, worklist); 389 cananian 1.6 while (!worklist.isEmpty()) 390 cananian 1.6 copyoneFinish(qf, worklist.removeFirst(), 391 cananian 1.6 old2new, ctm, worklist); 392 cananian 1.6 return r; 393 cananian 1.6 } 394 cananian 1.6 395 cananian 1.8 private static Quad copyoneStart(QuadFactory qf, Quad q, 396 cananian 1.8 Map<Quad,Quad> old2new, 397 cananian 1.6 CloningTempMap ctm, WorkSet<Quad> ws) { 398 cananian 1.8 Quad r = old2new.get(q); 399 cananian 1.1.2.1 // if we've already done this one, return previous clone. 400 cananian 1.1.2.1 if (r!=null) return r; 401 cananian 1.1.2.21 // clone the fields, add to map. 402 cananian 1.8 r = q.clone(qf, ctm); 403 cananian 1.1.2.1 old2new.put(q, r); 404 cananian 1.6 // we need to fix up this quad. 405 cananian 1.6 ws.add(q); 406 cananian 1.6 // okay, return for now. We're not done yet, but done w/ first part. 407 cananian 1.6 return r; 408 cananian 1.6 } 409 cananian 1.8 private static void copyoneFinish(QuadFactory qf, Quad q, 410 cananian 1.8 Map<Quad,Quad> old2new, 411 cananian 1.6 CloningTempMap ctm, WorkSet<Quad> ws) { 412 cananian 1.8 Quad r = old2new.get(q); 413 cananian 1.6 assert r!=null; 414 cananian 1.1.2.1 // fixup the edges. 415 cananian 1.1.2.1 for (int i=0; i<q.next.length; i++) { 416 cananian 1.3.2.1 assert q.next[i].from == q; 417 cananian 1.6 Quad to = copyoneStart(qf, q.next[i].to, old2new, ctm, ws); 418 cananian 1.1.2.1 Quad.addEdge(r, q.next[i].from_index, to, q.next[i].to_index); 419 cananian 1.1.2.1 } 420 cananian 1.1.2.1 for (int i=0; i<q.prev.length; i++) { 421 cananian 1.3.2.1 assert q.prev[i].to == q; 422 cananian 1.6 Quad from = copyoneStart(qf, q.prev[i].from, old2new, ctm, ws); 423 cananian 1.1.2.1 Quad.addEdge(from, q.prev[i].from_index, r, q.prev[i].to_index); 424 cananian 1.1.2.40 } 425 cananian 1.1.2.40 // for HANDLER quads, fixup the protectedSet. 426 cananian 1.1.2.41 if (r instanceof HANDLER) { 427 cananian 1.1.2.41 HANDLER h = (HANDLER) r; 428 cananian 1.1.2.41 HANDLER.ProtectedSet ps = h.protectedSet; 429 cananian 1.1.2.40 // map all protected quads. 430 cananian 1.1.2.41 Quad[] oldqs=(Quad[])h.protectedSet().toArray(new Quad[ps.size()]); 431 cananian 1.1.2.41 for (int i=0; i < oldqs.length; i++) { 432 cananian 1.1.2.41 ps.remove(oldqs[i]); 433 cananian 1.6 ps.insert(copyoneStart(qf, oldqs[i], old2new, ctm, ws)); 434 cananian 1.1.2.40 } 435 cananian 1.1.2.1 } 436 cananian 1.1.2.3 } 437 cananian 1.1.2.3 // ---------------------------------------------------- 438 cananian 1.1.2.13 // Useful for temp renaming. Exported only to subclasses. 439 cananian 1.1.2.35 /** Apply <code>TempMap</code> <code>tm</code> to <code>Temp</code> 440 cananian 1.1.2.35 * <code>t</code>. 441 cananian 1.1.2.35 * @return <code>tm.tempMap(t)</code> if <code>t</code> is 442 cananian 1.1.2.35 * non-<code>null</code>, or <code>null</code> if <code>t</code> is 443 cananian 1.1.2.35 * <code>null</code>. */ 444 cananian 1.1.2.11 protected final static Temp map(TempMap tm, Temp t) { 445 cananian 1.1.2.6 return (t==null)?null:(tm==null)?t:tm.tempMap(t); 446 cananian 1.1.2.3 } 447 cananian 1.1.2.35 /** Apply <code>TempMap</code> to array of <code>Temp</code>s. 448 cananian 1.1.2.35 * Null <code>Temp</code>s get mapped to <code>null</code>. */ 449 cananian 1.1.2.11 protected final static Temp[] map(TempMap tm, Temp[] ta) { 450 cananian 1.1.2.3 Temp[] r = new Temp[ta.length]; 451 cananian 1.1.2.3 for (int i=0; i<r.length; i++) 452 cananian 1.1.2.3 r[i] = map(tm, ta[i]); 453 cananian 1.1.2.3 return r; 454 cananian 1.1.2.3 } 455 cananian 1.1.2.35 /** Apply <code>TempMap</code> to 2-d array of <code>Temp</code>s. 456 cananian 1.1.2.35 * Null <code>Temp</code>s get mapped to <code>null</code>. */ 457 cananian 1.1.2.11 protected final static Temp[][] map(TempMap tm, Temp[][] taa) { 458 cananian 1.1.2.3 Temp[][] r = new Temp[taa.length][]; 459 cananian 1.1.2.3 for (int i=0; i<r.length; i++) 460 cananian 1.1.2.3 r[i] = map(tm, taa[i]); 461 cananian 1.1.2.1 return r; 462 cananian 1.1.2.1 } 463 cananian 1.2 }