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) {
  17     return computeLiveTemps(fm, null);
  18   }
  19   public static Hashtable<FlatNode, Set<TempDescriptor>> computeLiveTemps(FlatMethod fm, LocalityBinding lb) {
  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         for(int i=0; i<fn.numPrev(); i++)
  46           toprocess.add(fn.getPrev(i));
  47       }
  48     }
  49     return nodetotemps;
  50   }
  51
  52   public static Hashtable<FlatNode, Set<TempDescriptor>> computeLiveOut(FlatMethod fm) {
  53     return computeLiveOut(fm, null);
  54   }
  55
  56   public static Hashtable<FlatNode, Set<TempDescriptor>> computeLiveOut(FlatMethod fm, LocalityBinding lb) {
  57     Hashtable<FlatNode, Set<TempDescriptor>> liveinmap=computeLiveTemps(fm, lb);
  58     Hashtable<FlatNode, Set<TempDescriptor>> liveoutmap=new Hashtable<FlatNode, Set<TempDescriptor>>();
  59
  60     for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator(); fnit.hasNext();) {
  61       FlatNode fn=fnit.next();
  62       liveoutmap.put(fn, new HashSet<TempDescriptor>());
  63       for(int i=0;i<fn.numNext();i++) {
  64         FlatNode fn2=fn.getNext(i);
  65         liveoutmap.get(fn).addAll(liveinmap.get(fn2));
  66       }
  67     }
  68     return liveoutmap;
  69   }
  70
  71
  72   // Also allow an instantiation of this object that memoizes results
  73   protected Hashtable< FlatMethod, Hashtable< FlatNode, Set<TempDescriptor> > > fm2liveMap;
  74
  75   protected Hashtable< FlatMethod, Hashtable< FlatNode, Set<TempDescriptor> > > fm2liveOutMap;
  76
  77   public Liveness() {
  78     fm2liveMap = new Hashtable< FlatMethod, Hashtable< FlatNode, Set<TempDescriptor> > >();
  79     fm2liveOutMap = new Hashtable< FlatMethod, Hashtable< FlatNode, Set<TempDescriptor> > >();
  80   }
  81
  82   public Set<TempDescriptor> getLiveOutTemps( FlatMethod fm, FlatNode fn ) {
  83     if( !fm2liveOutMap.containsKey( fm ) ) {
  84       fm2liveOutMap.put( fm, Liveness.computeLiveOut( fm ) );
  85     }
  86     return fm2liveOutMap.get( fm ).get( fn );
  87   }
  88
  89   public Set<TempDescriptor> getLiveInTemps( FlatMethod fm, FlatNode fn ) {
  90     if( !fm2liveMap.containsKey( fm ) ) {
  91       fm2liveMap.put( fm, Liveness.computeLiveTemps( fm ) );
  92     }
  93     return fm2liveMap.get( fm ).get( fn );
  94   }
  95 }