Robust/src/Analysis/Loops/DomTree.java

   1 package Analysis.Loops;
   2 import java.util.Iterator;
   3 import java.util.Set;
   4 import java.util.HashSet;
   5 import java.util.Hashtable;
   6 import java.util.Vector;
   7 import java.util.Stack;
   8 import IR.Flat.FlatNode;
   9 import IR.Flat.FlatMethod;
  10
  11 public class DomTree {
  12   Hashtable<FlatNode, FlatNode> domtable;
  13   Vector<FlatNode> vec;
  14   Hashtable<FlatNode,Integer> vecindex;
  15   Hashtable<FlatNode, Set<FlatNode>> childtree;
  16
  17   public DomTree(FlatMethod fm, boolean postdominator) {
  18     analyze(fm, postdominator);
  19   }
  20
  21   public FlatNode idom(FlatNode fn) {
  22     return domtable.get(fn);
  23   }
  24
  25   public Set<FlatNode> children(FlatNode fn) {
  26     return childtree.get(fn);
  27   }
  28
  29   public void analyze(FlatMethod fm, boolean postdominator) {
  30     domtable=new Hashtable<FlatNode, FlatNode>();
  31     childtree=new Hashtable<FlatNode, Set<FlatNode>>();
  32     if (postdominator) {
  33       Set<FlatNode> fnodes=fm.getNodeSet();
  34       Vector<FlatNode> v=new Vector<FlatNode>();
  35       for(Iterator<FlatNode> fit=fnodes.iterator(); fit.hasNext(); ) {
  36         FlatNode fn=fit.next();
  37         if (fn.numNext()==0) {
  38           v.add(fn);
  39         }
  40       }
  41       FlatNode[] fnarray=new FlatNode[v.size()];
  42       for(int i=0; i<v.size(); i++) {
  43         fnarray[i]=v.elementAt(i);
  44         domtable.put(fnarray[i],fnarray[i]);
  45         HashSet<FlatNode> set=new HashSet<FlatNode> ();
  46         set.add(fnarray[i]);
  47         childtree.put(fnarray[i],set);
  48       }
  49       DFS(fnarray, postdominator);
  50     } else {
  51       DFS(new FlatNode[] {fm}, postdominator);
  52       HashSet<FlatNode> set=new HashSet<FlatNode> ();
  53       domtable.put(fm,fm);
  54       set.add(fm);
  55       childtree.put(fm,set);
  56     }
  57
  58     boolean changed=true;
  59     while(changed) {
  60       changed=false;
  61       for(int i=vec.size()-2; i>=0; i--) {
  62         FlatNode fn=vec.elementAt(i);
  63         FlatNode dom=null;
  64         for(int j=0; j<(postdominator?fn.numNext():fn.numPrev()); j++) {
  65           FlatNode np=postdominator?fn.getNext(j):fn.getPrev(j);
  66           FlatNode ndom=domtable.get(np);
  67           if (ndom!=null) {
  68             if (dom==null)
  69               dom=np;
  70             else
  71               dom=intersect(dom,np);
  72           }
  73         }
  74         if (!domtable.containsKey(fn)||
  75             !domtable.get(fn).equals(dom)) {
  76           domtable.put(fn,dom);
  77           if (!childtree.containsKey(dom))
  78             childtree.put(dom, new HashSet<FlatNode>());
  79           childtree.get(dom).add(fn);
  80           changed=true;
  81         }
  82       }
  83     }
  84   }
  85
  86   public FlatNode intersect(FlatNode fa, FlatNode fb) {
  87     int ifa=vecindex.get(fa).intValue();
  88     int ifb=vecindex.get(fb).intValue();
  89     while(ifa!=ifb) {
  90       while (ifa<ifb) {
  91         fa=domtable.get(fa);
  92         ifa=vecindex.get(fa).intValue();
  93       }
  94       while (ifb<ifa) {
  95         fb=domtable.get(fb);
  96         ifb=vecindex.get(fb).intValue();
  97       }
  98     }
  99     return fa;
 100   }
 101
 102
 103   public void DFS(FlatNode[] fm, boolean postdominator) {
 104     vec=new Vector<FlatNode>();
 105     vecindex=new Hashtable<FlatNode,Integer>();
 106     HashSet visited=new HashSet();
 107     Stack<FlatNode> stack=new Stack<FlatNode>();
 108     for(int i=0; i<fm.length; i++) {
 109       stack.push(fm[i]);
 110       visited.add(fm[i]);
 111     }
 112 mainloop:
 113     while(!stack.isEmpty()) {
 114       FlatNode fn=stack.peek();
 115       for(int i=0; i<(postdominator?fn.numPrev():fn.numNext()); i++) {
 116         FlatNode next=postdominator?fn.getPrev(i):fn.getNext(i);
 117         if (!visited.contains(next)) {
 118           visited.add(next);
 119           stack.push(next);
 120           continue mainloop;
 121         }
 122       }
 123       //We're done with this item, return
 124       vecindex.put(fn, new Integer(vec.size()));
 125       vec.add(fn);
 126       stack.pop();
 127     }
 128   }
 129 }