1
2
3
4 package net.sf.bddbddb.dataflow;
5
6 import java.util.HashMap;
7 import java.util.Iterator;
8 import java.util.LinkedList;
9 import java.util.List;
10 import java.util.Map;
11
12 import jwutil.collections.Pair;
13 import jwutil.util.Assert;
14 import net.sf.bddbddb.IterationList;
15 import net.sf.bddbddb.Relation;
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 import net.sf.javabdd.BDDFactory;
38
39 /***
40 * ConstantProp
41 *
42 * @author John Whaley
43 * @version $Id: ConstantProp.java 445 2005-02-21 02:32:50Z cs343 $
44 */
45 public class ConstantProp extends RelationProblem {
46 boolean TRACE = false;
47 final ConstantPropFact ZERO;
48 final ConstantPropFact BOTTOM;
49 Map factMap;
50 public ConstantPropFacts currentFacts;
51 Relation currentRelation;
52 IterationList currentLocation;
53
54 public boolean direction() {
55 return true;
56 }
57
58 public ConstantProp() {
59 factMap = new HashMap();
60 ZERO = new ConstantPropFact();
61 BOTTOM = new ConstantPropFact();
62 }
63
64 public Fact getBoundary() {
65 return new ConstantPropFacts();
66 }
67
68 ConstantPropFact getRepresentativeFact(Relation r, Operation op) {
69 ConstantPropFact f = (ConstantPropFact) currentFacts.getFact(r);
70 if (f == null) return allocNewRelation(r, op);
71 return f.getRepresentative();
72 }
73
74 void changeRelationValue(Relation r, ConstantPropFact fact) {
75 if (r == null) return;
76 if (TRACE) System.out.println("Changing relation " + r + " to " + fact);
77 ConstantPropFact old_f = (ConstantPropFact) currentFacts.getFact(r);
78 if (old_f != null) {
79 ConstantPropFact new_f = old_f.getRepresentative();
80 if (TRACE) System.out.println("Old value of relation: " + old_f);
81 if (old_f != new_f) if (TRACE) System.out.println("representative: " + new_f);
82 fact = fact.getRepresentative();
83 if (fact != new_f && old_f.backPointers != null) {
84 if (TRACE) System.out.println("Different fact! Replacing all copies of " + r);
85 for (Iterator i = old_f.backPointers.iterator(); i.hasNext();) {
86 ConstantPropFact f = (ConstantPropFact) i.next();
87 Assert._assert(f.representative == old_f);
88 if (old_f == new_f) {
89 if (TRACE) System.out.println("Relation is endpoint, using " + f
90 + " instead.");
91 new_f = f;
92 }
93 old_f.backPointers.remove(f);
94 f.representative = new_f;
95 new_f.backPointers.add(f);
96 }
97 }
98 }
99 currentFacts.relationFacts.put(r, fact);
100 }
101
102 ConstantPropFact allocNewRelation(Relation r, Object op) {
103 Object key = new Pair(r, op);
104 ConstantPropFact f = (ConstantPropFact) factMap.get(key);
105 if (f == null) {
106 factMap.put(key, f = new ConstantPropFact(r, op));
107 if (TRACE) System.out.println("Allocating fact for " + key + ": " + f);
108 }
109 return f;
110 }
111
112
113
114
115
116
117 public TransferFunction getTransferFunction(Operation op) {
118 return new ConstantPropTF(op);
119 }
120
121 boolean isSame(ConstantPropFact f1, ConstantPropFact f2) {
122 return f1 != BOTTOM && f1.equals(f2);
123 }
124 public class ConstantPropTF extends TransferFunction implements OperationVisitor {
125 Operation op;
126
127 public ConstantPropTF(Operation op) {
128 this.op = op;
129 }
130
131
132
133
134
135
136 public Fact apply(Fact f) {
137 currentFacts = (ConstantPropFacts) f;
138 ConstantPropFact result = (ConstantPropFact) op.visit(this);
139 changeRelationValue(op.getRelationDest(), result);
140 return currentFacts;
141 }
142
143
144
145
146
147
148 public Object visit(Join op) {
149 List srcs = op.getSrcs();
150 Relation r1 = (Relation) srcs.get(0);
151 Relation r2 = (Relation) srcs.get(1);
152 ConstantPropFact f1 = getRepresentativeFact(r1, op);
153 ConstantPropFact f2 = getRepresentativeFact(r2, op);
154 if (f1 == ZERO || f2 == ZERO) return ZERO;
155 if (isSame(f1, f2)) return f1;
156 return allocNewRelation(op.getRelationDest(), op);
157 }
158
159
160
161
162
163
164 public Object visit(Project op) {
165 List srcs = op.getSrcs();
166 Relation r1 = (Relation) srcs.get(0);
167 ConstantPropFact f1 = getRepresentativeFact(r1, op);
168 if (f1 == ZERO) return ZERO;
169 return allocNewRelation(op.getRelationDest(), op);
170 }
171
172 public Object visit(BDDProject op) {
173 List srcs = op.getSrcs();
174 Relation r1 = (Relation) srcs.get(0);
175 ConstantPropFact f1 = getRepresentativeFact(r1, op);
176 if (f1 == ZERO) return ZERO;
177 return allocNewRelation(op.getRelationDest(), op);
178 }
179
180
181
182
183
184
185 public Object visit(Rename op) {
186 List srcs = op.getSrcs();
187 Relation r1 = (Relation) srcs.get(0);
188 ConstantPropFact f1 = getRepresentativeFact(r1, op);
189 if (f1 == ZERO) return ZERO;
190 return allocNewRelation(op.getRelationDest(), op);
191 }
192
193
194
195
196
197
198 public Object visit(Union op) {
199 List srcs = op.getSrcs();
200 Relation r1 = (Relation) srcs.get(0);
201 Relation r2 = (Relation) srcs.get(1);
202 ConstantPropFact f1 = getRepresentativeFact(r1, op);
203 ConstantPropFact f2 = getRepresentativeFact(r2, op);
204 if (f1 == ZERO) return f2;
205 if (f2 == ZERO) return f1;
206 if (isSame(f1, f2)) return f1;
207 return allocNewRelation(op.getRelationDest(), op);
208 }
209
210
211
212
213
214
215 public Object visit(Difference op) {
216 List srcs = op.getSrcs();
217 Relation r1 = (Relation) srcs.get(0);
218 Relation r2 = (Relation) srcs.get(1);
219 ConstantPropFact f1 = getRepresentativeFact(r1, op);
220 ConstantPropFact f2 = getRepresentativeFact(r2, op);
221 if (f1 == ZERO) return ZERO;
222 if (f2 == ZERO) return f1;
223 if (isSame(f1, f2)) return ZERO;
224 return allocNewRelation(op.getRelationDest(), op);
225 }
226
227
228
229
230
231
232 public Object visit(JoinConstant op) {
233 List srcs = op.getSrcs();
234 Relation r1 = (Relation) srcs.get(0);
235 ConstantPropFact f1 = getRepresentativeFact(r1, op);
236 if (f1 == ZERO) return ZERO;
237 return allocNewRelation(op.getRelationDest(), op);
238 }
239
240
241
242
243
244
245 public Object visit(GenConstant op) {
246 return allocNewRelation(op.getRelationDest(), op);
247 }
248
249
250
251
252
253
254 public Object visit(Free op) {
255 return allocNewRelation(op.getRelationDest(), op);
256 }
257
258
259
260
261
262
263 public Object visit(Universe op) {
264 return allocNewRelation(op.getRelationDest(), op);
265 }
266
267
268
269
270
271
272 public Object visit(Zero op) {
273 return ZERO;
274 }
275
276
277
278
279
280
281 public Object visit(Invert op) {
282 return allocNewRelation(op.getRelationDest(), op);
283 }
284
285
286
287
288
289
290 public Object visit(Copy op) {
291 List srcs = op.getSrcs();
292 Relation r1 = (Relation) srcs.get(0);
293 ConstantPropFact f1 = getRepresentativeFact(r1, op);
294 return f1;
295 }
296
297
298
299
300
301
302 public Object visit(Load op) {
303 return allocNewRelation(op.getRelationDest(), op);
304 }
305
306
307
308
309
310
311 public Object visit(Save op) {
312 return null;
313 }
314
315
316
317
318
319
320 public Object visit(ApplyEx op) {
321 Relation r1 = op.getSrc1();
322 Relation r2 = op.getSrc2();
323 ConstantPropFact f1 = getRepresentativeFact(r1, op);
324 ConstantPropFact f2 = getRepresentativeFact(r2, op);
325 if (op.getOp() == BDDFactory.and) {
326 if (f1 == ZERO || f2 == ZERO) return ZERO;
327 } else if (op.getOp() == BDDFactory.diff) {
328 if (f1 == ZERO) return ZERO;
329 } else if (op.getOp() == BDDFactory.or || op.getOp() == BDDFactory.xor) {
330 if (f1 == ZERO && f2 == ZERO) return ZERO;
331 }
332 return allocNewRelation(op.getRelationDest(), op);
333 }
334
335
336
337
338
339
340 public Object visit(If op) {
341 return null;
342 }
343
344
345
346
347 public Object visit(Nop op){
348 return null;
349 }
350
351
352
353
354
355 public Object visit(Replace op) {
356 Relation r1 = op.getSrc();
357 ConstantPropFact f1 = getRepresentativeFact(r1, op);
358 return f1;
359 }
360 }
361 public class ConstantPropFact extends RelationFact {
362 Relation label;
363 Object op;
364 ConstantPropFact representative;
365 List backPointers;
366
367 public ConstantPropFact() {
368 label = null;
369 op = null;
370 representative = this;
371 }
372
373 public ConstantPropFact(Relation r, Object o) {
374 label = r;
375 op = o;
376 representative = this;
377 }
378
379 public ConstantPropFact(ConstantPropFact that) {
380 label = that.label;
381 op = that.op;
382 representative = that.representative;
383 }
384
385 void addBackPointer(ConstantPropFact that) {
386 if (backPointers == null) backPointers = new LinkedList();
387 backPointers.add(that);
388 }
389
390 void removeBackPointer(ConstantPropFact that) {
391 backPointers.remove(that);
392 }
393
394
395
396
397
398
399
400 public Fact join(Fact fact) {
401 ConstantPropFact that = (ConstantPropFact) fact;
402 if (this.equals(that)) return this;
403 if (TRACE) System.out.println("Join(" + this + " != " + that + ")");
404 Relation newLabel = currentRelation;
405 Fact result = allocNewRelation(newLabel, currentLocation);
406 if (TRACE) System.out.println("Result: " + result);
407 return result;
408 }
409
410 public ConstantPropFact getRepresentative() {
411 ConstantPropFact f = this;
412 while (f != f.representative)
413 f = f.representative;
414 if (true && this.representative != f) {
415
416 this.representative.removeBackPointer(this);
417 this.representative = f;
418 this.representative.addBackPointer(this);
419 }
420 return f;
421 }
422
423 public String toString() {
424 StringBuffer sb = new StringBuffer();
425 String name;
426 if (this == ZERO) name = "ZERO";
427 else if (this == BOTTOM) name = "BOTTOM";
428 else name = label.toString();
429 sb.append(name);
430 sb.append("@\"" + op + "\"");
431 if (this == representative) return sb.toString();
432 String rName;
433 if (representative == ZERO) rName = "ZERO";
434 else if (representative == BOTTOM) rName = "BOTTOM";
435 else rName = representative.label.toString();
436 sb.append(" (equal to ");
437 sb.append(rName);
438 sb.append("@\"" + representative.op + "\"");
439 sb.append(")");
440 return sb.toString();
441 }
442
443 public boolean equals(Object o) {
444 return equals((ConstantPropFact) o);
445 }
446
447 public boolean equals(ConstantPropFact that) {
448 if (this == that) return true;
449 return this.getRepresentative() == that.getRepresentative();
450 }
451
452 public int hashCode() {
453
454 return System.identityHashCode(this);
455 }
456
457 public Fact copy(IterationList loc) {
458 Assert.UNREACHABLE("");
459 return new ConstantPropFact(this);
460 }
461
462
463
464
465
466
467 public void setLocation(IterationList loc) {
468 Assert.UNREACHABLE("");
469 }
470
471 public IterationList getLocation() {
472 Assert.UNREACHABLE("");
473 return null;
474 }
475 }
476 public class ConstantPropFacts extends RelationFacts {
477 public RelationFacts create() {
478 return new ConstantPropFacts();
479 }
480
481 public Fact join(Fact fact) {
482 ConstantPropFacts that = (ConstantPropFacts) fact;
483 Assert._assert(this.location == that.location, this.location + " != " + that.location);
484 currentLocation = this.location;
485 ConstantPropFacts result = (ConstantPropFacts) create();
486 result.relationFacts.putAll(this.relationFacts);
487 for (Iterator i = that.relationFacts.entrySet().iterator(); i.hasNext();) {
488 Map.Entry e = (Map.Entry) i.next();
489 currentRelation = (Relation) e.getKey();
490 RelationFact f = (RelationFact) e.getValue();
491 RelationFact old = (RelationFact) result.relationFacts.put(currentRelation, f);
492 if (old != null) {
493 if (TRACE) System.out.println("Joining for relation " + currentRelation);
494 f = (RelationFact) f.join(old);
495 result.relationFacts.put(currentRelation, f);
496 }
497 }
498 result.location = this.location;
499 return result;
500 }
501
502 public Fact copy(IterationList loc) {
503 ConstantPropFacts that = new ConstantPropFacts();
504 that.relationFacts.putAll(this.relationFacts);
505 that.location = loc;
506 return that;
507 }
508
509 public boolean equals(RelationFacts that) {
510 if (this.relationFacts == that.relationFacts) return true;
511 if (relationFacts.size() != that.relationFacts.size()) {
512 if (TRACE) {
513 System.out.println("Size not equal ("+relationFacts.size()+" vs "+that.relationFacts.size());
514 Map m = new HashMap(relationFacts); m.keySet().removeAll(that.relationFacts.keySet());
515 System.out.println("New stuff: "+m);
516 }
517 return false;
518 }
519 Iterator i = relationFacts.entrySet().iterator();
520 while (i.hasNext()) {
521 Map.Entry e = (Map.Entry) i.next();
522 Object key = e.getKey();
523 Object value = e.getValue();
524 Object value2 = that.relationFacts.get(key);
525 if (!value.equals(value2)) {
526 if (TRACE) System.out.println("Key " + key + " differs: " + value + " vs "
527 + value2);
528 return false;
529 }
530 }
531 return true;
532 }
533
534 public String toString() {
535 StringBuffer sb = new StringBuffer();
536 sb.append("For " + location + ":\n");
537 Iterator i = relationFacts.entrySet().iterator();
538 while (i.hasNext()) {
539 Map.Entry e = (Map.Entry) i.next();
540 Object key = e.getKey();
541 Object value = e.getValue();
542 sb.append(key);
543 sb.append(" = ");
544 sb.append(value);
545 sb.append('\n');
546 }
547 return sb.toString();
548 }
549 }
550 public class SimplifyVisitor implements OperationVisitor {
551 public Object visit(Join op) {
552 Relation r1 = op.getSrc1();
553 Relation r2 = op.getSrc2();
554 ConstantPropFact f1 = getRepresentativeFact(r1, op);
555 ConstantPropFact f2 = getRepresentativeFact(r2, op);
556 if (f1 == ZERO || f2 == ZERO) {
557 return new Zero(op.getRelationDest());
558 }
559 if (isSame(f1, f2)) return new Copy(op.getRelationDest(), r1);
560 return op;
561 }
562
563 public Object visit(Project op) {
564 Relation r1 = op.getSrc();
565 ConstantPropFact f1 = getRepresentativeFact(r1, op);
566 if (f1 == ZERO) {
567 return new Zero(op.getRelationDest());
568 }
569 return op;
570 }
571
572 public Object visit(BDDProject op) {
573 Relation r1 = op.getSrc();
574 ConstantPropFact f1 = getRepresentativeFact(r1, op);
575 if (f1 == ZERO) {
576 return new Zero(op.getRelationDest());
577 }
578 return op;
579 }
580
581 public Object visit(Rename op) {
582 Relation r1 = op.getSrc();
583 ConstantPropFact f1 = getRepresentativeFact(r1, op);
584 if (f1 == ZERO) {
585 return new Zero(op.getRelationDest());
586 }
587 return op;
588 }
589
590 public Object visit(Union op) {
591 Relation r1 = op.getSrc1();
592 Relation r2 = op.getSrc2();
593 ConstantPropFact f1 = getRepresentativeFact(r1, op);
594 ConstantPropFact f2 = getRepresentativeFact(r2, op);
595 if (f1 == ZERO) {
596 if (f2 == ZERO) {
597 return new Zero(op.getRelationDest());
598 }
599 return new Copy(op.getRelationDest(), r2);
600 } else {
601 if (f2 == ZERO) {
602 return new Copy(op.getRelationDest(), r1);
603 }
604 }
605 if (isSame(f1, f2)) {
606 return new Copy(op.getRelationDest(), r1);
607 }
608 return op;
609 }
610
611 public Object visit(Difference op) {
612 Relation r1 = op.getSrc1();
613 Relation r2 = op.getSrc2();
614 ConstantPropFact f1 = getRepresentativeFact(r1, op);
615 ConstantPropFact f2 = getRepresentativeFact(r2, op);
616 if (f1 == ZERO || isSame(f1, f2)) {
617 return new Zero(op.getRelationDest());
618 }
619 if (f2 == ZERO) {
620 return new Copy(op.getRelationDest(), r1);
621 }
622 return op;
623 }
624
625 public Object visit(JoinConstant op) {
626 Relation r1 = op.getSrc();
627 ConstantPropFact f1 = getRepresentativeFact(r1, op);
628 if (f1 == ZERO) {
629 return new Zero(op.getRelationDest());
630 }
631 return op;
632 }
633
634 public Object visit(GenConstant op) {
635 return op;
636 }
637
638 public Object visit(Free op) {
639 return op;
640 }
641
642 public Object visit(Universe op) {
643 return op;
644 }
645
646 public Object visit(Zero op) {
647 return op;
648 }
649
650 public Object visit(Invert op) {
651 return op;
652 }
653
654 public Object visit(Copy op) {
655 return op;
656 }
657
658 public Object visit(Load op) {
659 return op;
660 }
661
662 public Object visit(Save op) {
663 return op;
664 }
665
666
667
668
669
670
671 public Object visit(ApplyEx op) {
672 Relation r1 = op.getSrc1();
673 Relation r2 = op.getSrc2();
674 ConstantPropFact f1 = getRepresentativeFact(r1, op);
675 ConstantPropFact f2 = getRepresentativeFact(r2, op);
676 if (op.getOp() == BDDFactory.and) {
677 if (f1 == ZERO || f2 == ZERO) {
678 return new Zero(op.getRelationDest());
679 }
680 if (isSame(f1, f2)) {
681
682 return new Project(op.getRelationDest(), r1);
683 }
684 } else if (op.getOp() == BDDFactory.diff) {
685 if (f1 == ZERO) {
686 return new Zero(op.getRelationDest());
687 }
688 if (f2 == ZERO) {
689
690 return new Project(op.getRelationDest(), r1);
691 }
692 } else if (op.getOp() == BDDFactory.or || op.getOp() == BDDFactory.xor) {
693 if (f1 == ZERO) {
694 if (f2 == ZERO) {
695 return new Zero(op.getRelationDest());
696 } else {
697
698 return new Project(op.getRelationDest(), op.getSrc2());
699 }
700 } else if (f2 == ZERO) {
701
702 return new Project(op.getRelationDest(), op.getSrc1());
703 }
704 }
705 return op;
706 }
707
708
709
710
711
712
713 public Object visit(If op) {
714 return op;
715 }
716
717
718
719
720 public Object visit(Nop op){
721 return op;
722 }
723
724
725
726
727
728 public Object visit(Replace op) {
729 return op;
730 }
731 }
732
733 public Operation simplify(Operation op, final ConstantPropFacts facts) {
734 currentFacts = facts;
735 return (Operation) op.visit(new SimplifyVisitor());
736 }
737 }