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