truffle: graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/LSStackSlotAllocator.java annotate

annotate graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/LSStackSlotAllocator.java @ 19035:9a3bde73e05a

StackSlotAllocation: add metric for uninitialized stack slots.

author	Josef Eisl <josef.eisl@jku.at>
date	Thu, 29 Jan 2015 10:56:07 +0100
parents	94ca6ce786ee
children	cc2b817de0b5

rev	line source
19028 f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	1 /*
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	2 * Copyright (c) 2014, 2014, Oracle and/or its affiliates. All rights reserved.
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	4 *
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	5 * This code is free software; you can redistribute it and/or modify it
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	6 * under the terms of the GNU General Public License version 2 only, as
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	7 * published by the Free Software Foundation.
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	8 *
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	9 * This code is distributed in the hope that it will be useful, but WITHOUT
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	12 * version 2 for more details (a copy is included in the LICENSE file that
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	13 * accompanied this code).
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	14 *
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	15 * You should have received a copy of the GNU General Public License version
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	16 * 2 along with this work; if not, write to the Free Software Foundation,
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	18 *
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	20 * or visit www.oracle.com if you need additional information or have any
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	21 * questions.
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	22 */
19031 beb7c10b7747 Move StackSlotAllocators into a package. Josef Eisl <josef.eisl@jku.at> parents: 19028 diff changeset	23 package com.oracle.graal.lir.stackslotalloc;
19028 f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	24
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	25 import static com.oracle.graal.api.code.ValueUtil.*;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	26
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	27 import java.util.*;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	28 import java.util.function.*;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	29
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	30 import com.oracle.graal.api.code.*;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	31 import com.oracle.graal.api.meta.*;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	32 import com.oracle.graal.compiler.common.cfg.*;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	33 import com.oracle.graal.debug.*;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	34 import com.oracle.graal.debug.Debug.Scope;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	35 import com.oracle.graal.lir.*;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	36 import com.oracle.graal.lir.LIRInstruction.OperandFlag;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	37 import com.oracle.graal.lir.LIRInstruction.OperandMode;
19031 beb7c10b7747 Move StackSlotAllocators into a package. Josef Eisl <josef.eisl@jku.at> parents: 19028 diff changeset	38 import com.oracle.graal.lir.framemap.*;
19028 f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	39 import com.oracle.graal.lir.gen.*;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	40 import com.oracle.graal.options.*;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	41
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	42 /**
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	43 * Linear Scan {@link StackSlotAllocator}.
19034 94ca6ce786ee StackSlotAllocation: improve javadoc. Josef Eisl <josef.eisl@jku.at> parents: 19032 diff changeset	44 * <p>
94ca6ce786ee StackSlotAllocation: improve javadoc. Josef Eisl <josef.eisl@jku.at> parents: 19032 diff changeset	45 * <b>Remark:</b> The analysis works under the assumption that a stack slot is no longer live after
94ca6ce786ee StackSlotAllocation: improve javadoc. Josef Eisl <josef.eisl@jku.at> parents: 19032 diff changeset	46 * its last usage. If an {@link LIRInstruction instruction} transfers the raw address of the stack
94ca6ce786ee StackSlotAllocation: improve javadoc. Josef Eisl <josef.eisl@jku.at> parents: 19032 diff changeset	47 * slot to another location, e.g. a registers, and this location is referenced later on, the
94ca6ce786ee StackSlotAllocation: improve javadoc. Josef Eisl <josef.eisl@jku.at> parents: 19032 diff changeset	48 * {@link com.oracle.graal.lir.LIRInstruction.Use usage} of the stack slot must be marked with the
94ca6ce786ee StackSlotAllocation: improve javadoc. Josef Eisl <josef.eisl@jku.at> parents: 19032 diff changeset	49 * {@link OperandFlag#UNINITIALIZED}. Otherwise the stack slot might be reused and its content
94ca6ce786ee StackSlotAllocation: improve javadoc. Josef Eisl <josef.eisl@jku.at> parents: 19032 diff changeset	50 * destroyed.
19028 f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	51 */
19034 94ca6ce786ee StackSlotAllocation: improve javadoc. Josef Eisl <josef.eisl@jku.at> parents: 19032 diff changeset	52 public final class LSStackSlotAllocator implements StackSlotAllocator {
19028 f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	53
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	54 public static class Options {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	55 // @formatter:off
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	56 @Option(help = "Enable linear scan stack slot allocation.")
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	57 public static final OptionValue<Boolean> EnableLSStackSlotAllocation = new OptionValue<>(true);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	58 // @formatter:on
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	59 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	60
19035 9a3bde73e05a StackSlotAllocation: add metric for uninitialized stack slots. Josef Eisl <josef.eisl@jku.at> parents: 19034 diff changeset	61 /**
9a3bde73e05a StackSlotAllocation: add metric for uninitialized stack slots. Josef Eisl <josef.eisl@jku.at> parents: 19034 diff changeset	62 * The number of allocated stack slots.
9a3bde73e05a StackSlotAllocation: add metric for uninitialized stack slots. Josef Eisl <josef.eisl@jku.at> parents: 19034 diff changeset	63 */
9a3bde73e05a StackSlotAllocation: add metric for uninitialized stack slots. Josef Eisl <josef.eisl@jku.at> parents: 19034 diff changeset	64 static final DebugMetric uninitializedSlots = Debug.metric("StackSlotAllocator[uninitializedSlots]");
9a3bde73e05a StackSlotAllocation: add metric for uninitialized stack slots. Josef Eisl <josef.eisl@jku.at> parents: 19034 diff changeset	65
19028 f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	66 public void allocateStackSlots(FrameMapBuilderTool builder, LIRGenerationResult res) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	67 new Allocator(res.getLIR(), builder).allocate();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	68 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	69
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	70 static final class Allocator extends InstructionNumberer {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	71 private final LIR lir;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	72 private final FrameMapBuilderTool frameMapBuilder;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	73 private final StackInterval[] stackSlotMap;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	74 private LinkedList<StackInterval> unhandled;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	75 private LinkedList<StackInterval> active;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	76
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	77 private List<? extends AbstractBlock<?>> sortedBlocks;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	78
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	79 private Allocator(LIR lir, FrameMapBuilderTool frameMapBuilder) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	80 this.lir = lir;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	81 this.frameMapBuilder = frameMapBuilder;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	82 this.stackSlotMap = new StackInterval[frameMapBuilder.getNumberOfStackSlots()];
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	83 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	84
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	85 private void allocate() {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	86 // create block ordering
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	87 List<? extends AbstractBlock<?>> blocks = lir.getControlFlowGraph().getBlocks();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	88 assert blocks.size() > 0;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	89
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	90 sortedBlocks = lir.getControlFlowGraph().getBlocks();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	91 numberInstructions(lir, sortedBlocks);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	92 Debug.dump(lir, "After StackSlot numbering");
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	93
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	94 long currentFrameSize = Debug.isMeterEnabled() ? frameMapBuilder.getFrameMap().currentFrameSize() : 0;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	95 // build intervals
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	96 // buildIntervals();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	97 try (Scope s = Debug.scope("StackSlotAllocationBuildIntervals"); Indent indent = Debug.logAndIndent("BuildIntervals")) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	98 buildIntervalsSlow();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	99 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	100 if (Debug.isEnabled()) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	101 verifyIntervals();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	102 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	103 if (Debug.isDumpEnabled()) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	104 dumpIntervals("Before stack slot allocation");
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	105 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	106 // allocate stack slots
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	107 allocateStackSlots();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	108 if (Debug.isDumpEnabled()) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	109 dumpIntervals("After stack slot allocation");
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	110 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	111
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	112 // assign stack slots
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	113 assignStackSlots();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	114 Debug.dump(lir, "After StackSlot assignment");
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	115 StackSlotAllocator.allocatedFramesize.add(frameMapBuilder.getFrameMap().currentFrameSize() - currentFrameSize);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	116 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	117
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	118 private void buildIntervalsSlow() {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	119 new SlowIntervalBuilder().build();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	120 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	121
19034 94ca6ce786ee StackSlotAllocation: improve javadoc. Josef Eisl <josef.eisl@jku.at> parents: 19032 diff changeset	122 /**
94ca6ce786ee StackSlotAllocation: improve javadoc. Josef Eisl <josef.eisl@jku.at> parents: 19032 diff changeset	123 * Calculates the stack intervals using a worklist-based backwards data-flow analysis.
94ca6ce786ee StackSlotAllocation: improve javadoc. Josef Eisl <josef.eisl@jku.at> parents: 19032 diff changeset	124 */
94ca6ce786ee StackSlotAllocation: improve javadoc. Josef Eisl <josef.eisl@jku.at> parents: 19032 diff changeset	125 private final class SlowIntervalBuilder {
19028 f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	126 final BlockMap<BitSet> liveInMap;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	127 final BlockMap<BitSet> liveOutMap;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	128
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	129 private SlowIntervalBuilder() {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	130 liveInMap = new BlockMap<>(lir.getControlFlowGraph());
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	131 liveOutMap = new BlockMap<>(lir.getControlFlowGraph());
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	132 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	133
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	134 private void build() {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	135 Deque<AbstractBlock<?>> worklist = new ArrayDeque<>();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	136 for (int i = lir.getControlFlowGraph().getBlocks().size() - 1; i >= 0; i--) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	137 worklist.add(lir.getControlFlowGraph().getBlocks().get(i));
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	138 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	139 for (AbstractBlock<?> block : lir.getControlFlowGraph().getBlocks()) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	140 liveInMap.put(block, new BitSet(frameMapBuilder.getNumberOfStackSlots()));
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	141 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	142 while (!worklist.isEmpty()) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	143 AbstractBlock<?> block = worklist.poll();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	144 processBlock(block, worklist);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	145 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	146 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	147
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	148 /**
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	149 * Merge outSet with in-set of successors.
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	150 */
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	151 private boolean updateOutBlock(AbstractBlock<?> block) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	152 BitSet union = new BitSet(frameMapBuilder.getNumberOfStackSlots());
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	153 block.getSuccessors().forEach(succ -> union.or(liveInMap.get(succ)));
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	154 BitSet outSet = liveOutMap.get(block);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	155 // check if changed
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	156 if (outSet == null \|\| !union.equals(outSet)) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	157 liveOutMap.put(block, union);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	158 return true;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	159 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	160 return false;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	161 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	162
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	163 private void processBlock(AbstractBlock<?> block, Deque<AbstractBlock<?>> worklist) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	164 if (updateOutBlock(block)) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	165 try (Indent indent = Debug.logAndIndent("handle block %s", block)) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	166 List<LIRInstruction> instructions = lir.getLIRforBlock(block);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	167 // get out set and mark intervals
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	168 BitSet outSet = liveOutMap.get(block);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	169 markOutInterval(outSet, getBlockEnd(instructions));
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	170 printLiveSet("liveOut", outSet);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	171
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	172 // process instructions
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	173 BlockClosure closure = new BlockClosure((BitSet) outSet.clone());
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	174 for (int i = instructions.size() - 1; i >= 0; i--) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	175 LIRInstruction inst = instructions.get(i);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	176 closure.processInstructionBottomUp(inst);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	177 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	178
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	179 // add predecessors to work list
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	180 worklist.addAll(block.getPredecessors());
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	181 // set in set and mark intervals
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	182 BitSet inSet = closure.getCurrentSet();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	183 liveInMap.put(block, inSet);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	184 markInInterval(inSet, getBlockBegin(instructions));
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	185 printLiveSet("liveIn", inSet);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	186 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	187 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	188 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	189
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	190 private void printLiveSet(String label, BitSet liveSet) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	191 if (Debug.isLogEnabled()) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	192 try (Indent indent = Debug.logAndIndent(label)) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	193 Debug.log("%s", liveSetToString(liveSet));
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	194 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	195 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	196 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	197
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	198 private String liveSetToString(BitSet liveSet) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	199 StringBuilder sb = new StringBuilder();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	200 for (int i = liveSet.nextSetBit(0); i >= 0; i = liveSet.nextSetBit(i + 1)) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	201 StackInterval interval = getIntervalFromStackId(i);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	202 sb.append(interval.getOperand()).append(" ");
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	203 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	204 return sb.toString();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	205 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	206
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	207 protected void markOutInterval(BitSet outSet, int blockEndOpId) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	208 for (int i = outSet.nextSetBit(0); i >= 0; i = outSet.nextSetBit(i + 1)) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	209 StackInterval interval = getIntervalFromStackId(i);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	210 Debug.log("mark live operand: %s", interval.getOperand());
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	211 interval.addTo(blockEndOpId);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	212 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	213 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	214
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	215 protected void markInInterval(BitSet inSet, int blockFirstOpId) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	216 for (int i = inSet.nextSetBit(0); i >= 0; i = inSet.nextSetBit(i + 1)) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	217 StackInterval interval = getIntervalFromStackId(i);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	218 Debug.log("mark live operand: %s", interval.getOperand());
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	219 interval.addFrom(blockFirstOpId);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	220 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	221 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	222
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	223 private final class BlockClosure {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	224 private final BitSet currentSet;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	225
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	226 private BlockClosure(BitSet set) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	227 currentSet = set;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	228 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	229
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	230 private BitSet getCurrentSet() {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	231 return currentSet;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	232 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	233
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	234 /**
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	235 * Process all values of an instruction bottom-up, i.e. definitions before usages.
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	236 * Values that start or end at the current operation are not included.
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	237 */
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	238 private void processInstructionBottomUp(LIRInstruction op) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	239 try (Indent indent = Debug.logAndIndent("handle op %d, %s", op.id(), op)) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	240 // kills
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	241 op.visitEachTemp(this::defConsumer);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	242 op.visitEachOutput(this::defConsumer);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	243 // forEachDestroyedCallerSavedRegister(op, this::defConsumer);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	244
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	245 // gen - values that are considered alive for this state
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	246 op.visitEachAlive(this::useConsumer);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	247 op.visitEachState(this::useConsumer);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	248 // mark locations
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	249 // gen
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	250 op.visitEachInput(this::useConsumer);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	251 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	252 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	253
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	254 /**
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	255 * @see InstructionValueConsumer
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	256 *
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	257 * @param inst
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	258 * @param operand
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	259 * @param mode
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	260 * @param flags
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	261 */
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	262 private void useConsumer(LIRInstruction inst, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	263 if (isVirtualStackSlot(operand)) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	264 VirtualStackSlot vslot = asVirtualStackSlot(operand);
19032 b646e37bc989 StackSlotAllocation: handle uninitialized stack slots. Josef Eisl <josef.eisl@jku.at> parents: 19031 diff changeset	265 addUse(vslot, inst, flags);
19028 f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	266 Debug.log("set operand: %s", operand);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	267 currentSet.set(vslot.getId());
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	268 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	269 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	270
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	271 /**
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	272 *
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	273 * @see InstructionValueConsumer
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	274 *
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	275 * @param inst
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	276 * @param operand
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	277 * @param mode
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	278 * @param flags
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	279 */
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	280 private void defConsumer(LIRInstruction inst, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	281 if (isVirtualStackSlot(operand)) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	282 VirtualStackSlot vslot = asVirtualStackSlot(operand);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	283 addDef(vslot, inst);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	284 Debug.log("clear operand: %s", operand);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	285 currentSet.clear(vslot.getId());
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	286 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	287
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	288 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	289
19032 b646e37bc989 StackSlotAllocation: handle uninitialized stack slots. Josef Eisl <josef.eisl@jku.at> parents: 19031 diff changeset	290 private void addUse(VirtualStackSlot stackSlot, LIRInstruction inst, EnumSet<OperandFlag> flags) {
19028 f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	291 StackInterval interval = getOrCreateInterval(stackSlot);
19032 b646e37bc989 StackSlotAllocation: handle uninitialized stack slots. Josef Eisl <josef.eisl@jku.at> parents: 19031 diff changeset	292 if (flags.contains(OperandFlag.UNINITIALIZED)) {
b646e37bc989 StackSlotAllocation: handle uninitialized stack slots. Josef Eisl <josef.eisl@jku.at> parents: 19031 diff changeset	293 // Stack slot is marked uninitialized so we have to assume it is live all
b646e37bc989 StackSlotAllocation: handle uninitialized stack slots. Josef Eisl <josef.eisl@jku.at> parents: 19031 diff changeset	294 // the time.
19035 9a3bde73e05a StackSlotAllocation: add metric for uninitialized stack slots. Josef Eisl <josef.eisl@jku.at> parents: 19034 diff changeset	295 if (Debug.isMeterEnabled() && !(interval.from() == 0 && interval.to() == maxOpId())) {
9a3bde73e05a StackSlotAllocation: add metric for uninitialized stack slots. Josef Eisl <josef.eisl@jku.at> parents: 19034 diff changeset	296 uninitializedSlots.increment();
9a3bde73e05a StackSlotAllocation: add metric for uninitialized stack slots. Josef Eisl <josef.eisl@jku.at> parents: 19034 diff changeset	297 }
19032 b646e37bc989 StackSlotAllocation: handle uninitialized stack slots. Josef Eisl <josef.eisl@jku.at> parents: 19031 diff changeset	298 interval.addDef(0);
b646e37bc989 StackSlotAllocation: handle uninitialized stack slots. Josef Eisl <josef.eisl@jku.at> parents: 19031 diff changeset	299 interval.addUse(maxOpId());
b646e37bc989 StackSlotAllocation: handle uninitialized stack slots. Josef Eisl <josef.eisl@jku.at> parents: 19031 diff changeset	300 } else {
b646e37bc989 StackSlotAllocation: handle uninitialized stack slots. Josef Eisl <josef.eisl@jku.at> parents: 19031 diff changeset	301 interval.addUse(inst.id());
b646e37bc989 StackSlotAllocation: handle uninitialized stack slots. Josef Eisl <josef.eisl@jku.at> parents: 19031 diff changeset	302 }
19028 f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	303 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	304
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	305 private void addDef(VirtualStackSlot stackSlot, LIRInstruction inst) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	306 StackInterval interval = getOrCreateInterval(stackSlot);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	307 interval.addDef(inst.id());
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	308 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	309
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	310 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	311 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	312
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	313 private static int getBlockBegin(List<LIRInstruction> instructions) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	314 return instructions.get(0).id();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	315 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	316
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	317 private static int getBlockEnd(List<LIRInstruction> instructions) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	318 return instructions.get(instructions.size() - 1).id() + 1;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	319 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	320
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	321 private StackInterval getOrCreateInterval(VirtualStackSlot stackSlot) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	322 StackInterval interval = get(stackSlot);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	323 if (interval == null) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	324 interval = new StackInterval(stackSlot, stackSlot.getLIRKind());
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	325 put(stackSlot, interval);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	326 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	327 return interval;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	328 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	329
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	330 private StackInterval get(VirtualStackSlot stackSlot) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	331 return stackSlotMap[stackSlot.getId()];
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	332 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	333
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	334 private StackInterval getIntervalFromStackId(int id) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	335 return stackSlotMap[id];
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	336 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	337
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	338 private void put(VirtualStackSlot stackSlot, StackInterval interval) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	339 stackSlotMap[stackSlot.getId()] = interval;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	340 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	341
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	342 private void verifyIntervals() {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	343 forEachInterval(interval -> {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	344 assert interval.verify(this);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	345 });
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	346 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	347
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	348 private void forEachInterval(Consumer<StackInterval> proc) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	349 for (StackInterval interval : stackSlotMap) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	350 if (interval != null) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	351 proc.accept(interval);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	352 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	353 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	354 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	355
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	356 public void dumpIntervals(String label) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	357 Debug.dump(stackSlotMap, label);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	358 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	359
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	360 private void createUnhandled() {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	361 unhandled = new LinkedList<>();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	362 active = new LinkedList<>();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	363 forEachInterval(this::insertSortedByFrom);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	364 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	365
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	366 private void insertSortedByFrom(StackInterval interval) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	367 unhandled.add(interval);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	368 unhandled.sort((a, b) -> a.from() - b.from());
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	369 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	370
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	371 private void insertSortedByTo(StackInterval interval) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	372 active.add(interval);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	373 active.sort((a, b) -> a.to() - b.to());
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	374 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	375
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	376 private void allocateStackSlots() {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	377 // create interval lists
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	378 createUnhandled();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	379
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	380 for (StackInterval current = activateNext(); current != null; current = activateNext()) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	381 try (Indent indent = Debug.logAndIndent("allocate %s", current)) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	382 allocateSlot(current);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	383 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	384 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	385
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	386 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	387
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	388 private void allocateSlot(StackInterval current) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	389 VirtualStackSlot virtualSlot = current.getOperand();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	390 final StackSlot location;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	391 if (virtualSlot instanceof VirtualStackSlotRange) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	392 // No reuse of ranges (yet).
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	393 VirtualStackSlotRange slotRange = (VirtualStackSlotRange) virtualSlot;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	394 location = frameMapBuilder.getFrameMap().allocateStackSlots(slotRange.getSlots(), slotRange.getObjects());
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	395 StackSlotAllocator.virtualFramesize.add(frameMapBuilder.getFrameMap().spillSlotRangeSize(slotRange.getSlots()));
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	396 StackSlotAllocator.allocatedSlots.increment();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	397 } else {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	398 assert virtualSlot instanceof SimpleVirtualStackSlot : "Unexpexted VirtualStackSlot type: " + virtualSlot;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	399 StackSlot slot = findFreeSlot((SimpleVirtualStackSlot) virtualSlot);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	400 if (slot != null) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	401 /*
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	402 * Free stack slot available. Note that we create a new one because the kind
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	403 * might not match.
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	404 */
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	405 location = StackSlot.get(current.kind(), slot.getRawOffset(), slot.getRawAddFrameSize());
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	406 StackSlotAllocator.reusedSlots.increment();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	407 Debug.log(1, "Reuse stack slot %s (reallocated from %s) for virtual stack slot %s", location, slot, virtualSlot);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	408 } else {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	409 // Allocate new stack slot.
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	410 location = frameMapBuilder.getFrameMap().allocateSpillSlot(virtualSlot.getLIRKind());
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	411 StackSlotAllocator.virtualFramesize.add(frameMapBuilder.getFrameMap().spillSlotSize(virtualSlot.getLIRKind()));
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	412 StackSlotAllocator.allocatedSlots.increment();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	413 Debug.log(1, "New stack slot %s for virtual stack slot %s", location, virtualSlot);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	414 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	415 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	416 Debug.log("Allocate location %s for interval %s", location, current);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	417 current.setLocation(location);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	418 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	419
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	420 private static enum SlotSize {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	421 Size1,
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	422 Size2,
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	423 Size4,
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	424 Size8,
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	425 Illegal;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	426 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	427
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	428 private SlotSize forKind(LIRKind kind) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	429 switch (frameMapBuilder.getFrameMap().spillSlotSize(kind)) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	430 case 1:
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	431 return SlotSize.Size1;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	432 case 2:
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	433 return SlotSize.Size2;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	434 case 4:
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	435 return SlotSize.Size4;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	436 case 8:
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	437 return SlotSize.Size8;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	438 default:
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	439 return SlotSize.Illegal;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	440 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	441 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	442
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	443 private EnumMap<SlotSize, LinkedList<StackSlot>> freeSlots = new EnumMap<>(SlotSize.class);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	444
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	445 private StackSlot findFreeSlot(SimpleVirtualStackSlot slot) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	446 assert slot != null;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	447 SlotSize size = forKind(slot.getLIRKind());
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	448 LinkedList<StackSlot> freeList = size == SlotSize.Illegal ? null : freeSlots.get(size);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	449 if (freeList == null) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	450 return null;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	451 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	452 return freeList.pollFirst();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	453 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	454
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	455 private void freeSlot(StackSlot slot) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	456 SlotSize size = forKind(slot.getLIRKind());
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	457 if (size == SlotSize.Illegal) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	458 return;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	459 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	460 LinkedList<StackSlot> freeList = freeSlots.get(size);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	461 if (freeList == null) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	462 freeList = new LinkedList<>();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	463 freeSlots.put(size, freeList);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	464 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	465 freeList.add(slot);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	466 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	467
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	468 private StackInterval activateNext() {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	469 if (unhandled.isEmpty()) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	470 return null;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	471 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	472 StackInterval next = unhandled.pollFirst();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	473 for (int id = next.from(); activePeekId() < id;) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	474 finished(active.pollFirst());
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	475 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	476 Debug.log("activte %s", next);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	477 insertSortedByTo(next);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	478 return next;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	479 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	480
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	481 private int activePeekId() {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	482 StackInterval first = active.peekFirst();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	483 if (first == null) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	484 return Integer.MAX_VALUE;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	485 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	486 return first.to();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	487 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	488
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	489 private void finished(StackInterval interval) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	490 StackSlot location = interval.location();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	491 Debug.log("finished %s (freeing %s)", interval, location);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	492 freeSlot(location);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	493 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	494
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	495 private void assignStackSlots() {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	496 for (AbstractBlock<?> block : sortedBlocks) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	497 lir.getLIRforBlock(block).forEach(op -> {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	498 op.forEachInput(this::assignSlot);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	499 op.forEachAlive(this::assignSlot);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	500 op.forEachState(this::assignSlot);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	501
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	502 op.forEachTemp(this::assignSlot);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	503 op.forEachOutput(this::assignSlot);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	504 });
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	505 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	506 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	507
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	508 /**
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	509 * @see ValueProcedure
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	510 * @param value
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	511 * @param mode
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	512 * @param flags
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	513 */
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	514 private Value assignSlot(Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	515 if (isVirtualStackSlot(value)) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	516 VirtualStackSlot slot = asVirtualStackSlot(value);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	517 StackInterval interval = get(slot);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	518 assert interval != null;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	519 return interval.location();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	520 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	521 return value;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	522 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	523 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	524 }

Mercurial > hg > truffle

annotate graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/LSStackSlotAllocator.java @ 19035:9a3bde73e05a