|
1
19
20 package soot.shimple.toolkits.graph;
21
22 import soot.*;
23 import soot.jimple.*;
24 import soot.util.*;
25 import soot.shimple.*;
26 import soot.toolkits.graph.*;
27 import java.util.*;
28 import soot.shimple.toolkits.graph.ValueGraph.Node;
29
30 public class SimpleGlobalValueNumberer implements GlobalValueNumberer
31 {
32 protected BlockGraph cfg;
33 protected ValueGraph vg;
34 protected Set partitions;
35 protected Map nodeToPartition;
36
37 protected int currentPartitionNumber;
38
39 public SimpleGlobalValueNumberer(BlockGraph cfg)
40 {
41 this.cfg = cfg;
42 vg = new ValueGraph(cfg);
43 partitions = new HashSet(); nodeToPartition = new HashMap();
45 currentPartitionNumber = 0;
46
47 initPartition();
48 iterPartition();
49 }
50
51 public static void main(String  [] args)
53 {
54
56 Scene.v().loadClassAndSupport(args[0]);
57 SootClass sc = Scene.v().getSootClass(args[0]);
58 SootMethod sm = sc.getMethod(args[1]);
59 Body b = sm.retrieveActiveBody();
60 ShimpleBody sb = Shimple.v().newBody(b);
61 CompleteBlockGraph cfg = new CompleteBlockGraph(sb);
62 SimpleGlobalValueNumberer sgvn = new SimpleGlobalValueNumberer(cfg);
63 System.out.println(sgvn);
64 }
65
66 public int getGlobalValueNumber(Local local)
67 {
68 Node node = vg.getNode(local);
69 return ((Partition)nodeToPartition.get(node)).getPartitionNumber();
70 }
71
72 public boolean areEqual(Local local1, Local local2)
73 {
74 Node node1 = vg.getNode(local1);
75 Node node2 = vg.getNode(local2);
76
77 return (nodeToPartition.get(node1) == nodeToPartition.get(node2));
78 }
79
80 protected void initPartition()
81 {
82 Map labelToPartition = new HashMap();
83
84 Iterator topNodesIt = vg.getTopNodes().iterator();
85 while(topNodesIt.hasNext()){
86 Node node = (Node) topNodesIt.next();
87 String label = node.getLabel();
88
89 Partition partition = (Partition) labelToPartition.get(label);
90 if(partition == null){
91 partition = new Partition();
92 partitions.add(partition);
93 labelToPartition.put(label, partition);
94 }
95
96 partition.add(node);
97 nodeToPartition.put(node, partition);
98 }
99 }
100
101 protected List newPartitions;
102
103 protected void iterPartition()
104 {
105 newPartitions = new ArrayList();
106
107 Iterator partitionsIt = partitions.iterator();
108 while(partitionsIt.hasNext()){
109 Partition partition = (Partition) partitionsIt.next();
110 processPartition(partition);
111 }
112
113 partitions.addAll(newPartitions);
114 }
115
116 protected void processPartition(Partition partition)
117 {
118 int size = partition.size();
119
120 if(size == 0)
121 return;
122
123 Node firstNode = (Node) partition.get(0);
124 Partition newPartition = new Partition();
125 boolean processNewPartition = false;
126
127 for(int i = 1; i < size; i++){
128 Node node = (Node) partition.get(i);
129
130 if(!childrenAreInSamePartition(firstNode, node)){
131 partition.remove(i);
132 size--;
133 newPartition.add(node);
134 newPartitions.add(newPartition);
135 nodeToPartition.put(node, newPartition);
136 processNewPartition = true;
137 }
138 }
139
140 if(processNewPartition)
141 processPartition(newPartition);
142 }
143
144 protected boolean childrenAreInSamePartition(Node node1, Node node2)
145 {
146 boolean ordered = node1.isOrdered();
147 if(ordered != node2.isOrdered())
148 throw new RuntimeException ("Assertion failed.");
149
150 List children1 = node1.getChildren();
151 List children2 = node2.getChildren();
152
153 int numberOfChildren = children1.size();
154 if(children2.size() != numberOfChildren)
155 return false;
156
157 if(ordered){
158 for(int i = 0; i < numberOfChildren; i++){
159 Node child1 = (Node) children1.get(i);
160 Node child2 = (Node) children2.get(i);
161 if(nodeToPartition.get(child1) != nodeToPartition.get(child2))
162 return false;
163 }
164 }
165 else{
166 for(int i = 0; i < numberOfChildren; i++){
167 Node child1 = (Node) children1.get(i);
168 for(int j = i; j < numberOfChildren; j++){
169 Node child2 = (Node) children2.get(j);
170
171 if(nodeToPartition.get(child1) ==
172 nodeToPartition.get(child2)){
173 if(j != i){
174 children2.remove(j);
175 children2.add(i, child2);
176 }
177 break;
178 }
179
180 if((j + 1) == numberOfChildren)
182 return false;
183 }
184 }
185 }
186
187 return true;
188 }
189
190 public String toString()
191 {
192 StringBuffer tmp = new StringBuffer ();
193
194 Body b = cfg.getBody();
195 Iterator localsIt = b.getLocals().iterator();
196
197 while(localsIt.hasNext()){
198 Local local = (Local)localsIt.next();
199 tmp.append(local + "\t" + getGlobalValueNumber(local) + "\n");
200 }
201
202
217
218 return tmp.toString();
219 }
220
221 protected class Partition extends ArrayList
222 {
223 protected int partitionNumber;
224
225 protected Partition()
226 {
227 super();
228 partitionNumber = currentPartitionNumber++;
229 }
230
231 protected int getPartitionNumber()
232 {
233 return partitionNumber;
234 }
235 }
236 }
237 |
Popular Tags |
Java API By Example, From Geeks To Geeks.