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