shithub: mc

ref: e9b59bee4efb648e323dfb6269209b59c575806f
dir: /6/ra.c/

View raw version
#define _GNU_SOURCE
#include <stdlib.h>
#include <stdio.h>
#include <inttypes.h>
#include <stdarg.h>
#include <assert.h>
#include <limits.h>
#include <string.h>

#include "util.h"
#include "parse.h"
#include "mi.h"
#include "asm.h"

#define Sizetbits (CHAR_BIT*sizeof(size_t)) /* used in graph reprs */

typedef struct Usemap Usemap;
struct Usemap {
	int l[Nreg + 1]; /* location of arg used in instruction's arg list */
	int r[Nreg + 1]; /* list of registers used implicitly by instruction */
};

void wlprint(FILE *fd, char *name, Loc **wl, size_t nwl);
static int moverelated(Isel *s, regid n);
static void printedge(FILE *fd, char *msg, size_t a, size_t b);

/* tables of uses/defs by instruction */
Usemap usetab[] = {
#define Def(...)
#define Use(...) {__VA_ARGS__}
#define Insn(i, gasfmt, p9fmt, use, def) use,
#include "insns.def"
#undef Insn
#undef Use
#undef Def
};

Usemap deftab[] = {
#define Use(...)
#define Def(...) {__VA_ARGS__}
#define Insn(i, gasfmt, p9fmt, use, def) def,
#include "insns.def"
#undef Insn
#undef Def
#undef Use
};

/*
 * A map of which registers interfere. A write to
 * any entry in regmap[colormap[reg]] will clobber
 * any of the other values in that row of regmap.
 */
#define Northogonal (32 - 2)
Reg regmap[Northogonal][Nmode] = {
		/* None,   ModeB, ModeW, ModeL, ModeQ, ModeF, ModeD */
	[0]	= {Rnone, Ral,   Rax,   Reax,  Rrax,  Rnone,  Rnone},
	[1]	= {Rnone, Rcl,   Rcx,   Recx,  Rrcx,  Rnone,  Rnone},
	[2]	= {Rnone, Rdl,   Rdx,   Redx,  Rrdx,  Rnone,  Rnone},
	[3]	= {Rnone, Rbl,   Rbx,   Rebx,  Rrbx,  Rnone,  Rnone},
	[4]	= {Rnone, Rsil,  Rsi,   Resi,  Rrsi,  Rnone,  Rnone},
	[5]	= {Rnone, Rdil,  Rdi,   Redi,  Rrdi,  Rnone,  Rnone},
	[6]	= {Rnone, Rr8b,  Rr8w,  Rr8d,  Rr8,   Rnone,  Rnone},
	[7]	= {Rnone, Rr9b,  Rr9w,  Rr9d,  Rr9,   Rnone,  Rnone},
	[8]	= {Rnone, Rr10b, Rr10w, Rr10d, Rr10,  Rnone,  Rnone},
	[9]	= {Rnone, Rr11b, Rr11w, Rr11d, Rr11,  Rnone,  Rnone},
	[10]	= {Rnone, Rr12b, Rr12w, Rr12d, Rr12,  Rnone,  Rnone},
	[11]	= {Rnone, Rr13b, Rr13w, Rr13d, Rr13,  Rnone,  Rnone},
	[12]	= {Rnone, Rr14b, Rr14w, Rr14d, Rr14,  Rnone,  Rnone},
	[13]	= {Rnone, Rr15b, Rr15w, Rr15d, Rr15,  Rnone,  Rnone},
	[14]	= {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm0f, Rxmm0d},
	[15]	= {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm1f, Rxmm1d},
	[16]	= {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm2f, Rxmm2d},
	[17]	= {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm3f, Rxmm3d},
	[18]	= {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm4f, Rxmm4d},
	[19]	= {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm5f, Rxmm5d},
	[20]	= {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm6f, Rxmm6d},
	[21]	= {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm7f, Rxmm7d},
	[22]	= {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm8f, Rxmm8d},
	[23]	= {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm9f, Rxmm9d},
	[24]	= {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm10f, Rxmm10d},
	[25]	= {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm11f, Rxmm11d},
	[26]	= {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm12f, Rxmm12d},
	[27]	= {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm13f, Rxmm13d},
	[28]	= {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm14f, Rxmm14d},
	[29]	= {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm15f, Rxmm15d},
};

/* Which regmap entry a register maps to */
int colourmap[Nreg] = {
	/* byte */
	[Ral]	= 0,  [Rax]	= 0,  [Reax]	= 0,  [Rrax]	= 0,
	[Rcl]	= 1,  [Rcx]	= 1,  [Recx]	= 1,  [Rrcx]	= 1,
	[Rdl]	= 2,  [Rdx]	= 2,  [Redx]	= 2,  [Rrdx]	= 2,
	[Rbl]	= 3,  [Rbx]	= 3,  [Rebx]	= 3,  [Rrbx]	= 3,
	[Rsil]	= 4,  [Rsi]	= 4,  [Resi]	= 4,  [Rrsi]	= 4,
	[Rdil]	= 5,  [Rdi]	= 5,  [Redi]	= 5,  [Rrdi]	= 5,
	[Rr8b]	= 6,  [Rr8w]	= 6,  [Rr8d]	= 6,  [Rr8]	= 6,
	[Rr9b]	= 7,  [Rr9w]	= 7,  [Rr9d]	= 7,  [Rr9]	= 7,
	[Rr10b]	= 8,  [Rr10w]	= 8,  [Rr10d]	= 8,  [Rr10]	= 8,
	[Rr11b]	= 9,  [Rr11w]	= 9,  [Rr11d]	= 9,  [Rr11]	= 9,
	[Rr12b]	= 10, [Rr12w]	= 10, [Rr12d]	= 10, [Rr12]	= 10,
	[Rr13b]	= 11, [Rr13w]	= 11, [Rr13d]	= 11, [Rr13]	= 11,
	[Rr14b]	= 12, [Rr14w]	= 12, [Rr14d]	= 12, [Rr14]	= 12,
	[Rr15b]	= 13, [Rr15w]	= 13, [Rr15d]	= 13, [Rr15]	= 13,
	[Rrsp]	= 14, [Rrbp]	= 15,

	/* float */
	[Rxmm0f]	= 14,  [Rxmm0d]		= 14,
	[Rxmm1f]	= 15,  [Rxmm1d]		= 15,
	[Rxmm2f]	= 16,  [Rxmm2d]		= 16,
	[Rxmm3f]	= 17,  [Rxmm3d]		= 17,
	[Rxmm4f]	= 18,  [Rxmm4d]		= 18,
	[Rxmm5f]	= 19,  [Rxmm5d]		= 19,
	[Rxmm6f]	= 20,  [Rxmm6d]		= 20,
	[Rxmm7f]	= 21,  [Rxmm7d]		= 21,
	[Rxmm8f]	= 22,  [Rxmm8d]		= 22,
	[Rxmm9f]	= 23,  [Rxmm9d]		= 23,
	[Rxmm10f]	= 24,  [Rxmm10d]	= 24,
	[Rxmm11f]	= 25,  [Rxmm11d]	= 25,
	[Rxmm12f]	= 26,  [Rxmm12d]	= 26,
	[Rxmm13f]	= 27,  [Rxmm13d]	= 27,
	[Rxmm14f]	= 28,  [Rxmm14d]	= 28,
	[Rxmm15f]	= 29,  [Rxmm15d]	= 29,
};

