1 salcianu 1.1.2.1 // AbstrPAEdgeSet.java, created Fri Jun 30 15:00:48 2000 by salcianu
2 cananian 1.1.2.4 // Copyright (C) 2000 Alexandru SALCIANU <salcianu@retezat.lcs.mit.edu>
3 salcianu 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 salcianu 1.1.2.1 package harpoon.Analysis.PointerAnalysis;
5 salcianu 1.1.2.1
6 salcianu 1.1.2.1
7 salcianu 1.1.2.1 import java.util.Collection;
8 salcianu 1.1.2.1 import java.util.Iterator;
9 salcianu 1.1.2.1 import java.util.Map;
10 salcianu 1.1.2.1 import java.util.Set;
11 salcianu 1.1.2.1 import java.util.HashSet;
12 salcianu 1.1.2.1
13 salcianu 1.1.2.2 import harpoon.Util.DataStructs.Relation;
14 salcianu 1.1.2.2 import harpoon.Util.DataStructs.RelationImpl;
15 salcianu 1.1.2.2
16 salcianu 1.1.2.1 import harpoon.Temp.Temp;
17 salcianu 1.1.2.1
18 salcianu 1.1.2.1
19 salcianu 1.1.2.1 /**
20 salcianu 1.1.2.1 * <code>AbstrPAEdgeSet</code>
21 salcianu 1.1.2.1 *
22 cananian 1.1.2.4 * @author Alexandru SALCIANU <salcianu@retezat.lcs.mit.edu>
23 cananian 1.4 * @version $Id: AbstrPAEdgeSet.java,v 1.4 2004/02/08 03:20:02 cananian Exp $
24 salcianu 1.1.2.1 */
25 salcianu 1.1.2.1 public abstract class AbstrPAEdgeSet implements PAEdgeSet, Cloneable {
26 salcianu 1.1.2.1
27 salcianu 1.3 public abstract void addEdge(Temp v, PANode node);
28 salcianu 1.3 public abstract void addEdges(Temp v, Collection nodes);
29 salcianu 1.1.2.1
30 salcianu 1.3 public abstract void removeEdge(Temp v, PANode node);
31 salcianu 1.3 public abstract void removeEdges(Temp v);
32 salcianu 1.1.2.1
33 salcianu 1.1.2.1
34 salcianu 1.3 public abstract Set pointedNodes(Temp v);
35 salcianu 1.1.2.1
36 salcianu 1.3 public abstract Set allVariables();
37 salcianu 1.1.2.1
38 salcianu 1.1.2.1
39 salcianu 1.1.2.1
40 salcianu 1.3 public abstract boolean addEdge(PANode node1, String f, PANode node2);
41 salcianu 1.3 public abstract boolean addEdges(PANode node1, String f,Collection node2s);
42 salcianu 1.1.2.1
43 salcianu 1.1.2.1 public void addEdges(Collection node1s, String f, PANode node2) {
44 salcianu 1.1.2.1 for(Iterator it = node1s.iterator(); it.hasNext(); )
45 salcianu 1.1.2.1 addEdge((PANode) it.next(), f, node2);
46 salcianu 1.1.2.1 }
47 salcianu 1.1.2.1
48 salcianu 1.1.2.1 public void addEdges(Collection node1s, String f, Collection node2s) {
49 salcianu 1.1.2.1 if(node2s.isEmpty()) return;
50 salcianu 1.1.2.1 for(Iterator it = node1s.iterator(); it.hasNext(); )
51 salcianu 1.1.2.1 addEdges((PANode) it.next(), f, node2s);
52 salcianu 1.1.2.1 }
53 salcianu 1.1.2.1
54 salcianu 1.1.2.1
55 salcianu 1.3 public abstract void removeEdge(PANode node1, String f, PANode node2);
56 salcianu 1.3 public abstract void removeEdges(PANode node1, String f);
57 salcianu 1.3 public abstract void removeEdges(PANode node1);
58 salcianu 1.1.2.1
59 salcianu 1.1.2.1
60 salcianu 1.3 public abstract Set pointedNodes(PANode node, String f);
61 salcianu 1.1.2.1
62 salcianu 1.1.2.1 public Set pointedNodes(Collection nodes, String f) {
63 salcianu 1.1.2.1 Set retval = new HashSet();
64 salcianu 1.1.2.1 for(Iterator it = nodes.iterator(); it.hasNext(); )
65 salcianu 1.1.2.1 retval.addAll(pointedNodes((PANode) it.next(), f));
66 salcianu 1.1.2.1 return retval;
67 salcianu 1.1.2.1 }
68 salcianu 1.1.2.1
69 salcianu 1.3 public abstract Set pointedNodes(PANode node);
70 salcianu 1.1.2.1
71 salcianu 1.3 public abstract Set allFlagsForNode(PANode node);
72 salcianu 1.1.2.1
73 salcianu 1.3 public abstract Set allSourceNodes();
74 salcianu 1.1.2.1
75 salcianu 1.1.2.1
76 salcianu 1.1.2.1 // I think this should be removed in the future
77 salcianu 1.1.2.1 public Set getEdgesFrom(PANode node, String f) {
78 salcianu 1.1.2.1 Set set = new HashSet();
79 salcianu 1.1.2.1 for(Iterator it = pointedNodes(node, f).iterator(); it.hasNext(); )
80 salcianu 1.1.2.1 set.add(new PAEdge(node, f, (PANode) it.next()));
81 salcianu 1.1.2.1 return set;
82 salcianu 1.1.2.1 }
83 salcianu 1.1.2.1
84 salcianu 1.1.2.1
85 salcianu 1.1.2.1
86 salcianu 1.1.2.1 public void forAllPointedNodes(Temp v, PANodeVisitor visitor) {
87 salcianu 1.1.2.1 for(Iterator it = pointedNodes(v).iterator(); it.hasNext(); )
88 salcianu 1.1.2.1 visitor.visit((PANode) it.next());
89 salcianu 1.1.2.1 }
90 salcianu 1.1.2.1
91 salcianu 1.1.2.1
92 salcianu 1.1.2.1 public void forAllPointedNodes(PANode node, String f,
93 salcianu 1.1.2.1 PANodeVisitor visitor) {
94 salcianu 1.1.2.1 for(Iterator it = pointedNodes(node, f).iterator(); it.hasNext(); )
95 salcianu 1.1.2.1 visitor.visit((PANode) it.next());
96 salcianu 1.1.2.1 }
97 salcianu 1.1.2.1
98 salcianu 1.3 // for maximum performance, this is implemented in the concrete class
99 salcianu 1.3 public abstract void forAllPointedNodes(PANode node, PANodeVisitor visitor);
100 salcianu 1.1.2.1
101 salcianu 1.1.2.1 public void forAllNodes(PANodeVisitor visitor) {
102 salcianu 1.1.2.1 for(Iterator it = allVariables().iterator(); it.hasNext(); )
103 salcianu 1.1.2.1 forAllPointedNodes((Temp) it.next(), visitor);
104 salcianu 1.1.2.1
105 cananian 1.4 for(Object nodeO : allSourceNodes()) {
106 cananian 1.4 PANode node = (PANode) nodeO;
107 salcianu 1.1.2.3 visitor.visit(node);
108 salcianu 1.1.2.3 forAllPointedNodes(node, visitor);
109 salcianu 1.1.2.3 }
110 salcianu 1.1.2.1 }
111 salcianu 1.1.2.1
112 salcianu 1.1.2.1
113 salcianu 1.1.2.1 public void forAllEdges(Temp v, PAEdgeVisitor visitor) {
114 salcianu 1.1.2.1 for(Iterator it = pointedNodes(v).iterator(); it.hasNext(); )
115 salcianu 1.1.2.1 visitor.visit(v, (PANode) it.next());
116 salcianu 1.1.2.1 }
117 salcianu 1.1.2.1
118 salcianu 1.3 public abstract void forAllEdges(PANode node, PAEdgeVisitor visitor);
119 salcianu 1.1.2.1
120 salcianu 1.1.2.1 public void forAllEdges(PAEdgeVisitor visitor) {
121 salcianu 1.1.2.1 for(Iterator it = allVariables().iterator(); it.hasNext(); )
122 salcianu 1.1.2.1 forAllEdges((Temp) it.next(), visitor);
123 salcianu 1.1.2.1 for(Iterator it = allSourceNodes().iterator(); it.hasNext(); )
124 salcianu 1.1.2.1 forAllEdges((PANode) it.next(), visitor);
125 salcianu 1.1.2.1 }
126 salcianu 1.1.2.1
127 salcianu 1.3 protected abstract PAEdgeSet getEmptyPAEdgeSet();
128 salcianu 1.1.2.1
129 salcianu 1.1.2.1 // very easy implementation (can be hand-crafted into the concrete class)
130 salcianu 1.1.2.1 public PAEdgeSet specialize(final Map map) {
131 salcianu 1.1.2.1 final PAEdgeSet es2 = getEmptyPAEdgeSet();
132 salcianu 1.1.2.1
133 salcianu 1.1.2.1 forAllEdges(new PAEdgeVisitor(){
134 salcianu 1.1.2.1 public void visit(Temp var, PANode node){
135 salcianu 1.1.2.1 es2.addEdge(var, PANode.translate(node,map));
136 salcianu 1.1.2.1 }
137 salcianu 1.1.2.1 public void visit(PANode node1, String f, PANode node2){
138 salcianu 1.1.2.1 es2.addEdge(PANode.translate(node1,map),
139 salcianu 1.1.2.1 f,
140 salcianu 1.1.2.1 PANode.translate(node2,map));
141 salcianu 1.1.2.1 }
142 salcianu 1.1.2.1 });
143 salcianu 1.1.2.1
144 salcianu 1.1.2.1 return es2;
145 salcianu 1.1.2.1 }
146 salcianu 1.1.2.1
147 salcianu 1.1.2.1
148 salcianu 1.3 public abstract void remove(Set set);
149 salcianu 1.1.2.1
150 salcianu 1.3 public abstract void union(PAEdgeSet edges2, Set ppgRoots);
151 salcianu 1.3 public void union(PAEdgeSet edges2) { union(edges2, null); }
152 salcianu 1.1.2.2
153 salcianu 1.1.2.2
154 salcianu 1.1.2.2 public Relation getPrecedenceRelation() {
155 salcianu 1.1.2.2 final Relation rel = new RelationImpl();
156 salcianu 1.1.2.2 forAllEdges(new PAEdgeVisitor() {
157 salcianu 1.1.2.2 public void visit(Temp var, PANode node) {}
158 salcianu 1.1.2.2 public void visit(PANode node1, String f, PANode node2) {
159 salcianu 1.1.2.2 rel.add(node2, node1);
160 salcianu 1.1.2.2 }
161 salcianu 1.1.2.2 });
162 salcianu 1.1.2.2 return rel;
163 salcianu 1.1.2.1 }
164 salcianu 1.1.2.1
165 salcianu 1.1.2.1
166 salcianu 1.1.2.1 public String toString() {
167 salcianu 1.1.2.1 StringBuffer buffer = new StringBuffer();
168 salcianu 1.1.2.1 buffer.append(" {\n");
169 salcianu 1.1.2.1
170 salcianu 1.1.2.1 Object[] vars = Debug.sortedCollection(allVariables());
171 salcianu 1.1.2.1 for(int i = 0; i < vars.length; i++) {
172 salcianu 1.1.2.1 Temp v = (Temp) vars[i];
173 salcianu 1.1.2.1 buffer.append(" " + v + " -> ");
174 salcianu 1.1.2.1 buffer.append(Debug.stringImg(pointedNodes(v)));
175 salcianu 1.1.2.1 buffer.append("\n");
176 salcianu 1.1.2.1 }
177 salcianu 1.1.2.1
178 salcianu 1.1.2.1
179 salcianu 1.1.2.1 Object[] nodes = Debug.sortedCollection(allSourceNodes());
180 salcianu 1.1.2.1 for(int i = 0 ; i < nodes.length ; i++) {
181 salcianu 1.1.2.1 PANode node = (PANode) nodes[i];
182 salcianu 1.1.2.1
183 salcianu 1.1.2.1 Object[] flags = Debug.sortedCollection(allFlagsForNode(node));
184 salcianu 1.1.2.1 if(flags.length == 0) continue;
185 salcianu 1.1.2.1
186 salcianu 1.1.2.1 buffer.append(" " + node + " -> {\n");
187 salcianu 1.1.2.1
188 salcianu 1.1.2.1 for(int j = 0; j < flags.length; j++) {
189 salcianu 1.1.2.1 String f = (String) flags[j];
190 salcianu 1.1.2.1 buffer.append(" " + f + " -> ");
191 salcianu 1.1.2.1 buffer.append(Debug.stringImg(pointedNodes(node, f)));
192 salcianu 1.1.2.1 buffer.append("\n");
193 salcianu 1.1.2.1 }
194 salcianu 1.1.2.1 buffer.append(" }\n");
195 salcianu 1.1.2.1 }
196 salcianu 1.1.2.1
197 salcianu 1.1.2.1 buffer.append(" }\n");
198 salcianu 1.1.2.1
199 salcianu 1.1.2.1 return buffer.toString();
200 salcianu 1.1.2.1 }
201 salcianu 1.1.2.1
202 salcianu 1.1.2.1 public Object clone() {
203 salcianu 1.1.2.1 try {
204 salcianu 1.1.2.1 return super.clone();
205 salcianu 1.1.2.1 } catch(CloneNotSupportedException e) {
206 salcianu 1.1.2.1 throw new InternalError();
207 salcianu 1.1.2.1 }
208 salcianu 1.1.2.1 }
209 salcianu 1.1.2.1
210 salcianu 1.1.2.1
211 salcianu 1.1.2.1 static class PASimpleEdge{
212 salcianu 1.1.2.1 Temp t;
213 salcianu 1.1.2.1 PANode node;
214 salcianu 1.1.2.1
215 salcianu 1.1.2.1 PASimpleEdge(Temp t, PANode node){
216 salcianu 1.1.2.1 this.t = t;
217 salcianu 1.1.2.1 this.node = node;
218 salcianu 1.1.2.1 }
219 salcianu 1.1.2.1
220 salcianu 1.1.2.1 public String toString(){
221 salcianu 1.1.2.1 return "<" + t + "," + node + ">";
222 salcianu 1.1.2.1 }
223 salcianu 1.1.2.1 }
224 salcianu 1.1.2.1
225 salcianu 1.1.2.1 static class PAComplexEdge{
226 salcianu 1.1.2.1 PANode node1;
227 salcianu 1.1.2.1 String f;
228 salcianu 1.1.2.1 PANode node2;
229 salcianu 1.1.2.1
230 salcianu 1.1.2.1 PAComplexEdge(PANode node1, String f, PANode node2){
231 salcianu 1.1.2.1 this.node1 = node1;
232 salcianu 1.1.2.1 this.f = f;
233 salcianu 1.1.2.1 this.node2 = node2;
234 salcianu 1.1.2.1 }
235 salcianu 1.1.2.1
236 salcianu 1.1.2.1 public String toString(){
237 salcianu 1.1.2.1 return "<" + node1 + "," + f + "," + node2 + ">";
238 salcianu 1.1.2.1 }
239 salcianu 1.1.2.1 }
240 salcianu 1.1.2.1
241 salcianu 1.1.2.1 /** Computes the difference between two sets of edges. Returns the
242 salcianu 1.1.2.1 set of edges that are present in es1 but not in es2. The returned
243 salcianu 1.1.2.1 set contains elements of type <code>PASimpleEdge</code> or
244 salcianu 1.1.2.1 <code>PAComplexEdge</code>. For debug purposes. */
245 salcianu 1.1.2.1 public static Set difference(final PAEdgeSet es1,
246 salcianu 1.3 final PAEdgeSet es2) {
247 salcianu 1.1.2.1 final Set retval = new HashSet();
248 salcianu 1.1.2.1 es1.forAllEdges(new PAEdgeVisitor(){
249 salcianu 1.1.2.1 public void visit(Temp l, PANode node){
250 salcianu 1.1.2.1 if(!es2.pointedNodes(l).contains(node))
251 salcianu 1.1.2.1 retval.add(new PASimpleEdge(l, node));
252 salcianu 1.1.2.1 }
253 salcianu 1.1.2.1 public void visit(PANode node1, String f, PANode node2){
254 salcianu 1.1.2.1 if(!es2.pointedNodes(node1, f).contains(node2))
255 salcianu 1.1.2.1 retval.add(new PAComplexEdge(node1, f, node2));
256 salcianu 1.1.2.1 }
257 salcianu 1.1.2.1 });
258 salcianu 1.1.2.1 return retval;
259 salcianu 1.1.2.1 }
260 salcianu 1.1.2.1
261 salcianu 1.1.2.1
262 salcianu 1.1.2.1 /** Display the edges which were removed and the edges which were
263 salcianu 1.1.2.1 added while passing from <code>es_old</code> to
264 salcianu 1.1.2.1 <code>es_new</code>. */
265 salcianu 1.1.2.1 public static void show_evolution(final PAEdgeSet es_old,
266 salcianu 1.3 final PAEdgeSet es_new) {
267 salcianu 1.1.2.1 Set old_edges = difference(es_old, es_new);
268 salcianu 1.3 if(!old_edges.isEmpty()) {
269 salcianu 1.1.2.1 System.out.println("Some edges were removed:");
270 salcianu 1.1.2.1 for(Iterator it = old_edges.iterator(); it.hasNext();)
271 salcianu 1.1.2.1 System.out.println(" " + it.next());
272 salcianu 1.1.2.1 }
273 salcianu 1.1.2.1 Set new_edges = difference(es_new, es_old);
274 salcianu 1.1.2.1 if(!new_edges.isEmpty()){
275 salcianu 1.1.2.1 System.out.println("New edges were added:");
276 salcianu 1.1.2.1 for(Iterator it = new_edges.iterator(); it.hasNext();)
277 salcianu 1.1.2.1 System.out.println(" " + it.next());
278 salcianu 1.1.2.1 }
279 salcianu 1.3 if(!old_edges.isEmpty())
280 salcianu 1.3 System.exit(1);
281 salcianu 1.1.2.1 }
282 salcianu 1.1.2.1
283 cananian 1.2 }