1
2
3
4 package net.sf.bddbddb.dataflow;
5
6 import java.util.AbstractSet;
7 import java.util.Collection;
8 import java.util.HashMap;
9 import java.util.Iterator;
10 import java.util.Map;
11 import jwutil.math.BitString;
12 import jwutil.math.BitString.BitStringIterator;
13 import net.sf.bddbddb.IterationList;
14 import net.sf.bddbddb.Relation;
15 import net.sf.bddbddb.ir.IR;
16 import net.sf.bddbddb.ir.Operation;
17
18 /***
19 * DefUse
20 *
21 * @author jwhaley
22 * @version $Id: DefUse.java 328 2004-10-16 02:45:30Z joewhaley $
23 */
24 public class DefUse extends OperationProblem {
25 boolean TRACE = false;
26
27 BitString[] defs;
28 BitString[] uses;
29 Operation[] opMap;
30 IR ir;
31 Map
32
33 public DefUse(IR ir) {
34 this.ir = ir;
35 int numRelations = ir.getNumberOfRelations();
36 int numOperations = Operation.getNumberOfOperations();
37 if (TRACE) System.out.println(numRelations + " relations, " + numOperations + " operations");
38 this.defs = new BitString[numRelations];
39 for (int i = 0; i < defs.length; ++i) {
40 defs[i] = new BitString(numOperations);
41 }
42 this.uses = new BitString[numRelations];
43 for (int i = 0; i < uses.length; ++i) {
44 uses[i] = new BitString(numOperations);
45 }
46 opMap = new Operation[numOperations];
47 initialize(ir.graph.getIterationList());
48 opIns = new HashMap();
49 }
50
51 public void setIn(Operation op, Fact fact){
52 opIns.put(op,fact);
53 }
54
55 public DefUseFact getIn(Operation op){
56 return (DefUseFact) opIns.get(op);
57 }
58 void initialize(IterationList block) {
59 for (Iterator i = block.iterator(); i.hasNext();) {
60 Object o = i.next();
61 if (o instanceof IterationList) {
62 initialize((IterationList) o);
63 } else {
64 Operation op = (Operation) o;
65 opMap[op.id] = op;
66 Relation def = op.getRelationDest();
67 if (def != null) defs[def.id].set(op.id);
68 Collection use = op.getSrcs();
69 for (Iterator j = use.iterator(); j.hasNext();) {
70 Relation r = (Relation) j.next();
71 uses[r.id].set(op.id);
72 }
73 }
74 }
75 }
76
77 public OperationSet getDefs(Relation r) {
78 return new OperationSet(defs[r.id]);
79 }
80
81 public OperationSet getUses(Relation r) {
82 return new OperationSet(uses[r.id]);
83 }
84 public class OperationSet extends AbstractSet {
85 BitString s;
86
87 /***
88 * @param s
89 */
90 public OperationSet(BitString s) {
91 this.s = s;
92 }
93
94
95
96
97
98
99 public Iterator iterator() {
100 return new OperationIterator(s);
101 }
102
103
104
105
106
107
108 public boolean contains(Object o) {
109 if (o instanceof Operation) {
110 int id = ((Operation) o).id;
111 return s.get(id);
112 }
113 return false;
114 }
115
116
117
118
119
120
121 public int size() {
122 return s.numberOfOnes();
123 }
124 }
125 public class OperationIterator implements Iterator {
126 BitStringIterator i;
127
128 /***
129 * @param s
130 */
131 public OperationIterator(BitString s) {
132 i = s.iterator();
133 }
134
135
136
137
138
139
140 public boolean hasNext() {
141 return i.hasNext();
142 }
143
144
145
146
147
148
149 public Object next() {
150 int index = i.nextIndex();
151 return opMap[index];
152 }
153
154
155
156
157
158
159 public void remove() {
160 throw new UnsupportedOperationException();
161 }
162 }
163 public class DefUseFact extends UnionBitVectorFact implements OperationFact {
164 Operation op;
165
166 /***
167 * @param setSize
168 */
169 public DefUseFact(int setSize) {
170 super(setSize);
171 }
172
173 /***
174 * @param s
175 */
176 public DefUseFact(BitString s) {
177 super(s);
178 }
179
180
181
182
183
184
185 public UnionBitVectorFact create(BitString s) {
186 return new DefUseFact(s);
187 }
188
189
190
191
192
193
194 public String toString() {
195 StringBuffer sb = new StringBuffer();
196 for (BitStringIterator i = fact.iterator(); i.hasNext();) {
197 sb.append(opMap[i.nextIndex()]);
198 sb.append(" ");
199 }
200 return sb.toString();
201 }
202
203 /***
204 * Get the reaching defs for this relation.
205 *
206 * @param r relation
207 * @return reaching defs for this relation
208 */
209 public OperationSet getReachingDefs(Relation r) {
210 BitString bs = (BitString) fact.clone();
211 bs.and(defs[r.id]);
212 return new OperationSet(bs);
213 }
214
215 /***
216 * Get the reaching defs for this collection of relations.
217 *
218 * @param rs collection of relations
219 * @return reaching defs for these relations
220 */
221 public OperationSet getReachingDefs(Collection rs) {
222 BitString bs = new BitString(fact.size());
223 for (Iterator i = rs.iterator(); i.hasNext();) {
224 Relation r = (Relation) i.next();
225 bs.or(defs[r.id]);
226 }
227 bs.and(fact);
228 return new OperationSet(bs);
229 }
230
231
232
233
234
235
236 public Operation getOperation() {
237 return op;
238 }
239
240 }
241
242
243
244
245
246
247 public boolean direction() {
248 return true;
249 }
250
251
252
253
254
255
256 public TransferFunction getTransferFunction(Operation op) {
257 return new DefUseTransferFunction(op);
258 }
259 public class DefUseTransferFunction extends OperationTransferFunction {
260 Operation op;
261
262 DefUseTransferFunction(Operation op) {
263 this.op = op;
264 }
265
266 public Fact apply(Fact f) {
267
268 DefUseFact oldFact = (DefUseFact) f;
269 setIn(op, oldFact);
270 BitString bs = (BitString) oldFact.fact.clone();
271
272 Relation r = op.getRelationDest();
273 if (r != null) bs.minus(defs[r.id]);
274
275 bs.set(op.id);
276 DefUseFact newFact = (DefUseFact) oldFact.create(bs);
277 newFact.op = op;
278 setFact(op, newFact);
279 return newFact;
280 }
281 }
282
283
284
285
286
287
288 public Fact getBoundary() {
289 return new DefUseFact(Operation.getNumberOfOperations());
290 }
291 }