size_t modesize[Nmode] = {
	[ModeNone]	= 0,
	[ModeB]	= 1,
	[ModeW]	= 2,
	[ModeL]	= 4,
	[ModeQ]	= 8,
	[ModeF]	= 4,
	[ModeD]	= 8,
};

static int _K[Nclass] = {
	[Classbad] = 0,
	[Classint] = 14,
	[Classflt] = 16,
};

Rclass
rclass(Loc *l)
{
	switch (l->mode) {
	case ModeNone:	return Classbad;
	case Nmode:	return Classbad;
	case ModeB:	return Classint;
	case ModeW:	return Classint;
	case ModeL:	return Classint;
	case ModeQ:	return Classint;

	case ModeF:	return Classflt;
	case ModeD:	return Classflt;
	}
	return Classbad;
}

/* %esp, %ebp are not in the allocatable pool */
static int
isfixreg(Loc *l)
{
	if (l->reg.colour == Resp)
		return 1;
	if (l->reg.colour == Rebp)
		return 1;
	return 0;
}

static size_t
uses(Insn *insn, regid *u)
{
	size_t i, j;
	int k;
	Loc *m;

	j = 0;
	/* Add all the registers used and defined. Duplicate
	 * in this list are fine, since they're being added to
	 * a set anyways */
	for (i = 0; i < Maxarg; i++) {
		if (!usetab[insn->op].l[i])
			break;
		k = usetab[insn->op].l[i] - 1;
		/* non-registers are handled later */
		if (insn->args[k]->type == Locreg)
			if (!isfixreg(insn->args[k]))
				u[j++] = insn->args[k]->reg.id;
	}
	/* some insns don't reflect their defs in the args.
	 * These are explictly listed in the insn description */
	for (i = 0; i < Nreg; i++) {
		if (!usetab[insn->op].r[i])
			break;
		/* not a leak; physical registers get memoized */
		u[j++] = locphysreg(usetab[insn->op].r[i])->reg.id;
	}
	/* If the registers are in an address calculation,
	 * they're used no matter what. */
	for (i = 0; i < insn->nargs; i++) {
		m = insn->args[i];
		if (m->type != Locmem && m->type != Locmeml)
			continue;
		if (m->mem.base)
			if (!isfixreg(m->mem.base))
				u[j++] = m->mem.base->reg.id;
		if (m->mem.idx)
			if (!isfixreg(m->mem.base))
				u[j++] = m->mem.idx->reg.id;
	}
	return j;
}

static size_t
defs(Insn *insn, regid *d)
{
	size_t i, j;
	int k;

	j = 0;
	/* Add all the registers dsed and defined. Duplicate
	 * in this list are fine, since they're being added to
	 * a set anyways */
	for (i = 0; i < Maxarg; i++) {
		if (!deftab[insn->op].l[i])
			break;
		k = deftab[insn->op].l[i] - 1;
		if (insn->args[k]->type == Locreg)
			if (!isfixreg(insn->args[k]))
				d[j++] = insn->args[k]->reg.id;
	}
	/* some insns don't reflect their defs in the args.
	 * These are explictly listed in the insn description */
	for (i = 0; i < Nreg; i++) {
		if (!deftab[insn->op].r[i])
			break;
		/* not a leak; physical registers get memoized */
		d[j++] = locphysreg(deftab[insn->op].r[i])->reg.id;
	}
	return j;
}

/* The uses and defs for an entire BB. */
static void
udcalc(Asmbb *bb)
{
	regid   u[Nreg], d[Nreg];
	size_t nu, nd;
	size_t i, j;

	bb->use = bsclear(bb->use);
	bb->def = bsclear(bb->def);
	for (i = 0; i < bb->ni; i++) {
		nu = uses(bb->il[i], u);
		nd = defs(bb->il[i], d);
		for (j = 0; j < nu; j++)
			if (!bshas(bb->def, u[j]))
				bsput(bb->use, u[j]);
		for (j = 0; j < nd; j++)
			bsput(bb->def, d[j]);
	}
}

static int
istrivial(Isel *s, regid r)
{
	return s->degree[r] < _K[rclass(locmap[r])];
}

static void
liveness(Isel *s)
{
	Bitset *old;
	Asmbb **bb;
	ssize_t nbb;
	ssize_t i;
	size_t j;
	int changed;

	bb = s->bb;
	nbb = s->nbb;
	for (i = 0; i < nbb; i++) {
		if (!bb[i])
			continue;
		udcalc(s->bb[i]);
		bb[i]->livein = bsclear(bb[i]->livein);
		bb[i]->liveout = bsclear(bb[i]->liveout);
	}

	changed = 1;
	while (changed) {
		changed = 0;
		old = NULL;
		for (i = nbb - 1; i >= 0; i--) {
			if (!bb[i])
				continue;
			old = bsdup(bb[i]->liveout);
			/* liveout[b] = U(s in succ) livein[s] */
			for (j = 0; bsiter(bb[i]->succ, &j); j++)
				bsunion(bb[i]->liveout, bb[j]->livein);
			/* livein[b] = use[b] U (out[b] \ def[b]) */
			bb[i]->livein = bsclear(bb[i]->livein);
			bsunion(bb[i]->livein, bb[i]->liveout);
			bsdiff(bb[i]->livein, bb[i]->def);
			bsunion(bb[i]->livein, bb[i]->use);
			if (!changed)
				changed = !bseq(old, bb[i]->liveout);
			bsfree(old);
		}
	}
}

