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: * <tt>SSAConstructionInfo</tt> contains information needed to convert a CFG
031: * into SSA form. Each variable (VarExpr) has an SSAConstructionInfo associated
032: * with it. Each <tt>SSAConstructionInfo</tt> keeps track of information such
033: * as the <tt>PhiStmt</tt>s that define copies of the variable, the
034: * <tt>Block</tt>s in which the variable is defined, and the occurrences
035: * (uses) of the variable in both phi and non-phi statements. Note that no
036: * <tt>PhiStmt</tt> is really inserted into a basic block. We just keep track
037: * of the mapping. It should also be noted that once a phi statement for a given
038: * variable is "inserted" into a block, no other phi statement for that variable
039: * is inserted. Thus, the order of insertion determines the precedence of the
040: * phi statements: <tt>PhiReturnStmt</tt> > <tt>PhiCatchStmt</tt> >
041: * <tt>PhiJoinStmt</tt>.
042: *
043: * <p>
044: *
045: * Additionally, <tt>SSAConstruction</tt> has methods to insert various
046: * flavors of <tt>PhiStmt</tt>s whose targets are the variable associated
047: * with the <tt>SSAConstruction</tt> into <tt>Block</tt>s.
048: *
049: * @see SSA
050: * @see PhiStmt
051: * @see PhiCatchStmt
052: * @see PhiJoinStmt
053: * @see PhiReturnStmt
054: */
055: public class SSAConstructionInfo {
056: FlowGraph cfg; // The cfg we're converting into SSA form
057:
058: VarExpr prototype; // The variable we're converting into SSA form
059:
060: LinkedList[] reals; // The real (non-phi) occurrences associated
061:
062: // with a given node (block)
063: LinkedList allReals; // All the real occurrences of the variable
064:
065: PhiStmt[] phis; // Phi statement associated with a given block
066:
067: Set defBlocks; // Blocks in which variable is defined
068:
069: /**
070: * Constructor.
071: *
072: * @param cfg
073: * The control flow graph that is being converted to SSA form.
074: * @param expr
075: * A variable in the CFG on which SSA analysis is being done.
076: */
077: public SSAConstructionInfo(final FlowGraph cfg, final VarExpr expr) {
078: this .cfg = cfg;
079:
080: prototype = (VarExpr) expr.clone();
081: prototype.setDef(null);
082:
083: reals = new LinkedList[cfg.size()];
084: allReals = new LinkedList();
085:
086: defBlocks = new HashSet();
087:
088: phis = new PhiStmt[cfg.size()];
089: }
090:
091: /**
092: * Returns the program variable associated with this
093: * <tt>SSAConstructionInfo</tt>.
094: */
095: public VarExpr prototype() {
096: return prototype;
097: }
098:
099: /**
100: * Makes note of a <tt>Block</tt> in which the variable is defined by a
101: * <tt>PhiStmt</tt>.
102: */
103: public void addDefBlock(final Block block) {
104: defBlocks.add(block);
105: }
106:
107: /**
108: * Returns the phi statement for the variable represented by this
109: * SSAConstructionInfo at a given block in the CFG.
110: */
111: public PhiStmt phiAtBlock(final Block block) {
112: return phis[cfg.preOrderIndex(block)];
113: }
114:
115: /**
116: * Removes the phi statement for this variable at a given block.
117: */
118: public void removePhiAtBlock(final Block block) {
119: final PhiStmt phi = phis[cfg.preOrderIndex(block)];
120:
121: if (phi != null) {
122: if (SSA.DEBUG) {
123: System.out
124: .println(" removing " + phi + " at " + block);
125: }
126:
127: phi.cleanup();
128: phis[cfg.preOrderIndex(block)] = null;
129: }
130: }
131:
132: /**
133: * Adds a <tt>PhiJoinStmt</tt> for the variable represented by this
134: * <tt>SSAConstructionInfo</tt> to a given <tt>Block</tt>.
135: */
136: public void addPhi(final Block block) {
137: if (phis[cfg.preOrderIndex(block)] != null) {
138: return;
139: }
140:
141: final VarExpr target = (VarExpr) prototype.clone();
142:
143: final PhiJoinStmt phi = new PhiJoinStmt(target, block);
144: phis[cfg.preOrderIndex(block)] = phi;
145:
146: if (SSA.DEBUG) {
147: System.out.println(" place " + phi + " in " + block);
148: }
149: }
150:
151: /**
152: * Adds a <tt>PhiReturnStmt</tt> to all of the <tt>Block</tt>s that are
153: * executed upon returning from a given <tt>Subroutine</tt>.
154: *
155: * @see PhiReturnStmt
156: * @see Subroutine#paths
157: */
158: public void addRetPhis(final Subroutine sub) {
159: final Iterator paths = sub.paths().iterator();
160:
161: while (paths.hasNext()) {
162: final Block[] path = (Block[]) paths.next();
163: addRetPhi(sub, path[1]);
164: }
165: }
166:
167: /**
168: * Inserts a <tt>PhiCatchStmt</tt> (whose target is the variable
169: * represented by this <tt>SSAConstructionInfo</tt>) into a given
170: * <tt>Block</tt>.
171: *
172: * @see PhiCatchStmt
173: */
174: public void addCatchPhi(final Block block) {
175: if (phis[cfg.preOrderIndex(block)] != null) {
176: return;
177: }
178:
179: if (prototype instanceof LocalExpr) {
180: final LocalExpr target = (LocalExpr) prototype.clone();
181:
182: final PhiCatchStmt phi = new PhiCatchStmt(target);
183: phis[cfg.preOrderIndex(block)] = phi;
184:
185: if (SSA.DEBUG) {
186: System.out.println(" place " + phi + " in " + block);
187: }
188: }
189: }
190:
191: /**
192: * Adds a <tt>PhiReturnStmt</tt> associated with a given
193: * <tt>Subroutine</tt>. The <tt>PhiReturnStmt</tt> is placed in a given
194: * block.
195: *
196: * @see PhiReturnStmt
197: */
198: private void addRetPhi(final Subroutine sub, final Block block) {
199: if (phis[cfg.preOrderIndex(block)] != null) {
200: return;
201: }
202:
203: final VarExpr target = (VarExpr) prototype.clone();
204:
205: final PhiReturnStmt phi = new PhiReturnStmt(target, sub);
206: phis[cfg.preOrderIndex(block)] = phi;
207:
208: if (SSA.DEBUG) {
209: System.out.println(" place " + phi + " in " + block);
210: }
211: }
212:
213: /**
214: * Notes a real occurrence (that is, a use that is not an operand to a phi
215: * statement) of the variable represented by this
216: * <tt>SSAConstructionInfo</tt>.
217: *
218: * @see PhiStmt
219: */
220: public void addReal(final VarExpr real) {
221: if (real.stmt() instanceof PhiStmt) {
222: return;
223: }
224:
225: final Block block = real.block();
226:
227: if (real.isDef()) {
228: defBlocks.add(block);
229: }
230:
231: Assert.isTrue(block != null, real + " not in a " + block);
232:
233: LinkedList l = reals[cfg.preOrderIndex(block)];
234:
235: if (l == null) {
236: l = new LinkedList();
237: reals[cfg.preOrderIndex(block)] = l;
238: }
239:
240: l.add(real);
241: allReals.add(real);
242: }
243:
244: /**
245: * Returns all of the real occurrences of this variable.
246: */
247: public Collection reals() {
248: return allReals;
249: }
250:
251: /**
252: * Returns all of the real occurrences of this variable in a given block.
253: */
254: public Collection realsAtBlock(final Block block) {
255: LinkedList l = reals[cfg.preOrderIndex(block)];
256:
257: if (l == null) {
258: l = new LinkedList();
259: reals[cfg.preOrderIndex(block)] = l;
260: }
261:
262: return l;
263: }
264:
265: /**
266: * Returns the Blocks containing a definition of the variable represented by
267: * this SSAConstruction info.
268: */
269: public Collection defBlocks() {
270: return defBlocks;
271: }
272: }
|