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.codegen;
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: * Liveness represents the interference graph of the local variables contained
031: * in a control flow graph.
032: *
033: * When the liveness of two variables overlap each other, the two variables are
034: * said to <i>interfere</i> with each other. The interference graph represents
035: * this relationship between variables. There is an (un-directed) edge between
036: * variables <tt>a</tt> and <tt>b</tt> in the interference graph if variable
037: * <tt>a</tt> interferes with variable <tt>b</tt>.
038: */
039: public class Liveness {
040: public static boolean DEBUG = false;
041:
042: public static boolean UNIQUE = false;
043:
044: public static final boolean BEFORE = false;
045:
046: public static final boolean AFTER = true;
047:
048: FlowGraph cfg;
049:
050: Graph ig;
051:
052: /**
053: * Constructor.
054: *
055: * @param cfg
056: * Control flow graph on which to perform liveness analysis.
057: */
058: public Liveness(final FlowGraph cfg) {
059: this .cfg = cfg;
060: computeIntersections();
061: }
062:
063: /**
064: * Removes a local expression from the interference graph.
065: */
066: public void removeVar(final LocalExpr expr) {
067: ig.removeNode(expr);
068: }
069:
070: /**
071: * Should not be called.
072: */
073: public boolean liveAtUse(final VarExpr isLive, final VarExpr at,
074: final boolean after) {
075: throw new RuntimeException();
076: }
077:
078: /**
079: * Should not be called.
080: */
081: public boolean liveAtStartOfBlock(final VarExpr isLive,
082: final Block block) {
083: throw new RuntimeException();
084: }
085:
086: /**
087: * Should not be called.
088: */
089: public boolean liveAtEndOfBlock(final VarExpr isLive,
090: final Block block) {
091: throw new RuntimeException();
092: }
093:
094: /**
095: * Returns the <tt>LocalExpr</tt>s (variables) that occur in the CFG.
096: * They correspond to nodes in the interference graph.
097: */
098: public Collection defs() {
099: return ig.keySet();
100: }
101:
102: /**
103: * Returns an <tt>Iterator</tt> of <tt>LocalExpr</tt>s that interfere
104: * with a given <tt>VarExpr</tt>.
105: */
106: public Iterator intersections(final VarExpr a) {
107: Assert.isTrue(a != null,
108: "Cannot get intersections for null def");
109: Assert.isTrue(a.isDef(),
110: "Cannot get intersections for variable uses");
111:
112: final GraphNode node = ig.getNode(a);
113:
114: Assert.isTrue(node != null, "Cannot find IG node for " + a);
115:
116: return new Iterator() {
117: Iterator succs = ig.succs(node).iterator();
118:
119: public boolean hasNext() {
120: return succs.hasNext();
121: }
122:
123: public Object next() {
124: final IGNode next = (IGNode) succs.next();
125: return next.def;
126: }
127:
128: public void remove() {
129: throw new RuntimeException();
130: }
131: };
132: }
133:
134: /**
135: * Determines whether or not two variables interfere with one another.
136: */
137: public boolean liveRangesIntersect(final VarExpr a, final VarExpr b) {
138: Assert.isTrue((a != null) && (b != null),
139: "Cannot get intersections for null def");
140: Assert.isTrue(a.isDef() && b.isDef(),
141: "Cannot get intersections for variable uses");
142:
143: if (a == b) {
144: return false;
145: }
146:
147: // If all locals should have unique colors, return true.
148: if (Liveness.UNIQUE) {
149: return true;
150: }
151:
152: final IGNode na = (IGNode) ig.getNode(a);
153: final IGNode nb = (IGNode) ig.getNode(b);
154:
155: Assert.isTrue((na != null) && (nb != null));
156:
157: return ig.hasEdge(na, nb);
158: }
159:
160: /**
161: * Constructs the interference graph.
162: */
163: private void computeIntersections() {
164: ig = new Graph(); // The interference graph
165:
166: if (Liveness.DEBUG) {
167: System.out
168: .println("-----------Computing live ranges-----------");
169: }
170:
171: // All of the nodes (IGNodes) in the IG
172: final List defNodes = new ArrayList();
173:
174: // The IGNodes whose local variable is defined by a PhiCatchStmt
175: final List phiCatchNodes = new ArrayList();
176:
177: // An array of NodeInfo for each node in the CFG (indexed by the
178: // node's pre-order index). Gives information about the local
179: // variables (nodes in the IG) that are defined in each block.
180: // The NodeInfos are stored in reverse order. That is, the
181: // NodeInfo for the final variable occurrence in the block is the
182: // first element in the list.
183: final List[] nodes = new ArrayList[cfg.size()];
184:
185: // We need to keep track of the order of the statements in which
186: // variables occur. There is an entry in nodeIndices for each
187: // block in the CFG. Each entry consists of a mapping between a
188: // statement in which a variable occurs and the number of the
189: // statement (with respect to the other statements in which
190: // variables occur) of interest. This is hard to explain in
191: // words. This numbering comes into play in the liveOut method.
192: final Map[] nodeIndices = new HashMap[cfg.size()];
193:
194: Iterator iter = cfg.nodes().iterator();
195:
196: // Initialize nodes and nodeIndices
197: while (iter.hasNext()) {
198: final Block block = (Block) iter.next();
199: final int blockIndex = cfg.preOrderIndex(block);
200: nodes[blockIndex] = new ArrayList();
201: nodeIndices[blockIndex] = new HashMap();
202: }
203:
204: // Go in trace order. Code generation for phis in the presence of
205: // critical edges depends on it!
206:
207: iter = cfg.trace().iterator();
208:
209: // When performing liveness analysis, we traverse the tree from
210: // the bottom up. That is, we do a REVERSE traversal.
211: while (iter.hasNext()) {
212: final Block block = (Block) iter.next();
213:
214: block.visit(new TreeVisitor(TreeVisitor.REVERSE) {
215: public void visitPhiJoinStmt(final PhiJoinStmt stmt) {
216: if (!(stmt.target() instanceof LocalExpr)) {
217: return;
218: }
219:
220: final LocalExpr target = (LocalExpr) stmt.target();
221:
222: // Examine each predacessor and maintain some information
223: // about the definitions. Remember that we're dealing with
224: // a PhiJoinStmt. The predacessors of PhiJoinStmts are
225: // statements that define or use the local (SSA) variable.
226: final Iterator preds = cfg.preds(block).iterator();
227:
228: while (preds.hasNext()) {
229: final Block pred = (Block) preds.next();
230: final int predIndex = cfg.preOrderIndex(pred);
231:
232: final List n = nodes[predIndex];
233: final Map indices = nodeIndices[predIndex];
234:
235: indices.put(stmt, new Integer(n.size()));
236: final NodeInfo info = new NodeInfo(stmt);
237: n.add(info);
238:
239: // Make a new node in the interference graph for target,
240: // if one does not already exists
241: IGNode node = (IGNode) ig.getNode(target);
242:
243: if (node == null) {
244: node = new IGNode(target);
245: ig.addNode(target, node);
246: defNodes.add(node);
247: }
248:
249: info.defNodes.add(node);
250: }
251: }
252:
253: public void visitPhiCatchStmt(final PhiCatchStmt stmt) {
254: }
255:
256: public void visitStmt(final Stmt stmt) {
257: }
258: });
259: }
260:
261: iter = cfg.trace().iterator();
262:
263: while (iter.hasNext()) {
264: final Block block = (Block) iter.next();
265: final int blockIndex = cfg.preOrderIndex(block);
266:
267: block.visit(new TreeVisitor(TreeVisitor.REVERSE) {
268: Node parent = null;
269:
270: public void visitNode(final Node node) {
271: final Node p = parent;
272: parent = node;
273: node.visitChildren(this );
274: parent = p;
275: }
276:
277: public void visitLocalExpr(final LocalExpr expr) {
278: Assert.isTrue(parent != null);
279:
280: // Recall that a LocalExpr represents a use or a definition
281: // of a local variable. If the LocalExpr is defined by a
282: // PhiJoinStmt, the block in which it resides should already
283: // have some information about it.
284:
285: NodeInfo info;
286:
287: final List n = nodes[blockIndex];
288: final Map indices = nodeIndices[blockIndex];
289:
290: final Integer i = (Integer) indices.get(parent);
291:
292: if (i == null) {
293: if (Liveness.DEBUG) {
294: System.out.println("adding " + parent
295: + " at " + n.size());
296: }
297:
298: indices.put(parent, new Integer(n.size()));
299: info = new NodeInfo(parent);
300: n.add(info);
301:
302: } else {
303: if (Liveness.DEBUG) {
304: System.out.println("found " + parent
305: + " at " + i);
306: }
307:
308: info = (NodeInfo) n.get(i.intValue());
309: Assert.isTrue(info != null);
310: }
311:
312: if (expr.isDef()) {
313: IGNode node = (IGNode) ig.getNode(expr);
314:
315: if (node == null) {
316: node = new IGNode(expr);
317: ig.addNode(expr, node);
318: defNodes.add(node);
319: }
320:
321: info.defNodes.add(node);
322: }
323: }
324:
325: public void visitPhiCatchStmt(final PhiCatchStmt stmt) {
326: NodeInfo info;
327:
328: final List n = nodes[blockIndex];
329: final Map indices = nodeIndices[blockIndex];
330:
331: final Integer i = (Integer) indices.get(stmt);
332:
333: if (i == null) {
334: if (Liveness.DEBUG) {
335: System.out.println("adding " + stmt
336: + " at " + n.size());
337: }
338:
339: indices.put(stmt, new Integer(n.size()));
340: info = new NodeInfo(stmt);
341: n.add(info);
342:
343: } else {
344: if (Liveness.DEBUG) {
345: System.out.println("found " + parent
346: + " at " + i);
347: }
348:
349: info = (NodeInfo) n.get(i.intValue());
350: Assert.isTrue(info != null);
351: }
352:
353: final LocalExpr target = (LocalExpr) stmt.target();
354:
355: IGNode node = (IGNode) ig.getNode(target);
356:
357: if (node == null) {
358: node = new IGNode(target);
359: ig.addNode(target, node);
360: defNodes.add(node);
361: phiCatchNodes.add(node);
362: }
363:
364: info.defNodes.add(node);
365: }
366:
367: public void visitPhiJoinStmt(final PhiJoinStmt stmt) {
368: }
369: });
370: }
371:
372: // Iterate over all of the nodes in the IG
373: final int numDefs = defNodes.size();
374:
375: for (int i = 0; i < numDefs; i++) {
376: final IGNode node = (IGNode) defNodes.get(i);
377: final LocalExpr def = node.def;
378:
379: // Set of blocks where this variable is live out (i.e. live on
380: // any of the block's outgoing edges).
381: final BitSet m = new BitSet(cfg.size());
382:
383: final Iterator uses = def.uses().iterator();
384:
385: // Look at each use of the local variable
386: while (uses.hasNext()) {
387: final LocalExpr use = (LocalExpr) uses.next();
388: Node parent = use.parent();
389:
390: if ((parent instanceof MemRefExpr)
391: && ((MemRefExpr) parent).isDef()) {
392: parent = parent.parent();
393: }
394:
395: // Skip catch-phis. We handle this later.
396: if (parent instanceof PhiCatchStmt) {
397: // If we want to be less conservative:
398: // Need to search back from the operand from all
399: // points in the protected region where it is live
400: // back to the def of the operand. For each block
401: // in protected region, if the operand def is closest
402: // dominator of the block
403: continue;
404: }
405:
406: if (Liveness.DEBUG) {
407: System.out.println("searching for " + def
408: + " from " + parent);
409: }
410:
411: final Block block = parent.block();
412:
413: if (parent instanceof PhiJoinStmt) {
414: final PhiJoinStmt phi = (PhiJoinStmt) parent;
415:
416: // The local variable (LocalExpr) occurs within a
417: // PhiJoinStmt. Look at the predacessors of the
418: // PhiJoinStmt. Recall that each predacessor defines one of
419: // the operands to the PhiJoinStmt. Locate the block that
420: // defines the LocalExpr in question. Call liveOut to
421: // determine for which nodes the LocalExpr is live out.
422:
423: // Examine the predacessors of the block containing the
424: // LocalExpr
425: final Iterator preds = cfg.preds(block).iterator();
426:
427: while (preds.hasNext()) {
428: final Block pred = (Block) preds.next();
429:
430: if (phi.operandAt(pred) == use) {
431: final Map indices = nodeIndices[cfg
432: .preOrderIndex(pred)];
433: final Integer index = (Integer) indices
434: .get(parent);
435: Assert.isTrue(index != null,
436: "No index for " + parent);
437:
438: liveOut(m, nodes, pred, index.intValue(),
439: node, phiCatchNodes);
440: break;
441: }
442: }
443:
444: } else {
445: // The LocalExpr is define in a non-Phi statement. Figure
446: // out which number definition define the LocalExpr in quest
447: // and call liveOut to compute the set of block in which the
448: // LocalExpr is live out.
449:
450: final Map indices = nodeIndices[cfg
451: .preOrderIndex(block)];
452: final Integer index = (Integer) indices.get(parent);
453: Assert.isTrue(index != null, "No index for "
454: + parent);
455:
456: liveOut(m, nodes, block, index.intValue(), node,
457: phiCatchNodes);
458: }
459: }
460: }
461:
462: // Go through all of the variables that are defined by
463: // PhiCatchStmts and make them (the variables) conflict with
464: // everything that the operands of the PhiCatchStmt conflict
465: // with. See liveOut for a discussion.
466:
467: final int numPhiCatches = phiCatchNodes.size();
468:
469: for (int i = 0; i < numPhiCatches; i++) {
470: final IGNode node = (IGNode) phiCatchNodes.get(i);
471:
472: final PhiCatchStmt phi = (PhiCatchStmt) node.def.parent();
473:
474: final Iterator operands = phi.operands().iterator();
475:
476: while (operands.hasNext()) {
477: final LocalExpr operand = (LocalExpr) operands.next();
478: final LocalExpr def = (LocalExpr) operand.def();
479:
480: if (def != null) {
481: final IGNode opNode = (IGNode) ig.getNode(def);
482:
483: // Conflict with everything the operand conflicts with.
484: final Iterator edges = new ImmutableIterator(ig
485: .succs(opNode));
486:
487: while (edges.hasNext()) {
488: final IGNode otherNode = (IGNode) edges.next();
489:
490: if (otherNode != node) {
491: if (Liveness.DEBUG) {
492: System.out.println(otherNode.def
493: + " conflicts with "
494: + opNode.def
495: + " and thus with " + node.def);
496: }
497:
498: ig.addEdge(otherNode, node);
499: ig.addEdge(node, otherNode);
500: }
501: }
502: }
503: }
504: }
505:
506: if (Liveness.DEBUG) {
507: System.out.println("Interference graph =");
508: System.out.println(ig);
509: }
510: }
511:
512: /**
513: * Computes (a portion of) the "live out" set for a given local variable. If
514: * a variable is live on a block's outgoing edge in the CFG, then it is
515: * "live out" at that block.
516: *
517: * @param m
518: * Bit vector that indicates the block for which block the
519: * defNode is live out
520: * @param nodes
521: * The NodeInfo for the local variables used or defined in each
522: * block
523: * @param block
524: * The block in which the LocalExpr of interest is defined
525: * @param nodeIndex
526: * Which number definition in the defining block
527: * @param defNode
528: * The node in the IG whose live out set we are interested in
529: * @param phiCatchNodes
530: * The nodes in the interference graph that represent local
531: * variables defined by PhiCatchStmts
532: */
533: // Nate sez:
534: //
535: // In a PhiJoin pred, add
536: // ...
537: // phi-target := phi-operand
538: // jump with throw succs
539: //
540: // Don't kill Phi targets in protected blocks
541: // The phi target and operand don't conflict
542: void liveOut(final BitSet m, final List[] nodes, Block block,
543: int nodeIndex, final IGNode defNode,
544: final Collection phiCatchNodes) {
545: boolean firstNode = true;
546:
547: int blockIndex = cfg.preOrderIndex(block);
548:
549: final ArrayList stack = new ArrayList();
550:
551: Pos pos = new Pos();
552: pos.block = block;
553: pos.blockIndex = blockIndex;
554: pos.nodeIndex = nodeIndex;
555:
556: stack.add(pos);
557:
558: while (!stack.isEmpty()) {
559: pos = (Pos) stack.remove(stack.size() - 1);
560:
561: block = pos.block;
562: blockIndex = pos.blockIndex;
563: nodeIndex = pos.nodeIndex;
564:
565: if (Liveness.DEBUG) {
566: System.out.println(defNode.def
567: + " is live at position " + nodeIndex + " of "
568: + block);
569: }
570:
571: boolean stop = false;
572:
573: // The nodes are sorted in reverse. So, the below gets all of
574: // the nodes defined at this block after nodeIndex. I believe
575: // this is an optimization so we don't calculate things twice.
576: // Or maybe its how we get things to terminate.
577: final ListIterator iter = nodes[blockIndex]
578: .listIterator(nodeIndex);
579:
580: while (!stop && iter.hasNext()) {
581: final NodeInfo info = (NodeInfo) iter.next();
582:
583: if (Liveness.DEBUG) {
584: System.out.println(defNode.def + " is live at "
585: + info.node);
586: }
587:
588: if (firstNode) {
589: // We don't care about the definition in the block that
590: // defines the LocalExpr of interest.
591: firstNode = false;
592: continue;
593: }
594:
595: // Look at all (?) of the definitions of the LocalExpr
596: final Iterator e = info.defNodes.iterator();
597:
598: while (e.hasNext()) {
599: final IGNode node = (IGNode) e.next();
600:
601: final Iterator catchPhis = phiCatchNodes.iterator();
602:
603: // Calculating the live region of the target of a phi-catch
604: // node is a little tricky. The target (variable) must be
605: // live throughout the protected region as well as after the
606: // PhiCatchStmt (its definition). However, we do not want
607: // the phi-catch target to conflict (interfere) with any of
608: // its operands. So, we make the target conflict with all
609: // of the variables that its operand conflict with. See
610: // page 37 of Nate's Thesis.
611:
612: PHIS: while (catchPhis.hasNext()) {
613: final IGNode catchNode = (IGNode) catchPhis
614: .next();
615:
616: final PhiCatchStmt phi = (PhiCatchStmt) catchNode.def
617: .parent();
618:
619: final Handler handler = (Handler) cfg
620: .handlersMap().get(phi.block());
621:
622: Assert.isTrue(handler != null,
623: "Null handler for " + phi.block());
624:
625: if (handler.protectedBlocks().contains(block)) {
626: final Iterator operands = phi.operands()
627: .iterator();
628:
629: // If the block containing the LocalExpr in question
630: // resides inside a protected region. Make sure that
631: // the LocalExpr is not one of the operands to the
632: // PhiCatchStmt associated with the protected
633: // region.
634:
635: while (operands.hasNext()) {
636: final LocalExpr expr = (LocalExpr) operands
637: .next();
638:
639: if (expr.def() == node.def) {
640: continue PHIS;
641: }
642: }
643:
644: if (Liveness.DEBUG) {
645: System.out
646: .println(defNode.def
647: + " conflicts with "
648: + node.def);
649: }
650:
651: // Hey, wow. The variable defined in the phi-catch
652: // interferes with the variable from the worklist.
653: ig.addEdge(node, catchNode);
654: ig.addEdge(catchNode, node);
655: }
656: }
657:
658: if (node != defNode) {
659: if (Liveness.DEBUG) {
660: System.out.println(defNode.def
661: + " conflicts with " + node.def);
662: }
663:
664: // If the node in the worklist is not the node we
665: // started
666: // with, then they conflict.
667: ig.addEdge(node, defNode);
668: ig.addEdge(defNode, node);
669:
670: } else {
671: if (Liveness.DEBUG) {
672: System.out
673: .println("def found stopping search");
674: }
675:
676: // We've come across a definition of the LocalExpr in
677: // question, so we don't need to do any more.
678: stop = true;
679: }
680: }
681: }
682:
683: if (!stop) {
684: // Propagate the liveness to each of the predacessors of the
685: // block in which the variable of interest is defined. This
686: // is accomplished by setting the appropriate bit in m. We
687: // also add another Pos to the worklist to work on the
688: // predacessor block.
689: final Iterator preds = cfg.preds(block).iterator();
690:
691: while (preds.hasNext()) {
692: final Block pred = (Block) preds.next();
693: final int predIndex = cfg.preOrderIndex(pred);
694:
695: if (Liveness.DEBUG) {
696: System.out.println(defNode.def
697: + " is live at end of " + pred);
698: }
699:
700: if (!m.get(predIndex)) {
701: pos = new Pos();
702: pos.block = pred;
703: pos.blockIndex = predIndex;
704:
705: // Look at all of the statements in which a variable
706: // occur
707: pos.nodeIndex = 0;
708:
709: m.set(predIndex);
710: stack.add(pos);
711: }
712: }
713: }
714: }
715: }
716:
717: /**
718: * Represents a node in the interference graph. Connected nodes in the
719: * interference graph interfere with each other. That is, their live regions
720: */
721: class IGNode extends GraphNode {
722: LocalExpr def;
723:
724: /**
725: * Constructor.
726: *
727: * @param def
728: * The local variable represented by this node.
729: */
730: public IGNode(final LocalExpr def) {
731: this .def = def;
732: }
733:
734: public String toString() {
735: return def.toString();
736: }
737: }
738:
739: /**
740: * Stores information about each Node in an expression tree (!) that defines
741: * a local variable (i.e. PhiJoinStmt, PhiCatchStmt, and the parent of a
742: * LocalExpr).
743: */
744: class NodeInfo {
745: Node node; // Node in an expression tree in which a variable occurs
746:
747: List defNodes; // node(s) in IG that define above Node
748:
749: public NodeInfo(final Node node) {
750: this .node = node;
751: defNodes = new ArrayList();
752: }
753: }
754:
755: class Key {
756: int blockIndex;
757:
758: Node node;
759:
760: public Key(final Node node, final int blockIndex) {
761: this .blockIndex = blockIndex;
762: this .node = node;
763: }
764:
765: public int hashCode() {
766: return node.hashCode() ^ blockIndex;
767: }
768:
769: public boolean equals(final Object obj) {
770: if (obj instanceof Key) {
771: final Key key = (Key) obj;
772: return (key.node == node)
773: && (key.blockIndex == blockIndex);
774: }
775:
776: return false;
777: }
778: }
779:
780: /**
781: * A Pos is an element in the worklist used to determine the live out set of
782: * a given LocalExpr. It consists of the block in which a local variable
783: * definition occurs, the block's index (i.e. pre-order traversal number) in
784: * the CFG, and the number of the definition in the block that defines the
785: * LocalExpr of interest.
786: */
787: class Pos {
788: Block block;
789:
790: int blockIndex;
791:
792: int nodeIndex;
793: }
794: }
|