/* we're only interested in register->register moves */
static int
ismove(Insn *i)
{
	if (i->op != Imov && i->op != Imovs)
		return 0;
	return i->args[0]->type == Locreg && i->args[1]->type == Locreg;
}

static int
gbhasedge(Isel *s, size_t u, size_t v)
{
	size_t i;
	i = (s->nreg * v) + u;
	return (s->gbits[i/Sizetbits] & (1ULL <<(i % Sizetbits))) != 0;
}

static void
gbputedge(Isel *s, size_t u, size_t v)
{
	size_t i, j;

	i = (s->nreg * u) + v;
	j = (s->nreg * v) + u;
	s->gbits[i/Sizetbits] |= 1ULL << (i % Sizetbits);
	s->gbits[j/Sizetbits] |= 1ULL << (j % Sizetbits);
	assert(gbhasedge(s, u, v) && gbhasedge(s, v, u));
}

static int
wlfind(Loc **wl, size_t nwl, regid v, size_t *idx)
{
	size_t i;

	for (i = 0; i < nwl; i++) {
		if (wl[i]->reg.id == v) {
			*idx = i;
			return 1;
		}
	}
	*idx = -1;
	return 0;
}

/*
 * If we have an edge between two aliasing registers,
 * we should not increment the degree, since that would
 * be double counting.
 */
static int
degreechange(Isel *s, regid u, regid v)
{
	regid phys, virt, r;
	size_t i;

	if (bshas(s->prepainted, u)) {
		phys = u;
		virt = v;
	} else if (bshas(s->prepainted, v)) {
		phys = v;
		virt = u;
	} else {
		return 1;
	}

	for (i = 0; i < Nmode; i++) {
		r = regmap[colourmap[phys]][i];
		if (r != phys && gbhasedge(s, virt, regmap[colourmap[phys]][i])) {
			return 0;
		}
	}
	return 1;
}

static void
alputedge(Isel *s, regid u, regid v)
{
	if (s->ngadj[u] == s->gadjsz[u]) {
		s->gadjsz[u] = s->gadjsz[u]*2 + 1;
		s->gadj[u] = xrealloc(s->gadj[u], s->gadjsz[u]*sizeof(regid));
	}
	s->gadj[u][s->ngadj[u]] = v;
	s->ngadj[u]++;
}

static void
wlput(Loc ***wl, size_t *nwl, Loc *l)
{
	lappend(wl, nwl, l);
	l->list = wl;
}

static void
wldel(Isel *s, Loc ***wl, size_t *nwl, size_t idx)
{
	(*wl)[idx]->list = NULL;
	ldel(wl, nwl, idx);
}

static void
wlputset(Bitset *bs, regid r)
{
	bsput(bs, r);
	locmap[r]->list = bs;
}


static void
addedge(Isel *s, regid u, regid v)
{
	if (u == v || gbhasedge(s, u, v))
		return;
	if (u == Rrbp || u == Rrsp || u == Rrip)
		return;
	if (v == Rrbp || v == Rrsp || v == Rrip)
		return;
	if (rclass(locmap[u]) != rclass(locmap[v]))
		return;
	if (bshas(s->prepainted, u) && bshas(s->prepainted, v))
		return;

	gbputedge(s, u, v);
	gbputedge(s, v, u);
	if (!bshas(s->prepainted, u)) {
		alputedge(s, u, v);
		s->degree[u] += degreechange(s, v, u);
	}
	if (!bshas(s->prepainted, v)) {
		alputedge(s, v, u);
		s->degree[v] += degreechange(s, u, v);
	}
}

static void
gfree(Isel *s)
{
	size_t i;

	for (i = 0; i < s->nreg; i++)
		free(s->gadj[i]);
	free(s->gbits);
	free(s->gadj);
	free(s->ngadj);
}

static void
setup(Isel *s)
{
	size_t gchunks;
	size_t i;

	gfree(s);
	s->nreg = maxregid;
	gchunks = (s->nreg*s->nreg)/Sizetbits + 1;
	s->gbits = zalloc(gchunks*sizeof(size_t));
	/* fresh adj list repr. */
	s->gadj = zalloc(s->nreg * sizeof(regid*));
	s->ngadj = zalloc(s->nreg * sizeof(size_t));
	s->gadjsz = zalloc(s->nreg * sizeof(size_t));

	s->mactiveset = bsclear(s->mactiveset);
	s->wlmoveset = bsclear(s->wlmoveset);
	s->spilled = bsclear(s->spilled);
	s->coalesced = bsclear(s->coalesced);
	lfree(&s->wlspill, &s->nwlspill);
	lfree(&s->wlfreeze, &s->nwlfreeze);
	lfree(&s->wlsimp, &s->nwlsimp);

	free(s->aliasmap);
	free(s->degree);
	free(s->rmoves);
	free(s->nrmoves);

	s->aliasmap = zalloc(s->nreg * sizeof(Loc*));
	s->degree = zalloc(s->nreg * sizeof(int));
	s->nuses = zalloc(s->nreg * sizeof(int));
	s->rmoves = zalloc(s->nreg * sizeof(Insn**));
	s->nrmoves = zalloc(s->nreg * sizeof(size_t));

	for (i = 0; bsiter(s->prepainted, &i); i++)
		s->degree[i] = 1<<16;
}

