inline.c

#include "all.h"

/* Module-wide function inlining.
 *
 * Requires whole-program mode (-O), where parse() collects every function
 * and keeps it resident in the alloc pool until freeall() at the very end.
 * The pass runs over the collected Fn set before any per-function lowering.
 *
 * Strategy (conservative): inline a call site when the callee
 *   - is another module function (not extern, not a hardware symbol),
 *   - is a leaf (contains no call) and not itself the caller (no recursion),
 *   - is not variadic and does not use vastart,
 *   - has a scalar return (retty < 0) and only scalar params/args
 *     (no aggregates, no environment/closure params),
 *   - does no stack allocation (alloc/salloc),
 *   - is small enough (calleesize <= MAXINLINE) and the caller stays under
 *     MAXFN total instructions.
 *
 * The clone remaps every callee temporary to a fresh caller temporary,
 * binds callee params to the caller's argument values, routes every return
 * through a continuation block whose phi redefines the original call result
 * temporary, and re-routes the call block to the cloned entry block.
 * Because the pass only ever removes a call and never introduces one, the
 * per-caller fixpoint loop terminates.  fillcfg() (run by the normal
 * pipeline) rebuilds rpo/preds/phis from the updated start/s1/s2/ins/jmp,
 * so the inliner does not need to maintain CFG data itself.
 */

#define MAXINLINE 200   /* max instructions in an inlineable callee */
#define MAXFN     10000 /* max total instructions in a caller */

static Fn **ftab;
static uint fmask;

static void
modinit(Fn **mod, uint nmod)
{
	uint cap, i, h;

	cap = 1;
	while (cap < nmod * 2)
		cap <<= 1;
	fmask = cap - 1;
	ftab = emalloc(cap * sizeof *ftab);
	for (i = 0; i < cap; i++)
		ftab[i] = 0;
	for (i = 0; i < nmod; i++) {
		h = intern(mod[i]->name) & fmask;
		while (ftab[h])
			h = (h + 1) & fmask;
		ftab[h] = mod[i];
	}
}

static Fn *
modlookup(Con *c)
{
	uint h;

	if (c->type != CAddr || (c->sym.type & (SExt | SThr)))
		return 0;
	h = c->sym.id & fmask;
	while (ftab[h]) {
		if (intern(ftab[h]->name) == c->sym.id)
			return ftab[h];
		h = (h + 1) & fmask;
	}
	return 0;
}

static uint
calleesize(Fn *M)
{
	Blk *b;
	uint n = 0;

	for (b = M->start; b; b = b->link)
		n += b->nins;
	return n;
}

/* Number of leading scalar params of M, or -1 if it has an aggregate/env
 * param before the first non-param instruction. */
static int
scalar_params(Fn *M)
{
	Ins *i;
	int n = 0;

	for (i = M->start->ins; i < &M->start->ins[M->start->nins]; i++) {
		if (i->op >= Opar && i->op <= Oparuh)
			n++;
		else if (ispar(i->op))
			return -1; /* parc/pare */
		else
			break;
	}
	return n;
}

static int
callee_ok(Fn *C, Fn *M)
{
	Blk *b;
	Ins *i;

	if (M == C || M->vararg || M->retty >= 0)
		return 0;
	if (calleesize(M) > MAXINLINE)
		return 0;
	if (scalar_params(M) < 0)
		return 0;
	for (b = M->start; b; b = b->link) {
		if (b->jmp.type == Jretc)
			return 0;
		for (i = b->ins; i < &b->ins[b->nins]; i++)
			switch (i->op) {
			case Ocall:
			case Oparc: case Opare:
			case Oargc: case Oarge: case Oargv:
			case Ovastart:
			case Oalloc4: case Oalloc8: case Oalloc16:
			case Osalloc:
				return 0;
			default:
				break;
			}
	}
	return 1;
}

static Ref
remap(Ref r, Fn *caller, Fn *callee, Ref *map)
{
	uint t;

	switch (rtype(r)) {
	case RTmp:
		t = r.val;
		if (t < Tmp0)
			return r; /* hardware register: pass through */
		return map[t];
	case RCon:
		return newcon(&callee->con[r.val], caller);
	default: /* RInt, RType */
		return r;
	}
}

/* Copy n instructions from src into dst, remapping operands.
 * Returns the number written (Onop instructions are dropped). */
