# HG changeset patch # User Josef Eisl # Date 1394727383 -3600 # Node ID cc2f1661f4735596b9b8015c7b9d1e469f6d3404 # Parent 18d5ffb7ac38662c1098bc551018a072f70b15ba Create BlocksToDoubles and use it in the backend. diff -r 18d5ffb7ac38 -r cc2f1661f473 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 Mar 13 17:11:16 2014 +0100 +++ b/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java Thu Mar 13 17:16:23 2014 +0100 @@ -26,7 +26,6 @@ import java.util.*; import com.oracle.graal.nodes.cfg.*; -import com.oracle.graal.nodes.util.*; /** * Computes an ordering of the block that can be used by the linear scan register allocator and the @@ -67,11 +66,11 @@ * * @return sorted list of blocks */ - public static > List computeLinearScanOrder(int blockCount, T startBlock, NodesToDoubles nodeProbabilities) { + public static > List computeLinearScanOrder(int blockCount, T startBlock, BlocksToDoubles blockProbabilities) { List order = new ArrayList<>(); BitSet visitedBlocks = new BitSet(blockCount); - PriorityQueue worklist = initializeWorklist(startBlock, visitedBlocks, nodeProbabilities); - computeLinearScanOrder(order, worklist, visitedBlocks, nodeProbabilities); + PriorityQueue worklist = initializeWorklist(startBlock, visitedBlocks, blockProbabilities); + computeLinearScanOrder(order, worklist, visitedBlocks, blockProbabilities); assert checkOrder(order, blockCount); return order; } @@ -81,11 +80,11 @@ * * @return sorted list of blocks */ - public static > List computeCodeEmittingOrder(int blockCount, T startBlock, NodesToDoubles nodeProbabilities) { + public static > List computeCodeEmittingOrder(int blockCount, T startBlock, BlocksToDoubles blockProbabilities) { List order = new ArrayList<>(); BitSet visitedBlocks = new BitSet(blockCount); - PriorityQueue worklist = initializeWorklist(startBlock, visitedBlocks, nodeProbabilities); - computeCodeEmittingOrder(order, worklist, visitedBlocks, nodeProbabilities); + PriorityQueue worklist = initializeWorklist(startBlock, visitedBlocks, blockProbabilities); + computeCodeEmittingOrder(order, worklist, visitedBlocks, blockProbabilities); assert checkOrder(order, blockCount); return order; } @@ -93,28 +92,28 @@ /** * Iteratively adds paths to the code emission block order. */ - private static > void computeCodeEmittingOrder(List order, PriorityQueue worklist, BitSet visitedBlocks, NodesToDoubles nodeProbabilities) { + private static > void computeCodeEmittingOrder(List order, PriorityQueue worklist, BitSet visitedBlocks, BlocksToDoubles blockProbabilities) { while (!worklist.isEmpty()) { T nextImportantPath = worklist.poll(); - addPathToCodeEmittingOrder(nextImportantPath, order, worklist, visitedBlocks, nodeProbabilities); + addPathToCodeEmittingOrder(nextImportantPath, order, worklist, visitedBlocks, blockProbabilities); } } /** * Iteratively adds paths to the linear scan block order. */ - private static > void computeLinearScanOrder(List order, PriorityQueue worklist, BitSet visitedBlocks, NodesToDoubles nodeProbabilities) { + private static > void computeLinearScanOrder(List order, PriorityQueue worklist, BitSet visitedBlocks, BlocksToDoubles blockProbabilities) { while (!worklist.isEmpty()) { T nextImportantPath = worklist.poll(); - addPathToLinearScanOrder(nextImportantPath, order, worklist, visitedBlocks, nodeProbabilities); + addPathToLinearScanOrder(nextImportantPath, order, worklist, visitedBlocks, blockProbabilities); } } /** * Initializes the priority queue used for the work list of blocks and adds the start block. */ - private static > PriorityQueue initializeWorklist(T startBlock, BitSet visitedBlocks, NodesToDoubles nodeProbabilities) { - PriorityQueue result = new PriorityQueue<>(INITIAL_WORKLIST_CAPACITY, new BlockOrderComparator(nodeProbabilities)); + private static > PriorityQueue initializeWorklist(T startBlock, BitSet visitedBlocks, BlocksToDoubles blockProbabilities) { + PriorityQueue result = new PriorityQueue<>(INITIAL_WORKLIST_CAPACITY, new BlockOrderComparator(blockProbabilities)); result.add(startBlock); visitedBlocks.set(startBlock.getId()); return result; @@ -123,10 +122,10 @@ /** * 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, NodesToDoubles nodeProbabilities) { + private static > void addPathToLinearScanOrder(T block, List order, PriorityQueue worklist, BitSet visitedBlocks, BlocksToDoubles blockProbabilities) { block.setLinearScanNumber(order.size()); order.add(block); - T mostLikelySuccessor = findAndMarkMostLikelySuccessor(block, visitedBlocks, nodeProbabilities); + T mostLikelySuccessor = findAndMarkMostLikelySuccessor(block, visitedBlocks, blockProbabilities); enqueueSuccessors(block, worklist, visitedBlocks); if (mostLikelySuccessor != null) { if (!mostLikelySuccessor.isLoopHeader() && mostLikelySuccessor.getPredecessorCount() > 1) { @@ -135,17 +134,17 @@ double unscheduledSum = 0.0; for (T pred : mostLikelySuccessor.getPredecessors()) { if (pred.getLinearScanNumber() == -1) { - unscheduledSum += nodeProbabilities.get(pred.getBeginNode()); + unscheduledSum += blockProbabilities.get(pred); } } - if (unscheduledSum > nodeProbabilities.get(block.getBeginNode()) / PENALTY_VERSUS_UNSCHEDULED) { + if (unscheduledSum > blockProbabilities.get(block) / 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, nodeProbabilities); + addPathToLinearScanOrder(mostLikelySuccessor, order, worklist, visitedBlocks, blockProbabilities); } } @@ -153,7 +152,7 @@ * Add a linear path to the code emission order greedily following the most likely successor. */ @SuppressWarnings("unchecked") - private static > void addPathToCodeEmittingOrder(T initialBlock, List order, PriorityQueue worklist, BitSet visitedBlocks, NodesToDoubles nodeProbabilities) { + private static > void addPathToCodeEmittingOrder(T initialBlock, List order, PriorityQueue worklist, BitSet visitedBlocks, BlocksToDoubles blockProbabilities) { T block = initialBlock; while (block != null) { // Skip loop headers if there is only a single loop end block to @@ -184,7 +183,7 @@ } } - T mostLikelySuccessor = findAndMarkMostLikelySuccessor(block, visitedBlocks, nodeProbabilities); + T mostLikelySuccessor = findAndMarkMostLikelySuccessor(block, visitedBlocks, blockProbabilities); enqueueSuccessors(block, worklist, visitedBlocks); block = mostLikelySuccessor; } @@ -201,12 +200,11 @@ /** * Find the highest likely unvisited successor block of a given block. */ - private static > T findAndMarkMostLikelySuccessor(T block, BitSet visitedBlocks, NodesToDoubles nodeProbabilities) { + private static > T findAndMarkMostLikelySuccessor(T block, BitSet visitedBlocks, BlocksToDoubles blockProbabilities) { 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()))) { + assert blockProbabilities.get(successor) >= 0.0 : "Probabilities must be positive"; + if (!visitedBlocks.get(successor.getId()) && successor.getLoopDepth() >= block.getLoopDepth() && (result == null || blockProbabilities.get(successor) >= blockProbabilities.get(result))) { result = successor; } } @@ -249,9 +247,9 @@ */ private static class BlockOrderComparator> implements Comparator { - private final NodesToDoubles probabilities; + private final BlocksToDoubles probabilities; - public BlockOrderComparator(NodesToDoubles probabilities) { + public BlockOrderComparator(BlocksToDoubles probabilities) { this.probabilities = probabilities; } @@ -264,7 +262,7 @@ } // Blocks with high probability before blocks with low probability. - if (probabilities.get(a.getBeginNode()) > probabilities.get(b.getBeginNode())) { + if (probabilities.get(a) > probabilities.get(b)) { return -1; } else { return 1; diff -r 18d5ffb7ac38 -r cc2f1661f473 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 Mar 13 17:11:16 2014 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Thu Mar 13 17:16:23 2014 +0100 @@ -244,8 +244,9 @@ try (Scope ds = Debug.scope("MidEnd")) { try (Scope s = Debug.scope("ComputeLinearScanOrder")) { NodesToDoubles nodeProbabilities = new ComputeProbabilityClosure(graph).apply(); - codeEmittingOrder = ComputeBlockOrder.computeCodeEmittingOrder(blocks.length, startBlock, nodeProbabilities); - linearScanOrder = ComputeBlockOrder.computeLinearScanOrder(blocks.length, startBlock, nodeProbabilities); + BlocksToDoubles blockProbabilities = BlocksToDoubles.createFromNodeProbability(nodeProbabilities, schedule.getCFG()); + codeEmittingOrder = ComputeBlockOrder.computeCodeEmittingOrder(blocks.length, startBlock, blockProbabilities); + linearScanOrder = ComputeBlockOrder.computeLinearScanOrder(blocks.length, startBlock, blockProbabilities); lir = new LIR(schedule.getCFG(), linearScanOrder, codeEmittingOrder); Debug.dump(lir, "After linear scan order"); diff -r 18d5ffb7ac38 -r cc2f1661f473 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/BlocksToDoubles.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/BlocksToDoubles.java Thu Mar 13 17:16:23 2014 +0100 @@ -0,0 +1,73 @@ +/* + * Copyright (c) 2013, 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 java.util.*; + +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.util.*; + +public class BlocksToDoubles { + + private final IdentityHashMap, Double> nodeProbabilities; + + public BlocksToDoubles(int numberOfNodes) { + this.nodeProbabilities = new IdentityHashMap<>(numberOfNodes); + } + + public void put(AbstractBlock n, double value) { + assert value >= 0.0 : value; + nodeProbabilities.put(n, value); + } + + public boolean contains(AbstractBlock n) { + return nodeProbabilities.containsKey(n); + } + + public double get(AbstractBlock n) { + Double value = nodeProbabilities.get(n); + assert value != null; + return value; + } + + public static BlocksToDoubles createFromNodeProbability(NodesToDoubles nodeProbabilities, ControlFlowGraph cfg) { + BlocksToDoubles blockProbabilities = new BlocksToDoubles(cfg.getBlocks().length); + for (AbstractBlock block : cfg.getBlocks()) { + blockProbabilities.put(block, nodeProbabilities.get(block.getBeginNode())); + } + assert verify(nodeProbabilities, cfg, blockProbabilities) : "Probabilities differ for nodes in the same block."; + return blockProbabilities; + } + + static private boolean verify(NodesToDoubles nodeProbabilities, ControlFlowGraph cfg, BlocksToDoubles blockProbabilities) { + for (Block b : cfg.getBlocks()) { + double p = blockProbabilities.get(b); + for (FixedNode n : b.getNodes()) { + if (nodeProbabilities.get(n) != p) { + return false; + } + } + } + return true; + } +}