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