KickJava   Java API By Example, From Geeks To Geeks.

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


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 2003 Jennifer Lhotak
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.toolkits.scalar.*;
26 import soot.options.*;
27
28 // STEP 1: What are we computing?
29 // SETS OF Units that are dominators => Use ArraySparseSet.
30 //
31 // STEP 2: Precisely define what we are computing.
32 // For each statement compute the set of stmts that dominate it
33 //
34 // STEP 3: Decide whether it is a backwards or forwards analysis.
35 // FORWARDS
36 //
37 //
38 public class DominatorAnalysis extends ForwardFlowAnalysis {
39
40     private UnitGraph g;
41     private FlowSet allNodes;
42     
43     public DominatorAnalysis(UnitGraph g)
44     {
45         super(g);
46         this.g = g;
47
48         initAllNodes();
49
50         doAnalysis();
51         
52     }
53
54     private void initAllNodes(){
55         allNodes = new ArraySparseSet();
56         Iterator it = g.iterator();
57         while (it.hasNext()){
58             allNodes.add(it.next());
59         }
60     }
61
62
63 // STEP 4: Is the merge operator union or intersection?
64 // INTERSECTION
65
66     protected void merge(Object JavaDoc in1, Object JavaDoc in2, Object JavaDoc out)
67     {
68         FlowSet inSet1 = (FlowSet) in1;
69         FlowSet inSet2 = (FlowSet) in2;
70         FlowSet outSet = (FlowSet) out;
71
72         inSet1.intersection(inSet2, outSet);
73     
74     }
75
76     protected void copy(Object JavaDoc source, Object JavaDoc dest) {
77
78         FlowSet sourceIn = (FlowSet)source;
79         FlowSet destOut = (FlowSet)dest;
80         
81         sourceIn.copy(destOut);
82
83     }
84    
85 // STEP 5: Define flow equations.
86 // dom(s) = s U ( ForAll Y in pred(s): Intersection (dom(y)))
87 // ie: dom(s) = s and whoever dominates all the predeccessors of s
88 //
89
90     protected void flowThrough(Object JavaDoc inValue, Object JavaDoc unit,
91             Object JavaDoc outValue)
92     {
93         FlowSet in = (FlowSet) inValue;
94         FlowSet out = (FlowSet) outValue;
95         Unit s = (Unit) unit;
96
97         if (isUnitStartNode(s)){
98             //System.out.println("s: "+s+" is start node");
99 out.clear();
100             out.add(s);
101             //System.out.println("in: "+in+" out: "+out);
102 }
103         else {
104         
105             //System.out.println("s: "+s+" is not start node");
106 FlowSet domsOfPreds = (FlowSet) allNodes.clone();
107         
108             // for each pred of s
109 Iterator predsIt = g.getPredsOf(s).iterator();
110             while (predsIt.hasNext()){
111                 Unit pred = (Unit)predsIt.next();
112                 // get the unitToBeforeFlow and find the intersection
113 //System.out.println("pred: "+pred);
114 FlowSet next = (FlowSet) unitToAfterFlow.get(pred);
115                 //System.out.println("next: "+next);
116 //System.out.println("in before intersect: "+in);
117 in.intersection(next, in);
118                 //System.out.println("in after intersect: "+in);
119 }
120         
121             // intersected with in
122
123             //System.out.println("out init: "+out);
124 out.intersection(in, out);
125             out.add(s);
126             //System.out.println("out after: "+out);
127 }
128     }
129     
130     private boolean isUnitStartNode(Unit s){
131         //System.out.println("head: "+g.getHeads().get(0));
132 if (s.equals(g.getHeads().get(0))) return true;
133         return false;
134     }
135
136 // STEP 6: Determine value for start/end node, and
137 // initial approximation.
138 // dom(startNode) = startNode
139 // dom(node) = allNodes
140 //
141 protected Object JavaDoc entryInitialFlow()
142     {
143
144         FlowSet fs = new ArraySparseSet();
145         List heads = g.getHeads();
146         if (heads.size() != 1) {
147             throw new RuntimeException JavaDoc("Expect one start node only.");
148         }
149         fs.add(heads.get(0));
150         return fs;
151     }
152
153
154     protected Object JavaDoc newInitialFlow()
155     {
156         return allNodes.clone();
157     }
158         
159
160 }
161
Popular Tags