Mercurial > hg > graal-compiler

changeset 23340:2e1f11dec368

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
TraceRA: rename TraceBuilder to UniDirectionalTraceBuilder.
author Josef Eisl <josef.eisl@jku.at>
date Wed, 20 Jan 2016 12:12:37 +0100
parents dd20a3a6b24f
children 0a7b897ae48a
files graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/alloc/TraceBuilder.java graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/alloc/UniDirectionalTraceBuilder.java graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceBuilderPhase.java
diffstat 3 files changed, 163 insertions(+), 160 deletions(-) [+]
line wrap: on
line diff
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/alloc/TraceBuilder.java	Wed Jan 20 11:59:13 2016 +0100
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,158 +0,0 @@
-/*
- * Copyright (c) 2015, 2015, 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.ArrayList;
-import java.util.BitSet;
-import java.util.List;
-import java.util.PriorityQueue;
-
-import com.oracle.graal.compiler.common.cfg.AbstractBlockBase;
-import com.oracle.graal.debug.Debug;
-import com.oracle.graal.debug.Indent;
-
-public final class TraceBuilder<T extends AbstractBlockBase<T>> {
-
-    public static <T extends AbstractBlockBase<T>> TraceBuilderResult<T> computeTraces(T startBlock, List<T> blocks) {
-        return new TraceBuilder<>(blocks).build(startBlock);
-    }
-
-    private final PriorityQueue<T> worklist;
-    private final BitSet processed;
-    /**
-     * Contains the number of unprocessed predecessors for every {@link AbstractBlockBase#getId()
-     * block}.
-     */
-    private final int[] blocked;
-    private final int[] blockToTrace;
-
-    private TraceBuilder(List<T> blocks) {
-        processed = new BitSet(blocks.size());
-        worklist = createQueue();
-        assert (worklist != null);
-
-        blocked = new int[blocks.size()];
-        blockToTrace = new int[blocks.size()];
-        for (T block : blocks) {
-            blocked[block.getId()] = block.getPredecessorCount();
-        }
-    }
-
-    @SuppressWarnings("unchecked")
-    private PriorityQueue<T> createQueue() {
-        return (PriorityQueue<T>) new PriorityQueue<AbstractBlockBase<?>>(TraceBuilder::compare);
-    }
-
-    private static int compare(AbstractBlockBase<?> a, AbstractBlockBase<?> b) {
-        return Double.compare(b.probability(), a.probability());
-    }
-
-    private boolean processed(T b) {
-        return processed.get(b.getId());
-    }
-
-    @SuppressWarnings("try")
-    private TraceBuilderResult<T> build(T startBlock) {
-        try (Indent indent = Debug.logAndIndent("start trace building: " + startBlock)) {
-            ArrayList<Trace<T>> traces = buildTraces(startBlock);
-            return new TraceBuilderResult<>(traces, blockToTrace);
-        }
-    }
-
-    protected ArrayList<Trace<T>> buildTraces(T startBlock) {
-        ArrayList<Trace<T>> traces = new ArrayList<>();
-        // add start block
-        worklist.add(startBlock);
-        // process worklist
-        while (!worklist.isEmpty()) {
-            T block = worklist.poll();
-            assert block != null;
-            if (!processed(block)) {
-                traces.add(new Trace<>(startTrace(block, traces.size())));
-            }
-        }
-        return traces;
-    }
-
-    /**
-     * Build a new trace starting at {@code block}.
-     */
-    @SuppressWarnings("try")
-    private List<T> startTrace(T block, int traceNumber) {
-        assert checkPredecessorsProcessed(block);
-        ArrayList<T> trace = new ArrayList<>();
-        int blockNumber = 0;
-        try (Indent i = Debug.logAndIndent("StartTrace: " + block)) {
-            for (T currentBlock = block; currentBlock != null; currentBlock = selectNext(currentBlock)) {
-                Debug.log("add %s (prob: %f)", currentBlock, currentBlock.probability());
-                processed.set(currentBlock.getId());
-                trace.add(currentBlock);
-                unblock(currentBlock);
-                currentBlock.setLinearScanNumber(blockNumber++);
-                blockToTrace[currentBlock.getId()] = traceNumber;
-            }
-        }
-        return trace;
-    }
-
-    private boolean checkPredecessorsProcessed(T block) {
-        List<T> predecessors = block.getPredecessors();
-        for (T pred : predecessors) {
-            if (!processed(pred)) {
-                assert false : "Predecessor unscheduled: " + pred;
-                return false;
-            }
-
-        }
-        return true;
-    }
-
-    /**
-     * Decrease the {@link #blocked} count for all predecessors and add them to the worklist once
-     * the count reaches 0.
-     */
-    private void unblock(T currentBlock) {
-        for (T successor : currentBlock.getSuccessors()) {
-            if (!processed(successor)) {
-                int blockCount = --blocked[successor.getId()];
-                assert blockCount >= 0;
-                if (blockCount == 0) {
-                    worklist.add(successor);
-                }
-            }
-        }
-    }
-
-    /**
-     * @return The unprocessed predecessor with the highest probability, or {@code null}.
-     */
-    private T selectNext(T currentBlock) {
-        T next = null;
-        for (T succ : currentBlock.getSuccessors()) {
-            if (!processed(succ) && (next == null || succ.probability() > next.probability())) {
-                next = succ;
-            }
-        }
-        return next;
-    }
-}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/alloc/UniDirectionalTraceBuilder.java	Wed Jan 20 12:12:37 2016 +0100
@@ -0,0 +1,161 @@
+/*
+ * Copyright (c) 2015, 2015, 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.ArrayList;
+import java.util.BitSet;
+import java.util.List;
+import java.util.PriorityQueue;
+
+import com.oracle.graal.compiler.common.cfg.AbstractBlockBase;
+import com.oracle.graal.debug.Debug;
+import com.oracle.graal.debug.Indent;
+
+/**
+ * Computes traces by starting at a trace head and keep adding predecessors as long as possible.
+ */
+public final class UniDirectionalTraceBuilder<T extends AbstractBlockBase<T>> {
+
+    public static <T extends AbstractBlockBase<T>> TraceBuilderResult<T> computeTraces(T startBlock, List<T> blocks) {
+        return new UniDirectionalTraceBuilder<>(blocks).build(startBlock);
+    }
+
+    private final PriorityQueue<T> worklist;
+    private final BitSet processed;
+    /**
+     * Contains the number of unprocessed predecessors for every {@link AbstractBlockBase#getId()
+     * block}.
+     */
+    private final int[] blocked;
+    private final int[] blockToTrace;
+
+    private UniDirectionalTraceBuilder(List<T> blocks) {
+        processed = new BitSet(blocks.size());
+        worklist = createQueue();
+        assert (worklist != null);
+
+        blocked = new int[blocks.size()];
+        blockToTrace = new int[blocks.size()];
+        for (T block : blocks) {
+            blocked[block.getId()] = block.getPredecessorCount();
+        }
+    }
+
+    @SuppressWarnings("unchecked")
+    private PriorityQueue<T> createQueue() {
+        return (PriorityQueue<T>) new PriorityQueue<AbstractBlockBase<?>>(UniDirectionalTraceBuilder::compare);
+    }
+
+    private static int compare(AbstractBlockBase<?> a, AbstractBlockBase<?> b) {
+        return Double.compare(b.probability(), a.probability());
+    }
+
+    private boolean processed(T b) {
+        return processed.get(b.getId());
+    }
+
+    @SuppressWarnings("try")
+    private TraceBuilderResult<T> build(T startBlock) {
+        try (Indent indent = Debug.logAndIndent("start trace building: " + startBlock)) {
+            ArrayList<Trace<T>> traces = buildTraces(startBlock);
+            return new TraceBuilderResult<>(traces, blockToTrace);
+        }
+    }
+
+    protected ArrayList<Trace<T>> buildTraces(T startBlock) {
+        ArrayList<Trace<T>> traces = new ArrayList<>();
+        // add start block
+        worklist.add(startBlock);
+        // process worklist
+        while (!worklist.isEmpty()) {
+            T block = worklist.poll();
+            assert block != null;
+            if (!processed(block)) {
+                traces.add(new Trace<>(startTrace(block, traces.size())));
+            }
+        }
+        return traces;
+    }
+
+    /**
+     * Build a new trace starting at {@code block}.
+     */
+    @SuppressWarnings("try")
+    private List<T> startTrace(T block, int traceNumber) {
+        assert checkPredecessorsProcessed(block);
+        ArrayList<T> trace = new ArrayList<>();
+        int blockNumber = 0;
+        try (Indent i = Debug.logAndIndent("StartTrace: " + block)) {
+            for (T currentBlock = block; currentBlock != null; currentBlock = selectNext(currentBlock)) {
+                Debug.log("add %s (prob: %f)", currentBlock, currentBlock.probability());
+                processed.set(currentBlock.getId());
+                trace.add(currentBlock);
+                unblock(currentBlock);
+                currentBlock.setLinearScanNumber(blockNumber++);
+                blockToTrace[currentBlock.getId()] = traceNumber;
+            }
+        }
+        return trace;
+    }
+
+    private boolean checkPredecessorsProcessed(T block) {
+        List<T> predecessors = block.getPredecessors();
+        for (T pred : predecessors) {
+            if (!processed(pred)) {
+                assert false : "Predecessor unscheduled: " + pred;
+                return false;
+            }
+
+        }
+        return true;
+    }
+
+    /**
+     * Decrease the {@link #blocked} count for all predecessors and add them to the worklist once
+     * the count reaches 0.
+     */
+    private void unblock(T currentBlock) {
+        for (T successor : currentBlock.getSuccessors()) {
+            if (!processed(successor)) {
+                int blockCount = --blocked[successor.getId()];
+                assert blockCount >= 0;
+                if (blockCount == 0) {
+                    worklist.add(successor);
+                }
+            }
+        }
+    }
+
+    /**
+     * @return The unprocessed predecessor with the highest probability, or {@code null}.
+     */
+    private T selectNext(T currentBlock) {
+        T next = null;
+        for (T succ : currentBlock.getSuccessors()) {
+            if (!processed(succ) && (next == null || succ.probability() > next.probability())) {
+                next = succ;
+            }
+        }
+        return next;
+    }
+}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceBuilderPhase.java	Wed Jan 20 11:59:13 2016 +0100
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceBuilderPhase.java	Wed Jan 20 12:12:37 2016 +0100
@@ -24,8 +24,8 @@
 
 import java.util.List;
 
-import com.oracle.graal.compiler.common.alloc.TraceBuilder;
 import com.oracle.graal.compiler.common.alloc.TraceBuilderResult;
+import com.oracle.graal.compiler.common.alloc.UniDirectionalTraceBuilder;
 import com.oracle.graal.compiler.common.cfg.AbstractBlockBase;
 import com.oracle.graal.lir.LIR;
 import com.oracle.graal.lir.gen.LIRGenerationResult;
@@ -45,7 +45,7 @@
         B startBlock = linearScanOrder.get(0);
         LIR lir = lirGenRes.getLIR();
         assert startBlock.equals(lir.getControlFlowGraph().getStartBlock());
-        context.traceBuilderResult = TraceBuilder.computeTraces(startBlock, linearScanOrder);
+        context.traceBuilderResult = UniDirectionalTraceBuilder.computeTraces(startBlock, linearScanOrder);
 
     }