Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java

   1 package Analysis.OwnershipAnalysis;
   2
   3 import IR.*;
   4 import IR.Flat.*;
   5 import java.util.*;
   6 import java.io.*;
   7
   8
   9 public class ReachabilitySet extends Canonical {
  10
  11   private HashSet<TokenTupleSet> possibleReachabilities;
  12
  13   public ReachabilitySet() {
  14     possibleReachabilities = new HashSet<TokenTupleSet>();
  15   }
  16
  17   public ReachabilitySet(TokenTupleSet tts) {
  18     this();
  19     assert tts != null;
  20     possibleReachabilities.add(tts);
  21   }
  22
  23   public ReachabilitySet(TokenTuple tt) {
  24     // can't assert before calling this(), it will
  25     // do the checking though
  26     this( new TokenTupleSet(tt).makeCanonical() );
  27   }
  28
  29   public ReachabilitySet(HashSet<TokenTupleSet> possibleReachabilities) {
  30     assert possibleReachabilities != null;
  31     this.possibleReachabilities = possibleReachabilities;
  32   }
  33
  34   public ReachabilitySet(ReachabilitySet rs) {
  35     assert rs != null;
  36     // okay to clone, ReachabilitySet should be canonical
  37     possibleReachabilities = (HashSet<TokenTupleSet>)rs.possibleReachabilities.clone();
  38   }
  39
  40
  41   public ReachabilitySet makeCanonical() {
  42     return (ReachabilitySet) Canonical.makeCanonical(this);
  43   }
  44
  45   public Iterator<TokenTupleSet> iterator() {
  46     return possibleReachabilities.iterator();
  47   }
  48
  49
  50   public int size() {
  51     return possibleReachabilities.size();
  52   }
  53
  54   public boolean isEmpty() {
  55     return possibleReachabilities.isEmpty();
  56   }
  57
  58   public boolean contains(TokenTupleSet tts) {
  59     assert tts != null;
  60     return possibleReachabilities.contains(tts);
  61   }
  62
  63   public boolean containsTuple(TokenTuple tt) {
  64     Iterator itr = iterator();
  65     while( itr.hasNext() ) {
  66       TokenTupleSet tts = (TokenTupleSet) itr.next();
  67       if( tts.containsTuple(tt) ) {
  68         return true;
  69       }
  70     }
  71     return false;
  72   }
  73
  74   public boolean containsTupleSetWithBoth(TokenTuple tt1, TokenTuple tt2) {
  75     Iterator itr = iterator();
  76     while( itr.hasNext() ) {
  77       TokenTupleSet tts = (TokenTupleSet) itr.next();
  78       if( tts.containsTuple(tt1) && tts.containsTuple(tt2) ) {
  79         return true;
  80       }
  81     }
  82     return false;
  83   }
  84
  85   public ReachabilitySet union(ReachabilitySet rsIn) {
  86     assert rsIn != null;
  87
  88     ReachabilitySet rsOut = new ReachabilitySet(this);
  89     rsOut.possibleReachabilities.addAll(rsIn.possibleReachabilities);
  90     return rsOut.makeCanonical();
  91   }
  92
  93   public ReachabilitySet union(TokenTupleSet ttsIn) {
  94     assert ttsIn != null;
  95
  96     ReachabilitySet rsOut = new ReachabilitySet(this);
  97     rsOut.possibleReachabilities.add(ttsIn);
  98     return rsOut.makeCanonical();
  99   }
 100
 101   public ReachabilitySet intersection(ReachabilitySet rsIn) {
 102     assert rsIn != null;
 103
 104     ReachabilitySet rsOut = new ReachabilitySet();
 105
 106     Iterator i = this.iterator();
 107     while( i.hasNext() ) {
 108       TokenTupleSet tts = (TokenTupleSet) i.next();
 109       if( rsIn.possibleReachabilities.contains(tts) ) {
 110         rsOut.possibleReachabilities.add(tts);
 111       }
 112     }
 113
 114     return rsOut.makeCanonical();
 115   }
 116
 117
 118   public ReachabilitySet add(TokenTupleSet tts) {
 119     assert tts != null;
 120     ReachabilitySet rsOut = new ReachabilitySet(tts);
 121     return rsOut.union(this);
 122   }
 123
 124
 125   public ChangeTupleSet unionUpArityToChangeSet(ReachabilitySet rsIn) {
 126     assert rsIn != null;
 127
 128     ChangeTupleSet ctsOut = new ChangeTupleSet();
 129
 130     Iterator itrO = this.iterator();
 131     while( itrO.hasNext() ) {
 132       TokenTupleSet o = (TokenTupleSet) itrO.next();
 133
 134       Iterator itrR = rsIn.iterator();
 135       while( itrR.hasNext() ) {
 136         TokenTupleSet r = (TokenTupleSet) itrR.next();
 137
 138         TokenTupleSet theUnion = new TokenTupleSet();
 139
 140         Iterator itrRelement = r.iterator();
 141         while( itrRelement.hasNext() ) {
 142           TokenTuple ttR = (TokenTuple) itrRelement.next();
 143           TokenTuple ttO = o.containsToken( ttR.getToken() );
 144
 145           if( ttO != null ) {
 146             theUnion = theUnion.union( new TokenTupleSet( ttR.unionArity(ttO) ) ).makeCanonical();
 147           } else {
 148             theUnion = theUnion.union( new TokenTupleSet( ttR                 ) ).makeCanonical();
 149           }
 150         }
 151
 152         Iterator itrOelement = o.iterator();
 153         while( itrOelement.hasNext() ) {
 154           TokenTuple ttO = (TokenTuple) itrOelement.next();
 155           TokenTuple ttR = theUnion.containsToken( ttO.getToken() );
 156
 157           if( ttR == null ) {
 158             theUnion = theUnion.union( new TokenTupleSet(ttO) ).makeCanonical();
 159           }
 160         }
 161
 162         if( !theUnion.isEmpty() ) {
 163           ctsOut = ctsOut.union( new ChangeTupleSet( new ChangeTuple(o, theUnion) ) );
 164         }
 165       }
 166     }
 167
 168     return ctsOut.makeCanonical();
 169   }
 170
 171
 172   public ReachabilitySet ageTokens(AllocationSite as) {
 173     assert as != null;
 174
 175     ReachabilitySet rsOut = new ReachabilitySet();
 176
 177     Iterator itrS = this.iterator();
 178     while( itrS.hasNext() ) {
 179       TokenTupleSet tts = (TokenTupleSet) itrS.next();
 180       rsOut.possibleReachabilities.add(tts.ageTokens(as) );
 181     }
 182
 183     return rsOut.makeCanonical();
 184   }
 185
 186
 187   public ReachabilitySet unshadowTokens(AllocationSite as) {
 188     assert as != null;
 189
 190     ReachabilitySet rsOut = new ReachabilitySet();
 191
 192     Iterator itrS = this.iterator();
 193     while( itrS.hasNext() ) {
 194       TokenTupleSet tts = (TokenTupleSet) itrS.next();
 195       rsOut.possibleReachabilities.add(tts.unshadowTokens(as) );
 196     }
 197
 198     return rsOut.makeCanonical();
 199   }
 200
 201
 202   public ReachabilitySet toShadowTokens(AllocationSite as) {
 203     assert as != null;
 204
 205     ReachabilitySet rsOut = new ReachabilitySet();
 206
 207     Iterator itrS = this.iterator();
 208     while( itrS.hasNext() ) {
 209       TokenTupleSet tts = (TokenTupleSet) itrS.next();
 210       rsOut.possibleReachabilities.add(tts.toShadowTokens(as) );
 211     }
 212
 213     return rsOut.makeCanonical();
 214   }
 215
 216
 217   public ReachabilitySet pruneBy(ReachabilitySet rsIn) {
 218     assert rsIn != null;
 219
 220     ReachabilitySet rsOut = new ReachabilitySet();
 221
 222     Iterator itrB = this.iterator();
 223     while( itrB.hasNext() ) {
 224       TokenTupleSet ttsB = (TokenTupleSet) itrB.next();
 225
 226       boolean subsetExists = false;
 227
 228       Iterator itrA = rsIn.iterator();
 229       while( itrA.hasNext() && !subsetExists ) {
 230         TokenTupleSet ttsA = (TokenTupleSet) itrA.next();
 231
 232         if( ttsA.isSubset(ttsB) ) {
 233           subsetExists = true;
 234         }
 235       }
 236
 237       if( subsetExists ) {
 238         rsOut.possibleReachabilities.add(ttsB);
 239       }
 240     }
 241
 242     return rsOut.makeCanonical();
 243   }
 244
 245
 246   public ReachabilitySet exhaustiveArityCombinations() {
 247     ReachabilitySet rsOut = new ReachabilitySet();
 248
 249     int numDimensions = this.possibleReachabilities.size();
 250
 251     if( numDimensions > 6 ) {
 252       // for problems that are too big, punt and use less
 253       // precise arity for reachability information
 254       TokenTupleSet ttsImprecise = new TokenTupleSet().makeCanonical();
 255
 256       Iterator<TokenTupleSet> itrThis = this.iterator();
 257       while( itrThis.hasNext() ) {
 258         TokenTupleSet ttsUnit = itrThis.next();
 259         ttsImprecise = ttsImprecise.unionUpArity( ttsUnit.makeArityZeroOrMore() );
 260       }
 261
 262       rsOut = rsOut.union( ttsImprecise );
 263       return rsOut;
 264     }
 265
 266
 267     // add an extra digit to detect termination
 268     int[] digits = new int[numDimensions+1];
 269
 270     int minArity = 0;
 271     int maxArity = 2;
 272
 273     // start with the minimum possible coordinate
 274     for( int i = 0; i < numDimensions+1; ++i ) {
 275       digits[i] = minArity;
 276     }
 277
 278     // and stop when the highest-ordered axis rolls above the minimum
 279     while( digits[numDimensions] == minArity ) {
 280
 281       // spit out a "coordinate" made from these digits
 282       TokenTupleSet ttsCoordinate = new TokenTupleSet().makeCanonical();
 283       Iterator<TokenTupleSet> ttsItr = this.iterator();
 284       for( int i = 0; i < numDimensions; ++i ) {
 285         assert ttsItr.hasNext();
 286         TokenTupleSet ttsUnit = ttsItr.next();
 287         for( int j = 0; j < digits[i]; ++j ) {
 288           ttsCoordinate = ttsCoordinate.unionUpArity(ttsUnit);
 289         }
 290       }
 291       rsOut = rsOut.add(ttsCoordinate.makeCanonical() );
 292
 293       // increment
 294       for( int i = 0; i < numDimensions+1; ++i ) {
 295         digits[i]++;
 296
 297         if( digits[i] > maxArity ) {
 298           // this axis reached its max, so roll it back to min and increment next higher digit
 299           digits[i] = minArity;
 300
 301         } else {
 302           // this axis did not reach its max so we just enumerated a new unique coordinate, stop
 303           break;
 304         }
 305       }
 306     }
 307
 308     return rsOut.makeCanonical();
 309   }
 310
 311
 312   public boolean equals(Object o) {
 313     if( o == null ) {
 314       return false;
 315     }
 316
 317     if( !(o instanceof ReachabilitySet) ) {
 318       return false;
 319     }
 320
 321     ReachabilitySet rs = (ReachabilitySet) o;
 322     return possibleReachabilities.equals(rs.possibleReachabilities);
 323   }
 324
 325   public int hashCode() {
 326     return possibleReachabilities.hashCode();
 327   }
 328
 329
 330   public String toStringEscapeNewline() {
 331     String s = "[";
 332
 333     Iterator i = this.iterator();
 334     while( i.hasNext() ) {
 335       s += i.next();
 336       if( i.hasNext() ) {
 337         s += "\\n";
 338       }
 339     }
 340
 341     s += "]";
 342     return s;
 343   }
 344
 345   public String toString() {
 346     String s = "[";
 347
 348     Iterator i = this.iterator();
 349     while( i.hasNext() ) {
 350       s += i.next();
 351       if( i.hasNext() ) {
 352         s += "\n";
 353       }
 354     }
 355
 356     s += "]";
 357     return s;
 358   }
 359 }