KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > jimple > toolkits > scalar > SlowAvailableExpressionsAnalysis


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 2000 Patrick Lam
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 /*
21  * Modified by the Sable Research Group and others 1997-1999.
22  * See the 'credits' file distributed with Soot for the complete list of
23  * contributors. (Soot is distributed at http://www.sable.mcgill.ca/soot)
24  */
25
26
27 package soot.jimple.toolkits.scalar;
28 import soot.*;
29 import soot.toolkits.scalar.*;
30 import soot.toolkits.graph.*;
31 import soot.jimple.*;
32 import java.util.*;
33 import soot.util.*;
34
35 // future work: fieldrefs.
36
37 /** Implements an available expressions analysis on local variables.
38  * The current implementation is slow but correct.
39  * A better implementation would use an implicit universe and
40  * the kill rule would be computed on-the-fly for each statement. */
41 public class SlowAvailableExpressionsAnalysis extends ForwardFlowAnalysis
42 {
43     Map unitToGenerateSet;
44     Map unitToPreserveSet;
45     Map rhsToContainingStmt;
46     private HashMap valueToEquivValue;
47
48     FlowSet emptySet;
49     
50     public SlowAvailableExpressionsAnalysis(DirectedGraph dg)
51     {
52         super(dg);
53
54         UnitGraph g = (UnitGraph)dg;
55
56         /* we need a universe of all of the expressions. */
57         Iterator unitsIt = g.getBody().getUnits().iterator();
58         ArrayList exprs = new ArrayList();
59
60         // Consider "a + b". containingExprs maps a and b (object equality) both to "a + b" (equivalence).
61 HashMap containingExprs = new HashMap();
62
63         // maps a Value to its EquivalentValue.
64 valueToEquivValue = new HashMap();
65
66         // maps an rhs to its containing stmt. object equality in rhs.
67 rhsToContainingStmt = new HashMap();
68
69         HashMap equivValToSiblingList = new HashMap();
70
71         // Create the set of all expressions, and a map from values to their containing expressions.
72 while (unitsIt.hasNext())
73         {
74             Stmt s = (Stmt)unitsIt.next();
75
76             if (s instanceof AssignStmt)
77             {
78                 Value v = ((AssignStmt)s).getRightOp();
79                 rhsToContainingStmt.put(v, s);
80                 EquivalentValue ev = (EquivalentValue)valueToEquivValue.get(v);
81                 if (ev == null)
82                 {
83                     ev = new EquivalentValue(v);
84                     valueToEquivValue.put(v, ev);
85                 }
86
87                 Chain sibList = null;
88                 if (equivValToSiblingList.get(ev) == null)
89                     { sibList = new HashChain(); equivValToSiblingList.put(ev, sibList); }
90                 else
91                     sibList = (Chain)equivValToSiblingList.get(ev);
92                 
93                 if (!sibList.contains(v)) sibList.add(v);
94
95                 if (!(v instanceof Expr))
96                     continue;
97
98                 if (!exprs.contains(v))
99                 {
100                     exprs.add(v);
101
102                     // Add map values for contained objects.
103 Iterator it = v.getUseBoxes().iterator();
104                     while (it.hasNext())
105                     {
106                         Value o = ((ValueBox)it.next()).getValue();
107                         EquivalentValue eo = (EquivalentValue)valueToEquivValue.get(o);
108                         if (eo == null)
109                         {
110                             eo = new EquivalentValue((Value)o);
111                             valueToEquivValue.put(o, eo);
112                         }
113
114                         if (equivValToSiblingList.get(eo) == null)
115                             { sibList = new HashChain(); equivValToSiblingList.put(eo, sibList); }
116                         else
117                             sibList = (Chain)equivValToSiblingList.get(eo);
118                         if (!sibList.contains(o)) sibList.add(o);
119
120                         Chain l = null;
121                         if (containingExprs.containsKey(eo))
122                             l = (HashChain)containingExprs.get(eo);
123                         else
124                         {
125                             l = new HashChain();
126                             containingExprs.put(eo, l);
127                         }
128
129                         if (!l.contains(ev))
130                             l.add(ev);
131                     }
132                 }
133             }
134         }
135
136         FlowUniverse exprUniv = new ArrayFlowUniverse(exprs.toArray());
137         emptySet = new ArrayPackedSet(exprUniv);
138
139         // Create preserve sets.
140 {
141             unitToPreserveSet = new HashMap(g.size() * 2 + 1, 0.7f);
142
143             Iterator unitIt = g.iterator();
144
145             while(unitIt.hasNext())
146             {
147                 BoundedFlowSet killSet = new ArrayPackedSet(exprUniv);
148                 Unit s = (Unit) unitIt.next();
149
150                 // We need to do more! In particular handle invokeExprs, etc.
151
152                 // For each def (say of x), kill the set of exprs containing x.
153 Iterator boxIt = s.getDefBoxes().iterator();
154
155                 while(boxIt.hasNext())
156                 {
157                     ValueBox box = (ValueBox) boxIt.next();
158                     Value v = box.getValue();
159                     EquivalentValue ev = (EquivalentValue)valueToEquivValue.get(v);
160
161                     HashChain c = (HashChain)containingExprs.get(ev);
162                     if (c != null)
163                     {
164                         Iterator it = c.iterator();
165                         while (it.hasNext())
166                         {
167                             // Add all siblings of it.next().
168 EquivalentValue container = (EquivalentValue)it.next();
169                             Iterator sibListIt = ((Chain)equivValToSiblingList.get(container)).iterator();
170                             while (sibListIt.hasNext())
171                                 killSet.add(sibListIt.next(), killSet);
172                         }
173                     }
174                 }
175
176                 // Store complement
177 killSet.complement(killSet);
178                     unitToPreserveSet.put(s, killSet);
179             }
180         }
181
182         // Create generate sets
183 {
184             unitToGenerateSet = new HashMap(g.size() * 2 + 1, 0.7f);
185
186             Iterator unitIt = g.iterator();
187
188             while(unitIt.hasNext())
189             {
190                 Unit s = (Unit) unitIt.next();
191
192                 BoundedFlowSet genSet = new ArrayPackedSet(exprUniv);
193                 // In Jimple, expressions only occur as the RHS of an AssignStmt.
194 if (s instanceof AssignStmt)
195
196                 {
197                     AssignStmt as = (AssignStmt)s;
198                     if (as.getRightOp() instanceof Expr)
199                     {
200                         // canonical rep of as.getRightOp();
201 Value gen = as.getRightOp();
202
203                         boolean cantAdd = false;
204                         if (gen instanceof NewExpr ||
205                                gen instanceof NewArrayExpr ||
206                                gen instanceof NewMultiArrayExpr)
207                             cantAdd = true;
208                         if (gen instanceof InvokeExpr)
209                             cantAdd = true;
210
211                         // Whee, double negative!
212 if (!cantAdd)
213                             genSet.add(gen, genSet);
214                     }
215                 }
216
217                 // remove the kill set
218 genSet.intersection((FlowSet)unitToPreserveSet.get(s), genSet);
219
220                 unitToGenerateSet.put(s, genSet);
221             }
222         }
223
224         doAnalysis();
225     }
226
227     protected Object JavaDoc newInitialFlow()
228     {
229         BoundedFlowSet out = (BoundedFlowSet)emptySet.clone();
230         out.complement(out);
231         return out;
232     }
233
234     protected Object JavaDoc entryInitialFlow()
235     {
236         return emptySet.clone();
237     }
238
239     protected void flowThrough(Object JavaDoc inValue, Object JavaDoc unit, Object JavaDoc outValue)
240     {
241         FlowSet in = (FlowSet) inValue, out = (FlowSet) outValue;
242
243         // Perform kill
244 in.intersection((FlowSet) unitToPreserveSet.get(unit), out);
245
246         // Perform generation
247 out.union((FlowSet) unitToGenerateSet.get(unit), out);
248     }
249
250     protected void merge(Object JavaDoc in1, Object JavaDoc in2, Object JavaDoc out)
251     {
252         FlowSet inSet1 = (FlowSet) in1,
253             inSet2 = (FlowSet) in2;
254
255         FlowSet outSet = (FlowSet) out;
256
257         inSet1.intersection(inSet2, outSet);
258     }
259     
260     protected void copy(Object JavaDoc source, Object JavaDoc dest)
261     {
262         FlowSet sourceSet = (FlowSet) source,
263             destSet = (FlowSet) dest;
264             
265         sourceSet.copy(destSet);
266     }
267 }
268
269
Popular Tags