CopyPropagator


1   package polyglot.visit;
2   
3   import polyglot.ast.*;
4   import polyglot.frontend.Job;
5   import polyglot.main.Report;
6   import polyglot.types.*;
7   import polyglot.util.InternalCompilerError;
8   
9   import java.util.*;
10  
11  /**
12   * Visitor which performs copy propagation.
13   */
14  public class CopyPropagator extends DataFlow {
15      public CopyPropagator(Job job, TypeSystem ts, NodeFactory nf) {
16      super(job, ts, nf,
17            true /* forward analysis */,
18            true /* perform dataflow on entry to CodeDecls */);
19      }
20  
21      protected static class DataFlowItem extends Item {
22      // Map of LocalInstance -> CopyInfo.  The CopyInfo nodes form a forest
23      // to represent copy information.
24      private Map map;  
25  
26      /**
27       * Constructor for creating an empty set.
28       */
29      protected DataFlowItem() {
30          this.map = new HashMap();
31      }
32  
33      /**
34       * Deep copy constructor.
35       */
36      protected DataFlowItem(DataFlowItem dfi) {
37          map = new HashMap(dfi.map.size());
38          for (Iterator it = dfi.map.entrySet().iterator(); it.hasNext(); ) {
39          Map.Entry e = (Map.Entry)it.next();
40  
41          LocalInstance li = (LocalInstance)e.getKey();
42          CopyInfo ci = (CopyInfo)e.getValue();
43          if (ci.from != null) add(ci.from.li, li);
44          }
45      }
46  
47      protected static class CopyInfo {
48          final LocalInstance li; // Local instance this node pertains to.
49          CopyInfo from;    // In edge.
50          Set to;       // Out edges.
51          CopyInfo root;    // Root CopyInfo node for this tree.
52  
53          protected CopyInfo(LocalInstance li) {
54          if (li == null) {
55              throw new InternalCompilerError("Null local instance "
56              + "encountered during copy propagation.");
57          }
58  
59          this.li = li;
60          this.from = null;
61          this.to = new HashSet();
62          this.root = this;
63          }
64  
65          protected void setRoot(CopyInfo root) {
66          List worklist = new ArrayList();
67          worklist.add(this);
68          while (worklist.size() > 0) {
69              CopyInfo ci = (CopyInfo)worklist.remove(worklist.size()-1);
70              worklist.addAll(ci.to);
71              ci.root = root;
72          }
73          }
74  
75          public boolean equals(Object   o) {
76          if (!(o instanceof CopyInfo)) return false;
77          CopyInfo ci = (CopyInfo)o;
78  
79          // Assume both are in consistent data structures, so only check
80          // up pointers.  Also check root pointers because we can.
81          return li == ci.li
82              && (from == null ? ci.from == null
83              : (ci.from != null && from.li == ci.from.li))
84              && root.li == ci.root.li;
85          }
86  
87          public int hashCode() {
88          return li.hashCode()
89              + 31*(from == null ? 0 : from.li.hashCode()
90              + 31*root.li.hashCode());
91          }
92      }
93  
94      protected void add(LocalInstance from, LocalInstance to) {
95          // Get the 'to' node.
96          boolean newTo = !map.containsKey(to);
97          CopyInfo ciTo;
98          if (newTo) {
99          ciTo = new CopyInfo(to);
100         map.put(to, ciTo);
101         } else {
102         ciTo = (CopyInfo)map.get(to);
103         }
104 
105         // Get the 'from' node.
106         CopyInfo ciFrom;
107         if (map.containsKey(from)) {
108         ciFrom = (CopyInfo)map.get(from);
109         } else {
110         ciFrom = new CopyInfo(from);
111         map.put(from, ciFrom);
112         ciFrom.root = ciFrom;
113         }
114 
115         // Make sure ciTo doesn't already have a 'from' node.
116         if (ciTo.from != null) {
117         throw new InternalCompilerError("Error while copying dataflow "
118             + "item during copy propagation.");
119         }
120 
121         // Link up.
122         ciFrom.to.add(ciTo);
123         ciTo.from = ciFrom;
124 
125         // Consistency fix-up.
126         if (newTo) {
127         ciTo.root = ciFrom.root;
128         } else {
129         ciTo.setRoot(ciFrom.root);
130         }
131     }
132 
133     protected void intersect(DataFlowItem dfi) {
134         boolean modified = false;
135 
136         for (Iterator it = map.entrySet().iterator(); it.hasNext(); ) {
137         Map.Entry e = (Map.Entry)it.next();
138         LocalInstance li = (LocalInstance)e.getKey();
139         CopyInfo ci = (CopyInfo)e.getValue();
140 
141         if (!dfi.map.containsKey(li)) {
142             modified = true;
143 
144             it.remove();
145 
146             // Surgery.  Bypass and remove the node.  We'll fix
147             // consistency later.
148             if (ci.from != null) ci.from.to.remove(ci);
149             for (Iterator i = ci.to.iterator(); i.hasNext(); ) {
150             CopyInfo toCI = (CopyInfo)i.next();
151             toCI.from = null;
152             }
153 
154             continue;
155         }
156 
157         if (ci.from == null) continue;
158 
159         // Other DFI contains this key.
160         // Make sure that ci and ci.from are also in the same tree in
161         // the other DFI.  If not, break the link in the intersection
162         // result.
163         CopyInfo otherCI = (CopyInfo)dfi.map.get(li);
164         CopyInfo otherCIfrom = (CopyInfo)dfi.map.get(ci.from.li);
165 
166         if (otherCIfrom == null || otherCI.root != otherCIfrom.root) {
167             modified = true;
168 
169             // Remove the uplink.
170             ci.from.to.remove(ci);
171             ci.from = null;
172         }
173         }
174 
175         if (!modified) return;
176 
177         // Fix consistency.
178         for (Iterator it = map.entrySet().iterator(); it.hasNext(); ) {
179         Map.Entry e = (Map.Entry)it.next();
180         CopyInfo ci = (CopyInfo)e.getValue();
181 
182         // Only work on roots.
183         if (ci.from != null) continue;
184 
185         // Cut out singleton nodes.
186         if (ci.to.isEmpty()) {
187             it.remove();
188             continue;
189         }
190 
191         // Fix root.
192         ci.setRoot(ci);
193         }
194     }
195 
196     public void kill(LocalInstance var) {
197         if (!map.containsKey(var)) return;
198 
199         CopyInfo ci = (CopyInfo)map.get(var);
200         map.remove(var);
201 
202         // Splice out 'ci' and fix consistency.
203         if (ci.from != null) ci.from.to.remove(ci);
204         for (Iterator it = ci.to.iterator(); it.hasNext(); ) {
205         CopyInfo toCI = (CopyInfo)it.next();
206         toCI.from = ci.from;
207         if (ci.from == null) {
208             toCI.setRoot(toCI);
209         } else {
210             ci.from.to.add(toCI);
211         }
212         }
213     }
214 
215     public LocalInstance getRoot(LocalInstance var) {
216         if (!map.containsKey(var)) return null;
217         return ((CopyInfo)map.get(var)).root.li;
218     }
219 
220     private void die() {
221         throw new InternalCompilerError("Copy propagation dataflow item "
222         + "consistency error.");
223     }
224 
225     private void consistencyCheck() {
226         for (Iterator it = map.entrySet().iterator(); it.hasNext(); ) {
227         Map.Entry e = (Map.Entry)it.next();
228 
229         LocalInstance li = (LocalInstance)e.getKey();
230         CopyInfo ci = (CopyInfo)e.getValue();
231 
232         if (li != ci.li) die();
233         if (!map.containsKey(ci.root.li)) die();
234         if (map.get(ci.root.li) != ci.root) die();
235 
236         if (ci.from == null) {
237             if (ci.root != ci) die();
238         } else {
239             if (!map.containsKey(ci.from.li)) die();
240             if (map.get(ci.from.li) != ci.from) die();
241             if (ci.from.root != ci.root) die();
242             if (!ci.from.to.contains(ci)) die();
243         }
244 
245         for (Iterator i = ci.to.iterator(); i.hasNext(); ) {
246             CopyInfo toCI = (CopyInfo)i.next();
247             if (!map.containsKey(toCI.li)) die();
248             if (map.get(toCI.li) != toCI) die();
249             if (toCI.root != ci.root) die();
250             if (toCI.from != ci) die();
251         }
252         }
253     }
254 
255     public int hashCode() {
256         int result = 0;
257         for (Iterator it = map.entrySet().iterator(); it.hasNext(); ) {
258         Map.Entry e = (Map.Entry)it.next();
259         result = 31*result + e.getKey().hashCode();
260         result = 31*result + e.getValue().hashCode();
261         }
262 
263         return result;
264     }
265 
266     public boolean equals(Object   o) {
267         if (!(o instanceof DataFlowItem)) return false;
268 
269         DataFlowItem dfi = (DataFlowItem)o;
270         return map.equals(dfi.map);
271     }
272 
273     public String   toString() {
274         String   result = "";
275         boolean first = true;
276 
277         for (Iterator it = map.values().iterator(); it.hasNext(); ) {
278         CopyInfo ci = (CopyInfo)it.next();
279         if (ci.from != null) {
280             if (!first) result += ", ";
281             if (ci.root != ci.from) result += ci.root.li + " ->* ";
282             result += ci.from.li + " -> " + ci.li;
283             first = false;
284         }
285         }
286         return "[" + result + "]";
287     }
288     }
289 
290     public Item createInitialItem(FlowGraph graph, Term node) {
291     return new DataFlowItem();
292     }
293 
294     public Item confluence(List inItems, Term node, FlowGraph graph) {
295     DataFlowItem result = null;
296     for (Iterator it = inItems.iterator(); it.hasNext(); ) {
297         DataFlowItem inItem = (DataFlowItem)it.next();
298         if (result == null) {
299         result = new DataFlowItem(inItem);
300         } else {
301         result.intersect(inItem);
302         }
303     }
304 
305     return result;
306     }
307 
308     private void killDecl(DataFlowItem dfi, Stmt stmt) {
309     if (stmt instanceof LocalDecl) {
310         dfi.kill(((LocalDecl)stmt).localInstance());
311     }
312     }
313 
314     protected DataFlowItem flow(Item in, FlowGraph graph, Term t) {
315     DataFlowItem result = new DataFlowItem((DataFlowItem)in);
316 
317     if (t instanceof Assign) {
318         Assign n = (Assign)t;
319         Assign.Operator op = n.operator();
320         Expr left = n.left();
321         Expr right = n.right();
322 
323         if (left instanceof Local) {
324         LocalInstance to = ((Local)left).localInstance();
325         result.kill(to);
326 
327         if (right instanceof Local && op == Assign.ASSIGN) {
328             LocalInstance from = ((Local)right).localInstance();
329             result.add(from, to);
330         }
331         }
332     } else if (t instanceof Unary) {
333         Unary n = (Unary)t;
334         Unary.Operator op = n.operator();
335         Expr expr = n.expr();
336 
337         if (expr instanceof Local && (op == Unary.POST_INC
338         || op == Unary.POST_DEC || op == Unary.PRE_INC
339         || op == Unary.PRE_DEC)) {
340 
341         result.kill(((Local)expr).localInstance());
342         }
343     } else if (t instanceof LocalDecl) {
344         LocalDecl n = (LocalDecl)t;
345 
346         LocalInstance to = n.localInstance();
347         result.kill(to);
348 
349         // It's a copy if we're initializing a non-final local declaration
350         // with a value from a local variable.  We only care about
351         // non-final local declarations because final locals have special
352         // use in local classes.
353         if (!n.flags().isFinal() && n.init() instanceof Local) {
354         LocalInstance from = ((Local)n.init()).localInstance();
355         result.add(from, to);
356         }
357     } else if (t instanceof Block) {
358         // Kill locals that were declared in the block.
359         Block n = (Block)t;
360         for (Iterator it = n.statements().iterator(); it.hasNext(); ) {
361         killDecl(result, (Stmt)it.next());
362         }
363     } else if (t instanceof Loop) {
364         if (t instanceof For) {
365         // Kill locals that were declared in the initializers.
366         For n = (For)t;
367         for (Iterator it = n.inits().iterator(); it.hasNext(); ) {
368             killDecl(result, (Stmt)it.next());
369         }
370         }
371 
372         // Kill locals that were declared in the body.
373         killDecl(result, ((Loop)t).body());
374     } else if (t instanceof Catch) {
375         // Kill catch's formal.
376         result.kill(((Catch)t).formal().localInstance());
377     } else if (t instanceof If) {
378         // Kill locals declared in consequent and alternative.
379         If n = (If)t;
380         killDecl(result, n.consequent());
381         killDecl(result, n.alternative());
382     }
383 
384     return result;
385     }
386 
387     public Map flow(Item in, FlowGraph graph, Term t, Set succEdgeKeys) {
388     return itemToMap(flow(in, graph, t), succEdgeKeys);
389     }
390 
391     public void post(FlowGraph graph, Term root) throws SemanticException {
392     // No need to do any checking.
393     if (Report.should_report(Report.cfg, 2)) {
394         dumpFlowGraph(graph, root);
395     }
396     }
397 
398     public void check(FlowGraph graph, Term n, Item inItem, Map outItems)
399     throws SemanticException {
400 
401     throw new InternalCompilerError("CopyPropagator.check should never be "
402         + "called.");
403     }
404 
405     public Node leaveCall(Node old, Node n, NodeVisitor v)
406     throws SemanticException {
407 
408     if (n instanceof Local) {
409         FlowGraph g = currentFlowGraph();
410         if (g == null) return n;
411 
412         Local l = (Local)n;
413         Collection peers = g.peers(l);
414         if (peers == null || peers.isEmpty()) return n;
415 
416         List items = new ArrayList();
417         for (Iterator it = peers.iterator(); it.hasNext(); ) {
418         FlowGraph.Peer p = (FlowGraph.Peer)it.next();
419         if (p.inItem() != null) items.add(p.inItem());
420         }
421 
422         DataFlowItem in = (DataFlowItem)confluence(items, l, g);
423         if (in == null) return n;
424 
425         LocalInstance root = in.getRoot(l.localInstance());
426         if (root == null) return n;
427         return l.name(root.name()).localInstance(root);
428     }
429 
430     if (n instanceof Unary) {
431         return old;
432     }
433 
434     if (n instanceof Assign) {
435         Assign oldAssign = (Assign)old;
436         Assign newAssign = (Assign)n;
437         return newAssign.left(oldAssign.left());
438     }
439 
440     return n;
441     }
442 }
443 
444
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags