Robust/src/Analysis/Loops/DomTree.java

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