KickJava   Java API By Example, From Geeks To Geeks.

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


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.*;
24 import java.util.*;
25 import soot.jimple.spark.sets.PointsToSetInternal;
26 import soot.jimple.spark.internal.*;
27 import soot.options.SparkOptions;
28
29 /** Collapses VarNodes (green) forming strongly-connected components in
30  * the pointer assignment graph.
31  * @author Ondrej Lhotak
32  */
33
34 public class SCCCollapser {
35     /** Actually collapse the SCCs in the PAG. */
36     public void collapse() {
37         boolean verbose = pag.getOpts().verbose();
38         if( verbose ) {
39             G.v().out.println( "Total VarNodes: "+pag.getVarNodeNumberer().size()+". Collapsing SCCs..." );
40         }
41
42         new TopoSorter( pag, ignoreTypes ).sort();
43         TreeSet s = new TreeSet();
44         for( Iterator vIt = pag.getVarNodeNumberer().iterator(); vIt.hasNext(); ) {
45             final VarNode v = (VarNode) vIt.next();
46             s.add(v);
47         }
48         for( Iterator vIt = s.iterator(); vIt.hasNext(); ) {
49             final VarNode v = (VarNode) vIt.next();
50             dfsVisit( v, v );
51         }
52
53         if( verbose ) {
54             G.v().out.println( ""+numCollapsed+" nodes were collapsed." );
55         }
56         visited = null;
57     }
58     public SCCCollapser( PAG pag, boolean ignoreTypes ) {
59         this.pag = pag;
60         this.ignoreTypes = ignoreTypes;
61         this.typeManager = (TypeManager) pag.getTypeManager();
62     }
63     
64     /* End of public methods. */
65     /* End of package methods. */
66
67     protected int numCollapsed = 0;
68     protected PAG pag;
69     protected HashSet visited = new HashSet();
70     protected boolean ignoreTypes;
71     protected TypeManager typeManager;
72
73     final protected void dfsVisit( VarNode v, VarNode rootOfSCC ) {
74         if( visited.contains( v ) ) return;
75         visited.add( v );
76         Node[] succs = pag.simpleInvLookup( v );
77         for( int i = 0; i < succs.length; i++ ) {
78             if( ignoreTypes
79             || typeManager.castNeverFails( succs[i].getType(), v.getType() ) ) {
80                 dfsVisit( (VarNode) succs[i], rootOfSCC );
81             }
82         }
83         if( v != rootOfSCC ) {
84             if( !ignoreTypes ) {
85                 if( typeManager.castNeverFails(
86                             v.getType(), rootOfSCC.getType() )
87                  && typeManager.castNeverFails(
88                             rootOfSCC.getType(), v.getType() ) ) {
89                     rootOfSCC.mergeWith( v );
90                     numCollapsed++;
91                 }
92             } else /* ignoreTypes */ {
93                 if( typeManager.castNeverFails(
94                             v.getType(), rootOfSCC.getType() ) ) {
95                     rootOfSCC.mergeWith( v );
96                 } else if( typeManager.castNeverFails(
97                             rootOfSCC.getType(), v.getType() ) ) {
98                     v.mergeWith( rootOfSCC );
99                 } else {
100                     rootOfSCC.getReplacement().setType( null );
101                     PointsToSetInternal set = rootOfSCC.getP2Set();
102                     if( set != null ) {
103                         set.setType( null );
104                     }
105                     rootOfSCC.mergeWith( v );
106                 }
107                 numCollapsed++;
108             }
109         }
110     }
111 }
112
113
114
115
Popular Tags