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     // Use these data structures to track progress of
  18     // processing all methods in the program, and by methods
  19     // TaskDescriptor and MethodDescriptor are combined
  20     // together, with a common parent class Descriptor
  21     private HashSet  <Descriptor>                 descriptorsToVisit;
  22     private Hashtable<Descriptor, OwnershipGraph> mapDescriptorToCompleteOwnershipGraph;
  23
  24     // Use these data structures to track progress of one pass of
  25     // processing the FlatNodes of a particular method
  26     private HashSet  <FlatNode>                 flatNodesToVisit;
  27     private Hashtable<FlatNode, OwnershipGraph> mapFlatNodeToOwnershipGraph;
  28     private HashSet  <FlatReturnNode>           returnNodesToCombineForCompleteOwnershipGraph;
  29
  30
  31     // for generating unique ownership node ID's throughout the
  32     // ownership analysis
  33     static private int uniqueIDcount = 0;
  34
  35     static public Integer generateUniqueID() {
  36         ++uniqueIDcount;
  37         return new Integer( uniqueIDcount );
  38     }
  39
  40
  41     // this analysis generates an ownership graph for every task
  42     // in the program
  43     public OwnershipAnalysis( State     state,
  44                               CallGraph callGraph,
  45                               int       allocationDepth ) throws java.io.IOException {
  46         this.state           = state;
  47         this.callGraph       = callGraph;
  48         this.allocationDepth = allocationDepth;
  49
  50         mapDescriptorToCompleteOwnershipGraph =
  51             new Hashtable<Descriptor, OwnershipGraph>();
  52
  53         // initialize methods to visit as the set of
  54         // all tasks
  55         descriptorsToVisit = new HashSet<Descriptor>();
  56         Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
  57         while( taskItr.hasNext() ) {
  58             descriptorsToVisit.add( (Descriptor) taskItr.next() );
  59         }
  60
  61         // as mentioned above, analyze methods one-by-one, possibly revisiting
  62         // a method if the methods that it calls are updated
  63         analyzeMethods();
  64     }
  65
  66     private void analyzeMethods() throws java.io.IOException {
  67
  68
  69         /*
  70         for( Iterator it_tasks=state.getTaskSymbolTable().getDescriptorsIterator();
  71              it_tasks.hasNext();
  72              ) {
  73
  74             // initialize the mapping of flat nodes to ownership graphs
  75             // every flat node in the IR graph has its own ownership graph
  76             flatNodeToOwnershipGraph = new Hashtable<FlatNode, OwnershipGraph>();
  77
  78             TaskDescriptor td = (TaskDescriptor) it_tasks.next();
  79             FlatMethod     fm = state.getMethodFlat( td );
  80
  81             // give every node in the flat IR graph a unique label
  82             // so a human being can inspect the graph and verify
  83             // correctness
  84             flatnodetolabel = new Hashtable<FlatNode, Integer>();
  85             visited         = new HashSet<FlatNode>();
  86             labelindex      = 0;
  87             labelFlatNodes( fm );
  88
  89             String methodname = td.getSymbol();
  90             analyzeFlatIRGraph( fm, methodname );
  91         }
  92         */
  93     }
  94
  95     /*
  96     private OwnershipGraph getGraphFromFlatNode( FlatNode fn ) {
  97         if( !flatNodeToOwnershipGraph.containsKey( fn ) ) {
  98             flatNodeToOwnershipGraph.put( fn, new OwnershipGraph( newDepthK ) );
  99         }
 100
 101         return flatNodeToOwnershipGraph.get( fn );
 102     }
 103
 104     private void setGraphForFlatNode( FlatNode fn, OwnershipGraph og ) {
 105         flatNodeToOwnershipGraph.put( fn, og );
 106     }
 107
 108     private void analyzeFlatMethod( FlatMethod flatm, String methodname ) throws java.io.IOException {
 109         toVisit=new HashSet<FlatNode>();
 110         toVisit.add( flatm );
 111
 112         while( !toVisit.isEmpty() ) {
 113             FlatNode fn = (FlatNode) toVisit.iterator().next();
 114             toVisit.remove( fn );
 115
 116             // perform this node's contributions to the ownership
 117             // graph on a new copy, then compare it to the old graph
 118             // at this node to see if anything was updated.
 119             OwnershipGraph og = new OwnershipGraph( newDepthK );
 120
 121             // start by merging all node's parents' graphs
 122             for( int i = 0; i < fn.numPrev(); ++i ) {
 123                 FlatNode       pn       = fn.getPrev( i );
 124                 OwnershipGraph ogParent = getGraphFromFlatNode( pn );
 125                 og.merge( ogParent );
 126             }
 127
 128             analyzeFlatNode( fn );
 129
 130             // if the results of the new graph are different from
 131             // the current graph at this node, replace the graph
 132             // with the update and enqueue the children for
 133             // processing
 134             OwnershipGraph ogOld = getGraphFromFlatNode( fn );
 135
 136             if( !og.equals( ogOld ) ) {
 137                 setGraphForFlatNode( fn, og );
 138
 139                 for( int i = 0; i < fn.numNext(); i++ ) {
 140                     FlatNode nn = fn.getNext( i );
 141                     visited.remove( nn );
 142                     toVisit.add( nn );
 143                 }
 144             }
 145         }
 146     }
 147
 148
 149     private void analyzeFlatNode( FlatNode fn, String methodname ) {
 150             TempDescriptor  src;
 151             TempDescriptor  dst;
 152             FieldDescriptor fld;
 153             String nodeDescription = "No description";
 154             boolean writeGraph = false;
 155
 156             // use node type to decide what alterations to make
 157             // to the ownership graph
 158             switch( fn.kind() ) {
 159
 160             case FKind.FlatMethod:
 161                 FlatMethod fm = (FlatMethod) fn;
 162
 163                 // add method parameters to the list of heap regions
 164                 // and remember names for analysis
 165                 for( int i = 0; i < fm.numParameters(); ++i ) {
 166                     TempDescriptor tdParam = fm.getParameter( i );
 167                     og.parameterAllocation( tdParam );
 168                     og.addAnalysisRegion( tdParam );
 169                 }
 170
 171                 nodeDescription = "Method";
 172                 writeGraph = true;
 173                 break;
 174
 175             case FKind.FlatOpNode:
 176                 FlatOpNode fon = (FlatOpNode) fn;
 177                 if( fon.getOp().getOp() == Operation.ASSIGN ) {
 178                     src = fon.getLeft();
 179                     dst = fon.getDest();
 180                     og.assignTempToTemp( src, dst );
 181                     nodeDescription = "Op";
 182                     writeGraph = true;
 183                 }
 184                 break;
 185
 186             case FKind.FlatFieldNode:
 187                 FlatFieldNode ffn = (FlatFieldNode) fn;
 188                 src = ffn.getSrc();
 189                 dst = ffn.getDst();
 190                 fld = ffn.getField();
 191                 if( !fld.getType().isPrimitive() ) {
 192                     og.assignTempToField( src, dst, fld );
 193                     nodeDescription = "Field";
 194                     writeGraph = true;
 195                 }
 196                 break;
 197
 198             case FKind.FlatSetFieldNode:
 199                 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 200                 src = fsfn.getSrc();
 201                 dst = fsfn.getDst();
 202                 fld = fsfn.getField();
 203                 og.assignFieldToTemp( src, dst, fld );
 204                 nodeDescription = "SetField";
 205                 writeGraph = true;
 206                 break;
 207
 208             case FKind.FlatNew:
 209                 FlatNew fnn = (FlatNew) fn;
 210                 dst = fnn.getDst();
 211                 og.assignTempToNewAllocation( dst, fnn );
 212
 213                 // !!!!!!!!!!!!!!
 214                 // do this if the new object is a flagged type
 215                 //og.addAnalysisRegion( tdParam );
 216
 217                 nodeDescription = "New";
 218                 writeGraph = true;
 219                 break;
 220
 221             case FKind.FlatReturnNode:
 222                 nodeDescription = "Return";
 223                 writeGraph = true;
 224                 og.writeCondensedAnalysis( makeCondensedAnalysisName( methodname, flatnodetolabel.get(fn) ) );
 225                 break;
 226             }
 227
 228             if( writeGraph ) {
 229                 og.writeGraph( makeNodeName( methodname,
 230                                              flatnodetolabel.get( fn ),
 231                                              nodeDescription ) );
 232             }
 233     }
 234
 235
 236     private String makeNodeName( String methodname, Integer id, String type ) {
 237         String s = String.format( "%05d", id );
 238         return "method_"+methodname+"_FN"+s+"_"+type;
 239     }
 240
 241     private String makeCondensedAnalysisName( String methodname, Integer id ) {
 242         return "method_"+methodname+"_Ownership_from"+id;
 243     }
 244     */
 245 }