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