simplify.c

   1 /*
   2  * Simplify - do instruction simplification before CSE
   3  *
   4  * Copyright (C) 2004 Linus Torvalds
   5  */
   6
   7 ///
   8 // Instruction simplification
   9 // --------------------------
  10 //
  11 // Notation
  12 // ^^^^^^^^
  13 // The following conventions are used to describe the simplications:
  14 // * Uppercase letters are reserved for constants:
  15 //   * `M` for a constant mask,
  16 //   * `S` for a constant shift,
  17 //   * `N` for a constant number of bits (usually other than a shift),
  18 //   * `C` or 'K' for others constants.
  19 // * Lowercase letters `a`, `b`, `x`, `y`, ... are used for non-constants
  20 //   or when it doesn't matter if the pseudo is a constant or not.
  21 // * Primes are used if needed to distinguish symbols (`M`, `M'`, ...).
  22 // * Expressions or sub-expressions involving only constants are
  23 //   understood to be evaluated.
  24 // * `$mask(N)` is used for `((1 << N) -1)`
  25 // * `$trunc(x, N)` is used for `(x & $mask(N))`
  26 // * Expressions like `(-1 << S)`, `(-1 >> S)` and others formulae are
  27 //   understood to be truncated to the size of the current instruction
  28 //   (needed, since in general this size is not the same as the one used
  29 //   by sparse for the evaluation of arithmetic operations).
  30 // * `TRUNC(x, N)` is used for a truncation *to* a size of `N` bits
  31 // * `ZEXT(x, N)` is used for a zero-extension *from* a size of `N` bits
  32 // * `OP(x, C)` is used to represent some generic operation using a constant,
  33 //   including when the constant is implicit (e.g. `TRUNC(x, N)`).
  34 // * `MASK(x, M)` is used to respresent a 'masking' instruction:
  35 //   - `AND(x, M)`
  36 //   - `LSR(x, S)`, with `M` = (-1 << S)
  37 //   - `SHL(x, S)`, with `M` = (-1 >> S)
  38 //   - `TRUNC(x, N)`, with `M` = $mask(N)
  39 //   - `ZEXT(x, N)`, with `M` = $mask(N)
  40 // * `SHIFT(x, S)` is used for `LSR(x, S)` or `SHL(x, S)`.
  41
  42 #include <assert.h>
  43
  44 #include "parse.h"
  45 #include "expression.h"
  46 #include "linearize.h"
  47 #include "flow.h"
  48 #include "symbol.h"
  49
  50 ///
  51 // Utilities
  52 // ^^^^^^^^^
  53
  54 ///
  55 // find the trivial parent for a phi-source
  56 static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseudo)
  57 {
  58         /* Can't go upwards if the pseudo is defined in the bb it came from.. */
  59         if (pseudo->type == PSEUDO_REG) {
  60                 struct instruction *def = pseudo->def;
  61                 if (def->bb == source)
  62                         return source;
  63         }
  64         if (bb_list_size(source->children) != 1 || bb_list_size(source->parents) != 1)
  65                 return source;
  66         return first_basic_block(source->parents);
  67 }
  68
  69 ///
  70 // copy the phi-node's phisrcs into to given array
  71 // @return: 0 if the the list contained the expected
  72 //      number of element, a positive number if there was
  73 //      more than expected and a negative one if less.
  74 //
  75 // :note: we can't reuse a function like linearize_ptr_list()
  76 //      because any VOIDs in the phi-list must be ignored here
  77 //      as in this context they mean 'entry has been removed'.
  78 static int get_phisources(struct instruction *sources[], int nbr, struct instruction *insn)
  79 {
  80         pseudo_t phi;
  81         int i = 0;
  82
  83         assert(insn->opcode == OP_PHI);
  84         FOR_EACH_PTR(insn->phi_list, phi) {
  85                 struct instruction *def;
  86                 if (phi == VOID)
  87                         continue;
  88                 if (i >= nbr)
  89                         return 1;
  90                 def = phi->def;
  91                 assert(def->opcode == OP_PHISOURCE);
  92                 sources[i++] = def;
  93         } END_FOR_EACH_PTR(phi);
  94         return i - nbr;
  95 }
  96
  97 static int if_convert_phi(struct instruction *insn)
  98 {
  99         struct instruction *array[2];
 100         struct basic_block *parents[3];
 101         struct basic_block *bb, *bb1, *bb2, *source;
 102         struct instruction *br;
 103         pseudo_t p1, p2;
 104
 105         bb = insn->bb;
 106         if (get_phisources(array, 2, insn))
 107                 return 0;
 108         if (linearize_ptr_list((struct ptr_list *)bb->parents, (void **)parents, 3) != 2)
 109                 return 0;
 110         p1 = array[0]->phi_src;
 111         bb1 = array[0]->bb;
 112         p2 = array[1]->phi_src;
 113         bb2 = array[1]->bb;
 114
 115         /* Only try the simple "direct parents" case */
 116         if ((bb1 != parents[0] || bb2 != parents[1]) &&
 117             (bb1 != parents[1] || bb2 != parents[0]))
 118                 return 0;
 119
 120         /*
 121          * See if we can find a common source for this..
 122          */
 123         source = phi_parent(bb1, p1);
 124         if (source != phi_parent(bb2, p2))
 125                 return 0;
 126
 127         /*
 128          * Cool. We now know that 'source' is the exclusive
 129          * parent of both phi-nodes, so the exit at the
 130          * end of it fully determines which one it is, and
 131          * we can turn it into a select.
 132          *
 133          * HOWEVER, right now we only handle regular
 134          * conditional branches. No multijumps or computed
 135          * stuff. Verify that here.
 136          */
 137         br = last_instruction(source->insns);
 138         if (!br || br->opcode != OP_CBR)
 139                 return 0;
 140
 141         assert(br->cond);
 142         assert(br->bb_false);
 143
 144         /*
 145          * We're in business. Match up true/false with p1/p2.
 146          */
 147         if (br->bb_true == bb2 || br->bb_false == bb1) {
 148                 pseudo_t p = p1;
 149                 p1 = p2;
 150                 p2 = p;
 151         }
 152
 153         /*
 154          * OK, we can now replace that last
 155          *
 156          *      br cond, a, b
 157          *
 158          * with the sequence
 159          *
 160          *      setcc cond
 161          *      select pseudo, p1, p2
 162          *      br cond, a, b
 163          *
 164          * and remove the phi-node. If it then
 165          * turns out that 'a' or 'b' is entirely
 166          * empty (common case), and now no longer
 167          * a phi-source, we'll be able to simplify
 168          * the conditional branch too.
 169          */
 170         insert_select(source, br, insn, p1, p2);
 171         kill_instruction(insn);
 172         return REPEAT_CSE;
 173 }
 174
 175 ///
 176 // detect trivial phi-nodes
 177 // @insn: the phi-node
 178 // @pseudo: the candidate resulting pseudo (NULL when starting)
 179 // @return: the unique result if the phi-node is trivial, NULL otherwise
 180 //
 181 // A phi-node is trivial if it has a single possible result:
 182 //      * all operands are the same
 183 //      * the operands are themselves defined by a chain or cycle of phi-nodes
 184 //              and the set of all operands involved contains a single value
 185 //              not defined by these phi-nodes
 186 //
 187 // Since the result is unique, these phi-nodes can be removed.
 188 static pseudo_t trivial_phi(pseudo_t pseudo, struct instruction *insn, struct pseudo_list **list)
 189 {
 190         pseudo_t target = insn->target;
 191         pseudo_t phi;
 192
 193         add_pseudo(list, target);
 194
 195         FOR_EACH_PTR(insn->phi_list, phi) {
 196                 struct instruction *def;
 197                 pseudo_t src;
 198
 199                 if (phi == VOID)
 200                         continue;
 201                 def = phi->def;
 202                 if (!def->bb)
 203                         continue;
 204                 src = def->phi_src; // bypass OP_PHISRC & get the real source
 205                 if (src == VOID)
 206                         continue;
 207                 if (!pseudo) {
 208                         pseudo = src;
 209                         continue;
 210                 }
 211                 if (src == pseudo)
 212                         continue;
 213                 if (src == target)
 214                         continue;
 215                 if (DEF_OPCODE(def, src) == OP_PHI) {
 216                         if (pseudo_in_list(*list, src))
 217                                 continue;
 218                         if ((pseudo = trivial_phi(pseudo, def, list)))
 219                                 continue;
 220                 }
 221                 return NULL;
 222         } END_FOR_EACH_PTR(phi);
 223
 224         return pseudo ? pseudo : VOID;
 225 }
 226
 227 static int clean_up_phi(struct instruction *insn)
 228 {
 229         struct pseudo_list *list = NULL;
 230         pseudo_t pseudo;
 231
 232         if ((pseudo = trivial_phi(NULL, insn, &list))) {
 233                 convert_instruction_target(insn, pseudo);
 234                 kill_instruction(insn);
 235                 return REPEAT_CSE;
 236         }
 237
 238         return if_convert_phi(insn);
 239 }
 240
 241 static int delete_pseudo_user_list_entry(struct pseudo_user_list **list, pseudo_t *entry, int count)
 242 {
 243         struct pseudo_user *pu;
 244
 245         FOR_EACH_PTR(*list, pu) {
 246                 if (pu->userp == entry) {
 247                         MARK_CURRENT_DELETED(pu);
 248                         if (!--count)
 249                                 goto out;
 250                 }
 251         } END_FOR_EACH_PTR(pu);
 252         assert(count <= 0);
 253 out:
 254         if (pseudo_user_list_empty(*list))
 255                 *list = NULL;
 256         return count;
 257 }
 258
 259 static inline void rem_usage(pseudo_t p, pseudo_t *usep, int kill)
 260 {
 261         if (has_use_list(p)) {
 262                 if (p->type == PSEUDO_SYM)
 263                         repeat_phase |= REPEAT_SYMBOL_CLEANUP;
 264                 delete_pseudo_user_list_entry(&p->users, usep, 1);
 265                 if (kill && !p->users)
 266                         kill_instruction(p->def);
 267         }
 268 }
 269
 270 static inline void remove_usage(pseudo_t p, pseudo_t *usep)
 271 {
 272         rem_usage(p, usep, 1);
 273 }
 274
 275 void kill_use(pseudo_t *usep)
 276 {
 277         if (usep) {
 278                 pseudo_t p = *usep;
 279                 *usep = VOID;
 280                 rem_usage(p, usep, 1);
 281         }
 282 }
 283
 284 // Like kill_use() but do not (recursively) kill dead instructions
 285 void remove_use(pseudo_t *usep)
 286 {
 287         pseudo_t p = *usep;
 288         *usep = VOID;
 289         rem_usage(p, usep, 0);
 290 }
 291
 292 static void kill_use_list(struct pseudo_list *list)
 293 {
 294         pseudo_t p;
 295         FOR_EACH_PTR(list, p) {
 296                 if (p == VOID)
 297                         continue;
 298                 kill_use(THIS_ADDRESS(p));
 299         } END_FOR_EACH_PTR(p);
 300 }
 301
 302 ///
 303 // kill an instruction
 304 // @insn: the instruction to be killed
 305 // @force: if unset, the normal case, the instruction is not killed
 306 //      if not free of possible side-effect; if set the instruction
 307 //      is unconditionally killed.
 308 //
 309 // The killed instruction is removed from its BB and the usage
 310 // of all its operands are removed. The instruction is also
 311 // marked as killed by setting its ->bb to NULL.
 312 int kill_insn(struct instruction *insn, int force)
 313 {
 314         if (!insn || !insn->bb)
 315                 return 0;
 316
 317         switch (insn->opcode) {
 318         case OP_SEL:
 319         case OP_RANGE:
 320                 kill_use(&insn->src3);
 321                 /* fall through */
 322
 323         case OP_BINARY ... OP_BINCMP_END:
 324                 kill_use(&insn->src2);
 325                 /* fall through */
 326
 327         case OP_UNOP ... OP_UNOP_END:
 328         case OP_SETVAL:
 329         case OP_SLICE:
 330                 kill_use(&insn->src1);
 331                 break;
 332
 333         case OP_PHI:
 334                 kill_use_list(insn->phi_list);
 335                 break;
 336         case OP_PHISOURCE:
 337                 kill_use(&insn->phi_src);
 338                 break;
 339
 340         case OP_SYMADDR:
 341                 kill_use(&insn->src);
 342                 repeat_phase |= REPEAT_SYMBOL_CLEANUP;
 343                 break;
 344
 345         case OP_CBR:
 346         case OP_SWITCH:
 347         case OP_COMPUTEDGOTO:
 348                 kill_use(&insn->cond);
 349                 break;
 350
 351         case OP_CALL:
 352                 if (!force) {
 353                         /* a "pure" function can be killed too */
 354                         if (!(insn->func->type == PSEUDO_SYM))
 355                                 return 0;
 356                         if (!(insn->func->sym->ctype.modifiers & MOD_PURE))
 357                                 return 0;
 358                 }
 359                 kill_use_list(insn->arguments);
 360                 if (insn->func->type == PSEUDO_REG)
 361                         kill_use(&insn->func);
 362                 break;
 363
 364         case OP_LOAD:
 365                 if (!force && insn->is_volatile)
 366                         return 0;
 367                 kill_use(&insn->src);
 368                 break;
 369
 370         case OP_STORE:
 371                 if (!force)
 372                         return 0;
 373                 kill_use(&insn->src);
 374                 kill_use(&insn->target);
 375                 break;
 376
 377         case OP_ENTRY:
 378                 /* ignore */
 379                 return 0;
 380
 381         case OP_BR:
 382         case OP_SETFVAL:
 383         default:
 384                 break;
 385         }
 386
 387         insn->bb = NULL;
 388         return repeat_phase |= REPEAT_CSE;
 389 }
 390
 391 ///
 392 // kill trivially dead instructions
 393 static int dead_insn(struct instruction *insn, pseudo_t *src1, pseudo_t *src2, pseudo_t *src3)
 394 {
 395         if (has_users(insn->target))
 396                 return 0;
 397
 398         insn->bb = NULL;
 399         kill_use(src1);
 400         kill_use(src2);
 401         kill_use(src3);
 402         return REPEAT_CSE;
 403 }
 404
 405 static inline bool has_target(struct instruction *insn)
 406 {
 407         return opcode_table[insn->opcode].flags & OPF_TARGET;
 408 }
 409
 410 void remove_dead_insns(struct entrypoint *ep)
 411 {
 412         struct basic_block *bb;
 413
 414         FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
 415                 struct instruction *insn;
 416                 FOR_EACH_PTR_REVERSE(bb->insns, insn) {
 417                         if (!insn->bb)
 418                                 continue;
 419                         if (!has_target(insn))
 420                                 continue;
 421                         if (!has_users(insn->target))
 422                                 kill_instruction(insn);
 423                 } END_FOR_EACH_PTR_REVERSE(insn);
 424         } END_FOR_EACH_PTR_REVERSE(bb);
 425 }
 426
 427 static inline int constant(pseudo_t pseudo)
 428 {
 429         return pseudo->type == PSEUDO_VAL;
 430 }
 431
 432 ///
 433 // replace the operand of an instruction
 434 // @insn: the instruction
 435 // @pp: the address of the instruction's operand
 436 // @new: the new value for the operand
 437 // @return: REPEAT_CSE.
 438 static inline int replace_pseudo(struct instruction *insn, pseudo_t *pp, pseudo_t new)
 439 {
 440         pseudo_t old = *pp;
 441         use_pseudo(insn, new, pp);
 442         remove_usage(old, pp);
 443         return REPEAT_CSE;
 444 }
 445
 446 static int replace_with_pseudo(struct instruction *insn, pseudo_t pseudo)
 447 {
 448         convert_instruction_target(insn, pseudo);
 449
 450         switch (insn->opcode) {
 451         case OP_SEL:
 452         case OP_RANGE:
 453                 kill_use(&insn->src3);
 454         case OP_BINARY ... OP_BINCMP_END:
 455                 kill_use(&insn->src2);
 456         case OP_UNOP ... OP_UNOP_END:
 457         case OP_SYMADDR:
 458                 kill_use(&insn->src1);
 459                 break;
 460
 461         default:
 462                 assert(0);
 463         }
 464         insn->bb = NULL;
 465         return REPEAT_CSE;
 466 }
 467
 468 static inline int def_opcode(pseudo_t p)
 469 {
 470         if (p->type != PSEUDO_REG)
 471                 return OP_BADOP;
 472         return p->def->opcode;
 473 }
 474
 475 static unsigned int value_size(long long value)
 476 {
 477         value >>= 8;
 478         if (!value)
 479                 return 8;
 480         value >>= 8;
 481         if (!value)
 482                 return 16;
 483         value >>= 16;
 484         if (!value)
 485                 return 32;
 486         return 64;
 487 }
 488
 489 ///
 490 // try to determine the maximum size of bits in a pseudo
 491 //
 492 // Right now this only follow casts and constant values, but we
 493 // could look at things like AND instructions, etc.
 494 static unsigned int operand_size(struct instruction *insn, pseudo_t pseudo)
 495 {
 496         unsigned int size = insn->size;
 497
 498         if (pseudo->type == PSEUDO_REG) {
 499                 struct instruction *src = pseudo->def;
 500                 if (src && src->opcode == OP_ZEXT && src->orig_type) {
 501                         unsigned int orig_size = src->orig_type->bit_size;
 502                         if (orig_size < size)
 503                                 size = orig_size;
 504                 }
 505         }
 506         if (pseudo->type == PSEUDO_VAL) {
 507                 unsigned int orig_size = value_size(pseudo->value);
 508                 if (orig_size < size)
 509                         size = orig_size;
 510         }
 511         return size;
 512 }
 513
 514 static pseudo_t eval_insn(struct instruction *insn)
 515 {
 516         /* FIXME! Verify signs and sizes!! */
 517         unsigned int size = insn->size;
 518         long long left = insn->src1->value;
 519         long long right = insn->src2->value;
 520         unsigned long long ul, ur;
 521         long long res, mask, bits;
 522
 523         mask = 1ULL << (size-1);
 524         bits = mask | (mask-1);
 525
 526         if (left & mask)
 527                 left |= ~bits;
 528         if (right & mask)
 529                 right |= ~bits;
 530         ul = left & bits;
 531         ur = right & bits;
 532
 533         switch (insn->opcode) {
 534         case OP_ADD:
 535                 res = left + right;
 536                 break;
 537         case OP_SUB:
 538                 res = left - right;
 539                 break;
 540         case OP_MUL:
 541                 res = ul * ur;
 542                 break;
 543         case OP_DIVU:
 544                 if (!ur)
 545                         goto undef;
 546                 res = ul / ur;
 547                 break;
 548         case OP_DIVS:
 549                 if (!right)
 550                         goto undef;
 551                 if (left == mask && right == -1)
 552                         goto undef;
 553                 res = left / right;
 554                 break;
 555         case OP_MODU:
 556                 if (!ur)
 557                         goto undef;
 558                 res = ul % ur;
 559                 break;
 560         case OP_MODS:
 561                 if (!right)
 562                         goto undef;
 563                 if (left == mask && right == -1)
 564                         goto undef;
 565                 res = left % right;
 566                 break;
 567         case OP_SHL:
 568                 if (ur >= size)
 569                         goto undef;
 570                 res = left << right;
 571                 break;
 572         case OP_LSR:
 573                 if (ur >= size)
 574                         goto undef;
 575                 res = ul >> ur;
 576                 break;
 577         case OP_ASR:
 578                 if (ur >= size)
 579                         goto undef;
 580                 res = left >> right;
 581                 break;
 582        /* Logical */
 583         case OP_AND:
 584                 res = left & right;
 585                 break;
 586         case OP_OR:
 587                 res = left | right;
 588                 break;
 589         case OP_XOR:
 590                 res = left ^ right;
 591                 break;
 592
 593         /* Binary comparison */
 594         case OP_SET_EQ:
 595                 res = left == right;
 596                 break;
 597         case OP_SET_NE:
 598                 res = left != right;
 599                 break;
 600         case OP_SET_LE:
 601                 res = left <= right;
 602                 break;
 603         case OP_SET_GE:
 604                 res = left >= right;
 605                 break;
 606         case OP_SET_LT:
 607                 res = left < right;
 608                 break;
 609         case OP_SET_GT:
 610                 res = left > right;
 611                 break;
 612         case OP_SET_B:
 613                 res = ul < ur;
 614                 break;
 615         case OP_SET_A:
 616                 res = ul > ur;
 617                 break;
 618         case OP_SET_BE:
 619                 res = ul <= ur;
 620                 break;
 621         case OP_SET_AE:
 622                 res = ul >= ur;
 623                 break;
 624         default:
 625                 return NULL;
 626         }
 627         res &= bits;
 628
 629         return value_pseudo(res);
 630
 631 undef:
 632         return NULL;
 633 }
 634
 635 ///
 636 // Simplifications
 637 // ^^^^^^^^^^^^^^^
 638
 639 ///
 640 // try to simplify MASK(OR(AND(x, M'), b), M)
 641 // @insn: the masking instruction
 642 // @mask: the associated mask (M)
 643 // @ora: one of the OR's operands, guaranteed to be PSEUDO_REG
 644 // @orb: the other OR's operand
 645 // @return: 0 if no changes have been made, one or more REPEAT_* flags otherwise.
 646 static int simplify_mask_or_and(struct instruction *insn, unsigned long long mask,
 647         pseudo_t ora, pseudo_t orb)
 648 {
 649         unsigned long long omask, nmask;
 650         struct instruction *and = ora->def;
 651         pseudo_t src2 = and->src2;
 652
 653         if (and->opcode != OP_AND)
 654                 return 0;
 655         if (!constant(src2))
 656                 return 0;
 657         omask = src2->value;
 658         nmask = omask & mask;
 659         if (nmask == 0) {
 660                 // if (M' & M) == 0: ((a & M') | b) -> b
 661                 return replace_pseudo(insn, &insn->src1, orb);
 662         }
 663         if (multi_users(insn->src1))
 664                 return 0;       // can't modify anything inside the OR
 665         if (nmask == mask) {
 666                 struct instruction *or = insn->src1->def;
 667                 pseudo_t *arg = (ora == or->src1) ? &or->src1 : &or->src2;
 668                 // if (M' & M) == M: ((a & M') | b) -> (a | b)
 669                 return replace_pseudo(or, arg, and->src1);
 670         }
 671         if (nmask != omask && !multi_users(ora)) {
 672                 // if (M' & M) != M': AND(a, M') -> AND(a, (M' & M))
 673                 and->src2 = value_pseudo(nmask);
 674                 return REPEAT_CSE;
 675         }
 676         return 0;
 677 }
 678
 679 ///
 680 // try to simplify MASK(OR(a, b), M)
 681 // @insn: the masking instruction
 682 // @mask: the associated mask (M)
 683 // @or: the OR instruction
 684 // @return: 0 if no changes have been made, one or more REPEAT_* flags otherwise.
 685 static int simplify_mask_or(struct instruction *insn, unsigned long long mask, struct instruction *or)
 686 {
 687         pseudo_t src1 = or->src1;
 688         pseudo_t src2 = or->src2;
 689         int rc;
 690
 691         if (src1->type == PSEUDO_REG) {
 692                 if ((rc = simplify_mask_or_and(insn, mask, src1, src2)))
 693                         return rc;
 694         }
 695         if (src2->type == PSEUDO_REG) {
 696                 if ((rc = simplify_mask_or_and(insn, mask, src2, src1)))
 697                         return rc;
 698         } else if (src2->type == PSEUDO_VAL) {
 699                 unsigned long long oval = src2->value;
 700                 unsigned long long nval = oval & mask;
 701                 // Try to simplify:
 702                 //      MASK(OR(x, C), M)
 703                 if (nval == 0) {
 704                         // if (C & M) == 0: OR(x, C) -> x
 705                         return replace_pseudo(insn, &insn->src1, src1);
 706                 }
 707                 if (nval == mask) {
 708                         // if (C & M) == M: OR(x, C) -> M
 709                         return replace_pseudo(insn, &insn->src1, value_pseudo(mask));
 710                 }
 711                 if (nval != oval && !multi_users(or->target)) {
 712                         // if (C & M) != C: OR(x, C) -> OR(x, (C & M))
 713                         return replace_pseudo(or, &or->src2, value_pseudo(nval));
 714                 }
 715         }
 716         return 0;
 717 }
 718
 719 ///
 720 // try to simplify MASK(SHIFT(OR(a, b), S), M)
 721 // @sh: the shift instruction
 722 // @or: the OR instruction
 723 // @mask: the mask associated to MASK (M):
 724 // @return: 0 if no changes have been made, one or more REPEAT_* flags otherwise.
 725 static int simplify_mask_shift_or(struct instruction *sh, struct instruction *or, unsigned long long mask)
 726 {
 727         unsigned long long smask = bits_mask(sh->size);
 728         int shift = sh->src2->value;
 729
 730         if (sh->opcode == OP_LSR)
 731                 mask <<= shift;
 732         else
 733                 mask >>= shift;
 734         return simplify_mask_or(sh, smask & mask, or);
 735 }
 736
 737 static int simplify_mask_shift(struct instruction *sh, unsigned long long mask)
 738 {
 739         struct instruction *inner;
 740
 741         if (!constant(sh->src2) || sh->tainted)
 742                 return 0;
 743         switch (DEF_OPCODE(inner, sh->src1)) {
 744         case OP_OR:
 745                 if (!multi_users(sh->target))
 746                         return simplify_mask_shift_or(sh, inner, mask);
 747                 break;
 748         }
 749         return 0;
 750 }
 751
 752 static long long check_shift_count(struct instruction *insn, unsigned long long uval)
 753 {
 754         unsigned int size = insn->size;
 755         long long sval = uval;
 756
 757         if (insn->tainted)
 758                 return -1;
 759
 760         if (uval < size)
 761                 return uval;
 762
 763         insn->tainted = 1;
 764         sval = sign_extend_safe(sval, size);
 765         sval = sign_extend_safe(sval, bits_in_int);
 766         if (sval < 0)
 767                 insn->src2 = value_pseudo(sval);
 768         return -1;
 769 }
 770
 771 static int simplify_shift(struct instruction *insn, pseudo_t pseudo, long long value)
 772 {
 773         struct instruction *def;
 774         unsigned long long mask, omask, nmask;
 775         unsigned long long nval;
 776         unsigned int size;
 777         pseudo_t src2;
 778
 779         if (!value)
 780                 return replace_with_pseudo(insn, pseudo);
 781         value = check_shift_count(insn, value);
 782         if (value < 0)
 783                 return 0;
 784
 785         size = insn->size;
 786         switch (insn->opcode) {
 787         case OP_ASR:
 788                 if (value >= size)
 789                         return 0;
 790                 if (pseudo->type != PSEUDO_REG)
 791                         break;
 792                 def = pseudo->def;
 793                 switch (def->opcode) {
 794                 case OP_LSR:
 795                 case OP_ASR:
 796                         if (def == insn)        // cyclic DAG!
 797                                 break;
 798                         src2 = def->src2;
 799                         if (src2->type != PSEUDO_VAL)
 800                                 break;
 801                         nval = src2->value;
 802                         if (nval > insn->size || nval == 0)
 803                                 break;
 804                         value += nval;
 805                         if (def->opcode == OP_LSR)
 806                                 insn->opcode = OP_LSR;
 807                         else if (value >= size)
 808                                 value = size - 1;
 809                         goto new_value;
 810
 811                 case OP_ZEXT:
 812                         // transform:
 813                         //      zext.N  %t <- (O) %a
 814                         //      asr.N   %r <- %t, C
 815                         // into
 816                         //      zext.N  %t <- (O) %a
 817                         //      lsr.N   %r <- %t, C
 818                         insn->opcode = OP_LSR;
 819                         return REPEAT_CSE;
 820                 }
 821                 break;
 822         case OP_LSR:
 823                 size = operand_size(insn, pseudo);
 824                 if (value >= size)
 825                         goto zero;
 826                 switch(DEF_OPCODE(def, pseudo)) {
 827                 case OP_AND:
 828                         // replace (A & M) >> S
 829                         // by      (A >> S) & (M >> S)
 830                         if (!constant(def->src2))
 831                                 break;
 832                         mask = bits_mask(insn->size - value) << value;
 833                         omask = def->src2->value;
 834                         nmask = omask & mask;
 835                         if (nmask == 0)
 836                                 return replace_with_pseudo(insn, value_pseudo(0));
 837                         if (nmask == mask)
 838                                 return replace_pseudo(insn, &insn->src1, def->src1);
 839                         if (nbr_users(pseudo) > 1)
 840                                 break;
 841                         def->opcode = OP_LSR;
 842                         def->src2 = insn->src2;
 843                         insn->opcode = OP_AND;
 844                         insn->src2 = value_pseudo(omask >> value);
 845                         return REPEAT_CSE;
 846                 case OP_LSR:
 847                         goto case_shift_shift;
 848                 case OP_OR:
 849                         mask = bits_mask(size);
 850                         return simplify_mask_shift_or(insn, def, mask);
 851                 case OP_SHL:
 852                         // replace ((x << S) >> S)
 853                         // by      (x & (-1 >> S))
 854                         if (def->src2 != insn->src2)
 855                                 break;
 856                         mask = bits_mask(insn->size - value);
 857                         goto replace_mask;
 858                 }
 859                 break;
 860         case OP_SHL:
 861                 if (value >= size)
 862                         goto zero;
 863                 switch(DEF_OPCODE(def, pseudo)) {
 864                 case OP_AND:
 865                         // simplify (A & M) << S
 866                         if (!constant(def->src2))
 867                                 break;
 868                         mask = bits_mask(insn->size) >> value;
 869                         omask = def->src2->value;
 870                         nmask = omask & mask;
 871                         if (nmask == 0)
 872                                 return replace_with_pseudo(insn, value_pseudo(0));
 873                         if (nmask == mask)
 874                                 return replace_pseudo(insn, &insn->src1, def->src1);
 875                         // do not simplify into ((A << S) & (M << S))
 876                         break;
 877                 case OP_LSR:
 878                         // replace ((x >> S) << S)
 879                         // by      (x & (-1 << S))
 880                         if (def->src2 != insn->src2)
 881                                 break;
 882                         mask = bits_mask(insn->size - value) << value;
 883                         goto replace_mask;
 884                 case OP_OR:
 885                         mask = bits_mask(size);
 886                         return simplify_mask_shift_or(insn, def, mask);
 887                 case OP_SHL:
 888                 case_shift_shift:               // also for LSR - LSR
 889                         if (def == insn)        // cyclic DAG!
 890                                 break;
 891                         src2 = def->src2;
 892                         if (src2->type != PSEUDO_VAL)
 893                                 break;
 894                         nval = src2->value;
 895                         if (nval > insn->size)
 896                                 break;
 897                         value += nval;
 898                         goto new_value;
 899                 }
 900                 break;
 901         }
 902         return 0;
 903
 904 new_value:
 905         if (value < size) {
 906                 insn->src2 = value_pseudo(value);
 907                 return replace_pseudo(insn, &insn->src1, pseudo->def->src1);
 908         }
 909 zero:
 910         return replace_with_pseudo(insn, value_pseudo(0));
 911 replace_mask:
 912         insn->opcode = OP_AND;
 913         insn->src2 = value_pseudo(mask);
 914         return replace_pseudo(insn, &insn->src1, def->src1);
 915 }
 916
 917 static int simplify_mul_div(struct instruction *insn, long long value)
 918 {
 919         unsigned long long sbit = 1ULL << (insn->size - 1);
 920         unsigned long long bits = sbit | (sbit - 1);
 921
 922         if (value == 1)
 923                 return replace_with_pseudo(insn, insn->src1);
 924
 925         switch (insn->opcode) {
 926         case OP_MUL:
 927                 if (value == 0)
 928                         return replace_with_pseudo(insn, insn->src2);
 929         /* Fall through */
 930         case OP_DIVS:
 931                 if (!(value & sbit))    // positive
 932                         break;
 933
 934                 value |= ~bits;
 935                 if (value == -1) {
 936                         insn->opcode = OP_NEG;
 937                         return REPEAT_CSE;
 938                 }
 939         }
 940
 941         return 0;
 942 }
 943
 944 static int simplify_seteq_setne(struct instruction *insn, long long value)
 945 {
 946         pseudo_t old = insn->src1;
 947         struct instruction *def;
 948         unsigned osize;
 949         int inverse;
 950         int opcode;
 951
 952         if (value != 0 && value != 1)
 953                 return 0;
 954
 955         if (old->type != PSEUDO_REG)
 956                 return 0;
 957         def = old->def;
 958         if (!def)
 959                 return 0;
 960
 961         inverse = (insn->opcode == OP_SET_NE) == value;
 962         if (!inverse && def->size == 1 && insn->size == 1) {
 963                 // Replace:
 964                 //      setne   %r <- %s, $0
 965                 // or:
 966                 //      seteq   %r <- %s, $1
 967                 // by %s when boolean
 968                 return replace_with_pseudo(insn, old);
 969         }
 970         opcode = def->opcode;
 971         switch (opcode) {
 972         case OP_AND:
 973                 if (inverse)
 974                         break;
 975                 if (def->size != insn->size)
 976                         break;
 977                 if (def->src2->type != PSEUDO_VAL)
 978                         break;
 979                 if (def->src2->value != 1)
 980                         break;
 981                 return replace_with_pseudo(insn, old);
 982         case OP_FPCMP ... OP_BINCMP_END:
 983                 // Convert:
 984                 //      setcc.n %t <- %a, %b
 985                 //      setne.m %r <- %t, $0
 986                 // into:
 987                 //      setcc.n %t <- %a, %b
 988                 //      setcc.m %r <- %a, $b
 989                 // and similar for setne/eq ... 0/1
 990                 insn->opcode = inverse ? opcode_table[opcode].negate : opcode;
 991                 use_pseudo(insn, def->src1, &insn->src1);
 992                 use_pseudo(insn, def->src2, &insn->src2);
 993                 remove_usage(old, &insn->src1);
 994                 return REPEAT_CSE;
 995
 996         case OP_SEXT:
 997                 if (value && (def->orig_type->bit_size == 1))
 998                         break;
 999                 /* Fall through */
1000         case OP_ZEXT:
1001                 // Convert:
1002                 //      *ext.m  %s <- (1) %a
1003                 //      setne.1 %r <- %s, $0
1004                 // into:
1005                 //      setne.1 %s <- %a, $0
1006                 // and same for setne/eq ... 0/1
1007                 return replace_pseudo(insn, &insn->src1, def->src);
1008         case OP_TRUNC:
1009                 if (multi_users(old))
1010                         break;
1011                 // convert
1012                 //      trunc.n %s <- (o) %a
1013                 //      setne.m %r <- %s, $0
1014                 // into:
1015                 //      and.o   %s <- %a, $((1 << o) - 1)
1016                 //      setne.m %r <- %s, $0
1017                 // and same for setne/eq ... 0/1
1018                 osize = def->size;
1019                 def->opcode = OP_AND;
1020                 def->type = def->orig_type;
1021                 def->size = def->type->bit_size;
1022                 def->src2 = value_pseudo(bits_mask(osize));
1023                 return REPEAT_CSE;
1024         }
1025         return 0;
1026 }
1027
1028 static int simplify_constant_mask(struct instruction *insn, unsigned long long mask)
1029 {
1030         pseudo_t old = insn->src1;
1031         unsigned long long omask;
1032         unsigned long long nmask;
1033         struct instruction *def;
1034         int osize;
1035
1036         switch (DEF_OPCODE(def, old)) {
1037         case OP_FPCMP ... OP_BINCMP_END:
1038                 osize = 1;
1039                 goto oldsize;
1040         case OP_OR:
1041                 return simplify_mask_or(insn, mask, def);
1042         case OP_LSR:
1043         case OP_SHL:
1044                 return simplify_mask_shift(def, mask);
1045         case OP_ZEXT:
1046                 osize = def->orig_type->bit_size;
1047                 /* fall through */
1048         oldsize:
1049                 omask = (1ULL << osize) - 1;
1050                 nmask = mask & omask;
1051                 if (nmask == omask)
1052                         // the AND mask is redundant
1053                         return replace_with_pseudo(insn, old);
1054                 if (nmask != mask) {
1055                         // can use a smaller mask
1056                         insn->src2 = value_pseudo(nmask);
1057                         return REPEAT_CSE;
1058                 }
1059                 break;
1060         }
1061         return 0;
1062 }
1063
1064 static int simplify_constant_rightside(struct instruction *insn)
1065 {
1066         long long value = insn->src2->value;
1067         long long sbit = 1ULL << (insn->size - 1);
1068         long long bits = sbit | (sbit - 1);
1069
1070         switch (insn->opcode) {
1071         case OP_OR:
1072                 if ((value & bits) == bits)
1073                         return replace_with_pseudo(insn, insn->src2);
1074                 goto case_neutral_zero;
1075
1076         case OP_XOR:
1077                 if ((value & bits) == bits) {
1078                         insn->opcode = OP_NOT;
1079                         return REPEAT_CSE;
1080                 }
1081                 goto case_neutral_zero;
1082
1083         case OP_SUB:
1084                 if (value) {
1085                         insn->opcode = OP_ADD;
1086                         insn->src2 = value_pseudo(-value);
1087                         return REPEAT_CSE;
1088                 }
1089         /* Fall through */
1090         case OP_ADD:
1091         case_neutral_zero:
1092                 if (!value)
1093                         return replace_with_pseudo(insn, insn->src1);
1094                 return 0;
1095         case OP_ASR:
1096         case OP_SHL:
1097         case OP_LSR:
1098                 return simplify_shift(insn, insn->src1, value);
1099
1100         case OP_MODU: case OP_MODS:
1101                 if (value == 1)
1102                         return replace_with_pseudo(insn, value_pseudo(0));
1103                 return 0;
1104
1105         case OP_DIVU: case OP_DIVS:
1106         case OP_MUL:
1107                 return simplify_mul_div(insn, value);
1108
1109         case OP_AND:
1110                 if (!value)
1111                         return replace_with_pseudo(insn, insn->src2);
1112                 if ((value & bits) == bits)
1113                         return replace_with_pseudo(insn, insn->src1);
1114                 return simplify_constant_mask(insn, value);
1115
1116         case OP_SET_NE:
1117         case OP_SET_EQ:
1118                 return simplify_seteq_setne(insn, value);
1119         }
1120         return 0;
1121 }
1122
1123 static int simplify_constant_leftside(struct instruction *insn)
1124 {
1125         long long value = insn->src1->value;
1126
1127         switch (insn->opcode) {
1128         case OP_ADD: case OP_OR: case OP_XOR:
1129                 if (!value)
1130                         return replace_with_pseudo(insn, insn->src2);
1131                 return 0;
1132
1133         case OP_SHL:
1134         case OP_LSR: case OP_ASR:
1135         case OP_AND:
1136         case OP_MUL:
1137                 if (!value)
1138                         return replace_with_pseudo(insn, insn->src1);
1139                 return 0;
1140         }
1141         return 0;
1142 }
1143
1144 static int simplify_constant_binop(struct instruction *insn)
1145 {
1146         pseudo_t res = eval_insn(insn);
1147
1148         if (!res)
1149                 return 0;
1150
1151         replace_with_pseudo(insn, res);
1152         return REPEAT_CSE;
1153 }
1154
1155 static int simplify_binop_same_args(struct instruction *insn, pseudo_t arg)
1156 {
1157         switch (insn->opcode) {
1158         case OP_SET_NE:
1159         case OP_SET_LT: case OP_SET_GT:
1160         case OP_SET_B:  case OP_SET_A:
1161                 if (Wtautological_compare)
1162                         warning(insn->pos, "self-comparison always evaluates to false");
1163         case OP_SUB:
1164         case OP_XOR:
1165                 return replace_with_pseudo(insn, value_pseudo(0));
1166
1167         case OP_SET_EQ:
1168         case OP_SET_LE: case OP_SET_GE:
1169         case OP_SET_BE: case OP_SET_AE:
1170                 if (Wtautological_compare)
1171                         warning(insn->pos, "self-comparison always evaluates to true");
1172                 return replace_with_pseudo(insn, value_pseudo(1));
1173
1174         case OP_AND:
1175         case OP_OR:
1176                 return replace_with_pseudo(insn, arg);
1177
1178         default:
1179                 break;
1180         }
1181
1182         return 0;
1183 }
1184
1185 static int simplify_binop(struct instruction *insn)
1186 {
1187         if (dead_insn(insn, &insn->src1, &insn->src2, NULL))
1188                 return REPEAT_CSE;
1189         if (constant(insn->src1)) {
1190                 if (constant(insn->src2))
1191                         return simplify_constant_binop(insn);
1192                 return simplify_constant_leftside(insn);
1193         }
1194         if (constant(insn->src2))
1195                 return simplify_constant_rightside(insn);
1196         if (insn->src1 == insn->src2)
1197                 return simplify_binop_same_args(insn, insn->src1);
1198         return 0;
1199 }
1200
1201 static void switch_pseudo(struct instruction *insn1, pseudo_t *pp1, struct instruction *insn2, pseudo_t *pp2)
1202 {
1203         pseudo_t p1 = *pp1, p2 = *pp2;
1204
1205         use_pseudo(insn1, p2, pp1);
1206         use_pseudo(insn2, p1, pp2);
1207         remove_usage(p1, pp1);
1208         remove_usage(p2, pp2);
1209 }
1210
1211 static int canonical_order(pseudo_t p1, pseudo_t p2)
1212 {
1213         /* symbol/constants on the right */
1214         if (p1->type == PSEUDO_VAL)
1215                 return p2->type == PSEUDO_VAL;
1216
1217         if (p1->type == PSEUDO_SYM)
1218                 return p2->type == PSEUDO_SYM || p2->type == PSEUDO_VAL;
1219
1220         return 1;
1221 }
1222
1223 static int canonicalize_commutative(struct instruction *insn)
1224 {
1225         if (canonical_order(insn->src1, insn->src2))
1226                 return 0;
1227
1228         switch_pseudo(insn, &insn->src1, insn, &insn->src2);
1229         return repeat_phase |= REPEAT_CSE;
1230 }
1231
1232 static int canonicalize_compare(struct instruction *insn)
1233 {
1234         if (canonical_order(insn->src1, insn->src2))
1235                 return 0;
1236
1237         switch_pseudo(insn, &insn->src1, insn, &insn->src2);
1238         insn->opcode = opcode_table[insn->opcode].swap;
1239         return repeat_phase |= REPEAT_CSE;
1240 }
1241
1242 static inline int simple_pseudo(pseudo_t pseudo)
1243 {
1244         return pseudo->type == PSEUDO_VAL || pseudo->type == PSEUDO_SYM;
1245 }
1246
1247 static int simplify_associative_binop(struct instruction *insn)
1248 {
1249         struct instruction *def;
1250         pseudo_t pseudo = insn->src1;
1251
1252         if (!simple_pseudo(insn->src2))
1253                 return 0;
1254         if (pseudo->type != PSEUDO_REG)
1255                 return 0;
1256         def = pseudo->def;
1257         if (def == insn)
1258                 return 0;
1259         if (def->opcode != insn->opcode)
1260                 return 0;
1261         if (!simple_pseudo(def->src2))
1262                 return 0;
1263         if (multi_users(def->target))
1264                 return 0;
1265         switch_pseudo(def, &def->src1, insn, &insn->src2);
1266         return REPEAT_CSE;
1267 }
1268
1269 static int simplify_constant_unop(struct instruction *insn)
1270 {
1271         long long val = insn->src1->value;
1272         long long res, mask;
1273
1274         switch (insn->opcode) {
1275         case OP_NOT:
1276                 res = ~val;
1277                 break;
1278         case OP_NEG:
1279                 res = -val;
1280                 break;
1281         case OP_SEXT:
1282                 mask = 1ULL << (insn->orig_type->bit_size-1);
1283                 if (val & mask)
1284                         val |= ~(mask | (mask-1));
1285                 /* fall through */
1286         case OP_ZEXT:
1287         case OP_TRUNC:
1288                 res = val;
1289                 break;
1290         default:
1291                 return 0;
1292         }
1293         mask = 1ULL << (insn->size-1);
1294         res &= mask | (mask-1);
1295
1296         replace_with_pseudo(insn, value_pseudo(res));
1297         return REPEAT_CSE;
1298 }
1299
1300 static int simplify_unop(struct instruction *insn)
1301 {
1302         if (dead_insn(insn, &insn->src1, NULL, NULL))
1303                 return REPEAT_CSE;
1304         if (constant(insn->src1))
1305                 return simplify_constant_unop(insn);
1306
1307         switch (insn->opcode) {
1308                 struct instruction *def;
1309
1310         case OP_NOT:
1311                 def = insn->src->def;
1312                 if (def && def->opcode == OP_NOT)
1313                         return replace_with_pseudo(insn, def->src);
1314                 break;
1315         case OP_NEG:
1316                 def = insn->src->def;
1317                 if (def && def->opcode == OP_NEG)
1318                         return replace_with_pseudo(insn, def->src);
1319                 break;
1320         default:
1321                 return 0;
1322         }
1323         return 0;
1324 }
1325
1326 static int simplify_one_memop(struct instruction *insn, pseudo_t orig)
1327 {
1328         pseudo_t addr = insn->src;
1329         pseudo_t new, off;
1330
1331         if (addr->type == PSEUDO_REG) {
1332                 struct instruction *def = addr->def;
1333                 if (def->opcode == OP_SYMADDR && def->src) {
1334                         kill_use(&insn->src);
1335                         use_pseudo(insn, def->src, &insn->src);
1336                         return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
1337                 }
1338                 if (def->opcode == OP_ADD) {
1339                         new = def->src1;
1340                         off = def->src2;
1341                         if (constant(off))
1342                                 goto offset;
1343                         new = off;
1344                         off = def->src1;
1345                         if (constant(off))
1346                                 goto offset;
1347                         return 0;
1348                 }
1349         }
1350         return 0;
1351
1352 offset:
1353         /* Invalid code */
1354         if (new == orig || new == addr) {
1355                 if (new == VOID)
1356                         return 0;
1357                 /*
1358                  * If some BB have been removed it is possible that this
1359                  * memop is in fact part of a dead BB. In this case
1360                  * we must not warn since nothing is wrong.
1361                  * If not part of a dead BB this will be redone after
1362                  * the BBs have been cleaned up.
1363                  */
1364                 if (repeat_phase & REPEAT_CFG_CLEANUP)
1365                         return 0;
1366                 warning(insn->pos, "crazy programmer");
1367                 replace_pseudo(insn, &insn->src, VOID);
1368                 return 0;
1369         }
1370         insn->offset += off->value;
1371         replace_pseudo(insn, &insn->src, new);
1372         return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
1373 }
1374
1375 ///
1376 // simplify memops instructions
1377 //
1378 // :note: We walk the whole chain of adds/subs backwards.
1379 //      That's not only more efficient, but it allows us to find loops.
1380 static int simplify_memop(struct instruction *insn)
1381 {
1382         int one, ret = 0;
1383         pseudo_t orig = insn->src;
1384
1385         do {
1386                 one = simplify_one_memop(insn, orig);
1387                 ret |= one;
1388         } while (one);
1389         return ret;
1390 }
1391
1392 static int simplify_cast(struct instruction *insn)
1393 {
1394         unsigned long long mask;
1395         struct instruction *def;
1396         pseudo_t src;
1397         pseudo_t val;
1398         int osize;
1399         int size;
1400
1401         if (dead_insn(insn, &insn->src, NULL, NULL))
1402                 return REPEAT_CSE;
1403
1404         src = insn->src;
1405
1406         /* A cast of a constant? */
1407         if (constant(src))
1408                 return simplify_constant_unop(insn);
1409
1410         // can merge with the previous instruction?
1411         size = insn->size;
1412         def = src->def;
1413         switch (def_opcode(src)) {
1414         case OP_AND:
1415                 val = def->src2;
1416                 if (val->type != PSEUDO_VAL)
1417                         break;
1418                 /* A cast of a AND might be a no-op.. */
1419                 switch (insn->opcode) {
1420                 case OP_TRUNC:
1421                         if (multi_users(src))
1422                                 break;
1423                         def->opcode = OP_TRUNC;
1424                         def->orig_type = def->type;
1425                         def->type = insn->type;
1426                         def->size = size;
1427
1428                         insn->opcode = OP_AND;
1429                         mask = val->value;
1430                         mask &= (1ULL << size) - 1;
1431                         insn->src2 = value_pseudo(mask);
1432                         return REPEAT_CSE;
1433
1434                 case OP_SEXT:
1435                         if (val->value & (1 << (def->size - 1)))
1436                                 break;
1437                         // OK, sign bit is 0
1438                 case OP_ZEXT:
1439                         if (multi_users(src))
1440                                 break;
1441                         // transform:
1442                         //      and.n   %b <- %a, M
1443                         //      *ext.m  %c <- (n) %b
1444                         // into:
1445                         //      zext.m  %b <- %a
1446                         //      and.m   %c <- %b, M
1447                         // For ZEXT, the mask will always be small
1448                         // enough. For SEXT, it can only be done if
1449                         // the mask force the sign bit to 0.
1450                         def->opcode = OP_ZEXT;
1451                         def->orig_type = insn->orig_type;
1452                         def->type = insn->type;
1453                         def->size = insn->size;
1454                         insn->opcode = OP_AND;
1455                         insn->src2 = val;
1456                         return REPEAT_CSE;
1457                 }
1458                 break;
1459         case OP_FPCMP ... OP_BINCMP_END:
1460                 switch (insn->opcode) {
1461                 case OP_SEXT:
1462                         if (insn->size == 1)
1463                                 break;
1464                         /* fall through */
1465                 case OP_ZEXT:
1466                 case OP_TRUNC:
1467                         // simplify:
1468                         //      setcc.n %t <- %a, %b
1469                         //      zext.m  %r <- (n) %t
1470                         // into:
1471                         //      setcc.m %r <- %a, %b
1472                         // and same for s/zext/trunc/
1473                         insn->opcode = def->opcode;
1474                         use_pseudo(insn, def->src2, &insn->src2);
1475                         return replace_pseudo(insn, &insn->src1, def->src1);
1476                 }
1477                 break;
1478         case OP_OR:
1479                 switch (insn->opcode) {
1480                 case OP_TRUNC:
1481                         mask = bits_mask(insn->size);
1482                         return simplify_mask_or(insn, mask, def);
1483                 }
1484                 break;
1485         case OP_LSR:
1486         case OP_SHL:
1487                 if (insn->opcode != OP_TRUNC)
1488                         break;
1489                 mask = bits_mask(insn->size);
1490                 return simplify_mask_shift(def, mask);
1491         case OP_TRUNC:
1492                 switch (insn->opcode) {
1493                 case OP_TRUNC:
1494                         insn->orig_type = def->orig_type;
1495                         return replace_pseudo(insn, &insn->src1, def->src);
1496                 case OP_ZEXT:
1497                         if (size != def->orig_type->bit_size)
1498                                 break;
1499                         insn->opcode = OP_AND;
1500                         insn->src2 = value_pseudo((1ULL << def->size) - 1);
1501                         return replace_pseudo(insn, &insn->src1, def->src);
1502                 }
1503                 break;
1504         case OP_ZEXT:
1505                 switch (insn->opcode) {
1506                 case OP_SEXT:
1507                         insn->opcode = OP_ZEXT;
1508                         /* fall through */
1509                 case OP_ZEXT:
1510                         insn->orig_type = def->orig_type;
1511                         return replace_pseudo(insn, &insn->src, def->src);
1512                 }
1513                 /* fall through */
1514         case OP_SEXT:
1515                 switch (insn->opcode) {
1516                 case OP_TRUNC:
1517                         osize = def->orig_type->bit_size;
1518                         if (size == osize)
1519                                 return replace_with_pseudo(insn, def->src);
1520                         if (size > osize)
1521                                 insn->opcode = def->opcode;
1522                         insn->orig_type = def->orig_type;
1523                         return replace_pseudo(insn, &insn->src, def->src);
1524                 }
1525                 switch (insn->opcode) {
1526                 case OP_SEXT:
1527                         insn->orig_type = def->orig_type;
1528                         return replace_pseudo(insn, &insn->src, def->src);
1529                 }
1530                 break;
1531         }
1532
1533         return 0;
1534 }
1535
1536 static int simplify_select(struct instruction *insn)
1537 {
1538         pseudo_t cond, src1, src2;
1539
1540         if (dead_insn(insn, &insn->src1, &insn->src2, &insn->src3))
1541                 return REPEAT_CSE;
1542
1543         cond = insn->src1;
1544         src1 = insn->src2;
1545         src2 = insn->src3;
1546         if (constant(cond) || src1 == src2) {
1547                 pseudo_t *kill, take;
1548                 kill_use(&insn->src1);
1549                 take = cond->value ? src1 : src2;
1550                 kill = cond->value ? &insn->src3 : &insn->src2;
1551                 kill_use(kill);
1552                 replace_with_pseudo(insn, take);
1553                 return REPEAT_CSE;
1554         }
1555         if (constant(src1) && constant(src2)) {
1556                 long long val1 = src1->value;
1557                 long long val2 = src2->value;
1558
1559                 /* The pair 0/1 is special - replace with SETNE/SETEQ */
1560                 if ((val1 | val2) == 1) {
1561                         int opcode = OP_SET_EQ;
1562                         if (val1) {
1563                                 src1 = src2;
1564                                 opcode = OP_SET_NE;
1565                         }
1566                         insn->opcode = opcode;
1567                         /* insn->src1 is already cond */
1568                         insn->src2 = src1; /* Zero */
1569                         return REPEAT_CSE;
1570                 }
1571         }
1572         if (cond == src2 && is_zero(src1)) {
1573                 kill_use(&insn->src1);
1574                 kill_use(&insn->src3);
1575                 replace_with_pseudo(insn, value_pseudo(0));
1576                 return REPEAT_CSE;
1577         }
1578         return 0;
1579 }
1580
1581 static int is_in_range(pseudo_t src, long long low, long long high)
1582 {
1583         long long value;
1584
1585         switch (src->type) {
1586         case PSEUDO_VAL:
1587                 value = src->value;
1588                 return value >= low && value <= high;
1589         default:
1590                 return 0;
1591         }
1592 }
1593
1594 static int simplify_range(struct instruction *insn)
1595 {
1596         pseudo_t src1, src2, src3;
1597
1598         src1 = insn->src1;
1599         src2 = insn->src2;
1600         src3 = insn->src3;
1601         if (src2->type != PSEUDO_VAL || src3->type != PSEUDO_VAL)
1602                 return 0;
1603         if (is_in_range(src1, src2->value, src3->value)) {
1604                 kill_instruction(insn);
1605                 return REPEAT_CSE;
1606         }
1607         return 0;
1608 }
1609
1610 ///
1611 // simplify SET_NE/EQ $0 + BR
1612 static int simplify_cond_branch(struct instruction *br, struct instruction *def, pseudo_t newcond)
1613 {
1614         replace_pseudo(br, &br->cond, newcond);
1615         if (def->opcode == OP_SET_EQ) {
1616                 struct basic_block *tmp = br->bb_true;
1617                 br->bb_true = br->bb_false;
1618                 br->bb_false = tmp;
1619         }
1620         return REPEAT_CSE;
1621 }
1622
1623 static int simplify_branch(struct instruction *insn)
1624 {
1625         pseudo_t cond = insn->cond;
1626
1627         /* Constant conditional */
1628         if (constant(cond)) {
1629                 insert_branch(insn->bb, insn, cond->value ? insn->bb_true : insn->bb_false);
1630                 return REPEAT_CSE;
1631         }
1632
1633         /* Same target? */
1634         if (insn->bb_true == insn->bb_false) {
1635                 struct basic_block *bb = insn->bb;
1636                 struct basic_block *target = insn->bb_false;
1637                 remove_bb_from_list(&target->parents, bb, 1);
1638                 remove_bb_from_list(&bb->children, target, 1);
1639                 insn->bb_false = NULL;
1640                 kill_use(&insn->cond);
1641                 insn->cond = NULL;
1642                 insn->opcode = OP_BR;
1643                 return REPEAT_CSE;
1644         }
1645
1646         /* Conditional on a SETNE $0 or SETEQ $0 */
1647         if (cond->type == PSEUDO_REG) {
1648                 struct instruction *def = cond->def;
1649
1650                 if (def->opcode == OP_SET_NE || def->opcode == OP_SET_EQ) {
1651                         if (constant(def->src1) && !def->src1->value)
1652                                 return simplify_cond_branch(insn, def, def->src2);
1653                         if (constant(def->src2) && !def->src2->value)
1654                                 return simplify_cond_branch(insn, def, def->src1);
1655                 }
1656                 if (def->opcode == OP_SEL) {
1657                         if (constant(def->src2) && constant(def->src3)) {
1658                                 long long val1 = def->src2->value;
1659                                 long long val2 = def->src3->value;
1660                                 if (!val1 && !val2) {
1661                                         insert_branch(insn->bb, insn, insn->bb_false);
1662                                         return REPEAT_CSE;
1663                                 }
1664                                 if (val1 && val2) {
1665                                         insert_branch(insn->bb, insn, insn->bb_true);
1666                                         return REPEAT_CSE;
1667                                 }
1668                                 if (val2) {
1669                                         struct basic_block *tmp = insn->bb_true;
1670                                         insn->bb_true = insn->bb_false;
1671                                         insn->bb_false = tmp;
1672                                 }
1673                                 return replace_pseudo(insn, &insn->cond, def->src1);
1674                         }
1675                 }
1676                 if (def->opcode == OP_SEXT || def->opcode == OP_ZEXT)
1677                         return replace_pseudo(insn, &insn->cond, def->src);
1678         }
1679         return 0;
1680 }
1681
1682 static int simplify_switch(struct instruction *insn)
1683 {
1684         pseudo_t cond = insn->cond;
1685         long long val;
1686         struct multijmp *jmp;
1687
1688         if (!constant(cond))
1689                 return 0;
1690         val = insn->cond->value;
1691
1692         FOR_EACH_PTR(insn->multijmp_list, jmp) {
1693                 /* Default case */
1694                 if (jmp->begin > jmp->end)
1695                         goto found;
1696                 if (val >= jmp->begin && val <= jmp->end)
1697                         goto found;
1698         } END_FOR_EACH_PTR(jmp);
1699         warning(insn->pos, "Impossible case statement");
1700         return 0;
1701
1702 found:
1703         insert_branch(insn->bb, insn, jmp->target);
1704         return REPEAT_CSE;
1705 }
1706
1707 int simplify_instruction(struct instruction *insn)
1708 {
1709         if (!insn->bb)
1710                 return 0;
1711         switch (insn->opcode) {
1712         case OP_ADD: case OP_MUL:
1713         case OP_AND: case OP_OR: case OP_XOR:
1714                 canonicalize_commutative(insn);
1715                 if (simplify_binop(insn))
1716                         return REPEAT_CSE;
1717                 return simplify_associative_binop(insn);
1718
1719         case OP_SET_EQ: case OP_SET_NE:
1720                 canonicalize_commutative(insn);
1721                 return simplify_binop(insn);
1722
1723         case OP_SET_LE: case OP_SET_GE:
1724         case OP_SET_LT: case OP_SET_GT:
1725         case OP_SET_B:  case OP_SET_A:
1726         case OP_SET_BE: case OP_SET_AE:
1727                 canonicalize_compare(insn);
1728                 /* fall through */
1729         case OP_SUB:
1730         case OP_DIVU: case OP_DIVS:
1731         case OP_MODU: case OP_MODS:
1732         case OP_SHL:
1733         case OP_LSR: case OP_ASR:
1734                 return simplify_binop(insn);
1735
1736         case OP_NOT: case OP_NEG: case OP_FNEG:
1737                 return simplify_unop(insn);
1738         case OP_LOAD:
1739                 if (!has_users(insn->target))
1740                         return kill_instruction(insn);
1741                 /* fall-through */
1742         case OP_STORE:
1743                 return simplify_memop(insn);
1744         case OP_SYMADDR:
1745                 if (dead_insn(insn, &insn->src, NULL, NULL))
1746                         return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
1747                 return replace_with_pseudo(insn, insn->src);
1748         case OP_SEXT: case OP_ZEXT:
1749         case OP_TRUNC:
1750                 return simplify_cast(insn);
1751         case OP_FCVTU: case OP_FCVTS:
1752         case OP_UCVTF: case OP_SCVTF:
1753         case OP_FCVTF:
1754         case OP_PTRCAST:
1755                 if (dead_insn(insn, &insn->src, NULL, NULL))
1756                         return REPEAT_CSE;
1757                 break;
1758         case OP_UTPTR:
1759         case OP_PTRTU:
1760                 return replace_with_pseudo(insn, insn->src);
1761         case OP_SLICE:
1762                 if (dead_insn(insn, &insn->src, NULL, NULL))
1763                         return REPEAT_CSE;
1764                 break;
1765         case OP_SETVAL:
1766         case OP_SETFVAL:
1767                 if (dead_insn(insn, NULL, NULL, NULL))
1768                         return REPEAT_CSE;
1769                 break;
1770         case OP_PHI:
1771                 if (dead_insn(insn, NULL, NULL, NULL)) {
1772                         kill_use_list(insn->phi_list);
1773                         return REPEAT_CSE;
1774                 }
1775                 return clean_up_phi(insn);
1776         case OP_PHISOURCE:
1777                 if (dead_insn(insn, &insn->phi_src, NULL, NULL))
1778                         return REPEAT_CSE;
1779                 break;
1780         case OP_SEL:
1781                 return simplify_select(insn);
1782         case OP_CBR:
1783                 return simplify_branch(insn);
1784         case OP_SWITCH:
1785                 return simplify_switch(insn);
1786         case OP_RANGE:
1787                 return simplify_range(insn);
1788         case OP_FADD:
1789         case OP_FSUB:
1790         case OP_FMUL:
1791         case OP_FDIV:
1792                 if (dead_insn(insn, &insn->src1, &insn->src2, NULL))
1793                         return REPEAT_CSE;
1794                 break;
1795         }
1796         return 0;
1797 }