001 /*
002 * This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 * This file is licensed to You under the Eclipse Public License (EPL);
005 * You may not use this file except in compliance with the License. You
006 * may obtain a copy of the License at
007 *
008 * http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 * See the COPYRIGHT.txt file distributed with this work for information
011 * regarding copyright ownership.
012 */
013 package org.jikesrvm.compilers.opt.instrsched;
014
015 import org.jikesrvm.compilers.opt.ir.Instruction;
016
017 /**
018 * Resource usage map representation
019 * Used by the scheduler to accommodate resource patterns
020 *
021 * @see OperatorClass
022 * @see org.jikesrvm.compilers.opt.ir.Operator
023 */
024 final class ResourceMap {
025 private static final int VERBOSE = 0;
026
027 private static void debug(String s) {
028 System.out.println(s);
029 }
030
031 private static String toBinaryPad32(int value) {
032 String s = Integer.toBinaryString(value);
033 return String.format("%032s", s);
034 }
035
036 /** GROWABLE Resource Usage map. */
037 private int[] rumap;
038 /** Current size of the RU map. */
039 private int size;
040
041 /** Grows the RU map to a given size. For internal use only. */
042 private void grow(int s) {
043 if (VERBOSE >= 2) {
044 debug("Growing from " + size + " to " + s);
045 }
046 if (size >= s) {
047 return;
048 }
049 int len = rumap.length;
050 if (len < s) {
051 for (; len < s; len <<= 1) ;
052 int[] t = new int[len];
053 for (int i = 0; i < rumap.length; i++) {
054 t[i] = rumap[i];
055 }
056 for (int i = rumap.length; i < len; i++) {
057 t[i] = OperatorClass.NONE;
058 }
059 rumap = t;
060 }
061 size = s;
062 }
063
064 /**
065 * Creates new resource map.
066 */
067 public ResourceMap() {
068 this(4);
069 }
070
071 /**
072 * Creates new resource map with desired initial length.
073 *
074 * @param length desired initial length of the resource map
075 */
076 public ResourceMap(int length) {
077 rumap = new int[length];
078 size = 0;
079 for (int i = 0; i < length; i++) {
080 rumap[i] = OperatorClass.NONE;
081 }
082 }
083
084 /**
085 * Reserves resources for given instruction at given time.
086 *
087 * @param i instruction
088 * @param time time to schedule
089 * @return true if succeeded, false if there was a conflict
090 * @see #unschedule(Instruction)
091 */
092 public boolean schedule(Instruction i, int time) {
093 if (SchedulingInfo.isScheduled(i)) {
094 throw new InternalError("Already scheduled");
095 }
096 OperatorClass opc = i.operator().getOpClass();
097 if (VERBOSE >= 2) {
098 debug("Op Class=" + opc);
099 }
100 for (int alt = 0; alt < opc.masks.length; alt++) {
101 int[] ru = opc.masks[alt];
102 if (schedule(ru, time)) {
103 SchedulingInfo.setInfo(i, alt, time);
104 return true;
105 }
106 }
107 return false;
108 }
109
110 /**
111 * Frees resources for given instruction.
112 *
113 * @param i instruction
114 * @see #schedule(Instruction,int)
115 */
116 public void unschedule(Instruction i) {
117 if (!SchedulingInfo.isScheduled(i)) {
118 throw new InternalError("Not scheduled");
119 }
120 OperatorClass opc = i.operator().getOpClass();
121 int[] ru = opc.masks[SchedulingInfo.getAlt(i)];
122 unschedule(ru, SchedulingInfo.getTime(i));
123 SchedulingInfo.resetInfo(i);
124 }
125
126 /**
127 * Returns a string representation of the resource map.
128 *
129 * @return a string representation of the resource map
130 */
131 @Override
132 public String toString() {
133 StringBuilder sb = new StringBuilder();
134 for (int i = 0; i < size; i++) {
135 sb.append(toBinaryPad32(rumap[i])).append("\n");
136 }
137 return sb.toString();
138 }
139
140 //
141 // Returns false if there is a resource conflict.
142
143
144 /**
145 * Binds resources for given resource usage pattern at given time.
146 * @param usage
147 * @param time
148 * @return {@code false} if there's a resource conflict, {@code true}
149 * otherwise
150 */
151 private boolean schedule(int[] usage, int time) {
152 grow(time + usage.length);
153 if (VERBOSE >= 1) {
154 debug("Pattern (" + usage.length + ")");
155 for (int anUsage : usage) debug(" " + toBinaryPad32(anUsage));
156 debug("");
157 }
158 for (int i = 0; i < usage.length; i++) {
159 if ((usage[i] & rumap[time + i]) != 0) {
160 return false;
161 }
162 }
163 for (int i = 0; i < usage.length; i++) {
164 rumap[time + i] |= usage[i];
165 }
166 return true;
167 }
168
169 /**
170 * Unbinds resources for given resource usage pattern at given time.
171 * @param usage
172 * @param time
173 */
174 private void unschedule(int[] usage, int time) {
175 for (int i = 0; i < usage.length; i++) {
176 rumap[time + i] &= ~usage[i];
177 }
178 }
179 }
180
181
182