1
2
3
4
5
6
7 package joeq.Compiler.Analysis.IPSSA;
8
9 import java.util.HashMap;
10 import java.util.HashSet;
11 import java.util.Iterator;
12 import java.util.LinkedList;
13 import java.util.Set;
14 import java.io.PrintStream;
15 import joeq.Compiler.Analysis.IPSSA.Utils.IteratorHelper;
16 import jwutil.collections.LinearSet;
17 import jwutil.util.Assert;
18
19 /***
20 * This is a graph consisting of definitions that uses as much sharing as possible.
21 *
22 * Provides a dot printer.
23 *
24 * @author V.Benjamin Livshits
25 */
26 public abstract class DefinitionGraph {
27 private HashSet _nodes;
28 protected int _edgeCount = 0;
29
30 public DefinitionGraph(){
31 _nodes = new HashSet();
32 }
33
34 protected void addNode(SSADefinition def){
35 _nodes.add(def);
36 }
37
38 public int getEdgeCount(){return _edgeCount;}
39 public int getNodeCount(){return _nodes.size();}
40
41 public abstract void addEdge(SSADefinition def1, SSADefinition def2, EdgeInfo ei);
42 public abstract boolean isRootNode(SSADefinition def);
43 public abstract boolean isTerminalNode(SSADefinition def);
44
45 /*** Retrieves all roots of the forest that we are constructing */
46 public Set getRoots(){
47 LinearSet set = new LinearSet();
48 for(Iterator iter = _nodes.iterator(); iter.hasNext();){
49 SSADefinition def = (SSADefinition)iter.next();
50
51 if(isRootNode(def)){
52 set.add(def);
53 }
54 }
55 return set;
56 }
57
58 public Set getTerminals(){
59 LinearSet set = new LinearSet();
60 for(Iterator iter = _nodes.iterator(); iter.hasNext();){
61 SSADefinition def = (SSADefinition)iter.next();
62
63 if(isTerminalNode(def)){
64 set.add(def);
65 }
66 }
67 return set;
68 }
69
70
71 public abstract SSAIterator.DefinitionIterator getReached(SSADefinition def);
72 /*** All reaching definitions */
73 public abstract SSAIterator.DefinitionIterator getAllReached(SSADefinition def);
74
75
76
77 /*** One level of pointees */
78 public abstract SSAIterator.DefinitionIterator getReaching(SSADefinition def);
79 /*** All reaching definitions */
80 public abstract SSAIterator.DefinitionIterator getAllReaching(SSADefinition def);
81
82
83 public String toString(){
84 return "DefinitionGraph: " + _nodes.size() + "nodes, " + _edgeCount + " edges";
85 }
86
87 /***
88 * Prints the subtree starting at definition def in a dot graph form.
89 * */
90 public void printDot(PrintStream out){
91 printDot(_nodes.iterator(), out, true);
92 }
93 public void printReachedToDot(SSADefinition def, PrintStream out){
94 printDot(new IteratorHelper.SingleIterator(def), out, true);
95 }
96 public void printReachingToDot(SSADefinition def, PrintStream out){
97 printDot(new IteratorHelper.SingleIterator(def), out, false);
98 }
99
100 protected void printDot(Iterator iter, PrintStream out, final boolean direction){
101 joeq.Util.SyntheticGraphs.Graph g = new joeq.Util.SyntheticGraphs.Graph();
102
103 while(iter.hasNext()){
104 SSADefinition def = (SSADefinition)iter.next();
105
106 (new Object(){
107 void makeDotAux(joeq.Util.SyntheticGraphs.Graph g, SSADefinition def){
108 g.addNode(def.getID(), def.toString());
109 Iterator iter = direction ? getReached(def) : getReaching(def);
110 if(iter != null){
111 while(iter.hasNext()){
112 SSADefinition def2 = (SSADefinition) iter.next();
113 g.addEdge(def.getID(), def2.getID());
114
115 makeDotAux(g, def2);
116 }
117 }
118 }
119 }).makeDotAux(g, def);
120
121 g.printDot(out);
122 }
123 }
124
125 /*** By default a true predicate edge is added */
126 public void addEdge(SSADefinition def1, SSADefinition def2){
127 addEdge(def1, def2, PredicateEdge.TrueEdge.FACTORY.get());
128 }
129
130 /*** null returned means that there is no edge */
131 public abstract EdgeInfo getEdgeInfo(SSADefinition def1, SSADefinition def2);
132
133
134
135 public interface EdgeInfo {};
136
137 class EmptyEdge implements EdgeInfo {}
138
139 static class PredicateEdge implements EdgeInfo {
140 SSAValue.Predicate _predicate;
141
142 PredicateEdge(SSAValue.Predicate predicate){
143 this._predicate = predicate;
144 }
145
146 static class TrueEdge extends PredicateEdge {
147 SSAValue.Predicate _predicate;
148
149 private TrueEdge(){
150 super(SSAValue.Predicate.True());
151 }
152
153 static class FACTORY {
154 static TrueEdge _sample;
155
156 /*** Use this method instead of the TrueEdge constructor */
157 static TrueEdge get(){
158 if(_sample == null){
159 _sample = new TrueEdge();
160 }
161 return _sample;
162 }
163 }
164 }
165 }
166
167 class ContextEdge implements EdgeInfo {
168 ContextSet _context;
169
170 ContextEdge(ContextSet context){
171 this._context = context;
172 }
173 }
174
175 class IPEdge implements EdgeInfo {
176
177
178
179 IPEdge(){
180
181 }
182 }
183
184 /***
185 * The representation consists of an bunch of adjecently lists pointing
186 * to and from a node. We can only have one edge between any two definitions.
187 * */
188 class EfficientDefinitionGraph extends DefinitionGraph {
189 private HashMap
190 private HashMap
191
192 EfficientDefinitionGraph(){}
193
194 public void addEdge(SSADefinition def1, SSADefinition def2, EdgeInfo ei){
195
196 HashMap map = (HashMap)_adjacencyLists.get(def2);
197 if(map == null){
198 map = new HashMap();
199 _adjacencyLists.put(def2, map);
200 }
201
202 Assert._assert(!map.containsKey(def1), "Already have a an edge " +
203 def1.toString() + " -> " + def2.toString() +
204 " with edge information " + ei.toString());
205
206 map.put(def1, ei);
207
208
209 LinkedList list = (LinkedList)_reverseAdjacencyLists.get(def1);
210 if(list == null){
211 list = new LinkedList();
212 }
213 list.addLast(def2);
214 _edgeCount++;
215 }
216
217 public EdgeInfo getEdgeInfo(SSADefinition def1, SSADefinition def2){
218 HashMap map = (HashMap)_adjacencyLists.get(def2);
219 if(map == null){
220 return null;
221 }
222 return (EdgeInfo)map.get(def1);
223 }
224
225 /*** True is this nodes doesn't point to anyone */
226 public boolean isTerminalNode(SSADefinition def){
227 LinkedList list = (LinkedList)_reverseAdjacencyLists.get(def);
228 if(list == null){
229 return true;
230 }
231
232 return list.isEmpty();
233 }
234
235 /*** True if nobody points to this node */
236 public boolean isRootNode(SSADefinition def){
237 HashMap map = (HashMap)_adjacencyLists.get(def);
238 if(map == null){
239 return true;
240 }
241
242 return map.isEmpty();
243 }
244
245
246 public SSAIterator.DefinitionIterator getReached(SSADefinition def){
247 LinkedList list = (LinkedList)_reverseAdjacencyLists.get(def);
248 if(list == null){
249 return null;
250 }
251
252 return new SSAIterator.DefinitionIterator(list.iterator());
253 }
254 public SSAIterator.DefinitionIterator getAllReached(SSADefinition def){
255 HashSet set = new HashSet();
256
257 (new Object(){
258 Set getReachedAux(SSADefinition def, Set set){
259 set.add(def);
260 Iterator iter = getReached(def);
261 if(iter != null){
262 while(iter.hasNext()){
263 SSADefinition def2 = (SSADefinition)iter.next();
264
265 getReachedAux(def2, set);
266 }
267 }
268
269 return set;
270 }
271 }).getReachedAux(def, set);
272
273 return new SSAIterator.DefinitionIterator(set.iterator());
274 }
275
276
277 public SSAIterator.DefinitionIterator getReaching(SSADefinition def){
278 HashMap map = (HashMap)_adjacencyLists.get(def);
279 if(map == null){
280 return null;
281 }
282
283 return new SSAIterator.DefinitionIterator(map.values().iterator());
284 }
285 public SSAIterator.DefinitionIterator getAllReaching(SSADefinition def){
286 HashSet set = new HashSet();
287
288 (new Object(){
289 Set getReachingAux(SSADefinition def, Set set){
290 set.add(def);
291 Iterator iter = getReaching(def);
292 if(iter != null){
293 while(iter.hasNext()){
294 SSADefinition def2 = (SSADefinition)iter.next();
295
296 getReachingAux(def2, set);
297 }
298 }
299
300 return set;
301 }
302 }).getReachingAux(def, set);
303
304 return new SSAIterator.DefinitionIterator(set.iterator());
305 }
306 }
307 }