1 cananian 1.1.2.1 // Derivation.java, created Fri Jan 22 16:46:17 1999 by cananian
2 cananian 1.1.2.1 // Copyright (C) 1999 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.Analysis.Maps;
5 cananian 1.1.2.1
6 cananian 1.1.2.1 import harpoon.ClassFile.HCodeElement;
7 cananian 1.1.2.1 import harpoon.Temp.CloningTempMap;
8 cananian 1.1.2.1 import harpoon.Temp.Temp;
9 cananian 1.1.2.1 import harpoon.Temp.TempMap;
10 cananian 1.1.2.4 import harpoon.Util.Util;
11 cananian 1.1.2.1
12 cananian 1.1.2.4 import java.util.ArrayList;
13 cananian 1.1.2.4 import java.util.Collections;
14 cananian 1.1.2.4 import java.util.Comparator;
15 cananian 1.1.2.4 import java.util.Iterator;
16 cananian 1.1.2.4 import java.util.List;
17 cananian 1.1.2.1 /**
18 cananian 1.1.2.1 * <code>Derivation</code> provides a means to access the derivation
19 cananian 1.1.2.1 * of a particular derived pointer. Given a compiler temporary, it
20 cananian 1.1.2.1 * will enumerate the base pointers and signs needed to allow proper
21 cananian 1.1.2.1 * garbage collection of the derived pointer.<p>
22 cananian 1.1.2.1 * See Diwan, Moss, and Hudson, <A
23 cananian 1.1.2.1 * HREF="http://www.acm.org/pubs/citations/proceedings/pldi/143095/p273-diwan/"
24 cananian 1.1.2.1 * >"Compiler Support for Garbage Collection in a Statically Typed
25 cananian 1.1.2.1 * Language"</A> in PLDI'92 for background on the derivation structure
26 cananian 1.1.2.1 * and its motivations.
27 cananian 1.1.2.1 *
28 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
29 cananian 1.5 * @version $Id: Derivation.java,v 1.5 2002/09/02 19:23:26 cananian Exp $
30 cananian 1.1.2.1 */
31 cananian 1.5 public interface Derivation<HCE extends HCodeElement>
32 cananian 1.5 extends harpoon.Analysis.Maps.TypeMap<HCE> {
33 cananian 1.1.2.1
34 cananian 1.1.2.1 /** Map compiler temporaries to their derivations.
35 cananian 1.1.2.1 * @param t The temporary to query.
36 cananian 1.1.2.1 * @param hce A definition point for <code>t</code>.
37 cananian 1.1.2.1 * @return <code>null</code> if the temporary has no derivation (is
38 cananian 1.1.2.1 * a base pointer, for example), or the derivation otherwise.
39 cananian 1.1.2.1 * @exception NullPointerException if <code>t</code> or <code>hc</code>
40 cananian 1.1.2.1 * is <code>null</code>.
41 cananian 1.1.2.1 * @exception TypeNotKnownException if the <code>Derivation</code>
42 cananian 1.1.2.1 * has no information about <code>t</code> as defined
43 cananian 1.1.2.1 * at <code>hce</code>.
44 cananian 1.1.2.1 */
45 cananian 1.5 public DList derivation(HCE hce, Temp t)
46 cananian 1.1.2.9 throws TypeMap.TypeNotKnownException;
47 cananian 1.1.2.1
48 cananian 1.1.2.2 /** Structure of the derivation information.<p>
49 cananian 1.1.2.2 * Given three <code>Temp</code>s <code>t1</code>, <code>t2</code>,
50 cananian 1.1.2.2 * and <code>t3</code>, a derived pointer <code>d</code> whose value
51 cananian 1.1.2.2 * can be described by the equation:<pre>
52 cananian 1.1.2.2 * d = K + t1 - t2 + t3
53 cananian 1.1.2.3 * </pre> for some (non-constant) integer K at every point during
54 cananian 1.1.2.3 * runtime can be represented as the <code>DList</code><pre>
55 cananian 1.1.2.2 * new DList(t1, true, new DList(t2, false, new DList(t3, true)))
56 cananian 1.1.2.2 * </pre>.<p>
57 cananian 1.1.2.2 * <b>NOTE</b> that the temporaries named in the <code>DList</code>
58 cananian 1.1.2.2 * refer to the <i>reaching definitions</i> of those temporaries at
59 cananian 1.1.2.2 * the <i>definition point</i> of the variable with the derived
60 cananian 1.1.2.2 * type. In SSI/SSA forms, this does not matter, as every variable
61 cananian 1.1.2.2 * has exactly one reaching definition, but in other forms <b>it
62 cananian 1.1.2.2 * is the responsibility of the implementor</b> to ensure that the
63 cananian 1.1.2.2 * base pointers are not overwritten while the derived value is
64 cananian 1.1.2.2 * live.
65 cananian 1.1.2.7 * <p><b>ALSO NOTE</b> that the temporaries named in the
66 cananian 1.1.2.7 * <code>DList</code> are <i>base pointers</i> -- that is,
67 cananian 1.1.2.7 * they have pure types, <i>not derived types</i>. In particular,
68 cananian 1.1.2.7 * the <code>derivation()</code> method applied to any temporary
69 cananian 1.1.2.7 * named in a <code>DList</code> should return <code>null</code>.
70 cananian 1.1.2.7 * Derived types derived from other derived types are not allowed.
71 cananian 1.1.2.2 */
72 cananian 1.1.2.1 public static class DList {
73 cananian 1.1.2.1 /** Base pointer. */
74 cananian 1.1.2.1 public final Temp base;
75 cananian 1.1.2.1 /** Sign of base pointer. <code>true</code> if derived pointer
76 cananian 1.1.2.1 * equals offset <b>+</b> base pointer, <code>false</code> if
77 cananian 1.1.2.1 * derived pointer equals offset <b>-</b> base pointer. */
78 cananian 1.1.2.1 public final boolean sign;
79 cananian 1.1.2.1 /** Pointer to a continuation of the derivation, or <Code>null</code>
80 cananian 1.1.2.1 * if there are no more base pointers associated with this derived
81 cananian 1.1.2.1 * pointer. */
82 cananian 1.1.2.1 public final DList next;
83 cananian 1.1.2.4 /** Specifies whether this <code>DList</code> is in canonical form.
84 cananian 1.1.2.4 */
85 cananian 1.1.2.4 private final boolean canonical;
86 cananian 1.1.2.1 /** Constructor. */
87 cananian 1.1.2.1 public DList(Temp base, boolean sign, DList next) {
88 cananian 1.1.2.1 this.base = base; this.sign = sign; this.next = next;
89 cananian 1.1.2.4 // this is the rule for canonicalization:
90 cananian 1.1.2.4 this.canonical = (next == null) ||
91 cananian 1.1.2.4 (next.canonical && base==next.base && sign==next.sign) ||
92 cananian 1.1.2.4 (next.canonical && base.compareTo(next.base) < 0);
93 cananian 1.3.2.1 assert base!=null : "Null base pointer in DList.";
94 cananian 1.1.2.1 }
95 cananian 1.1.2.1
96 cananian 1.1.2.5 /** Returns a human-readable description of this <code>DList</code>. */
97 cananian 1.1.2.5 public String toString() {
98 cananian 1.1.2.5 return "<k>"+toString(canonicalize());
99 cananian 1.1.2.5 }
100 cananian 1.1.2.5 // helper function for toString().
101 cananian 1.1.2.5 private static String toString(DList dl) {
102 cananian 1.1.2.5 if (dl==null) return "";
103 cananian 1.1.2.5 else return (dl.sign?"+":"-") + dl.base + toString(dl.next);
104 cananian 1.1.2.5 }
105 cananian 1.1.2.4 /** Equality test. Compares the canonical forms of the
106 cananian 1.1.2.4 * <code>DList</code>s for strict equality. */
107 cananian 1.1.2.4 public boolean equals(Object o) {
108 cananian 1.1.2.4 if (!canonical) return canonicalize().equals(o);
109 cananian 1.1.2.4 if (!(o instanceof DList)) return false;
110 cananian 1.1.2.4 DList dl = (DList) o;
111 cananian 1.1.2.4 if (!dl.canonical) return this.equals(dl.canonicalize());
112 cananian 1.1.2.4 if (this.base != dl.base) return false;
113 cananian 1.1.2.4 if (this.sign != dl.sign) return false;
114 cananian 1.1.2.4 if (this.next == null || dl.next == null)
115 cananian 1.1.2.4 return this.next == dl.next;
116 cananian 1.1.2.4 else return this.next.equals(dl.next);
117 cananian 1.1.2.4 }
118 cananian 1.1.2.4 /** Canonicalize a <code>DList</code>. The canonicalized
119 cananian 1.1.2.4 * form of a <code>DList</code> has all components sorted
120 cananian 1.1.2.4 * by <code>Temp</code> (using the natural ordering of
121 cananian 1.1.2.4 * <code>Temp</code>s), and is algebraically simplified
122 cananian 1.1.2.4 * --- that is, components with the same <code>Temp</code>
123 cananian 1.1.2.4 * and opposite signs cancel out. */
124 cananian 1.1.2.4 public DList canonicalize() {
125 cananian 1.1.2.4 if (canonical) return this;
126 cananian 1.5 List<DList> l = new ArrayList<DList>();
127 cananian 1.1.2.4 for (DList dl=this; dl!=null; dl=dl.next)
128 cananian 1.1.2.4 l.add(dl);
129 cananian 1.5 Collections.sort(l, new Comparator<DList> () {
130 cananian 1.1.2.4 // reverse order by dl.temp natural ordering.
131 cananian 1.5 public int compare(DList dl1, DList dl2) {
132 cananian 1.1.2.4 int order = dl1.base.compareTo(dl2.base);
133 cananian 1.1.2.4 if (order==0) order = (dl1.sign?1:-1) - (dl2.sign?1:-1);
134 cananian 1.1.2.4 return -order; // reverse
135 cananian 1.1.2.4 }
136 cananian 1.1.2.4 });
137 cananian 1.1.2.4 DList result = null;
138 cananian 1.5 for (Iterator<DList> it=l.iterator(); it.hasNext(); it.next()) {
139 cananian 1.5 DList dl = it.next();
140 cananian 1.1.2.4 if (result!=null &&
141 cananian 1.1.2.4 result.base == dl.base &&
142 cananian 1.1.2.4 result.sign != dl.sign)
143 cananian 1.1.2.4 result = result.next; // cancel out component.
144 cananian 1.1.2.4 else
145 cananian 1.1.2.4 result = new DList(dl.base, dl.sign, result);
146 cananian 1.1.2.4 }
147 cananian 1.3.2.1 assert result!=null && result.canonical;
148 cananian 1.1.2.4 return result;
149 cananian 1.1.2.4 }
150 cananian 1.1.2.4
151 cananian 1.1.2.6 /** Returns a clean copy of this <code>DList</code>. Does
152 cananian 1.1.2.6 * not rename <code>Temp</code>s in any way. */
153 cananian 1.1.2.1 public static DList clone(DList dlist) {
154 cananian 1.1.2.1 if (dlist==null) return null;
155 cananian 1.1.2.1 else return new DList(dlist.base, dlist.sign, clone(dlist.next));
156 cananian 1.1.2.1 }
157 cananian 1.1.2.1
158 cananian 1.1.2.1 /** Returns a new <code>DList</code> with the <code>Temp</code>s
159 cananian 1.1.2.1 * renamed by the supplied mapping */
160 cananian 1.1.2.1 public static DList rename(DList dlist, TempMap tempMap)
161 cananian 1.1.2.1 {
162 cananian 1.1.2.1 if (dlist==null) return null;
163 cananian 1.1.2.1 else return new DList
164 cananian 1.1.2.6 ( tempMap==null ? dlist.base : tempMap.tempMap(dlist.base),
165 cananian 1.1.2.1 dlist.sign,
166 cananian 1.1.2.1 rename(dlist.next, tempMap));
167 cananian 1.1.2.1 }
168 cananian 1.1.2.1 }
169 cananian 1.2 }