diff options
Diffstat (limited to 'contrib/gcc/gcse.c')
| -rw-r--r-- | contrib/gcc/gcse.c | 4704 |
1 files changed, 0 insertions, 4704 deletions
diff --git a/contrib/gcc/gcse.c b/contrib/gcc/gcse.c deleted file mode 100644 index cddd7ac63dfaf..0000000000000 --- a/contrib/gcc/gcse.c +++ /dev/null @@ -1,4704 +0,0 @@ -/* Global common subexpression elimination/Partial redundancy elimination - and global constant/copy propagation for GNU compiler. - Copyright (C) 1997, 1998, 1999 Free Software Foundation, Inc. - -This file is part of GNU CC. - -GNU CC is free software; you can redistribute it and/or modify -it under the terms of the GNU General Public License as published by -the Free Software Foundation; either version 2, or (at your option) -any later version. - -GNU CC is distributed in the hope that it will be useful, -but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -GNU General Public License for more details. - -You should have received a copy of the GNU General Public License -along with GNU CC; see the file COPYING. If not, write to -the Free Software Foundation, 59 Temple Place - Suite 330, -Boston, MA 02111-1307, USA. */ - -/* TODO - - reordering of memory allocation and freeing to be more space efficient - - do rough calc of how many regs are needed in each block, and a rough - calc of how many regs are available in each class and use that to - throttle back the code in cases where RTX_COST is minimal. - - dead store elimination - - a store to the same address as a load does not kill the load if the - source of the store is also the destination of the load. Handling this - allows more load motion, particularly out of loops. - - ability to realloc sbitmap vectors would allow one initial computation - of reg_set_in_block with only subsequent additions, rather than - recomputing it for each pass - -*/ - -/* References searched while implementing this. - - Compilers Principles, Techniques and Tools - Aho, Sethi, Ullman - Addison-Wesley, 1988 - - Global Optimization by Suppression of Partial Redundancies - E. Morel, C. Renvoise - communications of the acm, Vol. 22, Num. 2, Feb. 1979 - - A Portable Machine-Independent Global Optimizer - Design and Measurements - Frederick Chow - Stanford Ph.D. thesis, Dec. 1983 - - A Fast Algorithm for Code Movement Optimization - D.M. Dhamdhere - SIGPLAN Notices, Vol. 23, Num. 10, Oct. 1988 - - A Solution to a Problem with Morel and Renvoise's - Global Optimization by Suppression of Partial Redundancies - K-H Drechsler, M.P. Stadel - ACM TOPLAS, Vol. 10, Num. 4, Oct. 1988 - - Practical Adaptation of the Global Optimization - Algorithm of Morel and Renvoise - D.M. Dhamdhere - ACM TOPLAS, Vol. 13, Num. 2. Apr. 1991 - - Efficiently Computing Static Single Assignment Form and the Control - Dependence Graph - R. Cytron, J. Ferrante, B.K. Rosen, M.N. Wegman, and F.K. Zadeck - ACM TOPLAS, Vol. 13, Num. 4, Oct. 1991 - - Lazy Code Motion - J. Knoop, O. Ruthing, B. Steffen - ACM SIGPLAN Notices Vol. 27, Num. 7, Jul. 1992, '92 Conference on PLDI - - What's In a Region? Or Computing Control Dependence Regions in Near-Linear - Time for Reducible Flow Control - Thomas Ball - ACM Letters on Programming Languages and Systems, - Vol. 2, Num. 1-4, Mar-Dec 1993 - - An Efficient Representation for Sparse Sets - Preston Briggs, Linda Torczon - ACM Letters on Programming Languages and Systems, - Vol. 2, Num. 1-4, Mar-Dec 1993 - - A Variation of Knoop, Ruthing, and Steffen's Lazy Code Motion - K-H Drechsler, M.P. Stadel - ACM SIGPLAN Notices, Vol. 28, Num. 5, May 1993 - - Partial Dead Code Elimination - J. Knoop, O. Ruthing, B. Steffen - ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994 - - Effective Partial Redundancy Elimination - P. Briggs, K.D. Cooper - ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994 - - The Program Structure Tree: Computing Control Regions in Linear Time - R. Johnson, D. Pearson, K. Pingali - ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994 - - Optimal Code Motion: Theory and Practice - J. Knoop, O. Ruthing, B. Steffen - ACM TOPLAS, Vol. 16, Num. 4, Jul. 1994 - - The power of assignment motion - J. Knoop, O. Ruthing, B. Steffen - ACM SIGPLAN Notices Vol. 30, Num. 6, Jun. 1995, '95 Conference on PLDI - - Global code motion / global value numbering - C. Click - ACM SIGPLAN Notices Vol. 30, Num. 6, Jun. 1995, '95 Conference on PLDI - - Value Driven Redundancy Elimination - L.T. Simpson - Rice University Ph.D. thesis, Apr. 1996 - - Value Numbering - L.T. Simpson - Massively Scalar Compiler Project, Rice University, Sep. 1996 - - High Performance Compilers for Parallel Computing - Michael Wolfe - Addison-Wesley, 1996 - - Advanced Compiler Design and Implementation - Steven Muchnick - Morgan Kaufmann, 1997 - - People wishing to speed up the code here should read: - Elimination Algorithms for Data Flow Analysis - B.G. Ryder, M.C. Paull - ACM Computing Surveys, Vol. 18, Num. 3, Sep. 1986 - - How to Analyze Large Programs Efficiently and Informatively - D.M. Dhamdhere, B.K. Rosen, F.K. Zadeck - ACM SIGPLAN Notices Vol. 27, Num. 7, Jul. 1992, '92 Conference on PLDI - - People wishing to do something different can find various possibilities - in the above papers and elsewhere. -*/ - -#include "config.h" -#include "system.h" -#include "toplev.h" - -#include "rtl.h" -#include "regs.h" -#include "hard-reg-set.h" -#include "flags.h" -#include "real.h" -#include "insn-config.h" -#include "recog.h" -#include "basic-block.h" -#include "output.h" -#include "expr.h" - -#include "obstack.h" -#define obstack_chunk_alloc gmalloc -#define obstack_chunk_free free - -/* Maximum number of passes to perform. */ -#define MAX_PASSES 1 - -/* Propagate flow information through back edges and thus enable PRE's - moving loop invariant calculations out of loops. - - Originally this tended to create worse overall code, but several - improvements during the development of PRE seem to have made following - back edges generally a win. - - Note much of the loop invariant code motion done here would normally - be done by loop.c, which has more heuristics for when to move invariants - out of loops. At some point we might need to move some of those - heuristics into gcse.c. */ -#define FOLLOW_BACK_EDGES 1 - -/* We support GCSE via Partial Redundancy Elimination. PRE optimizations - are a superset of those done by GCSE. - - We perform the following steps: - - 1) Compute basic block information. - - 2) Compute table of places where registers are set. - - 3) Perform copy/constant propagation. - - 4) Perform global cse. - - 5) Perform another pass of copy/constant propagation. - - Two passes of copy/constant propagation are done because the first one - enables more GCSE and the second one helps to clean up the copies that - GCSE creates. This is needed more for PRE than for Classic because Classic - GCSE will try to use an existing register containing the common - subexpression rather than create a new one. This is harder to do for PRE - because of the code motion (which Classic GCSE doesn't do). - - Expressions we are interested in GCSE-ing are of the form - (set (pseudo-reg) (expression)). - Function want_to_gcse_p says what these are. - - PRE handles moving invariant expressions out of loops (by treating them as - partially redundant). - - Eventually it would be nice to replace cse.c/gcse.c with SSA (static single - assignment) based GVN (global value numbering). L. T. Simpson's paper - (Rice University) on value numbering is a useful reference for this. - - ********************** - - We used to support multiple passes but there are diminishing returns in - doing so. The first pass usually makes 90% of the changes that are doable. - A second pass can make a few more changes made possible by the first pass. - Experiments show any further passes don't make enough changes to justify - the expense. - - A study of spec92 using an unlimited number of passes: - [1 pass] = 1208 substitutions, [2] = 577, [3] = 202, [4] = 192, [5] = 83, - [6] = 34, [7] = 17, [8] = 9, [9] = 4, [10] = 4, [11] = 2, - [12] = 2, [13] = 1, [15] = 1, [16] = 2, [41] = 1 - - It was found doing copy propagation between each pass enables further - substitutions. - - PRE is quite expensive in complicated functions because the DFA can take - awhile to converge. Hence we only perform one pass. Macro MAX_PASSES can - be modified if one wants to experiment. - - ********************** - - The steps for PRE are: - - 1) Build the hash table of expressions we wish to GCSE (expr_hash_table). - - 2) Perform the data flow analysis for PRE. - - 3) Delete the redundant instructions - - 4) Insert the required copies [if any] that make the partially - redundant instructions fully redundant. - - 5) For other reaching expressions, insert an instruction to copy the value - to a newly created pseudo that will reach the redundant instruction. - - The deletion is done first so that when we do insertions we - know which pseudo reg to use. - - Various papers have argued that PRE DFA is expensive (O(n^2)) and others - argue it is not. The number of iterations for the algorithm to converge - is typically 2-4 so I don't view it as that expensive (relatively speaking). - - PRE GCSE depends heavily on the second CSE pass to clean up the copies - we create. To make an expression reach the place where it's redundant, - the result of the expression is copied to a new register, and the redundant - expression is deleted by replacing it with this new register. Classic GCSE - doesn't have this problem as much as it computes the reaching defs of - each register in each block and thus can try to use an existing register. - - ********************** - - A fair bit of simplicity is created by creating small functions for simple - tasks, even when the function is only called in one place. This may - measurably slow things down [or may not] by creating more function call - overhead than is necessary. The source is laid out so that it's trivial - to make the affected functions inline so that one can measure what speed - up, if any, can be achieved, and maybe later when things settle things can - be rearranged. - - Help stamp out big monolithic functions! */ - -/* GCSE global vars. */ - -/* -dG dump file. */ -static FILE *gcse_file; - -/* Note whether or not we should run jump optimization after gcse. We - want to do this for two cases. - - * If we changed any jumps via cprop. - - * If we added any labels via edge splitting. */ - -static int run_jump_opt_after_gcse; - -/* Element I is a list of I's predecessors/successors. */ -static int_list_ptr *s_preds; -static int_list_ptr *s_succs; - -/* Element I is the number of predecessors/successors of basic block I. */ -static int *num_preds; -static int *num_succs; - -/* Bitmaps are normally not included in debugging dumps. - However it's useful to be able to print them from GDB. - We could create special functions for this, but it's simpler to - just allow passing stderr to the dump_foo fns. Since stderr can - be a macro, we store a copy here. */ -static FILE *debug_stderr; - -/* An obstack for our working variables. */ -static struct obstack gcse_obstack; - -/* Non-zero for each mode that supports (set (reg) (reg)). - This is trivially true for integer and floating point values. - It may or may not be true for condition codes. */ -static char can_copy_p[(int) NUM_MACHINE_MODES]; - -/* Non-zero if can_copy_p has been initialized. */ -static int can_copy_init_p; - -/* Hash table of expressions. */ - -struct expr -{ - /* The expression (SET_SRC for expressions, PATTERN for assignments). */ - rtx expr; - /* Index in the available expression bitmaps. */ - int bitmap_index; - /* Next entry with the same hash. */ - struct expr *next_same_hash; - /* List of anticipatable occurrences in basic blocks in the function. - An "anticipatable occurrence" is one that is the first occurrence in the - basic block, the operands are not modified in the basic block prior - to the occurrence and the output is not used between the start of - the block and the occurrence. */ - struct occr *antic_occr; - /* List of available occurrence in basic blocks in the function. - An "available occurrence" is one that is the last occurrence in the - basic block and the operands are not modified by following statements in - the basic block [including this insn]. */ - struct occr *avail_occr; - /* Non-null if the computation is PRE redundant. - The value is the newly created pseudo-reg to record a copy of the - expression in all the places that reach the redundant copy. */ - rtx reaching_reg; -}; - -/* Occurrence of an expression. - There is one per basic block. If a pattern appears more than once the - last appearance is used [or first for anticipatable expressions]. */ - -struct occr -{ - /* Next occurrence of this expression. */ - struct occr *next; - /* The insn that computes the expression. */ - rtx insn; - /* Non-zero if this [anticipatable] occurrence has been deleted. */ - char deleted_p; - /* Non-zero if this [available] occurrence has been copied to - reaching_reg. */ - /* ??? This is mutually exclusive with deleted_p, so they could share - the same byte. */ - char copied_p; -}; - -/* Expression and copy propagation hash tables. - Each hash table is an array of buckets. - ??? It is known that if it were an array of entries, structure elements - `next_same_hash' and `bitmap_index' wouldn't be necessary. However, it is - not clear whether in the final analysis a sufficient amount of memory would - be saved as the size of the available expression bitmaps would be larger - [one could build a mapping table without holes afterwards though]. - Someday I'll perform the computation and figure it out. -*/ - -/* Total size of the expression hash table, in elements. */ -static int expr_hash_table_size; -/* The table itself. - This is an array of `expr_hash_table_size' elements. */ -static struct expr **expr_hash_table; - -/* Total size of the copy propagation hash table, in elements. */ -static int set_hash_table_size; -/* The table itself. - This is an array of `set_hash_table_size' elements. */ -static struct expr **set_hash_table; - -/* Mapping of uids to cuids. - Only real insns get cuids. */ -static int *uid_cuid; - -/* Highest UID in UID_CUID. */ -static int max_uid; - -/* Get the cuid of an insn. */ -#define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)]) - -/* Number of cuids. */ -static int max_cuid; - -/* Mapping of cuids to insns. */ -static rtx *cuid_insn; - -/* Get insn from cuid. */ -#define CUID_INSN(CUID) (cuid_insn[CUID]) - -/* Maximum register number in function prior to doing gcse + 1. - Registers created during this pass have regno >= max_gcse_regno. - This is named with "gcse" to not collide with global of same name. */ -static int max_gcse_regno; - -/* Maximum number of cse-able expressions found. */ -static int n_exprs; -/* Maximum number of assignments for copy propagation found. */ -static int n_sets; - -/* Table of registers that are modified. - For each register, each element is a list of places where the pseudo-reg - is set. - - For simplicity, GCSE is done on sets of pseudo-regs only. PRE GCSE only - requires knowledge of which blocks kill which regs [and thus could use - a bitmap instead of the lists `reg_set_table' uses]. - - `reg_set_table' and could be turned into an array of bitmaps - (num-bbs x num-regs) - [however perhaps it may be useful to keep the data as is]. - One advantage of recording things this way is that `reg_set_table' is - fairly sparse with respect to pseudo regs but for hard regs could be - fairly dense [relatively speaking]. - And recording sets of pseudo-regs in lists speeds - up functions like compute_transp since in the case of pseudo-regs we only - need to iterate over the number of times a pseudo-reg is set, not over the - number of basic blocks [clearly there is a bit of a slow down in the cases - where a pseudo is set more than once in a block, however it is believed - that the net effect is to speed things up]. This isn't done for hard-regs - because recording call-clobbered hard-regs in `reg_set_table' at each - function call can consume a fair bit of memory, and iterating over hard-regs - stored this way in compute_transp will be more expensive. */ - -typedef struct reg_set { - /* The next setting of this register. */ - struct reg_set *next; - /* The insn where it was set. */ - rtx insn; -} reg_set; -static reg_set **reg_set_table; -/* Size of `reg_set_table'. - The table starts out at max_gcse_regno + slop, and is enlarged as - necessary. */ -static int reg_set_table_size; -/* Amount to grow `reg_set_table' by when it's full. */ -#define REG_SET_TABLE_SLOP 100 - -/* Bitmap containing one bit for each register in the program. - Used when performing GCSE to track which registers have been set since - the start of the basic block. */ -static sbitmap reg_set_bitmap; - -/* For each block, a bitmap of registers set in the block. - This is used by expr_killed_p and compute_transp. - It is computed during hash table computation and not by compute_sets - as it includes registers added since the last pass (or between cprop and - gcse) and it's currently not easy to realloc sbitmap vectors. */ -static sbitmap *reg_set_in_block; - -/* For each block, non-zero if memory is set in that block. - This is computed during hash table computation and is used by - expr_killed_p and compute_transp. - ??? Handling of memory is very simple, we don't make any attempt - to optimize things (later). - ??? This can be computed by compute_sets since the information - doesn't change. */ -static char *mem_set_in_block; - -/* Various variables for statistics gathering. */ - -/* Memory used in a pass. - This isn't intended to be absolutely precise. Its intent is only - to keep an eye on memory usage. */ -static int bytes_used; -/* GCSE substitutions made. */ -static int gcse_subst_count; -/* Number of copy instructions created. */ -static int gcse_create_count; -/* Number of constants propagated. */ -static int const_prop_count; -/* Number of copys propagated. */ -static int copy_prop_count; - -extern char *current_function_name; -extern int current_function_calls_setjmp; - -/* These variables are used by classic GCSE. - Normally they'd be defined a bit later, but `rd_gen' needs to - be declared sooner. */ - -/* A bitmap of all ones for implementing the algorithm for available - expressions and reaching definitions. */ -/* ??? Available expression bitmaps have a different size than reaching - definition bitmaps. This should be the larger of the two, however, it - is not currently used for reaching definitions. */ -static sbitmap u_bitmap; - -/* Each block has a bitmap of each type. - The length of each blocks bitmap is: - - max_cuid - for reaching definitions - n_exprs - for available expressions - - Thus we view the bitmaps as 2 dimensional arrays. i.e. - rd_kill[block_num][cuid_num] - ae_kill[block_num][expr_num] -*/ - -/* For reaching defs */ -static sbitmap *rd_kill, *rd_gen, *reaching_defs, *rd_out; - -/* for available exprs */ -static sbitmap *ae_kill, *ae_gen, *ae_in, *ae_out; - - -static void compute_can_copy PROTO ((void)); - -static char *gmalloc PROTO ((unsigned int)); -static char *grealloc PROTO ((char *, unsigned int)); -static char *gcse_alloc PROTO ((unsigned long)); -static void alloc_gcse_mem PROTO ((rtx)); -static void free_gcse_mem PROTO ((void)); -static void alloc_reg_set_mem PROTO ((int)); -static void free_reg_set_mem PROTO ((void)); -static void record_one_set PROTO ((int, rtx)); -static void record_set_info PROTO ((rtx, rtx)); -static void compute_sets PROTO ((rtx)); - -static void hash_scan_insn PROTO ((rtx, int, int)); -static void hash_scan_set PROTO ((rtx, rtx, int)); -static void hash_scan_clobber PROTO ((rtx, rtx)); -static void hash_scan_call PROTO ((rtx, rtx)); -static int want_to_gcse_p PROTO ((rtx)); -static int oprs_unchanged_p PROTO ((rtx, rtx, int)); -static int oprs_anticipatable_p PROTO ((rtx, rtx)); -static int oprs_available_p PROTO ((rtx, rtx)); -static void insert_expr_in_table PROTO ((rtx, enum machine_mode, - rtx, int, int)); -static void insert_set_in_table PROTO ((rtx, rtx)); -static unsigned int hash_expr PROTO ((rtx, enum machine_mode, - int *, int)); -static unsigned int hash_expr_1 PROTO ((rtx, enum machine_mode, int *)); -static unsigned int hash_set PROTO ((int, int)); -static int expr_equiv_p PROTO ((rtx, rtx)); -static void record_last_reg_set_info PROTO ((rtx, int)); -static void record_last_mem_set_info PROTO ((rtx)); -static void record_last_set_info PROTO ((rtx, rtx)); -static void compute_hash_table PROTO ((int)); -static void alloc_set_hash_table PROTO ((int)); -static void free_set_hash_table PROTO ((void)); -static void compute_set_hash_table PROTO ((void)); -static void alloc_expr_hash_table PROTO ((int)); -static void free_expr_hash_table PROTO ((void)); -static void compute_expr_hash_table PROTO ((void)); -static void dump_hash_table PROTO ((FILE *, const char *, struct expr **, - int, int)); -static struct expr *lookup_expr PROTO ((rtx)); -static struct expr *lookup_set PROTO ((int, rtx)); -static struct expr *next_set PROTO ((int, struct expr *)); -static void reset_opr_set_tables PROTO ((void)); -static int oprs_not_set_p PROTO ((rtx, rtx)); -static void mark_call PROTO ((rtx)); -static void mark_set PROTO ((rtx, rtx)); -static void mark_clobber PROTO ((rtx, rtx)); -static void mark_oprs_set PROTO ((rtx)); - -static void alloc_cprop_mem PROTO ((int, int)); -static void free_cprop_mem PROTO ((void)); -static void compute_transp PROTO ((rtx, int, sbitmap *, int)); -static void compute_transpout PROTO ((void)); -static void compute_local_properties PROTO ((sbitmap *, sbitmap *, - sbitmap *, int)); -static void compute_cprop_avinout PROTO ((void)); -static void compute_cprop_data PROTO ((void)); -static void find_used_regs PROTO ((rtx)); -static int try_replace_reg PROTO ((rtx, rtx, rtx)); -static struct expr *find_avail_set PROTO ((int, rtx)); -static int cprop_insn PROTO ((rtx, int)); -static int cprop PROTO ((int)); -static int one_cprop_pass PROTO ((int, int)); - -static void alloc_pre_mem PROTO ((int, int)); -static void free_pre_mem PROTO ((void)); -static void compute_pre_data PROTO ((void)); -static int pre_expr_reaches_here_p PROTO ((int, struct expr *, - int, int, char *)); -static void insert_insn_end_bb PROTO ((struct expr *, int, int)); -static void pre_insert PROTO ((struct expr **)); -static void pre_insert_copy_insn PROTO ((struct expr *, rtx)); -static void pre_insert_copies PROTO ((void)); -static int pre_delete PROTO ((void)); -static int pre_gcse PROTO ((void)); -static int one_pre_gcse_pass PROTO ((int)); - -static void add_label_notes PROTO ((rtx, rtx)); - -static void alloc_rd_mem PROTO ((int, int)); -static void free_rd_mem PROTO ((void)); -static void handle_rd_kill_set PROTO ((rtx, int, int)); -static void compute_kill_rd PROTO ((void)); -static void compute_rd PROTO ((void)); -static void alloc_avail_expr_mem PROTO ((int, int)); -static void free_avail_expr_mem PROTO ((void)); -static void compute_ae_gen PROTO ((void)); -static int expr_killed_p PROTO ((rtx, int)); -static void compute_ae_kill PROTO ((void)); -static void compute_available PROTO ((void)); -static int expr_reaches_here_p PROTO ((struct occr *, struct expr *, - int, int, char *)); -static rtx computing_insn PROTO ((struct expr *, rtx)); -static int def_reaches_here_p PROTO ((rtx, rtx)); -static int can_disregard_other_sets PROTO ((struct reg_set **, rtx, int)); -static int handle_avail_expr PROTO ((rtx, struct expr *)); -static int classic_gcse PROTO ((void)); -static int one_classic_gcse_pass PROTO ((int)); - - -/* Entry point for global common subexpression elimination. - F is the first instruction in the function. */ - -int -gcse_main (f, file) - rtx f; - FILE *file; -{ - int changed, pass; - /* Bytes used at start of pass. */ - int initial_bytes_used; - /* Maximum number of bytes used by a pass. */ - int max_pass_bytes; - /* Point to release obstack data from for each pass. */ - char *gcse_obstack_bottom; - - /* We do not construct an accurate cfg in functions which call - setjmp, so just punt to be safe. */ - if (current_function_calls_setjmp) - return 0; - - /* Assume that we do not need to run jump optimizations after gcse. */ - run_jump_opt_after_gcse = 0; - - /* For calling dump_foo fns from gdb. */ - debug_stderr = stderr; - gcse_file = file; - - /* Identify the basic block information for this function, including - successors and predecessors. */ - max_gcse_regno = max_reg_num (); - find_basic_blocks (f, max_gcse_regno, file, 1); - - /* Return if there's nothing to do. */ - if (n_basic_blocks <= 1) - { - /* Free storage allocated by find_basic_blocks. */ - free_basic_block_vars (0); - return 0; - } - - /* See what modes support reg/reg copy operations. */ - if (! can_copy_init_p) - { - compute_can_copy (); - can_copy_init_p = 1; - } - - gcc_obstack_init (&gcse_obstack); - - /* Allocate and compute predecessors/successors. */ - - s_preds = (int_list_ptr *) alloca (n_basic_blocks * sizeof (int_list_ptr)); - s_succs = (int_list_ptr *) alloca (n_basic_blocks * sizeof (int_list_ptr)); - num_preds = (int *) alloca (n_basic_blocks * sizeof (int)); - num_succs = (int *) alloca (n_basic_blocks * sizeof (int)); - bytes_used = 4 * n_basic_blocks * sizeof (int_list_ptr); - compute_preds_succs (s_preds, s_succs, num_preds, num_succs); - - if (file) - dump_bb_data (file, s_preds, s_succs, 0); - - /* Record where pseudo-registers are set. - This data is kept accurate during each pass. - ??? We could also record hard-reg information here - [since it's unchanging], however it is currently done during - hash table computation. - - It may be tempting to compute MEM set information here too, but MEM - sets will be subject to code motion one day and thus we need to compute - information about memory sets when we build the hash tables. */ - - alloc_reg_set_mem (max_gcse_regno); - compute_sets (f); - - pass = 0; - initial_bytes_used = bytes_used; - max_pass_bytes = 0; - gcse_obstack_bottom = gcse_alloc (1); - changed = 1; - while (changed && pass < MAX_PASSES) - { - changed = 0; - if (file) - fprintf (file, "GCSE pass %d\n\n", pass + 1); - - /* Initialize bytes_used to the space for the pred/succ lists, - and the reg_set_table data. */ - bytes_used = initial_bytes_used; - - /* Each pass may create new registers, so recalculate each time. */ - max_gcse_regno = max_reg_num (); - - alloc_gcse_mem (f); - - /* Don't allow constant propagation to modify jumps - during this pass. */ - changed = one_cprop_pass (pass + 1, 0); - - if (optimize_size) - changed |= one_classic_gcse_pass (pass + 1); - else - changed |= one_pre_gcse_pass (pass + 1); - - if (max_pass_bytes < bytes_used) - max_pass_bytes = bytes_used; - - free_gcse_mem (); - - if (file) - { - fprintf (file, "\n"); - fflush (file); - } - obstack_free (&gcse_obstack, gcse_obstack_bottom); - pass++; - } - - /* Do one last pass of copy propagation, including cprop into - conditional jumps. */ - - max_gcse_regno = max_reg_num (); - alloc_gcse_mem (f); - /* This time, go ahead and allow cprop to alter jumps. */ - one_cprop_pass (pass + 1, 1); - free_gcse_mem (); - - if (file) - { - fprintf (file, "GCSE of %s: %d basic blocks, ", - current_function_name, n_basic_blocks); - fprintf (file, "%d pass%s, %d bytes\n\n", - pass, pass > 1 ? "es" : "", max_pass_bytes); - } - - /* Free our obstack. */ - obstack_free (&gcse_obstack, NULL_PTR); - /* Free reg_set_table. */ - free_reg_set_mem (); - /* Free storage used to record predecessor/successor data. */ - free_bb_mem (); - /* Free storage allocated by find_basic_blocks. */ - free_basic_block_vars (0); - return run_jump_opt_after_gcse; -} - -/* Misc. utilities. */ - -/* Compute which modes support reg/reg copy operations. */ - -static void -compute_can_copy () -{ - int i; -#ifndef AVOID_CCMODE_COPIES - rtx reg,insn; -#endif - char *free_point = (char *) oballoc (1); - - bzero (can_copy_p, NUM_MACHINE_MODES); - - start_sequence (); - for (i = 0; i < NUM_MACHINE_MODES; i++) - { - switch (GET_MODE_CLASS (i)) - { - case MODE_CC : -#ifdef AVOID_CCMODE_COPIES - can_copy_p[i] = 0; -#else - reg = gen_rtx_REG ((enum machine_mode) i, LAST_VIRTUAL_REGISTER + 1); - insn = emit_insn (gen_rtx_SET (VOIDmode, reg, reg)); - if (recog (PATTERN (insn), insn, NULL_PTR) >= 0) - can_copy_p[i] = 1; -#endif - break; - default : - can_copy_p[i] = 1; - break; - } - } - end_sequence (); - - /* Free the objects we just allocated. */ - obfree (free_point); -} - -/* Cover function to xmalloc to record bytes allocated. */ - -static char * -gmalloc (size) - unsigned int size; -{ - bytes_used += size; - return xmalloc (size); -} - -/* Cover function to xrealloc. - We don't record the additional size since we don't know it. - It won't affect memory usage stats much anyway. */ - -static char * -grealloc (ptr, size) - char *ptr; - unsigned int size; -{ - return xrealloc (ptr, size); -} - -/* Cover function to obstack_alloc. - We don't need to record the bytes allocated here since - obstack_chunk_alloc is set to gmalloc. */ - -static char * -gcse_alloc (size) - unsigned long size; -{ - return (char *) obstack_alloc (&gcse_obstack, size); -} - -/* Allocate memory for the cuid mapping array, - and reg/memory set tracking tables. - - This is called at the start of each pass. */ - -static void -alloc_gcse_mem (f) - rtx f; -{ - int i,n; - rtx insn; - - /* Find the largest UID and create a mapping from UIDs to CUIDs. - CUIDs are like UIDs except they increase monotonically, have no gaps, - and only apply to real insns. */ - - max_uid = get_max_uid (); - n = (max_uid + 1) * sizeof (int); - uid_cuid = (int *) gmalloc (n); - bzero ((char *) uid_cuid, n); - for (insn = f, i = 0; insn; insn = NEXT_INSN (insn)) - { - if (GET_RTX_CLASS (GET_CODE (insn)) == 'i') - INSN_CUID (insn) = i++; - else - INSN_CUID (insn) = i; - } - - /* Create a table mapping cuids to insns. */ - - max_cuid = i; - n = (max_cuid + 1) * sizeof (rtx); - cuid_insn = (rtx *) gmalloc (n); - bzero ((char *) cuid_insn, n); - for (insn = f, i = 0; insn; insn = NEXT_INSN (insn)) - { - if (GET_RTX_CLASS (GET_CODE (insn)) == 'i') - { - CUID_INSN (i) = insn; - i++; - } - } - - /* Allocate vars to track sets of regs. */ - - reg_set_bitmap = (sbitmap) sbitmap_alloc (max_gcse_regno); - - /* Allocate vars to track sets of regs, memory per block. */ - - reg_set_in_block = (sbitmap *) sbitmap_vector_alloc (n_basic_blocks, - max_gcse_regno); - mem_set_in_block = (char *) gmalloc (n_basic_blocks); -} - -/* Free memory allocated by alloc_gcse_mem. */ - -static void -free_gcse_mem () -{ - free (uid_cuid); - free (cuid_insn); - - free (reg_set_bitmap); - - free (reg_set_in_block); - free (mem_set_in_block); -} - - -/* Compute the local properties of each recorded expression. - Local properties are those that are defined by the block, irrespective - of other blocks. - - An expression is transparent in a block if its operands are not modified - in the block. - - An expression is computed (locally available) in a block if it is computed - at least once and expression would contain the same value if the - computation was moved to the end of the block. - - An expression is locally anticipatable in a block if it is computed at - least once and expression would contain the same value if the computation - was moved to the beginning of the block. - - We call this routine for cprop, pre and code hoisting. They all - compute basically the same information and thus can easily share - this code. - - TRANSP, COMP, and ANTLOC are destination sbitmaps for recording - local properties. If NULL, then it is not necessary to compute - or record that particular property. - - SETP controls which hash table to look at. If zero, this routine - looks at the expr hash table; if nonzero this routine looks at - the set hash table. Additionally, TRANSP is computed as ~TRANSP, - since this is really cprop's ABSALTERED. */ - -static void -compute_local_properties (transp, comp, antloc, setp) - sbitmap *transp; - sbitmap *comp; - sbitmap *antloc; - int setp; -{ - int i, hash_table_size; - struct expr **hash_table; - - /* Initialize any bitmaps that were passed in. */ - if (transp) - { - if (setp) - sbitmap_vector_zero (transp, n_basic_blocks); - else - sbitmap_vector_ones (transp, n_basic_blocks); - } - if (comp) - sbitmap_vector_zero (comp, n_basic_blocks); - if (antloc) - sbitmap_vector_zero (antloc, n_basic_blocks); - - /* We use the same code for cprop, pre and hoisting. For cprop - we care about the set hash table, for pre and hoisting we - care about the expr hash table. */ - hash_table_size = setp ? set_hash_table_size : expr_hash_table_size; - hash_table = setp ? set_hash_table : expr_hash_table; - - for (i = 0; i < hash_table_size; i++) - { - struct expr *expr; - - for (expr = hash_table[i]; expr != NULL; expr = expr->next_same_hash) - { - struct occr *occr; - int indx = expr->bitmap_index; - - /* The expression is transparent in this block if it is not killed. - We start by assuming all are transparent [none are killed], and - then reset the bits for those that are. */ - - if (transp) - compute_transp (expr->expr, indx, transp, setp); - - /* The occurrences recorded in antic_occr are exactly those that - we want to set to non-zero in ANTLOC. */ - - if (antloc) - { - for (occr = expr->antic_occr; occr != NULL; occr = occr->next) - { - int bb = BLOCK_NUM (occr->insn); - SET_BIT (antloc[bb], indx); - - /* While we're scanning the table, this is a good place to - initialize this. */ - occr->deleted_p = 0; - } - } - - /* The occurrences recorded in avail_occr are exactly those that - we want to set to non-zero in COMP. */ - if (comp) - { - - for (occr = expr->avail_occr; occr != NULL; occr = occr->next) - { - int bb = BLOCK_NUM (occr->insn); - SET_BIT (comp[bb], indx); - - /* While we're scanning the table, this is a good place to - initialize this. */ - occr->copied_p = 0; - } - } - - /* While we're scanning the table, this is a good place to - initialize this. */ - expr->reaching_reg = 0; - } - } -} - - -/* Register set information. - - `reg_set_table' records where each register is set or otherwise - modified. */ - -static struct obstack reg_set_obstack; - -static void -alloc_reg_set_mem (n_regs) - int n_regs; -{ - int n; - - reg_set_table_size = n_regs + REG_SET_TABLE_SLOP; - n = reg_set_table_size * sizeof (struct reg_set *); - reg_set_table = (struct reg_set **) gmalloc (n); - bzero ((char *) reg_set_table, n); - - gcc_obstack_init (®_set_obstack); -} - -static void -free_reg_set_mem () -{ - free (reg_set_table); - obstack_free (®_set_obstack, NULL_PTR); -} - -/* Record REGNO in the reg_set table. */ - -static void -record_one_set (regno, insn) - int regno; - rtx insn; -{ - /* allocate a new reg_set element and link it onto the list */ - struct reg_set *new_reg_info, *reg_info_ptr1, *reg_info_ptr2; - - /* If the table isn't big enough, enlarge it. */ - if (regno >= reg_set_table_size) - { - int new_size = regno + REG_SET_TABLE_SLOP; - reg_set_table = (struct reg_set **) - grealloc ((char *) reg_set_table, - new_size * sizeof (struct reg_set *)); - bzero ((char *) (reg_set_table + reg_set_table_size), - (new_size - reg_set_table_size) * sizeof (struct reg_set *)); - reg_set_table_size = new_size; - } - - new_reg_info = (struct reg_set *) obstack_alloc (®_set_obstack, - sizeof (struct reg_set)); - bytes_used += sizeof (struct reg_set); - new_reg_info->insn = insn; - new_reg_info->next = NULL; - if (reg_set_table[regno] == NULL) - reg_set_table[regno] = new_reg_info; - else - { - reg_info_ptr1 = reg_info_ptr2 = reg_set_table[regno]; - /* ??? One could keep a "last" pointer to speed this up. */ - while (reg_info_ptr1 != NULL) - { - reg_info_ptr2 = reg_info_ptr1; - reg_info_ptr1 = reg_info_ptr1->next; - } - reg_info_ptr2->next = new_reg_info; - } -} - -/* For communication between next two functions (via note_stores). */ -static rtx record_set_insn; - -/* Called from compute_sets via note_stores to handle one - SET or CLOBBER in an insn. */ - -static void -record_set_info (dest, setter) - rtx dest, setter ATTRIBUTE_UNUSED; -{ - if (GET_CODE (dest) == SUBREG) - dest = SUBREG_REG (dest); - - if (GET_CODE (dest) == REG) - { - if (REGNO (dest) >= FIRST_PSEUDO_REGISTER) - record_one_set (REGNO (dest), record_set_insn); - } -} - -/* Scan the function and record each set of each pseudo-register. - - This is called once, at the start of the gcse pass. - See the comments for `reg_set_table' for further docs. */ - -static void -compute_sets (f) - rtx f; -{ - rtx insn = f; - - while (insn) - { - if (GET_RTX_CLASS (GET_CODE (insn)) == 'i') - { - record_set_insn = insn; - note_stores (PATTERN (insn), record_set_info); - } - insn = NEXT_INSN (insn); - } -} - -/* Hash table support. */ - -#define NEVER_SET -1 - -/* For each register, the cuid of the first/last insn in the block to set it, - or -1 if not set. */ -static int *reg_first_set; -static int *reg_last_set; - -/* While computing "first/last set" info, this is the CUID of first/last insn - to set memory or -1 if not set. `mem_last_set' is also used when - performing GCSE to record whether memory has been set since the beginning - of the block. - Note that handling of memory is very simple, we don't make any attempt - to optimize things (later). */ -static int mem_first_set; -static int mem_last_set; - -/* Perform a quick check whether X, the source of a set, is something - we want to consider for GCSE. */ - -static int -want_to_gcse_p (x) - rtx x; -{ - enum rtx_code code = GET_CODE (x); - - switch (code) - { - case REG: - case SUBREG: - case CONST_INT: - case CONST_DOUBLE: - case CALL: - return 0; - - default: - break; - } - - return 1; -} - -/* Return non-zero if the operands of expression X are unchanged from the - start of INSN's basic block up to but not including INSN (if AVAIL_P == 0), - or from INSN to the end of INSN's basic block (if AVAIL_P != 0). */ - -static int -oprs_unchanged_p (x, insn, avail_p) - rtx x, insn; - int avail_p; -{ - int i; - enum rtx_code code; - char *fmt; - - /* repeat is used to turn tail-recursion into iteration. */ - repeat: - - if (x == 0) - return 1; - - code = GET_CODE (x); - switch (code) - { - case REG: - if (avail_p) - return (reg_last_set[REGNO (x)] == NEVER_SET - || reg_last_set[REGNO (x)] < INSN_CUID (insn)); - else - return (reg_first_set[REGNO (x)] == NEVER_SET - || reg_first_set[REGNO (x)] >= INSN_CUID (insn)); - - case MEM: - if (avail_p) - { - if (mem_last_set != NEVER_SET - && mem_last_set >= INSN_CUID (insn)) - return 0; - } - else - { - if (mem_first_set != NEVER_SET - && mem_first_set < INSN_CUID (insn)) - return 0; - } - x = XEXP (x, 0); - goto repeat; - - case PRE_DEC: - case PRE_INC: - case POST_DEC: - case POST_INC: - return 0; - - case PC: - case CC0: /*FIXME*/ - case CONST: - case CONST_INT: - case CONST_DOUBLE: - case SYMBOL_REF: - case LABEL_REF: - case ADDR_VEC: - case ADDR_DIFF_VEC: - return 1; - - default: - break; - } - - i = GET_RTX_LENGTH (code) - 1; - fmt = GET_RTX_FORMAT (code); - for (; i >= 0; i--) - { - if (fmt[i] == 'e') - { - rtx tem = XEXP (x, i); - - /* If we are about to do the last recursive call - needed at this level, change it into iteration. - This function is called enough to be worth it. */ - if (i == 0) - { - x = tem; - goto repeat; - } - if (! oprs_unchanged_p (tem, insn, avail_p)) - return 0; - } - else if (fmt[i] == 'E') - { - int j; - for (j = 0; j < XVECLEN (x, i); j++) - { - if (! oprs_unchanged_p (XVECEXP (x, i, j), insn, avail_p)) - return 0; - } - } - } - - return 1; -} - -/* Return non-zero if the operands of expression X are unchanged from - the start of INSN's basic block up to but not including INSN. */ - -static int -oprs_anticipatable_p (x, insn) - rtx x, insn; -{ - return oprs_unchanged_p (x, insn, 0); -} - -/* Return non-zero if the operands of expression X are unchanged from - INSN to the end of INSN's basic block. */ - -static int -oprs_available_p (x, insn) - rtx x, insn; -{ - return oprs_unchanged_p (x, insn, 1); -} - -/* Hash expression X. - MODE is only used if X is a CONST_INT. - A boolean indicating if a volatile operand is found or if the expression - contains something we don't want to insert in the table is stored in - DO_NOT_RECORD_P. - - ??? One might want to merge this with canon_hash. Later. */ - -static unsigned int -hash_expr (x, mode, do_not_record_p, hash_table_size) - rtx x; - enum machine_mode mode; - int *do_not_record_p; - int hash_table_size; -{ - unsigned int hash; - - *do_not_record_p = 0; - - hash = hash_expr_1 (x, mode, do_not_record_p); - return hash % hash_table_size; -} - -/* Subroutine of hash_expr to do the actual work. */ - -static unsigned int -hash_expr_1 (x, mode, do_not_record_p) - rtx x; - enum machine_mode mode; - int *do_not_record_p; -{ - int i, j; - unsigned hash = 0; - enum rtx_code code; - char *fmt; - - /* repeat is used to turn tail-recursion into iteration. */ - repeat: - - if (x == 0) - return hash; - - code = GET_CODE (x); - switch (code) - { - case REG: - { - register int regno = REGNO (x); - hash += ((unsigned) REG << 7) + regno; - return hash; - } - - case CONST_INT: - { - unsigned HOST_WIDE_INT tem = INTVAL (x); - hash += ((unsigned) CONST_INT << 7) + (unsigned) mode + tem; - return hash; - } - - case CONST_DOUBLE: - /* This is like the general case, except that it only counts - the integers representing the constant. */ - hash += (unsigned) code + (unsigned) GET_MODE (x); - if (GET_MODE (x) != VOIDmode) - for (i = 2; i < GET_RTX_LENGTH (CONST_DOUBLE); i++) - { - unsigned tem = XINT (x, i); - hash += tem; - } - else - hash += ((unsigned) CONST_DOUBLE_LOW (x) - + (unsigned) CONST_DOUBLE_HIGH (x)); - return hash; - - /* Assume there is only one rtx object for any given label. */ - case LABEL_REF: - /* We don't hash on the address of the CODE_LABEL to avoid bootstrap - differences and differences between each stage's debugging dumps. */ - hash += ((unsigned) LABEL_REF << 7) + CODE_LABEL_NUMBER (XEXP (x, 0)); - return hash; - - case SYMBOL_REF: - { - /* Don't hash on the symbol's address to avoid bootstrap differences. - Different hash values may cause expressions to be recorded in - different orders and thus different registers to be used in the - final assembler. This also avoids differences in the dump files - between various stages. */ - unsigned int h = 0; - unsigned char *p = (unsigned char *) XSTR (x, 0); - while (*p) - h += (h << 7) + *p++; /* ??? revisit */ - hash += ((unsigned) SYMBOL_REF << 7) + h; - return hash; - } - - case MEM: - if (MEM_VOLATILE_P (x)) - { - *do_not_record_p = 1; - return 0; - } - hash += (unsigned) MEM; - hash += MEM_ALIAS_SET (x); - x = XEXP (x, 0); - goto repeat; - - case PRE_DEC: - case PRE_INC: - case POST_DEC: - case POST_INC: - case PC: - case CC0: - case CALL: - case UNSPEC_VOLATILE: - *do_not_record_p = 1; - return 0; - - case ASM_OPERANDS: - if (MEM_VOLATILE_P (x)) - { - *do_not_record_p = 1; - return 0; - } - - default: - break; - } - - i = GET_RTX_LENGTH (code) - 1; - hash += (unsigned) code + (unsigned) GET_MODE (x); - fmt = GET_RTX_FORMAT (code); - for (; i >= 0; i--) - { - if (fmt[i] == 'e') - { - rtx tem = XEXP (x, i); - - /* If we are about to do the last recursive call - needed at this level, change it into iteration. - This function is called enough to be worth it. */ - if (i == 0) - { - x = tem; - goto repeat; - } - hash += hash_expr_1 (tem, 0, do_not_record_p); - if (*do_not_record_p) - return 0; - } - else if (fmt[i] == 'E') - for (j = 0; j < XVECLEN (x, i); j++) - { - hash += hash_expr_1 (XVECEXP (x, i, j), 0, do_not_record_p); - if (*do_not_record_p) - return 0; - } - else if (fmt[i] == 's') - { - register unsigned char *p = (unsigned char *) XSTR (x, i); - if (p) - while (*p) - hash += *p++; - } - else if (fmt[i] == 'i') - { - register unsigned tem = XINT (x, i); - hash += tem; - } - else - abort (); - } - - return hash; -} - -/* Hash a set of register REGNO. - - Sets are hashed on the register that is set. - This simplifies the PRE copy propagation code. - - ??? May need to make things more elaborate. Later, as necessary. */ - -static unsigned int -hash_set (regno, hash_table_size) - int regno; - int hash_table_size; -{ - unsigned int hash; - - hash = regno; - return hash % hash_table_size; -} - -/* Return non-zero if exp1 is equivalent to exp2. - ??? Borrowed from cse.c. Might want to remerge with cse.c. Later. */ - -static int -expr_equiv_p (x, y) - rtx x, y; -{ - register int i, j; - register enum rtx_code code; - register char *fmt; - - if (x == y) - return 1; - if (x == 0 || y == 0) - return x == y; - - code = GET_CODE (x); - if (code != GET_CODE (y)) - return 0; - - /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. */ - if (GET_MODE (x) != GET_MODE (y)) - return 0; - - switch (code) - { - case PC: - case CC0: - return x == y; - - case CONST_INT: - return INTVAL (x) == INTVAL (y); - - case LABEL_REF: - return XEXP (x, 0) == XEXP (y, 0); - - case SYMBOL_REF: - return XSTR (x, 0) == XSTR (y, 0); - - case REG: - return REGNO (x) == REGNO (y); - - case MEM: - /* Can't merge two expressions in different alias sets, since we can - decide that the expression is transparent in a block when it isn't, - due to it being set with the different alias set. */ - if (MEM_ALIAS_SET (x) != MEM_ALIAS_SET (y)) - return 0; - break; - - /* For commutative operations, check both orders. */ - case PLUS: - case MULT: - case AND: - case IOR: - case XOR: - case NE: - case EQ: - return ((expr_equiv_p (XEXP (x, 0), XEXP (y, 0)) - && expr_equiv_p (XEXP (x, 1), XEXP (y, 1))) - || (expr_equiv_p (XEXP (x, 0), XEXP (y, 1)) - && expr_equiv_p (XEXP (x, 1), XEXP (y, 0)))); - - default: - break; - } - - /* Compare the elements. If any pair of corresponding elements - fail to match, return 0 for the whole thing. */ - - fmt = GET_RTX_FORMAT (code); - for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) - { - switch (fmt[i]) - { - case 'e': - if (! expr_equiv_p (XEXP (x, i), XEXP (y, i))) - return 0; - break; - - case 'E': - if (XVECLEN (x, i) != XVECLEN (y, i)) - return 0; - for (j = 0; j < XVECLEN (x, i); j++) - if (! expr_equiv_p (XVECEXP (x, i, j), XVECEXP (y, i, j))) - return 0; - break; - - case 's': - if (strcmp (XSTR (x, i), XSTR (y, i))) - return 0; - break; - - case 'i': - if (XINT (x, i) != XINT (y, i)) - return 0; - break; - - case 'w': - if (XWINT (x, i) != XWINT (y, i)) - return 0; - break; - - case '0': - break; - - default: - abort (); - } - } - - return 1; -} - -/* Insert expression X in INSN in the hash table. - If it is already present, record it as the last occurrence in INSN's - basic block. - - MODE is the mode of the value X is being stored into. - It is only used if X is a CONST_INT. - - ANTIC_P is non-zero if X is an anticipatable expression. - AVAIL_P is non-zero if X is an available expression. */ - -static void -insert_expr_in_table (x, mode, insn, antic_p, avail_p) - rtx x; - enum machine_mode mode; - rtx insn; - int antic_p, avail_p; -{ - int found, do_not_record_p; - unsigned int hash; - struct expr *cur_expr, *last_expr = NULL; - struct occr *antic_occr, *avail_occr; - struct occr *last_occr = NULL; - - hash = hash_expr (x, mode, &do_not_record_p, expr_hash_table_size); - - /* Do not insert expression in table if it contains volatile operands, - or if hash_expr determines the expression is something we don't want - to or can't handle. */ - if (do_not_record_p) - return; - - cur_expr = expr_hash_table[hash]; - found = 0; - - while (cur_expr && ! (found = expr_equiv_p (cur_expr->expr, x))) - { - /* If the expression isn't found, save a pointer to the end of - the list. */ - last_expr = cur_expr; - cur_expr = cur_expr->next_same_hash; - } - - if (! found) - { - cur_expr = (struct expr *) gcse_alloc (sizeof (struct expr)); - bytes_used += sizeof (struct expr); - if (expr_hash_table[hash] == NULL) - { - /* This is the first pattern that hashed to this index. */ - expr_hash_table[hash] = cur_expr; - } - else - { - /* Add EXPR to end of this hash chain. */ - last_expr->next_same_hash = cur_expr; - } - /* Set the fields of the expr element. */ - cur_expr->expr = x; - cur_expr->bitmap_index = n_exprs++; - cur_expr->next_same_hash = NULL; - cur_expr->antic_occr = NULL; - cur_expr->avail_occr = NULL; - } - - /* Now record the occurrence(s). */ - - if (antic_p) - { - antic_occr = cur_expr->antic_occr; - - /* Search for another occurrence in the same basic block. */ - while (antic_occr && BLOCK_NUM (antic_occr->insn) != BLOCK_NUM (insn)) - { - /* If an occurrence isn't found, save a pointer to the end of - the list. */ - last_occr = antic_occr; - antic_occr = antic_occr->next; - } - - if (antic_occr) - { - /* Found another instance of the expression in the same basic block. - Prefer the currently recorded one. We want the first one in the - block and the block is scanned from start to end. */ - ; /* nothing to do */ - } - else - { - /* First occurrence of this expression in this basic block. */ - antic_occr = (struct occr *) gcse_alloc (sizeof (struct occr)); - bytes_used += sizeof (struct occr); - /* First occurrence of this expression in any block? */ - if (cur_expr->antic_occr == NULL) - cur_expr->antic_occr = antic_occr; - else - last_occr->next = antic_occr; - antic_occr->insn = insn; - antic_occr->next = NULL; - } - } - - if (avail_p) - { - avail_occr = cur_expr->avail_occr; - - /* Search for another occurrence in the same basic block. */ - while (avail_occr && BLOCK_NUM (avail_occr->insn) != BLOCK_NUM (insn)) - { - /* If an occurrence isn't found, save a pointer to the end of - the list. */ - last_occr = avail_occr; - avail_occr = avail_occr->next; - } - - if (avail_occr) - { - /* Found another instance of the expression in the same basic block. - Prefer this occurrence to the currently recorded one. We want - the last one in the block and the block is scanned from start - to end. */ - avail_occr->insn = insn; - } - else - { - /* First occurrence of this expression in this basic block. */ - avail_occr = (struct occr *) gcse_alloc (sizeof (struct occr)); - bytes_used += sizeof (struct occr); - /* First occurrence of this expression in any block? */ - if (cur_expr->avail_occr == NULL) - cur_expr->avail_occr = avail_occr; - else - last_occr->next = avail_occr; - avail_occr->insn = insn; - avail_occr->next = NULL; - } - } -} - -/* Insert pattern X in INSN in the hash table. - X is a SET of a reg to either another reg or a constant. - If it is already present, record it as the last occurrence in INSN's - basic block. */ - -static void -insert_set_in_table (x, insn) - rtx x; - rtx insn; -{ - int found; - unsigned int hash; - struct expr *cur_expr, *last_expr = NULL; - struct occr *cur_occr, *last_occr = NULL; - - if (GET_CODE (x) != SET - || GET_CODE (SET_DEST (x)) != REG) - abort (); - - hash = hash_set (REGNO (SET_DEST (x)), set_hash_table_size); - - cur_expr = set_hash_table[hash]; - found = 0; - - while (cur_expr && ! (found = expr_equiv_p (cur_expr->expr, x))) - { - /* If the expression isn't found, save a pointer to the end of - the list. */ - last_expr = cur_expr; - cur_expr = cur_expr->next_same_hash; - } - - if (! found) - { - cur_expr = (struct expr *) gcse_alloc (sizeof (struct expr)); - bytes_used += sizeof (struct expr); - if (set_hash_table[hash] == NULL) - { - /* This is the first pattern that hashed to this index. */ - set_hash_table[hash] = cur_expr; - } - else - { - /* Add EXPR to end of this hash chain. */ - last_expr->next_same_hash = cur_expr; - } - /* Set the fields of the expr element. - We must copy X because it can be modified when copy propagation is - performed on its operands. */ - /* ??? Should this go in a different obstack? */ - cur_expr->expr = copy_rtx (x); - cur_expr->bitmap_index = n_sets++; - cur_expr->next_same_hash = NULL; - cur_expr->antic_occr = NULL; - cur_expr->avail_occr = NULL; - } - - /* Now record the occurrence. */ - - cur_occr = cur_expr->avail_occr; - - /* Search for another occurrence in the same basic block. */ - while (cur_occr && BLOCK_NUM (cur_occr->insn) != BLOCK_NUM (insn)) - { - /* If an occurrence isn't found, save a pointer to the end of - the list. */ - last_occr = cur_occr; - cur_occr = cur_occr->next; - } - - if (cur_occr) - { - /* Found another instance of the expression in the same basic block. - Prefer this occurrence to the currently recorded one. We want - the last one in the block and the block is scanned from start - to end. */ - cur_occr->insn = insn; - } - else - { - /* First occurrence of this expression in this basic block. */ - cur_occr = (struct occr *) gcse_alloc (sizeof (struct occr)); - bytes_used += sizeof (struct occr); - /* First occurrence of this expression in any block? */ - if (cur_expr->avail_occr == NULL) - cur_expr->avail_occr = cur_occr; - else - last_occr->next = cur_occr; - cur_occr->insn = insn; - cur_occr->next = NULL; - } -} - -/* Scan pattern PAT of INSN and add an entry to the hash table. - If SET_P is non-zero, this is for the assignment hash table, - otherwise it is for the expression hash table. */ - -static void -hash_scan_set (pat, insn, set_p) - rtx pat, insn; - int set_p; -{ - rtx src = SET_SRC (pat); - rtx dest = SET_DEST (pat); - - if (GET_CODE (src) == CALL) - hash_scan_call (src, insn); - - if (GET_CODE (dest) == REG) - { - int regno = REGNO (dest); - rtx tmp; - - /* Only record sets of pseudo-regs in the hash table. */ - if (! set_p - && regno >= FIRST_PSEUDO_REGISTER - /* Don't GCSE something if we can't do a reg/reg copy. */ - && can_copy_p [GET_MODE (dest)] - /* Is SET_SRC something we want to gcse? */ - && want_to_gcse_p (src)) - { - /* An expression is not anticipatable if its operands are - modified before this insn. */ - int antic_p = ! optimize_size && oprs_anticipatable_p (src, insn); - /* An expression is not available if its operands are - subsequently modified, including this insn. */ - int avail_p = oprs_available_p (src, insn); - insert_expr_in_table (src, GET_MODE (dest), insn, antic_p, avail_p); - } - /* Record sets for constant/copy propagation. */ - else if (set_p - && regno >= FIRST_PSEUDO_REGISTER - && ((GET_CODE (src) == REG - && REGNO (src) >= FIRST_PSEUDO_REGISTER - && can_copy_p [GET_MODE (dest)]) - /* ??? CONST_INT:wip */ - || GET_CODE (src) == CONST_INT - || GET_CODE (src) == CONST_DOUBLE) - /* A copy is not available if its src or dest is subsequently - modified. Here we want to search from INSN+1 on, but - oprs_available_p searches from INSN on. */ - && (insn == BLOCK_END (BLOCK_NUM (insn)) - || ((tmp = next_nonnote_insn (insn)) != NULL_RTX - && oprs_available_p (pat, tmp)))) - insert_set_in_table (pat, insn); - } -} - -static void -hash_scan_clobber (x, insn) - rtx x ATTRIBUTE_UNUSED, insn ATTRIBUTE_UNUSED; -{ - /* Currently nothing to do. */ -} - -static void -hash_scan_call (x, insn) - rtx x ATTRIBUTE_UNUSED, insn ATTRIBUTE_UNUSED; -{ - /* Currently nothing to do. */ -} - -/* Process INSN and add hash table entries as appropriate. - - Only available expressions that set a single pseudo-reg are recorded. - - Single sets in a PARALLEL could be handled, but it's an extra complication - that isn't dealt with right now. The trick is handling the CLOBBERs that - are also in the PARALLEL. Later. - - If SET_P is non-zero, this is for the assignment hash table, - otherwise it is for the expression hash table. - If IN_LIBCALL_BLOCK nonzero, we are in a libcall block, and should - not record any expressions. */ - -static void -hash_scan_insn (insn, set_p, in_libcall_block) - rtx insn; - int set_p; - int in_libcall_block; -{ - rtx pat = PATTERN (insn); - - /* Pick out the sets of INSN and for other forms of instructions record - what's been modified. */ - - if (GET_CODE (pat) == SET && ! in_libcall_block) - hash_scan_set (pat, insn, set_p); - else if (GET_CODE (pat) == PARALLEL) - { - int i; - - for (i = 0; i < XVECLEN (pat, 0); i++) - { - rtx x = XVECEXP (pat, 0, i); - - if (GET_CODE (x) == SET) - { - if (GET_CODE (SET_SRC (x)) == CALL) - hash_scan_call (SET_SRC (x), insn); - } - else if (GET_CODE (x) == CLOBBER) - hash_scan_clobber (x, insn); - else if (GET_CODE (x) == CALL) - hash_scan_call (x, insn); - } - } - else if (GET_CODE (pat) == CLOBBER) - hash_scan_clobber (pat, insn); - else if (GET_CODE (pat) == CALL) - hash_scan_call (pat, insn); -} - -static void -dump_hash_table (file, name, table, table_size, total_size) - FILE *file; - const char *name; - struct expr **table; - int table_size, total_size; -{ - int i; - /* Flattened out table, so it's printed in proper order. */ - struct expr **flat_table = (struct expr **) alloca (total_size * sizeof (struct expr *)); - unsigned int *hash_val = (unsigned int *) alloca (total_size * sizeof (unsigned int)); - - bzero ((char *) flat_table, total_size * sizeof (struct expr *)); - for (i = 0; i < table_size; i++) - { - struct expr *expr; - - for (expr = table[i]; expr != NULL; expr = expr->next_same_hash) - { - flat_table[expr->bitmap_index] = expr; - hash_val[expr->bitmap_index] = i; - } - } - - fprintf (file, "%s hash table (%d buckets, %d entries)\n", - name, table_size, total_size); - - for (i = 0; i < total_size; i++) - { - struct expr *expr = flat_table[i]; - - fprintf (file, "Index %d (hash value %d)\n ", - expr->bitmap_index, hash_val[i]); - print_rtl (file, expr->expr); - fprintf (file, "\n"); - } - - fprintf (file, "\n"); -} - -/* Record register first/last/block set information for REGNO in INSN. - reg_first_set records the first place in the block where the register - is set and is used to compute "anticipatability". - reg_last_set records the last place in the block where the register - is set and is used to compute "availability". - reg_set_in_block records whether the register is set in the block - and is used to compute "transparency". */ - -static void -record_last_reg_set_info (insn, regno) - rtx insn; - int regno; -{ - if (reg_first_set[regno] == NEVER_SET) - reg_first_set[regno] = INSN_CUID (insn); - reg_last_set[regno] = INSN_CUID (insn); - SET_BIT (reg_set_in_block[BLOCK_NUM (insn)], regno); -} - -/* Record memory first/last/block set information for INSN. */ - -static void -record_last_mem_set_info (insn) - rtx insn; -{ - if (mem_first_set == NEVER_SET) - mem_first_set = INSN_CUID (insn); - mem_last_set = INSN_CUID (insn); - mem_set_in_block[BLOCK_NUM (insn)] = 1; -} - -/* Used for communicating between next two routines. */ -static rtx last_set_insn; - -/* Called from compute_hash_table via note_stores to handle one - SET or CLOBBER in an insn. */ - -static void -record_last_set_info (dest, setter) - rtx dest, setter ATTRIBUTE_UNUSED; -{ - if (GET_CODE (dest) == SUBREG) - dest = SUBREG_REG (dest); - - if (GET_CODE (dest) == REG) - record_last_reg_set_info (last_set_insn, REGNO (dest)); - else if (GET_CODE (dest) == MEM - /* Ignore pushes, they clobber nothing. */ - && ! push_operand (dest, GET_MODE (dest))) - record_last_mem_set_info (last_set_insn); -} - -/* Top level function to create an expression or assignment hash table. - - Expression entries are placed in the hash table if - - they are of the form (set (pseudo-reg) src), - - src is something we want to perform GCSE on, - - none of the operands are subsequently modified in the block - - Assignment entries are placed in the hash table if - - they are of the form (set (pseudo-reg) src), - - src is something we want to perform const/copy propagation on, - - none of the operands or target are subsequently modified in the block - Currently src must be a pseudo-reg or a const_int. - - F is the first insn. - SET_P is non-zero for computing the assignment hash table. */ - -static void -compute_hash_table (set_p) - int set_p; -{ - int bb; - - /* While we compute the hash table we also compute a bit array of which - registers are set in which blocks. - We also compute which blocks set memory, in the absence of aliasing - support [which is TODO]. - ??? This isn't needed during const/copy propagation, but it's cheap to - compute. Later. */ - sbitmap_vector_zero (reg_set_in_block, n_basic_blocks); - bzero ((char *) mem_set_in_block, n_basic_blocks); - - /* Some working arrays used to track first and last set in each block. */ - /* ??? One could use alloca here, but at some size a threshold is crossed - beyond which one should use malloc. Are we at that threshold here? */ - reg_first_set = (int *) gmalloc (max_gcse_regno * sizeof (int)); - reg_last_set = (int *) gmalloc (max_gcse_regno * sizeof (int)); - - for (bb = 0; bb < n_basic_blocks; bb++) - { - rtx insn; - int regno; - int in_libcall_block; - int i; - - /* First pass over the instructions records information used to - determine when registers and memory are first and last set. - ??? The mem_set_in_block and hard-reg reg_set_in_block computation - could be moved to compute_sets since they currently don't change. */ - - for (i = 0; i < max_gcse_regno; i++) - reg_first_set[i] = reg_last_set[i] = NEVER_SET; - mem_first_set = NEVER_SET; - mem_last_set = NEVER_SET; - - for (insn = BLOCK_HEAD (bb); - insn && insn != NEXT_INSN (BLOCK_END (bb)); - insn = NEXT_INSN (insn)) - { -#ifdef NON_SAVING_SETJMP - if (NON_SAVING_SETJMP && GET_CODE (insn) == NOTE - && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP) - { - for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++) - record_last_reg_set_info (insn, regno); - continue; - } -#endif - - if (GET_RTX_CLASS (GET_CODE (insn)) != 'i') - continue; - - if (GET_CODE (insn) == CALL_INSN) - { - for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++) - if ((call_used_regs[regno] - && regno != STACK_POINTER_REGNUM -#if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM - && regno != HARD_FRAME_POINTER_REGNUM -#endif -#if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM - && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno]) -#endif -#if defined (PIC_OFFSET_TABLE_REGNUM) && !defined (PIC_OFFSET_TABLE_REG_CALL_CLOBBERED) - && ! (regno == PIC_OFFSET_TABLE_REGNUM && flag_pic) -#endif - - && regno != FRAME_POINTER_REGNUM) - || global_regs[regno]) - record_last_reg_set_info (insn, regno); - if (! CONST_CALL_P (insn)) - record_last_mem_set_info (insn); - } - - last_set_insn = insn; - note_stores (PATTERN (insn), record_last_set_info); - } - - /* The next pass builds the hash table. */ - - for (insn = BLOCK_HEAD (bb), in_libcall_block = 0; - insn && insn != NEXT_INSN (BLOCK_END (bb)); - insn = NEXT_INSN (insn)) - { - if (GET_RTX_CLASS (GET_CODE (insn)) == 'i') - { - if (find_reg_note (insn, REG_LIBCALL, NULL_RTX)) - in_libcall_block = 1; - else if (find_reg_note (insn, REG_RETVAL, NULL_RTX)) - in_libcall_block = 0; - hash_scan_insn (insn, set_p, in_libcall_block); - } - } - } - - free (reg_first_set); - free (reg_last_set); - /* Catch bugs early. */ - reg_first_set = reg_last_set = 0; -} - -/* Allocate space for the set hash table. - N_INSNS is the number of instructions in the function. - It is used to determine the number of buckets to use. */ - -static void -alloc_set_hash_table (n_insns) - int n_insns; -{ - int n; - - set_hash_table_size = n_insns / 4; - if (set_hash_table_size < 11) - set_hash_table_size = 11; - /* Attempt to maintain efficient use of hash table. - Making it an odd number is simplest for now. - ??? Later take some measurements. */ - set_hash_table_size |= 1; - n = set_hash_table_size * sizeof (struct expr *); - set_hash_table = (struct expr **) gmalloc (n); -} - -/* Free things allocated by alloc_set_hash_table. */ - -static void -free_set_hash_table () -{ - free (set_hash_table); -} - -/* Compute the hash table for doing copy/const propagation. */ - -static void -compute_set_hash_table () -{ - /* Initialize count of number of entries in hash table. */ - n_sets = 0; - bzero ((char *) set_hash_table, set_hash_table_size * sizeof (struct expr *)); - - compute_hash_table (1); -} - -/* Allocate space for the expression hash table. - N_INSNS is the number of instructions in the function. - It is used to determine the number of buckets to use. */ - -static void -alloc_expr_hash_table (n_insns) - int n_insns; -{ - int n; - - expr_hash_table_size = n_insns / 2; - /* Make sure the amount is usable. */ - if (expr_hash_table_size < 11) - expr_hash_table_size = 11; - /* Attempt to maintain efficient use of hash table. - Making it an odd number is simplest for now. - ??? Later take some measurements. */ - expr_hash_table_size |= 1; - n = expr_hash_table_size * sizeof (struct expr *); - expr_hash_table = (struct expr **) gmalloc (n); -} - -/* Free things allocated by alloc_expr_hash_table. */ - -static void -free_expr_hash_table () -{ - free (expr_hash_table); -} - -/* Compute the hash table for doing GCSE. */ - -static void -compute_expr_hash_table () -{ - /* Initialize count of number of entries in hash table. */ - n_exprs = 0; - bzero ((char *) expr_hash_table, expr_hash_table_size * sizeof (struct expr *)); - - compute_hash_table (0); -} - -/* Expression tracking support. */ - -/* Lookup pattern PAT in the expression table. - The result is a pointer to the table entry, or NULL if not found. */ - -static struct expr * -lookup_expr (pat) - rtx pat; -{ - int do_not_record_p; - unsigned int hash = hash_expr (pat, GET_MODE (pat), &do_not_record_p, - expr_hash_table_size); - struct expr *expr; - - if (do_not_record_p) - return NULL; - - expr = expr_hash_table[hash]; - - while (expr && ! expr_equiv_p (expr->expr, pat)) - expr = expr->next_same_hash; - - return expr; -} - -/* Lookup REGNO in the set table. - If PAT is non-NULL look for the entry that matches it, otherwise return - the first entry for REGNO. - The result is a pointer to the table entry, or NULL if not found. */ - -static struct expr * -lookup_set (regno, pat) - int regno; - rtx pat; -{ - unsigned int hash = hash_set (regno, set_hash_table_size); - struct expr *expr; - - expr = set_hash_table[hash]; - - if (pat) - { - while (expr && ! expr_equiv_p (expr->expr, pat)) - expr = expr->next_same_hash; - } - else - { - while (expr && REGNO (SET_DEST (expr->expr)) != regno) - expr = expr->next_same_hash; - } - - return expr; -} - -/* Return the next entry for REGNO in list EXPR. */ - -static struct expr * -next_set (regno, expr) - int regno; - struct expr *expr; -{ - do - expr = expr->next_same_hash; - while (expr && REGNO (SET_DEST (expr->expr)) != regno); - return expr; -} - -/* Reset tables used to keep track of what's still available [since the - start of the block]. */ - -static void -reset_opr_set_tables () -{ - /* Maintain a bitmap of which regs have been set since beginning of - the block. */ - sbitmap_zero (reg_set_bitmap); - /* Also keep a record of the last instruction to modify memory. - For now this is very trivial, we only record whether any memory - location has been modified. */ - mem_last_set = 0; -} - -/* Return non-zero if the operands of X are not set before INSN in - INSN's basic block. */ - -static int -oprs_not_set_p (x, insn) - rtx x, insn; -{ - int i; - enum rtx_code code; - char *fmt; - - /* repeat is used to turn tail-recursion into iteration. */ -repeat: - - if (x == 0) - return 1; - - code = GET_CODE (x); - switch (code) - { - case PC: - case CC0: - case CONST: - case CONST_INT: - case CONST_DOUBLE: - case SYMBOL_REF: - case LABEL_REF: - case ADDR_VEC: - case ADDR_DIFF_VEC: - return 1; - - case MEM: - if (mem_last_set != 0) - return 0; - x = XEXP (x, 0); - goto repeat; - - case REG: - return ! TEST_BIT (reg_set_bitmap, REGNO (x)); - - default: - break; - } - - fmt = GET_RTX_FORMAT (code); - for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) - { - if (fmt[i] == 'e') - { - int not_set_p; - /* If we are about to do the last recursive call - needed at this level, change it into iteration. - This function is called enough to be worth it. */ - if (i == 0) - { - x = XEXP (x, 0); - goto repeat; - } - not_set_p = oprs_not_set_p (XEXP (x, i), insn); - if (! not_set_p) - return 0; - } - else if (fmt[i] == 'E') - { - int j; - for (j = 0; j < XVECLEN (x, i); j++) - { - int not_set_p = oprs_not_set_p (XVECEXP (x, i, j), insn); - if (! not_set_p) - return 0; - } - } - } - - return 1; -} - -/* Mark things set by a CALL. */ - -static void -mark_call (insn) - rtx insn; -{ - mem_last_set = INSN_CUID (insn); -} - -/* Mark things set by a SET. */ - -static void -mark_set (pat, insn) - rtx pat, insn; -{ - rtx dest = SET_DEST (pat); - - while (GET_CODE (dest) == SUBREG - || GET_CODE (dest) == ZERO_EXTRACT - || GET_CODE (dest) == SIGN_EXTRACT - || GET_CODE (dest) == STRICT_LOW_PART) - dest = XEXP (dest, 0); - - if (GET_CODE (dest) == REG) - SET_BIT (reg_set_bitmap, REGNO (dest)); - else if (GET_CODE (dest) == MEM) - mem_last_set = INSN_CUID (insn); - - if (GET_CODE (SET_SRC (pat)) == CALL) - mark_call (insn); -} - -/* Record things set by a CLOBBER. */ - -static void -mark_clobber (pat, insn) - rtx pat, insn; -{ - rtx clob = XEXP (pat, 0); - - while (GET_CODE (clob) == SUBREG || GET_CODE (clob) == STRICT_LOW_PART) - clob = XEXP (clob, 0); - - if (GET_CODE (clob) == REG) - SET_BIT (reg_set_bitmap, REGNO (clob)); - else - mem_last_set = INSN_CUID (insn); -} - -/* Record things set by INSN. - This data is used by oprs_not_set_p. */ - -static void -mark_oprs_set (insn) - rtx insn; -{ - rtx pat = PATTERN (insn); - - if (GET_CODE (pat) == SET) - mark_set (pat, insn); - else if (GET_CODE (pat) == PARALLEL) - { - int i; - - for (i = 0; i < XVECLEN (pat, 0); i++) - { - rtx x = XVECEXP (pat, 0, i); - - if (GET_CODE (x) == SET) - mark_set (x, insn); - else if (GET_CODE (x) == CLOBBER) - mark_clobber (x, insn); - else if (GET_CODE (x) == CALL) - mark_call (insn); - } - } - else if (GET_CODE (pat) == CLOBBER) - mark_clobber (pat, insn); - else if (GET_CODE (pat) == CALL) - mark_call (insn); -} - - -/* Classic GCSE reaching definition support. */ - -/* Allocate reaching def variables. */ - -static void -alloc_rd_mem (n_blocks, n_insns) - int n_blocks, n_insns; -{ - rd_kill = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_insns); - sbitmap_vector_zero (rd_kill, n_basic_blocks); - - rd_gen = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_insns); - sbitmap_vector_zero (rd_gen, n_basic_blocks); - - reaching_defs = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_insns); - sbitmap_vector_zero (reaching_defs, n_basic_blocks); - - rd_out = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_insns); - sbitmap_vector_zero (rd_out, n_basic_blocks); -} - -/* Free reaching def variables. */ - -static void -free_rd_mem () -{ - free (rd_kill); - free (rd_gen); - free (reaching_defs); - free (rd_out); -} - -/* Add INSN to the kills of BB. - REGNO, set in BB, is killed by INSN. */ - -static void -handle_rd_kill_set (insn, regno, bb) - rtx insn; - int regno, bb; -{ - struct reg_set *this_reg = reg_set_table[regno]; - - while (this_reg) - { - if (BLOCK_NUM (this_reg->insn) != BLOCK_NUM (insn)) - SET_BIT (rd_kill[bb], INSN_CUID (this_reg->insn)); - this_reg = this_reg->next; - } -} - -/* Compute the set of kill's for reaching definitions. */ - -static void -compute_kill_rd () -{ - int bb,cuid; - - /* For each block - For each set bit in `gen' of the block (i.e each insn which - generates a definition in the block) - Call the reg set by the insn corresponding to that bit regx - Look at the linked list starting at reg_set_table[regx] - For each setting of regx in the linked list, which is not in - this block - Set the bit in `kill' corresponding to that insn - */ - - for (bb = 0; bb < n_basic_blocks; bb++) - { - for (cuid = 0; cuid < max_cuid; cuid++) - { - if (TEST_BIT (rd_gen[bb], cuid)) - { - rtx insn = CUID_INSN (cuid); - rtx pat = PATTERN (insn); - - if (GET_CODE (insn) == CALL_INSN) - { - int regno; - - for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++) - { - if ((call_used_regs[regno] - && regno != STACK_POINTER_REGNUM -#if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM - && regno != HARD_FRAME_POINTER_REGNUM -#endif -#if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM - && ! (regno == ARG_POINTER_REGNUM - && fixed_regs[regno]) -#endif -#if defined (PIC_OFFSET_TABLE_REGNUM) && !defined (PIC_OFFSET_TABLE_REG_CALL_CLOBBERED) - && ! (regno == PIC_OFFSET_TABLE_REGNUM && flag_pic) -#endif - && regno != FRAME_POINTER_REGNUM) - || global_regs[regno]) - handle_rd_kill_set (insn, regno, bb); - } - } - - if (GET_CODE (pat) == PARALLEL) - { - int i; - - /* We work backwards because ... */ - for (i = XVECLEN (pat, 0) - 1; i >= 0; i--) - { - enum rtx_code code = GET_CODE (XVECEXP (pat, 0, i)); - if ((code == SET || code == CLOBBER) - && GET_CODE (XEXP (XVECEXP (pat, 0, i), 0)) == REG) - handle_rd_kill_set (insn, - REGNO (XEXP (XVECEXP (pat, 0, i), 0)), - bb); - } - } - else if (GET_CODE (pat) == SET) - { - if (GET_CODE (SET_DEST (pat)) == REG) - { - /* Each setting of this register outside of this block - must be marked in the set of kills in this block. */ - handle_rd_kill_set (insn, REGNO (SET_DEST (pat)), bb); - } - } - /* FIXME: CLOBBER? */ - } - } - } -} - -/* Compute the reaching definitions as in - Compilers Principles, Techniques, and Tools. Aho, Sethi, Ullman, - Chapter 10. It is the same algorithm as used for computing available - expressions but applied to the gens and kills of reaching definitions. */ - -static void -compute_rd () -{ - int bb, changed, passes; - - for (bb = 0; bb < n_basic_blocks; bb++) - sbitmap_copy (rd_out[bb] /*dst*/, rd_gen[bb] /*src*/); - - passes = 0; - changed = 1; - while (changed) - { - changed = 0; - for (bb = 0; bb < n_basic_blocks; bb++) - { - sbitmap_union_of_predecessors (reaching_defs[bb], rd_out, - bb, s_preds); - changed |= sbitmap_union_of_diff (rd_out[bb], rd_gen[bb], - reaching_defs[bb], rd_kill[bb]); - } - passes++; - } - - if (gcse_file) - fprintf (gcse_file, "reaching def computation: %d passes\n", passes); -} - -/* Classic GCSE available expression support. */ - -/* Allocate memory for available expression computation. */ - -static void -alloc_avail_expr_mem (n_blocks, n_exprs) - int n_blocks, n_exprs; -{ - ae_kill = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_exprs); - sbitmap_vector_zero (ae_kill, n_basic_blocks); - - ae_gen = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_exprs); - sbitmap_vector_zero (ae_gen, n_basic_blocks); - - ae_in = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_exprs); - sbitmap_vector_zero (ae_in, n_basic_blocks); - - ae_out = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_exprs); - sbitmap_vector_zero (ae_out, n_basic_blocks); - - u_bitmap = (sbitmap) sbitmap_alloc (n_exprs); - sbitmap_ones (u_bitmap); -} - -static void -free_avail_expr_mem () -{ - free (ae_kill); - free (ae_gen); - free (ae_in); - free (ae_out); - free (u_bitmap); -} - -/* Compute the set of available expressions generated in each basic block. */ - -static void -compute_ae_gen () -{ - int i; - - /* For each recorded occurrence of each expression, set ae_gen[bb][expr]. - This is all we have to do because an expression is not recorded if it - is not available, and the only expressions we want to work with are the - ones that are recorded. */ - - for (i = 0; i < expr_hash_table_size; i++) - { - struct expr *expr = expr_hash_table[i]; - while (expr != NULL) - { - struct occr *occr = expr->avail_occr; - while (occr != NULL) - { - SET_BIT (ae_gen[BLOCK_NUM (occr->insn)], expr->bitmap_index); - occr = occr->next; - } - expr = expr->next_same_hash; - } - } -} - -/* Return non-zero if expression X is killed in BB. */ - -static int -expr_killed_p (x, bb) - rtx x; - int bb; -{ - int i; - enum rtx_code code; - char *fmt; - - /* repeat is used to turn tail-recursion into iteration. */ - repeat: - - if (x == 0) - return 1; - - code = GET_CODE (x); - switch (code) - { - case REG: - return TEST_BIT (reg_set_in_block[bb], REGNO (x)); - - case MEM: - if (mem_set_in_block[bb]) - return 1; - x = XEXP (x, 0); - goto repeat; - - case PC: - case CC0: /*FIXME*/ - case CONST: - case CONST_INT: - case CONST_DOUBLE: - case SYMBOL_REF: - case LABEL_REF: - case ADDR_VEC: - case ADDR_DIFF_VEC: - return 0; - - default: - break; - } - - i = GET_RTX_LENGTH (code) - 1; - fmt = GET_RTX_FORMAT (code); - for (; i >= 0; i--) - { - if (fmt[i] == 'e') - { - rtx tem = XEXP (x, i); - - /* If we are about to do the last recursive call - needed at this level, change it into iteration. - This function is called enough to be worth it. */ - if (i == 0) - { - x = tem; - goto repeat; - } - if (expr_killed_p (tem, bb)) - return 1; - } - else if (fmt[i] == 'E') - { - int j; - for (j = 0; j < XVECLEN (x, i); j++) - { - if (expr_killed_p (XVECEXP (x, i, j), bb)) - return 1; - } - } - } - - return 0; -} - -/* Compute the set of available expressions killed in each basic block. */ - -static void -compute_ae_kill () -{ - int bb,i; - - for (bb = 0; bb < n_basic_blocks; bb++) - { - for (i = 0; i < expr_hash_table_size; i++) - { - struct expr *expr = expr_hash_table[i]; - - for ( ; expr != NULL; expr = expr->next_same_hash) - { - /* Skip EXPR if generated in this block. */ - if (TEST_BIT (ae_gen[bb], expr->bitmap_index)) - continue; - - if (expr_killed_p (expr->expr, bb)) - SET_BIT (ae_kill[bb], expr->bitmap_index); - } - } - } -} - -/* Compute available expressions. - - Implement the algorithm to find available expressions - as given in the Aho Sethi Ullman book, pages 627-631. */ - -static void -compute_available () -{ - int bb, changed, passes; - - sbitmap_zero (ae_in[0]); - - sbitmap_copy (ae_out[0] /*dst*/, ae_gen[0] /*src*/); - - for (bb = 1; bb < n_basic_blocks; bb++) - sbitmap_difference (ae_out[bb], u_bitmap, ae_kill[bb]); - - passes = 0; - changed = 1; - while (changed) - { - changed = 0; - for (bb = 1; bb < n_basic_blocks; bb++) - { - sbitmap_intersect_of_predecessors (ae_in[bb], ae_out, bb, s_preds); - changed |= sbitmap_union_of_diff (ae_out[bb], ae_gen[bb], - ae_in[bb], ae_kill[bb]); - } - passes++; - } - - if (gcse_file) - fprintf (gcse_file, "avail expr computation: %d passes\n", passes); -} - -/* Actually perform the Classic GCSE optimizations. */ - -/* Return non-zero if occurrence OCCR of expression EXPR reaches block BB. - - CHECK_SELF_LOOP is non-zero if we should consider a block reaching itself - as a positive reach. We want to do this when there are two computations - of the expression in the block. - - VISITED is a pointer to a working buffer for tracking which BB's have - been visited. It is NULL for the top-level call. - - We treat reaching expressions that go through blocks containing the same - reaching expression as "not reaching". E.g. if EXPR is generated in blocks - 2 and 3, INSN is in block 4, and 2->3->4, we treat the expression in block - 2 as not reaching. The intent is to improve the probability of finding - only one reaching expression and to reduce register lifetimes by picking - the closest such expression. */ - -static int -expr_reaches_here_p (occr, expr, bb, check_self_loop, visited) - struct occr *occr; - struct expr *expr; - int bb; - int check_self_loop; - char *visited; -{ - int_list_ptr pred; - - if (visited == NULL) - { - visited = (char *) alloca (n_basic_blocks); - bzero (visited, n_basic_blocks); - } - - for (pred = s_preds[bb]; pred != NULL; pred = pred->next) - { - int pred_bb = INT_LIST_VAL (pred); - - if (visited[pred_bb]) - { - /* This predecessor has already been visited. - Nothing to do. */ - ; - } - else if (pred_bb == bb) - { - /* BB loops on itself. */ - if (check_self_loop - && TEST_BIT (ae_gen[pred_bb], expr->bitmap_index) - && BLOCK_NUM (occr->insn) == pred_bb) - return 1; - visited[pred_bb] = 1; - } - /* Ignore this predecessor if it kills the expression. */ - else if (TEST_BIT (ae_kill[pred_bb], expr->bitmap_index)) - visited[pred_bb] = 1; - /* Does this predecessor generate this expression? */ - else if (TEST_BIT (ae_gen[pred_bb], expr->bitmap_index)) - { - /* Is this the occurrence we're looking for? - Note that there's only one generating occurrence per block - so we just need to check the block number. */ - if (BLOCK_NUM (occr->insn) == pred_bb) - return 1; - visited[pred_bb] = 1; - } - /* Neither gen nor kill. */ - else - { - visited[pred_bb] = 1; - if (expr_reaches_here_p (occr, expr, pred_bb, check_self_loop, visited)) - return 1; - } - } - - /* All paths have been checked. */ - return 0; -} - -/* Return the instruction that computes EXPR that reaches INSN's basic block. - If there is more than one such instruction, return NULL. - - Called only by handle_avail_expr. */ - -static rtx -computing_insn (expr, insn) - struct expr *expr; - rtx insn; -{ - int bb = BLOCK_NUM (insn); - - if (expr->avail_occr->next == NULL) - { - if (BLOCK_NUM (expr->avail_occr->insn) == bb) - { - /* The available expression is actually itself - (i.e. a loop in the flow graph) so do nothing. */ - return NULL; - } - /* (FIXME) Case that we found a pattern that was created by - a substitution that took place. */ - return expr->avail_occr->insn; - } - else - { - /* Pattern is computed more than once. - Search backwards from this insn to see how many of these - computations actually reach this insn. */ - struct occr *occr; - rtx insn_computes_expr = NULL; - int can_reach = 0; - - for (occr = expr->avail_occr; occr != NULL; occr = occr->next) - { - if (BLOCK_NUM (occr->insn) == bb) - { - /* The expression is generated in this block. - The only time we care about this is when the expression - is generated later in the block [and thus there's a loop]. - We let the normal cse pass handle the other cases. */ - if (INSN_CUID (insn) < INSN_CUID (occr->insn)) - { - if (expr_reaches_here_p (occr, expr, bb, 1, NULL)) - { - can_reach++; - if (can_reach > 1) - return NULL; - insn_computes_expr = occr->insn; - } - } - } - else /* Computation of the pattern outside this block. */ - { - if (expr_reaches_here_p (occr, expr, bb, 0, NULL)) - { - can_reach++; - if (can_reach > 1) - return NULL; - insn_computes_expr = occr->insn; - } - } - } - - if (insn_computes_expr == NULL) - abort (); - return insn_computes_expr; - } -} - -/* Return non-zero if the definition in DEF_INSN can reach INSN. - Only called by can_disregard_other_sets. */ - -static int -def_reaches_here_p (insn, def_insn) - rtx insn, def_insn; -{ - rtx reg; - - if (TEST_BIT (reaching_defs[BLOCK_NUM (insn)], INSN_CUID (def_insn))) - return 1; - - if (BLOCK_NUM (insn) == BLOCK_NUM (def_insn)) - { - if (INSN_CUID (def_insn) < INSN_CUID (insn)) - { - if (GET_CODE (PATTERN (def_insn)) == PARALLEL) - return 1; - if (GET_CODE (PATTERN (def_insn)) == CLOBBER) - reg = XEXP (PATTERN (def_insn), 0); - else if (GET_CODE (PATTERN (def_insn)) == SET) - reg = SET_DEST (PATTERN (def_insn)); - else - abort (); - return ! reg_set_between_p (reg, NEXT_INSN (def_insn), insn); - } - else - return 0; - } - - return 0; -} - -/* Return non-zero if *ADDR_THIS_REG can only have one value at INSN. - The value returned is the number of definitions that reach INSN. - Returning a value of zero means that [maybe] more than one definition - reaches INSN and the caller can't perform whatever optimization it is - trying. i.e. it is always safe to return zero. */ - -static int -can_disregard_other_sets (addr_this_reg, insn, for_combine) - struct reg_set **addr_this_reg; - rtx insn; - int for_combine; -{ - int number_of_reaching_defs = 0; - struct reg_set *this_reg = *addr_this_reg; - - while (this_reg) - { - if (def_reaches_here_p (insn, this_reg->insn)) - { - number_of_reaching_defs++; - /* Ignore parallels for now. */ - if (GET_CODE (PATTERN (this_reg->insn)) == PARALLEL) - return 0; - if (!for_combine - && (GET_CODE (PATTERN (this_reg->insn)) == CLOBBER - || ! rtx_equal_p (SET_SRC (PATTERN (this_reg->insn)), - SET_SRC (PATTERN (insn))))) - { - /* A setting of the reg to a different value reaches INSN. */ - return 0; - } - if (number_of_reaching_defs > 1) - { - /* If in this setting the value the register is being - set to is equal to the previous value the register - was set to and this setting reaches the insn we are - trying to do the substitution on then we are ok. */ - - if (GET_CODE (PATTERN (this_reg->insn)) == CLOBBER) - return 0; - if (! rtx_equal_p (SET_SRC (PATTERN (this_reg->insn)), - SET_SRC (PATTERN (insn)))) - return 0; - } - *addr_this_reg = this_reg; - } - - /* prev_this_reg = this_reg; */ - this_reg = this_reg->next; - } - - return number_of_reaching_defs; -} - -/* Expression computed by insn is available and the substitution is legal, - so try to perform the substitution. - - The result is non-zero if any changes were made. */ - -static int -handle_avail_expr (insn, expr) - rtx insn; - struct expr *expr; -{ - rtx pat, insn_computes_expr; - rtx to; - struct reg_set *this_reg; - int found_setting, use_src; - int changed = 0; - - /* We only handle the case where one computation of the expression - reaches this instruction. */ - insn_computes_expr = computing_insn (expr, insn); - if (insn_computes_expr == NULL) - return 0; - - found_setting = 0; - use_src = 0; - - /* At this point we know only one computation of EXPR outside of this - block reaches this insn. Now try to find a register that the - expression is computed into. */ - - if (GET_CODE (SET_SRC (PATTERN (insn_computes_expr))) == REG) - { - /* This is the case when the available expression that reaches - here has already been handled as an available expression. */ - int regnum_for_replacing = REGNO (SET_SRC (PATTERN (insn_computes_expr))); - /* If the register was created by GCSE we can't use `reg_set_table', - however we know it's set only once. */ - if (regnum_for_replacing >= max_gcse_regno - /* If the register the expression is computed into is set only once, - or only one set reaches this insn, we can use it. */ - || (((this_reg = reg_set_table[regnum_for_replacing]), - this_reg->next == NULL) - || can_disregard_other_sets (&this_reg, insn, 0))) - { - use_src = 1; - found_setting = 1; - } - } - - if (!found_setting) - { - int regnum_for_replacing = REGNO (SET_DEST (PATTERN (insn_computes_expr))); - /* This shouldn't happen. */ - if (regnum_for_replacing >= max_gcse_regno) - abort (); - this_reg = reg_set_table[regnum_for_replacing]; - /* If the register the expression is computed into is set only once, - or only one set reaches this insn, use it. */ - if (this_reg->next == NULL - || can_disregard_other_sets (&this_reg, insn, 0)) - found_setting = 1; - } - - if (found_setting) - { - pat = PATTERN (insn); - if (use_src) - to = SET_SRC (PATTERN (insn_computes_expr)); - else - to = SET_DEST (PATTERN (insn_computes_expr)); - changed = validate_change (insn, &SET_SRC (pat), to, 0); - - /* We should be able to ignore the return code from validate_change but - to play it safe we check. */ - if (changed) - { - gcse_subst_count++; - if (gcse_file != NULL) - { - fprintf (gcse_file, "GCSE: Replacing the source in insn %d with reg %d %s insn %d\n", - INSN_UID (insn), REGNO (to), - use_src ? "from" : "set in", - INSN_UID (insn_computes_expr)); - } - - } - } - /* The register that the expr is computed into is set more than once. */ - else if (1 /*expensive_op(this_pattrn->op) && do_expensive_gcse)*/) - { - /* Insert an insn after insnx that copies the reg set in insnx - into a new pseudo register call this new register REGN. - From insnb until end of basic block or until REGB is set - replace all uses of REGB with REGN. */ - rtx new_insn; - - to = gen_reg_rtx (GET_MODE (SET_DEST (PATTERN (insn_computes_expr)))); - - /* Generate the new insn. */ - /* ??? If the change fails, we return 0, even though we created - an insn. I think this is ok. */ - new_insn - = emit_insn_after (gen_rtx_SET (VOIDmode, to, - SET_DEST (PATTERN (insn_computes_expr))), - insn_computes_expr); - /* Keep block number table up to date. */ - set_block_num (new_insn, BLOCK_NUM (insn_computes_expr)); - /* Keep register set table up to date. */ - record_one_set (REGNO (to), new_insn); - - gcse_create_count++; - if (gcse_file != NULL) - { - fprintf (gcse_file, "GCSE: Creating insn %d to copy value of reg %d, computed in insn %d,\n", - INSN_UID (NEXT_INSN (insn_computes_expr)), - REGNO (SET_SRC (PATTERN (NEXT_INSN (insn_computes_expr)))), - INSN_UID (insn_computes_expr)); - fprintf (gcse_file, " into newly allocated reg %d\n", REGNO (to)); - } - - pat = PATTERN (insn); - - /* Do register replacement for INSN. */ - changed = validate_change (insn, &SET_SRC (pat), - SET_DEST (PATTERN (NEXT_INSN (insn_computes_expr))), - 0); - - /* We should be able to ignore the return code from validate_change but - to play it safe we check. */ - if (changed) - { - gcse_subst_count++; - if (gcse_file != NULL) - { - fprintf (gcse_file, "GCSE: Replacing the source in insn %d with reg %d set in insn %d\n", - INSN_UID (insn), - REGNO (SET_DEST (PATTERN (NEXT_INSN (insn_computes_expr)))), - INSN_UID (insn_computes_expr)); - } - - } - } - - return changed; -} - -/* Perform classic GCSE. - This is called by one_classic_gcse_pass after all the dataflow analysis - has been done. - - The result is non-zero if a change was made. */ - -static int -classic_gcse () -{ - int bb, changed; - rtx insn; - - /* Note we start at block 1. */ - - changed = 0; - for (bb = 1; bb < n_basic_blocks; bb++) - { - /* Reset tables used to keep track of what's still valid [since the - start of the block]. */ - reset_opr_set_tables (); - - for (insn = BLOCK_HEAD (bb); - insn != NULL && insn != NEXT_INSN (BLOCK_END (bb)); - insn = NEXT_INSN (insn)) - { - /* Is insn of form (set (pseudo-reg) ...)? */ - - if (GET_CODE (insn) == INSN - && GET_CODE (PATTERN (insn)) == SET - && GET_CODE (SET_DEST (PATTERN (insn))) == REG - && REGNO (SET_DEST (PATTERN (insn))) >= FIRST_PSEUDO_REGISTER) - { - rtx pat = PATTERN (insn); - rtx src = SET_SRC (pat); - struct expr *expr; - - if (want_to_gcse_p (src) - /* Is the expression recorded? */ - && ((expr = lookup_expr (src)) != NULL) - /* Is the expression available [at the start of the - block]? */ - && TEST_BIT (ae_in[bb], expr->bitmap_index) - /* Are the operands unchanged since the start of the - block? */ - && oprs_not_set_p (src, insn)) - changed |= handle_avail_expr (insn, expr); - } - - /* Keep track of everything modified by this insn. */ - /* ??? Need to be careful w.r.t. mods done to INSN. */ - if (GET_RTX_CLASS (GET_CODE (insn)) == 'i') - mark_oprs_set (insn); - } - } - - return changed; -} - -/* Top level routine to perform one classic GCSE pass. - - Return non-zero if a change was made. */ - -static int -one_classic_gcse_pass (pass) - int pass; -{ - int changed = 0; - - gcse_subst_count = 0; - gcse_create_count = 0; - - alloc_expr_hash_table (max_cuid); - alloc_rd_mem (n_basic_blocks, max_cuid); - compute_expr_hash_table (); - if (gcse_file) - dump_hash_table (gcse_file, "Expression", expr_hash_table, - expr_hash_table_size, n_exprs); - if (n_exprs > 0) - { - compute_kill_rd (); - compute_rd (); - alloc_avail_expr_mem (n_basic_blocks, n_exprs); - compute_ae_gen (); - compute_ae_kill (); - compute_available (); - changed = classic_gcse (); - free_avail_expr_mem (); - } - free_rd_mem (); - free_expr_hash_table (); - - if (gcse_file) - { - fprintf (gcse_file, "\n"); - fprintf (gcse_file, "GCSE of %s, pass %d: %d bytes needed, %d substs, %d insns created\n", - current_function_name, pass, - bytes_used, gcse_subst_count, gcse_create_count); - } - - return changed; -} - -/* Compute copy/constant propagation working variables. */ - -/* Local properties of assignments. */ - -static sbitmap *cprop_pavloc; -static sbitmap *cprop_absaltered; - -/* Global properties of assignments (computed from the local properties). */ - -static sbitmap *cprop_avin; -static sbitmap *cprop_avout; - -/* Allocate vars used for copy/const propagation. - N_BLOCKS is the number of basic blocks. - N_SETS is the number of sets. */ - -static void -alloc_cprop_mem (n_blocks, n_sets) - int n_blocks, n_sets; -{ - cprop_pavloc = sbitmap_vector_alloc (n_blocks, n_sets); - cprop_absaltered = sbitmap_vector_alloc (n_blocks, n_sets); - - cprop_avin = sbitmap_vector_alloc (n_blocks, n_sets); - cprop_avout = sbitmap_vector_alloc (n_blocks, n_sets); -} - -/* Free vars used by copy/const propagation. */ - -static void -free_cprop_mem () -{ - free (cprop_pavloc); - free (cprop_absaltered); - free (cprop_avin); - free (cprop_avout); -} - -/* For each block, compute whether X is transparent. - X is either an expression or an assignment [though we don't care which, - for this context an assignment is treated as an expression]. - For each block where an element of X is modified, set (SET_P == 1) or reset - (SET_P == 0) the INDX bit in BMAP. */ - -static void -compute_transp (x, indx, bmap, set_p) - rtx x; - int indx; - sbitmap *bmap; - int set_p; -{ - int bb,i; - enum rtx_code code; - char *fmt; - - /* repeat is used to turn tail-recursion into iteration. */ - repeat: - - if (x == 0) - return; - - code = GET_CODE (x); - switch (code) - { - case REG: - { - reg_set *r; - int regno = REGNO (x); - - if (set_p) - { - if (regno < FIRST_PSEUDO_REGISTER) - { - for (bb = 0; bb < n_basic_blocks; bb++) - if (TEST_BIT (reg_set_in_block[bb], regno)) - SET_BIT (bmap[bb], indx); - } - else - { - for (r = reg_set_table[regno]; r != NULL; r = r->next) - { - bb = BLOCK_NUM (r->insn); - SET_BIT (bmap[bb], indx); - } - } - } - else - { - if (regno < FIRST_PSEUDO_REGISTER) - { - for (bb = 0; bb < n_basic_blocks; bb++) - if (TEST_BIT (reg_set_in_block[bb], regno)) - RESET_BIT (bmap[bb], indx); - } - else - { - for (r = reg_set_table[regno]; r != NULL; r = r->next) - { - bb = BLOCK_NUM (r->insn); - RESET_BIT (bmap[bb], indx); - } - } - } - return; - } - - case MEM: - if (set_p) - { - for (bb = 0; bb < n_basic_blocks; bb++) - if (mem_set_in_block[bb]) - SET_BIT (bmap[bb], indx); - } - else - { - for (bb = 0; bb < n_basic_blocks; bb++) - if (mem_set_in_block[bb]) - RESET_BIT (bmap[bb], indx); - } - x = XEXP (x, 0); - goto repeat; - - case PC: - case CC0: /*FIXME*/ - case CONST: - case CONST_INT: - case CONST_DOUBLE: - case SYMBOL_REF: - case LABEL_REF: - case ADDR_VEC: - case ADDR_DIFF_VEC: - return; - - default: - break; - } - - i = GET_RTX_LENGTH (code) - 1; - fmt = GET_RTX_FORMAT (code); - for (; i >= 0; i--) - { - if (fmt[i] == 'e') - { - rtx tem = XEXP (x, i); - - /* If we are about to do the last recursive call - needed at this level, change it into iteration. - This function is called enough to be worth it. */ - if (i == 0) - { - x = tem; - goto repeat; - } - compute_transp (tem, indx, bmap, set_p); - } - else if (fmt[i] == 'E') - { - int j; - for (j = 0; j < XVECLEN (x, i); j++) - compute_transp (XVECEXP (x, i, j), indx, bmap, set_p); - } - } -} - -/* Compute the available expressions at the start and end of each - basic block for cprop. This particular dataflow equation is - used often enough that we might want to generalize it and make - as a subroutine for other global optimizations that need available - in/out information. */ -static void -compute_cprop_avinout () -{ - int bb, changed, passes; - - sbitmap_zero (cprop_avin[0]); - sbitmap_vector_ones (cprop_avout, n_basic_blocks); - - passes = 0; - changed = 1; - while (changed) - { - changed = 0; - for (bb = 0; bb < n_basic_blocks; bb++) - { - if (bb != 0) - sbitmap_intersect_of_predecessors (cprop_avin[bb], - cprop_avout, bb, s_preds); - changed |= sbitmap_union_of_diff (cprop_avout[bb], - cprop_pavloc[bb], - cprop_avin[bb], - cprop_absaltered[bb]); - } - passes++; - } - - if (gcse_file) - fprintf (gcse_file, "cprop avail expr computation: %d passes\n", passes); -} - -/* Top level routine to do the dataflow analysis needed by copy/const - propagation. */ - -static void -compute_cprop_data () -{ - compute_local_properties (cprop_absaltered, cprop_pavloc, NULL, 1); - compute_cprop_avinout (); -} - -/* Copy/constant propagation. */ - -struct reg_use { - rtx reg_rtx; -}; - -/* Maximum number of register uses in an insn that we handle. */ -#define MAX_USES 8 - -/* Table of uses found in an insn. - Allocated statically to avoid alloc/free complexity and overhead. */ -static struct reg_use reg_use_table[MAX_USES]; - -/* Index into `reg_use_table' while building it. */ -static int reg_use_count; - -/* Set up a list of register numbers used in INSN. - The found uses are stored in `reg_use_table'. - `reg_use_count' is initialized to zero before entry, and - contains the number of uses in the table upon exit. - - ??? If a register appears multiple times we will record it multiple - times. This doesn't hurt anything but it will slow things down. */ - -static void -find_used_regs (x) - rtx x; -{ - int i; - enum rtx_code code; - char *fmt; - - /* repeat is used to turn tail-recursion into iteration. */ - repeat: - - if (x == 0) - return; - - code = GET_CODE (x); - switch (code) - { - case REG: - if (reg_use_count == MAX_USES) - return; - reg_use_table[reg_use_count].reg_rtx = x; - reg_use_count++; - return; - - case MEM: - x = XEXP (x, 0); - goto repeat; - - case PC: - case CC0: - case CONST: - case CONST_INT: - case CONST_DOUBLE: - case SYMBOL_REF: - case LABEL_REF: - case CLOBBER: - case ADDR_VEC: - case ADDR_DIFF_VEC: - case ASM_INPUT: /*FIXME*/ - return; - - case SET: - if (GET_CODE (SET_DEST (x)) == MEM) - find_used_regs (SET_DEST (x)); - x = SET_SRC (x); - goto repeat; - - default: - break; - } - - /* Recursively scan the operands of this expression. */ - - fmt = GET_RTX_FORMAT (code); - for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) - { - if (fmt[i] == 'e') - { - /* If we are about to do the last recursive call - needed at this level, change it into iteration. - This function is called enough to be worth it. */ - if (i == 0) - { - x = XEXP (x, 0); - goto repeat; - } - find_used_regs (XEXP (x, i)); - } - else if (fmt[i] == 'E') - { - int j; - for (j = 0; j < XVECLEN (x, i); j++) - find_used_regs (XVECEXP (x, i, j)); - } - } -} - -/* Try to replace all non-SET_DEST occurrences of FROM in INSN with TO. - Returns non-zero is successful. */ - -static int -try_replace_reg (from, to, insn) - rtx from, to, insn; -{ - /* If this fails we could try to simplify the result of the - replacement and attempt to recognize the simplified insn. - - But we need a general simplify_rtx that doesn't have pass - specific state variables. I'm not aware of one at the moment. */ - return validate_replace_src (from, to, insn); -} - -/* Find a set of REGNO that is available on entry to INSN's block. - Returns NULL if not found. */ - -static struct expr * -find_avail_set (regno, insn) - int regno; - rtx insn; -{ - struct expr *set = lookup_set (regno, NULL_RTX); - - while (set) - { - if (TEST_BIT (cprop_avin[BLOCK_NUM (insn)], set->bitmap_index)) - break; - set = next_set (regno, set); - } - - return set; -} - -/* Perform constant and copy propagation on INSN. - The result is non-zero if a change was made. */ - -static int -cprop_insn (insn, alter_jumps) - rtx insn; - int alter_jumps; -{ - struct reg_use *reg_used; - int changed = 0; - - /* Only propagate into SETs. Note that a conditional jump is a - SET with pc_rtx as the destination. */ - if ((GET_CODE (insn) != INSN - && GET_CODE (insn) != JUMP_INSN) - || GET_CODE (PATTERN (insn)) != SET) - return 0; - - reg_use_count = 0; - find_used_regs (PATTERN (insn)); - - reg_used = ®_use_table[0]; - for ( ; reg_use_count > 0; reg_used++, reg_use_count--) - { - rtx pat, src; - struct expr *set; - int regno = REGNO (reg_used->reg_rtx); - - /* Ignore registers created by GCSE. - We do this because ... */ - if (regno >= max_gcse_regno) - continue; - - /* If the register has already been set in this block, there's - nothing we can do. */ - if (! oprs_not_set_p (reg_used->reg_rtx, insn)) - continue; - - /* Find an assignment that sets reg_used and is available - at the start of the block. */ - set = find_avail_set (regno, insn); - if (! set) - continue; - - pat = set->expr; - /* ??? We might be able to handle PARALLELs. Later. */ - if (GET_CODE (pat) != SET) - abort (); - src = SET_SRC (pat); - - /* Constant propagation. */ - if (GET_CODE (src) == CONST_INT || GET_CODE (src) == CONST_DOUBLE) - { - /* Handle normal insns first. */ - if (GET_CODE (insn) == INSN - && try_replace_reg (reg_used->reg_rtx, src, insn)) - { - changed = 1; - const_prop_count++; - if (gcse_file != NULL) - { - fprintf (gcse_file, "CONST-PROP: Replacing reg %d in insn %d with constant ", - regno, INSN_UID (insn)); - print_rtl (gcse_file, src); - fprintf (gcse_file, "\n"); - } - - /* The original insn setting reg_used may or may not now be - deletable. We leave the deletion to flow. */ - } - - /* Try to propagate a CONST_INT into a conditional jump. - We're pretty specific about what we will handle in this - code, we can extend this as necessary over time. - - Right now the insn in question must look like - - (set (pc) (if_then_else ...)) - - Note this does not currently handle machines which use cc0. */ - else if (alter_jumps - && GET_CODE (insn) == JUMP_INSN - && condjump_p (insn) - && ! simplejump_p (insn)) - { - /* We want a copy of the JUMP_INSN so we can modify it - in-place as needed without effecting the original. */ - rtx copy = copy_rtx (insn); - rtx set = PATTERN (copy); - rtx temp; - - /* Replace the register with the appropriate constant. */ - replace_rtx (SET_SRC (set), reg_used->reg_rtx, src); - - temp = simplify_ternary_operation (GET_CODE (SET_SRC (set)), - GET_MODE (SET_SRC (set)), - GET_MODE (XEXP (SET_SRC (set), 0)), - XEXP (SET_SRC (set), 0), - XEXP (SET_SRC (set), 1), - XEXP (SET_SRC (set), 2)); - - /* If no simplification can be made, then try the next - register. */ - if (temp) - SET_SRC (set) = temp; - else - continue; - - /* That may have changed the structure of TEMP, so - force it to be rerecognized if it has not turned - into a nop or unconditional jump. */ - - INSN_CODE (copy) = -1; - if ((SET_DEST (set) == pc_rtx - && (SET_SRC (set) == pc_rtx - || GET_CODE (SET_SRC (set)) == LABEL_REF)) - || recog (PATTERN (copy), copy, NULL) >= 0) - { - /* This has either become an unconditional jump - or a nop-jump. We'd like to delete nop jumps - here, but doing so confuses gcse. So we just - make the replacement and let later passes - sort things out. */ - PATTERN (insn) = set; - INSN_CODE (insn) = -1; - - /* One less use of the label this insn used to jump to - if we turned this into a NOP jump. */ - if (SET_SRC (set) == pc_rtx && JUMP_LABEL (insn) != 0) - --LABEL_NUSES (JUMP_LABEL (insn)); - - /* If this has turned into an unconditional jump, - then put a barrier after it so that the unreachable - code will be deleted. */ - if (GET_CODE (SET_SRC (set)) == LABEL_REF) - emit_barrier_after (insn); - - run_jump_opt_after_gcse = 1; - - changed = 1; - const_prop_count++; - if (gcse_file != NULL) - { - fprintf (gcse_file, "CONST-PROP: Replacing reg %d in insn %d with constant ", - regno, INSN_UID (insn)); - print_rtl (gcse_file, src); - fprintf (gcse_file, "\n"); - } - } - } - } - else if (GET_CODE (src) == REG - && REGNO (src) >= FIRST_PSEUDO_REGISTER - && REGNO (src) != regno) - { - /* We know the set is available. - Now check that SET_SRC is ANTLOC (i.e. none of the source operands - have changed since the start of the block). */ - if (oprs_not_set_p (src, insn)) - { - if (try_replace_reg (reg_used->reg_rtx, src, insn)) - { - changed = 1; - copy_prop_count++; - if (gcse_file != NULL) - { - fprintf (gcse_file, "COPY-PROP: Replacing reg %d in insn %d with reg %d\n", - regno, INSN_UID (insn), REGNO (src)); - } - - /* The original insn setting reg_used may or may not now be - deletable. We leave the deletion to flow. */ - /* FIXME: If it turns out that the insn isn't deletable, - then we may have unnecessarily extended register lifetimes - and made things worse. */ - } - } - } - } - - return changed; -} - -/* Forward propagate copies. - This includes copies and constants. - Return non-zero if a change was made. */ - -static int -cprop (alter_jumps) - int alter_jumps; -{ - int bb, changed; - rtx insn; - - /* Note we start at block 1. */ - - changed = 0; - for (bb = 1; bb < n_basic_blocks; bb++) - { - /* Reset tables used to keep track of what's still valid [since the - start of the block]. */ - reset_opr_set_tables (); - - for (insn = BLOCK_HEAD (bb); - insn != NULL && insn != NEXT_INSN (BLOCK_END (bb)); - insn = NEXT_INSN (insn)) - { - if (GET_RTX_CLASS (GET_CODE (insn)) == 'i') - { - changed |= cprop_insn (insn, alter_jumps); - - /* Keep track of everything modified by this insn. */ - /* ??? Need to be careful w.r.t. mods done to INSN. */ - mark_oprs_set (insn); - } - } - } - - if (gcse_file != NULL) - fprintf (gcse_file, "\n"); - - return changed; -} - -/* Perform one copy/constant propagation pass. - F is the first insn in the function. - PASS is the pass count. */ - -static int -one_cprop_pass (pass, alter_jumps) - int pass; - int alter_jumps; -{ - int changed = 0; - - const_prop_count = 0; - copy_prop_count = 0; - - alloc_set_hash_table (max_cuid); - compute_set_hash_table (); - if (gcse_file) - dump_hash_table (gcse_file, "SET", set_hash_table, set_hash_table_size, - n_sets); - if (n_sets > 0) - { - alloc_cprop_mem (n_basic_blocks, n_sets); - compute_cprop_data (); - changed = cprop (alter_jumps); - free_cprop_mem (); - } - free_set_hash_table (); - - if (gcse_file) - { - fprintf (gcse_file, "CPROP of %s, pass %d: %d bytes needed, %d const props, %d copy props\n", - current_function_name, pass, - bytes_used, const_prop_count, copy_prop_count); - fprintf (gcse_file, "\n"); - } - - return changed; -} - -/* Compute PRE+LCM working variables. */ - -/* Local properties of expressions. */ -/* Nonzero for expressions that are transparent in the block. */ -static sbitmap *transp; - -/* Nonzero for expressions that are transparent at the end of the block. - This is only zero for expressions killed by abnormal critical edge - created by a calls. */ -static sbitmap *transpout; - -/* Nonzero for expressions that are computed (available) in the block. */ -static sbitmap *comp; - -/* Nonzero for expressions that are locally anticipatable in the block. */ -static sbitmap *antloc; - -/* Nonzero for expressions where this block is an optimal computation - point. */ -static sbitmap *pre_optimal; - -/* Nonzero for expressions which are redundant in a particular block. */ -static sbitmap *pre_redundant; - -static sbitmap *temp_bitmap; - -/* Redundant insns. */ -static sbitmap pre_redundant_insns; - -/* Allocate vars used for PRE analysis. */ - -static void -alloc_pre_mem (n_blocks, n_exprs) - int n_blocks, n_exprs; -{ - transp = sbitmap_vector_alloc (n_blocks, n_exprs); - comp = sbitmap_vector_alloc (n_blocks, n_exprs); - antloc = sbitmap_vector_alloc (n_blocks, n_exprs); - - temp_bitmap = sbitmap_vector_alloc (n_blocks, n_exprs); - pre_optimal = sbitmap_vector_alloc (n_blocks, n_exprs); - pre_redundant = sbitmap_vector_alloc (n_blocks, n_exprs); - transpout = sbitmap_vector_alloc (n_blocks, n_exprs); -} - -/* Free vars used for PRE analysis. */ - -static void -free_pre_mem () -{ - free (transp); - free (comp); - free (antloc); - - free (pre_optimal); - free (pre_redundant); - free (transpout); -} - -/* Top level routine to do the dataflow analysis needed by PRE. */ - -static void -compute_pre_data () -{ - compute_local_properties (transp, comp, antloc, 0); - compute_transpout (); - pre_lcm (n_basic_blocks, n_exprs, s_preds, s_succs, transp, - antloc, pre_redundant, pre_optimal); -} - - -/* PRE utilities */ - -/* Return non-zero if an occurrence of expression EXPR in OCCR_BB would reach - block BB. - - VISITED is a pointer to a working buffer for tracking which BB's have - been visited. It is NULL for the top-level call. - - CHECK_PRE_COMP controls whether or not we check for a computation of - EXPR in OCCR_BB. - - We treat reaching expressions that go through blocks containing the same - reaching expression as "not reaching". E.g. if EXPR is generated in blocks - 2 and 3, INSN is in block 4, and 2->3->4, we treat the expression in block - 2 as not reaching. The intent is to improve the probability of finding - only one reaching expression and to reduce register lifetimes by picking - the closest such expression. */ - -static int -pre_expr_reaches_here_p (occr_bb, expr, bb, check_pre_comp, visited) - int occr_bb; - struct expr *expr; - int bb; - int check_pre_comp; - char *visited; -{ - int_list_ptr pred; - - if (visited == NULL) - { - visited = (char *) alloca (n_basic_blocks); - bzero (visited, n_basic_blocks); - } - - for (pred = s_preds[bb]; pred != NULL; pred = pred->next) - { - int pred_bb = INT_LIST_VAL (pred); - - if (pred_bb == ENTRY_BLOCK - /* Has predecessor has already been visited? */ - || visited[pred_bb]) - { - /* Nothing to do. */ - } - /* Does this predecessor generate this expression? */ - else if ((!check_pre_comp && occr_bb == pred_bb) - || TEST_BIT (comp[pred_bb], expr->bitmap_index)) - { - /* Is this the occurrence we're looking for? - Note that there's only one generating occurrence per block - so we just need to check the block number. */ - if (occr_bb == pred_bb) - return 1; - visited[pred_bb] = 1; - } - /* Ignore this predecessor if it kills the expression. */ - else if (! TEST_BIT (transp[pred_bb], expr->bitmap_index)) - visited[pred_bb] = 1; - /* Neither gen nor kill. */ - else - { - visited[pred_bb] = 1; - if (pre_expr_reaches_here_p (occr_bb, expr, pred_bb, - check_pre_comp, visited)) - return 1; - } - } - - /* All paths have been checked. */ - return 0; -} - -/* Add EXPR to the end of basic block BB. - - This is used by both the PRE and code hoisting. - - For PRE, we want to verify that the expr is either transparent - or locally anticipatable in the target block. This check makes - no sense for code hoisting. */ - -static void -insert_insn_end_bb (expr, bb, pre) - struct expr *expr; - int bb; - int pre; -{ - rtx insn = BLOCK_END (bb); - rtx new_insn; - rtx reg = expr->reaching_reg; - int regno = REGNO (reg); - rtx pat, copied_expr; - rtx first_new_insn; - - start_sequence (); - copied_expr = copy_rtx (expr->expr); - emit_move_insn (reg, copied_expr); - first_new_insn = get_insns (); - pat = gen_sequence (); - end_sequence (); - - /* If the last insn is a jump, insert EXPR in front [taking care to - handle cc0, etc. properly]. */ - - if (GET_CODE (insn) == JUMP_INSN) - { -#ifdef HAVE_cc0 - rtx note; -#endif - - /* If this is a jump table, then we can't insert stuff here. Since - we know the previous real insn must be the tablejump, we insert - the new instruction just before the tablejump. */ - if (GET_CODE (PATTERN (insn)) == ADDR_VEC - || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC) - insn = prev_real_insn (insn); - -#ifdef HAVE_cc0 - /* FIXME: 'twould be nice to call prev_cc0_setter here but it aborts - if cc0 isn't set. */ - note = find_reg_note (insn, REG_CC_SETTER, NULL_RTX); - if (note) - insn = XEXP (note, 0); - else - { - rtx maybe_cc0_setter = prev_nonnote_insn (insn); - if (maybe_cc0_setter - && GET_RTX_CLASS (GET_CODE (maybe_cc0_setter)) == 'i' - && sets_cc0_p (PATTERN (maybe_cc0_setter))) - insn = maybe_cc0_setter; - } -#endif - /* FIXME: What if something in cc0/jump uses value set in new insn? */ - new_insn = emit_insn_before (pat, insn); - if (BLOCK_HEAD (bb) == insn) - BLOCK_HEAD (bb) = new_insn; - } - /* Likewise if the last insn is a call, as will happen in the presence - of exception handling. */ - else if (GET_CODE (insn) == CALL_INSN) - { - HARD_REG_SET parm_regs; - int nparm_regs; - rtx p; - - /* Keeping in mind SMALL_REGISTER_CLASSES and parameters in registers, - we search backward and place the instructions before the first - parameter is loaded. Do this for everyone for consistency and a - presumtion that we'll get better code elsewhere as well. */ - - /* It should always be the case that we can put these instructions - anywhere in the basic block with performing PRE optimizations. - Check this. */ - if (pre - && !TEST_BIT (antloc[bb], expr->bitmap_index) - && !TEST_BIT (transp[bb], expr->bitmap_index)) - abort (); - - /* Since different machines initialize their parameter registers - in different orders, assume nothing. Collect the set of all - parameter registers. */ - CLEAR_HARD_REG_SET (parm_regs); - nparm_regs = 0; - for (p = CALL_INSN_FUNCTION_USAGE (insn); p ; p = XEXP (p, 1)) - if (GET_CODE (XEXP (p, 0)) == USE - && GET_CODE (XEXP (XEXP (p, 0), 0)) == REG) - { - int regno = REGNO (XEXP (XEXP (p, 0), 0)); - if (regno >= FIRST_PSEUDO_REGISTER) - abort (); - SET_HARD_REG_BIT (parm_regs, regno); - nparm_regs++; - } - - /* Search backward for the first set of a register in this set. */ - while (nparm_regs && BLOCK_HEAD (bb) != insn) - { - insn = PREV_INSN (insn); - p = single_set (insn); - if (p && GET_CODE (SET_DEST (p)) == REG - && REGNO (SET_DEST (p)) < FIRST_PSEUDO_REGISTER - && TEST_HARD_REG_BIT (parm_regs, REGNO (SET_DEST (p)))) - { - CLEAR_HARD_REG_BIT (parm_regs, REGNO (SET_DEST (p))); - nparm_regs--; - } - } - - /* If we found all the parameter loads, then we want to insert - before the first parameter load. - - If we did not find all the parameter loads, then we might have - stopped on the head of the block, which could be a CODE_LABEL. - If we inserted before the CODE_LABEL, then we would be putting - the insn in the wrong basic block. In that case, put the insn - after the CODE_LABEL. - - ?!? Do we need to account for NOTE_INSN_BASIC_BLOCK here? */ - if (GET_CODE (insn) != CODE_LABEL) - { - new_insn = emit_insn_before (pat, insn); - if (BLOCK_HEAD (bb) == insn) - BLOCK_HEAD (bb) = new_insn; - } - else - { - new_insn = emit_insn_after (pat, insn); - } - } - else - { - new_insn = emit_insn_after (pat, insn); - BLOCK_END (bb) = new_insn; - } - - /* Keep block number table up to date. - Note, PAT could be a multiple insn sequence, we have to make - sure that each insn in the sequence is handled. */ - if (GET_CODE (pat) == SEQUENCE) - { - int i; - - for (i = 0; i < XVECLEN (pat, 0); i++) - { - rtx insn = XVECEXP (pat, 0, i); - set_block_num (insn, bb); - if (GET_RTX_CLASS (GET_CODE (insn)) == 'i') - add_label_notes (PATTERN (insn), new_insn); - record_set_insn = insn; - note_stores (PATTERN (insn), record_set_info); - } - } - else - { - add_label_notes (SET_SRC (pat), new_insn); - set_block_num (new_insn, bb); - /* Keep register set table up to date. */ - record_one_set (regno, new_insn); - } - - gcse_create_count++; - - if (gcse_file) - { - fprintf (gcse_file, "PRE/HOIST: end of bb %d, insn %d, copying expression %d to reg %d\n", - bb, INSN_UID (new_insn), expr->bitmap_index, regno); - } -} - -/* Insert partially redundant expressions at the ends of appropriate basic - blocks making them fully redundant. */ - -static void -pre_insert (index_map) - struct expr **index_map; -{ - int bb, i, set_size; - sbitmap *inserted; - - /* Compute INSERT = PRE_OPTIMAL & ~PRE_REDUNDANT. - Where INSERT is nonzero, we add the expression at the end of the basic - block if it reaches any of the deleted expressions. */ - - set_size = pre_optimal[0]->size; - inserted = sbitmap_vector_alloc (n_basic_blocks, n_exprs); - sbitmap_vector_zero (inserted, n_basic_blocks); - - for (bb = 0; bb < n_basic_blocks; bb++) - { - int indx; - - /* This computes the number of potential insertions we need. */ - sbitmap_not (temp_bitmap[bb], pre_redundant[bb]); - sbitmap_a_and_b (temp_bitmap[bb], temp_bitmap[bb], pre_optimal[bb]); - - /* TEMP_BITMAP[bb] now contains a bitmap of the expressions that we need - to insert at the end of this basic block. */ - for (i = indx = 0; i < set_size; i++, indx += SBITMAP_ELT_BITS) - { - SBITMAP_ELT_TYPE insert = temp_bitmap[bb]->elms[i]; - int j; - - for (j = indx; insert && j < n_exprs; j++, insert >>= 1) - { - if ((insert & 1) != 0 && index_map[j]->reaching_reg != NULL_RTX) - { - struct expr *expr = index_map[j]; - struct occr *occr; - - /* Now look at each deleted occurence of this expression. */ - for (occr = expr->antic_occr; occr != NULL; occr = occr->next) - { - if (! occr->deleted_p) - continue; - - /* Insert this expression at the end of BB if it would - reach the deleted occurence. */ - if (!TEST_BIT (inserted[bb], j) - && pre_expr_reaches_here_p (bb, expr, - BLOCK_NUM (occr->insn), 0, - NULL)) - { - SET_BIT (inserted[bb], j); - insert_insn_end_bb (index_map[j], bb, 1); - } - } - } - } - } - } -} - -/* Copy the result of INSN to REG. - INDX is the expression number. */ - -static void -pre_insert_copy_insn (expr, insn) - struct expr *expr; - rtx insn; -{ - rtx reg = expr->reaching_reg; - int regno = REGNO (reg); - int indx = expr->bitmap_index; - rtx set = single_set (insn); - rtx new_insn; - - if (!set) - abort (); - new_insn = emit_insn_after (gen_rtx_SET (VOIDmode, reg, SET_DEST (set)), - insn); - /* Keep block number table up to date. */ - set_block_num (new_insn, BLOCK_NUM (insn)); - /* Keep register set table up to date. */ - record_one_set (regno, new_insn); - - gcse_create_count++; - - if (gcse_file) - { - fprintf (gcse_file, "PRE: bb %d, insn %d, copying expression %d in insn %d to reg %d\n", - BLOCK_NUM (insn), INSN_UID (new_insn), indx, INSN_UID (insn), regno); - } -} - -/* Copy available expressions that reach the redundant expression - to `reaching_reg'. */ - -static void -pre_insert_copies () -{ - int i, bb; - - for (bb = 0; bb < n_basic_blocks; bb++) - { - sbitmap_a_and_b (temp_bitmap[bb], pre_optimal[bb], pre_redundant[bb]); - } - - /* For each available expression in the table, copy the result to - `reaching_reg' if the expression reaches a deleted one. - - ??? The current algorithm is rather brute force. - Need to do some profiling. */ - - for (i = 0; i < expr_hash_table_size; i++) - { - struct expr *expr; - - for (expr = expr_hash_table[i]; expr != NULL; expr = expr->next_same_hash) - { - struct occr *occr; - - /* If the basic block isn't reachable, PPOUT will be TRUE. - However, we don't want to insert a copy here because the - expression may not really be redundant. So only insert - an insn if the expression was deleted. - This test also avoids further processing if the expression - wasn't deleted anywhere. */ - if (expr->reaching_reg == NULL) - continue; - - for (occr = expr->antic_occr; occr != NULL; occr = occr->next) - { - struct occr *avail; - - if (! occr->deleted_p) - continue; - - for (avail = expr->avail_occr; avail != NULL; avail = avail->next) - { - rtx insn = avail->insn; - int bb = BLOCK_NUM (insn); - - if (!TEST_BIT (temp_bitmap[bb], expr->bitmap_index)) - continue; - - /* No need to handle this one if handled already. */ - if (avail->copied_p) - continue; - /* Don't handle this one if it's a redundant one. */ - if (TEST_BIT (pre_redundant_insns, INSN_CUID (insn))) - continue; - /* Or if the expression doesn't reach the deleted one. */ - if (! pre_expr_reaches_here_p (BLOCK_NUM (avail->insn), expr, - BLOCK_NUM (occr->insn), - 1, NULL)) - continue; - - /* Copy the result of avail to reaching_reg. */ - pre_insert_copy_insn (expr, insn); - avail->copied_p = 1; - } - } - } - } -} - -/* Delete redundant computations. - Deletion is done by changing the insn to copy the `reaching_reg' of - the expression into the result of the SET. It is left to later passes - (cprop, cse2, flow, combine, regmove) to propagate the copy or eliminate it. - - Returns non-zero if a change is made. */ - -static int -pre_delete () -{ - int i, bb, changed; - - /* Compute the expressions which are redundant and need to be replaced by - copies from the reaching reg to the target reg. */ - for (bb = 0; bb < n_basic_blocks; bb++) - { - sbitmap_not (temp_bitmap[bb], pre_optimal[bb]); - sbitmap_a_and_b (temp_bitmap[bb], temp_bitmap[bb], pre_redundant[bb]); - } - - changed = 0; - for (i = 0; i < expr_hash_table_size; i++) - { - struct expr *expr; - - for (expr = expr_hash_table[i]; expr != NULL; expr = expr->next_same_hash) - { - struct occr *occr; - int indx = expr->bitmap_index; - - /* We only need to search antic_occr since we require - ANTLOC != 0. */ - - for (occr = expr->antic_occr; occr != NULL; occr = occr->next) - { - rtx insn = occr->insn; - rtx set; - int bb = BLOCK_NUM (insn); - - if (TEST_BIT (temp_bitmap[bb], indx)) - { - set = single_set (insn); - if (! set) - abort (); - - /* Create a pseudo-reg to store the result of reaching - expressions into. Get the mode for the new pseudo - from the mode of the original destination pseudo. */ - if (expr->reaching_reg == NULL) - expr->reaching_reg - = gen_reg_rtx (GET_MODE (SET_DEST (set))); - - /* In theory this should never fail since we're creating - a reg->reg copy. - - However, on the x86 some of the movXX patterns actually - contain clobbers of scratch regs. This may cause the - insn created by validate_change to not match any pattern - and thus cause validate_change to fail. */ - if (validate_change (insn, &SET_SRC (set), - expr->reaching_reg, 0)) - { - occr->deleted_p = 1; - SET_BIT (pre_redundant_insns, INSN_CUID (insn)); - changed = 1; - gcse_subst_count++; - } - - if (gcse_file) - { - fprintf (gcse_file, - "PRE: redundant insn %d (expression %d) in bb %d, reaching reg is %d\n", - INSN_UID (insn), indx, bb, REGNO (expr->reaching_reg)); - } - } - } - } - } - - return changed; -} - -/* Perform GCSE optimizations using PRE. - This is called by one_pre_gcse_pass after all the dataflow analysis - has been done. - - This is based on the original Morel-Renvoise paper Fred Chow's thesis, - and lazy code motion from Knoop, Ruthing and Steffen as described in - Advanced Compiler Design and Implementation. - - ??? A new pseudo reg is created to hold the reaching expression. - The nice thing about the classical approach is that it would try to - use an existing reg. If the register can't be adequately optimized - [i.e. we introduce reload problems], one could add a pass here to - propagate the new register through the block. - - ??? We don't handle single sets in PARALLELs because we're [currently] - not able to copy the rest of the parallel when we insert copies to create - full redundancies from partial redundancies. However, there's no reason - why we can't handle PARALLELs in the cases where there are no partial - redundancies. */ - -static int -pre_gcse () -{ - int i; - int changed; - struct expr **index_map; - - /* Compute a mapping from expression number (`bitmap_index') to - hash table entry. */ - - index_map = (struct expr **) alloca (n_exprs * sizeof (struct expr *)); - bzero ((char *) index_map, n_exprs * sizeof (struct expr *)); - for (i = 0; i < expr_hash_table_size; i++) - { - struct expr *expr; - - for (expr = expr_hash_table[i]; expr != NULL; expr = expr->next_same_hash) - index_map[expr->bitmap_index] = expr; - } - - /* Reset bitmap used to track which insns are redundant. */ - pre_redundant_insns = sbitmap_alloc (max_cuid); - sbitmap_zero (pre_redundant_insns); - - /* Delete the redundant insns first so that - - we know what register to use for the new insns and for the other - ones with reaching expressions - - we know which insns are redundant when we go to create copies */ - changed = pre_delete (); - - /* Insert insns in places that make partially redundant expressions - fully redundant. */ - pre_insert (index_map); - - /* In other places with reaching expressions, copy the expression to the - specially allocated pseudo-reg that reaches the redundant expression. */ - pre_insert_copies (); - - free (pre_redundant_insns); - - return changed; -} - -/* Top level routine to perform one PRE GCSE pass. - - Return non-zero if a change was made. */ - -static int -one_pre_gcse_pass (pass) - int pass; -{ - int changed = 0; - - gcse_subst_count = 0; - gcse_create_count = 0; - - alloc_expr_hash_table (max_cuid); - compute_expr_hash_table (); - if (gcse_file) - dump_hash_table (gcse_file, "Expression", expr_hash_table, - expr_hash_table_size, n_exprs); - if (n_exprs > 0) - { - alloc_pre_mem (n_basic_blocks, n_exprs); - compute_pre_data (); - changed |= pre_gcse (); - free_pre_mem (); - } - free_expr_hash_table (); - - if (gcse_file) - { - fprintf (gcse_file, "\n"); - fprintf (gcse_file, "PRE GCSE of %s, pass %d: %d bytes needed, %d substs, %d insns created\n", - current_function_name, pass, - bytes_used, gcse_subst_count, gcse_create_count); - } - - return changed; -} - -/* If X contains any LABEL_REF's, add REG_LABEL notes for them to INSN. - We have to add REG_LABEL notes, because the following loop optimization - pass requires them. */ - -/* ??? This is very similar to the loop.c add_label_notes function. We - could probably share code here. */ - -/* ??? If there was a jump optimization pass after gcse and before loop, - then we would not need to do this here, because jump would add the - necessary REG_LABEL notes. */ - -static void -add_label_notes (x, insn) - rtx x; - rtx insn; -{ - enum rtx_code code = GET_CODE (x); - int i, j; - char *fmt; - - if (code == LABEL_REF && !LABEL_REF_NONLOCAL_P (x)) - { - /* This code used to ignore labels that referred to dispatch tables to - avoid flow generating (slighly) worse code. - - We no longer ignore such label references (see LABEL_REF handling in - mark_jump_label for additional information). */ - REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_LABEL, XEXP (x, 0), - REG_NOTES (insn)); - return; - } - - fmt = GET_RTX_FORMAT (code); - for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) - { - if (fmt[i] == 'e') - add_label_notes (XEXP (x, i), insn); - else if (fmt[i] == 'E') - for (j = XVECLEN (x, i) - 1; j >= 0; j--) - add_label_notes (XVECEXP (x, i, j), insn); - } -} - -/* Compute transparent outgoing information for each block. - - An expression is transparent to an edge unless it is killed by - the edge itself. This can only happen with abnormal control flow, - when the edge is traversed through a call. This happens with - non-local labels and exceptions. - - This would not be necessary if we split the edge. While this is - normally impossible for abnormal critical edges, with some effort - it should be possible with exception handling, since we still have - control over which handler should be invoked. But due to increased - EH table sizes, this may not be worthwhile. */ - -static void -compute_transpout () -{ - int bb; - - sbitmap_vector_ones (transpout, n_basic_blocks); - - for (bb = 0; bb < n_basic_blocks; ++bb) - { - int i; - - /* Note that flow inserted a nop a the end of basic blocks that - end in call instructions for reasons other than abnormal - control flow. */ - if (GET_CODE (BLOCK_END (bb)) != CALL_INSN) - continue; - - for (i = 0; i < expr_hash_table_size; i++) - { - struct expr *expr; - for (expr = expr_hash_table[i]; expr ; expr = expr->next_same_hash) - if (GET_CODE (expr->expr) == MEM) - { - rtx addr = XEXP (expr->expr, 0); - - if (GET_CODE (addr) == SYMBOL_REF - && CONSTANT_POOL_ADDRESS_P (addr)) - continue; - - /* ??? Optimally, we would use interprocedural alias - analysis to determine if this mem is actually killed - by this call. */ - RESET_BIT (transpout[bb], expr->bitmap_index); - } - } - } -} |