# HG changeset patch # User Josef Eisl # Date 1422469967 -3600 # Node ID 74b144f7c54a9bc69fb515dcd5dbdbab2af2a534 # Parent b646e37bc9891bcad7092067b76bc5387aa92849# Parent 9c2396ef02db1ebadc37af739ac84fc08573d485 Merge. diff -r 9c2396ef02db -r 74b144f7c54a graal/com.oracle.graal.api.code/src/com/oracle/graal/api/code/VirtualStackSlot.java --- a/graal/com.oracle.graal.api.code/src/com/oracle/graal/api/code/VirtualStackSlot.java Wed Jan 28 15:01:21 2015 +0100 +++ b/graal/com.oracle.graal.api.code/src/com/oracle/graal/api/code/VirtualStackSlot.java Wed Jan 28 19:32:47 2015 +0100 @@ -44,7 +44,7 @@ @Override public String toString() { - return "vstack(" + id + ")" + getKindSuffix(); + return "vstack:" + id + getKindSuffix(); } @Override diff -r 9c2396ef02db -r 74b144f7c54a graal/com.oracle.graal.baseline/src/com/oracle/graal/baseline/BaselineBytecodeParser.java --- a/graal/com.oracle.graal.baseline/src/com/oracle/graal/baseline/BaselineBytecodeParser.java Wed Jan 28 15:01:21 2015 +0100 +++ b/graal/com.oracle.graal.baseline/src/com/oracle/graal/baseline/BaselineBytecodeParser.java Wed Jan 28 19:32:47 2015 +0100 @@ -44,6 +44,7 @@ import com.oracle.graal.lir.StandardOp.BlockEndOp; import com.oracle.graal.lir.framemap.*; import com.oracle.graal.lir.gen.*; +import com.oracle.graal.lir.stackslotalloc.*; import com.oracle.graal.phases.*; public class BaselineBytecodeParser extends AbstractBytecodeParser implements BytecodeParserTool { @@ -128,7 +129,6 @@ RegisterConfig registerConfig = null; FrameMapBuilder frameMapBuilder = backend.newFrameMapBuilder(registerConfig); - frameMapBuilder.requireMapping(lir); TargetDescription target = backend.getTarget(); CallingConvention cc = CodeUtil.getCallingConvention(backend.getProviders().getCodeCache(), CallingConvention.Type.JavaCallee, method, false); this.lirGenRes = backend.newLIRGenerationResult(lir, frameMapBuilder, method, null); @@ -153,22 +153,17 @@ try (Scope s = Debug.scope("Allocator")) { if (backend.shouldAllocateRegisters()) { LinearScan.allocate(target, lirGenRes); - } else if (!LocationMarker.Options.UseLocationMarker.getValue()) { - // build frame map for targets that do not allocate registers - lirGenRes.buildFrameMap(); } } - if (LocationMarker.Options.UseLocationMarker.getValue()) { - try (Scope s1 = Debug.scope("BuildFrameMap")) { - // build frame map - lirGenRes.buildFrameMap(); - Debug.dump(lir, "After FrameMap building"); - } - try (Scope s1 = Debug.scope("MarkLocations")) { - if (backend.shouldAllocateRegisters()) { - // currently we mark locations only if we do register allocation - LocationMarker.markLocations(lir, lirGenRes.getFrameMap()); - } + try (Scope s1 = Debug.scope("BuildFrameMap")) { + // build frame map + lirGenRes.buildFrameMap(new SimpleStackSlotAllocator()); + Debug.dump(lir, "After FrameMap building"); + } + try (Scope s1 = Debug.scope("MarkLocations")) { + if (backend.shouldAllocateRegisters()) { + // currently we mark locations only if we do register allocation + LocationMarker.markLocations(lir, lirGenRes.getFrameMap()); } } diff -r 9c2396ef02db -r 74b144f7c54a graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java --- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Wed Jan 28 15:01:21 2015 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Wed Jan 28 19:32:47 2015 +0100 @@ -46,6 +46,7 @@ import com.oracle.graal.lir.constopt.*; import com.oracle.graal.lir.framemap.*; import com.oracle.graal.lir.gen.*; +import com.oracle.graal.lir.stackslotalloc.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.nodes.spi.*; @@ -323,7 +324,6 @@ } try (Scope ds = Debug.scope("BackEnd", lir)) { FrameMapBuilder frameMapBuilder = backend.newFrameMapBuilder(registerConfig); - frameMapBuilder.requireMapping(lir); LIRGenerationResult lirGenRes = backend.newLIRGenerationResult(lir, frameMapBuilder, graph.method(), stub); LIRGeneratorTool lirGen = backend.newLIRGenerator(cc, lirGenRes); NodeLIRBuilderTool nodeLirGen = backend.newNodeLIRBuilder(graph, lirGen); @@ -351,25 +351,26 @@ try (Scope s = Debug.scope("Allocator", nodeLirGen)) { if (backend.shouldAllocateRegisters()) { LinearScan.allocate(target, lirGenRes); - } else if (!LocationMarker.Options.UseLocationMarker.getValue()) { - // build frame map for targets that do not allocate registers - lirGenRes.buildFrameMap(); } } catch (Throwable e) { throw Debug.handle(e); } - if (LocationMarker.Options.UseLocationMarker.getValue()) { - try (Scope s1 = Debug.scope("BuildFrameMap")) { - // build frame map - lirGenRes.buildFrameMap(); - Debug.dump(lir, "After FrameMap building"); + try (Scope s1 = Debug.scope("BuildFrameMap")) { + // build frame map + final StackSlotAllocator allocator; + if (LSStackSlotAllocator.Options.EnableLSStackSlotAllocation.getValue()) { + allocator = new LSStackSlotAllocator(); + } else { + allocator = new SimpleStackSlotAllocator(); } - try (Scope s1 = Debug.scope("MarkLocations")) { - if (backend.shouldAllocateRegisters()) { - // currently we mark locations only if we do register allocation - LocationMarker.markLocations(lir, lirGenRes.getFrameMap()); - } + lirGenRes.buildFrameMap(allocator); + Debug.dump(lir, "After FrameMap building"); + } + try (Scope s1 = Debug.scope("MarkLocations")) { + if (backend.shouldAllocateRegisters()) { + // currently we mark locations only if we do register allocation + LocationMarker.markLocations(lir, lirGenRes.getFrameMap()); } } diff -r 9c2396ef02db -r 74b144f7c54a graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScan.java --- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScan.java Wed Jan 28 15:01:21 2015 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScan.java Wed Jan 28 19:32:47 2015 +0100 @@ -1640,67 +1640,6 @@ return new IntervalWalker(this, oopIntervals, nonOopIntervals); } - /** - * Visits all intervals for a frame state. The frame state use this information to build the OOP - * maps. - */ - private void markFrameLocations(IntervalWalker iw, LIRInstruction op, LIRFrameState info, FrameMap frameMap) { - Debug.log("creating oop map at opId %d", op.id()); - - // walk before the current operation . intervals that start at - // the operation (i.e. output operands of the operation) are not - // included in the oop map - iw.walkBefore(op.id()); - - // TODO(je) we could pass this as parameter - AbstractBlock block = blockForId(op.id()); - - // Iterate through active intervals - for (Interval interval = iw.activeLists.get(RegisterBinding.Fixed); interval != Interval.EndMarker; interval = interval.next) { - Value operand = interval.operand; - - assert interval.currentFrom() <= op.id() && op.id() <= interval.currentTo() : "interval should not be active otherwise"; - assert isVariable(interval.operand) : "fixed interval found"; - - // Check if this range covers the instruction. Intervals that - // start or end at the current operation are not included in the - // oop map, except in the case of patching moves. For patching - // moves, any intervals which end at this instruction are included - // in the oop map since we may safepoint while doing the patch - // before we've consumed the inputs. - if (op.id() < interval.currentTo() && !isIllegal(interval.location())) { - // caller-save registers must not be included into oop-maps at calls - assert !op.destroysCallerSavedRegisters() || !isRegister(operand) || !isCallerSave(operand) : "interval is in a caller-save register at a call . register will be overwritten"; - - info.markLocation(interval.location(), frameMap); - - // Spill optimization: when the stack value is guaranteed to be always correct, - // then it must be added to the oop map even if the interval is currently in a - // register - int spillPos = interval.spillDefinitionPos(); - if (interval.spillState() != SpillState.SpillInDominator) { - if (interval.alwaysInMemory() && op.id() > interval.spillDefinitionPos() && !interval.location().equals(interval.spillSlot())) { - assert interval.spillDefinitionPos() > 0 : "position not set correctly"; - assert spillPos > 0 : "position not set correctly"; - assert interval.spillSlot() != null : "no spill slot assigned"; - assert !isRegister(interval.operand) : "interval is on stack : so stack slot is registered twice"; - info.markLocation(interval.spillSlot(), frameMap); - } - } else { - AbstractBlock spillBlock = blockForId(spillPos); - if (interval.alwaysInMemory() && !interval.location().equals(interval.spillSlot())) { - if ((spillBlock.equals(block) && op.id() > spillPos) || dominates(spillBlock, block)) { - assert spillPos > 0 : "position not set correctly"; - assert interval.spillSlot() != null : "no spill slot assigned"; - assert !isRegister(interval.operand) : "interval is on stack : so stack slot is registered twice"; - info.markLocation(interval.spillSlot(), frameMap); - } - } - } - } - } - } - private boolean isCallerSave(Value operand) { return attributes(asRegister(operand)).isCallerSave(); } @@ -1744,20 +1683,11 @@ return result; } - private void computeDebugInfo(IntervalWalker iw, final LIRInstruction op, LIRFrameState info) { - if (!LocationMarker.Options.UseLocationMarker.getValue()) { - FrameMap frameMap = res.getFrameMap(); - info.initDebugInfo(frameMap, !op.destroysCallerSavedRegisters() || !callKillsRegisters); - markFrameLocations(iw, op, info, frameMap); - } - + private void computeDebugInfo(final LIRInstruction op, LIRFrameState info) { info.forEachState(op, this::debugInfoProcedure); - if (!LocationMarker.Options.UseLocationMarker.getValue()) { - info.finish(op, res.getFrameMap()); - } } - private void assignLocations(List instructions, final IntervalWalker iw) { + private void assignLocations(List instructions) { int numInst = instructions.size(); boolean hasDead = false; @@ -1792,7 +1722,7 @@ op.forEachOutput(assignProc); // compute reference map and debug information - op.forEachState((inst, state) -> computeDebugInfo(iw, inst, state)); + op.forEachState((inst, state) -> computeDebugInfo(inst, state)); // remove useless moves if (move != null) { @@ -1810,41 +1740,15 @@ } private void assignLocations() { - IntervalWalker iw = initIntervalWalker(IS_STACK_INTERVAL); try (Indent indent = Debug.logAndIndent("assign locations")) { for (AbstractBlock block : sortedBlocks) { try (Indent indent2 = Debug.logAndIndent("assign locations in block B%d", block.getId())) { - assignLocations(ir.getLIRforBlock(block), iw); + assignLocations(ir.getLIRforBlock(block)); } } } } - private class Mapper implements FrameMappable { - - public void map(FrameMappingTool tool) { - try (Scope scope = Debug.scope("StackSlotMappingLSRA")) { - for (Interval current : intervals) { - if (current != null) { - if (isVirtualStackSlot(current.location())) { - VirtualStackSlot value = asVirtualStackSlot(current.location()); - StackSlot stackSlot = tool.getStackSlot(value); - Debug.log("map %s -> %s", value, stackSlot); - current.assignLocation(stackSlot); - } - if (current.isSplitParent() && current.spillSlot() != null && isVirtualStackSlot(current.spillSlot())) { - VirtualStackSlot value = asVirtualStackSlot(current.spillSlot()); - StackSlot stackSlot = tool.getStackSlot(value); - Debug.log("map %s -> %s", value, stackSlot); - current.setSpillSlot(stackSlot); - } - } - } - } - } - - } - public static void allocate(TargetDescription target, LIRGenerationResult res) { new LinearScan(target, res).allocate(); } @@ -1892,16 +1796,6 @@ printIntervals("After register allocation"); printLir("After register allocation", true); - // register interval mapper - frameMapBuilder.requireMapping(new Mapper()); - - if (!LocationMarker.Options.UseLocationMarker.getValue()) { - // build frame map - res.buildFrameMap(); - } - - printLir("After FrameMap building", true); - sortIntervalsAfterAllocation(); if (DetailedAsserts.getValue()) { diff -r 9c2396ef02db -r 74b144f7c54a graal/com.oracle.graal.lir.amd64/src/com/oracle/graal/lir/amd64/AMD64FrameMapBuilder.java --- a/graal/com.oracle.graal.lir.amd64/src/com/oracle/graal/lir/amd64/AMD64FrameMapBuilder.java Wed Jan 28 15:01:21 2015 +0100 +++ b/graal/com.oracle.graal.lir.amd64/src/com/oracle/graal/lir/amd64/AMD64FrameMapBuilder.java Wed Jan 28 19:32:47 2015 +0100 @@ -36,14 +36,14 @@ * runtime for walking/inspecting frames of such methods. */ public StackSlot allocateRBPSpillSlot() { - return ((AMD64FrameMap) frameMap).allocateRBPSpillSlot(); + return ((AMD64FrameMap) getFrameMap()).allocateRBPSpillSlot(); } public void freeRBPSpillSlot() { - ((AMD64FrameMap) frameMap).freeRBPSpillSlot(); + ((AMD64FrameMap) getFrameMap()).freeRBPSpillSlot(); } public StackSlot allocateDeoptimizationRescueSlot() { - return ((AMD64FrameMap) frameMap).allocateDeoptimizationRescueSlot(); + return ((AMD64FrameMap) getFrameMap()).allocateDeoptimizationRescueSlot(); } } diff -r 9c2396ef02db -r 74b144f7c54a graal/com.oracle.graal.lir.sparc/src/com/oracle/graal/lir/sparc/SPARCFrameMapBuilder.java --- a/graal/com.oracle.graal.lir.sparc/src/com/oracle/graal/lir/sparc/SPARCFrameMapBuilder.java Wed Jan 28 15:01:21 2015 +0100 +++ b/graal/com.oracle.graal.lir.sparc/src/com/oracle/graal/lir/sparc/SPARCFrameMapBuilder.java Wed Jan 28 19:32:47 2015 +0100 @@ -32,6 +32,6 @@ } public StackSlot allocateDeoptimizationRescueSlot() { - return ((SPARCFrameMap) frameMap).allocateDeoptimizationRescueSlot(); + return ((SPARCFrameMap) getFrameMap()).allocateDeoptimizationRescueSlot(); } } diff -r 9c2396ef02db -r 74b144f7c54a graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIR.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIR.java Wed Jan 28 15:01:21 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIR.java Wed Jan 28 19:32:47 2015 +0100 @@ -22,24 +22,18 @@ */ package com.oracle.graal.lir; -import static com.oracle.graal.api.code.ValueUtil.*; - import java.util.*; -import com.oracle.graal.api.code.*; import com.oracle.graal.api.meta.*; import com.oracle.graal.compiler.common.cfg.*; -import com.oracle.graal.debug.*; -import com.oracle.graal.debug.Debug.Scope; import com.oracle.graal.lir.StandardOp.BlockEndOp; import com.oracle.graal.lir.StandardOp.LabelOp; -import com.oracle.graal.lir.framemap.*; /** * This class implements the overall container for the LIR graph and directs its construction, * optimization, and finalization. */ -public class LIR implements FrameMappable { +public class LIR { private final AbstractControlFlowGraph cfg; @@ -226,30 +220,4 @@ } } - public void map(FrameMappingTool tool) { - try (Scope scope = Debug.scope("StackSlotMappingLIR")) { - ValueProcedure updateProc = (value, mode, flags) -> { - if (isVirtualStackSlot(value)) { - StackSlot stackSlot = tool.getStackSlot(asVirtualStackSlot(value)); - Debug.log("map %s -> %s", value, stackSlot); - return stackSlot; - } - return value; - }; - for (AbstractBlock block : getControlFlowGraph().getBlocks()) { - try (Indent indent0 = Debug.logAndIndent("block: %s", block)) { - for (LIRInstruction inst : getLIRforBlock(block)) { - try (Indent indent1 = Debug.logAndIndent("Inst: %d: %s", inst.id(), inst)) { - inst.forEachAlive(updateProc); - inst.forEachInput(updateProc); - inst.forEachOutput(updateProc); - inst.forEachTemp(updateProc); - inst.forEachState(updateProc); - } - } - } - } - } - } - } diff -r 9c2396ef02db -r 74b144f7c54a graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMap.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMap.java Wed Jan 28 15:01:21 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMap.java Wed Jan 28 19:32:47 2015 +0100 @@ -256,7 +256,7 @@ * @param kind The kind of the spill slot to be reserved. * @return A spill slot denoting the reserved memory area. */ - protected StackSlot allocateSpillSlot(LIRKind kind) { + public StackSlot allocateSpillSlot(LIRKind kind) { assert frameSize == -1 : "frame size must not yet be fixed"; int size = spillSlotSize(kind); spillSize = NumUtil.roundUp(spillSize + size, size); @@ -264,6 +264,16 @@ } /** + * Returns the size of the stack slot range for {@code slots} objects. + * + * @param slots The number of slots. + * @return The size in byte + */ + public int spillSlotRangeSize(int slots) { + return slots * getTarget().wordSize; + } + + /** * Reserves a number of contiguous slots in the frame of the method being compiled. If the * requested number of slots is 0, this method returns {@code null}. * @@ -274,12 +284,12 @@ * collector could see garbage object values. * @return the first reserved stack slot (i.e., at the lowest address) */ - protected StackSlot allocateStackSlots(int slots, BitSet objects) { + public StackSlot allocateStackSlots(int slots, BitSet objects) { assert frameSize == -1 : "frame size must not yet be fixed"; if (slots == 0) { return null; } - spillSize += (slots * getTarget().wordSize); + spillSize += spillSlotRangeSize(slots); if (!objects.isEmpty()) { assert objects.length() <= slots; diff -r 9c2396ef02db -r 74b144f7c54a graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMapBuilder.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMapBuilder.java Wed Jan 28 15:01:21 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMapBuilder.java Wed Jan 28 19:32:47 2015 +0100 @@ -27,6 +27,7 @@ import com.oracle.graal.api.code.*; import com.oracle.graal.api.meta.*; import com.oracle.graal.lir.gen.*; +import com.oracle.graal.lir.stackslotalloc.*; /** * A {@link FrameMapBuilder} is used to collect all information necessary to @@ -72,14 +73,8 @@ void callsMethod(CallingConvention cc); /** - * Registers a FrameMappable class so that virtual stack slots can be changed to real stack - * slots. - */ - void requireMapping(FrameMappable mappable); - - /** * Creates a {@linkplain FrameMap} based on the information collected by this * {@linkplain FrameMapBuilder}. */ - FrameMap buildFrameMap(LIRGenerationResult result); + FrameMap buildFrameMap(LIRGenerationResult result, StackSlotAllocator allocator); } diff -r 9c2396ef02db -r 74b144f7c54a graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMapBuilderImpl.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMapBuilderImpl.java Wed Jan 28 15:01:21 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMapBuilderImpl.java Wed Jan 28 19:32:47 2015 +0100 @@ -27,16 +27,19 @@ import com.oracle.graal.api.code.*; import com.oracle.graal.api.meta.*; import com.oracle.graal.compiler.common.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.debug.Debug.Scope; import com.oracle.graal.lir.gen.*; +import com.oracle.graal.lir.stackslotalloc.*; /** * A FrameMapBuilder that records allocation. */ -public class FrameMapBuilderImpl implements FrameMapBuilder { +public class FrameMapBuilderImpl implements FrameMapBuilderTool { private final RegisterConfig registerConfig; private final CodeCacheProvider codeCache; - protected final FrameMap frameMap; + private final FrameMap frameMap; private final List stackSlots; private final List calls; private int numStackSlots; @@ -48,12 +51,9 @@ this.frameMap = frameMap; this.stackSlots = new ArrayList<>(); this.calls = new ArrayList<>(); - this.mappables = new ArrayList<>(); this.numStackSlots = 0; } - private final List mappables; - public VirtualStackSlot allocateSpillSlot(LIRKind kind) { SimpleVirtualStackSlot slot = new SimpleVirtualStackSlot(numStackSlots++, kind); stackSlots.add(slot); @@ -80,10 +80,10 @@ return codeCache; } - /** - * Returns the number of {@link VirtualStackSlot}s created by this {@link FrameMapBuilder}. Can - * be used as an upper bound for an array indexed by {@link VirtualStackSlot#getId()}. - */ + public FrameMap getFrameMap() { + return frameMap; + } + public int getNumberOfStackSlots() { return numStackSlots; } @@ -92,23 +92,18 @@ calls.add(cc); } - public FrameMap buildFrameMap(LIRGenerationResult res) { - FrameMappingTool mapper = new SimpleStackSlotAllocator().allocateStackSlots(this); + public FrameMap buildFrameMap(LIRGenerationResult res, StackSlotAllocator allocator) { + try (Scope s = Debug.scope("StackSlotAllocation")) { + allocator.allocateStackSlots(this, res); + } for (CallingConvention cc : calls) { frameMap.callsMethod(cc); } - // rewrite - mappables.forEach(m -> m.map(mapper)); - frameMap.finish(); return frameMap; } - public void requireMapping(FrameMappable mappable) { - this.mappables.add(mappable); - } - - List getStackSlots() { + public List getStackSlots() { return stackSlots; } diff -r 9c2396ef02db -r 74b144f7c54a graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMapBuilderTool.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMapBuilderTool.java Wed Jan 28 19:32:47 2015 +0100 @@ -0,0 +1,44 @@ +/* + * 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.lir.framemap; + +import java.util.*; + +import com.oracle.graal.api.code.*; + +/** + * A {@link FrameMapBuilder} that allows access to the underlying {@link FrameMap}. + */ +public interface FrameMapBuilderTool extends FrameMapBuilder { + + /** + * Returns the number of {@link VirtualStackSlot}s created by this {@link FrameMapBuilder}. Can + * be used as an upper bound for an array indexed by {@link VirtualStackSlot#getId()}. + */ + int getNumberOfStackSlots(); + + List getStackSlots(); + + FrameMap getFrameMap(); + +} diff -r 9c2396ef02db -r 74b144f7c54a graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMappable.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMappable.java Wed Jan 28 15:01:21 2015 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,32 +0,0 @@ -/* - * 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.lir.framemap; - -/** - * This interface should be implemented by all classes that store virtual stack slots to convert - * them into real stack slots when {@link FrameMapBuilder#buildFrameMap} is called. Implementors - * should register themselves using {@link FrameMapBuilder#requireMapping(FrameMappable)}. - */ -public interface FrameMappable { - void map(FrameMappingTool tool); -} diff -r 9c2396ef02db -r 74b144f7c54a graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMappingTool.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMappingTool.java Wed Jan 28 15:01:21 2015 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,33 +0,0 @@ -/* - * 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.lir.framemap; - -import com.oracle.graal.api.code.*; - -/** - * A tool to get the real stack slot from a virtual stack slot. - */ -@FunctionalInterface -public interface FrameMappingTool { - StackSlot getStackSlot(VirtualStackSlot slot); -} diff -r 9c2396ef02db -r 74b144f7c54a graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/SimpleStackSlotAllocator.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/SimpleStackSlotAllocator.java Wed Jan 28 15:01:21 2015 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,53 +0,0 @@ -/* - * 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.lir.framemap; - -import com.oracle.graal.api.code.*; -import com.oracle.graal.compiler.common.*; - -public class SimpleStackSlotAllocator implements StackSlotAllocator { - - public FrameMappingTool allocateStackSlots(FrameMapBuilderImpl builder) { - StackSlot[] mapping = new StackSlot[builder.getNumberOfStackSlots()]; - for (VirtualStackSlot virtualSlot : builder.getStackSlots()) { - final StackSlot slot; - if (virtualSlot instanceof SimpleVirtualStackSlot) { - slot = mapSimpleVirtualStackSlot(builder, (SimpleVirtualStackSlot) virtualSlot); - } else if (virtualSlot instanceof VirtualStackSlotRange) { - slot = mapVirtualStackSlotRange(builder, (VirtualStackSlotRange) virtualSlot); - } else { - throw GraalInternalError.shouldNotReachHere("Unknown VirtualStackSlot: " + virtualSlot); - } - mapping[virtualSlot.getId()] = slot; - } - return v -> mapping[v.getId()]; - } - - protected StackSlot mapSimpleVirtualStackSlot(FrameMapBuilderImpl builder, SimpleVirtualStackSlot virtualStackSlot) { - return builder.frameMap.allocateSpillSlot(virtualStackSlot.getLIRKind()); - } - - protected StackSlot mapVirtualStackSlotRange(FrameMapBuilderImpl builder, VirtualStackSlotRange virtualStackSlot) { - return builder.frameMap.allocateStackSlots(virtualStackSlot.getSlots(), virtualStackSlot.getObjects()); - } -} diff -r 9c2396ef02db -r 74b144f7c54a graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/SimpleVirtualStackSlot.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/SimpleVirtualStackSlot.java Wed Jan 28 15:01:21 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/SimpleVirtualStackSlot.java Wed Jan 28 19:32:47 2015 +0100 @@ -28,7 +28,7 @@ /** * Represents a {@link VirtualStackSlot virtual stack slot} for a specific {@link LIRKind kind}. */ -class SimpleVirtualStackSlot extends VirtualStackSlot { +public class SimpleVirtualStackSlot extends VirtualStackSlot { private static final long serialVersionUID = 7654295701165421750L; diff -r 9c2396ef02db -r 74b144f7c54a graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/StackSlotAllocator.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/StackSlotAllocator.java Wed Jan 28 15:01:21 2015 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,33 +0,0 @@ -/* - * 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.lir.framemap; - -import com.oracle.graal.api.code.*; - -/** - * A {@link StackSlotAllocator} is responsible for translating {@link VirtualStackSlot virtual} - * stack slots into {@link StackSlot real} stack slots. - */ -public interface StackSlotAllocator { - FrameMappingTool allocateStackSlots(FrameMapBuilderImpl builder); -} diff -r 9c2396ef02db -r 74b144f7c54a graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/VirtualStackSlotRange.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/VirtualStackSlotRange.java Wed Jan 28 15:01:21 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/VirtualStackSlotRange.java Wed Jan 28 19:32:47 2015 +0100 @@ -31,7 +31,7 @@ * Represents a {@link #getSlots() numbered} range of {@link VirtualStackSlot virtual stack slot} of * size {@link TargetDescription#wordSize}. */ -class VirtualStackSlotRange extends VirtualStackSlot { +public class VirtualStackSlotRange extends VirtualStackSlot { private static final long serialVersionUID = 5152592950118317121L; private final BitSet objects; diff -r 9c2396ef02db -r 74b144f7c54a graal/com.oracle.graal.lir/src/com/oracle/graal/lir/gen/LIRGenerationResult.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/gen/LIRGenerationResult.java Wed Jan 28 15:01:21 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/gen/LIRGenerationResult.java Wed Jan 28 19:32:47 2015 +0100 @@ -24,6 +24,7 @@ import com.oracle.graal.lir.*; import com.oracle.graal.lir.framemap.*; +import com.oracle.graal.lir.stackslotalloc.*; public interface LIRGenerationResult { @@ -31,7 +32,7 @@ * Returns the {@link FrameMapBuilder} for collecting the information to build a * {@link FrameMap}. * - * This method can only be used prior calling {@link #buildFrameMap()}. + * This method can only be used prior calling {@link #buildFrameMap}. */ FrameMapBuilder getFrameMapBuilder(); @@ -41,12 +42,12 @@ * * @see FrameMapBuilder#buildFrameMap */ - void buildFrameMap(); + void buildFrameMap(StackSlotAllocator allocator); /** * Returns the {@link FrameMap} associated with this {@link LIRGenerationResult}. * - * This method can only be called after {@link #buildFrameMap()}. + * This method can only be called after {@link #buildFrameMap}. */ FrameMap getFrameMap(); diff -r 9c2396ef02db -r 74b144f7c54a graal/com.oracle.graal.lir/src/com/oracle/graal/lir/gen/LIRGenerationResultBase.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/gen/LIRGenerationResultBase.java Wed Jan 28 15:01:21 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/gen/LIRGenerationResultBase.java Wed Jan 28 19:32:47 2015 +0100 @@ -24,6 +24,7 @@ import com.oracle.graal.lir.*; import com.oracle.graal.lir.framemap.*; +import com.oracle.graal.lir.stackslotalloc.*; public class LIRGenerationResultBase implements LIRGenerationResult { private final LIR lir; @@ -59,9 +60,9 @@ return frameMapBuilder; } - public void buildFrameMap() { + public void buildFrameMap(StackSlotAllocator allocator) { assert frameMap == null : "buildFrameMap() can only be called once!"; - frameMap = frameMapBuilder.buildFrameMap(this); + frameMap = frameMapBuilder.buildFrameMap(this, allocator); } public FrameMap getFrameMap() { diff -r 9c2396ef02db -r 74b144f7c54a graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/InstructionNumberer.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/InstructionNumberer.java Wed Jan 28 19:32:47 2015 +0100 @@ -0,0 +1,104 @@ +/* + * 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.lir.stackslotalloc; + +import static com.oracle.graal.api.code.CodeUtil.*; + +import java.util.*; + +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.lir.*; + +public class InstructionNumberer { + + private LIRInstruction[] opIdToInstructionMap; + private AbstractBlock[] opIdToBlockMap; + + /** + * Converts an {@linkplain LIRInstruction#id instruction id} to an instruction index. All LIR + * instructions in a method have an index one greater than their linear-scan order predecesor + * with the first instruction having an index of 0. + */ + private static int opIdToIndex(int opId) { + return opId >> 1; + } + + /** + * Retrieves the {@link LIRInstruction} based on its {@linkplain LIRInstruction#id id}. + * + * @param opId an instruction {@linkplain LIRInstruction#id id} + * @return the instruction whose {@linkplain LIRInstruction#id} {@code == id} + */ + protected LIRInstruction instructionForId(int opId) { + assert isEven(opId) : "opId not even"; + LIRInstruction instr = opIdToInstructionMap[opIdToIndex(opId)]; + assert instr.id() == opId; + return instr; + } + + /** + * Numbers all instructions in all blocks. + */ + protected void numberInstructions(LIR lir, List> sortedBlocks) { + + // Assign IDs to LIR nodes and build a mapping, lirOps, from ID to LIRInstruction node. + int numInstructions = 0; + for (AbstractBlock block : sortedBlocks) { + numInstructions += lir.getLIRforBlock(block).size(); + } + + // initialize with correct length + opIdToInstructionMap = new LIRInstruction[numInstructions]; + opIdToBlockMap = new AbstractBlock[numInstructions]; + + int opId = 0; + int index = 0; + for (AbstractBlock block : sortedBlocks) { + + List instructions = lir.getLIRforBlock(block); + + int numInst = instructions.size(); + for (int j = 0; j < numInst; j++) { + LIRInstruction op = instructions.get(j); + op.setId(opId); + + opIdToInstructionMap[index] = op; + opIdToBlockMap[index] = block; + assert instructionForId(opId) == op : "must match"; + + index++; + opId += 2; // numbering of lirOps by two + } + } + assert index == numInstructions : "must match"; + assert (index << 1) == opId : "must match: " + (index << 1); + } + + /** + * Gets the highest instruction id allocated by this object. + */ + public int maxOpId() { + assert opIdToInstructionMap.length > 0 : "no operations"; + return (opIdToInstructionMap.length - 1) << 1; + } +} diff -r 9c2396ef02db -r 74b144f7c54a graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/LSStackSlotAllocator.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/LSStackSlotAllocator.java Wed Jan 28 19:32:47 2015 +0100 @@ -0,0 +1,506 @@ +/* + * 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.lir.stackslotalloc; + +import static com.oracle.graal.api.code.ValueUtil.*; + +import java.util.*; +import java.util.function.*; + +import com.oracle.graal.api.code.*; +import com.oracle.graal.api.meta.*; +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.debug.Debug.Scope; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.LIRInstruction.OperandFlag; +import com.oracle.graal.lir.LIRInstruction.OperandMode; +import com.oracle.graal.lir.framemap.*; +import com.oracle.graal.lir.gen.*; +import com.oracle.graal.options.*; + +/** + * Linear Scan {@link StackSlotAllocator}. + */ +public class LSStackSlotAllocator implements StackSlotAllocator { + + public static class Options { + // @formatter:off + @Option(help = "Enable linear scan stack slot allocation.") + public static final OptionValue EnableLSStackSlotAllocation = new OptionValue<>(true); + // @formatter:on + } + + public void allocateStackSlots(FrameMapBuilderTool builder, LIRGenerationResult res) { + new Allocator(res.getLIR(), builder).allocate(); + } + + static final class Allocator extends InstructionNumberer { + private final LIR lir; + private final FrameMapBuilderTool frameMapBuilder; + private final StackInterval[] stackSlotMap; + private LinkedList unhandled; + private LinkedList active; + + private List> sortedBlocks; + + private Allocator(LIR lir, FrameMapBuilderTool frameMapBuilder) { + this.lir = lir; + this.frameMapBuilder = frameMapBuilder; + this.stackSlotMap = new StackInterval[frameMapBuilder.getNumberOfStackSlots()]; + } + + private void allocate() { + // create block ordering + List> blocks = lir.getControlFlowGraph().getBlocks(); + assert blocks.size() > 0; + + sortedBlocks = lir.getControlFlowGraph().getBlocks(); + numberInstructions(lir, sortedBlocks); + Debug.dump(lir, "After StackSlot numbering"); + + long currentFrameSize = Debug.isMeterEnabled() ? frameMapBuilder.getFrameMap().currentFrameSize() : 0; + // build intervals + // buildIntervals(); + try (Scope s = Debug.scope("StackSlotAllocationBuildIntervals"); Indent indent = Debug.logAndIndent("BuildIntervals")) { + buildIntervalsSlow(); + } + if (Debug.isEnabled()) { + verifyIntervals(); + } + if (Debug.isDumpEnabled()) { + dumpIntervals("Before stack slot allocation"); + } + // allocate stack slots + allocateStackSlots(); + if (Debug.isDumpEnabled()) { + dumpIntervals("After stack slot allocation"); + } + + // assign stack slots + assignStackSlots(); + Debug.dump(lir, "After StackSlot assignment"); + StackSlotAllocator.allocatedFramesize.add(frameMapBuilder.getFrameMap().currentFrameSize() - currentFrameSize); + } + + private void buildIntervalsSlow() { + new SlowIntervalBuilder().build(); + } + + private class SlowIntervalBuilder { + final BlockMap liveInMap; + final BlockMap liveOutMap; + + private SlowIntervalBuilder() { + liveInMap = new BlockMap<>(lir.getControlFlowGraph()); + liveOutMap = new BlockMap<>(lir.getControlFlowGraph()); + } + + private void build() { + Deque> worklist = new ArrayDeque<>(); + for (int i = lir.getControlFlowGraph().getBlocks().size() - 1; i >= 0; i--) { + worklist.add(lir.getControlFlowGraph().getBlocks().get(i)); + } + for (AbstractBlock block : lir.getControlFlowGraph().getBlocks()) { + liveInMap.put(block, new BitSet(frameMapBuilder.getNumberOfStackSlots())); + } + while (!worklist.isEmpty()) { + AbstractBlock block = worklist.poll(); + processBlock(block, worklist); + } + } + + /** + * Merge outSet with in-set of successors. + */ + private boolean updateOutBlock(AbstractBlock block) { + BitSet union = new BitSet(frameMapBuilder.getNumberOfStackSlots()); + block.getSuccessors().forEach(succ -> union.or(liveInMap.get(succ))); + BitSet outSet = liveOutMap.get(block); + // check if changed + if (outSet == null || !union.equals(outSet)) { + liveOutMap.put(block, union); + return true; + } + return false; + } + + private void processBlock(AbstractBlock block, Deque> worklist) { + if (updateOutBlock(block)) { + try (Indent indent = Debug.logAndIndent("handle block %s", block)) { + List instructions = lir.getLIRforBlock(block); + // get out set and mark intervals + BitSet outSet = liveOutMap.get(block); + markOutInterval(outSet, getBlockEnd(instructions)); + printLiveSet("liveOut", outSet); + + // process instructions + BlockClosure closure = new BlockClosure((BitSet) outSet.clone()); + for (int i = instructions.size() - 1; i >= 0; i--) { + LIRInstruction inst = instructions.get(i); + closure.processInstructionBottomUp(inst); + } + + // add predecessors to work list + worklist.addAll(block.getPredecessors()); + // set in set and mark intervals + BitSet inSet = closure.getCurrentSet(); + liveInMap.put(block, inSet); + markInInterval(inSet, getBlockBegin(instructions)); + printLiveSet("liveIn", inSet); + } + } + } + + private void printLiveSet(String label, BitSet liveSet) { + if (Debug.isLogEnabled()) { + try (Indent indent = Debug.logAndIndent(label)) { + Debug.log("%s", liveSetToString(liveSet)); + } + } + } + + private String liveSetToString(BitSet liveSet) { + StringBuilder sb = new StringBuilder(); + for (int i = liveSet.nextSetBit(0); i >= 0; i = liveSet.nextSetBit(i + 1)) { + StackInterval interval = getIntervalFromStackId(i); + sb.append(interval.getOperand()).append(" "); + } + return sb.toString(); + } + + protected void markOutInterval(BitSet outSet, int blockEndOpId) { + for (int i = outSet.nextSetBit(0); i >= 0; i = outSet.nextSetBit(i + 1)) { + StackInterval interval = getIntervalFromStackId(i); + Debug.log("mark live operand: %s", interval.getOperand()); + interval.addTo(blockEndOpId); + } + } + + protected void markInInterval(BitSet inSet, int blockFirstOpId) { + for (int i = inSet.nextSetBit(0); i >= 0; i = inSet.nextSetBit(i + 1)) { + StackInterval interval = getIntervalFromStackId(i); + Debug.log("mark live operand: %s", interval.getOperand()); + interval.addFrom(blockFirstOpId); + } + } + + private final class BlockClosure { + private final BitSet currentSet; + + private BlockClosure(BitSet set) { + currentSet = set; + } + + private BitSet getCurrentSet() { + return currentSet; + } + + /** + * Process all values of an instruction bottom-up, i.e. definitions before usages. + * Values that start or end at the current operation are not included. + */ + private void processInstructionBottomUp(LIRInstruction op) { + try (Indent indent = Debug.logAndIndent("handle op %d, %s", op.id(), op)) { + // kills + op.visitEachTemp(this::defConsumer); + op.visitEachOutput(this::defConsumer); + // forEachDestroyedCallerSavedRegister(op, this::defConsumer); + + // gen - values that are considered alive for this state + op.visitEachAlive(this::useConsumer); + op.visitEachState(this::useConsumer); + // mark locations + // gen + op.visitEachInput(this::useConsumer); + } + } + + /** + * @see InstructionValueConsumer + * + * @param inst + * @param operand + * @param mode + * @param flags + */ + private void useConsumer(LIRInstruction inst, Value operand, OperandMode mode, EnumSet flags) { + if (isVirtualStackSlot(operand)) { + VirtualStackSlot vslot = asVirtualStackSlot(operand); + addUse(vslot, inst, flags); + Debug.log("set operand: %s", operand); + currentSet.set(vslot.getId()); + } + } + + /** + * + * @see InstructionValueConsumer + * + * @param inst + * @param operand + * @param mode + * @param flags + */ + private void defConsumer(LIRInstruction inst, Value operand, OperandMode mode, EnumSet flags) { + if (isVirtualStackSlot(operand)) { + VirtualStackSlot vslot = asVirtualStackSlot(operand); + addDef(vslot, inst); + Debug.log("clear operand: %s", operand); + currentSet.clear(vslot.getId()); + } + + } + + private void addUse(VirtualStackSlot stackSlot, LIRInstruction inst, EnumSet flags) { + StackInterval interval = getOrCreateInterval(stackSlot); + if (flags.contains(OperandFlag.UNINITIALIZED)) { + // Stack slot is marked uninitialized so we have to assume it is live all + // the time. + interval.addDef(0); + interval.addUse(maxOpId()); + } else { + interval.addUse(inst.id()); + } + } + + private void addDef(VirtualStackSlot stackSlot, LIRInstruction inst) { + StackInterval interval = getOrCreateInterval(stackSlot); + interval.addDef(inst.id()); + } + + } + } + + private static int getBlockBegin(List instructions) { + return instructions.get(0).id(); + } + + private static int getBlockEnd(List instructions) { + return instructions.get(instructions.size() - 1).id() + 1; + } + + private StackInterval getOrCreateInterval(VirtualStackSlot stackSlot) { + StackInterval interval = get(stackSlot); + if (interval == null) { + interval = new StackInterval(stackSlot, stackSlot.getLIRKind()); + put(stackSlot, interval); + } + return interval; + } + + private StackInterval get(VirtualStackSlot stackSlot) { + return stackSlotMap[stackSlot.getId()]; + } + + private StackInterval getIntervalFromStackId(int id) { + return stackSlotMap[id]; + } + + private void put(VirtualStackSlot stackSlot, StackInterval interval) { + stackSlotMap[stackSlot.getId()] = interval; + } + + private void verifyIntervals() { + forEachInterval(interval -> { + assert interval.verify(this); + }); + } + + private void forEachInterval(Consumer proc) { + for (StackInterval interval : stackSlotMap) { + if (interval != null) { + proc.accept(interval); + } + } + } + + public void dumpIntervals(String label) { + Debug.dump(stackSlotMap, label); + } + + private void createUnhandled() { + unhandled = new LinkedList<>(); + active = new LinkedList<>(); + forEachInterval(this::insertSortedByFrom); + } + + private void insertSortedByFrom(StackInterval interval) { + unhandled.add(interval); + unhandled.sort((a, b) -> a.from() - b.from()); + } + + private void insertSortedByTo(StackInterval interval) { + active.add(interval); + active.sort((a, b) -> a.to() - b.to()); + } + + private void allocateStackSlots() { + // create interval lists + createUnhandled(); + + for (StackInterval current = activateNext(); current != null; current = activateNext()) { + try (Indent indent = Debug.logAndIndent("allocate %s", current)) { + allocateSlot(current); + } + } + + } + + private void allocateSlot(StackInterval current) { + VirtualStackSlot virtualSlot = current.getOperand(); + final StackSlot location; + if (virtualSlot instanceof VirtualStackSlotRange) { + // No reuse of ranges (yet). + VirtualStackSlotRange slotRange = (VirtualStackSlotRange) virtualSlot; + location = frameMapBuilder.getFrameMap().allocateStackSlots(slotRange.getSlots(), slotRange.getObjects()); + StackSlotAllocator.virtualFramesize.add(frameMapBuilder.getFrameMap().spillSlotRangeSize(slotRange.getSlots())); + StackSlotAllocator.allocatedSlots.increment(); + } else { + assert virtualSlot instanceof SimpleVirtualStackSlot : "Unexpexted VirtualStackSlot type: " + virtualSlot; + StackSlot slot = findFreeSlot((SimpleVirtualStackSlot) virtualSlot); + if (slot != null) { + /* + * Free stack slot available. Note that we create a new one because the kind + * might not match. + */ + location = StackSlot.get(current.kind(), slot.getRawOffset(), slot.getRawAddFrameSize()); + StackSlotAllocator.reusedSlots.increment(); + Debug.log(1, "Reuse stack slot %s (reallocated from %s) for virtual stack slot %s", location, slot, virtualSlot); + } else { + // Allocate new stack slot. + location = frameMapBuilder.getFrameMap().allocateSpillSlot(virtualSlot.getLIRKind()); + StackSlotAllocator.virtualFramesize.add(frameMapBuilder.getFrameMap().spillSlotSize(virtualSlot.getLIRKind())); + StackSlotAllocator.allocatedSlots.increment(); + Debug.log(1, "New stack slot %s for virtual stack slot %s", location, virtualSlot); + } + } + Debug.log("Allocate location %s for interval %s", location, current); + current.setLocation(location); + } + + private static enum SlotSize { + Size1, + Size2, + Size4, + Size8, + Illegal; + } + + private SlotSize forKind(LIRKind kind) { + switch (frameMapBuilder.getFrameMap().spillSlotSize(kind)) { + case 1: + return SlotSize.Size1; + case 2: + return SlotSize.Size2; + case 4: + return SlotSize.Size4; + case 8: + return SlotSize.Size8; + default: + return SlotSize.Illegal; + } + } + + private EnumMap> freeSlots = new EnumMap<>(SlotSize.class); + + private StackSlot findFreeSlot(SimpleVirtualStackSlot slot) { + assert slot != null; + SlotSize size = forKind(slot.getLIRKind()); + LinkedList freeList = size == SlotSize.Illegal ? null : freeSlots.get(size); + if (freeList == null) { + return null; + } + return freeList.pollFirst(); + } + + private void freeSlot(StackSlot slot) { + SlotSize size = forKind(slot.getLIRKind()); + if (size == SlotSize.Illegal) { + return; + } + LinkedList freeList = freeSlots.get(size); + if (freeList == null) { + freeList = new LinkedList<>(); + freeSlots.put(size, freeList); + } + freeList.add(slot); + } + + private StackInterval activateNext() { + if (unhandled.isEmpty()) { + return null; + } + StackInterval next = unhandled.pollFirst(); + for (int id = next.from(); activePeekId() < id;) { + finished(active.pollFirst()); + } + Debug.log("activte %s", next); + insertSortedByTo(next); + return next; + } + + private int activePeekId() { + StackInterval first = active.peekFirst(); + if (first == null) { + return Integer.MAX_VALUE; + } + return first.to(); + } + + private void finished(StackInterval interval) { + StackSlot location = interval.location(); + Debug.log("finished %s (freeing %s)", interval, location); + freeSlot(location); + } + + private void assignStackSlots() { + for (AbstractBlock block : sortedBlocks) { + lir.getLIRforBlock(block).forEach(op -> { + op.forEachInput(this::assignSlot); + op.forEachAlive(this::assignSlot); + op.forEachState(this::assignSlot); + + op.forEachTemp(this::assignSlot); + op.forEachOutput(this::assignSlot); + }); + } + } + + /** + * @see ValueProcedure + * @param value + * @param mode + * @param flags + */ + private Value assignSlot(Value value, OperandMode mode, EnumSet flags) { + if (isVirtualStackSlot(value)) { + VirtualStackSlot slot = asVirtualStackSlot(value); + StackInterval interval = get(slot); + assert interval != null; + return interval.location(); + } + return value; + } + } +} diff -r 9c2396ef02db -r 74b144f7c54a graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/SimpleStackSlotAllocator.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/SimpleStackSlotAllocator.java Wed Jan 28 19:32:47 2015 +0100 @@ -0,0 +1,93 @@ +/* + * 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.lir.stackslotalloc; + +import static com.oracle.graal.api.code.ValueUtil.*; + +import com.oracle.graal.api.code.*; +import com.oracle.graal.compiler.common.*; +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.debug.Debug.*; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.framemap.*; +import com.oracle.graal.lir.gen.*; + +public class SimpleStackSlotAllocator implements StackSlotAllocator { + + public void allocateStackSlots(FrameMapBuilderTool builder, LIRGenerationResult res) { + StackSlot[] mapping = new StackSlot[builder.getNumberOfStackSlots()]; + long currentFrameSize = Debug.isMeterEnabled() ? builder.getFrameMap().currentFrameSize() : 0; + for (VirtualStackSlot virtualSlot : builder.getStackSlots()) { + final StackSlot slot; + if (virtualSlot instanceof SimpleVirtualStackSlot) { + slot = mapSimpleVirtualStackSlot(builder, (SimpleVirtualStackSlot) virtualSlot); + virtualFramesize.add(builder.getFrameMap().spillSlotSize(virtualSlot.getLIRKind())); + } else if (virtualSlot instanceof VirtualStackSlotRange) { + VirtualStackSlotRange slotRange = (VirtualStackSlotRange) virtualSlot; + slot = mapVirtualStackSlotRange(builder, slotRange); + virtualFramesize.add(builder.getFrameMap().spillSlotRangeSize(slotRange.getSlots())); + } else { + throw GraalInternalError.shouldNotReachHere("Unknown VirtualStackSlot: " + virtualSlot); + } + allocatedSlots.increment(); + mapping[virtualSlot.getId()] = slot; + } + updateLIR(res, mapping); + allocatedFramesize.add(builder.getFrameMap().currentFrameSize() - currentFrameSize); + } + + protected void updateLIR(LIRGenerationResult res, StackSlot[] mapping) { + try (Scope scope = Debug.scope("StackSlotMappingLIR")) { + ValueProcedure updateProc = (value, mode, flags) -> { + if (isVirtualStackSlot(value)) { + StackSlot stackSlot = mapping[asVirtualStackSlot(value).getId()]; + Debug.log("map %s -> %s", value, stackSlot); + return stackSlot; + } + return value; + }; + for (AbstractBlock block : res.getLIR().getControlFlowGraph().getBlocks()) { + try (Indent indent0 = Debug.logAndIndent("block: %s", block)) { + for (LIRInstruction inst : res.getLIR().getLIRforBlock(block)) { + try (Indent indent1 = Debug.logAndIndent("Inst: %d: %s", inst.id(), inst)) { + inst.forEachAlive(updateProc); + inst.forEachInput(updateProc); + inst.forEachOutput(updateProc); + inst.forEachTemp(updateProc); + inst.forEachState(updateProc); + } + } + } + } + } + } + + protected StackSlot mapSimpleVirtualStackSlot(FrameMapBuilderTool builder, SimpleVirtualStackSlot virtualStackSlot) { + return builder.getFrameMap().allocateSpillSlot(virtualStackSlot.getLIRKind()); + } + + protected StackSlot mapVirtualStackSlotRange(FrameMapBuilderTool builder, VirtualStackSlotRange virtualStackSlot) { + return builder.getFrameMap().allocateStackSlots(virtualStackSlot.getSlots(), virtualStackSlot.getObjects()); + } +} diff -r 9c2396ef02db -r 74b144f7c54a graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/StackInterval.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/StackInterval.java Wed Jan 28 19:32:47 2015 +0100 @@ -0,0 +1,134 @@ +/* + * 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.lir.stackslotalloc; + +import com.oracle.graal.api.code.*; +import com.oracle.graal.api.meta.*; +import com.oracle.graal.debug.*; + +public class StackInterval { + + private static final int INVALID_START = Integer.MAX_VALUE; + private static final int INVALID_END = Integer.MIN_VALUE; + private final VirtualStackSlot operand; + private final LIRKind kind; + private int from = INVALID_START; + private int to = INVALID_END; + private final StackUsePosList usePos; + private StackSlot location; + + public enum UseType { + // Prefixes for c1viz + M_USE, + S_DEF + } + + public StackInterval(VirtualStackSlot operand, LIRKind kind) { + this.operand = operand; + this.kind = kind; + this.usePos = new StackUsePosList(); + } + + public boolean verify(LSStackSlotAllocator.Allocator allocator) { + assert usePosList().verify(); + // maxOpId + 1 it the last position in the last block (i.e. the "write position") + assert from >= 0 && to <= allocator.maxOpId() + 1 : String.format("from %d, to %d, maxOpId %d", from, to, allocator.maxOpId()); + return true; + } + + public VirtualStackSlot getOperand() { + return operand; + } + + public void addUse(int opId) { + addTo(opId); + Debug.log("Adding use pos: %d", opId); + usePos.add(opId, UseType.M_USE); + } + + public void addDef(int opId) { + addFrom(opId); + Debug.log("Adding def pos: %d", opId); + usePos.add(opId, UseType.S_DEF); + } + + public void addTo(int opId) { + if (opId >= to) { + to = opId; + } + } + + protected void addFrom(int opId) { + if (from > opId) { + from = opId; + // set opId also as to if it has not yet been set + if (to == INVALID_END) { + to = opId; + } + } + } + + public LIRKind kind() { + return kind; + } + + public StackSlot location() { + return location; + } + + public void setLocation(StackSlot location) { + this.location = location; + } + + public StackInterval locationHint() { + return null; + } + + public int from() { + return from; + } + + public int to() { + return to; + } + + public StackUsePosList usePosList() { + return usePos; + } + + public void fixFrom() { + if (from == INVALID_START) { + from = 0; + } + } + + public boolean isFixed() { + return from == 0; + } + + @Override + public String toString() { + return String.format("SI[%d-%d] k=%s o=%s l=%s", from, to, kind, operand, location); + } + +} diff -r 9c2396ef02db -r 74b144f7c54a graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/StackSlotAllocator.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/StackSlotAllocator.java Wed Jan 28 19:32:47 2015 +0100 @@ -0,0 +1,53 @@ +/* + * 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.lir.stackslotalloc; + +import com.oracle.graal.api.code.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.lir.framemap.*; +import com.oracle.graal.lir.gen.*; + +/** + * A {@link StackSlotAllocator} is responsible for translating {@link VirtualStackSlot virtual} + * stack slots into {@link StackSlot real} stack slots. This includes changing all occurrences of + * {@link VirtualStackSlot} in the {@link LIRGenerationResult#getLIR() LIR} to {@link StackSlot}. + */ +public interface StackSlotAllocator { + /** + * The number of allocated stack slots. + */ + static final DebugMetric allocatedSlots = Debug.metric("StackSlotAllocator[allocatedSlots]"); + /** + * The number of reused stack slots. + */ + static final DebugMetric reusedSlots = Debug.metric("StackSlotAllocator[reusedSlots]"); + /** + * The size (in bytes) required for all allocated stack slots. Note that this number + * corresponds to the actual frame size and might include alignment. + */ + static final DebugMetric allocatedFramesize = Debug.metric("StackSlotAllocator[AllocatedFramesize]"); + /** The size (in bytes) required for all virtual stack slots. */ + static final DebugMetric virtualFramesize = Debug.metric("StackSlotAllocator[VirtualFramesize]"); + + void allocateStackSlots(FrameMapBuilderTool builder, LIRGenerationResult res); +} diff -r 9c2396ef02db -r 74b144f7c54a graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/StackUsePosList.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/StackUsePosList.java Wed Jan 28 19:32:47 2015 +0100 @@ -0,0 +1,101 @@ +/* + * 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.lir.stackslotalloc; + +import java.util.*; + +import com.oracle.graal.compiler.common.*; +import com.oracle.graal.lir.stackslotalloc.StackInterval.*; + +public class StackUsePosList { + + LinkedList usePosList; + LinkedList typeList; + + StackUsePosList() { + this.usePosList = new LinkedList<>(); + this.typeList = new LinkedList<>(); + } + + public int size() { + return usePosList.size(); + } + + public int usePos(int i) { + return usePosList.get(i); + } + + public void add(int opId, UseType type) { + if (usePosList.isEmpty() || opId <= usePosList.getLast()) { + usePosList.add(opId); + typeList.add(type); + } else if (opId >= usePosList.getFirst()) { + usePosList.addFirst(opId); + typeList.addFirst(type); + } else { + int size = usePosList.size(); + + assert size >= 2 : "Should be handled by the cases above"; + assert size == typeList.size() : "types and use pos out of sync"; + + ListIterator posIt = usePosList.listIterator(size - 1); + ListIterator typeIt = typeList.listIterator(size - 1); + + // we start with size-2 because we know it will not inserted at the end + while (posIt.hasPrevious()) { + assert posIt.nextIndex() == typeIt.nextIndex(); + int current = posIt.previous(); + + if (current >= opId) { + posIt.next(); + posIt.add(opId); + typeIt.add(type); + assert verify(); + return; + } + typeIt.previous(); + } + GraalInternalError.shouldNotReachHere(String.format("Unable to insert %d into %s", opId, usePosList)); + } + } + + public UseType getType(int i) { + return typeList.get(i); + } + + @Override + public String toString() { + return usePosList.toString() + System.lineSeparator() + typeList.toString(); + } + + public boolean verify() { + int prev = -1; + for (int i = usePosList.size() - 1; i >= 0; --i) { + int current = usePosList.get(i); + assert prev <= current : String.format("use positions not sorted: %d after %d", current, prev); + prev = current; + } + return true; + } + +} diff -r 9c2396ef02db -r 74b144f7c54a graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java --- a/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java Wed Jan 28 15:01:21 2015 +0100 +++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java Wed Jan 28 19:32:47 2015 +0100 @@ -37,6 +37,7 @@ import com.oracle.graal.java.*; import com.oracle.graal.java.BciBlockMapping.BciBlock; import com.oracle.graal.lir.*; +import com.oracle.graal.lir.stackslotalloc.*; import com.oracle.graal.nodeinfo.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.calc.*; @@ -560,6 +561,46 @@ out.println(); } + public void printStackIntervals(String label, StackInterval[] intervals) { + begin("intervals"); + out.println(String.format("name \"%s\"", label)); + + for (StackInterval interval : intervals) { + if (interval != null) { + printStackInterval(interval); + } + } + + end("intervals"); + } + + private void printStackInterval(StackInterval interval) { + out.printf("%s %s ", interval.getOperand(), interval.isFixed() ? "fixed" : interval.kind().getPlatformKind()); + if (interval.location() != null) { + out.printf("\"[%s|%c]\"", interval.location(), interval.location().getKind().getTypeChar()); + } else { + out.printf("\"[%s|%c]\"", interval.getOperand(), interval.getOperand().getKind().getTypeChar()); + } + + StackInterval hint = interval.locationHint(); + out.printf("%s %s ", interval.getOperand(), hint != null ? hint.getOperand() : -1); + + out.printf("[%d, %d[", interval.from(), interval.to()); + + // print use positions + int prev = -1; + StackUsePosList usePosList = interval.usePosList(); + for (int i = usePosList.size() - 1; i >= 0; --i) { + assert prev <= usePosList.usePos(i) : "use positions not sorted"; + out.printf("%d %s ", usePosList.usePos(i), usePosList.getType(i)); + prev = usePosList.usePos(i); + } + + // print spill state + out.printf(" \"%s\"", "NOT_SUPPORTED"); + out.println(); + } + public void printSchedule(String message, SchedulePhase theSchedule) { schedule = theSchedule; cfg = schedule.getCFG(); diff -r 9c2396ef02db -r 74b144f7c54a graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinterObserver.java --- a/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinterObserver.java Wed Jan 28 15:01:21 2015 +0100 +++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinterObserver.java Wed Jan 28 19:32:47 2015 +0100 @@ -35,6 +35,7 @@ import com.oracle.graal.graph.*; import com.oracle.graal.java.*; import com.oracle.graal.lir.*; +import com.oracle.graal.lir.stackslotalloc.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.phases.schedule.*; @@ -181,7 +182,8 @@ cfgPrinter.printMachineCode(codeCache.disassemble((CompilationResult) tuple[0], (InstalledCode) tuple[1]), message); } else if (object instanceof Interval[]) { cfgPrinter.printIntervals(message, (Interval[]) object); - + } else if (object instanceof StackInterval[]) { + cfgPrinter.printStackIntervals(message, (StackInterval[]) object); } cfgPrinter.target = null;