|
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.queue.*;
27 import java.util.*;
28 import soot.options.SparkOptions;
29
30
33
34 public final class PropWorklist extends Propagator {
35 protected final Set varNodeWorkList = new TreeSet();
36
37 public PropWorklist( PAG pag ) { this.pag = pag; }
38
39 public final void propagate() {
40 ofcg = pag.getOnFlyCallGraph();
41 new TopoSorter( pag, false ).sort();
42 for( Iterator it = pag.allocSources().iterator(); it.hasNext(); ) {
43 handleAllocNode( (AllocNode) it.next() );
44 }
45
46 boolean verbose = pag.getOpts().verbose();
47 do {
48 if( verbose ) {
49 G.v().out.println( "Worklist has "+varNodeWorkList.size()+
50 " nodes." );
51 }
52 while( !varNodeWorkList.isEmpty() ) {
53 VarNode src = (VarNode) varNodeWorkList.iterator().next();
54 varNodeWorkList.remove( src );
55 handleVarNode( src );
56 }
57 if( verbose ) {
58 G.v().out.println( "Now handling field references" );
59 }
60 for( Iterator srcIt = pag.storeSources().iterator(); srcIt.hasNext(); ) {
61 final VarNode src = (VarNode) srcIt.next();
62 Node[] targets = pag.storeLookup( src );
63 for( int i = 0; i < targets.length; i++ ) {
64 final FieldRefNode target = (FieldRefNode) targets[i];
65 target.getBase().makeP2Set().forall( new P2SetVisitor() {
66 public final void visit( Node n ) {
67 AllocDotField nDotF = pag.makeAllocDotField(
68 (AllocNode) n, target.getField() );
69 nDotF.makeP2Set().addAll( src.getP2Set(), null );
70 }
71 } );
72 }
73 }
74 HashSet edgesToPropagate = new HashSet();
75 for( Iterator it = pag.loadSources().iterator(); it.hasNext(); ) {
76 handleFieldRefNode( (FieldRefNode) it.next(), edgesToPropagate );
77 }
78 HashSet nodesToFlush = new HashSet();
79 for( Iterator pairIt = edgesToPropagate.iterator(); pairIt.hasNext(); ) {
80 final Object  [] pair = (Object []) pairIt.next();
81 PointsToSetInternal nDotF = (PointsToSetInternal) pair[0];
82 PointsToSetInternal newP2Set = nDotF.getNewSet();
83 VarNode loadTarget = (VarNode) pair[1];
84 if( loadTarget.makeP2Set().addAll( newP2Set, null ) ) {
85 varNodeWorkList.add( loadTarget );
86 }
87 nodesToFlush.add( nDotF );
88 }
89 for( Iterator nDotFIt = nodesToFlush.iterator(); nDotFIt.hasNext(); ) {
90 final PointsToSetInternal nDotF = (PointsToSetInternal) nDotFIt.next();
91 nDotF.flushNew();
92 }
93 } while( !varNodeWorkList.isEmpty() );
94 }
95
96
97
98
99
101 protected final boolean handleAllocNode( AllocNode src ) {
102 boolean ret = false;
103 Node[] targets = pag.allocLookup( src );
104 for( int i = 0; i < targets.length; i++ ) {
105 if( targets[i].makeP2Set().add( src ) ) {
106 varNodeWorkList.add( (VarNode) targets[i] );
107 ret = true;
108 }
109 }
110 return ret;
111 }
112
114 protected final boolean handleVarNode( final VarNode src ) {
115 boolean ret = false;
116 boolean flush = true;
117
118 if( src.getReplacement() != src ) throw new RuntimeException (
119 "Got bad node "+src+" with rep "+src.getReplacement() );
120
121 final PointsToSetInternal newP2Set = src.getP2Set().getNewSet();
122 if( newP2Set.isEmpty() ) return false;
123
124 if( ofcg != null ) {
125 QueueReader addedEdges = pag.edgeReader();
126 ofcg.updatedNode( src );
127 ofcg.build();
128
129 while(addedEdges.hasNext()) {
130 Node addedSrc = (Node) addedEdges.next();
131 Node addedTgt = (Node) addedEdges.next();
132 ret = true;
133 if( addedSrc instanceof VarNode ) {
134 if( addedTgt instanceof VarNode ) {
135 VarNode edgeSrc = (VarNode) addedSrc.getReplacement();
136 VarNode edgeTgt = (VarNode) addedTgt.getReplacement();
137
138 if( edgeTgt.makeP2Set().addAll( edgeSrc.getP2Set(), null ) ) {
139 varNodeWorkList.add( edgeTgt );
140 if(edgeTgt == src) flush = false;
141 }
142 }
143 } else if( addedSrc instanceof AllocNode ) {
144 AllocNode edgeSrc = (AllocNode) addedSrc;
145 VarNode edgeTgt = (VarNode) addedTgt.getReplacement();
146 if( edgeTgt.makeP2Set().add( edgeSrc ) ) {
147 varNodeWorkList.add( edgeTgt );
148 if(edgeTgt == src) flush = false;
149 }
150 }
151 }
152 }
153
154 Node[] simpleTargets = pag.simpleLookup( src );
155 for( int i = 0; i < simpleTargets.length; i++ ) {
156 if( simpleTargets[i].makeP2Set().addAll( newP2Set, null ) ) {
157 varNodeWorkList.add( (VarNode) simpleTargets[i] );
158 if(simpleTargets[i] == src) flush = false;
159 ret = true;
160 }
161 }
162
163 Node[] storeTargets = pag.storeLookup( src );
164 for( int i = 0; i < storeTargets.length; i++ ) {
165 final FieldRefNode fr = (FieldRefNode) storeTargets[i];
166 final SparkField f = fr.getField();
167 ret = fr.getBase().getP2Set().forall( new P2SetVisitor() {
168 public final void visit( Node n ) {
169 AllocDotField nDotF = pag.makeAllocDotField(
170 (AllocNode) n, f );
171 if( nDotF.makeP2Set().addAll( newP2Set, null ) ) {
172 returnValue = true;
173 }
174 }
175 } ) | ret;
176 }
177
178 final HashSet storesToPropagate = new HashSet();
179 final HashSet loadsToPropagate = new HashSet();
180 Collection fieldRefs = src.getAllFieldRefs();
181 for( Iterator frIt = fieldRefs.iterator(); frIt.hasNext(); ) {
182 final FieldRefNode fr = (FieldRefNode) frIt.next();
183 final SparkField field = fr.getField();
184 final Node[] storeSources = pag.storeInvLookup( fr );
185 if( storeSources.length > 0 ) {
186 newP2Set.forall( new P2SetVisitor() {
187 public final void visit( Node n ) {
188 AllocDotField nDotF = pag.makeAllocDotField(
189 (AllocNode) n, field );
190 for( int i = 0; i < storeSources.length; i++ ) {
191 Node[] pair = { storeSources[i],
192 nDotF.getReplacement() };
193 storesToPropagate.add( pair );
194 }
195 }
196 } );
197 }
198
199 final Node[] loadTargets = pag.loadLookup( fr );
200 if( loadTargets.length > 0 ) {
201 newP2Set.forall( new P2SetVisitor() {
202 public final void visit( Node n ) {
203 AllocDotField nDotF = pag.findAllocDotField(
204 (AllocNode) n, field );
205 if( nDotF != null ) {
206 for( int i = 0; i < loadTargets.length; i++ ) {
207 Node[] pair = { nDotF.getReplacement(),
208 loadTargets[i] };
209 loadsToPropagate.add( pair );
210 }
211 }
212 }
213 } );
214 }
215 }
216 if(flush) src.getP2Set().flushNew();
217 for( Iterator pIt = storesToPropagate.iterator(); pIt.hasNext(); ) {
218 final Node[] p = (Node[]) pIt.next();
219 VarNode storeSource = (VarNode) p[0];
220 AllocDotField nDotF = (AllocDotField) p[1];
221 if( nDotF.makeP2Set().addAll( storeSource.getP2Set(), null ) ) {
222 ret = true;
223 }
224 }
225 for( Iterator pIt = loadsToPropagate.iterator(); pIt.hasNext(); ) {
226 final Node[] p = (Node[]) pIt.next();
227 AllocDotField nDotF = (AllocDotField) p[0];
228 VarNode loadTarget = (VarNode) p[1];
229 if( loadTarget.makeP2Set().
230 addAll( nDotF.getP2Set(), null ) ) {
231 varNodeWorkList.add( loadTarget );
232 ret = true;
233 }
234 }
235 return ret;
236 }
237
238
240 protected final void handleFieldRefNode( FieldRefNode src,
241 final HashSet edgesToPropagate ) {
242 final Node[] loadTargets = pag.loadLookup( src );
243 if( loadTargets.length == 0 ) return;
244 final SparkField field = src.getField();
245
246 src.getBase().getP2Set().forall( new P2SetVisitor() {
247
248 public final void visit( Node n ) {
249 AllocDotField nDotF = pag.findAllocDotField(
250 (AllocNode) n, field );
251 if( nDotF != null ) {
252 PointsToSetInternal p2Set = nDotF.getP2Set();
253 if( !p2Set.getNewSet().isEmpty() ) {
254 for( int i = 0; i < loadTargets.length; i++ ) {
255 Object [] pair = { p2Set, loadTargets[i] };
256 edgesToPropagate.add( pair );
257 }
258 }
259 }
260 }
261 } );
262 }
263
264 protected PAG pag;
265 protected OnFlyCallGraph ofcg;
266 }
267
268
269
270 |
Popular Tags |
Java API By Example, From Geeks To Geeks.