Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.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 OwnershipAnalysis {
  10
  11     private State state;
  12     private HashSet<FlatNode> visited;
  13     private HashSet<FlatNode> toVisit;
  14
  15     private int labelindex;
  16     private Hashtable<FlatNode, Integer> flatnodetolabel;
  17
  18     private Hashtable<FlatNode, OwnershipGraph> flatNodeToOwnershipGraph;
  19
  20
  21     // this analysis generates an ownership graph for every task
  22     // in the program
  23     public OwnershipAnalysis(State state) throws java.io.IOException {
  24         this.state=state;
  25         analyzeTasks();
  26     }
  27
  28     public void analyzeTasks() throws java.io.IOException {
  29         for( Iterator it_tasks=state.getTaskSymbolTable().getDescriptorsIterator();
  30              it_tasks.hasNext();
  31              ) {
  32
  33             // initialize the mapping of flat nodes to ownership graphs
  34             // every flat node in the IR graph has its own ownership graph
  35             flatNodeToOwnershipGraph = new Hashtable<FlatNode, OwnershipGraph>();
  36
  37             TaskDescriptor td = (TaskDescriptor)it_tasks.next();
  38             FlatMethod     fm = state.getMethodFlat( td );
  39
  40             // give every node in the flat IR graph a unique label
  41             // so a human being can inspect the graph and verify
  42             // correctness
  43             flatnodetolabel = new Hashtable<FlatNode, Integer>();
  44             visited         = new HashSet<FlatNode>();
  45             labelindex      = 0;
  46             labelFlatNodes( fm );
  47
  48             String taskname = td.getSymbol();
  49             analyzeFlatIRGraph( fm, taskname );
  50         }
  51     }
  52
  53     private void labelFlatNodes(FlatNode fn) {
  54         visited.add(fn);
  55         flatnodetolabel.put(fn,new Integer(labelindex++));
  56         for(int i=0;i<fn.numNext();i++) {
  57             FlatNode nn=fn.getNext(i);
  58             if(!visited.contains(nn)) {
  59                 labelFlatNodes(nn);
  60             }
  61         }
  62     }
  63
  64     private OwnershipGraph getGraphFromFlat( FlatNode fn ) {
  65         if( !flatNodeToOwnershipGraph.containsKey( fn ) ) {
  66             flatNodeToOwnershipGraph.put( fn, new OwnershipGraph() );
  67         }
  68
  69         return flatNodeToOwnershipGraph.get( fn );
  70     }
  71
  72     private void setGraphForFlat( FlatNode fn, OwnershipGraph og ) {
  73         flatNodeToOwnershipGraph.put( fn, og );
  74     }
  75
  76     private void analyzeFlatIRGraph( FlatMethod flatm, String taskname ) throws java.io.IOException {
  77         visited=new HashSet<FlatNode>();
  78         toVisit=new HashSet<FlatNode>();
  79         toVisit.add( flatm );
  80
  81         while( !toVisit.isEmpty() ) {
  82             FlatNode fn = (FlatNode)toVisit.iterator().next();
  83             toVisit.remove( fn );
  84             visited.add( fn );
  85
  86             // perform this node's contributions to the ownership
  87             // graph on a new copy, then compare it to the old graph
  88             // at this node to see if anything was updated.
  89             OwnershipGraph og = new OwnershipGraph();
  90
  91             // start by merging all incoming node's graphs
  92             for( int i = 0; i < fn.numPrev(); ++i ) {
  93                 FlatNode       pn       = fn.getPrev( i );
  94                 OwnershipGraph ogParent = getGraphFromFlat( pn );
  95                 og.merge( ogParent );
  96             }
  97
  98             TempDescriptor  src;
  99             TempDescriptor  dst;
 100             FieldDescriptor fld;
 101             String nodeDescription = "No description";
 102             boolean writeGraph = false;
 103
 104             // use node type to decide what alterations to make
 105             // to the ownership graph
 106             switch( fn.kind() ) {
 107
 108             case FKind.FlatMethod:
 109                 FlatMethod fm = (FlatMethod) fn;
 110
 111                 // add method parameters to the list of heap regions
 112                 // and remember names for analysis
 113                 for( int i = 0; i < fm.numParameters(); ++i ) {
 114                     TempDescriptor tdParam = fm.getParameter( i );
 115                     og.newHeapRegion( tdParam );
 116                     og.addAnalysisRegion( tdParam );
 117                 }
 118
 119                 nodeDescription = "Method";
 120                 writeGraph = true;
 121                 break;
 122
 123             case FKind.FlatOpNode:
 124                 FlatOpNode fon = (FlatOpNode) fn;
 125                 if(fon.getOp().getOp()==Operation.ASSIGN) {
 126                     src = fon.getLeft();
 127                     dst = fon.getDest();
 128                     og.assignTempToTemp( src, dst );
 129                     nodeDescription = "Op";
 130                     writeGraph = true;
 131                 }
 132                 break;
 133
 134             case FKind.FlatFieldNode:
 135                 FlatFieldNode ffn = (FlatFieldNode) fn;
 136                 src = ffn.getSrc();
 137                 dst = ffn.getDst();
 138                 fld = ffn.getField();
 139                 og.assignTempToField( src, dst, fld );
 140                 nodeDescription = "Field";
 141                 writeGraph = true;
 142                 break;
 143
 144             case FKind.FlatSetFieldNode:
 145                 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 146                 src = fsfn.getSrc();
 147                 dst = fsfn.getDst();
 148                 fld = fsfn.getField();
 149                 og.assignFieldToTemp( src, dst, fld );
 150                 nodeDescription = "SetField";
 151                 writeGraph = true;
 152
 153                 break;
 154
 155             case FKind.FlatReturnNode:
 156                 nodeDescription = "Return";
 157                 writeGraph = true;
 158                 og.writeCondensedAnalysis( makeCondensedAnalysisName( taskname, flatnodetolabel.get(fn) ) );
 159                 break;
 160             }
 161
 162             if( writeGraph ) {
 163                 og.writeGraph( makeNodeName( taskname,
 164                                              flatnodetolabel.get( fn ),
 165                                              nodeDescription ) );
 166             }
 167
 168             // if the results of the new graph are different from
 169             // the current graph at this node, replace the graph
 170             // with the update and enqueue the children for
 171             // processing
 172             OwnershipGraph ogOld = getGraphFromFlat( fn );
 173
 174             if( !og.equivalent( ogOld ) ) {
 175                 setGraphForFlat( fn, og );
 176
 177                 for( int i = 0; i < fn.numNext(); i++ ) {
 178                     FlatNode nn = fn.getNext( i );
 179                     visited.remove( nn );
 180                     toVisit.add( nn );
 181                 }
 182             }
 183         }
 184     }
 185
 186     private String makeNodeName( String taskname, Integer id, String type ) {
 187         String s = String.format( "%05d", id );
 188         return "task"+taskname+"_FN"+s+"_"+type;
 189     }
 190
 191     private String makeCondensedAnalysisName( String taskname, Integer id ) {
 192         return "task"+taskname+"_Ownership_from"+id;
 193     }
 194 }