001 /*
002 * This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 * This file is licensed to You under the Eclipse Public License (EPL);
005 * You may not use this file except in compliance with the License. You
006 * may obtain a copy of the License at
007 *
008 * http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 * See the COPYRIGHT.txt file distributed with this work for information
011 * regarding copyright ownership.
012 */
013 package org.jikesrvm.compilers.opt.lir2mir;
014
015 import java.util.Enumeration;
016
017 import org.jikesrvm.ArchitectureSpecificOpt.BURS_Debug;
018 import org.jikesrvm.ArchitectureSpecificOpt.BURS_STATE;
019 import org.jikesrvm.ArchitectureSpecificOpt.BURS_TreeNode;
020 import org.jikesrvm.VM;
021 import org.jikesrvm.compilers.opt.OptimizingCompilerException;
022 import org.jikesrvm.compilers.opt.depgraph.DepGraph;
023 import org.jikesrvm.compilers.opt.depgraph.DepGraphEdge;
024 import org.jikesrvm.compilers.opt.depgraph.DepGraphNode;
025 import org.jikesrvm.compilers.opt.ir.IR;
026 import org.jikesrvm.compilers.opt.ir.Instruction;
027 import static org.jikesrvm.compilers.opt.ir.Operators.CALL_opcode;
028 import static org.jikesrvm.compilers.opt.ir.Operators.GUARD_COMBINE;
029 import static org.jikesrvm.compilers.opt.ir.Operators.GUARD_COND_MOVE;
030 import static org.jikesrvm.compilers.opt.ir.Operators.GUARD_MOVE;
031 import static org.jikesrvm.compilers.opt.ir.Operators.IR_PROLOGUE;
032 import static org.jikesrvm.compilers.opt.ir.Operators.OTHER_OPERAND_opcode;
033 import static org.jikesrvm.compilers.opt.ir.Operators.RETURN_opcode;
034 import static org.jikesrvm.compilers.opt.ir.Operators.SYSCALL_opcode;
035 import static org.jikesrvm.compilers.opt.ir.Operators.YIELDPOINT_OSR_opcode;
036 import org.jikesrvm.compilers.opt.ir.ResultCarrier;
037 import org.jikesrvm.compilers.opt.ir.operand.AddressConstantOperand;
038 import org.jikesrvm.compilers.opt.ir.operand.BranchOperand;
039 import org.jikesrvm.compilers.opt.ir.operand.InlinedOsrTypeInfoOperand;
040 import org.jikesrvm.compilers.opt.ir.operand.IntConstantOperand;
041 import org.jikesrvm.compilers.opt.ir.operand.LongConstantOperand;
042 import org.jikesrvm.compilers.opt.ir.operand.Operand;
043 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
044 import org.jikesrvm.compilers.opt.util.SpaceEffGraphEdge;
045 import org.jikesrvm.compilers.opt.util.SpaceEffGraphNode;
046
047 /**
048 * This class contains methods for invoking BURS tree-pattern matching
049 * from the OPT Compiler. BURS is invoked on trees obtained from the
050 * dependence graph of a basic block.
051 *
052 * @see DepGraph
053 * @see BURS_STATE
054 * @see BURS_TreeNode
055 */
056 final class NormalBURS extends BURS {
057
058 private int numTreeRoots;
059
060 /**
061 * Create a BURS object for the given IR.
062 *
063 * @param ir the IR to translate from LIR to MIR.
064 */
065 NormalBURS(IR ir) {
066 super(ir);
067 }
068
069 /**
070 * Build BURS trees for dependence graph dg, label the trees, and
071 * then generate MIR instructions based on the labeling.
072 * @param dg the dependence graph.
073 */
074 public void invoke(DepGraph dg) {
075 if (DEBUG) dg.printDepGraph();
076 BURS_STATE burs = new BURS_STATE(this);
077 buildTrees(dg);
078 if (haveProblemEdges()) {
079 problemEdgePrep();
080 handleProblemEdges();
081 }
082 orderTrees(dg);
083 labelTrees(burs);
084 generateTrees(burs);
085 }
086
087 ////////////////////////////////
088 // Implementation
089 ////////////////////////////////
090
091 /**
092 * Stage 1: Complete the expression trees and identify tree roots.
093 * Complete BURS trees by adding leaf nodes as needed, and
094 * creating tree edges by calling insertChild1() or insertChild2()
095 * This step is also where we introduce intermediate tree nodes for
096 * any LIR instruction that has > 2 "real" operands e.g., a CALL.
097 * We also mark nodes that must be tree roots.
098 *
099 * @param dg The dependence graph.
100 */
101 private void buildTrees(DepGraph dg) {
102 DepGraphNode bbNodes = (DepGraphNode) dg.firstNode();
103 for (DepGraphNode n = bbNodes; n != null; n = (DepGraphNode) n.getNext()) {
104 // Initialize n.treeNode
105 BURS_TreeNode cur_parent = new BURS_TreeNode(n);
106 n.scratchObject = cur_parent;
107 Instruction instr = n.instruction();
108 // cur_parent = current parent node for var length IR instructions
109 // loop for USES of an instruction
110 for (Enumeration<Operand> uses = instr.getUses(); uses.hasMoreElements();) {
111 // Create tree edge for next use.
112 Operand op = uses.nextElement();
113 if (op == null) continue;
114
115 // Set child = BURS_TreeNode for operand op
116 BURS_TreeNode child;
117 if (op instanceof RegisterOperand) {
118 RegisterOperand regOp = (RegisterOperand) op;
119 // ignore validation registers
120 if (regOp.getRegister().isValidation()) continue;
121 DepGraphEdge e = DepGraphEdge.findInputEdge(n, op);
122 if (e == null) { // operand is leaf
123 child = Register;
124 } else {
125 child = (BURS_TreeNode) e.fromNode().scratchObject;
126 }
127 } else if (op instanceof IntConstantOperand) {
128 child = new BURS_IntConstantTreeNode(((IntConstantOperand) op).value);
129 } else if (op instanceof LongConstantOperand) {
130 child = LongConstant;
131 } else if (op instanceof AddressConstantOperand) {
132 child = AddressConstant;
133 } else if (op instanceof BranchOperand && instr.isCall()) {
134 child = BranchTarget;
135 } else if (op instanceof InlinedOsrTypeInfoOperand && instr.isYieldPoint()) {
136 child = NullTreeNode;
137 } else {
138 continue;
139 }
140
141 // Attach child as child of cur_parent in correct position
142 if (cur_parent.child1 == null) {
143 cur_parent.child1 = child;
144 } else if (cur_parent.child2 == null) {
145 cur_parent.child2 = child;
146 } else {
147 // Create auxiliary node so as to represent
148 // a instruction with arity > 2 in a binary tree.
149 BURS_TreeNode child1 = cur_parent.child2;
150 BURS_TreeNode aux = new BURS_TreeNode(OTHER_OPERAND_opcode);
151 cur_parent.child2 = aux;
152 cur_parent = aux;
153 cur_parent.child1 = child1;
154 cur_parent.child2 = child;
155 }
156 } // for (uses = ...)
157
158 // patch for calls & return
159 switch (instr.getOpcode()) {
160 case CALL_opcode:
161 case SYSCALL_opcode:
162 case YIELDPOINT_OSR_opcode:
163 if (cur_parent.child2 == null) {
164 cur_parent.child2 = NullTreeNode;
165 }
166 // fall through
167 case RETURN_opcode:
168 if (cur_parent.child1 == null) {
169 cur_parent.child1 = NullTreeNode;
170 }
171 }
172
173 if (mustBeTreeRoot(n)) {
174 makeTreeRoot((BURS_TreeNode) n.scratchObject);
175 }
176 }
177 }
178
179 /**
180 * Stage 1b: Do bookkeeping to make it easier to identify
181 * harmless problem edges.
182 */
183 private void problemEdgePrep() {
184 for (int i = 0; i < numTreeRoots; i++) {
185 BURS_TreeNode n = treeRoots[i];
186 problemEdgePrep(n, n.dg_node);
187 }
188 }
189
190 private void problemEdgePrep(BURS_TreeNode n, SpaceEffGraphNode root) {
191 BURS_TreeNode child1 = n.child1;
192 BURS_TreeNode child2 = n.child2;
193 if (child1 != null && !child1.isTreeRoot()) {
194 problemEdgePrep(child1, root);
195 }
196 if (child2 != null && !child2.isTreeRoot()) {
197 problemEdgePrep(child2, root);
198 }
199 if (n.dg_node != null) {
200 n.dg_node.nextSorted = root;
201 n.dg_node.scratch = 0;
202 }
203 }
204
205 /**
206 * Stage 1c: Mark src node of some problem edges as tree roots to avoid
207 * cyclic dependencies.
208 */
209 private void handleProblemEdges() {
210 // Stage 1: Remove problem edges whose destination
211 // is the root of their own tree; these edges
212 // are trivially redundant with reg-true edges.
213 int remaining = 0;
214 for (int i = 0; i < numProblemEdges; i++) {
215 SpaceEffGraphEdge e = problemEdges[i];
216 SpaceEffGraphNode src = e.fromNode();
217 SpaceEffGraphNode dst = e.toNode();
218 SpaceEffGraphNode srcRoot = src.nextSorted;
219 if (srcRoot != dst) {
220 // might still be trouble
221 problemEdges[remaining++] = e;
222 }
223 }
224 numProblemEdges = remaining;
225 if (numProblemEdges == 0) return;
226
227 // Still some edges that might introduce cycles.
228 int searchnum = 0;
229 for (int i = 0; i < numProblemEdges; i++) {
230 SpaceEffGraphEdge e = problemEdges[i];
231 SpaceEffGraphNode src = e.fromNode();
232 SpaceEffGraphNode dst = e.toNode();
233 BURS_TreeNode n = (BURS_TreeNode) src.scratchObject;
234 if (n.isTreeRoot()) continue; // some other problem edge already forced it
235 SpaceEffGraphNode srcRoot = src.nextSorted;
236 SpaceEffGraphNode dstRoot = dst.nextSorted;
237 if (srcRoot == dstRoot && srcRoot != dst) {
238 // potential for intra-tree cycle
239 if (!trueEdgeRedundant(src, dst, srcRoot)) {
240 if (DEBUG) {
241 VM.sysWrite("Potential intra-tree cycle with edge " + e + " forcing " + n + " to be a tree root\n");
242 }
243 makeTreeRoot(n);
244 problemEdgePrep(n, n.dg_node);
245 }
246 } else {
247 // potential for inter-tree cycle
248 if (reachableRoot(dstRoot, srcRoot, ++searchnum)) {
249 if (DEBUG) {
250 VM.sysWrite("Potential inter-tree cycle with edge " + e + " forcing " + n + " to be a tree root\n");
251 }
252 makeTreeRoot(n);
253 problemEdgePrep(n, n.dg_node);
254 }
255 }
256 }
257 }
258
259 // routine to identify harmless intra-tree edges.
260 // if the edge is redundant wrt regTrue edges, then it
261 // can be ignored.
262 private boolean trueEdgeRedundant(SpaceEffGraphNode current, SpaceEffGraphNode goal,
263 SpaceEffGraphNode root) {
264 if (current == goal) return true;
265 if (current.nextSorted != root) return false; // don't cross tree boundaries
266 for (SpaceEffGraphEdge out = current.firstOutEdge(); out != null; out = out.getNextOut()) {
267 if (DepGraphEdge.isRegTrue(out) && trueEdgeRedundant(out.toNode(), goal, root)) {
268 return true;
269 }
270 }
271 return false;
272 }
273
274 // routine to identify harmless inter-tree edges.
275 // Is goal reachable via any edge in the current tree?
276 private boolean reachableRoot(SpaceEffGraphNode current, SpaceEffGraphNode goal, int searchnum) {
277 if (current == goal) return true;
278 if (current.scratch == searchnum) return false;
279 current.scratch = searchnum;
280 BURS_TreeNode root = (BURS_TreeNode) current.scratchObject;
281 return reachableChild(root, goal, searchnum);
282 }
283
284 private boolean reachableChild(BURS_TreeNode n, SpaceEffGraphNode goal, int searchnum) {
285 SpaceEffGraphNode dgn = n.dg_node;
286 if (dgn != null) {
287 for (SpaceEffGraphEdge out = dgn.firstOutEdge(); out != null; out = out.getNextOut()) {
288 if (reachableRoot(out.toNode().nextSorted, goal, searchnum)) return true;
289 }
290 }
291 if (n.child1 != null && !n.child1.isTreeRoot() && reachableChild(n.child1, goal, searchnum)) {
292 return true;
293 }
294 if (n.child2 != null && !n.child2.isTreeRoot() && reachableChild(n.child2, goal, searchnum)) {
295 return true;
296 }
297 return false;
298 }
299
300 /**
301 * Stage 2: Construct topological ordering of tree roots based on the
302 * dependencies between nodes in the tree.
303 *
304 * @param dg The dependence graph.
305 */
306 private void orderTrees(DepGraph dg) {
307 // Initialize tree root field for all nodes
308 for (int i = 0; i < numTreeRoots; i++) {
309 BURS_TreeNode n = treeRoots[i];
310 n.dg_node.scratch = 0;
311 initTreeRootNode(n, n.dg_node);
312 }
313
314 // Initialize predCount[*]
315 for (SpaceEffGraphNode node = dg.firstNode(); node != null; node = node.getNext()) {
316 SpaceEffGraphNode n_treeRoot = node.nextSorted;
317 for (SpaceEffGraphEdge in = node.firstInEdge(); in != null; in = in.getNextIn()) {
318 SpaceEffGraphNode source_treeRoot = in.fromNode().nextSorted;
319 if (source_treeRoot != n_treeRoot) {
320 n_treeRoot.scratch++;
321 }
322 }
323 }
324 if (DEBUG) {
325 for (int i = 0; i < numTreeRoots; i++) {
326 BURS_TreeNode n = treeRoots[i];
327 VM.sysWrite(n.dg_node.scratch + ":" + n + "\n");
328 }
329 }
330 }
331
332 /**
333 * Stage 3: Label the trees with their min cost cover.
334 * @param burs the BURS_STATE object.
335 */
336 private void labelTrees(BURS_STATE burs) {
337 for (int i = 0; i < numTreeRoots; i++) {
338 BURS_TreeNode n = treeRoots[i];
339 burs.label(n);
340 BURS_STATE.mark(n, /* goalnt */(byte) 1);
341 }
342 }
343
344 /**
345 * Stage 4: Visit the tree roots in topological order and
346 * emit MIR instructions by calling BURS_STATE.code on each
347 * supernode in the tree.
348 *
349 * @param burs the BURS_STATE object.
350 */
351 private void generateTrees(BURS_STATE burs) {
352 // Append tree roots with predCount = 0 to readySet
353 for (int i = 0; i < numTreeRoots; i++) {
354 BURS_TreeNode n = treeRoots[i];
355 if (n.dg_node.scratch == 0) {
356 readySetInsert(n);
357 }
358 }
359
360 // Emit code for each tree root in readySet
361 while (readySetNotEmpty()) {
362 BURS_TreeNode k = readySetRemove();
363 // Invoke burs.code on the supernodes of k in a post order walk of the
364 // tree (thus code for children is emited before code for the parent).
365 if (DEBUG) {
366 VM.sysWrite("PROCESSING TREE ROOTED AT " + k.dg_node + "\n");
367 BURS_STATE.dumpTree(k);
368 }
369 numTreeRoots--;
370 generateTree(k, burs);
371 }
372 if (numTreeRoots != 0) {
373 throw new OptimizingCompilerException("BURS", "Not all tree roots were processed");
374 }
375 }
376
377 // Generate code for a single tree root.
378 // Also process inter-tree dependencies from this tree to other trees.
379 private void generateTree(BURS_TreeNode k, BURS_STATE burs) {
380 BURS_TreeNode child1 = k.child1;
381 BURS_TreeNode child2 = k.child2;
382 if (child1 != null) {
383 if (child2 != null) {
384 // k has two children; use register labeling to
385 // determine order that minimizes register pressure
386 if (k.isSuperNodeRoot()) {
387 byte act = BURS_STATE.action[k.rule(k.getNonTerminal())];
388 if ((act & BURS_STATE.LEFT_CHILD_FIRST) != 0) {
389 // rule selected forces order of evaluation
390 generateTree(child1, burs);
391 generateTree(child2, burs);
392 } else if ((act & BURS_STATE.RIGHT_CHILD_FIRST) != 0) {
393 // rule selected forces order of evaluation
394 generateTree(child2, burs);
395 generateTree(child1, burs);
396 } else if (child2.numRegisters() > child1.numRegisters()) {
397 generateTree(child2, burs);
398 generateTree(child1, burs);
399 } else {
400 generateTree(child1, burs);
401 generateTree(child2, burs);
402 }
403 } else {
404 if (child2.numRegisters() > child1.numRegisters()) {
405 generateTree(child2, burs);
406 generateTree(child1, burs);
407 } else {
408 generateTree(child1, burs);
409 generateTree(child2, burs);
410 }
411 }
412 } else {
413 generateTree(child1, burs);
414 }
415 } else if (child2 != null) {
416 generateTree(child2, burs);
417 }
418
419 if (k.isSuperNodeRoot()) {
420 int nonterminal = k.getNonTerminal();
421 int rule = k.rule(nonterminal);
422 burs.code(k, nonterminal, rule);
423 if (DEBUG) VM.sysWrite(k + " " + BURS_Debug.string[rule] + "\n");
424 }
425
426 DepGraphNode dgnode = k.dg_node;
427 if (dgnode != null) {
428 SpaceEffGraphNode source = dgnode.nextSorted;
429 for (SpaceEffGraphEdge out = dgnode.firstOutEdge(); out != null; out = out.getNextOut()) {
430 SpaceEffGraphNode dest = out.toNode().nextSorted;
431 if (source != dest) {
432 int count = --dest.scratch;
433 if (DEBUG) VM.sysWrite(count + ": edge " + source + " to " + dest + "\n");
434 if (count == 0) {
435 readySetInsert((BURS_TreeNode) dest.scratchObject);
436 }
437 }
438 }
439 }
440 }
441
442 /**
443 * Return {@code true} if node n must be a root of a BURS tree
444 * based only on its register true dependencies.
445 * If the node might later have to be marked as a tree
446 * root, then include in a set of problem nodes.
447 * @param n the dep graph node in question.
448 */
449 private boolean mustBeTreeRoot(DepGraphNode n) {
450 // A "fan-out" node must be a root of a BURS tree.
451 // (A fan-out node is a node with > 1 outgoing register-true dependences)
452 SpaceEffGraphEdge trueDepEdge = null;
453 for (SpaceEffGraphEdge out = n.firstOutEdge(); out != null; out = out.getNextOut()) {
454 if (DepGraphEdge.isRegTrue(out)) {
455 if (trueDepEdge != null) return true;
456 trueDepEdge = out;
457 }
458 }
459
460 if (trueDepEdge == null) {
461 return true; // 0 outgoing register-true dependencies
462 } else {
463 // Exactly 1 true edge, since we would have bailed out of above
464 // loop if we'd found a second one.
465 // If the node produces a register value that is live on exit
466 // from the basic block then it must be the root of a BURS tree.
467 Instruction instr = n.instruction();
468 if (instr.operator() == IR_PROLOGUE) return true;
469 RegisterOperand rop = ResultCarrier.getResult(instr);
470 if (rop.getRegister().spansBasicBlock()) return true;
471 SpaceEffGraphNode parent = trueDepEdge.toNode();
472 // If our parent has a superset of our
473 // other out edges (ignoring trueDepEdge)
474 // then we don't have to worry about creating cycles
475 // by not forcing n to be a tree root.
476 for (SpaceEffGraphEdge out = n.firstOutEdge(); out != null; out = out.getNextOut()) {
477 if (out != trueDepEdge) {
478 boolean match = false;
479 for (SpaceEffGraphEdge out2 = parent.firstOutEdge(); out2 != null; out2 = out2.getNextOut()) {
480 if (out2.toNode() == out.toNode()) {
481 match = true;
482 break;
483 }
484 }
485 if (!match) {
486 // could be trouble. Remember for later processing.
487 rememberAsProblemEdge(out);
488 }
489 }
490 }
491 return false;
492 }
493 }
494
495 // NOTE: assumes n has exactly 1 reg true parent (ie it is in
496 // an expression tree and is not the tree root).
497 @SuppressWarnings("unused")
498 private SpaceEffGraphNode regTrueParent(SpaceEffGraphNode n) {
499 for (SpaceEffGraphEdge out = n.firstOutEdge(); out != null; out = out.getNextOut()) {
500 if (DepGraphEdge.isRegTrue(out)) {
501 return out.toNode();
502 }
503 }
504 if (VM.VerifyAssertions) VM._assert(VM.NOT_REACHED);
505 return null;
506 }
507
508 /**
509 * Initialize nextSorted for nodes in tree rooted at t i.e.
510 * for all register true descendants of t up to but not including
511 * any new tree roots.
512 */
513 private void initTreeRootNode(BURS_TreeNode t, SpaceEffGraphNode treeRoot) {
514 // Recurse
515 if (t.child1 != null) {
516 if (t.child1.isTreeRoot()) {
517 t.child1 = Register;
518 } else {
519 initTreeRootNode(t.child1, treeRoot);
520 }
521 }
522 if (t.child2 != null) {
523 if (t.child2.isTreeRoot()) {
524 t.child2 = Register;
525 } else {
526 initTreeRootNode(t.child2, treeRoot);
527 }
528 }
529 if (t.dg_node != null) {
530 t.dg_node.nextSorted = treeRoot;
531 if (DEBUG) VM.sysWrite(t.dg_node + " --> " + treeRoot + "\n");
532 }
533 if (t.child1 != null || t.child2 != null) {
534 // label t as in section 9.10 of the dragon book
535 int lchild = (t.child1 != null) ? t.child1.numRegisters() : 0;
536 int rchild = (t.child2 != null) ? t.child2.numRegisters() : 0;
537 if (lchild == rchild) {
538 t.setNumRegisters(lchild + 1);
539 } else {
540 t.setNumRegisters(Math.max(lchild, rchild));
541 }
542 if (DEBUG) VM.sysWrite("\tnum registers = " + t.numRegisters() + "\n");
543 }
544 }
545
546 /**
547 * Set of all tree roots.
548 */
549 private BURS_TreeNode[] treeRoots = new BURS_TreeNode[32];
550
551 private void makeTreeRoot(BURS_TreeNode n) {
552 if (numTreeRoots == treeRoots.length) {
553 BURS_TreeNode[] tmp = new BURS_TreeNode[treeRoots.length * 2];
554 for (int i = 0; i < treeRoots.length; i++) {
555 tmp[i] = treeRoots[i];
556 }
557 treeRoots = tmp;
558 }
559 n.setTreeRoot();
560 treeRoots[numTreeRoots++] = n;
561 }
562
563 /**
564 * A priority queue of ready tree nodes.
565 * Used to keep track of the tree roots that are ready to be
566 * emitted during code generation (since all of their
567 * predecessors have been emitted already).
568 * readySetRemove returns the node that uses the maximum
569 * number of registers. This is a heuristic that tends to
570 * reduce register pressure and enable coalescing by the
571 * register allocator. (Goal is to end live ranges 'early').
572 */
573 private BURS_TreeNode[] heap = new BURS_TreeNode[16];
574 private int numElements = 0;
575
576 /**
577 * Add a node to the ready set.
578 */
579 private void readySetInsert(BURS_TreeNode node) {
580 Instruction s = node.getInstruction();
581 if (s.operator == GUARD_COMBINE ||
582 s.operator == GUARD_COND_MOVE ||
583 s.operator == GUARD_MOVE ||
584 !ResultCarrier.conforms(s)) {
585 // Adjust numRegisters to bias away from picking trees that
586 // are rooted in result carriers, since they start a new live
587 // range. We don't count guard operations as result carriers, since
588 // guard operations get wiped out before register allocation anyways.
589 node.setNumRegisters(node.numRegisters() + 2);
590 }
591
592 numElements++;
593 if (numElements == heap.length) {
594 BURS_TreeNode[] tmp = new BURS_TreeNode[heap.length * 2];
595 for (int i = 0; i < heap.length; i++) {
596 tmp[i] = heap[i];
597 }
598 heap = tmp;
599 }
600
601 // restore heap property
602 int current = numElements;
603 heap[current] = node;
604 for (int parent = current / 2; current > 1 && heap[current].numRegisters() > heap[parent].numRegisters(); current =
605 parent, parent = current / 2) {
606 swap(current, parent);
607 }
608 }
609
610 /**
611 * Are there nodes to process on the stack?
612 */
613 private boolean readySetNotEmpty() {
614 return numElements > 0;
615 }
616
617 /**
618 * Remove a node from the ready set
619 */
620 private BURS_TreeNode readySetRemove() {
621 BURS_TreeNode ans = heap[1];
622 heap[1] = heap[numElements--];
623 heapify(1);
624 return ans;
625 }
626
627 private void heapify(int p) {
628 int l = p * 2;
629 int r = l + 1;
630 int max = p;
631 if (l <= numElements && heap[l].numRegisters() > heap[max].numRegisters()) {
632 max = l;
633 }
634 if (r <= numElements && heap[r].numRegisters() > heap[max].numRegisters()) {
635 max = r;
636 }
637 if (max != p) {
638 swap(p, max);
639 heapify(max);
640 }
641 }
642
643 private void swap(int x, int y) {
644 BURS_TreeNode t = heap[x];
645 heap[x] = heap[y];
646 heap[y] = t;
647 }
648
649 /*
650 * track problem nodes (nodes with outgoing non-reg-true edges)
651 */
652 private SpaceEffGraphEdge[] problemEdges;
653 private int numProblemEdges = 0;
654
655 void rememberAsProblemEdge(SpaceEffGraphEdge e) {
656 if (problemEdges == null) {
657 problemEdges = new SpaceEffGraphEdge[8];
658 }
659 if (numProblemEdges == problemEdges.length) {
660 SpaceEffGraphEdge[] tmp = new SpaceEffGraphEdge[problemEdges.length * 2];
661 for (int i = 0; i < problemEdges.length; i++) {
662 tmp[i] = problemEdges[i];
663 }
664 problemEdges = tmp;
665 }
666 problemEdges[numProblemEdges++] = e;
667 }
668
669 private boolean haveProblemEdges() {
670 return numProblemEdges > 0;
671 }
672 }