Robust/src/Analysis/Disjoint/ExistPred.java

   1 package Analysis.Disjoint;
   2
   3 import IR.*;
   4 import IR.Flat.*;
   5 import java.util.*;
   6 import java.io.*;
   7
   8 ///////////////////////////////////////////
   9 //  IMPORTANT
  10 //  This class is an immutable Canonical, so
  11 //
  12 //  0) construct them with a factory pattern
  13 //  to ensure only canonical versions escape
  14 //
  15 //  1) any operation that modifies a Canonical
  16 //  is a static method in the Canonical class
  17 //
  18 //  2) operations that just read this object
  19 //  should be defined here
  20 //
  21 //  3) every Canonical subclass hashCode should
  22 //  throw an error if the hash ever changes
  23 //
  24 ///////////////////////////////////////////
  25
  26 // Existence predicates in the callee final-result
  27 // graph are relevant on the caller's callee-reachable
  28 // graph parts.  Any callee result elements with
  29 // predicates not satisfied in the caller are not
  30 // mapped in the call site transfer function
  31
  32 public class ExistPred extends Canonical {
  33
  34   // there are several types of predicates, note that
  35   // there are not subclasses of the ExistPred class
  36   // because they must be Canonical, no multiple inheritence
  37
  38   // types: true, node, edge
  39   public static final int TYPE_TRUE = 0xa501;
  40   public static final int TYPE_NODE = 0x02fd;
  41   public static final int TYPE_EDGE = 0x414b;
  42   protected int predType;
  43
  44   // true predicates always evaluate to true
  45
  46   // A node existence predicate is satisfied if the heap
  47   // region ID defining a node is part of the given graph
  48   // The reach state may be null--if not the predicate is
  49   // satisfied when the edge exists AND it has the state.
  50   protected Integer    n_hrnID;
  51   protected ReachState ne_state;
  52
  53   // An edge existence predicate is satisfied if the elements
  54   // defining an edge are part of the given graph.
  55   // The reach state may be null--if not the predicate is
  56   // satisfied when the edge exists AND it has the state.
  57   // the source of an edge is *either* a variable
  58   // node or a heap region node
  59   protected TempDescriptor e_tdSrc;
  60   protected Integer        e_hrnSrcID;
  61
  62   // the source of an edge might be out of the callee
  63   // context but in the caller graph, a normal caller
  64   // heap region or variable, OR it might be out of the
  65   // caller context ALSO: an ooc node in the caller
  66   protected boolean        e_srcOutCalleeContext;
  67   protected boolean        e_srcOutCallerContext;
  68
  69   // dst is always a heap region
  70   protected Integer        e_hrnDstID;
  71
  72   // a reference has a field name and type
  73   protected TypeDescriptor e_type;
  74   protected String         e_field;
  75
  76   // edge uses same ReachState ne_state as node type above
  77
  78
  79   // a static debug flag for higher abstraction code
  80   // to enable debug info at this level
  81   public static boolean debug = false;
  82
  83
  84   // to make the true predicate
  85   public static ExistPred factory() {
  86     ExistPred out = new ExistPred();
  87     out = (ExistPred) Canonical.makeCanonical( out );
  88     return out;
  89   }
  90
  91   protected ExistPred() {
  92     this.predType = TYPE_TRUE;
  93     ne_state   = null;
  94     n_hrnID    = null;
  95     e_tdSrc    = null;
  96     e_hrnSrcID = null;
  97     e_hrnDstID = null;
  98     e_type     = null;
  99     e_field    = null;
 100     e_srcOutCalleeContext = false;
 101     e_srcOutCallerContext = false;
 102   }
 103
 104   // node predicates
 105   public static ExistPred factory( Integer    hrnID,
 106                                    ReachState state ) {
 107
 108     ExistPred out = new ExistPred( hrnID, state );
 109
 110     out = (ExistPred) Canonical.makeCanonical( out );
 111     return out;
 112   }
 113
 114   protected ExistPred( Integer    hrnID,
 115                        ReachState state ) {
 116     assert hrnID != null;
 117     this.n_hrnID  = hrnID;
 118     this.ne_state = state;
 119     this.predType = TYPE_NODE;
 120     e_tdSrc    = null;
 121     e_hrnSrcID = null;
 122     e_hrnDstID = null;
 123     e_type     = null;
 124     e_field    = null;
 125     e_srcOutCalleeContext = false;
 126     e_srcOutCallerContext = false;
 127   }
 128
 129   // edge predicates
 130   public static ExistPred factory( TempDescriptor tdSrc,
 131                                    Integer        hrnSrcID,
 132                                    Integer        hrnDstID,
 133                                    TypeDescriptor type,
 134                                    String         field,
 135                                    ReachState     state,
 136                                    boolean        srcOutCalleeContext,
 137                                    boolean        srcOutCallerContext ) {
 138
 139     ExistPred out = new ExistPred( tdSrc,
 140                                    hrnSrcID,
 141                                    hrnDstID,
 142                                    type,
 143                                    field,
 144                                    state,
 145                                    srcOutCalleeContext,
 146                                    srcOutCallerContext );
 147
 148     out = (ExistPred) Canonical.makeCanonical( out );
 149     return out;
 150   }
 151
 152   protected ExistPred( TempDescriptor tdSrc,
 153                        Integer        hrnSrcID,
 154                        Integer        hrnDstID,
 155                        TypeDescriptor type,
 156                        String         field,
 157                        ReachState     state,
 158                        boolean        srcOutCalleeContext,
 159                        boolean        srcOutCallerContext ) {
 160
 161     assert (tdSrc == null) || (hrnSrcID == null);
 162     assert hrnDstID != null;
 163     assert type     != null;
 164
 165     // fields can be null when the edge is from
 166     // a variable node to a heap region!
 167     // assert field    != null;
 168
 169     this.e_srcOutCalleeContext = srcOutCalleeContext;
 170     this.e_srcOutCallerContext = srcOutCallerContext;
 171
 172     assert !(e_srcOutCalleeContext && e_srcOutCallerContext);
 173
 174     this.e_tdSrc    = tdSrc;
 175     this.e_hrnSrcID = hrnSrcID;
 176     this.e_hrnDstID = hrnDstID;
 177     this.e_type     = type;
 178     this.e_field    = field;
 179     this.ne_state   = state;
 180     this.predType   = TYPE_EDGE;
 181     n_hrnID = null;
 182   }
 183
 184
 185   // only consider the subest of the caller elements that
 186   // are reachable by callee when testing predicates--if THIS
 187   // predicate is satisfied, return the predicate set of the
 188   // element that satisfied it, or null for false
 189   public ExistPredSet isSatisfiedBy( ReachGraph   rg,
 190                                      Set<Integer> calleeReachableNodes
 191                                      ) {
 192     if( predType == TYPE_TRUE ) {
 193       return ExistPredSet.factory( ExistPred.factory() );
 194     }
 195
 196     if( predType == TYPE_NODE ) {
 197
 198       // first find node
 199       HeapRegionNode hrn = rg.id2hrn.get( n_hrnID );
 200       if( hrn == null ) {
 201         return null;
 202       }
 203
 204       if( !calleeReachableNodes.contains( n_hrnID ) ) {
 205         return null;
 206       }
 207
 208       // when the state is null it is not part of the
 209       // predicate, so we've already satisfied
 210       if( ne_state == null ) {
 211         return hrn.getPreds();
 212       }
 213
 214       // otherwise look for state too
 215       // TODO: contains OR containsSuperSet OR containsWithZeroes??
 216       if( hrn.getAlpha().containsIgnorePreds( ne_state )
 217           == null ) {
 218         return hrn.getPreds();
 219       }
 220
 221       return null;
 222     }
 223
 224     if( predType == TYPE_EDGE ) {
 225
 226       // first establish whether the source of the
 227       // reference edge exists
 228       VariableNode vnSrc = null;
 229       if( e_tdSrc != null ) {
 230         vnSrc = rg.td2vn.get( e_tdSrc );
 231       }
 232       HeapRegionNode hrnSrc = null;
 233       if( e_hrnSrcID != null ) {
 234         hrnSrc = rg.id2hrn.get( e_hrnSrcID );
 235       }
 236       assert (vnSrc == null) || (hrnSrc == null);
 237
 238       // the source is not present in graph
 239       if( vnSrc == null && hrnSrc == null ) {
 240         return null;
 241       }
 242
 243       RefSrcNode rsn;
 244       if( vnSrc != null ) {
 245         rsn = vnSrc;
 246         assert e_srcOutCalleeContext;
 247         assert !e_srcOutCallerContext;
 248
 249       } else {
 250
 251         assert !(e_srcOutCalleeContext && e_srcOutCallerContext);
 252
 253         if( e_srcOutCalleeContext ) {
 254           if( calleeReachableNodes.contains( e_hrnSrcID ) ) {
 255             return null;
 256           }
 257
 258         } else if( e_srcOutCallerContext ) {
 259           if( !hrnSrc.isOutOfContext() ) {
 260             return null;
 261           }
 262
 263         } else {
 264
 265           if( !calleeReachableNodes.contains( e_hrnSrcID ) ) {
 266             return null;
 267           }
 268           if( hrnSrc.isOutOfContext() ) {
 269             return null;
 270           }
 271
 272         }
 273
 274         rsn = hrnSrc;
 275       }
 276
 277       // is the destination present?
 278       HeapRegionNode hrnDst = rg.id2hrn.get( e_hrnDstID );
 279       if( hrnDst == null ) {
 280         return null;
 281       }
 282
 283       if( !calleeReachableNodes.contains( e_hrnDstID ) ) {
 284         return null;
 285       }
 286
 287       // is there an edge between them with the given
 288       // type and field?
 289       // TODO: type OR a subtype?
 290       RefEdge edge = rsn.getReferenceTo( hrnDst,
 291                                          e_type,
 292                                          e_field );
 293       if( edge == null ) {
 294         return null;
 295       }
 296
 297       // when state is null it is not part of the predicate
 298       // so we've satisfied the edge existence
 299       if( ne_state == null ) {
 300         return edge.getPreds();
 301       }
 302
 303       // otherwise look for state too
 304       // TODO: contains OR containsSuperSet OR containsWithZeroes??
 305       if( hrnDst.getAlpha().containsIgnorePreds( ne_state )
 306           == null ) {
 307         return edge.getPreds();
 308       }
 309
 310       return null;
 311     }
 312
 313     throw new Error( "Unknown predicate type" );
 314   }
 315
 316
 317
 318   public boolean equalsSpecific( Object o ) {
 319     if( o == null ) {
 320       return false;
 321     }
 322
 323     if( !(o instanceof ExistPred) ) {
 324       return false;
 325     }
 326
 327     ExistPred pred = (ExistPred) o;
 328
 329     if( this.predType != pred.predType ) {
 330       return false;
 331     }
 332
 333     if( ne_state == null ) {
 334       if( pred.ne_state != null ) {
 335         return false;
 336       }
 337     } else if( !ne_state.equals( pred.ne_state ) ) {
 338       return false;
 339     }
 340
 341     if( n_hrnID == null ) {
 342       if( pred.n_hrnID != null ) {
 343         return false;
 344       }
 345     } else if( !n_hrnID.equals( pred.n_hrnID ) ) {
 346       return false;
 347     }
 348
 349     if( e_tdSrc == null ) {
 350       if( pred.e_tdSrc != null ) {
 351         return false;
 352       }
 353     } else if( !e_tdSrc.equals( pred.e_tdSrc ) ) {
 354       return false;
 355     }
 356
 357     if( e_hrnSrcID == null ) {
 358       if( pred.e_hrnSrcID != null ) {
 359         return false;
 360       }
 361     } else {
 362       if( !e_hrnSrcID.equals( pred.e_hrnSrcID ) ) {
 363         return false;
 364       }
 365       if( e_srcOutCalleeContext != pred.e_srcOutCalleeContext ) {
 366         return false;
 367       }
 368       if( e_srcOutCallerContext != pred.e_srcOutCallerContext ) {
 369         return false;
 370       }
 371     }
 372
 373     if( e_hrnDstID == null ) {
 374       if( pred.e_hrnDstID != null ) {
 375         return false;
 376       }
 377     } else if( !e_hrnDstID.equals( pred.e_hrnDstID ) ) {
 378       return false;
 379     }
 380
 381     if( e_type == null ) {
 382       if( pred.e_type != null ) {
 383         return false;
 384       }
 385     } else if( !e_type.equals( pred.e_type ) ) {
 386       return false;
 387     }
 388
 389     if( e_field == null ) {
 390       if( pred.e_field != null ) {
 391         return false;
 392       }
 393     } else if( !e_field.equals( pred.e_field ) ) {
 394       return false;
 395     }
 396
 397     return true;
 398   }
 399
 400
 401   public int hashCodeSpecific() {
 402     if( predType == TYPE_TRUE ) {
 403       return 1;
 404     }
 405
 406     if( predType == TYPE_NODE ) {
 407       int hash = n_hrnID.intValue()*17;
 408
 409       if( ne_state != null ) {
 410         hash ^= ne_state.hashCode();
 411       }
 412
 413       return hash;
 414     }
 415
 416     if( predType == TYPE_EDGE ) {
 417       int hash = 0;
 418
 419       hash += e_type.hashCode()*17;
 420
 421       if( e_field != null ) {
 422         hash += e_field.hashCode()*7;
 423       }
 424
 425       if( e_tdSrc != null ) {
 426         hash ^= e_tdSrc.hashCode()*11;
 427       } else {
 428         hash ^= e_hrnSrcID.hashCode()*11;
 429         if( e_srcOutCalleeContext ) {
 430           hash ^= 0xf1aeb;
 431         }
 432         if( e_srcOutCallerContext ) {
 433           hash ^= 0x875d;
 434         }
 435       }
 436
 437       hash += e_hrnDstID.hashCode();
 438
 439       if( ne_state != null ) {
 440         hash ^= ne_state.hashCode();
 441       }
 442
 443       return hash;
 444     }
 445
 446     throw new Error( "Unknown predicate type" );
 447   }
 448
 449
 450   public String toString() {
 451     if( predType == TYPE_TRUE ) {
 452       return "t";
 453     }
 454
 455     if( predType == TYPE_NODE ) {
 456       String s = n_hrnID.toString();
 457       if( ne_state != null ) {
 458         s += "w"+ne_state;
 459       }
 460       return s;
 461     }
 462
 463     if( predType == TYPE_EDGE ) {
 464       String s = "(";
 465
 466       if( e_tdSrc != null ) {
 467         s += e_tdSrc.toString();
 468       } else {
 469         s += e_hrnSrcID.toString();
 470       }
 471
 472       if( e_srcOutCalleeContext ) {
 473         s += "(ooCLEEc)";
 474       }
 475
 476       if( e_srcOutCallerContext ) {
 477         s += "(ooCLERc)";
 478       }
 479
 480       s += "-->"+e_hrnDstID+")";
 481
 482       if( ne_state != null ) {
 483         s += "w"+ne_state;
 484       }
 485
 486       return s;
 487     }
 488
 489     throw new Error( "Unknown predicate type" );
 490   }
 491
 492 }