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
  11 public class Liveness {
  12   /* This methods takes in a FlatMethod and returns a map from a
  13    * FlatNode to the set of temps that are live into the FlatNode.*/
  14
  15   public static Hashtable<FlatNode, Set<TempDescriptor>> computeLiveTemps(FlatMethod fm) {
  16     Hashtable<FlatNode, Set<TempDescriptor>> nodetotemps=new Hashtable<FlatNode, Set<TempDescriptor>>();
  17
  18     Set<FlatNode> toprocess=fm.getNodeSet();
  19
  20     while(!toprocess.isEmpty()) {
  21       FlatNode fn=toprocess.iterator().next();
  22       toprocess.remove(fn);
  23
  24       List<TempDescriptor> reads=Arrays.asList(fn.readsTemps());
  25       List<TempDescriptor> writes=Arrays.asList(fn.writesTemps());
  26
  27       HashSet<TempDescriptor> tempset=new HashSet<TempDescriptor>();
  28       for(int i=0; i<fn.numNext(); i++) {
  29         FlatNode fnnext=fn.getNext(i);
  30         if (nodetotemps.containsKey(fnnext))
  31           tempset.addAll(nodetotemps.get(fnnext));
  32       }
  33       tempset.removeAll(writes);
  34       tempset.addAll(reads);
  35       if (!nodetotemps.containsKey(fn)||
  36           !nodetotemps.get(fn).equals(tempset)) {
  37         nodetotemps.put(fn, tempset);
  38         for(int i=0; i<fn.numPrev(); i++)
  39           toprocess.add(fn.getPrev(i));
  40       }
  41     }
  42     return nodetotemps;
  43   }
  44
  45   public static Hashtable<FlatNode, Set<TempDescriptor>> computeLiveOut(FlatMethod fm) {
  46     Hashtable<FlatNode, Set<TempDescriptor>> liveinmap=computeLiveTemps(fm);
  47     Hashtable<FlatNode, Set<TempDescriptor>> liveoutmap=new Hashtable<FlatNode, Set<TempDescriptor>>();
  48
  49     for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator(); fnit.hasNext();) {
  50       FlatNode fn=fnit.next();
  51       liveoutmap.put(fn, new HashSet<TempDescriptor>());
  52       for(int i=0;i<fn.numNext();i++) {
  53         FlatNode fn2=fn.getNext(i);
  54         liveoutmap.get(fn).addAll(liveinmap.get(fn2));
  55       }
  56     }
  57     return liveoutmap;
  58   }
  59 }