gcse.c revision 161651
1/* Global common subexpression elimination/Partial redundancy elimination 2 and global constant/copy propagation for GNU compiler. 3 Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004 4 Free Software Foundation, Inc. 5 6This file is part of GCC. 7 8GCC is free software; you can redistribute it and/or modify it under 9the terms of the GNU General Public License as published by the Free 10Software Foundation; either version 2, or (at your option) any later 11version. 12 13GCC is distributed in the hope that it will be useful, but WITHOUT ANY 14WARRANTY; without even the implied warranty of MERCHANTABILITY or 15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16for more details. 17 18You should have received a copy of the GNU General Public License 19along with GCC; see the file COPYING. If not, write to the Free 20Software Foundation, 59 Temple Place - Suite 330, Boston, MA 2102111-1307, USA. */ 22 23/* TODO 24 - reordering of memory allocation and freeing to be more space efficient 25 - do rough calc of how many regs are needed in each block, and a rough 26 calc of how many regs are available in each class and use that to 27 throttle back the code in cases where RTX_COST is minimal. 28 - a store to the same address as a load does not kill the load if the 29 source of the store is also the destination of the load. Handling this 30 allows more load motion, particularly out of loops. 31 - ability to realloc sbitmap vectors would allow one initial computation 32 of reg_set_in_block with only subsequent additions, rather than 33 recomputing it for each pass 34 35*/ 36 37/* References searched while implementing this. 38 39 Compilers Principles, Techniques and Tools 40 Aho, Sethi, Ullman 41 Addison-Wesley, 1988 42 43 Global Optimization by Suppression of Partial Redundancies 44 E. Morel, C. Renvoise 45 communications of the acm, Vol. 22, Num. 2, Feb. 1979 46 47 A Portable Machine-Independent Global Optimizer - Design and Measurements 48 Frederick Chow 49 Stanford Ph.D. thesis, Dec. 1983 50 51 A Fast Algorithm for Code Movement Optimization 52 D.M. Dhamdhere 53 SIGPLAN Notices, Vol. 23, Num. 10, Oct. 1988 54 55 A Solution to a Problem with Morel and Renvoise's 56 Global Optimization by Suppression of Partial Redundancies 57 K-H Drechsler, M.P. Stadel 58 ACM TOPLAS, Vol. 10, Num. 4, Oct. 1988 59 60 Practical Adaptation of the Global Optimization 61 Algorithm of Morel and Renvoise 62 D.M. Dhamdhere 63 ACM TOPLAS, Vol. 13, Num. 2. Apr. 1991 64 65 Efficiently Computing Static Single Assignment Form and the Control 66 Dependence Graph 67 R. Cytron, J. Ferrante, B.K. Rosen, M.N. Wegman, and F.K. Zadeck 68 ACM TOPLAS, Vol. 13, Num. 4, Oct. 1991 69 70 Lazy Code Motion 71 J. Knoop, O. Ruthing, B. Steffen 72 ACM SIGPLAN Notices Vol. 27, Num. 7, Jul. 1992, '92 Conference on PLDI 73 74 What's In a Region? Or Computing Control Dependence Regions in Near-Linear 75 Time for Reducible Flow Control 76 Thomas Ball 77 ACM Letters on Programming Languages and Systems, 78 Vol. 2, Num. 1-4, Mar-Dec 1993 79 80 An Efficient Representation for Sparse Sets 81 Preston Briggs, Linda Torczon 82 ACM Letters on Programming Languages and Systems, 83 Vol. 2, Num. 1-4, Mar-Dec 1993 84 85 A Variation of Knoop, Ruthing, and Steffen's Lazy Code Motion 86 K-H Drechsler, M.P. Stadel 87 ACM SIGPLAN Notices, Vol. 28, Num. 5, May 1993 88 89 Partial Dead Code Elimination 90 J. Knoop, O. Ruthing, B. Steffen 91 ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994 92 93 Effective Partial Redundancy Elimination 94 P. Briggs, K.D. Cooper 95 ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994 96 97 The Program Structure Tree: Computing Control Regions in Linear Time 98 R. Johnson, D. Pearson, K. Pingali 99 ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994 100 101 Optimal Code Motion: Theory and Practice 102 J. Knoop, O. Ruthing, B. Steffen 103 ACM TOPLAS, Vol. 16, Num. 4, Jul. 1994 104 105 The power of assignment motion 106 J. Knoop, O. Ruthing, B. Steffen 107 ACM SIGPLAN Notices Vol. 30, Num. 6, Jun. 1995, '95 Conference on PLDI 108 109 Global code motion / global value numbering 110 C. Click 111 ACM SIGPLAN Notices Vol. 30, Num. 6, Jun. 1995, '95 Conference on PLDI 112 113 Value Driven Redundancy Elimination 114 L.T. Simpson 115 Rice University Ph.D. thesis, Apr. 1996 116 117 Value Numbering 118 L.T. Simpson 119 Massively Scalar Compiler Project, Rice University, Sep. 1996 120 121 High Performance Compilers for Parallel Computing 122 Michael Wolfe 123 Addison-Wesley, 1996 124 125 Advanced Compiler Design and Implementation 126 Steven Muchnick 127 Morgan Kaufmann, 1997 128 129 Building an Optimizing Compiler 130 Robert Morgan 131 Digital Press, 1998 132 133 People wishing to speed up the code here should read: 134 Elimination Algorithms for Data Flow Analysis 135 B.G. Ryder, M.C. Paull 136 ACM Computing Surveys, Vol. 18, Num. 3, Sep. 1986 137 138 How to Analyze Large Programs Efficiently and Informatively 139 D.M. Dhamdhere, B.K. Rosen, F.K. Zadeck 140 ACM SIGPLAN Notices Vol. 27, Num. 7, Jul. 1992, '92 Conference on PLDI 141 142 People wishing to do something different can find various possibilities 143 in the above papers and elsewhere. 144*/ 145 146#include "config.h" 147#include "system.h" 148#include "coretypes.h" 149#include "tm.h" 150#include "toplev.h" 151 152#include "rtl.h" 153#include "tree.h" 154#include "tm_p.h" 155#include "regs.h" 156#include "hard-reg-set.h" 157#include "flags.h" 158#include "real.h" 159#include "insn-config.h" 160#include "recog.h" 161#include "basic-block.h" 162#include "output.h" 163#include "function.h" 164#include "expr.h" 165#include "except.h" 166#include "ggc.h" 167#include "params.h" 168#include "cselib.h" 169#include "intl.h" 170#include "obstack.h" 171 172/* Propagate flow information through back edges and thus enable PRE's 173 moving loop invariant calculations out of loops. 174 175 Originally this tended to create worse overall code, but several 176 improvements during the development of PRE seem to have made following 177 back edges generally a win. 178 179 Note much of the loop invariant code motion done here would normally 180 be done by loop.c, which has more heuristics for when to move invariants 181 out of loops. At some point we might need to move some of those 182 heuristics into gcse.c. */ 183 184/* We support GCSE via Partial Redundancy Elimination. PRE optimizations 185 are a superset of those done by GCSE. 186 187 We perform the following steps: 188 189 1) Compute basic block information. 190 191 2) Compute table of places where registers are set. 192 193 3) Perform copy/constant propagation. 194 195 4) Perform global cse. 196 197 5) Perform another pass of copy/constant propagation. 198 199 Two passes of copy/constant propagation are done because the first one 200 enables more GCSE and the second one helps to clean up the copies that 201 GCSE creates. This is needed more for PRE than for Classic because Classic 202 GCSE will try to use an existing register containing the common 203 subexpression rather than create a new one. This is harder to do for PRE 204 because of the code motion (which Classic GCSE doesn't do). 205 206 Expressions we are interested in GCSE-ing are of the form 207 (set (pseudo-reg) (expression)). 208 Function want_to_gcse_p says what these are. 209 210 PRE handles moving invariant expressions out of loops (by treating them as 211 partially redundant). 212 213 Eventually it would be nice to replace cse.c/gcse.c with SSA (static single 214 assignment) based GVN (global value numbering). L. T. Simpson's paper 215 (Rice University) on value numbering is a useful reference for this. 216 217 ********************** 218 219 We used to support multiple passes but there are diminishing returns in 220 doing so. The first pass usually makes 90% of the changes that are doable. 221 A second pass can make a few more changes made possible by the first pass. 222 Experiments show any further passes don't make enough changes to justify 223 the expense. 224 225 A study of spec92 using an unlimited number of passes: 226 [1 pass] = 1208 substitutions, [2] = 577, [3] = 202, [4] = 192, [5] = 83, 227 [6] = 34, [7] = 17, [8] = 9, [9] = 4, [10] = 4, [11] = 2, 228 [12] = 2, [13] = 1, [15] = 1, [16] = 2, [41] = 1 229 230 It was found doing copy propagation between each pass enables further 231 substitutions. 232 233 PRE is quite expensive in complicated functions because the DFA can take 234 awhile to converge. Hence we only perform one pass. The parameter max-gcse-passes can 235 be modified if one wants to experiment. 236 237 ********************** 238 239 The steps for PRE are: 240 241 1) Build the hash table of expressions we wish to GCSE (expr_hash_table). 242 243 2) Perform the data flow analysis for PRE. 244 245 3) Delete the redundant instructions 246 247 4) Insert the required copies [if any] that make the partially 248 redundant instructions fully redundant. 249 250 5) For other reaching expressions, insert an instruction to copy the value 251 to a newly created pseudo that will reach the redundant instruction. 252 253 The deletion is done first so that when we do insertions we 254 know which pseudo reg to use. 255 256 Various papers have argued that PRE DFA is expensive (O(n^2)) and others 257 argue it is not. The number of iterations for the algorithm to converge 258 is typically 2-4 so I don't view it as that expensive (relatively speaking). 259 260 PRE GCSE depends heavily on the second CSE pass to clean up the copies 261 we create. To make an expression reach the place where it's redundant, 262 the result of the expression is copied to a new register, and the redundant 263 expression is deleted by replacing it with this new register. Classic GCSE 264 doesn't have this problem as much as it computes the reaching defs of 265 each register in each block and thus can try to use an existing register. 266 267 ********************** 268 269 A fair bit of simplicity is created by creating small functions for simple 270 tasks, even when the function is only called in one place. This may 271 measurably slow things down [or may not] by creating more function call 272 overhead than is necessary. The source is laid out so that it's trivial 273 to make the affected functions inline so that one can measure what speed 274 up, if any, can be achieved, and maybe later when things settle things can 275 be rearranged. 276 277 Help stamp out big monolithic functions! */ 278 279/* GCSE global vars. */ 280 281/* -dG dump file. */ 282static FILE *gcse_file; 283 284/* Note whether or not we should run jump optimization after gcse. We 285 want to do this for two cases. 286 287 * If we changed any jumps via cprop. 288 289 * If we added any labels via edge splitting. */ 290 291static int run_jump_opt_after_gcse; 292 293/* Bitmaps are normally not included in debugging dumps. 294 However it's useful to be able to print them from GDB. 295 We could create special functions for this, but it's simpler to 296 just allow passing stderr to the dump_foo fns. Since stderr can 297 be a macro, we store a copy here. */ 298static FILE *debug_stderr; 299 300/* An obstack for our working variables. */ 301static struct obstack gcse_obstack; 302 303struct reg_use {rtx reg_rtx; }; 304 305/* Hash table of expressions. */ 306 307struct expr 308{ 309 /* The expression (SET_SRC for expressions, PATTERN for assignments). */ 310 rtx expr; 311 /* Index in the available expression bitmaps. */ 312 int bitmap_index; 313 /* Next entry with the same hash. */ 314 struct expr *next_same_hash; 315 /* List of anticipatable occurrences in basic blocks in the function. 316 An "anticipatable occurrence" is one that is the first occurrence in the 317 basic block, the operands are not modified in the basic block prior 318 to the occurrence and the output is not used between the start of 319 the block and the occurrence. */ 320 struct occr *antic_occr; 321 /* List of available occurrence in basic blocks in the function. 322 An "available occurrence" is one that is the last occurrence in the 323 basic block and the operands are not modified by following statements in 324 the basic block [including this insn]. */ 325 struct occr *avail_occr; 326 /* Non-null if the computation is PRE redundant. 327 The value is the newly created pseudo-reg to record a copy of the 328 expression in all the places that reach the redundant copy. */ 329 rtx reaching_reg; 330}; 331 332/* Occurrence of an expression. 333 There is one per basic block. If a pattern appears more than once the 334 last appearance is used [or first for anticipatable expressions]. */ 335 336struct occr 337{ 338 /* Next occurrence of this expression. */ 339 struct occr *next; 340 /* The insn that computes the expression. */ 341 rtx insn; 342 /* Nonzero if this [anticipatable] occurrence has been deleted. */ 343 char deleted_p; 344 /* Nonzero if this [available] occurrence has been copied to 345 reaching_reg. */ 346 /* ??? This is mutually exclusive with deleted_p, so they could share 347 the same byte. */ 348 char copied_p; 349}; 350 351/* Expression and copy propagation hash tables. 352 Each hash table is an array of buckets. 353 ??? It is known that if it were an array of entries, structure elements 354 `next_same_hash' and `bitmap_index' wouldn't be necessary. However, it is 355 not clear whether in the final analysis a sufficient amount of memory would 356 be saved as the size of the available expression bitmaps would be larger 357 [one could build a mapping table without holes afterwards though]. 358 Someday I'll perform the computation and figure it out. */ 359 360struct hash_table 361{ 362 /* The table itself. 363 This is an array of `expr_hash_table_size' elements. */ 364 struct expr **table; 365 366 /* Size of the hash table, in elements. */ 367 unsigned int size; 368 369 /* Number of hash table elements. */ 370 unsigned int n_elems; 371 372 /* Whether the table is expression of copy propagation one. */ 373 int set_p; 374}; 375 376/* Expression hash table. */ 377static struct hash_table expr_hash_table; 378 379/* Copy propagation hash table. */ 380static struct hash_table set_hash_table; 381 382/* Mapping of uids to cuids. 383 Only real insns get cuids. */ 384static int *uid_cuid; 385 386/* Highest UID in UID_CUID. */ 387static int max_uid; 388 389/* Get the cuid of an insn. */ 390#ifdef ENABLE_CHECKING 391#define INSN_CUID(INSN) (INSN_UID (INSN) > max_uid ? (abort (), 0) : uid_cuid[INSN_UID (INSN)]) 392#else 393#define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)]) 394#endif 395 396/* Number of cuids. */ 397static int max_cuid; 398 399/* Mapping of cuids to insns. */ 400static rtx *cuid_insn; 401 402/* Get insn from cuid. */ 403#define CUID_INSN(CUID) (cuid_insn[CUID]) 404 405/* Maximum register number in function prior to doing gcse + 1. 406 Registers created during this pass have regno >= max_gcse_regno. 407 This is named with "gcse" to not collide with global of same name. */ 408static unsigned int max_gcse_regno; 409 410/* Table of registers that are modified. 411 412 For each register, each element is a list of places where the pseudo-reg 413 is set. 414 415 For simplicity, GCSE is done on sets of pseudo-regs only. PRE GCSE only 416 requires knowledge of which blocks kill which regs [and thus could use 417 a bitmap instead of the lists `reg_set_table' uses]. 418 419 `reg_set_table' and could be turned into an array of bitmaps (num-bbs x 420 num-regs) [however perhaps it may be useful to keep the data as is]. One 421 advantage of recording things this way is that `reg_set_table' is fairly 422 sparse with respect to pseudo regs but for hard regs could be fairly dense 423 [relatively speaking]. And recording sets of pseudo-regs in lists speeds 424 up functions like compute_transp since in the case of pseudo-regs we only 425 need to iterate over the number of times a pseudo-reg is set, not over the 426 number of basic blocks [clearly there is a bit of a slow down in the cases 427 where a pseudo is set more than once in a block, however it is believed 428 that the net effect is to speed things up]. This isn't done for hard-regs 429 because recording call-clobbered hard-regs in `reg_set_table' at each 430 function call can consume a fair bit of memory, and iterating over 431 hard-regs stored this way in compute_transp will be more expensive. */ 432 433typedef struct reg_set 434{ 435 /* The next setting of this register. */ 436 struct reg_set *next; 437 /* The insn where it was set. */ 438 rtx insn; 439} reg_set; 440 441static reg_set **reg_set_table; 442 443/* Size of `reg_set_table'. 444 The table starts out at max_gcse_regno + slop, and is enlarged as 445 necessary. */ 446static int reg_set_table_size; 447 448/* Amount to grow `reg_set_table' by when it's full. */ 449#define REG_SET_TABLE_SLOP 100 450 451/* This is a list of expressions which are MEMs and will be used by load 452 or store motion. 453 Load motion tracks MEMs which aren't killed by 454 anything except itself. (ie, loads and stores to a single location). 455 We can then allow movement of these MEM refs with a little special 456 allowance. (all stores copy the same value to the reaching reg used 457 for the loads). This means all values used to store into memory must have 458 no side effects so we can re-issue the setter value. 459 Store Motion uses this structure as an expression table to track stores 460 which look interesting, and might be moveable towards the exit block. */ 461 462struct ls_expr 463{ 464 struct expr * expr; /* Gcse expression reference for LM. */ 465 rtx pattern; /* Pattern of this mem. */ 466 rtx pattern_regs; /* List of registers mentioned by the mem. */ 467 rtx loads; /* INSN list of loads seen. */ 468 rtx stores; /* INSN list of stores seen. */ 469 struct ls_expr * next; /* Next in the list. */ 470 int invalid; /* Invalid for some reason. */ 471 int index; /* If it maps to a bitmap index. */ 472 unsigned int hash_index; /* Index when in a hash table. */ 473 rtx reaching_reg; /* Register to use when re-writing. */ 474}; 475 476/* Array of implicit set patterns indexed by basic block index. */ 477static rtx *implicit_sets; 478 479/* Head of the list of load/store memory refs. */ 480static struct ls_expr * pre_ldst_mems = NULL; 481 482/* Bitmap containing one bit for each register in the program. 483 Used when performing GCSE to track which registers have been set since 484 the start of the basic block. */ 485static regset reg_set_bitmap; 486 487/* For each block, a bitmap of registers set in the block. 488 This is used by expr_killed_p and compute_transp. 489 It is computed during hash table computation and not by compute_sets 490 as it includes registers added since the last pass (or between cprop and 491 gcse) and it's currently not easy to realloc sbitmap vectors. */ 492static sbitmap *reg_set_in_block; 493 494/* Array, indexed by basic block number for a list of insns which modify 495 memory within that block. */ 496static rtx * modify_mem_list; 497bitmap modify_mem_list_set; 498 499/* This array parallels modify_mem_list, but is kept canonicalized. */ 500static rtx * canon_modify_mem_list; 501bitmap canon_modify_mem_list_set; 502/* Various variables for statistics gathering. */ 503 504/* Memory used in a pass. 505 This isn't intended to be absolutely precise. Its intent is only 506 to keep an eye on memory usage. */ 507static int bytes_used; 508 509/* GCSE substitutions made. */ 510static int gcse_subst_count; 511/* Number of copy instructions created. */ 512static int gcse_create_count; 513/* Number of constants propagated. */ 514static int const_prop_count; 515/* Number of copys propagated. */ 516static int copy_prop_count; 517 518/* These variables are used by classic GCSE. 519 Normally they'd be defined a bit later, but `rd_gen' needs to 520 be declared sooner. */ 521 522/* Each block has a bitmap of each type. 523 The length of each blocks bitmap is: 524 525 max_cuid - for reaching definitions 526 n_exprs - for available expressions 527 528 Thus we view the bitmaps as 2 dimensional arrays. i.e. 529 rd_kill[block_num][cuid_num] 530 ae_kill[block_num][expr_num] */ 531 532/* For reaching defs */ 533static sbitmap *rd_kill, *rd_gen, *reaching_defs, *rd_out; 534 535/* for available exprs */ 536static sbitmap *ae_kill, *ae_gen, *ae_in, *ae_out; 537 538/* Objects of this type are passed around by the null-pointer check 539 removal routines. */ 540struct null_pointer_info 541{ 542 /* The basic block being processed. */ 543 basic_block current_block; 544 /* The first register to be handled in this pass. */ 545 unsigned int min_reg; 546 /* One greater than the last register to be handled in this pass. */ 547 unsigned int max_reg; 548 sbitmap *nonnull_local; 549 sbitmap *nonnull_killed; 550}; 551 552static void compute_can_copy (void); 553static void *gmalloc (size_t) ATTRIBUTE_MALLOC; 554static void *gcalloc (size_t, size_t) ATTRIBUTE_MALLOC; 555static void *grealloc (void *, size_t); 556static void *gcse_alloc (unsigned long); 557static void alloc_gcse_mem (rtx); 558static void free_gcse_mem (void); 559static void alloc_reg_set_mem (int); 560static void free_reg_set_mem (void); 561static int get_bitmap_width (int, int, int); 562static void record_one_set (int, rtx); 563static void replace_one_set (int, rtx, rtx); 564static void record_set_info (rtx, rtx, void *); 565static void compute_sets (rtx); 566static void hash_scan_insn (rtx, struct hash_table *, int); 567static void hash_scan_set (rtx, rtx, struct hash_table *); 568static void hash_scan_clobber (rtx, rtx, struct hash_table *); 569static void hash_scan_call (rtx, rtx, struct hash_table *); 570static int want_to_gcse_p (rtx); 571static bool gcse_constant_p (rtx); 572static int oprs_unchanged_p (rtx, rtx, int); 573static int oprs_anticipatable_p (rtx, rtx); 574static int oprs_available_p (rtx, rtx); 575static void insert_expr_in_table (rtx, enum machine_mode, rtx, int, int, 576 struct hash_table *); 577static void insert_set_in_table (rtx, rtx, struct hash_table *); 578static unsigned int hash_expr (rtx, enum machine_mode, int *, int); 579static unsigned int hash_expr_1 (rtx, enum machine_mode, int *); 580static unsigned int hash_string_1 (const char *); 581static unsigned int hash_set (int, int); 582static int expr_equiv_p (rtx, rtx); 583static void record_last_reg_set_info (rtx, int); 584static void record_last_mem_set_info (rtx); 585static void record_last_set_info (rtx, rtx, void *); 586static void compute_hash_table (struct hash_table *); 587static void alloc_hash_table (int, struct hash_table *, int); 588static void free_hash_table (struct hash_table *); 589static void compute_hash_table_work (struct hash_table *); 590static void dump_hash_table (FILE *, const char *, struct hash_table *); 591static struct expr *lookup_expr (rtx, struct hash_table *); 592static struct expr *lookup_set (unsigned int, struct hash_table *); 593static struct expr *next_set (unsigned int, struct expr *); 594static void reset_opr_set_tables (void); 595static int oprs_not_set_p (rtx, rtx); 596static void mark_call (rtx); 597static void mark_set (rtx, rtx); 598static void mark_clobber (rtx, rtx); 599static void mark_oprs_set (rtx); 600static void alloc_cprop_mem (int, int); 601static void free_cprop_mem (void); 602static void compute_transp (rtx, int, sbitmap *, int); 603static void compute_transpout (void); 604static void compute_local_properties (sbitmap *, sbitmap *, sbitmap *, 605 struct hash_table *); 606static void compute_cprop_data (void); 607static void find_used_regs (rtx *, void *); 608static int try_replace_reg (rtx, rtx, rtx); 609static struct expr *find_avail_set (int, rtx); 610static int cprop_jump (basic_block, rtx, rtx, rtx, rtx); 611static void mems_conflict_for_gcse_p (rtx, rtx, void *); 612static int load_killed_in_block_p (basic_block, int, rtx, int); 613static void canon_list_insert (rtx, rtx, void *); 614static int cprop_insn (rtx, int); 615static int cprop (int); 616static void find_implicit_sets (void); 617static int one_cprop_pass (int, int, int); 618static bool constprop_register (rtx, rtx, rtx, int); 619static struct expr *find_bypass_set (int, int); 620static bool reg_killed_on_edge (rtx, edge); 621static int bypass_block (basic_block, rtx, rtx); 622static int bypass_conditional_jumps (void); 623static void alloc_pre_mem (int, int); 624static void free_pre_mem (void); 625static void compute_pre_data (void); 626static int pre_expr_reaches_here_p (basic_block, struct expr *, 627 basic_block); 628static void insert_insn_end_bb (struct expr *, basic_block, int); 629static void pre_insert_copy_insn (struct expr *, rtx); 630static void pre_insert_copies (void); 631static int pre_delete (void); 632static int pre_gcse (void); 633static int one_pre_gcse_pass (int); 634static void add_label_notes (rtx, rtx); 635static void alloc_code_hoist_mem (int, int); 636static void free_code_hoist_mem (void); 637static void compute_code_hoist_vbeinout (void); 638static void compute_code_hoist_data (void); 639static int hoist_expr_reaches_here_p (basic_block, int, basic_block, char *); 640static void hoist_code (void); 641static int one_code_hoisting_pass (void); 642static void alloc_rd_mem (int, int); 643static void free_rd_mem (void); 644static void handle_rd_kill_set (rtx, int, basic_block); 645static void compute_kill_rd (void); 646static void compute_rd (void); 647static void alloc_avail_expr_mem (int, int); 648static void free_avail_expr_mem (void); 649static void compute_ae_gen (struct hash_table *); 650static int expr_killed_p (rtx, basic_block); 651static void compute_ae_kill (sbitmap *, sbitmap *, struct hash_table *); 652static int expr_reaches_here_p (struct occr *, struct expr *, basic_block, 653 int); 654static rtx computing_insn (struct expr *, rtx); 655static int def_reaches_here_p (rtx, rtx); 656static int can_disregard_other_sets (struct reg_set **, rtx, int); 657static int handle_avail_expr (rtx, struct expr *); 658static int classic_gcse (void); 659static int one_classic_gcse_pass (int); 660static void invalidate_nonnull_info (rtx, rtx, void *); 661static int delete_null_pointer_checks_1 (unsigned int *, sbitmap *, sbitmap *, 662 struct null_pointer_info *); 663static rtx process_insert_insn (struct expr *); 664static int pre_edge_insert (struct edge_list *, struct expr **); 665static int expr_reaches_here_p_work (struct occr *, struct expr *, 666 basic_block, int, char *); 667static int pre_expr_reaches_here_p_work (basic_block, struct expr *, 668 basic_block, char *); 669static struct ls_expr * ldst_entry (rtx); 670static void free_ldst_entry (struct ls_expr *); 671static void free_ldst_mems (void); 672static void print_ldst_list (FILE *); 673static struct ls_expr * find_rtx_in_ldst (rtx); 674static int enumerate_ldsts (void); 675static inline struct ls_expr * first_ls_expr (void); 676static inline struct ls_expr * next_ls_expr (struct ls_expr *); 677static int simple_mem (rtx); 678static void invalidate_any_buried_refs (rtx); 679static void compute_ld_motion_mems (void); 680static void trim_ld_motion_mems (void); 681static void update_ld_motion_stores (struct expr *); 682static void reg_set_info (rtx, rtx, void *); 683static void reg_clear_last_set (rtx, rtx, void *); 684static bool store_ops_ok (rtx, int *); 685static rtx extract_mentioned_regs (rtx); 686static rtx extract_mentioned_regs_helper (rtx, rtx); 687static void find_moveable_store (rtx, int *, int *); 688static int compute_store_table (void); 689static bool load_kills_store (rtx, rtx, int); 690static bool find_loads (rtx, rtx, int); 691static bool store_killed_in_insn (rtx, rtx, rtx, int); 692static bool store_killed_after (rtx, rtx, rtx, basic_block, int *, rtx *); 693static bool store_killed_before (rtx, rtx, rtx, basic_block, int *); 694static void build_store_vectors (void); 695static void insert_insn_start_bb (rtx, basic_block); 696static int insert_store (struct ls_expr *, edge); 697static void remove_reachable_equiv_notes (basic_block, struct ls_expr *); 698static void replace_store_insn (rtx, rtx, basic_block, struct ls_expr *); 699static void delete_store (struct ls_expr *, basic_block); 700static void free_store_memory (void); 701static void store_motion (void); 702static void free_insn_expr_list_list (rtx *); 703static void clear_modify_mem_tables (void); 704static void free_modify_mem_tables (void); 705static rtx gcse_emit_move_after (rtx, rtx, rtx); 706static void local_cprop_find_used_regs (rtx *, void *); 707static bool do_local_cprop (rtx, rtx, int, rtx*); 708static bool adjust_libcall_notes (rtx, rtx, rtx, rtx*); 709static void local_cprop_pass (int); 710static bool is_too_expensive (const char *); 711 712 713/* Entry point for global common subexpression elimination. 714 F is the first instruction in the function. */ 715 716int 717gcse_main (rtx f, FILE *file) 718{ 719 int changed, pass; 720 /* Bytes used at start of pass. */ 721 int initial_bytes_used; 722 /* Maximum number of bytes used by a pass. */ 723 int max_pass_bytes; 724 /* Point to release obstack data from for each pass. */ 725 char *gcse_obstack_bottom; 726 727 /* We do not construct an accurate cfg in functions which call 728 setjmp, so just punt to be safe. */ 729 if (current_function_calls_setjmp) 730 return 0; 731 732 /* Assume that we do not need to run jump optimizations after gcse. */ 733 run_jump_opt_after_gcse = 0; 734 735 /* For calling dump_foo fns from gdb. */ 736 debug_stderr = stderr; 737 gcse_file = file; 738 739 /* Identify the basic block information for this function, including 740 successors and predecessors. */ 741 max_gcse_regno = max_reg_num (); 742 743 if (file) 744 dump_flow_info (file); 745 746 /* Return if there's nothing to do, or it is too expensive. */ 747 if (n_basic_blocks <= 1 || is_too_expensive (_("GCSE disabled"))) 748 return 0; 749 750 gcc_obstack_init (&gcse_obstack); 751 bytes_used = 0; 752 753 /* We need alias. */ 754 init_alias_analysis (); 755 /* Record where pseudo-registers are set. This data is kept accurate 756 during each pass. ??? We could also record hard-reg information here 757 [since it's unchanging], however it is currently done during hash table 758 computation. 759 760 It may be tempting to compute MEM set information here too, but MEM sets 761 will be subject to code motion one day and thus we need to compute 762 information about memory sets when we build the hash tables. */ 763 764 alloc_reg_set_mem (max_gcse_regno); 765 compute_sets (f); 766 767 pass = 0; 768 initial_bytes_used = bytes_used; 769 max_pass_bytes = 0; 770 gcse_obstack_bottom = gcse_alloc (1); 771 changed = 1; 772 while (changed && pass < MAX_GCSE_PASSES) 773 { 774 changed = 0; 775 if (file) 776 fprintf (file, "GCSE pass %d\n\n", pass + 1); 777 778 /* Initialize bytes_used to the space for the pred/succ lists, 779 and the reg_set_table data. */ 780 bytes_used = initial_bytes_used; 781 782 /* Each pass may create new registers, so recalculate each time. */ 783 max_gcse_regno = max_reg_num (); 784 785 alloc_gcse_mem (f); 786 787 /* Don't allow constant propagation to modify jumps 788 during this pass. */ 789 changed = one_cprop_pass (pass + 1, 0, 0); 790 791 if (optimize_size) 792 changed |= one_classic_gcse_pass (pass + 1); 793 else 794 { 795 changed |= one_pre_gcse_pass (pass + 1); 796 /* We may have just created new basic blocks. Release and 797 recompute various things which are sized on the number of 798 basic blocks. */ 799 if (changed) 800 { 801 free_modify_mem_tables (); 802 modify_mem_list = gcalloc (last_basic_block, sizeof (rtx)); 803 canon_modify_mem_list = gcalloc (last_basic_block, sizeof (rtx)); 804 } 805 free_reg_set_mem (); 806 alloc_reg_set_mem (max_reg_num ()); 807 compute_sets (f); 808 run_jump_opt_after_gcse = 1; 809 } 810 811 if (max_pass_bytes < bytes_used) 812 max_pass_bytes = bytes_used; 813 814 /* Free up memory, then reallocate for code hoisting. We can 815 not re-use the existing allocated memory because the tables 816 will not have info for the insns or registers created by 817 partial redundancy elimination. */ 818 free_gcse_mem (); 819 820 /* It does not make sense to run code hoisting unless we are optimizing 821 for code size -- it rarely makes programs faster, and can make 822 them bigger if we did partial redundancy elimination (when optimizing 823 for space, we use a classic gcse algorithm instead of partial 824 redundancy algorithms). */ 825 if (optimize_size) 826 { 827 max_gcse_regno = max_reg_num (); 828 alloc_gcse_mem (f); 829 changed |= one_code_hoisting_pass (); 830 free_gcse_mem (); 831 832 if (max_pass_bytes < bytes_used) 833 max_pass_bytes = bytes_used; 834 } 835 836 if (file) 837 { 838 fprintf (file, "\n"); 839 fflush (file); 840 } 841 842 obstack_free (&gcse_obstack, gcse_obstack_bottom); 843 pass++; 844 } 845 846 /* Do one last pass of copy propagation, including cprop into 847 conditional jumps. */ 848 849 max_gcse_regno = max_reg_num (); 850 alloc_gcse_mem (f); 851 /* This time, go ahead and allow cprop to alter jumps. */ 852 one_cprop_pass (pass + 1, 1, 0); 853 free_gcse_mem (); 854 855 if (file) 856 { 857 fprintf (file, "GCSE of %s: %d basic blocks, ", 858 current_function_name (), n_basic_blocks); 859 fprintf (file, "%d pass%s, %d bytes\n\n", 860 pass, pass > 1 ? "es" : "", max_pass_bytes); 861 } 862 863 obstack_free (&gcse_obstack, NULL); 864 free_reg_set_mem (); 865 /* We are finished with alias. */ 866 end_alias_analysis (); 867 allocate_reg_info (max_reg_num (), FALSE, FALSE); 868 869 if (!optimize_size && flag_gcse_sm) 870 store_motion (); 871 872 /* Record where pseudo-registers are set. */ 873 return run_jump_opt_after_gcse; 874} 875 876/* Misc. utilities. */ 877 878/* Nonzero for each mode that supports (set (reg) (reg)). 879 This is trivially true for integer and floating point values. 880 It may or may not be true for condition codes. */ 881static char can_copy[(int) NUM_MACHINE_MODES]; 882 883/* Compute which modes support reg/reg copy operations. */ 884 885static void 886compute_can_copy (void) 887{ 888 int i; 889#ifndef AVOID_CCMODE_COPIES 890 rtx reg, insn; 891#endif 892 memset (can_copy, 0, NUM_MACHINE_MODES); 893 894 start_sequence (); 895 for (i = 0; i < NUM_MACHINE_MODES; i++) 896 if (GET_MODE_CLASS (i) == MODE_CC) 897 { 898#ifdef AVOID_CCMODE_COPIES 899 can_copy[i] = 0; 900#else 901 reg = gen_rtx_REG ((enum machine_mode) i, LAST_VIRTUAL_REGISTER + 1); 902 insn = emit_insn (gen_rtx_SET (VOIDmode, reg, reg)); 903 if (recog (PATTERN (insn), insn, NULL) >= 0) 904 can_copy[i] = 1; 905#endif 906 } 907 else 908 can_copy[i] = 1; 909 910 end_sequence (); 911} 912 913/* Returns whether the mode supports reg/reg copy operations. */ 914 915bool 916can_copy_p (enum machine_mode mode) 917{ 918 static bool can_copy_init_p = false; 919 920 if (! can_copy_init_p) 921 { 922 compute_can_copy (); 923 can_copy_init_p = true; 924 } 925 926 return can_copy[mode] != 0; 927} 928 929/* Cover function to xmalloc to record bytes allocated. */ 930 931static void * 932gmalloc (size_t size) 933{ 934 bytes_used += size; 935 return xmalloc (size); 936} 937 938/* Cover function to xcalloc to record bytes allocated. */ 939 940static void * 941gcalloc (size_t nelem, size_t elsize) 942{ 943 bytes_used += nelem * elsize; 944 return xcalloc (nelem, elsize); 945} 946 947/* Cover function to xrealloc. 948 We don't record the additional size since we don't know it. 949 It won't affect memory usage stats much anyway. */ 950 951static void * 952grealloc (void *ptr, size_t size) 953{ 954 return xrealloc (ptr, size); 955} 956 957/* Cover function to obstack_alloc. */ 958 959static void * 960gcse_alloc (unsigned long size) 961{ 962 bytes_used += size; 963 return obstack_alloc (&gcse_obstack, size); 964} 965 966/* Allocate memory for the cuid mapping array, 967 and reg/memory set tracking tables. 968 969 This is called at the start of each pass. */ 970 971static void 972alloc_gcse_mem (rtx f) 973{ 974 int i; 975 rtx insn; 976 977 /* Find the largest UID and create a mapping from UIDs to CUIDs. 978 CUIDs are like UIDs except they increase monotonically, have no gaps, 979 and only apply to real insns. */ 980 981 max_uid = get_max_uid (); 982 uid_cuid = gcalloc (max_uid + 1, sizeof (int)); 983 for (insn = f, i = 0; insn; insn = NEXT_INSN (insn)) 984 { 985 if (INSN_P (insn)) 986 uid_cuid[INSN_UID (insn)] = i++; 987 else 988 uid_cuid[INSN_UID (insn)] = i; 989 } 990 991 /* Create a table mapping cuids to insns. */ 992 993 max_cuid = i; 994 cuid_insn = gcalloc (max_cuid + 1, sizeof (rtx)); 995 for (insn = f, i = 0; insn; insn = NEXT_INSN (insn)) 996 if (INSN_P (insn)) 997 CUID_INSN (i++) = insn; 998 999 /* Allocate vars to track sets of regs. */ 1000 reg_set_bitmap = BITMAP_XMALLOC (); 1001 1002 /* Allocate vars to track sets of regs, memory per block. */ 1003 reg_set_in_block = sbitmap_vector_alloc (last_basic_block, max_gcse_regno); 1004 /* Allocate array to keep a list of insns which modify memory in each 1005 basic block. */ 1006 modify_mem_list = gcalloc (last_basic_block, sizeof (rtx)); 1007 canon_modify_mem_list = gcalloc (last_basic_block, sizeof (rtx)); 1008 modify_mem_list_set = BITMAP_XMALLOC (); 1009 canon_modify_mem_list_set = BITMAP_XMALLOC (); 1010} 1011 1012/* Free memory allocated by alloc_gcse_mem. */ 1013 1014static void 1015free_gcse_mem (void) 1016{ 1017 free (uid_cuid); 1018 free (cuid_insn); 1019 1020 BITMAP_XFREE (reg_set_bitmap); 1021 1022 sbitmap_vector_free (reg_set_in_block); 1023 free_modify_mem_tables (); 1024 BITMAP_XFREE (modify_mem_list_set); 1025 BITMAP_XFREE (canon_modify_mem_list_set); 1026} 1027 1028/* Many of the global optimization algorithms work by solving dataflow 1029 equations for various expressions. Initially, some local value is 1030 computed for each expression in each block. Then, the values across the 1031 various blocks are combined (by following flow graph edges) to arrive at 1032 global values. Conceptually, each set of equations is independent. We 1033 may therefore solve all the equations in parallel, solve them one at a 1034 time, or pick any intermediate approach. 1035 1036 When you're going to need N two-dimensional bitmaps, each X (say, the 1037 number of blocks) by Y (say, the number of expressions), call this 1038 function. It's not important what X and Y represent; only that Y 1039 correspond to the things that can be done in parallel. This function will 1040 return an appropriate chunking factor C; you should solve C sets of 1041 equations in parallel. By going through this function, we can easily 1042 trade space against time; by solving fewer equations in parallel we use 1043 less space. */ 1044 1045static int 1046get_bitmap_width (int n, int x, int y) 1047{ 1048 /* It's not really worth figuring out *exactly* how much memory will 1049 be used by a particular choice. The important thing is to get 1050 something approximately right. */ 1051 size_t max_bitmap_memory = 10 * 1024 * 1024; 1052 1053 /* The number of bytes we'd use for a single column of minimum 1054 width. */ 1055 size_t column_size = n * x * sizeof (SBITMAP_ELT_TYPE); 1056 1057 /* Often, it's reasonable just to solve all the equations in 1058 parallel. */ 1059 if (column_size * SBITMAP_SET_SIZE (y) <= max_bitmap_memory) 1060 return y; 1061 1062 /* Otherwise, pick the largest width we can, without going over the 1063 limit. */ 1064 return SBITMAP_ELT_BITS * ((max_bitmap_memory + column_size - 1) 1065 / column_size); 1066} 1067 1068/* Compute the local properties of each recorded expression. 1069 1070 Local properties are those that are defined by the block, irrespective of 1071 other blocks. 1072 1073 An expression is transparent in a block if its operands are not modified 1074 in the block. 1075 1076 An expression is computed (locally available) in a block if it is computed 1077 at least once and expression would contain the same value if the 1078 computation was moved to the end of the block. 1079 1080 An expression is locally anticipatable in a block if it is computed at 1081 least once and expression would contain the same value if the computation 1082 was moved to the beginning of the block. 1083 1084 We call this routine for cprop, pre and code hoisting. They all compute 1085 basically the same information and thus can easily share this code. 1086 1087 TRANSP, COMP, and ANTLOC are destination sbitmaps for recording local 1088 properties. If NULL, then it is not necessary to compute or record that 1089 particular property. 1090 1091 TABLE controls which hash table to look at. If it is set hash table, 1092 additionally, TRANSP is computed as ~TRANSP, since this is really cprop's 1093 ABSALTERED. */ 1094 1095static void 1096compute_local_properties (sbitmap *transp, sbitmap *comp, sbitmap *antloc, struct hash_table *table) 1097{ 1098 unsigned int i; 1099 1100 /* Initialize any bitmaps that were passed in. */ 1101 if (transp) 1102 { 1103 if (table->set_p) 1104 sbitmap_vector_zero (transp, last_basic_block); 1105 else 1106 sbitmap_vector_ones (transp, last_basic_block); 1107 } 1108 1109 if (comp) 1110 sbitmap_vector_zero (comp, last_basic_block); 1111 if (antloc) 1112 sbitmap_vector_zero (antloc, last_basic_block); 1113 1114 for (i = 0; i < table->size; i++) 1115 { 1116 struct expr *expr; 1117 1118 for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash) 1119 { 1120 int indx = expr->bitmap_index; 1121 struct occr *occr; 1122 1123 /* The expression is transparent in this block if it is not killed. 1124 We start by assuming all are transparent [none are killed], and 1125 then reset the bits for those that are. */ 1126 if (transp) 1127 compute_transp (expr->expr, indx, transp, table->set_p); 1128 1129 /* The occurrences recorded in antic_occr are exactly those that 1130 we want to set to nonzero in ANTLOC. */ 1131 if (antloc) 1132 for (occr = expr->antic_occr; occr != NULL; occr = occr->next) 1133 { 1134 SET_BIT (antloc[BLOCK_NUM (occr->insn)], indx); 1135 1136 /* While we're scanning the table, this is a good place to 1137 initialize this. */ 1138 occr->deleted_p = 0; 1139 } 1140 1141 /* The occurrences recorded in avail_occr are exactly those that 1142 we want to set to nonzero in COMP. */ 1143 if (comp) 1144 for (occr = expr->avail_occr; occr != NULL; occr = occr->next) 1145 { 1146 SET_BIT (comp[BLOCK_NUM (occr->insn)], indx); 1147 1148 /* While we're scanning the table, this is a good place to 1149 initialize this. */ 1150 occr->copied_p = 0; 1151 } 1152 1153 /* While we're scanning the table, this is a good place to 1154 initialize this. */ 1155 expr->reaching_reg = 0; 1156 } 1157 } 1158} 1159 1160/* Register set information. 1161 1162 `reg_set_table' records where each register is set or otherwise 1163 modified. */ 1164 1165static struct obstack reg_set_obstack; 1166 1167static void 1168alloc_reg_set_mem (int n_regs) 1169{ 1170 reg_set_table_size = n_regs + REG_SET_TABLE_SLOP; 1171 reg_set_table = gcalloc (reg_set_table_size, sizeof (struct reg_set *)); 1172 1173 gcc_obstack_init (®_set_obstack); 1174} 1175 1176static void 1177free_reg_set_mem (void) 1178{ 1179 free (reg_set_table); 1180 obstack_free (®_set_obstack, NULL); 1181} 1182 1183/* An OLD_INSN that used to set REGNO was replaced by NEW_INSN. 1184 Update the corresponding `reg_set_table' entry accordingly. 1185 We assume that NEW_INSN is not already recorded in reg_set_table[regno]. */ 1186 1187static void 1188replace_one_set (int regno, rtx old_insn, rtx new_insn) 1189{ 1190 struct reg_set *reg_info; 1191 if (regno >= reg_set_table_size) 1192 return; 1193 for (reg_info = reg_set_table[regno]; reg_info; reg_info = reg_info->next) 1194 if (reg_info->insn == old_insn) 1195 { 1196 reg_info->insn = new_insn; 1197 break; 1198 } 1199} 1200 1201/* Record REGNO in the reg_set table. */ 1202 1203static void 1204record_one_set (int regno, rtx insn) 1205{ 1206 /* Allocate a new reg_set element and link it onto the list. */ 1207 struct reg_set *new_reg_info; 1208 1209 /* If the table isn't big enough, enlarge it. */ 1210 if (regno >= reg_set_table_size) 1211 { 1212 int new_size = regno + REG_SET_TABLE_SLOP; 1213 1214 reg_set_table = grealloc (reg_set_table, 1215 new_size * sizeof (struct reg_set *)); 1216 memset (reg_set_table + reg_set_table_size, 0, 1217 (new_size - reg_set_table_size) * sizeof (struct reg_set *)); 1218 reg_set_table_size = new_size; 1219 } 1220 1221 new_reg_info = obstack_alloc (®_set_obstack, sizeof (struct reg_set)); 1222 bytes_used += sizeof (struct reg_set); 1223 new_reg_info->insn = insn; 1224 new_reg_info->next = reg_set_table[regno]; 1225 reg_set_table[regno] = new_reg_info; 1226} 1227 1228/* Called from compute_sets via note_stores to handle one SET or CLOBBER in 1229 an insn. The DATA is really the instruction in which the SET is 1230 occurring. */ 1231 1232static void 1233record_set_info (rtx dest, rtx setter ATTRIBUTE_UNUSED, void *data) 1234{ 1235 rtx record_set_insn = (rtx) data; 1236 1237 if (GET_CODE (dest) == REG && REGNO (dest) >= FIRST_PSEUDO_REGISTER) 1238 record_one_set (REGNO (dest), record_set_insn); 1239} 1240 1241/* Scan the function and record each set of each pseudo-register. 1242 1243 This is called once, at the start of the gcse pass. See the comments for 1244 `reg_set_table' for further documentation. */ 1245 1246static void 1247compute_sets (rtx f) 1248{ 1249 rtx insn; 1250 1251 for (insn = f; insn != 0; insn = NEXT_INSN (insn)) 1252 if (INSN_P (insn)) 1253 note_stores (PATTERN (insn), record_set_info, insn); 1254} 1255 1256/* Hash table support. */ 1257 1258struct reg_avail_info 1259{ 1260 basic_block last_bb; 1261 int first_set; 1262 int last_set; 1263}; 1264 1265static struct reg_avail_info *reg_avail_info; 1266static basic_block current_bb; 1267 1268 1269/* See whether X, the source of a set, is something we want to consider for 1270 GCSE. */ 1271 1272static GTY(()) rtx test_insn; 1273static int 1274want_to_gcse_p (rtx x) 1275{ 1276 int num_clobbers = 0; 1277 int icode; 1278 1279 switch (GET_CODE (x)) 1280 { 1281 case REG: 1282 case SUBREG: 1283 case CONST_INT: 1284 case CONST_DOUBLE: 1285 case CONST_VECTOR: 1286 case CALL: 1287 case CONSTANT_P_RTX: 1288 return 0; 1289 1290 default: 1291 break; 1292 } 1293 1294 /* If this is a valid operand, we are OK. If it's VOIDmode, we aren't. */ 1295 if (general_operand (x, GET_MODE (x))) 1296 return 1; 1297 else if (GET_MODE (x) == VOIDmode) 1298 return 0; 1299 1300 /* Otherwise, check if we can make a valid insn from it. First initialize 1301 our test insn if we haven't already. */ 1302 if (test_insn == 0) 1303 { 1304 test_insn 1305 = make_insn_raw (gen_rtx_SET (VOIDmode, 1306 gen_rtx_REG (word_mode, 1307 FIRST_PSEUDO_REGISTER * 2), 1308 const0_rtx)); 1309 NEXT_INSN (test_insn) = PREV_INSN (test_insn) = 0; 1310 } 1311 1312 /* Now make an insn like the one we would make when GCSE'ing and see if 1313 valid. */ 1314 PUT_MODE (SET_DEST (PATTERN (test_insn)), GET_MODE (x)); 1315 SET_SRC (PATTERN (test_insn)) = x; 1316 return ((icode = recog (PATTERN (test_insn), test_insn, &num_clobbers)) >= 0 1317 && (num_clobbers == 0 || ! added_clobbers_hard_reg_p (icode))); 1318} 1319 1320/* Return nonzero if the operands of expression X are unchanged from the 1321 start of INSN's basic block up to but not including INSN (if AVAIL_P == 0), 1322 or from INSN to the end of INSN's basic block (if AVAIL_P != 0). */ 1323 1324static int 1325oprs_unchanged_p (rtx x, rtx insn, int avail_p) 1326{ 1327 int i, j; 1328 enum rtx_code code; 1329 const char *fmt; 1330 1331 if (x == 0) 1332 return 1; 1333 1334 code = GET_CODE (x); 1335 switch (code) 1336 { 1337 case REG: 1338 { 1339 struct reg_avail_info *info = ®_avail_info[REGNO (x)]; 1340 1341 if (info->last_bb != current_bb) 1342 return 1; 1343 if (avail_p) 1344 return info->last_set < INSN_CUID (insn); 1345 else 1346 return info->first_set >= INSN_CUID (insn); 1347 } 1348 1349 case MEM: 1350 if (load_killed_in_block_p (current_bb, INSN_CUID (insn), 1351 x, avail_p)) 1352 return 0; 1353 else 1354 return oprs_unchanged_p (XEXP (x, 0), insn, avail_p); 1355 1356 case PRE_DEC: 1357 case PRE_INC: 1358 case POST_DEC: 1359 case POST_INC: 1360 case PRE_MODIFY: 1361 case POST_MODIFY: 1362 return 0; 1363 1364 case PC: 1365 case CC0: /*FIXME*/ 1366 case CONST: 1367 case CONST_INT: 1368 case CONST_DOUBLE: 1369 case CONST_VECTOR: 1370 case SYMBOL_REF: 1371 case LABEL_REF: 1372 case ADDR_VEC: 1373 case ADDR_DIFF_VEC: 1374 return 1; 1375 1376 default: 1377 break; 1378 } 1379 1380 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--) 1381 { 1382 if (fmt[i] == 'e') 1383 { 1384 /* If we are about to do the last recursive call needed at this 1385 level, change it into iteration. This function is called enough 1386 to be worth it. */ 1387 if (i == 0) 1388 return oprs_unchanged_p (XEXP (x, i), insn, avail_p); 1389 1390 else if (! oprs_unchanged_p (XEXP (x, i), insn, avail_p)) 1391 return 0; 1392 } 1393 else if (fmt[i] == 'E') 1394 for (j = 0; j < XVECLEN (x, i); j++) 1395 if (! oprs_unchanged_p (XVECEXP (x, i, j), insn, avail_p)) 1396 return 0; 1397 } 1398 1399 return 1; 1400} 1401 1402/* Used for communication between mems_conflict_for_gcse_p and 1403 load_killed_in_block_p. Nonzero if mems_conflict_for_gcse_p finds a 1404 conflict between two memory references. */ 1405static int gcse_mems_conflict_p; 1406 1407/* Used for communication between mems_conflict_for_gcse_p and 1408 load_killed_in_block_p. A memory reference for a load instruction, 1409 mems_conflict_for_gcse_p will see if a memory store conflicts with 1410 this memory load. */ 1411static rtx gcse_mem_operand; 1412 1413/* DEST is the output of an instruction. If it is a memory reference, and 1414 possibly conflicts with the load found in gcse_mem_operand, then set 1415 gcse_mems_conflict_p to a nonzero value. */ 1416 1417static void 1418mems_conflict_for_gcse_p (rtx dest, rtx setter ATTRIBUTE_UNUSED, 1419 void *data ATTRIBUTE_UNUSED) 1420{ 1421 while (GET_CODE (dest) == SUBREG 1422 || GET_CODE (dest) == ZERO_EXTRACT 1423 || GET_CODE (dest) == SIGN_EXTRACT 1424 || GET_CODE (dest) == STRICT_LOW_PART) 1425 dest = XEXP (dest, 0); 1426 1427 /* If DEST is not a MEM, then it will not conflict with the load. Note 1428 that function calls are assumed to clobber memory, but are handled 1429 elsewhere. */ 1430 if (GET_CODE (dest) != MEM) 1431 return; 1432 1433 /* If we are setting a MEM in our list of specially recognized MEMs, 1434 don't mark as killed this time. */ 1435 1436 if (expr_equiv_p (dest, gcse_mem_operand) && pre_ldst_mems != NULL) 1437 { 1438 if (!find_rtx_in_ldst (dest)) 1439 gcse_mems_conflict_p = 1; 1440 return; 1441 } 1442 1443 if (true_dependence (dest, GET_MODE (dest), gcse_mem_operand, 1444 rtx_addr_varies_p)) 1445 gcse_mems_conflict_p = 1; 1446} 1447 1448/* Return nonzero if the expression in X (a memory reference) is killed 1449 in block BB before or after the insn with the CUID in UID_LIMIT. 1450 AVAIL_P is nonzero for kills after UID_LIMIT, and zero for kills 1451 before UID_LIMIT. 1452 1453 To check the entire block, set UID_LIMIT to max_uid + 1 and 1454 AVAIL_P to 0. */ 1455 1456static int 1457load_killed_in_block_p (basic_block bb, int uid_limit, rtx x, int avail_p) 1458{ 1459 rtx list_entry = modify_mem_list[bb->index]; 1460 while (list_entry) 1461 { 1462 rtx setter; 1463 /* Ignore entries in the list that do not apply. */ 1464 if ((avail_p 1465 && INSN_CUID (XEXP (list_entry, 0)) < uid_limit) 1466 || (! avail_p 1467 && INSN_CUID (XEXP (list_entry, 0)) > uid_limit)) 1468 { 1469 list_entry = XEXP (list_entry, 1); 1470 continue; 1471 } 1472 1473 setter = XEXP (list_entry, 0); 1474 1475 /* If SETTER is a call everything is clobbered. Note that calls 1476 to pure functions are never put on the list, so we need not 1477 worry about them. */ 1478 if (GET_CODE (setter) == CALL_INSN) 1479 return 1; 1480 1481 /* SETTER must be an INSN of some kind that sets memory. Call 1482 note_stores to examine each hunk of memory that is modified. 1483 1484 The note_stores interface is pretty limited, so we have to 1485 communicate via global variables. Yuk. */ 1486 gcse_mem_operand = x; 1487 gcse_mems_conflict_p = 0; 1488 note_stores (PATTERN (setter), mems_conflict_for_gcse_p, NULL); 1489 if (gcse_mems_conflict_p) 1490 return 1; 1491 list_entry = XEXP (list_entry, 1); 1492 } 1493 return 0; 1494} 1495 1496/* Return nonzero if the operands of expression X are unchanged from 1497 the start of INSN's basic block up to but not including INSN. */ 1498 1499static int 1500oprs_anticipatable_p (rtx x, rtx insn) 1501{ 1502 return oprs_unchanged_p (x, insn, 0); 1503} 1504 1505/* Return nonzero if the operands of expression X are unchanged from 1506 INSN to the end of INSN's basic block. */ 1507 1508static int 1509oprs_available_p (rtx x, rtx insn) 1510{ 1511 return oprs_unchanged_p (x, insn, 1); 1512} 1513 1514/* Hash expression X. 1515 1516 MODE is only used if X is a CONST_INT. DO_NOT_RECORD_P is a boolean 1517 indicating if a volatile operand is found or if the expression contains 1518 something we don't want to insert in the table. HASH_TABLE_SIZE is 1519 the current size of the hash table to be probed. 1520 1521 ??? One might want to merge this with canon_hash. Later. */ 1522 1523static unsigned int 1524hash_expr (rtx x, enum machine_mode mode, int *do_not_record_p, 1525 int hash_table_size) 1526{ 1527 unsigned int hash; 1528 1529 *do_not_record_p = 0; 1530 1531 hash = hash_expr_1 (x, mode, do_not_record_p); 1532 return hash % hash_table_size; 1533} 1534 1535/* Hash a string. Just add its bytes up. */ 1536 1537static inline unsigned 1538hash_string_1 (const char *ps) 1539{ 1540 unsigned hash = 0; 1541 const unsigned char *p = (const unsigned char *) ps; 1542 1543 if (p) 1544 while (*p) 1545 hash += *p++; 1546 1547 return hash; 1548} 1549 1550/* Subroutine of hash_expr to do the actual work. */ 1551 1552static unsigned int 1553hash_expr_1 (rtx x, enum machine_mode mode, int *do_not_record_p) 1554{ 1555 int i, j; 1556 unsigned hash = 0; 1557 enum rtx_code code; 1558 const char *fmt; 1559 1560 /* Used to turn recursion into iteration. We can't rely on GCC's 1561 tail-recursion elimination since we need to keep accumulating values 1562 in HASH. */ 1563 1564 if (x == 0) 1565 return hash; 1566 1567 repeat: 1568 code = GET_CODE (x); 1569 switch (code) 1570 { 1571 case REG: 1572 hash += ((unsigned int) REG << 7) + REGNO (x); 1573 return hash; 1574 1575 case CONST_INT: 1576 hash += (((unsigned int) CONST_INT << 7) + (unsigned int) mode 1577 + (unsigned int) INTVAL (x)); 1578 return hash; 1579 1580 case CONST_DOUBLE: 1581 /* This is like the general case, except that it only counts 1582 the integers representing the constant. */ 1583 hash += (unsigned int) code + (unsigned int) GET_MODE (x); 1584 if (GET_MODE (x) != VOIDmode) 1585 for (i = 2; i < GET_RTX_LENGTH (CONST_DOUBLE); i++) 1586 hash += (unsigned int) XWINT (x, i); 1587 else 1588 hash += ((unsigned int) CONST_DOUBLE_LOW (x) 1589 + (unsigned int) CONST_DOUBLE_HIGH (x)); 1590 return hash; 1591 1592 case CONST_VECTOR: 1593 { 1594 int units; 1595 rtx elt; 1596 1597 units = CONST_VECTOR_NUNITS (x); 1598 1599 for (i = 0; i < units; ++i) 1600 { 1601 elt = CONST_VECTOR_ELT (x, i); 1602 hash += hash_expr_1 (elt, GET_MODE (elt), do_not_record_p); 1603 } 1604 1605 return hash; 1606 } 1607 1608 /* Assume there is only one rtx object for any given label. */ 1609 case LABEL_REF: 1610 /* We don't hash on the address of the CODE_LABEL to avoid bootstrap 1611 differences and differences between each stage's debugging dumps. */ 1612 hash += (((unsigned int) LABEL_REF << 7) 1613 + CODE_LABEL_NUMBER (XEXP (x, 0))); 1614 return hash; 1615 1616 case SYMBOL_REF: 1617 { 1618 /* Don't hash on the symbol's address to avoid bootstrap differences. 1619 Different hash values may cause expressions to be recorded in 1620 different orders and thus different registers to be used in the 1621 final assembler. This also avoids differences in the dump files 1622 between various stages. */ 1623 unsigned int h = 0; 1624 const unsigned char *p = (const unsigned char *) XSTR (x, 0); 1625 1626 while (*p) 1627 h += (h << 7) + *p++; /* ??? revisit */ 1628 1629 hash += ((unsigned int) SYMBOL_REF << 7) + h; 1630 return hash; 1631 } 1632 1633 case MEM: 1634 if (MEM_VOLATILE_P (x)) 1635 { 1636 *do_not_record_p = 1; 1637 return 0; 1638 } 1639 1640 hash += (unsigned int) MEM; 1641 /* We used alias set for hashing, but this is not good, since the alias 1642 set may differ in -fprofile-arcs and -fbranch-probabilities compilation 1643 causing the profiles to fail to match. */ 1644 x = XEXP (x, 0); 1645 goto repeat; 1646 1647 case PRE_DEC: 1648 case PRE_INC: 1649 case POST_DEC: 1650 case POST_INC: 1651 case PC: 1652 case CC0: 1653 case CALL: 1654 case UNSPEC_VOLATILE: 1655 *do_not_record_p = 1; 1656 return 0; 1657 1658 case ASM_OPERANDS: 1659 if (MEM_VOLATILE_P (x)) 1660 { 1661 *do_not_record_p = 1; 1662 return 0; 1663 } 1664 else 1665 { 1666 /* We don't want to take the filename and line into account. */ 1667 hash += (unsigned) code + (unsigned) GET_MODE (x) 1668 + hash_string_1 (ASM_OPERANDS_TEMPLATE (x)) 1669 + hash_string_1 (ASM_OPERANDS_OUTPUT_CONSTRAINT (x)) 1670 + (unsigned) ASM_OPERANDS_OUTPUT_IDX (x); 1671 1672 if (ASM_OPERANDS_INPUT_LENGTH (x)) 1673 { 1674 for (i = 1; i < ASM_OPERANDS_INPUT_LENGTH (x); i++) 1675 { 1676 hash += (hash_expr_1 (ASM_OPERANDS_INPUT (x, i), 1677 GET_MODE (ASM_OPERANDS_INPUT (x, i)), 1678 do_not_record_p) 1679 + hash_string_1 (ASM_OPERANDS_INPUT_CONSTRAINT 1680 (x, i))); 1681 } 1682 1683 hash += hash_string_1 (ASM_OPERANDS_INPUT_CONSTRAINT (x, 0)); 1684 x = ASM_OPERANDS_INPUT (x, 0); 1685 mode = GET_MODE (x); 1686 goto repeat; 1687 } 1688 return hash; 1689 } 1690 1691 default: 1692 break; 1693 } 1694 1695 hash += (unsigned) code + (unsigned) GET_MODE (x); 1696 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--) 1697 { 1698 if (fmt[i] == 'e') 1699 { 1700 /* If we are about to do the last recursive call 1701 needed at this level, change it into iteration. 1702 This function is called enough to be worth it. */ 1703 if (i == 0) 1704 { 1705 x = XEXP (x, i); 1706 goto repeat; 1707 } 1708 1709 hash += hash_expr_1 (XEXP (x, i), 0, do_not_record_p); 1710 if (*do_not_record_p) 1711 return 0; 1712 } 1713 1714 else if (fmt[i] == 'E') 1715 for (j = 0; j < XVECLEN (x, i); j++) 1716 { 1717 hash += hash_expr_1 (XVECEXP (x, i, j), 0, do_not_record_p); 1718 if (*do_not_record_p) 1719 return 0; 1720 } 1721 1722 else if (fmt[i] == 's') 1723 hash += hash_string_1 (XSTR (x, i)); 1724 else if (fmt[i] == 'i') 1725 hash += (unsigned int) XINT (x, i); 1726 else 1727 abort (); 1728 } 1729 1730 return hash; 1731} 1732 1733/* Hash a set of register REGNO. 1734 1735 Sets are hashed on the register that is set. This simplifies the PRE copy 1736 propagation code. 1737 1738 ??? May need to make things more elaborate. Later, as necessary. */ 1739 1740static unsigned int 1741hash_set (int regno, int hash_table_size) 1742{ 1743 unsigned int hash; 1744 1745 hash = regno; 1746 return hash % hash_table_size; 1747} 1748 1749/* Return nonzero if exp1 is equivalent to exp2. 1750 ??? Borrowed from cse.c. Might want to remerge with cse.c. Later. */ 1751 1752static int 1753expr_equiv_p (rtx x, rtx y) 1754{ 1755 int i, j; 1756 enum rtx_code code; 1757 const char *fmt; 1758 1759 if (x == y) 1760 return 1; 1761 1762 if (x == 0 || y == 0) 1763 return 0; 1764 1765 code = GET_CODE (x); 1766 if (code != GET_CODE (y)) 1767 return 0; 1768 1769 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. */ 1770 if (GET_MODE (x) != GET_MODE (y)) 1771 return 0; 1772 1773 switch (code) 1774 { 1775 case PC: 1776 case CC0: 1777 case CONST_INT: 1778 return 0; 1779 1780 case LABEL_REF: 1781 return XEXP (x, 0) == XEXP (y, 0); 1782 1783 case SYMBOL_REF: 1784 return XSTR (x, 0) == XSTR (y, 0); 1785 1786 case REG: 1787 return REGNO (x) == REGNO (y); 1788 1789 case MEM: 1790 /* Can't merge two expressions in different alias sets, since we can 1791 decide that the expression is transparent in a block when it isn't, 1792 due to it being set with the different alias set. */ 1793 if (MEM_ALIAS_SET (x) != MEM_ALIAS_SET (y)) 1794 return 0; 1795 1796 /* A volatile mem should not be considered equivalent to any other. */ 1797 if (MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y)) 1798 return 0; 1799 break; 1800 1801 /* For commutative operations, check both orders. */ 1802 case PLUS: 1803 case MULT: 1804 case AND: 1805 case IOR: 1806 case XOR: 1807 case NE: 1808 case EQ: 1809 return ((expr_equiv_p (XEXP (x, 0), XEXP (y, 0)) 1810 && expr_equiv_p (XEXP (x, 1), XEXP (y, 1))) 1811 || (expr_equiv_p (XEXP (x, 0), XEXP (y, 1)) 1812 && expr_equiv_p (XEXP (x, 1), XEXP (y, 0)))); 1813 1814 case ASM_OPERANDS: 1815 /* We don't use the generic code below because we want to 1816 disregard filename and line numbers. */ 1817 1818 /* A volatile asm isn't equivalent to any other. */ 1819 if (MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y)) 1820 return 0; 1821 1822 if (GET_MODE (x) != GET_MODE (y) 1823 || strcmp (ASM_OPERANDS_TEMPLATE (x), ASM_OPERANDS_TEMPLATE (y)) 1824 || strcmp (ASM_OPERANDS_OUTPUT_CONSTRAINT (x), 1825 ASM_OPERANDS_OUTPUT_CONSTRAINT (y)) 1826 || ASM_OPERANDS_OUTPUT_IDX (x) != ASM_OPERANDS_OUTPUT_IDX (y) 1827 || ASM_OPERANDS_INPUT_LENGTH (x) != ASM_OPERANDS_INPUT_LENGTH (y)) 1828 return 0; 1829 1830 if (ASM_OPERANDS_INPUT_LENGTH (x)) 1831 { 1832 for (i = ASM_OPERANDS_INPUT_LENGTH (x) - 1; i >= 0; i--) 1833 if (! expr_equiv_p (ASM_OPERANDS_INPUT (x, i), 1834 ASM_OPERANDS_INPUT (y, i)) 1835 || strcmp (ASM_OPERANDS_INPUT_CONSTRAINT (x, i), 1836 ASM_OPERANDS_INPUT_CONSTRAINT (y, i))) 1837 return 0; 1838 } 1839 1840 return 1; 1841 1842 default: 1843 break; 1844 } 1845 1846 /* Compare the elements. If any pair of corresponding elements 1847 fail to match, return 0 for the whole thing. */ 1848 1849 fmt = GET_RTX_FORMAT (code); 1850 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 1851 { 1852 switch (fmt[i]) 1853 { 1854 case 'e': 1855 if (! expr_equiv_p (XEXP (x, i), XEXP (y, i))) 1856 return 0; 1857 break; 1858 1859 case 'E': 1860 if (XVECLEN (x, i) != XVECLEN (y, i)) 1861 return 0; 1862 for (j = 0; j < XVECLEN (x, i); j++) 1863 if (! expr_equiv_p (XVECEXP (x, i, j), XVECEXP (y, i, j))) 1864 return 0; 1865 break; 1866 1867 case 's': 1868 if (strcmp (XSTR (x, i), XSTR (y, i))) 1869 return 0; 1870 break; 1871 1872 case 'i': 1873 if (XINT (x, i) != XINT (y, i)) 1874 return 0; 1875 break; 1876 1877 case 'w': 1878 if (XWINT (x, i) != XWINT (y, i)) 1879 return 0; 1880 break; 1881 1882 case '0': 1883 break; 1884 1885 default: 1886 abort (); 1887 } 1888 } 1889 1890 return 1; 1891} 1892 1893/* Insert expression X in INSN in the hash TABLE. 1894 If it is already present, record it as the last occurrence in INSN's 1895 basic block. 1896 1897 MODE is the mode of the value X is being stored into. 1898 It is only used if X is a CONST_INT. 1899 1900 ANTIC_P is nonzero if X is an anticipatable expression. 1901 AVAIL_P is nonzero if X is an available expression. */ 1902 1903static void 1904insert_expr_in_table (rtx x, enum machine_mode mode, rtx insn, int antic_p, 1905 int avail_p, struct hash_table *table) 1906{ 1907 int found, do_not_record_p; 1908 unsigned int hash; 1909 struct expr *cur_expr, *last_expr = NULL; 1910 struct occr *antic_occr, *avail_occr; 1911 struct occr *last_occr = NULL; 1912 1913 hash = hash_expr (x, mode, &do_not_record_p, table->size); 1914 1915 /* Do not insert expression in table if it contains volatile operands, 1916 or if hash_expr determines the expression is something we don't want 1917 to or can't handle. */ 1918 if (do_not_record_p) 1919 return; 1920 1921 cur_expr = table->table[hash]; 1922 found = 0; 1923 1924 while (cur_expr && 0 == (found = expr_equiv_p (cur_expr->expr, x))) 1925 { 1926 /* If the expression isn't found, save a pointer to the end of 1927 the list. */ 1928 last_expr = cur_expr; 1929 cur_expr = cur_expr->next_same_hash; 1930 } 1931 1932 if (! found) 1933 { 1934 cur_expr = gcse_alloc (sizeof (struct expr)); 1935 bytes_used += sizeof (struct expr); 1936 if (table->table[hash] == NULL) 1937 /* This is the first pattern that hashed to this index. */ 1938 table->table[hash] = cur_expr; 1939 else 1940 /* Add EXPR to end of this hash chain. */ 1941 last_expr->next_same_hash = cur_expr; 1942 1943 /* Set the fields of the expr element. */ 1944 cur_expr->expr = x; 1945 cur_expr->bitmap_index = table->n_elems++; 1946 cur_expr->next_same_hash = NULL; 1947 cur_expr->antic_occr = NULL; 1948 cur_expr->avail_occr = NULL; 1949 } 1950 1951 /* Now record the occurrence(s). */ 1952 if (antic_p) 1953 { 1954 antic_occr = cur_expr->antic_occr; 1955 1956 /* Search for another occurrence in the same basic block. */ 1957 while (antic_occr && BLOCK_NUM (antic_occr->insn) != BLOCK_NUM (insn)) 1958 { 1959 /* If an occurrence isn't found, save a pointer to the end of 1960 the list. */ 1961 last_occr = antic_occr; 1962 antic_occr = antic_occr->next; 1963 } 1964 1965 if (antic_occr) 1966 /* Found another instance of the expression in the same basic block. 1967 Prefer the currently recorded one. We want the first one in the 1968 block and the block is scanned from start to end. */ 1969 ; /* nothing to do */ 1970 else 1971 { 1972 /* First occurrence of this expression in this basic block. */ 1973 antic_occr = gcse_alloc (sizeof (struct occr)); 1974 bytes_used += sizeof (struct occr); 1975 /* First occurrence of this expression in any block? */ 1976 if (cur_expr->antic_occr == NULL) 1977 cur_expr->antic_occr = antic_occr; 1978 else 1979 last_occr->next = antic_occr; 1980 1981 antic_occr->insn = insn; 1982 antic_occr->next = NULL; 1983 } 1984 } 1985 1986 if (avail_p) 1987 { 1988 avail_occr = cur_expr->avail_occr; 1989 1990 /* Search for another occurrence in the same basic block. */ 1991 while (avail_occr && BLOCK_NUM (avail_occr->insn) != BLOCK_NUM (insn)) 1992 { 1993 /* If an occurrence isn't found, save a pointer to the end of 1994 the list. */ 1995 last_occr = avail_occr; 1996 avail_occr = avail_occr->next; 1997 } 1998 1999 if (avail_occr) 2000 /* Found another instance of the expression in the same basic block. 2001 Prefer this occurrence to the currently recorded one. We want 2002 the last one in the block and the block is scanned from start 2003 to end. */ 2004 avail_occr->insn = insn; 2005 else 2006 { 2007 /* First occurrence of this expression in this basic block. */ 2008 avail_occr = gcse_alloc (sizeof (struct occr)); 2009 bytes_used += sizeof (struct occr); 2010 2011 /* First occurrence of this expression in any block? */ 2012 if (cur_expr->avail_occr == NULL) 2013 cur_expr->avail_occr = avail_occr; 2014 else 2015 last_occr->next = avail_occr; 2016 2017 avail_occr->insn = insn; 2018 avail_occr->next = NULL; 2019 } 2020 } 2021} 2022 2023/* Insert pattern X in INSN in the hash table. 2024 X is a SET of a reg to either another reg or a constant. 2025 If it is already present, record it as the last occurrence in INSN's 2026 basic block. */ 2027 2028static void 2029insert_set_in_table (rtx x, rtx insn, struct hash_table *table) 2030{ 2031 int found; 2032 unsigned int hash; 2033 struct expr *cur_expr, *last_expr = NULL; 2034 struct occr *cur_occr, *last_occr = NULL; 2035 2036 if (GET_CODE (x) != SET 2037 || GET_CODE (SET_DEST (x)) != REG) 2038 abort (); 2039 2040 hash = hash_set (REGNO (SET_DEST (x)), table->size); 2041 2042 cur_expr = table->table[hash]; 2043 found = 0; 2044 2045 while (cur_expr && 0 == (found = expr_equiv_p (cur_expr->expr, x))) 2046 { 2047 /* If the expression isn't found, save a pointer to the end of 2048 the list. */ 2049 last_expr = cur_expr; 2050 cur_expr = cur_expr->next_same_hash; 2051 } 2052 2053 if (! found) 2054 { 2055 cur_expr = gcse_alloc (sizeof (struct expr)); 2056 bytes_used += sizeof (struct expr); 2057 if (table->table[hash] == NULL) 2058 /* This is the first pattern that hashed to this index. */ 2059 table->table[hash] = cur_expr; 2060 else 2061 /* Add EXPR to end of this hash chain. */ 2062 last_expr->next_same_hash = cur_expr; 2063 2064 /* Set the fields of the expr element. 2065 We must copy X because it can be modified when copy propagation is 2066 performed on its operands. */ 2067 cur_expr->expr = copy_rtx (x); 2068 cur_expr->bitmap_index = table->n_elems++; 2069 cur_expr->next_same_hash = NULL; 2070 cur_expr->antic_occr = NULL; 2071 cur_expr->avail_occr = NULL; 2072 } 2073 2074 /* Now record the occurrence. */ 2075 cur_occr = cur_expr->avail_occr; 2076 2077 /* Search for another occurrence in the same basic block. */ 2078 while (cur_occr && BLOCK_NUM (cur_occr->insn) != BLOCK_NUM (insn)) 2079 { 2080 /* If an occurrence isn't found, save a pointer to the end of 2081 the list. */ 2082 last_occr = cur_occr; 2083 cur_occr = cur_occr->next; 2084 } 2085 2086 if (cur_occr) 2087 /* Found another instance of the expression in the same basic block. 2088 Prefer this occurrence to the currently recorded one. We want the 2089 last one in the block and the block is scanned from start to end. */ 2090 cur_occr->insn = insn; 2091 else 2092 { 2093 /* First occurrence of this expression in this basic block. */ 2094 cur_occr = gcse_alloc (sizeof (struct occr)); 2095 bytes_used += sizeof (struct occr); 2096 2097 /* First occurrence of this expression in any block? */ 2098 if (cur_expr->avail_occr == NULL) 2099 cur_expr->avail_occr = cur_occr; 2100 else 2101 last_occr->next = cur_occr; 2102 2103 cur_occr->insn = insn; 2104 cur_occr->next = NULL; 2105 } 2106} 2107 2108/* Determine whether the rtx X should be treated as a constant for 2109 the purposes of GCSE's constant propagation. */ 2110 2111static bool 2112gcse_constant_p (rtx x) 2113{ 2114 /* Consider a COMPARE of two integers constant. */ 2115 if (GET_CODE (x) == COMPARE 2116 && GET_CODE (XEXP (x, 0)) == CONST_INT 2117 && GET_CODE (XEXP (x, 1)) == CONST_INT) 2118 return true; 2119 2120 2121 /* Consider a COMPARE of the same registers is a constant 2122 if they are not floating point registers. */ 2123 if (GET_CODE(x) == COMPARE 2124 && GET_CODE (XEXP (x, 0)) == REG 2125 && GET_CODE (XEXP (x, 1)) == REG 2126 && REGNO (XEXP (x, 0)) == REGNO (XEXP (x, 1)) 2127 && ! FLOAT_MODE_P (GET_MODE (XEXP (x, 0))) 2128 && ! FLOAT_MODE_P (GET_MODE (XEXP (x, 1)))) 2129 return true; 2130 2131 if (GET_CODE (x) == CONSTANT_P_RTX) 2132 return false; 2133 2134 return CONSTANT_P (x); 2135} 2136 2137/* Scan pattern PAT of INSN and add an entry to the hash TABLE (set or 2138 expression one). */ 2139 2140static void 2141hash_scan_set (rtx pat, rtx insn, struct hash_table *table) 2142{ 2143 rtx src = SET_SRC (pat); 2144 rtx dest = SET_DEST (pat); 2145 rtx note; 2146 2147 if (GET_CODE (src) == CALL) 2148 hash_scan_call (src, insn, table); 2149 2150 else if (GET_CODE (dest) == REG) 2151 { 2152 unsigned int regno = REGNO (dest); 2153 rtx tmp; 2154 2155 /* If this is a single set and we are doing constant propagation, 2156 see if a REG_NOTE shows this equivalent to a constant. */ 2157 if (table->set_p && (note = find_reg_equal_equiv_note (insn)) != 0 2158 && gcse_constant_p (XEXP (note, 0))) 2159 src = XEXP (note, 0), pat = gen_rtx_SET (VOIDmode, dest, src); 2160 2161 /* Only record sets of pseudo-regs in the hash table. */ 2162 if (! table->set_p 2163 && regno >= FIRST_PSEUDO_REGISTER 2164 /* Don't GCSE something if we can't do a reg/reg copy. */ 2165 && can_copy_p (GET_MODE (dest)) 2166 /* GCSE commonly inserts instruction after the insn. We can't 2167 do that easily for EH_REGION notes so disable GCSE on these 2168 for now. */ 2169 && !find_reg_note (insn, REG_EH_REGION, NULL_RTX) 2170 /* Is SET_SRC something we want to gcse? */ 2171 && want_to_gcse_p (src) 2172 /* Don't CSE a nop. */ 2173 && ! set_noop_p (pat) 2174 /* Don't GCSE if it has attached REG_EQUIV note. 2175 At this point this only function parameters should have 2176 REG_EQUIV notes and if the argument slot is used somewhere 2177 explicitly, it means address of parameter has been taken, 2178 so we should not extend the lifetime of the pseudo. */ 2179 && ((note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) == 0 2180 || GET_CODE (XEXP (note, 0)) != MEM)) 2181 { 2182 /* An expression is not anticipatable if its operands are 2183 modified before this insn or if this is not the only SET in 2184 this insn. */ 2185 int antic_p = oprs_anticipatable_p (src, insn) && single_set (insn); 2186 /* An expression is not available if its operands are 2187 subsequently modified, including this insn. It's also not 2188 available if this is a branch, because we can't insert 2189 a set after the branch. */ 2190 int avail_p = (oprs_available_p (src, insn) 2191 && ! JUMP_P (insn)); 2192 2193 insert_expr_in_table (src, GET_MODE (dest), insn, antic_p, avail_p, table); 2194 } 2195 2196 /* Record sets for constant/copy propagation. */ 2197 else if (table->set_p 2198 && regno >= FIRST_PSEUDO_REGISTER 2199 && ((GET_CODE (src) == REG 2200 && REGNO (src) >= FIRST_PSEUDO_REGISTER 2201 && can_copy_p (GET_MODE (dest)) 2202 && REGNO (src) != regno) 2203 || gcse_constant_p (src)) 2204 /* A copy is not available if its src or dest is subsequently 2205 modified. Here we want to search from INSN+1 on, but 2206 oprs_available_p searches from INSN on. */ 2207 && (insn == BB_END (BLOCK_FOR_INSN (insn)) 2208 || ((tmp = next_nonnote_insn (insn)) != NULL_RTX 2209 && oprs_available_p (pat, tmp)))) 2210 insert_set_in_table (pat, insn, table); 2211 } 2212 /* In case of store we want to consider the memory value as available in 2213 the REG stored in that memory. This makes it possible to remove 2214 redundant loads from due to stores to the same location. */ 2215 else if (flag_gcse_las && GET_CODE (src) == REG && GET_CODE (dest) == MEM) 2216 { 2217 unsigned int regno = REGNO (src); 2218 2219 /* Do not do this for constant/copy propagation. */ 2220 if (! table->set_p 2221 /* Only record sets of pseudo-regs in the hash table. */ 2222 && regno >= FIRST_PSEUDO_REGISTER 2223 /* Don't GCSE something if we can't do a reg/reg copy. */ 2224 && can_copy_p (GET_MODE (src)) 2225 /* GCSE commonly inserts instruction after the insn. We can't 2226 do that easily for EH_REGION notes so disable GCSE on these 2227 for now. */ 2228 && ! find_reg_note (insn, REG_EH_REGION, NULL_RTX) 2229 /* Is SET_DEST something we want to gcse? */ 2230 && want_to_gcse_p (dest) 2231 /* Don't CSE a nop. */ 2232 && ! set_noop_p (pat) 2233 /* Don't GCSE if it has attached REG_EQUIV note. 2234 At this point this only function parameters should have 2235 REG_EQUIV notes and if the argument slot is used somewhere 2236 explicitly, it means address of parameter has been taken, 2237 so we should not extend the lifetime of the pseudo. */ 2238 && ((note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) == 0 2239 || GET_CODE (XEXP (note, 0)) != MEM)) 2240 { 2241 /* Stores are never anticipatable. */ 2242 int antic_p = 0; 2243 /* An expression is not available if its operands are 2244 subsequently modified, including this insn. It's also not 2245 available if this is a branch, because we can't insert 2246 a set after the branch. */ 2247 int avail_p = oprs_available_p (dest, insn) 2248 && ! JUMP_P (insn); 2249 2250 /* Record the memory expression (DEST) in the hash table. */ 2251 insert_expr_in_table (dest, GET_MODE (dest), insn, 2252 antic_p, avail_p, table); 2253 } 2254 } 2255} 2256 2257static void 2258hash_scan_clobber (rtx x ATTRIBUTE_UNUSED, rtx insn ATTRIBUTE_UNUSED, 2259 struct hash_table *table ATTRIBUTE_UNUSED) 2260{ 2261 /* Currently nothing to do. */ 2262} 2263 2264static void 2265hash_scan_call (rtx x ATTRIBUTE_UNUSED, rtx insn ATTRIBUTE_UNUSED, 2266 struct hash_table *table ATTRIBUTE_UNUSED) 2267{ 2268 /* Currently nothing to do. */ 2269} 2270 2271/* Process INSN and add hash table entries as appropriate. 2272 2273 Only available expressions that set a single pseudo-reg are recorded. 2274 2275 Single sets in a PARALLEL could be handled, but it's an extra complication 2276 that isn't dealt with right now. The trick is handling the CLOBBERs that 2277 are also in the PARALLEL. Later. 2278 2279 If SET_P is nonzero, this is for the assignment hash table, 2280 otherwise it is for the expression hash table. 2281 If IN_LIBCALL_BLOCK nonzero, we are in a libcall block, and should 2282 not record any expressions. */ 2283 2284static void 2285hash_scan_insn (rtx insn, struct hash_table *table, int in_libcall_block) 2286{ 2287 rtx pat = PATTERN (insn); 2288 int i; 2289 2290 if (in_libcall_block) 2291 return; 2292 2293 /* Pick out the sets of INSN and for other forms of instructions record 2294 what's been modified. */ 2295 2296 if (GET_CODE (pat) == SET) 2297 hash_scan_set (pat, insn, table); 2298 else if (GET_CODE (pat) == PARALLEL) 2299 for (i = 0; i < XVECLEN (pat, 0); i++) 2300 { 2301 rtx x = XVECEXP (pat, 0, i); 2302 2303 if (GET_CODE (x) == SET) 2304 hash_scan_set (x, insn, table); 2305 else if (GET_CODE (x) == CLOBBER) 2306 hash_scan_clobber (x, insn, table); 2307 else if (GET_CODE (x) == CALL) 2308 hash_scan_call (x, insn, table); 2309 } 2310 2311 else if (GET_CODE (pat) == CLOBBER) 2312 hash_scan_clobber (pat, insn, table); 2313 else if (GET_CODE (pat) == CALL) 2314 hash_scan_call (pat, insn, table); 2315} 2316 2317static void 2318dump_hash_table (FILE *file, const char *name, struct hash_table *table) 2319{ 2320 int i; 2321 /* Flattened out table, so it's printed in proper order. */ 2322 struct expr **flat_table; 2323 unsigned int *hash_val; 2324 struct expr *expr; 2325 2326 flat_table = xcalloc (table->n_elems, sizeof (struct expr *)); 2327 hash_val = xmalloc (table->n_elems * sizeof (unsigned int)); 2328 2329 for (i = 0; i < (int) table->size; i++) 2330 for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash) 2331 { 2332 flat_table[expr->bitmap_index] = expr; 2333 hash_val[expr->bitmap_index] = i; 2334 } 2335 2336 fprintf (file, "%s hash table (%d buckets, %d entries)\n", 2337 name, table->size, table->n_elems); 2338 2339 for (i = 0; i < (int) table->n_elems; i++) 2340 if (flat_table[i] != 0) 2341 { 2342 expr = flat_table[i]; 2343 fprintf (file, "Index %d (hash value %d)\n ", 2344 expr->bitmap_index, hash_val[i]); 2345 print_rtl (file, expr->expr); 2346 fprintf (file, "\n"); 2347 } 2348 2349 fprintf (file, "\n"); 2350 2351 free (flat_table); 2352 free (hash_val); 2353} 2354 2355/* Record register first/last/block set information for REGNO in INSN. 2356 2357 first_set records the first place in the block where the register 2358 is set and is used to compute "anticipatability". 2359 2360 last_set records the last place in the block where the register 2361 is set and is used to compute "availability". 2362 2363 last_bb records the block for which first_set and last_set are 2364 valid, as a quick test to invalidate them. 2365 2366 reg_set_in_block records whether the register is set in the block 2367 and is used to compute "transparency". */ 2368 2369static void 2370record_last_reg_set_info (rtx insn, int regno) 2371{ 2372 struct reg_avail_info *info = ®_avail_info[regno]; 2373 int cuid = INSN_CUID (insn); 2374 2375 info->last_set = cuid; 2376 if (info->last_bb != current_bb) 2377 { 2378 info->last_bb = current_bb; 2379 info->first_set = cuid; 2380 SET_BIT (reg_set_in_block[current_bb->index], regno); 2381 } 2382} 2383 2384 2385/* Record all of the canonicalized MEMs of record_last_mem_set_info's insn. 2386 Note we store a pair of elements in the list, so they have to be 2387 taken off pairwise. */ 2388 2389static void 2390canon_list_insert (rtx dest ATTRIBUTE_UNUSED, rtx unused1 ATTRIBUTE_UNUSED, 2391 void * v_insn) 2392{ 2393 rtx dest_addr, insn; 2394 int bb; 2395 2396 while (GET_CODE (dest) == SUBREG 2397 || GET_CODE (dest) == ZERO_EXTRACT 2398 || GET_CODE (dest) == SIGN_EXTRACT 2399 || GET_CODE (dest) == STRICT_LOW_PART) 2400 dest = XEXP (dest, 0); 2401 2402 /* If DEST is not a MEM, then it will not conflict with a load. Note 2403 that function calls are assumed to clobber memory, but are handled 2404 elsewhere. */ 2405 2406 if (GET_CODE (dest) != MEM) 2407 return; 2408 2409 dest_addr = get_addr (XEXP (dest, 0)); 2410 dest_addr = canon_rtx (dest_addr); 2411 insn = (rtx) v_insn; 2412 bb = BLOCK_NUM (insn); 2413 2414 canon_modify_mem_list[bb] = 2415 alloc_EXPR_LIST (VOIDmode, dest_addr, canon_modify_mem_list[bb]); 2416 canon_modify_mem_list[bb] = 2417 alloc_EXPR_LIST (VOIDmode, dest, canon_modify_mem_list[bb]); 2418 bitmap_set_bit (canon_modify_mem_list_set, bb); 2419} 2420 2421/* Record memory modification information for INSN. We do not actually care 2422 about the memory location(s) that are set, or even how they are set (consider 2423 a CALL_INSN). We merely need to record which insns modify memory. */ 2424 2425static void 2426record_last_mem_set_info (rtx insn) 2427{ 2428 int bb = BLOCK_NUM (insn); 2429 2430 /* load_killed_in_block_p will handle the case of calls clobbering 2431 everything. */ 2432 modify_mem_list[bb] = alloc_INSN_LIST (insn, modify_mem_list[bb]); 2433 bitmap_set_bit (modify_mem_list_set, bb); 2434 2435 if (GET_CODE (insn) == CALL_INSN) 2436 { 2437 /* Note that traversals of this loop (other than for free-ing) 2438 will break after encountering a CALL_INSN. So, there's no 2439 need to insert a pair of items, as canon_list_insert does. */ 2440 canon_modify_mem_list[bb] = 2441 alloc_INSN_LIST (insn, canon_modify_mem_list[bb]); 2442 bitmap_set_bit (canon_modify_mem_list_set, bb); 2443 } 2444 else 2445 note_stores (PATTERN (insn), canon_list_insert, (void*) insn); 2446} 2447 2448/* Called from compute_hash_table via note_stores to handle one 2449 SET or CLOBBER in an insn. DATA is really the instruction in which 2450 the SET is taking place. */ 2451 2452static void 2453record_last_set_info (rtx dest, rtx setter ATTRIBUTE_UNUSED, void *data) 2454{ 2455 rtx last_set_insn = (rtx) data; 2456 2457 if (GET_CODE (dest) == SUBREG) 2458 dest = SUBREG_REG (dest); 2459 2460 if (GET_CODE (dest) == REG) 2461 record_last_reg_set_info (last_set_insn, REGNO (dest)); 2462 else if (GET_CODE (dest) == MEM 2463 /* Ignore pushes, they clobber nothing. */ 2464 && ! push_operand (dest, GET_MODE (dest))) 2465 record_last_mem_set_info (last_set_insn); 2466} 2467 2468/* Top level function to create an expression or assignment hash table. 2469 2470 Expression entries are placed in the hash table if 2471 - they are of the form (set (pseudo-reg) src), 2472 - src is something we want to perform GCSE on, 2473 - none of the operands are subsequently modified in the block 2474 2475 Assignment entries are placed in the hash table if 2476 - they are of the form (set (pseudo-reg) src), 2477 - src is something we want to perform const/copy propagation on, 2478 - none of the operands or target are subsequently modified in the block 2479 2480 Currently src must be a pseudo-reg or a const_int. 2481 2482 TABLE is the table computed. */ 2483 2484static void 2485compute_hash_table_work (struct hash_table *table) 2486{ 2487 unsigned int i; 2488 2489 /* While we compute the hash table we also compute a bit array of which 2490 registers are set in which blocks. 2491 ??? This isn't needed during const/copy propagation, but it's cheap to 2492 compute. Later. */ 2493 sbitmap_vector_zero (reg_set_in_block, last_basic_block); 2494 2495 /* re-Cache any INSN_LIST nodes we have allocated. */ 2496 clear_modify_mem_tables (); 2497 /* Some working arrays used to track first and last set in each block. */ 2498 reg_avail_info = gmalloc (max_gcse_regno * sizeof (struct reg_avail_info)); 2499 2500 for (i = 0; i < max_gcse_regno; ++i) 2501 reg_avail_info[i].last_bb = NULL; 2502 2503 FOR_EACH_BB (current_bb) 2504 { 2505 rtx insn; 2506 unsigned int regno; 2507 int in_libcall_block; 2508 2509 /* First pass over the instructions records information used to 2510 determine when registers and memory are first and last set. 2511 ??? hard-reg reg_set_in_block computation 2512 could be moved to compute_sets since they currently don't change. */ 2513 2514 for (insn = BB_HEAD (current_bb); 2515 insn && insn != NEXT_INSN (BB_END (current_bb)); 2516 insn = NEXT_INSN (insn)) 2517 { 2518 if (! INSN_P (insn)) 2519 continue; 2520 2521 if (GET_CODE (insn) == CALL_INSN) 2522 { 2523 bool clobbers_all = false; 2524#ifdef NON_SAVING_SETJMP 2525 if (NON_SAVING_SETJMP 2526 && find_reg_note (insn, REG_SETJMP, NULL_RTX)) 2527 clobbers_all = true; 2528#endif 2529 2530 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++) 2531 if (clobbers_all 2532 || TEST_HARD_REG_BIT (regs_invalidated_by_call, regno)) 2533 record_last_reg_set_info (insn, regno); 2534 2535 mark_call (insn); 2536 } 2537 2538 note_stores (PATTERN (insn), record_last_set_info, insn); 2539 } 2540 2541 /* Insert implicit sets in the hash table. */ 2542 if (table->set_p 2543 && implicit_sets[current_bb->index] != NULL_RTX) 2544 hash_scan_set (implicit_sets[current_bb->index], 2545 BB_HEAD (current_bb), table); 2546 2547 /* The next pass builds the hash table. */ 2548 2549 for (insn = BB_HEAD (current_bb), in_libcall_block = 0; 2550 insn && insn != NEXT_INSN (BB_END (current_bb)); 2551 insn = NEXT_INSN (insn)) 2552 if (INSN_P (insn)) 2553 { 2554 if (find_reg_note (insn, REG_LIBCALL, NULL_RTX)) 2555 in_libcall_block = 1; 2556 else if (table->set_p && find_reg_note (insn, REG_RETVAL, NULL_RTX)) 2557 in_libcall_block = 0; 2558 hash_scan_insn (insn, table, in_libcall_block); 2559 if (!table->set_p && find_reg_note (insn, REG_RETVAL, NULL_RTX)) 2560 in_libcall_block = 0; 2561 } 2562 } 2563 2564 free (reg_avail_info); 2565 reg_avail_info = NULL; 2566} 2567 2568/* Allocate space for the set/expr hash TABLE. 2569 N_INSNS is the number of instructions in the function. 2570 It is used to determine the number of buckets to use. 2571 SET_P determines whether set or expression table will 2572 be created. */ 2573 2574static void 2575alloc_hash_table (int n_insns, struct hash_table *table, int set_p) 2576{ 2577 int n; 2578 2579 table->size = n_insns / 4; 2580 if (table->size < 11) 2581 table->size = 11; 2582 2583 /* Attempt to maintain efficient use of hash table. 2584 Making it an odd number is simplest for now. 2585 ??? Later take some measurements. */ 2586 table->size |= 1; 2587 n = table->size * sizeof (struct expr *); 2588 table->table = gmalloc (n); 2589 table->set_p = set_p; 2590} 2591 2592/* Free things allocated by alloc_hash_table. */ 2593 2594static void 2595free_hash_table (struct hash_table *table) 2596{ 2597 free (table->table); 2598} 2599 2600/* Compute the hash TABLE for doing copy/const propagation or 2601 expression hash table. */ 2602 2603static void 2604compute_hash_table (struct hash_table *table) 2605{ 2606 /* Initialize count of number of entries in hash table. */ 2607 table->n_elems = 0; 2608 memset (table->table, 0, table->size * sizeof (struct expr *)); 2609 2610 compute_hash_table_work (table); 2611} 2612 2613/* Expression tracking support. */ 2614 2615/* Lookup pattern PAT in the expression TABLE. 2616 The result is a pointer to the table entry, or NULL if not found. */ 2617 2618static struct expr * 2619lookup_expr (rtx pat, struct hash_table *table) 2620{ 2621 int do_not_record_p; 2622 unsigned int hash = hash_expr (pat, GET_MODE (pat), &do_not_record_p, 2623 table->size); 2624 struct expr *expr; 2625 2626 if (do_not_record_p) 2627 return NULL; 2628 2629 expr = table->table[hash]; 2630 2631 while (expr && ! expr_equiv_p (expr->expr, pat)) 2632 expr = expr->next_same_hash; 2633 2634 return expr; 2635} 2636 2637/* Lookup REGNO in the set TABLE. The result is a pointer to the 2638 table entry, or NULL if not found. */ 2639 2640static struct expr * 2641lookup_set (unsigned int regno, struct hash_table *table) 2642{ 2643 unsigned int hash = hash_set (regno, table->size); 2644 struct expr *expr; 2645 2646 expr = table->table[hash]; 2647 2648 while (expr && REGNO (SET_DEST (expr->expr)) != regno) 2649 expr = expr->next_same_hash; 2650 2651 return expr; 2652} 2653 2654/* Return the next entry for REGNO in list EXPR. */ 2655 2656static struct expr * 2657next_set (unsigned int regno, struct expr *expr) 2658{ 2659 do 2660 expr = expr->next_same_hash; 2661 while (expr && REGNO (SET_DEST (expr->expr)) != regno); 2662 2663 return expr; 2664} 2665 2666/* Like free_INSN_LIST_list or free_EXPR_LIST_list, except that the node 2667 types may be mixed. */ 2668 2669static void 2670free_insn_expr_list_list (rtx *listp) 2671{ 2672 rtx list, next; 2673 2674 for (list = *listp; list ; list = next) 2675 { 2676 next = XEXP (list, 1); 2677 if (GET_CODE (list) == EXPR_LIST) 2678 free_EXPR_LIST_node (list); 2679 else 2680 free_INSN_LIST_node (list); 2681 } 2682 2683 *listp = NULL; 2684} 2685 2686/* Clear canon_modify_mem_list and modify_mem_list tables. */ 2687static void 2688clear_modify_mem_tables (void) 2689{ 2690 int i; 2691 2692 EXECUTE_IF_SET_IN_BITMAP 2693 (modify_mem_list_set, 0, i, free_INSN_LIST_list (modify_mem_list + i)); 2694 bitmap_clear (modify_mem_list_set); 2695 2696 EXECUTE_IF_SET_IN_BITMAP 2697 (canon_modify_mem_list_set, 0, i, 2698 free_insn_expr_list_list (canon_modify_mem_list + i)); 2699 bitmap_clear (canon_modify_mem_list_set); 2700} 2701 2702/* Release memory used by modify_mem_list_set and canon_modify_mem_list_set. */ 2703 2704static void 2705free_modify_mem_tables (void) 2706{ 2707 clear_modify_mem_tables (); 2708 free (modify_mem_list); 2709 free (canon_modify_mem_list); 2710 modify_mem_list = 0; 2711 canon_modify_mem_list = 0; 2712} 2713 2714/* Reset tables used to keep track of what's still available [since the 2715 start of the block]. */ 2716 2717static void 2718reset_opr_set_tables (void) 2719{ 2720 /* Maintain a bitmap of which regs have been set since beginning of 2721 the block. */ 2722 CLEAR_REG_SET (reg_set_bitmap); 2723 2724 /* Also keep a record of the last instruction to modify memory. 2725 For now this is very trivial, we only record whether any memory 2726 location has been modified. */ 2727 clear_modify_mem_tables (); 2728} 2729 2730/* Return nonzero if the operands of X are not set before INSN in 2731 INSN's basic block. */ 2732 2733static int 2734oprs_not_set_p (rtx x, rtx insn) 2735{ 2736 int i, j; 2737 enum rtx_code code; 2738 const char *fmt; 2739 2740 if (x == 0) 2741 return 1; 2742 2743 code = GET_CODE (x); 2744 switch (code) 2745 { 2746 case PC: 2747 case CC0: 2748 case CONST: 2749 case CONST_INT: 2750 case CONST_DOUBLE: 2751 case CONST_VECTOR: 2752 case SYMBOL_REF: 2753 case LABEL_REF: 2754 case ADDR_VEC: 2755 case ADDR_DIFF_VEC: 2756 return 1; 2757 2758 case MEM: 2759 if (load_killed_in_block_p (BLOCK_FOR_INSN (insn), 2760 INSN_CUID (insn), x, 0)) 2761 return 0; 2762 else 2763 return oprs_not_set_p (XEXP (x, 0), insn); 2764 2765 case REG: 2766 return ! REGNO_REG_SET_P (reg_set_bitmap, REGNO (x)); 2767 2768 default: 2769 break; 2770 } 2771 2772 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--) 2773 { 2774 if (fmt[i] == 'e') 2775 { 2776 /* If we are about to do the last recursive call 2777 needed at this level, change it into iteration. 2778 This function is called enough to be worth it. */ 2779 if (i == 0) 2780 return oprs_not_set_p (XEXP (x, i), insn); 2781 2782 if (! oprs_not_set_p (XEXP (x, i), insn)) 2783 return 0; 2784 } 2785 else if (fmt[i] == 'E') 2786 for (j = 0; j < XVECLEN (x, i); j++) 2787 if (! oprs_not_set_p (XVECEXP (x, i, j), insn)) 2788 return 0; 2789 } 2790 2791 return 1; 2792} 2793 2794/* Mark things set by a CALL. */ 2795 2796static void 2797mark_call (rtx insn) 2798{ 2799 if (! CONST_OR_PURE_CALL_P (insn)) 2800 record_last_mem_set_info (insn); 2801} 2802 2803/* Mark things set by a SET. */ 2804 2805static void 2806mark_set (rtx pat, rtx insn) 2807{ 2808 rtx dest = SET_DEST (pat); 2809 2810 while (GET_CODE (dest) == SUBREG 2811 || GET_CODE (dest) == ZERO_EXTRACT 2812 || GET_CODE (dest) == SIGN_EXTRACT 2813 || GET_CODE (dest) == STRICT_LOW_PART) 2814 dest = XEXP (dest, 0); 2815 2816 if (GET_CODE (dest) == REG) 2817 SET_REGNO_REG_SET (reg_set_bitmap, REGNO (dest)); 2818 else if (GET_CODE (dest) == MEM) 2819 record_last_mem_set_info (insn); 2820 2821 if (GET_CODE (SET_SRC (pat)) == CALL) 2822 mark_call (insn); 2823} 2824 2825/* Record things set by a CLOBBER. */ 2826 2827static void 2828mark_clobber (rtx pat, rtx insn) 2829{ 2830 rtx clob = XEXP (pat, 0); 2831 2832 while (GET_CODE (clob) == SUBREG || GET_CODE (clob) == STRICT_LOW_PART) 2833 clob = XEXP (clob, 0); 2834 2835 if (GET_CODE (clob) == REG) 2836 SET_REGNO_REG_SET (reg_set_bitmap, REGNO (clob)); 2837 else 2838 record_last_mem_set_info (insn); 2839} 2840 2841/* Record things set by INSN. 2842 This data is used by oprs_not_set_p. */ 2843 2844static void 2845mark_oprs_set (rtx insn) 2846{ 2847 rtx pat = PATTERN (insn); 2848 int i; 2849 2850 if (GET_CODE (pat) == SET) 2851 mark_set (pat, insn); 2852 else if (GET_CODE (pat) == PARALLEL) 2853 for (i = 0; i < XVECLEN (pat, 0); i++) 2854 { 2855 rtx x = XVECEXP (pat, 0, i); 2856 2857 if (GET_CODE (x) == SET) 2858 mark_set (x, insn); 2859 else if (GET_CODE (x) == CLOBBER) 2860 mark_clobber (x, insn); 2861 else if (GET_CODE (x) == CALL) 2862 mark_call (insn); 2863 } 2864 2865 else if (GET_CODE (pat) == CLOBBER) 2866 mark_clobber (pat, insn); 2867 else if (GET_CODE (pat) == CALL) 2868 mark_call (insn); 2869} 2870 2871 2872/* Classic GCSE reaching definition support. */ 2873 2874/* Allocate reaching def variables. */ 2875 2876static void 2877alloc_rd_mem (int n_blocks, int n_insns) 2878{ 2879 rd_kill = sbitmap_vector_alloc (n_blocks, n_insns); 2880 sbitmap_vector_zero (rd_kill, n_blocks); 2881 2882 rd_gen = sbitmap_vector_alloc (n_blocks, n_insns); 2883 sbitmap_vector_zero (rd_gen, n_blocks); 2884 2885 reaching_defs = sbitmap_vector_alloc (n_blocks, n_insns); 2886 sbitmap_vector_zero (reaching_defs, n_blocks); 2887 2888 rd_out = sbitmap_vector_alloc (n_blocks, n_insns); 2889 sbitmap_vector_zero (rd_out, n_blocks); 2890} 2891 2892/* Free reaching def variables. */ 2893 2894static void 2895free_rd_mem (void) 2896{ 2897 sbitmap_vector_free (rd_kill); 2898 sbitmap_vector_free (rd_gen); 2899 sbitmap_vector_free (reaching_defs); 2900 sbitmap_vector_free (rd_out); 2901} 2902 2903/* Add INSN to the kills of BB. REGNO, set in BB, is killed by INSN. */ 2904 2905static void 2906handle_rd_kill_set (rtx insn, int regno, basic_block bb) 2907{ 2908 struct reg_set *this_reg; 2909 2910 for (this_reg = reg_set_table[regno]; this_reg; this_reg = this_reg ->next) 2911 if (BLOCK_NUM (this_reg->insn) != BLOCK_NUM (insn)) 2912 SET_BIT (rd_kill[bb->index], INSN_CUID (this_reg->insn)); 2913} 2914 2915/* Compute the set of kill's for reaching definitions. */ 2916 2917static void 2918compute_kill_rd (void) 2919{ 2920 int cuid; 2921 unsigned int regno; 2922 int i; 2923 basic_block bb; 2924 2925 /* For each block 2926 For each set bit in `gen' of the block (i.e each insn which 2927 generates a definition in the block) 2928 Call the reg set by the insn corresponding to that bit regx 2929 Look at the linked list starting at reg_set_table[regx] 2930 For each setting of regx in the linked list, which is not in 2931 this block 2932 Set the bit in `kill' corresponding to that insn. */ 2933 FOR_EACH_BB (bb) 2934 for (cuid = 0; cuid < max_cuid; cuid++) 2935 if (TEST_BIT (rd_gen[bb->index], cuid)) 2936 { 2937 rtx insn = CUID_INSN (cuid); 2938 rtx pat = PATTERN (insn); 2939 2940 if (GET_CODE (insn) == CALL_INSN) 2941 { 2942 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++) 2943 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno)) 2944 handle_rd_kill_set (insn, regno, bb); 2945 } 2946 2947 if (GET_CODE (pat) == PARALLEL) 2948 { 2949 for (i = XVECLEN (pat, 0) - 1; i >= 0; i--) 2950 { 2951 enum rtx_code code = GET_CODE (XVECEXP (pat, 0, i)); 2952 2953 if ((code == SET || code == CLOBBER) 2954 && GET_CODE (XEXP (XVECEXP (pat, 0, i), 0)) == REG) 2955 handle_rd_kill_set (insn, 2956 REGNO (XEXP (XVECEXP (pat, 0, i), 0)), 2957 bb); 2958 } 2959 } 2960 else if (GET_CODE (pat) == SET && GET_CODE (SET_DEST (pat)) == REG) 2961 /* Each setting of this register outside of this block 2962 must be marked in the set of kills in this block. */ 2963 handle_rd_kill_set (insn, REGNO (SET_DEST (pat)), bb); 2964 } 2965} 2966 2967/* Compute the reaching definitions as in 2968 Compilers Principles, Techniques, and Tools. Aho, Sethi, Ullman, 2969 Chapter 10. It is the same algorithm as used for computing available 2970 expressions but applied to the gens and kills of reaching definitions. */ 2971 2972static void 2973compute_rd (void) 2974{ 2975 int changed, passes; 2976 basic_block bb; 2977 2978 FOR_EACH_BB (bb) 2979 sbitmap_copy (rd_out[bb->index] /*dst*/, rd_gen[bb->index] /*src*/); 2980 2981 passes = 0; 2982 changed = 1; 2983 while (changed) 2984 { 2985 changed = 0; 2986 FOR_EACH_BB (bb) 2987 { 2988 sbitmap_union_of_preds (reaching_defs[bb->index], rd_out, bb->index); 2989 changed |= sbitmap_union_of_diff_cg (rd_out[bb->index], rd_gen[bb->index], 2990 reaching_defs[bb->index], rd_kill[bb->index]); 2991 } 2992 passes++; 2993 } 2994 2995 if (gcse_file) 2996 fprintf (gcse_file, "reaching def computation: %d passes\n", passes); 2997} 2998 2999/* Classic GCSE available expression support. */ 3000 3001/* Allocate memory for available expression computation. */ 3002 3003static void 3004alloc_avail_expr_mem (int n_blocks, int n_exprs) 3005{ 3006 ae_kill = sbitmap_vector_alloc (n_blocks, n_exprs); 3007 sbitmap_vector_zero (ae_kill, n_blocks); 3008 3009 ae_gen = sbitmap_vector_alloc (n_blocks, n_exprs); 3010 sbitmap_vector_zero (ae_gen, n_blocks); 3011 3012 ae_in = sbitmap_vector_alloc (n_blocks, n_exprs); 3013 sbitmap_vector_zero (ae_in, n_blocks); 3014 3015 ae_out = sbitmap_vector_alloc (n_blocks, n_exprs); 3016 sbitmap_vector_zero (ae_out, n_blocks); 3017} 3018 3019static void 3020free_avail_expr_mem (void) 3021{ 3022 sbitmap_vector_free (ae_kill); 3023 sbitmap_vector_free (ae_gen); 3024 sbitmap_vector_free (ae_in); 3025 sbitmap_vector_free (ae_out); 3026} 3027 3028/* Compute the set of available expressions generated in each basic block. */ 3029 3030static void 3031compute_ae_gen (struct hash_table *expr_hash_table) 3032{ 3033 unsigned int i; 3034 struct expr *expr; 3035 struct occr *occr; 3036 3037 /* For each recorded occurrence of each expression, set ae_gen[bb][expr]. 3038 This is all we have to do because an expression is not recorded if it 3039 is not available, and the only expressions we want to work with are the 3040 ones that are recorded. */ 3041 for (i = 0; i < expr_hash_table->size; i++) 3042 for (expr = expr_hash_table->table[i]; expr != 0; expr = expr->next_same_hash) 3043 for (occr = expr->avail_occr; occr != 0; occr = occr->next) 3044 SET_BIT (ae_gen[BLOCK_NUM (occr->insn)], expr->bitmap_index); 3045} 3046 3047/* Return nonzero if expression X is killed in BB. */ 3048 3049static int 3050expr_killed_p (rtx x, basic_block bb) 3051{ 3052 int i, j; 3053 enum rtx_code code; 3054 const char *fmt; 3055 3056 if (x == 0) 3057 return 1; 3058 3059 code = GET_CODE (x); 3060 switch (code) 3061 { 3062 case REG: 3063 return TEST_BIT (reg_set_in_block[bb->index], REGNO (x)); 3064 3065 case MEM: 3066 if (load_killed_in_block_p (bb, get_max_uid () + 1, x, 0)) 3067 return 1; 3068 else 3069 return expr_killed_p (XEXP (x, 0), bb); 3070 3071 case PC: 3072 case CC0: /*FIXME*/ 3073 case CONST: 3074 case CONST_INT: 3075 case CONST_DOUBLE: 3076 case CONST_VECTOR: 3077 case SYMBOL_REF: 3078 case LABEL_REF: 3079 case ADDR_VEC: 3080 case ADDR_DIFF_VEC: 3081 return 0; 3082 3083 default: 3084 break; 3085 } 3086 3087 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--) 3088 { 3089 if (fmt[i] == 'e') 3090 { 3091 /* If we are about to do the last recursive call 3092 needed at this level, change it into iteration. 3093 This function is called enough to be worth it. */ 3094 if (i == 0) 3095 return expr_killed_p (XEXP (x, i), bb); 3096 else if (expr_killed_p (XEXP (x, i), bb)) 3097 return 1; 3098 } 3099 else if (fmt[i] == 'E') 3100 for (j = 0; j < XVECLEN (x, i); j++) 3101 if (expr_killed_p (XVECEXP (x, i, j), bb)) 3102 return 1; 3103 } 3104 3105 return 0; 3106} 3107 3108/* Compute the set of available expressions killed in each basic block. */ 3109 3110static void 3111compute_ae_kill (sbitmap *ae_gen, sbitmap *ae_kill, 3112 struct hash_table *expr_hash_table) 3113{ 3114 basic_block bb; 3115 unsigned int i; 3116 struct expr *expr; 3117 3118 FOR_EACH_BB (bb) 3119 for (i = 0; i < expr_hash_table->size; i++) 3120 for (expr = expr_hash_table->table[i]; expr; expr = expr->next_same_hash) 3121 { 3122 /* Skip EXPR if generated in this block. */ 3123 if (TEST_BIT (ae_gen[bb->index], expr->bitmap_index)) 3124 continue; 3125 3126 if (expr_killed_p (expr->expr, bb)) 3127 SET_BIT (ae_kill[bb->index], expr->bitmap_index); 3128 } 3129} 3130 3131/* Actually perform the Classic GCSE optimizations. */ 3132 3133/* Return nonzero if occurrence OCCR of expression EXPR reaches block BB. 3134 3135 CHECK_SELF_LOOP is nonzero if we should consider a block reaching itself 3136 as a positive reach. We want to do this when there are two computations 3137 of the expression in the block. 3138 3139 VISITED is a pointer to a working buffer for tracking which BB's have 3140 been visited. It is NULL for the top-level call. 3141 3142 We treat reaching expressions that go through blocks containing the same 3143 reaching expression as "not reaching". E.g. if EXPR is generated in blocks 3144 2 and 3, INSN is in block 4, and 2->3->4, we treat the expression in block 3145 2 as not reaching. The intent is to improve the probability of finding 3146 only one reaching expression and to reduce register lifetimes by picking 3147 the closest such expression. */ 3148 3149static int 3150expr_reaches_here_p_work (struct occr *occr, struct expr *expr, 3151 basic_block bb, int check_self_loop, char *visited) 3152{ 3153 edge pred; 3154 3155 for (pred = bb->pred; pred != NULL; pred = pred->pred_next) 3156 { 3157 basic_block pred_bb = pred->src; 3158 3159 if (visited[pred_bb->index]) 3160 /* This predecessor has already been visited. Nothing to do. */ 3161 ; 3162 else if (pred_bb == bb) 3163 { 3164 /* BB loops on itself. */ 3165 if (check_self_loop 3166 && TEST_BIT (ae_gen[pred_bb->index], expr->bitmap_index) 3167 && BLOCK_NUM (occr->insn) == pred_bb->index) 3168 return 1; 3169 3170 visited[pred_bb->index] = 1; 3171 } 3172 3173 /* Ignore this predecessor if it kills the expression. */ 3174 else if (TEST_BIT (ae_kill[pred_bb->index], expr->bitmap_index)) 3175 visited[pred_bb->index] = 1; 3176 3177 /* Does this predecessor generate this expression? */ 3178 else if (TEST_BIT (ae_gen[pred_bb->index], expr->bitmap_index)) 3179 { 3180 /* Is this the occurrence we're looking for? 3181 Note that there's only one generating occurrence per block 3182 so we just need to check the block number. */ 3183 if (BLOCK_NUM (occr->insn) == pred_bb->index) 3184 return 1; 3185 3186 visited[pred_bb->index] = 1; 3187 } 3188 3189 /* Neither gen nor kill. */ 3190 else 3191 { 3192 visited[pred_bb->index] = 1; 3193 if (expr_reaches_here_p_work (occr, expr, pred_bb, check_self_loop, 3194 visited)) 3195 3196 return 1; 3197 } 3198 } 3199 3200 /* All paths have been checked. */ 3201 return 0; 3202} 3203 3204/* This wrapper for expr_reaches_here_p_work() is to ensure that any 3205 memory allocated for that function is returned. */ 3206 3207static int 3208expr_reaches_here_p (struct occr *occr, struct expr *expr, basic_block bb, 3209 int check_self_loop) 3210{ 3211 int rval; 3212 char *visited = xcalloc (last_basic_block, 1); 3213 3214 rval = expr_reaches_here_p_work (occr, expr, bb, check_self_loop, visited); 3215 3216 free (visited); 3217 return rval; 3218} 3219 3220/* Return the instruction that computes EXPR that reaches INSN's basic block. 3221 If there is more than one such instruction, return NULL. 3222 3223 Called only by handle_avail_expr. */ 3224 3225static rtx 3226computing_insn (struct expr *expr, rtx insn) 3227{ 3228 basic_block bb = BLOCK_FOR_INSN (insn); 3229 3230 if (expr->avail_occr->next == NULL) 3231 { 3232 if (BLOCK_FOR_INSN (expr->avail_occr->insn) == bb) 3233 /* The available expression is actually itself 3234 (i.e. a loop in the flow graph) so do nothing. */ 3235 return NULL; 3236 3237 /* (FIXME) Case that we found a pattern that was created by 3238 a substitution that took place. */ 3239 return expr->avail_occr->insn; 3240 } 3241 else 3242 { 3243 /* Pattern is computed more than once. 3244 Search backwards from this insn to see how many of these 3245 computations actually reach this insn. */ 3246 struct occr *occr; 3247 rtx insn_computes_expr = NULL; 3248 int can_reach = 0; 3249 3250 for (occr = expr->avail_occr; occr != NULL; occr = occr->next) 3251 { 3252 if (BLOCK_FOR_INSN (occr->insn) == bb) 3253 { 3254 /* The expression is generated in this block. 3255 The only time we care about this is when the expression 3256 is generated later in the block [and thus there's a loop]. 3257 We let the normal cse pass handle the other cases. */ 3258 if (INSN_CUID (insn) < INSN_CUID (occr->insn) 3259 && expr_reaches_here_p (occr, expr, bb, 1)) 3260 { 3261 can_reach++; 3262 if (can_reach > 1) 3263 return NULL; 3264 3265 insn_computes_expr = occr->insn; 3266 } 3267 } 3268 else if (expr_reaches_here_p (occr, expr, bb, 0)) 3269 { 3270 can_reach++; 3271 if (can_reach > 1) 3272 return NULL; 3273 3274 insn_computes_expr = occr->insn; 3275 } 3276 } 3277 3278 if (insn_computes_expr == NULL) 3279 abort (); 3280 3281 return insn_computes_expr; 3282 } 3283} 3284 3285/* Return nonzero if the definition in DEF_INSN can reach INSN. 3286 Only called by can_disregard_other_sets. */ 3287 3288static int 3289def_reaches_here_p (rtx insn, rtx def_insn) 3290{ 3291 rtx reg; 3292 3293 if (TEST_BIT (reaching_defs[BLOCK_NUM (insn)], INSN_CUID (def_insn))) 3294 return 1; 3295 3296 if (BLOCK_NUM (insn) == BLOCK_NUM (def_insn)) 3297 { 3298 if (INSN_CUID (def_insn) < INSN_CUID (insn)) 3299 { 3300 if (GET_CODE (PATTERN (def_insn)) == PARALLEL) 3301 return 1; 3302 else if (GET_CODE (PATTERN (def_insn)) == CLOBBER) 3303 reg = XEXP (PATTERN (def_insn), 0); 3304 else if (GET_CODE (PATTERN (def_insn)) == SET) 3305 reg = SET_DEST (PATTERN (def_insn)); 3306 else 3307 abort (); 3308 3309 return ! reg_set_between_p (reg, NEXT_INSN (def_insn), insn); 3310 } 3311 else 3312 return 0; 3313 } 3314 3315 return 0; 3316} 3317 3318/* Return nonzero if *ADDR_THIS_REG can only have one value at INSN. The 3319 value returned is the number of definitions that reach INSN. Returning a 3320 value of zero means that [maybe] more than one definition reaches INSN and 3321 the caller can't perform whatever optimization it is trying. i.e. it is 3322 always safe to return zero. */ 3323 3324static int 3325can_disregard_other_sets (struct reg_set **addr_this_reg, rtx insn, int for_combine) 3326{ 3327 int number_of_reaching_defs = 0; 3328 struct reg_set *this_reg; 3329 3330 for (this_reg = *addr_this_reg; this_reg != 0; this_reg = this_reg->next) 3331 if (def_reaches_here_p (insn, this_reg->insn)) 3332 { 3333 number_of_reaching_defs++; 3334 /* Ignore parallels for now. */ 3335 if (GET_CODE (PATTERN (this_reg->insn)) == PARALLEL) 3336 return 0; 3337 3338 if (!for_combine 3339 && (GET_CODE (PATTERN (this_reg->insn)) == CLOBBER 3340 || ! rtx_equal_p (SET_SRC (PATTERN (this_reg->insn)), 3341 SET_SRC (PATTERN (insn))))) 3342 /* A setting of the reg to a different value reaches INSN. */ 3343 return 0; 3344 3345 if (number_of_reaching_defs > 1) 3346 { 3347 /* If in this setting the value the register is being set to is 3348 equal to the previous value the register was set to and this 3349 setting reaches the insn we are trying to do the substitution 3350 on then we are ok. */ 3351 if (GET_CODE (PATTERN (this_reg->insn)) == CLOBBER) 3352 return 0; 3353 else if (! rtx_equal_p (SET_SRC (PATTERN (this_reg->insn)), 3354 SET_SRC (PATTERN (insn)))) 3355 return 0; 3356 } 3357 3358 *addr_this_reg = this_reg; 3359 } 3360 3361 return number_of_reaching_defs; 3362} 3363 3364/* Expression computed by insn is available and the substitution is legal, 3365 so try to perform the substitution. 3366 3367 The result is nonzero if any changes were made. */ 3368 3369static int 3370handle_avail_expr (rtx insn, struct expr *expr) 3371{ 3372 rtx pat, insn_computes_expr, expr_set; 3373 rtx to; 3374 struct reg_set *this_reg; 3375 int found_setting, use_src; 3376 int changed = 0; 3377 3378 /* We only handle the case where one computation of the expression 3379 reaches this instruction. */ 3380 insn_computes_expr = computing_insn (expr, insn); 3381 if (insn_computes_expr == NULL) 3382 return 0; 3383 expr_set = single_set (insn_computes_expr); 3384 /* The set might be in a parallel with multiple sets; we could 3385 probably handle that, but there's currently no easy way to find 3386 the relevant sub-expression. */ 3387 if (!expr_set) 3388 return 0; 3389 3390 found_setting = 0; 3391 use_src = 0; 3392 3393 /* At this point we know only one computation of EXPR outside of this 3394 block reaches this insn. Now try to find a register that the 3395 expression is computed into. */ 3396 if (GET_CODE (SET_SRC (expr_set)) == REG) 3397 { 3398 /* This is the case when the available expression that reaches 3399 here has already been handled as an available expression. */ 3400 unsigned int regnum_for_replacing 3401 = REGNO (SET_SRC (expr_set)); 3402 3403 /* If the register was created by GCSE we can't use `reg_set_table', 3404 however we know it's set only once. */ 3405 if (regnum_for_replacing >= max_gcse_regno 3406 /* If the register the expression is computed into is set only once, 3407 or only one set reaches this insn, we can use it. */ 3408 || (((this_reg = reg_set_table[regnum_for_replacing]), 3409 this_reg->next == NULL) 3410 || can_disregard_other_sets (&this_reg, insn, 0))) 3411 { 3412 use_src = 1; 3413 found_setting = 1; 3414 } 3415 } 3416 3417 if (!found_setting) 3418 { 3419 unsigned int regnum_for_replacing 3420 = REGNO (SET_DEST (expr_set)); 3421 3422 /* This shouldn't happen. */ 3423 if (regnum_for_replacing >= max_gcse_regno) 3424 abort (); 3425 3426 this_reg = reg_set_table[regnum_for_replacing]; 3427 3428 /* If the register the expression is computed into is set only once, 3429 or only one set reaches this insn, use it. */ 3430 if (this_reg->next == NULL 3431 || can_disregard_other_sets (&this_reg, insn, 0)) 3432 found_setting = 1; 3433 } 3434 3435 if (found_setting) 3436 { 3437 pat = PATTERN (insn); 3438 if (use_src) 3439 to = SET_SRC (expr_set); 3440 else 3441 to = SET_DEST (expr_set); 3442 changed = validate_change (insn, &SET_SRC (pat), to, 0); 3443 3444 /* We should be able to ignore the return code from validate_change but 3445 to play it safe we check. */ 3446 if (changed) 3447 { 3448 gcse_subst_count++; 3449 if (gcse_file != NULL) 3450 { 3451 fprintf (gcse_file, "GCSE: Replacing the source in insn %d with", 3452 INSN_UID (insn)); 3453 fprintf (gcse_file, " reg %d %s insn %d\n", 3454 REGNO (to), use_src ? "from" : "set in", 3455 INSN_UID (insn_computes_expr)); 3456 } 3457 } 3458 } 3459 3460 /* The register that the expr is computed into is set more than once. */ 3461 else if (1 /*expensive_op(this_pattrn->op) && do_expensive_gcse)*/) 3462 { 3463 /* Insert an insn after insnx that copies the reg set in insnx 3464 into a new pseudo register call this new register REGN. 3465 From insnb until end of basic block or until REGB is set 3466 replace all uses of REGB with REGN. */ 3467 rtx new_insn; 3468 3469 to = gen_reg_rtx (GET_MODE (SET_DEST (expr_set))); 3470 3471 /* Generate the new insn. */ 3472 /* ??? If the change fails, we return 0, even though we created 3473 an insn. I think this is ok. */ 3474 new_insn 3475 = emit_insn_after (gen_rtx_SET (VOIDmode, to, 3476 SET_DEST (expr_set)), 3477 insn_computes_expr); 3478 3479 /* Keep register set table up to date. */ 3480 record_one_set (REGNO (to), new_insn); 3481 3482 gcse_create_count++; 3483 if (gcse_file != NULL) 3484 { 3485 fprintf (gcse_file, "GCSE: Creating insn %d to copy value of reg %d", 3486 INSN_UID (NEXT_INSN (insn_computes_expr)), 3487 REGNO (SET_SRC (PATTERN (NEXT_INSN (insn_computes_expr))))); 3488 fprintf (gcse_file, ", computed in insn %d,\n", 3489 INSN_UID (insn_computes_expr)); 3490 fprintf (gcse_file, " into newly allocated reg %d\n", 3491 REGNO (to)); 3492 } 3493 3494 pat = PATTERN (insn); 3495 3496 /* Do register replacement for INSN. */ 3497 changed = validate_change (insn, &SET_SRC (pat), 3498 SET_DEST (PATTERN 3499 (NEXT_INSN (insn_computes_expr))), 3500 0); 3501 3502 /* We should be able to ignore the return code from validate_change but 3503 to play it safe we check. */ 3504 if (changed) 3505 { 3506 gcse_subst_count++; 3507 if (gcse_file != NULL) 3508 { 3509 fprintf (gcse_file, 3510 "GCSE: Replacing the source in insn %d with reg %d ", 3511 INSN_UID (insn), 3512 REGNO (SET_DEST (PATTERN (NEXT_INSN 3513 (insn_computes_expr))))); 3514 fprintf (gcse_file, "set in insn %d\n", 3515 INSN_UID (insn_computes_expr)); 3516 } 3517 } 3518 } 3519 3520 return changed; 3521} 3522 3523/* Perform classic GCSE. This is called by one_classic_gcse_pass after all 3524 the dataflow analysis has been done. 3525 3526 The result is nonzero if a change was made. */ 3527 3528static int 3529classic_gcse (void) 3530{ 3531 int changed; 3532 rtx insn; 3533 basic_block bb; 3534 3535 /* Note we start at block 1. */ 3536 3537 if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR) 3538 return 0; 3539 3540 changed = 0; 3541 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb, EXIT_BLOCK_PTR, next_bb) 3542 { 3543 /* Reset tables used to keep track of what's still valid [since the 3544 start of the block]. */ 3545 reset_opr_set_tables (); 3546 3547 for (insn = BB_HEAD (bb); 3548 insn != NULL && insn != NEXT_INSN (BB_END (bb)); 3549 insn = NEXT_INSN (insn)) 3550 { 3551 /* Is insn of form (set (pseudo-reg) ...)? */ 3552 if (GET_CODE (insn) == INSN 3553 && GET_CODE (PATTERN (insn)) == SET 3554 && GET_CODE (SET_DEST (PATTERN (insn))) == REG 3555 && REGNO (SET_DEST (PATTERN (insn))) >= FIRST_PSEUDO_REGISTER) 3556 { 3557 rtx pat = PATTERN (insn); 3558 rtx src = SET_SRC (pat); 3559 struct expr *expr; 3560 3561 if (want_to_gcse_p (src) 3562 /* Is the expression recorded? */ 3563 && ((expr = lookup_expr (src, &expr_hash_table)) != NULL) 3564 /* Is the expression available [at the start of the 3565 block]? */ 3566 && TEST_BIT (ae_in[bb->index], expr->bitmap_index) 3567 /* Are the operands unchanged since the start of the 3568 block? */ 3569 && oprs_not_set_p (src, insn)) 3570 changed |= handle_avail_expr (insn, expr); 3571 } 3572 3573 /* Keep track of everything modified by this insn. */ 3574 /* ??? Need to be careful w.r.t. mods done to INSN. */ 3575 if (INSN_P (insn)) 3576 mark_oprs_set (insn); 3577 } 3578 } 3579 3580 return changed; 3581} 3582 3583/* Top level routine to perform one classic GCSE pass. 3584 3585 Return nonzero if a change was made. */ 3586 3587static int 3588one_classic_gcse_pass (int pass) 3589{ 3590 int changed = 0; 3591 3592 gcse_subst_count = 0; 3593 gcse_create_count = 0; 3594 3595 alloc_hash_table (max_cuid, &expr_hash_table, 0); 3596 alloc_rd_mem (last_basic_block, max_cuid); 3597 compute_hash_table (&expr_hash_table); 3598 if (gcse_file) 3599 dump_hash_table (gcse_file, "Expression", &expr_hash_table); 3600 3601 if (expr_hash_table.n_elems > 0) 3602 { 3603 compute_kill_rd (); 3604 compute_rd (); 3605 alloc_avail_expr_mem (last_basic_block, expr_hash_table.n_elems); 3606 compute_ae_gen (&expr_hash_table); 3607 compute_ae_kill (ae_gen, ae_kill, &expr_hash_table); 3608 compute_available (ae_gen, ae_kill, ae_out, ae_in); 3609 changed = classic_gcse (); 3610 free_avail_expr_mem (); 3611 } 3612 3613 free_rd_mem (); 3614 free_hash_table (&expr_hash_table); 3615 3616 if (gcse_file) 3617 { 3618 fprintf (gcse_file, "\n"); 3619 fprintf (gcse_file, "GCSE of %s, pass %d: %d bytes needed, %d substs,", 3620 current_function_name (), pass, bytes_used, gcse_subst_count); 3621 fprintf (gcse_file, "%d insns created\n", gcse_create_count); 3622 } 3623 3624 return changed; 3625} 3626 3627/* Compute copy/constant propagation working variables. */ 3628 3629/* Local properties of assignments. */ 3630static sbitmap *cprop_pavloc; 3631static sbitmap *cprop_absaltered; 3632 3633/* Global properties of assignments (computed from the local properties). */ 3634static sbitmap *cprop_avin; 3635static sbitmap *cprop_avout; 3636 3637/* Allocate vars used for copy/const propagation. N_BLOCKS is the number of 3638 basic blocks. N_SETS is the number of sets. */ 3639 3640static void 3641alloc_cprop_mem (int n_blocks, int n_sets) 3642{ 3643 cprop_pavloc = sbitmap_vector_alloc (n_blocks, n_sets); 3644 cprop_absaltered = sbitmap_vector_alloc (n_blocks, n_sets); 3645 3646 cprop_avin = sbitmap_vector_alloc (n_blocks, n_sets); 3647 cprop_avout = sbitmap_vector_alloc (n_blocks, n_sets); 3648} 3649 3650/* Free vars used by copy/const propagation. */ 3651 3652static void 3653free_cprop_mem (void) 3654{ 3655 sbitmap_vector_free (cprop_pavloc); 3656 sbitmap_vector_free (cprop_absaltered); 3657 sbitmap_vector_free (cprop_avin); 3658 sbitmap_vector_free (cprop_avout); 3659} 3660 3661/* For each block, compute whether X is transparent. X is either an 3662 expression or an assignment [though we don't care which, for this context 3663 an assignment is treated as an expression]. For each block where an 3664 element of X is modified, set (SET_P == 1) or reset (SET_P == 0) the INDX 3665 bit in BMAP. */ 3666 3667static void 3668compute_transp (rtx x, int indx, sbitmap *bmap, int set_p) 3669{ 3670 int i, j; 3671 basic_block bb; 3672 enum rtx_code code; 3673 reg_set *r; 3674 const char *fmt; 3675 3676 /* repeat is used to turn tail-recursion into iteration since GCC 3677 can't do it when there's no return value. */ 3678 repeat: 3679 3680 if (x == 0) 3681 return; 3682 3683 code = GET_CODE (x); 3684 switch (code) 3685 { 3686 case REG: 3687 if (set_p) 3688 { 3689 if (REGNO (x) < FIRST_PSEUDO_REGISTER) 3690 { 3691 FOR_EACH_BB (bb) 3692 if (TEST_BIT (reg_set_in_block[bb->index], REGNO (x))) 3693 SET_BIT (bmap[bb->index], indx); 3694 } 3695 else 3696 { 3697 for (r = reg_set_table[REGNO (x)]; r != NULL; r = r->next) 3698 SET_BIT (bmap[BLOCK_NUM (r->insn)], indx); 3699 } 3700 } 3701 else 3702 { 3703 if (REGNO (x) < FIRST_PSEUDO_REGISTER) 3704 { 3705 FOR_EACH_BB (bb) 3706 if (TEST_BIT (reg_set_in_block[bb->index], REGNO (x))) 3707 RESET_BIT (bmap[bb->index], indx); 3708 } 3709 else 3710 { 3711 for (r = reg_set_table[REGNO (x)]; r != NULL; r = r->next) 3712 RESET_BIT (bmap[BLOCK_NUM (r->insn)], indx); 3713 } 3714 } 3715 3716 return; 3717 3718 case MEM: 3719 FOR_EACH_BB (bb) 3720 { 3721 rtx list_entry = canon_modify_mem_list[bb->index]; 3722 3723 while (list_entry) 3724 { 3725 rtx dest, dest_addr; 3726 3727 if (GET_CODE (XEXP (list_entry, 0)) == CALL_INSN) 3728 { 3729 if (set_p) 3730 SET_BIT (bmap[bb->index], indx); 3731 else 3732 RESET_BIT (bmap[bb->index], indx); 3733 break; 3734 } 3735 /* LIST_ENTRY must be an INSN of some kind that sets memory. 3736 Examine each hunk of memory that is modified. */ 3737 3738 dest = XEXP (list_entry, 0); 3739 list_entry = XEXP (list_entry, 1); 3740 dest_addr = XEXP (list_entry, 0); 3741 3742 if (canon_true_dependence (dest, GET_MODE (dest), dest_addr, 3743 x, rtx_addr_varies_p)) 3744 { 3745 if (set_p) 3746 SET_BIT (bmap[bb->index], indx); 3747 else 3748 RESET_BIT (bmap[bb->index], indx); 3749 break; 3750 } 3751 list_entry = XEXP (list_entry, 1); 3752 } 3753 } 3754 3755 x = XEXP (x, 0); 3756 goto repeat; 3757 3758 case PC: 3759 case CC0: /*FIXME*/ 3760 case CONST: 3761 case CONST_INT: 3762 case CONST_DOUBLE: 3763 case CONST_VECTOR: 3764 case SYMBOL_REF: 3765 case LABEL_REF: 3766 case ADDR_VEC: 3767 case ADDR_DIFF_VEC: 3768 return; 3769 3770 default: 3771 break; 3772 } 3773 3774 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--) 3775 { 3776 if (fmt[i] == 'e') 3777 { 3778 /* If we are about to do the last recursive call 3779 needed at this level, change it into iteration. 3780 This function is called enough to be worth it. */ 3781 if (i == 0) 3782 { 3783 x = XEXP (x, i); 3784 goto repeat; 3785 } 3786 3787 compute_transp (XEXP (x, i), indx, bmap, set_p); 3788 } 3789 else if (fmt[i] == 'E') 3790 for (j = 0; j < XVECLEN (x, i); j++) 3791 compute_transp (XVECEXP (x, i, j), indx, bmap, set_p); 3792 } 3793} 3794 3795/* Top level routine to do the dataflow analysis needed by copy/const 3796 propagation. */ 3797 3798static void 3799compute_cprop_data (void) 3800{ 3801 compute_local_properties (cprop_absaltered, cprop_pavloc, NULL, &set_hash_table); 3802 compute_available (cprop_pavloc, cprop_absaltered, 3803 cprop_avout, cprop_avin); 3804} 3805 3806/* Copy/constant propagation. */ 3807 3808/* Maximum number of register uses in an insn that we handle. */ 3809#define MAX_USES 8 3810 3811/* Table of uses found in an insn. 3812 Allocated statically to avoid alloc/free complexity and overhead. */ 3813static struct reg_use reg_use_table[MAX_USES]; 3814 3815/* Index into `reg_use_table' while building it. */ 3816static int reg_use_count; 3817 3818/* Set up a list of register numbers used in INSN. The found uses are stored 3819 in `reg_use_table'. `reg_use_count' is initialized to zero before entry, 3820 and contains the number of uses in the table upon exit. 3821 3822 ??? If a register appears multiple times we will record it multiple times. 3823 This doesn't hurt anything but it will slow things down. */ 3824 3825static void 3826find_used_regs (rtx *xptr, void *data ATTRIBUTE_UNUSED) 3827{ 3828 int i, j; 3829 enum rtx_code code; 3830 const char *fmt; 3831 rtx x = *xptr; 3832 3833 /* repeat is used to turn tail-recursion into iteration since GCC 3834 can't do it when there's no return value. */ 3835 repeat: 3836 if (x == 0) 3837 return; 3838 3839 code = GET_CODE (x); 3840 if (REG_P (x)) 3841 { 3842 if (reg_use_count == MAX_USES) 3843 return; 3844 3845 reg_use_table[reg_use_count].reg_rtx = x; 3846 reg_use_count++; 3847 } 3848 3849 /* Recursively scan the operands of this expression. */ 3850 3851 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--) 3852 { 3853 if (fmt[i] == 'e') 3854 { 3855 /* If we are about to do the last recursive call 3856 needed at this level, change it into iteration. 3857 This function is called enough to be worth it. */ 3858 if (i == 0) 3859 { 3860 x = XEXP (x, 0); 3861 goto repeat; 3862 } 3863 3864 find_used_regs (&XEXP (x, i), data); 3865 } 3866 else if (fmt[i] == 'E') 3867 for (j = 0; j < XVECLEN (x, i); j++) 3868 find_used_regs (&XVECEXP (x, i, j), data); 3869 } 3870} 3871 3872/* Try to replace all non-SET_DEST occurrences of FROM in INSN with TO. 3873 Returns nonzero is successful. */ 3874 3875static int 3876try_replace_reg (rtx from, rtx to, rtx insn) 3877{ 3878 rtx note = find_reg_equal_equiv_note (insn); 3879 rtx src = 0; 3880 int success = 0; 3881 rtx set = single_set (insn); 3882 3883 validate_replace_src_group (from, to, insn); 3884 if (num_changes_pending () && apply_change_group ()) 3885 success = 1; 3886 3887 /* Try to simplify SET_SRC if we have substituted a constant. */ 3888 if (success && set && CONSTANT_P (to)) 3889 { 3890 src = simplify_rtx (SET_SRC (set)); 3891 3892 if (src) 3893 validate_change (insn, &SET_SRC (set), src, 0); 3894 } 3895 3896 /* If there is already a NOTE, update the expression in it with our 3897 replacement. */ 3898 if (note != 0) 3899 XEXP (note, 0) = simplify_replace_rtx (XEXP (note, 0), from, to); 3900 3901 if (!success && set && reg_mentioned_p (from, SET_SRC (set))) 3902 { 3903 /* If above failed and this is a single set, try to simplify the source of 3904 the set given our substitution. We could perhaps try this for multiple 3905 SETs, but it probably won't buy us anything. */ 3906 src = simplify_replace_rtx (SET_SRC (set), from, to); 3907 3908 if (!rtx_equal_p (src, SET_SRC (set)) 3909 && validate_change (insn, &SET_SRC (set), src, 0)) 3910 success = 1; 3911 3912 /* If we've failed to do replacement, have a single SET, don't already 3913 have a note, and have no special SET, add a REG_EQUAL note to not 3914 lose information. */ 3915 if (!success && note == 0 && set != 0 3916 && GET_CODE (XEXP (set, 0)) != ZERO_EXTRACT 3917 && GET_CODE (XEXP (set, 0)) != SIGN_EXTRACT) 3918 note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src)); 3919 } 3920 3921 /* REG_EQUAL may get simplified into register. 3922 We don't allow that. Remove that note. This code ought 3923 not to happen, because previous code ought to synthesize 3924 reg-reg move, but be on the safe side. */ 3925 if (note && REG_P (XEXP (note, 0))) 3926 remove_note (insn, note); 3927 3928 return success; 3929} 3930 3931/* Find a set of REGNOs that are available on entry to INSN's block. Returns 3932 NULL no such set is found. */ 3933 3934static struct expr * 3935find_avail_set (int regno, rtx insn) 3936{ 3937 /* SET1 contains the last set found that can be returned to the caller for 3938 use in a substitution. */ 3939 struct expr *set1 = 0; 3940 3941 /* Loops are not possible here. To get a loop we would need two sets 3942 available at the start of the block containing INSN. ie we would 3943 need two sets like this available at the start of the block: 3944 3945 (set (reg X) (reg Y)) 3946 (set (reg Y) (reg X)) 3947 3948 This can not happen since the set of (reg Y) would have killed the 3949 set of (reg X) making it unavailable at the start of this block. */ 3950 while (1) 3951 { 3952 rtx src; 3953 struct expr *set = lookup_set (regno, &set_hash_table); 3954 3955 /* Find a set that is available at the start of the block 3956 which contains INSN. */ 3957 while (set) 3958 { 3959 if (TEST_BIT (cprop_avin[BLOCK_NUM (insn)], set->bitmap_index)) 3960 break; 3961 set = next_set (regno, set); 3962 } 3963 3964 /* If no available set was found we've reached the end of the 3965 (possibly empty) copy chain. */ 3966 if (set == 0) 3967 break; 3968 3969 if (GET_CODE (set->expr) != SET) 3970 abort (); 3971 3972 src = SET_SRC (set->expr); 3973 3974 /* We know the set is available. 3975 Now check that SRC is ANTLOC (i.e. none of the source operands 3976 have changed since the start of the block). 3977 3978 If the source operand changed, we may still use it for the next 3979 iteration of this loop, but we may not use it for substitutions. */ 3980 3981 if (gcse_constant_p (src) || oprs_not_set_p (src, insn)) 3982 set1 = set; 3983 3984 /* If the source of the set is anything except a register, then 3985 we have reached the end of the copy chain. */ 3986 if (GET_CODE (src) != REG) 3987 break; 3988 3989 /* Follow the copy chain, ie start another iteration of the loop 3990 and see if we have an available copy into SRC. */ 3991 regno = REGNO (src); 3992 } 3993 3994 /* SET1 holds the last set that was available and anticipatable at 3995 INSN. */ 3996 return set1; 3997} 3998 3999/* Subroutine of cprop_insn that tries to propagate constants into 4000 JUMP_INSNS. JUMP must be a conditional jump. If SETCC is non-NULL 4001 it is the instruction that immediately precedes JUMP, and must be a 4002 single SET of a register. FROM is what we will try to replace, 4003 SRC is the constant we will try to substitute for it. Returns nonzero 4004 if a change was made. */ 4005 4006static int 4007cprop_jump (basic_block bb, rtx setcc, rtx jump, rtx from, rtx src) 4008{ 4009 rtx new, set_src, note_src; 4010 rtx set = pc_set (jump); 4011 rtx note = find_reg_equal_equiv_note (jump); 4012 4013 if (note) 4014 { 4015 note_src = XEXP (note, 0); 4016 if (GET_CODE (note_src) == EXPR_LIST) 4017 note_src = NULL_RTX; 4018 } 4019 else note_src = NULL_RTX; 4020 4021 /* Prefer REG_EQUAL notes except those containing EXPR_LISTs. */ 4022 set_src = note_src ? note_src : SET_SRC (set); 4023 4024 /* First substitute the SETCC condition into the JUMP instruction, 4025 then substitute that given values into this expanded JUMP. */ 4026 if (setcc != NULL_RTX 4027 && !modified_between_p (from, setcc, jump) 4028 && !modified_between_p (src, setcc, jump)) 4029 { 4030 rtx setcc_src; 4031 rtx setcc_set = single_set (setcc); 4032 rtx setcc_note = find_reg_equal_equiv_note (setcc); 4033 setcc_src = (setcc_note && GET_CODE (XEXP (setcc_note, 0)) != EXPR_LIST) 4034 ? XEXP (setcc_note, 0) : SET_SRC (setcc_set); 4035 set_src = simplify_replace_rtx (set_src, SET_DEST (setcc_set), 4036 setcc_src); 4037 } 4038 else 4039 setcc = NULL_RTX; 4040 4041 new = simplify_replace_rtx (set_src, from, src); 4042 4043 /* If no simplification can be made, then try the next register. */ 4044 if (rtx_equal_p (new, SET_SRC (set))) 4045 return 0; 4046 4047 /* If this is now a no-op delete it, otherwise this must be a valid insn. */ 4048 if (new == pc_rtx) 4049 delete_insn (jump); 4050 else 4051 { 4052 /* Ensure the value computed inside the jump insn to be equivalent 4053 to one computed by setcc. */ 4054 if (setcc && modified_in_p (new, setcc)) 4055 return 0; 4056 if (! validate_change (jump, &SET_SRC (set), new, 0)) 4057 { 4058 /* When (some) constants are not valid in a comparison, and there 4059 are two registers to be replaced by constants before the entire 4060 comparison can be folded into a constant, we need to keep 4061 intermediate information in REG_EQUAL notes. For targets with 4062 separate compare insns, such notes are added by try_replace_reg. 4063 When we have a combined compare-and-branch instruction, however, 4064 we need to attach a note to the branch itself to make this 4065 optimization work. */ 4066 4067 if (!rtx_equal_p (new, note_src)) 4068 set_unique_reg_note (jump, REG_EQUAL, copy_rtx (new)); 4069 return 0; 4070 } 4071 4072 /* Remove REG_EQUAL note after simplification. */ 4073 if (note_src) 4074 remove_note (jump, note); 4075 4076 /* If this has turned into an unconditional jump, 4077 then put a barrier after it so that the unreachable 4078 code will be deleted. */ 4079 if (GET_CODE (SET_SRC (set)) == LABEL_REF) 4080 emit_barrier_after (jump); 4081 } 4082 4083#ifdef HAVE_cc0 4084 /* Delete the cc0 setter. */ 4085 if (setcc != NULL && CC0_P (SET_DEST (single_set (setcc)))) 4086 delete_insn (setcc); 4087#endif 4088 4089 run_jump_opt_after_gcse = 1; 4090 4091 const_prop_count++; 4092 if (gcse_file != NULL) 4093 { 4094 fprintf (gcse_file, 4095 "CONST-PROP: Replacing reg %d in jump_insn %d with constant ", 4096 REGNO (from), INSN_UID (jump)); 4097 print_rtl (gcse_file, src); 4098 fprintf (gcse_file, "\n"); 4099 } 4100 purge_dead_edges (bb); 4101 4102 return 1; 4103} 4104 4105static bool 4106constprop_register (rtx insn, rtx from, rtx to, int alter_jumps) 4107{ 4108 rtx sset; 4109 4110 /* Check for reg or cc0 setting instructions followed by 4111 conditional branch instructions first. */ 4112 if (alter_jumps 4113 && (sset = single_set (insn)) != NULL 4114 && NEXT_INSN (insn) 4115 && any_condjump_p (NEXT_INSN (insn)) && onlyjump_p (NEXT_INSN (insn))) 4116 { 4117 rtx dest = SET_DEST (sset); 4118 if ((REG_P (dest) || CC0_P (dest)) 4119 && cprop_jump (BLOCK_FOR_INSN (insn), insn, NEXT_INSN (insn), from, to)) 4120 return 1; 4121 } 4122 4123 /* Handle normal insns next. */ 4124 if (GET_CODE (insn) == INSN 4125 && try_replace_reg (from, to, insn)) 4126 return 1; 4127 4128 /* Try to propagate a CONST_INT into a conditional jump. 4129 We're pretty specific about what we will handle in this 4130 code, we can extend this as necessary over time. 4131 4132 Right now the insn in question must look like 4133 (set (pc) (if_then_else ...)) */ 4134 else if (alter_jumps && any_condjump_p (insn) && onlyjump_p (insn)) 4135 return cprop_jump (BLOCK_FOR_INSN (insn), NULL, insn, from, to); 4136 return 0; 4137} 4138 4139/* Perform constant and copy propagation on INSN. 4140 The result is nonzero if a change was made. */ 4141 4142static int 4143cprop_insn (rtx insn, int alter_jumps) 4144{ 4145 struct reg_use *reg_used; 4146 int changed = 0; 4147 rtx note; 4148 4149 if (!INSN_P (insn)) 4150 return 0; 4151 4152 reg_use_count = 0; 4153 note_uses (&PATTERN (insn), find_used_regs, NULL); 4154 4155 note = find_reg_equal_equiv_note (insn); 4156 4157 /* We may win even when propagating constants into notes. */ 4158 if (note) 4159 find_used_regs (&XEXP (note, 0), NULL); 4160 4161 for (reg_used = ®_use_table[0]; reg_use_count > 0; 4162 reg_used++, reg_use_count--) 4163 { 4164 unsigned int regno = REGNO (reg_used->reg_rtx); 4165 rtx pat, src; 4166 struct expr *set; 4167 4168 /* Ignore registers created by GCSE. 4169 We do this because ... */ 4170 if (regno >= max_gcse_regno) 4171 continue; 4172 4173 /* If the register has already been set in this block, there's 4174 nothing we can do. */ 4175 if (! oprs_not_set_p (reg_used->reg_rtx, insn)) 4176 continue; 4177 4178 /* Find an assignment that sets reg_used and is available 4179 at the start of the block. */ 4180 set = find_avail_set (regno, insn); 4181 if (! set) 4182 continue; 4183 4184 pat = set->expr; 4185 /* ??? We might be able to handle PARALLELs. Later. */ 4186 if (GET_CODE (pat) != SET) 4187 abort (); 4188 4189 src = SET_SRC (pat); 4190 4191 /* Constant propagation. */ 4192 if (gcse_constant_p (src)) 4193 { 4194 if (constprop_register (insn, reg_used->reg_rtx, src, alter_jumps)) 4195 { 4196 changed = 1; 4197 const_prop_count++; 4198 if (gcse_file != NULL) 4199 { 4200 fprintf (gcse_file, "GLOBAL CONST-PROP: Replacing reg %d in ", regno); 4201 fprintf (gcse_file, "insn %d with constant ", INSN_UID (insn)); 4202 print_rtl (gcse_file, src); 4203 fprintf (gcse_file, "\n"); 4204 } 4205 if (INSN_DELETED_P (insn)) 4206 return 1; 4207 } 4208 } 4209 else if (GET_CODE (src) == REG 4210 && REGNO (src) >= FIRST_PSEUDO_REGISTER 4211 && REGNO (src) != regno) 4212 { 4213 if (try_replace_reg (reg_used->reg_rtx, src, insn)) 4214 { 4215 changed = 1; 4216 copy_prop_count++; 4217 if (gcse_file != NULL) 4218 { 4219 fprintf (gcse_file, "GLOBAL COPY-PROP: Replacing reg %d in insn %d", 4220 regno, INSN_UID (insn)); 4221 fprintf (gcse_file, " with reg %d\n", REGNO (src)); 4222 } 4223 4224 /* The original insn setting reg_used may or may not now be 4225 deletable. We leave the deletion to flow. */ 4226 /* FIXME: If it turns out that the insn isn't deletable, 4227 then we may have unnecessarily extended register lifetimes 4228 and made things worse. */ 4229 } 4230 } 4231 } 4232 4233 return changed; 4234} 4235 4236/* Like find_used_regs, but avoid recording uses that appear in 4237 input-output contexts such as zero_extract or pre_dec. This 4238 restricts the cases we consider to those for which local cprop 4239 can legitimately make replacements. */ 4240 4241static void 4242local_cprop_find_used_regs (rtx *xptr, void *data) 4243{ 4244 rtx x = *xptr; 4245 4246 if (x == 0) 4247 return; 4248 4249 switch (GET_CODE (x)) 4250 { 4251 case ZERO_EXTRACT: 4252 case SIGN_EXTRACT: 4253 case STRICT_LOW_PART: 4254 return; 4255 4256 case PRE_DEC: 4257 case PRE_INC: 4258 case POST_DEC: 4259 case POST_INC: 4260 case PRE_MODIFY: 4261 case POST_MODIFY: 4262 /* Can only legitimately appear this early in the context of 4263 stack pushes for function arguments, but handle all of the 4264 codes nonetheless. */ 4265 return; 4266 4267 case SUBREG: 4268 /* Setting a subreg of a register larger than word_mode leaves 4269 the non-written words unchanged. */ 4270 if (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))) > BITS_PER_WORD) 4271 return; 4272 break; 4273 4274 default: 4275 break; 4276 } 4277 4278 find_used_regs (xptr, data); 4279} 4280 4281/* LIBCALL_SP is a zero-terminated array of insns at the end of a libcall; 4282 their REG_EQUAL notes need updating. */ 4283 4284static bool 4285do_local_cprop (rtx x, rtx insn, int alter_jumps, rtx *libcall_sp) 4286{ 4287 rtx newreg = NULL, newcnst = NULL; 4288 4289 /* Rule out USE instructions and ASM statements as we don't want to 4290 change the hard registers mentioned. */ 4291 if (GET_CODE (x) == REG 4292 && (REGNO (x) >= FIRST_PSEUDO_REGISTER 4293 || (GET_CODE (PATTERN (insn)) != USE 4294 && asm_noperands (PATTERN (insn)) < 0))) 4295 { 4296 cselib_val *val = cselib_lookup (x, GET_MODE (x), 0); 4297 struct elt_loc_list *l; 4298 4299 if (!val) 4300 return false; 4301 for (l = val->locs; l; l = l->next) 4302 { 4303 rtx this_rtx = l->loc; 4304 rtx note; 4305 4306 /* Don't CSE non-constant values out of libcall blocks. */ 4307 if (l->in_libcall && ! CONSTANT_P (this_rtx)) 4308 continue; 4309 4310 if (gcse_constant_p (this_rtx)) 4311 newcnst = this_rtx; 4312 if (REG_P (this_rtx) && REGNO (this_rtx) >= FIRST_PSEUDO_REGISTER 4313 /* Don't copy propagate if it has attached REG_EQUIV note. 4314 At this point this only function parameters should have 4315 REG_EQUIV notes and if the argument slot is used somewhere 4316 explicitly, it means address of parameter has been taken, 4317 so we should not extend the lifetime of the pseudo. */ 4318 && (!(note = find_reg_note (l->setting_insn, REG_EQUIV, NULL_RTX)) 4319 || GET_CODE (XEXP (note, 0)) != MEM)) 4320 newreg = this_rtx; 4321 } 4322 if (newcnst && constprop_register (insn, x, newcnst, alter_jumps)) 4323 { 4324 /* If we find a case where we can't fix the retval REG_EQUAL notes 4325 match the new register, we either have to abandon this replacement 4326 or fix delete_trivially_dead_insns to preserve the setting insn, 4327 or make it delete the REG_EUAQL note, and fix up all passes that 4328 require the REG_EQUAL note there. */ 4329 if (!adjust_libcall_notes (x, newcnst, insn, libcall_sp)) 4330 abort (); 4331 if (gcse_file != NULL) 4332 { 4333 fprintf (gcse_file, "LOCAL CONST-PROP: Replacing reg %d in ", 4334 REGNO (x)); 4335 fprintf (gcse_file, "insn %d with constant ", 4336 INSN_UID (insn)); 4337 print_rtl (gcse_file, newcnst); 4338 fprintf (gcse_file, "\n"); 4339 } 4340 const_prop_count++; 4341 return true; 4342 } 4343 else if (newreg && newreg != x && try_replace_reg (x, newreg, insn)) 4344 { 4345 adjust_libcall_notes (x, newreg, insn, libcall_sp); 4346 if (gcse_file != NULL) 4347 { 4348 fprintf (gcse_file, 4349 "LOCAL COPY-PROP: Replacing reg %d in insn %d", 4350 REGNO (x), INSN_UID (insn)); 4351 fprintf (gcse_file, " with reg %d\n", REGNO (newreg)); 4352 } 4353 copy_prop_count++; 4354 return true; 4355 } 4356 } 4357 return false; 4358} 4359 4360/* LIBCALL_SP is a zero-terminated array of insns at the end of a libcall; 4361 their REG_EQUAL notes need updating to reflect that OLDREG has been 4362 replaced with NEWVAL in INSN. Return true if all substitutions could 4363 be made. */ 4364static bool 4365adjust_libcall_notes (rtx oldreg, rtx newval, rtx insn, rtx *libcall_sp) 4366{ 4367 rtx end; 4368 4369 while ((end = *libcall_sp++)) 4370 { 4371 rtx note = find_reg_equal_equiv_note (end); 4372 4373 if (! note) 4374 continue; 4375 4376 if (REG_P (newval)) 4377 { 4378 if (reg_set_between_p (newval, PREV_INSN (insn), end)) 4379 { 4380 do 4381 { 4382 note = find_reg_equal_equiv_note (end); 4383 if (! note) 4384 continue; 4385 if (reg_mentioned_p (newval, XEXP (note, 0))) 4386 return false; 4387 } 4388 while ((end = *libcall_sp++)); 4389 return true; 4390 } 4391 } 4392 XEXP (note, 0) = simplify_replace_rtx (XEXP (note, 0), oldreg, newval); 4393 insn = end; 4394 } 4395 return true; 4396} 4397 4398#define MAX_NESTED_LIBCALLS 9 4399 4400static void 4401local_cprop_pass (int alter_jumps) 4402{ 4403 rtx insn; 4404 struct reg_use *reg_used; 4405 rtx libcall_stack[MAX_NESTED_LIBCALLS + 1], *libcall_sp; 4406 bool changed = false; 4407 4408 cselib_init (); 4409 libcall_sp = &libcall_stack[MAX_NESTED_LIBCALLS]; 4410 *libcall_sp = 0; 4411 for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) 4412 { 4413 if (INSN_P (insn)) 4414 { 4415 rtx note = find_reg_note (insn, REG_LIBCALL, NULL_RTX); 4416 4417 if (note) 4418 { 4419 if (libcall_sp == libcall_stack) 4420 abort (); 4421 *--libcall_sp = XEXP (note, 0); 4422 } 4423 note = find_reg_note (insn, REG_RETVAL, NULL_RTX); 4424 if (note) 4425 libcall_sp++; 4426 note = find_reg_equal_equiv_note (insn); 4427 do 4428 { 4429 reg_use_count = 0; 4430 note_uses (&PATTERN (insn), local_cprop_find_used_regs, NULL); 4431 if (note) 4432 local_cprop_find_used_regs (&XEXP (note, 0), NULL); 4433 4434 for (reg_used = ®_use_table[0]; reg_use_count > 0; 4435 reg_used++, reg_use_count--) 4436 if (do_local_cprop (reg_used->reg_rtx, insn, alter_jumps, 4437 libcall_sp)) 4438 { 4439 changed = true; 4440 break; 4441 } 4442 if (INSN_DELETED_P (insn)) 4443 break; 4444 } 4445 while (reg_use_count); 4446 } 4447 cselib_process_insn (insn); 4448 } 4449 cselib_finish (); 4450 /* Global analysis may get into infinite loops for unreachable blocks. */ 4451 if (changed && alter_jumps) 4452 { 4453 delete_unreachable_blocks (); 4454 free_reg_set_mem (); 4455 alloc_reg_set_mem (max_reg_num ()); 4456 compute_sets (get_insns ()); 4457 } 4458} 4459 4460/* Forward propagate copies. This includes copies and constants. Return 4461 nonzero if a change was made. */ 4462 4463static int 4464cprop (int alter_jumps) 4465{ 4466 int changed; 4467 basic_block bb; 4468 rtx insn; 4469 4470 /* Note we start at block 1. */ 4471 if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR) 4472 { 4473 if (gcse_file != NULL) 4474 fprintf (gcse_file, "\n"); 4475 return 0; 4476 } 4477 4478 changed = 0; 4479 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb, EXIT_BLOCK_PTR, next_bb) 4480 { 4481 /* Reset tables used to keep track of what's still valid [since the 4482 start of the block]. */ 4483 reset_opr_set_tables (); 4484 4485 for (insn = BB_HEAD (bb); 4486 insn != NULL && insn != NEXT_INSN (BB_END (bb)); 4487 insn = NEXT_INSN (insn)) 4488 if (INSN_P (insn)) 4489 { 4490 changed |= cprop_insn (insn, alter_jumps); 4491 4492 /* Keep track of everything modified by this insn. */ 4493 /* ??? Need to be careful w.r.t. mods done to INSN. Don't 4494 call mark_oprs_set if we turned the insn into a NOTE. */ 4495 if (GET_CODE (insn) != NOTE) 4496 mark_oprs_set (insn); 4497 } 4498 } 4499 4500 if (gcse_file != NULL) 4501 fprintf (gcse_file, "\n"); 4502 4503 return changed; 4504} 4505 4506/* Similar to get_condition, only the resulting condition must be 4507 valid at JUMP, instead of at EARLIEST. 4508 4509 This differs from noce_get_condition in ifcvt.c in that we prefer not to 4510 settle for the condition variable in the jump instruction being integral. 4511 We prefer to be able to record the value of a user variable, rather than 4512 the value of a temporary used in a condition. This could be solved by 4513 recording the value of *every* register scaned by canonicalize_condition, 4514 but this would require some code reorganization. */ 4515 4516rtx 4517fis_get_condition (rtx jump) 4518{ 4519 rtx cond, set, tmp, insn, earliest; 4520 bool reverse; 4521 4522 if (! any_condjump_p (jump)) 4523 return NULL_RTX; 4524 4525 set = pc_set (jump); 4526 cond = XEXP (SET_SRC (set), 0); 4527 4528 /* If this branches to JUMP_LABEL when the condition is false, 4529 reverse the condition. */ 4530 reverse = (GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF 4531 && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (jump)); 4532 4533 /* Use canonicalize_condition to do the dirty work of manipulating 4534 MODE_CC values and COMPARE rtx codes. */ 4535 tmp = canonicalize_condition (jump, cond, reverse, &earliest, NULL_RTX, 4536 false); 4537 if (!tmp) 4538 return NULL_RTX; 4539 4540 /* Verify that the given condition is valid at JUMP by virtue of not 4541 having been modified since EARLIEST. */ 4542 for (insn = earliest; insn != jump; insn = NEXT_INSN (insn)) 4543 if (INSN_P (insn) && modified_in_p (tmp, insn)) 4544 break; 4545 if (insn == jump) 4546 return tmp; 4547 4548 /* The condition was modified. See if we can get a partial result 4549 that doesn't follow all the reversals. Perhaps combine can fold 4550 them together later. */ 4551 tmp = XEXP (tmp, 0); 4552 if (!REG_P (tmp) || GET_MODE_CLASS (GET_MODE (tmp)) != MODE_INT) 4553 return NULL_RTX; 4554 tmp = canonicalize_condition (jump, cond, reverse, &earliest, tmp, 4555 false); 4556 if (!tmp) 4557 return NULL_RTX; 4558 4559 /* For sanity's sake, re-validate the new result. */ 4560 for (insn = earliest; insn != jump; insn = NEXT_INSN (insn)) 4561 if (INSN_P (insn) && modified_in_p (tmp, insn)) 4562 return NULL_RTX; 4563 4564 return tmp; 4565} 4566 4567/* Check the comparison COND to see if we can safely form an implicit set from 4568 it. COND is either an EQ or NE comparison. */ 4569 4570static bool 4571implicit_set_cond_p (rtx cond) 4572{ 4573 enum machine_mode mode = GET_MODE (XEXP (cond, 0)); 4574 rtx cst = XEXP (cond, 1); 4575 4576 /* We can't perform this optimization if either operand might be or might 4577 contain a signed zero. */ 4578 if (HONOR_SIGNED_ZEROS (mode)) 4579 { 4580 /* It is sufficient to check if CST is or contains a zero. We must 4581 handle float, complex, and vector. If any subpart is a zero, then 4582 the optimization can't be performed. */ 4583 /* ??? The complex and vector checks are not implemented yet. We just 4584 always return zero for them. */ 4585 if (GET_CODE (cst) == CONST_DOUBLE) 4586 { 4587 REAL_VALUE_TYPE d; 4588 REAL_VALUE_FROM_CONST_DOUBLE (d, cst); 4589 if (REAL_VALUES_EQUAL (d, dconst0)) 4590 return 0; 4591 } 4592 else 4593 return 0; 4594 } 4595 4596 return gcse_constant_p (cst); 4597} 4598 4599/* Find the implicit sets of a function. An "implicit set" is a constraint 4600 on the value of a variable, implied by a conditional jump. For example, 4601 following "if (x == 2)", the then branch may be optimized as though the 4602 conditional performed an "explicit set", in this example, "x = 2". This 4603 function records the set patterns that are implicit at the start of each 4604 basic block. */ 4605 4606static void 4607find_implicit_sets (void) 4608{ 4609 basic_block bb, dest; 4610 unsigned int count; 4611 rtx cond, new; 4612 4613 count = 0; 4614 FOR_EACH_BB (bb) 4615 /* Check for more than one successor. */ 4616 if (bb->succ && bb->succ->succ_next) 4617 { 4618 cond = fis_get_condition (BB_END (bb)); 4619 4620 if (cond 4621 && (GET_CODE (cond) == EQ || GET_CODE (cond) == NE) 4622 && GET_CODE (XEXP (cond, 0)) == REG 4623 && REGNO (XEXP (cond, 0)) >= FIRST_PSEUDO_REGISTER 4624 && implicit_set_cond_p (cond)) 4625 { 4626 dest = GET_CODE (cond) == EQ ? BRANCH_EDGE (bb)->dest 4627 : FALLTHRU_EDGE (bb)->dest; 4628 4629 if (dest && ! dest->pred->pred_next 4630 && dest != EXIT_BLOCK_PTR) 4631 { 4632 new = gen_rtx_SET (VOIDmode, XEXP (cond, 0), 4633 XEXP (cond, 1)); 4634 implicit_sets[dest->index] = new; 4635 if (gcse_file) 4636 { 4637 fprintf(gcse_file, "Implicit set of reg %d in ", 4638 REGNO (XEXP (cond, 0))); 4639 fprintf(gcse_file, "basic block %d\n", dest->index); 4640 } 4641 count++; 4642 } 4643 } 4644 } 4645 4646 if (gcse_file) 4647 fprintf (gcse_file, "Found %d implicit sets\n", count); 4648} 4649 4650/* Perform one copy/constant propagation pass. 4651 PASS is the pass count. If CPROP_JUMPS is true, perform constant 4652 propagation into conditional jumps. If BYPASS_JUMPS is true, 4653 perform conditional jump bypassing optimizations. */ 4654 4655static int 4656one_cprop_pass (int pass, int cprop_jumps, int bypass_jumps) 4657{ 4658 int changed = 0; 4659 4660 const_prop_count = 0; 4661 copy_prop_count = 0; 4662 4663 local_cprop_pass (cprop_jumps); 4664 4665 /* Determine implicit sets. */ 4666 implicit_sets = xcalloc (last_basic_block, sizeof (rtx)); 4667 find_implicit_sets (); 4668 4669 alloc_hash_table (max_cuid, &set_hash_table, 1); 4670 compute_hash_table (&set_hash_table); 4671 4672 /* Free implicit_sets before peak usage. */ 4673 free (implicit_sets); 4674 implicit_sets = NULL; 4675 4676 if (gcse_file) 4677 dump_hash_table (gcse_file, "SET", &set_hash_table); 4678 if (set_hash_table.n_elems > 0) 4679 { 4680 alloc_cprop_mem (last_basic_block, set_hash_table.n_elems); 4681 compute_cprop_data (); 4682 changed = cprop (cprop_jumps); 4683 if (bypass_jumps) 4684 changed |= bypass_conditional_jumps (); 4685 free_cprop_mem (); 4686 } 4687 4688 free_hash_table (&set_hash_table); 4689 4690 if (gcse_file) 4691 { 4692 fprintf (gcse_file, "CPROP of %s, pass %d: %d bytes needed, ", 4693 current_function_name (), pass, bytes_used); 4694 fprintf (gcse_file, "%d const props, %d copy props\n\n", 4695 const_prop_count, copy_prop_count); 4696 } 4697 /* Global analysis may get into infinite loops for unreachable blocks. */ 4698 if (changed && cprop_jumps) 4699 delete_unreachable_blocks (); 4700 4701 return changed; 4702} 4703 4704/* Bypass conditional jumps. */ 4705 4706/* The value of last_basic_block at the beginning of the jump_bypass 4707 pass. The use of redirect_edge_and_branch_force may introduce new 4708 basic blocks, but the data flow analysis is only valid for basic 4709 block indices less than bypass_last_basic_block. */ 4710 4711static int bypass_last_basic_block; 4712 4713/* Find a set of REGNO to a constant that is available at the end of basic 4714 block BB. Returns NULL if no such set is found. Based heavily upon 4715 find_avail_set. */ 4716 4717static struct expr * 4718find_bypass_set (int regno, int bb) 4719{ 4720 struct expr *result = 0; 4721 4722 for (;;) 4723 { 4724 rtx src; 4725 struct expr *set = lookup_set (regno, &set_hash_table); 4726 4727 while (set) 4728 { 4729 if (TEST_BIT (cprop_avout[bb], set->bitmap_index)) 4730 break; 4731 set = next_set (regno, set); 4732 } 4733 4734 if (set == 0) 4735 break; 4736 4737 if (GET_CODE (set->expr) != SET) 4738 abort (); 4739 4740 src = SET_SRC (set->expr); 4741 if (gcse_constant_p (src)) 4742 result = set; 4743 4744 if (GET_CODE (src) != REG) 4745 break; 4746 4747 regno = REGNO (src); 4748 } 4749 return result; 4750} 4751 4752 4753/* Subroutine of bypass_block that checks whether a pseudo is killed by 4754 any of the instructions inserted on an edge. Jump bypassing places 4755 condition code setters on CFG edges using insert_insn_on_edge. This 4756 function is required to check that our data flow analysis is still 4757 valid prior to commit_edge_insertions. */ 4758 4759static bool 4760reg_killed_on_edge (rtx reg, edge e) 4761{ 4762 rtx insn; 4763 4764 for (insn = e->insns; insn; insn = NEXT_INSN (insn)) 4765 if (INSN_P (insn) && reg_set_p (reg, insn)) 4766 return true; 4767 4768 return false; 4769} 4770 4771/* Subroutine of bypass_conditional_jumps that attempts to bypass the given 4772 basic block BB which has more than one predecessor. If not NULL, SETCC 4773 is the first instruction of BB, which is immediately followed by JUMP_INSN 4774 JUMP. Otherwise, SETCC is NULL, and JUMP is the first insn of BB. 4775 Returns nonzero if a change was made. 4776 4777 During the jump bypassing pass, we may place copies of SETCC instructions 4778 on CFG edges. The following routine must be careful to pay attention to 4779 these inserted insns when performing its transformations. */ 4780 4781static int 4782bypass_block (basic_block bb, rtx setcc, rtx jump) 4783{ 4784 rtx insn, note; 4785 edge e, enext, edest; 4786 int i, change; 4787 int may_be_loop_header; 4788 4789 insn = (setcc != NULL) ? setcc : jump; 4790 4791 /* Determine set of register uses in INSN. */ 4792 reg_use_count = 0; 4793 note_uses (&PATTERN (insn), find_used_regs, NULL); 4794 note = find_reg_equal_equiv_note (insn); 4795 if (note) 4796 find_used_regs (&XEXP (note, 0), NULL); 4797 4798 may_be_loop_header = false; 4799 for (e = bb->pred; e; e = e->pred_next) 4800 if (e->flags & EDGE_DFS_BACK) 4801 { 4802 may_be_loop_header = true; 4803 break; 4804 } 4805 4806 change = 0; 4807 for (e = bb->pred; e; e = enext) 4808 { 4809 enext = e->pred_next; 4810 if (e->flags & EDGE_COMPLEX) 4811 continue; 4812 4813 /* We can't redirect edges from new basic blocks. */ 4814 if (e->src->index >= bypass_last_basic_block) 4815 continue; 4816 4817 /* The irreducible loops created by redirecting of edges entering the 4818 loop from outside would decrease effectiveness of some of the following 4819 optimizations, so prevent this. */ 4820 if (may_be_loop_header 4821 && !(e->flags & EDGE_DFS_BACK)) 4822 continue; 4823 4824 for (i = 0; i < reg_use_count; i++) 4825 { 4826 struct reg_use *reg_used = ®_use_table[i]; 4827 unsigned int regno = REGNO (reg_used->reg_rtx); 4828 basic_block dest, old_dest; 4829 struct expr *set; 4830 rtx src, new; 4831 4832 if (regno >= max_gcse_regno) 4833 continue; 4834 4835 set = find_bypass_set (regno, e->src->index); 4836 4837 if (! set) 4838 continue; 4839 4840 /* Check the data flow is valid after edge insertions. */ 4841 if (e->insns && reg_killed_on_edge (reg_used->reg_rtx, e)) 4842 continue; 4843 4844 src = SET_SRC (pc_set (jump)); 4845 4846 if (setcc != NULL) 4847 src = simplify_replace_rtx (src, 4848 SET_DEST (PATTERN (setcc)), 4849 SET_SRC (PATTERN (setcc))); 4850 4851 new = simplify_replace_rtx (src, reg_used->reg_rtx, 4852 SET_SRC (set->expr)); 4853 4854 /* Jump bypassing may have already placed instructions on 4855 edges of the CFG. We can't bypass an outgoing edge that 4856 has instructions associated with it, as these insns won't 4857 get executed if the incoming edge is redirected. */ 4858 4859 if (new == pc_rtx) 4860 { 4861 edest = FALLTHRU_EDGE (bb); 4862 dest = edest->insns ? NULL : edest->dest; 4863 } 4864 else if (GET_CODE (new) == LABEL_REF) 4865 { 4866 dest = BLOCK_FOR_INSN (XEXP (new, 0)); 4867 /* Don't bypass edges containing instructions. */ 4868 for (edest = bb->succ; edest; edest = edest->succ_next) 4869 if (edest->dest == dest && edest->insns) 4870 { 4871 dest = NULL; 4872 break; 4873 } 4874 } 4875 else 4876 dest = NULL; 4877 4878 /* Avoid unification of the edge with other edges from original 4879 branch. We would end up emitting the instruction on "both" 4880 edges. */ 4881 4882 if (dest && setcc && !CC0_P (SET_DEST (PATTERN (setcc)))) 4883 { 4884 edge e2; 4885 for (e2 = e->src->succ; e2; e2 = e2->succ_next) 4886 if (e2->dest == dest) 4887 break; 4888 if (e2) 4889 dest = NULL; 4890 } 4891 4892 old_dest = e->dest; 4893 if (dest != NULL 4894 && dest != old_dest 4895 && dest != EXIT_BLOCK_PTR) 4896 { 4897 redirect_edge_and_branch_force (e, dest); 4898 4899 /* Copy the register setter to the redirected edge. 4900 Don't copy CC0 setters, as CC0 is dead after jump. */ 4901 if (setcc) 4902 { 4903 rtx pat = PATTERN (setcc); 4904 if (!CC0_P (SET_DEST (pat))) 4905 insert_insn_on_edge (copy_insn (pat), e); 4906 } 4907 4908 if (gcse_file != NULL) 4909 { 4910 fprintf (gcse_file, "JUMP-BYPASS: Proved reg %d in jump_insn %d equals constant ", 4911 regno, INSN_UID (jump)); 4912 print_rtl (gcse_file, SET_SRC (set->expr)); 4913 fprintf (gcse_file, "\nBypass edge from %d->%d to %d\n", 4914 e->src->index, old_dest->index, dest->index); 4915 } 4916 change = 1; 4917 break; 4918 } 4919 } 4920 } 4921 return change; 4922} 4923 4924/* Find basic blocks with more than one predecessor that only contain a 4925 single conditional jump. If the result of the comparison is known at 4926 compile-time from any incoming edge, redirect that edge to the 4927 appropriate target. Returns nonzero if a change was made. 4928 4929 This function is now mis-named, because we also handle indirect jumps. */ 4930 4931static int 4932bypass_conditional_jumps (void) 4933{ 4934 basic_block bb; 4935 int changed; 4936 rtx setcc; 4937 rtx insn; 4938 rtx dest; 4939 4940 /* Note we start at block 1. */ 4941 if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR) 4942 return 0; 4943 4944 bypass_last_basic_block = last_basic_block; 4945 mark_dfs_back_edges (); 4946 4947 changed = 0; 4948 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb, 4949 EXIT_BLOCK_PTR, next_bb) 4950 { 4951 /* Check for more than one predecessor. */ 4952 if (bb->pred && bb->pred->pred_next) 4953 { 4954 setcc = NULL_RTX; 4955 for (insn = BB_HEAD (bb); 4956 insn != NULL && insn != NEXT_INSN (BB_END (bb)); 4957 insn = NEXT_INSN (insn)) 4958 if (GET_CODE (insn) == INSN) 4959 { 4960 if (setcc) 4961 break; 4962 if (GET_CODE (PATTERN (insn)) != SET) 4963 break; 4964 4965 dest = SET_DEST (PATTERN (insn)); 4966 if (REG_P (dest) || CC0_P (dest)) 4967 setcc = insn; 4968 else 4969 break; 4970 } 4971 else if (GET_CODE (insn) == JUMP_INSN) 4972 { 4973 if ((any_condjump_p (insn) || computed_jump_p (insn)) 4974 && onlyjump_p (insn)) 4975 changed |= bypass_block (bb, setcc, insn); 4976 break; 4977 } 4978 else if (INSN_P (insn)) 4979 break; 4980 } 4981 } 4982 4983 /* If we bypassed any register setting insns, we inserted a 4984 copy on the redirected edge. These need to be committed. */ 4985 if (changed) 4986 commit_edge_insertions(); 4987 4988 return changed; 4989} 4990 4991/* Compute PRE+LCM working variables. */ 4992 4993/* Local properties of expressions. */ 4994/* Nonzero for expressions that are transparent in the block. */ 4995static sbitmap *transp; 4996 4997/* Nonzero for expressions that are transparent at the end of the block. 4998 This is only zero for expressions killed by abnormal critical edge 4999 created by a calls. */ 5000static sbitmap *transpout; 5001 5002/* Nonzero for expressions that are computed (available) in the block. */ 5003static sbitmap *comp; 5004 5005/* Nonzero for expressions that are locally anticipatable in the block. */ 5006static sbitmap *antloc; 5007 5008/* Nonzero for expressions where this block is an optimal computation 5009 point. */ 5010static sbitmap *pre_optimal; 5011 5012/* Nonzero for expressions which are redundant in a particular block. */ 5013static sbitmap *pre_redundant; 5014 5015/* Nonzero for expressions which should be inserted on a specific edge. */ 5016static sbitmap *pre_insert_map; 5017 5018/* Nonzero for expressions which should be deleted in a specific block. */ 5019static sbitmap *pre_delete_map; 5020 5021/* Contains the edge_list returned by pre_edge_lcm. */ 5022static struct edge_list *edge_list; 5023 5024/* Redundant insns. */ 5025static sbitmap pre_redundant_insns; 5026 5027/* Allocate vars used for PRE analysis. */ 5028 5029static void 5030alloc_pre_mem (int n_blocks, int n_exprs) 5031{ 5032 transp = sbitmap_vector_alloc (n_blocks, n_exprs); 5033 comp = sbitmap_vector_alloc (n_blocks, n_exprs); 5034 antloc = sbitmap_vector_alloc (n_blocks, n_exprs); 5035 5036 pre_optimal = NULL; 5037 pre_redundant = NULL; 5038 pre_insert_map = NULL; 5039 pre_delete_map = NULL; 5040 ae_in = NULL; 5041 ae_out = NULL; 5042 ae_kill = sbitmap_vector_alloc (n_blocks, n_exprs); 5043 5044 /* pre_insert and pre_delete are allocated later. */ 5045} 5046 5047/* Free vars used for PRE analysis. */ 5048 5049static void 5050free_pre_mem (void) 5051{ 5052 sbitmap_vector_free (transp); 5053 sbitmap_vector_free (comp); 5054 5055 /* ANTLOC and AE_KILL are freed just after pre_lcm finishes. */ 5056 5057 if (pre_optimal) 5058 sbitmap_vector_free (pre_optimal); 5059 if (pre_redundant) 5060 sbitmap_vector_free (pre_redundant); 5061 if (pre_insert_map) 5062 sbitmap_vector_free (pre_insert_map); 5063 if (pre_delete_map) 5064 sbitmap_vector_free (pre_delete_map); 5065 if (ae_in) 5066 sbitmap_vector_free (ae_in); 5067 if (ae_out) 5068 sbitmap_vector_free (ae_out); 5069 5070 transp = comp = NULL; 5071 pre_optimal = pre_redundant = pre_insert_map = pre_delete_map = NULL; 5072 ae_in = ae_out = NULL; 5073} 5074 5075/* Top level routine to do the dataflow analysis needed by PRE. */ 5076 5077static void 5078compute_pre_data (void) 5079{ 5080 sbitmap trapping_expr; 5081 basic_block bb; 5082 unsigned int ui; 5083 5084 compute_local_properties (transp, comp, antloc, &expr_hash_table); 5085 sbitmap_vector_zero (ae_kill, last_basic_block); 5086 5087 /* Collect expressions which might trap. */ 5088 trapping_expr = sbitmap_alloc (expr_hash_table.n_elems); 5089 sbitmap_zero (trapping_expr); 5090 for (ui = 0; ui < expr_hash_table.size; ui++) 5091 { 5092 struct expr *e; 5093 for (e = expr_hash_table.table[ui]; e != NULL; e = e->next_same_hash) 5094 if (may_trap_p (e->expr)) 5095 SET_BIT (trapping_expr, e->bitmap_index); 5096 } 5097 5098 /* Compute ae_kill for each basic block using: 5099 5100 ~(TRANSP | COMP) 5101 5102 This is significantly faster than compute_ae_kill. */ 5103 5104 FOR_EACH_BB (bb) 5105 { 5106 edge e; 5107 5108 /* If the current block is the destination of an abnormal edge, we 5109 kill all trapping expressions because we won't be able to properly 5110 place the instruction on the edge. So make them neither 5111 anticipatable nor transparent. This is fairly conservative. */ 5112 for (e = bb->pred; e ; e = e->pred_next) 5113 if (e->flags & EDGE_ABNORMAL) 5114 { 5115 sbitmap_difference (antloc[bb->index], antloc[bb->index], trapping_expr); 5116 sbitmap_difference (transp[bb->index], transp[bb->index], trapping_expr); 5117 break; 5118 } 5119 5120 sbitmap_a_or_b (ae_kill[bb->index], transp[bb->index], comp[bb->index]); 5121 sbitmap_not (ae_kill[bb->index], ae_kill[bb->index]); 5122 } 5123 5124 edge_list = pre_edge_lcm (gcse_file, expr_hash_table.n_elems, transp, comp, antloc, 5125 ae_kill, &pre_insert_map, &pre_delete_map); 5126 sbitmap_vector_free (antloc); 5127 antloc = NULL; 5128 sbitmap_vector_free (ae_kill); 5129 ae_kill = NULL; 5130 sbitmap_free (trapping_expr); 5131} 5132 5133/* PRE utilities */ 5134 5135/* Return nonzero if an occurrence of expression EXPR in OCCR_BB would reach 5136 block BB. 5137 5138 VISITED is a pointer to a working buffer for tracking which BB's have 5139 been visited. It is NULL for the top-level call. 5140 5141 We treat reaching expressions that go through blocks containing the same 5142 reaching expression as "not reaching". E.g. if EXPR is generated in blocks 5143 2 and 3, INSN is in block 4, and 2->3->4, we treat the expression in block 5144 2 as not reaching. The intent is to improve the probability of finding 5145 only one reaching expression and to reduce register lifetimes by picking 5146 the closest such expression. */ 5147 5148static int 5149pre_expr_reaches_here_p_work (basic_block occr_bb, struct expr *expr, basic_block bb, char *visited) 5150{ 5151 edge pred; 5152 5153 for (pred = bb->pred; pred != NULL; pred = pred->pred_next) 5154 { 5155 basic_block pred_bb = pred->src; 5156 5157 if (pred->src == ENTRY_BLOCK_PTR 5158 /* Has predecessor has already been visited? */ 5159 || visited[pred_bb->index]) 5160 ;/* Nothing to do. */ 5161 5162 /* Does this predecessor generate this expression? */ 5163 else if (TEST_BIT (comp[pred_bb->index], expr->bitmap_index)) 5164 { 5165 /* Is this the occurrence we're looking for? 5166 Note that there's only one generating occurrence per block 5167 so we just need to check the block number. */ 5168 if (occr_bb == pred_bb) 5169 return 1; 5170 5171 visited[pred_bb->index] = 1; 5172 } 5173 /* Ignore this predecessor if it kills the expression. */ 5174 else if (! TEST_BIT (transp[pred_bb->index], expr->bitmap_index)) 5175 visited[pred_bb->index] = 1; 5176 5177 /* Neither gen nor kill. */ 5178 else 5179 { 5180 visited[pred_bb->index] = 1; 5181 if (pre_expr_reaches_here_p_work (occr_bb, expr, pred_bb, visited)) 5182 return 1; 5183 } 5184 } 5185 5186 /* All paths have been checked. */ 5187 return 0; 5188} 5189 5190/* The wrapper for pre_expr_reaches_here_work that ensures that any 5191 memory allocated for that function is returned. */ 5192 5193static int 5194pre_expr_reaches_here_p (basic_block occr_bb, struct expr *expr, basic_block bb) 5195{ 5196 int rval; 5197 char *visited = xcalloc (last_basic_block, 1); 5198 5199 rval = pre_expr_reaches_here_p_work (occr_bb, expr, bb, visited); 5200 5201 free (visited); 5202 return rval; 5203} 5204 5205 5206/* Given an expr, generate RTL which we can insert at the end of a BB, 5207 or on an edge. Set the block number of any insns generated to 5208 the value of BB. */ 5209 5210static rtx 5211process_insert_insn (struct expr *expr) 5212{ 5213 rtx reg = expr->reaching_reg; 5214 rtx exp = copy_rtx (expr->expr); 5215 rtx pat; 5216 5217 start_sequence (); 5218 5219 /* If the expression is something that's an operand, like a constant, 5220 just copy it to a register. */ 5221 if (general_operand (exp, GET_MODE (reg))) 5222 emit_move_insn (reg, exp); 5223 5224 /* Otherwise, make a new insn to compute this expression and make sure the 5225 insn will be recognized (this also adds any needed CLOBBERs). Copy the 5226 expression to make sure we don't have any sharing issues. */ 5227 else if (insn_invalid_p (emit_insn (gen_rtx_SET (VOIDmode, reg, exp)))) 5228 abort (); 5229 5230 pat = get_insns (); 5231 end_sequence (); 5232 5233 return pat; 5234} 5235 5236/* Add EXPR to the end of basic block BB. 5237 5238 This is used by both the PRE and code hoisting. 5239 5240 For PRE, we want to verify that the expr is either transparent 5241 or locally anticipatable in the target block. This check makes 5242 no sense for code hoisting. */ 5243 5244static void 5245insert_insn_end_bb (struct expr *expr, basic_block bb, int pre) 5246{ 5247 rtx insn = BB_END (bb); 5248 rtx new_insn; 5249 rtx reg = expr->reaching_reg; 5250 int regno = REGNO (reg); 5251 rtx pat, pat_end; 5252 5253 pat = process_insert_insn (expr); 5254 if (pat == NULL_RTX || ! INSN_P (pat)) 5255 abort (); 5256 5257 pat_end = pat; 5258 while (NEXT_INSN (pat_end) != NULL_RTX) 5259 pat_end = NEXT_INSN (pat_end); 5260 5261 /* If the last insn is a jump, insert EXPR in front [taking care to 5262 handle cc0, etc. properly]. Similarly we need to care trapping 5263 instructions in presence of non-call exceptions. */ 5264 5265 if (GET_CODE (insn) == JUMP_INSN 5266 || (GET_CODE (insn) == INSN 5267 && (bb->succ->succ_next || (bb->succ->flags & EDGE_ABNORMAL)))) 5268 { 5269#ifdef HAVE_cc0 5270 rtx note; 5271#endif 5272 /* It should always be the case that we can put these instructions 5273 anywhere in the basic block with performing PRE optimizations. 5274 Check this. */ 5275 if (GET_CODE (insn) == INSN && pre 5276 && !TEST_BIT (antloc[bb->index], expr->bitmap_index) 5277 && !TEST_BIT (transp[bb->index], expr->bitmap_index)) 5278 abort (); 5279 5280 /* If this is a jump table, then we can't insert stuff here. Since 5281 we know the previous real insn must be the tablejump, we insert 5282 the new instruction just before the tablejump. */ 5283 if (GET_CODE (PATTERN (insn)) == ADDR_VEC 5284 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC) 5285 insn = prev_real_insn (insn); 5286 5287#ifdef HAVE_cc0 5288 /* FIXME: 'twould be nice to call prev_cc0_setter here but it aborts 5289 if cc0 isn't set. */ 5290 note = find_reg_note (insn, REG_CC_SETTER, NULL_RTX); 5291 if (note) 5292 insn = XEXP (note, 0); 5293 else 5294 { 5295 rtx maybe_cc0_setter = prev_nonnote_insn (insn); 5296 if (maybe_cc0_setter 5297 && INSN_P (maybe_cc0_setter) 5298 && sets_cc0_p (PATTERN (maybe_cc0_setter))) 5299 insn = maybe_cc0_setter; 5300 } 5301#endif 5302 /* FIXME: What if something in cc0/jump uses value set in new insn? */ 5303 new_insn = emit_insn_before_noloc (pat, insn); 5304 } 5305 5306 /* Likewise if the last insn is a call, as will happen in the presence 5307 of exception handling. */ 5308 else if (GET_CODE (insn) == CALL_INSN 5309 && (bb->succ->succ_next || (bb->succ->flags & EDGE_ABNORMAL))) 5310 { 5311 /* Keeping in mind SMALL_REGISTER_CLASSES and parameters in registers, 5312 we search backward and place the instructions before the first 5313 parameter is loaded. Do this for everyone for consistency and a 5314 presumption that we'll get better code elsewhere as well. 5315 5316 It should always be the case that we can put these instructions 5317 anywhere in the basic block with performing PRE optimizations. 5318 Check this. */ 5319 5320 if (pre 5321 && !TEST_BIT (antloc[bb->index], expr->bitmap_index) 5322 && !TEST_BIT (transp[bb->index], expr->bitmap_index)) 5323 abort (); 5324 5325 /* Since different machines initialize their parameter registers 5326 in different orders, assume nothing. Collect the set of all 5327 parameter registers. */ 5328 insn = find_first_parameter_load (insn, BB_HEAD (bb)); 5329 5330 /* If we found all the parameter loads, then we want to insert 5331 before the first parameter load. 5332 5333 If we did not find all the parameter loads, then we might have 5334 stopped on the head of the block, which could be a CODE_LABEL. 5335 If we inserted before the CODE_LABEL, then we would be putting 5336 the insn in the wrong basic block. In that case, put the insn 5337 after the CODE_LABEL. Also, respect NOTE_INSN_BASIC_BLOCK. */ 5338 while (GET_CODE (insn) == CODE_LABEL 5339 || NOTE_INSN_BASIC_BLOCK_P (insn)) 5340 insn = NEXT_INSN (insn); 5341 5342 new_insn = emit_insn_before_noloc (pat, insn); 5343 } 5344 else 5345 new_insn = emit_insn_after_noloc (pat, insn); 5346 5347 while (1) 5348 { 5349 if (INSN_P (pat)) 5350 { 5351 add_label_notes (PATTERN (pat), new_insn); 5352 note_stores (PATTERN (pat), record_set_info, pat); 5353 } 5354 if (pat == pat_end) 5355 break; 5356 pat = NEXT_INSN (pat); 5357 } 5358 5359 gcse_create_count++; 5360 5361 if (gcse_file) 5362 { 5363 fprintf (gcse_file, "PRE/HOIST: end of bb %d, insn %d, ", 5364 bb->index, INSN_UID (new_insn)); 5365 fprintf (gcse_file, "copying expression %d to reg %d\n", 5366 expr->bitmap_index, regno); 5367 } 5368} 5369 5370/* Insert partially redundant expressions on edges in the CFG to make 5371 the expressions fully redundant. */ 5372 5373static int 5374pre_edge_insert (struct edge_list *edge_list, struct expr **index_map) 5375{ 5376 int e, i, j, num_edges, set_size, did_insert = 0; 5377 sbitmap *inserted; 5378 5379 /* Where PRE_INSERT_MAP is nonzero, we add the expression on that edge 5380 if it reaches any of the deleted expressions. */ 5381 5382 set_size = pre_insert_map[0]->size; 5383 num_edges = NUM_EDGES (edge_list); 5384 inserted = sbitmap_vector_alloc (num_edges, expr_hash_table.n_elems); 5385 sbitmap_vector_zero (inserted, num_edges); 5386 5387 for (e = 0; e < num_edges; e++) 5388 { 5389 int indx; 5390 basic_block bb = INDEX_EDGE_PRED_BB (edge_list, e); 5391 5392 for (i = indx = 0; i < set_size; i++, indx += SBITMAP_ELT_BITS) 5393 { 5394 SBITMAP_ELT_TYPE insert = pre_insert_map[e]->elms[i]; 5395 5396 for (j = indx; insert && j < (int) expr_hash_table.n_elems; j++, insert >>= 1) 5397 if ((insert & 1) != 0 && index_map[j]->reaching_reg != NULL_RTX) 5398 { 5399 struct expr *expr = index_map[j]; 5400 struct occr *occr; 5401 5402 /* Now look at each deleted occurrence of this expression. */ 5403 for (occr = expr->antic_occr; occr != NULL; occr = occr->next) 5404 { 5405 if (! occr->deleted_p) 5406 continue; 5407 5408 /* Insert this expression on this edge if if it would 5409 reach the deleted occurrence in BB. */ 5410 if (!TEST_BIT (inserted[e], j)) 5411 { 5412 rtx insn; 5413 edge eg = INDEX_EDGE (edge_list, e); 5414 5415 /* We can't insert anything on an abnormal and 5416 critical edge, so we insert the insn at the end of 5417 the previous block. There are several alternatives 5418 detailed in Morgans book P277 (sec 10.5) for 5419 handling this situation. This one is easiest for 5420 now. */ 5421 5422 if ((eg->flags & EDGE_ABNORMAL) == EDGE_ABNORMAL) 5423 insert_insn_end_bb (index_map[j], bb, 0); 5424 else 5425 { 5426 insn = process_insert_insn (index_map[j]); 5427 insert_insn_on_edge (insn, eg); 5428 } 5429 5430 if (gcse_file) 5431 { 5432 fprintf (gcse_file, "PRE/HOIST: edge (%d,%d), ", 5433 bb->index, 5434 INDEX_EDGE_SUCC_BB (edge_list, e)->index); 5435 fprintf (gcse_file, "copy expression %d\n", 5436 expr->bitmap_index); 5437 } 5438 5439 update_ld_motion_stores (expr); 5440 SET_BIT (inserted[e], j); 5441 did_insert = 1; 5442 gcse_create_count++; 5443 } 5444 } 5445 } 5446 } 5447 } 5448 5449 sbitmap_vector_free (inserted); 5450 return did_insert; 5451} 5452 5453/* Copy the result of EXPR->EXPR generated by INSN to EXPR->REACHING_REG. 5454 Given "old_reg <- expr" (INSN), instead of adding after it 5455 reaching_reg <- old_reg 5456 it's better to do the following: 5457 reaching_reg <- expr 5458 old_reg <- reaching_reg 5459 because this way copy propagation can discover additional PRE 5460 opportunities. But if this fails, we try the old way. 5461 When "expr" is a store, i.e. 5462 given "MEM <- old_reg", instead of adding after it 5463 reaching_reg <- old_reg 5464 it's better to add it before as follows: 5465 reaching_reg <- old_reg 5466 MEM <- reaching_reg. */ 5467 5468static void 5469pre_insert_copy_insn (struct expr *expr, rtx insn) 5470{ 5471 rtx reg = expr->reaching_reg; 5472 int regno = REGNO (reg); 5473 int indx = expr->bitmap_index; 5474 rtx pat = PATTERN (insn); 5475 rtx set, new_insn; 5476 rtx old_reg; 5477 int i; 5478 5479 /* This block matches the logic in hash_scan_insn. */ 5480 if (GET_CODE (pat) == SET) 5481 set = pat; 5482 else if (GET_CODE (pat) == PARALLEL) 5483 { 5484 /* Search through the parallel looking for the set whose 5485 source was the expression that we're interested in. */ 5486 set = NULL_RTX; 5487 for (i = 0; i < XVECLEN (pat, 0); i++) 5488 { 5489 rtx x = XVECEXP (pat, 0, i); 5490 if (GET_CODE (x) == SET 5491 && expr_equiv_p (SET_SRC (x), expr->expr)) 5492 { 5493 set = x; 5494 break; 5495 } 5496 } 5497 } 5498 else 5499 abort (); 5500 5501 if (GET_CODE (SET_DEST (set)) == REG) 5502 { 5503 old_reg = SET_DEST (set); 5504 /* Check if we can modify the set destination in the original insn. */ 5505 if (validate_change (insn, &SET_DEST (set), reg, 0)) 5506 { 5507 new_insn = gen_move_insn (old_reg, reg); 5508 new_insn = emit_insn_after (new_insn, insn); 5509 5510 /* Keep register set table up to date. */ 5511 replace_one_set (REGNO (old_reg), insn, new_insn); 5512 record_one_set (regno, insn); 5513 } 5514 else 5515 { 5516 new_insn = gen_move_insn (reg, old_reg); 5517 new_insn = emit_insn_after (new_insn, insn); 5518 5519 /* Keep register set table up to date. */ 5520 record_one_set (regno, new_insn); 5521 } 5522 } 5523 else /* This is possible only in case of a store to memory. */ 5524 { 5525 old_reg = SET_SRC (set); 5526 new_insn = gen_move_insn (reg, old_reg); 5527 5528 /* Check if we can modify the set source in the original insn. */ 5529 if (validate_change (insn, &SET_SRC (set), reg, 0)) 5530 new_insn = emit_insn_before (new_insn, insn); 5531 else 5532 new_insn = emit_insn_after (new_insn, insn); 5533 5534 /* Keep register set table up to date. */ 5535 record_one_set (regno, new_insn); 5536 } 5537 5538 gcse_create_count++; 5539 5540 if (gcse_file) 5541 fprintf (gcse_file, 5542 "PRE: bb %d, insn %d, copy expression %d in insn %d to reg %d\n", 5543 BLOCK_NUM (insn), INSN_UID (new_insn), indx, 5544 INSN_UID (insn), regno); 5545} 5546 5547/* Copy available expressions that reach the redundant expression 5548 to `reaching_reg'. */ 5549 5550static void 5551pre_insert_copies (void) 5552{ 5553 unsigned int i, added_copy; 5554 struct expr *expr; 5555 struct occr *occr; 5556 struct occr *avail; 5557 5558 /* For each available expression in the table, copy the result to 5559 `reaching_reg' if the expression reaches a deleted one. 5560 5561 ??? The current algorithm is rather brute force. 5562 Need to do some profiling. */ 5563 5564 for (i = 0; i < expr_hash_table.size; i++) 5565 for (expr = expr_hash_table.table[i]; expr != NULL; expr = expr->next_same_hash) 5566 { 5567 /* If the basic block isn't reachable, PPOUT will be TRUE. However, 5568 we don't want to insert a copy here because the expression may not 5569 really be redundant. So only insert an insn if the expression was 5570 deleted. This test also avoids further processing if the 5571 expression wasn't deleted anywhere. */ 5572 if (expr->reaching_reg == NULL) 5573 continue; 5574 5575 /* Set when we add a copy for that expression. */ 5576 added_copy = 0; 5577 5578 for (occr = expr->antic_occr; occr != NULL; occr = occr->next) 5579 { 5580 if (! occr->deleted_p) 5581 continue; 5582 5583 for (avail = expr->avail_occr; avail != NULL; avail = avail->next) 5584 { 5585 rtx insn = avail->insn; 5586 5587 /* No need to handle this one if handled already. */ 5588 if (avail->copied_p) 5589 continue; 5590 5591 /* Don't handle this one if it's a redundant one. */ 5592 if (TEST_BIT (pre_redundant_insns, INSN_CUID (insn))) 5593 continue; 5594 5595 /* Or if the expression doesn't reach the deleted one. */ 5596 if (! pre_expr_reaches_here_p (BLOCK_FOR_INSN (avail->insn), 5597 expr, 5598 BLOCK_FOR_INSN (occr->insn))) 5599 continue; 5600 5601 added_copy = 1; 5602 5603 /* Copy the result of avail to reaching_reg. */ 5604 pre_insert_copy_insn (expr, insn); 5605 avail->copied_p = 1; 5606 } 5607 } 5608 5609 if (added_copy) 5610 update_ld_motion_stores (expr); 5611 } 5612} 5613 5614/* Emit move from SRC to DEST noting the equivalence with expression computed 5615 in INSN. */ 5616static rtx 5617gcse_emit_move_after (rtx src, rtx dest, rtx insn) 5618{ 5619 rtx new; 5620 rtx set = single_set (insn), set2; 5621 rtx note; 5622 rtx eqv; 5623 5624 /* This should never fail since we're creating a reg->reg copy 5625 we've verified to be valid. */ 5626 5627 new = emit_insn_after (gen_move_insn (dest, src), insn); 5628 5629 /* Note the equivalence for local CSE pass. */ 5630 set2 = single_set (new); 5631 if (!set2 || !rtx_equal_p (SET_DEST (set2), dest)) 5632 return new; 5633 if ((note = find_reg_equal_equiv_note (insn))) 5634 eqv = XEXP (note, 0); 5635 else 5636 eqv = SET_SRC (set); 5637 5638 set_unique_reg_note (new, REG_EQUAL, copy_insn_1 (eqv)); 5639 5640 return new; 5641} 5642 5643/* Delete redundant computations. 5644 Deletion is done by changing the insn to copy the `reaching_reg' of 5645 the expression into the result of the SET. It is left to later passes 5646 (cprop, cse2, flow, combine, regmove) to propagate the copy or eliminate it. 5647 5648 Returns nonzero if a change is made. */ 5649 5650static int 5651pre_delete (void) 5652{ 5653 unsigned int i; 5654 int changed; 5655 struct expr *expr; 5656 struct occr *occr; 5657 5658 changed = 0; 5659 for (i = 0; i < expr_hash_table.size; i++) 5660 for (expr = expr_hash_table.table[i]; 5661 expr != NULL; 5662 expr = expr->next_same_hash) 5663 { 5664 int indx = expr->bitmap_index; 5665 5666 /* We only need to search antic_occr since we require 5667 ANTLOC != 0. */ 5668 5669 for (occr = expr->antic_occr; occr != NULL; occr = occr->next) 5670 { 5671 rtx insn = occr->insn; 5672 rtx set; 5673 basic_block bb = BLOCK_FOR_INSN (insn); 5674 5675 /* We only delete insns that have a single_set. */ 5676 if (TEST_BIT (pre_delete_map[bb->index], indx) 5677 && (set = single_set (insn)) != 0) 5678 { 5679 /* Create a pseudo-reg to store the result of reaching 5680 expressions into. Get the mode for the new pseudo from 5681 the mode of the original destination pseudo. */ 5682 if (expr->reaching_reg == NULL) 5683 expr->reaching_reg 5684 = gen_reg_rtx (GET_MODE (SET_DEST (set))); 5685 5686 gcse_emit_move_after (expr->reaching_reg, SET_DEST (set), insn); 5687 delete_insn (insn); 5688 occr->deleted_p = 1; 5689 SET_BIT (pre_redundant_insns, INSN_CUID (insn)); 5690 changed = 1; 5691 gcse_subst_count++; 5692 5693 if (gcse_file) 5694 { 5695 fprintf (gcse_file, 5696 "PRE: redundant insn %d (expression %d) in ", 5697 INSN_UID (insn), indx); 5698 fprintf (gcse_file, "bb %d, reaching reg is %d\n", 5699 bb->index, REGNO (expr->reaching_reg)); 5700 } 5701 } 5702 } 5703 } 5704 5705 return changed; 5706} 5707 5708/* Perform GCSE optimizations using PRE. 5709 This is called by one_pre_gcse_pass after all the dataflow analysis 5710 has been done. 5711 5712 This is based on the original Morel-Renvoise paper Fred Chow's thesis, and 5713 lazy code motion from Knoop, Ruthing and Steffen as described in Advanced 5714 Compiler Design and Implementation. 5715 5716 ??? A new pseudo reg is created to hold the reaching expression. The nice 5717 thing about the classical approach is that it would try to use an existing 5718 reg. If the register can't be adequately optimized [i.e. we introduce 5719 reload problems], one could add a pass here to propagate the new register 5720 through the block. 5721 5722 ??? We don't handle single sets in PARALLELs because we're [currently] not 5723 able to copy the rest of the parallel when we insert copies to create full 5724 redundancies from partial redundancies. However, there's no reason why we 5725 can't handle PARALLELs in the cases where there are no partial 5726 redundancies. */ 5727 5728static int 5729pre_gcse (void) 5730{ 5731 unsigned int i; 5732 int did_insert, changed; 5733 struct expr **index_map; 5734 struct expr *expr; 5735 5736 /* Compute a mapping from expression number (`bitmap_index') to 5737 hash table entry. */ 5738 5739 index_map = xcalloc (expr_hash_table.n_elems, sizeof (struct expr *)); 5740 for (i = 0; i < expr_hash_table.size; i++) 5741 for (expr = expr_hash_table.table[i]; expr != NULL; expr = expr->next_same_hash) 5742 index_map[expr->bitmap_index] = expr; 5743 5744 /* Reset bitmap used to track which insns are redundant. */ 5745 pre_redundant_insns = sbitmap_alloc (max_cuid); 5746 sbitmap_zero (pre_redundant_insns); 5747 5748 /* Delete the redundant insns first so that 5749 - we know what register to use for the new insns and for the other 5750 ones with reaching expressions 5751 - we know which insns are redundant when we go to create copies */ 5752 5753 changed = pre_delete (); 5754 5755 did_insert = pre_edge_insert (edge_list, index_map); 5756 5757 /* In other places with reaching expressions, copy the expression to the 5758 specially allocated pseudo-reg that reaches the redundant expr. */ 5759 pre_insert_copies (); 5760 if (did_insert) 5761 { 5762 commit_edge_insertions (); 5763 changed = 1; 5764 } 5765 5766 free (index_map); 5767 sbitmap_free (pre_redundant_insns); 5768 return changed; 5769} 5770 5771/* Top level routine to perform one PRE GCSE pass. 5772 5773 Return nonzero if a change was made. */ 5774 5775static int 5776one_pre_gcse_pass (int pass) 5777{ 5778 int changed = 0; 5779 5780 gcse_subst_count = 0; 5781 gcse_create_count = 0; 5782 5783 alloc_hash_table (max_cuid, &expr_hash_table, 0); 5784 add_noreturn_fake_exit_edges (); 5785 if (flag_gcse_lm) 5786 compute_ld_motion_mems (); 5787 5788 compute_hash_table (&expr_hash_table); 5789 trim_ld_motion_mems (); 5790 if (gcse_file) 5791 dump_hash_table (gcse_file, "Expression", &expr_hash_table); 5792 5793 if (expr_hash_table.n_elems > 0) 5794 { 5795 alloc_pre_mem (last_basic_block, expr_hash_table.n_elems); 5796 compute_pre_data (); 5797 changed |= pre_gcse (); 5798 free_edge_list (edge_list); 5799 free_pre_mem (); 5800 } 5801 5802 free_ldst_mems (); 5803 remove_fake_edges (); 5804 free_hash_table (&expr_hash_table); 5805 5806 if (gcse_file) 5807 { 5808 fprintf (gcse_file, "\nPRE GCSE of %s, pass %d: %d bytes needed, ", 5809 current_function_name (), pass, bytes_used); 5810 fprintf (gcse_file, "%d substs, %d insns created\n", 5811 gcse_subst_count, gcse_create_count); 5812 } 5813 5814 return changed; 5815} 5816 5817/* If X contains any LABEL_REF's, add REG_LABEL notes for them to INSN. 5818 If notes are added to an insn which references a CODE_LABEL, the 5819 LABEL_NUSES count is incremented. We have to add REG_LABEL notes, 5820 because the following loop optimization pass requires them. */ 5821 5822/* ??? This is very similar to the loop.c add_label_notes function. We 5823 could probably share code here. */ 5824 5825/* ??? If there was a jump optimization pass after gcse and before loop, 5826 then we would not need to do this here, because jump would add the 5827 necessary REG_LABEL notes. */ 5828 5829static void 5830add_label_notes (rtx x, rtx insn) 5831{ 5832 enum rtx_code code = GET_CODE (x); 5833 int i, j; 5834 const char *fmt; 5835 5836 if (code == LABEL_REF && !LABEL_REF_NONLOCAL_P (x)) 5837 { 5838 /* This code used to ignore labels that referred to dispatch tables to 5839 avoid flow generating (slightly) worse code. 5840 5841 We no longer ignore such label references (see LABEL_REF handling in 5842 mark_jump_label for additional information). */ 5843 5844 REG_NOTES (insn) = gen_rtx_INSN_LIST (REG_LABEL, XEXP (x, 0), 5845 REG_NOTES (insn)); 5846 if (LABEL_P (XEXP (x, 0))) 5847 LABEL_NUSES (XEXP (x, 0))++; 5848 return; 5849 } 5850 5851 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--) 5852 { 5853 if (fmt[i] == 'e') 5854 add_label_notes (XEXP (x, i), insn); 5855 else if (fmt[i] == 'E') 5856 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 5857 add_label_notes (XVECEXP (x, i, j), insn); 5858 } 5859} 5860 5861/* Compute transparent outgoing information for each block. 5862 5863 An expression is transparent to an edge unless it is killed by 5864 the edge itself. This can only happen with abnormal control flow, 5865 when the edge is traversed through a call. This happens with 5866 non-local labels and exceptions. 5867 5868 This would not be necessary if we split the edge. While this is 5869 normally impossible for abnormal critical edges, with some effort 5870 it should be possible with exception handling, since we still have 5871 control over which handler should be invoked. But due to increased 5872 EH table sizes, this may not be worthwhile. */ 5873 5874static void 5875compute_transpout (void) 5876{ 5877 basic_block bb; 5878 unsigned int i; 5879 struct expr *expr; 5880 5881 sbitmap_vector_ones (transpout, last_basic_block); 5882 5883 FOR_EACH_BB (bb) 5884 { 5885 /* Note that flow inserted a nop a the end of basic blocks that 5886 end in call instructions for reasons other than abnormal 5887 control flow. */ 5888 if (GET_CODE (BB_END (bb)) != CALL_INSN) 5889 continue; 5890 5891 for (i = 0; i < expr_hash_table.size; i++) 5892 for (expr = expr_hash_table.table[i]; expr ; expr = expr->next_same_hash) 5893 if (GET_CODE (expr->expr) == MEM) 5894 { 5895 if (GET_CODE (XEXP (expr->expr, 0)) == SYMBOL_REF 5896 && CONSTANT_POOL_ADDRESS_P (XEXP (expr->expr, 0))) 5897 continue; 5898 5899 /* ??? Optimally, we would use interprocedural alias 5900 analysis to determine if this mem is actually killed 5901 by this call. */ 5902 RESET_BIT (transpout[bb->index], expr->bitmap_index); 5903 } 5904 } 5905} 5906 5907/* Removal of useless null pointer checks */ 5908 5909/* Called via note_stores. X is set by SETTER. If X is a register we must 5910 invalidate nonnull_local and set nonnull_killed. DATA is really a 5911 `null_pointer_info *'. 5912 5913 We ignore hard registers. */ 5914 5915static void 5916invalidate_nonnull_info (rtx x, rtx setter ATTRIBUTE_UNUSED, void *data) 5917{ 5918 unsigned int regno; 5919 struct null_pointer_info *npi = (struct null_pointer_info *) data; 5920 5921 while (GET_CODE (x) == SUBREG) 5922 x = SUBREG_REG (x); 5923 5924 /* Ignore anything that is not a register or is a hard register. */ 5925 if (GET_CODE (x) != REG 5926 || REGNO (x) < npi->min_reg 5927 || REGNO (x) >= npi->max_reg) 5928 return; 5929 5930 regno = REGNO (x) - npi->min_reg; 5931 5932 RESET_BIT (npi->nonnull_local[npi->current_block->index], regno); 5933 SET_BIT (npi->nonnull_killed[npi->current_block->index], regno); 5934} 5935 5936/* Do null-pointer check elimination for the registers indicated in 5937 NPI. NONNULL_AVIN and NONNULL_AVOUT are pre-allocated sbitmaps; 5938 they are not our responsibility to free. */ 5939 5940static int 5941delete_null_pointer_checks_1 (unsigned int *block_reg, sbitmap *nonnull_avin, 5942 sbitmap *nonnull_avout, 5943 struct null_pointer_info *npi) 5944{ 5945 basic_block bb, current_block; 5946 sbitmap *nonnull_local = npi->nonnull_local; 5947 sbitmap *nonnull_killed = npi->nonnull_killed; 5948 int something_changed = 0; 5949 5950 /* Compute local properties, nonnull and killed. A register will have 5951 the nonnull property if at the end of the current block its value is 5952 known to be nonnull. The killed property indicates that somewhere in 5953 the block any information we had about the register is killed. 5954 5955 Note that a register can have both properties in a single block. That 5956 indicates that it's killed, then later in the block a new value is 5957 computed. */ 5958 sbitmap_vector_zero (nonnull_local, last_basic_block); 5959 sbitmap_vector_zero (nonnull_killed, last_basic_block); 5960 5961 FOR_EACH_BB (current_block) 5962 { 5963 rtx insn, stop_insn; 5964 5965 /* Set the current block for invalidate_nonnull_info. */ 5966 npi->current_block = current_block; 5967 5968 /* Scan each insn in the basic block looking for memory references and 5969 register sets. */ 5970 stop_insn = NEXT_INSN (BB_END (current_block)); 5971 for (insn = BB_HEAD (current_block); 5972 insn != stop_insn; 5973 insn = NEXT_INSN (insn)) 5974 { 5975 rtx set; 5976 rtx reg; 5977 5978 /* Ignore anything that is not a normal insn. */ 5979 if (! INSN_P (insn)) 5980 continue; 5981 5982 /* Basically ignore anything that is not a simple SET. We do have 5983 to make sure to invalidate nonnull_local and set nonnull_killed 5984 for such insns though. */ 5985 set = single_set (insn); 5986 if (!set) 5987 { 5988 note_stores (PATTERN (insn), invalidate_nonnull_info, npi); 5989 continue; 5990 } 5991 5992 /* See if we've got a usable memory load. We handle it first 5993 in case it uses its address register as a dest (which kills 5994 the nonnull property). */ 5995 if (GET_CODE (SET_SRC (set)) == MEM 5996 && GET_CODE ((reg = XEXP (SET_SRC (set), 0))) == REG 5997 && REGNO (reg) >= npi->min_reg 5998 && REGNO (reg) < npi->max_reg) 5999 SET_BIT (nonnull_local[current_block->index], 6000 REGNO (reg) - npi->min_reg); 6001 6002 /* Now invalidate stuff clobbered by this insn. */ 6003 note_stores (PATTERN (insn), invalidate_nonnull_info, npi); 6004 6005 /* And handle stores, we do these last since any sets in INSN can 6006 not kill the nonnull property if it is derived from a MEM 6007 appearing in a SET_DEST. */ 6008 if (GET_CODE (SET_DEST (set)) == MEM 6009 && GET_CODE ((reg = XEXP (SET_DEST (set), 0))) == REG 6010 && REGNO (reg) >= npi->min_reg 6011 && REGNO (reg) < npi->max_reg) 6012 SET_BIT (nonnull_local[current_block->index], 6013 REGNO (reg) - npi->min_reg); 6014 } 6015 } 6016 6017 /* Now compute global properties based on the local properties. This 6018 is a classic global availability algorithm. */ 6019 compute_available (nonnull_local, nonnull_killed, 6020 nonnull_avout, nonnull_avin); 6021 6022 /* Now look at each bb and see if it ends with a compare of a value 6023 against zero. */ 6024 FOR_EACH_BB (bb) 6025 { 6026 rtx last_insn = BB_END (bb); 6027 rtx condition, earliest; 6028 int compare_and_branch; 6029 6030 /* Since MIN_REG is always at least FIRST_PSEUDO_REGISTER, and 6031 since BLOCK_REG[BB] is zero if this block did not end with a 6032 comparison against zero, this condition works. */ 6033 if (block_reg[bb->index] < npi->min_reg 6034 || block_reg[bb->index] >= npi->max_reg) 6035 continue; 6036 6037 /* LAST_INSN is a conditional jump. Get its condition. */ 6038 condition = get_condition (last_insn, &earliest, false); 6039 6040 /* If we can't determine the condition then skip. */ 6041 if (! condition) 6042 continue; 6043 6044 /* Is the register known to have a nonzero value? */ 6045 if (!TEST_BIT (nonnull_avout[bb->index], block_reg[bb->index] - npi->min_reg)) 6046 continue; 6047 6048 /* Try to compute whether the compare/branch at the loop end is one or 6049 two instructions. */ 6050 if (earliest == last_insn) 6051 compare_and_branch = 1; 6052 else if (earliest == prev_nonnote_insn (last_insn)) 6053 compare_and_branch = 2; 6054 else 6055 continue; 6056 6057 /* We know the register in this comparison is nonnull at exit from 6058 this block. We can optimize this comparison. */ 6059 if (GET_CODE (condition) == NE) 6060 { 6061 rtx new_jump; 6062 6063 new_jump = emit_jump_insn_after (gen_jump (JUMP_LABEL (last_insn)), 6064 last_insn); 6065 JUMP_LABEL (new_jump) = JUMP_LABEL (last_insn); 6066 LABEL_NUSES (JUMP_LABEL (new_jump))++; 6067 emit_barrier_after (new_jump); 6068 } 6069 6070 something_changed = 1; 6071 delete_insn (last_insn); 6072#ifdef HAVE_cc0 6073 if (compare_and_branch == 2) 6074 delete_insn (earliest); 6075#endif 6076 purge_dead_edges (bb); 6077 6078 /* Don't check this block again. (Note that BB_END is 6079 invalid here; we deleted the last instruction in the 6080 block.) */ 6081 block_reg[bb->index] = 0; 6082 } 6083 6084 return something_changed; 6085} 6086 6087/* Find EQ/NE comparisons against zero which can be (indirectly) evaluated 6088 at compile time. 6089 6090 This is conceptually similar to global constant/copy propagation and 6091 classic global CSE (it even uses the same dataflow equations as cprop). 6092 6093 If a register is used as memory address with the form (mem (reg)), then we 6094 know that REG can not be zero at that point in the program. Any instruction 6095 which sets REG "kills" this property. 6096 6097 So, if every path leading to a conditional branch has an available memory 6098 reference of that form, then we know the register can not have the value 6099 zero at the conditional branch. 6100 6101 So we merely need to compute the local properties and propagate that data 6102 around the cfg, then optimize where possible. 6103 6104 We run this pass two times. Once before CSE, then again after CSE. This 6105 has proven to be the most profitable approach. It is rare for new 6106 optimization opportunities of this nature to appear after the first CSE 6107 pass. 6108 6109 This could probably be integrated with global cprop with a little work. */ 6110 6111int 6112delete_null_pointer_checks (rtx f ATTRIBUTE_UNUSED) 6113{ 6114 sbitmap *nonnull_avin, *nonnull_avout; 6115 unsigned int *block_reg; 6116 basic_block bb; 6117 int reg; 6118 int regs_per_pass; 6119 int max_reg = max_reg_num (); 6120 struct null_pointer_info npi; 6121 int something_changed = 0; 6122 6123 /* If we have only a single block, or it is too expensive, give up. */ 6124 if (n_basic_blocks <= 1 6125 || is_too_expensive (_ ("NULL pointer checks disabled"))) 6126 return 0; 6127 6128 /* We need four bitmaps, each with a bit for each register in each 6129 basic block. */ 6130 regs_per_pass = get_bitmap_width (4, last_basic_block, max_reg); 6131 6132 /* Allocate bitmaps to hold local and global properties. */ 6133 npi.nonnull_local = sbitmap_vector_alloc (last_basic_block, regs_per_pass); 6134 npi.nonnull_killed = sbitmap_vector_alloc (last_basic_block, regs_per_pass); 6135 nonnull_avin = sbitmap_vector_alloc (last_basic_block, regs_per_pass); 6136 nonnull_avout = sbitmap_vector_alloc (last_basic_block, regs_per_pass); 6137 6138 /* Go through the basic blocks, seeing whether or not each block 6139 ends with a conditional branch whose condition is a comparison 6140 against zero. Record the register compared in BLOCK_REG. */ 6141 block_reg = xcalloc (last_basic_block, sizeof (int)); 6142 FOR_EACH_BB (bb) 6143 { 6144 rtx last_insn = BB_END (bb); 6145 rtx condition, earliest, reg; 6146 6147 /* We only want conditional branches. */ 6148 if (GET_CODE (last_insn) != JUMP_INSN 6149 || !any_condjump_p (last_insn) 6150 || !onlyjump_p (last_insn)) 6151 continue; 6152 6153 /* LAST_INSN is a conditional jump. Get its condition. */ 6154 condition = get_condition (last_insn, &earliest, false); 6155 6156 /* If we were unable to get the condition, or it is not an equality 6157 comparison against zero then there's nothing we can do. */ 6158 if (!condition 6159 || (GET_CODE (condition) != NE && GET_CODE (condition) != EQ) 6160 || GET_CODE (XEXP (condition, 1)) != CONST_INT 6161 || (XEXP (condition, 1) 6162 != CONST0_RTX (GET_MODE (XEXP (condition, 0))))) 6163 continue; 6164 6165 /* We must be checking a register against zero. */ 6166 reg = XEXP (condition, 0); 6167 if (GET_CODE (reg) != REG) 6168 continue; 6169 6170 block_reg[bb->index] = REGNO (reg); 6171 } 6172 6173 /* Go through the algorithm for each block of registers. */ 6174 for (reg = FIRST_PSEUDO_REGISTER; reg < max_reg; reg += regs_per_pass) 6175 { 6176 npi.min_reg = reg; 6177 npi.max_reg = MIN (reg + regs_per_pass, max_reg); 6178 something_changed |= delete_null_pointer_checks_1 (block_reg, 6179 nonnull_avin, 6180 nonnull_avout, 6181 &npi); 6182 } 6183 6184 /* Free the table of registers compared at the end of every block. */ 6185 free (block_reg); 6186 6187 /* Free bitmaps. */ 6188 sbitmap_vector_free (npi.nonnull_local); 6189 sbitmap_vector_free (npi.nonnull_killed); 6190 sbitmap_vector_free (nonnull_avin); 6191 sbitmap_vector_free (nonnull_avout); 6192 6193 return something_changed; 6194} 6195 6196/* Code Hoisting variables and subroutines. */ 6197 6198/* Very busy expressions. */ 6199static sbitmap *hoist_vbein; 6200static sbitmap *hoist_vbeout; 6201 6202/* Hoistable expressions. */ 6203static sbitmap *hoist_exprs; 6204 6205/* ??? We could compute post dominators and run this algorithm in 6206 reverse to perform tail merging, doing so would probably be 6207 more effective than the tail merging code in jump.c. 6208 6209 It's unclear if tail merging could be run in parallel with 6210 code hoisting. It would be nice. */ 6211 6212/* Allocate vars used for code hoisting analysis. */ 6213 6214static void 6215alloc_code_hoist_mem (int n_blocks, int n_exprs) 6216{ 6217 antloc = sbitmap_vector_alloc (n_blocks, n_exprs); 6218 transp = sbitmap_vector_alloc (n_blocks, n_exprs); 6219 comp = sbitmap_vector_alloc (n_blocks, n_exprs); 6220 6221 hoist_vbein = sbitmap_vector_alloc (n_blocks, n_exprs); 6222 hoist_vbeout = sbitmap_vector_alloc (n_blocks, n_exprs); 6223 hoist_exprs = sbitmap_vector_alloc (n_blocks, n_exprs); 6224 transpout = sbitmap_vector_alloc (n_blocks, n_exprs); 6225} 6226 6227/* Free vars used for code hoisting analysis. */ 6228 6229static void 6230free_code_hoist_mem (void) 6231{ 6232 sbitmap_vector_free (antloc); 6233 sbitmap_vector_free (transp); 6234 sbitmap_vector_free (comp); 6235 6236 sbitmap_vector_free (hoist_vbein); 6237 sbitmap_vector_free (hoist_vbeout); 6238 sbitmap_vector_free (hoist_exprs); 6239 sbitmap_vector_free (transpout); 6240 6241 free_dominance_info (CDI_DOMINATORS); 6242} 6243 6244/* Compute the very busy expressions at entry/exit from each block. 6245 6246 An expression is very busy if all paths from a given point 6247 compute the expression. */ 6248 6249static void 6250compute_code_hoist_vbeinout (void) 6251{ 6252 int changed, passes; 6253 basic_block bb; 6254 6255 sbitmap_vector_zero (hoist_vbeout, last_basic_block); 6256 sbitmap_vector_zero (hoist_vbein, last_basic_block); 6257 6258 passes = 0; 6259 changed = 1; 6260 6261 while (changed) 6262 { 6263 changed = 0; 6264 6265 /* We scan the blocks in the reverse order to speed up 6266 the convergence. */ 6267 FOR_EACH_BB_REVERSE (bb) 6268 { 6269 changed |= sbitmap_a_or_b_and_c_cg (hoist_vbein[bb->index], antloc[bb->index], 6270 hoist_vbeout[bb->index], transp[bb->index]); 6271 if (bb->next_bb != EXIT_BLOCK_PTR) 6272 sbitmap_intersection_of_succs (hoist_vbeout[bb->index], hoist_vbein, bb->index); 6273 } 6274 6275 passes++; 6276 } 6277 6278 if (gcse_file) 6279 fprintf (gcse_file, "hoisting vbeinout computation: %d passes\n", passes); 6280} 6281 6282/* Top level routine to do the dataflow analysis needed by code hoisting. */ 6283 6284static void 6285compute_code_hoist_data (void) 6286{ 6287 compute_local_properties (transp, comp, antloc, &expr_hash_table); 6288 compute_transpout (); 6289 compute_code_hoist_vbeinout (); 6290 calculate_dominance_info (CDI_DOMINATORS); 6291 if (gcse_file) 6292 fprintf (gcse_file, "\n"); 6293} 6294 6295/* Determine if the expression identified by EXPR_INDEX would 6296 reach BB unimpared if it was placed at the end of EXPR_BB. 6297 6298 It's unclear exactly what Muchnick meant by "unimpared". It seems 6299 to me that the expression must either be computed or transparent in 6300 *every* block in the path(s) from EXPR_BB to BB. Any other definition 6301 would allow the expression to be hoisted out of loops, even if 6302 the expression wasn't a loop invariant. 6303 6304 Contrast this to reachability for PRE where an expression is 6305 considered reachable if *any* path reaches instead of *all* 6306 paths. */ 6307 6308static int 6309hoist_expr_reaches_here_p (basic_block expr_bb, int expr_index, basic_block bb, char *visited) 6310{ 6311 edge pred; 6312 int visited_allocated_locally = 0; 6313 6314 6315 if (visited == NULL) 6316 { 6317 visited_allocated_locally = 1; 6318 visited = xcalloc (last_basic_block, 1); 6319 } 6320 6321 for (pred = bb->pred; pred != NULL; pred = pred->pred_next) 6322 { 6323 basic_block pred_bb = pred->src; 6324 6325 if (pred->src == ENTRY_BLOCK_PTR) 6326 break; 6327 else if (pred_bb == expr_bb) 6328 continue; 6329 else if (visited[pred_bb->index]) 6330 continue; 6331 6332 /* Does this predecessor generate this expression? */ 6333 else if (TEST_BIT (comp[pred_bb->index], expr_index)) 6334 break; 6335 else if (! TEST_BIT (transp[pred_bb->index], expr_index)) 6336 break; 6337 6338 /* Not killed. */ 6339 else 6340 { 6341 visited[pred_bb->index] = 1; 6342 if (! hoist_expr_reaches_here_p (expr_bb, expr_index, 6343 pred_bb, visited)) 6344 break; 6345 } 6346 } 6347 if (visited_allocated_locally) 6348 free (visited); 6349 6350 return (pred == NULL); 6351} 6352 6353/* Actually perform code hoisting. */ 6354 6355static void 6356hoist_code (void) 6357{ 6358 basic_block bb, dominated; 6359 basic_block *domby; 6360 unsigned int domby_len; 6361 unsigned int i,j; 6362 struct expr **index_map; 6363 struct expr *expr; 6364 6365 sbitmap_vector_zero (hoist_exprs, last_basic_block); 6366 6367 /* Compute a mapping from expression number (`bitmap_index') to 6368 hash table entry. */ 6369 6370 index_map = xcalloc (expr_hash_table.n_elems, sizeof (struct expr *)); 6371 for (i = 0; i < expr_hash_table.size; i++) 6372 for (expr = expr_hash_table.table[i]; expr != NULL; expr = expr->next_same_hash) 6373 index_map[expr->bitmap_index] = expr; 6374 6375 /* Walk over each basic block looking for potentially hoistable 6376 expressions, nothing gets hoisted from the entry block. */ 6377 FOR_EACH_BB (bb) 6378 { 6379 int found = 0; 6380 int insn_inserted_p; 6381 6382 domby_len = get_dominated_by (CDI_DOMINATORS, bb, &domby); 6383 /* Examine each expression that is very busy at the exit of this 6384 block. These are the potentially hoistable expressions. */ 6385 for (i = 0; i < hoist_vbeout[bb->index]->n_bits; i++) 6386 { 6387 int hoistable = 0; 6388 6389 if (TEST_BIT (hoist_vbeout[bb->index], i) 6390 && TEST_BIT (transpout[bb->index], i)) 6391 { 6392 /* We've found a potentially hoistable expression, now 6393 we look at every block BB dominates to see if it 6394 computes the expression. */ 6395 for (j = 0; j < domby_len; j++) 6396 { 6397 dominated = domby[j]; 6398 /* Ignore self dominance. */ 6399 if (bb == dominated) 6400 continue; 6401 /* We've found a dominated block, now see if it computes 6402 the busy expression and whether or not moving that 6403 expression to the "beginning" of that block is safe. */ 6404 if (!TEST_BIT (antloc[dominated->index], i)) 6405 continue; 6406 6407 /* Note if the expression would reach the dominated block 6408 unimpared if it was placed at the end of BB. 6409 6410 Keep track of how many times this expression is hoistable 6411 from a dominated block into BB. */ 6412 if (hoist_expr_reaches_here_p (bb, i, dominated, NULL)) 6413 hoistable++; 6414 } 6415 6416 /* If we found more than one hoistable occurrence of this 6417 expression, then note it in the bitmap of expressions to 6418 hoist. It makes no sense to hoist things which are computed 6419 in only one BB, and doing so tends to pessimize register 6420 allocation. One could increase this value to try harder 6421 to avoid any possible code expansion due to register 6422 allocation issues; however experiments have shown that 6423 the vast majority of hoistable expressions are only movable 6424 from two successors, so raising this threshold is likely 6425 to nullify any benefit we get from code hoisting. */ 6426 if (hoistable > 1) 6427 { 6428 SET_BIT (hoist_exprs[bb->index], i); 6429 found = 1; 6430 } 6431 } 6432 } 6433 /* If we found nothing to hoist, then quit now. */ 6434 if (! found) 6435 { 6436 free (domby); 6437 continue; 6438 } 6439 6440 /* Loop over all the hoistable expressions. */ 6441 for (i = 0; i < hoist_exprs[bb->index]->n_bits; i++) 6442 { 6443 /* We want to insert the expression into BB only once, so 6444 note when we've inserted it. */ 6445 insn_inserted_p = 0; 6446 6447 /* These tests should be the same as the tests above. */ 6448 if (TEST_BIT (hoist_exprs[bb->index], i)) 6449 { 6450 /* We've found a potentially hoistable expression, now 6451 we look at every block BB dominates to see if it 6452 computes the expression. */ 6453 for (j = 0; j < domby_len; j++) 6454 { 6455 dominated = domby[j]; 6456 /* Ignore self dominance. */ 6457 if (bb == dominated) 6458 continue; 6459 6460 /* We've found a dominated block, now see if it computes 6461 the busy expression and whether or not moving that 6462 expression to the "beginning" of that block is safe. */ 6463 if (!TEST_BIT (antloc[dominated->index], i)) 6464 continue; 6465 6466 /* The expression is computed in the dominated block and 6467 it would be safe to compute it at the start of the 6468 dominated block. Now we have to determine if the 6469 expression would reach the dominated block if it was 6470 placed at the end of BB. */ 6471 if (hoist_expr_reaches_here_p (bb, i, dominated, NULL)) 6472 { 6473 struct expr *expr = index_map[i]; 6474 struct occr *occr = expr->antic_occr; 6475 rtx insn; 6476 rtx set; 6477 6478 /* Find the right occurrence of this expression. */ 6479 while (BLOCK_FOR_INSN (occr->insn) != dominated && occr) 6480 occr = occr->next; 6481 6482 /* Should never happen. */ 6483 if (!occr) 6484 abort (); 6485 6486 insn = occr->insn; 6487 6488 set = single_set (insn); 6489 if (! set) 6490 abort (); 6491 6492 /* Create a pseudo-reg to store the result of reaching 6493 expressions into. Get the mode for the new pseudo 6494 from the mode of the original destination pseudo. */ 6495 if (expr->reaching_reg == NULL) 6496 expr->reaching_reg 6497 = gen_reg_rtx (GET_MODE (SET_DEST (set))); 6498 6499 gcse_emit_move_after (expr->reaching_reg, SET_DEST (set), insn); 6500 delete_insn (insn); 6501 occr->deleted_p = 1; 6502 if (!insn_inserted_p) 6503 { 6504 insert_insn_end_bb (index_map[i], bb, 0); 6505 insn_inserted_p = 1; 6506 } 6507 } 6508 } 6509 } 6510 } 6511 free (domby); 6512 } 6513 6514 free (index_map); 6515} 6516 6517/* Top level routine to perform one code hoisting (aka unification) pass 6518 6519 Return nonzero if a change was made. */ 6520 6521static int 6522one_code_hoisting_pass (void) 6523{ 6524 int changed = 0; 6525 6526 alloc_hash_table (max_cuid, &expr_hash_table, 0); 6527 compute_hash_table (&expr_hash_table); 6528 if (gcse_file) 6529 dump_hash_table (gcse_file, "Code Hosting Expressions", &expr_hash_table); 6530 6531 if (expr_hash_table.n_elems > 0) 6532 { 6533 alloc_code_hoist_mem (last_basic_block, expr_hash_table.n_elems); 6534 compute_code_hoist_data (); 6535 hoist_code (); 6536 free_code_hoist_mem (); 6537 } 6538 6539 free_hash_table (&expr_hash_table); 6540 6541 return changed; 6542} 6543 6544/* Here we provide the things required to do store motion towards 6545 the exit. In order for this to be effective, gcse also needed to 6546 be taught how to move a load when it is kill only by a store to itself. 6547 6548 int i; 6549 float a[10]; 6550 6551 void foo(float scale) 6552 { 6553 for (i=0; i<10; i++) 6554 a[i] *= scale; 6555 } 6556 6557 'i' is both loaded and stored to in the loop. Normally, gcse cannot move 6558 the load out since its live around the loop, and stored at the bottom 6559 of the loop. 6560 6561 The 'Load Motion' referred to and implemented in this file is 6562 an enhancement to gcse which when using edge based lcm, recognizes 6563 this situation and allows gcse to move the load out of the loop. 6564 6565 Once gcse has hoisted the load, store motion can then push this 6566 load towards the exit, and we end up with no loads or stores of 'i' 6567 in the loop. */ 6568 6569/* This will search the ldst list for a matching expression. If it 6570 doesn't find one, we create one and initialize it. */ 6571 6572static struct ls_expr * 6573ldst_entry (rtx x) 6574{ 6575 int do_not_record_p = 0; 6576 struct ls_expr * ptr; 6577 unsigned int hash; 6578 6579 hash = hash_expr_1 (x, GET_MODE (x), & do_not_record_p); 6580 6581 for (ptr = pre_ldst_mems; ptr != NULL; ptr = ptr->next) 6582 if (ptr->hash_index == hash && expr_equiv_p (ptr->pattern, x)) 6583 return ptr; 6584 6585 ptr = xmalloc (sizeof (struct ls_expr)); 6586 6587 ptr->next = pre_ldst_mems; 6588 ptr->expr = NULL; 6589 ptr->pattern = x; 6590 ptr->pattern_regs = NULL_RTX; 6591 ptr->loads = NULL_RTX; 6592 ptr->stores = NULL_RTX; 6593 ptr->reaching_reg = NULL_RTX; 6594 ptr->invalid = 0; 6595 ptr->index = 0; 6596 ptr->hash_index = hash; 6597 pre_ldst_mems = ptr; 6598 6599 return ptr; 6600} 6601 6602/* Free up an individual ldst entry. */ 6603 6604static void 6605free_ldst_entry (struct ls_expr * ptr) 6606{ 6607 free_INSN_LIST_list (& ptr->loads); 6608 free_INSN_LIST_list (& ptr->stores); 6609 6610 free (ptr); 6611} 6612 6613/* Free up all memory associated with the ldst list. */ 6614 6615static void 6616free_ldst_mems (void) 6617{ 6618 while (pre_ldst_mems) 6619 { 6620 struct ls_expr * tmp = pre_ldst_mems; 6621 6622 pre_ldst_mems = pre_ldst_mems->next; 6623 6624 free_ldst_entry (tmp); 6625 } 6626 6627 pre_ldst_mems = NULL; 6628} 6629 6630/* Dump debugging info about the ldst list. */ 6631 6632static void 6633print_ldst_list (FILE * file) 6634{ 6635 struct ls_expr * ptr; 6636 6637 fprintf (file, "LDST list: \n"); 6638 6639 for (ptr = first_ls_expr(); ptr != NULL; ptr = next_ls_expr (ptr)) 6640 { 6641 fprintf (file, " Pattern (%3d): ", ptr->index); 6642 6643 print_rtl (file, ptr->pattern); 6644 6645 fprintf (file, "\n Loads : "); 6646 6647 if (ptr->loads) 6648 print_rtl (file, ptr->loads); 6649 else 6650 fprintf (file, "(nil)"); 6651 6652 fprintf (file, "\n Stores : "); 6653 6654 if (ptr->stores) 6655 print_rtl (file, ptr->stores); 6656 else 6657 fprintf (file, "(nil)"); 6658 6659 fprintf (file, "\n\n"); 6660 } 6661 6662 fprintf (file, "\n"); 6663} 6664 6665/* Returns 1 if X is in the list of ldst only expressions. */ 6666 6667static struct ls_expr * 6668find_rtx_in_ldst (rtx x) 6669{ 6670 struct ls_expr * ptr; 6671 6672 for (ptr = pre_ldst_mems; ptr != NULL; ptr = ptr->next) 6673 if (expr_equiv_p (ptr->pattern, x) && ! ptr->invalid) 6674 return ptr; 6675 6676 return NULL; 6677} 6678 6679/* Assign each element of the list of mems a monotonically increasing value. */ 6680 6681static int 6682enumerate_ldsts (void) 6683{ 6684 struct ls_expr * ptr; 6685 int n = 0; 6686 6687 for (ptr = pre_ldst_mems; ptr != NULL; ptr = ptr->next) 6688 ptr->index = n++; 6689 6690 return n; 6691} 6692 6693/* Return first item in the list. */ 6694 6695static inline struct ls_expr * 6696first_ls_expr (void) 6697{ 6698 return pre_ldst_mems; 6699} 6700 6701/* Return the next item in the list after the specified one. */ 6702 6703static inline struct ls_expr * 6704next_ls_expr (struct ls_expr * ptr) 6705{ 6706 return ptr->next; 6707} 6708 6709/* Load Motion for loads which only kill themselves. */ 6710 6711/* Return true if x is a simple MEM operation, with no registers or 6712 side effects. These are the types of loads we consider for the 6713 ld_motion list, otherwise we let the usual aliasing take care of it. */ 6714 6715static int 6716simple_mem (rtx x) 6717{ 6718 if (GET_CODE (x) != MEM) 6719 return 0; 6720 6721 if (MEM_VOLATILE_P (x)) 6722 return 0; 6723 6724 if (GET_MODE (x) == BLKmode) 6725 return 0; 6726 6727 /* If we are handling exceptions, we must be careful with memory references 6728 that may trap. If we are not, the behavior is undefined, so we may just 6729 continue. */ 6730 if (flag_non_call_exceptions && may_trap_p (x)) 6731 return 0; 6732 6733 if (side_effects_p (x)) 6734 return 0; 6735 6736 /* Do not consider function arguments passed on stack. */ 6737 if (reg_mentioned_p (stack_pointer_rtx, x)) 6738 return 0; 6739 6740 if (flag_float_store && FLOAT_MODE_P (GET_MODE (x))) 6741 return 0; 6742 6743 return 1; 6744} 6745 6746/* Make sure there isn't a buried reference in this pattern anywhere. 6747 If there is, invalidate the entry for it since we're not capable 6748 of fixing it up just yet.. We have to be sure we know about ALL 6749 loads since the aliasing code will allow all entries in the 6750 ld_motion list to not-alias itself. If we miss a load, we will get 6751 the wrong value since gcse might common it and we won't know to 6752 fix it up. */ 6753 6754static void 6755invalidate_any_buried_refs (rtx x) 6756{ 6757 const char * fmt; 6758 int i, j; 6759 struct ls_expr * ptr; 6760 6761 /* Invalidate it in the list. */ 6762 if (GET_CODE (x) == MEM && simple_mem (x)) 6763 { 6764 ptr = ldst_entry (x); 6765 ptr->invalid = 1; 6766 } 6767 6768 /* Recursively process the insn. */ 6769 fmt = GET_RTX_FORMAT (GET_CODE (x)); 6770 6771 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--) 6772 { 6773 if (fmt[i] == 'e') 6774 invalidate_any_buried_refs (XEXP (x, i)); 6775 else if (fmt[i] == 'E') 6776 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 6777 invalidate_any_buried_refs (XVECEXP (x, i, j)); 6778 } 6779} 6780 6781/* Find all the 'simple' MEMs which are used in LOADs and STORES. Simple 6782 being defined as MEM loads and stores to symbols, with no side effects 6783 and no registers in the expression. For a MEM destination, we also 6784 check that the insn is still valid if we replace the destination with a 6785 REG, as is done in update_ld_motion_stores. If there are any uses/defs 6786 which don't match this criteria, they are invalidated and trimmed out 6787 later. */ 6788 6789static void 6790compute_ld_motion_mems (void) 6791{ 6792 struct ls_expr * ptr; 6793 basic_block bb; 6794 rtx insn; 6795 6796 pre_ldst_mems = NULL; 6797 6798 FOR_EACH_BB (bb) 6799 { 6800 for (insn = BB_HEAD (bb); 6801 insn && insn != NEXT_INSN (BB_END (bb)); 6802 insn = NEXT_INSN (insn)) 6803 { 6804 if (INSN_P (insn)) 6805 { 6806 if (GET_CODE (PATTERN (insn)) == SET) 6807 { 6808 rtx src = SET_SRC (PATTERN (insn)); 6809 rtx dest = SET_DEST (PATTERN (insn)); 6810 6811 /* Check for a simple LOAD... */ 6812 if (GET_CODE (src) == MEM && simple_mem (src)) 6813 { 6814 ptr = ldst_entry (src); 6815 if (GET_CODE (dest) == REG) 6816 ptr->loads = alloc_INSN_LIST (insn, ptr->loads); 6817 else 6818 ptr->invalid = 1; 6819 } 6820 else 6821 { 6822 /* Make sure there isn't a buried load somewhere. */ 6823 invalidate_any_buried_refs (src); 6824 } 6825 6826 /* Check for stores. Don't worry about aliased ones, they 6827 will block any movement we might do later. We only care 6828 about this exact pattern since those are the only 6829 circumstance that we will ignore the aliasing info. */ 6830 if (GET_CODE (dest) == MEM && simple_mem (dest)) 6831 { 6832 ptr = ldst_entry (dest); 6833 6834 if (GET_CODE (src) != MEM 6835 && GET_CODE (src) != ASM_OPERANDS 6836 /* Check for REG manually since want_to_gcse_p 6837 returns 0 for all REGs. */ 6838 && (REG_P (src) || want_to_gcse_p (src))) 6839 ptr->stores = alloc_INSN_LIST (insn, ptr->stores); 6840 else 6841 ptr->invalid = 1; 6842 } 6843 } 6844 else 6845 invalidate_any_buried_refs (PATTERN (insn)); 6846 } 6847 } 6848 } 6849} 6850 6851/* Remove any references that have been either invalidated or are not in the 6852 expression list for pre gcse. */ 6853 6854static void 6855trim_ld_motion_mems (void) 6856{ 6857 struct ls_expr * * last = & pre_ldst_mems; 6858 struct ls_expr * ptr = pre_ldst_mems; 6859 6860 while (ptr != NULL) 6861 { 6862 struct expr * expr; 6863 6864 /* Delete if entry has been made invalid. */ 6865 if (! ptr->invalid) 6866 { 6867 /* Delete if we cannot find this mem in the expression list. */ 6868 unsigned int hash = ptr->hash_index % expr_hash_table.size; 6869 6870 for (expr = expr_hash_table.table[hash]; 6871 expr != NULL; 6872 expr = expr->next_same_hash) 6873 if (expr_equiv_p (expr->expr, ptr->pattern)) 6874 break; 6875 } 6876 else 6877 expr = (struct expr *) 0; 6878 6879 if (expr) 6880 { 6881 /* Set the expression field if we are keeping it. */ 6882 ptr->expr = expr; 6883 last = & ptr->next; 6884 ptr = ptr->next; 6885 } 6886 else 6887 { 6888 *last = ptr->next; 6889 free_ldst_entry (ptr); 6890 ptr = * last; 6891 } 6892 } 6893 6894 /* Show the world what we've found. */ 6895 if (gcse_file && pre_ldst_mems != NULL) 6896 print_ldst_list (gcse_file); 6897} 6898 6899/* This routine will take an expression which we are replacing with 6900 a reaching register, and update any stores that are needed if 6901 that expression is in the ld_motion list. Stores are updated by 6902 copying their SRC to the reaching register, and then storing 6903 the reaching register into the store location. These keeps the 6904 correct value in the reaching register for the loads. */ 6905 6906static void 6907update_ld_motion_stores (struct expr * expr) 6908{ 6909 struct ls_expr * mem_ptr; 6910 6911 if ((mem_ptr = find_rtx_in_ldst (expr->expr))) 6912 { 6913 /* We can try to find just the REACHED stores, but is shouldn't 6914 matter to set the reaching reg everywhere... some might be 6915 dead and should be eliminated later. */ 6916 6917 /* We replace (set mem expr) with (set reg expr) (set mem reg) 6918 where reg is the reaching reg used in the load. We checked in 6919 compute_ld_motion_mems that we can replace (set mem expr) with 6920 (set reg expr) in that insn. */ 6921 rtx list = mem_ptr->stores; 6922 6923 for ( ; list != NULL_RTX; list = XEXP (list, 1)) 6924 { 6925 rtx insn = XEXP (list, 0); 6926 rtx pat = PATTERN (insn); 6927 rtx src = SET_SRC (pat); 6928 rtx reg = expr->reaching_reg; 6929 rtx copy, new; 6930 6931 /* If we've already copied it, continue. */ 6932 if (expr->reaching_reg == src) 6933 continue; 6934 6935 if (gcse_file) 6936 { 6937 fprintf (gcse_file, "PRE: store updated with reaching reg "); 6938 print_rtl (gcse_file, expr->reaching_reg); 6939 fprintf (gcse_file, ":\n "); 6940 print_inline_rtx (gcse_file, insn, 8); 6941 fprintf (gcse_file, "\n"); 6942 } 6943 6944 copy = gen_move_insn ( reg, copy_rtx (SET_SRC (pat))); 6945 new = emit_insn_before (copy, insn); 6946 record_one_set (REGNO (reg), new); 6947 SET_SRC (pat) = reg; 6948 6949 /* un-recognize this pattern since it's probably different now. */ 6950 INSN_CODE (insn) = -1; 6951 gcse_create_count++; 6952 } 6953 } 6954} 6955 6956/* Store motion code. */ 6957 6958#define ANTIC_STORE_LIST(x) ((x)->loads) 6959#define AVAIL_STORE_LIST(x) ((x)->stores) 6960#define LAST_AVAIL_CHECK_FAILURE(x) ((x)->reaching_reg) 6961 6962/* This is used to communicate the target bitvector we want to use in the 6963 reg_set_info routine when called via the note_stores mechanism. */ 6964static int * regvec; 6965 6966/* And current insn, for the same routine. */ 6967static rtx compute_store_table_current_insn; 6968 6969/* Used in computing the reverse edge graph bit vectors. */ 6970static sbitmap * st_antloc; 6971 6972/* Global holding the number of store expressions we are dealing with. */ 6973static int num_stores; 6974 6975/* Checks to set if we need to mark a register set. Called from 6976 note_stores. */ 6977 6978static void 6979reg_set_info (rtx dest, rtx setter ATTRIBUTE_UNUSED, 6980 void *data) 6981{ 6982 sbitmap bb_reg = data; 6983 6984 if (GET_CODE (dest) == SUBREG) 6985 dest = SUBREG_REG (dest); 6986 6987 if (GET_CODE (dest) == REG) 6988 { 6989 regvec[REGNO (dest)] = INSN_UID (compute_store_table_current_insn); 6990 if (bb_reg) 6991 SET_BIT (bb_reg, REGNO (dest)); 6992 } 6993} 6994 6995/* Clear any mark that says that this insn sets dest. Called from 6996 note_stores. */ 6997 6998static void 6999reg_clear_last_set (rtx dest, rtx setter ATTRIBUTE_UNUSED, 7000 void *data) 7001{ 7002 int *dead_vec = data; 7003 7004 if (GET_CODE (dest) == SUBREG) 7005 dest = SUBREG_REG (dest); 7006 7007 if (GET_CODE (dest) == REG && 7008 dead_vec[REGNO (dest)] == INSN_UID (compute_store_table_current_insn)) 7009 dead_vec[REGNO (dest)] = 0; 7010} 7011 7012/* Return zero if some of the registers in list X are killed 7013 due to set of registers in bitmap REGS_SET. */ 7014 7015static bool 7016store_ops_ok (rtx x, int *regs_set) 7017{ 7018 rtx reg; 7019 7020 for (; x; x = XEXP (x, 1)) 7021 { 7022 reg = XEXP (x, 0); 7023 if (regs_set[REGNO(reg)]) 7024 return false; 7025 } 7026 7027 return true; 7028} 7029 7030/* Returns a list of registers mentioned in X. */ 7031static rtx 7032extract_mentioned_regs (rtx x) 7033{ 7034 return extract_mentioned_regs_helper (x, NULL_RTX); 7035} 7036 7037/* Helper for extract_mentioned_regs; ACCUM is used to accumulate used 7038 registers. */ 7039static rtx 7040extract_mentioned_regs_helper (rtx x, rtx accum) 7041{ 7042 int i; 7043 enum rtx_code code; 7044 const char * fmt; 7045 7046 /* Repeat is used to turn tail-recursion into iteration. */ 7047 repeat: 7048 7049 if (x == 0) 7050 return accum; 7051 7052 code = GET_CODE (x); 7053 switch (code) 7054 { 7055 case REG: 7056 return alloc_EXPR_LIST (0, x, accum); 7057 7058 case MEM: 7059 x = XEXP (x, 0); 7060 goto repeat; 7061 7062 case PRE_DEC: 7063 case PRE_INC: 7064 case POST_DEC: 7065 case POST_INC: 7066 /* We do not run this function with arguments having side effects. */ 7067 abort (); 7068 7069 case PC: 7070 case CC0: /*FIXME*/ 7071 case CONST: 7072 case CONST_INT: 7073 case CONST_DOUBLE: 7074 case CONST_VECTOR: 7075 case SYMBOL_REF: 7076 case LABEL_REF: 7077 case ADDR_VEC: 7078 case ADDR_DIFF_VEC: 7079 return accum; 7080 7081 default: 7082 break; 7083 } 7084 7085 i = GET_RTX_LENGTH (code) - 1; 7086 fmt = GET_RTX_FORMAT (code); 7087 7088 for (; i >= 0; i--) 7089 { 7090 if (fmt[i] == 'e') 7091 { 7092 rtx tem = XEXP (x, i); 7093 7094 /* If we are about to do the last recursive call 7095 needed at this level, change it into iteration. */ 7096 if (i == 0) 7097 { 7098 x = tem; 7099 goto repeat; 7100 } 7101 7102 accum = extract_mentioned_regs_helper (tem, accum); 7103 } 7104 else if (fmt[i] == 'E') 7105 { 7106 int j; 7107 7108 for (j = 0; j < XVECLEN (x, i); j++) 7109 accum = extract_mentioned_regs_helper (XVECEXP (x, i, j), accum); 7110 } 7111 } 7112 7113 return accum; 7114} 7115 7116/* Determine whether INSN is MEM store pattern that we will consider moving. 7117 REGS_SET_BEFORE is bitmap of registers set before (and including) the 7118 current insn, REGS_SET_AFTER is bitmap of registers set after (and 7119 including) the insn in this basic block. We must be passing through BB from 7120 head to end, as we are using this fact to speed things up. 7121 7122 The results are stored this way: 7123 7124 -- the first anticipatable expression is added into ANTIC_STORE_LIST 7125 -- if the processed expression is not anticipatable, NULL_RTX is added 7126 there instead, so that we can use it as indicator that no further 7127 expression of this type may be anticipatable 7128 -- if the expression is available, it is added as head of AVAIL_STORE_LIST; 7129 consequently, all of them but this head are dead and may be deleted. 7130 -- if the expression is not available, the insn due to that it fails to be 7131 available is stored in reaching_reg. 7132 7133 The things are complicated a bit by fact that there already may be stores 7134 to the same MEM from other blocks; also caller must take care of the 7135 necessary cleanup of the temporary markers after end of the basic block. 7136 */ 7137 7138static void 7139find_moveable_store (rtx insn, int *regs_set_before, int *regs_set_after) 7140{ 7141 struct ls_expr * ptr; 7142 rtx dest, set, tmp; 7143 int check_anticipatable, check_available; 7144 basic_block bb = BLOCK_FOR_INSN (insn); 7145 7146 set = single_set (insn); 7147 if (!set) 7148 return; 7149 7150 dest = SET_DEST (set); 7151 7152 if (GET_CODE (dest) != MEM || MEM_VOLATILE_P (dest) 7153 || GET_MODE (dest) == BLKmode) 7154 return; 7155 7156 if (side_effects_p (dest)) 7157 return; 7158 7159 /* If we are handling exceptions, we must be careful with memory references 7160 that may trap. If we are not, the behavior is undefined, so we may just 7161 continue. */ 7162 if (flag_non_call_exceptions && may_trap_p (dest)) 7163 return; 7164 7165 ptr = ldst_entry (dest); 7166 if (!ptr->pattern_regs) 7167 ptr->pattern_regs = extract_mentioned_regs (dest); 7168 7169 /* Do not check for anticipatability if we either found one anticipatable 7170 store already, or tested for one and found out that it was killed. */ 7171 check_anticipatable = 0; 7172 if (!ANTIC_STORE_LIST (ptr)) 7173 check_anticipatable = 1; 7174 else 7175 { 7176 tmp = XEXP (ANTIC_STORE_LIST (ptr), 0); 7177 if (tmp != NULL_RTX 7178 && BLOCK_FOR_INSN (tmp) != bb) 7179 check_anticipatable = 1; 7180 } 7181 if (check_anticipatable) 7182 { 7183 if (store_killed_before (dest, ptr->pattern_regs, insn, bb, regs_set_before)) 7184 tmp = NULL_RTX; 7185 else 7186 tmp = insn; 7187 ANTIC_STORE_LIST (ptr) = alloc_INSN_LIST (tmp, 7188 ANTIC_STORE_LIST (ptr)); 7189 } 7190 7191 /* It is not necessary to check whether store is available if we did 7192 it successfully before; if we failed before, do not bother to check 7193 until we reach the insn that caused us to fail. */ 7194 check_available = 0; 7195 if (!AVAIL_STORE_LIST (ptr)) 7196 check_available = 1; 7197 else 7198 { 7199 tmp = XEXP (AVAIL_STORE_LIST (ptr), 0); 7200 if (BLOCK_FOR_INSN (tmp) != bb) 7201 check_available = 1; 7202 } 7203 if (check_available) 7204 { 7205 /* Check that we have already reached the insn at that the check 7206 failed last time. */ 7207 if (LAST_AVAIL_CHECK_FAILURE (ptr)) 7208 { 7209 for (tmp = BB_END (bb); 7210 tmp != insn && tmp != LAST_AVAIL_CHECK_FAILURE (ptr); 7211 tmp = PREV_INSN (tmp)) 7212 continue; 7213 if (tmp == insn) 7214 check_available = 0; 7215 } 7216 else 7217 check_available = store_killed_after (dest, ptr->pattern_regs, insn, 7218 bb, regs_set_after, 7219 &LAST_AVAIL_CHECK_FAILURE (ptr)); 7220 } 7221 if (!check_available) 7222 AVAIL_STORE_LIST (ptr) = alloc_INSN_LIST (insn, AVAIL_STORE_LIST (ptr)); 7223} 7224 7225/* Find available and anticipatable stores. */ 7226 7227static int 7228compute_store_table (void) 7229{ 7230 int ret; 7231 basic_block bb; 7232 unsigned regno; 7233 rtx insn, pat, tmp; 7234 int *last_set_in, *already_set; 7235 struct ls_expr * ptr, **prev_next_ptr_ptr; 7236 7237 max_gcse_regno = max_reg_num (); 7238 7239 reg_set_in_block = sbitmap_vector_alloc (last_basic_block, 7240 max_gcse_regno); 7241 sbitmap_vector_zero (reg_set_in_block, last_basic_block); 7242 pre_ldst_mems = 0; 7243 last_set_in = xcalloc (max_gcse_regno, sizeof (int)); 7244 already_set = xmalloc (sizeof (int) * max_gcse_regno); 7245 7246 /* Find all the stores we care about. */ 7247 FOR_EACH_BB (bb) 7248 { 7249 /* First compute the registers set in this block. */ 7250 regvec = last_set_in; 7251 7252 for (insn = BB_HEAD (bb); 7253 insn != NEXT_INSN (BB_END (bb)); 7254 insn = NEXT_INSN (insn)) 7255 { 7256 if (! INSN_P (insn)) 7257 continue; 7258 7259 if (GET_CODE (insn) == CALL_INSN) 7260 { 7261 bool clobbers_all = false; 7262#ifdef NON_SAVING_SETJMP 7263 if (NON_SAVING_SETJMP 7264 && find_reg_note (insn, REG_SETJMP, NULL_RTX)) 7265 clobbers_all = true; 7266#endif 7267 7268 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++) 7269 if (clobbers_all 7270 || TEST_HARD_REG_BIT (regs_invalidated_by_call, regno)) 7271 { 7272 last_set_in[regno] = INSN_UID (insn); 7273 SET_BIT (reg_set_in_block[bb->index], regno); 7274 } 7275 } 7276 7277 pat = PATTERN (insn); 7278 compute_store_table_current_insn = insn; 7279 note_stores (pat, reg_set_info, reg_set_in_block[bb->index]); 7280 } 7281 7282 /* Now find the stores. */ 7283 memset (already_set, 0, sizeof (int) * max_gcse_regno); 7284 regvec = already_set; 7285 for (insn = BB_HEAD (bb); 7286 insn != NEXT_INSN (BB_END (bb)); 7287 insn = NEXT_INSN (insn)) 7288 { 7289 if (! INSN_P (insn)) 7290 continue; 7291 7292 if (GET_CODE (insn) == CALL_INSN) 7293 { 7294 bool clobbers_all = false; 7295#ifdef NON_SAVING_SETJMP 7296 if (NON_SAVING_SETJMP 7297 && find_reg_note (insn, REG_SETJMP, NULL_RTX)) 7298 clobbers_all = true; 7299#endif 7300 7301 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++) 7302 if (clobbers_all 7303 || TEST_HARD_REG_BIT (regs_invalidated_by_call, regno)) 7304 already_set[regno] = 1; 7305 } 7306 7307 pat = PATTERN (insn); 7308 note_stores (pat, reg_set_info, NULL); 7309 7310 /* Now that we've marked regs, look for stores. */ 7311 find_moveable_store (insn, already_set, last_set_in); 7312 7313 /* Unmark regs that are no longer set. */ 7314 compute_store_table_current_insn = insn; 7315 note_stores (pat, reg_clear_last_set, last_set_in); 7316 if (GET_CODE (insn) == CALL_INSN) 7317 { 7318 bool clobbers_all = false; 7319#ifdef NON_SAVING_SETJMP 7320 if (NON_SAVING_SETJMP 7321 && find_reg_note (insn, REG_SETJMP, NULL_RTX)) 7322 clobbers_all = true; 7323#endif 7324 7325 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++) 7326 if ((clobbers_all 7327 || TEST_HARD_REG_BIT (regs_invalidated_by_call, regno)) 7328 && last_set_in[regno] == INSN_UID (insn)) 7329 last_set_in[regno] = 0; 7330 } 7331 } 7332 7333#ifdef ENABLE_CHECKING 7334 /* last_set_in should now be all-zero. */ 7335 for (regno = 0; regno < max_gcse_regno; regno++) 7336 if (last_set_in[regno] != 0) 7337 abort (); 7338#endif 7339 7340 /* Clear temporary marks. */ 7341 for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr)) 7342 { 7343 LAST_AVAIL_CHECK_FAILURE(ptr) = NULL_RTX; 7344 if (ANTIC_STORE_LIST (ptr) 7345 && (tmp = XEXP (ANTIC_STORE_LIST (ptr), 0)) == NULL_RTX) 7346 ANTIC_STORE_LIST (ptr) = XEXP (ANTIC_STORE_LIST (ptr), 1); 7347 } 7348 } 7349 7350 /* Remove the stores that are not available anywhere, as there will 7351 be no opportunity to optimize them. */ 7352 for (ptr = pre_ldst_mems, prev_next_ptr_ptr = &pre_ldst_mems; 7353 ptr != NULL; 7354 ptr = *prev_next_ptr_ptr) 7355 { 7356 if (!AVAIL_STORE_LIST (ptr)) 7357 { 7358 *prev_next_ptr_ptr = ptr->next; 7359 free_ldst_entry (ptr); 7360 } 7361 else 7362 prev_next_ptr_ptr = &ptr->next; 7363 } 7364 7365 ret = enumerate_ldsts (); 7366 7367 if (gcse_file) 7368 { 7369 fprintf (gcse_file, "ST_avail and ST_antic (shown under loads..)\n"); 7370 print_ldst_list (gcse_file); 7371 } 7372 7373 free (last_set_in); 7374 free (already_set); 7375 return ret; 7376} 7377 7378/* Check to see if the load X is aliased with STORE_PATTERN. 7379 AFTER is true if we are checking the case when STORE_PATTERN occurs 7380 after the X. */ 7381 7382static bool 7383load_kills_store (rtx x, rtx store_pattern, int after) 7384{ 7385 if (after) 7386 return anti_dependence (x, store_pattern); 7387 else 7388 return true_dependence (store_pattern, GET_MODE (store_pattern), x, 7389 rtx_addr_varies_p); 7390} 7391 7392/* Go through the entire insn X, looking for any loads which might alias 7393 STORE_PATTERN. Return true if found. 7394 AFTER is true if we are checking the case when STORE_PATTERN occurs 7395 after the insn X. */ 7396 7397static bool 7398find_loads (rtx x, rtx store_pattern, int after) 7399{ 7400 const char * fmt; 7401 int i, j; 7402 int ret = false; 7403 7404 if (!x) 7405 return false; 7406 7407 if (GET_CODE (x) == SET) 7408 x = SET_SRC (x); 7409 7410 if (GET_CODE (x) == MEM) 7411 { 7412 if (load_kills_store (x, store_pattern, after)) 7413 return true; 7414 } 7415 7416 /* Recursively process the insn. */ 7417 fmt = GET_RTX_FORMAT (GET_CODE (x)); 7418 7419 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0 && !ret; i--) 7420 { 7421 if (fmt[i] == 'e') 7422 ret |= find_loads (XEXP (x, i), store_pattern, after); 7423 else if (fmt[i] == 'E') 7424 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 7425 ret |= find_loads (XVECEXP (x, i, j), store_pattern, after); 7426 } 7427 return ret; 7428} 7429 7430/* Check if INSN kills the store pattern X (is aliased with it). 7431 AFTER is true if we are checking the case when store X occurs 7432 after the insn. Return true if it it does. */ 7433 7434static bool 7435store_killed_in_insn (rtx x, rtx x_regs, rtx insn, int after) 7436{ 7437 rtx reg, base, note; 7438 7439 if (!INSN_P (insn)) 7440 return false; 7441 7442 if (GET_CODE (insn) == CALL_INSN) 7443 { 7444 /* A normal or pure call might read from pattern, 7445 but a const call will not. */ 7446 if (! CONST_OR_PURE_CALL_P (insn) || pure_call_p (insn)) 7447 return true; 7448 7449 /* But even a const call reads its parameters. Check whether the 7450 base of some of registers used in mem is stack pointer. */ 7451 for (reg = x_regs; reg; reg = XEXP (reg, 1)) 7452 { 7453 base = find_base_term (XEXP (reg, 0)); 7454 if (!base 7455 || (GET_CODE (base) == ADDRESS 7456 && GET_MODE (base) == Pmode 7457 && XEXP (base, 0) == stack_pointer_rtx)) 7458 return true; 7459 } 7460 7461 return false; 7462 } 7463 7464 if (GET_CODE (PATTERN (insn)) == SET) 7465 { 7466 rtx pat = PATTERN (insn); 7467 rtx dest = SET_DEST (pat); 7468 7469 if (GET_CODE (dest) == SIGN_EXTRACT 7470 || GET_CODE (dest) == ZERO_EXTRACT) 7471 dest = XEXP (dest, 0); 7472 7473 /* Check for memory stores to aliased objects. */ 7474 if (GET_CODE (dest) == MEM 7475 && !expr_equiv_p (dest, x)) 7476 { 7477 if (after) 7478 { 7479 if (output_dependence (dest, x)) 7480 return true; 7481 } 7482 else 7483 { 7484 if (output_dependence (x, dest)) 7485 return true; 7486 } 7487 } 7488 if (find_loads (SET_SRC (pat), x, after)) 7489 return true; 7490 } 7491 else if (find_loads (PATTERN (insn), x, after)) 7492 return true; 7493 7494 /* If this insn has a REG_EQUAL or REG_EQUIV note referencing a memory 7495 location aliased with X, then this insn kills X. */ 7496 note = find_reg_equal_equiv_note (insn); 7497 if (! note) 7498 return false; 7499 note = XEXP (note, 0); 7500 7501 /* However, if the note represents a must alias rather than a may 7502 alias relationship, then it does not kill X. */ 7503 if (expr_equiv_p (note, x)) 7504 return false; 7505 7506 /* See if there are any aliased loads in the note. */ 7507 return find_loads (note, x, after); 7508} 7509 7510/* Returns true if the expression X is loaded or clobbered on or after INSN 7511 within basic block BB. REGS_SET_AFTER is bitmap of registers set in 7512 or after the insn. X_REGS is list of registers mentioned in X. If the store 7513 is killed, return the last insn in that it occurs in FAIL_INSN. */ 7514 7515static bool 7516store_killed_after (rtx x, rtx x_regs, rtx insn, basic_block bb, 7517 int *regs_set_after, rtx *fail_insn) 7518{ 7519 rtx last = BB_END (bb), act; 7520 7521 if (!store_ops_ok (x_regs, regs_set_after)) 7522 { 7523 /* We do not know where it will happen. */ 7524 if (fail_insn) 7525 *fail_insn = NULL_RTX; 7526 return true; 7527 } 7528 7529 /* Scan from the end, so that fail_insn is determined correctly. */ 7530 for (act = last; act != PREV_INSN (insn); act = PREV_INSN (act)) 7531 if (store_killed_in_insn (x, x_regs, act, false)) 7532 { 7533 if (fail_insn) 7534 *fail_insn = act; 7535 return true; 7536 } 7537 7538 return false; 7539} 7540 7541/* Returns true if the expression X is loaded or clobbered on or before INSN 7542 within basic block BB. X_REGS is list of registers mentioned in X. 7543 REGS_SET_BEFORE is bitmap of registers set before or in this insn. */ 7544static bool 7545store_killed_before (rtx x, rtx x_regs, rtx insn, basic_block bb, 7546 int *regs_set_before) 7547{ 7548 rtx first = BB_HEAD (bb); 7549 7550 if (!store_ops_ok (x_regs, regs_set_before)) 7551 return true; 7552 7553 for ( ; insn != PREV_INSN (first); insn = PREV_INSN (insn)) 7554 if (store_killed_in_insn (x, x_regs, insn, true)) 7555 return true; 7556 7557 return false; 7558} 7559 7560/* Fill in available, anticipatable, transparent and kill vectors in 7561 STORE_DATA, based on lists of available and anticipatable stores. */ 7562static void 7563build_store_vectors (void) 7564{ 7565 basic_block bb; 7566 int *regs_set_in_block; 7567 rtx insn, st; 7568 struct ls_expr * ptr; 7569 unsigned regno; 7570 7571 /* Build the gen_vector. This is any store in the table which is not killed 7572 by aliasing later in its block. */ 7573 ae_gen = sbitmap_vector_alloc (last_basic_block, num_stores); 7574 sbitmap_vector_zero (ae_gen, last_basic_block); 7575 7576 st_antloc = sbitmap_vector_alloc (last_basic_block, num_stores); 7577 sbitmap_vector_zero (st_antloc, last_basic_block); 7578 7579 for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr)) 7580 { 7581 for (st = AVAIL_STORE_LIST (ptr); st != NULL; st = XEXP (st, 1)) 7582 { 7583 insn = XEXP (st, 0); 7584 bb = BLOCK_FOR_INSN (insn); 7585 7586 /* If we've already seen an available expression in this block, 7587 we can delete this one (It occurs earlier in the block). We'll 7588 copy the SRC expression to an unused register in case there 7589 are any side effects. */ 7590 if (TEST_BIT (ae_gen[bb->index], ptr->index)) 7591 { 7592 rtx r = gen_reg_rtx (GET_MODE (ptr->pattern)); 7593 if (gcse_file) 7594 fprintf (gcse_file, "Removing redundant store:\n"); 7595 replace_store_insn (r, XEXP (st, 0), bb, ptr); 7596 continue; 7597 } 7598 SET_BIT (ae_gen[bb->index], ptr->index); 7599 } 7600 7601 for (st = ANTIC_STORE_LIST (ptr); st != NULL; st = XEXP (st, 1)) 7602 { 7603 insn = XEXP (st, 0); 7604 bb = BLOCK_FOR_INSN (insn); 7605 SET_BIT (st_antloc[bb->index], ptr->index); 7606 } 7607 } 7608 7609 ae_kill = sbitmap_vector_alloc (last_basic_block, num_stores); 7610 sbitmap_vector_zero (ae_kill, last_basic_block); 7611 7612 transp = sbitmap_vector_alloc (last_basic_block, num_stores); 7613 sbitmap_vector_zero (transp, last_basic_block); 7614 regs_set_in_block = xmalloc (sizeof (int) * max_gcse_regno); 7615 7616 FOR_EACH_BB (bb) 7617 { 7618 for (regno = 0; regno < max_gcse_regno; regno++) 7619 regs_set_in_block[regno] = TEST_BIT (reg_set_in_block[bb->index], regno); 7620 7621 for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr)) 7622 { 7623 if (store_killed_after (ptr->pattern, ptr->pattern_regs, BB_HEAD (bb), 7624 bb, regs_set_in_block, NULL)) 7625 { 7626 /* It should not be necessary to consider the expression 7627 killed if it is both anticipatable and available. */ 7628 if (!TEST_BIT (st_antloc[bb->index], ptr->index) 7629 || !TEST_BIT (ae_gen[bb->index], ptr->index)) 7630 SET_BIT (ae_kill[bb->index], ptr->index); 7631 } 7632 else 7633 SET_BIT (transp[bb->index], ptr->index); 7634 } 7635 } 7636 7637 free (regs_set_in_block); 7638 7639 if (gcse_file) 7640 { 7641 dump_sbitmap_vector (gcse_file, "st_antloc", "", st_antloc, last_basic_block); 7642 dump_sbitmap_vector (gcse_file, "st_kill", "", ae_kill, last_basic_block); 7643 dump_sbitmap_vector (gcse_file, "Transpt", "", transp, last_basic_block); 7644 dump_sbitmap_vector (gcse_file, "st_avloc", "", ae_gen, last_basic_block); 7645 } 7646} 7647 7648/* Insert an instruction at the beginning of a basic block, and update 7649 the BB_HEAD if needed. */ 7650 7651static void 7652insert_insn_start_bb (rtx insn, basic_block bb) 7653{ 7654 /* Insert at start of successor block. */ 7655 rtx prev = PREV_INSN (BB_HEAD (bb)); 7656 rtx before = BB_HEAD (bb); 7657 while (before != 0) 7658 { 7659 if (GET_CODE (before) != CODE_LABEL 7660 && (GET_CODE (before) != NOTE 7661 || NOTE_LINE_NUMBER (before) != NOTE_INSN_BASIC_BLOCK)) 7662 break; 7663 prev = before; 7664 if (prev == BB_END (bb)) 7665 break; 7666 before = NEXT_INSN (before); 7667 } 7668 7669 insn = emit_insn_after_noloc (insn, prev); 7670 7671 if (gcse_file) 7672 { 7673 fprintf (gcse_file, "STORE_MOTION insert store at start of BB %d:\n", 7674 bb->index); 7675 print_inline_rtx (gcse_file, insn, 6); 7676 fprintf (gcse_file, "\n"); 7677 } 7678} 7679 7680/* This routine will insert a store on an edge. EXPR is the ldst entry for 7681 the memory reference, and E is the edge to insert it on. Returns nonzero 7682 if an edge insertion was performed. */ 7683 7684static int 7685insert_store (struct ls_expr * expr, edge e) 7686{ 7687 rtx reg, insn; 7688 basic_block bb; 7689 edge tmp; 7690 7691 /* We did all the deleted before this insert, so if we didn't delete a 7692 store, then we haven't set the reaching reg yet either. */ 7693 if (expr->reaching_reg == NULL_RTX) 7694 return 0; 7695 7696 if (e->flags & EDGE_FAKE) 7697 return 0; 7698 7699 reg = expr->reaching_reg; 7700 insn = gen_move_insn (copy_rtx (expr->pattern), reg); 7701 7702 /* If we are inserting this expression on ALL predecessor edges of a BB, 7703 insert it at the start of the BB, and reset the insert bits on the other 7704 edges so we don't try to insert it on the other edges. */ 7705 bb = e->dest; 7706 for (tmp = e->dest->pred; tmp ; tmp = tmp->pred_next) 7707 if (!(tmp->flags & EDGE_FAKE)) 7708 { 7709 int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest); 7710 if (index == EDGE_INDEX_NO_EDGE) 7711 abort (); 7712 if (! TEST_BIT (pre_insert_map[index], expr->index)) 7713 break; 7714 } 7715 7716 /* If tmp is NULL, we found an insertion on every edge, blank the 7717 insertion vector for these edges, and insert at the start of the BB. */ 7718 if (!tmp && bb != EXIT_BLOCK_PTR) 7719 { 7720 for (tmp = e->dest->pred; tmp ; tmp = tmp->pred_next) 7721 { 7722 int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest); 7723 RESET_BIT (pre_insert_map[index], expr->index); 7724 } 7725 insert_insn_start_bb (insn, bb); 7726 return 0; 7727 } 7728 7729 /* We can't insert on this edge, so we'll insert at the head of the 7730 successors block. See Morgan, sec 10.5. */ 7731 if ((e->flags & EDGE_ABNORMAL) == EDGE_ABNORMAL) 7732 { 7733 insert_insn_start_bb (insn, bb); 7734 return 0; 7735 } 7736 7737 insert_insn_on_edge (insn, e); 7738 7739 if (gcse_file) 7740 { 7741 fprintf (gcse_file, "STORE_MOTION insert insn on edge (%d, %d):\n", 7742 e->src->index, e->dest->index); 7743 print_inline_rtx (gcse_file, insn, 6); 7744 fprintf (gcse_file, "\n"); 7745 } 7746 7747 return 1; 7748} 7749 7750/* Remove any REG_EQUAL or REG_EQUIV notes containing a reference to the 7751 memory location in SMEXPR set in basic block BB. 7752 7753 This could be rather expensive. */ 7754 7755static void 7756remove_reachable_equiv_notes (basic_block bb, struct ls_expr *smexpr) 7757{ 7758 edge *stack = xmalloc (sizeof (edge) * n_basic_blocks), act; 7759 sbitmap visited = sbitmap_alloc (last_basic_block); 7760 int stack_top = 0; 7761 rtx last, insn, note; 7762 rtx mem = smexpr->pattern; 7763 7764 sbitmap_zero (visited); 7765 act = bb->succ; 7766 7767 while (1) 7768 { 7769 if (!act) 7770 { 7771 if (!stack_top) 7772 { 7773 free (stack); 7774 sbitmap_free (visited); 7775 return; 7776 } 7777 act = stack[--stack_top]; 7778 } 7779 bb = act->dest; 7780 7781 /* We used to continue the loop without scanning this block if the 7782 store expression was killed in this block. That is wrong as 7783 we could have had a REG_EQUAL note with the store expression 7784 appear in the block before the insn which killed the store 7785 expression and that REG_EQUAL note needs to be removed as it 7786 is invalid. */ 7787 if (bb == EXIT_BLOCK_PTR 7788 || TEST_BIT (visited, bb->index)) 7789 { 7790 act = act->succ_next; 7791 continue; 7792 } 7793 SET_BIT (visited, bb->index); 7794 7795 if (TEST_BIT (st_antloc[bb->index], smexpr->index)) 7796 { 7797 for (last = ANTIC_STORE_LIST (smexpr); 7798 BLOCK_FOR_INSN (XEXP (last, 0)) != bb; 7799 last = XEXP (last, 1)) 7800 continue; 7801 last = XEXP (last, 0); 7802 } 7803 else 7804 last = NEXT_INSN (BB_END (bb)); 7805 7806 for (insn = BB_HEAD (bb); insn != last; insn = NEXT_INSN (insn)) 7807 if (INSN_P (insn)) 7808 { 7809 note = find_reg_equal_equiv_note (insn); 7810 if (!note || !expr_equiv_p (XEXP (note, 0), mem)) 7811 continue; 7812 7813 if (gcse_file) 7814 fprintf (gcse_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n", 7815 INSN_UID (insn)); 7816 remove_note (insn, note); 7817 } 7818 act = act->succ_next; 7819 if (bb->succ) 7820 { 7821 if (act) 7822 stack[stack_top++] = act; 7823 act = bb->succ; 7824 } 7825 } 7826} 7827 7828/* This routine will replace a store with a SET to a specified register. */ 7829 7830static void 7831replace_store_insn (rtx reg, rtx del, basic_block bb, struct ls_expr *smexpr) 7832{ 7833 rtx insn, mem, note, set, ptr, pair; 7834 7835 mem = smexpr->pattern; 7836 insn = gen_move_insn (reg, SET_SRC (single_set (del))); 7837 insn = emit_insn_after (insn, del); 7838 7839 if (gcse_file) 7840 { 7841 fprintf (gcse_file, 7842 "STORE_MOTION delete insn in BB %d:\n ", bb->index); 7843 print_inline_rtx (gcse_file, del, 6); 7844 fprintf (gcse_file, "\nSTORE MOTION replaced with insn:\n "); 7845 print_inline_rtx (gcse_file, insn, 6); 7846 fprintf (gcse_file, "\n"); 7847 } 7848 7849 for (ptr = ANTIC_STORE_LIST (smexpr); ptr; ptr = XEXP (ptr, 1)) 7850 if (XEXP (ptr, 0) == del) 7851 { 7852 XEXP (ptr, 0) = insn; 7853 break; 7854 } 7855 7856 /* Move the notes from the deleted insn to its replacement, and patch 7857 up the LIBCALL notes. */ 7858 REG_NOTES (insn) = REG_NOTES (del); 7859 7860 note = find_reg_note (insn, REG_RETVAL, NULL_RTX); 7861 if (note) 7862 { 7863 pair = XEXP (note, 0); 7864 note = find_reg_note (pair, REG_LIBCALL, NULL_RTX); 7865 XEXP (note, 0) = insn; 7866 } 7867 note = find_reg_note (insn, REG_LIBCALL, NULL_RTX); 7868 if (note) 7869 { 7870 pair = XEXP (note, 0); 7871 note = find_reg_note (pair, REG_RETVAL, NULL_RTX); 7872 XEXP (note, 0) = insn; 7873 } 7874 7875 delete_insn (del); 7876 7877 /* Now we must handle REG_EQUAL notes whose contents is equal to the mem; 7878 they are no longer accurate provided that they are reached by this 7879 definition, so drop them. */ 7880 for (; insn != NEXT_INSN (BB_END (bb)); insn = NEXT_INSN (insn)) 7881 if (INSN_P (insn)) 7882 { 7883 set = single_set (insn); 7884 if (!set) 7885 continue; 7886 if (expr_equiv_p (SET_DEST (set), mem)) 7887 return; 7888 note = find_reg_equal_equiv_note (insn); 7889 if (!note || !expr_equiv_p (XEXP (note, 0), mem)) 7890 continue; 7891 7892 if (gcse_file) 7893 fprintf (gcse_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n", 7894 INSN_UID (insn)); 7895 remove_note (insn, note); 7896 } 7897 remove_reachable_equiv_notes (bb, smexpr); 7898} 7899 7900 7901/* Delete a store, but copy the value that would have been stored into 7902 the reaching_reg for later storing. */ 7903 7904static void 7905delete_store (struct ls_expr * expr, basic_block bb) 7906{ 7907 rtx reg, i, del; 7908 7909 if (expr->reaching_reg == NULL_RTX) 7910 expr->reaching_reg = gen_reg_rtx (GET_MODE (expr->pattern)); 7911 7912 reg = expr->reaching_reg; 7913 7914 for (i = AVAIL_STORE_LIST (expr); i; i = XEXP (i, 1)) 7915 { 7916 del = XEXP (i, 0); 7917 if (BLOCK_FOR_INSN (del) == bb) 7918 { 7919 /* We know there is only one since we deleted redundant 7920 ones during the available computation. */ 7921 replace_store_insn (reg, del, bb, expr); 7922 break; 7923 } 7924 } 7925} 7926 7927/* Free memory used by store motion. */ 7928 7929static void 7930free_store_memory (void) 7931{ 7932 free_ldst_mems (); 7933 7934 if (ae_gen) 7935 sbitmap_vector_free (ae_gen); 7936 if (ae_kill) 7937 sbitmap_vector_free (ae_kill); 7938 if (transp) 7939 sbitmap_vector_free (transp); 7940 if (st_antloc) 7941 sbitmap_vector_free (st_antloc); 7942 if (pre_insert_map) 7943 sbitmap_vector_free (pre_insert_map); 7944 if (pre_delete_map) 7945 sbitmap_vector_free (pre_delete_map); 7946 if (reg_set_in_block) 7947 sbitmap_vector_free (reg_set_in_block); 7948 7949 ae_gen = ae_kill = transp = st_antloc = NULL; 7950 pre_insert_map = pre_delete_map = reg_set_in_block = NULL; 7951} 7952 7953/* Perform store motion. Much like gcse, except we move expressions the 7954 other way by looking at the flowgraph in reverse. */ 7955 7956static void 7957store_motion (void) 7958{ 7959 basic_block bb; 7960 int x; 7961 struct ls_expr * ptr; 7962 int update_flow = 0; 7963 7964 if (gcse_file) 7965 { 7966 fprintf (gcse_file, "before store motion\n"); 7967 print_rtl (gcse_file, get_insns ()); 7968 } 7969 7970 init_alias_analysis (); 7971 7972 /* Find all the available and anticipatable stores. */ 7973 num_stores = compute_store_table (); 7974 if (num_stores == 0) 7975 { 7976 sbitmap_vector_free (reg_set_in_block); 7977 end_alias_analysis (); 7978 return; 7979 } 7980 7981 /* Now compute kill & transp vectors. */ 7982 build_store_vectors (); 7983 add_noreturn_fake_exit_edges (); 7984 connect_infinite_loops_to_exit (); 7985 7986 edge_list = pre_edge_rev_lcm (gcse_file, num_stores, transp, ae_gen, 7987 st_antloc, ae_kill, &pre_insert_map, 7988 &pre_delete_map); 7989 7990 /* Now we want to insert the new stores which are going to be needed. */ 7991 for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr)) 7992 { 7993 FOR_EACH_BB (bb) 7994 if (TEST_BIT (pre_delete_map[bb->index], ptr->index)) 7995 delete_store (ptr, bb); 7996 7997 for (x = 0; x < NUM_EDGES (edge_list); x++) 7998 if (TEST_BIT (pre_insert_map[x], ptr->index)) 7999 update_flow |= insert_store (ptr, INDEX_EDGE (edge_list, x)); 8000 } 8001 8002 if (update_flow) 8003 commit_edge_insertions (); 8004 8005 free_store_memory (); 8006 free_edge_list (edge_list); 8007 remove_fake_edges (); 8008 end_alias_analysis (); 8009} 8010 8011 8012/* Entry point for jump bypassing optimization pass. */ 8013 8014int 8015bypass_jumps (FILE *file) 8016{ 8017 int changed; 8018 8019 /* We do not construct an accurate cfg in functions which call 8020 setjmp, so just punt to be safe. */ 8021 if (current_function_calls_setjmp) 8022 return 0; 8023 8024 /* For calling dump_foo fns from gdb. */ 8025 debug_stderr = stderr; 8026 gcse_file = file; 8027 8028 /* Identify the basic block information for this function, including 8029 successors and predecessors. */ 8030 max_gcse_regno = max_reg_num (); 8031 8032 if (file) 8033 dump_flow_info (file); 8034 8035 /* Return if there's nothing to do, or it is too expensive. */ 8036 if (n_basic_blocks <= 1 || is_too_expensive (_ ("jump bypassing disabled"))) 8037 return 0; 8038 8039 gcc_obstack_init (&gcse_obstack); 8040 bytes_used = 0; 8041 8042 /* We need alias. */ 8043 init_alias_analysis (); 8044 8045 /* Record where pseudo-registers are set. This data is kept accurate 8046 during each pass. ??? We could also record hard-reg information here 8047 [since it's unchanging], however it is currently done during hash table 8048 computation. 8049 8050 It may be tempting to compute MEM set information here too, but MEM sets 8051 will be subject to code motion one day and thus we need to compute 8052 information about memory sets when we build the hash tables. */ 8053 8054 alloc_reg_set_mem (max_gcse_regno); 8055 compute_sets (get_insns ()); 8056 8057 max_gcse_regno = max_reg_num (); 8058 alloc_gcse_mem (get_insns ()); 8059 changed = one_cprop_pass (1, 1, 1); 8060 free_gcse_mem (); 8061 8062 if (file) 8063 { 8064 fprintf (file, "BYPASS of %s: %d basic blocks, ", 8065 current_function_name (), n_basic_blocks); 8066 fprintf (file, "%d bytes\n\n", bytes_used); 8067 } 8068 8069 obstack_free (&gcse_obstack, NULL); 8070 free_reg_set_mem (); 8071 8072 /* We are finished with alias. */ 8073 end_alias_analysis (); 8074 allocate_reg_info (max_reg_num (), FALSE, FALSE); 8075 8076 return changed; 8077} 8078 8079/* Return true if the graph is too expensive to optimize. PASS is the 8080 optimization about to be performed. */ 8081 8082static bool 8083is_too_expensive (const char *pass) 8084{ 8085 /* Trying to perform global optimizations on flow graphs which have 8086 a high connectivity will take a long time and is unlikely to be 8087 particularly useful. 8088 8089 In normal circumstances a cfg should have about twice as many 8090 edges as blocks. But we do not want to punish small functions 8091 which have a couple switch statements. Rather than simply 8092 threshold the number of blocks, uses something with a more 8093 graceful degradation. */ 8094 if (n_edges > 20000 + n_basic_blocks * 4) 8095 { 8096 if (warn_disabled_optimization) 8097 warning ("%s: %d basic blocks and %d edges/basic block", 8098 pass, n_basic_blocks, n_edges / n_basic_blocks); 8099 8100 return true; 8101 } 8102 8103 /* If allocating memory for the cprop bitmap would take up too much 8104 storage it's better just to disable the optimization. */ 8105 if ((n_basic_blocks 8106 * SBITMAP_SET_SIZE (max_reg_num ()) 8107 * sizeof (SBITMAP_ELT_TYPE)) > MAX_GCSE_MEMORY) 8108 { 8109 if (warn_disabled_optimization) 8110 warning ("%s: %d basic blocks and %d registers", 8111 pass, n_basic_blocks, max_reg_num ()); 8112 8113 return true; 8114 } 8115 8116 return false; 8117} 8118 8119#include "gt-gcse.h" 8120