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
  26         analyzeTasks();
  27     }
  28
  29     public void analyzeTasks() throws java.io.IOException {
  30         for( Iterator it_tasks=state.getTaskSymbolTable().getDescriptorsIterator();
  31              it_tasks.hasNext();
  32              ) {
  33
  34             // initialize the mapping of flat nodes to ownership graphs
  35             // every flat node in the IR graph has its own ownership graph
  36             flatNodeToOwnershipGraph = new Hashtable<FlatNode, OwnershipGraph>();
  37
  38             TaskDescriptor td = (TaskDescriptor)it_tasks.next();
  39             FlatMethod fm     = state.getMethodFlat( td );
  40
  41             // give every node in the flat IR graph a unique label
  42             // so a human being can inspect the graph and verify
  43             // correctness
  44             flatnodetolabel = new Hashtable<FlatNode, Integer>();
  45             visited         = new HashSet<FlatNode>();
  46             labelindex      = 0;
  47             labelFlatNodes( fm );
  48
  49             // add method parameters to the list of heap regions
  50             // and remember names for analysis
  51             OwnershipGraph og = getGraphFromFlat( fm );
  52             for( int i = 0; i < fm.numParameters(); ++i ) {
  53                 TempDescriptor tdParam = fm.getParameter( i );
  54                 og.newHeapRegion( tdParam );
  55                 og.addAnalysisRegion( tdParam );
  56             }
  57
  58             String taskname   = td.getSymbol();
  59             analyzeFlatIRGraph( fm, taskname );
  60         }
  61     }
  62
  63     private void labelFlatNodes(FlatNode fn) {
  64         visited.add(fn);
  65         flatnodetolabel.put(fn,new Integer(labelindex++));
  66         for(int i=0;i<fn.numNext();i++) {
  67             FlatNode nn=fn.getNext(i);
  68             if(!visited.contains(nn)) {
  69                 labelFlatNodes(nn);
  70             }
  71         }
  72     }
  73
  74     private OwnershipGraph getGraphFromFlat( FlatNode fn ) {
  75         if( !flatNodeToOwnershipGraph.containsKey(fn) ) {
  76             flatNodeToOwnershipGraph.put( fn, new OwnershipGraph() );
  77         }
  78
  79         return flatNodeToOwnershipGraph.get(fn);
  80     }
  81
  82     private void analyzeFlatIRGraph( FlatMethod fm, String taskname ) throws java.io.IOException {
  83         visited=new HashSet<FlatNode>();
  84         toVisit=new HashSet<FlatNode>();
  85         toVisit.add(fm);
  86
  87         while( !toVisit.isEmpty() ) {
  88             FlatNode fn=(FlatNode)toVisit.iterator().next();
  89             toVisit.remove(fn);
  90             visited.add(fn);
  91
  92             // get this node's ownership graph, or create a new one
  93             OwnershipGraph og = getGraphFromFlat( fn );
  94
  95             TempDescriptor  src;
  96             TempDescriptor  dst;
  97             FieldDescriptor fld;
  98
  99             switch(fn.kind()) {
 100
 101             case FKind.FlatMethod:
 102                 og.writeGraph( makeNodeName( taskname, flatnodetolabel.get(fn), "Method" ) );
 103                 break;
 104
 105             case FKind.FlatOpNode:
 106                 FlatOpNode fon = (FlatOpNode) fn;
 107                 if(fon.getOp().getOp()==Operation.ASSIGN) {
 108                     src = fon.getLeft();
 109                     dst = fon.getDest();
 110                     og.assignTempToTemp( src, dst );
 111                     og.writeGraph( makeNodeName( taskname, flatnodetolabel.get(fn), "Op" ) );
 112                 }
 113                 break;
 114
 115             case FKind.FlatFieldNode:
 116                 FlatFieldNode ffn = (FlatFieldNode) fn;
 117                 src = ffn.getSrc();
 118                 dst = ffn.getDst();
 119                 fld = ffn.getField();
 120                 og.assignTempToField( src, dst, fld );
 121                 og.writeGraph( makeNodeName( taskname, flatnodetolabel.get(fn), "Field" ) );
 122                 break;
 123
 124             case FKind.FlatSetFieldNode:
 125                 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 126                 src = fsfn.getSrc();
 127                 dst = fsfn.getDst();
 128                 fld = fsfn.getField();
 129                 og.assignFieldToTemp( src, dst, fld );
 130                 og.writeGraph( makeNodeName( taskname, flatnodetolabel.get(fn), "SetField" ) );
 131                 break;
 132
 133             case FKind.FlatReturnNode:
 134                 og.writeGraph( makeNodeName( taskname, flatnodetolabel.get(fn), "Return" ) );
 135                 og.writeCondensedAnalysis( makeCondensedAnalysisName( taskname, flatnodetolabel.get(fn) ) );
 136                 break;
 137             }
 138
 139             // send this flat node's ownership graph along the out edges
 140             // to be taken by the next flat edges in the flow, or if they
 141             // already have a graph, to be merged
 142             for(int i=0;i<fn.numNext();i++) {
 143                 FlatNode nn=fn.getNext(i);
 144
 145                 if( !visited.contains( nn ) ) {
 146                     // FIX THE COPY!!!!!!!!!!!!!!!
 147                     //flatNodeToOwnershipGraph.put( nn, og.copy() );
 148                     flatNodeToOwnershipGraph.put( nn, og );
 149                     toVisit.add( nn );
 150                 }
 151             }
 152         }
 153     }
 154
 155     private String makeNodeName( String taskname, Integer id, String type ) {
 156         String s = String.format( "%05d", id );
 157         return "task"+taskname+"_FN"+s+"_"+type;
 158     }
 159
 160     private String makeCondensedAnalysisName( String taskname, Integer id ) {
 161         return "task"+taskname+"_Ownership_from"+id;
 162     }
 163 }