KickJava   Java API By Example, From Geeks To Geeks.

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


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 soot.jimple.toolkits.pointer.*;
33 import java.util.*;
34 import soot.util.*;
35
36 /** Implements an available expressions analysis on local variables.
37  * The current implementation is slow but correct.
38  * A better implementation would use an implicit universe and
39  * the kill rule would be computed on-the-fly for each statement. */
40 public class FastAvailableExpressionsAnalysis extends ForwardFlowAnalysis
41 {
42     SideEffectTester st;
43
44     Map unitToGenerateSet;
45     Map unitToPreserveSet;
46     Map rhsToContainingStmt;
47
48     FlowSet emptySet;
49
50     public FastAvailableExpressionsAnalysis(DirectedGraph dg, SootMethod m,
51             SideEffectTester st)
52     {
53         super(dg);
54         this.st = st;
55
56         ExceptionalUnitGraph g = (ExceptionalUnitGraph)dg;
57         LocalDefs ld = new SmartLocalDefs(g, new SimpleLiveLocals(g));
58
59         // maps an rhs to its containing stmt. object equality in rhs.
60 rhsToContainingStmt = new HashMap();
61
62         emptySet = new ToppedSet(new ArraySparseSet());
63
64         // Create generate sets
65 {
66             unitToGenerateSet = new HashMap(g.size() * 2 + 1, 0.7f);
67
68             Iterator unitIt = g.iterator();
69
70             while(unitIt.hasNext())
71             {
72                 Unit s = (Unit) unitIt.next();
73
74                 FlowSet genSet = (FlowSet)emptySet.clone();
75                 // In Jimple, expressions only occur as the RHS of an AssignStmt.
76 if (s instanceof AssignStmt)
77                 {
78                     AssignStmt as = (AssignStmt)s;
79                     if (as.getRightOp() instanceof Expr ||
80                         as.getRightOp() instanceof FieldRef)
81                     {
82                         Value gen = as.getRightOp();
83                         rhsToContainingStmt.put(gen, s);
84
85                         boolean cantAdd = false;
86                         if (gen instanceof NewExpr ||
87                                gen instanceof NewArrayExpr ||
88                                gen instanceof NewMultiArrayExpr)
89                             cantAdd = true;
90                         if (gen instanceof InvokeExpr)
91                             cantAdd = true;
92
93                         // Whee, double negative!
94 if (!cantAdd)
95                             genSet.add(gen, genSet);
96                     }
97                 }
98
99                 unitToGenerateSet.put(s, genSet);
100             }
101         }
102
103         doAnalysis();
104     }
105
106     protected Object JavaDoc newInitialFlow()
107     {
108         Object JavaDoc newSet = emptySet.clone();
109         ((ToppedSet)newSet).setTop(true);
110         return newSet;
111     }
112
113     protected Object JavaDoc entryInitialFlow()
114     {
115         return emptySet.clone();
116     }
117
118     protected void flowThrough(Object JavaDoc inValue, Object JavaDoc unit, Object JavaDoc outValue)
119     {
120         FlowSet in = (FlowSet) inValue, out = (FlowSet) outValue;
121
122         in.copy(out);
123         if (((ToppedSet)in).isTop())
124             return;
125
126         // Perform generation
127 out.union((FlowSet) unitToGenerateSet.get(unit), out);
128
129         // Perform kill.
130 Unit u = (Unit)unit;
131         List toRemove = new ArrayList();
132
133             if (((ToppedSet)out).isTop())
134             {
135                 throw new RuntimeException JavaDoc("trying to kill on topped set!");
136             }
137         List l = new LinkedList();
138             l.addAll(((FlowSet)out).toList());
139             Iterator it = l.iterator();
140
141             // iterate over things (avail) in out set.
142 while (it.hasNext())
143             {
144                 Value avail = (Value) it.next();
145                 if (avail instanceof FieldRef)
146                 {
147                     if (st.unitCanWriteTo(u, avail)) {
148                         out.remove(avail, out);
149                     }
150                 }
151                 else
152                 {
153                     Iterator usesIt = avail.getUseBoxes().iterator();
154
155                     // iterate over uses in each avail.
156 while (usesIt.hasNext())
157                     {
158                         Value use = ((ValueBox)usesIt.next()).getValue();
159                         
160                         if (st.unitCanWriteTo(u, use)) {
161                             out.remove(avail, out);
162                         }
163                     }
164                 }
165             }
166     }
167
168     protected void merge(Object JavaDoc in1, Object JavaDoc in2, Object JavaDoc out)
169     {
170         FlowSet inSet1 = (FlowSet) in1,
171             inSet2 = (FlowSet) in2;
172
173         FlowSet outSet = (FlowSet) out;
174
175         inSet1.intersection(inSet2, outSet);
176     }
177     
178     protected void copy(Object JavaDoc source, Object JavaDoc dest)
179     {
180         FlowSet sourceSet = (FlowSet) source,
181             destSet = (FlowSet) dest;
182             
183         sourceSet.copy(destSet);
184     }
185 }
186
187
Popular Tags