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.runtimesupport;
014
015 import java.util.List;
016 import org.jikesrvm.ArchitectureSpecificOpt.OptGCMapIteratorConstants;
017 import org.jikesrvm.VM;
018 import org.jikesrvm.compilers.opt.ir.GCIRMapElement;
019 import org.jikesrvm.compilers.opt.ir.RegSpillListElement;
020 import org.vmmagic.pragma.Interruptible;
021 import org.vmmagic.pragma.Uninterruptible;
022
023 /**
024 * A class that encapsulates the GCMap portion of the machine code maps.
025 * An instance of this class is created to encode and instance of a
026 * GCIRMap into an int[]. The int[] is stored persistently,
027 * but the instance of the OptGCMap is NOT.
028 *
029 * <ul>
030 * <li> each map will be a sequence of 1 or more ints
031 * <li> the first int in each map is a bit map of registers that
032 * contain references (the MSB is used for chaining,
033 * we assume it will never contain a reference)
034 * <li> the remaining ints will be spill locations
035 * <li> the sequence will continue as long as the most significant bit
036 * is set to 1
037 * </ul>
038 *
039 * Note: This file contains two types of methods
040 * 1) methods called during compilation to create the GC maps
041 * these methods are virtual
042 * 2) methods called at GC time (no allocation allowed!)
043 * these methods are static
044 */
045 @Uninterruptible
046 public final class OptGCMap implements OptGCMapIteratorConstants {
047 public static final int NO_MAP_ENTRY = -1;
048 public static final int ERROR = -2;
049
050 /**
051 * The initial allocation size for a map
052 */
053 public static final int INITIAL_MAP_SIZE = 16;
054
055 /**
056 * bit pattern for the "next" bit in the GC maps array
057 */
058 private static final int NEXT_BIT = 0x80000000;
059
060 /**
061 * the index of the last map entry in use
062 */
063 private int lastGCMapEntry;
064
065 /**
066 * The gc map array, a sequence of gc maps. Each sequence starts
067 * with a register bit mask and is followed by a list of spills.
068 * The most significant bit of the spill location is used to chain
069 * the list.
070 */
071 private int[] gcMapInformation;
072
073 public static final boolean DEBUG = false;
074
075 /**
076 * Constructor, called during compilation
077 */
078 OptGCMap() {
079 lastGCMapEntry = -1;
080 gcMapInformation = new int[INITIAL_MAP_SIZE]; // initial map size
081 }
082
083 /**
084 * Called to complete the encoding and return the final int[]
085 */
086 @Interruptible
087 public int[] finish() {
088 if ((gcMapInformation != null) && (lastGCMapEntry < gcMapInformation.length - 1)) {
089 resizeMapInformation(lastGCMapEntry + 1);
090 }
091 return gcMapInformation;
092 }
093
094 /**
095 * Construct the GCMap for the argument GCIRMapElement
096 * @param irMapElem The IR Map element to create a GCMap for
097 * @return the GCMap index.
098 */
099 @Interruptible
100 public int generateGCMapEntry(GCIRMapElement irMapElem) {
101 // the index into the GC maps we will use for this instruction.
102 int mapIndex = NO_MAP_ENTRY;
103
104 // Before requesting the (first) map entry, lets make sure we
105 // will need it. If the reg/spill list is empty, we don't
106 // need a map slot, i.e., no references are live at this instruction
107 List<RegSpillListElement> regSpillList = irMapElem.regSpillList();
108 if (!regSpillList.isEmpty()) {
109
110 // For efficiency we create our own bit map and then set the
111 // appropriate array value
112 int bitMap = 0;
113 // count the spills so we know how big of an array we'll need
114 int numSpills = 0;
115 int numRegs = 0;
116
117 // Because the output data structure (the map) stores register
118 // information before spills, we need to traverse the list twice
119 // the first time we get the register mask, the 2nd time we get
120 // the spills
121 // process the register
122 for (RegSpillListElement elem : regSpillList) {
123 if (elem.isSpill()) {
124 numSpills++;
125 } else {
126 numRegs++;
127 int realRegNumber = elem.getRealRegNumber();
128
129 if (VM.VerifyAssertions && realRegNumber > LAST_GCMAP_REG) {
130 System.out.println(elem);
131 System.out.println(LAST_GCMAP_REG);
132 VM._assert(false, "reg > last GC Map Reg!!");
133 }
134
135 // get the bit position for this register number
136 int bitPosition = getRegBitPosition(realRegNumber);
137
138 // Set the appropriate bit
139 bitMap = bitMap | (NEXT_BIT >>> bitPosition);
140 }
141 }
142
143 // get the next free Map entry
144 int index = setRegisterBitMap(bitMap);
145
146 int[] spillArray = new int[numSpills];
147 int spillIndex = 0;
148 // Now we need to walk the list again to process the spills.
149 // first, get a fresh enumerator
150 for (RegSpillListElement elem : regSpillList) {
151 if (elem.isSpill()) {
152 spillArray[spillIndex++] = elem.getSpill();
153 }
154 }
155
156 // add the spills into the map
157 addAllSpills(spillArray);
158
159 // don't forget to report that there are no more spills
160 mapIndex = endCurrentMap(index);
161
162 }
163 return mapIndex;
164 }
165
166 ////////////////////////////////////////////
167 // Methods called at GC time
168 ////////////////////////////////////////////
169 /**
170 * Returns the GC map information for the GC map information entry passed
171 * @param entry map entry
172 * @param gcMap the gc map
173 */
174 public static int gcMapInformation(int entry, int[] gcMap) {
175 // before returning remember to clear the MSB.
176 return gcMap[entry] & ~NEXT_BIT;
177 }
178
179 /**
180 * Determines if the register map information for the entry passed is true
181 * @param entry map entry
182 * @param registerNumber the register number
183 * @param gcMap the encoded GCMap
184 */
185 public static boolean registerIsSet(int entry, int registerNumber, int[] gcMap) {
186 if (VM.VerifyAssertions) {
187 VM._assert(registerNumber >= FIRST_GCMAP_REG && registerNumber <= LAST_GCMAP_REG, "Bad registerNumber");
188 }
189
190 // Get the bit position for the register number
191 int bitPosition = getRegBitPosition(registerNumber);
192
193 // Using the register number passed construct the appropriate bit string,
194 // "and" it with the value, and see if we get a positive value
195 return (gcMap[entry] & (NEXT_BIT >>> bitPosition)) > 0;
196 }
197
198 /**
199 * @param gcMap the encoded GCMap
200 * @return the next (relative) location or -1 for no more locations
201 */
202 public static int nextLocation(int currentIndex, int[] gcMap) {
203 // Does the next entry contain anything useful?
204 if (nextBitSet(currentIndex, gcMap)) {
205 // if so, return the next index
206 return currentIndex + 1;
207 } else {
208 return -1;
209 }
210 }
211
212 /**
213 * This method maps a register number to its bit position
214 * @param registerNumber the register number of interest
215 */
216 private static int getRegBitPosition(int registerNumber) {
217 // Because we can't use bit position 0 (that is the next bit), we
218 // adjust depending on the value of FIRST_GCMAP_REG
219 //
220 // For example,
221 // FIRST_GCMAP_REG = 1 => registerNumber = 1 (PPC)
222 // FIRST_GCMAP_REG = 0 => registerNumber = 1 (IA32)
223 //
224 return registerNumber - FIRST_GCMAP_REG + 1;
225 }
226
227 /**
228 * Determines if the next bit is set for the entry passed in the gc map passed
229 * @param entry the entry (index) to check
230 * @param gcMap the gcmap
231 * @return whether the next bit is set
232 */
233 private static boolean nextBitSet(int entry, int[] gcMap) {
234 return (gcMap[entry] & NEXT_BIT) == NEXT_BIT;
235 }
236
237 /**
238 * Dumps the GCmap that starts at entry.
239 * @param entry the entry where the map begins
240 * @param gcMap the encoded GCmaps
241 */
242 @Interruptible
243 public static void dumpMap(int entry, int[] gcMap) {
244 VM.sysWrite("Regs [");
245 // Inspect the register bit map for the entry passed and print
246 // those bit map entries that are true
247 for (int registerNumber = FIRST_GCMAP_REG; registerNumber <= LAST_GCMAP_REG; registerNumber++) {
248 if (registerIsSet(entry, registerNumber, gcMap)) {
249 VM.sysWrite(registerNumber, " ");
250 }
251 }
252 VM.sysWrite("]");
253 VM.sysWrite(" Spills [");
254 while (nextBitSet(entry, gcMap)) {
255 entry++;
256 VM.sysWrite(gcMapInformation(entry, gcMap));
257 VM.sysWrite(" ");
258 }
259 VM.sysWrite("]");
260 }
261
262 ////////////////////////////////////////////
263 // Helper methods for GCMap creation
264 ////////////////////////////////////////////
265 /**
266 * Returns the next GC map entry for use
267 * @return the entry in the map table that can be used
268 */
269 @Interruptible
270 private int getNextMapEntry() {
271 // make sure we have enough room
272 int oldLength = gcMapInformation.length - 1;
273 if (lastGCMapEntry >= oldLength) {
274 // expand the mapInformation array to be twice as big
275 resizeMapInformation(oldLength << 1);
276 }
277 return ++lastGCMapEntry;
278 }
279
280 /**
281 * Resize the map array
282 * @param newSize the new size for the map array
283 */
284 @Interruptible
285 private void resizeMapInformation(int newSize) {
286 int[] newMapInformation = new int[newSize];
287 for (int i = 0; i <= lastGCMapEntry; i++) {
288 newMapInformation[i] = gcMapInformation[i];
289 }
290 gcMapInformation = newMapInformation;
291 }
292
293 //////////
294 // Setters for GC Maps
295 //////////
296
297 /**
298 * Sets the register map information at the next available entry
299 * @param bitMap map entry
300 * @return The index of that entry.
301 */
302 @Interruptible
303 private int setRegisterBitMap(int bitMap) {
304 // Set the appropriate bit, but make sure we preserve the NEXT bit!
305 int entry = getNextMapEntry();
306 gcMapInformation[entry] = bitMap | NEXT_BIT;
307 return entry;
308 }
309
310 /**
311 * If we will be looking for missed references we need to sort the list
312 * of spills and then add them to the map, otherwise, nothing to do
313 * @param spillArray an array of spills
314 */
315 @Interruptible
316 private void addAllSpills(int[] spillArray) {
317 // 1) sort the spills to increase the odds of reusing the GC map
318 java.util.Arrays.sort(spillArray);
319
320 // 2) add them to the map using addSpillLocation
321 for (int spill : spillArray) {
322 addSpillLocation(spill);
323 }
324 }
325
326 /**
327 * Adds the passed spill value to the current map
328 * @param spill the spill location
329 */
330 @Interruptible
331 private void addSpillLocation(int spill) {
332 // make sure the value doesn't overflow the maximum spill location
333 if (VM.VerifyAssertions && ((spill < 0) || (spill > 32767))) {
334 VM._assert(false, "Unexpected spill passed:" + spill);
335 }
336 // get the next entry (with the NEXT bit set) ...
337 int entry = getNextMapEntry();
338 gcMapInformation[entry] = spill | NEXT_BIT;
339 }
340
341 /**
342 * Ends the current map
343 * @param firstIndex the index of the beginning of the map
344 * @return the index of the beginning of the map (may be different)
345 */
346 @Interruptible
347 private int endCurrentMap(int firstIndex) {
348 int lastEntry = lastGCMapEntry;
349
350 // adjust the last entry so that the NEXT bit is not set.
351 gcMapInformation[lastEntry] = gcMapInformation[lastEntry] & ~NEXT_BIT;
352
353 if (DEBUG) {
354 System.out.println("\nendCurrentMap called with firstIndex: " +
355 firstIndex +
356 ", lastGCMapEntry: " +
357 lastGCMapEntry);
358 System.out.println("gc map array before reuse checking");
359 for (int i = 0; i <= lastGCMapEntry; i++) {
360 System.out.println(i + ": " + gcMapInformation[i]);
361 }
362 }
363
364 // Now that we know the complete map information, let's determine if
365 // we really need to store it, or instead can reuse a previous map.
366 int candidateBeginningIndex = 0; //this will be the beginning
367 int candidateIndex = candidateBeginningIndex; // this will walk the map
368 int curIndex = firstIndex;
369 while (candidateIndex < firstIndex && curIndex <= lastEntry) {
370 int old = gcMapInformation[candidateIndex++];
371 int cur = gcMapInformation[curIndex++];
372 if (old != cur) {
373 if (DEBUG) {
374 System.out.println("entries at " + (candidateIndex - 1) + " and " + (curIndex - 1) + " don't match");
375 }
376 // this entry won't work, advance to candidateIndex to GC map entry
377 // and reset curIndex
378 while ((old & NEXT_BIT) != 0) {
379 old = gcMapInformation[candidateIndex++];
380 }
381
382 // update the beginning index too
383 candidateBeginningIndex = candidateIndex;
384 curIndex = firstIndex;
385 } else if ((old & NEXT_BIT) == 0) {
386 // we've checked all of the candidate without stopping, so we found
387 // a winner to reuse
388
389 if (DEBUG) {
390 System.out.println("found a matching map: [" +
391 candidateBeginningIndex +
392 ", " +
393 (candidateIndex - 1) +
394 "] == [" +
395 firstIndex +
396 ", " +
397 lastGCMapEntry +
398 "]");
399 }
400
401 lastGCMapEntry = firstIndex - 1;
402 return candidateBeginningIndex;
403 }
404 }
405
406 return firstIndex;
407 }
408 }