# HG changeset patch # User Josef Eisl # Date 1453288357 -3600 # Node ID 2e1f11dec368967e12ff63dc181105e583bc3e68 # Parent dd20a3a6b24f5bda3530514a8a7f837194830cb1 TraceRA: rename TraceBuilder to UniDirectionalTraceBuilder. diff -r dd20a3a6b24f -r 2e1f11dec368 graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/alloc/TraceBuilder.java --- 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> { - - public static > TraceBuilderResult computeTraces(T startBlock, List blocks) { - return new TraceBuilder<>(blocks).build(startBlock); - } - - private final PriorityQueue 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 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 createQueue() { - return (PriorityQueue) new PriorityQueue>(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 build(T startBlock) { - try (Indent indent = Debug.logAndIndent("start trace building: " + startBlock)) { - ArrayList> traces = buildTraces(startBlock); - return new TraceBuilderResult<>(traces, blockToTrace); - } - } - - protected ArrayList> buildTraces(T startBlock) { - ArrayList> 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 startTrace(T block, int traceNumber) { - assert checkPredecessorsProcessed(block); - ArrayList 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 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; - } -} diff -r dd20a3a6b24f -r 2e1f11dec368 graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/alloc/UniDirectionalTraceBuilder.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/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> { + + public static > TraceBuilderResult computeTraces(T startBlock, List blocks) { + return new UniDirectionalTraceBuilder<>(blocks).build(startBlock); + } + + private final PriorityQueue 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 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 createQueue() { + return (PriorityQueue) new PriorityQueue>(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 build(T startBlock) { + try (Indent indent = Debug.logAndIndent("start trace building: " + startBlock)) { + ArrayList> traces = buildTraces(startBlock); + return new TraceBuilderResult<>(traces, blockToTrace); + } + } + + protected ArrayList> buildTraces(T startBlock) { + ArrayList> 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 startTrace(T block, int traceNumber) { + assert checkPredecessorsProcessed(block); + ArrayList 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 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; + } +} diff -r dd20a3a6b24f -r 2e1f11dec368 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceBuilderPhase.java --- 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); }