1 /* Redundant Extension Elimination pass for the GNU compiler. 2 Copyright (C) 2010-2015 Free Software Foundation, Inc. 3 Contributed by Ilya Enkovich (ilya.enkovich@intel.com) 4 5 Based on the Redundant Zero-extension elimination pass contributed by 6 Sriraman Tallam (tmsriram@google.com) and Silvius Rus (rus@google.com). 7 8 This file is part of GCC. 9 10 GCC is free software; you can redistribute it and/or modify it under 11 the terms of the GNU General Public License as published by the Free 12 Software Foundation; either version 3, or (at your option) any later 13 version. 14 15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 16 WARRANTY; without even the implied warranty of MERCHANTABILITY or 17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 18 for more details. 19 20 You should have received a copy of the GNU General Public License 21 along with GCC; see the file COPYING3. If not see 22 <http://www.gnu.org/licenses/>. */ 23 24 25 /* Problem Description : 26 -------------------- 27 This pass is intended to remove redundant extension instructions. 28 Such instructions appear for different reasons. We expect some of 29 them due to implicit zero-extension in 64-bit registers after writing 30 to their lower 32-bit half (e.g. for the x86-64 architecture). 31 Another possible reason is a type cast which follows a load (for 32 instance a register restore) and which can be combined into a single 33 instruction, and for which earlier local passes, e.g. the combiner, 34 weren't able to optimize. 35 36 How does this pass work ? 37 -------------------------- 38 39 This pass is run after register allocation. Hence, all registers that 40 this pass deals with are hard registers. This pass first looks for an 41 extension instruction that could possibly be redundant. Such extension 42 instructions show up in RTL with the pattern : 43 (set (reg:<SWI248> x) (any_extend:<SWI248> (reg:<SWI124> x))), 44 where x can be any hard register. 45 Now, this pass tries to eliminate this instruction by merging the 46 extension with the definitions of register x. For instance, if 47 one of the definitions of register x was : 48 (set (reg:SI x) (plus:SI (reg:SI z1) (reg:SI z2))), 49 followed by extension : 50 (set (reg:DI x) (zero_extend:DI (reg:SI x))) 51 then the combination converts this into : 52 (set (reg:DI x) (zero_extend:DI (plus:SI (reg:SI z1) (reg:SI z2)))). 53 If all the merged definitions are recognizable assembly instructions, 54 the extension is effectively eliminated. 55 56 For example, for the x86-64 architecture, implicit zero-extensions 57 are captured with appropriate patterns in the i386.md file. Hence, 58 these merged definition can be matched to a single assembly instruction. 59 The original extension instruction is then deleted if all the 60 definitions can be merged. 61 62 However, there are cases where the definition instruction cannot be 63 merged with an extension. Examples are CALL instructions. In such 64 cases, the original extension is not redundant and this pass does 65 not delete it. 66 67 Handling conditional moves : 68 ---------------------------- 69 70 Architectures like x86-64 support conditional moves whose semantics for 71 extension differ from the other instructions. For instance, the 72 instruction *cmov ebx, eax* 73 zero-extends eax onto rax only when the move from ebx to eax happens. 74 Otherwise, eax may not be zero-extended. Consider conditional moves as 75 RTL instructions of the form 76 (set (reg:SI x) (if_then_else (cond) (reg:SI y) (reg:SI z))). 77 This pass tries to merge an extension with a conditional move by 78 actually merging the definitions of y and z with an extension and then 79 converting the conditional move into : 80 (set (reg:DI x) (if_then_else (cond) (reg:DI y) (reg:DI z))). 81 Since registers y and z are extended, register x will also be extended 82 after the conditional move. Note that this step has to be done 83 transitively since the definition of a conditional copy can be 84 another conditional copy. 85 86 Motivating Example I : 87 --------------------- 88 For this program : 89 ********************************************** 90 bad_code.c 91 92 int mask[1000]; 93 94 int foo(unsigned x) 95 { 96 if (x < 10) 97 x = x * 45; 98 else 99 x = x * 78; 100 return mask[x]; 101 } 102 ********************************************** 103 104 $ gcc -O2 bad_code.c 105 ........ 106 400315: b8 4e 00 00 00 mov $0x4e,%eax 107 40031a: 0f af f8 imul %eax,%edi 108 40031d: 89 ff mov %edi,%edi - useless extension 109 40031f: 8b 04 bd 60 19 40 00 mov 0x401960(,%rdi,4),%eax 110 400326: c3 retq 111 ...... 112 400330: ba 2d 00 00 00 mov $0x2d,%edx 113 400335: 0f af fa imul %edx,%edi 114 400338: 89 ff mov %edi,%edi - useless extension 115 40033a: 8b 04 bd 60 19 40 00 mov 0x401960(,%rdi,4),%eax 116 400341: c3 retq 117 118 $ gcc -O2 -free bad_code.c 119 ...... 120 400315: 6b ff 4e imul $0x4e,%edi,%edi 121 400318: 8b 04 bd 40 19 40 00 mov 0x401940(,%rdi,4),%eax 122 40031f: c3 retq 123 400320: 6b ff 2d imul $0x2d,%edi,%edi 124 400323: 8b 04 bd 40 19 40 00 mov 0x401940(,%rdi,4),%eax 125 40032a: c3 retq 126 127 Motivating Example II : 128 --------------------- 129 130 Here is an example with a conditional move. 131 132 For this program : 133 ********************************************** 134 135 unsigned long long foo(unsigned x , unsigned y) 136 { 137 unsigned z; 138 if (x > 100) 139 z = x + y; 140 else 141 z = x - y; 142 return (unsigned long long)(z); 143 } 144 145 $ gcc -O2 bad_code.c 146 ............ 147 400360: 8d 14 3e lea (%rsi,%rdi,1),%edx 148 400363: 89 f8 mov %edi,%eax 149 400365: 29 f0 sub %esi,%eax 150 400367: 83 ff 65 cmp $0x65,%edi 151 40036a: 0f 43 c2 cmovae %edx,%eax 152 40036d: 89 c0 mov %eax,%eax - useless extension 153 40036f: c3 retq 154 155 $ gcc -O2 -free bad_code.c 156 ............. 157 400360: 89 fa mov %edi,%edx 158 400362: 8d 04 3e lea (%rsi,%rdi,1),%eax 159 400365: 29 f2 sub %esi,%edx 160 400367: 83 ff 65 cmp $0x65,%edi 161 40036a: 89 d6 mov %edx,%esi 162 40036c: 48 0f 42 c6 cmovb %rsi,%rax 163 400370: c3 retq 164 165 Motivating Example III : 166 --------------------- 167 168 Here is an example with a type cast. 169 170 For this program : 171 ********************************************** 172 173 void test(int size, unsigned char *in, unsigned char *out) 174 { 175 int i; 176 unsigned char xr, xg, xy=0; 177 178 for (i = 0; i < size; i++) { 179 xr = *in++; 180 xg = *in++; 181 xy = (unsigned char) ((19595*xr + 38470*xg) >> 16); 182 *out++ = xy; 183 } 184 } 185 186 $ gcc -O2 bad_code.c 187 ............ 188 10: 0f b6 0e movzbl (%rsi),%ecx 189 13: 0f b6 46 01 movzbl 0x1(%rsi),%eax 190 17: 48 83 c6 02 add $0x2,%rsi 191 1b: 0f b6 c9 movzbl %cl,%ecx - useless extension 192 1e: 0f b6 c0 movzbl %al,%eax - useless extension 193 21: 69 c9 8b 4c 00 00 imul $0x4c8b,%ecx,%ecx 194 27: 69 c0 46 96 00 00 imul $0x9646,%eax,%eax 195 196 $ gcc -O2 -free bad_code.c 197 ............. 198 10: 0f b6 0e movzbl (%rsi),%ecx 199 13: 0f b6 46 01 movzbl 0x1(%rsi),%eax 200 17: 48 83 c6 02 add $0x2,%rsi 201 1b: 69 c9 8b 4c 00 00 imul $0x4c8b,%ecx,%ecx 202 21: 69 c0 46 96 00 00 imul $0x9646,%eax,%eax 203 204 Usefulness : 205 ---------- 206 207 The original redundant zero-extension elimination pass reported reduction 208 of the dynamic instruction count of a compression benchmark by 2.8% and 209 improvement of its run time by about 1%. 210 211 The additional performance gain with the enhanced pass is mostly expected 212 on in-order architectures where redundancy cannot be compensated by out of 213 order execution. Measurements showed up to 10% performance gain (reduced 214 run time) on EEMBC 2.0 benchmarks on Atom processor with geomean performance 215 gain 1%. */ 216 217 218 #include "config.h" 219 #include "system.h" 220 #include "coretypes.h" 221 #include "tm.h" 222 #include "rtl.h" 223 #include "hash-set.h" 224 #include "machmode.h" 225 #include "vec.h" 226 #include "double-int.h" 227 #include "input.h" 228 #include "alias.h" 229 #include "symtab.h" 230 #include "wide-int.h" 231 #include "inchash.h" 232 #include "tree.h" 233 #include "tm_p.h" 234 #include "flags.h" 235 #include "regs.h" 236 #include "hard-reg-set.h" 237 #include "predict.h" 238 #include "function.h" 239 #include "dominance.h" 240 #include "cfg.h" 241 #include "cfgrtl.h" 242 #include "basic-block.h" 243 #include "insn-config.h" 244 #include "hashtab.h" 245 #include "statistics.h" 246 #include "real.h" 247 #include "fixed-value.h" 248 #include "expmed.h" 249 #include "dojump.h" 250 #include "explow.h" 251 #include "calls.h" 252 #include "emit-rtl.h" 253 #include "varasm.h" 254 #include "stmt.h" 255 #include "expr.h" 256 #include "insn-attr.h" 257 #include "recog.h" 258 #include "diagnostic-core.h" 259 #include "target.h" 260 #include "insn-codes.h" 261 #include "optabs.h" 262 #include "rtlhooks-def.h" 263 #include "params.h" 264 #include "tree-pass.h" 265 #include "df.h" 266 #include "hash-map.h" 267 #include "is-a.h" 268 #include "plugin-api.h" 269 #include "ipa-ref.h" 270 #include "cgraph.h" 271 272 /* This structure represents a candidate for elimination. */ 273 274 typedef struct ext_cand 275 { 276 /* The expression. */ 277 const_rtx expr; 278 279 /* The kind of extension. */ 280 enum rtx_code code; 281 282 /* The destination mode. */ 283 machine_mode mode; 284 285 /* The instruction where it lives. */ 286 rtx_insn *insn; 287 } ext_cand; 288 289 290 static int max_insn_uid; 291 292 /* Update or remove REG_EQUAL or REG_EQUIV notes for INSN. */ 293 294 static bool 295 update_reg_equal_equiv_notes (rtx_insn *insn, machine_mode new_mode, 296 machine_mode old_mode, enum rtx_code code) 297 { 298 rtx *loc = ®_NOTES (insn); 299 while (*loc) 300 { 301 enum reg_note kind = REG_NOTE_KIND (*loc); 302 if (kind == REG_EQUAL || kind == REG_EQUIV) 303 { 304 rtx orig_src = XEXP (*loc, 0); 305 /* Update equivalency constants. Recall that RTL constants are 306 sign-extended. */ 307 if (GET_CODE (orig_src) == CONST_INT 308 && HOST_BITS_PER_WIDE_INT >= GET_MODE_BITSIZE (new_mode)) 309 { 310 if (INTVAL (orig_src) >= 0 || code == SIGN_EXTEND) 311 /* Nothing needed. */; 312 else 313 { 314 /* Zero-extend the negative constant by masking out the 315 bits outside the source mode. */ 316 rtx new_const_int 317 = gen_int_mode (INTVAL (orig_src) 318 & GET_MODE_MASK (old_mode), 319 new_mode); 320 if (!validate_change (insn, &XEXP (*loc, 0), 321 new_const_int, true)) 322 return false; 323 } 324 loc = &XEXP (*loc, 1); 325 } 326 /* Drop all other notes, they assume a wrong mode. */ 327 else if (!validate_change (insn, loc, XEXP (*loc, 1), true)) 328 return false; 329 } 330 else 331 loc = &XEXP (*loc, 1); 332 } 333 return true; 334 } 335 336 /* Given a insn (CURR_INSN), an extension candidate for removal (CAND) 337 and a pointer to the SET rtx (ORIG_SET) that needs to be modified, 338 this code modifies the SET rtx to a new SET rtx that extends the 339 right hand expression into a register on the left hand side. Note 340 that multiple assumptions are made about the nature of the set that 341 needs to be true for this to work and is called from merge_def_and_ext. 342 343 Original : 344 (set (reg a) (expression)) 345 346 Transform : 347 (set (reg a) (any_extend (expression))) 348 349 Special Cases : 350 If the expression is a constant or another extension, then directly 351 assign it to the register. */ 352 353 static bool 354 combine_set_extension (ext_cand *cand, rtx_insn *curr_insn, rtx *orig_set) 355 { 356 rtx orig_src = SET_SRC (*orig_set); 357 machine_mode orig_mode = GET_MODE (SET_DEST (*orig_set)); 358 rtx new_set; 359 rtx cand_pat = PATTERN (cand->insn); 360 361 /* If the extension's source/destination registers are not the same 362 then we need to change the original load to reference the destination 363 of the extension. Then we need to emit a copy from that destination 364 to the original destination of the load. */ 365 rtx new_reg; 366 bool copy_needed 367 = (REGNO (SET_DEST (cand_pat)) != REGNO (XEXP (SET_SRC (cand_pat), 0))); 368 if (copy_needed) 369 new_reg = gen_rtx_REG (cand->mode, REGNO (SET_DEST (cand_pat))); 370 else 371 new_reg = gen_rtx_REG (cand->mode, REGNO (SET_DEST (*orig_set))); 372 373 #if 0 374 /* Rethinking test. Temporarily disabled. */ 375 /* We're going to be widening the result of DEF_INSN, ensure that doing so 376 doesn't change the number of hard registers needed for the result. */ 377 if (HARD_REGNO_NREGS (REGNO (new_reg), cand->mode) 378 != HARD_REGNO_NREGS (REGNO (SET_DEST (*orig_set)), 379 GET_MODE (SET_DEST (*orig_set)))) 380 return false; 381 #endif 382 383 /* Merge constants by directly moving the constant into the register under 384 some conditions. Recall that RTL constants are sign-extended. */ 385 if (GET_CODE (orig_src) == CONST_INT 386 && HOST_BITS_PER_WIDE_INT >= GET_MODE_BITSIZE (cand->mode)) 387 { 388 if (INTVAL (orig_src) >= 0 || cand->code == SIGN_EXTEND) 389 new_set = gen_rtx_SET (VOIDmode, new_reg, orig_src); 390 else 391 { 392 /* Zero-extend the negative constant by masking out the bits outside 393 the source mode. */ 394 rtx new_const_int 395 = gen_int_mode (INTVAL (orig_src) & GET_MODE_MASK (orig_mode), 396 GET_MODE (new_reg)); 397 new_set = gen_rtx_SET (VOIDmode, new_reg, new_const_int); 398 } 399 } 400 else if (GET_MODE (orig_src) == VOIDmode) 401 { 402 /* This is mostly due to a call insn that should not be optimized. */ 403 return false; 404 } 405 else if (GET_CODE (orig_src) == cand->code) 406 { 407 /* Here is a sequence of two extensions. Try to merge them. */ 408 rtx temp_extension 409 = gen_rtx_fmt_e (cand->code, cand->mode, XEXP (orig_src, 0)); 410 rtx simplified_temp_extension = simplify_rtx (temp_extension); 411 if (simplified_temp_extension) 412 temp_extension = simplified_temp_extension; 413 new_set = gen_rtx_SET (VOIDmode, new_reg, temp_extension); 414 } 415 else if (GET_CODE (orig_src) == IF_THEN_ELSE) 416 { 417 /* Only IF_THEN_ELSE of phi-type copies are combined. Otherwise, 418 in general, IF_THEN_ELSE should not be combined. */ 419 return false; 420 } 421 else 422 { 423 /* This is the normal case. */ 424 rtx temp_extension 425 = gen_rtx_fmt_e (cand->code, cand->mode, orig_src); 426 rtx simplified_temp_extension = simplify_rtx (temp_extension); 427 if (simplified_temp_extension) 428 temp_extension = simplified_temp_extension; 429 new_set = gen_rtx_SET (VOIDmode, new_reg, temp_extension); 430 } 431 432 /* This change is a part of a group of changes. Hence, 433 validate_change will not try to commit the change. */ 434 if (validate_change (curr_insn, orig_set, new_set, true) 435 && update_reg_equal_equiv_notes (curr_insn, cand->mode, orig_mode, 436 cand->code)) 437 { 438 if (dump_file) 439 { 440 fprintf (dump_file, 441 "Tentatively merged extension with definition %s:\n", 442 (copy_needed) ? "(copy needed)" : ""); 443 print_rtl_single (dump_file, curr_insn); 444 } 445 return true; 446 } 447 448 return false; 449 } 450 451 /* Treat if_then_else insns, where the operands of both branches 452 are registers, as copies. For instance, 453 Original : 454 (set (reg:SI a) (if_then_else (cond) (reg:SI b) (reg:SI c))) 455 Transformed : 456 (set (reg:DI a) (if_then_else (cond) (reg:DI b) (reg:DI c))) 457 DEF_INSN is the if_then_else insn. */ 458 459 static bool 460 transform_ifelse (ext_cand *cand, rtx_insn *def_insn) 461 { 462 rtx set_insn = PATTERN (def_insn); 463 rtx srcreg, dstreg, srcreg2; 464 rtx map_srcreg, map_dstreg, map_srcreg2; 465 rtx ifexpr; 466 rtx cond; 467 rtx new_set; 468 469 gcc_assert (GET_CODE (set_insn) == SET); 470 471 cond = XEXP (SET_SRC (set_insn), 0); 472 dstreg = SET_DEST (set_insn); 473 srcreg = XEXP (SET_SRC (set_insn), 1); 474 srcreg2 = XEXP (SET_SRC (set_insn), 2); 475 /* If the conditional move already has the right or wider mode, 476 there is nothing to do. */ 477 if (GET_MODE_SIZE (GET_MODE (dstreg)) >= GET_MODE_SIZE (cand->mode)) 478 return true; 479 480 map_srcreg = gen_rtx_REG (cand->mode, REGNO (srcreg)); 481 map_srcreg2 = gen_rtx_REG (cand->mode, REGNO (srcreg2)); 482 map_dstreg = gen_rtx_REG (cand->mode, REGNO (dstreg)); 483 ifexpr = gen_rtx_IF_THEN_ELSE (cand->mode, cond, map_srcreg, map_srcreg2); 484 new_set = gen_rtx_SET (VOIDmode, map_dstreg, ifexpr); 485 486 if (validate_change (def_insn, &PATTERN (def_insn), new_set, true) 487 && update_reg_equal_equiv_notes (def_insn, cand->mode, GET_MODE (dstreg), 488 cand->code)) 489 { 490 if (dump_file) 491 { 492 fprintf (dump_file, 493 "Mode of conditional move instruction extended:\n"); 494 print_rtl_single (dump_file, def_insn); 495 } 496 return true; 497 } 498 499 return false; 500 } 501 502 /* Get all the reaching definitions of an instruction. The definitions are 503 desired for REG used in INSN. Return the definition list or NULL if a 504 definition is missing. If DEST is non-NULL, additionally push the INSN 505 of the definitions onto DEST. */ 506 507 static struct df_link * 508 get_defs (rtx_insn *insn, rtx reg, vec<rtx_insn *> *dest) 509 { 510 df_ref use; 511 struct df_link *ref_chain, *ref_link; 512 513 FOR_EACH_INSN_USE (use, insn) 514 { 515 if (GET_CODE (DF_REF_REG (use)) == SUBREG) 516 return NULL; 517 if (REGNO (DF_REF_REG (use)) == REGNO (reg)) 518 break; 519 } 520 521 gcc_assert (use != NULL); 522 523 ref_chain = DF_REF_CHAIN (use); 524 525 for (ref_link = ref_chain; ref_link; ref_link = ref_link->next) 526 { 527 /* Problem getting some definition for this instruction. */ 528 if (ref_link->ref == NULL) 529 return NULL; 530 if (DF_REF_INSN_INFO (ref_link->ref) == NULL) 531 return NULL; 532 /* As global regs are assumed to be defined at each function call 533 dataflow can report a call_insn as being a definition of REG. 534 But we can't do anything with that in this pass so proceed only 535 if the instruction really sets REG in a way that can be deduced 536 from the RTL structure. */ 537 if (global_regs[REGNO (reg)] 538 && !set_of (reg, DF_REF_INSN (ref_link->ref))) 539 return NULL; 540 } 541 542 if (dest) 543 for (ref_link = ref_chain; ref_link; ref_link = ref_link->next) 544 dest->safe_push (DF_REF_INSN (ref_link->ref)); 545 546 return ref_chain; 547 } 548 549 /* Return true if INSN is 550 (SET (reg REGNO (def_reg)) (if_then_else (cond) (REG x1) (REG x2))) 551 and store x1 and x2 in REG_1 and REG_2. */ 552 553 static bool 554 is_cond_copy_insn (rtx_insn *insn, rtx *reg1, rtx *reg2) 555 { 556 rtx expr = single_set (insn); 557 558 if (expr != NULL_RTX 559 && GET_CODE (expr) == SET 560 && GET_CODE (SET_DEST (expr)) == REG 561 && GET_CODE (SET_SRC (expr)) == IF_THEN_ELSE 562 && GET_CODE (XEXP (SET_SRC (expr), 1)) == REG 563 && GET_CODE (XEXP (SET_SRC (expr), 2)) == REG) 564 { 565 *reg1 = XEXP (SET_SRC (expr), 1); 566 *reg2 = XEXP (SET_SRC (expr), 2); 567 return true; 568 } 569 570 return false; 571 } 572 573 enum ext_modified_kind 574 { 575 /* The insn hasn't been modified by ree pass yet. */ 576 EXT_MODIFIED_NONE, 577 /* Changed into zero extension. */ 578 EXT_MODIFIED_ZEXT, 579 /* Changed into sign extension. */ 580 EXT_MODIFIED_SEXT 581 }; 582 583 struct ATTRIBUTE_PACKED ext_modified 584 { 585 /* Mode from which ree has zero or sign extended the destination. */ 586 ENUM_BITFIELD(machine_mode) mode : 8; 587 588 /* Kind of modification of the insn. */ 589 ENUM_BITFIELD(ext_modified_kind) kind : 2; 590 591 unsigned int do_not_reextend : 1; 592 593 /* True if the insn is scheduled to be deleted. */ 594 unsigned int deleted : 1; 595 }; 596 597 /* Vectors used by combine_reaching_defs and its helpers. */ 598 typedef struct ext_state 599 { 600 /* In order to avoid constant alloc/free, we keep these 601 4 vectors live through the entire find_and_remove_re and just 602 truncate them each time. */ 603 vec<rtx_insn *> defs_list; 604 vec<rtx_insn *> copies_list; 605 vec<rtx_insn *> modified_list; 606 vec<rtx_insn *> work_list; 607 608 /* For instructions that have been successfully modified, this is 609 the original mode from which the insn is extending and 610 kind of extension. */ 611 struct ext_modified *modified; 612 } ext_state; 613 614 /* Reaching Definitions of the extended register could be conditional copies 615 or regular definitions. This function separates the two types into two 616 lists, STATE->DEFS_LIST and STATE->COPIES_LIST. This is necessary because, 617 if a reaching definition is a conditional copy, merging the extension with 618 this definition is wrong. Conditional copies are merged by transitively 619 merging their definitions. The defs_list is populated with all the reaching 620 definitions of the extension instruction (EXTEND_INSN) which must be merged 621 with an extension. The copies_list contains all the conditional moves that 622 will later be extended into a wider mode conditional move if all the merges 623 are successful. The function returns false upon failure, true upon 624 success. */ 625 626 static bool 627 make_defs_and_copies_lists (rtx_insn *extend_insn, const_rtx set_pat, 628 ext_state *state) 629 { 630 rtx src_reg = XEXP (SET_SRC (set_pat), 0); 631 bool *is_insn_visited; 632 bool ret = true; 633 634 state->work_list.truncate (0); 635 636 /* Initialize the work list. */ 637 if (!get_defs (extend_insn, src_reg, &state->work_list)) 638 return false; 639 640 is_insn_visited = XCNEWVEC (bool, max_insn_uid); 641 642 /* Perform transitive closure for conditional copies. */ 643 while (!state->work_list.is_empty ()) 644 { 645 rtx_insn *def_insn = state->work_list.pop (); 646 rtx reg1, reg2; 647 648 gcc_assert (INSN_UID (def_insn) < max_insn_uid); 649 650 if (is_insn_visited[INSN_UID (def_insn)]) 651 continue; 652 is_insn_visited[INSN_UID (def_insn)] = true; 653 654 if (is_cond_copy_insn (def_insn, ®1, ®2)) 655 { 656 /* Push it onto the copy list first. */ 657 state->copies_list.safe_push (def_insn); 658 659 /* Now perform the transitive closure. */ 660 if (!get_defs (def_insn, reg1, &state->work_list) 661 || !get_defs (def_insn, reg2, &state->work_list)) 662 { 663 ret = false; 664 break; 665 } 666 } 667 else 668 state->defs_list.safe_push (def_insn); 669 } 670 671 XDELETEVEC (is_insn_visited); 672 673 return ret; 674 } 675 676 /* If DEF_INSN has single SET expression, possibly buried inside 677 a PARALLEL, return the address of the SET expression, else 678 return NULL. This is similar to single_set, except that 679 single_set allows multiple SETs when all but one is dead. */ 680 static rtx * 681 get_sub_rtx (rtx_insn *def_insn) 682 { 683 enum rtx_code code = GET_CODE (PATTERN (def_insn)); 684 rtx *sub_rtx = NULL; 685 686 if (code == PARALLEL) 687 { 688 for (int i = 0; i < XVECLEN (PATTERN (def_insn), 0); i++) 689 { 690 rtx s_expr = XVECEXP (PATTERN (def_insn), 0, i); 691 if (GET_CODE (s_expr) != SET) 692 continue; 693 694 if (sub_rtx == NULL) 695 sub_rtx = &XVECEXP (PATTERN (def_insn), 0, i); 696 else 697 { 698 /* PARALLEL with multiple SETs. */ 699 return NULL; 700 } 701 } 702 } 703 else if (code == SET) 704 sub_rtx = &PATTERN (def_insn); 705 else 706 { 707 /* It is not a PARALLEL or a SET, what could it be ? */ 708 return NULL; 709 } 710 711 gcc_assert (sub_rtx != NULL); 712 return sub_rtx; 713 } 714 715 /* Merge the DEF_INSN with an extension. Calls combine_set_extension 716 on the SET pattern. */ 717 718 static bool 719 merge_def_and_ext (ext_cand *cand, rtx_insn *def_insn, ext_state *state) 720 { 721 machine_mode ext_src_mode; 722 rtx *sub_rtx; 723 724 ext_src_mode = GET_MODE (XEXP (SET_SRC (cand->expr), 0)); 725 sub_rtx = get_sub_rtx (def_insn); 726 727 if (sub_rtx == NULL) 728 return false; 729 730 if (REG_P (SET_DEST (*sub_rtx)) 731 && (GET_MODE (SET_DEST (*sub_rtx)) == ext_src_mode 732 || ((state->modified[INSN_UID (def_insn)].kind 733 == (cand->code == ZERO_EXTEND 734 ? EXT_MODIFIED_ZEXT : EXT_MODIFIED_SEXT)) 735 && state->modified[INSN_UID (def_insn)].mode 736 == ext_src_mode))) 737 { 738 if (GET_MODE_SIZE (GET_MODE (SET_DEST (*sub_rtx))) 739 >= GET_MODE_SIZE (cand->mode)) 740 return true; 741 /* If def_insn is already scheduled to be deleted, don't attempt 742 to modify it. */ 743 if (state->modified[INSN_UID (def_insn)].deleted) 744 return false; 745 if (combine_set_extension (cand, def_insn, sub_rtx)) 746 { 747 if (state->modified[INSN_UID (def_insn)].kind == EXT_MODIFIED_NONE) 748 state->modified[INSN_UID (def_insn)].mode = ext_src_mode; 749 return true; 750 } 751 } 752 753 return false; 754 } 755 756 /* Given SRC, which should be one or more extensions of a REG, strip 757 away the extensions and return the REG. */ 758 759 static inline rtx 760 get_extended_src_reg (rtx src) 761 { 762 while (GET_CODE (src) == SIGN_EXTEND || GET_CODE (src) == ZERO_EXTEND) 763 src = XEXP (src, 0); 764 gcc_assert (REG_P (src)); 765 return src; 766 } 767 768 /* This function goes through all reaching defs of the source 769 of the candidate for elimination (CAND) and tries to combine 770 the extension with the definition instruction. The changes 771 are made as a group so that even if one definition cannot be 772 merged, all reaching definitions end up not being merged. 773 When a conditional copy is encountered, merging is attempted 774 transitively on its definitions. It returns true upon success 775 and false upon failure. */ 776 777 static bool 778 combine_reaching_defs (ext_cand *cand, const_rtx set_pat, ext_state *state) 779 { 780 rtx_insn *def_insn; 781 bool merge_successful = true; 782 int i; 783 int defs_ix; 784 bool outcome; 785 786 state->defs_list.truncate (0); 787 state->copies_list.truncate (0); 788 789 outcome = make_defs_and_copies_lists (cand->insn, set_pat, state); 790 791 if (!outcome) 792 return false; 793 794 /* If the destination operand of the extension is a different 795 register than the source operand, then additional restrictions 796 are needed. Note we have to handle cases where we have nested 797 extensions in the source operand. */ 798 bool copy_needed 799 = (REGNO (SET_DEST (PATTERN (cand->insn))) 800 != REGNO (get_extended_src_reg (SET_SRC (PATTERN (cand->insn))))); 801 if (copy_needed) 802 { 803 /* Considering transformation of 804 (set (reg1) (expression)) 805 ... 806 (set (reg2) (any_extend (reg1))) 807 808 into 809 810 (set (reg2) (any_extend (expression))) 811 (set (reg1) (reg2)) 812 ... */ 813 814 /* In theory we could handle more than one reaching def, it 815 just makes the code to update the insn stream more complex. */ 816 if (state->defs_list.length () != 1) 817 return false; 818 819 /* We don't have the structure described above if there are 820 conditional moves in between the def and the candidate, 821 and we will not handle them correctly. See PR68194. */ 822 if (state->copies_list.length () > 0) 823 return false; 824 825 /* We require the candidate not already be modified. It may, 826 for example have been changed from a (sign_extend (reg)) 827 into (zero_extend (sign_extend (reg))). 828 829 Handling that case shouldn't be terribly difficult, but the code 830 here and the code to emit copies would need auditing. Until 831 we see a need, this is the safe thing to do. */ 832 if (state->modified[INSN_UID (cand->insn)].kind != EXT_MODIFIED_NONE) 833 return false; 834 835 machine_mode dst_mode = GET_MODE (SET_DEST (PATTERN (cand->insn))); 836 rtx src_reg = get_extended_src_reg (SET_SRC (PATTERN (cand->insn))); 837 838 /* Ensure the number of hard registers of the copy match. */ 839 if (HARD_REGNO_NREGS (REGNO (src_reg), dst_mode) 840 != HARD_REGNO_NREGS (REGNO (src_reg), GET_MODE (src_reg))) 841 return false; 842 843 /* There's only one reaching def. */ 844 rtx_insn *def_insn = state->defs_list[0]; 845 846 /* The defining statement must not have been modified either. */ 847 if (state->modified[INSN_UID (def_insn)].kind != EXT_MODIFIED_NONE) 848 return false; 849 850 /* The defining statement and candidate insn must be in the same block. 851 This is merely to keep the test for safety and updating the insn 852 stream simple. Also ensure that within the block the candidate 853 follows the defining insn. */ 854 basic_block bb = BLOCK_FOR_INSN (cand->insn); 855 if (bb != BLOCK_FOR_INSN (def_insn) 856 || DF_INSN_LUID (def_insn) > DF_INSN_LUID (cand->insn)) 857 return false; 858 859 /* If there is an overlap between the destination of DEF_INSN and 860 CAND->insn, then this transformation is not safe. Note we have 861 to test in the widened mode. */ 862 rtx *dest_sub_rtx = get_sub_rtx (def_insn); 863 if (dest_sub_rtx == NULL 864 || !REG_P (SET_DEST (*dest_sub_rtx))) 865 return false; 866 867 rtx tmp_reg = gen_rtx_REG (GET_MODE (SET_DEST (PATTERN (cand->insn))), 868 REGNO (SET_DEST (*dest_sub_rtx))); 869 if (reg_overlap_mentioned_p (tmp_reg, SET_DEST (PATTERN (cand->insn)))) 870 return false; 871 872 /* The destination register of the extension insn must not be 873 used or set between the def_insn and cand->insn exclusive. */ 874 if (reg_used_between_p (SET_DEST (PATTERN (cand->insn)), 875 def_insn, cand->insn) 876 || reg_set_between_p (SET_DEST (PATTERN (cand->insn)), 877 def_insn, cand->insn)) 878 return false; 879 880 /* We must be able to copy between the two registers. Generate, 881 recognize and verify constraints of the copy. Also fail if this 882 generated more than one insn. 883 884 This generates garbage since we throw away the insn when we're 885 done, only to recreate it later if this test was successful. 886 887 Make sure to get the mode from the extension (cand->insn). This 888 is different than in the code to emit the copy as we have not 889 modified the defining insn yet. */ 890 start_sequence (); 891 rtx pat = PATTERN (cand->insn); 892 rtx new_dst = gen_rtx_REG (GET_MODE (SET_DEST (pat)), 893 REGNO (get_extended_src_reg (SET_SRC (pat)))); 894 rtx new_src = gen_rtx_REG (GET_MODE (SET_DEST (pat)), 895 REGNO (SET_DEST (pat))); 896 emit_move_insn (new_dst, new_src); 897 898 rtx_insn *insn = get_insns(); 899 end_sequence (); 900 if (NEXT_INSN (insn)) 901 return false; 902 if (recog_memoized (insn) == -1) 903 return false; 904 extract_insn (insn); 905 if (!constrain_operands (1, get_preferred_alternatives (insn, bb))) 906 return false; 907 } 908 909 910 /* If cand->insn has been already modified, update cand->mode to a wider 911 mode if possible, or punt. */ 912 if (state->modified[INSN_UID (cand->insn)].kind != EXT_MODIFIED_NONE) 913 { 914 machine_mode mode; 915 rtx set; 916 917 if (state->modified[INSN_UID (cand->insn)].kind 918 != (cand->code == ZERO_EXTEND 919 ? EXT_MODIFIED_ZEXT : EXT_MODIFIED_SEXT) 920 || state->modified[INSN_UID (cand->insn)].mode != cand->mode 921 || (set = single_set (cand->insn)) == NULL_RTX) 922 return false; 923 mode = GET_MODE (SET_DEST (set)); 924 gcc_assert (GET_MODE_SIZE (mode) >= GET_MODE_SIZE (cand->mode)); 925 cand->mode = mode; 926 } 927 928 merge_successful = true; 929 930 /* Go through the defs vector and try to merge all the definitions 931 in this vector. */ 932 state->modified_list.truncate (0); 933 FOR_EACH_VEC_ELT (state->defs_list, defs_ix, def_insn) 934 { 935 if (merge_def_and_ext (cand, def_insn, state)) 936 state->modified_list.safe_push (def_insn); 937 else 938 { 939 merge_successful = false; 940 break; 941 } 942 } 943 944 /* Now go through the conditional copies vector and try to merge all 945 the copies in this vector. */ 946 if (merge_successful) 947 { 948 FOR_EACH_VEC_ELT (state->copies_list, i, def_insn) 949 { 950 if (transform_ifelse (cand, def_insn)) 951 state->modified_list.safe_push (def_insn); 952 else 953 { 954 merge_successful = false; 955 break; 956 } 957 } 958 } 959 960 if (merge_successful) 961 { 962 /* Commit the changes here if possible 963 FIXME: It's an all-or-nothing scenario. Even if only one definition 964 cannot be merged, we entirely give up. In the future, we should allow 965 extensions to be partially eliminated along those paths where the 966 definitions could be merged. */ 967 if (apply_change_group ()) 968 { 969 if (dump_file) 970 fprintf (dump_file, "All merges were successful.\n"); 971 972 FOR_EACH_VEC_ELT (state->modified_list, i, def_insn) 973 { 974 ext_modified *modified = &state->modified[INSN_UID (def_insn)]; 975 if (modified->kind == EXT_MODIFIED_NONE) 976 modified->kind = (cand->code == ZERO_EXTEND ? EXT_MODIFIED_ZEXT 977 : EXT_MODIFIED_SEXT); 978 979 if (copy_needed) 980 modified->do_not_reextend = 1; 981 } 982 return true; 983 } 984 else 985 { 986 /* Changes need not be cancelled explicitly as apply_change_group 987 does it. Print list of definitions in the dump_file for debug 988 purposes. This extension cannot be deleted. */ 989 if (dump_file) 990 { 991 fprintf (dump_file, 992 "Merge cancelled, non-mergeable definitions:\n"); 993 FOR_EACH_VEC_ELT (state->modified_list, i, def_insn) 994 print_rtl_single (dump_file, def_insn); 995 } 996 } 997 } 998 else 999 { 1000 /* Cancel any changes that have been made so far. */ 1001 cancel_changes (0); 1002 } 1003 1004 return false; 1005 } 1006 1007 /* Add an extension pattern that could be eliminated. */ 1008 1009 static void 1010 add_removable_extension (const_rtx expr, rtx_insn *insn, 1011 vec<ext_cand> *insn_list, 1012 unsigned *def_map) 1013 { 1014 enum rtx_code code; 1015 machine_mode mode; 1016 unsigned int idx; 1017 rtx src, dest; 1018 1019 /* We are looking for SET (REG N) (ANY_EXTEND (REG N)). */ 1020 if (GET_CODE (expr) != SET) 1021 return; 1022 1023 src = SET_SRC (expr); 1024 code = GET_CODE (src); 1025 dest = SET_DEST (expr); 1026 mode = GET_MODE (dest); 1027 1028 if (REG_P (dest) 1029 && (code == SIGN_EXTEND || code == ZERO_EXTEND) 1030 && REG_P (XEXP (src, 0))) 1031 { 1032 struct df_link *defs, *def; 1033 ext_cand *cand; 1034 1035 /* First, make sure we can get all the reaching definitions. */ 1036 defs = get_defs (insn, XEXP (src, 0), NULL); 1037 if (!defs) 1038 { 1039 if (dump_file) 1040 { 1041 fprintf (dump_file, "Cannot eliminate extension:\n"); 1042 print_rtl_single (dump_file, insn); 1043 fprintf (dump_file, " because of missing definition(s)\n"); 1044 } 1045 return; 1046 } 1047 1048 /* Second, make sure the reaching definitions don't feed another and 1049 different extension. FIXME: this obviously can be improved. */ 1050 for (def = defs; def; def = def->next) 1051 if ((idx = def_map[INSN_UID (DF_REF_INSN (def->ref))]) 1052 && idx != -1U 1053 && (cand = &(*insn_list)[idx - 1]) 1054 && cand->code != code) 1055 { 1056 if (dump_file) 1057 { 1058 fprintf (dump_file, "Cannot eliminate extension:\n"); 1059 print_rtl_single (dump_file, insn); 1060 fprintf (dump_file, " because of other extension\n"); 1061 } 1062 return; 1063 } 1064 /* For vector mode extensions, ensure that all uses of the 1065 XEXP (src, 0) register are the same extension (both code 1066 and to which mode), as unlike integral extensions lowpart 1067 subreg of the sign/zero extended register are not equal 1068 to the original register, so we have to change all uses or 1069 none. */ 1070 else if (VECTOR_MODE_P (GET_MODE (XEXP (src, 0)))) 1071 { 1072 if (idx == 0) 1073 { 1074 struct df_link *ref_chain, *ref_link; 1075 1076 ref_chain = DF_REF_CHAIN (def->ref); 1077 for (ref_link = ref_chain; ref_link; ref_link = ref_link->next) 1078 { 1079 if (ref_link->ref == NULL 1080 || DF_REF_INSN_INFO (ref_link->ref) == NULL) 1081 { 1082 idx = -1U; 1083 break; 1084 } 1085 rtx_insn *use_insn = DF_REF_INSN (ref_link->ref); 1086 const_rtx use_set; 1087 if (use_insn == insn || DEBUG_INSN_P (use_insn)) 1088 continue; 1089 if (!(use_set = single_set (use_insn)) 1090 || !REG_P (SET_DEST (use_set)) 1091 || GET_MODE (SET_DEST (use_set)) != GET_MODE (dest) 1092 || GET_CODE (SET_SRC (use_set)) != code 1093 || !rtx_equal_p (XEXP (SET_SRC (use_set), 0), 1094 XEXP (src, 0))) 1095 { 1096 idx = -1U; 1097 break; 1098 } 1099 } 1100 if (idx == -1U) 1101 def_map[INSN_UID (DF_REF_INSN (def->ref))] = idx; 1102 } 1103 if (idx == -1U) 1104 { 1105 if (dump_file) 1106 { 1107 fprintf (dump_file, "Cannot eliminate extension:\n"); 1108 print_rtl_single (dump_file, insn); 1109 fprintf (dump_file, 1110 " because some vector uses aren't extension\n"); 1111 } 1112 return; 1113 } 1114 } 1115 1116 /* Then add the candidate to the list and insert the reaching definitions 1117 into the definition map. */ 1118 ext_cand e = {expr, code, mode, insn}; 1119 insn_list->safe_push (e); 1120 idx = insn_list->length (); 1121 1122 for (def = defs; def; def = def->next) 1123 def_map[INSN_UID (DF_REF_INSN (def->ref))] = idx; 1124 } 1125 } 1126 1127 /* Traverse the instruction stream looking for extensions and return the 1128 list of candidates. */ 1129 1130 static vec<ext_cand> 1131 find_removable_extensions (void) 1132 { 1133 vec<ext_cand> insn_list = vNULL; 1134 basic_block bb; 1135 rtx_insn *insn; 1136 rtx set; 1137 unsigned *def_map = XCNEWVEC (unsigned, max_insn_uid); 1138 1139 FOR_EACH_BB_FN (bb, cfun) 1140 FOR_BB_INSNS (bb, insn) 1141 { 1142 if (!NONDEBUG_INSN_P (insn)) 1143 continue; 1144 1145 set = single_set (insn); 1146 if (set == NULL_RTX) 1147 continue; 1148 add_removable_extension (set, insn, &insn_list, def_map); 1149 } 1150 1151 XDELETEVEC (def_map); 1152 1153 return insn_list; 1154 } 1155 1156 /* This is the main function that checks the insn stream for redundant 1157 extensions and tries to remove them if possible. */ 1158 1159 static void 1160 find_and_remove_re (void) 1161 { 1162 ext_cand *curr_cand; 1163 rtx_insn *curr_insn = NULL; 1164 int num_re_opportunities = 0, num_realized = 0, i; 1165 vec<ext_cand> reinsn_list; 1166 auto_vec<rtx_insn *> reinsn_del_list; 1167 auto_vec<rtx_insn *> reinsn_copy_list; 1168 ext_state state; 1169 1170 /* Construct DU chain to get all reaching definitions of each 1171 extension instruction. */ 1172 df_set_flags (DF_RD_PRUNE_DEAD_DEFS); 1173 df_chain_add_problem (DF_UD_CHAIN + DF_DU_CHAIN); 1174 df_analyze (); 1175 df_set_flags (DF_DEFER_INSN_RESCAN); 1176 1177 max_insn_uid = get_max_uid (); 1178 reinsn_list = find_removable_extensions (); 1179 state.defs_list.create (0); 1180 state.copies_list.create (0); 1181 state.modified_list.create (0); 1182 state.work_list.create (0); 1183 if (reinsn_list.is_empty ()) 1184 state.modified = NULL; 1185 else 1186 state.modified = XCNEWVEC (struct ext_modified, max_insn_uid); 1187 1188 FOR_EACH_VEC_ELT (reinsn_list, i, curr_cand) 1189 { 1190 num_re_opportunities++; 1191 1192 /* Try to combine the extension with the definition. */ 1193 if (dump_file) 1194 { 1195 fprintf (dump_file, "Trying to eliminate extension:\n"); 1196 print_rtl_single (dump_file, curr_cand->insn); 1197 } 1198 1199 if (combine_reaching_defs (curr_cand, curr_cand->expr, &state)) 1200 { 1201 if (dump_file) 1202 fprintf (dump_file, "Eliminated the extension.\n"); 1203 num_realized++; 1204 /* If the RHS of the current candidate is not (extend (reg)), then 1205 we do not allow the optimization of extensions where 1206 the source and destination registers do not match. Thus 1207 checking REG_P here is correct. */ 1208 if (REG_P (XEXP (SET_SRC (PATTERN (curr_cand->insn)), 0)) 1209 && (REGNO (SET_DEST (PATTERN (curr_cand->insn))) 1210 != REGNO (XEXP (SET_SRC (PATTERN (curr_cand->insn)), 0)))) 1211 { 1212 reinsn_copy_list.safe_push (curr_cand->insn); 1213 reinsn_copy_list.safe_push (state.defs_list[0]); 1214 } 1215 reinsn_del_list.safe_push (curr_cand->insn); 1216 state.modified[INSN_UID (curr_cand->insn)].deleted = 1; 1217 } 1218 } 1219 1220 /* The copy list contains pairs of insns which describe copies we 1221 need to insert into the INSN stream. 1222 1223 The first insn in each pair is the extension insn, from which 1224 we derive the source and destination of the copy. 1225 1226 The second insn in each pair is the memory reference where the 1227 extension will ultimately happen. We emit the new copy 1228 immediately after this insn. 1229 1230 It may first appear that the arguments for the copy are reversed. 1231 Remember that the memory reference will be changed to refer to the 1232 destination of the extention. So we're actually emitting a copy 1233 from the new destination to the old destination. */ 1234 for (unsigned int i = 0; i < reinsn_copy_list.length (); i += 2) 1235 { 1236 rtx_insn *curr_insn = reinsn_copy_list[i]; 1237 rtx_insn *def_insn = reinsn_copy_list[i + 1]; 1238 1239 /* Use the mode of the destination of the defining insn 1240 for the mode of the copy. This is necessary if the 1241 defining insn was used to eliminate a second extension 1242 that was wider than the first. */ 1243 rtx sub_rtx = *get_sub_rtx (def_insn); 1244 rtx pat = PATTERN (curr_insn); 1245 rtx new_dst = gen_rtx_REG (GET_MODE (SET_DEST (sub_rtx)), 1246 REGNO (XEXP (SET_SRC (pat), 0))); 1247 rtx new_src = gen_rtx_REG (GET_MODE (SET_DEST (sub_rtx)), 1248 REGNO (SET_DEST (pat))); 1249 rtx set = gen_rtx_SET (VOIDmode, new_dst, new_src); 1250 emit_insn_after (set, def_insn); 1251 } 1252 1253 /* Delete all useless extensions here in one sweep. */ 1254 FOR_EACH_VEC_ELT (reinsn_del_list, i, curr_insn) 1255 delete_insn (curr_insn); 1256 1257 reinsn_list.release (); 1258 state.defs_list.release (); 1259 state.copies_list.release (); 1260 state.modified_list.release (); 1261 state.work_list.release (); 1262 XDELETEVEC (state.modified); 1263 1264 if (dump_file && num_re_opportunities > 0) 1265 fprintf (dump_file, "Elimination opportunities = %d realized = %d\n", 1266 num_re_opportunities, num_realized); 1267 } 1268 1269 /* Find and remove redundant extensions. */ 1270 1271 static unsigned int 1272 rest_of_handle_ree (void) 1273 { 1274 timevar_push (TV_REE); 1275 find_and_remove_re (); 1276 timevar_pop (TV_REE); 1277 return 0; 1278 } 1279 1280 namespace { 1281 1282 const pass_data pass_data_ree = 1283 { 1284 RTL_PASS, /* type */ 1285 "ree", /* name */ 1286 OPTGROUP_NONE, /* optinfo_flags */ 1287 TV_REE, /* tv_id */ 1288 0, /* properties_required */ 1289 0, /* properties_provided */ 1290 0, /* properties_destroyed */ 1291 0, /* todo_flags_start */ 1292 TODO_df_finish, /* todo_flags_finish */ 1293 }; 1294 1295 class pass_ree : public rtl_opt_pass 1296 { 1297 public: 1298 pass_ree (gcc::context *ctxt) 1299 : rtl_opt_pass (pass_data_ree, ctxt) 1300 {} 1301 1302 /* opt_pass methods: */ 1303 virtual bool gate (function *) { return (optimize > 0 && flag_ree); } 1304 virtual unsigned int execute (function *) { return rest_of_handle_ree (); } 1305 1306 }; // class pass_ree 1307 1308 } // anon namespace 1309 1310 rtl_opt_pass * 1311 make_pass_ree (gcc::context *ctxt) 1312 { 1313 return new pass_ree (ctxt); 1314 } 1315