Mercurial > hg > truffle

changeset 14146:59460dd271a5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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();
+    }
 }