KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > jimple > toolkits > pointer > CastCheckEliminator


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 2003, 2004 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.toolkits.pointer;
21 import java.util.*;
22 import soot.toolkits.scalar.*;
23 import soot.toolkits.graph.*;
24 import soot.*;
25 import soot.util.*;
26 import soot.jimple.*;
27
28 /** A flow analysis that detects redundant cast checks. */
29 public class CastCheckEliminator extends ForwardBranchedFlowAnalysis {
30     Map unitToKill = new HashMap();
31     Map unitToGenFallThrough = new HashMap();
32     Map unitToGenBranch = new HashMap();
33     LocalTypeSet emptySet;
34
35     public CastCheckEliminator(BriefUnitGraph cfg) {
36         super(cfg);
37         makeInitialSet();
38         doAnalysis();
39         tagCasts();
40     }
41
42     /** Put the results of the analysis into tags in cast statements. */
43     protected void tagCasts() {
44         for( Iterator sIt = ((UnitGraph)graph).getBody().getUnits().iterator(); sIt.hasNext(); ) {
45             final Stmt s = (Stmt) sIt.next();
46             if( s instanceof AssignStmt ) {
47                 AssignStmt as = (AssignStmt) s;
48                 Value rhs = as.getRightOp();
49                 if( rhs instanceof CastExpr ) {
50                     CastExpr cast = (CastExpr) rhs;
51                     Type t = cast.getCastType();
52                     if( t instanceof RefType ) {
53                         if( cast.getOp() instanceof Local ) {
54                             Local l = (Local) cast.getOp();
55                             LocalTypeSet set = (LocalTypeSet) unitToBeforeFlow.get(s);
56                             s.addTag( new CastCheckTag( set.get( set.indexOf(
57                                     l, (RefType) t ) ) ) );
58                         } else {
59                             NullConstant nc = (NullConstant) cast.getOp();
60                             s.addTag( new CastCheckTag( true ) );
61                         }
62                     }
63                 }
64             }
65         }
66     }
67
68     /** Find all the locals of reference type and all the types used in casts
69      * to initialize the mapping from locals and types to bits in the bit vector
70      * in LocalTypeSet. */
71     protected void makeInitialSet() {
72         // Find all locals of reference type
73 Chain locals = ((UnitGraph)graph).getBody().getLocals();
74         List refLocals = new ArrayList();
75         for( Iterator lIt = locals.iterator(); lIt.hasNext(); ) {
76             final Local l = (Local) lIt.next();
77             if( l.getType() instanceof RefType ) {
78                 refLocals.add( l );
79             }
80         }
81
82         // Find types of all casts
83 List types = new ArrayList();
84         for( Iterator sIt = ((UnitGraph)graph).getBody().getUnits().iterator(); sIt.hasNext(); ) {
85             final Stmt s = (Stmt) sIt.next();
86             if( s instanceof AssignStmt ) {
87                 AssignStmt as = (AssignStmt) s;
88                 Value rhs = as.getRightOp();
89                 if( rhs instanceof CastExpr ) {
90                     Type t = ( (CastExpr) rhs ).getCastType();
91                     if( t instanceof RefType && !types.contains( t ) ) {
92                         types.add( t );
93                     }
94                 }
95             }
96         }
97         
98         emptySet = new LocalTypeSet( refLocals, types );
99     }
100     
101
102     /** Returns a new, aggressive (local,type) set. */
103     protected Object JavaDoc newInitialFlow() {
104         LocalTypeSet ret = (LocalTypeSet) emptySet.clone();
105         ret.setAllBits();
106         return ret;
107     }
108
109     /** This is the flow function as described in the assignment write-up. */
110     protected void flowThrough( Object JavaDoc inValue, Unit unit, List outFallValues,
111                                 List outBranchValues )
112     {
113         final LocalTypeSet in = (LocalTypeSet) inValue;
114         final LocalTypeSet out = (LocalTypeSet) in.clone();
115         LocalTypeSet outBranch = out; // aliased to out unless unit is IfStmt
116 final Stmt stmt = (Stmt) unit;
117         
118         // First kill all locals defined in this statement
119 for( Iterator bIt = stmt.getDefBoxes().iterator(); bIt.hasNext(); ) {
120             final ValueBox b = (ValueBox) bIt.next();
121             Value v = b.getValue();
122             if( v instanceof Local && v.getType() instanceof RefType ) {
123                 out.killLocal( (Local) v );
124             }
125         }
126         
127         // An AssignStmt may be a new, a simple copy, or a cast
128 if( stmt instanceof AssignStmt ) {
129             AssignStmt astmt = (AssignStmt) stmt;
130             Value rhs = astmt.getRightOp();
131             Value lhs = astmt.getLeftOp();
132             if( lhs instanceof Local && rhs.getType() instanceof RefType ) {
133                 Local l = (Local) lhs;
134                 if( rhs instanceof NewExpr ) {
135                     out.localMustBeSubtypeOf( l, (RefType) rhs.getType() );
136                 } else if( rhs instanceof CastExpr ) {
137                     CastExpr cast = (CastExpr) rhs;
138                     Type castType = cast.getCastType();
139                     if( castType instanceof RefType
140                     && cast.getOp() instanceof Local ) {
141                         RefType refType = (RefType) castType;
142                         Local opLocal = (Local) cast.getOp();
143                         out.localCopy( l, opLocal );
144                         out.localMustBeSubtypeOf( l, refType );
145                         out.localMustBeSubtypeOf( opLocal, refType );
146                     }
147                 } else if( rhs instanceof Local ) {
148                     out.localCopy( l, (Local) rhs );
149                 }
150             }
151             
152             // Handle if statements
153 } else if( stmt instanceof IfStmt ) {
154             IfStmt ifstmt = (IfStmt) stmt;
155             
156             // This do ... while(false) is here so I can break out of it rather
157 // than having to have seven nested if statements. Silly people who
158 // took goto's out of the language... <grumble> <grumble>
159 do {
160                 if( graph.getPredsOf( stmt ).size() != 1 ) break;
161                 Object JavaDoc predecessor = (Stmt) graph.getPredsOf( stmt ).get(0);
162                 if( !( predecessor instanceof AssignStmt ) ) break;
163                 AssignStmt pred = (AssignStmt) predecessor;
164                 if( !(pred.getRightOp() instanceof InstanceOfExpr ) ) break;
165                 InstanceOfExpr iofexpr = (InstanceOfExpr) pred.getRightOp();
166                 if( !(iofexpr.getCheckType() instanceof RefType ) ) break;
167                 if( !(iofexpr.getOp() instanceof Local ) ) break;
168                 ConditionExpr c = (ConditionExpr) ifstmt.getCondition();
169                 if( !c.getOp1().equals( pred.getLeftOp() ) ) break;
170                 if( !( c.getOp2() instanceof IntConstant ) ) break;
171                 if( ( (IntConstant) c.getOp2() ).value != 0 ) break;
172                 if( c instanceof NeExpr ) {
173                     // The IfStmt is like this:
174 // if x instanceof t goto somewhere_else
175 // So x is of type t on the taken branch
176 outBranch = (LocalTypeSet) out.clone();
177                     outBranch.localMustBeSubtypeOf( (Local) iofexpr.getOp(),
178                                                     (RefType) iofexpr.getCheckType() );
179                 } else if( c instanceof EqExpr ) {
180                     // The IfStmt is like this:
181 // if !(x instanceof t) goto somewhere_else
182 // So x is of type t on the fallthrough branch
183 outBranch = (LocalTypeSet) out.clone();
184                     out.localMustBeSubtypeOf( (Local) iofexpr.getOp(),
185                                               (RefType) iofexpr.getCheckType() );
186                 }
187             } while( false );
188         }
189         
190         // Now copy the computed (local,type) set to all successors
191 for( Iterator it = outFallValues.iterator(); it.hasNext(); ) {
192             copy( out, it.next() );
193         }
194         for( Iterator it = outBranchValues.iterator(); it.hasNext(); ) {
195             copy( outBranch, it.next() );
196         }
197     }
198
199     protected void copy( Object JavaDoc source, Object JavaDoc dest ) {
200         LocalTypeSet s = (LocalTypeSet) source;
201         LocalTypeSet d = (LocalTypeSet) dest;
202         d.and( s );
203         d.or( s );
204     }
205
206     // The merge operator is set intersection.
207 protected void merge( Object JavaDoc in1, Object JavaDoc in2, Object JavaDoc out ) {
208         LocalTypeSet o = (LocalTypeSet) out;
209         o.setAllBits();
210         o.and( (LocalTypeSet) in1 );
211         o.and( (LocalTypeSet) in2 );
212     }
213     
214     /** Returns a new, aggressive (local,type) set. */
215     protected Object JavaDoc entryInitialFlow() {
216         LocalTypeSet ret = (LocalTypeSet) emptySet.clone();
217         return ret;
218     }
219 }
220
221
Popular Tags