hotspot/src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.lir/src/org/graalvm/compiler/lir/alloc/trace/lsra/TraceLocalMoveResolver.java - platform/libcore - Git at Google

 /*
  * Copyright (c) 2009, 2015, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
  * under the terms of the GNU General Public License version 2 only, as
  * published by the Free Software Foundation.
  *
  * This code is distributed in the hope that it will be useful, but WITHOUT
  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  * version 2 for more details (a copy is included in the LICENSE file that
  * accompanied this code).
  *
  * You should have received a copy of the GNU General Public License version
  * 2 along with this work; if not, write to the Free Software Foundation,
  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  *
  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  * or visit www.oracle.com if you need additional information or have any
  * questions.
  */
 package org.graalvm.compiler.lir.alloc.trace.lsra;

 import static org.graalvm.compiler.lir.LIRValueUtil.asVirtualStackSlot;
 import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;
 import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot;
 import static jdk.vm.ci.code.ValueUtil.asRegister;
 import static jdk.vm.ci.code.ValueUtil.asStackSlot;
 import static jdk.vm.ci.code.ValueUtil.isIllegal;
 import static jdk.vm.ci.code.ValueUtil.isRegister;
 import static jdk.vm.ci.code.ValueUtil.isStackSlot;

 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.HashSet;
 import java.util.List;

 import org.graalvm.compiler.core.common.LIRKind;
 import org.graalvm.compiler.debug.Debug;
 import org.graalvm.compiler.debug.DebugCounter;
 import org.graalvm.compiler.debug.GraalError;
 import org.graalvm.compiler.debug.Indent;
 import org.graalvm.compiler.lir.LIRInsertionBuffer;
 import org.graalvm.compiler.lir.LIRInstruction;
 import org.graalvm.compiler.lir.VirtualStackSlot;
 import org.graalvm.compiler.lir.alloc.trace.lsra.TraceLinearScanPhase.TraceLinearScan;
 import org.graalvm.compiler.lir.framemap.FrameMap;
 import org.graalvm.compiler.lir.framemap.FrameMapBuilderTool;

 import jdk.vm.ci.code.StackSlot;
 import jdk.vm.ci.meta.AllocatableValue;
 import jdk.vm.ci.meta.Constant;
 import jdk.vm.ci.meta.JavaConstant;
 import jdk.vm.ci.meta.Value;

 /**
  */
 final class TraceLocalMoveResolver {

     private static final DebugCounter cycleBreakingSlotsAllocated = Debug.counter("TraceRA[cycleBreakingSlotsAllocated(local)]");

     private static final int STACK_SLOT_IN_CALLER_FRAME_IDX = -1;
     private final TraceLinearScan allocator;

     private int insertIdx;
     private LIRInsertionBuffer insertionBuffer; // buffer where moves are inserted

     private final List<TraceInterval> mappingFrom;
     private final List<Constant> mappingFromOpr;
     private final List<TraceInterval> mappingTo;
     private final int[] registerBlocked;

     private int[] stackBlocked;
     private final int firstVirtualStackIndex;

     private int getStackArrayIndex(Value stackSlotValue) {
         if (isStackSlot(stackSlotValue)) {
             return getStackArrayIndex(asStackSlot(stackSlotValue));
         }
         if (isVirtualStackSlot(stackSlotValue)) {
             return getStackArrayIndex(asVirtualStackSlot(stackSlotValue));
         }
         throw GraalError.shouldNotReachHere("value is not a stack slot: " + stackSlotValue);
     }

     private int getStackArrayIndex(StackSlot stackSlot) {
         int stackIdx;
         if (stackSlot.isInCallerFrame()) {
             // incoming stack arguments can be ignored
             stackIdx = STACK_SLOT_IN_CALLER_FRAME_IDX;
         } else {
             assert stackSlot.getRawAddFrameSize() : "Unexpected stack slot: " + stackSlot;
             int offset = -stackSlot.getRawOffset();
             assert 0 <= offset && offset < firstVirtualStackIndex : String.format("Wrong stack slot offset: %d (first virtual stack slot index: %d", offset, firstVirtualStackIndex);
             stackIdx = offset;
         }
         return stackIdx;
     }

     private int getStackArrayIndex(VirtualStackSlot virtualStackSlot) {
         return firstVirtualStackIndex + virtualStackSlot.getId();
     }

     protected void setValueBlocked(Value location, int direction) {
         assert direction == 1 || direction == -1 : "out of bounds";
         if (isStackSlotValue(location)) {
             int stackIdx = getStackArrayIndex(location);
             if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) {
                 // incoming stack arguments can be ignored
                 return;
             }
             if (stackIdx >= stackBlocked.length) {
                 stackBlocked = Arrays.copyOf(stackBlocked, stackIdx + 1);
             }
             stackBlocked[stackIdx] += direction;
         } else {
             assert direction == 1 || direction == -1 : "out of bounds";
             if (isRegister(location)) {
                 registerBlocked[asRegister(location).number] += direction;
             } else {
                 throw GraalError.shouldNotReachHere("unhandled value " + location);
             }
         }
     }

     protected TraceInterval getMappingFrom(int i) {
         return mappingFrom.get(i);
     }

     protected int mappingFromSize() {
         return mappingFrom.size();
     }

     protected int valueBlocked(Value location) {
         if (isStackSlotValue(location)) {
             int stackIdx = getStackArrayIndex(location);
             if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) {
                 // incoming stack arguments are always blocked (aka they can not be written)
                 return 1;
             }
             if (stackIdx >= stackBlocked.length) {
                 return 0;
             }
             return stackBlocked[stackIdx];
         }
         if (isRegister(location)) {
             return registerBlocked[asRegister(location).number];
         }
         throw GraalError.shouldNotReachHere("unhandled value " + location);
     }

     /*
      * TODO (je) remove?
      */
     protected static boolean areMultipleReadsAllowed() {
         return true;
     }

     boolean hasMappings() {
         return mappingFrom.size() > 0;
     }

     protected TraceLinearScan getAllocator() {
         return allocator;
     }

     protected TraceLocalMoveResolver(TraceLinearScan allocator) {

         this.allocator = allocator;
         this.mappingFrom = new ArrayList<>(8);
         this.mappingFromOpr = new ArrayList<>(8);
         this.mappingTo = new ArrayList<>(8);
         this.insertIdx = -1;
         this.insertionBuffer = new LIRInsertionBuffer();
         this.registerBlocked = new int[allocator.getRegisters().size()];
         FrameMapBuilderTool frameMapBuilderTool = (FrameMapBuilderTool) allocator.getFrameMapBuilder();
         FrameMap frameMap = frameMapBuilderTool.getFrameMap();
         this.stackBlocked = new int[frameMapBuilderTool.getNumberOfStackSlots()];
         this.firstVirtualStackIndex = !frameMap.frameNeedsAllocating() ? 0 : frameMap.currentFrameSize() + 1;
     }

     protected boolean checkEmpty() {
         assert mappingFrom.size() == 0 && mappingFromOpr.size() == 0 && mappingTo.size() == 0 : "list must be empty before and after processing";
         for (int i = 0; i < stackBlocked.length; i++) {
             assert stackBlocked[i] == 0 : "stack map must be empty before and after processing";
         }
         for (int i = 0; i < getAllocator().getRegisters().size(); i++) {
             assert registerBlocked[i] == 0 : "register map must be empty before and after processing";
         }
         checkMultipleReads();
         return true;
     }

     protected void checkMultipleReads() {
         // multiple reads are allowed in SSA LSRA
     }

     private boolean verifyBeforeResolve() {
         assert mappingFrom.size() == mappingFromOpr.size() : "length must be equal";
         assert mappingFrom.size() == mappingTo.size() : "length must be equal";
         assert insertIdx != -1 : "insert position not set";

         int i;
         int j;
         if (!areMultipleReadsAllowed()) {
             for (i = 0; i < mappingFrom.size(); i++) {
                 for (j = i + 1; j < mappingFrom.size(); j++) {
                     assert mappingFrom.get(i) == null || mappingFrom.get(i) != mappingFrom.get(j) : "cannot read from same interval twice";
                 }
             }
         }

         for (i = 0; i < mappingTo.size(); i++) {
             for (j = i + 1; j < mappingTo.size(); j++) {
                 assert mappingTo.get(i) != mappingTo.get(j) : "cannot write to same interval twice";
             }
         }

         HashSet<Value> usedRegs = new HashSet<>();
         if (!areMultipleReadsAllowed()) {
             for (i = 0; i < mappingFrom.size(); i++) {
                 TraceInterval interval = mappingFrom.get(i);
                 if (interval != null && !isIllegal(interval.location())) {
                     boolean unique = usedRegs.add(interval.location());
                     assert unique : "cannot read from same register twice";
                 }
             }
         }

         usedRegs.clear();
         for (i = 0; i < mappingTo.size(); i++) {
             TraceInterval interval = mappingTo.get(i);
             if (isIllegal(interval.location())) {
                 // After insertion the location may become illegal, so don't check it since multiple
                 // intervals might be illegal.
                 continue;
             }
             boolean unique = usedRegs.add(interval.location());
             assert unique : "cannot write to same register twice";
         }

         verifyStackSlotMapping();

         return true;
     }

     protected void verifyStackSlotMapping() {
         // relax disjoint stack maps invariant
     }

     // mark assignedReg and assignedRegHi of the interval as blocked
     private void blockRegisters(TraceInterval interval) {
         Value location = interval.location();
         if (mightBeBlocked(location)) {
             assert areMultipleReadsAllowed() || valueBlocked(location) == 0 : "location already marked as used: " + location;
             int direction = 1;
             setValueBlocked(location, direction);
             Debug.log("block %s", location);
         }
     }

     // mark assignedReg and assignedRegHi of the interval as unblocked
     private void unblockRegisters(TraceInterval interval) {
         Value location = interval.location();
         if (mightBeBlocked(location)) {
             assert valueBlocked(location) > 0 : "location already marked as unused: " + location;
             setValueBlocked(location, -1);
             Debug.log("unblock %s", location);
         }
     }

     /**
      * Checks if the {@linkplain TraceInterval#location() location} of {@code to} is not blocked or
      * is only blocked by {@code from}.
      */
     private boolean safeToProcessMove(TraceInterval from, TraceInterval to) {
         Value fromReg = from != null ? from.location() : null;

         Value location = to.location();
         if (mightBeBlocked(location)) {
             if ((valueBlocked(location) > 1 || (valueBlocked(location) == 1 && !isMoveToSelf(fromReg, location)))) {
                 return false;
             }
         }

         return true;
     }

     protected static boolean isMoveToSelf(Value from, Value to) {
         assert to != null;
         if (to.equals(from)) {
             return true;
         }
         if (from != null && isRegister(from) && isRegister(to) && asRegister(from).equals(asRegister(to))) {
             assert LIRKind.verifyMoveKinds(to.getValueKind(), from.getValueKind()) : String.format("Same register but Kind mismatch %s <- %s", to, from);
             return true;
         }
         return false;
     }

     protected static boolean mightBeBlocked(Value location) {
         if (isRegister(location)) {
             return true;
         }
         if (isStackSlotValue(location)) {
             return true;
         }
         return false;
     }

     private void createInsertionBuffer(List<LIRInstruction> list) {
         assert !insertionBuffer.initialized() : "overwriting existing buffer";
         insertionBuffer.init(list);
     }

     private void appendInsertionBuffer() {
         if (insertionBuffer.initialized()) {
             insertionBuffer.finish();
         }
         assert !insertionBuffer.initialized() : "must be uninitialized now";

         insertIdx = -1;
     }

     private void insertMove(TraceInterval fromInterval, TraceInterval toInterval) {
         assert !fromInterval.operand.equals(toInterval.operand) : "from and to interval equal: " + fromInterval;
         assert LIRKind.verifyMoveKinds(toInterval.kind(), fromInterval.kind()) : "move between different types";
         assert insertIdx != -1 : "must setup insert position first";

         insertionBuffer.append(insertIdx, createMove(fromInterval.operand, toInterval.operand, fromInterval.location(), toInterval.location()));

         if (Debug.isLogEnabled()) {
             Debug.log("insert move from %s to %s at %d", fromInterval, toInterval, insertIdx);
         }
     }

     /**
      * @param fromOpr {@link TraceInterval#operand operand} of the {@code from} interval
      * @param toOpr {@link TraceInterval#operand operand} of the {@code to} interval
      * @param fromLocation {@link TraceInterval#location() location} of the {@code to} interval
      * @param toLocation {@link TraceInterval#location() location} of the {@code to} interval
      */
     protected LIRInstruction createMove(AllocatableValue fromOpr, AllocatableValue toOpr, AllocatableValue fromLocation, AllocatableValue toLocation) {
         if (isStackSlotValue(toLocation) && isStackSlotValue(fromLocation)) {
             return getAllocator().getSpillMoveFactory().createStackMove(toOpr, fromOpr);
         }
         return getAllocator().getSpillMoveFactory().createMove(toOpr, fromOpr);
     }

     private void insertMove(Constant fromOpr, TraceInterval toInterval) {
         assert insertIdx != -1 : "must setup insert position first";

         AllocatableValue toOpr = toInterval.operand;
         LIRInstruction move = getAllocator().getSpillMoveFactory().createLoad(toOpr, fromOpr);
         insertionBuffer.append(insertIdx, move);

         if (Debug.isLogEnabled()) {
             Debug.log("insert move from value %s to %s at %d", fromOpr, toInterval, insertIdx);
         }
     }

     @SuppressWarnings("try")
     private void resolveMappings() {
         try (Indent indent = Debug.logAndIndent("resolveMapping")) {
             assert verifyBeforeResolve();
             if (Debug.isLogEnabled()) {
                 printMapping();
             }

             // Block all registers that are used as input operands of a move.
             // When a register is blocked, no move to this register is emitted.
             // This is necessary for detecting cycles in moves.
             int i;
             for (i = mappingFrom.size() - 1; i >= 0; i--) {
                 TraceInterval fromInterval = mappingFrom.get(i);
                 if (fromInterval != null) {
                     blockRegisters(fromInterval);
                 }
             }

             ArrayList<AllocatableValue> busySpillSlots = null;
             while (mappingFrom.size() > 0) {
                 boolean processedInterval = false;

                 int spillCandidate = -1;
                 for (i = mappingFrom.size() - 1; i >= 0; i--) {
                     TraceInterval fromInterval = mappingFrom.get(i);
                     TraceInterval toInterval = mappingTo.get(i);

                     if (safeToProcessMove(fromInterval, toInterval)) {
                         // this interval can be processed because target is free
                         if (fromInterval != null) {
                             insertMove(fromInterval, toInterval);
                             unblockRegisters(fromInterval);
                         } else {
                             insertMove(mappingFromOpr.get(i), toInterval);
                         }
                         if (isStackSlotValue(toInterval.location())) {
                             if (busySpillSlots == null) {
                                 busySpillSlots = new ArrayList<>(2);
                             }
                             busySpillSlots.add(toInterval.location());
                         }
                         mappingFrom.remove(i);
                         mappingFromOpr.remove(i);
                         mappingTo.remove(i);

                         processedInterval = true;
                     } else if (fromInterval != null && isRegister(fromInterval.location()) && (busySpillSlots == null || !busySpillSlots.contains(fromInterval.spillSlot()))) {
                         // this interval cannot be processed now because target is not free
                         // it starts in a register, so it is a possible candidate for spilling
                         spillCandidate = i;
                     }
                 }

                 if (!processedInterval) {
                     breakCycle(spillCandidate);
                 }
             }
         }

         // check that all intervals have been processed
         assert checkEmpty();
     }

     protected void breakCycle(int spillCandidate) {
         if (spillCandidate != -1) {
             // no move could be processed because there is a cycle in the move list
             // (e.g. r1 . r2, r2 . r1), so one interval must be spilled to memory
             assert spillCandidate != -1 : "no interval in register for spilling found";

             // create a new spill interval and assign a stack slot to it
             TraceInterval fromInterval1 = mappingFrom.get(spillCandidate);
             // do not allocate a new spill slot for temporary interval, but
             // use spill slot assigned to fromInterval. Otherwise moves from
             // one stack slot to another can happen (not allowed by LIRAssembler
             AllocatableValue spillSlot1 = fromInterval1.spillSlot();
             if (spillSlot1 == null) {
                 spillSlot1 = getAllocator().getFrameMapBuilder().allocateSpillSlot(fromInterval1.kind());
                 fromInterval1.setSpillSlot(spillSlot1);
                 cycleBreakingSlotsAllocated.increment();
             }
             spillInterval(spillCandidate, fromInterval1, spillSlot1);
             return;
         }
         assert mappingFromSize() > 1;
         // Arbitrarily select the first entry for spilling.
         int stackSpillCandidate = 0;
         TraceInterval fromInterval = getMappingFrom(stackSpillCandidate);
         // allocate new stack slot
         VirtualStackSlot spillSlot = getAllocator().getFrameMapBuilder().allocateSpillSlot(fromInterval.kind());
         spillInterval(stackSpillCandidate, fromInterval, spillSlot);
     }

     protected void spillInterval(int spillCandidate, TraceInterval fromInterval, AllocatableValue spillSlot) {
         assert mappingFrom.get(spillCandidate).equals(fromInterval);
         TraceInterval spillInterval = getAllocator().createDerivedInterval(fromInterval);

         // add a dummy range because real position is difficult to calculate
         // Note: this range is a special case when the integrity of the allocation is
         // checked
         spillInterval.addRange(1, 2);

         spillInterval.assignLocation(spillSlot);

         if (Debug.isLogEnabled()) {
             Debug.log("created new Interval for spilling: %s", spillInterval);
         }
         blockRegisters(spillInterval);

         // insert a move from register to stack and update the mapping
         insertMove(fromInterval, spillInterval);
         mappingFrom.set(spillCandidate, spillInterval);
         unblockRegisters(fromInterval);
     }

     @SuppressWarnings("try")
     private void printMapping() {
         try (Indent indent = Debug.logAndIndent("Mapping")) {
             for (int i = mappingFrom.size() - 1; i >= 0; i--) {
                 TraceInterval fromInterval = mappingFrom.get(i);
                 TraceInterval toInterval = mappingTo.get(i);
                 String from;
                 Value to = toInterval.location();
                 if (fromInterval == null) {
                     from = mappingFromOpr.get(i).toString();
                 } else {
                     from = fromInterval.location().toString();
                 }
                 Debug.log("move %s <- %s", from, to);
             }
         }
     }

     void setInsertPosition(List<LIRInstruction> insertList, int insertIdx) {
         assert this.insertIdx == -1 : "use moveInsertPosition instead of setInsertPosition when data already set";

         createInsertionBuffer(insertList);
         this.insertIdx = insertIdx;
     }

     void moveInsertPosition(List<LIRInstruction> newInsertList, int newInsertIdx) {
         if (insertionBuffer.lirList() != null && (insertionBuffer.lirList() != newInsertList || this.insertIdx != newInsertIdx)) {
             // insert position changed . resolve current mappings
             resolveMappings();
         }

         assert insertionBuffer.lirList() != newInsertList || newInsertIdx >= insertIdx : String.format("Decreasing insert index: old=%d new=%d", insertIdx, newInsertIdx);

         if (insertionBuffer.lirList() != newInsertList) {
             // block changed . append insertionBuffer because it is
             // bound to a specific block and create a new insertionBuffer
             appendInsertionBuffer();
             createInsertionBuffer(newInsertList);
         }

         this.insertIdx = newInsertIdx;
     }

     public void addMapping(TraceInterval fromInterval, TraceInterval toInterval) {

         if (isIllegal(toInterval.location()) && toInterval.canMaterialize()) {
             if (Debug.isLogEnabled()) {
                 Debug.log("no store to rematerializable interval %s needed", toInterval);
             }
             return;
         }
         if (isIllegal(fromInterval.location()) && fromInterval.canMaterialize()) {
             // Instead of a reload, re-materialize the value
             JavaConstant rematValue = fromInterval.getMaterializedValue();
             addMapping(rematValue, toInterval);
             return;
         }
         if (Debug.isLogEnabled()) {
             Debug.log("add move mapping from %s to %s", fromInterval, toInterval);
         }

         assert !fromInterval.operand.equals(toInterval.operand) : "from and to interval equal: " + fromInterval;
         assert LIRKind.verifyMoveKinds(toInterval.kind(), fromInterval.kind()) : String.format("Kind mismatch: %s vs. %s, from=%s, to=%s", fromInterval.kind(), toInterval.kind(), fromInterval,
                         toInterval);
         mappingFrom.add(fromInterval);
         mappingFromOpr.add(null);
         mappingTo.add(toInterval);
     }

     public void addMapping(Constant fromOpr, TraceInterval toInterval) {
         if (Debug.isLogEnabled()) {
             Debug.log("add move mapping from %s to %s", fromOpr, toInterval);
         }

         mappingFrom.add(null);
         mappingFromOpr.add(fromOpr);
         mappingTo.add(toInterval);
     }

     void resolveAndAppendMoves() {
         if (hasMappings()) {
             resolveMappings();
         }
         appendInsertionBuffer();
     }
 }
	/*
	* Copyright (c) 2009, 2015, Oracle and/or its affiliates. All rights reserved.
	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
	*
	* This code is free software; you can redistribute it and/or modify it
	* under the terms of the GNU General Public License version 2 only, as
	* published by the Free Software Foundation.
	*
	* This code is distributed in the hope that it will be useful, but WITHOUT
	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	* version 2 for more details (a copy is included in the LICENSE file that
	* accompanied this code).
	*
	* You should have received a copy of the GNU General Public License version
	* 2 along with this work; if not, write to the Free Software Foundation,
	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
	*
	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
	* or visit www.oracle.com if you need additional information or have any
	* questions.
	*/
	package org.graalvm.compiler.lir.alloc.trace.lsra;

	import static org.graalvm.compiler.lir.LIRValueUtil.asVirtualStackSlot;
	import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;
	import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot;
	import static jdk.vm.ci.code.ValueUtil.asRegister;
	import static jdk.vm.ci.code.ValueUtil.asStackSlot;
	import static jdk.vm.ci.code.ValueUtil.isIllegal;
	import static jdk.vm.ci.code.ValueUtil.isRegister;
	import static jdk.vm.ci.code.ValueUtil.isStackSlot;

	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.HashSet;
	import java.util.List;

	import org.graalvm.compiler.core.common.LIRKind;
	import org.graalvm.compiler.debug.Debug;
	import org.graalvm.compiler.debug.DebugCounter;
	import org.graalvm.compiler.debug.GraalError;
	import org.graalvm.compiler.debug.Indent;
	import org.graalvm.compiler.lir.LIRInsertionBuffer;
	import org.graalvm.compiler.lir.LIRInstruction;
	import org.graalvm.compiler.lir.VirtualStackSlot;
	import org.graalvm.compiler.lir.alloc.trace.lsra.TraceLinearScanPhase.TraceLinearScan;
	import org.graalvm.compiler.lir.framemap.FrameMap;
	import org.graalvm.compiler.lir.framemap.FrameMapBuilderTool;

	import jdk.vm.ci.code.StackSlot;
	import jdk.vm.ci.meta.AllocatableValue;
	import jdk.vm.ci.meta.Constant;
	import jdk.vm.ci.meta.JavaConstant;
	import jdk.vm.ci.meta.Value;

	/**
	*/
	final class TraceLocalMoveResolver {

	private static final DebugCounter cycleBreakingSlotsAllocated = Debug.counter("TraceRA[cycleBreakingSlotsAllocated(local)]");

	private static final int STACK_SLOT_IN_CALLER_FRAME_IDX = -1;
	private final TraceLinearScan allocator;

	private int insertIdx;
	private LIRInsertionBuffer insertionBuffer; // buffer where moves are inserted

	private final List<TraceInterval> mappingFrom;
	private final List<Constant> mappingFromOpr;
	private final List<TraceInterval> mappingTo;
	private final int[] registerBlocked;

	private int[] stackBlocked;
	private final int firstVirtualStackIndex;

	private int getStackArrayIndex(Value stackSlotValue) {
	if (isStackSlot(stackSlotValue)) {
	return getStackArrayIndex(asStackSlot(stackSlotValue));
	}
	if (isVirtualStackSlot(stackSlotValue)) {
	return getStackArrayIndex(asVirtualStackSlot(stackSlotValue));
	}
	throw GraalError.shouldNotReachHere("value is not a stack slot: " + stackSlotValue);
	}

	private int getStackArrayIndex(StackSlot stackSlot) {
	int stackIdx;
	if (stackSlot.isInCallerFrame()) {
	// incoming stack arguments can be ignored
	stackIdx = STACK_SLOT_IN_CALLER_FRAME_IDX;
	} else {
	assert stackSlot.getRawAddFrameSize() : "Unexpected stack slot: " + stackSlot;
	int offset = -stackSlot.getRawOffset();
	assert 0 <= offset && offset < firstVirtualStackIndex : String.format("Wrong stack slot offset: %d (first virtual stack slot index: %d", offset, firstVirtualStackIndex);
	stackIdx = offset;
	}
	return stackIdx;
	}

	private int getStackArrayIndex(VirtualStackSlot virtualStackSlot) {
	return firstVirtualStackIndex + virtualStackSlot.getId();
	}

	protected void setValueBlocked(Value location, int direction) {
	assert direction == 1 \|\| direction == -1 : "out of bounds";
	if (isStackSlotValue(location)) {
	int stackIdx = getStackArrayIndex(location);
	if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) {
	// incoming stack arguments can be ignored
	return;
	}
	if (stackIdx >= stackBlocked.length) {
	stackBlocked = Arrays.copyOf(stackBlocked, stackIdx + 1);
	}
	stackBlocked[stackIdx] += direction;
	} else {
	assert direction == 1 \|\| direction == -1 : "out of bounds";
	if (isRegister(location)) {
	registerBlocked[asRegister(location).number] += direction;
	} else {
	throw GraalError.shouldNotReachHere("unhandled value " + location);
	}
	}
	}

	protected TraceInterval getMappingFrom(int i) {
	return mappingFrom.get(i);
	}

	protected int mappingFromSize() {
	return mappingFrom.size();
	}

	protected int valueBlocked(Value location) {
	if (isStackSlotValue(location)) {
	int stackIdx = getStackArrayIndex(location);
	if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) {
	// incoming stack arguments are always blocked (aka they can not be written)
	return 1;
	}
	if (stackIdx >= stackBlocked.length) {
	return 0;
	}
	return stackBlocked[stackIdx];
	}
	if (isRegister(location)) {
	return registerBlocked[asRegister(location).number];
	}
	throw GraalError.shouldNotReachHere("unhandled value " + location);
	}

	/*
	* TODO (je) remove?
	*/
	protected static boolean areMultipleReadsAllowed() {
	return true;
	}

	boolean hasMappings() {
	return mappingFrom.size() > 0;
	}

	protected TraceLinearScan getAllocator() {
	return allocator;
	}

	protected TraceLocalMoveResolver(TraceLinearScan allocator) {

	this.allocator = allocator;
	this.mappingFrom = new ArrayList<>(8);
	this.mappingFromOpr = new ArrayList<>(8);
	this.mappingTo = new ArrayList<>(8);
	this.insertIdx = -1;
	this.insertionBuffer = new LIRInsertionBuffer();
	this.registerBlocked = new int[allocator.getRegisters().size()];
	FrameMapBuilderTool frameMapBuilderTool = (FrameMapBuilderTool) allocator.getFrameMapBuilder();
	FrameMap frameMap = frameMapBuilderTool.getFrameMap();
	this.stackBlocked = new int[frameMapBuilderTool.getNumberOfStackSlots()];
	this.firstVirtualStackIndex = !frameMap.frameNeedsAllocating() ? 0 : frameMap.currentFrameSize() + 1;
	}

	protected boolean checkEmpty() {
	assert mappingFrom.size() == 0 && mappingFromOpr.size() == 0 && mappingTo.size() == 0 : "list must be empty before and after processing";
	for (int i = 0; i < stackBlocked.length; i++) {
	assert stackBlocked[i] == 0 : "stack map must be empty before and after processing";
	}
	for (int i = 0; i < getAllocator().getRegisters().size(); i++) {
	assert registerBlocked[i] == 0 : "register map must be empty before and after processing";
	}
	checkMultipleReads();
	return true;
	}

	protected void checkMultipleReads() {
	// multiple reads are allowed in SSA LSRA
	}

	private boolean verifyBeforeResolve() {
	assert mappingFrom.size() == mappingFromOpr.size() : "length must be equal";
	assert mappingFrom.size() == mappingTo.size() : "length must be equal";
	assert insertIdx != -1 : "insert position not set";

	int i;
	int j;
	if (!areMultipleReadsAllowed()) {
	for (i = 0; i < mappingFrom.size(); i++) {
	for (j = i + 1; j < mappingFrom.size(); j++) {
	assert mappingFrom.get(i) == null \|\| mappingFrom.get(i) != mappingFrom.get(j) : "cannot read from same interval twice";
	}
	}
	}

	for (i = 0; i < mappingTo.size(); i++) {
	for (j = i + 1; j < mappingTo.size(); j++) {
	assert mappingTo.get(i) != mappingTo.get(j) : "cannot write to same interval twice";
	}
	}

	HashSet<Value> usedRegs = new HashSet<>();
	if (!areMultipleReadsAllowed()) {
	for (i = 0; i < mappingFrom.size(); i++) {
	TraceInterval interval = mappingFrom.get(i);
	if (interval != null && !isIllegal(interval.location())) {
	boolean unique = usedRegs.add(interval.location());
	assert unique : "cannot read from same register twice";
	}
	}
	}

	usedRegs.clear();
	for (i = 0; i < mappingTo.size(); i++) {
	TraceInterval interval = mappingTo.get(i);
	if (isIllegal(interval.location())) {
	// After insertion the location may become illegal, so don't check it since multiple
	// intervals might be illegal.
	continue;
	}
	boolean unique = usedRegs.add(interval.location());
	assert unique : "cannot write to same register twice";
	}

	verifyStackSlotMapping();

	return true;
	}

	protected void verifyStackSlotMapping() {
	// relax disjoint stack maps invariant
	}

	// mark assignedReg and assignedRegHi of the interval as blocked
	private void blockRegisters(TraceInterval interval) {
	Value location = interval.location();
	if (mightBeBlocked(location)) {
	assert areMultipleReadsAllowed() \|\| valueBlocked(location) == 0 : "location already marked as used: " + location;
	int direction = 1;
	setValueBlocked(location, direction);
	Debug.log("block %s", location);
	}
	}

	// mark assignedReg and assignedRegHi of the interval as unblocked
	private void unblockRegisters(TraceInterval interval) {
	Value location = interval.location();
	if (mightBeBlocked(location)) {
	assert valueBlocked(location) > 0 : "location already marked as unused: " + location;
	setValueBlocked(location, -1);
	Debug.log("unblock %s", location);
	}
	}

	/**
	* Checks if the {@linkplain TraceInterval#location() location} of {@code to} is not blocked or
	* is only blocked by {@code from}.
	*/
	private boolean safeToProcessMove(TraceInterval from, TraceInterval to) {
	Value fromReg = from != null ? from.location() : null;

	Value location = to.location();
	if (mightBeBlocked(location)) {
	if ((valueBlocked(location) > 1 \|\| (valueBlocked(location) == 1 && !isMoveToSelf(fromReg, location)))) {
	return false;
	}
	}

	return true;
	}

	protected static boolean isMoveToSelf(Value from, Value to) {
	assert to != null;
	if (to.equals(from)) {
	return true;
	}
	if (from != null && isRegister(from) && isRegister(to) && asRegister(from).equals(asRegister(to))) {
	assert LIRKind.verifyMoveKinds(to.getValueKind(), from.getValueKind()) : String.format("Same register but Kind mismatch %s <- %s", to, from);
	return true;
	}
	return false;
	}

	protected static boolean mightBeBlocked(Value location) {
	if (isRegister(location)) {
	return true;
	}
	if (isStackSlotValue(location)) {
	return true;
	}
	return false;
	}

	private void createInsertionBuffer(List<LIRInstruction> list) {
	assert !insertionBuffer.initialized() : "overwriting existing buffer";
	insertionBuffer.init(list);
	}

	private void appendInsertionBuffer() {
	if (insertionBuffer.initialized()) {
	insertionBuffer.finish();
	}
	assert !insertionBuffer.initialized() : "must be uninitialized now";

	insertIdx = -1;
	}

	private void insertMove(TraceInterval fromInterval, TraceInterval toInterval) {
	assert !fromInterval.operand.equals(toInterval.operand) : "from and to interval equal: " + fromInterval;
	assert LIRKind.verifyMoveKinds(toInterval.kind(), fromInterval.kind()) : "move between different types";
	assert insertIdx != -1 : "must setup insert position first";

	insertionBuffer.append(insertIdx, createMove(fromInterval.operand, toInterval.operand, fromInterval.location(), toInterval.location()));

	if (Debug.isLogEnabled()) {
	Debug.log("insert move from %s to %s at %d", fromInterval, toInterval, insertIdx);
	}
	}

	/**
	* @param fromOpr {@link TraceInterval#operand operand} of the {@code from} interval
	* @param toOpr {@link TraceInterval#operand operand} of the {@code to} interval
	* @param fromLocation {@link TraceInterval#location() location} of the {@code to} interval
	* @param toLocation {@link TraceInterval#location() location} of the {@code to} interval
	*/
	protected LIRInstruction createMove(AllocatableValue fromOpr, AllocatableValue toOpr, AllocatableValue fromLocation, AllocatableValue toLocation) {
	if (isStackSlotValue(toLocation) && isStackSlotValue(fromLocation)) {
	return getAllocator().getSpillMoveFactory().createStackMove(toOpr, fromOpr);
	}
	return getAllocator().getSpillMoveFactory().createMove(toOpr, fromOpr);
	}

	private void insertMove(Constant fromOpr, TraceInterval toInterval) {
	assert insertIdx != -1 : "must setup insert position first";

	AllocatableValue toOpr = toInterval.operand;
	LIRInstruction move = getAllocator().getSpillMoveFactory().createLoad(toOpr, fromOpr);
	insertionBuffer.append(insertIdx, move);

	if (Debug.isLogEnabled()) {
	Debug.log("insert move from value %s to %s at %d", fromOpr, toInterval, insertIdx);
	}
	}

	@SuppressWarnings("try")
	private void resolveMappings() {
	try (Indent indent = Debug.logAndIndent("resolveMapping")) {
	assert verifyBeforeResolve();
	if (Debug.isLogEnabled()) {
	printMapping();
	}

	// Block all registers that are used as input operands of a move.
	// When a register is blocked, no move to this register is emitted.
	// This is necessary for detecting cycles in moves.
	int i;
	for (i = mappingFrom.size() - 1; i >= 0; i--) {
	TraceInterval fromInterval = mappingFrom.get(i);
	if (fromInterval != null) {
	blockRegisters(fromInterval);
	}
	}

	ArrayList<AllocatableValue> busySpillSlots = null;
	while (mappingFrom.size() > 0) {
	boolean processedInterval = false;

	int spillCandidate = -1;
	for (i = mappingFrom.size() - 1; i >= 0; i--) {
	TraceInterval fromInterval = mappingFrom.get(i);
	TraceInterval toInterval = mappingTo.get(i);

	if (safeToProcessMove(fromInterval, toInterval)) {
	// this interval can be processed because target is free
	if (fromInterval != null) {
	insertMove(fromInterval, toInterval);
	unblockRegisters(fromInterval);
	} else {
	insertMove(mappingFromOpr.get(i), toInterval);
	}
	if (isStackSlotValue(toInterval.location())) {
	if (busySpillSlots == null) {
	busySpillSlots = new ArrayList<>(2);
	}
	busySpillSlots.add(toInterval.location());
	}
	mappingFrom.remove(i);
	mappingFromOpr.remove(i);
	mappingTo.remove(i);

	processedInterval = true;
	} else if (fromInterval != null && isRegister(fromInterval.location()) && (busySpillSlots == null \|\| !busySpillSlots.contains(fromInterval.spillSlot()))) {
	// this interval cannot be processed now because target is not free
	// it starts in a register, so it is a possible candidate for spilling
	spillCandidate = i;
	}
	}

	if (!processedInterval) {
	breakCycle(spillCandidate);
	}
	}
	}

	// check that all intervals have been processed
	assert checkEmpty();
	}

	protected void breakCycle(int spillCandidate) {
	if (spillCandidate != -1) {
	// no move could be processed because there is a cycle in the move list
	// (e.g. r1 . r2, r2 . r1), so one interval must be spilled to memory
	assert spillCandidate != -1 : "no interval in register for spilling found";

	// create a new spill interval and assign a stack slot to it
	TraceInterval fromInterval1 = mappingFrom.get(spillCandidate);
	// do not allocate a new spill slot for temporary interval, but
	// use spill slot assigned to fromInterval. Otherwise moves from
	// one stack slot to another can happen (not allowed by LIRAssembler
	AllocatableValue spillSlot1 = fromInterval1.spillSlot();
	if (spillSlot1 == null) {
	spillSlot1 = getAllocator().getFrameMapBuilder().allocateSpillSlot(fromInterval1.kind());
	fromInterval1.setSpillSlot(spillSlot1);
	cycleBreakingSlotsAllocated.increment();
	}
	spillInterval(spillCandidate, fromInterval1, spillSlot1);
	return;
	}
	assert mappingFromSize() > 1;
	// Arbitrarily select the first entry for spilling.
	int stackSpillCandidate = 0;
	TraceInterval fromInterval = getMappingFrom(stackSpillCandidate);
	// allocate new stack slot
	VirtualStackSlot spillSlot = getAllocator().getFrameMapBuilder().allocateSpillSlot(fromInterval.kind());
	spillInterval(stackSpillCandidate, fromInterval, spillSlot);
	}

	protected void spillInterval(int spillCandidate, TraceInterval fromInterval, AllocatableValue spillSlot) {
	assert mappingFrom.get(spillCandidate).equals(fromInterval);
	TraceInterval spillInterval = getAllocator().createDerivedInterval(fromInterval);

	// add a dummy range because real position is difficult to calculate
	// Note: this range is a special case when the integrity of the allocation is
	// checked
	spillInterval.addRange(1, 2);

	spillInterval.assignLocation(spillSlot);

	if (Debug.isLogEnabled()) {
	Debug.log("created new Interval for spilling: %s", spillInterval);
	}
	blockRegisters(spillInterval);

	// insert a move from register to stack and update the mapping
	insertMove(fromInterval, spillInterval);
	mappingFrom.set(spillCandidate, spillInterval);
	unblockRegisters(fromInterval);
	}

	@SuppressWarnings("try")
	private void printMapping() {
	try (Indent indent = Debug.logAndIndent("Mapping")) {
	for (int i = mappingFrom.size() - 1; i >= 0; i--) {
	TraceInterval fromInterval = mappingFrom.get(i);
	TraceInterval toInterval = mappingTo.get(i);
	String from;
	Value to = toInterval.location();
	if (fromInterval == null) {
	from = mappingFromOpr.get(i).toString();
	} else {
	from = fromInterval.location().toString();
	}
	Debug.log("move %s <- %s", from, to);
	}
	}
	}

	void setInsertPosition(List<LIRInstruction> insertList, int insertIdx) {
	assert this.insertIdx == -1 : "use moveInsertPosition instead of setInsertPosition when data already set";

	createInsertionBuffer(insertList);
	this.insertIdx = insertIdx;
	}

	void moveInsertPosition(List<LIRInstruction> newInsertList, int newInsertIdx) {
	if (insertionBuffer.lirList() != null && (insertionBuffer.lirList() != newInsertList \|\| this.insertIdx != newInsertIdx)) {
	// insert position changed . resolve current mappings
	resolveMappings();
	}

	assert insertionBuffer.lirList() != newInsertList \|\| newInsertIdx >= insertIdx : String.format("Decreasing insert index: old=%d new=%d", insertIdx, newInsertIdx);

	if (insertionBuffer.lirList() != newInsertList) {
	// block changed . append insertionBuffer because it is
	// bound to a specific block and create a new insertionBuffer
	appendInsertionBuffer();
	createInsertionBuffer(newInsertList);
	}

	this.insertIdx = newInsertIdx;
	}

	public void addMapping(TraceInterval fromInterval, TraceInterval toInterval) {

	if (isIllegal(toInterval.location()) && toInterval.canMaterialize()) {
	if (Debug.isLogEnabled()) {
	Debug.log("no store to rematerializable interval %s needed", toInterval);
	}
	return;
	}
	if (isIllegal(fromInterval.location()) && fromInterval.canMaterialize()) {
	// Instead of a reload, re-materialize the value
	JavaConstant rematValue = fromInterval.getMaterializedValue();
	addMapping(rematValue, toInterval);
	return;
	}
	if (Debug.isLogEnabled()) {
	Debug.log("add move mapping from %s to %s", fromInterval, toInterval);
	}

	assert !fromInterval.operand.equals(toInterval.operand) : "from and to interval equal: " + fromInterval;
	assert LIRKind.verifyMoveKinds(toInterval.kind(), fromInterval.kind()) : String.format("Kind mismatch: %s vs. %s, from=%s, to=%s", fromInterval.kind(), toInterval.kind(), fromInterval,
	toInterval);
	mappingFrom.add(fromInterval);
	mappingFromOpr.add(null);
	mappingTo.add(toInterval);
	}

	public void addMapping(Constant fromOpr, TraceInterval toInterval) {
	if (Debug.isLogEnabled()) {
	Debug.log("add move mapping from %s to %s", fromOpr, toInterval);
	}

	mappingFrom.add(null);
	mappingFromOpr.add(fromOpr);
	mappingTo.add(toInterval);
	}

	void resolveAndAppendMoves() {
	if (hasMappings()) {
	resolveMappings();
	}
	appendInsertionBuffer();
	}
	}