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 @ 19077:3dd21f7125e9

LSStackSlotAllocator: fix typos.

author	Josef Eisl <josef.eisl@jku.at>
date	Fri, 30 Jan 2015 15:30:33 +0100
parents	76dd59e530b2
children	613a2b7f88c3

rev	line source
19028 f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	1 /*
19037 cc2b817de0b5 StackSlotAllocation: fix style/formating issues. Josef Eisl <josef.eisl@jku.at> parents: 19035 diff changeset	2 * Copyright (c) 2014, 2015, Oracle and/or its affiliates. All rights reserved.
19028 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
19076 76dd59e530b2 Rename EnableLSStackSlotAllocation command line flag to LSStackSlotAllocation. Josef Eisl <josef.eisl@jku.at> parents: 19037 diff changeset	56 @Option(help = "Use linear scan stack slot allocation.", type = OptionType.Debug)
76dd59e530b2 Rename EnableLSStackSlotAllocation command line flag to LSStackSlotAllocation. Josef Eisl <josef.eisl@jku.at> parents: 19037 diff changeset	57 public static final OptionValue<Boolean> LSStackSlotAllocation = new OptionValue<>(true);
19028 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 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	97 buildIntervalsSlow();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	98 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	99 if (Debug.isEnabled()) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	100 verifyIntervals();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	101 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	102 if (Debug.isDumpEnabled()) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	103 dumpIntervals("Before stack slot allocation");
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	104 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	105 // allocate stack slots
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	106 allocateStackSlots();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	107 if (Debug.isDumpEnabled()) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	108 dumpIntervals("After stack slot allocation");
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	109 }
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 // assign stack slots
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	112 assignStackSlots();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	113 Debug.dump(lir, "After StackSlot assignment");
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	114 StackSlotAllocator.allocatedFramesize.add(frameMapBuilder.getFrameMap().currentFrameSize() - currentFrameSize);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	115 }
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 private void buildIntervalsSlow() {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	118 new SlowIntervalBuilder().build();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	119 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	120
19034 94ca6ce786ee StackSlotAllocation: improve javadoc. Josef Eisl <josef.eisl@jku.at> parents: 19032 diff changeset	121 /**
94ca6ce786ee StackSlotAllocation: improve javadoc. Josef Eisl <josef.eisl@jku.at> parents: 19032 diff changeset	122 * 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	123 */
94ca6ce786ee StackSlotAllocation: improve javadoc. Josef Eisl <josef.eisl@jku.at> parents: 19032 diff changeset	124 private final class SlowIntervalBuilder {
19028 f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	125 final BlockMap<BitSet> liveInMap;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	126 final BlockMap<BitSet> liveOutMap;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	127
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	128 private SlowIntervalBuilder() {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	129 liveInMap = new BlockMap<>(lir.getControlFlowGraph());
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	130 liveOutMap = new BlockMap<>(lir.getControlFlowGraph());
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	131 }
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 private void build() {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	134 Deque<AbstractBlock<?>> worklist = new ArrayDeque<>();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	135 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	136 worklist.add(lir.getControlFlowGraph().getBlocks().get(i));
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	137 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	138 for (AbstractBlock<?> block : lir.getControlFlowGraph().getBlocks()) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	139 liveInMap.put(block, new BitSet(frameMapBuilder.getNumberOfStackSlots()));
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	140 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	141 while (!worklist.isEmpty()) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	142 AbstractBlock<?> block = worklist.poll();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	143 processBlock(block, worklist);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	144 }
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 * Merge outSet with in-set of successors.
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	149 */
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	150 private boolean updateOutBlock(AbstractBlock<?> block) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	151 BitSet union = new BitSet(frameMapBuilder.getNumberOfStackSlots());
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	152 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	153 BitSet outSet = liveOutMap.get(block);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	154 // check if changed
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	155 if (outSet == null \|\| !union.equals(outSet)) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	156 liveOutMap.put(block, union);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	157 return true;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	158 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	159 return false;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	160 }
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 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	163 if (updateOutBlock(block)) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	164 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	165 List<LIRInstruction> instructions = lir.getLIRforBlock(block);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	166 // get out set and mark intervals
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	167 BitSet outSet = liveOutMap.get(block);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	168 markOutInterval(outSet, getBlockEnd(instructions));
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	169 printLiveSet("liveOut", outSet);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	170
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	171 // process instructions
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	172 BlockClosure closure = new BlockClosure((BitSet) outSet.clone());
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	173 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	174 LIRInstruction inst = instructions.get(i);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	175 closure.processInstructionBottomUp(inst);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	176 }
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 // add predecessors to work list
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	179 worklist.addAll(block.getPredecessors());
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	180 // set in set and mark intervals
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	181 BitSet inSet = closure.getCurrentSet();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	182 liveInMap.put(block, inSet);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	183 markInInterval(inSet, getBlockBegin(instructions));
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	184 printLiveSet("liveIn", inSet);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	185 }
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 private void printLiveSet(String label, BitSet liveSet) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	190 if (Debug.isLogEnabled()) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	191 try (Indent indent = Debug.logAndIndent(label)) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	192 Debug.log("%s", liveSetToString(liveSet));
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	193 }
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 private String liveSetToString(BitSet liveSet) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	198 StringBuilder sb = new StringBuilder();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	199 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	200 StackInterval interval = getIntervalFromStackId(i);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	201 sb.append(interval.getOperand()).append(" ");
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	202 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	203 return sb.toString();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	204 }
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 protected void markOutInterval(BitSet outSet, int blockEndOpId) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	207 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	208 StackInterval interval = getIntervalFromStackId(i);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	209 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	210 interval.addTo(blockEndOpId);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	211 }
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 protected void markInInterval(BitSet inSet, int blockFirstOpId) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	215 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	216 StackInterval interval = getIntervalFromStackId(i);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	217 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	218 interval.addFrom(blockFirstOpId);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	219 }
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 private final class BlockClosure {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	223 private final BitSet currentSet;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	224
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	225 private BlockClosure(BitSet set) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	226 currentSet = set;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	227 }
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 private BitSet getCurrentSet() {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	230 return currentSet;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	231 }
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 * 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	235 * 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	236 */
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	237 private void processInstructionBottomUp(LIRInstruction op) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	238 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	239 // kills
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	240 op.visitEachTemp(this::defConsumer);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	241 op.visitEachOutput(this::defConsumer);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	242
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	243 // 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	244 op.visitEachAlive(this::useConsumer);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	245 op.visitEachState(this::useConsumer);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	246 // mark locations
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	247 // gen
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	248 op.visitEachInput(this::useConsumer);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	249 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	250 }
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 * @see InstructionValueConsumer
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 * @param inst
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	256 * @param operand
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	257 * @param mode
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	258 * @param flags
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	259 */
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	260 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	261 if (isVirtualStackSlot(operand)) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	262 VirtualStackSlot vslot = asVirtualStackSlot(operand);
19032 b646e37bc989 StackSlotAllocation: handle uninitialized stack slots. Josef Eisl <josef.eisl@jku.at> parents: 19031 diff changeset	263 addUse(vslot, inst, flags);
19028 f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	264 Debug.log("set operand: %s", operand);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	265 currentSet.set(vslot.getId());
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	266 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	267 }
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 * @see InstructionValueConsumer
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 * @param inst
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	274 * @param operand
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	275 * @param mode
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	276 * @param flags
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	277 */
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	278 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	279 if (isVirtualStackSlot(operand)) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	280 VirtualStackSlot vslot = asVirtualStackSlot(operand);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	281 addDef(vslot, inst);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	282 Debug.log("clear operand: %s", operand);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	283 currentSet.clear(vslot.getId());
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	284 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	285
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
19032 b646e37bc989 StackSlotAllocation: handle uninitialized stack slots. Josef Eisl <josef.eisl@jku.at> parents: 19031 diff changeset	288 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	289 StackInterval interval = getOrCreateInterval(stackSlot);
19032 b646e37bc989 StackSlotAllocation: handle uninitialized stack slots. Josef Eisl <josef.eisl@jku.at> parents: 19031 diff changeset	290 if (flags.contains(OperandFlag.UNINITIALIZED)) {
b646e37bc989 StackSlotAllocation: handle uninitialized stack slots. Josef Eisl <josef.eisl@jku.at> parents: 19031 diff changeset	291 // 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	292 // the time.
19035 9a3bde73e05a StackSlotAllocation: add metric for uninitialized stack slots. Josef Eisl <josef.eisl@jku.at> parents: 19034 diff changeset	293 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	294 uninitializedSlots.increment();
9a3bde73e05a StackSlotAllocation: add metric for uninitialized stack slots. Josef Eisl <josef.eisl@jku.at> parents: 19034 diff changeset	295 }
19032 b646e37bc989 StackSlotAllocation: handle uninitialized stack slots. Josef Eisl <josef.eisl@jku.at> parents: 19031 diff changeset	296 interval.addDef(0);
b646e37bc989 StackSlotAllocation: handle uninitialized stack slots. Josef Eisl <josef.eisl@jku.at> parents: 19031 diff changeset	297 interval.addUse(maxOpId());
b646e37bc989 StackSlotAllocation: handle uninitialized stack slots. Josef Eisl <josef.eisl@jku.at> parents: 19031 diff changeset	298 } else {
b646e37bc989 StackSlotAllocation: handle uninitialized stack slots. Josef Eisl <josef.eisl@jku.at> parents: 19031 diff changeset	299 interval.addUse(inst.id());
b646e37bc989 StackSlotAllocation: handle uninitialized stack slots. Josef Eisl <josef.eisl@jku.at> parents: 19031 diff changeset	300 }
19028 f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	301 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	302
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	303 private void addDef(VirtualStackSlot stackSlot, LIRInstruction inst) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	304 StackInterval interval = getOrCreateInterval(stackSlot);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	305 interval.addDef(inst.id());
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	306 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	307
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 private static int getBlockBegin(List<LIRInstruction> instructions) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	312 return instructions.get(0).id();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	313 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	314
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	315 private static int getBlockEnd(List<LIRInstruction> instructions) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	316 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	317 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	318
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	319 private StackInterval getOrCreateInterval(VirtualStackSlot stackSlot) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	320 StackInterval interval = get(stackSlot);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	321 if (interval == null) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	322 interval = new StackInterval(stackSlot, stackSlot.getLIRKind());
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	323 put(stackSlot, interval);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	324 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	325 return 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
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	328 private StackInterval get(VirtualStackSlot stackSlot) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	329 return stackSlotMap[stackSlot.getId()];
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	330 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	331
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	332 private StackInterval getIntervalFromStackId(int id) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	333 return stackSlotMap[id];
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	334 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	335
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	336 private void put(VirtualStackSlot stackSlot, StackInterval interval) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	337 stackSlotMap[stackSlot.getId()] = interval;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	338 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	339
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	340 private void verifyIntervals() {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	341 forEachInterval(interval -> {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	342 assert interval.verify(this);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	343 });
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	344 }
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 private void forEachInterval(Consumer<StackInterval> proc) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	347 for (StackInterval interval : stackSlotMap) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	348 if (interval != null) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	349 proc.accept(interval);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	350 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	351 }
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 public void dumpIntervals(String label) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	355 Debug.dump(stackSlotMap, label);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	356 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	357
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	358 private void createUnhandled() {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	359 unhandled = new LinkedList<>();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	360 active = new LinkedList<>();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	361 forEachInterval(this::insertSortedByFrom);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	362 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	363
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	364 private void insertSortedByFrom(StackInterval interval) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	365 unhandled.add(interval);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	366 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	367 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	368
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	369 private void insertSortedByTo(StackInterval interval) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	370 active.add(interval);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	371 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	372 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	373
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	374 private void allocateStackSlots() {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	375 // create interval lists
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	376 createUnhandled();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	377
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	378 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	379 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	380 allocateSlot(current);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	381 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	382 }
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 private void allocateSlot(StackInterval current) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	387 VirtualStackSlot virtualSlot = current.getOperand();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	388 final StackSlot location;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	389 if (virtualSlot instanceof VirtualStackSlotRange) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	390 // No reuse of ranges (yet).
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	391 VirtualStackSlotRange slotRange = (VirtualStackSlotRange) virtualSlot;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	392 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	393 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	394 StackSlotAllocator.allocatedSlots.increment();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	395 } else {
19077 3dd21f7125e9 LSStackSlotAllocator: fix typos. Josef Eisl <josef.eisl@jku.at> parents: 19076 diff changeset	396 assert virtualSlot instanceof SimpleVirtualStackSlot : "Unexpected VirtualStackSlot type: " + virtualSlot;
19028 f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	397 StackSlot slot = findFreeSlot((SimpleVirtualStackSlot) virtualSlot);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	398 if (slot != null) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	399 /*
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	400 * 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	401 * might not match.
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	402 */
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	403 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	404 StackSlotAllocator.reusedSlots.increment();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	405 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	406 } else {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	407 // Allocate new stack slot.
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	408 location = frameMapBuilder.getFrameMap().allocateSpillSlot(virtualSlot.getLIRKind());
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	409 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	410 StackSlotAllocator.allocatedSlots.increment();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	411 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	412 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	413 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	414 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	415 current.setLocation(location);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	416 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	417
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	418 private static enum SlotSize {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	419 Size1,
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	420 Size2,
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	421 Size4,
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	422 Size8,
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	423 Illegal;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	424 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	425
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	426 private SlotSize forKind(LIRKind kind) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	427 switch (frameMapBuilder.getFrameMap().spillSlotSize(kind)) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	428 case 1:
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	429 return SlotSize.Size1;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	430 case 2:
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	431 return SlotSize.Size2;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	432 case 4:
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	433 return SlotSize.Size4;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	434 case 8:
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	435 return SlotSize.Size8;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	436 default:
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	437 return SlotSize.Illegal;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	438 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	439 }
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 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	442
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	443 private StackSlot findFreeSlot(SimpleVirtualStackSlot slot) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	444 assert slot != null;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	445 SlotSize size = forKind(slot.getLIRKind());
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	446 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	447 if (freeList == null) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	448 return null;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	449 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	450 return freeList.pollFirst();
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
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	453 private void freeSlot(StackSlot slot) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	454 SlotSize size = forKind(slot.getLIRKind());
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	455 if (size == SlotSize.Illegal) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	456 return;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	457 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	458 LinkedList<StackSlot> freeList = freeSlots.get(size);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	459 if (freeList == null) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	460 freeList = new LinkedList<>();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	461 freeSlots.put(size, freeList);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	462 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	463 freeList.add(slot);
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
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	466 private StackInterval activateNext() {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	467 if (unhandled.isEmpty()) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	468 return null;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	469 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	470 StackInterval next = unhandled.pollFirst();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	471 for (int id = next.from(); activePeekId() < id;) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	472 finished(active.pollFirst());
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	473 }
19077 3dd21f7125e9 LSStackSlotAllocator: fix typos. Josef Eisl <josef.eisl@jku.at> parents: 19076 diff changeset	474 Debug.log("active %s", next);
19028 f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	475 insertSortedByTo(next);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	476 return next;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	477 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	478
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	479 private int activePeekId() {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	480 StackInterval first = active.peekFirst();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	481 if (first == null) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	482 return Integer.MAX_VALUE;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	483 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	484 return first.to();
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
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	487 private void finished(StackInterval interval) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	488 StackSlot location = interval.location();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	489 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	490 freeSlot(location);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	491 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	492
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	493 private void assignStackSlots() {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	494 for (AbstractBlock<?> block : sortedBlocks) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	495 lir.getLIRforBlock(block).forEach(op -> {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	496 op.forEachInput(this::assignSlot);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	497 op.forEachAlive(this::assignSlot);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	498 op.forEachState(this::assignSlot);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	499
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	500 op.forEachTemp(this::assignSlot);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	501 op.forEachOutput(this::assignSlot);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	502 });
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	503 }
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 * @see ValueProcedure
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	508 * @param value
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	509 * @param mode
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	510 * @param flags
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	511 */
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	512 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	513 if (isVirtualStackSlot(value)) {
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	514 VirtualStackSlot slot = asVirtualStackSlot(value);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	515 StackInterval interval = get(slot);
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	516 assert interval != null;
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	517 return interval.location();
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	518 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	519 return value;
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 }
f59fc4850df5 StackSlotAllocator: add linear scan stack slot allocator. Josef Eisl <josef.eisl@jku.at> parents: diff changeset	522 }

Mercurial > hg > truffle

annotate graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/LSStackSlotAllocator.java @ 19077:3dd21f7125e9