1 marinov 1.1 // Graph.java, created Thu Oct 15 20:22:46 1998 by marinov
2 cananian 1.2.2.6 // Copyright (C) 1998 Darko Marinov <marinov@lcs.mit.edu>
3 cananian 1.2.2.6 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 marinov 1.1 package harpoon.Util;
5 marinov 1.1
6 cananian 1.2.2.9 import harpoon.Analysis.ClassHierarchy;
7 cananian 1.2.2.5 import harpoon.ClassFile.HClass;
8 cananian 1.2.2.3 import harpoon.ClassFile.HCode;
9 cananian 1.2.2.3 import harpoon.ClassFile.HCodeEdge;
10 cananian 1.2.2.3 import harpoon.ClassFile.HCodeElement;
11 salcianu 1.2.2.13 import harpoon.ClassFile.HCodeFactory;
12 cananian 1.2.2.5 import harpoon.ClassFile.HMethod;
13 marinov 1.1 import harpoon.Analysis.DomTree;
14 marinov 1.1 import harpoon.Analysis.DomFrontier;
15 cananian 1.2.2.10 import harpoon.IR.Properties.CFGraphable;
16 salcianu 1.2.2.13 import harpoon.IR.Quads.Quad;
17 salcianu 1.2.2.13 import harpoon.IR.Quads.CALL;
18 salcianu 1.2.2.13 import harpoon.IR.Quads.HANDLER;
19 salcianu 1.2.2.13 import harpoon.IR.Quads.METHOD;
20 salcianu 1.2.2.13 import harpoon.IR.Quads.HEADER;
21 salcianu 1.2.2.13 import harpoon.IR.Quads.FOOTER;
22 salcianu 1.2.2.13
23 salcianu 1.2.2.13
24 salcianu 1.2.2.13 import harpoon.Util.LightBasicBlocks.LightBasicBlock;
25 salcianu 1.2.2.13 import harpoon.Util.LightBasicBlocks.LBBConverter;
26 salcianu 1.2.2.13 import harpoon.Util.BasicBlocks.BBConverter;
27 salcianu 1.2.2.13
28 salcianu 1.2.2.13 import harpoon.Temp.Temp;
29 salcianu 1.2.2.13
30 marinov 1.1 import java.util.Enumeration;
31 cananian 1.2.2.7 import java.util.Iterator;
32 salcianu 1.2.2.13 import java.util.Set;
33 salcianu 1.2.2.13 import java.util.HashSet;
34 salcianu 1.2.2.13 import java.util.Map;
35 salcianu 1.2.2.13 import java.util.HashMap;
36 salcianu 1.2.2.13
37 salcianu 1.2.2.13 import java.io.PrintWriter;
38 salcianu 1.2.2.13
39 salcianu 1.2.2.13
40 marinov 1.1 /**
41 marinov 1.1 * <code>Graph</code>
42 marinov 1.1 *
43 marinov 1.1 * @author Darko Marinov <marinov@lcs.mit.edu>
44 cananian 1.6 * @version $Id: Graph.java,v 1.6 2004/02/08 03:21:41 cananian Exp $
45 marinov 1.1 */
46 marinov 1.1
47 marinov 1.2 public abstract class Graph {
48 marinov 1.1
49 marinov 1.2 /** Print (vcg format) control from graph representing code view. Use default style. */
50 marinov 1.2 public static final void printCFG(HCode hc, java.io.PrintWriter pw, String title) {
51 marinov 1.2 printCFG(hc,pw,title,null);
52 marinov 1.2 }
53 marinov 1.2
54 marinov 1.2 /** Print (vcg format) DomTree of code view. Use default style. */
55 marinov 1.2 public static final void printDomTree(HCode hc, java.io.PrintWriter pw, String title) {
56 marinov 1.2 printDomTree(false,hc,pw,title,null);
57 marinov 1.2 }
58 marinov 1.2
59 marinov 1.2 /** Print (vcg format) (Post)DomTree of code view. Use default style. */
60 marinov 1.2 public static final void printDomTree(boolean isPost, HCode hc, java.io.PrintWriter pw, String title) {
61 marinov 1.2 printDomTree(isPost,hc,pw,title,null);
62 marinov 1.2 }
63 marinov 1.2
64 marinov 1.2 /** Print (vcg format) control flow graph representing code view. */
65 marinov 1.2 public static final void printCFG(HCode hc, java.io.PrintWriter pw, String title, String[] setup) {
66 marinov 1.2 commonHeader(hc, pw, title, setup, "CFG");
67 cananian 1.2.2.10 // control flow graph. The HCodeElements better implement CFGraphable
68 cananian 1.5 for (Iterator e = hc.getElementsI(); e.hasNext(); ) {
69 cananian 1.5 HCodeElement hce = (HCodeElement) e.next();
70 cananian 1.2.2.10 HCodeEdge[] next = ((CFGraphable)hce).succ();
71 marinov 1.2 for (int j=0; j<next.length; j++) {
72 marinov 1.2 String label;
73 marinov 1.2 if (next.length==1)
74 marinov 1.2 label = null;
75 marinov 1.2 else if (next.length==2)
76 marinov 1.2 label = (j==0)?"false":"true";
77 marinov 1.2 else
78 marinov 1.2 label = Integer.toString(j);
79 cananian 1.2.2.8 // also print which_pred of edge, for QuadSSI.
80 cananian 1.2.2.2 if (next[j] instanceof harpoon.IR.Quads.Edge &&
81 cananian 1.2.2.10 ((CFGraphable)next[j].to()).pred().length > 1)
82 cananian 1.2.2.1 label = ((label==null)?"":label) + "[" +
83 cananian 1.2.2.2 ((harpoon.IR.Quads.Edge)next[j]).which_pred() +
84 cananian 1.2.2.1 "]";
85 marinov 1.2 pw.println(edgeString(next[j].from(), next[j].to(),
86 marinov 1.2 label));
87 marinov 1.2 }
88 marinov 1.2 }
89 marinov 1.2 commonFooter(pw);
90 marinov 1.2 }
91 marinov 1.2
92 marinov 1.2 /** Print (vcg format) of DomTree. */
93 marinov 1.2 public static final void printDomTree(HCode hc, java.io.PrintWriter pw, String title, String[] setup) {
94 marinov 1.2 printDomTree(false,hc,pw,title,setup);
95 marinov 1.2 }
96 marinov 1.2
97 marinov 1.2 /** Print (vcg format) of (Post)DomTree. */
98 marinov 1.2 public static final void printDomTree(boolean isPost, HCode hc, java.io.PrintWriter pw, String title, String[] setup) {
99 marinov 1.2 commonHeader(hc, pw, title, setup, "DomTree");
100 cananian 1.2.2.12 DomTree dt = new DomTree(hc, isPost);
101 marinov 1.2 DomFrontier df = new DomFrontier(dt);
102 cananian 1.5 for (Iterator e = hc.getElementsI(); e.hasNext(); ) {
103 cananian 1.5 HCodeElement hce = (HCodeElement) e.next();
104 cananian 1.2.2.12 HCodeElement idom = dt.idom(hce);
105 marinov 1.2 // make dominance frontier label.
106 marinov 1.2 StringBuffer sb = new StringBuffer("DF[");
107 marinov 1.2 sb.append(hce.getID()); sb.append("]={");
108 cananian 1.2.2.12 for (Iterator it2=df.dfS(hce).iterator(); it2.hasNext(); ) {
109 cananian 1.2.2.12 sb.append(((HCodeElement)it2.next()).getID());
110 cananian 1.2.2.12 if (it2.hasNext())
111 marinov 1.2 sb.append(",");
112 marinov 1.2 }
113 marinov 1.2 sb.append("}");
114 marinov 1.2 if (idom!=null)
115 marinov 1.2 pw.println(edgeString(idom, hce,
116 marinov 1.2 sb.toString()));
117 marinov 1.2 }
118 marinov 1.2 commonFooter(pw);
119 marinov 1.1 }
120 marinov 1.1
121 cananian 1.2.2.5 public static final void printClassHierarchy(java.io.PrintWriter pw, HMethod root, ClassHierarchy ch) {
122 cananian 1.2.2.5 pw.println("graph: {");
123 cananian 1.2.2.5 pw.println(" title: \"Class Hierarchy: "+root+"\"");
124 cananian 1.2.2.5 pw.println(" x: 30");
125 cananian 1.2.2.5 pw.println(" y: 30");
126 cananian 1.2.2.5 pw.println(" height: 800");
127 cananian 1.2.2.5 pw.println(" width: 500");
128 cananian 1.2.2.5 pw.println(" stretch: 60");
129 cananian 1.2.2.5 pw.println(" shrink: 100");
130 cananian 1.2.2.5 pw.println(" display_edge_labels: no");
131 cananian 1.2.2.5 pw.println(" dirty_edge_labels: no");
132 cananian 1.2.2.5 pw.println(" near_edges: no");
133 cananian 1.2.2.5 pw.println(" orientation: left_to_right");
134 cananian 1.2.2.5 pw.println(" layoutalgorithm: minbackward");
135 cananian 1.2.2.5 pw.println(" port_sharing: no");
136 cananian 1.2.2.5 pw.println(" arrowmode: free");
137 cananian 1.6 for (Object cO : ch.classes()) {
138 cananian 1.6 HClass c = (HClass) cO;
139 cananian 1.2.2.5 pw.print(" node: { ");
140 cananian 1.2.2.5 pw.print("title:\""+c.getName()+"\" ");
141 cananian 1.2.2.5 pw.print("label:\""+c.getName()+ "\" ");
142 cananian 1.2.2.5 pw.print("shape: box ");
143 cananian 1.2.2.5 pw.println("}");
144 cananian 1.2.2.5 }
145 cananian 1.6 for (Object cO : ch.classes()) {
146 cananian 1.6 HClass c = (HClass) cO;
147 cananian 1.2.2.5 HClass sc= c.getSuperclass();
148 cananian 1.2.2.5 if (sc!=null)
149 cananian 1.2.2.5 pw.println(" edge: { " +
150 cananian 1.2.2.5 "sourcename: \""+sc.getName()+"\" " +
151 cananian 1.2.2.5 "targetname: \""+ c.getName()+"\" " +
152 cananian 1.2.2.5 "}");
153 cananian 1.2.2.5 HClass[] in=c.getInterfaces();
154 cananian 1.2.2.5 for (int i=0; i<in.length; i++)
155 cananian 1.2.2.5 pw.println(" edge: { " +
156 cananian 1.2.2.5 "sourcename: \""+in[i].getName()+"\" " +
157 cananian 1.2.2.5 "targetname: \""+ c.getName()+"\" " +
158 cananian 1.2.2.5 "}");
159 cananian 1.2.2.5 }
160 cananian 1.2.2.5 pw.println("}");
161 marinov 1.1 }
162 marinov 1.1
163 marinov 1.2 /** Print common header of (vcg format) graphs for CFG and (Post)DomTree. */
164 marinov 1.2 private static void commonHeader(HCode hc, java.io.PrintWriter pw, String title, String[] setup, String type) {
165 marinov 1.1 pw.println("graph: {");
166 marinov 1.1 pw.println("title: \""+title+"/"+hc.getName()+"\"");
167 marinov 1.1 if (setup==null) {
168 cananian 1.2.2.11 String[] defaultSetup = { "x: 30", "y: 30", "yspace: 15",
169 marinov 1.1 "height: 800", "width: 500",
170 marinov 1.1 "stretch: 60", "shrink: 100",
171 marinov 1.1 "display_edge_labels: yes",
172 marinov 1.1 "dirty_edge_labels: yes",
173 marinov 1.1 "near_edges: no"
174 marinov 1.1 };
175 marinov 1.1 setup = defaultSetup;
176 marinov 1.1 }
177 marinov 1.1 for (int i=0; i<setup.length; i++)
178 marinov 1.1 pw.println(setup[i]);
179 marinov 1.2 pw.println((type!="CFG") ? "layoutalgorithm: tree" : "priority_phase: yes");
180 cananian 1.5 for (Iterator e = hc.getElementsI(); e.hasNext(); ) {
181 cananian 1.5 HCodeElement hce = (HCodeElement) e.next();
182 marinov 1.1 String label = "#" + hce.getID() + ": " + escape(hce.toString());
183 marinov 1.1 pw.print("node: { ");
184 marinov 1.1 pw.print("title:\""+hce.getID()+"\" ");
185 marinov 1.1 pw.print("label:\"" + label + "\" ");
186 marinov 1.1 pw.print("shape: box ");
187 marinov 1.1 pw.println("}");
188 marinov 1.1 }
189 marinov 1.2
190 marinov 1.2 }
191 marinov 1.2
192 marinov 1.2 private static void commonFooter (java.io.PrintWriter pw) {
193 marinov 1.1 pw.println("}");
194 marinov 1.1 }
195 marinov 1.1
196 marinov 1.1 private static String edgeString(HCodeElement from, HCodeElement to, String label)
197 marinov 1.1 {
198 marinov 1.1 return "edge: { " +
199 marinov 1.1 "sourcename: \""+from.getID()+"\" " +
200 marinov 1.1 "targetname: \""+to.getID()+"\" " +
201 marinov 1.1 ( (label==null)?"":("label: \""+label+"\" ") ) +
202 marinov 1.1 "}";
203 marinov 1.1 }
204 marinov 1.1
205 marinov 1.1 private static String escape(String s) {
206 marinov 1.1 s = Util.escape(s);
207 marinov 1.1 return s.replace('\"', ' ');
208 salcianu 1.2.2.13 }
209 salcianu 1.2.2.13
210 salcianu 1.2.2.13
211 salcianu 1.2.2.13
212 salcianu 1.2.2.13
213 salcianu 1.2.2.13 /** Print the Control Flow Graph of the Basic Blocks composing
214 salcianu 1.2.2.13 the code of method <code>hm</code>, as constructed by the
215 salcianu 1.2.2.13 code factory <code>hcf</code>. The output is written to
216 salcianu 1.2.2.13 <code>out</code> in VCG format. */
217 salcianu 1.2.2.13 public static void printBBCFG(HMethod hm, HCodeFactory hcf,
218 salcianu 1.2.2.13 PrintWriter out) {
219 salcianu 1.2.2.13 BBConverter bbconv = new BBConverter(hcf);
220 salcianu 1.2.2.13 LBBConverter lbbconv = new LBBConverter(bbconv);
221 salcianu 1.2.2.13 printBBCFG(hm, lbbconv, out);
222 salcianu 1.2.2.13 }
223 salcianu 1.2.2.13
224 salcianu 1.2.2.13 /** Print the Control Flow Graph of the Basic Blocks composing
225 salcianu 1.2.2.13 the code of method <code>hm</code>, as constructed by the
226 salcianu 1.2.2.13 <code>LBBConverter</code> <code>hcf</code>.
227 salcianu 1.2.2.13 The output is written to <code>out</code> in VCG format. */
228 salcianu 1.2.2.13 public static void printBBCFG(HMethod hm, LBBConverter lbbconv,
229 salcianu 1.2.2.13 PrintWriter out) {
230 salcianu 1.2.2.13 LightBasicBlock.Factory lbbfact = lbbconv.convert2lbb(hm);
231 salcianu 1.2.2.13
232 salcianu 1.2.2.13 print_VCG_header(out, "BB_CFG for " + hm.getName());
233 salcianu 1.2.2.13 Map map = print_VCG_nodes(out, lbbfact);
234 salcianu 1.2.2.13 print_VCG_edges(out, lbbfact, map);
235 salcianu 1.2.2.13 print_VCG_footer(out);
236 salcianu 1.2.2.13 }
237 salcianu 1.2.2.13
238 salcianu 1.2.2.13 private static void print_VCG_header(PrintWriter out, String graph_name) {
239 salcianu 1.2.2.13 out.println("graph: {");
240 salcianu 1.2.2.13 out.println("\ttitle: \"" + graph_name + "\"");
241 salcianu 1.2.2.13 out.println("\tlayoutalgorithm: maxdepthslow");
242 salcianu 1.2.2.13 out.println("\tdisplay_edge_labels: yes");
243 salcianu 1.2.2.13 }
244 salcianu 1.2.2.13
245 salcianu 1.2.2.13 private static Map print_VCG_nodes
246 salcianu 1.2.2.13 (PrintWriter out, LightBasicBlock.Factory lbbfact) {
247 salcianu 1.2.2.13 out.println("\n/* (light) basic block description */");
248 salcianu 1.2.2.13 Map map = new HashMap();
249 salcianu 1.2.2.13 LightBasicBlock lbbs[] = lbbfact.getAllBBs();
250 salcianu 1.2.2.13 for(int i = 0; i < lbbs.length ; i++) {
251 salcianu 1.2.2.13 String lbb_name = Integer.toString(i);
252 salcianu 1.2.2.13 map.put(lbbs[i], lbb_name);
253 salcianu 1.2.2.13 print_VCG_node(out, lbbs[i], lbb_name);
254 salcianu 1.2.2.13 }
255 salcianu 1.2.2.13 out.println();
256 salcianu 1.2.2.13 return map;
257 salcianu 1.2.2.13 }
258 salcianu 1.2.2.13
259 salcianu 1.2.2.13 private static void print_VCG_node
260 salcianu 1.2.2.13 (PrintWriter out, LightBasicBlock lbb, String lbb_name) {
261 salcianu 1.2.2.13 out.println("node: {");
262 salcianu 1.2.2.13 out.println("\ttitle: \"" + lbb_name + "\"");
263 salcianu 1.2.2.13 out.print("\tlabel: \"");
264 salcianu 1.2.2.13 HCodeElement quads[] = lbb.getElements();
265 salcianu 1.2.2.13 for(int i = 0; i < quads.length; i++)
266 salcianu 1.2.2.13 out.print( ((i == 0) ? "" : "\\n") +
267 salcianu 1.2.2.13 quad2string(quads[i]) );
268 salcianu 1.2.2.13 out.println("\"");
269 salcianu 1.2.2.13 out.println("}");
270 salcianu 1.2.2.13 }
271 salcianu 1.2.2.13
272 salcianu 1.2.2.13 private static String quad2string(HCodeElement hce) {
273 salcianu 1.2.2.13 if(!(hce instanceof CALL))
274 salcianu 1.2.2.14 return Util.adjust_quotes(hce.toString());
275 salcianu 1.2.2.13 CALL call = (CALL) hce;
276 salcianu 1.2.2.13 StringBuffer buff = new StringBuffer();
277 salcianu 1.2.2.13 if(call.retval() != null) {
278 salcianu 1.2.2.13 buff.append(call.retval());
279 salcianu 1.2.2.13 buff.append(" = ");
280 salcianu 1.2.2.13 }
281 salcianu 1.2.2.13 if(call.isStatic())
282 salcianu 1.2.2.13 buff.append("(static) ");
283 salcianu 1.2.2.13 buff.append("CALL ");
284 salcianu 1.2.2.13 HMethod hm = call.method();
285 salcianu 1.2.2.13
286 salcianu 1.2.2.13 String classname = hm.getDeclaringClass().getName();
287 salcianu 1.2.2.13 classname = classname.substring(classname.lastIndexOf(".") + 1);
288 salcianu 1.2.2.13 buff.append(classname);
289 salcianu 1.2.2.13
290 salcianu 1.2.2.13 buff.append(".");
291 salcianu 1.2.2.13 buff.append(hm.getName());
292 salcianu 1.2.2.13 buff.append("(");
293 salcianu 1.2.2.13 Temp params[] = call.params();
294 salcianu 1.2.2.13 for(int i = 0; i < params.length; i++)
295 salcianu 1.2.2.13 buff.append(((i == 0) ? "" : ",") + params[i]);
296 salcianu 1.2.2.13 buff.append(")");
297 salcianu 1.2.2.14 return Util.adjust_quotes(buff.toString());
298 salcianu 1.2.2.13 }
299 salcianu 1.2.2.13
300 salcianu 1.2.2.13 private static void print_VCG_edges
301 salcianu 1.2.2.13 (PrintWriter out, LightBasicBlock.Factory lbbfact, Map map) {
302 salcianu 1.2.2.13 out.println("\n/* control flow edges */");
303 salcianu 1.2.2.13
304 salcianu 1.2.2.13 METHOD method = get_METHOD(lbbfact);
305 salcianu 1.2.2.13
306 salcianu 1.2.2.13 LightBasicBlock lbbs[] = lbbfact.getAllBBs();
307 salcianu 1.2.2.13 for(int i = 0; i < lbbs.length; i++) {
308 salcianu 1.2.2.13 LightBasicBlock lbb = lbbs[i];
309 salcianu 1.2.2.13 String sourcename = (String) map.get(lbb);
310 salcianu 1.2.2.13
311 salcianu 1.2.2.13 LightBasicBlock next[] = lbb.getNextLBBs();
312 salcianu 1.2.2.13 for(int j = 0; j < next.length; j++) {
313 salcianu 1.2.2.13 String targetname = (String) map.get(next[j]);
314 salcianu 1.2.2.13 out.println("edge: { " +
315 salcianu 1.2.2.13 "sourcename : \"" + sourcename + "\" " +
316 salcianu 1.2.2.13 "targetname : \"" + targetname + "\" " +
317 salcianu 1.2.2.13 ((j >= lbb.getHandlerStartIndex()) ?
318 salcianu 1.4 "linestyle : dotted " : "" ) +
319 salcianu 1.2.2.13 "}");
320 salcianu 1.2.2.13 }
321 salcianu 1.2.2.13 }
322 salcianu 1.2.2.13 }
323 salcianu 1.2.2.13
324 salcianu 1.2.2.13 private static METHOD get_METHOD(LightBasicBlock.Factory lbbfact) {
325 salcianu 1.2.2.13 LightBasicBlock root = lbbfact.getRoot();
326 salcianu 1.2.2.13 HEADER header = (HEADER) root.getFirstElement();
327 salcianu 1.2.2.13 return (METHOD) header.next(1);
328 salcianu 1.2.2.13 }
329 salcianu 1.2.2.13
330 salcianu 1.2.2.13 private static void print_VCG_footer(PrintWriter out) {
331 salcianu 1.2.2.13 out.println("}");
332 marinov 1.1 }
333 marinov 1.1
334 marinov 1.1 }