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