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 //OperatorClass.java
014 package org.jikesrvm.compilers.opt.instrsched;
015
016 import org.jikesrvm.*;
017 import org.jikesrvm.compilers.opt.ir.*;
018 import java.util.ArrayList;
019
020 /**
021 * Generated from a template.
022 * Consists of an operator class and information about resource usage
023 * There is only one instance of each OperatorClass, which is stored
024 * as a static final field in OperatorClass. You can compare
025 * OperatorClasses using ==.
026 * Every Operator contains one of these.
027 *
028 * @see Operator
029 * @see Operators
030 */
031 public final class OperatorClass implements Operators {
032
033 // debug level (0 = no debug)
034 private static final int verbose = 0;
035
036 private static void debug(String s) {
037 System.err.println(s);
038 }
039 private static String SPACES = null;
040 private static void debug(int depth, String s) {
041 if (SPACES == null) SPACES = dup(7200, ' ');
042 debug(SPACES.substring(0,depth*2)+s);
043 }
044
045 // Padding
046 // For internal use only.
047 private static final String ZEROS = dup(32, '0');
048 private static String toBinaryPad32(int value) {
049 String s = Integer.toBinaryString(value);
050 return ZEROS.substring(s.length())+s;
051 }
052
053 // Returns a special resource type embodying all resources of a given class.
054 // For internal use only.
055 private static int all_units(int rclass) { return rclass | 0x80000000; }
056
057 /**
058 * Empty Resources Mask
059 */
060 static int NONE = 0;
061
062 /**
063 * All Resources Mask
064 */
065 static int ALL = 0; // will be filled in
066
067 // Generates an array of resource masks, and updating the static field
068 // ALL to contain all of the masks.
069 // For internal use only.
070 private static int M = 1; // current mask
071 private static int[] genMasks(int number) {
072 int[] rs = new int[number + 1];
073 int rall = 0;
074 for (int i = 0; i < number; i++) {
075 if (VM.VerifyAssertions && M == 0)
076 throw new InternalError("Exceeded 32 resources");
077 //System.err.println("Scheduler: Resource "+M);
078 rs[i] = M;
079 ALL |= M;
080 rall |= M;
081 M <<= 1;
082 }
083 rs[number] = rall;
084 return rs;
085 }
086
087 /**
088 * Resource Masks
089 */
090 private static final int[][] resources = {
091 null
092 };
093
094 /**
095 * Total number of resources
096 */
097 static final int N = resources.length - 1;
098
099 /**
100 * Resource Names
101 */
102 private static final String[] resource_names = {
103 null
104 };
105
106 /**
107 * Resources
108 */
109
110
111 /**
112 * Id of the operator class
113 */
114 private int id = 0;
115
116 /**
117 * Maximum Latency of any instruction
118 */
119 private int maxlat = 0;
120
121 /**
122 * Returns the maximum latency of any instruction in the class.
123 * Note: it is faster to simply check the field directly, if possible.
124 */
125 public int maxLatency() { return maxlat; }
126
127 /**
128 * Latencies to other classes
129 */
130 private final ArrayList<Integer> latencies;
131
132 // Returns latency lookup in the hashtable for a given operator class.
133 // For internal use only.
134 private Object latObj(OperatorClass opclass) {
135 int latsize = latencies.size();
136 Object latObj = null;
137 if (latsize > opclass.id) latObj = latencies.get(opclass.id);
138
139 // walk through backwards, since any_insn (most general) is first
140 ArrayList<OperatorClass> opcrc = opclass.rclasses;
141 for (int i = opcrc.size(); latObj == null && i > 0; i--) {
142 OperatorClass rc = opcrc.get(i - 1);
143 if (latsize > rc.id) latObj = latencies.get(rc.id);
144 }
145
146 for (int i = rclasses.size(); latObj == null && i > 0; i--) {
147 OperatorClass rc = rclasses.get(i - 1);
148 latObj = rc.latObj(opclass);
149 }
150
151 return latObj;
152 }
153
154 /**
155 * Sets the operator class (for hierarchy)
156 *
157 * @param opClass operator class
158 */
159 public void setOpClass(OperatorClass opClass) {
160 rclasses.add(opClass);
161 }
162
163 /**
164 * Returns the latency between instructions in this class and given class
165 *
166 * @param opclass destination operator class
167 * @return latency to given operator class
168 */
169 public int latency(OperatorClass opclass) {
170 return (Integer) latObj(opclass);
171 }
172
173 /**
174 * Sets the latency between instructions in this class and given class
175 *
176 * @param opclass destination operator class
177 * @param latency desired latency
178 */
179 public void setLatency(OperatorClass opclass, int latency) {
180 int latencies_size = latencies.size();
181 if (opclass.id < latencies_size) {
182 latencies.set(opclass.id, latency);
183 }
184 else {
185 for(; latencies_size < opclass.id; latencies_size++) {
186 latencies.add(null);
187 }
188 latencies.add(latency);
189 }
190 }
191 /**
192 * Sets the latency between instructions in given class and this class
193 *
194 * @param opclass source operator class
195 * @param latency desired latency
196 */
197 public void setRevLatency(OperatorClass opclass, int latency) {
198 opclass.setLatency(this, latency);
199 }
200
201 /*
202 * Operator Classes
203 */
204
205 // Global class embodying all operator classes. For internal use only.
206 private static final OperatorClass any_insn = new OperatorClass(0);
207
208
209 /**
210 * Map from resource to operator class representing that resource
211 */
212 private static OperatorClass[] res2class = {
213 null
214 };
215
216 private static final OperatorClass
217 pseudo_ops = new OperatorClass(
218 0+N+1,
219 new ResourceReservation[] {
220 }
221 );
222 static {
223 LABEL.setOpClass(pseudo_ops);
224 BBEND.setOpClass(pseudo_ops);
225 UNINT_BEGIN.setOpClass(pseudo_ops);
226 UNINT_END.setOpClass(pseudo_ops);
227
228
229 pseudo_ops.setLatency(any_insn, 0);
230
231 }
232
233 /**
234 * Resource Classes used by this Operator Class
235 */
236 final ArrayList<OperatorClass> rclasses;
237
238 /**
239 * Resource Usage Masks
240 */
241 int[][] masks;
242
243 // For internal use only.
244 private OperatorClass(int _id) {
245 id = _id;
246 rclasses = new ArrayList<OperatorClass>();
247 latencies = new ArrayList<Integer>();
248 }
249
250 // For internal use only.
251 private OperatorClass(int _id, ResourceReservation[] pat) {
252 this(_id);
253 allocateMasks(pat);
254 if (verbose >= 2) debug(masks.length+" masks allocated for "+pat.length+
255 " requests");
256 int[] assign = new int[pat.length];
257 int comb = fillMasks(pat, assign, 0, 0, 0);
258 if (false && comb != masks.length)
259 throw new InternalError("Insufficient Resources");
260 }
261
262 /**
263 * Returns the string representation of this operator class.
264 */
265 @Override
266 public String toString() {
267 StringBuffer sb = new StringBuffer("Size=");
268 sb.append(masks.length).append('\n');
269 for (int[] mask : masks) {
270 for (int v : mask)
271 sb.append(toBinaryPad32(v)).append('\n');
272 sb.append('\n');
273 }
274 return sb.toString();
275 }
276
277 // For internal use only.
278 private void allocateMasks(ResourceReservation[] pat) {
279 ResourceReservation.sort(pat);
280 int maxlen = 0;
281 int size = 1;
282 ResourceReservation r = new ResourceReservation(-1, -1, -1000);
283 int len = -1;
284 OperatorClass[] rss = new OperatorClass[N];
285 for (ResourceReservation p : pat) {
286 rss[p.rclass()] = res2class[p.rclass()];
287 boolean same = p.equals(r);
288 if (!p.conflicts(r)) {
289 r = p;
290 if (r.isGlobal())
291 len = 1;
292 else
293 len = resources[r.rclass()].length - 1;
294 } else if (r.isGlobal()) {
295 throw new InternalError("Insufficient Resources");
296 } else {
297 len--;
298 }
299 size *= len;
300 if (same)
301 size /= 2;
302 if (p.start + p.duration > maxlen)
303 maxlen = p.start + p.duration;
304 }
305 rclasses.add(any_insn);
306 for (int i = 0; i < N; i++)
307 if (rss[i] != null)
308 rclasses.add(rss[i]);
309 masks = new int[size][];
310 for (int i = 0; i < size; i++)
311 masks[i] = new int[maxlen];
312 }
313
314 // For internal debug use only.
315 static int depth = 0;
316
317 // For internal use only.
318 private int fillMasks(ResourceReservation[] pat, int[] assign,
319 int all, int rrq, int comb) {
320 if (rrq == pat.length) {
321 for (int i = 0; i < masks[comb].length; i++)
322 masks[comb][i] = 0;
323 StringBuffer dbSB;
324 if (verbose >= 1) dbSB = new StringBuffer();
325 for (int i = 0; i < pat.length; i++) {
326 ResourceReservation pi = pat[i];
327 int rc = pi.rclass();
328 int mask = resources[rc][assign[i]];
329 if (verbose >= 1) dbSB.append(toBinaryPad32(mask)).append(" ");
330 for (int j = 0; j < pi.duration; j++)
331 masks[comb][pi.start + j] |= mask;
332 if (maxlat < pi.duration)
333 maxlat = pi.duration;
334 }
335 if (verbose >= 1) debug(dbSB.toString());
336 return comb + 1;
337 }
338 int rc = pat[rrq].rclass();
339 int start = 0;
340 int end = resources[rc].length - 1;
341 if (rrq != 0 && pat[rrq].equals(pat[rrq-1]))
342 start = assign[rrq-1] + 1;
343 boolean ignore = ((rrq != 0 && !pat[rrq].conflicts(pat[rrq-1])) ||
344 pat[rrq].isGlobal());
345 if (pat[rrq].isGlobal()) {
346 start = end;
347 end++;
348 }
349
350 for (int i = start; i < end; i++)
351 if (ignore || (resources[rc][i] & all) == 0) {
352 if (verbose >= 2) debug(depth, rrq+": Res#"+rc+"; Trying "+i+
353 "; reserved='"+toBinaryPad32(all)+"'");
354
355 depth++;
356 assign[rrq] = i;
357 comb = fillMasks(pat, assign, all | resources[rc][i], rrq+1, comb);
358 depth--;
359 }
360
361 return comb;
362 }
363
364 // Generates a string of a given length filled by a given character.
365 // For internal use only.
366 private static String dup(int len, char c) {
367 StringBuffer sb = new StringBuffer();
368 for (int i = 0; i < len; i++)
369 sb.append(c);
370 return sb.toString();
371 }
372 }