parallel-move

gistfile1.c

#include <stdio.h>
#include <string.h>
#include <stdint.h>

typedef uint32_t Reg;

#define RID_NONE		0x80
#define RID_MASK		0x7f
#define RID_INIT		(RID_NONE|RID_MASK)
#define RID_SINK		(RID_INIT-1)
#define RID_SUNK		(RID_INIT-2)

#define ra_noreg(r)		((r) & RID_NONE)
#define ra_hasreg(r)		(!((r) & RID_NONE))

/* The ra_hashint() macro assumes a previous test for ra_noreg(). */
#define ra_hashint(r)		((r) < RID_SUNK)
#define ra_gethint(r)		((Reg)((r) & RID_MASK))
#define ra_sethint(rr, r)	rr = (uint8_t)((r)|RID_NONE)
#define ra_samehint(r1, r2)	(ra_gethint((r1)^(r2)) == 0)

/* Spill slot 0 means no spill slot has been allocated. */
#define SPS_NONE		0

#define ra_hasspill(s)		((s) != SPS_NONE)

/* Combined register and spill slot (uint16_t in ir->prev). */
typedef uint32_t RegSP;

#define REGSP(r, s)		((r) + ((s) << 8))
#define REGSP_HINT(r)		((r)|RID_NONE)
#define REGSP_INIT		REGSP(RID_INIT, 0)

#define regsp_reg(rs)		((rs) & 255)
#define regsp_spill(rs)		((rs) >> 8)
#define regsp_used(rs) \
  (((rs) & ~REGSP(RID_MASK, 0)) != REGSP(RID_NONE, 0))

typedef uint8_t Status;
typedef uint32_t u32;

#define STATUS_TO_MOVE 0
#define STATUS_MOVING  1
#define STATUS_MOVED   2

Reg getTemp(RegSP dst) {
  return 15;  // TODO
}

void emitMove(Reg dest, Reg src) {
  printf("\tr%d <- r%d\n", dest, src);
}

// Semantics of RegSP
//   - if hasreg(...), then the value is definitely stored in
//     that register.
//
//   - if hasspill(...), then the value is definitely stored
//     in that spill slot.
//
//   - We can have both.
//
// The register assignment may change due to a rename. The snapshot
// restore code must take care of these cases.

// Here are the possible cases that we have to support:
//
// dst \ src  |  Reg(rS)  | Spill(N)   | Reg(rS) + Spill(N)
// -----------+-----------+------------+---------------
//  Reg=rS    |     -     | rS = sp[N] |   -
//  Reg=rD    | rD = rS   | rD = sp[N] | rD = rS  if no writes to rS
//            |           |            | rD = sp[N]  if no writes to sp[N]
// -----------+-----------+------------+----------------
// Spill(N)   | sp[N]= rS |    -       |  -
// Spill(M)   | sp[M]= rS | tmp=sp[N]  | ...
//            |           | sp[M]=tmp  | 
//
// If dst has a register and a spill slot assigned it means we have to
// write it to both.  In that case it's easier to emit the store and
// then treat it as a register-only target.

void moveOne(u32 i, u32 total, RegSP *dest, RegSP *source, Status *status) {
  RegSP dst = dest[i];
  RegSP src = source[i];
  Reg destreg = regsp_reg(dst);
  Reg srcreg = regsp_reg(src);
  if (destreg != srcreg) {
    status[i] = STATUS_MOVING;
    // We want to emit a store "dest = src".  This is only valid if we
    // do not also want to emit a store to src later on.  (Since we're
    // generating code backwards, this store would execute before we
    // reach this point.)  Note: there can only be exactly one store
    // for each target register.
    for (int j = 0; j < total; ++j) {
      if (regsp_reg(dest[j]) == srcreg) { // We found a store.
        if (status[j] == STATUS_TO_MOVE) {
          // We haven't tried moving that one, yet, so lets emit the
          // code for that one first.
          moveOne(j, total, dest, source, status);
        } else if (status[j] == STATUS_MOVING) {
          // We have discovered cyclic dependencies.  We break the
          // cycle by grabbing reading the source from a temporary
          // register.
          Reg dst2 = regsp_reg(dest[j]);
          Reg tmp = getTemp(dst2);
          emitMove(dst2, tmp);
          dest[j] = tmp;
        }
        // Otherwise, we already processed the move. Nothing to do.
      }
    }
    // Note: dest[i] may have changed.
    Reg destreg = regsp_reg(dest[i]);
    emitMove(destreg, srcreg);
  }
}

#define COUNT 4

int main(int argc, char *argv[])
{
  int i;
  RegSP source[COUNT] = { 1, 3, 0, 2 };
  RegSP dest[COUNT]   = { 0, 1, 3, 2 };
  Status status[COUNT];
  for (i = 0; i < COUNT; ++i) status[i] = STATUS_TO_MOVE;

  printf("NOTE: Emitted code is in inverse order.\n\n");
  
  for (i = 0; i < COUNT; ++i) {
    if (status[i] == STATUS_TO_MOVE)
      moveOne(i, COUNT, dest, source, status);
  }

  return 0;
}