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      }