KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > toolkits > graph > MHGDominatorsFinder


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 2005 Navindra Umanee <navindra@cs.mcgill.ca>
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Lesser General Public
6  * License as published by the Free Software Foundation; either
7  * version 2.1 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12  * Lesser General Public License for more details.
13  *
14  * You should have received a copy of the GNU Lesser General Public
15  * License along with this library; if not, write to the
16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17  * Boston, MA 02111-1307, USA.
18  */
19
20 package soot.toolkits.graph;
21
22 import soot.*;
23 import soot.util.*;
24 import java.util.*;
25 import soot.jimple.*;
26 import soot.options.*;
27 import soot.toolkits.graph.*;
28 import soot.toolkits.scalar.*;
29
30 /**
31  * Dominators finder for multi-headed graph.
32  *
33  * @author Navindra Umanee
34  **/
35 public class MHGDominatorsFinder implements DominatorsFinder
36 {
37     protected DirectedGraph graph;
38     protected Map nodeToDominators;
39
40     public MHGDominatorsFinder(DirectedGraph graph)
41     {
42         //if(Options.v().verbose())
43 //G.v().out.println("[" + graph.getBody().getMethod().getName() +
44 //"] Finding Dominators...");
45
46         this.graph = graph;
47         MHGDominatorsAnalysis analysis = new MHGDominatorsAnalysis(graph);
48         analysis.doAnalysis();
49         nodeToDominators = analysis.nodeToFlowSet;
50         /*
51         for(Iterator i = nodeToDominators.keySet().iterator(); i.hasNext();){
52             Object key = i.next();
53             System.out.println(key + " is dominated by: ");
54             for(Iterator j = ((FlowSet)nodeToDominators.get(key)).iterator(); j.hasNext();)
55                 System.out.println(j.next());
56             System.out.println();
57         }
58         */
59     }
60
61     public DirectedGraph getGraph()
62     {
63         return graph;
64     }
65     
66     public List getDominators(Object JavaDoc node)
67     {
68         // non-backed list since FlowSet is an ArrayPackedFlowSet
69 return ((FlowSet) nodeToDominators.get(node)).toList();
70     }
71
72     public Object JavaDoc getImmediateDominator(Object JavaDoc node)
73     {
74         // root node
75 if(getGraph().getHeads().contains(node))
76             return null;
77
78     // could be memoised, I guess
79
80         List dominatorsList = getDominators(node);
81         dominatorsList.remove(node);
82
83         Iterator dominatorsIt = dominatorsList.iterator();
84         Object JavaDoc immediateDominator = null;
85
86         while((immediateDominator == null) && dominatorsIt.hasNext()){
87             Object JavaDoc dominator = dominatorsIt.next();
88
89             if(isDominatedByAll(dominator, dominatorsList))
90                 immediateDominator = dominator;
91         }
92
93         if(immediateDominator == null)
94             throw new RuntimeException JavaDoc("Assertion failed.");
95         
96         return immediateDominator;
97     }
98
99     public boolean isDominatedBy(Object JavaDoc node, Object JavaDoc dominator)
100     {
101         return getDominators(node).contains(dominator);
102     }
103
104     public boolean isDominatedByAll(Object JavaDoc node, Collection dominators)
105     {
106         return getDominators(node).containsAll(dominators);
107     }
108 }
109
110 /**
111  * Calculate dominators for basic blocks.
112  * <p> Uses the algorithm contained in Dragon book, pg. 670-1.
113  * <pre>
114  * D(n0) := { n0 }
115  * for n in N - { n0 } do D(n) := N;
116  * while changes to any D(n) occur do
117  * for n in N - {n0} do
118  * D(n) := {n} U (intersect of D(p) over all predecessors p of n)
119  * </pre>
120  **/
121 class MHGDominatorsAnalysis
122 {
123     DirectedGraph graph;
124     List heads;
125     ArraySparseSet fullSet;
126     Map nodeToFlowSet;
127     
128     public MHGDominatorsAnalysis(DirectedGraph graph)
129     {
130         this.graph = graph;
131         heads = graph.getHeads();
132         nodeToFlowSet = new HashMap();
133
134         fullSet = new ArraySparseSet();
135         for(Iterator i = graph.iterator(); i.hasNext();)
136             fullSet.add(i.next());
137         
138         for(Iterator i = graph.iterator(); i.hasNext();){
139             Object JavaDoc o = i.next();
140             if(heads.contains(o)){
141                 ArraySparseSet self = new ArraySparseSet();
142                 self.add(o);
143                 nodeToFlowSet.put(o, self);
144             }
145             else{
146                 nodeToFlowSet.put(o, fullSet.clone());
147             }
148         }
149     }
150
151     public void doAnalysis()
152     {
153         boolean change = true;
154         while(change){
155             change = false;
156             for(Iterator i = graph.iterator(); i.hasNext();){
157                 Object JavaDoc o = i.next();
158
159                 ArraySparseSet predsIntersect = new ArraySparseSet();
160                 if(heads.contains(o))
161                     predsIntersect.add(o);
162                 else
163                     predsIntersect.union(fullSet, predsIntersect);
164
165                 for(Iterator j = graph.getPredsOf(o).iterator(); j.hasNext();){
166                     ArraySparseSet predSet = (ArraySparseSet) nodeToFlowSet.get(j.next());
167                     predsIntersect.intersection(predSet, predsIntersect);
168                 }
169
170                 ArraySparseSet oldSet = (ArraySparseSet) nodeToFlowSet.get(o);
171                 ArraySparseSet newSet = new ArraySparseSet();
172                 newSet.add(o);
173                 newSet.union(predsIntersect, newSet);
174                 if(!newSet.equals(oldSet)){
175                     nodeToFlowSet.put(o, newSet);
176                     change = true;
177                 }
178             }
179         }
180     }
181 }
182
Popular Tags