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