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