linearize.c

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