static uint
clone_ins(Ins *dst, Ins *src, uint n, Fn *C, Fn *M, Ref *map)
{
	Ins ii;
	uint k, d = 0;

	for (k = 0; k < n; k++) {
		ii = src[k];
		if (rtype(ii.to) == RTmp && ii.to.val >= Tmp0)
			ii.to = map[ii.to.val];
		ii.arg[0] = remap(ii.arg[0], C, M, map);
		ii.arg[1] = remap(ii.arg[1], C, M, map);
		if (ii.op != Onop)
			dst[d++] = ii;
	}
	return d;
}

/* Inline the call at block b, ins index j (caller C, callee M).
 * Returns 1 if inlined (caller restructured; must rescan), 0 if skipped. */
static int
inline_callsite(Fn *C, Blk *b, uint j, Fn *M)
{
	Blk **bmap, *cb, *mb, *cont, *chead, *ctail, *t;
	Blk **retblk;
	Ins *i, *call, *pre, *post;
	Ref *map, *retarg, argvals[64];
	Phi *ph;
	uint t2, k, nargs, npre, npost, nret, np;
	uchar *parmask;
	short oldjmp;
	Ref oldarg;
	Blk *olds1, *olds2;

	call = &b->ins[j];
	if (call->arg[0].type != RCon)
		return 0;

	/* collect scalar arg values preceding the call */
	nargs = 0;
	for (k = j; k > 0 && nargs < 64
	     && b->ins[k-1].op >= Oarg && b->ins[k-1].op <= Oarguh; k--)
		argvals[nargs++] = b->ins[k-1].arg[0];
	for (t2 = 0; t2 < nargs / 2; t2++) {
		Ref tmp = argvals[t2];
		argvals[t2] = argvals[nargs-1-t2];
		argvals[nargs-1-t2] = tmp;
	}
	npre = k; /* args occupied indices k..j-1 */

	np = scalar_params(M);
	if ((uint)np != nargs)
		return 0;
	if (calleesize(C) + calleesize(M) > MAXFN)
		return 0;

	map = alloc(M->ntmp * sizeof *map);
	memset(map, 0, M->ntmp * sizeof *map);
	parmask = alloc(M->ntmp);
	memset(parmask, 0, M->ntmp);

	/* bind callee params to caller argument values */
	for (i = M->start->ins; i < &M->start->ins[M->start->nins]; i++) {
		if (i->op >= Opar && i->op <= Oparuh) {
			uint pt = i->to.val;
			assert(pt >= Tmp0 && pt < (uint)M->ntmp);
			map[pt] = argvals[nargs - np];
			parmask[pt] = 1;
			np--;
		} else
			break;
	}

	/* fresh caller temps for every other callee temp */
	for (t2 = Tmp0; t2 < (uint)M->ntmp; t2++)
		if (!parmask[t2])
			map[t2] = newtmp(M->tmp[t2].name, M->tmp[t2].cls, C);

	/* pass 1: create cloned blocks + continuation, chain them in M's
	 * link order so the continuation phi argument order matches the
	 * predecessor order that fillpreds() derives from the link chain */
	bmap = alloc(M->nblk * sizeof *bmap);
	memset(bmap, 0, M->nblk * sizeof *bmap);
	chead = ctail = 0;
	for (mb = M->start; mb; mb = mb->link) {
		cb = newblk();
		bmap[mb->id] = cb;
		if (!chead)
			chead = cb;
		else
			ctail->link = cb;
		ctail = cb;
	}
	cont = newblk();
	ctail->link = cont;
	ctail = cont;
	ctail->link = 0;

	/* pass 2: fill clones */
	nret = 0;
	retarg = alloc(M->nblk * sizeof *retarg);
	retblk = alloc(M->nblk * sizeof *retblk);
	for (mb = M->start; mb; mb = mb->link) {
		Phi *p, *last = 0;
		Ins *buf;
		uint ci = 0;

		cb = bmap[mb->id];
		/* clone phis */
		for (p = mb->phi; p; p = p->link) {
			Phi *np_phi = alloc(sizeof *np_phi);
			np_phi->to = remap(p->to, C, M, map);
			np_phi->cls = p->cls;
			np_phi->narg = p->narg;
			np_phi->arg = alloc(p->narg * sizeof *np_phi->arg);
			np_phi->blk = alloc(p->narg * sizeof *np_phi->blk);
			for (k = 0; k < p->narg; k++) {
				np_phi->arg[k] = remap(p->arg[k], C, M, map);
				np_phi->blk[k] = bmap[p->blk[k]->id];
			}
			if (last)
				last->link = np_phi;
			else
				cb->phi = np_phi;
			last = np_phi;
		}
		/* clone ins (strip leading params of the entry block) */
		if (mb == M->start) {
			i = mb->ins;
			while (i < &mb->ins[mb->nins] && ispar(i->op))
				i++;
			buf = alloc((mb->nins - (i - mb->ins)) * sizeof *buf);
			ci = clone_ins(buf, i, mb->nins - (i - mb->ins), C, M, map);
		} else {
			buf = alloc(mb->nins * sizeof *buf);
			ci = clone_ins(buf, mb->ins, mb->nins, C, M, map);
		}
		if (ci)
			idup(cb, buf, ci);
		else
			cb->nins = 0;
		/* clone jmp */
		if (isret(mb->jmp.type)) {
			cb->jmp.type = Jjmp;
			cb->jmp.arg = R;
			cb->s1 = cont;
			cb->s2 = 0;
			if (mb->jmp.type != Jret0) {
				retarg[nret] = remap(mb->jmp.arg, C, M, map);
				retblk[nret] = cb;
				nret++;
			}
		} else {
			cb->jmp = mb->jmp;
			if (!req(mb->jmp.arg, R))
				cb->jmp.arg = remap(mb->jmp.arg, C, M, map);
			cb->s1 = mb->s1 ? bmap[mb->s1->id] : 0;
			cb->s2 = mb->s2 ? bmap[mb->s2->id] : 0;
		}
	}

	/* append cloned region + continuation to caller's link chain */
	for (t = C->start; t && t->link; t = t->link)
		;
	if (t)
		t->link = chead;
	else
		C->start = chead;

	/* rewrite the call block: prelude + jump to cloned entry */
	npost = b->nins - j - 1;
	pre = npre ? alloc(npre * sizeof *pre) : 0;
	post = npost ? alloc(npost * sizeof *post) : 0;
	if (npre)
		memcpy(pre, b->ins, npre * sizeof *pre);
	if (npost)
		memcpy(post, &b->ins[j+1], npost * sizeof *post);
	oldjmp = b->jmp.type;
	oldarg = b->jmp.arg;
	olds1 = b->s1;
	olds2 = b->s2;

	if (npre)
		idup(b, pre, npre);
	else
		b->nins = 0;
	b->jmp.type = Jjmp;
	b->jmp.arg = R;
	b->s1 = bmap[M->start->id];
	b->s2 = 0;

	/* continuation: original post + original jmp, with a return phi
	 * redefining the call's result temporary */
	if (npost)
		idup(cont, post, npost);
	else
		cont->nins = 0;
	cont->jmp.type = oldjmp;
	cont->jmp.arg = oldarg;
	cont->s1 = olds1;
	cont->s2 = olds2;
	if (!req(call->to, R)) {
		ph = alloc(sizeof *ph);
		ph->to = call->to;
		ph->cls = call->cls;
		ph->narg = nret;
		ph->arg = alloc(nret * sizeof *ph->arg);
		ph->blk = alloc(nret * sizeof *ph->blk);
		for (k = 0; k < nret; k++) {
			ph->arg[k] = retarg[k];
			ph->blk[k] = retblk[k];
		}
		ph->link = cont->phi;
		cont->phi = ph;
	}

	return 1;
}

static void
recompute_leaf(Fn *C)
{
	Blk *b;
	Ins *i;

	C->leaf = 1;
	for (b = C->start; b; b = b->link)
		for (i = b->ins; i < &b->ins[b->nins]; i++)
			if (i->op == Ocall)
				C->leaf = 0;
}

void
inline_module(Fn **mod, uint nmod)
{
	uint i;

	modinit(mod, nmod);
	for (i = 0; i < nmod; i++) {
		Fn *C = mod[i];
		int changed = 1;

		while (changed) {
			Blk *b;
			uint j;
			changed = 0;
			for (b = C->start; b; b = b->link) {
				for (j = 0; j < b->nins; j++) {
					Ins *call = &b->ins[j];
					Fn *M;
					if (call->op != Ocall)
						continue;
					if (call->arg[0].type != RCon)
						continue;
					M = modlookup(&C->con[call->arg[0].val]);
					if (!M || !callee_ok(C, M))
						continue;
					if (inline_callsite(C, b, j, M)) {
						changed = 1;
						break;
					}
				}
				if (changed)
					break;
			}
		}
		recompute_leaf(C);
	}
	free(ftab);
}