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 }