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, "%d", 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 (!linearize_address_gen(ep, target, &ad))
1145                 return VOID;
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;
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         context_diff = 0;
1193         if (fn->ctype) {
1194                 int in = fn->ctype->ctype.in_context;
1195                 int out = fn->ctype->ctype.out_context;
1196                 if (in < 0 || out < 0)
1197                         in = out = 0;
1198                 context_diff = out - in;
1199         }
1200
1201         if (fn->type == EXPR_PREOP) {
1202                 if (fn->unop->type == EXPR_SYMBOL) {
1203                         struct symbol *sym = fn->unop->symbol;
1204                         if (sym->ctype.base_type->type == SYM_FN)
1205                                 fn = fn->unop;
1206                 }
1207         }
1208         if (fn->type == EXPR_SYMBOL) {
1209                 call = symbol_pseudo(ep, fn->symbol);
1210         } else {
1211                 call = linearize_expression(ep, fn);
1212         }
1213         use_pseudo(call, &insn->func);
1214         retval = VOID;
1215         if (expr->ctype != &void_ctype)
1216                 retval = alloc_pseudo(insn);
1217         insn->target = retval;
1218         add_one_insn(ep, insn);
1219
1220         if (context_diff) {
1221                 insn = alloc_instruction(OP_CONTEXT, 0);
1222                 insn->increment = context_diff;
1223                 add_one_insn(ep, insn);
1224         }
1225
1226         return retval;
1227 }
1228
1229 static pseudo_t linearize_binop(struct entrypoint *ep, struct expression *expr)
1230 {
1231         pseudo_t src1, src2, dst;
1232         static const int opcode[] = {
1233                 ['+'] = OP_ADD, ['-'] = OP_SUB,
1234                 ['*'] = OP_MULU, ['/'] = OP_DIVU,
1235                 ['%'] = OP_MODU, ['&'] = OP_AND,
1236                 ['|'] = OP_OR,  ['^'] = OP_XOR,
1237                 [SPECIAL_LEFTSHIFT] = OP_SHL,
1238                 [SPECIAL_RIGHTSHIFT] = OP_LSR,
1239                 [SPECIAL_LOGICAL_AND] = OP_AND_BOOL,
1240                 [SPECIAL_LOGICAL_OR] = OP_OR_BOOL,
1241         };
1242         int op;
1243
1244         src1 = linearize_expression(ep, expr->left);
1245         src2 = linearize_expression(ep, expr->right);
1246         op = opcode_sign(opcode[expr->op], expr->ctype);
1247         dst = add_binary_op(ep, expr->ctype, op, src1, src2);
1248         return dst;
1249 }
1250
1251 static pseudo_t linearize_logical_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false);
1252
1253 pseudo_t linearize_cond_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false);
1254
1255 static pseudo_t linearize_select(struct entrypoint *ep, struct expression *expr)
1256 {
1257         pseudo_t cond, true, false, res;
1258         struct instruction *insn;
1259
1260         true = linearize_expression(ep, expr->cond_true);
1261         false = linearize_expression(ep, expr->cond_false);
1262         cond = linearize_expression(ep, expr->conditional);
1263
1264         insn = alloc_typed_instruction(OP_SEL, expr->ctype);
1265         if (!expr->cond_true)
1266                 true = cond;
1267         use_pseudo(cond, &insn->src1);
1268         use_pseudo(true, &insn->src2);
1269         use_pseudo(false, &insn->src3);
1270
1271         res = alloc_pseudo(insn);
1272         insn->target = res;
1273         add_one_insn(ep, insn);
1274         return res;
1275 }
1276
1277 static pseudo_t add_join_conditional(struct entrypoint *ep, struct expression *expr,
1278                                      pseudo_t phi1, pseudo_t phi2)
1279 {
1280         pseudo_t target;
1281         struct instruction *phi_node;
1282
1283         if (phi1 == VOID)
1284                 return phi2;
1285         if (phi2 == VOID)
1286                 return phi1;
1287
1288         phi_node = alloc_typed_instruction(OP_PHI, expr->ctype);
1289         use_pseudo(phi1, add_pseudo(&phi_node->phi_list, phi1));
1290         use_pseudo(phi2, add_pseudo(&phi_node->phi_list, phi2));
1291         phi_node->target = target = alloc_pseudo(phi_node);
1292         add_one_insn(ep, phi_node);
1293         return target;
1294 }
1295
1296 static pseudo_t linearize_short_conditional(struct entrypoint *ep, struct expression *expr,
1297                                             struct expression *cond,
1298                                             struct expression *expr_false)
1299 {
1300         pseudo_t src1, src2;
1301         struct basic_block *bb_false = alloc_basic_block(ep, expr_false->pos);
1302         struct basic_block *merge = alloc_basic_block(ep, expr->pos);
1303         pseudo_t phi1, phi2;
1304         int size = type_size(expr->ctype);
1305
1306         src1 = linearize_expression(ep, cond);
1307         phi1 = alloc_phi(ep->active, src1, size);
1308         add_branch(ep, expr, src1, merge, bb_false);
1309
1310         set_activeblock(ep, bb_false);
1311         src2 = linearize_expression(ep, expr_false);
1312         phi2 = alloc_phi(ep->active, src2, size);
1313         set_activeblock(ep, merge);
1314
1315         return add_join_conditional(ep, expr, phi1, phi2);
1316 }
1317
1318 static pseudo_t linearize_conditional(struct entrypoint *ep, struct expression *expr,
1319                                       struct expression *cond,
1320                                       struct expression *expr_true,
1321                                       struct expression *expr_false)
1322 {
1323         pseudo_t src1, src2;
1324         pseudo_t phi1, phi2;
1325         struct basic_block *bb_true = alloc_basic_block(ep, expr_true->pos);
1326         struct basic_block *bb_false = alloc_basic_block(ep, expr_false->pos);
1327         struct basic_block *merge = alloc_basic_block(ep, expr->pos);
1328         int size = type_size(expr->ctype);
1329
1330         linearize_cond_branch(ep, cond, bb_true, bb_false);
1331
1332         set_activeblock(ep, bb_true);
1333         src1 = linearize_expression(ep, expr_true);
1334         phi1 = alloc_phi(ep->active, src1, size);
1335         add_goto(ep, merge);
1336
1337         set_activeblock(ep, bb_false);
1338         src2 = linearize_expression(ep, expr_false);
1339         phi2 = alloc_phi(ep->active, src2, size);
1340         set_activeblock(ep, merge);
1341
1342         return add_join_conditional(ep, expr, phi1, phi2);
1343 }
1344
1345 static pseudo_t linearize_logical(struct entrypoint *ep, struct expression *expr)
1346 {
1347         struct expression *shortcut;
1348
1349         shortcut = alloc_const_expression(expr->pos, expr->op == SPECIAL_LOGICAL_OR);
1350         shortcut->ctype = expr->ctype;
1351         return  linearize_conditional(ep, expr, expr->left, shortcut, expr->right);
1352 }
1353
1354 static pseudo_t linearize_compare(struct entrypoint *ep, struct expression *expr)
1355 {
1356         static const int cmpop[] = {
1357                 ['>'] = OP_SET_GT, ['<'] = OP_SET_LT,
1358                 [SPECIAL_EQUAL] = OP_SET_EQ,
1359                 [SPECIAL_NOTEQUAL] = OP_SET_NE,
1360                 [SPECIAL_GTE] = OP_SET_GE,
1361                 [SPECIAL_LTE] = OP_SET_LE,
1362                 [SPECIAL_UNSIGNED_LT] = OP_SET_B,
1363                 [SPECIAL_UNSIGNED_GT] = OP_SET_A,
1364                 [SPECIAL_UNSIGNED_LTE] = OP_SET_BE,
1365                 [SPECIAL_UNSIGNED_GTE] = OP_SET_AE,
1366         };
1367
1368         pseudo_t src1 = linearize_expression(ep, expr->left);
1369         pseudo_t src2 = linearize_expression(ep, expr->right);
1370         pseudo_t dst = add_binary_op(ep, expr->left->ctype, cmpop[expr->op], src1, src2);
1371         return dst;
1372 }
1373
1374
1375 pseudo_t linearize_cond_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false)
1376 {
1377         pseudo_t cond;
1378
1379         if (!expr || !bb_reachable(ep->active))
1380                 return VOID;
1381
1382         switch (expr->type) {
1383
1384         case EXPR_STRING:
1385         case EXPR_VALUE:
1386                 add_goto(ep, expr->value ? bb_true : bb_false);
1387                 return VOID;
1388
1389         case EXPR_FVALUE:
1390                 add_goto(ep, expr->fvalue ? bb_true : bb_false);
1391                 return VOID;
1392
1393         case EXPR_LOGICAL:
1394                 linearize_logical_branch(ep, expr, bb_true, bb_false);
1395                 return VOID;
1396
1397         case EXPR_COMPARE:
1398                 cond = linearize_compare(ep, expr);
1399                 add_branch(ep, expr, cond, bb_true, bb_false);
1400                 break;
1401
1402         case EXPR_PREOP:
1403                 if (expr->op == '!')
1404                         return linearize_cond_branch(ep, expr->unop, bb_false, bb_true);
1405                 /* fall through */
1406         default: {
1407                 cond = linearize_expression(ep, expr);
1408                 add_branch(ep, expr, cond, bb_true, bb_false);
1409
1410                 return VOID;
1411         }
1412         }
1413         return VOID;
1414 }
1415
1416
1417
1418 static pseudo_t linearize_logical_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false)
1419 {
1420         struct basic_block *next = alloc_basic_block(ep, expr->pos);
1421
1422         if (expr->op == SPECIAL_LOGICAL_OR)
1423                 linearize_cond_branch(ep, expr->left, bb_true, next);
1424         else
1425                 linearize_cond_branch(ep, expr->left, next, bb_false);
1426         set_activeblock(ep, next);
1427         linearize_cond_branch(ep, expr->right, bb_true, bb_false);
1428         return VOID;
1429 }
1430
1431 pseudo_t linearize_cast(struct entrypoint *ep, struct expression *expr)
1432 {
1433         pseudo_t src;
1434         struct expression *orig = expr->cast_expression;
1435
1436         src = linearize_expression(ep, orig);
1437         return cast_pseudo(ep, src, orig->ctype, expr->ctype);
1438 }
1439
1440 pseudo_t linearize_position(struct entrypoint *ep, struct expression *pos, struct access_data *ad)
1441 {
1442         struct expression *init_expr = pos->init_expr;
1443
1444         ad->offset = pos->init_offset;
1445         ad->source_type = base_type(init_expr->ctype);
1446         ad->result_type = init_expr->ctype;
1447         return linearize_initializer(ep, init_expr, ad);
1448 }
1449
1450 pseudo_t linearize_initializer(struct entrypoint *ep, struct expression *initializer, struct access_data *ad)
1451 {
1452         switch (initializer->type) {
1453         case EXPR_INITIALIZER: {
1454                 struct expression *expr;
1455                 FOR_EACH_PTR(initializer->expr_list, expr) {
1456                         linearize_initializer(ep, expr, ad);
1457                 } END_FOR_EACH_PTR(expr);
1458                 break;
1459         }
1460         case EXPR_POS:
1461                 linearize_position(ep, initializer, ad);
1462                 break;
1463         default: {
1464                 pseudo_t value = linearize_expression(ep, initializer);
1465                 ad->source_type = base_type(initializer->ctype);
1466                 ad->result_type = initializer->ctype;
1467                 linearize_store_gen(ep, value, ad);
1468         }
1469         }
1470
1471         return VOID;
1472 }
1473
1474 void linearize_argument(struct entrypoint *ep, struct symbol *arg, int nr)
1475 {
1476         struct access_data ad = { NULL, };
1477
1478         ad.source_type = arg;
1479         ad.result_type = arg;
1480         ad.address = symbol_pseudo(ep, arg);
1481         linearize_store_gen(ep, argument_pseudo(ep, nr), &ad);
1482         finish_address_gen(ep, &ad);
1483 }
1484
1485 pseudo_t linearize_expression(struct entrypoint *ep, struct expression *expr)
1486 {
1487         if (!expr)
1488                 return VOID;
1489
1490         current_pos = expr->pos;
1491         switch (expr->type) {
1492         case EXPR_SYMBOL:
1493                 linearize_one_symbol(ep, expr->symbol);
1494                 return add_symbol_address(ep, expr->symbol);
1495
1496         case EXPR_VALUE:
1497                 return value_pseudo(expr->value);
1498
1499         case EXPR_STRING: case EXPR_FVALUE: case EXPR_LABEL:
1500                 return add_setval(ep, expr->ctype, expr);
1501
1502         case EXPR_STATEMENT:
1503                 return linearize_statement(ep, expr->statement);
1504
1505         case EXPR_CALL:
1506                 return linearize_call_expression(ep, expr);
1507
1508         case EXPR_BINOP:
1509                 return linearize_binop(ep, expr);
1510
1511         case EXPR_LOGICAL:
1512                 return linearize_logical(ep, expr);
1513
1514         case EXPR_COMPARE:
1515                 return  linearize_compare(ep, expr);
1516
1517         case EXPR_SELECT:
1518                 return  linearize_select(ep, expr);
1519
1520         case EXPR_CONDITIONAL:
1521                 if (!expr->cond_true)
1522                         return linearize_short_conditional(ep, expr, expr->conditional, expr->cond_false);
1523
1524                 return  linearize_conditional(ep, expr, expr->conditional,
1525                                               expr->cond_true, expr->cond_false);
1526
1527         case EXPR_COMMA:
1528                 linearize_expression(ep, expr->left);
1529                 return linearize_expression(ep, expr->right);
1530
1531         case EXPR_ASSIGNMENT:
1532                 return linearize_assignment(ep, expr);
1533
1534         case EXPR_PREOP:
1535                 return linearize_preop(ep, expr);
1536
1537         case EXPR_POSTOP:
1538                 return linearize_postop(ep, expr);
1539
1540         case EXPR_CAST:
1541         case EXPR_IMPLIED_CAST:
1542                 return linearize_cast(ep, expr);
1543
1544         case EXPR_SLICE:
1545                 return linearize_slice(ep, expr);
1546
1547         case EXPR_INITIALIZER:
1548         case EXPR_POS:
1549                 warning(expr->pos, "unexpected initializer expression (%d %d)", expr->type, expr->op);
1550                 return VOID;
1551         default:
1552                 warning(expr->pos, "unknown expression (%d %d)", expr->type, expr->op);
1553                 return VOID;
1554         }
1555         return VOID;
1556 }
1557
1558 static void linearize_one_symbol(struct entrypoint *ep, struct symbol *sym)
1559 {
1560         struct access_data ad = { NULL, };
1561
1562         if (!sym || !sym->initializer || sym->initialized)
1563                 return;
1564
1565         /* We need to output these puppies some day too.. */
1566         if (sym->ctype.modifiers & (MOD_STATIC | MOD_TOPLEVEL))
1567                 return;
1568
1569         sym->initialized = 1;
1570         ad.address = symbol_pseudo(ep, sym);
1571         linearize_initializer(ep, sym->initializer, &ad);
1572         finish_address_gen(ep, &ad);
1573 }
1574
1575 static pseudo_t linearize_compound_statement(struct entrypoint *ep, struct statement *stmt)
1576 {
1577         pseudo_t pseudo;
1578         struct statement *s;
1579         struct symbol *sym;
1580         struct symbol *ret = stmt->ret;
1581
1582         concat_symbol_list(stmt->syms, &ep->syms);
1583
1584         FOR_EACH_PTR(stmt->syms, sym) {
1585                 linearize_one_symbol(ep, sym);
1586         } END_FOR_EACH_PTR(sym);
1587
1588         pseudo = VOID;
1589         FOR_EACH_PTR(stmt->stmts, s) {
1590                 pseudo = linearize_statement(ep, s);
1591         } END_FOR_EACH_PTR(s);
1592
1593         if (ret) {
1594                 struct basic_block *bb = add_label(ep, ret);
1595                 struct instruction *phi_node = first_instruction(bb->insns);
1596
1597                 if (!phi_node)
1598                         return pseudo;
1599
1600                 if (pseudo_list_size(phi_node->phi_list)==1) {
1601                         pseudo = first_pseudo(phi_node->phi_list);
1602                         assert(pseudo->type == PSEUDO_PHI);
1603                         return pseudo->def->src1;
1604                 }
1605                 return phi_node->target;
1606         }
1607         return pseudo;
1608 }
1609
1610 pseudo_t linearize_context(struct entrypoint *ep, struct statement *stmt)
1611 {
1612         struct instruction *insn = alloc_instruction(OP_CONTEXT, 0);
1613         struct expression *expr = stmt->expression;
1614         int value = 0;
1615
1616         if (expr->type == EXPR_VALUE)
1617                 value = expr->value;
1618
1619         insn->increment = value;
1620         add_one_insn(ep, insn);
1621         return VOID;
1622 }
1623
1624 pseudo_t linearize_range(struct entrypoint *ep, struct statement *stmt)
1625 {
1626         struct instruction *insn = alloc_instruction(OP_RANGE, 0);
1627
1628         use_pseudo(linearize_expression(ep, stmt->range_expression), &insn->src1);
1629         use_pseudo(linearize_expression(ep, stmt->range_low), &insn->src2);
1630         use_pseudo(linearize_expression(ep, stmt->range_high), &insn->src3);
1631         add_one_insn(ep, insn);
1632         return VOID;
1633 }
1634
1635 ALLOCATOR(asm_rules, "asm rules");
1636 ALLOCATOR(asm_constraint, "asm constraints");
1637
1638 static void add_asm_input(struct entrypoint *ep, struct instruction *insn, struct expression *expr,
1639         const char *constraint, const struct ident *ident)
1640 {
1641         pseudo_t pseudo = linearize_expression(ep, expr);
1642         struct asm_constraint *rule = __alloc_asm_constraint(0);
1643
1644         rule->ident = ident;
1645         rule->constraint = constraint;
1646         use_pseudo(pseudo, &rule->pseudo);
1647         add_ptr_list(&insn->asm_rules->inputs, rule);
1648 }
1649
1650 static void add_asm_output(struct entrypoint *ep, struct instruction *insn, struct expression *expr,
1651         const char *constraint, const struct ident *ident)
1652 {
1653         struct access_data ad = { NULL, };
1654         pseudo_t pseudo = alloc_pseudo(insn);
1655         struct asm_constraint *rule;
1656
1657         if (!linearize_address_gen(ep, expr, &ad))
1658                 return;
1659         linearize_store_gen(ep, pseudo, &ad);
1660         finish_address_gen(ep, &ad);
1661         rule = __alloc_asm_constraint(0);
1662         rule->ident = ident;
1663         rule->constraint = constraint;
1664         use_pseudo(pseudo, &rule->pseudo);
1665         add_ptr_list(&insn->asm_rules->outputs, rule);
1666 }
1667
1668 pseudo_t linearize_asm_statement(struct entrypoint *ep, struct statement *stmt)
1669 {
1670         int state;
1671         struct expression *expr;
1672         struct instruction *insn;
1673         struct asm_rules *rules;
1674         const char *constraint;
1675         struct ident *ident;
1676
1677         insn = alloc_instruction(OP_ASM, 0);
1678         expr = stmt->asm_string;
1679         if (!expr || expr->type != EXPR_STRING) {
1680                 warning(stmt->pos, "expected string in inline asm");
1681                 return VOID;
1682         }
1683         insn->string = expr->string->data;
1684
1685         rules = __alloc_asm_rules(0);
1686         insn->asm_rules = rules;
1687
1688         /* Gather the inputs.. */
1689         state = 0;
1690         ident = NULL;
1691         constraint = NULL;
1692         FOR_EACH_PTR(stmt->asm_inputs, expr) {
1693                 switch (state) {
1694                 case 0: /* Identifier */
1695                         state = 1;
1696                         ident = (struct ident *)expr;
1697                         continue;
1698
1699                 case 1: /* Constraint */
1700                         state = 2;
1701                         constraint = expr ? expr->string->data : "";
1702                         continue;
1703
1704                 case 2: /* Expression */
1705                         state = 0;
1706                         add_asm_input(ep, insn, expr, constraint, ident);
1707                 }
1708         } END_FOR_EACH_PTR(expr);
1709
1710         add_one_insn(ep, insn);
1711
1712         /* Assign the outputs */
1713         state = 0;
1714         ident = NULL;
1715         constraint = NULL;
1716         FOR_EACH_PTR(stmt->asm_outputs, expr) {
1717                 switch (state) {
1718                 case 0: /* Identifier */
1719                         state = 1;
1720                         ident = (struct ident *)expr;
1721                         continue;
1722
1723                 case 1: /* Constraint */
1724                         state = 2;
1725                         constraint = expr->string->data;
1726                         continue;
1727
1728                 case 2:
1729                         state = 0;
1730                         add_asm_output(ep, insn, expr, constraint, ident);
1731                 }
1732         } END_FOR_EACH_PTR(expr);
1733
1734         return VOID;
1735 }
1736
1737 static int multijmp_cmp(const void *_a, const void *_b)
1738 {
1739         const struct multijmp *a = _a;
1740         const struct multijmp *b = _b;
1741
1742         // "default" case?
1743         if (a->begin > a->end) {
1744                 if (b->begin > b->end)
1745                         return 0;
1746                 return 1;
1747         }
1748         if (b->begin > b->end)
1749                 return -1;
1750         if (a->begin == b->begin) {
1751                 if (a->end == b->end)
1752                         return 0;
1753                 return (a->end < b->end) ? -1 : 1;
1754         }
1755         return a->begin < b->begin ? -1 : 1;
1756 }
1757
1758 static void sort_switch_cases(struct instruction *insn)
1759 {
1760         sort_list((struct ptr_list **)&insn->multijmp_list, multijmp_cmp);
1761 }
1762
1763 pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt)
1764 {
1765         struct basic_block *bb;
1766
1767         if (!stmt)
1768                 return VOID;
1769
1770         bb = ep->active;
1771         if (bb && !bb->insns)
1772                 bb->pos = stmt->pos;
1773         current_pos = stmt->pos;
1774
1775         switch (stmt->type) {
1776         case STMT_NONE:
1777                 break;
1778
1779         case STMT_CONTEXT:
1780                 return linearize_context(ep, stmt);
1781
1782         case STMT_RANGE:
1783                 return linearize_range(ep, stmt);
1784
1785         case STMT_EXPRESSION:
1786                 return linearize_expression(ep, stmt->expression);
1787
1788         case STMT_ASM:
1789                 return linearize_asm_statement(ep, stmt);
1790
1791         case STMT_RETURN: {
1792                 struct expression *expr = stmt->expression;
1793                 struct basic_block *bb_return = get_bound_block(ep, stmt->ret_target);
1794                 struct basic_block *active;
1795                 pseudo_t src = linearize_expression(ep, expr);
1796                 active = ep->active;
1797                 if (active && src != &void_pseudo) {
1798                         struct instruction *phi_node = first_instruction(bb_return->insns);
1799                         pseudo_t phi;
1800                         if (!phi_node) {
1801                                 phi_node = alloc_typed_instruction(OP_PHI, expr->ctype);
1802                                 phi_node->target = alloc_pseudo(phi_node);
1803                                 phi_node->bb = bb_return;
1804                                 add_instruction(&bb_return->insns, phi_node);
1805                         }
1806                         phi = alloc_phi(active, src, type_size(expr->ctype));
1807                         phi->ident = &return_ident;
1808                         use_pseudo(phi, add_pseudo(&phi_node->phi_list, phi));
1809                 }
1810                 add_goto(ep, bb_return);
1811                 return VOID;
1812         }
1813
1814         case STMT_CASE: {
1815                 add_label(ep, stmt->case_label);
1816                 linearize_statement(ep, stmt->case_statement);
1817                 break;
1818         }
1819
1820         case STMT_LABEL: {
1821                 struct symbol *label = stmt->label_identifier;
1822
1823                 if (label->used) {
1824                         add_label(ep, label);
1825                         linearize_statement(ep, stmt->label_statement);
1826                 }
1827                 break;
1828         }
1829
1830         case STMT_GOTO: {
1831                 struct symbol *sym;
1832                 struct expression *expr;
1833                 struct instruction *goto_ins;
1834                 struct basic_block *active;
1835                 pseudo_t pseudo;
1836
1837                 active = ep->active;
1838                 if (!bb_reachable(active))
1839                         break;
1840
1841                 if (stmt->goto_label) {
1842                         add_goto(ep, get_bound_block(ep, stmt->goto_label));
1843                         break;
1844                 }
1845
1846                 expr = stmt->goto_expression;
1847                 if (!expr)
1848                         break;
1849
1850                 /* This can happen as part of simplification */
1851                 if (expr->type == EXPR_LABEL) {
1852                         add_goto(ep, get_bound_block(ep, expr->label_symbol));
1853                         break;
1854                 }
1855
1856                 pseudo = linearize_expression(ep, expr);
1857                 goto_ins = alloc_instruction(OP_COMPUTEDGOTO, 0);
1858                 use_pseudo(pseudo, &goto_ins->target);
1859                 add_one_insn(ep, goto_ins);
1860
1861                 FOR_EACH_PTR(stmt->target_list, sym) {
1862                         struct basic_block *bb_computed = get_bound_block(ep, sym);
1863                         struct multijmp *jmp = alloc_multijmp(bb_computed, 1, 0);
1864                         add_multijmp(&goto_ins->multijmp_list, jmp);
1865                         add_bb(&bb_computed->parents, ep->active);
1866                         add_bb(&active->children, bb_computed);
1867                 } END_FOR_EACH_PTR(sym);
1868
1869                 finish_block(ep);
1870                 break;
1871         }
1872
1873         case STMT_COMPOUND:
1874                 return linearize_compound_statement(ep, stmt);
1875
1876         /*
1877          * This could take 'likely/unlikely' into account, and
1878          * switch the arms around appropriately..
1879          */
1880         case STMT_IF: {
1881                 struct basic_block *bb_true, *bb_false, *endif;
1882                 struct expression *cond = stmt->if_conditional;
1883
1884                 bb_true = alloc_basic_block(ep, stmt->pos);
1885                 bb_false = endif = alloc_basic_block(ep, stmt->pos);
1886
1887                 linearize_cond_branch(ep, cond, bb_true, bb_false);
1888
1889                 set_activeblock(ep, bb_true);
1890                 linearize_statement(ep, stmt->if_true);
1891
1892                 if (stmt->if_false) {
1893                         endif = alloc_basic_block(ep, stmt->pos);
1894                         add_goto(ep, endif);
1895                         set_activeblock(ep, bb_false);
1896                         linearize_statement(ep, stmt->if_false);
1897                 }
1898                 set_activeblock(ep, endif);
1899                 break;
1900         }
1901
1902         case STMT_SWITCH: {
1903                 struct symbol *sym;
1904                 struct instruction *switch_ins;
1905                 struct basic_block *switch_end = alloc_basic_block(ep, stmt->pos);
1906                 struct basic_block *active, *default_case;
1907                 struct multijmp *jmp;
1908                 pseudo_t pseudo;
1909
1910                 pseudo = linearize_expression(ep, stmt->switch_expression);
1911
1912                 active = ep->active;
1913                 if (!bb_reachable(active))
1914                         break;
1915
1916                 switch_ins = alloc_instruction(OP_SWITCH, 0);
1917                 use_pseudo(pseudo, &switch_ins->cond);
1918                 add_one_insn(ep, switch_ins);
1919                 finish_block(ep);
1920
1921                 default_case = NULL;
1922                 FOR_EACH_PTR(stmt->switch_case->symbol_list, sym) {
1923                         struct statement *case_stmt = sym->stmt;
1924                         struct basic_block *bb_case = get_bound_block(ep, sym);
1925
1926                         if (!case_stmt->case_expression) {
1927                                 default_case = bb_case;
1928                                 continue;
1929                         } else {
1930                                 int begin, end;
1931
1932                                 begin = end = case_stmt->case_expression->value;
1933                                 if (case_stmt->case_to)
1934                                         end = case_stmt->case_to->value;
1935                                 if (begin > end)
1936                                         jmp = alloc_multijmp(bb_case, end, begin);
1937                                 else
1938                                         jmp = alloc_multijmp(bb_case, begin, end);
1939
1940                         }
1941                         add_multijmp(&switch_ins->multijmp_list, jmp);
1942                         add_bb(&bb_case->parents, active);
1943                         add_bb(&active->children, bb_case);
1944                 } END_FOR_EACH_PTR(sym);
1945
1946                 bind_label(stmt->switch_break, switch_end, stmt->pos);
1947
1948                 /* And linearize the actual statement */
1949                 linearize_statement(ep, stmt->switch_statement);
1950                 set_activeblock(ep, switch_end);
1951
1952                 if (!default_case)
1953                         default_case = switch_end;
1954
1955                 jmp = alloc_multijmp(default_case, 1, 0);
1956                 add_multijmp(&switch_ins->multijmp_list, jmp);
1957                 add_bb(&default_case->parents, active);
1958                 add_bb(&active->children, default_case);
1959                 sort_switch_cases(switch_ins);
1960
1961                 break;
1962         }
1963
1964         case STMT_ITERATOR: {
1965                 struct statement  *pre_statement = stmt->iterator_pre_statement;
1966                 struct expression *pre_condition = stmt->iterator_pre_condition;
1967                 struct statement  *statement = stmt->iterator_statement;
1968                 struct statement  *post_statement = stmt->iterator_post_statement;
1969                 struct expression *post_condition = stmt->iterator_post_condition;
1970                 struct basic_block *loop_top, *loop_body, *loop_continue, *loop_end;
1971
1972                 concat_symbol_list(stmt->iterator_syms, &ep->syms);
1973                 linearize_statement(ep, pre_statement);
1974
1975                 loop_body = loop_top = alloc_basic_block(ep, stmt->pos);
1976                 loop_continue = alloc_basic_block(ep, stmt->pos);
1977                 loop_end = alloc_basic_block(ep, stmt->pos);
1978
1979                 if (pre_condition == post_condition) {
1980                         loop_top = alloc_basic_block(ep, stmt->pos);
1981                         set_activeblock(ep, loop_top);
1982                 }
1983
1984                 if (pre_condition)
1985                         linearize_cond_branch(ep, pre_condition, loop_body, loop_end);
1986
1987                 bind_label(stmt->iterator_continue, loop_continue, stmt->pos);
1988                 bind_label(stmt->iterator_break, loop_end, stmt->pos);
1989
1990                 set_activeblock(ep, loop_body);
1991                 linearize_statement(ep, statement);
1992                 add_goto(ep, loop_continue);
1993
1994                 set_activeblock(ep, loop_continue);
1995                 linearize_statement(ep, post_statement);
1996                 if (!post_condition || pre_condition == post_condition)
1997                         add_goto(ep, loop_top);
1998                 else
1999                         linearize_cond_branch(ep, post_condition, loop_top, loop_end);
2000                 set_activeblock(ep, loop_end);
2001                 break;
2002         }
2003
2004         default:
2005                 break;
2006         }
2007         return VOID;
2008 }
2009
2010 static struct entrypoint *linearize_fn(struct symbol *sym, struct symbol *base_type)
2011 {
2012         struct entrypoint *ep;
2013         struct basic_block *bb;
2014         struct symbol *arg;
2015         struct instruction *entry;
2016         pseudo_t result;
2017         int i;
2018
2019         if (!base_type->stmt)
2020                 return NULL;
2021
2022         ep = alloc_entrypoint();
2023         bb = alloc_basic_block(ep, sym->pos);
2024
2025         ep->name = sym;
2026         set_activeblock(ep, bb);
2027
2028         entry = alloc_instruction(OP_ENTRY, 0);
2029         add_one_insn(ep, entry);
2030         ep->entry = entry;
2031
2032         concat_symbol_list(base_type->arguments, &ep->syms);
2033
2034         /* FIXME!! We should do something else about varargs.. */
2035         i = 0;
2036         FOR_EACH_PTR(base_type->arguments, arg) {
2037                 linearize_argument(ep, arg, ++i);
2038         } END_FOR_EACH_PTR(arg);
2039
2040         result = linearize_statement(ep, base_type->stmt);
2041         if (bb_reachable(ep->active) && !bb_terminated(ep->active)) {
2042                 struct symbol *ret_type = base_type->ctype.base_type;
2043                 struct instruction *insn = alloc_typed_instruction(OP_RET, ret_type);
2044
2045                 if (type_size(ret_type) > 0)
2046                         use_pseudo(result, &insn->src);
2047                 add_one_insn(ep, insn);
2048         }
2049
2050         /*
2051          * Do trivial flow simplification - branches to
2052          * branches, kill dead basicblocks etc
2053          */
2054         kill_unreachable_bbs(ep);
2055
2056         /*
2057          * Turn symbols into pseudos
2058          */
2059         simplify_symbol_usage(ep);
2060
2061 repeat:
2062         /*
2063          * Remove trivial instructions, and try to CSE
2064          * the rest.
2065          */
2066         do {
2067                 cleanup_and_cse(ep);
2068                 pack_basic_blocks(ep);
2069         } while (repeat_phase & REPEAT_CSE);
2070
2071         kill_unreachable_bbs(ep);
2072         vrfy_flow(ep);
2073
2074         /* Cleanup */
2075         clear_symbol_pseudos(ep);
2076
2077         /* And track pseudo register usage */
2078         track_pseudo_liveness(ep);
2079
2080         /*
2081          * Some flow optimizations can only effectively
2082          * be done when we've done liveness analysis. But
2083          * if they trigger, we need to start all over
2084          * again
2085          */
2086         if (simplify_flow(ep)) {
2087                 clear_liveness(ep);
2088                 goto repeat;
2089         }
2090
2091         /* Finally, add deathnotes to pseudos now that we have them */
2092         track_pseudo_death(ep);
2093
2094         return ep;
2095 }
2096
2097 struct entrypoint *linearize_symbol(struct symbol *sym)
2098 {
2099         struct symbol *base_type;
2100
2101         if (!sym)
2102                 return NULL;
2103         current_pos = sym->pos;
2104         base_type = sym->ctype.base_type;
2105         if (!base_type)
2106                 return NULL;
2107         if (base_type->type == SYM_FN)
2108                 return linearize_fn(sym, base_type);
2109         return NULL;
2110 }