001: /* Soot - a J*va Optimization Framework
002: * Copyright (C) 2003 Ondrej Lhotak
003: *
004: * This library is free software; you can redistribute it and/or
005: * modify it under the terms of the GNU Lesser General Public
006: * License as published by the Free Software Foundation; either
007: * version 2.1 of the License, or (at your option) any later version.
008: *
009: * This library is distributed in the hope that it will be useful,
010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
012: * Lesser General Public License for more details.
013: *
014: * You should have received a copy of the GNU Lesser General Public
015: * License along with this library; if not, write to the
016: * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
017: * Boston, MA 02111-1307, USA.
018: */
019:
020: package soot.jimple.toolkits.pointer;
021:
022: import soot.*;
023: import java.util.*;
024: import soot.jimple.toolkits.callgraph.*;
025: import soot.jimple.*;
026:
027: public class SideEffectTagger extends BodyTransformer {
028: public SideEffectTagger(Singletons.Global g) {
029: }
030:
031: public static SideEffectTagger v() {
032: return G.v().soot_jimple_toolkits_pointer_SideEffectTagger();
033: }
034:
035: public int numRWs = 0;
036: public int numWRs = 0;
037: public int numRRs = 0;
038: public int numWWs = 0;
039: public int numNatives = 0;
040: public Date startTime = null;
041: boolean optionNaive = false;
042: private CallGraph cg;
043:
044: protected class UniqueRWSets {
045: protected ArrayList<RWSet> l = new ArrayList<RWSet>();
046:
047: RWSet getUnique(RWSet s) {
048: if (s == null)
049: return s;
050: for (RWSet ret : l) {
051: if (ret.isEquivTo(s))
052: return ret;
053: }
054: l.add(s);
055: return s;
056: }
057:
058: Iterator<RWSet> iterator() {
059: return l.iterator();
060: }
061:
062: short indexOf(RWSet s) {
063: short i = 0;
064: for (RWSet ret : l) {
065: if (ret.isEquivTo(s))
066: return i;
067: i++;
068: }
069: return -1;
070: }
071: }
072:
073: protected void initializationStuff(String phaseName) {
074: G.v().Union_factory = new UnionFactory() {
075: //ReallyCheapRasUnion ru = new ReallyCheapRasUnion();
076: //public Union newUnion() { return new RasUnion(); }
077: public Union newUnion() {
078: return new MemoryEfficientRasUnion();
079: }
080: };
081:
082: if (startTime == null) {
083: startTime = new Date();
084: }
085: cg = Scene.v().getCallGraph();
086: }
087:
088: protected Object keyFor(Stmt s) {
089: if (s.containsInvokeExpr()) {
090: if (optionNaive)
091: throw new RuntimeException("shouldn't get here");
092: Iterator it = cg.edgesOutOf(s);
093: if (!it.hasNext()) {
094: return Collections.EMPTY_LIST;
095: }
096: ArrayList ret = new ArrayList();
097: while (it.hasNext()) {
098: ret.add(it.next());
099: }
100: return ret;
101: } else {
102: return s;
103: }
104: }
105:
106: protected void internalTransform(Body body, String phaseName,
107: Map options) {
108: initializationStuff(phaseName);
109: SideEffectAnalysis sea = Scene.v().getSideEffectAnalysis();
110: optionNaive = PhaseOptions.getBoolean(options, "naive");
111: if (!optionNaive) {
112: sea.findNTRWSets(body.getMethod());
113: }
114: HashMap<Object, RWSet> stmtToReadSet = new HashMap<Object, RWSet>();
115: HashMap<Object, RWSet> stmtToWriteSet = new HashMap<Object, RWSet>();
116: UniqueRWSets sets = new UniqueRWSets();
117: boolean justDoTotallyConservativeThing = body.getMethod()
118: .getName().equals("<clinit>");
119: for (Iterator stmtIt = body.getUnits().iterator(); stmtIt
120: .hasNext();) {
121: final Stmt stmt = (Stmt) stmtIt.next();
122: if (justDoTotallyConservativeThing
123: || (optionNaive && stmt.containsInvokeExpr())) {
124: stmtToReadSet
125: .put(stmt, sets.getUnique(new FullRWSet()));
126: stmtToWriteSet.put(stmt, sets
127: .getUnique(new FullRWSet()));
128: continue;
129: }
130: Object key = keyFor(stmt);
131: if (!stmtToReadSet.containsKey(key)) {
132: stmtToReadSet.put(key, sets.getUnique(sea.readSet(body
133: .getMethod(), stmt)));
134: stmtToWriteSet.put(key, sets.getUnique(sea.writeSet(
135: body.getMethod(), stmt)));
136: }
137: }
138: DependenceGraph graph = new DependenceGraph();
139: for (Iterator<RWSet> outerIt = sets.iterator(); outerIt
140: .hasNext();) {
141: final RWSet outer = outerIt.next();
142:
143: for (Iterator<RWSet> innerIt = sets.iterator(); innerIt
144: .hasNext();) {
145:
146: final RWSet inner = innerIt.next();
147: if (inner == outer)
148: break;
149: if (outer.hasNonEmptyIntersection(inner)) {
150: //G.v().out.println( "inner set is: "+inner );
151: //G.v().out.println( "outer set is: "+outer );
152: graph.addEdge(sets.indexOf(outer), sets
153: .indexOf(inner));
154: }
155: }
156: }
157: body.getMethod().addTag(graph);
158: for (Iterator stmtIt = body.getUnits().iterator(); stmtIt
159: .hasNext();) {
160: final Stmt stmt = (Stmt) stmtIt.next();
161: Object key;
162: if (optionNaive && stmt.containsInvokeExpr()) {
163: key = stmt;
164: } else {
165: key = keyFor(stmt);
166: }
167: RWSet read = stmtToReadSet.get(key);
168: RWSet write = stmtToWriteSet.get(key);
169: if (read != null || write != null) {
170: DependenceTag tag = new DependenceTag();
171: if (read != null && read.getCallsNative()) {
172: tag.setCallsNative();
173: numNatives++;
174: } else if (write != null && write.getCallsNative()) {
175: tag.setCallsNative();
176: numNatives++;
177: }
178: tag.setRead(sets.indexOf(read));
179: tag.setWrite(sets.indexOf(write));
180: stmt.addTag(tag);
181:
182: // The loop below is just for calculating stats.
183: /*
184: if( !justDoTotallyConservativeThing ) {
185: for( Iterator innerIt = body.getUnits().iterator(); innerIt.hasNext(); ) {
186: final Stmt inner = (Stmt) innerIt.next();
187: Object ikey;
188: if( optionNaive && inner.containsInvokeExpr() ) {
189: ikey = inner;
190: } else {
191: ikey = keyFor( inner );
192: }
193: RWSet innerRead = (RWSet) stmtToReadSet.get( ikey );
194: RWSet innerWrite = (RWSet) stmtToWriteSet.get( ikey );
195: if( graph.areAdjacent( sets.indexOf( read ),
196: sets.indexOf( innerWrite ) ) ) numRWs++;
197: if( graph.areAdjacent( sets.indexOf( write ),
198: sets.indexOf( innerRead ) ) ) numWRs++;
199: if( inner == stmt ) continue;
200: if( graph.areAdjacent( sets.indexOf( write ),
201: sets.indexOf( innerWrite ) ) ) numWWs++;
202: if( graph.areAdjacent( sets.indexOf( read ),
203: sets.indexOf( innerRead ) ) ) numRRs++;
204: }
205: }
206: */
207: }
208: }
209: }
210: }
|