diff options
Diffstat (limited to 'contrib/gcc/cse.c')
| -rw-r--r-- | contrib/gcc/cse.c | 9267 |
1 files changed, 0 insertions, 9267 deletions
diff --git a/contrib/gcc/cse.c b/contrib/gcc/cse.c deleted file mode 100644 index e315610b3e28..000000000000 --- a/contrib/gcc/cse.c +++ /dev/null @@ -1,9267 +0,0 @@ -/* Common subexpression elimination for GNU compiler. - Copyright (C) 1987, 88, 89, 92-99, 2000 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. */ - - -#include "config.h" -/* stdio.h must precede rtl.h for FFS. */ -#include "system.h" -#include <setjmp.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 "expr.h" -#include "toplev.h" -#include "output.h" -#include "splay-tree.h" - -/* The basic idea of common subexpression elimination is to go - through the code, keeping a record of expressions that would - have the same value at the current scan point, and replacing - expressions encountered with the cheapest equivalent expression. - - It is too complicated to keep track of the different possibilities - when control paths merge in this code; so, at each label, we forget all - that is known and start fresh. This can be described as processing each - extended basic block separately. We have a separate pass to perform - global CSE. - - Note CSE can turn a conditional or computed jump into a nop or - an unconditional jump. When this occurs we arrange to run the jump - optimizer after CSE to delete the unreachable code. - - We use two data structures to record the equivalent expressions: - a hash table for most expressions, and several vectors together - with "quantity numbers" to record equivalent (pseudo) registers. - - The use of the special data structure for registers is desirable - because it is faster. It is possible because registers references - contain a fairly small number, the register number, taken from - a contiguously allocated series, and two register references are - identical if they have the same number. General expressions - do not have any such thing, so the only way to retrieve the - information recorded on an expression other than a register - is to keep it in a hash table. - -Registers and "quantity numbers": - - At the start of each basic block, all of the (hardware and pseudo) - registers used in the function are given distinct quantity - numbers to indicate their contents. During scan, when the code - copies one register into another, we copy the quantity number. - When a register is loaded in any other way, we allocate a new - quantity number to describe the value generated by this operation. - `reg_qty' records what quantity a register is currently thought - of as containing. - - All real quantity numbers are greater than or equal to `max_reg'. - If register N has not been assigned a quantity, reg_qty[N] will equal N. - - Quantity numbers below `max_reg' do not exist and none of the `qty_...' - variables should be referenced with an index below `max_reg'. - - We also maintain a bidirectional chain of registers for each - quantity number. `qty_first_reg', `qty_last_reg', - `reg_next_eqv' and `reg_prev_eqv' hold these chains. - - The first register in a chain is the one whose lifespan is least local. - Among equals, it is the one that was seen first. - We replace any equivalent register with that one. - - If two registers have the same quantity number, it must be true that - REG expressions with `qty_mode' must be in the hash table for both - registers and must be in the same class. - - The converse is not true. Since hard registers may be referenced in - any mode, two REG expressions might be equivalent in the hash table - but not have the same quantity number if the quantity number of one - of the registers is not the same mode as those expressions. - -Constants and quantity numbers - - When a quantity has a known constant value, that value is stored - in the appropriate element of qty_const. This is in addition to - putting the constant in the hash table as is usual for non-regs. - - Whether a reg or a constant is preferred is determined by the configuration - macro CONST_COSTS and will often depend on the constant value. In any - event, expressions containing constants can be simplified, by fold_rtx. - - When a quantity has a known nearly constant value (such as an address - of a stack slot), that value is stored in the appropriate element - of qty_const. - - Integer constants don't have a machine mode. However, cse - determines the intended machine mode from the destination - of the instruction that moves the constant. The machine mode - is recorded in the hash table along with the actual RTL - constant expression so that different modes are kept separate. - -Other expressions: - - To record known equivalences among expressions in general - we use a hash table called `table'. It has a fixed number of buckets - that contain chains of `struct table_elt' elements for expressions. - These chains connect the elements whose expressions have the same - hash codes. - - Other chains through the same elements connect the elements which - currently have equivalent values. - - Register references in an expression are canonicalized before hashing - the expression. This is done using `reg_qty' and `qty_first_reg'. - The hash code of a register reference is computed using the quantity - number, not the register number. - - When the value of an expression changes, it is necessary to remove from the - hash table not just that expression but all expressions whose values - could be different as a result. - - 1. If the value changing is in memory, except in special cases - ANYTHING referring to memory could be changed. That is because - nobody knows where a pointer does not point. - The function `invalidate_memory' removes what is necessary. - - The special cases are when the address is constant or is - a constant plus a fixed register such as the frame pointer - or a static chain pointer. When such addresses are stored in, - we can tell exactly which other such addresses must be invalidated - due to overlap. `invalidate' does this. - All expressions that refer to non-constant - memory addresses are also invalidated. `invalidate_memory' does this. - - 2. If the value changing is a register, all expressions - containing references to that register, and only those, - must be removed. - - Because searching the entire hash table for expressions that contain - a register is very slow, we try to figure out when it isn't necessary. - Precisely, this is necessary only when expressions have been - entered in the hash table using this register, and then the value has - changed, and then another expression wants to be added to refer to - the register's new value. This sequence of circumstances is rare - within any one basic block. - - The vectors `reg_tick' and `reg_in_table' are used to detect this case. - reg_tick[i] is incremented whenever a value is stored in register i. - reg_in_table[i] holds -1 if no references to register i have been - entered in the table; otherwise, it contains the value reg_tick[i] had - when the references were entered. If we want to enter a reference - and reg_in_table[i] != reg_tick[i], we must scan and remove old references. - Until we want to enter a new entry, the mere fact that the two vectors - don't match makes the entries be ignored if anyone tries to match them. - - Registers themselves are entered in the hash table as well as in - the equivalent-register chains. However, the vectors `reg_tick' - and `reg_in_table' do not apply to expressions which are simple - register references. These expressions are removed from the table - immediately when they become invalid, and this can be done even if - we do not immediately search for all the expressions that refer to - the register. - - A CLOBBER rtx in an instruction invalidates its operand for further - reuse. A CLOBBER or SET rtx whose operand is a MEM:BLK - invalidates everything that resides in memory. - -Related expressions: - - Constant expressions that differ only by an additive integer - are called related. When a constant expression is put in - the table, the related expression with no constant term - is also entered. These are made to point at each other - so that it is possible to find out if there exists any - register equivalent to an expression related to a given expression. */ - -/* One plus largest register number used in this function. */ - -static int max_reg; - -/* One plus largest instruction UID used in this function at time of - cse_main call. */ - -static int max_insn_uid; - -/* Length of vectors indexed by quantity number. - We know in advance we will not need a quantity number this big. */ - -static int max_qty; - -/* Next quantity number to be allocated. - This is 1 + the largest number needed so far. */ - -static int next_qty; - -/* Indexed by quantity number, gives the first (or last) register - in the chain of registers that currently contain this quantity. */ - -static int *qty_first_reg; -static int *qty_last_reg; - -/* Index by quantity number, gives the mode of the quantity. */ - -static enum machine_mode *qty_mode; - -/* Indexed by quantity number, gives the rtx of the constant value of the - quantity, or zero if it does not have a known value. - A sum of the frame pointer (or arg pointer) plus a constant - can also be entered here. */ - -static rtx *qty_const; - -/* Indexed by qty number, gives the insn that stored the constant value - recorded in `qty_const'. */ - -static rtx *qty_const_insn; - -/* The next three variables are used to track when a comparison between a - quantity and some constant or register has been passed. In that case, we - know the results of the comparison in case we see it again. These variables - record a comparison that is known to be true. */ - -/* Indexed by qty number, gives the rtx code of a comparison with a known - result involving this quantity. If none, it is UNKNOWN. */ -static enum rtx_code *qty_comparison_code; - -/* Indexed by qty number, gives the constant being compared against in a - comparison of known result. If no such comparison, it is undefined. - If the comparison is not with a constant, it is zero. */ - -static rtx *qty_comparison_const; - -/* Indexed by qty number, gives the quantity being compared against in a - comparison of known result. If no such comparison, if it undefined. - If the comparison is not with a register, it is -1. */ - -static int *qty_comparison_qty; - -#ifdef HAVE_cc0 -/* For machines that have a CC0, we do not record its value in the hash - table since its use is guaranteed to be the insn immediately following - its definition and any other insn is presumed to invalidate it. - - Instead, we store below the value last assigned to CC0. If it should - happen to be a constant, it is stored in preference to the actual - assigned value. In case it is a constant, we store the mode in which - the constant should be interpreted. */ - -static rtx prev_insn_cc0; -static enum machine_mode prev_insn_cc0_mode; -#endif - -/* Previous actual insn. 0 if at first insn of basic block. */ - -static rtx prev_insn; - -/* Insn being scanned. */ - -static rtx this_insn; - -/* Index by register number, gives the number of the next (or - previous) register in the chain of registers sharing the same - value. - - Or -1 if this register is at the end of the chain. - - If reg_qty[N] == N, reg_next_eqv[N] is undefined. */ - -static int *reg_next_eqv; -static int *reg_prev_eqv; - -struct cse_reg_info { - union { - /* The number of times the register has been altered in the current - basic block. */ - int reg_tick; - - /* The next cse_reg_info structure in the free list. */ - struct cse_reg_info* next; - } variant; - - /* The REG_TICK value at which rtx's containing this register are - valid in the hash table. If this does not equal the current - reg_tick value, such expressions existing in the hash table are - invalid. */ - int reg_in_table; - - /* The quantity number of the register's current contents. */ - int reg_qty; -}; - -/* A free list of cse_reg_info entries. */ -static struct cse_reg_info *cse_reg_info_free_list; - -/* A mapping from registers to cse_reg_info data structures. */ -static splay_tree cse_reg_info_tree; - -/* The last lookup we did into the cse_reg_info_tree. This allows us - to cache repeated lookups. */ -static int cached_regno; -static struct cse_reg_info *cached_cse_reg_info; - -/* A HARD_REG_SET containing all the hard registers for which there is - currently a REG expression in the hash table. Note the difference - from the above variables, which indicate if the REG is mentioned in some - expression in the table. */ - -static HARD_REG_SET hard_regs_in_table; - -/* A HARD_REG_SET containing all the hard registers that are invalidated - by a CALL_INSN. */ - -static HARD_REG_SET regs_invalidated_by_call; - -/* CUID of insn that starts the basic block currently being cse-processed. */ - -static int cse_basic_block_start; - -/* CUID of insn that ends the basic block currently being cse-processed. */ - -static int cse_basic_block_end; - -/* Vector mapping INSN_UIDs to cuids. - The cuids are like uids but increase monotonically always. - We use them to see whether a reg is used outside a given basic block. */ - -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)]) - -/* Nonzero if cse has altered conditional jump insns - in such a way that jump optimization should be redone. */ - -static int cse_jumps_altered; - -/* Nonzero if we put a LABEL_REF into the hash table. Since we may have put - it into an INSN without a REG_LABEL, we have to rerun jump after CSE - to put in the note. */ -static int recorded_label_ref; - -/* canon_hash stores 1 in do_not_record - if it notices a reference to CC0, PC, or some other volatile - subexpression. */ - -static int do_not_record; - -#ifdef LOAD_EXTEND_OP - -/* Scratch rtl used when looking for load-extended copy of a MEM. */ -static rtx memory_extend_rtx; -#endif - -/* canon_hash stores 1 in hash_arg_in_memory - if it notices a reference to memory within the expression being hashed. */ - -static int hash_arg_in_memory; - -/* canon_hash stores 1 in hash_arg_in_struct - if it notices a reference to memory that's part of a structure. */ - -static int hash_arg_in_struct; - -/* The hash table contains buckets which are chains of `struct table_elt's, - each recording one expression's information. - That expression is in the `exp' field. - - Those elements with the same hash code are chained in both directions - through the `next_same_hash' and `prev_same_hash' fields. - - Each set of expressions with equivalent values - are on a two-way chain through the `next_same_value' - and `prev_same_value' fields, and all point with - the `first_same_value' field at the first element in - that chain. The chain is in order of increasing cost. - Each element's cost value is in its `cost' field. - - The `in_memory' field is nonzero for elements that - involve any reference to memory. These elements are removed - whenever a write is done to an unidentified location in memory. - To be safe, we assume that a memory address is unidentified unless - the address is either a symbol constant or a constant plus - the frame pointer or argument pointer. - - The `in_struct' field is nonzero for elements that - involve any reference to memory inside a structure or array. - - The `related_value' field is used to connect related expressions - (that differ by adding an integer). - The related expressions are chained in a circular fashion. - `related_value' is zero for expressions for which this - chain is not useful. - - The `cost' field stores the cost of this element's expression. - - The `is_const' flag is set if the element is a constant (including - a fixed address). - - The `flag' field is used as a temporary during some search routines. - - The `mode' field is usually the same as GET_MODE (`exp'), but - if `exp' is a CONST_INT and has no machine mode then the `mode' - field is the mode it was being used as. Each constant is - recorded separately for each mode it is used with. */ - - -struct table_elt -{ - rtx exp; - struct table_elt *next_same_hash; - struct table_elt *prev_same_hash; - struct table_elt *next_same_value; - struct table_elt *prev_same_value; - struct table_elt *first_same_value; - struct table_elt *related_value; - int cost; - enum machine_mode mode; - char in_memory; - char in_struct; - char is_const; - char flag; -}; - -/* We don't want a lot of buckets, because we rarely have very many - things stored in the hash table, and a lot of buckets slows - down a lot of loops that happen frequently. */ -#define NBUCKETS 31 - -/* Compute hash code of X in mode M. Special-case case where X is a pseudo - register (hard registers may require `do_not_record' to be set). */ - -#define HASH(X, M) \ - (GET_CODE (X) == REG && REGNO (X) >= FIRST_PSEUDO_REGISTER \ - ? (((unsigned) REG << 7) + (unsigned) REG_QTY (REGNO (X))) % NBUCKETS \ - : canon_hash (X, M) % NBUCKETS) - -/* Determine whether register number N is considered a fixed register for CSE. - It is desirable to replace other regs with fixed regs, to reduce need for - non-fixed hard regs. - A reg wins if it is either the frame pointer or designated as fixed, - but not if it is an overlapping register. */ -#ifdef OVERLAPPING_REGNO_P -#define FIXED_REGNO_P(N) \ - (((N) == FRAME_POINTER_REGNUM || (N) == HARD_FRAME_POINTER_REGNUM \ - || fixed_regs[N] || global_regs[N]) \ - && ! OVERLAPPING_REGNO_P ((N))) -#else -#define FIXED_REGNO_P(N) \ - ((N) == FRAME_POINTER_REGNUM || (N) == HARD_FRAME_POINTER_REGNUM \ - || fixed_regs[N] || global_regs[N]) -#endif - -/* Compute cost of X, as stored in the `cost' field of a table_elt. Fixed - hard registers and pointers into the frame are the cheapest with a cost - of 0. Next come pseudos with a cost of one and other hard registers with - a cost of 2. Aside from these special cases, call `rtx_cost'. */ - -#define CHEAP_REGNO(N) \ - ((N) == FRAME_POINTER_REGNUM || (N) == HARD_FRAME_POINTER_REGNUM \ - || (N) == STACK_POINTER_REGNUM || (N) == ARG_POINTER_REGNUM \ - || ((N) >= FIRST_VIRTUAL_REGISTER && (N) <= LAST_VIRTUAL_REGISTER) \ - || ((N) < FIRST_PSEUDO_REGISTER \ - && FIXED_REGNO_P (N) && REGNO_REG_CLASS (N) != NO_REGS)) - -/* A register is cheap if it is a user variable assigned to the register - or if its register number always corresponds to a cheap register. */ - -#define CHEAP_REG(N) \ - ((REG_USERVAR_P (N) && REGNO (N) < FIRST_PSEUDO_REGISTER) \ - || CHEAP_REGNO (REGNO (N))) - -#define COST(X) \ - (GET_CODE (X) == REG \ - ? (CHEAP_REG (X) ? 0 \ - : REGNO (X) >= FIRST_PSEUDO_REGISTER ? 1 \ - : 2) \ - : notreg_cost(X)) - -/* Get the info associated with register N. */ - -#define GET_CSE_REG_INFO(N) \ - (((N) == cached_regno && cached_cse_reg_info) \ - ? cached_cse_reg_info : get_cse_reg_info ((N))) - -/* Get the number of times this register has been updated in this - basic block. */ - -#define REG_TICK(N) ((GET_CSE_REG_INFO (N))->variant.reg_tick) - -/* Get the point at which REG was recorded in the table. */ - -#define REG_IN_TABLE(N) ((GET_CSE_REG_INFO (N))->reg_in_table) - -/* Get the quantity number for REG. */ - -#define REG_QTY(N) ((GET_CSE_REG_INFO (N))->reg_qty) - -/* Determine if the quantity number for register X represents a valid index - into the `qty_...' variables. */ - -#define REGNO_QTY_VALID_P(N) (REG_QTY (N) != (N)) - -#ifdef ADDRESS_COST -/* The ADDRESS_COST macro does not deal with ADDRESSOF nodes. But, - during CSE, such nodes are present. Using an ADDRESSOF node which - refers to the address of a REG is a good thing because we can then - turn (MEM (ADDRESSSOF (REG))) into just plain REG. */ -#define CSE_ADDRESS_COST(RTX) \ - ((GET_CODE (RTX) == ADDRESSOF && REG_P (XEXP ((RTX), 0))) \ - ? -1 : ADDRESS_COST(RTX)) -#endif - -static struct table_elt *table[NBUCKETS]; - -/* Chain of `struct table_elt's made so far for this function - but currently removed from the table. */ - -static struct table_elt *free_element_chain; - -/* Number of `struct table_elt' structures made so far for this function. */ - -static int n_elements_made; - -/* Maximum value `n_elements_made' has had so far in this compilation - for functions previously processed. */ - -static int max_elements_made; - -/* Surviving equivalence class when two equivalence classes are merged - by recording the effects of a jump in the last insn. Zero if the - last insn was not a conditional jump. */ - -static struct table_elt *last_jump_equiv_class; - -/* Set to the cost of a constant pool reference if one was found for a - symbolic constant. If this was found, it means we should try to - convert constants into constant pool entries if they don't fit in - the insn. */ - -static int constant_pool_entries_cost; - -/* Define maximum length of a branch path. */ - -#define PATHLENGTH 10 - -/* This data describes a block that will be processed by cse_basic_block. */ - -struct cse_basic_block_data { - /* Lowest CUID value of insns in block. */ - int low_cuid; - /* Highest CUID value of insns in block. */ - int high_cuid; - /* Total number of SETs in block. */ - int nsets; - /* Last insn in the block. */ - rtx last; - /* Size of current branch path, if any. */ - int path_size; - /* Current branch path, indicating which branches will be taken. */ - struct branch_path { - /* The branch insn. */ - rtx branch; - /* Whether it should be taken or not. AROUND is the same as taken - except that it is used when the destination label is not preceded - by a BARRIER. */ - enum taken {TAKEN, NOT_TAKEN, AROUND} status; - } path[PATHLENGTH]; -}; - -/* Nonzero if X has the form (PLUS frame-pointer integer). We check for - virtual regs here because the simplify_*_operation routines are called - by integrate.c, which is called before virtual register instantiation. */ - -#define FIXED_BASE_PLUS_P(X) \ - ((X) == frame_pointer_rtx || (X) == hard_frame_pointer_rtx \ - || (X) == arg_pointer_rtx \ - || (X) == virtual_stack_vars_rtx \ - || (X) == virtual_incoming_args_rtx \ - || (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT \ - && (XEXP (X, 0) == frame_pointer_rtx \ - || XEXP (X, 0) == hard_frame_pointer_rtx \ - || XEXP (X, 0) == arg_pointer_rtx \ - || XEXP (X, 0) == virtual_stack_vars_rtx \ - || XEXP (X, 0) == virtual_incoming_args_rtx)) \ - || GET_CODE (X) == ADDRESSOF) - -/* Similar, but also allows reference to the stack pointer. - - This used to include FIXED_BASE_PLUS_P, however, we can't assume that - arg_pointer_rtx by itself is nonzero, because on at least one machine, - the i960, the arg pointer is zero when it is unused. */ - -#define NONZERO_BASE_PLUS_P(X) \ - ((X) == frame_pointer_rtx || (X) == hard_frame_pointer_rtx \ - || (X) == virtual_stack_vars_rtx \ - || (X) == virtual_incoming_args_rtx \ - || (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT \ - && (XEXP (X, 0) == frame_pointer_rtx \ - || XEXP (X, 0) == hard_frame_pointer_rtx \ - || XEXP (X, 0) == arg_pointer_rtx \ - || XEXP (X, 0) == virtual_stack_vars_rtx \ - || XEXP (X, 0) == virtual_incoming_args_rtx)) \ - || (X) == stack_pointer_rtx \ - || (X) == virtual_stack_dynamic_rtx \ - || (X) == virtual_outgoing_args_rtx \ - || (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT \ - && (XEXP (X, 0) == stack_pointer_rtx \ - || XEXP (X, 0) == virtual_stack_dynamic_rtx \ - || XEXP (X, 0) == virtual_outgoing_args_rtx)) \ - || GET_CODE (X) == ADDRESSOF) - -static int notreg_cost PROTO((rtx)); -static void new_basic_block PROTO((void)); -static void make_new_qty PROTO((int)); -static void make_regs_eqv PROTO((int, int)); -static void delete_reg_equiv PROTO((int)); -static int mention_regs PROTO((rtx)); -static int insert_regs PROTO((rtx, struct table_elt *, int)); -static void free_element PROTO((struct table_elt *)); -static void remove_from_table PROTO((struct table_elt *, unsigned)); -static struct table_elt *get_element PROTO((void)); -static struct table_elt *lookup PROTO((rtx, unsigned, enum machine_mode)), - *lookup_for_remove PROTO((rtx, unsigned, enum machine_mode)); -static rtx lookup_as_function PROTO((rtx, enum rtx_code)); -static struct table_elt *insert PROTO((rtx, struct table_elt *, unsigned, - enum machine_mode)); -static void merge_equiv_classes PROTO((struct table_elt *, - struct table_elt *)); -static void invalidate PROTO((rtx, enum machine_mode)); -static int cse_rtx_varies_p PROTO((rtx)); -static void remove_invalid_refs PROTO((int)); -static void remove_invalid_subreg_refs PROTO((int, int, enum machine_mode)); -static void rehash_using_reg PROTO((rtx)); -static void invalidate_memory PROTO((void)); -static void invalidate_for_call PROTO((void)); -static rtx use_related_value PROTO((rtx, struct table_elt *)); -static unsigned canon_hash PROTO((rtx, enum machine_mode)); -static unsigned safe_hash PROTO((rtx, enum machine_mode)); -static int exp_equiv_p PROTO((rtx, rtx, int, int)); -static void set_nonvarying_address_components PROTO((rtx, int, rtx *, - HOST_WIDE_INT *, - HOST_WIDE_INT *)); -static int refers_to_p PROTO((rtx, rtx)); -static rtx canon_reg PROTO((rtx, rtx)); -static void find_best_addr PROTO((rtx, rtx *)); -static enum rtx_code find_comparison_args PROTO((enum rtx_code, rtx *, rtx *, - enum machine_mode *, - enum machine_mode *)); -static rtx cse_gen_binary PROTO((enum rtx_code, enum machine_mode, - rtx, rtx)); -static rtx simplify_plus_minus PROTO((enum rtx_code, enum machine_mode, - rtx, rtx)); -static rtx fold_rtx PROTO((rtx, rtx)); -static rtx equiv_constant PROTO((rtx)); -static void record_jump_equiv PROTO((rtx, int)); -static void record_jump_cond PROTO((enum rtx_code, enum machine_mode, - rtx, rtx, int)); -static void cse_insn PROTO((rtx, rtx)); -static int note_mem_written PROTO((rtx)); -static void invalidate_from_clobbers PROTO((rtx)); -static rtx cse_process_notes PROTO((rtx, rtx)); -static void cse_around_loop PROTO((rtx)); -static void invalidate_skipped_set PROTO((rtx, rtx)); -static void invalidate_skipped_block PROTO((rtx)); -static void cse_check_loop_start PROTO((rtx, rtx)); -static void cse_set_around_loop PROTO((rtx, rtx, rtx)); -static rtx cse_basic_block PROTO((rtx, rtx, struct branch_path *, int)); -static void count_reg_usage PROTO((rtx, int *, rtx, int)); -extern void dump_class PROTO((struct table_elt*)); -static void check_fold_consts PROTO((PTR)); -static struct cse_reg_info* get_cse_reg_info PROTO((int)); -static void free_cse_reg_info PROTO((splay_tree_value)); -static void flush_hash_table PROTO((void)); - -extern int rtx_equal_function_value_matters; - -/* Dump the expressions in the equivalence class indicated by CLASSP. - This function is used only for debugging. */ -void -dump_class (classp) - struct table_elt *classp; -{ - struct table_elt *elt; - - fprintf (stderr, "Equivalence chain for "); - print_rtl (stderr, classp->exp); - fprintf (stderr, ": \n"); - - for (elt = classp->first_same_value; elt; elt = elt->next_same_value) - { - print_rtl (stderr, elt->exp); - fprintf (stderr, "\n"); - } -} - -/* Return an estimate of the cost of computing rtx X. - One use is in cse, to decide which expression to keep in the hash table. - Another is in rtl generation, to pick the cheapest way to multiply. - Other uses like the latter are expected in the future. */ - -/* Internal function, to compute cost when X is not a register; called - from COST macro to keep it simple. */ - -static int -notreg_cost (x) - rtx x; -{ - return ((GET_CODE (x) == SUBREG - && GET_CODE (SUBREG_REG (x)) == REG - && GET_MODE_CLASS (GET_MODE (x)) == MODE_INT - && GET_MODE_CLASS (GET_MODE (SUBREG_REG (x))) == MODE_INT - && (GET_MODE_SIZE (GET_MODE (x)) - < GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))) - && subreg_lowpart_p (x) - && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (x)), - GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))))) - ? (CHEAP_REG (SUBREG_REG (x)) ? 0 - : (REGNO (SUBREG_REG (x)) >= FIRST_PSEUDO_REGISTER ? 1 - : 2)) - : rtx_cost (x, SET) * 2); -} - -/* Return the right cost to give to an operation - to make the cost of the corresponding register-to-register instruction - N times that of a fast register-to-register instruction. */ - -#define COSTS_N_INSNS(N) ((N) * 4 - 2) - -int -rtx_cost (x, outer_code) - rtx x; - enum rtx_code outer_code ATTRIBUTE_UNUSED; -{ - register int i, j; - register enum rtx_code code; - register char *fmt; - register int total; - - if (x == 0) - return 0; - - /* Compute the default costs of certain things. - Note that RTX_COSTS can override the defaults. */ - - code = GET_CODE (x); - switch (code) - { - case MULT: - /* Count multiplication by 2**n as a shift, - because if we are considering it, we would output it as a shift. */ - if (GET_CODE (XEXP (x, 1)) == CONST_INT - && exact_log2 (INTVAL (XEXP (x, 1))) >= 0) - total = 2; - else - total = COSTS_N_INSNS (5); - break; - case DIV: - case UDIV: - case MOD: - case UMOD: - total = COSTS_N_INSNS (7); - break; - case USE: - /* Used in loop.c and combine.c as a marker. */ - total = 0; - break; - case ASM_OPERANDS: - /* We don't want these to be used in substitutions because - we have no way of validating the resulting insn. So assign - anything containing an ASM_OPERANDS a very high cost. */ - total = 1000; - break; - default: - total = 2; - } - - switch (code) - { - case REG: - return ! CHEAP_REG (x); - - case SUBREG: - /* If we can't tie these modes, make this expensive. The larger - the mode, the more expensive it is. */ - if (! MODES_TIEABLE_P (GET_MODE (x), GET_MODE (SUBREG_REG (x)))) - return COSTS_N_INSNS (2 - + GET_MODE_SIZE (GET_MODE (x)) / UNITS_PER_WORD); - return 2; -#ifdef RTX_COSTS - RTX_COSTS (x, code, outer_code); -#endif -#ifdef CONST_COSTS - CONST_COSTS (x, code, outer_code); -#endif - - default: -#ifdef DEFAULT_RTX_COSTS - DEFAULT_RTX_COSTS(x, code, outer_code); -#endif - break; - } - - /* Sum the costs of the sub-rtx's, plus cost of this operation, - which is already in total. */ - - fmt = GET_RTX_FORMAT (code); - for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) - if (fmt[i] == 'e') - total += rtx_cost (XEXP (x, i), code); - else if (fmt[i] == 'E') - for (j = 0; j < XVECLEN (x, i); j++) - total += rtx_cost (XVECEXP (x, i, j), code); - - return total; -} - -static struct cse_reg_info * -get_cse_reg_info (regno) - int regno; -{ - struct cse_reg_info *cri; - splay_tree_node n; - - /* See if we already have this entry. */ - n = splay_tree_lookup (cse_reg_info_tree, - (splay_tree_key) regno); - if (n) - cri = (struct cse_reg_info *) (n->value); - else - { - /* Get a new cse_reg_info structure. */ - if (cse_reg_info_free_list) - { - cri = cse_reg_info_free_list; - cse_reg_info_free_list = cri->variant.next; - } - else - cri = (struct cse_reg_info *) xmalloc (sizeof (struct cse_reg_info)); - - /* Initialize it. */ - cri->variant.reg_tick = 0; - cri->reg_in_table = -1; - cri->reg_qty = regno; - - splay_tree_insert (cse_reg_info_tree, - (splay_tree_key) regno, - (splay_tree_value) cri); - } - - /* Cache this lookup; we tend to be looking up information about the - same register several times in a row. */ - cached_regno = regno; - cached_cse_reg_info = cri; - - return cri; -} - -static void -free_cse_reg_info (v) - splay_tree_value v; -{ - struct cse_reg_info *cri = (struct cse_reg_info *) v; - - cri->variant.next = cse_reg_info_free_list; - cse_reg_info_free_list = cri; -} - -/* Clear the hash table and initialize each register with its own quantity, - for a new basic block. */ - -static void -new_basic_block () -{ - register int i; - - next_qty = max_reg; - - if (cse_reg_info_tree) - { - splay_tree_delete (cse_reg_info_tree); - cached_cse_reg_info = 0; - } - - cse_reg_info_tree = splay_tree_new (splay_tree_compare_ints, 0, - free_cse_reg_info); - - CLEAR_HARD_REG_SET (hard_regs_in_table); - - /* The per-quantity values used to be initialized here, but it is - much faster to initialize each as it is made in `make_new_qty'. */ - - for (i = 0; i < NBUCKETS; i++) - { - register struct table_elt *this, *next; - for (this = table[i]; this; this = next) - { - next = this->next_same_hash; - free_element (this); - } - } - - bzero ((char *) table, sizeof table); - - prev_insn = 0; - -#ifdef HAVE_cc0 - prev_insn_cc0 = 0; -#endif -} - -/* Say that register REG contains a quantity not in any register before - and initialize that quantity. */ - -static void -make_new_qty (reg) - register int reg; -{ - register int q; - - if (next_qty >= max_qty) - abort (); - - q = REG_QTY (reg) = next_qty++; - qty_first_reg[q] = reg; - qty_last_reg[q] = reg; - qty_const[q] = qty_const_insn[q] = 0; - qty_comparison_code[q] = UNKNOWN; - - reg_next_eqv[reg] = reg_prev_eqv[reg] = -1; -} - -/* Make reg NEW equivalent to reg OLD. - OLD is not changing; NEW is. */ - -static void -make_regs_eqv (new, old) - register int new, old; -{ - register int lastr, firstr; - register int q = REG_QTY (old); - - /* Nothing should become eqv until it has a "non-invalid" qty number. */ - if (! REGNO_QTY_VALID_P (old)) - abort (); - - REG_QTY (new) = q; - firstr = qty_first_reg[q]; - lastr = qty_last_reg[q]; - - /* Prefer fixed hard registers to anything. Prefer pseudo regs to other - hard regs. Among pseudos, if NEW will live longer than any other reg - of the same qty, and that is beyond the current basic block, - make it the new canonical replacement for this qty. */ - if (! (firstr < FIRST_PSEUDO_REGISTER && FIXED_REGNO_P (firstr)) - /* Certain fixed registers might be of the class NO_REGS. This means - that not only can they not be allocated by the compiler, but - they cannot be used in substitutions or canonicalizations - either. */ - && (new >= FIRST_PSEUDO_REGISTER || REGNO_REG_CLASS (new) != NO_REGS) - && ((new < FIRST_PSEUDO_REGISTER && FIXED_REGNO_P (new)) - || (new >= FIRST_PSEUDO_REGISTER - && (firstr < FIRST_PSEUDO_REGISTER - || ((uid_cuid[REGNO_LAST_UID (new)] > cse_basic_block_end - || (uid_cuid[REGNO_FIRST_UID (new)] - < cse_basic_block_start)) - && (uid_cuid[REGNO_LAST_UID (new)] - > uid_cuid[REGNO_LAST_UID (firstr)])))))) - { - reg_prev_eqv[firstr] = new; - reg_next_eqv[new] = firstr; - reg_prev_eqv[new] = -1; - qty_first_reg[q] = new; - } - else - { - /* If NEW is a hard reg (known to be non-fixed), insert at end. - Otherwise, insert before any non-fixed hard regs that are at the - end. Registers of class NO_REGS cannot be used as an - equivalent for anything. */ - while (lastr < FIRST_PSEUDO_REGISTER && reg_prev_eqv[lastr] >= 0 - && (REGNO_REG_CLASS (lastr) == NO_REGS || ! FIXED_REGNO_P (lastr)) - && new >= FIRST_PSEUDO_REGISTER) - lastr = reg_prev_eqv[lastr]; - reg_next_eqv[new] = reg_next_eqv[lastr]; - if (reg_next_eqv[lastr] >= 0) - reg_prev_eqv[reg_next_eqv[lastr]] = new; - else - qty_last_reg[q] = new; - reg_next_eqv[lastr] = new; - reg_prev_eqv[new] = lastr; - } -} - -/* Remove REG from its equivalence class. */ - -static void -delete_reg_equiv (reg) - register int reg; -{ - register int q = REG_QTY (reg); - register int p, n; - - /* If invalid, do nothing. */ - if (q == reg) - return; - - p = reg_prev_eqv[reg]; - n = reg_next_eqv[reg]; - - if (n != -1) - reg_prev_eqv[n] = p; - else - qty_last_reg[q] = p; - if (p != -1) - reg_next_eqv[p] = n; - else - qty_first_reg[q] = n; - - REG_QTY (reg) = reg; -} - -/* Remove any invalid expressions from the hash table - that refer to any of the registers contained in expression X. - - Make sure that newly inserted references to those registers - as subexpressions will be considered valid. - - mention_regs is not called when a register itself - is being stored in the table. - - Return 1 if we have done something that may have changed the hash code - of X. */ - -static int -mention_regs (x) - rtx x; -{ - register enum rtx_code code; - register int i, j; - register char *fmt; - register int changed = 0; - - if (x == 0) - return 0; - - code = GET_CODE (x); - if (code == REG) - { - register int regno = REGNO (x); - register int endregno - = regno + (regno >= FIRST_PSEUDO_REGISTER ? 1 - : HARD_REGNO_NREGS (regno, GET_MODE (x))); - int i; - - for (i = regno; i < endregno; i++) - { - if (REG_IN_TABLE (i) >= 0 && REG_IN_TABLE (i) != REG_TICK (i)) - remove_invalid_refs (i); - - REG_IN_TABLE (i) = REG_TICK (i); - } - - return 0; - } - - /* If this is a SUBREG, we don't want to discard other SUBREGs of the same - pseudo if they don't use overlapping words. We handle only pseudos - here for simplicity. */ - if (code == SUBREG && GET_CODE (SUBREG_REG (x)) == REG - && REGNO (SUBREG_REG (x)) >= FIRST_PSEUDO_REGISTER) - { - int i = REGNO (SUBREG_REG (x)); - - if (REG_IN_TABLE (i) >= 0 && REG_IN_TABLE (i) != REG_TICK (i)) - { - /* If reg_tick has been incremented more than once since - reg_in_table was last set, that means that the entire - register has been set before, so discard anything memorized - for the entrire register, including all SUBREG expressions. */ - if (REG_IN_TABLE (i) != REG_TICK (i) - 1) - remove_invalid_refs (i); - else - remove_invalid_subreg_refs (i, SUBREG_WORD (x), GET_MODE (x)); - } - - REG_IN_TABLE (i) = REG_TICK (i); - return 0; - } - - /* If X is a comparison or a COMPARE and either operand is a register - that does not have a quantity, give it one. This is so that a later - call to record_jump_equiv won't cause X to be assigned a different - hash code and not found in the table after that call. - - It is not necessary to do this here, since rehash_using_reg can - fix up the table later, but doing this here eliminates the need to - call that expensive function in the most common case where the only - use of the register is in the comparison. */ - - if (code == COMPARE || GET_RTX_CLASS (code) == '<') - { - if (GET_CODE (XEXP (x, 0)) == REG - && ! REGNO_QTY_VALID_P (REGNO (XEXP (x, 0)))) - if (insert_regs (XEXP (x, 0), NULL_PTR, 0)) - { - rehash_using_reg (XEXP (x, 0)); - changed = 1; - } - - if (GET_CODE (XEXP (x, 1)) == REG - && ! REGNO_QTY_VALID_P (REGNO (XEXP (x, 1)))) - if (insert_regs (XEXP (x, 1), NULL_PTR, 0)) - { - rehash_using_reg (XEXP (x, 1)); - changed = 1; - } - } - - fmt = GET_RTX_FORMAT (code); - for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) - if (fmt[i] == 'e') - changed |= mention_regs (XEXP (x, i)); - else if (fmt[i] == 'E') - for (j = 0; j < XVECLEN (x, i); j++) - changed |= mention_regs (XVECEXP (x, i, j)); - - return changed; -} - -/* Update the register quantities for inserting X into the hash table - with a value equivalent to CLASSP. - (If the class does not contain a REG, it is irrelevant.) - If MODIFIED is nonzero, X is a destination; it is being modified. - Note that delete_reg_equiv should be called on a register - before insert_regs is done on that register with MODIFIED != 0. - - Nonzero value means that elements of reg_qty have changed - so X's hash code may be different. */ - -static int -insert_regs (x, classp, modified) - rtx x; - struct table_elt *classp; - int modified; -{ - if (GET_CODE (x) == REG) - { - register int regno = REGNO (x); - - /* If REGNO is in the equivalence table already but is of the - wrong mode for that equivalence, don't do anything here. */ - - if (REGNO_QTY_VALID_P (regno) - && qty_mode[REG_QTY (regno)] != GET_MODE (x)) - return 0; - - if (modified || ! REGNO_QTY_VALID_P (regno)) - { - if (classp) - for (classp = classp->first_same_value; - classp != 0; - classp = classp->next_same_value) - if (GET_CODE (classp->exp) == REG - && GET_MODE (classp->exp) == GET_MODE (x)) - { - make_regs_eqv (regno, REGNO (classp->exp)); - return 1; - } - - make_new_qty (regno); - qty_mode[REG_QTY (regno)] = GET_MODE (x); - return 1; - } - - return 0; - } - - /* If X is a SUBREG, we will likely be inserting the inner register in the - table. If that register doesn't have an assigned quantity number at - this point but does later, the insertion that we will be doing now will - not be accessible because its hash code will have changed. So assign - a quantity number now. */ - - else if (GET_CODE (x) == SUBREG && GET_CODE (SUBREG_REG (x)) == REG - && ! REGNO_QTY_VALID_P (REGNO (SUBREG_REG (x)))) - { - int regno = REGNO (SUBREG_REG (x)); - - insert_regs (SUBREG_REG (x), NULL_PTR, 0); - /* Mention_regs checks if REG_TICK is exactly one larger than - REG_IN_TABLE to find out if there was only a single preceding - invalidation - for the SUBREG - or another one, which would be - for the full register. Since we don't invalidate the SUBREG - here first, we might have to bump up REG_TICK so that mention_regs - will do the right thing. */ - if (REG_IN_TABLE (regno) >= 0 - && REG_TICK (regno) == REG_IN_TABLE (regno) + 1) - REG_TICK (regno)++; - mention_regs (x); - return 1; - } - else - return mention_regs (x); -} - -/* Look in or update the hash table. */ - -/* Put the element ELT on the list of free elements. */ - -static void -free_element (elt) - struct table_elt *elt; -{ - elt->next_same_hash = free_element_chain; - free_element_chain = elt; -} - -/* Return an element that is free for use. */ - -static struct table_elt * -get_element () -{ - struct table_elt *elt = free_element_chain; - if (elt) - { - free_element_chain = elt->next_same_hash; - return elt; - } - n_elements_made++; - return (struct table_elt *) oballoc (sizeof (struct table_elt)); -} - -/* Remove table element ELT from use in the table. - HASH is its hash code, made using the HASH macro. - It's an argument because often that is known in advance - and we save much time not recomputing it. */ - -static void -remove_from_table (elt, hash) - register struct table_elt *elt; - unsigned hash; -{ - if (elt == 0) - return; - - /* Mark this element as removed. See cse_insn. */ - elt->first_same_value = 0; - - /* Remove the table element from its equivalence class. */ - - { - register struct table_elt *prev = elt->prev_same_value; - register struct table_elt *next = elt->next_same_value; - - if (next) next->prev_same_value = prev; - - if (prev) - prev->next_same_value = next; - else - { - register struct table_elt *newfirst = next; - while (next) - { - next->first_same_value = newfirst; - next = next->next_same_value; - } - } - } - - /* Remove the table element from its hash bucket. */ - - { - register struct table_elt *prev = elt->prev_same_hash; - register struct table_elt *next = elt->next_same_hash; - - if (next) next->prev_same_hash = prev; - - if (prev) - prev->next_same_hash = next; - else if (table[hash] == elt) - table[hash] = next; - else - { - /* This entry is not in the proper hash bucket. This can happen - when two classes were merged by `merge_equiv_classes'. Search - for the hash bucket that it heads. This happens only very - rarely, so the cost is acceptable. */ - for (hash = 0; hash < NBUCKETS; hash++) - if (table[hash] == elt) - table[hash] = next; - } - } - - /* Remove the table element from its related-value circular chain. */ - - if (elt->related_value != 0 && elt->related_value != elt) - { - register struct table_elt *p = elt->related_value; - while (p->related_value != elt) - p = p->related_value; - p->related_value = elt->related_value; - if (p->related_value == p) - p->related_value = 0; - } - - free_element (elt); -} - -/* Look up X in the hash table and return its table element, - or 0 if X is not in the table. - - MODE is the machine-mode of X, or if X is an integer constant - with VOIDmode then MODE is the mode with which X will be used. - - Here we are satisfied to find an expression whose tree structure - looks like X. */ - -static struct table_elt * -lookup (x, hash, mode) - rtx x; - unsigned hash; - enum machine_mode mode; -{ - register struct table_elt *p; - - for (p = table[hash]; p; p = p->next_same_hash) - if (mode == p->mode && ((x == p->exp && GET_CODE (x) == REG) - || exp_equiv_p (x, p->exp, GET_CODE (x) != REG, 0))) - return p; - - return 0; -} - -/* Like `lookup' but don't care whether the table element uses invalid regs. - Also ignore discrepancies in the machine mode of a register. */ - -static struct table_elt * -lookup_for_remove (x, hash, mode) - rtx x; - unsigned hash; - enum machine_mode mode; -{ - register struct table_elt *p; - - if (GET_CODE (x) == REG) - { - int regno = REGNO (x); - /* Don't check the machine mode when comparing registers; - invalidating (REG:SI 0) also invalidates (REG:DF 0). */ - for (p = table[hash]; p; p = p->next_same_hash) - if (GET_CODE (p->exp) == REG - && REGNO (p->exp) == regno) - return p; - } - else - { - for (p = table[hash]; p; p = p->next_same_hash) - if (mode == p->mode && (x == p->exp || exp_equiv_p (x, p->exp, 0, 0))) - return p; - } - - return 0; -} - -/* Look for an expression equivalent to X and with code CODE. - If one is found, return that expression. */ - -static rtx -lookup_as_function (x, code) - rtx x; - enum rtx_code code; -{ - register struct table_elt *p = lookup (x, safe_hash (x, VOIDmode) % NBUCKETS, - GET_MODE (x)); - /* If we are looking for a CONST_INT, the mode doesn't really matter, as - long as we are narrowing. So if we looked in vain for a mode narrower - than word_mode before, look for word_mode now. */ - if (p == 0 && code == CONST_INT - && GET_MODE_SIZE (GET_MODE (x)) < GET_MODE_SIZE (word_mode)) - { - x = copy_rtx (x); - PUT_MODE (x, word_mode); - p = lookup (x, safe_hash (x, VOIDmode) % NBUCKETS, word_mode); - } - - if (p == 0) - return 0; - - for (p = p->first_same_value; p; p = p->next_same_value) - { - if (GET_CODE (p->exp) == code - /* Make sure this is a valid entry in the table. */ - && exp_equiv_p (p->exp, p->exp, 1, 0)) - return p->exp; - } - - return 0; -} - -/* Insert X in the hash table, assuming HASH is its hash code - and CLASSP is an element of the class it should go in - (or 0 if a new class should be made). - It is inserted at the proper position to keep the class in - the order cheapest first. - - MODE is the machine-mode of X, or if X is an integer constant - with VOIDmode then MODE is the mode with which X will be used. - - For elements of equal cheapness, the most recent one - goes in front, except that the first element in the list - remains first unless a cheaper element is added. The order of - pseudo-registers does not matter, as canon_reg will be called to - find the cheapest when a register is retrieved from the table. - - The in_memory field in the hash table element is set to 0. - The caller must set it nonzero if appropriate. - - You should call insert_regs (X, CLASSP, MODIFY) before calling here, - and if insert_regs returns a nonzero value - you must then recompute its hash code before calling here. - - If necessary, update table showing constant values of quantities. */ - -#define CHEAPER(X,Y) ((X)->cost < (Y)->cost) - -static struct table_elt * -insert (x, classp, hash, mode) - register rtx x; - register struct table_elt *classp; - unsigned hash; - enum machine_mode mode; -{ - register struct table_elt *elt; - - /* If X is a register and we haven't made a quantity for it, - something is wrong. */ - if (GET_CODE (x) == REG && ! REGNO_QTY_VALID_P (REGNO (x))) - abort (); - - /* If X is a hard register, show it is being put in the table. */ - if (GET_CODE (x) == REG && REGNO (x) < FIRST_PSEUDO_REGISTER) - { - int regno = REGNO (x); - int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (x)); - int i; - - for (i = regno; i < endregno; i++) - SET_HARD_REG_BIT (hard_regs_in_table, i); - } - - /* If X is a label, show we recorded it. */ - if (GET_CODE (x) == LABEL_REF - || (GET_CODE (x) == CONST && GET_CODE (XEXP (x, 0)) == PLUS - && GET_CODE (XEXP (XEXP (x, 0), 0)) == LABEL_REF)) - recorded_label_ref = 1; - - /* Put an element for X into the right hash bucket. */ - - elt = get_element (); - elt->exp = x; - elt->cost = COST (x); - elt->next_same_value = 0; - elt->prev_same_value = 0; - elt->next_same_hash = table[hash]; - elt->prev_same_hash = 0; - elt->related_value = 0; - elt->in_memory = 0; - elt->mode = mode; - elt->is_const = (CONSTANT_P (x) - /* GNU C++ takes advantage of this for `this' - (and other const values). */ - || (RTX_UNCHANGING_P (x) - && GET_CODE (x) == REG - && REGNO (x) >= FIRST_PSEUDO_REGISTER) - || FIXED_BASE_PLUS_P (x)); - - if (table[hash]) - table[hash]->prev_same_hash = elt; - table[hash] = elt; - - /* Put it into the proper value-class. */ - if (classp) - { - classp = classp->first_same_value; - if (CHEAPER (elt, classp)) - /* Insert at the head of the class */ - { - register struct table_elt *p; - elt->next_same_value = classp; - classp->prev_same_value = elt; - elt->first_same_value = elt; - - for (p = classp; p; p = p->next_same_value) - p->first_same_value = elt; - } - else - { - /* Insert not at head of the class. */ - /* Put it after the last element cheaper than X. */ - register struct table_elt *p, *next; - for (p = classp; (next = p->next_same_value) && CHEAPER (next, elt); - p = next); - /* Put it after P and before NEXT. */ - elt->next_same_value = next; - if (next) - next->prev_same_value = elt; - elt->prev_same_value = p; - p->next_same_value = elt; - elt->first_same_value = classp; - } - } - else - elt->first_same_value = elt; - - /* If this is a constant being set equivalent to a register or a register - being set equivalent to a constant, note the constant equivalence. - - If this is a constant, it cannot be equivalent to a different constant, - and a constant is the only thing that can be cheaper than a register. So - we know the register is the head of the class (before the constant was - inserted). - - If this is a register that is not already known equivalent to a - constant, we must check the entire class. - - If this is a register that is already known equivalent to an insn, - update `qty_const_insn' to show that `this_insn' is the latest - insn making that quantity equivalent to the constant. */ - - if (elt->is_const && classp && GET_CODE (classp->exp) == REG - && GET_CODE (x) != REG) - { - qty_const[REG_QTY (REGNO (classp->exp))] - = gen_lowpart_if_possible (qty_mode[REG_QTY (REGNO (classp->exp))], x); - qty_const_insn[REG_QTY (REGNO (classp->exp))] = this_insn; - } - - else if (GET_CODE (x) == REG && classp && ! qty_const[REG_QTY (REGNO (x))] - && ! elt->is_const) - { - register struct table_elt *p; - - for (p = classp; p != 0; p = p->next_same_value) - { - if (p->is_const && GET_CODE (p->exp) != REG) - { - qty_const[REG_QTY (REGNO (x))] - = gen_lowpart_if_possible (GET_MODE (x), p->exp); - qty_const_insn[REG_QTY (REGNO (x))] = this_insn; - break; - } - } - } - - else if (GET_CODE (x) == REG && qty_const[REG_QTY (REGNO (x))] - && GET_MODE (x) == qty_mode[REG_QTY (REGNO (x))]) - qty_const_insn[REG_QTY (REGNO (x))] = this_insn; - - /* If this is a constant with symbolic value, - and it has a term with an explicit integer value, - link it up with related expressions. */ - if (GET_CODE (x) == CONST) - { - rtx subexp = get_related_value (x); - unsigned subhash; - struct table_elt *subelt, *subelt_prev; - - if (subexp != 0) - { - /* Get the integer-free subexpression in the hash table. */ - subhash = safe_hash (subexp, mode) % NBUCKETS; - subelt = lookup (subexp, subhash, mode); - if (subelt == 0) - subelt = insert (subexp, NULL_PTR, subhash, mode); - /* Initialize SUBELT's circular chain if it has none. */ - if (subelt->related_value == 0) - subelt->related_value = subelt; - /* Find the element in the circular chain that precedes SUBELT. */ - subelt_prev = subelt; - while (subelt_prev->related_value != subelt) - subelt_prev = subelt_prev->related_value; - /* Put new ELT into SUBELT's circular chain just before SUBELT. - This way the element that follows SUBELT is the oldest one. */ - elt->related_value = subelt_prev->related_value; - subelt_prev->related_value = elt; - } - } - - return elt; -} - -/* Given two equivalence classes, CLASS1 and CLASS2, put all the entries from - CLASS2 into CLASS1. This is done when we have reached an insn which makes - the two classes equivalent. - - CLASS1 will be the surviving class; CLASS2 should not be used after this - call. - - Any invalid entries in CLASS2 will not be copied. */ - -static void -merge_equiv_classes (class1, class2) - struct table_elt *class1, *class2; -{ - struct table_elt *elt, *next, *new; - - /* Ensure we start with the head of the classes. */ - class1 = class1->first_same_value; - class2 = class2->first_same_value; - - /* If they were already equal, forget it. */ - if (class1 == class2) - return; - - for (elt = class2; elt; elt = next) - { - unsigned hash; - rtx exp = elt->exp; - enum machine_mode mode = elt->mode; - - next = elt->next_same_value; - - /* Remove old entry, make a new one in CLASS1's class. - Don't do this for invalid entries as we cannot find their - hash code (it also isn't necessary). */ - if (GET_CODE (exp) == REG || exp_equiv_p (exp, exp, 1, 0)) - { - hash_arg_in_memory = 0; - hash_arg_in_struct = 0; - hash = HASH (exp, mode); - - if (GET_CODE (exp) == REG) - delete_reg_equiv (REGNO (exp)); - - remove_from_table (elt, hash); - - if (insert_regs (exp, class1, 0)) - { - rehash_using_reg (exp); - hash = HASH (exp, mode); - } - new = insert (exp, class1, hash, mode); - new->in_memory = hash_arg_in_memory; - new->in_struct = hash_arg_in_struct; - } - } -} - - -/* Flush the entire hash table. */ - -static void -flush_hash_table () -{ - int i; - struct table_elt *p; - - for (i = 0; i < NBUCKETS; i++) - for (p = table[i]; p; p = table[i]) - { - /* Note that invalidate can remove elements - after P in the current hash chain. */ - if (GET_CODE (p->exp) == REG) - invalidate (p->exp, p->mode); - else - remove_from_table (p, i); - } -} - - -/* Remove from the hash table, or mark as invalid, - all expressions whose values could be altered by storing in X. - X is a register, a subreg, or a memory reference with nonvarying address - (because, when a memory reference with a varying address is stored in, - all memory references are removed by invalidate_memory - so specific invalidation is superfluous). - FULL_MODE, if not VOIDmode, indicates that this much should be invalidated - instead of just the amount indicated by the mode of X. This is only used - for bitfield stores into memory. - - A nonvarying address may be just a register or just - a symbol reference, or it may be either of those plus - a numeric offset. */ - -static void -invalidate (x, full_mode) - rtx x; - enum machine_mode full_mode; -{ - register int i; - register struct table_elt *p; - - /* If X is a register, dependencies on its contents - are recorded through the qty number mechanism. - Just change the qty number of the register, - mark it as invalid for expressions that refer to it, - and remove it itself. */ - - if (GET_CODE (x) == REG) - { - register int regno = REGNO (x); - register unsigned hash = HASH (x, GET_MODE (x)); - - /* Remove REGNO from any quantity list it might be on and indicate - that its value might have changed. If it is a pseudo, remove its - entry from the hash table. - - For a hard register, we do the first two actions above for any - additional hard registers corresponding to X. Then, if any of these - registers are in the table, we must remove any REG entries that - overlap these registers. */ - - delete_reg_equiv (regno); - REG_TICK (regno)++; - - if (regno >= FIRST_PSEUDO_REGISTER) - { - /* Because a register can be referenced in more than one mode, - we might have to remove more than one table entry. */ - - struct table_elt *elt; - - while ((elt = lookup_for_remove (x, hash, GET_MODE (x)))) - remove_from_table (elt, hash); - } - else - { - HOST_WIDE_INT in_table - = TEST_HARD_REG_BIT (hard_regs_in_table, regno); - int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (x)); - int tregno, tendregno; - register struct table_elt *p, *next; - - CLEAR_HARD_REG_BIT (hard_regs_in_table, regno); - - for (i = regno + 1; i < endregno; i++) - { - in_table |= TEST_HARD_REG_BIT (hard_regs_in_table, i); - CLEAR_HARD_REG_BIT (hard_regs_in_table, i); - delete_reg_equiv (i); - REG_TICK (i)++; - } - - if (in_table) - for (hash = 0; hash < NBUCKETS; hash++) - for (p = table[hash]; p; p = next) - { - next = p->next_same_hash; - - if (GET_CODE (p->exp) != REG - || REGNO (p->exp) >= FIRST_PSEUDO_REGISTER) - continue; - - tregno = REGNO (p->exp); - tendregno - = tregno + HARD_REGNO_NREGS (tregno, GET_MODE (p->exp)); - if (tendregno > regno && tregno < endregno) - remove_from_table (p, hash); - } - } - - return; - } - - if (GET_CODE (x) == SUBREG) - { - if (GET_CODE (SUBREG_REG (x)) != REG) - abort (); - invalidate (SUBREG_REG (x), VOIDmode); - return; - } - - /* If X is a parallel, invalidate all of its elements. */ - - if (GET_CODE (x) == PARALLEL) - { - for (i = XVECLEN (x, 0) - 1; i >= 0 ; --i) - invalidate (XVECEXP (x, 0, i), VOIDmode); - return; - } - - /* If X is an expr_list, this is part of a disjoint return value; - extract the location in question ignoring the offset. */ - - if (GET_CODE (x) == EXPR_LIST) - { - invalidate (XEXP (x, 0), VOIDmode); - return; - } - - /* X is not a register; it must be a memory reference with - a nonvarying address. Remove all hash table elements - that refer to overlapping pieces of memory. */ - - if (GET_CODE (x) != MEM) - abort (); - - if (full_mode == VOIDmode) - full_mode = GET_MODE (x); - - for (i = 0; i < NBUCKETS; i++) - { - register struct table_elt *next; - for (p = table[i]; p; p = next) - { - next = p->next_same_hash; - /* Invalidate ASM_OPERANDS which reference memory (this is easier - than checking all the aliases). */ - if (p->in_memory - && (GET_CODE (p->exp) != MEM - || true_dependence (x, full_mode, p->exp, cse_rtx_varies_p))) - remove_from_table (p, i); - } - } -} - -/* Remove all expressions that refer to register REGNO, - since they are already invalid, and we are about to - mark that register valid again and don't want the old - expressions to reappear as valid. */ - -static void -remove_invalid_refs (regno) - int regno; -{ - register int i; - register struct table_elt *p, *next; - - for (i = 0; i < NBUCKETS; i++) - for (p = table[i]; p; p = next) - { - next = p->next_same_hash; - if (GET_CODE (p->exp) != REG - && refers_to_regno_p (regno, regno + 1, p->exp, NULL_PTR)) - remove_from_table (p, i); - } -} - -/* Likewise for a subreg with subreg_reg WORD and mode MODE. */ -static void -remove_invalid_subreg_refs (regno, word, mode) - int regno; - int word; - enum machine_mode mode; -{ - register int i; - register struct table_elt *p, *next; - int end = word + (GET_MODE_SIZE (mode) - 1) / UNITS_PER_WORD; - - for (i = 0; i < NBUCKETS; i++) - for (p = table[i]; p; p = next) - { - rtx exp; - next = p->next_same_hash; - - exp = p->exp; - if (GET_CODE (p->exp) != REG - && (GET_CODE (exp) != SUBREG - || GET_CODE (SUBREG_REG (exp)) != REG - || REGNO (SUBREG_REG (exp)) != regno - || (((SUBREG_WORD (exp) - + (GET_MODE_SIZE (GET_MODE (exp)) - 1) / UNITS_PER_WORD) - >= word) - && SUBREG_WORD (exp) <= end)) - && refers_to_regno_p (regno, regno + 1, p->exp, NULL_PTR)) - remove_from_table (p, i); - } -} - -/* Recompute the hash codes of any valid entries in the hash table that - reference X, if X is a register, or SUBREG_REG (X) if X is a SUBREG. - - This is called when we make a jump equivalence. */ - -static void -rehash_using_reg (x) - rtx x; -{ - unsigned int i; - struct table_elt *p, *next; - unsigned hash; - - if (GET_CODE (x) == SUBREG) - x = SUBREG_REG (x); - - /* If X is not a register or if the register is known not to be in any - valid entries in the table, we have no work to do. */ - - if (GET_CODE (x) != REG - || REG_IN_TABLE (REGNO (x)) < 0 - || REG_IN_TABLE (REGNO (x)) != REG_TICK (REGNO (x))) - return; - - /* Scan all hash chains looking for valid entries that mention X. - If we find one and it is in the wrong hash chain, move it. We can skip - objects that are registers, since they are handled specially. */ - - for (i = 0; i < NBUCKETS; i++) - for (p = table[i]; p; p = next) - { - next = p->next_same_hash; - if (GET_CODE (p->exp) != REG && reg_mentioned_p (x, p->exp) - && exp_equiv_p (p->exp, p->exp, 1, 0) - && i != (hash = safe_hash (p->exp, p->mode) % NBUCKETS)) - { - if (p->next_same_hash) - p->next_same_hash->prev_same_hash = p->prev_same_hash; - - if (p->prev_same_hash) - p->prev_same_hash->next_same_hash = p->next_same_hash; - else - table[i] = p->next_same_hash; - - p->next_same_hash = table[hash]; - p->prev_same_hash = 0; - if (table[hash]) - table[hash]->prev_same_hash = p; - table[hash] = p; - } - } -} - -/* Remove from the hash table any expression that is a call-clobbered - register. Also update their TICK values. */ - -static void -invalidate_for_call () -{ - int regno, endregno; - int i; - unsigned hash; - struct table_elt *p, *next; - int in_table = 0; - - /* Go through all the hard registers. For each that is clobbered in - a CALL_INSN, remove the register from quantity chains and update - reg_tick if defined. Also see if any of these registers is currently - in the table. */ - - for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++) - if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno)) - { - delete_reg_equiv (regno); - if (REG_TICK (regno) >= 0) - REG_TICK (regno)++; - - in_table |= (TEST_HARD_REG_BIT (hard_regs_in_table, regno) != 0); - } - - /* In the case where we have no call-clobbered hard registers in the - table, we are done. Otherwise, scan the table and remove any - entry that overlaps a call-clobbered register. */ - - if (in_table) - for (hash = 0; hash < NBUCKETS; hash++) - for (p = table[hash]; p; p = next) - { - next = p->next_same_hash; - - if (p->in_memory) - { - remove_from_table (p, hash); - continue; - } - - if (GET_CODE (p->exp) != REG - || REGNO (p->exp) >= FIRST_PSEUDO_REGISTER) - continue; - - regno = REGNO (p->exp); - endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (p->exp)); - - for (i = regno; i < endregno; i++) - if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i)) - { - remove_from_table (p, hash); - break; - } - } -} - -/* Given an expression X of type CONST, - and ELT which is its table entry (or 0 if it - is not in the hash table), - return an alternate expression for X as a register plus integer. - If none can be found, return 0. */ - -static rtx -use_related_value (x, elt) - rtx x; - struct table_elt *elt; -{ - register struct table_elt *relt = 0; - register struct table_elt *p, *q; - HOST_WIDE_INT offset; - - /* First, is there anything related known? - If we have a table element, we can tell from that. - Otherwise, must look it up. */ - - if (elt != 0 && elt->related_value != 0) - relt = elt; - else if (elt == 0 && GET_CODE (x) == CONST) - { - rtx subexp = get_related_value (x); - if (subexp != 0) - relt = lookup (subexp, - safe_hash (subexp, GET_MODE (subexp)) % NBUCKETS, - GET_MODE (subexp)); - } - - if (relt == 0) - return 0; - - /* Search all related table entries for one that has an - equivalent register. */ - - p = relt; - while (1) - { - /* This loop is strange in that it is executed in two different cases. - The first is when X is already in the table. Then it is searching - the RELATED_VALUE list of X's class (RELT). The second case is when - X is not in the table. Then RELT points to a class for the related - value. - - Ensure that, whatever case we are in, that we ignore classes that have - the same value as X. */ - - if (rtx_equal_p (x, p->exp)) - q = 0; - else - for (q = p->first_same_value; q; q = q->next_same_value) - if (GET_CODE (q->exp) == REG) - break; - - if (q) - break; - - p = p->related_value; - - /* We went all the way around, so there is nothing to be found. - Alternatively, perhaps RELT was in the table for some other reason - and it has no related values recorded. */ - if (p == relt || p == 0) - break; - } - - if (q == 0) - return 0; - - offset = (get_integer_term (x) - get_integer_term (p->exp)); - /* Note: OFFSET may be 0 if P->xexp and X are related by commutativity. */ - return plus_constant (q->exp, offset); -} - -/* Hash an rtx. We are careful to make sure the value is never negative. - Equivalent registers hash identically. - MODE is used in hashing for CONST_INTs only; - otherwise the mode of X is used. - - Store 1 in do_not_record if any subexpression is volatile. - - Store 1 in hash_arg_in_memory if X contains a MEM rtx - which does not have the RTX_UNCHANGING_P bit set. - In this case, also store 1 in hash_arg_in_struct - if there is a MEM rtx which has the MEM_IN_STRUCT_P bit set. - - Note that cse_insn knows that the hash code of a MEM expression - is just (int) MEM plus the hash code of the address. */ - -static unsigned -canon_hash (x, mode) - rtx x; - enum machine_mode mode; -{ - register int i, j; - register unsigned hash = 0; - register enum rtx_code code; - register 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); - - /* On some machines, we can't record any non-fixed hard register, - because extending its life will cause reload problems. We - consider ap, fp, and sp to be fixed for this purpose. - - We also consider CCmode registers to be fixed for this purpose; - failure to do so leads to failure to simplify 0<100 type of - conditionals. - - On all machines, we can't record any global registers. */ - - if (regno < FIRST_PSEUDO_REGISTER - && (global_regs[regno] - || (SMALL_REGISTER_CLASSES - && ! fixed_regs[regno] - && regno != FRAME_POINTER_REGNUM - && regno != HARD_FRAME_POINTER_REGNUM - && regno != ARG_POINTER_REGNUM - && regno != STACK_POINTER_REGNUM - && GET_MODE_CLASS (GET_MODE (x)) != MODE_CC))) - { - do_not_record = 1; - return 0; - } - hash += ((unsigned) REG << 7) + (unsigned) REG_QTY (regno); - return hash; - } - - /* We handle SUBREG of a REG specially because the underlying - reg changes its hash value with every value change; we don't - want to have to forget unrelated subregs when one subreg changes. */ - case SUBREG: - { - if (GET_CODE (SUBREG_REG (x)) == REG) - { - hash += (((unsigned) SUBREG << 7) - + REGNO (SUBREG_REG (x)) + SUBREG_WORD (x)); - return hash; - } - break; - } - - 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: - hash - += ((unsigned) LABEL_REF << 7) + (unsigned long) XEXP (x, 0); - return hash; - - case SYMBOL_REF: - hash - += ((unsigned) SYMBOL_REF << 7) + (unsigned long) XSTR (x, 0); - return hash; - - case MEM: - if (MEM_VOLATILE_P (x)) - { - do_not_record = 1; - return 0; - } - if (! RTX_UNCHANGING_P (x) || FIXED_BASE_PLUS_P (XEXP (x, 0))) - { - hash_arg_in_memory = 1; - if (MEM_IN_STRUCT_P (x)) hash_arg_in_struct = 1; - } - /* Now that we have already found this special case, - might as well speed it up as much as possible. */ - hash += (unsigned) MEM; - 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 = 1; - return 0; - - case ASM_OPERANDS: - if (MEM_VOLATILE_P (x)) - { - do_not_record = 1; - return 0; - } - break; - - 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 += canon_hash (tem, 0); - } - else if (fmt[i] == 'E') - for (j = 0; j < XVECLEN (x, i); j++) - hash += canon_hash (XVECEXP (x, i, j), 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 if (fmt[i] == '0') - /* unused */; - else - abort (); - } - return hash; -} - -/* Like canon_hash but with no side effects. */ - -static unsigned -safe_hash (x, mode) - rtx x; - enum machine_mode mode; -{ - int save_do_not_record = do_not_record; - int save_hash_arg_in_memory = hash_arg_in_memory; - int save_hash_arg_in_struct = hash_arg_in_struct; - unsigned hash = canon_hash (x, mode); - hash_arg_in_memory = save_hash_arg_in_memory; - hash_arg_in_struct = save_hash_arg_in_struct; - do_not_record = save_do_not_record; - return hash; -} - -/* Return 1 iff X and Y would canonicalize into the same thing, - without actually constructing the canonicalization of either one. - If VALIDATE is nonzero, - we assume X is an expression being processed from the rtl - and Y was found in the hash table. We check register refs - in Y for being marked as valid. - - If EQUAL_VALUES is nonzero, we allow a register to match a constant value - that is known to be in the register. Ordinarily, we don't allow them - to match, because letting them match would cause unpredictable results - in all the places that search a hash table chain for an equivalent - for a given value. A possible equivalent that has different structure - has its hash code computed from different data. Whether the hash code - is the same as that of the given value is pure luck. */ - -static int -exp_equiv_p (x, y, validate, equal_values) - rtx x, y; - int validate; - int equal_values; -{ - register int i, j; - register enum rtx_code code; - register char *fmt; - - /* Note: it is incorrect to assume an expression is equivalent to itself - if VALIDATE is nonzero. */ - if (x == y && !validate) - return 1; - if (x == 0 || y == 0) - return x == y; - - code = GET_CODE (x); - if (code != GET_CODE (y)) - { - if (!equal_values) - return 0; - - /* If X is a constant and Y is a register or vice versa, they may be - equivalent. We only have to validate if Y is a register. */ - if (CONSTANT_P (x) && GET_CODE (y) == REG - && REGNO_QTY_VALID_P (REGNO (y)) - && GET_MODE (y) == qty_mode[REG_QTY (REGNO (y))] - && rtx_equal_p (x, qty_const[REG_QTY (REGNO (y))]) - && (! validate || REG_IN_TABLE (REGNO (y)) == REG_TICK (REGNO (y)))) - return 1; - - if (CONSTANT_P (y) && code == REG - && REGNO_QTY_VALID_P (REGNO (x)) - && GET_MODE (x) == qty_mode[REG_QTY (REGNO (x))] - && rtx_equal_p (y, qty_const[REG_QTY (REGNO (x))])) - return 1; - - 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: - { - int regno = REGNO (y); - int endregno - = regno + (regno >= FIRST_PSEUDO_REGISTER ? 1 - : HARD_REGNO_NREGS (regno, GET_MODE (y))); - int i; - - /* If the quantities are not the same, the expressions are not - equivalent. If there are and we are not to validate, they - are equivalent. Otherwise, ensure all regs are up-to-date. */ - - if (REG_QTY (REGNO (x)) != REG_QTY (regno)) - return 0; - - if (! validate) - return 1; - - for (i = regno; i < endregno; i++) - if (REG_IN_TABLE (i) != REG_TICK (i)) - return 0; - - return 1; - } - - /* For commutative operations, check both orders. */ - case PLUS: - case MULT: - case AND: - case IOR: - case XOR: - case NE: - case EQ: - return ((exp_equiv_p (XEXP (x, 0), XEXP (y, 0), validate, equal_values) - && exp_equiv_p (XEXP (x, 1), XEXP (y, 1), - validate, equal_values)) - || (exp_equiv_p (XEXP (x, 0), XEXP (y, 1), - validate, equal_values) - && exp_equiv_p (XEXP (x, 1), XEXP (y, 0), - validate, equal_values))); - - default: - break; - } - - /* Compare the elements. If any pair of corresponding elements - fail to match, return 0 for the whole things. */ - - fmt = GET_RTX_FORMAT (code); - for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) - { - switch (fmt[i]) - { - case 'e': - if (! exp_equiv_p (XEXP (x, i), XEXP (y, i), validate, equal_values)) - return 0; - break; - - case 'E': - if (XVECLEN (x, i) != XVECLEN (y, i)) - return 0; - for (j = 0; j < XVECLEN (x, i); j++) - if (! exp_equiv_p (XVECEXP (x, i, j), XVECEXP (y, i, j), - validate, equal_values)) - 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; -} - -/* Return 1 iff any subexpression of X matches Y. - Here we do not require that X or Y be valid (for registers referred to) - for being in the hash table. */ - -static int -refers_to_p (x, y) - rtx x, y; -{ - register int i; - register enum rtx_code code; - register char *fmt; - - repeat: - if (x == y) - return 1; - if (x == 0 || y == 0) - return 0; - - code = GET_CODE (x); - /* If X as a whole has the same code as Y, they may match. - If so, return 1. */ - if (code == GET_CODE (y)) - { - if (exp_equiv_p (x, y, 0, 1)) - return 1; - } - - /* X does not match, so try its subexpressions. */ - - fmt = GET_RTX_FORMAT (code); - for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) - if (fmt[i] == 'e') - { - if (i == 0) - { - x = XEXP (x, 0); - goto repeat; - } - else - if (refers_to_p (XEXP (x, i), y)) - return 1; - } - else if (fmt[i] == 'E') - { - int j; - for (j = 0; j < XVECLEN (x, i); j++) - if (refers_to_p (XVECEXP (x, i, j), y)) - return 1; - } - - return 0; -} - -/* Given ADDR and SIZE (a memory address, and the size of the memory reference), - set PBASE, PSTART, and PEND which correspond to the base of the address, - the starting offset, and ending offset respectively. - - ADDR is known to be a nonvarying address. */ - -/* ??? Despite what the comments say, this function is in fact frequently - passed varying addresses. This does not appear to cause any problems. */ - -static void -set_nonvarying_address_components (addr, size, pbase, pstart, pend) - rtx addr; - int size; - rtx *pbase; - HOST_WIDE_INT *pstart, *pend; -{ - rtx base; - HOST_WIDE_INT start, end; - - base = addr; - start = 0; - end = 0; - - if (flag_pic && GET_CODE (base) == PLUS - && XEXP (base, 0) == pic_offset_table_rtx) - base = XEXP (base, 1); - - /* Registers with nonvarying addresses usually have constant equivalents; - but the frame pointer register is also possible. */ - if (GET_CODE (base) == REG - && qty_const != 0 - && REGNO_QTY_VALID_P (REGNO (base)) - && qty_mode[REG_QTY (REGNO (base))] == GET_MODE (base) - && qty_const[REG_QTY (REGNO (base))] != 0) - base = qty_const[REG_QTY (REGNO (base))]; - else if (GET_CODE (base) == PLUS - && GET_CODE (XEXP (base, 1)) == CONST_INT - && GET_CODE (XEXP (base, 0)) == REG - && qty_const != 0 - && REGNO_QTY_VALID_P (REGNO (XEXP (base, 0))) - && (qty_mode[REG_QTY (REGNO (XEXP (base, 0)))] - == GET_MODE (XEXP (base, 0))) - && qty_const[REG_QTY (REGNO (XEXP (base, 0)))]) - { - start = INTVAL (XEXP (base, 1)); - base = qty_const[REG_QTY (REGNO (XEXP (base, 0)))]; - } - /* This can happen as the result of virtual register instantiation, - if the initial offset is too large to be a valid address. */ - else if (GET_CODE (base) == PLUS - && GET_CODE (XEXP (base, 0)) == REG - && GET_CODE (XEXP (base, 1)) == REG - && qty_const != 0 - && REGNO_QTY_VALID_P (REGNO (XEXP (base, 0))) - && (qty_mode[REG_QTY (REGNO (XEXP (base, 0)))] - == GET_MODE (XEXP (base, 0))) - && qty_const[REG_QTY (REGNO (XEXP (base, 0)))] - && REGNO_QTY_VALID_P (REGNO (XEXP (base, 1))) - && (qty_mode[REG_QTY (REGNO (XEXP (base, 1)))] - == GET_MODE (XEXP (base, 1))) - && qty_const[REG_QTY (REGNO (XEXP (base, 1)))]) - { - rtx tem = qty_const[REG_QTY (REGNO (XEXP (base, 1)))]; - base = qty_const[REG_QTY (REGNO (XEXP (base, 0)))]; - - /* One of the two values must be a constant. */ - if (GET_CODE (base) != CONST_INT) - { - if (GET_CODE (tem) != CONST_INT) - abort (); - start = INTVAL (tem); - } - else - { - start = INTVAL (base); - base = tem; - } - } - - /* Handle everything that we can find inside an address that has been - viewed as constant. */ - - while (1) - { - /* If no part of this switch does a "continue", the code outside - will exit this loop. */ - - switch (GET_CODE (base)) - { - case LO_SUM: - /* By definition, operand1 of a LO_SUM is the associated constant - address. Use the associated constant address as the base - instead. */ - base = XEXP (base, 1); - continue; - - case CONST: - /* Strip off CONST. */ - base = XEXP (base, 0); - continue; - - case PLUS: - if (GET_CODE (XEXP (base, 1)) == CONST_INT) - { - start += INTVAL (XEXP (base, 1)); - base = XEXP (base, 0); - continue; - } - break; - - case AND: - /* Handle the case of an AND which is the negative of a power of - two. This is used to represent unaligned memory operations. */ - if (GET_CODE (XEXP (base, 1)) == CONST_INT - && exact_log2 (- INTVAL (XEXP (base, 1))) > 0) - { - set_nonvarying_address_components (XEXP (base, 0), size, - pbase, pstart, pend); - - /* Assume the worst misalignment. START is affected, but not - END, so compensate but adjusting SIZE. Don't lose any - constant we already had. */ - - size = *pend - *pstart - INTVAL (XEXP (base, 1)) - 1; - start += *pstart + INTVAL (XEXP (base, 1)) + 1; - end += *pend; - base = *pbase; - } - break; - - default: - break; - } - - break; - } - - if (GET_CODE (base) == CONST_INT) - { - start += INTVAL (base); - base = const0_rtx; - } - - end = start + size; - - /* Set the return values. */ - *pbase = base; - *pstart = start; - *pend = end; -} - -/* Return 1 if X has a value that can vary even between two - executions of the program. 0 means X can be compared reliably - against certain constants or near-constants. */ - -static int -cse_rtx_varies_p (x) - register rtx x; -{ - /* We need not check for X and the equivalence class being of the same - mode because if X is equivalent to a constant in some mode, it - doesn't vary in any mode. */ - - if (GET_CODE (x) == REG - && REGNO_QTY_VALID_P (REGNO (x)) - && GET_MODE (x) == qty_mode[REG_QTY (REGNO (x))] - && qty_const[REG_QTY (REGNO (x))] != 0) - return 0; - - if (GET_CODE (x) == PLUS - && GET_CODE (XEXP (x, 1)) == CONST_INT - && GET_CODE (XEXP (x, 0)) == REG - && REGNO_QTY_VALID_P (REGNO (XEXP (x, 0))) - && (GET_MODE (XEXP (x, 0)) - == qty_mode[REG_QTY (REGNO (XEXP (x, 0)))]) - && qty_const[REG_QTY (REGNO (XEXP (x, 0)))]) - return 0; - - /* This can happen as the result of virtual register instantiation, if - the initial constant is too large to be a valid address. This gives - us a three instruction sequence, load large offset into a register, - load fp minus a constant into a register, then a MEM which is the - sum of the two `constant' registers. */ - if (GET_CODE (x) == PLUS - && GET_CODE (XEXP (x, 0)) == REG - && GET_CODE (XEXP (x, 1)) == REG - && REGNO_QTY_VALID_P (REGNO (XEXP (x, 0))) - && (GET_MODE (XEXP (x, 0)) - == qty_mode[REG_QTY (REGNO (XEXP (x, 0)))]) - && qty_const[REG_QTY (REGNO (XEXP (x, 0)))] - && REGNO_QTY_VALID_P (REGNO (XEXP (x, 1))) - && (GET_MODE (XEXP (x, 1)) - == qty_mode[REG_QTY (REGNO (XEXP (x, 1)))]) - && qty_const[REG_QTY (REGNO (XEXP (x, 1)))]) - return 0; - - return rtx_varies_p (x); -} - -/* Canonicalize an expression: - replace each register reference inside it - with the "oldest" equivalent register. - - If INSN is non-zero and we are replacing a pseudo with a hard register - or vice versa, validate_change is used to ensure that INSN remains valid - after we make our substitution. The calls are made with IN_GROUP non-zero - so apply_change_group must be called upon the outermost return from this - function (unless INSN is zero). The result of apply_change_group can - generally be discarded since the changes we are making are optional. */ - -static rtx -canon_reg (x, insn) - rtx x; - rtx insn; -{ - register int i; - register enum rtx_code code; - register char *fmt; - - if (x == 0) - return x; - - 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 x; - - case REG: - { - register int first; - - /* Never replace a hard reg, because hard regs can appear - in more than one machine mode, and we must preserve the mode - of each occurrence. Also, some hard regs appear in - MEMs that are shared and mustn't be altered. Don't try to - replace any reg that maps to a reg of class NO_REGS. */ - if (REGNO (x) < FIRST_PSEUDO_REGISTER - || ! REGNO_QTY_VALID_P (REGNO (x))) - return x; - - first = qty_first_reg[REG_QTY (REGNO (x))]; - return (first >= FIRST_PSEUDO_REGISTER ? regno_reg_rtx[first] - : REGNO_REG_CLASS (first) == NO_REGS ? x - : gen_rtx_REG (qty_mode[REG_QTY (REGNO (x))], first)); - } - - default: - break; - } - - fmt = GET_RTX_FORMAT (code); - for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) - { - register int j; - - if (fmt[i] == 'e') - { - rtx new = canon_reg (XEXP (x, i), insn); - int insn_code; - - /* If replacing pseudo with hard reg or vice versa, ensure the - insn remains valid. Likewise if the insn has MATCH_DUPs. */ - if (insn != 0 && new != 0 - && GET_CODE (new) == REG && GET_CODE (XEXP (x, i)) == REG - && (((REGNO (new) < FIRST_PSEUDO_REGISTER) - != (REGNO (XEXP (x, i)) < FIRST_PSEUDO_REGISTER)) - || (insn_code = recog_memoized (insn)) < 0 - || insn_n_dups[insn_code] > 0)) - validate_change (insn, &XEXP (x, i), new, 1); - else - XEXP (x, i) = new; - } - else if (fmt[i] == 'E') - for (j = 0; j < XVECLEN (x, i); j++) - XVECEXP (x, i, j) = canon_reg (XVECEXP (x, i, j), insn); - } - - return x; -} - -/* LOC is a location within INSN that is an operand address (the contents of - a MEM). Find the best equivalent address to use that is valid for this - insn. - - On most CISC machines, complicated address modes are costly, and rtx_cost - is a good approximation for that cost. However, most RISC machines have - only a few (usually only one) memory reference formats. If an address is - valid at all, it is often just as cheap as any other address. Hence, for - RISC machines, we use the configuration macro `ADDRESS_COST' to compare the - costs of various addresses. For two addresses of equal cost, choose the one - with the highest `rtx_cost' value as that has the potential of eliminating - the most insns. For equal costs, we choose the first in the equivalence - class. Note that we ignore the fact that pseudo registers are cheaper - than hard registers here because we would also prefer the pseudo registers. - */ - -static void -find_best_addr (insn, loc) - rtx insn; - rtx *loc; -{ - struct table_elt *elt; - rtx addr = *loc; -#ifdef ADDRESS_COST - struct table_elt *p; - int found_better = 1; -#endif - int save_do_not_record = do_not_record; - int save_hash_arg_in_memory = hash_arg_in_memory; - int save_hash_arg_in_struct = hash_arg_in_struct; - int addr_volatile; - int regno; - unsigned hash; - - /* Do not try to replace constant addresses or addresses of local and - argument slots. These MEM expressions are made only once and inserted - in many instructions, as well as being used to control symbol table - output. It is not safe to clobber them. - - There are some uncommon cases where the address is already in a register - for some reason, but we cannot take advantage of that because we have - no easy way to unshare the MEM. In addition, looking up all stack - addresses is costly. */ - if ((GET_CODE (addr) == PLUS - && GET_CODE (XEXP (addr, 0)) == REG - && GET_CODE (XEXP (addr, 1)) == CONST_INT - && (regno = REGNO (XEXP (addr, 0)), - regno == FRAME_POINTER_REGNUM || regno == HARD_FRAME_POINTER_REGNUM - || regno == ARG_POINTER_REGNUM)) - || (GET_CODE (addr) == REG - && (regno = REGNO (addr), regno == FRAME_POINTER_REGNUM - || regno == HARD_FRAME_POINTER_REGNUM - || regno == ARG_POINTER_REGNUM)) - || GET_CODE (addr) == ADDRESSOF - || CONSTANT_ADDRESS_P (addr)) - return; - - /* If this address is not simply a register, try to fold it. This will - sometimes simplify the expression. Many simplifications - will not be valid, but some, usually applying the associative rule, will - be valid and produce better code. */ - if (GET_CODE (addr) != REG) - { - rtx folded = fold_rtx (copy_rtx (addr), NULL_RTX); - - if (1 -#ifdef ADDRESS_COST - && (CSE_ADDRESS_COST (folded) < CSE_ADDRESS_COST (addr) - || (CSE_ADDRESS_COST (folded) == CSE_ADDRESS_COST (addr) - && rtx_cost (folded, MEM) > rtx_cost (addr, MEM))) -#else - && rtx_cost (folded, MEM) < rtx_cost (addr, MEM) -#endif - && validate_change (insn, loc, folded, 0)) - addr = folded; - } - - /* If this address is not in the hash table, we can't look for equivalences - of the whole address. Also, ignore if volatile. */ - - do_not_record = 0; - hash = HASH (addr, Pmode); - addr_volatile = do_not_record; - do_not_record = save_do_not_record; - hash_arg_in_memory = save_hash_arg_in_memory; - hash_arg_in_struct = save_hash_arg_in_struct; - - if (addr_volatile) - return; - - elt = lookup (addr, hash, Pmode); - -#ifndef ADDRESS_COST - if (elt) - { - int our_cost = elt->cost; - - /* Find the lowest cost below ours that works. */ - for (elt = elt->first_same_value; elt; elt = elt->next_same_value) - if (elt->cost < our_cost - && (GET_CODE (elt->exp) == REG - || exp_equiv_p (elt->exp, elt->exp, 1, 0)) - && validate_change (insn, loc, - canon_reg (copy_rtx (elt->exp), NULL_RTX), 0)) - return; - } -#else - - if (elt) - { - /* We need to find the best (under the criteria documented above) entry - in the class that is valid. We use the `flag' field to indicate - choices that were invalid and iterate until we can't find a better - one that hasn't already been tried. */ - - for (p = elt->first_same_value; p; p = p->next_same_value) - p->flag = 0; - - while (found_better) - { - int best_addr_cost = CSE_ADDRESS_COST (*loc); - int best_rtx_cost = (elt->cost + 1) >> 1; - struct table_elt *best_elt = elt; - - found_better = 0; - for (p = elt->first_same_value; p; p = p->next_same_value) - if (! p->flag) - { - if ((GET_CODE (p->exp) == REG - || exp_equiv_p (p->exp, p->exp, 1, 0)) - && (CSE_ADDRESS_COST (p->exp) < best_addr_cost - || (CSE_ADDRESS_COST (p->exp) == best_addr_cost - && (p->cost + 1) >> 1 > best_rtx_cost))) - { - found_better = 1; - best_addr_cost = CSE_ADDRESS_COST (p->exp); - best_rtx_cost = (p->cost + 1) >> 1; - best_elt = p; - } - } - - if (found_better) - { - if (validate_change (insn, loc, - canon_reg (copy_rtx (best_elt->exp), - NULL_RTX), 0)) - return; - else - best_elt->flag = 1; - } - } - } - - /* If the address is a binary operation with the first operand a register - and the second a constant, do the same as above, but looking for - equivalences of the register. Then try to simplify before checking for - the best address to use. This catches a few cases: First is when we - have REG+const and the register is another REG+const. We can often merge - the constants and eliminate one insn and one register. It may also be - that a machine has a cheap REG+REG+const. Finally, this improves the - code on the Alpha for unaligned byte stores. */ - - if (flag_expensive_optimizations - && (GET_RTX_CLASS (GET_CODE (*loc)) == '2' - || GET_RTX_CLASS (GET_CODE (*loc)) == 'c') - && GET_CODE (XEXP (*loc, 0)) == REG - && GET_CODE (XEXP (*loc, 1)) == CONST_INT) - { - rtx c = XEXP (*loc, 1); - - do_not_record = 0; - hash = HASH (XEXP (*loc, 0), Pmode); - do_not_record = save_do_not_record; - hash_arg_in_memory = save_hash_arg_in_memory; - hash_arg_in_struct = save_hash_arg_in_struct; - - elt = lookup (XEXP (*loc, 0), hash, Pmode); - if (elt == 0) - return; - - /* We need to find the best (under the criteria documented above) entry - in the class that is valid. We use the `flag' field to indicate - choices that were invalid and iterate until we can't find a better - one that hasn't already been tried. */ - - for (p = elt->first_same_value; p; p = p->next_same_value) - p->flag = 0; - - while (found_better) - { - int best_addr_cost = CSE_ADDRESS_COST (*loc); - int best_rtx_cost = (COST (*loc) + 1) >> 1; - struct table_elt *best_elt = elt; - rtx best_rtx = *loc; - int count; - - /* This is at worst case an O(n^2) algorithm, so limit our search - to the first 32 elements on the list. This avoids trouble - compiling code with very long basic blocks that can easily - call cse_gen_binary so many times that we run out of memory. */ - - found_better = 0; - for (p = elt->first_same_value, count = 0; - p && count < 32; - p = p->next_same_value, count++) - if (! p->flag - && (GET_CODE (p->exp) == REG - || exp_equiv_p (p->exp, p->exp, 1, 0))) - { - rtx new = cse_gen_binary (GET_CODE (*loc), Pmode, p->exp, c); - - if ((CSE_ADDRESS_COST (new) < best_addr_cost - || (CSE_ADDRESS_COST (new) == best_addr_cost - && (COST (new) + 1) >> 1 > best_rtx_cost))) - { - found_better = 1; - best_addr_cost = CSE_ADDRESS_COST (new); - best_rtx_cost = (COST (new) + 1) >> 1; - best_elt = p; - best_rtx = new; - } - } - - if (found_better) - { - if (validate_change (insn, loc, - canon_reg (copy_rtx (best_rtx), - NULL_RTX), 0)) - return; - else - best_elt->flag = 1; - } - } - } -#endif -} - -/* Given an operation (CODE, *PARG1, *PARG2), where code is a comparison - operation (EQ, NE, GT, etc.), follow it back through the hash table and - what values are being compared. - - *PARG1 and *PARG2 are updated to contain the rtx representing the values - actually being compared. For example, if *PARG1 was (cc0) and *PARG2 - was (const_int 0), *PARG1 and *PARG2 will be set to the objects that were - compared to produce cc0. - - The return value is the comparison operator and is either the code of - A or the code corresponding to the inverse of the comparison. */ - -static enum rtx_code -find_comparison_args (code, parg1, parg2, pmode1, pmode2) - enum rtx_code code; - rtx *parg1, *parg2; - enum machine_mode *pmode1, *pmode2; -{ - rtx arg1, arg2; - - arg1 = *parg1, arg2 = *parg2; - - /* If ARG2 is const0_rtx, see what ARG1 is equivalent to. */ - - while (arg2 == CONST0_RTX (GET_MODE (arg1))) - { - /* Set non-zero when we find something of interest. */ - rtx x = 0; - int reverse_code = 0; - struct table_elt *p = 0; - - /* If arg1 is a COMPARE, extract the comparison arguments from it. - On machines with CC0, this is the only case that can occur, since - fold_rtx will return the COMPARE or item being compared with zero - when given CC0. */ - - if (GET_CODE (arg1) == COMPARE && arg2 == const0_rtx) - x = arg1; - - /* If ARG1 is a comparison operator and CODE is testing for - STORE_FLAG_VALUE, get the inner arguments. */ - - else if (GET_RTX_CLASS (GET_CODE (arg1)) == '<') - { - if (code == NE - || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_INT - && code == LT && STORE_FLAG_VALUE == -1) -#ifdef FLOAT_STORE_FLAG_VALUE - || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_FLOAT - && FLOAT_STORE_FLAG_VALUE < 0) -#endif - ) - x = arg1; - else if (code == EQ - || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_INT - && code == GE && STORE_FLAG_VALUE == -1) -#ifdef FLOAT_STORE_FLAG_VALUE - || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_FLOAT - && FLOAT_STORE_FLAG_VALUE < 0) -#endif - ) - x = arg1, reverse_code = 1; - } - - /* ??? We could also check for - - (ne (and (eq (...) (const_int 1))) (const_int 0)) - - and related forms, but let's wait until we see them occurring. */ - - if (x == 0) - /* Look up ARG1 in the hash table and see if it has an equivalence - that lets us see what is being compared. */ - p = lookup (arg1, safe_hash (arg1, GET_MODE (arg1)) % NBUCKETS, - GET_MODE (arg1)); - if (p) p = p->first_same_value; - - for (; p; p = p->next_same_value) - { - enum machine_mode inner_mode = GET_MODE (p->exp); - - /* If the entry isn't valid, skip it. */ - if (! exp_equiv_p (p->exp, p->exp, 1, 0)) - continue; - - if (GET_CODE (p->exp) == COMPARE - /* Another possibility is that this machine has a compare insn - that includes the comparison code. In that case, ARG1 would - be equivalent to a comparison operation that would set ARG1 to - either STORE_FLAG_VALUE or zero. If this is an NE operation, - ORIG_CODE is the actual comparison being done; if it is an EQ, - we must reverse ORIG_CODE. On machine with a negative value - for STORE_FLAG_VALUE, also look at LT and GE operations. */ - || ((code == NE - || (code == LT - && GET_MODE_CLASS (inner_mode) == MODE_INT - && (GET_MODE_BITSIZE (inner_mode) - <= HOST_BITS_PER_WIDE_INT) - && (STORE_FLAG_VALUE - & ((HOST_WIDE_INT) 1 - << (GET_MODE_BITSIZE (inner_mode) - 1)))) -#ifdef FLOAT_STORE_FLAG_VALUE - || (code == LT - && GET_MODE_CLASS (inner_mode) == MODE_FLOAT - && FLOAT_STORE_FLAG_VALUE < 0) -#endif - ) - && GET_RTX_CLASS (GET_CODE (p->exp)) == '<')) - { - x = p->exp; - break; - } - else if ((code == EQ - || (code == GE - && GET_MODE_CLASS (inner_mode) == MODE_INT - && (GET_MODE_BITSIZE (inner_mode) - <= HOST_BITS_PER_WIDE_INT) - && (STORE_FLAG_VALUE - & ((HOST_WIDE_INT) 1 - << (GET_MODE_BITSIZE (inner_mode) - 1)))) -#ifdef FLOAT_STORE_FLAG_VALUE - || (code == GE - && GET_MODE_CLASS (inner_mode) == MODE_FLOAT - && FLOAT_STORE_FLAG_VALUE < 0) -#endif - ) - && GET_RTX_CLASS (GET_CODE (p->exp)) == '<') - { - reverse_code = 1; - x = p->exp; - break; - } - - /* If this is fp + constant, the equivalent is a better operand since - it may let us predict the value of the comparison. */ - else if (NONZERO_BASE_PLUS_P (p->exp)) - { - arg1 = p->exp; - continue; - } - } - - /* If we didn't find a useful equivalence for ARG1, we are done. - Otherwise, set up for the next iteration. */ - if (x == 0) - break; - - arg1 = XEXP (x, 0), arg2 = XEXP (x, 1); - if (GET_RTX_CLASS (GET_CODE (x)) == '<') - code = GET_CODE (x); - - if (reverse_code) - code = reverse_condition (code); - } - - /* Return our results. Return the modes from before fold_rtx - because fold_rtx might produce const_int, and then it's too late. */ - *pmode1 = GET_MODE (arg1), *pmode2 = GET_MODE (arg2); - *parg1 = fold_rtx (arg1, 0), *parg2 = fold_rtx (arg2, 0); - - return code; -} - -/* Try to simplify a unary operation CODE whose output mode is to be - MODE with input operand OP whose mode was originally OP_MODE. - Return zero if no simplification can be made. */ - -rtx -simplify_unary_operation (code, mode, op, op_mode) - enum rtx_code code; - enum machine_mode mode; - rtx op; - enum machine_mode op_mode; -{ - register int width = GET_MODE_BITSIZE (mode); - - /* The order of these tests is critical so that, for example, we don't - check the wrong mode (input vs. output) for a conversion operation, - such as FIX. At some point, this should be simplified. */ - -#if !defined(REAL_IS_NOT_DOUBLE) || defined(REAL_ARITHMETIC) - - if (code == FLOAT && GET_MODE (op) == VOIDmode - && (GET_CODE (op) == CONST_DOUBLE || GET_CODE (op) == CONST_INT)) - { - HOST_WIDE_INT hv, lv; - REAL_VALUE_TYPE d; - - if (GET_CODE (op) == CONST_INT) - lv = INTVAL (op), hv = INTVAL (op) < 0 ? -1 : 0; - else - lv = CONST_DOUBLE_LOW (op), hv = CONST_DOUBLE_HIGH (op); - -#ifdef REAL_ARITHMETIC - REAL_VALUE_FROM_INT (d, lv, hv, mode); -#else - if (hv < 0) - { - d = (double) (~ hv); - d *= ((double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2)) - * (double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2))); - d += (double) (unsigned HOST_WIDE_INT) (~ lv); - d = (- d - 1.0); - } - else - { - d = (double) hv; - d *= ((double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2)) - * (double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2))); - d += (double) (unsigned HOST_WIDE_INT) lv; - } -#endif /* REAL_ARITHMETIC */ - d = real_value_truncate (mode, d); - return CONST_DOUBLE_FROM_REAL_VALUE (d, mode); - } - else if (code == UNSIGNED_FLOAT && GET_MODE (op) == VOIDmode - && (GET_CODE (op) == CONST_DOUBLE || GET_CODE (op) == CONST_INT)) - { - HOST_WIDE_INT hv, lv; - REAL_VALUE_TYPE d; - - if (GET_CODE (op) == CONST_INT) - lv = INTVAL (op), hv = INTVAL (op) < 0 ? -1 : 0; - else - lv = CONST_DOUBLE_LOW (op), hv = CONST_DOUBLE_HIGH (op); - - if (op_mode == VOIDmode) - { - /* We don't know how to interpret negative-looking numbers in - this case, so don't try to fold those. */ - if (hv < 0) - return 0; - } - else if (GET_MODE_BITSIZE (op_mode) >= HOST_BITS_PER_WIDE_INT * 2) - ; - else - hv = 0, lv &= GET_MODE_MASK (op_mode); - -#ifdef REAL_ARITHMETIC - REAL_VALUE_FROM_UNSIGNED_INT (d, lv, hv, mode); -#else - - d = (double) (unsigned HOST_WIDE_INT) hv; - d *= ((double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2)) - * (double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2))); - d += (double) (unsigned HOST_WIDE_INT) lv; -#endif /* REAL_ARITHMETIC */ - d = real_value_truncate (mode, d); - return CONST_DOUBLE_FROM_REAL_VALUE (d, mode); - } -#endif - - if (GET_CODE (op) == CONST_INT - && width <= HOST_BITS_PER_WIDE_INT && width > 0) - { - register HOST_WIDE_INT arg0 = INTVAL (op); - register HOST_WIDE_INT val; - - switch (code) - { - case NOT: - val = ~ arg0; - break; - - case NEG: - val = - arg0; - break; - - case ABS: - val = (arg0 >= 0 ? arg0 : - arg0); - break; - - case FFS: - /* Don't use ffs here. Instead, get low order bit and then its - number. If arg0 is zero, this will return 0, as desired. */ - arg0 &= GET_MODE_MASK (mode); - val = exact_log2 (arg0 & (- arg0)) + 1; - break; - - case TRUNCATE: - val = arg0; - break; - - case ZERO_EXTEND: - if (op_mode == VOIDmode) - op_mode = mode; - if (GET_MODE_BITSIZE (op_mode) == HOST_BITS_PER_WIDE_INT) - { - /* If we were really extending the mode, - we would have to distinguish between zero-extension - and sign-extension. */ - if (width != GET_MODE_BITSIZE (op_mode)) - abort (); - val = arg0; - } - else if (GET_MODE_BITSIZE (op_mode) < HOST_BITS_PER_WIDE_INT) - val = arg0 & ~((HOST_WIDE_INT) (-1) << GET_MODE_BITSIZE (op_mode)); - else - return 0; - break; - - case SIGN_EXTEND: - if (op_mode == VOIDmode) - op_mode = mode; - if (GET_MODE_BITSIZE (op_mode) == HOST_BITS_PER_WIDE_INT) - { - /* If we were really extending the mode, - we would have to distinguish between zero-extension - and sign-extension. */ - if (width != GET_MODE_BITSIZE (op_mode)) - abort (); - val = arg0; - } - else if (GET_MODE_BITSIZE (op_mode) < HOST_BITS_PER_WIDE_INT) - { - val - = arg0 & ~((HOST_WIDE_INT) (-1) << GET_MODE_BITSIZE (op_mode)); - if (val - & ((HOST_WIDE_INT) 1 << (GET_MODE_BITSIZE (op_mode) - 1))) - val -= (HOST_WIDE_INT) 1 << GET_MODE_BITSIZE (op_mode); - } - else - return 0; - break; - - case SQRT: - return 0; - - default: - abort (); - } - - /* Clear the bits that don't belong in our mode, - unless they and our sign bit are all one. - So we get either a reasonable negative value or a reasonable - unsigned value for this mode. */ - if (width < HOST_BITS_PER_WIDE_INT - && ((val & ((HOST_WIDE_INT) (-1) << (width - 1))) - != ((HOST_WIDE_INT) (-1) << (width - 1)))) - val &= ((HOST_WIDE_INT) 1 << width) - 1; - - /* If this would be an entire word for the target, but is not for - the host, then sign-extend on the host so that the number will look - the same way on the host that it would on the target. - - For example, when building a 64 bit alpha hosted 32 bit sparc - targeted compiler, then we want the 32 bit unsigned value -1 to be - represented as a 64 bit value -1, and not as 0x00000000ffffffff. - The later confuses the sparc backend. */ - - if (BITS_PER_WORD < HOST_BITS_PER_WIDE_INT && BITS_PER_WORD == width - && (val & ((HOST_WIDE_INT) 1 << (width - 1)))) - val |= ((HOST_WIDE_INT) (-1) << width); - - return GEN_INT (val); - } - - /* We can do some operations on integer CONST_DOUBLEs. Also allow - for a DImode operation on a CONST_INT. */ - else if (GET_MODE (op) == VOIDmode && width <= HOST_BITS_PER_INT * 2 - && (GET_CODE (op) == CONST_DOUBLE || GET_CODE (op) == CONST_INT)) - { - HOST_WIDE_INT l1, h1, lv, hv; - - if (GET_CODE (op) == CONST_DOUBLE) - l1 = CONST_DOUBLE_LOW (op), h1 = CONST_DOUBLE_HIGH (op); - else - l1 = INTVAL (op), h1 = l1 < 0 ? -1 : 0; - - switch (code) - { - case NOT: - lv = ~ l1; - hv = ~ h1; - break; - - case NEG: - neg_double (l1, h1, &lv, &hv); - break; - - case ABS: - if (h1 < 0) - neg_double (l1, h1, &lv, &hv); - else - lv = l1, hv = h1; - break; - - case FFS: - hv = 0; - if (l1 == 0) - lv = HOST_BITS_PER_WIDE_INT + exact_log2 (h1 & (-h1)) + 1; - else - lv = exact_log2 (l1 & (-l1)) + 1; - break; - - case TRUNCATE: - /* This is just a change-of-mode, so do nothing. */ - lv = l1, hv = h1; - break; - - case ZERO_EXTEND: - if (op_mode == VOIDmode - || GET_MODE_BITSIZE (op_mode) > HOST_BITS_PER_WIDE_INT) - return 0; - - hv = 0; - lv = l1 & GET_MODE_MASK (op_mode); - break; - - case SIGN_EXTEND: - if (op_mode == VOIDmode - || GET_MODE_BITSIZE (op_mode) > HOST_BITS_PER_WIDE_INT) - return 0; - else - { - lv = l1 & GET_MODE_MASK (op_mode); - if (GET_MODE_BITSIZE (op_mode) < HOST_BITS_PER_WIDE_INT - && (lv & ((HOST_WIDE_INT) 1 - << (GET_MODE_BITSIZE (op_mode) - 1))) != 0) - lv -= (HOST_WIDE_INT) 1 << GET_MODE_BITSIZE (op_mode); - - hv = (lv < 0) ? ~ (HOST_WIDE_INT) 0 : 0; - } - break; - - case SQRT: - return 0; - - default: - return 0; - } - - return immed_double_const (lv, hv, mode); - } - -#if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC) - else if (GET_CODE (op) == CONST_DOUBLE - && GET_MODE_CLASS (mode) == MODE_FLOAT) - { - REAL_VALUE_TYPE d; - jmp_buf handler; - rtx x; - - if (setjmp (handler)) - /* There used to be a warning here, but that is inadvisable. - People may want to cause traps, and the natural way - to do it should not get a warning. */ - return 0; - - set_float_handler (handler); - - REAL_VALUE_FROM_CONST_DOUBLE (d, op); - - switch (code) - { - case NEG: - d = REAL_VALUE_NEGATE (d); - break; - - case ABS: - if (REAL_VALUE_NEGATIVE (d)) - d = REAL_VALUE_NEGATE (d); - break; - - case FLOAT_TRUNCATE: - d = real_value_truncate (mode, d); - break; - - case FLOAT_EXTEND: - /* All this does is change the mode. */ - break; - - case FIX: - d = REAL_VALUE_RNDZINT (d); - break; - - case UNSIGNED_FIX: - d = REAL_VALUE_UNSIGNED_RNDZINT (d); - break; - - case SQRT: - return 0; - - default: - abort (); - } - - x = CONST_DOUBLE_FROM_REAL_VALUE (d, mode); - set_float_handler (NULL_PTR); - return x; - } - - else if (GET_CODE (op) == CONST_DOUBLE - && GET_MODE_CLASS (GET_MODE (op)) == MODE_FLOAT - && GET_MODE_CLASS (mode) == MODE_INT - && width <= HOST_BITS_PER_WIDE_INT && width > 0) - { - REAL_VALUE_TYPE d; - jmp_buf handler; - HOST_WIDE_INT val; - - if (setjmp (handler)) - return 0; - - set_float_handler (handler); - - REAL_VALUE_FROM_CONST_DOUBLE (d, op); - - switch (code) - { - case FIX: - val = REAL_VALUE_FIX (d); - break; - - case UNSIGNED_FIX: - val = REAL_VALUE_UNSIGNED_FIX (d); - break; - - default: - abort (); - } - - set_float_handler (NULL_PTR); - - /* Clear the bits that don't belong in our mode, - unless they and our sign bit are all one. - So we get either a reasonable negative value or a reasonable - unsigned value for this mode. */ - if (width < HOST_BITS_PER_WIDE_INT - && ((val & ((HOST_WIDE_INT) (-1) << (width - 1))) - != ((HOST_WIDE_INT) (-1) << (width - 1)))) - val &= ((HOST_WIDE_INT) 1 << width) - 1; - - /* If this would be an entire word for the target, but is not for - the host, then sign-extend on the host so that the number will look - the same way on the host that it would on the target. - - For example, when building a 64 bit alpha hosted 32 bit sparc - targeted compiler, then we want the 32 bit unsigned value -1 to be - represented as a 64 bit value -1, and not as 0x00000000ffffffff. - The later confuses the sparc backend. */ - - if (BITS_PER_WORD < HOST_BITS_PER_WIDE_INT && BITS_PER_WORD == width - && (val & ((HOST_WIDE_INT) 1 << (width - 1)))) - val |= ((HOST_WIDE_INT) (-1) << width); - - return GEN_INT (val); - } -#endif - /* This was formerly used only for non-IEEE float. - eggert@twinsun.com says it is safe for IEEE also. */ - else - { - /* There are some simplifications we can do even if the operands - aren't constant. */ - switch (code) - { - case NEG: - case NOT: - /* (not (not X)) == X, similarly for NEG. */ - if (GET_CODE (op) == code) - return XEXP (op, 0); - break; - - case SIGN_EXTEND: - /* (sign_extend (truncate (minus (label_ref L1) (label_ref L2)))) - becomes just the MINUS if its mode is MODE. This allows - folding switch statements on machines using casesi (such as - the Vax). */ - if (GET_CODE (op) == TRUNCATE - && GET_MODE (XEXP (op, 0)) == mode - && GET_CODE (XEXP (op, 0)) == MINUS - && GET_CODE (XEXP (XEXP (op, 0), 0)) == LABEL_REF - && GET_CODE (XEXP (XEXP (op, 0), 1)) == LABEL_REF) - return XEXP (op, 0); - -#ifdef POINTERS_EXTEND_UNSIGNED - if (! POINTERS_EXTEND_UNSIGNED - && mode == Pmode && GET_MODE (op) == ptr_mode - && CONSTANT_P (op)) - return convert_memory_address (Pmode, op); -#endif - break; - -#ifdef POINTERS_EXTEND_UNSIGNED - case ZERO_EXTEND: - if (POINTERS_EXTEND_UNSIGNED - && mode == Pmode && GET_MODE (op) == ptr_mode - && CONSTANT_P (op)) - return convert_memory_address (Pmode, op); - break; -#endif - - default: - break; - } - - return 0; - } -} - -/* Simplify a binary operation CODE with result mode MODE, operating on OP0 - and OP1. Return 0 if no simplification is possible. - - Don't use this for relational operations such as EQ or LT. - Use simplify_relational_operation instead. */ - -rtx -simplify_binary_operation (code, mode, op0, op1) - enum rtx_code code; - enum machine_mode mode; - rtx op0, op1; -{ - register HOST_WIDE_INT arg0, arg1, arg0s, arg1s; - HOST_WIDE_INT val; - int width = GET_MODE_BITSIZE (mode); - rtx tem; - - /* Relational operations don't work here. We must know the mode - of the operands in order to do the comparison correctly. - Assuming a full word can give incorrect results. - Consider comparing 128 with -128 in QImode. */ - - if (GET_RTX_CLASS (code) == '<') - abort (); - -#if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC) - if (GET_MODE_CLASS (mode) == MODE_FLOAT - && GET_CODE (op0) == CONST_DOUBLE && GET_CODE (op1) == CONST_DOUBLE - && mode == GET_MODE (op0) && mode == GET_MODE (op1)) - { - REAL_VALUE_TYPE f0, f1, value; - jmp_buf handler; - - if (setjmp (handler)) - return 0; - - set_float_handler (handler); - - REAL_VALUE_FROM_CONST_DOUBLE (f0, op0); - REAL_VALUE_FROM_CONST_DOUBLE (f1, op1); - f0 = real_value_truncate (mode, f0); - f1 = real_value_truncate (mode, f1); - -#ifdef REAL_ARITHMETIC -#ifndef REAL_INFINITY - if (code == DIV && REAL_VALUES_EQUAL (f1, dconst0)) - return 0; -#endif - REAL_ARITHMETIC (value, rtx_to_tree_code (code), f0, f1); -#else - switch (code) - { - case PLUS: - value = f0 + f1; - break; - case MINUS: - value = f0 - f1; - break; - case MULT: - value = f0 * f1; - break; - case DIV: -#ifndef REAL_INFINITY - if (f1 == 0) - return 0; -#endif - value = f0 / f1; - break; - case SMIN: - value = MIN (f0, f1); - break; - case SMAX: - value = MAX (f0, f1); - break; - default: - abort (); - } -#endif - - value = real_value_truncate (mode, value); - set_float_handler (NULL_PTR); - return CONST_DOUBLE_FROM_REAL_VALUE (value, mode); - } -#endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */ - - /* We can fold some multi-word operations. */ - if (GET_MODE_CLASS (mode) == MODE_INT - && width == HOST_BITS_PER_WIDE_INT * 2 - && (GET_CODE (op0) == CONST_DOUBLE || GET_CODE (op0) == CONST_INT) - && (GET_CODE (op1) == CONST_DOUBLE || GET_CODE (op1) == CONST_INT)) - { - HOST_WIDE_INT l1, l2, h1, h2, lv, hv; - - if (GET_CODE (op0) == CONST_DOUBLE) - l1 = CONST_DOUBLE_LOW (op0), h1 = CONST_DOUBLE_HIGH (op0); - else - l1 = INTVAL (op0), h1 = l1 < 0 ? -1 : 0; - - if (GET_CODE (op1) == CONST_DOUBLE) - l2 = CONST_DOUBLE_LOW (op1), h2 = CONST_DOUBLE_HIGH (op1); - else - l2 = INTVAL (op1), h2 = l2 < 0 ? -1 : 0; - - switch (code) - { - case MINUS: - /* A - B == A + (-B). */ - neg_double (l2, h2, &lv, &hv); - l2 = lv, h2 = hv; - - /* .. fall through ... */ - - case PLUS: - add_double (l1, h1, l2, h2, &lv, &hv); - break; - - case MULT: - mul_double (l1, h1, l2, h2, &lv, &hv); - break; - - case DIV: case MOD: case UDIV: case UMOD: - /* We'd need to include tree.h to do this and it doesn't seem worth - it. */ - return 0; - - case AND: - lv = l1 & l2, hv = h1 & h2; - break; - - case IOR: - lv = l1 | l2, hv = h1 | h2; - break; - - case XOR: - lv = l1 ^ l2, hv = h1 ^ h2; - break; - - case SMIN: - if (h1 < h2 - || (h1 == h2 - && ((unsigned HOST_WIDE_INT) l1 - < (unsigned HOST_WIDE_INT) l2))) - lv = l1, hv = h1; - else - lv = l2, hv = h2; - break; - - case SMAX: - if (h1 > h2 - || (h1 == h2 - && ((unsigned HOST_WIDE_INT) l1 - > (unsigned HOST_WIDE_INT) l2))) - lv = l1, hv = h1; - else - lv = l2, hv = h2; - break; - - case UMIN: - if ((unsigned HOST_WIDE_INT) h1 < (unsigned HOST_WIDE_INT) h2 - || (h1 == h2 - && ((unsigned HOST_WIDE_INT) l1 - < (unsigned HOST_WIDE_INT) l2))) - lv = l1, hv = h1; - else - lv = l2, hv = h2; - break; - - case UMAX: - if ((unsigned HOST_WIDE_INT) h1 > (unsigned HOST_WIDE_INT) h2 - || (h1 == h2 - && ((unsigned HOST_WIDE_INT) l1 - > (unsigned HOST_WIDE_INT) l2))) - lv = l1, hv = h1; - else - lv = l2, hv = h2; - break; - - case LSHIFTRT: case ASHIFTRT: - case ASHIFT: - case ROTATE: case ROTATERT: -#ifdef SHIFT_COUNT_TRUNCATED - if (SHIFT_COUNT_TRUNCATED) - l2 &= (GET_MODE_BITSIZE (mode) - 1), h2 = 0; -#endif - - if (h2 != 0 || l2 < 0 || l2 >= GET_MODE_BITSIZE (mode)) - return 0; - - if (code == LSHIFTRT || code == ASHIFTRT) - rshift_double (l1, h1, l2, GET_MODE_BITSIZE (mode), &lv, &hv, - code == ASHIFTRT); - else if (code == ASHIFT) - lshift_double (l1, h1, l2, GET_MODE_BITSIZE (mode), &lv, &hv, 1); - else if (code == ROTATE) - lrotate_double (l1, h1, l2, GET_MODE_BITSIZE (mode), &lv, &hv); - else /* code == ROTATERT */ - rrotate_double (l1, h1, l2, GET_MODE_BITSIZE (mode), &lv, &hv); - break; - - default: - return 0; - } - - return immed_double_const (lv, hv, mode); - } - - if (GET_CODE (op0) != CONST_INT || GET_CODE (op1) != CONST_INT - || width > HOST_BITS_PER_WIDE_INT || width == 0) - { - /* Even if we can't compute a constant result, - there are some cases worth simplifying. */ - - switch (code) - { - case PLUS: - /* In IEEE floating point, x+0 is not the same as x. Similarly - for the other optimizations below. */ - if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT - && FLOAT_MODE_P (mode) && ! flag_fast_math) - break; - - if (op1 == CONST0_RTX (mode)) - return op0; - - /* ((-a) + b) -> (b - a) and similarly for (a + (-b)) */ - if (GET_CODE (op0) == NEG) - return cse_gen_binary (MINUS, mode, op1, XEXP (op0, 0)); - else if (GET_CODE (op1) == NEG) - return cse_gen_binary (MINUS, mode, op0, XEXP (op1, 0)); - - /* Handle both-operands-constant cases. We can only add - CONST_INTs to constants since the sum of relocatable symbols - can't be handled by most assemblers. Don't add CONST_INT - to CONST_INT since overflow won't be computed properly if wider - than HOST_BITS_PER_WIDE_INT. */ - - if (CONSTANT_P (op0) && GET_MODE (op0) != VOIDmode - && GET_CODE (op1) == CONST_INT) - return plus_constant (op0, INTVAL (op1)); - else if (CONSTANT_P (op1) && GET_MODE (op1) != VOIDmode - && GET_CODE (op0) == CONST_INT) - return plus_constant (op1, INTVAL (op0)); - - /* See if this is something like X * C - X or vice versa or - if the multiplication is written as a shift. If so, we can - distribute and make a new multiply, shift, or maybe just - have X (if C is 2 in the example above). But don't make - real multiply if we didn't have one before. */ - - if (! FLOAT_MODE_P (mode)) - { - HOST_WIDE_INT coeff0 = 1, coeff1 = 1; - rtx lhs = op0, rhs = op1; - int had_mult = 0; - - if (GET_CODE (lhs) == NEG) - coeff0 = -1, lhs = XEXP (lhs, 0); - else if (GET_CODE (lhs) == MULT - && GET_CODE (XEXP (lhs, 1)) == CONST_INT) - { - coeff0 = INTVAL (XEXP (lhs, 1)), lhs = XEXP (lhs, 0); - had_mult = 1; - } - else if (GET_CODE (lhs) == ASHIFT - && GET_CODE (XEXP (lhs, 1)) == CONST_INT - && INTVAL (XEXP (lhs, 1)) >= 0 - && INTVAL (XEXP (lhs, 1)) < HOST_BITS_PER_WIDE_INT) - { - coeff0 = ((HOST_WIDE_INT) 1) << INTVAL (XEXP (lhs, 1)); - lhs = XEXP (lhs, 0); - } - - if (GET_CODE (rhs) == NEG) - coeff1 = -1, rhs = XEXP (rhs, 0); - else if (GET_CODE (rhs) == MULT - && GET_CODE (XEXP (rhs, 1)) == CONST_INT) - { - coeff1 = INTVAL (XEXP (rhs, 1)), rhs = XEXP (rhs, 0); - had_mult = 1; - } - else if (GET_CODE (rhs) == ASHIFT - && GET_CODE (XEXP (rhs, 1)) == CONST_INT - && INTVAL (XEXP (rhs, 1)) >= 0 - && INTVAL (XEXP (rhs, 1)) < HOST_BITS_PER_WIDE_INT) - { - coeff1 = ((HOST_WIDE_INT) 1) << INTVAL (XEXP (rhs, 1)); - rhs = XEXP (rhs, 0); - } - - if (rtx_equal_p (lhs, rhs)) - { - tem = cse_gen_binary (MULT, mode, lhs, - GEN_INT (coeff0 + coeff1)); - return (GET_CODE (tem) == MULT && ! had_mult) ? 0 : tem; - } - } - - /* If one of the operands is a PLUS or a MINUS, see if we can - simplify this by the associative law. - Don't use the associative law for floating point. - The inaccuracy makes it nonassociative, - and subtle programs can break if operations are associated. */ - - if (INTEGRAL_MODE_P (mode) - && (GET_CODE (op0) == PLUS || GET_CODE (op0) == MINUS - || GET_CODE (op1) == PLUS || GET_CODE (op1) == MINUS) - && (tem = simplify_plus_minus (code, mode, op0, op1)) != 0) - return tem; - break; - - case COMPARE: -#ifdef HAVE_cc0 - /* Convert (compare FOO (const_int 0)) to FOO unless we aren't - using cc0, in which case we want to leave it as a COMPARE - so we can distinguish it from a register-register-copy. - - In IEEE floating point, x-0 is not the same as x. */ - - if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT - || ! FLOAT_MODE_P (mode) || flag_fast_math) - && op1 == CONST0_RTX (mode)) - return op0; -#else - /* Do nothing here. */ -#endif - break; - - case MINUS: - /* None of these optimizations can be done for IEEE - floating point. */ - if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT - && FLOAT_MODE_P (mode) && ! flag_fast_math) - break; - - /* We can't assume x-x is 0 even with non-IEEE floating point, - but since it is zero except in very strange circumstances, we - will treat it as zero with -ffast-math. */ - if (rtx_equal_p (op0, op1) - && ! side_effects_p (op0) - && (! FLOAT_MODE_P (mode) || flag_fast_math)) - return CONST0_RTX (mode); - - /* Change subtraction from zero into negation. */ - if (op0 == CONST0_RTX (mode)) - return gen_rtx_NEG (mode, op1); - - /* (-1 - a) is ~a. */ - if (op0 == constm1_rtx) - return gen_rtx_NOT (mode, op1); - - /* Subtracting 0 has no effect. */ - if (op1 == CONST0_RTX (mode)) - return op0; - - /* See if this is something like X * C - X or vice versa or - if the multiplication is written as a shift. If so, we can - distribute and make a new multiply, shift, or maybe just - have X (if C is 2 in the example above). But don't make - real multiply if we didn't have one before. */ - - if (! FLOAT_MODE_P (mode)) - { - HOST_WIDE_INT coeff0 = 1, coeff1 = 1; - rtx lhs = op0, rhs = op1; - int had_mult = 0; - - if (GET_CODE (lhs) == NEG) - coeff0 = -1, lhs = XEXP (lhs, 0); - else if (GET_CODE (lhs) == MULT - && GET_CODE (XEXP (lhs, 1)) == CONST_INT) - { - coeff0 = INTVAL (XEXP (lhs, 1)), lhs = XEXP (lhs, 0); - had_mult = 1; - } - else if (GET_CODE (lhs) == ASHIFT - && GET_CODE (XEXP (lhs, 1)) == CONST_INT - && INTVAL (XEXP (lhs, 1)) >= 0 - && INTVAL (XEXP (lhs, 1)) < HOST_BITS_PER_WIDE_INT) - { - coeff0 = ((HOST_WIDE_INT) 1) << INTVAL (XEXP (lhs, 1)); - lhs = XEXP (lhs, 0); - } - - if (GET_CODE (rhs) == NEG) - coeff1 = - 1, rhs = XEXP (rhs, 0); - else if (GET_CODE (rhs) == MULT - && GET_CODE (XEXP (rhs, 1)) == CONST_INT) - { - coeff1 = INTVAL (XEXP (rhs, 1)), rhs = XEXP (rhs, 0); - had_mult = 1; - } - else if (GET_CODE (rhs) == ASHIFT - && GET_CODE (XEXP (rhs, 1)) == CONST_INT - && INTVAL (XEXP (rhs, 1)) >= 0 - && INTVAL (XEXP (rhs, 1)) < HOST_BITS_PER_WIDE_INT) - { - coeff1 = ((HOST_WIDE_INT) 1) << INTVAL (XEXP (rhs, 1)); - rhs = XEXP (rhs, 0); - } - - if (rtx_equal_p (lhs, rhs)) - { - tem = cse_gen_binary (MULT, mode, lhs, - GEN_INT (coeff0 - coeff1)); - return (GET_CODE (tem) == MULT && ! had_mult) ? 0 : tem; - } - } - - /* (a - (-b)) -> (a + b). */ - if (GET_CODE (op1) == NEG) - return cse_gen_binary (PLUS, mode, op0, XEXP (op1, 0)); - - /* If one of the operands is a PLUS or a MINUS, see if we can - simplify this by the associative law. - Don't use the associative law for floating point. - The inaccuracy makes it nonassociative, - and subtle programs can break if operations are associated. */ - - if (INTEGRAL_MODE_P (mode) - && (GET_CODE (op0) == PLUS || GET_CODE (op0) == MINUS - || GET_CODE (op1) == PLUS || GET_CODE (op1) == MINUS) - && (tem = simplify_plus_minus (code, mode, op0, op1)) != 0) - return tem; - - /* Don't let a relocatable value get a negative coeff. */ - if (GET_CODE (op1) == CONST_INT && GET_MODE (op0) != VOIDmode) - return plus_constant (op0, - INTVAL (op1)); - - /* (x - (x & y)) -> (x & ~y) */ - if (GET_CODE (op1) == AND) - { - if (rtx_equal_p (op0, XEXP (op1, 0))) - return cse_gen_binary (AND, mode, op0, gen_rtx_NOT (mode, XEXP (op1, 1))); - if (rtx_equal_p (op0, XEXP (op1, 1))) - return cse_gen_binary (AND, mode, op0, gen_rtx_NOT (mode, XEXP (op1, 0))); - } - break; - - case MULT: - if (op1 == constm1_rtx) - { - tem = simplify_unary_operation (NEG, mode, op0, mode); - - return tem ? tem : gen_rtx_NEG (mode, op0); - } - - /* In IEEE floating point, x*0 is not always 0. */ - if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT - || ! FLOAT_MODE_P (mode) || flag_fast_math) - && op1 == CONST0_RTX (mode) - && ! side_effects_p (op0)) - return op1; - - /* In IEEE floating point, x*1 is not equivalent to x for nans. - However, ANSI says we can drop signals, - so we can do this anyway. */ - if (op1 == CONST1_RTX (mode)) - return op0; - - /* Convert multiply by constant power of two into shift unless - we are still generating RTL. This test is a kludge. */ - if (GET_CODE (op1) == CONST_INT - && (val = exact_log2 (INTVAL (op1))) >= 0 - /* If the mode is larger than the host word size, and the - uppermost bit is set, then this isn't a power of two due - to implicit sign extension. */ - && (width <= HOST_BITS_PER_WIDE_INT - || val != HOST_BITS_PER_WIDE_INT - 1) - && ! rtx_equal_function_value_matters) - return gen_rtx_ASHIFT (mode, op0, GEN_INT (val)); - - if (GET_CODE (op1) == CONST_DOUBLE - && GET_MODE_CLASS (GET_MODE (op1)) == MODE_FLOAT) - { - REAL_VALUE_TYPE d; - jmp_buf handler; - int op1is2, op1ism1; - - if (setjmp (handler)) - return 0; - - set_float_handler (handler); - REAL_VALUE_FROM_CONST_DOUBLE (d, op1); - op1is2 = REAL_VALUES_EQUAL (d, dconst2); - op1ism1 = REAL_VALUES_EQUAL (d, dconstm1); - set_float_handler (NULL_PTR); - - /* x*2 is x+x and x*(-1) is -x */ - if (op1is2 && GET_MODE (op0) == mode) - return gen_rtx_PLUS (mode, op0, copy_rtx (op0)); - - else if (op1ism1 && GET_MODE (op0) == mode) - return gen_rtx_NEG (mode, op0); - } - break; - - case IOR: - if (op1 == const0_rtx) - return op0; - if (GET_CODE (op1) == CONST_INT - && (INTVAL (op1) & GET_MODE_MASK (mode)) == GET_MODE_MASK (mode)) - return op1; - if (rtx_equal_p (op0, op1) && ! side_effects_p (op0)) - return op0; - /* A | (~A) -> -1 */ - if (((GET_CODE (op0) == NOT && rtx_equal_p (XEXP (op0, 0), op1)) - || (GET_CODE (op1) == NOT && rtx_equal_p (XEXP (op1, 0), op0))) - && ! side_effects_p (op0) - && GET_MODE_CLASS (mode) != MODE_CC) - return constm1_rtx; - break; - - case XOR: - if (op1 == const0_rtx) - return op0; - if (GET_CODE (op1) == CONST_INT - && (INTVAL (op1) & GET_MODE_MASK (mode)) == GET_MODE_MASK (mode)) - return gen_rtx_NOT (mode, op0); - if (op0 == op1 && ! side_effects_p (op0) - && GET_MODE_CLASS (mode) != MODE_CC) - return const0_rtx; - break; - - case AND: - if (op1 == const0_rtx && ! side_effects_p (op0)) - return const0_rtx; - if (GET_CODE (op1) == CONST_INT - && (INTVAL (op1) & GET_MODE_MASK (mode)) == GET_MODE_MASK (mode)) - return op0; - if (op0 == op1 && ! side_effects_p (op0) - && GET_MODE_CLASS (mode) != MODE_CC) - return op0; - /* A & (~A) -> 0 */ - if (((GET_CODE (op0) == NOT && rtx_equal_p (XEXP (op0, 0), op1)) - || (GET_CODE (op1) == NOT && rtx_equal_p (XEXP (op1, 0), op0))) - && ! side_effects_p (op0) - && GET_MODE_CLASS (mode) != MODE_CC) - return const0_rtx; - break; - - case UDIV: - /* Convert divide by power of two into shift (divide by 1 handled - below). */ - if (GET_CODE (op1) == CONST_INT - && (arg1 = exact_log2 (INTVAL (op1))) > 0) - return gen_rtx_LSHIFTRT (mode, op0, GEN_INT (arg1)); - - /* ... fall through ... */ - - case DIV: - if (op1 == CONST1_RTX (mode)) - return op0; - - /* In IEEE floating point, 0/x is not always 0. */ - if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT - || ! FLOAT_MODE_P (mode) || flag_fast_math) - && op0 == CONST0_RTX (mode) - && ! side_effects_p (op1)) - return op0; - -#if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC) - /* Change division by a constant into multiplication. Only do - this with -ffast-math until an expert says it is safe in - general. */ - else if (GET_CODE (op1) == CONST_DOUBLE - && GET_MODE_CLASS (GET_MODE (op1)) == MODE_FLOAT - && op1 != CONST0_RTX (mode) - && flag_fast_math) - { - REAL_VALUE_TYPE d; - REAL_VALUE_FROM_CONST_DOUBLE (d, op1); - - if (! REAL_VALUES_EQUAL (d, dconst0)) - { -#if defined (REAL_ARITHMETIC) - REAL_ARITHMETIC (d, rtx_to_tree_code (DIV), dconst1, d); - return gen_rtx_MULT (mode, op0, - CONST_DOUBLE_FROM_REAL_VALUE (d, mode)); -#else - return gen_rtx_MULT (mode, op0, - CONST_DOUBLE_FROM_REAL_VALUE (1./d, mode)); -#endif - } - } -#endif - break; - - case UMOD: - /* Handle modulus by power of two (mod with 1 handled below). */ - if (GET_CODE (op1) == CONST_INT - && exact_log2 (INTVAL (op1)) > 0) - return gen_rtx_AND (mode, op0, GEN_INT (INTVAL (op1) - 1)); - - /* ... fall through ... */ - - case MOD: - if ((op0 == const0_rtx || op1 == const1_rtx) - && ! side_effects_p (op0) && ! side_effects_p (op1)) - return const0_rtx; - break; - - case ROTATERT: - case ROTATE: - /* Rotating ~0 always results in ~0. */ - if (GET_CODE (op0) == CONST_INT && width <= HOST_BITS_PER_WIDE_INT - && INTVAL (op0) == GET_MODE_MASK (mode) - && ! side_effects_p (op1)) - return op0; - - /* ... fall through ... */ - - case ASHIFT: - case ASHIFTRT: - case LSHIFTRT: - if (op1 == const0_rtx) - return op0; - if (op0 == const0_rtx && ! side_effects_p (op1)) - return op0; - break; - - case SMIN: - if (width <= HOST_BITS_PER_WIDE_INT && GET_CODE (op1) == CONST_INT - && INTVAL (op1) == (HOST_WIDE_INT) 1 << (width -1) - && ! side_effects_p (op0)) - return op1; - else if (rtx_equal_p (op0, op1) && ! side_effects_p (op0)) - return op0; - break; - - case SMAX: - if (width <= HOST_BITS_PER_WIDE_INT && GET_CODE (op1) == CONST_INT - && (INTVAL (op1) - == (unsigned HOST_WIDE_INT) GET_MODE_MASK (mode) >> 1) - && ! side_effects_p (op0)) - return op1; - else if (rtx_equal_p (op0, op1) && ! side_effects_p (op0)) - return op0; - break; - - case UMIN: - if (op1 == const0_rtx && ! side_effects_p (op0)) - return op1; - else if (rtx_equal_p (op0, op1) && ! side_effects_p (op0)) - return op0; - break; - - case UMAX: - if (op1 == constm1_rtx && ! side_effects_p (op0)) - return op1; - else if (rtx_equal_p (op0, op1) && ! side_effects_p (op0)) - return op0; - break; - - default: - abort (); - } - - return 0; - } - - /* Get the integer argument values in two forms: - zero-extended in ARG0, ARG1 and sign-extended in ARG0S, ARG1S. */ - - arg0 = INTVAL (op0); - arg1 = INTVAL (op1); - - if (width < HOST_BITS_PER_WIDE_INT) - { - arg0 &= ((HOST_WIDE_INT) 1 << width) - 1; - arg1 &= ((HOST_WIDE_INT) 1 << width) - 1; - - arg0s = arg0; - if (arg0s & ((HOST_WIDE_INT) 1 << (width - 1))) - arg0s |= ((HOST_WIDE_INT) (-1) << width); - - arg1s = arg1; - if (arg1s & ((HOST_WIDE_INT) 1 << (width - 1))) - arg1s |= ((HOST_WIDE_INT) (-1) << width); - } - else - { - arg0s = arg0; - arg1s = arg1; - } - - /* Compute the value of the arithmetic. */ - - switch (code) - { - case PLUS: - val = arg0s + arg1s; - break; - - case MINUS: - val = arg0s - arg1s; - break; - - case MULT: - val = arg0s * arg1s; - break; - - case DIV: - if (arg1s == 0) - return 0; - val = arg0s / arg1s; - break; - - case MOD: - if (arg1s == 0) - return 0; - val = arg0s % arg1s; - break; - - case UDIV: - if (arg1 == 0) - return 0; - val = (unsigned HOST_WIDE_INT) arg0 / arg1; - break; - - case UMOD: - if (arg1 == 0) - return 0; - val = (unsigned HOST_WIDE_INT) arg0 % arg1; - break; - - case AND: - val = arg0 & arg1; - break; - - case IOR: - val = arg0 | arg1; - break; - - case XOR: - val = arg0 ^ arg1; - break; - - case LSHIFTRT: - /* If shift count is undefined, don't fold it; let the machine do - what it wants. But truncate it if the machine will do that. */ - if (arg1 < 0) - return 0; - -#ifdef SHIFT_COUNT_TRUNCATED - if (SHIFT_COUNT_TRUNCATED) - arg1 %= width; -#endif - - val = ((unsigned HOST_WIDE_INT) arg0) >> arg1; - break; - - case ASHIFT: - if (arg1 < 0) - return 0; - -#ifdef SHIFT_COUNT_TRUNCATED - if (SHIFT_COUNT_TRUNCATED) - arg1 %= width; -#endif - - val = ((unsigned HOST_WIDE_INT) arg0) << arg1; - break; - - case ASHIFTRT: - if (arg1 < 0) - return 0; - -#ifdef SHIFT_COUNT_TRUNCATED - if (SHIFT_COUNT_TRUNCATED) - arg1 %= width; -#endif - - val = arg0s >> arg1; - - /* Bootstrap compiler may not have sign extended the right shift. - Manually extend the sign to insure bootstrap cc matches gcc. */ - if (arg0s < 0 && arg1 > 0) - val |= ((HOST_WIDE_INT) -1) << (HOST_BITS_PER_WIDE_INT - arg1); - - break; - - case ROTATERT: - if (arg1 < 0) - return 0; - - arg1 %= width; - val = ((((unsigned HOST_WIDE_INT) arg0) << (width - arg1)) - | (((unsigned HOST_WIDE_INT) arg0) >> arg1)); - break; - - case ROTATE: - if (arg1 < 0) - return 0; - - arg1 %= width; - val = ((((unsigned HOST_WIDE_INT) arg0) << arg1) - | (((unsigned HOST_WIDE_INT) arg0) >> (width - arg1))); - break; - - case COMPARE: - /* Do nothing here. */ - return 0; - - case SMIN: - val = arg0s <= arg1s ? arg0s : arg1s; - break; - - case UMIN: - val = ((unsigned HOST_WIDE_INT) arg0 - <= (unsigned HOST_WIDE_INT) arg1 ? arg0 : arg1); - break; - - case SMAX: - val = arg0s > arg1s ? arg0s : arg1s; - break; - - case UMAX: - val = ((unsigned HOST_WIDE_INT) arg0 - > (unsigned HOST_WIDE_INT) arg1 ? arg0 : arg1); - break; - - default: - abort (); - } - - /* Clear the bits that don't belong in our mode, unless they and our sign - bit are all one. So we get either a reasonable negative value or a - reasonable unsigned value for this mode. */ - if (width < HOST_BITS_PER_WIDE_INT - && ((val & ((HOST_WIDE_INT) (-1) << (width - 1))) - != ((HOST_WIDE_INT) (-1) << (width - 1)))) - val &= ((HOST_WIDE_INT) 1 << width) - 1; - - /* If this would be an entire word for the target, but is not for - the host, then sign-extend on the host so that the number will look - the same way on the host that it would on the target. - - For example, when building a 64 bit alpha hosted 32 bit sparc - targeted compiler, then we want the 32 bit unsigned value -1 to be - represented as a 64 bit value -1, and not as 0x00000000ffffffff. - The later confuses the sparc backend. */ - - if (BITS_PER_WORD < HOST_BITS_PER_WIDE_INT && BITS_PER_WORD == width - && (val & ((HOST_WIDE_INT) 1 << (width - 1)))) - val |= ((HOST_WIDE_INT) (-1) << width); - - return GEN_INT (val); -} - -/* Simplify a PLUS or MINUS, at least one of whose operands may be another - PLUS or MINUS. - - Rather than test for specific case, we do this by a brute-force method - and do all possible simplifications until no more changes occur. Then - we rebuild the operation. */ - -static rtx -simplify_plus_minus (code, mode, op0, op1) - enum rtx_code code; - enum machine_mode mode; - rtx op0, op1; -{ - rtx ops[8]; - int negs[8]; - rtx result, tem; - int n_ops = 2, input_ops = 2, input_consts = 0, n_consts = 0; - int first = 1, negate = 0, changed; - int i, j; - - bzero ((char *) ops, sizeof ops); - - /* Set up the two operands and then expand them until nothing has been - changed. If we run out of room in our array, give up; this should - almost never happen. */ - - ops[0] = op0, ops[1] = op1, negs[0] = 0, negs[1] = (code == MINUS); - - changed = 1; - while (changed) - { - changed = 0; - - for (i = 0; i < n_ops; i++) - switch (GET_CODE (ops[i])) - { - case PLUS: - case MINUS: - if (n_ops == 7) - return 0; - - ops[n_ops] = XEXP (ops[i], 1); - negs[n_ops++] = GET_CODE (ops[i]) == MINUS ? !negs[i] : negs[i]; - ops[i] = XEXP (ops[i], 0); - input_ops++; - changed = 1; - break; - - case NEG: - ops[i] = XEXP (ops[i], 0); - negs[i] = ! negs[i]; - changed = 1; - break; - - case CONST: - ops[i] = XEXP (ops[i], 0); - input_consts++; - changed = 1; - break; - - case NOT: - /* ~a -> (-a - 1) */ - if (n_ops != 7) - { - ops[n_ops] = constm1_rtx; - negs[n_ops++] = negs[i]; - ops[i] = XEXP (ops[i], 0); - negs[i] = ! negs[i]; - changed = 1; - } - break; - - case CONST_INT: - if (negs[i]) - ops[i] = GEN_INT (- INTVAL (ops[i])), negs[i] = 0, changed = 1; - break; - - default: - break; - } - } - - /* If we only have two operands, we can't do anything. */ - if (n_ops <= 2) - return 0; - - /* Now simplify each pair of operands until nothing changes. The first - time through just simplify constants against each other. */ - - changed = 1; - while (changed) - { - changed = first; - - for (i = 0; i < n_ops - 1; i++) - for (j = i + 1; j < n_ops; j++) - if (ops[i] != 0 && ops[j] != 0 - && (! first || (CONSTANT_P (ops[i]) && CONSTANT_P (ops[j])))) - { - rtx lhs = ops[i], rhs = ops[j]; - enum rtx_code ncode = PLUS; - - if (negs[i] && ! negs[j]) - lhs = ops[j], rhs = ops[i], ncode = MINUS; - else if (! negs[i] && negs[j]) - ncode = MINUS; - - tem = simplify_binary_operation (ncode, mode, lhs, rhs); - if (tem) - { - ops[i] = tem, ops[j] = 0; - negs[i] = negs[i] && negs[j]; - if (GET_CODE (tem) == NEG) - ops[i] = XEXP (tem, 0), negs[i] = ! negs[i]; - - if (GET_CODE (ops[i]) == CONST_INT && negs[i]) - ops[i] = GEN_INT (- INTVAL (ops[i])), negs[i] = 0; - changed = 1; - } - } - - first = 0; - } - - /* Pack all the operands to the lower-numbered entries and give up if - we didn't reduce the number of operands we had. Make sure we - count a CONST as two operands. If we have the same number of - operands, but have made more CONSTs than we had, this is also - an improvement, so accept it. */ - - for (i = 0, j = 0; j < n_ops; j++) - if (ops[j] != 0) - { - ops[i] = ops[j], negs[i++] = negs[j]; - if (GET_CODE (ops[j]) == CONST) - n_consts++; - } - - if (i + n_consts > input_ops - || (i + n_consts == input_ops && n_consts <= input_consts)) - return 0; - - n_ops = i; - - /* If we have a CONST_INT, put it last. */ - for (i = 0; i < n_ops - 1; i++) - if (GET_CODE (ops[i]) == CONST_INT) - { - tem = ops[n_ops - 1], ops[n_ops - 1] = ops[i] , ops[i] = tem; - j = negs[n_ops - 1], negs[n_ops - 1] = negs[i], negs[i] = j; - } - - /* Put a non-negated operand first. If there aren't any, make all - operands positive and negate the whole thing later. */ - for (i = 0; i < n_ops && negs[i]; i++) - ; - - if (i == n_ops) - { - for (i = 0; i < n_ops; i++) - negs[i] = 0; - negate = 1; - } - else if (i != 0) - { - tem = ops[0], ops[0] = ops[i], ops[i] = tem; - j = negs[0], negs[0] = negs[i], negs[i] = j; - } - - /* Now make the result by performing the requested operations. */ - result = ops[0]; - for (i = 1; i < n_ops; i++) - result = cse_gen_binary (negs[i] ? MINUS : PLUS, mode, result, ops[i]); - - return negate ? gen_rtx_NEG (mode, result) : result; -} - -/* Make a binary operation by properly ordering the operands and - seeing if the expression folds. */ - -static rtx -cse_gen_binary (code, mode, op0, op1) - enum rtx_code code; - enum machine_mode mode; - rtx op0, op1; -{ - rtx tem; - - /* Put complex operands first and constants second if commutative. */ - if (GET_RTX_CLASS (code) == 'c' - && ((CONSTANT_P (op0) && GET_CODE (op1) != CONST_INT) - || (GET_RTX_CLASS (GET_CODE (op0)) == 'o' - && GET_RTX_CLASS (GET_CODE (op1)) != 'o') - || (GET_CODE (op0) == SUBREG - && GET_RTX_CLASS (GET_CODE (SUBREG_REG (op0))) == 'o' - && GET_RTX_CLASS (GET_CODE (op1)) != 'o'))) - tem = op0, op0 = op1, op1 = tem; - - /* If this simplifies, do it. */ - tem = simplify_binary_operation (code, mode, op0, op1); - - if (tem) - return tem; - - /* Handle addition and subtraction of CONST_INT specially. Otherwise, - just form the operation. */ - - if (code == PLUS && GET_CODE (op1) == CONST_INT - && GET_MODE (op0) != VOIDmode) - return plus_constant (op0, INTVAL (op1)); - else if (code == MINUS && GET_CODE (op1) == CONST_INT - && GET_MODE (op0) != VOIDmode) - return plus_constant (op0, - INTVAL (op1)); - else - return gen_rtx_fmt_ee (code, mode, op0, op1); -} - -struct cfc_args -{ - /* Input */ - rtx op0, op1; - /* Output */ - int equal, op0lt, op1lt; -}; - -static void -check_fold_consts (data) - PTR data; -{ - struct cfc_args * args = (struct cfc_args *) data; - REAL_VALUE_TYPE d0, d1; - - REAL_VALUE_FROM_CONST_DOUBLE (d0, args->op0); - REAL_VALUE_FROM_CONST_DOUBLE (d1, args->op1); - args->equal = REAL_VALUES_EQUAL (d0, d1); - args->op0lt = REAL_VALUES_LESS (d0, d1); - args->op1lt = REAL_VALUES_LESS (d1, d0); -} - -/* Like simplify_binary_operation except used for relational operators. - MODE is the mode of the operands, not that of the result. If MODE - is VOIDmode, both operands must also be VOIDmode and we compare the - operands in "infinite precision". - - If no simplification is possible, this function returns zero. Otherwise, - it returns either const_true_rtx or const0_rtx. */ - -rtx -simplify_relational_operation (code, mode, op0, op1) - enum rtx_code code; - enum machine_mode mode; - rtx op0, op1; -{ - int equal, op0lt, op0ltu, op1lt, op1ltu; - rtx tem; - - /* If op0 is a compare, extract the comparison arguments from it. */ - if (GET_CODE (op0) == COMPARE && op1 == const0_rtx) - op1 = XEXP (op0, 1), op0 = XEXP (op0, 0); - - /* We can't simplify MODE_CC values since we don't know what the - actual comparison is. */ - if (GET_MODE_CLASS (GET_MODE (op0)) == MODE_CC -#ifdef HAVE_cc0 - || op0 == cc0_rtx -#endif - ) - return 0; - - /* For integer comparisons of A and B maybe we can simplify A - B and can - then simplify a comparison of that with zero. If A and B are both either - a register or a CONST_INT, this can't help; testing for these cases will - prevent infinite recursion here and speed things up. - - If CODE is an unsigned comparison, then we can never do this optimization, - because it gives an incorrect result if the subtraction wraps around zero. - ANSI C defines unsigned operations such that they never overflow, and - thus such cases can not be ignored. */ - - if (INTEGRAL_MODE_P (mode) && op1 != const0_rtx - && ! ((GET_CODE (op0) == REG || GET_CODE (op0) == CONST_INT) - && (GET_CODE (op1) == REG || GET_CODE (op1) == CONST_INT)) - && 0 != (tem = simplify_binary_operation (MINUS, mode, op0, op1)) - && code != GTU && code != GEU && code != LTU && code != LEU) - return simplify_relational_operation (signed_condition (code), - mode, tem, const0_rtx); - - /* For non-IEEE floating-point, if the two operands are equal, we know the - result. */ - if (rtx_equal_p (op0, op1) - && (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT - || ! FLOAT_MODE_P (GET_MODE (op0)) || flag_fast_math)) - equal = 1, op0lt = 0, op0ltu = 0, op1lt = 0, op1ltu = 0; - - /* If the operands are floating-point constants, see if we can fold - the result. */ -#if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC) - else if (GET_CODE (op0) == CONST_DOUBLE && GET_CODE (op1) == CONST_DOUBLE - && GET_MODE_CLASS (GET_MODE (op0)) == MODE_FLOAT) - { - struct cfc_args args; - - /* Setup input for check_fold_consts() */ - args.op0 = op0; - args.op1 = op1; - - if (do_float_handler(check_fold_consts, (PTR) &args) == 0) - /* We got an exception from check_fold_consts() */ - return 0; - - /* Receive output from check_fold_consts() */ - equal = args.equal; - op0lt = op0ltu = args.op0lt; - op1lt = op1ltu = args.op1lt; - } -#endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */ - - /* Otherwise, see if the operands are both integers. */ - else if ((GET_MODE_CLASS (mode) == MODE_INT || mode == VOIDmode) - && (GET_CODE (op0) == CONST_DOUBLE || GET_CODE (op0) == CONST_INT) - && (GET_CODE (op1) == CONST_DOUBLE || GET_CODE (op1) == CONST_INT)) - { - int width = GET_MODE_BITSIZE (mode); - HOST_WIDE_INT l0s, h0s, l1s, h1s; - unsigned HOST_WIDE_INT l0u, h0u, l1u, h1u; - - /* Get the two words comprising each integer constant. */ - if (GET_CODE (op0) == CONST_DOUBLE) - { - l0u = l0s = CONST_DOUBLE_LOW (op0); - h0u = h0s = CONST_DOUBLE_HIGH (op0); - } - else - { - l0u = l0s = INTVAL (op0); - h0u = h0s = l0s < 0 ? -1 : 0; - } - - if (GET_CODE (op1) == CONST_DOUBLE) - { - l1u = l1s = CONST_DOUBLE_LOW (op1); - h1u = h1s = CONST_DOUBLE_HIGH (op1); - } - else - { - l1u = l1s = INTVAL (op1); - h1u = h1s = l1s < 0 ? -1 : 0; - } - - /* If WIDTH is nonzero and smaller than HOST_BITS_PER_WIDE_INT, - we have to sign or zero-extend the values. */ - if (width != 0 && width <= HOST_BITS_PER_WIDE_INT) - h0u = h1u = 0, h0s = l0s < 0 ? -1 : 0, h1s = l1s < 0 ? -1 : 0; - - if (width != 0 && width < HOST_BITS_PER_WIDE_INT) - { - l0u &= ((HOST_WIDE_INT) 1 << width) - 1; - l1u &= ((HOST_WIDE_INT) 1 << width) - 1; - - if (l0s & ((HOST_WIDE_INT) 1 << (width - 1))) - l0s |= ((HOST_WIDE_INT) (-1) << width); - - if (l1s & ((HOST_WIDE_INT) 1 << (width - 1))) - l1s |= ((HOST_WIDE_INT) (-1) << width); - } - - equal = (h0u == h1u && l0u == l1u); - op0lt = (h0s < h1s || (h0s == h1s && l0s < l1s)); - op1lt = (h1s < h0s || (h1s == h0s && l1s < l0s)); - op0ltu = (h0u < h1u || (h0u == h1u && l0u < l1u)); - op1ltu = (h1u < h0u || (h1u == h0u && l1u < l0u)); - } - - /* Otherwise, there are some code-specific tests we can make. */ - else - { - switch (code) - { - case EQ: - /* References to the frame plus a constant or labels cannot - be zero, but a SYMBOL_REF can due to #pragma weak. */ - if (((NONZERO_BASE_PLUS_P (op0) && op1 == const0_rtx) - || GET_CODE (op0) == LABEL_REF) -#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM - /* On some machines, the ap reg can be 0 sometimes. */ - && op0 != arg_pointer_rtx -#endif - ) - return const0_rtx; - break; - - case NE: - if (((NONZERO_BASE_PLUS_P (op0) && op1 == const0_rtx) - || GET_CODE (op0) == LABEL_REF) -#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM - && op0 != arg_pointer_rtx -#endif - ) - return const_true_rtx; - break; - - case GEU: - /* Unsigned values are never negative. */ - if (op1 == const0_rtx) - return const_true_rtx; - break; - - case LTU: - if (op1 == const0_rtx) - return const0_rtx; - break; - - case LEU: - /* Unsigned values are never greater than the largest - unsigned value. */ - if (GET_CODE (op1) == CONST_INT - && INTVAL (op1) == GET_MODE_MASK (mode) - && INTEGRAL_MODE_P (mode)) - return const_true_rtx; - break; - - case GTU: - if (GET_CODE (op1) == CONST_INT - && INTVAL (op1) == GET_MODE_MASK (mode) - && INTEGRAL_MODE_P (mode)) - return const0_rtx; - break; - - default: - break; - } - - return 0; - } - - /* If we reach here, EQUAL, OP0LT, OP0LTU, OP1LT, and OP1LTU are set - as appropriate. */ - switch (code) - { - case EQ: - return equal ? const_true_rtx : const0_rtx; - case NE: - return ! equal ? const_true_rtx : const0_rtx; - case LT: - return op0lt ? const_true_rtx : const0_rtx; - case GT: - return op1lt ? const_true_rtx : const0_rtx; - case LTU: - return op0ltu ? const_true_rtx : const0_rtx; - case GTU: - return op1ltu ? const_true_rtx : const0_rtx; - case LE: - return equal || op0lt ? const_true_rtx : const0_rtx; - case GE: - return equal || op1lt ? const_true_rtx : const0_rtx; - case LEU: - return equal || op0ltu ? const_true_rtx : const0_rtx; - case GEU: - return equal || op1ltu ? const_true_rtx : const0_rtx; - default: - abort (); - } -} - -/* Simplify CODE, an operation with result mode MODE and three operands, - OP0, OP1, and OP2. OP0_MODE was the mode of OP0 before it became - a constant. Return 0 if no simplifications is possible. */ - -rtx -simplify_ternary_operation (code, mode, op0_mode, op0, op1, op2) - enum rtx_code code; - enum machine_mode mode, op0_mode; - rtx op0, op1, op2; -{ - int width = GET_MODE_BITSIZE (mode); - - /* VOIDmode means "infinite" precision. */ - if (width == 0) - width = HOST_BITS_PER_WIDE_INT; - - switch (code) - { - case SIGN_EXTRACT: - case ZERO_EXTRACT: - if (GET_CODE (op0) == CONST_INT - && GET_CODE (op1) == CONST_INT - && GET_CODE (op2) == CONST_INT - && INTVAL (op1) + INTVAL (op2) <= GET_MODE_BITSIZE (op0_mode) - && width <= HOST_BITS_PER_WIDE_INT) - { - /* Extracting a bit-field from a constant */ - HOST_WIDE_INT val = INTVAL (op0); - - if (BITS_BIG_ENDIAN) - val >>= (GET_MODE_BITSIZE (op0_mode) - - INTVAL (op2) - INTVAL (op1)); - else - val >>= INTVAL (op2); - - if (HOST_BITS_PER_WIDE_INT != INTVAL (op1)) - { - /* First zero-extend. */ - val &= ((HOST_WIDE_INT) 1 << INTVAL (op1)) - 1; - /* If desired, propagate sign bit. */ - if (code == SIGN_EXTRACT - && (val & ((HOST_WIDE_INT) 1 << (INTVAL (op1) - 1)))) - val |= ~ (((HOST_WIDE_INT) 1 << INTVAL (op1)) - 1); - } - - /* Clear the bits that don't belong in our mode, - unless they and our sign bit are all one. - So we get either a reasonable negative value or a reasonable - unsigned value for this mode. */ - if (width < HOST_BITS_PER_WIDE_INT - && ((val & ((HOST_WIDE_INT) (-1) << (width - 1))) - != ((HOST_WIDE_INT) (-1) << (width - 1)))) - val &= ((HOST_WIDE_INT) 1 << width) - 1; - - return GEN_INT (val); - } - break; - - case IF_THEN_ELSE: - if (GET_CODE (op0) == CONST_INT) - return op0 != const0_rtx ? op1 : op2; - - /* Convert a == b ? b : a to "a". */ - if (GET_CODE (op0) == NE && ! side_effects_p (op0) - && rtx_equal_p (XEXP (op0, 0), op1) - && rtx_equal_p (XEXP (op0, 1), op2)) - return op1; - else if (GET_CODE (op0) == EQ && ! side_effects_p (op0) - && rtx_equal_p (XEXP (op0, 1), op1) - && rtx_equal_p (XEXP (op0, 0), op2)) - return op2; - else if (GET_RTX_CLASS (GET_CODE (op0)) == '<' && ! side_effects_p (op0)) - { - rtx temp; - temp = simplify_relational_operation (GET_CODE (op0), op0_mode, - XEXP (op0, 0), XEXP (op0, 1)); - /* See if any simplifications were possible. */ - if (temp == const0_rtx) - return op2; - else if (temp == const1_rtx) - return op1; - } - break; - - default: - abort (); - } - - return 0; -} - -/* If X is a nontrivial arithmetic operation on an argument - for which a constant value can be determined, return - the result of operating on that value, as a constant. - Otherwise, return X, possibly with one or more operands - modified by recursive calls to this function. - - If X is a register whose contents are known, we do NOT - return those contents here. equiv_constant is called to - perform that task. - - INSN is the insn that we may be modifying. If it is 0, make a copy - of X before modifying it. */ - -static rtx -fold_rtx (x, insn) - rtx x; - rtx insn; -{ - register enum rtx_code code; - register enum machine_mode mode; - register char *fmt; - register int i; - rtx new = 0; - int copied = 0; - int must_swap = 0; - - /* Folded equivalents of first two operands of X. */ - rtx folded_arg0; - rtx folded_arg1; - - /* Constant equivalents of first three operands of X; - 0 when no such equivalent is known. */ - rtx const_arg0; - rtx const_arg1; - rtx const_arg2; - - /* The mode of the first operand of X. We need this for sign and zero - extends. */ - enum machine_mode mode_arg0; - - if (x == 0) - return x; - - mode = GET_MODE (x); - code = GET_CODE (x); - switch (code) - { - case CONST: - case CONST_INT: - case CONST_DOUBLE: - case SYMBOL_REF: - case LABEL_REF: - case REG: - /* No use simplifying an EXPR_LIST - since they are used only for lists of args - in a function call's REG_EQUAL note. */ - case EXPR_LIST: - /* Changing anything inside an ADDRESSOF is incorrect; we don't - want to (e.g.,) make (addressof (const_int 0)) just because - the location is known to be zero. */ - case ADDRESSOF: - return x; - -#ifdef HAVE_cc0 - case CC0: - return prev_insn_cc0; -#endif - - case PC: - /* If the next insn is a CODE_LABEL followed by a jump table, - PC's value is a LABEL_REF pointing to that label. That - lets us fold switch statements on the Vax. */ - if (insn && GET_CODE (insn) == JUMP_INSN) - { - rtx next = next_nonnote_insn (insn); - - if (next && GET_CODE (next) == CODE_LABEL - && NEXT_INSN (next) != 0 - && GET_CODE (NEXT_INSN (next)) == JUMP_INSN - && (GET_CODE (PATTERN (NEXT_INSN (next))) == ADDR_VEC - || GET_CODE (PATTERN (NEXT_INSN (next))) == ADDR_DIFF_VEC)) - return gen_rtx_LABEL_REF (Pmode, next); - } - break; - - case SUBREG: - /* See if we previously assigned a constant value to this SUBREG. */ - if ((new = lookup_as_function (x, CONST_INT)) != 0 - || (new = lookup_as_function (x, CONST_DOUBLE)) != 0) - return new; - - /* If this is a paradoxical SUBREG, we have no idea what value the - extra bits would have. However, if the operand is equivalent - to a SUBREG whose operand is the same as our mode, and all the - modes are within a word, we can just use the inner operand - because these SUBREGs just say how to treat the register. - - Similarly if we find an integer constant. */ - - if (GET_MODE_SIZE (mode) > GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))) - { - enum machine_mode imode = GET_MODE (SUBREG_REG (x)); - struct table_elt *elt; - - if (GET_MODE_SIZE (mode) <= UNITS_PER_WORD - && GET_MODE_SIZE (imode) <= UNITS_PER_WORD - && (elt = lookup (SUBREG_REG (x), HASH (SUBREG_REG (x), imode), - imode)) != 0) - for (elt = elt->first_same_value; - elt; elt = elt->next_same_value) - { - if (CONSTANT_P (elt->exp) - && GET_MODE (elt->exp) == VOIDmode) - return elt->exp; - - if (GET_CODE (elt->exp) == SUBREG - && GET_MODE (SUBREG_REG (elt->exp)) == mode - && exp_equiv_p (elt->exp, elt->exp, 1, 0)) - return copy_rtx (SUBREG_REG (elt->exp)); - } - - return x; - } - - /* Fold SUBREG_REG. If it changed, see if we can simplify the SUBREG. - We might be able to if the SUBREG is extracting a single word in an - integral mode or extracting the low part. */ - - folded_arg0 = fold_rtx (SUBREG_REG (x), insn); - const_arg0 = equiv_constant (folded_arg0); - if (const_arg0) - folded_arg0 = const_arg0; - - if (folded_arg0 != SUBREG_REG (x)) - { - new = 0; - - if (GET_MODE_CLASS (mode) == MODE_INT - && GET_MODE_SIZE (mode) == UNITS_PER_WORD - && GET_MODE (SUBREG_REG (x)) != VOIDmode) - new = operand_subword (folded_arg0, SUBREG_WORD (x), 0, - GET_MODE (SUBREG_REG (x))); - if (new == 0 && subreg_lowpart_p (x)) - new = gen_lowpart_if_possible (mode, folded_arg0); - if (new) - return new; - } - - /* If this is a narrowing SUBREG and our operand is a REG, see if - we can find an equivalence for REG that is an arithmetic operation - in a wider mode where both operands are paradoxical SUBREGs - from objects of our result mode. In that case, we couldn't report - an equivalent value for that operation, since we don't know what the - extra bits will be. But we can find an equivalence for this SUBREG - by folding that operation is the narrow mode. This allows us to - fold arithmetic in narrow modes when the machine only supports - word-sized arithmetic. - - Also look for a case where we have a SUBREG whose operand is the - same as our result. If both modes are smaller than a word, we - are simply interpreting a register in different modes and we - can use the inner value. */ - - if (GET_CODE (folded_arg0) == REG - && GET_MODE_SIZE (mode) < GET_MODE_SIZE (GET_MODE (folded_arg0)) - && subreg_lowpart_p (x)) - { - struct table_elt *elt; - - /* We can use HASH here since we know that canon_hash won't be - called. */ - elt = lookup (folded_arg0, - HASH (folded_arg0, GET_MODE (folded_arg0)), - GET_MODE (folded_arg0)); - - if (elt) - elt = elt->first_same_value; - - for (; elt; elt = elt->next_same_value) - { - enum rtx_code eltcode = GET_CODE (elt->exp); - - /* Just check for unary and binary operations. */ - if (GET_RTX_CLASS (GET_CODE (elt->exp)) == '1' - && GET_CODE (elt->exp) != SIGN_EXTEND - && GET_CODE (elt->exp) != ZERO_EXTEND - && GET_CODE (XEXP (elt->exp, 0)) == SUBREG - && GET_MODE (SUBREG_REG (XEXP (elt->exp, 0))) == mode) - { - rtx op0 = SUBREG_REG (XEXP (elt->exp, 0)); - - if (GET_CODE (op0) != REG && ! CONSTANT_P (op0)) - op0 = fold_rtx (op0, NULL_RTX); - - op0 = equiv_constant (op0); - if (op0) - new = simplify_unary_operation (GET_CODE (elt->exp), mode, - op0, mode); - } - else if ((GET_RTX_CLASS (GET_CODE (elt->exp)) == '2' - || GET_RTX_CLASS (GET_CODE (elt->exp)) == 'c') - && eltcode != DIV && eltcode != MOD - && eltcode != UDIV && eltcode != UMOD - && eltcode != ASHIFTRT && eltcode != LSHIFTRT - && eltcode != ROTATE && eltcode != ROTATERT - && ((GET_CODE (XEXP (elt->exp, 0)) == SUBREG - && (GET_MODE (SUBREG_REG (XEXP (elt->exp, 0))) - == mode)) - || CONSTANT_P (XEXP (elt->exp, 0))) - && ((GET_CODE (XEXP (elt->exp, 1)) == SUBREG - && (GET_MODE (SUBREG_REG (XEXP (elt->exp, 1))) - == mode)) - || CONSTANT_P (XEXP (elt->exp, 1)))) - { - rtx op0 = gen_lowpart_common (mode, XEXP (elt->exp, 0)); - rtx op1 = gen_lowpart_common (mode, XEXP (elt->exp, 1)); - - if (op0 && GET_CODE (op0) != REG && ! CONSTANT_P (op0)) - op0 = fold_rtx (op0, NULL_RTX); - - if (op0) - op0 = equiv_constant (op0); - - if (op1 && GET_CODE (op1) != REG && ! CONSTANT_P (op1)) - op1 = fold_rtx (op1, NULL_RTX); - - if (op1) - op1 = equiv_constant (op1); - - /* If we are looking for the low SImode part of - (ashift:DI c (const_int 32)), it doesn't work - to compute that in SImode, because a 32-bit shift - in SImode is unpredictable. We know the value is 0. */ - if (op0 && op1 - && GET_CODE (elt->exp) == ASHIFT - && GET_CODE (op1) == CONST_INT - && INTVAL (op1) >= GET_MODE_BITSIZE (mode)) - { - if (INTVAL (op1) < GET_MODE_BITSIZE (GET_MODE (elt->exp))) - - /* If the count fits in the inner mode's width, - but exceeds the outer mode's width, - the value will get truncated to 0 - by the subreg. */ - new = const0_rtx; - else - /* If the count exceeds even the inner mode's width, - don't fold this expression. */ - new = 0; - } - else if (op0 && op1) - new = simplify_binary_operation (GET_CODE (elt->exp), mode, - op0, op1); - } - - else if (GET_CODE (elt->exp) == SUBREG - && GET_MODE (SUBREG_REG (elt->exp)) == mode - && (GET_MODE_SIZE (GET_MODE (folded_arg0)) - <= UNITS_PER_WORD) - && exp_equiv_p (elt->exp, elt->exp, 1, 0)) - new = copy_rtx (SUBREG_REG (elt->exp)); - - if (new) - return new; - } - } - - return x; - - case NOT: - case NEG: - /* If we have (NOT Y), see if Y is known to be (NOT Z). - If so, (NOT Y) simplifies to Z. Similarly for NEG. */ - new = lookup_as_function (XEXP (x, 0), code); - if (new) - return fold_rtx (copy_rtx (XEXP (new, 0)), insn); - break; - - case MEM: - /* If we are not actually processing an insn, don't try to find the - best address. Not only don't we care, but we could modify the - MEM in an invalid way since we have no insn to validate against. */ - if (insn != 0) - find_best_addr (insn, &XEXP (x, 0)); - - { - /* Even if we don't fold in the insn itself, - we can safely do so here, in hopes of getting a constant. */ - rtx addr = fold_rtx (XEXP (x, 0), NULL_RTX); - rtx base = 0; - HOST_WIDE_INT offset = 0; - - if (GET_CODE (addr) == REG - && REGNO_QTY_VALID_P (REGNO (addr)) - && GET_MODE (addr) == qty_mode[REG_QTY (REGNO (addr))] - && qty_const[REG_QTY (REGNO (addr))] != 0) - addr = qty_const[REG_QTY (REGNO (addr))]; - - /* If address is constant, split it into a base and integer offset. */ - if (GET_CODE (addr) == SYMBOL_REF || GET_CODE (addr) == LABEL_REF) - base = addr; - else if (GET_CODE (addr) == CONST && GET_CODE (XEXP (addr, 0)) == PLUS - && GET_CODE (XEXP (XEXP (addr, 0), 1)) == CONST_INT) - { - base = XEXP (XEXP (addr, 0), 0); - offset = INTVAL (XEXP (XEXP (addr, 0), 1)); - } - else if (GET_CODE (addr) == LO_SUM - && GET_CODE (XEXP (addr, 1)) == SYMBOL_REF) - base = XEXP (addr, 1); - else if (GET_CODE (addr) == ADDRESSOF) - return change_address (x, VOIDmode, addr); - - /* If this is a constant pool reference, we can fold it into its - constant to allow better value tracking. */ - if (base && GET_CODE (base) == SYMBOL_REF - && CONSTANT_POOL_ADDRESS_P (base)) - { - rtx constant = get_pool_constant (base); - enum machine_mode const_mode = get_pool_mode (base); - rtx new; - - if (CONSTANT_P (constant) && GET_CODE (constant) != CONST_INT) - constant_pool_entries_cost = COST (constant); - - /* If we are loading the full constant, we have an equivalence. */ - if (offset == 0 && mode == const_mode) - return constant; - - /* If this actually isn't a constant (weird!), we can't do - anything. Otherwise, handle the two most common cases: - extracting a word from a multi-word constant, and extracting - the low-order bits. Other cases don't seem common enough to - worry about. */ - if (! CONSTANT_P (constant)) - return x; - - if (GET_MODE_CLASS (mode) == MODE_INT - && GET_MODE_SIZE (mode) == UNITS_PER_WORD - && offset % UNITS_PER_WORD == 0 - && (new = operand_subword (constant, - offset / UNITS_PER_WORD, - 0, const_mode)) != 0) - return new; - - if (((BYTES_BIG_ENDIAN - && offset == GET_MODE_SIZE (GET_MODE (constant)) - 1) - || (! BYTES_BIG_ENDIAN && offset == 0)) - && (new = gen_lowpart_if_possible (mode, constant)) != 0) - return new; - } - - /* If this is a reference to a label at a known position in a jump - table, we also know its value. */ - if (base && GET_CODE (base) == LABEL_REF) - { - rtx label = XEXP (base, 0); - rtx table_insn = NEXT_INSN (label); - - if (table_insn && GET_CODE (table_insn) == JUMP_INSN - && GET_CODE (PATTERN (table_insn)) == ADDR_VEC) - { - rtx table = PATTERN (table_insn); - - if (offset >= 0 - && (offset / GET_MODE_SIZE (GET_MODE (table)) - < XVECLEN (table, 0))) - return XVECEXP (table, 0, - offset / GET_MODE_SIZE (GET_MODE (table))); - } - if (table_insn && GET_CODE (table_insn) == JUMP_INSN - && GET_CODE (PATTERN (table_insn)) == ADDR_DIFF_VEC) - { - rtx table = PATTERN (table_insn); - - if (offset >= 0 - && (offset / GET_MODE_SIZE (GET_MODE (table)) - < XVECLEN (table, 1))) - { - offset /= GET_MODE_SIZE (GET_MODE (table)); - new = gen_rtx_MINUS (Pmode, XVECEXP (table, 1, offset), - XEXP (table, 0)); - - if (GET_MODE (table) != Pmode) - new = gen_rtx_TRUNCATE (GET_MODE (table), new); - - /* Indicate this is a constant. This isn't a - valid form of CONST, but it will only be used - to fold the next insns and then discarded, so - it should be safe. - - Note this expression must be explicitly discarded, - by cse_insn, else it may end up in a REG_EQUAL note - and "escape" to cause problems elsewhere. */ - return gen_rtx_CONST (GET_MODE (new), new); - } - } - } - - return x; - } - - case ASM_OPERANDS: - for (i = XVECLEN (x, 3) - 1; i >= 0; i--) - validate_change (insn, &XVECEXP (x, 3, i), - fold_rtx (XVECEXP (x, 3, i), insn), 0); - break; - - default: - break; - } - - const_arg0 = 0; - const_arg1 = 0; - const_arg2 = 0; - mode_arg0 = VOIDmode; - - /* Try folding our operands. - Then see which ones have constant values known. */ - - fmt = GET_RTX_FORMAT (code); - for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) - if (fmt[i] == 'e') - { - rtx arg = XEXP (x, i); - rtx folded_arg = arg, const_arg = 0; - enum machine_mode mode_arg = GET_MODE (arg); - rtx cheap_arg, expensive_arg; - rtx replacements[2]; - int j; - - /* Most arguments are cheap, so handle them specially. */ - switch (GET_CODE (arg)) - { - case REG: - /* This is the same as calling equiv_constant; it is duplicated - here for speed. */ - if (REGNO_QTY_VALID_P (REGNO (arg)) - && qty_const[REG_QTY (REGNO (arg))] != 0 - && GET_CODE (qty_const[REG_QTY (REGNO (arg))]) != REG - && GET_CODE (qty_const[REG_QTY (REGNO (arg))]) != PLUS) - const_arg - = gen_lowpart_if_possible (GET_MODE (arg), - qty_const[REG_QTY (REGNO (arg))]); - break; - - case CONST: - case CONST_INT: - case SYMBOL_REF: - case LABEL_REF: - case CONST_DOUBLE: - const_arg = arg; - break; - -#ifdef HAVE_cc0 - case CC0: - folded_arg = prev_insn_cc0; - mode_arg = prev_insn_cc0_mode; - const_arg = equiv_constant (folded_arg); - break; -#endif - - default: - folded_arg = fold_rtx (arg, insn); - const_arg = equiv_constant (folded_arg); - } - - /* For the first three operands, see if the operand - is constant or equivalent to a constant. */ - switch (i) - { - case 0: - folded_arg0 = folded_arg; - const_arg0 = const_arg; - mode_arg0 = mode_arg; - break; - case 1: - folded_arg1 = folded_arg; - const_arg1 = const_arg; - break; - case 2: - const_arg2 = const_arg; - break; - } - - /* Pick the least expensive of the folded argument and an - equivalent constant argument. */ - if (const_arg == 0 || const_arg == folded_arg - || COST (const_arg) > COST (folded_arg)) - cheap_arg = folded_arg, expensive_arg = const_arg; - else - cheap_arg = const_arg, expensive_arg = folded_arg; - - /* Try to replace the operand with the cheapest of the two - possibilities. If it doesn't work and this is either of the first - two operands of a commutative operation, try swapping them. - If THAT fails, try the more expensive, provided it is cheaper - than what is already there. */ - - if (cheap_arg == XEXP (x, i)) - continue; - - if (insn == 0 && ! copied) - { - x = copy_rtx (x); - copied = 1; - } - - replacements[0] = cheap_arg, replacements[1] = expensive_arg; - for (j = 0; - j < 2 && replacements[j] - && COST (replacements[j]) < COST (XEXP (x, i)); - j++) - { - if (validate_change (insn, &XEXP (x, i), replacements[j], 0)) - break; - - if (code == NE || code == EQ || GET_RTX_CLASS (code) == 'c') - { - validate_change (insn, &XEXP (x, i), XEXP (x, 1 - i), 1); - validate_change (insn, &XEXP (x, 1 - i), replacements[j], 1); - - if (apply_change_group ()) - { - /* Swap them back to be invalid so that this loop can - continue and flag them to be swapped back later. */ - rtx tem; - - tem = XEXP (x, 0); XEXP (x, 0) = XEXP (x, 1); - XEXP (x, 1) = tem; - must_swap = 1; - break; - } - } - } - } - - else - { - if (fmt[i] == 'E') - /* Don't try to fold inside of a vector of expressions. - Doing nothing is harmless. */ - {;} - } - - /* If a commutative operation, place a constant integer as the second - operand unless the first operand is also a constant integer. Otherwise, - place any constant second unless the first operand is also a constant. */ - - if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c') - { - if (must_swap || (const_arg0 - && (const_arg1 == 0 - || (GET_CODE (const_arg0) == CONST_INT - && GET_CODE (const_arg1) != CONST_INT)))) - { - register rtx tem = XEXP (x, 0); - - if (insn == 0 && ! copied) - { - x = copy_rtx (x); - copied = 1; - } - - validate_change (insn, &XEXP (x, 0), XEXP (x, 1), 1); - validate_change (insn, &XEXP (x, 1), tem, 1); - if (apply_change_group ()) - { - tem = const_arg0, const_arg0 = const_arg1, const_arg1 = tem; - tem = folded_arg0, folded_arg0 = folded_arg1, folded_arg1 = tem; - } - } - } - - /* If X is an arithmetic operation, see if we can simplify it. */ - - switch (GET_RTX_CLASS (code)) - { - case '1': - { - int is_const = 0; - - /* We can't simplify extension ops unless we know the - original mode. */ - if ((code == ZERO_EXTEND || code == SIGN_EXTEND) - && mode_arg0 == VOIDmode) - break; - - /* If we had a CONST, strip it off and put it back later if we - fold. */ - if (const_arg0 != 0 && GET_CODE (const_arg0) == CONST) - is_const = 1, const_arg0 = XEXP (const_arg0, 0); - - new = simplify_unary_operation (code, mode, - const_arg0 ? const_arg0 : folded_arg0, - mode_arg0); - if (new != 0 && is_const) - new = gen_rtx_CONST (mode, new); - } - break; - - case '<': - /* See what items are actually being compared and set FOLDED_ARG[01] - to those values and CODE to the actual comparison code. If any are - constant, set CONST_ARG0 and CONST_ARG1 appropriately. We needn't - do anything if both operands are already known to be constant. */ - - if (const_arg0 == 0 || const_arg1 == 0) - { - struct table_elt *p0, *p1; - rtx true = const_true_rtx, false = const0_rtx; - enum machine_mode mode_arg1; - -#ifdef FLOAT_STORE_FLAG_VALUE - if (GET_MODE_CLASS (mode) == MODE_FLOAT) - { - true = CONST_DOUBLE_FROM_REAL_VALUE (FLOAT_STORE_FLAG_VALUE, - mode); - false = CONST0_RTX (mode); - } -#endif - - code = find_comparison_args (code, &folded_arg0, &folded_arg1, - &mode_arg0, &mode_arg1); - const_arg0 = equiv_constant (folded_arg0); - const_arg1 = equiv_constant (folded_arg1); - - /* If the mode is VOIDmode or a MODE_CC mode, we don't know - what kinds of things are being compared, so we can't do - anything with this comparison. */ - - if (mode_arg0 == VOIDmode || GET_MODE_CLASS (mode_arg0) == MODE_CC) - break; - - /* If we do not now have two constants being compared, see - if we can nevertheless deduce some things about the - comparison. */ - if (const_arg0 == 0 || const_arg1 == 0) - { - /* Is FOLDED_ARG0 frame-pointer plus a constant? Or - non-explicit constant? These aren't zero, but we - don't know their sign. */ - if (const_arg1 == const0_rtx - && (NONZERO_BASE_PLUS_P (folded_arg0) -#if 0 /* Sad to say, on sysvr4, #pragma weak can make a symbol address - come out as 0. */ - || GET_CODE (folded_arg0) == SYMBOL_REF -#endif - || GET_CODE (folded_arg0) == LABEL_REF - || GET_CODE (folded_arg0) == CONST)) - { - if (code == EQ) - return false; - else if (code == NE) - return true; - } - - /* See if the two operands are the same. We don't do this - for IEEE floating-point since we can't assume x == x - since x might be a NaN. */ - - if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT - || ! FLOAT_MODE_P (mode_arg0) || flag_fast_math) - && (folded_arg0 == folded_arg1 - || (GET_CODE (folded_arg0) == REG - && GET_CODE (folded_arg1) == REG - && (REG_QTY (REGNO (folded_arg0)) - == REG_QTY (REGNO (folded_arg1)))) - || ((p0 = lookup (folded_arg0, - (safe_hash (folded_arg0, mode_arg0) - % NBUCKETS), mode_arg0)) - && (p1 = lookup (folded_arg1, - (safe_hash (folded_arg1, mode_arg0) - % NBUCKETS), mode_arg0)) - && p0->first_same_value == p1->first_same_value))) - return ((code == EQ || code == LE || code == GE - || code == LEU || code == GEU) - ? true : false); - - /* If FOLDED_ARG0 is a register, see if the comparison we are - doing now is either the same as we did before or the reverse - (we only check the reverse if not floating-point). */ - else if (GET_CODE (folded_arg0) == REG) - { - int qty = REG_QTY (REGNO (folded_arg0)); - - if (REGNO_QTY_VALID_P (REGNO (folded_arg0)) - && (comparison_dominates_p (qty_comparison_code[qty], code) - || (comparison_dominates_p (qty_comparison_code[qty], - reverse_condition (code)) - && ! FLOAT_MODE_P (mode_arg0))) - && (rtx_equal_p (qty_comparison_const[qty], folded_arg1) - || (const_arg1 - && rtx_equal_p (qty_comparison_const[qty], - const_arg1)) - || (GET_CODE (folded_arg1) == REG - && (REG_QTY (REGNO (folded_arg1)) - == qty_comparison_qty[qty])))) - return (comparison_dominates_p (qty_comparison_code[qty], - code) - ? true : false); - } - } - } - - /* If we are comparing against zero, see if the first operand is - equivalent to an IOR with a constant. If so, we may be able to - determine the result of this comparison. */ - - if (const_arg1 == const0_rtx) - { - rtx y = lookup_as_function (folded_arg0, IOR); - rtx inner_const; - - if (y != 0 - && (inner_const = equiv_constant (XEXP (y, 1))) != 0 - && GET_CODE (inner_const) == CONST_INT - && INTVAL (inner_const) != 0) - { - int sign_bitnum = GET_MODE_BITSIZE (mode_arg0) - 1; - int has_sign = (HOST_BITS_PER_WIDE_INT >= sign_bitnum - && (INTVAL (inner_const) - & ((HOST_WIDE_INT) 1 << sign_bitnum))); - rtx true = const_true_rtx, false = const0_rtx; - -#ifdef FLOAT_STORE_FLAG_VALUE - if (GET_MODE_CLASS (mode) == MODE_FLOAT) - { - true = CONST_DOUBLE_FROM_REAL_VALUE (FLOAT_STORE_FLAG_VALUE, - mode); - false = CONST0_RTX (mode); - } -#endif - - switch (code) - { - case EQ: - return false; - case NE: - return true; - case LT: case LE: - if (has_sign) - return true; - break; - case GT: case GE: - if (has_sign) - return false; - break; - default: - break; - } - } - } - - new = simplify_relational_operation (code, mode_arg0, - const_arg0 ? const_arg0 : folded_arg0, - const_arg1 ? const_arg1 : folded_arg1); -#ifdef FLOAT_STORE_FLAG_VALUE - if (new != 0 && GET_MODE_CLASS (mode) == MODE_FLOAT) - new = ((new == const0_rtx) ? CONST0_RTX (mode) - : CONST_DOUBLE_FROM_REAL_VALUE (FLOAT_STORE_FLAG_VALUE, mode)); -#endif - break; - - case '2': - case 'c': - switch (code) - { - case PLUS: - /* If the second operand is a LABEL_REF, see if the first is a MINUS - with that LABEL_REF as its second operand. If so, the result is - the first operand of that MINUS. This handles switches with an - ADDR_DIFF_VEC table. */ - if (const_arg1 && GET_CODE (const_arg1) == LABEL_REF) - { - rtx y - = GET_CODE (folded_arg0) == MINUS ? folded_arg0 - : lookup_as_function (folded_arg0, MINUS); - - if (y != 0 && GET_CODE (XEXP (y, 1)) == LABEL_REF - && XEXP (XEXP (y, 1), 0) == XEXP (const_arg1, 0)) - return XEXP (y, 0); - - /* Now try for a CONST of a MINUS like the above. */ - if ((y = (GET_CODE (folded_arg0) == CONST ? folded_arg0 - : lookup_as_function (folded_arg0, CONST))) != 0 - && GET_CODE (XEXP (y, 0)) == MINUS - && GET_CODE (XEXP (XEXP (y, 0), 1)) == LABEL_REF - && XEXP (XEXP (XEXP (y, 0),1), 0) == XEXP (const_arg1, 0)) - return XEXP (XEXP (y, 0), 0); - } - - /* Likewise if the operands are in the other order. */ - if (const_arg0 && GET_CODE (const_arg0) == LABEL_REF) - { - rtx y - = GET_CODE (folded_arg1) == MINUS ? folded_arg1 - : lookup_as_function (folded_arg1, MINUS); - - if (y != 0 && GET_CODE (XEXP (y, 1)) == LABEL_REF - && XEXP (XEXP (y, 1), 0) == XEXP (const_arg0, 0)) - return XEXP (y, 0); - - /* Now try for a CONST of a MINUS like the above. */ - if ((y = (GET_CODE (folded_arg1) == CONST ? folded_arg1 - : lookup_as_function (folded_arg1, CONST))) != 0 - && GET_CODE (XEXP (y, 0)) == MINUS - && GET_CODE (XEXP (XEXP (y, 0), 1)) == LABEL_REF - && XEXP (XEXP (XEXP (y, 0),1), 0) == XEXP (const_arg0, 0)) - return XEXP (XEXP (y, 0), 0); - } - - /* If second operand is a register equivalent to a negative - CONST_INT, see if we can find a register equivalent to the - positive constant. Make a MINUS if so. Don't do this for - a non-negative constant since we might then alternate between - chosing positive and negative constants. Having the positive - constant previously-used is the more common case. Be sure - the resulting constant is non-negative; if const_arg1 were - the smallest negative number this would overflow: depending - on the mode, this would either just be the same value (and - hence not save anything) or be incorrect. */ - if (const_arg1 != 0 && GET_CODE (const_arg1) == CONST_INT - && INTVAL (const_arg1) < 0 - /* This used to test - - - INTVAL (const_arg1) >= 0 - - But The Sun V5.0 compilers mis-compiled that test. So - instead we test for the problematic value in a more direct - manner and hope the Sun compilers get it correct. */ - && INTVAL (const_arg1) != - ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1)) - && GET_CODE (folded_arg1) == REG) - { - rtx new_const = GEN_INT (- INTVAL (const_arg1)); - struct table_elt *p - = lookup (new_const, safe_hash (new_const, mode) % NBUCKETS, - mode); - - if (p) - for (p = p->first_same_value; p; p = p->next_same_value) - if (GET_CODE (p->exp) == REG) - return cse_gen_binary (MINUS, mode, folded_arg0, - canon_reg (p->exp, NULL_RTX)); - } - goto from_plus; - - case MINUS: - /* If we have (MINUS Y C), see if Y is known to be (PLUS Z C2). - If so, produce (PLUS Z C2-C). */ - if (const_arg1 != 0 && GET_CODE (const_arg1) == CONST_INT) - { - rtx y = lookup_as_function (XEXP (x, 0), PLUS); - if (y && GET_CODE (XEXP (y, 1)) == CONST_INT) - return fold_rtx (plus_constant (copy_rtx (y), - -INTVAL (const_arg1)), - NULL_RTX); - } - - /* ... fall through ... */ - - from_plus: - case SMIN: case SMAX: case UMIN: case UMAX: - case IOR: case AND: case XOR: - case MULT: case DIV: case UDIV: - case ASHIFT: case LSHIFTRT: case ASHIFTRT: - /* If we have (<op> <reg> <const_int>) for an associative OP and REG - is known to be of similar form, we may be able to replace the - operation with a combined operation. This may eliminate the - intermediate operation if every use is simplified in this way. - Note that the similar optimization done by combine.c only works - if the intermediate operation's result has only one reference. */ - - if (GET_CODE (folded_arg0) == REG - && const_arg1 && GET_CODE (const_arg1) == CONST_INT) - { - int is_shift - = (code == ASHIFT || code == ASHIFTRT || code == LSHIFTRT); - rtx y = lookup_as_function (folded_arg0, code); - rtx inner_const; - enum rtx_code associate_code; - rtx new_const; - - if (y == 0 - || 0 == (inner_const - = equiv_constant (fold_rtx (XEXP (y, 1), 0))) - || GET_CODE (inner_const) != CONST_INT - /* If we have compiled a statement like - "if (x == (x & mask1))", and now are looking at - "x & mask2", we will have a case where the first operand - of Y is the same as our first operand. Unless we detect - this case, an infinite loop will result. */ - || XEXP (y, 0) == folded_arg0) - break; - - /* Don't associate these operations if they are a PLUS with the - same constant and it is a power of two. These might be doable - with a pre- or post-increment. Similarly for two subtracts of - identical powers of two with post decrement. */ - - if (code == PLUS && INTVAL (const_arg1) == INTVAL (inner_const) - && ((HAVE_PRE_INCREMENT - && exact_log2 (INTVAL (const_arg1)) >= 0) - || (HAVE_POST_INCREMENT - && exact_log2 (INTVAL (const_arg1)) >= 0) - || (HAVE_PRE_DECREMENT - && exact_log2 (- INTVAL (const_arg1)) >= 0) - || (HAVE_POST_DECREMENT - && exact_log2 (- INTVAL (const_arg1)) >= 0))) - break; - - /* Compute the code used to compose the constants. For example, - A/C1/C2 is A/(C1 * C2), so if CODE == DIV, we want MULT. */ - - associate_code - = (code == MULT || code == DIV || code == UDIV ? MULT - : is_shift || code == PLUS || code == MINUS ? PLUS : code); - - new_const = simplify_binary_operation (associate_code, mode, - const_arg1, inner_const); - - if (new_const == 0) - break; - - /* If we are associating shift operations, don't let this - produce a shift of the size of the object or larger. - This could occur when we follow a sign-extend by a right - shift on a machine that does a sign-extend as a pair - of shifts. */ - - if (is_shift && GET_CODE (new_const) == CONST_INT - && INTVAL (new_const) >= GET_MODE_BITSIZE (mode)) - { - /* As an exception, we can turn an ASHIFTRT of this - form into a shift of the number of bits - 1. */ - if (code == ASHIFTRT) - new_const = GEN_INT (GET_MODE_BITSIZE (mode) - 1); - else - break; - } - - y = copy_rtx (XEXP (y, 0)); - - /* If Y contains our first operand (the most common way this - can happen is if Y is a MEM), we would do into an infinite - loop if we tried to fold it. So don't in that case. */ - - if (! reg_mentioned_p (folded_arg0, y)) - y = fold_rtx (y, insn); - - return cse_gen_binary (code, mode, y, new_const); - } - break; - - default: - break; - } - - new = simplify_binary_operation (code, mode, - const_arg0 ? const_arg0 : folded_arg0, - const_arg1 ? const_arg1 : folded_arg1); - break; - - case 'o': - /* (lo_sum (high X) X) is simply X. */ - if (code == LO_SUM && const_arg0 != 0 - && GET_CODE (const_arg0) == HIGH - && rtx_equal_p (XEXP (const_arg0, 0), const_arg1)) - return const_arg1; - break; - - case '3': - case 'b': - new = simplify_ternary_operation (code, mode, mode_arg0, - const_arg0 ? const_arg0 : folded_arg0, - const_arg1 ? const_arg1 : folded_arg1, - const_arg2 ? const_arg2 : XEXP (x, 2)); - break; - - case 'x': - /* Always eliminate CONSTANT_P_RTX at this stage. */ - if (code == CONSTANT_P_RTX) - return (const_arg0 ? const1_rtx : const0_rtx); - break; - } - - return new ? new : x; -} - -/* Return a constant value currently equivalent to X. - Return 0 if we don't know one. */ - -static rtx -equiv_constant (x) - rtx x; -{ - if (GET_CODE (x) == REG - && REGNO_QTY_VALID_P (REGNO (x)) - && qty_const[REG_QTY (REGNO (x))]) - x = gen_lowpart_if_possible (GET_MODE (x), qty_const[REG_QTY (REGNO (x))]); - - if (x == 0 || CONSTANT_P (x)) - return x; - - /* If X is a MEM, try to fold it outside the context of any insn to see if - it might be equivalent to a constant. That handles the case where it - is a constant-pool reference. Then try to look it up in the hash table - in case it is something whose value we have seen before. */ - - if (GET_CODE (x) == MEM) - { - struct table_elt *elt; - - x = fold_rtx (x, NULL_RTX); - if (CONSTANT_P (x)) - return x; - - elt = lookup (x, safe_hash (x, GET_MODE (x)) % NBUCKETS, GET_MODE (x)); - if (elt == 0) - return 0; - - for (elt = elt->first_same_value; elt; elt = elt->next_same_value) - if (elt->is_const && CONSTANT_P (elt->exp)) - return elt->exp; - } - - return 0; -} - -/* Assuming that X is an rtx (e.g., MEM, REG or SUBREG) for a fixed-point - number, return an rtx (MEM, SUBREG, or CONST_INT) that refers to the - least-significant part of X. - MODE specifies how big a part of X to return. - - If the requested operation cannot be done, 0 is returned. - - This is similar to gen_lowpart in emit-rtl.c. */ - -rtx -gen_lowpart_if_possible (mode, x) - enum machine_mode mode; - register rtx x; -{ - rtx result = gen_lowpart_common (mode, x); - - if (result) - return result; - else if (GET_CODE (x) == MEM) - { - /* This is the only other case we handle. */ - register int offset = 0; - rtx new; - - if (WORDS_BIG_ENDIAN) - offset = (MAX (GET_MODE_SIZE (GET_MODE (x)), UNITS_PER_WORD) - - MAX (GET_MODE_SIZE (mode), UNITS_PER_WORD)); - if (BYTES_BIG_ENDIAN) - /* Adjust the address so that the address-after-the-data is - unchanged. */ - offset -= (MIN (UNITS_PER_WORD, GET_MODE_SIZE (mode)) - - MIN (UNITS_PER_WORD, GET_MODE_SIZE (GET_MODE (x)))); - new = gen_rtx_MEM (mode, plus_constant (XEXP (x, 0), offset)); - if (! memory_address_p (mode, XEXP (new, 0))) - return 0; - RTX_UNCHANGING_P (new) = RTX_UNCHANGING_P (x); - MEM_COPY_ATTRIBUTES (new, x); - return new; - } - else - return 0; -} - -/* Given INSN, a jump insn, TAKEN indicates if we are following the "taken" - branch. It will be zero if not. - - In certain cases, this can cause us to add an equivalence. For example, - if we are following the taken case of - if (i == 2) - we can add the fact that `i' and '2' are now equivalent. - - In any case, we can record that this comparison was passed. If the same - comparison is seen later, we will know its value. */ - -static void -record_jump_equiv (insn, taken) - rtx insn; - int taken; -{ - int cond_known_true; - rtx op0, op1; - enum machine_mode mode, mode0, mode1; - int reversed_nonequality = 0; - enum rtx_code code; - - /* Ensure this is the right kind of insn. */ - if (! condjump_p (insn) || simplejump_p (insn)) - return; - - /* See if this jump condition is known true or false. */ - if (taken) - cond_known_true = (XEXP (SET_SRC (PATTERN (insn)), 2) == pc_rtx); - else - cond_known_true = (XEXP (SET_SRC (PATTERN (insn)), 1) == pc_rtx); - - /* Get the type of comparison being done and the operands being compared. - If we had to reverse a non-equality condition, record that fact so we - know that it isn't valid for floating-point. */ - code = GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 0)); - op0 = fold_rtx (XEXP (XEXP (SET_SRC (PATTERN (insn)), 0), 0), insn); - op1 = fold_rtx (XEXP (XEXP (SET_SRC (PATTERN (insn)), 0), 1), insn); - - code = find_comparison_args (code, &op0, &op1, &mode0, &mode1); - if (! cond_known_true) - { - reversed_nonequality = (code != EQ && code != NE); - code = reverse_condition (code); - } - - /* The mode is the mode of the non-constant. */ - mode = mode0; - if (mode1 != VOIDmode) - mode = mode1; - - record_jump_cond (code, mode, op0, op1, reversed_nonequality); -} - -/* We know that comparison CODE applied to OP0 and OP1 in MODE is true. - REVERSED_NONEQUALITY is nonzero if CODE had to be swapped. - Make any useful entries we can with that information. Called from - above function and called recursively. */ - -static void -record_jump_cond (code, mode, op0, op1, reversed_nonequality) - enum rtx_code code; - enum machine_mode mode; - rtx op0, op1; - int reversed_nonequality; -{ - unsigned op0_hash, op1_hash; - int op0_in_memory, op0_in_struct, op1_in_memory, op1_in_struct; - struct table_elt *op0_elt, *op1_elt; - - /* If OP0 and OP1 are known equal, and either is a paradoxical SUBREG, - we know that they are also equal in the smaller mode (this is also - true for all smaller modes whether or not there is a SUBREG, but - is not worth testing for with no SUBREG). */ - - /* Note that GET_MODE (op0) may not equal MODE. */ - if (code == EQ && GET_CODE (op0) == SUBREG - && (GET_MODE_SIZE (GET_MODE (op0)) - > GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0))))) - { - enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op0)); - rtx tem = gen_lowpart_if_possible (inner_mode, op1); - - record_jump_cond (code, mode, SUBREG_REG (op0), - tem ? tem : gen_rtx_SUBREG (inner_mode, op1, 0), - reversed_nonequality); - } - - if (code == EQ && GET_CODE (op1) == SUBREG - && (GET_MODE_SIZE (GET_MODE (op1)) - > GET_MODE_SIZE (GET_MODE (SUBREG_REG (op1))))) - { - enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op1)); - rtx tem = gen_lowpart_if_possible (inner_mode, op0); - - record_jump_cond (code, mode, SUBREG_REG (op1), - tem ? tem : gen_rtx_SUBREG (inner_mode, op0, 0), - reversed_nonequality); - } - - /* Similarly, if this is an NE comparison, and either is a SUBREG - making a smaller mode, we know the whole thing is also NE. */ - - /* Note that GET_MODE (op0) may not equal MODE; - if we test MODE instead, we can get an infinite recursion - alternating between two modes each wider than MODE. */ - - if (code == NE && GET_CODE (op0) == SUBREG - && subreg_lowpart_p (op0) - && (GET_MODE_SIZE (GET_MODE (op0)) - < GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0))))) - { - enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op0)); - rtx tem = gen_lowpart_if_possible (inner_mode, op1); - - record_jump_cond (code, mode, SUBREG_REG (op0), - tem ? tem : gen_rtx_SUBREG (inner_mode, op1, 0), - reversed_nonequality); - } - - if (code == NE && GET_CODE (op1) == SUBREG - && subreg_lowpart_p (op1) - && (GET_MODE_SIZE (GET_MODE (op1)) - < GET_MODE_SIZE (GET_MODE (SUBREG_REG (op1))))) - { - enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op1)); - rtx tem = gen_lowpart_if_possible (inner_mode, op0); - - record_jump_cond (code, mode, SUBREG_REG (op1), - tem ? tem : gen_rtx_SUBREG (inner_mode, op0, 0), - reversed_nonequality); - } - - /* Hash both operands. */ - - do_not_record = 0; - hash_arg_in_memory = 0; - hash_arg_in_struct = 0; - op0_hash = HASH (op0, mode); - op0_in_memory = hash_arg_in_memory; - op0_in_struct = hash_arg_in_struct; - - if (do_not_record) - return; - - do_not_record = 0; - hash_arg_in_memory = 0; - hash_arg_in_struct = 0; - op1_hash = HASH (op1, mode); - op1_in_memory = hash_arg_in_memory; - op1_in_struct = hash_arg_in_struct; - - if (do_not_record) - return; - - /* Look up both operands. */ - op0_elt = lookup (op0, op0_hash, mode); - op1_elt = lookup (op1, op1_hash, mode); - - /* If both operands are already equivalent or if they are not in the - table but are identical, do nothing. */ - if ((op0_elt != 0 && op1_elt != 0 - && op0_elt->first_same_value == op1_elt->first_same_value) - || op0 == op1 || rtx_equal_p (op0, op1)) - return; - - /* If we aren't setting two things equal all we can do is save this - comparison. Similarly if this is floating-point. In the latter - case, OP1 might be zero and both -0.0 and 0.0 are equal to it. - If we record the equality, we might inadvertently delete code - whose intent was to change -0 to +0. */ - - if (code != EQ || FLOAT_MODE_P (GET_MODE (op0))) - { - /* If we reversed a floating-point comparison, if OP0 is not a - register, or if OP1 is neither a register or constant, we can't - do anything. */ - - if (GET_CODE (op1) != REG) - op1 = equiv_constant (op1); - - if ((reversed_nonequality && FLOAT_MODE_P (mode)) - || GET_CODE (op0) != REG || op1 == 0) - return; - - /* Put OP0 in the hash table if it isn't already. This gives it a - new quantity number. */ - if (op0_elt == 0) - { - if (insert_regs (op0, NULL_PTR, 0)) - { - rehash_using_reg (op0); - op0_hash = HASH (op0, mode); - - /* If OP0 is contained in OP1, this changes its hash code - as well. Faster to rehash than to check, except - for the simple case of a constant. */ - if (! CONSTANT_P (op1)) - op1_hash = HASH (op1,mode); - } - - op0_elt = insert (op0, NULL_PTR, op0_hash, mode); - op0_elt->in_memory = op0_in_memory; - op0_elt->in_struct = op0_in_struct; - } - - qty_comparison_code[REG_QTY (REGNO (op0))] = code; - if (GET_CODE (op1) == REG) - { - /* Look it up again--in case op0 and op1 are the same. */ - op1_elt = lookup (op1, op1_hash, mode); - - /* Put OP1 in the hash table so it gets a new quantity number. */ - if (op1_elt == 0) - { - if (insert_regs (op1, NULL_PTR, 0)) - { - rehash_using_reg (op1); - op1_hash = HASH (op1, mode); - } - - op1_elt = insert (op1, NULL_PTR, op1_hash, mode); - op1_elt->in_memory = op1_in_memory; - op1_elt->in_struct = op1_in_struct; - } - - qty_comparison_qty[REG_QTY (REGNO (op0))] = REG_QTY (REGNO (op1)); - qty_comparison_const[REG_QTY (REGNO (op0))] = 0; - } - else - { - qty_comparison_qty[REG_QTY (REGNO (op0))] = -1; - qty_comparison_const[REG_QTY (REGNO (op0))] = op1; - } - - return; - } - - /* If either side is still missing an equivalence, make it now, - then merge the equivalences. */ - - if (op0_elt == 0) - { - if (insert_regs (op0, NULL_PTR, 0)) - { - rehash_using_reg (op0); - op0_hash = HASH (op0, mode); - } - - op0_elt = insert (op0, NULL_PTR, op0_hash, mode); - op0_elt->in_memory = op0_in_memory; - op0_elt->in_struct = op0_in_struct; - } - - if (op1_elt == 0) - { - if (insert_regs (op1, NULL_PTR, 0)) - { - rehash_using_reg (op1); - op1_hash = HASH (op1, mode); - } - - op1_elt = insert (op1, NULL_PTR, op1_hash, mode); - op1_elt->in_memory = op1_in_memory; - op1_elt->in_struct = op1_in_struct; - } - - merge_equiv_classes (op0_elt, op1_elt); - last_jump_equiv_class = op0_elt; -} - -/* CSE processing for one instruction. - First simplify sources and addresses of all assignments - in the instruction, using previously-computed equivalents values. - Then install the new sources and destinations in the table - of available values. - - If LIBCALL_INSN is nonzero, don't record any equivalence made in - the insn. It means that INSN is inside libcall block. In this - case LIBCALL_INSN is the corresponding insn with REG_LIBCALL. */ - -/* Data on one SET contained in the instruction. */ - -struct set -{ - /* The SET rtx itself. */ - rtx rtl; - /* The SET_SRC of the rtx (the original value, if it is changing). */ - rtx src; - /* The hash-table element for the SET_SRC of the SET. */ - struct table_elt *src_elt; - /* Hash value for the SET_SRC. */ - unsigned src_hash; - /* Hash value for the SET_DEST. */ - unsigned dest_hash; - /* The SET_DEST, with SUBREG, etc., stripped. */ - rtx inner_dest; - /* Place where the pointer to the INNER_DEST was found. */ - rtx *inner_dest_loc; - /* Nonzero if the SET_SRC is in memory. */ - char src_in_memory; - /* Nonzero if the SET_SRC is in a structure. */ - char src_in_struct; - /* Nonzero if the SET_SRC contains something - whose value cannot be predicted and understood. */ - char src_volatile; - /* Original machine mode, in case it becomes a CONST_INT. */ - enum machine_mode mode; - /* A constant equivalent for SET_SRC, if any. */ - rtx src_const; - /* Hash value of constant equivalent for SET_SRC. */ - unsigned src_const_hash; - /* Table entry for constant equivalent for SET_SRC, if any. */ - struct table_elt *src_const_elt; -}; - -static void -cse_insn (insn, libcall_insn) - rtx insn; - rtx libcall_insn; -{ - register rtx x = PATTERN (insn); - register int i; - rtx tem; - register int n_sets = 0; - -#ifdef HAVE_cc0 - /* Records what this insn does to set CC0. */ - rtx this_insn_cc0 = 0; - enum machine_mode this_insn_cc0_mode = VOIDmode; -#endif - - rtx src_eqv = 0; - struct table_elt *src_eqv_elt = 0; - int src_eqv_volatile; - int src_eqv_in_memory; - int src_eqv_in_struct; - unsigned src_eqv_hash; - - struct set *sets; - - this_insn = insn; - - /* Find all the SETs and CLOBBERs in this instruction. - Record all the SETs in the array `set' and count them. - Also determine whether there is a CLOBBER that invalidates - all memory references, or all references at varying addresses. */ - - if (GET_CODE (insn) == CALL_INSN) - { - for (tem = CALL_INSN_FUNCTION_USAGE (insn); tem; tem = XEXP (tem, 1)) - if (GET_CODE (XEXP (tem, 0)) == CLOBBER) - invalidate (SET_DEST (XEXP (tem, 0)), VOIDmode); - } - - if (GET_CODE (x) == SET) - { - sets = (struct set *) alloca (sizeof (struct set)); - sets[0].rtl = x; - - /* Ignore SETs that are unconditional jumps. - They never need cse processing, so this does not hurt. - The reason is not efficiency but rather - so that we can test at the end for instructions - that have been simplified to unconditional jumps - and not be misled by unchanged instructions - that were unconditional jumps to begin with. */ - if (SET_DEST (x) == pc_rtx - && GET_CODE (SET_SRC (x)) == LABEL_REF) - ; - - /* Don't count call-insns, (set (reg 0) (call ...)), as a set. - The hard function value register is used only once, to copy to - someplace else, so it isn't worth cse'ing (and on 80386 is unsafe)! - Ensure we invalidate the destination register. On the 80386 no - other code would invalidate it since it is a fixed_reg. - We need not check the return of apply_change_group; see canon_reg. */ - - else if (GET_CODE (SET_SRC (x)) == CALL) - { - canon_reg (SET_SRC (x), insn); - apply_change_group (); - fold_rtx (SET_SRC (x), insn); - invalidate (SET_DEST (x), VOIDmode); - } - else - n_sets = 1; - } - else if (GET_CODE (x) == PARALLEL) - { - register int lim = XVECLEN (x, 0); - - sets = (struct set *) alloca (lim * sizeof (struct set)); - - /* Find all regs explicitly clobbered in this insn, - and ensure they are not replaced with any other regs - elsewhere in this insn. - When a reg that is clobbered is also used for input, - we should presume that that is for a reason, - and we should not substitute some other register - which is not supposed to be clobbered. - Therefore, this loop cannot be merged into the one below - because a CALL may precede a CLOBBER and refer to the - value clobbered. We must not let a canonicalization do - anything in that case. */ - for (i = 0; i < lim; i++) - { - register rtx y = XVECEXP (x, 0, i); - if (GET_CODE (y) == CLOBBER) - { - rtx clobbered = XEXP (y, 0); - - if (GET_CODE (clobbered) == REG - || GET_CODE (clobbered) == SUBREG) - invalidate (clobbered, VOIDmode); - else if (GET_CODE (clobbered) == STRICT_LOW_PART - || GET_CODE (clobbered) == ZERO_EXTRACT) - invalidate (XEXP (clobbered, 0), GET_MODE (clobbered)); - } - } - - for (i = 0; i < lim; i++) - { - register rtx y = XVECEXP (x, 0, i); - if (GET_CODE (y) == SET) - { - /* As above, we ignore unconditional jumps and call-insns and - ignore the result of apply_change_group. */ - if (GET_CODE (SET_SRC (y)) == CALL) - { - canon_reg (SET_SRC (y), insn); - apply_change_group (); - fold_rtx (SET_SRC (y), insn); - invalidate (SET_DEST (y), VOIDmode); - } - else if (SET_DEST (y) == pc_rtx - && GET_CODE (SET_SRC (y)) == LABEL_REF) - ; - else - sets[n_sets++].rtl = y; - } - else if (GET_CODE (y) == CLOBBER) - { - /* If we clobber memory, canon the address. - This does nothing when a register is clobbered - because we have already invalidated the reg. */ - if (GET_CODE (XEXP (y, 0)) == MEM) - canon_reg (XEXP (y, 0), NULL_RTX); - } - else if (GET_CODE (y) == USE - && ! (GET_CODE (XEXP (y, 0)) == REG - && REGNO (XEXP (y, 0)) < FIRST_PSEUDO_REGISTER)) - canon_reg (y, NULL_RTX); - else if (GET_CODE (y) == CALL) - { - /* The result of apply_change_group can be ignored; see - canon_reg. */ - canon_reg (y, insn); - apply_change_group (); - fold_rtx (y, insn); - } - } - } - else if (GET_CODE (x) == CLOBBER) - { - if (GET_CODE (XEXP (x, 0)) == MEM) - canon_reg (XEXP (x, 0), NULL_RTX); - } - - /* Canonicalize a USE of a pseudo register or memory location. */ - else if (GET_CODE (x) == USE - && ! (GET_CODE (XEXP (x, 0)) == REG - && REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER)) - canon_reg (XEXP (x, 0), NULL_RTX); - else if (GET_CODE (x) == CALL) - { - /* The result of apply_change_group can be ignored; see canon_reg. */ - canon_reg (x, insn); - apply_change_group (); - fold_rtx (x, insn); - } - - /* Store the equivalent value in SRC_EQV, if different, or if the DEST - is a STRICT_LOW_PART. The latter condition is necessary because SRC_EQV - is handled specially for this case, and if it isn't set, then there will - be no equivalence for the destination. */ - if (n_sets == 1 && REG_NOTES (insn) != 0 - && (tem = find_reg_note (insn, REG_EQUAL, NULL_RTX)) != 0 - && (! rtx_equal_p (XEXP (tem, 0), SET_SRC (sets[0].rtl)) - || GET_CODE (SET_DEST (sets[0].rtl)) == STRICT_LOW_PART)) - src_eqv = canon_reg (XEXP (tem, 0), NULL_RTX); - - /* Canonicalize sources and addresses of destinations. - We do this in a separate pass to avoid problems when a MATCH_DUP is - present in the insn pattern. In that case, we want to ensure that - we don't break the duplicate nature of the pattern. So we will replace - both operands at the same time. Otherwise, we would fail to find an - equivalent substitution in the loop calling validate_change below. - - We used to suppress canonicalization of DEST if it appears in SRC, - but we don't do this any more. */ - - for (i = 0; i < n_sets; i++) - { - rtx dest = SET_DEST (sets[i].rtl); - rtx src = SET_SRC (sets[i].rtl); - rtx new = canon_reg (src, insn); - int insn_code; - - if ((GET_CODE (new) == REG && GET_CODE (src) == REG - && ((REGNO (new) < FIRST_PSEUDO_REGISTER) - != (REGNO (src) < FIRST_PSEUDO_REGISTER))) - || (insn_code = recog_memoized (insn)) < 0 - || insn_n_dups[insn_code] > 0) - validate_change (insn, &SET_SRC (sets[i].rtl), new, 1); - else - SET_SRC (sets[i].rtl) = new; - - if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT) - { - validate_change (insn, &XEXP (dest, 1), - canon_reg (XEXP (dest, 1), insn), 1); - validate_change (insn, &XEXP (dest, 2), - canon_reg (XEXP (dest, 2), insn), 1); - } - - while (GET_CODE (dest) == SUBREG || GET_CODE (dest) == STRICT_LOW_PART - || GET_CODE (dest) == ZERO_EXTRACT - || GET_CODE (dest) == SIGN_EXTRACT) - dest = XEXP (dest, 0); - - if (GET_CODE (dest) == MEM) - canon_reg (dest, insn); - } - - /* Now that we have done all the replacements, we can apply the change - group and see if they all work. Note that this will cause some - canonicalizations that would have worked individually not to be applied - because some other canonicalization didn't work, but this should not - occur often. - - The result of apply_change_group can be ignored; see canon_reg. */ - - apply_change_group (); - - /* Set sets[i].src_elt to the class each source belongs to. - Detect assignments from or to volatile things - and set set[i] to zero so they will be ignored - in the rest of this function. - - Nothing in this loop changes the hash table or the register chains. */ - - for (i = 0; i < n_sets; i++) - { - register rtx src, dest; - register rtx src_folded; - register struct table_elt *elt = 0, *p; - enum machine_mode mode; - rtx src_eqv_here; - rtx src_const = 0; - rtx src_related = 0; - struct table_elt *src_const_elt = 0; - int src_cost = 10000, src_eqv_cost = 10000, src_folded_cost = 10000; - int src_related_cost = 10000, src_elt_cost = 10000; - /* Set non-zero if we need to call force_const_mem on with the - contents of src_folded before using it. */ - int src_folded_force_flag = 0; - - dest = SET_DEST (sets[i].rtl); - src = SET_SRC (sets[i].rtl); - - /* If SRC is a constant that has no machine mode, - hash it with the destination's machine mode. - This way we can keep different modes separate. */ - - mode = GET_MODE (src) == VOIDmode ? GET_MODE (dest) : GET_MODE (src); - sets[i].mode = mode; - - if (src_eqv) - { - enum machine_mode eqvmode = mode; - if (GET_CODE (dest) == STRICT_LOW_PART) - eqvmode = GET_MODE (SUBREG_REG (XEXP (dest, 0))); - do_not_record = 0; - hash_arg_in_memory = 0; - hash_arg_in_struct = 0; - src_eqv = fold_rtx (src_eqv, insn); - src_eqv_hash = HASH (src_eqv, eqvmode); - - /* Find the equivalence class for the equivalent expression. */ - - if (!do_not_record) - src_eqv_elt = lookup (src_eqv, src_eqv_hash, eqvmode); - - src_eqv_volatile = do_not_record; - src_eqv_in_memory = hash_arg_in_memory; - src_eqv_in_struct = hash_arg_in_struct; - } - - /* If this is a STRICT_LOW_PART assignment, src_eqv corresponds to the - value of the INNER register, not the destination. So it is not - a valid substitution for the source. But save it for later. */ - if (GET_CODE (dest) == STRICT_LOW_PART) - src_eqv_here = 0; - else - src_eqv_here = src_eqv; - - /* Simplify and foldable subexpressions in SRC. Then get the fully- - simplified result, which may not necessarily be valid. */ - src_folded = fold_rtx (src, insn); - -#if 0 - /* ??? This caused bad code to be generated for the m68k port with -O2. - Suppose src is (CONST_INT -1), and that after truncation src_folded - is (CONST_INT 3). Suppose src_folded is then used for src_const. - At the end we will add src and src_const to the same equivalence - class. We now have 3 and -1 on the same equivalence class. This - causes later instructions to be mis-optimized. */ - /* If storing a constant in a bitfield, pre-truncate the constant - so we will be able to record it later. */ - if (GET_CODE (SET_DEST (sets[i].rtl)) == ZERO_EXTRACT - || GET_CODE (SET_DEST (sets[i].rtl)) == SIGN_EXTRACT) - { - rtx width = XEXP (SET_DEST (sets[i].rtl), 1); - - if (GET_CODE (src) == CONST_INT - && GET_CODE (width) == CONST_INT - && INTVAL (width) < HOST_BITS_PER_WIDE_INT - && (INTVAL (src) & ((HOST_WIDE_INT) (-1) << INTVAL (width)))) - src_folded - = GEN_INT (INTVAL (src) & (((HOST_WIDE_INT) 1 - << INTVAL (width)) - 1)); - } -#endif - - /* Compute SRC's hash code, and also notice if it - should not be recorded at all. In that case, - prevent any further processing of this assignment. */ - do_not_record = 0; - hash_arg_in_memory = 0; - hash_arg_in_struct = 0; - - sets[i].src = src; - sets[i].src_hash = HASH (src, mode); - sets[i].src_volatile = do_not_record; - sets[i].src_in_memory = hash_arg_in_memory; - sets[i].src_in_struct = hash_arg_in_struct; - - /* If SRC is a MEM, there is a REG_EQUIV note for SRC, and DEST is - a pseudo that is set more than once, do not record SRC. Using - SRC as a replacement for anything else will be incorrect in that - situation. Note that this usually occurs only for stack slots, - in which case all the RTL would be referring to SRC, so we don't - lose any optimization opportunities by not having SRC in the - hash table. */ - - if (GET_CODE (src) == MEM - && find_reg_note (insn, REG_EQUIV, src) != 0 - && GET_CODE (dest) == REG - && REGNO (dest) >= FIRST_PSEUDO_REGISTER - && REG_N_SETS (REGNO (dest)) != 1) - sets[i].src_volatile = 1; - -#if 0 - /* It is no longer clear why we used to do this, but it doesn't - appear to still be needed. So let's try without it since this - code hurts cse'ing widened ops. */ - /* If source is a perverse subreg (such as QI treated as an SI), - treat it as volatile. It may do the work of an SI in one context - where the extra bits are not being used, but cannot replace an SI - in general. */ - if (GET_CODE (src) == SUBREG - && (GET_MODE_SIZE (GET_MODE (src)) - > GET_MODE_SIZE (GET_MODE (SUBREG_REG (src))))) - sets[i].src_volatile = 1; -#endif - - /* Locate all possible equivalent forms for SRC. Try to replace - SRC in the insn with each cheaper equivalent. - - We have the following types of equivalents: SRC itself, a folded - version, a value given in a REG_EQUAL note, or a value related - to a constant. - - Each of these equivalents may be part of an additional class - of equivalents (if more than one is in the table, they must be in - the same class; we check for this). - - If the source is volatile, we don't do any table lookups. - - We note any constant equivalent for possible later use in a - REG_NOTE. */ - - if (!sets[i].src_volatile) - elt = lookup (src, sets[i].src_hash, mode); - - sets[i].src_elt = elt; - - if (elt && src_eqv_here && src_eqv_elt) - { - if (elt->first_same_value != src_eqv_elt->first_same_value) - { - /* The REG_EQUAL is indicating that two formerly distinct - classes are now equivalent. So merge them. */ - merge_equiv_classes (elt, src_eqv_elt); - src_eqv_hash = HASH (src_eqv, elt->mode); - src_eqv_elt = lookup (src_eqv, src_eqv_hash, elt->mode); - } - - src_eqv_here = 0; - } - - else if (src_eqv_elt) - elt = src_eqv_elt; - - /* Try to find a constant somewhere and record it in `src_const'. - Record its table element, if any, in `src_const_elt'. Look in - any known equivalences first. (If the constant is not in the - table, also set `sets[i].src_const_hash'). */ - if (elt) - for (p = elt->first_same_value; p; p = p->next_same_value) - if (p->is_const) - { - src_const = p->exp; - src_const_elt = elt; - break; - } - - if (src_const == 0 - && (CONSTANT_P (src_folded) - /* Consider (minus (label_ref L1) (label_ref L2)) as - "constant" here so we will record it. This allows us - to fold switch statements when an ADDR_DIFF_VEC is used. */ - || (GET_CODE (src_folded) == MINUS - && GET_CODE (XEXP (src_folded, 0)) == LABEL_REF - && GET_CODE (XEXP (src_folded, 1)) == LABEL_REF))) - src_const = src_folded, src_const_elt = elt; - else if (src_const == 0 && src_eqv_here && CONSTANT_P (src_eqv_here)) - src_const = src_eqv_here, src_const_elt = src_eqv_elt; - - /* If we don't know if the constant is in the table, get its - hash code and look it up. */ - if (src_const && src_const_elt == 0) - { - sets[i].src_const_hash = HASH (src_const, mode); - src_const_elt = lookup (src_const, sets[i].src_const_hash, mode); - } - - sets[i].src_const = src_const; - sets[i].src_const_elt = src_const_elt; - - /* If the constant and our source are both in the table, mark them as - equivalent. Otherwise, if a constant is in the table but the source - isn't, set ELT to it. */ - if (src_const_elt && elt - && src_const_elt->first_same_value != elt->first_same_value) - merge_equiv_classes (elt, src_const_elt); - else if (src_const_elt && elt == 0) - elt = src_const_elt; - - /* See if there is a register linearly related to a constant - equivalent of SRC. */ - if (src_const - && (GET_CODE (src_const) == CONST - || (src_const_elt && src_const_elt->related_value != 0))) - { - src_related = use_related_value (src_const, src_const_elt); - if (src_related) - { - struct table_elt *src_related_elt - = lookup (src_related, HASH (src_related, mode), mode); - if (src_related_elt && elt) - { - if (elt->first_same_value - != src_related_elt->first_same_value) - /* This can occur when we previously saw a CONST - involving a SYMBOL_REF and then see the SYMBOL_REF - twice. Merge the involved classes. */ - merge_equiv_classes (elt, src_related_elt); - - src_related = 0; - src_related_elt = 0; - } - else if (src_related_elt && elt == 0) - elt = src_related_elt; - } - } - - /* See if we have a CONST_INT that is already in a register in a - wider mode. */ - - if (src_const && src_related == 0 && GET_CODE (src_const) == CONST_INT - && GET_MODE_CLASS (mode) == MODE_INT - && GET_MODE_BITSIZE (mode) < BITS_PER_WORD) - { - enum machine_mode wider_mode; - - for (wider_mode = GET_MODE_WIDER_MODE (mode); - GET_MODE_BITSIZE (wider_mode) <= BITS_PER_WORD - && src_related == 0; - wider_mode = GET_MODE_WIDER_MODE (wider_mode)) - { - struct table_elt *const_elt - = lookup (src_const, HASH (src_const, wider_mode), wider_mode); - - if (const_elt == 0) - continue; - - for (const_elt = const_elt->first_same_value; - const_elt; const_elt = const_elt->next_same_value) - if (GET_CODE (const_elt->exp) == REG) - { - src_related = gen_lowpart_if_possible (mode, - const_elt->exp); - break; - } - } - } - - /* Another possibility is that we have an AND with a constant in - a mode narrower than a word. If so, it might have been generated - as part of an "if" which would narrow the AND. If we already - have done the AND in a wider mode, we can use a SUBREG of that - value. */ - - if (flag_expensive_optimizations && ! src_related - && GET_CODE (src) == AND && GET_CODE (XEXP (src, 1)) == CONST_INT - && GET_MODE_SIZE (mode) < UNITS_PER_WORD) - { - enum machine_mode tmode; - rtx new_and = gen_rtx_AND (VOIDmode, NULL_RTX, XEXP (src, 1)); - - for (tmode = GET_MODE_WIDER_MODE (mode); - GET_MODE_SIZE (tmode) <= UNITS_PER_WORD; - tmode = GET_MODE_WIDER_MODE (tmode)) - { - rtx inner = gen_lowpart_if_possible (tmode, XEXP (src, 0)); - struct table_elt *larger_elt; - - if (inner) - { - PUT_MODE (new_and, tmode); - XEXP (new_and, 0) = inner; - larger_elt = lookup (new_and, HASH (new_and, tmode), tmode); - if (larger_elt == 0) - continue; - - for (larger_elt = larger_elt->first_same_value; - larger_elt; larger_elt = larger_elt->next_same_value) - if (GET_CODE (larger_elt->exp) == REG) - { - src_related - = gen_lowpart_if_possible (mode, larger_elt->exp); - break; - } - - if (src_related) - break; - } - } - } - -#ifdef LOAD_EXTEND_OP - /* See if a MEM has already been loaded with a widening operation; - if it has, we can use a subreg of that. Many CISC machines - also have such operations, but this is only likely to be - beneficial these machines. */ - - if (flag_expensive_optimizations && src_related == 0 - && (GET_MODE_SIZE (mode) < UNITS_PER_WORD) - && GET_MODE_CLASS (mode) == MODE_INT - && GET_CODE (src) == MEM && ! do_not_record - && LOAD_EXTEND_OP (mode) != NIL) - { - enum machine_mode tmode; - - /* Set what we are trying to extend and the operation it might - have been extended with. */ - PUT_CODE (memory_extend_rtx, LOAD_EXTEND_OP (mode)); - XEXP (memory_extend_rtx, 0) = src; - - for (tmode = GET_MODE_WIDER_MODE (mode); - GET_MODE_SIZE (tmode) <= UNITS_PER_WORD; - tmode = GET_MODE_WIDER_MODE (tmode)) - { - struct table_elt *larger_elt; - - PUT_MODE (memory_extend_rtx, tmode); - larger_elt = lookup (memory_extend_rtx, - HASH (memory_extend_rtx, tmode), tmode); - if (larger_elt == 0) - continue; - - for (larger_elt = larger_elt->first_same_value; - larger_elt; larger_elt = larger_elt->next_same_value) - if (GET_CODE (larger_elt->exp) == REG) - { - src_related = gen_lowpart_if_possible (mode, - larger_elt->exp); - break; - } - - if (src_related) - break; - } - } -#endif /* LOAD_EXTEND_OP */ - - if (src == src_folded) - src_folded = 0; - - /* At this point, ELT, if non-zero, points to a class of expressions - equivalent to the source of this SET and SRC, SRC_EQV, SRC_FOLDED, - and SRC_RELATED, if non-zero, each contain additional equivalent - expressions. Prune these latter expressions by deleting expressions - already in the equivalence class. - - Check for an equivalent identical to the destination. If found, - this is the preferred equivalent since it will likely lead to - elimination of the insn. Indicate this by placing it in - `src_related'. */ - - if (elt) elt = elt->first_same_value; - for (p = elt; p; p = p->next_same_value) - { - enum rtx_code code = GET_CODE (p->exp); - - /* If the expression is not valid, ignore it. Then we do not - have to check for validity below. In most cases, we can use - `rtx_equal_p', since canonicalization has already been done. */ - if (code != REG && ! exp_equiv_p (p->exp, p->exp, 1, 0)) - continue; - - /* Also skip paradoxical subregs, unless that's what we're - looking for. */ - if (code == SUBREG - && (GET_MODE_SIZE (GET_MODE (p->exp)) - > GET_MODE_SIZE (GET_MODE (SUBREG_REG (p->exp)))) - && ! (src != 0 - && GET_CODE (src) == SUBREG - && GET_MODE (src) == GET_MODE (p->exp) - && (GET_MODE_SIZE (GET_MODE (SUBREG_REG (src))) - < GET_MODE_SIZE (GET_MODE (SUBREG_REG (p->exp)))))) - continue; - - if (src && GET_CODE (src) == code && rtx_equal_p (src, p->exp)) - src = 0; - else if (src_folded && GET_CODE (src_folded) == code - && rtx_equal_p (src_folded, p->exp)) - src_folded = 0; - else if (src_eqv_here && GET_CODE (src_eqv_here) == code - && rtx_equal_p (src_eqv_here, p->exp)) - src_eqv_here = 0; - else if (src_related && GET_CODE (src_related) == code - && rtx_equal_p (src_related, p->exp)) - src_related = 0; - - /* This is the same as the destination of the insns, we want - to prefer it. Copy it to src_related. The code below will - then give it a negative cost. */ - if (GET_CODE (dest) == code && rtx_equal_p (p->exp, dest)) - src_related = dest; - - } - - /* Find the cheapest valid equivalent, trying all the available - possibilities. Prefer items not in the hash table to ones - that are when they are equal cost. Note that we can never - worsen an insn as the current contents will also succeed. - If we find an equivalent identical to the destination, use it as best, - since this insn will probably be eliminated in that case. */ - if (src) - { - if (rtx_equal_p (src, dest)) - src_cost = -1; - else - src_cost = COST (src); - } - - if (src_eqv_here) - { - if (rtx_equal_p (src_eqv_here, dest)) - src_eqv_cost = -1; - else - src_eqv_cost = COST (src_eqv_here); - } - - if (src_folded) - { - if (rtx_equal_p (src_folded, dest)) - src_folded_cost = -1; - else - src_folded_cost = COST (src_folded); - } - - if (src_related) - { - if (rtx_equal_p (src_related, dest)) - src_related_cost = -1; - else - src_related_cost = COST (src_related); - } - - /* If this was an indirect jump insn, a known label will really be - cheaper even though it looks more expensive. */ - if (dest == pc_rtx && src_const && GET_CODE (src_const) == LABEL_REF) - src_folded = src_const, src_folded_cost = -1; - - /* Terminate loop when replacement made. This must terminate since - the current contents will be tested and will always be valid. */ - while (1) - { - rtx trial, old_src; - - /* Skip invalid entries. */ - while (elt && GET_CODE (elt->exp) != REG - && ! exp_equiv_p (elt->exp, elt->exp, 1, 0)) - elt = elt->next_same_value; - - /* A paradoxical subreg would be bad here: it'll be the right - size, but later may be adjusted so that the upper bits aren't - what we want. So reject it. */ - if (elt != 0 - && GET_CODE (elt->exp) == SUBREG - && (GET_MODE_SIZE (GET_MODE (elt->exp)) - > GET_MODE_SIZE (GET_MODE (SUBREG_REG (elt->exp)))) - /* It is okay, though, if the rtx we're trying to match - will ignore any of the bits we can't predict. */ - && ! (src != 0 - && GET_CODE (src) == SUBREG - && GET_MODE (src) == GET_MODE (elt->exp) - && (GET_MODE_SIZE (GET_MODE (SUBREG_REG (src))) - < GET_MODE_SIZE (GET_MODE (SUBREG_REG (elt->exp)))))) - { - elt = elt->next_same_value; - continue; - } - - if (elt) src_elt_cost = elt->cost; - - /* Find cheapest and skip it for the next time. For items - of equal cost, use this order: - src_folded, src, src_eqv, src_related and hash table entry. */ - if (src_folded_cost <= src_cost - && src_folded_cost <= src_eqv_cost - && src_folded_cost <= src_related_cost - && src_folded_cost <= src_elt_cost) - { - trial = src_folded, src_folded_cost = 10000; - if (src_folded_force_flag) - trial = force_const_mem (mode, trial); - } - else if (src_cost <= src_eqv_cost - && src_cost <= src_related_cost - && src_cost <= src_elt_cost) - trial = src, src_cost = 10000; - else if (src_eqv_cost <= src_related_cost - && src_eqv_cost <= src_elt_cost) - trial = copy_rtx (src_eqv_here), src_eqv_cost = 10000; - else if (src_related_cost <= src_elt_cost) - trial = copy_rtx (src_related), src_related_cost = 10000; - else - { - trial = copy_rtx (elt->exp); - elt = elt->next_same_value; - src_elt_cost = 10000; - } - - /* We don't normally have an insn matching (set (pc) (pc)), so - check for this separately here. We will delete such an - insn below. - - Tablejump insns contain a USE of the table, so simply replacing - the operand with the constant won't match. This is simply an - unconditional branch, however, and is therefore valid. Just - insert the substitution here and we will delete and re-emit - the insn later. */ - - /* Keep track of the original SET_SRC so that we can fix notes - on libcall instructions. */ - old_src = SET_SRC (sets[i].rtl); - - if (n_sets == 1 && dest == pc_rtx - && (trial == pc_rtx - || (GET_CODE (trial) == LABEL_REF - && ! condjump_p (insn)))) - { - /* If TRIAL is a label in front of a jump table, we are - really falling through the switch (this is how casesi - insns work), so we must branch around the table. */ - if (GET_CODE (trial) == CODE_LABEL - && NEXT_INSN (trial) != 0 - && GET_CODE (NEXT_INSN (trial)) == JUMP_INSN - && (GET_CODE (PATTERN (NEXT_INSN (trial))) == ADDR_DIFF_VEC - || GET_CODE (PATTERN (NEXT_INSN (trial))) == ADDR_VEC)) - - trial = gen_rtx_LABEL_REF (Pmode, get_label_after (trial)); - - SET_SRC (sets[i].rtl) = trial; - cse_jumps_altered = 1; - break; - } - - /* Look for a substitution that makes a valid insn. */ - else if (validate_change (insn, &SET_SRC (sets[i].rtl), trial, 0)) - { - /* If we just made a substitution inside a libcall, then we - need to make the same substitution in any notes attached - to the RETVAL insn. */ - if (libcall_insn - && (GET_CODE (old_src) == REG - || GET_CODE (old_src) == SUBREG - || GET_CODE (old_src) == MEM)) - replace_rtx (REG_NOTES (libcall_insn), old_src, - canon_reg (SET_SRC (sets[i].rtl), insn)); - - /* The result of apply_change_group can be ignored; see - canon_reg. */ - - validate_change (insn, &SET_SRC (sets[i].rtl), - canon_reg (SET_SRC (sets[i].rtl), insn), - 1); - apply_change_group (); - break; - } - - /* If we previously found constant pool entries for - constants and this is a constant, try making a - pool entry. Put it in src_folded unless we already have done - this since that is where it likely came from. */ - - else if (constant_pool_entries_cost - && CONSTANT_P (trial) - && ! (GET_CODE (trial) == CONST - && GET_CODE (XEXP (trial, 0)) == TRUNCATE) - && (src_folded == 0 - || (GET_CODE (src_folded) != MEM - && ! src_folded_force_flag)) - && GET_MODE_CLASS (mode) != MODE_CC - && mode != VOIDmode) - { - src_folded_force_flag = 1; - src_folded = trial; - src_folded_cost = constant_pool_entries_cost; - } - } - - src = SET_SRC (sets[i].rtl); - - /* In general, it is good to have a SET with SET_SRC == SET_DEST. - However, there is an important exception: If both are registers - that are not the head of their equivalence class, replace SET_SRC - with the head of the class. If we do not do this, we will have - both registers live over a portion of the basic block. This way, - their lifetimes will likely abut instead of overlapping. */ - if (GET_CODE (dest) == REG - && REGNO_QTY_VALID_P (REGNO (dest)) - && qty_mode[REG_QTY (REGNO (dest))] == GET_MODE (dest) - && qty_first_reg[REG_QTY (REGNO (dest))] != REGNO (dest) - && GET_CODE (src) == REG && REGNO (src) == REGNO (dest) - /* Don't do this if the original insn had a hard reg as - SET_SRC. */ - && (GET_CODE (sets[i].src) != REG - || REGNO (sets[i].src) >= FIRST_PSEUDO_REGISTER)) - /* We can't call canon_reg here because it won't do anything if - SRC is a hard register. */ - { - int first = qty_first_reg[REG_QTY (REGNO (src))]; - rtx new_src - = (first >= FIRST_PSEUDO_REGISTER - ? regno_reg_rtx[first] : gen_rtx_REG (GET_MODE (src), first)); - - /* We must use validate-change even for this, because this - might be a special no-op instruction, suitable only to - tag notes onto. */ - if (validate_change (insn, &SET_SRC (sets[i].rtl), new_src, 0)) - { - src = new_src; - /* If we had a constant that is cheaper than what we are now - setting SRC to, use that constant. We ignored it when we - thought we could make this into a no-op. */ - if (src_const && COST (src_const) < COST (src) - && validate_change (insn, &SET_SRC (sets[i].rtl), src_const, - 0)) - src = src_const; - } - } - - /* If we made a change, recompute SRC values. */ - if (src != sets[i].src) - { - do_not_record = 0; - hash_arg_in_memory = 0; - hash_arg_in_struct = 0; - sets[i].src = src; - sets[i].src_hash = HASH (src, mode); - sets[i].src_volatile = do_not_record; - sets[i].src_in_memory = hash_arg_in_memory; - sets[i].src_in_struct = hash_arg_in_struct; - sets[i].src_elt = lookup (src, sets[i].src_hash, mode); - } - - /* If this is a single SET, we are setting a register, and we have an - equivalent constant, we want to add a REG_NOTE. We don't want - to write a REG_EQUAL note for a constant pseudo since verifying that - that pseudo hasn't been eliminated is a pain. Such a note also - won't help anything. - - Avoid a REG_EQUAL note for (CONST (MINUS (LABEL_REF) (LABEL_REF))) - which can be created for a reference to a compile time computable - entry in a jump table. */ - - if (n_sets == 1 && src_const && GET_CODE (dest) == REG - && GET_CODE (src_const) != REG - && ! (GET_CODE (src_const) == CONST - && GET_CODE (XEXP (src_const, 0)) == MINUS - && GET_CODE (XEXP (XEXP (src_const, 0), 0)) == LABEL_REF - && GET_CODE (XEXP (XEXP (src_const, 0), 1)) == LABEL_REF)) - { - tem = find_reg_note (insn, REG_EQUAL, NULL_RTX); - - /* Make sure that the rtx is not shared with any other insn. */ - src_const = copy_rtx (src_const); - - /* Record the actual constant value in a REG_EQUAL note, making - a new one if one does not already exist. */ - if (tem) - XEXP (tem, 0) = src_const; - else - REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_EQUAL, - src_const, REG_NOTES (insn)); - - /* If storing a constant value in a register that - previously held the constant value 0, - record this fact with a REG_WAS_0 note on this insn. - - Note that the *register* is required to have previously held 0, - not just any register in the quantity and we must point to the - insn that set that register to zero. - - Rather than track each register individually, we just see if - the last set for this quantity was for this register. */ - - if (REGNO_QTY_VALID_P (REGNO (dest)) - && qty_const[REG_QTY (REGNO (dest))] == const0_rtx) - { - /* See if we previously had a REG_WAS_0 note. */ - rtx note = find_reg_note (insn, REG_WAS_0, NULL_RTX); - rtx const_insn = qty_const_insn[REG_QTY (REGNO (dest))]; - - if ((tem = single_set (const_insn)) != 0 - && rtx_equal_p (SET_DEST (tem), dest)) - { - if (note) - XEXP (note, 0) = const_insn; - else - REG_NOTES (insn) = gen_rtx_INSN_LIST (REG_WAS_0, - const_insn, - REG_NOTES (insn)); - } - } - } - - /* Now deal with the destination. */ - do_not_record = 0; - sets[i].inner_dest_loc = &SET_DEST (sets[0].rtl); - - /* Look within any SIGN_EXTRACT or ZERO_EXTRACT - to the MEM or REG within it. */ - while (GET_CODE (dest) == SIGN_EXTRACT - || GET_CODE (dest) == ZERO_EXTRACT - || GET_CODE (dest) == SUBREG - || GET_CODE (dest) == STRICT_LOW_PART) - { - sets[i].inner_dest_loc = &XEXP (dest, 0); - dest = XEXP (dest, 0); - } - - sets[i].inner_dest = dest; - - if (GET_CODE (dest) == MEM) - { -#ifdef PUSH_ROUNDING - /* Stack pushes invalidate the stack pointer. */ - rtx addr = XEXP (dest, 0); - if ((GET_CODE (addr) == PRE_DEC || GET_CODE (addr) == PRE_INC - || GET_CODE (addr) == POST_DEC || GET_CODE (addr) == POST_INC) - && XEXP (addr, 0) == stack_pointer_rtx) - invalidate (stack_pointer_rtx, Pmode); -#endif - dest = fold_rtx (dest, insn); - } - - /* Compute the hash code of the destination now, - before the effects of this instruction are recorded, - since the register values used in the address computation - are those before this instruction. */ - sets[i].dest_hash = HASH (dest, mode); - - /* Don't enter a bit-field in the hash table - because the value in it after the store - may not equal what was stored, due to truncation. */ - - if (GET_CODE (SET_DEST (sets[i].rtl)) == ZERO_EXTRACT - || GET_CODE (SET_DEST (sets[i].rtl)) == SIGN_EXTRACT) - { - rtx width = XEXP (SET_DEST (sets[i].rtl), 1); - - if (src_const != 0 && GET_CODE (src_const) == CONST_INT - && GET_CODE (width) == CONST_INT - && INTVAL (width) < HOST_BITS_PER_WIDE_INT - && ! (INTVAL (src_const) - & ((HOST_WIDE_INT) (-1) << INTVAL (width)))) - /* Exception: if the value is constant, - and it won't be truncated, record it. */ - ; - else - { - /* This is chosen so that the destination will be invalidated - but no new value will be recorded. - We must invalidate because sometimes constant - values can be recorded for bitfields. */ - sets[i].src_elt = 0; - sets[i].src_volatile = 1; - src_eqv = 0; - src_eqv_elt = 0; - } - } - - /* If only one set in a JUMP_INSN and it is now a no-op, we can delete - the insn. */ - else if (n_sets == 1 && dest == pc_rtx && src == pc_rtx) - { - PUT_CODE (insn, NOTE); - NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED; - NOTE_SOURCE_FILE (insn) = 0; - cse_jumps_altered = 1; - /* One less use of the label this insn used to jump to. */ - if (JUMP_LABEL (insn) != 0) - --LABEL_NUSES (JUMP_LABEL (insn)); - /* No more processing for this set. */ - sets[i].rtl = 0; - } - - /* If this SET is now setting PC to a label, we know it used to - be a conditional or computed branch. So we see if we can follow - it. If it was a computed branch, delete it and re-emit. */ - else if (dest == pc_rtx && GET_CODE (src) == LABEL_REF) - { - rtx p; - - /* If this is not in the format for a simple branch and - we are the only SET in it, re-emit it. */ - if (! simplejump_p (insn) && n_sets == 1) - { - rtx new = emit_jump_insn_before (gen_jump (XEXP (src, 0)), insn); - JUMP_LABEL (new) = XEXP (src, 0); - LABEL_NUSES (XEXP (src, 0))++; - insn = new; - } - else - /* Otherwise, force rerecognition, since it probably had - a different pattern before. - This shouldn't really be necessary, since whatever - changed the source value above should have done this. - Until the right place is found, might as well do this here. */ - INSN_CODE (insn) = -1; - - /* Now emit a BARRIER after the unconditional jump. Do not bother - deleting any unreachable code, let jump/flow do that. */ - if (NEXT_INSN (insn) != 0 - && GET_CODE (NEXT_INSN (insn)) != BARRIER) - emit_barrier_after (insn); - - cse_jumps_altered = 1; - sets[i].rtl = 0; - } - - /* If destination is volatile, invalidate it and then do no further - processing for this assignment. */ - - else if (do_not_record) - { - if (GET_CODE (dest) == REG || GET_CODE (dest) == SUBREG - || GET_CODE (dest) == MEM) - invalidate (dest, VOIDmode); - else if (GET_CODE (dest) == STRICT_LOW_PART - || GET_CODE (dest) == ZERO_EXTRACT) - invalidate (XEXP (dest, 0), GET_MODE (dest)); - sets[i].rtl = 0; - } - - if (sets[i].rtl != 0 && dest != SET_DEST (sets[i].rtl)) - sets[i].dest_hash = HASH (SET_DEST (sets[i].rtl), mode); - -#ifdef HAVE_cc0 - /* If setting CC0, record what it was set to, or a constant, if it - is equivalent to a constant. If it is being set to a floating-point - value, make a COMPARE with the appropriate constant of 0. If we - don't do this, later code can interpret this as a test against - const0_rtx, which can cause problems if we try to put it into an - insn as a floating-point operand. */ - if (dest == cc0_rtx) - { - this_insn_cc0 = src_const && mode != VOIDmode ? src_const : src; - this_insn_cc0_mode = mode; - if (FLOAT_MODE_P (mode)) - this_insn_cc0 = gen_rtx_COMPARE (VOIDmode, this_insn_cc0, - CONST0_RTX (mode)); - } -#endif - } - - /* Now enter all non-volatile source expressions in the hash table - if they are not already present. - Record their equivalence classes in src_elt. - This way we can insert the corresponding destinations into - the same classes even if the actual sources are no longer in them - (having been invalidated). */ - - if (src_eqv && src_eqv_elt == 0 && sets[0].rtl != 0 && ! src_eqv_volatile - && ! rtx_equal_p (src_eqv, SET_DEST (sets[0].rtl))) - { - register struct table_elt *elt; - register struct table_elt *classp = sets[0].src_elt; - rtx dest = SET_DEST (sets[0].rtl); - enum machine_mode eqvmode = GET_MODE (dest); - - if (GET_CODE (dest) == STRICT_LOW_PART) - { - eqvmode = GET_MODE (SUBREG_REG (XEXP (dest, 0))); - classp = 0; - } - if (insert_regs (src_eqv, classp, 0)) - { - rehash_using_reg (src_eqv); - src_eqv_hash = HASH (src_eqv, eqvmode); - } - elt = insert (src_eqv, classp, src_eqv_hash, eqvmode); - elt->in_memory = src_eqv_in_memory; - elt->in_struct = src_eqv_in_struct; - src_eqv_elt = elt; - - /* Check to see if src_eqv_elt is the same as a set source which - does not yet have an elt, and if so set the elt of the set source - to src_eqv_elt. */ - for (i = 0; i < n_sets; i++) - if (sets[i].rtl && sets[i].src_elt == 0 - && rtx_equal_p (SET_SRC (sets[i].rtl), src_eqv)) - sets[i].src_elt = src_eqv_elt; - } - - for (i = 0; i < n_sets; i++) - if (sets[i].rtl && ! sets[i].src_volatile - && ! rtx_equal_p (SET_SRC (sets[i].rtl), SET_DEST (sets[i].rtl))) - { - if (GET_CODE (SET_DEST (sets[i].rtl)) == STRICT_LOW_PART) - { - /* REG_EQUAL in setting a STRICT_LOW_PART - gives an equivalent for the entire destination register, - not just for the subreg being stored in now. - This is a more interesting equivalence, so we arrange later - to treat the entire reg as the destination. */ - sets[i].src_elt = src_eqv_elt; - sets[i].src_hash = src_eqv_hash; - } - else - { - /* Insert source and constant equivalent into hash table, if not - already present. */ - register struct table_elt *classp = src_eqv_elt; - register rtx src = sets[i].src; - register rtx dest = SET_DEST (sets[i].rtl); - enum machine_mode mode - = GET_MODE (src) == VOIDmode ? GET_MODE (dest) : GET_MODE (src); - - /* Don't put a hard register source into the table if this is - the last insn of a libcall. */ - if (sets[i].src_elt == 0 - && (GET_CODE (src) != REG - || REGNO (src) >= FIRST_PSEUDO_REGISTER - || ! find_reg_note (insn, REG_RETVAL, NULL_RTX))) - { - register struct table_elt *elt; - - /* Note that these insert_regs calls cannot remove - any of the src_elt's, because they would have failed to - match if not still valid. */ - if (insert_regs (src, classp, 0)) - { - rehash_using_reg (src); - sets[i].src_hash = HASH (src, mode); - } - elt = insert (src, classp, sets[i].src_hash, mode); - elt->in_memory = sets[i].src_in_memory; - elt->in_struct = sets[i].src_in_struct; - sets[i].src_elt = classp = elt; - } - - if (sets[i].src_const && sets[i].src_const_elt == 0 - && src != sets[i].src_const - && ! rtx_equal_p (sets[i].src_const, src)) - sets[i].src_elt = insert (sets[i].src_const, classp, - sets[i].src_const_hash, mode); - } - } - else if (sets[i].src_elt == 0) - /* If we did not insert the source into the hash table (e.g., it was - volatile), note the equivalence class for the REG_EQUAL value, if any, - so that the destination goes into that class. */ - sets[i].src_elt = src_eqv_elt; - - invalidate_from_clobbers (x); - - /* Some registers are invalidated by subroutine calls. Memory is - invalidated by non-constant calls. */ - - if (GET_CODE (insn) == CALL_INSN) - { - if (! CONST_CALL_P (insn)) - invalidate_memory (); - invalidate_for_call (); - } - - /* Now invalidate everything set by this instruction. - If a SUBREG or other funny destination is being set, - sets[i].rtl is still nonzero, so here we invalidate the reg - a part of which is being set. */ - - for (i = 0; i < n_sets; i++) - if (sets[i].rtl) - { - /* We can't use the inner dest, because the mode associated with - a ZERO_EXTRACT is significant. */ - register rtx dest = SET_DEST (sets[i].rtl); - - /* Needed for registers to remove the register from its - previous quantity's chain. - Needed for memory if this is a nonvarying address, unless - we have just done an invalidate_memory that covers even those. */ - if (GET_CODE (dest) == REG || GET_CODE (dest) == SUBREG - || GET_CODE (dest) == MEM) - invalidate (dest, VOIDmode); - else if (GET_CODE (dest) == STRICT_LOW_PART - || GET_CODE (dest) == ZERO_EXTRACT) - invalidate (XEXP (dest, 0), GET_MODE (dest)); - } - - /* A volatile ASM invalidates everything. */ - if (GET_CODE (insn) == INSN - && GET_CODE (PATTERN (insn)) == ASM_OPERANDS - && MEM_VOLATILE_P (PATTERN (insn))) - flush_hash_table (); - - /* Make sure registers mentioned in destinations - are safe for use in an expression to be inserted. - This removes from the hash table - any invalid entry that refers to one of these registers. - - We don't care about the return value from mention_regs because - we are going to hash the SET_DEST values unconditionally. */ - - for (i = 0; i < n_sets; i++) - { - if (sets[i].rtl) - { - rtx x = SET_DEST (sets[i].rtl); - - if (GET_CODE (x) != REG) - mention_regs (x); - else - { - /* We used to rely on all references to a register becoming - inaccessible when a register changes to a new quantity, - since that changes the hash code. However, that is not - safe, since after NBUCKETS new quantities we get a - hash 'collision' of a register with its own invalid - entries. And since SUBREGs have been changed not to - change their hash code with the hash code of the register, - it wouldn't work any longer at all. So we have to check - for any invalid references lying around now. - This code is similar to the REG case in mention_regs, - but it knows that reg_tick has been incremented, and - it leaves reg_in_table as -1 . */ - register int regno = REGNO (x); - register int endregno - = regno + (regno >= FIRST_PSEUDO_REGISTER ? 1 - : HARD_REGNO_NREGS (regno, GET_MODE (x))); - int i; - - for (i = regno; i < endregno; i++) - { - if (REG_IN_TABLE (i) >= 0) - { - remove_invalid_refs (i); - REG_IN_TABLE (i) = -1; - } - } - } - } - } - - /* We may have just removed some of the src_elt's from the hash table. - So replace each one with the current head of the same class. */ - - for (i = 0; i < n_sets; i++) - if (sets[i].rtl) - { - if (sets[i].src_elt && sets[i].src_elt->first_same_value == 0) - /* If elt was removed, find current head of same class, - or 0 if nothing remains of that class. */ - { - register struct table_elt *elt = sets[i].src_elt; - - while (elt && elt->prev_same_value) - elt = elt->prev_same_value; - - while (elt && elt->first_same_value == 0) - elt = elt->next_same_value; - sets[i].src_elt = elt ? elt->first_same_value : 0; - } - } - - /* Now insert the destinations into their equivalence classes. */ - - for (i = 0; i < n_sets; i++) - if (sets[i].rtl) - { - register rtx dest = SET_DEST (sets[i].rtl); - rtx inner_dest = sets[i].inner_dest; - register struct table_elt *elt; - - /* Don't record value if we are not supposed to risk allocating - floating-point values in registers that might be wider than - memory. */ - if ((flag_float_store - && GET_CODE (dest) == MEM - && FLOAT_MODE_P (GET_MODE (dest))) - /* Don't record BLKmode values, because we don't know the - size of it, and can't be sure that other BLKmode values - have the same or smaller size. */ - || GET_MODE (dest) == BLKmode - /* Don't record values of destinations set inside a libcall block - since we might delete the libcall. Things should have been set - up so we won't want to reuse such a value, but we play it safe - here. */ - || libcall_insn - /* If we didn't put a REG_EQUAL value or a source into the hash - table, there is no point is recording DEST. */ - || sets[i].src_elt == 0 - /* If DEST is a paradoxical SUBREG and SRC is a ZERO_EXTEND - or SIGN_EXTEND, don't record DEST since it can cause - some tracking to be wrong. - - ??? Think about this more later. */ - || (GET_CODE (dest) == SUBREG - && (GET_MODE_SIZE (GET_MODE (dest)) - > GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest)))) - && (GET_CODE (sets[i].src) == SIGN_EXTEND - || GET_CODE (sets[i].src) == ZERO_EXTEND))) - continue; - - /* STRICT_LOW_PART isn't part of the value BEING set, - and neither is the SUBREG inside it. - Note that in this case SETS[I].SRC_ELT is really SRC_EQV_ELT. */ - if (GET_CODE (dest) == STRICT_LOW_PART) - dest = SUBREG_REG (XEXP (dest, 0)); - - if (GET_CODE (dest) == REG || GET_CODE (dest) == SUBREG) - /* Registers must also be inserted into chains for quantities. */ - if (insert_regs (dest, sets[i].src_elt, 1)) - { - /* If `insert_regs' changes something, the hash code must be - recalculated. */ - rehash_using_reg (dest); - sets[i].dest_hash = HASH (dest, GET_MODE (dest)); - } - - if (GET_CODE (inner_dest) == MEM - && GET_CODE (XEXP (inner_dest, 0)) == ADDRESSOF) - /* Given (SET (MEM (ADDRESSOF (X))) Y) we don't want to say - that (MEM (ADDRESSOF (X))) is equivalent to Y. - Consider the case in which the address of the MEM is - passed to a function, which alters the MEM. Then, if we - later use Y instead of the MEM we'll miss the update. */ - elt = insert (dest, 0, sets[i].dest_hash, GET_MODE (dest)); - else - elt = insert (dest, sets[i].src_elt, - sets[i].dest_hash, GET_MODE (dest)); - - elt->in_memory = (GET_CODE (sets[i].inner_dest) == MEM - && (! RTX_UNCHANGING_P (sets[i].inner_dest) - || FIXED_BASE_PLUS_P (XEXP (sets[i].inner_dest, - 0)))); - - if (elt->in_memory) - { - /* This implicitly assumes a whole struct - need not have MEM_IN_STRUCT_P. - But a whole struct is *supposed* to have MEM_IN_STRUCT_P. */ - elt->in_struct = (MEM_IN_STRUCT_P (sets[i].inner_dest) - || sets[i].inner_dest != SET_DEST (sets[i].rtl)); - } - - /* If we have (set (subreg:m1 (reg:m2 foo) 0) (bar:m1)), M1 is no - narrower than M2, and both M1 and M2 are the same number of words, - we are also doing (set (reg:m2 foo) (subreg:m2 (bar:m1) 0)) so - make that equivalence as well. - - However, BAR may have equivalences for which gen_lowpart_if_possible - will produce a simpler value than gen_lowpart_if_possible applied to - BAR (e.g., if BAR was ZERO_EXTENDed from M2), so we will scan all - BAR's equivalences. If we don't get a simplified form, make - the SUBREG. It will not be used in an equivalence, but will - cause two similar assignments to be detected. - - Note the loop below will find SUBREG_REG (DEST) since we have - already entered SRC and DEST of the SET in the table. */ - - if (GET_CODE (dest) == SUBREG - && (((GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))) - 1) - / UNITS_PER_WORD) - == (GET_MODE_SIZE (GET_MODE (dest)) - 1)/ UNITS_PER_WORD) - && (GET_MODE_SIZE (GET_MODE (dest)) - >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest)))) - && sets[i].src_elt != 0) - { - enum machine_mode new_mode = GET_MODE (SUBREG_REG (dest)); - struct table_elt *elt, *classp = 0; - - for (elt = sets[i].src_elt->first_same_value; elt; - elt = elt->next_same_value) - { - rtx new_src = 0; - unsigned src_hash; - struct table_elt *src_elt; - - /* Ignore invalid entries. */ - if (GET_CODE (elt->exp) != REG - && ! exp_equiv_p (elt->exp, elt->exp, 1, 0)) - continue; - - new_src = gen_lowpart_if_possible (new_mode, elt->exp); - if (new_src == 0) - new_src = gen_rtx_SUBREG (new_mode, elt->exp, 0); - - src_hash = HASH (new_src, new_mode); - src_elt = lookup (new_src, src_hash, new_mode); - - /* Put the new source in the hash table is if isn't - already. */ - if (src_elt == 0) - { - if (insert_regs (new_src, classp, 0)) - { - rehash_using_reg (new_src); - src_hash = HASH (new_src, new_mode); - } - src_elt = insert (new_src, classp, src_hash, new_mode); - src_elt->in_memory = elt->in_memory; - src_elt->in_struct = elt->in_struct; - } - else if (classp && classp != src_elt->first_same_value) - /* Show that two things that we've seen before are - actually the same. */ - merge_equiv_classes (src_elt, classp); - - classp = src_elt->first_same_value; - /* Ignore invalid entries. */ - while (classp - && GET_CODE (classp->exp) != REG - && ! exp_equiv_p (classp->exp, classp->exp, 1, 0)) - classp = classp->next_same_value; - } - } - } - - /* Special handling for (set REG0 REG1) - where REG0 is the "cheapest", cheaper than REG1. - After cse, REG1 will probably not be used in the sequel, - so (if easily done) change this insn to (set REG1 REG0) and - replace REG1 with REG0 in the previous insn that computed their value. - Then REG1 will become a dead store and won't cloud the situation - for later optimizations. - - Do not make this change if REG1 is a hard register, because it will - then be used in the sequel and we may be changing a two-operand insn - into a three-operand insn. - - Also do not do this if we are operating on a copy of INSN. - - Also don't do this if INSN ends a libcall; this would cause an unrelated - register to be set in the middle of a libcall, and we then get bad code - if the libcall is deleted. */ - - if (n_sets == 1 && sets[0].rtl && GET_CODE (SET_DEST (sets[0].rtl)) == REG - && NEXT_INSN (PREV_INSN (insn)) == insn - && GET_CODE (SET_SRC (sets[0].rtl)) == REG - && REGNO (SET_SRC (sets[0].rtl)) >= FIRST_PSEUDO_REGISTER - && REGNO_QTY_VALID_P (REGNO (SET_SRC (sets[0].rtl))) - && (qty_first_reg[REG_QTY (REGNO (SET_SRC (sets[0].rtl)))] - == REGNO (SET_DEST (sets[0].rtl))) - && ! find_reg_note (insn, REG_RETVAL, NULL_RTX)) - { - rtx prev = PREV_INSN (insn); - while (prev && GET_CODE (prev) == NOTE) - prev = PREV_INSN (prev); - - if (prev && GET_CODE (prev) == INSN && GET_CODE (PATTERN (prev)) == SET - && SET_DEST (PATTERN (prev)) == SET_SRC (sets[0].rtl)) - { - rtx dest = SET_DEST (sets[0].rtl); - rtx note = find_reg_note (prev, REG_EQUIV, NULL_RTX); - - validate_change (prev, & SET_DEST (PATTERN (prev)), dest, 1); - validate_change (insn, & SET_DEST (sets[0].rtl), - SET_SRC (sets[0].rtl), 1); - validate_change (insn, & SET_SRC (sets[0].rtl), dest, 1); - apply_change_group (); - - /* If REG1 was equivalent to a constant, REG0 is not. */ - if (note) - PUT_REG_NOTE_KIND (note, REG_EQUAL); - - /* If there was a REG_WAS_0 note on PREV, remove it. Move - any REG_WAS_0 note on INSN to PREV. */ - note = find_reg_note (prev, REG_WAS_0, NULL_RTX); - if (note) - remove_note (prev, note); - - note = find_reg_note (insn, REG_WAS_0, NULL_RTX); - if (note) - { - remove_note (insn, note); - XEXP (note, 1) = REG_NOTES (prev); - REG_NOTES (prev) = note; - } - - /* If INSN has a REG_EQUAL note, and this note mentions REG0, - then we must delete it, because the value in REG0 has changed. */ - note = find_reg_note (insn, REG_EQUAL, NULL_RTX); - if (note && reg_mentioned_p (dest, XEXP (note, 0))) - remove_note (insn, note); - } - } - - /* If this is a conditional jump insn, record any known equivalences due to - the condition being tested. */ - - last_jump_equiv_class = 0; - if (GET_CODE (insn) == JUMP_INSN - && n_sets == 1 && GET_CODE (x) == SET - && GET_CODE (SET_SRC (x)) == IF_THEN_ELSE) - record_jump_equiv (insn, 0); - -#ifdef HAVE_cc0 - /* If the previous insn set CC0 and this insn no longer references CC0, - delete the previous insn. Here we use the fact that nothing expects CC0 - to be valid over an insn, which is true until the final pass. */ - if (prev_insn && GET_CODE (prev_insn) == INSN - && (tem = single_set (prev_insn)) != 0 - && SET_DEST (tem) == cc0_rtx - && ! reg_mentioned_p (cc0_rtx, x)) - { - PUT_CODE (prev_insn, NOTE); - NOTE_LINE_NUMBER (prev_insn) = NOTE_INSN_DELETED; - NOTE_SOURCE_FILE (prev_insn) = 0; - } - - prev_insn_cc0 = this_insn_cc0; - prev_insn_cc0_mode = this_insn_cc0_mode; -#endif - - prev_insn = insn; -} - -/* Remove from the hash table all expressions that reference memory. */ -static void -invalidate_memory () -{ - register int i; - register struct table_elt *p, *next; - - for (i = 0; i < NBUCKETS; i++) - for (p = table[i]; p; p = next) - { - next = p->next_same_hash; - if (p->in_memory) - remove_from_table (p, i); - } -} - -/* XXX ??? The name of this function bears little resemblance to - what this function actually does. FIXME. */ -static int -note_mem_written (addr) - register rtx addr; -{ - /* Pushing or popping the stack invalidates just the stack pointer. */ - if ((GET_CODE (addr) == PRE_DEC || GET_CODE (addr) == PRE_INC - || GET_CODE (addr) == POST_DEC || GET_CODE (addr) == POST_INC) - && GET_CODE (XEXP (addr, 0)) == REG - && REGNO (XEXP (addr, 0)) == STACK_POINTER_REGNUM) - { - if (REG_TICK (STACK_POINTER_REGNUM) >= 0) - REG_TICK (STACK_POINTER_REGNUM)++; - - /* This should be *very* rare. */ - if (TEST_HARD_REG_BIT (hard_regs_in_table, STACK_POINTER_REGNUM)) - invalidate (stack_pointer_rtx, VOIDmode); - return 1; - } - return 0; -} - -/* Perform invalidation on the basis of everything about an insn - except for invalidating the actual places that are SET in it. - This includes the places CLOBBERed, and anything that might - alias with something that is SET or CLOBBERed. - - X is the pattern of the insn. */ - -static void -invalidate_from_clobbers (x) - rtx x; -{ - if (GET_CODE (x) == CLOBBER) - { - rtx ref = XEXP (x, 0); - if (ref) - { - if (GET_CODE (ref) == REG || GET_CODE (ref) == SUBREG - || GET_CODE (ref) == MEM) - invalidate (ref, VOIDmode); - else if (GET_CODE (ref) == STRICT_LOW_PART - || GET_CODE (ref) == ZERO_EXTRACT) - invalidate (XEXP (ref, 0), GET_MODE (ref)); - } - } - else if (GET_CODE (x) == PARALLEL) - { - register int i; - for (i = XVECLEN (x, 0) - 1; i >= 0; i--) - { - register rtx y = XVECEXP (x, 0, i); - if (GET_CODE (y) == CLOBBER) - { - rtx ref = XEXP (y, 0); - if (GET_CODE (ref) == REG || GET_CODE (ref) == SUBREG - || GET_CODE (ref) == MEM) - invalidate (ref, VOIDmode); - else if (GET_CODE (ref) == STRICT_LOW_PART - || GET_CODE (ref) == ZERO_EXTRACT) - invalidate (XEXP (ref, 0), GET_MODE (ref)); - } - } - } -} - -/* Process X, part of the REG_NOTES of an insn. Look at any REG_EQUAL notes - and replace any registers in them with either an equivalent constant - or the canonical form of the register. If we are inside an address, - only do this if the address remains valid. - - OBJECT is 0 except when within a MEM in which case it is the MEM. - - Return the replacement for X. */ - -static rtx -cse_process_notes (x, object) - rtx x; - rtx object; -{ - enum rtx_code code = GET_CODE (x); - char *fmt = GET_RTX_FORMAT (code); - int i; - - switch (code) - { - case CONST_INT: - case CONST: - case SYMBOL_REF: - case LABEL_REF: - case CONST_DOUBLE: - case PC: - case CC0: - case LO_SUM: - return x; - - case MEM: - XEXP (x, 0) = cse_process_notes (XEXP (x, 0), x); - return x; - - case EXPR_LIST: - case INSN_LIST: - if (REG_NOTE_KIND (x) == REG_EQUAL) - XEXP (x, 0) = cse_process_notes (XEXP (x, 0), NULL_RTX); - if (XEXP (x, 1)) - XEXP (x, 1) = cse_process_notes (XEXP (x, 1), NULL_RTX); - return x; - - case SIGN_EXTEND: - case ZERO_EXTEND: - case SUBREG: - { - rtx new = cse_process_notes (XEXP (x, 0), object); - /* We don't substitute VOIDmode constants into these rtx, - since they would impede folding. */ - if (GET_MODE (new) != VOIDmode) - validate_change (object, &XEXP (x, 0), new, 0); - return x; - } - - case REG: - i = REG_QTY (REGNO (x)); - - /* Return a constant or a constant register. */ - if (REGNO_QTY_VALID_P (REGNO (x)) - && qty_const[i] != 0 - && (CONSTANT_P (qty_const[i]) - || GET_CODE (qty_const[i]) == REG)) - { - rtx new = gen_lowpart_if_possible (GET_MODE (x), qty_const[i]); - if (new) - return new; - } - - /* Otherwise, canonicalize this register. */ - return canon_reg (x, NULL_RTX); - - default: - break; - } - - for (i = 0; i < GET_RTX_LENGTH (code); i++) - if (fmt[i] == 'e') - validate_change (object, &XEXP (x, i), - cse_process_notes (XEXP (x, i), object), 0); - - return x; -} - -/* Find common subexpressions between the end test of a loop and the beginning - of the loop. LOOP_START is the CODE_LABEL at the start of a loop. - - Often we have a loop where an expression in the exit test is used - in the body of the loop. For example "while (*p) *q++ = *p++;". - Because of the way we duplicate the loop exit test in front of the loop, - however, we don't detect that common subexpression. This will be caught - when global cse is implemented, but this is a quite common case. - - This function handles the most common cases of these common expressions. - It is called after we have processed the basic block ending with the - NOTE_INSN_LOOP_END note that ends a loop and the previous JUMP_INSN - jumps to a label used only once. */ - -static void -cse_around_loop (loop_start) - rtx loop_start; -{ - rtx insn; - int i; - struct table_elt *p; - - /* If the jump at the end of the loop doesn't go to the start, we don't - do anything. */ - for (insn = PREV_INSN (loop_start); - insn && (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) >= 0); - insn = PREV_INSN (insn)) - ; - - if (insn == 0 - || GET_CODE (insn) != NOTE - || NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG) - return; - - /* If the last insn of the loop (the end test) was an NE comparison, - we will interpret it as an EQ comparison, since we fell through - the loop. Any equivalences resulting from that comparison are - therefore not valid and must be invalidated. */ - if (last_jump_equiv_class) - for (p = last_jump_equiv_class->first_same_value; p; - p = p->next_same_value) - { - if (GET_CODE (p->exp) == MEM || GET_CODE (p->exp) == REG - || (GET_CODE (p->exp) == SUBREG - && GET_CODE (SUBREG_REG (p->exp)) == REG)) - invalidate (p->exp, VOIDmode); - else if (GET_CODE (p->exp) == STRICT_LOW_PART - || GET_CODE (p->exp) == ZERO_EXTRACT) - invalidate (XEXP (p->exp, 0), GET_MODE (p->exp)); - } - - /* Process insns starting after LOOP_START until we hit a CALL_INSN or - a CODE_LABEL (we could handle a CALL_INSN, but it isn't worth it). - - The only thing we do with SET_DEST is invalidate entries, so we - can safely process each SET in order. It is slightly less efficient - to do so, but we only want to handle the most common cases. - - The gen_move_insn call in cse_set_around_loop may create new pseudos. - These pseudos won't have valid entries in any of the tables indexed - by register number, such as reg_qty. We avoid out-of-range array - accesses by not processing any instructions created after cse started. */ - - for (insn = NEXT_INSN (loop_start); - GET_CODE (insn) != CALL_INSN && GET_CODE (insn) != CODE_LABEL - && INSN_UID (insn) < max_insn_uid - && ! (GET_CODE (insn) == NOTE - && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END); - insn = NEXT_INSN (insn)) - { - if (GET_RTX_CLASS (GET_CODE (insn)) == 'i' - && (GET_CODE (PATTERN (insn)) == SET - || GET_CODE (PATTERN (insn)) == CLOBBER)) - cse_set_around_loop (PATTERN (insn), insn, loop_start); - else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i' - && GET_CODE (PATTERN (insn)) == PARALLEL) - for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--) - if (GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == SET - || GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == CLOBBER) - cse_set_around_loop (XVECEXP (PATTERN (insn), 0, i), insn, - loop_start); - } -} - -/* Process one SET of an insn that was skipped. We ignore CLOBBERs - since they are done elsewhere. This function is called via note_stores. */ - -static void -invalidate_skipped_set (dest, set) - rtx set; - rtx dest; -{ - enum rtx_code code = GET_CODE (dest); - - if (code == MEM - && ! note_mem_written (dest) /* If this is not a stack push ... */ - /* There are times when an address can appear varying and be a PLUS - during this scan when it would be a fixed address were we to know - the proper equivalences. So invalidate all memory if there is - a BLKmode or nonscalar memory reference or a reference to a - variable address. */ - && (MEM_IN_STRUCT_P (dest) || GET_MODE (dest) == BLKmode - || cse_rtx_varies_p (XEXP (dest, 0)))) - { - invalidate_memory (); - return; - } - - if (GET_CODE (set) == CLOBBER -#ifdef HAVE_cc0 - || dest == cc0_rtx -#endif - || dest == pc_rtx) - return; - - if (code == STRICT_LOW_PART || code == ZERO_EXTRACT) - invalidate (XEXP (dest, 0), GET_MODE (dest)); - else if (code == REG || code == SUBREG || code == MEM) - invalidate (dest, VOIDmode); -} - -/* Invalidate all insns from START up to the end of the function or the - next label. This called when we wish to CSE around a block that is - conditionally executed. */ - -static void -invalidate_skipped_block (start) - rtx start; -{ - rtx insn; - - for (insn = start; insn && GET_CODE (insn) != CODE_LABEL; - insn = NEXT_INSN (insn)) - { - if (GET_RTX_CLASS (GET_CODE (insn)) != 'i') - continue; - - if (GET_CODE (insn) == CALL_INSN) - { - if (! CONST_CALL_P (insn)) - invalidate_memory (); - invalidate_for_call (); - } - - invalidate_from_clobbers (PATTERN (insn)); - note_stores (PATTERN (insn), invalidate_skipped_set); - } -} - -/* Used for communication between the following two routines; contains a - value to be checked for modification. */ - -static rtx cse_check_loop_start_value; - -/* If modifying X will modify the value in CSE_CHECK_LOOP_START_VALUE, - indicate that fact by setting CSE_CHECK_LOOP_START_VALUE to 0. */ - -static void -cse_check_loop_start (x, set) - rtx x; - rtx set ATTRIBUTE_UNUSED; -{ - if (cse_check_loop_start_value == 0 - || GET_CODE (x) == CC0 || GET_CODE (x) == PC) - return; - - if ((GET_CODE (x) == MEM && GET_CODE (cse_check_loop_start_value) == MEM) - || reg_overlap_mentioned_p (x, cse_check_loop_start_value)) - cse_check_loop_start_value = 0; -} - -/* X is a SET or CLOBBER contained in INSN that was found near the start of - a loop that starts with the label at LOOP_START. - - If X is a SET, we see if its SET_SRC is currently in our hash table. - If so, we see if it has a value equal to some register used only in the - loop exit code (as marked by jump.c). - - If those two conditions are true, we search backwards from the start of - the loop to see if that same value was loaded into a register that still - retains its value at the start of the loop. - - If so, we insert an insn after the load to copy the destination of that - load into the equivalent register and (try to) replace our SET_SRC with that - register. - - In any event, we invalidate whatever this SET or CLOBBER modifies. */ - -static void -cse_set_around_loop (x, insn, loop_start) - rtx x; - rtx insn; - rtx loop_start; -{ - struct table_elt *src_elt; - - /* If this is a SET, see if we can replace SET_SRC, but ignore SETs that - are setting PC or CC0 or whose SET_SRC is already a register. */ - if (GET_CODE (x) == SET - && GET_CODE (SET_DEST (x)) != PC && GET_CODE (SET_DEST (x)) != CC0 - && GET_CODE (SET_SRC (x)) != REG) - { - src_elt = lookup (SET_SRC (x), - HASH (SET_SRC (x), GET_MODE (SET_DEST (x))), - GET_MODE (SET_DEST (x))); - - if (src_elt) - for (src_elt = src_elt->first_same_value; src_elt; - src_elt = src_elt->next_same_value) - if (GET_CODE (src_elt->exp) == REG && REG_LOOP_TEST_P (src_elt->exp) - && COST (src_elt->exp) < COST (SET_SRC (x))) - { - rtx p, set; - - /* Look for an insn in front of LOOP_START that sets - something in the desired mode to SET_SRC (x) before we hit - a label or CALL_INSN. */ - - for (p = prev_nonnote_insn (loop_start); - p && GET_CODE (p) != CALL_INSN - && GET_CODE (p) != CODE_LABEL; - p = prev_nonnote_insn (p)) - if ((set = single_set (p)) != 0 - && GET_CODE (SET_DEST (set)) == REG - && GET_MODE (SET_DEST (set)) == src_elt->mode - && rtx_equal_p (SET_SRC (set), SET_SRC (x))) - { - /* We now have to ensure that nothing between P - and LOOP_START modified anything referenced in - SET_SRC (x). We know that nothing within the loop - can modify it, or we would have invalidated it in - the hash table. */ - rtx q; - - cse_check_loop_start_value = SET_SRC (x); - for (q = p; q != loop_start; q = NEXT_INSN (q)) - if (GET_RTX_CLASS (GET_CODE (q)) == 'i') - note_stores (PATTERN (q), cse_check_loop_start); - - /* If nothing was changed and we can replace our - SET_SRC, add an insn after P to copy its destination - to what we will be replacing SET_SRC with. */ - if (cse_check_loop_start_value - && validate_change (insn, &SET_SRC (x), - src_elt->exp, 0)) - { - /* If this creates new pseudos, this is unsafe, - because the regno of new pseudo is unsuitable - to index into reg_qty when cse_insn processes - the new insn. Therefore, if a new pseudo was - created, discard this optimization. */ - int nregs = max_reg_num (); - rtx move - = gen_move_insn (src_elt->exp, SET_DEST (set)); - if (nregs != max_reg_num ()) - { - if (! validate_change (insn, &SET_SRC (x), - SET_SRC (set), 0)) - abort (); - } - else - emit_insn_after (move, p); - } - break; - } - } - } - - /* Now invalidate anything modified by X. */ - note_mem_written (SET_DEST (x)); - - /* See comment on similar code in cse_insn for explanation of these tests. */ - if (GET_CODE (SET_DEST (x)) == REG || GET_CODE (SET_DEST (x)) == SUBREG - || GET_CODE (SET_DEST (x)) == MEM) - invalidate (SET_DEST (x), VOIDmode); - else if (GET_CODE (SET_DEST (x)) == STRICT_LOW_PART - || GET_CODE (SET_DEST (x)) == ZERO_EXTRACT) - invalidate (XEXP (SET_DEST (x), 0), GET_MODE (SET_DEST (x))); -} - -/* Find the end of INSN's basic block and return its range, - the total number of SETs in all the insns of the block, the last insn of the - block, and the branch path. - - The branch path indicates which branches should be followed. If a non-zero - path size is specified, the block should be rescanned and a different set - of branches will be taken. The branch path is only used if - FLAG_CSE_FOLLOW_JUMPS or FLAG_CSE_SKIP_BLOCKS is non-zero. - - DATA is a pointer to a struct cse_basic_block_data, defined below, that is - used to describe the block. It is filled in with the information about - the current block. The incoming structure's branch path, if any, is used - to construct the output branch path. */ - -void -cse_end_of_basic_block (insn, data, follow_jumps, after_loop, skip_blocks) - rtx insn; - struct cse_basic_block_data *data; - int follow_jumps; - int after_loop; - int skip_blocks; -{ - rtx p = insn, q; - int nsets = 0; - int low_cuid = INSN_CUID (insn), high_cuid = INSN_CUID (insn); - rtx next = GET_RTX_CLASS (GET_CODE (insn)) == 'i' ? insn : next_real_insn (insn); - int path_size = data->path_size; - int path_entry = 0; - int i; - - /* Update the previous branch path, if any. If the last branch was - previously TAKEN, mark it NOT_TAKEN. If it was previously NOT_TAKEN, - shorten the path by one and look at the previous branch. We know that - at least one branch must have been taken if PATH_SIZE is non-zero. */ - while (path_size > 0) - { - if (data->path[path_size - 1].status != NOT_TAKEN) - { - data->path[path_size - 1].status = NOT_TAKEN; - break; - } - else - path_size--; - } - - /* Scan to end of this basic block. */ - while (p && GET_CODE (p) != CODE_LABEL) - { - /* Don't cse out the end of a loop. This makes a difference - only for the unusual loops that always execute at least once; - all other loops have labels there so we will stop in any case. - Cse'ing out the end of the loop is dangerous because it - might cause an invariant expression inside the loop - to be reused after the end of the loop. This would make it - hard to move the expression out of the loop in loop.c, - especially if it is one of several equivalent expressions - and loop.c would like to eliminate it. - - If we are running after loop.c has finished, we can ignore - the NOTE_INSN_LOOP_END. */ - - if (! after_loop && GET_CODE (p) == NOTE - && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END) - break; - - /* Don't cse over a call to setjmp; on some machines (eg vax) - the regs restored by the longjmp come from - a later time than the setjmp. */ - if (GET_CODE (p) == NOTE - && NOTE_LINE_NUMBER (p) == NOTE_INSN_SETJMP) - break; - - /* A PARALLEL can have lots of SETs in it, - especially if it is really an ASM_OPERANDS. */ - if (GET_RTX_CLASS (GET_CODE (p)) == 'i' - && GET_CODE (PATTERN (p)) == PARALLEL) - nsets += XVECLEN (PATTERN (p), 0); - else if (GET_CODE (p) != NOTE) - nsets += 1; - - /* Ignore insns made by CSE; they cannot affect the boundaries of - the basic block. */ - - if (INSN_UID (p) <= max_uid && INSN_CUID (p) > high_cuid) - high_cuid = INSN_CUID (p); - if (INSN_UID (p) <= max_uid && INSN_CUID (p) < low_cuid) - low_cuid = INSN_CUID (p); - - /* See if this insn is in our branch path. If it is and we are to - take it, do so. */ - if (path_entry < path_size && data->path[path_entry].branch == p) - { - if (data->path[path_entry].status != NOT_TAKEN) - p = JUMP_LABEL (p); - - /* Point to next entry in path, if any. */ - path_entry++; - } - - /* If this is a conditional jump, we can follow it if -fcse-follow-jumps - was specified, we haven't reached our maximum path length, there are - insns following the target of the jump, this is the only use of the - jump label, and the target label is preceded by a BARRIER. - - Alternatively, we can follow the jump if it branches around a - block of code and there are no other branches into the block. - In this case invalidate_skipped_block will be called to invalidate any - registers set in the block when following the jump. */ - - else if ((follow_jumps || skip_blocks) && path_size < PATHLENGTH - 1 - && GET_CODE (p) == JUMP_INSN - && GET_CODE (PATTERN (p)) == SET - && GET_CODE (SET_SRC (PATTERN (p))) == IF_THEN_ELSE - && JUMP_LABEL (p) != 0 - && LABEL_NUSES (JUMP_LABEL (p)) == 1 - && NEXT_INSN (JUMP_LABEL (p)) != 0) - { - for (q = PREV_INSN (JUMP_LABEL (p)); q; q = PREV_INSN (q)) - if ((GET_CODE (q) != NOTE - || NOTE_LINE_NUMBER (q) == NOTE_INSN_LOOP_END - || NOTE_LINE_NUMBER (q) == NOTE_INSN_SETJMP) - && (GET_CODE (q) != CODE_LABEL || LABEL_NUSES (q) != 0)) - break; - - /* If we ran into a BARRIER, this code is an extension of the - basic block when the branch is taken. */ - if (follow_jumps && q != 0 && GET_CODE (q) == BARRIER) - { - /* Don't allow ourself to keep walking around an - always-executed loop. */ - if (next_real_insn (q) == next) - { - p = NEXT_INSN (p); - continue; - } - - /* Similarly, don't put a branch in our path more than once. */ - for (i = 0; i < path_entry; i++) - if (data->path[i].branch == p) - break; - - if (i != path_entry) - break; - - data->path[path_entry].branch = p; - data->path[path_entry++].status = TAKEN; - - /* This branch now ends our path. It was possible that we - didn't see this branch the last time around (when the - insn in front of the target was a JUMP_INSN that was - turned into a no-op). */ - path_size = path_entry; - - p = JUMP_LABEL (p); - /* Mark block so we won't scan it again later. */ - PUT_MODE (NEXT_INSN (p), QImode); - } - /* Detect a branch around a block of code. */ - else if (skip_blocks && q != 0 && GET_CODE (q) != CODE_LABEL) - { - register rtx tmp; - - if (next_real_insn (q) == next) - { - p = NEXT_INSN (p); - continue; - } - - for (i = 0; i < path_entry; i++) - if (data->path[i].branch == p) - break; - - if (i != path_entry) - break; - - /* This is no_labels_between_p (p, q) with an added check for - reaching the end of a function (in case Q precedes P). */ - for (tmp = NEXT_INSN (p); tmp && tmp != q; tmp = NEXT_INSN (tmp)) - if (GET_CODE (tmp) == CODE_LABEL) - break; - - if (tmp == q) - { - data->path[path_entry].branch = p; - data->path[path_entry++].status = AROUND; - - path_size = path_entry; - - p = JUMP_LABEL (p); - /* Mark block so we won't scan it again later. */ - PUT_MODE (NEXT_INSN (p), QImode); - } - } - } - p = NEXT_INSN (p); - } - - data->low_cuid = low_cuid; - data->high_cuid = high_cuid; - data->nsets = nsets; - data->last = p; - - /* If all jumps in the path are not taken, set our path length to zero - so a rescan won't be done. */ - for (i = path_size - 1; i >= 0; i--) - if (data->path[i].status != NOT_TAKEN) - break; - - if (i == -1) - data->path_size = 0; - else - data->path_size = path_size; - - /* End the current branch path. */ - data->path[path_size].branch = 0; -} - -/* Perform cse on the instructions of a function. - F is the first instruction. - NREGS is one plus the highest pseudo-reg number used in the instruction. - - AFTER_LOOP is 1 if this is the cse call done after loop optimization - (only if -frerun-cse-after-loop). - - Returns 1 if jump_optimize should be redone due to simplifications - in conditional jump instructions. */ - -int -cse_main (f, nregs, after_loop, file) - rtx f; - int nregs; - int after_loop; - FILE *file; -{ - struct cse_basic_block_data val; - register rtx insn = f; - register int i; - - cse_jumps_altered = 0; - recorded_label_ref = 0; - constant_pool_entries_cost = 0; - val.path_size = 0; - - init_recog (); - init_alias_analysis (); - - max_reg = nregs; - - max_insn_uid = get_max_uid (); - - reg_next_eqv = (int *) alloca (nregs * sizeof (int)); - reg_prev_eqv = (int *) alloca (nregs * sizeof (int)); - -#ifdef LOAD_EXTEND_OP - - /* Allocate scratch rtl here. cse_insn will fill in the memory reference - and change the code and mode as appropriate. */ - memory_extend_rtx = gen_rtx_ZERO_EXTEND (VOIDmode, NULL_RTX); -#endif - - /* Discard all the free elements of the previous function - since they are allocated in the temporarily obstack. */ - bzero ((char *) table, sizeof table); - free_element_chain = 0; - n_elements_made = 0; - - /* Find the largest uid. */ - - max_uid = get_max_uid (); - uid_cuid = (int *) alloca ((max_uid + 1) * sizeof (int)); - bzero ((char *) uid_cuid, (max_uid + 1) * sizeof (int)); - - /* Compute the mapping from uids to cuids. - CUIDs are numbers assigned to insns, like uids, - except that cuids increase monotonically through the code. - Don't assign cuids to line-number NOTEs, so that the distance in cuids - between two insns is not affected by -g. */ - - for (insn = f, i = 0; insn; insn = NEXT_INSN (insn)) - { - if (GET_CODE (insn) != NOTE - || NOTE_LINE_NUMBER (insn) < 0) - INSN_CUID (insn) = ++i; - else - /* Give a line number note the same cuid as preceding insn. */ - INSN_CUID (insn) = i; - } - - /* Initialize which registers are clobbered by calls. */ - - CLEAR_HARD_REG_SET (regs_invalidated_by_call); - - for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) - if ((call_used_regs[i] - /* Used to check !fixed_regs[i] here, but that isn't safe; - fixed regs are still call-clobbered, and sched can get - confused if they can "live across calls". - - The frame pointer is always preserved across calls. The arg - pointer is if it is fixed. The stack pointer usually is, unless - RETURN_POPS_ARGS, in which case an explicit CLOBBER - will be present. If we are generating PIC code, the PIC offset - table register is preserved across calls. */ - - && i != STACK_POINTER_REGNUM - && i != FRAME_POINTER_REGNUM -#if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM - && i != HARD_FRAME_POINTER_REGNUM -#endif -#if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM - && ! (i == ARG_POINTER_REGNUM && fixed_regs[i]) -#endif -#if defined (PIC_OFFSET_TABLE_REGNUM) && !defined (PIC_OFFSET_TABLE_REG_CALL_CLOBBERED) - && ! (i == PIC_OFFSET_TABLE_REGNUM && flag_pic) -#endif - ) - || global_regs[i]) - SET_HARD_REG_BIT (regs_invalidated_by_call, i); - - /* Loop over basic blocks. - Compute the maximum number of qty's needed for each basic block - (which is 2 for each SET). */ - insn = f; - while (insn) - { - cse_end_of_basic_block (insn, &val, flag_cse_follow_jumps, after_loop, - flag_cse_skip_blocks); - - /* If this basic block was already processed or has no sets, skip it. */ - if (val.nsets == 0 || GET_MODE (insn) == QImode) - { - PUT_MODE (insn, VOIDmode); - insn = (val.last ? NEXT_INSN (val.last) : 0); - val.path_size = 0; - continue; - } - - cse_basic_block_start = val.low_cuid; - cse_basic_block_end = val.high_cuid; - max_qty = val.nsets * 2; - - if (file) - fnotice (file, ";; Processing block from %d to %d, %d sets.\n", - INSN_UID (insn), val.last ? INSN_UID (val.last) : 0, - val.nsets); - - /* Make MAX_QTY bigger to give us room to optimize - past the end of this basic block, if that should prove useful. */ - if (max_qty < 500) - max_qty = 500; - - max_qty += max_reg; - - /* If this basic block is being extended by following certain jumps, - (see `cse_end_of_basic_block'), we reprocess the code from the start. - Otherwise, we start after this basic block. */ - if (val.path_size > 0) - cse_basic_block (insn, val.last, val.path, 0); - else - { - int old_cse_jumps_altered = cse_jumps_altered; - rtx temp; - - /* When cse changes a conditional jump to an unconditional - jump, we want to reprocess the block, since it will give - us a new branch path to investigate. */ - cse_jumps_altered = 0; - temp = cse_basic_block (insn, val.last, val.path, ! after_loop); - if (cse_jumps_altered == 0 - || (flag_cse_follow_jumps == 0 && flag_cse_skip_blocks == 0)) - insn = temp; - - cse_jumps_altered |= old_cse_jumps_altered; - } - -#ifdef USE_C_ALLOCA - alloca (0); -#endif - } - - /* Tell refers_to_mem_p that qty_const info is not available. */ - qty_const = 0; - - if (max_elements_made < n_elements_made) - max_elements_made = n_elements_made; - - return cse_jumps_altered || recorded_label_ref; -} - -/* Process a single basic block. FROM and TO and the limits of the basic - block. NEXT_BRANCH points to the branch path when following jumps or - a null path when not following jumps. - - AROUND_LOOP is non-zero if we are to try to cse around to the start of a - loop. This is true when we are being called for the last time on a - block and this CSE pass is before loop.c. */ - -static rtx -cse_basic_block (from, to, next_branch, around_loop) - register rtx from, to; - struct branch_path *next_branch; - int around_loop; -{ - register rtx insn; - int to_usage = 0; - rtx libcall_insn = NULL_RTX; - int num_insns = 0; - - /* Each of these arrays is undefined before max_reg, so only allocate - the space actually needed and adjust the start below. */ - - qty_first_reg = (int *) alloca ((max_qty - max_reg) * sizeof (int)); - qty_last_reg = (int *) alloca ((max_qty - max_reg) * sizeof (int)); - qty_mode= (enum machine_mode *) alloca ((max_qty - max_reg) * sizeof (enum machine_mode)); - qty_const = (rtx *) alloca ((max_qty - max_reg) * sizeof (rtx)); - qty_const_insn = (rtx *) alloca ((max_qty - max_reg) * sizeof (rtx)); - qty_comparison_code - = (enum rtx_code *) alloca ((max_qty - max_reg) * sizeof (enum rtx_code)); - qty_comparison_qty = (int *) alloca ((max_qty - max_reg) * sizeof (int)); - qty_comparison_const = (rtx *) alloca ((max_qty - max_reg) * sizeof (rtx)); - - qty_first_reg -= max_reg; - qty_last_reg -= max_reg; - qty_mode -= max_reg; - qty_const -= max_reg; - qty_const_insn -= max_reg; - qty_comparison_code -= max_reg; - qty_comparison_qty -= max_reg; - qty_comparison_const -= max_reg; - - new_basic_block (); - - /* TO might be a label. If so, protect it from being deleted. */ - if (to != 0 && GET_CODE (to) == CODE_LABEL) - ++LABEL_NUSES (to); - - for (insn = from; insn != to; insn = NEXT_INSN (insn)) - { - register enum rtx_code code = GET_CODE (insn); - - /* If we have processed 1,000 insns, flush the hash table to - avoid extreme quadratic behavior. We must not include NOTEs - in the count since there may be more or them when generating - debugging information. If we clear the table at different - times, code generated with -g -O might be different than code - generated with -O but not -g. - - ??? This is a real kludge and needs to be done some other way. - Perhaps for 2.9. */ - if (code != NOTE && num_insns++ > 1000) - { - flush_hash_table (); - num_insns = 0; - } - - /* See if this is a branch that is part of the path. If so, and it is - to be taken, do so. */ - if (next_branch->branch == insn) - { - enum taken status = next_branch++->status; - if (status != NOT_TAKEN) - { - if (status == TAKEN) - record_jump_equiv (insn, 1); - else - invalidate_skipped_block (NEXT_INSN (insn)); - - /* Set the last insn as the jump insn; it doesn't affect cc0. - Then follow this branch. */ -#ifdef HAVE_cc0 - prev_insn_cc0 = 0; -#endif - prev_insn = insn; - insn = JUMP_LABEL (insn); - continue; - } - } - - if (GET_MODE (insn) == QImode) - PUT_MODE (insn, VOIDmode); - - if (GET_RTX_CLASS (code) == 'i') - { - rtx p; - - /* Process notes first so we have all notes in canonical forms when - looking for duplicate operations. */ - - if (REG_NOTES (insn)) - REG_NOTES (insn) = cse_process_notes (REG_NOTES (insn), NULL_RTX); - - /* Track when we are inside in LIBCALL block. Inside such a block, - we do not want to record destinations. The last insn of a - LIBCALL block is not considered to be part of the block, since - its destination is the result of the block and hence should be - recorded. */ - - if ((p = find_reg_note (insn, REG_LIBCALL, NULL_RTX))) - libcall_insn = XEXP (p, 0); - else if (find_reg_note (insn, REG_RETVAL, NULL_RTX)) - libcall_insn = NULL_RTX; - - cse_insn (insn, libcall_insn); - } - - /* If INSN is now an unconditional jump, skip to the end of our - basic block by pretending that we just did the last insn in the - basic block. If we are jumping to the end of our block, show - that we can have one usage of TO. */ - - if (simplejump_p (insn)) - { - if (to == 0) - return 0; - - if (JUMP_LABEL (insn) == to) - to_usage = 1; - - /* Maybe TO was deleted because the jump is unconditional. - If so, there is nothing left in this basic block. */ - /* ??? Perhaps it would be smarter to set TO - to whatever follows this insn, - and pretend the basic block had always ended here. */ - if (INSN_DELETED_P (to)) - break; - - insn = PREV_INSN (to); - } - - /* See if it is ok to keep on going past the label - which used to end our basic block. Remember that we incremented - the count of that label, so we decrement it here. If we made - a jump unconditional, TO_USAGE will be one; in that case, we don't - want to count the use in that jump. */ - - if (to != 0 && NEXT_INSN (insn) == to - && GET_CODE (to) == CODE_LABEL && --LABEL_NUSES (to) == to_usage) - { - struct cse_basic_block_data val; - rtx prev; - - insn = NEXT_INSN (to); - - /* If TO was the last insn in the function, we are done. */ - if (insn == 0) - return 0; - - /* If TO was preceded by a BARRIER we are done with this block - because it has no continuation. */ - prev = prev_nonnote_insn (to); - if (prev && GET_CODE (prev) == BARRIER) - return insn; - - /* Find the end of the following block. Note that we won't be - following branches in this case. */ - to_usage = 0; - val.path_size = 0; - cse_end_of_basic_block (insn, &val, 0, 0, 0); - - /* If the tables we allocated have enough space left - to handle all the SETs in the next basic block, - continue through it. Otherwise, return, - and that block will be scanned individually. */ - if (val.nsets * 2 + next_qty > max_qty) - break; - - cse_basic_block_start = val.low_cuid; - cse_basic_block_end = val.high_cuid; - to = val.last; - - /* Prevent TO from being deleted if it is a label. */ - if (to != 0 && GET_CODE (to) == CODE_LABEL) - ++LABEL_NUSES (to); - - /* Back up so we process the first insn in the extension. */ - insn = PREV_INSN (insn); - } - } - - if (next_qty > max_qty) - abort (); - - /* If we are running before loop.c, we stopped on a NOTE_INSN_LOOP_END, and - the previous insn is the only insn that branches to the head of a loop, - we can cse into the loop. Don't do this if we changed the jump - structure of a loop unless we aren't going to be following jumps. */ - - if ((cse_jumps_altered == 0 - || (flag_cse_follow_jumps == 0 && flag_cse_skip_blocks == 0)) - && around_loop && to != 0 - && GET_CODE (to) == NOTE && NOTE_LINE_NUMBER (to) == NOTE_INSN_LOOP_END - && GET_CODE (PREV_INSN (to)) == JUMP_INSN - && JUMP_LABEL (PREV_INSN (to)) != 0 - && LABEL_NUSES (JUMP_LABEL (PREV_INSN (to))) == 1) - cse_around_loop (JUMP_LABEL (PREV_INSN (to))); - - return to ? NEXT_INSN (to) : 0; -} - -/* Count the number of times registers are used (not set) in X. - COUNTS is an array in which we accumulate the count, INCR is how much - we count each register usage. - - Don't count a usage of DEST, which is the SET_DEST of a SET which - contains X in its SET_SRC. This is because such a SET does not - modify the liveness of DEST. */ - -static void -count_reg_usage (x, counts, dest, incr) - rtx x; - int *counts; - rtx dest; - int incr; -{ - enum rtx_code code; - char *fmt; - int i, j; - - if (x == 0) - return; - - switch (code = GET_CODE (x)) - { - case REG: - if (x != dest) - counts[REGNO (x)] += incr; - return; - - case PC: - case CC0: - case CONST: - case CONST_INT: - case CONST_DOUBLE: - case SYMBOL_REF: - case LABEL_REF: - return; - - case CLOBBER: - /* If we are clobbering a MEM, mark any registers inside the address - as being used. */ - if (GET_CODE (XEXP (x, 0)) == MEM) - count_reg_usage (XEXP (XEXP (x, 0), 0), counts, NULL_RTX, incr); - return; - - case SET: - /* Unless we are setting a REG, count everything in SET_DEST. */ - if (GET_CODE (SET_DEST (x)) != REG) - count_reg_usage (SET_DEST (x), counts, NULL_RTX, incr); - - /* If SRC has side-effects, then we can't delete this insn, so the - usage of SET_DEST inside SRC counts. - - ??? Strictly-speaking, we might be preserving this insn - because some other SET has side-effects, but that's hard - to do and can't happen now. */ - count_reg_usage (SET_SRC (x), counts, - side_effects_p (SET_SRC (x)) ? NULL_RTX : SET_DEST (x), - incr); - return; - - case CALL_INSN: - count_reg_usage (CALL_INSN_FUNCTION_USAGE (x), counts, NULL_RTX, incr); - - /* ... falls through ... */ - case INSN: - case JUMP_INSN: - count_reg_usage (PATTERN (x), counts, NULL_RTX, incr); - - /* Things used in a REG_EQUAL note aren't dead since loop may try to - use them. */ - - count_reg_usage (REG_NOTES (x), counts, NULL_RTX, incr); - return; - - case EXPR_LIST: - case INSN_LIST: - if (REG_NOTE_KIND (x) == REG_EQUAL - || (REG_NOTE_KIND (x) != REG_NONNEG && GET_CODE (XEXP (x,0)) == USE)) - count_reg_usage (XEXP (x, 0), counts, NULL_RTX, incr); - count_reg_usage (XEXP (x, 1), counts, NULL_RTX, incr); - return; - - default: - break; - } - - fmt = GET_RTX_FORMAT (code); - for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) - { - if (fmt[i] == 'e') - count_reg_usage (XEXP (x, i), counts, dest, incr); - else if (fmt[i] == 'E') - for (j = XVECLEN (x, i) - 1; j >= 0; j--) - count_reg_usage (XVECEXP (x, i, j), counts, dest, incr); - } -} - -/* Scan all the insns and delete any that are dead; i.e., they store a register - that is never used or they copy a register to itself. - - This is used to remove insns made obviously dead by cse, loop or other - optimizations. It improves the heuristics in loop since it won't try to - move dead invariants out of loops or make givs for dead quantities. The - remaining passes of the compilation are also sped up. */ - -void -delete_trivially_dead_insns (insns, nreg) - rtx insns; - int nreg; -{ - int *counts = (int *) alloca (nreg * sizeof (int)); - rtx insn, prev; -#ifdef HAVE_cc0 - rtx tem; -#endif - int i; - int in_libcall = 0, dead_libcall = 0; - - /* First count the number of times each register is used. */ - bzero ((char *) counts, sizeof (int) * nreg); - for (insn = next_real_insn (insns); insn; insn = next_real_insn (insn)) - count_reg_usage (insn, counts, NULL_RTX, 1); - - /* Go from the last insn to the first and delete insns that only set unused - registers or copy a register to itself. As we delete an insn, remove - usage counts for registers it uses. */ - for (insn = prev_real_insn (get_last_insn ()); insn; insn = prev) - { - int live_insn = 0; - rtx note; - - prev = prev_real_insn (insn); - - /* Don't delete any insns that are part of a libcall block unless - we can delete the whole libcall block. - - Flow or loop might get confused if we did that. Remember - that we are scanning backwards. */ - if (find_reg_note (insn, REG_RETVAL, NULL_RTX)) - { - in_libcall = 1; - live_insn = 1; - dead_libcall = 0; - - /* See if there's a REG_EQUAL note on this insn and try to - replace the source with the REG_EQUAL expression. - - We assume that insns with REG_RETVALs can only be reg->reg - copies at this point. */ - note = find_reg_note (insn, REG_EQUAL, NULL_RTX); - if (note) - { - rtx set = single_set (insn); - if (set - && validate_change (insn, &SET_SRC (set), XEXP (note, 0), 0)) - { - remove_note (insn, - find_reg_note (insn, REG_RETVAL, NULL_RTX)); - dead_libcall = 1; - } - } - } - else if (in_libcall) - live_insn = ! dead_libcall; - else if (GET_CODE (PATTERN (insn)) == SET) - { - if (GET_CODE (SET_DEST (PATTERN (insn))) == REG - && SET_DEST (PATTERN (insn)) == SET_SRC (PATTERN (insn))) - ; - -#ifdef HAVE_cc0 - else if (GET_CODE (SET_DEST (PATTERN (insn))) == CC0 - && ! side_effects_p (SET_SRC (PATTERN (insn))) - && ((tem = next_nonnote_insn (insn)) == 0 - || GET_RTX_CLASS (GET_CODE (tem)) != 'i' - || ! reg_referenced_p (cc0_rtx, PATTERN (tem)))) - ; -#endif - else if (GET_CODE (SET_DEST (PATTERN (insn))) != REG - || REGNO (SET_DEST (PATTERN (insn))) < FIRST_PSEUDO_REGISTER - || counts[REGNO (SET_DEST (PATTERN (insn)))] != 0 - || side_effects_p (SET_SRC (PATTERN (insn)))) - live_insn = 1; - } - else if (GET_CODE (PATTERN (insn)) == PARALLEL) - for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--) - { - rtx elt = XVECEXP (PATTERN (insn), 0, i); - - if (GET_CODE (elt) == SET) - { - if (GET_CODE (SET_DEST (elt)) == REG - && SET_DEST (elt) == SET_SRC (elt)) - ; - -#ifdef HAVE_cc0 - else if (GET_CODE (SET_DEST (elt)) == CC0 - && ! side_effects_p (SET_SRC (elt)) - && ((tem = next_nonnote_insn (insn)) == 0 - || GET_RTX_CLASS (GET_CODE (tem)) != 'i' - || ! reg_referenced_p (cc0_rtx, PATTERN (tem)))) - ; -#endif - else if (GET_CODE (SET_DEST (elt)) != REG - || REGNO (SET_DEST (elt)) < FIRST_PSEUDO_REGISTER - || counts[REGNO (SET_DEST (elt))] != 0 - || side_effects_p (SET_SRC (elt))) - live_insn = 1; - } - else if (GET_CODE (elt) != CLOBBER && GET_CODE (elt) != USE) - live_insn = 1; - } - else - live_insn = 1; - - /* If this is a dead insn, delete it and show registers in it aren't - being used. */ - - if (! live_insn) - { - count_reg_usage (insn, counts, NULL_RTX, -1); - delete_insn (insn); - } - - if (find_reg_note (insn, REG_LIBCALL, NULL_RTX)) - { - in_libcall = 0; - dead_libcall = 0; - } - } -} |