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     return defs.get(new TempFlatPair(t,fn));
  23   }
  24
  25   /* Return FlatNodes that use Temp */
  26   public Set<FlatNode> useMap(FlatNode fn, TempDescriptor t) {
  27     return uses.get(new TempFlatPair(t,fn));
  28   }
  29
  30   public void analyze(FlatMethod fm) {
  31     Hashtable<FlatNode, Set<TempFlatPair>> tmp=new Hashtable<FlatNode, Set<TempFlatPair>>();
  32     HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
  33     toanalyze.addAll(fm.getNodeSet());
  34     while(!toanalyze.isEmpty()) {
  35       FlatNode fn=toanalyze.iterator().next();
  36       TempDescriptor[] fnwrites=fn.writesTemps();
  37
  38       toanalyze.remove(fn);
  39       HashSet<TempFlatPair> s=new HashSet<TempFlatPair>();
  40       for(int i=0;i<fn.numPrev();i++) {
  41         FlatNode prev=fn.getPrev(i);
  42         Set<TempFlatPair> prevs=tmp.get(prev);
  43         nexttfp:
  44         for(Iterator<TempFlatPair> tfit=prevs.iterator();tfit.hasNext();) {
  45           TempFlatPair tfp=tfit.next();
  46           for(int j=0;j<fnwrites.length;j++) {
  47             if (tfp.t==fnwrites[j])
  48               continue nexttfp;
  49           }
  50           s.add(tfp);
  51         }
  52         for(int j=0;j<fnwrites.length;j++) {
  53           TempFlatPair tfp=new TempFlatPair(fnwrites[j], fn);
  54           s.add(tfp);
  55         }
  56       }
  57       if (!tmp.containsKey(fn)||
  58           !tmp.get(fn).equals(s)) {
  59         tmp.put(fn,s);
  60         for(int i=0;i<fn.numNext();i++)
  61           toanalyze.add(fn.getNext(i));
  62       }
  63     }
  64     Set<FlatNode> fset=fm.getNodeSet();
  65     defs=new Hashtable<TempFlatPair, Set<FlatNode>>();
  66     uses=new Hashtable<TempFlatPair, Set<FlatNode>>();
  67     for(Iterator<FlatNode> fnit=fset.iterator();fnit.hasNext();) {
  68       FlatNode fn=fnit.next();
  69       TempDescriptor[] fnreads=fn.readsTemps();
  70       Set<TempFlatPair> tfpset=tmp.get(fn);
  71
  72       for(int i=0;i<fnreads.length;i++) {
  73         TempDescriptor readt=fnreads[i];
  74         for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
  75           TempFlatPair tfp=tfpit.next();
  76           if (tfp.t==readt) {
  77             //have use
  78             if (!uses.containsKey(tfp))
  79               uses.put(tfp,new HashSet<FlatNode>());
  80             uses.get(tfp).add(fn);
  81             TempFlatPair readtfp=new TempFlatPair(readt,fn);
  82             if (!defs.containsKey(readtfp))
  83               defs.put(readtfp,new HashSet<FlatNode>());
  84             defs.get(readtfp).add(tfp.f);
  85           }
  86         }
  87       }
  88     }
  89   }
  90 }
  91
  92 class TempFlatPair {
  93   FlatNode f;
  94   TempDescriptor t;
  95   TempFlatPair(TempDescriptor t, FlatNode f) {
  96     this.t=t;
  97     this.f=f;
  98   }
  99
 100   public int hashCode() {
 101     return f.hashCode()^t.hashCode();
 102   }
 103   public boolean equals(Object o) {
 104     TempFlatPair tf=(TempFlatPair)o;
 105     return t.equals(tf.t)&&f.equals(tf.f);
 106   }
 107 }