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