static void
build(Isel *s)
{
	regid u[Nreg], d[Nreg];
	size_t nu, nd;
	size_t i, k, a;
	ssize_t j;
	regid *livesparse;
	regid *livedense;
	size_t nlive;
	regid  r;
	Asmbb **bb;
	size_t nbb;
	Insn *insn;
	size_t l;

	/* set up convenience vars */
	bb = s->bb;
	nbb = s->nbb;

#define PUT(reg) do { \
	assert(reg < maxregid); \
	if (livesparse[reg] >= nlive || livedense[livesparse[reg]] != reg) {\
		livesparse[reg] = nlive; \
		livedense[nlive] = reg; \
		nlive++; \
	} \
	} while(0)

#define DEL(reg) do { \
	assert(reg < maxregid); \
	regid rtmp; \
	if (livesparse[reg] < nlive && livedense[livesparse[reg]] == reg) { \
		rtmp = livedense[nlive - 1]; \
		livedense[livesparse[reg]] = rtmp; \
		livesparse[rtmp] = livesparse[reg]; \
		nlive--; \
	} \
	} while(0)

	/* sparse sets are used here because we iterate them. A lot. */
	livedense = zalloc((maxregid + 1) * sizeof(regid));
	livesparse = zalloc((maxregid + 1) * sizeof(regid));
	for (i = 0; i < nbb; i++) {
		if (!bb[i])
			continue;
		nlive = 0;
		for (k = 0; bsiter(bb[i]->liveout, &k); k++)
			PUT(k);
		for (j = bb[i]->ni - 1; j >= 0; j--) {
			insn = bb[i]->il[j];
			nu = uses(insn, u);
			nd = defs(insn, d);

			/* add these to the initial set */
			for (k = 0; k < nu; k++) {
				if (!bshas(s->prepainted, u[k])) {
					wlputset(s->initial, u[k]);
					s->nuses[u[k]]++;
				}
			}
			for (k = 0; k < nd; k++) {
				if (!bshas(s->prepainted, d[k]))
					wlputset(s->initial, d[k]);
			}

			/* moves get special treatment, since we don't want spuriou
			 * edges between the src and dest */
			if (ismove(insn)) {
				/* live \= uses(i) */
				for (k = 0; k < nu; k++) {
					/* remove all physical register aliases */
					if (bshas(s->prepainted, u[k])) {
						for (a = 0; a < Nmode; a++) {
							r = regmap[colourmap[u[k]]][a];
							DEL(r);
						}
					} else {
						DEL(u[k]);
					}
				}

				for (k = 0; k < nu; k++)
					lappend(&s->rmoves[u[k]], &s->nrmoves[u[k]], insn);
				for (k = 0; k < nd; k++)
					lappend(&s->rmoves[d[k]], &s->nrmoves[d[k]], insn);
				lappend(&s->wlmove, &s->nwlmove, insn);
				bsput(s->wlmoveset, insn->uid);
			}
			/* live = live U def(i) */
			for (k = 0; k < nd; k++) {
				PUT(d[k]);
			}

			for (k = 0; k < nd; k++) {
				for (l = 0; l < nlive; l++) {
					addedge(s, d[k], livedense[l]);
				}
			}
			/* live = use(i) U (live \ def(i)) */
			for (k = 0; k < nd; k++) {
				DEL(d[k]);
			}

			for (k = 0; k < nu; k++) {
				PUT(u[k]);
			}
		}
	}
	free(livedense);
	free(livesparse);
#undef PUT
#undef DEL
}

static int
adjavail(Isel *s, regid r)
{
	if (locmap[r]->list == &s->selstk)
		return 0;
	if (bshas(s->coalesced, r))
		return 0;
	return 1;
}

static size_t
nodemoves(Isel *s, regid n, Insn ***pil)
{
	size_t i, count;
	regid rid;
	Insn **il;

	count = 0;
	il = malloc(s->nrmoves[n] * sizeof(Insn*));
	for (i = 0; i < s->nrmoves[n]; i++) {
		rid = s->rmoves[n][i]->uid;
		if (bshas(s->mactiveset, rid) || bshas(s->wlmoveset, rid))
			il[count++] = s->rmoves[n][i];
	}
	*pil = il;
	return count;
}


static int
moverelated(Isel *s, regid n)
{
	size_t i;

	for (i = 0; i < s->nrmoves[n]; i++) {
		if (bshas(s->mactiveset, s->rmoves[n][i]->uid))
			return 1;
		if (bshas(s->wlmoveset, s->rmoves[n][i]->uid))
			return 1;
	}
	return 0;
}

static void
mkworklist(Isel *s)
{
	size_t i;

	for (i = 0; bsiter(s->initial, &i); i++) {
		if (bshas(s->prepainted, i))
			continue;
		else if (!istrivial(s, i))
			wlput(&s->wlspill, &s->nwlspill, locmap[i]);
		else if (moverelated(s, i)) {
			wlput(&s->wlfreeze, &s->nwlfreeze, locmap[i]);
		}
		else
			wlput(&s->wlsimp, &s->nwlsimp, locmap[i]);
		locmap[i]->reg.colour = 0;
	}
}

static void
enablemove(Isel *s, regid n)
{
	size_t i, j;
	Insn **il;
	size_t ni;

	ni = nodemoves(s, n, &il);
	for (i = 0; i < ni; i++) {
		if (!bshas(s->mactiveset, il[i]->uid))
			continue;
		for (j = 0; j < s->nmactive; j++) {
			if (il[i] == s->mactive[j]) {
				ldel(&s->mactive, &s->nmactive, j);
				lappend(&s->wlmove, &s->nwlmove, il[i]);
				bsdel(s->mactiveset, il[i]->uid);
				bsput(s->wlmoveset, il[i]->uid);
			}
		}
	}
	free(il);
}

