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.lsra;
24
25 import static jdk.vm.ci.code.ValueUtil.asRegister;
26 import static jdk.vm.ci.code.ValueUtil.isIllegal;
27 import static jdk.vm.ci.code.ValueUtil.isRegister;
28 import static jdk.vm.ci.code.ValueUtil.isStackSlot;
29 import static org.graalvm.compiler.core.common.GraalOptions.DetailedAsserts;
30 import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;
31 import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
32 import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot;
33
34 import java.util.ArrayList;
35 import java.util.Arrays;
36 import java.util.Collections;
37 import java.util.EnumSet;
38 import java.util.List;
39
40 import org.graalvm.compiler.core.common.LIRKind;
41 import org.graalvm.compiler.core.common.util.Util;
42 import org.graalvm.compiler.debug.GraalError;
43 import org.graalvm.compiler.lir.LIRInstruction;
44 import org.graalvm.compiler.lir.Variable;
45 import org.graalvm.compiler.lir.alloc.trace.lsra.TraceLinearScanPhase.TraceLinearScan;
46 import org.graalvm.compiler.options.OptionValues;
47
48 import jdk.vm.ci.code.RegisterValue;
49 import jdk.vm.ci.code.StackSlot;
50 import jdk.vm.ci.meta.AllocatableValue;
51 import jdk.vm.ci.meta.JavaConstant;
52 import jdk.vm.ci.meta.Value;
53 import jdk.vm.ci.meta.ValueKind;
54
55 /**
56 * Represents an interval in the {@linkplain TraceLinearScan linear scan register allocator}.
57 */
58 final class TraceInterval extends IntervalHint {
59
60 /**
61 * Constants denoting the register usage priority for an interval. The constants are declared in
705
706 int previousUsage(RegisterPriority minRegisterPriority, int from) {
707 int prev = -1;
708 for (int i = numUsePos() - 1; i >= 0; --i) {
709 int usePos = getUsePos(i);
710 if (usePos > from) {
711 return prev;
712 }
713 if (adaptPriority(getUsePosRegisterPriority(i)).greaterEqual(minRegisterPriority)) {
714 prev = usePos;
715 }
716 }
717 return prev;
718 }
719
720 public void addUsePos(int pos, RegisterPriority registerPriority, OptionValues options) {
721 assert isEmpty() || covers(pos, LIRInstruction.OperandMode.USE) : String.format("use position %d not covered by live range of interval %s", pos, this);
722
723 // do not add use positions for precolored intervals because they are never used
724 if (registerPriority != RegisterPriority.None) {
725 if (DetailedAsserts.getValue(options)) {
726 for (int i = 0; i < numUsePos(); i++) {
727 assert pos <= getUsePos(i) : "already added a use-position with lower position";
728 if (i > 0) {
729 assert getUsePos(i) < getUsePos(i - 1) : "not sorted descending";
730 }
731 }
732 }
733
734 // Note: addUse is called in descending order, so list gets sorted
735 // automatically by just appending new use positions
736 int len = numUsePos();
737 if (len == 0 || getUsePos(len - 1) > pos) {
738 usePosAdd(pos, registerPriority);
739 } else if (getUsePosRegisterPriority(len - 1).lessThan(registerPriority)) {
740 assert getUsePos(len - 1) == pos : "list not sorted correctly";
741 setUsePosRegisterPriority(len - 1, registerPriority);
742 }
743 }
744 }
745
785 * parent. That is, there is no tree of split children stored, just a flat list. All split
786 * children are spilled to the same {@linkplain #spillSlot spill slot}.
787 *
788 * @param splitPos the position at which to split this interval
789 * @param allocator the register allocator context
790 * @return the child interval split off from this interval
791 */
792 TraceInterval split(int splitPos, TraceLinearScan allocator) {
793
794 // allocate new interval
795 TraceInterval result = newSplitChild(allocator);
796
797 // split the ranges
798 result.setTo(intTo);
799 result.setFrom(splitPos);
800 intTo = splitPos;
801
802 // split list of use positions
803 splitUsePosAt(result, splitPos);
804
805 if (DetailedAsserts.getValue(allocator.getOptions())) {
806 for (int i = 0; i < numUsePos(); i++) {
807 assert getUsePos(i) < splitPos;
808 }
809 for (int i = 0; i < result.numUsePos(); i++) {
810 assert result.getUsePos(i) >= splitPos;
811 }
812 }
813 return result;
814 }
815
816 // returns true if the opId is inside the interval
817 boolean covers(int opId, LIRInstruction.OperandMode mode) {
818 if (mode == LIRInstruction.OperandMode.DEF) {
819 return from() <= opId && opId < to();
820 }
821 return from() <= opId && opId <= to();
822 }
823
824 @Override
825 public String toString() {
|
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.lsra;
24
25 import static jdk.vm.ci.code.ValueUtil.asRegister;
26 import static jdk.vm.ci.code.ValueUtil.isIllegal;
27 import static jdk.vm.ci.code.ValueUtil.isRegister;
28 import static jdk.vm.ci.code.ValueUtil.isStackSlot;
29 import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;
30 import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
31 import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot;
32
33 import java.util.ArrayList;
34 import java.util.Arrays;
35 import java.util.Collections;
36 import java.util.EnumSet;
37 import java.util.List;
38
39 import org.graalvm.compiler.core.common.LIRKind;
40 import org.graalvm.compiler.core.common.util.Util;
41 import org.graalvm.compiler.debug.Assertions;
42 import org.graalvm.compiler.debug.GraalError;
43 import org.graalvm.compiler.lir.LIRInstruction;
44 import org.graalvm.compiler.lir.Variable;
45 import org.graalvm.compiler.lir.alloc.trace.lsra.TraceLinearScanPhase.TraceLinearScan;
46 import org.graalvm.compiler.options.OptionValues;
47
48 import jdk.vm.ci.code.RegisterValue;
49 import jdk.vm.ci.code.StackSlot;
50 import jdk.vm.ci.meta.AllocatableValue;
51 import jdk.vm.ci.meta.JavaConstant;
52 import jdk.vm.ci.meta.Value;
53 import jdk.vm.ci.meta.ValueKind;
54
55 /**
56 * Represents an interval in the {@linkplain TraceLinearScan linear scan register allocator}.
57 */
58 final class TraceInterval extends IntervalHint {
59
60 /**
61 * Constants denoting the register usage priority for an interval. The constants are declared in
705
706 int previousUsage(RegisterPriority minRegisterPriority, int from) {
707 int prev = -1;
708 for (int i = numUsePos() - 1; i >= 0; --i) {
709 int usePos = getUsePos(i);
710 if (usePos > from) {
711 return prev;
712 }
713 if (adaptPriority(getUsePosRegisterPriority(i)).greaterEqual(minRegisterPriority)) {
714 prev = usePos;
715 }
716 }
717 return prev;
718 }
719
720 public void addUsePos(int pos, RegisterPriority registerPriority, OptionValues options) {
721 assert isEmpty() || covers(pos, LIRInstruction.OperandMode.USE) : String.format("use position %d not covered by live range of interval %s", pos, this);
722
723 // do not add use positions for precolored intervals because they are never used
724 if (registerPriority != RegisterPriority.None) {
725 if (Assertions.detailedAssertionsEnabled(options)) {
726 for (int i = 0; i < numUsePos(); i++) {
727 assert pos <= getUsePos(i) : "already added a use-position with lower position";
728 if (i > 0) {
729 assert getUsePos(i) < getUsePos(i - 1) : "not sorted descending";
730 }
731 }
732 }
733
734 // Note: addUse is called in descending order, so list gets sorted
735 // automatically by just appending new use positions
736 int len = numUsePos();
737 if (len == 0 || getUsePos(len - 1) > pos) {
738 usePosAdd(pos, registerPriority);
739 } else if (getUsePosRegisterPriority(len - 1).lessThan(registerPriority)) {
740 assert getUsePos(len - 1) == pos : "list not sorted correctly";
741 setUsePosRegisterPriority(len - 1, registerPriority);
742 }
743 }
744 }
745
785 * parent. That is, there is no tree of split children stored, just a flat list. All split
786 * children are spilled to the same {@linkplain #spillSlot spill slot}.
787 *
788 * @param splitPos the position at which to split this interval
789 * @param allocator the register allocator context
790 * @return the child interval split off from this interval
791 */
792 TraceInterval split(int splitPos, TraceLinearScan allocator) {
793
794 // allocate new interval
795 TraceInterval result = newSplitChild(allocator);
796
797 // split the ranges
798 result.setTo(intTo);
799 result.setFrom(splitPos);
800 intTo = splitPos;
801
802 // split list of use positions
803 splitUsePosAt(result, splitPos);
804
805 if (Assertions.detailedAssertionsEnabled(allocator.getOptions())) {
806 for (int i = 0; i < numUsePos(); i++) {
807 assert getUsePos(i) < splitPos;
808 }
809 for (int i = 0; i < result.numUsePos(); i++) {
810 assert result.getUsePos(i) >= splitPos;
811 }
812 }
813 return result;
814 }
815
816 // returns true if the opId is inside the interval
817 boolean covers(int opId, LIRInstruction.OperandMode mode) {
818 if (mode == LIRInstruction.OperandMode.DEF) {
819 return from() <= opId && opId < to();
820 }
821 return from() <= opId && opId <= to();
822 }
823
824 @Override
825 public String toString() {
|