simplify.c

   1 /*
   2  * Simplify - do instruction simplification before CSE
   3  *
   4  * Copyright (C) 2004 Linus Torvalds
   5  */
   6
   7 #include <assert.h>
   8
   9 #include "parse.h"
  10 #include "expression.h"
  11 #include "linearize.h"
  12 #include "flow.h"
  13 #include "symbol.h"
  14
  15 /* Find the trivial parent for a phi-source */
  16 static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseudo)
  17 {
  18         /* Can't go upwards if the pseudo is defined in the bb it came from.. */
  19         if (pseudo->type == PSEUDO_REG) {
  20                 struct instruction *def = pseudo->def;
  21                 if (def->bb == source)
  22                         return source;
  23         }
  24         if (bb_list_size(source->children) != 1 || bb_list_size(source->parents) != 1)
  25                 return source;
  26         return first_basic_block(source->parents);
  27 }
  28
  29 static int if_convert_phi(struct instruction *insn)
  30 {
  31         pseudo_t array[3];
  32         struct basic_block *parents[3];
  33         struct basic_block *bb, *bb1, *bb2, *source;
  34         struct instruction *br;
  35         pseudo_t p1, p2;
  36
  37         bb = insn->bb;
  38         if (linearize_ptr_list((struct ptr_list *)insn->phi_list, (void **)array, 3) != 2)
  39                 return 0;
  40         if (linearize_ptr_list((struct ptr_list *)bb->parents, (void **)parents, 3) != 2)
  41                 return 0;
  42         p1 = array[0]->def->src1;
  43         bb1 = array[0]->def->bb;
  44         p2 = array[1]->def->src1;
  45         bb2 = array[1]->def->bb;
  46
  47         /* Only try the simple "direct parents" case */
  48         if ((bb1 != parents[0] || bb2 != parents[1]) &&
  49             (bb1 != parents[1] || bb2 != parents[0]))
  50                 return 0;
  51
  52         /*
  53          * See if we can find a common source for this..
  54          */
  55         source = phi_parent(bb1, p1);
  56         if (source != phi_parent(bb2, p2))
  57                 return 0;
  58
  59         /*
  60          * Cool. We now know that 'source' is the exclusive
  61          * parent of both phi-nodes, so the exit at the
  62          * end of it fully determines which one it is, and
  63          * we can turn it into a select.
  64          *
  65          * HOWEVER, right now we only handle regular
  66          * conditional branches. No multijumps or computed
  67          * stuff. Verify that here.
  68          */
  69         br = last_instruction(source->insns);
  70         if (!br || br->opcode != OP_BR)
  71                 return 0;
  72
  73         assert(br->cond);
  74         assert(br->bb_false);
  75
  76         /*
  77          * We're in business. Match up true/false with p1/p2.
  78          */
  79         if (br->bb_true == bb2 || br->bb_false == bb1) {
  80                 pseudo_t p = p1;
  81                 p1 = p2;
  82                 p2 = p;
  83         }
  84
  85         /*
  86          * OK, we can now replace that last
  87          *
  88          *      br cond, a, b
  89          *
  90          * with the sequence
  91          *
  92          *      setcc cond
  93          *      select pseudo, p1, p2
  94          *      br cond, a, b
  95          *
  96          * and remove the phi-node. If it then
  97          * turns out that 'a' or 'b' is entirely
  98          * empty (common case), and now no longer
  99          * a phi-source, we'll be able to simplify
 100          * the conditional branch too.
 101          */
 102         insert_select(source, br, insn, p1, p2);
 103         kill_instruction(insn);
 104         return REPEAT_CSE;
 105 }
 106
 107 static int clean_up_phi(struct instruction *insn)
 108 {
 109         pseudo_t phi;
 110         struct instruction *last;
 111         int same;
 112
 113         last = NULL;
 114         same = 1;
 115         FOR_EACH_PTR(insn->phi_list, phi) {
 116                 struct instruction *def;
 117                 if (phi == VOID)
 118                         continue;
 119                 def = phi->def;
 120                 if (def->src1 == VOID || !def->bb)
 121                         continue;
 122                 if (last) {
 123                         if (last->src1 != def->src1)
 124                                 same = 0;
 125                         continue;
 126                 }
 127                 last = def;
 128         } END_FOR_EACH_PTR(phi);
 129
 130         if (same) {
 131                 pseudo_t pseudo = last ? last->src1 : VOID;
 132                 convert_instruction_target(insn, pseudo);
 133                 kill_instruction(insn);
 134                 return REPEAT_CSE;
 135         }
 136
 137         return if_convert_phi(insn);
 138 }
 139
 140 static int delete_pseudo_user_list_entry(struct pseudo_user_list **list, pseudo_t *entry, int count)
 141 {
 142         struct pseudo_user *pu;
 143
 144         FOR_EACH_PTR(*list, pu) {
 145                 if (pu->userp == entry) {
 146                         DELETE_CURRENT_PTR(pu);
 147                         if (!--count)
 148                                 goto out;
 149                 }
 150         } END_FOR_EACH_PTR(pu);
 151         assert(count <= 0);
 152 out:
 153         pack_ptr_list((struct ptr_list **)list);
 154         return count;
 155 }
 156
 157 static inline void remove_usage(pseudo_t p, pseudo_t *usep)
 158 {
 159         if (has_use_list(p)) {
 160                 delete_pseudo_user_list_entry(&p->users, usep, 1);
 161                 if (!p->users)
 162                         kill_instruction(p->def);
 163         }
 164 }
 165
 166 void kill_use(pseudo_t *usep)
 167 {
 168         if (usep) {
 169                 pseudo_t p = *usep;
 170                 *usep = VOID;
 171                 remove_usage(p, usep);
 172         }
 173 }
 174
 175 static void kill_use_list(struct pseudo_list *list)
 176 {
 177         pseudo_t p;
 178         FOR_EACH_PTR(list, p) {
 179                 if (p == VOID)
 180                         continue;
 181                 kill_use(THIS_ADDRESS(p));
 182         } END_FOR_EACH_PTR(p);
 183 }
 184
 185 /*
 186  * kill an instruction:
 187  * - remove it from its bb
 188  * - remove the usage of all its operands
 189  * If forse is zero, the normal case, the function only for
 190  * instructions free of (possible) side-effects. Otherwise
 191  * the function does that unconditionally (must only be used
 192  * for unreachable instructions.
 193  */
 194 void kill_insn(struct instruction *insn, int force)
 195 {
 196         if (!insn || !insn->bb)
 197                 return;
 198
 199         switch (insn->opcode) {
 200         case OP_SEL:
 201         case OP_RANGE:
 202                 kill_use(&insn->src3);
 203                 /* fall through */
 204
 205         case OP_BINARY ... OP_BINCMP_END:
 206                 kill_use(&insn->src2);
 207                 /* fall through */
 208
 209         case OP_CAST:
 210         case OP_SCAST:
 211         case OP_FPCAST:
 212         case OP_PTRCAST:
 213         case OP_SETVAL:
 214         case OP_NOT: case OP_NEG:
 215         case OP_SLICE:
 216                 kill_use(&insn->src1);
 217                 break;
 218
 219         case OP_PHI:
 220                 kill_use_list(insn->phi_list);
 221                 break;
 222         case OP_PHISOURCE:
 223                 kill_use(&insn->phi_src);
 224                 break;
 225
 226         case OP_SYMADDR:
 227                 repeat_phase |= REPEAT_SYMBOL_CLEANUP;
 228                 break;
 229
 230         case OP_BR:
 231                 if (!insn->bb_true || !insn->bb_false)
 232                         break;
 233                 /* fall through */
 234
 235         case OP_COMPUTEDGOTO:
 236                 kill_use(&insn->cond);
 237                 break;
 238
 239         case OP_CALL:
 240                 if (!force) {
 241                         /* a "pure" function can be killed too */
 242                         if (!(insn->func->type == PSEUDO_SYM))
 243                                 return;
 244                         if (!(insn->func->sym->ctype.modifiers & MOD_PURE))
 245                                 return;
 246                 }
 247                 kill_use_list(insn->arguments);
 248                 break;
 249
 250         case OP_ENTRY:
 251                 /* ignore */
 252                 return;
 253
 254         default:
 255                 break;
 256         }
 257
 258         insn->bb = NULL;
 259         repeat_phase |= REPEAT_CSE;
 260         return;
 261 }
 262
 263 /*
 264  * Kill trivially dead instructions
 265  */
 266 static int dead_insn(struct instruction *insn, pseudo_t *src1, pseudo_t *src2, pseudo_t *src3)
 267 {
 268         struct pseudo_user *pu;
 269         FOR_EACH_PTR(insn->target->users, pu) {
 270                 if (*pu->userp != VOID)
 271                         return 0;
 272         } END_FOR_EACH_PTR(pu);
 273
 274         insn->bb = NULL;
 275         kill_use(src1);
 276         kill_use(src2);
 277         kill_use(src3);
 278         return REPEAT_CSE;
 279 }
 280
 281 static inline int constant(pseudo_t pseudo)
 282 {
 283         return pseudo->type == PSEUDO_VAL;
 284 }
 285
 286 static int replace_with_pseudo(struct instruction *insn, pseudo_t pseudo)
 287 {
 288         convert_instruction_target(insn, pseudo);
 289
 290         switch (insn->opcode) {
 291         case OP_SEL:
 292         case OP_RANGE:
 293                 kill_use(&insn->src3);
 294         case OP_BINARY ... OP_BINCMP_END:
 295                 kill_use(&insn->src2);
 296         case OP_NOT:
 297         case OP_NEG:
 298         case OP_SYMADDR:
 299         case OP_CAST:
 300         case OP_SCAST:
 301         case OP_FPCAST:
 302         case OP_PTRCAST:
 303                 kill_use(&insn->src1);
 304                 break;
 305
 306         default:
 307                 assert(0);
 308         }
 309         insn->bb = NULL;
 310         return REPEAT_CSE;
 311 }
 312
 313 static unsigned int value_size(long long value)
 314 {
 315         value >>= 8;
 316         if (!value)
 317                 return 8;
 318         value >>= 8;
 319         if (!value)
 320                 return 16;
 321         value >>= 16;
 322         if (!value)
 323                 return 32;
 324         return 64;
 325 }
 326
 327 /*
 328  * Try to determine the maximum size of bits in a pseudo.
 329  *
 330  * Right now this only follow casts and constant values, but we
 331  * could look at things like logical 'and' instructions etc.
 332  */
 333 static unsigned int operand_size(struct instruction *insn, pseudo_t pseudo)
 334 {
 335         unsigned int size = insn->size;
 336
 337         if (pseudo->type == PSEUDO_REG) {
 338                 struct instruction *src = pseudo->def;
 339                 if (src && src->opcode == OP_CAST && src->orig_type) {
 340                         unsigned int orig_size = src->orig_type->bit_size;
 341                         if (orig_size < size)
 342                                 size = orig_size;
 343                 }
 344         }
 345         if (pseudo->type == PSEUDO_VAL) {
 346                 unsigned int orig_size = value_size(pseudo->value);
 347                 if (orig_size < size)
 348                         size = orig_size;
 349         }
 350         return size;
 351 }
 352
 353 static int simplify_asr(struct instruction *insn, pseudo_t pseudo, long long value)
 354 {
 355         unsigned int size = operand_size(insn, pseudo);
 356
 357         if (value >= size) {
 358                 warning(insn->pos, "right shift by bigger than source value");
 359                 return replace_with_pseudo(insn, value_pseudo(0));
 360         }
 361         if (!value)
 362                 return replace_with_pseudo(insn, pseudo);
 363         return 0;
 364 }
 365
 366 static int simplify_mul_div(struct instruction *insn, long long value)
 367 {
 368         unsigned long long sbit = 1ULL << (insn->size - 1);
 369         unsigned long long bits = sbit | (sbit - 1);
 370
 371         if (value == 1)
 372                 return replace_with_pseudo(insn, insn->src1);
 373
 374         switch (insn->opcode) {
 375         case OP_MULS:
 376         case OP_MULU:
 377                 if (value == 0)
 378                         return replace_with_pseudo(insn, insn->src2);
 379         /* Fall through */
 380         case OP_DIVS:
 381                 if (!(value & sbit))    // positive
 382                         break;
 383
 384                 value |= ~bits;
 385                 if (value == -1) {
 386                         insn->opcode = OP_NEG;
 387                         return REPEAT_CSE;
 388                 }
 389         }
 390
 391         return 0;
 392 }
 393
 394 static int compare_opcode(int opcode, int inverse)
 395 {
 396         if (!inverse)
 397                 return opcode;
 398
 399         switch (opcode) {
 400         case OP_SET_EQ: return OP_SET_NE;
 401         case OP_SET_NE: return OP_SET_EQ;
 402
 403         case OP_SET_LT: return OP_SET_GE;
 404         case OP_SET_LE: return OP_SET_GT;
 405         case OP_SET_GT: return OP_SET_LE;
 406         case OP_SET_GE: return OP_SET_LT;
 407
 408         case OP_SET_A:  return OP_SET_BE;
 409         case OP_SET_AE: return OP_SET_B;
 410         case OP_SET_B:  return OP_SET_AE;
 411         case OP_SET_BE: return OP_SET_A;
 412
 413         default:
 414                 return opcode;
 415         }
 416 }
 417
 418 static int simplify_seteq_setne(struct instruction *insn, long long value)
 419 {
 420         struct instruction *def = insn->src1->def;
 421         pseudo_t src1, src2;
 422         int inverse;
 423         int opcode;
 424
 425         if (value != 0 && value != 1)
 426                 return 0;
 427
 428         if (!def)
 429                 return 0;
 430
 431         inverse = (insn->opcode == OP_SET_NE) == value;
 432         opcode = def->opcode;
 433         switch (opcode) {
 434         case OP_BINCMP ... OP_BINCMP_END:
 435                 // Convert:
 436                 //      setcc.n %t <- %a, %b
 437                 //      setne.m %r <- %t, $0
 438                 // into:
 439                 //      setcc.n %t <- %a, %b
 440                 //      setcc.m %r <- %a, $b
 441                 // and similar for setne/eq ... 0/1
 442                 src1 = def->src1;
 443                 src2 = def->src2;
 444                 remove_usage(insn->src1, &insn->src1);
 445                 insn->opcode = compare_opcode(opcode, inverse);
 446                 use_pseudo(insn, src1, &insn->src1);
 447                 use_pseudo(insn, src2, &insn->src2);
 448                 return REPEAT_CSE;
 449
 450         default:
 451                 return 0;
 452         }
 453 }
 454
 455 static int simplify_constant_rightside(struct instruction *insn)
 456 {
 457         long long value = insn->src2->value;
 458
 459         switch (insn->opcode) {
 460         case OP_OR_BOOL:
 461                 if (value == 1)
 462                         return replace_with_pseudo(insn, insn->src2);
 463                 goto case_neutral_zero;
 464
 465         case OP_SUB:
 466                 if (value) {
 467                         insn->opcode = OP_ADD;
 468                         insn->src2 = value_pseudo(-value);
 469                         return REPEAT_CSE;
 470                 }
 471         /* Fall through */
 472         case OP_ADD:
 473         case OP_OR: case OP_XOR:
 474         case OP_SHL:
 475         case OP_LSR:
 476         case_neutral_zero:
 477                 if (!value)
 478                         return replace_with_pseudo(insn, insn->src1);
 479                 return 0;
 480         case OP_ASR:
 481                 return simplify_asr(insn, insn->src1, value);
 482
 483         case OP_MODU: case OP_MODS:
 484                 if (value == 1)
 485                         return replace_with_pseudo(insn, value_pseudo(0));
 486                 return 0;
 487
 488         case OP_DIVU: case OP_DIVS:
 489         case OP_MULU: case OP_MULS:
 490                 return simplify_mul_div(insn, value);
 491
 492         case OP_AND_BOOL:
 493                 if (value == 1)
 494                         return replace_with_pseudo(insn, insn->src1);
 495         /* Fall through */
 496         case OP_AND:
 497                 if (!value)
 498                         return replace_with_pseudo(insn, insn->src2);
 499                 return 0;
 500
 501         case OP_SET_NE:
 502         case OP_SET_EQ:
 503                 return simplify_seteq_setne(insn, value);
 504         }
 505         return 0;
 506 }
 507
 508 static int simplify_constant_leftside(struct instruction *insn)
 509 {
 510         long long value = insn->src1->value;
 511
 512         switch (insn->opcode) {
 513         case OP_ADD: case OP_OR: case OP_XOR:
 514                 if (!value)
 515                         return replace_with_pseudo(insn, insn->src2);
 516                 return 0;
 517
 518         case OP_SHL:
 519         case OP_LSR: case OP_ASR:
 520         case OP_AND:
 521         case OP_MULU: case OP_MULS:
 522                 if (!value)
 523                         return replace_with_pseudo(insn, insn->src1);
 524                 return 0;
 525         }
 526         return 0;
 527 }
 528
 529 static int simplify_constant_binop(struct instruction *insn)
 530 {
 531         /* FIXME! Verify signs and sizes!! */
 532         long long left = insn->src1->value;
 533         long long right = insn->src2->value;
 534         unsigned long long ul, ur;
 535         long long res, mask, bits;
 536
 537         mask = 1ULL << (insn->size-1);
 538         bits = mask | (mask-1);
 539
 540         if (left & mask)
 541                 left |= ~bits;
 542         if (right & mask)
 543                 right |= ~bits;
 544         ul = left & bits;
 545         ur = right & bits;
 546
 547         switch (insn->opcode) {
 548         case OP_ADD:
 549                 res = left + right;
 550                 break;
 551         case OP_SUB:
 552                 res = left - right;
 553                 break;
 554         case OP_MULU:
 555                 res = ul * ur;
 556                 break;
 557         case OP_MULS:
 558                 res = left * right;
 559                 break;
 560         case OP_DIVU:
 561                 if (!ur)
 562                         return 0;
 563                 res = ul / ur;
 564                 break;
 565         case OP_DIVS:
 566                 if (!right)
 567                         return 0;
 568                 if (left == mask && right == -1)
 569                         return 0;
 570                 res = left / right;
 571                 break;
 572         case OP_MODU:
 573                 if (!ur)
 574                         return 0;
 575                 res = ul % ur;
 576                 break;
 577         case OP_MODS:
 578                 if (!right)
 579                         return 0;
 580                 if (left == mask && right == -1)
 581                         return 0;
 582                 res = left % right;
 583                 break;
 584         case OP_SHL:
 585                 res = left << right;
 586                 break;
 587         case OP_LSR:
 588                 res = ul >> ur;
 589                 break;
 590         case OP_ASR:
 591                 res = left >> right;
 592                 break;
 593        /* Logical */
 594         case OP_AND:
 595                 res = left & right;
 596                 break;
 597         case OP_OR:
 598                 res = left | right;
 599                 break;
 600         case OP_XOR:
 601                 res = left ^ right;
 602                 break;
 603         case OP_AND_BOOL:
 604                 res = left && right;
 605                 break;
 606         case OP_OR_BOOL:
 607                 res = left || right;
 608                 break;
 609
 610         /* Binary comparison */
 611         case OP_SET_EQ:
 612                 res = left == right;
 613                 break;
 614         case OP_SET_NE:
 615                 res = left != right;
 616                 break;
 617         case OP_SET_LE:
 618                 res = left <= right;
 619                 break;
 620         case OP_SET_GE:
 621                 res = left >= right;
 622                 break;
 623         case OP_SET_LT:
 624                 res = left < right;
 625                 break;
 626         case OP_SET_GT:
 627                 res = left > right;
 628                 break;
 629         case OP_SET_B:
 630                 res = ul < ur;
 631                 break;
 632         case OP_SET_A:
 633                 res = ul > ur;
 634                 break;
 635         case OP_SET_BE:
 636                 res = ul <= ur;
 637                 break;
 638         case OP_SET_AE:
 639                 res = ul >= ur;
 640                 break;
 641         default:
 642                 return 0;
 643         }
 644         res &= bits;
 645
 646         replace_with_pseudo(insn, value_pseudo(res));
 647         return REPEAT_CSE;
 648 }
 649
 650 static int simplify_binop_same_args(struct instruction *insn, pseudo_t arg)
 651 {
 652         switch (insn->opcode) {
 653         case OP_SET_NE:
 654         case OP_SET_LT: case OP_SET_GT:
 655         case OP_SET_B:  case OP_SET_A:
 656                 if (Wtautological_compare)
 657                         warning(insn->pos, "self-comparison always evaluates to false");
 658         case OP_SUB:
 659         case OP_XOR:
 660                 return replace_with_pseudo(insn, value_pseudo(0));
 661
 662         case OP_SET_EQ:
 663         case OP_SET_LE: case OP_SET_GE:
 664         case OP_SET_BE: case OP_SET_AE:
 665                 if (Wtautological_compare)
 666                         warning(insn->pos, "self-comparison always evaluates to true");
 667                 return replace_with_pseudo(insn, value_pseudo(1));
 668
 669         case OP_AND:
 670         case OP_OR:
 671                 return replace_with_pseudo(insn, arg);
 672
 673         case OP_AND_BOOL:
 674         case OP_OR_BOOL:
 675                 remove_usage(arg, &insn->src2);
 676                 insn->src2 = value_pseudo(0);
 677                 insn->opcode = OP_SET_NE;
 678                 return REPEAT_CSE;
 679
 680         default:
 681                 break;
 682         }
 683
 684         return 0;
 685 }
 686
 687 static int simplify_binop(struct instruction *insn)
 688 {
 689         if (dead_insn(insn, &insn->src1, &insn->src2, NULL))
 690                 return REPEAT_CSE;
 691         if (constant(insn->src1)) {
 692                 if (constant(insn->src2))
 693                         return simplify_constant_binop(insn);
 694                 return simplify_constant_leftside(insn);
 695         }
 696         if (constant(insn->src2))
 697                 return simplify_constant_rightside(insn);
 698         if (insn->src1 == insn->src2)
 699                 return simplify_binop_same_args(insn, insn->src1);
 700         return 0;
 701 }
 702
 703 static void switch_pseudo(struct instruction *insn1, pseudo_t *pp1, struct instruction *insn2, pseudo_t *pp2)
 704 {
 705         pseudo_t p1 = *pp1, p2 = *pp2;
 706
 707         use_pseudo(insn1, p2, pp1);
 708         use_pseudo(insn2, p1, pp2);
 709         remove_usage(p1, pp1);
 710         remove_usage(p2, pp2);
 711 }
 712
 713 static int canonical_order(pseudo_t p1, pseudo_t p2)
 714 {
 715         /* symbol/constants on the right */
 716         if (p1->type == PSEUDO_VAL)
 717                 return p2->type == PSEUDO_VAL;
 718
 719         if (p1->type == PSEUDO_SYM)
 720                 return p2->type == PSEUDO_SYM || p2->type == PSEUDO_VAL;
 721
 722         return 1;
 723 }
 724
 725 static int simplify_commutative_binop(struct instruction *insn)
 726 {
 727         if (!canonical_order(insn->src1, insn->src2)) {
 728                 switch_pseudo(insn, &insn->src1, insn, &insn->src2);
 729                 return REPEAT_CSE;
 730         }
 731         return 0;
 732 }
 733
 734 static inline int simple_pseudo(pseudo_t pseudo)
 735 {
 736         return pseudo->type == PSEUDO_VAL || pseudo->type == PSEUDO_SYM;
 737 }
 738
 739 static int simplify_associative_binop(struct instruction *insn)
 740 {
 741         struct instruction *def;
 742         pseudo_t pseudo = insn->src1;
 743
 744         if (!simple_pseudo(insn->src2))
 745                 return 0;
 746         if (pseudo->type != PSEUDO_REG)
 747                 return 0;
 748         def = pseudo->def;
 749         if (def == insn)
 750                 return 0;
 751         if (def->opcode != insn->opcode)
 752                 return 0;
 753         if (!simple_pseudo(def->src2))
 754                 return 0;
 755         if (ptr_list_size((struct ptr_list *)def->target->users) != 1)
 756                 return 0;
 757         switch_pseudo(def, &def->src1, insn, &insn->src2);
 758         return REPEAT_CSE;
 759 }
 760
 761 static int simplify_constant_unop(struct instruction *insn)
 762 {
 763         long long val = insn->src1->value;
 764         long long res, mask;
 765
 766         switch (insn->opcode) {
 767         case OP_NOT:
 768                 res = ~val;
 769                 break;
 770         case OP_NEG:
 771                 res = -val;
 772                 break;
 773         default:
 774                 return 0;
 775         }
 776         mask = 1ULL << (insn->size-1);
 777         res &= mask | (mask-1);
 778
 779         replace_with_pseudo(insn, value_pseudo(res));
 780         return REPEAT_CSE;
 781 }
 782
 783 static int simplify_unop(struct instruction *insn)
 784 {
 785         if (dead_insn(insn, &insn->src1, NULL, NULL))
 786                 return REPEAT_CSE;
 787         if (constant(insn->src1))
 788                 return simplify_constant_unop(insn);
 789
 790         switch (insn->opcode) {
 791                 struct instruction *def;
 792
 793         case OP_NOT:
 794                 def = insn->src->def;
 795                 if (def && def->opcode == OP_NOT)
 796                         return replace_with_pseudo(insn, def->src);
 797                 break;
 798         case OP_NEG:
 799                 def = insn->src->def;
 800                 if (def && def->opcode == OP_NEG)
 801                         return replace_with_pseudo(insn, def->src);
 802                 break;
 803         default:
 804                 return 0;
 805         }
 806         return 0;
 807 }
 808
 809 static int simplify_one_memop(struct instruction *insn, pseudo_t orig)
 810 {
 811         pseudo_t addr = insn->src;
 812         pseudo_t new, off;
 813
 814         if (addr->type == PSEUDO_REG) {
 815                 struct instruction *def = addr->def;
 816                 if (def->opcode == OP_SYMADDR && def->src) {
 817                         kill_use(&insn->src);
 818                         use_pseudo(insn, def->src, &insn->src);
 819                         return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
 820                 }
 821                 if (def->opcode == OP_ADD) {
 822                         new = def->src1;
 823                         off = def->src2;
 824                         if (constant(off))
 825                                 goto offset;
 826                         new = off;
 827                         off = def->src1;
 828                         if (constant(off))
 829                                 goto offset;
 830                         return 0;
 831                 }
 832         }
 833         return 0;
 834
 835 offset:
 836         /* Invalid code */
 837         if (new == orig) {
 838                 if (new == VOID)
 839                         return 0;
 840                 new = VOID;
 841                 warning(insn->pos, "crazy programmer");
 842         }
 843         insn->offset += off->value;
 844         use_pseudo(insn, new, &insn->src);
 845         remove_usage(addr, &insn->src);
 846         return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
 847 }
 848
 849 /*
 850  * We walk the whole chain of adds/subs backwards. That's not
 851  * only more efficient, but it allows us to find loops.
 852  */
 853 static int simplify_memop(struct instruction *insn)
 854 {
 855         int one, ret = 0;
 856         pseudo_t orig = insn->src;
 857
 858         do {
 859                 one = simplify_one_memop(insn, orig);
 860                 ret |= one;
 861         } while (one);
 862         return ret;
 863 }
 864
 865 static long long get_cast_value(long long val, int old_size, int new_size, int sign)
 866 {
 867         long long mask;
 868
 869         if (sign && new_size > old_size) {
 870                 mask = 1 << (old_size-1);
 871                 if (val & mask)
 872                         val |= ~(mask | (mask-1));
 873         }
 874         mask = 1 << (new_size-1);
 875         return val & (mask | (mask-1));
 876 }
 877
 878 static int simplify_cast(struct instruction *insn)
 879 {
 880         struct symbol *orig_type;
 881         int orig_size, size;
 882         pseudo_t src;
 883
 884         if (dead_insn(insn, &insn->src, NULL, NULL))
 885                 return REPEAT_CSE;
 886
 887         orig_type = insn->orig_type;
 888         if (!orig_type)
 889                 return 0;
 890
 891         /* Keep casts with pointer on either side (not only case of OP_PTRCAST) */
 892         if (is_ptr_type(orig_type) || is_ptr_type(insn->type))
 893                 return 0;
 894
 895         orig_size = orig_type->bit_size;
 896         size = insn->size;
 897         src = insn->src;
 898
 899         /* A cast of a constant? */
 900         if (constant(src)) {
 901                 int sign = orig_type->ctype.modifiers & MOD_SIGNED;
 902                 long long val = get_cast_value(src->value, orig_size, size, sign);
 903                 src = value_pseudo(val);
 904                 goto simplify;
 905         }
 906
 907         /* A cast of a "and" might be a no-op.. */
 908         if (src->type == PSEUDO_REG) {
 909                 struct instruction *def = src->def;
 910                 if (def->opcode == OP_AND && def->size >= size) {
 911                         pseudo_t val = def->src2;
 912                         if (val->type == PSEUDO_VAL) {
 913                                 unsigned long long value = val->value;
 914                                 if (!(value >> (size-1)))
 915                                         goto simplify;
 916                         }
 917                 }
 918         }
 919
 920         if (size == orig_size) {
 921                 int op = (orig_type->ctype.modifiers & MOD_SIGNED) ? OP_SCAST : OP_CAST;
 922                 if (insn->opcode == op)
 923                         goto simplify;
 924         }
 925
 926         return 0;
 927
 928 simplify:
 929         return replace_with_pseudo(insn, src);
 930 }
 931
 932 static int simplify_select(struct instruction *insn)
 933 {
 934         pseudo_t cond, src1, src2;
 935
 936         if (dead_insn(insn, &insn->src1, &insn->src2, &insn->src3))
 937                 return REPEAT_CSE;
 938
 939         cond = insn->src1;
 940         src1 = insn->src2;
 941         src2 = insn->src3;
 942         if (constant(cond) || src1 == src2) {
 943                 pseudo_t *kill, take;
 944                 kill_use(&insn->src1);
 945                 take = cond->value ? src1 : src2;
 946                 kill = cond->value ? &insn->src3 : &insn->src2;
 947                 kill_use(kill);
 948                 replace_with_pseudo(insn, take);
 949                 return REPEAT_CSE;
 950         }
 951         if (constant(src1) && constant(src2)) {
 952                 long long val1 = src1->value;
 953                 long long val2 = src2->value;
 954
 955                 /* The pair 0/1 is special - replace with SETNE/SETEQ */
 956                 if ((val1 | val2) == 1) {
 957                         int opcode = OP_SET_EQ;
 958                         if (val1) {
 959                                 src1 = src2;
 960                                 opcode = OP_SET_NE;
 961                         }
 962                         insn->opcode = opcode;
 963                         /* insn->src1 is already cond */
 964                         insn->src2 = src1; /* Zero */
 965                         return REPEAT_CSE;
 966                 }
 967         }
 968         return 0;
 969 }
 970
 971 static int is_in_range(pseudo_t src, long long low, long long high)
 972 {
 973         long long value;
 974
 975         switch (src->type) {
 976         case PSEUDO_VAL:
 977                 value = src->value;
 978                 return value >= low && value <= high;
 979         default:
 980                 return 0;
 981         }
 982 }
 983
 984 static int simplify_range(struct instruction *insn)
 985 {
 986         pseudo_t src1, src2, src3;
 987
 988         src1 = insn->src1;
 989         src2 = insn->src2;
 990         src3 = insn->src3;
 991         if (src2->type != PSEUDO_VAL || src3->type != PSEUDO_VAL)
 992                 return 0;
 993         if (is_in_range(src1, src2->value, src3->value)) {
 994                 kill_instruction(insn);
 995                 return REPEAT_CSE;
 996         }
 997         return 0;
 998 }
 999
