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