001: /* Copyright (C) 2004 - 2007 db4objects Inc. http://www.db4o.com
002:
003: This file is part of the db4o open source object database.
004:
005: db4o is free software; you can redistribute it and/or modify it under
006: the terms of version 2 of the GNU General Public License as published
007: by the Free Software Foundation and as clarified by db4objects' GPL
008: interpretation policy, available at
009: http://www.db4o.com/about/company/legalpolicies/gplinterpretation/
010: Alternatively you can write to db4objects, Inc., 1900 S Norfolk Street,
011: Suite 350, San Mateo, CA 94403, USA.
012:
013: db4o is distributed in the hope that it will be useful, but WITHOUT ANY
014: WARRANTY; without even the implied warranty of MERCHANTABILITY or
015: FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
016: for more details.
017:
018: You should have received a copy of the GNU General Public License along
019: with this program; if not, write to the Free Software Foundation, Inc.,
020: 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
021: package EDU.purdue.cs.bloat.tree;
022:
023: import java.util.*;
024:
025: import EDU.purdue.cs.bloat.cfg.*;
026:
027: /**
028: * StackOptimizer analyzes the relative distances of various uses of the same
029: * definition of a local variable to add dups and swaps to the bytecode and
030: * eliminate loads and stores.
031: *
032: * @author Thomas VanDrunen
033: */
034:
035: public class StackOptimizer {
036:
037: static boolean DEBUG = false;
038:
039: Hashtable defInfoMap; /*
040: * maps LocalExprs (which are definitions) to
041: * DefInformations
042: */
043:
044: Hashtable useInfoMap; /* maps LocalExprs to UseInformations */
045:
046: Block owningBlock;
047:
048: public StackOptimizer(final Block owningBlock) {
049: this .owningBlock = owningBlock;
050: defInfoMap = new Hashtable();
051: useInfoMap = new Hashtable();
052: }
053:
054: public static void optimizeCFG(final FlowGraph cfg) {
055:
056: final List blocks = cfg.preOrder();
057: for (final Iterator it = blocks.iterator(); it.hasNext();) {
058: ((Block) it.next()).stackOptimizer().optimize();
059: }
060:
061: }
062:
063: /**
064: * Optimize runs the algorithm for analyzing the tree, looking for
065: * opportunities to replaces stores and loads with dups and swaps. It
066: * initiates several visitors, and information is sotred in defInfoMap and
067: * useInfoMap
068: */
069:
070: public void optimize() {
071:
072: final Vector LEs = (new LEGatherer()).getLEs(owningBlock); // get all
073: // the
074: LocalExpr current; // LocalExprs in the block
075:
076: for (int i = 0; i < LEs.size(); i++) {
077:
078: current = (LocalExpr) LEs.elementAt(i);
079:
080: useInfoMap.put(current, new UseInformation());
081:
082: if (current.isDef()) {
083: final DefInformation DI = new DefInformation(
084: current.uses.size());
085: defInfoMap.put(current, DI);
086: // send the DefInformation the number of uses of the var
087: } else if (current.def() != null) {
088:
089: final DefInformation DI = (DefInformation) defInfoMap
090: .get(current.def());
091:
092: if (DI == null) {
093: continue; // if it has no def information,
094: // it's probably a parameter, and we need to store it
095: // anyway.
096: }
097:
098: DI.usesFound++;
099:
100: // handle a special case
101: // if we have something like L := L + k, we can do
102: // "iinc L, k", which would be better (wouldn't it?) than
103: // propogating L on the stack, loading a constant, adding,
104: // and saving. In that case, also, we'll have to load.
105: // (see codegen/CodeGenerator.java, circa line 1334)
106:
107: if ((current.parent() instanceof ArithExpr)
108: && (current.parent().parent() instanceof StoreExpr)
109: && (((((ArithExpr) current.parent()).left() instanceof ConstantExpr) && ((ArithExpr) current
110: .parent()).left().type().isIntegral()) || ((((ArithExpr) current
111: .parent()).right() instanceof ConstantExpr) && ((ArithExpr) current
112: .parent()).left().type().isIntegral()))
113: && (((StoreExpr) current.parent().parent())
114: .target() instanceof LocalExpr)
115: && (((LocalExpr) ((StoreExpr) current.parent()
116: .parent()).target()).index() == current
117: .index())) {
118: DI.type1s += 3;
119: } else if ((current.parent() instanceof StoreExpr)
120: && (current.parent().parent() instanceof ExprStmt)
121: && (((StoreExpr) current.parent()).target() instanceof LocalExpr)
122: && (((LocalExpr) ((StoreExpr) current.parent())
123: .target()).index() == current.index())) {
124: DI.type1s += 3; // the new "definition" no doubt
125: // has uses, so we need the original stored
126: continue;
127: }
128:
129: else {
130:
131: // first search using a Type0Visitor. If that search
132: // fails, use a Type1Visitor. (The second condition checks
133: // whether we have too many type 1s already, and will
134: // have to store it.... there's no point in looking for
135: // anymore
136: if (!((new Type0Visitor(defInfoMap, useInfoMap))
137: .search(current))
138: && (DI.type1s < 3)) {
139:
140: // Java, I hate you as much as I love you.
141: // I blink my eyes and more complications spring up.
142: // So far I have been happily ignoring the problem
143: // of wide expressions-- there's no way we can
144: // do type 1 optimizations on wide values because
145: // we can't do a swap on values that take up two
146: // stack positions...
147:
148: if (current.type().isWide()) {
149: DI.type1s += 3; // give up
150: } else {
151: (new Type1Visitor(defInfoMap, useInfoMap))
152: .search(current);
153: }
154: }
155: }
156: }
157: }
158: }
159:
160: /**
161: * Various methods used by CodeGenerator, used as an interface into the
162: * information in defInfoMap and useInfoMap
163: */
164:
165: public boolean shouldStore(final LocalExpr expr) {
166:
167: // We should store if there are more than 2 type 1 uses or
168: // any uses of type greater than one-- which will be indicated
169: // by type1s being greater than 2
170:
171: // the parameter expr might be null, e.g., if this method is
172: // called from "dups" in "!shouldStore((LocalExpr) expr.def())",
173: // because if the expression is a use of a parameter in a method,
174: // its definition is null. Return true in that case because it
175: // will be saved to a local anyway
176: if (expr == null) {
177: return true;
178: }
179:
180: final DefInformation DI = (DefInformation) defInfoMap.get(expr);
181: if (DI == null) {
182: if (StackOptimizer.DEBUG) {
183: System.err
184: .println("Error in StackOptimizer.shouldStore: parameter not found in defInfoMap:");
185: System.err.println(expr.toString());
186: }
187:
188: return true;
189: }
190:
191: if ((DI.type1s > 2) || (DI.usesFound < DI.uses)) {
192: return true;
193: } else {
194: return false;
195: }
196: }
197:
198: public int dups(final LocalExpr expr) {
199:
200: int toReturn = 0;
201: final UseInformation UI = (UseInformation) useInfoMap.get(expr);
202:
203: if (UI == null) {
204: if (StackOptimizer.DEBUG) {
205: System.err
206: .println("Error in StackOptimizer.dups: parameter not found in useInfoMap");
207: }
208: return toReturn;
209: }
210:
211: toReturn += (UI.type0s - UI.type0_x1s - UI.type0_x2s);
212: if ((expr.isDef() && !shouldStore(expr))
213: || (!(expr.isDef()) && !shouldStore((LocalExpr) expr
214: .def()))) {
215: toReturn += (UI.type1s - UI.type1_x1s - UI.type1_x2s);
216: }
217:
218: return toReturn;
219: }
220:
221: public int dup_x1s(final LocalExpr expr) {
222:
223: int toReturn = 0;
224: final UseInformation UI = (UseInformation) useInfoMap.get(expr);
225:
226: if (UI == null) {
227: if (StackOptimizer.DEBUG) {
228: System.err
229: .println("Error in StackOptimizer.dup_x1s: parameter not found in useInfoMap");
230: }
231: return toReturn;
232: }
233:
234: toReturn += UI.type0_x1s;
235: if ((expr.isDef() && !shouldStore(expr))
236: || (!(expr.isDef()) && !shouldStore((LocalExpr) expr
237: .def()))) {
238: toReturn += UI.type1_x1s;
239: }
240:
241: return toReturn;
242: }
243:
244: public int dup_x2s(final LocalExpr expr) {
245:
246: int toReturn = 0;
247: final UseInformation UI = (UseInformation) useInfoMap.get(expr);
248:
249: if (UI == null) {
250: if (StackOptimizer.DEBUG) {
251: System.err
252: .println("Error in StackOptimizer.dup_x2s: parameter not found in useInfoMap");
253: }
254: return toReturn;
255: }
256:
257: toReturn += UI.type0_x2s;
258: if ((expr.isDef() && !shouldStore(expr))
259: || (!(expr.isDef()) && !shouldStore((LocalExpr) expr
260: .def()))) {
261: toReturn += UI.type1_x2s;
262: }
263:
264: return toReturn;
265: }
266:
267: public boolean onStack(final LocalExpr expr) {
268:
269: if (expr.isDef()) {
270: return false;
271: }
272:
273: final UseInformation UI = (UseInformation) useInfoMap.get(expr);
274:
275: if (UI == null) {
276: if (StackOptimizer.DEBUG) {
277: System.err
278: .println("Error in StackOptimizer.onStack: parameter not found in useInfoMap");
279: }
280: return false;
281: }
282:
283: if (UI.type == 0) {
284: return true;
285: }
286:
287: if ((UI.type == 1) && !shouldStore((LocalExpr) expr.def())) {
288: return true;
289: }
290:
291: return false;
292: }
293:
294: public boolean shouldSwap(final LocalExpr expr) {
295:
296: final UseInformation UI = (UseInformation) useInfoMap.get(expr);
297:
298: if (UI == null) {
299: if (StackOptimizer.DEBUG) {
300: System.err
301: .println("Error in StackOptimizer.onStack: parameter not found in useInfoMap");
302: }
303: return false;
304: }
305:
306: return (onStack(expr) && (UI.type == 1));
307: }
308:
309: public void infoDisplay(final LocalExpr expr) {
310:
311: final UseInformation UI = (UseInformation) useInfoMap.get(expr);
312: final DefInformation DI = (DefInformation) defInfoMap.get(expr);
313:
314: System.err.println(expr.toString());
315: System.err.println(expr.parent().toString() + "-"
316: + expr.parent().parent().toString());
317: if ((expr.parent().parent().parent() != null)
318: && (expr.parent().parent().parent().parent() != null)) {
319: System.err.println(expr.parent().parent().parent()
320: .toString()
321: + "-"
322: + expr.parent().parent().parent().parent()
323: .toString());
324: }
325:
326: if (DI == null) {
327: System.err.println("not a definition");
328: if (expr.def() == null) {
329: System.err.println("has no definition (is parameter?)");
330: } else {
331: System.err.println("has definition " + expr.def());
332: }
333: } else {
334: System.err.println("a definition with " + DI.type1s
335: + " type1s total");
336: System.err.println("uses: " + DI.uses);
337: System.err.println("uses found: " + DI.usesFound);
338: if (shouldStore(expr)) {
339: System.err.println("should store");
340: }
341: }
342:
343: if (UI == null) {
344: System.err.println("No use information entry. trouble");
345: } else {
346: if (DI == null) {
347: System.err.println("type on stack: " + UI.type);
348: }
349: System.err
350: .println("type0s for this instance: " + UI.type0s);
351: System.err.println("of above, number of x1s: "
352: + UI.type0_x1s);
353: System.err.println("of above, number of x2s: "
354: + UI.type0_x2s);
355: System.err
356: .println("type1s for this instance: " + UI.type1s);
357: System.err.println("of above, number of x1s: "
358: + UI.type1_x1s);
359: System.err.println("of above, number of x2s: "
360: + UI.type1_x2s);
361: }
362:
363: }
364: }
|