1 package Analysis.Loops;
2 import java.util.Iterator;
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;
11 public class DomTree {
12 Hashtable<FlatNode, FlatNode> domtable;
14 Hashtable<FlatNode,Integer> vecindex;
15 Hashtable<FlatNode, Set<FlatNode>> childtree;
17 public DomTree(FlatMethod fm, boolean postdominator) {
18 analyze(fm, postdominator);
21 public FlatNode idom(FlatNode fn) {
22 return domtable.get(fn);
25 public Set<FlatNode> children(FlatNode fn) {
26 return childtree.get(fn);
29 public void analyze(FlatMethod fm, boolean postdominator) {
30 domtable=new Hashtable<FlatNode, FlatNode>();
31 childtree=new Hashtable<FlatNode, Set<FlatNode>>();
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) {
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> ();
47 childtree.put(fnarray[i],set);
49 DFS(fnarray, postdominator);
51 DFS(new FlatNode[] {fm}, postdominator);
52 HashSet<FlatNode> set=new HashSet<FlatNode> ();
55 childtree.put(fm,set);
61 for(int i=vec.size()-2; i>=0; i--) {
62 FlatNode fn=vec.elementAt(i);
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);
71 dom=intersect(dom,np);
74 if (!domtable.containsKey(fn)||
75 !domtable.get(fn).equals(dom)) {
77 if (!childtree.containsKey(dom))
78 childtree.put(dom, new HashSet<FlatNode>());
79 childtree.get(dom).add(fn);
86 public FlatNode intersect(FlatNode fa, FlatNode fb) {
87 int ifa=vecindex.get(fa).intValue();
88 int ifb=vecindex.get(fb).intValue();
92 ifa=vecindex.get(fa).intValue();
96 ifb=vecindex.get(fb).intValue();
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++) {
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)) {
123 //We're done with this item, return
124 vecindex.put(fn, new Integer(vec.size()));