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
  18 #include "parse.h"
  19 #include "expression.h"
  20 #include "linearize.h"
  21
  22 pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt);
  23 pseudo_t linearize_expression(struct entrypoint *ep, struct expression *expr);
  24
  25 static struct instruction *alloc_instruction(int opcode, struct symbol *type)
  26 {
  27         struct instruction * insn = __alloc_instruction(0);
  28         insn->type = type;
  29         insn->opcode = opcode;
  30         return insn;
  31 }
  32
  33 static struct entrypoint *alloc_entrypoint(void)
  34 {
  35         return __alloc_entrypoint(0);
  36 }
  37
  38 static struct basic_block *alloc_basic_block(void)
  39 {
  40         return __alloc_basic_block(0);
  41 }
  42
  43 static struct multijmp* alloc_multijmp(struct basic_block *target, int begin, int end)
  44 {
  45         struct multijmp *multijmp = __alloc_multijmp(0);
  46         multijmp->target = target;
  47         multijmp->begin = begin;
  48         multijmp->end = end;
  49         return multijmp;
  50 }
  51
  52 static struct phi* alloc_phi(struct basic_block *source, pseudo_t pseudo)
  53 {
  54         struct phi *phi = __alloc_phi(0);
  55         phi->source = source;
  56         phi->pseudo = pseudo;
  57         return phi;
  58 }
  59
  60 static void show_instruction(struct instruction *insn)
  61 {
  62         int op = insn->opcode;
  63
  64         switch (op) {
  65         case OP_BADOP:
  66                 printf("\tAIEEE! (%d %d)\n", insn->target.nr, insn->src.nr);
  67                 break;
  68         case OP_RET:
  69                 printf("\tret %%r%d\n", insn->src.nr);
  70                 break;
  71         case OP_BR:
  72                 if (insn->bb_true && insn->bb_false) {
  73                         printf("\tbr\t%%r%d, .L%p, .L%p\n", insn->cond.nr, insn->bb_true, insn->bb_false);
  74                         break;
  75                 }
  76                 printf("\tbr\t.L%p\n", insn->bb_true ? insn->bb_true : insn->bb_false);
  77                 break;
  78
  79         case OP_SETVAL: {
  80                 struct expression *expr = insn->val;
  81                 switch (expr->type) {
  82                 case EXPR_VALUE:
  83                         printf("\t%%r%d <- %lld\n",
  84                                 insn->target.nr, expr->value);
  85                         break;
  86                 case EXPR_STRING:
  87                         printf("\t%%r%d <- %s\n",
  88                                 insn->target.nr, show_string(expr->string));
  89                         break;
  90                 case EXPR_SYMBOL:
  91                         printf("\t%%r%d <- %s\n",
  92                                 insn->target.nr, show_ident(expr->symbol->ident));
  93                         break;
  94                 default:
  95                         printf("\t SETVAL ?? ");
  96                 }
  97                 break;
  98         }
  99         case OP_SWITCH: {
 100                 struct multijmp *jmp;
 101                 printf("\tswitch %%r%d", insn->cond.nr);
 102                 FOR_EACH_PTR(insn->multijmp_list, jmp) {
 103                         if (jmp->begin == jmp->end)
 104                                 printf(", %d -> .L%p", jmp->begin, jmp->target);
 105                         else if (jmp->begin < jmp->end)
 106                                 printf(", %d ... %d -> .L%p", jmp->begin, jmp->end, jmp->target);
 107                         else
 108                                 printf(", default -> .L%p\n", jmp->target);
 109                 } END_FOR_EACH_PTR;
 110                 printf("\n");
 111                 break;
 112         }
 113
 114         case OP_PHI: {
 115                 struct phi *phi;
 116                 char *s = " ";
 117                 printf("\t%%r%d <- phi", insn->target.nr);
 118                 FOR_EACH_PTR(insn->phi_list, phi) {
 119                         printf("%s(%%r%d, .L%p)", s, phi->pseudo.nr, phi->source);
 120                         s = ", ";
 121                 } END_FOR_EACH_PTR;
 122                 printf("\n");
 123                 break;
 124         }
 125         case OP_LOAD:
 126                 printf("\tload %%r%d <- [%%r%d]\n", insn->target.nr, insn->src.nr);
 127                 break;
 128         case OP_STORE:
 129                 printf("\tstore %%r%d -> [%%r%d]\n", insn->target.nr, insn->src.nr);
 130                 break;
 131         case OP_ARGUMENT:
 132                 printf("\tpush %%r%d\n", insn->src.nr);
 133                 break;
 134         case OP_CALL:
 135                 printf("\t%%r%d <- CALL %s\n", insn->target.nr, show_ident(insn->address->ident));
 136                 break;
 137         case OP_INDCALL:
 138                 printf("\t%%r%d <- CALL [%%r%d]\n", insn->target.nr, insn->src.nr);
 139                 break;
 140         case OP_CAST:
 141                 printf("\t%%r%d <- CAST(%d->%d) %%r%d\n",
 142                         insn->target.nr,
 143                         insn->orig_type->bit_size, insn->type->bit_size,
 144                         insn->src.nr);
 145                 break;
 146         case OP_BINARY ... OP_BINARY_END:
 147         case OP_LOGICAL ... OP_LOGICAL_END: {
 148                 static const char *opname[] = {
 149                         [OP_ADD - OP_BINARY] = "add", [OP_SUB - OP_BINARY] = "sub",
 150                         [OP_MUL - OP_BINARY] = "mul", [OP_DIV - OP_BINARY] = "div",
 151                         [OP_MOD - OP_BINARY] = "mod", [OP_AND - OP_BINARY] = "and",
 152                         [OP_OR  - OP_BINARY] = "or",  [OP_XOR - OP_BINARY] = "xor"
 153                 };
 154                 printf("\t%%r%d <- %s  %%r%d, %%r%d\n",
 155                         insn->target.nr,
 156                         opname[op - OP_BINARY], insn->src1.nr, insn->src2.nr);
 157                 break;
 158         }
 159
 160         case OP_BINCMP ... OP_BINCMP_END: {
 161                 static const char *opname[] = {
 162                         [OP_SET_EQ - OP_BINCMP] = "seteq",
 163                         [OP_SET_NE - OP_BINCMP] = "setne",
 164                         [OP_SET_LE - OP_BINCMP] = "setle",
 165                         [OP_SET_GE - OP_BINCMP] = "setge",
 166                         [OP_SET_LT - OP_BINCMP] = "setlt",
 167                         [OP_SET_GT - OP_BINCMP] = "setgt",
 168                 };
 169                 printf("\t%%r%d <- %s  %%r%d, %%r%d\n",
 170                         insn->target.nr,
 171                         opname[op - OP_BINCMP], insn->src1.nr, insn->src2.nr);
 172                 break;
 173         }
 174
 175         case OP_UNOP ... OP_LASTUNOP:
 176                 printf("\t%%r%d <- %s %%r%d\n",
 177                         insn->target.nr,
 178                         show_special(op - OP_UNOP), insn->src.nr);
 179                 break;
 180         default:
 181                 printf("\top %d ???\n", op);
 182         }
 183 }
 184
 185 static void show_bb(struct basic_block *bb)
 186 {
 187         struct instruction *insn;
 188
 189         printf("bb: %p\n", bb);
 190         if (bb->parents) {
 191                 struct basic_block *from;
 192                 FOR_EACH_PTR(bb->parents, from) {
 193                         printf("  **from %p**\n", from);
 194                 } END_FOR_EACH_PTR;
 195         }
 196         FOR_EACH_PTR(bb->insns, insn) {
 197                 show_instruction(insn);
 198         } END_FOR_EACH_PTR;
 199         if (!bb_terminated(bb))
 200                 printf("\tEND\n");
 201         printf("\n");
 202 }
 203
 204 static void show_entry(struct entrypoint *ep)
 205 {
 206         struct symbol *sym;
 207         struct basic_block *bb;
 208
 209         printf("ep %p: %s\n", ep, show_ident(ep->name->ident));
 210
 211         FOR_EACH_PTR(ep->syms, sym) {
 212                 printf("   sym: %p %s\n", sym, show_ident(sym->ident));
 213         } END_FOR_EACH_PTR;
 214
 215         printf("\n");
 216
 217         FOR_EACH_PTR(ep->bbs, bb) {
 218                 show_bb(bb);
 219         } END_FOR_EACH_PTR;
 220
 221         printf("\n");
 222 }
 223
 224 static void bind_label(struct symbol *label, struct basic_block *bb, struct position pos)
 225 {
 226         if (label->bb_target)
 227                 warn(pos, "label already bound\n");
 228         label->bb_target = bb;
 229 }
 230
 231 static struct basic_block * get_bound_block(struct entrypoint *ep, struct symbol *label)
 232 {
 233         struct basic_block *bb = label->bb_target;
 234
 235         if (!bb) {
 236                 label->bb_target = bb = alloc_basic_block();
 237                 bb->flags |= BB_REACHABLE;
 238         }
 239         return bb;
 240 }
 241
 242 static void add_goto(struct entrypoint *ep, struct basic_block *dst)
 243 {
 244         struct basic_block *src = ep->active;
 245         if (bb_reachable(src)) {
 246                 struct instruction *br = alloc_instruction(OP_BR, NULL);
 247                 br->bb_true = dst;
 248                 add_bb(&dst->parents, src);
 249                 add_instruction(&src->insns, br);
 250                 ep->active = NULL;
 251         }
 252 }
 253
 254 static void add_one_insn(struct entrypoint *ep, struct position pos, struct instruction *insn)
 255 {
 256         struct basic_block *bb = ep->active;
 257
 258         if (bb_reachable(bb))
 259                 add_instruction(&bb->insns, insn);
 260 }
 261
 262 static void set_activeblock(struct entrypoint *ep, struct basic_block *bb)
 263 {
 264         if (!bb_terminated(ep->active))
 265                 add_goto(ep, bb);
 266
 267         ep->active = bb;
 268         if (bb_reachable(bb))
 269                 add_bb(&ep->bbs, bb);
 270 }
 271
 272 static void add_branch(struct entrypoint *ep, struct expression *expr, pseudo_t cond, struct basic_block *bb_true, struct basic_block *bb_false)
 273 {
 274         struct basic_block *bb = ep->active;
 275         struct instruction *br;
 276
 277         if (bb_reachable(bb)) {
 278                 br = alloc_instruction(OP_BR, expr->ctype);
 279                 br->cond = cond;
 280                 br->bb_true = bb_true;
 281                 br->bb_false = bb_false;
 282                 add_bb(&bb_true->parents, bb);
 283                 add_bb(&bb_false->parents, bb);
 284                 add_one_insn(ep, expr->pos, br);
 285         }
 286 }
 287
 288 /* Dummy pseudo allocator */
 289 static pseudo_t alloc_pseudo(void)
 290 {
 291         static int nr = 0;
 292         return to_pseudo(++nr);
 293 }
 294
 295 /*
 296  * FIXME! Not all accesses are memory loads. We should
 297  * check what kind of symbol is behind the dereference.
 298  */
 299 static pseudo_t linearize_address_gen(struct entrypoint *ep, struct expression *expr)
 300 {
 301         if (expr->type == EXPR_PREOP)
 302                 return linearize_expression(ep, expr->unop);
 303         if (expr->type == EXPR_BITFIELD)
 304                 return linearize_expression(ep, expr->address);
 305         warn(expr->pos, "generating address of non-lvalue");
 306         return VOID;
 307 }
 308
 309 static void linearize_store_gen(struct entrypoint *ep, pseudo_t value, struct expression *expr, pseudo_t addr)
 310 {
 311         struct instruction *store = alloc_instruction(OP_STORE, expr->ctype);
 312         store->target = value;
 313         store->src = addr;
 314         add_one_insn(ep, expr->pos, store);
 315 }
 316
 317 static pseudo_t linearize_load_gen(struct entrypoint *ep, struct expression *expr, pseudo_t addr)
 318 {
 319         pseudo_t new = alloc_pseudo();
 320         struct instruction *insn = alloc_instruction(OP_LOAD, expr->ctype);
 321
 322         insn->target = new;
 323         insn->src = addr;
 324         add_one_insn(ep, expr->pos, insn);
 325         if (expr->type == EXPR_PREOP)
 326                 return new;
 327
 328         /* bitfield load */
 329         /* FIXME! Add shift and mask!!! */
 330         return new;
 331 }
 332
 333 static pseudo_t linearize_access(struct entrypoint *ep, struct expression *expr)
 334 {
 335         pseudo_t addr = linearize_address_gen(ep, expr);
 336         return linearize_load_gen(ep, expr, addr);
 337 }
 338
 339 static pseudo_t linearize_inc_dec(struct entrypoint *ep, struct expression *expr, int postop)
 340 {
 341         pseudo_t addr = linearize_address_gen(ep, expr->unop);
 342         pseudo_t retval, new;
 343         struct instruction *insn;
 344
 345         retval = linearize_load_gen(ep, expr->unop, addr);
 346         new = retval;
 347         if (postop)
 348                 new = alloc_pseudo();
 349
 350         /* Generate the inc/dec */
 351         insn = alloc_instruction(OP_UNOP + expr->op, expr->ctype);
 352         insn->target = new;
 353         insn->src = retval;
 354         add_one_insn(ep, expr->pos, insn);
 355
 356         /* Store back value */
 357         linearize_store_gen(ep, new, expr->unop, addr);
 358         return retval;
 359 }
 360
 361 static pseudo_t linearize_regular_preop(struct entrypoint *ep, struct expression *expr)
 362 {
 363         pseudo_t target = linearize_expression(ep, expr->unop);
 364         pseudo_t new = alloc_pseudo();
 365         struct instruction *insn = alloc_instruction(OP_UNOP + expr->op, expr->ctype);
 366         insn->target = new;
 367         insn->src1 = target;
 368         return new;
 369 }
 370
 371 static pseudo_t linearize_preop(struct entrypoint *ep, struct expression *expr)
 372 {
 373         /*
 374          * '*' is an lvalue access, and is fundamentally different
 375          * from an arithmetic operation. Maybe it should have an
 376          * expression type of its own..
 377          */
 378         if (expr->op == '*')
 379                 return linearize_access(ep, expr);
 380         if (expr->op == SPECIAL_INCREMENT || expr->op == SPECIAL_DECREMENT)
 381                 return linearize_inc_dec(ep, expr, 0);
 382         return linearize_regular_preop(ep, expr);
 383 }
 384
 385 static pseudo_t linearize_postop(struct entrypoint *ep, struct expression *expr)
 386 {
 387         return linearize_inc_dec(ep, expr, 1);
 388 }
 389
 390 static pseudo_t linearize_assignment(struct entrypoint *ep, struct expression *expr)
 391 {
 392         struct expression *target = expr->left;
 393         pseudo_t value, address;
 394
 395         value = linearize_expression(ep, expr->right);
 396         address = linearize_address_gen(ep, target);
 397         linearize_store_gen(ep, value, target, address);
 398         return value;
 399 }
 400
 401 static void push_argument(struct entrypoint *ep, struct expression *expr, pseudo_t pseudo)
 402 {
 403         struct instruction *insn = alloc_instruction(OP_ARGUMENT, expr->ctype);
 404         insn->src = pseudo;
 405         add_one_insn(ep, expr->pos, insn);
 406 }
 407
 408 static pseudo_t linearize_direct_call(struct entrypoint *ep, struct expression *expr, struct symbol *direct)
 409 {
 410         struct instruction *insn = alloc_instruction(OP_CALL, expr->ctype);
 411         pseudo_t retval = alloc_pseudo();
 412
 413         insn->target = retval;
 414         insn->address = direct;
 415         add_one_insn(ep, expr->pos, insn);
 416         return retval;
 417 }
 418
 419 static pseudo_t linearize_indirect_call(struct entrypoint *ep, struct expression *expr, pseudo_t pseudo)
 420 {
 421         struct instruction *insn = alloc_instruction(OP_INDCALL, expr->ctype);
 422         pseudo_t retval = alloc_pseudo();
 423
 424         insn->target = retval;
 425         insn->src = pseudo;
 426         add_one_insn(ep, expr->pos, insn);
 427         return retval;
 428 }
 429
 430 static pseudo_t linearize_call_expression(struct entrypoint *ep, struct expression *expr)
 431 {
 432         struct symbol *direct;
 433         struct expression *arg, *fn;
 434         pseudo_t retval;
 435
 436         if (!expr->ctype) {
 437                 warn(expr->pos, "\tcall with no type!");
 438                 return VOID;
 439         }
 440
 441         FOR_EACH_PTR_REVERSE(expr->args, arg) {
 442                 pseudo_t new = linearize_expression(ep, arg);
 443                 push_argument(ep, arg, new);
 444         } END_FOR_EACH_PTR_REVERSE;
 445
 446         fn = expr->fn;
 447
 448         /* Remove dereference, if any */
 449         direct = NULL;
 450         if (fn->type == EXPR_PREOP) {
 451                 if (fn->unop->type == EXPR_SYMBOL) {
 452                         struct symbol *sym = fn->unop->symbol;
 453                         if (sym->ctype.base_type->type == SYM_FN)
 454                                 direct = sym;
 455                 }
 456         }
 457         if (direct) {
 458                 retval = linearize_direct_call(ep, expr, direct);
 459         } else {
 460                 pseudo_t fncall = linearize_expression(ep, fn);
 461                 retval = linearize_indirect_call(ep, expr, fncall);
 462         }
 463         return retval;
 464 }
 465
 466 static pseudo_t linearize_binop(struct entrypoint *ep, struct expression *expr)
 467 {
 468         pseudo_t src1, src2, result;
 469         struct instruction *insn;
 470         static const int opcode[] = {
 471                 ['+'] = OP_ADD, ['-'] = OP_SUB,
 472                 ['*'] = OP_MUL, ['/'] = OP_DIV,
 473                 ['%'] = OP_MOD, ['&'] = OP_AND,
 474                 ['|'] = OP_OR,  ['^'] = OP_XOR,
 475         };
 476
 477         src1 = linearize_expression(ep, expr->left);
 478         src2 = linearize_expression(ep, expr->right);
 479         result = alloc_pseudo();
 480
 481         insn = alloc_instruction(opcode[expr->op], expr->ctype);
 482         insn->target = result;
 483         insn->src1 = src1;
 484         insn->src2 = src2;
 485         add_one_insn(ep, expr->pos, insn);
 486         return result;
 487 }
 488
 489 static pseudo_t linearize_logical_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false);
 490
 491 pseudo_t linearize_cond_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false);
 492
 493 static pseudo_t linearize_logical(struct entrypoint *ep, struct expression *expr)
 494 {
 495         pseudo_t src1, src2, target;
 496         struct basic_block *bb_true = alloc_basic_block();
 497         struct basic_block *bb_false = alloc_basic_block();
 498         struct basic_block *merge = alloc_basic_block();
 499         struct basic_block *first = bb_true;
 500         struct basic_block *second = bb_false;
 501         struct instruction *insn;
 502
 503         if (expr->op == SPECIAL_LOGICAL_OR) {
 504                 first = bb_false;
 505                 second = bb_true;
 506         }
 507
 508         linearize_cond_branch(ep, expr->left, bb_true, bb_false);
 509
 510         set_activeblock(ep, first);
 511         src1 = linearize_expression(ep, expr->right);
 512         add_goto(ep, merge);
 513
 514         set_activeblock(ep, second);
 515         insn = alloc_instruction(OP_SETVAL, expr->ctype);
 516         insn->target = src2 = alloc_pseudo();
 517         insn->val = alloc_const_expression(expr->pos, expr->op == SPECIAL_LOGICAL_OR);
 518         add_one_insn(ep, expr->pos,insn);
 519
 520         set_activeblock(ep, merge);
 521
 522         if (bb_reachable(bb_true) && bb_reachable(bb_false)) {
 523                 struct instruction *phi_node = alloc_instruction(OP_PHI, expr->ctype);
 524                 add_phi(&phi_node->phi_list, alloc_phi(first, src1));
 525                 add_phi(&phi_node->phi_list, alloc_phi(second, src2));
 526                 phi_node->target = target = alloc_pseudo();
 527                 add_one_insn(ep, expr->pos, phi_node);
 528                 set_activeblock(ep, alloc_basic_block());
 529                 return target;
 530         }
 531
 532         return bb_reachable(first) ? src1 : src2;
 533 }
 534
 535 static pseudo_t linearize_compare(struct entrypoint *ep, struct expression *expr)
 536 {
 537         static const int cmpop[] = {
 538                 ['>'] = OP_SET_GT, ['<'] = OP_SET_LT,
 539                 [SPECIAL_EQUAL] = OP_SET_EQ,
 540                 [SPECIAL_NOTEQUAL] = OP_SET_NE,
 541                 [SPECIAL_GTE] = OP_SET_GE,
 542                 [SPECIAL_LTE] = OP_SET_LE,
 543         };
 544         struct instruction *insn = alloc_instruction(cmpop[expr->op], expr->ctype);
 545         pseudo_t target;
 546         insn->src1 = linearize_expression(ep, expr->left);
 547         insn->src2 = linearize_expression(ep, expr->right);
 548         insn->target = target = alloc_pseudo();
 549         add_one_insn(ep, expr->pos, insn);
 550         return target;
 551 }
 552
 553
 554 pseudo_t linearize_cond_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false)
 555 {
 556         pseudo_t cond;
 557
 558         if (!expr || !bb_reachable(ep->active))
 559                 return VOID;
 560
 561         switch (expr->type) {
 562
 563         case EXPR_STRING:
 564         case EXPR_VALUE:
 565                 add_goto(ep, expr->value ? bb_true : bb_false);
 566                 return VOID;
 567
 568         case EXPR_LOGICAL:
 569                 linearize_logical_branch(ep, expr, bb_true, bb_false);
 570                 return VOID;
 571
 572         case EXPR_COMPARE:
 573                 cond = linearize_compare(ep, expr);
 574                 add_branch(ep, expr, cond, bb_true, bb_false);
 575                 break;
 576
 577         case EXPR_PREOP:
 578                 if (expr->op == '!')
 579                         return linearize_cond_branch(ep, expr->unop, bb_false, bb_true);
 580                 /* fall through */
 581         default: {
 582                 cond = linearize_expression(ep, expr);
 583                 add_branch(ep, expr, cond, bb_true, bb_false);
 584
 585                 return VOID;
 586         }
 587         }
 588         return VOID;
 589 }
 590
 591
 592
 593 static pseudo_t linearize_logical_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false)
 594 {
 595         struct basic_block *next = alloc_basic_block();
 596
 597         if (expr->op == SPECIAL_LOGICAL_OR)
 598                 linearize_cond_branch(ep, expr->left, bb_true, next);
 599         else
 600                 linearize_cond_branch(ep, expr->left, next, bb_false);
 601         set_activeblock(ep, next);
 602         linearize_cond_branch(ep, expr->right, bb_true, bb_false);
 603         return VOID;
 604 }
 605
 606 pseudo_t linearize_cast(struct entrypoint *ep, struct expression *expr)
 607 {
 608         pseudo_t src, result;
 609         struct instruction *insn;
 610
 611         src = linearize_expression(ep, expr->cast_expression);
 612         insn = alloc_instruction(OP_CAST, expr->ctype);
 613         result = alloc_pseudo();
 614         insn->target = result;
 615         insn->src = src;
 616         insn->orig_type = expr->cast_expression->ctype;
 617         add_one_insn(ep, expr->pos, insn);
 618         return result;
 619 }
 620
 621 pseudo_t linearize_expression(struct entrypoint *ep, struct expression *expr)
 622 {
 623         if (!expr)
 624                 return VOID;
 625
 626         switch (expr->type) {
 627         case EXPR_VALUE: case EXPR_STRING: case EXPR_SYMBOL: {
 628                 pseudo_t pseudo;
 629                 struct instruction *insn = alloc_instruction(OP_SETVAL, expr->ctype);
 630                 insn->target = pseudo = alloc_pseudo();
 631                 insn->val = expr;
 632                 add_one_insn(ep, expr->pos,insn);
 633                 return pseudo;
 634         }
 635
 636         case EXPR_STATEMENT:
 637                 return linearize_statement(ep, expr->statement);
 638
 639         case EXPR_CALL:
 640                 return linearize_call_expression(ep, expr);
 641
 642         case EXPR_BINOP:
 643                 return linearize_binop(ep, expr);
 644
 645         case EXPR_LOGICAL:
 646                 return linearize_logical(ep, expr);
 647
 648         case EXPR_COMPARE:
 649                 return  linearize_compare(ep, expr);
 650
 651         case EXPR_COMMA: {
 652                 linearize_expression(ep, expr->left);
 653                 return linearize_expression(ep, expr->right);
 654         }
 655
 656         case EXPR_ASSIGNMENT:
 657                 return linearize_assignment(ep, expr);
 658
 659         case EXPR_PREOP:
 660                 return linearize_preop(ep, expr);
 661
 662         case EXPR_POSTOP:
 663                 return linearize_postop(ep, expr);
 664
 665         case EXPR_CAST:
 666                 return linearize_cast(ep, expr);
 667
 668         default: {
 669                 struct instruction *bad = alloc_instruction(OP_BADOP, expr->ctype);
 670                 bad->target.nr = expr->type;
 671                 bad->src.nr = expr->op;
 672                 add_one_insn(ep, expr->pos, bad);
 673                 return VOID;
 674         }
 675         }
 676         return VOID;
 677 }
 678
 679 pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt)
 680 {
 681         if (!stmt)
 682                 return VOID;
 683
 684         switch (stmt->type) {
 685         case STMT_NONE:
 686                 break;
 687
 688         case STMT_EXPRESSION:
 689                 return linearize_expression(ep, stmt->expression);
 690
 691         case STMT_ASM:
 692                 /* FIXME */
 693                 break;
 694
 695         case STMT_RETURN: {
 696                 struct expression *expr = stmt->expression;
 697                 struct instruction *ret = alloc_instruction(OP_RET, expr->ctype);
 698                 ret->src = linearize_expression(ep, expr);
 699                 add_one_insn(ep, stmt->pos, ret);
 700                 ep->active = NULL;
 701                 return VOID;
 702         }
 703
 704         case STMT_CASE: {
 705                 struct basic_block *bb = get_bound_block(ep, stmt->case_label);
 706                 set_activeblock(ep, bb);
 707                 linearize_statement(ep, stmt->case_statement);
 708                 break;
 709         }
 710
 711         case STMT_LABEL: {
 712                 struct symbol *label = stmt->label_identifier;
 713                 struct basic_block *bb;
 714
 715                 if (label->used) {
 716                         bb = get_bound_block(ep, stmt->label_identifier);
 717                         set_activeblock(ep, bb);
 718                         linearize_statement(ep, stmt->label_statement);
 719                 }
 720                 break;
 721         }
 722
 723         case STMT_GOTO: {
 724                 add_goto(ep, get_bound_block(ep, stmt->goto_label));
 725                 break;
 726         }
 727
 728         case STMT_COMPOUND: {
 729                 pseudo_t pseudo;
 730                 struct statement *s;
 731                 concat_symbol_list(stmt->syms, &ep->syms);
 732                 FOR_EACH_PTR(stmt->stmts, s) {
 733                         pseudo = linearize_statement(ep, s);
 734                 } END_FOR_EACH_PTR;
 735                 return pseudo;
 736         }
 737
 738         /*
 739          * This could take 'likely/unlikely' into account, and
 740          * switch the arms around appropriately..
 741          */
 742         case STMT_IF: {
 743                 struct basic_block *bb_true, *bb_false, *endif;
 744                 struct expression *cond = stmt->if_conditional;
 745
 746                 bb_true = alloc_basic_block();
 747                 bb_false = endif = alloc_basic_block();
 748
 749                 linearize_cond_branch(ep, cond, bb_true, bb_false);
 750
 751                 set_activeblock(ep, bb_true);
 752                 linearize_statement(ep, stmt->if_true);
 753
 754                 if (stmt->if_false) {
 755                         endif = alloc_basic_block();
 756                         add_goto(ep, endif);
 757                         set_activeblock(ep, bb_false);
 758                         linearize_statement(ep, stmt->if_false);
 759                 }
 760                 set_activeblock(ep, endif);
 761                 break;
 762         }
 763
 764         case STMT_SWITCH: {
 765                 struct symbol *sym;
 766                 struct instruction *switch_ins;
 767                 struct basic_block *switch_end = alloc_basic_block();
 768                 pseudo_t pseudo;
 769
 770                 pseudo = linearize_expression(ep, stmt->switch_expression);
 771                 switch_ins = alloc_instruction(OP_SWITCH, NULL);
 772                 switch_ins->cond = pseudo;
 773                 add_one_insn(ep, stmt->pos, switch_ins);
 774
 775                 FOR_EACH_PTR(stmt->switch_case->symbol_list, sym) {
 776                         struct statement *case_stmt = sym->stmt;
 777                         struct basic_block *bb_case = get_bound_block(ep, sym);
 778                         struct multijmp *jmp;
 779                         int begin, end;
 780                         if (!case_stmt->case_expression) {
 781                               jmp = alloc_multijmp(bb_case, 1, 0);
 782                         } else {
 783                                 if (case_stmt->case_expression)
 784                                         begin = end = case_stmt->case_expression->value;
 785                                 if (case_stmt->case_to)
 786                                         end = case_stmt->case_to->value;
 787                                 if (begin > end)
 788                                         jmp = alloc_multijmp(bb_case, end, begin);
 789                                 else
 790                                         jmp = alloc_multijmp(bb_case, begin, end);
 791
 792                         }
 793                         add_multijmp(&switch_ins->multijmp_list, jmp);
 794                         add_bb(&bb_case->parents, ep->active);
 795                 } END_FOR_EACH_PTR;
 796
 797                 bind_label(stmt->switch_break, switch_end, stmt->pos);
 798
 799                 /* And linearize the actual statement */
 800                 linearize_statement(ep, stmt->switch_statement);
 801                 set_activeblock(ep, switch_end);
 802
 803                 break;
 804         }
 805
 806         case STMT_ITERATOR: {
 807                 struct statement  *pre_statement = stmt->iterator_pre_statement;
 808                 struct expression *pre_condition = stmt->iterator_pre_condition;
 809                 struct statement  *statement = stmt->iterator_statement;
 810                 struct statement  *post_statement = stmt->iterator_post_statement;
 811                 struct expression *post_condition = stmt->iterator_post_condition;
 812                 struct basic_block *loop_top, *loop_body, *loop_continue, *loop_end;
 813
 814                 concat_symbol_list(stmt->iterator_syms, &ep->syms);
 815                 linearize_statement(ep, pre_statement);
 816
 817                 loop_body = loop_top = alloc_basic_block();
 818                 loop_continue = alloc_basic_block();
 819                 loop_end = alloc_basic_block();
 820
 821                 if (!post_statement && (pre_condition == post_condition)) {
 822                         /*
 823                          * If it is a while loop, optimize away the post_condition.
 824                          */
 825                         post_condition = NULL;
 826                         loop_body = loop_continue;
 827                         loop_continue = loop_top;
 828                         loop_top->flags |= BB_REACHABLE;
 829                         set_activeblock(ep, loop_top);
 830                 }
 831
 832                 loop_top->flags |= BB_REACHABLE;
 833                 if (pre_condition)
 834                         linearize_cond_branch(ep, pre_condition, loop_body, loop_end);
 835
 836                 bind_label(stmt->iterator_continue, loop_continue, stmt->pos);
 837                 bind_label(stmt->iterator_break, loop_end, stmt->pos);
 838
 839                 set_activeblock(ep, loop_body);
 840                 linearize_statement(ep, statement);
 841                 add_goto(ep, loop_continue);
 842
 843                 if (post_condition) {
 844                         set_activeblock(ep, loop_continue);
 845                         linearize_statement(ep, post_statement);
 846                         linearize_cond_branch(ep, post_condition, loop_top, loop_end);
 847                 }
 848
 849                 set_activeblock(ep, loop_end);
 850                 break;
 851         }
 852
 853         default:
 854                 break;
 855         }
 856         return VOID;
 857 }
 858
 859 void mark_bb_reachable(struct basic_block *bb)
 860 {
 861         struct basic_block *child;
 862         struct terminator_iterator term;
 863         struct basic_block_list *bbstack = NULL;
 864
 865         if (!bb || bb->flags & BB_REACHABLE)
 866                 return;
 867
 868         add_bb(&bbstack, bb);
 869         while (bbstack) {
 870                 bb = delete_last_basic_block(&bbstack);
 871                 if (bb->flags & BB_REACHABLE)
 872                         continue;
 873                 bb->flags |= BB_REACHABLE;
 874                 init_terminator_iterator(last_instruction(bb->insns), &term);
 875                 while ((child=next_terminator_bb(&term))) {
 876                         if (!(child->flags & BB_REACHABLE))
 877                                 add_bb(&bbstack, child);
 878                 }
 879         }
 880 }
 881
 882 void remove_unreachable_bbs(struct basic_block_list **bblist)
 883 {
 884         struct basic_block *bb, *child;
 885         struct list_iterator iterator;
 886         struct terminator_iterator term;
 887
 888         init_iterator((struct ptr_list **) bblist, &iterator, 0);
 889         while((bb=next_basic_block(&iterator)))
 890                 bb->flags &= ~BB_REACHABLE;
 891
 892         init_iterator((struct ptr_list **) bblist, &iterator, 0);
 893         mark_bb_reachable(next_basic_block(&iterator));
 894         while((bb=next_basic_block(&iterator))) {
 895                 if (bb->flags & BB_REACHABLE)
 896                         continue;
 897                 init_terminator_iterator(last_instruction(bb->insns), &term);
 898                 while ((child=next_terminator_bb(&term)))
 899                         replace_basic_block_list(&child->parents, bb, NULL);
 900                 delete_iterator(&iterator);
 901         }
 902 }
 903
 904 void pack_basic_blocks(struct basic_block_list **bblist)
 905 {
 906         struct basic_block *child, *bb, *parent;
 907         struct list_iterator iterator;
 908         struct terminator_iterator term;
 909         struct instruction *jmp;
 910
 911         remove_unreachable_bbs(bblist);
 912         init_bb_iterator(bblist, &iterator, 0);
 913         while((bb=next_basic_block(&iterator))) {
 914                 if (is_branch_goto(jmp=first_instruction(bb->insns))) {
 915                         /*
 916                          * This is an empty goto block. Transfer the parents' terminator
 917                          * to target directly.
 918                          */
 919                         struct list_iterator it_parents;
 920                         struct basic_block *target;
 921
 922                         target = jmp->bb_true ? jmp->bb_true : jmp->bb_false;
 923                         replace_basic_block_list(&target->parents, bb, NULL);
 924                         init_bb_iterator(&bb->parents, &it_parents, 0);
 925                         while((parent=next_basic_block(&it_parents))) {
 926                                 init_terminator_iterator(last_instruction(parent->insns), &term);
 927                                 while ((child=next_terminator_bb(&term))) {
 928                                         if (child == bb) {
 929                                                 replace_terminator_bb(&term, target);
 930                                                 add_bb(&target->parents, parent);
 931                                         }
 932                                 }
 933                         }
 934                         delete_iterator(&iterator);
 935                         continue;
 936                 }
 937
 938                 if (bb_list_size(bb->parents)!=1)
 939                        continue;
 940                 parent = first_basic_block(bb->parents);
 941                 if (parent!=bb && is_branch_goto(last_instruction(parent->insns))) {
 942                         /*
 943                          * Combine this block with the parent.
 944                          */
 945                         delete_last_instruction(&parent->insns);
 946                         concat_instruction_list(bb->insns, &parent->insns);
 947                         init_terminator_iterator(last_instruction(bb->insns), &term);
 948                         while ((child=next_terminator_bb(&term)))
 949                                 replace_basic_block_list(&child->parents, bb, parent);
 950                         delete_iterator(&iterator);
 951                 }
 952         }
 953 }
 954
 955 void linearize_symbol(struct symbol *sym)
 956 {
 957         struct symbol *base_type;
 958
 959         if (!sym)
 960                 return;
 961         base_type = sym->ctype.base_type;
 962         if (!base_type)
 963                 return;
 964         if (base_type->type == SYM_FN) {
 965                 if (base_type->stmt) {
 966                         struct entrypoint *ep = alloc_entrypoint();
 967                         struct basic_block *bb = alloc_basic_block();
 968
 969                         ep->name = sym;
 970                         bb->flags |= BB_REACHABLE;
 971                         set_activeblock(ep, bb);
 972                         concat_symbol_list(base_type->arguments, &ep->syms);
 973                         linearize_statement(ep, base_type->stmt);
 974                         pack_basic_blocks(&ep->bbs);
 975                         show_entry(ep);
 976                 }
 977         }
 978 }