1 salcianu 1.1.2.1 // EdgeOrdering.java, created Wed Feb 16 14:50:33 2000 by salcianu
2 cananian 1.1.2.12 // 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.Set;
8 salcianu 1.1.2.1 import java.util.HashSet;
9 salcianu 1.1.2.8 import java.util.Map;
10 salcianu 1.1.2.1 import java.util.Iterator;
11 salcianu 1.1.2.5 import java.util.Enumeration;
12 salcianu 1.1.2.1
13 salcianu 1.1.2.1 import harpoon.Temp.Temp;
14 salcianu 1.1.2.1
15 salcianu 1.1.2.10 import harpoon.Util.PredicateWrapper;
16 salcianu 1.1.2.10 import harpoon.Util.DataStructs.Relation;
17 salcianu 1.1.2.10 import harpoon.Util.DataStructs.LightRelation;
18 salcianu 1.1.2.10 import harpoon.Util.DataStructs.RelationEntryVisitor;
19 salcianu 1.1.2.10
20 salcianu 1.1.2.1
21 salcianu 1.1.2.1 /**
22 salcianu 1.1.2.5 * <code>EdgeOrdering</code> models the ordering relation between the
23 salcianu 1.1.2.1 inside and the outside edges belonging to the same analysis scope.<br>
24 salcianu 1.1.2.5
25 salcianu 1.1.2.5 This relation records facts like this: <i>the outside edge <code>eo</code>
26 salcianu 1.1.2.5 could have been read after the inside edge <code>ei</code> was created.</i>
27 salcianu 1.1.2.5 This information is used in the inter-thread analysis, when outside edges
28 salcianu 1.1.2.5 are matched not only against inside edges from the opposite scope but even
29 salcianu 1.1.2.5 against inside edges from their own scope. Of course, only edges with the
30 salcianu 1.1.2.5 same field can match, so we are interested in the ordering relation only
31 salcianu 1.1.2.5 between such edges.<br>
32 salcianu 1.1.2.5
33 salcianu 1.1.2.1 Although the actual implementation is fully functional, it is not
34 salcianu 1.1.2.1 a very performant one. My main concern was to make the algorithm work
35 salcianu 1.1.2.5 correctly; speed was only a second issue.
36 salcianu 1.1.2.1 *
37 cananian 1.1.2.12 * @author Alexandru SALCIANU <salcianu@retezat.lcs.mit.edu>
38 cananian 1.3 * @version $Id: EdgeOrdering.java,v 1.3 2004/02/08 03:20:02 cananian Exp $
39 salcianu 1.1.2.1 */
40 salcianu 1.1.2.11 public class EdgeOrdering implements java.io.Serializable {
41 salcianu 1.1.2.1
42 salcianu 1.1.2.5 // the relation behind the implementation: if <eo,ei> appears in this
43 salcianu 1.1.2.5 // relation, the outside edge eo could have been read after the inside
44 salcianu 1.1.2.5 // edge ei was created.
45 salcianu 1.1.2.5 // So, outside edges are the keys and inside edges are the values
46 salcianu 1.1.2.5 // of this relation.
47 salcianu 1.1.2.1 private Relation after;
48 salcianu 1.1.2.1
49 salcianu 1.1.2.1 /** Creates a <code>EdgeOrdering</code> object. */
50 salcianu 1.1.2.1 public EdgeOrdering(){
51 salcianu 1.1.2.10 after = new LightRelation();
52 salcianu 1.1.2.1 }
53 salcianu 1.1.2.1
54 salcianu 1.1.2.5 /** Adds a piece of ordering information. More specifically, it records
55 salcianu 1.1.2.5 the following information: <i>the outside edge <code>eo</code>
56 salcianu 1.1.2.5 could have been read after the inside edge <code>ei</code> was
57 salcianu 1.1.2.5 created</i>. */
58 salcianu 1.1.2.1 public boolean add(PAEdge eo, PAEdge ei){
59 salcianu 1.1.2.2 if(!eo.f.equals(ei.f)) return false;
60 salcianu 1.1.2.1 return after.add(eo,ei);
61 salcianu 1.1.2.6 }
62 salcianu 1.1.2.6
63 salcianu 1.1.2.6 /** Returns an iterator over the set of the inside edges that could
64 salcianu 1.1.2.6 be already created when the inside edge <code>eo</code> is read.
65 salcianu 1.1.2.6 This method will be used in the intre-thread analysis when trying to
66 salcianu 1.1.2.6 match an outside edge against those inside edges from the same scope
67 salcianu 1.1.2.6 that could be created when the load is done. */
68 salcianu 1.1.2.6 public Iterator getBeforeEdges(PAEdge eo){
69 salcianu 1.1.2.10 return after.getValues(eo).iterator();
70 salcianu 1.1.2.1 }
71 salcianu 1.1.2.1
72 salcianu 1.1.2.1 /** Checks whether the inside edge <code>ei</code> could have been
73 salcianu 1.1.2.1 created before the outside edge <code>eo</code> is read. */
74 salcianu 1.1.2.1 public boolean wasBefore(PAEdge ei, PAEdge eo){
75 salcianu 1.1.2.1 return after.contains(eo,ei);
76 salcianu 1.1.2.1 }
77 salcianu 1.1.2.1
78 salcianu 1.1.2.1 /** Records the fact that all the outside edges from the set
79 salcianu 1.1.2.3 <code>outside_edges</code> are created after all the inside
80 salcianu 1.1.2.5 edges from I. We are interested only in the relation between
81 salcianu 1.1.2.5 edges with the same field <code>f</code>.<br>
82 salcianu 1.1.2.5 <b>Parameters:</b> <code>outside_edge</code> must be a set
83 salcianu 1.1.2.5 of <code>PAEdge</code>s, all with the same field <code>f</code>.
84 salcianu 1.1.2.5 <b>Result:</b> it returns <code>true</code> if the edge ordering
85 salcianu 1.1.2.3 relation was changed by this addition. */
86 salcianu 1.1.2.5 private boolean add(final Set outside_edges, PAEdgeSet I, String f){
87 salcianu 1.1.2.5 boolean modified = false;
88 salcianu 1.1.2.5
89 cananian 1.3 for(Object node1O : I.allSourceNodes()) {
90 cananian 1.3 PANode node1 = (PANode) node1O;
91 cananian 1.3 for(Object node2O : I.pointedNodes(node1, f)) {
92 cananian 1.3 PANode node2 = (PANode) node2O;
93 salcianu 1.1.2.9 PAEdge ei = new PAEdge(node1, f, node2);
94 cananian 1.3 for (Object eoO : outside_edges){
95 cananian 1.3 PAEdge eo = (PAEdge) eoO;
96 salcianu 1.1.2.5 if(add(eo,ei)) modified = true;
97 salcianu 1.1.2.1 }
98 salcianu 1.1.2.5 }
99 salcianu 1.1.2.5 }
100 salcianu 1.1.2.5
101 salcianu 1.1.2.5 return modified;
102 salcianu 1.1.2.1 }
103 salcianu 1.1.2.1
104 salcianu 1.1.2.1
105 salcianu 1.1.2.5 /** Records the fact that the new outside edges
106 salcianu 1.1.2.5 <code><node1,f,node2></code>
107 salcianu 1.1.2.5 (forall <code>node1</code> in <code>nodes1</code>) are created after
108 salcianu 1.1.2.5 all the inside edges from <code>I</code>.
109 salcianu 1.1.2.5 Returns <code>true</code> if he edge ordering relation was changed by
110 salcianu 1.1.2.5 this addition. */
111 salcianu 1.1.2.1 public boolean add(Set nodes1, String f, PANode node2, PAEdgeSet I){
112 salcianu 1.1.2.1 Set outside_edges = new HashSet();
113 cananian 1.3 for (Object node1O : nodes1){
114 cananian 1.3 PANode node1 = (PANode) node1O;
115 salcianu 1.1.2.1 outside_edges.add(new PAEdge(node1,f,node2));
116 salcianu 1.1.2.1 }
117 salcianu 1.1.2.5 return add(outside_edges,I,f);
118 salcianu 1.1.2.1 }
119 salcianu 1.1.2.1
120 salcianu 1.1.2.1
121 salcianu 1.1.2.1 /** <code>join</code> is called in the control-flow join points. */
122 salcianu 1.1.2.1 public void join(EdgeOrdering eo2){
123 salcianu 1.1.2.1 after.union(eo2.after);
124 salcianu 1.1.2.1 }
125 salcianu 1.1.2.1
126 salcianu 1.1.2.2
127 salcianu 1.1.2.2 /** Visits all the entry of <code>this</code> edge ordering relation.
128 salcianu 1.1.2.2 In order not to add one more interface, a simple
129 salcianu 1.1.2.2 <code>RelationEntryVisitor</code> interface is used for the type
130 salcianu 1.1.2.5 of the argument <code>visitor</code>.
131 salcianu 1.1.2.5 For each outside edge <code>eo</code> and for each inside edge
132 salcianu 1.1.2.5 <code>ei</code> such that the information <i>eo can be read
133 salcianu 1.1.2.5 after ei was created</i> is recorded into <code>this</code> object,
134 salcianu 1.1.2.5 <code>visitor.visit(eo,ei)</code> is called. */
135 salcianu 1.1.2.2 public void forAllEntries(RelationEntryVisitor visitor){
136 salcianu 1.1.2.2 after.forAllEntries(visitor);
137 salcianu 1.1.2.2 }
138 salcianu 1.1.2.2
139 salcianu 1.1.2.2 /** Removes all the information related to edges containing nodes from
140 salcianu 1.1.2.2 <code>nodes</code>. */
141 salcianu 1.1.2.3 public void removeNodes(final Set nodes){
142 salcianu 1.1.2.3 after.removeObjects(new PredicateWrapper(){
143 salcianu 1.1.2.3 public boolean check(Object obj){
144 salcianu 1.1.2.5 return ((PAEdge) obj).isBad(nodes);
145 salcianu 1.1.2.3 }
146 salcianu 1.1.2.3 });
147 salcianu 1.1.2.2 }
148 salcianu 1.1.2.2
149 salcianu 1.1.2.3 /** Removes all the information related to edges from <code>edges</code>.
150 salcianu 1.1.2.3 <code>edges</code> must be a set of <code>PAEdge</code>s. */
151 salcianu 1.1.2.3 public void removeEdges(final Set edges){
152 salcianu 1.1.2.3 after.removeObjects(new PredicateWrapper(){
153 salcianu 1.1.2.3 public boolean check(Object obj){
154 salcianu 1.1.2.3 return edges.contains((PAEdge) obj);
155 salcianu 1.1.2.3 }
156 salcianu 1.1.2.3 });
157 salcianu 1.1.2.2 }
158 salcianu 1.1.2.1
159 salcianu 1.1.2.1 // Private constructor for clone and keepTheEssential.
160 salcianu 1.1.2.1 private EdgeOrdering(Relation after){
161 salcianu 1.1.2.1 this.after = after;
162 salcianu 1.1.2.1 }
163 salcianu 1.1.2.1
164 salcianu 1.1.2.1
165 salcianu 1.1.2.1 /** Clone this object. */
166 salcianu 1.1.2.1 public Object clone(){
167 salcianu 1.1.2.1 return new EdgeOrdering((Relation)after.clone());
168 salcianu 1.1.2.1 }
169 salcianu 1.1.2.1
170 salcianu 1.1.2.1
171 salcianu 1.1.2.1 /** Returns a new relation containing information only about the ordering
172 salcianu 1.1.2.1 of edges between nodes from <code>remaining_nodes</code>. */
173 salcianu 1.1.2.1 public EdgeOrdering keepTheEssential(final Set remaining_nodes){
174 salcianu 1.1.2.10 final Relation essence = new LightRelation();
175 salcianu 1.1.2.1 after.forAllEntries(new RelationEntryVisitor(){
176 salcianu 1.1.2.1 public void visit(Object o1, Object o2){
177 salcianu 1.1.2.1 PAEdge eo = (PAEdge) o1;
178 salcianu 1.1.2.1 PAEdge ei = (PAEdge) o2;
179 salcianu 1.1.2.5 if(ei.isGood(remaining_nodes) &&
180 salcianu 1.1.2.5 eo.isGood(remaining_nodes))
181 salcianu 1.1.2.1 essence.add(eo,ei);
182 salcianu 1.1.2.1 }
183 salcianu 1.1.2.1 });
184 salcianu 1.1.2.1 return new EdgeOrdering(essence);
185 salcianu 1.1.2.7 }
186 salcianu 1.1.2.7
187 salcianu 1.1.2.7
188 salcianu 1.1.2.7 public static void insertProjection(final EdgeOrdering eo_source,
189 salcianu 1.1.2.8 final EdgeOrdering eo_dest,
190 salcianu 1.1.2.8 final Relation mu){
191 salcianu 1.1.2.7
192 salcianu 1.1.2.7 eo_source.forAllEntries(new RelationEntryVisitor(){
193 salcianu 1.1.2.7 public void visit(Object key, Object value){
194 salcianu 1.1.2.7 PAEdge eo = (PAEdge) key;
195 salcianu 1.1.2.7 PAEdge ei = (PAEdge) value;
196 salcianu 1.1.2.7
197 salcianu 1.1.2.7 Set eo_set = eo.project(mu);
198 salcianu 1.1.2.7 Set ei_set = ei.project(mu);
199 salcianu 1.1.2.7
200 salcianu 1.1.2.7 if(ei_set.isEmpty() || eo_set.isEmpty()) return;
201 salcianu 1.1.2.7
202 cananian 1.3 for (Object new_eoO : eo_set){
203 cananian 1.3 PAEdge new_eo = (PAEdge) new_eoO;
204 cananian 1.3 for (Object new_eiO : ei_set){
205 cananian 1.3 PAEdge new_ei = (PAEdge) new_eiO;
206 salcianu 1.1.2.7 eo_dest.add(new_eo,new_ei);
207 salcianu 1.1.2.7 }
208 salcianu 1.1.2.7 }
209 salcianu 1.1.2.7 }
210 salcianu 1.1.2.7 });
211 salcianu 1.1.2.8 }
212 salcianu 1.1.2.8
213 salcianu 1.1.2.8 /* Specializes <code>this</code> edge ordering by mapping
214 salcianu 1.1.2.8 the nodes appearing in the edges according to <code>map</code>.
215 salcianu 1.1.2.8 The nodes which are not explicitly mapped, are considered
216 salcianu 1.1.2.8 to be mapped to themselves (identity mapping). */
217 salcianu 1.1.2.8 public EdgeOrdering specialize(final Map map){
218 salcianu 1.1.2.8 final EdgeOrdering eord2 = new EdgeOrdering();
219 salcianu 1.1.2.8
220 salcianu 1.1.2.8 forAllEntries(new RelationEntryVisitor(){
221 salcianu 1.1.2.8 public void visit(Object key, Object value){
222 salcianu 1.1.2.8 PAEdge eo = (PAEdge) key;
223 salcianu 1.1.2.8 PAEdge ei = (PAEdge) value;
224 salcianu 1.1.2.8 PAEdge eo2 = eo.specialize(map);
225 salcianu 1.1.2.8 PAEdge ei2 = ei.specialize(map);
226 salcianu 1.1.2.8 eord2.add(eo2,ei2);
227 salcianu 1.1.2.8 }
228 salcianu 1.1.2.8 });
229 salcianu 1.1.2.8
230 salcianu 1.1.2.8 return eord2;
231 salcianu 1.1.2.1 }
232 salcianu 1.1.2.1
233 salcianu 1.1.2.1 /** Checks the equality of two <code>NodeOrdering</code> objects. */
234 salcianu 1.1.2.1 public boolean equals(Object o2){
235 salcianu 1.1.2.1 EdgeOrdering no2 = (EdgeOrdering) o2;
236 salcianu 1.1.2.1 if(this==no2) return true;
237 salcianu 1.1.2.1 return this.after.equals(no2.after);
238 salcianu 1.1.2.1 }
239 salcianu 1.1.2.1
240 salcianu 1.1.2.1 /** String representation for debug purposes. */
241 salcianu 1.1.2.1 public String toString(){
242 salcianu 1.1.2.1 final StringBuffer buffer = new StringBuffer();
243 salcianu 1.1.2.1 buffer.append(" Edge ordering:\n");
244 salcianu 1.1.2.1 after.forAllEntries(new RelationEntryVisitor(){
245 salcianu 1.1.2.1 public void visit(Object o1, Object o2){
246 salcianu 1.1.2.1 PAEdge eo = (PAEdge) o1;
247 salcianu 1.1.2.1 PAEdge ei = (PAEdge) o2;
248 salcianu 1.1.2.1 buffer.append(" ");
249 salcianu 1.1.2.1 buffer.append(eo.toString());
250 salcianu 1.1.2.1 buffer.append(" after ");
251 salcianu 1.1.2.1 buffer.append(ei.toString());
252 salcianu 1.1.2.1 buffer.append("\n");
253 salcianu 1.1.2.1 }
254 salcianu 1.1.2.1 });
255 salcianu 1.1.2.1 return buffer.toString();
256 salcianu 1.1.2.1 }
257 salcianu 1.1.2.1
258 salcianu 1.1.2.1 }
259 salcianu 1.1.2.1
260 cananian 1.2