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
  14 /* Find the trivial parent for a phi-source */
  15 static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseudo)
  16 {
  17         /* Can't go upwards if the pseudo is defined in the bb it came from.. */
  18         if (pseudo->type == PSEUDO_REG) {
  19                 struct instruction *def = pseudo->def;
  20                 if (def->bb == source)
  21                         return source;
  22         }
  23         if (bb_list_size(source->children) != 1 || bb_list_size(source->parents) != 1)
  24                 return source;
  25         return first_basic_block(source->parents);
  26 }
  27
  28 static void clear_phi(struct instruction *insn)
  29 {
  30         pseudo_t phi;
  31
  32         insn->bb = NULL;
  33         FOR_EACH_PTR(insn->phi_list, phi) {
  34                 *THIS_ADDRESS(phi) = VOID;
  35         } END_FOR_EACH_PTR(phi);
  36 }
  37
  38 static int if_convert_phi(struct instruction *insn)
  39 {
  40         pseudo_t array[3];
  41         struct basic_block *parents[3];
  42         struct basic_block *bb, *bb1, *bb2, *source;
  43         struct instruction *br;
  44         pseudo_t p1, p2;
  45
  46         bb = insn->bb;
  47         if (linearize_ptr_list((struct ptr_list *)insn->phi_list, (void **)array, 3) != 2)
  48                 return 0;
  49         if (linearize_ptr_list((struct ptr_list *)bb->parents, (void **)parents, 3) != 2)
  50                 return 0;
  51         p1 = array[0]->def->src1;
  52         bb1 = array[0]->def->bb;
  53         p2 = array[1]->def->src1;
  54         bb2 = array[1]->def->bb;
  55
  56         /* Only try the simple "direct parents" case */
  57         if ((bb1 != parents[0] || bb2 != parents[1]) &&
  58             (bb1 != parents[1] || bb2 != parents[0]))
  59                 return 0;
  60
  61         /*
  62          * See if we can find a common source for this..
  63          */
  64         source = phi_parent(bb1, p1);
  65         if (source != phi_parent(bb2, p2))
  66                 return 0;
  67
  68         /*
  69          * Cool. We now know that 'source' is the exclusive
  70          * parent of both phi-nodes, so the exit at the
  71          * end of it fully determines which one it is, and
  72          * we can turn it into a select.
  73          *
  74          * HOWEVER, right now we only handle regular
  75          * conditional branches. No multijumps or computed
  76          * stuff. Verify that here.
  77          */
  78         br = last_instruction(source->insns);
  79         if (!br || br->opcode != OP_BR)
  80                 return 0;
  81
  82         assert(br->cond);
  83         assert(br->bb_false);
  84
  85         /*
  86          * We're in business. Match up true/false with p1/p2.
  87          */
  88         if (br->bb_true == bb2 || br->bb_false == bb1) {
  89                 pseudo_t p = p1;
  90                 p1 = p2;
  91                 p2 = p;
  92         }
  93
  94         /*
  95          * Ok, we can now replace that last
  96          *
  97          *      br cond, a, b
  98          *
  99          * with the sequence
 100          *
 101          *      setcc cond
 102          *      select pseudo, p1, p2
 103          *      br cond, a, b
 104          *
 105          * and remove the phi-node. If it then
 106          * turns out that 'a' or 'b' is entirely
 107          * empty (common case), and now no longer
 108          * a phi-source, we'll be able to simplify
 109          * the conditional branch too.
 110          */
 111         insert_select(source, br, insn, p1, p2);
 112         clear_phi(insn);
 113         return REPEAT_CSE;
 114 }
 115
 116 static int clean_up_phi(struct instruction *insn)
 117 {
 118         pseudo_t phi;
 119         struct instruction *last;
 120         int same;
 121
 122         last = NULL;
 123         same = 1;
 124         FOR_EACH_PTR(insn->phi_list, phi) {
 125                 struct instruction *def;
 126                 if (phi == VOID)
 127                         continue;
 128                 def = phi->def;
 129                 if (def->src1 == VOID || !def->bb)
 130                         continue;
 131                 if (last) {
 132                         if (last->src1 != def->src1)
 133                                 same = 0;
 134                         continue;
 135                 }
 136                 last = def;
 137         } END_FOR_EACH_PTR(phi);
 138
 139         if (same) {
 140                 pseudo_t pseudo = last ? last->src1 : VOID;
 141                 convert_instruction_target(insn, pseudo);
 142                 clear_phi(insn);
 143                 return REPEAT_CSE;
 144         }
 145
 146         return if_convert_phi(insn);
 147 }
 148
 149 static inline void remove_usage(pseudo_t p, pseudo_t *usep)
 150 {
 151         if (has_use_list(p)) {
 152                 delete_ptr_list_entry((struct ptr_list **)&p->users, usep, 1);
 153                 if (!p->users)
 154                         kill_instruction(p->def);
 155         }
 156 }
 157
 158 void kill_use(pseudo_t *usep)
 159 {
 160         if (usep) {
 161                 pseudo_t p = *usep;
 162                 *usep = VOID;
 163                 remove_usage(p, usep);
 164         }
 165 }
 166
 167 void kill_instruction(struct instruction *insn)
 168 {
 169         if (!insn || !insn->bb)
 170                 return;
 171
 172         switch (insn->opcode) {
 173         case OP_BINARY ... OP_BINCMP_END:
 174                 insn->bb = NULL;
 175                 kill_use(&insn->src1);
 176                 kill_use(&insn->src2);
 177                 repeat_phase |= REPEAT_CSE;
 178                 return;
 179
 180         case OP_NOT: case OP_NEG:
 181                 insn->bb = NULL;
 182                 kill_use(&insn->src1);
 183                 repeat_phase |= REPEAT_CSE;
 184                 return;
 185
 186         case OP_PHI:
 187                 insn->bb = NULL;
 188                 repeat_phase |= REPEAT_CSE;
 189                 return;
 190
 191         case OP_SYMADDR:
 192                 insn->bb = NULL;
 193                 repeat_phase |= REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
 194                 return;
 195
 196         case OP_RANGE:
 197                 insn->bb = NULL;
 198                 repeat_phase |= REPEAT_CSE;
 199                 kill_use(&insn->src1);
 200                 kill_use(&insn->src2);
 201                 kill_use(&insn->src3);
 202                 return;
 203         }
 204 }
 205
 206 /*
 207  * Kill trivially dead instructions
 208  */
 209 static int dead_insn(struct instruction *insn, pseudo_t *src1, pseudo_t *src2, pseudo_t *src3)
 210 {
 211         pseudo_t *usep;
 212         FOR_EACH_PTR(insn->target->users, usep) {
 213                 if (*usep != VOID)
 214                         return 0;
 215         } END_FOR_EACH_PTR(usep);
 216
 217         insn->bb = NULL;
 218         kill_use(src1);
 219         kill_use(src2);
 220         kill_use(src3);
 221         return REPEAT_CSE;
 222 }
 223
 224 static inline int constant(pseudo_t pseudo)
 225 {
 226         return pseudo->type == PSEUDO_VAL;
 227 }
 228
 229 static int replace_with_pseudo(struct instruction *insn, pseudo_t pseudo)
 230 {
 231         convert_instruction_target(insn, pseudo);
 232         insn->bb = NULL;
 233         return REPEAT_CSE;
 234 }
 235
 236 static int simplify_constant_rightside(struct instruction *insn)
 237 {
 238         long long value = insn->src2->value;
 239
 240         switch (insn->opcode) {
 241         case OP_SUB:
 242                 if (value) {
 243                         insn->opcode = OP_ADD;
 244                         insn->src2 = value_pseudo(-value);
 245                         return REPEAT_CSE;
 246                 }
 247         /* Fallthrough */
 248         case OP_ADD:
 249         case OP_OR: case OP_XOR:
 250         case OP_OR_BOOL:
 251         case OP_SHL:
 252         case OP_LSR: case OP_ASR:
 253                 if (!value)
 254                         return replace_with_pseudo(insn, insn->src1);
 255                 return 0;
 256
 257         case OP_MULU: case OP_MULS:
 258         case OP_AND_BOOL:
 259                 if (value == 1)
 260                         return replace_with_pseudo(insn, insn->src1);
 261         /* Fallthrough */
 262         case OP_AND:
 263                 if (!value)
 264                         return replace_with_pseudo(insn, insn->src2);
 265                 return 0;
 266         }
 267         return 0;
 268 }
 269
 270 static int simplify_constant_leftside(struct instruction *insn)
 271 {
 272         long long value = insn->src1->value;
 273
 274         switch (insn->opcode) {
 275         case OP_ADD: case OP_OR: case OP_XOR:
 276                 if (!value)
 277                         return replace_with_pseudo(insn, insn->src2);
 278                 return 0;
 279
 280         case OP_SHL:
 281         case OP_LSR: case OP_ASR:
 282         case OP_AND:
 283         case OP_MULU: case OP_MULS:
 284                 if (!value)
 285                         return replace_with_pseudo(insn, insn->src1);
 286                 return 0;
 287         }
 288         return 0;
 289 }
 290
 291 static int simplify_constant_binop(struct instruction *insn)
 292 {
 293         /* FIXME! Verify signs and sizes!! */
 294         long long left = insn->src1->value;
 295         long long right = insn->src2->value;
 296         unsigned long long ul, ur;
 297         long long res, mask, bits;
 298
 299         mask = 1ULL << (insn->size-1);
 300         bits = mask | (mask-1);
 301
 302         if (left & mask)
 303                 left |= ~bits;
 304         if (right & mask)
 305                 right |= ~bits;
 306         ul = left & bits;
 307         ur = right & bits;
 308
 309         switch (insn->opcode) {
 310         case OP_ADD:
 311                 res = left + right;
 312                 break;
 313         case OP_SUB:
 314                 res = left - right;
 315                 break;
 316         case OP_MULU:
 317                 res = ul * ur;
 318                 break;
 319         case OP_MULS:
 320                 res = left * right;
 321                 break;
 322         case OP_DIVU:
 323                 if (!ur)
 324                         return 0;
 325                 res = ul / ur;
 326                 break;
 327         case OP_DIVS:
 328                 if (!right)
 329                         return 0;
 330                 res = left / right;
 331                 break;
 332         case OP_MODU:
 333                 if (!ur)
 334                         return 0;
 335                 res = ul % ur;
 336                 break;
 337         case OP_MODS:
 338                 if (!right)
 339                         return 0;
 340                 res = left % right;
 341                 break;
 342         case OP_SHL:
 343                 res = left << right;
 344                 break;
 345         case OP_LSR:
 346                 res = ul >> ur;
 347                 break;
 348         case OP_ASR:
 349                 res = left >> right;
 350                 break;
 351        /* Logical */
 352         case OP_AND:
 353                 res = left & right;
 354                 break;
 355         case OP_OR:
 356                 res = left | right;
 357                 break;
 358         case OP_XOR:
 359                 res = left ^ right;
 360                 break;
 361         case OP_AND_BOOL:
 362                 res = left && right;
 363                 break;
 364         case OP_OR_BOOL:
 365                 res = left || right;
 366                 break;
 367
 368         /* Binary comparison */
 369         case OP_SET_EQ:
 370                 res = left == right;
 371                 break;
 372         case OP_SET_NE:
 373                 res = left != right;
 374                 break;
 375         case OP_SET_LE:
 376                 res = left <= right;
 377                 break;
 378         case OP_SET_GE:
 379                 res = left >= right;
 380                 break;
 381         case OP_SET_LT:
 382                 res = left < right;
 383                 break;
 384         case OP_SET_GT:
 385                 res = left > right;
 386                 break;
 387         case OP_SET_B:
 388                 res = ul < ur;
 389                 break;
 390         case OP_SET_A:
 391                 res = ul > ur;
 392                 break;
 393         case OP_SET_BE:
 394                 res = ul <= ur;
 395                 break;
 396         case OP_SET_AE:
 397                 res = ul >= ur;
 398                 break;
 399         default:
 400                 return 0;
 401         }
 402         res &= bits;
 403
 404         replace_with_pseudo(insn, value_pseudo(res));
 405         return REPEAT_CSE;
 406 }
 407
 408 static int simplify_binop(struct instruction *insn)
 409 {
 410         if (dead_insn(insn, &insn->src1, &insn->src2, NULL))
 411                 return REPEAT_CSE;
 412         if (constant(insn->src1)) {
 413                 if (constant(insn->src2))
 414                         return simplify_constant_binop(insn);
 415                 return simplify_constant_leftside(insn);
 416         }
 417         if (constant(insn->src2))
 418                 return simplify_constant_rightside(insn);
 419         return 0;
 420 }
 421
 422 static void switch_pseudo(pseudo_t *pp1, pseudo_t *pp2)
 423 {
 424         pseudo_t p1 = *pp1, p2 = *pp2;
 425
 426         use_pseudo(p2, pp1);
 427         use_pseudo(p1, pp2);
 428         remove_usage(p1, pp1);
 429         remove_usage(p2, pp2);
 430 }
 431
 432 static int canonical_order(pseudo_t p1, pseudo_t p2)
 433 {
 434         /* symbol/constants on the right */
 435         if (p1->type == PSEUDO_VAL)
 436                 return p2->type == PSEUDO_VAL;
 437
 438         if (p1->type == PSEUDO_SYM)
 439                 return p2->type == PSEUDO_SYM || p2->type == PSEUDO_VAL;
 440
 441         return 1;
 442 }
 443
 444 static int simplify_commutative_binop(struct instruction *insn)
 445 {
 446         if (!canonical_order(insn->src1, insn->src2)) {
 447                 switch_pseudo(&insn->src1, &insn->src2);
 448                 return REPEAT_CSE;
 449         }
 450         return 0;
 451 }
 452
 453 static inline int simple_pseudo(pseudo_t pseudo)
 454 {
 455         return pseudo->type == PSEUDO_VAL || pseudo->type == PSEUDO_SYM;
 456 }
 457
 458 static int simplify_associative_binop(struct instruction *insn)
 459 {
 460         struct instruction *def;
 461         pseudo_t pseudo = insn->src1;
 462
 463         if (!simple_pseudo(insn->src2))
 464                 return 0;
 465         if (pseudo->type != PSEUDO_REG)
 466                 return 0;
 467         def = pseudo->def;
 468         if (def == insn)
 469                 return 0;
 470         if (def->opcode != insn->opcode)
 471                 return 0;
 472         if (!simple_pseudo(def->src2))
 473                 return 0;
 474         if (ptr_list_size((struct ptr_list *)def->target->users) != 1)
 475                 return 0;
 476         switch_pseudo(&def->src1, &insn->src2);
 477         return REPEAT_CSE;
 478 }
 479
 480 static int simplify_constant_unop(struct instruction *insn)
 481 {
 482         long long val = insn->src1->value;
 483         long long res, mask;
 484
 485         switch (insn->opcode) {
 486         case OP_NOT:
 487                 res = ~val;
 488                 break;
 489         case OP_NEG:
 490                 res = -val;
 491                 break;
 492         default:
 493                 return 0;
 494         }
 495         mask = 1ULL << (insn->size-1);
 496         res &= mask | (mask-1);
 497
 498         replace_with_pseudo(insn, value_pseudo(res));
 499         return REPEAT_CSE;
 500 }
 501
 502 static int simplify_unop(struct instruction *insn)
 503 {
 504         if (dead_insn(insn, &insn->src1, NULL, NULL))
 505                 return REPEAT_CSE;
 506         if (constant(insn->src1))
 507                 return simplify_constant_unop(insn);
 508         return 0;
 509 }
 510
 511 static int simplify_one_memop(struct instruction *insn, pseudo_t orig)
 512 {
 513         pseudo_t addr = insn->src;
 514         pseudo_t new, off;
 515
 516         if (addr->type == PSEUDO_REG) {
 517                 struct instruction *def = addr->def;
 518                 if (def->opcode == OP_SYMADDR && def->src) {
 519                         kill_use(&insn->src);
 520                         use_pseudo(def->src, &insn->src);
 521                         return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
 522                 }
 523                 if (def->opcode == OP_ADD) {
 524                         new = def->src1;
 525                         off = def->src2;
 526                         if (constant(off))
 527                                 goto offset;
 528                         new = off;
 529                         off = def->src1;
 530                         if (constant(off))
 531                                 goto offset;
 532                         return 0;
 533                 }
 534         }
 535         return 0;
 536
 537 offset:
 538         /* Invalid code */
 539         if (new == orig) {
 540                 if (new == VOID)
 541                         return 0;
 542                 new = VOID;
 543                 warning(insn->pos, "crazy programmer");
 544         }
 545         insn->offset += off->value;
 546         use_pseudo(new, &insn->src);
 547         remove_usage(addr, &insn->src);
 548         return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
 549 }
 550
 551 /*
 552  * We walk the whole chain of adds/subs backwards. That's not
 553  * only more efficient, but it allows us to find loops.
 554  */
 555 static int simplify_memop(struct instruction *insn)
 556 {
 557         int one, ret = 0;
 558         pseudo_t orig = insn->src;
 559
 560         do {
 561                 one = simplify_one_memop(insn, orig);
 562                 ret |= one;
 563         } while (one);
 564         return ret;
 565 }
 566
 567 static long long get_cast_value(long long val, int old_size, int new_size, int sign)
 568 {
 569         long long mask;
 570
 571         if (sign && new_size > old_size) {
 572                 mask = 1 << (old_size-1);
 573                 if (val & mask)
 574                         val |= ~(mask | (mask-1));
 575         }
 576         mask = 1 << (new_size-1);
 577         return val & (mask | (mask-1));
 578 }
 579
 580 static int simplify_cast(struct instruction *insn)
 581 {
 582         struct symbol *orig_type;
 583         int orig_size, size;
 584         pseudo_t src;
 585
 586         if (dead_insn(insn, &insn->src, NULL, NULL))
 587                 return REPEAT_CSE;
 588
 589         orig_type = insn->orig_type;
 590         if (!orig_type)
 591                 return 0;
 592         orig_size = orig_type->bit_size;
 593         size = insn->size;
 594         src = insn->src;
 595
 596         /* A cast of a constant? */
 597         if (constant(src)) {
 598                 int sign = orig_type->ctype.modifiers & MOD_SIGNED;
 599                 long long val = get_cast_value(src->value, orig_size, size, sign);
 600                 src = value_pseudo(val);
 601                 goto simplify;
 602         }
 603
 604         /* A cast of a "and" might be a no-op.. */
 605         if (src->type == PSEUDO_REG) {
 606                 struct instruction *def = src->def;
 607                 if (def->opcode == OP_AND && def->size >= size) {
 608                         pseudo_t val = def->src2;
 609                         if (val->type == PSEUDO_VAL) {
 610                                 unsigned long long value = val->value;
 611                                 if (!(value >> (size-1)))
 612                                         goto simplify;
 613                         }
 614                 }
 615         }
 616
 617         if (size == orig_size) {
 618                 int op = (orig_type->ctype.modifiers & MOD_SIGNED) ? OP_SCAST : OP_CAST;
 619                 if (insn->opcode == op)
 620                         goto simplify;
 621         }
 622
 623         return 0;
 624
 625 simplify:
 626         return replace_with_pseudo(insn, src);
 627 }
 628
 629 static int simplify_select(struct instruction *insn)
 630 {
 631         pseudo_t cond, src1, src2;
 632
 633         if (dead_insn(insn, &insn->src1, &insn->src2, &insn->src3))
 634                 return REPEAT_CSE;
 635
 636         cond = insn->src1;
 637         src1 = insn->src2;
 638         src2 = insn->src3;
 639         if (constant(cond) || src1 == src2) {
 640                 pseudo_t *kill, take;
 641                 kill_use(&insn->src1);
 642                 take = cond->value ? src1 : src2;
 643                 kill = cond->value ? &insn->src3 : &insn->src2;
 644                 kill_use(kill);
 645                 replace_with_pseudo(insn, take);
 646                 return REPEAT_CSE;
 647         }
 648         if (constant(src1) && constant(src2)) {
 649                 long long val1 = src1->value;
 650                 long long val2 = src2->value;
 651
 652                 /* The pair 0/1 is special - replace with SETNE/SETEQ */
 653                 if ((val1 | val2) == 1) {
 654                         int opcode = OP_SET_EQ;
 655                         if (val1) {
 656                                 src1 = src2;
 657                                 opcode = OP_SET_NE;
 658                         }
 659                         insn->opcode = opcode;
 660                         /* insn->src1 is already cond */
 661                         insn->src2 = src1; /* Zero */
 662                         return REPEAT_CSE;
 663                 }
 664         }
 665         return 0;
 666 }
 667
 668 static int is_in_range(pseudo_t src, long long low, long long high)
 669 {
 670         long long value;
 671
 672         switch (src->type) {
 673         case PSEUDO_VAL:
 674                 value = src->value;
 675                 return value >= low && value <= high;
 676         default:
 677                 return 0;
 678         }
 679 }
 680
 681 static int simplify_range(struct instruction *insn)
 682 {
 683         pseudo_t src1, src2, src3;
 684
 685         src1 = insn->src1;
 686         src2 = insn->src2;
 687         src3 = insn->src3;
 688         if (src2->type != PSEUDO_VAL || src3->type != PSEUDO_VAL)
 689                 return 0;
 690         if (is_in_range(src1, src2->value, src3->value)) {
 691                 kill_instruction(insn);
 692                 return REPEAT_CSE;
 693         }
 694         return 0;
 695 }
 696
 697 /*
 698  * Simplify "set_ne/eq $0 + br"
 699  */
 700 static int simplify_cond_branch(struct instruction *br, pseudo_t cond, struct instruction *def, pseudo_t *pp)
 701 {
 702         use_pseudo(*pp, &br->cond);
 703         remove_usage(cond, &br->cond);
 704         if (def->opcode == OP_SET_EQ) {
 705                 struct basic_block *true = br->bb_true;
 706                 struct basic_block *false = br->bb_false;
 707                 br->bb_false = true;
 708                 br->bb_true = false;
 709         }
 710         return REPEAT_CSE;
 711 }
 712
 713 static int simplify_branch(struct instruction *insn)
 714 {
 715         pseudo_t cond = insn->cond;
 716
 717         if (!cond)
 718                 return 0;
 719
 720         /* Constant conditional */
 721         if (constant(cond)) {
 722                 insert_branch(insn->bb, insn, cond->value ? insn->bb_true : insn->bb_false);
 723                 return REPEAT_CSE;
 724         }
 725
 726         /* Same target? */
 727         if (insn->bb_true == insn->bb_false) {
 728                 struct basic_block *bb = insn->bb;
 729                 struct basic_block *target = insn->bb_false;
 730                 remove_bb_from_list(&target->parents, bb, 1);
 731                 remove_bb_from_list(&bb->children, target, 1);
 732                 insn->bb_false = NULL;
 733                 kill_use(&insn->cond);
 734                 insn->cond = NULL;
 735                 return REPEAT_CSE;
 736         }
 737
 738         /* Conditional on a SETNE $0 or SETEQ $0 */
 739         if (cond->type == PSEUDO_REG) {
 740                 struct instruction *def = cond->def;
 741
 742                 if (def->opcode == OP_SET_NE || def->opcode == OP_SET_EQ) {
 743                         if (constant(def->src1) && !def->src1->value)
 744                                 return simplify_cond_branch(insn, cond, def, &def->src2);
 745                         if (constant(def->src2) && !def->src2->value)
 746                                 return simplify_cond_branch(insn, cond, def, &def->src1);
 747                 }
 748                 if (def->opcode == OP_SEL) {
 749                         if (constant(def->src2) && constant(def->src3)) {
 750                                 long long val1 = def->src2->value;
 751                                 long long val2 = def->src3->value;
 752                                 if (!val1 && !val2) {
 753                                         insert_branch(insn->bb, insn, insn->bb_false);
 754                                         return REPEAT_CSE;
 755                                 }
 756                                 if (val1 && val2) {
 757                                         insert_branch(insn->bb, insn, insn->bb_true);
 758                                         return REPEAT_CSE;
 759                                 }
 760                                 if (val2) {
 761                                         struct basic_block *true = insn->bb_true;
 762                                         struct basic_block *false = insn->bb_false;
 763                                         insn->bb_false = true;
 764                                         insn->bb_true = false;
 765                                 }
 766                                 use_pseudo(def->src1, &insn->cond);
 767                                 remove_usage(cond, &insn->cond);
 768                                 return REPEAT_CSE;
 769                         }
 770                 }
 771                 if (def->opcode == OP_CAST || def->opcode == OP_SCAST) {
 772                         int orig_size = def->orig_type ? def->orig_type->bit_size : 0;
 773                         if (def->size > orig_size) {
 774                                 use_pseudo(def->src, &insn->cond);
 775                                 remove_usage(cond, &insn->cond);
 776                                 return REPEAT_CSE;
 777                         }
 778                 }
 779         }
 780         return 0;
 781 }
 782
 783 static int simplify_switch(struct instruction *insn)
 784 {
 785         pseudo_t cond = insn->cond;
 786         long long val;
 787         struct multijmp *jmp;
 788
 789         if (!constant(cond))
 790                 return 0;
 791         val = insn->cond->value;
 792
 793         FOR_EACH_PTR(insn->multijmp_list, jmp) {
 794                 /* Default case */
 795                 if (jmp->begin > jmp->end)
 796                         goto found;
 797                 if (val >= jmp->begin && val <= jmp->end)
 798                         goto found;
 799         } END_FOR_EACH_PTR(jmp);
 800         warning(insn->pos, "Impossible case statement");
 801         return 0;
 802
 803 found:
 804         insert_branch(insn->bb, insn, jmp->target);
 805         return REPEAT_CSE;
 806 }
 807
 808 int simplify_instruction(struct instruction *insn)
 809 {
 810         if (!insn->bb)
 811                 return 0;
 812         switch (insn->opcode) {
 813         case OP_ADD: case OP_MULS:
 814         case OP_AND: case OP_OR: case OP_XOR:
 815         case OP_AND_BOOL: case OP_OR_BOOL:
 816                 if (simplify_binop(insn))
 817                         return REPEAT_CSE;
 818                 if (simplify_commutative_binop(insn))
 819                         return REPEAT_CSE;
 820                 return simplify_associative_binop(insn);
 821
 822         case OP_MULU:
 823         case OP_SET_EQ: case OP_SET_NE:
 824                 if (simplify_binop(insn))
 825                         return REPEAT_CSE;
 826                 return simplify_commutative_binop(insn);
 827
 828         case OP_SUB:
 829         case OP_DIVU: case OP_DIVS:
 830         case OP_MODU: case OP_MODS:
 831         case OP_SHL:
 832         case OP_LSR: case OP_ASR:
 833         case OP_SET_LE: case OP_SET_GE:
 834         case OP_SET_LT: case OP_SET_GT:
 835         case OP_SET_B:  case OP_SET_A:
 836         case OP_SET_BE: case OP_SET_AE:
 837                 return simplify_binop(insn);
 838
 839         case OP_NOT: case OP_NEG:
 840                 return simplify_unop(insn);
 841         case OP_LOAD: case OP_STORE:
 842                 return simplify_memop(insn);
 843         case OP_SYMADDR:
 844                 if (dead_insn(insn, NULL, NULL, NULL))
 845                         return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
 846                 return replace_with_pseudo(insn, insn->symbol);
 847         case OP_CAST:
 848         case OP_SCAST:
 849         case OP_FPCAST:
 850         case OP_PTRCAST:
 851                 return simplify_cast(insn);
 852         case OP_PHI:
 853                 if (dead_insn(insn, NULL, NULL, NULL)) {
 854                         clear_phi(insn);
 855                         return REPEAT_CSE;
 856                 }
 857                 return clean_up_phi(insn);
 858         case OP_PHISOURCE:
 859                 if (dead_insn(insn, &insn->phi_src, NULL, NULL))
 860                         return REPEAT_CSE;
 861                 break;
 862         case OP_SEL:
 863                 return simplify_select(insn);
 864         case OP_BR:
 865                 return simplify_branch(insn);
 866         case OP_SWITCH:
 867                 return simplify_switch(insn);
 868         case OP_RANGE:
 869                 return simplify_range(insn);
 870         }
 871         return 0;
 872 }