View Javadoc

1   package net.sf.bddbddb.dataflow;
2   
3   import java.util.HashMap;
4   import java.util.Iterator;
5   import java.util.List;
6   import java.util.ListIterator;
7   import java.util.Map;
8   import jwutil.math.BitString;
9   import jwutil.math.BitString.BitStringIterator;
10  import net.sf.bddbddb.IterationList;
11  import net.sf.bddbddb.Relation;
12  import net.sf.bddbddb.ir.IR;
13  import net.sf.bddbddb.ir.Operation;
14  import net.sf.bddbddb.ir.highlevel.Free;
15  
16  /***
17   * @author Administrator
18   */
19  public class Liveness extends OperationProblem implements IRPass {
20      public IR ir;
21      int numRelations;
22      boolean TRACE = false;
23      Map opOuts;
24  
25      public Liveness(IR ir) {
26          this.ir = ir;
27          this.numRelations = ir.getNumberOfRelations();
28          opOuts = new HashMap();
29      }
30  
31      /*
32       * (non-Javadoc)
33       * 
34       * @see net.sf.bddbddb.dataflow.IRPass#run()
35       */
36      public boolean run() {
37          System.out.print("Running Liveness...");
38          long time = System.currentTimeMillis();
39          IterationList list = ir.graph.getIterationList();
40          DataflowSolver solver = new DataflowSolver();
41          solver.solve(this, list);
42          boolean result = transform(list);
43          System.out.println(((System.currentTimeMillis()-time)/1000.)+"s");
44          return result;
45      }
46  
47      boolean transform(IterationList list) {
48          boolean changed = false;
49          for (ListIterator it = list.iterator(); it.hasNext();) {
50              Object o = it.next();
51              if (o instanceof Operation) {
52                  Operation op = (Operation) o;
53                  LivenessFact fact = (LivenessFact) getOut(op);
54                  if (TRACE) System.out.println("Live: " + fact);
55                  for (Iterator it2 = op.getSrcs().iterator(); it2.hasNext();) {
56                      Relation r = (Relation) it2.next();
57                      if (!fact.isAlive(r)) {
58                          Free free = new Free(r);
59                          if (TRACE) System.out.println("Adding a free for " + r);
60                          it.add(free);
61                          changed = true;
62                      }
63                  }
64              } else {
65                  IterationList p = (IterationList) o;
66                  boolean b = transform(p);
67                  if (!changed) changed = b;
68              }
69          }
70          return changed;
71      }
72  
73      public boolean direction() {
74          return false;
75      }
76  
77      public LivenessFact getOut(Operation op) {
78          return (LivenessFact) opOuts.get(op);
79      }
80  
81      public void setOut(Operation op, Fact fact) {
82          opOuts.put(op, fact);
83      }
84  
85      public Fact getBoundary() {
86          return new LivenessFact(numRelations);
87      }
88      public class LivenessFact extends UnionBitVectorFact implements OperationFact {
89          Operation op;
90  
91          public LivenessFact(BitString fact) {
92              super(fact);
93          }
94  
95          public LivenessFact(int size) {
96              super(size);
97          }
98  
99          public UnionBitVectorFact create(BitString bs) {
100             return new LivenessFact(bs);
101         }
102 
103         public Fact join(Fact that) {
104             if (TRACE) System.out.println("Joining " + this + " and " + that);
105             Fact result = super.join(that);
106             if (TRACE) System.out.println("Result = " + result);
107             return result;
108         }
109 
110         /*
111          * (non-Javadoc)
112          * 
113          * @see java.lang.Object#toString()
114          */
115         public String toString() {
116             StringBuffer sb = new StringBuffer();
117             sb.append(op);
118             sb.append(" : ");
119             for (BitStringIterator i = fact.iterator(); i.hasNext();) {
120                 sb.append(ir.getRelation(i.nextIndex()));
121                 sb.append(" ");
122             }
123             return sb.toString();
124         }
125 
126         public boolean isAlive(Relation r) {
127             return fact.get(r.id);
128         }
129 
130         /*
131          * (non-Javadoc)
132          * 
133          * @see net.sf.bddbddb.dataflow.OperationProblem.OperationFact#getOperation()
134          */
135         public Operation getOperation() {
136             return op;
137         }
138 
139     }
140 
141     public TransferFunction getTransferFunction(Operation op) {
142         return new LivenessTF(op);
143     }
144     public class LivenessTF extends OperationTransferFunction {
145         Operation op;
146 
147         public LivenessTF(Operation op) {
148             this.op = op;
149         }
150 
151         public Fact apply(Fact f) {
152             //super.apply(f);
153             LivenessFact oldFact = (LivenessFact) f;
154             setOut(op, f);
155             BitString bs = (BitString) oldFact.fact.clone();
156             //kill
157             Relation r = op.getRelationDest();
158             if (r != null) bs.clear(r.id);
159             //gen
160             List srcs = op.getSrcs();
161             for (Iterator it = srcs.iterator(); it.hasNext();) {
162                 Object o = it.next();
163                 if (o instanceof Relation) bs.set(((Relation) o).id);
164             }
165             LivenessFact newFact = (LivenessFact) oldFact.create(bs);
166             newFact.op = op;
167             setFact(op, newFact);
168             return newFact;
169         }
170     }
171 }