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.diva;
022:
023: import java.util.*;
024:
025: import EDU.purdue.cs.bloat.cfg.*;
026: import EDU.purdue.cs.bloat.ssa.*;
027: import EDU.purdue.cs.bloat.tree.*;
028:
029: /**
030: * InductionVarAnalyzer traverses a control flow graph and looks for array
031: * element swizzle operations inside loops. If possible, these swizzle
032: * operations are hoisted out of the loop and are replaced with range swizzle
033: * operations. The technique used is Demand-driven Induction Variable Analysis
034: * (DIVA).
035: * <p>
036: * To accomplish its tasks, InductionVarAnalyzer keeps track of a number of
037: * induction variables (represented by Swizzler objects) and local variables.
038: *
039: * @see Swizzler
040: * @see LocalExpr
041: */
042: public class InductionVarAnalyzer {
043: public static boolean DEBUG = false;
044:
045: SSAGraph ssaGraph;
046:
047: FlowGraph CFG; // Control flow graph being operated on
048:
049: HashMap IndStore; // Stores induction variables and
050:
051: // associated swizzlers
052: HashMap LocalStore; // Stores local variables
053:
054: Expr ind_var = null; // An induction variable
055:
056: Expr ind_init = null; // Initial value of an induction variable
057:
058: Expr ind_term = null; // Not used???
059:
060: Expr ind_inc = null; // Expression used to increment induction
061:
062: // variable (all uses commented out)
063: Expr tgt = null; // Target of the phi statement that defines
064:
065: // an induction var
066:
067: boolean changed = false; // Was the cfg changed?
068:
069: /**
070: * Searches the list of induction variables for an induction variable with a
071: * given value number.
072: *
073: * @param vn
074: * Value number to search for.
075: *
076: * @return Swizzler object whose target has the desired value number or
077: * null, if value number is not found.
078: */
079: public Object get_swizzler(final int vn) {
080: final Iterator iter = IndStore.values().iterator();
081:
082: while (iter.hasNext()) {
083: final Swizzler swz = (Swizzler) iter.next();
084: if ((swz.target().valueNumber() == vn)
085: || (swz.ind_var().valueNumber() == vn)) {
086: return swz;
087: }
088: }
089: return null;
090: }
091:
092: /**
093: * Searchs the stored list of local variables for a local variable with a
094: * given value number.
095: *
096: * @param vn
097: * The value number to search for.
098: *
099: * @return The local variable with the given value number, or null, if not
100: * found.
101: */
102: public MemExpr get_local(final int vn) {
103: final Iterator iter = LocalStore.keySet().iterator();
104:
105: while (iter.hasNext()) {
106: final MemExpr le = (MemExpr) iter.next();
107: if (le.valueNumber() == vn) {
108: return le;
109: }
110: }
111: return null;
112: }
113:
114: /**
115: * Displays (to System.out) all of the Swizzlers stored in the induction
116: * variable store.
117: *
118: * @see Swizzler
119: */
120: public void Display_store() {
121: final Iterator iter = IndStore.values().iterator();
122:
123: while (iter.hasNext()) {
124: final Swizzler indswz = (Swizzler) iter.next();
125:
126: System.out.println("\nIV: " + indswz.ind_var() + " tgt: "
127: + indswz.target() + "\narray: " + indswz.array()
128: + " init: " + indswz.init_val() + " end: "
129: + indswz.end_val());
130: }
131: }
132:
133: /**
134: * Displays the contents of a Swizzler object to System.out.
135: *
136: * @param indswz
137: * The Swizzler to display.
138: */
139: public void displaySwizzler(final Swizzler indswz) {
140: System.out.println("\nIV: " + indswz.ind_var() + "vn:"
141: + indswz.ind_var().valueNumber() + " tgt: "
142: + indswz.target() + "vn:"
143: + indswz.target().valueNumber() + "\narray: "
144: + indswz.array() + " init: " + indswz.init_val()
145: + " end: " + indswz.end_val());
146: }
147:
148: /**
149: * Adds a swizzle range statement (SRStmt) to the end of each predacessor
150: * block of the block containing the phi statement that defines an induction
151: * variable provided that the phi block does not dominate its predacessor.
152: * Phew.
153: *
154: * @param indswz
155: * Swizzler representing the induction variable on which the
156: * range swizzle statement is added.
157: */
158: public void insert_aswrange(final Swizzler indswz) {
159: final Iterator iter = CFG.preds(indswz.phi_block()).iterator();
160: while (iter.hasNext()) {
161: final Block blk = (Block) iter.next();
162: if (!indswz.phi_block().dominates(blk)) {
163: final SRStmt aswrange = new SRStmt((Expr) indswz
164: .array().clone(), (Expr) indswz.init_val()
165: .clone(), (Expr) indswz.end_val().clone());
166: blk.tree().addStmtBeforeJump(aswrange);
167: changed = true;
168: if (InductionVarAnalyzer.DEBUG) {
169: System.out.println("Inserted ASWR: " + aswrange
170: + "\nin block: " + blk);
171:
172: System.out.println("$$$ can insert aswrange now\n"
173: + "array: " + indswz.array() + "\nIV: "
174: + indswz.ind_var() + "\ninit: "
175: + indswz.init_val() + "\nend: "
176: + indswz.end_val());
177: }
178: }
179: }
180: }
181:
182: /* To determine if a phi statement is a mu */
183: /* Returns null if not a MU and sets ind_var & ind_init */
184: /* to refer to the IV & its initial value otherwise */
185:
186: /**
187: * Determines whether or not a phi statement is a mu function. A mu function
188: * is a phi function that merges values at loop headers, as opposed to those
189: * that occur as a result of forward branching. Mu functions always have two
190: * arguments.
191: *
192: * @param phi
193: * phi statement that may be a mu function
194: * @param cfg
195: * CFG to look through <font color="ff0000">Get rid of this
196: * parameter</font>
197: *
198: * @return The block containing the mu functions external (that is, outside
199: * the loop) argument, also known as the external ssalink. If the
200: * phi statement is not a mu function, null is returned.
201: */
202: public Block isMu(final PhiJoinStmt phi, final FlowGraph cfg) {
203: // Does it contain two operands?
204: if (phi.numOperands() != 2) {
205: return null;
206: }
207:
208: // Is it REDUCIBLE?
209: if ((cfg.blockType(phi.block()) == Block.IRREDUCIBLE)
210: || (cfg.blockType(phi.block()) == Block.NON_HEADER)) {
211: return null;
212: }
213:
214: /*
215: * Does one of them dominate the phi and the other dominated by the phi?
216: */
217:
218: final Iterator iter = cfg.preds(phi.block()).iterator();
219: final Block pred1 = (Block) iter.next();
220: final Block pred2 = (Block) iter.next();
221:
222: if (pred1.dominates(phi.block())
223: && phi.block().dominates(pred2)
224: && (pred1 != phi.block())) {
225: if (InductionVarAnalyzer.DEBUG) {
226: System.out.println("Extlink = 1 pred1:" + pred1
227: + " pred2:" + pred2);
228: }
229: ind_var = phi.operandAt(pred2);
230: ind_init = phi.operandAt(pred1);
231: return pred1;
232: }
233: if (pred2.dominates(phi.block())
234: && phi.block().dominates(pred1)
235: && (pred2 != phi.block())) {
236: if (InductionVarAnalyzer.DEBUG) {
237: System.out.println("Extlink = 2 pred1:" + pred1
238: + " pred2:" + pred2);
239: }
240: ind_var = phi.operandAt(pred1);
241: ind_init = phi.operandAt(pred2);
242: return pred2;
243: }
244:
245: return null;
246:
247: }
248:
249: /**
250: * Performs DIVA on a CFG public static void transform(FlowGraph cfg) { //
251: * Create a new instance to allow multiple threads. InductionVarAnalyzer me =
252: * new InductionVarAnalyzer(); me.transform(cfg); }
253: */
254:
255: /**
256: * Performs DIVA on a CFG.
257: */
258: public void transform(final FlowGraph cfg) {
259: ssaGraph = new SSAGraph(cfg);
260: CFG = cfg;
261: IndStore = new HashMap();
262: LocalStore = new HashMap();
263: changed = false;
264:
265: if (InductionVarAnalyzer.DEBUG) {
266: System.out
267: .println("----------Before visitComponents--------------");
268: cfg.print(System.out);
269: }
270:
271: // Visit each strongly connected component (SCC) in the CFG. SCCs
272: // correspond to sequences in the program. Visit each node in the
273: // SCC and build the local variable store. Create Swizzlers at
274: // PhiStmts, if approproate, and store them in the induction
275: // variable store. If it can be determined that an array element
276: // swizzle can be hoisted out of a loop, it is hoisted.
277: ssaGraph.visitComponents(new ComponentVisitor() {
278: public void visitComponent(final List scc) {
279: if (InductionVarAnalyzer.DEBUG) {
280: System.out.println("SCC =");
281: }
282:
283: final Iterator e = scc.iterator();
284:
285: while (e.hasNext()) {
286: final Node v = (Node) e.next();
287: if (InductionVarAnalyzer.DEBUG) {
288: System.out.println(" " + v + "{" + v.key()
289: + "} " + v.getClass());
290: }
291:
292: v.visit(new TreeVisitor() {
293: public void visitPhiJoinStmt(
294: final PhiJoinStmt phi) {
295: if (isMu(phi, CFG) != null) {
296: tgt = phi.target();
297: if (InductionVarAnalyzer.DEBUG) {
298: System.out.println("IV:" + ind_var
299: + " VN:"
300: + ind_var.valueNumber()
301: + "\ninit:" + ind_init
302: + " target: " + tgt
303: + " VN: "
304: + tgt.valueNumber());
305: }
306: final Swizzler swz = new Swizzler(
307: ind_var, tgt, ind_init, phi
308: .block());
309: if (InductionVarAnalyzer.DEBUG) {
310: System.out
311: .println("store swizzler for "
312: + ind_var.def()
313: + " & " + tgt.def());
314: displaySwizzler(swz);
315: }
316:
317: if (ind_var.def() != null) {
318: IndStore.put(ind_var.def(), swz);
319: }
320:
321: if (tgt.def() != null) {
322: IndStore.put(tgt.def(), swz);
323: }
324:
325: if (InductionVarAnalyzer.DEBUG) {
326: System.out.println(" Mu: " + phi
327: + "{" + phi.key() + "}");
328: }
329: } else {
330: if (InductionVarAnalyzer.DEBUG) {
331: System.out.println("Phi: " + phi
332: + "{" + phi.key() + "}");
333: }
334: }
335: }
336:
337: public void visitLocalExpr(final LocalExpr me) {
338: if (me.def() != null) {
339: if (LocalStore.get(me.def()) == null) {
340: LocalStore.put(me.def(), me);
341: }
342: }
343: if (LocalStore.get(me) == null) {
344: LocalStore.put(me, me);
345: }
346: if (InductionVarAnalyzer.DEBUG) {
347: System.out.println("stored ME: " + me
348: + " vn: " + me.valueNumber());
349: }
350: }
351:
352: public void visitStaticFieldExpr(
353: final StaticFieldExpr me) {
354: if (me.def() != null) {
355: if (LocalStore.get(me.def()) == null) {
356: LocalStore.put(me.def(), me);
357: }
358: }
359: if (LocalStore.get(me) == null) {
360: LocalStore.put(me, me);
361: }
362: if (InductionVarAnalyzer.DEBUG) {
363: System.out.println("stored ME: " + me
364: + " vn: " + me.valueNumber());
365: }
366: }
367:
368: public void visitIfCmpStmt(final IfCmpStmt cmp) {
369: Swizzler indswz = null;
370: boolean set_term = false;
371:
372: if (cmp.left().def() != null) {
373: indswz = (Swizzler) IndStore.get(cmp
374: .left().def());
375: }
376: if (indswz != null) {
377: if (InductionVarAnalyzer.DEBUG) {
378: displaySwizzler(indswz);
379: }
380: if (indswz.end_val() == null) {
381: indswz.set_end_val(cmp.right());
382: set_term = true;
383: if (InductionVarAnalyzer.DEBUG) {
384: System.out
385: .println("Set end_val of "
386: + indswz
387: .ind_var()
388: + " to "
389: + cmp.right());
390: }
391: }
392: } else {
393: if (cmp.right().def() != null) {
394: indswz = (Swizzler) IndStore
395: .get(cmp.right().def());
396: }
397: if (indswz != null) {
398: if (InductionVarAnalyzer.DEBUG) {
399: displaySwizzler(indswz);
400: }
401: if (indswz.end_val() == null) {
402: indswz.set_end_val(cmp.left());
403: set_term = true;
404: if (InductionVarAnalyzer.DEBUG) {
405: System.out
406: .println("Set end_val of "
407: + indswz
408: .ind_var()
409: + " to "
410: + cmp
411: .left());
412: }
413: }
414: }
415: }
416:
417: if (set_term && (indswz != null)
418: && (indswz.array() != null)) {
419: indswz.aswizzle().set_redundant(true);
420: insert_aswrange(indswz);
421: }
422: }
423:
424: public void visitSCStmt(final SCStmt sc) {
425: Swizzler indswz;
426: MemExpr le = null;
427:
428: if (InductionVarAnalyzer.DEBUG) {
429: System.out.println("SC: array= "
430: + sc.array() + " VN:"
431: + sc.array().valueNumber()
432: + "\nindex=" + sc.index()
433: + " VN:"
434: + sc.index().valueNumber());
435: }
436:
437: indswz = (Swizzler) get_swizzler(sc.index()
438: .valueNumber());
439: if (indswz != null) {
440: if (InductionVarAnalyzer.DEBUG) {
441: displaySwizzler(indswz);
442: }
443: if (indswz.array() == null) {
444: le = get_local(sc.array()
445: .valueNumber());
446: if ((le == null)
447: && (sc.array().def() != null)) {
448: le = get_local(sc.array().def()
449: .valueNumber());
450: }
451: if (le != null) {
452: if (InductionVarAnalyzer.DEBUG) {
453: System.out.println("Le: "
454: + le);
455: }
456: indswz.set_array(le);
457: indswz.set_aswizzle(sc);
458: } else {
459: return;
460: }
461: }
462: if (indswz.end_val() != null) {
463: sc.set_redundant(true);
464: insert_aswrange(indswz);
465: }
466: }
467: }
468:
469: /*
470: * public void visitStoreExpr(StoreExpr ind_store) {
471: * if(ind_var != null) {
472: * if(ind_var.equalsExpr(ind_store.target())) { if (tgt !=
473: * null && ind_store.expr() instanceof ArithExpr){
474: * ArithExpr ind_exp = (ArithExpr)ind_store.expr();
475: * if(tgt.equalsExpr(ind_exp.left())) ind_inc =
476: * ind_exp.right(); else if(tgt.equals(ind_exp.right()))
477: * ind_inc = ind_exp.left(); else { ind_inc = null;
478: * return; } System.out.println("Ind_inc: "+ind_inc); } } } }
479: */
480:
481: });
482:
483: }
484:
485: }
486:
487: });
488:
489: if (InductionVarAnalyzer.DEBUG) {
490: System.out
491: .println("------------After visitComponents---------");
492: cfg.print(System.out);
493: }
494:
495: // If the CFG changed (i.e. if an array range swizzle was added),
496: // traverse
497: // the graph and remove redundent swizzle statements.
498: if (changed) {
499: cfg.visit(new TreeVisitor() {
500: ListIterator iter;
501:
502: public void visitTree(final Tree tree) {
503: iter = tree.stmts().listIterator();
504:
505: while (iter.hasNext()) {
506: final Stmt stmt = (Stmt) iter.next();
507: stmt.visit(this );
508: }
509: }
510:
511: public void visitSCStmt(final SCStmt sc) {
512: Object dup2stmt;
513: if (sc.redundant()) {
514:
515: iter.remove();
516: dup2stmt = iter.previous();
517: iter.remove();
518: if (InductionVarAnalyzer.DEBUG) {
519: System.out
520: .println("Removed Redundant ASW: "
521: + sc + "\nand " + dup2stmt);
522: }
523: }
524: }
525: });
526: }
527:
528: if (InductionVarAnalyzer.DEBUG) {
529: System.out
530: .println("----------------After cfg.visit--------------");
531: cfg.print(System.out);
532: }
533: }
534: }
|