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