1
2
3
4 package net.sf.bddbddb.dataflow;
5
6 import java.util.Comparator;
7 import java.util.HashMap;
8 import java.util.Iterator;
9 import java.util.Map;
10 import java.util.SortedMap;
11 import java.util.TreeMap;
12
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 import net.sf.bddbddb.ir.OperationVisitor;
18 import net.sf.bddbddb.ir.dynamic.If;
19 import net.sf.bddbddb.ir.dynamic.Nop;
20 import net.sf.bddbddb.ir.highlevel.Copy;
21 import net.sf.bddbddb.ir.highlevel.Difference;
22 import net.sf.bddbddb.ir.highlevel.Free;
23 import net.sf.bddbddb.ir.highlevel.GenConstant;
24 import net.sf.bddbddb.ir.highlevel.Invert;
25 import net.sf.bddbddb.ir.highlevel.Join;
26 import net.sf.bddbddb.ir.highlevel.JoinConstant;
27 import net.sf.bddbddb.ir.highlevel.Load;
28 import net.sf.bddbddb.ir.highlevel.Project;
29 import net.sf.bddbddb.ir.highlevel.Rename;
30 import net.sf.bddbddb.ir.highlevel.Save;
31 import net.sf.bddbddb.ir.highlevel.Union;
32 import net.sf.bddbddb.ir.highlevel.Universe;
33 import net.sf.bddbddb.ir.highlevel.Zero;
34 import net.sf.bddbddb.ir.lowlevel.ApplyEx;
35 import net.sf.bddbddb.ir.lowlevel.BDDProject;
36 import net.sf.bddbddb.ir.lowlevel.Replace;
37
38 /***
39 * CopyProp
40 *
41 * @author mcarbin
42 * @version $Id: CopyProp.java 445 2005-02-21 02:32:50Z cs343 $
43 */
44 public class CopyProp extends OperationProblem implements IRPass {
45
46 IR ir;
47 Map opIns;
48 boolean TRACE = false;
49
50 public CopyProp(IR ir) {
51 this.ir = ir;
52 opIns = new HashMap();
53 }
54
55 public boolean run() {
56 IterationList list = ir.graph.getIterationList();
57 DataflowSolver df_solver = new DataflowSolver();
58 df_solver.solve(this, list);
59 return transform(list);
60 }
61
62 public void setIn(Operation op, CopyPropFact fact) {
63 opIns.put(op, fact);
64 }
65
66 public CopyPropFact getIn(Operation op) {
67 return (CopyPropFact) opIns.get(op);
68 }
69 public class CopyPropFact implements OperationFact {
70 Operation op;
71 Map copies;
72 IterationList loc;
73
74
75 public CopyPropFact() {
76 copies = new HashMap();
77
78 }
79
80 public Relation getCopy(Relation r) {
81 return (Relation) copies.get(r);
82 }
83
84
85
86
87
88
89 public Operation getOperation() {
90 return op;
91 }
92
93
94
95
96
97
98 public Fact join(Fact that) {
99 CopyPropFact thatFact = (CopyPropFact) that;
100 CopyPropFact result = new CopyPropFact();
101 result.copies.putAll(this.copies);
102 Map thatCopies = thatFact.copies;
103 for (Iterator it = this.copies.entrySet().iterator(); it.hasNext();) {
104 Map.Entry e = (Map.Entry) it.next();
105 Relation thisKey = (Relation) e.getKey();
106 Relation thisValue = (Relation) e.getValue();
107 Relation thatValue = (Relation) thatCopies.get(thisKey);
108 if (thatValue == null) {
109 result.copies.remove(thisKey);
110 } else {
111 if (!thisValue.equals(thatValue)) result.copies.remove(thisKey);
112 }
113 }
114 result.loc = this.loc;
115 return result;
116 }
117
118 public CopyPropFact copy() {
119 CopyPropFact result = new CopyPropFact();
120 result.copies.putAll(this.copies);
121 result.op = this.op;
122 result.loc = this.loc;
123 return result;
124 }
125
126
127
128
129
130
131 public Fact copy(IterationList loc) {
132 CopyPropFact c = copy();
133 c.loc = loc;
134 return c;
135 }
136
137
138
139
140
141
142 public void setLocation(IterationList loc) {
143 this.loc = loc;
144 }
145
146
147
148
149
150
151 public IterationList getLocation() {
152 return loc;
153 }
154
155
156
157
158 public boolean equals(Object o) {
159 if (o instanceof CopyPropFact) {
160 return this.copies.equals(((CopyPropFact) o).copies);
161 }
162 return false;
163 }
164
165
166
167
168 public int hashCode() {
169 return this.copies.hashCode();
170 }
171
172 public String toString() {
173 return copies.toString();
174 }
175 }
176 /***
177 * @author Administrator
178 *
179 * TODO To change the template for this generated type comment go to Window -
180 * Preferences - Java - Code Style - Code Templates
181 */
182 public class CopyPropTF extends TransferFunction {
183 Operation op;
184
185 /***
186 * @param op
187 */
188 public CopyPropTF(Operation op) {
189 super();
190 this.op = op;
191 }
192
193
194
195
196
197
198 public Fact apply(Fact f) {
199 CopyPropFact lastFact = (CopyPropFact) f;
200 setIn(op, lastFact);
201 CopyPropFact newFact = lastFact.copy();
202 Relation dest = op.getRelationDest();
203 for (Iterator it = newFact.copies.entrySet().iterator(); it.hasNext();) {
204 Map.Entry e = (Map.Entry) it.next();
205 Relation key = (Relation) e.getKey();
206 Relation value = (Relation) e.getValue();
207 if (key.equals(dest) || value.equals(dest)) it.remove();
208 }
209
210 if (op instanceof Copy) {
211 Copy cOp = (Copy) op;
212 Relation src = cOp.getSrc();
213 newFact.copies.put(cOp.getRelationDest(), src);
214 }
215 newFact.op = op;
216 setFact(op, newFact);
217 return newFact;
218 }
219 }
220
221
222
223
224
225
226 public boolean direction() {
227 return true;
228 }
229
230
231
232
233
234
235 public TransferFunction getTransferFunction(Operation o) {
236 return new CopyPropTF(o);
237 }
238
239
240
241
242
243
244 public Fact getBoundary() {
245 return new CopyPropFact();
246 }
247
248 public String toString() {
249 StringBuffer sb = new StringBuffer();
250 SortedMap sortedMap = new TreeMap(new Comparator() {
251 public int compare(Object o1, Object o2) {
252 return ((Operation) o1).id - ((Operation) o2).id;
253 }
254 });
255 sortedMap.putAll(operationFacts);
256 for (Iterator it = sortedMap.entrySet().iterator(); it.hasNext();) {
257 Map.Entry e = (Map.Entry) it.next();
258 sb.append("@" + e.getKey() + " : " + e.getValue() + '\n');
259 }
260 return sb.toString();
261 }
262
263 public boolean transform(IterationList list) {
264 boolean changed = false;
265 for (Iterator it = list.iterator(); it.hasNext();) {
266 Object o = it.next();
267 if (o instanceof Operation) {
268 Boolean b = (Boolean) ((Operation) o).visit(new Transformer());
269 if (!changed) changed = b.booleanValue();
270 } else {
271 boolean b = transform((IterationList) o);
272 if (!changed) changed = b;
273 }
274 }
275 if (list.isLoop()) {
276 boolean b = transform(list.getLoopEdge());
277 if (!changed) changed = b;
278 }
279 return changed;
280 }
281 class Transformer implements OperationVisitor {
282
283 public Object visitBinary(Operation op, Relation src1, Relation src2){
284 Boolean changed = Boolean.FALSE;
285 CopyPropFact fact = getIn(op);
286 Relation t1 = fact.getCopy(src1);
287 if (t1 != null && !t1.equals(src1)) {
288 if (TRACE) System.out.println(op + ": replacing " + src1 + " with " + t1);
289 op.replaceSrc(src1, t1);
290 changed = Boolean.TRUE;
291 }
292 Relation t2 = fact.getCopy(src2);
293 if (t2 != null && !t2.equals(src2)) {
294 if (TRACE) System.out.println(op + ": changing " + src2 + " to " + t2);
295 op.replaceSrc(src2, t2);
296 changed = Boolean.TRUE;
297 }
298 return changed;
299 }
300 public Object visitUnary(Operation op, Relation src){
301 CopyPropFact fact = getIn(op);
302 Relation t = fact.getCopy(src);
303 if (t != null && !t.equals(src)) {
304 if (TRACE) System.out.println(op + ": changing " + src + " to " + t);
305 op.replaceSrc(src, t);
306 return Boolean.TRUE;
307 }
308 return Boolean.FALSE;
309 }
310
311
312
313
314
315 public Object visit(Join op) {
316 Boolean changed = Boolean.FALSE;
317 Relation src1 = op.getSrc1();
318 Relation src2 = op.getSrc2();
319 return visitBinary(op,src1,src2);
320 }
321
322
323
324
325
326
327 public Object visit(Project op) {
328 Relation src = op.getSrc();
329 return visitUnary(op,src);
330 }
331
332 public Object visit(BDDProject op){
333 Relation src = op.getSrc();
334 return visitUnary(op,src);
335 }
336
337
338
339
340
341 public Object visit(Rename op) {
342 Relation src = op.getSrc();
343 return visitUnary(op,src);
344 }
345
346
347
348
349
350
351 public Object visit(Union op) {
352
353 Relation src1 = op.getSrc1();
354 Relation src2 = op.getSrc2();
355 return visitBinary(op,src1,src2);
356
357 }
358
359
360
361
362
363
364 public Object visit(Difference op) {
365 Relation src1 = op.getSrc1();
366 Relation src2 = op.getSrc2();
367 return visitBinary(op,src1,src2);
368 }
369
370
371
372
373
374
375 public Object visit(JoinConstant op) {
376 Relation src = op.getSrc();
377 return visitUnary(op,src);
378 }
379
380
381
382
383
384
385 public Object visit(GenConstant op) {
386 return Boolean.FALSE;
387 }
388
389
390
391
392
393
394 public Object visit(Free op) {
395 Relation src = op.getSrc();
396 return visitUnary(op,src);
397 }
398
399
400
401
402
403
404 public Object visit(Universe op) {
405 return Boolean.FALSE;
406 }
407
408
409
410
411
412
413 public Object visit(Zero op) {
414 return Boolean.FALSE;
415 }
416
417
418
419
420
421
422 public Object visit(Invert op) {
423 Relation src = op.getSrc();
424 return visitUnary(op,src);
425 }
426
427
428
429
430
431
432 public Object visit(Copy op) {
433 Relation src = op.getSrc();
434 return visitUnary(op,src);
435 }
436
437
438
439
440
441
442 public Object visit(Load op) {
443 return Boolean.FALSE;
444 }
445
446
447
448
449
450
451 public Object visit(Save op) {
452 Relation src = op.getSrc();
453 return visitUnary(op,src);
454 }
455
456
457
458
459
460
461 public Object visit(ApplyEx op) {
462 Relation src1 = op.getSrc1();
463 Relation src2 = op.getSrc2();
464 return visitBinary(op,src1,src2);
465 }
466
467
468
469
470
471
472 public Object visit(If op) {
473 return Boolean.FALSE;
474 }
475
476
477
478
479
480
481 public Object visit(Nop op) {
482 return Boolean.FALSE;
483 }
484
485 public Object visit(Replace op) {
486 Relation src = op.getSrc();
487 return visitUnary(op,src);
488 }
489
490
491 }
492
493
494
495
496
497 }