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