1
2
3
4
5
6
7 package joeq.Compiler.Analysis.IPA;
8
9 import java.io.BufferedReader;
10 import java.io.BufferedWriter;
11 import java.io.File;
12 import java.io.FileReader;
13 import java.io.FileWriter;
14 import java.io.IOException;
15 import java.util.Collection;
16 import java.util.Collections;
17 import java.util.HashMap;
18 import java.util.HashSet;
19 import java.util.Iterator;
20 import java.util.LinkedList;
21 import java.util.NoSuchElementException;
22 import java.util.Set;
23 import java.util.StringTokenizer;
24 import jwutil.graphs.DominanceFrontier;
25 import jwutil.graphs.Dominators;
26 import jwutil.graphs.Navigator;
27
28 /***
29 * @author V.Benjamin Livshits
30 *
31 */
32 public class ObjectNamingSupport {
33 private AnnotatedDirectedGraph g;
34 private static final Object HEAD = "HEAD";
35 private HashMap names = new HashMap();
36 private Set sources = new HashSet();
37 private static final boolean SHOW_PRED = false;
38 private Set frontierNodes = new HashSet();
39 private Dominators dominators;
40 private DominanceFrontier df;
41 private static String DIR = "";
42 private boolean TRACE = false;
43
44 public static void main(String[] args) {
45 if(args.length > 0){
46 DIR = args[0];
47 if(!DIR.endsWith(File.separator)){
48 DIR += File.separator;
49 }
50 System.out.println("Using directory " + DIR);
51 }
52
53 ObjectNamingSupport md = new ObjectNamingSupport();
54 md.run();
55 }
56
57 private void run() {
58 try {
59 readGraph(DIR + "flows.tuples");
60 readNames(DIR + "heap2.map");
61 String firstLine = readSources(DIR + "source_h2.tuples");
62
63
64
65
66 dominators = new Dominators(true, HEAD, g.getNavigator());
67 df = new DominanceFrontier(HEAD, g.getNavigator(), dominators);
68 printDF(df);
69 dumpFrontierNodes(DIR + "frontier.tuples", firstLine);
70 }catch(IOException e){
71 System.err.println(e.getMessage());
72 }
73 }
74
75 private void dumpFrontierNodes(String frontierFile, String firstLine) {
76 System.out.println("DF set: " + frontierNodes);
77 try {
78 BufferedWriter bw = new BufferedWriter(new FileWriter(frontierFile));
79 bw.write(firstLine);
80 bw.write("\n");
81
82 for(Iterator iter = frontierNodes.iterator(); iter.hasNext();){
83 String n = (String) iter.next();
84 bw.write(n + "\n");
85 }
86 bw.close();
87 }catch(IOException e){
88 System.err.println(e.getMessage());
89 }
90 }
91
92 private void printDF(DominanceFrontier df) {
93
94 for(Iterator iter = sources.iterator(); iter.hasNext();){
95 String node = (String) iter.next();
96 if(g.containsNode(node)){
97 Set frontier = df.getIteratedDominanceFrontier(node);
98
99 if(TRACE) System.out.println("Source " + names.get(node) + "(" + node + ")");
100 if(TRACE) System.out.println("Frontier of " + names.get(node));
101
102 for(Iterator frontierIter = frontier.iterator(); frontierIter.hasNext();){
103 String n = (String) frontierIter.next();
104 if(!predDominatedBySources(n)){
105 if(TRACE) System.out.println("\t\t" + names.get(n) +
106 "(" + n + ") " + g.getPredsOf(n).size());
107
108 frontierNodes.add(n);
109
110 if(SHOW_PRED){
111 for(Iterator predIter = g.getPredsOf(n).iterator(); predIter.hasNext();){
112 String pred = (String) predIter.next();
113 String annote = g.getEdgeAnnote(pred, n);
114
115 if(!isDominatedBySources(pred)){
116 if(TRACE) System.out.println("\t\t\t" + pred + ": " + names.get(pred) + ", " + annote);
117 }else{
118 if(TRACE) System.out.println("\t\t\t+" + pred + ": " + names.get(pred) + ", " + annote);
119 }
120 }
121 }
122 }
123 }
124 }else{
125 if(TRACE) System.out.println("Source " + " is missing from the graph.");
126 }
127 }
128 }
129
130 private boolean predDominatedBySources(Object gode) {
131 for(Iterator predIter = g.getPredsOf(gode).iterator(); predIter.hasNext();){
132 String pred = (String) predIter.next();
133
134 if(!isDominatedBySources(pred)){
135 return false;
136 }
137 }
138
139 return true;
140 }
141
142 boolean isDominatedBySources(String node) {
143 for(Iterator sourceIter = sources.iterator(); sourceIter.hasNext();){
144 String source = (String) sourceIter.next();
145
146 if(dominators.inDominatees(source, node)){
147 return true;
148 }
149 }
150 return false;
151 }
152
153 void readGraph(String tuplesFile) throws IOException {
154 g = new AnnotatedDirectedGraph();
155 BufferedReader di = new BufferedReader(new FileReader(tuplesFile));
156 String line = di.readLine();
157 long lineCount = 0;
158 do {
159 if (!line.startsWith("#")) {
160 try {
161 StringTokenizer tok = new StringTokenizer(line);
162 String h2 = tok.nextToken();
163 String h1 = tok.nextToken();
164 String i = tok.nextToken();
165 String r = tok.nextToken();
166
167 if(!g.containsNode(h1)){
168 g.addNode(h1);
169 }
170 if(!g.containsNode(h2)){
171 g.addNode(h2);
172 }
173 g.addEdge(h1, h2, r);
174 } catch (NoSuchElementException e) {
175 line = di.readLine();
176 }
177 }
178 lineCount++;
179 } while ((line = di.readLine()) != null);
180 System.out.println("Read " + lineCount + " lines.");
181
182 for(Iterator iter = g.nodeIterator(); iter.hasNext();){
183 String node = (String) iter.next();
184
185 if(isEntry(node)){
186 g.addEntry(node);
187 if(sources.contains(node)){
188 System.out.println("Source " + node);
189 }else{
190
191 }
192 }
193 }
194
195 g.addNode(HEAD);
196 for(Iterator iter = g.getEntryIterator(); iter.hasNext();){
197 g.addEdge(HEAD, iter.next(), "initial");
198 }
199 di.close();
200 }
201
202 private boolean isEntry(String node) {
203 if(g.getPredsOf(node).isEmpty()){
204
205 return true;
206 }
207 if(g.getPredsOf(node).iterator().next().equals(node)){
208
209 return true;
210 }
211
212 return false;
213 }
214
215 void readNames(String namesFile) throws IOException {
216 BufferedReader di = new BufferedReader(new FileReader(namesFile));
217 int lineno = 0;
218 String line = di.readLine();
219
220 do {
221 names.put(new Integer(lineno++).toString(), line);
222 } while ((line = di.readLine()) != null);
223 System.out.println("Read " + names.size() + " names.");
224 }
225
226 String readSources(String namesFile) throws IOException {
227 BufferedReader di = new BufferedReader(new FileReader(namesFile));
228 String line = di.readLine();
229 String firstLine = null;
230
231 do {
232 if (!line.startsWith("#")) {
233 try {
234 StringTokenizer tok = new StringTokenizer(line);
235 String h = tok.nextToken();
236
237 sources.add(h);
238 }catch(NoSuchElementException e) {
239 line = di.readLine();
240 }
241 }else{
242 firstLine = line;
243 int idx = firstLine.indexOf("I0");
244 if(idx != -1){
245 firstLine = firstLine.substring(0, idx-1);
246 }
247 }
248
249 } while ((line = di.readLine()) != null);
250 System.out.println("Read " + sources.size() + " sources.");
251
252 return firstLine;
253 }
254 }
255
256 class AnnotatedDirectedGraph implements jwutil.graphs.Graph {
257 HashMap edgeAnnotes = new HashMap();
258 LinkedList entries = new LinkedList();
259 HashMap nextMap = new HashMap();
260 HashMap prevMap = new HashMap();
261 private Set nodeSet = new HashSet();
262
263 public void addEdge(Object from, Object to, String annote){
264 nodeSet.add(from); nodeSet.add(to);
265
266 Set toList = (Set) nextMap.get(from);
267 Set fromList = (Set) prevMap.get(to);
268
269 if(toList == null){
270 toList = new HashSet();
271 }
272 if(fromList == null){
273 fromList = new HashSet();
274 }
275 toList.add(to); fromList.add(from);
276
277 nextMap.put(from, toList);
278 prevMap.put(to, fromList);
279
280 edgeAnnotes.put(from.toString() + ":" + to.toString(), annote);
281
282 }
283
284 public Iterator nodeIterator() {
285 return nodeSet.iterator();
286 }
287
288 public boolean containsNode(String node) {
289 return nodeSet.contains(node);
290 }
291
292 public void addNode(Object n) {
293 nodeSet.add(n);
294 }
295
296 public String getEdgeAnnote(String from, Object to) {
297 return (String) edgeAnnotes.get(from.toString() + ":" + to.toString());
298 }
299
300 public void addEntry(Object node) {
301 entries.add(node);
302
303 }
304
305 public Iterator getEntryIterator() {
306 return entries.iterator();
307 }
308
309 public void printGraph() {
310 for (Iterator it = nodeSet.iterator(); it.hasNext();) {
311 Object node = it.next();
312 System.out.println("Node = " + node);
313 System.out.println("Preds:");
314 for (Iterator predsIt = getPredsOf(node).iterator(); predsIt.hasNext();) {
315 System.out.print(" ");
316 System.out.println(predsIt.next());
317 }
318 System.out.println("Succs:");
319 for (Iterator succsIt = getSuccsOf(node).iterator(); succsIt.hasNext();) {
320 System.out.print(" ");
321 System.out.println(succsIt.next());
322 }
323 }
324 }
325
326 public Collection getSuccsOf(Object node) {
327 Collection result = (Collection) nextMap.get(node);
328 if(result == null){
329 result = Collections.EMPTY_SET;
330 }
331
332 return result;
333 }
334
335 public Collection getPredsOf(Object node) {
336 Collection result = (Collection) prevMap.get(node);
337 if(result == null){
338 result = Collections.EMPTY_SET;
339 }
340
341 return result;
342 }
343
344
345
346
347 public Collection getRoots() {
348 return this.entries;
349 }
350
351
352
353
354 public Navigator getNavigator() {
355 return new Navigator(){
356 public Collection next(Object node) {
357 return getPredsOf(node);
358 }
359 public Collection prev(Object node) {
360 return getSuccsOf(node);
361 }
362 };
363 }
364 }