1/*	Id: inline.c,v 1.2 2012/03/22 18:51:40 plunky Exp 	*/
2/*	$NetBSD: inline.c,v 1.1.1.1.2.1 2012/04/03 16:36:22 riz Exp $	*/
3/*
4 * Copyright (c) 2003, 2008 Anders Magnusson (ragge@ludd.luth.se).
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 *    notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 *    notice, this list of conditions and the following disclaimer in the
14 *    documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
17 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
25 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
27
28
29#include "pass1.h"
30
31#include <stdarg.h>
32
33/*
34 * Simple description of how the inlining works:
35 * A function found with the keyword "inline" is always saved.
36 * If it also has the keyword "extern" it is written out thereafter.
37 * If it has the keyword "static" it will be written out if it is referenced.
38 * inlining will only be done if -xinline is given, and only if it is
39 * possible to inline the function.
40 */
41static void printip(struct interpass *pole);
42
43struct ntds {
44	int temp;
45	TWORD type;
46	union dimfun *df;
47	struct attr *attr;
48};
49
50/*
51 * ilink from ipole points to the next struct in the list of functions.
52 */
53static struct istat {
54	SLIST_ENTRY(istat) link;
55	struct symtab *sp;
56	int flags;
57#define	CANINL	1	/* function is possible to inline */
58#define	WRITTEN	2	/* function is written out */
59#define	REFD	4	/* Referenced but not yet written out */
60	struct ntds *nt;/* Array of arg temp type data */
61	int nargs;	/* number of args in array */
62	int retval;	/* number of return temporary, if any */
63	struct interpass shead;
64} *cifun;
65
66static SLIST_HEAD(, istat) ipole = { NULL, &ipole.q_forw };
67static int nlabs;
68
69#define	IP_REF	(MAXIP+1)
70#ifdef PCC_DEBUG
71#define	SDEBUG(x)	if (sdebug) printf x
72#else
73#define	SDEBUG(x)
74#endif
75
76int isinlining;
77int inlnodecnt, inlstatcnt;
78
79#define	SZSI	sizeof(struct istat)
80#define	ialloc() memset(permalloc(SZSI), 0, SZSI); inlstatcnt++
81
82static void
83tcnt(NODE *p, void *arg)
84{
85	inlnodecnt++;
86	if (nlabs > 1 && (p->n_op == REG || p->n_op == OREG) &&
87	    regno(p) == FPREG)
88		SLIST_FIRST(&ipole)->flags &= ~CANINL; /* no stack refs */
89	if (p->n_op == NAME || p->n_op == ICON)
90		p->n_sp = NULL; /* let symtabs be freed for inline funcs */
91	if (ndebug)
92		printf("locking node %p\n", p);
93}
94
95static struct istat *
96findfun(struct symtab *sp)
97{
98	struct istat *is;
99
100	SLIST_FOREACH(is, &ipole, link)
101		if (is->sp == sp)
102			return is;
103	return NULL;
104}
105
106static void
107refnode(struct symtab *sp)
108{
109	struct interpass *ip;
110
111	SDEBUG(("refnode(%s)\n", sp->sname));
112
113	ip = permalloc(sizeof(*ip));
114	ip->type = IP_REF;
115	ip->ip_name = (char *)sp;
116	inline_addarg(ip);
117}
118
119void
120inline_addarg(struct interpass *ip)
121{
122	extern NODE *cftnod;
123
124	SDEBUG(("inline_addarg(%p)\n", ip));
125	DLIST_INSERT_BEFORE(&cifun->shead, ip, qelem);
126	if (ip->type == IP_DEFLAB)
127		nlabs++;
128	if (ip->type == IP_NODE)
129		walkf(ip->ip_node, tcnt, 0); /* Count as saved */
130	if (cftnod)
131		cifun->retval = regno(cftnod);
132}
133
134/*
135 * Called to setup for inlining of a new function.
136 */
137void
138inline_start(struct symtab *sp)
139{
140	struct istat *is;
141
142	SDEBUG(("inline_start(\"%s\")\n", sp->sname));
143
144	if (isinlining)
145		cerror("already inlining function");
146
147	if ((is = findfun(sp)) != 0) {
148		if (!DLIST_ISEMPTY(&is->shead, qelem))
149			uerror("inline function already defined");
150	} else {
151		is = ialloc();
152		is->sp = sp;
153		SLIST_INSERT_FIRST(&ipole, is, link);
154		DLIST_INIT(&is->shead, qelem);
155	}
156	cifun = is;
157	nlabs = 0;
158	isinlining++;
159}
160
161/*
162 * End of an inline function. In C99 an inline function declared "extern"
163 * should also have external linkage and are therefore printed out.
164 *
165 * Gcc inline syntax is a mess, see matrix below on emitting functions:
166 *		    without extern
167 *	-std=		-	gnu89	gnu99
168 *	gcc 3.3.5:	ja	ja	ja
169 *	gcc 4.1.3:	ja	ja	ja
170 *	gcc 4.3.1	ja	ja	nej
171 *
172 *		     with extern
173 *	gcc 3.3.5:	nej	nej	nej
174 *	gcc 4.1.3:	nej	nej	nej
175 *	gcc 4.3.1	nej	nej	ja
176 *
177 * The attribute gnu_inline sets gnu89 behaviour.
178 * Since pcc mimics gcc 4.3.1 that is the behaviour we emulate.
179 */
180void
181inline_end()
182{
183	struct symtab *sp = cifun->sp;
184
185	SDEBUG(("inline_end()\n"));
186
187	if (sdebug)printip(&cifun->shead);
188	isinlining = 0;
189
190	if (sp->sclass != STATIC &&
191	    (attr_find(sp->sap, GCC_ATYP_GNU_INLINE) || xgnu89)) {
192		if (sp->sclass == EXTDEF)
193			sp->sclass = 0;
194		else
195			sp->sclass = EXTDEF;
196	}
197
198	if (sp->sclass == EXTDEF) {
199		cifun->flags |= REFD;
200		inline_prtout();
201	}
202}
203
204/*
205 * Called when an inline function is found, to be sure that it will
206 * be written out.
207 * The function may not be defined when inline_ref() is called.
208 */
209void
210inline_ref(struct symtab *sp)
211{
212	struct istat *w;
213
214	SDEBUG(("inline_ref(\"%s\")\n", sp->sname));
215	if (sp->sclass == SNULL)
216		return; /* only inline, no references */
217	if (isinlining) {
218		refnode(sp);
219	} else {
220		SLIST_FOREACH(w,&ipole, link) {
221			if (w->sp != sp)
222				continue;
223			w->flags |= REFD;
224			return;
225		}
226		/* function not yet defined, print out when found */
227		w = ialloc();
228		w->sp = sp;
229		w->flags |= REFD;
230		SLIST_INSERT_FIRST(&ipole, w, link);
231		DLIST_INIT(&w->shead, qelem);
232	}
233}
234
235static void
236puto(struct istat *w)
237{
238	struct interpass_prolog *ipp, *epp, *pp;
239	struct interpass *ip, *nip;
240	extern int crslab;
241	int lbloff = 0;
242
243	/* Copy the saved function and print it out */
244	ipp = 0; /* XXX data flow analysis */
245	DLIST_FOREACH(ip, &w->shead, qelem) {
246		switch (ip->type) {
247		case IP_EPILOG:
248		case IP_PROLOG:
249			if (ip->type == IP_PROLOG) {
250				ipp = (struct interpass_prolog *)ip;
251				/* fix label offsets */
252				lbloff = crslab - ipp->ip_lblnum;
253			} else {
254				epp = (struct interpass_prolog *)ip;
255				crslab += (epp->ip_lblnum - ipp->ip_lblnum);
256			}
257			pp = tmpalloc(sizeof(struct interpass_prolog));
258			memcpy(pp, ip, sizeof(struct interpass_prolog));
259			pp->ip_lblnum += lbloff;
260#ifdef PCC_DEBUG
261			if (ip->type == IP_EPILOG && crslab != pp->ip_lblnum)
262				cerror("puto: %d != %d", crslab, pp->ip_lblnum);
263#endif
264			pass2_compile((struct interpass *)pp);
265			break;
266
267		case IP_REF:
268			inline_ref((struct symtab *)ip->ip_name);
269			break;
270
271		default:
272			nip = tmpalloc(sizeof(struct interpass));
273			*nip = *ip;
274			if (nip->type == IP_NODE) {
275				NODE *p;
276
277				p = nip->ip_node = ccopy(nip->ip_node);
278				if (p->n_op == GOTO)
279					p->n_left->n_lval += lbloff;
280				else if (p->n_op == CBRANCH)
281					p->n_right->n_lval += lbloff;
282			} else if (nip->type == IP_DEFLAB)
283				nip->ip_lbl += lbloff;
284			pass2_compile(nip);
285			break;
286		}
287	}
288	w->flags |= WRITTEN;
289}
290
291/*
292 * printout functions that are referenced.
293 */
294void
295inline_prtout()
296{
297	struct istat *w;
298	int gotone = 0;
299
300	SLIST_FOREACH(w, &ipole, link) {
301		if ((w->flags & (REFD|WRITTEN)) == REFD &&
302		    !DLIST_ISEMPTY(&w->shead, qelem)) {
303			locctr(PROG, w->sp);
304			defloc(w->sp);
305			puto(w);
306			w->flags |= WRITTEN;
307			gotone++;
308		}
309	}
310	if (gotone)
311		inline_prtout();
312}
313
314#if 1
315static void
316printip(struct interpass *pole)
317{
318	static char *foo[] = {
319	   0, "NODE", "PROLOG", "STKOFF", "EPILOG", "DEFLAB", "DEFNAM", "ASM" };
320	struct interpass *ip;
321	struct interpass_prolog *ipplg, *epplg;
322
323	DLIST_FOREACH(ip, pole, qelem) {
324		if (ip->type > MAXIP)
325			printf("IP(%d) (%p): ", ip->type, ip);
326		else
327			printf("%s (%p): ", foo[ip->type], ip);
328		switch (ip->type) {
329		case IP_NODE: printf("\n");
330#ifdef PCC_DEBUG
331			fwalk(ip->ip_node, eprint, 0); break;
332#endif
333		case IP_PROLOG:
334			ipplg = (struct interpass_prolog *)ip;
335			printf("%s %s regs %lx autos %d mintemp %d minlbl %d\n",
336			    ipplg->ipp_name, ipplg->ipp_vis ? "(local)" : "",
337			    (long)ipplg->ipp_regs[0], ipplg->ipp_autos,
338			    ipplg->ip_tmpnum, ipplg->ip_lblnum);
339			break;
340		case IP_EPILOG:
341			epplg = (struct interpass_prolog *)ip;
342			printf("%s %s regs %lx autos %d mintemp %d minlbl %d\n",
343			    epplg->ipp_name, epplg->ipp_vis ? "(local)" : "",
344			    (long)epplg->ipp_regs[0], epplg->ipp_autos,
345			    epplg->ip_tmpnum, epplg->ip_lblnum);
346			break;
347		case IP_DEFLAB: printf(LABFMT "\n", ip->ip_lbl); break;
348		case IP_DEFNAM: printf("\n"); break;
349		case IP_ASM: printf("%s\n", ip->ip_asm); break;
350		default:
351			break;
352		}
353	}
354}
355#endif
356
357static int toff;
358
359static NODE *
360mnode(struct ntds *nt, NODE *p)
361{
362	NODE *q;
363	int num = nt->temp + toff;
364
365	if (p->n_op == CM) {
366		q = p->n_right;
367		q = tempnode(num, nt->type, nt->df, nt->attr);
368		nt--;
369		p->n_right = buildtree(ASSIGN, q, p->n_right);
370		p->n_left = mnode(nt, p->n_left);
371		p->n_op = COMOP;
372	} else {
373		p = pconvert(p);
374		q = tempnode(num, nt->type, nt->df, nt->attr);
375		p = buildtree(ASSIGN, q, p);
376	}
377	return p;
378}
379
380static void
381rtmps(NODE *p, void *arg)
382{
383	if (p->n_op == TEMP)
384		regno(p) += toff;
385}
386
387/*
388 * Inline a function. Returns the return value.
389 * There are two major things that must be converted when
390 * inlining a function:
391 * - Label numbers must be updated with an offset.
392 * - The stack block must be relocated (add to REG or OREG).
393 * - Temporaries should be updated (but no must)
394 */
395NODE *
396inlinetree(struct symtab *sp, NODE *f, NODE *ap)
397{
398	extern int crslab, tvaloff;
399	struct istat *is = findfun(sp);
400	struct interpass *ip, *ipf, *ipl;
401	int lmin, l0, l1, l2, gainl;
402	NODE *p, *rp;
403
404	if (is == NULL || nerrors) {
405		inline_ref(sp); /* prototype of not yet declared inline ftn */
406		return NIL;
407	}
408
409	SDEBUG(("inlinetree(%p,%p) OK %d\n", f, ap, is->flags & CANINL));
410
411	gainl = attr_find(sp->sap, GCC_ATYP_ALW_INL) != NULL;
412
413	if ((is->flags & CANINL) == 0 && gainl)
414		werror("cannot inline but always_inline");
415
416	if ((is->flags & CANINL) == 0 || (xinline == 0 && gainl == 0)) {
417		if (is->sp->sclass == STATIC || is->sp->sclass == USTATIC)
418			inline_ref(sp);
419		return NIL;
420	}
421
422	if (isinlining && cifun->sp == sp) {
423		/* Do not try to inline ourselves */
424		inline_ref(sp);
425		return NIL;
426	}
427
428#ifdef mach_i386
429	if (kflag) {
430		is->flags |= REFD; /* if static inline, emit */
431		return NIL; /* XXX cannot handle hidden ebx arg */
432	}
433#endif
434
435	/* emit jumps to surround inline function */
436	branch(l0 = getlab());
437	plabel(l1 = getlab());
438	l2 = getlab();
439	SDEBUG(("branch labels %d,%d,%d\n", l0, l1, l2));
440
441	ipf = DLIST_NEXT(&is->shead, qelem); /* prolog */
442	ipl = DLIST_PREV(&is->shead, qelem); /* epilog */
443
444	/* Fix label & temp offsets */
445#define	IPP(x) ((struct interpass_prolog *)x)
446	SDEBUG(("pre-offsets crslab %d tvaloff %d\n", crslab, tvaloff));
447	lmin = crslab - IPP(ipf)->ip_lblnum;
448	crslab += (IPP(ipl)->ip_lblnum - IPP(ipf)->ip_lblnum) + 1;
449	toff = tvaloff - IPP(ipf)->ip_tmpnum;
450	tvaloff += (IPP(ipl)->ip_tmpnum - IPP(ipf)->ip_tmpnum) + 1;
451	SDEBUG(("offsets crslab %d lmin %d tvaloff %d toff %d\n",
452	    crslab, lmin, tvaloff, toff));
453
454	/* traverse until first real label */
455	ipf = DLIST_NEXT(ipf, qelem);
456	do
457		ipf = DLIST_NEXT(ipf, qelem);
458	while (ipf->type != IP_DEFLAB);
459
460	/* traverse backwards to last label */
461	do
462		ipl = DLIST_PREV(ipl, qelem);
463	while (ipl->type != IP_DEFLAB);
464
465	/* So, walk over all statements and emit them */
466	for (ip = ipf; ip != ipl; ip = DLIST_NEXT(ip, qelem)) {
467		switch (ip->type) {
468		case IP_NODE:
469			p = ccopy(ip->ip_node);
470			if (p->n_op == GOTO)
471				p->n_left->n_lval += lmin;
472			else if (p->n_op == CBRANCH)
473				p->n_right->n_lval += lmin;
474			walkf(p, rtmps, 0);
475#ifdef PCC_DEBUG
476			if (sdebug) {
477				printf("converted node\n");
478				fwalk(ip->ip_node, eprint, 0);
479				fwalk(p, eprint, 0);
480			}
481#endif
482			send_passt(IP_NODE, p);
483			break;
484
485		case IP_DEFLAB:
486			SDEBUG(("converted label %d to %d\n",
487			    ip->ip_lbl, ip->ip_lbl + lmin));
488			send_passt(IP_DEFLAB, ip->ip_lbl + lmin);
489			break;
490
491		case IP_ASM:
492			send_passt(IP_ASM, ip->ip_asm);
493			break;
494
495		case IP_REF:
496			inline_ref((struct symtab *)ip->ip_name);
497			break;
498
499		default:
500			cerror("bad inline stmt %d", ip->type);
501		}
502	}
503	SDEBUG(("last label %d to %d\n", ip->ip_lbl, ip->ip_lbl + lmin));
504	send_passt(IP_DEFLAB, ip->ip_lbl + lmin);
505
506	branch(l2);
507	plabel(l0);
508
509	rp = block(GOTO, bcon(l1), NIL, INT, 0, 0);
510	if (is->retval)
511		p = tempnode(is->retval + toff, DECREF(sp->stype),
512		    sp->sdf, sp->sap);
513	else
514		p = bcon(0);
515	rp = buildtree(COMOP, rp, p);
516
517	if (is->nargs) {
518		p = mnode(&is->nt[is->nargs-1], ap);
519		rp = buildtree(COMOP, p, rp);
520	}
521
522	tfree(f);
523	return rp;
524}
525
526void
527inline_args(struct symtab **sp, int nargs)
528{
529	union arglist *al;
530	struct istat *cf;
531	TWORD t;
532	int i;
533
534	SDEBUG(("inline_args\n"));
535	cf = cifun;
536	/*
537	 * First handle arguments.  We currently do not inline anything if:
538	 * - function has varargs
539	 * - function args are volatile, checked if no temp node is asg'd.
540	 */
541	/* XXX - this is ugly, invent something better */
542	if (cf->sp->sdf->dfun == NULL)
543		return; /* no prototype */
544	for (al = cf->sp->sdf->dfun; al->type != TNULL; al++) {
545		t = al->type;
546		if (t == TELLIPSIS)
547			return; /* cannot inline */
548		if (ISSOU(BTYPE(t)))
549			al++;
550		for (; t > BTMASK; t = DECREF(t))
551			if (ISARY(t) || ISFTN(t))
552				al++;
553	}
554
555	if (nargs) {
556		for (i = 0; i < nargs; i++)
557			if ((sp[i]->sflags & STNODE) == 0)
558				return; /* not temporary */
559		cf->nt = permalloc(sizeof(struct ntds)*nargs);
560		for (i = 0; i < nargs; i++) {
561			cf->nt[i].temp = sp[i]->soffset;
562			cf->nt[i].type = sp[i]->stype;
563			cf->nt[i].df = sp[i]->sdf;
564			cf->nt[i].attr = sp[i]->sap;
565		}
566	}
567	cf->nargs = nargs;
568	cf->flags |= CANINL;
569}
570