|
1
19
20 package soot.jimple.spark.pag;
21 import java.util.*;
22 import soot.jimple.*;
23 import soot.jimple.spark.*;
24 import soot.*;
25 import soot.jimple.spark.sets.*;
26 import soot.jimple.spark.solver.OnFlyCallGraph;
27 import soot.jimple.spark.internal.*;
28 import soot.jimple.spark.builder.*;
29 import soot.jimple.toolkits.callgraph.Edge;
30 import soot.jimple.toolkits.pointer.util.NativeMethodDriver;
31 import soot.util.*;
32 import soot.util.queue.*;
33 import soot.options.SparkOptions;
34 import soot.tagkit.*;
35
36
39 public class PAG implements PointsToAnalysis {
40 public PAG( final SparkOptions opts ) {
41 this.opts = opts;
42 if( opts.add_tags() ) {
43 nodeToTag = new HashMap();
44 }
45 typeManager = new TypeManager(this);
46 if( !opts.ignore_types() ) {
47 typeManager.setFastHierarchy( Scene.v().getOrMakeFastHierarchy() );
48 }
49 switch( opts.set_impl() ) {
50 case SparkOptions.set_impl_hash:
51 setFactory = HashPointsToSet.getFactory();
52 break;
53 case SparkOptions.set_impl_hybrid:
54 setFactory = HybridPointsToSet.getFactory();
55 break;
56 case SparkOptions.set_impl_shared:
57 setFactory = SharedPointsToSet.getFactory();
58 break;
59 case SparkOptions.set_impl_array:
60 setFactory = SortedArraySet.getFactory();
61 break;
62 case SparkOptions.set_impl_bit:
63 setFactory = BitPointsToSet.getFactory();
64 break;
65 case SparkOptions.set_impl_double:
66 P2SetFactory oldF;
67 P2SetFactory newF;
68 switch( opts.double_set_old() ) {
69 case SparkOptions.double_set_old_hash:
70 oldF = HashPointsToSet.getFactory();
71 break;
72 case SparkOptions.double_set_old_hybrid:
73 oldF = HybridPointsToSet.getFactory();
74 break;
75 case SparkOptions.double_set_old_shared:
76 oldF = SharedPointsToSet.getFactory();
77 break;
78 case SparkOptions.double_set_old_array:
79 oldF = SortedArraySet.getFactory();
80 break;
81 case SparkOptions.double_set_old_bit:
82 oldF = BitPointsToSet.getFactory();
83 break;
84 default:
85 throw new RuntimeException  ();
86 }
87 switch( opts.double_set_new() ) {
88 case SparkOptions.double_set_new_hash:
89 newF = HashPointsToSet.getFactory();
90 break;
91 case SparkOptions.double_set_new_hybrid:
92 newF = HybridPointsToSet.getFactory();
93 break;
94 case SparkOptions.double_set_new_shared:
95 newF = SharedPointsToSet.getFactory();
96 break;
97 case SparkOptions.double_set_new_array:
98 newF = SortedArraySet.getFactory();
99 break;
100 case SparkOptions.double_set_new_bit:
101 newF = BitPointsToSet.getFactory();
102 break;
103 default:
104 throw new RuntimeException ();
105 }
106 setFactory = DoublePointsToSet.getFactory( newF, oldF );
107 break;
108 default:
109 throw new RuntimeException ();
110 }
111 }
112
113
114
115 public PointsToSet reachingObjects( Local l ) {
116 VarNode n = findLocalVarNode( l );
117 if( n == null ) {
118 return EmptyPointsToSet.v();
119 }
120 return n.getP2Set();
121 }
122
123
124 public PointsToSet reachingObjects( Context c, Local l ) {
125 VarNode n = findContextVarNode( l, c );
126 if( n == null ) {
127 return EmptyPointsToSet.v();
128 }
129 return n.getP2Set();
130 }
131
132
133 public PointsToSet reachingObjects( SootField f ) {
134 if( !f.isStatic() )
135 throw new RuntimeException ( "The parameter f must be a *static* field." );
136 VarNode n = findGlobalVarNode( f );
137 if( n == null ) {
138 return EmptyPointsToSet.v();
139 }
140 return n.getP2Set();
141 }
142
143
145 public PointsToSet reachingObjects( PointsToSet s, final SootField f ) {
146 if( f.isStatic() )
147 throw new RuntimeException ( "The parameter f must be an *instance* field." );
148
149 return reachingObjectsInternal( s, f );
150 }
151
152
154 public PointsToSet reachingObjectsOfArrayElement( PointsToSet s ) {
155 return reachingObjectsInternal( s, ArrayElement.v() );
156 }
157
158 private PointsToSet reachingObjectsInternal( PointsToSet s, final SparkField f ) {
159 if( getOpts().field_based() || getOpts().vta() ) {
160 VarNode n = findGlobalVarNode( f );
161 if( n == null ) {
162 return EmptyPointsToSet.v();
163 }
164 return n.getP2Set();
165 }
166 if( ((SparkOptions)getOpts()).propagator() == SparkOptions.propagator_alias ) {
167 throw new RuntimeException ( "The alias edge propagator does not compute points-to information for instance fields! Use a different propagator." );
168 }
169 PointsToSetInternal bases = (PointsToSetInternal) s;
170 final PointsToSetInternal ret = setFactory.newSet(
171 (f instanceof SootField) ? ((SootField)f).getType() : null, this );
172 bases.forall( new P2SetVisitor() {
173 public final void visit( Node n ) {
174 Node nDotF = ((AllocNode) n).dot( f );
175 if(nDotF != null) ret.addAll( nDotF.getP2Set(), null );
176 }} );
177 return ret;
178 }
179
180 public P2SetFactory getSetFactory() {
181 return setFactory;
182 }
183 public void cleanUpMerges() {
184 if( opts.verbose() ) {
185 G.v().out.println( "Cleaning up graph for merged nodes" );
186 }
187 Map[] maps = { simple, alloc, store, load,
188 simpleInv, allocInv, storeInv, loadInv };
189 for( int i = 0; i < maps.length; i++ ) {
190 Map m = maps[i];
191 for( Iterator it = m.keySet().iterator(); it.hasNext(); ) {
192 lookup( m, it.next() );
193 }
194 }
195 somethingMerged = false;
196 if( opts.verbose() ) {
197 G.v().out.println( "Done cleaning up graph for merged nodes" );
198 }
199 }
200 public boolean doAddSimpleEdge( VarNode from, VarNode to ) {
201 return addToMap( simple, from, to ) | addToMap( simpleInv, to, from );
202 }
203
204 public boolean doAddStoreEdge( VarNode from, FieldRefNode to ) {
205 return addToMap( store, from, to ) | addToMap( storeInv, to, from );
206 }
207
208 public boolean doAddLoadEdge( FieldRefNode from, VarNode to ) {
209 return addToMap( load, from, to ) | addToMap( loadInv, to, from );
210 }
211
212 public boolean doAddAllocEdge( AllocNode from, VarNode to ) {
213 return addToMap( alloc, from, to ) | addToMap( allocInv, to, from );
214 }
215
216
217 void mergedWith( Node n1, Node n2 ) {
218 if( n1.equals( n2 ) ) throw new RuntimeException ( "oops" );
219
220 somethingMerged = true;
221 if( ofcg() != null ) ofcg().mergedWith( n1, n2 );
222
223 Map[] maps = { simple, alloc, store, load,
224 simpleInv, allocInv, storeInv, loadInv };
225 for( int mapi = 0; mapi < maps.length; mapi++ ) {
226 Map m = maps[mapi];
227
228 if( !m.keySet().contains( n2 ) ) continue;
229
230 Object [] os = { m.get( n1 ), m.get( n2 ) };
231 int size1 = getSize(os[0]); int size2 = getSize(os[1]);
232 if( size1 == 0 ) {
233 if( os[1] != null ) m.put( n1, os[1] );
234 } else if( size2 == 0 ) {
235 } else if( os[0] instanceof HashSet ) {
237 if( os[1] instanceof HashSet ) {
238 ((HashSet) os[0]).addAll( (HashSet) os[1] );
239 } else {
240 Node[] ar = (Node[]) os[1];
241 for( int j = 0; j < ar.length; j++ ) {
242 ( (HashSet) os[0] ).add( ar[j] );
243 }
244 }
245 } else if( os[1] instanceof HashSet ) {
246 Node[] ar = (Node[]) os[0];
247 for( int j = 0; j < ar.length; j++ ) {
248 ((HashSet) os[1]).add( ar[j] );
249 }
250 m.put( n1, os[1] );
251 } else if( size1*size2 < 1000 ) {
252 Node[] a1 = (Node[]) os[0];
253 Node[] a2 = (Node[]) os[1];
254 Node[] ret = new Node[size1+size2];
255 System.arraycopy( a1, 0, ret, 0, a1.length );
256 int j = a1.length;
257 outer: for( int i = 0; i < a2.length; i++ ) {
258 Node rep = a2[i];
259 for( int k = 0; k < j; k++ )
260 if( rep == ret[k] ) continue outer;
261 ret[j++] = rep;
262 }
263 Node[] newArray = new Node[j];
264 System.arraycopy( ret, 0, newArray, 0, j );
265 m.put( n1, ret = newArray );
266 } else {
267 HashSet s = new HashSet( size1+size2 );
268 for( int j = 0; j < os.length; j++ ) {
269 Object o = os[j];
270 if( o == null ) continue;
271 if( o instanceof Set ) {
272 s.addAll( (Set) o );
273 } else {
274 Node[] ar = (Node[]) o;
275 for( int k = 0; k < ar.length; k++ ) {
276 s.add( ar[k] );
277 }
278 }
279 }
280 m.put( n1, s );
281 }
282 m.remove( n2 );
283 }
284 }
285 protected final static Node[] EMPTY_NODE_ARRAY = new Node[0];
286 protected Node[] lookup( Map m, Object key ) {
287 Object valueList = m.get( key );
288 if( valueList == null ) {
289 return EMPTY_NODE_ARRAY;
290 }
291 if( valueList instanceof Set ) {
292 try {
293 m.put( key, valueList =
294 (Node[]) ( (Set) valueList ).toArray( EMPTY_NODE_ARRAY ) );
295 } catch( Exception e ) {
296 for( Iterator it = ((Set)valueList).iterator(); it.hasNext(); ) {
297 G.v().out.println( ""+it.next() );
298 }
299 throw new RuntimeException ( ""+valueList+e );
300 }
301 }
302 Node[] ret = (Node[]) valueList;
303 if( somethingMerged ) {
304 for( int i = 0; i < ret.length; i++ ) {
305 Node reti = ret[i];
306 Node rep = reti.getReplacement();
307 if( rep != reti || rep == key ) {
308 Set s;
309 if( ret.length <= 75 ) {
310 int j = i;
311 outer: for( ; i < ret.length; i++ ) {
312 reti = ret[i];
313 rep = reti.getReplacement();
314 if( rep == key ) continue;
315 for( int k = 0; k < j; k++ )
316 if( rep == ret[k] ) continue outer;
317 ret[j++] = rep;
318 }
319 Node[] newArray = new Node[j];
320 System.arraycopy( ret, 0, newArray, 0, j );
321 m.put( key, ret = newArray );
322 } else {
323 s = new HashSet( ret.length * 2 );
324 for( int j = 0; j < i; j++ ) s.add( ret[j] );
325 for( int j = i; j < ret.length; j++ ) {
326 rep = ret[j].getReplacement();
327 if( rep != key ) {
328 s.add( rep );
329 }
330 }
331 m.put( key, ret = (Node[]) s.toArray( EMPTY_NODE_ARRAY ) );
332 }
333 break;
334 }
335 }
336 }
337 return ret;
338 }
339
340 public Node[] simpleLookup( VarNode key )
341 { return lookup( simple, key ); }
342 public Node[] simpleInvLookup( VarNode key )
343 { return lookup( simpleInv, key ); }
344 public Node[] loadLookup( FieldRefNode key )
345 { return lookup( load, key ); }
346 public Node[] loadInvLookup( VarNode key )
347 { return lookup( loadInv, key ); }
348 public Node[] storeLookup( VarNode key )
349 { return lookup( store, key ); }
350 public Node[] storeInvLookup( FieldRefNode key )
351 { return lookup( storeInv, key ); }
352 public Node[] allocLookup( AllocNode key )
353 { return lookup( alloc, key ); }
354 public Node[] allocInvLookup( VarNode key )
355 { return lookup( allocInv, key ); }
356 public Set simpleSources() { return simple.keySet(); }
357 public Set allocSources() { return alloc.keySet(); }
358 public Set storeSources() { return store.keySet(); }
359 public Set loadSources() { return load.keySet(); }
360 public Set simpleInvSources() { return simpleInv.keySet(); }
361 public Set allocInvSources() { return allocInv.keySet(); }
362 public Set storeInvSources() { return storeInv.keySet(); }
363 public Set loadInvSources() { return loadInv.keySet(); }
364
365 public Iterator simpleSourcesIterator() { return simple.keySet().iterator(); }
366 public Iterator allocSourcesIterator() { return alloc.keySet().iterator(); }
367 public Iterator storeSourcesIterator() { return store.keySet().iterator(); }
368 public Iterator loadSourcesIterator() { return load.keySet().iterator(); }
369 public Iterator simpleInvSourcesIterator() { return simpleInv.keySet().iterator(); }
370 public Iterator allocInvSourcesIterator() { return allocInv.keySet().iterator(); }
371 public Iterator storeInvSourcesIterator() { return storeInv.keySet().iterator(); }
372 public Iterator loadInvSourcesIterator() { return loadInv.keySet().iterator(); }
373
374 static private int getSize( Object set ) {
375 if( set instanceof Set ) return ((Set) set).size();
376 else if( set == null ) return 0;
377 else return ((Object []) set).length;
378 }
379
380
381 protected P2SetFactory setFactory;
382 protected boolean somethingMerged = false;
383
384
386 public PointsToSet reachingObjects( Local l, SootField f ) {
387 return reachingObjects( reachingObjects(l), f );
388 }
389
390
392 public PointsToSet reachingObjects( Context c, Local l, SootField f ) {
393 return reachingObjects( reachingObjects(c, l), f );
394 }
395
396 private void addNodeTag( Node node, SootMethod m ) {
397 if( nodeToTag != null ) {
398 Tag tag;
399 if( m == null ) {
400 tag = new StringTag( node.toString() );
401 } else {
402 tag = new LinkTag( node.toString(), m, m.getDeclaringClass().getName() );
403 }
404 nodeToTag.put( node, tag );
405 }
406 }
407 public AllocNode makeAllocNode( Object newExpr, Type type, SootMethod m ) {
408 if( opts.types_for_sites() || opts.vta() ) newExpr = type;
409 AllocNode ret = (AllocNode) valToAllocNode.get( newExpr );
410 if( ret == null ) {
411 valToAllocNode.put( newExpr, ret = new AllocNode( this, newExpr, type, m ) );
412 newAllocNodes.add( ret );
413 addNodeTag( ret, m );
414 } else if( !( ret.getType().equals( type ) ) ) {
415 throw new RuntimeException ( "NewExpr "+newExpr+" of type "+type+
416 " previously had type "+ret.getType() );
417 }
418 return ret;
419 }
420 public AllocNode makeStringConstantNode( String s ) {
421 if( opts.types_for_sites() || opts.vta() )
422 return makeAllocNode( RefType.v( "java.lang.String" ),
423 RefType.v( "java.lang.String" ), null );
424 StringConstantNode ret = (StringConstantNode) valToAllocNode.get( s );
425 if( ret == null ) {
426 valToAllocNode.put( s, ret = new StringConstantNode( this, s ) );
427 newAllocNodes.add( ret );
428 addNodeTag( ret, null );
429 }
430 return ret;
431 }
432 public AllocNode makeClassConstantNode( ClassConstant cc ) {
433 if( opts.types_for_sites() || opts.vta() )
434 return makeAllocNode( RefType.v( "java.lang.Class" ),
435 RefType.v( "java.lang.Class" ), null );
436 ClassConstantNode ret = (ClassConstantNode) valToAllocNode.get(cc);
437 if( ret == null ) {
438 valToAllocNode.put(cc, ret = new ClassConstantNode(this, cc));
439 newAllocNodes.add( ret );
440 addNodeTag( ret, null );
441 }
442 return ret;
443 }
444
445 ChunkedQueue newAllocNodes = new ChunkedQueue();
446 public QueueReader allocNodeListener() { return newAllocNodes.reader(); }
447
448
449 public GlobalVarNode findGlobalVarNode( Object value ) {
450 if( opts.rta() ) {
451 value = null;
452 }
453 return (GlobalVarNode) valToGlobalVarNode.get( value );
454 }
455
456 public LocalVarNode findLocalVarNode( Object value ) {
457 if( opts.rta() ) {
458 value = null;
459 } else if( value instanceof Local ) {
460 return (LocalVarNode) localToNodeMap.get( (Local) value );
461 }
462 return (LocalVarNode) valToLocalVarNode.get( value );
463 }
464
465 public GlobalVarNode makeGlobalVarNode( Object value, Type type ) {
466 if( opts.rta() ) {
467 value = null;
468 type = RefType.v("java.lang.Object");
469 }
470 GlobalVarNode ret = (GlobalVarNode) valToGlobalVarNode.get( value );
471 if( ret == null ) {
472 valToGlobalVarNode.put( value,
473 ret = new GlobalVarNode( this, value, type ) );
474 addNodeTag( ret, null );
475 } else if( !( ret.getType().equals( type ) ) ) {
476 throw new RuntimeException ( "Value "+value+" of type "+type+
477 " previously had type "+ret.getType() );
478 }
479 return ret;
480 }
481
482 public LocalVarNode makeLocalVarNode( Object value, Type type, SootMethod method ) {
483 if( opts.rta() ) {
484 value = null;
485 type = RefType.v("java.lang.Object");
486 method = null;
487 } else if( value instanceof Local ) {
488 Local val = (Local) value;
489 if( val.getNumber() == 0 ) Scene.v().getLocalNumberer().add(val);
490 LocalVarNode ret = (LocalVarNode) localToNodeMap.get( val );
491 if( ret == null ) {
492 localToNodeMap.put( (Local) value,
493 ret = new LocalVarNode( this, value, type, method ) );
494 addNodeTag( ret, method );
495 } else if( !( ret.getType().equals( type ) ) ) {
496 throw new RuntimeException ( "Value "+value+" of type "+type+
497 " previously had type "+ret.getType() );
498 }
499 return ret;
500 }
501 LocalVarNode ret = (LocalVarNode) valToLocalVarNode.get( value );
502 if( ret == null ) {
503 valToLocalVarNode.put( value,
504 ret = new LocalVarNode( this, value, type, method ) );
505 addNodeTag( ret, method );
506 } else if( !( ret.getType().equals( type ) ) ) {
507 throw new RuntimeException ( "Value "+value+" of type "+type+
508 " previously had type "+ret.getType() );
509 }
510 return ret;
511 }
512
514 public ContextVarNode findContextVarNode( Object baseValue, Context context ) {
515 LocalVarNode base = findLocalVarNode( baseValue );
516 if( base == null ) return null;
517 return base.context( context );
518 }
519
521 public ContextVarNode makeContextVarNode( Object baseValue, Type baseType,
522 Context context, SootMethod method ) {
523 LocalVarNode base = makeLocalVarNode( baseValue, baseType, method );
524 return makeContextVarNode( base, context );
525 }
526
528 public ContextVarNode makeContextVarNode( LocalVarNode base, Context context ) {
529 ContextVarNode ret = base.context( context );
530 if( ret == null ) {
531 ret = new ContextVarNode( this, base, context );
532 addNodeTag( ret, base.getMethod() );
533 }
534 return ret;
535 }
536
538 public FieldRefNode findLocalFieldRefNode( Object baseValue, SparkField field ) {
539 VarNode base = findLocalVarNode( baseValue );
540 if( base == null ) return null;
541 return base.dot( field );
542 }
543
545 public FieldRefNode findGlobalFieldRefNode( Object baseValue, SparkField field ) {
546 VarNode base = findGlobalVarNode( baseValue );
547 if( base == null ) return null;
548 return base.dot( field );
549 }
550
552 public FieldRefNode makeLocalFieldRefNode( Object baseValue, Type baseType,
553 SparkField field, SootMethod method ) {
554 VarNode base = makeLocalVarNode( baseValue, baseType, method );
555 return makeFieldRefNode( base, field );
556 }
557
559 public FieldRefNode makeGlobalFieldRefNode( Object baseValue, Type baseType,
560 SparkField field ) {
561 VarNode base = makeGlobalVarNode( baseValue, baseType );
562 return makeFieldRefNode( base, field );
563 }
564
566 public FieldRefNode makeFieldRefNode( VarNode base, SparkField field ) {
567 FieldRefNode ret = base.dot( field );
568 if( ret == null ) {
569 ret = new FieldRefNode( this, base, field );
570 if( base instanceof LocalVarNode ) {
571 addNodeTag( ret, ((LocalVarNode) base).getMethod() );
572 } else {
573 addNodeTag( ret, null );
574 }
575 }
576 return ret;
577 }
578
580 public AllocDotField findAllocDotField( AllocNode an, SparkField field ) {
581 return an.dot( field );
582 }
583
585 public AllocDotField makeAllocDotField( AllocNode an, SparkField field ) {
586 AllocDotField ret = an.dot( field );
587 if( ret == null ) {
588 ret = new AllocDotField( this, an, field );
589 }
590 return ret;
591 }
592
593 public boolean addSimpleEdge( VarNode from, VarNode to ) {
594 boolean ret = false;
595 if( doAddSimpleEdge( from, to ) ) {
596 edgeQueue.add( from );
597 edgeQueue.add( to );
598 ret = true;
599 }
600 if( opts.simple_edges_bidirectional() ) {
601 if( doAddSimpleEdge( to, from ) ) {
602 edgeQueue.add( to );
603 edgeQueue.add( from );
604 ret = true;
605 }
606 }
607 return ret;
608 }
609
610 public boolean addStoreEdge( VarNode from, FieldRefNode to ) {
611 if( !opts.rta() ) {
612 if( doAddStoreEdge( from, to ) ) {
613 edgeQueue.add( from );
614 edgeQueue.add( to );
615 return true;
616 }
617 }
618 return false;
619 }
620
621 public boolean addLoadEdge( FieldRefNode from, VarNode to ) {
622 if( !opts.rta() ) {
623 if( doAddLoadEdge( from, to ) ) {
624 edgeQueue.add( from );
625 edgeQueue.add( to );
626 return true;
627 }
628 }
629 return false;
630 }
631
632 public boolean addAllocEdge( AllocNode from, VarNode to ) {
633 FastHierarchy fh = typeManager.getFastHierarchy();
634 if( fh == null || to.getType() == null
635 || fh.canStoreType( from.getType(), to.getType() ) ) {
636 if( doAddAllocEdge( from, to ) ) {
637 edgeQueue.add( from );
638 edgeQueue.add( to );
639 return true;
640 }
641 }
642 return false;
643 }
644
645
646 public final boolean addEdge( Node from, Node to ) {
647 from = from.getReplacement();
648 to = to.getReplacement();
649 if( from instanceof VarNode ) {
650 if( to instanceof VarNode ) {
651 return addSimpleEdge( (VarNode) from, (VarNode) to );
652 } else {
653 return addStoreEdge( (VarNode) from, (FieldRefNode) to );
654 }
655 } else if( from instanceof FieldRefNode ) {
656 return addLoadEdge( (FieldRefNode) from, (VarNode) to );
657
658 } else {
659 return addAllocEdge( (AllocNode) from, (VarNode) to );
660 }
661 }
662
663 protected ChunkedQueue edgeQueue = new ChunkedQueue();
664 public QueueReader edgeReader() { return edgeQueue.reader(); }
665
666 public int getNumAllocNodes() {
667 return allocNodeNumberer.size();
668 }
669 public TypeManager getTypeManager() {
670 return typeManager;
671 }
672
673 public void setOnFlyCallGraph( OnFlyCallGraph ofcg ) { this.ofcg = ofcg; }
674 public OnFlyCallGraph getOnFlyCallGraph() { return ofcg; }
675 public OnFlyCallGraph ofcg() { return ofcg; }
676
678 public void addDereference( VarNode base ) {
679 dereferences.add( base );
680 }
681
682
683 public List getDereferences() {
684 return dereferences;
685 }
686
687 public Map getNodeTags() {
688 return nodeToTag;
689 }
690
691 private ArrayNumberer allocNodeNumberer = new ArrayNumberer();
692 public ArrayNumberer getAllocNodeNumberer() { return allocNodeNumberer; }
693 private ArrayNumberer varNodeNumberer = new ArrayNumberer();
694 public ArrayNumberer getVarNodeNumberer() { return varNodeNumberer; }
695 private ArrayNumberer fieldRefNodeNumberer = new ArrayNumberer();
696 public ArrayNumberer getFieldRefNodeNumberer() { return fieldRefNodeNumberer; }
697 private ArrayNumberer allocDotFieldNodeNumberer = new ArrayNumberer();
698 public ArrayNumberer getAllocDotFieldNodeNumberer() { return allocDotFieldNodeNumberer; }
699
700
701
702 public SparkOptions getOpts() { return opts; }
703
704 final public void addCallTarget( Edge e ) {
705 if( !e.passesParameters() ) return;
706 MethodPAG srcmpag = MethodPAG.v( this, e.src() );
707 MethodPAG tgtmpag = MethodPAG.v( this, e.tgt() );
708 if( e.isExplicit() || e.kind() == Kind.THREAD ) {
709 addCallTarget( srcmpag, tgtmpag, (Stmt) e.srcUnit(),
710 e.srcCtxt(), e.tgtCtxt() );
711 } else {
712 if( e.kind() == Kind.PRIVILEGED ) {
713
717 InvokeExpr ie = e.srcStmt().getInvokeExpr();
718
719 Node parm = srcmpag.nodeFactory().getNode( ie.getArg(0) );
720 parm = srcmpag.parameterize( parm, e.srcCtxt() );
721 parm = parm.getReplacement();
722
723 Node thiz = tgtmpag.nodeFactory().caseThis();
724 thiz = tgtmpag.parameterize( thiz, e.tgtCtxt() );
725 thiz = thiz.getReplacement();
726
727 addEdge( parm, thiz );
728
729 if( e.srcUnit() instanceof AssignStmt ) {
730 AssignStmt as = (AssignStmt) e.srcUnit();
731
732 Node ret = tgtmpag.nodeFactory().caseRet();
733 ret = tgtmpag.parameterize( ret, e.tgtCtxt() );
734 ret = ret.getReplacement();
735
736 Node lhs = srcmpag.nodeFactory().getNode(as.getLeftOp());
737 lhs = srcmpag.parameterize( lhs, e.srcCtxt() );
738 lhs = lhs.getReplacement();
739
740 addEdge( ret, lhs );
741 }
742 } else if( e.kind() == Kind.FINALIZE ) {
743 Node srcThis = srcmpag.nodeFactory().caseThis();
744 srcThis = srcmpag.parameterize( srcThis, e.srcCtxt() );
745 srcThis = srcThis.getReplacement();
746
747 Node tgtThis = tgtmpag.nodeFactory().caseThis();
748 tgtThis = tgtmpag.parameterize( tgtThis, e.tgtCtxt() );
749 tgtThis = tgtThis.getReplacement();
750
751 addEdge( srcThis, tgtThis );
752 } else if( e.kind() == Kind.NEWINSTANCE ) {
753 Stmt s = (Stmt) e.srcUnit();
754 InstanceInvokeExpr iie = (InstanceInvokeExpr) s.getInvokeExpr();
755
756 Node cls = srcmpag.nodeFactory().getNode( iie.getBase() );
757 cls = srcmpag.parameterize( cls, e.srcCtxt() );
758 cls = cls.getReplacement();
759 Node newObject = nodeFactory.caseNewInstance( (VarNode) cls );
760
761 Node initThis = tgtmpag.nodeFactory().caseThis();
762 initThis = tgtmpag.parameterize( initThis, e.tgtCtxt() );
763 initThis = initThis.getReplacement();
764
765 addEdge( newObject, initThis );
766 } else {
767 throw new RuntimeException ( "Unhandled edge "+e );
768 }
769 }
770 }
771
772
773
777 final public void addCallTarget( MethodPAG srcmpag,
778 MethodPAG tgtmpag,
779 Stmt s,
780 Context srcContext,
781 Context tgtContext ) {
782 MethodNodeFactory srcnf = srcmpag.nodeFactory();
783 MethodNodeFactory tgtnf = tgtmpag.nodeFactory();
784 InvokeExpr ie = (InvokeExpr) s.getInvokeExpr();
785 int numArgs = ie.getArgCount();
786 for( int i = 0; i < numArgs; i++ ) {
787 Value arg = ie.getArg( i );
788 if( !( arg.getType() instanceof RefLikeType ) ) continue;
789 if( arg instanceof NullConstant ) continue;
790
791 Node argNode = srcnf.getNode( arg );
792 argNode = srcmpag.parameterize( argNode, srcContext );
793 argNode = argNode.getReplacement();
794
795 Node parm = tgtnf.caseParm( i );
796 parm = tgtmpag.parameterize( parm, tgtContext );
797 parm = parm.getReplacement();
798
799 addEdge( argNode, parm );
800 }
801 if( ie instanceof InstanceInvokeExpr ) {
802 InstanceInvokeExpr iie = (InstanceInvokeExpr) ie;
803
804 Node baseNode = srcnf.getNode( iie.getBase() );
805 baseNode = srcmpag.parameterize( baseNode, srcContext );
806 baseNode = baseNode.getReplacement();
807
808 Node thisRef = tgtnf.caseThis();
809 thisRef = tgtmpag.parameterize( thisRef, tgtContext );
810 thisRef = thisRef.getReplacement();
811 addEdge( baseNode, thisRef );
812 }
813 if( s instanceof AssignStmt ) {
814 Value dest = ( (AssignStmt) s ).getLeftOp();
815 if( dest.getType() instanceof RefLikeType && !(dest instanceof NullConstant) ) {
816
817 Node destNode = srcnf.getNode( dest );
818 destNode = srcmpag.parameterize( destNode, srcContext );
819 destNode = destNode.getReplacement();
820
821 Node retNode = tgtnf.caseRet();
822 retNode = tgtmpag.parameterize( retNode, tgtContext );
823 retNode = retNode.getReplacement();
824
825 addEdge( retNode, destNode );
826 }
827 }
828 }
829
830
831 protected SparkOptions opts;
832
833 protected Map simple = new HashMap();
834 protected Map load = new HashMap();
835 protected Map store = new HashMap();
836 protected Map alloc = new HashMap();
837
838 protected Map simpleInv = new HashMap();
839 protected Map loadInv = new HashMap();
840 protected Map storeInv = new HashMap();
841 protected Map allocInv = new HashMap();
842
843 protected boolean addToMap( Map m, Node key, Node value ) {
844 Object valueList = m.get( key );
845
846 if( valueList == null ) {
847 m.put( key, valueList = new HashSet(4) );
848 } else if( !(valueList instanceof Set) ) {
849 Node[] ar = (Node[]) valueList;
850 HashSet vl = new HashSet(ar.length+4);
851 m.put( key, vl );
852 for( int i = 0; i < ar.length; i++ ) vl.add( ar[i] );
853 return vl.add( value );
854
866 }
867 return ((Set) valueList).add( value );
868 }
869 private Map valToLocalVarNode = new HashMap(1000);
870 private Map valToGlobalVarNode = new HashMap(1000);
871 private Map valToAllocNode = new HashMap(1000);
872 private OnFlyCallGraph ofcg;
873 private ArrayList dereferences = new ArrayList();
874 protected TypeManager typeManager;
875 private LargeNumberedMap localToNodeMap = new LargeNumberedMap( Scene.v().getLocalNumberer() );
876 public int maxFinishNumber = 0;
877 private Map nodeToTag;
878 private GlobalNodeFactory nodeFactory = new GlobalNodeFactory(this);
879 public GlobalNodeFactory nodeFactory() { return nodeFactory; }
880 public NativeMethodDriver nativeMethodDriver;
881
882 }
883
884 |
Popular Tags |
Java API By Example, From Geeks To Geeks.