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 (uval < size)
 758                 return uval;
 759
 760         sval = sign_extend_safe(sval, size);
 761         sval = sign_extend_safe(sval, bits_in_int);
 762         if (sval < 0)
 763                 insn->src2 = value_pseudo(sval);
 764         if (insn->tainted)
 765                 return sval;
 766
 767         if (sval < 0 && Wshift_count_negative)
 768                 warning(insn->pos, "shift count is negative (%lld)", sval);
 769         if (sval > 0 && Wshift_count_overflow) {
 770                 struct symbol *ctype = insn->type;
 771                 const char *tname;
 772                 if (ctype->type == SYM_NODE)
 773                         ctype = ctype->ctype.base_type;
 774                 tname = show_typename(ctype);
 775                 warning(insn->pos, "shift too big (%llu) for type %s", sval, tname);
 776         }
 777         insn->tainted = 1;
 778         return sval;
 779 }
 780
 781 static int simplify_shift(struct instruction *insn, pseudo_t pseudo, long long value)
 782 {
 783         struct instruction *def;
 784         unsigned long long mask, omask, nmask;
 785         unsigned long long nval;
 786         unsigned int size;
 787         pseudo_t src2;
 788
 789         if (!value)
 790                 return replace_with_pseudo(insn, pseudo);
 791         value = check_shift_count(insn, value);
 792         if (value < 0)
 793                 return 0;
 794
 795         size = insn->size;
 796         switch (insn->opcode) {
 797         case OP_ASR:
 798                 if (value >= size)
 799                         return 0;
 800                 if (pseudo->type != PSEUDO_REG)
 801                         break;
 802                 def = pseudo->def;
 803                 switch (def->opcode) {
 804                 case OP_LSR:
 805                 case OP_ASR:
 806                         if (def == insn)        // cyclic DAG!
 807                                 break;
 808                         src2 = def->src2;
 809                         if (src2->type != PSEUDO_VAL)
 810                                 break;
 811                         nval = src2->value;
 812                         if (nval > insn->size || nval == 0)
 813                                 break;
 814                         value += nval;
 815                         if (def->opcode == OP_LSR)
 816                                 insn->opcode = OP_LSR;
 817                         else if (value >= size)
 818                                 value = size - 1;
 819                         goto new_value;
 820
 821                 case OP_ZEXT:
 822                         // transform:
 823                         //      zext.N  %t <- (O) %a
 824                         //      asr.N   %r <- %t, C
 825                         // into
 826                         //      zext.N  %t <- (O) %a
 827                         //      lsr.N   %r <- %t, C
 828                         insn->opcode = OP_LSR;
 829                         return REPEAT_CSE;
 830                 }
 831                 break;
 832         case OP_LSR:
 833                 size = operand_size(insn, pseudo);
 834                 if (value >= size)
 835                         goto zero;
 836                 switch(DEF_OPCODE(def, pseudo)) {
 837                 case OP_AND:
 838                         // replace (A & M) >> S
 839                         // by      (A >> S) & (M >> S)
 840                         if (!constant(def->src2))
 841                                 break;
 842                         mask = bits_mask(insn->size - value) << value;
 843                         omask = def->src2->value;
 844                         nmask = omask & mask;
 845                         if (nmask == 0)
 846                                 return replace_with_pseudo(insn, value_pseudo(0));
 847                         if (nmask == mask)
 848                                 return replace_pseudo(insn, &insn->src1, def->src1);
 849                         if (nbr_users(pseudo) > 1)
 850                                 break;
 851                         def->opcode = OP_LSR;
 852                         def->src2 = insn->src2;
 853                         insn->opcode = OP_AND;
 854                         insn->src2 = value_pseudo(omask >> value);
 855                         return REPEAT_CSE;
 856                 case OP_LSR:
 857                         goto case_shift_shift;
 858                 case OP_OR:
 859                         mask = bits_mask(size);
 860                         return simplify_mask_shift_or(insn, def, mask);
 861                 case OP_SHL:
 862                         // replace ((x << S) >> S)
 863                         // by      (x & (-1 >> S))
 864                         if (def->src2 != insn->src2)
 865                                 break;
 866                         mask = bits_mask(insn->size - value);
 867                         goto replace_mask;
 868                 }
 869                 break;
 870         case OP_SHL:
 871                 if (value >= size)
 872                         goto zero;
 873                 switch(DEF_OPCODE(def, pseudo)) {
 874                 case OP_AND:
 875                         // simplify (A & M) << S
 876                         if (!constant(def->src2))
 877                                 break;
 878                         mask = bits_mask(insn->size) >> value;
 879                         omask = def->src2->value;
 880                         nmask = omask & mask;
 881                         if (nmask == 0)
 882                                 return replace_with_pseudo(insn, value_pseudo(0));
 883                         if (nmask == mask)
 884                                 return replace_pseudo(insn, &insn->src1, def->src1);
 885                         // do not simplify into ((A << S) & (M << S))
 886                         break;
 887                 case OP_LSR:
 888                         // replace ((x >> S) << S)
 889                         // by      (x & (-1 << S))
 890                         if (def->src2 != insn->src2)
 891                                 break;
 892                         mask = bits_mask(insn->size - value) << value;
 893                         goto replace_mask;
 894                 case OP_OR:
 895                         mask = bits_mask(size);
 896                         return simplify_mask_shift_or(insn, def, mask);
 897                 case OP_SHL:
 898                 case_shift_shift:               // also for LSR - LSR
 899                         if (def == insn)        // cyclic DAG!
 900                                 break;
 901                         src2 = def->src2;
 902                         if (src2->type != PSEUDO_VAL)
 903                                 break;
 904                         nval = src2->value;
 905                         if (nval > insn->size)
 906                                 break;
 907                         value += nval;
 908                         goto new_value;
 909                 }
 910                 break;
 911         }
 912         return 0;
 913
 914 new_value:
 915         if (value < size) {
 916                 insn->src2 = value_pseudo(value);
 917                 return replace_pseudo(insn, &insn->src1, pseudo->def->src1);
 918         }
 919 zero:
 920         return replace_with_pseudo(insn, value_pseudo(0));
 921 replace_mask:
 922         insn->opcode = OP_AND;
 923         insn->src2 = value_pseudo(mask);
 924         return replace_pseudo(insn, &insn->src1, def->src1);
 925 }
 926
 927 static int simplify_mul_div(struct instruction *insn, long long value)
 928 {
 929         unsigned long long sbit = 1ULL << (insn->size - 1);
 930         unsigned long long bits = sbit | (sbit - 1);
 931
 932         if (value == 1)
 933                 return replace_with_pseudo(insn, insn->src1);
 934
 935         switch (insn->opcode) {
 936         case OP_MUL:
 937                 if (value == 0)
 938                         return replace_with_pseudo(insn, insn->src2);
 939         /* Fall through */
 940         case OP_DIVS:
 941                 if (!(value & sbit))    // positive
 942                         break;
 943
 944                 value |= ~bits;
 945                 if (value == -1) {
 946                         insn->opcode = OP_NEG;
 947                         return REPEAT_CSE;
 948                 }
 949         }
 950
 951         return 0;
 952 }
 953
 954 static int simplify_seteq_setne(struct instruction *insn, long long value)
 955 {
 956         pseudo_t old = insn->src1;
 957         struct instruction *def;
 958         unsigned osize;
 959         int inverse;
 960         int opcode;
 961
 962         if (value != 0 && value != 1)
 963                 return 0;
 964
 965         if (old->type != PSEUDO_REG)
 966                 return 0;
 967         def = old->def;
 968         if (!def)
 969                 return 0;
 970
 971         inverse = (insn->opcode == OP_SET_NE) == value;
 972         if (!inverse && def->size == 1 && insn->size == 1) {
 973                 // Replace:
 974                 //      setne   %r <- %s, $0
 975                 // or:
 976                 //      seteq   %r <- %s, $1
 977                 // by %s when boolean
 978                 return replace_with_pseudo(insn, old);
 979         }
 980         opcode = def->opcode;
 981         switch (opcode) {
 982         case OP_AND:
 983                 if (inverse)
 984                         break;
 985                 if (def->size != insn->size)
 986                         break;
 987                 if (def->src2->type != PSEUDO_VAL)
 988                         break;
 989                 if (def->src2->value != 1)
 990                         break;
 991                 return replace_with_pseudo(insn, old);
 992         case OP_FPCMP ... OP_BINCMP_END:
 993                 // Convert:
 994                 //      setcc.n %t <- %a, %b
 995                 //      setne.m %r <- %t, $0
 996                 // into:
 997                 //      setcc.n %t <- %a, %b
 998                 //      setcc.m %r <- %a, $b
 999                 // and similar for setne/eq ... 0/1
1000                 insn->opcode = inverse ? opcode_table[opcode].negate : opcode;
1001                 use_pseudo(insn, def->src1, &insn->src1);
1002                 use_pseudo(insn, def->src2, &insn->src2);
1003                 remove_usage(old, &insn->src1);
1004                 return REPEAT_CSE;
1005
1006         case OP_SEXT:
1007                 if (value && (def->orig_type->bit_size == 1))
1008                         break;
1009                 /* Fall through */
1010         case OP_ZEXT:
1011                 // Convert:
1012                 //      *ext.m  %s <- (1) %a
1013                 //      setne.1 %r <- %s, $0
1014                 // into:
1015                 //      setne.1 %s <- %a, $0
1016                 // and same for setne/eq ... 0/1
1017                 return replace_pseudo(insn, &insn->src1, def->src);
1018         case OP_TRUNC:
1019                 if (multi_users(old))
1020                         break;
1021                 // convert
1022                 //      trunc.n %s <- (o) %a
1023                 //      setne.m %r <- %s, $0
1024                 // into:
1025                 //      and.o   %s <- %a, $((1 << o) - 1)
1026                 //      setne.m %r <- %s, $0
1027                 // and same for setne/eq ... 0/1
1028                 osize = def->size;
1029                 def->opcode = OP_AND;
1030                 def->type = def->orig_type;
1031                 def->size = def->type->bit_size;
1032                 def->src2 = value_pseudo(bits_mask(osize));
1033                 return REPEAT_CSE;
1034         }
1035         return 0;
1036 }
1037
1038 static int simplify_constant_mask(struct instruction *insn, unsigned long long mask)
1039 {
1040         pseudo_t old = insn->src1;
1041         unsigned long long omask;
1042         unsigned long long nmask;
1043         struct instruction *def;
1044         int osize;
1045
1046         switch (DEF_OPCODE(def, old)) {
1047         case OP_FPCMP ... OP_BINCMP_END:
1048                 osize = 1;
1049                 goto oldsize;
1050         case OP_OR:
1051                 return simplify_mask_or(insn, mask, def);
1052         case OP_LSR:
1053         case OP_SHL:
1054                 return simplify_mask_shift(def, mask);
1055         case OP_ZEXT:
1056                 osize = def->orig_type->bit_size;
1057                 /* fall through */
1058         oldsize:
1059                 omask = (1ULL << osize) - 1;
1060                 nmask = mask & omask;
1061                 if (nmask == omask)
1062                         // the AND mask is redundant
1063                         return replace_with_pseudo(insn, old);
1064                 if (nmask != mask) {
1065                         // can use a smaller mask
1066                         insn->src2 = value_pseudo(nmask);
1067                         return REPEAT_CSE;
1068                 }
1069                 break;
1070         }
1071         return 0;
1072 }
1073
1074 static int simplify_constant_rightside(struct instruction *insn)
1075 {
1076         long long value = insn->src2->value;
1077         long long sbit = 1ULL << (insn->size - 1);
1078         long long bits = sbit | (sbit - 1);
1079
1080         switch (insn->opcode) {
1081         case OP_OR:
1082                 if ((value & bits) == bits)
1083                         return replace_with_pseudo(insn, insn->src2);
1084                 goto case_neutral_zero;
1085
1086         case OP_XOR:
1087                 if ((value & bits) == bits) {
1088                         insn->opcode = OP_NOT;
1089                         return REPEAT_CSE;
1090                 }
1091                 goto case_neutral_zero;
1092
1093         case OP_SUB:
1094                 if (value) {
1095                         insn->opcode = OP_ADD;
1096                         insn->src2 = value_pseudo(-value);
1097                         return REPEAT_CSE;
1098                 }
1099         /* Fall through */
1100         case OP_ADD:
1101         case_neutral_zero:
1102                 if (!value)
1103                         return replace_with_pseudo(insn, insn->src1);
1104                 return 0;
1105         case OP_ASR:
1106         case OP_SHL:
1107         case OP_LSR:
1108                 return simplify_shift(insn, insn->src1, value);
1109
1110         case OP_MODU: case OP_MODS:
1111                 if (value == 1)
1112                         return replace_with_pseudo(insn, value_pseudo(0));
1113                 return 0;
1114
1115         case OP_DIVU: case OP_DIVS:
1116         case OP_MUL:
1117                 return simplify_mul_div(insn, value);
1118
1119         case OP_AND:
1120                 if (!value)
1121                         return replace_with_pseudo(insn, insn->src2);
1122                 if ((value & bits) == bits)
1123                         return replace_with_pseudo(insn, insn->src1);
1124                 return simplify_constant_mask(insn, value);
1125
1126         case OP_SET_NE:
1127         case OP_SET_EQ:
1128                 return simplify_seteq_setne(insn, value);
1129         }
1130         return 0;
1131 }
1132
1133 static int simplify_constant_leftside(struct instruction *insn)
1134 {
1135         long long value = insn->src1->value;
1136
1137         switch (insn->opcode) {
1138         case OP_ADD: case OP_OR: case OP_XOR:
1139                 if (!value)
1140                         return replace_with_pseudo(insn, insn->src2);
1141                 return 0;
1142
1143         case OP_SHL:
1144         case OP_LSR: case OP_ASR:
1145         case OP_AND:
1146         case OP_MUL:
1147                 if (!value)
1148                         return replace_with_pseudo(insn, insn->src1);
1149                 return 0;
1150         }
1151         return 0;
1152 }
1153
1154 static int simplify_constant_binop(struct instruction *insn)
1155 {
1156         pseudo_t res = eval_insn(insn);
1157
1158         if (!res)
1159                 return 0;
1160
1161         replace_with_pseudo(insn, res);
1162         return REPEAT_CSE;
1163 }
1164
1165 static int simplify_binop_same_args(struct instruction *insn, pseudo_t arg)
1166 {
1167         switch (insn->opcode) {
1168         case OP_SET_NE:
1169         case OP_SET_LT: case OP_SET_GT:
1170         case OP_SET_B:  case OP_SET_A:
1171                 if (Wtautological_compare)
1172                         warning(insn->pos, "self-comparison always evaluates to false");
1173         case OP_SUB:
1174         case OP_XOR:
1175                 return replace_with_pseudo(insn, value_pseudo(0));
1176
1177         case OP_SET_EQ:
1178         case OP_SET_LE: case OP_SET_GE:
1179         case OP_SET_BE: case OP_SET_AE:
1180                 if (Wtautological_compare)
1181                         warning(insn->pos, "self-comparison always evaluates to true");
1182                 return replace_with_pseudo(insn, value_pseudo(1));
1183
1184         case OP_AND:
1185         case OP_OR:
1186                 return replace_with_pseudo(insn, arg);
1187
1188         default:
1189                 break;
1190         }
1191
1192         return 0;
1193 }
1194
1195 static int simplify_binop(struct instruction *insn)
1196 {
1197         if (dead_insn(insn, &insn->src1, &insn->src2, NULL))
1198                 return REPEAT_CSE;
1199         if (constant(insn->src1)) {
1200                 if (constant(insn->src2))
1201                         return simplify_constant_binop(insn);
1202                 return simplify_constant_leftside(insn);
1203         }
1204         if (constant(insn->src2))
1205                 return simplify_constant_rightside(insn);
1206         if (insn->src1 == insn->src2)
1207                 return simplify_binop_same_args(insn, insn->src1);
1208         return 0;
1209 }
1210
1211 static void switch_pseudo(struct instruction *insn1, pseudo_t *pp1, struct instruction *insn2, pseudo_t *pp2)
1212 {
1213         pseudo_t p1 = *pp1, p2 = *pp2;
1214
1215         use_pseudo(insn1, p2, pp1);
1216         use_pseudo(insn2, p1, pp2);
1217         remove_usage(p1, pp1);
1218         remove_usage(p2, pp2);
1219 }
1220
1221 static int canonical_order(pseudo_t p1, pseudo_t p2)
1222 {
1223         /* symbol/constants on the right */
1224         if (p1->type == PSEUDO_VAL)
1225                 return p2->type == PSEUDO_VAL;
1226
1227         if (p1->type == PSEUDO_SYM)
1228                 return p2->type == PSEUDO_SYM || p2->type == PSEUDO_VAL;
1229
1230         return 1;
1231 }
1232
1233 static int canonicalize_commutative(struct instruction *insn)
1234 {
1235         if (canonical_order(insn->src1, insn->src2))
1236                 return 0;
1237
1238         switch_pseudo(insn, &insn->src1, insn, &insn->src2);
1239         return repeat_phase |= REPEAT_CSE;
1240 }
1241
1242 static int canonicalize_compare(struct instruction *insn)
1243 {
1244         if (canonical_order(insn->src1, insn->src2))
1245                 return 0;
1246
1247         switch_pseudo(insn, &insn->src1, insn, &insn->src2);
1248         insn->opcode = opcode_table[insn->opcode].swap;
1249         return repeat_phase |= REPEAT_CSE;
1250 }
1251
1252 static inline int simple_pseudo(pseudo_t pseudo)
1253 {
1254         return pseudo->type == PSEUDO_VAL || pseudo->type == PSEUDO_SYM;
1255 }
1256
1257 static int simplify_associative_binop(struct instruction *insn)
1258 {
1259         struct instruction *def;
1260         pseudo_t pseudo = insn->src1;
1261
1262         if (!simple_pseudo(insn->src2))
1263                 return 0;
1264         if (pseudo->type != PSEUDO_REG)
1265                 return 0;
1266         def = pseudo->def;
1267         if (def == insn)
1268                 return 0;
1269         if (def->opcode != insn->opcode)
1270                 return 0;
1271         if (!simple_pseudo(def->src2))
1272                 return 0;
1273         if (multi_users(def->target))
1274                 return 0;
1275         switch_pseudo(def, &def->src1, insn, &insn->src2);
1276         return REPEAT_CSE;
1277 }
1278
1279 static int simplify_constant_unop(struct instruction *insn)
1280 {
1281         long long val = insn->src1->value;
1282         long long res, mask;
1283
1284         switch (insn->opcode) {
1285         case OP_NOT:
1286                 res = ~val;
1287                 break;
1288         case OP_NEG:
1289                 res = -val;
1290                 break;
1291         case OP_SEXT:
1292                 mask = 1ULL << (insn->orig_type->bit_size-1);
1293                 if (val & mask)
1294                         val |= ~(mask | (mask-1));
1295                 /* fall through */
1296         case OP_ZEXT:
1297         case OP_TRUNC:
1298                 res = val;
1299                 break;
1300         default:
1301                 return 0;
1302         }
1303         mask = 1ULL << (insn->size-1);
1304         res &= mask | (mask-1);
1305
1306         replace_with_pseudo(insn, value_pseudo(res));
1307         return REPEAT_CSE;
1308 }
1309
1310 static int simplify_unop(struct instruction *insn)
1311 {
1312         if (dead_insn(insn, &insn->src1, NULL, NULL))
1313                 return REPEAT_CSE;
1314         if (constant(insn->src1))
1315                 return simplify_constant_unop(insn);
1316
1317         switch (insn->opcode) {
1318                 struct instruction *def;
1319
1320         case OP_NOT:
1321                 def = insn->src->def;
1322                 if (def && def->opcode == OP_NOT)
1323                         return replace_with_pseudo(insn, def->src);
1324                 break;
1325         case OP_NEG:
1326                 def = insn->src->def;
1327                 if (def && def->opcode == OP_NEG)
1328                         return replace_with_pseudo(insn, def->src);
1329                 break;
1330         default:
1331                 return 0;
1332         }
1333         return 0;
1334 }
1335
1336 static int simplify_one_memop(struct instruction *insn, pseudo_t orig)
1337 {
1338         pseudo_t addr = insn->src;
1339         pseudo_t new, off;
1340
1341         if (addr->type == PSEUDO_REG) {
1342                 struct instruction *def = addr->def;
1343                 if (def->opcode == OP_SYMADDR && def->src) {
1344                         kill_use(&insn->src);
1345                         use_pseudo(insn, def->src, &insn->src);
1346                         return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
1347                 }
1348                 if (def->opcode == OP_ADD) {
1349                         new = def->src1;
1350                         off = def->src2;
1351                         if (constant(off))
1352                                 goto offset;
1353                         new = off;
1354                         off = def->src1;
1355                         if (constant(off))
1356                                 goto offset;
1357                         return 0;
1358                 }
1359         }
1360         return 0;
1361
1362 offset:
1363         /* Invalid code */
1364         if (new == orig || new == addr) {
1365                 if (new == VOID)
1366                         return 0;
1367                 /*
1368                  * If some BB have been removed it is possible that this
1369                  * memop is in fact part of a dead BB. In this case
1370                  * we must not warn since nothing is wrong.
1371                  * If not part of a dead BB this will be redone after
1372                  * the BBs have been cleaned up.
1373                  */
1374                 if (repeat_phase & REPEAT_CFG_CLEANUP)
1375                         return 0;
1376                 warning(insn->pos, "crazy programmer");
1377                 replace_pseudo(insn, &insn->src, VOID);
1378                 return 0;
1379         }
1380         insn->offset += off->value;
1381         replace_pseudo(insn, &insn->src, new);
1382         return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
1383 }
1384
1385 ///
1386 // simplify memops instructions
1387 //
1388 // :note: We walk the whole chain of adds/subs backwards.
1389 //      That's not only more efficient, but it allows us to find loops.
1390 static int simplify_memop(struct instruction *insn)
1391 {
1392         int one, ret = 0;
1393         pseudo_t orig = insn->src;
1394
1395         do {
1396                 one = simplify_one_memop(insn, orig);
1397                 ret |= one;
1398         } while (one);
1399         return ret;
1400 }
1401
1402 static int simplify_cast(struct instruction *insn)
1403 {
1404         unsigned long long mask;
1405         struct instruction *def;
1406         pseudo_t src;
1407         pseudo_t val;
1408         int osize;
1409         int size;
1410
1411         if (dead_insn(insn, &insn->src, NULL, NULL))
1412                 return REPEAT_CSE;
1413
1414         src = insn->src;
1415
1416         /* A cast of a constant? */
1417         if (constant(src))
1418                 return simplify_constant_unop(insn);
1419
1420         // can merge with the previous instruction?
1421         size = insn->size;
1422         def = src->def;
1423         switch (def_opcode(src)) {
1424         case OP_AND:
1425                 val = def->src2;
1426                 if (val->type != PSEUDO_VAL)
1427                         break;
1428                 /* A cast of a AND might be a no-op.. */
1429                 switch (insn->opcode) {
1430                 case OP_TRUNC:
1431                         if (multi_users(src))
1432                                 break;
1433                         def->opcode = OP_TRUNC;
1434                         def->orig_type = def->type;
1435                         def->type = insn->type;
1436                         def->size = size;
1437
1438                         insn->opcode = OP_AND;
1439                         mask = val->value;
1440                         mask &= (1ULL << size) - 1;
1441                         insn->src2 = value_pseudo(mask);
1442                         return REPEAT_CSE;
1443
1444                 case OP_SEXT:
1445                         if (val->value & (1 << (def->size - 1)))
1446                                 break;
1447                         // OK, sign bit is 0
1448                 case OP_ZEXT:
1449                         if (multi_users(src))
1450                                 break;
1451                         // transform:
1452                         //      and.n   %b <- %a, M
1453                         //      *ext.m  %c <- (n) %b
1454                         // into:
1455                         //      zext.m  %b <- %a
1456                         //      and.m   %c <- %b, M
1457                         // For ZEXT, the mask will always be small
1458                         // enough. For SEXT, it can only be done if
1459                         // the mask force the sign bit to 0.
1460                         def->opcode = OP_ZEXT;
1461                         def->orig_type = insn->orig_type;
1462                         def->type = insn->type;
1463                         def->size = insn->size;
1464                         insn->opcode = OP_AND;
1465                         insn->src2 = val;
1466                         return REPEAT_CSE;
1467                 }
1468                 break;
1469         case OP_FPCMP ... OP_BINCMP_END:
1470                 switch (insn->opcode) {
1471                 case OP_SEXT:
1472                         if (insn->size == 1)
1473                                 break;
1474                         /* fall through */
1475                 case OP_ZEXT:
1476                 case OP_TRUNC:
1477                         // simplify:
1478                         //      setcc.n %t <- %a, %b
1479                         //      zext.m  %r <- (n) %t
1480                         // into:
1481                         //      setcc.m %r <- %a, %b
1482                         // and same for s/zext/trunc/
1483                         insn->opcode = def->opcode;
1484                         use_pseudo(insn, def->src2, &insn->src2);
1485                         return replace_pseudo(insn, &insn->src1, def->src1);
1486                 }
1487                 break;
1488         case OP_OR:
1489                 switch (insn->opcode) {
1490                 case OP_TRUNC:
1491                         mask = bits_mask(insn->size);
1492                         return simplify_mask_or(insn, mask, def);
1493                 }
1494                 break;
1495         case OP_LSR:
1496         case OP_SHL:
1497                 if (insn->opcode != OP_TRUNC)
1498                         break;
1499                 mask = bits_mask(insn->size);
1500                 return simplify_mask_shift(def, mask);
1501         case OP_TRUNC:
1502                 switch (insn->opcode) {
1503                 case OP_TRUNC:
1504                         insn->orig_type = def->orig_type;
1505                         return replace_pseudo(insn, &insn->src1, def->src);
1506                 case OP_ZEXT:
1507                         if (size != def->orig_type->bit_size)
1508                                 break;
1509                         insn->opcode = OP_AND;
1510                         insn->src2 = value_pseudo((1ULL << def->size) - 1);
1511                         return replace_pseudo(insn, &insn->src1, def->src);
1512                 }
1513                 break;
1514         case OP_ZEXT:
1515                 switch (insn->opcode) {
1516                 case OP_SEXT:
1517                         insn->opcode = OP_ZEXT;
1518                         /* fall through */
1519                 case OP_ZEXT:
1520                         insn->orig_type = def->orig_type;
1521                         return replace_pseudo(insn, &insn->src, def->src);
1522                 }
1523                 /* fall through */
1524         case OP_SEXT:
1525                 switch (insn->opcode) {
1526                 case OP_TRUNC:
1527                         osize = def->orig_type->bit_size;
1528                         if (size == osize)
1529                                 return replace_with_pseudo(insn, def->src);
1530                         if (size > osize)
1531                                 insn->opcode = def->opcode;
1532                         insn->orig_type = def->orig_type;
1533                         return replace_pseudo(insn, &insn->src, def->src);
1534                 }
1535                 switch (insn->opcode) {
1536                 case OP_SEXT:
1537                         insn->orig_type = def->orig_type;
1538                         return replace_pseudo(insn, &insn->src, def->src);
1539                 }
1540                 break;
1541         }
1542
1543         return 0;
1544 }
1545
1546 static int simplify_select(struct instruction *insn)
1547 {
1548         pseudo_t cond, src1, src2;
1549
1550         if (dead_insn(insn, &insn->src1, &insn->src2, &insn->src3))
1551                 return REPEAT_CSE;
1552
1553         cond = insn->src1;
1554         src1 = insn->src2;
1555         src2 = insn->src3;
1556         if (constant(cond) || src1 == src2) {
1557                 pseudo_t *kill, take;
1558                 kill_use(&insn->src1);
1559                 take = cond->value ? src1 : src2;
1560                 kill = cond->value ? &insn->src3 : &insn->src2;
1561                 kill_use(kill);
1562                 replace_with_pseudo(insn, take);
1563                 return REPEAT_CSE;
1564         }
1565         if (constant(src1) && constant(src2)) {
1566                 long long val1 = src1->value;
1567                 long long val2 = src2->value;
1568
1569                 /* The pair 0/1 is special - replace with SETNE/SETEQ */
1570                 if ((val1 | val2) == 1) {
1571                         int opcode = OP_SET_EQ;
1572                         if (val1) {
1573                                 src1 = src2;
1574                                 opcode = OP_SET_NE;
1575                         }
1576                         insn->opcode = opcode;
1577                         /* insn->src1 is already cond */
1578                         insn->src2 = src1; /* Zero */
1579                         return REPEAT_CSE;
1580                 }
1581         }
1582         if (cond == src2 && is_zero(src1)) {
1583                 kill_use(&insn->src1);
1584                 kill_use(&insn->src3);
1585                 replace_with_pseudo(insn, value_pseudo(0));
1586                 return REPEAT_CSE;
1587         }
1588         return 0;
1589 }
1590
1591 static int is_in_range(pseudo_t src, long long low, long long high)
1592 {
1593         long long value;
1594
1595         switch (src->type) {
1596         case PSEUDO_VAL:
1597                 value = src->value;
1598                 return value >= low && value <= high;
1599         default:
1600                 return 0;
1601         }
1602 }
1603
1604 static int simplify_range(struct instruction *insn)
1605 {
1606         pseudo_t src1, src2, src3;
1607
1608         src1 = insn->src1;
1609         src2 = insn->src2;
1610         src3 = insn->src3;
1611         if (src2->type != PSEUDO_VAL || src3->type != PSEUDO_VAL)
1612                 return 0;
1613         if (is_in_range(src1, src2->value, src3->value)) {
1614                 kill_instruction(insn);
1615                 return REPEAT_CSE;
1616         }
1617         return 0;
1618 }
1619
1620 ///
1621 // simplify SET_NE/EQ $0 + BR
1622 static int simplify_cond_branch(struct instruction *br, struct instruction *def, pseudo_t newcond)
1623 {
1624         replace_pseudo(br, &br->cond, newcond);
1625         if (def->opcode == OP_SET_EQ) {
1626                 struct basic_block *tmp = br->bb_true;
1627                 br->bb_true = br->bb_false;
1628                 br->bb_false = tmp;
1629         }
1630         return REPEAT_CSE;
1631 }
1632
1633 static int simplify_branch(struct instruction *insn)
1634 {
1635         pseudo_t cond = insn->cond;
1636
1637         /* Constant conditional */
1638         if (constant(cond)) {
1639                 insert_branch(insn->bb, insn, cond->value ? insn->bb_true : insn->bb_false);
1640                 return REPEAT_CSE;
1641         }
1642
1643         /* Same target? */
1644         if (insn->bb_true == insn->bb_false) {
1645                 struct basic_block *bb = insn->bb;
1646                 struct basic_block *target = insn->bb_false;
1647                 remove_bb_from_list(&target->parents, bb, 1);
1648                 remove_bb_from_list(&bb->children, target, 1);
1649                 insn->bb_false = NULL;
1650                 kill_use(&insn->cond);
1651                 insn->cond = NULL;
1652                 insn->opcode = OP_BR;
1653                 return REPEAT_CSE;
1654         }
1655
1656         /* Conditional on a SETNE $0 or SETEQ $0 */
1657         if (cond->type == PSEUDO_REG) {
1658                 struct instruction *def = cond->def;
1659
1660                 if (def->opcode == OP_SET_NE || def->opcode == OP_SET_EQ) {
1661                         if (constant(def->src1) && !def->src1->value)
1662                                 return simplify_cond_branch(insn, def, def->src2);
1663                         if (constant(def->src2) && !def->src2->value)
1664                                 return simplify_cond_branch(insn, def, def->src1);
1665                 }
1666                 if (def->opcode == OP_SEL) {
1667                         if (constant(def->src2) && constant(def->src3)) {
1668                                 long long val1 = def->src2->value;
1669                                 long long val2 = def->src3->value;
1670                                 if (!val1 && !val2) {
1671                                         insert_branch(insn->bb, insn, insn->bb_false);
1672                                         return REPEAT_CSE;
1673                                 }
1674                                 if (val1 && val2) {
1675                                         insert_branch(insn->bb, insn, insn->bb_true);
1676                                         return REPEAT_CSE;
1677                                 }
1678                                 if (val2) {
1679                                         struct basic_block *tmp = insn->bb_true;
1680                                         insn->bb_true = insn->bb_false;
1681                                         insn->bb_false = tmp;
1682                                 }
1683                                 return replace_pseudo(insn, &insn->cond, def->src1);
1684                         }
1685                 }
1686                 if (def->opcode == OP_SEXT || def->opcode == OP_ZEXT)
1687                         return replace_pseudo(insn, &insn->cond, def->src);
1688         }
1689         return 0;
1690 }
1691
1692 static int simplify_switch(struct instruction *insn)
1693 {
1694         pseudo_t cond = insn->cond;
1695         long long val;
1696         struct multijmp *jmp;
1697
1698         if (!constant(cond))
1699                 return 0;
1700         val = insn->cond->value;
1701
1702         FOR_EACH_PTR(insn->multijmp_list, jmp) {
1703                 /* Default case */
1704                 if (jmp->begin > jmp->end)
1705                         goto found;
1706                 if (val >= jmp->begin && val <= jmp->end)
1707                         goto found;
1708         } END_FOR_EACH_PTR(jmp);
1709         warning(insn->pos, "Impossible case statement");
1710         return 0;
1711
1712 found:
1713         insert_branch(insn->bb, insn, jmp->target);
1714         return REPEAT_CSE;
1715 }
1716
1717 int simplify_instruction(struct instruction *insn)
1718 {
1719         if (!insn->bb)
1720                 return 0;
1721         switch (insn->opcode) {
1722         case OP_ADD: case OP_MUL:
1723         case OP_AND: case OP_OR: case OP_XOR:
1724                 canonicalize_commutative(insn);
1725                 if (simplify_binop(insn))
1726                         return REPEAT_CSE;
1727                 return simplify_associative_binop(insn);
1728
1729         case OP_SET_EQ: case OP_SET_NE:
1730                 canonicalize_commutative(insn);
1731                 return simplify_binop(insn);
1732
1733         case OP_SET_LE: case OP_SET_GE:
1734         case OP_SET_LT: case OP_SET_GT:
1735         case OP_SET_B:  case OP_SET_A:
1736         case OP_SET_BE: case OP_SET_AE:
1737                 canonicalize_compare(insn);
1738                 /* fall through */
1739         case OP_SUB:
1740         case OP_DIVU: case OP_DIVS:
1741         case OP_MODU: case OP_MODS:
1742         case OP_SHL:
1743         case OP_LSR: case OP_ASR:
1744                 return simplify_binop(insn);
1745
1746         case OP_NOT: case OP_NEG: case OP_FNEG:
1747                 return simplify_unop(insn);
1748         case OP_LOAD:
1749                 if (!has_users(insn->target))
1750                         return kill_instruction(insn);
1751                 /* fall-through */
1752         case OP_STORE:
1753                 return simplify_memop(insn);
1754         case OP_SYMADDR:
1755                 if (dead_insn(insn, &insn->src, NULL, NULL))
1756                         return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
1757                 return replace_with_pseudo(insn, insn->src);
1758         case OP_SEXT: case OP_ZEXT:
1759         case OP_TRUNC:
1760                 return simplify_cast(insn);
1761         case OP_FCVTU: case OP_FCVTS:
1762         case OP_UCVTF: case OP_SCVTF:
1763         case OP_FCVTF:
1764         case OP_PTRCAST:
1765                 if (dead_insn(insn, &insn->src, NULL, NULL))
1766                         return REPEAT_CSE;
1767                 break;
1768         case OP_UTPTR:
1769         case OP_PTRTU:
1770                 return replace_with_pseudo(insn, insn->src);
1771         case OP_SLICE:
1772                 if (dead_insn(insn, &insn->src, NULL, NULL))
1773                         return REPEAT_CSE;
1774                 break;
1775         case OP_SETVAL:
1776         case OP_SETFVAL:
1777                 if (dead_insn(insn, NULL, NULL, NULL))
1778                         return REPEAT_CSE;
1779                 break;
1780         case OP_PHI:
1781                 if (dead_insn(insn, NULL, NULL, NULL)) {
1782                         kill_use_list(insn->phi_list);
1783                         return REPEAT_CSE;
1784                 }
1785                 return clean_up_phi(insn);
1786         case OP_PHISOURCE:
1787                 if (dead_insn(insn, &insn->phi_src, NULL, NULL))
1788                         return REPEAT_CSE;
1789                 break;
1790         case OP_SEL:
1791                 return simplify_select(insn);
1792         case OP_CBR:
1793                 return simplify_branch(insn);
1794         case OP_SWITCH:
1795                 return simplify_switch(insn);
1796         case OP_RANGE:
1797                 return simplify_range(insn);
1798         case OP_FADD:
1799         case OP_FSUB:
1800         case OP_FMUL:
1801         case OP_FDIV:
1802                 if (dead_insn(insn, &insn->src1, &insn->src2, NULL))
1803                         return REPEAT_CSE;
1804                 break;
1805         }
1806         return 0;
1807 }