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