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