Mercurial > hg > truffle

changeset 19165:b3b81dfff200

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Move ComputeBlockOrder to compiler.common and delete c.o.g.alloc project.
author Josef Eisl <josef.eisl@jku.at>
date Fri, 06 Feb 2015 10:09:13 +0100
parents b215b88e215f
children 39e99cf01468
files graal/com.oracle.graal.alloc/overview.html graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java graal/com.oracle.graal.baseline/src/com/oracle/graal/baseline/BaselineBytecodeParser.java graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/alloc/ComputeBlockOrder.java graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScan.java mx/suite.py
diffstat 7 files changed, 268 insertions(+), 314 deletions(-) [+]
line wrap: on
line diff
--- a/graal/com.oracle.graal.alloc/overview.html	Thu Feb 05 19:17:47 2015 +0100
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,36 +0,0 @@
-<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
-<html>
-<head>
-<!--
-
-Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved.
-DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
-
-This code is free software; you can redistribute it and/or modify it
-under the terms of the GNU General Public License version 2 only, as
-published by the Free Software Foundation.  Oracle designates this
-particular file as subject to the "Classpath" exception as provided
-by Oracle in the LICENSE file that accompanied this code.
-
-This code is distributed in the hope that it will be useful, but WITHOUT
-ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
-FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
-version 2 for more details (a copy is included in the LICENSE file that
-accompanied this code).
-
-You should have received a copy of the GNU General Public License version
-2 along with this work; if not, write to the Free Software Foundation,
-Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
-
-Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
-or visit www.oracle.com if you need additional information or have any
-questions.
--->
-
-</head>
-<body>
-
-Documentation for the <code>com.oracle.graal.alloc</code> project.
-
-</body>
-</html>
--- a/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java	Thu Feb 05 19:17:47 2015 +0100
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,265 +0,0 @@
-/*
- * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved.
- * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
- *
- * This code is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License version 2 only, as
- * published by the Free Software Foundation.
- *
- * This code is distributed in the hope that it will be useful, but WITHOUT
- * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
- * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
- * version 2 for more details (a copy is included in the LICENSE file that
- * accompanied this code).
- *
- * You should have received a copy of the GNU General Public License version
- * 2 along with this work; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
- *
- * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
- * or visit www.oracle.com if you need additional information or have any
- * questions.
- */
-
-package com.oracle.graal.alloc;
-
-import java.util.*;
-
-import com.oracle.graal.compiler.common.cfg.*;
-
-/**
- * Computes an ordering of the block that can be used by the linear scan register allocator and the
- * machine code generator. The machine code generation order will start with the first block and
- * produce a straight sequence always following the most likely successor. Then it will continue
- * with the most likely path that was left out during this process. The process iteratively
- * continues until all blocks are scheduled. Additionally, it is guaranteed that all blocks of a
- * loop are scheduled before any block following the loop is scheduled.
- *
- * The machine code generator order includes reordering of loop headers such that the backward jump
- * is a conditional jump if there is only one loop end block. Additionally, the target of loop
- * backward jumps are always marked as aligned. Aligning the target of conditional jumps does not
- * bring a measurable benefit and is therefore avoided to keep the code size small.
- *
- * The linear scan register allocator order has an additional mechanism that prevents merge nodes
- * from being scheduled if there is at least one highly likely predecessor still unscheduled. This
- * increases the probability that the merge node and the corresponding predecessor are more closely
- * together in the schedule thus decreasing the probability for inserted phi moves. Also, the
- * algorithm sets the linear scan order number of the block that corresponds to its index in the
- * linear scan order.
- */
-public final class ComputeBlockOrder {
-
-    /**
-     * The initial capacities of the worklists used for iteratively finding the block order.
-     */
-    private static final int INITIAL_WORKLIST_CAPACITY = 10;
-
-    /**
-     * Divisor used for degrading the probability of the current path versus unscheduled paths at a
-     * merge node when calculating the linear scan order. A high value means that predecessors of
-     * merge nodes are more likely to be scheduled before the merge node.
-     */
-    private static final int PENALTY_VERSUS_UNSCHEDULED = 10;
-
-    /**
-     * Computes the block order used for the linear scan register allocator.
-     *
-     * @return sorted list of blocks
-     */
-    public static <T extends AbstractBlock<T>> List<T> computeLinearScanOrder(int blockCount, T startBlock) {
-        List<T> order = new ArrayList<>();
-        BitSet visitedBlocks = new BitSet(blockCount);
-        PriorityQueue<T> worklist = initializeWorklist(startBlock, visitedBlocks);
-        computeLinearScanOrder(order, worklist, visitedBlocks);
-        assert checkOrder(order, blockCount);
-        return order;
-    }
-
-    /**
-     * Computes the block order used for code emission.
-     *
-     * @return sorted list of blocks
-     */
-    public static <T extends AbstractBlock<T>> List<T> computeCodeEmittingOrder(int blockCount, T startBlock) {
-        List<T> order = new ArrayList<>();
-        BitSet visitedBlocks = new BitSet(blockCount);
-        PriorityQueue<T> worklist = initializeWorklist(startBlock, visitedBlocks);
-        computeCodeEmittingOrder(order, worklist, visitedBlocks);
-        assert checkOrder(order, blockCount);
-        return order;
-    }
-
-    /**
-     * Iteratively adds paths to the code emission block order.
-     */
-    private static <T extends AbstractBlock<T>> void computeCodeEmittingOrder(List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks) {
-        while (!worklist.isEmpty()) {
-            T nextImportantPath = worklist.poll();
-            addPathToCodeEmittingOrder(nextImportantPath, order, worklist, visitedBlocks);
-        }
-    }
-
-    /**
-     * Iteratively adds paths to the linear scan block order.
-     */
-    private static <T extends AbstractBlock<T>> void computeLinearScanOrder(List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks) {
-        while (!worklist.isEmpty()) {
-            T nextImportantPath = worklist.poll();
-            addPathToLinearScanOrder(nextImportantPath, order, worklist, visitedBlocks);
-        }
-    }
-
-    /**
-     * Initializes the priority queue used for the work list of blocks and adds the start block.
-     */
-    private static <T extends AbstractBlock<T>> PriorityQueue<T> initializeWorklist(T startBlock, BitSet visitedBlocks) {
-        PriorityQueue<T> result = new PriorityQueue<>(INITIAL_WORKLIST_CAPACITY, new BlockOrderComparator<>());
-        result.add(startBlock);
-        visitedBlocks.set(startBlock.getId());
-        return result;
-    }
-
-    /**
-     * Add a linear path to the linear scan order greedily following the most likely successor.
-     */
-    private static <T extends AbstractBlock<T>> void addPathToLinearScanOrder(T block, List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks) {
-        block.setLinearScanNumber(order.size());
-        order.add(block);
-        T mostLikelySuccessor = findAndMarkMostLikelySuccessor(block, visitedBlocks);
-        enqueueSuccessors(block, worklist, visitedBlocks);
-        if (mostLikelySuccessor != null) {
-            if (!mostLikelySuccessor.isLoopHeader() && mostLikelySuccessor.getPredecessorCount() > 1) {
-                // We are at a merge. Check probabilities of predecessors that are not yet
-                // scheduled.
-                double unscheduledSum = 0.0;
-                for (T pred : mostLikelySuccessor.getPredecessors()) {
-                    if (pred.getLinearScanNumber() == -1) {
-                        unscheduledSum += pred.probability();
-                    }
-                }
-
-                if (unscheduledSum > block.probability() / PENALTY_VERSUS_UNSCHEDULED) {
-                    // Add this merge only after at least one additional predecessor gets scheduled.
-                    visitedBlocks.clear(mostLikelySuccessor.getId());
-                    return;
-                }
-            }
-            addPathToLinearScanOrder(mostLikelySuccessor, order, worklist, visitedBlocks);
-        }
-    }
-
-    /**
-     * Add a linear path to the code emission order greedily following the most likely successor.
-     */
-    private static <T extends AbstractBlock<T>> void addPathToCodeEmittingOrder(T initialBlock, List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks) {
-        T block = initialBlock;
-        while (block != null) {
-            // Skip loop headers if there is only a single loop end block to
-            // make the backward jump be a conditional jump.
-            if (!skipLoopHeader(block)) {
-
-                // Align unskipped loop headers as they are the target of the backward jump.
-                if (block.isLoopHeader()) {
-                    block.setAlign(true);
-                }
-                addBlock(block, order);
-            }
-
-            Loop<T> loop = block.getLoop();
-            if (block.isLoopEnd() && skipLoopHeader(loop.getHeader())) {
-
-                // This is the only loop end of a skipped loop header.
-                // Add the header immediately afterwards.
-                addBlock(loop.getHeader(), order);
-
-                // Make sure the loop successors of the loop header are aligned
-                // as they are the target
-                // of the backward jump.
-                for (T successor : loop.getHeader().getSuccessors()) {
-                    if (successor.getLoopDepth() == block.getLoopDepth()) {
-                        successor.setAlign(true);
-                    }
-                }
-            }
-
-            T mostLikelySuccessor = findAndMarkMostLikelySuccessor(block, visitedBlocks);
-            enqueueSuccessors(block, worklist, visitedBlocks);
-            block = mostLikelySuccessor;
-        }
-    }
-
-    /**
-     * Adds a block to the ordering.
-     */
-    private static <T extends AbstractBlock<T>> void addBlock(T header, List<T> order) {
-        assert !order.contains(header) : "Cannot insert block twice";
-        order.add(header);
-    }
-
-    /**
-     * Find the highest likely unvisited successor block of a given block.
-     */
-    private static <T extends AbstractBlock<T>> T findAndMarkMostLikelySuccessor(T block, BitSet visitedBlocks) {
-        T result = null;
-        for (T successor : block.getSuccessors()) {
-            assert successor.probability() >= 0.0 : "Probabilities must be positive";
-            if (!visitedBlocks.get(successor.getId()) && successor.getLoopDepth() >= block.getLoopDepth() && (result == null || successor.probability() >= result.probability())) {
-                result = successor;
-            }
-        }
-        if (result != null) {
-            visitedBlocks.set(result.getId());
-        }
-        return result;
-    }
-
-    /**
-     * Add successor blocks into the given work list if they are not already marked as visited.
-     */
-    private static <T extends AbstractBlock<T>> void enqueueSuccessors(T block, PriorityQueue<T> worklist, BitSet visitedBlocks) {
-        for (T successor : block.getSuccessors()) {
-            if (!visitedBlocks.get(successor.getId())) {
-                visitedBlocks.set(successor.getId());
-                worklist.add(successor);
-            }
-        }
-    }
-
-    /**
-     * Skip the loop header block if the loop consists of more than one block and it has only a
-     * single loop end block.
-     */
-    private static <T extends AbstractBlock<T>> boolean skipLoopHeader(AbstractBlock<T> block) {
-        return (block.isLoopHeader() && !block.isLoopEnd() && block.getLoop().numBackedges() == 1);
-    }
-
-    /**
-     * Checks that the ordering contains the expected number of blocks.
-     */
-    private static boolean checkOrder(List<? extends AbstractBlock<?>> order, int expectedBlockCount) {
-        assert order.size() == expectedBlockCount : String.format("Number of blocks in ordering (%d) does not match expected block count (%d)", order.size(), expectedBlockCount);
-        return true;
-    }
-
-    /**
-     * Comparator for sorting blocks based on loop depth and probability.
-     */
-    private static class BlockOrderComparator<T extends AbstractBlock<T>> implements Comparator<T> {
-
-        @Override
-        public int compare(T a, T b) {
-            // Loop blocks before any loop exit block.
-            int diff = b.getLoopDepth() - a.getLoopDepth();
-            if (diff != 0) {
-                return diff;
-            }
-
-            // Blocks with high probability before blocks with low probability.
-            if (a.probability() > b.probability()) {
-                return -1;
-            } else {
-                return 1;
-            }
-        }
-    }
-}
--- a/graal/com.oracle.graal.baseline/src/com/oracle/graal/baseline/BaselineBytecodeParser.java	Thu Feb 05 19:17:47 2015 +0100
+++ b/graal/com.oracle.graal.baseline/src/com/oracle/graal/baseline/BaselineBytecodeParser.java	Fri Feb 06 10:09:13 2015 +0100
@@ -26,11 +26,11 @@
 
 import java.util.*;
 
