Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java

   1 package Analysis.OwnershipAnalysis;
   2
   3 import Analysis.CallGraph.*;
   4 import IR.*;
   5 import IR.Flat.*;
   6 import java.util.*;
   7 import java.io.*;
   8
   9
  10 public class OwnershipAnalysis {
  11
  12     // from the compiler
  13     private State     state;
  14     private CallGraph callGraph;
  15     private int       allocationDepth;
  16
  17
  18     static private int uniqueIDcount = 0;
  19
  20
  21     // Use these data structures to track progress of
  22     // processing all methods in the program, and by methods
  23     // TaskDescriptor and MethodDescriptor are combined
  24     // together, with a common parent class Descriptor
  25     private HashSet  <Descriptor>                 descriptorsToVisit;
  26     private Hashtable<Descriptor, OwnershipGraph> mapDescriptorToCompleteOwnershipGraph;
  27     private Hashtable<FlatNew,    AllocationSite> mapFlatNewToAllocationSite;
  28
  29
  30     // Use these data structures to track progress of one pass of
  31     // processing the FlatNodes of a particular method
  32     private HashSet  <FlatNode>                 flatNodesToVisit;
  33     private Hashtable<FlatNode, OwnershipGraph> mapFlatNodeToOwnershipGraph;
  34     private HashSet  <FlatReturnNode>           returnNodesToCombineForCompleteOwnershipGraph;
  35
  36
  37     // this analysis generates an ownership graph for every task
  38     // in the program
  39     public OwnershipAnalysis( State     state,
  40                               CallGraph callGraph,
  41                               int       allocationDepth ) throws java.io.IOException {
  42         this.state           = state;
  43         this.callGraph       = callGraph;
  44         this.allocationDepth = allocationDepth;
  45
  46         mapDescriptorToCompleteOwnershipGraph =
  47             new Hashtable<Descriptor, OwnershipGraph>();
  48
  49         mapFlatNewToAllocationSite =
  50             new Hashtable<FlatNew, AllocationSite>();
  51
  52         // initialize methods to visit as the set of all tasks
  53         descriptorsToVisit = new HashSet<Descriptor>();
  54         Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
  55         while( taskItr.hasNext() ) {
  56             Descriptor d = (Descriptor) taskItr.next();
  57             descriptorsToVisit.add( d );
  58         }
  59
  60         // as mentioned above, analyze methods one-by-one, possibly revisiting
  61         // a method if the methods that it calls are updated
  62         analyzeMethods();
  63     }
  64
  65
  66     // manage the set of tasks and methods to be analyzed
  67     // and be sure to reschedule tasks/methods when the methods
  68     // they call are updated
  69     private void analyzeMethods() throws java.io.IOException {
  70
  71         while( !descriptorsToVisit.isEmpty() ) {
  72             Descriptor d = (Descriptor) descriptorsToVisit.iterator().next();
  73             descriptorsToVisit.remove( d );
  74
  75             // because the task or method descriptor just extracted
  76             // was in the "to visit" set it either hasn't been analyzed
  77             // yet, or some method that it depends on has been
  78             // updated.  Recompute a complete ownership graph for
  79             // this task/method and compare it to any previous result.
  80             // If there is a change detected, add any methods/tasks
  81             // that depend on this one to the "to visit" set.
  82
  83             System.out.println( "Analyzing " + d );
  84
  85             boolean    isTask;
  86             FlatMethod fm;
  87             if( d instanceof MethodDescriptor ) {
  88                 isTask = false;
  89                 fm     = state.getMethodFlat( (MethodDescriptor) d );
  90             } else {
  91                 assert d instanceof TaskDescriptor;
  92                 isTask = true;
  93                 fm     = state.getMethodFlat( (TaskDescriptor) d );
  94             }
  95
  96             OwnershipGraph og     = analyzeFlatMethod( isTask, fm );
  97             OwnershipGraph ogPrev = mapDescriptorToCompleteOwnershipGraph.get( d );
  98
  99             if( !og.equals( ogPrev ) ) {
 100                 mapDescriptorToCompleteOwnershipGraph.put( d, og );
 101
 102                 // only methods have dependents, tasks cannot
 103                 // be invoked by any user program calls
 104                 if( d instanceof MethodDescriptor ) {
 105                     MethodDescriptor md = (MethodDescriptor) d;
 106                     Set dependents = callGraph.getCallerSet( md );
 107                     System.out.println( "  Caller set is: " + dependents );
 108                     descriptorsToVisit.addAll( dependents );
 109                 }
 110             }
 111         }
 112
 113     }
 114
 115
 116     private OwnershipGraph
 117         analyzeFlatMethod( boolean    isTask,
 118                            FlatMethod flatm ) throws java.io.IOException {
 119
 120         // initialize flat nodes to visit as the flat method
 121         // because all other nodes in this flat method are
 122         // decendents of the flat method itself
 123         flatNodesToVisit = new HashSet<FlatNode>();
 124         flatNodesToVisit.add( flatm );
 125
 126         // initilize the mapping of flat nodes in this flat method to
 127         // ownership graph results to an empty mapping
 128         mapFlatNodeToOwnershipGraph = new Hashtable<FlatNode, OwnershipGraph>();
 129
 130         // initialize the set of return nodes that will be combined as
 131         // the final ownership graph result to return as an empty set
 132         returnNodesToCombineForCompleteOwnershipGraph = new HashSet<FlatReturnNode>();
 133
 134         while( !flatNodesToVisit.isEmpty() ) {
 135             FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 136             flatNodesToVisit.remove( fn );
 137
 138             // perform this node's contributions to the ownership
 139             // graph on a new copy, then compare it to the old graph
 140             // at this node to see if anything was updated.
 141             OwnershipGraph og = new OwnershipGraph( allocationDepth );
 142
 143             // start by merging all node's parents' graphs
 144             for( int i = 0; i < fn.numPrev(); ++i ) {
 145                 FlatNode       pn       = fn.getPrev( i );
 146                 OwnershipGraph ogParent = getGraphFromFlatNode( pn );
 147                 og.merge( ogParent );
 148             }
 149
 150             // apply the analysis of the flat node to the
 151             // ownership graph made from the merge of the
 152             // parent graphs
 153             analyzeFlatNode( isTask, fn, og );
 154
 155             // if the results of the new graph are different from
 156             // the current graph at this node, replace the graph
 157             // with the update and enqueue the children for
 158             // processing
 159             OwnershipGraph ogPrev = getGraphFromFlatNode( fn );
 160
 161             if( !og.equals( ogPrev ) ) {
 162                 setGraphForFlatNode( fn, og );
 163
 164                 for( int i = 0; i < fn.numNext(); i++ ) {
 165                     FlatNode nn = fn.getNext( i );
 166                     flatNodesToVisit.add( nn );
 167                 }
 168             }
 169         }
 170
 171         // end by merging all return nodes into a complete
 172         // ownership graph that represents all possible heap
 173         // states after the flat method returns
 174         OwnershipGraph completeGraph = new OwnershipGraph( allocationDepth );
 175         Iterator retItr = returnNodesToCombineForCompleteOwnershipGraph.iterator();
 176         while( retItr.hasNext() ) {
 177             FlatReturnNode frn = (FlatReturnNode) retItr.next();
 178             OwnershipGraph ogr = getGraphFromFlatNode( frn );
 179             completeGraph.merge( ogr );
 180         }
 181         return completeGraph;
 182     }
 183
 184
 185     private void
 186         analyzeFlatNode( boolean        isTask,
 187                          FlatNode       fn,
 188                          OwnershipGraph og ) throws java.io.IOException {
 189
 190         //System.out.println( "Analyszing a flat node" );
 191
 192         TempDescriptor  src;
 193         TempDescriptor  dst;
 194         FieldDescriptor fld;
 195         //String nodeDescription = "No description";
 196         //boolean writeGraph = false;
 197
 198         // use node type to decide what alterations to make
 199         // to the ownership graph
 200         switch( fn.kind() ) {
 201
 202         case FKind.FlatMethod:
 203             FlatMethod fm = (FlatMethod) fn;
 204
 205             if( isTask ) {
 206                 // add method parameters to the list of heap regions
 207                 // and remember names for analysis
 208                 for( int i = 0; i < fm.numParameters(); ++i ) {
 209                     TempDescriptor tdParam = fm.getParameter( i );
 210                     og.taskParameterAllocation( tdParam );
 211                     //og.addAnalysisRegion( tdParam );
 212                 }
 213             }
 214             break;
 215
 216             /*
 217         case FKind.FlatOpNode:
 218             FlatOpNode fon = (FlatOpNode) fn;
 219             if( fon.getOp().getOp() == Operation.ASSIGN ) {
 220                 src = fon.getLeft();
 221                 dst = fon.getDest();
 222                 og.assignTempToTemp( src, dst );
 223                 //nodeDescription = "Op";
 224                 //writeGraph = true;
 225                 og.writeGraph( fn );
 226             }
 227             break;
 228
 229         case FKind.FlatFieldNode:
 230             FlatFieldNode ffn = (FlatFieldNode) fn;
 231             src = ffn.getSrc();
 232             dst = ffn.getDst();
 233             fld = ffn.getField();
 234             if( !fld.getType().isPrimitive() ) {
 235                 og.assignTempToField( src, dst, fld );
 236                 //nodeDescription = "Field";
 237                 //writeGraph = true;
 238                 og.writeGraph( fn );
 239             }
 240             break;
 241
 242         case FKind.FlatSetFieldNode:
 243             FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 244             src = fsfn.getSrc();
 245             dst = fsfn.getDst();
 246             fld = fsfn.getField();
 247             og.assignFieldToTemp( src, dst, fld );
 248             //nodeDescription = "SetField";
 249             //writeGraph = true;
 250             og.writeGraph( fn );
 251             break;
 252
 253         case FKind.FlatNew:
 254             FlatNew fnn = (FlatNew) fn;
 255             dst = fnn.getDst();
 256             og.assignTempToNewAllocation( dst, fnn );
 257
 258             // !!!!!!!!!!!!!!
 259             // do this if the new object is a flagged type
 260             //og.addAnalysisRegion( tdParam );
 261
 262             //nodeDescription = "New";
 263             //writeGraph = true;
 264             og.writeGraph( fn );
 265
 266             break;
 267
 268             */
 269
 270         case FKind.FlatCall:
 271             FlatCall         fc = (FlatCall) fn;
 272             MethodDescriptor md = fc.getMethod();
 273             descriptorsToVisit.add( md );
 274             break;
 275
 276         case FKind.FlatReturnNode:
 277             //nodeDescription = "Return";
 278             //writeGraph = true;
 279             //og.writeCondensedAnalysis( makeCondensedAnalysisName( methodname, flatnodetolabel.get(fn) ) );
 280             //og.writeGraph( fn );
 281             break;
 282         }
 283
 284         /*
 285         if( writeGraph ) {
 286             og.writeGraph( makeNodeName( methodname,
 287                                          flatnodetolabel.get( fn ),
 288                                          nodeDescription ) );
 289         }
 290         */
 291     }
 292
 293     static public Integer generateUniqueHeapRegionNodeID() {
 294         ++uniqueIDcount;
 295         return new Integer( uniqueIDcount );
 296     }
 297
 298     private OwnershipGraph getGraphFromFlatNode( FlatNode fn ) {
 299         if( !mapFlatNodeToOwnershipGraph.containsKey( fn ) ) {
 300             mapFlatNodeToOwnershipGraph.put( fn, new OwnershipGraph( allocationDepth ) );
 301         }
 302
 303         return mapFlatNodeToOwnershipGraph.get( fn );
 304     }
 305
 306     private void setGraphForFlatNode( FlatNode fn, OwnershipGraph og ) {
 307         mapFlatNodeToOwnershipGraph.put( fn, og );
 308     }
 309
 310     private AllocationSite getAllocationSiteFromFlatNew( FlatNew fn ) {
 311         if( !mapFlatNewToAllocationSite.containsKey( fn ) ) {
 312             AllocationSite as = new AllocationSite( allocationDepth );
 313
 314             // the first k-1 nodes are single objects
 315             for( int i = 0; i < allocationDepth - 1; ++i ) {
 316                 //HeapRegionNode hrn = createNewHeapRegionNode( null, true, false, false );
 317                 Integer id = generateUniqueHeapRegionNodeID();
 318                 as.setIthOldest( i, id );
 319             }
 320
 321             // the kth node is a summary node
 322             //HeapRegionNode hrnNewSummary = createNewHeapRegionNode( null, false, false, true );
 323             Integer id2 = generateUniqueHeapRegionNodeID();
 324             as.setIthOldest( allocationDepth - 1, id2 );
 325
 326             mapFlatNewToAllocationSite.put( fn, as );
 327         }
 328
 329         return mapFlatNewToAllocationSite.get( fn );
 330     }
 331 }