qdra.java

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

package scale.backend;

import scale.common.*;
import java.text.DecimalFormat;

/** 
 * This class implements a quick and dirty register allocator.
 * <p>
 * $Id: QDRA.java,v 1.75 2007-10-04 19:57:49 burrill Exp $
 * <p>
 * Copyright 2007 by the
 * <a href="http://ali-www.cs.umass.edu/">Scale Compiler Group</a>,<br>
 * <a href="http://www.cs.umass.edu/">Department of Computer Science</a><br>
 * <a href="http://www.umass.edu/">University of Massachusetts</a>,<br>
 * Amherst MA. 01003, USA<br>
 * All Rights Reserved.<br>
 * <p>
 * It's quick not because it runs quickly but because it was written
 * quickly.  It's dirty because it's not been proven to terminate in
 * all cases.
 * <p>
 * <h2>Algorithm</h2>
 * <pre>
 *   FOR trip = 1 to 30 DO
 *      compute the importance of each instruction (Note 1)
 *      FOR each instruction
 *        obtain the registers used by the instruction
 *        obtain the registers defined by the instruction
 *        obtain the registers clobbered by the instruction
 *      FOREND
 *      compute register liveness across instructions
 *      FOR each virtual register (VA)
 *        compute VA's importance (Note 2)
 *      FOREND
 *      sort virtual registers by importance 
 *      FOR each un-allocated virtual register (VA) in order of its importance
 *        FOR each real register (RA) (Note 3)
 *          IF the liveness of VA does not conflict with the liveness of RA THEN
 *            allocate VA to RA
 *            update RA's liveness
 *            BREAK
 *        FOREND
 *      FOREND
 *      IF no un-allocated virtual registers remain THEN
 *        RETURN allocation map
 *      spill
 *   FOREND
 *   ABORT(Allocation failure)
 * </pre>
 * <b>Notes</b>
 * <ol>
 * <li> The importance of an instruction is basically its loop_depth * 10.
 * <li> The importance of a register is a function of the sum of the
 * importance of the instructions that use the register and the number
 * of instructions over which the register is live.
 * <li> Real registers are checked in the order specified by the
 * register set definition.
 * </ol>
 * <p>
 * Our "bin-packing" register allocator is based on the bin-packing
 * register allocator as described in [Truab "Quality and Speed in
 * Linear-scan Register Allocation"].
 * <p>
 * <h3>Spilling</h3>
 * <p>
 * We use two different methods to select virtual registers to be
 * spilled.  The method chosen is determined by a heuristic.  The
 * first spill method (meek) simply spills those virtual registers
 * that were not allocated.  The second spill method (aggressive)
 * attempts to spill those virtual registers with the longest live
 * sequence. Since that information is not readily available, it uses
 * the number of instructions over which the register is live as an
 * approximation.  The number spilled by the second method is the
 * number of virtual registers that were not allocated.
 * <p>
 * The heuristic for selecting the method is simply to choose the
 * aggressive method if there are more un-allocated virtual registers
 * than real registers or if the meek method has already been used in
 * a previous attempt.
 * <p>
 * When spilling, register saves are inserted immediately after any
 * code sequence that defines the virtual register.  Code sequences
 * basically consist of those instructions generated for one CFG node.
 * Code sequences are defined by the backend code generator which
 * marks the last instruction in a sequence.
 * <p>
 * The point at which a spilled virtual register is loaded is also
 * determined by heuristic.  If the virtual register is defined only
 * once, it is reloaded immediately before every use.  Otherwise, it
 * is reloaded immediately before the first use in a basic block.
 */
public class QDRA extends RegisterAllocator
{
  private static int spillCount = 0;
  private static int redoCount  = 0;
  private static int maxVRCount = 0;

  private static final String[] stats = {"spills", "redo", "maxVirtualRegs"};

  static
  {
    Statistics.register("scale.backend.QDRA", stats);
  }

  /**
   * Return the number of spills required.
   */
  public static int spills()
  {
    return spillCount;
  }

  /**
   * Return the number of times register allocation was re-done.
   */
  public static int redo()
  {
    return redoCount;
  }

  /**
   * Return the maximum number of virtual registers encountered.
   */
  public static int maxVirtualRegs()
  {
    return maxVRCount;
  }

  private int       ssc;         // Initial spill count.
  private int       sslc;        // Initial spill load count.
  private int       sssc;        // Initial spill store count.
  private int[]     unallocated; // List of un-allocated virtual registers.
  private int[]     sorted;      // Virtual registers sorted in the order to be allocated.
  private double[]  strengths;   // Strength of each register.
  private boolean[] spilled;     // True if register has been spilled.
  private int[]     map;         // Map from virtual register to real register.

  /**
   * Setup a quick & dirty register allocation.
   * @param gen is the instruction generator in use
   * @param trace is true if the register allocation should be traced
   */
  public QDRA(Generator gen, boolean trace)
  {
    super(gen, trace);
    ssc  = spillCount;
    sslc = spillLoadCount;
    sssc = spillStoreCount;
  }