-import com.oracle.graal.alloc.*;
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.compiler.alloc.*;
 import com.oracle.graal.compiler.common.*;
+import com.oracle.graal.compiler.common.alloc.*;
 import com.oracle.graal.compiler.common.calc.*;
 import com.oracle.graal.compiler.common.cfg.*;
 import com.oracle.graal.compiler.gen.*;
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/alloc/ComputeBlockOrder.java	Fri Feb 06 10:09:13 2015 +0100
@@ -0,0 +1,265 @@
+/*
+ * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+package com.oracle.graal.compiler.common.alloc;
+
+import java.util.*;
+
+import com.oracle.graal.compiler.common.cfg.*;
+
+/**
+ * Computes an ordering of the block that can be used by the linear scan register allocator and the
+ * machine code generator. The machine code generation order will start with the first block and
+ * produce a straight sequence always following the most likely successor. Then it will continue
+ * with the most likely path that was left out during this process. The process iteratively
+ * continues until all blocks are scheduled. Additionally, it is guaranteed that all blocks of a
+ * loop are scheduled before any block following the loop is scheduled.
+ *
+ * The machine code generator order includes reordering of loop headers such that the backward jump
+ * is a conditional jump if there is only one loop end block. Additionally, the target of loop
+ * backward jumps are always marked as aligned. Aligning the target of conditional jumps does not
+ * bring a measurable benefit and is therefore avoided to keep the code size small.
+ *
+ * The linear scan register allocator order has an additional mechanism that prevents merge nodes
+ * from being scheduled if there is at least one highly likely predecessor still unscheduled. This
+ * increases the probability that the merge node and the corresponding predecessor are more closely
+ * together in the schedule thus decreasing the probability for inserted phi moves. Also, the
+ * algorithm sets the linear scan order number of the block that corresponds to its index in the
+ * linear scan order.
+ */
+public final class ComputeBlockOrder {
+
+    /**
+     * The initial capacities of the worklists used for iteratively finding the block order.
+     */
+    private static final int INITIAL_WORKLIST_CAPACITY = 10;
+
+    /**
+     * Divisor used for degrading the probability of the current path versus unscheduled paths at a
+     * merge node when calculating the linear scan order. A high value means that predecessors of
+     * merge nodes are more likely to be scheduled before the merge node.
+     */
+    private static final int PENALTY_VERSUS_UNSCHEDULED = 10;
+
+    /**
+     * Computes the block order used for the linear scan register allocator.
+     *
+     * @return sorted list of blocks
+     */
+    public static <T extends AbstractBlock<T>> List<T> computeLinearScanOrder(int blockCount, T startBlock) {
+        List<T> order = new ArrayList<>();
+        BitSet visitedBlocks = new BitSet(blockCount);
+        PriorityQueue<T> worklist = initializeWorklist(startBlock, visitedBlocks);
+        computeLinearScanOrder(order, worklist, visitedBlocks);
+        assert checkOrder(order, blockCount);
+        return order;
+    }
+
+    /**
+     * Computes the block order used for code emission.
+     *
+     * @return sorted list of blocks
+     */
+    public static <T extends AbstractBlock<T>> List<T> computeCodeEmittingOrder(int blockCount, T startBlock) {
+        List<T> order = new ArrayList<>();
+        BitSet visitedBlocks = new BitSet(blockCount);
+        PriorityQueue<T> worklist = initializeWorklist(startBlock, visitedBlocks);
+        computeCodeEmittingOrder(order, worklist, visitedBlocks);
+        assert checkOrder(order, blockCount);
+        return order;
+    }
+
+    /**
+     * Iteratively adds paths to the code emission block order.
+     */
+    private static <T extends AbstractBlock<T>> void computeCodeEmittingOrder(List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks) {
+        while (!worklist.isEmpty()) {
+            T nextImportantPath = worklist.poll();
+            addPathToCodeEmittingOrder(nextImportantPath, order, worklist, visitedBlocks);
+        }
+    }
+
+    /**
+     * Iteratively adds paths to the linear scan block order.
+     */
+    private static <T extends AbstractBlock<T>> void computeLinearScanOrder(List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks) {
+        while (!worklist.isEmpty()) {
+            T nextImportantPath = worklist.poll();
+            addPathToLinearScanOrder(nextImportantPath, order, worklist, visitedBlocks);
+        }
+    }
+
+    /**
+     * Initializes the priority queue used for the work list of blocks and adds the start block.
+     */
+    private static <T extends AbstractBlock<T>> PriorityQueue<T> initializeWorklist(T startBlock, BitSet visitedBlocks) {
+        PriorityQueue<T> result = new PriorityQueue<>(INITIAL_WORKLIST_CAPACITY, new BlockOrderComparator<>());
+        result.add(startBlock);
+        visitedBlocks.set(startBlock.getId());
+        return result;
+    }
+
+    /**
+     * Add a linear path to the linear scan order greedily following the most likely successor.
+     */
+    private static <T extends AbstractBlock<T>> void addPathToLinearScanOrder(T block, List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks) {
+        block.setLinearScanNumber(order.size());
+        order.add(block);
+        T mostLikelySuccessor = findAndMarkMostLikelySuccessor(block, visitedBlocks);
+        enqueueSuccessors(block, worklist, visitedBlocks);
+        if (mostLikelySuccessor != null) {
+            if (!mostLikelySuccessor.isLoopHeader() && mostLikelySuccessor.getPredecessorCount() > 1) {
+                // We are at a merge. Check probabilities of predecessors that are not yet
+                // scheduled.
+                double unscheduledSum = 0.0;
+                for (T pred : mostLikelySuccessor.getPredecessors()) {
+                    if (pred.getLinearScanNumber() == -1) {
+                        unscheduledSum += pred.probability();
+                    }
+                }
+
+                if (unscheduledSum > block.probability() / PENALTY_VERSUS_UNSCHEDULED) {
+                    // Add this merge only after at least one additional predecessor gets scheduled.
+                    visitedBlocks.clear(mostLikelySuccessor.getId());
+                    return;
+                }
+            }
+            addPathToLinearScanOrder(mostLikelySuccessor, order, worklist, visitedBlocks);
+        }
+    }
+
+    /**
+     * Add a linear path to the code emission order greedily following the most likely successor.
+     */
+    private static <T extends AbstractBlock<T>> void addPathToCodeEmittingOrder(T initialBlock, List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks) {
+        T block = initialBlock;
+        while (block != null) {
+            // Skip loop headers if there is only a single loop end block to
+            // make the backward jump be a conditional jump.
+            if (!skipLoopHeader(block)) {
+
+                // Align unskipped loop headers as they are the target of the backward jump.
+                if (block.isLoopHeader()) {
+                    block.setAlign(true);
+                }
+                addBlock(block, order);
+            }
+
+            Loop<T> loop = block.getLoop();
+            if (block.isLoopEnd() && skipLoopHeader(loop.getHeader())) {
+
+                // This is the only loop end of a skipped loop header.
+                // Add the header immediately afterwards.
+                addBlock(loop.getHeader(), order);
+
+                // Make sure the loop successors of the loop header are aligned
+                // as they are the target
+                // of the backward jump.
+                for (T successor : loop.getHeader().getSuccessors()) {
+                    if (successor.getLoopDepth() == block.getLoopDepth()) {
+                        successor.setAlign(true);
+                    }
+                }
+            }
+
+            T mostLikelySuccessor = findAndMarkMostLikelySuccessor(block, visitedBlocks);
+            enqueueSuccessors(block, worklist, visitedBlocks);
+            block = mostLikelySuccessor;
+        }
+    }
+
+    /**
+     * Adds a block to the ordering.
+     */
+    private static <T extends AbstractBlock<T>> void addBlock(T header, List<T> order) {
+        assert !order.contains(header) : "Cannot insert block twice";
+        order.add(header);
+    }
+
+    /**
+     * Find the highest likely unvisited successor block of a given block.
+     */
+    private static <T extends AbstractBlock<T>> T findAndMarkMostLikelySuccessor(T block, BitSet visitedBlocks) {
+        T result = null;
+        for (T successor : block.getSuccessors()) {
+            assert successor.probability() >= 0.0 : "Probabilities must be positive";
+            if (!visitedBlocks.get(successor.getId()) && successor.getLoopDepth() >= block.getLoopDepth() && (result == null || successor.probability() >= result.probability())) {
+                result = successor;
+            }
+        }
+        if (result != null) {
+            visitedBlocks.set(result.getId());
+        }
+        return result;
+    }
+
+    /**
+     * Add successor blocks into the given work list if they are not already marked as visited.
+     */
+    private static <T extends AbstractBlock<T>> void enqueueSuccessors(T block, PriorityQueue<T> worklist, BitSet visitedBlocks) {
+        for (T successor : block.getSuccessors()) {
+            if (!visitedBlocks.get(successor.getId())) {
+                visitedBlocks.set(successor.getId());
+                worklist.add(successor);
+            }
+        }
+    }
+
+    /**
+     * Skip the loop header block if the loop consists of more than one block and it has only a
+     * single loop end block.
+     */
+    private static <T extends AbstractBlock<T>> boolean skipLoopHeader(AbstractBlock<T> block) {
+        return (block.isLoopHeader() && !block.isLoopEnd() && block.getLoop().numBackedges() == 1);
+    }
+
+    /**
+     * Checks that the ordering contains the expected number of blocks.
+     */
+    private static boolean checkOrder(List<? extends AbstractBlock<?>> order, int expectedBlockCount) {
+        assert order.size() == expectedBlockCount : String.format("Number of blocks in ordering (%d) does not match expected block count (%d)", order.size(), expectedBlockCount);
+        return true;
+    }
+
+    /**
+     * Comparator for sorting blocks based on loop depth and probability.
+     */
+    private static class BlockOrderComparator<T extends AbstractBlock<T>> implements Comparator<T> {
+
+        @Override
+        public int compare(T a, T b) {
+            // Loop blocks before any loop exit block.
+            int diff = b.getLoopDepth() - a.getLoopDepth();
+            if (diff != 0) {
+                return diff;
+            }
+
+            // Blocks with high probability before blocks with low probability.
+            if (a.probability() > b.probability()) {
+                return -1;
+            } else {
+                return 1;
+            }
+        }
+    }
+}
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java	Thu Feb 05 19:17:47 2015 +0100
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java	Fri Feb 06 10:09:13 2015 +0100
@@ -29,13 +29,13 @@
 
 import java.util.*;
 
