KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > jimple > toolkits > scalar > CommonSubexpressionEliminator


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 2000 Patrick Lam
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 /*
21  * Modified by the Sable Research Group and others 1997-1999.
22  * See the 'credits' file distributed with Soot for the complete list of
23  * contributors. (Soot is distributed at http://www.sable.mcgill.ca/soot)
24  */
25
26
27 package soot.jimple.toolkits.scalar;
28 import soot.options.*;
29 import soot.options.*;
30 import soot.*;
31 import soot.toolkits.scalar.*;
32 import soot.toolkits.graph.*;
33 import soot.jimple.*;
34 import java.util.*;
35 import soot.util.*;
36 import soot.jimple.toolkits.pointer.PASideEffectTester;
37 import soot.tagkit.*;
38
39 /** Runs an available expressions analysis on a body, then
40  * eliminates common subexpressions.
41  *
42  * This implementation is especially slow, as it does not
43  * run on basic blocks. A better implementation (which wouldn't
44  * catch every single cse, but would get most) would use
45  * basic blocks instead.
46  *
47  * It is also slow because the flow universe is explicitly created; it
48  * need not be. A better implementation would implicitly compute the
49  * kill sets at every node. */
50
51 public class CommonSubexpressionEliminator extends BodyTransformer
52 {
53     public CommonSubexpressionEliminator( Singletons.Global g ) {}
54     public static CommonSubexpressionEliminator v() { return G.v().soot_jimple_toolkits_scalar_CommonSubexpressionEliminator(); }
55
56     /** Common subexpression eliminator. */
57     protected void internalTransform(Body b, String JavaDoc phaseName, Map options)
58     {
59         int counter = 0;
60
61         // Sigh. check for name collisions.
62 Iterator localsIt = b.getLocals().iterator();
63         HashSet localNames = new HashSet(b.getLocals().size());
64         while (localsIt.hasNext())
65         {
66             localNames.add(((Local)localsIt.next()).getName());
67         }
68
69         SideEffectTester sideEffect;
70         if( Scene.v().hasCallGraph()
71         && !PhaseOptions.getBoolean( options, "naive-side-effect" ) ) {
72             sideEffect = new PASideEffectTester();
73         } else {
74             sideEffect = new NaiveSideEffectTester();
75         }
76         sideEffect.newMethod( b.getMethod() );
77
78         if(Options.v().verbose())
79             G.v().out.println("[" + b.getMethod().getName() +
80                 "] Eliminating common subexpressions " +
81         (sideEffect instanceof NaiveSideEffectTester ?
82          "(naively)" : "") +
83         "...");
84
85         AvailableExpressions ae = // new SlowAvailableExpressions(b);
86 new FastAvailableExpressions(b, sideEffect);
87
88         Chain units = b.getUnits();
89         Iterator unitsIt = units.snapshotIterator();
90         while (unitsIt.hasNext())
91         {
92             Stmt s = (Stmt) unitsIt.next();
93
94             if (s instanceof AssignStmt)
95             {
96                 Chain availExprs = ae.getAvailableEquivsBefore(s);
97                 //G.v().out.println("availExprs: "+availExprs);
98 Value v = (Value)((AssignStmt)s).getRightOp();
99                 EquivalentValue ev = new EquivalentValue(v);
100
101                 if (availExprs.contains(ev))
102                 {
103                     // now we need to track down the containing stmt.
104 List availPairs = ae.getAvailablePairsBefore(s);
105                     //G.v().out.println("availPairs: "+availPairs);
106 Iterator availIt = availPairs.iterator();
107                     while (availIt.hasNext())
108                     {
109                         UnitValueBoxPair up = (UnitValueBoxPair)availIt.next();
110                         if (up.getValueBox().getValue().equivTo(v))
111                         {
112                             // create a local for temp storage.
113 // (we could check to see that the def must-reach, I guess...)
114 String JavaDoc newName = "$cseTmp"+counter;
115                             counter++;
116
117                             while (localNames.contains(newName))
118                             {
119                                 newName = "$cseTmp"+counter;
120                                 counter++;
121                             }
122
123                             Local l = Jimple.v().newLocal(newName, Type.toMachineType(v.getType()));
124
125                             b.getLocals().add(l);
126
127                             // I hope it's always an AssignStmt -- Jimple should guarantee this.
128 AssignStmt origCalc = (AssignStmt)up.getUnit();
129                             Value origLHS = origCalc.getLeftOp();
130
131                             origCalc.setLeftOp(l);
132                             
133                             Unit copier = Jimple.v().newAssignStmt(origLHS, l);
134                             units.insertAfter(copier, origCalc);
135
136                             ((AssignStmt)s).setRightOp(l);
137                             copier.addTag(new StringTag("Common sub-expression"));
138                             s.addTag(new StringTag("Common sub-expression"));
139                             //G.v().out.println("added tag to : "+copier);
140 //G.v().out.println("added tag to : "+s);
141 }
142                     }
143                 }
144             }
145         }
146         if(Options.v().verbose())
147             G.v().out.println("[" + b.getMethod().getName() +
148                      "] Eliminating common subexpressions done!");
149     }
150 }
151
Popular Tags