Mercurial > hg > graal-compiler
changeset 23338:859766efc59e
TraceRA: introduce Trace class.
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/alloc/Trace.java Wed Jan 20 11:58:32 2016 +0100 @@ -0,0 +1,57 @@ +/* + * 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.ArrayList; +import java.util.Collection; +import java.util.List; + +import com.oracle.graal.compiler.common.cfg.AbstractBlockBase; + +/** + * Represents a list of sequentially executed {@code AbstractBlockBase blocks}. + */ +public class Trace<T extends AbstractBlockBase<T>> { + private final List<T> blocks; + + public Trace(Collection<T> blocks) { + this.blocks = new ArrayList<>(blocks); + } + + public Trace(List<T> blocks) { + this.blocks = blocks; + } + + public List<T> getBlocks() { + return blocks; + } + + public int size() { + return getBlocks().size(); + } + + @Override + public String toString() { + return "Trace" + blocks; + } +}
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/alloc/TraceBuilder.java Tue Jan 19 18:46:15 2016 +0100 +++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/alloc/TraceBuilder.java Wed Jan 20 11:58:32 2016 +0100 @@ -74,13 +74,13 @@ @SuppressWarnings("try") private TraceBuilderResult<T> build(T startBlock) { try (Indent indent = Debug.logAndIndent("start trace building: " + startBlock)) { - ArrayList<List<T>> traces = buildTraces(startBlock); + ArrayList<Trace<T>> traces = buildTraces(startBlock); return new TraceBuilderResult<>(traces, blockToTrace); } } - protected ArrayList<List<T>> buildTraces(T startBlock) { - ArrayList<List<T>> traces = new ArrayList<>(); + protected ArrayList<Trace<T>> buildTraces(T startBlock) { + ArrayList<Trace<T>> traces = new ArrayList<>(); // add start block worklist.add(startBlock); // process worklist @@ -88,7 +88,7 @@ T block = worklist.poll(); assert block != null; if (!processed(block)) { - traces.add(startTrace(block, traces.size())); + traces.add(new Trace<>(startTrace(block, traces.size()))); } } return traces;
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/alloc/TraceBuilderResult.java Tue Jan 19 18:46:15 2016 +0100 +++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/alloc/TraceBuilderResult.java Wed Jan 20 11:58:32 2016 +0100 @@ -23,15 +23,16 @@ package com.oracle.graal.compiler.common.alloc; import java.util.BitSet; +import java.util.Iterator; import java.util.List; import com.oracle.graal.compiler.common.cfg.AbstractBlockBase; public final class TraceBuilderResult<T extends AbstractBlockBase<T>> { - private final List<List<T>> traces; + private final List<Trace<T>> traces; private final int[] blockToTrace; - TraceBuilderResult(List<List<T>> traces, int[] blockToTrace) { + TraceBuilderResult(List<Trace<T>> traces, int[] blockToTrace) { this.traces = traces; this.blockToTrace = blockToTrace; } @@ -40,26 +41,28 @@ return blockToTrace[block.getId()]; } - public List<List<T>> getTraces() { + public List<Trace<T>> getTraces() { return traces; } public boolean incomingEdges(int traceNr) { - List<T> trace = getTraces().get(traceNr); - return incomingEdges(traceNr, trace); + Iterator<T> traceIt = getTraces().get(traceNr).getBlocks().iterator(); + return incomingEdges(traceNr, traceIt); } public boolean incomingSideEdges(int traceNr) { - List<T> trace = getTraces().get(traceNr); - if (trace.size() <= 1) { + Iterator<T> traceIt = getTraces().get(traceNr).getBlocks().iterator(); + if (!traceIt.hasNext()) { return false; } - return incomingEdges(traceNr, trace.subList(1, trace.size())); + traceIt.next(); + return incomingEdges(traceNr, traceIt); } - private boolean incomingEdges(int traceNr, List<T> trace) { + private boolean incomingEdges(int traceNr, Iterator<T> trace) { /* TODO (je): not efficient. find better solution. */ - for (T block : trace) { + while (trace.hasNext()) { + T block = trace.next(); for (T pred : block.getPredecessors()) { if (getTraceForBlock(pred) != traceNr) { return true; @@ -70,11 +73,11 @@ } public static <T extends AbstractBlockBase<T>> boolean verify(TraceBuilderResult<T> traceBuilderResult, int expectedLength) { - List<List<T>> traces = traceBuilderResult.getTraces(); + List<Trace<T>> traces = traceBuilderResult.getTraces(); assert verifyAllBlocksScheduled(traceBuilderResult, expectedLength) : "Not all blocks assigned to traces!"; - for (List<T> trace : traces) { + for (Trace<T> trace : traces) { T last = null; - for (T current : trace) { + for (T current : trace.getBlocks()) { assert last == null || current.getPredecessors().contains(last); last = current; } @@ -83,10 +86,10 @@ } private static <T extends AbstractBlockBase<T>> boolean verifyAllBlocksScheduled(TraceBuilderResult<T> traceBuilderResult, int expectedLength) { - List<List<T>> traces = traceBuilderResult.getTraces(); + List<Trace<T>> traces = traceBuilderResult.getTraces(); BitSet handled = new BitSet(expectedLength); - for (List<T> trace : traces) { - for (T block : trace) { + for (Trace<T> trace : traces) { + for (T block : trace.getBlocks()) { handled.set(block.getId()); } }
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/alloc/TraceStatisticsPrinter.java Tue Jan 19 18:46:15 2016 +0100 +++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/alloc/TraceStatisticsPrinter.java Wed Jan 20 11:58:32 2016 +0100 @@ -46,7 +46,7 @@ @SuppressWarnings("try") protected static <T extends AbstractBlockBase<T>> void print(TraceBuilderResult<T> result, String compilationUnitName) { - List<List<T>> traces = result.getTraces(); + List<Trace<T>> traces = result.getTraces(); int numTraces = traces.size(); try (Indent indent0 = Debug.logAndIndent(TRACE_DUMP_LEVEL, "<tracestatistics>")) { @@ -54,7 +54,7 @@ try (Indent indent1 = Debug.logAndIndent(TRACE_DUMP_LEVEL, "<traces>")) { printRawLine("tracenumber", "total", "min", "max", "numBlocks"); for (int i = 0; i < numTraces; i++) { - List<T> t = traces.get(i); + List<T> t = traces.get(i).getBlocks(); double total = 0; double max = Double.NEGATIVE_INFINITY; double min = Double.POSITIVE_INFINITY;
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceAllocationPhase.java Tue Jan 19 18:46:15 2016 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceAllocationPhase.java Wed Jan 20 11:58:32 2016 +0100 @@ -22,11 +22,18 @@ */ package com.oracle.graal.lir.alloc.trace; +import java.util.List; + import com.oracle.graal.compiler.common.alloc.RegisterAllocationConfig; +import com.oracle.graal.compiler.common.alloc.Trace; import com.oracle.graal.compiler.common.alloc.TraceBuilderResult; +import com.oracle.graal.compiler.common.cfg.AbstractBlockBase; +import com.oracle.graal.lir.gen.LIRGenerationResult; import com.oracle.graal.lir.gen.LIRGeneratorTool.MoveFactory; import com.oracle.graal.lir.phases.LIRPhase; +import jdk.vm.ci.code.TargetDescription; + public abstract class TraceAllocationPhase extends LIRPhase<TraceAllocationPhase.TraceAllocationContext> { public static final class TraceAllocationContext { @@ -41,4 +48,26 @@ } } + public final <B extends AbstractBlockBase<B>> void apply(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, Trace<B> trace, TraceAllocationContext context, + boolean dumpLIR) { + apply(target, lirGenRes, codeEmittingOrder, trace.getBlocks(), context, dumpLIR); + } + + public final <B extends AbstractBlockBase<B>> void apply(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, Trace<B> trace, TraceAllocationContext context) { + apply(target, lirGenRes, codeEmittingOrder, trace.getBlocks(), context); + } + + @Override + protected final <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> sortedBlocks, TraceAllocationContext context) { + TraceBuilderResult<B> resultTraces = getTraceBuilderResult(context); + Trace<B> trace = resultTraces.getTraces().get(resultTraces.getTraceForBlock(sortedBlocks.get(0))); + run(target, lirGenRes, codeEmittingOrder, trace, context); + } + + @SuppressWarnings("unchecked") + private static <B extends AbstractBlockBase<B>> TraceBuilderResult<B> getTraceBuilderResult(TraceAllocationContext context) { + return (TraceBuilderResult<B>) context.resultTraces; + } + + protected abstract <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, Trace<B> trace, TraceAllocationContext context); }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceGlobalMoveResolutionPhase.java Tue Jan 19 18:46:15 2016 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceGlobalMoveResolutionPhase.java Wed Jan 20 11:58:32 2016 +0100 @@ -31,12 +31,7 @@ import java.util.List; -import jdk.vm.ci.code.Architecture; -import jdk.vm.ci.code.RegisterValue; -import jdk.vm.ci.code.TargetDescription; -import jdk.vm.ci.meta.AllocatableValue; -import jdk.vm.ci.meta.Value; - +import com.oracle.graal.compiler.common.alloc.Trace; import com.oracle.graal.compiler.common.alloc.TraceBuilderResult; import com.oracle.graal.compiler.common.cfg.AbstractBlockBase; import com.oracle.graal.debug.Debug; @@ -48,6 +43,12 @@ import com.oracle.graal.lir.ssa.SSAUtil.PhiValueVisitor; import com.oracle.graal.lir.ssi.SSIUtil; +import jdk.vm.ci.code.Architecture; +import jdk.vm.ci.code.RegisterValue; +import jdk.vm.ci.code.TargetDescription; +import jdk.vm.ci.meta.AllocatableValue; +import jdk.vm.ci.meta.Value; + public final class TraceGlobalMoveResolutionPhase extends TraceAllocationPhase { /** @@ -58,7 +59,7 @@ } @Override - protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, TraceAllocationContext context) { + protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, Trace<B> trace, TraceAllocationContext context) { MoveFactory spillMoveFactory = context.spillMoveFactory; resolveGlobalDataFlow(context.resultTraces, lirGenRes, spillMoveFactory, target.arch); } @@ -75,8 +76,8 @@ }; try (Indent indent = Debug.logAndIndent("Trace global move resolution")) { - for (List<B> trace : resultTraces.getTraces()) { - for (AbstractBlockBase<?> fromBlock : trace) { + for (Trace<B> trace : resultTraces.getTraces()) { + for (AbstractBlockBase<?> fromBlock : trace.getBlocks()) { for (AbstractBlockBase<?> toBlock : fromBlock.getSuccessors()) { if (resultTraces.getTraceForBlock(fromBlock) != resultTraces.getTraceForBlock(toBlock)) { try (Indent indent0 = Debug.logAndIndent("Handle trace edge from %s (Trace%d) to %s (Trace%d)", fromBlock, resultTraces.getTraceForBlock(fromBlock), toBlock,
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceRegisterAllocationPhase.java Tue Jan 19 18:46:15 2016 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceRegisterAllocationPhase.java Wed Jan 20 11:58:32 2016 +0100 @@ -22,9 +22,11 @@ */ package com.oracle.graal.lir.alloc.trace; +import java.util.Collection; import java.util.List; import com.oracle.graal.compiler.common.alloc.RegisterAllocationConfig; +import com.oracle.graal.compiler.common.alloc.Trace; import com.oracle.graal.compiler.common.alloc.TraceBuilderResult; import com.oracle.graal.compiler.common.alloc.TraceStatisticsPrinter; import com.oracle.graal.compiler.common.cfg.AbstractBlockBase; @@ -92,7 +94,7 @@ Debug.dump(lir, "Before TraceRegisterAllocation"); int traceNumber = 0; - for (List<B> trace : resultTraces.getTraces()) { + for (Trace<B> trace : resultTraces.getTraces()) { try (Indent i = Debug.logAndIndent("Allocating Trace%d: %s", traceNumber, trace); Scope s = Debug.scope("AllocateTrace", trace)) { tracesMetric.increment(); if (trivialTracesMetric.isEnabled() && isTrivialTrace(lir, trace)) { @@ -110,7 +112,7 @@ } catch (Throwable e) { throw Debug.handle(e); } - unnumberInstructions(trace, lir); + unnumberInstructions(trace.getBlocks(), lir); } Debug.dump(lir, "After trace allocation"); @@ -127,9 +129,9 @@ assert TraceBuilderResult.verify(resultTraces, lirGenRes.getLIR().getControlFlowGraph().getBlocks().size()); if (Debug.isLogEnabled(TRACE_LOG_LEVEL)) { - List<List<B>> traces = resultTraces.getTraces(); + List<Trace<B>> traces = resultTraces.getTraces(); for (int i = 0; i < traces.size(); i++) { - List<B> trace = traces.get(i); + Trace<B> trace = traces.get(i); Debug.log(TRACE_LOG_LEVEL, "Trace %5d: %s", i, trace); } } @@ -158,11 +160,11 @@ } } - static boolean isTrivialTrace(LIR lir, List<? extends AbstractBlockBase<?>> trace) { + static boolean isTrivialTrace(LIR lir, Trace<? extends AbstractBlockBase<?>> trace) { if (trace.size() != 1) { return false; } - List<LIRInstruction> instructions = lir.getLIRforBlock(trace.iterator().next()); + List<LIRInstruction> instructions = lir.getLIRforBlock(trace.getBlocks().iterator().next()); if (instructions.size() != 2) { return false; } @@ -174,7 +176,7 @@ return instructions.get(1) instanceof JumpOp; } - private static void unnumberInstructions(List<? extends AbstractBlockBase<?>> trace, LIR lir) { + private static void unnumberInstructions(Collection<? extends AbstractBlockBase<?>> trace, LIR lir) { for (AbstractBlockBase<?> block : trace) { for (LIRInstruction op : lir.getLIRforBlock(block)) { op.setId(-1);
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceTrivialAllocator.java Tue Jan 19 18:46:15 2016 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceTrivialAllocator.java Wed Jan 20 11:58:32 2016 +0100 @@ -28,9 +28,7 @@ import java.util.List; -import jdk.vm.ci.code.TargetDescription; -import jdk.vm.ci.meta.Value; - +import com.oracle.graal.compiler.common.alloc.Trace; import com.oracle.graal.compiler.common.alloc.TraceBuilderResult; import com.oracle.graal.compiler.common.cfg.AbstractBlockBase; import com.oracle.graal.lir.LIR; @@ -44,6 +42,9 @@ import com.oracle.graal.lir.ssi.SSIUtil; import com.oracle.graal.lir.util.VariableVirtualStackValueMap; +import jdk.vm.ci.code.TargetDescription; +import jdk.vm.ci.meta.Value; + /** * Allocates a trivial trace i.e. a trace consisting of a single block with no instructions other * than the {@link LabelOp} and the {@link JumpOp}. @@ -51,11 +52,11 @@ final class TraceTrivialAllocator extends TraceAllocationPhase { @Override - protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> trace, TraceAllocationContext context) { + protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, Trace<B> trace, TraceAllocationContext context) { LIR lir = lirGenRes.getLIR(); TraceBuilderResult<?> resultTraces = context.resultTraces; assert isTrivialTrace(lir, trace) : "Not a trivial trace! " + trace; - B block = trace.iterator().next(); + B block = trace.getBlocks().iterator().next(); AbstractBlockBase<?> pred = TraceUtil.getBestTraceInterPredecessor(resultTraces, block);
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/lsra/TraceLinearScan.java Tue Jan 19 18:46:15 2016 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/lsra/TraceLinearScan.java Wed Jan 20 11:58:32 2016 +0100 @@ -36,17 +36,8 @@ import java.util.EnumSet; import java.util.List; -import jdk.vm.ci.code.BailoutException; -import jdk.vm.ci.code.Register; -import jdk.vm.ci.code.RegisterAttributes; -import jdk.vm.ci.code.RegisterValue; -import jdk.vm.ci.code.TargetDescription; -import jdk.vm.ci.common.JVMCIError; -import jdk.vm.ci.meta.AllocatableValue; -import jdk.vm.ci.meta.LIRKind; -import jdk.vm.ci.meta.Value; - import com.oracle.graal.compiler.common.alloc.RegisterAllocationConfig; +import com.oracle.graal.compiler.common.alloc.Trace; import com.oracle.graal.compiler.common.alloc.TraceBuilderResult; import com.oracle.graal.compiler.common.cfg.AbstractBlockBase; import com.oracle.graal.compiler.common.cfg.BlockMap; @@ -72,10 +63,20 @@ import com.oracle.graal.options.OptionType; import com.oracle.graal.options.OptionValue; +import jdk.vm.ci.code.BailoutException; +import jdk.vm.ci.code.Register; +import jdk.vm.ci.code.RegisterAttributes; +import jdk.vm.ci.code.RegisterValue; +import jdk.vm.ci.code.TargetDescription; +import jdk.vm.ci.common.JVMCIError; +import jdk.vm.ci.meta.AllocatableValue; +import jdk.vm.ci.meta.LIRKind; +import jdk.vm.ci.meta.Value; + /** * An implementation of the linear scan register allocator algorithm described in <a - * href="http://doi.acm.org/10.1145/1064979.1064998" - * >"Optimized Interval Splitting in a Linear Scan Register Allocator"</a> by Christian Wimmer and + * href="http://doi.acm.org/10.1145/1064979.1064998" > + * "Optimized Interval Splitting in a Linear Scan Register Allocator"</a> by Christian Wimmer and * Hanspeter Moessenboeck. */ public final class TraceLinearScan { @@ -186,12 +187,12 @@ protected final TraceBuilderResult<?> traceBuilderResult; private final boolean neverSpillConstants; - public TraceLinearScan(TargetDescription target, LIRGenerationResult res, MoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, List<? extends AbstractBlockBase<?>> sortedBlocks, + public TraceLinearScan(TargetDescription target, LIRGenerationResult res, MoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, Trace<? extends AbstractBlockBase<?>> trace, TraceBuilderResult<?> traceBuilderResult, boolean neverSpillConstants) { this.ir = res.getLIR(); this.moveFactory = spillMoveFactory; this.frameMapBuilder = res.getFrameMapBuilder(); - this.sortedBlocks = sortedBlocks; + this.sortedBlocks = trace.getBlocks(); this.registerAttributes = regAllocConfig.getRegisterConfig().getAttributesMap(); this.regAllocConfig = regAllocConfig;