# HG changeset patch # User Josef Eisl # Date 1421167328 -3600 # Node ID f59fc4850df5c1b90debb6c2011bb124bb38f4b1 # Parent 9236f6bd4aafbf2bcb9c5bd46a5eac40b8ebb66a StackSlotAllocator: add linear scan stack slot allocator. diff -r 9236f6bd4aaf -r f59fc4850df5 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 Tue Jan 13 17:37:44 2015 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Tue Jan 13 17:42:08 2015 +0100 @@ -357,7 +357,13 @@ try (Scope s1 = Debug.scope("BuildFrameMap")) { // build frame map - lirGenRes.buildFrameMap(new SimpleStackSlotAllocator()); + final StackSlotAllocator allocator; + if (LSStackSlotAllocator.Options.EnableLSStackSlotAllocation.getValue()) { + allocator = new LSStackSlotAllocator(); + } else { + allocator = new SimpleStackSlotAllocator(); + } + lirGenRes.buildFrameMap(allocator); Debug.dump(lir, "After FrameMap building"); } try (Scope s1 = Debug.scope("MarkLocations")) { diff -r 9236f6bd4aaf -r f59fc4850df5 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/InstructionNumberer.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/InstructionNumberer.java Tue Jan 13 17:42:08 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.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> 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 9236f6bd4aaf -r f59fc4850df5 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/LSStackSlotAllocator.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/LSStackSlotAllocator.java Tue Jan 13 17:42:08 2015 +0100 @@ -0,0 +1,498 @@ +/* + * 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 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); + 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) { + 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 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 9236f6bd4aaf -r f59fc4850df5 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/StackInterval.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/StackInterval.java Tue Jan 13 17:42:08 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.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); + } + +} diff -r 9236f6bd4aaf -r f59fc4850df5 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/StackUsePosList.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/StackUsePosList.java Tue Jan 13 17:42:08 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.framemap; + +import java.util.*; + +import com.oracle.graal.compiler.common.*; +import com.oracle.graal.lir.framemap.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; + } + +}