1
2
3
4 package net.sf.bddbddb.dataflow;
5
6 import java.util.AbstractSet;
7 import java.util.Collection;
8 import java.util.Collections;
9 import java.util.Comparator;
10 import java.util.HashMap;
11 import java.util.HashSet;
12 import java.util.Iterator;
13 import java.util.LinkedList;
14 import java.util.List;
15 import java.util.ListIterator;
16 import java.util.Map;
17 import java.util.Set;
18 import java.util.SortedMap;
19 import java.util.TreeMap;
20 import jwutil.collections.IndexMap;
21 import jwutil.collections.IndexedMap;
22 import jwutil.collections.Pair;
23 import jwutil.math.BitString;
24 import jwutil.math.BitString.BitStringIterator;
25 import jwutil.util.Assert;
26 import net.sf.bddbddb.BDDRelation;
27 import net.sf.bddbddb.IterationList;
28 import net.sf.bddbddb.Relation;
29 import net.sf.bddbddb.Solver;
30 import net.sf.bddbddb.dataflow.DefUse.DefUseFact;
31 import net.sf.bddbddb.dataflow.OperationProblem.OperationFact;
32 import net.sf.bddbddb.dataflow.PartialRedundancy.Anticipated.AnticipatedFact;
33 import net.sf.bddbddb.dataflow.PartialRedundancy.Available.AvailableFact;
34 import net.sf.bddbddb.dataflow.PartialRedundancy.Earliest.EarliestFact;
35 import net.sf.bddbddb.dataflow.PartialRedundancy.Latest.LatestFact;
36 import net.sf.bddbddb.dataflow.Problem.Fact;
37 import net.sf.bddbddb.ir.IR;
38 import net.sf.bddbddb.ir.Operation;
39 import net.sf.bddbddb.ir.OperationVisitor;
40 import net.sf.bddbddb.ir.dynamic.Nop;
41 import net.sf.bddbddb.ir.highlevel.Copy;
42 import net.sf.bddbddb.ir.highlevel.GenConstant;
43 import net.sf.bddbddb.ir.highlevel.Join;
44 import net.sf.bddbddb.ir.highlevel.JoinConstant;
45 import net.sf.bddbddb.ir.highlevel.Load;
46 import net.sf.bddbddb.ir.highlevel.Project;
47 import net.sf.bddbddb.ir.highlevel.Rename;
48 import net.sf.bddbddb.ir.highlevel.Save;
49 import net.sf.bddbddb.ir.highlevel.Universe;
50 import net.sf.bddbddb.ir.highlevel.Zero;
51 import net.sf.bddbddb.ir.lowlevel.Replace;
52
53 /***
54 * Partial redundancy elimination.
55 *
56 * @author mcarbin
57 * @version $Id: PartialRedundancy.java 328 2004-10-16 02:45:30Z joewhaley $
58 */
59 public class PartialRedundancy implements IRPass {
60 public DefUse defUse;
61 public Anticipated anticipated;
62 public Available available;
63 public Earliest earliest;
64 public Used used;
65 public Postponed postponed;
66 public Latest latest;
67 Solver solver;
68 IR ir;
69 ExpressionSet allExpressions;
70 boolean TRACE = false;
71 int[] opToExpression;
72 public PartialRedundancy(IR ir) {
73 this.ir = ir;
74 this.solver = ir.solver;
75
76 anticipated = new Anticipated();
77 available = new Available();
78 earliest = new Earliest();
79 used = new Used();
80 postponed = new Postponed();
81 latest = new Latest();
82 initialize(ir.graph.getIterationList());
83
84 opToExpression = new int[Operation.getNumberOfOperations()];
85 defUse = new DefUse(ir);
86 }
87
88 public void initialize(IterationList list) {
89 for (ListIterator it = list.iterator(); it.hasNext();) {
90 Object o = it.next();
91 if (o instanceof IterationList) {
92 IterationList l = (IterationList) o;
93 if (l.isLoop()) {
94 l.getLoopEdge().addElement(new Nop());
95 IterationList newList = new IterationList(false);
96 newList.addElement(new Nop());
97 it.previous();
98 it.add(newList);
99 it.next();
100 }
101 initialize(l);
102 }
103 }
104 }
105
106 public boolean run() {
107 IterationList list = ir.graph.getIterationList();
108 DataflowSolver solver = new DataflowSolver();
109 solver.solve(defUse,ir.graph.getIterationList());
110
111 getExpressions();
112
113 solver = new DataflowSolver();
114 solver.solve(anticipated, list);
115
116 solver = new DataflowSolver();
117 solver.solve(available, list);
118
119 solver = new DataflowSolver();
120 solver.solve(earliest, list);
121
122 solver = new DataflowSolver();
123 solver.solve(postponed, list);
124
125 solver = new DataflowSolver();
126 solver.solve(latest, list);
127
128 solver = new DataflowSolver();
129 solver.solve(used, list);
130
131 if(TRACE) System.out.println("transform");
132 return transform(list);
133 }
134
135 public void printOperationMap(Map operationMap){
136 StringBuffer sb = new StringBuffer();
137 SortedMap sortedMap = new TreeMap(new Comparator() {
138 public int compare(Object o1, Object o2) {
139 return ((Operation) o1).id - ((Operation) o2).id;
140 }
141 });
142 sortedMap.putAll(operationMap);
143 for (Iterator it = sortedMap.entrySet().iterator(); it.hasNext();) {
144 Map.Entry e = (Map.Entry) it.next();
145 sb.append("@" + e.getKey() + " : " + e.getValue() + '\n');
146 }
147 System.out.println(sb.toString());
148 }
149 Map phis = new HashMap();
150 Map myOpToExpression = new HashMap();
151 IndexedMap expressions = new IndexMap("expressions");
152 public void getExpressions(){
153 getExpressions(ir.graph.getIterationList(), 0);
154
155
156 Set visited = new HashSet();
157 for(Iterator it = myOpToExpression.values().iterator(); it.hasNext(); ){
158 Expression e = (Expression) it.next();
159 for(Iterator jt = e.subExpressions().iterator(); jt.hasNext(); ){
160 Expression e2 = (Expression) jt.next();
161 if(e2.op instanceof Phi && !visited.contains(e2.op)){
162 Phi p = (Phi) e2.op;
163 for(Iterator kt = p.operations.iterator(); kt.hasNext(); ){
164 e2.subExpressions.add(myOpToExpression.get(kt.next()));
165 }
166 visited.add(p);
167 }
168 }
169 }
170
171 mapOpsToExpressions(ir.graph.getIterationList());
172
173 BitString s = new BitString(expressions.size());
174 s.setAll();
175 allExpressions = new ExpressionSet(s);
176 }
177
178 public void mapOpsToExpressions(IterationList list){
179 for(Iterator it = list.iterator(); it.hasNext(); ){
180 Object o = it.next();
181 if(o instanceof Operation){
182 Operation op = (Operation) o;
183 Expression e = (Expression) myOpToExpression.get(op);
184 int index = -1;
185 if(TRACE) System.out.print("Op: " + op + " value: ");
186 if(e != null){
187 e = e.number();
188 opToExpression[op.id] = index = e.number;
189 }
190
191 if(TRACE) System.out.println(Integer.toString(index));
192 }else{
193 mapOpsToExpressions((IterationList) o );
194 }
195 }
196 }
197
198 public boolean considerable(Operation op){
199 if(op instanceof Copy) return false;
200 if(op instanceof Load) return false;
201 if(op instanceof Save) return false;
202 if(op instanceof Universe) return false;
203 if(op instanceof Zero) return false;
204 return true;
205 }
206
207 public void getExpressions(IterationList list, int depth){
208 for(Iterator it = list.iterator(); it.hasNext(); ){
209 Object o = it.next();;
210 if(o instanceof Operation){
211
212 Operation op = (Operation) o;
213 DefUseFact fact = defUse.getIn(op);
214 Relation dest = op.getRelationDest();
215 if(dest != null){
216 List srcs = op.getSrcs();
217 Expression newExpression = new Expression(op, new LinkedList(), depth);
218 myOpToExpression.put(op,newExpression);
219 for(Iterator jt = srcs.iterator(); jt.hasNext(); ){
220 Relation r = (Relation) jt.next();
221 if(r != null){
222 Collection defs = null;
223 Expression subExpression = null;
224 if(( defs = fact.getReachingDefs(r)).size() > 1){
225 if(TRACE) System.out.println(r + " has multiple definitions");
226 Pair p = new Pair(r,fact.getLocation());
227
228 Phi phi = (Phi) phis.get(p);
229 if(phi == null){
230 phi = new Phi(r,defs);
231 phis.put(p, phi);
232 }
233
234 subExpression = new Expression(phi, new LinkedList(),depth);
235 }else{
236 Iterator kt = defs.iterator();
237 if(kt.hasNext()){
238
239 subExpression = (Expression) myOpToExpression.get(kt.next());
240 }
241 }
242 if(subExpression != null)
243 newExpression.subExpressions.add(subExpression);
244
245 }
246 }
247 }
248
249 }else{
250 getExpressions((IterationList)o, depth + 1);
251 }
252 }
253
254 }
255
256
257 public static class Phi extends Operation{
258 Relation dest;
259 Collection operations;
260 public Phi(Relation dest, Collection operations){
261 this.dest = dest;
262 this.operations = operations;
263 }
264
265
266
267 public Object visit(OperationVisitor i) {
268 return null;
269 }
270
271
272
273
274 public String toString() {
275 return dest + " = " + getExpressionString();
276 }
277
278
279
280
281 public Relation getRelationDest() {
282 return dest;
283 }
284
285
286
287
288 public void setRelationDest(Relation r0) {
289 dest = r0;
290 }
291
292
293
294
295 public List getSrcs() {
296 return Collections.EMPTY_LIST;
297 }
298
299
300
301
302 public void replaceSrc(Relation r_old, Relation r_new) {
303
304
305
306 }
307
308
309
310
311 public String getExpressionString() {
312 return "phi" + operations;
313 }
314
315
316
317
318 public Operation copy() {
319 return new Phi(dest,operations);
320 }
321
322 }
323 public class Anticipated extends OperationProblem {
324
325
326
327
328
329 public boolean direction() {
330 return false;
331 }
332
333
334
335
336
337
338 public Fact getBoundary() {
339 return new AnticipatedFact();
340 }
341
342
343
344
345
346
347 public TransferFunction getTransferFunction(Operation o) {
348 return new AnticipatedTF(o);
349 }
350 public class AnticipatedFact extends PreFact {
351 public PreFact create() {
352 return new AnticipatedFact();
353 }
354
355
356
357
358
359
360 public Fact join(Fact that) {
361 AnticipatedFact thatFact = (AnticipatedFact) that;
362 AnticipatedFact result = new AnticipatedFact();
363 result.loc = this.loc;
364 result.expressions.addAll(this.expressions);
365 result.expressions.retainAll(thatFact.expressions);
366 return result;
367 }
368
369
370 }
371 class AnticipatedTF extends TransferFunction {
372 Operation op;
373
374 public AnticipatedTF(Operation op) {
375 this.op = op;
376 }
377
378
379
380
381
382
383 public Fact apply(Fact f) {
384 AnticipatedFact lastFact = (AnticipatedFact) f;
385
386 AnticipatedFact currFact = (lastFact != null) ? (AnticipatedFact) lastFact.copy() : new AnticipatedFact();
387 Expression e = (Expression) expressions.get(opToExpression[op.id]);
388
389
390
391 if(op.getRelationDest() != null)
392 currFact.killExpressions(op);
393 if(e.op == op)
394 currFact.addExpression(e);
395
396
397
398 currFact.op = op;
399 setFact(op, currFact);
400 return currFact;
401 }
402 }
403
404 public String toString() {
405 StringBuffer sb = new StringBuffer();
406 SortedMap sortedMap = new TreeMap(new Comparator() {
407 public int compare(Object o1, Object o2) {
408 return ((Operation) o1).id - ((Operation) o2).id;
409 }
410 });
411 sortedMap.putAll(operationFacts);
412 for (Iterator it = sortedMap.entrySet().iterator(); it.hasNext();) {
413 Map.Entry e = (Map.Entry) it.next();
414 sb.append("@" + e.getKey() + " : " + e.getValue() + '\n');
415 }
416 return sb.toString();
417 }
418 }
419 public class Available extends OperationProblem {
420 public Map availOpIns;
421
422 /***
423 *
424 */
425 public Available() {
426 availOpIns = new HashMap();
427 }
428
429
430
431
432
433
434 public boolean direction() {
435 return true;
436 }
437
438
439
440
441
442
443 public TransferFunction getTransferFunction(Operation o) {
444
445 return new AvailableTF(o);
446 }
447
448
449
450
451
452
453 public Fact getBoundary() {
454 return new AvailableFact();
455 }
456 public class AvailableFact extends PreFact {
457 public PreFact create() {
458 return new AvailableFact();
459 }
460
461
462
463
464
465
466 public Fact join(Fact that) {
467 AvailableFact result = new AvailableFact();
468 AvailableFact thatFact = (AvailableFact) that;
469 result.expressions.addAll(this.expressions);
470 result.expressions.retainAll(thatFact.expressions);
471 result.loc = this.loc;
472 return result;
473 }
474
475 }
476 class AvailableTF extends TransferFunction {
477 Operation op;
478
479 public AvailableTF(Operation op) {
480 this.op = op;
481 }
482
483
484
485
486
487
488 public Fact apply(Fact f) {
489 AvailableFact lastFact = (AvailableFact) f;
490 setIn(op, lastFact);
491 AvailableFact currFact = (lastFact) != null ? (AvailableFact) lastFact.copy() : new AvailableFact();
492
493
494
495 AnticipatedFact antiFact = (AnticipatedFact) anticipated.getFact(op);
496
497 currFact.addExpressions(antiFact.getExpressions());
498 currFact.killExpressions(op);
499
500
501 currFact.op = op;
502 setFact(op, currFact);
503 return currFact;
504 }
505 }
506
507 private void setIn(Operation op, AvailableFact lastFact) {
508 availOpIns.put(op, lastFact);
509 }
510
511 public AvailableFact getIn(Operation op) {
512 return (AvailableFact) availOpIns.get(op);
513 }
514
515 public String toString() {
516 StringBuffer sb = new StringBuffer();
517 SortedMap sortedMap = new TreeMap(new Comparator() {
518 public int compare(Object o1, Object o2) {
519 return ((Operation) o1).id - ((Operation) o2).id;
520 }
521 });
522 sortedMap.putAll(operationFacts);
523 for (Iterator it = sortedMap.entrySet().iterator(); it.hasNext();) {
524 Map.Entry e = (Map.Entry) it.next();
525 sb.append("@" + e.getKey() + " : " + e.getValue() + '\n');
526 }
527 return sb.toString();
528 }
529 }
530 public class Earliest extends OperationProblem {
531 public boolean direction() {
532 return true;
533 }
534
535 public TransferFunction getTransferFunction(Operation o) {
536 return new EarliestTF(o);
537 }
538
539 public Fact getBoundary() {
540 return new EarliestFact();
541 }
542 public class EarliestTF extends TransferFunction {
543 Operation op;
544
545 /***
546 * @param op
547 */
548 public EarliestTF(Operation op) {
549 super();
550 this.op = op;
551 }
552
553 public Fact apply(Fact f) {
554 EarliestFact lastFact = (EarliestFact) f;
555 AnticipatedFact antiFact = (AnticipatedFact) anticipated.getFact(op);
556 AvailableFact availFact = available.getIn(op);
557 EarliestFact currFact = new EarliestFact();
558 currFact.addExpressions(antiFact.getExpressions());
559 if (availFact != null) currFact.removeExpressions(availFact.getExpressions());
560
561
562 currFact.op = op;
563 setFact(op, currFact);
564 return currFact;
565 }
566 }
567 public class EarliestFact extends PreFact {
568 public PreFact create() {
569 return new EarliestFact();
570 }
571
572 public Fact join(Fact that) {
573 return this;
574 }
575 }
576
577 public String toString() {
578 StringBuffer sb = new StringBuffer();
579 SortedMap sortedMap = new TreeMap(new Comparator() {
580 public int compare(Object o1, Object o2) {
581 return ((Operation) o1).id - ((Operation) o2).id;
582 }
583 });
584 sortedMap.putAll(operationFacts);
585 for (Iterator it = sortedMap.entrySet().iterator(); it.hasNext();) {
586 Map.Entry e = (Map.Entry) it.next();
587 sb.append("@" + e.getKey() + " : " + e.getValue() + '\n');
588 }
589 return sb.toString();
590 }
591 }
592 public class Postponed extends OperationProblem {
593 Map opIns;
594
595 /***
596 *
597 */
598 public Postponed() {
599 super();
600 opIns = new HashMap();
601 }
602
603
604
605
606
607
608 public boolean direction() {
609 return true;
610 }
611
612
613
614
615
616
617 public TransferFunction getTransferFunction(Operation o) {
618 return new PostponedTF(o);
619 }
620
621
622
623
624
625
626 public Fact getBoundary() {
627 return new PostponedFact();
628 }
629 class PostponedTF extends TransferFunction {
630 Operation op;
631
632 /***
633 * @param op
634 */
635 public PostponedTF(Operation op) {
636 super();
637 this.op = op;
638 }
639
640
641
642
643
644
645 public Fact apply(Fact f) {
646 PostponedFact lastFact = (PostponedFact) f;
647 setIn(op, lastFact);
648 EarliestFact earlFact = (EarliestFact) earliest.getFact(op);
649 PostponedFact newFact = (PostponedFact) lastFact.copy();
650 newFact.addExpressions(earlFact.expressions);
651 newFact.removeExpression((Expression) expressions.get(opToExpression[op.id]));
652 newFact.op = op;
653 setFact(op, newFact);
654 return newFact;
655 }
656 }
657 public class PostponedFact extends PreFact {
658 public Fact join(Fact that) {
659 PostponedFact thatFact = (PostponedFact) that;
660 PostponedFact result = new PostponedFact();
661 result.expressions.addAll(this.expressions);
662 result.expressions.retainAll(thatFact.expressions);
663 result.loc = this.loc;
664 return result;
665 }
666
667
668
669
670
671
672 public PreFact create() {
673 return new PostponedFact();
674 }
675 }
676
677 public void setIn(Operation op, PostponedFact fact) {
678 opIns.put(op, fact);
679 }
680
681 public PostponedFact getIn(Operation op) {
682 return (PostponedFact) opIns.get(op);
683 }
684
685 public String toString() {
686 StringBuffer sb = new StringBuffer();
687 SortedMap sortedMap = new TreeMap(new Comparator() {
688 public int compare(Object o1, Object o2) {
689 return ((Operation) o1).id - ((Operation) o2).id;
690 }
691 });
692 sortedMap.putAll(operationFacts);
693 for (Iterator it = sortedMap.entrySet().iterator(); it.hasNext();) {
694 Map.Entry e = (Map.Entry) it.next();
695 sb.append("@" + e.getKey() + " : " + e.getValue() + '\n');
696 }
697 return sb.toString();
698 }
699 }
700 public class Latest extends OperationProblem {
701 /***
702 * @author Administrator
703 *
704 * TODO To change the template for this generated type comment go to
705 * Window - Preferences - Java - Code Style - Code Templates
706 */
707 public class LatestTF extends TransferFunction {
708 Operation op;
709
710 /***
711 * @param op
712 */
713 public LatestTF(Operation op) {
714 super();
715 this.op = op;
716 }
717
718
719
720
721
722
723 public Fact apply(Fact f) {
724 LatestFact lastFact = (LatestFact) f;
725 Set right = new ExpressionSet(lastFact.expressions);
726 Set trueRight = new ExpressionSet(allExpressions);
727 trueRight.removeAll(right);
728 trueRight.add(expressions.get(opToExpression[op.id]));
729 Set left = new ExpressionSet(((EarliestFact) earliest.getFact(op)).expressions);
730 left.addAll(postponed.getIn(op).expressions);
731 LatestFact returnLeft = new LatestFact();
732 returnLeft.addExpressions(left);
733 left.retainAll(trueRight);
734 LatestFact thisLatest = new LatestFact();
735 thisLatest.addExpressions(left);
736 thisLatest.op = op;
737 setFact(op, thisLatest);
738 return returnLeft;
739 }
740 }
741
742
743
744
745
746
747 public boolean direction() {
748 return false;
749 }
750
751
752
753
754
755
756 public TransferFunction getTransferFunction(Operation o) {
757 return new LatestTF(o);
758 }
759
760
761
762
763
764
765 public Fact getBoundary() {
766
767 return new LatestFact();
768 }
769 public class LatestFact extends PreFact {
770
771
772
773
774
775 public PreFact create() {
776 return new LatestFact();
777 }
778
779
780
781
782
783
784 public Fact join(Fact that) {
785 LatestFact thatFact = (LatestFact) that;
786 LatestFact result = new LatestFact();
787 result.expressions.addAll(this.expressions);
788 result.expressions.retainAll(thatFact.expressions);
789 result.loc = this.loc;
790 return result;
791 }
792 }
793
794 public String toString() {
795 StringBuffer sb = new StringBuffer();
796 SortedMap sortedMap = new TreeMap(new Comparator() {
797 public int compare(Object o1, Object o2) {
798 return ((Operation) o1).id - ((Operation) o2).id;
799 }
800 });
801 sortedMap.putAll(operationFacts);
802 for (Iterator it = sortedMap.entrySet().iterator(); it.hasNext();) {
803 Map.Entry e = (Map.Entry) it.next();
804 sb.append("@" + e.getKey() + " : " + e.getValue() + '\n');
805 }
806 return sb.toString();
807 }
808 }
809 public class Used extends OperationProblem {
810 public HashMap opOuts;
811
812 /***
813 *
814 */
815 public Used() {
816 opOuts = new HashMap();
817 }
818
819
820
821
822
823
824 public boolean direction() {
825 return false;
826 }
827
828
829
830
831
832
833 public TransferFunction getTransferFunction(Operation o) {
834 return new UsedTF(o);
835 }
836
837
838
839
840
841
842 public Fact getBoundary() {
843 return new UsedFact();
844 }
845 public class UsedFact extends PreFact {
846
847
848
849
850
851 public PreFact create() {
852 return new UsedFact();
853 }
854
855
856
857
858
859
860 public Fact join(Fact that) {
861 UsedFact thatFact = (UsedFact) that;
862 UsedFact result = (UsedFact) create();
863 result.addExpressions(this.expressions);
864 result.addExpressions(thatFact.expressions);
865 result.loc = this.loc;
866 return result;
867 }
868
869
870 }
871 public class UsedTF extends TransferFunction {
872 Operation op;
873
874 /***
875 * @param op
876 */
877 public UsedTF(Operation op) {
878 super();
879 this.op = op;
880 }
881
882
883
884
885
886
887 public Fact apply(Fact f) {
888 UsedFact lastFact = (UsedFact) f;
889 setOut(op, lastFact);
890 UsedFact newFact = new UsedFact();
891 newFact.addExpressions(lastFact.expressions);
892
893 newFact.addExpression((Expression) expressions.get(opToExpression[op.id]));
894 newFact.removeExpressions(((EarliestFact) earliest.getFact(op)).expressions);
895 newFact.op = op;
896 setFact(op, newFact);
897 return newFact;
898 }
899 }
900
901 public void setOut(Operation op, UsedFact fact) {
902 opOuts.put(op, fact);
903 }
904
905 public UsedFact getOut(Operation op) {
906 return (UsedFact) opOuts.get(op);
907 }
908
909 public String toString() {
910 StringBuffer sb = new StringBuffer();
911 SortedMap sortedMap = new TreeMap(new Comparator() {
912 public int compare(Object o1, Object o2) {
913 return ((Operation) o1).id - ((Operation) o2).id;
914 }
915 });
916 sortedMap.putAll(operationFacts);
917 for (Iterator it = sortedMap.entrySet().iterator(); it.hasNext();) {
918 Map.Entry e = (Map.Entry) it.next();
919 sb.append("@" + e.getKey() + " : " + e.getValue() + '\n');
920 }
921 return sb.toString();
922 }
923 }
924 Map exprToOp = new HashMap();
925
926 public boolean transform(IterationList list) {
927 boolean changed = false;
928 if (list.isLoop()) {
929 boolean b = transform(list.getLoopEdge());
930 if (!changed) changed = b;
931 }
932 for (ListIterator it = list.iterator(); it.hasNext();) {
933 Object o = it.next();
934 if (o instanceof Operation) {
935
936
937
938
939
940
941
942
943
944 Set latest = ((LatestFact) PartialRedundancy.this.latest.getFact((Operation) o)).expressions;
945 latest.retainAll(used.getOut(((Operation) o)).expressions);
946
947 it.previous();
948 for (Iterator it2 = latest.iterator(); it2.hasNext();) {
949 Expression e = (Expression) it2.next();
950 Operation relOp = (Operation) exprToOp.get(e);
951 if (relOp == null) {
952 BDDRelation oldR = (BDDRelation) e.op.getRelationDest();
953 if (oldR != null) {
954 BDDRelation r = (BDDRelation) solver.createRelation("pre_" + e.toString(), oldR.getAttributes());
955 r.initialize();
956 r.setDomainAssignment(oldR.getBDDDomains());
957 relOp = e.op.copy();
958 relOp.setRelationDest(r);
959 exprToOp.put(e, relOp);
960 }
961 }
962 if (TRACE) System.out.println("Adding " + relOp + " before " + o);
963 it.add(relOp);
964 changed = true;
965 }
966 it.next();
967 Set notLatest = new ExpressionSet(allExpressions);
968 notLatest.removeAll(((LatestFact) PartialRedundancy.this.latest.getFact((Operation) o)).expressions);
969 notLatest.addAll(used.getOut((Operation) o).expressions);
970 if (notLatest.contains(expressions.get(opToExpression[((Operation) o).id]))) {
971 Expression e = (Expression) expressions.get(opToExpression[((Operation) o).id]);
972 Operation op = (Operation) exprToOp.get(e);
973 if (e != null && op != null) {
974 Copy newOp = new Copy(((Operation) o).getRelationDest(), op.getRelationDest());
975 if (TRACE) System.out.println("Replacing " + o + " with " + newOp);
976 it.set(newOp);
977 changed = true;
978 }
979 }
980 if (o instanceof Nop) it.remove();
981 } else {
982 IterationList l = (IterationList) o;
983 boolean b = transform(l);
984 if (!changed) changed = b;
985
986 if (l.isEmpty()) it.remove();
987 }
988 }
989 return changed;
990 }
991 abstract class PreFact implements OperationFact {
992 Operation op;
993 IterationList loc;
994 public ExpressionSet expressions;
995 public PreFact() {
996 expressions = new ExpressionSet();
997 }
998
999 public boolean containsExpression(Expression e) {
1000 return expressions.contains(e);
1001 }
1002
1003 public boolean addExpression(Expression e) {
1004 if (e != null && considerable(e.op) )
1005 return expressions.add(e);
1006 return false;
1007 }
1008
1009 public boolean addExpressions(Set e) {
1010 return expressions.addAll(e);
1011 }
1012
1013 public boolean removeExpression(Expression e) {
1014 return expressions.remove(e);
1015 }
1016
1017 public boolean removeExpressions(Set e) {
1018 return expressions.removeAll(e);
1019 }
1020
1021 public Set getExpressions() {
1022 return expressions;
1023 }
1024
1025
1026
1027
1028
1029
1030 public Fact copy(IterationList list) {
1031 PreFact result = this.copy();
1032 result.loc = list;
1033 return result;
1034 }
1035
1036
1037
1038
1039
1040
1041 public void setLocation(IterationList list) {
1042 loc = list;
1043 }
1044
1045 public void killExpressions(Operation op) {
1046 for (Iterator it = expressions.iterator(); it.hasNext();) {
1047 Expression e = (Expression) it.next();
1048 if (e.killedBy(op)) it.remove();
1049 }
1050 }
1051
1052
1053
1054
1055
1056 public IterationList getLocation() {
1057 return loc;
1058 }
1059
1060 public String toString() {
1061 return expressions.toString();
1062 }
1063
1064
1065
1066
1067 public boolean equals(Object o) {
1068 return expressions.equals(((PreFact) o).expressions);
1069 }
1070
1071
1072
1073
1074 public int hashCode() {
1075 return this.expressions.hashCode();
1076 }
1077
1078 public abstract PreFact create();
1079
1080 public PreFact copy() {
1081 PreFact result = create();
1082 result.expressions.addAll(this.expressions);
1083 result.loc = loc;
1084 return result;
1085 }
1086
1087
1088
1089
1090
1091 public Operation getOperation() {
1092 return op;
1093 }
1094 }
1095
1096 class ExpressionSet extends AbstractSet{
1097 BitString s;
1098
1099 public ExpressionSet(){
1100 this(PartialRedundancy.this.expressions.size());
1101 }
1102
1103 public ExpressionSet(int numExpressions){
1104 this(new BitString(numExpressions));
1105 }
1106
1107 public ExpressionSet(BitString s){
1108 this.s = s;
1109 }
1110
1111 public ExpressionSet(ExpressionSet other){
1112 this((BitString) other.s.clone());
1113 }
1114
1115
1116
1117
1118 public int size() {
1119 return s.numberOfOnes();
1120 }
1121
1122 public boolean contains(Object o){
1123 if(o instanceof Expression){
1124 return s.get(expressions.get(o));
1125 }
1126 return false;
1127 }
1128
1129 public boolean containsAll(Collection c){
1130 if(c instanceof ExpressionSet){
1131 ExpressionSet those = (ExpressionSet) c;
1132 return s.contains(those.s);
1133 }
1134 return false;
1135 }
1136 public boolean add(Object o){
1137 boolean changed = false;
1138 if(o instanceof Expression){
1139 int index = expressions.get(o);
1140 changed = !s.get(index);
1141 if(changed) s.set(index);
1142 }
1143 return changed;
1144 }
1145
1146 public boolean addAll(Collection c){
1147 if(c instanceof ExpressionSet){
1148 ExpressionSet those = (ExpressionSet) c;
1149 return s.or(those.s);
1150 }
1151 return false;
1152 }
1153
1154 public boolean remove(Object o){
1155 boolean changed = false;
1156 if(o instanceof Expression){
1157 int index = expressions.get(o);
1158 changed = s.get(index);
1159 if(changed) s.clear(index);
1160 }
1161 return changed;
1162 }
1163
1164 public boolean removeAll(Collection c){
1165 if(c instanceof ExpressionSet){
1166 ExpressionSet those = (ExpressionSet) c;
1167 return s.minus(those.s);
1168 }
1169
1170 return false;
1171 }
1172
1173
1174
1175
1176 public Iterator iterator() {
1177 return new ExpressionIterator();
1178 }
1179
1180 class ExpressionIterator implements Iterator{
1181
1182 BitStringIterator it;
1183 int lastIndex;
1184 public ExpressionIterator(){
1185 lastIndex = -1;
1186 it = s.iterator();
1187 }
1188
1189
1190
1191 public void remove() {
1192 if(lastIndex != -1)
1193 s.clear(lastIndex);
1194
1195 }
1196
1197
1198
1199
1200 public boolean hasNext() {
1201 return it.hasNext();
1202 }
1203
1204
1205
1206
1207 public Object next() {
1208 return expressions.get(lastIndex = it.nextIndex());
1209 }
1210
1211 }
1212 }
1213
1214 static class ExpressionWrapper {
1215 Expression e;
1216
1217 /***
1218 * @param e
1219 */
1220 public ExpressionWrapper(Expression e) {
1221 super();
1222 this.e = e;
1223 }
1224
1225
1226
1227 public boolean equals(Object o){
1228 ExpressionWrapper that = (ExpressionWrapper) o;
1229 return this.e == that.e;
1230 }
1231
1232
1233
1234
1235 public int hashCode() {
1236 return System.identityHashCode(e);
1237 }
1238
1239 public String toString(){ return e.toString(); }
1240 }
1241
1242 class Expression {
1243 int number = -1;
1244 Operation op;
1245 int depth = -1;
1246 public List subExpressions;
1247 public Collection reachingDefs;
1248 public Expression(Operation op, List subExpressions, int depth) {
1249 this.op = op;
1250 this.subExpressions = subExpressions;
1251 this.depth = depth;
1252 }
1253
1254 public List getSrcs() {
1255 return op.getSrcs();
1256 }
1257
1258 public List subExpressions(){
1259 return subExpressions;
1260 }
1261 public Class getType() {
1262 return op.getClass();
1263 }
1264
1265
1266
1267
1268 public boolean equals(Object obj) {
1269 Expression that = (Expression) obj;
1270 if(this.number != -1 && that.number != -1)
1271 return this.number == that.number;
1272
1273 return equals(that, new HashSet());
1274 }
1275
1276 private boolean equals(Expression that, Collection visited){
1277
1278
1279 ExpressionWrapper thisWrap = new ExpressionWrapper(this);
1280 ExpressionWrapper thatWrap = new ExpressionWrapper(that);
1281 if(visited.contains(thisWrap) && visited.contains(thatWrap)) return true;
1282 if(this.depth != that.depth) return false;
1283
1284 visited.add(thisWrap);
1285 visited.add(thatWrap);
1286 if (this == that) return true;
1287
1288
1289 if(!this.op.getClass().equals(that.op.getClass())) return false;
1290
1291 if(!passesOpSpecificChecks(that)) return false;
1292
1293 if(this.subExpressions.size() != that.subExpressions.size()) return false;
1294 for(int i = 0; i < this.subExpressions.size(); i++){
1295 Expression e1 = (Expression) this.subExpressions.get(i);
1296 Expression e2 = (Expression) that.subExpressions.get(i);
1297 if(!e1.equals(e2,visited)) return false;
1298 }
1299 visited.remove(thisWrap);
1300 visited.remove(thatWrap);
1301 return true;
1302 }
1303
1304 boolean passesOpSpecificChecks(Expression that){
1305 if(this.op instanceof Load){
1306 Load thisL = (Load) this.op;
1307 Load thatL = (Load) that.op;
1308 if(!thisL.getRelationDest().equals(thatL.getRelationDest())) return false;
1309
1310 }else if(this.op instanceof Project){
1311 Project thisP = (Project) this.op;
1312 Project thatP = (Project) that.op;
1313 if(!thisP.getAttributes().equals(thatP.getAttributes())) return false;
1314 }else if(this.op instanceof Rename){
1315 Rename thisR = (Rename) this.op;
1316 Rename thatR = (Rename) that.op;
1317 if(!thisR.getRenameMap().equals(thatR.getRenameMap())) return false;
1318 }else if(this.op instanceof Join){
1319 Join thisJ = (Join) this.op;
1320 Join thatJ = (Join) that.op;
1321 if(!thisJ.getAttributes().equals(thatJ.getAttributes())) return false;
1322 }else if(this.op instanceof GenConstant){
1323 GenConstant thisG = (GenConstant) this.op;
1324 GenConstant thatG = (GenConstant) that.op;
1325 if(!thisG.getAttribute().equals(thatG.getAttribute())
1326 || thisG.getValue() != thatG.getValue())
1327 return false;
1328 }else if(this.op instanceof JoinConstant){
1329 JoinConstant thisG = (JoinConstant) this.op;
1330 JoinConstant thatG = (JoinConstant) that.op;
1331 if(!thisG.getAttribute().equals(thatG.getAttribute())
1332 || thisG.getValue() != thatG.getValue())
1333 return false;
1334 }else if(this.op instanceof Replace){
1335 Replace thisR = (Replace) this.op;
1336 Replace thatR = (Replace) that.op;
1337 if(!thisR.getPairing().equals(thatR.getPairing())) return false;
1338 }
1339 return true;
1340 }
1341
1342 public Expression number(){
1343 if(this.number != -1) return this;
1344 int initSize = expressions.size();
1345 int number = expressions.get(this);
1346 if(expressions.size() - initSize > 0){
1347
1348 this.number = number;
1349 List newSubs = new LinkedList();
1350 for(Iterator it = subExpressions.iterator(); it.hasNext(); ){
1351 Expression e = (Expression) it.next();
1352 newSubs.add(e.number());
1353 }
1354 subExpressions = newSubs;
1355 }
1356
1357 return (Expression) expressions.get(number);
1358 }
1359 public boolean killedBy(Operation op) {
1360
1361
1362
1363 Expression killE = (Expression) expressions.get(opToExpression[op.id]);
1364 for(Iterator it = subExpressions.iterator(); it.hasNext(); ){
1365 Expression subE = (Expression) it.next();
1366 if(subE.op instanceof Phi){
1367 Phi phi = (Phi) subE.op;
1368 if(phi.operations.contains(op)) return true;
1369
1370 }else{
1371 if(subE.equals(killE)) return true;
1372 }
1373 }
1374 return false;
1375 }
1376
1377 public boolean uses(Expression e, Collection visited){
1378 Assert._assert(e != null, "expression is null");
1379 ExpressionWrapper thisWrap = new ExpressionWrapper(this);
1380 if(visited.contains(this)) return false;
1381 visited.add(this);
1382 if(subExpressions.contains(e)) return true;
1383
1384 for(Iterator it = subExpressions.iterator(); it.hasNext(); ){
1385
1386 if(((Expression) it.next()).uses(e,visited)) return true;
1387 }
1388 return false;
1389
1390 }
1391 public String toString() {
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409 return op.getExpressionString();
1410 }
1411 public int hashCode() {
1412 return 1;
1413 }
1414
1415 }
1416 }