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