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