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