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