View Javadoc

1   // Dataflow.java, created Tue Jun  4 15:58:53 2002 by joewhaley
2   // Copyright (C) 2001-3 mcmartin
3   // Licensed under the terms of the GNU LGPL; see COPYING for details.
4   package joeq.Compiler.Quad;
5   import java.util.HashMap;
6   import java.util.Iterator;
7   import joeq.Class.jq_Method;
8   import joeq.Class.jq_MethodVisitor;
9   
10  /***
11   * @author Michael Martin <mcmartin@stanford.edu>
12   * @version $Id: DataflowFramework.java 1931 2004-09-22 22:17:47Z joewhaley $
13   */
14  public class DataflowFramework {
15      private static final boolean TRACE_DATAFLOW = true;
16      private static final boolean TRACE_DATAFLOW_QUADS = false;
17      private static final java.io.PrintStream DF_OUT = System.err;
18  
19      interface FactCollection {
20          Fact getPre(Quad q);
21          Fact getPost(Quad q);
22          Fact getInitial();
23          Fact getFinal();
24          void setPre(Quad q, Fact dff);
25          void setPost(Quad q, Fact dff);
26          void setInitial(Fact dff);
27          void setFinal(Fact dff);
28      }
29  
30      interface Fact {
31          Fact meetWith(Fact f);
32          Fact deepCopy();
33      }
34  
35      interface Transfer {
36          void registerFactCollection(FactCollection fc);
37          void preprocess(ControlFlowGraph cfg);
38          boolean transfer(Quad q);
39          void postprocess(ControlFlowGraph cfg);
40      }
41  
42      static class DataflowArray implements FactCollection {
43          private Fact[] _pre, _post;
44          private Fact _initial, _final;
45  
46          public DataflowArray(int size) {
47              _pre = new Fact[size];
48              _post = new Fact[size];
49              _initial = null;
50              _final = null;
51          }
52          
53          public Fact getPre(Quad q) { return _pre[q.getID()]; }
54          public Fact getPost(Quad q) { return _post[q.getID()]; }
55          public Fact getInitial() { return _initial; }
56          public Fact getFinal() { return _final; }
57          public void setPre(Quad q, Fact dff) { _pre[q.getID()] = dff; }
58          public void setPost(Quad q, Fact dff) { _post[q.getID()] = dff; }
59          public void setInitial(Fact dff) { _initial = dff; }
60          public void setFinal(Fact dff) { _final = dff; }
61      }
62  
63      static class DataflowHash implements FactCollection {
64          private HashMap _pre, _post;
65          private Fact _initial, _final;
66  
67          public DataflowHash() {
68              _pre = new HashMap();
69              _post = new HashMap();
70              _initial = null;
71              _final = null;
72          }
73  
74          public Fact getPre(Quad q) { return (Fact)(_pre.get(new Integer(q.getID()))); }
75          public Fact getPost(Quad q) { return (Fact)(_post.get(new Integer(q.getID()))); }
76          public Fact getInitial() { return _initial; }
77          public Fact getFinal() { return _final; }
78          public void setPre(Quad q, Fact dff) { _pre.put(new Integer(q.getID()), dff); }
79          public void setPost(Quad q, Fact dff) { _post.put(new Integer(q.getID()), dff); }
80          public void setInitial(Fact dff) { _initial = dff; }
81          public void setFinal(Fact dff) { _final = dff; }
82      }
83  
84      static class Intraprocedural implements ControlFlowGraphVisitor {
85          private FactCollection _dfc;
86          private Transfer _transfer;
87  
88          public Intraprocedural (Transfer t) { _transfer = t; _dfc = null; }
89  
90          private void determineStorageStyle(ControlFlowGraph cfg) {
91              QuadIterator qi = new QuadIterator(cfg);
92              int quadCount = 0;
93              int quadIDMax = Integer.MIN_VALUE;
94              int quadIDMin = Integer.MAX_VALUE;
95              while (qi.hasNext()) {
96                  int qID = qi.nextQuad().getID();
97                  if (qID > quadIDMax) quadIDMax = qID;
98                  if (qID < quadIDMin) quadIDMin = qID;
99                  ++quadCount;
100             }
101             boolean useArray = (quadIDMin >= 0) || (quadIDMax <= quadCount * 2);
102 
103             if (TRACE_DATAFLOW) {
104                 DF_OUT.println("Number of quads: "+quadCount);
105                 DF_OUT.println("Minimum Quad ID: "+quadIDMin);
106                 DF_OUT.println("Maximum Quad ID: "+quadIDMax);
107                 DF_OUT.println("Using " + (useArray ? "array" : "HashMap") + " implementation.");
108             }
109             if (useArray)
110                 _dfc = new DataflowArray(quadIDMax+1);
111             else
112                 _dfc = new DataflowHash();
113             _transfer.registerFactCollection(_dfc);
114         }
115 
116         public void visitCFG(ControlFlowGraph cfg) {
117             determineStorageStyle(cfg);
118             
119             _transfer.preprocess(cfg);
120 
121             boolean changed;
122 
123             changed = true;
124             while (changed) {
125                 if (TRACE_DATAFLOW) DF_OUT.println("Beginning a new pass.");
126                 QuadIterator qi = new QuadIterator(cfg);
127                 changed = false;
128                 while (qi.hasNext()) {
129                     Quad q = qi.nextQuad();
130                     if (TRACE_DATAFLOW_QUADS) {
131                         DF_OUT.println("Analyzing Quad: "+q);
132                     }
133 
134                     Fact f = _dfc.getPre(q);
135                     if (f != null) {
136                         Iterator pi = qi.predecessors();
137                         while (pi.hasNext()) {
138                             Quad p = (Quad)pi.next();
139                             if (p == null) {
140                                 f.meetWith(_dfc.getInitial());
141                             } else {
142                                 f.meetWith(_dfc.getPost(p));
143                             }
144                         }
145                     }
146 
147                     if (_transfer.transfer(q))
148                         changed = true;
149                 }
150             }
151             if (TRACE_DATAFLOW) DF_OUT.println("No changes, postprocessing...");
152             _transfer.postprocess(cfg);
153             if (TRACE_DATAFLOW) DF_OUT.println("Method complete.");
154         }
155     }
156 
157     public static class EmptyAnalysis extends jq_MethodVisitor.EmptyVisitor
158                                       implements Transfer {
159         ControlFlowGraphVisitor.CodeCacheVisitor ccv;
160 
161         protected FactCollection _fc;
162 
163         public void registerFactCollection(FactCollection fc) { _fc = fc; }
164 
165         public void preprocess(ControlFlowGraph cfg) { }
166         public boolean transfer(Quad q) { return false; }
167         public void postprocess(ControlFlowGraph cfg) { }
168 
169         public EmptyAnalysis() {
170             ccv = new ControlFlowGraphVisitor.CodeCacheVisitor(new Intraprocedural(this));
171         }
172         
173         public void visitMethod (jq_Method m) {
174             if (TRACE_DATAFLOW) DF_OUT.println("Analyzing method: "+m.getName());
175             ccv.visitMethod(m);
176         }
177     }
178 }