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