12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23 package org.graalvm.compiler.lir.alloc.lsra; 24 25 import static org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph.commonDominator; 26 import static org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph.dominates; 27 import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue; 28 29 import java.util.Iterator; 30 31 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase; 32 import org.graalvm.compiler.debug.Debug; 33 import org.graalvm.compiler.debug.DebugCounter; 34 import org.graalvm.compiler.debug.Indent; 35 import org.graalvm.compiler.lir.LIRInsertionBuffer; 36 import org.graalvm.compiler.lir.LIRInstruction; 37 import org.graalvm.compiler.lir.LIRInstruction.OperandMode; 38 import org.graalvm.compiler.lir.alloc.lsra.Interval.SpillState; 39 import org.graalvm.compiler.lir.gen.LIRGenerationResult; 40 import org.graalvm.compiler.lir.phases.AllocationPhase.AllocationContext; 41 42 import jdk.vm.ci.code.TargetDescription; 43 import jdk.vm.ci.meta.AllocatableValue; 44 45 public final class LinearScanOptimizeSpillPositionPhase extends LinearScanAllocationPhase { 46 47 private static final DebugCounter betterSpillPos = Debug.counter("BetterSpillPosition"); 48 private static final DebugCounter betterSpillPosWithLowerProbability = Debug.counter("BetterSpillPositionWithLowerProbability"); 49 50 private final LinearScan allocator; 51 52 LinearScanOptimizeSpillPositionPhase(LinearScan allocator) { 53 this.allocator = allocator; 54 } 55 56 @Override 57 protected void run(TargetDescription target, LIRGenerationResult lirGenRes, AllocationContext context) { 58 optimizeSpillPosition(lirGenRes); 59 allocator.printIntervals("After optimize spill position"); 60 } 61 62 @SuppressWarnings("try") 63 private void optimizeSpillPosition(LIRGenerationResult res) { 64 try (Indent indent0 = Debug.logAndIndent("OptimizeSpillPositions")) { 65 LIRInsertionBuffer[] insertionBuffers = new LIRInsertionBuffer[allocator.getLIR().linearScanOrder().length]; 66 for (Interval interval : allocator.intervals()) { 67 optimizeInterval(insertionBuffers, interval, res); 68 } 69 for (LIRInsertionBuffer insertionBuffer : insertionBuffers) { 70 if (insertionBuffer != null) { 71 assert insertionBuffer.initialized() : "Insertion buffer is nonnull but not initialized!"; 72 insertionBuffer.finish(); 73 } 74 } 75 } 76 } 77 78 @SuppressWarnings("try") 79 private void optimizeInterval(LIRInsertionBuffer[] insertionBuffers, Interval interval, LIRGenerationResult res) { 80 if (interval == null || !interval.isSplitParent() || interval.spillState() != SpillState.SpillInDominator) { 81 return; 82 } 83 AbstractBlockBase<?> defBlock = allocator.blockForId(interval.spillDefinitionPos()); 84 AbstractBlockBase<?> spillBlock = null; 85 Interval firstSpillChild = null; 86 try (Indent indent = Debug.logAndIndent("interval %s (%s)", interval, defBlock)) { 87 for (Interval splitChild : interval.getSplitChildren()) { 88 if (isStackSlotValue(splitChild.location())) { 89 if (firstSpillChild == null || splitChild.from() < firstSpillChild.from()) { 90 firstSpillChild = splitChild; 91 } else { 92 assert firstSpillChild.from() < splitChild.from(); 93 } 94 // iterate all blocks where the interval has use positions 95 for (AbstractBlockBase<?> splitBlock : blocksForInterval(splitChild)) { 96 if (dominates(defBlock, splitBlock)) { 97 Debug.log("Split interval %s, block %s", splitChild, splitBlock); 98 if (spillBlock == null) { 99 spillBlock = splitBlock; 100 } else { 101 spillBlock = commonDominator(spillBlock, splitBlock); 102 assert spillBlock != null; 103 } 104 } 105 } 106 } 107 } 108 if (spillBlock == null) { 109 Debug.log("not spill interval found"); 110 // no spill interval 111 interval.setSpillState(SpillState.StoreAtDefinition); 112 return; 113 } 114 Debug.log(Debug.VERBOSE_LEVEL, "Spill block candidate (initial): %s", spillBlock); 115 // move out of loops 116 if (defBlock.getLoopDepth() < spillBlock.getLoopDepth()) { 117 spillBlock = moveSpillOutOfLoop(defBlock, spillBlock); 118 } 119 Debug.log(Debug.VERBOSE_LEVEL, "Spill block candidate (after loop optimizaton): %s", spillBlock); 120 121 /* 122 * The spill block is the begin of the first split child (aka the value is on the 123 * stack). 124 * 125 * The problem is that if spill block has more than one predecessor, the values at the 126 * end of the predecessors might differ. Therefore, we would need a spill move in all 127 * predecessors. To avoid this we spill in the dominator. 128 */ 129 assert firstSpillChild != null; 130 if (!defBlock.equals(spillBlock) && spillBlock.equals(allocator.blockForId(firstSpillChild.from()))) { 131 AbstractBlockBase<?> dom = spillBlock.getDominator(); 132 if (Debug.isLogEnabled()) { 133 Debug.log("Spill block (%s) is the beginning of a spill child -> use dominator (%s)", spillBlock, dom); 134 } 135 spillBlock = dom; 136 } 137 if (defBlock.equals(spillBlock)) { 138 Debug.log(Debug.VERBOSE_LEVEL, "Definition is the best choice: %s", defBlock); 139 // definition is the best choice 140 interval.setSpillState(SpillState.StoreAtDefinition); 141 return; 142 } 143 assert dominates(defBlock, spillBlock); 144 betterSpillPos.increment(); 145 if (Debug.isLogEnabled()) { 146 Debug.log("Better spill position found (Block %s)", spillBlock); 147 } 148 149 if (defBlock.probability() <= spillBlock.probability()) { 150 Debug.log(Debug.VERBOSE_LEVEL, "Definition has lower probability %s (%f) is lower than spill block %s (%f)", defBlock, defBlock.probability(), spillBlock, 151 spillBlock.probability()); 152 // better spill block has the same probability -> do nothing 153 interval.setSpillState(SpillState.StoreAtDefinition); 154 return; 155 } 156 157 LIRInsertionBuffer insertionBuffer = insertionBuffers[spillBlock.getId()]; 158 if (insertionBuffer == null) { 159 insertionBuffer = new LIRInsertionBuffer(); 160 insertionBuffers[spillBlock.getId()] = insertionBuffer; 161 insertionBuffer.init(allocator.getLIR().getLIRforBlock(spillBlock)); 162 } 163 int spillOpId = allocator.getFirstLirInstructionId(spillBlock); 164 // insert spill move 165 AllocatableValue fromLocation = interval.getSplitChildAtOpId(spillOpId, OperandMode.DEF, allocator).location(); 166 AllocatableValue toLocation = LinearScan.canonicalSpillOpr(interval); 167 LIRInstruction move = allocator.getSpillMoveFactory().createMove(toLocation, fromLocation); 168 move.setComment(res, "LSRAOptimizeSpillPos: optimize spill pos"); 169 Debug.log(Debug.VERBOSE_LEVEL, "Insert spill move %s", move); 170 move.setId(LinearScan.DOMINATOR_SPILL_MOVE_ID); 171 /* 172 * We can use the insertion buffer directly because we always insert at position 1. 173 */ 174 insertionBuffer.append(1, move); 175 176 betterSpillPosWithLowerProbability.increment(); 177 interval.setSpillDefinitionPos(spillOpId); 178 } 179 } 180 181 /** 182 * Iterate over all {@link AbstractBlockBase blocks} of an interval. 183 */ 184 private class IntervalBlockIterator implements Iterator<AbstractBlockBase<?>> { 185 186 Range range; 187 AbstractBlockBase<?> block; 188 189 IntervalBlockIterator(Interval interval) { 190 range = interval.first(); 191 block = allocator.blockForId(range.from); 192 } 193 194 @Override 195 public AbstractBlockBase<?> next() { 196 AbstractBlockBase<?> currentBlock = block; | 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23 package org.graalvm.compiler.lir.alloc.lsra; 24 25 import static org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph.commonDominator; 26 import static org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph.dominates; 27 import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue; 28 29 import java.util.Iterator; 30 31 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase; 32 import org.graalvm.compiler.debug.CounterKey; 33 import org.graalvm.compiler.debug.DebugContext; 34 import org.graalvm.compiler.debug.Indent; 35 import org.graalvm.compiler.lir.LIRInsertionBuffer; 36 import org.graalvm.compiler.lir.LIRInstruction; 37 import org.graalvm.compiler.lir.LIRInstruction.OperandMode; 38 import org.graalvm.compiler.lir.alloc.lsra.Interval.SpillState; 39 import org.graalvm.compiler.lir.gen.LIRGenerationResult; 40 import org.graalvm.compiler.lir.phases.AllocationPhase.AllocationContext; 41 42 import jdk.vm.ci.code.TargetDescription; 43 import jdk.vm.ci.meta.AllocatableValue; 44 45 public final class LinearScanOptimizeSpillPositionPhase extends LinearScanAllocationPhase { 46 47 private static final CounterKey betterSpillPos = DebugContext.counter("BetterSpillPosition"); 48 private static final CounterKey betterSpillPosWithLowerProbability = DebugContext.counter("BetterSpillPositionWithLowerProbability"); 49 50 private final LinearScan allocator; 51 private DebugContext debug; 52 53 LinearScanOptimizeSpillPositionPhase(LinearScan allocator) { 54 this.allocator = allocator; 55 this.debug = allocator.getDebug(); 56 } 57 58 @Override 59 protected void run(TargetDescription target, LIRGenerationResult lirGenRes, AllocationContext context) { 60 optimizeSpillPosition(lirGenRes); 61 allocator.printIntervals("After optimize spill position"); 62 } 63 64 @SuppressWarnings("try") 65 private void optimizeSpillPosition(LIRGenerationResult res) { 66 try (Indent indent0 = debug.logAndIndent("OptimizeSpillPositions")) { 67 LIRInsertionBuffer[] insertionBuffers = new LIRInsertionBuffer[allocator.getLIR().linearScanOrder().length]; 68 for (Interval interval : allocator.intervals()) { 69 optimizeInterval(insertionBuffers, interval, res); 70 } 71 for (LIRInsertionBuffer insertionBuffer : insertionBuffers) { 72 if (insertionBuffer != null) { 73 assert insertionBuffer.initialized() : "Insertion buffer is nonnull but not initialized!"; 74 insertionBuffer.finish(); 75 } 76 } 77 } 78 } 79 80 @SuppressWarnings("try") 81 private void optimizeInterval(LIRInsertionBuffer[] insertionBuffers, Interval interval, LIRGenerationResult res) { 82 if (interval == null || !interval.isSplitParent() || interval.spillState() != SpillState.SpillInDominator) { 83 return; 84 } 85 AbstractBlockBase<?> defBlock = allocator.blockForId(interval.spillDefinitionPos()); 86 AbstractBlockBase<?> spillBlock = null; 87 Interval firstSpillChild = null; 88 try (Indent indent = debug.logAndIndent("interval %s (%s)", interval, defBlock)) { 89 for (Interval splitChild : interval.getSplitChildren()) { 90 if (isStackSlotValue(splitChild.location())) { 91 if (firstSpillChild == null || splitChild.from() < firstSpillChild.from()) { 92 firstSpillChild = splitChild; 93 } else { 94 assert firstSpillChild.from() < splitChild.from(); 95 } 96 // iterate all blocks where the interval has use positions 97 for (AbstractBlockBase<?> splitBlock : blocksForInterval(splitChild)) { 98 if (dominates(defBlock, splitBlock)) { 99 debug.log("Split interval %s, block %s", splitChild, splitBlock); 100 if (spillBlock == null) { 101 spillBlock = splitBlock; 102 } else { 103 spillBlock = commonDominator(spillBlock, splitBlock); 104 assert spillBlock != null; 105 } 106 } 107 } 108 } 109 } 110 if (spillBlock == null) { 111 debug.log("not spill interval found"); 112 // no spill interval 113 interval.setSpillState(SpillState.StoreAtDefinition); 114 return; 115 } 116 debug.log(DebugContext.VERBOSE_LEVEL, "Spill block candidate (initial): %s", spillBlock); 117 // move out of loops 118 if (defBlock.getLoopDepth() < spillBlock.getLoopDepth()) { 119 spillBlock = moveSpillOutOfLoop(defBlock, spillBlock); 120 } 121 debug.log(DebugContext.VERBOSE_LEVEL, "Spill block candidate (after loop optimizaton): %s", spillBlock); 122 123 /* 124 * The spill block is the begin of the first split child (aka the value is on the 125 * stack). 126 * 127 * The problem is that if spill block has more than one predecessor, the values at the 128 * end of the predecessors might differ. Therefore, we would need a spill move in all 129 * predecessors. To avoid this we spill in the dominator. 130 */ 131 assert firstSpillChild != null; 132 if (!defBlock.equals(spillBlock) && spillBlock.equals(allocator.blockForId(firstSpillChild.from()))) { 133 AbstractBlockBase<?> dom = spillBlock.getDominator(); 134 if (debug.isLogEnabled()) { 135 debug.log("Spill block (%s) is the beginning of a spill child -> use dominator (%s)", spillBlock, dom); 136 } 137 spillBlock = dom; 138 } 139 if (defBlock.equals(spillBlock)) { 140 debug.log(DebugContext.VERBOSE_LEVEL, "Definition is the best choice: %s", defBlock); 141 // definition is the best choice 142 interval.setSpillState(SpillState.StoreAtDefinition); 143 return; 144 } 145 assert dominates(defBlock, spillBlock); 146 betterSpillPos.increment(debug); 147 if (debug.isLogEnabled()) { 148 debug.log("Better spill position found (Block %s)", spillBlock); 149 } 150 151 if (defBlock.probability() <= spillBlock.probability()) { 152 debug.log(DebugContext.VERBOSE_LEVEL, "Definition has lower probability %s (%f) is lower than spill block %s (%f)", defBlock, defBlock.probability(), spillBlock, 153 spillBlock.probability()); 154 // better spill block has the same probability -> do nothing 155 interval.setSpillState(SpillState.StoreAtDefinition); 156 return; 157 } 158 159 LIRInsertionBuffer insertionBuffer = insertionBuffers[spillBlock.getId()]; 160 if (insertionBuffer == null) { 161 insertionBuffer = new LIRInsertionBuffer(); 162 insertionBuffers[spillBlock.getId()] = insertionBuffer; 163 insertionBuffer.init(allocator.getLIR().getLIRforBlock(spillBlock)); 164 } 165 int spillOpId = allocator.getFirstLirInstructionId(spillBlock); 166 // insert spill move 167 AllocatableValue fromLocation = interval.getSplitChildAtOpId(spillOpId, OperandMode.DEF, allocator).location(); 168 AllocatableValue toLocation = LinearScan.canonicalSpillOpr(interval); 169 LIRInstruction move = allocator.getSpillMoveFactory().createMove(toLocation, fromLocation); 170 move.setComment(res, "LSRAOptimizeSpillPos: optimize spill pos"); 171 debug.log(DebugContext.VERBOSE_LEVEL, "Insert spill move %s", move); 172 move.setId(LinearScan.DOMINATOR_SPILL_MOVE_ID); 173 /* 174 * We can use the insertion buffer directly because we always insert at position 1. 175 */ 176 insertionBuffer.append(1, move); 177 178 betterSpillPosWithLowerProbability.increment(debug); 179 interval.setSpillDefinitionPos(spillOpId); 180 } 181 } 182 183 /** 184 * Iterate over all {@link AbstractBlockBase blocks} of an interval. 185 */ 186 private class IntervalBlockIterator implements Iterator<AbstractBlockBase<?>> { 187 188 Range range; 189 AbstractBlockBase<?> block; 190 191 IntervalBlockIterator(Interval interval) { 192 range = interval.first(); 193 block = allocator.blockForId(range.from); 194 } 195 196 @Override 197 public AbstractBlockBase<?> next() { 198 AbstractBlockBase<?> currentBlock = block; |