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