flow.c revision 146895
1/* Data flow analysis for GNU compiler. 2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 3 1999, 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc. 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 2, 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 COPYING. If not, write to the Free 19Software Foundation, 59 Temple Place - Suite 330, Boston, MA 2002111-1307, USA. */ 21 22/* This file contains the data flow analysis pass of the compiler. It 23 computes data flow information which tells combine_instructions 24 which insns to consider combining and controls register allocation. 25 26 Additional data flow information that is too bulky to record is 27 generated during the analysis, and is used at that time to create 28 autoincrement and autodecrement addressing. 29 30 The first step is dividing the function into basic blocks. 31 find_basic_blocks does this. Then life_analysis determines 32 where each register is live and where it is dead. 33 34 ** find_basic_blocks ** 35 36 find_basic_blocks divides the current function's rtl into basic 37 blocks and constructs the CFG. The blocks are recorded in the 38 basic_block_info array; the CFG exists in the edge structures 39 referenced by the blocks. 40 41 find_basic_blocks also finds any unreachable loops and deletes them. 42 43 ** life_analysis ** 44 45 life_analysis is called immediately after find_basic_blocks. 46 It uses the basic block information to determine where each 47 hard or pseudo register is live. 48 49 ** live-register info ** 50 51 The information about where each register is live is in two parts: 52 the REG_NOTES of insns, and the vector basic_block->global_live_at_start. 53 54 basic_block->global_live_at_start has an element for each basic 55 block, and the element is a bit-vector with a bit for each hard or 56 pseudo register. The bit is 1 if the register is live at the 57 beginning of the basic block. 58 59 Two types of elements can be added to an insn's REG_NOTES. 60 A REG_DEAD note is added to an insn's REG_NOTES for any register 61 that meets both of two conditions: The value in the register is not 62 needed in subsequent insns and the insn does not replace the value in 63 the register (in the case of multi-word hard registers, the value in 64 each register must be replaced by the insn to avoid a REG_DEAD note). 65 66 In the vast majority of cases, an object in a REG_DEAD note will be 67 used somewhere in the insn. The (rare) exception to this is if an 68 insn uses a multi-word hard register and only some of the registers are 69 needed in subsequent insns. In that case, REG_DEAD notes will be 70 provided for those hard registers that are not subsequently needed. 71 Partial REG_DEAD notes of this type do not occur when an insn sets 72 only some of the hard registers used in such a multi-word operand; 73 omitting REG_DEAD notes for objects stored in an insn is optional and 74 the desire to do so does not justify the complexity of the partial 75 REG_DEAD notes. 76 77 REG_UNUSED notes are added for each register that is set by the insn 78 but is unused subsequently (if every register set by the insn is unused 79 and the insn does not reference memory or have some other side-effect, 80 the insn is deleted instead). If only part of a multi-word hard 81 register is used in a subsequent insn, REG_UNUSED notes are made for 82 the parts that will not be used. 83 84 To determine which registers are live after any insn, one can 85 start from the beginning of the basic block and scan insns, noting 86 which registers are set by each insn and which die there. 87 88 ** Other actions of life_analysis ** 89 90 life_analysis sets up the LOG_LINKS fields of insns because the 91 information needed to do so is readily available. 92 93 life_analysis deletes insns whose only effect is to store a value 94 that is never used. 95 96 life_analysis notices cases where a reference to a register as 97 a memory address can be combined with a preceding or following 98 incrementation or decrementation of the register. The separate 99 instruction to increment or decrement is deleted and the address 100 is changed to a POST_INC or similar rtx. 101 102 Each time an incrementing or decrementing address is created, 103 a REG_INC element is added to the insn's REG_NOTES list. 104 105 life_analysis fills in certain vectors containing information about 106 register usage: REG_N_REFS, REG_N_DEATHS, REG_N_SETS, REG_LIVE_LENGTH, 107 REG_N_CALLS_CROSSED and REG_BASIC_BLOCK. 108 109 life_analysis sets current_function_sp_is_unchanging if the function 110 doesn't modify the stack pointer. */ 111 112/* TODO: 113 114 Split out from life_analysis: 115 - local property discovery (bb->local_live, bb->local_set) 116 - global property computation 117 - log links creation 118 - pre/post modify transformation 119*/ 120 121#include "config.h" 122#include "system.h" 123#include "coretypes.h" 124#include "tm.h" 125#include "tree.h" 126#include "rtl.h" 127#include "tm_p.h" 128#include "hard-reg-set.h" 129#include "basic-block.h" 130#include "insn-config.h" 131#include "regs.h" 132#include "flags.h" 133#include "output.h" 134#include "function.h" 135#include "except.h" 136#include "toplev.h" 137#include "recog.h" 138#include "expr.h" 139#include "timevar.h" 140 141#include "obstack.h" 142#include "splay-tree.h" 143 144#ifndef HAVE_epilogue 145#define HAVE_epilogue 0 146#endif 147#ifndef HAVE_prologue 148#define HAVE_prologue 0 149#endif 150#ifndef HAVE_sibcall_epilogue 151#define HAVE_sibcall_epilogue 0 152#endif 153 154#ifndef EPILOGUE_USES 155#define EPILOGUE_USES(REGNO) 0 156#endif 157#ifndef EH_USES 158#define EH_USES(REGNO) 0 159#endif 160 161#ifdef HAVE_conditional_execution 162#ifndef REVERSE_CONDEXEC_PREDICATES_P 163#define REVERSE_CONDEXEC_PREDICATES_P(x, y) ((x) == reverse_condition (y)) 164#endif 165#endif 166 167/* Nonzero if the second flow pass has completed. */ 168int flow2_completed; 169 170/* Maximum register number used in this function, plus one. */ 171 172int max_regno; 173 174/* Indexed by n, giving various register information */ 175 176varray_type reg_n_info; 177 178/* Size of a regset for the current function, 179 in (1) bytes and (2) elements. */ 180 181int regset_bytes; 182int regset_size; 183 184/* Regset of regs live when calls to `setjmp'-like functions happen. */ 185/* ??? Does this exist only for the setjmp-clobbered warning message? */ 186 187regset regs_live_at_setjmp; 188 189/* List made of EXPR_LIST rtx's which gives pairs of pseudo registers 190 that have to go in the same hard reg. 191 The first two regs in the list are a pair, and the next two 192 are another pair, etc. */ 193rtx regs_may_share; 194 195/* Callback that determines if it's ok for a function to have no 196 noreturn attribute. */ 197int (*lang_missing_noreturn_ok_p) (tree); 198 199/* Set of registers that may be eliminable. These are handled specially 200 in updating regs_ever_live. */ 201 202static HARD_REG_SET elim_reg_set; 203 204/* Holds information for tracking conditional register life information. */ 205struct reg_cond_life_info 206{ 207 /* A boolean expression of conditions under which a register is dead. */ 208 rtx condition; 209 /* Conditions under which a register is dead at the basic block end. */ 210 rtx orig_condition; 211 212 /* A boolean expression of conditions under which a register has been 213 stored into. */ 214 rtx stores; 215 216 /* ??? Could store mask of bytes that are dead, so that we could finally 217 track lifetimes of multi-word registers accessed via subregs. */ 218}; 219 220/* For use in communicating between propagate_block and its subroutines. 221 Holds all information needed to compute life and def-use information. */ 222 223struct propagate_block_info 224{ 225 /* The basic block we're considering. */ 226 basic_block bb; 227 228 /* Bit N is set if register N is conditionally or unconditionally live. */ 229 regset reg_live; 230 231 /* Bit N is set if register N is set this insn. */ 232 regset new_set; 233 234 /* Element N is the next insn that uses (hard or pseudo) register N 235 within the current basic block; or zero, if there is no such insn. */ 236 rtx *reg_next_use; 237 238 /* Contains a list of all the MEMs we are tracking for dead store 239 elimination. */ 240 rtx mem_set_list; 241 242 /* If non-null, record the set of registers set unconditionally in the 243 basic block. */ 244 regset local_set; 245 246 /* If non-null, record the set of registers set conditionally in the 247 basic block. */ 248 regset cond_local_set; 249 250#ifdef HAVE_conditional_execution 251 /* Indexed by register number, holds a reg_cond_life_info for each 252 register that is not unconditionally live or dead. */ 253 splay_tree reg_cond_dead; 254 255 /* Bit N is set if register N is in an expression in reg_cond_dead. */ 256 regset reg_cond_reg; 257#endif 258 259 /* The length of mem_set_list. */ 260 int mem_set_list_len; 261 262 /* Nonzero if the value of CC0 is live. */ 263 int cc0_live; 264 265 /* Flags controlling the set of information propagate_block collects. */ 266 int flags; 267}; 268 269/* Number of dead insns removed. */ 270static int ndead; 271 272/* Maximum length of pbi->mem_set_list before we start dropping 273 new elements on the floor. */ 274#define MAX_MEM_SET_LIST_LEN 100 275 276/* Forward declarations */ 277static int verify_wide_reg_1 (rtx *, void *); 278static void verify_wide_reg (int, basic_block); 279static void verify_local_live_at_start (regset, basic_block); 280static void notice_stack_pointer_modification_1 (rtx, rtx, void *); 281static void notice_stack_pointer_modification (rtx); 282static void mark_reg (rtx, void *); 283static void mark_regs_live_at_end (regset); 284static void calculate_global_regs_live (sbitmap, sbitmap, int); 285static void propagate_block_delete_insn (rtx); 286static rtx propagate_block_delete_libcall (rtx, rtx); 287static int insn_dead_p (struct propagate_block_info *, rtx, int, rtx); 288static int libcall_dead_p (struct propagate_block_info *, rtx, rtx); 289static void mark_set_regs (struct propagate_block_info *, rtx, rtx); 290static void mark_set_1 (struct propagate_block_info *, enum rtx_code, rtx, 291 rtx, rtx, int); 292static int find_regno_partial (rtx *, void *); 293 294#ifdef HAVE_conditional_execution 295static int mark_regno_cond_dead (struct propagate_block_info *, int, rtx); 296static void free_reg_cond_life_info (splay_tree_value); 297static int flush_reg_cond_reg_1 (splay_tree_node, void *); 298static void flush_reg_cond_reg (struct propagate_block_info *, int); 299static rtx elim_reg_cond (rtx, unsigned int); 300static rtx ior_reg_cond (rtx, rtx, int); 301static rtx not_reg_cond (rtx); 302static rtx and_reg_cond (rtx, rtx, int); 303#endif 304#ifdef AUTO_INC_DEC 305static void attempt_auto_inc (struct propagate_block_info *, rtx, rtx, rtx, 306 rtx, rtx); 307static void find_auto_inc (struct propagate_block_info *, rtx, rtx); 308static int try_pre_increment_1 (struct propagate_block_info *, rtx); 309static int try_pre_increment (rtx, rtx, HOST_WIDE_INT); 310#endif 311static void mark_used_reg (struct propagate_block_info *, rtx, rtx, rtx); 312static void mark_used_regs (struct propagate_block_info *, rtx, rtx, rtx); 313void debug_flow_info (void); 314static void add_to_mem_set_list (struct propagate_block_info *, rtx); 315static int invalidate_mems_from_autoinc (rtx *, void *); 316static void invalidate_mems_from_set (struct propagate_block_info *, rtx); 317static void clear_log_links (sbitmap); 318static int count_or_remove_death_notes_bb (basic_block, int); 319 320 321void 322check_function_return_warnings (void) 323{ 324 if (warn_missing_noreturn 325 && !TREE_THIS_VOLATILE (cfun->decl) 326 && EXIT_BLOCK_PTR->pred == NULL 327 && (lang_missing_noreturn_ok_p 328 && !lang_missing_noreturn_ok_p (cfun->decl))) 329 warning ("function might be possible candidate for attribute `noreturn'"); 330 331 /* If we have a path to EXIT, then we do return. */ 332 if (TREE_THIS_VOLATILE (cfun->decl) 333 && EXIT_BLOCK_PTR->pred != NULL) 334 warning ("`noreturn' function does return"); 335 336 /* If the clobber_return_insn appears in some basic block, then we 337 do reach the end without returning a value. */ 338 else if (warn_return_type 339 && cfun->x_clobber_return_insn != NULL 340 && EXIT_BLOCK_PTR->pred != NULL) 341 { 342 int max_uid = get_max_uid (); 343 344 /* If clobber_return_insn was excised by jump1, then renumber_insns 345 can make max_uid smaller than the number still recorded in our rtx. 346 That's fine, since this is a quick way of verifying that the insn 347 is no longer in the chain. */ 348 if (INSN_UID (cfun->x_clobber_return_insn) < max_uid) 349 { 350 rtx insn; 351 352 for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) 353 if (insn == cfun->x_clobber_return_insn) 354 { 355 warning ("control reaches end of non-void function"); 356 break; 357 } 358 } 359 } 360} 361 362/* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK 363 note associated with the BLOCK. */ 364 365rtx 366first_insn_after_basic_block_note (basic_block block) 367{ 368 rtx insn; 369 370 /* Get the first instruction in the block. */ 371 insn = BB_HEAD (block); 372 373 if (insn == NULL_RTX) 374 return NULL_RTX; 375 if (GET_CODE (insn) == CODE_LABEL) 376 insn = NEXT_INSN (insn); 377 if (!NOTE_INSN_BASIC_BLOCK_P (insn)) 378 abort (); 379 380 return NEXT_INSN (insn); 381} 382 383/* Perform data flow analysis. 384 F is the first insn of the function; FLAGS is a set of PROP_* flags 385 to be used in accumulating flow info. */ 386 387void 388life_analysis (rtx f, FILE *file, int flags) 389{ 390#ifdef ELIMINABLE_REGS 391 int i; 392 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS; 393#endif 394 395 /* Record which registers will be eliminated. We use this in 396 mark_used_regs. */ 397 398 CLEAR_HARD_REG_SET (elim_reg_set); 399 400#ifdef ELIMINABLE_REGS 401 for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++) 402 SET_HARD_REG_BIT (elim_reg_set, eliminables[i].from); 403#else 404 SET_HARD_REG_BIT (elim_reg_set, FRAME_POINTER_REGNUM); 405#endif 406 407 408#ifdef CANNOT_CHANGE_MODE_CLASS 409 if (flags & PROP_REG_INFO) 410 init_subregs_of_mode (); 411#endif 412 413 if (! optimize) 414 flags &= ~(PROP_LOG_LINKS | PROP_AUTOINC | PROP_ALLOW_CFG_CHANGES); 415 416 /* The post-reload life analysis have (on a global basis) the same 417 registers live as was computed by reload itself. elimination 418 Otherwise offsets and such may be incorrect. 419 420 Reload will make some registers as live even though they do not 421 appear in the rtl. 422 423 We don't want to create new auto-incs after reload, since they 424 are unlikely to be useful and can cause problems with shared 425 stack slots. */ 426 if (reload_completed) 427 flags &= ~(PROP_REG_INFO | PROP_AUTOINC); 428 429 /* We want alias analysis information for local dead store elimination. */ 430 if (optimize && (flags & PROP_SCAN_DEAD_STORES)) 431 init_alias_analysis (); 432 433 /* Always remove no-op moves. Do this before other processing so 434 that we don't have to keep re-scanning them. */ 435 delete_noop_moves (f); 436 437 /* Some targets can emit simpler epilogues if they know that sp was 438 not ever modified during the function. After reload, of course, 439 we've already emitted the epilogue so there's no sense searching. */ 440 if (! reload_completed) 441 notice_stack_pointer_modification (f); 442 443 /* Allocate and zero out data structures that will record the 444 data from lifetime analysis. */ 445 allocate_reg_life_data (); 446 allocate_bb_life_data (); 447 448 /* Find the set of registers live on function exit. */ 449 mark_regs_live_at_end (EXIT_BLOCK_PTR->global_live_at_start); 450 451 /* "Update" life info from zero. It'd be nice to begin the 452 relaxation with just the exit and noreturn blocks, but that set 453 is not immediately handy. */ 454 455 if (flags & PROP_REG_INFO) 456 { 457 memset (regs_ever_live, 0, sizeof (regs_ever_live)); 458 memset (regs_asm_clobbered, 0, sizeof (regs_asm_clobbered)); 459 } 460 update_life_info (NULL, UPDATE_LIFE_GLOBAL, flags); 461 462 /* Clean up. */ 463 if (optimize && (flags & PROP_SCAN_DEAD_STORES)) 464 end_alias_analysis (); 465 466 if (file) 467 dump_flow_info (file); 468 469 free_basic_block_vars (1); 470 471 /* Removing dead insns should've made jumptables really dead. */ 472 delete_dead_jumptables (); 473} 474 475/* A subroutine of verify_wide_reg, called through for_each_rtx. 476 Search for REGNO. If found, return 2 if it is not wider than 477 word_mode. */ 478 479static int 480verify_wide_reg_1 (rtx *px, void *pregno) 481{ 482 rtx x = *px; 483 unsigned int regno = *(int *) pregno; 484 485 if (GET_CODE (x) == REG && REGNO (x) == regno) 486 { 487 if (GET_MODE_BITSIZE (GET_MODE (x)) <= BITS_PER_WORD) 488 return 2; 489 return 1; 490 } 491 return 0; 492} 493 494/* A subroutine of verify_local_live_at_start. Search through insns 495 of BB looking for register REGNO. */ 496 497static void 498verify_wide_reg (int regno, basic_block bb) 499{ 500 rtx head = BB_HEAD (bb), end = BB_END (bb); 501 502 while (1) 503 { 504 if (INSN_P (head)) 505 { 506 int r = for_each_rtx (&PATTERN (head), verify_wide_reg_1, ®no); 507 if (r == 1) 508 return; 509 if (r == 2) 510 break; 511 } 512 if (head == end) 513 break; 514 head = NEXT_INSN (head); 515 } 516 517 if (rtl_dump_file) 518 { 519 fprintf (rtl_dump_file, "Register %d died unexpectedly.\n", regno); 520 dump_bb (bb, rtl_dump_file); 521 } 522 abort (); 523} 524 525/* A subroutine of update_life_info. Verify that there are no untoward 526 changes in live_at_start during a local update. */ 527 528static void 529verify_local_live_at_start (regset new_live_at_start, basic_block bb) 530{ 531 if (reload_completed) 532 { 533 /* After reload, there are no pseudos, nor subregs of multi-word 534 registers. The regsets should exactly match. */ 535 if (! REG_SET_EQUAL_P (new_live_at_start, bb->global_live_at_start)) 536 { 537 if (rtl_dump_file) 538 { 539 fprintf (rtl_dump_file, 540 "live_at_start mismatch in bb %d, aborting\nNew:\n", 541 bb->index); 542 debug_bitmap_file (rtl_dump_file, new_live_at_start); 543 fputs ("Old:\n", rtl_dump_file); 544 dump_bb (bb, rtl_dump_file); 545 } 546 abort (); 547 } 548 } 549 else 550 { 551 int i; 552 553 /* Find the set of changed registers. */ 554 XOR_REG_SET (new_live_at_start, bb->global_live_at_start); 555 556 EXECUTE_IF_SET_IN_REG_SET (new_live_at_start, 0, i, 557 { 558 /* No registers should die. */ 559 if (REGNO_REG_SET_P (bb->global_live_at_start, i)) 560 { 561 if (rtl_dump_file) 562 { 563 fprintf (rtl_dump_file, 564 "Register %d died unexpectedly.\n", i); 565 dump_bb (bb, rtl_dump_file); 566 } 567 abort (); 568 } 569 570 /* Verify that the now-live register is wider than word_mode. */ 571 verify_wide_reg (i, bb); 572 }); 573 } 574} 575 576/* Updates life information starting with the basic blocks set in BLOCKS. 577 If BLOCKS is null, consider it to be the universal set. 578 579 If EXTENT is UPDATE_LIFE_LOCAL, such as after splitting or peepholing, 580 we are only expecting local modifications to basic blocks. If we find 581 extra registers live at the beginning of a block, then we either killed 582 useful data, or we have a broken split that wants data not provided. 583 If we find registers removed from live_at_start, that means we have 584 a broken peephole that is killing a register it shouldn't. 585 586 ??? This is not true in one situation -- when a pre-reload splitter 587 generates subregs of a multi-word pseudo, current life analysis will 588 lose the kill. So we _can_ have a pseudo go live. How irritating. 589 590 It is also not true when a peephole decides that it doesn't need one 591 or more of the inputs. 592 593 Including PROP_REG_INFO does not properly refresh regs_ever_live 594 unless the caller resets it to zero. */ 595 596int 597update_life_info (sbitmap blocks, enum update_life_extent extent, int prop_flags) 598{ 599 regset tmp; 600 regset_head tmp_head; 601 int i; 602 int stabilized_prop_flags = prop_flags; 603 basic_block bb; 604 605 tmp = INITIALIZE_REG_SET (tmp_head); 606 ndead = 0; 607 608 timevar_push ((extent == UPDATE_LIFE_LOCAL || blocks) 609 ? TV_LIFE_UPDATE : TV_LIFE); 610 611 /* Changes to the CFG are only allowed when 612 doing a global update for the entire CFG. */ 613 if ((prop_flags & PROP_ALLOW_CFG_CHANGES) 614 && (extent == UPDATE_LIFE_LOCAL || blocks)) 615 abort (); 616 617 /* For a global update, we go through the relaxation process again. */ 618 if (extent != UPDATE_LIFE_LOCAL) 619 { 620 for ( ; ; ) 621 { 622 int changed = 0; 623 624 calculate_global_regs_live (blocks, blocks, 625 prop_flags & (PROP_SCAN_DEAD_CODE 626 | PROP_SCAN_DEAD_STORES 627 | PROP_ALLOW_CFG_CHANGES)); 628 629 if ((prop_flags & (PROP_KILL_DEAD_CODE | PROP_ALLOW_CFG_CHANGES)) 630 != (PROP_KILL_DEAD_CODE | PROP_ALLOW_CFG_CHANGES)) 631 break; 632 633 /* Removing dead code may allow the CFG to be simplified which 634 in turn may allow for further dead code detection / removal. */ 635 FOR_EACH_BB_REVERSE (bb) 636 { 637 COPY_REG_SET (tmp, bb->global_live_at_end); 638 changed |= propagate_block (bb, tmp, NULL, NULL, 639 prop_flags & (PROP_SCAN_DEAD_CODE 640 | PROP_SCAN_DEAD_STORES 641 | PROP_KILL_DEAD_CODE)); 642 } 643 644 /* Don't pass PROP_SCAN_DEAD_CODE or PROP_KILL_DEAD_CODE to 645 subsequent propagate_block calls, since removing or acting as 646 removing dead code can affect global register liveness, which 647 is supposed to be finalized for this call after this loop. */ 648 stabilized_prop_flags 649 &= ~(PROP_SCAN_DEAD_CODE | PROP_SCAN_DEAD_STORES 650 | PROP_KILL_DEAD_CODE); 651 652 if (! changed) 653 break; 654 655 /* We repeat regardless of what cleanup_cfg says. If there were 656 instructions deleted above, that might have been only a 657 partial improvement (see MAX_MEM_SET_LIST_LEN usage). 658 Further improvement may be possible. */ 659 cleanup_cfg (CLEANUP_EXPENSIVE); 660 661 /* Zap the life information from the last round. If we don't 662 do this, we can wind up with registers that no longer appear 663 in the code being marked live at entry, which twiggs bogus 664 warnings from regno_uninitialized. */ 665 FOR_EACH_BB (bb) 666 { 667 CLEAR_REG_SET (bb->global_live_at_start); 668 CLEAR_REG_SET (bb->global_live_at_end); 669 } 670 } 671 672 /* If asked, remove notes from the blocks we'll update. */ 673 if (extent == UPDATE_LIFE_GLOBAL_RM_NOTES) 674 count_or_remove_death_notes (blocks, 1); 675 } 676 677 /* Clear log links in case we are asked to (re)compute them. */ 678 if (prop_flags & PROP_LOG_LINKS) 679 clear_log_links (blocks); 680 681 if (blocks) 682 { 683 EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i, 684 { 685 bb = BASIC_BLOCK (i); 686 687 COPY_REG_SET (tmp, bb->global_live_at_end); 688 propagate_block (bb, tmp, NULL, NULL, stabilized_prop_flags); 689 690 if (extent == UPDATE_LIFE_LOCAL) 691 verify_local_live_at_start (tmp, bb); 692 }); 693 } 694 else 695 { 696 FOR_EACH_BB_REVERSE (bb) 697 { 698 COPY_REG_SET (tmp, bb->global_live_at_end); 699 700 propagate_block (bb, tmp, NULL, NULL, stabilized_prop_flags); 701 702 if (extent == UPDATE_LIFE_LOCAL) 703 verify_local_live_at_start (tmp, bb); 704 } 705 } 706 707 FREE_REG_SET (tmp); 708 709 if (prop_flags & PROP_REG_INFO) 710 { 711 /* The only pseudos that are live at the beginning of the function 712 are those that were not set anywhere in the function. local-alloc 713 doesn't know how to handle these correctly, so mark them as not 714 local to any one basic block. */ 715 EXECUTE_IF_SET_IN_REG_SET (ENTRY_BLOCK_PTR->global_live_at_end, 716 FIRST_PSEUDO_REGISTER, i, 717 { REG_BASIC_BLOCK (i) = REG_BLOCK_GLOBAL; }); 718 719 /* We have a problem with any pseudoreg that lives across the setjmp. 720 ANSI says that if a user variable does not change in value between 721 the setjmp and the longjmp, then the longjmp preserves it. This 722 includes longjmp from a place where the pseudo appears dead. 723 (In principle, the value still exists if it is in scope.) 724 If the pseudo goes in a hard reg, some other value may occupy 725 that hard reg where this pseudo is dead, thus clobbering the pseudo. 726 Conclusion: such a pseudo must not go in a hard reg. */ 727 EXECUTE_IF_SET_IN_REG_SET (regs_live_at_setjmp, 728 FIRST_PSEUDO_REGISTER, i, 729 { 730 if (regno_reg_rtx[i] != 0) 731 { 732 REG_LIVE_LENGTH (i) = -1; 733 REG_BASIC_BLOCK (i) = REG_BLOCK_UNKNOWN; 734 } 735 }); 736 } 737 timevar_pop ((extent == UPDATE_LIFE_LOCAL || blocks) 738 ? TV_LIFE_UPDATE : TV_LIFE); 739 if (ndead && rtl_dump_file) 740 fprintf (rtl_dump_file, "deleted %i dead insns\n", ndead); 741 return ndead; 742} 743 744/* Update life information in all blocks where BB_DIRTY is set. */ 745 746int 747update_life_info_in_dirty_blocks (enum update_life_extent extent, int prop_flags) 748{ 749 sbitmap update_life_blocks = sbitmap_alloc (last_basic_block); 750 int n = 0; 751 basic_block bb; 752 int retval = 0; 753 754 sbitmap_zero (update_life_blocks); 755 FOR_EACH_BB (bb) 756 { 757 if (extent == UPDATE_LIFE_LOCAL) 758 { 759 if (bb->flags & BB_DIRTY) 760 { 761 SET_BIT (update_life_blocks, bb->index); 762 n++; 763 } 764 } 765 else 766 { 767 /* ??? Bootstrap with -march=pentium4 fails to terminate 768 with only a partial life update. */ 769 SET_BIT (update_life_blocks, bb->index); 770 if (bb->flags & BB_DIRTY) 771 n++; 772 } 773 } 774 775 if (n) 776 retval = update_life_info (update_life_blocks, extent, prop_flags); 777 778 sbitmap_free (update_life_blocks); 779 return retval; 780} 781 782/* Free the variables allocated by find_basic_blocks. 783 784 KEEP_HEAD_END_P is nonzero if basic_block_info is not to be freed. */ 785 786void 787free_basic_block_vars (int keep_head_end_p) 788{ 789 if (! keep_head_end_p) 790 { 791 if (basic_block_info) 792 { 793 clear_edges (); 794 VARRAY_FREE (basic_block_info); 795 } 796 n_basic_blocks = 0; 797 last_basic_block = 0; 798 799 ENTRY_BLOCK_PTR->aux = NULL; 800 ENTRY_BLOCK_PTR->global_live_at_end = NULL; 801 EXIT_BLOCK_PTR->aux = NULL; 802 EXIT_BLOCK_PTR->global_live_at_start = NULL; 803 } 804} 805 806/* Delete any insns that copy a register to itself. */ 807 808int 809delete_noop_moves (rtx f ATTRIBUTE_UNUSED) 810{ 811 rtx insn, next; 812 basic_block bb; 813 int nnoops = 0; 814 815 FOR_EACH_BB (bb) 816 { 817 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); insn = next) 818 { 819 next = NEXT_INSN (insn); 820 if (INSN_P (insn) && noop_move_p (insn)) 821 { 822 rtx note; 823 824 /* If we're about to remove the first insn of a libcall 825 then move the libcall note to the next real insn and 826 update the retval note. */ 827 if ((note = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) 828 && XEXP (note, 0) != insn) 829 { 830 rtx new_libcall_insn = next_real_insn (insn); 831 rtx retval_note = find_reg_note (XEXP (note, 0), 832 REG_RETVAL, NULL_RTX); 833 REG_NOTES (new_libcall_insn) 834 = gen_rtx_INSN_LIST (REG_LIBCALL, XEXP (note, 0), 835 REG_NOTES (new_libcall_insn)); 836 XEXP (retval_note, 0) = new_libcall_insn; 837 } 838 839 delete_insn_and_edges (insn); 840 nnoops++; 841 } 842 } 843 } 844 if (nnoops && rtl_dump_file) 845 fprintf (rtl_dump_file, "deleted %i noop moves", nnoops); 846 return nnoops; 847} 848 849/* Delete any jump tables never referenced. We can't delete them at the 850 time of removing tablejump insn as they are referenced by the preceding 851 insns computing the destination, so we delay deleting and garbagecollect 852 them once life information is computed. */ 853void 854delete_dead_jumptables (void) 855{ 856 rtx insn, next; 857 for (insn = get_insns (); insn; insn = next) 858 { 859 next = NEXT_INSN (insn); 860 if (GET_CODE (insn) == CODE_LABEL 861 && LABEL_NUSES (insn) == LABEL_PRESERVE_P (insn) 862 && GET_CODE (next) == JUMP_INSN 863 && (GET_CODE (PATTERN (next)) == ADDR_VEC 864 || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC)) 865 { 866 if (rtl_dump_file) 867 fprintf (rtl_dump_file, "Dead jumptable %i removed\n", INSN_UID (insn)); 868 delete_insn (NEXT_INSN (insn)); 869 delete_insn (insn); 870 next = NEXT_INSN (next); 871 } 872 } 873} 874 875/* Determine if the stack pointer is constant over the life of the function. 876 Only useful before prologues have been emitted. */ 877 878static void 879notice_stack_pointer_modification_1 (rtx x, rtx pat ATTRIBUTE_UNUSED, 880 void *data ATTRIBUTE_UNUSED) 881{ 882 if (x == stack_pointer_rtx 883 /* The stack pointer is only modified indirectly as the result 884 of a push until later in flow. See the comments in rtl.texi 885 regarding Embedded Side-Effects on Addresses. */ 886 || (GET_CODE (x) == MEM 887 && GET_RTX_CLASS (GET_CODE (XEXP (x, 0))) == 'a' 888 && XEXP (XEXP (x, 0), 0) == stack_pointer_rtx)) 889 current_function_sp_is_unchanging = 0; 890} 891 892static void 893notice_stack_pointer_modification (rtx f) 894{ 895 rtx insn; 896 897 /* Assume that the stack pointer is unchanging if alloca hasn't 898 been used. */ 899 current_function_sp_is_unchanging = !current_function_calls_alloca; 900 if (! current_function_sp_is_unchanging) 901 return; 902 903 for (insn = f; insn; insn = NEXT_INSN (insn)) 904 { 905 if (INSN_P (insn)) 906 { 907 /* Check if insn modifies the stack pointer. */ 908 note_stores (PATTERN (insn), notice_stack_pointer_modification_1, 909 NULL); 910 if (! current_function_sp_is_unchanging) 911 return; 912 } 913 } 914} 915 916/* Mark a register in SET. Hard registers in large modes get all 917 of their component registers set as well. */ 918 919static void 920mark_reg (rtx reg, void *xset) 921{ 922 regset set = (regset) xset; 923 int regno = REGNO (reg); 924 925 if (GET_MODE (reg) == BLKmode) 926 abort (); 927 928 SET_REGNO_REG_SET (set, regno); 929 if (regno < FIRST_PSEUDO_REGISTER) 930 { 931 int n = HARD_REGNO_NREGS (regno, GET_MODE (reg)); 932 while (--n > 0) 933 SET_REGNO_REG_SET (set, regno + n); 934 } 935} 936 937/* Mark those regs which are needed at the end of the function as live 938 at the end of the last basic block. */ 939 940static void 941mark_regs_live_at_end (regset set) 942{ 943 unsigned int i; 944 945 /* If exiting needs the right stack value, consider the stack pointer 946 live at the end of the function. */ 947 if ((HAVE_epilogue && epilogue_completed) 948 || ! EXIT_IGNORE_STACK 949 || (! FRAME_POINTER_REQUIRED 950 && ! current_function_calls_alloca 951 && flag_omit_frame_pointer) 952 || current_function_sp_is_unchanging) 953 { 954 SET_REGNO_REG_SET (set, STACK_POINTER_REGNUM); 955 } 956 957 /* Mark the frame pointer if needed at the end of the function. If 958 we end up eliminating it, it will be removed from the live list 959 of each basic block by reload. */ 960 961 if (! reload_completed || frame_pointer_needed) 962 { 963 SET_REGNO_REG_SET (set, FRAME_POINTER_REGNUM); 964#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM 965 /* If they are different, also mark the hard frame pointer as live. */ 966 if (! LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM)) 967 SET_REGNO_REG_SET (set, HARD_FRAME_POINTER_REGNUM); 968#endif 969 } 970 971#ifndef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED 972 /* Many architectures have a GP register even without flag_pic. 973 Assume the pic register is not in use, or will be handled by 974 other means, if it is not fixed. */ 975 if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM 976 && fixed_regs[PIC_OFFSET_TABLE_REGNUM]) 977 SET_REGNO_REG_SET (set, PIC_OFFSET_TABLE_REGNUM); 978#endif 979 980 /* Mark all global registers, and all registers used by the epilogue 981 as being live at the end of the function since they may be 982 referenced by our caller. */ 983 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 984 if (global_regs[i] || EPILOGUE_USES (i)) 985 SET_REGNO_REG_SET (set, i); 986 987 if (HAVE_epilogue && epilogue_completed) 988 { 989 /* Mark all call-saved registers that we actually used. */ 990 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 991 if (regs_ever_live[i] && ! LOCAL_REGNO (i) 992 && ! TEST_HARD_REG_BIT (regs_invalidated_by_call, i)) 993 SET_REGNO_REG_SET (set, i); 994 } 995 996#ifdef EH_RETURN_DATA_REGNO 997 /* Mark the registers that will contain data for the handler. */ 998 if (reload_completed && current_function_calls_eh_return) 999 for (i = 0; ; ++i) 1000 { 1001 unsigned regno = EH_RETURN_DATA_REGNO(i); 1002 if (regno == INVALID_REGNUM) 1003 break; 1004 SET_REGNO_REG_SET (set, regno); 1005 } 1006#endif 1007#ifdef EH_RETURN_STACKADJ_RTX 1008 if ((! HAVE_epilogue || ! epilogue_completed) 1009 && current_function_calls_eh_return) 1010 { 1011 rtx tmp = EH_RETURN_STACKADJ_RTX; 1012 if (tmp && REG_P (tmp)) 1013 mark_reg (tmp, set); 1014 } 1015#endif 1016#ifdef EH_RETURN_HANDLER_RTX 1017 if ((! HAVE_epilogue || ! epilogue_completed) 1018 && current_function_calls_eh_return) 1019 { 1020 rtx tmp = EH_RETURN_HANDLER_RTX; 1021 if (tmp && REG_P (tmp)) 1022 mark_reg (tmp, set); 1023 } 1024#endif 1025 1026 /* Mark function return value. */ 1027 diddle_return_value (mark_reg, set); 1028} 1029 1030/* Propagate global life info around the graph of basic blocks. Begin 1031 considering blocks with their corresponding bit set in BLOCKS_IN. 1032 If BLOCKS_IN is null, consider it the universal set. 1033 1034 BLOCKS_OUT is set for every block that was changed. */ 1035 1036static void 1037calculate_global_regs_live (sbitmap blocks_in, sbitmap blocks_out, int flags) 1038{ 1039 basic_block *queue, *qhead, *qtail, *qend, bb; 1040 regset tmp, new_live_at_end, invalidated_by_call; 1041 regset_head tmp_head, invalidated_by_call_head; 1042 regset_head new_live_at_end_head; 1043 int i; 1044 1045 /* Some passes used to forget clear aux field of basic block causing 1046 sick behavior here. */ 1047#ifdef ENABLE_CHECKING 1048 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 1049 if (bb->aux) 1050 abort (); 1051#endif 1052 1053 tmp = INITIALIZE_REG_SET (tmp_head); 1054 new_live_at_end = INITIALIZE_REG_SET (new_live_at_end_head); 1055 invalidated_by_call = INITIALIZE_REG_SET (invalidated_by_call_head); 1056 1057 /* Inconveniently, this is only readily available in hard reg set form. */ 1058 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) 1059 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i)) 1060 SET_REGNO_REG_SET (invalidated_by_call, i); 1061 1062 /* Create a worklist. Allocate an extra slot for ENTRY_BLOCK, and one 1063 because the `head == tail' style test for an empty queue doesn't 1064 work with a full queue. */ 1065 queue = xmalloc ((n_basic_blocks + 2) * sizeof (*queue)); 1066 qtail = queue; 1067 qhead = qend = queue + n_basic_blocks + 2; 1068 1069 /* Queue the blocks set in the initial mask. Do this in reverse block 1070 number order so that we are more likely for the first round to do 1071 useful work. We use AUX non-null to flag that the block is queued. */ 1072 if (blocks_in) 1073 { 1074 FOR_EACH_BB (bb) 1075 if (TEST_BIT (blocks_in, bb->index)) 1076 { 1077 *--qhead = bb; 1078 bb->aux = bb; 1079 } 1080 } 1081 else 1082 { 1083 FOR_EACH_BB (bb) 1084 { 1085 *--qhead = bb; 1086 bb->aux = bb; 1087 } 1088 } 1089 1090 /* We clean aux when we remove the initially-enqueued bbs, but we 1091 don't enqueue ENTRY and EXIT initially, so clean them upfront and 1092 unconditionally. */ 1093 ENTRY_BLOCK_PTR->aux = EXIT_BLOCK_PTR->aux = NULL; 1094 1095 if (blocks_out) 1096 sbitmap_zero (blocks_out); 1097 1098 /* We work through the queue until there are no more blocks. What 1099 is live at the end of this block is precisely the union of what 1100 is live at the beginning of all its successors. So, we set its 1101 GLOBAL_LIVE_AT_END field based on the GLOBAL_LIVE_AT_START field 1102 for its successors. Then, we compute GLOBAL_LIVE_AT_START for 1103 this block by walking through the instructions in this block in 1104 reverse order and updating as we go. If that changed 1105 GLOBAL_LIVE_AT_START, we add the predecessors of the block to the 1106 queue; they will now need to recalculate GLOBAL_LIVE_AT_END. 1107 1108 We are guaranteed to terminate, because GLOBAL_LIVE_AT_START 1109 never shrinks. If a register appears in GLOBAL_LIVE_AT_START, it 1110 must either be live at the end of the block, or used within the 1111 block. In the latter case, it will certainly never disappear 1112 from GLOBAL_LIVE_AT_START. In the former case, the register 1113 could go away only if it disappeared from GLOBAL_LIVE_AT_START 1114 for one of the successor blocks. By induction, that cannot 1115 occur. */ 1116 while (qhead != qtail) 1117 { 1118 int rescan, changed; 1119 basic_block bb; 1120 edge e; 1121 1122 bb = *qhead++; 1123 if (qhead == qend) 1124 qhead = queue; 1125 bb->aux = NULL; 1126 1127 /* Begin by propagating live_at_start from the successor blocks. */ 1128 CLEAR_REG_SET (new_live_at_end); 1129 1130 if (bb->succ) 1131 for (e = bb->succ; e; e = e->succ_next) 1132 { 1133 basic_block sb = e->dest; 1134 1135 /* Call-clobbered registers die across exception and 1136 call edges. */ 1137 /* ??? Abnormal call edges ignored for the moment, as this gets 1138 confused by sibling call edges, which crashes reg-stack. */ 1139 if (e->flags & EDGE_EH) 1140 { 1141 bitmap_operation (tmp, sb->global_live_at_start, 1142 invalidated_by_call, BITMAP_AND_COMPL); 1143 IOR_REG_SET (new_live_at_end, tmp); 1144 } 1145 else 1146 IOR_REG_SET (new_live_at_end, sb->global_live_at_start); 1147 1148 /* If a target saves one register in another (instead of on 1149 the stack) the save register will need to be live for EH. */ 1150 if (e->flags & EDGE_EH) 1151 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1152 if (EH_USES (i)) 1153 SET_REGNO_REG_SET (new_live_at_end, i); 1154 } 1155 else 1156 { 1157 /* This might be a noreturn function that throws. And 1158 even if it isn't, getting the unwind info right helps 1159 debugging. */ 1160 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1161 if (EH_USES (i)) 1162 SET_REGNO_REG_SET (new_live_at_end, i); 1163 } 1164 1165 /* The all-important stack pointer must always be live. */ 1166 SET_REGNO_REG_SET (new_live_at_end, STACK_POINTER_REGNUM); 1167 1168 /* Before reload, there are a few registers that must be forced 1169 live everywhere -- which might not already be the case for 1170 blocks within infinite loops. */ 1171 if (! reload_completed) 1172 { 1173 /* Any reference to any pseudo before reload is a potential 1174 reference of the frame pointer. */ 1175 SET_REGNO_REG_SET (new_live_at_end, FRAME_POINTER_REGNUM); 1176 1177#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM 1178 /* Pseudos with argument area equivalences may require 1179 reloading via the argument pointer. */ 1180 if (fixed_regs[ARG_POINTER_REGNUM]) 1181 SET_REGNO_REG_SET (new_live_at_end, ARG_POINTER_REGNUM); 1182#endif 1183 1184 /* Any constant, or pseudo with constant equivalences, may 1185 require reloading from memory using the pic register. */ 1186 if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM 1187 && fixed_regs[PIC_OFFSET_TABLE_REGNUM]) 1188 SET_REGNO_REG_SET (new_live_at_end, PIC_OFFSET_TABLE_REGNUM); 1189 } 1190 1191 if (bb == ENTRY_BLOCK_PTR) 1192 { 1193 COPY_REG_SET (bb->global_live_at_end, new_live_at_end); 1194 continue; 1195 } 1196 1197 /* On our first pass through this block, we'll go ahead and continue. 1198 Recognize first pass by local_set NULL. On subsequent passes, we 1199 get to skip out early if live_at_end wouldn't have changed. */ 1200 1201 if (bb->local_set == NULL) 1202 { 1203 bb->local_set = OBSTACK_ALLOC_REG_SET (&flow_obstack); 1204 bb->cond_local_set = OBSTACK_ALLOC_REG_SET (&flow_obstack); 1205 rescan = 1; 1206 } 1207 else 1208 { 1209 /* If any bits were removed from live_at_end, we'll have to 1210 rescan the block. This wouldn't be necessary if we had 1211 precalculated local_live, however with PROP_SCAN_DEAD_CODE 1212 local_live is really dependent on live_at_end. */ 1213 CLEAR_REG_SET (tmp); 1214 rescan = bitmap_operation (tmp, bb->global_live_at_end, 1215 new_live_at_end, BITMAP_AND_COMPL); 1216 1217 if (! rescan) 1218 { 1219 /* If any of the registers in the new live_at_end set are 1220 conditionally set in this basic block, we must rescan. 1221 This is because conditional lifetimes at the end of the 1222 block do not just take the live_at_end set into account, 1223 but also the liveness at the start of each successor 1224 block. We can miss changes in those sets if we only 1225 compare the new live_at_end against the previous one. */ 1226 CLEAR_REG_SET (tmp); 1227 rescan = bitmap_operation (tmp, new_live_at_end, 1228 bb->cond_local_set, BITMAP_AND); 1229 } 1230 1231 if (! rescan) 1232 { 1233 /* Find the set of changed bits. Take this opportunity 1234 to notice that this set is empty and early out. */ 1235 CLEAR_REG_SET (tmp); 1236 changed = bitmap_operation (tmp, bb->global_live_at_end, 1237 new_live_at_end, BITMAP_XOR); 1238 if (! changed) 1239 continue; 1240 1241 /* If any of the changed bits overlap with local_set, 1242 we'll have to rescan the block. Detect overlap by 1243 the AND with ~local_set turning off bits. */ 1244 rescan = bitmap_operation (tmp, tmp, bb->local_set, 1245 BITMAP_AND_COMPL); 1246 } 1247 } 1248 1249 /* Let our caller know that BB changed enough to require its 1250 death notes updated. */ 1251 if (blocks_out) 1252 SET_BIT (blocks_out, bb->index); 1253 1254 if (! rescan) 1255 { 1256 /* Add to live_at_start the set of all registers in 1257 new_live_at_end that aren't in the old live_at_end. */ 1258 1259 bitmap_operation (tmp, new_live_at_end, bb->global_live_at_end, 1260 BITMAP_AND_COMPL); 1261 COPY_REG_SET (bb->global_live_at_end, new_live_at_end); 1262 1263 changed = bitmap_operation (bb->global_live_at_start, 1264 bb->global_live_at_start, 1265 tmp, BITMAP_IOR); 1266 if (! changed) 1267 continue; 1268 } 1269 else 1270 { 1271 COPY_REG_SET (bb->global_live_at_end, new_live_at_end); 1272 1273 /* Rescan the block insn by insn to turn (a copy of) live_at_end 1274 into live_at_start. */ 1275 propagate_block (bb, new_live_at_end, bb->local_set, 1276 bb->cond_local_set, flags); 1277 1278 /* If live_at start didn't change, no need to go farther. */ 1279 if (REG_SET_EQUAL_P (bb->global_live_at_start, new_live_at_end)) 1280 continue; 1281 1282 COPY_REG_SET (bb->global_live_at_start, new_live_at_end); 1283 } 1284 1285 /* Queue all predecessors of BB so that we may re-examine 1286 their live_at_end. */ 1287 for (e = bb->pred; e; e = e->pred_next) 1288 { 1289 basic_block pb = e->src; 1290 if (pb->aux == NULL) 1291 { 1292 *qtail++ = pb; 1293 if (qtail == qend) 1294 qtail = queue; 1295 pb->aux = pb; 1296 } 1297 } 1298 } 1299 1300 FREE_REG_SET (tmp); 1301 FREE_REG_SET (new_live_at_end); 1302 FREE_REG_SET (invalidated_by_call); 1303 1304 if (blocks_out) 1305 { 1306 EXECUTE_IF_SET_IN_SBITMAP (blocks_out, 0, i, 1307 { 1308 basic_block bb = BASIC_BLOCK (i); 1309 FREE_REG_SET (bb->local_set); 1310 FREE_REG_SET (bb->cond_local_set); 1311 }); 1312 } 1313 else 1314 { 1315 FOR_EACH_BB (bb) 1316 { 1317 FREE_REG_SET (bb->local_set); 1318 FREE_REG_SET (bb->cond_local_set); 1319 } 1320 } 1321 1322 free (queue); 1323} 1324 1325 1326/* This structure is used to pass parameters to and from the 1327 the function find_regno_partial(). It is used to pass in the 1328 register number we are looking, as well as to return any rtx 1329 we find. */ 1330 1331typedef struct { 1332 unsigned regno_to_find; 1333 rtx retval; 1334} find_regno_partial_param; 1335 1336 1337/* Find the rtx for the reg numbers specified in 'data' if it is 1338 part of an expression which only uses part of the register. Return 1339 it in the structure passed in. */ 1340static int 1341find_regno_partial (rtx *ptr, void *data) 1342{ 1343 find_regno_partial_param *param = (find_regno_partial_param *)data; 1344 unsigned reg = param->regno_to_find; 1345 param->retval = NULL_RTX; 1346 1347 if (*ptr == NULL_RTX) 1348 return 0; 1349 1350 switch (GET_CODE (*ptr)) 1351 { 1352 case ZERO_EXTRACT: 1353 case SIGN_EXTRACT: 1354 case STRICT_LOW_PART: 1355 if (GET_CODE (XEXP (*ptr, 0)) == REG && REGNO (XEXP (*ptr, 0)) == reg) 1356 { 1357 param->retval = XEXP (*ptr, 0); 1358 return 1; 1359 } 1360 break; 1361 1362 case SUBREG: 1363 if (GET_CODE (SUBREG_REG (*ptr)) == REG 1364 && REGNO (SUBREG_REG (*ptr)) == reg) 1365 { 1366 param->retval = SUBREG_REG (*ptr); 1367 return 1; 1368 } 1369 break; 1370 1371 default: 1372 break; 1373 } 1374 1375 return 0; 1376} 1377 1378/* Process all immediate successors of the entry block looking for pseudo 1379 registers which are live on entry. Find all of those whose first 1380 instance is a partial register reference of some kind, and initialize 1381 them to 0 after the entry block. This will prevent bit sets within 1382 registers whose value is unknown, and may contain some kind of sticky 1383 bits we don't want. */ 1384 1385int 1386initialize_uninitialized_subregs (void) 1387{ 1388 rtx insn; 1389 edge e; 1390 int reg, did_something = 0; 1391 find_regno_partial_param param; 1392 1393 for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next) 1394 { 1395 basic_block bb = e->dest; 1396 regset map = bb->global_live_at_start; 1397 EXECUTE_IF_SET_IN_REG_SET (map, 1398 FIRST_PSEUDO_REGISTER, reg, 1399 { 1400 int uid = REGNO_FIRST_UID (reg); 1401 rtx i; 1402 1403 /* Find an insn which mentions the register we are looking for. 1404 Its preferable to have an instance of the register's rtl since 1405 there may be various flags set which we need to duplicate. 1406 If we can't find it, its probably an automatic whose initial 1407 value doesn't matter, or hopefully something we don't care about. */ 1408 for (i = get_insns (); i && INSN_UID (i) != uid; i = NEXT_INSN (i)) 1409 ; 1410 if (i != NULL_RTX) 1411 { 1412 /* Found the insn, now get the REG rtx, if we can. */ 1413 param.regno_to_find = reg; 1414 for_each_rtx (&i, find_regno_partial, ¶m); 1415 if (param.retval != NULL_RTX) 1416 { 1417 start_sequence (); 1418 emit_move_insn (param.retval, 1419 CONST0_RTX (GET_MODE (param.retval))); 1420 insn = get_insns (); 1421 end_sequence (); 1422 insert_insn_on_edge (insn, e); 1423 did_something = 1; 1424 } 1425 } 1426 }); 1427 } 1428 1429 if (did_something) 1430 commit_edge_insertions (); 1431 return did_something; 1432} 1433 1434 1435/* Subroutines of life analysis. */ 1436 1437/* Allocate the permanent data structures that represent the results 1438 of life analysis. Not static since used also for stupid life analysis. */ 1439 1440void 1441allocate_bb_life_data (void) 1442{ 1443 basic_block bb; 1444 1445 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 1446 { 1447 bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack); 1448 bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack); 1449 } 1450 1451 regs_live_at_setjmp = OBSTACK_ALLOC_REG_SET (&flow_obstack); 1452} 1453 1454void 1455allocate_reg_life_data (void) 1456{ 1457 int i; 1458 1459 max_regno = max_reg_num (); 1460 1461 /* Recalculate the register space, in case it has grown. Old style 1462 vector oriented regsets would set regset_{size,bytes} here also. */ 1463 allocate_reg_info (max_regno, FALSE, FALSE); 1464 1465 /* Reset all the data we'll collect in propagate_block and its 1466 subroutines. */ 1467 for (i = 0; i < max_regno; i++) 1468 { 1469 REG_N_SETS (i) = 0; 1470 REG_N_REFS (i) = 0; 1471 REG_N_DEATHS (i) = 0; 1472 REG_N_CALLS_CROSSED (i) = 0; 1473 REG_LIVE_LENGTH (i) = 0; 1474 REG_FREQ (i) = 0; 1475 REG_BASIC_BLOCK (i) = REG_BLOCK_UNKNOWN; 1476 } 1477} 1478 1479/* Delete dead instructions for propagate_block. */ 1480 1481static void 1482propagate_block_delete_insn (rtx insn) 1483{ 1484 rtx inote = find_reg_note (insn, REG_LABEL, NULL_RTX); 1485 1486 /* If the insn referred to a label, and that label was attached to 1487 an ADDR_VEC, it's safe to delete the ADDR_VEC. In fact, it's 1488 pretty much mandatory to delete it, because the ADDR_VEC may be 1489 referencing labels that no longer exist. 1490 1491 INSN may reference a deleted label, particularly when a jump 1492 table has been optimized into a direct jump. There's no 1493 real good way to fix up the reference to the deleted label 1494 when the label is deleted, so we just allow it here. */ 1495 1496 if (inote && GET_CODE (inote) == CODE_LABEL) 1497 { 1498 rtx label = XEXP (inote, 0); 1499 rtx next; 1500 1501 /* The label may be forced if it has been put in the constant 1502 pool. If that is the only use we must discard the table 1503 jump following it, but not the label itself. */ 1504 if (LABEL_NUSES (label) == 1 + LABEL_PRESERVE_P (label) 1505 && (next = next_nonnote_insn (label)) != NULL 1506 && GET_CODE (next) == JUMP_INSN 1507 && (GET_CODE (PATTERN (next)) == ADDR_VEC 1508 || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC)) 1509 { 1510 rtx pat = PATTERN (next); 1511 int diff_vec_p = GET_CODE (pat) == ADDR_DIFF_VEC; 1512 int len = XVECLEN (pat, diff_vec_p); 1513 int i; 1514 1515 for (i = 0; i < len; i++) 1516 LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0))--; 1517 1518 delete_insn_and_edges (next); 1519 ndead++; 1520 } 1521 } 1522 1523 delete_insn_and_edges (insn); 1524 ndead++; 1525} 1526 1527/* Delete dead libcalls for propagate_block. Return the insn 1528 before the libcall. */ 1529 1530static rtx 1531propagate_block_delete_libcall (rtx insn, rtx note) 1532{ 1533 rtx first = XEXP (note, 0); 1534 rtx before = PREV_INSN (first); 1535 1536 delete_insn_chain_and_edges (first, insn); 1537 ndead++; 1538 return before; 1539} 1540 1541/* Update the life-status of regs for one insn. Return the previous insn. */ 1542 1543rtx 1544propagate_one_insn (struct propagate_block_info *pbi, rtx insn) 1545{ 1546 rtx prev = PREV_INSN (insn); 1547 int flags = pbi->flags; 1548 int insn_is_dead = 0; 1549 int libcall_is_dead = 0; 1550 rtx note; 1551 int i; 1552 1553 if (! INSN_P (insn)) 1554 return prev; 1555 1556 note = find_reg_note (insn, REG_RETVAL, NULL_RTX); 1557 if (flags & PROP_SCAN_DEAD_CODE) 1558 { 1559 insn_is_dead = insn_dead_p (pbi, PATTERN (insn), 0, REG_NOTES (insn)); 1560 libcall_is_dead = (insn_is_dead && note != 0 1561 && libcall_dead_p (pbi, note, insn)); 1562 } 1563 1564 /* If an instruction consists of just dead store(s) on final pass, 1565 delete it. */ 1566 if ((flags & PROP_KILL_DEAD_CODE) && insn_is_dead) 1567 { 1568 /* If we're trying to delete a prologue or epilogue instruction 1569 that isn't flagged as possibly being dead, something is wrong. 1570 But if we are keeping the stack pointer depressed, we might well 1571 be deleting insns that are used to compute the amount to update 1572 it by, so they are fine. */ 1573 if (reload_completed 1574 && !(TREE_CODE (TREE_TYPE (current_function_decl)) == FUNCTION_TYPE 1575 && (TYPE_RETURNS_STACK_DEPRESSED 1576 (TREE_TYPE (current_function_decl)))) 1577 && (((HAVE_epilogue || HAVE_prologue) 1578 && prologue_epilogue_contains (insn)) 1579 || (HAVE_sibcall_epilogue 1580 && sibcall_epilogue_contains (insn))) 1581 && find_reg_note (insn, REG_MAYBE_DEAD, NULL_RTX) == 0) 1582 fatal_insn ("Attempt to delete prologue/epilogue insn:", insn); 1583 1584 /* Record sets. Do this even for dead instructions, since they 1585 would have killed the values if they hadn't been deleted. */ 1586 mark_set_regs (pbi, PATTERN (insn), insn); 1587 1588 /* CC0 is now known to be dead. Either this insn used it, 1589 in which case it doesn't anymore, or clobbered it, 1590 so the next insn can't use it. */ 1591 pbi->cc0_live = 0; 1592 1593 if (libcall_is_dead) 1594 prev = propagate_block_delete_libcall (insn, note); 1595 else 1596 { 1597 1598 /* If INSN contains a RETVAL note and is dead, but the libcall 1599 as a whole is not dead, then we want to remove INSN, but 1600 not the whole libcall sequence. 1601 1602 However, we need to also remove the dangling REG_LIBCALL 1603 note so that we do not have mis-matched LIBCALL/RETVAL 1604 notes. In theory we could find a new location for the 1605 REG_RETVAL note, but it hardly seems worth the effort. 1606 1607 NOTE at this point will be the RETVAL note if it exists. */ 1608 if (note) 1609 { 1610 rtx libcall_note; 1611 1612 libcall_note 1613 = find_reg_note (XEXP (note, 0), REG_LIBCALL, NULL_RTX); 1614 remove_note (XEXP (note, 0), libcall_note); 1615 } 1616 1617 /* Similarly if INSN contains a LIBCALL note, remove the 1618 dangling REG_RETVAL note. */ 1619 note = find_reg_note (insn, REG_LIBCALL, NULL_RTX); 1620 if (note) 1621 { 1622 rtx retval_note; 1623 1624 retval_note 1625 = find_reg_note (XEXP (note, 0), REG_RETVAL, NULL_RTX); 1626 remove_note (XEXP (note, 0), retval_note); 1627 } 1628 1629 /* Now delete INSN. */ 1630 propagate_block_delete_insn (insn); 1631 } 1632 1633 return prev; 1634 } 1635 1636 /* See if this is an increment or decrement that can be merged into 1637 a following memory address. */ 1638#ifdef AUTO_INC_DEC 1639 { 1640 rtx x = single_set (insn); 1641 1642 /* Does this instruction increment or decrement a register? */ 1643 if ((flags & PROP_AUTOINC) 1644 && x != 0 1645 && GET_CODE (SET_DEST (x)) == REG 1646 && (GET_CODE (SET_SRC (x)) == PLUS 1647 || GET_CODE (SET_SRC (x)) == MINUS) 1648 && XEXP (SET_SRC (x), 0) == SET_DEST (x) 1649 && GET_CODE (XEXP (SET_SRC (x), 1)) == CONST_INT 1650 /* Ok, look for a following memory ref we can combine with. 1651 If one is found, change the memory ref to a PRE_INC 1652 or PRE_DEC, cancel this insn, and return 1. 1653 Return 0 if nothing has been done. */ 1654 && try_pre_increment_1 (pbi, insn)) 1655 return prev; 1656 } 1657#endif /* AUTO_INC_DEC */ 1658 1659 CLEAR_REG_SET (pbi->new_set); 1660 1661 /* If this is not the final pass, and this insn is copying the value of 1662 a library call and it's dead, don't scan the insns that perform the 1663 library call, so that the call's arguments are not marked live. */ 1664 if (libcall_is_dead) 1665 { 1666 /* Record the death of the dest reg. */ 1667 mark_set_regs (pbi, PATTERN (insn), insn); 1668 1669 insn = XEXP (note, 0); 1670 return PREV_INSN (insn); 1671 } 1672 else if (GET_CODE (PATTERN (insn)) == SET 1673 && SET_DEST (PATTERN (insn)) == stack_pointer_rtx 1674 && GET_CODE (SET_SRC (PATTERN (insn))) == PLUS 1675 && XEXP (SET_SRC (PATTERN (insn)), 0) == stack_pointer_rtx 1676 && GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 1)) == CONST_INT) 1677 /* We have an insn to pop a constant amount off the stack. 1678 (Such insns use PLUS regardless of the direction of the stack, 1679 and any insn to adjust the stack by a constant is always a pop.) 1680 These insns, if not dead stores, have no effect on life, though 1681 they do have an effect on the memory stores we are tracking. */ 1682 invalidate_mems_from_set (pbi, stack_pointer_rtx); 1683 else 1684 { 1685 rtx note; 1686 /* Any regs live at the time of a call instruction must not go 1687 in a register clobbered by calls. Find all regs now live and 1688 record this for them. */ 1689 1690 if (GET_CODE (insn) == CALL_INSN && (flags & PROP_REG_INFO)) 1691 EXECUTE_IF_SET_IN_REG_SET (pbi->reg_live, 0, i, 1692 { REG_N_CALLS_CROSSED (i)++; }); 1693 1694 /* Record sets. Do this even for dead instructions, since they 1695 would have killed the values if they hadn't been deleted. */ 1696 mark_set_regs (pbi, PATTERN (insn), insn); 1697 1698 if (GET_CODE (insn) == CALL_INSN) 1699 { 1700 regset live_at_end; 1701 bool sibcall_p; 1702 rtx note, cond; 1703 int i; 1704 1705 cond = NULL_RTX; 1706 if (GET_CODE (PATTERN (insn)) == COND_EXEC) 1707 cond = COND_EXEC_TEST (PATTERN (insn)); 1708 1709 /* Non-constant calls clobber memory, constant calls do not 1710 clobber memory, though they may clobber outgoing arguments 1711 on the stack. */ 1712 if (! CONST_OR_PURE_CALL_P (insn)) 1713 { 1714 free_EXPR_LIST_list (&pbi->mem_set_list); 1715 pbi->mem_set_list_len = 0; 1716 } 1717 else 1718 invalidate_mems_from_set (pbi, stack_pointer_rtx); 1719 1720 /* There may be extra registers to be clobbered. */ 1721 for (note = CALL_INSN_FUNCTION_USAGE (insn); 1722 note; 1723 note = XEXP (note, 1)) 1724 if (GET_CODE (XEXP (note, 0)) == CLOBBER) 1725 mark_set_1 (pbi, CLOBBER, XEXP (XEXP (note, 0), 0), 1726 cond, insn, pbi->flags); 1727 1728 /* Calls change all call-used and global registers; sibcalls do not 1729 clobber anything that must be preserved at end-of-function, 1730 except for return values. */ 1731 1732 sibcall_p = SIBLING_CALL_P (insn); 1733 live_at_end = EXIT_BLOCK_PTR->global_live_at_start; 1734 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1735 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i) 1736 && ! (sibcall_p 1737 && REGNO_REG_SET_P (live_at_end, i) 1738 && ! refers_to_regno_p (i, i+1, 1739 current_function_return_rtx, 1740 (rtx *) 0))) 1741 { 1742 enum rtx_code code = global_regs[i] ? SET : CLOBBER; 1743 /* We do not want REG_UNUSED notes for these registers. */ 1744 mark_set_1 (pbi, code, regno_reg_rtx[i], cond, insn, 1745 pbi->flags & ~(PROP_DEATH_NOTES | PROP_REG_INFO)); 1746 } 1747 } 1748 1749 /* If an insn doesn't use CC0, it becomes dead since we assume 1750 that every insn clobbers it. So show it dead here; 1751 mark_used_regs will set it live if it is referenced. */ 1752 pbi->cc0_live = 0; 1753 1754 /* Record uses. */ 1755 if (! insn_is_dead) 1756 mark_used_regs (pbi, PATTERN (insn), NULL_RTX, insn); 1757 if ((flags & PROP_EQUAL_NOTES) 1758 && ((note = find_reg_note (insn, REG_EQUAL, NULL_RTX)) 1759 || (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)))) 1760 mark_used_regs (pbi, XEXP (note, 0), NULL_RTX, insn); 1761 1762 /* Sometimes we may have inserted something before INSN (such as a move) 1763 when we make an auto-inc. So ensure we will scan those insns. */ 1764#ifdef AUTO_INC_DEC 1765 prev = PREV_INSN (insn); 1766#endif 1767 1768 if (! insn_is_dead && GET_CODE (insn) == CALL_INSN) 1769 { 1770 int i; 1771 rtx note, cond; 1772 1773 cond = NULL_RTX; 1774 if (GET_CODE (PATTERN (insn)) == COND_EXEC) 1775 cond = COND_EXEC_TEST (PATTERN (insn)); 1776 1777 /* Calls use their arguments, and may clobber memory which 1778 address involves some register. */ 1779 for (note = CALL_INSN_FUNCTION_USAGE (insn); 1780 note; 1781 note = XEXP (note, 1)) 1782 /* We find USE or CLOBBER entities in a FUNCTION_USAGE list: both 1783 of which mark_used_regs knows how to handle. */ 1784 mark_used_regs (pbi, XEXP (XEXP (note, 0), 0), cond, insn); 1785 1786 /* The stack ptr is used (honorarily) by a CALL insn. */ 1787 SET_REGNO_REG_SET (pbi->reg_live, STACK_POINTER_REGNUM); 1788 1789 /* Calls may also reference any of the global registers, 1790 so they are made live. */ 1791 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1792 if (global_regs[i]) 1793 mark_used_reg (pbi, regno_reg_rtx[i], cond, insn); 1794 } 1795 } 1796 1797 /* On final pass, update counts of how many insns in which each reg 1798 is live. */ 1799 if (flags & PROP_REG_INFO) 1800 EXECUTE_IF_SET_IN_REG_SET (pbi->reg_live, 0, i, 1801 { REG_LIVE_LENGTH (i)++; }); 1802 1803 return prev; 1804} 1805 1806/* Initialize a propagate_block_info struct for public consumption. 1807 Note that the structure itself is opaque to this file, but that 1808 the user can use the regsets provided here. */ 1809 1810struct propagate_block_info * 1811init_propagate_block_info (basic_block bb, regset live, regset local_set, 1812 regset cond_local_set, int flags) 1813{ 1814 struct propagate_block_info *pbi = xmalloc (sizeof (*pbi)); 1815 1816 pbi->bb = bb; 1817 pbi->reg_live = live; 1818 pbi->mem_set_list = NULL_RTX; 1819 pbi->mem_set_list_len = 0; 1820 pbi->local_set = local_set; 1821 pbi->cond_local_set = cond_local_set; 1822 pbi->cc0_live = 0; 1823 pbi->flags = flags; 1824 1825 if (flags & (PROP_LOG_LINKS | PROP_AUTOINC)) 1826 pbi->reg_next_use = xcalloc (max_reg_num (), sizeof (rtx)); 1827 else 1828 pbi->reg_next_use = NULL; 1829 1830 pbi->new_set = BITMAP_XMALLOC (); 1831 1832#ifdef HAVE_conditional_execution 1833 pbi->reg_cond_dead = splay_tree_new (splay_tree_compare_ints, NULL, 1834 free_reg_cond_life_info); 1835 pbi->reg_cond_reg = BITMAP_XMALLOC (); 1836 1837 /* If this block ends in a conditional branch, for each register 1838 live from one side of the branch and not the other, record the 1839 register as conditionally dead. */ 1840 if (GET_CODE (BB_END (bb)) == JUMP_INSN 1841 && any_condjump_p (BB_END (bb))) 1842 { 1843 regset_head diff_head; 1844 regset diff = INITIALIZE_REG_SET (diff_head); 1845 basic_block bb_true, bb_false; 1846 int i; 1847 1848 /* Identify the successor blocks. */ 1849 bb_true = bb->succ->dest; 1850 if (bb->succ->succ_next != NULL) 1851 { 1852 bb_false = bb->succ->succ_next->dest; 1853 1854 if (bb->succ->flags & EDGE_FALLTHRU) 1855 { 1856 basic_block t = bb_false; 1857 bb_false = bb_true; 1858 bb_true = t; 1859 } 1860 else if (! (bb->succ->succ_next->flags & EDGE_FALLTHRU)) 1861 abort (); 1862 } 1863 else 1864 { 1865 /* This can happen with a conditional jump to the next insn. */ 1866 if (JUMP_LABEL (BB_END (bb)) != BB_HEAD (bb_true)) 1867 abort (); 1868 1869 /* Simplest way to do nothing. */ 1870 bb_false = bb_true; 1871 } 1872 1873 /* Compute which register lead different lives in the successors. */ 1874 if (bitmap_operation (diff, bb_true->global_live_at_start, 1875 bb_false->global_live_at_start, BITMAP_XOR)) 1876 { 1877 /* Extract the condition from the branch. */ 1878 rtx set_src = SET_SRC (pc_set (BB_END (bb))); 1879 rtx cond_true = XEXP (set_src, 0); 1880 rtx reg = XEXP (cond_true, 0); 1881 1882 if (GET_CODE (reg) == SUBREG) 1883 reg = SUBREG_REG (reg); 1884 1885 /* We can only track conditional lifetimes if the condition is 1886 in the form of a comparison of a register against zero. 1887 If the condition is more complex than that, then it is safe 1888 not to record any information. */ 1889 if (GET_CODE (reg) == REG 1890 && XEXP (cond_true, 1) == const0_rtx) 1891 { 1892 rtx cond_false 1893 = gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond_true)), 1894 GET_MODE (cond_true), XEXP (cond_true, 0), 1895 XEXP (cond_true, 1)); 1896 if (GET_CODE (XEXP (set_src, 1)) == PC) 1897 { 1898 rtx t = cond_false; 1899 cond_false = cond_true; 1900 cond_true = t; 1901 } 1902 1903 SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (reg)); 1904 1905 /* For each such register, mark it conditionally dead. */ 1906 EXECUTE_IF_SET_IN_REG_SET 1907 (diff, 0, i, 1908 { 1909 struct reg_cond_life_info *rcli; 1910 rtx cond; 1911 1912 rcli = xmalloc (sizeof (*rcli)); 1913 1914 if (REGNO_REG_SET_P (bb_true->global_live_at_start, i)) 1915 cond = cond_false; 1916 else 1917 cond = cond_true; 1918 rcli->condition = cond; 1919 rcli->stores = const0_rtx; 1920 rcli->orig_condition = cond; 1921 1922 splay_tree_insert (pbi->reg_cond_dead, i, 1923 (splay_tree_value) rcli); 1924 }); 1925 } 1926 } 1927 1928 FREE_REG_SET (diff); 1929 } 1930#endif 1931 1932 /* If this block has no successors, any stores to the frame that aren't 1933 used later in the block are dead. So make a pass over the block 1934 recording any such that are made and show them dead at the end. We do 1935 a very conservative and simple job here. */ 1936 if (optimize 1937 && ! (TREE_CODE (TREE_TYPE (current_function_decl)) == FUNCTION_TYPE 1938 && (TYPE_RETURNS_STACK_DEPRESSED 1939 (TREE_TYPE (current_function_decl)))) 1940 && (flags & PROP_SCAN_DEAD_STORES) 1941 && (bb->succ == NULL 1942 || (bb->succ->succ_next == NULL 1943 && bb->succ->dest == EXIT_BLOCK_PTR 1944 && ! current_function_calls_eh_return))) 1945 { 1946 rtx insn, set; 1947 for (insn = BB_END (bb); insn != BB_HEAD (bb); insn = PREV_INSN (insn)) 1948 if (GET_CODE (insn) == INSN 1949 && (set = single_set (insn)) 1950 && GET_CODE (SET_DEST (set)) == MEM) 1951 { 1952 rtx mem = SET_DEST (set); 1953 rtx canon_mem = canon_rtx (mem); 1954 1955 if (XEXP (canon_mem, 0) == frame_pointer_rtx 1956 || (GET_CODE (XEXP (canon_mem, 0)) == PLUS 1957 && XEXP (XEXP (canon_mem, 0), 0) == frame_pointer_rtx 1958 && GET_CODE (XEXP (XEXP (canon_mem, 0), 1)) == CONST_INT)) 1959 add_to_mem_set_list (pbi, canon_mem); 1960 } 1961 } 1962 1963 return pbi; 1964} 1965 1966/* Release a propagate_block_info struct. */ 1967 1968void 1969free_propagate_block_info (struct propagate_block_info *pbi) 1970{ 1971 free_EXPR_LIST_list (&pbi->mem_set_list); 1972 1973 BITMAP_XFREE (pbi->new_set); 1974 1975#ifdef HAVE_conditional_execution 1976 splay_tree_delete (pbi->reg_cond_dead); 1977 BITMAP_XFREE (pbi->reg_cond_reg); 1978#endif 1979 1980 if (pbi->reg_next_use) 1981 free (pbi->reg_next_use); 1982 1983 free (pbi); 1984} 1985 1986/* Compute the registers live at the beginning of a basic block BB from 1987 those live at the end. 1988 1989 When called, REG_LIVE contains those live at the end. On return, it 1990 contains those live at the beginning. 1991 1992 LOCAL_SET, if non-null, will be set with all registers killed 1993 unconditionally by this basic block. 1994 Likewise, COND_LOCAL_SET, if non-null, will be set with all registers 1995 killed conditionally by this basic block. If there is any unconditional 1996 set of a register, then the corresponding bit will be set in LOCAL_SET 1997 and cleared in COND_LOCAL_SET. 1998 It is valid for LOCAL_SET and COND_LOCAL_SET to be the same set. In this 1999 case, the resulting set will be equal to the union of the two sets that 2000 would otherwise be computed. 2001 2002 Return nonzero if an INSN is deleted (i.e. by dead code removal). */ 2003 2004int 2005propagate_block (basic_block bb, regset live, regset local_set, 2006 regset cond_local_set, int flags) 2007{ 2008 struct propagate_block_info *pbi; 2009 rtx insn, prev; 2010 int changed; 2011 2012 pbi = init_propagate_block_info (bb, live, local_set, cond_local_set, flags); 2013 2014 if (flags & PROP_REG_INFO) 2015 { 2016 int i; 2017 2018 /* Process the regs live at the end of the block. 2019 Mark them as not local to any one basic block. */ 2020 EXECUTE_IF_SET_IN_REG_SET (live, 0, i, 2021 { REG_BASIC_BLOCK (i) = REG_BLOCK_GLOBAL; }); 2022 } 2023 2024 /* Scan the block an insn at a time from end to beginning. */ 2025 2026 changed = 0; 2027 for (insn = BB_END (bb); ; insn = prev) 2028 { 2029 /* If this is a call to `setjmp' et al, warn if any 2030 non-volatile datum is live. */ 2031 if ((flags & PROP_REG_INFO) 2032 && GET_CODE (insn) == CALL_INSN 2033 && find_reg_note (insn, REG_SETJMP, NULL)) 2034 IOR_REG_SET (regs_live_at_setjmp, pbi->reg_live); 2035 2036 prev = propagate_one_insn (pbi, insn); 2037 if (!prev) 2038 changed |= insn != get_insns (); 2039 else 2040 changed |= NEXT_INSN (prev) != insn; 2041 2042 if (insn == BB_HEAD (bb)) 2043 break; 2044 } 2045 2046 free_propagate_block_info (pbi); 2047 2048 return changed; 2049} 2050 2051/* Return 1 if X (the body of an insn, or part of it) is just dead stores 2052 (SET expressions whose destinations are registers dead after the insn). 2053 NEEDED is the regset that says which regs are alive after the insn. 2054 2055 Unless CALL_OK is nonzero, an insn is needed if it contains a CALL. 2056 2057 If X is the entire body of an insn, NOTES contains the reg notes 2058 pertaining to the insn. */ 2059 2060static int 2061insn_dead_p (struct propagate_block_info *pbi, rtx x, int call_ok, 2062 rtx notes ATTRIBUTE_UNUSED) 2063{ 2064 enum rtx_code code = GET_CODE (x); 2065 2066 /* Don't eliminate insns that may trap. */ 2067 if (flag_non_call_exceptions && may_trap_p (x)) 2068 return 0; 2069 2070#ifdef AUTO_INC_DEC 2071 /* As flow is invoked after combine, we must take existing AUTO_INC 2072 expressions into account. */ 2073 for (; notes; notes = XEXP (notes, 1)) 2074 { 2075 if (REG_NOTE_KIND (notes) == REG_INC) 2076 { 2077 int regno = REGNO (XEXP (notes, 0)); 2078 2079 /* Don't delete insns to set global regs. */ 2080 if ((regno < FIRST_PSEUDO_REGISTER && global_regs[regno]) 2081 || REGNO_REG_SET_P (pbi->reg_live, regno)) 2082 return 0; 2083 } 2084 } 2085#endif 2086 2087 /* If setting something that's a reg or part of one, 2088 see if that register's altered value will be live. */ 2089 2090 if (code == SET) 2091 { 2092 rtx r = SET_DEST (x); 2093 2094#ifdef HAVE_cc0 2095 if (GET_CODE (r) == CC0) 2096 return ! pbi->cc0_live; 2097#endif 2098 2099 /* A SET that is a subroutine call cannot be dead. */ 2100 if (GET_CODE (SET_SRC (x)) == CALL) 2101 { 2102 if (! call_ok) 2103 return 0; 2104 } 2105 2106 /* Don't eliminate loads from volatile memory or volatile asms. */ 2107 else if (volatile_refs_p (SET_SRC (x))) 2108 return 0; 2109 2110 if (GET_CODE (r) == MEM) 2111 { 2112 rtx temp, canon_r; 2113 2114 if (MEM_VOLATILE_P (r) || GET_MODE (r) == BLKmode) 2115 return 0; 2116 2117 canon_r = canon_rtx (r); 2118 2119 /* Walk the set of memory locations we are currently tracking 2120 and see if one is an identical match to this memory location. 2121 If so, this memory write is dead (remember, we're walking 2122 backwards from the end of the block to the start). Since 2123 rtx_equal_p does not check the alias set or flags, we also 2124 must have the potential for them to conflict (anti_dependence). */ 2125 for (temp = pbi->mem_set_list; temp != 0; temp = XEXP (temp, 1)) 2126 if (unchanging_anti_dependence (r, XEXP (temp, 0))) 2127 { 2128 rtx mem = XEXP (temp, 0); 2129 2130 if (rtx_equal_p (XEXP (canon_r, 0), XEXP (mem, 0)) 2131 && (GET_MODE_SIZE (GET_MODE (canon_r)) 2132 <= GET_MODE_SIZE (GET_MODE (mem)))) 2133 return 1; 2134 2135#ifdef AUTO_INC_DEC 2136 /* Check if memory reference matches an auto increment. Only 2137 post increment/decrement or modify are valid. */ 2138 if (GET_MODE (mem) == GET_MODE (r) 2139 && (GET_CODE (XEXP (mem, 0)) == POST_DEC 2140 || GET_CODE (XEXP (mem, 0)) == POST_INC 2141 || GET_CODE (XEXP (mem, 0)) == POST_MODIFY) 2142 && GET_MODE (XEXP (mem, 0)) == GET_MODE (r) 2143 && rtx_equal_p (XEXP (XEXP (mem, 0), 0), XEXP (r, 0))) 2144 return 1; 2145#endif 2146 } 2147 } 2148 else 2149 { 2150 while (GET_CODE (r) == SUBREG 2151 || GET_CODE (r) == STRICT_LOW_PART 2152 || GET_CODE (r) == ZERO_EXTRACT) 2153 r = XEXP (r, 0); 2154 2155 if (GET_CODE (r) == REG) 2156 { 2157 int regno = REGNO (r); 2158 2159 /* Obvious. */ 2160 if (REGNO_REG_SET_P (pbi->reg_live, regno)) 2161 return 0; 2162 2163 /* If this is a hard register, verify that subsequent 2164 words are not needed. */ 2165 if (regno < FIRST_PSEUDO_REGISTER) 2166 { 2167 int n = HARD_REGNO_NREGS (regno, GET_MODE (r)); 2168 2169 while (--n > 0) 2170 if (REGNO_REG_SET_P (pbi->reg_live, regno+n)) 2171 return 0; 2172 } 2173 2174 /* Don't delete insns to set global regs. */ 2175 if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno]) 2176 return 0; 2177 2178 /* Make sure insns to set the stack pointer aren't deleted. */ 2179 if (regno == STACK_POINTER_REGNUM) 2180 return 0; 2181 2182 /* ??? These bits might be redundant with the force live bits 2183 in calculate_global_regs_live. We would delete from 2184 sequential sets; whether this actually affects real code 2185 for anything but the stack pointer I don't know. */ 2186 /* Make sure insns to set the frame pointer aren't deleted. */ 2187 if (regno == FRAME_POINTER_REGNUM 2188 && (! reload_completed || frame_pointer_needed)) 2189 return 0; 2190#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM 2191 if (regno == HARD_FRAME_POINTER_REGNUM 2192 && (! reload_completed || frame_pointer_needed)) 2193 return 0; 2194#endif 2195 2196#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM 2197 /* Make sure insns to set arg pointer are never deleted 2198 (if the arg pointer isn't fixed, there will be a USE 2199 for it, so we can treat it normally). */ 2200 if (regno == ARG_POINTER_REGNUM && fixed_regs[regno]) 2201 return 0; 2202#endif 2203 2204 /* Otherwise, the set is dead. */ 2205 return 1; 2206 } 2207 } 2208 } 2209 2210 /* If performing several activities, insn is dead if each activity 2211 is individually dead. Also, CLOBBERs and USEs can be ignored; a 2212 CLOBBER or USE that's inside a PARALLEL doesn't make the insn 2213 worth keeping. */ 2214 else if (code == PARALLEL) 2215 { 2216 int i = XVECLEN (x, 0); 2217 2218 for (i--; i >= 0; i--) 2219 if (GET_CODE (XVECEXP (x, 0, i)) != CLOBBER 2220 && GET_CODE (XVECEXP (x, 0, i)) != USE 2221 && ! insn_dead_p (pbi, XVECEXP (x, 0, i), call_ok, NULL_RTX)) 2222 return 0; 2223 2224 return 1; 2225 } 2226 2227 /* A CLOBBER of a pseudo-register that is dead serves no purpose. That 2228 is not necessarily true for hard registers until after reload. */ 2229 else if (code == CLOBBER) 2230 { 2231 if (GET_CODE (XEXP (x, 0)) == REG 2232 && (REGNO (XEXP (x, 0)) >= FIRST_PSEUDO_REGISTER 2233 || reload_completed) 2234 && ! REGNO_REG_SET_P (pbi->reg_live, REGNO (XEXP (x, 0)))) 2235 return 1; 2236 } 2237 2238 /* ??? A base USE is a historical relic. It ought not be needed anymore. 2239 Instances where it is still used are either (1) temporary and the USE 2240 escaped the pass, (2) cruft and the USE need not be emitted anymore, 2241 or (3) hiding bugs elsewhere that are not properly representing data 2242 flow. */ 2243 2244 return 0; 2245} 2246 2247/* If INSN is the last insn in a libcall, and assuming INSN is dead, 2248 return 1 if the entire library call is dead. 2249 This is true if INSN copies a register (hard or pseudo) 2250 and if the hard return reg of the call insn is dead. 2251 (The caller should have tested the destination of the SET inside 2252 INSN already for death.) 2253 2254 If this insn doesn't just copy a register, then we don't 2255 have an ordinary libcall. In that case, cse could not have 2256 managed to substitute the source for the dest later on, 2257 so we can assume the libcall is dead. 2258 2259 PBI is the block info giving pseudoregs live before this insn. 2260 NOTE is the REG_RETVAL note of the insn. */ 2261 2262static int 2263libcall_dead_p (struct propagate_block_info *pbi, rtx note, rtx insn) 2264{ 2265 rtx x = single_set (insn); 2266 2267 if (x) 2268 { 2269 rtx r = SET_SRC (x); 2270 2271 if (GET_CODE (r) == REG || GET_CODE (r) == SUBREG) 2272 { 2273 rtx call = XEXP (note, 0); 2274 rtx call_pat; 2275 int i; 2276 2277 /* Find the call insn. */ 2278 while (call != insn && GET_CODE (call) != CALL_INSN) 2279 call = NEXT_INSN (call); 2280 2281 /* If there is none, do nothing special, 2282 since ordinary death handling can understand these insns. */ 2283 if (call == insn) 2284 return 0; 2285 2286 /* See if the hard reg holding the value is dead. 2287 If this is a PARALLEL, find the call within it. */ 2288 call_pat = PATTERN (call); 2289 if (GET_CODE (call_pat) == PARALLEL) 2290 { 2291 for (i = XVECLEN (call_pat, 0) - 1; i >= 0; i--) 2292 if (GET_CODE (XVECEXP (call_pat, 0, i)) == SET 2293 && GET_CODE (SET_SRC (XVECEXP (call_pat, 0, i))) == CALL) 2294 break; 2295 2296 /* This may be a library call that is returning a value 2297 via invisible pointer. Do nothing special, since 2298 ordinary death handling can understand these insns. */ 2299 if (i < 0) 2300 return 0; 2301 2302 call_pat = XVECEXP (call_pat, 0, i); 2303 } 2304 2305 if (! insn_dead_p (pbi, call_pat, 1, REG_NOTES (call))) 2306 return 0; 2307 2308 while ((insn = PREV_INSN (insn)) != call) 2309 { 2310 if (! INSN_P (insn)) 2311 continue; 2312 if (! insn_dead_p (pbi, PATTERN (insn), 0, REG_NOTES (insn))) 2313 return 0; 2314 } 2315 return 1; 2316 } 2317 } 2318 return 0; 2319} 2320 2321/* Return 1 if register REGNO was used before it was set, i.e. if it is 2322 live at function entry. Don't count global register variables, variables 2323 in registers that can be used for function arg passing, or variables in 2324 fixed hard registers. */ 2325 2326int 2327regno_uninitialized (unsigned int regno) 2328{ 2329 if (n_basic_blocks == 0 2330 || (regno < FIRST_PSEUDO_REGISTER 2331 && (global_regs[regno] 2332 || fixed_regs[regno] 2333 || FUNCTION_ARG_REGNO_P (regno)))) 2334 return 0; 2335 2336 return REGNO_REG_SET_P (ENTRY_BLOCK_PTR->global_live_at_end, regno); 2337} 2338 2339/* 1 if register REGNO was alive at a place where `setjmp' was called 2340 and was set more than once or is an argument. 2341 Such regs may be clobbered by `longjmp'. */ 2342 2343int 2344regno_clobbered_at_setjmp (int regno) 2345{ 2346 if (n_basic_blocks == 0) 2347 return 0; 2348 2349 return ((REG_N_SETS (regno) > 1 2350 || REGNO_REG_SET_P (ENTRY_BLOCK_PTR->global_live_at_end, regno)) 2351 && REGNO_REG_SET_P (regs_live_at_setjmp, regno)); 2352} 2353 2354/* Add MEM to PBI->MEM_SET_LIST. MEM should be canonical. Respect the 2355 maximal list size; look for overlaps in mode and select the largest. */ 2356static void 2357add_to_mem_set_list (struct propagate_block_info *pbi, rtx mem) 2358{ 2359 rtx i; 2360 2361 /* We don't know how large a BLKmode store is, so we must not 2362 take them into consideration. */ 2363 if (GET_MODE (mem) == BLKmode) 2364 return; 2365 2366 for (i = pbi->mem_set_list; i ; i = XEXP (i, 1)) 2367 { 2368 rtx e = XEXP (i, 0); 2369 if (rtx_equal_p (XEXP (mem, 0), XEXP (e, 0))) 2370 { 2371 if (GET_MODE_SIZE (GET_MODE (mem)) > GET_MODE_SIZE (GET_MODE (e))) 2372 { 2373#ifdef AUTO_INC_DEC 2374 /* If we must store a copy of the mem, we can just modify 2375 the mode of the stored copy. */ 2376 if (pbi->flags & PROP_AUTOINC) 2377 PUT_MODE (e, GET_MODE (mem)); 2378 else 2379#endif 2380 XEXP (i, 0) = mem; 2381 } 2382 return; 2383 } 2384 } 2385 2386 if (pbi->mem_set_list_len < MAX_MEM_SET_LIST_LEN) 2387 { 2388#ifdef AUTO_INC_DEC 2389 /* Store a copy of mem, otherwise the address may be 2390 scrogged by find_auto_inc. */ 2391 if (pbi->flags & PROP_AUTOINC) 2392 mem = shallow_copy_rtx (mem); 2393#endif 2394 pbi->mem_set_list = alloc_EXPR_LIST (0, mem, pbi->mem_set_list); 2395 pbi->mem_set_list_len++; 2396 } 2397} 2398 2399/* INSN references memory, possibly using autoincrement addressing modes. 2400 Find any entries on the mem_set_list that need to be invalidated due 2401 to an address change. */ 2402 2403static int 2404invalidate_mems_from_autoinc (rtx *px, void *data) 2405{ 2406 rtx x = *px; 2407 struct propagate_block_info *pbi = data; 2408 2409 if (GET_RTX_CLASS (GET_CODE (x)) == 'a') 2410 { 2411 invalidate_mems_from_set (pbi, XEXP (x, 0)); 2412 return -1; 2413 } 2414 2415 return 0; 2416} 2417 2418/* EXP is a REG. Remove any dependent entries from pbi->mem_set_list. */ 2419 2420static void 2421invalidate_mems_from_set (struct propagate_block_info *pbi, rtx exp) 2422{ 2423 rtx temp = pbi->mem_set_list; 2424 rtx prev = NULL_RTX; 2425 rtx next; 2426 2427 while (temp) 2428 { 2429 next = XEXP (temp, 1); 2430 if (reg_overlap_mentioned_p (exp, XEXP (temp, 0))) 2431 { 2432 /* Splice this entry out of the list. */ 2433 if (prev) 2434 XEXP (prev, 1) = next; 2435 else 2436 pbi->mem_set_list = next; 2437 free_EXPR_LIST_node (temp); 2438 pbi->mem_set_list_len--; 2439 } 2440 else 2441 prev = temp; 2442 temp = next; 2443 } 2444} 2445 2446/* Process the registers that are set within X. Their bits are set to 2447 1 in the regset DEAD, because they are dead prior to this insn. 2448 2449 If INSN is nonzero, it is the insn being processed. 2450 2451 FLAGS is the set of operations to perform. */ 2452 2453static void 2454mark_set_regs (struct propagate_block_info *pbi, rtx x, rtx insn) 2455{ 2456 rtx cond = NULL_RTX; 2457 rtx link; 2458 enum rtx_code code; 2459 int flags = pbi->flags; 2460 2461 if (insn) 2462 for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) 2463 { 2464 if (REG_NOTE_KIND (link) == REG_INC) 2465 mark_set_1 (pbi, SET, XEXP (link, 0), 2466 (GET_CODE (x) == COND_EXEC 2467 ? COND_EXEC_TEST (x) : NULL_RTX), 2468 insn, flags); 2469 } 2470 retry: 2471 switch (code = GET_CODE (x)) 2472 { 2473 case SET: 2474 if (GET_CODE (XEXP (x, 1)) == ASM_OPERANDS) 2475 flags |= PROP_ASM_SCAN; 2476 /* Fall through */ 2477 case CLOBBER: 2478 mark_set_1 (pbi, code, SET_DEST (x), cond, insn, flags); 2479 return; 2480 2481 case COND_EXEC: 2482 cond = COND_EXEC_TEST (x); 2483 x = COND_EXEC_CODE (x); 2484 goto retry; 2485 2486 case PARALLEL: 2487 { 2488 int i; 2489 2490 /* We must scan forwards. If we have an asm, we need to set 2491 the PROP_ASM_SCAN flag before scanning the clobbers. */ 2492 for (i = 0; i < XVECLEN (x, 0); i++) 2493 { 2494 rtx sub = XVECEXP (x, 0, i); 2495 switch (code = GET_CODE (sub)) 2496 { 2497 case COND_EXEC: 2498 if (cond != NULL_RTX) 2499 abort (); 2500 2501 cond = COND_EXEC_TEST (sub); 2502 sub = COND_EXEC_CODE (sub); 2503 if (GET_CODE (sub) == SET) 2504 goto mark_set; 2505 if (GET_CODE (sub) == CLOBBER) 2506 goto mark_clob; 2507 break; 2508 2509 case SET: 2510 mark_set: 2511 if (GET_CODE (XEXP (sub, 1)) == ASM_OPERANDS) 2512 flags |= PROP_ASM_SCAN; 2513 /* Fall through */ 2514 case CLOBBER: 2515 mark_clob: 2516 mark_set_1 (pbi, code, SET_DEST (sub), cond, insn, flags); 2517 break; 2518 2519 case ASM_OPERANDS: 2520 flags |= PROP_ASM_SCAN; 2521 break; 2522 2523 default: 2524 break; 2525 } 2526 } 2527 break; 2528 } 2529 2530 default: 2531 break; 2532 } 2533} 2534 2535/* Process a single set, which appears in INSN. REG (which may not 2536 actually be a REG, it may also be a SUBREG, PARALLEL, etc.) is 2537 being set using the CODE (which may be SET, CLOBBER, or COND_EXEC). 2538 If the set is conditional (because it appear in a COND_EXEC), COND 2539 will be the condition. */ 2540 2541static void 2542mark_set_1 (struct propagate_block_info *pbi, enum rtx_code code, rtx reg, rtx cond, rtx insn, int flags) 2543{ 2544 int regno_first = -1, regno_last = -1; 2545 unsigned long not_dead = 0; 2546 int i; 2547 2548 /* Modifying just one hardware register of a multi-reg value or just a 2549 byte field of a register does not mean the value from before this insn 2550 is now dead. Of course, if it was dead after it's unused now. */ 2551 2552 switch (GET_CODE (reg)) 2553 { 2554 case PARALLEL: 2555 /* Some targets place small structures in registers for return values of 2556 functions. We have to detect this case specially here to get correct 2557 flow information. */ 2558 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--) 2559 if (XEXP (XVECEXP (reg, 0, i), 0) != 0) 2560 mark_set_1 (pbi, code, XEXP (XVECEXP (reg, 0, i), 0), cond, insn, 2561 flags); 2562 return; 2563 2564 case ZERO_EXTRACT: 2565 case SIGN_EXTRACT: 2566 case STRICT_LOW_PART: 2567 /* ??? Assumes STRICT_LOW_PART not used on multi-word registers. */ 2568 do 2569 reg = XEXP (reg, 0); 2570 while (GET_CODE (reg) == SUBREG 2571 || GET_CODE (reg) == ZERO_EXTRACT 2572 || GET_CODE (reg) == SIGN_EXTRACT 2573 || GET_CODE (reg) == STRICT_LOW_PART); 2574 if (GET_CODE (reg) == MEM) 2575 break; 2576 not_dead = (unsigned long) REGNO_REG_SET_P (pbi->reg_live, REGNO (reg)); 2577 /* Fall through. */ 2578 2579 case REG: 2580 regno_last = regno_first = REGNO (reg); 2581 if (regno_first < FIRST_PSEUDO_REGISTER) 2582 regno_last += HARD_REGNO_NREGS (regno_first, GET_MODE (reg)) - 1; 2583 break; 2584 2585 case SUBREG: 2586 if (GET_CODE (SUBREG_REG (reg)) == REG) 2587 { 2588 enum machine_mode outer_mode = GET_MODE (reg); 2589 enum machine_mode inner_mode = GET_MODE (SUBREG_REG (reg)); 2590 2591 /* Identify the range of registers affected. This is moderately 2592 tricky for hard registers. See alter_subreg. */ 2593 2594 regno_last = regno_first = REGNO (SUBREG_REG (reg)); 2595 if (regno_first < FIRST_PSEUDO_REGISTER) 2596 { 2597 regno_first += subreg_regno_offset (regno_first, inner_mode, 2598 SUBREG_BYTE (reg), 2599 outer_mode); 2600 regno_last = (regno_first 2601 + HARD_REGNO_NREGS (regno_first, outer_mode) - 1); 2602 2603 /* Since we've just adjusted the register number ranges, make 2604 sure REG matches. Otherwise some_was_live will be clear 2605 when it shouldn't have been, and we'll create incorrect 2606 REG_UNUSED notes. */ 2607 reg = gen_rtx_REG (outer_mode, regno_first); 2608 } 2609 else 2610 { 2611 /* If the number of words in the subreg is less than the number 2612 of words in the full register, we have a well-defined partial 2613 set. Otherwise the high bits are undefined. 2614 2615 This is only really applicable to pseudos, since we just took 2616 care of multi-word hard registers. */ 2617 if (((GET_MODE_SIZE (outer_mode) 2618 + UNITS_PER_WORD - 1) / UNITS_PER_WORD) 2619 < ((GET_MODE_SIZE (inner_mode) 2620 + UNITS_PER_WORD - 1) / UNITS_PER_WORD)) 2621 not_dead = (unsigned long) REGNO_REG_SET_P (pbi->reg_live, 2622 regno_first); 2623 2624 reg = SUBREG_REG (reg); 2625 } 2626 } 2627 else 2628 reg = SUBREG_REG (reg); 2629 break; 2630 2631 default: 2632 break; 2633 } 2634 2635 /* If this set is a MEM, then it kills any aliased writes. 2636 If this set is a REG, then it kills any MEMs which use the reg. */ 2637 if (optimize && (flags & PROP_SCAN_DEAD_STORES)) 2638 { 2639 if (GET_CODE (reg) == REG) 2640 invalidate_mems_from_set (pbi, reg); 2641 2642 /* If the memory reference had embedded side effects (autoincrement 2643 address modes. Then we may need to kill some entries on the 2644 memory set list. */ 2645 if (insn && GET_CODE (reg) == MEM) 2646 for_each_rtx (&PATTERN (insn), invalidate_mems_from_autoinc, pbi); 2647 2648 if (GET_CODE (reg) == MEM && ! side_effects_p (reg) 2649 /* ??? With more effort we could track conditional memory life. */ 2650 && ! cond) 2651 add_to_mem_set_list (pbi, canon_rtx (reg)); 2652 } 2653 2654 if (GET_CODE (reg) == REG 2655 && ! (regno_first == FRAME_POINTER_REGNUM 2656 && (! reload_completed || frame_pointer_needed)) 2657#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM 2658 && ! (regno_first == HARD_FRAME_POINTER_REGNUM 2659 && (! reload_completed || frame_pointer_needed)) 2660#endif 2661#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM 2662 && ! (regno_first == ARG_POINTER_REGNUM && fixed_regs[regno_first]) 2663#endif 2664 ) 2665 { 2666 int some_was_live = 0, some_was_dead = 0; 2667 2668 for (i = regno_first; i <= regno_last; ++i) 2669 { 2670 int needed_regno = REGNO_REG_SET_P (pbi->reg_live, i); 2671 if (pbi->local_set) 2672 { 2673 /* Order of the set operation matters here since both 2674 sets may be the same. */ 2675 CLEAR_REGNO_REG_SET (pbi->cond_local_set, i); 2676 if (cond != NULL_RTX 2677 && ! REGNO_REG_SET_P (pbi->local_set, i)) 2678 SET_REGNO_REG_SET (pbi->cond_local_set, i); 2679 else 2680 SET_REGNO_REG_SET (pbi->local_set, i); 2681 } 2682 if (code != CLOBBER) 2683 SET_REGNO_REG_SET (pbi->new_set, i); 2684 2685 some_was_live |= needed_regno; 2686 some_was_dead |= ! needed_regno; 2687 } 2688 2689#ifdef HAVE_conditional_execution 2690 /* Consider conditional death in deciding that the register needs 2691 a death note. */ 2692 if (some_was_live && ! not_dead 2693 /* The stack pointer is never dead. Well, not strictly true, 2694 but it's very difficult to tell from here. Hopefully 2695 combine_stack_adjustments will fix up the most egregious 2696 errors. */ 2697 && regno_first != STACK_POINTER_REGNUM) 2698 { 2699 for (i = regno_first; i <= regno_last; ++i) 2700 if (! mark_regno_cond_dead (pbi, i, cond)) 2701 not_dead |= ((unsigned long) 1) << (i - regno_first); 2702 } 2703#endif 2704 2705 /* Additional data to record if this is the final pass. */ 2706 if (flags & (PROP_LOG_LINKS | PROP_REG_INFO 2707 | PROP_DEATH_NOTES | PROP_AUTOINC)) 2708 { 2709 rtx y; 2710 int blocknum = pbi->bb->index; 2711 2712 y = NULL_RTX; 2713 if (flags & (PROP_LOG_LINKS | PROP_AUTOINC)) 2714 { 2715 y = pbi->reg_next_use[regno_first]; 2716 2717 /* The next use is no longer next, since a store intervenes. */ 2718 for (i = regno_first; i <= regno_last; ++i) 2719 pbi->reg_next_use[i] = 0; 2720 } 2721 2722 if (flags & PROP_REG_INFO) 2723 { 2724 for (i = regno_first; i <= regno_last; ++i) 2725 { 2726 /* Count (weighted) references, stores, etc. This counts a 2727 register twice if it is modified, but that is correct. */ 2728 REG_N_SETS (i) += 1; 2729 REG_N_REFS (i) += 1; 2730 REG_FREQ (i) += REG_FREQ_FROM_BB (pbi->bb); 2731 2732 /* The insns where a reg is live are normally counted 2733 elsewhere, but we want the count to include the insn 2734 where the reg is set, and the normal counting mechanism 2735 would not count it. */ 2736 REG_LIVE_LENGTH (i) += 1; 2737 } 2738 2739 /* If this is a hard reg, record this function uses the reg. */ 2740 if (regno_first < FIRST_PSEUDO_REGISTER) 2741 { 2742 for (i = regno_first; i <= regno_last; i++) 2743 regs_ever_live[i] = 1; 2744 if (flags & PROP_ASM_SCAN) 2745 for (i = regno_first; i <= regno_last; i++) 2746 regs_asm_clobbered[i] = 1; 2747 } 2748 else 2749 { 2750 /* Keep track of which basic blocks each reg appears in. */ 2751 if (REG_BASIC_BLOCK (regno_first) == REG_BLOCK_UNKNOWN) 2752 REG_BASIC_BLOCK (regno_first) = blocknum; 2753 else if (REG_BASIC_BLOCK (regno_first) != blocknum) 2754 REG_BASIC_BLOCK (regno_first) = REG_BLOCK_GLOBAL; 2755 } 2756 } 2757 2758 if (! some_was_dead) 2759 { 2760 if (flags & PROP_LOG_LINKS) 2761 { 2762 /* Make a logical link from the next following insn 2763 that uses this register, back to this insn. 2764 The following insns have already been processed. 2765 2766 We don't build a LOG_LINK for hard registers containing 2767 in ASM_OPERANDs. If these registers get replaced, 2768 we might wind up changing the semantics of the insn, 2769 even if reload can make what appear to be valid 2770 assignments later. 2771 2772 We don't build a LOG_LINK for global registers to 2773 or from a function call. We don't want to let 2774 combine think that it knows what is going on with 2775 global registers. */ 2776 if (y && (BLOCK_NUM (y) == blocknum) 2777 && (regno_first >= FIRST_PSEUDO_REGISTER 2778 || (asm_noperands (PATTERN (y)) < 0 2779 && ! ((GET_CODE (insn) == CALL_INSN 2780 || GET_CODE (y) == CALL_INSN) 2781 && global_regs[regno_first])))) 2782 LOG_LINKS (y) = alloc_INSN_LIST (insn, LOG_LINKS (y)); 2783 } 2784 } 2785 else if (not_dead) 2786 ; 2787 else if (! some_was_live) 2788 { 2789 if (flags & PROP_REG_INFO) 2790 REG_N_DEATHS (regno_first) += 1; 2791 2792 if (flags & PROP_DEATH_NOTES) 2793 { 2794 /* Note that dead stores have already been deleted 2795 when possible. If we get here, we have found a 2796 dead store that cannot be eliminated (because the 2797 same insn does something useful). Indicate this 2798 by marking the reg being set as dying here. */ 2799 REG_NOTES (insn) 2800 = alloc_EXPR_LIST (REG_UNUSED, reg, REG_NOTES (insn)); 2801 } 2802 } 2803 else 2804 { 2805 if (flags & PROP_DEATH_NOTES) 2806 { 2807 /* This is a case where we have a multi-word hard register 2808 and some, but not all, of the words of the register are 2809 needed in subsequent insns. Write REG_UNUSED notes 2810 for those parts that were not needed. This case should 2811 be rare. */ 2812 2813 for (i = regno_first; i <= regno_last; ++i) 2814 if (! REGNO_REG_SET_P (pbi->reg_live, i)) 2815 REG_NOTES (insn) 2816 = alloc_EXPR_LIST (REG_UNUSED, 2817 regno_reg_rtx[i], 2818 REG_NOTES (insn)); 2819 } 2820 } 2821 } 2822 2823 /* Mark the register as being dead. */ 2824 if (some_was_live 2825 /* The stack pointer is never dead. Well, not strictly true, 2826 but it's very difficult to tell from here. Hopefully 2827 combine_stack_adjustments will fix up the most egregious 2828 errors. */ 2829 && regno_first != STACK_POINTER_REGNUM) 2830 { 2831 for (i = regno_first; i <= regno_last; ++i) 2832 if (!(not_dead & (((unsigned long) 1) << (i - regno_first)))) 2833 CLEAR_REGNO_REG_SET (pbi->reg_live, i); 2834 } 2835 } 2836 else if (GET_CODE (reg) == REG) 2837 { 2838 if (flags & (PROP_LOG_LINKS | PROP_AUTOINC)) 2839 pbi->reg_next_use[regno_first] = 0; 2840 2841 if ((flags & PROP_REG_INFO) != 0 2842 && (flags & PROP_ASM_SCAN) != 0 2843 && regno_first < FIRST_PSEUDO_REGISTER) 2844 { 2845 for (i = regno_first; i <= regno_last; i++) 2846 regs_asm_clobbered[i] = 1; 2847 } 2848 } 2849 2850 /* If this is the last pass and this is a SCRATCH, show it will be dying 2851 here and count it. */ 2852 else if (GET_CODE (reg) == SCRATCH) 2853 { 2854 if (flags & PROP_DEATH_NOTES) 2855 REG_NOTES (insn) 2856 = alloc_EXPR_LIST (REG_UNUSED, reg, REG_NOTES (insn)); 2857 } 2858} 2859 2860#ifdef HAVE_conditional_execution 2861/* Mark REGNO conditionally dead. 2862 Return true if the register is now unconditionally dead. */ 2863 2864static int 2865mark_regno_cond_dead (struct propagate_block_info *pbi, int regno, rtx cond) 2866{ 2867 /* If this is a store to a predicate register, the value of the 2868 predicate is changing, we don't know that the predicate as seen 2869 before is the same as that seen after. Flush all dependent 2870 conditions from reg_cond_dead. This will make all such 2871 conditionally live registers unconditionally live. */ 2872 if (REGNO_REG_SET_P (pbi->reg_cond_reg, regno)) 2873 flush_reg_cond_reg (pbi, regno); 2874 2875 /* If this is an unconditional store, remove any conditional 2876 life that may have existed. */ 2877 if (cond == NULL_RTX) 2878 splay_tree_remove (pbi->reg_cond_dead, regno); 2879 else 2880 { 2881 splay_tree_node node; 2882 struct reg_cond_life_info *rcli; 2883 rtx ncond; 2884 2885 /* Otherwise this is a conditional set. Record that fact. 2886 It may have been conditionally used, or there may be a 2887 subsequent set with a complimentary condition. */ 2888 2889 node = splay_tree_lookup (pbi->reg_cond_dead, regno); 2890 if (node == NULL) 2891 { 2892 /* The register was unconditionally live previously. 2893 Record the current condition as the condition under 2894 which it is dead. */ 2895 rcli = xmalloc (sizeof (*rcli)); 2896 rcli->condition = cond; 2897 rcli->stores = cond; 2898 rcli->orig_condition = const0_rtx; 2899 splay_tree_insert (pbi->reg_cond_dead, regno, 2900 (splay_tree_value) rcli); 2901 2902 SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (XEXP (cond, 0))); 2903 2904 /* Not unconditionally dead. */ 2905 return 0; 2906 } 2907 else 2908 { 2909 /* The register was conditionally live previously. 2910 Add the new condition to the old. */ 2911 rcli = (struct reg_cond_life_info *) node->value; 2912 ncond = rcli->condition; 2913 ncond = ior_reg_cond (ncond, cond, 1); 2914 if (rcli->stores == const0_rtx) 2915 rcli->stores = cond; 2916 else if (rcli->stores != const1_rtx) 2917 rcli->stores = ior_reg_cond (rcli->stores, cond, 1); 2918 2919 /* If the register is now unconditionally dead, remove the entry 2920 in the splay_tree. A register is unconditionally dead if the 2921 dead condition ncond is true. A register is also unconditionally 2922 dead if the sum of all conditional stores is an unconditional 2923 store (stores is true), and the dead condition is identically the 2924 same as the original dead condition initialized at the end of 2925 the block. This is a pointer compare, not an rtx_equal_p 2926 compare. */ 2927 if (ncond == const1_rtx 2928 || (ncond == rcli->orig_condition && rcli->stores == const1_rtx)) 2929 splay_tree_remove (pbi->reg_cond_dead, regno); 2930 else 2931 { 2932 rcli->condition = ncond; 2933 2934 SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (XEXP (cond, 0))); 2935 2936 /* Not unconditionally dead. */ 2937 return 0; 2938 } 2939 } 2940 } 2941 2942 return 1; 2943} 2944 2945/* Called from splay_tree_delete for pbi->reg_cond_life. */ 2946 2947static void 2948free_reg_cond_life_info (splay_tree_value value) 2949{ 2950 struct reg_cond_life_info *rcli = (struct reg_cond_life_info *) value; 2951 free (rcli); 2952} 2953 2954/* Helper function for flush_reg_cond_reg. */ 2955 2956static int 2957flush_reg_cond_reg_1 (splay_tree_node node, void *data) 2958{ 2959 struct reg_cond_life_info *rcli; 2960 int *xdata = (int *) data; 2961 unsigned int regno = xdata[0]; 2962 2963 /* Don't need to search if last flushed value was farther on in 2964 the in-order traversal. */ 2965 if (xdata[1] >= (int) node->key) 2966 return 0; 2967 2968 /* Splice out portions of the expression that refer to regno. */ 2969 rcli = (struct reg_cond_life_info *) node->value; 2970 rcli->condition = elim_reg_cond (rcli->condition, regno); 2971 if (rcli->stores != const0_rtx && rcli->stores != const1_rtx) 2972 rcli->stores = elim_reg_cond (rcli->stores, regno); 2973 2974 /* If the entire condition is now false, signal the node to be removed. */ 2975 if (rcli->condition == const0_rtx) 2976 { 2977 xdata[1] = node->key; 2978 return -1; 2979 } 2980 else if (rcli->condition == const1_rtx) 2981 abort (); 2982 2983 return 0; 2984} 2985 2986/* Flush all (sub) expressions referring to REGNO from REG_COND_LIVE. */ 2987 2988static void 2989flush_reg_cond_reg (struct propagate_block_info *pbi, int regno) 2990{ 2991 int pair[2]; 2992 2993 pair[0] = regno; 2994 pair[1] = -1; 2995 while (splay_tree_foreach (pbi->reg_cond_dead, 2996 flush_reg_cond_reg_1, pair) == -1) 2997 splay_tree_remove (pbi->reg_cond_dead, pair[1]); 2998 2999 CLEAR_REGNO_REG_SET (pbi->reg_cond_reg, regno); 3000} 3001 3002/* Logical arithmetic on predicate conditions. IOR, NOT and AND. 3003 For ior/and, the ADD flag determines whether we want to add the new 3004 condition X to the old one unconditionally. If it is zero, we will 3005 only return a new expression if X allows us to simplify part of 3006 OLD, otherwise we return NULL to the caller. 3007 If ADD is nonzero, we will return a new condition in all cases. The 3008 toplevel caller of one of these functions should always pass 1 for 3009 ADD. */ 3010 3011static rtx 3012ior_reg_cond (rtx old, rtx x, int add) 3013{ 3014 rtx op0, op1; 3015 3016 if (GET_RTX_CLASS (GET_CODE (old)) == '<') 3017 { 3018 if (GET_RTX_CLASS (GET_CODE (x)) == '<' 3019 && REVERSE_CONDEXEC_PREDICATES_P (GET_CODE (x), GET_CODE (old)) 3020 && REGNO (XEXP (x, 0)) == REGNO (XEXP (old, 0))) 3021 return const1_rtx; 3022 if (GET_CODE (x) == GET_CODE (old) 3023 && REGNO (XEXP (x, 0)) == REGNO (XEXP (old, 0))) 3024 return old; 3025 if (! add) 3026 return NULL; 3027 return gen_rtx_IOR (0, old, x); 3028 } 3029 3030 switch (GET_CODE (old)) 3031 { 3032 case IOR: 3033 op0 = ior_reg_cond (XEXP (old, 0), x, 0); 3034 op1 = ior_reg_cond (XEXP (old, 1), x, 0); 3035 if (op0 != NULL || op1 != NULL) 3036 { 3037 if (op0 == const0_rtx) 3038 return op1 ? op1 : gen_rtx_IOR (0, XEXP (old, 1), x); 3039 if (op1 == const0_rtx) 3040 return op0 ? op0 : gen_rtx_IOR (0, XEXP (old, 0), x); 3041 if (op0 == const1_rtx || op1 == const1_rtx) 3042 return const1_rtx; 3043 if (op0 == NULL) 3044 op0 = gen_rtx_IOR (0, XEXP (old, 0), x); 3045 else if (rtx_equal_p (x, op0)) 3046 /* (x | A) | x ~ (x | A). */ 3047 return old; 3048 if (op1 == NULL) 3049 op1 = gen_rtx_IOR (0, XEXP (old, 1), x); 3050 else if (rtx_equal_p (x, op1)) 3051 /* (A | x) | x ~ (A | x). */ 3052 return old; 3053 return gen_rtx_IOR (0, op0, op1); 3054 } 3055 if (! add) 3056 return NULL; 3057 return gen_rtx_IOR (0, old, x); 3058 3059 case AND: 3060 op0 = ior_reg_cond (XEXP (old, 0), x, 0); 3061 op1 = ior_reg_cond (XEXP (old, 1), x, 0); 3062 if (op0 != NULL || op1 != NULL) 3063 { 3064 if (op0 == const1_rtx) 3065 return op1 ? op1 : gen_rtx_IOR (0, XEXP (old, 1), x); 3066 if (op1 == const1_rtx) 3067 return op0 ? op0 : gen_rtx_IOR (0, XEXP (old, 0), x); 3068 if (op0 == const0_rtx || op1 == const0_rtx) 3069 return const0_rtx; 3070 if (op0 == NULL) 3071 op0 = gen_rtx_IOR (0, XEXP (old, 0), x); 3072 else if (rtx_equal_p (x, op0)) 3073 /* (x & A) | x ~ x. */ 3074 return op0; 3075 if (op1 == NULL) 3076 op1 = gen_rtx_IOR (0, XEXP (old, 1), x); 3077 else if (rtx_equal_p (x, op1)) 3078 /* (A & x) | x ~ x. */ 3079 return op1; 3080 return gen_rtx_AND (0, op0, op1); 3081 } 3082 if (! add) 3083 return NULL; 3084 return gen_rtx_IOR (0, old, x); 3085 3086 case NOT: 3087 op0 = and_reg_cond (XEXP (old, 0), not_reg_cond (x), 0); 3088 if (op0 != NULL) 3089 return not_reg_cond (op0); 3090 if (! add) 3091 return NULL; 3092 return gen_rtx_IOR (0, old, x); 3093 3094 default: 3095 abort (); 3096 } 3097} 3098 3099static rtx 3100not_reg_cond (rtx x) 3101{ 3102 enum rtx_code x_code; 3103 3104 if (x == const0_rtx) 3105 return const1_rtx; 3106 else if (x == const1_rtx) 3107 return const0_rtx; 3108 x_code = GET_CODE (x); 3109 if (x_code == NOT) 3110 return XEXP (x, 0); 3111 if (GET_RTX_CLASS (x_code) == '<' 3112 && GET_CODE (XEXP (x, 0)) == REG) 3113 { 3114 if (XEXP (x, 1) != const0_rtx) 3115 abort (); 3116 3117 return gen_rtx_fmt_ee (reverse_condition (x_code), 3118 VOIDmode, XEXP (x, 0), const0_rtx); 3119 } 3120 return gen_rtx_NOT (0, x); 3121} 3122 3123static rtx 3124and_reg_cond (rtx old, rtx x, int add) 3125{ 3126 rtx op0, op1; 3127 3128 if (GET_RTX_CLASS (GET_CODE (old)) == '<') 3129 { 3130 if (GET_RTX_CLASS (GET_CODE (x)) == '<' 3131 && GET_CODE (x) == reverse_condition (GET_CODE (old)) 3132 && REGNO (XEXP (x, 0)) == REGNO (XEXP (old, 0))) 3133 return const0_rtx; 3134 if (GET_CODE (x) == GET_CODE (old) 3135 && REGNO (XEXP (x, 0)) == REGNO (XEXP (old, 0))) 3136 return old; 3137 if (! add) 3138 return NULL; 3139 return gen_rtx_AND (0, old, x); 3140 } 3141 3142 switch (GET_CODE (old)) 3143 { 3144 case IOR: 3145 op0 = and_reg_cond (XEXP (old, 0), x, 0); 3146 op1 = and_reg_cond (XEXP (old, 1), x, 0); 3147 if (op0 != NULL || op1 != NULL) 3148 { 3149 if (op0 == const0_rtx) 3150 return op1 ? op1 : gen_rtx_AND (0, XEXP (old, 1), x); 3151 if (op1 == const0_rtx) 3152 return op0 ? op0 : gen_rtx_AND (0, XEXP (old, 0), x); 3153 if (op0 == const1_rtx || op1 == const1_rtx) 3154 return const1_rtx; 3155 if (op0 == NULL) 3156 op0 = gen_rtx_AND (0, XEXP (old, 0), x); 3157 else if (rtx_equal_p (x, op0)) 3158 /* (x | A) & x ~ x. */ 3159 return op0; 3160 if (op1 == NULL) 3161 op1 = gen_rtx_AND (0, XEXP (old, 1), x); 3162 else if (rtx_equal_p (x, op1)) 3163 /* (A | x) & x ~ x. */ 3164 return op1; 3165 return gen_rtx_IOR (0, op0, op1); 3166 } 3167 if (! add) 3168 return NULL; 3169 return gen_rtx_AND (0, old, x); 3170 3171 case AND: 3172 op0 = and_reg_cond (XEXP (old, 0), x, 0); 3173 op1 = and_reg_cond (XEXP (old, 1), x, 0); 3174 if (op0 != NULL || op1 != NULL) 3175 { 3176 if (op0 == const1_rtx) 3177 return op1 ? op1 : gen_rtx_AND (0, XEXP (old, 1), x); 3178 if (op1 == const1_rtx) 3179 return op0 ? op0 : gen_rtx_AND (0, XEXP (old, 0), x); 3180 if (op0 == const0_rtx || op1 == const0_rtx) 3181 return const0_rtx; 3182 if (op0 == NULL) 3183 op0 = gen_rtx_AND (0, XEXP (old, 0), x); 3184 else if (rtx_equal_p (x, op0)) 3185 /* (x & A) & x ~ (x & A). */ 3186 return old; 3187 if (op1 == NULL) 3188 op1 = gen_rtx_AND (0, XEXP (old, 1), x); 3189 else if (rtx_equal_p (x, op1)) 3190 /* (A & x) & x ~ (A & x). */ 3191 return old; 3192 return gen_rtx_AND (0, op0, op1); 3193 } 3194 if (! add) 3195 return NULL; 3196 return gen_rtx_AND (0, old, x); 3197 3198 case NOT: 3199 op0 = ior_reg_cond (XEXP (old, 0), not_reg_cond (x), 0); 3200 if (op0 != NULL) 3201 return not_reg_cond (op0); 3202 if (! add) 3203 return NULL; 3204 return gen_rtx_AND (0, old, x); 3205 3206 default: 3207 abort (); 3208 } 3209} 3210 3211/* Given a condition X, remove references to reg REGNO and return the 3212 new condition. The removal will be done so that all conditions 3213 involving REGNO are considered to evaluate to false. This function 3214 is used when the value of REGNO changes. */ 3215 3216static rtx 3217elim_reg_cond (rtx x, unsigned int regno) 3218{ 3219 rtx op0, op1; 3220 3221 if (GET_RTX_CLASS (GET_CODE (x)) == '<') 3222 { 3223 if (REGNO (XEXP (x, 0)) == regno) 3224 return const0_rtx; 3225 return x; 3226 } 3227 3228 switch (GET_CODE (x)) 3229 { 3230 case AND: 3231 op0 = elim_reg_cond (XEXP (x, 0), regno); 3232 op1 = elim_reg_cond (XEXP (x, 1), regno); 3233 if (op0 == const0_rtx || op1 == const0_rtx) 3234 return const0_rtx; 3235 if (op0 == const1_rtx) 3236 return op1; 3237 if (op1 == const1_rtx) 3238 return op0; 3239 if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1)) 3240 return x; 3241 return gen_rtx_AND (0, op0, op1); 3242 3243 case IOR: 3244 op0 = elim_reg_cond (XEXP (x, 0), regno); 3245 op1 = elim_reg_cond (XEXP (x, 1), regno); 3246 if (op0 == const1_rtx || op1 == const1_rtx) 3247 return const1_rtx; 3248 if (op0 == const0_rtx) 3249 return op1; 3250 if (op1 == const0_rtx) 3251 return op0; 3252 if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1)) 3253 return x; 3254 return gen_rtx_IOR (0, op0, op1); 3255 3256 case NOT: 3257 op0 = elim_reg_cond (XEXP (x, 0), regno); 3258 if (op0 == const0_rtx) 3259 return const1_rtx; 3260 if (op0 == const1_rtx) 3261 return const0_rtx; 3262 if (op0 != XEXP (x, 0)) 3263 return not_reg_cond (op0); 3264 return x; 3265 3266 default: 3267 abort (); 3268 } 3269} 3270#endif /* HAVE_conditional_execution */ 3271 3272#ifdef AUTO_INC_DEC 3273 3274/* Try to substitute the auto-inc expression INC as the address inside 3275 MEM which occurs in INSN. Currently, the address of MEM is an expression 3276 involving INCR_REG, and INCR is the next use of INCR_REG; it is an insn 3277 that has a single set whose source is a PLUS of INCR_REG and something 3278 else. */ 3279 3280static void 3281attempt_auto_inc (struct propagate_block_info *pbi, rtx inc, rtx insn, 3282 rtx mem, rtx incr, rtx incr_reg) 3283{ 3284 int regno = REGNO (incr_reg); 3285 rtx set = single_set (incr); 3286 rtx q = SET_DEST (set); 3287 rtx y = SET_SRC (set); 3288 int opnum = XEXP (y, 0) == incr_reg ? 0 : 1; 3289 3290 /* Make sure this reg appears only once in this insn. */ 3291 if (count_occurrences (PATTERN (insn), incr_reg, 1) != 1) 3292 return; 3293 3294 if (dead_or_set_p (incr, incr_reg) 3295 /* Mustn't autoinc an eliminable register. */ 3296 && (regno >= FIRST_PSEUDO_REGISTER 3297 || ! TEST_HARD_REG_BIT (elim_reg_set, regno))) 3298 { 3299 /* This is the simple case. Try to make the auto-inc. If 3300 we can't, we are done. Otherwise, we will do any 3301 needed updates below. */ 3302 if (! validate_change (insn, &XEXP (mem, 0), inc, 0)) 3303 return; 3304 } 3305 else if (GET_CODE (q) == REG 3306 /* PREV_INSN used here to check the semi-open interval 3307 [insn,incr). */ 3308 && ! reg_used_between_p (q, PREV_INSN (insn), incr) 3309 /* We must also check for sets of q as q may be 3310 a call clobbered hard register and there may 3311 be a call between PREV_INSN (insn) and incr. */ 3312 && ! reg_set_between_p (q, PREV_INSN (insn), incr)) 3313 { 3314 /* We have *p followed sometime later by q = p+size. 3315 Both p and q must be live afterward, 3316 and q is not used between INSN and its assignment. 3317 Change it to q = p, ...*q..., q = q+size. 3318 Then fall into the usual case. */ 3319 rtx insns, temp; 3320 3321 start_sequence (); 3322 emit_move_insn (q, incr_reg); 3323 insns = get_insns (); 3324 end_sequence (); 3325 3326 /* If we can't make the auto-inc, or can't make the 3327 replacement into Y, exit. There's no point in making 3328 the change below if we can't do the auto-inc and doing 3329 so is not correct in the pre-inc case. */ 3330 3331 XEXP (inc, 0) = q; 3332 validate_change (insn, &XEXP (mem, 0), inc, 1); 3333 validate_change (incr, &XEXP (y, opnum), q, 1); 3334 if (! apply_change_group ()) 3335 return; 3336 3337 /* We now know we'll be doing this change, so emit the 3338 new insn(s) and do the updates. */ 3339 emit_insn_before (insns, insn); 3340 3341 if (BB_HEAD (pbi->bb) == insn) 3342 BB_HEAD (pbi->bb) = insns; 3343 3344 /* INCR will become a NOTE and INSN won't contain a 3345 use of INCR_REG. If a use of INCR_REG was just placed in 3346 the insn before INSN, make that the next use. 3347 Otherwise, invalidate it. */ 3348 if (GET_CODE (PREV_INSN (insn)) == INSN 3349 && GET_CODE (PATTERN (PREV_INSN (insn))) == SET 3350 && SET_SRC (PATTERN (PREV_INSN (insn))) == incr_reg) 3351 pbi->reg_next_use[regno] = PREV_INSN (insn); 3352 else 3353 pbi->reg_next_use[regno] = 0; 3354 3355 incr_reg = q; 3356 regno = REGNO (q); 3357 3358 /* REGNO is now used in INCR which is below INSN, but 3359 it previously wasn't live here. If we don't mark 3360 it as live, we'll put a REG_DEAD note for it 3361 on this insn, which is incorrect. */ 3362 SET_REGNO_REG_SET (pbi->reg_live, regno); 3363 3364 /* If there are any calls between INSN and INCR, show 3365 that REGNO now crosses them. */ 3366 for (temp = insn; temp != incr; temp = NEXT_INSN (temp)) 3367 if (GET_CODE (temp) == CALL_INSN) 3368 REG_N_CALLS_CROSSED (regno)++; 3369 3370 /* Invalidate alias info for Q since we just changed its value. */ 3371 clear_reg_alias_info (q); 3372 } 3373 else 3374 return; 3375 3376 /* If we haven't returned, it means we were able to make the 3377 auto-inc, so update the status. First, record that this insn 3378 has an implicit side effect. */ 3379 3380 REG_NOTES (insn) = alloc_EXPR_LIST (REG_INC, incr_reg, REG_NOTES (insn)); 3381 3382 /* Modify the old increment-insn to simply copy 3383 the already-incremented value of our register. */ 3384 if (! validate_change (incr, &SET_SRC (set), incr_reg, 0)) 3385 abort (); 3386 3387 /* If that makes it a no-op (copying the register into itself) delete 3388 it so it won't appear to be a "use" and a "set" of this 3389 register. */ 3390 if (REGNO (SET_DEST (set)) == REGNO (incr_reg)) 3391 { 3392 /* If the original source was dead, it's dead now. */ 3393 rtx note; 3394 3395 while ((note = find_reg_note (incr, REG_DEAD, NULL_RTX)) != NULL_RTX) 3396 { 3397 remove_note (incr, note); 3398 if (XEXP (note, 0) != incr_reg) 3399 CLEAR_REGNO_REG_SET (pbi->reg_live, REGNO (XEXP (note, 0))); 3400 } 3401 3402 PUT_CODE (incr, NOTE); 3403 NOTE_LINE_NUMBER (incr) = NOTE_INSN_DELETED; 3404 NOTE_SOURCE_FILE (incr) = 0; 3405 } 3406 3407 if (regno >= FIRST_PSEUDO_REGISTER) 3408 { 3409 /* Count an extra reference to the reg. When a reg is 3410 incremented, spilling it is worse, so we want to make 3411 that less likely. */ 3412 REG_FREQ (regno) += REG_FREQ_FROM_BB (pbi->bb); 3413 3414 /* Count the increment as a setting of the register, 3415 even though it isn't a SET in rtl. */ 3416 REG_N_SETS (regno)++; 3417 } 3418} 3419 3420/* X is a MEM found in INSN. See if we can convert it into an auto-increment 3421 reference. */ 3422 3423static void 3424find_auto_inc (struct propagate_block_info *pbi, rtx x, rtx insn) 3425{ 3426 rtx addr = XEXP (x, 0); 3427 HOST_WIDE_INT offset = 0; 3428 rtx set, y, incr, inc_val; 3429 int regno; 3430 int size = GET_MODE_SIZE (GET_MODE (x)); 3431 3432 if (GET_CODE (insn) == JUMP_INSN) 3433 return; 3434 3435 /* Here we detect use of an index register which might be good for 3436 postincrement, postdecrement, preincrement, or predecrement. */ 3437 3438 if (GET_CODE (addr) == PLUS && GET_CODE (XEXP (addr, 1)) == CONST_INT) 3439 offset = INTVAL (XEXP (addr, 1)), addr = XEXP (addr, 0); 3440 3441 if (GET_CODE (addr) != REG) 3442 return; 3443 3444 regno = REGNO (addr); 3445 3446 /* Is the next use an increment that might make auto-increment? */ 3447 incr = pbi->reg_next_use[regno]; 3448 if (incr == 0 || BLOCK_NUM (incr) != BLOCK_NUM (insn)) 3449 return; 3450 set = single_set (incr); 3451 if (set == 0 || GET_CODE (set) != SET) 3452 return; 3453 y = SET_SRC (set); 3454 3455 if (GET_CODE (y) != PLUS) 3456 return; 3457 3458 if (REG_P (XEXP (y, 0)) && REGNO (XEXP (y, 0)) == REGNO (addr)) 3459 inc_val = XEXP (y, 1); 3460 else if (REG_P (XEXP (y, 1)) && REGNO (XEXP (y, 1)) == REGNO (addr)) 3461 inc_val = XEXP (y, 0); 3462 else 3463 return; 3464 3465 if (GET_CODE (inc_val) == CONST_INT) 3466 { 3467 if (HAVE_POST_INCREMENT 3468 && (INTVAL (inc_val) == size && offset == 0)) 3469 attempt_auto_inc (pbi, gen_rtx_POST_INC (Pmode, addr), insn, x, 3470 incr, addr); 3471 else if (HAVE_POST_DECREMENT 3472 && (INTVAL (inc_val) == -size && offset == 0)) 3473 attempt_auto_inc (pbi, gen_rtx_POST_DEC (Pmode, addr), insn, x, 3474 incr, addr); 3475 else if (HAVE_PRE_INCREMENT 3476 && (INTVAL (inc_val) == size && offset == size)) 3477 attempt_auto_inc (pbi, gen_rtx_PRE_INC (Pmode, addr), insn, x, 3478 incr, addr); 3479 else if (HAVE_PRE_DECREMENT 3480 && (INTVAL (inc_val) == -size && offset == -size)) 3481 attempt_auto_inc (pbi, gen_rtx_PRE_DEC (Pmode, addr), insn, x, 3482 incr, addr); 3483 else if (HAVE_POST_MODIFY_DISP && offset == 0) 3484 attempt_auto_inc (pbi, gen_rtx_POST_MODIFY (Pmode, addr, 3485 gen_rtx_PLUS (Pmode, 3486 addr, 3487 inc_val)), 3488 insn, x, incr, addr); 3489 else if (HAVE_PRE_MODIFY_DISP && offset == INTVAL (inc_val)) 3490 attempt_auto_inc (pbi, gen_rtx_PRE_MODIFY (Pmode, addr, 3491 gen_rtx_PLUS (Pmode, 3492 addr, 3493 inc_val)), 3494 insn, x, incr, addr); 3495 } 3496 else if (GET_CODE (inc_val) == REG 3497 && ! reg_set_between_p (inc_val, PREV_INSN (insn), 3498 NEXT_INSN (incr))) 3499 3500 { 3501 if (HAVE_POST_MODIFY_REG && offset == 0) 3502 attempt_auto_inc (pbi, gen_rtx_POST_MODIFY (Pmode, addr, 3503 gen_rtx_PLUS (Pmode, 3504 addr, 3505 inc_val)), 3506 insn, x, incr, addr); 3507 } 3508} 3509 3510#endif /* AUTO_INC_DEC */ 3511 3512static void 3513mark_used_reg (struct propagate_block_info *pbi, rtx reg, 3514 rtx cond ATTRIBUTE_UNUSED, rtx insn) 3515{ 3516 unsigned int regno_first, regno_last, i; 3517 int some_was_live, some_was_dead, some_not_set; 3518 3519 regno_last = regno_first = REGNO (reg); 3520 if (regno_first < FIRST_PSEUDO_REGISTER) 3521 regno_last += HARD_REGNO_NREGS (regno_first, GET_MODE (reg)) - 1; 3522 3523 /* Find out if any of this register is live after this instruction. */ 3524 some_was_live = some_was_dead = 0; 3525 for (i = regno_first; i <= regno_last; ++i) 3526 { 3527 int needed_regno = REGNO_REG_SET_P (pbi->reg_live, i); 3528 some_was_live |= needed_regno; 3529 some_was_dead |= ! needed_regno; 3530 } 3531 3532 /* Find out if any of the register was set this insn. */ 3533 some_not_set = 0; 3534 for (i = regno_first; i <= regno_last; ++i) 3535 some_not_set |= ! REGNO_REG_SET_P (pbi->new_set, i); 3536 3537 if (pbi->flags & (PROP_LOG_LINKS | PROP_AUTOINC)) 3538 { 3539 /* Record where each reg is used, so when the reg is set we know 3540 the next insn that uses it. */ 3541 pbi->reg_next_use[regno_first] = insn; 3542 } 3543 3544 if (pbi->flags & PROP_REG_INFO) 3545 { 3546 if (regno_first < FIRST_PSEUDO_REGISTER) 3547 { 3548 /* If this is a register we are going to try to eliminate, 3549 don't mark it live here. If we are successful in 3550 eliminating it, it need not be live unless it is used for 3551 pseudos, in which case it will have been set live when it 3552 was allocated to the pseudos. If the register will not 3553 be eliminated, reload will set it live at that point. 3554 3555 Otherwise, record that this function uses this register. */ 3556 /* ??? The PPC backend tries to "eliminate" on the pic 3557 register to itself. This should be fixed. In the mean 3558 time, hack around it. */ 3559 3560 if (! (TEST_HARD_REG_BIT (elim_reg_set, regno_first) 3561 && (regno_first == FRAME_POINTER_REGNUM 3562 || regno_first == ARG_POINTER_REGNUM))) 3563 for (i = regno_first; i <= regno_last; ++i) 3564 regs_ever_live[i] = 1; 3565 } 3566 else 3567 { 3568 /* Keep track of which basic block each reg appears in. */ 3569 3570 int blocknum = pbi->bb->index; 3571 if (REG_BASIC_BLOCK (regno_first) == REG_BLOCK_UNKNOWN) 3572 REG_BASIC_BLOCK (regno_first) = blocknum; 3573 else if (REG_BASIC_BLOCK (regno_first) != blocknum) 3574 REG_BASIC_BLOCK (regno_first) = REG_BLOCK_GLOBAL; 3575 3576 /* Count (weighted) number of uses of each reg. */ 3577 REG_FREQ (regno_first) += REG_FREQ_FROM_BB (pbi->bb); 3578 REG_N_REFS (regno_first)++; 3579 } 3580 } 3581 3582 /* Record and count the insns in which a reg dies. If it is used in 3583 this insn and was dead below the insn then it dies in this insn. 3584 If it was set in this insn, we do not make a REG_DEAD note; 3585 likewise if we already made such a note. */ 3586 if ((pbi->flags & (PROP_DEATH_NOTES | PROP_REG_INFO)) 3587 && some_was_dead 3588 && some_not_set) 3589 { 3590 /* Check for the case where the register dying partially 3591 overlaps the register set by this insn. */ 3592 if (regno_first != regno_last) 3593 for (i = regno_first; i <= regno_last; ++i) 3594 some_was_live |= REGNO_REG_SET_P (pbi->new_set, i); 3595 3596 /* If none of the words in X is needed, make a REG_DEAD note. 3597 Otherwise, we must make partial REG_DEAD notes. */ 3598 if (! some_was_live) 3599 { 3600 if ((pbi->flags & PROP_DEATH_NOTES) 3601 && ! find_regno_note (insn, REG_DEAD, regno_first)) 3602 REG_NOTES (insn) 3603 = alloc_EXPR_LIST (REG_DEAD, reg, REG_NOTES (insn)); 3604 3605 if (pbi->flags & PROP_REG_INFO) 3606 REG_N_DEATHS (regno_first)++; 3607 } 3608 else 3609 { 3610 /* Don't make a REG_DEAD note for a part of a register 3611 that is set in the insn. */ 3612 for (i = regno_first; i <= regno_last; ++i) 3613 if (! REGNO_REG_SET_P (pbi->reg_live, i) 3614 && ! dead_or_set_regno_p (insn, i)) 3615 REG_NOTES (insn) 3616 = alloc_EXPR_LIST (REG_DEAD, 3617 regno_reg_rtx[i], 3618 REG_NOTES (insn)); 3619 } 3620 } 3621 3622 /* Mark the register as being live. */ 3623 for (i = regno_first; i <= regno_last; ++i) 3624 { 3625#ifdef HAVE_conditional_execution 3626 int this_was_live = REGNO_REG_SET_P (pbi->reg_live, i); 3627#endif 3628 3629 SET_REGNO_REG_SET (pbi->reg_live, i); 3630 3631#ifdef HAVE_conditional_execution 3632 /* If this is a conditional use, record that fact. If it is later 3633 conditionally set, we'll know to kill the register. */ 3634 if (cond != NULL_RTX) 3635 { 3636 splay_tree_node node; 3637 struct reg_cond_life_info *rcli; 3638 rtx ncond; 3639 3640 if (this_was_live) 3641 { 3642 node = splay_tree_lookup (pbi->reg_cond_dead, i); 3643 if (node == NULL) 3644 { 3645 /* The register was unconditionally live previously. 3646 No need to do anything. */ 3647 } 3648 else 3649 { 3650 /* The register was conditionally live previously. 3651 Subtract the new life cond from the old death cond. */ 3652 rcli = (struct reg_cond_life_info *) node->value; 3653 ncond = rcli->condition; 3654 ncond = and_reg_cond (ncond, not_reg_cond (cond), 1); 3655 3656 /* If the register is now unconditionally live, 3657 remove the entry in the splay_tree. */ 3658 if (ncond == const0_rtx) 3659 splay_tree_remove (pbi->reg_cond_dead, i); 3660 else 3661 { 3662 rcli->condition = ncond; 3663 SET_REGNO_REG_SET (pbi->reg_cond_reg, 3664 REGNO (XEXP (cond, 0))); 3665 } 3666 } 3667 } 3668 else 3669 { 3670 /* The register was not previously live at all. Record 3671 the condition under which it is still dead. */ 3672 rcli = xmalloc (sizeof (*rcli)); 3673 rcli->condition = not_reg_cond (cond); 3674 rcli->stores = const0_rtx; 3675 rcli->orig_condition = const0_rtx; 3676 splay_tree_insert (pbi->reg_cond_dead, i, 3677 (splay_tree_value) rcli); 3678 3679 SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (XEXP (cond, 0))); 3680 } 3681 } 3682 else if (this_was_live) 3683 { 3684 /* The register may have been conditionally live previously, but 3685 is now unconditionally live. Remove it from the conditionally 3686 dead list, so that a conditional set won't cause us to think 3687 it dead. */ 3688 splay_tree_remove (pbi->reg_cond_dead, i); 3689 } 3690#endif 3691 } 3692} 3693 3694/* Scan expression X and store a 1-bit in NEW_LIVE for each reg it uses. 3695 This is done assuming the registers needed from X are those that 3696 have 1-bits in PBI->REG_LIVE. 3697 3698 INSN is the containing instruction. If INSN is dead, this function 3699 is not called. */ 3700 3701static void 3702mark_used_regs (struct propagate_block_info *pbi, rtx x, rtx cond, rtx insn) 3703{ 3704 RTX_CODE code; 3705 int regno; 3706 int flags = pbi->flags; 3707 3708 retry: 3709 if (!x) 3710 return; 3711 code = GET_CODE (x); 3712 switch (code) 3713 { 3714 case LABEL_REF: 3715 case SYMBOL_REF: 3716 case CONST_INT: 3717 case CONST: 3718 case CONST_DOUBLE: 3719 case CONST_VECTOR: 3720 case PC: 3721 case ADDR_VEC: 3722 case ADDR_DIFF_VEC: 3723 return; 3724 3725#ifdef HAVE_cc0 3726 case CC0: 3727 pbi->cc0_live = 1; 3728 return; 3729#endif 3730 3731 case CLOBBER: 3732 /* If we are clobbering a MEM, mark any registers inside the address 3733 as being used. */ 3734 if (GET_CODE (XEXP (x, 0)) == MEM) 3735 mark_used_regs (pbi, XEXP (XEXP (x, 0), 0), cond, insn); 3736 return; 3737 3738 case MEM: 3739 /* Don't bother watching stores to mems if this is not the 3740 final pass. We'll not be deleting dead stores this round. */ 3741 if (optimize && (flags & PROP_SCAN_DEAD_STORES)) 3742 { 3743 /* Invalidate the data for the last MEM stored, but only if MEM is 3744 something that can be stored into. */ 3745 if (GET_CODE (XEXP (x, 0)) == SYMBOL_REF 3746 && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0))) 3747 /* Needn't clear the memory set list. */ 3748 ; 3749 else 3750 { 3751 rtx temp = pbi->mem_set_list; 3752 rtx prev = NULL_RTX; 3753 rtx next; 3754 3755 while (temp) 3756 { 3757 next = XEXP (temp, 1); 3758 if (unchanging_anti_dependence (XEXP (temp, 0), x)) 3759 { 3760 /* Splice temp out of the list. */ 3761 if (prev) 3762 XEXP (prev, 1) = next; 3763 else 3764 pbi->mem_set_list = next; 3765 free_EXPR_LIST_node (temp); 3766 pbi->mem_set_list_len--; 3767 } 3768 else 3769 prev = temp; 3770 temp = next; 3771 } 3772 } 3773 3774 /* If the memory reference had embedded side effects (autoincrement 3775 address modes. Then we may need to kill some entries on the 3776 memory set list. */ 3777 if (insn) 3778 for_each_rtx (&PATTERN (insn), invalidate_mems_from_autoinc, pbi); 3779 } 3780 3781#ifdef AUTO_INC_DEC 3782 if (flags & PROP_AUTOINC) 3783 find_auto_inc (pbi, x, insn); 3784#endif 3785 break; 3786 3787 case SUBREG: 3788#ifdef CANNOT_CHANGE_MODE_CLASS 3789 if (flags & PROP_REG_INFO) 3790 record_subregs_of_mode (x); 3791#endif 3792 3793 /* While we're here, optimize this case. */ 3794 x = SUBREG_REG (x); 3795 if (GET_CODE (x) != REG) 3796 goto retry; 3797 /* Fall through. */ 3798 3799 case REG: 3800 /* See a register other than being set => mark it as needed. */ 3801 mark_used_reg (pbi, x, cond, insn); 3802 return; 3803 3804 case SET: 3805 { 3806 rtx testreg = SET_DEST (x); 3807 int mark_dest = 0; 3808 3809 /* If storing into MEM, don't show it as being used. But do 3810 show the address as being used. */ 3811 if (GET_CODE (testreg) == MEM) 3812 { 3813#ifdef AUTO_INC_DEC 3814 if (flags & PROP_AUTOINC) 3815 find_auto_inc (pbi, testreg, insn); 3816#endif 3817 mark_used_regs (pbi, XEXP (testreg, 0), cond, insn); 3818 mark_used_regs (pbi, SET_SRC (x), cond, insn); 3819 return; 3820 } 3821 3822 /* Storing in STRICT_LOW_PART is like storing in a reg 3823 in that this SET might be dead, so ignore it in TESTREG. 3824 but in some other ways it is like using the reg. 3825 3826 Storing in a SUBREG or a bit field is like storing the entire 3827 register in that if the register's value is not used 3828 then this SET is not needed. */ 3829 while (GET_CODE (testreg) == STRICT_LOW_PART 3830 || GET_CODE (testreg) == ZERO_EXTRACT 3831 || GET_CODE (testreg) == SIGN_EXTRACT 3832 || GET_CODE (testreg) == SUBREG) 3833 { 3834#ifdef CANNOT_CHANGE_MODE_CLASS 3835 if ((flags & PROP_REG_INFO) && GET_CODE (testreg) == SUBREG) 3836 record_subregs_of_mode (testreg); 3837#endif 3838 3839 /* Modifying a single register in an alternate mode 3840 does not use any of the old value. But these other 3841 ways of storing in a register do use the old value. */ 3842 if (GET_CODE (testreg) == SUBREG 3843 && !((REG_BYTES (SUBREG_REG (testreg)) 3844 + UNITS_PER_WORD - 1) / UNITS_PER_WORD 3845 > (REG_BYTES (testreg) 3846 + UNITS_PER_WORD - 1) / UNITS_PER_WORD)) 3847 ; 3848 else 3849 mark_dest = 1; 3850 3851 testreg = XEXP (testreg, 0); 3852 } 3853 3854 /* If this is a store into a register or group of registers, 3855 recursively scan the value being stored. */ 3856 3857 if ((GET_CODE (testreg) == PARALLEL 3858 && GET_MODE (testreg) == BLKmode) 3859 || (GET_CODE (testreg) == REG 3860 && (regno = REGNO (testreg), 3861 ! (regno == FRAME_POINTER_REGNUM 3862 && (! reload_completed || frame_pointer_needed))) 3863#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM 3864 && ! (regno == HARD_FRAME_POINTER_REGNUM 3865 && (! reload_completed || frame_pointer_needed)) 3866#endif 3867#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM 3868 && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno]) 3869#endif 3870 )) 3871 { 3872 if (mark_dest) 3873 mark_used_regs (pbi, SET_DEST (x), cond, insn); 3874 mark_used_regs (pbi, SET_SRC (x), cond, insn); 3875 return; 3876 } 3877 } 3878 break; 3879 3880 case ASM_OPERANDS: 3881 case UNSPEC_VOLATILE: 3882 case TRAP_IF: 3883 case ASM_INPUT: 3884 { 3885 /* Traditional and volatile asm instructions must be considered to use 3886 and clobber all hard registers, all pseudo-registers and all of 3887 memory. So must TRAP_IF and UNSPEC_VOLATILE operations. 3888 3889 Consider for instance a volatile asm that changes the fpu rounding 3890 mode. An insn should not be moved across this even if it only uses 3891 pseudo-regs because it might give an incorrectly rounded result. 3892 3893 ?!? Unfortunately, marking all hard registers as live causes massive 3894 problems for the register allocator and marking all pseudos as live 3895 creates mountains of uninitialized variable warnings. 3896 3897 So for now, just clear the memory set list and mark any regs 3898 we can find in ASM_OPERANDS as used. */ 3899 if (code != ASM_OPERANDS || MEM_VOLATILE_P (x)) 3900 { 3901 free_EXPR_LIST_list (&pbi->mem_set_list); 3902 pbi->mem_set_list_len = 0; 3903 } 3904 3905 /* For all ASM_OPERANDS, we must traverse the vector of input operands. 3906 We can not just fall through here since then we would be confused 3907 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate 3908 traditional asms unlike their normal usage. */ 3909 if (code == ASM_OPERANDS) 3910 { 3911 int j; 3912 3913 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++) 3914 mark_used_regs (pbi, ASM_OPERANDS_INPUT (x, j), cond, insn); 3915 } 3916 break; 3917 } 3918 3919 case COND_EXEC: 3920 if (cond != NULL_RTX) 3921 abort (); 3922 3923 mark_used_regs (pbi, COND_EXEC_TEST (x), NULL_RTX, insn); 3924 3925 cond = COND_EXEC_TEST (x); 3926 x = COND_EXEC_CODE (x); 3927 goto retry; 3928 3929 default: 3930 break; 3931 } 3932 3933 /* Recursively scan the operands of this expression. */ 3934 3935 { 3936 const char * const fmt = GET_RTX_FORMAT (code); 3937 int i; 3938 3939 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 3940 { 3941 if (fmt[i] == 'e') 3942 { 3943 /* Tail recursive case: save a function call level. */ 3944 if (i == 0) 3945 { 3946 x = XEXP (x, 0); 3947 goto retry; 3948 } 3949 mark_used_regs (pbi, XEXP (x, i), cond, insn); 3950 } 3951 else if (fmt[i] == 'E') 3952 { 3953 int j; 3954 for (j = 0; j < XVECLEN (x, i); j++) 3955 mark_used_regs (pbi, XVECEXP (x, i, j), cond, insn); 3956 } 3957 } 3958 } 3959} 3960 3961#ifdef AUTO_INC_DEC 3962 3963static int 3964try_pre_increment_1 (struct propagate_block_info *pbi, rtx insn) 3965{ 3966 /* Find the next use of this reg. If in same basic block, 3967 make it do pre-increment or pre-decrement if appropriate. */ 3968 rtx x = single_set (insn); 3969 HOST_WIDE_INT amount = ((GET_CODE (SET_SRC (x)) == PLUS ? 1 : -1) 3970 * INTVAL (XEXP (SET_SRC (x), 1))); 3971 int regno = REGNO (SET_DEST (x)); 3972 rtx y = pbi->reg_next_use[regno]; 3973 if (y != 0 3974 && SET_DEST (x) != stack_pointer_rtx 3975 && BLOCK_NUM (y) == BLOCK_NUM (insn) 3976 /* Don't do this if the reg dies, or gets set in y; a standard addressing 3977 mode would be better. */ 3978 && ! dead_or_set_p (y, SET_DEST (x)) 3979 && try_pre_increment (y, SET_DEST (x), amount)) 3980 { 3981 /* We have found a suitable auto-increment and already changed 3982 insn Y to do it. So flush this increment instruction. */ 3983 propagate_block_delete_insn (insn); 3984 3985 /* Count a reference to this reg for the increment insn we are 3986 deleting. When a reg is incremented, spilling it is worse, 3987 so we want to make that less likely. */ 3988 if (regno >= FIRST_PSEUDO_REGISTER) 3989 { 3990 REG_FREQ (regno) += REG_FREQ_FROM_BB (pbi->bb); 3991 REG_N_SETS (regno)++; 3992 } 3993 3994 /* Flush any remembered memories depending on the value of 3995 the incremented register. */ 3996 invalidate_mems_from_set (pbi, SET_DEST (x)); 3997 3998 return 1; 3999 } 4000 return 0; 4001} 4002 4003/* Try to change INSN so that it does pre-increment or pre-decrement 4004 addressing on register REG in order to add AMOUNT to REG. 4005 AMOUNT is negative for pre-decrement. 4006 Returns 1 if the change could be made. 4007 This checks all about the validity of the result of modifying INSN. */ 4008 4009static int 4010try_pre_increment (rtx insn, rtx reg, HOST_WIDE_INT amount) 4011{ 4012 rtx use; 4013 4014 /* Nonzero if we can try to make a pre-increment or pre-decrement. 4015 For example, addl $4,r1; movl (r1),... can become movl +(r1),... */ 4016 int pre_ok = 0; 4017 /* Nonzero if we can try to make a post-increment or post-decrement. 4018 For example, addl $4,r1; movl -4(r1),... can become movl (r1)+,... 4019 It is possible for both PRE_OK and POST_OK to be nonzero if the machine 4020 supports both pre-inc and post-inc, or both pre-dec and post-dec. */ 4021 int post_ok = 0; 4022 4023 /* Nonzero if the opportunity actually requires post-inc or post-dec. */ 4024 int do_post = 0; 4025 4026 /* From the sign of increment, see which possibilities are conceivable 4027 on this target machine. */ 4028 if (HAVE_PRE_INCREMENT && amount > 0) 4029 pre_ok = 1; 4030 if (HAVE_POST_INCREMENT && amount > 0) 4031 post_ok = 1; 4032 4033 if (HAVE_PRE_DECREMENT && amount < 0) 4034 pre_ok = 1; 4035 if (HAVE_POST_DECREMENT && amount < 0) 4036 post_ok = 1; 4037 4038 if (! (pre_ok || post_ok)) 4039 return 0; 4040 4041 /* It is not safe to add a side effect to a jump insn 4042 because if the incremented register is spilled and must be reloaded 4043 there would be no way to store the incremented value back in memory. */ 4044 4045 if (GET_CODE (insn) == JUMP_INSN) 4046 return 0; 4047 4048 use = 0; 4049 if (pre_ok) 4050 use = find_use_as_address (PATTERN (insn), reg, 0); 4051 if (post_ok && (use == 0 || use == (rtx) (size_t) 1)) 4052 { 4053 use = find_use_as_address (PATTERN (insn), reg, -amount); 4054 do_post = 1; 4055 } 4056 4057 if (use == 0 || use == (rtx) (size_t) 1) 4058 return 0; 4059 4060 if (GET_MODE_SIZE (GET_MODE (use)) != (amount > 0 ? amount : - amount)) 4061 return 0; 4062 4063 /* See if this combination of instruction and addressing mode exists. */ 4064 if (! validate_change (insn, &XEXP (use, 0), 4065 gen_rtx_fmt_e (amount > 0 4066 ? (do_post ? POST_INC : PRE_INC) 4067 : (do_post ? POST_DEC : PRE_DEC), 4068 Pmode, reg), 0)) 4069 return 0; 4070 4071 /* Record that this insn now has an implicit side effect on X. */ 4072 REG_NOTES (insn) = alloc_EXPR_LIST (REG_INC, reg, REG_NOTES (insn)); 4073 return 1; 4074} 4075 4076#endif /* AUTO_INC_DEC */ 4077 4078/* Find the place in the rtx X where REG is used as a memory address. 4079 Return the MEM rtx that so uses it. 4080 If PLUSCONST is nonzero, search instead for a memory address equivalent to 4081 (plus REG (const_int PLUSCONST)). 4082 4083 If such an address does not appear, return 0. 4084 If REG appears more than once, or is used other than in such an address, 4085 return (rtx) 1. */ 4086 4087rtx 4088find_use_as_address (rtx x, rtx reg, HOST_WIDE_INT plusconst) 4089{ 4090 enum rtx_code code = GET_CODE (x); 4091 const char * const fmt = GET_RTX_FORMAT (code); 4092 int i; 4093 rtx value = 0; 4094 rtx tem; 4095 4096 if (code == MEM && XEXP (x, 0) == reg && plusconst == 0) 4097 return x; 4098 4099 if (code == MEM && GET_CODE (XEXP (x, 0)) == PLUS 4100 && XEXP (XEXP (x, 0), 0) == reg 4101 && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT 4102 && INTVAL (XEXP (XEXP (x, 0), 1)) == plusconst) 4103 return x; 4104 4105 if (code == SIGN_EXTRACT || code == ZERO_EXTRACT) 4106 { 4107 /* If REG occurs inside a MEM used in a bit-field reference, 4108 that is unacceptable. */ 4109 if (find_use_as_address (XEXP (x, 0), reg, 0) != 0) 4110 return (rtx) (size_t) 1; 4111 } 4112 4113 if (x == reg) 4114 return (rtx) (size_t) 1; 4115 4116 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 4117 { 4118 if (fmt[i] == 'e') 4119 { 4120 tem = find_use_as_address (XEXP (x, i), reg, plusconst); 4121 if (value == 0) 4122 value = tem; 4123 else if (tem != 0) 4124 return (rtx) (size_t) 1; 4125 } 4126 else if (fmt[i] == 'E') 4127 { 4128 int j; 4129 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 4130 { 4131 tem = find_use_as_address (XVECEXP (x, i, j), reg, plusconst); 4132 if (value == 0) 4133 value = tem; 4134 else if (tem != 0) 4135 return (rtx) (size_t) 1; 4136 } 4137 } 4138 } 4139 4140 return value; 4141} 4142 4143/* Write information about registers and basic blocks into FILE. 4144 This is part of making a debugging dump. */ 4145 4146void 4147dump_regset (regset r, FILE *outf) 4148{ 4149 int i; 4150 if (r == NULL) 4151 { 4152 fputs (" (nil)", outf); 4153 return; 4154 } 4155 4156 EXECUTE_IF_SET_IN_REG_SET (r, 0, i, 4157 { 4158 fprintf (outf, " %d", i); 4159 if (i < FIRST_PSEUDO_REGISTER) 4160 fprintf (outf, " [%s]", 4161 reg_names[i]); 4162 }); 4163} 4164 4165/* Print a human-readable representation of R on the standard error 4166 stream. This function is designed to be used from within the 4167 debugger. */ 4168 4169void 4170debug_regset (regset r) 4171{ 4172 dump_regset (r, stderr); 4173 putc ('\n', stderr); 4174} 4175 4176/* Recompute register set/reference counts immediately prior to register 4177 allocation. 4178 4179 This avoids problems with set/reference counts changing to/from values 4180 which have special meanings to the register allocators. 4181 4182 Additionally, the reference counts are the primary component used by the 4183 register allocators to prioritize pseudos for allocation to hard regs. 4184 More accurate reference counts generally lead to better register allocation. 4185 4186 F is the first insn to be scanned. 4187 4188 LOOP_STEP denotes how much loop_depth should be incremented per 4189 loop nesting level in order to increase the ref count more for 4190 references in a loop. 4191 4192 It might be worthwhile to update REG_LIVE_LENGTH, REG_BASIC_BLOCK and 4193 possibly other information which is used by the register allocators. */ 4194 4195void 4196recompute_reg_usage (rtx f ATTRIBUTE_UNUSED, int loop_step ATTRIBUTE_UNUSED) 4197{ 4198 allocate_reg_life_data (); 4199 update_life_info (NULL, UPDATE_LIFE_LOCAL, PROP_REG_INFO); 4200} 4201 4202/* Optionally removes all the REG_DEAD and REG_UNUSED notes from a set of 4203 blocks. If BLOCKS is NULL, assume the universal set. Returns a count 4204 of the number of registers that died. */ 4205 4206int 4207count_or_remove_death_notes (sbitmap blocks, int kill) 4208{ 4209 int count = 0; 4210 int i; 4211 basic_block bb; 4212 4213 4214 /* This used to be a loop over all the blocks with a membership test 4215 inside the loop. That can be amazingly expensive on a large CFG 4216 when only a small number of bits are set in BLOCKs (for example, 4217 the calls from the scheduler typically have very few bits set). 4218 4219 For extra credit, someone should convert BLOCKS to a bitmap rather 4220 than an sbitmap. */ 4221 if (blocks) 4222 { 4223 EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i, 4224 { 4225 count += count_or_remove_death_notes_bb (BASIC_BLOCK (i), kill); 4226 }); 4227 } 4228 else 4229 { 4230 FOR_EACH_BB (bb) 4231 { 4232 count += count_or_remove_death_notes_bb (bb, kill); 4233 } 4234 } 4235 4236 return count; 4237} 4238 4239/* Optionally removes all the REG_DEAD and REG_UNUSED notes from basic 4240 block BB. Returns a count of the number of registers that died. */ 4241 4242static int 4243count_or_remove_death_notes_bb (basic_block bb, int kill) 4244{ 4245 int count = 0; 4246 rtx insn; 4247 4248 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn)) 4249 { 4250 if (INSN_P (insn)) 4251 { 4252 rtx *pprev = ®_NOTES (insn); 4253 rtx link = *pprev; 4254 4255 while (link) 4256 { 4257 switch (REG_NOTE_KIND (link)) 4258 { 4259 case REG_DEAD: 4260 if (GET_CODE (XEXP (link, 0)) == REG) 4261 { 4262 rtx reg = XEXP (link, 0); 4263 int n; 4264 4265 if (REGNO (reg) >= FIRST_PSEUDO_REGISTER) 4266 n = 1; 4267 else 4268 n = HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg)); 4269 count += n; 4270 } 4271 4272 /* Fall through. */ 4273 4274 case REG_UNUSED: 4275 if (kill) 4276 { 4277 rtx next = XEXP (link, 1); 4278 free_EXPR_LIST_node (link); 4279 *pprev = link = next; 4280 break; 4281 } 4282 /* Fall through. */ 4283 4284 default: 4285 pprev = &XEXP (link, 1); 4286 link = *pprev; 4287 break; 4288 } 4289 } 4290 } 4291 4292 if (insn == BB_END (bb)) 4293 break; 4294 } 4295 4296 return count; 4297} 4298 4299/* Clear LOG_LINKS fields of insns in a selected blocks or whole chain 4300 if blocks is NULL. */ 4301 4302static void 4303clear_log_links (sbitmap blocks) 4304{ 4305 rtx insn; 4306 int i; 4307 4308 if (!blocks) 4309 { 4310 for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) 4311 if (INSN_P (insn)) 4312 free_INSN_LIST_list (&LOG_LINKS (insn)); 4313 } 4314 else 4315 EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i, 4316 { 4317 basic_block bb = BASIC_BLOCK (i); 4318 4319 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); 4320 insn = NEXT_INSN (insn)) 4321 if (INSN_P (insn)) 4322 free_INSN_LIST_list (&LOG_LINKS (insn)); 4323 }); 4324} 4325 4326/* Given a register bitmap, turn on the bits in a HARD_REG_SET that 4327 correspond to the hard registers, if any, set in that map. This 4328 could be done far more efficiently by having all sorts of special-cases 4329 with moving single words, but probably isn't worth the trouble. */ 4330 4331void 4332reg_set_to_hard_reg_set (HARD_REG_SET *to, bitmap from) 4333{ 4334 int i; 4335 4336 EXECUTE_IF_SET_IN_BITMAP 4337 (from, 0, i, 4338 { 4339 if (i >= FIRST_PSEUDO_REGISTER) 4340 return; 4341 SET_HARD_REG_BIT (*to, i); 4342 }); 4343} 4344