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