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.editor.*;
027: import EDU.purdue.cs.bloat.tree.*;
028: import EDU.purdue.cs.bloat.util.*;
029:
030: /**
031: * RegisterAllocator performs analysis on a control flow graph and determines
032: * the minimum amount of local variables needed in a method.
033: *
034: * @see LocalVariable
035: */
036: // Note that RegisterAllocator uses a different IGNode from Liveness!
037: public class RegisterAllocator {
038: FlowGraph cfg;
039:
040: Liveness liveness;
041:
042: Map colors;
043:
044: int colorsUsed;
045:
046: final static float MAX_WEIGHT = Float.MAX_VALUE;
047:
048: final static float LOOP_FACTOR = 10.0F;
049:
050: final static int MAX_DEPTH = (int) (Math
051: .log(RegisterAllocator.MAX_WEIGHT) / Math
052: .log(RegisterAllocator.LOOP_FACTOR));
053:
054: /**
055: * Constructor. Builds an interference graph based on the expression nodes
056: * found in liveness. Traverses the graph and determines which nodes needs
057: * to be precolored and which nodes can be coalesced (move statements).
058: * Nodes are coalesced and local variables are assigned to expressions.
059: *
060: * @see FlowGraph
061: * @see LocalVariable
062: */
063: public RegisterAllocator(final FlowGraph cfg,
064: final Liveness liveness) {
065: this .cfg = cfg;
066: this .liveness = liveness;
067: colorsUsed = 0;
068: colors = new HashMap();
069:
070: // Construct the interference graph.
071: final Graph ig = new Graph();
072:
073: Iterator iter = liveness.defs().iterator();
074:
075: while (iter.hasNext()) {
076: final VarExpr def = (VarExpr) iter.next();
077:
078: if (!(def instanceof LocalExpr)) {
079: // Ignore node in the Liveness IG that are not LocalExprs
080: continue;
081: }
082:
083: // Create a new node in the IG, if one does not already exist
084: IGNode defNode = (IGNode) ig.getNode(def);
085:
086: if (defNode == null) {
087: defNode = new IGNode((LocalExpr) def);
088: ig.addNode(def, defNode);
089: }
090:
091: // Examine each variable that interferes with def
092: final Iterator intersections = liveness.intersections(def);
093:
094: while (intersections.hasNext()) {
095: final VarExpr expr = (VarExpr) intersections.next();
096:
097: if (expr == def) {
098: // If for some reason, def interferes with itself, ignore it
099: continue;
100: }
101:
102: // Add an edge in RegisterAllocator's IG between the variables
103: // that interfere
104: if (expr instanceof LocalExpr) {
105: IGNode node = (IGNode) ig.getNode(expr);
106:
107: if (node == null) {
108: node = new IGNode((LocalExpr) expr);
109: ig.addNode(expr, node);
110: }
111:
112: ig.addEdge(defNode, node);
113: ig.addEdge(node, defNode);
114: }
115: }
116: }
117:
118: // Arrays of expressions that invovle a copy of one local variable
119: // to another. Expressions invovled in copies (i.e. "moves") can
120: // be coalesced into one expression.
121: final ArrayList copies = new ArrayList();
122:
123: // Nodes that are the targets of InitStmt are considered to be
124: // precolored.
125: final ArrayList precolor = new ArrayList();
126:
127: cfg.visit(new TreeVisitor() {
128: public void visitBlock(final Block block) {
129: // Don't visit the sink block. There's nothing interesting
130: // there.
131: if (block != RegisterAllocator.this .cfg.sink()) {
132: block.visitChildren(this );
133: }
134: }
135:
136: public void visitPhiStmt(final PhiStmt stmt) {
137: stmt.visitChildren(this );
138:
139: if (!(stmt.target() instanceof LocalExpr)) {
140: return;
141: }
142:
143: // A PhiStmt invovles an assignment (copy). So note the copy
144: // between the target and all of the PhiStmt's operands in the
145: // copies list.
146:
147: final IGNode lnode = (IGNode) ig.getNode(stmt.target());
148:
149: final HashSet set = new HashSet();
150:
151: final Iterator e = stmt.operands().iterator();
152:
153: while (e.hasNext()) {
154: final Expr op = (Expr) e.next();
155:
156: if ((op instanceof LocalExpr) && (op.def() != null)) {
157: if (!set.contains(op.def())) {
158: set.add(op.def());
159:
160: if (op.def() != stmt.target()) {
161: final IGNode rnode = (IGNode) ig
162: .getNode(op.def());
163: copies
164: .add(new IGNode[] { lnode,
165: rnode });
166: }
167: }
168: }
169: }
170: }
171:
172: public void visitStoreExpr(final StoreExpr expr) {
173: expr.visitChildren(this );
174:
175: if (!(expr.target() instanceof LocalExpr)) {
176: return;
177: }
178:
179: final IGNode lnode = (IGNode) ig.getNode(expr.target());
180:
181: if ((expr.expr() instanceof LocalExpr)
182: && (expr.expr().def() != null)) {
183:
184: // A store of a variable into another variable is a copy
185: final IGNode rnode = (IGNode) ig.getNode(expr
186: .expr().def());
187: copies.add(new IGNode[] { lnode, rnode });
188: return;
189: }
190:
191: // Treat L := L + k as a copy so that they get converted
192: // back to iincs.
193: if (expr.target().type().equals(Type.INTEGER)) {
194: if (!(expr.expr() instanceof ArithExpr)) {
195: return;
196: }
197:
198: // We're dealing with integer arithmetic. Remember that an
199: // ArithExpr has a left and a right operand. If one of the
200: // operands is a variable and if the other is a constant and
201: // the operation is addition or substraction, we have an
202: // increment.
203:
204: final ArithExpr rhs = (ArithExpr) expr.expr();
205: LocalExpr var = null;
206:
207: Integer value = null;
208:
209: if ((rhs.left() instanceof LocalExpr)
210: && (rhs.right() instanceof ConstantExpr)) {
211:
212: var = (LocalExpr) rhs.left();
213:
214: final ConstantExpr c = (ConstantExpr) rhs
215: .right();
216:
217: if (c.value() instanceof Integer) {
218: value = (Integer) c.value();
219: }
220:
221: } else if ((rhs.right() instanceof LocalExpr)
222: && (rhs.left() instanceof ConstantExpr)) {
223:
224: var = (LocalExpr) rhs.right();
225:
226: final ConstantExpr c = (ConstantExpr) rhs
227: .left();
228:
229: if (c.value() instanceof Integer) {
230: value = (Integer) c.value();
231: }
232: }
233:
234: if (rhs.operation() == ArithExpr.SUB) {
235: if (value != null) {
236: value = new Integer(-value.intValue());
237: }
238:
239: } else if (rhs.operation() != ArithExpr.ADD) {
240: value = null;
241: }
242:
243: if ((value != null) && (var.def() != null)) {
244: final int incr = value.intValue();
245:
246: if ((short) incr == incr) {
247: // Only generate an iinc if the increment
248: // fits in a short
249: final IGNode rnode = (IGNode) ig
250: .getNode(var.def());
251: copies.add(new IGNode[] { lnode, rnode });
252: }
253: }
254: }
255: }
256:
257: public void visitInitStmt(final InitStmt stmt) {
258: stmt.visitChildren(this );
259:
260: // The initialized variables are precolored.
261: final LocalExpr[] t = stmt.targets();
262:
263: for (int i = 0; i < t.length; i++) {
264: precolor.add(t[i]);
265: }
266: }
267: });
268:
269: // Coalesce move related nodes, maximum weight first.
270: while (copies.size() > 0) {
271: // We want the copy (v <- w) with the maximum:
272: // weight(v) + weight(w)
273: // ---------------------
274: // size(union)
275: // where union is the intersection of the nodes that conflict
276: // with v and the nodes that conflict with w. This equation
277: // appears to be in conflict with the one given on page 38 of
278: // Nate's thesis.
279:
280: HashSet union; // The union of neighboring nodes
281:
282: int max = 0;
283:
284: IGNode[] copy = (IGNode[]) copies.get(max);
285:
286: float maxWeight = copy[0].weight + copy[1].weight;
287: union = new HashSet();
288: union.addAll(ig.succs(copy[0]));
289: union.addAll(ig.succs(copy[1]));
290: maxWeight /= union.size();
291:
292: for (int i = 1; i < copies.size(); i++) {
293: copy = (IGNode[]) copies.get(i);
294:
295: float weight = copy[0].weight + copy[1].weight;
296: union.clear();
297: union.addAll(ig.succs(copy[0]));
298: union.addAll(ig.succs(copy[1]));
299: weight /= union.size();
300:
301: if (weight > maxWeight) {
302: // The ith copy has the maximum weight
303: maxWeight = weight;
304: max = i;
305: }
306: }
307:
308: // Remove the copy with the max weight from the copies list. He
309: // does it in a rather round-about way.
310: copy = (IGNode[]) copies.get(max);
311: copies.set(max, copies.get(copies.size() - 1));
312: copies.remove(copies.size() - 1);
313:
314: if (!ig.hasEdge(copy[0], copy[1])) {
315: // If the variables involved in the copy do not interfere with
316: // each other, they are coalesced.
317:
318: if (CodeGenerator.DEBUG) {
319: System.out.println("coalescing " + copy[0] + " "
320: + copy[1]);
321: System.out.println(" 0 conflicts "
322: + ig.succs(copy[0]));
323: System.out.println(" 1 conflicts "
324: + ig.succs(copy[1]));
325: }
326:
327: ig.succs(copy[0]).addAll(ig.succs(copy[1]));
328: ig.preds(copy[0]).addAll(ig.preds(copy[1]));
329:
330: copy[0].coalesce(copy[1]);
331:
332: if (CodeGenerator.DEBUG) {
333: System.out.println(" coalesced " + copy[0]);
334: System.out.println(" conflicts "
335: + ig.succs(copy[0]));
336: }
337:
338: // Remove coalesced node from the IG
339: ig.removeNode(copy[1].key);
340:
341: iter = copies.iterator();
342:
343: // Examine all copies. If the copy involves the node that was
344: // coalesced, the copy is no longer interesting. Remove it.
345: while (iter.hasNext()) {
346: final IGNode[] c = (IGNode[]) iter.next();
347:
348: if ((c[0] == copy[1]) || (c[1] == copy[1])) {
349: iter.remove();
350: }
351: }
352: }
353: }
354:
355: // Create a list of uncolored nodes.
356: final ArrayList uncoloredNodes = new ArrayList();
357:
358: Iterator nodes = ig.nodes().iterator();
359:
360: while (nodes.hasNext()) {
361: final IGNode node = (IGNode) nodes.next();
362:
363: final ArrayList p = new ArrayList(precolor);
364: p.retainAll(node.defs);
365:
366: // See if any node got coalesced with a precolored node.
367: if (p.size() == 1) {
368: // Precolored
369: node.color = ((LocalExpr) p.get(0)).index();
370:
371: if (CodeGenerator.DEBUG) {
372: System.out.println("precolored " + node + " "
373: + node.color);
374: }
375:
376: } else if (p.size() == 0) {
377: // Uncolored (i.e. not coalesced with any of the pre-colored
378: // nodes.
379: node.color = -1;
380: uncoloredNodes.add(node);
381:
382: } else {
383: // If two or more pre-colored nodes were coalesced, we have a
384: // problem.
385: throw new RuntimeException(
386: "coalesced pre-colored defs " + p);
387: }
388: }
389:
390: // Sort the uncolored nodes, by decreasing weight. Wide nodes
391: // have half their original weight since they take up two indices
392: // and we want to put color nodes with the lower indices.
393:
394: Collections.sort(uncoloredNodes, new Comparator() {
395: public int compare(final Object a, final Object b) {
396: final IGNode na = (IGNode) a;
397: final IGNode nb = (IGNode) b;
398:
399: float wa = na.weight / ig.succs(na).size();
400: float wb = nb.weight / ig.succs(nb).size();
401:
402: if (na.wide) {
403: wa /= 2;
404: }
405:
406: if (nb.wide) {
407: wb /= 2;
408: }
409:
410: if (wb > wa) {
411: return 1;
412: }
413:
414: if (wb < wa) {
415: return -1;
416: }
417:
418: return 0;
419: }
420: });
421:
422: nodes = uncoloredNodes.iterator();
423:
424: while (nodes.hasNext()) {
425: final IGNode node = (IGNode) nodes.next();
426:
427: if (CodeGenerator.DEBUG) {
428: System.out.println("coloring " + node);
429: System.out.println(" conflicts " + ig.succs(node));
430: }
431:
432: // Make sure node has not been colored
433: Assert.isTrue(node.color == -1);
434:
435: // Determine which colors have been assigned to the nodes
436: // conflicting with the node of interest
437: final BitSet used = new BitSet();
438:
439: final Iterator succs = ig.succs(node).iterator();
440:
441: while (succs.hasNext()) {
442: final IGNode succ = (IGNode) succs.next();
443:
444: if (succ.color != -1) {
445: used.set(succ.color);
446:
447: if (succ.wide) {
448: used.set(succ.color + 1);
449: }
450: }
451: }
452:
453: // Find the next available color
454: for (int i = 0; node.color == -1; i++) {
455: if (!used.get(i)) {
456: if (node.wide) {
457: // Wide variables need two colors
458: if (!used.get(i + 1)) {
459: node.color = i;
460:
461: if (CodeGenerator.DEBUG) {
462: System.out
463: .println(" assigning color "
464: + i + " to " + node);
465: }
466:
467: if (i + 1 >= colorsUsed) {
468: colorsUsed = i + 2;
469: }
470: }
471:
472: } else {
473: node.color = i;
474:
475: if (CodeGenerator.DEBUG) {
476: System.out.println(" assigning color "
477: + i + " to " + node);
478: }
479:
480: if (i >= colorsUsed) {
481: colorsUsed = i + 1;
482: }
483: }
484: }
485: }
486: }
487:
488: nodes = ig.nodes().iterator();
489:
490: while (nodes.hasNext()) {
491: final IGNode node = (IGNode) nodes.next();
492:
493: // Make sure each node has been colored
494: Assert.isTrue(node.color != -1, "No color for " + node);
495:
496: iter = node.defs.iterator();
497:
498: // Set the index of the variable and all of its uses to be the
499: // chosen color.
500: while (iter.hasNext()) {
501: final LocalExpr def = (LocalExpr) iter.next();
502: def.setIndex(node.color);
503:
504: final Iterator uses = def.uses().iterator();
505:
506: while (uses.hasNext()) {
507: final LocalExpr use = (LocalExpr) uses.next();
508: use.setIndex(node.color);
509: }
510: }
511: }
512:
513: if (CodeGenerator.DEBUG) {
514: System.out
515: .println("After allocating locals--------------------");
516: cfg.print(System.out);
517: System.out
518: .println("End print----------------------------------");
519: }
520: }
521:
522: /**
523: * Returns the maximum number of local variables used by the cfg after its
524: * "registers" (local variables) have been allocated.
525: */
526: public int maxLocals() {
527: return colorsUsed;
528: }
529:
530: /**
531: * Creates a new local variable in this method (as modeled by the cfg).
532: * Updates the number of local variables appropriately.
533: */
534: public LocalVariable newLocal(final Type type) {
535: // Why don't we add Type information to the LocalVariable? Are we
536: // assuming that type checking has already been done and so its a
537: // moot point?
538:
539: final LocalVariable var = new LocalVariable(colorsUsed);
540: colorsUsed += type.stackHeight();
541: return var;
542: }
543:
544: /**
545: * IGNode is a node in the interference graph. Note that this node is
546: * different from the one in Liveness. For instance, this one stores
547: * information about a node's color, its weight, etc. Because nodes may be
548: * coalesced, an IGNode may represent more than one LocalExpr. That's why
549: * there is a list of definitions.
550: */
551: class IGNode extends GraphNode {
552: Set defs;
553:
554: LocalExpr key;
555:
556: int color;
557:
558: boolean wide; // Is the variable wide?
559:
560: float weight;
561:
562: public IGNode(final LocalExpr def) {
563: color = -1;
564: key = def;
565: defs = new HashSet();
566: defs.add(def);
567: wide = def.type().isWide();
568: computeWeight();
569: }
570:
571: /**
572: * Coalesce two nodes in the interference graph. The weight of the other
573: * node is added to that of this node. This node also inherits all of
574: * the definitions of the other node.
575: */
576: void coalesce(final IGNode node) {
577: Assert.isTrue(wide == node.wide);
578:
579: weight += node.weight;
580:
581: final Iterator iter = node.defs.iterator();
582:
583: while (iter.hasNext()) {
584: final LocalExpr def = (LocalExpr) iter.next();
585: defs.add(def);
586: }
587: }
588:
589: public String toString() {
590: return "(color=" + color + " weight=" + weight + " "
591: + defs.toString() + ")";
592: }
593:
594: /**
595: * Calculates the weight of a Block based on its loop depth. If the
596: * block does not exceed the MAX_DEPTH, then the weight is LOOP_FACTOR
597: * raised to the depth.
598: */
599: private float blockWeight(final Block block) {
600: int depth = cfg.loopDepth(block);
601:
602: if (depth > RegisterAllocator.MAX_DEPTH) {
603: return RegisterAllocator.MAX_WEIGHT;
604: }
605:
606: float w = 1.0F;
607:
608: while (depth-- > 0) {
609: w *= RegisterAllocator.LOOP_FACTOR;
610: }
611:
612: return w;
613: }
614:
615: /**
616: * Computes the weight of a node in the interference graph. The weight
617: * is based on where the variable represented by this node is used. The
618: * method blockWeight is used to determine the weight of a variable used
619: * in a block based on the loop depth of the block. Special care must be
620: * taken if the variable is used in a PhiStmt.
621: */
622: private void computeWeight() {
623: weight = 0.0F;
624:
625: final Iterator iter = defs.iterator();
626:
627: // Look at all(?) of the definitions of the IGNode
628: while (iter.hasNext()) {
629: final LocalExpr def = (LocalExpr) iter.next();
630:
631: weight += blockWeight(def.block());
632:
633: final Iterator uses = def.uses().iterator();
634:
635: // If the variable is used as an operand to a PhiJoinStmt,
636: // find the predacessor block to the PhiJoinStmt in which the
637: // variable occurs and add the weight of that block to the
638: // running total weight.
639: while (uses.hasNext()) {
640: final LocalExpr use = (LocalExpr) uses.next();
641:
642: if (use.parent() instanceof PhiJoinStmt) {
643: final PhiJoinStmt phi = (PhiJoinStmt) use
644: .parent();
645:
646: final Iterator preds = cfg.preds(phi.block())
647: .iterator();
648:
649: while (preds.hasNext()) {
650: final Block pred = (Block) preds.next();
651: final Expr op = phi.operandAt(pred);
652:
653: if (use == op) {
654: weight += blockWeight(pred);
655: break;
656: }
657: }
658:
659: } else if (use.parent() instanceof PhiCatchStmt) {
660: // If the variable is used in a PhiCatchStmt, add the
661: // weight of the block in which the variable is defined
662: // to
663: // the running total.
664: weight += blockWeight(use.def().block());
665:
666: } else {
667: // Just add in the weight of the block in which the
668: // variable is used.
669: weight += blockWeight(use.block());
670: }
671: }
672: }
673: }
674: }
675: }
|