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 YYCONST 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