Robust/src/Analysis/ReachingDefs.java

   1 package Analysis;
   2
   3 import IR.Flat.*;
   4 import java.util.HashSet;
   5 import java.util.Set;
   6 import java.util.Iterator;
   7 import java.util.Hashtable;
   8 import Analysis.Locality.*;
   9
  10 public class ReachingDefs {
  11   /* This methods takes in a FlatMethod and returns a map from a
  12    * FlatNode to the set of live temps for that FlatNode.*/
  13
  14   /* liveintoset if true computes the reaching defs into the node and if false computes the reaching defs out of the node. */
  15
  16   public static Hashtable<FlatNode, Hashtable<TempDescriptor, Set<FlatNode>>> computeReachingDefs(FlatMethod fm, Hashtable<FlatNode, Set<TempDescriptor>> livemap, boolean liveintoset) {
  17     return computeReachingDefs(fm, livemap, liveintoset, null);
  18   }
  19
  20   public static Hashtable<FlatNode, Hashtable<TempDescriptor, Set<FlatNode>>> computeReachingDefs(FlatMethod fm, Hashtable<FlatNode, Set<TempDescriptor>> livemap, boolean liveintoset, LocalityBinding lb) {
  21     Hashtable<FlatNode, Hashtable<TempDescriptor, Set<FlatNode>>> nodetotemps=new Hashtable<FlatNode, Hashtable<TempDescriptor,Set<FlatNode>>>();
  22
  23     Hashtable<FlatNode, Hashtable<TempDescriptor, Set<FlatNode>>> liveinto=liveintoset?new Hashtable<FlatNode, Hashtable<TempDescriptor,Set<FlatNode>>>():null;
  24
  25
  26     Set<FlatNode> toprocess=fm.getNodeSet();
  27
  28     while(!toprocess.isEmpty()) {
  29       FlatNode fn=toprocess.iterator().next();
  30       toprocess.remove(fn);
  31
  32       Hashtable<TempDescriptor, Set<FlatNode>> tempset=new Hashtable<TempDescriptor, Set<FlatNode>>();
  33
  34       Set<TempDescriptor> livetempset=livemap.get(fn);
  35
  36       for(int i=0; i<fn.numPrev(); i++) {
  37         FlatNode fnprev=fn.getPrev(i);
  38         if (nodetotemps.containsKey(fnprev)) {
  39           Hashtable<TempDescriptor,Set<FlatNode>> prevtable=nodetotemps.get(fnprev);
  40           for(Iterator<TempDescriptor> tmpit=prevtable.keySet().iterator();tmpit.hasNext();) {
  41             TempDescriptor tmp=tmpit.next();
  42             if (!livetempset.contains(tmp))
  43               continue;
  44             if (!tempset.containsKey(tmp))
  45               tempset.put(tmp, new HashSet<FlatNode>());
  46             tempset.get(tmp).addAll(prevtable.get(tmp));
  47           }
  48         }
  49       }
  50
  51       if (liveintoset) {
  52         liveinto.put(fn, new Hashtable<TempDescriptor, Set<FlatNode>>(tempset));
  53       }
  54
  55       if (lb==null||(!(fn instanceof FlatGlobalConvNode))||
  56           ((FlatGlobalConvNode) fn).getLocality()==lb) {
  57         TempDescriptor writes[]=fn.writesTemps();
  58         for(int i=0;i<writes.length;i++) {
  59           HashSet<FlatNode> s=new HashSet<FlatNode>();
  60           s.add(fn);
  61           tempset.put(writes[i],s);
  62         }
  63       }
  64       if (!nodetotemps.containsKey(fn)||
  65           !nodetotemps.get(fn).equals(tempset)) {
  66         nodetotemps.put(fn, tempset);
  67         for(int i=0; i<fn.numNext(); i++)
  68           toprocess.add(fn.getNext(i));
  69       }
  70     }
  71     return liveintoset?liveinto:nodetotemps;
  72   }
  73 }