1 /* 2 * Linearize - walk the statement tree (but _not_ the expressions) 3 * to generate a linear version of it and the basic blocks. 4 * 5 * NOTE! We're not interested in the actual sub-expressions yet, 6 * even though they can generate conditional branches and 7 * subroutine calls. That's all "local" behaviour. 8 * 9 * Copyright (C) 2004 Linus Torvalds 10 * Copyright (C) 2004 Christopher Li 11 */ 12 13 #include <string.h> 14 #include <stdarg.h> 15 #include <stdlib.h> 16 #include <stdio.h> 17 #include <assert.h> 18 19 #include "parse.h" 20 #include "expression.h" 21 #include "linearize.h" 22 #include "flow.h" 23 #include "target.h" 24 25 pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt); 26 pseudo_t linearize_expression(struct entrypoint *ep, struct expression *expr); 27 28 static pseudo_t add_binary_op(struct entrypoint *ep, struct symbol *ctype, int op, pseudo_t left, pseudo_t right); 29 static pseudo_t add_setval(struct entrypoint *ep, struct symbol *ctype, struct expression *val); 30 static pseudo_t linearize_one_symbol(struct entrypoint *ep, struct symbol *sym); 31 32 struct access_data; 33 static pseudo_t add_load(struct entrypoint *ep, struct access_data *); 34 static pseudo_t linearize_initializer(struct entrypoint *ep, struct expression *initializer, struct access_data *); 35 static pseudo_t cast_pseudo(struct entrypoint *ep, pseudo_t src, struct symbol *from, struct symbol *to); 36 37 struct pseudo void_pseudo = {}; 38 39 static struct position current_pos; 40 41 ALLOCATOR(pseudo_user, "pseudo_user"); 42 43 static struct instruction *alloc_instruction(int opcode, int size) 44 { 45 struct instruction * insn = __alloc_instruction(0); 46 insn->opcode = opcode; 47 insn->size = size; 48 insn->pos = current_pos; 49 return insn; 50 } 51 52 static inline int type_size(struct symbol *type) 53 { 54 return type ? type->bit_size > 0 ? type->bit_size : 0 : 0; 55 } 56 57 static struct instruction *alloc_typed_instruction(int opcode, struct symbol *type) 58 { 59 struct instruction *insn = alloc_instruction(opcode, type_size(type)); 60 insn->type = type; 61 return insn; 62 } 63 64 static struct entrypoint *alloc_entrypoint(void) 65 { 66 return __alloc_entrypoint(0); 67 } 68 69 static struct basic_block *alloc_basic_block(struct entrypoint *ep, struct position pos) 70 { 71 static int nr; 72 struct basic_block *bb = __alloc_basic_block(0); 73 bb->context = -1; 74 bb->pos = pos; 75 bb->ep = ep; 76 bb->nr = nr++; 77 return bb; 78 } 79 80 static struct multijmp *alloc_multijmp(struct basic_block *target, int begin, int end) 81 { 82 struct multijmp *multijmp = __alloc_multijmp(0); 83 multijmp->target = target; 84 multijmp->begin = begin; 85 multijmp->end = end; 86 return multijmp; 87 } 88 89 static inline int regno(pseudo_t n) 90 { 91 int retval = -1; 92 if (n && n->type == PSEUDO_REG) 93 retval = n->nr; 94 return retval; 95 } 96 97 const char *show_pseudo(pseudo_t pseudo) 98 { 99 static int n; 100 static char buffer[4][64]; 101 char *buf; 102 int i; 103 104 if (!pseudo) 105 return "no pseudo"; 106 if (pseudo == VOID) 107 return "VOID"; 108 buf = buffer[3 & ++n]; 109 switch(pseudo->type) { 110 case PSEUDO_SYM: { 111 struct symbol *sym = pseudo->sym; 112 struct expression *expr; 113 114 if (sym->bb_target) { 115 snprintf(buf, 64, ".L%u", sym->bb_target->nr); 116 break; 117 } 118 if (sym->ident) { 119 snprintf(buf, 64, "%s", show_ident(sym->ident)); 120 break; 121 } 122 expr = sym->initializer; 123 snprintf(buf, 64, "<anon symbol:%p>", sym); 124 if (expr) { 125 switch (expr->type) { 126 case EXPR_VALUE: 127 snprintf(buf, 64, "<symbol value: %lld>", expr->value); 128 break; 129 case EXPR_STRING: 130 return show_string(expr->string); 131 default: 132 break; 133 } 134 } 135 break; 136 } 137 case PSEUDO_REG: 138 i = snprintf(buf, 64, "%%r%d", pseudo->nr); 139 if (pseudo->ident) 140 sprintf(buf+i, "(%s)", show_ident(pseudo->ident)); 141 break; 142 case PSEUDO_VAL: { 143 long long value = pseudo->value; 144 if (value > 1000 || value < -1000) 145 snprintf(buf, 64, "$%#llx", value); 146 else 147 snprintf(buf, 64, "$%lld", value); 148 break; 149 } 150 case PSEUDO_ARG: 151 snprintf(buf, 64, "%%arg%d", pseudo->nr); 152 break; 153 case PSEUDO_PHI: 154 i = snprintf(buf, 64, "%%phi%d", pseudo->nr); 155 if (pseudo->ident) 156 sprintf(buf+i, "(%s)", show_ident(pseudo->ident)); 157 break; 158 default: 159 snprintf(buf, 64, "<bad pseudo type %d>", pseudo->type); 160 } 161 return buf; 162 } 163 164 static const char *opcodes[] = { 165 [OP_BADOP] = "bad_op", 166 167 /* Fn entrypoint */ 168 [OP_ENTRY] = "<entry-point>", 169 170 /* Terminator */ 171 [OP_RET] = "ret", 172 [OP_BR] = "br", 173 [OP_CBR] = "cbr", 174 [OP_SWITCH] = "switch", 175 [OP_INVOKE] = "invoke", 176 [OP_COMPUTEDGOTO] = "jmp *", 177 [OP_UNWIND] = "unwind", 178 179 /* Binary */ 180 [OP_ADD] = "add", 181 [OP_SUB] = "sub", 182 [OP_MULU] = "mulu", 183 [OP_MULS] = "muls", 184 [OP_DIVU] = "divu", 185 [OP_DIVS] = "divs", 186 [OP_MODU] = "modu", 187 [OP_MODS] = "mods", 188 [OP_SHL] = "shl", 189 [OP_LSR] = "lsr", 190 [OP_ASR] = "asr", 191 192 /* Logical */ 193 [OP_AND] = "and", 194 [OP_OR] = "or", 195 [OP_XOR] = "xor", 196 [OP_AND_BOOL] = "and-bool", 197 [OP_OR_BOOL] = "or-bool", 198 199 /* Binary comparison */ 200 [OP_SET_EQ] = "seteq", 201 [OP_SET_NE] = "setne", 202 [OP_SET_LE] = "setle", 203 [OP_SET_GE] = "setge", 204 [OP_SET_LT] = "setlt", 205 [OP_SET_GT] = "setgt", 206 [OP_SET_B] = "setb", 207 [OP_SET_A] = "seta", 208 [OP_SET_BE] = "setbe", 209 [OP_SET_AE] = "setae", 210 211 /* Uni */ 212 [OP_NOT] = "not", 213 [OP_NEG] = "neg", 214 215 /* Special three-input */ 216 [OP_SEL] = "select", 217 218 /* Memory */ 219 [OP_MALLOC] = "malloc", 220 [OP_FREE] = "free", 221 [OP_ALLOCA] = "alloca", 222 [OP_LOAD] = "load", 223 [OP_STORE] = "store", 224 [OP_SETVAL] = "set", 225 [OP_SYMADDR] = "symaddr", 226 [OP_GET_ELEMENT_PTR] = "getelem", 227 228 /* Other */ 229 [OP_PHI] = "phi", 230 [OP_PHISOURCE] = "phisrc", 231 [OP_CAST] = "cast", 232 [OP_SCAST] = "scast", 233 [OP_FPCAST] = "fpcast", 234 [OP_PTRCAST] = "ptrcast", 235 [OP_INLINED_CALL] = "# call", 236 [OP_CALL] = "call", 237 [OP_VANEXT] = "va_next", 238 [OP_VAARG] = "va_arg", 239 [OP_SLICE] = "slice", 240 [OP_SNOP] = "snop", 241 [OP_LNOP] = "lnop", 242 [OP_NOP] = "nop", 243 [OP_DEATHNOTE] = "dead", 244 [OP_ASM] = "asm", 245 246 /* Sparse tagging (line numbers, context, whatever) */ 247 [OP_CONTEXT] = "context", 248 [OP_RANGE] = "range-check", 249 250 [OP_COPY] = "copy", 251 }; 252 253 static char *show_asm_constraints(char *buf, const char *sep, struct asm_constraint_list *list) 254 { 255 struct asm_constraint *entry; 256 257 FOR_EACH_PTR(list, entry) { 258 buf += sprintf(buf, "%s\"%s\"", sep, entry->constraint); 259 if (entry->pseudo) 260 buf += sprintf(buf, " (%s)", show_pseudo(entry->pseudo)); 261 if (entry->ident) 262 buf += sprintf(buf, " [%s]", show_ident(entry->ident)); 263 sep = ", "; 264 } END_FOR_EACH_PTR(entry); 265 return buf; 266 } 267 268 static char *show_asm(char *buf, struct instruction *insn) 269 { 270 struct asm_rules *rules = insn->asm_rules; 271 272 buf += sprintf(buf, "\"%s\"", insn->string); 273 buf = show_asm_constraints(buf, "\n\t\tout: ", rules->outputs); 274 buf = show_asm_constraints(buf, "\n\t\tin: ", rules->inputs); 275 buf = show_asm_constraints(buf, "\n\t\tclobber: ", rules->clobbers); 276 return buf; 277 } 278 279 const char *show_instruction(struct instruction *insn) 280 { 281 int opcode = insn->opcode; 282 static char buffer[4096]; 283 char *buf; 284 285 buf = buffer; 286 if (!insn->bb) 287 buf += sprintf(buf, "# "); 288 289 if (opcode < ARRAY_SIZE(opcodes)) { 290 const char *op = opcodes[opcode]; 291 if (!op) 292 buf += sprintf(buf, "opcode:%d", opcode); 293 else 294 buf += sprintf(buf, "%s", op); 295 if (insn->size) 296 buf += sprintf(buf, ".%d", insn->size); 297 memset(buf, ' ', 20); 298 buf++; 299 } 300 301 if (buf < buffer + 12) 302 buf = buffer + 12; 303 switch (opcode) { 304 case OP_RET: 305 if (insn->src && insn->src != VOID) 306 buf += sprintf(buf, "%s", show_pseudo(insn->src)); 307 break; 308 309 case OP_CBR: 310 buf += sprintf(buf, "%s, .L%u, .L%u", show_pseudo(insn->cond), insn->bb_true->nr, insn->bb_false->nr); 311 break; 312 313 case OP_BR: 314 buf += sprintf(buf, ".L%u", insn->bb_true->nr); 315 break; 316 317 case OP_SYMADDR: { 318 struct symbol *sym = insn->symbol->sym; 319 buf += sprintf(buf, "%s <- ", show_pseudo(insn->target)); 320 321 if (!insn->bb && !sym) 322 break; 323 if (sym->bb_target) { 324 buf += sprintf(buf, ".L%u", sym->bb_target->nr); 325 break; 326 } 327 if (sym->ident) { 328 buf += sprintf(buf, "%s", show_ident(sym->ident)); 329 break; 330 } 331 buf += sprintf(buf, "<anon symbol:%p>", sym); 332 break; 333 } 334 335 case OP_SETVAL: { 336 struct expression *expr = insn->val; 337 struct symbol *sym; 338 buf += sprintf(buf, "%s <- ", show_pseudo(insn->target)); 339 340 if (!expr) { 341 buf += sprintf(buf, "%s", "<none>"); 342 break; 343 } 344 345 switch (expr->type) { 346 case EXPR_VALUE: 347 buf += sprintf(buf, "%lld", expr->value); 348 break; 349 case EXPR_FVALUE: 350 buf += sprintf(buf, "%Lf", expr->fvalue); 351 break; 352 case EXPR_STRING: 353 buf += sprintf(buf, "%.40s", show_string(expr->string)); 354 break; 355 case EXPR_SYMBOL: 356 buf += sprintf(buf, "%s", show_ident(expr->symbol->ident)); 357 break; 358 case EXPR_LABEL: 359 sym = expr->symbol; 360 if (sym->bb_target) 361 buf += sprintf(buf, ".L%u", sym->bb_target->nr); 362 break; 363 default: 364 buf += sprintf(buf, "SETVAL EXPR TYPE %d", expr->type); 365 } 366 break; 367 } 368 case OP_SWITCH: { 369 struct multijmp *jmp; 370 buf += sprintf(buf, "%s", show_pseudo(insn->cond)); 371 FOR_EACH_PTR(insn->multijmp_list, jmp) { 372 if (jmp->begin == jmp->end) 373 buf += sprintf(buf, ", %d -> .L%u", jmp->begin, jmp->target->nr); 374 else if (jmp->begin < jmp->end) 375 buf += sprintf(buf, ", %d ... %d -> .L%u", jmp->begin, jmp->end, jmp->target->nr); 376 else 377 buf += sprintf(buf, ", default -> .L%u", jmp->target->nr); 378 } END_FOR_EACH_PTR(jmp); 379 break; 380 } 381 case OP_COMPUTEDGOTO: { 382 struct multijmp *jmp; 383 buf += sprintf(buf, "%s", show_pseudo(insn->target)); 384 FOR_EACH_PTR(insn->multijmp_list, jmp) { 385 buf += sprintf(buf, ", .L%u", jmp->target->nr); 386 } END_FOR_EACH_PTR(jmp); 387 break; 388 } 389 390 case OP_PHISOURCE: { 391 struct instruction *phi; 392 buf += sprintf(buf, "%s <- %s ", show_pseudo(insn->target), show_pseudo(insn->phi_src)); 393 FOR_EACH_PTR(insn->phi_users, phi) { 394 buf += sprintf(buf, " (%s)", show_pseudo(phi->target)); 395 } END_FOR_EACH_PTR(phi); 396 break; 397 } 398 399 case OP_PHI: { 400 pseudo_t phi; 401 const char *s = " <-"; 402 buf += sprintf(buf, "%s", show_pseudo(insn->target)); 403 FOR_EACH_PTR(insn->phi_list, phi) { 404 buf += sprintf(buf, "%s %s", s, show_pseudo(phi)); 405 s = ","; 406 } END_FOR_EACH_PTR(phi); 407 break; 408 } 409 case OP_LOAD: case OP_LNOP: 410 buf += sprintf(buf, "%s <- %d[%s]", show_pseudo(insn->target), insn->offset, show_pseudo(insn->src)); 411 break; 412 case OP_STORE: case OP_SNOP: 413 buf += sprintf(buf, "%s -> %d[%s]", show_pseudo(insn->target), insn->offset, show_pseudo(insn->src)); 414 break; 415 case OP_INLINED_CALL: 416 case OP_CALL: { 417 struct pseudo *arg; 418 if (insn->target && insn->target != VOID) 419 buf += sprintf(buf, "%s <- ", show_pseudo(insn->target)); 420 buf += sprintf(buf, "%s", show_pseudo(insn->func)); 421 FOR_EACH_PTR(insn->arguments, arg) { 422 buf += sprintf(buf, ", %s", show_pseudo(arg)); 423 } END_FOR_EACH_PTR(arg); 424 break; 425 } 426 case OP_CAST: 427 case OP_SCAST: 428 case OP_FPCAST: 429 case OP_PTRCAST: 430 buf += sprintf(buf, "%s <- (%d) %s", 431 show_pseudo(insn->target), 432 type_size(insn->orig_type), 433 show_pseudo(insn->src)); 434 break; 435 case OP_BINARY ... OP_BINARY_END: 436 case OP_BINCMP ... OP_BINCMP_END: 437 buf += sprintf(buf, "%s <- %s, %s", show_pseudo(insn->target), show_pseudo(insn->src1), show_pseudo(insn->src2)); 438 break; 439 440 case OP_SEL: 441 buf += sprintf(buf, "%s <- %s, %s, %s", show_pseudo(insn->target), 442 show_pseudo(insn->src1), show_pseudo(insn->src2), show_pseudo(insn->src3)); 443 break; 444 445 case OP_SLICE: 446 buf += sprintf(buf, "%s <- %s, %d, %d", show_pseudo(insn->target), show_pseudo(insn->base), insn->from, insn->len); 447 break; 448 449 case OP_NOT: case OP_NEG: 450 buf += sprintf(buf, "%s <- %s", show_pseudo(insn->target), show_pseudo(insn->src1)); 451 break; 452 453 case OP_CONTEXT: 454 buf += sprintf(buf, "%s%d", insn->check ? "check: " : "", insn->increment); 455 break; 456 case OP_RANGE: 457 buf += sprintf(buf, "%s between %s..%s", show_pseudo(insn->src1), show_pseudo(insn->src2), show_pseudo(insn->src3)); 458 break; 459 case OP_NOP: 460 buf += sprintf(buf, "%s <- %s", show_pseudo(insn->target), show_pseudo(insn->src1)); 461 break; 462 case OP_DEATHNOTE: 463 buf += sprintf(buf, "%s", show_pseudo(insn->target)); 464 break; 465 case OP_ASM: 466 buf = show_asm(buf, insn); 467 break; 468 case OP_COPY: 469 buf += sprintf(buf, "%s <- %s", show_pseudo(insn->target), show_pseudo(insn->src)); 470 break; 471 default: 472 break; 473 } 474 475 if (buf >= buffer + sizeof(buffer)) 476 die("instruction buffer overflowed %td\n", buf - buffer); 477 do { --buf; } while (*buf == ' '); 478 *++buf = 0; 479 return buffer; 480 } 481 482 void show_bb(struct basic_block *bb) 483 { 484 struct instruction *insn; 485 486 printf(".L%u:\n", bb->nr); 487 if (verbose) { 488 pseudo_t needs, defines; 489 printf("%s:%d\n", stream_name(bb->pos.stream), bb->pos.line); 490 491 FOR_EACH_PTR(bb->needs, needs) { 492 struct instruction *def = needs->def; 493 if (def->opcode != OP_PHI) { 494 printf(" **uses %s (from .L%u)**\n", show_pseudo(needs), def->bb->nr); 495 } else { 496 pseudo_t phi; 497 const char *sep = " "; 498 printf(" **uses %s (from", show_pseudo(needs)); 499 FOR_EACH_PTR(def->phi_list, phi) { 500 if (phi == VOID) 501 continue; 502 printf("%s(%s:.L%u)", sep, show_pseudo(phi), phi->def->bb->nr); 503 sep = ", "; 504 } END_FOR_EACH_PTR(phi); 505 printf(")**\n"); 506 } 507 } END_FOR_EACH_PTR(needs); 508 509 FOR_EACH_PTR(bb->defines, defines) { 510 printf(" **defines %s **\n", show_pseudo(defines)); 511 } END_FOR_EACH_PTR(defines); 512 513 if (bb->parents) { 514 struct basic_block *from; 515 FOR_EACH_PTR(bb->parents, from) { 516 printf(" **from .L%u (%s:%d:%d)**\n", from->nr, 517 stream_name(from->pos.stream), from->pos.line, from->pos.pos); 518 } END_FOR_EACH_PTR(from); 519 } 520 521 if (bb->children) { 522 struct basic_block *to; 523 FOR_EACH_PTR(bb->children, to) { 524 printf(" **to .L%u (%s:%d:%d)**\n", to->nr, 525 stream_name(to->pos.stream), to->pos.line, to->pos.pos); 526 } END_FOR_EACH_PTR(to); 527 } 528 } 529 530 FOR_EACH_PTR(bb->insns, insn) { 531 if (!insn->bb && verbose < 2) 532 continue; 533 printf("\t%s\n", show_instruction(insn)); 534 } END_FOR_EACH_PTR(insn); 535 if (!bb_terminated(bb)) 536 printf("\tEND\n"); 537 } 538 539 static void show_symbol_usage(pseudo_t pseudo) 540 { 541 struct pseudo_user *pu; 542 543 if (pseudo) { 544 FOR_EACH_PTR(pseudo->users, pu) { 545 printf("\t%s\n", show_instruction(pu->insn)); 546 } END_FOR_EACH_PTR(pu); 547 } 548 } 549 550 void show_entry(struct entrypoint *ep) 551 { 552 struct symbol *sym; 553 struct basic_block *bb; 554 555 printf("%s:\n", show_ident(ep->name->ident)); 556 557 if (verbose) { 558 printf("ep %p: %s\n", ep, show_ident(ep->name->ident)); 559 560 FOR_EACH_PTR(ep->syms, sym) { 561 if (!sym->pseudo) 562 continue; 563 if (!sym->pseudo->users) 564 continue; 565 printf(" sym: %p %s\n", sym, show_ident(sym->ident)); 566 if (sym->ctype.modifiers & (MOD_EXTERN | MOD_STATIC | MOD_ADDRESSABLE)) 567 printf("\texternal visibility\n"); 568 show_symbol_usage(sym->pseudo); 569 } END_FOR_EACH_PTR(sym); 570 571 printf("\n"); 572 } 573 574 FOR_EACH_PTR(ep->bbs, bb) { 575 if (!bb) 576 continue; 577 if (!bb->parents && !bb->children && !bb->insns && verbose < 2) 578 continue; 579 show_bb(bb); 580 printf("\n"); 581 } END_FOR_EACH_PTR(bb); 582 583 printf("\n"); 584 } 585 586 static void bind_label(struct symbol *label, struct basic_block *bb, struct position pos) 587 { 588 if (label->bb_target) 589 warning(pos, "label '%s' already bound", show_ident(label->ident)); 590 label->bb_target = bb; 591 } 592 593 static struct basic_block * get_bound_block(struct entrypoint *ep, struct symbol *label) 594 { 595 struct basic_block *bb = label->bb_target; 596 597 if (!bb) { 598 bb = alloc_basic_block(ep, label->pos); 599 label->bb_target = bb; 600 } 601 return bb; 602 } 603 604 static void finish_block(struct entrypoint *ep) 605 { 606 struct basic_block *src = ep->active; 607 if (bb_reachable(src)) 608 ep->active = NULL; 609 } 610 611 static void add_goto(struct entrypoint *ep, struct basic_block *dst) 612 { 613 struct basic_block *src = ep->active; 614 if (bb_reachable(src)) { 615 struct instruction *br = alloc_instruction(OP_BR, 0); 616 br->bb_true = dst; 617 add_bb(&dst->parents, src); 618 add_bb(&src->children, dst); 619 br->bb = src; 620 add_instruction(&src->insns, br); 621 ep->active = NULL; 622 } 623 } 624 625 static void add_one_insn(struct entrypoint *ep, struct instruction *insn) 626 { 627 struct basic_block *bb = ep->active; 628 629 if (bb_reachable(bb)) { 630 insn->bb = bb; 631 add_instruction(&bb->insns, insn); 632 } 633 } 634 635 static void set_activeblock(struct entrypoint *ep, struct basic_block *bb) 636 { 637 if (!bb_terminated(ep->active)) 638 add_goto(ep, bb); 639 640 ep->active = bb; 641 if (bb_reachable(bb)) 642 add_bb(&ep->bbs, bb); 643 } 644 645 static void remove_parent(struct basic_block *child, struct basic_block *parent) 646 { 647 remove_bb_from_list(&child->parents, parent, 1); 648 if (!child->parents) 649 repeat_phase |= REPEAT_CFG_CLEANUP; 650 } 651 652 /* Change a "switch" or a conditional branch into a branch */ 653 void insert_branch(struct basic_block *bb, struct instruction *jmp, struct basic_block *target) 654 { 655 struct instruction *br, *old; 656 struct basic_block *child; 657 658 /* Remove the switch */ 659 old = delete_last_instruction(&bb->insns); 660 assert(old == jmp); 661 kill_instruction(old); 662 663 br = alloc_instruction(OP_BR, 0); 664 br->bb = bb; 665 br->bb_true = target; 666 add_instruction(&bb->insns, br); 667 668 FOR_EACH_PTR(bb->children, child) { 669 if (child == target) { 670 target = NULL; /* Trigger just once */ 671 continue; 672 } 673 DELETE_CURRENT_PTR(child); 674 remove_parent(child, bb); 675 } END_FOR_EACH_PTR(child); 676 PACK_PTR_LIST(&bb->children); 677 } 678 679 680 void insert_select(struct basic_block *bb, struct instruction *br, struct instruction *phi_node, pseudo_t if_true, pseudo_t if_false) 681 { 682 pseudo_t target; 683 struct instruction *select; 684 685 /* Remove the 'br' */ 686 delete_last_instruction(&bb->insns); 687 688 select = alloc_instruction(OP_SEL, phi_node->size); 689 select->bb = bb; 690 691 assert(br->cond); 692 use_pseudo(select, br->cond, &select->src1); 693 694 target = phi_node->target; 695 assert(target->def == phi_node); 696 select->target = target; 697 target->def = select; 698 699 use_pseudo(select, if_true, &select->src2); 700 use_pseudo(select, if_false, &select->src3); 701 702 add_instruction(&bb->insns, select); 703 add_instruction(&bb->insns, br); 704 } 705 706 static inline int bb_empty(struct basic_block *bb) 707 { 708 return !bb->insns; 709 } 710 711 /* Add a label to the currently active block, return new active block */ 712 static struct basic_block * add_label(struct entrypoint *ep, struct symbol *label) 713 { 714 struct basic_block *bb = label->bb_target; 715 716 if (bb) { 717 set_activeblock(ep, bb); 718 return bb; 719 } 720 bb = ep->active; 721 if (!bb_reachable(bb) || !bb_empty(bb)) { 722 bb = alloc_basic_block(ep, label->pos); 723 set_activeblock(ep, bb); 724 } 725 label->bb_target = bb; 726 return bb; 727 } 728 729 static void add_branch(struct entrypoint *ep, struct expression *expr, pseudo_t cond, struct basic_block *bb_true, struct basic_block *bb_false) 730 { 731 struct basic_block *bb = ep->active; 732 struct instruction *br; 733 734 if (bb_reachable(bb)) { 735 br = alloc_instruction(OP_CBR, 0); 736 use_pseudo(br, cond, &br->cond); 737 br->bb_true = bb_true; 738 br->bb_false = bb_false; 739 add_bb(&bb_true->parents, bb); 740 add_bb(&bb_false->parents, bb); 741 add_bb(&bb->children, bb_true); 742 add_bb(&bb->children, bb_false); 743 add_one_insn(ep, br); 744 } 745 } 746 747 /* Dummy pseudo allocator */ 748 pseudo_t alloc_pseudo(struct instruction *def) 749 { 750 static int nr = 0; 751 struct pseudo * pseudo = __alloc_pseudo(0); 752 pseudo->type = PSEUDO_REG; 753 pseudo->nr = ++nr; 754 pseudo->def = def; 755 return pseudo; 756 } 757 758 static void clear_symbol_pseudos(struct entrypoint *ep) 759 { 760 pseudo_t pseudo; 761 762 FOR_EACH_PTR(ep->accesses, pseudo) { 763 pseudo->sym->pseudo = NULL; 764 } END_FOR_EACH_PTR(pseudo); 765 } 766 767 static pseudo_t symbol_pseudo(struct entrypoint *ep, struct symbol *sym) 768 { 769 pseudo_t pseudo; 770 771 if (!sym) 772 return VOID; 773 774 pseudo = sym->pseudo; 775 if (!pseudo) { 776 pseudo = __alloc_pseudo(0); 777 pseudo->nr = -1; 778 pseudo->type = PSEUDO_SYM; 779 pseudo->sym = sym; 780 pseudo->ident = sym->ident; 781 sym->pseudo = pseudo; 782 add_pseudo(&ep->accesses, pseudo); 783 } 784 /* Symbol pseudos have neither nr, usage nor def */ 785 return pseudo; 786 } 787 788 pseudo_t value_pseudo(struct symbol *type, long long val) 789 { 790 #define MAX_VAL_HASH 64 791 static struct pseudo_list *prev[MAX_VAL_HASH]; 792 int hash = val & (MAX_VAL_HASH-1); 793 struct pseudo_list **list = prev + hash; 794 int size = type ? type->bit_size : value_size(val); 795 pseudo_t pseudo; 796 797 798 FOR_EACH_PTR(*list, pseudo) { 799 if (pseudo->value == val && pseudo->size == size) 800 return pseudo; 801 } END_FOR_EACH_PTR(pseudo); 802 803 pseudo = __alloc_pseudo(0); 804 pseudo->type = PSEUDO_VAL; 805 pseudo->value = val; 806 pseudo->size = size; 807 add_pseudo(list, pseudo); 808 809 /* Value pseudos have neither nr, usage nor def */ 810 return pseudo; 811 } 812 813 static pseudo_t argument_pseudo(struct entrypoint *ep, int nr) 814 { 815 pseudo_t pseudo = __alloc_pseudo(0); 816 struct instruction *entry = ep->entry; 817 818 pseudo->type = PSEUDO_ARG; 819 pseudo->nr = nr; 820 pseudo->def = entry; 821 add_pseudo(&entry->arg_list, pseudo); 822 823 /* Argument pseudos have neither usage nor def */ 824 return pseudo; 825 } 826 827 pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, int size) 828 { 829 struct instruction *insn; 830 pseudo_t phi; 831 static int nr = 0; 832 833 if (!source) 834 return VOID; 835 836 insn = alloc_instruction(OP_PHISOURCE, size); 837 phi = __alloc_pseudo(0); 838 phi->type = PSEUDO_PHI; 839 phi->nr = ++nr; 840 phi->def = insn; 841 842 use_pseudo(insn, pseudo, &insn->phi_src); 843 insn->bb = source; 844 insn->target = phi; 845 add_instruction(&source->insns, insn); 846 return phi; 847 } 848 849 /* 850 * We carry the "access_data" structure around for any accesses, 851 * which simplifies things a lot. It contains all the access 852 * information in one place. 853 */ 854 struct access_data { 855 struct symbol *result_type; // result ctype 856 struct symbol *source_type; // source ctype 857 pseudo_t address; // pseudo containing address .. 858 unsigned int offset; // byte offset 859 struct position pos; 860 }; 861 862 static void finish_address_gen(struct entrypoint *ep, struct access_data *ad) 863 { 864 } 865 866 static int linearize_simple_address(struct entrypoint *ep, 867 struct expression *addr, 868 struct access_data *ad) 869 { 870 if (addr->type == EXPR_SYMBOL) { 871 linearize_one_symbol(ep, addr->symbol); 872 ad->address = symbol_pseudo(ep, addr->symbol); 873 return 1; 874 } 875 if (addr->type == EXPR_BINOP) { 876 if (addr->right->type == EXPR_VALUE) { 877 if (addr->op == '+') { 878 ad->offset += get_expression_value(addr->right); 879 return linearize_simple_address(ep, addr->left, ad); 880 } 881 } 882 } 883 ad->address = linearize_expression(ep, addr); 884 return 1; 885 } 886 887 static struct symbol *base_type(struct symbol *sym) 888 { 889 struct symbol *base = sym; 890 891 if (sym) { 892 if (sym->type == SYM_NODE) 893 base = base->ctype.base_type; 894 if (base->type == SYM_BITFIELD) 895 return base->ctype.base_type; 896 } 897 return sym; 898 } 899 900 static int linearize_address_gen(struct entrypoint *ep, 901 struct expression *expr, 902 struct access_data *ad) 903 { 904 struct symbol *ctype = expr->ctype; 905 906 if (!ctype) 907 return 0; 908 ad->pos = expr->pos; 909 ad->result_type = ctype; 910 ad->source_type = base_type(ctype); 911 if (expr->type == EXPR_PREOP && expr->op == '*') 912 return linearize_simple_address(ep, expr->unop, ad); 913 914 warning(expr->pos, "generating address of non-lvalue (%d)", expr->type); 915 return 0; 916 } 917 918 static pseudo_t add_load(struct entrypoint *ep, struct access_data *ad) 919 { 920 struct instruction *insn; 921 pseudo_t new; 922 923 insn = alloc_typed_instruction(OP_LOAD, ad->source_type); 924 new = alloc_pseudo(insn); 925 926 insn->target = new; 927 insn->offset = ad->offset; 928 use_pseudo(insn, ad->address, &insn->src); 929 add_one_insn(ep, insn); 930 return new; 931 } 932 933 static void add_store(struct entrypoint *ep, struct access_data *ad, pseudo_t value) 934 { 935 struct basic_block *bb = ep->active; 936 937 if (bb_reachable(bb)) { 938 struct instruction *store = alloc_typed_instruction(OP_STORE, ad->source_type); 939 store->offset = ad->offset; 940 use_pseudo(store, value, &store->target); 941 use_pseudo(store, ad->address, &store->src); 942 add_one_insn(ep, store); 943 } 944 } 945 946 static pseudo_t linearize_store_gen(struct entrypoint *ep, 947 pseudo_t value, 948 struct access_data *ad) 949 { 950 pseudo_t store = value; 951 952 if (type_size(ad->source_type) != type_size(ad->result_type)) { 953 struct symbol *ctype = ad->result_type; 954 unsigned int shift = ctype->bit_offset; 955 unsigned int size = ctype->bit_size; 956 pseudo_t orig = add_load(ep, ad); 957 unsigned long long mask = (1ULL << size) - 1; 958 959 if (shift) { 960 store = add_binary_op(ep, ad->source_type, OP_SHL, value, value_pseudo(ctype, shift)); 961 mask <<= shift; 962 } 963 orig = add_binary_op(ep, ad->source_type, OP_AND, orig, value_pseudo(ctype, ~mask)); 964 store = add_binary_op(ep, ad->source_type, OP_OR, orig, store); 965 } 966 add_store(ep, ad, store); 967 return value; 968 } 969 970 static pseudo_t add_binary_op(struct entrypoint *ep, struct symbol *ctype, int op, pseudo_t left, pseudo_t right) 971 { 972 struct instruction *insn = alloc_typed_instruction(op, ctype); 973 pseudo_t target = alloc_pseudo(insn); 974 insn->target = target; 975 use_pseudo(insn, left, &insn->src1); 976 use_pseudo(insn, right, &insn->src2); 977 add_one_insn(ep, insn); 978 return target; 979 } 980 981 static pseudo_t add_setval(struct entrypoint *ep, struct symbol *ctype, struct expression *val) 982 { 983 struct instruction *insn = alloc_typed_instruction(OP_SETVAL, ctype); 984 pseudo_t target = alloc_pseudo(insn); 985 insn->target = target; 986 insn->val = val; 987 add_one_insn(ep, insn); 988 return target; 989 } 990 991 static pseudo_t add_symbol_address(struct entrypoint *ep, struct symbol *sym) 992 { 993 struct instruction *insn = alloc_instruction(OP_SYMADDR, bits_in_pointer); 994 pseudo_t target = alloc_pseudo(insn); 995 996 insn->target = target; 997 use_pseudo(insn, symbol_pseudo(ep, sym), &insn->symbol); 998 add_one_insn(ep, insn); 999 return target; 1000 } 1001 1002 static pseudo_t linearize_load_gen(struct entrypoint *ep, struct access_data *ad) 1003 { 1004 struct symbol *ctype = ad->result_type; 1005 pseudo_t new = add_load(ep, ad); 1006 1007 if (ctype->bit_offset) { 1008 pseudo_t shift = value_pseudo(ctype, ctype->bit_offset); 1009 pseudo_t newval = add_binary_op(ep, ad->source_type, OP_LSR, new, shift); 1010 new = newval; 1011 } 1012 if (ctype->bit_size != type_size(ad->source_type)) 1013 new = cast_pseudo(ep, new, ad->source_type, ad->result_type); 1014 return new; 1015 } 1016 1017 static pseudo_t linearize_access(struct entrypoint *ep, struct expression *expr) 1018 { 1019 struct access_data ad = { NULL, }; 1020 pseudo_t value; 1021 1022 if (!linearize_address_gen(ep, expr, &ad)) 1023 return VOID; 1024 value = linearize_load_gen(ep, &ad); 1025 finish_address_gen(ep, &ad); 1026 return value; 1027 } 1028 1029 /* FIXME: FP */ 1030 static pseudo_t linearize_inc_dec(struct entrypoint *ep, struct expression *expr, int postop) 1031 { 1032 struct access_data ad = { NULL, }; 1033 pseudo_t old, new, one; 1034 int op = expr->op == SPECIAL_INCREMENT ? OP_ADD : OP_SUB; 1035 1036 if (!linearize_address_gen(ep, expr->unop, &ad)) 1037 return VOID; 1038 1039 old = linearize_load_gen(ep, &ad); 1040 one = value_pseudo(expr->ctype, expr->op_value); 1041 new = add_binary_op(ep, expr->ctype, op, old, one); 1042 linearize_store_gen(ep, new, &ad); 1043 finish_address_gen(ep, &ad); 1044 return postop ? old : new; 1045 } 1046 1047 static pseudo_t add_uniop(struct entrypoint *ep, struct expression *expr, int op, pseudo_t src) 1048 { 1049 struct instruction *insn = alloc_typed_instruction(op, expr->ctype); 1050 pseudo_t new = alloc_pseudo(insn); 1051 1052 insn->target = new; 1053 use_pseudo(insn, src, &insn->src1); 1054 add_one_insn(ep, insn); 1055 return new; 1056 } 1057 1058 static pseudo_t linearize_slice(struct entrypoint *ep, struct expression *expr) 1059 { 1060 pseudo_t pre = linearize_expression(ep, expr->base); 1061 struct instruction *insn = alloc_typed_instruction(OP_SLICE, expr->ctype); 1062 pseudo_t new = alloc_pseudo(insn); 1063 1064 insn->target = new; 1065 insn->from = expr->r_bitpos; 1066 insn->len = expr->r_nrbits; 1067 use_pseudo(insn, pre, &insn->base); 1068 add_one_insn(ep, insn); 1069 return new; 1070 } 1071 1072 static pseudo_t linearize_regular_preop(struct entrypoint *ep, struct expression *expr) 1073 { 1074 pseudo_t pre = linearize_expression(ep, expr->unop); 1075 switch (expr->op) { 1076 case '+': 1077 return pre; 1078 case '!': { 1079 pseudo_t zero = value_pseudo(expr->ctype, 0); 1080 return add_binary_op(ep, expr->ctype, OP_SET_EQ, pre, zero); 1081 } 1082 case '~': 1083 return add_uniop(ep, expr, OP_NOT, pre); 1084 case '-': 1085 return add_uniop(ep, expr, OP_NEG, pre); 1086 } 1087 return VOID; 1088 } 1089 1090 static pseudo_t linearize_preop(struct entrypoint *ep, struct expression *expr) 1091 { 1092 /* 1093 * '*' is an lvalue access, and is fundamentally different 1094 * from an arithmetic operation. Maybe it should have an 1095 * expression type of its own.. 1096 */ 1097 if (expr->op == '*') 1098 return linearize_access(ep, expr); 1099 if (expr->op == SPECIAL_INCREMENT || expr->op == SPECIAL_DECREMENT) 1100 return linearize_inc_dec(ep, expr, 0); 1101 return linearize_regular_preop(ep, expr); 1102 } 1103 1104 static pseudo_t linearize_postop(struct entrypoint *ep, struct expression *expr) 1105 { 1106 return linearize_inc_dec(ep, expr, 1); 1107 } 1108 1109 /* 1110 * Casts to pointers are "less safe" than other casts, since 1111 * they imply type-unsafe accesses. "void *" is a special 1112 * case, since you can't access through it anyway without another 1113 * cast. 1114 */ 1115 static struct instruction *alloc_cast_instruction(struct symbol *src, struct symbol *ctype) 1116 { 1117 int opcode = OP_CAST; 1118 struct symbol *base = ctype; 1119 1120 if (src->ctype.modifiers & MOD_SIGNED) 1121 opcode = OP_SCAST; 1122 if (base->type == SYM_NODE) 1123 base = base->ctype.base_type; 1124 if (base->type == SYM_PTR) { 1125 base = base->ctype.base_type; 1126 if (base != &void_ctype) 1127 opcode = OP_PTRCAST; 1128 } else if (base->ctype.base_type == &fp_type) 1129 opcode = OP_FPCAST; 1130 return alloc_typed_instruction(opcode, ctype); 1131 } 1132 1133 static pseudo_t cast_pseudo(struct entrypoint *ep, pseudo_t src, struct symbol *from, struct symbol *to) 1134 { 1135 pseudo_t result; 1136 struct instruction *insn; 1137 1138 if (src == VOID) 1139 return VOID; 1140 if (!from || !to) 1141 return VOID; 1142 if (from->bit_size < 0 || to->bit_size < 0) 1143 return VOID; 1144 insn = alloc_cast_instruction(from, to); 1145 result = alloc_pseudo(insn); 1146 insn->target = result; 1147 insn->orig_type = from; 1148 use_pseudo(insn, src, &insn->src); 1149 add_one_insn(ep, insn); 1150 return result; 1151 } 1152 1153 static int opcode_sign(int opcode, struct symbol *ctype) 1154 { 1155 if (ctype && (ctype->ctype.modifiers & MOD_SIGNED)) { 1156 switch(opcode) { 1157 case OP_MULU: case OP_DIVU: case OP_MODU: case OP_LSR: 1158 opcode++; 1159 } 1160 } 1161 return opcode; 1162 } 1163 1164 static inline pseudo_t add_convert_to_bool(struct entrypoint *ep, pseudo_t src, struct symbol *type) 1165 { 1166 pseudo_t zero; 1167 int op; 1168 1169 if (is_bool_type(type)) 1170 return src; 1171 zero = value_pseudo(type, 0); 1172 op = OP_SET_NE; 1173 return add_binary_op(ep, &bool_ctype, op, src, zero); 1174 } 1175 1176 static pseudo_t linearize_expression_to_bool(struct entrypoint *ep, struct expression *expr) 1177 { 1178 pseudo_t dst; 1179 dst = linearize_expression(ep, expr); 1180 dst = add_convert_to_bool(ep, dst, expr->ctype); 1181 return dst; 1182 } 1183 1184 static pseudo_t linearize_assignment(struct entrypoint *ep, struct expression *expr) 1185 { 1186 struct access_data ad = { NULL, }; 1187 struct expression *target = expr->left; 1188 struct expression *src = expr->right; 1189 struct symbol *ctype; 1190 pseudo_t value; 1191 1192 value = linearize_expression(ep, src); 1193 if (!target || !linearize_address_gen(ep, target, &ad)) 1194 return value; 1195 if (expr->op != '=') { 1196 pseudo_t oldvalue = linearize_load_gen(ep, &ad); 1197 pseudo_t dst; 1198 static const int op_trans[] = { 1199 [SPECIAL_ADD_ASSIGN - SPECIAL_BASE] = OP_ADD, 1200 [SPECIAL_SUB_ASSIGN - SPECIAL_BASE] = OP_SUB, 1201 [SPECIAL_MUL_ASSIGN - SPECIAL_BASE] = OP_MULU, 1202 [SPECIAL_DIV_ASSIGN - SPECIAL_BASE] = OP_DIVU, 1203 [SPECIAL_MOD_ASSIGN - SPECIAL_BASE] = OP_MODU, 1204 [SPECIAL_SHL_ASSIGN - SPECIAL_BASE] = OP_SHL, 1205 [SPECIAL_SHR_ASSIGN - SPECIAL_BASE] = OP_LSR, 1206 [SPECIAL_AND_ASSIGN - SPECIAL_BASE] = OP_AND, 1207 [SPECIAL_OR_ASSIGN - SPECIAL_BASE] = OP_OR, 1208 [SPECIAL_XOR_ASSIGN - SPECIAL_BASE] = OP_XOR 1209 }; 1210 int opcode; 1211 1212 if (!src) 1213 return VOID; 1214 1215 ctype = src->ctype; 1216 oldvalue = cast_pseudo(ep, oldvalue, target->ctype, ctype); 1217 opcode = opcode_sign(op_trans[expr->op - SPECIAL_BASE], ctype); 1218 dst = add_binary_op(ep, ctype, opcode, oldvalue, value); 1219 value = cast_pseudo(ep, dst, ctype, expr->ctype); 1220 } 1221 value = linearize_store_gen(ep, value, &ad); 1222 finish_address_gen(ep, &ad); 1223 return value; 1224 } 1225 1226 static pseudo_t linearize_call_expression(struct entrypoint *ep, struct expression *expr) 1227 { 1228 struct expression *arg, *fn; 1229 struct instruction *insn = alloc_typed_instruction(OP_CALL, expr->ctype); 1230 pseudo_t retval, call; 1231 struct ctype *ctype = NULL; 1232 struct symbol *fntype; 1233 struct context *context; 1234 1235 if (!expr->ctype) { 1236 warning(expr->pos, "call with no type!"); 1237 return VOID; 1238 } 1239 1240 FOR_EACH_PTR(expr->args, arg) { 1241 pseudo_t new = linearize_expression(ep, arg); 1242 use_pseudo(insn, new, add_pseudo(&insn->arguments, new)); 1243 } END_FOR_EACH_PTR(arg); 1244 1245 fn = expr->fn; 1246 1247 if (fn->ctype) 1248 ctype = &fn->ctype->ctype; 1249 1250 fntype = fn->ctype; 1251 if (fntype) { 1252 if (fntype->type == SYM_NODE) 1253 fntype = fntype->ctype.base_type; 1254 } 1255 insn->fntype = fntype; 1256 1257 if (fn->type == EXPR_PREOP) { 1258 if (fn->unop->type == EXPR_SYMBOL) { 1259 struct symbol *sym = fn->unop->symbol; 1260 if (sym->ctype.base_type->type == SYM_FN) 1261 fn = fn->unop; 1262 } 1263 } 1264 if (fn->type == EXPR_SYMBOL) { 1265 call = symbol_pseudo(ep, fn->symbol); 1266 } else { 1267 call = linearize_expression(ep, fn); 1268 } 1269 use_pseudo(insn, call, &insn->func); 1270 retval = VOID; 1271 if (expr->ctype != &void_ctype) 1272 retval = alloc_pseudo(insn); 1273 insn->target = retval; 1274 add_one_insn(ep, insn); 1275 1276 if (ctype) { 1277 FOR_EACH_PTR(ctype->contexts, context) { 1278 int in = context->in; 1279 int out = context->out; 1280 int check = 0; 1281 int context_diff; 1282 if (in < 0) { 1283 check = 1; 1284 in = 0; 1285 } 1286 if (out < 0) { 1287 check = 0; 1288 out = 0; 1289 } 1290 context_diff = out - in; 1291 if (check || context_diff) { 1292 insn = alloc_instruction(OP_CONTEXT, 0); 1293 insn->increment = context_diff; 1294 insn->check = check; 1295 insn->context_expr = context->context; 1296 add_one_insn(ep, insn); 1297 } 1298 } END_FOR_EACH_PTR(context); 1299 } 1300 1301 return retval; 1302 } 1303 1304 static pseudo_t linearize_binop_bool(struct entrypoint *ep, struct expression *expr) 1305 { 1306 pseudo_t src1, src2, dst; 1307 int op = (expr->op == SPECIAL_LOGICAL_OR) ? OP_OR_BOOL : OP_AND_BOOL; 1308 1309 src1 = linearize_expression_to_bool(ep, expr->left); 1310 src2 = linearize_expression_to_bool(ep, expr->right); 1311 dst = add_binary_op(ep, &bool_ctype, op, src1, src2); 1312 if (expr->ctype != &bool_ctype) 1313 dst = cast_pseudo(ep, dst, &bool_ctype, expr->ctype); 1314 return dst; 1315 } 1316 1317 static pseudo_t linearize_binop(struct entrypoint *ep, struct expression *expr) 1318 { 1319 pseudo_t src1, src2, dst; 1320 static const int opcode[] = { 1321 ['+'] = OP_ADD, ['-'] = OP_SUB, 1322 ['*'] = OP_MULU, ['/'] = OP_DIVU, 1323 ['%'] = OP_MODU, ['&'] = OP_AND, 1324 ['|'] = OP_OR, ['^'] = OP_XOR, 1325 [SPECIAL_LEFTSHIFT] = OP_SHL, 1326 [SPECIAL_RIGHTSHIFT] = OP_LSR, 1327 }; 1328 int op; 1329 1330 src1 = linearize_expression(ep, expr->left); 1331 src2 = linearize_expression(ep, expr->right); 1332 op = opcode_sign(opcode[expr->op], expr->ctype); 1333 dst = add_binary_op(ep, expr->ctype, op, src1, src2); 1334 return dst; 1335 } 1336 1337 static pseudo_t linearize_logical_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false); 1338 1339 pseudo_t linearize_cond_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false); 1340 1341 static pseudo_t linearize_select(struct entrypoint *ep, struct expression *expr) 1342 { 1343 pseudo_t cond, true, false, res; 1344 struct instruction *insn; 1345 1346 true = linearize_expression(ep, expr->cond_true); 1347 false = linearize_expression(ep, expr->cond_false); 1348 cond = linearize_expression(ep, expr->conditional); 1349 1350 insn = alloc_typed_instruction(OP_SEL, expr->ctype); 1351 if (!expr->cond_true) 1352 true = cond; 1353 use_pseudo(insn, cond, &insn->src1); 1354 use_pseudo(insn, true, &insn->src2); 1355 use_pseudo(insn, false, &insn->src3); 1356 1357 res = alloc_pseudo(insn); 1358 insn->target = res; 1359 add_one_insn(ep, insn); 1360 return res; 1361 } 1362 1363 static pseudo_t add_join_conditional(struct entrypoint *ep, struct expression *expr, 1364 pseudo_t phi1, pseudo_t phi2) 1365 { 1366 pseudo_t target; 1367 struct instruction *phi_node; 1368 1369 if (phi1 == VOID) 1370 return phi2; 1371 if (phi2 == VOID) 1372 return phi1; 1373 1374 phi_node = alloc_typed_instruction(OP_PHI, expr->ctype); 1375 use_pseudo(phi_node, phi1, add_pseudo(&phi_node->phi_list, phi1)); 1376 use_pseudo(phi_node, phi2, add_pseudo(&phi_node->phi_list, phi2)); 1377 phi_node->target = target = alloc_pseudo(phi_node); 1378 add_one_insn(ep, phi_node); 1379 return target; 1380 } 1381 1382 static pseudo_t linearize_short_conditional(struct entrypoint *ep, struct expression *expr, 1383 struct expression *cond, 1384 struct expression *expr_false) 1385 { 1386 pseudo_t src1, src2; 1387 struct basic_block *bb_false; 1388 struct basic_block *merge = alloc_basic_block(ep, expr->pos); 1389 pseudo_t phi1, phi2; 1390 int size = type_size(expr->ctype); 1391 1392 if (!expr_false || !ep->active) 1393 return VOID; 1394 1395 bb_false = alloc_basic_block(ep, expr_false->pos); 1396 src1 = linearize_expression(ep, cond); 1397 phi1 = alloc_phi(ep->active, src1, size); 1398 add_branch(ep, expr, src1, merge, bb_false); 1399 1400 set_activeblock(ep, bb_false); 1401 src2 = linearize_expression(ep, expr_false); 1402 phi2 = alloc_phi(ep->active, src2, size); 1403 set_activeblock(ep, merge); 1404 1405 return add_join_conditional(ep, expr, phi1, phi2); 1406 } 1407 1408 static pseudo_t linearize_conditional(struct entrypoint *ep, struct expression *expr, 1409 struct expression *cond, 1410 struct expression *expr_true, 1411 struct expression *expr_false) 1412 { 1413 pseudo_t src1, src2; 1414 pseudo_t phi1, phi2; 1415 struct basic_block *bb_true, *bb_false, *merge; 1416 int size = type_size(expr->ctype); 1417 1418 if (!cond || !expr_true || !expr_false || !ep->active) 1419 return VOID; 1420 bb_true = alloc_basic_block(ep, expr_true->pos); 1421 bb_false = alloc_basic_block(ep, expr_false->pos); 1422 merge = alloc_basic_block(ep, expr->pos); 1423 1424 linearize_cond_branch(ep, cond, bb_true, bb_false); 1425 1426 set_activeblock(ep, bb_true); 1427 src1 = linearize_expression(ep, expr_true); 1428 phi1 = alloc_phi(ep->active, src1, size); 1429 add_goto(ep, merge); 1430 1431 set_activeblock(ep, bb_false); 1432 src2 = linearize_expression(ep, expr_false); 1433 phi2 = alloc_phi(ep->active, src2, size); 1434 set_activeblock(ep, merge); 1435 1436 return add_join_conditional(ep, expr, phi1, phi2); 1437 } 1438 1439 static pseudo_t linearize_logical(struct entrypoint *ep, struct expression *expr) 1440 { 1441 struct expression *shortcut; 1442 1443 shortcut = alloc_const_expression(expr->pos, expr->op == SPECIAL_LOGICAL_OR); 1444 shortcut->ctype = expr->ctype; 1445 if (expr->op == SPECIAL_LOGICAL_OR) 1446 return linearize_conditional(ep, expr, expr->left, shortcut, expr->right); 1447 return linearize_conditional(ep, expr, expr->left, expr->right, shortcut); 1448 } 1449 1450 static pseudo_t linearize_compare(struct entrypoint *ep, struct expression *expr) 1451 { 1452 static const int cmpop[] = { 1453 ['>'] = OP_SET_GT, ['<'] = OP_SET_LT, 1454 [SPECIAL_EQUAL] = OP_SET_EQ, 1455 [SPECIAL_NOTEQUAL] = OP_SET_NE, 1456 [SPECIAL_GTE] = OP_SET_GE, 1457 [SPECIAL_LTE] = OP_SET_LE, 1458 [SPECIAL_UNSIGNED_LT] = OP_SET_B, 1459 [SPECIAL_UNSIGNED_GT] = OP_SET_A, 1460 [SPECIAL_UNSIGNED_LTE] = OP_SET_BE, 1461 [SPECIAL_UNSIGNED_GTE] = OP_SET_AE, 1462 }; 1463 1464 pseudo_t src1 = linearize_expression(ep, expr->left); 1465 pseudo_t src2 = linearize_expression(ep, expr->right); 1466 pseudo_t dst = add_binary_op(ep, expr->ctype, cmpop[expr->op], src1, src2); 1467 return dst; 1468 } 1469 1470 1471 pseudo_t linearize_cond_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false) 1472 { 1473 pseudo_t cond; 1474 1475 if (!expr || !bb_reachable(ep->active)) 1476 return VOID; 1477 1478 switch (expr->type) { 1479 1480 case EXPR_STRING: 1481 case EXPR_VALUE: 1482 add_goto(ep, expr->value ? bb_true : bb_false); 1483 return VOID; 1484 1485 case EXPR_FVALUE: 1486 add_goto(ep, expr->fvalue ? bb_true : bb_false); 1487 return VOID; 1488 1489 case EXPR_LOGICAL: 1490 linearize_logical_branch(ep, expr, bb_true, bb_false); 1491 return VOID; 1492 1493 case EXPR_COMPARE: 1494 cond = linearize_compare(ep, expr); 1495 add_branch(ep, expr, cond, bb_true, bb_false); 1496 break; 1497 1498 case EXPR_PREOP: 1499 if (expr->op == '!') 1500 return linearize_cond_branch(ep, expr->unop, bb_false, bb_true); 1501 /* fall through */ 1502 default: { 1503 cond = linearize_expression(ep, expr); 1504 add_branch(ep, expr, cond, bb_true, bb_false); 1505 1506 return VOID; 1507 } 1508 } 1509 return VOID; 1510 } 1511 1512 1513 1514 static pseudo_t linearize_logical_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false) 1515 { 1516 struct basic_block *next = alloc_basic_block(ep, expr->pos); 1517 1518 if (expr->op == SPECIAL_LOGICAL_OR) 1519 linearize_cond_branch(ep, expr->left, bb_true, next); 1520 else 1521 linearize_cond_branch(ep, expr->left, next, bb_false); 1522 set_activeblock(ep, next); 1523 linearize_cond_branch(ep, expr->right, bb_true, bb_false); 1524 return VOID; 1525 } 1526 1527 static pseudo_t linearize_cast(struct entrypoint *ep, struct expression *expr) 1528 { 1529 pseudo_t src; 1530 struct expression *orig = expr->cast_expression; 1531 1532 if (!orig) 1533 return VOID; 1534 1535 src = linearize_expression(ep, orig); 1536 return cast_pseudo(ep, src, orig->ctype, expr->ctype); 1537 } 1538 1539 static pseudo_t linearize_position(struct entrypoint *ep, struct expression *pos, struct access_data *ad) 1540 { 1541 struct expression *init_expr = pos->init_expr; 1542 1543 ad->offset = pos->init_offset; 1544 ad->source_type = base_type(init_expr->ctype); 1545 ad->result_type = init_expr->ctype; 1546 return linearize_initializer(ep, init_expr, ad); 1547 } 1548 1549 static pseudo_t linearize_initializer(struct entrypoint *ep, struct expression *initializer, struct access_data *ad) 1550 { 1551 switch (initializer->type) { 1552 case EXPR_INITIALIZER: { 1553 struct expression *expr; 1554 FOR_EACH_PTR(initializer->expr_list, expr) { 1555 linearize_initializer(ep, expr, ad); 1556 } END_FOR_EACH_PTR(expr); 1557 break; 1558 } 1559 case EXPR_POS: 1560 linearize_position(ep, initializer, ad); 1561 break; 1562 default: { 1563 pseudo_t value = linearize_expression(ep, initializer); 1564 ad->source_type = base_type(initializer->ctype); 1565 ad->result_type = initializer->ctype; 1566 linearize_store_gen(ep, value, ad); 1567 return value; 1568 } 1569 } 1570 1571 return VOID; 1572 } 1573 1574 static void linearize_argument(struct entrypoint *ep, struct symbol *arg, int nr) 1575 { 1576 struct access_data ad = { NULL, }; 1577 1578 ad.source_type = arg; 1579 ad.result_type = arg; 1580 ad.address = symbol_pseudo(ep, arg); 1581 linearize_store_gen(ep, argument_pseudo(ep, nr), &ad); 1582 finish_address_gen(ep, &ad); 1583 } 1584 1585 pseudo_t linearize_expression(struct entrypoint *ep, struct expression *expr) 1586 { 1587 if (!expr) 1588 return VOID; 1589 1590 current_pos = expr->pos; 1591 switch (expr->type) { 1592 case EXPR_SYMBOL: 1593 linearize_one_symbol(ep, expr->symbol); 1594 return add_symbol_address(ep, expr->symbol); 1595 1596 case EXPR_VALUE: 1597 return value_pseudo(expr->ctype, expr->value); 1598 1599 case EXPR_STRING: case EXPR_FVALUE: case EXPR_LABEL: 1600 return add_setval(ep, expr->ctype, expr); 1601 1602 case EXPR_STATEMENT: 1603 return linearize_statement(ep, expr->statement); 1604 1605 case EXPR_CALL: 1606 return linearize_call_expression(ep, expr); 1607 1608 case EXPR_BINOP: 1609 if (expr->op == SPECIAL_LOGICAL_AND || expr->op == SPECIAL_LOGICAL_OR) 1610 return linearize_binop_bool(ep, expr); 1611 return linearize_binop(ep, expr); 1612 1613 case EXPR_LOGICAL: 1614 return linearize_logical(ep, expr); 1615 1616 case EXPR_COMPARE: 1617 return linearize_compare(ep, expr); 1618 1619 case EXPR_SELECT: 1620 return linearize_select(ep, expr); 1621 1622 case EXPR_CONDITIONAL: 1623 if (!expr->cond_true) 1624 return linearize_short_conditional(ep, expr, expr->conditional, expr->cond_false); 1625 1626 return linearize_conditional(ep, expr, expr->conditional, 1627 expr->cond_true, expr->cond_false); 1628 1629 case EXPR_COMMA: 1630 linearize_expression(ep, expr->left); 1631 return linearize_expression(ep, expr->right); 1632 1633 case EXPR_ASSIGNMENT: 1634 return linearize_assignment(ep, expr); 1635 1636 case EXPR_PREOP: 1637 return linearize_preop(ep, expr); 1638 1639 case EXPR_POSTOP: 1640 return linearize_postop(ep, expr); 1641 1642 case EXPR_CAST: 1643 case EXPR_FORCE_CAST: 1644 case EXPR_IMPLIED_CAST: 1645 return linearize_cast(ep, expr); 1646 1647 case EXPR_SLICE: 1648 return linearize_slice(ep, expr); 1649 1650 case EXPR_INITIALIZER: 1651 case EXPR_POS: 1652 warning(expr->pos, "unexpected initializer expression (%d %d)", expr->type, expr->op); 1653 return VOID; 1654 default: 1655 warning(expr->pos, "unknown expression (%d %d)", expr->type, expr->op); 1656 return VOID; 1657 } 1658 return VOID; 1659 } 1660 1661 static pseudo_t linearize_one_symbol(struct entrypoint *ep, struct symbol *sym) 1662 { 1663 struct access_data ad = { NULL, }; 1664 pseudo_t value; 1665 1666 if (!sym || !sym->initializer || sym->initialized) 1667 return VOID; 1668 1669 /* We need to output these puppies some day too.. */ 1670 if (sym->ctype.modifiers & (MOD_STATIC | MOD_TOPLEVEL)) 1671 return VOID; 1672 1673 sym->initialized = 1; 1674 ad.address = symbol_pseudo(ep, sym); 1675 1676 if (sym->initializer && !is_scalar_type(sym)) { 1677 // default zero initialization [6.7.9.21] 1678 // FIXME: this init the whole aggregate while 1679 // only the existing fields need to be initialized. 1680 // FIXME: this init the whole aggregate even if 1681 // all fields arelater explicitely initialized. 1682 struct expression *expr = sym->initializer; 1683 ad.pos = expr->pos; 1684 ad.result_type = sym; 1685 ad.source_type = base_type(sym); 1686 ad.address = symbol_pseudo(ep, sym); 1687 linearize_store_gen(ep, value_pseudo(sym, 0), &ad); 1688 } 1689 1690 value = linearize_initializer(ep, sym->initializer, &ad); 1691 finish_address_gen(ep, &ad); 1692 return value; 1693 } 1694 1695 static pseudo_t linearize_compound_statement(struct entrypoint *ep, struct statement *stmt) 1696 { 1697 pseudo_t pseudo; 1698 struct statement *s; 1699 struct symbol *ret = stmt->ret; 1700 1701 pseudo = VOID; 1702 FOR_EACH_PTR(stmt->stmts, s) { 1703 pseudo = linearize_statement(ep, s); 1704 } END_FOR_EACH_PTR(s); 1705 1706 if (ret) { 1707 struct basic_block *bb = add_label(ep, ret); 1708 struct instruction *phi_node = first_instruction(bb->insns); 1709 1710 if (!phi_node) 1711 return pseudo; 1712 1713 if (pseudo_list_size(phi_node->phi_list)==1) { 1714 pseudo = first_pseudo(phi_node->phi_list); 1715 assert(pseudo->type == PSEUDO_PHI); 1716 return pseudo->def->src1; 1717 } 1718 return phi_node->target; 1719 } 1720 1721 return pseudo; 1722 } 1723 1724 static pseudo_t linearize_inlined_call(struct entrypoint *ep, struct statement *stmt) 1725 { 1726 struct instruction *insn = alloc_instruction(OP_INLINED_CALL, 0); 1727 struct statement *args = stmt->args; 1728 struct basic_block *bb; 1729 pseudo_t pseudo; 1730 1731 if (args) { 1732 struct symbol *sym; 1733 1734 concat_symbol_list(args->declaration, &ep->syms); 1735 FOR_EACH_PTR(args->declaration, sym) { 1736 pseudo_t value = linearize_one_symbol(ep, sym); 1737 use_pseudo(insn, value, add_pseudo(&insn->arguments, value)); 1738 } END_FOR_EACH_PTR(sym); 1739 } 1740 1741 insn->target = pseudo = linearize_compound_statement(ep, stmt); 1742 use_pseudo(insn, symbol_pseudo(ep, stmt->inline_fn), &insn->func); 1743 bb = ep->active; 1744 if (bb && !bb->insns) 1745 bb->pos = stmt->pos; 1746 add_one_insn(ep, insn); 1747 return pseudo; 1748 } 1749 1750 static pseudo_t linearize_context(struct entrypoint *ep, struct statement *stmt) 1751 { 1752 struct instruction *insn = alloc_instruction(OP_CONTEXT, 0); 1753 struct expression *expr = stmt->expression; 1754 int value = 0; 1755 1756 if (expr->type == EXPR_VALUE) 1757 value = expr->value; 1758 1759 insn->increment = value; 1760 insn->context_expr = stmt->context; 1761 add_one_insn(ep, insn); 1762 return VOID; 1763 } 1764 1765 static pseudo_t linearize_range(struct entrypoint *ep, struct statement *stmt) 1766 { 1767 struct instruction *insn = alloc_instruction(OP_RANGE, 0); 1768 1769 use_pseudo(insn, linearize_expression(ep, stmt->range_expression), &insn->src1); 1770 use_pseudo(insn, linearize_expression(ep, stmt->range_low), &insn->src2); 1771 use_pseudo(insn, linearize_expression(ep, stmt->range_high), &insn->src3); 1772 add_one_insn(ep, insn); 1773 return VOID; 1774 } 1775 1776 ALLOCATOR(asm_rules, "asm rules"); 1777 ALLOCATOR(asm_constraint, "asm constraints"); 1778 1779 static void add_asm_input(struct entrypoint *ep, struct instruction *insn, struct expression *expr, 1780 const char *constraint, const struct ident *ident) 1781 { 1782 pseudo_t pseudo = linearize_expression(ep, expr); 1783 struct asm_constraint *rule = __alloc_asm_constraint(0); 1784 1785 rule->ident = ident; 1786 rule->constraint = constraint; 1787 use_pseudo(insn, pseudo, &rule->pseudo); 1788 add_ptr_list(&insn->asm_rules->inputs, rule); 1789 } 1790 1791 static void add_asm_output(struct entrypoint *ep, struct instruction *insn, struct expression *expr, 1792 const char *constraint, const struct ident *ident) 1793 { 1794 struct access_data ad = { NULL, }; 1795 pseudo_t pseudo = alloc_pseudo(insn); 1796 struct asm_constraint *rule; 1797 1798 if (!expr || !linearize_address_gen(ep, expr, &ad)) 1799 return; 1800 linearize_store_gen(ep, pseudo, &ad); 1801 finish_address_gen(ep, &ad); 1802 rule = __alloc_asm_constraint(0); 1803 rule->ident = ident; 1804 rule->constraint = constraint; 1805 use_pseudo(insn, pseudo, &rule->pseudo); 1806 add_ptr_list(&insn->asm_rules->outputs, rule); 1807 } 1808 1809 static pseudo_t linearize_asm_statement(struct entrypoint *ep, struct statement *stmt) 1810 { 1811 int state; 1812 struct expression *expr; 1813 struct instruction *insn; 1814 struct asm_rules *rules; 1815 const char *constraint; 1816 struct ident *ident; 1817 1818 insn = alloc_instruction(OP_ASM, 0); 1819 expr = stmt->asm_string; 1820 if (!expr || expr->type != EXPR_STRING) { 1821 warning(stmt->pos, "expected string in inline asm"); 1822 return VOID; 1823 } 1824 insn->string = expr->string->data; 1825 1826 rules = __alloc_asm_rules(0); 1827 insn->asm_rules = rules; 1828 1829 /* Gather the inputs.. */ 1830 state = 0; 1831 ident = NULL; 1832 constraint = NULL; 1833 FOR_EACH_PTR(stmt->asm_inputs, expr) { 1834 switch (state) { 1835 case 0: /* Identifier */ 1836 state = 1; 1837 ident = (struct ident *)expr; 1838 continue; 1839 1840 case 1: /* Constraint */ 1841 state = 2; 1842 constraint = expr ? expr->string->data : ""; 1843 continue; 1844 1845 case 2: /* Expression */ 1846 state = 0; 1847 add_asm_input(ep, insn, expr, constraint, ident); 1848 } 1849 } END_FOR_EACH_PTR(expr); 1850 1851 add_one_insn(ep, insn); 1852 1853 /* Assign the outputs */ 1854 state = 0; 1855 ident = NULL; 1856 constraint = NULL; 1857 FOR_EACH_PTR(stmt->asm_outputs, expr) { 1858 switch (state) { 1859 case 0: /* Identifier */ 1860 state = 1; 1861 ident = (struct ident *)expr; 1862 continue; 1863 1864 case 1: /* Constraint */ 1865 state = 2; 1866 constraint = expr ? expr->string->data : ""; 1867 continue; 1868 1869 case 2: 1870 state = 0; 1871 add_asm_output(ep, insn, expr, constraint, ident); 1872 } 1873 } END_FOR_EACH_PTR(expr); 1874 1875 return VOID; 1876 } 1877 1878 static int multijmp_cmp(const void *_a, const void *_b) 1879 { 1880 const struct multijmp *a = _a; 1881 const struct multijmp *b = _b; 1882 1883 // "default" case? 1884 if (a->begin > a->end) { 1885 if (b->begin > b->end) 1886 return 0; 1887 return 1; 1888 } 1889 if (b->begin > b->end) 1890 return -1; 1891 if (a->begin == b->begin) { 1892 if (a->end == b->end) 1893 return 0; 1894 return (a->end < b->end) ? -1 : 1; 1895 } 1896 return a->begin < b->begin ? -1 : 1; 1897 } 1898 1899 static void sort_switch_cases(struct instruction *insn) 1900 { 1901 sort_list((struct ptr_list **)&insn->multijmp_list, multijmp_cmp); 1902 } 1903 1904 static pseudo_t linearize_declaration(struct entrypoint *ep, struct statement *stmt) 1905 { 1906 struct symbol *sym; 1907 1908 concat_symbol_list(stmt->declaration, &ep->syms); 1909 1910 FOR_EACH_PTR(stmt->declaration, sym) { 1911 linearize_one_symbol(ep, sym); 1912 } END_FOR_EACH_PTR(sym); 1913 return VOID; 1914 } 1915 1916 static pseudo_t linearize_return(struct entrypoint *ep, struct statement *stmt) 1917 { 1918 struct expression *expr = stmt->expression; 1919 struct basic_block *bb_return = get_bound_block(ep, stmt->ret_target); 1920 struct basic_block *active; 1921 pseudo_t src = linearize_expression(ep, expr); 1922 active = ep->active; 1923 if (active && src != VOID) { 1924 struct instruction *phi_node = first_instruction(bb_return->insns); 1925 pseudo_t phi; 1926 if (!phi_node) { 1927 phi_node = alloc_typed_instruction(OP_PHI, expr->ctype); 1928 phi_node->target = alloc_pseudo(phi_node); 1929 phi_node->bb = bb_return; 1930 add_instruction(&bb_return->insns, phi_node); 1931 } 1932 phi = alloc_phi(active, src, type_size(expr->ctype)); 1933 phi->ident = &return_ident; 1934 use_pseudo(phi_node, phi, add_pseudo(&phi_node->phi_list, phi)); 1935 } 1936 add_goto(ep, bb_return); 1937 return VOID; 1938 } 1939 1940 static pseudo_t linearize_switch(struct entrypoint *ep, struct statement *stmt) 1941 { 1942 struct symbol *sym; 1943 struct instruction *switch_ins; 1944 struct basic_block *switch_end = alloc_basic_block(ep, stmt->pos); 1945 struct basic_block *active, *default_case; 1946 struct multijmp *jmp; 1947 pseudo_t pseudo; 1948 1949 pseudo = linearize_expression(ep, stmt->switch_expression); 1950 1951 active = ep->active; 1952 if (!bb_reachable(active)) 1953 return VOID; 1954 1955 switch_ins = alloc_instruction(OP_SWITCH, 0); 1956 use_pseudo(switch_ins, pseudo, &switch_ins->cond); 1957 add_one_insn(ep, switch_ins); 1958 finish_block(ep); 1959 1960 default_case = NULL; 1961 FOR_EACH_PTR(stmt->switch_case->symbol_list, sym) { 1962 struct statement *case_stmt = sym->stmt; 1963 struct basic_block *bb_case = get_bound_block(ep, sym); 1964 1965 if (!case_stmt->case_expression) { 1966 default_case = bb_case; 1967 continue; 1968 } else { 1969 int begin, end; 1970 1971 begin = end = case_stmt->case_expression->value; 1972 if (case_stmt->case_to) 1973 end = case_stmt->case_to->value; 1974 if (begin > end) 1975 jmp = alloc_multijmp(bb_case, end, begin); 1976 else 1977 jmp = alloc_multijmp(bb_case, begin, end); 1978 1979 } 1980 add_multijmp(&switch_ins->multijmp_list, jmp); 1981 add_bb(&bb_case->parents, active); 1982 add_bb(&active->children, bb_case); 1983 } END_FOR_EACH_PTR(sym); 1984 1985 bind_label(stmt->switch_break, switch_end, stmt->pos); 1986 1987 /* And linearize the actual statement */ 1988 linearize_statement(ep, stmt->switch_statement); 1989 set_activeblock(ep, switch_end); 1990 1991 if (!default_case) 1992 default_case = switch_end; 1993 1994 jmp = alloc_multijmp(default_case, 1, 0); 1995 add_multijmp(&switch_ins->multijmp_list, jmp); 1996 add_bb(&default_case->parents, active); 1997 add_bb(&active->children, default_case); 1998 sort_switch_cases(switch_ins); 1999 2000 return VOID; 2001 } 2002 2003 static pseudo_t linearize_iterator(struct entrypoint *ep, struct statement *stmt) 2004 { 2005 struct statement *pre_statement = stmt->iterator_pre_statement; 2006 struct expression *pre_condition = stmt->iterator_pre_condition; 2007 struct statement *statement = stmt->iterator_statement; 2008 struct statement *post_statement = stmt->iterator_post_statement; 2009 struct expression *post_condition = stmt->iterator_post_condition; 2010 struct basic_block *loop_top, *loop_body, *loop_continue, *loop_end; 2011 struct symbol *sym; 2012 2013 FOR_EACH_PTR(stmt->iterator_syms, sym) { 2014 linearize_one_symbol(ep, sym); 2015 } END_FOR_EACH_PTR(sym); 2016 concat_symbol_list(stmt->iterator_syms, &ep->syms); 2017 linearize_statement(ep, pre_statement); 2018 2019 loop_body = loop_top = alloc_basic_block(ep, stmt->pos); 2020 loop_continue = alloc_basic_block(ep, stmt->pos); 2021 loop_end = alloc_basic_block(ep, stmt->pos); 2022 2023 /* An empty post-condition means that it's the same as the pre-condition */ 2024 if (!post_condition) { 2025 loop_top = alloc_basic_block(ep, stmt->pos); 2026 set_activeblock(ep, loop_top); 2027 } 2028 2029 if (pre_condition) 2030 linearize_cond_branch(ep, pre_condition, loop_body, loop_end); 2031 2032 bind_label(stmt->iterator_continue, loop_continue, stmt->pos); 2033 bind_label(stmt->iterator_break, loop_end, stmt->pos); 2034 2035 set_activeblock(ep, loop_body); 2036 linearize_statement(ep, statement); 2037 add_goto(ep, loop_continue); 2038 2039 set_activeblock(ep, loop_continue); 2040 linearize_statement(ep, post_statement); 2041 if (!post_condition) 2042 add_goto(ep, loop_top); 2043 else 2044 linearize_cond_branch(ep, post_condition, loop_top, loop_end); 2045 set_activeblock(ep, loop_end); 2046 2047 return VOID; 2048 } 2049 2050 pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt) 2051 { 2052 struct basic_block *bb; 2053 2054 if (!stmt) 2055 return VOID; 2056 2057 bb = ep->active; 2058 if (bb && !bb->insns) 2059 bb->pos = stmt->pos; 2060 current_pos = stmt->pos; 2061 2062 switch (stmt->type) { 2063 case STMT_NONE: 2064 break; 2065 2066 case STMT_DECLARATION: 2067 return linearize_declaration(ep, stmt); 2068 2069 case STMT_CONTEXT: 2070 return linearize_context(ep, stmt); 2071 2072 case STMT_RANGE: 2073 return linearize_range(ep, stmt); 2074 2075 case STMT_EXPRESSION: 2076 return linearize_expression(ep, stmt->expression); 2077 2078 case STMT_ASM: 2079 return linearize_asm_statement(ep, stmt); 2080 2081 case STMT_RETURN: 2082 return linearize_return(ep, stmt); 2083 2084 case STMT_CASE: { 2085 add_label(ep, stmt->case_label); 2086 linearize_statement(ep, stmt->case_statement); 2087 break; 2088 } 2089 2090 case STMT_LABEL: { 2091 struct symbol *label = stmt->label_identifier; 2092 2093 if (label->used) { 2094 add_label(ep, label); 2095 } 2096 return linearize_statement(ep, stmt->label_statement); 2097 } 2098 2099 case STMT_GOTO: { 2100 struct symbol *sym; 2101 struct expression *expr; 2102 struct instruction *goto_ins; 2103 struct basic_block *active; 2104 pseudo_t pseudo; 2105 2106 active = ep->active; 2107 if (!bb_reachable(active)) 2108 break; 2109 2110 if (stmt->goto_label) { 2111 add_goto(ep, get_bound_block(ep, stmt->goto_label)); 2112 break; 2113 } 2114 2115 expr = stmt->goto_expression; 2116 if (!expr) 2117 break; 2118 2119 /* This can happen as part of simplification */ 2120 if (expr->type == EXPR_LABEL) { 2121 add_goto(ep, get_bound_block(ep, expr->label_symbol)); 2122 break; 2123 } 2124 2125 pseudo = linearize_expression(ep, expr); 2126 goto_ins = alloc_instruction(OP_COMPUTEDGOTO, 0); 2127 use_pseudo(goto_ins, pseudo, &goto_ins->target); 2128 add_one_insn(ep, goto_ins); 2129 2130 FOR_EACH_PTR(stmt->target_list, sym) { 2131 struct basic_block *bb_computed = get_bound_block(ep, sym); 2132 struct multijmp *jmp = alloc_multijmp(bb_computed, 1, 0); 2133 add_multijmp(&goto_ins->multijmp_list, jmp); 2134 add_bb(&bb_computed->parents, ep->active); 2135 add_bb(&active->children, bb_computed); 2136 } END_FOR_EACH_PTR(sym); 2137 2138 finish_block(ep); 2139 break; 2140 } 2141 2142 case STMT_COMPOUND: 2143 if (stmt->inline_fn) 2144 return linearize_inlined_call(ep, stmt); 2145 return linearize_compound_statement(ep, stmt); 2146 2147 /* 2148 * This could take 'likely/unlikely' into account, and 2149 * switch the arms around appropriately.. 2150 */ 2151 case STMT_IF: { 2152 struct basic_block *bb_true, *bb_false, *endif; 2153 struct expression *cond = stmt->if_conditional; 2154 2155 bb_true = alloc_basic_block(ep, stmt->pos); 2156 bb_false = endif = alloc_basic_block(ep, stmt->pos); 2157 2158 linearize_cond_branch(ep, cond, bb_true, bb_false); 2159 2160 set_activeblock(ep, bb_true); 2161 linearize_statement(ep, stmt->if_true); 2162 2163 if (stmt->if_false) { 2164 endif = alloc_basic_block(ep, stmt->pos); 2165 add_goto(ep, endif); 2166 set_activeblock(ep, bb_false); 2167 linearize_statement(ep, stmt->if_false); 2168 } 2169 set_activeblock(ep, endif); 2170 break; 2171 } 2172 2173 case STMT_SWITCH: 2174 return linearize_switch(ep, stmt); 2175 2176 case STMT_ITERATOR: 2177 return linearize_iterator(ep, stmt); 2178 2179 default: 2180 break; 2181 } 2182 return VOID; 2183 } 2184 2185 static struct entrypoint *linearize_fn(struct symbol *sym, struct symbol *base_type) 2186 { 2187 struct entrypoint *ep; 2188 struct basic_block *bb; 2189 struct symbol *arg; 2190 struct instruction *entry; 2191 pseudo_t result; 2192 int i; 2193 2194 if (!base_type->stmt) 2195 return NULL; 2196 2197 ep = alloc_entrypoint(); 2198 bb = alloc_basic_block(ep, sym->pos); 2199 2200 ep->name = sym; 2201 sym->ep = ep; 2202 set_activeblock(ep, bb); 2203 2204 entry = alloc_instruction(OP_ENTRY, 0); 2205 add_one_insn(ep, entry); 2206 ep->entry = entry; 2207 2208 concat_symbol_list(base_type->arguments, &ep->syms); 2209 2210 /* FIXME!! We should do something else about varargs.. */ 2211 i = 0; 2212 FOR_EACH_PTR(base_type->arguments, arg) { 2213 linearize_argument(ep, arg, ++i); 2214 } END_FOR_EACH_PTR(arg); 2215 2216 result = linearize_statement(ep, base_type->stmt); 2217 if (bb_reachable(ep->active) && !bb_terminated(ep->active)) { 2218 struct symbol *ret_type = base_type->ctype.base_type; 2219 struct instruction *insn = alloc_typed_instruction(OP_RET, ret_type); 2220 2221 if (type_size(ret_type) > 0) 2222 use_pseudo(insn, result, &insn->src); 2223 add_one_insn(ep, insn); 2224 } 2225 2226 if (fdump_linearize) { 2227 if (fdump_linearize == 2) 2228 return ep; 2229 show_entry(ep); 2230 } 2231 2232 /* 2233 * Do trivial flow simplification - branches to 2234 * branches, kill dead basicblocks etc 2235 */ 2236 kill_unreachable_bbs(ep); 2237 2238 /* 2239 * Turn symbols into pseudos 2240 */ 2241 simplify_symbol_usage(ep); 2242 2243 repeat: 2244 /* 2245 * Remove trivial instructions, and try to CSE 2246 * the rest. 2247 */ 2248 do { 2249 cleanup_and_cse(ep); 2250 pack_basic_blocks(ep); 2251 } while (repeat_phase & REPEAT_CSE); 2252 2253 kill_unreachable_bbs(ep); 2254 vrfy_flow(ep); 2255 2256 /* Cleanup */ 2257 clear_symbol_pseudos(ep); 2258 2259 /* And track pseudo register usage */ 2260 track_pseudo_liveness(ep); 2261 2262 /* 2263 * Some flow optimizations can only effectively 2264 * be done when we've done liveness analysis. But 2265 * if they trigger, we need to start all over 2266 * again 2267 */ 2268 if (simplify_flow(ep)) { 2269 clear_liveness(ep); 2270 goto repeat; 2271 } 2272 2273 /* Finally, add deathnotes to pseudos now that we have them */ 2274 if (dbg_dead) 2275 track_pseudo_death(ep); 2276 2277 return ep; 2278 } 2279 2280 struct entrypoint *linearize_symbol(struct symbol *sym) 2281 { 2282 struct symbol *base_type; 2283 2284 if (!sym) 2285 return NULL; 2286 current_pos = sym->pos; 2287 base_type = sym->ctype.base_type; 2288 if (!base_type) 2289 return NULL; 2290 if (base_type->type == SYM_FN) 2291 return linearize_fn(sym, base_type); 2292 return NULL; 2293 } 2294