Mercurial > hg > truffle
changeset 19031:beb7c10b7747
Move StackSlotAllocators into a package.
line wrap: on
line diff
--- a/graal/com.oracle.graal.baseline/src/com/oracle/graal/baseline/BaselineBytecodeParser.java Tue Jan 13 17:50:58 2015 +0100 +++ b/graal/com.oracle.graal.baseline/src/com/oracle/graal/baseline/BaselineBytecodeParser.java Tue Jan 13 17:52:18 2015 +0100 @@ -45,6 +45,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<Value, BaselineFrameStateBuilder> implements BytecodeParserTool {
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Tue Jan 13 17:50:58 2015 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Tue Jan 13 17:52:18 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.*;
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMapBuilder.java Tue Jan 13 17:50:58 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMapBuilder.java Tue Jan 13 17:52:18 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
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMapBuilderImpl.java Tue Jan 13 17:50:58 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMapBuilderImpl.java Tue Jan 13 17:52:18 2015 +0100 @@ -30,6 +30,7 @@ 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.
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/InstructionNumberer.java Tue Jan 13 17:50:58 2015 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,104 +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 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<? extends AbstractBlock<?>> 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<LIRInstruction> 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; - } -}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/LSStackSlotAllocator.java Tue Jan 13 17:50:58 2015 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,498 +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 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.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<Boolean> 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<StackInterval> unhandled; - private LinkedList<StackInterval> active; - - private List<? extends AbstractBlock<?>> 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<? extends AbstractBlock<?>> 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<BitSet> liveInMap; - final BlockMap<BitSet> liveOutMap; - - private SlowIntervalBuilder() { - liveInMap = new BlockMap<>(lir.getControlFlowGraph()); - liveOutMap = new BlockMap<>(lir.getControlFlowGraph()); - } - - private void build() { - Deque<AbstractBlock<?>> 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<AbstractBlock<?>> worklist) { - if (updateOutBlock(block)) { - try (Indent indent = Debug.logAndIndent("handle block %s", block)) { - List<LIRInstruction> 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<OperandFlag> flags) { - if (isVirtualStackSlot(operand)) { - VirtualStackSlot vslot = asVirtualStackSlot(operand); - addUse(vslot, inst); - 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<OperandFlag> 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) { - StackInterval interval = getOrCreateInterval(stackSlot); - interval.addUse(inst.id()); - } - - private void addDef(VirtualStackSlot stackSlot, LIRInstruction inst) { - StackInterval interval = getOrCreateInterval(stackSlot); - interval.addDef(inst.id()); - } - - } - } - - private static int getBlockBegin(List<LIRInstruction> instructions) { - return instructions.get(0).id(); - } - - private static int getBlockEnd(List<LIRInstruction> 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<StackInterval> 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<SlotSize, LinkedList<StackSlot>> freeSlots = new EnumMap<>(SlotSize.class); - - private StackSlot findFreeSlot(SimpleVirtualStackSlot slot) { - assert slot != null; - SlotSize size = forKind(slot.getLIRKind()); - LinkedList<StackSlot> 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<StackSlot> 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<OperandFlag> flags) { - if (isVirtualStackSlot(value)) { - VirtualStackSlot slot = asVirtualStackSlot(value); - StackInterval interval = get(slot); - assert interval != null; - return interval.location(); - } - return value; - } - } -}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/SimpleStackSlotAllocator.java Tue Jan 13 17:50:58 2015 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,92 +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 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.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()); - } -}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/StackInterval.java Tue Jan 13 17:50:58 2015 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,134 +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.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); - } - -}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/StackSlotAllocator.java Tue Jan 13 17:50:58 2015 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,52 +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.debug.*; -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); -}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/StackUsePosList.java Tue Jan 13 17:50:58 2015 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,101 +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 java.util.*; - -import com.oracle.graal.compiler.common.*; -import com.oracle.graal.lir.framemap.StackInterval.*; - -public class StackUsePosList { - - LinkedList<Integer> usePosList; - LinkedList<UseType> 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<Integer> posIt = usePosList.listIterator(size - 1); - ListIterator<UseType> 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; - } - -}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/gen/LIRGenerationResult.java Tue Jan 13 17:50:58 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/gen/LIRGenerationResult.java Tue Jan 13 17:52:18 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 {
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/gen/LIRGenerationResultBase.java Tue Jan 13 17:50:58 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/gen/LIRGenerationResultBase.java Tue Jan 13 17:52:18 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;
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/InstructionNumberer.java Tue Jan 13 17:52:18 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<? extends AbstractBlock<?>> 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<LIRInstruction> 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; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/LSStackSlotAllocator.java Tue Jan 13 17:52:18 2015 +0100 @@ -0,0 +1,499 @@ +/* + * 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<Boolean> 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<StackInterval> unhandled; + private LinkedList<StackInterval> active; + + private List<? extends AbstractBlock<?>> 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<? extends AbstractBlock<?>> 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<BitSet> liveInMap; + final BlockMap<BitSet> liveOutMap; + + private SlowIntervalBuilder() { + liveInMap = new BlockMap<>(lir.getControlFlowGraph()); + liveOutMap = new BlockMap<>(lir.getControlFlowGraph()); + } + + private void build() { + Deque<AbstractBlock<?>> 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<AbstractBlock<?>> worklist) { + if (updateOutBlock(block)) { + try (Indent indent = Debug.logAndIndent("handle block %s", block)) { + List<LIRInstruction> 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<OperandFlag> flags) { + if (isVirtualStackSlot(operand)) { + VirtualStackSlot vslot = asVirtualStackSlot(operand); + addUse(vslot, inst); + 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<OperandFlag> 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) { + StackInterval interval = getOrCreateInterval(stackSlot); + interval.addUse(inst.id()); + } + + private void addDef(VirtualStackSlot stackSlot, LIRInstruction inst) { + StackInterval interval = getOrCreateInterval(stackSlot); + interval.addDef(inst.id()); + } + + } + } + + private static int getBlockBegin(List<LIRInstruction> instructions) { + return instructions.get(0).id(); + } + + private static int getBlockEnd(List<LIRInstruction> 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<StackInterval> 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<SlotSize, LinkedList<StackSlot>> freeSlots = new EnumMap<>(SlotSize.class); + + private StackSlot findFreeSlot(SimpleVirtualStackSlot slot) { + assert slot != null; + SlotSize size = forKind(slot.getLIRKind()); + LinkedList<StackSlot> 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<StackSlot> 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<OperandFlag> flags) { + if (isVirtualStackSlot(value)) { + VirtualStackSlot slot = asVirtualStackSlot(value); + StackInterval interval = get(slot); + assert interval != null; + return interval.location(); + } + return value; + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/SimpleStackSlotAllocator.java Tue Jan 13 17:52:18 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()); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/StackInterval.java Tue Jan 13 17:52:18 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); + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/StackSlotAllocator.java Tue Jan 13 17:52:18 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); +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/StackUsePosList.java Tue Jan 13 17:52:18 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<Integer> usePosList; + LinkedList<UseType> 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<Integer> posIt = usePosList.listIterator(size - 1); + ListIterator<UseType> 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; + } + +}
--- a/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java Tue Jan 13 17:50:58 2015 +0100 +++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java Tue Jan 13 17:52:18 2015 +0100 @@ -37,7 +37,7 @@ import com.oracle.graal.java.*; import com.oracle.graal.java.BciBlockMapping.BciBlock; import com.oracle.graal.lir.*; -import com.oracle.graal.lir.framemap.*; +import com.oracle.graal.lir.stackslotalloc.*; import com.oracle.graal.nodeinfo.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.calc.*;
--- a/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinterObserver.java Tue Jan 13 17:50:58 2015 +0100 +++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinterObserver.java Tue Jan 13 17:52:18 2015 +0100 @@ -35,7 +35,7 @@ import com.oracle.graal.graph.*; import com.oracle.graal.java.*; import com.oracle.graal.lir.*; -import com.oracle.graal.lir.framemap.*; +import com.oracle.graal.lir.stackslotalloc.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.phases.schedule.*;