Robust/src/Analysis/Liveness.java

   1 package Analysis;
   2
   3 import IR.Flat.*;
   4 import java.util.Arrays;
   5 import java.util.HashSet;
   6 import java.util.Set;
   7 import java.util.Iterator;
   8 import java.util.List;
   9 import java.util.Hashtable;
  10 import Analysis.Locality.*;
  11
  12 public class Liveness {
  13   /* This methods takes in a FlatMethod and returns a map from a
  14    * FlatNode to the set of temps that are live into the FlatNode.*/
  15
  16   public static Hashtable<FlatNode, Set<TempDescriptor>> computeLiveTemps(FlatMethod fm, int threshold) {
  17     return computeLiveTemps(fm, null, threshold);
  18   }
  19   public static Hashtable<FlatNode, Set<TempDescriptor>> computeLiveTemps(FlatMethod fm, LocalityBinding lb, int threshold) {
  20     Hashtable<FlatNode, Set<TempDescriptor>> nodetotemps=new Hashtable<FlatNode, Set<TempDescriptor>>();
  21
  22     Set<FlatNode> toprocess=fm.getNodeSet();
  23
  24     while(!toprocess.isEmpty()) {
  25       FlatNode fn=toprocess.iterator().next();
  26       toprocess.remove(fn);
  27
  28       List<TempDescriptor> reads=Arrays.asList(fn.readsTemps());
  29       List<TempDescriptor> writes=Arrays.asList(fn.writesTemps());
  30
  31       HashSet<TempDescriptor> tempset=new HashSet<TempDescriptor>();
  32       for(int i=0; i<fn.numNext(); i++) {
  33         FlatNode fnnext=fn.getNext(i);
  34         if (nodetotemps.containsKey(fnnext))
  35           tempset.addAll(nodetotemps.get(fnnext));
  36       }
  37       if ((lb==null)||(!(fn instanceof FlatGlobalConvNode))||
  38           ((FlatGlobalConvNode)fn).getLocality()==lb) {
  39         tempset.removeAll(writes);
  40         tempset.addAll(reads);
  41       }
  42       if (!nodetotemps.containsKey(fn)||
  43           !nodetotemps.get(fn).equals(tempset)) {
  44         nodetotemps.put(fn, tempset);
  45         if(threshold!=-1 && nodetotemps.size()>threshold){
  46           return null;
  47         }
  48         for(int i=0; i<fn.numPrev(); i++)
  49           toprocess.add(fn.getPrev(i));
  50       }
  51     }
  52     return nodetotemps;
  53   }
  54
  55   public static Hashtable<FlatNode, Set<TempDescriptor>> computeLiveOut(FlatMethod fm) {
  56     return computeLiveOut(fm, null);
  57   }
  58
  59   public static Hashtable<FlatNode, Set<TempDescriptor>> computeLiveOut(FlatMethod fm, LocalityBinding lb) {
  60     Hashtable<FlatNode, Set<TempDescriptor>> liveinmap=computeLiveTemps(fm, lb,-1);
  61     Hashtable<FlatNode, Set<TempDescriptor>> liveoutmap=new Hashtable<FlatNode, Set<TempDescriptor>>();
  62
  63     for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator(); fnit.hasNext();) {
  64       FlatNode fn=fnit.next();
  65       liveoutmap.put(fn, new HashSet<TempDescriptor>());
  66       for(int i=0;i<fn.numNext();i++) {
  67         FlatNode fn2=fn.getNext(i);
  68         liveoutmap.get(fn).addAll(liveinmap.get(fn2));
  69       }
  70     }
  71     return liveoutmap;
  72   }
  73
  74
  75   // Also allow an instantiation of this object that memoizes results
  76   protected Hashtable< FlatMethod, Hashtable< FlatNode, Set<TempDescriptor> > > fm2liveMap;
  77
  78   protected Hashtable< FlatMethod, Hashtable< FlatNode, Set<TempDescriptor> > > fm2liveOutMap;
  79
  80   public Liveness() {
  81     fm2liveMap = new Hashtable< FlatMethod, Hashtable< FlatNode, Set<TempDescriptor> > >();
  82     fm2liveOutMap = new Hashtable< FlatMethod, Hashtable< FlatNode, Set<TempDescriptor> > >();
  83   }
  84
  85   public Set<TempDescriptor> getLiveOutTemps( FlatMethod fm, FlatNode fn ) {
  86     if( !fm2liveOutMap.containsKey( fm ) ) {
  87       fm2liveOutMap.put( fm, Liveness.computeLiveOut( fm ) );
  88     }
  89     return fm2liveOutMap.get( fm ).get( fn );
  90   }
  91
  92   public Set<TempDescriptor> getLiveInTemps( FlatMethod fm, FlatNode fn ) {
  93     if( !fm2liveMap.containsKey( fm ) ) {
  94       fm2liveMap.put( fm, Liveness.computeLiveTemps( fm,-1 ) );
  95     }
  96     return fm2liveMap.get( fm ).get( fn );
  97   }
  98 }