1 cananian 1.1.2.9 // EqTempSets.java, created Thu May 25 20:26:25 2000 by pnkfelix
2 pnkfelix 1.1.2.1 /// EqTempSets.java, created Thu May 25 19:42:05 2000 by pnkfelix
3 cananian 1.1.2.9 // Copyright (C) 2000 Felix S. Klock II <pnkfelix@mit.edu>
4 pnkfelix 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
5 pnkfelix 1.1.2.1 package harpoon.Analysis.Instr;
6 pnkfelix 1.1.2.1
7 cananian 1.6 import net.cscott.jutil.DisjointSet;
8 cananian 1.6 import net.cscott.jutil.CombineIterator;
9 pnkfelix 1.1.2.1 import harpoon.Util.Util;
10 pnkfelix 1.1.2.1 import harpoon.Temp.Temp;
11 pnkfelix 1.1.2.1
12 pnkfelix 1.1.2.1 import java.util.List;
13 pnkfelix 1.1.2.1 import java.util.Map;
14 pnkfelix 1.1.2.1 import java.util.HashMap;
15 pnkfelix 1.1.2.1 import java.util.ArrayList;
16 pnkfelix 1.1.2.1 import java.util.Collections;
17 pnkfelix 1.1.2.1 import java.util.Iterator;
18 pnkfelix 1.1.2.1 import java.util.Set;
19 pnkfelix 1.1.2.1 import java.util.HashSet;
20 pnkfelix 1.1.2.1
21 pnkfelix 1.1.2.1 /**
22 pnkfelix 1.1.2.1 * <code>EqTempSets</code> tracks a set of disjoint set of temps, and
23 pnkfelix 1.1.2.1 * potentially associates each set with a favored register temp (which
24 pnkfelix 1.1.2.1 * itself is not part of the set)
25 cananian 1.1.2.8 * <p>
26 cananian 1.1.2.8 * Overview: an EqTempSets is a pair <S,M>, where <ul>
27 cananian 1.1.2.8 * <li> S is a set of disjoint sets of temps
28 cananian 1.1.2.8 * <li> M is a mapping from disjoint sets to register temps. </ul>
29 cananian 1.1.2.8 * Each element of S is represented by one of its members,
30 pnkfelix 1.1.2.1 * called the Representative (or Rep for short).
31 pnkfelix 1.1.2.1 *
32 cananian 1.1.2.9 * @author Felix S. Klock II <pnkfelix@mit.edu>
33 cananian 1.6 * @version $Id: EqTempSets.java,v 1.6 2004/02/08 01:52:07 cananian Exp $
34 pnkfelix 1.1.2.1 */
35 pnkfelix 1.1.2.7 public abstract class EqTempSets implements harpoon.Temp.TempMap {
36 pnkfelix 1.1.2.1
37 pnkfelix 1.1.2.1 /** Constructs and returns a new <code>EqTempSets</code>. The
38 pnkfelix 1.1.2.1 returned <code>EqTempSets</code> will have a usable toString()
39 pnkfelix 1.1.2.1 method (but have less efficent operation) if
40 pnkfelix 1.1.2.1 the <code>printable</code> argument is true.
41 pnkfelix 1.1.2.1 */
42 pnkfelix 1.1.2.1 public static EqTempSets make(RegAlloc ra, boolean printable) {
43 pnkfelix 1.1.2.1 EqTempSets eqt;
44 pnkfelix 1.1.2.1 if (printable) {
45 pnkfelix 1.1.2.1 eqt = new EqTempSets1();
46 pnkfelix 1.1.2.1 } else {
47 pnkfelix 1.1.2.1 eqt = new EqTempSets2();
48 pnkfelix 1.1.2.1 }
49 pnkfelix 1.1.2.1 eqt.ra = ra;
50 pnkfelix 1.1.2.1 return eqt;
51 pnkfelix 1.1.2.1 }
52 pnkfelix 1.1.2.1
53 pnkfelix 1.1.2.3 protected RegAlloc ra; // needed for isRegister operation
54 pnkfelix 1.1.2.1
55 pnkfelix 1.1.2.1 // maps set-representatives to the register associated with that
56 pnkfelix 1.1.2.1 // set. Undefined for sets not associated with a register.
57 pnkfelix 1.1.2.1 protected HashMap repToReg = new HashMap();
58 pnkfelix 1.1.2.1
59 pnkfelix 1.1.2.1 /** Associates <code>t</code> with <code>reg</code>.
60 pnkfelix 1.1.2.1 effects: M_post = { getRep( `t' ) -> `reg' } + M
61 pnkfelix 1.1.2.1 */
62 pnkfelix 1.1.2.1 public void associate(Temp t, Temp reg) {
63 pnkfelix 1.1.2.1 repToReg.put(getRep(t), reg);
64 pnkfelix 1.1.2.1 }
65 pnkfelix 1.1.2.1
66 pnkfelix 1.1.2.1 /** Returns the register temp associated with <code>t</code>.
67 pnkfelix 1.1.2.1 effects: if `t' is a register temp, returns `t'.
68 pnkfelix 1.1.2.1 else if the set for `t' has an
69 pnkfelix 1.1.2.1 register `r', returns `r'
70 pnkfelix 1.1.2.1 else returns null
71 pnkfelix 1.1.2.1 */
72 pnkfelix 1.1.2.1 public Temp getReg(Temp t) {
73 pnkfelix 1.1.2.3 if (ra.isRegister(t))
74 pnkfelix 1.1.2.1 return t;
75 pnkfelix 1.1.2.1 else {
76 pnkfelix 1.1.2.1 Temp rep = getRep(t);
77 pnkfelix 1.1.2.1 if (repToReg.containsKey(rep)) {
78 pnkfelix 1.1.2.1 return (Temp) repToReg.get(rep);
79 pnkfelix 1.1.2.1 } else {
80 pnkfelix 1.1.2.1 return null;
81 pnkfelix 1.1.2.1 }
82 pnkfelix 1.1.2.1 }
83 pnkfelix 1.1.2.1 }
84 pnkfelix 1.1.2.1
85 pnkfelix 1.1.2.7 public Temp tempMap(Temp t) {
86 pnkfelix 1.1.2.7 Temp r = getReg(t);
87 pnkfelix 1.1.2.7 if (r == null) r = getRep(t);
88 pnkfelix 1.1.2.7 return r;
89 pnkfelix 1.1.2.7 }
90 pnkfelix 1.1.2.7
91 pnkfelix 1.1.2.1 // optional operation that makes the sets in this immutable.
92 pnkfelix 1.1.2.1 void lock() { return; }
93 pnkfelix 1.1.2.1
94 pnkfelix 1.1.2.1 /** Adds an equivalency between <code>t1</code> and
95 pnkfelix 1.1.2.1 <code>t2</code> to <code>this</code>.
96 cananian 1.4 requires: <code>t1</code> or <code>t2</code> is not a register
97 cananian 1.4 modifies: <code>this</code>
98 cananian 1.4 effects: puts <code>t1</code> and <code>t2</code> in the same equivalence class,
99 pnkfelix 1.1.2.1 unifying all the temps in the two equivalence
100 cananian 1.4 classes for <code>t1</code> and <code>t2</code>
101 pnkfelix 1.1.2.1 unless:
102 pnkfelix 1.1.2.1 - one of the temps is a register and the equivalence
103 pnkfelix 1.1.2.1 set for the other temp already has a register
104 cananian 1.4 => no modification to <code>this</code>
105 pnkfelix 1.1.2.1 */
106 pnkfelix 1.1.2.1 public void add(Temp t1, Temp t2) {
107 cananian 1.3.2.1 assert (!ra.isRegister(t1)) ||
108 cananian 1.3.2.1 (!ra.isRegister(t2)) : "need non-register";
109 pnkfelix 1.1.2.1
110 pnkfelix 1.1.2.1 Temp rep1 = getRep(t1);
111 pnkfelix 1.1.2.1 Temp rep2 = getRep(t2);
112 pnkfelix 1.1.2.1
113 pnkfelix 1.1.2.3 if (ra.isRegister(t1)) {
114 pnkfelix 1.1.2.1 if ( repToReg.containsKey(rep2) ) {
115 pnkfelix 1.1.2.1 return;
116 pnkfelix 1.1.2.1 } else {
117 pnkfelix 1.1.2.1 repToReg.put(rep2, t1);
118 pnkfelix 1.1.2.1 }
119 pnkfelix 1.1.2.3 } else if (ra.isRegister(t2)) {
120 pnkfelix 1.1.2.1 if (repToReg.containsKey(rep1) ) {
121 pnkfelix 1.1.2.1 return;
122 pnkfelix 1.1.2.1 } else {
123 pnkfelix 1.1.2.1 repToReg.put(rep1, t2);
124 pnkfelix 1.1.2.1 }
125 pnkfelix 1.1.2.1 } else {
126 pnkfelix 1.1.2.1 union(t1, t2);
127 pnkfelix 1.1.2.1
128 pnkfelix 1.1.2.1 Temp newRep = getRep(t1);
129 pnkfelix 1.1.2.1
130 pnkfelix 1.1.2.1 if (repToReg.containsKey(rep1)) {
131 pnkfelix 1.1.2.1 Temp reg = (Temp) repToReg.get(rep1);
132 pnkfelix 1.1.2.1 repToReg.remove(rep1);
133 pnkfelix 1.1.2.1 repToReg.put(newRep, reg);
134 pnkfelix 1.1.2.1 }
135 pnkfelix 1.1.2.1 if (repToReg.containsKey(rep2)) {
136 pnkfelix 1.1.2.1 Temp reg = (Temp) repToReg.get(rep2);
137 pnkfelix 1.1.2.1 repToReg.remove(rep2);
138 pnkfelix 1.1.2.1 repToReg.put(newRep, reg);
139 pnkfelix 1.1.2.1 }
140 pnkfelix 1.1.2.1 }
141 pnkfelix 1.1.2.1 }
142 pnkfelix 1.1.2.1
143 pnkfelix 1.1.2.1 /** Returns the rep for <code>t</code>.
144 pnkfelix 1.1.2.1 effects: if `t' is not a register, returns the set-rep for
145 pnkfelix 1.1.2.1 the set containing `t'. If `t' is a register, returns
146 pnkfelix 1.1.2.1 `t'.
147 pnkfelix 1.1.2.1 */
148 pnkfelix 1.1.2.1 public abstract Temp getRep(Temp t);
149 pnkfelix 1.1.2.1
150 pnkfelix 1.1.2.1 /** Unifies <code>t1</code> and <code>t2</code>.
151 cananian 1.4 requires: <code>t1</code> and <code>t2</code> are not registers
152 cananian 1.4 modifies: <code>this</code>
153 pnkfelix 1.1.2.1 effects: unifies the equivalence classes for t1 and t2,
154 pnkfelix 1.1.2.1 removing the old equivalence sets and creating a
155 pnkfelix 1.1.2.1 new one whose rep is either t1 or t2.
156 pnkfelix 1.1.2.1 */
157 pnkfelix 1.1.2.1 protected abstract void union(Temp t1, Temp t2);
158 pnkfelix 1.1.2.1
159 pnkfelix 1.1.2.1 }
160 pnkfelix 1.1.2.1
161 pnkfelix 1.1.2.1 // (inefficient implementation with useful toString)
162 pnkfelix 1.1.2.1 class EqTempSets1 extends EqTempSets {
163 pnkfelix 1.1.2.1 private Map tempToSet = new HashMap();
164 pnkfelix 1.1.2.1 private Map setToRep = new HashMap();
165 pnkfelix 1.1.2.1 private List sets = new ArrayList();
166 pnkfelix 1.1.2.1
167 pnkfelix 1.1.2.1 private boolean locked = false;
168 pnkfelix 1.1.2.1
169 pnkfelix 1.1.2.1 void lock() {
170 pnkfelix 1.1.2.1 tempToSet = Collections.unmodifiableMap(tempToSet);
171 pnkfelix 1.1.2.1 setToRep = Collections.unmodifiableMap(setToRep);
172 pnkfelix 1.1.2.1 sets = Collections.unmodifiableList(sets);
173 pnkfelix 1.1.2.1 locked = true;
174 pnkfelix 1.1.2.1 }
175 pnkfelix 1.1.2.1
176 pnkfelix 1.1.2.1 public Temp getRep(Temp t) {
177 pnkfelix 1.1.2.3 if (ra.isRegister(t)) return t;
178 pnkfelix 1.1.2.1 Set s = (Set) tempToSet.get(t);
179 pnkfelix 1.1.2.1 if (s == null) {
180 pnkfelix 1.1.2.4 if (locked) return t;
181 pnkfelix 1.1.2.4
182 pnkfelix 1.1.2.1 s = new HashSet();
183 pnkfelix 1.1.2.1 sets.add(s);
184 pnkfelix 1.1.2.1 s.add(t);
185 pnkfelix 1.1.2.1 tempToSet.put(t, s);
186 pnkfelix 1.1.2.1 setToRep.put(s, t);
187 pnkfelix 1.1.2.1 return t;
188 pnkfelix 1.1.2.1 } else {
189 pnkfelix 1.1.2.1 return (Temp) setToRep.get(s);
190 pnkfelix 1.1.2.1 }
191 pnkfelix 1.1.2.1 }
192 pnkfelix 1.1.2.1 protected void union(Temp t1, Temp t2) {
193 pnkfelix 1.1.2.1 Set s1 = (Set) tempToSet.get(t1);
194 pnkfelix 1.1.2.1 if (s1 == null) s1 = new HashSet();
195 pnkfelix 1.1.2.1 Set s2 = (Set) tempToSet.get(t2);
196 pnkfelix 1.1.2.1 if (s2 == null) s2 = new HashSet();
197 pnkfelix 1.1.2.1
198 pnkfelix 1.1.2.1 HashSet s3 = new HashSet(s1);
199 pnkfelix 1.1.2.1 s3.addAll(s2);
200 pnkfelix 1.1.2.1 Iterator iter = new CombineIterator(s1.iterator(), s2.iterator());
201 pnkfelix 1.1.2.1 while(iter.hasNext()) {
202 pnkfelix 1.1.2.1 Temp t = (Temp) iter.next();
203 pnkfelix 1.1.2.1 tempToSet.put(t, s3);
204 pnkfelix 1.1.2.1 }
205 pnkfelix 1.1.2.1 setToRep.remove(s1); sets.remove(s1);
206 pnkfelix 1.1.2.1 setToRep.remove(s2); sets.remove(s2);
207 pnkfelix 1.1.2.1 setToRep.put(s3, t1); sets.add(s3);
208 pnkfelix 1.1.2.1 }
209 pnkfelix 1.1.2.1 public String toString() {
210 pnkfelix 1.1.2.5 StringBuffer sb = new StringBuffer(sets.size()*32);
211 pnkfelix 1.1.2.1 Iterator iter = sets.iterator();
212 pnkfelix 1.1.2.1 int i=0;
213 pnkfelix 1.1.2.1 while(iter.hasNext()) {
214 pnkfelix 1.1.2.1 i++;
215 pnkfelix 1.1.2.1 Set s = (Set) iter.next();
216 pnkfelix 1.1.2.1 sb.append("< Set"+i+": ");
217 pnkfelix 1.1.2.1 sb.append(s.toString());
218 pnkfelix 1.1.2.1 Object rep = setToRep.get(s);
219 pnkfelix 1.1.2.1 sb.append(", Rep:" + rep);
220 pnkfelix 1.1.2.1 sb.append(", Reg:" + repToReg.get(rep)+" >");
221 pnkfelix 1.1.2.2 if (iter.hasNext()) sb.append("\n");
222 pnkfelix 1.1.2.1 }
223 pnkfelix 1.1.2.1 return sb.toString();
224 pnkfelix 1.1.2.1 }
225 pnkfelix 1.1.2.1 }
226 pnkfelix 1.1.2.1
227 pnkfelix 1.1.2.1 // efficient implementation that will replace instances of
228 pnkfelix 1.1.2.1 // EqTempSets1 once the code using EqTempSets1 has been debugged
229 pnkfelix 1.1.2.1 // completely and EqTempSets1.toString() is not needed.
230 pnkfelix 1.1.2.1 class EqTempSets2 extends EqTempSets {
231 pnkfelix 1.1.2.1 private DisjointSet dss = new DisjointSet();
232 pnkfelix 1.1.2.1
233 pnkfelix 1.1.2.1 public Temp getRep(Temp t) {
234 pnkfelix 1.1.2.3 if (ra.isRegister(t))
235 pnkfelix 1.1.2.1 return t;
236 pnkfelix 1.1.2.1 else
237 pnkfelix 1.1.2.1 return (Temp) dss.find(t);
238 pnkfelix 1.1.2.1 }
239 pnkfelix 1.1.2.1
240 pnkfelix 1.1.2.1 protected void union(Temp t1, Temp t2) {
241 pnkfelix 1.1.2.1 dss.union(t1, t2);
242 pnkfelix 1.1.2.1 }
243 cananian 1.2 }