static void
decdegree(Isel *s, regid m)
{
	int before, after;
	int found;
	size_t idx, i;
	regid n;

	assert(m < s->nreg);
	before = istrivial(s, m);
	s->degree[m]--;
	after = istrivial(s, m);

	if (before != after) {
		enablemove(s, m);
		for (i = 0; i < s->ngadj[m]; i++) {
			n = s->gadj[m][i];
			if (adjavail(s, n))
				enablemove(s, n);
		}

		/* Subtle:
		 *
		 * If this code is being called from coalesce(),
		 * then the degree could have been bumped up only
		 * temporarily. This means that the node can already
		 * be on wlfreeze or wlsimp.
		 *
		 * Therefore, if we don't find it on wlspill, we assert
		 * that the node is already on the list that we'd be
		 * moving it to.
		 */
		found = wlfind(s->wlspill, s->nwlspill, m, &idx);
		if (found)
			wldel(s, &s->wlspill, &s->nwlspill, idx);
		if (moverelated(s, m)) {
			if (!found) {
				assert(wlfind(s->wlfreeze, s->nwlfreeze, m, &idx) != 0);
			} else {
				wlput(&s->wlfreeze, &s->nwlfreeze, locmap[m]);
			}
		} else {
			if (!found) {
				assert(wlfind(s->wlsimp, s->nwlsimp, m, &idx));
			} else {
				wlput(&s->wlsimp, &s->nwlsimp, locmap[m]);
			}
		}
	}
}

static void
simp(Isel *s)
{
	Loc *l;
	regid m;
	size_t i;

	l = lpop(&s->wlsimp, &s->nwlsimp);
	wlput(&s->selstk, &s->nselstk, l);
	for (i = 0; i < s->ngadj[l->reg.id]; i++) {
		m = s->gadj[l->reg.id][i];
		if (adjavail(s, m))
			decdegree(s, m);
	}
}

static regid
getmappedalias(Loc **aliasmap, size_t nreg, regid id)
{
	/*
	 * if we get called from rewrite(), we can get a register that
	 * we just created, with an id bigger than the number of entrie
	 * in the alias map. We should just return its id in that case.
	 */
	while (id < nreg) {
		if (!aliasmap[id])
			break;
		id = aliasmap[id]->reg.id;
	};
	return id;
}

static regid
getalias(Isel *s, regid id)
{
	return getmappedalias(s->aliasmap, s->nreg, id);
}

static void
wladd(Isel *s, regid u)
{
	size_t i;

	if (bshas(s->prepainted, u))
		return;
	if (moverelated(s, u))
		return;
	if (!istrivial(s, u))
		return;

	assert(locmap[u]->list == &s->wlfreeze || locmap[u]->list == &s->wlsimp);
	if (wlfind(s->wlfreeze, s->nwlfreeze, u, &i))
		wldel(s, &s->wlfreeze, &s->nwlfreeze, i);
	wlput(&s->wlsimp, &s->nwlsimp, locmap[u]);
}

static int
conservative(Isel *s, regid u, regid v)
{
	int k;
	size_t i;
	regid n;

	k = 0;
	for (i = 0; i < s->ngadj[u]; i++) {
		n = s->gadj[u][i];
		if (adjavail(s, n) && !istrivial(s, n))
			k++;
	}
	for (i = 0; i < s->ngadj[v]; i++) {
		n = s->gadj[v][i];
		if (adjavail(s, n) && !istrivial(s, n))
			k++;
	}
	return k < _K[rclass(locmap[u])];
}

/* FIXME: is this actually correct? */
static int
ok(Isel *s, regid t, regid r)
{
	return istrivial(s, t) || bshas(s->prepainted, t) || gbhasedge(s, t, r);
}

static int
combinable(Isel *s, regid u, regid v)
{
	regid t;
	size_t i;

	/* Regs of different modes can't be combined as things stand.
	 * In principle they should be combinable, but it confused the
	 * whole mode dance. */
	if (locmap[u]->mode != locmap[v]->mode)
		return 0;
	/* if u isn't prepainted, can we conservatively coalesce? */
	if (!bshas(s->prepainted, u) && conservative(s, u, v))
		return 1;

	/* if it is, are the adjacent nodes ok to combine with this? */
	for (i = 0; i < s->ngadj[v]; i++) {
		t = s->gadj[v][i];
		if (adjavail(s, t) && !ok(s, t, u))
			return 0;
	}
	return 1;
}

static void
combine(Isel *s, regid u, regid v)
{
	regid t;
	size_t idx;
	size_t i, j;
	int has;

	if (debugopt['r'] > 2)
		printedge(stdout, "combining:", u, v);
	if (wlfind(s->wlfreeze, s->nwlfreeze, v, &idx))
		wldel(s, &s->wlfreeze, &s->nwlfreeze, idx);
	else if (wlfind(s->wlspill, s->nwlspill, v, &idx)) {
		wldel(s, &s->wlspill, &s->nwlspill, idx);
	}
	wlputset(s->coalesced, v);
	s->aliasmap[v] = locmap[u];
	s->nuses[u] += s->nuses[v];

	/* nodemoves[u] = nodemoves[u] U nodemoves[v] */
	for (i = 0; i < s->nrmoves[v]; i++) {
		has = 0;
		for (j = 0; j < s->nrmoves[u]; j++) {
			if (s->rmoves[v][i] == s->rmoves[u][j]) {
				has = 1;
				break;
			}
		}
		if (!has)
			lappend(&s->rmoves[u], &s->nrmoves[u], s->rmoves[v][i]);
	}

	for (i = 0; i < s->ngadj[v]; i++) {
		t = s->gadj[v][i];
		if (!adjavail(s, t))
			continue;
		if (debugopt['r'] > 2)
			printedge(stdout, "combine-putedge:", t, u);
		addedge(s, t, u);
		decdegree(s, t);
	}
	if (!istrivial(s, u) && wlfind(s->wlfreeze, s->nwlfreeze, u, &idx)) {
		wldel(s, &s->wlfreeze, &s->nwlfreeze, idx);
		wlput(&s->wlspill, &s->nwlspill, locmap[u]);
	}
}

static int
constrained(Isel *s, regid u, regid v)
{
	size_t i;

	if (bshas(s->prepainted, v))
		return 1;
	if (bshas(s->prepainted, u))
		for (i = 0; i < Nmode; i++)
			if (regmap[colourmap[u]][i] && gbhasedge(s, regmap[colourmap[u]][i], v))
				return 1;
	return gbhasedge(s, u, v);
}

