Mercurial > hg > truffle
changeset 14146:59460dd271a5
Add experimental AbstractBlock interface to make ComputeBlockOrder generic.
author | Thomas Wuerthinger <thomas.wuerthinger@oracle.com> |
---|---|
date | Tue, 11 Mar 2014 17:43:29 +0100 |
parents | 4ff08c0366ae |
children | 594ee32296ff |
files | graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/AbstractBlock.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/Block.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/NodesToDoubles.java |
diffstat | 5 files changed, 95 insertions(+), 30 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java Tue Mar 11 16:55:57 2014 +0100 +++ b/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java Tue Mar 11 17:43:29 2014 +0100 @@ -67,10 +67,10 @@ * * @return sorted list of blocks */ - public static List<Block> computeLinearScanOrder(int blockCount, Block startBlock, NodesToDoubles nodeProbabilities) { - List<Block> order = new ArrayList<>(); + public static <T extends AbstractBlock<T>> List<T> computeLinearScanOrder(int blockCount, T startBlock, NodesToDoubles nodeProbabilities) { + List<T> order = new ArrayList<>(); BitSet visitedBlocks = new BitSet(blockCount); - PriorityQueue<Block> worklist = initializeWorklist(startBlock, visitedBlocks, nodeProbabilities); + PriorityQueue<T> worklist = initializeWorklist(startBlock, visitedBlocks, nodeProbabilities); computeLinearScanOrder(order, worklist, visitedBlocks, nodeProbabilities); assert checkOrder(order, blockCount); return order; @@ -81,10 +81,10 @@ * * @return sorted list of blocks */ - public static List<Block> computeCodeEmittingOrder(int blockCount, Block startBlock, NodesToDoubles nodeProbabilities) { - List<Block> order = new ArrayList<>(); + public static <T extends AbstractBlock<T>> List<T> computeCodeEmittingOrder(int blockCount, T startBlock, NodesToDoubles nodeProbabilities) { + List<T> order = new ArrayList<>(); BitSet visitedBlocks = new BitSet(blockCount); - PriorityQueue<Block> worklist = initializeWorklist(startBlock, visitedBlocks, nodeProbabilities); + PriorityQueue<T> worklist = initializeWorklist(startBlock, visitedBlocks, nodeProbabilities); computeCodeEmittingOrder(order, worklist, visitedBlocks, nodeProbabilities); assert checkOrder(order, blockCount); return order; @@ -93,9 +93,9 @@ /** * Iteratively adds paths to the code emission block order. */ - private static void computeCodeEmittingOrder(List<Block> order, PriorityQueue<Block> worklist, BitSet visitedBlocks, NodesToDoubles nodeProbabilities) { + private static <T extends AbstractBlock<T>> void computeCodeEmittingOrder(List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks, NodesToDoubles nodeProbabilities) { while (!worklist.isEmpty()) { - Block nextImportantPath = worklist.poll(); + T nextImportantPath = worklist.poll(); addPathToCodeEmittingOrder(nextImportantPath, order, worklist, visitedBlocks, nodeProbabilities); } } @@ -103,9 +103,9 @@ /** * Iteratively adds paths to the linear scan block order. */ - private static void computeLinearScanOrder(List<Block> order, PriorityQueue<Block> worklist, BitSet visitedBlocks, NodesToDoubles nodeProbabilities) { + private static <T extends AbstractBlock<T>> void computeLinearScanOrder(List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks, NodesToDoubles nodeProbabilities) { while (!worklist.isEmpty()) { - Block nextImportantPath = worklist.poll(); + T nextImportantPath = worklist.poll(); addPathToLinearScanOrder(nextImportantPath, order, worklist, visitedBlocks, nodeProbabilities); } } @@ -113,8 +113,9 @@ /** * Initializes the priority queue used for the work list of blocks and adds the start block. */ - private static PriorityQueue<Block> initializeWorklist(Block startBlock, BitSet visitedBlocks, NodesToDoubles nodeProbabilities) { - PriorityQueue<Block> result = new PriorityQueue<>(INITIAL_WORKLIST_CAPACITY, new BlockOrderComparator(nodeProbabilities)); + @SuppressWarnings("unchecked") + private static <T extends AbstractBlock<T>> PriorityQueue<T> initializeWorklist(T startBlock, BitSet visitedBlocks, NodesToDoubles nodeProbabilities) { + PriorityQueue<T> result = new PriorityQueue<>(INITIAL_WORKLIST_CAPACITY, new BlockOrderComparator(nodeProbabilities)); result.add(startBlock); visitedBlocks.set(startBlock.getId()); return result; @@ -123,17 +124,17 @@ /** * Add a linear path to the linear scan order greedily following the most likely successor. */ - private static void addPathToLinearScanOrder(Block block, List<Block> order, PriorityQueue<Block> worklist, BitSet visitedBlocks, NodesToDoubles nodeProbabilities) { + private static <T extends AbstractBlock<T>> void addPathToLinearScanOrder(T block, List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks, NodesToDoubles nodeProbabilities) { block.setLinearScanNumber(order.size()); order.add(block); - Block mostLikelySuccessor = findAndMarkMostLikelySuccessor(block, visitedBlocks, nodeProbabilities); + T mostLikelySuccessor = findAndMarkMostLikelySuccessor(block, visitedBlocks, nodeProbabilities); 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 (Block pred : mostLikelySuccessor.getPredecessors()) { + for (T pred : mostLikelySuccessor.getPredecessors()) { if (pred.getLinearScanNumber() == -1) { unscheduledSum += nodeProbabilities.get(pred.getBeginNode()); } @@ -152,8 +153,9 @@ /** * Add a linear path to the code emission order greedily following the most likely successor. */ - private static void addPathToCodeEmittingOrder(Block initialBlock, List<Block> order, PriorityQueue<Block> worklist, BitSet visitedBlocks, NodesToDoubles nodeProbabilities) { - Block block = initialBlock; + @SuppressWarnings("unchecked") + private static <T extends AbstractBlock<T>> void addPathToCodeEmittingOrder(T initialBlock, List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks, NodesToDoubles nodeProbabilities) { + 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. @@ -171,7 +173,7 @@ // This is the only loop end of a skipped loop header. // Add the header immediately afterwards. - addBlock(loop.header, order); + addBlock((T) loop.header, order); // Make sure the loop successors of the loop header are aligned // as they are the target @@ -183,7 +185,7 @@ } } - Block mostLikelySuccessor = findAndMarkMostLikelySuccessor(block, visitedBlocks, nodeProbabilities); + T mostLikelySuccessor = findAndMarkMostLikelySuccessor(block, visitedBlocks, nodeProbabilities); enqueueSuccessors(block, worklist, visitedBlocks); block = mostLikelySuccessor; } @@ -192,7 +194,7 @@ /** * Adds a block to the ordering. */ - private static void addBlock(Block header, List<Block> order) { + private static <T extends AbstractBlock<T>> void addBlock(T header, List<T> order) { assert !order.contains(header) : "Cannot insert block twice"; order.add(header); } @@ -200,9 +202,9 @@ /** * Find the highest likely unvisited successor block of a given block. */ - private static Block findAndMarkMostLikelySuccessor(Block block, BitSet visitedBlocks, NodesToDoubles nodeProbabilities) { - Block result = null; - for (Block successor : block.getSuccessors()) { + private static <T extends AbstractBlock<T>> T findAndMarkMostLikelySuccessor(T block, BitSet visitedBlocks, NodesToDoubles nodeProbabilities) { + T result = null; + for (T successor : block.getSuccessors()) { assert nodeProbabilities.get(successor.getBeginNode()) >= 0.0 : "Probabilities must be positive"; if (!visitedBlocks.get(successor.getId()) && successor.getLoopDepth() >= block.getLoopDepth() && (result == null || nodeProbabilities.get(successor.getBeginNode()) >= nodeProbabilities.get(result.getBeginNode()))) { @@ -218,8 +220,8 @@ /** * Add successor blocks into the given work list if they are not already marked as visited. */ - private static void enqueueSuccessors(Block block, PriorityQueue<Block> worklist, BitSet visitedBlocks) { - for (Block successor : block.getSuccessors()) { + 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); @@ -231,14 +233,14 @@ * 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(Block block) { + private static boolean skipLoopHeader(AbstractBlock block) { return (block.isLoopHeader() && !block.isLoopEnd() && block.getLoop().loopBegin().loopEnds().count() == 1); } /** * Checks that the ordering contains the expected number of blocks. */ - private static boolean checkOrder(List<Block> order, int expectedBlockCount) { + 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; } @@ -246,7 +248,7 @@ /** * Comparator for sorting blocks based on loop depth and probability. */ - private static class BlockOrderComparator implements Comparator<Block> { + private static class BlockOrderComparator<T extends AbstractBlock<T>> implements Comparator<T> { private final NodesToDoubles probabilities; @@ -255,7 +257,7 @@ } @Override - public int compare(Block a, Block b) { + public int compare(T a, T b) { // Loop blocks before any loop exit block. int diff = b.getLoopDepth() - a.getLoopDepth(); if (diff != 0) {
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Tue Mar 11 16:55:57 2014 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Tue Mar 11 17:43:29 2014 +0100 @@ -242,6 +242,7 @@ try (Scope ds = Debug.scope("MidEnd")) { try (Scope s = Debug.scope("ComputeLinearScanOrder")) { NodesToDoubles nodeProbabilities = new ComputeProbabilityClosure(graph).apply(); + System.out.printf("%d, %d\n", nodeProbabilities.getCount(), graph.getNodeCount()); List<Block> codeEmittingOrder = ComputeBlockOrder.computeCodeEmittingOrder(blocks.length, startBlock, nodeProbabilities); List<Block> linearScanOrder = ComputeBlockOrder.computeLinearScanOrder(blocks.length, startBlock, nodeProbabilities);
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/AbstractBlock.java Tue Mar 11 17:43:29 2014 +0100 @@ -0,0 +1,58 @@ +/* + * Copyright (c) 2014, 2014, 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.nodes.cfg; + +import com.oracle.graal.nodes.*; + +public interface AbstractBlock<T extends AbstractBlock> { + + int getId(); + + AbstractBeginNode getBeginNode(); + + Loop getLoop(); + + int getLoopDepth(); + + boolean isLoopHeader(); + + boolean isLoopEnd(); + + boolean isExceptionEntry(); + + Iterable<T> getPredecessors(); + + int getPredecessorCount(); + + Iterable<T> getSuccessors(); + + int getSuccessorCount(); + + int getLinearScanNumber(); + + void setLinearScanNumber(int linearScanNumber); + + boolean isAligned(); + + void setAlign(boolean align); +}
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/Block.java Tue Mar 11 16:55:57 2014 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/Block.java Tue Mar 11 17:43:29 2014 +0100 @@ -27,7 +27,7 @@ import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.java.*; -public final class Block { +public final class Block implements AbstractBlock<Block> { protected final AbstractBeginNode beginNode;
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/NodesToDoubles.java Tue Mar 11 16:55:57 2014 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/NodesToDoubles.java Tue Mar 11 17:43:29 2014 +0100 @@ -48,4 +48,8 @@ assert value != null; return value; } + + public int getCount() { + return nodeProbabilities.size(); + } }