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.ssa;
022:
023: import java.util.*;
024:
025: import EDU.purdue.cs.bloat.cfg.*;
026: import EDU.purdue.cs.bloat.tree.*;
027: import EDU.purdue.cs.bloat.util.*;
028:
029: /**
030: * Compute the SSA form of the control flow graph and build FUD chains.
031: * <p>
032: * The SSA algorithm is from:
033: *
034: * <pre>
035: * R. Cytron, J. Ferrante J, B. K. Rosen, M. N. Wegman, and F. K. Zadeck,
036: * "Efficiently Computing Static Single Assignment Form and the Control
037: * Dependence Graph", TOPLAS, 13(4): 451-490, October 1991.
038: * </pre>
039: *
040: * <p>
041: * I made modifications to the algorithm to compute FUD chains and to run the
042: * algorithm separately for each variable similar to the SSAPRE algorithm.
043: * Making a separate pass for each variable allows variables to be added
044: * incrementally.
045: */
046: public class SSA {
047: public static boolean DEBUG = false;
048:
049: /**
050: * Transforms a control flow graph into Single Static Assignment (SSA) form.
051: * First, the CFG is traversed and a list of all variables (both local and
052: * stack) eligible for SSA renaming is compiled. Variables are represented
053: * by instances of <tt>SSAConstructionInfo</tt>. Each of these variables
054: * is then transformed.
055: *
056: * @see #transform(FlowGraph)
057: * @see SSAConstructionInfo
058: */
059: public static void transform(final FlowGraph cfg) {
060: final Iterator e = SSA.collectVars(cfg);
061:
062: while (e.hasNext()) {
063: final SSAConstructionInfo info = (SSAConstructionInfo) e
064: .next();
065: SSA.transform(cfg, info);
066: }
067: }
068:
069: /**
070: * Performs the actions necessary to convert a CFG into SSA form with
071: * respect to one variable. The variable's information is stored in the
072: * <tt>SSAConstructionInfo</tt>.
073: */
074: public static void transform(final FlowGraph cfg,
075: final SSAConstructionInfo info) {
076: if (SSA.DEBUG) {
077: System.out.println("transforming " + info.prototype + " ("
078: + info.prototype.type() + ")");
079: }
080:
081: SSA.placePhiFunctions(cfg, info);
082: SSA.rename(cfg, info);
083: SSA.insertCode(cfg, info);
084: }
085:
086: /**
087: * Visits the nodes in a control flow graph and constructs
088: * <tt>SSAConstructionInfo</tt> objects for each variable in the CFG.
089: * Returns the <tt>SSAConstructionInfo</tt>s for the variables in the
090: * CFG.
091: */
092: private static Iterator collectVars(final FlowGraph cfg) {
093: // SSAConstructionInfo objects for cfg
094: final Map infos = new HashMap();
095:
096: cfg.visit(new TreeVisitor() {
097: // Visit all statements in the CFG. Remove any pre-existing
098: // PhiStmts.
099: public void visitTree(final Tree tree) {
100: final Iterator iter = tree.stmts().iterator();
101:
102: while (iter.hasNext()) {
103: final Stmt stmt = (Stmt) iter.next();
104:
105: if (stmt instanceof PhiStmt) {
106: iter.remove();
107:
108: } else {
109: stmt.visit(this );
110: }
111: }
112: }
113:
114: // Recall that VarExprs represent variables. If we have not
115: // already created a SSAConstructionInfo for a variable
116: // (VarExpr), do so. Make note of the fact that this is a real
117: // occurrence of the variable.
118: public void visitVarExpr(final VarExpr expr) {
119: expr.visitChildren(this );
120:
121: expr.setDef(null);
122:
123: final Object key = expr.comparator();
124:
125: SSAConstructionInfo info = (SSAConstructionInfo) infos
126: .get(key);
127:
128: if (info == null) {
129: info = new SSAConstructionInfo(cfg, expr);
130: infos.put(key, info);
131: }
132:
133: info.addReal(expr);
134: }
135: });
136:
137: return infos.values().iterator();
138: }
139:
140: /**
141: * Places phi statements at the appropriate locations in the CFG. This
142: * implementation only places phi functions for variables that are live on
143: * entry to at least one block. That is, if a variable is only used within
144: * one block, we don't bother searching for a place to put phi functions for
145: * it.
146: *
147: * @param cfg
148: * The CFG in which phi functions are placed.
149: * @param info
150: * The variable for which phi functions will be placed.
151: */
152: private static void placePhiFunctions(final FlowGraph cfg,
153: final SSAConstructionInfo info) {
154: if (SSA.DEBUG) {
155: System.out.println("Placing phi-functions for " + info);
156: }
157:
158: // Phis are only placed for variables which are live on entry to
159: // at least one block.
160: //
161: // This is the semi-pruned form described in "Practical
162: // Improvements to the Construction and Destruction of Static
163: // Single Assignment Form" by Briggs, Cooper, Harvey, Simpson
164: //
165:
166: // Blocks in which the variable in the SSAConstructionInfo is
167: // defined. That is, variables that are defined in this block.
168: final BitSet killed = new BitSet(cfg.size());
169:
170: // Is the variable used in more than one block?
171: boolean nonLocal = false;
172:
173: final Iterator reals = info.reals().iterator();
174:
175: // Look at all real (not in phi statement) occurrences of the
176: // variable in the SSAConstructionInfo. Determine which variables
177: // are live on entry to some basic block (i.e. "non-local"). If
178: // a variable is not live on entry to some basic block, it is only
179: // used within the block in which it is defined, so don't bother
180: // adding a phi statement for it.
181: while (reals.hasNext()) {
182: final VarExpr real = (VarExpr) reals.next();
183:
184: final Block block = real.block(); // Block in which variable
185: // occurs
186:
187: if (real.isDef()) {
188: killed.set(cfg.preOrderIndex(block));
189:
190: } else if (!killed.get(cfg.preOrderIndex(block))) {
191: // There is a use of the variable as an operand that is not
192: // defined in the block in which it occurs. Therefore, the
193: // variable is non-local.
194: nonLocal = true;
195: break;
196: }
197: }
198:
199: if (!nonLocal) {
200: return;
201: }
202:
203: // We've decided that this variable is used in multiple blocks,
204: // so go ahead and place phi functions for it.
205:
206: // Iterate over all of the catch blocks (blocks that begin an
207: // exception handler) in the CFG and instert PhiCatchStmts where
208: // appropriate.
209: final Iterator catchBlocks = cfg.catchBlocks().iterator();
210:
211: while (catchBlocks.hasNext()) {
212: final Block block = (Block) catchBlocks.next();
213: info.addCatchPhi(block);
214: info.addDefBlock(block);
215: }
216:
217: // Iterate over all of the subroutines (finally blocks) and insert
218: // PhiReturnStmts where appropriate.
219: final Iterator subs = cfg.subroutines().iterator();
220:
221: while (subs.hasNext()) {
222: final Subroutine sub = (Subroutine) subs.next();
223: info.addRetPhis(sub);
224:
225: final Iterator paths = sub.paths().iterator();
226:
227: while (paths.hasNext()) {
228: final Block[] path = (Block[]) paths.next();
229: info.addDefBlock(path[1]);
230: }
231: }
232:
233: // Now we add real phi functions to the CFG. Phi functions are
234: // placed at the (blocks in the) iterated dominance fontier of each
235: // of the blocks containing a definition of the variable.
236: final Iterator df = cfg.iteratedDomFrontier(info.defBlocks())
237: .iterator();
238:
239: while (df.hasNext()) {
240: final Block block = (Block) df.next();
241:
242: // Don't place phi-statements in the exit block because one of
243: // the operands will always have a null definition.
244: if (block != cfg.sink()) {
245: info.addPhi(block);
246: }
247: }
248: }
249:
250: /**
251: * If the block resides in a protected region and there is a
252: * <tt>PhiCatchStmt</tt> for the variable in question in the handler of
253: * the exception thrown by the protected region (meaning that the variable
254: * is used in the protected region), the variable becomes an operand to the
255: * <tt>PhiCatchStmt</tt>.
256: *
257: * @param info
258: * The variable (LocalExpr) that we're dealing with
259: * @param block
260: * The block in a potentially protected region. If the block is
261: * indeed in a protected region, the occurrence of the the
262: * variable represented by info becomes an operand to the
263: * PhiCatchStmt at the beginning of the protected region's
264: * handler.
265: * @param def
266: * The defining occurrence of the variable stored in info.
267: */
268: private static void addCatchPhiOperands(
269: final SSAConstructionInfo info, final Block block,
270: final LocalExpr def) {
271: final Iterator handlers = block.graph().handlers().iterator();
272:
273: // Iterate over all of the exception handlers in the CFG. If
274: // the block we are dealing with is a protected block (that is,
275: // is inside a try block), then the variable represented by info
276: // becomes an operand to the PhiCatchStmt residing at the
277: // beginning of the protected block's handler.
278: while (handlers.hasNext()) {
279: final Handler handler = (Handler) handlers.next();
280:
281: if (handler.protectedBlocks().contains(block)) {
282: final PhiCatchStmt phi = (PhiCatchStmt) info
283: .phiAtBlock(handler.catchBlock());
284:
285: if ((phi != null) && !phi.hasOperandDef(def)) {
286: final LocalExpr operand = (LocalExpr) info.prototype
287: .clone();
288: operand.setDef(def); // ???
289: phi.addOperand(operand);
290: }
291: }
292: }
293: }
294:
295: /**
296: * The actual renamining is done by the search method. This method just
297: * takes care of <Tt>PhiReturnStmts</tt>.
298: */
299: private static void rename(final FlowGraph cfg,
300: final SSAConstructionInfo info) {
301: SSA.search(cfg, info, null, cfg.source());
302:
303: // Eliminate PhiReturns by replacing their uses with the defs live
304: // at the end of the returning sub or live on the same path on entry
305: // to the sub (if the variable did not occur in the subroutine).
306:
307: // Examine each PhiReturnStmt in the CFG. Recall that
308: // PhiReturnStmts are "inserted" at blocks that begin exceptions
309: boolean changed = true;
310:
311: while (changed) {
312: changed = false;
313:
314: final Iterator subs = cfg.subroutines().iterator();
315:
316: while (subs.hasNext()) {
317: final Subroutine sub = (Subroutine) subs.next();
318: final Iterator paths = sub.paths().iterator();
319:
320: final PhiJoinStmt entry = (PhiJoinStmt) info
321: .phiAtBlock(sub.entry());
322:
323: if (entry == null) {
324: // If there was no PhiJoinStmt for the variable in the
325: // subroutine, who cares? We don't.
326: continue;
327: }
328:
329: while (paths.hasNext()) {
330: final Block[] path = (Block[]) paths.next();
331:
332: final PhiReturnStmt ret = (PhiReturnStmt) info
333: .phiAtBlock(path[1]);
334:
335: if (ret != null) {
336: DefExpr def = ret.operand().def();
337:
338: if (def != entry.target()) {
339: // If the operand of the PhiReturnStmt is different
340: // from
341: // the new SSA variable defined by the PhiCatchStmt
342: // at
343: // the beginning of the subroutine, then the
344: // variable
345: // was defined in the subroutine, so the operand to
346: // the
347: // PhiReturnStmt is the correct SSA variable. This
348: // is
349: // like the variable "b" in figure 3.5 in Nate's
350: // Thesis.
351: continue;
352: }
353:
354: // Replace all uses of the target of the PhiReturnStmt
355: // with the SSA variable corresponding to the block in
356: // which the jsr occured. This is like variable "a" in
357: // figure 3.5 in Nate's Thesis.
358: def = ((VarExpr) entry.operandAt(path[0]))
359: .def();
360:
361: final Iterator uses = ret.target().uses()
362: .iterator();
363:
364: while (uses.hasNext()) {
365: final VarExpr use = (VarExpr) uses.next();
366: use.setDef(def);
367: }
368:
369: // The PhiReturnStmt is no longer needed
370: info.removePhiAtBlock(path[1]);
371: changed = true;
372: }
373: }
374: }
375: }
376:
377: final Iterator subs = cfg.subroutines().iterator();
378:
379: // Examine any remaining PhiReturnStmts. Replace all uses of the
380: // target of the PhiReturnStmt with its operand.
381: while (subs.hasNext()) {
382: final Subroutine sub = (Subroutine) subs.next();
383:
384: final Iterator paths = sub.paths().iterator();
385:
386: while (paths.hasNext()) {
387: final Block[] path = (Block[]) paths.next();
388:
389: final PhiReturnStmt ret = (PhiReturnStmt) info
390: .phiAtBlock(path[1]);
391:
392: if (ret != null) {
393: final DefExpr def = ret.operand().def();
394:
395: final Iterator uses = ret.target().uses()
396: .iterator();
397:
398: while (uses.hasNext()) {
399: final VarExpr use = (VarExpr) uses.next();
400: use.setDef(def);
401: }
402:
403: info.removePhiAtBlock(path[1]);
404: }
405: }
406: }
407: }
408:
409: /**
410: * Does the actual renaming. It keeps track of the most recent occurrence of
411: * an (SSA numbered) variable and recalculates the definitions of variables
412: * appropriately.
413: *
414: * @param info
415: * SSAConstructionInfo representing the variable being converted
416: * into SSA form.
417: * @param top
418: * "Top" of the variable stack for the variable in question. Each
419: * variable has a "stack" associated with it. The top of the
420: * stack contains the current SSA name of the variable. It can
421: * also be thought of as the "most recent definition" of the
422: * variable.
423: * @param block
424: * Basic block in which the variable is being renamed.
425: */
426: private static void search(final FlowGraph cfg,
427: final SSAConstructionInfo info, VarExpr top,
428: final Block block) {
429: if (SSA.DEBUG) {
430: System.out.println(" renaming " + info.prototype + " in "
431: + block);
432: }
433:
434: // If appropriate, add top as an operand of a PhiCatchStmt
435: if (top instanceof LocalExpr) {
436: SSA.addCatchPhiOperands(info, block, (LocalExpr) top);
437: }
438:
439: // First handle any phi in the block.
440: final PhiStmt phi = info.phiAtBlock(block);
441:
442: if (phi != null) {
443: top = phi.target();
444:
445: if (top instanceof LocalExpr) {
446: SSA.addCatchPhiOperands(info, block, (LocalExpr) top);
447: }
448: }
449:
450: // If the block in which the variable is being renamed begins an
451: // exception handler and we're dealing with a stack variable, then
452: // there is no most recent definition of the variable because the
453: // stack is cleared when an exception is handled. I dunno.
454: if (cfg.catchBlocks().contains(block)
455: && (info.prototype instanceof StackExpr)) {
456:
457: if (SSA.DEBUG) {
458: System.out.println(" Killing TOS at " + block);
459: }
460:
461: // The operand stack is popped down to 0 at catch blocks.
462: top = null;
463: }
464:
465: final Iterator e = info.realsAtBlock(block).iterator();
466:
467: // Examine each occurrence of the variable in the block of
468: // interest. When we encounter a definition of the variable, make
469: // that definition to the most recent SSA variable (top). For
470: // each use, make this most recent SSA variable be its defining
471: // expression.
472: while (e.hasNext()) {
473: final VarExpr real = (VarExpr) e.next();
474:
475: if (real.isDef()) {
476: real.setDef(null);
477:
478: top = real; // A definition means a new SSA variable
479:
480: if (top instanceof LocalExpr) {
481: SSA.addCatchPhiOperands(info, block,
482: (LocalExpr) top);
483: }
484:
485: if (SSA.DEBUG) {
486: System.out.println(" TOS = " + top);
487: }
488:
489: } else {
490: // Make sure that the variable is defined somewhere else
491: // (somewhere that we have already seen).
492: Assert.isTrue(top != null, "Null def for " + real);
493: real.setDef(top);
494: }
495: }
496:
497: final Iterator succs = cfg.succs(block).iterator();
498:
499: // Examine all successors of the block in question. If the
500: // successor contains a PhiJoinStmt for the variable, then set the
501: // operand corresponding to the block to be defined by the most
502: // recent SSA variable. Similarly for a PhiReturnStmt.
503: while (succs.hasNext()) {
504: final Block succ = (Block) succs.next();
505:
506: final PhiStmt succPhi = info.phiAtBlock(succ);
507:
508: if (succPhi instanceof PhiJoinStmt) {
509: final PhiJoinStmt f = (PhiJoinStmt) succPhi;
510: final VarExpr operand = (VarExpr) f.operandAt(block);
511: operand.setDef(top);
512:
513: } else if (succPhi instanceof PhiReturnStmt) {
514: final PhiReturnStmt f = (PhiReturnStmt) succPhi;
515: final VarExpr operand = (VarExpr) f.operand();
516: operand.setDef(top);
517: }
518:
519: // Adjust the operands of any PhiCatchStmts if the sucessor node
520: // is protected.
521: if (top instanceof LocalExpr) {
522: SSA.addCatchPhiOperands(info, succ, (LocalExpr) top);
523: }
524: }
525:
526: final Iterator children = cfg.domChildren(block).iterator();
527:
528: // Visit the children in the dominator tree. Keep the same most
529: // recent SSA variable (top).
530: while (children.hasNext()) {
531: final Block child = (Block) children.next();
532: SSA.search(cfg, info, top, child);
533: }
534: }
535:
536: /**
537: * Iterates over the blocks in the CFG and inserts the phi statement
538: * associated with that block. Up until this point, the phi statement is
539: * only maintained in SSAConstructionInfo. Note that the phi statement
540: * cannot be a return phi.
541: *
542: * @param cfg
543: * The CFG into which to insert phi statements.
544: * @param info
545: * Represents the variable whose phi statements we are inserting.
546: *
547: * @see PhiReturnStmt
548: */
549: private static void insertCode(final FlowGraph cfg,
550: final SSAConstructionInfo info) {
551: final Iterator blocks = cfg.nodes().iterator();
552:
553: while (blocks.hasNext()) {
554: final Block block = (Block) blocks.next();
555:
556: final PhiStmt phi = info.phiAtBlock(block);
557:
558: if (phi != null) {
559: Assert.isFalse(phi instanceof PhiReturnStmt);
560: block.tree().prependStmt(phi);
561: }
562: }
563: }
564: }
|