1 /* 2 * Copyright (c) 2014, 2015, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 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.lir.LIRValueUtil.isStackSlotValue; 26 import static jdk.vm.ci.code.ValueUtil.asRegister; 27 import static jdk.vm.ci.code.ValueUtil.isRegister; 28 29 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase; 30 import org.graalvm.compiler.debug.Debug; 31 import org.graalvm.compiler.debug.Debug.Scope; 32 import org.graalvm.compiler.debug.Indent; 33 import org.graalvm.compiler.lir.alloc.lsra.Interval.RegisterBinding; 34 import org.graalvm.compiler.lir.alloc.lsra.Interval.RegisterBindingLists; 35 import org.graalvm.compiler.lir.alloc.lsra.Interval.RegisterPriority; 36 import org.graalvm.compiler.lir.alloc.lsra.Interval.State; 37 import org.graalvm.compiler.options.Option; 38 import org.graalvm.compiler.options.OptionType; 39 import org.graalvm.compiler.options.OptionValue; 40 41 import jdk.vm.ci.code.Register; 42 import jdk.vm.ci.meta.AllocatableValue; 43 44 public class OptimizingLinearScanWalker extends LinearScanWalker { 45 46 public static class Options { 47 // @formatter:off 48 @Option(help = "Enable LSRA optimization", type = OptionType.Debug) 49 public static final OptionValue<Boolean> LSRAOptimization = new OptionValue<>(false); 50 @Option(help = "LSRA optimization: Only split but do not reassign", type = OptionType.Debug) 51 public static final OptionValue<Boolean> LSRAOptSplitOnly = new OptionValue<>(false); 52 // @formatter:on 53 } 54 55 OptimizingLinearScanWalker(LinearScan allocator, Interval unhandledFixedFirst, Interval unhandledAnyFirst) { 56 super(allocator, unhandledFixedFirst, unhandledAnyFirst); 57 } 58 59 @SuppressWarnings("try") 60 @Override 61 protected void handleSpillSlot(Interval interval) { 62 assert interval.location() != null : "interval not assigned " + interval; 63 if (interval.canMaterialize()) { 64 assert !isStackSlotValue(interval.location()) : "interval can materialize but assigned to a stack slot " + interval; 65 return; 66 } 67 assert isStackSlotValue(interval.location()) : "interval not assigned to a stack slot " + interval; 68 try (Scope s1 = Debug.scope("LSRAOptimization")) { 69 Debug.log("adding stack to unhandled list %s", interval); 70 unhandledLists.addToListSortedByStartAndUsePositions(RegisterBinding.Stack, interval); 71 } 72 } 73 74 @SuppressWarnings("unused") 75 private static void printRegisterBindingList(RegisterBindingLists list, RegisterBinding binding) { 76 for (Interval interval = list.get(binding); interval != Interval.EndMarker; interval = interval.next) { 77 Debug.log("%s", interval); 78 } 79 } 80 81 @SuppressWarnings("try") 82 @Override 83 void walk() { 84 try (Scope s = Debug.scope("OptimizingLinearScanWalker")) { 85 for (AbstractBlockBase<?> block : allocator.sortedBlocks()) { 86 optimizeBlock(block); 87 } 88 } 89 super.walk(); 90 } 91 92 @SuppressWarnings("try") 93 private void optimizeBlock(AbstractBlockBase<?> block) { 94 if (block.getPredecessorCount() == 1) { 95 int nextBlock = allocator.getFirstLirInstructionId(block); 96 try (Scope s1 = Debug.scope("LSRAOptimization")) { 97 Debug.log("next block: %s (%d)", block, nextBlock); 98 } 99 try (Indent indent0 = Debug.indent()) { 100 walkTo(nextBlock); 101 102 try (Scope s1 = Debug.scope("LSRAOptimization")) { 103 boolean changed = true; 104 // we need to do this because the active lists might change 105 loop: while (changed) { 106 changed = false; 107 try (Indent indent1 = Debug.logAndIndent("Active intervals: (block %s [%d])", block, nextBlock)) { 108 for (Interval active = activeLists.get(RegisterBinding.Any); active != Interval.EndMarker; active = active.next) { 109 Debug.log("active (any): %s", active); 110 if (optimize(nextBlock, block, active, RegisterBinding.Any)) { 111 changed = true; 112 break loop; 113 } 114 } 115 for (Interval active = activeLists.get(RegisterBinding.Stack); active != Interval.EndMarker; active = active.next) { 116 Debug.log("active (stack): %s", active); 117 if (optimize(nextBlock, block, active, RegisterBinding.Stack)) { 118 changed = true; 119 break loop; 120 } 121 } 122 } 123 } 124 } 125 } 126 } 127 } 128 129 @SuppressWarnings("try") 130 private boolean optimize(int currentPos, AbstractBlockBase<?> currentBlock, Interval currentInterval, RegisterBinding binding) { 131 // BEGIN initialize and sanity checks 132 assert currentBlock != null : "block must not be null"; 133 assert currentInterval != null : "interval must not be null"; 134 135 assert currentBlock.getPredecessorCount() == 1 : "more than one predecessors -> optimization not possible"; 136 137 if (!currentInterval.isSplitChild()) { 138 // interval is not a split child -> no need for optimization 139 return false; 140 } 141 142 if (currentInterval.from() == currentPos) { 143 // the interval starts at the current position so no need for splitting 144 return false; 145 } 146 147 // get current location 148 AllocatableValue currentLocation = currentInterval.location(); 149 assert currentLocation != null : "active intervals must have a location assigned!"; 150 151 // get predecessor stuff 152 AbstractBlockBase<?> predecessorBlock = currentBlock.getPredecessors()[0]; 153 int predEndId = allocator.getLastLirInstructionId(predecessorBlock); 154 Interval predecessorInterval = currentInterval.getIntervalCoveringOpId(predEndId); 155 assert predecessorInterval != null : "variable not live at the end of the only predecessor! " + predecessorBlock + " -> " + currentBlock + " interval: " + currentInterval; 156 AllocatableValue predecessorLocation = predecessorInterval.location(); 157 assert predecessorLocation != null : "handled intervals must have a location assigned!"; 158 159 // END initialize and sanity checks 160 161 if (currentLocation.equals(predecessorLocation)) { 162 // locations are already equal -> nothing to optimize 163 return false; 164 } 165 166 if (!isStackSlotValue(predecessorLocation) && !isRegister(predecessorLocation)) { 167 assert predecessorInterval.canMaterialize(); 168 // value is materialized -> no need for optimization 169 return false; 170 } 171 172 assert isStackSlotValue(currentLocation) || isRegister(currentLocation) : "current location not a register or stack slot " + currentLocation; 173 174 try (Indent indent = Debug.logAndIndent("location differs: %s vs. %s", predecessorLocation, currentLocation)) { 175 // split current interval at current position 176 Debug.log("splitting at position %d", currentPos); 177 178 assert allocator.isBlockBegin(currentPos) && ((currentPos & 1) == 0) : "split pos must be even when on block boundary"; 179 180 Interval splitPart = currentInterval.split(currentPos, allocator); 181 activeLists.remove(binding, currentInterval); 182 183 assert splitPart.from() >= currentPosition : "cannot append new interval before current walk position"; 184 185 // the currentSplitChild is needed later when moves are inserted for reloading 186 assert splitPart.currentSplitChild() == currentInterval : "overwriting wrong currentSplitChild"; 187 splitPart.makeCurrentSplitChild(); 188 189 if (Debug.isLogEnabled()) { 190 Debug.log("left interval : %s", currentInterval.logString(allocator)); 191 Debug.log("right interval : %s", splitPart.logString(allocator)); 192 } 193 194 if (Options.LSRAOptSplitOnly.getValue()) { 195 // just add the split interval to the unhandled list 196 unhandledLists.addToListSortedByStartAndUsePositions(RegisterBinding.Any, splitPart); 197 } else { 198 if (isRegister(predecessorLocation)) { 199 splitRegisterInterval(splitPart, asRegister(predecessorLocation)); 200 } else { 201 assert isStackSlotValue(predecessorLocation); 202 Debug.log("assigning interval %s to %s", splitPart, predecessorLocation); 203 splitPart.assignLocation(predecessorLocation); 204 // activate interval 205 activeLists.addToListSortedByCurrentFromPositions(RegisterBinding.Stack, splitPart); 206 splitPart.state = State.Active; 207 208 splitStackInterval(splitPart); 209 } 210 } 211 } 212 return true; 213 } 214 215 @SuppressWarnings("try") 216 private void splitRegisterInterval(Interval interval, Register reg) { 217 // collect current usage of registers 218 initVarsForAlloc(interval); 219 initUseLists(false); 220 spillExcludeActiveFixed(); 221 // spillBlockUnhandledFixed(cur); 222 assert unhandledLists.get(RegisterBinding.Fixed) == Interval.EndMarker : "must not have unhandled fixed intervals because all fixed intervals have a use at position 0"; 223 spillBlockInactiveFixed(interval); 224 spillCollectActiveAny(RegisterPriority.LiveAtLoopEnd); 225 spillCollectInactiveAny(interval); 226 227 if (Debug.isLogEnabled()) { 228 try (Indent indent2 = Debug.logAndIndent("state of registers:")) { 229 for (Register register : availableRegs) { 230 int i = register.number; 231 try (Indent indent3 = Debug.logAndIndent("reg %d: usePos: %d, blockPos: %d, intervals: ", i, usePos[i], blockPos[i])) { 232 for (int j = 0; j < spillIntervals[i].size(); j++) { 233 Debug.log("%d ", spillIntervals[i].get(j).operandNumber); 234 } 235 } 236 } 237 } 238 } 239 240 // the register must be free at least until this position 241 boolean needSplit = blockPos[reg.number] <= interval.to(); 242 243 int splitPos = blockPos[reg.number]; 244 245 assert splitPos > 0 : "invalid splitPos"; 246 assert needSplit || splitPos > interval.from() : "splitting interval at from"; 247 248 Debug.log("assigning interval %s to %s", interval, reg); 249 interval.assignLocation(reg.asValue(interval.kind())); 250 if (needSplit) { 251 // register not available for full interval : so split it 252 splitWhenPartialRegisterAvailable(interval, splitPos); 253 } 254 255 // perform splitting and spilling for all affected intervals 256 splitAndSpillIntersectingIntervals(reg); 257 258 // activate interval 259 activeLists.addToListSortedByCurrentFromPositions(RegisterBinding.Any, interval); 260 interval.state = State.Active; 261 262 } 263 }