-import com.oracle.graal.alloc.*;
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.code.CompilationResult.ConstantReference;
 import com.oracle.graal.api.code.CompilationResult.DataPatch;
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.api.meta.ProfilingInfo.TriState;
 import com.oracle.graal.compiler.alloc.*;
+import com.oracle.graal.compiler.common.alloc.*;
 import com.oracle.graal.compiler.common.cfg.*;
 import com.oracle.graal.compiler.target.*;
 import com.oracle.graal.debug.*;
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScan.java	Thu Feb 05 19:17:47 2015 +0100
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScan.java	Fri Feb 06 10:09:13 2015 +0100
@@ -31,13 +31,13 @@
 
 import java.util.*;
 
-import com.oracle.graal.alloc.*;
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.compiler.alloc.Interval.RegisterBinding;
 import com.oracle.graal.compiler.alloc.Interval.RegisterPriority;
 import com.oracle.graal.compiler.alloc.Interval.SpillState;
 import com.oracle.graal.compiler.common.*;
+import com.oracle.graal.compiler.common.alloc.*;
 import com.oracle.graal.compiler.common.cfg.*;
 import com.oracle.graal.compiler.common.util.*;
 import com.oracle.graal.debug.*;
--- a/mx/suite.py	Thu Feb 05 19:17:47 2015 +0100
+++ b/mx/suite.py	Fri Feb 06 10:09:13 2015 +0100
@@ -577,15 +577,6 @@
       "workingSets" : "Graal,LIR,SPARC",
     },
 
-    "com.oracle.graal.alloc" : {
-      "subDir" : "graal",
-      "sourceDirs" : ["src"],
-      "dependencies" : ["com.oracle.graal.compiler.common"],
-      "checkstyle" : "com.oracle.graal.graph",
-      "javaCompliance" : "1.8",
-      "workingSets" : "Graal",
-    },
-
     "com.oracle.graal.word" : {
       "subDir" : "graal",
       "sourceDirs" : ["src"],
@@ -738,7 +729,6 @@
       "dependencies" : [
         "com.oracle.graal.virtual",
         "com.oracle.graal.loop",
-        "com.oracle.graal.alloc",
       ],
       "checkstyle" : "com.oracle.graal.graph",
       "javaCompliance" : "1.8",