1000 /*
1001  * Simplify "set_ne/eq $0 + br"
1002  */
1003 static int simplify_cond_branch(struct instruction *br, pseudo_t cond, struct instruction *def, pseudo_t *pp)
1004 {
1005         use_pseudo(br, *pp, &br->cond);
1006         remove_usage(cond, &br->cond);
1007         if (def->opcode == OP_SET_EQ) {
1008                 struct basic_block *true = br->bb_true;
1009                 struct basic_block *false = br->bb_false;
1010                 br->bb_false = true;
1011                 br->bb_true = false;
1012         }
1013         return REPEAT_CSE;
1014 }
1015
1016 static int simplify_branch(struct instruction *insn)
1017 {
1018         pseudo_t cond = insn->cond;
1019
1020         if (!cond)
1021                 return 0;
1022
1023         /* Constant conditional */
1024         if (constant(cond)) {
1025                 insert_branch(insn->bb, insn, cond->value ? insn->bb_true : insn->bb_false);
1026                 return REPEAT_CSE;
1027         }
1028
1029         /* Same target? */
1030         if (insn->bb_true == insn->bb_false) {
1031                 struct basic_block *bb = insn->bb;
1032                 struct basic_block *target = insn->bb_false;
1033                 remove_bb_from_list(&target->parents, bb, 1);
1034                 remove_bb_from_list(&bb->children, target, 1);
1035                 insn->bb_false = NULL;
1036                 kill_use(&insn->cond);
1037                 insn->cond = NULL;
1038                 return REPEAT_CSE;
1039         }
1040
1041         /* Conditional on a SETNE $0 or SETEQ $0 */
1042         if (cond->type == PSEUDO_REG) {
1043                 struct instruction *def = cond->def;
1044
1045                 if (def->opcode == OP_SET_NE || def->opcode == OP_SET_EQ) {
1046                         if (constant(def->src1) && !def->src1->value)
1047                                 return simplify_cond_branch(insn, cond, def, &def->src2);
1048                         if (constant(def->src2) && !def->src2->value)
1049                                 return simplify_cond_branch(insn, cond, def, &def->src1);
1050                 }
1051                 if (def->opcode == OP_SEL) {
1052                         if (constant(def->src2) && constant(def->src3)) {
1053                                 long long val1 = def->src2->value;
1054                                 long long val2 = def->src3->value;
1055                                 if (!val1 && !val2) {
1056                                         insert_branch(insn->bb, insn, insn->bb_false);
1057                                         return REPEAT_CSE;
1058                                 }
1059                                 if (val1 && val2) {
1060                                         insert_branch(insn->bb, insn, insn->bb_true);
1061                                         return REPEAT_CSE;
1062                                 }
1063                                 if (val2) {
1064                                         struct basic_block *true = insn->bb_true;
1065                                         struct basic_block *false = insn->bb_false;
1066                                         insn->bb_false = true;
1067                                         insn->bb_true = false;
1068                                 }
1069                                 use_pseudo(insn, def->src1, &insn->cond);
1070                                 remove_usage(cond, &insn->cond);
1071                                 return REPEAT_CSE;
1072                         }
1073                 }
1074                 if (def->opcode == OP_CAST || def->opcode == OP_SCAST) {
1075                         int orig_size = def->orig_type ? def->orig_type->bit_size : 0;
1076                         if (def->size > orig_size) {
1077                                 use_pseudo(insn, def->src, &insn->cond);
1078                                 remove_usage(cond, &insn->cond);
1079                                 return REPEAT_CSE;
1080                         }
1081                 }
1082         }
1083         return 0;
1084 }
1085
1086 static int simplify_switch(struct instruction *insn)
1087 {
1088         pseudo_t cond = insn->cond;
1089         long long val;
1090         struct multijmp *jmp;
1091
1092         if (!constant(cond))
1093                 return 0;
1094         val = insn->cond->value;
1095
1096         FOR_EACH_PTR(insn->multijmp_list, jmp) {
1097                 /* Default case */
1098                 if (jmp->begin > jmp->end)
1099                         goto found;
1100                 if (val >= jmp->begin && val <= jmp->end)
1101                         goto found;
1102         } END_FOR_EACH_PTR(jmp);
1103         warning(insn->pos, "Impossible case statement");
1104         return 0;
1105
1106 found:
1107         insert_branch(insn->bb, insn, jmp->target);
1108         return REPEAT_CSE;
1109 }
1110
1111 int simplify_instruction(struct instruction *insn)
1112 {
1113         if (!insn->bb)
1114                 return 0;
1115         switch (insn->opcode) {
1116         case OP_ADD: case OP_MULS:
1117         case OP_AND: case OP_OR: case OP_XOR:
1118         case OP_AND_BOOL: case OP_OR_BOOL:
1119                 if (simplify_binop(insn))
1120                         return REPEAT_CSE;
1121                 if (simplify_commutative_binop(insn))
1122                         return REPEAT_CSE;
1123                 return simplify_associative_binop(insn);
1124
1125         case OP_MULU:
1126         case OP_SET_EQ: case OP_SET_NE:
1127                 if (simplify_binop(insn))
1128                         return REPEAT_CSE;
1129                 return simplify_commutative_binop(insn);
1130
1131         case OP_SUB:
1132         case OP_DIVU: case OP_DIVS:
1133         case OP_MODU: case OP_MODS:
1134         case OP_SHL:
1135         case OP_LSR: case OP_ASR:
1136         case OP_SET_LE: case OP_SET_GE:
1137         case OP_SET_LT: case OP_SET_GT:
1138         case OP_SET_B:  case OP_SET_A:
1139         case OP_SET_BE: case OP_SET_AE:
1140                 return simplify_binop(insn);
1141
1142         case OP_NOT: case OP_NEG:
1143                 return simplify_unop(insn);
1144         case OP_LOAD: case OP_STORE:
1145                 return simplify_memop(insn);
1146         case OP_SYMADDR:
1147                 if (dead_insn(insn, NULL, NULL, NULL))
1148                         return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
1149                 return replace_with_pseudo(insn, insn->symbol);
1150         case OP_CAST:
1151         case OP_SCAST:
1152         case OP_FPCAST:
1153         case OP_PTRCAST:
1154                 return simplify_cast(insn);
1155         case OP_PHI:
1156                 if (dead_insn(insn, NULL, NULL, NULL)) {
1157                         kill_use_list(insn->phi_list);
1158                         return REPEAT_CSE;
1159                 }
1160                 return clean_up_phi(insn);
1161         case OP_PHISOURCE:
1162                 if (dead_insn(insn, &insn->phi_src, NULL, NULL))
1163                         return REPEAT_CSE;
1164                 break;
1165         case OP_SEL:
1166                 return simplify_select(insn);
1167         case OP_BR:
1168                 return simplify_branch(insn);
1169         case OP_SWITCH:
1170                 return simplify_switch(insn);
1171         case OP_RANGE:
1172                 return simplify_range(insn);
1173         }
1174         return 0;
1175 }