1 /*
   2  * Copyright (c) 2009, 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.trace;
  24 
  25 import static jdk.vm.ci.code.ValueUtil.asAllocatableValue;
  26 import static jdk.vm.ci.code.ValueUtil.asRegister;
  27 import static jdk.vm.ci.code.ValueUtil.asStackSlot;
  28 import static jdk.vm.ci.code.ValueUtil.isIllegal;
  29 import static jdk.vm.ci.code.ValueUtil.isRegister;
  30 import static jdk.vm.ci.code.ValueUtil.isStackSlot;
  31 import static org.graalvm.compiler.lir.LIRValueUtil.asVirtualStackSlot;
  32 import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;
  33 import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot;
  34 import static org.graalvm.compiler.lir.alloc.trace.TraceUtil.asShadowedRegisterValue;
  35 import static org.graalvm.compiler.lir.alloc.trace.TraceUtil.isShadowedRegisterValue;
  36 
  37 import java.util.ArrayList;
  38 import java.util.Arrays;
  39 import java.util.HashSet;
  40 
  41 import org.graalvm.compiler.core.common.LIRKind;
  42 import org.graalvm.compiler.debug.Debug;
  43 import org.graalvm.compiler.debug.DebugCounter;
  44 import org.graalvm.compiler.debug.GraalError;
  45 import org.graalvm.compiler.debug.Indent;
  46 import org.graalvm.compiler.lir.LIRInsertionBuffer;
  47 import org.graalvm.compiler.lir.LIRInstruction;
  48 import org.graalvm.compiler.lir.VirtualStackSlot;
  49 import org.graalvm.compiler.lir.framemap.FrameMap;
  50 import org.graalvm.compiler.lir.framemap.FrameMapBuilder;
  51 import org.graalvm.compiler.lir.framemap.FrameMapBuilderTool;
  52 import org.graalvm.compiler.lir.gen.LIRGenerationResult;
  53 import org.graalvm.compiler.lir.gen.LIRGeneratorTool.MoveFactory;
  54 import org.graalvm.compiler.options.OptionValues;
  55 
  56 import jdk.vm.ci.code.Architecture;
  57 import jdk.vm.ci.code.RegisterArray;
  58 import jdk.vm.ci.code.StackSlot;
  59 import jdk.vm.ci.meta.AllocatableValue;
  60 import jdk.vm.ci.meta.Value;
  61 
  62 /**
  63  */
  64 public final class TraceGlobalMoveResolver extends TraceGlobalMoveResolutionPhase.MoveResolver {
  65 
  66     private static final DebugCounter cycleBreakingSlotsAllocated = Debug.counter("TraceRA[cycleBreakingSlotsAllocated(global)]");
  67     private static final DebugCounter cycleBreakingSlotsReused = Debug.counter("TraceRA[cycleBreakingSlotsReused(global)]");
  68 
  69     private int insertIdx;
  70     private LIRInsertionBuffer insertionBuffer; // buffer where moves are inserted
  71 
  72     private final ArrayList<Value> mappingFrom;
  73     private final ArrayList<Value> mappingFromStack;
  74     private final ArrayList<AllocatableValue> mappingTo;
  75     private final int[] registerBlocked;
  76     private static final int STACK_SLOT_IN_CALLER_FRAME_IDX = -1;
  77     private int[] stackBlocked;
  78     private final int firstVirtualStackIndex;
  79     private final MoveFactory spillMoveFactory;
  80     private final FrameMapBuilder frameMapBuilder;
  81     private final OptionValues options;
  82 
  83     private void setValueBlocked(Value location, int direction) {
  84         assert direction == 1 || direction == -1 : "out of bounds";
  85         if (isStackSlotValue(location)) {
  86             int stackIdx = getStackArrayIndex(location);
  87             if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) {
  88                 // incoming stack arguments can be ignored
  89                 return;
  90             }
  91             if (stackIdx >= stackBlocked.length) {
  92                 stackBlocked = Arrays.copyOf(stackBlocked, stackIdx + 1);
  93             }
  94             stackBlocked[stackIdx] += direction;
  95         } else {
  96             assert direction == 1 || direction == -1 : "out of bounds";
  97             if (isRegister(location)) {
  98                 registerBlocked[asRegister(location).number] += direction;
  99             } else {
 100                 throw GraalError.shouldNotReachHere("unhandled value " + location);
 101             }
 102         }
 103     }
 104 
 105     private int valueBlocked(Value location) {
 106         if (isStackSlotValue(location)) {
 107             int stackIdx = getStackArrayIndex(location);
 108             if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) {
 109                 // incoming stack arguments are always blocked (aka they can not be written)
 110                 return 1;
 111             }
 112             if (stackIdx >= stackBlocked.length) {
 113                 return 0;
 114             }
 115             return stackBlocked[stackIdx];
 116         }
 117         if (isRegister(location)) {
 118             return registerBlocked[asRegister(location).number];
 119         }
 120         throw GraalError.shouldNotReachHere("unhandled value " + location);
 121     }
 122 
 123     private static boolean areMultipleReadsAllowed() {
 124         return true;
 125     }
 126 
 127     private boolean hasMappings() {
 128         return mappingFrom.size() > 0;
 129     }
 130 
 131     private MoveFactory getSpillMoveFactory() {
 132         return spillMoveFactory;
 133     }
 134 
 135     private RegisterArray getRegisters() {
 136         return frameMapBuilder.getRegisterConfig().getAllocatableRegisters();
 137     }
 138 
 139     public TraceGlobalMoveResolver(LIRGenerationResult res, MoveFactory spillMoveFactory, Architecture arch) {
 140 
 141         this.mappingFrom = new ArrayList<>(8);
 142         this.mappingFromStack = new ArrayList<>(8);
 143         this.mappingTo = new ArrayList<>(8);
 144         this.insertIdx = -1;
 145         this.insertionBuffer = new LIRInsertionBuffer();
 146 
 147         this.frameMapBuilder = res.getFrameMapBuilder();
 148         this.spillMoveFactory = spillMoveFactory;
 149         this.registerBlocked = new int[arch.getRegisters().size()];
 150 
 151         FrameMapBuilderTool frameMapBuilderTool = (FrameMapBuilderTool) frameMapBuilder;
 152         this.stackBlocked = new int[frameMapBuilderTool.getNumberOfStackSlots()];
 153 
 154         FrameMap frameMap = frameMapBuilderTool.getFrameMap();
 155         this.firstVirtualStackIndex = !frameMap.frameNeedsAllocating() ? 0 : frameMap.currentFrameSize() + 1;
 156         this.options = res.getLIR().getOptions();
 157     }
 158 
 159     private boolean checkEmpty() {
 160         for (int i = 0; i < stackBlocked.length; i++) {
 161             assert stackBlocked[i] == 0 : "stack map must be empty before and after processing";
 162         }
 163         assert mappingFrom.size() == 0 && mappingTo.size() == 0 && mappingFromStack.size() == 0 : "list must be empty before and after processing";
 164         for (int i = 0; i < getRegisters().size(); i++) {
 165             assert registerBlocked[i] == 0 : "register map must be empty before and after processing";
 166         }
 167         return true;
 168     }
 169 
 170     private boolean verifyBeforeResolve() {
 171         assert mappingFrom.size() == mappingTo.size() && mappingFrom.size() == mappingFromStack.size() : "length must be equal";
 172         assert insertIdx != -1 : "insert position not set";
 173 
 174         int i;
 175         int j;
 176         if (!areMultipleReadsAllowed()) {
 177             for (i = 0; i < mappingFrom.size(); i++) {
 178                 for (j = i + 1; j < mappingFrom.size(); j++) {
 179                     assert mappingFrom.get(i) == null || mappingFrom.get(i) != mappingFrom.get(j) : "cannot read from same interval twice";
 180                 }
 181             }
 182         }
 183 
 184         for (i = 0; i < mappingTo.size(); i++) {
 185             for (j = i + 1; j < mappingTo.size(); j++) {
 186                 assert mappingTo.get(i) != mappingTo.get(j) : "cannot write to same interval twice";
 187             }
 188         }
 189 
 190         for (i = 0; i < mappingTo.size(); i++) {
 191             Value to = mappingTo.get(i);
 192             assert !isStackSlotValue(to) || getStackArrayIndex(to) != STACK_SLOT_IN_CALLER_FRAME_IDX : "Cannot move to in argument: " + to;
 193         }
 194 
 195         HashSet<Value> usedRegs = new HashSet<>();
 196         if (!areMultipleReadsAllowed()) {
 197             for (i = 0; i < mappingFrom.size(); i++) {
 198                 Value from = mappingFrom.get(i);
 199                 if (from != null && !isIllegal(from)) {
 200                     boolean unique = usedRegs.add(from);
 201                     assert unique : "cannot read from same register twice";
 202                 }
 203             }
 204         }
 205 
 206         usedRegs.clear();
 207         for (i = 0; i < mappingTo.size(); i++) {
 208             Value to = mappingTo.get(i);
 209             if (isIllegal(to)) {
 210                 // After insertion the location may become illegal, so don't check it since multiple
 211                 // intervals might be illegal.
 212                 continue;
 213             }
 214             boolean unique = usedRegs.add(to);
 215             assert unique : "cannot write to same register twice";
 216         }
 217 
 218         return true;
 219     }
 220 
 221     // mark assignedReg and assignedRegHi of the interval as blocked
 222     private void block(Value location) {
 223         if (mightBeBlocked(location)) {
 224             assert areMultipleReadsAllowed() || valueBlocked(location) == 0 : "location already marked as used: " + location;
 225             setValueBlocked(location, 1);
 226             Debug.log("block %s", location);
 227         }
 228     }
 229 
 230     // mark assignedReg and assignedRegHi of the interval as unblocked
 231     private void unblock(Value location) {
 232         if (mightBeBlocked(location)) {
 233             assert valueBlocked(location) > 0 : "location already marked as unused: " + location;
 234             setValueBlocked(location, -1);
 235             Debug.log("unblock %s", location);
 236         }
 237     }
 238 
 239     /**
 240      * Checks if {@code to} is not blocked or is only blocked by {@code from}.
 241      */
 242     private boolean safeToProcessMove(Value fromLocation, Value toLocation) {
 243         if (mightBeBlocked(toLocation)) {
 244             if ((valueBlocked(toLocation) > 1 || (valueBlocked(toLocation) == 1 && !isMoveToSelf(fromLocation, toLocation)))) {
 245                 return false;
 246             }
 247         }
 248 
 249         return true;
 250     }
 251 
 252     public static boolean isMoveToSelf(Value from, Value to) {
 253         assert to != null;
 254         if (to.equals(from)) {
 255             return true;
 256         }
 257         if (from == null) {
 258             return false;
 259         }
 260         if (isShadowedRegisterValue(from)) {
 261             /* From is a shadowed register. */
 262             if (isShadowedRegisterValue(to)) {
 263                 // both shadowed but not equal
 264                 return false;
 265             }
 266             ShadowedRegisterValue shadowed = asShadowedRegisterValue(from);
 267             if (isRegisterToRegisterMoveToSelf(shadowed.getRegister(), to)) {
 268                 return true;
 269             }
 270             if (isStackSlotValue(to)) {
 271                 return to.equals(shadowed.getStackSlot());
 272             }
 273         } else {
 274             /*
 275              * A shadowed destination value is never a self move it both values are not equal. Fall
 276              * through.
 277              */
 278             // if (isShadowedRegisterValue(to)) return false;
 279 
 280             return isRegisterToRegisterMoveToSelf(from, to);
 281         }
 282         return false;
 283     }
 284 
 285     private static boolean isRegisterToRegisterMoveToSelf(Value from, Value to) {
 286         if (to.equals(from)) {
 287             return true;
 288         }
 289         if (isRegister(from) && isRegister(to) && asRegister(from).equals(asRegister(to))) {
 290             // Values differ but Registers are the same
 291             assert LIRKind.verifyMoveKinds(to.getValueKind(), from.getValueKind()) : String.format("Same register but Kind mismatch %s <- %s", to, from);
 292             return true;
 293         }
 294         return false;
 295     }
 296 
 297     private static boolean mightBeBlocked(Value location) {
 298         return isRegister(location) || isStackSlotValue(location);
 299     }
 300 
 301     private void createInsertionBuffer(ArrayList<LIRInstruction> list) {
 302         assert !insertionBuffer.initialized() : "overwriting existing buffer";
 303         insertionBuffer.init(list);
 304     }
 305 
 306     private void appendInsertionBuffer() {
 307         if (insertionBuffer.initialized()) {
 308             insertionBuffer.finish();
 309         }
 310         assert !insertionBuffer.initialized() : "must be uninitialized now";
 311 
 312         insertIdx = -1;
 313     }
 314 
 315     private void insertMove(Value fromOperand, AllocatableValue toOperand) {
 316         assert !fromOperand.equals(toOperand) : "from and to are equal: " + fromOperand + " vs. " + toOperand;
 317         assert LIRKind.verifyMoveKinds(fromOperand.getValueKind(), fromOperand.getValueKind()) : "move between different types";
 318         assert insertIdx != -1 : "must setup insert position first";
 319 
 320         insertionBuffer.append(insertIdx, createMove(fromOperand, toOperand));
 321 
 322         if (Debug.isLogEnabled()) {
 323             Debug.log("insert move from %s to %s at %d", fromOperand, toOperand, insertIdx);
 324         }
 325     }
 326 
 327     /**
 328      * @param fromOpr Operand of the {@code from} interval
 329      * @param toOpr Operand of the {@code to} interval
 330      */
 331     private LIRInstruction createMove(Value fromOpr, AllocatableValue toOpr) {
 332         if (isStackSlotValue(toOpr) && isStackSlotValue(fromOpr)) {
 333             return getSpillMoveFactory().createStackMove(toOpr, asAllocatableValue(fromOpr));
 334         }
 335         return getSpillMoveFactory().createMove(toOpr, fromOpr);
 336     }
 337 
 338     @SuppressWarnings("try")
 339     private void resolveMappings() {
 340         try (Indent indent = Debug.logAndIndent("resolveMapping")) {
 341             assert verifyBeforeResolve();
 342             if (Debug.isLogEnabled()) {
 343                 printMapping();
 344             }
 345 
 346             // Block all registers that are used as input operands of a move.
 347             // When a register is blocked, no move to this register is emitted.
 348             // This is necessary for detecting cycles in moves.
 349             for (int i = mappingFrom.size() - 1; i >= 0; i--) {
 350                 Value from = mappingFrom.get(i);
 351                 block(from);
 352             }
 353 
 354             ArrayList<AllocatableValue> busySpillSlots = null;
 355             while (mappingFrom.size() > 0) {
 356                 boolean processedInterval = false;
 357 
 358                 int spillCandidate = -1;
 359                 for (int i = mappingFrom.size() - 1; i >= 0; i--) {
 360                     Value fromLocation = mappingFrom.get(i);
 361                     AllocatableValue toLocation = mappingTo.get(i);
 362                     if (safeToProcessMove(fromLocation, toLocation)) {
 363                         // this interval can be processed because target is free
 364                         insertMove(fromLocation, toLocation);
 365                         unblock(fromLocation);
 366                         if (isStackSlotValue(toLocation)) {
 367                             if (busySpillSlots == null) {
 368                                 busySpillSlots = new ArrayList<>(2);
 369                             }
 370                             busySpillSlots.add(toLocation);
 371                         }
 372                         mappingFrom.remove(i);
 373                         mappingFromStack.remove(i);
 374                         mappingTo.remove(i);
 375 
 376                         processedInterval = true;
 377                     } else if (fromLocation != null) {
 378                         if (isRegister(fromLocation) && (busySpillSlots == null || !busySpillSlots.contains(mappingFromStack.get(i)))) {
 379                             // this interval cannot be processed now because target is not free
 380                             // it starts in a register, so it is a possible candidate for spilling
 381                             spillCandidate = i;
 382                         } else if (isStackSlotValue(fromLocation) && spillCandidate == -1) {
 383                             // fall back to spill a stack slot in case no other candidate is found
 384                             spillCandidate = i;
 385                         }
 386                     }
 387                 }
 388 
 389                 if (!processedInterval) {
 390                     breakCycle(spillCandidate);
 391                 }
 392             }
 393         }
 394 
 395         // check that all intervals have been processed
 396         assert checkEmpty();
 397     }
 398 
 399     @SuppressWarnings("try")
 400     private void breakCycle(int spillCandidate) {
 401         // no move could be processed because there is a cycle in the move list
 402         // (e.g. r1 . r2, r2 . r1), so one interval must be spilled to memory
 403         assert spillCandidate != -1 : "no interval in register for spilling found";
 404 
 405         // create a new spill interval and assign a stack slot to it
 406         Value from = mappingFrom.get(spillCandidate);
 407         try (Indent indent = Debug.logAndIndent("BreakCycle: %s", from)) {
 408             AllocatableValue spillSlot = null;
 409             if (TraceRegisterAllocationPhase.Options.TraceRAreuseStackSlotsForMoveResolutionCycleBreaking.getValue(options) && !isStackSlotValue(from)) {
 410                 // don't use the stack slot if from is already the stack slot
 411                 Value fromStack = mappingFromStack.get(spillCandidate);
 412                 if (fromStack != null) {
 413                     spillSlot = (AllocatableValue) fromStack;
 414                     cycleBreakingSlotsReused.increment();
 415                     Debug.log("reuse slot for spilling: %s", spillSlot);
 416                 }
 417             }
 418             if (spillSlot == null) {
 419                 spillSlot = frameMapBuilder.allocateSpillSlot(from.getValueKind());
 420                 cycleBreakingSlotsAllocated.increment();
 421                 Debug.log("created new slot for spilling: %s", spillSlot);
 422                 // insert a move from register to stack and update the mapping
 423                 insertMove(from, spillSlot);
 424             }
 425             block(spillSlot);
 426             mappingFrom.set(spillCandidate, spillSlot);
 427             unblock(from);
 428         }
 429     }
 430 
 431     @SuppressWarnings("try")
 432     private void printMapping() {
 433         try (Indent indent = Debug.logAndIndent("Mapping")) {
 434             for (int i = mappingFrom.size() - 1; i >= 0; i--) {
 435                 Debug.log("move %s <- %s (%s)", mappingTo.get(i), mappingFrom.get(i), mappingFromStack.get(i));
 436             }
 437         }
 438     }
 439 
 440     public void setInsertPosition(ArrayList<LIRInstruction> insertList, int insertIdx) {
 441         assert this.insertIdx == -1 : "use moveInsertPosition instead of setInsertPosition when data already set";
 442 
 443         createInsertionBuffer(insertList);
 444         this.insertIdx = insertIdx;
 445     }
 446 
 447     @Override
 448     public void addMapping(Value from, AllocatableValue to, Value fromStack) {
 449         if (Debug.isLogEnabled()) {
 450             Debug.log("add move mapping from %s to %s", from, to);
 451         }
 452 
 453         assert !from.equals(to) : "from and to interval equal: " + from;
 454         assert LIRKind.verifyMoveKinds(to.getValueKind(), from.getValueKind()) : String.format("Kind mismatch: %s vs. %s, from=%s, to=%s", from.getValueKind(), to.getValueKind(), from, to);
 455         assert fromStack == null || LIRKind.verifyMoveKinds(to.getValueKind(), fromStack.getValueKind()) : String.format("Kind mismatch: %s vs. %s, fromStack=%s, to=%s", fromStack.getValueKind(),
 456                         to.getValueKind(), fromStack, to);
 457         mappingFrom.add(from);
 458         mappingFromStack.add(fromStack);
 459         mappingTo.add(to);
 460     }
 461 
 462     public void resolveAndAppendMoves() {
 463         if (hasMappings()) {
 464             resolveMappings();
 465         }
 466         appendInsertionBuffer();
 467     }
 468 
 469     private int getStackArrayIndex(Value stackSlotValue) {
 470         if (isStackSlot(stackSlotValue)) {
 471             return getStackArrayIndex(asStackSlot(stackSlotValue));
 472         }
 473         if (isVirtualStackSlot(stackSlotValue)) {
 474             return getStackArrayIndex(asVirtualStackSlot(stackSlotValue));
 475         }
 476         throw GraalError.shouldNotReachHere("value is not a stack slot: " + stackSlotValue);
 477     }
 478 
 479     private int getStackArrayIndex(StackSlot stackSlot) {
 480         int stackIdx;
 481         if (stackSlot.isInCallerFrame()) {
 482             // incoming stack arguments can be ignored
 483             stackIdx = STACK_SLOT_IN_CALLER_FRAME_IDX;
 484         } else {
 485             assert stackSlot.getRawAddFrameSize() : "Unexpected stack slot: " + stackSlot;
 486             int offset = -stackSlot.getRawOffset();
 487             assert 0 <= offset && offset < firstVirtualStackIndex : String.format("Wrong stack slot offset: %d (first virtual stack slot index: %d", offset, firstVirtualStackIndex);
 488             stackIdx = offset;
 489         }
 490         return stackIdx;
 491     }
 492 
 493     private int getStackArrayIndex(VirtualStackSlot virtualStackSlot) {
 494         return firstVirtualStackIndex + virtualStackSlot.getId();
 495     }
 496 
 497 }