KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > jimple > spark > solver > PropCycle


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 2003 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.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 import soot.util.*;
30
31 /** Propagates points-to sets using an on-line cycle detection algorithm
32  * based on Heintze and Tardieu, PLDI 2000.
33  * @author Ondrej Lhotak
34  */

35
36 public final class PropCycle extends Propagator {
37     public PropCycle( PAG pag ) {
38         this.pag = pag;
39         typeManager = (TypeManager) pag.getTypeManager();
40         varNodeToIteration = new LargeNumberedMap( pag.getVarNodeNumberer() );
41     }
42
43     /** Actually does the propagation. */
44     public final void propagate() {
45         ofcg = pag.getOnFlyCallGraph();
46         boolean verbose = pag.getOpts().verbose();
47         Collection bases = new HashSet();
48         for( Iterator frnIt = pag.getFieldRefNodeNumberer().iterator(); frnIt.hasNext(); ) {
49             final FieldRefNode frn = (FieldRefNode) frnIt.next();
50             bases.add( frn.getBase() );
51         }
52         bases = new ArrayList( bases );
53         int iteration = 0;
54         boolean changed;
55         boolean finalIter = false;
56     do {
57             changed = false;
58             iteration++;
59             currentIteration = new Integer JavaDoc( iteration );
60             if( verbose ) G.v().out.println( "Iteration: "+iteration );
61             for( Iterator vIt = bases.iterator(); vIt.hasNext(); ) {
62                 final VarNode v = (VarNode) vIt.next();
63                 changed = computeP2Set( (VarNode) v.getReplacement(), new ArrayList() ) | changed;
64             }
65             if( ofcg != null ) throw new RuntimeException JavaDoc( "NYI" );
66             if( verbose ) G.v().out.println( "Processing stores" );
67             for( Iterator srcIt = pag.storeSources().iterator(); srcIt.hasNext(); ) {
68                 final VarNode src = (VarNode) srcIt.next();
69                 Node[] targets = pag.storeLookup( src );
70                 for( int i = 0; i < targets.length; i++ ) {
71                     final FieldRefNode target = (FieldRefNode) targets[i];
72                     changed = target.getBase().makeP2Set().forall( new P2SetVisitor() {
73                     public final void visit( Node n ) {
74                             AllocDotField nDotF = pag.makeAllocDotField(
75                                 (AllocNode) n, target.getField() );
76                             nDotF.makeP2Set().addAll( src.getP2Set(), null );
77                         }
78                     } ) | changed;
79                 }
80             }
81             if( !changed && !finalIter ) {
82                 finalIter = true;
83                 if( verbose ) G.v().out.println( "Doing full graph" );
84                 bases = new ArrayList(pag.getVarNodeNumberer().size());
85                 for( Iterator vIt = pag.getVarNodeNumberer().iterator(); vIt.hasNext(); ) {
86                     final VarNode v = (VarNode) vIt.next();
87                     bases.add( v );
88                 }
89                 changed = true;
90             }
91     } while( changed );
92     }
93
94
95     /* End of public methods. */
96     /* End of package methods. */
97
98     private boolean computeP2Set( final VarNode v, ArrayList path ) {
99         boolean ret = false;
100
101         if( path.contains( v ) ) {
102             for( Iterator nIt = path.iterator(); nIt.hasNext(); ) {
103                 final Node n = (Node) nIt.next();
104         // if( n != v ) n.mergeWith( v );
105
}
106             return false;
107         }
108
109         if( currentIteration == varNodeToIteration.get(v) ) return false;
110         varNodeToIteration.put(v, currentIteration);
111
112         path.add( v );
113         if( v.getP2Set().isEmpty() ) {
114             Node[] srcs = pag.allocInvLookup( v );
115             for( int i = 0; i < srcs.length; i++ ) {
116                 ret = v.makeP2Set().add( srcs[i] ) | ret;
117             }
118         }
119         {
120             Node[] srcs = pag.simpleInvLookup( v );
121             for( int i = 0; i < srcs.length; i++ ) {
122                 VarNode src = (VarNode) srcs[i];
123                 ret = computeP2Set( src, path ) | ret;
124                 ret = v.makeP2Set().addAll( src.getP2Set(), null ) | ret;
125             }
126         }
127         {
128             Node[] srcs = pag.loadInvLookup( v );
129             for( int i = 0; i < srcs.length; i++ ) {
130                 final FieldRefNode src = (FieldRefNode) srcs[i];
131                 ret = src.getBase().getP2Set().forall( new P2SetVisitor() {
132                 public final void visit( Node n ) {
133                     AllocNode an = (AllocNode) n;
134                     AllocDotField adf =
135                         pag.makeAllocDotField( an, src.getField() );
136                     returnValue = v.makeP2Set().addAll( adf.getP2Set(), null ) | returnValue;
137                 }} ) | ret;
138             }
139         }
140         path.remove(path.size()-1);
141         return ret;
142     }
143
144     private PAG pag;
145     private OnFlyCallGraph ofcg;
146     private Integer JavaDoc currentIteration;
147     private LargeNumberedMap varNodeToIteration;
148     private TypeManager typeManager;
149 }
150
151
152
153
Popular Tags