KickJava   Java API By Example, From Geeks To Geeks.

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


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 2003 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  * Wrapper class for a simple dominators analysis based on a simple
32  * flow analysis algorithm. Works with any DirectedGraph with a
33  * single head.
34  *
35  * @author Navindra Umanee
36  **/

37 public class SimpleDominatorsFinder implements DominatorsFinder
38 {
39     protected DirectedGraph graph;
40     protected Map nodeToDominators;
41
42     /**
43      * Compute dominators for provided singled-headed directed graph.
44      **/

45     public SimpleDominatorsFinder(DirectedGraph graph)
46     {
47         //if(Options.v().verbose())
48
//G.v().out.println("[" + graph.getBody().getMethod().getName() +
49
//"] Finding Dominators...");
50

51         this.graph = graph;
52         SimpleDominatorsAnalysis analysis = new SimpleDominatorsAnalysis(graph);
53
54         // build node to dominators map
55
{
56             nodeToDominators = new HashMap(graph.size() * 2 + 1, 0.7f);
57             
58             for(Iterator nodeIt = graph.iterator(); nodeIt.hasNext();) {
59                 Object JavaDoc node = nodeIt.next();
60                 FlowSet set = (FlowSet) analysis.getFlowAfter(node);
61                 nodeToDominators.put(node, set);
62             }
63         }
64     }
65
66     public DirectedGraph getGraph()
67     {
68         return graph;
69     }
70     
71     public List getDominators(Object JavaDoc node)
72     {
73         // non-backed list since FlowSet is an ArrayPackedFlowSet
74
return ((FlowSet) nodeToDominators.get(node)).toList();
75     }
76
77     public Object JavaDoc getImmediateDominator(Object JavaDoc node)
78     {
79         // root node
80
if(getGraph().getHeads().contains(node))
81             return null;
82
83     // could be memoised, I guess
84

85         List dominatorsList = getDominators(node);
86         dominatorsList.remove(node);
87
88         Iterator dominatorsIt = dominatorsList.iterator();
89         Object JavaDoc immediateDominator = null;
90
91         while((immediateDominator == null) && dominatorsIt.hasNext()){
92             Object JavaDoc dominator = dominatorsIt.next();
93
94             if(isDominatedByAll(dominator, dominatorsList))
95                 immediateDominator = dominator;
96         }
97
98         if(immediateDominator == null)
99             throw new RuntimeException JavaDoc("Assertion failed.");
100         
101         return immediateDominator;
102     }
103
104     public boolean isDominatedBy(Object JavaDoc node, Object JavaDoc dominator)
105     {
106         return getDominators(node).contains(dominator);
107     }
108
109     public boolean isDominatedByAll(Object JavaDoc node, Collection dominators)
110     {
111         return getDominators(node).containsAll(dominators);
112     }
113 }
114
115 /**
116  * Calculate dominators for basic blocks.
117  * <p> Uses the algorithm contained in Dragon book, pg. 670-1.
118  * <pre>
119  * D(n0) := { n0 }
120  * for n in N - { n0 } do D(n) := N;
121  * while changes to any D(n) occur do
122  * for n in N - {n0} do
123  * D(n) := {n} U (intersect of D(p) over all predecessors p of n)
124  * </pre>
125  **/

126 class SimpleDominatorsAnalysis extends ForwardFlowAnalysis
127 {
128     FlowSet emptySet;
129     Map nodeToGenerateSet;
130     
131     SimpleDominatorsAnalysis(DirectedGraph graph)
132     {
133         super(graph);
134
135         // define empty set, with proper universe for complementation
136
{
137             List nodes = new ArrayList();
138
139             for(Iterator nodesIt = graph.iterator(); nodesIt.hasNext();)
140                 nodes.add(nodesIt.next());
141             
142             FlowUniverse nodeUniverse = new CollectionFlowUniverse(nodes);
143             emptySet = new ArrayPackedSet(nodeUniverse);
144         }
145
146         // pre-compute generate sets
147
{
148             nodeToGenerateSet = new HashMap(graph.size() * 2 + 1, 0.7f);
149
150             for(Iterator nodeIt = graph.iterator(); nodeIt.hasNext();){
151                 Object JavaDoc s = nodeIt.next();
152                 FlowSet genSet = (FlowSet) emptySet.clone();
153                 genSet.add(s, genSet);
154                 nodeToGenerateSet.put(s, genSet);
155             }
156         }
157         
158         doAnalysis();
159     }
160
161     /**
162      * All OUTs are initialized to the full set of definitions
163      * OUT(Start) is tweaked in customizeInitialFlowGraph.
164      **/

165     protected Object JavaDoc newInitialFlow()
166     {
167         BoundedFlowSet initSet = (BoundedFlowSet) emptySet.clone();
168         initSet.complement();
169         return initSet;
170     }
171
172     /**
173      * OUT(Start) contains only Start at initialization time.
174      **/

175     protected Object JavaDoc entryInitialFlow()
176     {
177         List heads = graph.getHeads();
178
179         if(heads.size() != 1)
180             throw new RuntimeException JavaDoc("Assertion failed: Only one head expected.");
181
182         BoundedFlowSet initSet = (BoundedFlowSet) emptySet.clone();
183         initSet.add(heads.get(0));
184         return initSet;
185     }
186
187     /**
188      * We compute out straightforwardly.
189      **/

190     protected void flowThrough(Object JavaDoc inValue, Object JavaDoc block, Object JavaDoc outValue)
191     {
192         FlowSet in = (FlowSet) inValue, out = (FlowSet) outValue;
193
194         // Perform generation
195
in.union((FlowSet) nodeToGenerateSet.get(block), out);
196     }
197
198     /**
199      * All paths == Intersection.
200      **/

201     protected void merge(Object JavaDoc in1, Object JavaDoc in2, Object JavaDoc out)
202     {
203         FlowSet inSet1 = (FlowSet) in1,
204             inSet2 = (FlowSet) in2;
205
206         FlowSet outSet = (FlowSet) out;
207
208         inSet1.intersection(inSet2, outSet);
209     }
210
211     protected void copy(Object JavaDoc source, Object JavaDoc dest)
212     {
213         FlowSet sourceSet = (FlowSet) source,
214             destSet = (FlowSet) dest;
215
216         sourceSet.copy(destSet);
217     }
218 }
219
Popular Tags