Robust/src/Analysis/Loops/UseDef.java

   1 package Analysis.Loops;
   2
   3 import IR.Flat.*;
   4 import java.util.HashSet;
   5 import java.util.Hashtable;
   6 import java.util.Set;
   7 import java.util.Iterator;
   8
   9 public class UseDef{
  10   Hashtable<TempFlatPair, Set<FlatNode>> defs;
  11   Hashtable<TempFlatPair, Set<FlatNode>> uses;
  12
  13   public UseDef() {
  14   }
  15
  16   public UseDef(FlatMethod fm) {
  17     analyze(fm);
  18   }
  19
  20   /* Return FlatNodes that define Temp */
  21   public Set<FlatNode> defMap(FlatNode fn, TempDescriptor t) {
  22     Set<FlatNode> s=defs.get(new TempFlatPair(t,fn));
  23     if (s==null)
  24       return new HashSet<FlatNode>();
  25     else
  26       return s;
  27   }
  28
  29   /* Return FlatNodes that use Temp */
  30   public Set<FlatNode> useMap(FlatNode fn, TempDescriptor t) {
  31     Set<FlatNode> s=uses.get(new TempFlatPair(t,fn));
  32     if (s==null)
  33       return new HashSet<FlatNode>();
  34     else
  35       return s;
  36   }
  37
  38   public void analyze(FlatMethod fm) {
  39     Hashtable<FlatNode, Set<TempFlatPair>> tmp=new Hashtable<FlatNode, Set<TempFlatPair>>();
  40     HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
  41     toanalyze.addAll(fm.getNodeSet());
  42     while(!toanalyze.isEmpty()) {
  43       FlatNode fn=toanalyze.iterator().next();
  44       TempDescriptor[] fnwrites=fn.writesTemps();
  45
  46       toanalyze.remove(fn);
  47       HashSet<TempFlatPair> s=new HashSet<TempFlatPair>();
  48       for(int i=0;i<fn.numPrev();i++) {
  49         FlatNode prev=fn.getPrev(i);
  50         Set<TempFlatPair> prevs=tmp.get(prev);
  51         if (prevs!=null) {
  52           nexttfp:
  53           for(Iterator<TempFlatPair> tfit=prevs.iterator();tfit.hasNext();) {
  54             TempFlatPair tfp=tfit.next();
  55             for(int j=0;j<fnwrites.length;j++) {
  56               if (tfp.t==fnwrites[j])
  57                 continue nexttfp;
  58             }
  59             s.add(tfp);
  60           }
  61         }
  62         for(int j=0;j<fnwrites.length;j++) {
  63           TempFlatPair tfp=new TempFlatPair(fnwrites[j], fn);
  64           s.add(tfp);
  65         }
  66       }
  67       if (!tmp.containsKey(fn)||
  68           !tmp.get(fn).equals(s)) {
  69         tmp.put(fn,s);
  70         for(int i=0;i<fn.numNext();i++)
  71           toanalyze.add(fn.getNext(i));
  72       }
  73     }
  74     Set<FlatNode> fset=fm.getNodeSet();
  75     defs=new Hashtable<TempFlatPair, Set<FlatNode>>();
  76     uses=new Hashtable<TempFlatPair, Set<FlatNode>>();
  77     for(Iterator<FlatNode> fnit=fset.iterator();fnit.hasNext();) {
  78       FlatNode fn=fnit.next();
  79       TempDescriptor[] fnreads=fn.readsTemps();
  80       Set<TempFlatPair> tfpset=tmp.get(fn);
  81
  82       for(int i=0;i<fnreads.length;i++) {
  83         TempDescriptor readt=fnreads[i];
  84         for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
  85           TempFlatPair tfp=tfpit.next();
  86           if (tfp.t==readt) {
  87             //have use
  88             if (!uses.containsKey(tfp))
  89               uses.put(tfp,new HashSet<FlatNode>());
  90             uses.get(tfp).add(fn);
  91             TempFlatPair readtfp=new TempFlatPair(readt,fn);
  92             if (!defs.containsKey(readtfp))
  93               defs.put(readtfp,new HashSet<FlatNode>());
  94             defs.get(readtfp).add(tfp.f);
  95           }
  96         }
  97       }
  98     }
  99   }
 100 }
 101
 102 class TempFlatPair {
 103   FlatNode f;
 104   TempDescriptor t;
 105   TempFlatPair(TempDescriptor t, FlatNode f) {
 106     this.t=t;
 107     this.f=f;
 108   }
 109
 110   public int hashCode() {
 111     return f.hashCode()^t.hashCode();
 112   }
 113   public boolean equals(Object o) {
 114     TempFlatPair tf=(TempFlatPair)o;
 115     return t.equals(tf.t)&&f.equals(tf.f);
 116   }
 117 }