1 /* Global common subexpression elimination/Partial redundancy elimination 2 and global constant/copy propagation for GNU compiler. 3 Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 4 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc. 5 6 This file is part of GCC. 7 8 GCC is free software; you can redistribute it and/or modify it under 9 the terms of the GNU General Public License as published by the Free 10 Software Foundation; either version 3, or (at your option) any later 11 version. 12 13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 14 WARRANTY; without even the implied warranty of MERCHANTABILITY or 15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16 for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with GCC; see the file COPYING3. If not see 20 <http://www.gnu.org/licenses/>. */ 21 22 /* TODO 23 - reordering of memory allocation and freeing to be more space efficient 24 - do rough calc of how many regs are needed in each block, and a rough 25 calc of how many regs are available in each class and use that to 26 throttle back the code in cases where RTX_COST is minimal. 27 - a store to the same address as a load does not kill the load if the 28 source of the store is also the destination of the load. Handling this 29 allows more load motion, particularly out of loops. 30 31 */ 32 33 /* References searched while implementing this. 34 35 Compilers Principles, Techniques and Tools 36 Aho, Sethi, Ullman 37 Addison-Wesley, 1988 38 39 Global Optimization by Suppression of Partial Redundancies 40 E. Morel, C. Renvoise 41 communications of the acm, Vol. 22, Num. 2, Feb. 1979 42 43 A Portable Machine-Independent Global Optimizer - Design and Measurements 44 Frederick Chow 45 Stanford Ph.D. thesis, Dec. 1983 46 47 A Fast Algorithm for Code Movement Optimization 48 D.M. Dhamdhere 49 SIGPLAN Notices, Vol. 23, Num. 10, Oct. 1988 50 51 A Solution to a Problem with Morel and Renvoise's 52 Global Optimization by Suppression of Partial Redundancies 53 K-H Drechsler, M.P. Stadel 54 ACM TOPLAS, Vol. 10, Num. 4, Oct. 1988 55 56 Practical Adaptation of the Global Optimization 57 Algorithm of Morel and Renvoise 58 D.M. Dhamdhere 59 ACM TOPLAS, Vol. 13, Num. 2. Apr. 1991 60 61 Efficiently Computing Static Single Assignment Form and the Control 62 Dependence Graph 63 R. Cytron, J. Ferrante, B.K. Rosen, M.N. Wegman, and F.K. Zadeck 64 ACM TOPLAS, Vol. 13, Num. 4, Oct. 1991 65 66 Lazy Code Motion 67 J. Knoop, O. Ruthing, B. Steffen 68 ACM SIGPLAN Notices Vol. 27, Num. 7, Jul. 1992, '92 Conference on PLDI 69 70 What's In a Region? Or Computing Control Dependence Regions in Near-Linear 71 Time for Reducible Flow Control 72 Thomas Ball 73 ACM Letters on Programming Languages and Systems, 74 Vol. 2, Num. 1-4, Mar-Dec 1993 75 76 An Efficient Representation for Sparse Sets 77 Preston Briggs, Linda Torczon 78 ACM Letters on Programming Languages and Systems, 79 Vol. 2, Num. 1-4, Mar-Dec 1993 80 81 A Variation of Knoop, Ruthing, and Steffen's Lazy Code Motion 82 K-H Drechsler, M.P. Stadel 83 ACM SIGPLAN Notices, Vol. 28, Num. 5, May 1993 84 85 Partial Dead Code Elimination 86 J. Knoop, O. Ruthing, B. Steffen 87 ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994 88 89 Effective Partial Redundancy Elimination 90 P. Briggs, K.D. Cooper 91 ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994 92 93 The Program Structure Tree: Computing Control Regions in Linear Time 94 R. Johnson, D. Pearson, K. Pingali 95 ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994 96 97 Optimal Code Motion: Theory and Practice 98 J. Knoop, O. Ruthing, B. Steffen 99 ACM TOPLAS, Vol. 16, Num. 4, Jul. 1994 100 101 The power of assignment motion 102 J. Knoop, O. Ruthing, B. Steffen 103 ACM SIGPLAN Notices Vol. 30, Num. 6, Jun. 1995, '95 Conference on PLDI 104 105 Global code motion / global value numbering 106 C. Click 107 ACM SIGPLAN Notices Vol. 30, Num. 6, Jun. 1995, '95 Conference on PLDI 108 109 Value Driven Redundancy Elimination 110 L.T. Simpson 111 Rice University Ph.D. thesis, Apr. 1996 112 113 Value Numbering 114 L.T. Simpson 115 Massively Scalar Compiler Project, Rice University, Sep. 1996 116 117 High Performance Compilers for Parallel Computing 118 Michael Wolfe 119 Addison-Wesley, 1996 120 121 Advanced Compiler Design and Implementation 122 Steven Muchnick 123 Morgan Kaufmann, 1997 124 125 Building an Optimizing Compiler 126 Robert Morgan 127 Digital Press, 1998 128 129 People wishing to speed up the code here should read: 130 Elimination Algorithms for Data Flow Analysis 131 B.G. Ryder, M.C. Paull 132 ACM Computing Surveys, Vol. 18, Num. 3, Sep. 1986 133 134 How to Analyze Large Programs Efficiently and Informatively 135 D.M. Dhamdhere, B.K. Rosen, F.K. Zadeck 136 ACM SIGPLAN Notices Vol. 27, Num. 7, Jul. 1992, '92 Conference on PLDI 137 138 People wishing to do something different can find various possibilities 139 in the above papers and elsewhere. 140 */ 141 142 #include "config.h" 143 #include "system.h" 144 #include "coretypes.h" 145 #include "tm.h" 146 #include "toplev.h" 147 148 #include "rtl.h" 149 #include "tree.h" 150 #include "tm_p.h" 151 #include "regs.h" 152 #include "hard-reg-set.h" 153 #include "flags.h" 154 #include "real.h" 155 #include "insn-config.h" 156 #include "recog.h" 157 #include "basic-block.h" 158 #include "output.h" 159 #include "function.h" 160 #include "expr.h" 161 #include "except.h" 162 #include "ggc.h" 163 #include "params.h" 164 #include "cselib.h" 165 #include "intl.h" 166 #include "obstack.h" 167 #include "timevar.h" 168 #include "tree-pass.h" 169 #include "hashtab.h" 170 #include "df.h" 171 #include "dbgcnt.h" 172 #include "target.h" 173 174 /* We support GCSE via Partial Redundancy Elimination. PRE optimizations 175 are a superset of those done by classic GCSE. 176 177 We perform the following steps: 178 179 1) Compute table of places where registers are set. 180 181 2) Perform copy/constant propagation. 182 183 3) Perform global cse using lazy code motion if not optimizing 184 for size, or code hoisting if we are. 185 186 4) Perform another pass of copy/constant propagation. Try to bypass 187 conditional jumps if the condition can be computed from a value of 188 an incoming edge. 189 190 Two passes of copy/constant propagation are done because the first one 191 enables more GCSE and the second one helps to clean up the copies that 192 GCSE creates. This is needed more for PRE than for Classic because Classic 193 GCSE will try to use an existing register containing the common 194 subexpression rather than create a new one. This is harder to do for PRE 195 because of the code motion (which Classic GCSE doesn't do). 196 197 Expressions we are interested in GCSE-ing are of the form 198 (set (pseudo-reg) (expression)). 199 Function want_to_gcse_p says what these are. 200 201 In addition, expressions in REG_EQUAL notes are candidates for GCSE-ing. 202 This allows PRE to hoist expressions that are expressed in multiple insns, 203 such as complex address calculations (e.g. for PIC code, or loads with a 204 high part and a low part). 205 206 PRE handles moving invariant expressions out of loops (by treating them as 207 partially redundant). 208 209 ********************** 210 211 We used to support multiple passes but there are diminishing returns in 212 doing so. The first pass usually makes 90% of the changes that are doable. 213 A second pass can make a few more changes made possible by the first pass. 214 Experiments show any further passes don't make enough changes to justify 215 the expense. 216 217 A study of spec92 using an unlimited number of passes: 218 [1 pass] = 1208 substitutions, [2] = 577, [3] = 202, [4] = 192, [5] = 83, 219 [6] = 34, [7] = 17, [8] = 9, [9] = 4, [10] = 4, [11] = 2, 220 [12] = 2, [13] = 1, [15] = 1, [16] = 2, [41] = 1 221 222 It was found doing copy propagation between each pass enables further 223 substitutions. 224 225 This study was done before expressions in REG_EQUAL notes were added as 226 candidate expressions for optimization, and before the GIMPLE optimizers 227 were added. Probably, multiple passes is even less efficient now than 228 at the time when the study was conducted. 229 230 PRE is quite expensive in complicated functions because the DFA can take 231 a while to converge. Hence we only perform one pass. 232 233 ********************** 234 235 The steps for PRE are: 236 237 1) Build the hash table of expressions we wish to GCSE (expr_hash_table). 238 239 2) Perform the data flow analysis for PRE. 240 241 3) Delete the redundant instructions 242 243 4) Insert the required copies [if any] that make the partially 244 redundant instructions fully redundant. 245 246 5) For other reaching expressions, insert an instruction to copy the value 247 to a newly created pseudo that will reach the redundant instruction. 248 249 The deletion is done first so that when we do insertions we 250 know which pseudo reg to use. 251 252 Various papers have argued that PRE DFA is expensive (O(n^2)) and others 253 argue it is not. The number of iterations for the algorithm to converge 254 is typically 2-4 so I don't view it as that expensive (relatively speaking). 255 256 PRE GCSE depends heavily on the second CPROP pass to clean up the copies 257 we create. To make an expression reach the place where it's redundant, 258 the result of the expression is copied to a new register, and the redundant 259 expression is deleted by replacing it with this new register. Classic GCSE 260 doesn't have this problem as much as it computes the reaching defs of 261 each register in each block and thus can try to use an existing 262 register. */ 263 264 /* GCSE global vars. */ 265 266 /* Set to non-zero if CSE should run after all GCSE optimizations are done. */ 267 int flag_rerun_cse_after_global_opts; 268 269 /* An obstack for our working variables. */ 270 static struct obstack gcse_obstack; 271 272 struct reg_use {rtx reg_rtx; }; 273 274 /* Hash table of expressions. */ 275 276 struct expr 277 { 278 /* The expression (SET_SRC for expressions, PATTERN for assignments). */ 279 rtx expr; 280 /* Index in the available expression bitmaps. */ 281 int bitmap_index; 282 /* Next entry with the same hash. */ 283 struct expr *next_same_hash; 284 /* List of anticipatable occurrences in basic blocks in the function. 285 An "anticipatable occurrence" is one that is the first occurrence in the 286 basic block, the operands are not modified in the basic block prior 287 to the occurrence and the output is not used between the start of 288 the block and the occurrence. */ 289 struct occr *antic_occr; 290 /* List of available occurrence in basic blocks in the function. 291 An "available occurrence" is one that is the last occurrence in the 292 basic block and the operands are not modified by following statements in 293 the basic block [including this insn]. */ 294 struct occr *avail_occr; 295 /* Non-null if the computation is PRE redundant. 296 The value is the newly created pseudo-reg to record a copy of the 297 expression in all the places that reach the redundant copy. */ 298 rtx reaching_reg; 299 }; 300 301 /* Occurrence of an expression. 302 There is one per basic block. If a pattern appears more than once the 303 last appearance is used [or first for anticipatable expressions]. */ 304 305 struct occr 306 { 307 /* Next occurrence of this expression. */ 308 struct occr *next; 309 /* The insn that computes the expression. */ 310 rtx insn; 311 /* Nonzero if this [anticipatable] occurrence has been deleted. */ 312 char deleted_p; 313 /* Nonzero if this [available] occurrence has been copied to 314 reaching_reg. */ 315 /* ??? This is mutually exclusive with deleted_p, so they could share 316 the same byte. */ 317 char copied_p; 318 }; 319 320 /* Expression and copy propagation hash tables. 321 Each hash table is an array of buckets. 322 ??? It is known that if it were an array of entries, structure elements 323 `next_same_hash' and `bitmap_index' wouldn't be necessary. However, it is 324 not clear whether in the final analysis a sufficient amount of memory would 325 be saved as the size of the available expression bitmaps would be larger 326 [one could build a mapping table without holes afterwards though]. 327 Someday I'll perform the computation and figure it out. */ 328 329 struct hash_table_d 330 { 331 /* The table itself. 332 This is an array of `expr_hash_table_size' elements. */ 333 struct expr **table; 334 335 /* Size of the hash table, in elements. */ 336 unsigned int size; 337 338 /* Number of hash table elements. */ 339 unsigned int n_elems; 340 341 /* Whether the table is expression of copy propagation one. */ 342 int set_p; 343 }; 344 345 /* Expression hash table. */ 346 static struct hash_table_d expr_hash_table; 347 348 /* Copy propagation hash table. */ 349 static struct hash_table_d set_hash_table; 350 351 /* This is a list of expressions which are MEMs and will be used by load 352 or store motion. 353 Load motion tracks MEMs which aren't killed by 354 anything except itself. (i.e., loads and stores to a single location). 355 We can then allow movement of these MEM refs with a little special 356 allowance. (all stores copy the same value to the reaching reg used 357 for the loads). This means all values used to store into memory must have 358 no side effects so we can re-issue the setter value. 359 Store Motion uses this structure as an expression table to track stores 360 which look interesting, and might be moveable towards the exit block. */ 361 362 struct ls_expr 363 { 364 struct expr * expr; /* Gcse expression reference for LM. */ 365 rtx pattern; /* Pattern of this mem. */ 366 rtx pattern_regs; /* List of registers mentioned by the mem. */ 367 rtx loads; /* INSN list of loads seen. */ 368 rtx stores; /* INSN list of stores seen. */ 369 struct ls_expr * next; /* Next in the list. */ 370 int invalid; /* Invalid for some reason. */ 371 int index; /* If it maps to a bitmap index. */ 372 unsigned int hash_index; /* Index when in a hash table. */ 373 rtx reaching_reg; /* Register to use when re-writing. */ 374 }; 375 376 /* Array of implicit set patterns indexed by basic block index. */ 377 static rtx *implicit_sets; 378 379 /* Head of the list of load/store memory refs. */ 380 static struct ls_expr * pre_ldst_mems = NULL; 381 382 /* Hashtable for the load/store memory refs. */ 383 static htab_t pre_ldst_table = NULL; 384 385 /* Bitmap containing one bit for each register in the program. 386 Used when performing GCSE to track which registers have been set since 387 the start of the basic block. */ 388 static regset reg_set_bitmap; 389 390 /* Array, indexed by basic block number for a list of insns which modify 391 memory within that block. */ 392 static rtx * modify_mem_list; 393 static bitmap modify_mem_list_set; 394 395 /* This array parallels modify_mem_list, but is kept canonicalized. */ 396 static rtx * canon_modify_mem_list; 397 398 /* Bitmap indexed by block numbers to record which blocks contain 399 function calls. */ 400 static bitmap blocks_with_calls; 401 402 /* Various variables for statistics gathering. */ 403 404 /* Memory used in a pass. 405 This isn't intended to be absolutely precise. Its intent is only 406 to keep an eye on memory usage. */ 407 static int bytes_used; 408 409 /* GCSE substitutions made. */ 410 static int gcse_subst_count; 411 /* Number of copy instructions created. */ 412 static int gcse_create_count; 413 /* Number of local constants propagated. */ 414 static int local_const_prop_count; 415 /* Number of local copies propagated. */ 416 static int local_copy_prop_count; 417 /* Number of global constants propagated. */ 418 static int global_const_prop_count; 419 /* Number of global copies propagated. */ 420 static int global_copy_prop_count; 421 422 /* For available exprs */ 423 static sbitmap *ae_kill; 424 425 static void compute_can_copy (void); 426 static void *gmalloc (size_t) ATTRIBUTE_MALLOC; 427 static void *gcalloc (size_t, size_t) ATTRIBUTE_MALLOC; 428 static void *gcse_alloc (unsigned long); 429 static void alloc_gcse_mem (void); 430 static void free_gcse_mem (void); 431 static void hash_scan_insn (rtx, struct hash_table_d *); 432 static void hash_scan_set (rtx, rtx, struct hash_table_d *); 433 static void hash_scan_clobber (rtx, rtx, struct hash_table_d *); 434 static void hash_scan_call (rtx, rtx, struct hash_table_d *); 435 static int want_to_gcse_p (rtx); 436 static bool gcse_constant_p (const_rtx); 437 static int oprs_unchanged_p (const_rtx, const_rtx, int); 438 static int oprs_anticipatable_p (const_rtx, const_rtx); 439 static int oprs_available_p (const_rtx, const_rtx); 440 static void insert_expr_in_table (rtx, enum machine_mode, rtx, int, int, 441 struct hash_table_d *); 442 static void insert_set_in_table (rtx, rtx, struct hash_table_d *); 443 static unsigned int hash_expr (const_rtx, enum machine_mode, int *, int); 444 static unsigned int hash_set (int, int); 445 static int expr_equiv_p (const_rtx, const_rtx); 446 static void record_last_reg_set_info (rtx, int); 447 static void record_last_mem_set_info (rtx); 448 static void record_last_set_info (rtx, const_rtx, void *); 449 static void compute_hash_table (struct hash_table_d *); 450 static void alloc_hash_table (struct hash_table_d *, int); 451 static void free_hash_table (struct hash_table_d *); 452 static void compute_hash_table_work (struct hash_table_d *); 453 static void dump_hash_table (FILE *, const char *, struct hash_table_d *); 454 static struct expr *lookup_set (unsigned int, struct hash_table_d *); 455 static struct expr *next_set (unsigned int, struct expr *); 456 static void reset_opr_set_tables (void); 457 static int oprs_not_set_p (const_rtx, const_rtx); 458 static void mark_call (rtx); 459 static void mark_set (rtx, rtx); 460 static void mark_clobber (rtx, rtx); 461 static void mark_oprs_set (rtx); 462 static void alloc_cprop_mem (int, int); 463 static void free_cprop_mem (void); 464 static void compute_transp (const_rtx, int, sbitmap *, int); 465 static void compute_transpout (void); 466 static void compute_local_properties (sbitmap *, sbitmap *, sbitmap *, 467 struct hash_table_d *); 468 static void compute_cprop_data (void); 469 static void find_used_regs (rtx *, void *); 470 static int try_replace_reg (rtx, rtx, rtx); 471 static struct expr *find_avail_set (int, rtx); 472 static int cprop_jump (basic_block, rtx, rtx, rtx, rtx); 473 static void mems_conflict_for_gcse_p (rtx, const_rtx, void *); 474 static int load_killed_in_block_p (const_basic_block, int, const_rtx, int); 475 static void canon_list_insert (rtx, const_rtx, void *); 476 static int cprop_insn (rtx); 477 static void find_implicit_sets (void); 478 static int one_cprop_pass (void); 479 static bool constprop_register (rtx, rtx, rtx); 480 static struct expr *find_bypass_set (int, int); 481 static bool reg_killed_on_edge (const_rtx, const_edge); 482 static int bypass_block (basic_block, rtx, rtx); 483 static int bypass_conditional_jumps (void); 484 static void alloc_pre_mem (int, int); 485 static void free_pre_mem (void); 486 static void compute_pre_data (void); 487 static int pre_expr_reaches_here_p (basic_block, struct expr *, 488 basic_block); 489 static void insert_insn_end_basic_block (struct expr *, basic_block, int); 490 static void pre_insert_copy_insn (struct expr *, rtx); 491 static void pre_insert_copies (void); 492 static int pre_delete (void); 493 static int pre_gcse (void); 494 static int one_pre_gcse_pass (void); 495 static void add_label_notes (rtx, rtx); 496 static void alloc_code_hoist_mem (int, int); 497 static void free_code_hoist_mem (void); 498 static void compute_code_hoist_vbeinout (void); 499 static void compute_code_hoist_data (void); 500 static int hoist_expr_reaches_here_p (basic_block, int, basic_block, char *); 501 static int hoist_code (void); 502 static int one_code_hoisting_pass (void); 503 static rtx process_insert_insn (struct expr *); 504 static int pre_edge_insert (struct edge_list *, struct expr **); 505 static int pre_expr_reaches_here_p_work (basic_block, struct expr *, 506 basic_block, char *); 507 static struct ls_expr * ldst_entry (rtx); 508 static void free_ldst_entry (struct ls_expr *); 509 static void free_ldst_mems (void); 510 static void print_ldst_list (FILE *); 511 static struct ls_expr * find_rtx_in_ldst (rtx); 512 static inline struct ls_expr * first_ls_expr (void); 513 static inline struct ls_expr * next_ls_expr (struct ls_expr *); 514 static int simple_mem (const_rtx); 515 static void invalidate_any_buried_refs (rtx); 516 static void compute_ld_motion_mems (void); 517 static void trim_ld_motion_mems (void); 518 static void update_ld_motion_stores (struct expr *); 519 static void free_insn_expr_list_list (rtx *); 520 static void clear_modify_mem_tables (void); 521 static void free_modify_mem_tables (void); 522 static rtx gcse_emit_move_after (rtx, rtx, rtx); 523 static void local_cprop_find_used_regs (rtx *, void *); 524 static bool do_local_cprop (rtx, rtx); 525 static int local_cprop_pass (void); 526 static bool is_too_expensive (const char *); 527 528 #define GNEW(T) ((T *) gmalloc (sizeof (T))) 529 #define GCNEW(T) ((T *) gcalloc (1, sizeof (T))) 530 531 #define GNEWVEC(T, N) ((T *) gmalloc (sizeof (T) * (N))) 532 #define GCNEWVEC(T, N) ((T *) gcalloc ((N), sizeof (T))) 533 534 #define GNEWVAR(T, S) ((T *) gmalloc ((S))) 535 #define GCNEWVAR(T, S) ((T *) gcalloc (1, (S))) 536 537 #define GOBNEW(T) ((T *) gcse_alloc (sizeof (T))) 538 #define GOBNEWVAR(T, S) ((T *) gcse_alloc ((S))) 539 540 /* Misc. utilities. */ 541 542 /* Nonzero for each mode that supports (set (reg) (reg)). 543 This is trivially true for integer and floating point values. 544 It may or may not be true for condition codes. */ 545 static char can_copy[(int) NUM_MACHINE_MODES]; 546 547 /* Compute which modes support reg/reg copy operations. */ 548 549 static void 550 compute_can_copy (void) 551 { 552 int i; 553 #ifndef AVOID_CCMODE_COPIES 554 rtx reg, insn; 555 #endif 556 memset (can_copy, 0, NUM_MACHINE_MODES); 557 558 start_sequence (); 559 for (i = 0; i < NUM_MACHINE_MODES; i++) 560 if (GET_MODE_CLASS (i) == MODE_CC) 561 { 562 #ifdef AVOID_CCMODE_COPIES 563 can_copy[i] = 0; 564 #else 565 reg = gen_rtx_REG ((enum machine_mode) i, LAST_VIRTUAL_REGISTER + 1); 566 insn = emit_insn (gen_rtx_SET (VOIDmode, reg, reg)); 567 if (recog (PATTERN (insn), insn, NULL) >= 0) 568 can_copy[i] = 1; 569 #endif 570 } 571 else 572 can_copy[i] = 1; 573 574 end_sequence (); 575 } 576 577 /* Returns whether the mode supports reg/reg copy operations. */ 578 579 bool 580 can_copy_p (enum machine_mode mode) 581 { 582 static bool can_copy_init_p = false; 583 584 if (! can_copy_init_p) 585 { 586 compute_can_copy (); 587 can_copy_init_p = true; 588 } 589 590 return can_copy[mode] != 0; 591 } 592 593 594 /* Cover function to xmalloc to record bytes allocated. */ 595 596 static void * 597 gmalloc (size_t size) 598 { 599 bytes_used += size; 600 return xmalloc (size); 601 } 602 603 /* Cover function to xcalloc to record bytes allocated. */ 604 605 static void * 606 gcalloc (size_t nelem, size_t elsize) 607 { 608 bytes_used += nelem * elsize; 609 return xcalloc (nelem, elsize); 610 } 611 612 /* Cover function to obstack_alloc. */ 613 614 static void * 615 gcse_alloc (unsigned long size) 616 { 617 bytes_used += size; 618 return obstack_alloc (&gcse_obstack, size); 619 } 620 621 /* Allocate memory for the reg/memory set tracking tables. 622 This is called at the start of each pass. */ 623 624 static void 625 alloc_gcse_mem (void) 626 { 627 /* Allocate vars to track sets of regs. */ 628 reg_set_bitmap = BITMAP_ALLOC (NULL); 629 630 /* Allocate array to keep a list of insns which modify memory in each 631 basic block. */ 632 modify_mem_list = GCNEWVEC (rtx, last_basic_block); 633 canon_modify_mem_list = GCNEWVEC (rtx, last_basic_block); 634 modify_mem_list_set = BITMAP_ALLOC (NULL); 635 blocks_with_calls = BITMAP_ALLOC (NULL); 636 } 637 638 /* Free memory allocated by alloc_gcse_mem. */ 639 640 static void 641 free_gcse_mem (void) 642 { 643 free_modify_mem_tables (); 644 BITMAP_FREE (modify_mem_list_set); 645 BITMAP_FREE (blocks_with_calls); 646 } 647 648 /* Compute the local properties of each recorded expression. 649 650 Local properties are those that are defined by the block, irrespective of 651 other blocks. 652 653 An expression is transparent in a block if its operands are not modified 654 in the block. 655 656 An expression is computed (locally available) in a block if it is computed 657 at least once and expression would contain the same value if the 658 computation was moved to the end of the block. 659 660 An expression is locally anticipatable in a block if it is computed at 661 least once and expression would contain the same value if the computation 662 was moved to the beginning of the block. 663 664 We call this routine for cprop, pre and code hoisting. They all compute 665 basically the same information and thus can easily share this code. 666 667 TRANSP, COMP, and ANTLOC are destination sbitmaps for recording local 668 properties. If NULL, then it is not necessary to compute or record that 669 particular property. 670 671 TABLE controls which hash table to look at. If it is set hash table, 672 additionally, TRANSP is computed as ~TRANSP, since this is really cprop's 673 ABSALTERED. */ 674 675 static void 676 compute_local_properties (sbitmap *transp, sbitmap *comp, sbitmap *antloc, 677 struct hash_table_d *table) 678 { 679 unsigned int i; 680 681 /* Initialize any bitmaps that were passed in. */ 682 if (transp) 683 { 684 if (table->set_p) 685 sbitmap_vector_zero (transp, last_basic_block); 686 else 687 sbitmap_vector_ones (transp, last_basic_block); 688 } 689 690 if (comp) 691 sbitmap_vector_zero (comp, last_basic_block); 692 if (antloc) 693 sbitmap_vector_zero (antloc, last_basic_block); 694 695 for (i = 0; i < table->size; i++) 696 { 697 struct expr *expr; 698 699 for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash) 700 { 701 int indx = expr->bitmap_index; 702 struct occr *occr; 703 704 /* The expression is transparent in this block if it is not killed. 705 We start by assuming all are transparent [none are killed], and 706 then reset the bits for those that are. */ 707 if (transp) 708 compute_transp (expr->expr, indx, transp, table->set_p); 709 710 /* The occurrences recorded in antic_occr are exactly those that 711 we want to set to nonzero in ANTLOC. */ 712 if (antloc) 713 for (occr = expr->antic_occr; occr != NULL; occr = occr->next) 714 { 715 SET_BIT (antloc[BLOCK_FOR_INSN (occr->insn)->index], indx); 716 717 /* While we're scanning the table, this is a good place to 718 initialize this. */ 719 occr->deleted_p = 0; 720 } 721 722 /* The occurrences recorded in avail_occr are exactly those that 723 we want to set to nonzero in COMP. */ 724 if (comp) 725 for (occr = expr->avail_occr; occr != NULL; occr = occr->next) 726 { 727 SET_BIT (comp[BLOCK_FOR_INSN (occr->insn)->index], indx); 728 729 /* While we're scanning the table, this is a good place to 730 initialize this. */ 731 occr->copied_p = 0; 732 } 733 734 /* While we're scanning the table, this is a good place to 735 initialize this. */ 736 expr->reaching_reg = 0; 737 } 738 } 739 } 740 741 /* Hash table support. */ 742 743 struct reg_avail_info 744 { 745 basic_block last_bb; 746 int first_set; 747 int last_set; 748 }; 749 750 static struct reg_avail_info *reg_avail_info; 751 static basic_block current_bb; 752 753 754 /* See whether X, the source of a set, is something we want to consider for 755 GCSE. */ 756 757 static int 758 want_to_gcse_p (rtx x) 759 { 760 #ifdef STACK_REGS 761 /* On register stack architectures, don't GCSE constants from the 762 constant pool, as the benefits are often swamped by the overhead 763 of shuffling the register stack between basic blocks. */ 764 if (IS_STACK_MODE (GET_MODE (x))) 765 x = avoid_constant_pool_reference (x); 766 #endif 767 768 switch (GET_CODE (x)) 769 { 770 case REG: 771 case SUBREG: 772 case CONST_INT: 773 case CONST_DOUBLE: 774 case CONST_FIXED: 775 case CONST_VECTOR: 776 case CALL: 777 return 0; 778 779 default: 780 return can_assign_to_reg_without_clobbers_p (x); 781 } 782 } 783 784 /* Used internally by can_assign_to_reg_without_clobbers_p. */ 785 786 static GTY(()) rtx test_insn; 787 788 /* Return true if we can assign X to a pseudo register such that the 789 resulting insn does not result in clobbering a hard register as a 790 side-effect. 791 792 Additionally, if the target requires it, check that the resulting insn 793 can be copied. If it cannot, this means that X is special and probably 794 has hidden side-effects we don't want to mess with. 795 796 This function is typically used by code motion passes, to verify 797 that it is safe to insert an insn without worrying about clobbering 798 maybe live hard regs. */ 799 800 bool 801 can_assign_to_reg_without_clobbers_p (rtx x) 802 { 803 int num_clobbers = 0; 804 int icode; 805 806 /* If this is a valid operand, we are OK. If it's VOIDmode, we aren't. */ 807 if (general_operand (x, GET_MODE (x))) 808 return 1; 809 else if (GET_MODE (x) == VOIDmode) 810 return 0; 811 812 /* Otherwise, check if we can make a valid insn from it. First initialize 813 our test insn if we haven't already. */ 814 if (test_insn == 0) 815 { 816 test_insn 817 = make_insn_raw (gen_rtx_SET (VOIDmode, 818 gen_rtx_REG (word_mode, 819 FIRST_PSEUDO_REGISTER * 2), 820 const0_rtx)); 821 NEXT_INSN (test_insn) = PREV_INSN (test_insn) = 0; 822 } 823 824 /* Now make an insn like the one we would make when GCSE'ing and see if 825 valid. */ 826 PUT_MODE (SET_DEST (PATTERN (test_insn)), GET_MODE (x)); 827 SET_SRC (PATTERN (test_insn)) = x; 828 829 icode = recog (PATTERN (test_insn), test_insn, &num_clobbers); 830 if (icode < 0) 831 return false; 832 833 if (num_clobbers > 0 && added_clobbers_hard_reg_p (icode)) 834 return false; 835 836 if (targetm.cannot_copy_insn_p && targetm.cannot_copy_insn_p (test_insn)) 837 return false; 838 839 return true; 840 } 841 842 /* Return nonzero if the operands of expression X are unchanged from the 843 start of INSN's basic block up to but not including INSN (if AVAIL_P == 0), 844 or from INSN to the end of INSN's basic block (if AVAIL_P != 0). */ 845 846 static int 847 oprs_unchanged_p (const_rtx x, const_rtx insn, int avail_p) 848 { 849 int i, j; 850 enum rtx_code code; 851 const char *fmt; 852 853 if (x == 0) 854 return 1; 855 856 code = GET_CODE (x); 857 switch (code) 858 { 859 case REG: 860 { 861 struct reg_avail_info *info = ®_avail_info[REGNO (x)]; 862 863 if (info->last_bb != current_bb) 864 return 1; 865 if (avail_p) 866 return info->last_set < DF_INSN_LUID (insn); 867 else 868 return info->first_set >= DF_INSN_LUID (insn); 869 } 870 871 case MEM: 872 if (load_killed_in_block_p (current_bb, DF_INSN_LUID (insn), 873 x, avail_p)) 874 return 0; 875 else 876 return oprs_unchanged_p (XEXP (x, 0), insn, avail_p); 877 878 case PRE_DEC: 879 case PRE_INC: 880 case POST_DEC: 881 case POST_INC: 882 case PRE_MODIFY: 883 case POST_MODIFY: 884 return 0; 885 886 case PC: 887 case CC0: /*FIXME*/ 888 case CONST: 889 case CONST_INT: 890 case CONST_DOUBLE: 891 case CONST_FIXED: 892 case CONST_VECTOR: 893 case SYMBOL_REF: 894 case LABEL_REF: 895 case ADDR_VEC: 896 case ADDR_DIFF_VEC: 897 return 1; 898 899 default: 900 break; 901 } 902 903 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--) 904 { 905 if (fmt[i] == 'e') 906 { 907 /* If we are about to do the last recursive call needed at this 908 level, change it into iteration. This function is called enough 909 to be worth it. */ 910 if (i == 0) 911 return oprs_unchanged_p (XEXP (x, i), insn, avail_p); 912 913 else if (! oprs_unchanged_p (XEXP (x, i), insn, avail_p)) 914 return 0; 915 } 916 else if (fmt[i] == 'E') 917 for (j = 0; j < XVECLEN (x, i); j++) 918 if (! oprs_unchanged_p (XVECEXP (x, i, j), insn, avail_p)) 919 return 0; 920 } 921 922 return 1; 923 } 924 925 /* Used for communication between mems_conflict_for_gcse_p and 926 load_killed_in_block_p. Nonzero if mems_conflict_for_gcse_p finds a 927 conflict between two memory references. */ 928 static int gcse_mems_conflict_p; 929 930 /* Used for communication between mems_conflict_for_gcse_p and 931 load_killed_in_block_p. A memory reference for a load instruction, 932 mems_conflict_for_gcse_p will see if a memory store conflicts with 933 this memory load. */ 934 static const_rtx gcse_mem_operand; 935 936 /* DEST is the output of an instruction. If it is a memory reference, and 937 possibly conflicts with the load found in gcse_mem_operand, then set 938 gcse_mems_conflict_p to a nonzero value. */ 939 940 static void 941 mems_conflict_for_gcse_p (rtx dest, const_rtx setter ATTRIBUTE_UNUSED, 942 void *data ATTRIBUTE_UNUSED) 943 { 944 while (GET_CODE (dest) == SUBREG 945 || GET_CODE (dest) == ZERO_EXTRACT 946 || GET_CODE (dest) == STRICT_LOW_PART) 947 dest = XEXP (dest, 0); 948 949 /* If DEST is not a MEM, then it will not conflict with the load. Note 950 that function calls are assumed to clobber memory, but are handled 951 elsewhere. */ 952 if (! MEM_P (dest)) 953 return; 954 955 /* If we are setting a MEM in our list of specially recognized MEMs, 956 don't mark as killed this time. */ 957 958 if (expr_equiv_p (dest, gcse_mem_operand) && pre_ldst_mems != NULL) 959 { 960 if (!find_rtx_in_ldst (dest)) 961 gcse_mems_conflict_p = 1; 962 return; 963 } 964 965 if (true_dependence (dest, GET_MODE (dest), gcse_mem_operand, 966 rtx_addr_varies_p)) 967 gcse_mems_conflict_p = 1; 968 } 969 970 /* Return nonzero if the expression in X (a memory reference) is killed 971 in block BB before or after the insn with the LUID in UID_LIMIT. 972 AVAIL_P is nonzero for kills after UID_LIMIT, and zero for kills 973 before UID_LIMIT. 974 975 To check the entire block, set UID_LIMIT to max_uid + 1 and 976 AVAIL_P to 0. */ 977 978 static int 979 load_killed_in_block_p (const_basic_block bb, int uid_limit, const_rtx x, int avail_p) 980 { 981 rtx list_entry = modify_mem_list[bb->index]; 982 983 /* If this is a readonly then we aren't going to be changing it. */ 984 if (MEM_READONLY_P (x)) 985 return 0; 986 987 while (list_entry) 988 { 989 rtx setter; 990 /* Ignore entries in the list that do not apply. */ 991 if ((avail_p 992 && DF_INSN_LUID (XEXP (list_entry, 0)) < uid_limit) 993 || (! avail_p 994 && DF_INSN_LUID (XEXP (list_entry, 0)) > uid_limit)) 995 { 996 list_entry = XEXP (list_entry, 1); 997 continue; 998 } 999 1000 setter = XEXP (list_entry, 0); 1001 1002 /* If SETTER is a call everything is clobbered. Note that calls 1003 to pure functions are never put on the list, so we need not 1004 worry about them. */ 1005 if (CALL_P (setter)) 1006 return 1; 1007 1008 /* SETTER must be an INSN of some kind that sets memory. Call 1009 note_stores to examine each hunk of memory that is modified. 1010 1011 The note_stores interface is pretty limited, so we have to 1012 communicate via global variables. Yuk. */ 1013 gcse_mem_operand = x; 1014 gcse_mems_conflict_p = 0; 1015 note_stores (PATTERN (setter), mems_conflict_for_gcse_p, NULL); 1016 if (gcse_mems_conflict_p) 1017 return 1; 1018 list_entry = XEXP (list_entry, 1); 1019 } 1020 return 0; 1021 } 1022 1023 /* Return nonzero if the operands of expression X are unchanged from 1024 the start of INSN's basic block up to but not including INSN. */ 1025 1026 static int 1027 oprs_anticipatable_p (const_rtx x, const_rtx insn) 1028 { 1029 return oprs_unchanged_p (x, insn, 0); 1030 } 1031 1032 /* Return nonzero if the operands of expression X are unchanged from 1033 INSN to the end of INSN's basic block. */ 1034 1035 static int 1036 oprs_available_p (const_rtx x, const_rtx insn) 1037 { 1038 return oprs_unchanged_p (x, insn, 1); 1039 } 1040 1041 /* Hash expression X. 1042 1043 MODE is only used if X is a CONST_INT. DO_NOT_RECORD_P is a boolean 1044 indicating if a volatile operand is found or if the expression contains 1045 something we don't want to insert in the table. HASH_TABLE_SIZE is 1046 the current size of the hash table to be probed. */ 1047 1048 static unsigned int 1049 hash_expr (const_rtx x, enum machine_mode mode, int *do_not_record_p, 1050 int hash_table_size) 1051 { 1052 unsigned int hash; 1053 1054 *do_not_record_p = 0; 1055 1056 hash = hash_rtx (x, mode, do_not_record_p, 1057 NULL, /*have_reg_qty=*/false); 1058 return hash % hash_table_size; 1059 } 1060 1061 /* Hash a set of register REGNO. 1062 1063 Sets are hashed on the register that is set. This simplifies the PRE copy 1064 propagation code. 1065 1066 ??? May need to make things more elaborate. Later, as necessary. */ 1067 1068 static unsigned int 1069 hash_set (int regno, int hash_table_size) 1070 { 1071 unsigned int hash; 1072 1073 hash = regno; 1074 return hash % hash_table_size; 1075 } 1076 1077 /* Return nonzero if exp1 is equivalent to exp2. */ 1078 1079 static int 1080 expr_equiv_p (const_rtx x, const_rtx y) 1081 { 1082 return exp_equiv_p (x, y, 0, true); 1083 } 1084 1085 /* Insert expression X in INSN in the hash TABLE. 1086 If it is already present, record it as the last occurrence in INSN's 1087 basic block. 1088 1089 MODE is the mode of the value X is being stored into. 1090 It is only used if X is a CONST_INT. 1091 1092 ANTIC_P is nonzero if X is an anticipatable expression. 1093 AVAIL_P is nonzero if X is an available expression. */ 1094 1095 static void 1096 insert_expr_in_table (rtx x, enum machine_mode mode, rtx insn, int antic_p, 1097 int avail_p, struct hash_table_d *table) 1098 { 1099 int found, do_not_record_p; 1100 unsigned int hash; 1101 struct expr *cur_expr, *last_expr = NULL; 1102 struct occr *antic_occr, *avail_occr; 1103 1104 hash = hash_expr (x, mode, &do_not_record_p, table->size); 1105 1106 /* Do not insert expression in table if it contains volatile operands, 1107 or if hash_expr determines the expression is something we don't want 1108 to or can't handle. */ 1109 if (do_not_record_p) 1110 return; 1111 1112 cur_expr = table->table[hash]; 1113 found = 0; 1114 1115 while (cur_expr && 0 == (found = expr_equiv_p (cur_expr->expr, x))) 1116 { 1117 /* If the expression isn't found, save a pointer to the end of 1118 the list. */ 1119 last_expr = cur_expr; 1120 cur_expr = cur_expr->next_same_hash; 1121 } 1122 1123 if (! found) 1124 { 1125 cur_expr = GOBNEW (struct expr); 1126 bytes_used += sizeof (struct expr); 1127 if (table->table[hash] == NULL) 1128 /* This is the first pattern that hashed to this index. */ 1129 table->table[hash] = cur_expr; 1130 else 1131 /* Add EXPR to end of this hash chain. */ 1132 last_expr->next_same_hash = cur_expr; 1133 1134 /* Set the fields of the expr element. */ 1135 cur_expr->expr = x; 1136 cur_expr->bitmap_index = table->n_elems++; 1137 cur_expr->next_same_hash = NULL; 1138 cur_expr->antic_occr = NULL; 1139 cur_expr->avail_occr = NULL; 1140 } 1141 1142 /* Now record the occurrence(s). */ 1143 if (antic_p) 1144 { 1145 antic_occr = cur_expr->antic_occr; 1146 1147 if (antic_occr 1148 && BLOCK_FOR_INSN (antic_occr->insn) != BLOCK_FOR_INSN (insn)) 1149 antic_occr = NULL; 1150 1151 if (antic_occr) 1152 /* Found another instance of the expression in the same basic block. 1153 Prefer the currently recorded one. We want the first one in the 1154 block and the block is scanned from start to end. */ 1155 ; /* nothing to do */ 1156 else 1157 { 1158 /* First occurrence of this expression in this basic block. */ 1159 antic_occr = GOBNEW (struct occr); 1160 bytes_used += sizeof (struct occr); 1161 antic_occr->insn = insn; 1162 antic_occr->next = cur_expr->antic_occr; 1163 antic_occr->deleted_p = 0; 1164 cur_expr->antic_occr = antic_occr; 1165 } 1166 } 1167 1168 if (avail_p) 1169 { 1170 avail_occr = cur_expr->avail_occr; 1171 1172 if (avail_occr 1173 && BLOCK_FOR_INSN (avail_occr->insn) == BLOCK_FOR_INSN (insn)) 1174 { 1175 /* Found another instance of the expression in the same basic block. 1176 Prefer this occurrence to the currently recorded one. We want 1177 the last one in the block and the block is scanned from start 1178 to end. */ 1179 avail_occr->insn = insn; 1180 } 1181 else 1182 { 1183 /* First occurrence of this expression in this basic block. */ 1184 avail_occr = GOBNEW (struct occr); 1185 bytes_used += sizeof (struct occr); 1186 avail_occr->insn = insn; 1187 avail_occr->next = cur_expr->avail_occr; 1188 avail_occr->deleted_p = 0; 1189 cur_expr->avail_occr = avail_occr; 1190 } 1191 } 1192 } 1193 1194 /* Insert pattern X in INSN in the hash table. 1195 X is a SET of a reg to either another reg or a constant. 1196 If it is already present, record it as the last occurrence in INSN's 1197 basic block. */ 1198 1199 static void 1200 insert_set_in_table (rtx x, rtx insn, struct hash_table_d *table) 1201 { 1202 int found; 1203 unsigned int hash; 1204 struct expr *cur_expr, *last_expr = NULL; 1205 struct occr *cur_occr; 1206 1207 gcc_assert (GET_CODE (x) == SET && REG_P (SET_DEST (x))); 1208 1209 hash = hash_set (REGNO (SET_DEST (x)), table->size); 1210 1211 cur_expr = table->table[hash]; 1212 found = 0; 1213 1214 while (cur_expr && 0 == (found = expr_equiv_p (cur_expr->expr, x))) 1215 { 1216 /* If the expression isn't found, save a pointer to the end of 1217 the list. */ 1218 last_expr = cur_expr; 1219 cur_expr = cur_expr->next_same_hash; 1220 } 1221 1222 if (! found) 1223 { 1224 cur_expr = GOBNEW (struct expr); 1225 bytes_used += sizeof (struct expr); 1226 if (table->table[hash] == NULL) 1227 /* This is the first pattern that hashed to this index. */ 1228 table->table[hash] = cur_expr; 1229 else 1230 /* Add EXPR to end of this hash chain. */ 1231 last_expr->next_same_hash = cur_expr; 1232 1233 /* Set the fields of the expr element. 1234 We must copy X because it can be modified when copy propagation is 1235 performed on its operands. */ 1236 cur_expr->expr = copy_rtx (x); 1237 cur_expr->bitmap_index = table->n_elems++; 1238 cur_expr->next_same_hash = NULL; 1239 cur_expr->antic_occr = NULL; 1240 cur_expr->avail_occr = NULL; 1241 } 1242 1243 /* Now record the occurrence. */ 1244 cur_occr = cur_expr->avail_occr; 1245 1246 if (cur_occr 1247 && BLOCK_FOR_INSN (cur_occr->insn) == BLOCK_FOR_INSN (insn)) 1248 { 1249 /* Found another instance of the expression in the same basic block. 1250 Prefer this occurrence to the currently recorded one. We want 1251 the last one in the block and the block is scanned from start 1252 to end. */ 1253 cur_occr->insn = insn; 1254 } 1255 else 1256 { 1257 /* First occurrence of this expression in this basic block. */ 1258 cur_occr = GOBNEW (struct occr); 1259 bytes_used += sizeof (struct occr); 1260 cur_occr->insn = insn; 1261 cur_occr->next = cur_expr->avail_occr; 1262 cur_occr->deleted_p = 0; 1263 cur_expr->avail_occr = cur_occr; 1264 } 1265 } 1266 1267 /* Determine whether the rtx X should be treated as a constant for 1268 the purposes of GCSE's constant propagation. */ 1269 1270 static bool 1271 gcse_constant_p (const_rtx x) 1272 { 1273 /* Consider a COMPARE of two integers constant. */ 1274 if (GET_CODE (x) == COMPARE 1275 && CONST_INT_P (XEXP (x, 0)) 1276 && CONST_INT_P (XEXP (x, 1))) 1277 return true; 1278 1279 /* Consider a COMPARE of the same registers is a constant 1280 if they are not floating point registers. */ 1281 if (GET_CODE(x) == COMPARE 1282 && REG_P (XEXP (x, 0)) && REG_P (XEXP (x, 1)) 1283 && REGNO (XEXP (x, 0)) == REGNO (XEXP (x, 1)) 1284 && ! FLOAT_MODE_P (GET_MODE (XEXP (x, 0))) 1285 && ! FLOAT_MODE_P (GET_MODE (XEXP (x, 1)))) 1286 return true; 1287 1288 /* Since X might be inserted more than once we have to take care that it 1289 is sharable. */ 1290 return CONSTANT_P (x) && (GET_CODE (x) != CONST || shared_const_p (x)); 1291 } 1292 1293 /* Scan pattern PAT of INSN and add an entry to the hash TABLE (set or 1294 expression one). */ 1295 1296 static void 1297 hash_scan_set (rtx pat, rtx insn, struct hash_table_d *table) 1298 { 1299 rtx src = SET_SRC (pat); 1300 rtx dest = SET_DEST (pat); 1301 rtx note; 1302 1303 if (GET_CODE (src) == CALL) 1304 hash_scan_call (src, insn, table); 1305 1306 else if (REG_P (dest)) 1307 { 1308 unsigned int regno = REGNO (dest); 1309 rtx tmp; 1310 1311 /* See if a REG_EQUAL note shows this equivalent to a simpler expression. 1312 1313 This allows us to do a single GCSE pass and still eliminate 1314 redundant constants, addresses or other expressions that are 1315 constructed with multiple instructions. 1316 1317 However, keep the original SRC if INSN is a simple reg-reg move. In 1318 In this case, there will almost always be a REG_EQUAL note on the 1319 insn that sets SRC. By recording the REG_EQUAL value here as SRC 1320 for INSN, we miss copy propagation opportunities and we perform the 1321 same PRE GCSE operation repeatedly on the same REG_EQUAL value if we 1322 do more than one PRE GCSE pass. 1323 1324 Note that this does not impede profitable constant propagations. We 1325 "look through" reg-reg sets in lookup_avail_set. */ 1326 note = find_reg_equal_equiv_note (insn); 1327 if (note != 0 1328 && REG_NOTE_KIND (note) == REG_EQUAL 1329 && !REG_P (src) 1330 && (table->set_p 1331 ? gcse_constant_p (XEXP (note, 0)) 1332 : want_to_gcse_p (XEXP (note, 0)))) 1333 src = XEXP (note, 0), pat = gen_rtx_SET (VOIDmode, dest, src); 1334 1335 /* Only record sets of pseudo-regs in the hash table. */ 1336 if (! table->set_p 1337 && regno >= FIRST_PSEUDO_REGISTER 1338 /* Don't GCSE something if we can't do a reg/reg copy. */ 1339 && can_copy_p (GET_MODE (dest)) 1340 /* GCSE commonly inserts instruction after the insn. We can't 1341 do that easily for EH edges so disable GCSE on these for now. */ 1342 /* ??? We can now easily create new EH landing pads at the 1343 gimple level, for splitting edges; there's no reason we 1344 can't do the same thing at the rtl level. */ 1345 && !can_throw_internal (insn) 1346 /* Is SET_SRC something we want to gcse? */ 1347 && want_to_gcse_p (src) 1348 /* Don't CSE a nop. */ 1349 && ! set_noop_p (pat) 1350 /* Don't GCSE if it has attached REG_EQUIV note. 1351 At this point this only function parameters should have 1352 REG_EQUIV notes and if the argument slot is used somewhere 1353 explicitly, it means address of parameter has been taken, 1354 so we should not extend the lifetime of the pseudo. */ 1355 && (note == NULL_RTX || ! MEM_P (XEXP (note, 0)))) 1356 { 1357 /* An expression is not anticipatable if its operands are 1358 modified before this insn or if this is not the only SET in 1359 this insn. The latter condition does not have to mean that 1360 SRC itself is not anticipatable, but we just will not be 1361 able to handle code motion of insns with multiple sets. */ 1362 int antic_p = oprs_anticipatable_p (src, insn) 1363 && !multiple_sets (insn); 1364 /* An expression is not available if its operands are 1365 subsequently modified, including this insn. It's also not 1366 available if this is a branch, because we can't insert 1367 a set after the branch. */ 1368 int avail_p = (oprs_available_p (src, insn) 1369 && ! JUMP_P (insn)); 1370 1371 insert_expr_in_table (src, GET_MODE (dest), insn, antic_p, avail_p, table); 1372 } 1373 1374 /* Record sets for constant/copy propagation. */ 1375 else if (table->set_p 1376 && regno >= FIRST_PSEUDO_REGISTER 1377 && ((REG_P (src) 1378 && REGNO (src) >= FIRST_PSEUDO_REGISTER 1379 && can_copy_p (GET_MODE (dest)) 1380 && REGNO (src) != regno) 1381 || gcse_constant_p (src)) 1382 /* A copy is not available if its src or dest is subsequently 1383 modified. Here we want to search from INSN+1 on, but 1384 oprs_available_p searches from INSN on. */ 1385 && (insn == BB_END (BLOCK_FOR_INSN (insn)) 1386 || (tmp = next_nonnote_nondebug_insn (insn)) == NULL_RTX 1387 || BLOCK_FOR_INSN (tmp) != BLOCK_FOR_INSN (insn) 1388 || oprs_available_p (pat, tmp))) 1389 insert_set_in_table (pat, insn, table); 1390 } 1391 /* In case of store we want to consider the memory value as available in 1392 the REG stored in that memory. This makes it possible to remove 1393 redundant loads from due to stores to the same location. */ 1394 else if (flag_gcse_las && REG_P (src) && MEM_P (dest)) 1395 { 1396 unsigned int regno = REGNO (src); 1397 1398 /* Do not do this for constant/copy propagation. */ 1399 if (! table->set_p 1400 /* Only record sets of pseudo-regs in the hash table. */ 1401 && regno >= FIRST_PSEUDO_REGISTER 1402 /* Don't GCSE something if we can't do a reg/reg copy. */ 1403 && can_copy_p (GET_MODE (src)) 1404 /* GCSE commonly inserts instruction after the insn. We can't 1405 do that easily for EH edges so disable GCSE on these for now. */ 1406 && !can_throw_internal (insn) 1407 /* Is SET_DEST something we want to gcse? */ 1408 && want_to_gcse_p (dest) 1409 /* Don't CSE a nop. */ 1410 && ! set_noop_p (pat) 1411 /* Don't GCSE if it has attached REG_EQUIV note. 1412 At this point this only function parameters should have 1413 REG_EQUIV notes and if the argument slot is used somewhere 1414 explicitly, it means address of parameter has been taken, 1415 so we should not extend the lifetime of the pseudo. */ 1416 && ((note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) == 0 1417 || ! MEM_P (XEXP (note, 0)))) 1418 { 1419 /* Stores are never anticipatable. */ 1420 int antic_p = 0; 1421 /* An expression is not available if its operands are 1422 subsequently modified, including this insn. It's also not 1423 available if this is a branch, because we can't insert 1424 a set after the branch. */ 1425 int avail_p = oprs_available_p (dest, insn) 1426 && ! JUMP_P (insn); 1427 1428 /* Record the memory expression (DEST) in the hash table. */ 1429 insert_expr_in_table (dest, GET_MODE (dest), insn, 1430 antic_p, avail_p, table); 1431 } 1432 } 1433 } 1434 1435 static void 1436 hash_scan_clobber (rtx x ATTRIBUTE_UNUSED, rtx insn ATTRIBUTE_UNUSED, 1437 struct hash_table_d *table ATTRIBUTE_UNUSED) 1438 { 1439 /* Currently nothing to do. */ 1440 } 1441 1442 static void 1443 hash_scan_call (rtx x ATTRIBUTE_UNUSED, rtx insn ATTRIBUTE_UNUSED, 1444 struct hash_table_d *table ATTRIBUTE_UNUSED) 1445 { 1446 /* Currently nothing to do. */ 1447 } 1448 1449 /* Process INSN and add hash table entries as appropriate. 1450 1451 Only available expressions that set a single pseudo-reg are recorded. 1452 1453 Single sets in a PARALLEL could be handled, but it's an extra complication 1454 that isn't dealt with right now. The trick is handling the CLOBBERs that 1455 are also in the PARALLEL. Later. 1456 1457 If SET_P is nonzero, this is for the assignment hash table, 1458 otherwise it is for the expression hash table. */ 1459 1460 static void 1461 hash_scan_insn (rtx insn, struct hash_table_d *table) 1462 { 1463 rtx pat = PATTERN (insn); 1464 int i; 1465 1466 /* Pick out the sets of INSN and for other forms of instructions record 1467 what's been modified. */ 1468 1469 if (GET_CODE (pat) == SET) 1470 hash_scan_set (pat, insn, table); 1471 else if (GET_CODE (pat) == PARALLEL) 1472 for (i = 0; i < XVECLEN (pat, 0); i++) 1473 { 1474 rtx x = XVECEXP (pat, 0, i); 1475 1476 if (GET_CODE (x) == SET) 1477 hash_scan_set (x, insn, table); 1478 else if (GET_CODE (x) == CLOBBER) 1479 hash_scan_clobber (x, insn, table); 1480 else if (GET_CODE (x) == CALL) 1481 hash_scan_call (x, insn, table); 1482 } 1483 1484 else if (GET_CODE (pat) == CLOBBER) 1485 hash_scan_clobber (pat, insn, table); 1486 else if (GET_CODE (pat) == CALL) 1487 hash_scan_call (pat, insn, table); 1488 } 1489 1490 static void 1491 dump_hash_table (FILE *file, const char *name, struct hash_table_d *table) 1492 { 1493 int i; 1494 /* Flattened out table, so it's printed in proper order. */ 1495 struct expr **flat_table; 1496 unsigned int *hash_val; 1497 struct expr *expr; 1498 1499 flat_table = XCNEWVEC (struct expr *, table->n_elems); 1500 hash_val = XNEWVEC (unsigned int, table->n_elems); 1501 1502 for (i = 0; i < (int) table->size; i++) 1503 for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash) 1504 { 1505 flat_table[expr->bitmap_index] = expr; 1506 hash_val[expr->bitmap_index] = i; 1507 } 1508 1509 fprintf (file, "%s hash table (%d buckets, %d entries)\n", 1510 name, table->size, table->n_elems); 1511 1512 for (i = 0; i < (int) table->n_elems; i++) 1513 if (flat_table[i] != 0) 1514 { 1515 expr = flat_table[i]; 1516 fprintf (file, "Index %d (hash value %d)\n ", 1517 expr->bitmap_index, hash_val[i]); 1518 print_rtl (file, expr->expr); 1519 fprintf (file, "\n"); 1520 } 1521 1522 fprintf (file, "\n"); 1523 1524 free (flat_table); 1525 free (hash_val); 1526 } 1527 1528 /* Record register first/last/block set information for REGNO in INSN. 1529 1530 first_set records the first place in the block where the register 1531 is set and is used to compute "anticipatability". 1532 1533 last_set records the last place in the block where the register 1534 is set and is used to compute "availability". 1535 1536 last_bb records the block for which first_set and last_set are 1537 valid, as a quick test to invalidate them. */ 1538 1539 static void 1540 record_last_reg_set_info (rtx insn, int regno) 1541 { 1542 struct reg_avail_info *info = ®_avail_info[regno]; 1543 int luid = DF_INSN_LUID (insn); 1544 1545 info->last_set = luid; 1546 if (info->last_bb != current_bb) 1547 { 1548 info->last_bb = current_bb; 1549 info->first_set = luid; 1550 } 1551 } 1552 1553 1554 /* Record all of the canonicalized MEMs of record_last_mem_set_info's insn. 1555 Note we store a pair of elements in the list, so they have to be 1556 taken off pairwise. */ 1557 1558 static void 1559 canon_list_insert (rtx dest ATTRIBUTE_UNUSED, const_rtx unused1 ATTRIBUTE_UNUSED, 1560 void * v_insn) 1561 { 1562 rtx dest_addr, insn; 1563 int bb; 1564 1565 while (GET_CODE (dest) == SUBREG 1566 || GET_CODE (dest) == ZERO_EXTRACT 1567 || GET_CODE (dest) == STRICT_LOW_PART) 1568 dest = XEXP (dest, 0); 1569 1570 /* If DEST is not a MEM, then it will not conflict with a load. Note 1571 that function calls are assumed to clobber memory, but are handled 1572 elsewhere. */ 1573 1574 if (! MEM_P (dest)) 1575 return; 1576 1577 dest_addr = get_addr (XEXP (dest, 0)); 1578 dest_addr = canon_rtx (dest_addr); 1579 insn = (rtx) v_insn; 1580 bb = BLOCK_FOR_INSN (insn)->index; 1581 1582 canon_modify_mem_list[bb] = 1583 alloc_EXPR_LIST (VOIDmode, dest_addr, canon_modify_mem_list[bb]); 1584 canon_modify_mem_list[bb] = 1585 alloc_EXPR_LIST (VOIDmode, dest, canon_modify_mem_list[bb]); 1586 } 1587 1588 /* Record memory modification information for INSN. We do not actually care 1589 about the memory location(s) that are set, or even how they are set (consider 1590 a CALL_INSN). We merely need to record which insns modify memory. */ 1591 1592 static void 1593 record_last_mem_set_info (rtx insn) 1594 { 1595 int bb = BLOCK_FOR_INSN (insn)->index; 1596 1597 /* load_killed_in_block_p will handle the case of calls clobbering 1598 everything. */ 1599 modify_mem_list[bb] = alloc_INSN_LIST (insn, modify_mem_list[bb]); 1600 bitmap_set_bit (modify_mem_list_set, bb); 1601 1602 if (CALL_P (insn)) 1603 { 1604 /* Note that traversals of this loop (other than for free-ing) 1605 will break after encountering a CALL_INSN. So, there's no 1606 need to insert a pair of items, as canon_list_insert does. */ 1607 canon_modify_mem_list[bb] = 1608 alloc_INSN_LIST (insn, canon_modify_mem_list[bb]); 1609 bitmap_set_bit (blocks_with_calls, bb); 1610 } 1611 else 1612 note_stores (PATTERN (insn), canon_list_insert, (void*) insn); 1613 } 1614 1615 /* Called from compute_hash_table via note_stores to handle one 1616 SET or CLOBBER in an insn. DATA is really the instruction in which 1617 the SET is taking place. */ 1618 1619 static void 1620 record_last_set_info (rtx dest, const_rtx setter ATTRIBUTE_UNUSED, void *data) 1621 { 1622 rtx last_set_insn = (rtx) data; 1623 1624 if (GET_CODE (dest) == SUBREG) 1625 dest = SUBREG_REG (dest); 1626 1627 if (REG_P (dest)) 1628 record_last_reg_set_info (last_set_insn, REGNO (dest)); 1629 else if (MEM_P (dest) 1630 /* Ignore pushes, they clobber nothing. */ 1631 && ! push_operand (dest, GET_MODE (dest))) 1632 record_last_mem_set_info (last_set_insn); 1633 } 1634 1635 /* Top level function to create an expression or assignment hash table. 1636 1637 Expression entries are placed in the hash table if 1638 - they are of the form (set (pseudo-reg) src), 1639 - src is something we want to perform GCSE on, 1640 - none of the operands are subsequently modified in the block 1641 1642 Assignment entries are placed in the hash table if 1643 - they are of the form (set (pseudo-reg) src), 1644 - src is something we want to perform const/copy propagation on, 1645 - none of the operands or target are subsequently modified in the block 1646 1647 Currently src must be a pseudo-reg or a const_int. 1648 1649 TABLE is the table computed. */ 1650 1651 static void 1652 compute_hash_table_work (struct hash_table_d *table) 1653 { 1654 int i; 1655 1656 /* re-Cache any INSN_LIST nodes we have allocated. */ 1657 clear_modify_mem_tables (); 1658 /* Some working arrays used to track first and last set in each block. */ 1659 reg_avail_info = GNEWVEC (struct reg_avail_info, max_reg_num ()); 1660 1661 for (i = 0; i < max_reg_num (); ++i) 1662 reg_avail_info[i].last_bb = NULL; 1663 1664 FOR_EACH_BB (current_bb) 1665 { 1666 rtx insn; 1667 unsigned int regno; 1668 1669 /* First pass over the instructions records information used to 1670 determine when registers and memory are first and last set. */ 1671 FOR_BB_INSNS (current_bb, insn) 1672 { 1673 if (!NONDEBUG_INSN_P (insn)) 1674 continue; 1675 1676 if (CALL_P (insn)) 1677 { 1678 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++) 1679 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno)) 1680 record_last_reg_set_info (insn, regno); 1681 1682 mark_call (insn); 1683 } 1684 1685 note_stores (PATTERN (insn), record_last_set_info, insn); 1686 } 1687 1688 /* Insert implicit sets in the hash table. */ 1689 if (table->set_p 1690 && implicit_sets[current_bb->index] != NULL_RTX) 1691 hash_scan_set (implicit_sets[current_bb->index], 1692 BB_HEAD (current_bb), table); 1693 1694 /* The next pass builds the hash table. */ 1695 FOR_BB_INSNS (current_bb, insn) 1696 if (NONDEBUG_INSN_P (insn)) 1697 hash_scan_insn (insn, table); 1698 } 1699 1700 free (reg_avail_info); 1701 reg_avail_info = NULL; 1702 } 1703 1704 /* Allocate space for the set/expr hash TABLE. 1705 It is used to determine the number of buckets to use. 1706 SET_P determines whether set or expression table will 1707 be created. */ 1708 1709 static void 1710 alloc_hash_table (struct hash_table_d *table, int set_p) 1711 { 1712 int n; 1713 1714 n = get_max_insn_count (); 1715 1716 table->size = n / 4; 1717 if (table->size < 11) 1718 table->size = 11; 1719 1720 /* Attempt to maintain efficient use of hash table. 1721 Making it an odd number is simplest for now. 1722 ??? Later take some measurements. */ 1723 table->size |= 1; 1724 n = table->size * sizeof (struct expr *); 1725 table->table = GNEWVAR (struct expr *, n); 1726 table->set_p = set_p; 1727 } 1728 1729 /* Free things allocated by alloc_hash_table. */ 1730 1731 static void 1732 free_hash_table (struct hash_table_d *table) 1733 { 1734 free (table->table); 1735 } 1736 1737 /* Compute the hash TABLE for doing copy/const propagation or 1738 expression hash table. */ 1739 1740 static void 1741 compute_hash_table (struct hash_table_d *table) 1742 { 1743 /* Initialize count of number of entries in hash table. */ 1744 table->n_elems = 0; 1745 memset (table->table, 0, table->size * sizeof (struct expr *)); 1746 1747 compute_hash_table_work (table); 1748 } 1749 1750 /* Expression tracking support. */ 1751 1752 /* Lookup REGNO in the set TABLE. The result is a pointer to the 1753 table entry, or NULL if not found. */ 1754 1755 static struct expr * 1756 lookup_set (unsigned int regno, struct hash_table_d *table) 1757 { 1758 unsigned int hash = hash_set (regno, table->size); 1759 struct expr *expr; 1760 1761 expr = table->table[hash]; 1762 1763 while (expr && REGNO (SET_DEST (expr->expr)) != regno) 1764 expr = expr->next_same_hash; 1765 1766 return expr; 1767 } 1768 1769 /* Return the next entry for REGNO in list EXPR. */ 1770 1771 static struct expr * 1772 next_set (unsigned int regno, struct expr *expr) 1773 { 1774 do 1775 expr = expr->next_same_hash; 1776 while (expr && REGNO (SET_DEST (expr->expr)) != regno); 1777 1778 return expr; 1779 } 1780 1781 /* Like free_INSN_LIST_list or free_EXPR_LIST_list, except that the node 1782 types may be mixed. */ 1783 1784 static void 1785 free_insn_expr_list_list (rtx *listp) 1786 { 1787 rtx list, next; 1788 1789 for (list = *listp; list ; list = next) 1790 { 1791 next = XEXP (list, 1); 1792 if (GET_CODE (list) == EXPR_LIST) 1793 free_EXPR_LIST_node (list); 1794 else 1795 free_INSN_LIST_node (list); 1796 } 1797 1798 *listp = NULL; 1799 } 1800 1801 /* Clear canon_modify_mem_list and modify_mem_list tables. */ 1802 static void 1803 clear_modify_mem_tables (void) 1804 { 1805 unsigned i; 1806 bitmap_iterator bi; 1807 1808 EXECUTE_IF_SET_IN_BITMAP (modify_mem_list_set, 0, i, bi) 1809 { 1810 free_INSN_LIST_list (modify_mem_list + i); 1811 free_insn_expr_list_list (canon_modify_mem_list + i); 1812 } 1813 bitmap_clear (modify_mem_list_set); 1814 bitmap_clear (blocks_with_calls); 1815 } 1816 1817 /* Release memory used by modify_mem_list_set. */ 1818 1819 static void 1820 free_modify_mem_tables (void) 1821 { 1822 clear_modify_mem_tables (); 1823 free (modify_mem_list); 1824 free (canon_modify_mem_list); 1825 modify_mem_list = 0; 1826 canon_modify_mem_list = 0; 1827 } 1828 1829 /* Reset tables used to keep track of what's still available [since the 1830 start of the block]. */ 1831 1832 static void 1833 reset_opr_set_tables (void) 1834 { 1835 /* Maintain a bitmap of which regs have been set since beginning of 1836 the block. */ 1837 CLEAR_REG_SET (reg_set_bitmap); 1838 1839 /* Also keep a record of the last instruction to modify memory. 1840 For now this is very trivial, we only record whether any memory 1841 location has been modified. */ 1842 clear_modify_mem_tables (); 1843 } 1844 1845 /* Return nonzero if the operands of X are not set before INSN in 1846 INSN's basic block. */ 1847 1848 static int 1849 oprs_not_set_p (const_rtx x, const_rtx insn) 1850 { 1851 int i, j; 1852 enum rtx_code code; 1853 const char *fmt; 1854 1855 if (x == 0) 1856 return 1; 1857 1858 code = GET_CODE (x); 1859 switch (code) 1860 { 1861 case PC: 1862 case CC0: 1863 case CONST: 1864 case CONST_INT: 1865 case CONST_DOUBLE: 1866 case CONST_FIXED: 1867 case CONST_VECTOR: 1868 case SYMBOL_REF: 1869 case LABEL_REF: 1870 case ADDR_VEC: 1871 case ADDR_DIFF_VEC: 1872 return 1; 1873 1874 case MEM: 1875 if (load_killed_in_block_p (BLOCK_FOR_INSN (insn), 1876 DF_INSN_LUID (insn), x, 0)) 1877 return 0; 1878 else 1879 return oprs_not_set_p (XEXP (x, 0), insn); 1880 1881 case REG: 1882 return ! REGNO_REG_SET_P (reg_set_bitmap, REGNO (x)); 1883 1884 default: 1885 break; 1886 } 1887 1888 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--) 1889 { 1890 if (fmt[i] == 'e') 1891 { 1892 /* If we are about to do the last recursive call 1893 needed at this level, change it into iteration. 1894 This function is called enough to be worth it. */ 1895 if (i == 0) 1896 return oprs_not_set_p (XEXP (x, i), insn); 1897 1898 if (! oprs_not_set_p (XEXP (x, i), insn)) 1899 return 0; 1900 } 1901 else if (fmt[i] == 'E') 1902 for (j = 0; j < XVECLEN (x, i); j++) 1903 if (! oprs_not_set_p (XVECEXP (x, i, j), insn)) 1904 return 0; 1905 } 1906 1907 return 1; 1908 } 1909 1910 /* Mark things set by a CALL. */ 1911 1912 static void 1913 mark_call (rtx insn) 1914 { 1915 if (! RTL_CONST_OR_PURE_CALL_P (insn)) 1916 record_last_mem_set_info (insn); 1917 } 1918 1919 /* Mark things set by a SET. */ 1920 1921 static void 1922 mark_set (rtx pat, rtx insn) 1923 { 1924 rtx dest = SET_DEST (pat); 1925 1926 while (GET_CODE (dest) == SUBREG 1927 || GET_CODE (dest) == ZERO_EXTRACT 1928 || GET_CODE (dest) == STRICT_LOW_PART) 1929 dest = XEXP (dest, 0); 1930 1931 if (REG_P (dest)) 1932 SET_REGNO_REG_SET (reg_set_bitmap, REGNO (dest)); 1933 else if (MEM_P (dest)) 1934 record_last_mem_set_info (insn); 1935 1936 if (GET_CODE (SET_SRC (pat)) == CALL) 1937 mark_call (insn); 1938 } 1939 1940 /* Record things set by a CLOBBER. */ 1941 1942 static void 1943 mark_clobber (rtx pat, rtx insn) 1944 { 1945 rtx clob = XEXP (pat, 0); 1946 1947 while (GET_CODE (clob) == SUBREG || GET_CODE (clob) == STRICT_LOW_PART) 1948 clob = XEXP (clob, 0); 1949 1950 if (REG_P (clob)) 1951 SET_REGNO_REG_SET (reg_set_bitmap, REGNO (clob)); 1952 else 1953 record_last_mem_set_info (insn); 1954 } 1955 1956 /* Record things set by INSN. 1957 This data is used by oprs_not_set_p. */ 1958 1959 static void 1960 mark_oprs_set (rtx insn) 1961 { 1962 rtx pat = PATTERN (insn); 1963 int i; 1964 1965 if (GET_CODE (pat) == SET) 1966 mark_set (pat, insn); 1967 else if (GET_CODE (pat) == PARALLEL) 1968 for (i = 0; i < XVECLEN (pat, 0); i++) 1969 { 1970 rtx x = XVECEXP (pat, 0, i); 1971 1972 if (GET_CODE (x) == SET) 1973 mark_set (x, insn); 1974 else if (GET_CODE (x) == CLOBBER) 1975 mark_clobber (x, insn); 1976 else if (GET_CODE (x) == CALL) 1977 mark_call (insn); 1978 } 1979 1980 else if (GET_CODE (pat) == CLOBBER) 1981 mark_clobber (pat, insn); 1982 else if (GET_CODE (pat) == CALL) 1983 mark_call (insn); 1984 } 1985 1986 1987 /* Compute copy/constant propagation working variables. */ 1988 1989 /* Local properties of assignments. */ 1990 static sbitmap *cprop_pavloc; 1991 static sbitmap *cprop_absaltered; 1992 1993 /* Global properties of assignments (computed from the local properties). */ 1994 static sbitmap *cprop_avin; 1995 static sbitmap *cprop_avout; 1996 1997 /* Allocate vars used for copy/const propagation. N_BLOCKS is the number of 1998 basic blocks. N_SETS is the number of sets. */ 1999 2000 static void 2001 alloc_cprop_mem (int n_blocks, int n_sets) 2002 { 2003 cprop_pavloc = sbitmap_vector_alloc (n_blocks, n_sets); 2004 cprop_absaltered = sbitmap_vector_alloc (n_blocks, n_sets); 2005 2006 cprop_avin = sbitmap_vector_alloc (n_blocks, n_sets); 2007 cprop_avout = sbitmap_vector_alloc (n_blocks, n_sets); 2008 } 2009 2010 /* Free vars used by copy/const propagation. */ 2011 2012 static void 2013 free_cprop_mem (void) 2014 { 2015 sbitmap_vector_free (cprop_pavloc); 2016 sbitmap_vector_free (cprop_absaltered); 2017 sbitmap_vector_free (cprop_avin); 2018 sbitmap_vector_free (cprop_avout); 2019 } 2020 2021 /* For each block, compute whether X is transparent. X is either an 2022 expression or an assignment [though we don't care which, for this context 2023 an assignment is treated as an expression]. For each block where an 2024 element of X is modified, set (SET_P == 1) or reset (SET_P == 0) the INDX 2025 bit in BMAP. */ 2026 2027 static void 2028 compute_transp (const_rtx x, int indx, sbitmap *bmap, int set_p) 2029 { 2030 int i, j; 2031 enum rtx_code code; 2032 const char *fmt; 2033 2034 /* repeat is used to turn tail-recursion into iteration since GCC 2035 can't do it when there's no return value. */ 2036 repeat: 2037 2038 if (x == 0) 2039 return; 2040 2041 code = GET_CODE (x); 2042 switch (code) 2043 { 2044 case REG: 2045 if (set_p) 2046 { 2047 df_ref def; 2048 for (def = DF_REG_DEF_CHAIN (REGNO (x)); 2049 def; 2050 def = DF_REF_NEXT_REG (def)) 2051 SET_BIT (bmap[DF_REF_BB (def)->index], indx); 2052 } 2053 else 2054 { 2055 df_ref def; 2056 for (def = DF_REG_DEF_CHAIN (REGNO (x)); 2057 def; 2058 def = DF_REF_NEXT_REG (def)) 2059 RESET_BIT (bmap[DF_REF_BB (def)->index], indx); 2060 } 2061 2062 return; 2063 2064 case MEM: 2065 if (! MEM_READONLY_P (x)) 2066 { 2067 bitmap_iterator bi; 2068 unsigned bb_index; 2069 2070 /* First handle all the blocks with calls. We don't need to 2071 do any list walking for them. */ 2072 EXECUTE_IF_SET_IN_BITMAP (blocks_with_calls, 0, bb_index, bi) 2073 { 2074 if (set_p) 2075 SET_BIT (bmap[bb_index], indx); 2076 else 2077 RESET_BIT (bmap[bb_index], indx); 2078 } 2079 2080 /* Now iterate over the blocks which have memory modifications 2081 but which do not have any calls. */ 2082 EXECUTE_IF_AND_COMPL_IN_BITMAP (modify_mem_list_set, 2083 blocks_with_calls, 2084 0, bb_index, bi) 2085 { 2086 rtx list_entry = canon_modify_mem_list[bb_index]; 2087 2088 while (list_entry) 2089 { 2090 rtx dest, dest_addr; 2091 2092 /* LIST_ENTRY must be an INSN of some kind that sets memory. 2093 Examine each hunk of memory that is modified. */ 2094 2095 dest = XEXP (list_entry, 0); 2096 list_entry = XEXP (list_entry, 1); 2097 dest_addr = XEXP (list_entry, 0); 2098 2099 if (canon_true_dependence (dest, GET_MODE (dest), dest_addr, 2100 x, NULL_RTX, rtx_addr_varies_p)) 2101 { 2102 if (set_p) 2103 SET_BIT (bmap[bb_index], indx); 2104 else 2105 RESET_BIT (bmap[bb_index], indx); 2106 break; 2107 } 2108 list_entry = XEXP (list_entry, 1); 2109 } 2110 } 2111 } 2112 2113 x = XEXP (x, 0); 2114 goto repeat; 2115 2116 case PC: 2117 case CC0: /*FIXME*/ 2118 case CONST: 2119 case CONST_INT: 2120 case CONST_DOUBLE: 2121 case CONST_FIXED: 2122 case CONST_VECTOR: 2123 case SYMBOL_REF: 2124 case LABEL_REF: 2125 case ADDR_VEC: 2126 case ADDR_DIFF_VEC: 2127 return; 2128 2129 default: 2130 break; 2131 } 2132 2133 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--) 2134 { 2135 if (fmt[i] == 'e') 2136 { 2137 /* If we are about to do the last recursive call 2138 needed at this level, change it into iteration. 2139 This function is called enough to be worth it. */ 2140 if (i == 0) 2141 { 2142 x = XEXP (x, i); 2143 goto repeat; 2144 } 2145 2146 compute_transp (XEXP (x, i), indx, bmap, set_p); 2147 } 2148 else if (fmt[i] == 'E') 2149 for (j = 0; j < XVECLEN (x, i); j++) 2150 compute_transp (XVECEXP (x, i, j), indx, bmap, set_p); 2151 } 2152 } 2153 2154 /* Top level routine to do the dataflow analysis needed by copy/const 2155 propagation. */ 2156 2157 static void 2158 compute_cprop_data (void) 2159 { 2160 compute_local_properties (cprop_absaltered, cprop_pavloc, NULL, &set_hash_table); 2161 compute_available (cprop_pavloc, cprop_absaltered, 2162 cprop_avout, cprop_avin); 2163 } 2164 2165 /* Copy/constant propagation. */ 2166 2167 /* Maximum number of register uses in an insn that we handle. */ 2168 #define MAX_USES 8 2169 2170 /* Table of uses found in an insn. 2171 Allocated statically to avoid alloc/free complexity and overhead. */ 2172 static struct reg_use reg_use_table[MAX_USES]; 2173 2174 /* Index into `reg_use_table' while building it. */ 2175 static int reg_use_count; 2176 2177 /* Set up a list of register numbers used in INSN. The found uses are stored 2178 in `reg_use_table'. `reg_use_count' is initialized to zero before entry, 2179 and contains the number of uses in the table upon exit. 2180 2181 ??? If a register appears multiple times we will record it multiple times. 2182 This doesn't hurt anything but it will slow things down. */ 2183 2184 static void 2185 find_used_regs (rtx *xptr, void *data ATTRIBUTE_UNUSED) 2186 { 2187 int i, j; 2188 enum rtx_code code; 2189 const char *fmt; 2190 rtx x = *xptr; 2191 2192 /* repeat is used to turn tail-recursion into iteration since GCC 2193 can't do it when there's no return value. */ 2194 repeat: 2195 if (x == 0) 2196 return; 2197 2198 code = GET_CODE (x); 2199 if (REG_P (x)) 2200 { 2201 if (reg_use_count == MAX_USES) 2202 return; 2203 2204 reg_use_table[reg_use_count].reg_rtx = x; 2205 reg_use_count++; 2206 } 2207 2208 /* Recursively scan the operands of this expression. */ 2209 2210 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--) 2211 { 2212 if (fmt[i] == 'e') 2213 { 2214 /* If we are about to do the last recursive call 2215 needed at this level, change it into iteration. 2216 This function is called enough to be worth it. */ 2217 if (i == 0) 2218 { 2219 x = XEXP (x, 0); 2220 goto repeat; 2221 } 2222 2223 find_used_regs (&XEXP (x, i), data); 2224 } 2225 else if (fmt[i] == 'E') 2226 for (j = 0; j < XVECLEN (x, i); j++) 2227 find_used_regs (&XVECEXP (x, i, j), data); 2228 } 2229 } 2230 2231 /* Try to replace all non-SET_DEST occurrences of FROM in INSN with TO. 2232 Returns nonzero is successful. */ 2233 2234 static int 2235 try_replace_reg (rtx from, rtx to, rtx insn) 2236 { 2237 rtx note = find_reg_equal_equiv_note (insn); 2238 rtx src = 0; 2239 int success = 0; 2240 rtx set = single_set (insn); 2241 2242 /* Usually we substitute easy stuff, so we won't copy everything. 2243 We however need to take care to not duplicate non-trivial CONST 2244 expressions. */ 2245 to = copy_rtx (to); 2246 2247 validate_replace_src_group (from, to, insn); 2248 if (num_changes_pending () && apply_change_group ()) 2249 success = 1; 2250 2251 /* Try to simplify SET_SRC if we have substituted a constant. */ 2252 if (success && set && CONSTANT_P (to)) 2253 { 2254 src = simplify_rtx (SET_SRC (set)); 2255 2256 if (src) 2257 validate_change (insn, &SET_SRC (set), src, 0); 2258 } 2259 2260 /* If there is already a REG_EQUAL note, update the expression in it 2261 with our replacement. */ 2262 if (note != 0 && REG_NOTE_KIND (note) == REG_EQUAL) 2263 set_unique_reg_note (insn, REG_EQUAL, 2264 simplify_replace_rtx (XEXP (note, 0), from, to)); 2265 if (!success && set && reg_mentioned_p (from, SET_SRC (set))) 2266 { 2267 /* If above failed and this is a single set, try to simplify the source of 2268 the set given our substitution. We could perhaps try this for multiple 2269 SETs, but it probably won't buy us anything. */ 2270 src = simplify_replace_rtx (SET_SRC (set), from, to); 2271 2272 if (!rtx_equal_p (src, SET_SRC (set)) 2273 && validate_change (insn, &SET_SRC (set), src, 0)) 2274 success = 1; 2275 2276 /* If we've failed to do replacement, have a single SET, don't already 2277 have a note, and have no special SET, add a REG_EQUAL note to not 2278 lose information. */ 2279 if (!success && note == 0 && set != 0 2280 && GET_CODE (SET_DEST (set)) != ZERO_EXTRACT 2281 && GET_CODE (SET_DEST (set)) != STRICT_LOW_PART) 2282 note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src)); 2283 } 2284 2285 /* REG_EQUAL may get simplified into register. 2286 We don't allow that. Remove that note. This code ought 2287 not to happen, because previous code ought to synthesize 2288 reg-reg move, but be on the safe side. */ 2289 if (note && REG_NOTE_KIND (note) == REG_EQUAL && REG_P (XEXP (note, 0))) 2290 remove_note (insn, note); 2291 2292 return success; 2293 } 2294 2295 /* Find a set of REGNOs that are available on entry to INSN's block. Returns 2296 NULL no such set is found. */ 2297 2298 static struct expr * 2299 find_avail_set (int regno, rtx insn) 2300 { 2301 /* SET1 contains the last set found that can be returned to the caller for 2302 use in a substitution. */ 2303 struct expr *set1 = 0; 2304 2305 /* Loops are not possible here. To get a loop we would need two sets 2306 available at the start of the block containing INSN. i.e. we would 2307 need two sets like this available at the start of the block: 2308 2309 (set (reg X) (reg Y)) 2310 (set (reg Y) (reg X)) 2311 2312 This can not happen since the set of (reg Y) would have killed the 2313 set of (reg X) making it unavailable at the start of this block. */ 2314 while (1) 2315 { 2316 rtx src; 2317 struct expr *set = lookup_set (regno, &set_hash_table); 2318 2319 /* Find a set that is available at the start of the block 2320 which contains INSN. */ 2321 while (set) 2322 { 2323 if (TEST_BIT (cprop_avin[BLOCK_FOR_INSN (insn)->index], 2324 set->bitmap_index)) 2325 break; 2326 set = next_set (regno, set); 2327 } 2328 2329 /* If no available set was found we've reached the end of the 2330 (possibly empty) copy chain. */ 2331 if (set == 0) 2332 break; 2333 2334 gcc_assert (GET_CODE (set->expr) == SET); 2335 2336 src = SET_SRC (set->expr); 2337 2338 /* We know the set is available. 2339 Now check that SRC is ANTLOC (i.e. none of the source operands 2340 have changed since the start of the block). 2341 2342 If the source operand changed, we may still use it for the next 2343 iteration of this loop, but we may not use it for substitutions. */ 2344 2345 if (gcse_constant_p (src) || oprs_not_set_p (src, insn)) 2346 set1 = set; 2347 2348 /* If the source of the set is anything except a register, then 2349 we have reached the end of the copy chain. */ 2350 if (! REG_P (src)) 2351 break; 2352 2353 /* Follow the copy chain, i.e. start another iteration of the loop 2354 and see if we have an available copy into SRC. */ 2355 regno = REGNO (src); 2356 } 2357 2358 /* SET1 holds the last set that was available and anticipatable at 2359 INSN. */ 2360 return set1; 2361 } 2362 2363 /* Subroutine of cprop_insn that tries to propagate constants into 2364 JUMP_INSNS. JUMP must be a conditional jump. If SETCC is non-NULL 2365 it is the instruction that immediately precedes JUMP, and must be a 2366 single SET of a register. FROM is what we will try to replace, 2367 SRC is the constant we will try to substitute for it. Returns nonzero 2368 if a change was made. */ 2369 2370 static int 2371 cprop_jump (basic_block bb, rtx setcc, rtx jump, rtx from, rtx src) 2372 { 2373 rtx new_rtx, set_src, note_src; 2374 rtx set = pc_set (jump); 2375 rtx note = find_reg_equal_equiv_note (jump); 2376 2377 if (note) 2378 { 2379 note_src = XEXP (note, 0); 2380 if (GET_CODE (note_src) == EXPR_LIST) 2381 note_src = NULL_RTX; 2382 } 2383 else note_src = NULL_RTX; 2384 2385 /* Prefer REG_EQUAL notes except those containing EXPR_LISTs. */ 2386 set_src = note_src ? note_src : SET_SRC (set); 2387 2388 /* First substitute the SETCC condition into the JUMP instruction, 2389 then substitute that given values into this expanded JUMP. */ 2390 if (setcc != NULL_RTX 2391 && !modified_between_p (from, setcc, jump) 2392 && !modified_between_p (src, setcc, jump)) 2393 { 2394 rtx setcc_src; 2395 rtx setcc_set = single_set (setcc); 2396 rtx setcc_note = find_reg_equal_equiv_note (setcc); 2397 setcc_src = (setcc_note && GET_CODE (XEXP (setcc_note, 0)) != EXPR_LIST) 2398 ? XEXP (setcc_note, 0) : SET_SRC (setcc_set); 2399 set_src = simplify_replace_rtx (set_src, SET_DEST (setcc_set), 2400 setcc_src); 2401 } 2402 else 2403 setcc = NULL_RTX; 2404 2405 new_rtx = simplify_replace_rtx (set_src, from, src); 2406 2407 /* If no simplification can be made, then try the next register. */ 2408 if (rtx_equal_p (new_rtx, SET_SRC (set))) 2409 return 0; 2410 2411 /* If this is now a no-op delete it, otherwise this must be a valid insn. */ 2412 if (new_rtx == pc_rtx) 2413 delete_insn (jump); 2414 else 2415 { 2416 /* Ensure the value computed inside the jump insn to be equivalent 2417 to one computed by setcc. */ 2418 if (setcc && modified_in_p (new_rtx, setcc)) 2419 return 0; 2420 if (! validate_unshare_change (jump, &SET_SRC (set), new_rtx, 0)) 2421 { 2422 /* When (some) constants are not valid in a comparison, and there 2423 are two registers to be replaced by constants before the entire 2424 comparison can be folded into a constant, we need to keep 2425 intermediate information in REG_EQUAL notes. For targets with 2426 separate compare insns, such notes are added by try_replace_reg. 2427 When we have a combined compare-and-branch instruction, however, 2428 we need to attach a note to the branch itself to make this 2429 optimization work. */ 2430 2431 if (!rtx_equal_p (new_rtx, note_src)) 2432 set_unique_reg_note (jump, REG_EQUAL, copy_rtx (new_rtx)); 2433 return 0; 2434 } 2435 2436 /* Remove REG_EQUAL note after simplification. */ 2437 if (note_src) 2438 remove_note (jump, note); 2439 } 2440 2441 #ifdef HAVE_cc0 2442 /* Delete the cc0 setter. */ 2443 if (setcc != NULL && CC0_P (SET_DEST (single_set (setcc)))) 2444 delete_insn (setcc); 2445 #endif 2446 2447 global_const_prop_count++; 2448 if (dump_file != NULL) 2449 { 2450 fprintf (dump_file, 2451 "GLOBAL CONST-PROP: Replacing reg %d in jump_insn %d with constant ", 2452 REGNO (from), INSN_UID (jump)); 2453 print_rtl (dump_file, src); 2454 fprintf (dump_file, "\n"); 2455 } 2456 purge_dead_edges (bb); 2457 2458 /* If a conditional jump has been changed into unconditional jump, remove 2459 the jump and make the edge fallthru - this is always called in 2460 cfglayout mode. */ 2461 if (new_rtx != pc_rtx && simplejump_p (jump)) 2462 { 2463 edge e; 2464 edge_iterator ei; 2465 2466 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ei_next (&ei)) 2467 if (e->dest != EXIT_BLOCK_PTR 2468 && BB_HEAD (e->dest) == JUMP_LABEL (jump)) 2469 { 2470 e->flags |= EDGE_FALLTHRU; 2471 break; 2472 } 2473 delete_insn (jump); 2474 } 2475 2476 return 1; 2477 } 2478 2479 static bool 2480 constprop_register (rtx insn, rtx from, rtx to) 2481 { 2482 rtx sset; 2483 2484 /* Check for reg or cc0 setting instructions followed by 2485 conditional branch instructions first. */ 2486 if ((sset = single_set (insn)) != NULL 2487 && NEXT_INSN (insn) 2488 && any_condjump_p (NEXT_INSN (insn)) && onlyjump_p (NEXT_INSN (insn))) 2489 { 2490 rtx dest = SET_DEST (sset); 2491 if ((REG_P (dest) || CC0_P (dest)) 2492 && cprop_jump (BLOCK_FOR_INSN (insn), insn, NEXT_INSN (insn), from, to)) 2493 return 1; 2494 } 2495 2496 /* Handle normal insns next. */ 2497 if (NONJUMP_INSN_P (insn) 2498 && try_replace_reg (from, to, insn)) 2499 return 1; 2500 2501 /* Try to propagate a CONST_INT into a conditional jump. 2502 We're pretty specific about what we will handle in this 2503 code, we can extend this as necessary over time. 2504 2505 Right now the insn in question must look like 2506 (set (pc) (if_then_else ...)) */ 2507 else if (any_condjump_p (insn) && onlyjump_p (insn)) 2508 return cprop_jump (BLOCK_FOR_INSN (insn), NULL, insn, from, to); 2509 return 0; 2510 } 2511 2512 /* Perform constant and copy propagation on INSN. 2513 The result is nonzero if a change was made. */ 2514 2515 static int 2516 cprop_insn (rtx insn) 2517 { 2518 struct reg_use *reg_used; 2519 int changed = 0; 2520 rtx note; 2521 2522 if (!INSN_P (insn)) 2523 return 0; 2524 2525 reg_use_count = 0; 2526 note_uses (&PATTERN (insn), find_used_regs, NULL); 2527 2528 note = find_reg_equal_equiv_note (insn); 2529 2530 /* We may win even when propagating constants into notes. */ 2531 if (note) 2532 find_used_regs (&XEXP (note, 0), NULL); 2533 2534 for (reg_used = ®_use_table[0]; reg_use_count > 0; 2535 reg_used++, reg_use_count--) 2536 { 2537 unsigned int regno = REGNO (reg_used->reg_rtx); 2538 rtx pat, src; 2539 struct expr *set; 2540 2541 /* If the register has already been set in this block, there's 2542 nothing we can do. */ 2543 if (! oprs_not_set_p (reg_used->reg_rtx, insn)) 2544 continue; 2545 2546 /* Find an assignment that sets reg_used and is available 2547 at the start of the block. */ 2548 set = find_avail_set (regno, insn); 2549 if (! set) 2550 continue; 2551 2552 pat = set->expr; 2553 /* ??? We might be able to handle PARALLELs. Later. */ 2554 gcc_assert (GET_CODE (pat) == SET); 2555 2556 src = SET_SRC (pat); 2557 2558 /* Constant propagation. */ 2559 if (gcse_constant_p (src)) 2560 { 2561 if (constprop_register (insn, reg_used->reg_rtx, src)) 2562 { 2563 changed = 1; 2564 global_const_prop_count++; 2565 if (dump_file != NULL) 2566 { 2567 fprintf (dump_file, "GLOBAL CONST-PROP: Replacing reg %d in ", regno); 2568 fprintf (dump_file, "insn %d with constant ", INSN_UID (insn)); 2569 print_rtl (dump_file, src); 2570 fprintf (dump_file, "\n"); 2571 } 2572 if (INSN_DELETED_P (insn)) 2573 return 1; 2574 } 2575 } 2576 else if (REG_P (src) 2577 && REGNO (src) >= FIRST_PSEUDO_REGISTER 2578 && REGNO (src) != regno) 2579 { 2580 if (try_replace_reg (reg_used->reg_rtx, src, insn)) 2581 { 2582 changed = 1; 2583 global_copy_prop_count++; 2584 if (dump_file != NULL) 2585 { 2586 fprintf (dump_file, "GLOBAL COPY-PROP: Replacing reg %d in insn %d", 2587 regno, INSN_UID (insn)); 2588 fprintf (dump_file, " with reg %d\n", REGNO (src)); 2589 } 2590 2591 /* The original insn setting reg_used may or may not now be 2592 deletable. We leave the deletion to flow. */ 2593 /* FIXME: If it turns out that the insn isn't deletable, 2594 then we may have unnecessarily extended register lifetimes 2595 and made things worse. */ 2596 } 2597 } 2598 } 2599 2600 if (changed && DEBUG_INSN_P (insn)) 2601 return 0; 2602 2603 return changed; 2604 } 2605 2606 /* Like find_used_regs, but avoid recording uses that appear in 2607 input-output contexts such as zero_extract or pre_dec. This 2608 restricts the cases we consider to those for which local cprop 2609 can legitimately make replacements. */ 2610 2611 static void 2612 local_cprop_find_used_regs (rtx *xptr, void *data) 2613 { 2614 rtx x = *xptr; 2615 2616 if (x == 0) 2617 return; 2618 2619 switch (GET_CODE (x)) 2620 { 2621 case ZERO_EXTRACT: 2622 case SIGN_EXTRACT: 2623 case STRICT_LOW_PART: 2624 return; 2625 2626 case PRE_DEC: 2627 case PRE_INC: 2628 case POST_DEC: 2629 case POST_INC: 2630 case PRE_MODIFY: 2631 case POST_MODIFY: 2632 /* Can only legitimately appear this early in the context of 2633 stack pushes for function arguments, but handle all of the 2634 codes nonetheless. */ 2635 return; 2636 2637 case SUBREG: 2638 /* Setting a subreg of a register larger than word_mode leaves 2639 the non-written words unchanged. */ 2640 if (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))) > BITS_PER_WORD) 2641 return; 2642 break; 2643 2644 default: 2645 break; 2646 } 2647 2648 find_used_regs (xptr, data); 2649 } 2650 2651 /* Try to perform local const/copy propagation on X in INSN. */ 2652 2653 static bool 2654 do_local_cprop (rtx x, rtx insn) 2655 { 2656 rtx newreg = NULL, newcnst = NULL; 2657 2658 /* Rule out USE instructions and ASM statements as we don't want to 2659 change the hard registers mentioned. */ 2660 if (REG_P (x) 2661 && (REGNO (x) >= FIRST_PSEUDO_REGISTER 2662 || (GET_CODE (PATTERN (insn)) != USE 2663 && asm_noperands (PATTERN (insn)) < 0))) 2664 { 2665 cselib_val *val = cselib_lookup (x, GET_MODE (x), 0); 2666 struct elt_loc_list *l; 2667 2668 if (!val) 2669 return false; 2670 for (l = val->locs; l; l = l->next) 2671 { 2672 rtx this_rtx = l->loc; 2673 rtx note; 2674 2675 if (gcse_constant_p (this_rtx)) 2676 newcnst = this_rtx; 2677 if (REG_P (this_rtx) && REGNO (this_rtx) >= FIRST_PSEUDO_REGISTER 2678 /* Don't copy propagate if it has attached REG_EQUIV note. 2679 At this point this only function parameters should have 2680 REG_EQUIV notes and if the argument slot is used somewhere 2681 explicitly, it means address of parameter has been taken, 2682 so we should not extend the lifetime of the pseudo. */ 2683 && (!(note = find_reg_note (l->setting_insn, REG_EQUIV, NULL_RTX)) 2684 || ! MEM_P (XEXP (note, 0)))) 2685 newreg = this_rtx; 2686 } 2687 if (newcnst && constprop_register (insn, x, newcnst)) 2688 { 2689 if (dump_file != NULL) 2690 { 2691 fprintf (dump_file, "LOCAL CONST-PROP: Replacing reg %d in ", 2692 REGNO (x)); 2693 fprintf (dump_file, "insn %d with constant ", 2694 INSN_UID (insn)); 2695 print_rtl (dump_file, newcnst); 2696 fprintf (dump_file, "\n"); 2697 } 2698 local_const_prop_count++; 2699 return true; 2700 } 2701 else if (newreg && newreg != x && try_replace_reg (x, newreg, insn)) 2702 { 2703 if (dump_file != NULL) 2704 { 2705 fprintf (dump_file, 2706 "LOCAL COPY-PROP: Replacing reg %d in insn %d", 2707 REGNO (x), INSN_UID (insn)); 2708 fprintf (dump_file, " with reg %d\n", REGNO (newreg)); 2709 } 2710 local_copy_prop_count++; 2711 return true; 2712 } 2713 } 2714 return false; 2715 } 2716 2717 /* Do local const/copy propagation (i.e. within each basic block). */ 2718 2719 static int 2720 local_cprop_pass (void) 2721 { 2722 basic_block bb; 2723 rtx insn; 2724 struct reg_use *reg_used; 2725 bool changed = false; 2726 2727 cselib_init (0); 2728 FOR_EACH_BB (bb) 2729 { 2730 FOR_BB_INSNS (bb, insn) 2731 { 2732 if (INSN_P (insn)) 2733 { 2734 rtx note = find_reg_equal_equiv_note (insn); 2735 do 2736 { 2737 reg_use_count = 0; 2738 note_uses (&PATTERN (insn), local_cprop_find_used_regs, 2739 NULL); 2740 if (note) 2741 local_cprop_find_used_regs (&XEXP (note, 0), NULL); 2742 2743 for (reg_used = ®_use_table[0]; reg_use_count > 0; 2744 reg_used++, reg_use_count--) 2745 { 2746 if (do_local_cprop (reg_used->reg_rtx, insn)) 2747 { 2748 changed = true; 2749 break; 2750 } 2751 } 2752 if (INSN_DELETED_P (insn)) 2753 break; 2754 } 2755 while (reg_use_count); 2756 } 2757 cselib_process_insn (insn); 2758 } 2759 2760 /* Forget everything at the end of a basic block. */ 2761 cselib_clear_table (); 2762 } 2763 2764 cselib_finish (); 2765 2766 return changed; 2767 } 2768 2769 /* Similar to get_condition, only the resulting condition must be 2770 valid at JUMP, instead of at EARLIEST. 2771 2772 This differs from noce_get_condition in ifcvt.c in that we prefer not to 2773 settle for the condition variable in the jump instruction being integral. 2774 We prefer to be able to record the value of a user variable, rather than 2775 the value of a temporary used in a condition. This could be solved by 2776 recording the value of *every* register scanned by canonicalize_condition, 2777 but this would require some code reorganization. */ 2778 2779 rtx 2780 fis_get_condition (rtx jump) 2781 { 2782 return get_condition (jump, NULL, false, true); 2783 } 2784 2785 /* Check the comparison COND to see if we can safely form an implicit set from 2786 it. COND is either an EQ or NE comparison. */ 2787 2788 static bool 2789 implicit_set_cond_p (const_rtx cond) 2790 { 2791 const enum machine_mode mode = GET_MODE (XEXP (cond, 0)); 2792 const_rtx cst = XEXP (cond, 1); 2793 2794 /* We can't perform this optimization if either operand might be or might 2795 contain a signed zero. */ 2796 if (HONOR_SIGNED_ZEROS (mode)) 2797 { 2798 /* It is sufficient to check if CST is or contains a zero. We must 2799 handle float, complex, and vector. If any subpart is a zero, then 2800 the optimization can't be performed. */ 2801 /* ??? The complex and vector checks are not implemented yet. We just 2802 always return zero for them. */ 2803 if (GET_CODE (cst) == CONST_DOUBLE) 2804 { 2805 REAL_VALUE_TYPE d; 2806 REAL_VALUE_FROM_CONST_DOUBLE (d, cst); 2807 if (REAL_VALUES_EQUAL (d, dconst0)) 2808 return 0; 2809 } 2810 else 2811 return 0; 2812 } 2813 2814 return gcse_constant_p (cst); 2815 } 2816 2817 /* Find the implicit sets of a function. An "implicit set" is a constraint 2818 on the value of a variable, implied by a conditional jump. For example, 2819 following "if (x == 2)", the then branch may be optimized as though the 2820 conditional performed an "explicit set", in this example, "x = 2". This 2821 function records the set patterns that are implicit at the start of each 2822 basic block. 2823 2824 FIXME: This would be more effective if critical edges are pre-split. As 2825 it is now, we can't record implicit sets for blocks that have 2826 critical successor edges. This results in missed optimizations 2827 and in more (unnecessary) work in cfgcleanup.c:thread_jump(). */ 2828 2829 static void 2830 find_implicit_sets (void) 2831 { 2832 basic_block bb, dest; 2833 unsigned int count; 2834 rtx cond, new_rtx; 2835 2836 count = 0; 2837 FOR_EACH_BB (bb) 2838 /* Check for more than one successor. */ 2839 if (EDGE_COUNT (bb->succs) > 1) 2840 { 2841 cond = fis_get_condition (BB_END (bb)); 2842 2843 if (cond 2844 && (GET_CODE (cond) == EQ || GET_CODE (cond) == NE) 2845 && REG_P (XEXP (cond, 0)) 2846 && REGNO (XEXP (cond, 0)) >= FIRST_PSEUDO_REGISTER 2847 && implicit_set_cond_p (cond)) 2848 { 2849 dest = GET_CODE (cond) == EQ ? BRANCH_EDGE (bb)->dest 2850 : FALLTHRU_EDGE (bb)->dest; 2851 2852 if (dest 2853 /* Record nothing for a critical edge. */ 2854 && single_pred_p (dest) 2855 && dest != EXIT_BLOCK_PTR) 2856 { 2857 new_rtx = gen_rtx_SET (VOIDmode, XEXP (cond, 0), 2858 XEXP (cond, 1)); 2859 implicit_sets[dest->index] = new_rtx; 2860 if (dump_file) 2861 { 2862 fprintf(dump_file, "Implicit set of reg %d in ", 2863 REGNO (XEXP (cond, 0))); 2864 fprintf(dump_file, "basic block %d\n", dest->index); 2865 } 2866 count++; 2867 } 2868 } 2869 } 2870 2871 if (dump_file) 2872 fprintf (dump_file, "Found %d implicit sets\n", count); 2873 } 2874 2875 /* Bypass conditional jumps. */ 2876 2877 /* The value of last_basic_block at the beginning of the jump_bypass 2878 pass. The use of redirect_edge_and_branch_force may introduce new 2879 basic blocks, but the data flow analysis is only valid for basic 2880 block indices less than bypass_last_basic_block. */ 2881 2882 static int bypass_last_basic_block; 2883 2884 /* Find a set of REGNO to a constant that is available at the end of basic 2885 block BB. Returns NULL if no such set is found. Based heavily upon 2886 find_avail_set. */ 2887 2888 static struct expr * 2889 find_bypass_set (int regno, int bb) 2890 { 2891 struct expr *result = 0; 2892 2893 for (;;) 2894 { 2895 rtx src; 2896 struct expr *set = lookup_set (regno, &set_hash_table); 2897 2898 while (set) 2899 { 2900 if (TEST_BIT (cprop_avout[bb], set->bitmap_index)) 2901 break; 2902 set = next_set (regno, set); 2903 } 2904 2905 if (set == 0) 2906 break; 2907 2908 gcc_assert (GET_CODE (set->expr) == SET); 2909 2910 src = SET_SRC (set->expr); 2911 if (gcse_constant_p (src)) 2912 result = set; 2913 2914 if (! REG_P (src)) 2915 break; 2916 2917 regno = REGNO (src); 2918 } 2919 return result; 2920 } 2921 2922 2923 /* Subroutine of bypass_block that checks whether a pseudo is killed by 2924 any of the instructions inserted on an edge. Jump bypassing places 2925 condition code setters on CFG edges using insert_insn_on_edge. This 2926 function is required to check that our data flow analysis is still 2927 valid prior to commit_edge_insertions. */ 2928 2929 static bool 2930 reg_killed_on_edge (const_rtx reg, const_edge e) 2931 { 2932 rtx insn; 2933 2934 for (insn = e->insns.r; insn; insn = NEXT_INSN (insn)) 2935 if (INSN_P (insn) && reg_set_p (reg, insn)) 2936 return true; 2937 2938 return false; 2939 } 2940 2941 /* Subroutine of bypass_conditional_jumps that attempts to bypass the given 2942 basic block BB which has more than one predecessor. If not NULL, SETCC 2943 is the first instruction of BB, which is immediately followed by JUMP_INSN 2944 JUMP. Otherwise, SETCC is NULL, and JUMP is the first insn of BB. 2945 Returns nonzero if a change was made. 2946 2947 During the jump bypassing pass, we may place copies of SETCC instructions 2948 on CFG edges. The following routine must be careful to pay attention to 2949 these inserted insns when performing its transformations. */ 2950 2951 static int 2952 bypass_block (basic_block bb, rtx setcc, rtx jump) 2953 { 2954 rtx insn, note; 2955 edge e, edest; 2956 int i, change; 2957 int may_be_loop_header; 2958 unsigned removed_p; 2959 edge_iterator ei; 2960 2961 insn = (setcc != NULL) ? setcc : jump; 2962 2963 /* Determine set of register uses in INSN. */ 2964 reg_use_count = 0; 2965 note_uses (&PATTERN (insn), find_used_regs, NULL); 2966 note = find_reg_equal_equiv_note (insn); 2967 if (note) 2968 find_used_regs (&XEXP (note, 0), NULL); 2969 2970 may_be_loop_header = false; 2971 FOR_EACH_EDGE (e, ei, bb->preds) 2972 if (e->flags & EDGE_DFS_BACK) 2973 { 2974 may_be_loop_header = true; 2975 break; 2976 } 2977 2978 change = 0; 2979 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); ) 2980 { 2981 removed_p = 0; 2982 2983 if (e->flags & EDGE_COMPLEX) 2984 { 2985 ei_next (&ei); 2986 continue; 2987 } 2988 2989 /* We can't redirect edges from new basic blocks. */ 2990 if (e->src->index >= bypass_last_basic_block) 2991 { 2992 ei_next (&ei); 2993 continue; 2994 } 2995 2996 /* The irreducible loops created by redirecting of edges entering the 2997 loop from outside would decrease effectiveness of some of the following 2998 optimizations, so prevent this. */ 2999 if (may_be_loop_header 3000 && !(e->flags & EDGE_DFS_BACK)) 3001 { 3002 ei_next (&ei); 3003 continue; 3004 } 3005 3006 for (i = 0; i < reg_use_count; i++) 3007 { 3008 struct reg_use *reg_used = ®_use_table[i]; 3009 unsigned int regno = REGNO (reg_used->reg_rtx); 3010 basic_block dest, old_dest; 3011 struct expr *set; 3012 rtx src, new_rtx; 3013 3014 set = find_bypass_set (regno, e->src->index); 3015 3016 if (! set) 3017 continue; 3018 3019 /* Check the data flow is valid after edge insertions. */ 3020 if (e->insns.r && reg_killed_on_edge (reg_used->reg_rtx, e)) 3021 continue; 3022 3023 src = SET_SRC (pc_set (jump)); 3024 3025 if (setcc != NULL) 3026 src = simplify_replace_rtx (src, 3027 SET_DEST (PATTERN (setcc)), 3028 SET_SRC (PATTERN (setcc))); 3029 3030 new_rtx = simplify_replace_rtx (src, reg_used->reg_rtx, 3031 SET_SRC (set->expr)); 3032 3033 /* Jump bypassing may have already placed instructions on 3034 edges of the CFG. We can't bypass an outgoing edge that 3035 has instructions associated with it, as these insns won't 3036 get executed if the incoming edge is redirected. */ 3037 3038 if (new_rtx == pc_rtx) 3039 { 3040 edest = FALLTHRU_EDGE (bb); 3041 dest = edest->insns.r ? NULL : edest->dest; 3042 } 3043 else if (GET_CODE (new_rtx) == LABEL_REF) 3044 { 3045 dest = BLOCK_FOR_INSN (XEXP (new_rtx, 0)); 3046 /* Don't bypass edges containing instructions. */ 3047 edest = find_edge (bb, dest); 3048 if (edest && edest->insns.r) 3049 dest = NULL; 3050 } 3051 else 3052 dest = NULL; 3053 3054 /* Avoid unification of the edge with other edges from original 3055 branch. We would end up emitting the instruction on "both" 3056 edges. */ 3057 3058 if (dest && setcc && !CC0_P (SET_DEST (PATTERN (setcc))) 3059 && find_edge (e->src, dest)) 3060 dest = NULL; 3061 3062 old_dest = e->dest; 3063 if (dest != NULL 3064 && dest != old_dest 3065 && dest != EXIT_BLOCK_PTR) 3066 { 3067 redirect_edge_and_branch_force (e, dest); 3068 3069 /* Copy the register setter to the redirected edge. 3070 Don't copy CC0 setters, as CC0 is dead after jump. */ 3071 if (setcc) 3072 { 3073 rtx pat = PATTERN (setcc); 3074 if (!CC0_P (SET_DEST (pat))) 3075 insert_insn_on_edge (copy_insn (pat), e); 3076 } 3077 3078 if (dump_file != NULL) 3079 { 3080 fprintf (dump_file, "JUMP-BYPASS: Proved reg %d " 3081 "in jump_insn %d equals constant ", 3082 regno, INSN_UID (jump)); 3083 print_rtl (dump_file, SET_SRC (set->expr)); 3084 fprintf (dump_file, "\nBypass edge from %d->%d to %d\n", 3085 e->src->index, old_dest->index, dest->index); 3086 } 3087 change = 1; 3088 removed_p = 1; 3089 break; 3090 } 3091 } 3092 if (!removed_p) 3093 ei_next (&ei); 3094 } 3095 return change; 3096 } 3097 3098 /* Find basic blocks with more than one predecessor that only contain a 3099 single conditional jump. If the result of the comparison is known at 3100 compile-time from any incoming edge, redirect that edge to the 3101 appropriate target. Returns nonzero if a change was made. 3102 3103 This function is now mis-named, because we also handle indirect jumps. */ 3104 3105 static int 3106 bypass_conditional_jumps (void) 3107 { 3108 basic_block bb; 3109 int changed; 3110 rtx setcc; 3111 rtx insn; 3112 rtx dest; 3113 3114 /* Note we start at block 1. */ 3115 if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR) 3116 return 0; 3117 3118 bypass_last_basic_block = last_basic_block; 3119 mark_dfs_back_edges (); 3120 3121 changed = 0; 3122 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb, 3123 EXIT_BLOCK_PTR, next_bb) 3124 { 3125 /* Check for more than one predecessor. */ 3126 if (!single_pred_p (bb)) 3127 { 3128 setcc = NULL_RTX; 3129 FOR_BB_INSNS (bb, insn) 3130 if (DEBUG_INSN_P (insn)) 3131 continue; 3132 else if (NONJUMP_INSN_P (insn)) 3133 { 3134 if (setcc) 3135 break; 3136 if (GET_CODE (PATTERN (insn)) != SET) 3137 break; 3138 3139 dest = SET_DEST (PATTERN (insn)); 3140 if (REG_P (dest) || CC0_P (dest)) 3141 setcc = insn; 3142 else 3143 break; 3144 } 3145 else if (JUMP_P (insn)) 3146 { 3147 if ((any_condjump_p (insn) || computed_jump_p (insn)) 3148 && onlyjump_p (insn)) 3149 changed |= bypass_block (bb, setcc, insn); 3150 break; 3151 } 3152 else if (INSN_P (insn)) 3153 break; 3154 } 3155 } 3156 3157 /* If we bypassed any register setting insns, we inserted a 3158 copy on the redirected edge. These need to be committed. */ 3159 if (changed) 3160 commit_edge_insertions (); 3161 3162 return changed; 3163 } 3164 3165 /* Compute PRE+LCM working variables. */ 3166 3167 /* Local properties of expressions. */ 3168 /* Nonzero for expressions that are transparent in the block. */ 3169 static sbitmap *transp; 3170 3171 /* Nonzero for expressions that are transparent at the end of the block. 3172 This is only zero for expressions killed by abnormal critical edge 3173 created by a calls. */ 3174 static sbitmap *transpout; 3175 3176 /* Nonzero for expressions that are computed (available) in the block. */ 3177 static sbitmap *comp; 3178 3179 /* Nonzero for expressions that are locally anticipatable in the block. */ 3180 static sbitmap *antloc; 3181 3182 /* Nonzero for expressions where this block is an optimal computation 3183 point. */ 3184 static sbitmap *pre_optimal; 3185 3186 /* Nonzero for expressions which are redundant in a particular block. */ 3187 static sbitmap *pre_redundant; 3188 3189 /* Nonzero for expressions which should be inserted on a specific edge. */ 3190 static sbitmap *pre_insert_map; 3191 3192 /* Nonzero for expressions which should be deleted in a specific block. */ 3193 static sbitmap *pre_delete_map; 3194 3195 /* Contains the edge_list returned by pre_edge_lcm. */ 3196 static struct edge_list *edge_list; 3197 3198 /* Allocate vars used for PRE analysis. */ 3199 3200 static void 3201 alloc_pre_mem (int n_blocks, int n_exprs) 3202 { 3203 transp = sbitmap_vector_alloc (n_blocks, n_exprs); 3204 comp = sbitmap_vector_alloc (n_blocks, n_exprs); 3205 antloc = sbitmap_vector_alloc (n_blocks, n_exprs); 3206 3207 pre_optimal = NULL; 3208 pre_redundant = NULL; 3209 pre_insert_map = NULL; 3210 pre_delete_map = NULL; 3211 ae_kill = sbitmap_vector_alloc (n_blocks, n_exprs); 3212 3213 /* pre_insert and pre_delete are allocated later. */ 3214 } 3215 3216 /* Free vars used for PRE analysis. */ 3217 3218 static void 3219 free_pre_mem (void) 3220 { 3221 sbitmap_vector_free (transp); 3222 sbitmap_vector_free (comp); 3223 3224 /* ANTLOC and AE_KILL are freed just after pre_lcm finishes. */ 3225 3226 if (pre_optimal) 3227 sbitmap_vector_free (pre_optimal); 3228 if (pre_redundant) 3229 sbitmap_vector_free (pre_redundant); 3230 if (pre_insert_map) 3231 sbitmap_vector_free (pre_insert_map); 3232 if (pre_delete_map) 3233 sbitmap_vector_free (pre_delete_map); 3234 3235 transp = comp = NULL; 3236 pre_optimal = pre_redundant = pre_insert_map = pre_delete_map = NULL; 3237 } 3238 3239 /* Top level routine to do the dataflow analysis needed by PRE. */ 3240 3241 static void 3242 compute_pre_data (void) 3243 { 3244 sbitmap trapping_expr; 3245 basic_block bb; 3246 unsigned int ui; 3247 3248 compute_local_properties (transp, comp, antloc, &expr_hash_table); 3249 sbitmap_vector_zero (ae_kill, last_basic_block); 3250 3251 /* Collect expressions which might trap. */ 3252 trapping_expr = sbitmap_alloc (expr_hash_table.n_elems); 3253 sbitmap_zero (trapping_expr); 3254 for (ui = 0; ui < expr_hash_table.size; ui++) 3255 { 3256 struct expr *e; 3257 for (e = expr_hash_table.table[ui]; e != NULL; e = e->next_same_hash) 3258 if (may_trap_p (e->expr)) 3259 SET_BIT (trapping_expr, e->bitmap_index); 3260 } 3261 3262 /* Compute ae_kill for each basic block using: 3263 3264 ~(TRANSP | COMP) 3265 */ 3266 3267 FOR_EACH_BB (bb) 3268 { 3269 edge e; 3270 edge_iterator ei; 3271 3272 /* If the current block is the destination of an abnormal edge, we 3273 kill all trapping expressions because we won't be able to properly 3274 place the instruction on the edge. So make them neither 3275 anticipatable nor transparent. This is fairly conservative. */ 3276 FOR_EACH_EDGE (e, ei, bb->preds) 3277 if (e->flags & EDGE_ABNORMAL) 3278 { 3279 sbitmap_difference (antloc[bb->index], antloc[bb->index], trapping_expr); 3280 sbitmap_difference (transp[bb->index], transp[bb->index], trapping_expr); 3281 break; 3282 } 3283 3284 sbitmap_a_or_b (ae_kill[bb->index], transp[bb->index], comp[bb->index]); 3285 sbitmap_not (ae_kill[bb->index], ae_kill[bb->index]); 3286 } 3287 3288 edge_list = pre_edge_lcm (expr_hash_table.n_elems, transp, comp, antloc, 3289 ae_kill, &pre_insert_map, &pre_delete_map); 3290 sbitmap_vector_free (antloc); 3291 antloc = NULL; 3292 sbitmap_vector_free (ae_kill); 3293 ae_kill = NULL; 3294 sbitmap_free (trapping_expr); 3295 } 3296 3297 /* PRE utilities */ 3298 3299 /* Return nonzero if an occurrence of expression EXPR in OCCR_BB would reach 3300 block BB. 3301 3302 VISITED is a pointer to a working buffer for tracking which BB's have 3303 been visited. It is NULL for the top-level call. 3304 3305 We treat reaching expressions that go through blocks containing the same 3306 reaching expression as "not reaching". E.g. if EXPR is generated in blocks 3307 2 and 3, INSN is in block 4, and 2->3->4, we treat the expression in block 3308 2 as not reaching. The intent is to improve the probability of finding 3309 only one reaching expression and to reduce register lifetimes by picking 3310 the closest such expression. */ 3311 3312 static int 3313 pre_expr_reaches_here_p_work (basic_block occr_bb, struct expr *expr, basic_block bb, char *visited) 3314 { 3315 edge pred; 3316 edge_iterator ei; 3317 3318 FOR_EACH_EDGE (pred, ei, bb->preds) 3319 { 3320 basic_block pred_bb = pred->src; 3321 3322 if (pred->src == ENTRY_BLOCK_PTR 3323 /* Has predecessor has already been visited? */ 3324 || visited[pred_bb->index]) 3325 ;/* Nothing to do. */ 3326 3327 /* Does this predecessor generate this expression? */ 3328 else if (TEST_BIT (comp[pred_bb->index], expr->bitmap_index)) 3329 { 3330 /* Is this the occurrence we're looking for? 3331 Note that there's only one generating occurrence per block 3332 so we just need to check the block number. */ 3333 if (occr_bb == pred_bb) 3334 return 1; 3335 3336 visited[pred_bb->index] = 1; 3337 } 3338 /* Ignore this predecessor if it kills the expression. */ 3339 else if (! TEST_BIT (transp[pred_bb->index], expr->bitmap_index)) 3340 visited[pred_bb->index] = 1; 3341 3342 /* Neither gen nor kill. */ 3343 else 3344 { 3345 visited[pred_bb->index] = 1; 3346 if (pre_expr_reaches_here_p_work (occr_bb, expr, pred_bb, visited)) 3347 return 1; 3348 } 3349 } 3350 3351 /* All paths have been checked. */ 3352 return 0; 3353 } 3354 3355 /* The wrapper for pre_expr_reaches_here_work that ensures that any 3356 memory allocated for that function is returned. */ 3357 3358 static int 3359 pre_expr_reaches_here_p (basic_block occr_bb, struct expr *expr, basic_block bb) 3360 { 3361 int rval; 3362 char *visited = XCNEWVEC (char, last_basic_block); 3363 3364 rval = pre_expr_reaches_here_p_work (occr_bb, expr, bb, visited); 3365 3366 free (visited); 3367 return rval; 3368 } 3369 3370 3371 /* Given an expr, generate RTL which we can insert at the end of a BB, 3372 or on an edge. Set the block number of any insns generated to 3373 the value of BB. */ 3374 3375 static rtx 3376 process_insert_insn (struct expr *expr) 3377 { 3378 rtx reg = expr->reaching_reg; 3379 rtx exp = copy_rtx (expr->expr); 3380 rtx pat; 3381 3382 start_sequence (); 3383 3384 /* If the expression is something that's an operand, like a constant, 3385 just copy it to a register. */ 3386 if (general_operand (exp, GET_MODE (reg))) 3387 emit_move_insn (reg, exp); 3388 3389 /* Otherwise, make a new insn to compute this expression and make sure the 3390 insn will be recognized (this also adds any needed CLOBBERs). Copy the 3391 expression to make sure we don't have any sharing issues. */ 3392 else 3393 { 3394 rtx insn = emit_insn (gen_rtx_SET (VOIDmode, reg, exp)); 3395 3396 if (insn_invalid_p (insn)) 3397 gcc_unreachable (); 3398 } 3399 3400 3401 pat = get_insns (); 3402 end_sequence (); 3403 3404 return pat; 3405 } 3406 3407 /* Add EXPR to the end of basic block BB. 3408 3409 This is used by both the PRE and code hoisting. 3410 3411 For PRE, we want to verify that the expr is either transparent 3412 or locally anticipatable in the target block. This check makes 3413 no sense for code hoisting. */ 3414 3415 static void 3416 insert_insn_end_basic_block (struct expr *expr, basic_block bb, int pre) 3417 { 3418 rtx insn = BB_END (bb); 3419 rtx new_insn; 3420 rtx reg = expr->reaching_reg; 3421 int regno = REGNO (reg); 3422 rtx pat, pat_end; 3423 3424 pat = process_insert_insn (expr); 3425 gcc_assert (pat && INSN_P (pat)); 3426 3427 pat_end = pat; 3428 while (NEXT_INSN (pat_end) != NULL_RTX) 3429 pat_end = NEXT_INSN (pat_end); 3430 3431 /* If the last insn is a jump, insert EXPR in front [taking care to 3432 handle cc0, etc. properly]. Similarly we need to care trapping 3433 instructions in presence of non-call exceptions. */ 3434 3435 if (JUMP_P (insn) 3436 || (NONJUMP_INSN_P (insn) 3437 && (!single_succ_p (bb) 3438 || single_succ_edge (bb)->flags & EDGE_ABNORMAL))) 3439 { 3440 #ifdef HAVE_cc0 3441 rtx note; 3442 #endif 3443 /* It should always be the case that we can put these instructions 3444 anywhere in the basic block with performing PRE optimizations. 3445 Check this. */ 3446 gcc_assert (!NONJUMP_INSN_P (insn) || !pre 3447 || TEST_BIT (antloc[bb->index], expr->bitmap_index) 3448 || TEST_BIT (transp[bb->index], expr->bitmap_index)); 3449 3450 /* If this is a jump table, then we can't insert stuff here. Since 3451 we know the previous real insn must be the tablejump, we insert 3452 the new instruction just before the tablejump. */ 3453 if (GET_CODE (PATTERN (insn)) == ADDR_VEC 3454 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC) 3455 insn = prev_real_insn (insn); 3456 3457 #ifdef HAVE_cc0 3458 /* FIXME: 'twould be nice to call prev_cc0_setter here but it aborts 3459 if cc0 isn't set. */ 3460 note = find_reg_note (insn, REG_CC_SETTER, NULL_RTX); 3461 if (note) 3462 insn = XEXP (note, 0); 3463 else 3464 { 3465 rtx maybe_cc0_setter = prev_nonnote_insn (insn); 3466 if (maybe_cc0_setter 3467 && INSN_P (maybe_cc0_setter) 3468 && sets_cc0_p (PATTERN (maybe_cc0_setter))) 3469 insn = maybe_cc0_setter; 3470 } 3471 #endif 3472 /* FIXME: What if something in cc0/jump uses value set in new insn? */ 3473 new_insn = emit_insn_before_noloc (pat, insn, bb); 3474 } 3475 3476 /* Likewise if the last insn is a call, as will happen in the presence 3477 of exception handling. */ 3478 else if (CALL_P (insn) 3479 && (!single_succ_p (bb) 3480 || single_succ_edge (bb)->flags & EDGE_ABNORMAL)) 3481 { 3482 /* Keeping in mind SMALL_REGISTER_CLASSES and parameters in registers, 3483 we search backward and place the instructions before the first 3484 parameter is loaded. Do this for everyone for consistency and a 3485 presumption that we'll get better code elsewhere as well. 3486 3487 It should always be the case that we can put these instructions 3488 anywhere in the basic block with performing PRE optimizations. 3489 Check this. */ 3490 3491 gcc_assert (!pre 3492 || TEST_BIT (antloc[bb->index], expr->bitmap_index) 3493 || TEST_BIT (transp[bb->index], expr->bitmap_index)); 3494 3495 /* Since different machines initialize their parameter registers 3496 in different orders, assume nothing. Collect the set of all 3497 parameter registers. */ 3498 insn = find_first_parameter_load (insn, BB_HEAD (bb)); 3499 3500 /* If we found all the parameter loads, then we want to insert 3501 before the first parameter load. 3502 3503 If we did not find all the parameter loads, then we might have 3504 stopped on the head of the block, which could be a CODE_LABEL. 3505 If we inserted before the CODE_LABEL, then we would be putting 3506 the insn in the wrong basic block. In that case, put the insn 3507 after the CODE_LABEL. Also, respect NOTE_INSN_BASIC_BLOCK. */ 3508 while (LABEL_P (insn) 3509 || NOTE_INSN_BASIC_BLOCK_P (insn)) 3510 insn = NEXT_INSN (insn); 3511 3512 new_insn = emit_insn_before_noloc (pat, insn, bb); 3513 } 3514 else 3515 new_insn = emit_insn_after_noloc (pat, insn, bb); 3516 3517 while (1) 3518 { 3519 if (INSN_P (pat)) 3520 add_label_notes (PATTERN (pat), new_insn); 3521 if (pat == pat_end) 3522 break; 3523 pat = NEXT_INSN (pat); 3524 } 3525 3526 gcse_create_count++; 3527 3528 if (dump_file) 3529 { 3530 fprintf (dump_file, "PRE/HOIST: end of bb %d, insn %d, ", 3531 bb->index, INSN_UID (new_insn)); 3532 fprintf (dump_file, "copying expression %d to reg %d\n", 3533 expr->bitmap_index, regno); 3534 } 3535 } 3536 3537 /* Insert partially redundant expressions on edges in the CFG to make 3538 the expressions fully redundant. */ 3539 3540 static int 3541 pre_edge_insert (struct edge_list *edge_list, struct expr **index_map) 3542 { 3543 int e, i, j, num_edges, set_size, did_insert = 0; 3544 sbitmap *inserted; 3545 3546 /* Where PRE_INSERT_MAP is nonzero, we add the expression on that edge 3547 if it reaches any of the deleted expressions. */ 3548 3549 set_size = pre_insert_map[0]->size; 3550 num_edges = NUM_EDGES (edge_list); 3551 inserted = sbitmap_vector_alloc (num_edges, expr_hash_table.n_elems); 3552 sbitmap_vector_zero (inserted, num_edges); 3553 3554 for (e = 0; e < num_edges; e++) 3555 { 3556 int indx; 3557 basic_block bb = INDEX_EDGE_PRED_BB (edge_list, e); 3558 3559 for (i = indx = 0; i < set_size; i++, indx += SBITMAP_ELT_BITS) 3560 { 3561 SBITMAP_ELT_TYPE insert = pre_insert_map[e]->elms[i]; 3562 3563 for (j = indx; insert && j < (int) expr_hash_table.n_elems; j++, insert >>= 1) 3564 if ((insert & 1) != 0 && index_map[j]->reaching_reg != NULL_RTX) 3565 { 3566 struct expr *expr = index_map[j]; 3567 struct occr *occr; 3568 3569 /* Now look at each deleted occurrence of this expression. */ 3570 for (occr = expr->antic_occr; occr != NULL; occr = occr->next) 3571 { 3572 if (! occr->deleted_p) 3573 continue; 3574 3575 /* Insert this expression on this edge if it would 3576 reach the deleted occurrence in BB. */ 3577 if (!TEST_BIT (inserted[e], j)) 3578 { 3579 rtx insn; 3580 edge eg = INDEX_EDGE (edge_list, e); 3581 3582 /* We can't insert anything on an abnormal and 3583 critical edge, so we insert the insn at the end of 3584 the previous block. There are several alternatives 3585 detailed in Morgans book P277 (sec 10.5) for 3586 handling this situation. This one is easiest for 3587 now. */ 3588 3589 if (eg->flags & EDGE_ABNORMAL) 3590 insert_insn_end_basic_block (index_map[j], bb, 0); 3591 else 3592 { 3593 insn = process_insert_insn (index_map[j]); 3594 insert_insn_on_edge (insn, eg); 3595 } 3596 3597 if (dump_file) 3598 { 3599 fprintf (dump_file, "PRE: edge (%d,%d), ", 3600 bb->index, 3601 INDEX_EDGE_SUCC_BB (edge_list, e)->index); 3602 fprintf (dump_file, "copy expression %d\n", 3603 expr->bitmap_index); 3604 } 3605 3606 update_ld_motion_stores (expr); 3607 SET_BIT (inserted[e], j); 3608 did_insert = 1; 3609 gcse_create_count++; 3610 } 3611 } 3612 } 3613 } 3614 } 3615 3616 sbitmap_vector_free (inserted); 3617 return did_insert; 3618 } 3619 3620 /* Copy the result of EXPR->EXPR generated by INSN to EXPR->REACHING_REG. 3621 Given "old_reg <- expr" (INSN), instead of adding after it 3622 reaching_reg <- old_reg 3623 it's better to do the following: 3624 reaching_reg <- expr 3625 old_reg <- reaching_reg 3626 because this way copy propagation can discover additional PRE 3627 opportunities. But if this fails, we try the old way. 3628 When "expr" is a store, i.e. 3629 given "MEM <- old_reg", instead of adding after it 3630 reaching_reg <- old_reg 3631 it's better to add it before as follows: 3632 reaching_reg <- old_reg 3633 MEM <- reaching_reg. */ 3634 3635 static void 3636 pre_insert_copy_insn (struct expr *expr, rtx insn) 3637 { 3638 rtx reg = expr->reaching_reg; 3639 int regno = REGNO (reg); 3640 int indx = expr->bitmap_index; 3641 rtx pat = PATTERN (insn); 3642 rtx set, first_set, new_insn; 3643 rtx old_reg; 3644 int i; 3645 3646 /* This block matches the logic in hash_scan_insn. */ 3647 switch (GET_CODE (pat)) 3648 { 3649 case SET: 3650 set = pat; 3651 break; 3652 3653 case PARALLEL: 3654 /* Search through the parallel looking for the set whose 3655 source was the expression that we're interested in. */ 3656 first_set = NULL_RTX; 3657 set = NULL_RTX; 3658 for (i = 0; i < XVECLEN (pat, 0); i++) 3659 { 3660 rtx x = XVECEXP (pat, 0, i); 3661 if (GET_CODE (x) == SET) 3662 { 3663 /* If the source was a REG_EQUAL or REG_EQUIV note, we 3664 may not find an equivalent expression, but in this 3665 case the PARALLEL will have a single set. */ 3666 if (first_set == NULL_RTX) 3667 first_set = x; 3668 if (expr_equiv_p (SET_SRC (x), expr->expr)) 3669 { 3670 set = x; 3671 break; 3672 } 3673 } 3674 } 3675 3676 gcc_assert (first_set); 3677 if (set == NULL_RTX) 3678 set = first_set; 3679 break; 3680 3681 default: 3682 gcc_unreachable (); 3683 } 3684 3685 if (REG_P (SET_DEST (set))) 3686 { 3687 old_reg = SET_DEST (set); 3688 /* Check if we can modify the set destination in the original insn. */ 3689 if (validate_change (insn, &SET_DEST (set), reg, 0)) 3690 { 3691 new_insn = gen_move_insn (old_reg, reg); 3692 new_insn = emit_insn_after (new_insn, insn); 3693 } 3694 else 3695 { 3696 new_insn = gen_move_insn (reg, old_reg); 3697 new_insn = emit_insn_after (new_insn, insn); 3698 } 3699 } 3700 else /* This is possible only in case of a store to memory. */ 3701 { 3702 old_reg = SET_SRC (set); 3703 new_insn = gen_move_insn (reg, old_reg); 3704 3705 /* Check if we can modify the set source in the original insn. */ 3706 if (validate_change (insn, &SET_SRC (set), reg, 0)) 3707 new_insn = emit_insn_before (new_insn, insn); 3708 else 3709 new_insn = emit_insn_after (new_insn, insn); 3710 } 3711 3712 gcse_create_count++; 3713 3714 if (dump_file) 3715 fprintf (dump_file, 3716 "PRE: bb %d, insn %d, copy expression %d in insn %d to reg %d\n", 3717 BLOCK_FOR_INSN (insn)->index, INSN_UID (new_insn), indx, 3718 INSN_UID (insn), regno); 3719 } 3720 3721 /* Copy available expressions that reach the redundant expression 3722 to `reaching_reg'. */ 3723 3724 static void 3725 pre_insert_copies (void) 3726 { 3727 unsigned int i, added_copy; 3728 struct expr *expr; 3729 struct occr *occr; 3730 struct occr *avail; 3731 3732 /* For each available expression in the table, copy the result to 3733 `reaching_reg' if the expression reaches a deleted one. 3734 3735 ??? The current algorithm is rather brute force. 3736 Need to do some profiling. */ 3737 3738 for (i = 0; i < expr_hash_table.size; i++) 3739 for (expr = expr_hash_table.table[i]; expr != NULL; expr = expr->next_same_hash) 3740 { 3741 /* If the basic block isn't reachable, PPOUT will be TRUE. However, 3742 we don't want to insert a copy here because the expression may not 3743 really be redundant. So only insert an insn if the expression was 3744 deleted. This test also avoids further processing if the 3745 expression wasn't deleted anywhere. */ 3746 if (expr->reaching_reg == NULL) 3747 continue; 3748 3749 /* Set when we add a copy for that expression. */ 3750 added_copy = 0; 3751 3752 for (occr = expr->antic_occr; occr != NULL; occr = occr->next) 3753 { 3754 if (! occr->deleted_p) 3755 continue; 3756 3757 for (avail = expr->avail_occr; avail != NULL; avail = avail->next) 3758 { 3759 rtx insn = avail->insn; 3760 3761 /* No need to handle this one if handled already. */ 3762 if (avail->copied_p) 3763 continue; 3764 3765 /* Don't handle this one if it's a redundant one. */ 3766 if (INSN_DELETED_P (insn)) 3767 continue; 3768 3769 /* Or if the expression doesn't reach the deleted one. */ 3770 if (! pre_expr_reaches_here_p (BLOCK_FOR_INSN (avail->insn), 3771 expr, 3772 BLOCK_FOR_INSN (occr->insn))) 3773 continue; 3774 3775 added_copy = 1; 3776 3777 /* Copy the result of avail to reaching_reg. */ 3778 pre_insert_copy_insn (expr, insn); 3779 avail->copied_p = 1; 3780 } 3781 } 3782 3783 if (added_copy) 3784 update_ld_motion_stores (expr); 3785 } 3786 } 3787 3788 /* Emit move from SRC to DEST noting the equivalence with expression computed 3789 in INSN. */ 3790 static rtx 3791 gcse_emit_move_after (rtx src, rtx dest, rtx insn) 3792 { 3793 rtx new_rtx; 3794 rtx set = single_set (insn), set2; 3795 rtx note; 3796 rtx eqv; 3797 3798 /* This should never fail since we're creating a reg->reg copy 3799 we've verified to be valid. */ 3800 3801 new_rtx = emit_insn_after (gen_move_insn (dest, src), insn); 3802 3803 /* Note the equivalence for local CSE pass. */ 3804 set2 = single_set (new_rtx); 3805 if (!set2 || !rtx_equal_p (SET_DEST (set2), dest)) 3806 return new_rtx; 3807 if ((note = find_reg_equal_equiv_note (insn))) 3808 eqv = XEXP (note, 0); 3809 else 3810 eqv = SET_SRC (set); 3811 3812 set_unique_reg_note (new_rtx, REG_EQUAL, copy_insn_1 (eqv)); 3813 3814 return new_rtx; 3815 } 3816 3817 /* Delete redundant computations. 3818 Deletion is done by changing the insn to copy the `reaching_reg' of 3819 the expression into the result of the SET. It is left to later passes 3820 (cprop, cse2, flow, combine, regmove) to propagate the copy or eliminate it. 3821 3822 Returns nonzero if a change is made. */ 3823 3824 static int 3825 pre_delete (void) 3826 { 3827 unsigned int i; 3828 int changed; 3829 struct expr *expr; 3830 struct occr *occr; 3831 3832 changed = 0; 3833 for (i = 0; i < expr_hash_table.size; i++) 3834 for (expr = expr_hash_table.table[i]; 3835 expr != NULL; 3836 expr = expr->next_same_hash) 3837 { 3838 int indx = expr->bitmap_index; 3839 3840 /* We only need to search antic_occr since we require 3841 ANTLOC != 0. */ 3842 3843 for (occr = expr->antic_occr; occr != NULL; occr = occr->next) 3844 { 3845 rtx insn = occr->insn; 3846 rtx set; 3847 basic_block bb = BLOCK_FOR_INSN (insn); 3848 3849 /* We only delete insns that have a single_set. */ 3850 if (TEST_BIT (pre_delete_map[bb->index], indx) 3851 && (set = single_set (insn)) != 0 3852 && dbg_cnt (pre_insn)) 3853 { 3854 /* Create a pseudo-reg to store the result of reaching 3855 expressions into. Get the mode for the new pseudo from 3856 the mode of the original destination pseudo. */ 3857 if (expr->reaching_reg == NULL) 3858 expr->reaching_reg = gen_reg_rtx_and_attrs (SET_DEST (set)); 3859 3860 gcse_emit_move_after (expr->reaching_reg, SET_DEST (set), insn); 3861 delete_insn (insn); 3862 occr->deleted_p = 1; 3863 changed = 1; 3864 gcse_subst_count++; 3865 3866 if (dump_file) 3867 { 3868 fprintf (dump_file, 3869 "PRE: redundant insn %d (expression %d) in ", 3870 INSN_UID (insn), indx); 3871 fprintf (dump_file, "bb %d, reaching reg is %d\n", 3872 bb->index, REGNO (expr->reaching_reg)); 3873 } 3874 } 3875 } 3876 } 3877 3878 return changed; 3879 } 3880 3881 /* Perform GCSE optimizations using PRE. 3882 This is called by one_pre_gcse_pass after all the dataflow analysis 3883 has been done. 3884 3885 This is based on the original Morel-Renvoise paper Fred Chow's thesis, and 3886 lazy code motion from Knoop, Ruthing and Steffen as described in Advanced 3887 Compiler Design and Implementation. 3888 3889 ??? A new pseudo reg is created to hold the reaching expression. The nice 3890 thing about the classical approach is that it would try to use an existing 3891 reg. If the register can't be adequately optimized [i.e. we introduce 3892 reload problems], one could add a pass here to propagate the new register 3893 through the block. 3894 3895 ??? We don't handle single sets in PARALLELs because we're [currently] not 3896 able to copy the rest of the parallel when we insert copies to create full 3897 redundancies from partial redundancies. However, there's no reason why we 3898 can't handle PARALLELs in the cases where there are no partial 3899 redundancies. */ 3900 3901 static int 3902 pre_gcse (void) 3903 { 3904 unsigned int i; 3905 int did_insert, changed; 3906 struct expr **index_map; 3907 struct expr *expr; 3908 3909 /* Compute a mapping from expression number (`bitmap_index') to 3910 hash table entry. */ 3911 3912 index_map = XCNEWVEC (struct expr *, expr_hash_table.n_elems); 3913 for (i = 0; i < expr_hash_table.size; i++) 3914 for (expr = expr_hash_table.table[i]; expr != NULL; expr = expr->next_same_hash) 3915 index_map[expr->bitmap_index] = expr; 3916 3917 /* Delete the redundant insns first so that 3918 - we know what register to use for the new insns and for the other 3919 ones with reaching expressions 3920 - we know which insns are redundant when we go to create copies */ 3921 3922 changed = pre_delete (); 3923 did_insert = pre_edge_insert (edge_list, index_map); 3924 3925 /* In other places with reaching expressions, copy the expression to the 3926 specially allocated pseudo-reg that reaches the redundant expr. */ 3927 pre_insert_copies (); 3928 if (did_insert) 3929 { 3930 commit_edge_insertions (); 3931 changed = 1; 3932 } 3933 3934 free (index_map); 3935 return changed; 3936 } 3937 3938 /* Top level routine to perform one PRE GCSE pass. 3939 3940 Return nonzero if a change was made. */ 3941 3942 static int 3943 one_pre_gcse_pass (void) 3944 { 3945 int changed = 0; 3946 3947 gcse_subst_count = 0; 3948 gcse_create_count = 0; 3949 3950 /* Return if there's nothing to do, or it is too expensive. */ 3951 if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1 3952 || is_too_expensive (_("PRE disabled"))) 3953 return 0; 3954 3955 /* We need alias. */ 3956 init_alias_analysis (); 3957 3958 bytes_used = 0; 3959 gcc_obstack_init (&gcse_obstack); 3960 alloc_gcse_mem (); 3961 3962 alloc_hash_table (&expr_hash_table, 0); 3963 add_noreturn_fake_exit_edges (); 3964 if (flag_gcse_lm) 3965 compute_ld_motion_mems (); 3966 3967 compute_hash_table (&expr_hash_table); 3968 trim_ld_motion_mems (); 3969 if (dump_file) 3970 dump_hash_table (dump_file, "Expression", &expr_hash_table); 3971 3972 if (expr_hash_table.n_elems > 0) 3973 { 3974 alloc_pre_mem (last_basic_block, expr_hash_table.n_elems); 3975 compute_pre_data (); 3976 changed |= pre_gcse (); 3977 free_edge_list (edge_list); 3978 free_pre_mem (); 3979 } 3980 3981 free_ldst_mems (); 3982 remove_fake_exit_edges (); 3983 free_hash_table (&expr_hash_table); 3984 3985 free_gcse_mem (); 3986 obstack_free (&gcse_obstack, NULL); 3987 3988 /* We are finished with alias. */ 3989 end_alias_analysis (); 3990 3991 if (dump_file) 3992 { 3993 fprintf (dump_file, "PRE GCSE of %s, %d basic blocks, %d bytes needed, ", 3994 current_function_name (), n_basic_blocks, bytes_used); 3995 fprintf (dump_file, "%d substs, %d insns created\n", 3996 gcse_subst_count, gcse_create_count); 3997 } 3998 3999 return changed; 4000 } 4001 4002 /* If X contains any LABEL_REF's, add REG_LABEL_OPERAND notes for them 4003 to INSN. If such notes are added to an insn which references a 4004 CODE_LABEL, the LABEL_NUSES count is incremented. We have to add 4005 that note, because the following loop optimization pass requires 4006 them. */ 4007 4008 /* ??? If there was a jump optimization pass after gcse and before loop, 4009 then we would not need to do this here, because jump would add the 4010 necessary REG_LABEL_OPERAND and REG_LABEL_TARGET notes. */ 4011 4012 static void 4013 add_label_notes (rtx x, rtx insn) 4014 { 4015 enum rtx_code code = GET_CODE (x); 4016 int i, j; 4017 const char *fmt; 4018 4019 if (code == LABEL_REF && !LABEL_REF_NONLOCAL_P (x)) 4020 { 4021 /* This code used to ignore labels that referred to dispatch tables to 4022 avoid flow generating (slightly) worse code. 4023 4024 We no longer ignore such label references (see LABEL_REF handling in 4025 mark_jump_label for additional information). */ 4026 4027 /* There's no reason for current users to emit jump-insns with 4028 such a LABEL_REF, so we don't have to handle REG_LABEL_TARGET 4029 notes. */ 4030 gcc_assert (!JUMP_P (insn)); 4031 add_reg_note (insn, REG_LABEL_OPERAND, XEXP (x, 0)); 4032 4033 if (LABEL_P (XEXP (x, 0))) 4034 LABEL_NUSES (XEXP (x, 0))++; 4035 4036 return; 4037 } 4038 4039 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--) 4040 { 4041 if (fmt[i] == 'e') 4042 add_label_notes (XEXP (x, i), insn); 4043 else if (fmt[i] == 'E') 4044 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 4045 add_label_notes (XVECEXP (x, i, j), insn); 4046 } 4047 } 4048 4049 /* Compute transparent outgoing information for each block. 4050 4051 An expression is transparent to an edge unless it is killed by 4052 the edge itself. This can only happen with abnormal control flow, 4053 when the edge is traversed through a call. This happens with 4054 non-local labels and exceptions. 4055 4056 This would not be necessary if we split the edge. While this is 4057 normally impossible for abnormal critical edges, with some effort 4058 it should be possible with exception handling, since we still have 4059 control over which handler should be invoked. But due to increased 4060 EH table sizes, this may not be worthwhile. */ 4061 4062 static void 4063 compute_transpout (void) 4064 { 4065 basic_block bb; 4066 unsigned int i; 4067 struct expr *expr; 4068 4069 sbitmap_vector_ones (transpout, last_basic_block); 4070 4071 FOR_EACH_BB (bb) 4072 { 4073 /* Note that flow inserted a nop at the end of basic blocks that 4074 end in call instructions for reasons other than abnormal 4075 control flow. */ 4076 if (! CALL_P (BB_END (bb))) 4077 continue; 4078 4079 for (i = 0; i < expr_hash_table.size; i++) 4080 for (expr = expr_hash_table.table[i]; expr ; expr = expr->next_same_hash) 4081 if (MEM_P (expr->expr)) 4082 { 4083 if (GET_CODE (XEXP (expr->expr, 0)) == SYMBOL_REF 4084 && CONSTANT_POOL_ADDRESS_P (XEXP (expr->expr, 0))) 4085 continue; 4086 4087 /* ??? Optimally, we would use interprocedural alias 4088 analysis to determine if this mem is actually killed 4089 by this call. */ 4090 RESET_BIT (transpout[bb->index], expr->bitmap_index); 4091 } 4092 } 4093 } 4094 4095 /* Code Hoisting variables and subroutines. */ 4096 4097 /* Very busy expressions. */ 4098 static sbitmap *hoist_vbein; 4099 static sbitmap *hoist_vbeout; 4100 4101 /* Hoistable expressions. */ 4102 static sbitmap *hoist_exprs; 4103 4104 /* ??? We could compute post dominators and run this algorithm in 4105 reverse to perform tail merging, doing so would probably be 4106 more effective than the tail merging code in jump.c. 4107 4108 It's unclear if tail merging could be run in parallel with 4109 code hoisting. It would be nice. */ 4110 4111 /* Allocate vars used for code hoisting analysis. */ 4112 4113 static void 4114 alloc_code_hoist_mem (int n_blocks, int n_exprs) 4115 { 4116 antloc = sbitmap_vector_alloc (n_blocks, n_exprs); 4117 transp = sbitmap_vector_alloc (n_blocks, n_exprs); 4118 comp = sbitmap_vector_alloc (n_blocks, n_exprs); 4119 4120 hoist_vbein = sbitmap_vector_alloc (n_blocks, n_exprs); 4121 hoist_vbeout = sbitmap_vector_alloc (n_blocks, n_exprs); 4122 hoist_exprs = sbitmap_vector_alloc (n_blocks, n_exprs); 4123 transpout = sbitmap_vector_alloc (n_blocks, n_exprs); 4124 } 4125 4126 /* Free vars used for code hoisting analysis. */ 4127 4128 static void 4129 free_code_hoist_mem (void) 4130 { 4131 sbitmap_vector_free (antloc); 4132 sbitmap_vector_free (transp); 4133 sbitmap_vector_free (comp); 4134 4135 sbitmap_vector_free (hoist_vbein); 4136 sbitmap_vector_free (hoist_vbeout); 4137 sbitmap_vector_free (hoist_exprs); 4138 sbitmap_vector_free (transpout); 4139 4140 free_dominance_info (CDI_DOMINATORS); 4141 } 4142 4143 /* Compute the very busy expressions at entry/exit from each block. 4144 4145 An expression is very busy if all paths from a given point 4146 compute the expression. */ 4147 4148 static void 4149 compute_code_hoist_vbeinout (void) 4150 { 4151 int changed, passes; 4152 basic_block bb; 4153 4154 sbitmap_vector_zero (hoist_vbeout, last_basic_block); 4155 sbitmap_vector_zero (hoist_vbein, last_basic_block); 4156 4157 passes = 0; 4158 changed = 1; 4159 4160 while (changed) 4161 { 4162 changed = 0; 4163 4164 /* We scan the blocks in the reverse order to speed up 4165 the convergence. */ 4166 FOR_EACH_BB_REVERSE (bb) 4167 { 4168 if (bb->next_bb != EXIT_BLOCK_PTR) 4169 sbitmap_intersection_of_succs (hoist_vbeout[bb->index], 4170 hoist_vbein, bb->index); 4171 4172 changed |= sbitmap_a_or_b_and_c_cg (hoist_vbein[bb->index], 4173 antloc[bb->index], 4174 hoist_vbeout[bb->index], 4175 transp[bb->index]); 4176 } 4177 4178 passes++; 4179 } 4180 4181 if (dump_file) 4182 fprintf (dump_file, "hoisting vbeinout computation: %d passes\n", passes); 4183 } 4184 4185 /* Top level routine to do the dataflow analysis needed by code hoisting. */ 4186 4187 static void 4188 compute_code_hoist_data (void) 4189 { 4190 compute_local_properties (transp, comp, antloc, &expr_hash_table); 4191 compute_transpout (); 4192 compute_code_hoist_vbeinout (); 4193 calculate_dominance_info (CDI_DOMINATORS); 4194 if (dump_file) 4195 fprintf (dump_file, "\n"); 4196 } 4197 4198 /* Determine if the expression identified by EXPR_INDEX would 4199 reach BB unimpared if it was placed at the end of EXPR_BB. 4200 4201 It's unclear exactly what Muchnick meant by "unimpared". It seems 4202 to me that the expression must either be computed or transparent in 4203 *every* block in the path(s) from EXPR_BB to BB. Any other definition 4204 would allow the expression to be hoisted out of loops, even if 4205 the expression wasn't a loop invariant. 4206 4207 Contrast this to reachability for PRE where an expression is 4208 considered reachable if *any* path reaches instead of *all* 4209 paths. */ 4210 4211 static int 4212 hoist_expr_reaches_here_p (basic_block expr_bb, int expr_index, basic_block bb, char *visited) 4213 { 4214 edge pred; 4215 edge_iterator ei; 4216 int visited_allocated_locally = 0; 4217 4218 4219 if (visited == NULL) 4220 { 4221 visited_allocated_locally = 1; 4222 visited = XCNEWVEC (char, last_basic_block); 4223 } 4224 4225 FOR_EACH_EDGE (pred, ei, bb->preds) 4226 { 4227 basic_block pred_bb = pred->src; 4228 4229 if (pred->src == ENTRY_BLOCK_PTR) 4230 break; 4231 else if (pred_bb == expr_bb) 4232 continue; 4233 else if (visited[pred_bb->index]) 4234 continue; 4235 4236 /* Does this predecessor generate this expression? */ 4237 else if (TEST_BIT (comp[pred_bb->index], expr_index)) 4238 break; 4239 else if (! TEST_BIT (transp[pred_bb->index], expr_index)) 4240 break; 4241 4242 /* Not killed. */ 4243 else 4244 { 4245 visited[pred_bb->index] = 1; 4246 if (! hoist_expr_reaches_here_p (expr_bb, expr_index, 4247 pred_bb, visited)) 4248 break; 4249 } 4250 } 4251 if (visited_allocated_locally) 4252 free (visited); 4253 4254 return (pred == NULL); 4255 } 4256 4257 /* Actually perform code hoisting. */ 4258 4259 static int 4260 hoist_code (void) 4261 { 4262 basic_block bb, dominated; 4263 VEC (basic_block, heap) *domby; 4264 unsigned int i,j; 4265 struct expr **index_map; 4266 struct expr *expr; 4267 int changed = 0; 4268 4269 sbitmap_vector_zero (hoist_exprs, last_basic_block); 4270 4271 /* Compute a mapping from expression number (`bitmap_index') to 4272 hash table entry. */ 4273 4274 index_map = XCNEWVEC (struct expr *, expr_hash_table.n_elems); 4275 for (i = 0; i < expr_hash_table.size; i++) 4276 for (expr = expr_hash_table.table[i]; expr != NULL; expr = expr->next_same_hash) 4277 index_map[expr->bitmap_index] = expr; 4278 4279 /* Walk over each basic block looking for potentially hoistable 4280 expressions, nothing gets hoisted from the entry block. */ 4281 FOR_EACH_BB (bb) 4282 { 4283 int found = 0; 4284 int insn_inserted_p; 4285 4286 domby = get_dominated_by (CDI_DOMINATORS, bb); 4287 /* Examine each expression that is very busy at the exit of this 4288 block. These are the potentially hoistable expressions. */ 4289 for (i = 0; i < hoist_vbeout[bb->index]->n_bits; i++) 4290 { 4291 int hoistable = 0; 4292 4293 if (TEST_BIT (hoist_vbeout[bb->index], i) 4294 && TEST_BIT (transpout[bb->index], i)) 4295 { 4296 /* We've found a potentially hoistable expression, now 4297 we look at every block BB dominates to see if it 4298 computes the expression. */ 4299 for (j = 0; VEC_iterate (basic_block, domby, j, dominated); j++) 4300 { 4301 /* Ignore self dominance. */ 4302 if (bb == dominated) 4303 continue; 4304 /* We've found a dominated block, now see if it computes 4305 the busy expression and whether or not moving that 4306 expression to the "beginning" of that block is safe. */ 4307 if (!TEST_BIT (antloc[dominated->index], i)) 4308 continue; 4309 4310 /* Note if the expression would reach the dominated block 4311 unimpared if it was placed at the end of BB. 4312 4313 Keep track of how many times this expression is hoistable 4314 from a dominated block into BB. */ 4315 if (hoist_expr_reaches_here_p (bb, i, dominated, NULL)) 4316 hoistable++; 4317 } 4318 4319 /* If we found more than one hoistable occurrence of this 4320 expression, then note it in the bitmap of expressions to 4321 hoist. It makes no sense to hoist things which are computed 4322 in only one BB, and doing so tends to pessimize register 4323 allocation. One could increase this value to try harder 4324 to avoid any possible code expansion due to register 4325 allocation issues; however experiments have shown that 4326 the vast majority of hoistable expressions are only movable 4327 from two successors, so raising this threshold is likely 4328 to nullify any benefit we get from code hoisting. */ 4329 if (hoistable > 1) 4330 { 4331 SET_BIT (hoist_exprs[bb->index], i); 4332 found = 1; 4333 } 4334 } 4335 } 4336 /* If we found nothing to hoist, then quit now. */ 4337 if (! found) 4338 { 4339 VEC_free (basic_block, heap, domby); 4340 continue; 4341 } 4342 4343 /* Loop over all the hoistable expressions. */ 4344 for (i = 0; i < hoist_exprs[bb->index]->n_bits; i++) 4345 { 4346 /* We want to insert the expression into BB only once, so 4347 note when we've inserted it. */ 4348 insn_inserted_p = 0; 4349 4350 /* These tests should be the same as the tests above. */ 4351 if (TEST_BIT (hoist_exprs[bb->index], i)) 4352 { 4353 /* We've found a potentially hoistable expression, now 4354 we look at every block BB dominates to see if it 4355 computes the expression. */ 4356 for (j = 0; VEC_iterate (basic_block, domby, j, dominated); j++) 4357 { 4358 /* Ignore self dominance. */ 4359 if (bb == dominated) 4360 continue; 4361 4362 /* We've found a dominated block, now see if it computes 4363 the busy expression and whether or not moving that 4364 expression to the "beginning" of that block is safe. */ 4365 if (!TEST_BIT (antloc[dominated->index], i)) 4366 continue; 4367 4368 /* The expression is computed in the dominated block and 4369 it would be safe to compute it at the start of the 4370 dominated block. Now we have to determine if the 4371 expression would reach the dominated block if it was 4372 placed at the end of BB. */ 4373 if (hoist_expr_reaches_here_p (bb, i, dominated, NULL)) 4374 { 4375 struct expr *expr = index_map[i]; 4376 struct occr *occr = expr->antic_occr; 4377 rtx insn; 4378 rtx set; 4379 4380 /* Find the right occurrence of this expression. */ 4381 while (BLOCK_FOR_INSN (occr->insn) != dominated && occr) 4382 occr = occr->next; 4383 4384 gcc_assert (occr); 4385 insn = occr->insn; 4386 set = single_set (insn); 4387 gcc_assert (set); 4388 4389 /* Create a pseudo-reg to store the result of reaching 4390 expressions into. Get the mode for the new pseudo 4391 from the mode of the original destination pseudo. */ 4392 if (expr->reaching_reg == NULL) 4393 expr->reaching_reg 4394 = gen_reg_rtx_and_attrs (SET_DEST (set)); 4395 4396 gcse_emit_move_after (expr->reaching_reg, SET_DEST (set), insn); 4397 delete_insn (insn); 4398 occr->deleted_p = 1; 4399 changed = 1; 4400 gcse_subst_count++; 4401 4402 if (!insn_inserted_p) 4403 { 4404 insert_insn_end_basic_block (index_map[i], bb, 0); 4405 insn_inserted_p = 1; 4406 } 4407 } 4408 } 4409 } 4410 } 4411 VEC_free (basic_block, heap, domby); 4412 } 4413 4414 free (index_map); 4415 4416 return changed; 4417 } 4418 4419 /* Top level routine to perform one code hoisting (aka unification) pass 4420 4421 Return nonzero if a change was made. */ 4422 4423 static int 4424 one_code_hoisting_pass (void) 4425 { 4426 int changed = 0; 4427 4428 gcse_subst_count = 0; 4429 gcse_create_count = 0; 4430 4431 /* Return if there's nothing to do, or it is too expensive. */ 4432 if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1 4433 || is_too_expensive (_("GCSE disabled"))) 4434 return 0; 4435 4436 /* We need alias. */ 4437 init_alias_analysis (); 4438 4439 bytes_used = 0; 4440 gcc_obstack_init (&gcse_obstack); 4441 alloc_gcse_mem (); 4442 4443 alloc_hash_table (&expr_hash_table, 0); 4444 compute_hash_table (&expr_hash_table); 4445 if (dump_file) 4446 dump_hash_table (dump_file, "Code Hosting Expressions", &expr_hash_table); 4447 4448 if (expr_hash_table.n_elems > 0) 4449 { 4450 alloc_code_hoist_mem (last_basic_block, expr_hash_table.n_elems); 4451 compute_code_hoist_data (); 4452 changed = hoist_code (); 4453 free_code_hoist_mem (); 4454 } 4455 4456 free_hash_table (&expr_hash_table); 4457 free_gcse_mem (); 4458 obstack_free (&gcse_obstack, NULL); 4459 4460 /* We are finished with alias. */ 4461 end_alias_analysis (); 4462 4463 if (dump_file) 4464 { 4465 fprintf (dump_file, "HOIST of %s, %d basic blocks, %d bytes needed, ", 4466 current_function_name (), n_basic_blocks, bytes_used); 4467 fprintf (dump_file, "%d substs, %d insns created\n", 4468 gcse_subst_count, gcse_create_count); 4469 } 4470 4471 return changed; 4472 } 4473 4474 /* Here we provide the things required to do store motion towards 4475 the exit. In order for this to be effective, gcse also needed to 4476 be taught how to move a load when it is kill only by a store to itself. 4477 4478 int i; 4479 float a[10]; 4480 4481 void foo(float scale) 4482 { 4483 for (i=0; i<10; i++) 4484 a[i] *= scale; 4485 } 4486 4487 'i' is both loaded and stored to in the loop. Normally, gcse cannot move 4488 the load out since its live around the loop, and stored at the bottom 4489 of the loop. 4490 4491 The 'Load Motion' referred to and implemented in this file is 4492 an enhancement to gcse which when using edge based lcm, recognizes 4493 this situation and allows gcse to move the load out of the loop. 4494 4495 Once gcse has hoisted the load, store motion can then push this 4496 load towards the exit, and we end up with no loads or stores of 'i' 4497 in the loop. */ 4498 4499 static hashval_t 4500 pre_ldst_expr_hash (const void *p) 4501 { 4502 int do_not_record_p = 0; 4503 const struct ls_expr *const x = (const struct ls_expr *) p; 4504 return hash_rtx (x->pattern, GET_MODE (x->pattern), &do_not_record_p, NULL, false); 4505 } 4506 4507 static int 4508 pre_ldst_expr_eq (const void *p1, const void *p2) 4509 { 4510 const struct ls_expr *const ptr1 = (const struct ls_expr *) p1, 4511 *const ptr2 = (const struct ls_expr *) p2; 4512 return expr_equiv_p (ptr1->pattern, ptr2->pattern); 4513 } 4514 4515 /* This will search the ldst list for a matching expression. If it 4516 doesn't find one, we create one and initialize it. */ 4517 4518 static struct ls_expr * 4519 ldst_entry (rtx x) 4520 { 4521 int do_not_record_p = 0; 4522 struct ls_expr * ptr; 4523 unsigned int hash; 4524 void **slot; 4525 struct ls_expr e; 4526 4527 hash = hash_rtx (x, GET_MODE (x), &do_not_record_p, 4528 NULL, /*have_reg_qty=*/false); 4529 4530 e.pattern = x; 4531 slot = htab_find_slot_with_hash (pre_ldst_table, &e, hash, INSERT); 4532 if (*slot) 4533 return (struct ls_expr *)*slot; 4534 4535 ptr = XNEW (struct ls_expr); 4536 4537 ptr->next = pre_ldst_mems; 4538 ptr->expr = NULL; 4539 ptr->pattern = x; 4540 ptr->pattern_regs = NULL_RTX; 4541 ptr->loads = NULL_RTX; 4542 ptr->stores = NULL_RTX; 4543 ptr->reaching_reg = NULL_RTX; 4544 ptr->invalid = 0; 4545 ptr->index = 0; 4546 ptr->hash_index = hash; 4547 pre_ldst_mems = ptr; 4548 *slot = ptr; 4549 4550 return ptr; 4551 } 4552 4553 /* Free up an individual ldst entry. */ 4554 4555 static void 4556 free_ldst_entry (struct ls_expr * ptr) 4557 { 4558 free_INSN_LIST_list (& ptr->loads); 4559 free_INSN_LIST_list (& ptr->stores); 4560 4561 free (ptr); 4562 } 4563 4564 /* Free up all memory associated with the ldst list. */ 4565 4566 static void 4567 free_ldst_mems (void) 4568 { 4569 if (pre_ldst_table) 4570 htab_delete (pre_ldst_table); 4571 pre_ldst_table = NULL; 4572 4573 while (pre_ldst_mems) 4574 { 4575 struct ls_expr * tmp = pre_ldst_mems; 4576 4577 pre_ldst_mems = pre_ldst_mems->next; 4578 4579 free_ldst_entry (tmp); 4580 } 4581 4582 pre_ldst_mems = NULL; 4583 } 4584 4585 /* Dump debugging info about the ldst list. */ 4586 4587 static void 4588 print_ldst_list (FILE * file) 4589 { 4590 struct ls_expr * ptr; 4591 4592 fprintf (file, "LDST list: \n"); 4593 4594 for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr)) 4595 { 4596 fprintf (file, " Pattern (%3d): ", ptr->index); 4597 4598 print_rtl (file, ptr->pattern); 4599 4600 fprintf (file, "\n Loads : "); 4601 4602 if (ptr->loads) 4603 print_rtl (file, ptr->loads); 4604 else 4605 fprintf (file, "(nil)"); 4606 4607 fprintf (file, "\n Stores : "); 4608 4609 if (ptr->stores) 4610 print_rtl (file, ptr->stores); 4611 else 4612 fprintf (file, "(nil)"); 4613 4614 fprintf (file, "\n\n"); 4615 } 4616 4617 fprintf (file, "\n"); 4618 } 4619 4620 /* Returns 1 if X is in the list of ldst only expressions. */ 4621 4622 static struct ls_expr * 4623 find_rtx_in_ldst (rtx x) 4624 { 4625 struct ls_expr e; 4626 void **slot; 4627 if (!pre_ldst_table) 4628 return NULL; 4629 e.pattern = x; 4630 slot = htab_find_slot (pre_ldst_table, &e, NO_INSERT); 4631 if (!slot || ((struct ls_expr *)*slot)->invalid) 4632 return NULL; 4633 return (struct ls_expr *) *slot; 4634 } 4635 4636 /* Return first item in the list. */ 4637 4638 static inline struct ls_expr * 4639 first_ls_expr (void) 4640 { 4641 return pre_ldst_mems; 4642 } 4643 4644 /* Return the next item in the list after the specified one. */ 4645 4646 static inline struct ls_expr * 4647 next_ls_expr (struct ls_expr * ptr) 4648 { 4649 return ptr->next; 4650 } 4651 4652 /* Load Motion for loads which only kill themselves. */ 4653 4654 /* Return true if x is a simple MEM operation, with no registers or 4655 side effects. These are the types of loads we consider for the 4656 ld_motion list, otherwise we let the usual aliasing take care of it. */ 4657 4658 static int 4659 simple_mem (const_rtx x) 4660 { 4661 if (! MEM_P (x)) 4662 return 0; 4663 4664 if (MEM_VOLATILE_P (x)) 4665 return 0; 4666 4667 if (GET_MODE (x) == BLKmode) 4668 return 0; 4669 4670 /* If we are handling exceptions, we must be careful with memory references 4671 that may trap. If we are not, the behavior is undefined, so we may just 4672 continue. */ 4673 if (flag_non_call_exceptions && may_trap_p (x)) 4674 return 0; 4675 4676 if (side_effects_p (x)) 4677 return 0; 4678 4679 /* Do not consider function arguments passed on stack. */ 4680 if (reg_mentioned_p (stack_pointer_rtx, x)) 4681 return 0; 4682 4683 if (flag_float_store && FLOAT_MODE_P (GET_MODE (x))) 4684 return 0; 4685 4686 return 1; 4687 } 4688 4689 /* Make sure there isn't a buried reference in this pattern anywhere. 4690 If there is, invalidate the entry for it since we're not capable 4691 of fixing it up just yet.. We have to be sure we know about ALL 4692 loads since the aliasing code will allow all entries in the 4693 ld_motion list to not-alias itself. If we miss a load, we will get 4694 the wrong value since gcse might common it and we won't know to 4695 fix it up. */ 4696 4697 static void 4698 invalidate_any_buried_refs (rtx x) 4699 { 4700 const char * fmt; 4701 int i, j; 4702 struct ls_expr * ptr; 4703 4704 /* Invalidate it in the list. */ 4705 if (MEM_P (x) && simple_mem (x)) 4706 { 4707 ptr = ldst_entry (x); 4708 ptr->invalid = 1; 4709 } 4710 4711 /* Recursively process the insn. */ 4712 fmt = GET_RTX_FORMAT (GET_CODE (x)); 4713 4714 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--) 4715 { 4716 if (fmt[i] == 'e') 4717 invalidate_any_buried_refs (XEXP (x, i)); 4718 else if (fmt[i] == 'E') 4719 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 4720 invalidate_any_buried_refs (XVECEXP (x, i, j)); 4721 } 4722 } 4723 4724 /* Find all the 'simple' MEMs which are used in LOADs and STORES. Simple 4725 being defined as MEM loads and stores to symbols, with no side effects 4726 and no registers in the expression. For a MEM destination, we also 4727 check that the insn is still valid if we replace the destination with a 4728 REG, as is done in update_ld_motion_stores. If there are any uses/defs 4729 which don't match this criteria, they are invalidated and trimmed out 4730 later. */ 4731 4732 static void 4733 compute_ld_motion_mems (void) 4734 { 4735 struct ls_expr * ptr; 4736 basic_block bb; 4737 rtx insn; 4738 4739 pre_ldst_mems = NULL; 4740 pre_ldst_table = htab_create (13, pre_ldst_expr_hash, 4741 pre_ldst_expr_eq, NULL); 4742 4743 FOR_EACH_BB (bb) 4744 { 4745 FOR_BB_INSNS (bb, insn) 4746 { 4747 if (NONDEBUG_INSN_P (insn)) 4748 { 4749 if (GET_CODE (PATTERN (insn)) == SET) 4750 { 4751 rtx src = SET_SRC (PATTERN (insn)); 4752 rtx dest = SET_DEST (PATTERN (insn)); 4753 4754 /* Check for a simple LOAD... */ 4755 if (MEM_P (src) && simple_mem (src)) 4756 { 4757 ptr = ldst_entry (src); 4758 if (REG_P (dest)) 4759 ptr->loads = alloc_INSN_LIST (insn, ptr->loads); 4760 else 4761 ptr->invalid = 1; 4762 } 4763 else 4764 { 4765 /* Make sure there isn't a buried load somewhere. */ 4766 invalidate_any_buried_refs (src); 4767 } 4768 4769 /* Check for stores. Don't worry about aliased ones, they 4770 will block any movement we might do later. We only care 4771 about this exact pattern since those are the only 4772 circumstance that we will ignore the aliasing info. */ 4773 if (MEM_P (dest) && simple_mem (dest)) 4774 { 4775 ptr = ldst_entry (dest); 4776 4777 if (! MEM_P (src) 4778 && GET_CODE (src) != ASM_OPERANDS 4779 /* Check for REG manually since want_to_gcse_p 4780 returns 0 for all REGs. */ 4781 && can_assign_to_reg_without_clobbers_p (src)) 4782 ptr->stores = alloc_INSN_LIST (insn, ptr->stores); 4783 else 4784 ptr->invalid = 1; 4785 } 4786 } 4787 else 4788 invalidate_any_buried_refs (PATTERN (insn)); 4789 } 4790 } 4791 } 4792 } 4793 4794 /* Remove any references that have been either invalidated or are not in the 4795 expression list for pre gcse. */ 4796 4797 static void 4798 trim_ld_motion_mems (void) 4799 { 4800 struct ls_expr * * last = & pre_ldst_mems; 4801 struct ls_expr * ptr = pre_ldst_mems; 4802 4803 while (ptr != NULL) 4804 { 4805 struct expr * expr; 4806 4807 /* Delete if entry has been made invalid. */ 4808 if (! ptr->invalid) 4809 { 4810 /* Delete if we cannot find this mem in the expression list. */ 4811 unsigned int hash = ptr->hash_index % expr_hash_table.size; 4812 4813 for (expr = expr_hash_table.table[hash]; 4814 expr != NULL; 4815 expr = expr->next_same_hash) 4816 if (expr_equiv_p (expr->expr, ptr->pattern)) 4817 break; 4818 } 4819 else 4820 expr = (struct expr *) 0; 4821 4822 if (expr) 4823 { 4824 /* Set the expression field if we are keeping it. */ 4825 ptr->expr = expr; 4826 last = & ptr->next; 4827 ptr = ptr->next; 4828 } 4829 else 4830 { 4831 *last = ptr->next; 4832 htab_remove_elt_with_hash (pre_ldst_table, ptr, ptr->hash_index); 4833 free_ldst_entry (ptr); 4834 ptr = * last; 4835 } 4836 } 4837 4838 /* Show the world what we've found. */ 4839 if (dump_file && pre_ldst_mems != NULL) 4840 print_ldst_list (dump_file); 4841 } 4842 4843 /* This routine will take an expression which we are replacing with 4844 a reaching register, and update any stores that are needed if 4845 that expression is in the ld_motion list. Stores are updated by 4846 copying their SRC to the reaching register, and then storing 4847 the reaching register into the store location. These keeps the 4848 correct value in the reaching register for the loads. */ 4849 4850 static void 4851 update_ld_motion_stores (struct expr * expr) 4852 { 4853 struct ls_expr * mem_ptr; 4854 4855 if ((mem_ptr = find_rtx_in_ldst (expr->expr))) 4856 { 4857 /* We can try to find just the REACHED stores, but is shouldn't 4858 matter to set the reaching reg everywhere... some might be 4859 dead and should be eliminated later. */ 4860 4861 /* We replace (set mem expr) with (set reg expr) (set mem reg) 4862 where reg is the reaching reg used in the load. We checked in 4863 compute_ld_motion_mems that we can replace (set mem expr) with 4864 (set reg expr) in that insn. */ 4865 rtx list = mem_ptr->stores; 4866 4867 for ( ; list != NULL_RTX; list = XEXP (list, 1)) 4868 { 4869 rtx insn = XEXP (list, 0); 4870 rtx pat = PATTERN (insn); 4871 rtx src = SET_SRC (pat); 4872 rtx reg = expr->reaching_reg; 4873 rtx copy; 4874 4875 /* If we've already copied it, continue. */ 4876 if (expr->reaching_reg == src) 4877 continue; 4878 4879 if (dump_file) 4880 { 4881 fprintf (dump_file, "PRE: store updated with reaching reg "); 4882 print_rtl (dump_file, expr->reaching_reg); 4883 fprintf (dump_file, ":\n "); 4884 print_inline_rtx (dump_file, insn, 8); 4885 fprintf (dump_file, "\n"); 4886 } 4887 4888 copy = gen_move_insn (reg, copy_rtx (SET_SRC (pat))); 4889 emit_insn_before (copy, insn); 4890 SET_SRC (pat) = reg; 4891 df_insn_rescan (insn); 4892 4893 /* un-recognize this pattern since it's probably different now. */ 4894 INSN_CODE (insn) = -1; 4895 gcse_create_count++; 4896 } 4897 } 4898 } 4899 4900 /* Return true if the graph is too expensive to optimize. PASS is the 4901 optimization about to be performed. */ 4902 4903 static bool 4904 is_too_expensive (const char *pass) 4905 { 4906 /* Trying to perform global optimizations on flow graphs which have 4907 a high connectivity will take a long time and is unlikely to be 4908 particularly useful. 4909 4910 In normal circumstances a cfg should have about twice as many 4911 edges as blocks. But we do not want to punish small functions 4912 which have a couple switch statements. Rather than simply 4913 threshold the number of blocks, uses something with a more 4914 graceful degradation. */ 4915 if (n_edges > 20000 + n_basic_blocks * 4) 4916 { 4917 warning (OPT_Wdisabled_optimization, 4918 "%s: %d basic blocks and %d edges/basic block", 4919 pass, n_basic_blocks, n_edges / n_basic_blocks); 4920 4921 return true; 4922 } 4923 4924 /* If allocating memory for the cprop bitmap would take up too much 4925 storage it's better just to disable the optimization. */ 4926 if ((n_basic_blocks 4927 * SBITMAP_SET_SIZE (max_reg_num ()) 4928 * sizeof (SBITMAP_ELT_TYPE)) > MAX_GCSE_MEMORY) 4929 { 4930 warning (OPT_Wdisabled_optimization, 4931 "%s: %d basic blocks and %d registers", 4932 pass, n_basic_blocks, max_reg_num ()); 4933 4934 return true; 4935 } 4936 4937 return false; 4938 } 4939 4940 4941 /* Main function for the CPROP pass. */ 4942 4943 static int 4944 one_cprop_pass (void) 4945 { 4946 int changed = 0; 4947 4948 /* Return if there's nothing to do, or it is too expensive. */ 4949 if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1 4950 || is_too_expensive (_ ("const/copy propagation disabled"))) 4951 return 0; 4952 4953 global_const_prop_count = local_const_prop_count = 0; 4954 global_copy_prop_count = local_copy_prop_count = 0; 4955 4956 bytes_used = 0; 4957 gcc_obstack_init (&gcse_obstack); 4958 alloc_gcse_mem (); 4959 4960 /* Do a local const/copy propagation pass first. The global pass 4961 only handles global opportunities. 4962 If the local pass changes something, remove any unreachable blocks 4963 because the CPROP global dataflow analysis may get into infinite 4964 loops for CFGs with unreachable blocks. 4965 4966 FIXME: This local pass should not be necessary after CSE (but for 4967 some reason it still is). It is also (proven) not necessary 4968 to run the local pass right after FWPWOP. 4969 4970 FIXME: The global analysis would not get into infinite loops if it 4971 would use the DF solver (via df_simple_dataflow) instead of 4972 the solver implemented in this file. */ 4973 if (local_cprop_pass ()) 4974 { 4975 delete_unreachable_blocks (); 4976 df_analyze (); 4977 } 4978 4979 /* Determine implicit sets. */ 4980 implicit_sets = XCNEWVEC (rtx, last_basic_block); 4981 find_implicit_sets (); 4982 4983 alloc_hash_table (&set_hash_table, 1); 4984 compute_hash_table (&set_hash_table); 4985 4986 /* Free implicit_sets before peak usage. */ 4987 free (implicit_sets); 4988 implicit_sets = NULL; 4989 4990 if (dump_file) 4991 dump_hash_table (dump_file, "SET", &set_hash_table); 4992 if (set_hash_table.n_elems > 0) 4993 { 4994 basic_block bb; 4995 rtx insn; 4996 4997 alloc_cprop_mem (last_basic_block, set_hash_table.n_elems); 4998 compute_cprop_data (); 4999 5000 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb, EXIT_BLOCK_PTR, next_bb) 5001 { 5002 /* Reset tables used to keep track of what's still valid [since 5003 the start of the block]. */ 5004 reset_opr_set_tables (); 5005 5006 FOR_BB_INSNS (bb, insn) 5007 if (INSN_P (insn)) 5008 { 5009 changed |= cprop_insn (insn); 5010 5011 /* Keep track of everything modified by this insn. */ 5012 /* ??? Need to be careful w.r.t. mods done to INSN. 5013 Don't call mark_oprs_set if we turned the 5014 insn into a NOTE. */ 5015 if (! NOTE_P (insn)) 5016 mark_oprs_set (insn); 5017 } 5018 } 5019 5020 changed |= bypass_conditional_jumps (); 5021 free_cprop_mem (); 5022 } 5023 5024 free_hash_table (&set_hash_table); 5025 free_gcse_mem (); 5026 obstack_free (&gcse_obstack, NULL); 5027 5028 if (dump_file) 5029 { 5030 fprintf (dump_file, "CPROP of %s, %d basic blocks, %d bytes needed, ", 5031 current_function_name (), n_basic_blocks, bytes_used); 5032 fprintf (dump_file, "%d local const props, %d local copy props, ", 5033 local_const_prop_count, local_copy_prop_count); 5034 fprintf (dump_file, "%d global const props, %d global copy props\n\n", 5035 global_const_prop_count, global_copy_prop_count); 5036 } 5037 5038 return changed; 5039 } 5040 5041 5042 /* All the passes implemented in this file. Each pass has its 5043 own gate and execute function, and at the end of the file a 5044 pass definition for passes.c. 5045 5046 We do not construct an accurate cfg in functions which call 5047 setjmp, so none of these passes runs if the function calls 5048 setjmp. 5049 FIXME: Should just handle setjmp via REG_SETJMP notes. */ 5050 5051 static bool 5052 gate_rtl_cprop (void) 5053 { 5054 return optimize > 0 && flag_gcse 5055 && !cfun->calls_setjmp 5056 && dbg_cnt (cprop); 5057 } 5058 5059 static unsigned int 5060 execute_rtl_cprop (void) 5061 { 5062 delete_unreachable_blocks (); 5063 df_set_flags (DF_LR_RUN_DCE); 5064 df_analyze (); 5065 flag_rerun_cse_after_global_opts |= one_cprop_pass (); 5066 return 0; 5067 } 5068 5069 static bool 5070 gate_rtl_pre (void) 5071 { 5072 return optimize > 0 && flag_gcse 5073 && !cfun->calls_setjmp 5074 && optimize_function_for_speed_p (cfun) 5075 && dbg_cnt (pre); 5076 } 5077 5078 static unsigned int 5079 execute_rtl_pre (void) 5080 { 5081 delete_unreachable_blocks (); 5082 df_analyze (); 5083 flag_rerun_cse_after_global_opts |= one_pre_gcse_pass (); 5084 return 0; 5085 } 5086 5087 static bool 5088 gate_rtl_hoist (void) 5089 { 5090 return optimize > 0 && flag_gcse 5091 && !cfun->calls_setjmp 5092 /* It does not make sense to run code hoisting unless we are optimizing 5093 for code size -- it rarely makes programs faster, and can make then 5094 bigger if we did PRE (when optimizing for space, we don't run PRE). */ 5095 && optimize_function_for_size_p (cfun) 5096 && dbg_cnt (hoist); 5097 } 5098 5099 static unsigned int 5100 execute_rtl_hoist (void) 5101 { 5102 delete_unreachable_blocks (); 5103 df_analyze (); 5104 flag_rerun_cse_after_global_opts |= one_code_hoisting_pass (); 5105 return 0; 5106 } 5107 5108 struct rtl_opt_pass pass_rtl_cprop = 5109 { 5110 { 5111 RTL_PASS, 5112 "cprop", /* name */ 5113 gate_rtl_cprop, /* gate */ 5114 execute_rtl_cprop, /* execute */ 5115 NULL, /* sub */ 5116 NULL, /* next */ 5117 0, /* static_pass_number */ 5118 TV_CPROP, /* tv_id */ 5119 PROP_cfglayout, /* properties_required */ 5120 0, /* properties_provided */ 5121 0, /* properties_destroyed */ 5122 0, /* todo_flags_start */ 5123 TODO_df_finish | TODO_verify_rtl_sharing | 5124 TODO_dump_func | 5125 TODO_verify_flow | TODO_ggc_collect /* todo_flags_finish */ 5126 } 5127 }; 5128 5129 struct rtl_opt_pass pass_rtl_pre = 5130 { 5131 { 5132 RTL_PASS, 5133 "rtl pre", /* name */ 5134 gate_rtl_pre, /* gate */ 5135 execute_rtl_pre, /* execute */ 5136 NULL, /* sub */ 5137 NULL, /* next */ 5138 0, /* static_pass_number */ 5139 TV_PRE, /* tv_id */ 5140 PROP_cfglayout, /* properties_required */ 5141 0, /* properties_provided */ 5142 0, /* properties_destroyed */ 5143 0, /* todo_flags_start */ 5144 TODO_df_finish | TODO_verify_rtl_sharing | 5145 TODO_dump_func | 5146 TODO_verify_flow | TODO_ggc_collect /* todo_flags_finish */ 5147 } 5148 }; 5149 5150 struct rtl_opt_pass pass_rtl_hoist = 5151 { 5152 { 5153 RTL_PASS, 5154 "hoist", /* name */ 5155 gate_rtl_hoist, /* gate */ 5156 execute_rtl_hoist, /* execute */ 5157 NULL, /* sub */ 5158 NULL, /* next */ 5159 0, /* static_pass_number */ 5160 TV_HOIST, /* tv_id */ 5161 PROP_cfglayout, /* properties_required */ 5162 0, /* properties_provided */ 5163 0, /* properties_destroyed */ 5164 0, /* todo_flags_start */ 5165 TODO_df_finish | TODO_verify_rtl_sharing | 5166 TODO_dump_func | 5167 TODO_verify_flow | TODO_ggc_collect /* todo_flags_finish */ 5168 } 5169 }; 5170 5171 #include "gt-gcse.h" 5172