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