1/* Global constant/copy propagation for RTL. 2 Copyright (C) 1997-2015 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify it under 7the terms of the GNU General Public License as published by the Free 8Software Foundation; either version 3, or (at your option) any later 9version. 10 11GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12WARRANTY; without even the implied warranty of MERCHANTABILITY or 13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14for more details. 15 16You should have received a copy of the GNU General Public License 17along with GCC; see the file COPYING3. If not see 18<http://www.gnu.org/licenses/>. */ 19 20#include "config.h" 21#include "system.h" 22#include "coretypes.h" 23#include "tm.h" 24#include "diagnostic-core.h" 25#include "toplev.h" 26#include "rtl.h" 27#include "hash-set.h" 28#include "machmode.h" 29#include "vec.h" 30#include "double-int.h" 31#include "input.h" 32#include "alias.h" 33#include "symtab.h" 34#include "wide-int.h" 35#include "inchash.h" 36#include "tree.h" 37#include "tm_p.h" 38#include "regs.h" 39#include "hard-reg-set.h" 40#include "flags.h" 41#include "insn-config.h" 42#include "recog.h" 43#include "predict.h" 44#include "hashtab.h" 45#include "function.h" 46#include "dominance.h" 47#include "cfg.h" 48#include "cfgrtl.h" 49#include "cfganal.h" 50#include "lcm.h" 51#include "cfgcleanup.h" 52#include "basic-block.h" 53#include "statistics.h" 54#include "real.h" 55#include "fixed-value.h" 56#include "expmed.h" 57#include "dojump.h" 58#include "explow.h" 59#include "calls.h" 60#include "emit-rtl.h" 61#include "varasm.h" 62#include "stmt.h" 63#include "expr.h" 64#include "except.h" 65#include "params.h" 66#include "cselib.h" 67#include "intl.h" 68#include "obstack.h" 69#include "tree-pass.h" 70#include "df.h" 71#include "dbgcnt.h" 72#include "target.h" 73#include "cfgloop.h" 74 75 76/* An obstack for our working variables. */ 77static struct obstack cprop_obstack; 78 79/* Occurrence of an expression. 80 There is one per basic block. If a pattern appears more than once the 81 last appearance is used. */ 82 83struct cprop_occr 84{ 85 /* Next occurrence of this expression. */ 86 struct cprop_occr *next; 87 /* The insn that computes the expression. */ 88 rtx_insn *insn; 89}; 90 91typedef struct cprop_occr *occr_t; 92 93/* Hash table entry for assignment expressions. */ 94 95struct cprop_expr 96{ 97 /* The expression (DEST := SRC). */ 98 rtx dest; 99 rtx src; 100 101 /* Index in the available expression bitmaps. */ 102 int bitmap_index; 103 /* Next entry with the same hash. */ 104 struct cprop_expr *next_same_hash; 105 /* List of available occurrence in basic blocks in the function. 106 An "available occurrence" is one that is the last occurrence in the 107 basic block and whose operands are not modified by following statements 108 in the basic block [including this insn]. */ 109 struct cprop_occr *avail_occr; 110}; 111 112/* Hash table for copy propagation expressions. 113 Each hash table is an array of buckets. 114 ??? It is known that if it were an array of entries, structure elements 115 `next_same_hash' and `bitmap_index' wouldn't be necessary. However, it is 116 not clear whether in the final analysis a sufficient amount of memory would 117 be saved as the size of the available expression bitmaps would be larger 118 [one could build a mapping table without holes afterwards though]. 119 Someday I'll perform the computation and figure it out. */ 120 121struct hash_table_d 122{ 123 /* The table itself. 124 This is an array of `set_hash_table_size' elements. */ 125 struct cprop_expr **table; 126 127 /* Size of the hash table, in elements. */ 128 unsigned int size; 129 130 /* Number of hash table elements. */ 131 unsigned int n_elems; 132}; 133 134/* Copy propagation hash table. */ 135static struct hash_table_d set_hash_table; 136 137/* Array of implicit set patterns indexed by basic block index. */ 138static rtx *implicit_sets; 139 140/* Array of indexes of expressions for implicit set patterns indexed by basic 141 block index. In other words, implicit_set_indexes[i] is the bitmap_index 142 of the expression whose RTX is implicit_sets[i]. */ 143static int *implicit_set_indexes; 144 145/* Bitmap containing one bit for each register in the program. 146 Used when performing GCSE to track which registers have been set since 147 the start or end of the basic block while traversing that block. */ 148static regset reg_set_bitmap; 149 150/* Various variables for statistics gathering. */ 151 152/* Memory used in a pass. 153 This isn't intended to be absolutely precise. Its intent is only 154 to keep an eye on memory usage. */ 155static int bytes_used; 156 157/* Number of local constants propagated. */ 158static int local_const_prop_count; 159/* Number of local copies propagated. */ 160static int local_copy_prop_count; 161/* Number of global constants propagated. */ 162static int global_const_prop_count; 163/* Number of global copies propagated. */ 164static int global_copy_prop_count; 165 166#define GOBNEW(T) ((T *) cprop_alloc (sizeof (T))) 167#define GOBNEWVAR(T, S) ((T *) cprop_alloc ((S))) 168 169/* Cover function to obstack_alloc. */ 170 171static void * 172cprop_alloc (unsigned long size) 173{ 174 bytes_used += size; 175 return obstack_alloc (&cprop_obstack, size); 176} 177 178/* Return nonzero if register X is unchanged from INSN to the end 179 of INSN's basic block. */ 180 181static int 182reg_available_p (const_rtx x, const rtx_insn *insn ATTRIBUTE_UNUSED) 183{ 184 return ! REGNO_REG_SET_P (reg_set_bitmap, REGNO (x)); 185} 186 187/* Hash a set of register REGNO. 188 189 Sets are hashed on the register that is set. This simplifies the PRE copy 190 propagation code. 191 192 ??? May need to make things more elaborate. Later, as necessary. */ 193 194static unsigned int 195hash_mod (int regno, int hash_table_size) 196{ 197 return (unsigned) regno % hash_table_size; 198} 199 200/* Insert assignment DEST:=SET from INSN in the hash table. 201 DEST is a register and SET is a register or a suitable constant. 202 If the assignment is already present in the table, record it as 203 the last occurrence in INSN's basic block. 204 IMPLICIT is true if it's an implicit set, false otherwise. */ 205 206static void 207insert_set_in_table (rtx dest, rtx src, rtx_insn *insn, 208 struct hash_table_d *table, bool implicit) 209{ 210 bool found = false; 211 unsigned int hash; 212 struct cprop_expr *cur_expr, *last_expr = NULL; 213 struct cprop_occr *cur_occr; 214 215 hash = hash_mod (REGNO (dest), table->size); 216 217 for (cur_expr = table->table[hash]; cur_expr; 218 cur_expr = cur_expr->next_same_hash) 219 { 220 if (dest == cur_expr->dest 221 && src == cur_expr->src) 222 { 223 found = true; 224 break; 225 } 226 last_expr = cur_expr; 227 } 228 229 if (! found) 230 { 231 cur_expr = GOBNEW (struct cprop_expr); 232 bytes_used += sizeof (struct cprop_expr); 233 if (table->table[hash] == NULL) 234 /* This is the first pattern that hashed to this index. */ 235 table->table[hash] = cur_expr; 236 else 237 /* Add EXPR to end of this hash chain. */ 238 last_expr->next_same_hash = cur_expr; 239 240 /* Set the fields of the expr element. 241 We must copy X because it can be modified when copy propagation is 242 performed on its operands. */ 243 cur_expr->dest = copy_rtx (dest); 244 cur_expr->src = copy_rtx (src); 245 cur_expr->bitmap_index = table->n_elems++; 246 cur_expr->next_same_hash = NULL; 247 cur_expr->avail_occr = NULL; 248 } 249 250 /* Now record the occurrence. */ 251 cur_occr = cur_expr->avail_occr; 252 253 if (cur_occr 254 && BLOCK_FOR_INSN (cur_occr->insn) == BLOCK_FOR_INSN (insn)) 255 { 256 /* Found another instance of the expression in the same basic block. 257 Prefer this occurrence to the currently recorded one. We want 258 the last one in the block and the block is scanned from start 259 to end. */ 260 cur_occr->insn = insn; 261 } 262 else 263 { 264 /* First occurrence of this expression in this basic block. */ 265 cur_occr = GOBNEW (struct cprop_occr); 266 bytes_used += sizeof (struct cprop_occr); 267 cur_occr->insn = insn; 268 cur_occr->next = cur_expr->avail_occr; 269 cur_expr->avail_occr = cur_occr; 270 } 271 272 /* Record bitmap_index of the implicit set in implicit_set_indexes. */ 273 if (implicit) 274 implicit_set_indexes[BLOCK_FOR_INSN (insn)->index] 275 = cur_expr->bitmap_index; 276} 277 278/* Determine whether the rtx X should be treated as a constant for CPROP. 279 Since X might be inserted more than once we have to take care that it 280 is sharable. */ 281 282static bool 283cprop_constant_p (const_rtx x) 284{ 285 return CONSTANT_P (x) && (GET_CODE (x) != CONST || shared_const_p (x)); 286} 287 288/* Scan SET present in INSN and add an entry to the hash TABLE. 289 IMPLICIT is true if it's an implicit set, false otherwise. */ 290 291static void 292hash_scan_set (rtx set, rtx_insn *insn, struct hash_table_d *table, 293 bool implicit) 294{ 295 rtx src = SET_SRC (set); 296 rtx dest = SET_DEST (set); 297 298 if (REG_P (dest) 299 && ! HARD_REGISTER_P (dest) 300 && reg_available_p (dest, insn) 301 && can_copy_p (GET_MODE (dest))) 302 { 303 /* See if a REG_EQUAL note shows this equivalent to a simpler expression. 304 305 This allows us to do a single CPROP pass and still eliminate 306 redundant constants, addresses or other expressions that are 307 constructed with multiple instructions. 308 309 However, keep the original SRC if INSN is a simple reg-reg move. In 310 In this case, there will almost always be a REG_EQUAL note on the 311 insn that sets SRC. By recording the REG_EQUAL value here as SRC 312 for INSN, we miss copy propagation opportunities. 313 314 Note that this does not impede profitable constant propagations. We 315 "look through" reg-reg sets in lookup_set. */ 316 rtx note = find_reg_equal_equiv_note (insn); 317 if (note != 0 318 && REG_NOTE_KIND (note) == REG_EQUAL 319 && !REG_P (src) 320 && cprop_constant_p (XEXP (note, 0))) 321 src = XEXP (note, 0), set = gen_rtx_SET (VOIDmode, dest, src); 322 323 /* Record sets for constant/copy propagation. */ 324 if ((REG_P (src) 325 && src != dest 326 && ! HARD_REGISTER_P (src) 327 && reg_available_p (src, insn)) 328 || cprop_constant_p (src)) 329 insert_set_in_table (dest, src, insn, table, implicit); 330 } 331} 332 333/* Process INSN and add hash table entries as appropriate. */ 334 335static void 336hash_scan_insn (rtx_insn *insn, struct hash_table_d *table) 337{ 338 rtx pat = PATTERN (insn); 339 int i; 340 341 /* Pick out the sets of INSN and for other forms of instructions record 342 what's been modified. */ 343 344 if (GET_CODE (pat) == SET) 345 hash_scan_set (pat, insn, table, false); 346 else if (GET_CODE (pat) == PARALLEL) 347 for (i = 0; i < XVECLEN (pat, 0); i++) 348 { 349 rtx x = XVECEXP (pat, 0, i); 350 351 if (GET_CODE (x) == SET) 352 hash_scan_set (x, insn, table, false); 353 } 354} 355 356/* Dump the hash table TABLE to file FILE under the name NAME. */ 357 358static void 359dump_hash_table (FILE *file, const char *name, struct hash_table_d *table) 360{ 361 int i; 362 /* Flattened out table, so it's printed in proper order. */ 363 struct cprop_expr **flat_table; 364 unsigned int *hash_val; 365 struct cprop_expr *expr; 366 367 flat_table = XCNEWVEC (struct cprop_expr *, table->n_elems); 368 hash_val = XNEWVEC (unsigned int, table->n_elems); 369 370 for (i = 0; i < (int) table->size; i++) 371 for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash) 372 { 373 flat_table[expr->bitmap_index] = expr; 374 hash_val[expr->bitmap_index] = i; 375 } 376 377 fprintf (file, "%s hash table (%d buckets, %d entries)\n", 378 name, table->size, table->n_elems); 379 380 for (i = 0; i < (int) table->n_elems; i++) 381 if (flat_table[i] != 0) 382 { 383 expr = flat_table[i]; 384 fprintf (file, "Index %d (hash value %d)\n ", 385 expr->bitmap_index, hash_val[i]); 386 print_rtl (file, expr->dest); 387 fprintf (file, " := "); 388 print_rtl (file, expr->src); 389 fprintf (file, "\n"); 390 } 391 392 fprintf (file, "\n"); 393 394 free (flat_table); 395 free (hash_val); 396} 397 398/* Record as unavailable all registers that are DEF operands of INSN. */ 399 400static void 401make_set_regs_unavailable (rtx_insn *insn) 402{ 403 df_ref def; 404 405 FOR_EACH_INSN_DEF (def, insn) 406 SET_REGNO_REG_SET (reg_set_bitmap, DF_REF_REGNO (def)); 407} 408 409/* Top level function to create an assignment hash table. 410 411 Assignment entries are placed in the hash table if 412 - they are of the form (set (pseudo-reg) src), 413 - src is something we want to perform const/copy propagation on, 414 - none of the operands or target are subsequently modified in the block 415 416 Currently src must be a pseudo-reg or a const_int. 417 418 TABLE is the table computed. */ 419 420static void 421compute_hash_table_work (struct hash_table_d *table) 422{ 423 basic_block bb; 424 425 /* Allocate vars to track sets of regs. */ 426 reg_set_bitmap = ALLOC_REG_SET (NULL); 427 428 FOR_EACH_BB_FN (bb, cfun) 429 { 430 rtx_insn *insn; 431 432 /* Reset tables used to keep track of what's not yet invalid [since 433 the end of the block]. */ 434 CLEAR_REG_SET (reg_set_bitmap); 435 436 /* Go over all insns from the last to the first. This is convenient 437 for tracking available registers, i.e. not set between INSN and 438 the end of the basic block BB. */ 439 FOR_BB_INSNS_REVERSE (bb, insn) 440 { 441 /* Only real insns are interesting. */ 442 if (!NONDEBUG_INSN_P (insn)) 443 continue; 444 445 /* Record interesting sets from INSN in the hash table. */ 446 hash_scan_insn (insn, table); 447 448 /* Any registers set in INSN will make SETs above it not AVAIL. */ 449 make_set_regs_unavailable (insn); 450 } 451 452 /* Insert implicit sets in the hash table, pretending they appear as 453 insns at the head of the basic block. */ 454 if (implicit_sets[bb->index] != NULL_RTX) 455 hash_scan_set (implicit_sets[bb->index], BB_HEAD (bb), table, true); 456 } 457 458 FREE_REG_SET (reg_set_bitmap); 459} 460 461/* Allocate space for the set/expr hash TABLE. 462 It is used to determine the number of buckets to use. */ 463 464static void 465alloc_hash_table (struct hash_table_d *table) 466{ 467 int n; 468 469 n = get_max_insn_count (); 470 471 table->size = n / 4; 472 if (table->size < 11) 473 table->size = 11; 474 475 /* Attempt to maintain efficient use of hash table. 476 Making it an odd number is simplest for now. 477 ??? Later take some measurements. */ 478 table->size |= 1; 479 n = table->size * sizeof (struct cprop_expr *); 480 table->table = XNEWVAR (struct cprop_expr *, n); 481} 482 483/* Free things allocated by alloc_hash_table. */ 484 485static void 486free_hash_table (struct hash_table_d *table) 487{ 488 free (table->table); 489} 490 491/* Compute the hash TABLE for doing copy/const propagation or 492 expression hash table. */ 493 494static void 495compute_hash_table (struct hash_table_d *table) 496{ 497 /* Initialize count of number of entries in hash table. */ 498 table->n_elems = 0; 499 memset (table->table, 0, table->size * sizeof (struct cprop_expr *)); 500 501 compute_hash_table_work (table); 502} 503 504/* Expression tracking support. */ 505 506/* Lookup REGNO in the set TABLE. The result is a pointer to the 507 table entry, or NULL if not found. */ 508 509static struct cprop_expr * 510lookup_set (unsigned int regno, struct hash_table_d *table) 511{ 512 unsigned int hash = hash_mod (regno, table->size); 513 struct cprop_expr *expr; 514 515 expr = table->table[hash]; 516 517 while (expr && REGNO (expr->dest) != regno) 518 expr = expr->next_same_hash; 519 520 return expr; 521} 522 523/* Return the next entry for REGNO in list EXPR. */ 524 525static struct cprop_expr * 526next_set (unsigned int regno, struct cprop_expr *expr) 527{ 528 do 529 expr = expr->next_same_hash; 530 while (expr && REGNO (expr->dest) != regno); 531 532 return expr; 533} 534 535/* Reset tables used to keep track of what's still available [since the 536 start of the block]. */ 537 538static void 539reset_opr_set_tables (void) 540{ 541 /* Maintain a bitmap of which regs have been set since beginning of 542 the block. */ 543 CLEAR_REG_SET (reg_set_bitmap); 544} 545 546/* Return nonzero if the register X has not been set yet [since the 547 start of the basic block containing INSN]. */ 548 549static int 550reg_not_set_p (const_rtx x, const rtx_insn *insn ATTRIBUTE_UNUSED) 551{ 552 return ! REGNO_REG_SET_P (reg_set_bitmap, REGNO (x)); 553} 554 555/* Record things set by INSN. 556 This data is used by reg_not_set_p. */ 557 558static void 559mark_oprs_set (rtx_insn *insn) 560{ 561 df_ref def; 562 563 FOR_EACH_INSN_DEF (def, insn) 564 SET_REGNO_REG_SET (reg_set_bitmap, DF_REF_REGNO (def)); 565} 566 567/* Compute copy/constant propagation working variables. */ 568 569/* Local properties of assignments. */ 570static sbitmap *cprop_avloc; 571static sbitmap *cprop_kill; 572 573/* Global properties of assignments (computed from the local properties). */ 574static sbitmap *cprop_avin; 575static sbitmap *cprop_avout; 576 577/* Allocate vars used for copy/const propagation. N_BLOCKS is the number of 578 basic blocks. N_SETS is the number of sets. */ 579 580static void 581alloc_cprop_mem (int n_blocks, int n_sets) 582{ 583 cprop_avloc = sbitmap_vector_alloc (n_blocks, n_sets); 584 cprop_kill = sbitmap_vector_alloc (n_blocks, n_sets); 585 586 cprop_avin = sbitmap_vector_alloc (n_blocks, n_sets); 587 cprop_avout = sbitmap_vector_alloc (n_blocks, n_sets); 588} 589 590/* Free vars used by copy/const propagation. */ 591 592static void 593free_cprop_mem (void) 594{ 595 sbitmap_vector_free (cprop_avloc); 596 sbitmap_vector_free (cprop_kill); 597 sbitmap_vector_free (cprop_avin); 598 sbitmap_vector_free (cprop_avout); 599} 600 601/* Compute the local properties of each recorded expression. 602 603 Local properties are those that are defined by the block, irrespective of 604 other blocks. 605 606 An expression is killed in a block if its operands, either DEST or SRC, are 607 modified in the block. 608 609 An expression is computed (locally available) in a block if it is computed 610 at least once and expression would contain the same value if the 611 computation was moved to the end of the block. 612 613 KILL and COMP are destination sbitmaps for recording local properties. */ 614 615static void 616compute_local_properties (sbitmap *kill, sbitmap *comp, 617 struct hash_table_d *table) 618{ 619 unsigned int i; 620 621 /* Initialize the bitmaps that were passed in. */ 622 bitmap_vector_clear (kill, last_basic_block_for_fn (cfun)); 623 bitmap_vector_clear (comp, last_basic_block_for_fn (cfun)); 624 625 for (i = 0; i < table->size; i++) 626 { 627 struct cprop_expr *expr; 628 629 for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash) 630 { 631 int indx = expr->bitmap_index; 632 df_ref def; 633 struct cprop_occr *occr; 634 635 /* For each definition of the destination pseudo-reg, the expression 636 is killed in the block where the definition is. */ 637 for (def = DF_REG_DEF_CHAIN (REGNO (expr->dest)); 638 def; def = DF_REF_NEXT_REG (def)) 639 bitmap_set_bit (kill[DF_REF_BB (def)->index], indx); 640 641 /* If the source is a pseudo-reg, for each definition of the source, 642 the expression is killed in the block where the definition is. */ 643 if (REG_P (expr->src)) 644 for (def = DF_REG_DEF_CHAIN (REGNO (expr->src)); 645 def; def = DF_REF_NEXT_REG (def)) 646 bitmap_set_bit (kill[DF_REF_BB (def)->index], indx); 647 648 /* The occurrences recorded in avail_occr are exactly those that 649 are locally available in the block where they are. */ 650 for (occr = expr->avail_occr; occr != NULL; occr = occr->next) 651 { 652 bitmap_set_bit (comp[BLOCK_FOR_INSN (occr->insn)->index], indx); 653 } 654 } 655 } 656} 657 658/* Hash table support. */ 659 660/* Top level routine to do the dataflow analysis needed by copy/const 661 propagation. */ 662 663static void 664compute_cprop_data (void) 665{ 666 basic_block bb; 667 668 compute_local_properties (cprop_kill, cprop_avloc, &set_hash_table); 669 compute_available (cprop_avloc, cprop_kill, cprop_avout, cprop_avin); 670 671 /* Merge implicit sets into CPROP_AVIN. They are always available at the 672 entry of their basic block. We need to do this because 1) implicit sets 673 aren't recorded for the local pass so they cannot be propagated within 674 their basic block by this pass and 2) the global pass would otherwise 675 propagate them only in the successors of their basic block. */ 676 FOR_EACH_BB_FN (bb, cfun) 677 { 678 int index = implicit_set_indexes[bb->index]; 679 if (index != -1) 680 bitmap_set_bit (cprop_avin[bb->index], index); 681 } 682} 683 684/* Copy/constant propagation. */ 685 686/* Maximum number of register uses in an insn that we handle. */ 687#define MAX_USES 8 688 689/* Table of uses (registers, both hard and pseudo) found in an insn. 690 Allocated statically to avoid alloc/free complexity and overhead. */ 691static rtx reg_use_table[MAX_USES]; 692 693/* Index into `reg_use_table' while building it. */ 694static unsigned reg_use_count; 695 696/* Set up a list of register numbers used in INSN. The found uses are stored 697 in `reg_use_table'. `reg_use_count' is initialized to zero before entry, 698 and contains the number of uses in the table upon exit. 699 700 ??? If a register appears multiple times we will record it multiple times. 701 This doesn't hurt anything but it will slow things down. */ 702 703static void 704find_used_regs (rtx *xptr, void *data ATTRIBUTE_UNUSED) 705{ 706 int i, j; 707 enum rtx_code code; 708 const char *fmt; 709 rtx x = *xptr; 710 711 /* repeat is used to turn tail-recursion into iteration since GCC 712 can't do it when there's no return value. */ 713 repeat: 714 if (x == 0) 715 return; 716 717 code = GET_CODE (x); 718 if (REG_P (x)) 719 { 720 if (reg_use_count == MAX_USES) 721 return; 722 723 reg_use_table[reg_use_count] = x; 724 reg_use_count++; 725 } 726 727 /* Recursively scan the operands of this expression. */ 728 729 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--) 730 { 731 if (fmt[i] == 'e') 732 { 733 /* If we are about to do the last recursive call 734 needed at this level, change it into iteration. 735 This function is called enough to be worth it. */ 736 if (i == 0) 737 { 738 x = XEXP (x, 0); 739 goto repeat; 740 } 741 742 find_used_regs (&XEXP (x, i), data); 743 } 744 else if (fmt[i] == 'E') 745 for (j = 0; j < XVECLEN (x, i); j++) 746 find_used_regs (&XVECEXP (x, i, j), data); 747 } 748} 749 750/* Try to replace all uses of FROM in INSN with TO. 751 Return nonzero if successful. */ 752 753static int 754try_replace_reg (rtx from, rtx to, rtx_insn *insn) 755{ 756 rtx note = find_reg_equal_equiv_note (insn); 757 rtx src = 0; 758 int success = 0; 759 rtx set = single_set (insn); 760 761 /* Usually we substitute easy stuff, so we won't copy everything. 762 We however need to take care to not duplicate non-trivial CONST 763 expressions. */ 764 to = copy_rtx (to); 765 766 validate_replace_src_group (from, to, insn); 767 if (num_changes_pending () && apply_change_group ()) 768 success = 1; 769 770 /* Try to simplify SET_SRC if we have substituted a constant. */ 771 if (success && set && CONSTANT_P (to)) 772 { 773 src = simplify_rtx (SET_SRC (set)); 774 775 if (src) 776 validate_change (insn, &SET_SRC (set), src, 0); 777 } 778 779 /* If there is already a REG_EQUAL note, update the expression in it 780 with our replacement. */ 781 if (note != 0 && REG_NOTE_KIND (note) == REG_EQUAL) 782 set_unique_reg_note (insn, REG_EQUAL, 783 simplify_replace_rtx (XEXP (note, 0), from, to)); 784 if (!success && set && reg_mentioned_p (from, SET_SRC (set))) 785 { 786 /* If above failed and this is a single set, try to simplify the source 787 of the set given our substitution. We could perhaps try this for 788 multiple SETs, but it probably won't buy us anything. */ 789 src = simplify_replace_rtx (SET_SRC (set), from, to); 790 791 if (!rtx_equal_p (src, SET_SRC (set)) 792 && validate_change (insn, &SET_SRC (set), src, 0)) 793 success = 1; 794 795 /* If we've failed perform the replacement, have a single SET to 796 a REG destination and don't yet have a note, add a REG_EQUAL note 797 to not lose information. */ 798 if (!success && note == 0 && set != 0 && REG_P (SET_DEST (set))) 799 note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src)); 800 } 801 802 if (set && MEM_P (SET_DEST (set)) && reg_mentioned_p (from, SET_DEST (set))) 803 { 804 /* Registers can also appear as uses in SET_DEST if it is a MEM. 805 We could perhaps try this for multiple SETs, but it probably 806 won't buy us anything. */ 807 rtx dest = simplify_replace_rtx (SET_DEST (set), from, to); 808 809 if (!rtx_equal_p (dest, SET_DEST (set)) 810 && validate_change (insn, &SET_DEST (set), dest, 0)) 811 success = 1; 812 } 813 814 /* REG_EQUAL may get simplified into register. 815 We don't allow that. Remove that note. This code ought 816 not to happen, because previous code ought to synthesize 817 reg-reg move, but be on the safe side. */ 818 if (note && REG_NOTE_KIND (note) == REG_EQUAL && REG_P (XEXP (note, 0))) 819 remove_note (insn, note); 820 821 return success; 822} 823 824/* Find a set of REGNOs that are available on entry to INSN's block. Return 825 NULL no such set is found. */ 826 827static struct cprop_expr * 828find_avail_set (int regno, rtx_insn *insn) 829{ 830 /* SET1 contains the last set found that can be returned to the caller for 831 use in a substitution. */ 832 struct cprop_expr *set1 = 0; 833 834 /* Loops are not possible here. To get a loop we would need two sets 835 available at the start of the block containing INSN. i.e. we would 836 need two sets like this available at the start of the block: 837 838 (set (reg X) (reg Y)) 839 (set (reg Y) (reg X)) 840 841 This can not happen since the set of (reg Y) would have killed the 842 set of (reg X) making it unavailable at the start of this block. */ 843 while (1) 844 { 845 rtx src; 846 struct cprop_expr *set = lookup_set (regno, &set_hash_table); 847 848 /* Find a set that is available at the start of the block 849 which contains INSN. */ 850 while (set) 851 { 852 if (bitmap_bit_p (cprop_avin[BLOCK_FOR_INSN (insn)->index], 853 set->bitmap_index)) 854 break; 855 set = next_set (regno, set); 856 } 857 858 /* If no available set was found we've reached the end of the 859 (possibly empty) copy chain. */ 860 if (set == 0) 861 break; 862 863 src = set->src; 864 865 /* We know the set is available. 866 Now check that SRC is locally anticipatable (i.e. none of the 867 source operands have changed since the start of the block). 868 869 If the source operand changed, we may still use it for the next 870 iteration of this loop, but we may not use it for substitutions. */ 871 872 if (cprop_constant_p (src) || reg_not_set_p (src, insn)) 873 set1 = set; 874 875 /* If the source of the set is anything except a register, then 876 we have reached the end of the copy chain. */ 877 if (! REG_P (src)) 878 break; 879 880 /* Follow the copy chain, i.e. start another iteration of the loop 881 and see if we have an available copy into SRC. */ 882 regno = REGNO (src); 883 } 884 885 /* SET1 holds the last set that was available and anticipatable at 886 INSN. */ 887 return set1; 888} 889 890/* Subroutine of cprop_insn that tries to propagate constants into 891 JUMP_INSNS. JUMP must be a conditional jump. If SETCC is non-NULL 892 it is the instruction that immediately precedes JUMP, and must be a 893 single SET of a register. FROM is what we will try to replace, 894 SRC is the constant we will try to substitute for it. Return nonzero 895 if a change was made. */ 896 897static int 898cprop_jump (basic_block bb, rtx_insn *setcc, rtx_insn *jump, rtx from, rtx src) 899{ 900 rtx new_rtx, set_src, note_src; 901 rtx set = pc_set (jump); 902 rtx note = find_reg_equal_equiv_note (jump); 903 904 if (note) 905 { 906 note_src = XEXP (note, 0); 907 if (GET_CODE (note_src) == EXPR_LIST) 908 note_src = NULL_RTX; 909 } 910 else note_src = NULL_RTX; 911 912 /* Prefer REG_EQUAL notes except those containing EXPR_LISTs. */ 913 set_src = note_src ? note_src : SET_SRC (set); 914 915 /* First substitute the SETCC condition into the JUMP instruction, 916 then substitute that given values into this expanded JUMP. */ 917 if (setcc != NULL_RTX 918 && !modified_between_p (from, setcc, jump) 919 && !modified_between_p (src, setcc, jump)) 920 { 921 rtx setcc_src; 922 rtx setcc_set = single_set (setcc); 923 rtx setcc_note = find_reg_equal_equiv_note (setcc); 924 setcc_src = (setcc_note && GET_CODE (XEXP (setcc_note, 0)) != EXPR_LIST) 925 ? XEXP (setcc_note, 0) : SET_SRC (setcc_set); 926 set_src = simplify_replace_rtx (set_src, SET_DEST (setcc_set), 927 setcc_src); 928 } 929 else 930 setcc = NULL; 931 932 new_rtx = simplify_replace_rtx (set_src, from, src); 933 934 /* If no simplification can be made, then try the next register. */ 935 if (rtx_equal_p (new_rtx, SET_SRC (set))) 936 return 0; 937 938 /* If this is now a no-op delete it, otherwise this must be a valid insn. */ 939 if (new_rtx == pc_rtx) 940 delete_insn (jump); 941 else 942 { 943 /* Ensure the value computed inside the jump insn to be equivalent 944 to one computed by setcc. */ 945 if (setcc && modified_in_p (new_rtx, setcc)) 946 return 0; 947 if (! validate_unshare_change (jump, &SET_SRC (set), new_rtx, 0)) 948 { 949 /* When (some) constants are not valid in a comparison, and there 950 are two registers to be replaced by constants before the entire 951 comparison can be folded into a constant, we need to keep 952 intermediate information in REG_EQUAL notes. For targets with 953 separate compare insns, such notes are added by try_replace_reg. 954 When we have a combined compare-and-branch instruction, however, 955 we need to attach a note to the branch itself to make this 956 optimization work. */ 957 958 if (!rtx_equal_p (new_rtx, note_src)) 959 set_unique_reg_note (jump, REG_EQUAL, copy_rtx (new_rtx)); 960 return 0; 961 } 962 963 /* Remove REG_EQUAL note after simplification. */ 964 if (note_src) 965 remove_note (jump, note); 966 } 967 968#ifdef HAVE_cc0 969 /* Delete the cc0 setter. */ 970 if (setcc != NULL && CC0_P (SET_DEST (single_set (setcc)))) 971 delete_insn (setcc); 972#endif 973 974 global_const_prop_count++; 975 if (dump_file != NULL) 976 { 977 fprintf (dump_file, 978 "GLOBAL CONST-PROP: Replacing reg %d in jump_insn %d with" 979 "constant ", REGNO (from), INSN_UID (jump)); 980 print_rtl (dump_file, src); 981 fprintf (dump_file, "\n"); 982 } 983 purge_dead_edges (bb); 984 985 /* If a conditional jump has been changed into unconditional jump, remove 986 the jump and make the edge fallthru - this is always called in 987 cfglayout mode. */ 988 if (new_rtx != pc_rtx && simplejump_p (jump)) 989 { 990 edge e; 991 edge_iterator ei; 992 993 FOR_EACH_EDGE (e, ei, bb->succs) 994 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) 995 && BB_HEAD (e->dest) == JUMP_LABEL (jump)) 996 { 997 e->flags |= EDGE_FALLTHRU; 998 break; 999 } 1000 delete_insn (jump); 1001 } 1002 1003 return 1; 1004} 1005 1006/* Subroutine of cprop_insn that tries to propagate constants. FROM is what 1007 we will try to replace, SRC is the constant we will try to substitute for 1008 it and INSN is the instruction where this will be happening. */ 1009 1010static int 1011constprop_register (rtx from, rtx src, rtx_insn *insn) 1012{ 1013 rtx sset; 1014 1015 /* Check for reg or cc0 setting instructions followed by 1016 conditional branch instructions first. */ 1017 if ((sset = single_set (insn)) != NULL 1018 && NEXT_INSN (insn) 1019 && any_condjump_p (NEXT_INSN (insn)) && onlyjump_p (NEXT_INSN (insn))) 1020 { 1021 rtx dest = SET_DEST (sset); 1022 if ((REG_P (dest) || CC0_P (dest)) 1023 && cprop_jump (BLOCK_FOR_INSN (insn), insn, NEXT_INSN (insn), 1024 from, src)) 1025 return 1; 1026 } 1027 1028 /* Handle normal insns next. */ 1029 if (NONJUMP_INSN_P (insn) && try_replace_reg (from, src, insn)) 1030 return 1; 1031 1032 /* Try to propagate a CONST_INT into a conditional jump. 1033 We're pretty specific about what we will handle in this 1034 code, we can extend this as necessary over time. 1035 1036 Right now the insn in question must look like 1037 (set (pc) (if_then_else ...)) */ 1038 else if (any_condjump_p (insn) && onlyjump_p (insn)) 1039 return cprop_jump (BLOCK_FOR_INSN (insn), NULL, insn, from, src); 1040 return 0; 1041} 1042 1043/* Perform constant and copy propagation on INSN. 1044 Return nonzero if a change was made. */ 1045 1046static int 1047cprop_insn (rtx_insn *insn) 1048{ 1049 unsigned i; 1050 int changed = 0, changed_this_round; 1051 rtx note; 1052 1053retry: 1054 changed_this_round = 0; 1055 reg_use_count = 0; 1056 note_uses (&PATTERN (insn), find_used_regs, NULL); 1057 1058 /* We may win even when propagating constants into notes. */ 1059 note = find_reg_equal_equiv_note (insn); 1060 if (note) 1061 find_used_regs (&XEXP (note, 0), NULL); 1062 1063 for (i = 0; i < reg_use_count; i++) 1064 { 1065 rtx reg_used = reg_use_table[i]; 1066 unsigned int regno = REGNO (reg_used); 1067 rtx src; 1068 struct cprop_expr *set; 1069 1070 /* If the register has already been set in this block, there's 1071 nothing we can do. */ 1072 if (! reg_not_set_p (reg_used, insn)) 1073 continue; 1074 1075 /* Find an assignment that sets reg_used and is available 1076 at the start of the block. */ 1077 set = find_avail_set (regno, insn); 1078 if (! set) 1079 continue; 1080 1081 src = set->src; 1082 1083 /* Constant propagation. */ 1084 if (cprop_constant_p (src)) 1085 { 1086 if (constprop_register (reg_used, src, insn)) 1087 { 1088 changed_this_round = changed = 1; 1089 global_const_prop_count++; 1090 if (dump_file != NULL) 1091 { 1092 fprintf (dump_file, 1093 "GLOBAL CONST-PROP: Replacing reg %d in ", regno); 1094 fprintf (dump_file, "insn %d with constant ", 1095 INSN_UID (insn)); 1096 print_rtl (dump_file, src); 1097 fprintf (dump_file, "\n"); 1098 } 1099 if (insn->deleted ()) 1100 return 1; 1101 } 1102 } 1103 else if (REG_P (src) 1104 && REGNO (src) >= FIRST_PSEUDO_REGISTER 1105 && REGNO (src) != regno) 1106 { 1107 if (try_replace_reg (reg_used, src, insn)) 1108 { 1109 changed_this_round = changed = 1; 1110 global_copy_prop_count++; 1111 if (dump_file != NULL) 1112 { 1113 fprintf (dump_file, 1114 "GLOBAL COPY-PROP: Replacing reg %d in insn %d", 1115 regno, INSN_UID (insn)); 1116 fprintf (dump_file, " with reg %d\n", REGNO (src)); 1117 } 1118 1119 /* The original insn setting reg_used may or may not now be 1120 deletable. We leave the deletion to DCE. */ 1121 /* FIXME: If it turns out that the insn isn't deletable, 1122 then we may have unnecessarily extended register lifetimes 1123 and made things worse. */ 1124 } 1125 } 1126 1127 /* If try_replace_reg simplified the insn, the regs found 1128 by find_used_regs may not be valid anymore. Start over. */ 1129 if (changed_this_round) 1130 goto retry; 1131 } 1132 1133 if (changed && DEBUG_INSN_P (insn)) 1134 return 0; 1135 1136 return changed; 1137} 1138 1139/* Like find_used_regs, but avoid recording uses that appear in 1140 input-output contexts such as zero_extract or pre_dec. This 1141 restricts the cases we consider to those for which local cprop 1142 can legitimately make replacements. */ 1143 1144static void 1145local_cprop_find_used_regs (rtx *xptr, void *data) 1146{ 1147 rtx x = *xptr; 1148 1149 if (x == 0) 1150 return; 1151 1152 switch (GET_CODE (x)) 1153 { 1154 case ZERO_EXTRACT: 1155 case SIGN_EXTRACT: 1156 case STRICT_LOW_PART: 1157 return; 1158 1159 case PRE_DEC: 1160 case PRE_INC: 1161 case POST_DEC: 1162 case POST_INC: 1163 case PRE_MODIFY: 1164 case POST_MODIFY: 1165 /* Can only legitimately appear this early in the context of 1166 stack pushes for function arguments, but handle all of the 1167 codes nonetheless. */ 1168 return; 1169 1170 case SUBREG: 1171 /* Setting a subreg of a register larger than word_mode leaves 1172 the non-written words unchanged. */ 1173 if (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))) > BITS_PER_WORD) 1174 return; 1175 break; 1176 1177 default: 1178 break; 1179 } 1180 1181 find_used_regs (xptr, data); 1182} 1183 1184/* Try to perform local const/copy propagation on X in INSN. */ 1185 1186static bool 1187do_local_cprop (rtx x, rtx_insn *insn) 1188{ 1189 rtx newreg = NULL, newcnst = NULL; 1190 1191 /* Rule out USE instructions and ASM statements as we don't want to 1192 change the hard registers mentioned. */ 1193 if (REG_P (x) 1194 && (REGNO (x) >= FIRST_PSEUDO_REGISTER 1195 || (GET_CODE (PATTERN (insn)) != USE 1196 && asm_noperands (PATTERN (insn)) < 0))) 1197 { 1198 cselib_val *val = cselib_lookup (x, GET_MODE (x), 0, VOIDmode); 1199 struct elt_loc_list *l; 1200 1201 if (!val) 1202 return false; 1203 for (l = val->locs; l; l = l->next) 1204 { 1205 rtx this_rtx = l->loc; 1206 rtx note; 1207 1208 if (cprop_constant_p (this_rtx)) 1209 newcnst = this_rtx; 1210 if (REG_P (this_rtx) && REGNO (this_rtx) >= FIRST_PSEUDO_REGISTER 1211 /* Don't copy propagate if it has attached REG_EQUIV note. 1212 At this point this only function parameters should have 1213 REG_EQUIV notes and if the argument slot is used somewhere 1214 explicitly, it means address of parameter has been taken, 1215 so we should not extend the lifetime of the pseudo. */ 1216 && (!(note = find_reg_note (l->setting_insn, REG_EQUIV, NULL_RTX)) 1217 || ! MEM_P (XEXP (note, 0)))) 1218 newreg = this_rtx; 1219 } 1220 if (newcnst && constprop_register (x, newcnst, insn)) 1221 { 1222 if (dump_file != NULL) 1223 { 1224 fprintf (dump_file, "LOCAL CONST-PROP: Replacing reg %d in ", 1225 REGNO (x)); 1226 fprintf (dump_file, "insn %d with constant ", 1227 INSN_UID (insn)); 1228 print_rtl (dump_file, newcnst); 1229 fprintf (dump_file, "\n"); 1230 } 1231 local_const_prop_count++; 1232 return true; 1233 } 1234 else if (newreg && newreg != x && try_replace_reg (x, newreg, insn)) 1235 { 1236 if (dump_file != NULL) 1237 { 1238 fprintf (dump_file, 1239 "LOCAL COPY-PROP: Replacing reg %d in insn %d", 1240 REGNO (x), INSN_UID (insn)); 1241 fprintf (dump_file, " with reg %d\n", REGNO (newreg)); 1242 } 1243 local_copy_prop_count++; 1244 return true; 1245 } 1246 } 1247 return false; 1248} 1249 1250/* Do local const/copy propagation (i.e. within each basic block). */ 1251 1252static int 1253local_cprop_pass (void) 1254{ 1255 basic_block bb; 1256 rtx_insn *insn; 1257 bool changed = false; 1258 unsigned i; 1259 1260 cselib_init (0); 1261 FOR_EACH_BB_FN (bb, cfun) 1262 { 1263 FOR_BB_INSNS (bb, insn) 1264 { 1265 if (INSN_P (insn)) 1266 { 1267 rtx note = find_reg_equal_equiv_note (insn); 1268 do 1269 { 1270 reg_use_count = 0; 1271 note_uses (&PATTERN (insn), local_cprop_find_used_regs, 1272 NULL); 1273 if (note) 1274 local_cprop_find_used_regs (&XEXP (note, 0), NULL); 1275 1276 for (i = 0; i < reg_use_count; i++) 1277 { 1278 if (do_local_cprop (reg_use_table[i], insn)) 1279 { 1280 if (!DEBUG_INSN_P (insn)) 1281 changed = true; 1282 break; 1283 } 1284 } 1285 if (insn->deleted ()) 1286 break; 1287 } 1288 while (i < reg_use_count); 1289 } 1290 cselib_process_insn (insn); 1291 } 1292 1293 /* Forget everything at the end of a basic block. */ 1294 cselib_clear_table (); 1295 } 1296 1297 cselib_finish (); 1298 1299 return changed; 1300} 1301 1302/* Similar to get_condition, only the resulting condition must be 1303 valid at JUMP, instead of at EARLIEST. 1304 1305 This differs from noce_get_condition in ifcvt.c in that we prefer not to 1306 settle for the condition variable in the jump instruction being integral. 1307 We prefer to be able to record the value of a user variable, rather than 1308 the value of a temporary used in a condition. This could be solved by 1309 recording the value of *every* register scanned by canonicalize_condition, 1310 but this would require some code reorganization. */ 1311 1312rtx 1313fis_get_condition (rtx_insn *jump) 1314{ 1315 return get_condition (jump, NULL, false, true); 1316} 1317 1318/* Check the comparison COND to see if we can safely form an implicit 1319 set from it. */ 1320 1321static bool 1322implicit_set_cond_p (const_rtx cond) 1323{ 1324 machine_mode mode; 1325 rtx cst; 1326 1327 /* COND must be either an EQ or NE comparison. */ 1328 if (GET_CODE (cond) != EQ && GET_CODE (cond) != NE) 1329 return false; 1330 1331 /* The first operand of COND must be a pseudo-reg. */ 1332 if (! REG_P (XEXP (cond, 0)) 1333 || HARD_REGISTER_P (XEXP (cond, 0))) 1334 return false; 1335 1336 /* The second operand of COND must be a suitable constant. */ 1337 mode = GET_MODE (XEXP (cond, 0)); 1338 cst = XEXP (cond, 1); 1339 1340 /* We can't perform this optimization if either operand might be or might 1341 contain a signed zero. */ 1342 if (HONOR_SIGNED_ZEROS (mode)) 1343 { 1344 /* It is sufficient to check if CST is or contains a zero. We must 1345 handle float, complex, and vector. If any subpart is a zero, then 1346 the optimization can't be performed. */ 1347 /* ??? The complex and vector checks are not implemented yet. We just 1348 always return zero for them. */ 1349 if (CONST_DOUBLE_AS_FLOAT_P (cst)) 1350 { 1351 REAL_VALUE_TYPE d; 1352 REAL_VALUE_FROM_CONST_DOUBLE (d, cst); 1353 if (REAL_VALUES_EQUAL (d, dconst0)) 1354 return 0; 1355 } 1356 else 1357 return 0; 1358 } 1359 1360 return cprop_constant_p (cst); 1361} 1362 1363/* Find the implicit sets of a function. An "implicit set" is a constraint 1364 on the value of a variable, implied by a conditional jump. For example, 1365 following "if (x == 2)", the then branch may be optimized as though the 1366 conditional performed an "explicit set", in this example, "x = 2". This 1367 function records the set patterns that are implicit at the start of each 1368 basic block. 1369 1370 If an implicit set is found but the set is implicit on a critical edge, 1371 this critical edge is split. 1372 1373 Return true if the CFG was modified, false otherwise. */ 1374 1375static bool 1376find_implicit_sets (void) 1377{ 1378 basic_block bb, dest; 1379 rtx cond, new_rtx; 1380 unsigned int count = 0; 1381 bool edges_split = false; 1382 size_t implicit_sets_size = last_basic_block_for_fn (cfun) + 10; 1383 1384 implicit_sets = XCNEWVEC (rtx, implicit_sets_size); 1385 1386 FOR_EACH_BB_FN (bb, cfun) 1387 { 1388 /* Check for more than one successor. */ 1389 if (EDGE_COUNT (bb->succs) <= 1) 1390 continue; 1391 1392 cond = fis_get_condition (BB_END (bb)); 1393 1394 /* If no condition is found or if it isn't of a suitable form, 1395 ignore it. */ 1396 if (! cond || ! implicit_set_cond_p (cond)) 1397 continue; 1398 1399 dest = GET_CODE (cond) == EQ 1400 ? BRANCH_EDGE (bb)->dest : FALLTHRU_EDGE (bb)->dest; 1401 1402 /* If DEST doesn't go anywhere, ignore it. */ 1403 if (! dest || dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) 1404 continue; 1405 1406 /* We have found a suitable implicit set. Try to record it now as 1407 a SET in DEST. If DEST has more than one predecessor, the edge 1408 between BB and DEST is a critical edge and we must split it, 1409 because we can only record one implicit set per DEST basic block. */ 1410 if (! single_pred_p (dest)) 1411 { 1412 dest = split_edge (find_edge (bb, dest)); 1413 edges_split = true; 1414 } 1415 1416 if (implicit_sets_size <= (size_t) dest->index) 1417 { 1418 size_t old_implicit_sets_size = implicit_sets_size; 1419 implicit_sets_size *= 2; 1420 implicit_sets = XRESIZEVEC (rtx, implicit_sets, implicit_sets_size); 1421 memset (implicit_sets + old_implicit_sets_size, 0, 1422 (implicit_sets_size - old_implicit_sets_size) * sizeof (rtx)); 1423 } 1424 1425 new_rtx = gen_rtx_SET (VOIDmode, XEXP (cond, 0), 1426 XEXP (cond, 1)); 1427 implicit_sets[dest->index] = new_rtx; 1428 if (dump_file) 1429 { 1430 fprintf (dump_file, "Implicit set of reg %d in ", 1431 REGNO (XEXP (cond, 0))); 1432 fprintf (dump_file, "basic block %d\n", dest->index); 1433 } 1434 count++; 1435 } 1436 1437 if (dump_file) 1438 fprintf (dump_file, "Found %d implicit sets\n", count); 1439 1440 /* Confess our sins. */ 1441 return edges_split; 1442} 1443 1444/* Bypass conditional jumps. */ 1445 1446/* The value of last_basic_block at the beginning of the jump_bypass 1447 pass. The use of redirect_edge_and_branch_force may introduce new 1448 basic blocks, but the data flow analysis is only valid for basic 1449 block indices less than bypass_last_basic_block. */ 1450 1451static int bypass_last_basic_block; 1452 1453/* Find a set of REGNO to a constant that is available at the end of basic 1454 block BB. Return NULL if no such set is found. Based heavily upon 1455 find_avail_set. */ 1456 1457static struct cprop_expr * 1458find_bypass_set (int regno, int bb) 1459{ 1460 struct cprop_expr *result = 0; 1461 1462 for (;;) 1463 { 1464 rtx src; 1465 struct cprop_expr *set = lookup_set (regno, &set_hash_table); 1466 1467 while (set) 1468 { 1469 if (bitmap_bit_p (cprop_avout[bb], set->bitmap_index)) 1470 break; 1471 set = next_set (regno, set); 1472 } 1473 1474 if (set == 0) 1475 break; 1476 1477 src = set->src; 1478 if (cprop_constant_p (src)) 1479 result = set; 1480 1481 if (! REG_P (src)) 1482 break; 1483 1484 regno = REGNO (src); 1485 } 1486 return result; 1487} 1488 1489/* Subroutine of bypass_block that checks whether a pseudo is killed by 1490 any of the instructions inserted on an edge. Jump bypassing places 1491 condition code setters on CFG edges using insert_insn_on_edge. This 1492 function is required to check that our data flow analysis is still 1493 valid prior to commit_edge_insertions. */ 1494 1495static bool 1496reg_killed_on_edge (const_rtx reg, const_edge e) 1497{ 1498 rtx_insn *insn; 1499 1500 for (insn = e->insns.r; insn; insn = NEXT_INSN (insn)) 1501 if (INSN_P (insn) && reg_set_p (reg, insn)) 1502 return true; 1503 1504 return false; 1505} 1506 1507/* Subroutine of bypass_conditional_jumps that attempts to bypass the given 1508 basic block BB which has more than one predecessor. If not NULL, SETCC 1509 is the first instruction of BB, which is immediately followed by JUMP_INSN 1510 JUMP. Otherwise, SETCC is NULL, and JUMP is the first insn of BB. 1511 Returns nonzero if a change was made. 1512 1513 During the jump bypassing pass, we may place copies of SETCC instructions 1514 on CFG edges. The following routine must be careful to pay attention to 1515 these inserted insns when performing its transformations. */ 1516 1517static int 1518bypass_block (basic_block bb, rtx_insn *setcc, rtx_insn *jump) 1519{ 1520 rtx_insn *insn; 1521 rtx note; 1522 edge e, edest; 1523 int change; 1524 int may_be_loop_header = false; 1525 unsigned removed_p; 1526 unsigned i; 1527 edge_iterator ei; 1528 1529 insn = (setcc != NULL) ? setcc : jump; 1530 1531 /* Determine set of register uses in INSN. */ 1532 reg_use_count = 0; 1533 note_uses (&PATTERN (insn), find_used_regs, NULL); 1534 note = find_reg_equal_equiv_note (insn); 1535 if (note) 1536 find_used_regs (&XEXP (note, 0), NULL); 1537 1538 if (current_loops) 1539 { 1540 /* If we are to preserve loop structure then do not bypass 1541 a loop header. This will either rotate the loop, create 1542 multiple entry loops or even irreducible regions. */ 1543 if (bb == bb->loop_father->header) 1544 return 0; 1545 } 1546 else 1547 { 1548 FOR_EACH_EDGE (e, ei, bb->preds) 1549 if (e->flags & EDGE_DFS_BACK) 1550 { 1551 may_be_loop_header = true; 1552 break; 1553 } 1554 } 1555 1556 change = 0; 1557 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); ) 1558 { 1559 removed_p = 0; 1560 1561 if (e->flags & EDGE_COMPLEX) 1562 { 1563 ei_next (&ei); 1564 continue; 1565 } 1566 1567 /* We can't redirect edges from new basic blocks. */ 1568 if (e->src->index >= bypass_last_basic_block) 1569 { 1570 ei_next (&ei); 1571 continue; 1572 } 1573 1574 /* The irreducible loops created by redirecting of edges entering the 1575 loop from outside would decrease effectiveness of some of the 1576 following optimizations, so prevent this. */ 1577 if (may_be_loop_header 1578 && !(e->flags & EDGE_DFS_BACK)) 1579 { 1580 ei_next (&ei); 1581 continue; 1582 } 1583 1584 for (i = 0; i < reg_use_count; i++) 1585 { 1586 rtx reg_used = reg_use_table[i]; 1587 unsigned int regno = REGNO (reg_used); 1588 basic_block dest, old_dest; 1589 struct cprop_expr *set; 1590 rtx src, new_rtx; 1591 1592 set = find_bypass_set (regno, e->src->index); 1593 1594 if (! set) 1595 continue; 1596 1597 /* Check the data flow is valid after edge insertions. */ 1598 if (e->insns.r && reg_killed_on_edge (reg_used, e)) 1599 continue; 1600 1601 src = SET_SRC (pc_set (jump)); 1602 1603 if (setcc != NULL) 1604 src = simplify_replace_rtx (src, 1605 SET_DEST (PATTERN (setcc)), 1606 SET_SRC (PATTERN (setcc))); 1607 1608 new_rtx = simplify_replace_rtx (src, reg_used, set->src); 1609 1610 /* Jump bypassing may have already placed instructions on 1611 edges of the CFG. We can't bypass an outgoing edge that 1612 has instructions associated with it, as these insns won't 1613 get executed if the incoming edge is redirected. */ 1614 if (new_rtx == pc_rtx) 1615 { 1616 edest = FALLTHRU_EDGE (bb); 1617 dest = edest->insns.r ? NULL : edest->dest; 1618 } 1619 else if (GET_CODE (new_rtx) == LABEL_REF) 1620 { 1621 dest = BLOCK_FOR_INSN (XEXP (new_rtx, 0)); 1622 /* Don't bypass edges containing instructions. */ 1623 edest = find_edge (bb, dest); 1624 if (edest && edest->insns.r) 1625 dest = NULL; 1626 } 1627 else 1628 dest = NULL; 1629 1630 /* Avoid unification of the edge with other edges from original 1631 branch. We would end up emitting the instruction on "both" 1632 edges. */ 1633 if (dest && setcc && !CC0_P (SET_DEST (PATTERN (setcc))) 1634 && find_edge (e->src, dest)) 1635 dest = NULL; 1636 1637 old_dest = e->dest; 1638 if (dest != NULL 1639 && dest != old_dest 1640 && dest != EXIT_BLOCK_PTR_FOR_FN (cfun)) 1641 { 1642 redirect_edge_and_branch_force (e, dest); 1643 1644 /* Copy the register setter to the redirected edge. 1645 Don't copy CC0 setters, as CC0 is dead after jump. */ 1646 if (setcc) 1647 { 1648 rtx pat = PATTERN (setcc); 1649 if (!CC0_P (SET_DEST (pat))) 1650 insert_insn_on_edge (copy_insn (pat), e); 1651 } 1652 1653 if (dump_file != NULL) 1654 { 1655 fprintf (dump_file, "JUMP-BYPASS: Proved reg %d " 1656 "in jump_insn %d equals constant ", 1657 regno, INSN_UID (jump)); 1658 print_rtl (dump_file, set->src); 1659 fprintf (dump_file, "\n\t when BB %d is entered from " 1660 "BB %d. Redirect edge %d->%d to %d.\n", 1661 old_dest->index, e->src->index, e->src->index, 1662 old_dest->index, dest->index); 1663 } 1664 change = 1; 1665 removed_p = 1; 1666 break; 1667 } 1668 } 1669 if (!removed_p) 1670 ei_next (&ei); 1671 } 1672 return change; 1673} 1674 1675/* Find basic blocks with more than one predecessor that only contain a 1676 single conditional jump. If the result of the comparison is known at 1677 compile-time from any incoming edge, redirect that edge to the 1678 appropriate target. Return nonzero if a change was made. 1679 1680 This function is now mis-named, because we also handle indirect jumps. */ 1681 1682static int 1683bypass_conditional_jumps (void) 1684{ 1685 basic_block bb; 1686 int changed; 1687 rtx_insn *setcc; 1688 rtx_insn *insn; 1689 rtx dest; 1690 1691 /* Note we start at block 1. */ 1692 if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)) 1693 return 0; 1694 1695 bypass_last_basic_block = last_basic_block_for_fn (cfun); 1696 mark_dfs_back_edges (); 1697 1698 changed = 0; 1699 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb->next_bb, 1700 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb) 1701 { 1702 /* Check for more than one predecessor. */ 1703 if (!single_pred_p (bb)) 1704 { 1705 setcc = NULL; 1706 FOR_BB_INSNS (bb, insn) 1707 if (DEBUG_INSN_P (insn)) 1708 continue; 1709 else if (NONJUMP_INSN_P (insn)) 1710 { 1711 if (setcc) 1712 break; 1713 if (GET_CODE (PATTERN (insn)) != SET) 1714 break; 1715 1716 dest = SET_DEST (PATTERN (insn)); 1717 if (REG_P (dest) || CC0_P (dest)) 1718 setcc = insn; 1719 else 1720 break; 1721 } 1722 else if (JUMP_P (insn)) 1723 { 1724 if ((any_condjump_p (insn) || computed_jump_p (insn)) 1725 && onlyjump_p (insn)) 1726 changed |= bypass_block (bb, setcc, insn); 1727 break; 1728 } 1729 else if (INSN_P (insn)) 1730 break; 1731 } 1732 } 1733 1734 /* If we bypassed any register setting insns, we inserted a 1735 copy on the redirected edge. These need to be committed. */ 1736 if (changed) 1737 commit_edge_insertions (); 1738 1739 return changed; 1740} 1741 1742/* Return true if the graph is too expensive to optimize. PASS is the 1743 optimization about to be performed. */ 1744 1745static bool 1746is_too_expensive (const char *pass) 1747{ 1748 /* Trying to perform global optimizations on flow graphs which have 1749 a high connectivity will take a long time and is unlikely to be 1750 particularly useful. 1751 1752 In normal circumstances a cfg should have about twice as many 1753 edges as blocks. But we do not want to punish small functions 1754 which have a couple switch statements. Rather than simply 1755 threshold the number of blocks, uses something with a more 1756 graceful degradation. */ 1757 if (n_edges_for_fn (cfun) > 20000 + n_basic_blocks_for_fn (cfun) * 4) 1758 { 1759 warning (OPT_Wdisabled_optimization, 1760 "%s: %d basic blocks and %d edges/basic block", 1761 pass, n_basic_blocks_for_fn (cfun), 1762 n_edges_for_fn (cfun) / n_basic_blocks_for_fn (cfun)); 1763 1764 return true; 1765 } 1766 1767 /* If allocating memory for the cprop bitmap would take up too much 1768 storage it's better just to disable the optimization. */ 1769 if ((n_basic_blocks_for_fn (cfun) 1770 * SBITMAP_SET_SIZE (max_reg_num ()) 1771 * sizeof (SBITMAP_ELT_TYPE)) > MAX_GCSE_MEMORY) 1772 { 1773 warning (OPT_Wdisabled_optimization, 1774 "%s: %d basic blocks and %d registers", 1775 pass, n_basic_blocks_for_fn (cfun), max_reg_num ()); 1776 1777 return true; 1778 } 1779 1780 return false; 1781} 1782 1783/* Main function for the CPROP pass. */ 1784 1785static int 1786one_cprop_pass (void) 1787{ 1788 int i; 1789 int changed = 0; 1790 1791 /* Return if there's nothing to do, or it is too expensive. */ 1792 if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1 1793 || is_too_expensive (_ ("const/copy propagation disabled"))) 1794 return 0; 1795 1796 global_const_prop_count = local_const_prop_count = 0; 1797 global_copy_prop_count = local_copy_prop_count = 0; 1798 1799 bytes_used = 0; 1800 gcc_obstack_init (&cprop_obstack); 1801 1802 /* Do a local const/copy propagation pass first. The global pass 1803 only handles global opportunities. 1804 If the local pass changes something, remove any unreachable blocks 1805 because the CPROP global dataflow analysis may get into infinite 1806 loops for CFGs with unreachable blocks. 1807 1808 FIXME: This local pass should not be necessary after CSE (but for 1809 some reason it still is). It is also (proven) not necessary 1810 to run the local pass right after FWPWOP. 1811 1812 FIXME: The global analysis would not get into infinite loops if it 1813 would use the DF solver (via df_simple_dataflow) instead of 1814 the solver implemented in this file. */ 1815 changed |= local_cprop_pass (); 1816 if (changed) 1817 delete_unreachable_blocks (); 1818 1819 /* Determine implicit sets. This may change the CFG (split critical 1820 edges if that exposes an implicit set). 1821 Note that find_implicit_sets() does not rely on up-to-date DF caches 1822 so that we do not have to re-run df_analyze() even if local CPROP 1823 changed something. 1824 ??? This could run earlier so that any uncovered implicit sets 1825 sets could be exploited in local_cprop_pass() also. Later. */ 1826 changed |= find_implicit_sets (); 1827 1828 /* If local_cprop_pass() or find_implicit_sets() changed something, 1829 run df_analyze() to bring all insn caches up-to-date, and to take 1830 new basic blocks from edge splitting on the DF radar. 1831 NB: This also runs the fast DCE pass, because execute_rtl_cprop 1832 sets DF_LR_RUN_DCE. */ 1833 if (changed) 1834 df_analyze (); 1835 1836 /* Initialize implicit_set_indexes array. */ 1837 implicit_set_indexes = XNEWVEC (int, last_basic_block_for_fn (cfun)); 1838 for (i = 0; i < last_basic_block_for_fn (cfun); i++) 1839 implicit_set_indexes[i] = -1; 1840 1841 alloc_hash_table (&set_hash_table); 1842 compute_hash_table (&set_hash_table); 1843 1844 /* Free implicit_sets before peak usage. */ 1845 free (implicit_sets); 1846 implicit_sets = NULL; 1847 1848 if (dump_file) 1849 dump_hash_table (dump_file, "SET", &set_hash_table); 1850 if (set_hash_table.n_elems > 0) 1851 { 1852 basic_block bb; 1853 rtx_insn *insn; 1854 1855 alloc_cprop_mem (last_basic_block_for_fn (cfun), 1856 set_hash_table.n_elems); 1857 compute_cprop_data (); 1858 1859 free (implicit_set_indexes); 1860 implicit_set_indexes = NULL; 1861 1862 /* Allocate vars to track sets of regs. */ 1863 reg_set_bitmap = ALLOC_REG_SET (NULL); 1864 1865 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb->next_bb, 1866 EXIT_BLOCK_PTR_FOR_FN (cfun), 1867 next_bb) 1868 { 1869 /* Reset tables used to keep track of what's still valid [since 1870 the start of the block]. */ 1871 reset_opr_set_tables (); 1872 1873 FOR_BB_INSNS (bb, insn) 1874 if (INSN_P (insn)) 1875 { 1876 changed |= cprop_insn (insn); 1877 1878 /* Keep track of everything modified by this insn. */ 1879 /* ??? Need to be careful w.r.t. mods done to INSN. 1880 Don't call mark_oprs_set if we turned the 1881 insn into a NOTE, or deleted the insn. */ 1882 if (! NOTE_P (insn) && ! insn->deleted ()) 1883 mark_oprs_set (insn); 1884 } 1885 } 1886 1887 changed |= bypass_conditional_jumps (); 1888 1889 FREE_REG_SET (reg_set_bitmap); 1890 free_cprop_mem (); 1891 } 1892 else 1893 { 1894 free (implicit_set_indexes); 1895 implicit_set_indexes = NULL; 1896 } 1897 1898 free_hash_table (&set_hash_table); 1899 obstack_free (&cprop_obstack, NULL); 1900 1901 if (dump_file) 1902 { 1903 fprintf (dump_file, "CPROP of %s, %d basic blocks, %d bytes needed, ", 1904 current_function_name (), n_basic_blocks_for_fn (cfun), 1905 bytes_used); 1906 fprintf (dump_file, "%d local const props, %d local copy props, ", 1907 local_const_prop_count, local_copy_prop_count); 1908 fprintf (dump_file, "%d global const props, %d global copy props\n\n", 1909 global_const_prop_count, global_copy_prop_count); 1910 } 1911 1912 return changed; 1913} 1914 1915/* All the passes implemented in this file. Each pass has its 1916 own gate and execute function, and at the end of the file a 1917 pass definition for passes.c. 1918 1919 We do not construct an accurate cfg in functions which call 1920 setjmp, so none of these passes runs if the function calls 1921 setjmp. 1922 FIXME: Should just handle setjmp via REG_SETJMP notes. */ 1923 1924static unsigned int 1925execute_rtl_cprop (void) 1926{ 1927 int changed; 1928 delete_unreachable_blocks (); 1929 df_set_flags (DF_LR_RUN_DCE); 1930 df_analyze (); 1931 changed = one_cprop_pass (); 1932 flag_rerun_cse_after_global_opts |= changed; 1933 if (changed) 1934 cleanup_cfg (CLEANUP_CFG_CHANGED); 1935 return 0; 1936} 1937 1938namespace { 1939 1940const pass_data pass_data_rtl_cprop = 1941{ 1942 RTL_PASS, /* type */ 1943 "cprop", /* name */ 1944 OPTGROUP_NONE, /* optinfo_flags */ 1945 TV_CPROP, /* tv_id */ 1946 PROP_cfglayout, /* properties_required */ 1947 0, /* properties_provided */ 1948 0, /* properties_destroyed */ 1949 0, /* todo_flags_start */ 1950 TODO_df_finish, /* todo_flags_finish */ 1951}; 1952 1953class pass_rtl_cprop : public rtl_opt_pass 1954{ 1955public: 1956 pass_rtl_cprop (gcc::context *ctxt) 1957 : rtl_opt_pass (pass_data_rtl_cprop, ctxt) 1958 {} 1959 1960 /* opt_pass methods: */ 1961 opt_pass * clone () { return new pass_rtl_cprop (m_ctxt); } 1962 virtual bool gate (function *fun) 1963 { 1964 return optimize > 0 && flag_gcse 1965 && !fun->calls_setjmp 1966 && dbg_cnt (cprop); 1967 } 1968 1969 virtual unsigned int execute (function *) { return execute_rtl_cprop (); } 1970 1971}; // class pass_rtl_cprop 1972 1973} // anon namespace 1974 1975rtl_opt_pass * 1976make_pass_rtl_cprop (gcc::context *ctxt) 1977{ 1978 return new pass_rtl_cprop (ctxt); 1979} 1980