KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > toolkits > graph > BlockGraphConverter


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 2003 Navindra Umanee <navindra@cs.mcgill.ca>
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Lesser General Public
6  * License as published by the Free Software Foundation; either
7  * version 2.1 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12  * Lesser General Public License for more details.
13  *
14  * You should have received a copy of the GNU Lesser General Public
15  * License along with this library; if not, write to the
16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17  * Boston, MA 02111-1307, USA.
18  */
19
20 package soot.toolkits.graph;
21
22 import soot.*;
23 import soot.toolkits.graph.*;
24 import soot.util.*;
25 import java.util.*;
26
27 /**
28  * This utility class can convert any BlockGraph to a single-headed
29  * and single-tailed graph by inserting appropriate Start or Stop
30  * nodes. It can also fully reverse the graph, something that might
31  * be useful e.g. when computing control dependences with a dominators
32  * algorithm.
33  *
34  * <p>
35  * Note: This class may be retracted in a future release when a suitable
36  * replacement becomes available.
37  * </p>
38  *
39  * @author Navindra Umanee
40  **/
41 public class BlockGraphConverter
42 {
43     /**
44      * Transforms a multi-headed and/or multi-tailed BlockGraph to a
45      * single-headed singled-tailed BlockGraph by inserting a dummy
46      * start and stop nodes.
47      **/
48     public static void addStartStopNodesTo(BlockGraph graph)
49     {
50         ADDSTART:
51         {
52             List heads = graph.getHeads();
53
54             if(heads.size() == 0)
55                 break ADDSTART;
56             
57             if((heads.size() == 1) && (heads.get(0) instanceof DummyBlock))
58                 break ADDSTART;
59
60             List blocks = graph.getBlocks();
61             DummyBlock head = new DummyBlock(graph.getBody(), 0);
62             head.makeHeadBlock(heads);
63
64             graph.mHeads = new SingletonList(head);
65             
66             {
67                 Iterator blocksIt = blocks.iterator();
68                 while(blocksIt.hasNext()){
69                     Block block = (Block) blocksIt.next();
70                     block.setIndexInMethod(block.getIndexInMethod() + 1);
71                 }
72             }
73             
74         List newBlocks = new ArrayList();
75         newBlocks.add(head);
76         newBlocks.addAll(blocks);
77             graph.mBlocks = newBlocks;
78         }
79
80         ADDSTOP:
81         {
82             List tails = graph.getTails();
83
84             if(tails.size() == 0)
85                 break ADDSTOP;
86             
87             if((tails.size() == 1) && (tails.get(0) instanceof DummyBlock))
88                 break ADDSTOP;
89
90             List blocks = graph.getBlocks();
91             DummyBlock tail = new DummyBlock(graph.getBody(), blocks.size());
92             tail.makeTailBlock(tails);
93
94             graph.mTails = new SingletonList(tail);
95
96             blocks.add(tail);
97         }
98     }
99
100     /**
101      * Reverses a BlockGraph by making the heads tails, the tails
102      * heads and reversing the edges. It does not change the ordering
103      * of Units in individual blocks, nor does it change the Block
104      * labels. This utility could be useful when calculating control
105      * dependences with a dominators algorithm.
106      **/
107     public static void reverse(BlockGraph graph)
108     {
109         // Issue: Do we change indexInMethod? No...
110 // Issue: Do we reverse the Units list in the Block?
111 // Issue: Do we need to implement an equals method in Block?
112 // When are two Blocks from two different BlockGraphs
113 // equal?
114
115         for(Iterator blocksIt = graph.getBlocks().iterator(); blocksIt.hasNext();){
116             Block block = (Block) blocksIt.next();
117             List succs = block.getSuccs();
118             List preds = block.getPreds();
119             block.setSuccs(preds);
120             block.setPreds(succs);
121         }
122
123         List heads = graph.getHeads();
124         List tails = graph.getTails();
125
126         graph.mHeads = new ArrayList(tails);
127         graph.mTails = new ArrayList(heads);
128     }
129
130     public static void main(String JavaDoc[] args)
131     {
132         // assumes 2 args: Class + Method
133
134         Scene.v().loadClassAndSupport(args[0]);
135         SootClass sc = Scene.v().getSootClass(args[0]);
136         SootMethod sm = sc.getMethod(args[1]);
137         Body b = sm.retrieveActiveBody();
138         CompleteBlockGraph cfg = new CompleteBlockGraph(b);
139         System.out.println(cfg);
140         BlockGraphConverter.addStartStopNodesTo(cfg);
141         System.out.println(cfg);
142         BlockGraphConverter.reverse(cfg);
143         System.out.println(cfg);
144     }
145     
146 }
147
148 /**
149  * Represents Start or Stop node in the graph.
150  *
151  * @author Navindra Umanee
152  **/
153 class DummyBlock extends Block
154 {
155     DummyBlock(Body body, int indexInMethod)
156     {
157         super(null, null, body, indexInMethod, 0, null);
158     }
159
160     void makeHeadBlock(List oldHeads)
161     {
162         setPreds(new ArrayList());
163         setSuccs(new ArrayList(oldHeads));
164
165         Iterator headsIt = oldHeads.iterator();
166         while(headsIt.hasNext()){
167             Block oldHead = (Block) headsIt.next();
168
169             List newPreds = new ArrayList();
170             newPreds.add(this);
171
172             List oldPreds = oldHead.getPreds();
173             if(oldPreds != null)
174                 newPreds.addAll(oldPreds);
175             
176             oldHead.setPreds(newPreds);
177         }
178     }
179
180     void makeTailBlock(List oldTails)
181     {
182         setSuccs(new ArrayList());
183         setPreds(new ArrayList(oldTails));
184
185         Iterator tailsIt = oldTails.iterator();
186         while(tailsIt.hasNext()){
187             Block oldTail = (Block) tailsIt.next();
188
189             List newSuccs = new ArrayList();
190             newSuccs.add(this);
191
192             List oldSuccs = oldTail.getSuccs();
193             if(oldSuccs != null)
194                 newSuccs.addAll(oldSuccs);
195
196             oldTail.setSuccs(newSuccs);
197         }
198     }
199
200     public Iterator iterator()
201     {
202         return Collections.EMPTY_LIST.iterator();
203     }
204 }
205
Popular Tags