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.baseline;
014
015 import org.jikesrvm.ArchitectureSpecific.BaselineConstants;
016 import org.jikesrvm.VM;
017 import org.jikesrvm.classloader.RVMArray;
018 import org.jikesrvm.classloader.RVMMethod;
019 import org.jikesrvm.classloader.NormalMethod;
020 import org.jikesrvm.classloader.TypeReference;
021 import org.jikesrvm.scheduler.SpinLock;
022 import org.vmmagic.pragma.Interruptible;
023 import org.vmmagic.pragma.Uninterruptible;
024 import org.vmmagic.unboxed.Offset;
025
026 /**
027 * class that provides stack (and local var) map for a baseline compiled method
028 * GC uses the methods provided here
029 */
030 @Uninterruptible
031 public final class ReferenceMaps implements BaselineConstants {
032
033 public static final byte JSR_MASK = -128; // byte = x'80'
034 public static final byte JSR_INDEX_MASK = 0x7F;
035
036 public static final int STARTINDEX = 0;
037 public static final int NOMORE = 0;
038 /** Kinds of merge operation when merging delta maps into table maps */
039 private static enum MergeOperation {
040 OR, NAND, COPY
041 }
042
043 /** Serializes JSR processing */
044 public static final SpinLock jsrLock = new SpinLock(); // for serialization of JSR processing
045
046 /** Number of bits in each map element */
047 private static final int BITS_PER_MAP_ELEMENT = 8;
048 private byte[] referenceMaps;
049 private int[] MCSites;
050 /** Number of bits in each map */
051 private final int bitsPerMap;
052 /** Number of maps */
053 private int mapCount;
054 private JSRInfo jsrInfo;
055
056 /**
057 * size of individual maps
058 */
059 private int bytesPerMap() {
060 return ((bitsPerMap + 7) / 8) + 1;
061 }
062
063 ReferenceMaps(BaselineCompiledMethod cm, int[] stackHeights, byte[] localTypes) {
064
065 NormalMethod method = (NormalMethod) cm.getMethod();
066 // save input information and compute related data
067 this.bitsPerMap = (method.getLocalWords() + method.getOperandWords() + 1); // +1 for jsr bit
068
069 // this.startLocal0Offset = BaselineCompilerImpl.getStartLocalOffset(method);
070
071 if (VM.TraceStkMaps) {
072 VM.sysWrite("ReferenceMaps constructor. Method name is:");
073 VM.sysWrite(method.getName());
074 VM.sysWrite(" -Class name is :");
075 VM.sysWrite(method.getDeclaringClass().getDescriptor());
076 VM.sysWrite("\n");
077 VM.sysWrite(" bytesPerMap = ", bytesPerMap());
078 VM.sysWrite(" - bitsPerMap = ", bitsPerMap);
079 // VM.sysWriteln(" - startLocal0Offset = ", startLocal0Offset);
080 }
081
082 // define the basic blocks
083 BuildBB buildBB = new BuildBB();
084 buildBB.determineTheBasicBlocks(method);
085
086 BuildReferenceMaps buildRefMaps = new BuildReferenceMaps();
087 buildRefMaps.buildReferenceMaps(method, stackHeights, localTypes, this, buildBB);
088
089 if (VM.ReferenceMapsBitStatistics) {
090 showReferenceMapStatistics(method);
091 }
092 }
093
094 /**
095 * Given a machine code instruction offset, return an index to
096 * identify the stack map closest to the offset ( but not beyond).<p>
097 *
098 * Usage note: "machCodeOffset" must point to the instruction *following*
099 * the actual instruction
100 * whose stack map is sought. This allows us to properly handle the case where
101 * the only address we have to work with is a return address (i.e. from a stackframe)
102 * or an exception address (i.e. from a null pointer dereference, array bounds check,
103 * or divide by zero) on a machine architecture with variable length instructions.
104 * In such situations we'd have no idea how far to back up the instruction pointer
105 * to point to the "call site" or "exception site".<p>
106 *
107 * If the located site is within the scope of a jsr subroutine
108 * the index value returned is a negative number.
109 */
110 public int locateGCPoint(Offset machCodeOffset, RVMMethod method) {
111
112 machCodeOffset = machCodeOffset.minus(1 << LG_INSTRUCTION_WIDTH); // this assumes that machCodeOffset points
113 // to "next" instruction eg bal type instruction
114
115 if (VM.TraceStkMaps) {
116 VM.sysWrite("ReferenceMaps-locateGCPoint for machine code offset = ");
117 VM.sysWrite(machCodeOffset);
118 VM.sysWrite(" --- in method = ");
119 VM.sysWrite(method.getName());
120 VM.sysWrite("\n");
121 }
122
123 // Scan the list of machine code addresses to find the
124 // closest site offset BEFORE the input machine code index ( offset in the code)
125 Offset distance = Offset.zero();
126 int index = 0;
127 // get the first possible location
128 for (int i = 0; i < mapCount; i++) {
129 // get an initial non zero distance
130 distance = machCodeOffset.minus(MCSites[i]);
131 if (distance.sGE(Offset.zero())) {
132 index = i;
133 break;
134 }
135 }
136 // scan to find any better location i.e. closer to the site
137 for (int i = index + 1; i < mapCount; i++) {
138 Offset dist = machCodeOffset.minus(MCSites[i]);
139 if (dist.sLT(Offset.zero())) continue;
140 if (dist.sLE(distance)) {
141 index = i;
142 distance = dist;
143 }
144 }
145
146 if (VM.TraceStkMaps) {
147 showInfo();
148 VM.sysWrite(" ReferenceMaps-locateGCPoint located index = ");
149 VM.sysWrite(index);
150 VM.sysWrite(" byte = ");
151 VM.sysWrite(referenceMaps[index]);
152 VM.sysWrite("\n");
153 if (index - 1 >= 0) {
154 VM.sysWrite(" MCSites[index-1] = ");
155 VM.sysWrite(machCodeOffset.minus(MCSites[index - 1]));
156 VM.sysWrite("\n");
157 }
158 VM.sysWrite(" MCSites[index ] = ");
159 VM.sysWrite(machCodeOffset.minus(MCSites[index]));
160 VM.sysWrite("\n");
161 if (index + 1 < MCSites.length) {
162 VM.sysWrite(" MCSites[index+1] = ");
163 VM.sysWrite(machCodeOffset.minus(MCSites[index + 1]));
164 VM.sysWrite("\n");
165 }
166 }
167
168 // test for a site within a jsr subroutine
169 if ((0x000000FF & (referenceMaps[index * bytesPerMap()] & JSR_MASK)) ==
170 (0x000000FF & JSR_MASK)) { // test for jsr map
171 index = -index; // indicate site within a jsr to caller
172 if (VM.TraceStkMaps) {
173 VM.sysWrite(" ReferenceMaps-locateGCPoint jsr mapid = ");
174 VM.sysWrite(-index);
175 VM.sysWrite("\n");
176 }
177 }
178
179 if (VM.TraceStkMaps) {
180 VM.sysWrite(" ReferenceMaps-locateGCPoint machine offset = ");
181 VM.sysWrite(machCodeOffset);
182 VM.sysWrite(" - return map index = ");
183 VM.sysWrite(index);
184 VM.sysWrite("\n");
185 }
186
187 return index;
188 }
189
190 /**
191 * @param index offset in the reference stack frame,
192 * @param siteindex index that indicates the callsite (siteindex),
193 * @return return the offset where the next reference can be found.
194 * @return NOMORE when no more pointers can be found
195 */
196 public int getNextRefIndex(int index, int siteindex) {
197 if (VM.TraceStkMaps) {
198 VM.sysWrite("ReferenceMaps-getNextRef-inputs index = ");
199 VM.sysWrite(index);
200 VM.sysWrite(" -siteindex = ");
201 VM.sysWrite(siteindex);
202 VM.sysWrite("\n");
203 }
204
205 // use index to locate the gc point of interest
206 if (bytesPerMap() == 0) return 0; // no map ie no refs
207 int mapindex = siteindex * bytesPerMap();
208
209 int bitnum;
210 if (index == STARTINDEX) {
211 // this is the initial scan for the map
212 int mapByteNum = mapindex;
213 int startbitnumb = 1; // start search from beginning
214 bitnum = scanForNextRef(startbitnumb, mapByteNum, bitsPerMap, referenceMaps);
215
216 if (VM.TraceStkMaps) {
217 VM.sysWriteln("ReferenceMaps-getNextRef-initial call bitnum = ", bitnum);
218 }
219 } else {
220 // get bitnum and determine mapword to restart scan
221 bitnum = index + 1; // +1 for jsr bit
222
223 if (VM.TraceStkMaps) {
224 VM.sysWriteln("ReferenceMaps-getnextref- not initial- entry index,bitnum = ", index, " ", bitnum);
225 }
226
227 // scan forward from current position to next ref
228 bitnum = scanForNextRef(bitnum + 1, mapindex, (bitsPerMap - (bitnum - 1)), referenceMaps);
229
230 if (VM.TraceStkMaps) {
231 VM.sysWriteln("ReferenceMaps-getnextref- not initial- scan returned bitnum = ", bitnum);
232 }
233 }
234
235 if (bitnum == NOMORE) {
236 if (VM.TraceStkMaps) VM.sysWriteln(" NOMORE");
237 return NOMORE;
238 } else {
239 int ans = bitnum - 1; //-1 for jsr bit
240 if (VM.TraceStkMaps) VM.sysWriteln(" result = ", ans);
241 return ans;
242 }
243 }
244
245 /**
246 * Given an offset in the jsr reference map,
247 * return the offset where the next returnAddress can be found.<p>
248
249 * NOTE: There is only one JSR map for the entire method because it has to
250 * be constructed at GC time and would normally require additional
251 * storage.
252 * <p>
253 * To avoid this, the space for one map is pre-allocated and the map
254 * is built in that space. When multiple threads exist and if GC runs
255 * in multiple threads concurrently, then the MethodMap must be locked
256 * when a JSR map is being scanned. This should be a low probability
257 * event.
258 *
259 * @param index offset in the JSR reference map,
260 * @return The offset where the next reference can be found or
261 * <code>NOMORE</code> when no more pointers can be found
262 *
263 */
264 public int getNextJSRRefIndex(int index) {
265 // user index to locate the gc point of interest
266 if (bytesPerMap() == 0) return 0; // no map ie no refs
267 int mapword = jsrInfo.mergedReferenceMap;
268
269 int bitnum;
270 if (index == STARTINDEX) {
271 // this is the initial scan for the map
272 int startbitnumb = 1; // start search from beginning
273 bitnum = scanForNextRef(startbitnumb, mapword, bitsPerMap, jsrInfo.unusualReferenceMaps);
274 if (VM.TraceStkMaps) {
275 VM.sysWrite("ReferenceMaps-getJSRNextRef-initial call - startbitnum =", startbitnumb);
276 VM.sysWrite(" mapword = ", mapword);
277 VM.sysWrite(" bitspermap = ", bitsPerMap);
278 VM.sysWrite(" bitnum = ", bitnum);
279 }
280 } else {
281 // get bitnum and determine mapword to restart scan
282 bitnum = index; // get the bit number from last time
283
284 // scan forward from current position to next ref
285 if (VM.TraceStkMaps) {
286 VM.sysWrite("ReferenceMaps.getJSRnextref - not initial- starting (index,bitnum) = ");
287 VM.sysWrite(index);
288 VM.sysWrite(", ");
289 VM.sysWrite(bitnum);
290 }
291
292 bitnum = scanForNextRef(bitnum + 1, mapword, (bitsPerMap - (bitnum - 1)), jsrInfo.unusualReferenceMaps);
293 }
294
295 if (bitnum == NOMORE) {
296 if (VM.TraceStkMaps) VM.sysWriteln(" NOMORE");
297 return NOMORE;
298 } else {
299 int ans = bitnum;
300 if (VM.TraceStkMaps) VM.sysWriteln(" result = ", ans);
301 return ans;
302 }
303 }
304
305 /**
306 * Given an offset in the jsr returnAddress map,
307 * return the offset where the next returnAddress can be found.<p>
308 *
309 * NOTE: there is only one jsr returnAddress map for the entire method because it has to be
310 * be constructed a GC time and would normally require additional storage.
311 * To avoid this, the space for one map is pre-allocated and the map
312 * is built in that space. When multiple threads exist and if GC runs
313 * in multiple threads concurrently, then the MethodMap must be locked
314 * when a jsr map is being scanned.
315 * This should be a low probability event.<p>
316 *
317 * NOTE: return addresses are handled separately from references because they point
318 * inside an object ( internal pointers)
319 *
320 * @param index offset in the JSR returnAddress map,
321 * @return The offset where the next reference can be found or
322 * <code>NOMORE</code> when no more pointers can be found
323 */
324 public int getNextJSRReturnAddrIndex(int index) {
325 // use the preallocated map to locate the current point of interest
326 int mapword = jsrInfo.mergedReturnAddressMap;
327 if (bytesPerMap() == 0) {
328 if (VM.TraceStkMaps) {
329 VM.sysWriteln("ReferenceMaps-getJSRNextReturnAddr-initial call no returnaddresses");
330 }
331 return 0; // no map ie no refs
332 }
333
334 int bitnum;
335 if (index == STARTINDEX) {
336 // this is the initial scan for the map
337 int startbitnumb = 1; // start search from beginning
338 bitnum = scanForNextRef(startbitnumb, mapword, bitsPerMap, jsrInfo.unusualReferenceMaps);
339 if (VM.TraceStkMaps) {
340 VM.sysWrite("ReferenceMaps-getJSRNextReturnAddr-initial call startbitnum, mapword, bitspermap = ");
341 VM.sysWrite(startbitnumb);
342 VM.sysWrite(" , ");
343 VM.sysWrite(mapword);
344 VM.sysWrite(" , ");
345 VM.sysWrite(bitsPerMap);
346 VM.sysWrite(" \n ");
347 VM.sysWrite("ReferenceMaps-getJSRNextReturnAddr-initial call return bitnum = ");
348 VM.sysWrite(bitnum);
349 VM.sysWrite("\n");
350 }
351 } else {
352 // get bitnum and determine mapword to restart scan
353 bitnum = index; // get the bit number
354 if (VM.TraceStkMaps) {
355 VM.sysWriteln("ReferenceMaps-getJSRnextReturnAddr- not initial- starting index, starting bitnum = ",
356 index,
357 " ",
358 bitnum);
359 }
360
361 // scan forward from current position to next ref
362 bitnum = scanForNextRef(bitnum + 1, mapword, (bitsPerMap - (bitnum - 1)), jsrInfo.unusualReferenceMaps);
363
364 if (VM.TraceStkMaps) {
365 VM.sysWriteln("ReferenceMaps-getJSRnextref- not initial- scan returned bitnum = ", bitnum);
366 }
367 }
368
369 if (bitnum == NOMORE) {
370 if (VM.TraceStkMaps) VM.sysWriteln(" NOMORE");
371 return NOMORE;
372 } else {
373 int ans = bitnum;
374 if (VM.TraceStkMaps) VM.sysWrite("ReferenceMaps-getJSRNextReturnAddr-return = ", ans);
375 return ans;
376 }
377 }
378
379 /**
380 * For debugging (used with CheckRefMaps)
381 * Note: all maps are the same size
382 */
383 public int getStackDepth(int mapid) {
384 return bytesPerMap();
385 }
386
387 @Interruptible
388 public int size() {
389 int size = TypeReference.ReferenceMaps.peekType().asClass().getInstanceSize();
390 if (MCSites != null) size += RVMArray.IntArray.getInstanceSize(MCSites.length);
391 if (referenceMaps != null) size += RVMArray.ByteArray.getInstanceSize(referenceMaps.length);
392 if (jsrInfo != null && jsrInfo.unusualReferenceMaps != null) {
393 size += RVMArray.JavaLangObjectArray.getInstanceSize(jsrInfo.unusualReferenceMaps.length);
394 }
395 return size;
396 }
397
398 /**
399 * start setting up the reference maps for this method.
400 */
401 @Interruptible
402 public void startNewMaps(int gcPointCount, int jsrCount, int parameterWords) {
403 // normal map information
404 mapCount = 0;
405 MCSites = new int[gcPointCount];
406 referenceMaps = new byte[gcPointCount * bytesPerMap()];
407
408 if (VM.TraceStkMaps) {
409 VM.sysWrite("ReferenceMaps-startNewMaps- gcPointCount = ");
410 VM.sysWrite(gcPointCount);
411 VM.sysWrite(" -jsrCount = ");
412 VM.sysWrite(jsrCount);
413 VM.sysWrite("\n");
414 }
415
416 if (jsrCount > 0) {
417
418 jsrInfo = new JSRInfo(2 * jsrCount);
419
420 // reserve a map for merging maps
421 jsrInfo.tempIndex = getNextMapElement();
422
423 // reserve map words for merged reference map
424 jsrInfo.mergedReferenceMap = getNextMapElement();
425
426 // reserve map words for merged return address map
427 jsrInfo.mergedReturnAddressMap = getNextMapElement();
428
429 //reserve maps for the jsrInfo.extraUnusualMapObject
430 // the reference map
431 int mapstart = getNextMapElement();
432 jsrInfo.extraUnusualMap.setReferenceMapIndex(mapstart);
433
434 //the set of non reference stores
435 mapstart = getNextMapElement();
436 jsrInfo.extraUnusualMap.setNonReferenceMapIndex(mapstart);
437
438 // the return address map
439 mapstart = getNextMapElement();
440 jsrInfo.extraUnusualMap.setReturnAddressMapIndex(mapstart);
441
442 }
443
444 }
445
446 /**
447 * Given the information about a GC point, record the information in the proper tables.
448 * @param byteindex the index in the bytecode of this site
449 * @param byteMap a byte array that describes the contents of the local variables and the java stack
450 * @param BBLastPtr the last offset of a byte that contains information about the map
451 * @param replacemap whether this map is a replacement for a currently
452 * existing map
453 */
454 @Interruptible
455 public void recordStkMap(int byteindex, byte[] byteMap, int BBLastPtr, boolean replacemap) {
456
457 int mapNum = 0;
458
459 if (VM.TraceStkMaps) {
460 VM.sysWrite(" ReferenceMaps-recordStkMap bytecode offset = ");
461 VM.sysWrite(byteindex);
462 VM.sysWrite("\n");
463 VM.sysWrite(" input byte map = ");
464 for (int j = 0; j <= BBLastPtr; j++) {
465 VM.sysWrite(byteMap[j]);
466 }
467 VM.sysWrite("\n");
468 if (replacemap) {
469 VM.sysWrite(" ReferenceMaps-recordStkMap- replacing map at byteindex = ");
470 VM.sysWrite(byteindex);
471 VM.sysWrite("\n");
472 }
473 }
474
475 if (replacemap) {
476 // replace a map that already exists in the table
477 // locate the site
478 for (mapNum = 0; mapNum < mapCount; mapNum++) {
479 if (MCSites[mapNum] == byteindex) {
480 // location found -clear out old map
481 int start = mapNum * bytesPerMap(); // get starting byte in map
482 for (int i = start; i < start + bytesPerMap(); i++) {
483 referenceMaps[i] = 0;
484 }
485 if (VM.TraceStkMaps) {
486 VM.sysWrite(" ReferenceMaps-recordStkMap replacing map number = ", mapNum);
487 VM.sysWriteln(" for machinecode index = ", MCSites[mapNum]);
488 }
489 break;
490 }
491 }
492 } else {
493 // add a map to the table - its a new site
494 // allocate a new site
495 mapNum = mapCount++;
496 // fill in basic information
497 MCSites[mapNum] = byteindex; // gen and save bytecode offset
498 if (BBLastPtr == -1) return; // empty map for this gc point
499 }
500
501 if (VM.TraceStkMaps) {
502 VM.sysWrite(" ReferenceMaps-recordStkMap map id = ");
503 VM.sysWrite(mapNum);
504 VM.sysWrite("\n");
505 }
506
507 // convert Boolean array into array of bits ie create the map
508 int mapslot = mapNum * bytesPerMap();
509 int len = (BBLastPtr + 1); // get last ptr in map
510 int offset = 0; // offset from origin
511 int convertLength; //to start in the map
512 int word = mapslot;
513
514 // convert first byte of map
515 // get correct length for first map byte - smaller of bits in first byte or size of map
516 if (len < (BITS_PER_MAP_ELEMENT - 1)) {
517 convertLength = len;
518 } else {
519 convertLength = BITS_PER_MAP_ELEMENT - 1;
520 }
521 byte firstByte = convertMapElement(byteMap, offset, convertLength, BuildReferenceMaps.REFERENCE);
522 referenceMaps[word] = (byte) ((0x000000ff & firstByte) >>> 1); // shift for jsr bit ie set it to 0
523
524 if (VM.TraceStkMaps) {
525 VM.sysWrite(" ReferenceMaps-recordStkMap convert first map bytes- byte number = ");
526 VM.sysWrite(word);
527 VM.sysWrite(" byte value in map = ");
528 VM.sysWrite(referenceMaps[word]);
529 VM.sysWrite(" - before shift = ");
530 VM.sysWrite(firstByte);
531 VM.sysWrite("\n");
532 }
533
534 // update indexes for additional bytes
535 word++; // next byte in bit map
536 len -= (BITS_PER_MAP_ELEMENT - 1); // remaining count
537 offset += (BITS_PER_MAP_ELEMENT - 1); // offset into input array
538
539 // convert remaining byte array to bit array -
540 while (len > 0) {
541 // map takes multiple bytes -convert 1 at a time
542 if (len <= (BITS_PER_MAP_ELEMENT - 1)) {
543 convertLength = len;
544 } else {
545 convertLength = BITS_PER_MAP_ELEMENT;
546 }
547 // map takes multiple bytes -convert 1 at a time
548 referenceMaps[word] = convertMapElement(byteMap, offset, convertLength, BuildReferenceMaps.REFERENCE);
549
550 if (VM.TraceStkMaps) {
551 VM.sysWriteln(" ReferenceMaps-recordStkMap convert another map byte- byte number = ",
552 word,
553 " byte value = ",
554 referenceMaps[word]);
555 }
556
557 len -= BITS_PER_MAP_ELEMENT; // update remaining words
558 offset += BITS_PER_MAP_ELEMENT; // and offset
559 word++;
560 } // end of while
561
562 // update stats
563 if (VM.ReferenceMapsStatistics) {
564 if (!replacemap) {
565 }
566 }
567 }
568
569 /**
570 * Record a map for a point within a JSR Subroutine. This requires setting up one
571 * of the unusual maps.
572 * @param byteindex index into the byte code array of the point for the map
573 * @param currReferenceMap map of references and return addresses that were set
574 * within the JSR Subroutine
575 * @param BBLastPtr map runs from -1 to BBLastPtr inclusively
576 * @param returnAddrIndex Index in the stack where the return address
577 * for the jsr routine (in which this gcpoint is located)
578 * can be found
579 * @param replacemap {@code false} if this is the first time this map point has been
580 * recorded.
581 */
582 @Interruptible
583 public void recordJSRSubroutineMap(int byteindex, byte[] currReferenceMap, int BBLastPtr, int returnAddrIndex,
584 boolean replacemap) {
585 int mapNum = 0;
586 int unusualMapIndex = 0;
587 int internalReturnIndex;
588 UnusualMaps jsrSiteMap;
589
590 if (replacemap) {
591 // update an already existing map
592 // locate existing site in table
593 jsrSiteMap = null;
594 findJSRSiteMap:
595 for (mapNum = 0; mapNum < mapCount; mapNum++) {
596 if (MCSites[mapNum] == byteindex) {
597 // GC site found - get index in unusual map table and the unusual Map
598 unusualMapIndex = JSR_INDEX_MASK & referenceMaps[mapNum * bytesPerMap()];
599 internalReturnIndex = returnAddrIndex - 1; //-1 for jsrbit
600 if (unusualMapIndex == JSR_INDEX_MASK) {
601 // greater than 127 jsrInfo.unusualMaps- sequential scan of locate others unusual map
602 for (unusualMapIndex = JSR_INDEX_MASK; unusualMapIndex < jsrInfo.numberUnusualMaps; unusualMapIndex++) {
603 if (jsrInfo.unusualMaps[unusualMapIndex].getReturnAddressIndex() == internalReturnIndex) {
604 jsrSiteMap = jsrInfo.unusualMaps[unusualMapIndex];
605 break findJSRSiteMap;
606 }
607 }
608 VM.sysFail(" can't find unusual map !!!!!!! - should never occur");
609 } else {
610 jsrSiteMap = jsrInfo.unusualMaps[unusualMapIndex];
611 break;
612 }
613 }
614 }
615 } else {
616 // new map, add to end of table
617 mapNum = mapCount++; // get slot and update count
618 MCSites[mapNum] = byteindex; // gen and save bytecode offset
619
620 // generate an UnusualMap for the site
621 jsrSiteMap = new UnusualMaps();
622
623 // add unusual map to UnusualMap table (table may need to be expanded)
624 unusualMapIndex = addUnusualMap(jsrSiteMap);
625
626 // set back pointer i.e. pointer from unusual maps back into referencemaps
627 jsrSiteMap.setNormalMapIndex(mapNum);
628
629 // setup index in reference maps
630 if (unusualMapIndex > JSR_INDEX_MASK) {
631 unusualMapIndex = JSR_INDEX_MASK;
632 }
633 referenceMaps[mapNum * bytesPerMap()] = (byte) ((byte) unusualMapIndex | JSR_MASK);
634
635 // setup new unusual Map
636 internalReturnIndex = returnAddrIndex - 1 + 2; // -1 for jsrbit +2 to convert to our index
637 jsrSiteMap.setReturnAddressIndex(internalReturnIndex);
638
639 if (VM.TraceStkMaps) {
640 VM.sysWrite("ReferenceMaps-recordJSRSubroutineMap- input map = ");
641 for (int i = 0; i < BBLastPtr + 1; i++) {
642 VM.sysWrite(currReferenceMap[i]);
643 }
644 VM.sysWrite("\n");
645 VM.sysWrite("ReferenceMaps-recordJSRSubroutineMap- mapNum = ");
646 VM.sysWrite(mapNum);
647 VM.sysWrite(" - byteindex = ");
648 VM.sysWrite(byteindex);
649 VM.sysWrite(" - return address index = ");
650 VM.sysWrite(internalReturnIndex);
651 VM.sysWrite(" - reference map byte = ");
652 VM.sysWrite(referenceMaps[mapNum * bytesPerMap()]);
653 VM.sysWrite("\n");
654 }
655 } // end else clause - add new map
656
657 // for new maps, setup maps in UnusualMap, for existing map replace them
658
659 // setup Reference Map
660 int refindex =
661 scanByteArray(currReferenceMap,
662 BBLastPtr,
663 BuildReferenceMaps.SET_TO_REFERENCE,
664 jsrSiteMap.getReferenceMapIndex(),
665 true);
666 jsrSiteMap.setReferenceMapIndex(refindex);
667
668 if (VM.TraceStkMaps) {
669 VM.sysWrite(" - reference map index = ");
670 VM.sysWrite(refindex);
671 VM.sysWrite(" - reference map = ");
672 for (int i = refindex; i < refindex + bytesPerMap(); i++) {
673 VM.sysWrite(jsrInfo.unusualReferenceMaps[i]);
674 }
675 VM.sysWrite("\n");
676 }
677
678 // setup NONReference Map
679 int nonrefindex =
680 scanByteArray(currReferenceMap,
681 BBLastPtr,
682 BuildReferenceMaps.SET_TO_NONREFERENCE,
683 jsrSiteMap.getNonReferenceMapIndex(),
684 true);
685 jsrSiteMap.setNonReferenceMapIndex(nonrefindex);
686
687 if (VM.TraceStkMaps) {
688 VM.sysWrite(" - NONreference map index = ");
689 VM.sysWrite(nonrefindex);
690 VM.sysWrite(" - NON reference map = ");
691 for (int i = nonrefindex; i < nonrefindex + bytesPerMap(); i++) {
692 VM.sysWrite(jsrInfo.unusualReferenceMaps[i]);
693 }
694 VM.sysWrite("\n");
695 }
696
697 // setup returnAddress Map
698 int addrindex =
699 scanByteArray(currReferenceMap,
700 BBLastPtr,
701 BuildReferenceMaps.RETURN_ADDRESS,
702 jsrSiteMap.getReturnAddressMapIndex(),
703 false);
704 jsrSiteMap.setReturnAddressMapIndex(addrindex);
705
706 if (VM.TraceStkMaps) {
707 VM.sysWrite(" - returnAddress map index = ");
708 VM.sysWrite(addrindex);
709 VM.sysWrite(" - return Address map = ");
710 for (int i = addrindex; i < addrindex + bytesPerMap(); i++) {
711 VM.sysWrite(jsrInfo.unusualReferenceMaps[i]);
712 }
713 VM.sysWrite("\n");
714 }
715
716 if (VM.TraceStkMaps) {
717 VM.sysWrite("ReferenceMaps-recordJSRSubroutineMap- unusualmap index = ");
718 VM.sysWrite(unusualMapIndex);
719 VM.sysWrite("\n");
720 }
721
722 // update stats
723 if (VM.ReferenceMapsStatistics) {
724 if (!replacemap) {
725 }
726 }
727 }
728
729 /**
730 * Add an UnusualMap to the array of unusual maps, expand the array
731 * and referencemap array if necessary
732 *
733 * @param jsrSiteMap unusualMap to be added to array
734 */
735 @Interruptible
736 private int addUnusualMap(UnusualMaps jsrSiteMap) {
737 if (jsrInfo.unusualMaps == null) {
738 // start up code
739 jsrInfo.unusualMaps = new UnusualMaps[5];
740 jsrInfo.numberUnusualMaps = 0;
741 }
742 // add to array and bump count
743 jsrInfo.unusualMaps[jsrInfo.numberUnusualMaps] = jsrSiteMap;
744 int returnnumber = jsrInfo.numberUnusualMaps;
745 jsrInfo.numberUnusualMaps++;
746
747 // do we need to extend the maps
748 if (jsrInfo.numberUnusualMaps == jsrInfo.unusualMaps.length) {
749 // array is full, expand arrays for jsrInfo.unusualMaps and unusual referencemaps
750 UnusualMaps[] temp = new UnusualMaps[jsrInfo.numberUnusualMaps + 5];
751 for (int i = 0; i < jsrInfo.numberUnusualMaps; i++) {
752 temp[i] = jsrInfo.unusualMaps[i];
753 }
754 jsrInfo.unusualMaps = temp;
755
756 byte[] temp2 = new byte[jsrInfo.unusualReferenceMaps.length + (5 * bytesPerMap() * 3)];
757 for (int i = 0; i < jsrInfo.unusualReferenceMaps.length; i++) {
758 temp2[i] = jsrInfo.unusualReferenceMaps[i];
759 }
760 jsrInfo.unusualReferenceMaps = temp2;
761 }
762 return returnnumber;
763 }
764
765 /**
766 * Setup a map within a JSR Subroutine. This requires using up one
767 * of the unusual maps. This routine is called when the caller gets a
768 * negative mapindex value return from {@link #locateGCPoint}. This routine
769 * searches the map tables and uses its stack frameAddress input to build
770 * reference and returnAddress maps. The caller uses the getNext...
771 * routines to scan these maps for offsets in the frame of the
772 * related references.<p>
773 *
774 * Steps for this routine:
775 * <ol>
776 * <li>use the mapid to get index of the Unusual Map
777 * <li>from the unusual map and the frame - get the location of the jsr invoker
778 * <li>from the invoker address and the code base address - get the machine code offset
779 * from the machine code offset locate the map for that instruction
780 * <li>if the invoker was itself in a jsr- merge the delta maps of each jsr and
781 * compute the new total delta maps
782 * <li>else the invoker was not already in a jsr merge the unusual map differences
783 * with the invoker map
784 * </ol>
785 *
786 * @param mapid Index of map of instruction where map is required
787 * ( this value was returned by locateGCpoint)
788 */
789 public int setupJSRSubroutineMap(int mapid) {
790
791 // first clear the maps in the jsrInfo.extraUnusualMap
792 int j = jsrInfo.extraUnusualMap.getReferenceMapIndex();
793 int k = jsrInfo.extraUnusualMap.getNonReferenceMapIndex();
794 int l = jsrInfo.extraUnusualMap.getReturnAddressMapIndex();
795 for (int i = 0; i < bytesPerMap(); i++) {
796 jsrInfo.unusualReferenceMaps[j + i] = 0;
797 jsrInfo.unusualReferenceMaps[k + i] = 0;
798 jsrInfo.unusualReferenceMaps[l + i] = 0;
799 }
800
801 // use the mapid to get index of the Unusual Map
802 //
803 if (VM.TraceStkMaps) {
804 VM.sysWriteln("ReferenceMaps-setupJSRSubroutineMap- mapid = ", mapid, " - mapid = ", -mapid);
805 VM.sysWriteln(" -referenceMaps[(- mapid) * bytesPerMap] = ", referenceMaps[(-mapid) * bytesPerMap()]);
806 VM.sysWriteln(" unusual mapid index = ", referenceMaps[(-mapid) * bytesPerMap()] & JSR_INDEX_MASK);
807 }
808
809 int unusualMapid = (referenceMaps[(-mapid) * bytesPerMap()] & JSR_INDEX_MASK);
810
811 // if jsr map is > 127 go search for the right one
812 if (unusualMapid == JSR_INDEX_MASK) {
813 unusualMapid = findUnusualMap(-mapid);
814 }
815
816 UnusualMaps unusualMap = jsrInfo.unusualMaps[unusualMapid];
817 unusualMapcopy(unusualMap); // deep copy unusual map into the extra map
818
819 // from the unusual map and the frame - get the location of the jsr invoker
820 //
821 return unusualMap.getReturnAddressIndex();
822 }
823
824 public int getNextJSRAddressIndex(Offset nextMachineCodeOffset, NormalMethod m) {
825 int jsrMapid = locateGCPoint(nextMachineCodeOffset, m);
826
827 if (jsrMapid >= 0) {
828 finalMergeMaps((jsrMapid * bytesPerMap()), jsrInfo.extraUnusualMap);
829
830 if (VM.TraceStkMaps) {
831 VM.sysWriteln("ReferenceMaps-setupJSRsubroutineMap- afterfinalMerge jsrInfo.extraUnusualMap = ");
832 jsrInfo.extraUnusualMap.showInfo();
833 VM.sysWriteln();
834 VM.sysWriteln(" jsrInfo.mergedReferenceMap Index = ", jsrInfo.mergedReferenceMap);
835 VM.sysWrite(" jsrInfo.mergedReferenceMap = ");
836 jsrInfo.showAnUnusualMap(jsrInfo.mergedReferenceMap, bytesPerMap());
837 VM.sysWriteln(jsrInfo.unusualReferenceMaps[jsrInfo.mergedReferenceMap]);
838 VM.sysWriteln(" jsrInfo.mergedReturnAddressMap Index = ", jsrInfo.mergedReturnAddressMap);
839 VM.sysWriteln(" jsrInfo.mergedReturnAddressMap = ",
840 jsrInfo.unusualReferenceMaps[jsrInfo.mergedReturnAddressMap]);
841 showInfo();
842 jsrInfo.showUnusualMapInfo(bytesPerMap());
843 }
844 return 0;
845 }
846
847 jsrMapid = -jsrMapid;
848
849 if (VM.TraceStkMaps) {
850 VM.sysWriteln("ReferenceMaps-setupJSRsubroutineMap- outer MapIndex = ",
851 jsrMapid,
852 " unusualMapIndex = ",
853 referenceMaps[jsrMapid]);
854 }
855
856 // merge unusual maps- occurs in nested jsr conditions
857 // merge each nested delta into the maps of the extraUnusualmap
858 int unusualMapIndex = JSR_INDEX_MASK & referenceMaps[jsrMapid * bytesPerMap()];
859 if (unusualMapIndex == JSR_INDEX_MASK) {
860 unusualMapIndex = findUnusualMap(jsrMapid);
861 }
862 jsrInfo.extraUnusualMap = combineDeltaMaps(unusualMapIndex);
863
864 // Locate the next JSR from the current
865 //
866 UnusualMaps thisMap = jsrInfo.unusualMaps[unusualMapIndex];
867 if (VM.TraceStkMaps) {
868 VM.sysWriteln("ReferenceMaps-setupJSRsubroutineMap- nested jsrs jsrInfo.extraUnusualMap = ");
869 jsrInfo.extraUnusualMap.showInfo();
870 VM.sysWriteln();
871 VM.sysWriteln("ReferenceMaps-setupJSRsubroutineMap- nested jsrs thisMap = ");
872 thisMap.showInfo();
873 VM.sysWriteln();
874 }
875 return thisMap.getReturnAddressIndex();
876 }
877
878 /**
879 * Called when all the recording for this map is complete. Can now
880 * sort or perform other cleanups
881 */
882 public void recordingComplete() {
883 }
884
885 /**
886 * After code is generated, translate the bytecode indices
887 * recorded in MCSites array into real machine code offsets.
888 */
889 public void translateByte2Machine(int[] b2m) {
890 for (int i = 0; i < MCSites.length; i++) {
891 MCSites[i] = b2m[MCSites[i]] << LG_INSTRUCTION_WIDTH;
892 }
893 }
894
895 /**
896 * convert a portion of an array word of Bytes into a bitmap of references
897 * i.e. given a byte array,
898 * a starting offset in the array,
899 * the length to scan,
900 * and the type of byte to scan for
901 * ... convert the area in the array to a
902 * word of bits ... max length is 31 i.e. BITS_PER_MAP_ELEMENT
903 */
904 private byte convertMapElement(byte[] curBBMap, int offset, int len, byte reftype) {
905 byte bitmap = 0;
906 byte mask = JSR_MASK; // starting bit mask
907 for (int i = offset; i < offset + len; i++) {
908 if (curBBMap[i] == reftype) {
909 bitmap = (byte) (bitmap | mask); // add bit to mask
910 }
911 mask = (byte) ((0x000000ff & mask) >>> 1); // shift for next byte and bit
912 }
913 return bitmap;
914 }
915
916 /**
917 * get Next free word in referencemaps for GC call sites
918 */
919 @Interruptible
920 private int getNextMapElement() {
921 if (jsrInfo.unusualReferenceMaps == null) {
922 // start up code
923 jsrInfo.unusualReferenceMaps = new byte[((6 * 3) + 1) * bytesPerMap()]; // 3 maps per unusual map
924 }
925
926 if (jsrInfo.freeMapSlot >= jsrInfo.unusualReferenceMaps.length) {
927 // map is full - get new array, twice the size
928 byte[] newArray = new byte[jsrInfo.unusualReferenceMaps.length << 1];
929 // copy array from old to new
930 for (int i = 0; i < jsrInfo.unusualReferenceMaps.length; i++) {
931 newArray[i] = jsrInfo.unusualReferenceMaps[i];
932 }
933 // replace old array with the new
934 jsrInfo.unusualReferenceMaps = newArray; // replace array
935 }
936
937 int allocate = jsrInfo.freeMapSlot;
938 jsrInfo.freeMapSlot = jsrInfo.freeMapSlot + bytesPerMap();
939 return allocate;
940 }
941
942 /**
943 * given a index in the local area (biased : local0 has index 1)
944 * this routine determines the correspondig offset in the stack
945 */
946 /* public int convertIndexToOffset(int index) {
947 if (index == 0) return NOMORE; //invalid
948
949 // convert from top of local words
950 int offset = startLocal0Offset - (index <<LOG_BYTES_IN_ADDRESS); // no jsrbit here
951 if (VM.TraceStkMaps) {
952 VM.sysWriteln("convertIndexToOffset- input index = ", index, " offset = ", offset);
953 }
954 return offset;
955 }
956 */
957
958 /**
959 * Scans the map for the next reference.
960 *
961 * @param bitnum starting bitnumber in a map (inclusive)
962 * @param wordnum index of the corresponding byte,
963 * @param remaining remaining number of bits in the map,
964 * @param map map to search
965 * @return TODO document me
966 */
967 private int scanForNextRef(int bitnum, int wordnum, int remaining, byte[] map) {
968 int retbit, count = 0;
969
970 // adjust bitnum and wordnum to bit within word
971 while (bitnum > BITS_PER_MAP_ELEMENT) {
972 wordnum++;
973 bitnum -= BITS_PER_MAP_ELEMENT;
974 count += BITS_PER_MAP_ELEMENT;
975 }
976
977 // determine remaining bits in this byte - first byte of scan
978 int remain = (BITS_PER_MAP_ELEMENT + 1) - bitnum; // remaining bits in this word
979 if (remain >= remaining) {
980 // last word in this map
981 retbit = scanByte(bitnum, wordnum, remaining, map);
982 if (retbit == 0) return 0;
983 return (retbit + count);
984 }
985 // search at least the rest of this byte
986 int startbit = bitnum; // start at this bit
987 retbit = scanByte(startbit, wordnum, remain, map);
988 if (retbit != 0) return (retbit + count);
989
990 // search additional bytes of map
991 startbit = 1; // start from beginning from now on
992 remaining -= remain; // remaing bits in map
993 count += BITS_PER_MAP_ELEMENT; // remember you did the first byte
994 while (remaining > BITS_PER_MAP_ELEMENT) {
995 wordnum++; // bump to next word
996 remaining -= BITS_PER_MAP_ELEMENT; // search this wordd
997 retbit = scanByte(startbit, wordnum, BITS_PER_MAP_ELEMENT, map);
998 if (retbit != 0) return (retbit + count);
999 count += BITS_PER_MAP_ELEMENT;
1000 } // end while
1001
1002 // scan last byte of map
1003 wordnum++;
1004 retbit = scanByte(startbit, wordnum, remaining, map); // last word
1005 if (retbit != 0) return (retbit + count);
1006 return 0;
1007 }
1008
1009 /**
1010 * Scans for a reference in a byte.
1011 *
1012 * @param bitnum bitnumber in the map
1013 * @param bytenum index of the corresponding map byte
1014 * @param toscan the remaining number of bits in the byte,
1015 * @param map the map
1016 * @return next ref in the byte or zero if not found
1017 */
1018 private int scanByte(int bitnum, int bytenum, int toscan, byte[] map) {
1019 int count = 0, mask;
1020
1021 if (VM.TraceStkMaps) {
1022 VM.sysWrite(" scanByte- inputs bitnum = ", bitnum);
1023 VM.sysWrite(" bytenum = ", bytenum);
1024 VM.sysWriteln(" toscan = ", toscan);
1025 VM.sysWriteln(" stackmap byte = ", map[bytenum]);
1026 }
1027
1028 // convert bitnum to mask
1029 mask = (1 << (BITS_PER_MAP_ELEMENT - bitnum)); // generate mask
1030
1031 // scan rest of word
1032 while (toscan > 0) {
1033 if ((mask & map[bytenum]) == 0) {
1034 // this bit not a ref
1035 mask = mask >>> 1; // move mask bit
1036 count++; // inc count of bits checked
1037 toscan--; // decrement remaining count
1038 } else {
1039 // ref bit found
1040 if (VM.TraceStkMaps) {
1041 VM.sysWriteln(" scanByte- return bit number = ", bitnum + count);
1042 }
1043 return bitnum + count;
1044 }
1045 } // end while
1046 return 0; // no more refs
1047 }
1048
1049 /**
1050 * Scans the byte array to look for the type of information that was requested. Builds a
1051 * bit array in the stack maps with the information.
1052 *
1053 * @param byteMap bytearray where each byte describes the corresponding word on a stack
1054 * @param BBLastPtr length of the byte array
1055 * @param refType type of information that is to be scanned
1056 * @param mapslot slot where map should be stored, 0 for next free slot
1057 * @param skipOneBit should a bit in the bitarray be skipped? Necessary for setRef and
1058 * setNonRef maps so so they are properly merged with jsr base maps.
1059 * @return index of the map in the reference map
1060 */
1061 @Interruptible
1062 int scanByteArray(byte[] byteMap, int BBLastPtr, byte refType, int mapslot, boolean skipOneBit) {
1063 skipOneBit = false;
1064
1065 if (BBLastPtr == -1) return -1; // no map for this jsr
1066
1067 // get a place to hold the map if necessary
1068 if (mapslot == 0) {
1069 mapslot = getNextMapElement(); // get first word of map
1070 }
1071
1072 // initialize search variables
1073 int len = (BBLastPtr + 1); // get length of map
1074 int offset = 0; // offset from origin
1075 int word = mapslot; // first word of map
1076
1077 // map may take multiple words -convert 1 at a time
1078 while (len > 0) {
1079 boolean doSkip = (offset == 0 && skipOneBit); // skip a bit if first word and skipOneBit is set
1080 int bitsToDo = doSkip ? BITS_PER_MAP_ELEMENT - 1 : BITS_PER_MAP_ELEMENT;
1081 if (len < bitsToDo) {
1082 bitsToDo = len;
1083 }
1084
1085 byte result = convertMapElement(byteMap, offset, bitsToDo, refType);
1086 if (doSkip) {
1087 result =
1088 (byte) ((0x000000ff & result) >>>
1089 1); // shift right to skip high bit for jsr to be consistent with normal maps
1090 }
1091 jsrInfo.unusualReferenceMaps[word] = result;
1092
1093 len -= bitsToDo; // update remaining words
1094 offset += bitsToDo; // and offset
1095 word++; // get next word
1096 }
1097 return mapslot;
1098 }
1099
1100
1101 /**
1102 * Makes a deep copy of {@code from} into {@code jsrInfo.extraUnusualMap}
1103 * @param from
1104 */
1105 private void unusualMapcopy(UnusualMaps from) {
1106 jsrInfo.extraUnusualMap.setReturnAddressIndex(from.getReturnAddressIndex());
1107 copyBitMap(jsrInfo.extraUnusualMap.getReferenceMapIndex(), from.getReferenceMapIndex());
1108 copyBitMap(jsrInfo.extraUnusualMap.getNonReferenceMapIndex(), from.getNonReferenceMapIndex());
1109 copyBitMap(jsrInfo.extraUnusualMap.getReturnAddressMapIndex(), from.getReturnAddressMapIndex());
1110 }
1111
1112 /**
1113 * Copies a bit map into the extra unusualmap.
1114 * @param extramapindex the index of the map in the jsrInfo.extraUnusualMap ie the "to" map
1115 * @param index he index of the map to copy ie the "from" map
1116 */
1117 private void copyBitMap(int extramapindex, int index) {
1118 if (VM.TraceStkMaps) {
1119 VM.sysWriteln(" copyBitMap from map index = ",
1120 index,
1121 " copyBitMap from value = ",
1122 jsrInfo.unusualReferenceMaps[index]);
1123 }
1124
1125 // copy the map over to the extra map
1126 for (int i = 0; i < bytesPerMap(); i++) {
1127 jsrInfo.unusualReferenceMaps[extramapindex + i] = jsrInfo.unusualReferenceMaps[index + i];
1128 }
1129
1130 if (VM.TraceStkMaps) {
1131 VM.sysWriteln(" extraUnusualBitMap index = ",
1132 extramapindex,
1133 " extraunusualBitMap value = ",
1134 jsrInfo.unusualReferenceMaps[extramapindex]);
1135 }
1136 }
1137
1138 /**
1139 *
1140 * m
1141 * NOTE: while the routine is written to combine 2 jsrInfo.unusualMaps in general
1142 * in reality the target map is always the same ( the jsrInfo.extraUnusualMap)
1143 */
1144
1145 /**
1146 * Merges unusual maps (occurs in nested jsr conditions) by merging each nested
1147 * delta map ( as represented by the jsrMapid of the location site) into the
1148 * jsrInfo.extraUnusualMap where the deltas are accumulated
1149 *
1150 * @param jsrUnusualMapid the delta map's id
1151 * @return merged map
1152 */
1153 private UnusualMaps combineDeltaMaps(int jsrUnusualMapid) {
1154 //get the delta unusualMap
1155 UnusualMaps deltaMap = jsrInfo.unusualMaps[jsrUnusualMapid];
1156
1157 // get the map indicies of the inner jsr map
1158 int reftargetindex = jsrInfo.extraUnusualMap.getReferenceMapIndex();
1159 int nreftargetindex = jsrInfo.extraUnusualMap.getNonReferenceMapIndex();
1160 int addrtargetindex = jsrInfo.extraUnusualMap.getReturnAddressMapIndex();
1161
1162 // get the map indices of the outer jsr map
1163 int refdeltaindex = deltaMap.getReferenceMapIndex();
1164 int nrefdeltaindex = deltaMap.getNonReferenceMapIndex();
1165 int addrdeltaindex = deltaMap.getReturnAddressMapIndex();
1166
1167 if (VM.TraceStkMaps) {
1168 // display original maps
1169 VM.sysWriteln("combineDeltaMaps- original ref map id = ", reftargetindex);
1170 VM.sysWrite("combineDeltaMaps- original ref map = ");
1171 for (int i = 0; i < bytesPerMap(); i++) {
1172 VM.sysWrite(jsrInfo.unusualReferenceMaps[reftargetindex + i]);
1173 }
1174 VM.sysWriteln();
1175 VM.sysWriteln("combineDeltaMaps- original nref map id = ", nreftargetindex);
1176 VM.sysWrite("combineDeltaMaps original nref map = ");
1177 for (int i = 0; i < bytesPerMap(); i++) {
1178 VM.sysWrite(jsrInfo.unusualReferenceMaps[nreftargetindex + i]);
1179 }
1180 VM.sysWriteln();
1181 VM.sysWriteln("combineDeltaMaps- original retaddr map id = ", addrtargetindex);
1182 VM.sysWrite("combineDeltaMaps original retaddr map = ");
1183 for (int i = 0; i < bytesPerMap(); i++) {
1184 VM.sysWrite(jsrInfo.unusualReferenceMaps[addrtargetindex + i]);
1185 }
1186 VM.sysWriteln();
1187
1188 VM.sysWriteln("combineDeltaMaps- delta ref map id = ", refdeltaindex);
1189 VM.sysWrite("combineDeltaMaps- original delta ref map = ");
1190 for (int i = 0; i < bytesPerMap(); i++) {
1191 VM.sysWrite(jsrInfo.unusualReferenceMaps[refdeltaindex + i]);
1192 }
1193 VM.sysWriteln();
1194 VM.sysWriteln("combineDeltaMaps- delta nref map id = ", nrefdeltaindex);
1195 VM.sysWrite("combineDeltaMaps original delta nref map = ");
1196 for (int i = 0; i < bytesPerMap(); i++) {
1197 VM.sysWrite(jsrInfo.unusualReferenceMaps[nrefdeltaindex + i]);
1198 }
1199 VM.sysWriteln();
1200 VM.sysWriteln("combineDeltaMaps- delta retaddr map id = ", addrdeltaindex);
1201 VM.sysWrite("combineDeltaMaps original delta retaddr map = ");
1202 for (int i = 0; i < bytesPerMap(); i++) {
1203 VM.sysWrite(jsrInfo.unusualReferenceMaps[addrdeltaindex + i]);
1204 }
1205 VM.sysWriteln();
1206
1207 // display indices
1208 VM.sysWriteln("combineDeltaMaps- ref target mapid = ", reftargetindex);
1209 VM.sysWriteln(" ref delta mapid = ", refdeltaindex);
1210 VM.sysWriteln("combineDeltaMaps- NONref target mapid = ", nreftargetindex);
1211 VM.sysWriteln(" NONref delta mapid = ", nrefdeltaindex);
1212 VM.sysWriteln("combineDeltaMaps- retaddr target mapid = ", addrtargetindex);
1213 VM.sysWriteln(" retaddr delta mapid = ", addrdeltaindex);
1214 VM.sysWriteln(" jsrInfo.tempIndex = ", jsrInfo.tempIndex);
1215 }
1216
1217 // merge the reference maps
1218 mergeMap(jsrInfo.tempIndex, reftargetindex, MergeOperation.COPY); // save refs made in inner jsr sub(s)
1219 mergeMap(reftargetindex, refdeltaindex, MergeOperation.OR); // get refs from outer loop
1220 mergeMap(reftargetindex, nreftargetindex, MergeOperation.NAND); // turn off non refs made in inner jsr sub(s)
1221 mergeMap(reftargetindex, addrtargetindex, MergeOperation.NAND); // then the return adresses
1222 mergeMap(reftargetindex, jsrInfo.tempIndex, MergeOperation.OR); // OR inrefs made in inner jsr sub(s)
1223
1224 // merge the non reference maps
1225 mergeMap(jsrInfo.tempIndex, nreftargetindex, MergeOperation.COPY); // save nonrefs made in inner loop(s)
1226 mergeMap(nreftargetindex, nrefdeltaindex, MergeOperation.OR); // get nrefs from outer loop
1227 mergeMap(nreftargetindex, reftargetindex, MergeOperation.NAND); // turn off refs made in inner jsr sub(s)
1228 mergeMap(nreftargetindex, addrtargetindex, MergeOperation.NAND); // then the return adresses
1229 mergeMap(nreftargetindex, jsrInfo.tempIndex, MergeOperation.OR); // OR in non refs made in inner jsr sub(s)
1230
1231 // merge return address maps
1232 mergeMap(addrtargetindex, addrdeltaindex, MergeOperation.OR);
1233
1234 if (VM.TraceStkMaps) {
1235 //display final maps
1236 VM.sysWrite("setupjsrmap-combineDeltaMaps- merged ref map = ");
1237 for (int i = 0; i < bytesPerMap(); i++) {
1238 VM.sysWrite(jsrInfo.unusualReferenceMaps[reftargetindex + i]);
1239 }
1240 VM.sysWriteln();
1241 VM.sysWrite("setupjsrmap-combineDeltaMaps- merged nonref map = ");
1242 for (int i = 0; i < bytesPerMap(); i++) {
1243 VM.sysWrite(jsrInfo.unusualReferenceMaps[nreftargetindex + i]);
1244 }
1245 VM.sysWriteln();
1246 VM.sysWrite("setupjsrmap-combineDeltaMaps- merged retaddr map = ");
1247 for (int i = 0; i < bytesPerMap(); i++) {
1248 VM.sysWrite(jsrInfo.unusualReferenceMaps[addrtargetindex + i]);
1249 }
1250 VM.sysWriteln();
1251 }
1252
1253 return jsrInfo.extraUnusualMap;
1254 }
1255
1256 /**
1257 * Merges a delta map into a target map.
1258 *
1259 * @param targetindex the delta map's index in the reference map table
1260 * @param deltaindex the target map's index in the reference map tbale
1261 * @param Op the merge operation to use
1262 */
1263 private void mergeMap(int targetindex, int deltaindex, MergeOperation Op) {
1264 int i;
1265 // Merge the maps
1266 if (Op == MergeOperation.COPY) {
1267 for (i = 0; i < bytesPerMap(); i++) {
1268 jsrInfo.unusualReferenceMaps[targetindex + i] = jsrInfo.unusualReferenceMaps[deltaindex + i];
1269 }
1270 }
1271 if (Op == MergeOperation.OR) {
1272 for (i = 0; i < bytesPerMap(); i++) {
1273 jsrInfo.unusualReferenceMaps[targetindex + i] =
1274 (byte) (jsrInfo.unusualReferenceMaps[targetindex + i] | jsrInfo.unusualReferenceMaps[deltaindex + i]);
1275 }
1276 }
1277 if (Op == MergeOperation.NAND) {
1278 for (i = 0; i < bytesPerMap(); i++) {
1279 short temp = (byte) (~(jsrInfo.unusualReferenceMaps[deltaindex + i]));
1280 jsrInfo.unusualReferenceMaps[targetindex + i] = (byte) (jsrInfo.unusualReferenceMaps[targetindex + i] & temp);
1281 }
1282 }
1283 }
1284
1285 /**
1286 * This method will merge the jsr invoker's base map with changes
1287 * due to *all* nested jsr subroutines.<p>
1288 *
1289 * The nested jsr subroutine maps were merged into a single delta
1290 * map prior to the calling of this method. We therefore know that
1291 * the base map can never be due to a subroutine (since all
1292 * subroutines have been merged), and therefore that there are no
1293 * return address maps due to the invoker (since return addresses
1294 * are only due to the subroutine maps).
1295 *
1296 * @param jsrBaseMapIndex The map index for the invoker
1297 * @param deltaMap The map for the invoked subroutine/s (all nested
1298 * subroutine maps are guaranteed to have been combined prior to
1299 * calling this)
1300 */
1301 private void finalMergeMaps(int jsrBaseMapIndex, UnusualMaps deltaMap) {
1302 int i;
1303
1304 /* clear out the destination (merged) maps */
1305 for (i = 0; i < bytesPerMap(); i++) {
1306 jsrInfo.unusualReferenceMaps[jsrInfo.mergedReferenceMap + i] = 0;
1307 jsrInfo.unusualReferenceMaps[jsrInfo.mergedReturnAddressMap + i] = 0;
1308 }
1309
1310 /* get the indices of the maps for the combined subroutine map */
1311 int refMapIndex = deltaMap.getReferenceMapIndex();
1312 int nonRefMapIndex = deltaMap.getNonReferenceMapIndex();
1313 int returnAddressMapIndex = deltaMap.getReturnAddressMapIndex();
1314
1315 /* merge the subroutine delta map into the invoker (base) map */
1316 for (i = 0; i < bytesPerMap(); i++) {
1317 /* first establish the change in the maps due to the combined subroutines */
1318 byte deltaRef = jsrInfo.unusualReferenceMaps[refMapIndex + i];
1319 byte deltaNonRef = jsrInfo.unusualReferenceMaps[nonRefMapIndex + i];
1320 byte deltaRtnAddr = jsrInfo.unusualReferenceMaps[returnAddressMapIndex + i];
1321 byte deltaAny = (byte) (deltaRef | deltaNonRef | deltaRtnAddr);
1322
1323 /* There is no merging to be done for the return address map
1324 * since the invoker cannot have any return addressses since it
1325 * is guaranteed not to be a subroutine (and only subroutines
1326 * can generate return address map entries) */
1327 jsrInfo.unusualReferenceMaps[jsrInfo.mergedReturnAddressMap + i] = deltaRtnAddr;
1328
1329 /* Get the base reference map (the high bit is used to denote jsr) */
1330 byte thisBase = referenceMaps[jsrBaseMapIndex + i];
1331 byte nextBase = (i + 1 < bytesPerMap()) ? referenceMaps[jsrBaseMapIndex + i + 1] : 0;
1332 byte baseRef = (byte) ((thisBase << 1) | ((0xff & nextBase) >>> 7));
1333
1334 /* Merge the reference maps */
1335 byte mergedRef = (byte) (deltaRef | (baseRef & ~deltaAny));
1336 jsrInfo.unusualReferenceMaps[jsrInfo.mergedReferenceMap + i] = mergedRef;
1337
1338 /*
1339 VM.sysWrite(" **** thisBase = "); VM.sysWrite(thisBase);
1340 VM.sysWrite(" nextBase = "); VM.sysWrite(nextBase);
1341 VM.sysWrite(" deltaRef = "); VM.sysWrite(deltaRef);
1342 VM.sysWrite(" deltaNonRef = "); VM.sysWrite(deltaNonRef);
1343 VM.sysWrite(" base = "); VM.sysWrite(base);
1344 VM.sysWrite(" newRef = "); VM.sysWrite(newRef);
1345 VM.sysWrite("\n");
1346 */
1347 }
1348
1349 if (VM.TraceStkMaps) {
1350 //Note: this displays each byte as a word ... only look at low order byte
1351 VM.sysWrite("finalmergemaps-jsr total set2ref delta map = ");
1352 for (i = 0; i < bytesPerMap(); i++) {
1353 VM.sysWrite(jsrInfo.unusualReferenceMaps[refMapIndex + i]);
1354 }
1355 VM.sysWrite("\n");
1356
1357 VM.sysWrite(" -jsr total set2nonref delta map = ");
1358 for (i = 0; i < bytesPerMap(); i++) {
1359 VM.sysWrite(jsrInfo.unusualReferenceMaps[nonRefMapIndex + i]);
1360 }
1361 VM.sysWrite("\n");
1362
1363 VM.sysWrite(" -jsr base map = ");
1364 for (i = 0; i < bytesPerMap(); i++)
1365 // ORIGINAL VM.sysWrite( jsrInfo.unusualReferenceMaps[jsrBaseMapIndex + i]);
1366 {
1367 VM.sysWrite(referenceMaps[jsrBaseMapIndex + i]);
1368 }
1369 VM.sysWrite("\n");
1370
1371 VM.sysWrite(" -combined merged ref map = ");
1372 for (i = 0; i < bytesPerMap(); i++) {
1373 VM.sysWrite(jsrInfo.unusualReferenceMaps[jsrInfo.mergedReferenceMap + i]);
1374 }
1375 VM.sysWrite("\n");
1376
1377 VM.sysWrite(" -combined merged return address map = ");
1378 for (i = 0; i < bytesPerMap(); i++) {
1379 VM.sysWrite(jsrInfo.unusualReferenceMaps[jsrInfo.mergedReturnAddressMap + i]);
1380 }
1381 VM.sysWrite("\n");
1382 }
1383 }
1384
1385 /**
1386 * This routine is used to clean out the MethodMap of structures that
1387 * were allocated from temporary storage. Temporary storage is freed up
1388 * between stack frames as the GC scans the stack.
1389 */
1390 public void cleanupPointers() {
1391 if (VM.TraceStkMaps) VM.sysWrite("ReferenceMaps- cleanupPointers\n");
1392 }
1393
1394 /**
1395 * This routine is used to find an Unusual map with an index
1396 * greater than 127
1397 *
1398 */
1399
1400 /**
1401 * Finds an unsual map with an index greater than 127. It returns the index
1402 * by doing a sequential scan and looking for the mapid in the normal map
1403 * directory.
1404 *
1405 * @param mapid the map's id
1406 * @return the map's index
1407 */
1408 int findUnusualMap(int mapid) {
1409 int i;
1410 // Greater than 127 map sites- can't use direct index.
1411 // Do sequential scan for rest of maps. It's slow but should almost never
1412 // happen.
1413
1414 for (i = JSR_INDEX_MASK; i < jsrInfo.numberUnusualMaps; i++) {
1415 if (jsrInfo.unusualMaps[i].getNormalMapIndex() == mapid) {
1416 break;
1417 }
1418 }
1419 if (i >= jsrInfo.numberUnusualMaps) {
1420 VM.sysFail(" can't find jsr map - PANIC !!!!");
1421 }
1422 return i;
1423 }
1424
1425 /**
1426 * Shows the basic information for each of the maps.
1427 * This is for testing use.
1428 */
1429 public void showInfo() {
1430 VM.sysWriteln("showInfo- reference maps");
1431 if (MCSites == null) {
1432 VM.sysWrite(" no MCSites array - assume using cached data - can't do showInfo()");
1433 return;
1434 }
1435
1436 VM.sysWrite(" MCSites.length = ", MCSites.length);
1437 VM.sysWrite(" mapCount = ", mapCount);
1438 // VM.sysWriteln(" startLocal0Offset = ", startLocal0Offset);
1439
1440 for (int i = 0; i < mapCount; i++) {
1441 VM.sysWrite("mapid = ", i);
1442 VM.sysWrite(" - machine code offset ", MCSites[i]);
1443 VM.sysWrite(" -reference Map = ");
1444 for (int j = 0; j < bytesPerMap(); j++) {
1445 VM.sysWriteHex(referenceMaps[(i * bytesPerMap()) + j]);
1446 }
1447 VM.sysWriteln();
1448 }
1449 }
1450
1451 /**
1452 * Show the basic information for a single map. This is for testing
1453 * use.
1454 */
1455 public void showAMap(int MCSiteIndex) {
1456 VM.sysWriteln("show the map for MCSite index= ", MCSiteIndex);
1457 VM.sysWrite("machine code offset = ", MCSites[MCSiteIndex]);
1458 VM.sysWrite(" reference Map = ");
1459 for (int i = 0; i < bytesPerMap(); i++) {
1460 VM.sysWrite(referenceMaps[(MCSiteIndex * bytesPerMap()) + i]);
1461 }
1462 VM.sysWriteln();
1463 }
1464
1465 /**
1466 * Show the offsets for all the maps. This is for test use.
1467 */
1468 public void showOffsets() {
1469 VM.sysWrite("in showOffset- #maps = ");
1470 VM.sysWrite(mapCount);
1471 VM.sysWrite("\n");
1472 int i, tindex = 0;
1473
1474 if (mapCount == 0) {
1475 VM.sysWrite(" no maps for method");
1476 return;
1477 }
1478 for (i = 0; i < mapCount; i++) {
1479 tindex = getNextRefIndex(tindex, i);
1480 VM.sysWrite("initial offset = ");
1481 VM.sysWrite(tindex);
1482 VM.sysWrite(" for map ");
1483 VM.sysWrite(i);
1484 VM.sysWrite("\n");
1485 while (tindex != 0) {
1486 tindex = getNextRefIndex(tindex, i);
1487 VM.sysWrite("next offset = ");
1488 VM.sysWrite(tindex);
1489 if (tindex == 0) VM.sysWrite("---------------- end of map");
1490 }
1491 }
1492 }
1493
1494 @Interruptible
1495 public int showReferenceMapStatistics(RVMMethod method) {
1496 int index = 0;
1497 int totalCount = 0;
1498 int count;
1499
1500 VM.sysWrite("-- Number of refs for method = ");
1501 VM.sysWrite(method.getDeclaringClass().getDescriptor());
1502 VM.sysWrite(".");
1503 VM.sysWrite(method.getName());
1504 VM.sysWrite("---------------------------\n");
1505
1506 for (int i = 0; i < mapCount; i++) {
1507 byte mapindex = referenceMaps[i * bytesPerMap()];
1508 if (mapindex < 0) {
1509 // check for non jsr map
1510 VM.sysWrite(" -----skipping jsr map------- \n ");
1511 continue;
1512 }
1513 index = getNextRefIndex(index, i);
1514 count = 0;
1515 while (index != 0) {
1516 totalCount++;
1517 count++;
1518 index = getNextRefIndex(index, i);
1519 // display number of refs at each site - very noisy
1520 if (index == 0) {
1521 VM.sysWriteln(" -----map machine code offset = ", MCSites[i], " number of refs in this map = ", count);
1522 }
1523 }
1524 }
1525 VM.sysWrite("----- Total number of refs in method = ");
1526 VM.sysWrite(totalCount);
1527 VM.sysWrite(" total number of maps in method = ");
1528 VM.sysWrite(mapCount);
1529 VM.sysWrite("\n");
1530
1531 return totalCount;
1532 }
1533
1534 /* Interface for general queries such as given a GC point, if a stack slot
1535 * or a local variable is a reference.
1536 */
1537
1538 /**
1539 * Query if a local variable has a reference type value
1540 * @param method The method we're asking about.
1541 * @param mcoff The machine code offset of the instruction *following* the
1542 * actual instruction.
1543 * @param lidx the local index
1544 * @return {@code true}, if it is a reference type. {@code false}, otherwise
1545 */
1546 public boolean isLocalRefType(RVMMethod method, Offset mcoff, int lidx) {
1547 int bytenum, bitnum;
1548 byte[] maps;
1549
1550 if (bytesPerMap() == 0) return false; // no map ie no refs
1551 int mapid = locateGCPoint(mcoff, method);
1552
1553 if (mapid >= 0) {
1554 // normal case
1555 bytenum = mapid * bytesPerMap();
1556 bitnum = lidx + 1 + 1; // 1 for being 1 based +1 for jsr bit
1557 maps = referenceMaps;
1558 } else {
1559 // in JSR
1560 bytenum = jsrInfo.mergedReferenceMap;
1561 bitnum = lidx + 1; // 1 for being 1 based
1562 maps = jsrInfo.unusualReferenceMaps;
1563 }
1564
1565 // adjust bitnum and wordnum to bit within word
1566 while (bitnum > BITS_PER_MAP_ELEMENT) {
1567 bytenum++;
1568 bitnum -= BITS_PER_MAP_ELEMENT;
1569 }
1570
1571 int mask = (1 << (BITS_PER_MAP_ELEMENT - bitnum)); // generate mask
1572
1573 return ((mask & maps[bytenum]) != 0);
1574 }
1575 }