static void
coalesce(Isel *s)
{
	Insn *m;
	regid u, v, tmp;

	m = lpop(&s->wlmove, &s->nwlmove);
	bsdel(s->wlmoveset, m->uid);
	u = getalias(s, m->args[0]->reg.id);
	v = getalias(s, m->args[1]->reg.id);

	if (bshas(s->prepainted, v)) {
		tmp = u;
		u = v;
		v = tmp;
	}

	if (u == v) {
		lappend(&s->mcoalesced, &s->nmcoalesced, m);
		wladd(s, u);
		wladd(s, v);
	} else if (constrained(s, u, v)) {
		lappend(&s->mconstrained, &s->nmconstrained, m);
		wladd(s, u);
		wladd(s, v);
	} else if (combinable(s, u, v)) {
		lappend(&s->mcoalesced, &s->nmcoalesced, m);
		combine(s, u, v);
		wladd(s, u);
	} else {
		lappend(&s->mactive, &s->nmactive, m);
		bsput(s->mactiveset, m->uid);
	}
}

static int
mldel(Insn ***ml, size_t *nml, Bitset *bs, Insn *m)
{
	size_t i;
	if (bshas(bs, m->uid)) {
		bsdel(bs, m->uid);
		for (i = 0; i < *nml; i++) {
			if (m == (*ml)[i]) {
				ldel(ml, nml, i);
				return 1;
			}
		}
	}
	return 0;
}

static void
freezemoves(Isel *s, Loc *u)
{
	size_t i;
	Insn **ml;
	Insn *m;
	size_t nml;
	size_t idx;
	Loc *v;

	nml = nodemoves(s, u->reg.id, &ml);
	for (i = 0; i < nml; i++) {
		m = ml[i];
		if (getalias(s, m->args[0]->reg.id) == getalias(s, u->reg.id))
			v = locmap[getalias(s, m->args[1]->reg.id)];
		else
			v = locmap[getalias(s, m->args[0]->reg.id)];

		if (!mldel(&s->mactive, &s->nmactive, s->mactiveset, m))
			mldel(&s->wlmove, &s->nwlmove, s->wlmoveset, m);

		lappend(&s->mfrozen, &s->nmfrozen, m);
		if (!moverelated(s, v->reg.id) && istrivial(s, v->reg.id)) {
			if (!wlfind(s->wlfreeze, s->nwlfreeze, v->reg.id, &idx))
				die("Reg %zd not in freeze wl\n", v->reg.id);
			wldel(s, &s->wlfreeze, &s->nwlfreeze, idx);
			wlput(&s->wlsimp, &s->nwlsimp, v);
		}

	}
	lfree(&ml, &nml);
}

static void
freeze(Isel *s)
{
	Loc *l;

	l = lpop(&s->wlfreeze, &s->nwlfreeze);
	wlput(&s->wlsimp, &s->nwlsimp, l);
	freezemoves(s, l);
}

/* Select the spill candidates */
static void
selspill(Isel *s)
{
	size_t i;
	Loc *m;

	/* FIXME: pick a better heuristic for spilling */
	m = NULL;
	for (i = 0; i < s->nwlspill; i++) {
		if (!bshas(s->shouldspill, s->wlspill[i]->reg.id))
			continue;
		m = s->wlspill[i];
		wldel(s, &s->wlspill, &s->nwlspill, i);
		break;
	}
	if (!m) {
		for (i = 0; i < s->nwlspill; i++) {
			if (bshas(s->neverspill, s->wlspill[i]->reg.id)) {
				continue;
			}
			m = s->wlspill[i];
			wldel(s, &s->wlspill, &s->nwlspill, i);
			break;
		}
	}
	assert(m != NULL);
	wlput(&s->wlsimp, &s->nwlsimp, m);
	freezemoves(s, m);
}

/*
 * Selects the colours for registers, spilling to the
 * stack if no free registers can be found.
 */
static int
paint(Isel *s)
{
	int taken[Nreg];
	Loc *n, *w;
	regid l;
	size_t i, j;
	int spilled;
	int found;

	spilled = 0;
	while (s->nselstk) {
		memset(taken, 0, Nreg*sizeof(int));
		n = lpop(&s->selstk, &s->nselstk);

		for (j = 0; j < s->ngadj[n->reg.id];j++) {
			l = s->gadj[n->reg.id][j];
			if (debugopt['r'] > 1)
				printedge(stdout, "paint-edge:", n->reg.id, l);
			w = locmap[getalias(s, l)];
			if (w->reg.colour)
				taken[colourmap[w->reg.colour]] = 1;
		}

		found = 0;
		for (i = 0; i < Northogonal; i++) {
			if (regmap[i][n->mode] && !taken[i]) {
				n->reg.colour = regmap[i][n->mode];
				found = 1;
				break;
			}
		}
		if (!found) {
			spilled = 1;
			wlputset(s->spilled, n->reg.id);
		}
	}
	for (l = 0; bsiter(s->coalesced, &l); l++) {
		n = locmap[getalias(s, l)];
		locmap[l]->reg.colour = n->reg.colour;
	}
	return spilled;
}

static Loc *
mapfind(Isel *s, Htab *map, Loc *old)
{
	Loc *new;
	Loc *base;
	Loc *idx;
	regid id;

	if (!old)
		return NULL;

	new = NULL;
	if (old->type == Locreg) {
		id = getalias(s, old->reg.id);
		new = htget(map, locmap[id]);
	} else if (old->type == Locmem || old->type == Locmeml) {
		base = old->mem.base;
		idx = old->mem.idx;
		if (base)
			base = locmap[getalias(s, base->reg.id)];
		if (idx)
			idx = locmap[getalias(s, idx->reg.id)];
		base = mapfind(s, map, base);
		idx = mapfind(s, map, idx);
		if (base != old->mem.base || idx != old->mem.idx) {
			if (old->type == Locmem)
				new = locmems(old->mem.constdisp, base, idx, old->mem.scale, old->mode);
			else
				new = locmemls(old->mem.lbldisp, base, idx, old->mem.scale, old->mode);
		}
	}
	if (new)
		return new;
	return old;
}

static Loc *
spillslot(Isel *s, regid reg)
{
	size_t stkoff;

	stkoff = ptoi(htget(s->spillslots, itop(reg)));
	return locmem(-stkoff, locphysreg(Rrbp), NULL, locmap[reg]->mode);
}

