1 package Analysis.Disjoint;
11 public class DefiniteReachState {
15 // Maps two variables to an edge (x, y, e) to an unused value when the
16 // object of x is already reachable from the object of y, and the
17 // set of edges conservatively gives the path.
18 // NOTE: Use EdgeKey instead of edges because this analysis's
19 // scope is beyond the scope of a single reach graph.
20 private static MultiViewMapBuilder<Object> RBuilder;
21 private static BitSet viewRfull;
22 private static BitSet viewR0;
23 private static BitSet viewR1;
24 private static BitSet viewR2;
25 private static BitSet viewR01;
26 private MultiViewMap<Object> R;
31 // Tracks whether the analysis must know the definite reachability
32 // information of a given variable.
33 private enum DefReachKnown {
37 private Map<TempDescriptor, DefReachKnown> Rs;
40 // Fu (field upstream)
42 // Maps a variable that points to object o0 to the
43 // set of variables that point to objects o1...oN
44 // that have a reference to o0.
45 private class FuSource {
46 DefReachKnown isKnown;
47 TempDescriptor knownSrc;
49 this.isKnown = DefReachKnown.UNKNOWN;
52 public FuSource( TempDescriptor src ) {
53 assert( src != null );
54 this.isKnown = DefReachKnown.KNOWN;
57 public boolean equals( Object o ) {
58 if( !(o instanceof FuSource) ) {
61 FuSource fus = (FuSource)o;
63 this.isKnown == fus.isKnown &&
64 this.knownSrc == fus.knownSrc;
66 public int hashCode() {
68 if( isKnown == DefReachKnown.KNOWN ) {
71 if( knownSrc != null ) {
72 hash ^= knownSrc.hashCode();
77 private static MultiViewMapBuilder<Object> FuBuilder;
78 private static BitSet viewFufull;
79 private static BitSet viewFu0;
80 private static BitSet viewFu1;
81 private MultiViewMap<Object> Fu;
84 // Fd (field downstream)
86 // Entries <x, f, y> mean x.f points directly at what
88 public class FdEntry {
92 public FdEntry( TempDescriptor y,
100 private static MultiViewMapBuilder<Object> FdBuilder;
101 private static BitSet viewFd0;
102 private static BitSet viewFd2;
103 private MultiViewMap<Object> Fd;
109 // call before instantiating this class
110 static public void initBuilders() {
113 new MultiViewMapBuilder<Object>( new Class[] {
114 TempDescriptor.class,
115 TempDescriptor.class,
118 viewRfull = RBuilder.getFullView();
119 viewR0 = RBuilder.addPartialView( 0 );
120 viewR1 = RBuilder.addPartialView( 1 );
121 viewR2 = RBuilder.addPartialView( 2 );
122 viewR01 = RBuilder.addPartialView( 0, 1 );
123 RBuilder.setCheckTypes( true );
124 RBuilder.setCheckConsistency( true );
128 new MultiViewMapBuilder<Object>( new Class[] {
129 TempDescriptor.class,
132 viewFufull = FuBuilder.getFullView();
133 viewFu0 = FuBuilder.addPartialView( 0 );
134 viewFu1 = FuBuilder.addPartialView( 1 );
135 FuBuilder.setCheckTypes( true );
136 FuBuilder.setCheckConsistency( true );
140 new MultiViewMapBuilder<Object>( new Class[] {
141 TempDescriptor.class,
142 FieldDescriptor.class,
143 TempDescriptor.class},
145 viewFd0 = FdBuilder.addPartialView( 0 );
146 viewFd2 = FdBuilder.addPartialView( 2 );
147 FdBuilder.setCheckTypes( true );
148 FdBuilder.setCheckConsistency( true );
153 public DefiniteReachState( DefiniteReachState toCopy ) {
154 this.R = toCopy.R.clone( RBuilder );
155 this.Rs = new HashMap<TempDescriptor, DefReachKnown>( toCopy.Rs );
156 this.Fu = toCopy.Fu.clone( FuBuilder );
157 this.Fd = toCopy.Fd.clone( FdBuilder );
161 public DefiniteReachState() {
162 R = RBuilder.build();
163 Rs = new HashMap<TempDescriptor, DefReachKnown>();
164 Fu = FuBuilder.build();
165 Fd = FdBuilder.build();
171 public boolean isAlreadyReachable( TempDescriptor a,
174 boolean case1 = !R.get( viewR01, MultiKey.factory( a, b ) ).isEmpty();
176 boolean case3 = false;
177 if( Rs.get( b ) != null &&
178 Rs.get( b ) == DefReachKnown.KNOWN &&
179 Fu.get( viewFufull, MultiKey.factory( b, new FuSource() ) ).isEmpty()
181 boolean allEntriesOk = true;
182 for( MultiKey fullKeyB : Fu.get( viewFu0,
183 MultiKey.factory( b ) ).keySet()
187 ((FuSource)fullKeyB.get( 1 )).knownSrc
190 allEntriesOk = false;
194 case3 = allEntriesOk;
197 return case1 || case3;
202 public Set<FdEntry> edgesToElidePropagation( TempDescriptor x,
204 // return the set of edges that definite reach analysis tells
205 // us we can elide propagating reach info across during the
208 Set<FdEntry> out = new HashSet<FdEntry>();
210 // we have to know something about y
211 DefReachKnown known = Rs.get( y );
212 if( known == null || known == DefReachKnown.UNKNOWN ) {
216 // find all 'y points at' entries in Fd
217 MultiKey keyY = MultiKey.factory( y );
218 Map<MultiKey, Object> mapY0 = Fd.get( viewFd0, keyY );
220 for( MultiKey fullKeyY : mapY0.keySet() ) {
221 // if y.f0 points at z, and z is already reachable from x,
222 // include the edge y.f0->z
223 FieldDescriptor f0 = (FieldDescriptor) fullKeyY.get( 1 );
224 TempDescriptor z = (TempDescriptor) fullKeyY.get( 2 );
226 if( isAlreadyReachable( z, x ) ) {
227 out.add( new FdEntry( y, f0, z ) );
237 public void methodEntry( Set<TempDescriptor> parameters ) {
238 methodEntryR ( parameters );
239 methodEntryRs( parameters );
240 methodEntryFu( parameters );
241 methodEntryFd( parameters );
244 public void copy( TempDescriptor x,
252 public void load( TempDescriptor x,
255 Set<EdgeKey> edgeKeysForLoad ) {
257 loadR ( x, y, f, edgeKeysForLoad );
258 loadRs( x, y, f, edgeKeysForLoad );
259 loadFu( x, y, f, edgeKeysForLoad );
260 loadFd( x, y, f, edgeKeysForLoad );
263 public void store( TempDescriptor x,
266 Set<EdgeKey> edgeKeysRemoved,
267 Set<EdgeKey> edgeKeysAdded ) {
269 storeR ( x, f, y, edgeKeysRemoved, edgeKeysAdded );
270 storeRs( x, f, y, edgeKeysRemoved, edgeKeysAdded );
271 storeFu( x, f, y, edgeKeysRemoved, edgeKeysAdded );
272 storeFd( x, f, y, edgeKeysRemoved, edgeKeysAdded );
275 public void newObject( TempDescriptor x ) {
282 public void methodCall( TempDescriptor retVal ) {
283 methodCallR ( retVal );
284 methodCallRs( retVal );
285 methodCallFu( retVal );
286 methodCallFd( retVal );
289 public void merge( DefiniteReachState that ) {
301 public void methodEntryR( Set<TempDescriptor> parameters ) {
305 public void copyR( TempDescriptor x,
307 // consider that x and y can be the same, so do the
308 // parts of the update in the right order:
310 // first get all info for update
311 MultiKey keyY = MultiKey.factory( y );
312 Map<MultiKey, Object> mapY0 = R.get( viewR0, keyY );
313 Map<MultiKey, Object> mapY1 = R.get( viewR1, keyY );
315 // then remove anything
316 MultiKey keyX = MultiKey.factory( x );
317 R.remove( viewR0, keyX );
318 R.remove( viewR1, keyX );
320 // then insert new stuff
321 for( MultiKey fullKeyY : mapY0.keySet() ) {
322 MultiKey fullKeyX = MultiKey.factory( x,
325 R.put( fullKeyX, MultiViewMap.dummyValue );
327 for( MultiKey fullKeyY : mapY1.keySet() ) {
328 MultiKey fullKeyX = MultiKey.factory( fullKeyY.get( 0 ),
331 R.put( fullKeyX, MultiViewMap.dummyValue );
335 public void loadR( TempDescriptor x,
338 Set<EdgeKey> edgeKeysForLoad ) {
339 // consider that x and y can be the same, so do the
340 // parts of the update in the right order:
342 // first get all info for update
343 MultiKey keyY = MultiKey.factory( y );
344 Map<MultiKey, Object> mapY0 = R.get( viewR0, keyY );
346 // then remove anything
347 MultiKey keyX = MultiKey.factory( x );
348 R.remove( viewR0, keyX );
349 R.remove( viewR1, keyX );
351 // then insert new stuff
352 for( EdgeKey e : edgeKeysForLoad ) {
353 R.put( MultiKey.factory( x, y, e ), MultiViewMap.dummyValue );
355 for( MultiKey fullKeyY : mapY0.keySet() ) {
356 R.put( MultiKey.factory( x,
359 MultiViewMap.dummyValue );
361 R.put( MultiKey.factory( x,
364 MultiViewMap.dummyValue );
369 public void storeR( TempDescriptor x,
372 Set<EdgeKey> edgeKeysRemoved,
373 Set<EdgeKey> edgeKeysAdded ) {
375 for( EdgeKey edgeKeyWZ : edgeKeysRemoved ) {
376 R.remove( viewR2, MultiKey.factory( edgeKeyWZ ) );
379 for( EdgeKey edgeKeyXY : edgeKeysAdded ) {
380 R.put( MultiKey.factory( y, x, edgeKeyXY ), MultiViewMap.dummyValue );
384 public void newObjectR( TempDescriptor x ) {
385 MultiKey keyX = MultiKey.factory( x );
386 R.remove( viewR0, keyX );
387 R.remove( viewR1, keyX );
390 public void methodCallR( TempDescriptor retVal ) {
391 MultiKey keyRetVal = MultiKey.factory( retVal );
392 R.remove( viewR0, keyRetVal );
393 R.remove( viewR1, keyRetVal );
396 public void mergeR( DefiniteReachState that ) {
397 for( MultiKey key : this.R.get().keySet() ) {
398 if( that.R.get( viewRfull, key ).isEmpty() ) {
399 this.R.remove( viewRfull, key );
411 public void methodEntryRs( Set<TempDescriptor> parameters ) {
413 for( TempDescriptor p : parameters ) {
414 Rs.put( p, DefReachKnown.UNKNOWN );
418 public void copyRs( TempDescriptor x,
420 DefReachKnown valRs = Rs.get( y );
421 assert( valRs != null );
425 public void loadRs( TempDescriptor x,
428 Set<EdgeKey> edgeKeysForLoad ) {
429 Rs.put( x, DefReachKnown.UNKNOWN );
432 public void storeRs( TempDescriptor x,
435 Set<EdgeKey> edgeKeysRemoved,
436 Set<EdgeKey> edgeKeysAdded ) {
439 public void newObjectRs( TempDescriptor x ) {
440 Rs.put( x, DefReachKnown.KNOWN );
443 public void methodCallRs( TempDescriptor retVal ) {
444 Rs.put( retVal, DefReachKnown.UNKNOWN );
447 private void mergeRs( DefiniteReachState that ) {
448 Set<TempDescriptor> allVars = new HashSet<TempDescriptor>();
449 allVars.addAll( this.Rs.keySet() );
450 allVars.addAll( that.Rs.keySet() );
451 for( TempDescriptor x : allVars ) {
452 DefReachKnown vThis = this.Rs.get( x );
453 DefReachKnown vThat = that.Rs.get( x );
454 if( vThis != null && vThis.equals( DefReachKnown.KNOWN ) &&
455 vThat != null && vThat.equals( DefReachKnown.KNOWN ) ) {
456 this.Rs.put( x, DefReachKnown.KNOWN );
458 this.Rs.put( x, DefReachKnown.UNKNOWN );
470 public void methodEntryFu( Set<TempDescriptor> parameters ) {
474 public void copyFu( TempDescriptor x,
476 // consider that x and y can be the same, so do the
477 // parts of the update in the right order:
479 // first get all info for update
480 MultiKey keyY = MultiKey.factory( y );
481 MultiKey keyYsrc = MultiKey.factory( new FuSource( y ) );
482 Map<MultiKey, Object> mapY0 = Fu.get( viewFu0, keyY );
483 Map<MultiKey, Object> mapY1 = Fu.get( viewFu1, keyYsrc );
485 MultiKey keyXsrc = MultiKey.factory( new FuSource( x ) );
486 Map<MultiKey, Object> mapX1 = Fu.get( viewFu1, keyXsrc );
488 // then remove anything
489 MultiKey keyX = MultiKey.factory( x );
490 Fu.remove( viewFu0, keyX );
491 Fu.remove( viewFu1, keyXsrc );
493 // then insert new stuff
494 for( MultiKey fullKeyY : mapY0.keySet() ) {
495 MultiKey fullKeyX = MultiKey.factory( x,
497 Fu.put( fullKeyX, MultiViewMap.dummyValue );
499 for( MultiKey fullKeyY : mapY1.keySet() ) {
500 MultiKey fullKeyX = MultiKey.factory( fullKeyY.get( 0 ),
502 Fu.put( fullKeyX, MultiViewMap.dummyValue );
504 for( MultiKey fullKeyXsrc : mapX1.keySet() ) {
505 Fu.put( MultiKey.factory( fullKeyXsrc.get( 0 ),
507 MultiViewMap.dummyValue );
511 public void loadFu( TempDescriptor x,
514 Set<EdgeKey> edgeKeysForLoad ) {
516 // first get all info for update
517 MultiKey keyXsrc = MultiKey.factory( new FuSource( x ) );
518 Map<MultiKey, Object> mapX1 = Fu.get( viewFu1, keyXsrc );
520 MultiKey keyX = MultiKey.factory( x );
521 // then remove anything
522 Fu.remove( viewFu0, keyX );
523 Fu.remove( viewFu1, keyXsrc );
525 // then insert new stuff
526 for( MultiKey fullKeyXsrc : mapX1.keySet() ) {
527 Fu.put( MultiKey.factory( fullKeyXsrc.get( 0 ),
529 MultiViewMap.dummyValue );
533 public void storeFu( TempDescriptor x,
536 Set<EdgeKey> edgeKeysRemoved,
537 Set<EdgeKey> edgeKeysAdded ) {
539 Fu.put( MultiKey.factory( y, new FuSource( x ) ),
540 MultiViewMap.dummyValue );
543 public void newObjectFu( TempDescriptor x ) {
544 MultiKey keyXsrc = MultiKey.factory( new FuSource( x ) );
545 Map<MultiKey, Object> mapX1 = Fu.get( viewFu1, keyXsrc );
547 MultiKey keyX = MultiKey.factory( x );
548 Fu.remove( viewFu0, keyX );
549 Fu.remove( viewFu1, keyXsrc );
551 for( MultiKey fullKeyXsrc : mapX1.keySet() ) {
552 Fu.put( MultiKey.factory( fullKeyXsrc.get( 0 ),
554 MultiViewMap.dummyValue );
558 public void methodCallFu( TempDescriptor retVal ) {
559 MultiKey keyRetValsrc = MultiKey.factory( new FuSource( retVal ) );
560 Map<MultiKey, Object> mapRetVal1 = Fu.get( viewFu1, keyRetValsrc );
562 MultiKey keyRetVal = MultiKey.factory( retVal );
563 Fu.remove( viewFu0, keyRetVal );
564 Fu.remove( viewFu1, keyRetValsrc );
566 for( MultiKey fullKeyRetValsrc : mapRetVal1.keySet() ) {
567 Fu.put( MultiKey.factory( fullKeyRetValsrc.get( 0 ),
569 MultiViewMap.dummyValue );
573 public void mergeFu( DefiniteReachState that ) {
574 this.Fu.merge( that.Fu );
582 public void methodEntryFd( Set<TempDescriptor> parameters ) {
586 public void copyFd( TempDescriptor x,
588 // consider that x and y can be the same, so do the
589 // parts of the update in the right order:
591 // first get all info for update
592 MultiKey keyY = MultiKey.factory( y );
593 Map<MultiKey, Object> mapY0 = Fd.get( viewFd0, keyY );
594 Map<MultiKey, Object> mapY2 = Fd.get( viewFd2, keyY );
596 // then remove anything
597 MultiKey keyX = MultiKey.factory( x );
598 Fd.remove( viewFd0, keyX );
599 Fd.remove( viewFd2, keyX );
601 // then insert new stuff
602 for( MultiKey fullKeyY : mapY0.keySet() ) {
603 MultiKey fullKeyX = MultiKey.factory( x,
606 Fd.put( fullKeyX, MultiViewMap.dummyValue );
608 for( MultiKey fullKeyY : mapY2.keySet() ) {
609 MultiKey fullKeyX = MultiKey.factory( fullKeyY.get( 0 ),
612 Fd.put( fullKeyX, MultiViewMap.dummyValue );
616 public void loadFd( TempDescriptor x,
619 Set<EdgeKey> edgeKeysForLoad ) {
621 MultiKey keyX = MultiKey.factory( x );
622 Fd.remove( viewFd0, keyX );
623 Fd.remove( viewFd2, keyX );
626 public void storeFd( TempDescriptor x,
629 Set<EdgeKey> edgeKeysFdemoved,
630 Set<EdgeKey> edgeKeysAdded ) {
631 Fd.put( MultiKey.factory( x, f, y ),
632 MultiViewMap.dummyValue );
635 public void newObjectFd( TempDescriptor x ) {
636 MultiKey keyX = MultiKey.factory( x );
637 Fd.remove( viewFd0, keyX );
638 Fd.remove( viewFd2, keyX );
641 public void methodCallFd( TempDescriptor retVal ) {
642 MultiKey keyRetVal = MultiKey.factory( retVal );
643 Fd.remove( viewFd0, keyRetVal );
644 Fd.remove( viewFd2, keyRetVal );
647 public void mergeFd( DefiniteReachState that ) {
648 this.Fd.merge( that.Fd );
662 public boolean equals( Object o ) {
669 if( !(o instanceof DefiniteReachState) ) {
672 DefiniteReachState that = (DefiniteReachState) o;
679 public int hashCode() {
685 public void writeState( String outputName ) {
687 BufferedWriter bw = new BufferedWriter( new FileWriter( "defReach-"+outputName+".txt" ) );
688 bw.write( this.toString() );
690 } catch( IOException e ) {
691 System.out.println( "ERROR writing definite reachability state:\n "+e );
696 public String toString() {
697 StringBuilder s = new StringBuilder();
699 s.append( "R = {\n" );
700 s.append( R.toString( 2 ) );
703 s.append( "Rs = {\n" );
704 for( TempDescriptor x : Rs.keySet() ) {
705 s.append( " "+x+"->"+Rs.get( x )+"\n" );
709 s.append( "Fd = {\n" );
710 s.append( Fd.toString( 2 ) );