1 /* RTL-based forward propagation pass for GNU compiler. 2 Copyright (C) 2005-2018 Free Software Foundation, Inc. 3 Contributed by Paolo Bonzini and Steven Bosscher. 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify it under 8 the terms of the GNU General Public License as published by the Free 9 Software Foundation; either version 3, or (at your option) any later 10 version. 11 12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13 WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 #include "config.h" 22 #include "system.h" 23 #include "coretypes.h" 24 #include "backend.h" 25 #include "target.h" 26 #include "rtl.h" 27 #include "predict.h" 28 #include "df.h" 29 #include "memmodel.h" 30 #include "tm_p.h" 31 #include "insn-config.h" 32 #include "emit-rtl.h" 33 #include "recog.h" 34 35 #include "sparseset.h" 36 #include "cfgrtl.h" 37 #include "cfgcleanup.h" 38 #include "cfgloop.h" 39 #include "tree-pass.h" 40 #include "domwalk.h" 41 #include "rtl-iter.h" 42 43 44 /* This pass does simple forward propagation and simplification when an 45 operand of an insn can only come from a single def. This pass uses 46 df.c, so it is global. However, we only do limited analysis of 47 available expressions. 48 49 1) The pass tries to propagate the source of the def into the use, 50 and checks if the result is independent of the substituted value. 51 For example, the high word of a (zero_extend:DI (reg:SI M)) is always 52 zero, independent of the source register. 53 54 In particular, we propagate constants into the use site. Sometimes 55 RTL expansion did not put the constant in the same insn on purpose, 56 to satisfy a predicate, and the result will fail to be recognized; 57 but this happens rarely and in this case we can still create a 58 REG_EQUAL note. For multi-word operations, this 59 60 (set (subreg:SI (reg:DI 120) 0) (const_int 0)) 61 (set (subreg:SI (reg:DI 120) 4) (const_int -1)) 62 (set (subreg:SI (reg:DI 122) 0) 63 (ior:SI (subreg:SI (reg:DI 119) 0) (subreg:SI (reg:DI 120) 0))) 64 (set (subreg:SI (reg:DI 122) 4) 65 (ior:SI (subreg:SI (reg:DI 119) 4) (subreg:SI (reg:DI 120) 4))) 66 67 can be simplified to the much simpler 68 69 (set (subreg:SI (reg:DI 122) 0) (subreg:SI (reg:DI 119))) 70 (set (subreg:SI (reg:DI 122) 4) (const_int -1)) 71 72 This particular propagation is also effective at putting together 73 complex addressing modes. We are more aggressive inside MEMs, in 74 that all definitions are propagated if the use is in a MEM; if the 75 result is a valid memory address we check address_cost to decide 76 whether the substitution is worthwhile. 77 78 2) The pass propagates register copies. This is not as effective as 79 the copy propagation done by CSE's canon_reg, which works by walking 80 the instruction chain, it can help the other transformations. 81 82 We should consider removing this optimization, and instead reorder the 83 RTL passes, because GCSE does this transformation too. With some luck, 84 the CSE pass at the end of rest_of_handle_gcse could also go away. 85 86 3) The pass looks for paradoxical subregs that are actually unnecessary. 87 Things like this: 88 89 (set (reg:QI 120) (subreg:QI (reg:SI 118) 0)) 90 (set (reg:QI 121) (subreg:QI (reg:SI 119) 0)) 91 (set (reg:SI 122) (plus:SI (subreg:SI (reg:QI 120) 0) 92 (subreg:SI (reg:QI 121) 0))) 93 94 are very common on machines that can only do word-sized operations. 95 For each use of a paradoxical subreg (subreg:WIDER (reg:NARROW N) 0), 96 if it has a single def and it is (subreg:NARROW (reg:WIDE M) 0), 97 we can replace the paradoxical subreg with simply (reg:WIDE M). The 98 above will simplify this to 99 100 (set (reg:QI 120) (subreg:QI (reg:SI 118) 0)) 101 (set (reg:QI 121) (subreg:QI (reg:SI 119) 0)) 102 (set (reg:SI 122) (plus:SI (reg:SI 118) (reg:SI 119))) 103 104 where the first two insns are now dead. 105 106 We used to use reaching definitions to find which uses have a 107 single reaching definition (sounds obvious...), but this is too 108 complex a problem in nasty testcases like PR33928. Now we use the 109 multiple definitions problem in df-problems.c. The similarity 110 between that problem and SSA form creation is taken further, in 111 that fwprop does a dominator walk to create its chains; however, 112 instead of creating a PHI function where multiple definitions meet 113 I just punt and record only singleton use-def chains, which is 114 all that is needed by fwprop. */ 115 116 117 static int num_changes; 118 119 static vec<df_ref> use_def_ref; 120 static vec<df_ref> reg_defs; 121 static vec<df_ref> reg_defs_stack; 122 123 /* The maximum number of propagations that are still allowed. If we do 124 more propagations than originally we had uses, we must have ended up 125 in a propagation loop, as in PR79405. Until the algorithm fwprop 126 uses can obviously not get into such loops we need a workaround like 127 this. */ 128 static int propagations_left; 129 130 /* The MD bitmaps are trimmed to include only live registers to cut 131 memory usage on testcases like insn-recog.c. Track live registers 132 in the basic block and do not perform forward propagation if the 133 destination is a dead pseudo occurring in a note. */ 134 static bitmap local_md; 135 static bitmap local_lr; 136 137 /* Return the only def in USE's use-def chain, or NULL if there is 138 more than one def in the chain. */ 139 140 static inline df_ref 141 get_def_for_use (df_ref use) 142 { 143 return use_def_ref[DF_REF_ID (use)]; 144 } 145 146 147 /* Update the reg_defs vector with non-partial definitions in DEF_REC. 148 TOP_FLAG says which artificials uses should be used, when DEF_REC 149 is an artificial def vector. LOCAL_MD is modified as after a 150 df_md_simulate_* function; we do more or less the same processing 151 done there, so we do not use those functions. */ 152 153 #define DF_MD_GEN_FLAGS \ 154 (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER) 155 156 static void 157 process_defs (df_ref def, int top_flag) 158 { 159 for (; def; def = DF_REF_NEXT_LOC (def)) 160 { 161 df_ref curr_def = reg_defs[DF_REF_REGNO (def)]; 162 unsigned int dregno; 163 164 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) != top_flag) 165 continue; 166 167 dregno = DF_REF_REGNO (def); 168 if (curr_def) 169 reg_defs_stack.safe_push (curr_def); 170 else 171 { 172 /* Do not store anything if "transitioning" from NULL to NULL. But 173 otherwise, push a special entry on the stack to tell the 174 leave_block callback that the entry in reg_defs was NULL. */ 175 if (DF_REF_FLAGS (def) & DF_MD_GEN_FLAGS) 176 ; 177 else 178 reg_defs_stack.safe_push (def); 179 } 180 181 if (DF_REF_FLAGS (def) & DF_MD_GEN_FLAGS) 182 { 183 bitmap_set_bit (local_md, dregno); 184 reg_defs[dregno] = NULL; 185 } 186 else 187 { 188 bitmap_clear_bit (local_md, dregno); 189 reg_defs[dregno] = def; 190 } 191 } 192 } 193 194 195 /* Fill the use_def_ref vector with values for the uses in USE_REC, 196 taking reaching definitions info from LOCAL_MD and REG_DEFS. 197 TOP_FLAG says which artificials uses should be used, when USE_REC 198 is an artificial use vector. */ 199 200 static void 201 process_uses (df_ref use, int top_flag) 202 { 203 for (; use; use = DF_REF_NEXT_LOC (use)) 204 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == top_flag) 205 { 206 unsigned int uregno = DF_REF_REGNO (use); 207 if (reg_defs[uregno] 208 && !bitmap_bit_p (local_md, uregno) 209 && bitmap_bit_p (local_lr, uregno)) 210 use_def_ref[DF_REF_ID (use)] = reg_defs[uregno]; 211 } 212 } 213 214 class single_def_use_dom_walker : public dom_walker 215 { 216 public: 217 single_def_use_dom_walker (cdi_direction direction) 218 : dom_walker (direction) {} 219 virtual edge before_dom_children (basic_block); 220 virtual void after_dom_children (basic_block); 221 }; 222 223 edge 224 single_def_use_dom_walker::before_dom_children (basic_block bb) 225 { 226 int bb_index = bb->index; 227 struct df_md_bb_info *md_bb_info = df_md_get_bb_info (bb_index); 228 struct df_lr_bb_info *lr_bb_info = df_lr_get_bb_info (bb_index); 229 rtx_insn *insn; 230 231 bitmap_copy (local_md, &md_bb_info->in); 232 bitmap_copy (local_lr, &lr_bb_info->in); 233 234 /* Push a marker for the leave_block callback. */ 235 reg_defs_stack.safe_push (NULL); 236 237 process_uses (df_get_artificial_uses (bb_index), DF_REF_AT_TOP); 238 process_defs (df_get_artificial_defs (bb_index), DF_REF_AT_TOP); 239 240 /* We don't call df_simulate_initialize_forwards, as it may overestimate 241 the live registers if there are unused artificial defs. We prefer 242 liveness to be underestimated. */ 243 244 FOR_BB_INSNS (bb, insn) 245 if (INSN_P (insn)) 246 { 247 unsigned int uid = INSN_UID (insn); 248 process_uses (DF_INSN_UID_USES (uid), 0); 249 process_uses (DF_INSN_UID_EQ_USES (uid), 0); 250 process_defs (DF_INSN_UID_DEFS (uid), 0); 251 df_simulate_one_insn_forwards (bb, insn, local_lr); 252 } 253 254 process_uses (df_get_artificial_uses (bb_index), 0); 255 process_defs (df_get_artificial_defs (bb_index), 0); 256 257 return NULL; 258 } 259 260 /* Pop the definitions created in this basic block when leaving its 261 dominated parts. */ 262 263 void 264 single_def_use_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED) 265 { 266 df_ref saved_def; 267 while ((saved_def = reg_defs_stack.pop ()) != NULL) 268 { 269 unsigned int dregno = DF_REF_REGNO (saved_def); 270 271 /* See also process_defs. */ 272 if (saved_def == reg_defs[dregno]) 273 reg_defs[dregno] = NULL; 274 else 275 reg_defs[dregno] = saved_def; 276 } 277 } 278 279 280 /* Build a vector holding the reaching definitions of uses reached by a 281 single dominating definition. */ 282 283 static void 284 build_single_def_use_links (void) 285 { 286 /* We use the multiple definitions problem to compute our restricted 287 use-def chains. */ 288 df_set_flags (DF_EQ_NOTES); 289 df_md_add_problem (); 290 df_note_add_problem (); 291 df_analyze (); 292 df_maybe_reorganize_use_refs (DF_REF_ORDER_BY_INSN_WITH_NOTES); 293 294 use_def_ref.create (DF_USES_TABLE_SIZE ()); 295 use_def_ref.safe_grow_cleared (DF_USES_TABLE_SIZE ()); 296 297 reg_defs.create (max_reg_num ()); 298 reg_defs.safe_grow_cleared (max_reg_num ()); 299 300 reg_defs_stack.create (n_basic_blocks_for_fn (cfun) * 10); 301 local_md = BITMAP_ALLOC (NULL); 302 local_lr = BITMAP_ALLOC (NULL); 303 304 /* Walk the dominator tree looking for single reaching definitions 305 dominating the uses. This is similar to how SSA form is built. */ 306 single_def_use_dom_walker (CDI_DOMINATORS) 307 .walk (cfun->cfg->x_entry_block_ptr); 308 309 BITMAP_FREE (local_lr); 310 BITMAP_FREE (local_md); 311 reg_defs.release (); 312 reg_defs_stack.release (); 313 } 314 315 316 /* Do not try to replace constant addresses or addresses of local and 317 argument slots. These MEM expressions are made only once and inserted 318 in many instructions, as well as being used to control symbol table 319 output. It is not safe to clobber them. 320 321 There are some uncommon cases where the address is already in a register 322 for some reason, but we cannot take advantage of that because we have 323 no easy way to unshare the MEM. In addition, looking up all stack 324 addresses is costly. */ 325 326 static bool 327 can_simplify_addr (rtx addr) 328 { 329 rtx reg; 330 331 if (CONSTANT_ADDRESS_P (addr)) 332 return false; 333 334 if (GET_CODE (addr) == PLUS) 335 reg = XEXP (addr, 0); 336 else 337 reg = addr; 338 339 return (!REG_P (reg) 340 || (REGNO (reg) != FRAME_POINTER_REGNUM 341 && REGNO (reg) != HARD_FRAME_POINTER_REGNUM 342 && REGNO (reg) != ARG_POINTER_REGNUM)); 343 } 344 345 /* Returns a canonical version of X for the address, from the point of view, 346 that all multiplications are represented as MULT instead of the multiply 347 by a power of 2 being represented as ASHIFT. 348 349 Every ASHIFT we find has been made by simplify_gen_binary and was not 350 there before, so it is not shared. So we can do this in place. */ 351 352 static void 353 canonicalize_address (rtx x) 354 { 355 for (;;) 356 switch (GET_CODE (x)) 357 { 358 case ASHIFT: 359 if (CONST_INT_P (XEXP (x, 1)) 360 && INTVAL (XEXP (x, 1)) < GET_MODE_UNIT_BITSIZE (GET_MODE (x)) 361 && INTVAL (XEXP (x, 1)) >= 0) 362 { 363 HOST_WIDE_INT shift = INTVAL (XEXP (x, 1)); 364 PUT_CODE (x, MULT); 365 XEXP (x, 1) = gen_int_mode (HOST_WIDE_INT_1 << shift, 366 GET_MODE (x)); 367 } 368 369 x = XEXP (x, 0); 370 break; 371 372 case PLUS: 373 if (GET_CODE (XEXP (x, 0)) == PLUS 374 || GET_CODE (XEXP (x, 0)) == ASHIFT 375 || GET_CODE (XEXP (x, 0)) == CONST) 376 canonicalize_address (XEXP (x, 0)); 377 378 x = XEXP (x, 1); 379 break; 380 381 case CONST: 382 x = XEXP (x, 0); 383 break; 384 385 default: 386 return; 387 } 388 } 389 390 /* OLD is a memory address. Return whether it is good to use NEW instead, 391 for a memory access in the given MODE. */ 392 393 static bool 394 should_replace_address (rtx old_rtx, rtx new_rtx, machine_mode mode, 395 addr_space_t as, bool speed) 396 { 397 int gain; 398 399 if (rtx_equal_p (old_rtx, new_rtx) 400 || !memory_address_addr_space_p (mode, new_rtx, as)) 401 return false; 402 403 /* Copy propagation is always ok. */ 404 if (REG_P (old_rtx) && REG_P (new_rtx)) 405 return true; 406 407 /* Prefer the new address if it is less expensive. */ 408 gain = (address_cost (old_rtx, mode, as, speed) 409 - address_cost (new_rtx, mode, as, speed)); 410 411 /* If the addresses have equivalent cost, prefer the new address 412 if it has the highest `set_src_cost'. That has the potential of 413 eliminating the most insns without additional costs, and it 414 is the same that cse.c used to do. */ 415 if (gain == 0) 416 gain = (set_src_cost (new_rtx, VOIDmode, speed) 417 - set_src_cost (old_rtx, VOIDmode, speed)); 418 419 return (gain > 0); 420 } 421 422 423 /* Flags for the last parameter of propagate_rtx_1. */ 424 425 enum { 426 /* If PR_CAN_APPEAR is true, propagate_rtx_1 always returns true; 427 if it is false, propagate_rtx_1 returns false if, for at least 428 one occurrence OLD, it failed to collapse the result to a constant. 429 For example, (mult:M (reg:M A) (minus:M (reg:M B) (reg:M A))) may 430 collapse to zero if replacing (reg:M B) with (reg:M A). 431 432 PR_CAN_APPEAR is disregarded inside MEMs: in that case, 433 propagate_rtx_1 just tries to make cheaper and valid memory 434 addresses. */ 435 PR_CAN_APPEAR = 1, 436 437 /* If PR_HANDLE_MEM is not set, propagate_rtx_1 won't attempt any replacement 438 outside memory addresses. This is needed because propagate_rtx_1 does 439 not do any analysis on memory; thus it is very conservative and in general 440 it will fail if non-read-only MEMs are found in the source expression. 441 442 PR_HANDLE_MEM is set when the source of the propagation was not 443 another MEM. Then, it is safe not to treat non-read-only MEMs as 444 ``opaque'' objects. */ 445 PR_HANDLE_MEM = 2, 446 447 /* Set when costs should be optimized for speed. */ 448 PR_OPTIMIZE_FOR_SPEED = 4 449 }; 450 451 452 /* Replace all occurrences of OLD in *PX with NEW and try to simplify the 453 resulting expression. Replace *PX with a new RTL expression if an 454 occurrence of OLD was found. 455 456 This is only a wrapper around simplify-rtx.c: do not add any pattern 457 matching code here. (The sole exception is the handling of LO_SUM, but 458 that is because there is no simplify_gen_* function for LO_SUM). */ 459 460 static bool 461 propagate_rtx_1 (rtx *px, rtx old_rtx, rtx new_rtx, int flags) 462 { 463 rtx x = *px, tem = NULL_RTX, op0, op1, op2; 464 enum rtx_code code = GET_CODE (x); 465 machine_mode mode = GET_MODE (x); 466 machine_mode op_mode; 467 bool can_appear = (flags & PR_CAN_APPEAR) != 0; 468 bool valid_ops = true; 469 470 if (!(flags & PR_HANDLE_MEM) && MEM_P (x) && !MEM_READONLY_P (x)) 471 { 472 /* If unsafe, change MEMs to CLOBBERs or SCRATCHes (to preserve whether 473 they have side effects or not). */ 474 *px = (side_effects_p (x) 475 ? gen_rtx_CLOBBER (GET_MODE (x), const0_rtx) 476 : gen_rtx_SCRATCH (GET_MODE (x))); 477 return false; 478 } 479 480 /* If X is OLD_RTX, return NEW_RTX. But not if replacing only within an 481 address, and we are *not* inside one. */ 482 if (x == old_rtx) 483 { 484 *px = new_rtx; 485 return can_appear; 486 } 487 488 /* If this is an expression, try recursive substitution. */ 489 switch (GET_RTX_CLASS (code)) 490 { 491 case RTX_UNARY: 492 op0 = XEXP (x, 0); 493 op_mode = GET_MODE (op0); 494 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags); 495 if (op0 == XEXP (x, 0)) 496 return true; 497 tem = simplify_gen_unary (code, mode, op0, op_mode); 498 break; 499 500 case RTX_BIN_ARITH: 501 case RTX_COMM_ARITH: 502 op0 = XEXP (x, 0); 503 op1 = XEXP (x, 1); 504 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags); 505 valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags); 506 if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1)) 507 return true; 508 tem = simplify_gen_binary (code, mode, op0, op1); 509 break; 510 511 case RTX_COMPARE: 512 case RTX_COMM_COMPARE: 513 op0 = XEXP (x, 0); 514 op1 = XEXP (x, 1); 515 op_mode = GET_MODE (op0) != VOIDmode ? GET_MODE (op0) : GET_MODE (op1); 516 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags); 517 valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags); 518 if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1)) 519 return true; 520 tem = simplify_gen_relational (code, mode, op_mode, op0, op1); 521 break; 522 523 case RTX_TERNARY: 524 case RTX_BITFIELD_OPS: 525 op0 = XEXP (x, 0); 526 op1 = XEXP (x, 1); 527 op2 = XEXP (x, 2); 528 op_mode = GET_MODE (op0); 529 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags); 530 valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags); 531 valid_ops &= propagate_rtx_1 (&op2, old_rtx, new_rtx, flags); 532 if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1) && op2 == XEXP (x, 2)) 533 return true; 534 if (op_mode == VOIDmode) 535 op_mode = GET_MODE (op0); 536 tem = simplify_gen_ternary (code, mode, op_mode, op0, op1, op2); 537 break; 538 539 case RTX_EXTRA: 540 /* The only case we try to handle is a SUBREG. */ 541 if (code == SUBREG) 542 { 543 op0 = XEXP (x, 0); 544 valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags); 545 if (op0 == XEXP (x, 0)) 546 return true; 547 tem = simplify_gen_subreg (mode, op0, GET_MODE (SUBREG_REG (x)), 548 SUBREG_BYTE (x)); 549 } 550 break; 551 552 case RTX_OBJ: 553 if (code == MEM && x != new_rtx) 554 { 555 rtx new_op0; 556 op0 = XEXP (x, 0); 557 558 /* There are some addresses that we cannot work on. */ 559 if (!can_simplify_addr (op0)) 560 return true; 561 562 op0 = new_op0 = targetm.delegitimize_address (op0); 563 valid_ops &= propagate_rtx_1 (&new_op0, old_rtx, new_rtx, 564 flags | PR_CAN_APPEAR); 565 566 /* Dismiss transformation that we do not want to carry on. */ 567 if (!valid_ops 568 || new_op0 == op0 569 || !(GET_MODE (new_op0) == GET_MODE (op0) 570 || GET_MODE (new_op0) == VOIDmode)) 571 return true; 572 573 canonicalize_address (new_op0); 574 575 /* Copy propagations are always ok. Otherwise check the costs. */ 576 if (!(REG_P (old_rtx) && REG_P (new_rtx)) 577 && !should_replace_address (op0, new_op0, GET_MODE (x), 578 MEM_ADDR_SPACE (x), 579 flags & PR_OPTIMIZE_FOR_SPEED)) 580 return true; 581 582 tem = replace_equiv_address_nv (x, new_op0); 583 } 584 585 else if (code == LO_SUM) 586 { 587 op0 = XEXP (x, 0); 588 op1 = XEXP (x, 1); 589 590 /* The only simplification we do attempts to remove references to op0 591 or make it constant -- in both cases, op0's invalidity will not 592 make the result invalid. */ 593 propagate_rtx_1 (&op0, old_rtx, new_rtx, flags | PR_CAN_APPEAR); 594 valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags); 595 if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1)) 596 return true; 597 598 /* (lo_sum (high x) x) -> x */ 599 if (GET_CODE (op0) == HIGH && rtx_equal_p (XEXP (op0, 0), op1)) 600 tem = op1; 601 else 602 tem = gen_rtx_LO_SUM (mode, op0, op1); 603 604 /* OP1 is likely not a legitimate address, otherwise there would have 605 been no LO_SUM. We want it to disappear if it is invalid, return 606 false in that case. */ 607 return memory_address_p (mode, tem); 608 } 609 610 else if (code == REG) 611 { 612 if (rtx_equal_p (x, old_rtx)) 613 { 614 *px = new_rtx; 615 return can_appear; 616 } 617 } 618 break; 619 620 default: 621 break; 622 } 623 624 /* No change, no trouble. */ 625 if (tem == NULL_RTX) 626 return true; 627 628 *px = tem; 629 630 /* Allow replacements that simplify operations on a vector or complex 631 value to a component. The most prominent case is 632 (subreg ([vec_]concat ...)). */ 633 if (REG_P (tem) && !HARD_REGISTER_P (tem) 634 && (VECTOR_MODE_P (GET_MODE (new_rtx)) 635 || COMPLEX_MODE_P (GET_MODE (new_rtx))) 636 && GET_MODE (tem) == GET_MODE_INNER (GET_MODE (new_rtx))) 637 return true; 638 639 /* The replacement we made so far is valid, if all of the recursive 640 replacements were valid, or we could simplify everything to 641 a constant. */ 642 return valid_ops || can_appear || CONSTANT_P (tem); 643 } 644 645 646 /* Return true if X constains a non-constant mem. */ 647 648 static bool 649 varying_mem_p (const_rtx x) 650 { 651 subrtx_iterator::array_type array; 652 FOR_EACH_SUBRTX (iter, array, x, NONCONST) 653 if (MEM_P (*iter) && !MEM_READONLY_P (*iter)) 654 return true; 655 return false; 656 } 657 658 659 /* Replace all occurrences of OLD in X with NEW and try to simplify the 660 resulting expression (in mode MODE). Return a new expression if it is 661 a constant, otherwise X. 662 663 Simplifications where occurrences of NEW collapse to a constant are always 664 accepted. All simplifications are accepted if NEW is a pseudo too. 665 Otherwise, we accept simplifications that have a lower or equal cost. */ 666 667 static rtx 668 propagate_rtx (rtx x, machine_mode mode, rtx old_rtx, rtx new_rtx, 669 bool speed) 670 { 671 rtx tem; 672 bool collapsed; 673 int flags; 674 675 if (REG_P (new_rtx) && REGNO (new_rtx) < FIRST_PSEUDO_REGISTER) 676 return NULL_RTX; 677 678 flags = 0; 679 if (REG_P (new_rtx) 680 || CONSTANT_P (new_rtx) 681 || (GET_CODE (new_rtx) == SUBREG 682 && REG_P (SUBREG_REG (new_rtx)) 683 && !paradoxical_subreg_p (mode, GET_MODE (SUBREG_REG (new_rtx))))) 684 flags |= PR_CAN_APPEAR; 685 if (!varying_mem_p (new_rtx)) 686 flags |= PR_HANDLE_MEM; 687 688 if (speed) 689 flags |= PR_OPTIMIZE_FOR_SPEED; 690 691 tem = x; 692 collapsed = propagate_rtx_1 (&tem, old_rtx, copy_rtx (new_rtx), flags); 693 if (tem == x || !collapsed) 694 return NULL_RTX; 695 696 /* gen_lowpart_common will not be able to process VOIDmode entities other 697 than CONST_INTs. */ 698 if (GET_MODE (tem) == VOIDmode && !CONST_INT_P (tem)) 699 return NULL_RTX; 700 701 if (GET_MODE (tem) == VOIDmode) 702 tem = rtl_hooks.gen_lowpart_no_emit (mode, tem); 703 else 704 gcc_assert (GET_MODE (tem) == mode); 705 706 return tem; 707 } 708 709 710 711 712 /* Return true if the register from reference REF is killed 713 between FROM to (but not including) TO. */ 714 715 static bool 716 local_ref_killed_between_p (df_ref ref, rtx_insn *from, rtx_insn *to) 717 { 718 rtx_insn *insn; 719 720 for (insn = from; insn != to; insn = NEXT_INSN (insn)) 721 { 722 df_ref def; 723 if (!INSN_P (insn)) 724 continue; 725 726 FOR_EACH_INSN_DEF (def, insn) 727 if (DF_REF_REGNO (ref) == DF_REF_REGNO (def)) 728 return true; 729 } 730 return false; 731 } 732 733 734 /* Check if the given DEF is available in INSN. This would require full 735 computation of available expressions; we check only restricted conditions: 736 - if DEF is the sole definition of its register, go ahead; 737 - in the same basic block, we check for no definitions killing the 738 definition of DEF_INSN; 739 - if USE's basic block has DEF's basic block as the sole predecessor, 740 we check if the definition is killed after DEF_INSN or before 741 TARGET_INSN insn, in their respective basic blocks. */ 742 static bool 743 use_killed_between (df_ref use, rtx_insn *def_insn, rtx_insn *target_insn) 744 { 745 basic_block def_bb = BLOCK_FOR_INSN (def_insn); 746 basic_block target_bb = BLOCK_FOR_INSN (target_insn); 747 int regno; 748 df_ref def; 749 750 /* We used to have a def reaching a use that is _before_ the def, 751 with the def not dominating the use even though the use and def 752 are in the same basic block, when a register may be used 753 uninitialized in a loop. This should not happen anymore since 754 we do not use reaching definitions, but still we test for such 755 cases and assume that DEF is not available. */ 756 if (def_bb == target_bb 757 ? DF_INSN_LUID (def_insn) >= DF_INSN_LUID (target_insn) 758 : !dominated_by_p (CDI_DOMINATORS, target_bb, def_bb)) 759 return true; 760 761 /* Check if the reg in USE has only one definition. We already 762 know that this definition reaches use, or we wouldn't be here. 763 However, this is invalid for hard registers because if they are 764 live at the beginning of the function it does not mean that we 765 have an uninitialized access. */ 766 regno = DF_REF_REGNO (use); 767 def = DF_REG_DEF_CHAIN (regno); 768 if (def 769 && DF_REF_NEXT_REG (def) == NULL 770 && regno >= FIRST_PSEUDO_REGISTER) 771 return false; 772 773 /* Check locally if we are in the same basic block. */ 774 if (def_bb == target_bb) 775 return local_ref_killed_between_p (use, def_insn, target_insn); 776 777 /* Finally, if DEF_BB is the sole predecessor of TARGET_BB. */ 778 if (single_pred_p (target_bb) 779 && single_pred (target_bb) == def_bb) 780 { 781 df_ref x; 782 783 /* See if USE is killed between DEF_INSN and the last insn in the 784 basic block containing DEF_INSN. */ 785 x = df_bb_regno_last_def_find (def_bb, regno); 786 if (x && DF_INSN_LUID (DF_REF_INSN (x)) >= DF_INSN_LUID (def_insn)) 787 return true; 788 789 /* See if USE is killed between TARGET_INSN and the first insn in the 790 basic block containing TARGET_INSN. */ 791 x = df_bb_regno_first_def_find (target_bb, regno); 792 if (x && DF_INSN_LUID (DF_REF_INSN (x)) < DF_INSN_LUID (target_insn)) 793 return true; 794 795 return false; 796 } 797 798 /* Otherwise assume the worst case. */ 799 return true; 800 } 801 802 803 /* Check if all uses in DEF_INSN can be used in TARGET_INSN. This 804 would require full computation of available expressions; 805 we check only restricted conditions, see use_killed_between. */ 806 static bool 807 all_uses_available_at (rtx_insn *def_insn, rtx_insn *target_insn) 808 { 809 df_ref use; 810 struct df_insn_info *insn_info = DF_INSN_INFO_GET (def_insn); 811 rtx def_set = single_set (def_insn); 812 rtx_insn *next; 813 814 gcc_assert (def_set); 815 816 /* If target_insn comes right after def_insn, which is very common 817 for addresses, we can use a quicker test. Ignore debug insns 818 other than target insns for this. */ 819 next = NEXT_INSN (def_insn); 820 while (next && next != target_insn && DEBUG_INSN_P (next)) 821 next = NEXT_INSN (next); 822 if (next == target_insn && REG_P (SET_DEST (def_set))) 823 { 824 rtx def_reg = SET_DEST (def_set); 825 826 /* If the insn uses the reg that it defines, the substitution is 827 invalid. */ 828 FOR_EACH_INSN_INFO_USE (use, insn_info) 829 if (rtx_equal_p (DF_REF_REG (use), def_reg)) 830 return false; 831 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info) 832 if (rtx_equal_p (DF_REF_REG (use), def_reg)) 833 return false; 834 } 835 else 836 { 837 rtx def_reg = REG_P (SET_DEST (def_set)) ? SET_DEST (def_set) : NULL_RTX; 838 839 /* Look at all the uses of DEF_INSN, and see if they are not 840 killed between DEF_INSN and TARGET_INSN. */ 841 FOR_EACH_INSN_INFO_USE (use, insn_info) 842 { 843 if (def_reg && rtx_equal_p (DF_REF_REG (use), def_reg)) 844 return false; 845 if (use_killed_between (use, def_insn, target_insn)) 846 return false; 847 } 848 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info) 849 { 850 if (def_reg && rtx_equal_p (DF_REF_REG (use), def_reg)) 851 return false; 852 if (use_killed_between (use, def_insn, target_insn)) 853 return false; 854 } 855 } 856 857 return true; 858 } 859 860 861 static df_ref *active_defs; 862 static sparseset active_defs_check; 863 864 /* Fill the ACTIVE_DEFS array with the use->def link for the registers 865 mentioned in USE_REC. Register the valid entries in ACTIVE_DEFS_CHECK 866 too, for checking purposes. */ 867 868 static void 869 register_active_defs (df_ref use) 870 { 871 for (; use; use = DF_REF_NEXT_LOC (use)) 872 { 873 df_ref def = get_def_for_use (use); 874 int regno = DF_REF_REGNO (use); 875 876 if (flag_checking) 877 sparseset_set_bit (active_defs_check, regno); 878 active_defs[regno] = def; 879 } 880 } 881 882 883 /* Build the use->def links that we use to update the dataflow info 884 for new uses. Note that building the links is very cheap and if 885 it were done earlier, they could be used to rule out invalid 886 propagations (in addition to what is done in all_uses_available_at). 887 I'm not doing this yet, though. */ 888 889 static void 890 update_df_init (rtx_insn *def_insn, rtx_insn *insn) 891 { 892 if (flag_checking) 893 sparseset_clear (active_defs_check); 894 register_active_defs (DF_INSN_USES (def_insn)); 895 register_active_defs (DF_INSN_USES (insn)); 896 register_active_defs (DF_INSN_EQ_USES (insn)); 897 } 898 899 900 /* Update the USE_DEF_REF array for the given use, using the active definitions 901 in the ACTIVE_DEFS array to match pseudos to their def. */ 902 903 static inline void 904 update_uses (df_ref use) 905 { 906 for (; use; use = DF_REF_NEXT_LOC (use)) 907 { 908 int regno = DF_REF_REGNO (use); 909 910 /* Set up the use-def chain. */ 911 if (DF_REF_ID (use) >= (int) use_def_ref.length ()) 912 use_def_ref.safe_grow_cleared (DF_REF_ID (use) + 1); 913 914 if (flag_checking) 915 gcc_assert (sparseset_bit_p (active_defs_check, regno)); 916 use_def_ref[DF_REF_ID (use)] = active_defs[regno]; 917 } 918 } 919 920 921 /* Update the USE_DEF_REF array for the uses in INSN. Only update note 922 uses if NOTES_ONLY is true. */ 923 924 static void 925 update_df (rtx_insn *insn, rtx note) 926 { 927 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn); 928 929 if (note) 930 { 931 df_uses_create (&XEXP (note, 0), insn, DF_REF_IN_NOTE); 932 df_notes_rescan (insn); 933 } 934 else 935 { 936 df_uses_create (&PATTERN (insn), insn, 0); 937 df_insn_rescan (insn); 938 update_uses (DF_INSN_INFO_USES (insn_info)); 939 } 940 941 update_uses (DF_INSN_INFO_EQ_USES (insn_info)); 942 } 943 944 945 /* Try substituting NEW into LOC, which originated from forward propagation 946 of USE's value from DEF_INSN. SET_REG_EQUAL says whether we are 947 substituting the whole SET_SRC, so we can set a REG_EQUAL note if the 948 new insn is not recognized. Return whether the substitution was 949 performed. */ 950 951 static bool 952 try_fwprop_subst (df_ref use, rtx *loc, rtx new_rtx, rtx_insn *def_insn, 953 bool set_reg_equal) 954 { 955 rtx_insn *insn = DF_REF_INSN (use); 956 rtx set = single_set (insn); 957 rtx note = NULL_RTX; 958 bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn)); 959 int old_cost = 0; 960 bool ok; 961 962 update_df_init (def_insn, insn); 963 964 /* forward_propagate_subreg may be operating on an instruction with 965 multiple sets. If so, assume the cost of the new instruction is 966 not greater than the old one. */ 967 if (set) 968 old_cost = set_src_cost (SET_SRC (set), GET_MODE (SET_DEST (set)), speed); 969 if (dump_file) 970 { 971 fprintf (dump_file, "\nIn insn %d, replacing\n ", INSN_UID (insn)); 972 print_inline_rtx (dump_file, *loc, 2); 973 fprintf (dump_file, "\n with "); 974 print_inline_rtx (dump_file, new_rtx, 2); 975 fprintf (dump_file, "\n"); 976 } 977 978 validate_unshare_change (insn, loc, new_rtx, true); 979 if (!verify_changes (0)) 980 { 981 if (dump_file) 982 fprintf (dump_file, "Changes to insn %d not recognized\n", 983 INSN_UID (insn)); 984 ok = false; 985 } 986 987 else if (DF_REF_TYPE (use) == DF_REF_REG_USE 988 && set 989 && (set_src_cost (SET_SRC (set), GET_MODE (SET_DEST (set)), speed) 990 > old_cost)) 991 { 992 if (dump_file) 993 fprintf (dump_file, "Changes to insn %d not profitable\n", 994 INSN_UID (insn)); 995 ok = false; 996 } 997 998 else 999 { 1000 if (dump_file) 1001 fprintf (dump_file, "Changed insn %d\n", INSN_UID (insn)); 1002 ok = true; 1003 } 1004 1005 if (ok) 1006 { 1007 confirm_change_group (); 1008 num_changes++; 1009 } 1010 else 1011 { 1012 cancel_changes (0); 1013 1014 /* Can also record a simplified value in a REG_EQUAL note, 1015 making a new one if one does not already exist. */ 1016 if (set_reg_equal) 1017 { 1018 /* If there are any paradoxical SUBREGs, don't add REG_EQUAL note, 1019 because the bits in there can be anything and so might not 1020 match the REG_EQUAL note content. See PR70574. */ 1021 subrtx_var_iterator::array_type array; 1022 FOR_EACH_SUBRTX_VAR (iter, array, *loc, NONCONST) 1023 { 1024 rtx x = *iter; 1025 if (SUBREG_P (x) && paradoxical_subreg_p (x)) 1026 { 1027 set_reg_equal = false; 1028 break; 1029 } 1030 } 1031 1032 if (set_reg_equal) 1033 { 1034 if (dump_file) 1035 fprintf (dump_file, " Setting REG_EQUAL note\n"); 1036 1037 note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (new_rtx)); 1038 } 1039 } 1040 } 1041 1042 if ((ok || note) && !CONSTANT_P (new_rtx)) 1043 update_df (insn, note); 1044 1045 return ok; 1046 } 1047 1048 /* For the given single_set INSN, containing SRC known to be a 1049 ZERO_EXTEND or SIGN_EXTEND of a register, return true if INSN 1050 is redundant due to the register being set by a LOAD_EXTEND_OP 1051 load from memory. */ 1052 1053 static bool 1054 free_load_extend (rtx src, rtx_insn *insn) 1055 { 1056 rtx reg; 1057 df_ref def, use; 1058 1059 reg = XEXP (src, 0); 1060 if (load_extend_op (GET_MODE (reg)) != GET_CODE (src)) 1061 return false; 1062 1063 FOR_EACH_INSN_USE (use, insn) 1064 if (!DF_REF_IS_ARTIFICIAL (use) 1065 && DF_REF_TYPE (use) == DF_REF_REG_USE 1066 && DF_REF_REG (use) == reg) 1067 break; 1068 if (!use) 1069 return false; 1070 1071 def = get_def_for_use (use); 1072 if (!def) 1073 return false; 1074 1075 if (DF_REF_IS_ARTIFICIAL (def)) 1076 return false; 1077 1078 if (NONJUMP_INSN_P (DF_REF_INSN (def))) 1079 { 1080 rtx patt = PATTERN (DF_REF_INSN (def)); 1081 1082 if (GET_CODE (patt) == SET 1083 && GET_CODE (SET_SRC (patt)) == MEM 1084 && rtx_equal_p (SET_DEST (patt), reg)) 1085 return true; 1086 } 1087 return false; 1088 } 1089 1090 /* If USE is a subreg, see if it can be replaced by a pseudo. */ 1091 1092 static bool 1093 forward_propagate_subreg (df_ref use, rtx_insn *def_insn, rtx def_set) 1094 { 1095 rtx use_reg = DF_REF_REG (use); 1096 rtx_insn *use_insn; 1097 rtx src; 1098 scalar_int_mode int_use_mode, src_mode; 1099 1100 /* Only consider subregs... */ 1101 machine_mode use_mode = GET_MODE (use_reg); 1102 if (GET_CODE (use_reg) != SUBREG 1103 || !REG_P (SET_DEST (def_set))) 1104 return false; 1105 1106 if (paradoxical_subreg_p (use_reg)) 1107 { 1108 /* If this is a paradoxical SUBREG, we have no idea what value the 1109 extra bits would have. However, if the operand is equivalent to 1110 a SUBREG whose operand is the same as our mode, and all the modes 1111 are within a word, we can just use the inner operand because 1112 these SUBREGs just say how to treat the register. */ 1113 use_insn = DF_REF_INSN (use); 1114 src = SET_SRC (def_set); 1115 if (GET_CODE (src) == SUBREG 1116 && REG_P (SUBREG_REG (src)) 1117 && REGNO (SUBREG_REG (src)) >= FIRST_PSEUDO_REGISTER 1118 && GET_MODE (SUBREG_REG (src)) == use_mode 1119 && subreg_lowpart_p (src) 1120 && all_uses_available_at (def_insn, use_insn)) 1121 return try_fwprop_subst (use, DF_REF_LOC (use), SUBREG_REG (src), 1122 def_insn, false); 1123 } 1124 1125 /* If this is a SUBREG of a ZERO_EXTEND or SIGN_EXTEND, and the SUBREG 1126 is the low part of the reg being extended then just use the inner 1127 operand. Don't do this if the ZERO_EXTEND or SIGN_EXTEND insn will 1128 be removed due to it matching a LOAD_EXTEND_OP load from memory, 1129 or due to the operation being a no-op when applied to registers. 1130 For example, if we have: 1131 1132 A: (set (reg:DI X) (sign_extend:DI (reg:SI Y))) 1133 B: (... (subreg:SI (reg:DI X)) ...) 1134 1135 and mode_rep_extended says that Y is already sign-extended, 1136 the backend will typically allow A to be combined with the 1137 definition of Y or, failing that, allow A to be deleted after 1138 reload through register tying. Introducing more uses of Y 1139 prevents both optimisations. */ 1140 else if (is_a <scalar_int_mode> (use_mode, &int_use_mode) 1141 && subreg_lowpart_p (use_reg)) 1142 { 1143 use_insn = DF_REF_INSN (use); 1144 src = SET_SRC (def_set); 1145 if ((GET_CODE (src) == ZERO_EXTEND 1146 || GET_CODE (src) == SIGN_EXTEND) 1147 && is_a <scalar_int_mode> (GET_MODE (src), &src_mode) 1148 && REG_P (XEXP (src, 0)) 1149 && REGNO (XEXP (src, 0)) >= FIRST_PSEUDO_REGISTER 1150 && GET_MODE (XEXP (src, 0)) == use_mode 1151 && !free_load_extend (src, def_insn) 1152 && (targetm.mode_rep_extended (int_use_mode, src_mode) 1153 != (int) GET_CODE (src)) 1154 && all_uses_available_at (def_insn, use_insn)) 1155 return try_fwprop_subst (use, DF_REF_LOC (use), XEXP (src, 0), 1156 def_insn, false); 1157 } 1158 1159 return false; 1160 } 1161 1162 /* Try to replace USE with SRC (defined in DEF_INSN) in __asm. */ 1163 1164 static bool 1165 forward_propagate_asm (df_ref use, rtx_insn *def_insn, rtx def_set, rtx reg) 1166 { 1167 rtx_insn *use_insn = DF_REF_INSN (use); 1168 rtx src, use_pat, asm_operands, new_rtx, *loc; 1169 int speed_p, i; 1170 df_ref uses; 1171 1172 gcc_assert ((DF_REF_FLAGS (use) & DF_REF_IN_NOTE) == 0); 1173 1174 src = SET_SRC (def_set); 1175 use_pat = PATTERN (use_insn); 1176 1177 /* In __asm don't replace if src might need more registers than 1178 reg, as that could increase register pressure on the __asm. */ 1179 uses = DF_INSN_USES (def_insn); 1180 if (uses && DF_REF_NEXT_LOC (uses)) 1181 return false; 1182 1183 update_df_init (def_insn, use_insn); 1184 speed_p = optimize_bb_for_speed_p (BLOCK_FOR_INSN (use_insn)); 1185 asm_operands = NULL_RTX; 1186 switch (GET_CODE (use_pat)) 1187 { 1188 case ASM_OPERANDS: 1189 asm_operands = use_pat; 1190 break; 1191 case SET: 1192 if (MEM_P (SET_DEST (use_pat))) 1193 { 1194 loc = &SET_DEST (use_pat); 1195 new_rtx = propagate_rtx (*loc, GET_MODE (*loc), reg, src, speed_p); 1196 if (new_rtx) 1197 validate_unshare_change (use_insn, loc, new_rtx, true); 1198 } 1199 asm_operands = SET_SRC (use_pat); 1200 break; 1201 case PARALLEL: 1202 for (i = 0; i < XVECLEN (use_pat, 0); i++) 1203 if (GET_CODE (XVECEXP (use_pat, 0, i)) == SET) 1204 { 1205 if (MEM_P (SET_DEST (XVECEXP (use_pat, 0, i)))) 1206 { 1207 loc = &SET_DEST (XVECEXP (use_pat, 0, i)); 1208 new_rtx = propagate_rtx (*loc, GET_MODE (*loc), reg, 1209 src, speed_p); 1210 if (new_rtx) 1211 validate_unshare_change (use_insn, loc, new_rtx, true); 1212 } 1213 asm_operands = SET_SRC (XVECEXP (use_pat, 0, i)); 1214 } 1215 else if (GET_CODE (XVECEXP (use_pat, 0, i)) == ASM_OPERANDS) 1216 asm_operands = XVECEXP (use_pat, 0, i); 1217 break; 1218 default: 1219 gcc_unreachable (); 1220 } 1221 1222 gcc_assert (asm_operands && GET_CODE (asm_operands) == ASM_OPERANDS); 1223 for (i = 0; i < ASM_OPERANDS_INPUT_LENGTH (asm_operands); i++) 1224 { 1225 loc = &ASM_OPERANDS_INPUT (asm_operands, i); 1226 new_rtx = propagate_rtx (*loc, GET_MODE (*loc), reg, src, speed_p); 1227 if (new_rtx) 1228 validate_unshare_change (use_insn, loc, new_rtx, true); 1229 } 1230 1231 if (num_changes_pending () == 0 || !apply_change_group ()) 1232 return false; 1233 1234 update_df (use_insn, NULL); 1235 num_changes++; 1236 return true; 1237 } 1238 1239 /* Try to replace USE with SRC (defined in DEF_INSN) and simplify the 1240 result. */ 1241 1242 static bool 1243 forward_propagate_and_simplify (df_ref use, rtx_insn *def_insn, rtx def_set) 1244 { 1245 rtx_insn *use_insn = DF_REF_INSN (use); 1246 rtx use_set = single_set (use_insn); 1247 rtx src, reg, new_rtx, *loc; 1248 bool set_reg_equal; 1249 machine_mode mode; 1250 int asm_use = -1; 1251 1252 if (INSN_CODE (use_insn) < 0) 1253 asm_use = asm_noperands (PATTERN (use_insn)); 1254 1255 if (!use_set && asm_use < 0 && !DEBUG_INSN_P (use_insn)) 1256 return false; 1257 1258 /* Do not propagate into PC, CC0, etc. */ 1259 if (use_set && GET_MODE (SET_DEST (use_set)) == VOIDmode) 1260 return false; 1261 1262 /* If def and use are subreg, check if they match. */ 1263 reg = DF_REF_REG (use); 1264 if (GET_CODE (reg) == SUBREG && GET_CODE (SET_DEST (def_set)) == SUBREG) 1265 { 1266 if (maybe_ne (SUBREG_BYTE (SET_DEST (def_set)), SUBREG_BYTE (reg))) 1267 return false; 1268 } 1269 /* Check if the def had a subreg, but the use has the whole reg. */ 1270 else if (REG_P (reg) && GET_CODE (SET_DEST (def_set)) == SUBREG) 1271 return false; 1272 /* Check if the use has a subreg, but the def had the whole reg. Unlike the 1273 previous case, the optimization is possible and often useful indeed. */ 1274 else if (GET_CODE (reg) == SUBREG && REG_P (SET_DEST (def_set))) 1275 reg = SUBREG_REG (reg); 1276 1277 /* Make sure that we can treat REG as having the same mode as the 1278 source of DEF_SET. */ 1279 if (GET_MODE (SET_DEST (def_set)) != GET_MODE (reg)) 1280 return false; 1281 1282 /* Check if the substitution is valid (last, because it's the most 1283 expensive check!). */ 1284 src = SET_SRC (def_set); 1285 if (!CONSTANT_P (src) && !all_uses_available_at (def_insn, use_insn)) 1286 return false; 1287 1288 /* Check if the def is loading something from the constant pool; in this 1289 case we would undo optimization such as compress_float_constant. 1290 Still, we can set a REG_EQUAL note. */ 1291 if (MEM_P (src) && MEM_READONLY_P (src)) 1292 { 1293 rtx x = avoid_constant_pool_reference (src); 1294 if (x != src && use_set) 1295 { 1296 rtx note = find_reg_note (use_insn, REG_EQUAL, NULL_RTX); 1297 rtx old_rtx = note ? XEXP (note, 0) : SET_SRC (use_set); 1298 rtx new_rtx = simplify_replace_rtx (old_rtx, src, x); 1299 if (old_rtx != new_rtx) 1300 set_unique_reg_note (use_insn, REG_EQUAL, copy_rtx (new_rtx)); 1301 } 1302 return false; 1303 } 1304 1305 if (asm_use >= 0) 1306 return forward_propagate_asm (use, def_insn, def_set, reg); 1307 1308 /* Else try simplifying. */ 1309 1310 if (DF_REF_TYPE (use) == DF_REF_REG_MEM_STORE) 1311 { 1312 loc = &SET_DEST (use_set); 1313 set_reg_equal = false; 1314 } 1315 else if (!use_set) 1316 { 1317 loc = &INSN_VAR_LOCATION_LOC (use_insn); 1318 set_reg_equal = false; 1319 } 1320 else 1321 { 1322 rtx note = find_reg_note (use_insn, REG_EQUAL, NULL_RTX); 1323 if (DF_REF_FLAGS (use) & DF_REF_IN_NOTE) 1324 loc = &XEXP (note, 0); 1325 else 1326 loc = &SET_SRC (use_set); 1327 1328 /* Do not replace an existing REG_EQUAL note if the insn is not 1329 recognized. Either we're already replacing in the note, or we'll 1330 separately try plugging the definition in the note and simplifying. 1331 And only install a REQ_EQUAL note when the destination is a REG 1332 that isn't mentioned in USE_SET, as the note would be invalid 1333 otherwise. We also don't want to install a note if we are merely 1334 propagating a pseudo since verifying that this pseudo isn't dead 1335 is a pain; moreover such a note won't help anything. 1336 If the use is a paradoxical subreg, make sure we don't add a 1337 REG_EQUAL note for it, because it is not equivalent, it is one 1338 possible value for it, but we can't rely on it holding that value. 1339 See PR70574. */ 1340 set_reg_equal = (note == NULL_RTX 1341 && REG_P (SET_DEST (use_set)) 1342 && !REG_P (src) 1343 && !(GET_CODE (src) == SUBREG 1344 && REG_P (SUBREG_REG (src))) 1345 && !reg_mentioned_p (SET_DEST (use_set), 1346 SET_SRC (use_set)) 1347 && !paradoxical_subreg_p (DF_REF_REG (use))); 1348 } 1349 1350 if (GET_MODE (*loc) == VOIDmode) 1351 mode = GET_MODE (SET_DEST (use_set)); 1352 else 1353 mode = GET_MODE (*loc); 1354 1355 new_rtx = propagate_rtx (*loc, mode, reg, src, 1356 optimize_bb_for_speed_p (BLOCK_FOR_INSN (use_insn))); 1357 1358 if (!new_rtx) 1359 return false; 1360 1361 return try_fwprop_subst (use, loc, new_rtx, def_insn, set_reg_equal); 1362 } 1363 1364 1365 /* Given a use USE of an insn, if it has a single reaching 1366 definition, try to forward propagate it into that insn. 1367 Return true if cfg cleanup will be needed. */ 1368 1369 static bool 1370 forward_propagate_into (df_ref use) 1371 { 1372 df_ref def; 1373 rtx_insn *def_insn, *use_insn; 1374 rtx def_set; 1375 rtx parent; 1376 1377 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE) 1378 return false; 1379 if (DF_REF_IS_ARTIFICIAL (use)) 1380 return false; 1381 1382 /* Only consider uses that have a single definition. */ 1383 def = get_def_for_use (use); 1384 if (!def) 1385 return false; 1386 if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE) 1387 return false; 1388 if (DF_REF_IS_ARTIFICIAL (def)) 1389 return false; 1390 1391 /* Do not propagate loop invariant definitions inside the loop. */ 1392 if (DF_REF_BB (def)->loop_father != DF_REF_BB (use)->loop_father) 1393 return false; 1394 1395 /* Check if the use is still present in the insn! */ 1396 use_insn = DF_REF_INSN (use); 1397 if (DF_REF_FLAGS (use) & DF_REF_IN_NOTE) 1398 parent = find_reg_note (use_insn, REG_EQUAL, NULL_RTX); 1399 else 1400 parent = PATTERN (use_insn); 1401 1402 if (!reg_mentioned_p (DF_REF_REG (use), parent)) 1403 return false; 1404 1405 def_insn = DF_REF_INSN (def); 1406 if (multiple_sets (def_insn)) 1407 return false; 1408 def_set = single_set (def_insn); 1409 if (!def_set) 1410 return false; 1411 1412 /* Only try one kind of propagation. If two are possible, we'll 1413 do it on the following iterations. */ 1414 if (forward_propagate_and_simplify (use, def_insn, def_set) 1415 || forward_propagate_subreg (use, def_insn, def_set)) 1416 { 1417 propagations_left--; 1418 1419 if (cfun->can_throw_non_call_exceptions 1420 && find_reg_note (use_insn, REG_EH_REGION, NULL_RTX) 1421 && purge_dead_edges (DF_REF_BB (use))) 1422 return true; 1423 } 1424 return false; 1425 } 1426 1427 1428 static void 1429 fwprop_init (void) 1430 { 1431 num_changes = 0; 1432 calculate_dominance_info (CDI_DOMINATORS); 1433 1434 /* We do not always want to propagate into loops, so we have to find 1435 loops and be careful about them. Avoid CFG modifications so that 1436 we don't have to update dominance information afterwards for 1437 build_single_def_use_links. */ 1438 loop_optimizer_init (AVOID_CFG_MODIFICATIONS); 1439 1440 build_single_def_use_links (); 1441 df_set_flags (DF_DEFER_INSN_RESCAN); 1442 1443 active_defs = XNEWVEC (df_ref, max_reg_num ()); 1444 if (flag_checking) 1445 active_defs_check = sparseset_alloc (max_reg_num ()); 1446 1447 propagations_left = DF_USES_TABLE_SIZE (); 1448 } 1449 1450 static void 1451 fwprop_done (void) 1452 { 1453 loop_optimizer_finalize (); 1454 1455 use_def_ref.release (); 1456 free (active_defs); 1457 if (flag_checking) 1458 sparseset_free (active_defs_check); 1459 1460 free_dominance_info (CDI_DOMINATORS); 1461 cleanup_cfg (0); 1462 delete_trivially_dead_insns (get_insns (), max_reg_num ()); 1463 1464 if (dump_file) 1465 fprintf (dump_file, 1466 "\nNumber of successful forward propagations: %d\n\n", 1467 num_changes); 1468 } 1469 1470 1471 /* Main entry point. */ 1472 1473 static bool 1474 gate_fwprop (void) 1475 { 1476 return optimize > 0 && flag_forward_propagate; 1477 } 1478 1479 static unsigned int 1480 fwprop (void) 1481 { 1482 unsigned i; 1483 1484 fwprop_init (); 1485 1486 /* Go through all the uses. df_uses_create will create new ones at the 1487 end, and we'll go through them as well. 1488 1489 Do not forward propagate addresses into loops until after unrolling. 1490 CSE did so because it was able to fix its own mess, but we are not. */ 1491 1492 for (i = 0; i < DF_USES_TABLE_SIZE (); i++) 1493 { 1494 if (!propagations_left) 1495 break; 1496 1497 df_ref use = DF_USES_GET (i); 1498 if (use) 1499 if (DF_REF_TYPE (use) == DF_REF_REG_USE 1500 || DF_REF_BB (use)->loop_father == NULL 1501 /* The outer most loop is not really a loop. */ 1502 || loop_outer (DF_REF_BB (use)->loop_father) == NULL) 1503 forward_propagate_into (use); 1504 } 1505 1506 fwprop_done (); 1507 return 0; 1508 } 1509 1510 namespace { 1511 1512 const pass_data pass_data_rtl_fwprop = 1513 { 1514 RTL_PASS, /* type */ 1515 "fwprop1", /* name */ 1516 OPTGROUP_NONE, /* optinfo_flags */ 1517 TV_FWPROP, /* tv_id */ 1518 0, /* properties_required */ 1519 0, /* properties_provided */ 1520 0, /* properties_destroyed */ 1521 0, /* todo_flags_start */ 1522 TODO_df_finish, /* todo_flags_finish */ 1523 }; 1524 1525 class pass_rtl_fwprop : public rtl_opt_pass 1526 { 1527 public: 1528 pass_rtl_fwprop (gcc::context *ctxt) 1529 : rtl_opt_pass (pass_data_rtl_fwprop, ctxt) 1530 {} 1531 1532 /* opt_pass methods: */ 1533 virtual bool gate (function *) { return gate_fwprop (); } 1534 virtual unsigned int execute (function *) { return fwprop (); } 1535 1536 }; // class pass_rtl_fwprop 1537 1538 } // anon namespace 1539 1540 rtl_opt_pass * 1541 make_pass_rtl_fwprop (gcc::context *ctxt) 1542 { 1543 return new pass_rtl_fwprop (ctxt); 1544 } 1545 1546 static unsigned int 1547 fwprop_addr (void) 1548 { 1549 unsigned i; 1550 1551 fwprop_init (); 1552 1553 /* Go through all the uses. df_uses_create will create new ones at the 1554 end, and we'll go through them as well. */ 1555 for (i = 0; i < DF_USES_TABLE_SIZE (); i++) 1556 { 1557 if (!propagations_left) 1558 break; 1559 1560 df_ref use = DF_USES_GET (i); 1561 if (use) 1562 if (DF_REF_TYPE (use) != DF_REF_REG_USE 1563 && DF_REF_BB (use)->loop_father != NULL 1564 /* The outer most loop is not really a loop. */ 1565 && loop_outer (DF_REF_BB (use)->loop_father) != NULL) 1566 forward_propagate_into (use); 1567 } 1568 1569 fwprop_done (); 1570 return 0; 1571 } 1572 1573 namespace { 1574 1575 const pass_data pass_data_rtl_fwprop_addr = 1576 { 1577 RTL_PASS, /* type */ 1578 "fwprop2", /* name */ 1579 OPTGROUP_NONE, /* optinfo_flags */ 1580 TV_FWPROP, /* tv_id */ 1581 0, /* properties_required */ 1582 0, /* properties_provided */ 1583 0, /* properties_destroyed */ 1584 0, /* todo_flags_start */ 1585 TODO_df_finish, /* todo_flags_finish */ 1586 }; 1587 1588 class pass_rtl_fwprop_addr : public rtl_opt_pass 1589 { 1590 public: 1591 pass_rtl_fwprop_addr (gcc::context *ctxt) 1592 : rtl_opt_pass (pass_data_rtl_fwprop_addr, ctxt) 1593 {} 1594 1595 /* opt_pass methods: */ 1596 virtual bool gate (function *) { return gate_fwprop (); } 1597 virtual unsigned int execute (function *) { return fwprop_addr (); } 1598 1599 }; // class pass_rtl_fwprop_addr 1600 1601 } // anon namespace 1602 1603 rtl_opt_pass * 1604 make_pass_rtl_fwprop_addr (gcc::context *ctxt) 1605 { 1606 return new pass_rtl_fwprop_addr (ctxt); 1607 } 1608