|
1
19
20 package soot.dava.toolkits.base.finders;
21 import soot.*;
22
23 import soot.dava.*;
24 import java.util.*;
25 import soot.util.*;
26 import soot.dava.internal.asg.*;
27 import soot.dava.internal.SET.*;
28 import soot.dava.internal.AST.*;
29
30 public class LabeledBlockFinder implements FactFinder
31 {
32 public LabeledBlockFinder( Singletons.Global g ) {}
33 public static LabeledBlockFinder v() { return G.v().soot_dava_toolkits_base_finders_LabeledBlockFinder(); }
34
35 private HashMap orderNumber = new HashMap();
36
37 public void find( DavaBody body, AugmentedStmtGraph asg, SETNode SET) throws RetriggerAnalysisException
38 {
39 Dava.v().log( "LabeledBlockFinder::find()");
40
41 Iterator bit = SET.get_Body().iterator();
42 while (bit.hasNext())
43 SET.find_SmallestSETNode((AugmentedStmt) bit.next());
44
45 SET.find_LabeledBlocks( this);
46 }
47
48 public void perform_ChildOrder( SETNode SETParent)
49 {
50 Dava.v().log( "LabeledBlockFinder::perform_ChildOrder()");
51
52 if (SETParent instanceof SETStatementSequenceNode)
53 return;
54
55 Iterator sbit = SETParent.get_SubBodies().iterator();
56 while (sbit.hasNext()) {
57
58 IterableSet body = (IterableSet) sbit.next();
59 IterableSet children = (IterableSet) SETParent.get_Body2ChildChain().get( body);
60
61 HashSet touchSet = new HashSet();
62 IterableSet childOrdering = new IterableSet();
63 LinkedList worklist = new LinkedList();
64 List SETBasicBlocks = null;
65
66 if (SETParent instanceof SETUnconditionalWhileNode) {
67 SETNode startSETNode = ((SETUnconditionalWhileNode) SETParent).get_CharacterizingStmt().myNode;
68
69 while (children.contains( startSETNode) == false)
70 startSETNode = startSETNode.get_Parent();
71
72 SETBasicBlocks = build_Connectivity( SETParent, body, startSETNode);
73 worklist.add( SETBasicBlock.get_SETBasicBlock( startSETNode));
74 }
75
76 else if (SETParent instanceof SETTryNode) {
77 SETNode startSETNode = null;
78
79 Iterator bit = body.iterator();
80 find_entry_loop:
81 while (bit.hasNext()) {
82 AugmentedStmt as = (AugmentedStmt) bit.next();
83
84 Iterator pbit = as.cpreds.iterator();
85 while (pbit.hasNext())
86 if (body.contains( pbit.next()) == false) {
87 startSETNode = as.myNode;
88 break find_entry_loop;
89 }
90 }
91 if (startSETNode == null)
92 startSETNode = ((SETTryNode) SETParent).get_EntryStmt().myNode;
93
94 while (children.contains( startSETNode) == false)
95 startSETNode = startSETNode.get_Parent();
96
97 SETBasicBlocks = build_Connectivity( SETParent, body, startSETNode);
98 worklist.add( SETBasicBlock.get_SETBasicBlock( startSETNode));
99 }
100
101 else {
102 SETBasicBlocks = build_Connectivity( SETParent, body, null);
103
104 Iterator cit = children.iterator();
105 while (cit.hasNext()) {
106 SETNode child = (SETNode) cit.next();
107
108 if (child.get_Predecessors().isEmpty())
109 worklist.add( SETBasicBlock.get_SETBasicBlock( child));
110 }
111 }
112
113 while (worklist.isEmpty() == false) {
114 SETBasicBlock sbb = (SETBasicBlock) worklist.removeFirst();
115
116 Iterator bit = sbb.get_Body().iterator();
118 while (bit.hasNext())
119 childOrdering.addLast( bit.next());
120
121 touchSet.add( sbb);
122
123
124
127
128 TreeSet sortedSuccessors = new TreeSet();
129
130 Iterator sit = sbb.get_Successors().iterator();
131 SETBasicBlock_successor_loop:
132 while (sit.hasNext()) {
133 SETBasicBlock ssbb = (SETBasicBlock) sit.next();
134
135 if (touchSet.contains( ssbb))
136 continue;
137
138 Iterator psit = ssbb.get_Predecessors().iterator();
139 while (psit.hasNext())
140 if (touchSet.contains( psit.next()) == false)
141 continue SETBasicBlock_successor_loop;
142
143 sortedSuccessors.add( ssbb);
144 }
145
146 sit = sortedSuccessors.iterator();
147 while (sit.hasNext())
148 worklist.addFirst( sit.next());
149
150
153
154 }
155
156 int count = 0;
157
158 Iterator it = childOrdering.iterator();
159 while (it.hasNext())
160 orderNumber.put( it.next(), new Integer  ( count++));
161
162 children.clear();
163 children.addAll( childOrdering);
164 }
165 }
166
167 private List build_Connectivity( SETNode SETParent, IterableSet body, SETNode startSETNode)
168 {
169 Dava.v().log( "LabeledBlockFinder::build_Connectivity()");
170
171 IterableSet children = (IterableSet) SETParent.get_Body2ChildChain().get( body);
172
173
176
177 Iterator it = body.iterator();
179 while (it.hasNext()) {
180 AugmentedStmt as = (AugmentedStmt) it.next();
181
182 Iterator sit = as.csuccs.iterator();
184 while (sit.hasNext()) {
185 AugmentedStmt sas = (AugmentedStmt) sit.next();
186
187 if (body.contains( sas)) {
188
189 SETNode srcNode = as.myNode;
191 SETNode dstNode = sas.myNode;
192
193 while (children.contains( srcNode) == false)
194 srcNode = srcNode.get_Parent();
195
196 while (children.contains( dstNode) == false)
197 dstNode = dstNode.get_Parent();
198
199 if (srcNode == dstNode)
200 continue;
201
202 if (srcNode.get_Successors().contains( dstNode) == false)
204 srcNode.get_Successors().add( dstNode);
205
206 if (dstNode.get_Predecessors().contains( srcNode) == false)
207 dstNode.get_Predecessors().add( srcNode);
208 }
209 }
210 }
211
212 Dava.v().log( "LabeledBlockFinder::build_Connectivity() - built connectivity");
213
214
215
218
219 LinkedList basicBlockList = new LinkedList();
221
222 Iterator cit = children.iterator();
223 while (cit.hasNext()) {
224 SETNode child = (SETNode) cit.next();
225
226 if (SETBasicBlock.get_SETBasicBlock( child) != null)
227 continue;
228
229 SETBasicBlock basicBlock = new SETBasicBlock();
231 while (child.get_Predecessors().size() == 1) {
232
233 if ((startSETNode != null) && (child == startSETNode))
234 break;
235
236 SETNode prev = (SETNode) child.get_Predecessors().getFirst();
237 if ((SETBasicBlock.get_SETBasicBlock( prev) != null) || (prev.get_Successors().size() != 1))
238 break;
239
240 child = prev;
241 }
242
243 basicBlock.add( child);
244
245 while (child.get_Successors().size() == 1) {
246 child = (SETNode) child.get_Successors().getFirst();
247
248 if ((SETBasicBlock.get_SETBasicBlock( child) != null) || (child.get_Predecessors().size() != 1))
249 break;
250
251 basicBlock.add( child);
252 }
253
254 basicBlockList.add( basicBlock);
255 }
256
257
258 Dava.v().log( "LabeledBlockFinder::build_Connectivity() - created basic blocks");
259
260 Iterator bblit = basicBlockList.iterator();
262 while (bblit.hasNext()) {
263 SETBasicBlock sbb = (SETBasicBlock) bblit.next();
264 SETNode entryNode = sbb.get_EntryNode();
265
266 Iterator pit = entryNode.get_Predecessors().iterator();
267 while (pit.hasNext()) {
268 SETNode psn = (SETNode) pit.next();
269
270 SETBasicBlock psbb = SETBasicBlock.get_SETBasicBlock( psn);
271
272 if (sbb.get_Predecessors().contains( psbb) == false)
273 sbb.get_Predecessors().add( psbb);
274
275 if (psbb.get_Successors().contains( sbb) == false)
276 psbb.get_Successors().add( sbb);
277 }
278 }
279
280 Dava.v().log( "LabeledBlockFinder::build_Connectivity() - done");
281
282 return basicBlockList;
283 }
284
285 public void find_LabeledBlocks( SETNode SETParent)
286 {
287 Dava.v().log( "LabeledBlockFinder::find_LabeledBlocks()");
288
289 Iterator sbit = SETParent.get_SubBodies().iterator();
290 while (sbit.hasNext()) {
291 IterableSet curBody = (IterableSet) sbit.next();
292 IterableSet children = (IterableSet) SETParent.get_Body2ChildChain().get( curBody);
293
294 Iterator it = children.snapshotIterator();
295 if (it.hasNext()) {
296 SETNode
297 curNode = (SETNode) it.next(),
298 prevNode = null;
299
300 while (it.hasNext()) {
302 prevNode = curNode;
303 curNode = (SETNode) it.next();
304 AugmentedStmt entryStmt = curNode.get_EntryStmt();
305
306 SETNode minNode = null;
307 boolean build = false;
308
309 Iterator pit = entryStmt.cpreds.iterator();
311 while (pit.hasNext()) {
312 AugmentedStmt pas = (AugmentedStmt) pit.next();
313
314 if (curBody.contains( pas) == false) continue;
316
317 SETNode srcNode = pas.myNode;
318
319 while (children.contains( srcNode) == false)
320 srcNode = srcNode.get_Parent();
321
322 if (srcNode == curNode)
323 continue;
324
325 if (srcNode != prevNode) {
326 build = true;
327
328 if ((minNode == null) || (((Integer ) orderNumber.get( srcNode)).intValue() < ((Integer ) orderNumber.get( minNode)).intValue()))
329 minNode = srcNode;
330 }
331 }
332
333 if (build) {
334 IterableSet labeledBlockBody = new IterableSet();
335
336 Iterator cit = children.iterator( minNode);
337 while (cit.hasNext()) {
338 SETNode child = (SETNode) cit.next();
339 if (child == curNode)
340 break;
341
342 labeledBlockBody.addAll( child.get_Body());
343 }
344
345 SETLabeledBlockNode slbn = new SETLabeledBlockNode( labeledBlockBody);
346 orderNumber.put( slbn, orderNumber.get( minNode));
347
348 cit = children.snapshotIterator( minNode);
349 while (cit.hasNext()) {
350 SETNode child = (SETNode) cit.next();
351 if (child == curNode)
352 break;
353
354 SETParent.remove_Child( child, children );
355 slbn.add_Child( child, (IterableSet) slbn.get_Body2ChildChain().get( slbn.get_SubBodies().get(0)));
356 }
357
358 SETParent.insert_ChildBefore( slbn, curNode, children);
359 }
360 }
361 }
362 }
363 }
364 }
365 |
Popular Tags |
Java API By Example, From Geeks To Geeks.