static void
updatelocs(Isel *s, Htab *map, Insn *insn)
{
	size_t i;

	for (i = 0; i < insn->nargs; i++) {
		insn->args[i] = mapfind(s, map, insn->args[i]);
		insn->args[i] = mapfind(s, map, insn->args[i]);
	}
}

/*
 * Takes two tables for remappings, of size Nreg/Nreg,
 * and fills them, storign the number of uses or defs. Return
 * whether there are any remappings at all.
 */
static int
remap(Isel *s, Htab *map, Insn *insn, regid *use, size_t nuse, regid *def, size_t ndef)
{
	regid ruse, rdef;
	int remapped;
	Loc *tmp;
	size_t i;

	remapped = 0;
	for (i = 0; i < nuse; i++) {
		ruse = getalias(s, use[i]);
		if (!bshas(s->spilled, ruse))
			continue;
		tmp = locreg(locmap[ruse]->mode);
		htput(map, locmap[ruse], tmp);
		bsput(s->neverspill, tmp->reg.id);
		remapped = 1;
	}

	for (i = 0; i < ndef; i++) {
		rdef = getalias(s, def[i]);
		if (!bshas(s->spilled, rdef))
			continue;
		if (hthas(map, locmap[rdef]))
			continue;
		tmp = locreg(locmap[rdef]->mode);
		htput(map, locmap[rdef], tmp);
		bsput(s->neverspill, tmp->reg.id);
		remapped = 1;
	}

	return remapped;
}

static int
nopmov(Isel *s, Insn *insn)
{
	if (insn->op != Imov)
		return 0;
	if (insn->args[0]->type != Locreg || insn->args[1]->type != Locreg)
		return 0;
	/* Prepainted register moves need to be kept live to avoid coalescing over them */
	return insn->args[0]->reg.id == insn->args[1]->reg.id && !bshas(s->prepainted, insn->args[0]->reg.id);
}

void
replacealias(Isel *s, Loc **map, size_t nreg, Insn *insn)
{
	size_t i;
	Loc *l;

	if (!map)
		return;
	for (i = 0; i < insn->nargs; i++) {
		l = insn->args[i];
		if (l->type == Locreg) {
			insn->args[i] = locmap[getalias(s, l->reg.id)];
		} else if (l->type == Locmem || l->type == Locmeml) {
			if (l->mem.base)
				l->mem.base = locmap[getalias(s, l->mem.base->reg.id)];
			if (l->mem.idx)
				l->mem.idx = locmap[getalias(s, l->mem.idx->reg.id)];
		}
	}
}

static ulong
reglochash(void *p)
{
	Loc *l;

	l = p;
	return inthash(l->reg.id);
}


static int
regloceq(void *pa, void *pb)
{
	Loc *a, *b;

	a = pa;
	b = pb;
	return a->reg.id == b->reg.id;
}
/*
 * Rewrite instructions using spilled registers, inserting
 * appropriate loads and stores into the BB
 */
static void
rewritebb(Isel *s, Asmbb *bb, Loc **aliasmap)
{
	regid use[Nreg], def[Nreg];
	size_t nuse, ndef;
	Insn *insn, *mov;
	size_t i, j;
	Insn **new;
	size_t nnew;
	Htab *map;
	Loc *tmp;

	new = NULL;
	nnew = 0;
	if (!bb)
		return;
	map = mkht(reglochash, regloceq);
	for (j = bb->ni; j > 0; j--) {
		insn = bb->il[j - 1];
		replacealias(s, aliasmap, s->nreg, insn);
		if (nopmov(s, insn))
			continue;
		nuse = uses(insn, use);
		ndef = defs(insn, def);
		/* if there is a remapping, insert the loads and stores as needed */
		if (remap(s, map, insn, use, nuse, def, ndef)) {
			for (i = 0; i < ndef; i++) {
				tmp = htget(map, locmap[def[i]]);
				if (!tmp)
					continue;
				if (isfloatmode(tmp->mode))
					mov = mkinsn(Imovs, tmp, spillslot(s, def[i]), NULL);
				else
					mov = mkinsn(Imov, tmp, spillslot(s, def[i]), NULL);
				lappend(&new, &nnew, mov);
			}
			updatelocs(s, map, insn);
			lappend(&new, &nnew, insn);
			for (i = 0; i < nuse; i++) {
				tmp = htget(map, locmap[use[i]]);
				if (!tmp)
					continue;
				if (isfloatmode(tmp->mode))
					mov = mkinsn(Imovs, spillslot(s, use[i]), tmp, NULL);
				else
					mov = mkinsn(Imov, spillslot(s, use[i]), tmp, NULL);
				lappend(&new, &nnew, mov);
			}
			for (i = 0; i < nuse; i++)
				htdel(map, locmap[use[i]]);
			for (i = 0; i < ndef; i++)
				htdel(map, locmap[def[i]]);
		} else {
			lappend(&new, &nnew, insn);
		}
	}
	for (i = 0; i < nnew/2; i++) {
		insn = new[i];
		new[i] = new[nnew - i - 1];
		new[nnew - i -1] = insn;
	}
	lfree(&bb->il, &bb->ni);
	bb->il = new;
	bb->ni = nnew;
}

static void
addspill(Isel *s, Loc *l)
{
	s->stksz->lit += modesize[l->mode];
	s->stksz->lit = align(s->stksz->lit, modesize[l->mode]);
	if (debugopt['r']) {
		printf("spill ");
		dbglocprint(stdout, l, 'x');
		printf(" to %zd(%%rbp)\n", s->stksz->lit);
	}
	htput(s->spillslots, itop(l->reg.id), itop(s->stksz->lit));
}

/*
 * Rewrites the function code so that it no longer contain
 * references to spilled registers. Every use of spilled reg
 *
 *      insn %rX,%rY
 *
 * is rewritten to look like:
 *
 *      mov 123(%rsp),%rZ
 *      insn %rZ,%rW
 *      mov %rW,234(%rsp)
 */
