xref: /illumos-gate/usr/src/cmd/sgs/yacc/common/y4.c (revision 1a90c98d7539778aeb0a1d20f735b66aaba17fca)
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 /*
22  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
23  * Use is subject to license terms.
24  */
25 
26 /* Copyright (c) 1988 AT&T */
27 /* All Rights Reserved */
28 
29 #include "dextern.h"
30 #define	NOMORE -1000
31 
32 static void gin(int);
33 static void stin(int);
34 static void osummary(void);
35 static void aoutput(void);
36 static void arout(wchar_t *, int *, int);
37 static int nxti(void);
38 static int gtnm(void);
39 
40 static int *ggreed;
41 static int *pgo;
42 static int *yypgo;
43 
44 static int maxspr = 0;  /* maximum spread of any entry */
45 static int maxoff = 0;  /* maximum offset into an array */
46 int *optimmem;
47 static int *maxa;
48 
49 static int nxdb = 0;
50 static int adb = 0;
51 
52 void
callopt(void)53 callopt(void)
54 {
55 	int i, *p, j, k, *q;
56 
57 	ggreed = (int *) malloc(sizeof (int) * size);
58 	pgo = (int *) malloc(sizeof (int) * size);
59 	yypgo = &nontrst[0].tvalue;
60 
61 	/* read the arrays from tempfile and set parameters */
62 
63 	if ((finput = fopen(TEMPNAME, "r")) == NULL)
64 /*
65  * TRANSLATION_NOTE  -- This is a message from yacc.
66  *	This message is passed to error() function.
67  *	tempfile can be translated as temporary file.
68  */
69 		error(gettext(
70 		    "optimizer cannot open tempfile"));
71 
72 	optimmem = tracemem;
73 	pgo[0] = 0;
74 	temp1[0] = 0;
75 	nstate = 0;
76 	nnonter = 0;
77 	for (;;) {
78 		switch (gtnm()) {
79 
80 		case L'\n':
81 			temp1[++nstate] = (--optimmem) - tracemem;
82 			/* FALLTHRU */
83 
84 		case L',':
85 			continue;
86 
87 		case L'$':
88 			break;
89 
90 		default:
91 			error("bad tempfile");
92 		}
93 		break;
94 	}
95 
96 	temp1[nstate] = yypgo[0] = (--optimmem) - tracemem;
97 
98 	for (;;) {
99 		switch (gtnm()) {
100 
101 		case L'\n':
102 			yypgo[++nnonter] = optimmem-tracemem;
103 			/* FALLTHRU */
104 		case L',':
105 			continue;
106 
107 		case EOF:
108 			break;
109 
110 		default:
111 /*
112  * TRANSLATION_NOTE  -- This is a message from yacc.
113  *	This message is passed to error() function.
114  *	tempfile can be translated as 'temporary file'.
115  */
116 			error(gettext(
117 			"bad tempfile"));
118 		}
119 		break;
120 	}
121 
122 	yypgo[nnonter--] = (--optimmem) - tracemem;
123 
124 	for (i = 0; i < nstate; ++i) {
125 		k = 32000000;
126 		j = 0;
127 		q = tracemem + temp1[i+1];
128 		for (p = tracemem + temp1[i]; p < q; p += 2) {
129 			if (*p > j)
130 				j = *p;
131 			if (*p < k)
132 				k = *p;
133 		}
134 		if (k <= j) {
135 			/*
136 			 * nontrivial situation
137 			 * temporarily, kill this for compatibility
138 			 */
139 			/* j -= k;  j is now the range */
140 			if (k > maxoff)
141 				maxoff = k;
142 		}
143 		tystate[i] = (temp1[i+1] - temp1[i]) + 2*j;
144 		if (j > maxspr)
145 			maxspr = j;
146 	}
147 
148 	/* initialize ggreed table */
149 	for (i = 1; i <= nnonter; ++i) {
150 		ggreed[i] = 1;
151 		j = 0;
152 		/* minimum entry index is always 0 */
153 		q = tracemem + yypgo[i+1] -1;
154 		for (p = tracemem + yypgo[i]; p < q; p += 2) {
155 			ggreed[i] += 2;
156 			if (*p > j)
157 				j = *p;
158 		}
159 		ggreed[i] = ggreed[i] + 2*j;
160 		if (j > maxoff)
161 			maxoff = j;
162 	}
163 
164 	/* now, prepare to put the shift actions into the amem array */
165 	for (i = 0; i < new_actsize; ++i)
166 		amem[i] = 0;
167 	maxa = amem;
168 
169 	for (i = 0; i < nstate; ++i) {
170 		if (tystate[i] == 0 && adb > 1)
171 			(void) fprintf(ftable, "State %d: null\n", i);
172 		indgo[i] = YYFLAG1;
173 	}
174 
175 	while ((i = nxti()) != NOMORE) {
176 		if (i >= 0)
177 			stin(i);
178 		else
179 			gin(-i);
180 	}
181 
182 	if (adb > 2) { /* print a array */
183 		for (p = amem; p <= maxa; p += 10) {
184 			(void) fprintf(ftable, "%4" PRIdPTR "  ", p-amem);
185 			for (i = 0; i < 10; ++i)
186 				(void) fprintf(ftable, "%4d  ", p[i]);
187 			(void) fprintf(ftable, "\n");
188 		}
189 	}
190 	/* write out the output appropriate to the language */
191 	aoutput();
192 	osummary();
193 	ZAPFILE(TEMPNAME);
194 }
195 
196 static void
gin(int i)197 gin(int i)
198 {
199 	int *r, *s, *q1, *q2;
200 	int *p;
201 
202 	/* enter gotos on nonterminal i into array amem */
203 	ggreed[i] = 0;
204 
205 	q2 = tracemem + yypgo[i+1] - 1;
206 	q1 = tracemem + yypgo[i];
207 
208 	/* now, find a place for it */
209 
210 	/* for( p=amem; p < &amem[new_actsize]; ++p ){ */
211 	p = amem;
212 	for (;;) {
213 		while (p >= &amem[new_actsize])
214 			exp_act(&p);
215 		if (*p)
216 			goto nextgp;
217 		for (r = q1; r < q2; r += 2) {
218 			s = p + *r + 1;
219 			/*
220 			 * Check if action table needs to
221 			 * be expanded or not. If so,
222 			 * expand it.
223 			 */
224 			while (s >= &amem[new_actsize]) {
225 				exp_act(&p);
226 				s = p + *r + 1;
227 			}
228 			if (*s)
229 				goto nextgp;
230 			if (s > maxa) {
231 				while ((maxa = s) >= &amem[new_actsize])
232 					/* error( "amem array overflow" ); */
233 					exp_act(&p);
234 			}
235 		}
236 		/* we have found a spot */
237 		*p = *q2;
238 		if (p > maxa) {
239 			while ((maxa = p) >= &amem[new_actsize])
240 				/* error("amem array overflow"); */
241 				exp_act(&p);
242 		}
243 		for (r = q1; r < q2; r += 2) {
244 			s = p + *r + 1;
245 			/*
246 			 * Check if action table needs to
247 			 * be expanded or not. If so,
248 			 * expand it.
249 			 */
250 			while (s >= &amem[new_actsize]) {
251 				exp_act(&p);
252 				s = p + *r + 1;
253 			}
254 			*s = r[1];
255 		}
256 
257 		pgo[i] = p - amem;
258 		if (adb > 1)
259 			(void) fprintf(ftable,
260 			    "Nonterminal %d, entry at %d\n", i, pgo[i]);
261 		goto nextgi;
262 
263 		nextgp:
264 			++p;
265 	}
266 	/* error( "cannot place goto %d\n", i ); */
267 	nextgi:;
268 }
269 
270 static void
stin(int i)271 stin(int i)
272 {
273 	int *r, n, nn, flag, j, *q1, *q2;
274 	int *s;
275 
276 	tystate[i] = 0;
277 
278 	/* Enter state i into the amem array */
279 
280 	q2 = tracemem + temp1[i + 1];
281 	q1 = tracemem + temp1[i];
282 	/* Find an acceptable place */
283 
284 	nn = -maxoff;
285 	more:
286 	for (n = nn; n < new_actsize; ++n) {
287 		flag = 0;
288 		for (r = q1; r < q2; r += 2) {
289 			s = *r + n + amem;
290 			if (s < amem)
291 				goto nextn;
292 			/*
293 			 * Check if action table needs to
294 			 * be expanded or not. If so,
295 			 * expand it.
296 			 */
297 			while (s >= &amem[new_actsize]) {
298 				exp_act((int **)NULL);
299 				s = *r + n + amem;
300 			}
301 			if (*s == 0)
302 				++flag;
303 			else if (*s != r[1])
304 				goto nextn;
305 		}
306 
307 		/*
308 		 * check that the position equals another
309 		 * only if the states are identical
310 		 */
311 		for (j = 0; j < nstate; ++j) {
312 			if (indgo[j] == n) {
313 				if (flag)
314 					/*
315 					 * we have some disagreement.
316 					 */
317 					goto nextn;
318 				if (temp1[j+1] + temp1[i] ==
319 				    temp1[j] + temp1[i+1]) {
320 					/* states are equal */
321 					indgo[i] = n;
322 					if (adb > 1)
323 						(void) fprintf(ftable,
324 						    "State %d: entry at"
325 						    " %d equals state %d\n",
326 						    i, n, j);
327 					return;
328 				}
329 				goto nextn;  /* we have some disagreement */
330 			}
331 		}
332 
333 		for (r = q1; r < q2; r += 2) {
334 			while ((s = *r + n + amem) >= &amem[new_actsize]) {
335 				/*
336 				 * error( "out of space");
337 				 */
338 				exp_act((int **)NULL);
339 			}
340 			if (s > maxa)
341 				maxa = s;
342 			if (*s != 0 && *s != r[1])
343 /*
344  * TRANSLATION_NOTE  -- This is a message from yacc.
345  *	This message is passed to error() function.
346  *	Leave this untrasnlated. Yacc internal error.
347  */
348 				error(gettext(
349 				    "clobber of amem array, pos'n %d, by %d"),
350 				    s-amem, r[1]);
351 			*s = r[1];
352 		}
353 		indgo[i] = n;
354 		if (adb > 1)
355 			(void) fprintf(ftable,
356 			    "State %d: entry at %d\n", i, indgo[i]);
357 		return;
358 		nextn:;
359 	}
360 
361 	/* error( "Error; failure to place state %d\n", i ); */
362 	exp_act((int **)NULL);
363 	nn = new_actsize - ACTSIZE;
364 	goto more;
365 	/* NOTREACHED */
366 }
367 
368 static int
nxti(void)369 nxti(void)
370 {
371 	/* finds the next i */
372 	int i, max, maxi;
373 	max = 0;
374 
375 	for (i = 1; i <= nnonter; ++i)
376 		if (ggreed[i] >= max) {
377 		max = ggreed[i];
378 		maxi = -i;
379 		}
380 
381 	for (i = 0; i < nstate; ++i)
382 		if (tystate[i] >= max) {
383 			max = tystate[i];
384 			maxi = i;
385 		}
386 	if (nxdb)
387 		(void) fprintf(ftable, "nxti = %d, max = %d\n", maxi, max);
388 	if (max == 0)
389 		return (NOMORE);
390 	else
391 		return (maxi);
392 }
393 
394 static void
osummary(void)395 osummary(void)
396 {
397 	/* write summary */
398 	int i, *p;
399 
400 	if (foutput == NULL)
401 		return;
402 	i = 0;
403 	for (p = maxa; p >= amem; --p) {
404 		if (*p == 0)
405 			++i;
406 	}
407 
408 	(void) fprintf(foutput,
409 	    "Optimizer space used: input %" PRIdPTR
410 	    "/%d, output %" PRIdPTR "/%d\n",
411 	    optimmem-tracemem + 1, new_memsize, maxa-amem + 1, new_actsize);
412 	(void) fprintf(foutput,
413 	    "%" PRIdPTR " table entries, %d zero\n", (maxa-amem) + 1, i);
414 	(void) fprintf(foutput,
415 	    "maximum spread: %d, maximum offset: %d\n", maxspr, maxoff);
416 
417 }
418 
419 static void
aoutput(void)420 aoutput(void)
421 {
422 	/* this version is for C */
423 	/* write out the optimized parser */
424 
425 	(void) fprintf(ftable, "# define YYLAST %" PRIdPTR "\n", maxa-amem + 1);
426 	arout(L"yyact", amem, (maxa - amem) + 1);
427 	arout(L"yypact", indgo, nstate);
428 	arout(L"yypgo", pgo, nnonter + 1);
429 }
430 
431 static void
arout(wchar_t * s,int * v,int n)432 arout(wchar_t *s, int *v, int n)
433 {
434 	int i;
435 
436 	(void) fprintf(ftable, "static const yytabelem %ws[]={\n", s);
437 	for (i = 0; i < n; ) {
438 		if (i % 10 == 0)
439 			(void) fprintf(ftable, "\n");
440 		(void) fprintf(ftable, "%6d", v[i]);
441 		if (++i == n)
442 			(void) fprintf(ftable, " };\n");
443 		else
444 			(void) fprintf(ftable, ",");
445 	}
446 }
447 
448 static int
gtnm(void)449 gtnm(void)
450 {
451 	int s, val, c;
452 
453 	/* read and convert an integer from the standard input */
454 	/* return the terminating character */
455 	/* blanks, tabs, and newlines are ignored */
456 
457 	s = 1;
458 	val = 0;
459 
460 	while ((c = getwc(finput)) != EOF) {
461 		if (iswdigit(c))
462 			val = val * 10 + c - L'0';
463 		else if (c == L'-')
464 			s = -1;
465 		else
466 			break;
467 	}
468 	*optimmem++ = s*val;
469 	if (optimmem >= &tracemem[new_memsize])
470 		exp_mem(0);
471 	return (c);
472 }
473 
474 void
exp_act(int ** ptr)475 exp_act(int **ptr)
476 {
477 	static int *actbase;
478 	int i;
479 	new_actsize += ACTSIZE;
480 
481 	actbase = amem;
482 	amem = (int *) realloc((char *)amem, sizeof (int) * new_actsize);
483 	if (amem == NULL)
484 /*
485  * TRANSLATION_NOTE  -- This is a message from yacc.
486  *	This message is passed to error() function.
487  *
488  *	You may just translate this as:
489  *	'Could not allocate internally used memory.'
490  */
491 		error(gettext(
492 		"couldn't expand action table"));
493 
494 	for (i = new_actsize-ACTSIZE; i < new_actsize; ++i)
495 		amem[i] = 0;
496 	if (ptr != NULL)
497 		*ptr = *ptr - actbase + amem;
498 	if (memp >= amem)
499 		memp = memp - actbase + amem;
500 	if (maxa >= amem)
501 		maxa = maxa - actbase + amem;
502 }
503