Mercurial > hg > truffle

annotate graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanOptimizeSpillPositionPhase.java @ 21511:47c5e0903d06

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add RegisterAllocationConfig to AllocationContext.
author Josef Eisl <josef.eisl@jku.at>
date Thu, 28 May 2015 10:04:46 +0200
parents 1c56b7be2731
children ce2113326bc8
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
21322
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
1 /*
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
2 * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved.
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
4 *
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
5 * This code is free software; you can redistribute it and/or modify it
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
6 * under the terms of the GNU General Public License version 2 only, as
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
7 * published by the Free Software Foundation.
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
8 *
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
9 * This code is distributed in the hope that it will be useful, but WITHOUT
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
12 * version 2 for more details (a copy is included in the LICENSE file that
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
13 * accompanied this code).
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
14 *
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
15 * You should have received a copy of the GNU General Public License version
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
16 * 2 along with this work; if not, write to the Free Software Foundation,
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
18 *
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
20 * or visit www.oracle.com if you need additional information or have any
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
21 * questions.
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
22 */
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
23 package com.oracle.graal.lir.alloc.lsra;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
24
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
25 import static com.oracle.graal.api.code.ValueUtil.*;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
26 import static com.oracle.graal.compiler.common.cfg.AbstractControlFlowGraph.*;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
27
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
28 import java.util.*;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
29
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
30 import com.oracle.graal.api.code.*;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
31 import com.oracle.graal.api.meta.*;
21511
47c5e0903d06 Add RegisterAllocationConfig to AllocationContext.
Josef Eisl <josef.eisl@jku.at>
parents: 21339
diff changeset
32 import com.oracle.graal.compiler.common.alloc.*;
21322
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
33 import com.oracle.graal.compiler.common.cfg.*;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
34 import com.oracle.graal.debug.*;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
35 import com.oracle.graal.lir.*;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
36 import com.oracle.graal.lir.LIRInstruction.OperandMode;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
37 import com.oracle.graal.lir.alloc.lsra.Interval.SpillState;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
38 import com.oracle.graal.lir.gen.*;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
39 import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
40 import com.oracle.graal.lir.phases.*;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
41
21339
1c56b7be2731 LinearScan: renamed sub phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21327
diff changeset
42 final class LinearScanOptimizeSpillPositionPhase extends AllocationPhase {
21322
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
43
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
44 private static final DebugMetric betterSpillPos = Debug.metric("BetterSpillPosition");
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
45 private static final DebugMetric betterSpillPosWithLowerProbability = Debug.metric("BetterSpillPositionWithLowerProbability");
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
46
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
47 private final LinearScan allocator;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
48
21339
1c56b7be2731 LinearScan: renamed sub phases.
Josef Eisl <josef.eisl@jku.at>
parents: 21327
diff changeset
49 LinearScanOptimizeSpillPositionPhase(LinearScan allocator) {
21322
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
50 this.allocator = allocator;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
51 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
52
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
53 @Override
21511
47c5e0903d06 Add RegisterAllocationConfig to AllocationContext.
Josef Eisl <josef.eisl@jku.at>
parents: 21339
diff changeset
54 protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory,
47c5e0903d06 Add RegisterAllocationConfig to AllocationContext.
Josef Eisl <josef.eisl@jku.at>
parents: 21339
diff changeset
55 RegisterAllocationConfig registerAllocationConfig) {
21322
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
56 optimizeSpillPosition();
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
57 allocator.printIntervals("After optimize spill position");
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
58 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
59
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
60 private void optimizeSpillPosition() {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
61 LIRInsertionBuffer[] insertionBuffers = new LIRInsertionBuffer[allocator.ir.linearScanOrder().size()];
21327
b8dcf353b822 LinearScan: encapsulate intervals.
Josef Eisl <josef.eisl@jku.at>
parents: 21322
diff changeset
62 for (Interval interval : allocator.intervals()) {
21322
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
63 if (interval != null && interval.isSplitParent() && interval.spillState() == SpillState.SpillInDominator) {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
64 AbstractBlockBase<?> defBlock = allocator.blockForId(interval.spillDefinitionPos());
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
65 AbstractBlockBase<?> spillBlock = null;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
66 Interval firstSpillChild = null;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
67 try (Indent indent = Debug.logAndIndent("interval %s (%s)", interval, defBlock)) {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
68 for (Interval splitChild : interval.getSplitChildren()) {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
69 if (isStackSlotValue(splitChild.location())) {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
70 if (firstSpillChild == null || splitChild.from() < firstSpillChild.from()) {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
71 firstSpillChild = splitChild;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
72 } else {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
73 assert firstSpillChild.from() < splitChild.from();
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
74 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
75 // iterate all blocks where the interval has use positions
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
76 for (AbstractBlockBase<?> splitBlock : blocksForInterval(splitChild)) {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
77 if (dominates(defBlock, splitBlock)) {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
78 if (Debug.isLogEnabled()) {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
79 Debug.log("Split interval %s, block %s", splitChild, splitBlock);
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
80 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
81 if (spillBlock == null) {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
82 spillBlock = splitBlock;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
83 } else {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
84 spillBlock = commonDominator(spillBlock, splitBlock);
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
85 assert spillBlock != null;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
86 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
87 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
88 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
89 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
90 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
91 if (spillBlock == null) {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
92 // no spill interval
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
93 interval.setSpillState(SpillState.StoreAtDefinition);
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
94 } else {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
95 // move out of loops
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
96 if (defBlock.getLoopDepth() < spillBlock.getLoopDepth()) {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
97 spillBlock = moveSpillOutOfLoop(defBlock, spillBlock);
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
98 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
99
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
100 /*
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
101 * If the spill block is the begin of the first split child (aka the value
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
102 * is on the stack) spill in the dominator.
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
103 */
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
104 assert firstSpillChild != null;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
105 if (!defBlock.equals(spillBlock) && spillBlock.equals(allocator.blockForId(firstSpillChild.from()))) {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
106 AbstractBlockBase<?> dom = spillBlock.getDominator();
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
107 if (Debug.isLogEnabled()) {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
108 Debug.log("Spill block (%s) is the beginning of a spill child -> use dominator (%s)", spillBlock, dom);
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
109 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
110 spillBlock = dom;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
111 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
112
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
113 if (!defBlock.equals(spillBlock)) {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
114 assert dominates(defBlock, spillBlock);
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
115 betterSpillPos.increment();
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
116 if (Debug.isLogEnabled()) {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
117 Debug.log("Better spill position found (Block %s)", spillBlock);
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
118 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
119
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
120 if (defBlock.probability() <= spillBlock.probability()) {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
121 // better spill block has the same probability -> do nothing
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
122 interval.setSpillState(SpillState.StoreAtDefinition);
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
123 } else {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
124 LIRInsertionBuffer insertionBuffer = insertionBuffers[spillBlock.getId()];
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
125 if (insertionBuffer == null) {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
126 insertionBuffer = new LIRInsertionBuffer();
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
127 insertionBuffers[spillBlock.getId()] = insertionBuffer;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
128 insertionBuffer.init(allocator.ir.getLIRforBlock(spillBlock));
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
129 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
130 int spillOpId = allocator.getFirstLirInstructionId(spillBlock);
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
131 // insert spill move
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
132 AllocatableValue fromLocation = interval.getSplitChildAtOpId(spillOpId, OperandMode.DEF, allocator).location();
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
133 AllocatableValue toLocation = LinearScan.canonicalSpillOpr(interval);
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
134 LIRInstruction move = allocator.getSpillMoveFactory().createMove(toLocation, fromLocation);
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
135 move.setId(LinearScan.DOMINATOR_SPILL_MOVE_ID);
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
136 /*
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
137 * We can use the insertion buffer directly because we always insert
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
138 * at position 1.
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
139 */
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
140 insertionBuffer.append(1, move);
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
141
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
142 betterSpillPosWithLowerProbability.increment();
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
143 interval.setSpillDefinitionPos(spillOpId);
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
144 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
145 } else {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
146 // definition is the best choice
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
147 interval.setSpillState(SpillState.StoreAtDefinition);
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
148 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
149 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
150 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
151 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
152 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
153 for (LIRInsertionBuffer insertionBuffer : insertionBuffers) {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
154 if (insertionBuffer != null) {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
155 assert insertionBuffer.initialized() : "Insertion buffer is nonnull but not initialized!";
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
156 insertionBuffer.finish();
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
157 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
158 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
159 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
160
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
161 /**
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
162 * Iterate over all {@link AbstractBlockBase blocks} of an interval.
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
163 */
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
164 private class IntervalBlockIterator implements Iterator<AbstractBlockBase<?>> {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
165
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
166 Range range;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
167 AbstractBlockBase<?> block;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
168
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
169 public IntervalBlockIterator(Interval interval) {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
170 range = interval.first();
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
171 block = allocator.blockForId(range.from);
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
172 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
173
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
174 public AbstractBlockBase<?> next() {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
175 AbstractBlockBase<?> currentBlock = block;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
176 int nextBlockIndex = block.getLinearScanNumber() + 1;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
177 if (nextBlockIndex < allocator.sortedBlocks.size()) {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
178 block = allocator.sortedBlocks.get(nextBlockIndex);
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
179 if (range.to <= allocator.getFirstLirInstructionId(block)) {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
180 range = range.next;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
181 if (range == Range.EndMarker) {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
182 block = null;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
183 } else {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
184 block = allocator.blockForId(range.from);
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
185 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
186 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
187 } else {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
188 block = null;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
189 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
190 return currentBlock;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
191 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
192
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
193 public boolean hasNext() {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
194 return block != null;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
195 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
196 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
197
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
198 private Iterable<AbstractBlockBase<?>> blocksForInterval(Interval interval) {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
199 return new Iterable<AbstractBlockBase<?>>() {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
200 public Iterator<AbstractBlockBase<?>> iterator() {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
201 return new IntervalBlockIterator(interval);
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
202 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
203 };
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
204 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
205
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
206 private static AbstractBlockBase<?> moveSpillOutOfLoop(AbstractBlockBase<?> defBlock, AbstractBlockBase<?> spillBlock) {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
207 int defLoopDepth = defBlock.getLoopDepth();
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
208 for (AbstractBlockBase<?> block = spillBlock.getDominator(); !defBlock.equals(block); block = block.getDominator()) {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
209 assert block != null : "spill block not dominated by definition block?";
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
210 if (block.getLoopDepth() <= defLoopDepth) {
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
211 assert block.getLoopDepth() == defLoopDepth : "Cannot spill an interval outside of the loop where it is defined!";
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
212 return block;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
213 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
214 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
215 return defBlock;
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
216 }
73942ac6e650 LinearScan: outsource OptimizeSpillPosition.
Josef Eisl <josef.eisl@jku.at>
parents:
diff changeset
217 }