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