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.compilers.opt.runtimesupport; 014 015import static org.jikesrvm.compilers.opt.driver.OptConstants.INSTRUMENTATION_BCI; 016import static org.jikesrvm.compilers.opt.driver.OptConstants.UNKNOWN_BCI; 017import static org.jikesrvm.compilers.opt.ir.Operators.IR_PROLOGUE_opcode; 018 019import java.util.ArrayList; 020 021import org.jikesrvm.VM; 022import org.jikesrvm.adaptive.database.callgraph.CallSite; 023import org.jikesrvm.architecture.ArchConstants; 024import org.jikesrvm.classloader.MemberReference; 025import org.jikesrvm.classloader.NormalMethod; 026import org.jikesrvm.classloader.RVMArray; 027import org.jikesrvm.classloader.RVMMethod; 028import org.jikesrvm.classloader.TypeReference; 029import org.jikesrvm.compilers.opt.OptimizingCompilerException; 030import org.jikesrvm.compilers.opt.inlining.CallSiteTree; 031import org.jikesrvm.compilers.opt.ir.GCIRMap; 032import org.jikesrvm.compilers.opt.ir.GCIRMapElement; 033import org.jikesrvm.compilers.opt.ir.IR; 034import org.jikesrvm.compilers.opt.ir.Instruction; 035import org.jikesrvm.compilers.opt.ir.operand.MethodOperand; 036import org.jikesrvm.compilers.opt.mir2mc.MachineCodeOffsets; 037import org.vmmagic.pragma.Inline; 038import org.vmmagic.pragma.Uninterruptible; 039import org.vmmagic.unboxed.Offset; 040 041/** 042 * A class that encapsulates mapping information about generated machine code. 043 * Since there will be an instance of this class with every OptCompiledMethod, 044 * we attempt to pack the data into a reasonably small number of bits. 045 * 046 * <p> The supported functions are: 047 * <ul> 048 * <li> (1) Map from a machine code offset to a GC map (register & stack map). 049 * <li> (2) Map from machinecode offset to <method, bcIndex> pair. 050 * Used for: 051 * <ul> 052 * <li> dynamic linking 053 * <li> lazy compilation 054 * <li> adaptive system profiling 055 * </ul> 056 * <li> (3) Map from a machine code offset to a tree of <method, bcIndex> pairs 057 * that encodes the inlining sequence. 058 * Used for: 059 * <ul> 060 * <li> IPA 061 * <li> stack inspection (print stack trace, 062 * security manager, etc). 063 * <li> general debugging support. 064 * <li> adaptive system profiling 065 * </ul> 066 *</ul> 067 *<p> 068 * Note: This file contains two types of methods 069 * <ul> 070 * <li>1) methods called during compilation to create the maps 071 * <li>2) methods called at GC time (no allocation allowed!) 072 * </ul> 073 */ 074public final class OptMachineCodeMap { 075 076 private OptMachineCodeMap(int[] _MCInformation, int[] _gcMaps, int[] _inlineEncoding) { 077 MCInformation = _MCInformation; 078 gcMaps = _gcMaps; 079 inlineEncoding = _inlineEncoding; 080 } 081 082 /** 083 * Creates the map, called during compilation 084 * @param ir the ir object for this method 085 * @param machineCodeSize the number of machine code instructions generated. 086 * @return the created map 087 */ 088 static OptMachineCodeMap create(IR ir, int machineCodeSize) { 089 /** Dump maps as methods are compiled */ 090 final boolean DUMP_MAPS = 091 ir.options.PRINT_GC_MAPS && 092 (!ir.options.hasMETHOD_TO_PRINT() || 093 (ir.options.hasMETHOD_TO_PRINT() && ir.options.fuzzyMatchMETHOD_TO_PRINT(ir.method.toString())) 094 ); 095 /** Dump stats on map size as maps are compiled */ 096 final boolean DUMP_MAP_SIZES = false; 097 if (DUMP_MAPS) { 098 VM.sysWrite("Creating final machine code map for " + ir.method + "\n"); 099 } 100 101 // create all machine code maps 102 MachineCodeOffsets mcOffsets = ir.MIRInfo.mcOffsets; 103 final OptMachineCodeMap map = generateMCInformation(ir.MIRInfo.gcIRMap, DUMP_MAPS, mcOffsets); 104 105 if (DUMP_MAP_SIZES) { 106 map.recordStats(ir.method, 107 map.size(), 108 machineCodeSize << ArchConstants.getLogInstructionWidth(), DUMP_MAP_SIZES); 109 } 110 111 if (DUMP_MAPS) { 112 VM.sysWrite("Final Machine code information:\n"); 113 map.dumpMCInformation(DUMP_MAPS); 114 for (Instruction i = ir.firstInstructionInCodeOrder(); i != null; i = i.nextInstructionInCodeOrder()) { 115 VM.sysWriteln(mcOffsets.getMachineCodeOffset(i) + "\t" + i); 116 } 117 } 118 return map; 119 } 120 121 /** 122 * Get the bytecode index for a machine instruction offset. 123 * 124 * @param MCOffset the machine code offset of interest 125 * @return -1 if unknown. 126 */ 127 @Uninterruptible 128 public int getBytecodeIndexForMCOffset(Offset MCOffset) { 129 int entry = findMCEntry(MCOffset); 130 if (entry == -1) { 131 return -1; 132 } 133 return getBytecodeIndex(entry); 134 } 135 136 /** 137 * Get the RVMMethod for a machine instruction offset. 138 * This method is the source method that the instruction came from. 139 * 140 * @param MCOffset the machine code offset of interest 141 * @return {@code null} if unknown 142 */ 143 @Uninterruptible 144 public NormalMethod getMethodForMCOffset(Offset MCOffset) { 145 int entry = findMCEntry(MCOffset); 146 if (entry == -1) { 147 return null; 148 } 149 int iei = getInlineEncodingIndex(entry); 150 if (iei == -1) { 151 return null; 152 } 153 int mid = OptEncodedCallSiteTree.getMethodID(iei, inlineEncoding); 154 return (NormalMethod) MemberReference.getMethodRef(mid).getResolvedMember(); 155 } 156 157 /** 158 * Return the inlining encoding index for the machine instruction offset. 159 * 160 * @param MCOffset the machine code offset of interest 161 * @return -1 if unknown. 162 */ 163 @Uninterruptible 164 public int getInlineEncodingForMCOffset(Offset MCOffset) { 165 int entry = findMCEntry(MCOffset); 166 if (entry == -1) { 167 return -1; 168 } 169 return getInlineEncodingIndex(entry); 170 } 171 172 /** 173 * This method searches for the GC map corresponding to the 174 * passed machine code offset. 175 * If no map is present, an error has occurred and OptGCMap.ERROR 176 * is returned. 177 * 178 * @param MCOffset the machine code offset to look for 179 * @return the GC map index or OptGCMap.ERROR 180 */ 181 @Uninterruptible 182 public int findGCMapIndex(Offset MCOffset) { 183 int entry = findMCEntry(MCOffset); 184 if (entry == -1) return OptGCMap.ERROR; 185 return getGCMapIndex(entry); 186 } 187 188 /** 189 * @return an arraylist of CallSite objects representing all non-inlined 190 * callsites in the method. Returns null if there are no such callsites. 191 */ 192 public ArrayList<CallSite> getNonInlinedCallSites() { 193 ArrayList<CallSite> ans = null; 194 if (MCInformation == null) return ans; 195 for (int entry = 0; entry < MCInformation.length;) { 196 int callInfo = getCallInfo(entry); 197 if (callInfo == IS_UNGUARDED_CALL) { 198 int bcIndex = getBytecodeIndex(entry); 199 if (bcIndex != -1) { 200 int iei = getInlineEncodingIndex(entry); 201 if (iei != -1) { 202 int mid = OptEncodedCallSiteTree.getMethodID(iei, inlineEncoding); 203 RVMMethod caller = MemberReference.getMemberRef(mid).asMethodReference().peekResolvedMethod(); 204 if (caller != null) { 205 if (ans == null) ans = new ArrayList<CallSite>(); 206 ans.add(new CallSite(caller, bcIndex)); 207 } 208 } 209 } 210 } 211 entry = nextEntry(entry); 212 } 213 return ans; 214 } 215 216 /** 217 * This method searches the machine code maps and determines if 218 * the given call edge is definitely inlined into the method. 219 * NOTE: This current implementation may return false even if the 220 * edge actually was inlined. This happens when no GC point occurs within 221 * the inlined body. This is less than ideal; we need to fix this at some point. 222 * @param caller caller RVMMethod 223 * @param bcIndex bytecode index of the caller method 224 * @param callee callee RVMMethod 225 * @return {@code true} if the call edge is <em>definitely</em> inlined in this compiled method. 226 */ 227 public boolean hasInlinedEdge(RVMMethod caller, int bcIndex, RVMMethod callee) { 228 if (MCInformation == null) return false; 229 if (inlineEncoding == null) return false; 230 return OptEncodedCallSiteTree.edgePresent(caller.getId(), bcIndex, callee.getId(), inlineEncoding); 231 } 232 233 @Uninterruptible 234 public int gcMapInformation(int index) { 235 return OptGCMap.gcMapInformation(index, gcMaps); 236 } 237 238 @Uninterruptible 239 public boolean registerIsSet(int entry, int registerNumber) { 240 return OptGCMap.registerIsSet(entry, registerNumber, gcMaps); 241 } 242 243 /** 244 * @param currentIndex index for current location 245 * @return the next (relative) location or -1 for no more locations 246 */ 247 @Uninterruptible 248 public int nextLocation(int currentIndex) { 249 return OptGCMap.nextLocation(currentIndex, gcMaps); 250 } 251 252 /////////////////////////////////////// 253 // Implementation 254 /////////////////////////////////////// 255 256 /** 257 * Does a binary search of the machine code maps to find the index 258 * in MCInformation where the entry for the argument machine code 259 * offset starts. Will return -1 if the entry doesn't exist. 260 * 261 * @param MCOffset the machine code offset of interest 262 * @return -1 if no entry exists, the index of the matching entry otherwise 263 */ 264 @Uninterruptible 265 private int findMCEntry(Offset MCOffset) { 266 // Given a machine code instruction MCOffset, find the corresponding entry 267 if (MCInformation == null) return -1; 268 if (MCInformation.length == 0) return -1; 269 270 int left = 0; 271 int right = MCInformation.length - 1; 272 while (left <= right) { 273 int middle = (left + right) >> 1; // take the average 274 while ((MCInformation[middle] & START_OF_ENTRY) != START_OF_ENTRY) { 275 // if necessary, step backwards to beginning of entry. 276 middle--; 277 } 278 Offset offset = Offset.fromIntSignExtend(getMCOffset(middle)); 279 if (MCOffset.EQ(offset)) { 280 return middle; 281 } else if (MCOffset.sGT(offset)) { 282 // middle is too small, shift interval to the right 283 left = middle + 1; 284 if (left >= MCInformation.length) return -1; 285 while ((MCInformation[left] & START_OF_ENTRY) != START_OF_ENTRY) { 286 // if necessary, step forward to find next entry, but not passed end 287 // Need to do this to avoid finding middle again 288 left++; 289 if (left >= MCInformation.length) { 290 return -1; 291 } 292 } 293 } else { 294 // middle is too small, shift interval to the left 295 right = middle - 1; 296 // Note no need to adjust as, we won't chance finding middle again 297 } 298 } 299 return -1; 300 } 301 302 private int nextEntry(int entry) { 303 if (isBigEntry(entry)) return entry + SIZEOF_BIG_ENTRY; 304 if (isHugeEntry(entry)) return entry + SIZEOF_HUGE_ENTRY; 305 return entry + SIZEOF_ENTRY; 306 } 307 308 //////////////////////////////////////////// 309 // Create the map (at compile time) 310 //////////////////////////////////////////// 311 312 /** 313 * This method walks the IR map, and for each entry it creates 314 * the machine code mapping information for the entry. 315 * It is called during the compilation of the method, not at GC time. 316 * @param irMap the irmap to translate from 317 * @param DUMP_MAPS dump while we work 318 * @param mcOffsets machine code offset information 319 * @return the machine code map 320 */ 321 private static OptMachineCodeMap generateMCInformation(GCIRMap irMap, boolean DUMP_MAPS, MachineCodeOffsets mcOffsets) { 322 CallSiteTree inliningMap = new CallSiteTree(); 323 int numEntries = 0; 324 325 // (1) Count how many entries we are going to have and 326 // construct and encode the inlining information for those entries. 327 for (GCIRMapElement irMapElem : irMap) { 328 numEntries++; 329 Instruction instr = irMapElem.getInstruction(); 330 if (instr.position == null && instr.bcIndex != INSTRUMENTATION_BCI) { 331 if ((VM.BuildForIA32 && 332 org.jikesrvm.compilers.opt.ir.ia32.MIR_Call.conforms(instr) && 333 org.jikesrvm.compilers.opt.ir.ia32.MIR_Call.hasMethod(instr)) || 334 (VM.BuildForPowerPC && 335 org.jikesrvm.compilers.opt.ir.ppc.MIR_Call.conforms(instr) && 336 org.jikesrvm.compilers.opt.ir.ppc.MIR_Call.hasMethod(instr))) { 337 throw new OptimizingCompilerException("position required for all call instructions " + instr); 338 } 339 } else { 340 inliningMap.addLocation(instr.position); 341 } 342 } 343 344 if (numEntries == 0) return emptyMachineCodeMap; // if no entries, then we are done. 345 346 int[] inlineEncoding = OptEncodedCallSiteTree.getEncoding(inliningMap); 347 348 // (2) Encode the primary machine code mapping information and the GCMaps. 349 OptGCMap gcMapBuilder = new OptGCMap(); 350 int[] tmpMC = new int[numEntries * SIZEOF_HUGE_ENTRY]; 351 int lastMCInfoEntry = 0; 352 for (GCIRMapElement irMapElem : irMap) { 353 Instruction instr = irMapElem.getInstruction(); 354 if (DUMP_MAPS) VM.sysWrite("IR Map for " + instr + "\n\t" + irMapElem); 355 356 // retrieve the machine code offset (in bytes) from the instruction, 357 ensureCorrectMapConstruction(mcOffsets, instr); 358 int mco = mcOffsets.getMachineCodeOffset(instr); 359 360 if (mco < 0) { 361 VM.sysWrite("Negative machine code MCOffset found:" + mco); 362 Instruction i = irMapElem.getInstruction(); 363 int machineCodeOffsetForI = mcOffsets.getMachineCodeOffset(i); 364 VM.sysWrite(i.bcIndex + ", " + i + ", " + machineCodeOffsetForI + "\n"); 365 throw new OptimizingCompilerException("Negative machine code MCOffset found"); 366 } 367 // create GC map and get GCI 368 int gci = gcMapBuilder.generateGCMapEntry(irMapElem); 369 // get bci information 370 int bci = instr.getBytecodeIndex(); 371 if (bci < 0) { 372 if ((bci == UNKNOWN_BCI) && 373 ((VM.BuildForIA32 && 374 org.jikesrvm.compilers.opt.ir.ia32.MIR_Call.conforms(instr) && 375 org.jikesrvm.compilers.opt.ir.ia32.MIR_Call.hasMethod(instr)) || 376 (VM.BuildForPowerPC && 377 org.jikesrvm.compilers.opt.ir.ppc.MIR_Call.conforms(instr) && 378 org.jikesrvm.compilers.opt.ir.ppc.MIR_Call.hasMethod(instr)))) { 379 throw new OptimizingCompilerException("valid bytecode index required for all calls " + instr); 380 } 381 bci = -1; 382 } 383 // get index into inline encoding 384 int iei = -1; 385 if (instr.position != null) { 386 iei = inliningMap.find(instr.position).encodedOffset; 387 } 388 // set the call info 389 int cm = 0; 390 if ((VM.BuildForIA32 && org.jikesrvm.compilers.opt.ir.ia32.MIR_Call.conforms(instr)) || 391 (VM.BuildForPowerPC && org.jikesrvm.compilers.opt.ir.ppc.MIR_Call.conforms(instr))) { 392 MethodOperand mo; 393 if (VM.BuildForIA32) { 394 mo = org.jikesrvm.compilers.opt.ir.ia32.MIR_Call.getMethod(instr); 395 } else { 396 if (VM.VerifyAssertions) VM._assert(VM.BuildForPowerPC); 397 mo = org.jikesrvm.compilers.opt.ir.ppc.MIR_Call.getMethod(instr); 398 } 399 if (mo != null && mo.isGuardedInlineOffBranch()) { 400 cm = IS_GUARDED_CALL; 401 } else { 402 cm = IS_UNGUARDED_CALL; 403 } 404 } 405 406 // Encode this entry into MCInformation 407 if (bci < INVALID_BCI && iei < INVALID_IEI && gci < INVALID_GCI && mco < (OFFSET_MASK >>> OFFSET_SHIFT)) { 408 // use a small entry 409 if (bci == -1) bci = INVALID_BCI; 410 if (iei == -1) iei = INVALID_IEI; 411 if (gci == -1) gci = INVALID_GCI; 412 if (VM.VerifyAssertions) { 413 VM._assert((cm & (CALL_MASK >>> CALL_SHIFT)) == cm); 414 VM._assert((bci & (BCI_MASK >>> BCI_SHIFT)) == bci); 415 VM._assert((iei & (IEI_MASK >>> IEI_SHIFT)) == iei); 416 VM._assert((gci & (GCI_MASK >>> GCI_SHIFT)) == gci); 417 VM._assert((mco & (OFFSET_MASK >>> OFFSET_SHIFT)) == mco); 418 } 419 int t = START_OF_ENTRY; 420 t |= (cm << CALL_SHIFT); 421 t |= (bci << BCI_SHIFT); 422 t |= (iei << IEI_SHIFT); 423 t |= (gci << GCI_SHIFT); 424 t |= (mco << OFFSET_SHIFT); 425 tmpMC[lastMCInfoEntry++] = t; 426 } else if (bci < BIG_INVALID_BCI && 427 iei < BIG_INVALID_IEI && 428 gci < BIG_INVALID_GCI && 429 mco < (BIG_OFFSET_MASK >>> BIG_OFFSET_SHIFT)) { 430 // use a big entry 431 if (bci == -1) bci = BIG_INVALID_BCI; 432 if (iei == -1) iei = BIG_INVALID_IEI; 433 if (gci == -1) gci = BIG_INVALID_GCI; 434 if (VM.VerifyAssertions) { 435 VM._assert((cm & (BIG_CALL_MASK >>> BIG_CALL_SHIFT)) == cm); 436 VM._assert((bci & (BIG_BCI_MASK >>> BIG_BCI_SHIFT)) == bci); 437 VM._assert((iei & (BIG_IEI_MASK >>> BIG_IEI_SHIFT)) == iei); 438 VM._assert((gci & (BIG_GCI_MASK >>> BIG_GCI_SHIFT)) == gci); 439 VM._assert((mco & (BIG_OFFSET_MASK >>> BIG_OFFSET_SHIFT)) == mco); 440 } 441 int startIdx = lastMCInfoEntry; 442 tmpMC[startIdx] = START_OF_BIG_ENTRY; 443 tmpMC[startIdx + BIG_CALL_IDX_ADJ] |= (cm << BIG_CALL_SHIFT); 444 tmpMC[startIdx + BIG_BCI_IDX_ADJ] |= (bci << BIG_BCI_SHIFT); 445 tmpMC[startIdx + BIG_OFFSET_IDX_ADJ] |= (mco << BIG_OFFSET_SHIFT); 446 tmpMC[startIdx + BIG_GCI_IDX_ADJ] |= (gci << BIG_GCI_SHIFT); 447 tmpMC[startIdx + BIG_IEI_IDX_ADJ] |= (iei << BIG_IEI_SHIFT); 448 lastMCInfoEntry += SIZEOF_BIG_ENTRY; 449 } else { 450 // use a huge entry 451 if (bci == -1) bci = HUGE_INVALID_BCI; 452 if (iei == -1) iei = HUGE_INVALID_IEI; 453 if (gci == -1) gci = HUGE_INVALID_GCI; 454 if (VM.VerifyAssertions) { 455 VM._assert((cm & (HUGE_CALL_MASK >>> HUGE_CALL_SHIFT)) == cm); 456 VM._assert((bci & (HUGE_BCI_MASK >>> HUGE_BCI_SHIFT)) == bci); 457 VM._assert((iei & (HUGE_IEI_MASK >>> HUGE_IEI_SHIFT)) == iei); 458 VM._assert((gci & (HUGE_GCI_MASK >>> HUGE_GCI_SHIFT)) == gci); 459 VM._assert((mco & (HUGE_OFFSET_MASK >>> HUGE_OFFSET_SHIFT)) == mco); 460 } 461 int startIdx = lastMCInfoEntry; 462 tmpMC[startIdx] = START_OF_HUGE_ENTRY; 463 tmpMC[startIdx + HUGE_CALL_IDX_ADJ] |= (cm << HUGE_CALL_SHIFT); 464 tmpMC[startIdx + HUGE_BCI_IDX_ADJ] |= (bci << HUGE_BCI_SHIFT); 465 tmpMC[startIdx + HUGE_OFFSET_IDX_ADJ] |= (mco << HUGE_OFFSET_SHIFT); 466 tmpMC[startIdx + HUGE_GCI_IDX_ADJ] |= (gci << HUGE_GCI_SHIFT); 467 tmpMC[startIdx + HUGE_IEI_IDX_ADJ] |= (iei << HUGE_IEI_SHIFT); 468 lastMCInfoEntry += SIZEOF_HUGE_ENTRY; 469 } 470 } 471 int[] mcInformation = new int[lastMCInfoEntry]; 472 System.arraycopy(tmpMC, 0, mcInformation, 0, mcInformation.length); 473 int[] gcMaps = gcMapBuilder.finish(); 474 475 return new OptMachineCodeMap(mcInformation, gcMaps, inlineEncoding); 476 } 477 478 /** 479 * Ensures correct map construction by either correcting oddities or failing 480 * immediately in case of errors. 481 * 482 * @param mcOffsets machine code offset information 483 * @param instr the instruction to be processed 484 */ 485 private static void ensureCorrectMapConstruction( 486 MachineCodeOffsets mcOffsets, Instruction instr) { 487 if (mcOffsets.lacksMachineCodeOffset(instr)) { 488 // In non-interruptible code, we may encounter an IR_PROLOGUE instruction 489 // without a machine code offset. This can happen in the following way: 490 // - GC maps are built. The prologue instruction is present at this stage. 491 // - After register allocation (and after all GC Maps have been updated), 492 // the prologue and epilogue will be created. Because the method is 493 // not interruptible, no stack overflow check will be inserted and the 494 // prologue instruction will be removed. 495 // - Machine code offsets are set by the Assembler. The instruction does not 496 // get an offset because it is no longer present in the IR. 497 // - The machine code maps are created from the GC maps via this class 498 // which runs into the instruction with the machine code offset. 499 // This is merely an oddity and not a problem because runtime services 500 // will not query the machine code maps for non-interruptible code. 501 // Therefore, it is justified to add a special case for this. 502 if (instr.getOpcode() == IR_PROLOGUE_opcode) { 503 mcOffsets.fabricateMachineCodeOffsetForPrologueInstruction(instr); 504 } else { 505 // Unknown case, most likely an error. 506 throw new OptimizingCompilerException("Found instruction without valid machine code offset during " + 507 "generation of machine code information: " + instr); 508 } 509 } 510 } 511 512 //////////////////////////////////////////// 513 // Accessors 514 // NB: The accessors take an entry number, which is defined to 515 // be the index of word I of the MCInformation entry 516 //////////////////////////////////////////// 517 /** 518 * Returns the MCOffset for the entry passed 519 * @param entry the index of the start of the entry 520 * @return the MCOffset for this entry 521 */ 522 @Uninterruptible 523 private int getMCOffset(int entry) { 524 if (isBigEntry(entry)) { 525 int t = MCInformation[entry + BIG_OFFSET_IDX_ADJ]; 526 return (t & BIG_OFFSET_MASK) >>> BIG_OFFSET_SHIFT; 527 } else if (isHugeEntry(entry)) { 528 int t = MCInformation[entry + HUGE_OFFSET_IDX_ADJ]; 529 return (t & HUGE_OFFSET_MASK) >>> HUGE_OFFSET_SHIFT; 530 } else { 531 int t = MCInformation[entry]; 532 return (t & OFFSET_MASK) >>> OFFSET_SHIFT; 533 } 534 } 535 536 /** 537 * Returns the GC map index for the entry passed 538 * @param entry the index of the start of the entry 539 * @return the GC map entry index for this entry (or -1 if none) 540 */ 541 @Uninterruptible 542 private int getGCMapIndex(int entry) { 543 if (isBigEntry(entry)) { 544 int t = MCInformation[entry + BIG_GCI_IDX_ADJ]; 545 int gci = (t & BIG_GCI_MASK) >>> BIG_GCI_SHIFT; 546 if (gci == BIG_INVALID_GCI) return -1; 547 return gci; 548 } else if (isHugeEntry(entry)) { 549 int t = MCInformation[entry + HUGE_GCI_IDX_ADJ]; 550 int gci = (t & HUGE_GCI_MASK) >>> HUGE_GCI_SHIFT; 551 if (gci == HUGE_INVALID_GCI) return -1; 552 return gci; 553 } else { 554 int t = MCInformation[entry]; 555 int gci = (t & GCI_MASK) >>> GCI_SHIFT; 556 if (gci == INVALID_GCI) return -1; 557 return gci; 558 } 559 } 560 561 /** 562 * Returns the Bytecode index for the entry passed 563 * @param entry the index of the start of the entry 564 * @return the bytecode index for this entry (-1 if unknown) 565 */ 566 @Uninterruptible 567 private int getBytecodeIndex(int entry) { 568 if (isBigEntry(entry)) { 569 int t = MCInformation[entry + BIG_BCI_IDX_ADJ]; 570 int bci = (t & BIG_BCI_MASK) >>> BIG_BCI_SHIFT; 571 if (bci == BIG_INVALID_BCI) return -1; 572 return bci; 573 } else if (isHugeEntry(entry)) { 574 int t = MCInformation[entry + HUGE_BCI_IDX_ADJ]; 575 int bci = (t & HUGE_BCI_MASK) >>> HUGE_BCI_SHIFT; 576 if (bci == HUGE_INVALID_BCI) return -1; 577 return bci; 578 } else { 579 int t = MCInformation[entry]; 580 int bci = (t & BCI_MASK) >>> BCI_SHIFT; 581 if (bci == INVALID_BCI) return -1; 582 return bci; 583 } 584 } 585 586 /** 587 * Returns the inline encoding index for the entry passed. 588 * @param entry the index of the start of the entry 589 * @return the inline encoding index for this entry (-1 if unknown) 590 */ 591 @Uninterruptible 592 private int getInlineEncodingIndex(int entry) { 593 if (isBigEntry(entry)) { 594 int t = MCInformation[entry + BIG_IEI_IDX_ADJ]; 595 int iei = (t & BIG_IEI_MASK) >>> BIG_IEI_SHIFT; 596 if (iei == BIG_INVALID_IEI) return -1; 597 return iei; 598 } else if (isHugeEntry(entry)) { 599 int t = MCInformation[entry + HUGE_IEI_IDX_ADJ]; 600 int iei = (t & HUGE_IEI_MASK) >>> HUGE_IEI_SHIFT; 601 if (iei == HUGE_INVALID_IEI) return -1; 602 return iei; 603 } else { 604 int t = MCInformation[entry]; 605 int iei = (t & IEI_MASK) >>> IEI_SHIFT; 606 if (iei == INVALID_IEI) return -1; 607 return iei; 608 } 609 } 610 611 /** 612 * Returns the call info for the entry passed. 613 * @param entry the index of the start of the entry 614 * @return the call info for this entry 615 */ 616 @Uninterruptible 617 private int getCallInfo(int entry) { 618 if (isBigEntry(entry)) { 619 int t = MCInformation[entry + BIG_CALL_IDX_ADJ]; 620 return (t & BIG_CALL_MASK) >>> BIG_CALL_SHIFT; 621 } else if (isHugeEntry(entry)) { 622 int t = MCInformation[entry + HUGE_CALL_IDX_ADJ]; 623 return (t & HUGE_CALL_MASK) >>> HUGE_CALL_SHIFT; 624 } else { 625 int t = MCInformation[entry]; 626 return (t & CALL_MASK) >>> CALL_SHIFT; 627 } 628 } 629 630 /** 631 * @param entry the entry's index 632 * @return whether the the entry is a big entry 633 */ 634 @Uninterruptible 635 @Inline 636 private boolean isBigEntry(int entry) { 637 if (VM.VerifyAssertions) { 638 VM._assert((MCInformation[entry] & START_OF_ENTRY) == START_OF_ENTRY); 639 } 640 return (MCInformation[entry] & START_BITS) == START_OF_BIG_ENTRY; 641 } 642 643 /** 644 * @param entry the entry's index 645 * @return whether the the entry is a huge entry 646 */ 647 @Uninterruptible 648 @Inline 649 private boolean isHugeEntry(int entry) { 650 if (VM.VerifyAssertions) { 651 VM._assert((MCInformation[entry] & START_OF_ENTRY) == START_OF_ENTRY); 652 } 653 return (MCInformation[entry] & START_BITS) == START_OF_HUGE_ENTRY; 654 } 655 656 //////////////////////////////////////////// 657 // Debugging 658 //////////////////////////////////////////// 659 660 public void dumpMCInformation(boolean DUMP_MAPS) { 661 if (DUMP_MAPS) { 662 VM.sysWrite(" Dumping the MCInformation\n"); 663 if (MCInformation == null) return; 664 for (int idx = 0; idx < MCInformation.length;) { 665 printMCInformationEntry(idx, DUMP_MAPS); 666 idx = nextEntry(idx); 667 } 668 } 669 } 670 671 private void printMCInformationEntry(int entry, boolean DUMP_MAPS) { 672 if (DUMP_MAPS) { 673 String sep = "\tMC: "; 674 if (isBigEntry(entry)) sep = "B\tMC: "; 675 if (isHugeEntry(entry)) sep = "H\tMC: "; 676 VM.sysWrite(entry + sep + getMCOffset(entry)); 677 int bci = getBytecodeIndex(entry); 678 if (bci != -1) { 679 VM.sysWrite("\n\tBCI: " + bci); 680 } 681 int iei = getInlineEncodingIndex(entry); 682 if (iei != -1) { 683 VM.sysWrite("\n\tIEI: " + iei); 684 } 685 boolean first = true; 686 while (iei >= 0) { 687 int mid = OptEncodedCallSiteTree.getMethodID(iei, inlineEncoding); 688 RVMMethod meth = MemberReference.getMethodRef(mid).getResolvedMember(); 689 if (first) { 690 first = false; 691 VM.sysWrite("\n\tIn method " + meth + " at bytecode " + bci); 692 } else { 693 VM.sysWrite("\n\tInlined into " + meth + " at bytecode " + bci); 694 } 695 if (iei > 0) { 696 bci = OptEncodedCallSiteTree.getByteCodeOffset(iei, inlineEncoding); 697 } 698 iei = OptEncodedCallSiteTree.getParent(iei, inlineEncoding); 699 } 700 if (getGCMapIndex(entry) != OptGCMap.NO_MAP_ENTRY) { 701 VM.sysWrite("\n\tGC Map Idx: " + getGCMapIndex(entry) + " "); 702 OptGCMap.dumpMap(getGCMapIndex(entry), gcMaps); 703 } else { 704 VM.sysWrite("\n\tno GC map"); 705 } 706 VM.sysWrite("\n"); 707 } 708 } 709 710 private void recordStats(RVMMethod method, int mapSize, int machineCodeSize, boolean DUMP_MAP_SIZES) { 711 if (DUMP_MAP_SIZES) { 712 double mapMCPercent = (double) mapSize / machineCodeSize; 713 VM.sysWrite(method); 714 VM.sysWrite(" map is " + (int) (mapMCPercent * 100) + "% (" + mapSize + "/" + machineCodeSize + ") of MC.\n"); 715 totalMCSize += machineCodeSize; 716 totalMapSize += mapSize; 717 double MCPct = (double) totalMapSize / totalMCSize; 718 VM.sysWrite(" Cumulative maps are now " + 719 (int) (MCPct * 100) + 720 "% (" + 721 totalMapSize + 722 "/" + 723 totalMCSize + 724 ") of MC.\n"); 725 } 726 } 727 728 /** 729 * @return total bytes of machine code maps 730 */ 731 int size() { 732 int size = TYPE.peekType().asClass().getInstanceSize(); 733 if (MCInformation != null) size += RVMArray.IntArray.getInstanceSize(MCInformation.length); 734 if (inlineEncoding != null) size += RVMArray.IntArray.getInstanceSize(inlineEncoding.length); 735 if (gcMaps != null) size += RVMArray.IntArray.getInstanceSize(gcMaps.length); 736 return size; 737 } 738 739 //////////////////////////////////////////// 740 // 741 // Encoding constants and backing data. 742 // 743 //////////////////////////////////////////// 744 // An entry contains the following data: 745 // o: a machine code offset (in bytes) 746 // g: an index into the GC maps array 747 // b: bytecode index of the instruction 748 // i: index into the inline encoding. 749 // c: bits to encode one of three possibilites 750 // (a) the instruction is not a call 751 // (b) the instruction is a "normal" call 752 // (c) the instruction is a call in the off-branch 753 // of a guarded inline. 754 // U indicates an unused bit; its value is undefined. 755 // 756 // We support three entry formats as defined below 757 // 758 private static final int START_OF_ENTRY = 0x80000000; 759 private static final int START_OF_BIG_ENTRY = 0xc0000000; 760 private static final int START_OF_HUGE_ENTRY = 0xe0000000; 761 private static final int START_BITS = 0xe0000000; 762 763 // A small entry is 1 int used as follows: 764 // 10cc bbbb bbii iiii iggg ggoo oooo oooo 765 private static final int CALL_MASK = 0x30000000; 766 private static final int CALL_SHIFT = 28; 767 private static final int BCI_MASK = 0x0fc00000; 768 private static final int BCI_SHIFT = 22; 769 private static final int IEI_MASK = 0x003f8000; 770 private static final int IEI_SHIFT = 15; 771 private static final int GCI_MASK = 0x00007c00; 772 private static final int GCI_SHIFT = 10; 773 private static final int OFFSET_MASK = 0x000003ff; 774 private static final int OFFSET_SHIFT = 0; 775 private static final int INVALID_GCI = (GCI_MASK >>> GCI_SHIFT); 776 private static final int INVALID_BCI = (BCI_MASK >>> BCI_SHIFT); 777 private static final int INVALID_IEI = (IEI_MASK >>> IEI_SHIFT); 778 private static final int SIZEOF_ENTRY = 1; 779 780 // A big entry is 2 ints used as follows: 781 // 110c cbbb bbbb bbbb biii iiii iiii iiii 782 // 0ggg gggg gggg ggoo oooo oooo oooo oooo 783 private static final int BIG_CALL_MASK = 0x18000000; 784 private static final int BIG_CALL_SHIFT = 27; 785 private static final int BIG_CALL_IDX_ADJ = 0; 786 private static final int BIG_BCI_MASK = 0x07ff8000; 787 private static final int BIG_BCI_SHIFT = 15; 788 private static final int BIG_BCI_IDX_ADJ = 0; 789 private static final int BIG_IEI_MASK = 0x00007fff; 790 private static final int BIG_IEI_SHIFT = 0; 791 private static final int BIG_IEI_IDX_ADJ = 0; 792 private static final int BIG_GCI_MASK = 0x7ffc0000; 793 private static final int BIG_GCI_SHIFT = 18; 794 private static final int BIG_GCI_IDX_ADJ = 1; 795 private static final int BIG_OFFSET_MASK = 0x0003ffff; 796 private static final int BIG_OFFSET_SHIFT = 0; 797 private static final int BIG_OFFSET_IDX_ADJ = 1; 798 private static final int BIG_INVALID_GCI = (BIG_GCI_MASK >>> BIG_GCI_SHIFT); 799 private static final int BIG_INVALID_BCI = (BIG_BCI_MASK >>> BIG_BCI_SHIFT); 800 private static final int BIG_INVALID_IEI = (BIG_IEI_MASK >>> BIG_IEI_SHIFT); 801 private static final int SIZEOF_BIG_ENTRY = 2; 802 803 // A huge entry is 4 ints used as follows: 804 // 111c cUUU UUUU UUUU bbbb bbbb bbbb bbbb 805 // 0iii iiii iiii iiii iiii iiii iiii iiii 806 // 0ggg gggg gggg gggg gggg gggg gggg gggg 807 // 0ooo oooo oooo oooo oooo oooo oooo oooo 808 private static final int HUGE_CALL_MASK = 0x18000000; 809 private static final int HUGE_CALL_SHIFT = 27; 810 private static final int HUGE_CALL_IDX_ADJ = 0; 811 private static final int HUGE_BCI_MASK = 0x0000ffff; 812 private static final int HUGE_BCI_SHIFT = 0; 813 private static final int HUGE_BCI_IDX_ADJ = 0; 814 private static final int HUGE_IEI_MASK = 0x7fffffff; 815 private static final int HUGE_IEI_SHIFT = 0; 816 private static final int HUGE_IEI_IDX_ADJ = 1; 817 private static final int HUGE_GCI_MASK = 0x7fffffff; 818 private static final int HUGE_GCI_SHIFT = 0; 819 private static final int HUGE_GCI_IDX_ADJ = 2; 820 private static final int HUGE_OFFSET_MASK = 0x7fffffff; 821 private static final int HUGE_OFFSET_SHIFT = 0; 822 private static final int HUGE_OFFSET_IDX_ADJ = 3; 823 private static final int HUGE_INVALID_GCI = (HUGE_GCI_MASK >>> HUGE_GCI_SHIFT); 824 private static final int HUGE_INVALID_BCI = (HUGE_BCI_MASK >>> HUGE_BCI_SHIFT); 825 private static final int HUGE_INVALID_IEI = (HUGE_IEI_MASK >>> HUGE_IEI_SHIFT); 826 private static final int SIZEOF_HUGE_ENTRY = 4; 827 828 // bit patterns for cc portion of machine code map */ 829 private static final int IS_UNGUARDED_CALL = 0x1; 830 private static final int IS_GUARDED_CALL = 0x3; 831 832 /** 833 * Hold entries as defined by the constants above. 834 */ 835 private final int[] MCInformation; 836 /** 837 * array of GC maps as defined by OptGCMap 838 */ 839 private final int[] gcMaps; 840 /** 841 * encoded data as defined by OptEncodedCallSiteTree. 842 */ 843 public final int[] inlineEncoding; 844 /** 845 * Running totals for the size of machine code and maps 846 */ 847 private static int totalMCSize = 0; 848 private static int totalMapSize = 0; 849 /** 850 * A machine code map when no information is present 851 */ 852 private static final OptMachineCodeMap emptyMachineCodeMap = new OptMachineCodeMap(null, null, null); 853 854 private static final TypeReference TYPE = TypeReference.findOrCreate(OptMachineCodeMap.class); 855}