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 int delete_pseudo_user_list_entry(struct pseudo_user_list **list, pseudo_t *entry, int count)
 150 {
 151         struct pseudo_user *pu;
 152
 153         FOR_EACH_PTR(*list, pu) {
 154                 if (pu->userp == entry) {
 155                         DELETE_CURRENT_PTR(pu);
 156                         if (!--count)
 157                                 goto out;
 158                 }
 159         } END_FOR_EACH_PTR(pu);
 160         assert(count <= 0);
 161 out:
 162         pack_ptr_list((struct ptr_list **)list);
 163         return count;
 164 }
 165
 166 static inline void remove_usage(pseudo_t p, pseudo_t *usep)
 167 {
 168         if (has_use_list(p)) {
 169                 delete_pseudo_user_list_entry(&p->users, usep, 1);
 170                 if (!p->users)
 171                         kill_instruction(p->def);
 172         }
 173 }
 174
 175 void kill_use(pseudo_t *usep)
 176 {
 177         if (usep) {
 178                 pseudo_t p = *usep;
 179                 *usep = VOID;
 180                 remove_usage(p, usep);
 181         }
 182 }
 183
 184 void kill_instruction(struct instruction *insn)
 185 {
 186         if (!insn || !insn->bb)
 187                 return;
 188
 189         switch (insn->opcode) {
 190         case OP_BINARY ... OP_BINCMP_END:
 191                 insn->bb = NULL;
 192                 kill_use(&insn->src1);
 193                 kill_use(&insn->src2);
 194                 repeat_phase |= REPEAT_CSE;
 195                 return;
 196
 197         case OP_NOT: case OP_NEG:
 198                 insn->bb = NULL;
 199                 kill_use(&insn->src1);
 200                 repeat_phase |= REPEAT_CSE;
 201                 return;
 202
 203         case OP_PHI:
 204                 insn->bb = NULL;
 205                 repeat_phase |= REPEAT_CSE;
 206                 return;
 207
 208         case OP_SYMADDR:
 209                 insn->bb = NULL;
 210                 repeat_phase |= REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
 211                 return;
 212
 213         case OP_RANGE:
 214                 insn->bb = NULL;
 215                 repeat_phase |= REPEAT_CSE;
 216                 kill_use(&insn->src1);
 217                 kill_use(&insn->src2);
 218                 kill_use(&insn->src3);
 219                 return;
 220         }
 221 }
 222
 223 /*
 224  * Kill trivially dead instructions
 225  */
 226 static int dead_insn(struct instruction *insn, pseudo_t *src1, pseudo_t *src2, pseudo_t *src3)
 227 {
 228         struct pseudo_user *pu;
 229         FOR_EACH_PTR(insn->target->users, pu) {
 230                 if (*pu->userp != VOID)
 231                         return 0;
 232         } END_FOR_EACH_PTR(pu);
 233
 234         insn->bb = NULL;
 235         kill_use(src1);
 236         kill_use(src2);
 237         kill_use(src3);
 238         return REPEAT_CSE;
 239 }
 240
 241 static inline int constant(pseudo_t pseudo)
 242 {
 243         return pseudo->type == PSEUDO_VAL;
 244 }
 245
 246 static int replace_with_pseudo(struct instruction *insn, pseudo_t pseudo)
 247 {
 248         convert_instruction_target(insn, pseudo);
 249         insn->bb = NULL;
 250         return REPEAT_CSE;
 251 }
 252
 253 static int simplify_constant_rightside(struct instruction *insn)
 254 {
 255         long long value = insn->src2->value;
 256
 257         switch (insn->opcode) {
 258         case OP_SUB:
 259                 if (value) {
 260                         insn->opcode = OP_ADD;
 261                         insn->src2 = value_pseudo(-value);
 262                         return REPEAT_CSE;
 263                 }
 264         /* Fallthrough */
 265         case OP_ADD:
 266         case OP_OR: case OP_XOR:
 267         case OP_OR_BOOL:
 268         case OP_SHL:
 269         case OP_LSR: case OP_ASR:
 270                 if (!value)
 271                         return replace_with_pseudo(insn, insn->src1);
 272                 return 0;
 273
 274         case OP_MULU: case OP_MULS:
 275         case OP_AND_BOOL:
 276                 if (value == 1)
 277                         return replace_with_pseudo(insn, insn->src1);
 278         /* Fallthrough */
 279         case OP_AND:
 280                 if (!value)
 281                         return replace_with_pseudo(insn, insn->src2);
 282                 return 0;
 283         }
 284         return 0;
 285 }
 286
 287 static int simplify_constant_leftside(struct instruction *insn)
 288 {
 289         long long value = insn->src1->value;
 290
 291         switch (insn->opcode) {
 292         case OP_ADD: case OP_OR: case OP_XOR:
 293                 if (!value)
 294                         return replace_with_pseudo(insn, insn->src2);
 295                 return 0;
 296
 297         case OP_SHL:
 298         case OP_LSR: case OP_ASR:
 299         case OP_AND:
 300         case OP_MULU: case OP_MULS:
 301                 if (!value)
 302                         return replace_with_pseudo(insn, insn->src1);
 303                 return 0;
 304         }
 305         return 0;
 306 }
 307
 308 static int simplify_constant_binop(struct instruction *insn)
 309 {
 310         /* FIXME! Verify signs and sizes!! */
 311         long long left = insn->src1->value;
 312         long long right = insn->src2->value;
 313         unsigned long long ul, ur;
 314         long long res, mask, bits;
 315
 316         mask = 1ULL << (insn->size-1);
 317         bits = mask | (mask-1);
 318
 319         if (left & mask)
 320                 left |= ~bits;
 321         if (right & mask)
 322                 right |= ~bits;
 323         ul = left & bits;
 324         ur = right & bits;
 325
 326         switch (insn->opcode) {
 327         case OP_ADD:
 328                 res = left + right;
 329                 break;
 330         case OP_SUB:
 331                 res = left - right;
 332                 break;
 333         case OP_MULU:
 334                 res = ul * ur;
 335                 break;
 336         case OP_MULS:
 337                 res = left * right;
 338                 break;
 339         case OP_DIVU:
 340                 if (!ur)
 341                         return 0;
 342                 res = ul / ur;
 343                 break;
 344         case OP_DIVS:
 345                 if (!right)
 346                         return 0;
 347                 res = left / right;
 348                 break;
 349         case OP_MODU:
 350                 if (!ur)
 351                         return 0;
 352                 res = ul % ur;
 353                 break;
 354         case OP_MODS:
 355                 if (!right)
 356                         return 0;
 357                 res = left % right;
 358                 break;
 359         case OP_SHL:
 360                 res = left << right;
 361                 break;
 362         case OP_LSR:
 363                 res = ul >> ur;
 364                 break;
 365         case OP_ASR:
 366                 res = left >> right;
 367                 break;
 368        /* Logical */
 369         case OP_AND:
 370                 res = left & right;
 371                 break;
 372         case OP_OR:
 373                 res = left | right;
 374                 break;
 375         case OP_XOR:
 376                 res = left ^ right;
 377                 break;
 378         case OP_AND_BOOL:
 379                 res = left && right;
 380                 break;
 381         case OP_OR_BOOL:
 382                 res = left || right;
 383                 break;
 384
 385         /* Binary comparison */
 386         case OP_SET_EQ:
 387                 res = left == right;
 388                 break;
 389         case OP_SET_NE:
 390                 res = left != right;
 391                 break;
 392         case OP_SET_LE:
 393                 res = left <= right;
 394                 break;
 395         case OP_SET_GE:
 396                 res = left >= right;
 397                 break;
 398         case OP_SET_LT:
 399                 res = left < right;
 400                 break;
 401         case OP_SET_GT:
 402                 res = left > right;
 403                 break;
 404         case OP_SET_B:
 405                 res = ul < ur;
 406                 break;
 407         case OP_SET_A:
 408                 res = ul > ur;
 409                 break;
 410         case OP_SET_BE:
 411                 res = ul <= ur;
 412                 break;
 413         case OP_SET_AE:
 414                 res = ul >= ur;
 415                 break;
 416         default:
 417                 return 0;
 418         }
 419         res &= bits;
 420
 421         replace_with_pseudo(insn, value_pseudo(res));
 422         return REPEAT_CSE;
 423 }
 424
 425 static int simplify_binop(struct instruction *insn)
 426 {
 427         if (dead_insn(insn, &insn->src1, &insn->src2, NULL))
 428                 return REPEAT_CSE;
 429         if (constant(insn->src1)) {
 430                 if (constant(insn->src2))
 431                         return simplify_constant_binop(insn);
 432                 return simplify_constant_leftside(insn);
 433         }
 434         if (constant(insn->src2))
 435                 return simplify_constant_rightside(insn);
 436         return 0;
 437 }
 438
 439 static void switch_pseudo(struct instruction *insn1, pseudo_t *pp1, struct instruction *insn2, pseudo_t *pp2)
 440 {
 441         pseudo_t p1 = *pp1, p2 = *pp2;
 442
 443         use_pseudo(insn1, p2, pp1);
 444         use_pseudo(insn2, p1, pp2);
 445         remove_usage(p1, pp1);
 446         remove_usage(p2, pp2);
 447 }
 448
 449 static int canonical_order(pseudo_t p1, pseudo_t p2)
 450 {
 451         /* symbol/constants on the right */
 452         if (p1->type == PSEUDO_VAL)
 453                 return p2->type == PSEUDO_VAL;
 454
 455         if (p1->type == PSEUDO_SYM)
 456                 return p2->type == PSEUDO_SYM || p2->type == PSEUDO_VAL;
 457
 458         return 1;
 459 }
 460
 461 static int simplify_commutative_binop(struct instruction *insn)
 462 {
 463         if (!canonical_order(insn->src1, insn->src2)) {
 464                 switch_pseudo(insn, &insn->src1, insn, &insn->src2);
 465                 return REPEAT_CSE;
 466         }
 467         return 0;
 468 }
 469
 470 static inline int simple_pseudo(pseudo_t pseudo)
 471 {
 472         return pseudo->type == PSEUDO_VAL || pseudo->type == PSEUDO_SYM;
 473 }
 474
 475 static int simplify_associative_binop(struct instruction *insn)
 476 {
 477         struct instruction *def;
 478         pseudo_t pseudo = insn->src1;
 479
 480         if (!simple_pseudo(insn->src2))
 481                 return 0;
 482         if (pseudo->type != PSEUDO_REG)
 483                 return 0;
 484         def = pseudo->def;
 485         if (def == insn)
 486                 return 0;
 487         if (def->opcode != insn->opcode)
 488                 return 0;
 489         if (!simple_pseudo(def->src2))
 490                 return 0;
 491         if (ptr_list_size((struct ptr_list *)def->target->users) != 1)
 492                 return 0;
 493         switch_pseudo(def, &def->src1, insn, &insn->src2);
 494         return REPEAT_CSE;
 495 }
 496
 497 static int simplify_constant_unop(struct instruction *insn)
 498 {
 499         long long val = insn->src1->value;
 500         long long res, mask;
 501
 502         switch (insn->opcode) {
 503         case OP_NOT:
 504                 res = ~val;
 505                 break;
 506         case OP_NEG:
 507                 res = -val;
 508                 break;
 509         default:
 510                 return 0;
 511         }
 512         mask = 1ULL << (insn->size-1);
 513         res &= mask | (mask-1);
 514
 515         replace_with_pseudo(insn, value_pseudo(res));
 516         return REPEAT_CSE;
 517 }
 518
 519 static int simplify_unop(struct instruction *insn)
 520 {
 521         if (dead_insn(insn, &insn->src1, NULL, NULL))
 522                 return REPEAT_CSE;
 523         if (constant(insn->src1))
 524                 return simplify_constant_unop(insn);
 525         return 0;
 526 }
 527
 528 static int simplify_one_memop(struct instruction *insn, pseudo_t orig)
 529 {
 530         pseudo_t addr = insn->src;
 531         pseudo_t new, off;
 532
 533         if (addr->type == PSEUDO_REG) {
 534                 struct instruction *def = addr->def;
 535                 if (def->opcode == OP_SYMADDR && def->src) {
 536                         kill_use(&insn->src);
 537                         use_pseudo(insn, def->src, &insn->src);
 538                         return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
 539                 }
 540                 if (def->opcode == OP_ADD) {
 541                         new = def->src1;
 542                         off = def->src2;
 543                         if (constant(off))
 544                                 goto offset;
 545                         new = off;
 546                         off = def->src1;
 547                         if (constant(off))
 548                                 goto offset;
 549                         return 0;
 550                 }
 551         }
 552         return 0;
 553
 554 offset:
 555         /* Invalid code */
 556         if (new == orig) {
 557                 if (new == VOID)
 558                         return 0;
 559                 new = VOID;
 560                 warning(insn->pos, "crazy programmer");
 561         }
 562         insn->offset += off->value;
 563         use_pseudo(insn, new, &insn->src);
 564         remove_usage(addr, &insn->src);
 565         return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
 566 }
 567
 568 /*
 569  * We walk the whole chain of adds/subs backwards. That's not
 570  * only more efficient, but it allows us to find loops.
 571  */
 572 static int simplify_memop(struct instruction *insn)
 573 {
 574         int one, ret = 0;
 575         pseudo_t orig = insn->src;
 576
 577         do {
 578                 one = simplify_one_memop(insn, orig);
 579                 ret |= one;
 580         } while (one);
 581         return ret;
 582 }
 583
 584 static long long get_cast_value(long long val, int old_size, int new_size, int sign)
 585 {
 586         long long mask;
 587
 588         if (sign && new_size > old_size) {
 589                 mask = 1 << (old_size-1);
 590                 if (val & mask)
 591                         val |= ~(mask | (mask-1));
 592         }
 593         mask = 1 << (new_size-1);
 594         return val & (mask | (mask-1));
 595 }
 596
 597 static int simplify_cast(struct instruction *insn)
 598 {
 599         struct symbol *orig_type;
 600         int orig_size, size;
 601         pseudo_t src;
 602
 603         if (dead_insn(insn, &insn->src, NULL, NULL))
 604                 return REPEAT_CSE;
 605
 606         orig_type = insn->orig_type;
 607         if (!orig_type)
 608                 return 0;
 609         orig_size = orig_type->bit_size;
 610         size = insn->size;
 611         src = insn->src;
 612
 613         /* A cast of a constant? */
 614         if (constant(src)) {
 615                 int sign = orig_type->ctype.modifiers & MOD_SIGNED;
 616                 long long val = get_cast_value(src->value, orig_size, size, sign);
 617                 src = value_pseudo(val);
 618                 goto simplify;
 619         }
 620
 621         /* A cast of a "and" might be a no-op.. */
 622         if (src->type == PSEUDO_REG) {
 623                 struct instruction *def = src->def;
 624                 if (def->opcode == OP_AND && def->size >= size) {
 625                         pseudo_t val = def->src2;
 626                         if (val->type == PSEUDO_VAL) {
 627                                 unsigned long long value = val->value;
 628                                 if (!(value >> (size-1)))
 629                                         goto simplify;
 630                         }
 631                 }
 632         }
 633
 634         if (size == orig_size) {
 635                 int op = (orig_type->ctype.modifiers & MOD_SIGNED) ? OP_SCAST : OP_CAST;
 636                 if (insn->opcode == op)
 637                         goto simplify;
 638         }
 639
 640         return 0;
 641
 642 simplify:
 643         return replace_with_pseudo(insn, src);
 644 }
 645
 646 static int simplify_select(struct instruction *insn)
 647 {
 648         pseudo_t cond, src1, src2;
 649
 650         if (dead_insn(insn, &insn->src1, &insn->src2, &insn->src3))
 651                 return REPEAT_CSE;
 652
 653         cond = insn->src1;
 654         src1 = insn->src2;
 655         src2 = insn->src3;
 656         if (constant(cond) || src1 == src2) {
 657                 pseudo_t *kill, take;
 658                 kill_use(&insn->src1);
 659                 take = cond->value ? src1 : src2;
 660                 kill = cond->value ? &insn->src3 : &insn->src2;
 661                 kill_use(kill);
 662                 replace_with_pseudo(insn, take);
 663                 return REPEAT_CSE;
 664         }
 665         if (constant(src1) && constant(src2)) {
 666                 long long val1 = src1->value;
 667                 long long val2 = src2->value;
 668
 669                 /* The pair 0/1 is special - replace with SETNE/SETEQ */
 670                 if ((val1 | val2) == 1) {
 671                         int opcode = OP_SET_EQ;
 672                         if (val1) {
 673                                 src1 = src2;
 674                                 opcode = OP_SET_NE;
 675                         }
 676                         insn->opcode = opcode;
 677                         /* insn->src1 is already cond */
 678                         insn->src2 = src1; /* Zero */
 679                         return REPEAT_CSE;
 680                 }
 681         }
 682         return 0;
 683 }
 684
 685 static int is_in_range(pseudo_t src, long long low, long long high)
 686 {
 687         long long value;
 688
 689         switch (src->type) {
 690         case PSEUDO_VAL:
 691                 value = src->value;
 692                 return value >= low && value <= high;
 693         default:
 694                 return 0;
 695         }
 696 }
 697
 698 static int simplify_range(struct instruction *insn)
 699 {
 700         pseudo_t src1, src2, src3;
 701
 702         src1 = insn->src1;
 703         src2 = insn->src2;
 704         src3 = insn->src3;
 705         if (src2->type != PSEUDO_VAL || src3->type != PSEUDO_VAL)
 706                 return 0;
 707         if (is_in_range(src1, src2->value, src3->value)) {
 708                 kill_instruction(insn);
 709                 return REPEAT_CSE;
 710         }
 711         return 0;
 712 }
 713
 714 /*
 715  * Simplify "set_ne/eq $0 + br"
 716  */
 717 static int simplify_cond_branch(struct instruction *br, pseudo_t cond, struct instruction *def, pseudo_t *pp)
 718 {
 719         use_pseudo(br, *pp, &br->cond);
 720         remove_usage(cond, &br->cond);
 721         if (def->opcode == OP_SET_EQ) {
 722                 struct basic_block *true = br->bb_true;
 723                 struct basic_block *false = br->bb_false;
 724                 br->bb_false = true;
 725                 br->bb_true = false;
 726         }
 727         return REPEAT_CSE;
 728 }
 729
 730 static int simplify_branch(struct instruction *insn)
 731 {
 732         pseudo_t cond = insn->cond;
 733
 734         if (!cond)
 735                 return 0;
 736
 737         /* Constant conditional */
 738         if (constant(cond)) {
 739                 insert_branch(insn->bb, insn, cond->value ? insn->bb_true : insn->bb_false);
 740                 return REPEAT_CSE;
 741         }
 742
 743         /* Same target? */
 744         if (insn->bb_true == insn->bb_false) {
 745                 struct basic_block *bb = insn->bb;
 746                 struct basic_block *target = insn->bb_false;
 747                 remove_bb_from_list(&target->parents, bb, 1);
 748                 remove_bb_from_list(&bb->children, target, 1);
 749                 insn->bb_false = NULL;
 750                 kill_use(&insn->cond);
 751                 insn->cond = NULL;
 752                 return REPEAT_CSE;
 753         }
 754
 755         /* Conditional on a SETNE $0 or SETEQ $0 */
 756         if (cond->type == PSEUDO_REG) {
 757                 struct instruction *def = cond->def;
 758
 759                 if (def->opcode == OP_SET_NE || def->opcode == OP_SET_EQ) {
 760                         if (constant(def->src1) && !def->src1->value)
 761                                 return simplify_cond_branch(insn, cond, def, &def->src2);
 762                         if (constant(def->src2) && !def->src2->value)
 763                                 return simplify_cond_branch(insn, cond, def, &def->src1);
 764                 }
 765                 if (def->opcode == OP_SEL) {
 766                         if (constant(def->src2) && constant(def->src3)) {
 767                                 long long val1 = def->src2->value;
 768                                 long long val2 = def->src3->value;
 769                                 if (!val1 && !val2) {
 770                                         insert_branch(insn->bb, insn, insn->bb_false);
 771                                         return REPEAT_CSE;
 772                                 }
 773                                 if (val1 && val2) {
 774                                         insert_branch(insn->bb, insn, insn->bb_true);
 775                                         return REPEAT_CSE;
 776                                 }
 777                                 if (val2) {
 778                                         struct basic_block *true = insn->bb_true;
 779                                         struct basic_block *false = insn->bb_false;
 780                                         insn->bb_false = true;
 781                                         insn->bb_true = false;
 782                                 }
 783                                 use_pseudo(insn, def->src1, &insn->cond);
 784                                 remove_usage(cond, &insn->cond);
 785                                 return REPEAT_CSE;
 786                         }
 787                 }
 788                 if (def->opcode == OP_CAST || def->opcode == OP_SCAST) {
 789                         int orig_size = def->orig_type ? def->orig_type->bit_size : 0;
 790                         if (def->size > orig_size) {
 791                                 use_pseudo(insn, def->src, &insn->cond);
 792                                 remove_usage(cond, &insn->cond);
 793                                 return REPEAT_CSE;
 794                         }
 795                 }
 796         }
 797         return 0;
 798 }
 799
 800 static int simplify_switch(struct instruction *insn)
 801 {
 802         pseudo_t cond = insn->cond;
 803         long long val;
 804         struct multijmp *jmp;
 805
 806         if (!constant(cond))
 807                 return 0;
 808         val = insn->cond->value;
 809
 810         FOR_EACH_PTR(insn->multijmp_list, jmp) {
 811                 /* Default case */
 812                 if (jmp->begin > jmp->end)
 813                         goto found;
 814                 if (val >= jmp->begin && val <= jmp->end)
 815                         goto found;
 816         } END_FOR_EACH_PTR(jmp);
 817         warning(insn->pos, "Impossible case statement");
 818         return 0;
 819
 820 found:
 821         insert_branch(insn->bb, insn, jmp->target);
 822         return REPEAT_CSE;
 823 }
 824
 825 int simplify_instruction(struct instruction *insn)
 826 {
 827         if (!insn->bb)
 828                 return 0;
 829         switch (insn->opcode) {
 830         case OP_ADD: case OP_MULS:
 831         case OP_AND: case OP_OR: case OP_XOR:
 832         case OP_AND_BOOL: case OP_OR_BOOL:
 833                 if (simplify_binop(insn))
 834                         return REPEAT_CSE;
 835                 if (simplify_commutative_binop(insn))
 836                         return REPEAT_CSE;
 837                 return simplify_associative_binop(insn);
 838
 839         case OP_MULU:
 840         case OP_SET_EQ: case OP_SET_NE:
 841                 if (simplify_binop(insn))
 842                         return REPEAT_CSE;
 843                 return simplify_commutative_binop(insn);
 844
 845         case OP_SUB:
 846         case OP_DIVU: case OP_DIVS:
 847         case OP_MODU: case OP_MODS:
 848         case OP_SHL:
 849         case OP_LSR: case OP_ASR:
 850         case OP_SET_LE: case OP_SET_GE:
 851         case OP_SET_LT: case OP_SET_GT:
 852         case OP_SET_B:  case OP_SET_A:
 853         case OP_SET_BE: case OP_SET_AE:
 854                 return simplify_binop(insn);
 855
 856         case OP_NOT: case OP_NEG:
 857                 return simplify_unop(insn);
 858         case OP_LOAD: case OP_STORE:
 859                 return simplify_memop(insn);
 860         case OP_SYMADDR:
 861                 if (dead_insn(insn, NULL, NULL, NULL))
 862                         return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
 863                 return replace_with_pseudo(insn, insn->symbol);
 864         case OP_CAST:
 865         case OP_SCAST:
 866         case OP_FPCAST:
 867         case OP_PTRCAST:
 868                 return simplify_cast(insn);
 869         case OP_PHI:
 870                 if (dead_insn(insn, NULL, NULL, NULL)) {
 871                         clear_phi(insn);
 872                         return REPEAT_CSE;
 873                 }
 874                 return clean_up_phi(insn);
 875         case OP_PHISOURCE:
 876                 if (dead_insn(insn, &insn->phi_src, NULL, NULL))
 877                         return REPEAT_CSE;
 878                 break;
 879         case OP_SEL:
 880                 return simplify_select(insn);
 881         case OP_BR:
 882                 return simplify_branch(insn);
 883         case OP_SWITCH:
 884                 return simplify_switch(insn);
 885         case OP_RANGE:
 886                 return simplify_range(insn);
 887         }
 888         return 0;
 889 }