stmt.c (17113B)
1 #include "c.h" 2 3 4 #define SWSIZE 512 5 6 #define den(i,j) ((j-buckets[i]+1.0)/(v[j]-v[buckets[i]]+1)) 7 8 struct code codehead = { Start }; 9 Code codelist = &codehead; 10 float density = 0.5; 11 Table stmtlabs; 12 13 static int foldcond(Tree e1, Tree e2); 14 static void caselabel(Swtch, long, int); 15 static void cmp(int, Symbol, long, int); 16 static Tree conditional(int); 17 static void dostmt(int, Swtch, int); 18 static int equal(Symbol, Symbol); 19 static void forstmt(int, Swtch, int); 20 static void ifstmt(int, int, Swtch, int); 21 static Symbol localaddr(Tree); 22 static void stmtlabel(void); 23 static void swstmt(int, int, int); 24 static void whilestmt(int, Swtch, int); 25 Code code(int kind) { 26 Code cp; 27 28 if (!reachable(kind)) 29 warning("unreachable code\n"); 30 31 NEW(cp, FUNC); 32 cp->kind = kind; 33 cp->prev = codelist; 34 cp->next = NULL; 35 codelist->next = cp; 36 codelist = cp; 37 return cp; 38 } 39 int reachable(int kind) { 40 Code cp; 41 42 if (kind > Start) { 43 Code cp; 44 for (cp = codelist; cp->kind < Label; ) 45 cp = cp->prev; 46 if (cp->kind == Jump || cp->kind == Switch) 47 return 0; 48 } 49 return 1; 50 } 51 void addlocal(Symbol p) { 52 if (!p->defined) { 53 code(Local)->u.var = p; 54 p->defined = 1; 55 p->scope = level; 56 } 57 } 58 void definept(Coordinate *p) { 59 Code cp = code(Defpoint); 60 61 cp->u.point.src = p ? *p : src; 62 cp->u.point.point = npoints; 63 if (ncalled > 0) { 64 int n = findcount(cp->u.point.src.file, 65 cp->u.point.src.x, cp->u.point.src.y); 66 if (n > 0) 67 refinc = (float)n/ncalled; 68 } 69 if (glevel > 2) locus(identifiers, &cp->u.point.src); 70 if (events.points && reachable(Gen)) 71 { 72 Tree e = NULL; 73 apply(events.points, &cp->u.point.src, &e); 74 if (e) 75 listnodes(e, 0, 0); 76 } 77 } 78 void statement(int loop, Swtch swp, int lev) { 79 float ref = refinc; 80 81 if (Aflag >= 2 && lev == 15) 82 warning("more than 15 levels of nested statements\n"); 83 switch (t) { 84 case IF: ifstmt(genlabel(2), loop, swp, lev + 1); 85 break; 86 case WHILE: whilestmt(genlabel(3), swp, lev + 1); break; 87 case DO: dostmt(genlabel(3), swp, lev + 1); expect(';'); 88 break; 89 90 case FOR: forstmt(genlabel(4), swp, lev + 1); 91 break; 92 case BREAK: walk(NULL, 0, 0); 93 definept(NULL); 94 if (swp && swp->lab > loop) 95 branch(swp->lab + 1); 96 else if (loop) 97 branch(loop + 2); 98 else 99 error("illegal break statement\n"); 100 t = gettok(); expect(';'); 101 break; 102 103 case CONTINUE: walk(NULL, 0, 0); 104 definept(NULL); 105 if (loop) 106 branch(loop + 1); 107 else 108 error("illegal continue statement\n"); 109 t = gettok(); expect(';'); 110 break; 111 112 case SWITCH: swstmt(loop, genlabel(2), lev + 1); 113 break; 114 case CASE: { 115 int lab = genlabel(1); 116 if (swp == NULL) 117 error("illegal case label\n"); 118 definelab(lab); 119 while (t == CASE) { 120 static char stop[] = { IF, ID, 0 }; 121 Tree p; 122 t = gettok(); 123 p = constexpr(0); 124 if (generic(p->op) == CNST && isint(p->type)) { 125 if (swp) { 126 needconst++; 127 p = cast(p, swp->sym->type); 128 if (p->type->op == UNSIGNED) 129 p->u.v.i = extend(p->u.v.u, p->type); 130 needconst--; 131 caselabel(swp, p->u.v.i, lab); 132 } 133 } else 134 error("case label must be a constant integer expression\n"); 135 136 test(':', stop); 137 } 138 statement(loop, swp, lev); 139 } break; 140 case DEFAULT: if (swp == NULL) 141 error("illegal default label\n"); 142 else if (swp->deflab) 143 error("extra default label\n"); 144 else { 145 swp->deflab = findlabel(swp->lab); 146 definelab(swp->deflab->u.l.label); 147 } 148 t = gettok(); 149 expect(':'); 150 statement(loop, swp, lev); break; 151 case RETURN: { 152 Type rty = freturn(cfunc->type); 153 t = gettok(); 154 definept(NULL); 155 if (t != ';') 156 if (rty == voidtype) { 157 error("extraneous return value\n"); 158 expr(0); 159 retcode(NULL); 160 } else 161 retcode(expr(0)); 162 else { 163 if (rty != voidtype) 164 warning("missing return value\n"); 165 retcode(NULL); 166 } 167 branch(cfunc->u.f.label); 168 } expect(';'); 169 break; 170 171 case '{': compound(loop, swp, lev + 1); break; 172 case ';': definept(NULL); t = gettok(); break; 173 case GOTO: walk(NULL, 0, 0); 174 definept(NULL); 175 t = gettok(); 176 if (t == ID) { 177 Symbol p = lookup(token, stmtlabs); 178 if (p == NULL) { 179 p = install(token, &stmtlabs, 0, FUNC); 180 p->scope = LABELS; 181 p->u.l.label = genlabel(1); 182 p->src = src; 183 } 184 use(p, src); 185 branch(p->u.l.label); 186 t = gettok(); 187 } else 188 error("missing label in goto\n"); expect(';'); 189 break; 190 191 case ID: if (getchr() == ':') { 192 stmtlabel(); 193 statement(loop, swp, lev); 194 break; 195 } 196 default: definept(NULL); 197 if (kind[t] != ID) { 198 error("unrecognized statement\n"); 199 t = gettok(); 200 } else { 201 Tree e = expr0(0); 202 listnodes(e, 0, 0); 203 if (nodecount == 0 || nodecount > 200) 204 walk(NULL, 0, 0); 205 else if (glevel) walk(NULL, 0, 0); 206 deallocate(STMT); 207 } expect(';'); 208 break; 209 210 } 211 if (kind[t] != IF && kind[t] != ID 212 && t != '}' && t != EOI) { 213 static char stop[] = { IF, ID, '}', 0 }; 214 error("illegal statement termination\n"); 215 skipto(0, stop); 216 } 217 refinc = ref; 218 } 219 220 static void ifstmt(int lab, int loop, Swtch swp, int lev) { 221 t = gettok(); 222 expect('('); 223 definept(NULL); 224 walk(conditional(')'), 0, lab); 225 refinc /= 2.0; 226 statement(loop, swp, lev); 227 if (t == ELSE) { 228 branch(lab + 1); 229 t = gettok(); 230 definelab(lab); 231 statement(loop, swp, lev); 232 if (findlabel(lab + 1)->ref) 233 definelab(lab + 1); 234 } else 235 definelab(lab); 236 } 237 static Tree conditional(int tok) { 238 Tree p = expr(tok); 239 240 if (Aflag > 1 && isfunc(p->type)) 241 warning("%s used in a conditional expression\n", 242 funcname(p)); 243 return cond(p); 244 } 245 static void stmtlabel(void) { 246 Symbol p = lookup(token, stmtlabs); 247 248 if (p == NULL) { 249 p = install(token, &stmtlabs, 0, FUNC); 250 p->scope = LABELS; 251 p->u.l.label = genlabel(1); 252 p->src = src; 253 } 254 if (p->defined) 255 error("redefinition of label `%s' previously defined at %w\n", p->name, &p->src); 256 257 p->defined = 1; 258 definelab(p->u.l.label); 259 t = gettok(); 260 expect(':'); 261 } 262 static void forstmt(int lab, Swtch swp, int lev) { 263 int once = 0; 264 Tree e1 = NULL, e2 = NULL, e3 = NULL; 265 Coordinate pt2, pt3; 266 267 t = gettok(); 268 expect('('); 269 definept(NULL); 270 if (kind[t] == ID) 271 e1 = texpr(expr0, ';', FUNC); 272 else 273 expect(';'); 274 walk(e1, 0, 0); 275 pt2 = src; 276 refinc *= 10.0; 277 if (kind[t] == ID) 278 e2 = texpr(conditional, ';', FUNC); 279 else 280 expect(';'); 281 pt3 = src; 282 if (kind[t] == ID) 283 e3 = texpr(expr0, ')', FUNC); 284 else { 285 static char stop[] = { IF, ID, '}', 0 }; 286 test(')', stop); 287 } 288 if (e2) { 289 once = foldcond(e1, e2); 290 if (!once) 291 branch(lab + 3); 292 } 293 definelab(lab); 294 statement(lab, swp, lev); 295 definelab(lab + 1); 296 definept(&pt3); 297 if (e3) 298 walk(e3, 0, 0); 299 if (e2) { 300 if (!once) 301 definelab(lab + 3); 302 definept(&pt2); 303 walk(e2, lab, 0); 304 } else { 305 definept(&pt2); 306 branch(lab); 307 } 308 if (findlabel(lab + 2)->ref) 309 definelab(lab + 2); 310 } 311 static void swstmt(int loop, int lab, int lev) { 312 Tree e; 313 struct swtch sw; 314 Code head, tail; 315 316 t = gettok(); 317 expect('('); 318 definept(NULL); 319 e = expr(')'); 320 if (!isint(e->type)) { 321 error("illegal type `%t' in switch expression\n", 322 e->type); 323 e = retype(e, inttype); 324 } 325 e = cast(e, promote(e->type)); 326 if (generic(e->op) == INDIR && isaddrop(e->kids[0]->op) 327 && e->kids[0]->u.sym->type == e->type 328 && !isvolatile(e->kids[0]->u.sym->type)) { 329 sw.sym = e->kids[0]->u.sym; 330 walk(NULL, 0, 0); 331 } else { 332 sw.sym = genident(REGISTER, e->type, level); 333 addlocal(sw.sym); 334 walk(asgn(sw.sym, e), 0, 0); 335 } 336 head = code(Switch); 337 sw.lab = lab; 338 sw.deflab = NULL; 339 sw.ncases = 0; 340 sw.size = SWSIZE; 341 sw.values = newarray(SWSIZE, sizeof *sw.values, FUNC); 342 sw.labels = newarray(SWSIZE, sizeof *sw.labels, FUNC); 343 refinc /= 10.0; 344 statement(loop, &sw, lev); 345 if (sw.deflab == NULL) { 346 sw.deflab = findlabel(lab); 347 definelab(lab); 348 if (sw.ncases == 0) 349 warning("switch statement with no cases\n"); 350 } 351 if (findlabel(lab + 1)->ref) 352 definelab(lab + 1); 353 tail = codelist; 354 codelist = head->prev; 355 codelist->next = head->prev = NULL; 356 if (sw.ncases > 0) 357 swgen(&sw); 358 branch(lab); 359 head->next->prev = codelist; 360 codelist->next = head->next; 361 codelist = tail; 362 } 363 static void caselabel(Swtch swp, long val, int lab) { 364 int k; 365 366 if (swp->ncases >= swp->size) 367 { 368 long *vals = swp->values; 369 Symbol *labs = swp->labels; 370 swp->size *= 2; 371 swp->values = newarray(swp->size, sizeof *swp->values, FUNC); 372 swp->labels = newarray(swp->size, sizeof *swp->labels, FUNC); 373 for (k = 0; k < swp->ncases; k++) { 374 swp->values[k] = vals[k]; 375 swp->labels[k] = labs[k]; 376 } 377 } 378 k = swp->ncases; 379 for ( ; k > 0 && swp->values[k-1] >= val; k--) { 380 swp->values[k] = swp->values[k-1]; 381 swp->labels[k] = swp->labels[k-1]; 382 } 383 if (k < swp->ncases && swp->values[k] == val) 384 error("duplicate case label `%d'\n", val); 385 swp->values[k] = val; 386 swp->labels[k] = findlabel(lab); 387 ++swp->ncases; 388 if (Aflag >= 2 && swp->ncases == 258) 389 warning("more than 257 cases in a switch\n"); 390 } 391 void swgen(Swtch swp) { 392 int *buckets, k, n; 393 long *v = swp->values; 394 395 buckets = newarray(swp->ncases + 1, 396 sizeof *buckets, FUNC); 397 for (n = k = 0; k < swp->ncases; k++, n++) { 398 buckets[n] = k; 399 while (n > 0 && den(n-1, k) >= density) 400 n--; 401 } 402 buckets[n] = swp->ncases; 403 swcode(swp, buckets, 0, n - 1); 404 } 405 void swcode(Swtch swp, int b[], int lb, int ub) { 406 int hilab, lolab, l, u, k = (lb + ub)/2; 407 long *v = swp->values; 408 409 if (k > lb && k < ub) { 410 lolab = genlabel(1); 411 hilab = genlabel(1); 412 } else if (k > lb) { 413 lolab = genlabel(1); 414 hilab = swp->deflab->u.l.label; 415 } else if (k < ub) { 416 lolab = swp->deflab->u.l.label; 417 hilab = genlabel(1); 418 } else 419 lolab = hilab = swp->deflab->u.l.label; 420 l = b[k]; 421 u = b[k+1] - 1; 422 if (u - l + 1 <= 3) 423 { 424 int i; 425 for (i = l; i <= u; i++) 426 cmp(EQ, swp->sym, v[i], swp->labels[i]->u.l.label); 427 if (k > lb && k < ub) 428 cmp(GT, swp->sym, v[u], hilab); 429 else if (k > lb) 430 cmp(GT, swp->sym, v[u], hilab); 431 else if (k < ub) 432 cmp(LT, swp->sym, v[l], lolab); 433 else 434 assert(lolab == hilab), 435 branch(lolab); 436 walk(NULL, 0, 0); 437 } 438 else { 439 Tree e; 440 Type ty = signedint(swp->sym->type); 441 Symbol table = genident(STATIC, 442 array(voidptype, u - l + 1, 0), GLOBAL); 443 (*IR->defsymbol)(table); 444 if (!isunsigned(swp->sym->type) || v[l] != 0) 445 cmp(LT, swp->sym, v[l], lolab); 446 cmp(GT, swp->sym, v[u], hilab); 447 e = (*optree['-'])(SUB, cast(idtree(swp->sym), ty), cnsttree(ty, v[l])); 448 if (e->type->size < unsignedptr->size) 449 e = cast(e, unsignedlong); 450 walk(tree(JUMP, voidtype, 451 rvalue((*optree['+'])(ADD, pointer(idtree(table)), e)), NULL), 452 0, 0); 453 code(Switch); 454 codelist->u.swtch.table = table; 455 codelist->u.swtch.sym = swp->sym; 456 codelist->u.swtch.deflab = swp->deflab; 457 codelist->u.swtch.size = u - l + 1; 458 codelist->u.swtch.values = &v[l]; 459 codelist->u.swtch.labels = &swp->labels[l]; 460 if (v[u] - v[l] + 1 >= 10000) 461 warning("switch generates a huge table\n"); 462 } 463 if (k > lb) { 464 assert(lolab != swp->deflab->u.l.label); 465 definelab(lolab); 466 swcode(swp, b, lb, k - 1); 467 } 468 if (k < ub) { 469 assert(hilab != swp->deflab->u.l.label); 470 definelab(hilab); 471 swcode(swp, b, k + 1, ub); 472 } 473 } 474 static void cmp(int op, Symbol p, long n, int lab) { 475 Type ty = signedint(p->type); 476 477 listnodes(eqtree(op, 478 cast(idtree(p), ty), 479 cnsttree(ty, n)), 480 lab, 0); 481 } 482 void retcode(Tree p) { 483 Type ty; 484 485 if (p == NULL) { 486 if (events.returns) 487 apply(events.returns, cfunc, NULL); 488 return; 489 } 490 p = pointer(p); 491 ty = assign(freturn(cfunc->type), p); 492 if (ty == NULL) { 493 error("illegal return type; found `%t' expected `%t'\n", 494 p->type, freturn(cfunc->type)); 495 return; 496 } 497 p = cast(p, ty); 498 if (retv) 499 { 500 if (iscallb(p)) 501 p = tree(RIGHT, p->type, 502 tree(CALL+B, p->type, 503 p->kids[0]->kids[0], idtree(retv)), 504 rvalue(idtree(retv))); 505 else 506 p = asgntree(ASGN, rvalue(idtree(retv)), p); 507 walk(p, 0, 0); 508 if (events.returns) 509 apply(events.returns, cfunc, rvalue(idtree(retv))); 510 return; 511 } 512 if (events.returns) 513 { 514 Symbol t1 = genident(AUTO, p->type, level); 515 addlocal(t1); 516 walk(asgn(t1, p), 0, 0); 517 apply(events.returns, cfunc, idtree(t1)); 518 p = idtree(t1); 519 } 520 if (!isfloat(p->type)) 521 p = cast(p, promote(p->type)); 522 if (isptr(p->type)) 523 { 524 Symbol q = localaddr(p); 525 if (q && (q->computed || q->generated)) 526 warning("pointer to a %s is an illegal return value\n", 527 q->scope == PARAM ? "parameter" : "local"); 528 else if (q) 529 warning("pointer to %s `%s' is an illegal return value\n", 530 q->scope == PARAM ? "parameter" : "local", q->name); 531 } 532 walk(tree(mkop(RET,p->type), p->type, p, NULL), 0, 0); 533 } 534 void definelab(int lab) { 535 Code cp; 536 Symbol p = findlabel(lab); 537 538 assert(lab); 539 walk(NULL, 0, 0); 540 code(Label)->u.forest = newnode(LABEL+V, NULL, NULL, p); 541 for (cp = codelist->prev; cp->kind <= Label; ) 542 cp = cp->prev; 543 while ( cp->kind == Jump 544 && cp->u.forest->kids[0] 545 && specific(cp->u.forest->kids[0]->op) == ADDRG+P 546 && cp->u.forest->kids[0]->syms[0] == p) { 547 assert(cp->u.forest->kids[0]->syms[0]->u.l.label == lab); 548 p->ref--; 549 assert(cp->next); 550 assert(cp->prev); 551 cp->prev->next = cp->next; 552 cp->next->prev = cp->prev; 553 cp = cp->prev; 554 while (cp->kind <= Label) 555 cp = cp->prev; 556 } 557 } 558 Node jump(int lab) { 559 Symbol p = findlabel(lab); 560 561 p->ref++; 562 return newnode(JUMP+V, newnode(ADDRG+ttob(voidptype), NULL, NULL, p), 563 NULL, NULL); 564 } 565 void branch(int lab) { 566 Code cp; 567 Symbol p = findlabel(lab); 568 569 assert(lab); 570 walk(NULL, 0, 0); 571 code(Label)->u.forest = jump(lab); 572 for (cp = codelist->prev; cp->kind < Label; ) 573 cp = cp->prev; 574 while ( cp->kind == Label 575 && cp->u.forest->op == LABEL+V 576 && !equal(cp->u.forest->syms[0], p)) { 577 equatelab(cp->u.forest->syms[0], p); 578 assert(cp->next); 579 assert(cp->prev); 580 cp->prev->next = cp->next; 581 cp->next->prev = cp->prev; 582 cp = cp->prev; 583 while (cp->kind < Label) 584 cp = cp->prev; 585 } 586 if (cp->kind == Jump || cp->kind == Switch) { 587 p->ref--; 588 codelist->prev->next = NULL; 589 codelist = codelist->prev; 590 } else { 591 codelist->kind = Jump; 592 if (cp->kind == Label 593 && cp->u.forest->op == LABEL+V 594 && equal(cp->u.forest->syms[0], p)) 595 warning("source code specifies an infinite loop"); 596 } 597 } 598 void equatelab(Symbol old, Symbol new) { 599 assert(old->u.l.equatedto == NULL); 600 old->u.l.equatedto = new; 601 new->ref++; 602 } 603 static int equal(Symbol lprime, Symbol dst) { 604 assert(dst && lprime); 605 for ( ; dst; dst = dst->u.l.equatedto) 606 if (lprime == dst) 607 return 1; 608 return 0; 609 } 610 /* dostmt - do statement while ( expression ) */ 611 static void dostmt(int lab, Swtch swp, int lev) { 612 refinc *= 10.0; 613 t = gettok(); 614 definelab(lab); 615 statement(lab, swp, lev); 616 definelab(lab + 1); 617 expect(WHILE); 618 expect('('); 619 definept(NULL); 620 walk(conditional(')'), lab, 0); 621 if (findlabel(lab + 2)->ref) 622 definelab(lab + 2); 623 } 624 625 /* foldcond - check if initial test in for(e1;e2;e3) S is necessary */ 626 static int foldcond(Tree e1, Tree e2) { 627 int op = generic(e2->op); 628 Symbol v; 629 630 if (e1 == 0 || e2 == 0) 631 return 0; 632 if (generic(e1->op) == ASGN && isaddrop(e1->kids[0]->op) 633 && generic(e1->kids[1]->op) == CNST) { 634 v = e1->kids[0]->u.sym; 635 e1 = e1->kids[1]; 636 } else 637 return 0; 638 if ((op==LE || op==LT || op==EQ || op==NE || op==GT || op==GE) 639 && generic(e2->kids[0]->op) == INDIR 640 && e2->kids[0]->kids[0]->u.sym == v 641 && e2->kids[1]->op == e1->op) { 642 e1 = simplify(op, e2->type, e1, e2->kids[1]); 643 if (e1->op == CNST+I) 644 return e1->u.v.i; 645 } 646 return 0; 647 } 648 649 /* localaddr - returns q if p yields the address of local/parameter q; otherwise returns 0 */ 650 static Symbol localaddr(Tree p) { 651 if (p == NULL) 652 return NULL; 653 switch (generic(p->op)) { 654 case INDIR: case CALL: case ARG: 655 return NULL; 656 case ADDRL: case ADDRF: 657 return p->u.sym; 658 case RIGHT: case ASGN: 659 if (p->kids[1]) 660 return localaddr(p->kids[1]); 661 return localaddr(p->kids[0]); 662 case COND: { 663 Symbol q; 664 assert(p->kids[1] && p->kids[1]->op == RIGHT); 665 if ((q = localaddr(p->kids[1]->kids[0])) != NULL) 666 return q; 667 return localaddr(p->kids[1]->kids[1]); 668 } 669 default: { 670 Symbol q; 671 if (p->kids[0] && (q = localaddr(p->kids[0])) != NULL) 672 return q; 673 return localaddr(p->kids[1]); 674 } 675 } 676 } 677 678 /* whilestmt - while ( expression ) statement */ 679 static void whilestmt(int lab, Swtch swp, int lev) { 680 Coordinate pt; 681 Tree e; 682 683 refinc *= 10.0; 684 t = gettok(); 685 expect('('); 686 walk(NULL, 0, 0); 687 pt = src; 688 e = texpr(conditional, ')', FUNC); 689 branch(lab + 1); 690 definelab(lab); 691 statement(lab, swp, lev); 692 definelab(lab + 1); 693 definept(&pt); 694 walk(e, lab, 0); 695 if (findlabel(lab + 2)->ref) 696 definelab(lab + 2); 697 }