|
1
19
20 package soot.jimple.spark.solver;
21 import soot.jimple.spark.*;
22 import soot.jimple.spark.pag.*;
23 import soot.jimple.spark.sets.*;
24 import soot.jimple.spark.internal.*;
25 import soot.*;
26 import soot.util.*;
27 import soot.util.queue.*;
28 import java.util.*;
29 import soot.options.SparkOptions;
30
31
35
36 public final class PropAlias extends Propagator {
37 protected final Set varNodeWorkList = new TreeSet();
38 protected Set aliasWorkList;
39 protected Set fieldRefWorkList = new HashSet();
40 protected Set outFieldRefWorkList = new HashSet();
41
42 public PropAlias( PAG pag ) {
43 this.pag = pag;
44 loadSets = new LargeNumberedMap( pag.getFieldRefNodeNumberer() );
45 }
46
47
48 public final void propagate() {
49 ofcg = pag.getOnFlyCallGraph();
50 new TopoSorter( pag, false ).sort();
51 for( Iterator frIt = pag.loadSources().iterator(); frIt.hasNext(); ) {
52 final FieldRefNode fr = (FieldRefNode) frIt.next();
53 fieldToBase.put( fr.getField(), fr.getBase() );
54 }
55 for( Iterator frIt = pag.storeInvSources().iterator(); frIt.hasNext(); ) {
56 final FieldRefNode fr = (FieldRefNode) frIt.next();
57 fieldToBase.put( fr.getField(), fr.getBase() );
58 }
59 for( Iterator it = pag.allocSources().iterator(); it.hasNext(); ) {
60 handleAllocNode( (AllocNode) it.next() );
61 }
62
63 boolean verbose = pag.getOpts().verbose();
64 do {
65 if( verbose ) {
66 G.v().out.println( "Worklist has "+varNodeWorkList.size()+
67 " nodes." );
68 }
69 aliasWorkList = new HashSet();
70 while( !varNodeWorkList.isEmpty() ) {
71 VarNode src = (VarNode) varNodeWorkList.iterator().next();
72 varNodeWorkList.remove( src );
73 aliasWorkList.add( src );
74 handleVarNode( src );
75 }
76 if( verbose ) {
77 G.v().out.println( "Now handling field references" );
78 }
79
80 for( Iterator srcIt = aliasWorkList.iterator(); srcIt.hasNext(); ) {
81
82 final VarNode src = (VarNode) srcIt.next();
83 for( Iterator srcFrIt = src.getAllFieldRefs().iterator(); srcFrIt.hasNext(); ) {
84 final FieldRefNode srcFr = (FieldRefNode) srcFrIt.next();
85 SparkField field = srcFr.getField();
86 for( Iterator dstIt = fieldToBase.get( field ).iterator(); dstIt.hasNext(); ) {
87 final VarNode dst = (VarNode) dstIt.next();
88 if( src.getP2Set().hasNonEmptyIntersection(
89 dst.getP2Set() ) ) {
90 FieldRefNode dstFr = dst.dot( field );
91 aliasEdges.put( srcFr, dstFr );
92 aliasEdges.put( dstFr, srcFr );
93 fieldRefWorkList.add( srcFr );
94 fieldRefWorkList.add( dstFr );
95 if( makeP2Set( dstFr ).addAll(
96 srcFr.getP2Set().getOldSet(), null ) ) {
97 outFieldRefWorkList.add( dstFr );
98 }
99 if( makeP2Set( srcFr ).addAll(
100 dstFr.getP2Set().getOldSet(), null ) ) {
101 outFieldRefWorkList.add( srcFr );
102 }
103 }
104 }
105 }
106 }
107 for( Iterator srcIt = fieldRefWorkList.iterator(); srcIt.hasNext(); ) {
108 final FieldRefNode src = (FieldRefNode) srcIt.next();
109 for( Iterator dstIt = aliasEdges.get( src ).iterator(); dstIt.hasNext(); ) {
110 final FieldRefNode dst = (FieldRefNode) dstIt.next();
111 if( makeP2Set( dst ).addAll( src.getP2Set().getNewSet(), null ) ) {
112 outFieldRefWorkList.add( dst );
113 }
114 }
115 src.getP2Set().flushNew();
116 }
117 fieldRefWorkList = new HashSet();
118 for( Iterator srcIt = outFieldRefWorkList.iterator(); srcIt.hasNext(); ) {
119 final FieldRefNode src = (FieldRefNode) srcIt.next();
120 PointsToSetInternal set = getP2Set( src ).getNewSet();
121 if( set.isEmpty() ) continue;
122 Node[] targets = pag.loadLookup( src );
123 for( int i = 0; i < targets.length; i++ ) {
124 VarNode target = (VarNode) targets[i];
125 if( target.makeP2Set().addAll( set, null ) ) {
126 addToWorklist( target );
127 }
128 }
129 getP2Set( src ).flushNew();
130 }
131 outFieldRefWorkList = new HashSet();
132 } while( !varNodeWorkList.isEmpty() );
133 }
134
135
136
137
138
140 protected final boolean handleAllocNode( AllocNode src ) {
141 boolean ret = false;
142 Node[] targets = pag.allocLookup( src );
143 for( int i = 0; i < targets.length; i++ ) {
144 if( targets[i].makeP2Set().add( src ) ) {
145 addToWorklist( (VarNode) targets[i] );
146 ret = true;
147 }
148 }
149 return ret;
150 }
151
153 protected final boolean handleVarNode( final VarNode src ) {
154 boolean ret = false;
155
156 if( src.getReplacement() != src ) throw new RuntimeException  (
157 "Got bad node "+src+" with rep "+src.getReplacement() );
158
159 final PointsToSetInternal newP2Set = src.getP2Set().getNewSet();
160 if( newP2Set.isEmpty() ) return false;
161
162 if( ofcg != null ) {
163 QueueReader addedEdges = pag.edgeReader();
164 ofcg.updatedNode( src );
165 ofcg.build();
166
167 while(addedEdges.hasNext()) {
168 Node addedSrc = (Node) addedEdges.next();
169 Node addedTgt = (Node) addedEdges.next();
170 ret = true;
171 if( addedSrc instanceof VarNode ) {
172 if( addedTgt instanceof VarNode ) {
173 VarNode edgeSrc = (VarNode) addedSrc;
174 VarNode edgeTgt = (VarNode) addedTgt;
175 if( edgeTgt.makeP2Set().addAll( edgeSrc.getP2Set(), null ) )
176 addToWorklist( edgeTgt );
177 }
178 } else if( addedSrc instanceof AllocNode ) {
179 AllocNode edgeSrc = (AllocNode) addedSrc;
180 VarNode edgeTgt = (VarNode) addedTgt;
181 if( edgeTgt.makeP2Set().add( edgeSrc ) )
182 addToWorklist( edgeTgt );
183 }
184 FieldRefNode frn = null;
185 if( addedSrc instanceof FieldRefNode )
186 frn = (FieldRefNode) addedSrc;
187 if( addedTgt instanceof FieldRefNode )
188 frn = (FieldRefNode) addedTgt;
189 if( frn != null ) {
190 VarNode base = frn.getBase();
191 if( fieldToBase.put( frn.getField(), base ) ) {
192 aliasWorkList.add( base );
193 }
194 }
195 }
196 }
197
198 Node[] simpleTargets = pag.simpleLookup( src );
199 for( int i = 0; i < simpleTargets.length; i++ ) {
200 if( simpleTargets[i].makeP2Set().addAll( newP2Set, null ) ) {
201 addToWorklist( (VarNode) simpleTargets[i] );
202 ret = true;
203 }
204 }
205
206 Node[] storeTargets = pag.storeLookup( src );
207 for( int i = 0; i < storeTargets.length; i++ ) {
208 final FieldRefNode fr = (FieldRefNode) storeTargets[i];
209 if( fr.makeP2Set().addAll( newP2Set, null ) ) {
210 fieldRefWorkList.add( fr );
211 ret = true;
212 }
213 }
214
215 src.getP2Set().flushNew();
216 return ret;
217 }
218
219 protected final PointsToSetInternal makeP2Set( FieldRefNode n ) {
220 PointsToSetInternal ret = (PointsToSetInternal) loadSets.get(n);
221 if( ret == null ) {
222 ret = pag.getSetFactory().newSet( null, pag );
223 loadSets.put( n, ret );
224 }
225 return ret;
226 }
227
228 protected final PointsToSetInternal getP2Set( FieldRefNode n ) {
229 PointsToSetInternal ret = (PointsToSetInternal) loadSets.get(n);
230 if( ret == null ) {
231 return EmptyPointsToSet.v();
232 }
233 return ret;
234 }
235
236 private boolean addToWorklist( VarNode n ) {
237 if( n.getReplacement() != n ) throw new RuntimeException (
238 "Adding bad node "+n+" with rep "+n.getReplacement() );
239 return varNodeWorkList.add( n );
240 }
241
242 protected PAG pag;
243 protected MultiMap fieldToBase = new HashMultiMap();
244 protected MultiMap aliasEdges = new HashMultiMap();
245 protected LargeNumberedMap loadSets;
246 protected OnFlyCallGraph ofcg;
247 }
248
249
250
251 |
Popular Tags |
Java API By Example, From Geeks To Geeks.