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 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 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 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 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 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 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 432 arout(wchar_t *s, int *v, int n) 433 { 434 int i; 435 436 (void) fprintf(ftable, WSFMT("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 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 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