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