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