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