1
2
3
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 }