linearize.c

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