qdra.java

用Java实现的一个简单的寄存器分配器

        continue;

      if (trace)
        System.out.println("try " + registers.display(vr));

      if (!spilled[vr]) {
        spillReg(vr, firstInstruction, true);
        changed = true;
      }

      // Find and spill each un-spilled register whose live range overlaps.

      for (int i = nrr; i < nr; i++) {
        if (map[i] >= nrr)
          continue; // Not allocated last time around.

        if (spilled[i])
          continue; // Already spilled.

        if (registers.continueRegister(i))
          continue; // Spill main register.

        if (registers.floatRegister(vr) ^ registers.floatRegister(i))
          continue; // Not the right type.

        if (regUseCnt[i] <= 1)
          continue; // Spilling likely to have no bennefit.

        int ic = turned[vr].intersectCount(turned[i]);
        if (ic <= 0)
          continue;

        // Spill the register because its live range overlaps..

        spillReg(i, firstInstruction, true);
        changed = true;
      }
    }

    return changed;
  }

  private String formatInt(long v, int f)
  {
    String s = Long.toString(v);
    int    l = s.length();
    if (l == f)
      return s;
    if (l > f)
      return "*********************************".substring(0, f);
    return ("             ".substring(0, f - l) + s);
  }

  /**
   * Generate a virtual register to real register mapping.
   * @param regs is the register set of the machine
   * @param turned is the liveness of each register
   * @return the number of virtual registers that were not allocated.
   */
  private int allocateRealRegisters(RegisterSet regs, BitVect[] turned)
  {
    int nr  = regs.numRegisters();
    int nrr = regs.numRealRegisters();
    int nvr = nr - nrr;

    for (int i = 0; i < nrr; i++)
      map[i] = i;

    for (int i = 0; i < nvr; i++) {
      int virtualReg = nrr + i;
      map[virtualReg] = virtualReg;
    }

    // Determine the importance of each register.  Importance is the
    // measure of how important it is to allocate it before other
    // registers.

    for (int i = 0; i < nvr; i++) {
      int virtualReg = nrr + i;
      int liveness   = turned[virtualReg].count();
      if (liveness <= 1) {
        liveness = 1;
        spilled[virtualReg] = true; // Inhibit spilling.
      }
      sorted[i] = i;

      // Allocate the registers with the shortest live ranges first.
      // Spilling them is less likely to be effective.

      strengths[i] = 1.0 / liveness;
    }

    // Sort virtual registers in descending order of importance using
    // a combination sort.

    int     jumpSize = nvr;
    boolean flag;
    do {
      flag = false;
      jumpSize = (10 * jumpSize + 3) / 13;
      int ul = nvr - jumpSize;
      for (int i = 0; i < ul; i++) {
        int k  = i + jumpSize;
        int i1 = sorted[i];
        int i2 = sorted[k];
        // The test below for the register number being less is not
        // strictly necessary but it helps in debugging when comparing
        // two .s files.
        boolean swap = (strengths[i2] > strengths[i1]) ||
                       ((strengths[i2] == strengths[i1]) && (i2 < i1));
        if (swap) {
          sorted[i] = i2;
          sorted[k] = i1;
          flag = true;
        }
      }
    } while (flag || (jumpSize > 1));

    assert trace0(turned, nvr, nrr);

    // Multiple virtual registers may be mapped to the same real register.

    int notAllocatedCnt = (regs.useContiguous() ?
                           allocateRealRegsContiguous(regs, turned) :
                           allocateRealRegsNonContiguous(regs, turned));

    assert (notAllocatedCnt == 0) || trace1(turned, notAllocatedCnt, nvr, nrr);

    return notAllocatedCnt;
  }

  private boolean trace0(BitVect[] turned, int nvr, int nrr)
  {
    if (!trace)
      return true;

    int           k      = 0;
    DecimalFormat format = new DecimalFormat("###0.000000");
    for (int j = 0; j < nrr; j++) {
      if (turned[j].count() == 0)
        continue;
      System.out.print(registers.display(j));
      System.out.println("   " + turned[j]);
    }

    for (int j = 0; j < nvr; j++) {
      int i = sorted[j];
      int virtualReg = nrr + i;

      if (registers.continueRegister(virtualReg))
        continue; // Not allocatable.

      System.out.print(formatInt(k++, 5));
      System.out.print(" ");
      System.out.print(registers.display(virtualReg));
      System.out.print(" ");
      System.out.print(format.format(strengths[i]));
      System.out.println("   " + turned[virtualReg]);
    }

    return true;
  }

  private boolean trace1(BitVect[] turned, int notAllocatedCnt, int nvr, int nrr)
  {
    if (!trace)
      return true;

    StringBuffer buf = new StringBuffer("");

    System.out.println("** " + notAllocatedCnt + " not allocated.");
    DecimalFormat format = new DecimalFormat("###0.000000");
    for (int i = 0; i < nvr; i++) {
      int virtualReg = nrr + i;

      if (registers.continueRegister(virtualReg))
        continue;

      buf.setLength(0);

      int realReg = map[virtualReg];

      if (realReg < nrr)
        continue;

      buf.append("Nomap ");

      buf.append(registers.display(virtualReg));
      buf.append(" ");
      buf.append(format.format(strengths[virtualReg - nrr]));
      buf.append(" ");
      int lv = buf.length();

      buf.append(turned[virtualReg]);

      if (realReg < nrr) {
        System.out.println(buf.toString());
        buf.setLength(0);
        buf.append("      ");
        buf.append(registers.display(realReg));
        int lr = buf.length();
        if (lv > lr)
          buf.append("                                   ".substring(0, lv - lr));
        buf.append(turned[realReg]);
      }
      System.out.println(buf.toString());
    }

    return true;
  }

  /**
   * Assign the virtual registers to real registers where continue
   * registers are assigned to contiguous real registers.
   * Used for the Sparc for extended precision (integer and floating point).
   */
  private int allocateRealRegsContiguous(RegisterSet regs, BitVect[] turned)
  {
    int     nr              = regs.numRegisters();
    int     nrr             = regs.numRealRegisters();
    int     nvr             = nr - nrr;
    short[] preferredOrder  = regs.getPreferredOrder(); // Order real registers should be allocated.
    int     notAllocatedCnt = 0;

    for (int i = 0; i < nvr; i++) { // For each virtual register.
      int virtualReg = nrr + sorted[i];

      if (registers.continueRegister(virtualReg))
        continue; // Not allocatable.

      for (int j = 0; j < preferredOrder.length; j++) {
        // For each real register, allocate all virtual registers that
        // do not conflict.

        int realReg = preferredOrder[j];

        if (regs.readOnlyRegister(realReg))
          continue;

        if (!registers.compatible(realReg, virtualReg))
          continue; // Not compatible.

        if (turned[realReg].intersect(turned[virtualReg]))
          continue; // Register conflict.

        int fr  = registers.rangeBegin(realReg);
        int lr  = registers.rangeEnd(realReg);
        int ncr = regs.numContiguousRegisters(virtualReg);

        assert ((fr + ncr - 1) == lr) :
          "Real register (" + realReg + ") does not match " + virtualReg;

        if (fr != realReg) { // Check all contiguous real registers needed.
          // If the first register (fr) is not the same as the real
          // register (realReg), this means that we have a "real
          // register" mapped onto a real register.  For example, on
          // the Sparc V8, a double precision real register is mapped
          // onto two single precision real registers.

          // If a 64-bit long long is mapped onto two 32-bit integers
          // registers, it is possible that a conversion of the 64-bit
          // value to 32-bits may result in referencing only the
          // "continue" register part of the virtual register.  That's
          // why there are two checks below.  It's conceivable that
          // only the second one is really needed and that better
          // register allocation may result if the first is removed.

          boolean flg = false;
          for (int k = 0; k < ncr; k++) {
            if (turned[fr + k].intersect(turned[virtualReg]) ||
                turned[fr + k].intersect(turned[virtualReg + k])) {
              flg = true;
              break; // Not all contiguous real registers, that are needed, are available.
            }
          }
          
          if (flg)
            continue; // Register conflict.

          for (int k = 0; k < ncr; k++) {
            turned[fr + k].or(turned[virtualReg]);
            turned[fr + k].or(turned[virtualReg + k]);
          }
        }

        // Found a virtual register to allocate to the real register.

        for (int k = 0; k < ncr; k++) {
          turned[realReg + k].or(turned[virtualReg]);
          map[virtualReg + k] = realReg + k;
        }

        break;
      }

      if (map[virtualReg] >= nrr) {
        if (notAllocatedCnt >= unallocated.length) {
          int[] nua = new int[notAllocatedCnt * 2];
          System.arraycopy(unallocated, 0, nua, 0, notAllocatedCnt);
          unallocated = nua;
        }
        unallocated[notAllocatedCnt++] = virtualReg;
      }
    }

    return notAllocatedCnt;
  }

  /**
   * Assign the virtual registers to real registers where continue
   * registers are not assigned to contiguous real registers.
   * Used for the Alpha for structs in registers.
   */
  private int allocateRealRegsNonContiguous(RegisterSet regs, BitVect[] turned)
  {
    int     nr              = regs.numRegisters();
    int     nrr             = regs.numRealRegisters();
    int     nvr             = nr - nrr;
    short[] preferredOrder  = regs.getPreferredOrder(); // Order real registers should be allocated.
    int     notAllocatedCnt = 0;

    for (int i = 0; i < nvr; i++) { // For each virtual register.
      int virtualReg = nrr + sorted[i];

      for (int j = 0; j < preferredOrder.length; j++) {
        // For each real register, allocate all virtual registers that
        // do not conflict.

        int realReg = preferredOrder[j];

        if (regs.readOnlyRegister(realReg))
          continue;

        if (!registers.compatibleNS(realReg, virtualReg))
          continue; // Not compatible.

        if (turned[realReg].intersect(turned[virtualReg]))
          continue; // Register conflict.

        // Found a virtual register to allocate to the real register.

        turned[realReg].or(turned[virtualReg]);
        map[virtualReg] = realReg;

        break;
      }

      if (map[virtualReg] >= nrr) {
        if (notAllocatedCnt >= unallocated.length) {
          int[] nua = new int[notAllocatedCnt * 2];
          System.arraycopy(unallocated, 0, nua, 0, notAllocatedCnt);
          unallocated = nua;
        }
        unallocated[notAllocatedCnt++] = virtualReg;
      }
    }

    return notAllocatedCnt;
  }
}