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.osr;
014
015 import java.util.ArrayList;
016 import java.util.Arrays;
017 import java.util.Comparator;
018 import java.util.LinkedList;
019 import org.jikesrvm.ArchitectureSpecificOpt.OptGCMapIteratorConstants;
020 import org.jikesrvm.VM;
021 import org.jikesrvm.compilers.opt.inlining.CallSiteTree;
022 import org.jikesrvm.compilers.opt.ir.Instruction;
023 import org.vmmagic.pragma.Inline;
024 import org.vmmagic.unboxed.Offset;
025
026 /**
027 * EncodedOSRMap provides the similar function as GC map
028 * in OptMachineCodeMap.
029 * <p>
030 * In OptCompiledMethod, an instance of this class will represent
031 * all OSR map info for that method.
032 */
033 public final class EncodedOSRMap implements OptGCMapIteratorConstants, OSRConstants {
034
035 /** osr info entries */
036 private final long[] mapEntries;
037
038 /** the last entry index. */
039 private final int lastEntry;
040
041 /** the OSR map */
042 private final int[] osrMaps;
043
044 /** map used when there are no OSR instructions */
045 private static final EncodedOSRMap emptyMap = new EncodedOSRMap();
046
047 @Inline
048 public static boolean registerIsSet(int map, int regnum) {
049 int bitpos = getRegBitPosition(regnum);
050 return (map & (NEXT_BIT >>> bitpos)) > 0;
051 }
052
053 /**
054 * mark a register as reference type
055 */
056 private static int setRegister(int map, int regnum) {
057 int bitpos = getRegBitPosition(regnum);
058 map |= (NEXT_BIT >>> bitpos);
059 return map;
060 }
061
062 /**
063 * get register bit position
064 */
065 @Inline
066 private static int getRegBitPosition(int regnum) {
067 return regnum - FIRST_GCMAP_REG + 1;
068 }
069
070 /** Constructor to build empty map */
071 private EncodedOSRMap() {
072 this.mapEntries = null;
073 this.osrMaps = null;
074 this.lastEntry = -1;
075 }
076
077 /** Constructor that builds EncodedOSRMap from variable map */
078 private EncodedOSRMap(VariableMap varMap) {
079 int entries = varMap.getNumberOfElements();
080
081 this.lastEntry = entries - 1;
082
083 if (VM.VerifyAssertions) VM._assert(entries > 0);
084 this.mapEntries = new long[entries];
085 ArrayList<Integer> tempOsrMaps = new ArrayList<Integer>();
086 translateMap(tempOsrMaps, varMap.list);
087 this.osrMaps = new int[tempOsrMaps.size()];
088 for (int i=0; i < tempOsrMaps.size(); i++) {
089 this.osrMaps[i] = tempOsrMaps.get(i);
090 }
091
092 //if (VM.TraceOnStackReplacement) {
093 // printMap();
094 //}
095 }
096
097 /**
098 * Encode the given variable map returning the canonical empty map if the map
099 * is empty
100 */
101 public static EncodedOSRMap makeMap(VariableMap varMap) {
102 if (varMap.getNumberOfElements() > 0) {
103 return new EncodedOSRMap(varMap);
104 } else {
105 return emptyMap;
106 }
107 }
108
109 /**
110 * Translates a list of OSR_MapElement to encoding,
111 * we can not trust the osrlist is in the increasing order of
112 * machine code offset. Sort it first.
113 */
114 private void translateMap(ArrayList<Integer> tempOsrMaps, LinkedList<VariableMapElement> osrlist) {
115
116 /* sort the list, use the mc offset of the index instruction
117 * as the key.
118 */
119 int n = osrlist.size();
120
121 VariableMapElement[] osrarray = new VariableMapElement[n];
122 for (int i = 0; i < n; i++) {
123 osrarray[i] = osrlist.get(i);
124 }
125
126 /* ideally, the osrList should be in sorted order by MC offset,
127 * but I got once it is not in the order. To work correctly,
128 * sort it first.
129 *
130 * TODO: figure out why LiveAnalysis does not give correct order?
131 */
132 if (n > 1) {
133 Arrays.sort(osrarray,
134 new Comparator<VariableMapElement>() {
135 @Override
136 public int compare(VariableMapElement a, VariableMapElement b) {
137 return a.osr.getmcOffset() - b.osr.getmcOffset();
138 }
139 });
140 }
141 CallSiteTree inliningTree = new CallSiteTree();
142 for (int i = 0; i < n; i++) {
143 Instruction instr = osrarray[i].osr;
144 // add lining element, move sanity later
145 if (instr.position != null) {
146 inliningTree.addLocation(instr.position);
147 }
148 }
149
150 for (int i = 0; i < n; i++) {
151
152 VariableMapElement elm = osrarray[i];
153 Instruction instr = elm.osr;
154
155 int iei = inliningTree.find(instr.position).encodedOffset;
156 setIEIndex(i, iei);
157
158 // get osr map
159 LinkedList<MethodVariables> mVarList = elm.mvars;
160 int osrMapIndex = generateOsrMaps(tempOsrMaps, mVarList);
161
162 // use this offset, and adjust on extractState
163 int mcOffset = instr.getmcOffset();
164 setMCOffset(i, mcOffset);
165 setOSRMapIndex(i, osrMapIndex);
166 setBCIndex(i, instr.getBytecodeIndex());
167 }
168 }
169
170 /**
171 * Generate value in the Osr map,
172 * return the index of the first integer in the map.
173 * <p>
174 * An OSR Map has following structure:
175 * <pre>
176 * | regmap || mid, mpc, (n1, n2) ... ||
177 * || mid, mpc, (n1, n2) ... ||
178 * </pre>
179 * Regmap indicates the value of which register is a reference,
180 * the execution state extractor can convert the value to an
181 * object to avoid confusing GC.
182 * The MSB of regmap indicates next mid is valid.
183 * <p>
184 * The MSB of mid indicates if the next mid item will be
185 * available.
186 * <p>
187 * The MSB of mpc indicates if the next is a valid pair
188 */
189 private int generateOsrMaps(ArrayList<Integer> tempOsrMaps, LinkedList<MethodVariables> mVarList) {
190
191 int regmap = (!mVarList.isEmpty()) ? NEXT_BIT : 0;
192 tempOsrMaps.add(regmap);
193 int mapIndex = tempOsrMaps.size()-1;
194
195 // from inner to outer
196 for (int i = 0, m = mVarList.size(); i < m; i++) {
197 MethodVariables mVar = mVarList.get(i);
198 _generateMapForOneMethodVariable(tempOsrMaps, mapIndex, mVar, (i == (m - 1)));
199 }
200
201 return mapIndex;
202 }
203
204 /**
205 * Generate value in the Osr map
206 * @param tempOsrMaps the maps under construction
207 * @param regMapIndex used to patch the register map
208 * @param mVar the method variables
209 * @param lastMid
210 */
211 private void _generateMapForOneMethodVariable(ArrayList<Integer> tempOsrMaps, int regMapIndex, MethodVariables mVar, boolean lastMid) {
212 // Is this the last method in the inlined chain?
213 int mid = lastMid ? mVar.methId : (mVar.methId | NEXT_BIT);
214 tempOsrMaps.add(mid);
215
216 LinkedList<LocalRegPair> tupleList = mVar.tupleList;
217 int m = tupleList.size();
218
219 // Is this method has variables?
220 int bci = (m == 0) ? mVar.bcIndex : (mVar.bcIndex | NEXT_BIT);
221 tempOsrMaps.add(bci);
222
223 // append each element
224 for (int j = 0; j < m; j++) {
225 LocalRegPair tuple = tupleList.get(j);
226
227 boolean isLast = (j == m - 1);
228
229 processTuple(tempOsrMaps, tuple, isLast);
230 // mark the reg ref map
231 if (((tuple.typeCode == ClassTypeCode) || (tuple.typeCode == ArrayTypeCode)) && (tuple.valueType == PHYREG)) {
232 tempOsrMaps.set(regMapIndex, setRegister(tempOsrMaps.get(regMapIndex), tuple.value.toInt()));
233 }
234 }
235 }
236
237 /**
238 * Process on 32-bit tuple.
239 * <p>
240 * tuple, maps the local to register, spill
241 * isLast, indicates to set NEXT_BIT
242 */
243 private void processTuple(ArrayList<Integer> tempOsrMaps, LocalRegPair tuple, boolean isLast) {
244
245 int first = (tuple.num << NUM_SHIFT) & NUM_MASK;
246
247 if (!isLast) {
248 first |= NEXT_BIT;
249 }
250
251 first |= (tuple.kind ? 1 : 0) << KIND_SHIFT;
252
253 first |= (tuple.valueType << VTYPE_SHIFT);
254
255 switch (tuple.typeCode) {
256 case BooleanTypeCode:
257 case ByteTypeCode:
258 case CharTypeCode:
259 case ShortTypeCode:
260 case IntTypeCode:
261 first |= (INT << TCODE_SHIFT);
262 break;
263 case FloatTypeCode:
264 first |= (FLOAT << TCODE_SHIFT);
265 break;
266 case DoubleTypeCode:
267 first |= (DOUBLE << TCODE_SHIFT);
268 break;
269 case LongTypeCode:
270 if (VM.BuildFor32Addr || (tuple.valueType == LCONST)) {
271 // split in two integer parts for OSR map
272 // process the first half part,
273 // it is not the last.
274 first |= NEXT_BIT;
275 first |= (HIGH_64BIT << TCODE_SHIFT);
276
277 // add first word
278 tempOsrMaps.add(first);
279 // add the second word
280
281 if (VM.BuildFor64Addr) {
282 tempOsrMaps.add(tuple.value.rshl(32).toInt());
283 } else {
284 tempOsrMaps.add(tuple.value.toInt());
285 tuple = tuple._otherHalf;
286 }
287 // process the second half part,
288 // it may be the last, and it is not the first half.
289 first = (tuple.num << NUM_SHIFT) & NUM_MASK;
290
291 if (!isLast) first |= NEXT_BIT;
292
293 first |= (tuple.kind ? 1 : 0) << KIND_SHIFT;
294 first |= (tuple.valueType << VTYPE_SHIFT);
295 }
296 first |= (LONG << TCODE_SHIFT);
297 break;
298 case ReturnAddressTypeCode:
299
300 if (false) {
301 VM.sysWrite("returnaddress type for ");
302 if (tuple.kind == LOCAL) {
303 VM.sysWrite("L" + tuple.num);
304 } else {
305 VM.sysWrite("S" + tuple.num);
306 }
307 VM.sysWrite("\n");
308 }
309
310 first |= (RET_ADDR << TCODE_SHIFT);
311 break;
312 case WordTypeCode:
313 if (VM.BuildFor64Addr && (tuple.valueType == ICONST)) {//KV:TODO
314 //split in two integer parts for OSR map
315 // process the first half part,
316 // it is not the last. */
317 first |= NEXT_BIT;
318 first |= (HIGH_64BIT << TCODE_SHIFT);
319
320 // add first word
321 tempOsrMaps.add(first);
322 // add the second word
323 tempOsrMaps.add(tuple.value.rshl(32).toInt());
324
325 // process the second half part,
326 // it may be the last, and it is not the first half.
327 first = (tuple.num << NUM_SHIFT) & NUM_MASK;
328 if (!isLast) first |= NEXT_BIT;
329 first |= (tuple.kind ? 1 : 0) << KIND_SHIFT;
330 first |= (tuple.valueType << VTYPE_SHIFT);
331 }
332 first |= (WORD << TCODE_SHIFT);
333 break;
334 case ClassTypeCode:
335 case ArrayTypeCode:
336 first |= (REF << TCODE_SHIFT);
337 break;
338 }
339
340 // add first word
341 tempOsrMaps.add(first);
342 // add the second word
343 tempOsrMaps.add(tuple.value.toInt());
344 }
345
346 ////////////////////////////////////
347 // INTERFACE
348 ///////////////////////////////////
349 /**
350 * Does the OSR map exist for a machine instruction offset
351 */
352 public boolean hasOSRMap(Offset mcOffset) {
353 int entry = findOSREntry(mcOffset);
354 return (entry != NO_OSR_ENTRY);
355 }
356
357 /* WARNING:
358 * It is the caller's reposibility to make sure there are OSR
359 * entry exist for a machine instruction offset.
360 */
361 /**
362 * Get bytecode index for a given instruction offset in bytes.
363 */
364 public int getBytecodeIndexForMCOffset(Offset mcOffset) {
365 int entry = findOSREntry(mcOffset);
366 return getBCIndex(entry);
367 }
368
369 /* TODO!
370 * get inline encoding index for the machine instruction offset
371 */
372 public int getInlineEncodingForMCOffset(Offset mcOffset) {
373 return -1;
374 }
375
376 /**
377 * get register's reference map for the machine instruction offset
378 */
379 public int getRegisterMapForMCOffset(Offset mcOffset) {
380 int entry = findOSREntry(mcOffset);
381 int mapIndex = getOSRMapIndex(entry);
382 return osrMaps[mapIndex];
383 }
384
385 /**
386 * given a MC offset, return an iterator over the
387 * elements of this map.
388 * NOTE: the map index is gotten from 'findOSRMapIndex'.
389 * This has to be changed....
390 */
391 public OSRMapIterator getOsrMapIteratorForMCOffset(Offset mcOffset) {
392 int entry = findOSREntry(mcOffset);
393 int mapIndex = getOSRMapIndex(entry);
394 return new OSRMapIterator(osrMaps, mapIndex);
395 }
396
397 /////////////////////////////////
398 // private functions
399 ////////////////////////////////
400 /**
401 * Do a binary search, find the entry for the machine code offset.
402 * Return -1 if no entry was found.
403 */
404 private int findOSREntry(Offset mcOffset) {
405
406 int l = 0;
407 int r = lastEntry;
408
409 while (l <= r) {
410 int m = (l + r) >> 1;
411 Offset offset = Offset.fromIntSignExtend(getMCOffset(m));
412 if (offset.EQ(mcOffset)) {
413 return m;
414 } else if (offset.sLT(mcOffset)) {
415 l = m + 1;
416 } else {
417 r = m - 1;
418 }
419 }
420
421 /* this is the place should not be reached, dump OSR content */
422 if (VM.TraceOnStackReplacement) {
423 VM.sysWrite("cannot find map entry for ", mcOffset, "\n");
424 this.printMap();
425 }
426
427 if (VM.VerifyAssertions) VM._assert(VM.NOT_REACHED);
428
429 return NO_OSR_ENTRY;
430 }
431
432 private int getMCOffset(int entry) {
433 return (int) ((mapEntries[entry] & OFFSET_MASK) >>> OFFSET_SHIFT);
434 }
435
436 private int getOSRMapIndex(int entry) {
437 return (int) ((mapEntries[entry] & OSRI_MASK) >>> OSRI_SHIFT);
438 }
439
440 private int getBCIndex(int entry) {
441 return (int) ((mapEntries[entry] & BCI_MASK) >>> BCI_SHIFT);
442 }
443
444 @SuppressWarnings("unused")
445 // Here for completeness (RJG ??)
446 private int getIEIndex(int entry) {
447 return (int) ((mapEntries[entry] & IEI_MASK) >>> IEI_SHIFT);
448 }
449
450 private void setMCOffset(int entry, int offset) {
451 mapEntries[entry] = (mapEntries[entry] & ~OFFSET_MASK) | (((long) offset) << OFFSET_SHIFT);
452 }
453
454 private void setOSRMapIndex(int entry, int index) {
455 mapEntries[entry] = (mapEntries[entry] & ~OSRI_MASK) | (((long) index) << OSRI_SHIFT);
456 }
457
458 private void setBCIndex(int entry, int index) {
459 mapEntries[entry] = (mapEntries[entry] & ~BCI_MASK) | (((long) index) << BCI_SHIFT);
460 }
461
462 private void setIEIndex(int entry, int index) {
463 mapEntries[entry] = (mapEntries[entry] & ~IEI_MASK) | (((long) index) << IEI_SHIFT);
464 }
465
466 /**
467 * print the encoded map for debugging.
468 */
469 public void printMap() {
470 if (lastEntry > 0) {
471 VM.sysWrite("On-stack-replacement maps:\n");
472 }
473 for (int i = 0; i <= lastEntry; i++) {
474 VM.sysWrite("Entry " + i + " : ");
475 int mapIndex = getOSRMapIndex(i);
476 VM.sysWrite(" mapIndex " + mapIndex + ", ");
477 int mcOffset = getMCOffset(i);
478 VM.sysWrite(" mc " + mcOffset + ", ");
479 int bcIndex = getBCIndex(i);
480 VM.sysWriteln("bc " + bcIndex);
481
482 /*
483 for (int j=0; j<osrMaps.length; j++) {
484 VM.sysWriteHex(osrMaps[j]);VM.sysWrite(" ");
485 }
486 VM.sysWrite("\n");
487 */
488
489 // register map
490 int regmap = osrMaps[mapIndex] & ~NEXT_BIT;
491 VM.sysWrite("regmap: " + Integer.toBinaryString(regmap));
492
493 OSRMapIterator iterator = new OSRMapIterator(osrMaps, mapIndex);
494
495 while (iterator.hasMore()) {
496 VM.sysWrite("(" + iterator.getValueType() + "," + iterator.getValue() + ")");
497 iterator.moveToNext();
498 }
499 VM.sysWrite("\n");
500 }
501 }
502
503 public int[] getMCIndexes() {
504 int[] indexes = new int[mapEntries.length];
505 for (int i = 0, n = mapEntries.length; i < n; i++) {
506 indexes[i] = getMCOffset(i);
507 }
508
509 return indexes;
510 }
511 }