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