|
1
6
7
8
9
27
28 package soot.shimple.toolkits.graph;
29
30 import soot.*;
31 import soot.jimple.*;
32 import soot.util.*;
33 import soot.shimple.*;
34 import soot.toolkits.graph.*;
35 import java.util.*;
36
37 public class ValueGraph
39 {
40
46 protected Map localToNode;
47 protected Map nodeToLocal;
48 protected List nodeList;
49 protected int currentNodeNumber;
50
51 public ValueGraph(BlockGraph cfg)
52 {
53 if(!(cfg.getBody() instanceof ShimpleBody))
54 throw new RuntimeException  ("ValueGraph requires SSA form");
55
56 localToNode = new HashMap();
57 nodeToLocal = new HashMap();
58 nodeList = new ArrayList();
59 currentNodeNumber = 0;
60 PseudoTopologicalOrderer pto = new PseudoTopologicalOrderer();
61 List blocks = pto.newList(cfg);
62
63 for(Iterator blocksIt = blocks.iterator(); blocksIt.hasNext();){
64 Block block = (Block) blocksIt.next();
65 for(Iterator blockIt = block.iterator(); blockIt.hasNext();)
66 handleStmt((Stmt) blockIt.next());
67 }
68
69 for(Iterator nodesIt = nodeList.iterator(); nodesIt.hasNext();){
70 Node node = (Node) nodesIt.next();
71 node.patchStubs();
72 }
73 }
74
75 protected void handleStmt(Stmt stmt)
76 {
77 if(!(stmt instanceof DefinitionStmt))
78 return;
79 DefinitionStmt dStmt = (DefinitionStmt) stmt;
80
81 Value leftOp = dStmt.getLeftOp();
82 if(!(leftOp instanceof Local))
83 return;
84
85 Value rightOp = dStmt.getRightOp();
86 Node node = fetchGraph(rightOp);
87 localToNode.put(leftOp, node);
88
89 if(!(rightOp instanceof Local) && !node.isStub())
91 nodeToLocal.put(node, leftOp);
92 }
93
94 protected Node fetchNode(Value value)
95 {
96 Node ret = null;
97
98 if(value instanceof Local){
99 ret = getNode(value);
101
102 if(ret == null)
106 ret = new Node(value, true);
107 }
108
109 else
111 ret = new Node(value);
112
113 return ret;
114 }
115
116 protected Node fetchGraph(Value value)
117 {
118 AbstractShimpleValueSwitch vs;
119
120 value.apply(vs = new AbstractShimpleValueSwitch()
121 {
122
126 public void defaultCase(Object object)
127 {
128 throw new RuntimeException ("Internal error: " + object +
129 " unhandled case.");
130 }
131
132
135 public void caseLocal(Local l)
136 {
137 setResult(fetchNode(l));
138 }
139
140
143 public void handleConstant(Constant constant)
144 {
145 setResult(fetchNode(constant));
146 }
147
148
151 public void handleRef(Ref ref)
152 {
153 setResult(fetchNode(ref));
154 }
155
156 public void handleBinop(BinopExpr binop, boolean ordered)
157 {
158 Node nop1 = fetchNode(binop.getOp1());
159 Node nop2 = fetchNode(binop.getOp2());
160
161 List children = new ArrayList();
162 children.add(nop1);
163 children.add(nop2);
164
165 setResult(new Node(binop, ordered, children));
166 }
167
168 public void handleUnknown(Expr expr)
172 {
173 setResult(fetchNode(expr));
174 }
175
176 public void handleUnop(UnopExpr unop)
177 {
178 Node nop = fetchNode(unop.getOp());
179 List child = new SingletonList(nop);
180 setResult(new Node(unop, true, child));
181 }
182
183
184 public void caseDoubleSwitch(DoubleConstant v)
185 {
186 handleConstant(v);
187 }
188
189 public void caseFloatConstant(FloatConstant v)
190 {
191 handleConstant(v);
192 }
193
194 public void caseIntConstant(IntConstant v)
195 {
196 handleConstant(v);
197 }
198
199 public void caseLongConstant(LongConstant v)
200 {
201 handleConstant(v);
202 }
203
204 public void caseNullConstant(NullConstant v)
205 {
206 handleConstant(v);
207 }
208
209 public void caseStringConstant(StringConstant v)
210 {
211 handleConstant(v);
212 }
213
214 public void caseArrayRef(ArrayRef v)
215 {
216 handleRef(v);
217 }
218
219 public void caseStaticFieldRef(StaticFieldRef v)
220 {
221 handleRef(v);
222 }
223
224 public void caseInstanceFieldRef(InstanceFieldRef v)
225 {
226 handleRef(v);
227 }
228
229 public void caseParameterRef(ParameterRef v)
230 {
231 handleRef(v);
232 }
233
234 public void caseCaughtExceptionRef(CaughtExceptionRef v)
235 {
236 handleRef(v);
237 }
238
239 public void caseThisRef(ThisRef v)
240 {
241 handleRef(v);
242 }
243
244 public void caseAddExpr(AddExpr v)
245 {
246 handleBinop(v, false);
247 }
248
249 public void caseAndExpr(AndExpr v)
250 {
251 handleBinop(v, false);
252 }
253
254 public void caseCmpExpr(CmpExpr v)
255 {
256 handleBinop(v, true);
257 }
258
259 public void caseCmpgExpr(CmpgExpr v)
260 {
261 handleBinop(v, true);
262 }
263
264 public void caseCmplExpr(CmplExpr v)
265 {
266 handleBinop(v, true);
267 }
268
269 public void caseDivExpr(DivExpr v)
270 {
271 handleBinop(v, true);
272 }
273
274 public void caseEqExpr(EqExpr v)
275 {
276 handleBinop(v, false);
277 }
278
279 public void caseNeExpr(NeExpr v)
280 {
281 handleBinop(v, false);
282 }
283
284 public void caseGeExpr(GeExpr v)
285 {
286 handleBinop(v, true);
287 }
288
289 public void caseGtExpr(GtExpr v)
290 {
291 handleBinop(v, true);
292 }
293
294 public void caseLeExpr(LeExpr v)
295 {
296 handleBinop(v, true);
297 }
298
299 public void caseLtExpr(LtExpr v)
300 {
301 handleBinop(v, true);
302 }
303
304 public void caseMulExpr(MulExpr v)
305 {
306 handleBinop(v, false);
307 }
308
309 public void caseOrExpr(OrExpr v)
311 {
312 handleBinop(v, false);
313 }
314
315 public void caseRemExpr(RemExpr v)
316 {
317 handleBinop(v, true);
318 }
319
320 public void caseShlExpr(ShlExpr v)
321 {
322 handleBinop(v, true);
323 }
324
325 public void caseShrExpr(ShrExpr v)
326 {
327 handleBinop(v, true);
328 }
329
330 public void caseUshrExpr(UshrExpr v)
331 {
332 handleBinop(v, true);
333 }
334
335 public void caseSubExpr(SubExpr v)
336 {
337 handleBinop(v, true);
338 }
339
340 public void caseXorExpr(XorExpr v)
342 {
343 handleBinop(v, false);
344 }
345
346 public void caseInterfaceInvokeExpr(InterfaceInvokeExpr v)
347 {
348 handleUnknown(v);
349 }
350
351 public void caseSpecialInvokeExpr(SpecialInvokeExpr v)
352 {
353 handleUnknown(v);
354 }
355
356 public void caseStaticInvokeExpr(StaticInvokeExpr v)
357 {
358 handleUnknown(v);
359 }
360
361 public void caseVirtualInvokeExpr(VirtualInvokeExpr v)
362 {
363 handleUnknown(v);
364 }
365
366
369 public void caseCastExpr(CastExpr v)
370 {
371 setResult(fetchNode(v.getOp()));
372 }
373
374
377 public void caseInstanceOfExpr(InstanceOfExpr v)
378 {
379 Node nop1 = fetchNode(v.getOp());
380
381 Value op2 = new TypeValueWrapper(v.getCheckType());
382 Node nop2 = fetchNode(op2);
383
384 List children = new ArrayList();
385 children.add(nop1);
386 children.add(nop2);
387
388 setResult(new Node(v, true, children));
389 }
390
391 public void caseNewArrayExpr(NewArrayExpr v)
393 {
394 handleUnknown(v);
395 }
396
397 public void caseNewMultiArrayExpr(NewMultiArrayExpr v)
398 {
399 handleUnknown(v);
400 }
401
402 public void caseNewExpr(NewExpr v)
403 {
404 handleUnknown(v);
405 }
406
407 public void caseLengthExpr(LengthExpr v)
408 {
409 handleUnop(v);
410 }
411
412 public void caseNegExpr(NegExpr v)
413 {
414 handleUnop(v);
415 }
416
417 public void casePhiExpr(PhiExpr v)
418 {
419 List children = new ArrayList();
420 Iterator argsIt = v.getValues().iterator();
421
422 while(argsIt.hasNext()){
423 Value arg = (Value) argsIt.next();
424 children.add(fetchNode(arg));
425 }
426
427 setResult(new Node(v, true, children));
430 }
431 });
432
433 return((Node)vs.getResult());
434 }
435
436 public Node getNode(Value local)
437 {
438 return (Node) localToNode.get(local);
439 }
440
441 public Collection getTopNodes()
443 {
444 return localToNode.values();
445 }
446
447 public Local getLocal(Node node)
448 {
449 return (Local)nodeToLocal.get(node);
450 }
451
452 public String toString()
453 {
454 StringBuffer tmp = new StringBuffer ();
455
456 for(int i = 0; i < nodeList.size(); i++){
457 tmp.append(nodeList.get(i));
458 tmp.append("\n");
459 }
460
461 return tmp.toString();
462 }
463
464 public static void main(String [] args)
466 {
467
469 Scene.v().loadClassAndSupport(args[0]);
470 SootClass sc = Scene.v().getSootClass(args[0]);
471 SootMethod sm = sc.getMethod(args[1]);
472 Body b = sm.retrieveActiveBody();
473 ShimpleBody sb = Shimple.v().newBody(b);
474 CompleteBlockGraph cfg = new CompleteBlockGraph(sb);
475 ValueGraph vg = new ValueGraph(cfg);
476 System.out.println(vg);
477 }
478
479 public class Node
480 {
481 protected int nodeNumber;
482 protected Value node;
483 protected String nodeLabel;
484 protected boolean ordered;
485 protected List children;
486
487 protected boolean stub = false;
488
489 protected Node(Value local, boolean ignored)
491 {
492 this.stub = true;
493 setNode(local);
494 }
495
496 protected void patchStubs()
497 {
498 if(isStub())
500 throw new RuntimeException ("Assertion failed.");
501
502 for(int i = 0; i < children.size(); i++){
504 Node child = (Node) children.get(i);
505
506 if(child.isStub()){
507 Node newChild = (Node) localToNode.get(child.node);
508 if(newChild == null || newChild.isStub())
509 throw new RuntimeException ("Assertion failed.");
510 children.set(i, newChild);
511 }
512 }
513 }
514
515 protected void checkIfStub()
516 {
517 if(isStub())
518 throw new RuntimeException ("Assertion failed: Attempted operation on invalid node (stub)");
519 }
520
521 protected Node(Value node)
522 {
523 this(node, true, Collections.EMPTY_LIST);
524 }
525
526 protected Node(Value node, boolean ordered, List children)
527 {
528 setNode(node);
529 setOrdered(ordered);
530 setChildren(children);
531
532 nodeNumber = currentNodeNumber++;
534 updateLabel();
535 nodeList.add(nodeNumber, this);
536 }
537
538 protected void setNode(Value node)
539 {
540 this.node = node;
541 }
542
543 protected void setOrdered(boolean ordered)
544 {
545 this.ordered = ordered;
546 }
547
548 protected void setChildren(List children)
549 {
550 this.children = children;
551 }
552
553 protected void updateLabel()
554 {
555 if(!children.isEmpty()){
556 nodeLabel = node.getClass().getName();
557 if(node instanceof PhiExpr)
558 nodeLabel = nodeLabel + ((PhiExpr)node).getBlockId();
559 }
560 else{
561
563
567
574 nodeLabel = node.toString();
581 if((node instanceof NewExpr) ||
582 (node instanceof NewArrayExpr) ||
583 (node instanceof NewMultiArrayExpr) ||
584 (node instanceof Ref) ||
585 (node instanceof InvokeExpr))
586 nodeLabel = nodeLabel + " " + getNodeNumber();
587 }
588 }
589
590 public boolean isStub()
591 {
592 return stub;
593 }
594
595 public String getLabel()
596 {
597 checkIfStub();
598 return nodeLabel;
599 }
600
601 public boolean isOrdered()
602 {
603 checkIfStub();
604 return ordered;
605 }
606
607 public List getChildren()
608 {
609 checkIfStub();
610 return children;
611 }
613
614 public int getNodeNumber()
615 {
616 checkIfStub();
617 return nodeNumber;
618 }
619
620 public String toString()
621 {
622 checkIfStub();
623
624 StringBuffer tmp = new StringBuffer ();
625
626 Local local = getLocal(this);
627 if(local != null)
628 tmp.append(local.toString());
629
630 tmp.append("\tNode " + getNodeNumber() + ": " + getLabel());
631
632 List children = getChildren();
633
634 if(!children.isEmpty()){
635 tmp.append(" [" +
636 (isOrdered() ? "ordered" : "unordered") + ": ");
637 for(int i = 0; i < children.size(); i++){
638 if(i != 0)
639 tmp.append(", ");
640 tmp.append(((Node) children.get(i)).getNodeNumber());
641 }
642 tmp.append("]");
643 }
644
645 return tmp.toString();
646 }
647 }
648
649 protected static class TypeValueWrapper implements Value
650 {
651 protected Type type;
652
653 protected TypeValueWrapper(Type type)
654 {
655 this.type = type;
656 }
657
658 public List getUseBoxes()
659 {
660 return Collections.EMPTY_LIST;
661 }
662
663 public Type getType()
664 {
665 return type;
666 }
667
668 public Object clone()
669 {
670 return new TypeValueWrapper(type);
671 }
672
673 public void toString(UnitPrinter up)
674 {
675 up.literal("[Wrapped] " + type);
676 }
677
678 public void apply(Switch sw)
679 {
680 throw new RuntimeException ("Not Implemented.");
681 }
682
683 public boolean equals(Object o)
684 {
685 if(!(o instanceof TypeValueWrapper))
686 return false;
687
688 return getType().equals(((TypeValueWrapper)o).getType());
689 }
690
691 public int hashCode()
692 {
693 return getType().hashCode();
694 }
695
696 public boolean equivTo(Object o)
697 {
698 return equals(o);
699 }
700
701 public int equivHashCode()
702 {
703 return hashCode();
704 }
705 }
706 }
707 |
Popular Tags |
Java API By Example, From Geeks To Geeks.