KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > jimple > spark > SparkTransformer


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 2002 Ondrej 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.jimple.spark;
21 import soot.*;
22 import soot.jimple.spark.builder.*;
23 import soot.jimple.spark.pag.*;
24 import soot.jimple.spark.solver.*;
25 import soot.jimple.spark.sets.*;
26 import soot.jimple.toolkits.callgraph.*;
27 import soot.jimple.*;
28 import java.util.*;
29 import soot.util.*;
30 import soot.options.SparkOptions;
31 import soot.options.Options;
32 import soot.tagkit.*;
33
34 /** Main entry point for Spark.
35  * @author Ondrej Lhotak
36  */
37 public class SparkTransformer extends SceneTransformer
38 {
39     public SparkTransformer( Singletons.Global g ) {}
40     public static SparkTransformer v() { return G.v().soot_jimple_spark_SparkTransformer(); }
41
42     protected void internalTransform( String JavaDoc phaseName, Map options )
43     {
44         SparkOptions opts = new SparkOptions( options );
45         final String JavaDoc output_dir = SourceLocator.v().getOutputDir();
46
47         // Build pointer assignment graph
48 ContextInsensitiveBuilder b = new ContextInsensitiveBuilder();
49         if( opts.pre_jimplify() ) b.preJimplify();
50         if( opts.force_gc() ) doGC();
51         Date startBuild = new Date();
52         final PAG pag = (PAG) b.setup( opts );
53         b.build();
54         Date endBuild = new Date();
55         reportTime( "Pointer Assignment Graph", startBuild, endBuild );
56         if( opts.force_gc() ) doGC();
57
58         // Build type masks
59 Date startTM = new Date();
60         pag.getTypeManager().makeTypeMask();
61         Date endTM = new Date();
62         reportTime( "Type masks", startTM, endTM );
63         if( opts.force_gc() ) doGC();
64
65         if( opts.verbose() ) {
66             G.v().out.println( "VarNodes: "+pag.getVarNodeNumberer().size() );
67             G.v().out.println( "FieldRefNodes: "+pag.getFieldRefNodeNumberer().size() );
68             G.v().out.println( "AllocNodes: "+pag.getAllocNodeNumberer().size() );
69         }
70
71         // Simplify pag
72 Date startSimplify = new Date();
73
74         // We only simplify if on_fly_cg is false. But, if vta is true, it
75 // overrides on_fly_cg, so we can still simplify. Something to handle
76 // these option interdependencies more cleanly would be nice...
77 if( ( opts.simplify_sccs() && !opts.on_fly_cg() ) || opts.vta() ) {
78                 new SCCCollapser( pag, opts.ignore_types_for_sccs() ).collapse();
79         }
80         if( opts.simplify_offline() && !opts.on_fly_cg() ) {
81             new EBBCollapser( pag ).collapse();
82         }
83         if( true || opts.simplify_sccs() || opts.vta() || opts.simplify_offline() ) {
84             pag.cleanUpMerges();
85         }
86         Date endSimplify = new Date();
87         reportTime( "Pointer Graph simplified", startSimplify, endSimplify );
88         if( opts.force_gc() ) doGC();
89
90         // Dump pag
91 PAGDumper dumper = null;
92         if( opts.dump_pag() || opts.dump_solution() ) {
93             dumper = new PAGDumper( pag, output_dir );
94         }
95         if( opts.dump_pag() ) dumper.dump();
96
97         // Propagate
98 Date startProp = new Date();
99         final Propagator[] propagator = new Propagator[1];
100         switch( opts.propagator() ) {
101             case SparkOptions.propagator_iter:
102                 propagator[0] = new PropIter( pag );
103                 break;
104             case SparkOptions.propagator_worklist:
105                 propagator[0] = new PropWorklist( pag );
106                 break;
107             case SparkOptions.propagator_cycle:
108                 propagator[0] = new PropCycle( pag );
109                 break;
110             case SparkOptions.propagator_merge:
111                 propagator[0] = new PropMerge( pag );
112                 break;
113             case SparkOptions.propagator_alias:
114                 propagator[0] = new PropAlias( pag );
115                 break;
116             case SparkOptions.propagator_none:
117                 break;
118             default:
119                 throw new RuntimeException JavaDoc();
120         }
121         if( propagator[0] != null ) propagator[0].propagate();
122         Date endProp = new Date();
123         reportTime( "Propagation", startProp, endProp );
124         reportTime( "Solution found", startSimplify, endProp );
125         if( opts.force_gc() ) doGC();
126         
127         if( !opts.on_fly_cg() || opts.vta() ) {
128             CallGraphBuilder cgb = new CallGraphBuilder( pag );
129             cgb.build();
130         }
131
132         if( opts.verbose() ) {
133             G.v().out.println( "[Spark] Number of reachable methods: "
134                     +Scene.v().getReachableMethods().size() );
135         }
136
137         if( opts.set_mass() ) findSetMass( pag );
138
139         /*
140         if( propagator[0] instanceof PropMerge ) {
141             new MergeChecker( pag ).check();
142         } else if( propagator[0] != null ) {
143             new Checker( pag ).check();
144         }
145         */
146
147         if( opts.dump_answer() ) new ReachingTypeDumper( pag, output_dir ).dump();
148         if( opts.dump_solution() ) dumper.dumpPointsToSets();
149         if( opts.dump_html() ) new PAG2HTML( pag, output_dir ).dump();
150         Scene.v().setPointsToAnalysis( pag );
151         if( opts.add_tags() ) {
152             addTags( pag );
153         }
154     }
155     protected void addTags( PAG pag ) {
156         final Tag unknown = new StringTag( "Untagged Spark node" );
157         final Map nodeToTag = pag.getNodeTags();
158         for( Iterator cIt = Scene.v().getClasses().iterator(); cIt.hasNext(); ) {
159             final SootClass c = (SootClass) cIt.next();
160             for( Iterator mIt = c.methodIterator(); mIt.hasNext(); ) {
161                 SootMethod m = (SootMethod) mIt.next();
162                 if( !m.isConcrete() ) continue;
163                 if( !m.hasActiveBody() ) continue;
164                 for( Iterator sIt = m.getActiveBody().getUnits().iterator(); sIt.hasNext(); ) {
165                     final Stmt s = (Stmt) sIt.next();
166                     if( s instanceof DefinitionStmt ) {
167                         Value lhs = ((DefinitionStmt) s).getLeftOp();
168                         VarNode v = null;
169                         if( lhs instanceof Local ) {
170                             v = pag.findLocalVarNode( (Local) lhs );
171                         } else if( lhs instanceof FieldRef ) {
172                             v = pag.findGlobalVarNode( ((FieldRef) lhs).getField() );
173                         }
174                         if( v != null ) {
175                             PointsToSetInternal p2set = v.getP2Set();
176                             p2set.forall( new P2SetVisitor() {
177                             public final void visit( Node n ) {
178                                 addTag( s, n, nodeToTag, unknown );
179                             }} );
180                             Node[] simpleSources = pag.simpleInvLookup(v);
181                             for( int i=0; i < simpleSources.length; i++ ) {
182                                 addTag( s, simpleSources[i], nodeToTag, unknown );
183                             }
184                             simpleSources = pag.allocInvLookup(v);
185                             for( int i=0; i < simpleSources.length; i++ ) {
186                                 addTag( s, simpleSources[i], nodeToTag, unknown );
187                             }
188                             simpleSources = pag.loadInvLookup(v);
189                             for( int i=0; i < simpleSources.length; i++ ) {
190                                 addTag( s, simpleSources[i], nodeToTag, unknown );
191                             }
192                         }
193                     }
194                 }
195             }
196         }
197     }
198     protected static void reportTime( String JavaDoc desc, Date start, Date end ) {
199         long time = end.getTime()-start.getTime();
200         G.v().out.println( "[Spark] "+desc+" in "+time/1000+"."+(time/100)%10+" seconds." );
201     }
202     protected static void doGC() {
203         // Do 5 times because the garbage collector doesn't seem to always collect
204 // everything on the first try.
205 System.gc();
206         System.gc();
207         System.gc();
208         System.gc();
209         System.gc();
210     }
211
212     protected void addTag( Host h, Node n, Map nodeToTag, Tag unknown ) {
213         if( nodeToTag.containsKey( n ) ) h.addTag( (Tag) nodeToTag.get(n) );
214         else h.addTag( unknown );
215     }
216
217     protected void findSetMass( PAG pag ) {
218         int mass = 0;
219         int varMass = 0;
220         int adfs = 0;
221         int scalars = 0;
222         if( false ) {
223             for( Iterator it = Scene.v().getReachableMethods().listener(); it.hasNext(); ) {
224                 SootMethod m = (SootMethod) it.next();
225                 G.v().out.println( m.getBytecodeSignature() );
226             }
227         }
228
229
230         for( Iterator vIt = pag.getVarNodeNumberer().iterator(); vIt.hasNext(); ) {
231
232
233             final VarNode v = (VarNode) vIt.next();
234                 scalars++;
235             PointsToSetInternal set = v.getP2Set();
236             if( set != null ) mass += set.size();
237             if( set != null ) varMass += set.size();
238             if( set != null && set.size() > 0 ) {
239                 //G.v().out.println( "V "+v.getVariable()+" "+set.size() );
240 // G.v().out.println( ""+v.getVariable()+" "+v.getMethod()+" "+set.size() );
241 }
242         }
243         for( Iterator anIt = pag.allocSourcesIterator(); anIt.hasNext(); ) {
244             final AllocNode an = (AllocNode) anIt.next();
245             for( Iterator adfIt = an.getFields().iterator(); adfIt.hasNext(); ) {
246                 final AllocDotField adf = (AllocDotField) adfIt.next();
247                 PointsToSetInternal set = adf.getP2Set();
248                 if( set != null ) mass += set.size();
249                 if( set != null && set.size() > 0 ) {
250                     adfs++;
251             // G.v().out.println( ""+adf.getBase().getNewExpr()+"."+adf.getField()+" "+set.size() );
252 }
253             }
254         }
255         G.v().out.println( "Set mass: " + mass );
256         G.v().out.println( "Variable mass: " + varMass );
257         G.v().out.println( "Scalars: "+scalars );
258         G.v().out.println( "adfs: "+adfs );
259         // Compute points-to set sizes of dereference sites BEFORE
260 // trimming sets by declared type
261 int[] deRefCounts = new int[30001];
262         for( Iterator vIt = pag.getDereferences().iterator(); vIt.hasNext(); ) {
263             final VarNode v = (VarNode) vIt.next();
264             PointsToSetInternal set = v.getP2Set();
265             int size = 0;
266             if( set != null ) size = set.size();
267             deRefCounts[size]++;
268         }
269         int total = 0;
270         for( int i=0; i < deRefCounts.length; i++ ) total+= deRefCounts[i];
271         G.v().out.println( "Dereference counts BEFORE trimming (total = "+total+"):" );
272         for( int i=0; i < deRefCounts.length; i++ ) {
273             if( deRefCounts[i] > 0 ) {
274                 G.v().out.println( ""+i+" "+deRefCounts[i]+" "+(deRefCounts[i]*100.0/total)+"%" );
275             }
276         }
277         // Compute points-to set sizes of dereference sites AFTER
278 // trimming sets by declared type
279 /*
280         if( pag.getTypeManager().getFastHierarchy() == null ) {
281             pag.getTypeManager().clearTypeMask();
282             pag.getTypeManager().setFastHierarchy( Scene.v().getOrMakeFastHierarchy() );
283             pag.getTypeManager().makeTypeMask( pag );
284             deRefCounts = new int[30001];
285             for( Iterator vIt = pag.getDereferences().iterator(); vIt.hasNext(); ) {
286                 final VarNode v = (VarNode) vIt.next();
287                 PointsToSetInternal set =
288                     pag.getSetFactory().newSet( v.getType(), pag );
289                 int size = 0;
290                 if( set != null ) {
291                     v.getP2Set().setType( null );
292                     v.getP2Set().getNewSet().setType( null );
293                     v.getP2Set().getOldSet().setType( null );
294                     set.addAll( v.getP2Set(), null );
295                     size = set.size();
296                 }
297                 deRefCounts[size]++;
298             }
299             total = 0;
300             for( int i=0; i < deRefCounts.length; i++ ) total+= deRefCounts[i];
301             G.v().out.println( "Dereference counts AFTER trimming (total = "+total+"):" );
302             for( int i=0; i < deRefCounts.length; i++ ) {
303                 if( deRefCounts[i] > 0 ) {
304                     G.v().out.println( ""+i+" "+deRefCounts[i]+" "+(deRefCounts[i]*100.0/total)+"%" );
305                 }
306             }
307         }
308         */
309         /*
310         deRefCounts = new int[30001];
311         for( Iterator siteIt = ig.getAllSites().iterator(); siteIt.hasNext(); ) {
312             final Stmt site = (Stmt) siteIt.next();
313             SootMethod method = ig.getDeclaringMethod( site );
314             Value ie = site.getInvokeExpr();
315             if( !(ie instanceof VirtualInvokeExpr)
316                     && !(ie instanceof InterfaceInvokeExpr) ) continue;
317             InstanceInvokeExpr expr = (InstanceInvokeExpr) site.getInvokeExpr();
318             Local receiver = (Local) expr.getBase();
319             Collection types = pag.reachingObjects( method, site, receiver )
320                 .possibleTypes();
321             Type receiverType = receiver.getType();
322             if( receiverType instanceof ArrayType ) {
323                 receiverType = RefType.v( "java.lang.Object" );
324             }
325             Collection targets =
326                 Scene.v().getOrMakeFastHierarchy().resolveConcreteDispatchWithoutFailing(
327                         types, expr.getMethod(), (RefType) receiverType );
328             deRefCounts[targets.size()]++;
329         }
330         total = 0;
331         for( int i=0; i < deRefCounts.length; i++ ) total+= deRefCounts[i];
332         G.v().out.println( "Virtual invoke target counts (total = "+total+"):" );
333         for( int i=0; i < deRefCounts.length; i++ ) {
334             if( deRefCounts[i] > 0 ) {
335                 G.v().out.println( ""+i+" "+deRefCounts[i]+" "+(deRefCounts[i]*100.0/total)+"%" );
336             }
337         }
338         */
339     }
340 }
341
342
343
Popular Tags