Robust/src/IR/Flat/BCXPointsToCheckVRuntime.java

   1 package IR.Flat;
   2
   3 import Analysis.Disjoint.HeapAnalysis;
   4 import Analysis.Disjoint.Alloc;
   5 import IR.*;
   6
   7 import java.io.*;
   8 import java.util.*;
   9
  10
  11 // This BuildCode Extension (BCX) takes a heap analysis
  12 // with points-to information and generates checks at runtime
  13 // verifies the allocation site of objects pointed-to.  It
  14 // doesn't fully verify an analysis but it can reveal bugs!
  15
  16
  17 public class BCXPointsToCheckVRuntime implements BuildCodeExtension {
  18
  19   protected BuildCode    buildCode;
  20   protected HeapAnalysis heapAnalysis;
  21
  22
  23   public BCXPointsToCheckVRuntime( BuildCode    buildCode,
  24                                    HeapAnalysis heapAnalysis ) {
  25     this.buildCode    = buildCode;
  26     this.heapAnalysis = heapAnalysis;
  27   }
  28
  29
  30   public void additionalIncludesMethodsHeader(PrintWriter outmethodheader) {
  31     outmethodheader.println("#include \"assert.h\"");
  32   }
  33
  34
  35   public void additionalCodeAtTopFlatMethodBody(PrintWriter output, FlatMethod fm) {
  36
  37     for( int i = 0; i < fm.numParameters(); ++i ) {
  38       TempDescriptor td   = fm.getParameter( i );
  39       TypeDescriptor type = td.getType();
  40       if( type.isPtr() ) {
  41         genAssertRuntimePtrVsHeapResults( output,
  42                                           fm,
  43                                           td,
  44                                           heapAnalysis.canPointToAfter( td, fm )
  45                                           );
  46       }
  47     }
  48   }
  49
  50
  51   public void additionalCodePreNode(FlatMethod fm, FlatNode fn, PrintWriter output) {
  52
  53     TempDescriptor  lhs;
  54     TempDescriptor  rhs;
  55     FieldDescriptor fld;
  56     TempDescriptor  idx;
  57     TypeDescriptor  type;
  58
  59
  60     switch( fn.kind() ) {
  61
  62       case FKind.FlatOpNode: {
  63         FlatOpNode fon = (FlatOpNode) fn;
  64         if( fon.getOp().getOp() == Operation.ASSIGN ) {
  65           lhs = fon.getDest();
  66           rhs = fon.getLeft();
  67
  68           type = lhs.getType();
  69           if( type.isPtr() ) {
  70             genAssertRuntimePtrVsHeapResults( output,
  71                                               fm,
  72                                               lhs,
  73                                               heapAnalysis.canPointToAt( lhs, fn )
  74                                               );
  75
  76             genAssertRuntimePtrVsHeapResults( output,
  77                                               fm,
  78                                               rhs,
  79                                               heapAnalysis.canPointToAt( rhs, fn )
  80                                               );
  81           }
  82         }
  83       } break;
  84
  85
  86       case FKind.FlatCastNode: {
  87         FlatCastNode fcn = (FlatCastNode) fn;
  88         lhs = fcn.getDst();
  89         rhs = fcn.getSrc();
  90
  91         type = fcn.getType();
  92         if( type.isPtr() ) {
  93           genAssertRuntimePtrVsHeapResults( output,
  94                                             fm,
  95                                             lhs,
  96                                             heapAnalysis.canPointToAt( lhs, fn )
  97                                             );
  98
  99           genAssertRuntimePtrVsHeapResults( output,
 100                                             fm,
 101                                             rhs,
 102                                             heapAnalysis.canPointToAt( rhs, fn )
 103                                             );
 104         }
 105       } break;
 106
 107
 108       case FKind.FlatFieldNode: {
 109         FlatFieldNode ffn = (FlatFieldNode) fn;
 110         lhs = ffn.getDst();
 111         rhs = ffn.getSrc();
 112         fld = ffn.getField();
 113
 114         type = lhs.getType();
 115         if( type.isPtr() ) {
 116           genAssertRuntimePtrVsHeapResults( output,
 117                                             fm,
 118                                             lhs,
 119                                             heapAnalysis.canPointToAt( lhs, fn )
 120                                             );
 121
 122           genAssertRuntimePtrVsHeapResults( output,
 123                                             fm,
 124                                             rhs,
 125                                             fld,
 126                                             null,
 127                                             heapAnalysis.canPointToAt( rhs, fld, fn )
 128                                             );
 129         }
 130       } break;
 131
 132
 133       case FKind.FlatElementNode: {
 134         FlatElementNode fen = (FlatElementNode) fn;
 135         lhs = fen.getDst();
 136         rhs = fen.getSrc();
 137         idx = fen.getIndex();
 138
 139         type = lhs.getType();
 140         if( type.isPtr() ) {
 141           genAssertRuntimePtrVsHeapResults( output,
 142                                             fm,
 143                                             lhs,
 144                                             heapAnalysis.canPointToAt( lhs, fn )
 145                                             );
 146
 147           genAssertRuntimePtrVsHeapResults( output,
 148                                             fm,
 149                                             rhs,
 150                                             null,
 151                                             idx,
 152                                             heapAnalysis.canPointToAtElement( rhs, fn )
 153                                             );
 154         }
 155       } break;
 156
 157     }
 158
 159   }
 160
 161
 162   public void additionalCodePostNode(FlatMethod fm,
 163                                      FlatNode fn,
 164                                      PrintWriter output) {
 165     switch( fn.kind() ) {
 166       case FKind.FlatCall: {
 167         FlatCall       fc = (FlatCall) fn;
 168         TempDescriptor td = fc.getReturnTemp();
 169
 170         if( td != null ) {
 171           TypeDescriptor type = td.getType();
 172           if( type.isPtr() ) {
 173             genAssertRuntimePtrVsHeapResults( output,
 174                                               fm,
 175                                               td,
 176                                               heapAnalysis.canPointToAfter( td, fn )
 177                                               );
 178           }
 179         }
 180       } break;
 181     }
 182   }
 183
 184
 185
 186   protected void
 187     genAssertRuntimePtrVsHeapResults( PrintWriter    output,
 188                                       FlatMethod     context,
 189                                       TempDescriptor x,
 190                                       Set<Alloc>     targetsByAnalysis ) {
 191
 192     assert targetsByAnalysis != null;
 193
 194
 195     output.println( "" );
 196     output.println( "// asserts vs. heap results (DEBUG)" );
 197
 198
 199     if( targetsByAnalysis == HeapAnalysis.DONTCARE_PTR ) {
 200       output.println( "// ANALYSIS DIDN'T CARE WHAT "+x+" POINTS-TO" );
 201       return;
 202     }
 203
 204
 205     if( targetsByAnalysis.isEmpty() ) {
 206       output.println( "assert( "+
 207                       buildCode.generateTemp( context, x )+
 208                       " == NULL );\n" );
 209
 210     } else {
 211       output.print( "assert( "+
 212                     buildCode.generateTemp( context, x )+
 213                     " == NULL || " );
 214
 215       Iterator<Alloc> aItr = targetsByAnalysis.iterator();
 216       while( aItr.hasNext() ) {
 217         Alloc a = aItr.next();
 218         output.print( buildCode.generateTemp( context, x )+
 219                       "->allocsite == "+
 220                       a.getUniqueAllocSiteID()
 221                       );
 222         if( aItr.hasNext() ) {
 223           output.print( " || " );
 224         }
 225       }
 226
 227       output.println( " );\n" );
 228     }
 229   }
 230
 231
 232
 233   protected void
 234     genAssertRuntimePtrVsHeapResults( PrintWriter                    output,
 235                                       FlatMethod                     context,
 236                                       TempDescriptor                 x,
 237                                       FieldDescriptor                f, // this null OR
 238                                       TempDescriptor                 i, // this null
 239                                       Hashtable< Alloc, Set<Alloc> > targetsByAnalysis ) {
 240     assert targetsByAnalysis != null;
 241
 242     assert f == null || i == null;
 243
 244     output.println( "// asserts vs. heap results (DEBUG)" );
 245
 246
 247     if( targetsByAnalysis == HeapAnalysis.DONTCARE_DREF ) {
 248       output.println( "// ANALYSIS DIDN'T CARE WHAT "+x+" POINTS-TO" );
 249       return;
 250     }
 251
 252
 253     if( targetsByAnalysis.isEmpty() ) {
 254       output.println( "assert( "+
 255                       buildCode.generateTemp( context, x )+
 256                       " == NULL );\n" );
 257     } else {
 258       output.println( "{" );
 259
 260       // if the ptr is null, that's ok, if not check allocsite
 261       output.println( "if( "+
 262                       buildCode.generateTemp( context, x )+
 263                       " != NULL ) {" );
 264
 265       // precompute the allocsite, if any, of the object we will
 266       // get from hopping through the first ptr
 267       output.println( "int allocsiteOneHop = -1;" );
 268       output.println( buildCode.strObjType+"* objOneHop;" );
 269
 270       if( f != null ) {
 271         output.println( "objOneHop = ("+buildCode.strObjType+"*) "+
 272                         buildCode.generateTemp( context, x )+
 273                         "->"+f.getSafeSymbol()+";");
 274       } else {
 275         output.println( "objOneHop = ("+buildCode.strObjType+"*) "+
 276                         "((struct "+x.getType().dereference().getSafeSymbol()+"**)"+
 277                         "(((void*) &("+buildCode.generateTemp( context, x )+"->___length___))+sizeof(int)))"+
 278                         "["+buildCode.generateTemp( context, i )+"];" );
 279       }
 280
 281       output.println( "if( objOneHop != NULL ) { allocsiteOneHop = objOneHop->allocsite; }" );
 282
 283       output.println( "switch( "+
 284                       buildCode.generateTemp( context, x )+
 285                       "->allocsite ) {" );
 286
 287       Iterator<Alloc> kItr = targetsByAnalysis.keySet().iterator();
 288       while( kItr.hasNext() ) {
 289         Alloc k = kItr.next();
 290
 291         output.print( "case "+
 292                       k.getUniqueAllocSiteID()+
 293                       ":" );
 294
 295         Set<Alloc> hopTargets = targetsByAnalysis.get( k );
 296         if( hopTargets == HeapAnalysis.DONTCARE_PTR ) {
 297           output.print( "/* ANALYSIS DOESN'T CARE */" );
 298
 299         } else {
 300           output.print( "assert( allocsiteOneHop == -1" );
 301
 302           if( !hopTargets.isEmpty() ) {
 303             output.print( " || " );
 304           }
 305
 306           Iterator<Alloc> aItr = hopTargets.iterator();
 307           while( aItr.hasNext() ) {
 308             Alloc a = aItr.next();
 309
 310             output.print( "allocsiteOneHop == "+
 311                           a.getUniqueAllocSiteID() );
 312
 313             if( aItr.hasNext() ) {
 314               output.print( " || " );
 315             }
 316           }
 317
 318           output.print( " );" );
 319         }
 320
 321         output.println( " break;" );
 322       }
 323
 324       output.println( "    default: assert( 0 ); break;" );
 325       output.println( "}" );
 326       output.println( "}" );
 327       output.println( "}\n" );
 328     }
 329   }
 330
 331
 332
 333
 334   public void printExtraArrayFields(PrintWriter outclassdefs) {}
 335   public void outputTransCode(PrintWriter output) {}
 336   public void buildCodeSetup() {}
 337   public void generateSizeArrayExtensions(PrintWriter outclassdefs) {}
 338   public void preCodeGenInitialization() {}
 339   public void postCodeGenCleanUp() {}
 340   public void additionalClassObjectFields(PrintWriter outclassdefs) {}
 341   public void additionalCodeGen(PrintWriter outmethodheader,
 342                                    PrintWriter outstructs,
 343                                    PrintWriter outmethod) {}
 344   public void additionalCodeAtTopOfMain(PrintWriter outmethod) {}
 345   public void additionalCodeForCommandLineArgs(PrintWriter outmethod, String argsVar) {}
 346   public void additionalCodeAtBottomOfMain(PrintWriter outmethod) {}
 347   public void additionalIncludesMethodsImplementation(PrintWriter outmethod) {}
 348   public void additionalIncludesStructsHeader(PrintWriter outstructs) {}
 349   public void additionalCodeAtTopMethodsImplementation(PrintWriter outmethod) {}
 350   public void additionalCodeNewObject(PrintWriter outmethod, String dstVar, FlatNew flatNew) {}
 351 }