# HG changeset patch # User Josef Eisl # Date 1453287785 -3600 # Node ID 0a7b897ae48ae83dd049e826d9ce5555cfeddf3f # Parent 2e1f11dec368967e12ff63dc181105e583bc3e68 TraceRA: add BiDirectionalTraceBuilder. diff -r 2e1f11dec368 -r 0a7b897ae48a graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/alloc/BiDirectionalTraceBuilder.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/BiDirectionalTraceBuilder.java Wed Jan 20 12:03:05 2016 +0100 @@ -0,0 +1,161 @@ +/* + * Copyright (c) 2016, 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.ArrayDeque; +import java.util.ArrayList; +import java.util.BitSet; +import java.util.Collection; +import java.util.Deque; +import java.util.List; + +import com.oracle.graal.compiler.common.cfg.AbstractBlockBase; +import com.oracle.graal.debug.Debug; +import com.oracle.graal.debug.Indent; + +/** + * Computes traces by selecting the unhandled block with the highest execution frequency and going + * in both directions, up and down, as long as possible. + */ +public final class BiDirectionalTraceBuilder> { + + public static > TraceBuilderResult computeTraces(T startBlock, List blocks) { + return new BiDirectionalTraceBuilder<>(blocks).build(startBlock); + } + + private final Deque worklist; + private final BitSet processed; + private final int[] blockToTrace; + + private BiDirectionalTraceBuilder(List blocks) { + processed = new BitSet(blocks.size()); + worklist = createQueue(blocks); + blockToTrace = new int[blocks.size()]; + } + + private static > Deque createQueue(List blocks) { + ArrayList queue = new ArrayList<>(blocks); + queue.sort(BiDirectionalTraceBuilder::compare); + return new ArrayDeque<>(queue); + } + + 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.pollFirst(); + 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 Collection startTrace(T block, int traceNumber) { + ArrayDeque trace = new ArrayDeque<>(); + try (Indent i = Debug.logAndIndent("StartTrace: " + block)) { + try (Indent indentFront = Debug.logAndIndent("Head:")) { + for (T currentBlock = block; currentBlock != null; currentBlock = selectPredecessor(currentBlock)) { + addBlockToTrace(currentBlock, traceNumber); + trace.addFirst(currentBlock); + } + } + /* Number head blocks. Can not do this in the loop as we go backwards. */ + int blockNr = 0; + for (T b : trace) { + b.setLinearScanNumber(blockNr++); + } + + try (Indent indentBack = Debug.logAndIndent("Tail:")) { + for (T currentBlock = selectSuccessor(block); currentBlock != null; currentBlock = selectSuccessor(currentBlock)) { + addBlockToTrace(currentBlock, traceNumber); + trace.addLast(currentBlock); + /* This time we can number the blocks immediately as we go forwards. */ + currentBlock.setLinearScanNumber(blockNr++); + } + } + } + Debug.log("Trace: %s", trace); + return trace; + } + + private void addBlockToTrace(T currentBlock, int traceNumber) { + Debug.log("add %s (prob: %f)", currentBlock, currentBlock.probability()); + processed.set(currentBlock.getId()); + blockToTrace[currentBlock.getId()] = traceNumber; + } + + /** + * @return The unprocessed predecessor with the highest probability, or {@code null}. + */ + private T selectPredecessor(T currentBlock) { + T next = null; + for (T pred : currentBlock.getPredecessors()) { + if (!processed(pred) && !isBackEdge(pred, currentBlock) && (next == null || pred.probability() > next.probability())) { + next = pred; + } + } + return next; + } + + private boolean isBackEdge(T from, T to) { + assert from.getSuccessors().contains(to) : "No edge from " + from + " to " + to; + return from.isLoopEnd() && to.isLoopHeader() && from.getLoop().equals(to.getLoop()); + } + + /** + * @return The unprocessed successor with the highest probability, or {@code null}. + */ + private T selectSuccessor(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 2e1f11dec368 -r 0a7b897ae48a 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 12:12:37 2016 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceBuilderPhase.java Wed Jan 20 12:03:05 2016 +0100 @@ -24,17 +24,28 @@ import java.util.List; +import com.oracle.graal.compiler.common.alloc.UniDirectionalTraceBuilder; +import com.oracle.graal.compiler.common.alloc.BiDirectionalTraceBuilder; 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; import com.oracle.graal.lir.phases.LIRPhase; +import com.oracle.graal.options.Option; +import com.oracle.graal.options.OptionType; +import com.oracle.graal.options.OptionValue; import jdk.vm.ci.code.TargetDescription; public class TraceBuilderPhase extends LIRPhase { + public static class Options { + // @formatter:off + @Option(help = "", type = OptionType.Debug) + public static final OptionValue TraceRAbiDirectionalTraceBuilder = new OptionValue<>(false); + // @formatter:on + } + public static final class TraceBuilderContext { public TraceBuilderResult traceBuilderResult; @@ -45,7 +56,11 @@ B startBlock = linearScanOrder.get(0); LIR lir = lirGenRes.getLIR(); assert startBlock.equals(lir.getControlFlowGraph().getStartBlock()); - context.traceBuilderResult = UniDirectionalTraceBuilder.computeTraces(startBlock, linearScanOrder); + if (Options.TraceRAbiDirectionalTraceBuilder.getValue()) { + context.traceBuilderResult = BiDirectionalTraceBuilder.computeTraces(startBlock, linearScanOrder); + } else { + context.traceBuilderResult = UniDirectionalTraceBuilder.computeTraces(startBlock, linearScanOrder); + } }