Mercurial > hg > truffle
changeset 19092:5e33637f5e5a
Merge StackSlotAllocation cleanups.
| author | Josef Eisl <josef.eisl@jku.at> |
|---|---|
| date | Tue, 03 Feb 2015 11:10:24 +0100 |
| parents | 336adcd0070b (current diff) 684612ee6abb (diff) |
| children | 81e464d45137 08eacfeb8b76 |
| files | graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/InstructionNumberer.java graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/StackUsePosList.java |
| diffstat | 7 files changed, 430 insertions(+), 538 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Tue Feb 03 04:17:06 2015 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Tue Feb 03 11:10:24 2015 +0100 @@ -356,7 +356,7 @@ try (Scope s1 = Debug.scope("BuildFrameMap")) { // build frame map final StackSlotAllocator allocator; - if (LSStackSlotAllocator.Options.EnableLSStackSlotAllocation.getValue()) { + if (LSStackSlotAllocator.Options.LSStackSlotAllocation.getValue()) { allocator = new LSStackSlotAllocator(); } else { allocator = new SimpleStackSlotAllocator();
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/FixPointIntervalBuilder.java Tue Feb 03 11:10:24 2015 +0100 @@ -0,0 +1,266 @@ +/* + * Copyright (c) 2015, 2015, 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 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.lir.*; +import com.oracle.graal.lir.LIRInstruction.OperandFlag; +import com.oracle.graal.lir.LIRInstruction.OperandMode; + +/** + * Calculates the stack intervals using a worklist-based backwards data-flow analysis. + */ +final class FixPointIntervalBuilder { + private final BlockMap<BitSet> liveInMap; + private final BlockMap<BitSet> liveOutMap; + private final LIR lir; + private final int maxOpId; + private final StackInterval[] stackSlotMap; + + /** + * The number of allocated stack slots. + */ + private static final DebugMetric uninitializedSlots = Debug.metric("StackSlotAllocator[uninitializedSlots]"); + + FixPointIntervalBuilder(LIR lir, StackInterval[] stackSlotMap, int maxOpId) { + this.lir = lir; + this.stackSlotMap = stackSlotMap; + this.maxOpId = maxOpId; + liveInMap = new BlockMap<>(lir.getControlFlowGraph()); + liveOutMap = new BlockMap<>(lir.getControlFlowGraph()); + } + + 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(stackSlotMap.length)); + } + 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(stackSlotMap.length); + 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(); + } + + private 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); + } + } + + private 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); + + // 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, flags); + Debug.log("set operand: %s", operand); + currentSet.set(vslot.getId()); + } + } + + /** + * + * @see InstructionValueConsumer + * + * @param inst + * @param operand + * @param mode + * @param flags + */ + private void defConsumer(LIRInstruction inst, Value operand, OperandMode mode, EnumSet<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, EnumSet<OperandFlag> flags) { + StackInterval interval = getOrCreateInterval(stackSlot); + if (flags.contains(OperandFlag.UNINITIALIZED)) { + // Stack slot is marked uninitialized so we have to assume it is live all + // the time. + if (Debug.isMeterEnabled() && !(interval.from() == 0 && interval.to() == maxOpId)) { + uninitializedSlots.increment(); + } + interval.addFrom(0); + interval.addTo(maxOpId); + } else { + interval.addTo(inst.id()); + } + } + + private void addDef(VirtualStackSlot stackSlot, LIRInstruction inst) { + StackInterval interval = getOrCreateInterval(stackSlot); + interval.addFrom(inst.id()); + } + + } + + private StackInterval get(VirtualStackSlot stackSlot) { + return stackSlotMap[stackSlot.getId()]; + } + + private void put(VirtualStackSlot stackSlot, StackInterval interval) { + stackSlotMap[stackSlot.getId()] = interval; + } + + 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 getIntervalFromStackId(int id) { + return stackSlotMap[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; + } + +}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/InstructionNumberer.java Tue Feb 03 04:17:06 2015 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,104 +0,0 @@ -/* - * Copyright (c) 2014, 2015, 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; - } -}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/LSStackSlotAllocator.java Tue Feb 03 04:17:06 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/LSStackSlotAllocator.java Tue Feb 03 11:10:24 2015 +0100 @@ -53,329 +53,122 @@ public static class Options { // @formatter:off - @Option(help = "Enable linear scan stack slot allocation.", type = OptionType.Debug) - public static final OptionValue<Boolean> EnableLSStackSlotAllocation = new OptionValue<>(true); + @Option(help = "Use linear scan stack slot allocation.", type = OptionType.Debug) + public static final OptionValue<Boolean> LSStackSlotAllocation = new OptionValue<>(true); // @formatter:on } - /** - * The number of allocated stack slots. - */ - static final DebugMetric uninitializedSlots = Debug.metric("StackSlotAllocator[uninitializedSlots]"); - public void allocateStackSlots(FrameMapBuilderTool builder, LIRGenerationResult res) { new Allocator(res.getLIR(), builder).allocate(); } - static final class Allocator extends InstructionNumberer { + private static final class Allocator { 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 final PriorityQueue<StackInterval> unhandled; + private final PriorityQueue<StackInterval> active; + private final List<? extends AbstractBlock<?>> sortedBlocks; + private final int maxOpId; private Allocator(LIR lir, FrameMapBuilderTool frameMapBuilder) { this.lir = lir; this.frameMapBuilder = frameMapBuilder; this.stackSlotMap = new StackInterval[frameMapBuilder.getNumberOfStackSlots()]; + this.sortedBlocks = lir.getControlFlowGraph().getBlocks(); + + // insert by from + this.unhandled = new PriorityQueue<>((a, b) -> a.from() - b.from()); + // insert by to + this.active = new PriorityQueue<>((a, b) -> a.to() - b.to()); + + // step 1: number instructions + this.maxOpId = numberInstructions(lir, sortedBlocks); } 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(); + // step 2: build intervals try (Scope s = Debug.scope("StackSlotAllocationBuildIntervals"); Indent indent = Debug.logAndIndent("BuildIntervals")) { - buildIntervalsSlow(); + buildIntervals(); } + // step 3: verify intervals if (Debug.isEnabled()) { verifyIntervals(); } if (Debug.isDumpEnabled()) { dumpIntervals("Before stack slot allocation"); } - // allocate stack slots + // step 4: allocate stack slots allocateStackSlots(); if (Debug.isDumpEnabled()) { dumpIntervals("After stack slot allocation"); } - // assign stack slots + // step 5: assign stack slots assignStackSlots(); Debug.dump(lir, "After StackSlot assignment"); - StackSlotAllocator.allocatedFramesize.add(frameMapBuilder.getFrameMap().currentFrameSize() - currentFrameSize); - } - - private void buildIntervalsSlow() { - new SlowIntervalBuilder().build(); - } - - /** - * Calculates the stack intervals using a worklist-based backwards data-flow analysis. - */ - private final 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, flags); - Debug.log("set operand: %s", operand); - currentSet.set(vslot.getId()); - } - } - - /** - * - * @see InstructionValueConsumer - * - * @param inst - * @param operand - * @param mode - * @param flags - */ - private void defConsumer(LIRInstruction inst, Value operand, OperandMode mode, EnumSet<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, EnumSet<OperandFlag> flags) { - StackInterval interval = getOrCreateInterval(stackSlot); - if (flags.contains(OperandFlag.UNINITIALIZED)) { - // Stack slot is marked uninitialized so we have to assume it is live all - // the time. - if (Debug.isMeterEnabled() && !(interval.from() == 0 && interval.to() == maxOpId())) { - uninitializedSlots.increment(); - } - interval.addDef(0); - interval.addUse(maxOpId()); - } else { - interval.addUse(inst.id()); - } - } - - private void addDef(VirtualStackSlot stackSlot, LIRInstruction inst) { - StackInterval interval = getOrCreateInterval(stackSlot); - interval.addDef(inst.id()); - } - + if (Debug.isMeterEnabled()) { + StackSlotAllocator.allocatedFramesize.add(frameMapBuilder.getFrameMap().currentFrameSize() - currentFrameSize); } } - private static int getBlockBegin(List<LIRInstruction> instructions) { - return instructions.get(0).id(); - } + // ==================== + // step 1: number instructions + // ==================== + + /** + * Numbers all instructions in all blocks. + * + * @return The id of the last operation. + */ + private static int numberInstructions(LIR lir, List<? extends AbstractBlock<?>> sortedBlocks) { + int opId = 0; + int index = 0; + for (AbstractBlock<?> block : sortedBlocks) { - private static int getBlockEnd(List<LIRInstruction> instructions) { - return instructions.get(instructions.size() - 1).id() + 1; + 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); + + index++; + opId += 2; // numbering of lirOps by two + } + } + assert (index << 1) == opId : "must match: " + (index << 1); + return opId - 2; } - private StackInterval getOrCreateInterval(VirtualStackSlot stackSlot) { - StackInterval interval = get(stackSlot); - if (interval == null) { - interval = new StackInterval(stackSlot, stackSlot.getLIRKind()); - put(stackSlot, interval); - } - return interval; + // ==================== + // step 2: build intervals + // ==================== + + private void buildIntervals() { + new FixPointIntervalBuilder(lir, stackSlotMap, maxOpId()).build(); } - 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; - } + // ==================== + // step 3: verify intervals + // ==================== private void verifyIntervals() { forEachInterval(interval -> { - assert interval.verify(this); + assert interval.verify(maxOpId()); }); } - 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()); - } + // ==================== + // step 4: allocate stack slots + // ==================== private void allocateStackSlots() { - // create interval lists - createUnhandled(); + // create unhandled lists + forEachInterval(unhandled::add); for (StackInterval current = activateNext(); current != null; current = activateNext()) { try (Indent indent = Debug.logAndIndent("allocate %s", current)) { @@ -395,7 +188,7 @@ StackSlotAllocator.virtualFramesize.add(frameMapBuilder.getFrameMap().spillSlotRangeSize(slotRange.getSlots())); StackSlotAllocator.allocatedSlots.increment(); } else { - assert virtualSlot instanceof SimpleVirtualStackSlot : "Unexpexted VirtualStackSlot type: " + virtualSlot; + assert virtualSlot instanceof SimpleVirtualStackSlot : "Unexpected VirtualStackSlot type: " + virtualSlot; StackSlot slot = findFreeSlot((SimpleVirtualStackSlot) virtualSlot); if (slot != null) { /* @@ -440,58 +233,108 @@ } } - private EnumMap<SlotSize, LinkedList<StackSlot>> freeSlots = new EnumMap<>(SlotSize.class); + private EnumMap<SlotSize, Deque<StackSlot>> freeSlots; + + /** + * @return The list of free stack slots for {@code size} or {@code null} if there is none. + */ + private Deque<StackSlot> getOrNullFreeSlots(SlotSize size) { + if (freeSlots == null) { + return null; + } + return freeSlots.get(size); + } + /** + * @return the list of free stack slots for {@code size}. If there is none a list is + * created. + */ + private Deque<StackSlot> getOrInitFreeSlots(SlotSize size) { + assert size != SlotSize.Illegal; + Deque<StackSlot> freeList; + if (freeSlots != null) { + freeList = freeSlots.get(size); + } else { + freeSlots = new EnumMap<>(SlotSize.class); + freeList = null; + } + if (freeList == null) { + freeList = new ArrayDeque<>(); + freeSlots.put(size, freeList); + } + assert freeList != null; + return freeList; + } + + /** + * Gets a free stack slot for {@code slot} or {@code null} if there is none. + */ private StackSlot findFreeSlot(SimpleVirtualStackSlot slot) { assert slot != null; SlotSize size = forKind(slot.getLIRKind()); - LinkedList<StackSlot> freeList = size == SlotSize.Illegal ? null : freeSlots.get(size); + if (size == SlotSize.Illegal) { + return null; + } + Deque<StackSlot> freeList = getOrNullFreeSlots(size); if (freeList == null) { return null; } - return freeList.pollFirst(); + return freeList.pollLast(); } + /** + * Adds a stack slot to the list of free slots. + */ 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); + getOrInitFreeSlots(size).addLast(slot); } + /** + * Gets the next unhandled interval and finishes handled intervals. + */ private StackInterval activateNext() { if (unhandled.isEmpty()) { return null; } - StackInterval next = unhandled.pollFirst(); + StackInterval next = unhandled.poll(); + // finish handled intervals for (int id = next.from(); activePeekId() < id;) { - finished(active.pollFirst()); + finished(active.poll()); } - Debug.log("activte %s", next); - insertSortedByTo(next); + Debug.log("active %s", next); + active.add(next); return next; } + /** + * Gets the lowest {@link StackInterval#to() end position} of all active intervals. If there + * is none {@link Integer#MAX_VALUE} is returned. + */ private int activePeekId() { - StackInterval first = active.peekFirst(); + StackInterval first = active.peek(); if (first == null) { return Integer.MAX_VALUE; } return first.to(); } + /** + * Finishes {@code interval} by adding its location to the list of free stack slots. + */ private void finished(StackInterval interval) { StackSlot location = interval.location(); Debug.log("finished %s (freeing %s)", interval, location); freeSlot(location); } + // ==================== + // step 5: assign stack slots + // ==================== + private void assignStackSlots() { for (AbstractBlock<?> block : sortedBlocks) { lir.getLIRforBlock(block).forEach(op -> { @@ -520,5 +363,33 @@ } return value; } + + // ==================== + // + // ==================== + + /** + * Gets the highest instruction id. + */ + private int maxOpId() { + return maxOpId; + } + + private StackInterval get(VirtualStackSlot stackSlot) { + return stackSlotMap[stackSlot.getId()]; + } + + private void forEachInterval(Consumer<StackInterval> proc) { + for (StackInterval interval : stackSlotMap) { + if (interval != null) { + proc.accept(interval); + } + } + } + + private void dumpIntervals(String label) { + Debug.dump(stackSlotMap, label); + } + } }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/StackInterval.java Tue Feb 03 04:17:06 2015 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/StackInterval.java Tue Feb 03 11:10:24 2015 +0100 @@ -24,9 +24,8 @@ import com.oracle.graal.api.code.*; import com.oracle.graal.api.meta.*; -import com.oracle.graal.debug.*; -public class StackInterval { +public final class StackInterval { private static final int INVALID_START = Integer.MAX_VALUE; private static final int INVALID_END = Integer.MIN_VALUE; @@ -34,25 +33,16 @@ 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()); + public boolean verify(int maxOpId) { + // maxOpId + 1 is the last position in the last block (i.e. the "write position") + assert 0 <= from && from <= to && to <= maxOpId + 1 : String.format("from %d, to %d, maxOpId %d", from, to, maxOpId); return true; } @@ -60,18 +50,6 @@ 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; @@ -100,10 +78,6 @@ this.location = location; } - public StackInterval locationHint() { - return null; - } - public int from() { return from; } @@ -112,10 +86,6 @@ return to; } - public StackUsePosList usePosList() { - return usePos; - } - public void fixFrom() { if (from == INVALID_START) { from = 0;
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/StackUsePosList.java Tue Feb 03 04:17:06 2015 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,101 +0,0 @@ -/* - * Copyright (c) 2014, 2015, 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 Feb 03 04:17:06 2015 +0100 +++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java Tue Feb 03 11:10:24 2015 +0100 @@ -582,22 +582,12 @@ out.printf("\"[%s|%c]\"", interval.getOperand(), interval.getOperand().getKind().getTypeChar()); } - StackInterval hint = interval.locationHint(); - out.printf("%s %s ", interval.getOperand(), hint != null ? hint.getOperand() : -1); + out.printf("%s -1 ", interval.getOperand()); out.printf("[%d, %d[", interval.from(), interval.to()); - // print use positions - int prev = -1; - StackUsePosList usePosList = interval.usePosList(); - for (int i = usePosList.size() - 1; i >= 0; --i) { - assert prev <= usePosList.usePos(i) : "use positions not sorted"; - out.printf("%d %s ", usePosList.usePos(i), usePosList.getType(i)); - prev = usePosList.usePos(i); - } - // print spill state - out.printf(" \"%s\"", "NOT_SUPPORTED"); + out.printf(" \"NOT_SUPPORTED\""); out.println(); }