simplify.c

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