scc

  1#include <assert.h>
  2#include <inttypes.h>
  3#include <stdlib.h>
  4#include <string.h>
  5
  6#include <scc/cstd.h>
  7#include <scc/scc.h>
  8#include "cc1.h"
  9
 10#define NR_TYPE_HASH 16
 11#define HASH(t) (((t)->op ^ (uintptr_t) (t)->type>>3) & NR_TYPE_HASH-1)
 12
 13static Type *typetab[NR_TYPE_HASH], *localtypes;
 14
 15/* FIXME:
 16 * Compiler can generate warnings here if the ranges of long long,
 17 * unsigned long long and double are smaller than any of the constants in this
 18 * array. Ignore them if you know that the target types are correct
 19 */
 20static struct limits limits[][4] = {
 21	{
 22		{	/* 0 = unsigned 1 byte */
 23			.min.i = 0,
 24			.max.i = 0xff
 25		},
 26		{	/* 1 = unsigned 2 bytes */
 27			.min.i = 0,
 28			.max.i = 0xffff
 29		},
 30		{	/* 2 = unsigned 4 bytes */
 31			.min.i = 0,
 32			.max.i = 0xffffffff
 33		},
 34		{	/* 3 = unsigned 8 bytes */
 35			.min.i = 0,
 36			.max.i = 0xffffffffffffffff
 37		}
 38	},
 39	{
 40		{	/* 0 = signed 1 byte */
 41			.min.i = -0x7f-1,
 42			.max.i = 0x7f
 43		},
 44		{	/* 1 = signed 2 byte */
 45			.min.i = -0x7fff-1,
 46			.max.i = 0x7fff
 47		},
 48		{	/* 2 = signed 4 byte */
 49			.min.i = -0x7fffffff-1,
 50			.max.i = 0x7fffffff
 51		},
 52		{	/* 3 = signed 8 byte */
 53			.min.i = -0x7fffffffffffffff-1,
 54			.max.i = 0x7fffffffffffffff,
 55		}
 56	},
 57	{
 58		{
 59			/* 0 = float 4 bytes */
 60			.min.f = -1,
 61			.max.f = 2
 62		},
 63		{
 64			/* 1 = float 8 bytes */
 65			.min.f = -1,
 66			.max.f = 2,
 67		},
 68		{
 69			/* 2 = float 16 bytes */
 70			.min.f = -1,
 71			.max.f = 2,
 72		}
 73	}
 74};
 75
 76struct limits *
 77getlimits(Type *tp)
 78{
 79	int ntable, ntype;
 80
 81	switch (tp->op) {
 82	case ENUM:
 83	case INT:
 84		ntable = ((tp->prop & TSIGNED) != 0);
 85		switch (tp->size) {
 86		case 1: ntype = 0; break;
 87		case 2: ntype = 1; break;
 88		case 4: ntype = 2; break;
 89		case 8: ntype = 3; break;
 90		}
 91		break;
 92	case FLOAT:
 93		ntable = 2;
 94		switch (tp->size) {
 95		case 4:  ntype = 0; break;
 96		case 8:  ntype = 1; break;
 97		case 16: ntype = 2; break;
 98		}
 99		break;
100	default:
101		abort();
102	}
103
104	return &limits[ntable][ntype];
105}
106
107Type *
108ctype(int type, int sign, int size)
109{
110	switch (type) {
111	case CHAR:
112		if (size)
113			goto invalid_type;
114		switch (sign) {
115		case 0:
116			return chartype;
117		case SIGNED:
118			return schartype;
119		case UNSIGNED:
120			return uchartype;
121		}
122		break;
123	case VA_LIST:
124		if (size || sign)
125			goto invalid_type;
126		return va_list_type;
127	case VOID:
128		if (size || sign)
129			goto invalid_type;
130		return voidtype;
131	case BOOL:
132		if (size || sign)
133			goto invalid_type;
134		return booltype;
135	case 0:
136	case INT:
137		switch (size) {
138		case 0:
139			return (sign == UNSIGNED) ? uinttype   : inttype;
140		case SHORT:
141			return (sign == UNSIGNED) ? ushorttype  : shorttype;
142		case LONG:
143			return (sign == UNSIGNED) ? ulongtype  : longtype;
144		case LLONG:
145			return (sign == UNSIGNED) ? ullongtype : llongtype;
146		}
147		break;
148	case DOUBLE:
149		if (size == LLONG)
150			goto invalid_type;
151		if (size == LONG)
152			size = LLONG;
153		else
154			size = LONG;
155		goto floating;
156	case FLOAT:
157		if (size == LLONG)
158			goto invalid_type;
159	floating:
160		if (sign)
161			goto invalid_type;
162		switch (size) {
163		case 0:
164			return floattype;
165		case LONG:
166			return doubletype;
167		case LLONG:
168			return ldoubletype;
169		}
170		break;
171	}
172
173invalid_type:
174	errorp("invalid type specification");
175	return inttype;
176}
177
178void
179typesize(Type *tp)
180{
181	Symbol **sp;
182	Type *type;
183	unsigned long size, offset;
184	int align, a;
185	long long n;
186
187	switch (tp->op) {
188	case ARY:
189		/* FIXME: Control overflow */
190		tp->size = tp->n.elem * tp->type->size;
191		tp->align = tp->type->align;
192		return;
193	case PTR:
194		tp->size = pvoidtype->size;
195		tp->align = pvoidtype->align;
196		return;
197	case STRUCT:
198	case UNION:
199		/* FIXME: Control overflow */
200		/*
201		 * The alignment of the struct/union is
202		 * the alignment of the largest included type.
203		 * The size of an union is the size of the largest
204		 * field, and the size of a struct is the sum
205		 * of the size of every field plus padding bits.
206		 */
207		offset = align = size = 0;
208		n = tp->n.elem;
209		for (sp = tp->p.fields; n--; ++sp) {
210			type = (*sp)->type;
211			a = type->align;
212			if (a > align)
213				align = a;
214			if (tp->op == STRUCT) {
215				if (--a != 0)
216					offset = (offset + a) & ~a;
217				(*sp)->u.i = offset;
218				size = offset + type->size;
219				offset = size;
220			} else {
221				(*sp)->u.i = 0;
222				if (type->size > size)
223					size = type->size;
224			}
225		}
226
227		tp->align = align;
228		/*
229		 * We have to add the padding bits to
230		 * ensure next struct in an array is well
231		 * alignment.
232		 */
233		if (tp->op == STRUCT && align-- > 1)
234			size = size+align & ~align;
235		tp->size = size;
236		return;
237	case ENUM:
238		tp->size = inttype->size;
239		tp->align = inttype->align;
240		return;
241	case FTN:
242		return;
243	default:
244		abort();
245	}
246}
247
248Type *
249deftype(Type *tp)
250{
251	tp->prop |= TDEFINED;
252	typesize(tp);
253	emit(OTYP, tp);
254	return tp;
255}
256
257static Type *
258newtype(Type *base)
259{
260	Type *tp, **pars;
261	size_t siz;
262
263	tp = xmalloc(sizeof(*tp));
264	*tp = *base;
265	tp->id = newid();
266
267	if (tp->op == FTN) {
268		siz = (tp->n.elem + 1) * sizeof(Type *);
269		pars = xmalloc(siz);
270		if (tp->n.elem > 0)
271			memcpy(pars, tp->p.pars, siz);
272		pars[tp->n.elem] = NULL;
273		tp->p.pars = pars;
274	} else if (tp->op == ARY) {
275		/* We need alignment for flexible array members */
276		tp->align = tp->type->align;
277	}
278
279	if (curfun) {
280		/* it is a type defined in the body of a function */
281		tp->next = localtypes;
282		localtypes = tp;
283	}
284	if (tp->prop & TDEFINED)
285		deftype(tp);
286	return tp;
287}
288
289Type *
290mktype(Type *tp, int op, long long nelem, Type *pars[])
291{
292	Type **tbl, type;
293	Type *bp;
294
295	if (op == PTR && tp == voidtype)
296		return pvoidtype;
297
298	type = (Type) {
299		.type = tp,
300		.op = op,
301		.p.pars = pars,
302		.n.elem = nelem,
303	};
304
305	switch (op) {
306	case ARY:
307		if (tp == voidtype) {
308			errorp("declaration of array of voids type");
309			tp = inttype;
310		}
311		type.letter = L_ARRAY;
312		if (nelem != 0)
313			type.prop |= TDEFINED;
314		break;
315	case KRFTN:
316		type.prop |= TDEFINED | TK_R;
317		type.op = FTN;
318		type.letter = L_FUNCTION;
319		break;
320	case FTN:
321		if (nelem > 0 && pars[nelem-1] == ellipsistype)
322			type.prop |= TELLIPSIS;
323		type.letter = L_FUNCTION;
324		type.prop |= TDEFINED;
325		break;
326	case PTR:
327	        type.letter = L_POINTER;
328		type.prop |= TDEFINED;
329		break;
330	case ENUM:
331		type.letter = inttype->letter;
332		type.prop |= TINTEGER | TARITH;
333		type.n.rank = inttype->n.rank;
334		goto create_type;
335	case STRUCT:
336		type.letter = L_STRUCT;
337		type.prop |= TAGGREG;
338		goto create_type;
339	case UNION:
340		type.letter = L_UNION;
341		type.prop |= TAGGREG;
342	create_type:
343		return newtype(&type);
344	default:
345		abort();
346	}
347
348	tbl = &typetab[HASH(&type)];
349	for (bp = *tbl; bp; bp = bp->h_next) {
350		if (eqtype(bp, &type, EQUAL))
351			return bp;
352	}
353
354	bp = newtype(&type);
355	bp->h_next = *tbl;
356	*tbl = bp;
357
358	return bp;
359}
360
361/*
362 * If one type has a parameter type list and the other type is specified by
363 * a function declarator that is not part of a function definition and that
364 * contains an empty identifier list, the parameter list shall not have an
365 * ellipsis terminator and the type of each parameter shall be compatible
366 * with the type that results from the application of the default argument
367 * promotions.
368 */
369static int
370eqfuns(Type *tp1, Type *tp2, int equiv)
371{
372	long long n;
373	int f1kr, f2kr;
374	Type *krf, *ansi, **pp, *p;
375
376	f1kr = (tp1->prop&TK_R) != 0;
377	f2kr = (tp2->prop&TK_R) != 0;
378
379	/* 1: 2 ansi functions */
380	if (!f1kr && !f2kr) {
381		Type **p1, **p2;
382		if (tp1->n.elem != tp2->n.elem)
383			return 0;
384		p1 = tp1->p.pars, p2 = tp2->p.pars;
385		for (n = tp1->n.elem; n > 0; --n) {
386			if (!eqtype(*p1++, *p2++, equiv))
387				return 0;
388		}
389		goto check_base;
390	}
391
392	/* 2: 2 k&r functions */
393	if (f1kr && f2kr)
394		goto check_base;
395
396	/* 3: 1 k&r function + 1 ansi function */
397	if (!equiv)
398		return 0;
399
400	if (f1kr) {
401		krf = tp1;
402		ansi = tp2;
403	} else {
404		ansi = tp1;
405		krf = tp2;
406	}
407
408	for (pp = ansi->p.pars; p = *pp; ++pp) {
409		switch (p->op) {
410		case ELLIPSIS:
411			return 0;
412		case INT:
413		case ENUM:
414			if (p->n.rank < inttype->n.rank)
415				return 0;
416			break;
417		case FLOAT:
418			if (p == floattype)
419				return 0;
420			break;
421		}
422	}
423
424check_base:
425	return eqtype(tp1->type, tp2->type, equiv);
426}
427
428int
429eqtype(Type *tp1, Type *tp2, int equiv)
430{
431	long long n;
432	Symbol **s1, **s2;
433
434	if (tp1 == tp2)
435		return 1;
436	if (!tp1 || !tp2)
437		return 0;
438	if (tp1->op != tp2->op)
439		return 0;
440
441	switch (tp1->op) {
442	case UNION:
443	case STRUCT:
444		if (tp1->letter != tp2->letter)
445			return 0;
446		if (tp1->tag->name || tp2->tag->name)
447			return tp1->tag == tp2->tag;
448		if (tp1->n.elem != tp2->n.elem)
449			return 0;
450		s1 = tp1->p.fields, s2 = tp2->p.fields;
451		for (n = tp1->n.elem; n > 0; --n, ++s1, ++s2) {
452			if (strcmp((*s1)->name, (*s2)->name))
453				return 0;
454			if (!eqtype((*s1)->type, (*s2)->type, equiv))
455				return 0;
456		}
457		return 1;
458	case FTN:
459		return eqfuns(tp1, tp2, equiv);
460	case ARY:
461		if (equiv && (tp1->n.elem == 0 || tp2->n.elem == 0))
462			goto check_base;
463		if (tp1->n.elem != tp2->n.elem)
464			return 0;
465	case PTR:
466	check_base:
467		return eqtype(tp1->type, tp2->type, equiv);
468	case VOID:
469	case ENUM:
470		return 0;
471	case INT:
472	case FLOAT:
473		return tp1->letter == tp2->letter;
474	default:
475		abort();
476	}
477}
478
479void
480flushtypes(void)
481{
482	Type *tp, *next, **h;
483
484	for (tp = localtypes; tp; tp = next) {
485		next = tp->next;
486		switch (tp->op) {
487		default:
488			/*
489			 * All the local types are linked after
490			 * global types, and since we are
491			 * unlinking them in the inverse order
492			 * we do know that tp is always the head
493			 * of the collision list
494			 */
495			h = &typetab[HASH(tp)];
496			assert(*h == tp);
497			*h = tp->h_next;
498		case STRUCT:
499		case UNION:
500		case ENUM:
501			free(tp);
502			break;
503		}
504	}
505	localtypes = NULL;
506}