1 /* Partial redundancy elimination / Hoisting for RTL. 2 Copyright (C) 1997-2015 Free Software Foundation, Inc. 3 4 This file is part of GCC. 5 6 GCC is free software; you can redistribute it and/or modify it under 7 the terms of the GNU General Public License as published by the Free 8 Software Foundation; either version 3, or (at your option) any later 9 version. 10 11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12 WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with GCC; see the file COPYING3. If not see 18 <http://www.gnu.org/licenses/>. */ 19 20 /* TODO 21 - reordering of memory allocation and freeing to be more space efficient 22 - calc rough register pressure information and use the info to drive all 23 kinds of code motion (including code hoisting) in a unified way. 24 */ 25 26 /* References searched while implementing this. 27 28 Compilers Principles, Techniques and Tools 29 Aho, Sethi, Ullman 30 Addison-Wesley, 1988 31 32 Global Optimization by Suppression of Partial Redundancies 33 E. Morel, C. Renvoise 34 communications of the acm, Vol. 22, Num. 2, Feb. 1979 35 36 A Portable Machine-Independent Global Optimizer - Design and Measurements 37 Frederick Chow 38 Stanford Ph.D. thesis, Dec. 1983 39 40 A Fast Algorithm for Code Movement Optimization 41 D.M. Dhamdhere 42 SIGPLAN Notices, Vol. 23, Num. 10, Oct. 1988 43 44 A Solution to a Problem with Morel and Renvoise's 45 Global Optimization by Suppression of Partial Redundancies 46 K-H Drechsler, M.P. Stadel 47 ACM TOPLAS, Vol. 10, Num. 4, Oct. 1988 48 49 Practical Adaptation of the Global Optimization 50 Algorithm of Morel and Renvoise 51 D.M. Dhamdhere 52 ACM TOPLAS, Vol. 13, Num. 2. Apr. 1991 53 54 Efficiently Computing Static Single Assignment Form and the Control 55 Dependence Graph 56 R. Cytron, J. Ferrante, B.K. Rosen, M.N. Wegman, and F.K. Zadeck 57 ACM TOPLAS, Vol. 13, Num. 4, Oct. 1991 58 59 Lazy Code Motion 60 J. Knoop, O. Ruthing, B. Steffen 61 ACM SIGPLAN Notices Vol. 27, Num. 7, Jul. 1992, '92 Conference on PLDI 62 63 What's In a Region? Or Computing Control Dependence Regions in Near-Linear 64 Time for Reducible Flow Control 65 Thomas Ball 66 ACM Letters on Programming Languages and Systems, 67 Vol. 2, Num. 1-4, Mar-Dec 1993 68 69 An Efficient Representation for Sparse Sets 70 Preston Briggs, Linda Torczon 71 ACM Letters on Programming Languages and Systems, 72 Vol. 2, Num. 1-4, Mar-Dec 1993 73 74 A Variation of Knoop, Ruthing, and Steffen's Lazy Code Motion 75 K-H Drechsler, M.P. Stadel 76 ACM SIGPLAN Notices, Vol. 28, Num. 5, May 1993 77 78 Partial Dead Code Elimination 79 J. Knoop, O. Ruthing, B. Steffen 80 ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994 81 82 Effective Partial Redundancy Elimination 83 P. Briggs, K.D. Cooper 84 ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994 85 86 The Program Structure Tree: Computing Control Regions in Linear Time 87 R. Johnson, D. Pearson, K. Pingali 88 ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994 89 90 Optimal Code Motion: Theory and Practice 91 J. Knoop, O. Ruthing, B. Steffen 92 ACM TOPLAS, Vol. 16, Num. 4, Jul. 1994 93 94 The power of assignment motion 95 J. Knoop, O. Ruthing, B. Steffen 96 ACM SIGPLAN Notices Vol. 30, Num. 6, Jun. 1995, '95 Conference on PLDI 97 98 Global code motion / global value numbering 99 C. Click 100 ACM SIGPLAN Notices Vol. 30, Num. 6, Jun. 1995, '95 Conference on PLDI 101 102 Value Driven Redundancy Elimination 103 L.T. Simpson 104 Rice University Ph.D. thesis, Apr. 1996 105 106 Value Numbering 107 L.T. Simpson 108 Massively Scalar Compiler Project, Rice University, Sep. 1996 109 110 High Performance Compilers for Parallel Computing 111 Michael Wolfe 112 Addison-Wesley, 1996 113 114 Advanced Compiler Design and Implementation 115 Steven Muchnick 116 Morgan Kaufmann, 1997 117 118 Building an Optimizing Compiler 119 Robert Morgan 120 Digital Press, 1998 121 122 People wishing to speed up the code here should read: 123 Elimination Algorithms for Data Flow Analysis 124 B.G. Ryder, M.C. Paull 125 ACM Computing Surveys, Vol. 18, Num. 3, Sep. 1986 126 127 How to Analyze Large Programs Efficiently and Informatively 128 D.M. Dhamdhere, B.K. Rosen, F.K. Zadeck 129 ACM SIGPLAN Notices Vol. 27, Num. 7, Jul. 1992, '92 Conference on PLDI 130 131 People wishing to do something different can find various possibilities 132 in the above papers and elsewhere. 133 */ 134 135 #include "config.h" 136 #include "system.h" 137 #include "coretypes.h" 138 #include "tm.h" 139 #include "diagnostic-core.h" 140 #include "toplev.h" 141 #include "hard-reg-set.h" 142 #include "rtl.h" 143 #include "hash-set.h" 144 #include "machmode.h" 145 #include "vec.h" 146 #include "double-int.h" 147 #include "input.h" 148 #include "alias.h" 149 #include "symtab.h" 150 #include "wide-int.h" 151 #include "inchash.h" 152 #include "tree.h" 153 #include "tm_p.h" 154 #include "regs.h" 155 #include "ira.h" 156 #include "flags.h" 157 #include "insn-config.h" 158 #include "recog.h" 159 #include "predict.h" 160 #include "function.h" 161 #include "dominance.h" 162 #include "cfg.h" 163 #include "cfgrtl.h" 164 #include "cfganal.h" 165 #include "lcm.h" 166 #include "cfgcleanup.h" 167 #include "basic-block.h" 168 #include "hashtab.h" 169 #include "statistics.h" 170 #include "real.h" 171 #include "fixed-value.h" 172 #include "expmed.h" 173 #include "dojump.h" 174 #include "explow.h" 175 #include "calls.h" 176 #include "emit-rtl.h" 177 #include "varasm.h" 178 #include "stmt.h" 179 #include "expr.h" 180 #include "except.h" 181 #include "ggc.h" 182 #include "params.h" 183 #include "cselib.h" 184 #include "intl.h" 185 #include "obstack.h" 186 #include "tree-pass.h" 187 #include "hash-table.h" 188 #include "df.h" 189 #include "dbgcnt.h" 190 #include "target.h" 191 #include "gcse.h" 192 #include "gcse-common.h" 193 194 /* We support GCSE via Partial Redundancy Elimination. PRE optimizations 195 are a superset of those done by classic GCSE. 196 197 Two passes of copy/constant propagation are done around PRE or hoisting 198 because the first one enables more GCSE and the second one helps to clean 199 up the copies that PRE and HOIST create. This is needed more for PRE than 200 for HOIST because code hoisting will try to use an existing register 201 containing the common subexpression rather than create a new one. This is 202 harder to do for PRE because of the code motion (which HOIST doesn't do). 203 204 Expressions we are interested in GCSE-ing are of the form 205 (set (pseudo-reg) (expression)). 206 Function want_to_gcse_p says what these are. 207 208 In addition, expressions in REG_EQUAL notes are candidates for GCSE-ing. 209 This allows PRE to hoist expressions that are expressed in multiple insns, 210 such as complex address calculations (e.g. for PIC code, or loads with a 211 high part and a low part). 212 213 PRE handles moving invariant expressions out of loops (by treating them as 214 partially redundant). 215 216 ********************** 217 218 We used to support multiple passes but there are diminishing returns in 219 doing so. The first pass usually makes 90% of the changes that are doable. 220 A second pass can make a few more changes made possible by the first pass. 221 Experiments show any further passes don't make enough changes to justify 222 the expense. 223 224 A study of spec92 using an unlimited number of passes: 225 [1 pass] = 1208 substitutions, [2] = 577, [3] = 202, [4] = 192, [5] = 83, 226 [6] = 34, [7] = 17, [8] = 9, [9] = 4, [10] = 4, [11] = 2, 227 [12] = 2, [13] = 1, [15] = 1, [16] = 2, [41] = 1 228 229 It was found doing copy propagation between each pass enables further 230 substitutions. 231 232 This study was done before expressions in REG_EQUAL notes were added as 233 candidate expressions for optimization, and before the GIMPLE optimizers 234 were added. Probably, multiple passes is even less efficient now than 235 at the time when the study was conducted. 236 237 PRE is quite expensive in complicated functions because the DFA can take 238 a while to converge. Hence we only perform one pass. 239 240 ********************** 241 242 The steps for PRE are: 243 244 1) Build the hash table of expressions we wish to GCSE (expr_hash_table). 245 246 2) Perform the data flow analysis for PRE. 247 248 3) Delete the redundant instructions 249 250 4) Insert the required copies [if any] that make the partially 251 redundant instructions fully redundant. 252 253 5) For other reaching expressions, insert an instruction to copy the value 254 to a newly created pseudo that will reach the redundant instruction. 255 256 The deletion is done first so that when we do insertions we 257 know which pseudo reg to use. 258 259 Various papers have argued that PRE DFA is expensive (O(n^2)) and others 260 argue it is not. The number of iterations for the algorithm to converge 261 is typically 2-4 so I don't view it as that expensive (relatively speaking). 262 263 PRE GCSE depends heavily on the second CPROP pass to clean up the copies 264 we create. To make an expression reach the place where it's redundant, 265 the result of the expression is copied to a new register, and the redundant 266 expression is deleted by replacing it with this new register. Classic GCSE 267 doesn't have this problem as much as it computes the reaching defs of 268 each register in each block and thus can try to use an existing 269 register. */ 270 271 /* GCSE global vars. */ 272 273 struct target_gcse default_target_gcse; 274 #if SWITCHABLE_TARGET 275 struct target_gcse *this_target_gcse = &default_target_gcse; 276 #endif 277 278 /* Set to non-zero if CSE should run after all GCSE optimizations are done. */ 279 int flag_rerun_cse_after_global_opts; 280 281 /* An obstack for our working variables. */ 282 static struct obstack gcse_obstack; 283 284 /* Hash table of expressions. */ 285 286 struct gcse_expr 287 { 288 /* The expression. */ 289 rtx expr; 290 /* Index in the available expression bitmaps. */ 291 int bitmap_index; 292 /* Next entry with the same hash. */ 293 struct gcse_expr *next_same_hash; 294 /* List of anticipatable occurrences in basic blocks in the function. 295 An "anticipatable occurrence" is one that is the first occurrence in the 296 basic block, the operands are not modified in the basic block prior 297 to the occurrence and the output is not used between the start of 298 the block and the occurrence. */ 299 struct gcse_occr *antic_occr; 300 /* List of available occurrence in basic blocks in the function. 301 An "available occurrence" is one that is the last occurrence in the 302 basic block and the operands are not modified by following statements in 303 the basic block [including this insn]. */ 304 struct gcse_occr *avail_occr; 305 /* Non-null if the computation is PRE redundant. 306 The value is the newly created pseudo-reg to record a copy of the 307 expression in all the places that reach the redundant copy. */ 308 rtx reaching_reg; 309 /* Maximum distance in instructions this expression can travel. 310 We avoid moving simple expressions for more than a few instructions 311 to keep register pressure under control. 312 A value of "0" removes restrictions on how far the expression can 313 travel. */ 314 HOST_WIDE_INT max_distance; 315 }; 316 317 /* Occurrence of an expression. 318 There is one per basic block. If a pattern appears more than once the 319 last appearance is used [or first for anticipatable expressions]. */ 320 321 struct gcse_occr 322 { 323 /* Next occurrence of this expression. */ 324 struct gcse_occr *next; 325 /* The insn that computes the expression. */ 326 rtx_insn *insn; 327 /* Nonzero if this [anticipatable] occurrence has been deleted. */ 328 char deleted_p; 329 /* Nonzero if this [available] occurrence has been copied to 330 reaching_reg. */ 331 /* ??? This is mutually exclusive with deleted_p, so they could share 332 the same byte. */ 333 char copied_p; 334 }; 335 336 typedef struct gcse_occr *occr_t; 337 338 /* Expression hash tables. 339 Each hash table is an array of buckets. 340 ??? It is known that if it were an array of entries, structure elements 341 `next_same_hash' and `bitmap_index' wouldn't be necessary. However, it is 342 not clear whether in the final analysis a sufficient amount of memory would 343 be saved as the size of the available expression bitmaps would be larger 344 [one could build a mapping table without holes afterwards though]. 345 Someday I'll perform the computation and figure it out. */ 346 347 struct gcse_hash_table_d 348 { 349 /* The table itself. 350 This is an array of `expr_hash_table_size' elements. */ 351 struct gcse_expr **table; 352 353 /* Size of the hash table, in elements. */ 354 unsigned int size; 355 356 /* Number of hash table elements. */ 357 unsigned int n_elems; 358 }; 359 360 /* Expression hash table. */ 361 static struct gcse_hash_table_d expr_hash_table; 362 363 /* This is a list of expressions which are MEMs and will be used by load 364 or store motion. 365 Load motion tracks MEMs which aren't killed by anything except itself, 366 i.e. loads and stores to a single location. 367 We can then allow movement of these MEM refs with a little special 368 allowance. (all stores copy the same value to the reaching reg used 369 for the loads). This means all values used to store into memory must have 370 no side effects so we can re-issue the setter value. */ 371 372 struct ls_expr 373 { 374 struct gcse_expr * expr; /* Gcse expression reference for LM. */ 375 rtx pattern; /* Pattern of this mem. */ 376 rtx pattern_regs; /* List of registers mentioned by the mem. */ 377 rtx_insn_list *loads; /* INSN list of loads seen. */ 378 rtx_insn_list *stores; /* INSN list of stores seen. */ 379 struct ls_expr * next; /* Next in the list. */ 380 int invalid; /* Invalid for some reason. */ 381 int index; /* If it maps to a bitmap index. */ 382 unsigned int hash_index; /* Index when in a hash table. */ 383 rtx reaching_reg; /* Register to use when re-writing. */ 384 }; 385 386 /* Head of the list of load/store memory refs. */ 387 static struct ls_expr * pre_ldst_mems = NULL; 388 389 struct pre_ldst_expr_hasher : typed_noop_remove <ls_expr> 390 { 391 typedef ls_expr value_type; 392 typedef value_type compare_type; 393 static inline hashval_t hash (const value_type *); 394 static inline bool equal (const value_type *, const compare_type *); 395 }; 396 397 /* Hashtable helpers. */ 398 inline hashval_t 399 pre_ldst_expr_hasher::hash (const value_type *x) 400 { 401 int do_not_record_p = 0; 402 return 403 hash_rtx (x->pattern, GET_MODE (x->pattern), &do_not_record_p, NULL, false); 404 } 405 406 static int expr_equiv_p (const_rtx, const_rtx); 407 408 inline bool 409 pre_ldst_expr_hasher::equal (const value_type *ptr1, 410 const compare_type *ptr2) 411 { 412 return expr_equiv_p (ptr1->pattern, ptr2->pattern); 413 } 414 415 /* Hashtable for the load/store memory refs. */ 416 static hash_table<pre_ldst_expr_hasher> *pre_ldst_table; 417 418 /* Bitmap containing one bit for each register in the program. 419 Used when performing GCSE to track which registers have been set since 420 the start of the basic block. */ 421 static regset reg_set_bitmap; 422 423 /* Array, indexed by basic block number for a list of insns which modify 424 memory within that block. */ 425 static vec<rtx_insn *> *modify_mem_list; 426 static bitmap modify_mem_list_set; 427 428 /* This array parallels modify_mem_list, except that it stores MEMs 429 being set and their canonicalized memory addresses. */ 430 static vec<modify_pair> *canon_modify_mem_list; 431 432 /* Bitmap indexed by block numbers to record which blocks contain 433 function calls. */ 434 static bitmap blocks_with_calls; 435 436 /* Various variables for statistics gathering. */ 437 438 /* Memory used in a pass. 439 This isn't intended to be absolutely precise. Its intent is only 440 to keep an eye on memory usage. */ 441 static int bytes_used; 442 443 /* GCSE substitutions made. */ 444 static int gcse_subst_count; 445 /* Number of copy instructions created. */ 446 static int gcse_create_count; 447 448 /* Doing code hoisting. */ 449 static bool doing_code_hoisting_p = false; 450 451 /* For available exprs */ 452 static sbitmap *ae_kill; 453 454 /* Data stored for each basic block. */ 455 struct bb_data 456 { 457 /* Maximal register pressure inside basic block for given register class 458 (defined only for the pressure classes). */ 459 int max_reg_pressure[N_REG_CLASSES]; 460 /* Recorded register pressure of basic block before trying to hoist 461 an expression. Will be used to restore the register pressure 462 if the expression should not be hoisted. */ 463 int old_pressure; 464 /* Recorded register live_in info of basic block during code hoisting 465 process. BACKUP is used to record live_in info before trying to 466 hoist an expression, and will be used to restore LIVE_IN if the 467 expression should not be hoisted. */ 468 bitmap live_in, backup; 469 }; 470 471 #define BB_DATA(bb) ((struct bb_data *) (bb)->aux) 472 473 static basic_block curr_bb; 474 475 /* Current register pressure for each pressure class. */ 476 static int curr_reg_pressure[N_REG_CLASSES]; 477 478 479 static void compute_can_copy (void); 480 static void *gmalloc (size_t) ATTRIBUTE_MALLOC; 481 static void *gcalloc (size_t, size_t) ATTRIBUTE_MALLOC; 482 static void *gcse_alloc (unsigned long); 483 static void alloc_gcse_mem (void); 484 static void free_gcse_mem (void); 485 static void hash_scan_insn (rtx_insn *, struct gcse_hash_table_d *); 486 static void hash_scan_set (rtx, rtx_insn *, struct gcse_hash_table_d *); 487 static void hash_scan_clobber (rtx, rtx_insn *, struct gcse_hash_table_d *); 488 static void hash_scan_call (rtx, rtx_insn *, struct gcse_hash_table_d *); 489 static int want_to_gcse_p (rtx, HOST_WIDE_INT *); 490 static int oprs_unchanged_p (const_rtx, const rtx_insn *, int); 491 static int oprs_anticipatable_p (const_rtx, const rtx_insn *); 492 static int oprs_available_p (const_rtx, const rtx_insn *); 493 static void insert_expr_in_table (rtx, machine_mode, rtx_insn *, int, int, 494 HOST_WIDE_INT, struct gcse_hash_table_d *); 495 static unsigned int hash_expr (const_rtx, machine_mode, int *, int); 496 static void record_last_reg_set_info (rtx, int); 497 static void record_last_mem_set_info (rtx_insn *); 498 static void record_last_set_info (rtx, const_rtx, void *); 499 static void compute_hash_table (struct gcse_hash_table_d *); 500 static void alloc_hash_table (struct gcse_hash_table_d *); 501 static void free_hash_table (struct gcse_hash_table_d *); 502 static void compute_hash_table_work (struct gcse_hash_table_d *); 503 static void dump_hash_table (FILE *, const char *, struct gcse_hash_table_d *); 504 static void compute_local_properties (sbitmap *, sbitmap *, sbitmap *, 505 struct gcse_hash_table_d *); 506 static void mems_conflict_for_gcse_p (rtx, const_rtx, void *); 507 static int load_killed_in_block_p (const_basic_block, int, const_rtx, int); 508 static void alloc_pre_mem (int, int); 509 static void free_pre_mem (void); 510 static struct edge_list *compute_pre_data (void); 511 static int pre_expr_reaches_here_p (basic_block, struct gcse_expr *, 512 basic_block); 513 static void insert_insn_end_basic_block (struct gcse_expr *, basic_block); 514 static void pre_insert_copy_insn (struct gcse_expr *, rtx_insn *); 515 static void pre_insert_copies (void); 516 static int pre_delete (void); 517 static int pre_gcse (struct edge_list *); 518 static int one_pre_gcse_pass (void); 519 static void add_label_notes (rtx, rtx); 520 static void alloc_code_hoist_mem (int, int); 521 static void free_code_hoist_mem (void); 522 static void compute_code_hoist_vbeinout (void); 523 static void compute_code_hoist_data (void); 524 static int should_hoist_expr_to_dom (basic_block, struct gcse_expr *, 525 basic_block, 526 sbitmap, HOST_WIDE_INT, int *, 527 enum reg_class, 528 int *, bitmap, rtx_insn *); 529 static int hoist_code (void); 530 static enum reg_class get_regno_pressure_class (int regno, int *nregs); 531 static enum reg_class get_pressure_class_and_nregs (rtx_insn *insn, int *nregs); 532 static int one_code_hoisting_pass (void); 533 static rtx_insn *process_insert_insn (struct gcse_expr *); 534 static int pre_edge_insert (struct edge_list *, struct gcse_expr **); 535 static int pre_expr_reaches_here_p_work (basic_block, struct gcse_expr *, 536 basic_block, char *); 537 static struct ls_expr * ldst_entry (rtx); 538 static void free_ldst_entry (struct ls_expr *); 539 static void free_ld_motion_mems (void); 540 static void print_ldst_list (FILE *); 541 static struct ls_expr * find_rtx_in_ldst (rtx); 542 static int simple_mem (const_rtx); 543 static void invalidate_any_buried_refs (rtx); 544 static void compute_ld_motion_mems (void); 545 static void trim_ld_motion_mems (void); 546 static void update_ld_motion_stores (struct gcse_expr *); 547 static void clear_modify_mem_tables (void); 548 static void free_modify_mem_tables (void); 549 static rtx gcse_emit_move_after (rtx, rtx, rtx_insn *); 550 static bool is_too_expensive (const char *); 551 552 #define GNEW(T) ((T *) gmalloc (sizeof (T))) 553 #define GCNEW(T) ((T *) gcalloc (1, sizeof (T))) 554 555 #define GNEWVEC(T, N) ((T *) gmalloc (sizeof (T) * (N))) 556 #define GCNEWVEC(T, N) ((T *) gcalloc ((N), sizeof (T))) 557 558 #define GNEWVAR(T, S) ((T *) gmalloc ((S))) 559 #define GCNEWVAR(T, S) ((T *) gcalloc (1, (S))) 560 561 #define GOBNEW(T) ((T *) gcse_alloc (sizeof (T))) 562 #define GOBNEWVAR(T, S) ((T *) gcse_alloc ((S))) 563 564 /* Misc. utilities. */ 565 566 #define can_copy \ 567 (this_target_gcse->x_can_copy) 568 #define can_copy_init_p \ 569 (this_target_gcse->x_can_copy_init_p) 570 571 /* Compute which modes support reg/reg copy operations. */ 572 573 static void 574 compute_can_copy (void) 575 { 576 int i; 577 #ifndef AVOID_CCMODE_COPIES 578 rtx reg, insn; 579 #endif 580 memset (can_copy, 0, NUM_MACHINE_MODES); 581 582 start_sequence (); 583 for (i = 0; i < NUM_MACHINE_MODES; i++) 584 if (GET_MODE_CLASS (i) == MODE_CC) 585 { 586 #ifdef AVOID_CCMODE_COPIES 587 can_copy[i] = 0; 588 #else 589 reg = gen_rtx_REG ((machine_mode) i, LAST_VIRTUAL_REGISTER + 1); 590 insn = emit_insn (gen_rtx_SET (VOIDmode, reg, reg)); 591 if (recog (PATTERN (insn), insn, NULL) >= 0) 592 can_copy[i] = 1; 593 #endif 594 } 595 else 596 can_copy[i] = 1; 597 598 end_sequence (); 599 } 600 601 /* Returns whether the mode supports reg/reg copy operations. */ 602 603 bool 604 can_copy_p (machine_mode mode) 605 { 606 if (! can_copy_init_p) 607 { 608 compute_can_copy (); 609 can_copy_init_p = true; 610 } 611 612 return can_copy[mode] != 0; 613 } 614 615 /* Cover function to xmalloc to record bytes allocated. */ 616 617 static void * 618 gmalloc (size_t size) 619 { 620 bytes_used += size; 621 return xmalloc (size); 622 } 623 624 /* Cover function to xcalloc to record bytes allocated. */ 625 626 static void * 627 gcalloc (size_t nelem, size_t elsize) 628 { 629 bytes_used += nelem * elsize; 630 return xcalloc (nelem, elsize); 631 } 632 633 /* Cover function to obstack_alloc. */ 634 635 static void * 636 gcse_alloc (unsigned long size) 637 { 638 bytes_used += size; 639 return obstack_alloc (&gcse_obstack, size); 640 } 641 642 /* Allocate memory for the reg/memory set tracking tables. 643 This is called at the start of each pass. */ 644 645 static void 646 alloc_gcse_mem (void) 647 { 648 /* Allocate vars to track sets of regs. */ 649 reg_set_bitmap = ALLOC_REG_SET (NULL); 650 651 /* Allocate array to keep a list of insns which modify memory in each 652 basic block. The two typedefs are needed to work around the 653 pre-processor limitation with template types in macro arguments. */ 654 typedef vec<rtx_insn *> vec_rtx_heap; 655 typedef vec<modify_pair> vec_modify_pair_heap; 656 modify_mem_list = GCNEWVEC (vec_rtx_heap, last_basic_block_for_fn (cfun)); 657 canon_modify_mem_list = GCNEWVEC (vec_modify_pair_heap, 658 last_basic_block_for_fn (cfun)); 659 modify_mem_list_set = BITMAP_ALLOC (NULL); 660 blocks_with_calls = BITMAP_ALLOC (NULL); 661 } 662 663 /* Free memory allocated by alloc_gcse_mem. */ 664 665 static void 666 free_gcse_mem (void) 667 { 668 FREE_REG_SET (reg_set_bitmap); 669 670 free_modify_mem_tables (); 671 BITMAP_FREE (modify_mem_list_set); 672 BITMAP_FREE (blocks_with_calls); 673 } 674 675 /* Compute the local properties of each recorded expression. 676 677 Local properties are those that are defined by the block, irrespective of 678 other blocks. 679 680 An expression is transparent in a block if its operands are not modified 681 in the block. 682 683 An expression is computed (locally available) in a block if it is computed 684 at least once and expression would contain the same value if the 685 computation was moved to the end of the block. 686 687 An expression is locally anticipatable in a block if it is computed at 688 least once and expression would contain the same value if the computation 689 was moved to the beginning of the block. 690 691 We call this routine for pre and code hoisting. They all compute 692 basically the same information and thus can easily share this code. 693 694 TRANSP, COMP, and ANTLOC are destination sbitmaps for recording local 695 properties. If NULL, then it is not necessary to compute or record that 696 particular property. 697 698 TABLE controls which hash table to look at. */ 699 700 static void 701 compute_local_properties (sbitmap *transp, sbitmap *comp, sbitmap *antloc, 702 struct gcse_hash_table_d *table) 703 { 704 unsigned int i; 705 706 /* Initialize any bitmaps that were passed in. */ 707 if (transp) 708 { 709 bitmap_vector_ones (transp, last_basic_block_for_fn (cfun)); 710 } 711 712 if (comp) 713 bitmap_vector_clear (comp, last_basic_block_for_fn (cfun)); 714 if (antloc) 715 bitmap_vector_clear (antloc, last_basic_block_for_fn (cfun)); 716 717 for (i = 0; i < table->size; i++) 718 { 719 struct gcse_expr *expr; 720 721 for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash) 722 { 723 int indx = expr->bitmap_index; 724 struct gcse_occr *occr; 725 726 /* The expression is transparent in this block if it is not killed. 727 We start by assuming all are transparent [none are killed], and 728 then reset the bits for those that are. */ 729 if (transp) 730 compute_transp (expr->expr, indx, transp, 731 blocks_with_calls, 732 modify_mem_list_set, 733 canon_modify_mem_list); 734 735 /* The occurrences recorded in antic_occr are exactly those that 736 we want to set to nonzero in ANTLOC. */ 737 if (antloc) 738 for (occr = expr->antic_occr; occr != NULL; occr = occr->next) 739 { 740 bitmap_set_bit (antloc[BLOCK_FOR_INSN (occr->insn)->index], indx); 741 742 /* While we're scanning the table, this is a good place to 743 initialize this. */ 744 occr->deleted_p = 0; 745 } 746 747 /* The occurrences recorded in avail_occr are exactly those that 748 we want to set to nonzero in COMP. */ 749 if (comp) 750 for (occr = expr->avail_occr; occr != NULL; occr = occr->next) 751 { 752 bitmap_set_bit (comp[BLOCK_FOR_INSN (occr->insn)->index], indx); 753 754 /* While we're scanning the table, this is a good place to 755 initialize this. */ 756 occr->copied_p = 0; 757 } 758 759 /* While we're scanning the table, this is a good place to 760 initialize this. */ 761 expr->reaching_reg = 0; 762 } 763 } 764 } 765 766 /* Hash table support. */ 767 768 struct reg_avail_info 769 { 770 basic_block last_bb; 771 int first_set; 772 int last_set; 773 }; 774 775 static struct reg_avail_info *reg_avail_info; 776 static basic_block current_bb; 777 778 /* See whether X, the source of a set, is something we want to consider for 779 GCSE. */ 780 781 static int 782 want_to_gcse_p (rtx x, HOST_WIDE_INT *max_distance_ptr) 783 { 784 #ifdef STACK_REGS 785 /* On register stack architectures, don't GCSE constants from the 786 constant pool, as the benefits are often swamped by the overhead 787 of shuffling the register stack between basic blocks. */ 788 if (IS_STACK_MODE (GET_MODE (x))) 789 x = avoid_constant_pool_reference (x); 790 #endif 791 792 /* GCSE'ing constants: 793 794 We do not specifically distinguish between constant and non-constant 795 expressions in PRE and Hoist. We use set_src_cost below to limit 796 the maximum distance simple expressions can travel. 797 798 Nevertheless, constants are much easier to GCSE, and, hence, 799 it is easy to overdo the optimizations. Usually, excessive PRE and 800 Hoisting of constant leads to increased register pressure. 801 802 RA can deal with this by rematerialing some of the constants. 803 Therefore, it is important that the back-end generates sets of constants 804 in a way that allows reload rematerialize them under high register 805 pressure, i.e., a pseudo register with REG_EQUAL to constant 806 is set only once. Failing to do so will result in IRA/reload 807 spilling such constants under high register pressure instead of 808 rematerializing them. */ 809 810 switch (GET_CODE (x)) 811 { 812 case REG: 813 case SUBREG: 814 case CALL: 815 return 0; 816 817 CASE_CONST_ANY: 818 if (!doing_code_hoisting_p) 819 /* Do not PRE constants. */ 820 return 0; 821 822 /* FALLTHRU */ 823 824 default: 825 if (doing_code_hoisting_p) 826 /* PRE doesn't implement max_distance restriction. */ 827 { 828 int cost; 829 HOST_WIDE_INT max_distance; 830 831 gcc_assert (!optimize_function_for_speed_p (cfun) 832 && optimize_function_for_size_p (cfun)); 833 cost = set_src_cost (x, 0); 834 835 if (cost < COSTS_N_INSNS (GCSE_UNRESTRICTED_COST)) 836 { 837 max_distance 838 = ((HOST_WIDE_INT)GCSE_COST_DISTANCE_RATIO * cost) / 10; 839 if (max_distance == 0) 840 return 0; 841 842 gcc_assert (max_distance > 0); 843 } 844 else 845 max_distance = 0; 846 847 if (max_distance_ptr) 848 *max_distance_ptr = max_distance; 849 } 850 851 return can_assign_to_reg_without_clobbers_p (x); 852 } 853 } 854 855 /* Used internally by can_assign_to_reg_without_clobbers_p. */ 856 857 static GTY(()) rtx_insn *test_insn; 858 859 /* Return true if we can assign X to a pseudo register such that the 860 resulting insn does not result in clobbering a hard register as a 861 side-effect. 862 863 Additionally, if the target requires it, check that the resulting insn 864 can be copied. If it cannot, this means that X is special and probably 865 has hidden side-effects we don't want to mess with. 866 867 This function is typically used by code motion passes, to verify 868 that it is safe to insert an insn without worrying about clobbering 869 maybe live hard regs. */ 870 871 bool 872 can_assign_to_reg_without_clobbers_p (rtx x) 873 { 874 int num_clobbers = 0; 875 int icode; 876 bool can_assign = false; 877 878 /* If this is a valid operand, we are OK. If it's VOIDmode, we aren't. */ 879 if (general_operand (x, GET_MODE (x))) 880 return 1; 881 else if (GET_MODE (x) == VOIDmode) 882 return 0; 883 884 /* Otherwise, check if we can make a valid insn from it. First initialize 885 our test insn if we haven't already. */ 886 if (test_insn == 0) 887 { 888 test_insn 889 = make_insn_raw (gen_rtx_SET (VOIDmode, 890 gen_rtx_REG (word_mode, 891 FIRST_PSEUDO_REGISTER * 2), 892 const0_rtx)); 893 SET_NEXT_INSN (test_insn) = SET_PREV_INSN (test_insn) = 0; 894 INSN_LOCATION (test_insn) = UNKNOWN_LOCATION; 895 } 896 897 /* Now make an insn like the one we would make when GCSE'ing and see if 898 valid. */ 899 PUT_MODE (SET_DEST (PATTERN (test_insn)), GET_MODE (x)); 900 SET_SRC (PATTERN (test_insn)) = x; 901 902 icode = recog (PATTERN (test_insn), test_insn, &num_clobbers); 903 904 /* If the test insn is valid and doesn't need clobbers, and the target also 905 has no objections, we're good. */ 906 if (icode >= 0 907 && (num_clobbers == 0 || !added_clobbers_hard_reg_p (icode)) 908 && ! (targetm.cannot_copy_insn_p 909 && targetm.cannot_copy_insn_p (test_insn))) 910 can_assign = true; 911 912 /* Make sure test_insn doesn't have any pointers into GC space. */ 913 SET_SRC (PATTERN (test_insn)) = NULL_RTX; 914 915 return can_assign; 916 } 917 918 /* Return nonzero if the operands of expression X are unchanged from the 919 start of INSN's basic block up to but not including INSN (if AVAIL_P == 0), 920 or from INSN to the end of INSN's basic block (if AVAIL_P != 0). */ 921 922 static int 923 oprs_unchanged_p (const_rtx x, const rtx_insn *insn, int avail_p) 924 { 925 int i, j; 926 enum rtx_code code; 927 const char *fmt; 928 929 if (x == 0) 930 return 1; 931 932 code = GET_CODE (x); 933 switch (code) 934 { 935 case REG: 936 { 937 struct reg_avail_info *info = ®_avail_info[REGNO (x)]; 938 939 if (info->last_bb != current_bb) 940 return 1; 941 if (avail_p) 942 return info->last_set < DF_INSN_LUID (insn); 943 else 944 return info->first_set >= DF_INSN_LUID (insn); 945 } 946 947 case MEM: 948 if (! flag_gcse_lm 949 || load_killed_in_block_p (current_bb, DF_INSN_LUID (insn), 950 x, avail_p)) 951 return 0; 952 else 953 return oprs_unchanged_p (XEXP (x, 0), insn, avail_p); 954 955 case PRE_DEC: 956 case PRE_INC: 957 case POST_DEC: 958 case POST_INC: 959 case PRE_MODIFY: 960 case POST_MODIFY: 961 return 0; 962 963 case PC: 964 case CC0: /*FIXME*/ 965 case CONST: 966 CASE_CONST_ANY: 967 case SYMBOL_REF: 968 case LABEL_REF: 969 case ADDR_VEC: 970 case ADDR_DIFF_VEC: 971 return 1; 972 973 default: 974 break; 975 } 976 977 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--) 978 { 979 if (fmt[i] == 'e') 980 { 981 /* If we are about to do the last recursive call needed at this 982 level, change it into iteration. This function is called enough 983 to be worth it. */ 984 if (i == 0) 985 return oprs_unchanged_p (XEXP (x, i), insn, avail_p); 986 987 else if (! oprs_unchanged_p (XEXP (x, i), insn, avail_p)) 988 return 0; 989 } 990 else if (fmt[i] == 'E') 991 for (j = 0; j < XVECLEN (x, i); j++) 992 if (! oprs_unchanged_p (XVECEXP (x, i, j), insn, avail_p)) 993 return 0; 994 } 995 996 return 1; 997 } 998 999 /* Info passed from load_killed_in_block_p to mems_conflict_for_gcse_p. */ 1000 1001 struct mem_conflict_info 1002 { 1003 /* A memory reference for a load instruction, mems_conflict_for_gcse_p will 1004 see if a memory store conflicts with this memory load. */ 1005 const_rtx mem; 1006 1007 /* True if mems_conflict_for_gcse_p finds a conflict between two memory 1008 references. */ 1009 bool conflict; 1010 }; 1011 1012 /* DEST is the output of an instruction. If it is a memory reference and 1013 possibly conflicts with the load found in DATA, then communicate this 1014 information back through DATA. */ 1015 1016 static void 1017 mems_conflict_for_gcse_p (rtx dest, const_rtx setter ATTRIBUTE_UNUSED, 1018 void *data) 1019 { 1020 struct mem_conflict_info *mci = (struct mem_conflict_info *) data; 1021 1022 while (GET_CODE (dest) == SUBREG 1023 || GET_CODE (dest) == ZERO_EXTRACT 1024 || GET_CODE (dest) == STRICT_LOW_PART) 1025 dest = XEXP (dest, 0); 1026 1027 /* If DEST is not a MEM, then it will not conflict with the load. Note 1028 that function calls are assumed to clobber memory, but are handled 1029 elsewhere. */ 1030 if (! MEM_P (dest)) 1031 return; 1032 1033 /* If we are setting a MEM in our list of specially recognized MEMs, 1034 don't mark as killed this time. */ 1035 if (pre_ldst_mems != NULL && expr_equiv_p (dest, mci->mem)) 1036 { 1037 if (!find_rtx_in_ldst (dest)) 1038 mci->conflict = true; 1039 return; 1040 } 1041 1042 if (true_dependence (dest, GET_MODE (dest), mci->mem)) 1043 mci->conflict = true; 1044 } 1045 1046 /* Return nonzero if the expression in X (a memory reference) is killed 1047 in block BB before or after the insn with the LUID in UID_LIMIT. 1048 AVAIL_P is nonzero for kills after UID_LIMIT, and zero for kills 1049 before UID_LIMIT. 1050 1051 To check the entire block, set UID_LIMIT to max_uid + 1 and 1052 AVAIL_P to 0. */ 1053 1054 static int 1055 load_killed_in_block_p (const_basic_block bb, int uid_limit, const_rtx x, 1056 int avail_p) 1057 { 1058 vec<rtx_insn *> list = modify_mem_list[bb->index]; 1059 rtx_insn *setter; 1060 unsigned ix; 1061 1062 /* If this is a readonly then we aren't going to be changing it. */ 1063 if (MEM_READONLY_P (x)) 1064 return 0; 1065 1066 FOR_EACH_VEC_ELT_REVERSE (list, ix, setter) 1067 { 1068 struct mem_conflict_info mci; 1069 1070 /* Ignore entries in the list that do not apply. */ 1071 if ((avail_p 1072 && DF_INSN_LUID (setter) < uid_limit) 1073 || (! avail_p 1074 && DF_INSN_LUID (setter) > uid_limit)) 1075 continue; 1076 1077 /* If SETTER is a call everything is clobbered. Note that calls 1078 to pure functions are never put on the list, so we need not 1079 worry about them. */ 1080 if (CALL_P (setter)) 1081 return 1; 1082 1083 /* SETTER must be an INSN of some kind that sets memory. Call 1084 note_stores to examine each hunk of memory that is modified. */ 1085 mci.mem = x; 1086 mci.conflict = false; 1087 note_stores (PATTERN (setter), mems_conflict_for_gcse_p, &mci); 1088 if (mci.conflict) 1089 return 1; 1090 } 1091 return 0; 1092 } 1093 1094 /* Return nonzero if the operands of expression X are unchanged from 1095 the start of INSN's basic block up to but not including INSN. */ 1096 1097 static int 1098 oprs_anticipatable_p (const_rtx x, const rtx_insn *insn) 1099 { 1100 return oprs_unchanged_p (x, insn, 0); 1101 } 1102 1103 /* Return nonzero if the operands of expression X are unchanged from 1104 INSN to the end of INSN's basic block. */ 1105 1106 static int 1107 oprs_available_p (const_rtx x, const rtx_insn *insn) 1108 { 1109 return oprs_unchanged_p (x, insn, 1); 1110 } 1111 1112 /* Hash expression X. 1113 1114 MODE is only used if X is a CONST_INT. DO_NOT_RECORD_P is a boolean 1115 indicating if a volatile operand is found or if the expression contains 1116 something we don't want to insert in the table. HASH_TABLE_SIZE is 1117 the current size of the hash table to be probed. */ 1118 1119 static unsigned int 1120 hash_expr (const_rtx x, machine_mode mode, int *do_not_record_p, 1121 int hash_table_size) 1122 { 1123 unsigned int hash; 1124 1125 *do_not_record_p = 0; 1126 1127 hash = hash_rtx (x, mode, do_not_record_p, NULL, /*have_reg_qty=*/false); 1128 return hash % hash_table_size; 1129 } 1130 1131 /* Return nonzero if exp1 is equivalent to exp2. */ 1132 1133 static int 1134 expr_equiv_p (const_rtx x, const_rtx y) 1135 { 1136 return exp_equiv_p (x, y, 0, true); 1137 } 1138 1139 /* Insert expression X in INSN in the hash TABLE. 1140 If it is already present, record it as the last occurrence in INSN's 1141 basic block. 1142 1143 MODE is the mode of the value X is being stored into. 1144 It is only used if X is a CONST_INT. 1145 1146 ANTIC_P is nonzero if X is an anticipatable expression. 1147 AVAIL_P is nonzero if X is an available expression. 1148 1149 MAX_DISTANCE is the maximum distance in instructions this expression can 1150 be moved. */ 1151 1152 static void 1153 insert_expr_in_table (rtx x, machine_mode mode, rtx_insn *insn, 1154 int antic_p, 1155 int avail_p, HOST_WIDE_INT max_distance, 1156 struct gcse_hash_table_d *table) 1157 { 1158 int found, do_not_record_p; 1159 unsigned int hash; 1160 struct gcse_expr *cur_expr, *last_expr = NULL; 1161 struct gcse_occr *antic_occr, *avail_occr; 1162 1163 hash = hash_expr (x, mode, &do_not_record_p, table->size); 1164 1165 /* Do not insert expression in table if it contains volatile operands, 1166 or if hash_expr determines the expression is something we don't want 1167 to or can't handle. */ 1168 if (do_not_record_p) 1169 return; 1170 1171 cur_expr = table->table[hash]; 1172 found = 0; 1173 1174 while (cur_expr && 0 == (found = expr_equiv_p (cur_expr->expr, x))) 1175 { 1176 /* If the expression isn't found, save a pointer to the end of 1177 the list. */ 1178 last_expr = cur_expr; 1179 cur_expr = cur_expr->next_same_hash; 1180 } 1181 1182 if (! found) 1183 { 1184 cur_expr = GOBNEW (struct gcse_expr); 1185 bytes_used += sizeof (struct gcse_expr); 1186 if (table->table[hash] == NULL) 1187 /* This is the first pattern that hashed to this index. */ 1188 table->table[hash] = cur_expr; 1189 else 1190 /* Add EXPR to end of this hash chain. */ 1191 last_expr->next_same_hash = cur_expr; 1192 1193 /* Set the fields of the expr element. */ 1194 cur_expr->expr = x; 1195 cur_expr->bitmap_index = table->n_elems++; 1196 cur_expr->next_same_hash = NULL; 1197 cur_expr->antic_occr = NULL; 1198 cur_expr->avail_occr = NULL; 1199 gcc_assert (max_distance >= 0); 1200 cur_expr->max_distance = max_distance; 1201 } 1202 else 1203 gcc_assert (cur_expr->max_distance == max_distance); 1204 1205 /* Now record the occurrence(s). */ 1206 if (antic_p) 1207 { 1208 antic_occr = cur_expr->antic_occr; 1209 1210 if (antic_occr 1211 && BLOCK_FOR_INSN (antic_occr->insn) != BLOCK_FOR_INSN (insn)) 1212 antic_occr = NULL; 1213 1214 if (antic_occr) 1215 /* Found another instance of the expression in the same basic block. 1216 Prefer the currently recorded one. We want the first one in the 1217 block and the block is scanned from start to end. */ 1218 ; /* nothing to do */ 1219 else 1220 { 1221 /* First occurrence of this expression in this basic block. */ 1222 antic_occr = GOBNEW (struct gcse_occr); 1223 bytes_used += sizeof (struct gcse_occr); 1224 antic_occr->insn = insn; 1225 antic_occr->next = cur_expr->antic_occr; 1226 antic_occr->deleted_p = 0; 1227 cur_expr->antic_occr = antic_occr; 1228 } 1229 } 1230 1231 if (avail_p) 1232 { 1233 avail_occr = cur_expr->avail_occr; 1234 1235 if (avail_occr 1236 && BLOCK_FOR_INSN (avail_occr->insn) == BLOCK_FOR_INSN (insn)) 1237 { 1238 /* Found another instance of the expression in the same basic block. 1239 Prefer this occurrence to the currently recorded one. We want 1240 the last one in the block and the block is scanned from start 1241 to end. */ 1242 avail_occr->insn = insn; 1243 } 1244 else 1245 { 1246 /* First occurrence of this expression in this basic block. */ 1247 avail_occr = GOBNEW (struct gcse_occr); 1248 bytes_used += sizeof (struct gcse_occr); 1249 avail_occr->insn = insn; 1250 avail_occr->next = cur_expr->avail_occr; 1251 avail_occr->deleted_p = 0; 1252 cur_expr->avail_occr = avail_occr; 1253 } 1254 } 1255 } 1256 1257 /* Scan SET present in INSN and add an entry to the hash TABLE. */ 1258 1259 static void 1260 hash_scan_set (rtx set, rtx_insn *insn, struct gcse_hash_table_d *table) 1261 { 1262 rtx src = SET_SRC (set); 1263 rtx dest = SET_DEST (set); 1264 rtx note; 1265 1266 if (GET_CODE (src) == CALL) 1267 hash_scan_call (src, insn, table); 1268 1269 else if (REG_P (dest)) 1270 { 1271 unsigned int regno = REGNO (dest); 1272 HOST_WIDE_INT max_distance = 0; 1273 1274 /* See if a REG_EQUAL note shows this equivalent to a simpler expression. 1275 1276 This allows us to do a single GCSE pass and still eliminate 1277 redundant constants, addresses or other expressions that are 1278 constructed with multiple instructions. 1279 1280 However, keep the original SRC if INSN is a simple reg-reg move. 1281 In this case, there will almost always be a REG_EQUAL note on the 1282 insn that sets SRC. By recording the REG_EQUAL value here as SRC 1283 for INSN, we miss copy propagation opportunities and we perform the 1284 same PRE GCSE operation repeatedly on the same REG_EQUAL value if we 1285 do more than one PRE GCSE pass. 1286 1287 Note that this does not impede profitable constant propagations. We 1288 "look through" reg-reg sets in lookup_avail_set. */ 1289 note = find_reg_equal_equiv_note (insn); 1290 if (note != 0 1291 && REG_NOTE_KIND (note) == REG_EQUAL 1292 && !REG_P (src) 1293 && want_to_gcse_p (XEXP (note, 0), NULL)) 1294 src = XEXP (note, 0), set = gen_rtx_SET (VOIDmode, dest, src); 1295 1296 /* Only record sets of pseudo-regs in the hash table. */ 1297 if (regno >= FIRST_PSEUDO_REGISTER 1298 /* Don't GCSE something if we can't do a reg/reg copy. */ 1299 && can_copy_p (GET_MODE (dest)) 1300 /* GCSE commonly inserts instruction after the insn. We can't 1301 do that easily for EH edges so disable GCSE on these for now. */ 1302 /* ??? We can now easily create new EH landing pads at the 1303 gimple level, for splitting edges; there's no reason we 1304 can't do the same thing at the rtl level. */ 1305 && !can_throw_internal (insn) 1306 /* Is SET_SRC something we want to gcse? */ 1307 && want_to_gcse_p (src, &max_distance) 1308 /* Don't CSE a nop. */ 1309 && ! set_noop_p (set) 1310 /* Don't GCSE if it has attached REG_EQUIV note. 1311 At this point this only function parameters should have 1312 REG_EQUIV notes and if the argument slot is used somewhere 1313 explicitly, it means address of parameter has been taken, 1314 so we should not extend the lifetime of the pseudo. */ 1315 && (note == NULL_RTX || ! MEM_P (XEXP (note, 0)))) 1316 { 1317 /* An expression is not anticipatable if its operands are 1318 modified before this insn or if this is not the only SET in 1319 this insn. The latter condition does not have to mean that 1320 SRC itself is not anticipatable, but we just will not be 1321 able to handle code motion of insns with multiple sets. */ 1322 int antic_p = oprs_anticipatable_p (src, insn) 1323 && !multiple_sets (insn); 1324 /* An expression is not available if its operands are 1325 subsequently modified, including this insn. It's also not 1326 available if this is a branch, because we can't insert 1327 a set after the branch. */ 1328 int avail_p = (oprs_available_p (src, insn) 1329 && ! JUMP_P (insn)); 1330 1331 insert_expr_in_table (src, GET_MODE (dest), insn, antic_p, avail_p, 1332 max_distance, table); 1333 } 1334 } 1335 /* In case of store we want to consider the memory value as available in 1336 the REG stored in that memory. This makes it possible to remove 1337 redundant loads from due to stores to the same location. */ 1338 else if (flag_gcse_las && REG_P (src) && MEM_P (dest)) 1339 { 1340 unsigned int regno = REGNO (src); 1341 HOST_WIDE_INT max_distance = 0; 1342 1343 /* Only record sets of pseudo-regs in the hash table. */ 1344 if (regno >= FIRST_PSEUDO_REGISTER 1345 /* Don't GCSE something if we can't do a reg/reg copy. */ 1346 && can_copy_p (GET_MODE (src)) 1347 /* GCSE commonly inserts instruction after the insn. We can't 1348 do that easily for EH edges so disable GCSE on these for now. */ 1349 && !can_throw_internal (insn) 1350 /* Is SET_DEST something we want to gcse? */ 1351 && want_to_gcse_p (dest, &max_distance) 1352 /* Don't CSE a nop. */ 1353 && ! set_noop_p (set) 1354 /* Don't GCSE if it has attached REG_EQUIV note. 1355 At this point this only function parameters should have 1356 REG_EQUIV notes and if the argument slot is used somewhere 1357 explicitly, it means address of parameter has been taken, 1358 so we should not extend the lifetime of the pseudo. */ 1359 && ((note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) == 0 1360 || ! MEM_P (XEXP (note, 0)))) 1361 { 1362 /* Stores are never anticipatable. */ 1363 int antic_p = 0; 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 (dest, insn) 1369 && ! JUMP_P (insn); 1370 1371 /* Record the memory expression (DEST) in the hash table. */ 1372 insert_expr_in_table (dest, GET_MODE (dest), insn, 1373 antic_p, avail_p, max_distance, table); 1374 } 1375 } 1376 } 1377 1378 static void 1379 hash_scan_clobber (rtx x ATTRIBUTE_UNUSED, rtx_insn *insn ATTRIBUTE_UNUSED, 1380 struct gcse_hash_table_d *table ATTRIBUTE_UNUSED) 1381 { 1382 /* Currently nothing to do. */ 1383 } 1384 1385 static void 1386 hash_scan_call (rtx x ATTRIBUTE_UNUSED, rtx_insn *insn ATTRIBUTE_UNUSED, 1387 struct gcse_hash_table_d *table ATTRIBUTE_UNUSED) 1388 { 1389 /* Currently nothing to do. */ 1390 } 1391 1392 /* Process INSN and add hash table entries as appropriate. */ 1393 1394 static void 1395 hash_scan_insn (rtx_insn *insn, struct gcse_hash_table_d *table) 1396 { 1397 rtx pat = PATTERN (insn); 1398 int i; 1399 1400 /* Pick out the sets of INSN and for other forms of instructions record 1401 what's been modified. */ 1402 1403 if (GET_CODE (pat) == SET) 1404 hash_scan_set (pat, insn, table); 1405 1406 else if (GET_CODE (pat) == CLOBBER) 1407 hash_scan_clobber (pat, insn, table); 1408 1409 else if (GET_CODE (pat) == CALL) 1410 hash_scan_call (pat, insn, table); 1411 1412 else if (GET_CODE (pat) == PARALLEL) 1413 for (i = 0; i < XVECLEN (pat, 0); i++) 1414 { 1415 rtx x = XVECEXP (pat, 0, i); 1416 1417 if (GET_CODE (x) == SET) 1418 hash_scan_set (x, insn, table); 1419 else if (GET_CODE (x) == CLOBBER) 1420 hash_scan_clobber (x, insn, table); 1421 else if (GET_CODE (x) == CALL) 1422 hash_scan_call (x, insn, table); 1423 } 1424 } 1425 1426 /* Dump the hash table TABLE to file FILE under the name NAME. */ 1427 1428 static void 1429 dump_hash_table (FILE *file, const char *name, struct gcse_hash_table_d *table) 1430 { 1431 int i; 1432 /* Flattened out table, so it's printed in proper order. */ 1433 struct gcse_expr **flat_table; 1434 unsigned int *hash_val; 1435 struct gcse_expr *expr; 1436 1437 flat_table = XCNEWVEC (struct gcse_expr *, table->n_elems); 1438 hash_val = XNEWVEC (unsigned int, table->n_elems); 1439 1440 for (i = 0; i < (int) table->size; i++) 1441 for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash) 1442 { 1443 flat_table[expr->bitmap_index] = expr; 1444 hash_val[expr->bitmap_index] = i; 1445 } 1446 1447 fprintf (file, "%s hash table (%d buckets, %d entries)\n", 1448 name, table->size, table->n_elems); 1449 1450 for (i = 0; i < (int) table->n_elems; i++) 1451 if (flat_table[i] != 0) 1452 { 1453 expr = flat_table[i]; 1454 fprintf (file, "Index %d (hash value %d; max distance " 1455 HOST_WIDE_INT_PRINT_DEC ")\n ", 1456 expr->bitmap_index, hash_val[i], expr->max_distance); 1457 print_rtl (file, expr->expr); 1458 fprintf (file, "\n"); 1459 } 1460 1461 fprintf (file, "\n"); 1462 1463 free (flat_table); 1464 free (hash_val); 1465 } 1466 1467 /* Record register first/last/block set information for REGNO in INSN. 1468 1469 first_set records the first place in the block where the register 1470 is set and is used to compute "anticipatability". 1471 1472 last_set records the last place in the block where the register 1473 is set and is used to compute "availability". 1474 1475 last_bb records the block for which first_set and last_set are 1476 valid, as a quick test to invalidate them. */ 1477 1478 static void 1479 record_last_reg_set_info (rtx insn, int regno) 1480 { 1481 struct reg_avail_info *info = ®_avail_info[regno]; 1482 int luid = DF_INSN_LUID (insn); 1483 1484 info->last_set = luid; 1485 if (info->last_bb != current_bb) 1486 { 1487 info->last_bb = current_bb; 1488 info->first_set = luid; 1489 } 1490 } 1491 1492 /* Record memory modification information for INSN. We do not actually care 1493 about the memory location(s) that are set, or even how they are set (consider 1494 a CALL_INSN). We merely need to record which insns modify memory. */ 1495 1496 static void 1497 record_last_mem_set_info (rtx_insn *insn) 1498 { 1499 if (! flag_gcse_lm) 1500 return; 1501 1502 record_last_mem_set_info_common (insn, modify_mem_list, 1503 canon_modify_mem_list, 1504 modify_mem_list_set, 1505 blocks_with_calls); 1506 } 1507 1508 /* Called from compute_hash_table via note_stores to handle one 1509 SET or CLOBBER in an insn. DATA is really the instruction in which 1510 the SET is taking place. */ 1511 1512 static void 1513 record_last_set_info (rtx dest, const_rtx setter ATTRIBUTE_UNUSED, void *data) 1514 { 1515 rtx_insn *last_set_insn = (rtx_insn *) data; 1516 1517 if (GET_CODE (dest) == SUBREG) 1518 dest = SUBREG_REG (dest); 1519 1520 if (REG_P (dest)) 1521 record_last_reg_set_info (last_set_insn, REGNO (dest)); 1522 else if (MEM_P (dest) 1523 /* Ignore pushes, they clobber nothing. */ 1524 && ! push_operand (dest, GET_MODE (dest))) 1525 record_last_mem_set_info (last_set_insn); 1526 } 1527 1528 /* Top level function to create an expression hash table. 1529 1530 Expression entries are placed in the hash table if 1531 - they are of the form (set (pseudo-reg) src), 1532 - src is something we want to perform GCSE on, 1533 - none of the operands are subsequently modified in the block 1534 1535 Currently src must be a pseudo-reg or a const_int. 1536 1537 TABLE is the table computed. */ 1538 1539 static void 1540 compute_hash_table_work (struct gcse_hash_table_d *table) 1541 { 1542 int i; 1543 1544 /* re-Cache any INSN_LIST nodes we have allocated. */ 1545 clear_modify_mem_tables (); 1546 /* Some working arrays used to track first and last set in each block. */ 1547 reg_avail_info = GNEWVEC (struct reg_avail_info, max_reg_num ()); 1548 1549 for (i = 0; i < max_reg_num (); ++i) 1550 reg_avail_info[i].last_bb = NULL; 1551 1552 FOR_EACH_BB_FN (current_bb, cfun) 1553 { 1554 rtx_insn *insn; 1555 unsigned int regno; 1556 1557 /* First pass over the instructions records information used to 1558 determine when registers and memory are first and last set. */ 1559 FOR_BB_INSNS (current_bb, insn) 1560 { 1561 if (!NONDEBUG_INSN_P (insn)) 1562 continue; 1563 1564 if (CALL_P (insn)) 1565 { 1566 hard_reg_set_iterator hrsi; 1567 EXECUTE_IF_SET_IN_HARD_REG_SET (regs_invalidated_by_call, 1568 0, regno, hrsi) 1569 record_last_reg_set_info (insn, regno); 1570 1571 if (! RTL_CONST_OR_PURE_CALL_P (insn)) 1572 record_last_mem_set_info (insn); 1573 } 1574 1575 note_stores (PATTERN (insn), record_last_set_info, insn); 1576 } 1577 1578 /* The next pass builds the hash table. */ 1579 FOR_BB_INSNS (current_bb, insn) 1580 if (NONDEBUG_INSN_P (insn)) 1581 hash_scan_insn (insn, table); 1582 } 1583 1584 free (reg_avail_info); 1585 reg_avail_info = NULL; 1586 } 1587 1588 /* Allocate space for the set/expr hash TABLE. 1589 It is used to determine the number of buckets to use. */ 1590 1591 static void 1592 alloc_hash_table (struct gcse_hash_table_d *table) 1593 { 1594 int n; 1595 1596 n = get_max_insn_count (); 1597 1598 table->size = n / 4; 1599 if (table->size < 11) 1600 table->size = 11; 1601 1602 /* Attempt to maintain efficient use of hash table. 1603 Making it an odd number is simplest for now. 1604 ??? Later take some measurements. */ 1605 table->size |= 1; 1606 n = table->size * sizeof (struct gcse_expr *); 1607 table->table = GNEWVAR (struct gcse_expr *, n); 1608 } 1609 1610 /* Free things allocated by alloc_hash_table. */ 1611 1612 static void 1613 free_hash_table (struct gcse_hash_table_d *table) 1614 { 1615 free (table->table); 1616 } 1617 1618 /* Compute the expression hash table TABLE. */ 1619 1620 static void 1621 compute_hash_table (struct gcse_hash_table_d *table) 1622 { 1623 /* Initialize count of number of entries in hash table. */ 1624 table->n_elems = 0; 1625 memset (table->table, 0, table->size * sizeof (struct gcse_expr *)); 1626 1627 compute_hash_table_work (table); 1628 } 1629 1630 /* Expression tracking support. */ 1631 1632 /* Clear canon_modify_mem_list and modify_mem_list tables. */ 1633 static void 1634 clear_modify_mem_tables (void) 1635 { 1636 unsigned i; 1637 bitmap_iterator bi; 1638 1639 EXECUTE_IF_SET_IN_BITMAP (modify_mem_list_set, 0, i, bi) 1640 { 1641 modify_mem_list[i].release (); 1642 canon_modify_mem_list[i].release (); 1643 } 1644 bitmap_clear (modify_mem_list_set); 1645 bitmap_clear (blocks_with_calls); 1646 } 1647 1648 /* Release memory used by modify_mem_list_set. */ 1649 1650 static void 1651 free_modify_mem_tables (void) 1652 { 1653 clear_modify_mem_tables (); 1654 free (modify_mem_list); 1655 free (canon_modify_mem_list); 1656 modify_mem_list = 0; 1657 canon_modify_mem_list = 0; 1658 } 1659 1660 /* Compute PRE+LCM working variables. */ 1661 1662 /* Local properties of expressions. */ 1663 1664 /* Nonzero for expressions that are transparent in the block. */ 1665 static sbitmap *transp; 1666 1667 /* Nonzero for expressions that are computed (available) in the block. */ 1668 static sbitmap *comp; 1669 1670 /* Nonzero for expressions that are locally anticipatable in the block. */ 1671 static sbitmap *antloc; 1672 1673 /* Nonzero for expressions where this block is an optimal computation 1674 point. */ 1675 static sbitmap *pre_optimal; 1676 1677 /* Nonzero for expressions which are redundant in a particular block. */ 1678 static sbitmap *pre_redundant; 1679 1680 /* Nonzero for expressions which should be inserted on a specific edge. */ 1681 static sbitmap *pre_insert_map; 1682 1683 /* Nonzero for expressions which should be deleted in a specific block. */ 1684 static sbitmap *pre_delete_map; 1685 1686 /* Allocate vars used for PRE analysis. */ 1687 1688 static void 1689 alloc_pre_mem (int n_blocks, int n_exprs) 1690 { 1691 transp = sbitmap_vector_alloc (n_blocks, n_exprs); 1692 comp = sbitmap_vector_alloc (n_blocks, n_exprs); 1693 antloc = sbitmap_vector_alloc (n_blocks, n_exprs); 1694 1695 pre_optimal = NULL; 1696 pre_redundant = NULL; 1697 pre_insert_map = NULL; 1698 pre_delete_map = NULL; 1699 ae_kill = sbitmap_vector_alloc (n_blocks, n_exprs); 1700 1701 /* pre_insert and pre_delete are allocated later. */ 1702 } 1703 1704 /* Free vars used for PRE analysis. */ 1705 1706 static void 1707 free_pre_mem (void) 1708 { 1709 sbitmap_vector_free (transp); 1710 sbitmap_vector_free (comp); 1711 1712 /* ANTLOC and AE_KILL are freed just after pre_lcm finishes. */ 1713 1714 if (pre_optimal) 1715 sbitmap_vector_free (pre_optimal); 1716 if (pre_redundant) 1717 sbitmap_vector_free (pre_redundant); 1718 if (pre_insert_map) 1719 sbitmap_vector_free (pre_insert_map); 1720 if (pre_delete_map) 1721 sbitmap_vector_free (pre_delete_map); 1722 1723 transp = comp = NULL; 1724 pre_optimal = pre_redundant = pre_insert_map = pre_delete_map = NULL; 1725 } 1726 1727 /* Remove certain expressions from anticipatable and transparent 1728 sets of basic blocks that have incoming abnormal edge. 1729 For PRE remove potentially trapping expressions to avoid placing 1730 them on abnormal edges. For hoisting remove memory references that 1731 can be clobbered by calls. */ 1732 1733 static void 1734 prune_expressions (bool pre_p) 1735 { 1736 sbitmap prune_exprs; 1737 struct gcse_expr *expr; 1738 unsigned int ui; 1739 basic_block bb; 1740 1741 prune_exprs = sbitmap_alloc (expr_hash_table.n_elems); 1742 bitmap_clear (prune_exprs); 1743 for (ui = 0; ui < expr_hash_table.size; ui++) 1744 { 1745 for (expr = expr_hash_table.table[ui]; expr; expr = expr->next_same_hash) 1746 { 1747 /* Note potentially trapping expressions. */ 1748 if (may_trap_p (expr->expr)) 1749 { 1750 bitmap_set_bit (prune_exprs, expr->bitmap_index); 1751 continue; 1752 } 1753 1754 if (!pre_p && MEM_P (expr->expr)) 1755 /* Note memory references that can be clobbered by a call. 1756 We do not split abnormal edges in hoisting, so would 1757 a memory reference get hoisted along an abnormal edge, 1758 it would be placed /before/ the call. Therefore, only 1759 constant memory references can be hoisted along abnormal 1760 edges. */ 1761 { 1762 if (GET_CODE (XEXP (expr->expr, 0)) == SYMBOL_REF 1763 && CONSTANT_POOL_ADDRESS_P (XEXP (expr->expr, 0))) 1764 continue; 1765 1766 if (MEM_READONLY_P (expr->expr) 1767 && !MEM_VOLATILE_P (expr->expr) 1768 && MEM_NOTRAP_P (expr->expr)) 1769 /* Constant memory reference, e.g., a PIC address. */ 1770 continue; 1771 1772 /* ??? Optimally, we would use interprocedural alias 1773 analysis to determine if this mem is actually killed 1774 by this call. */ 1775 1776 bitmap_set_bit (prune_exprs, expr->bitmap_index); 1777 } 1778 } 1779 } 1780 1781 FOR_EACH_BB_FN (bb, cfun) 1782 { 1783 edge e; 1784 edge_iterator ei; 1785 1786 /* If the current block is the destination of an abnormal edge, we 1787 kill all trapping (for PRE) and memory (for hoist) expressions 1788 because we won't be able to properly place the instruction on 1789 the edge. So make them neither anticipatable nor transparent. 1790 This is fairly conservative. 1791 1792 ??? For hoisting it may be necessary to check for set-and-jump 1793 instructions here, not just for abnormal edges. The general problem 1794 is that when an expression cannot not be placed right at the end of 1795 a basic block we should account for any side-effects of a subsequent 1796 jump instructions that could clobber the expression. It would 1797 be best to implement this check along the lines of 1798 should_hoist_expr_to_dom where the target block is already known 1799 and, hence, there's no need to conservatively prune expressions on 1800 "intermediate" set-and-jump instructions. */ 1801 FOR_EACH_EDGE (e, ei, bb->preds) 1802 if ((e->flags & EDGE_ABNORMAL) 1803 && (pre_p || CALL_P (BB_END (e->src)))) 1804 { 1805 bitmap_and_compl (antloc[bb->index], 1806 antloc[bb->index], prune_exprs); 1807 bitmap_and_compl (transp[bb->index], 1808 transp[bb->index], prune_exprs); 1809 break; 1810 } 1811 } 1812 1813 sbitmap_free (prune_exprs); 1814 } 1815 1816 /* It may be necessary to insert a large number of insns on edges to 1817 make the existing occurrences of expressions fully redundant. This 1818 routine examines the set of insertions and deletions and if the ratio 1819 of insertions to deletions is too high for a particular expression, then 1820 the expression is removed from the insertion/deletion sets. 1821 1822 N_ELEMS is the number of elements in the hash table. */ 1823 1824 static void 1825 prune_insertions_deletions (int n_elems) 1826 { 1827 sbitmap_iterator sbi; 1828 sbitmap prune_exprs; 1829 1830 /* We always use I to iterate over blocks/edges and J to iterate over 1831 expressions. */ 1832 unsigned int i, j; 1833 1834 /* Counts for the number of times an expression needs to be inserted and 1835 number of times an expression can be removed as a result. */ 1836 int *insertions = GCNEWVEC (int, n_elems); 1837 int *deletions = GCNEWVEC (int, n_elems); 1838 1839 /* Set of expressions which require too many insertions relative to 1840 the number of deletions achieved. We will prune these out of the 1841 insertion/deletion sets. */ 1842 prune_exprs = sbitmap_alloc (n_elems); 1843 bitmap_clear (prune_exprs); 1844 1845 /* Iterate over the edges counting the number of times each expression 1846 needs to be inserted. */ 1847 for (i = 0; i < (unsigned) n_edges_for_fn (cfun); i++) 1848 { 1849 EXECUTE_IF_SET_IN_BITMAP (pre_insert_map[i], 0, j, sbi) 1850 insertions[j]++; 1851 } 1852 1853 /* Similarly for deletions, but those occur in blocks rather than on 1854 edges. */ 1855 for (i = 0; i < (unsigned) last_basic_block_for_fn (cfun); i++) 1856 { 1857 EXECUTE_IF_SET_IN_BITMAP (pre_delete_map[i], 0, j, sbi) 1858 deletions[j]++; 1859 } 1860 1861 /* Now that we have accurate counts, iterate over the elements in the 1862 hash table and see if any need too many insertions relative to the 1863 number of evaluations that can be removed. If so, mark them in 1864 PRUNE_EXPRS. */ 1865 for (j = 0; j < (unsigned) n_elems; j++) 1866 if (deletions[j] 1867 && ((unsigned) insertions[j] / deletions[j]) > MAX_GCSE_INSERTION_RATIO) 1868 bitmap_set_bit (prune_exprs, j); 1869 1870 /* Now prune PRE_INSERT_MAP and PRE_DELETE_MAP based on PRUNE_EXPRS. */ 1871 EXECUTE_IF_SET_IN_BITMAP (prune_exprs, 0, j, sbi) 1872 { 1873 for (i = 0; i < (unsigned) n_edges_for_fn (cfun); i++) 1874 bitmap_clear_bit (pre_insert_map[i], j); 1875 1876 for (i = 0; i < (unsigned) last_basic_block_for_fn (cfun); i++) 1877 bitmap_clear_bit (pre_delete_map[i], j); 1878 } 1879 1880 sbitmap_free (prune_exprs); 1881 free (insertions); 1882 free (deletions); 1883 } 1884 1885 /* Top level routine to do the dataflow analysis needed by PRE. */ 1886 1887 static struct edge_list * 1888 compute_pre_data (void) 1889 { 1890 struct edge_list *edge_list; 1891 basic_block bb; 1892 1893 compute_local_properties (transp, comp, antloc, &expr_hash_table); 1894 prune_expressions (true); 1895 bitmap_vector_clear (ae_kill, last_basic_block_for_fn (cfun)); 1896 1897 /* Compute ae_kill for each basic block using: 1898 1899 ~(TRANSP | COMP) 1900 */ 1901 1902 FOR_EACH_BB_FN (bb, cfun) 1903 { 1904 bitmap_ior (ae_kill[bb->index], transp[bb->index], comp[bb->index]); 1905 bitmap_not (ae_kill[bb->index], ae_kill[bb->index]); 1906 } 1907 1908 edge_list = pre_edge_lcm (expr_hash_table.n_elems, transp, comp, antloc, 1909 ae_kill, &pre_insert_map, &pre_delete_map); 1910 sbitmap_vector_free (antloc); 1911 antloc = NULL; 1912 sbitmap_vector_free (ae_kill); 1913 ae_kill = NULL; 1914 1915 prune_insertions_deletions (expr_hash_table.n_elems); 1916 1917 return edge_list; 1918 } 1919 1920 /* PRE utilities */ 1921 1922 /* Return nonzero if an occurrence of expression EXPR in OCCR_BB would reach 1923 block BB. 1924 1925 VISITED is a pointer to a working buffer for tracking which BB's have 1926 been visited. It is NULL for the top-level call. 1927 1928 We treat reaching expressions that go through blocks containing the same 1929 reaching expression as "not reaching". E.g. if EXPR is generated in blocks 1930 2 and 3, INSN is in block 4, and 2->3->4, we treat the expression in block 1931 2 as not reaching. The intent is to improve the probability of finding 1932 only one reaching expression and to reduce register lifetimes by picking 1933 the closest such expression. */ 1934 1935 static int 1936 pre_expr_reaches_here_p_work (basic_block occr_bb, struct gcse_expr *expr, 1937 basic_block bb, char *visited) 1938 { 1939 edge pred; 1940 edge_iterator ei; 1941 1942 FOR_EACH_EDGE (pred, ei, bb->preds) 1943 { 1944 basic_block pred_bb = pred->src; 1945 1946 if (pred->src == ENTRY_BLOCK_PTR_FOR_FN (cfun) 1947 /* Has predecessor has already been visited? */ 1948 || visited[pred_bb->index]) 1949 ;/* Nothing to do. */ 1950 1951 /* Does this predecessor generate this expression? */ 1952 else if (bitmap_bit_p (comp[pred_bb->index], expr->bitmap_index)) 1953 { 1954 /* Is this the occurrence we're looking for? 1955 Note that there's only one generating occurrence per block 1956 so we just need to check the block number. */ 1957 if (occr_bb == pred_bb) 1958 return 1; 1959 1960 visited[pred_bb->index] = 1; 1961 } 1962 /* Ignore this predecessor if it kills the expression. */ 1963 else if (! bitmap_bit_p (transp[pred_bb->index], expr->bitmap_index)) 1964 visited[pred_bb->index] = 1; 1965 1966 /* Neither gen nor kill. */ 1967 else 1968 { 1969 visited[pred_bb->index] = 1; 1970 if (pre_expr_reaches_here_p_work (occr_bb, expr, pred_bb, visited)) 1971 return 1; 1972 } 1973 } 1974 1975 /* All paths have been checked. */ 1976 return 0; 1977 } 1978 1979 /* The wrapper for pre_expr_reaches_here_work that ensures that any 1980 memory allocated for that function is returned. */ 1981 1982 static int 1983 pre_expr_reaches_here_p (basic_block occr_bb, struct gcse_expr *expr, basic_block bb) 1984 { 1985 int rval; 1986 char *visited = XCNEWVEC (char, last_basic_block_for_fn (cfun)); 1987 1988 rval = pre_expr_reaches_here_p_work (occr_bb, expr, bb, visited); 1989 1990 free (visited); 1991 return rval; 1992 } 1993 1994 /* Generate RTL to copy an EXPR to its `reaching_reg' and return it. */ 1995 1996 static rtx_insn * 1997 process_insert_insn (struct gcse_expr *expr) 1998 { 1999 rtx reg = expr->reaching_reg; 2000 /* Copy the expression to make sure we don't have any sharing issues. */ 2001 rtx exp = copy_rtx (expr->expr); 2002 rtx_insn *pat; 2003 2004 start_sequence (); 2005 2006 /* If the expression is something that's an operand, like a constant, 2007 just copy it to a register. */ 2008 if (general_operand (exp, GET_MODE (reg))) 2009 emit_move_insn (reg, exp); 2010 2011 /* Otherwise, make a new insn to compute this expression and make sure the 2012 insn will be recognized (this also adds any needed CLOBBERs). */ 2013 else 2014 { 2015 rtx_insn *insn = emit_insn (gen_rtx_SET (VOIDmode, reg, exp)); 2016 2017 if (insn_invalid_p (insn, false)) 2018 gcc_unreachable (); 2019 } 2020 2021 pat = get_insns (); 2022 end_sequence (); 2023 2024 return pat; 2025 } 2026 2027 /* Add EXPR to the end of basic block BB. 2028 2029 This is used by both the PRE and code hoisting. */ 2030 2031 static void 2032 insert_insn_end_basic_block (struct gcse_expr *expr, basic_block bb) 2033 { 2034 rtx_insn *insn = BB_END (bb); 2035 rtx_insn *new_insn; 2036 rtx reg = expr->reaching_reg; 2037 int regno = REGNO (reg); 2038 rtx_insn *pat, *pat_end; 2039 2040 pat = process_insert_insn (expr); 2041 gcc_assert (pat && INSN_P (pat)); 2042 2043 pat_end = pat; 2044 while (NEXT_INSN (pat_end) != NULL_RTX) 2045 pat_end = NEXT_INSN (pat_end); 2046 2047 /* If the last insn is a jump, insert EXPR in front [taking care to 2048 handle cc0, etc. properly]. Similarly we need to care trapping 2049 instructions in presence of non-call exceptions. */ 2050 2051 if (JUMP_P (insn) 2052 || (NONJUMP_INSN_P (insn) 2053 && (!single_succ_p (bb) 2054 || single_succ_edge (bb)->flags & EDGE_ABNORMAL))) 2055 { 2056 #ifdef HAVE_cc0 2057 /* FIXME: 'twould be nice to call prev_cc0_setter here but it aborts 2058 if cc0 isn't set. */ 2059 rtx note = find_reg_note (insn, REG_CC_SETTER, NULL_RTX); 2060 if (note) 2061 insn = safe_as_a <rtx_insn *> (XEXP (note, 0)); 2062 else 2063 { 2064 rtx_insn *maybe_cc0_setter = prev_nonnote_insn (insn); 2065 if (maybe_cc0_setter 2066 && INSN_P (maybe_cc0_setter) 2067 && sets_cc0_p (PATTERN (maybe_cc0_setter))) 2068 insn = maybe_cc0_setter; 2069 } 2070 #endif 2071 /* FIXME: What if something in cc0/jump uses value set in new insn? */ 2072 new_insn = emit_insn_before_noloc (pat, insn, bb); 2073 } 2074 2075 /* Likewise if the last insn is a call, as will happen in the presence 2076 of exception handling. */ 2077 else if (CALL_P (insn) 2078 && (!single_succ_p (bb) 2079 || single_succ_edge (bb)->flags & EDGE_ABNORMAL)) 2080 { 2081 /* Keeping in mind targets with small register classes and parameters 2082 in registers, we search backward and place the instructions before 2083 the first parameter is loaded. Do this for everyone for consistency 2084 and a presumption that we'll get better code elsewhere as well. */ 2085 2086 /* Since different machines initialize their parameter registers 2087 in different orders, assume nothing. Collect the set of all 2088 parameter registers. */ 2089 insn = find_first_parameter_load (insn, BB_HEAD (bb)); 2090 2091 /* If we found all the parameter loads, then we want to insert 2092 before the first parameter load. 2093 2094 If we did not find all the parameter loads, then we might have 2095 stopped on the head of the block, which could be a CODE_LABEL. 2096 If we inserted before the CODE_LABEL, then we would be putting 2097 the insn in the wrong basic block. In that case, put the insn 2098 after the CODE_LABEL. Also, respect NOTE_INSN_BASIC_BLOCK. */ 2099 while (LABEL_P (insn) 2100 || NOTE_INSN_BASIC_BLOCK_P (insn)) 2101 insn = NEXT_INSN (insn); 2102 2103 new_insn = emit_insn_before_noloc (pat, insn, bb); 2104 } 2105 else 2106 new_insn = emit_insn_after_noloc (pat, insn, bb); 2107 2108 while (1) 2109 { 2110 if (INSN_P (pat)) 2111 add_label_notes (PATTERN (pat), new_insn); 2112 if (pat == pat_end) 2113 break; 2114 pat = NEXT_INSN (pat); 2115 } 2116 2117 gcse_create_count++; 2118 2119 if (dump_file) 2120 { 2121 fprintf (dump_file, "PRE/HOIST: end of bb %d, insn %d, ", 2122 bb->index, INSN_UID (new_insn)); 2123 fprintf (dump_file, "copying expression %d to reg %d\n", 2124 expr->bitmap_index, regno); 2125 } 2126 } 2127 2128 /* Insert partially redundant expressions on edges in the CFG to make 2129 the expressions fully redundant. */ 2130 2131 static int 2132 pre_edge_insert (struct edge_list *edge_list, struct gcse_expr **index_map) 2133 { 2134 int e, i, j, num_edges, set_size, did_insert = 0; 2135 sbitmap *inserted; 2136 2137 /* Where PRE_INSERT_MAP is nonzero, we add the expression on that edge 2138 if it reaches any of the deleted expressions. */ 2139 2140 set_size = pre_insert_map[0]->size; 2141 num_edges = NUM_EDGES (edge_list); 2142 inserted = sbitmap_vector_alloc (num_edges, expr_hash_table.n_elems); 2143 bitmap_vector_clear (inserted, num_edges); 2144 2145 for (e = 0; e < num_edges; e++) 2146 { 2147 int indx; 2148 basic_block bb = INDEX_EDGE_PRED_BB (edge_list, e); 2149 2150 for (i = indx = 0; i < set_size; i++, indx += SBITMAP_ELT_BITS) 2151 { 2152 SBITMAP_ELT_TYPE insert = pre_insert_map[e]->elms[i]; 2153 2154 for (j = indx; 2155 insert && j < (int) expr_hash_table.n_elems; 2156 j++, insert >>= 1) 2157 if ((insert & 1) != 0 && index_map[j]->reaching_reg != NULL_RTX) 2158 { 2159 struct gcse_expr *expr = index_map[j]; 2160 struct gcse_occr *occr; 2161 2162 /* Now look at each deleted occurrence of this expression. */ 2163 for (occr = expr->antic_occr; occr != NULL; occr = occr->next) 2164 { 2165 if (! occr->deleted_p) 2166 continue; 2167 2168 /* Insert this expression on this edge if it would 2169 reach the deleted occurrence in BB. */ 2170 if (!bitmap_bit_p (inserted[e], j)) 2171 { 2172 rtx_insn *insn; 2173 edge eg = INDEX_EDGE (edge_list, e); 2174 2175 /* We can't insert anything on an abnormal and 2176 critical edge, so we insert the insn at the end of 2177 the previous block. There are several alternatives 2178 detailed in Morgans book P277 (sec 10.5) for 2179 handling this situation. This one is easiest for 2180 now. */ 2181 2182 if (eg->flags & EDGE_ABNORMAL) 2183 insert_insn_end_basic_block (index_map[j], bb); 2184 else 2185 { 2186 insn = process_insert_insn (index_map[j]); 2187 insert_insn_on_edge (insn, eg); 2188 } 2189 2190 if (dump_file) 2191 { 2192 fprintf (dump_file, "PRE: edge (%d,%d), ", 2193 bb->index, 2194 INDEX_EDGE_SUCC_BB (edge_list, e)->index); 2195 fprintf (dump_file, "copy expression %d\n", 2196 expr->bitmap_index); 2197 } 2198 2199 update_ld_motion_stores (expr); 2200 bitmap_set_bit (inserted[e], j); 2201 did_insert = 1; 2202 gcse_create_count++; 2203 } 2204 } 2205 } 2206 } 2207 } 2208 2209 sbitmap_vector_free (inserted); 2210 return did_insert; 2211 } 2212 2213 /* Copy the result of EXPR->EXPR generated by INSN to EXPR->REACHING_REG. 2214 Given "old_reg <- expr" (INSN), instead of adding after it 2215 reaching_reg <- old_reg 2216 it's better to do the following: 2217 reaching_reg <- expr 2218 old_reg <- reaching_reg 2219 because this way copy propagation can discover additional PRE 2220 opportunities. But if this fails, we try the old way. 2221 When "expr" is a store, i.e. 2222 given "MEM <- old_reg", instead of adding after it 2223 reaching_reg <- old_reg 2224 it's better to add it before as follows: 2225 reaching_reg <- old_reg 2226 MEM <- reaching_reg. */ 2227 2228 static void 2229 pre_insert_copy_insn (struct gcse_expr *expr, rtx_insn *insn) 2230 { 2231 rtx reg = expr->reaching_reg; 2232 int regno = REGNO (reg); 2233 int indx = expr->bitmap_index; 2234 rtx pat = PATTERN (insn); 2235 rtx set, first_set, new_insn; 2236 rtx old_reg; 2237 int i; 2238 2239 /* This block matches the logic in hash_scan_insn. */ 2240 switch (GET_CODE (pat)) 2241 { 2242 case SET: 2243 set = pat; 2244 break; 2245 2246 case PARALLEL: 2247 /* Search through the parallel looking for the set whose 2248 source was the expression that we're interested in. */ 2249 first_set = NULL_RTX; 2250 set = NULL_RTX; 2251 for (i = 0; i < XVECLEN (pat, 0); i++) 2252 { 2253 rtx x = XVECEXP (pat, 0, i); 2254 if (GET_CODE (x) == SET) 2255 { 2256 /* If the source was a REG_EQUAL or REG_EQUIV note, we 2257 may not find an equivalent expression, but in this 2258 case the PARALLEL will have a single set. */ 2259 if (first_set == NULL_RTX) 2260 first_set = x; 2261 if (expr_equiv_p (SET_SRC (x), expr->expr)) 2262 { 2263 set = x; 2264 break; 2265 } 2266 } 2267 } 2268 2269 gcc_assert (first_set); 2270 if (set == NULL_RTX) 2271 set = first_set; 2272 break; 2273 2274 default: 2275 gcc_unreachable (); 2276 } 2277 2278 if (REG_P (SET_DEST (set))) 2279 { 2280 old_reg = SET_DEST (set); 2281 /* Check if we can modify the set destination in the original insn. */ 2282 if (validate_change (insn, &SET_DEST (set), reg, 0)) 2283 { 2284 new_insn = gen_move_insn (old_reg, reg); 2285 new_insn = emit_insn_after (new_insn, insn); 2286 } 2287 else 2288 { 2289 new_insn = gen_move_insn (reg, old_reg); 2290 new_insn = emit_insn_after (new_insn, insn); 2291 } 2292 } 2293 else /* This is possible only in case of a store to memory. */ 2294 { 2295 old_reg = SET_SRC (set); 2296 new_insn = gen_move_insn (reg, old_reg); 2297 2298 /* Check if we can modify the set source in the original insn. */ 2299 if (validate_change (insn, &SET_SRC (set), reg, 0)) 2300 new_insn = emit_insn_before (new_insn, insn); 2301 else 2302 new_insn = emit_insn_after (new_insn, insn); 2303 } 2304 2305 gcse_create_count++; 2306 2307 if (dump_file) 2308 fprintf (dump_file, 2309 "PRE: bb %d, insn %d, copy expression %d in insn %d to reg %d\n", 2310 BLOCK_FOR_INSN (insn)->index, INSN_UID (new_insn), indx, 2311 INSN_UID (insn), regno); 2312 } 2313 2314 /* Copy available expressions that reach the redundant expression 2315 to `reaching_reg'. */ 2316 2317 static void 2318 pre_insert_copies (void) 2319 { 2320 unsigned int i, added_copy; 2321 struct gcse_expr *expr; 2322 struct gcse_occr *occr; 2323 struct gcse_occr *avail; 2324 2325 /* For each available expression in the table, copy the result to 2326 `reaching_reg' if the expression reaches a deleted one. 2327 2328 ??? The current algorithm is rather brute force. 2329 Need to do some profiling. */ 2330 2331 for (i = 0; i < expr_hash_table.size; i++) 2332 for (expr = expr_hash_table.table[i]; expr; expr = expr->next_same_hash) 2333 { 2334 /* If the basic block isn't reachable, PPOUT will be TRUE. However, 2335 we don't want to insert a copy here because the expression may not 2336 really be redundant. So only insert an insn if the expression was 2337 deleted. This test also avoids further processing if the 2338 expression wasn't deleted anywhere. */ 2339 if (expr->reaching_reg == NULL) 2340 continue; 2341 2342 /* Set when we add a copy for that expression. */ 2343 added_copy = 0; 2344 2345 for (occr = expr->antic_occr; occr != NULL; occr = occr->next) 2346 { 2347 if (! occr->deleted_p) 2348 continue; 2349 2350 for (avail = expr->avail_occr; avail != NULL; avail = avail->next) 2351 { 2352 rtx_insn *insn = avail->insn; 2353 2354 /* No need to handle this one if handled already. */ 2355 if (avail->copied_p) 2356 continue; 2357 2358 /* Don't handle this one if it's a redundant one. */ 2359 if (insn->deleted ()) 2360 continue; 2361 2362 /* Or if the expression doesn't reach the deleted one. */ 2363 if (! pre_expr_reaches_here_p (BLOCK_FOR_INSN (avail->insn), 2364 expr, 2365 BLOCK_FOR_INSN (occr->insn))) 2366 continue; 2367 2368 added_copy = 1; 2369 2370 /* Copy the result of avail to reaching_reg. */ 2371 pre_insert_copy_insn (expr, insn); 2372 avail->copied_p = 1; 2373 } 2374 } 2375 2376 if (added_copy) 2377 update_ld_motion_stores (expr); 2378 } 2379 } 2380 2381 struct set_data 2382 { 2383 rtx_insn *insn; 2384 const_rtx set; 2385 int nsets; 2386 }; 2387 2388 /* Increment number of sets and record set in DATA. */ 2389 2390 static void 2391 record_set_data (rtx dest, const_rtx set, void *data) 2392 { 2393 struct set_data *s = (struct set_data *)data; 2394 2395 if (GET_CODE (set) == SET) 2396 { 2397 /* We allow insns having multiple sets, where all but one are 2398 dead as single set insns. In the common case only a single 2399 set is present, so we want to avoid checking for REG_UNUSED 2400 notes unless necessary. */ 2401 if (s->nsets == 1 2402 && find_reg_note (s->insn, REG_UNUSED, SET_DEST (s->set)) 2403 && !side_effects_p (s->set)) 2404 s->nsets = 0; 2405 2406 if (!s->nsets) 2407 { 2408 /* Record this set. */ 2409 s->nsets += 1; 2410 s->set = set; 2411 } 2412 else if (!find_reg_note (s->insn, REG_UNUSED, dest) 2413 || side_effects_p (set)) 2414 s->nsets += 1; 2415 } 2416 } 2417 2418 static const_rtx 2419 single_set_gcse (rtx_insn *insn) 2420 { 2421 struct set_data s; 2422 rtx pattern; 2423 2424 gcc_assert (INSN_P (insn)); 2425 2426 /* Optimize common case. */ 2427 pattern = PATTERN (insn); 2428 if (GET_CODE (pattern) == SET) 2429 return pattern; 2430 2431 s.insn = insn; 2432 s.nsets = 0; 2433 note_stores (pattern, record_set_data, &s); 2434 2435 /* Considered invariant insns have exactly one set. */ 2436 gcc_assert (s.nsets == 1); 2437 return s.set; 2438 } 2439 2440 /* Emit move from SRC to DEST noting the equivalence with expression computed 2441 in INSN. */ 2442 2443 static rtx 2444 gcse_emit_move_after (rtx dest, rtx src, rtx_insn *insn) 2445 { 2446 rtx_insn *new_rtx; 2447 const_rtx set = single_set_gcse (insn); 2448 rtx set2; 2449 rtx note; 2450 rtx eqv = NULL_RTX; 2451 2452 /* This should never fail since we're creating a reg->reg copy 2453 we've verified to be valid. */ 2454 2455 new_rtx = emit_insn_after (gen_move_insn (dest, src), insn); 2456 2457 /* Note the equivalence for local CSE pass. Take the note from the old 2458 set if there was one. Otherwise record the SET_SRC from the old set 2459 unless DEST is also an operand of the SET_SRC. */ 2460 set2 = single_set (new_rtx); 2461 if (!set2 || !rtx_equal_p (SET_DEST (set2), dest)) 2462 return new_rtx; 2463 if ((note = find_reg_equal_equiv_note (insn))) 2464 eqv = XEXP (note, 0); 2465 else if (! REG_P (dest) 2466 || ! reg_mentioned_p (dest, SET_SRC (set))) 2467 eqv = SET_SRC (set); 2468 2469 if (eqv != NULL_RTX) 2470 set_unique_reg_note (new_rtx, REG_EQUAL, copy_insn_1 (eqv)); 2471 2472 return new_rtx; 2473 } 2474 2475 /* Delete redundant computations. 2476 Deletion is done by changing the insn to copy the `reaching_reg' of 2477 the expression into the result of the SET. It is left to later passes 2478 to propagate the copy or eliminate it. 2479 2480 Return nonzero if a change is made. */ 2481 2482 static int 2483 pre_delete (void) 2484 { 2485 unsigned int i; 2486 int changed; 2487 struct gcse_expr *expr; 2488 struct gcse_occr *occr; 2489 2490 changed = 0; 2491 for (i = 0; i < expr_hash_table.size; i++) 2492 for (expr = expr_hash_table.table[i]; expr; expr = expr->next_same_hash) 2493 { 2494 int indx = expr->bitmap_index; 2495 2496 /* We only need to search antic_occr since we require ANTLOC != 0. */ 2497 for (occr = expr->antic_occr; occr != NULL; occr = occr->next) 2498 { 2499 rtx_insn *insn = occr->insn; 2500 rtx set; 2501 basic_block bb = BLOCK_FOR_INSN (insn); 2502 2503 /* We only delete insns that have a single_set. */ 2504 if (bitmap_bit_p (pre_delete_map[bb->index], indx) 2505 && (set = single_set (insn)) != 0 2506 && dbg_cnt (pre_insn)) 2507 { 2508 /* Create a pseudo-reg to store the result of reaching 2509 expressions into. Get the mode for the new pseudo from 2510 the mode of the original destination pseudo. */ 2511 if (expr->reaching_reg == NULL) 2512 expr->reaching_reg = gen_reg_rtx_and_attrs (SET_DEST (set)); 2513 2514 gcse_emit_move_after (SET_DEST (set), expr->reaching_reg, insn); 2515 delete_insn (insn); 2516 occr->deleted_p = 1; 2517 changed = 1; 2518 gcse_subst_count++; 2519 2520 if (dump_file) 2521 { 2522 fprintf (dump_file, 2523 "PRE: redundant insn %d (expression %d) in ", 2524 INSN_UID (insn), indx); 2525 fprintf (dump_file, "bb %d, reaching reg is %d\n", 2526 bb->index, REGNO (expr->reaching_reg)); 2527 } 2528 } 2529 } 2530 } 2531 2532 return changed; 2533 } 2534 2535 /* Perform GCSE optimizations using PRE. 2536 This is called by one_pre_gcse_pass after all the dataflow analysis 2537 has been done. 2538 2539 This is based on the original Morel-Renvoise paper Fred Chow's thesis, and 2540 lazy code motion from Knoop, Ruthing and Steffen as described in Advanced 2541 Compiler Design and Implementation. 2542 2543 ??? A new pseudo reg is created to hold the reaching expression. The nice 2544 thing about the classical approach is that it would try to use an existing 2545 reg. If the register can't be adequately optimized [i.e. we introduce 2546 reload problems], one could add a pass here to propagate the new register 2547 through the block. 2548 2549 ??? We don't handle single sets in PARALLELs because we're [currently] not 2550 able to copy the rest of the parallel when we insert copies to create full 2551 redundancies from partial redundancies. However, there's no reason why we 2552 can't handle PARALLELs in the cases where there are no partial 2553 redundancies. */ 2554 2555 static int 2556 pre_gcse (struct edge_list *edge_list) 2557 { 2558 unsigned int i; 2559 int did_insert, changed; 2560 struct gcse_expr **index_map; 2561 struct gcse_expr *expr; 2562 2563 /* Compute a mapping from expression number (`bitmap_index') to 2564 hash table entry. */ 2565 2566 index_map = XCNEWVEC (struct gcse_expr *, expr_hash_table.n_elems); 2567 for (i = 0; i < expr_hash_table.size; i++) 2568 for (expr = expr_hash_table.table[i]; expr; expr = expr->next_same_hash) 2569 index_map[expr->bitmap_index] = expr; 2570 2571 /* Delete the redundant insns first so that 2572 - we know what register to use for the new insns and for the other 2573 ones with reaching expressions 2574 - we know which insns are redundant when we go to create copies */ 2575 2576 changed = pre_delete (); 2577 did_insert = pre_edge_insert (edge_list, index_map); 2578 2579 /* In other places with reaching expressions, copy the expression to the 2580 specially allocated pseudo-reg that reaches the redundant expr. */ 2581 pre_insert_copies (); 2582 if (did_insert) 2583 { 2584 commit_edge_insertions (); 2585 changed = 1; 2586 } 2587 2588 free (index_map); 2589 return changed; 2590 } 2591 2592 /* Top level routine to perform one PRE GCSE pass. 2593 2594 Return nonzero if a change was made. */ 2595 2596 static int 2597 one_pre_gcse_pass (void) 2598 { 2599 int changed = 0; 2600 2601 gcse_subst_count = 0; 2602 gcse_create_count = 0; 2603 2604 /* Return if there's nothing to do, or it is too expensive. */ 2605 if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1 2606 || is_too_expensive (_("PRE disabled"))) 2607 return 0; 2608 2609 /* We need alias. */ 2610 init_alias_analysis (); 2611 2612 bytes_used = 0; 2613 gcc_obstack_init (&gcse_obstack); 2614 alloc_gcse_mem (); 2615 2616 alloc_hash_table (&expr_hash_table); 2617 add_noreturn_fake_exit_edges (); 2618 if (flag_gcse_lm) 2619 compute_ld_motion_mems (); 2620 2621 compute_hash_table (&expr_hash_table); 2622 if (flag_gcse_lm) 2623 trim_ld_motion_mems (); 2624 if (dump_file) 2625 dump_hash_table (dump_file, "Expression", &expr_hash_table); 2626 2627 if (expr_hash_table.n_elems > 0) 2628 { 2629 struct edge_list *edge_list; 2630 alloc_pre_mem (last_basic_block_for_fn (cfun), expr_hash_table.n_elems); 2631 edge_list = compute_pre_data (); 2632 changed |= pre_gcse (edge_list); 2633 free_edge_list (edge_list); 2634 free_pre_mem (); 2635 } 2636 2637 if (flag_gcse_lm) 2638 free_ld_motion_mems (); 2639 remove_fake_exit_edges (); 2640 free_hash_table (&expr_hash_table); 2641 2642 free_gcse_mem (); 2643 obstack_free (&gcse_obstack, NULL); 2644 2645 /* We are finished with alias. */ 2646 end_alias_analysis (); 2647 2648 if (dump_file) 2649 { 2650 fprintf (dump_file, "PRE GCSE of %s, %d basic blocks, %d bytes needed, ", 2651 current_function_name (), n_basic_blocks_for_fn (cfun), 2652 bytes_used); 2653 fprintf (dump_file, "%d substs, %d insns created\n", 2654 gcse_subst_count, gcse_create_count); 2655 } 2656 2657 return changed; 2658 } 2659 2660 /* If X contains any LABEL_REF's, add REG_LABEL_OPERAND notes for them 2661 to INSN. If such notes are added to an insn which references a 2662 CODE_LABEL, the LABEL_NUSES count is incremented. We have to add 2663 that note, because the following loop optimization pass requires 2664 them. */ 2665 2666 /* ??? If there was a jump optimization pass after gcse and before loop, 2667 then we would not need to do this here, because jump would add the 2668 necessary REG_LABEL_OPERAND and REG_LABEL_TARGET notes. */ 2669 2670 static void 2671 add_label_notes (rtx x, rtx insn) 2672 { 2673 enum rtx_code code = GET_CODE (x); 2674 int i, j; 2675 const char *fmt; 2676 2677 if (code == LABEL_REF && !LABEL_REF_NONLOCAL_P (x)) 2678 { 2679 /* This code used to ignore labels that referred to dispatch tables to 2680 avoid flow generating (slightly) worse code. 2681 2682 We no longer ignore such label references (see LABEL_REF handling in 2683 mark_jump_label for additional information). */ 2684 2685 /* There's no reason for current users to emit jump-insns with 2686 such a LABEL_REF, so we don't have to handle REG_LABEL_TARGET 2687 notes. */ 2688 gcc_assert (!JUMP_P (insn)); 2689 add_reg_note (insn, REG_LABEL_OPERAND, LABEL_REF_LABEL (x)); 2690 2691 if (LABEL_P (LABEL_REF_LABEL (x))) 2692 LABEL_NUSES (LABEL_REF_LABEL (x))++; 2693 2694 return; 2695 } 2696 2697 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--) 2698 { 2699 if (fmt[i] == 'e') 2700 add_label_notes (XEXP (x, i), insn); 2701 else if (fmt[i] == 'E') 2702 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 2703 add_label_notes (XVECEXP (x, i, j), insn); 2704 } 2705 } 2706 2707 /* Code Hoisting variables and subroutines. */ 2708 2709 /* Very busy expressions. */ 2710 static sbitmap *hoist_vbein; 2711 static sbitmap *hoist_vbeout; 2712 2713 /* ??? We could compute post dominators and run this algorithm in 2714 reverse to perform tail merging, doing so would probably be 2715 more effective than the tail merging code in jump.c. 2716 2717 It's unclear if tail merging could be run in parallel with 2718 code hoisting. It would be nice. */ 2719 2720 /* Allocate vars used for code hoisting analysis. */ 2721 2722 static void 2723 alloc_code_hoist_mem (int n_blocks, int n_exprs) 2724 { 2725 antloc = sbitmap_vector_alloc (n_blocks, n_exprs); 2726 transp = sbitmap_vector_alloc (n_blocks, n_exprs); 2727 comp = sbitmap_vector_alloc (n_blocks, n_exprs); 2728 2729 hoist_vbein = sbitmap_vector_alloc (n_blocks, n_exprs); 2730 hoist_vbeout = sbitmap_vector_alloc (n_blocks, n_exprs); 2731 } 2732 2733 /* Free vars used for code hoisting analysis. */ 2734 2735 static void 2736 free_code_hoist_mem (void) 2737 { 2738 sbitmap_vector_free (antloc); 2739 sbitmap_vector_free (transp); 2740 sbitmap_vector_free (comp); 2741 2742 sbitmap_vector_free (hoist_vbein); 2743 sbitmap_vector_free (hoist_vbeout); 2744 2745 free_dominance_info (CDI_DOMINATORS); 2746 } 2747 2748 /* Compute the very busy expressions at entry/exit from each block. 2749 2750 An expression is very busy if all paths from a given point 2751 compute the expression. */ 2752 2753 static void 2754 compute_code_hoist_vbeinout (void) 2755 { 2756 int changed, passes; 2757 basic_block bb; 2758 2759 bitmap_vector_clear (hoist_vbeout, last_basic_block_for_fn (cfun)); 2760 bitmap_vector_clear (hoist_vbein, last_basic_block_for_fn (cfun)); 2761 2762 passes = 0; 2763 changed = 1; 2764 2765 while (changed) 2766 { 2767 changed = 0; 2768 2769 /* We scan the blocks in the reverse order to speed up 2770 the convergence. */ 2771 FOR_EACH_BB_REVERSE_FN (bb, cfun) 2772 { 2773 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun)) 2774 { 2775 bitmap_intersection_of_succs (hoist_vbeout[bb->index], 2776 hoist_vbein, bb); 2777 2778 /* Include expressions in VBEout that are calculated 2779 in BB and available at its end. */ 2780 bitmap_ior (hoist_vbeout[bb->index], 2781 hoist_vbeout[bb->index], comp[bb->index]); 2782 } 2783 2784 changed |= bitmap_or_and (hoist_vbein[bb->index], 2785 antloc[bb->index], 2786 hoist_vbeout[bb->index], 2787 transp[bb->index]); 2788 } 2789 2790 passes++; 2791 } 2792 2793 if (dump_file) 2794 { 2795 fprintf (dump_file, "hoisting vbeinout computation: %d passes\n", passes); 2796 2797 FOR_EACH_BB_FN (bb, cfun) 2798 { 2799 fprintf (dump_file, "vbein (%d): ", bb->index); 2800 dump_bitmap_file (dump_file, hoist_vbein[bb->index]); 2801 fprintf (dump_file, "vbeout(%d): ", bb->index); 2802 dump_bitmap_file (dump_file, hoist_vbeout[bb->index]); 2803 } 2804 } 2805 } 2806 2807 /* Top level routine to do the dataflow analysis needed by code hoisting. */ 2808 2809 static void 2810 compute_code_hoist_data (void) 2811 { 2812 compute_local_properties (transp, comp, antloc, &expr_hash_table); 2813 prune_expressions (false); 2814 compute_code_hoist_vbeinout (); 2815 calculate_dominance_info (CDI_DOMINATORS); 2816 if (dump_file) 2817 fprintf (dump_file, "\n"); 2818 } 2819 2820 /* Update register pressure for BB when hoisting an expression from 2821 instruction FROM, if live ranges of inputs are shrunk. Also 2822 maintain live_in information if live range of register referred 2823 in FROM is shrunk. 2824 2825 Return 0 if register pressure doesn't change, otherwise return 2826 the number by which register pressure is decreased. 2827 2828 NOTE: Register pressure won't be increased in this function. */ 2829 2830 static int 2831 update_bb_reg_pressure (basic_block bb, rtx_insn *from) 2832 { 2833 rtx dreg; 2834 rtx_insn *insn; 2835 basic_block succ_bb; 2836 df_ref use, op_ref; 2837 edge succ; 2838 edge_iterator ei; 2839 int decreased_pressure = 0; 2840 int nregs; 2841 enum reg_class pressure_class; 2842 2843 FOR_EACH_INSN_USE (use, from) 2844 { 2845 dreg = DF_REF_REAL_REG (use); 2846 /* The live range of register is shrunk only if it isn't: 2847 1. referred on any path from the end of this block to EXIT, or 2848 2. referred by insns other than FROM in this block. */ 2849 FOR_EACH_EDGE (succ, ei, bb->succs) 2850 { 2851 succ_bb = succ->dest; 2852 if (succ_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)) 2853 continue; 2854 2855 if (bitmap_bit_p (BB_DATA (succ_bb)->live_in, REGNO (dreg))) 2856 break; 2857 } 2858 if (succ != NULL) 2859 continue; 2860 2861 op_ref = DF_REG_USE_CHAIN (REGNO (dreg)); 2862 for (; op_ref; op_ref = DF_REF_NEXT_REG (op_ref)) 2863 { 2864 if (!DF_REF_INSN_INFO (op_ref)) 2865 continue; 2866 2867 insn = DF_REF_INSN (op_ref); 2868 if (BLOCK_FOR_INSN (insn) == bb 2869 && NONDEBUG_INSN_P (insn) && insn != from) 2870 break; 2871 } 2872 2873 pressure_class = get_regno_pressure_class (REGNO (dreg), &nregs); 2874 /* Decrease register pressure and update live_in information for 2875 this block. */ 2876 if (!op_ref && pressure_class != NO_REGS) 2877 { 2878 decreased_pressure += nregs; 2879 BB_DATA (bb)->max_reg_pressure[pressure_class] -= nregs; 2880 bitmap_clear_bit (BB_DATA (bb)->live_in, REGNO (dreg)); 2881 } 2882 } 2883 return decreased_pressure; 2884 } 2885 2886 /* Determine if the expression EXPR should be hoisted to EXPR_BB up in 2887 flow graph, if it can reach BB unimpared. Stop the search if the 2888 expression would need to be moved more than DISTANCE instructions. 2889 2890 DISTANCE is the number of instructions through which EXPR can be 2891 hoisted up in flow graph. 2892 2893 BB_SIZE points to an array which contains the number of instructions 2894 for each basic block. 2895 2896 PRESSURE_CLASS and NREGS are register class and number of hard registers 2897 for storing EXPR. 2898 2899 HOISTED_BBS points to a bitmap indicating basic blocks through which 2900 EXPR is hoisted. 2901 2902 FROM is the instruction from which EXPR is hoisted. 2903 2904 It's unclear exactly what Muchnick meant by "unimpared". It seems 2905 to me that the expression must either be computed or transparent in 2906 *every* block in the path(s) from EXPR_BB to BB. Any other definition 2907 would allow the expression to be hoisted out of loops, even if 2908 the expression wasn't a loop invariant. 2909 2910 Contrast this to reachability for PRE where an expression is 2911 considered reachable if *any* path reaches instead of *all* 2912 paths. */ 2913 2914 static int 2915 should_hoist_expr_to_dom (basic_block expr_bb, struct gcse_expr *expr, 2916 basic_block bb, sbitmap visited, 2917 HOST_WIDE_INT distance, 2918 int *bb_size, enum reg_class pressure_class, 2919 int *nregs, bitmap hoisted_bbs, rtx_insn *from) 2920 { 2921 unsigned int i; 2922 edge pred; 2923 edge_iterator ei; 2924 sbitmap_iterator sbi; 2925 int visited_allocated_locally = 0; 2926 int decreased_pressure = 0; 2927 2928 if (flag_ira_hoist_pressure) 2929 { 2930 /* Record old information of basic block BB when it is visited 2931 at the first time. */ 2932 if (!bitmap_bit_p (hoisted_bbs, bb->index)) 2933 { 2934 struct bb_data *data = BB_DATA (bb); 2935 bitmap_copy (data->backup, data->live_in); 2936 data->old_pressure = data->max_reg_pressure[pressure_class]; 2937 } 2938 decreased_pressure = update_bb_reg_pressure (bb, from); 2939 } 2940 /* Terminate the search if distance, for which EXPR is allowed to move, 2941 is exhausted. */ 2942 if (distance > 0) 2943 { 2944 if (flag_ira_hoist_pressure) 2945 { 2946 /* Prefer to hoist EXPR if register pressure is decreased. */ 2947 if (decreased_pressure > *nregs) 2948 distance += bb_size[bb->index]; 2949 /* Let EXPR be hoisted through basic block at no cost if one 2950 of following conditions is satisfied: 2951 2952 1. The basic block has low register pressure. 2953 2. Register pressure won't be increases after hoisting EXPR. 2954 2955 Constant expressions is handled conservatively, because 2956 hoisting constant expression aggressively results in worse 2957 code. This decision is made by the observation of CSiBE 2958 on ARM target, while it has no obvious effect on other 2959 targets like x86, x86_64, mips and powerpc. */ 2960 else if (CONST_INT_P (expr->expr) 2961 || (BB_DATA (bb)->max_reg_pressure[pressure_class] 2962 >= ira_class_hard_regs_num[pressure_class] 2963 && decreased_pressure < *nregs)) 2964 distance -= bb_size[bb->index]; 2965 } 2966 else 2967 distance -= bb_size[bb->index]; 2968 2969 if (distance <= 0) 2970 return 0; 2971 } 2972 else 2973 gcc_assert (distance == 0); 2974 2975 if (visited == NULL) 2976 { 2977 visited_allocated_locally = 1; 2978 visited = sbitmap_alloc (last_basic_block_for_fn (cfun)); 2979 bitmap_clear (visited); 2980 } 2981 2982 FOR_EACH_EDGE (pred, ei, bb->preds) 2983 { 2984 basic_block pred_bb = pred->src; 2985 2986 if (pred->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)) 2987 break; 2988 else if (pred_bb == expr_bb) 2989 continue; 2990 else if (bitmap_bit_p (visited, pred_bb->index)) 2991 continue; 2992 else if (! bitmap_bit_p (transp[pred_bb->index], expr->bitmap_index)) 2993 break; 2994 /* Not killed. */ 2995 else 2996 { 2997 bitmap_set_bit (visited, pred_bb->index); 2998 if (! should_hoist_expr_to_dom (expr_bb, expr, pred_bb, 2999 visited, distance, bb_size, 3000 pressure_class, nregs, 3001 hoisted_bbs, from)) 3002 break; 3003 } 3004 } 3005 if (visited_allocated_locally) 3006 { 3007 /* If EXPR can be hoisted to expr_bb, record basic blocks through 3008 which EXPR is hoisted in hoisted_bbs. */ 3009 if (flag_ira_hoist_pressure && !pred) 3010 { 3011 /* Record the basic block from which EXPR is hoisted. */ 3012 bitmap_set_bit (visited, bb->index); 3013 EXECUTE_IF_SET_IN_BITMAP (visited, 0, i, sbi) 3014 bitmap_set_bit (hoisted_bbs, i); 3015 } 3016 sbitmap_free (visited); 3017 } 3018 3019 return (pred == NULL); 3020 } 3021 3022 /* Find occurrence in BB. */ 3023 3024 static struct gcse_occr * 3025 find_occr_in_bb (struct gcse_occr *occr, basic_block bb) 3026 { 3027 /* Find the right occurrence of this expression. */ 3028 while (occr && BLOCK_FOR_INSN (occr->insn) != bb) 3029 occr = occr->next; 3030 3031 return occr; 3032 } 3033 3034 /* Actually perform code hoisting. 3035 3036 The code hoisting pass can hoist multiple computations of the same 3037 expression along dominated path to a dominating basic block, like 3038 from b2/b3 to b1 as depicted below: 3039 3040 b1 ------ 3041 /\ | 3042 / \ | 3043 bx by distance 3044 / \ | 3045 / \ | 3046 b2 b3 ------ 3047 3048 Unfortunately code hoisting generally extends the live range of an 3049 output pseudo register, which increases register pressure and hurts 3050 register allocation. To address this issue, an attribute MAX_DISTANCE 3051 is computed and attached to each expression. The attribute is computed 3052 from rtx cost of the corresponding expression and it's used to control 3053 how long the expression can be hoisted up in flow graph. As the 3054 expression is hoisted up in flow graph, GCC decreases its DISTANCE 3055 and stops the hoist if DISTANCE reaches 0. Code hoisting can decrease 3056 register pressure if live ranges of inputs are shrunk. 3057 3058 Option "-fira-hoist-pressure" implements register pressure directed 3059 hoist based on upper method. The rationale is: 3060 1. Calculate register pressure for each basic block by reusing IRA 3061 facility. 3062 2. When expression is hoisted through one basic block, GCC checks 3063 the change of live ranges for inputs/output. The basic block's 3064 register pressure will be increased because of extended live 3065 range of output. However, register pressure will be decreased 3066 if the live ranges of inputs are shrunk. 3067 3. After knowing how hoisting affects register pressure, GCC prefers 3068 to hoist the expression if it can decrease register pressure, by 3069 increasing DISTANCE of the corresponding expression. 3070 4. If hoisting the expression increases register pressure, GCC checks 3071 register pressure of the basic block and decrease DISTANCE only if 3072 the register pressure is high. In other words, expression will be 3073 hoisted through at no cost if the basic block has low register 3074 pressure. 3075 5. Update register pressure information for basic blocks through 3076 which expression is hoisted. */ 3077 3078 static int 3079 hoist_code (void) 3080 { 3081 basic_block bb, dominated; 3082 vec<basic_block> dom_tree_walk; 3083 unsigned int dom_tree_walk_index; 3084 vec<basic_block> domby; 3085 unsigned int i, j, k; 3086 struct gcse_expr **index_map; 3087 struct gcse_expr *expr; 3088 int *to_bb_head; 3089 int *bb_size; 3090 int changed = 0; 3091 struct bb_data *data; 3092 /* Basic blocks that have occurrences reachable from BB. */ 3093 bitmap from_bbs; 3094 /* Basic blocks through which expr is hoisted. */ 3095 bitmap hoisted_bbs = NULL; 3096 bitmap_iterator bi; 3097 3098 /* Compute a mapping from expression number (`bitmap_index') to 3099 hash table entry. */ 3100 3101 index_map = XCNEWVEC (struct gcse_expr *, expr_hash_table.n_elems); 3102 for (i = 0; i < expr_hash_table.size; i++) 3103 for (expr = expr_hash_table.table[i]; expr; expr = expr->next_same_hash) 3104 index_map[expr->bitmap_index] = expr; 3105 3106 /* Calculate sizes of basic blocks and note how far 3107 each instruction is from the start of its block. We then use this 3108 data to restrict distance an expression can travel. */ 3109 3110 to_bb_head = XCNEWVEC (int, get_max_uid ()); 3111 bb_size = XCNEWVEC (int, last_basic_block_for_fn (cfun)); 3112 3113 FOR_EACH_BB_FN (bb, cfun) 3114 { 3115 rtx_insn *insn; 3116 int to_head; 3117 3118 to_head = 0; 3119 FOR_BB_INSNS (bb, insn) 3120 { 3121 /* Don't count debug instructions to avoid them affecting 3122 decision choices. */ 3123 if (NONDEBUG_INSN_P (insn)) 3124 to_bb_head[INSN_UID (insn)] = to_head++; 3125 } 3126 3127 bb_size[bb->index] = to_head; 3128 } 3129 3130 gcc_assert (EDGE_COUNT (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs) == 1 3131 && (EDGE_SUCC (ENTRY_BLOCK_PTR_FOR_FN (cfun), 0)->dest 3132 == ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb)); 3133 3134 from_bbs = BITMAP_ALLOC (NULL); 3135 if (flag_ira_hoist_pressure) 3136 hoisted_bbs = BITMAP_ALLOC (NULL); 3137 3138 dom_tree_walk = get_all_dominated_blocks (CDI_DOMINATORS, 3139 ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb); 3140 3141 /* Walk over each basic block looking for potentially hoistable 3142 expressions, nothing gets hoisted from the entry block. */ 3143 FOR_EACH_VEC_ELT (dom_tree_walk, dom_tree_walk_index, bb) 3144 { 3145 domby = get_dominated_to_depth (CDI_DOMINATORS, bb, MAX_HOIST_DEPTH); 3146 3147 if (domby.length () == 0) 3148 continue; 3149 3150 /* Examine each expression that is very busy at the exit of this 3151 block. These are the potentially hoistable expressions. */ 3152 for (i = 0; i < SBITMAP_SIZE (hoist_vbeout[bb->index]); i++) 3153 { 3154 if (bitmap_bit_p (hoist_vbeout[bb->index], i)) 3155 { 3156 int nregs = 0; 3157 enum reg_class pressure_class = NO_REGS; 3158 /* Current expression. */ 3159 struct gcse_expr *expr = index_map[i]; 3160 /* Number of occurrences of EXPR that can be hoisted to BB. */ 3161 int hoistable = 0; 3162 /* Occurrences reachable from BB. */ 3163 vec<occr_t> occrs_to_hoist = vNULL; 3164 /* We want to insert the expression into BB only once, so 3165 note when we've inserted it. */ 3166 int insn_inserted_p; 3167 occr_t occr; 3168 3169 /* If an expression is computed in BB and is available at end of 3170 BB, hoist all occurrences dominated by BB to BB. */ 3171 if (bitmap_bit_p (comp[bb->index], i)) 3172 { 3173 occr = find_occr_in_bb (expr->antic_occr, bb); 3174 3175 if (occr) 3176 { 3177 /* An occurrence might've been already deleted 3178 while processing a dominator of BB. */ 3179 if (!occr->deleted_p) 3180 { 3181 gcc_assert (NONDEBUG_INSN_P (occr->insn)); 3182 hoistable++; 3183 } 3184 } 3185 else 3186 hoistable++; 3187 } 3188 3189 /* We've found a potentially hoistable expression, now 3190 we look at every block BB dominates to see if it 3191 computes the expression. */ 3192 FOR_EACH_VEC_ELT (domby, j, dominated) 3193 { 3194 HOST_WIDE_INT max_distance; 3195 3196 /* Ignore self dominance. */ 3197 if (bb == dominated) 3198 continue; 3199 /* We've found a dominated block, now see if it computes 3200 the busy expression and whether or not moving that 3201 expression to the "beginning" of that block is safe. */ 3202 if (!bitmap_bit_p (antloc[dominated->index], i)) 3203 continue; 3204 3205 occr = find_occr_in_bb (expr->antic_occr, dominated); 3206 gcc_assert (occr); 3207 3208 /* An occurrence might've been already deleted 3209 while processing a dominator of BB. */ 3210 if (occr->deleted_p) 3211 continue; 3212 gcc_assert (NONDEBUG_INSN_P (occr->insn)); 3213 3214 max_distance = expr->max_distance; 3215 if (max_distance > 0) 3216 /* Adjust MAX_DISTANCE to account for the fact that 3217 OCCR won't have to travel all of DOMINATED, but 3218 only part of it. */ 3219 max_distance += (bb_size[dominated->index] 3220 - to_bb_head[INSN_UID (occr->insn)]); 3221 3222 pressure_class = get_pressure_class_and_nregs (occr->insn, 3223 &nregs); 3224 3225 /* Note if the expression should be hoisted from the dominated 3226 block to BB if it can reach DOMINATED unimpared. 3227 3228 Keep track of how many times this expression is hoistable 3229 from a dominated block into BB. */ 3230 if (should_hoist_expr_to_dom (bb, expr, dominated, NULL, 3231 max_distance, bb_size, 3232 pressure_class, &nregs, 3233 hoisted_bbs, occr->insn)) 3234 { 3235 hoistable++; 3236 occrs_to_hoist.safe_push (occr); 3237 bitmap_set_bit (from_bbs, dominated->index); 3238 } 3239 } 3240 3241 /* If we found more than one hoistable occurrence of this 3242 expression, then note it in the vector of expressions to 3243 hoist. It makes no sense to hoist things which are computed 3244 in only one BB, and doing so tends to pessimize register 3245 allocation. One could increase this value to try harder 3246 to avoid any possible code expansion due to register 3247 allocation issues; however experiments have shown that 3248 the vast majority of hoistable expressions are only movable 3249 from two successors, so raising this threshold is likely 3250 to nullify any benefit we get from code hoisting. */ 3251 if (hoistable > 1 && dbg_cnt (hoist_insn)) 3252 { 3253 /* If (hoistable != vec::length), then there is 3254 an occurrence of EXPR in BB itself. Don't waste 3255 time looking for LCA in this case. */ 3256 if ((unsigned) hoistable == occrs_to_hoist.length ()) 3257 { 3258 basic_block lca; 3259 3260 lca = nearest_common_dominator_for_set (CDI_DOMINATORS, 3261 from_bbs); 3262 if (lca != bb) 3263 /* Punt, it's better to hoist these occurrences to 3264 LCA. */ 3265 occrs_to_hoist.release (); 3266 } 3267 } 3268 else 3269 /* Punt, no point hoisting a single occurrence. */ 3270 occrs_to_hoist.release (); 3271 3272 if (flag_ira_hoist_pressure 3273 && !occrs_to_hoist.is_empty ()) 3274 { 3275 /* Increase register pressure of basic blocks to which 3276 expr is hoisted because of extended live range of 3277 output. */ 3278 data = BB_DATA (bb); 3279 data->max_reg_pressure[pressure_class] += nregs; 3280 EXECUTE_IF_SET_IN_BITMAP (hoisted_bbs, 0, k, bi) 3281 { 3282 data = BB_DATA (BASIC_BLOCK_FOR_FN (cfun, k)); 3283 data->max_reg_pressure[pressure_class] += nregs; 3284 } 3285 } 3286 else if (flag_ira_hoist_pressure) 3287 { 3288 /* Restore register pressure and live_in info for basic 3289 blocks recorded in hoisted_bbs when expr will not be 3290 hoisted. */ 3291 EXECUTE_IF_SET_IN_BITMAP (hoisted_bbs, 0, k, bi) 3292 { 3293 data = BB_DATA (BASIC_BLOCK_FOR_FN (cfun, k)); 3294 bitmap_copy (data->live_in, data->backup); 3295 data->max_reg_pressure[pressure_class] 3296 = data->old_pressure; 3297 } 3298 } 3299 3300 if (flag_ira_hoist_pressure) 3301 bitmap_clear (hoisted_bbs); 3302 3303 insn_inserted_p = 0; 3304 3305 /* Walk through occurrences of I'th expressions we want 3306 to hoist to BB and make the transformations. */ 3307 FOR_EACH_VEC_ELT (occrs_to_hoist, j, occr) 3308 { 3309 rtx_insn *insn; 3310 const_rtx set; 3311 3312 gcc_assert (!occr->deleted_p); 3313 3314 insn = occr->insn; 3315 set = single_set_gcse (insn); 3316 3317 /* Create a pseudo-reg to store the result of reaching 3318 expressions into. Get the mode for the new pseudo 3319 from the mode of the original destination pseudo. 3320 3321 It is important to use new pseudos whenever we 3322 emit a set. This will allow reload to use 3323 rematerialization for such registers. */ 3324 if (!insn_inserted_p) 3325 expr->reaching_reg 3326 = gen_reg_rtx_and_attrs (SET_DEST (set)); 3327 3328 gcse_emit_move_after (SET_DEST (set), expr->reaching_reg, 3329 insn); 3330 delete_insn (insn); 3331 occr->deleted_p = 1; 3332 changed = 1; 3333 gcse_subst_count++; 3334 3335 if (!insn_inserted_p) 3336 { 3337 insert_insn_end_basic_block (expr, bb); 3338 insn_inserted_p = 1; 3339 } 3340 } 3341 3342 occrs_to_hoist.release (); 3343 bitmap_clear (from_bbs); 3344 } 3345 } 3346 domby.release (); 3347 } 3348 3349 dom_tree_walk.release (); 3350 BITMAP_FREE (from_bbs); 3351 if (flag_ira_hoist_pressure) 3352 BITMAP_FREE (hoisted_bbs); 3353 3354 free (bb_size); 3355 free (to_bb_head); 3356 free (index_map); 3357 3358 return changed; 3359 } 3360 3361 /* Return pressure class and number of needed hard registers (through 3362 *NREGS) of register REGNO. */ 3363 static enum reg_class 3364 get_regno_pressure_class (int regno, int *nregs) 3365 { 3366 if (regno >= FIRST_PSEUDO_REGISTER) 3367 { 3368 enum reg_class pressure_class; 3369 3370 pressure_class = reg_allocno_class (regno); 3371 pressure_class = ira_pressure_class_translate[pressure_class]; 3372 *nregs 3373 = ira_reg_class_max_nregs[pressure_class][PSEUDO_REGNO_MODE (regno)]; 3374 return pressure_class; 3375 } 3376 else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno) 3377 && ! TEST_HARD_REG_BIT (eliminable_regset, regno)) 3378 { 3379 *nregs = 1; 3380 return ira_pressure_class_translate[REGNO_REG_CLASS (regno)]; 3381 } 3382 else 3383 { 3384 *nregs = 0; 3385 return NO_REGS; 3386 } 3387 } 3388 3389 /* Return pressure class and number of hard registers (through *NREGS) 3390 for destination of INSN. */ 3391 static enum reg_class 3392 get_pressure_class_and_nregs (rtx_insn *insn, int *nregs) 3393 { 3394 rtx reg; 3395 enum reg_class pressure_class; 3396 const_rtx set = single_set_gcse (insn); 3397 3398 reg = SET_DEST (set); 3399 if (GET_CODE (reg) == SUBREG) 3400 reg = SUBREG_REG (reg); 3401 if (MEM_P (reg)) 3402 { 3403 *nregs = 0; 3404 pressure_class = NO_REGS; 3405 } 3406 else 3407 { 3408 gcc_assert (REG_P (reg)); 3409 pressure_class = reg_allocno_class (REGNO (reg)); 3410 pressure_class = ira_pressure_class_translate[pressure_class]; 3411 *nregs 3412 = ira_reg_class_max_nregs[pressure_class][GET_MODE (SET_SRC (set))]; 3413 } 3414 return pressure_class; 3415 } 3416 3417 /* Increase (if INCR_P) or decrease current register pressure for 3418 register REGNO. */ 3419 static void 3420 change_pressure (int regno, bool incr_p) 3421 { 3422 int nregs; 3423 enum reg_class pressure_class; 3424 3425 pressure_class = get_regno_pressure_class (regno, &nregs); 3426 if (! incr_p) 3427 curr_reg_pressure[pressure_class] -= nregs; 3428 else 3429 { 3430 curr_reg_pressure[pressure_class] += nregs; 3431 if (BB_DATA (curr_bb)->max_reg_pressure[pressure_class] 3432 < curr_reg_pressure[pressure_class]) 3433 BB_DATA (curr_bb)->max_reg_pressure[pressure_class] 3434 = curr_reg_pressure[pressure_class]; 3435 } 3436 } 3437 3438 /* Calculate register pressure for each basic block by walking insns 3439 from last to first. */ 3440 static void 3441 calculate_bb_reg_pressure (void) 3442 { 3443 int i; 3444 unsigned int j; 3445 rtx_insn *insn; 3446 basic_block bb; 3447 bitmap curr_regs_live; 3448 bitmap_iterator bi; 3449 3450 3451 ira_setup_eliminable_regset (); 3452 curr_regs_live = BITMAP_ALLOC (®_obstack); 3453 FOR_EACH_BB_FN (bb, cfun) 3454 { 3455 curr_bb = bb; 3456 BB_DATA (bb)->live_in = BITMAP_ALLOC (NULL); 3457 BB_DATA (bb)->backup = BITMAP_ALLOC (NULL); 3458 bitmap_copy (BB_DATA (bb)->live_in, df_get_live_in (bb)); 3459 bitmap_copy (curr_regs_live, df_get_live_out (bb)); 3460 for (i = 0; i < ira_pressure_classes_num; i++) 3461 curr_reg_pressure[ira_pressure_classes[i]] = 0; 3462 EXECUTE_IF_SET_IN_BITMAP (curr_regs_live, 0, j, bi) 3463 change_pressure (j, true); 3464 3465 FOR_BB_INSNS_REVERSE (bb, insn) 3466 { 3467 rtx dreg; 3468 int regno; 3469 df_ref def, use; 3470 3471 if (! NONDEBUG_INSN_P (insn)) 3472 continue; 3473 3474 FOR_EACH_INSN_DEF (def, insn) 3475 { 3476 dreg = DF_REF_REAL_REG (def); 3477 gcc_assert (REG_P (dreg)); 3478 regno = REGNO (dreg); 3479 if (!(DF_REF_FLAGS (def) 3480 & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))) 3481 { 3482 if (bitmap_clear_bit (curr_regs_live, regno)) 3483 change_pressure (regno, false); 3484 } 3485 } 3486 3487 FOR_EACH_INSN_USE (use, insn) 3488 { 3489 dreg = DF_REF_REAL_REG (use); 3490 gcc_assert (REG_P (dreg)); 3491 regno = REGNO (dreg); 3492 if (bitmap_set_bit (curr_regs_live, regno)) 3493 change_pressure (regno, true); 3494 } 3495 } 3496 } 3497 BITMAP_FREE (curr_regs_live); 3498 3499 if (dump_file == NULL) 3500 return; 3501 3502 fprintf (dump_file, "\nRegister Pressure: \n"); 3503 FOR_EACH_BB_FN (bb, cfun) 3504 { 3505 fprintf (dump_file, " Basic block %d: \n", bb->index); 3506 for (i = 0; (int) i < ira_pressure_classes_num; i++) 3507 { 3508 enum reg_class pressure_class; 3509 3510 pressure_class = ira_pressure_classes[i]; 3511 if (BB_DATA (bb)->max_reg_pressure[pressure_class] == 0) 3512 continue; 3513 3514 fprintf (dump_file, " %s=%d\n", reg_class_names[pressure_class], 3515 BB_DATA (bb)->max_reg_pressure[pressure_class]); 3516 } 3517 } 3518 fprintf (dump_file, "\n"); 3519 } 3520 3521 /* Top level routine to perform one code hoisting (aka unification) pass 3522 3523 Return nonzero if a change was made. */ 3524 3525 static int 3526 one_code_hoisting_pass (void) 3527 { 3528 int changed = 0; 3529 3530 gcse_subst_count = 0; 3531 gcse_create_count = 0; 3532 3533 /* Return if there's nothing to do, or it is too expensive. */ 3534 if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1 3535 || is_too_expensive (_("GCSE disabled"))) 3536 return 0; 3537 3538 doing_code_hoisting_p = true; 3539 3540 /* Calculate register pressure for each basic block. */ 3541 if (flag_ira_hoist_pressure) 3542 { 3543 regstat_init_n_sets_and_refs (); 3544 ira_set_pseudo_classes (false, dump_file); 3545 alloc_aux_for_blocks (sizeof (struct bb_data)); 3546 calculate_bb_reg_pressure (); 3547 regstat_free_n_sets_and_refs (); 3548 } 3549 3550 /* We need alias. */ 3551 init_alias_analysis (); 3552 3553 bytes_used = 0; 3554 gcc_obstack_init (&gcse_obstack); 3555 alloc_gcse_mem (); 3556 3557 alloc_hash_table (&expr_hash_table); 3558 compute_hash_table (&expr_hash_table); 3559 if (dump_file) 3560 dump_hash_table (dump_file, "Code Hosting Expressions", &expr_hash_table); 3561 3562 if (expr_hash_table.n_elems > 0) 3563 { 3564 alloc_code_hoist_mem (last_basic_block_for_fn (cfun), 3565 expr_hash_table.n_elems); 3566 compute_code_hoist_data (); 3567 changed = hoist_code (); 3568 free_code_hoist_mem (); 3569 } 3570 3571 if (flag_ira_hoist_pressure) 3572 { 3573 free_aux_for_blocks (); 3574 free_reg_info (); 3575 } 3576 free_hash_table (&expr_hash_table); 3577 free_gcse_mem (); 3578 obstack_free (&gcse_obstack, NULL); 3579 3580 /* We are finished with alias. */ 3581 end_alias_analysis (); 3582 3583 if (dump_file) 3584 { 3585 fprintf (dump_file, "HOIST of %s, %d basic blocks, %d bytes needed, ", 3586 current_function_name (), n_basic_blocks_for_fn (cfun), 3587 bytes_used); 3588 fprintf (dump_file, "%d substs, %d insns created\n", 3589 gcse_subst_count, gcse_create_count); 3590 } 3591 3592 doing_code_hoisting_p = false; 3593 3594 return changed; 3595 } 3596 3597 /* Here we provide the things required to do store motion towards the exit. 3598 In order for this to be effective, gcse also needed to be taught how to 3599 move a load when it is killed only by a store to itself. 3600 3601 int i; 3602 float a[10]; 3603 3604 void foo(float scale) 3605 { 3606 for (i=0; i<10; i++) 3607 a[i] *= scale; 3608 } 3609 3610 'i' is both loaded and stored to in the loop. Normally, gcse cannot move 3611 the load out since its live around the loop, and stored at the bottom 3612 of the loop. 3613 3614 The 'Load Motion' referred to and implemented in this file is 3615 an enhancement to gcse which when using edge based LCM, recognizes 3616 this situation and allows gcse to move the load out of the loop. 3617 3618 Once gcse has hoisted the load, store motion can then push this 3619 load towards the exit, and we end up with no loads or stores of 'i' 3620 in the loop. */ 3621 3622 /* This will search the ldst list for a matching expression. If it 3623 doesn't find one, we create one and initialize it. */ 3624 3625 static struct ls_expr * 3626 ldst_entry (rtx x) 3627 { 3628 int do_not_record_p = 0; 3629 struct ls_expr * ptr; 3630 unsigned int hash; 3631 ls_expr **slot; 3632 struct ls_expr e; 3633 3634 hash = hash_rtx (x, GET_MODE (x), &do_not_record_p, 3635 NULL, /*have_reg_qty=*/false); 3636 3637 e.pattern = x; 3638 slot = pre_ldst_table->find_slot_with_hash (&e, hash, INSERT); 3639 if (*slot) 3640 return *slot; 3641 3642 ptr = XNEW (struct ls_expr); 3643 3644 ptr->next = pre_ldst_mems; 3645 ptr->expr = NULL; 3646 ptr->pattern = x; 3647 ptr->pattern_regs = NULL_RTX; 3648 ptr->loads = NULL; 3649 ptr->stores = NULL; 3650 ptr->reaching_reg = NULL_RTX; 3651 ptr->invalid = 0; 3652 ptr->index = 0; 3653 ptr->hash_index = hash; 3654 pre_ldst_mems = ptr; 3655 *slot = ptr; 3656 3657 return ptr; 3658 } 3659 3660 /* Free up an individual ldst entry. */ 3661 3662 static void 3663 free_ldst_entry (struct ls_expr * ptr) 3664 { 3665 free_INSN_LIST_list (& ptr->loads); 3666 free_INSN_LIST_list (& ptr->stores); 3667 3668 free (ptr); 3669 } 3670 3671 /* Free up all memory associated with the ldst list. */ 3672 3673 static void 3674 free_ld_motion_mems (void) 3675 { 3676 delete pre_ldst_table; 3677 pre_ldst_table = NULL; 3678 3679 while (pre_ldst_mems) 3680 { 3681 struct ls_expr * tmp = pre_ldst_mems; 3682 3683 pre_ldst_mems = pre_ldst_mems->next; 3684 3685 free_ldst_entry (tmp); 3686 } 3687 3688 pre_ldst_mems = NULL; 3689 } 3690 3691 /* Dump debugging info about the ldst list. */ 3692 3693 static void 3694 print_ldst_list (FILE * file) 3695 { 3696 struct ls_expr * ptr; 3697 3698 fprintf (file, "LDST list: \n"); 3699 3700 for (ptr = pre_ldst_mems; ptr != NULL; ptr = ptr->next) 3701 { 3702 fprintf (file, " Pattern (%3d): ", ptr->index); 3703 3704 print_rtl (file, ptr->pattern); 3705 3706 fprintf (file, "\n Loads : "); 3707 3708 if (ptr->loads) 3709 print_rtl (file, ptr->loads); 3710 else 3711 fprintf (file, "(nil)"); 3712 3713 fprintf (file, "\n Stores : "); 3714 3715 if (ptr->stores) 3716 print_rtl (file, ptr->stores); 3717 else 3718 fprintf (file, "(nil)"); 3719 3720 fprintf (file, "\n\n"); 3721 } 3722 3723 fprintf (file, "\n"); 3724 } 3725 3726 /* Returns 1 if X is in the list of ldst only expressions. */ 3727 3728 static struct ls_expr * 3729 find_rtx_in_ldst (rtx x) 3730 { 3731 struct ls_expr e; 3732 ls_expr **slot; 3733 if (!pre_ldst_table) 3734 return NULL; 3735 e.pattern = x; 3736 slot = pre_ldst_table->find_slot (&e, NO_INSERT); 3737 if (!slot || (*slot)->invalid) 3738 return NULL; 3739 return *slot; 3740 } 3741 3742 /* Load Motion for loads which only kill themselves. */ 3743 3744 /* Return true if x, a MEM, is a simple access with no side effects. 3745 These are the types of loads we consider for the ld_motion list, 3746 otherwise we let the usual aliasing take care of it. */ 3747 3748 static int 3749 simple_mem (const_rtx x) 3750 { 3751 if (MEM_VOLATILE_P (x)) 3752 return 0; 3753 3754 if (GET_MODE (x) == BLKmode) 3755 return 0; 3756 3757 /* If we are handling exceptions, we must be careful with memory references 3758 that may trap. If we are not, the behavior is undefined, so we may just 3759 continue. */ 3760 if (cfun->can_throw_non_call_exceptions && may_trap_p (x)) 3761 return 0; 3762 3763 if (side_effects_p (x)) 3764 return 0; 3765 3766 /* Do not consider function arguments passed on stack. */ 3767 if (reg_mentioned_p (stack_pointer_rtx, x)) 3768 return 0; 3769 3770 if (flag_float_store && FLOAT_MODE_P (GET_MODE (x))) 3771 return 0; 3772 3773 return 1; 3774 } 3775 3776 /* Make sure there isn't a buried reference in this pattern anywhere. 3777 If there is, invalidate the entry for it since we're not capable 3778 of fixing it up just yet.. We have to be sure we know about ALL 3779 loads since the aliasing code will allow all entries in the 3780 ld_motion list to not-alias itself. If we miss a load, we will get 3781 the wrong value since gcse might common it and we won't know to 3782 fix it up. */ 3783 3784 static void 3785 invalidate_any_buried_refs (rtx x) 3786 { 3787 const char * fmt; 3788 int i, j; 3789 struct ls_expr * ptr; 3790 3791 /* Invalidate it in the list. */ 3792 if (MEM_P (x) && simple_mem (x)) 3793 { 3794 ptr = ldst_entry (x); 3795 ptr->invalid = 1; 3796 } 3797 3798 /* Recursively process the insn. */ 3799 fmt = GET_RTX_FORMAT (GET_CODE (x)); 3800 3801 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--) 3802 { 3803 if (fmt[i] == 'e') 3804 invalidate_any_buried_refs (XEXP (x, i)); 3805 else if (fmt[i] == 'E') 3806 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 3807 invalidate_any_buried_refs (XVECEXP (x, i, j)); 3808 } 3809 } 3810 3811 /* Find all the 'simple' MEMs which are used in LOADs and STORES. Simple 3812 being defined as MEM loads and stores to symbols, with no side effects 3813 and no registers in the expression. For a MEM destination, we also 3814 check that the insn is still valid if we replace the destination with a 3815 REG, as is done in update_ld_motion_stores. If there are any uses/defs 3816 which don't match this criteria, they are invalidated and trimmed out 3817 later. */ 3818 3819 static void 3820 compute_ld_motion_mems (void) 3821 { 3822 struct ls_expr * ptr; 3823 basic_block bb; 3824 rtx_insn *insn; 3825 3826 pre_ldst_mems = NULL; 3827 pre_ldst_table = new hash_table<pre_ldst_expr_hasher> (13); 3828 3829 FOR_EACH_BB_FN (bb, cfun) 3830 { 3831 FOR_BB_INSNS (bb, insn) 3832 { 3833 if (NONDEBUG_INSN_P (insn)) 3834 { 3835 if (GET_CODE (PATTERN (insn)) == SET) 3836 { 3837 rtx src = SET_SRC (PATTERN (insn)); 3838 rtx dest = SET_DEST (PATTERN (insn)); 3839 3840 /* Check for a simple load. */ 3841 if (MEM_P (src) && simple_mem (src)) 3842 { 3843 ptr = ldst_entry (src); 3844 if (REG_P (dest)) 3845 ptr->loads = alloc_INSN_LIST (insn, ptr->loads); 3846 else 3847 ptr->invalid = 1; 3848 } 3849 else 3850 { 3851 /* Make sure there isn't a buried load somewhere. */ 3852 invalidate_any_buried_refs (src); 3853 } 3854 3855 /* Check for a simple load through a REG_EQUAL note. */ 3856 rtx note = find_reg_equal_equiv_note (insn), src_eq; 3857 if (note 3858 && REG_NOTE_KIND (note) == REG_EQUAL 3859 && (src_eq = XEXP (note, 0)) 3860 && !(MEM_P (src_eq) && simple_mem (src_eq))) 3861 invalidate_any_buried_refs (src_eq); 3862 3863 /* Check for stores. Don't worry about aliased ones, they 3864 will block any movement we might do later. We only care 3865 about this exact pattern since those are the only 3866 circumstance that we will ignore the aliasing info. */ 3867 if (MEM_P (dest) && simple_mem (dest)) 3868 { 3869 ptr = ldst_entry (dest); 3870 3871 if (! MEM_P (src) 3872 && GET_CODE (src) != ASM_OPERANDS 3873 /* Check for REG manually since want_to_gcse_p 3874 returns 0 for all REGs. */ 3875 && can_assign_to_reg_without_clobbers_p (src)) 3876 ptr->stores = alloc_INSN_LIST (insn, ptr->stores); 3877 else 3878 ptr->invalid = 1; 3879 } 3880 } 3881 else 3882 { 3883 /* Invalidate all MEMs in the pattern and... */ 3884 invalidate_any_buried_refs (PATTERN (insn)); 3885 3886 /* ...in REG_EQUAL notes for PARALLELs with single SET. */ 3887 rtx note = find_reg_equal_equiv_note (insn), src_eq; 3888 if (note 3889 && REG_NOTE_KIND (note) == REG_EQUAL 3890 && (src_eq = XEXP (note, 0))) 3891 invalidate_any_buried_refs (src_eq); 3892 } 3893 } 3894 } 3895 } 3896 } 3897 3898 /* Remove any references that have been either invalidated or are not in the 3899 expression list for pre gcse. */ 3900 3901 static void 3902 trim_ld_motion_mems (void) 3903 { 3904 struct ls_expr * * last = & pre_ldst_mems; 3905 struct ls_expr * ptr = pre_ldst_mems; 3906 3907 while (ptr != NULL) 3908 { 3909 struct gcse_expr * expr; 3910 3911 /* Delete if entry has been made invalid. */ 3912 if (! ptr->invalid) 3913 { 3914 /* Delete if we cannot find this mem in the expression list. */ 3915 unsigned int hash = ptr->hash_index % expr_hash_table.size; 3916 3917 for (expr = expr_hash_table.table[hash]; 3918 expr != NULL; 3919 expr = expr->next_same_hash) 3920 if (expr_equiv_p (expr->expr, ptr->pattern)) 3921 break; 3922 } 3923 else 3924 expr = (struct gcse_expr *) 0; 3925 3926 if (expr) 3927 { 3928 /* Set the expression field if we are keeping it. */ 3929 ptr->expr = expr; 3930 last = & ptr->next; 3931 ptr = ptr->next; 3932 } 3933 else 3934 { 3935 *last = ptr->next; 3936 pre_ldst_table->remove_elt_with_hash (ptr, ptr->hash_index); 3937 free_ldst_entry (ptr); 3938 ptr = * last; 3939 } 3940 } 3941 3942 /* Show the world what we've found. */ 3943 if (dump_file && pre_ldst_mems != NULL) 3944 print_ldst_list (dump_file); 3945 } 3946 3947 /* This routine will take an expression which we are replacing with 3948 a reaching register, and update any stores that are needed if 3949 that expression is in the ld_motion list. Stores are updated by 3950 copying their SRC to the reaching register, and then storing 3951 the reaching register into the store location. These keeps the 3952 correct value in the reaching register for the loads. */ 3953 3954 static void 3955 update_ld_motion_stores (struct gcse_expr * expr) 3956 { 3957 struct ls_expr * mem_ptr; 3958 3959 if ((mem_ptr = find_rtx_in_ldst (expr->expr))) 3960 { 3961 /* We can try to find just the REACHED stores, but is shouldn't 3962 matter to set the reaching reg everywhere... some might be 3963 dead and should be eliminated later. */ 3964 3965 /* We replace (set mem expr) with (set reg expr) (set mem reg) 3966 where reg is the reaching reg used in the load. We checked in 3967 compute_ld_motion_mems that we can replace (set mem expr) with 3968 (set reg expr) in that insn. */ 3969 rtx list = mem_ptr->stores; 3970 3971 for ( ; list != NULL_RTX; list = XEXP (list, 1)) 3972 { 3973 rtx_insn *insn = as_a <rtx_insn *> (XEXP (list, 0)); 3974 rtx pat = PATTERN (insn); 3975 rtx src = SET_SRC (pat); 3976 rtx reg = expr->reaching_reg; 3977 rtx copy; 3978 3979 /* If we've already copied it, continue. */ 3980 if (expr->reaching_reg == src) 3981 continue; 3982 3983 if (dump_file) 3984 { 3985 fprintf (dump_file, "PRE: store updated with reaching reg "); 3986 print_rtl (dump_file, reg); 3987 fprintf (dump_file, ":\n "); 3988 print_inline_rtx (dump_file, insn, 8); 3989 fprintf (dump_file, "\n"); 3990 } 3991 3992 copy = gen_move_insn (reg, copy_rtx (SET_SRC (pat))); 3993 emit_insn_before (copy, insn); 3994 SET_SRC (pat) = reg; 3995 df_insn_rescan (insn); 3996 3997 /* un-recognize this pattern since it's probably different now. */ 3998 INSN_CODE (insn) = -1; 3999 gcse_create_count++; 4000 } 4001 } 4002 } 4003 4004 /* Return true if the graph is too expensive to optimize. PASS is the 4005 optimization about to be performed. */ 4006 4007 static bool 4008 is_too_expensive (const char *pass) 4009 { 4010 /* Trying to perform global optimizations on flow graphs which have 4011 a high connectivity will take a long time and is unlikely to be 4012 particularly useful. 4013 4014 In normal circumstances a cfg should have about twice as many 4015 edges as blocks. But we do not want to punish small functions 4016 which have a couple switch statements. Rather than simply 4017 threshold the number of blocks, uses something with a more 4018 graceful degradation. */ 4019 if (n_edges_for_fn (cfun) > 20000 + n_basic_blocks_for_fn (cfun) * 4) 4020 { 4021 warning (OPT_Wdisabled_optimization, 4022 "%s: %d basic blocks and %d edges/basic block", 4023 pass, n_basic_blocks_for_fn (cfun), 4024 n_edges_for_fn (cfun) / n_basic_blocks_for_fn (cfun)); 4025 4026 return true; 4027 } 4028 4029 /* If allocating memory for the dataflow bitmaps would take up too much 4030 storage it's better just to disable the optimization. */ 4031 if ((n_basic_blocks_for_fn (cfun) 4032 * SBITMAP_SET_SIZE (max_reg_num ()) 4033 * sizeof (SBITMAP_ELT_TYPE)) > MAX_GCSE_MEMORY) 4034 { 4035 warning (OPT_Wdisabled_optimization, 4036 "%s: %d basic blocks and %d registers", 4037 pass, n_basic_blocks_for_fn (cfun), max_reg_num ()); 4038 4039 return true; 4040 } 4041 4042 return false; 4043 } 4044 4045 static unsigned int 4046 execute_rtl_pre (void) 4047 { 4048 int changed; 4049 delete_unreachable_blocks (); 4050 df_analyze (); 4051 changed = one_pre_gcse_pass (); 4052 flag_rerun_cse_after_global_opts |= changed; 4053 if (changed) 4054 cleanup_cfg (0); 4055 return 0; 4056 } 4057 4058 static unsigned int 4059 execute_rtl_hoist (void) 4060 { 4061 int changed; 4062 delete_unreachable_blocks (); 4063 df_analyze (); 4064 changed = one_code_hoisting_pass (); 4065 flag_rerun_cse_after_global_opts |= changed; 4066 if (changed) 4067 cleanup_cfg (0); 4068 return 0; 4069 } 4070 4071 namespace { 4072 4073 const pass_data pass_data_rtl_pre = 4074 { 4075 RTL_PASS, /* type */ 4076 "rtl pre", /* name */ 4077 OPTGROUP_NONE, /* optinfo_flags */ 4078 TV_PRE, /* tv_id */ 4079 PROP_cfglayout, /* properties_required */ 4080 0, /* properties_provided */ 4081 0, /* properties_destroyed */ 4082 0, /* todo_flags_start */ 4083 TODO_df_finish, /* todo_flags_finish */ 4084 }; 4085 4086 class pass_rtl_pre : public rtl_opt_pass 4087 { 4088 public: 4089 pass_rtl_pre (gcc::context *ctxt) 4090 : rtl_opt_pass (pass_data_rtl_pre, ctxt) 4091 {} 4092 4093 /* opt_pass methods: */ 4094 virtual bool gate (function *); 4095 virtual unsigned int execute (function *) { return execute_rtl_pre (); } 4096 4097 }; // class pass_rtl_pre 4098 4099 /* We do not construct an accurate cfg in functions which call 4100 setjmp, so none of these passes runs if the function calls 4101 setjmp. 4102 FIXME: Should just handle setjmp via REG_SETJMP notes. */ 4103 4104 bool 4105 pass_rtl_pre::gate (function *fun) 4106 { 4107 return optimize > 0 && flag_gcse 4108 && !fun->calls_setjmp 4109 && optimize_function_for_speed_p (fun) 4110 && dbg_cnt (pre); 4111 } 4112 4113 } // anon namespace 4114 4115 rtl_opt_pass * 4116 make_pass_rtl_pre (gcc::context *ctxt) 4117 { 4118 return new pass_rtl_pre (ctxt); 4119 } 4120 4121 namespace { 4122 4123 const pass_data pass_data_rtl_hoist = 4124 { 4125 RTL_PASS, /* type */ 4126 "hoist", /* name */ 4127 OPTGROUP_NONE, /* optinfo_flags */ 4128 TV_HOIST, /* tv_id */ 4129 PROP_cfglayout, /* properties_required */ 4130 0, /* properties_provided */ 4131 0, /* properties_destroyed */ 4132 0, /* todo_flags_start */ 4133 TODO_df_finish, /* todo_flags_finish */ 4134 }; 4135 4136 class pass_rtl_hoist : public rtl_opt_pass 4137 { 4138 public: 4139 pass_rtl_hoist (gcc::context *ctxt) 4140 : rtl_opt_pass (pass_data_rtl_hoist, ctxt) 4141 {} 4142 4143 /* opt_pass methods: */ 4144 virtual bool gate (function *); 4145 virtual unsigned int execute (function *) { return execute_rtl_hoist (); } 4146 4147 }; // class pass_rtl_hoist 4148 4149 bool 4150 pass_rtl_hoist::gate (function *) 4151 { 4152 return optimize > 0 && flag_gcse 4153 && !cfun->calls_setjmp 4154 /* It does not make sense to run code hoisting unless we are optimizing 4155 for code size -- it rarely makes programs faster, and can make then 4156 bigger if we did PRE (when optimizing for space, we don't run PRE). */ 4157 && optimize_function_for_size_p (cfun) 4158 && dbg_cnt (hoist); 4159 } 4160 4161 } // anon namespace 4162 4163 rtl_opt_pass * 4164 make_pass_rtl_hoist (gcc::context *ctxt) 4165 { 4166 return new pass_rtl_hoist (ctxt); 4167 } 4168 4169 /* Reset all state within gcse.c so that we can rerun the compiler 4170 within the same process. For use by toplev::finalize. */ 4171 4172 void 4173 gcse_c_finalize (void) 4174 { 4175 test_insn = NULL; 4176 } 4177 4178 #include "gt-gcse.h" 4179