KickJava   Java API By Example, From Geeks To Geeks.

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


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.internal.*;
24 import soot.*;
25 import java.util.*;
26 import soot.options.SparkOptions;
27
28 /** Collapses nodes that are members of simple trees (EBBs)
29  * in the pointer assignment graph.
30  * @author Ondrej Lhotak
31  */
32
33 public class EBBCollapser {
34     /** Actually collapse the EBBs in the PAG. */
35     public void collapse() {
36         boolean verbose = pag.getOpts().verbose();
37         if( verbose ) {
38             G.v().out.println( "Total VarNodes: "+pag.getVarNodeNumberer().size()+". Collapsing EBBs..." );
39         }
40         collapseAlloc();
41         collapseLoad();
42         collapseSimple();
43         if( verbose ) {
44             G.v().out.println( ""+numCollapsed+" nodes were collapsed." );
45         }
46     }
47     public EBBCollapser( PAG pag ) {
48         this.pag = pag;
49     }
50     
51     /* End of public methods. */
52     /* End of package methods. */
53
54     protected int numCollapsed = 0;
55     protected PAG pag;
56     protected void collapseAlloc() {
57         final boolean ofcg = (pag.getOnFlyCallGraph() != null);
58         for( Iterator nIt = pag.allocSources().iterator(); nIt.hasNext(); ) {
59             final AllocNode n = (AllocNode) nIt.next();
60             Node[] succs = pag.allocLookup( n );
61             VarNode firstSucc = null;
62             for( int i = 0; i < succs.length; i++ ) {
63                 VarNode succ = (VarNode) succs[i];
64                 if( pag.allocInvLookup( succ ).length > 1 ) continue;
65                 if( pag.loadInvLookup( succ ).length > 0 ) continue;
66                 if( pag.simpleInvLookup( succ ).length > 0 ) continue;
67                 if( ofcg && succ.isInterProcTarget() ) continue;
68                 if( firstSucc == null ) {
69                     firstSucc = succ;
70                 } else {
71                     if( firstSucc.getType().equals( succ.getType() ) ) {
72                         firstSucc.mergeWith( succ );
73                         numCollapsed++;
74                     }
75                 }
76             }
77         }
78     }
79     protected void collapseSimple() {
80         final boolean ofcg = (pag.getOnFlyCallGraph() != null);
81         final TypeManager typeManager = (TypeManager) pag.getTypeManager();
82         boolean change;
83         do {
84             change = false;
85             for( Iterator nIt = new ArrayList( pag.simpleSources() ).iterator(); nIt.hasNext(); ) {
86                 final VarNode n = (VarNode) nIt.next();
87                 Type nType = n.getType();
88                 Node[] succs = pag.simpleLookup( n );
89                 for( int i = 0; i < succs.length; i++ ) {
90                     VarNode succ = (VarNode) succs[i];
91                     Type sType = succ.getType();
92                     if( !typeManager.castNeverFails( nType, sType ) ) continue;
93                     if( pag.allocInvLookup( succ ).length > 0 ) continue;
94                     if( pag.loadInvLookup( succ ).length > 0 ) continue;
95                     if( pag.simpleInvLookup( succ ).length > 1 ) continue;
96                     if( ofcg
97                     && ( succ.isInterProcTarget() || n.isInterProcSource() ) ) continue;
98                     n.mergeWith( succ );
99                     change = true;
100                     numCollapsed++;
101                 }
102             }
103         } while( change );
104     }
105     protected void collapseLoad() {
106         final boolean ofcg = (pag.getOnFlyCallGraph() != null);
107         final TypeManager typeManager = (TypeManager) pag.getTypeManager();
108         for( Iterator nIt = new ArrayList( pag.loadSources() ).iterator(); nIt.hasNext(); ) {
109             final FieldRefNode n = (FieldRefNode) nIt.next();
110             Type nType = n.getType();
111             Node[] succs = pag.loadLookup( n );
112             Node firstSucc = null;
113             HashMap typeToSucc = new HashMap();
114             for( int i = 0; i < succs.length; i++ ) {
115                 VarNode succ = (VarNode) succs[i];
116                 Type sType = succ.getType();
117                 if( pag.allocInvLookup( succ ).length > 0 ) continue;
118                 if( pag.loadInvLookup( succ ).length > 1 ) continue;
119                 if( pag.simpleInvLookup( succ ).length > 0 ) continue;
120                 if( ofcg && succ.isInterProcTarget() ) continue;
121                 if( typeManager.castNeverFails( nType, sType ) ) {
122                     if( firstSucc == null ) {
123                         firstSucc = succ;
124                     } else {
125                         firstSucc.mergeWith( succ );
126                         numCollapsed++;
127                     }
128                 } else {
129                     VarNode rep = (VarNode) typeToSucc.get( succ.getType() );
130                     if( rep == null ) {
131                         typeToSucc.put( succ.getType(), succ );
132                     } else {
133                         rep.mergeWith( succ );
134                         numCollapsed++;
135                     }
136                 }
137             }
138         }
139     }
140 }
141
142
143
144
Popular Tags