optimize.c 2.89 KB
Newer Older
dcw's avatar
dcw committed
1 2 3
/* optimize.c */


4
#include <stdio.h>
5
#include <stdlib.h>
6
#include <stdbool.h>
dcw's avatar
dcw committed
7
#include <string.h>
8

dcw's avatar
dcw committed
9
#include "struct.h"
10
#include "optimize.h"
dcw's avatar
dcw committed
11 12


13 14
bool opt;		/* opt     == perform optimizations    */
bool verbose;		/* verbose == be verbose - diagnostics */
dcw's avatar
dcw committed
15 16


dcw's avatar
dcw committed
17
static void optimize_decln( decln );
18
static bool tail_optimize( decln );
dcw's avatar
dcw committed
19 20 21 22 23


#define implies( a, b ) (!(a) || (b))


Duncan White's avatar
Duncan White committed
24
void optimize( declnlist d )
dcw's avatar
dcw committed
25 26 27 28 29 30 31 32
{
	for( ; d != NULL; d = d->next )
	{
		if( opt )
		{
			optimize_decln( d );
		} else
		{
33 34
			d->ManyShapes = d->TagField = d->Struct = d->Union = true;
			d->UseNull = d->PutLoop = false;
dcw's avatar
dcw committed
35 36 37 38 39
		}
	}
}


Duncan White's avatar
Duncan White committed
40
static void optimize_decln( decln d )
dcw's avatar
dcw committed
41 42 43
{
	int		t, e, ne;
	shapelist	s;
44
	bool		firstempty = d->shapes->params == NULL;
dcw's avatar
dcw committed
45 46 47 48 49 50 51 52 53 54

	e = ne = 0;
	for( s = d->shapes; s != NULL; s = s->next )
	{
		if( s->params == NULL ) e++; else ne++;
	}

	t = e+ne;

/*
dcw's avatar
dcw committed
55 56 57 58 59
	ManyShapes when:	">1 shape"
	Struct when:		">0 chunks of data to be stored"
	TagField when:		">1 chunks or (>0 chunks && >2 shapes)"
	Union when:		">1 chunks of data to be stored"
	UseNull when:		"firstempty and some data elsewhere"
dcw's avatar
dcw committed
60
 */
dcw's avatar
dcw committed
61
	d->ManyShapes	= t>1;
dcw's avatar
dcw committed
62 63 64 65
	d->Struct	= ne>0;
	d->TagField	= ne>1 || ( ne>0 && t>2);
	d->Union	= ne>1;
	d->UseNull	= ne>0 && firstempty;
dcw's avatar
dcw committed
66 67

	d->PutLoop	= tail_optimize( d );
dcw's avatar
dcw committed
68 69 70 71

	if( verbose )
	{
#define XXX(x)	( (x)?' ':'!')
dcw's avatar
dcw committed
72 73
		printf( "type %s: %cManyShapes, %cTagField, ",
			d->name, XXX(d->ManyShapes),
dcw's avatar
dcw committed
74 75 76 77 78 79 80
			XXX(d->TagField) );
		printf( "%cStruct, %cUnion, %cUseNull\n",
			XXX(d->Struct), XXX(d->Union),
			XXX(d->UseNull) );
#undef XXX
	}

81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115
	if( ! implies(d->Union,d->Struct) )
	{
		fprintf( stderr,
			"optimizer error: type %s has Union&!Struct\n",
			d->name );
		exit(1);
	}
	if( ! implies(d->TagField,d->Struct) )
	{
		fprintf( stderr,
			"optimizer error: type %s has TagField&!Struct\n",
			d->name );
		exit(1);
	}
	if( ! implies(d->UseNull,d->Struct) )
	{
		fprintf( stderr,
			"optimizer error: type %s has UseNull&!Struct\n",
			d->name );
		exit(1);
	}
	if( ! implies(d->TagField,d->ManyShapes) )
	{
		fprintf( stderr,
			"optimizer error: type %s has TagField&!ManyShapes\n",
			d->name );
		exit(1);
	}
	if( ! implies(d->Union,d->TagField) )
	{
		fprintf( stderr,
			"optimizer error: type %s has Union&!TagField\n",
			d->name );
		exit(1);
	}
dcw's avatar
dcw committed
116
}
dcw's avatar
dcw committed
117 118 119 120 121 122 123


/*
	Given a data decln, check if a tail recursion optimization is possible.
	This is when the last print item of any shape is a number corresponding
	to a field that is the same type as the decln itself.

124
	Return true if the optimization is possible.
dcw's avatar
dcw committed
125 126
 */

127
static bool tail_optimize( decln d )
dcw's avatar
dcw committed
128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146
{
	shapelist	s;
	printlist	pl;
	param		p;

	for( s = d->shapes; s != NULL; s = s->next )
	{
		if( s->pl != NULL )
		{
			/* find the last print item */

			for( pl = s->pl; pl->next != NULL; pl = pl->next );

			if( pl->item->tag == printitem_is_num )
			{
				p = findnthparam( pl->item->num, s->params,
						  s->name, d->name );
				if( streq( p->type, d->name ) )
				{
147
					return true;
dcw's avatar
dcw committed
148 149 150 151
				}
			}
		}
	}
152
	return false;
dcw's avatar
dcw committed
153
}