static void
rewrite(Isel *s, Loc **aliasmap)
{
	size_t i;

	s->spillslots = mkht(ptrhash, ptreq);
	/* set up stack locations for all spilled registers. */
	for (i = 0; bsiter(s->spilled, &i); i++)
		addspill(s, locmap[i]);

	/* rewrite instructions using them */
	for (i = 0; i < s->nbb; i++)
		rewritebb(s, s->bb[i], aliasmap);
	htfree(s->spillslots);
	bsclear(s->spilled);
}

/*
 * Coalescing registers leaves a lot
 * of moves that look like
 *
 *      mov %r123,%r123.
 *
 * This is useless. This deletes them.
 */
static void
delnops(Isel *s)
{
	Insn *insn;
	Asmbb *bb;
	Insn **new;
	size_t nnew;
	size_t i, j;

	for (i = 0; i < s->nbb; i++) {
		if (!s->bb[i])
			continue;
		new = NULL;
		nnew = 0;
		bb = s->bb[i];
		for (j = 0; j < bb->ni; j++) {
			insn = bb->il[j];
			if (ismove(insn) && insn->args[0]->reg.colour == insn->args[1]->reg.colour)
				continue;
			lappend(&new, &nnew, insn);
		}
		lfree(&bb->il, &bb->ni);
		bb->il = new;
		bb->ni = nnew;
	}
	if (debugopt['r'])
		dumpasm(s, stdout);
}

void
regalloc(Isel *s)
{
	int spilled;
	size_t i;
	Loc **aliasmap;

	/* Initialize the list of prepainted registers */
	s->prepainted = mkbs();
	bsput(s->prepainted, 0);
	for (i = 0; i < Nreg; i++)
		bsput(s->prepainted, i);

	s->shouldspill = mkbs();
	s->neverspill = mkbs();
	s->initial = mkbs();
	for (i = 0; i < s->nsaved; i++)
		bsput(s->shouldspill, s->calleesave[i]->reg.id);
	do {
		aliasmap = NULL;
		setup(s);
		liveness(s);
		build(s);
		mkworklist(s);
		if (debugopt['r'])
			dumpasm(s, stdout);
		do {
			if (s->nwlsimp)
				simp(s);
			else if (s->nwlmove)
				coalesce(s);
			else if (s->nwlfreeze)
				freeze(s);
			else if (s->nwlspill) {
				if (!aliasmap)
					aliasmap = memdup(s->aliasmap, s->nreg * sizeof(Loc*));
				selspill(s);
			}
		} while (s->nwlsimp || s->nwlmove || s->nwlfreeze || s->nwlspill);
		spilled = paint(s);
		if (spilled)
			rewrite(s, aliasmap);
	} while (spilled);
	delnops(s);
	bsfree(s->prepainted);
	bsfree(s->shouldspill);
	bsfree(s->neverspill);
	gfree(s);
}

void
wlprint(FILE *fd, char *name, Loc **wl, size_t nwl)
{
	size_t i;
	char *sep;

	sep = "";
	fprintf(fd, "%s = [", name);
	for (i = 0; i < nwl; i++) {
		fprintf(fd, "%s", sep);
		dbglocprint(fd, wl[i], 'x');
		fprintf(fd, "(%zd)", wl[i]->reg.id);
		sep = ",";
	}
	fprintf(fd, "]\n");
}

static void
setprint(FILE *fd, Bitset *s)
{
	char *sep;
	size_t i;

	sep = "";
	for (i = 0; i < bsmax(s); i++) {
		if (bshas(s, i)) {
			fprintf(fd, "%s%zd", sep, i);
			sep = ",";
		}
	}
	fprintf(fd, "\n");
}

static void
locsetprint(FILE *fd, Bitset *s)
{
	char *sep;
	size_t i;

	sep = "";
	for (i = 0; i < bsmax(s); i++) {
		if (bshas(s, i)) {
			fprintf(fd, "%s", sep);
			dbglocprint(fd, locmap[i], 'x');
			sep = ",";
		}
	}
	fprintf(fd, "\n");
}

static void
printedge(FILE *fd, char *msg, size_t a, size_t b)
{
	fprintf(fd, "\t%s ", msg);
	dbglocprint(fd, locmap[a], 'x');
	fprintf(fd, " -- ");
	dbglocprint(fd, locmap[b], 'x');
	fprintf(fd, "\n");
}

void
dumpasm(Isel *s, FILE *fd)
{
	size_t i, j;
	char *sep;
	Asmbb *bb;

	fprintf(fd, "function %s\n", s->name);
	fprintf(fd, "WORKLISTS -- \n");
	wlprint(stdout, "spill", s->wlspill, s->nwlspill);
	wlprint(stdout, "simp", s->wlsimp, s->nwlsimp);
	wlprint(stdout, "freeze", s->wlfreeze, s->nwlfreeze);
	/* noisy to dump this all the time; only dump for higher debug levels */
	if (debugopt['r'] > 2) {
		fprintf(fd, "IGRAPH ----- \n");
		for (i = 0; i < s->nreg; i++) {
			for (j = i; j < s->nreg; j++) {
				if (gbhasedge(s, i, j))
					printedge(stdout, "", i, j);
			}
		}
	}
	fprintf(fd, "ASM -------- \n");
	for (j = 0; j < s->nbb; j++) {
		bb = s->bb[j];
		if (!bb)
			continue;
		fprintf(fd, "\n");
		fprintf(fd, "Bb: %d labels=(", bb->id);
		sep = "";
		for (i = 0; i < bb->nlbls; i++) {;
			fprintf(fd, "%s%s", bb->lbls[i], sep);
			sep = ",";
		}
		fprintf(fd, ")\n");

		fprintf(fd, "Pred: ");
		setprint(fd, bb->pred);
		fprintf(fd, "Succ: ");
		setprint(fd, bb->succ);

		fprintf(fd, "Use: ");
		locsetprint(fd, bb->use);
		fprintf(fd, "Def: ");
		locsetprint(fd, bb->def);
		fprintf(fd, "Livein:  ");
		locsetprint(fd, bb->livein);
		fprintf(fd, "Liveout: ");
		locsetprint(fd, bb->liveout);
		for (i = 0; i < bb->ni; i++)
			dbgiprintf(fd, bb->il[i]);
	}
	fprintf(fd, "ENDASM -------- \n");
}