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.ia32;
014
015import static org.jikesrvm.compilers.common.assembler.ia32.AssemblerConstants.GT;
016import static org.jikesrvm.compilers.common.assembler.ia32.AssemblerConstants.LT;
017import static org.jikesrvm.ia32.RegisterConstants.EAX;
018import static org.jikesrvm.ia32.RegisterConstants.ECX;
019import static org.jikesrvm.ia32.RegisterConstants.THREAD_REGISTER;
020
021import org.jikesrvm.VM;
022import org.jikesrvm.classloader.RVMMethod;
023import org.jikesrvm.compilers.common.CodeArray;
024import org.jikesrvm.compilers.common.assembler.ia32.Assembler;
025import org.jikesrvm.runtime.ArchEntrypoints;
026import org.vmmagic.unboxed.Offset;
027
028/**
029 * An interface conflict resolution stub uses a hidden parameter to
030 * distinguish among multiple interface methods of a class that map to
031 * the same slot in the class's IMT.
032 *
033 * <p><STRONG>Assumption:</STRONG>
034 * Register EAX contains the "this" parameter of the
035 * method being called invoked.
036 *
037 * <p><STRONG>Assumption:</STRONG>
038 * Register ECX is available as a scratch register (we need one!)
039 */
040public abstract class InterfaceMethodConflictResolver {
041
042  // Create a conflict resolution stub for the set of interface method signatures l.
043  //
044  public static CodeArray createStub(int[] sigIds, RVMMethod[] targets) {
045    int numEntries = sigIds.length;
046    // (1) Create an assembler.
047    Assembler asm = new Assembler(numEntries);
048
049    // (2) signatures must be in ascending order (to build binary search tree).
050    if (VM.VerifyAssertions) {
051      for (int i = 1; i < sigIds.length; i++) {
052        VM._assert(sigIds[i - 1] < sigIds[i]);
053      }
054    }
055
056    // (3) Assign synthetic bytecode numbers to each switch such that we'll generate them
057    // in ascending order.  This lets us use the general forward branching mechanisms
058    // of the Assembler.
059    int[] bcIndices = new int[numEntries];
060    assignBytecodeIndices(0, bcIndices, 0, numEntries - 1);
061
062    // (4) Generate the stub.
063    insertStubPrologue(asm);
064    insertStubCase(asm, sigIds, targets, bcIndices, 0, numEntries - 1);
065
066    return asm.getMachineCodes();
067  }
068
069  // Assign ascending bytecode indices to each case (in the order they will be generated)
070  private static int assignBytecodeIndices(int bcIndex, int[] bcIndices, int low, int high) {
071    int middle = (high + low) / 2;
072    bcIndices[middle] = bcIndex++;
073    if (low == middle && middle == high) {
074      return bcIndex;
075    } else {
076      // Recurse.
077      if (low < middle) {
078        bcIndex = assignBytecodeIndices(bcIndex, bcIndices, low, middle - 1);
079      }
080      if (middle < high) {
081        bcIndex = assignBytecodeIndices(bcIndex, bcIndices, middle + 1, high);
082      }
083      return bcIndex;
084    }
085  }
086
087  // Make a stub prologue: get TIB into ECX
088  // factor out to reduce code space in each call.
089  //
090  private static void insertStubPrologue(Assembler asm) {
091    asm.baselineEmitLoadTIB(ECX, EAX);
092  }
093
094  // Generate a subtree covering from low to high inclusive.
095  private static void insertStubCase(Assembler asm, int[] sigIds, RVMMethod[] targets, int[] bcIndices, int low,
096                                     int high) {
097    int middle = (high + low) / 2;
098    asm.resolveForwardReferences(bcIndices[middle]);
099    if (low == middle && middle == high) {
100      // a leaf case; can simply invoke the method directly.
101      RVMMethod target = targets[middle];
102      if (target.isStatic()) { // an error case...
103        asm.generateJTOCjmp(target.getOffset());
104      } else {
105        asm.emitJMP_RegDisp(ECX, target.getOffset());
106      }
107    } else {
108      Offset disp = ArchEntrypoints.hiddenSignatureIdField.getOffset();
109      asm.emitCMP_RegDisp_Imm(THREAD_REGISTER, disp, sigIds[middle]);
110      if (low < middle) {
111        asm.emitJCC_Cond_Label(LT, bcIndices[(low + middle - 1) / 2]);
112      }
113      if (middle < high) {
114        asm.emitJCC_Cond_Label(GT, bcIndices[(middle + 1 + high) / 2]);
115      }
116      // invoke the method for middle.
117      RVMMethod target = targets[middle];
118      if (target.isStatic()) { // an error case...
119        asm.generateJTOCjmp(target.getOffset());
120      } else {
121        asm.emitJMP_RegDisp(ECX, target.getOffset());
122      }
123      // Recurse.
124      if (low < middle) {
125        insertStubCase(asm, sigIds, targets, bcIndices, low, middle - 1);
126      }
127      if (middle < high) {
128        insertStubCase(asm, sigIds, targets, bcIndices, middle + 1, high);
129      }
130    }
131  }
132}