KickJava   Java API By Example, From Geeks To Geeks.

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


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.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 java.util.*;
27 import soot.options.SparkOptions;
28
29 /** Propagates points-to sets along pointer assignment graph using a merging
30  * of field reference (Red) nodes to improve scalability.
31  * @author Ondrej Lhotak
32  */
33
34 public final class PropMerge extends Propagator {
35     protected final Set varNodeWorkList = new TreeSet();
36
37     public PropMerge( PAG pag ) { this.pag = pag; }
38     /** Actually does the propagation. */
39     public final void propagate() {
40         new TopoSorter( pag, false ).sort();
41     for( Iterator it = pag.allocSources().iterator(); it.hasNext(); ) {
42         handleAllocNode( (AllocNode) it.next() );
43     }
44
45         boolean verbose = pag.getOpts().verbose();
46     do {
47             if( verbose ) {
48                 G.v().out.println( "Worklist has "+varNodeWorkList.size()+
49                         " nodes." );
50             }
51             int iter = 0;
52             while( !varNodeWorkList.isEmpty() ) {
53                 VarNode src = (VarNode) varNodeWorkList.iterator().next();
54                 varNodeWorkList.remove( src );
55         handleVarNode( src );
56                 if( verbose ) {
57                     iter++;
58                     if( iter >= 1000 ) {
59                         iter = 0;
60                         G.v().out.println( "Worklist has "+varNodeWorkList.size()+
61                                 " nodes." );
62                     }
63                 }
64             }
65             if( verbose ) {
66                 G.v().out.println( "Now handling field references" );
67             }
68             for( Iterator srcIt = pag.storeSources().iterator(); srcIt.hasNext(); ) {
69                 final VarNode src = (VarNode) srcIt.next();
70                 Node[] storeTargets = pag.storeLookup( src );
71                 for( int i = 0; i < storeTargets.length; i++ ) {
72                     final FieldRefNode fr = (FieldRefNode) storeTargets[i];
73                     fr.makeP2Set().addAll( src.getP2Set(), null );
74                 }
75             }
76             for( Iterator srcIt = pag.loadSources().iterator(); srcIt.hasNext(); ) {
77                 final FieldRefNode src = (FieldRefNode) srcIt.next();
78                 if( src != src.getReplacement() ) {
79                     throw new RuntimeException JavaDoc( "shouldn't happen" );
80                 }
81                 Node[] targets = pag.loadLookup( src );
82                 for( int i = 0; i < targets.length; i++ ) {
83                     VarNode target = (VarNode) targets[i];
84                     if( target.makeP2Set().addAll(
85                                 src.getP2Set(), null ) ) {
86                         varNodeWorkList.add( target );
87                     }
88                 }
89             }
90     } while( !varNodeWorkList.isEmpty() );
91     }
92
93     /* End of public methods. */
94     /* End of package methods. */
95
96     /** Propagates new points-to information of node src to all its
97      * successors. */
98     protected final boolean handleAllocNode( AllocNode src ) {
99     boolean ret = false;
100     Node[] targets = pag.allocLookup( src );
101     for( int i = 0; i < targets.length; i++ ) {
102         if( targets[i].makeP2Set().add( src ) ) {
103                 varNodeWorkList.add( targets[i] );
104                 ret = true;
105             }
106     }
107     return ret;
108     }
109     /** Propagates new points-to information of node src to all its
110      * successors. */
111     protected final boolean handleVarNode( final VarNode src ) {
112     boolean ret = false;
113
114         if( src.getReplacement() != src ) return ret;
115             /*
116             throw new RuntimeException(
117                 "Got bad node "+src+" with rep "+src.getReplacement() );
118                 */
119
120     final PointsToSetInternal newP2Set = src.getP2Set();
121     if( newP2Set.isEmpty() ) return false;
122
123     Node[] simpleTargets = pag.simpleLookup( src );
124     for( int i = 0; i < simpleTargets.length; i++ ) {
125         if( simpleTargets[i].makeP2Set().addAll( newP2Set, null ) ) {
126                 varNodeWorkList.add( simpleTargets[i] );
127                 ret = true;
128             }
129     }
130
131         Node[] storeTargets = pag.storeLookup( src );
132         for( int i = 0; i < storeTargets.length; i++ ) {
133             final FieldRefNode fr = (FieldRefNode) storeTargets[i];
134             if( fr.makeP2Set().addAll( newP2Set, null ) ) {
135                 ret = true;
136             }
137         }
138
139         for( Iterator frIt = src.getAllFieldRefs().iterator(); frIt.hasNext(); ) {
140
141             final FieldRefNode fr = (FieldRefNode) frIt.next();
142             final SparkField field = fr.getField();
143             ret = newP2Set.forall( new P2SetVisitor() {
144             public final void visit( Node n ) {
145                 AllocDotField nDotF = pag.makeAllocDotField(
146                     (AllocNode) n, field );
147                 Node nDotFNode = nDotF.getReplacement();
148                 if( nDotFNode != fr ) {
149                     fr.mergeWith( nDotFNode );
150                     returnValue = true;
151                 }
152             }} ) | ret;
153         }
154     //src.getP2Set().flushNew();
155 return ret;
156     }
157
158     protected PAG pag;
159 }
160
161
162
163
Popular Tags