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