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