  /**
   * Determine a mapping from virtual registers to real registers.
   * This may involve the insertion of instructions to load and store
   * the value of a virtual register.
   * @param firstInstruction is the first instruction in the
   * instruction sequence
   * @return the mapping from virtual register to real register
   */
  public int[] allocate(Instruction firstInstruction)
  {
    int nr  = registers.numRegisters();
    int nrr = registers.numRealRegisters();
    int nvr = nr - nrr;

    map         = new int[nr];
    spilled     = new boolean[nr];
    unallocated = new int[100];
    sorted      = new int[nvr];
    strengths   = new double[nvr];

    if (nr > maxVRCount)
      maxVRCount = nr;

    for (int trip = 0; trip < 30; trip++) {
      computePredecessors(firstInstruction);

      Instruction[] insts   = linearize(firstInstruction);
      BitVect[]     live    = compress(computeLiveness(insts));
      BitVect[]     turned  = transpose(live, nr);
      int           unalloc = allocateRealRegisters(registers, turned);

      if (unalloc == 0) {
        int num = spillCount - ssc;
        if ((num > 0) && (trace || Debug.debug(2))) {
          System.out.print("  spills ");
          System.out.print(generator.useMemory);
          System.out.print(" ");
          System.out.print(generator.getCurrentRoutine().getName());
          System.out.print(" r:");
          System.out.print(num);
          System.out.print(" l:");
          System.out.print(spillLoadCount - sslc);
          System.out.print(" s:");
          System.out.println(spillStoreCount - sssc);
        }
        return map; // All virtual registers are allocated.
      }

      if (trace || Debug.debug(2)) {
        System.out.print("** QDRA " + nr + " " + nrr + ":");
        for (int i = 0; i < unalloc; i++)
          if (unallocated[i] > 0) {
            System.out.print(" ");
            System.out.print(registers.display(unallocated[i]));
          }
        System.out.println("");
      }
 
      // Spilling required.

      String  allocType = "";
      boolean changed   = false;

      if (trip > 4) {
        changed = fullSpill(unalloc, turned, firstInstruction);
        allocType = "full";
      } else {
        changed = partialSpill(unalloc, turned, firstInstruction);
        allocType = "part";
      }

      int nr2 = registers.numRegisters();
      if (nr2 > nr) {
        boolean[] nspilled = new boolean[nr2];
        System.arraycopy(spilled, 0, nspilled, 0, nr);

        spilled   = nspilled;
        nr        = nr2;
        nvr       = nr - nrr;
        map       = new int[nr];
        sorted    = new int[nvr];
        strengths = new double[nvr];
      }

      if (!changed)
        throw new scale.common.InternalError("Register allocation failed - no change.");

      if (trace) {
        System.out.print("Spill ");
        System.out.print(allocType);
        System.out.print(' ');
        System.out.print(trip);
        System.out.print(' ');
        System.out.print(nrr);
        System.out.print(' ');
        System.out.print(nr);
        System.out.print(' ');
        System.out.println(unalloc);
      }

      redoCount++;
    }

    throw new scale.common.InternalError("Register allocation failed - too many attempts.");
  }

  /**
   * Spill the specified register.
   * @param reg is the register to be spilled, spilled[reg] is set true
   * @param firstInstruction is the first instruction in the program
   * @param aggressive is true for aggressive spilling
   */
  private void spillReg(int reg, Instruction firstInstruction, boolean aggressive)
  {
    if (trace)
      System.out.println("spill " + registers.display(reg));
    spill(reg, firstInstruction, aggressive || (registers.numContiguousRegisters(reg) > 1));
    spillCount++;
    spilled[reg] = true;
  }

  /**
   * Spill the registers that were not allocated and one other whose
   * live range overlapped.
   * @param numNotAllopcated is the number of un-allocated virtual registers
   * @param turned[reg] is the live range for register reg
   * @param firstInstruction is the first instruction in the program
   */
  private boolean partialSpill(int         numNotAllocated,
                               BitVect[]   turned,
                               Instruction firstInstruction)
  {
    int     nr      = registers.numRegisters();
    int     nrr     = registers.numRealRegisters();
    boolean changed = false;

    for (int un = 0; un < numNotAllocated; un++) {
      int vr = unallocated[un];
      if (vr == 0)
        continue;

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

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

      // Find an un-spilled register, to spill also, from the set of
      // registers that were allocated last time around.

      int best      = -1;
      int bestCount = -1;

      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.

        // Pick the register whose live ranges overlap the live ranges of
        // the un-allocated register the most.

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

        bestCount = ic;
        best = i;
      }

      if (best < 0) // No suitable candidate found.
        continue;

      // Spill register best.

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

    return changed;
  }

  /**
   * Spill the registers that were not allocated and all the registers
   * whose live ranges overlapped.
   * @param numNotAllopcated is the number of un-allocated virtual registers
   * @param turned[reg] is the live range for register reg
   * @param firstInstruction is the first instruction in the program
   */
  private boolean fullSpill(int         numNotAllocated,
                            BitVect[]   turned,
                            Instruction firstInstruction)
  {
    int     nr      = registers.numRegisters();
    int     nrr     = registers.numRealRegisters();
    boolean changed = false;

    for (int un = 0; un < numNotAllocated; un++) {
      int vr = unallocated[un];
      if (vr == 0)