# HG changeset patch # User Josef Eisl # Date 1423213753 -3600 # Node ID b3b81dfff200f1d93ef0ab1e552f7975bd0b52f7 # Parent b215b88e215f8e0e8e6f4041db4d4f48f0a7f4b7 Move ComputeBlockOrder to compiler.common and delete c.o.g.alloc project. diff -r b215b88e215f -r b3b81dfff200 graal/com.oracle.graal.alloc/overview.html --- 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 @@ - - - - - - - - -Documentation for the com.oracle.graal.alloc project. - - - diff -r b215b88e215f -r b3b81dfff200 graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java --- 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 > List computeLinearScanOrder(int blockCount, T startBlock) { - List order = new ArrayList<>(); - BitSet visitedBlocks = new BitSet(blockCount); - PriorityQueue 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 > List computeCodeEmittingOrder(int blockCount, T startBlock) { - List order = new ArrayList<>(); - BitSet visitedBlocks = new BitSet(blockCount); - PriorityQueue 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 > void computeCodeEmittingOrder(List order, PriorityQueue 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 > void computeLinearScanOrder(List order, PriorityQueue 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 > PriorityQueue initializeWorklist(T startBlock, BitSet visitedBlocks) { - PriorityQueue 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 > void addPathToLinearScanOrder(T block, List order, PriorityQueue 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 > void addPathToCodeEmittingOrder(T initialBlock, List order, PriorityQueue 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 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 > void addBlock(T header, List 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 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 > void enqueueSuccessors(T block, PriorityQueue 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 > boolean skipLoopHeader(AbstractBlock 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> 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> implements Comparator { - - @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; - } - } - } -} diff -r b215b88e215f -r b3b81dfff200 graal/com.oracle.graal.baseline/src/com/oracle/graal/baseline/BaselineBytecodeParser.java --- 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.*; diff -r b215b88e215f -r b3b81dfff200 graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/alloc/ComputeBlockOrder.java --- /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 > List computeLinearScanOrder(int blockCount, T startBlock) { + List order = new ArrayList<>(); + BitSet visitedBlocks = new BitSet(blockCount); + PriorityQueue 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 > List computeCodeEmittingOrder(int blockCount, T startBlock) { + List order = new ArrayList<>(); + BitSet visitedBlocks = new BitSet(blockCount); + PriorityQueue 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 > void computeCodeEmittingOrder(List order, PriorityQueue 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 > void computeLinearScanOrder(List order, PriorityQueue 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 > PriorityQueue initializeWorklist(T startBlock, BitSet visitedBlocks) { + PriorityQueue 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 > void addPathToLinearScanOrder(T block, List order, PriorityQueue 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 > void addPathToCodeEmittingOrder(T initialBlock, List order, PriorityQueue 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 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 > void addBlock(T header, List 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 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 > void enqueueSuccessors(T block, PriorityQueue 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 > boolean skipLoopHeader(AbstractBlock 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> 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> implements Comparator { + + @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; + } + } + } +} diff -r b215b88e215f -r b3b81dfff200 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java --- 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.*; diff -r b215b88e215f -r b3b81dfff200 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScan.java --- 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.*; diff -r b215b88e215f -r b3b81dfff200 mx/suite.py --- 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",