diff options
author | Niklas Hallqvist <niklas@cvs.openbsd.org> | 1995-12-20 01:06:22 +0000 |
---|---|---|
committer | Niklas Hallqvist <niklas@cvs.openbsd.org> | 1995-12-20 01:06:22 +0000 |
commit | c482518380683ee38d14024c1e362a0d681cf967 (patch) | |
tree | e69b4f6d3fee3aced20a41f3fdf543fc1c77fb5d /gnu/usr.bin/gcc/cse.c | |
parent | 76a62188d0db49c65b696d474c855a799fd96dce (diff) |
FSF GCC version 2.7.2
Diffstat (limited to 'gnu/usr.bin/gcc/cse.c')
-rw-r--r-- | gnu/usr.bin/gcc/cse.c | 8779 |
1 files changed, 8779 insertions, 0 deletions
diff --git a/gnu/usr.bin/gcc/cse.c b/gnu/usr.bin/gcc/cse.c new file mode 100644 index 00000000000..efd05dedaf9 --- /dev/null +++ b/gnu/usr.bin/gcc/cse.c @@ -0,0 +1,8779 @@ +/* Common subexpression elimination for GNU compiler. + Copyright (C) 1987, 88, 89, 92, 93, 94, 1995 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" +/* Must precede rtl.h for FFS. */ +#include <stdio.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 <setjmp.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; so, at each label, we forget all that is + known and start fresh. This can be described as processing each + basic block separately. Note, however, that these are not quite + the same as the basic blocks found by a later pass and used for + data flow analysis and register packing. We do not need to start fresh + after a conditional jump instruction if there is no label there. + + 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; + +/* 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) (pseudo) 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 (pseudo) register number, gives the quantity number + of the register's current contents. */ + +static int *reg_qty; + +/* Index by (pseudo) register number, gives the number of the next (or + previous) (pseudo) 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; + +/* Index by (pseudo) register number, gives the number of times + that register has been altered in the current basic block. */ + +static int *reg_tick; + +/* Index by (pseudo) register number, gives 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. + If this is -1, no expressions containing this register have been + entered in the table. */ + +static int *reg_in_table; + +/* 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; + +/* Two vectors of ints: + one containing max_reg -1's; the other max_reg + 500 (an approximation + for max_qty) elements where element i contains i. + These are used to initialize various other vectors fast. */ + +static int *all_minus_one; +static int *consec_ints; + +/* 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) \ + : rtx_cost (X, SET) * 2) + +/* 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)) + +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; + +/* Bits describing what kind of values in memory must be invalidated + for a particular instruction. If all three bits are zero, + no memory refs need to be invalidated. Each bit is more powerful + than the preceding ones, and if a bit is set then the preceding + bits are also set. + + Here is how the bits are set: + Pushing onto the stack invalidates only the stack pointer, + writing at a fixed address invalidates only variable addresses, + writing in a structure element at variable address + invalidates all but scalar variables, + and writing in anything else at variable address invalidates everything. */ + +struct write_data +{ + int sp : 1; /* Invalidate stack pointer. */ + int var : 1; /* Invalidate variable addresses. */ + int nonscalar : 1; /* Invalidate all but scalar variables. */ + int all : 1; /* Invalidate all memory refs. */ +}; + +/* 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))) + +/* 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))) + +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 void remove_invalid_refs PROTO((int)); +static void rehash_using_reg PROTO((rtx)); +static void invalidate_memory PROTO((struct write_data *)); +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 int refers_to_mem_p PROTO((rtx, rtx, HOST_WIDE_INT, + HOST_WIDE_INT)); +static int cse_rtx_addr_varies_p PROTO((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, int)); +static void note_mem_written PROTO((rtx, struct write_data *)); +static void invalidate_from_clobbers PROTO((struct write_data *, 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 int rtx_equal_function_value_matters; + +/* 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. */ + +/* 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; +{ + 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 + CONST_COSTS (x, code, outer_code); + } + + /* 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; +} + +/* 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; + + bzero ((char *) reg_tick, max_reg * sizeof (int)); + + bcopy ((char *) all_minus_one, (char *) reg_in_table, + max_reg * sizeof (int)); + bcopy ((char *) consec_ints, (char *) reg_qty, max_reg * sizeof (int)); + 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 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)))) + { + insert_regs (SUBREG_REG (x), NULL_PTR, 0); + mention_regs (SUBREG_REG (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 (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; + } + } +} + +/* 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; + rtx base; + HOST_WIDE_INT start, end; + + /* 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 it's 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; + } + + /* 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); + + set_nonvarying_address_components (XEXP (x, 0), GET_MODE_SIZE (full_mode), + &base, &start, &end); + + for (i = 0; i < NBUCKETS; i++) + { + register struct table_elt *next; + for (p = table[i]; p; p = next) + { + next = p->next_same_hash; + if (refers_to_mem_p (p->exp, base, start, end)) + 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); + } +} + +/* 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; +{ + 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 all expressions that reference memory, + or some of them as specified by *WRITES. */ + +static void +invalidate_memory (writes) + struct write_data *writes; +{ + register int i; + register struct table_elt *p, *next; + int all = writes->all; + int nonscalar = writes->nonscalar; + + for (i = 0; i < NBUCKETS; i++) + for (p = table[i]; p; p = next) + { + next = p->next_same_hash; + if (p->in_memory + && (all + || (nonscalar && p->in_struct) + || cse_rtx_addr_varies_p (p->exp))) + remove_from_table (p, i); + } +} + +/* 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 (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. + On all machines, we can't record any global registers. */ + + if (regno < FIRST_PSEUDO_REGISTER + && (global_regs[regno] +#ifdef SMALL_REGISTER_CLASSES + || (! fixed_regs[regno] + && regno != FRAME_POINTER_REGNUM + && regno != HARD_FRAME_POINTER_REGNUM + && regno != ARG_POINTER_REGNUM + && regno != STACK_POINTER_REGNUM) +#endif + )) + { + do_not_record = 1; + return 0; + } + hash += ((unsigned) REG << 7) + (unsigned) reg_qty[regno]; + return hash; + } + + case CONST_INT: + { + unsigned HOST_WIDE_INT tem = INTVAL (x); + hash += ((unsigned) CONST_INT << 7) + (unsigned) mode + tem; + return hash; + } + + case CONST_DOUBLE: + /* This is like the general case, except that it only counts + the integers representing the constant. */ + hash += (unsigned) code + (unsigned) GET_MODE (x); + if (GET_MODE (x) != VOIDmode) + for (i = 2; i < GET_RTX_LENGTH (CONST_DOUBLE); i++) + { + unsigned tem = XINT (x, i); + hash += tem; + } + else + hash += ((unsigned) CONST_DOUBLE_LOW (x) + + (unsigned) CONST_DOUBLE_HIGH (x)); + return hash; + + /* Assume there is only one rtx object for any given label. */ + case LABEL_REF: + hash + += ((unsigned) LABEL_REF << 7) + (unsigned HOST_WIDE_INT) XEXP (x, 0); + return hash; + + case SYMBOL_REF: + hash + += ((unsigned) SYMBOL_REF << 7) + (unsigned HOST_WIDE_INT) XSTR (x, 0); + return hash; + + case MEM: + if (MEM_VOLATILE_P (x)) + { + do_not_record = 1; + return 0; + } + if (! RTX_UNCHANGING_P (x)) + { + 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; + } + } + + 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 + 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 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))); + } + + /* 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; + + /* 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; + } + + 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 iff any subexpression of X refers to memory + at an address of BASE plus some offset + such that any of the bytes' offsets fall between START (inclusive) + and END (exclusive). + + The value is undefined if X is a varying address (as determined by + cse_rtx_addr_varies_p). This function is not used in such cases. + + When used in the cse pass, `qty_const' is nonzero, and it is used + to treat an address that is a register with a known constant value + as if it were that constant value. + In the loop pass, `qty_const' is zero, so this is not done. */ + +static int +refers_to_mem_p (x, base, start, end) + rtx x, base; + HOST_WIDE_INT start, end; +{ + register HOST_WIDE_INT i; + register enum rtx_code code; + register char *fmt; + + repeat: + if (x == 0) + return 0; + + code = GET_CODE (x); + if (code == MEM) + { + register rtx addr = XEXP (x, 0); /* Get the address. */ + rtx mybase; + HOST_WIDE_INT mystart, myend; + + set_nonvarying_address_components (addr, GET_MODE_SIZE (GET_MODE (x)), + &mybase, &mystart, &myend); + + + /* refers_to_mem_p is never called with varying addresses. + If the base addresses are not equal, there is no chance + of the memory addresses conflicting. */ + if (! rtx_equal_p (mybase, base)) + return 0; + + return myend > start && mystart < end; + } + + /* 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_mem_p (XEXP (x, i), base, start, end)) + return 1; + } + else if (fmt[i] == 'E') + { + int j; + for (j = 0; j < XVECLEN (x, i); j++) + if (refers_to_mem_p (XVECEXP (x, i, j), base, start, end)) + return 1; + } + + return 0; +} + +/* Nonzero if X refers to memory at a varying address; + except that a register which has at the moment a known constant value + isn't considered variable. */ + +static int +cse_rtx_addr_varies_p (x) + 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) == MEM + && 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))]] != 0) + return 0; + + if (GET_CODE (x) == MEM + && GET_CODE (XEXP (x, 0)) == PLUS + && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT + && GET_CODE (XEXP (XEXP (x, 0), 0)) == REG + && REGNO_QTY_VALID_P (REGNO (XEXP (XEXP (x, 0), 0))) + && (GET_MODE (XEXP (XEXP (x, 0), 0)) + == qty_mode[reg_qty[REGNO (XEXP (XEXP (x, 0), 0))]]) + && qty_const[reg_qty[REGNO (XEXP (XEXP (x, 0), 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) == MEM + && GET_CODE (XEXP (x, 0)) == PLUS + && GET_CODE (XEXP (XEXP (x, 0), 0)) == REG + && GET_CODE (XEXP (XEXP (x, 0), 1)) == REG + && REGNO_QTY_VALID_P (REGNO (XEXP (XEXP (x, 0), 0))) + && (GET_MODE (XEXP (XEXP (x, 0), 0)) + == qty_mode[reg_qty[REGNO (XEXP (XEXP (x, 0), 0))]]) + && qty_const[reg_qty[REGNO (XEXP (XEXP (x, 0), 0))]] + && REGNO_QTY_VALID_P (REGNO (XEXP (XEXP (x, 0), 1))) + && (GET_MODE (XEXP (XEXP (x, 0), 1)) + == qty_mode[reg_qty[REGNO (XEXP (XEXP (x, 0), 1))]]) + && qty_const[reg_qty[REGNO (XEXP (XEXP (x, 0), 1))]]) + return 0; + + return rtx_addr_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)); + } + } + + 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); + + /* 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_n_dups[recog_memoized (insn)] > 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 with 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, *p; + rtx addr = *loc; + int our_cost; + int found_better = 1; + 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)) + || 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 + && validate_change (insn, loc, fold_rtx (addr, insn), 0)) + addr = *loc; + + /* 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) + { + 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 = 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 + && (GET_CODE (p->exp) == REG + || exp_equiv_p (p->exp, p->exp, 1, 0)) + && (ADDRESS_COST (p->exp) < best_addr_cost + || (ADDRESS_COST (p->exp) == best_addr_cost + && (p->cost + 1) >> 1 > best_rtx_cost))) + { + found_better = 1; + best_addr_cost = 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 = 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 ((ADDRESS_COST (new) < best_addr_cost + || (ADDRESS_COST (new) == best_addr_cost + && (COST (new) + 1) >> 1 > best_rtx_cost))) + { + found_better = 1; + best_addr_cost = 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); +#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); +#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; + + 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 + } + + 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 + 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 + && ! 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; + } + } + + /* 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 (code, mode, op0, op1); +} + +/* 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) + { + REAL_VALUE_TYPE d0, d1; + jmp_buf handler; + + if (setjmp (handler)) + return 0; + + set_float_handler (handler); + REAL_VALUE_FROM_CONST_DOUBLE (d0, op0); + REAL_VALUE_FROM_CONST_DOUBLE (d1, op1); + equal = REAL_VALUES_EQUAL (d0, d1); + op0lt = op0ltu = REAL_VALUES_LESS (d0, d1); + op1lt = op1ltu = REAL_VALUES_LESS (d1, d0); + set_float_handler (NULL_PTR); + } +#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 = 0, 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 = 0, 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; + } + + 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; + } + + 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; + 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: + 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); + + /* 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. */ + return gen_rtx (CONST, GET_MODE (new), new); + } + } + } + + return x; + } + } + + 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; + } + } + } + + 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 negative constant since we might then alternate between + chosing positive and negative constants. Having the positive + constant previously-used is the more common case. */ + if (const_arg1 && GET_CODE (const_arg1) == CONST_INT + && INTVAL (const_arg1) < 0 && 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) + && (0 +#if defined(HAVE_PRE_INCREMENT) || defined(HAVE_POST_INCREMENT) + || exact_log2 (INTVAL (const_arg1)) >= 0 +#endif +#if defined(HAVE_PRE_DECREMENT) || defined(HAVE_POST_DECREMENT) + || exact_log2 (- INTVAL (const_arg1)) >= 0 +#endif + )) + 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); + } + } + + 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; + } + + 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; + MEM_VOLATILE_P (new) = MEM_VOLATILE_P (x); + RTX_UNCHANGING_P (new) = RTX_UNCHANGING_P (x); + MEM_IN_STRUCT_P (new) = MEM_IN_STRUCT_P (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 IN_LIBCALL_BLOCK is nonzero, don't record any equivalence made in + the insn. */ + +/* 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, in_libcall_block) + rtx insn; + int in_libcall_block; +{ + register rtx x = PATTERN (insn); + register int i; + rtx tem; + register int n_sets = 0; + + /* Records what this insn does to set CC0. */ + rtx this_insn_cc0 = 0; + enum machine_mode this_insn_cc0_mode; + struct write_data writes_memory; + static struct write_data init = {0, 0, 0, 0}; + + 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; + writes_memory = init; + + /* 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, take note of that, + and 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); + note_mem_written (XEXP (y, 0), &writes_memory); + } + } + 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); + note_mem_written (XEXP (x, 0), &writes_memory); + } + } + + /* 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); + + if ((GET_CODE (new) == REG && GET_CODE (src) == REG + && ((REGNO (new) < FIRST_PSEUDO_REGISTER) + != (REGNO (src) < FIRST_PSEUDO_REGISTER))) + || insn_n_dups[recog_memoized (insn)] > 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 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; + + 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; + + /* Skip invalid entries. */ + while (elt && GET_CODE (elt->exp) != REG + && ! exp_equiv_p (elt->exp, elt->exp, 1, 0)) + elt = elt->next_same_value; + + 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. */ + + 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)) + { + /* 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) + { + 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)]]; + + src = SET_SRC (sets[i].rtl) + = first >= FIRST_PSEUDO_REGISTER ? regno_reg_rtx[first] + : gen_rtx (REG, GET_MODE (src), first); + + /* 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. */ + if (n_sets == 1 && src_const && GET_CODE (dest) == REG + && GET_CODE (src_const) != REG) + { + tem = find_reg_note (insn, REG_EQUAL, NULL_RTX); + + /* 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) + { + dest = fold_rtx (dest, insn); + + /* Decide whether we invalidate everything in memory, + or just things at non-fixed places. + Writing a large aggregate must invalidate everything + because we don't know how long it is. */ + note_mem_written (dest, &writes_memory); + } + + /* 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. */ + --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))++; + delete_insn (insn); + 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 that we've converted this jump to an unconditional jump, + there is dead code after it. Delete the dead code until we + reach a BARRIER, the end of the function, or a label. Do + not delete NOTEs except for NOTE_INSN_DELETED since later + phases assume these notes are retained. */ + + p = insn; + + while (NEXT_INSN (p) != 0 + && GET_CODE (NEXT_INSN (p)) != BARRIER + && GET_CODE (NEXT_INSN (p)) != CODE_LABEL) + { + if (GET_CODE (NEXT_INSN (p)) != NOTE + || NOTE_LINE_NUMBER (NEXT_INSN (p)) == NOTE_INSN_DELETED) + delete_insn (NEXT_INSN (p)); + else + p = NEXT_INSN (p); + } + + /* If we don't have a BARRIER immediately after INSN, put one there. + Much code assumes that there are no NOTEs between a JUMP_INSN and + BARRIER. */ + + if (NEXT_INSN (insn) == 0 + || GET_CODE (NEXT_INSN (insn)) != BARRIER) + emit_barrier_before (NEXT_INSN (insn)); + + /* We might have two BARRIERs separated by notes. Delete the second + one if so. */ + + if (p != insn && NEXT_INSN (p) != 0 + && GET_CODE (NEXT_INSN (p)) == BARRIER) + delete_insn (NEXT_INSN (p)); + + 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); + + if (sets[i].src_elt == 0) + { + 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 (&writes_memory, x); + + /* Some registers are invalidated by subroutine calls. Memory is + invalidated by non-constant calls. */ + + if (GET_CODE (insn) == CALL_INSN) + { + static struct write_data everything = {0, 1, 1, 1}; + + if (! CONST_CALL_P (insn)) + invalidate_memory (&everything); + 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 && ! writes_memory.all + && ! cse_rtx_addr_varies_p (dest))) + invalidate (dest, VOIDmode); + else if (GET_CODE (dest) == STRICT_LOW_PART + || GET_CODE (dest) == ZERO_EXTRACT) + invalidate (XEXP (dest, 0), GET_MODE (dest)); + } + + /* 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 && GET_CODE (SET_DEST (sets[i].rtl)) != REG) + mention_regs (SET_DEST (sets[i].rtl)); + + /* 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); + 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 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. */ + || in_libcall_block + /* 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)); + } + + 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)); + + 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; + } + } + } + + /* 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. */ + + 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)))) + { + 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; +} + +/* Store 1 in *WRITES_PTR for those categories of memory ref + that must be invalidated when the expression WRITTEN is stored in. + If WRITTEN is null, say everything must be invalidated. */ + +static void +note_mem_written (written, writes_ptr) + rtx written; + struct write_data *writes_ptr; +{ + static struct write_data everything = {0, 1, 1, 1}; + + if (written == 0) + *writes_ptr = everything; + else if (GET_CODE (written) == MEM) + { + /* Pushing or popping the stack invalidates just the stack pointer. */ + rtx addr = XEXP (written, 0); + 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) + { + writes_ptr->sp = 1; + return; + } + else if (GET_MODE (written) == BLKmode) + *writes_ptr = everything; + /* (mem (scratch)) means clobber everything. */ + else if (GET_CODE (addr) == SCRATCH) + *writes_ptr = everything; + else if (cse_rtx_addr_varies_p (written)) + { + /* A varying address that is a sum indicates an array element, + and that's just as good as a structure element + in implying that we need not invalidate scalar variables. + However, we must allow QImode aliasing of scalars, because the + ANSI C standard allows character pointers to alias anything. */ + if (! ((MEM_IN_STRUCT_P (written) + || GET_CODE (XEXP (written, 0)) == PLUS) + && GET_MODE (written) != QImode)) + writes_ptr->all = 1; + writes_ptr->nonscalar = 1; + } + writes_ptr->var = 1; + } +} + +/* 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. + + W points to the writes_memory for this insn, a struct write_data + saying which kinds of memory references must be invalidated. + X is the pattern of the insn. */ + +static void +invalidate_from_clobbers (w, x) + struct write_data *w; + rtx x; +{ + /* If W->var is not set, W specifies no action. + If W->all is set, this step gets all memory refs + so they can be ignored in the rest of this function. */ + if (w->var) + invalidate_memory (w); + + if (w->sp) + { + 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); + } + + 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 && ! w->all)) + 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 (ref) + { + if (GET_CODE (ref) == REG || GET_CODE (ref) == SUBREG + || (GET_CODE (ref) == MEM && !w->all)) + 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: + { + 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); + } + + 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. */ + + for (insn = NEXT_INSN (loop_start); + GET_CODE (insn) != CALL_INSN && GET_CODE (insn) != CODE_LABEL + && ! (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); + } +} + +/* Variable used for communications between the next two routines. */ + +static struct write_data skipped_writes_memory; + +/* 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; +{ + if (GET_CODE (set) == CLOBBER +#ifdef HAVE_cc0 + || dest == cc0_rtx +#endif + || dest == pc_rtx) + return; + + if (GET_CODE (dest) == MEM) + note_mem_written (dest, &skipped_writes_memory); + + /* 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 promote "nonscalar" to be "all". */ + if (skipped_writes_memory.nonscalar) + skipped_writes_memory.all = 1; + + if (GET_CODE (dest) == REG || GET_CODE (dest) == SUBREG + || (! skipped_writes_memory.all && ! cse_rtx_addr_varies_p (dest))) + invalidate (dest, VOIDmode); + else if (GET_CODE (dest) == STRICT_LOW_PART + || GET_CODE (dest) == ZERO_EXTRACT) + invalidate (XEXP (dest, 0), GET_MODE (dest)); +} + +/* 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; + static struct write_data init = {0, 0, 0, 0}; + static struct write_data everything = {0, 1, 1, 1}; + + for (insn = start; insn && GET_CODE (insn) != CODE_LABEL; + insn = NEXT_INSN (insn)) + { + if (GET_RTX_CLASS (GET_CODE (insn)) != 'i') + continue; + + skipped_writes_memory = init; + + if (GET_CODE (insn) == CALL_INSN) + { + invalidate_for_call (); + skipped_writes_memory = everything; + } + + note_stores (PATTERN (insn), invalidate_skipped_set); + invalidate_from_clobbers (&skipped_writes_memory, PATTERN (insn)); + } +} + +/* 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; +{ + 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; + static struct write_data init = {0, 0, 0, 0}; + struct write_data writes_memory; + + writes_memory = init; + + /* 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)) + emit_insn_after (gen_move_insn (src_elt->exp, + SET_DEST (set)), + p); + break; + } + } + } + + /* Now invalidate anything modified by X. */ + note_mem_written (SET_DEST (x), &writes_memory); + + if (writes_memory.var) + invalidate_memory (&writes_memory); + + /* 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 && ! writes_memory.all + && ! cse_rtx_addr_varies_p (SET_DEST (x)))) + 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 + && 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 (); + + max_reg = nregs; + + all_minus_one = (int *) alloca (nregs * sizeof (int)); + consec_ints = (int *) alloca (nregs * sizeof (int)); + + for (i = 0; i < nregs; i++) + { + all_minus_one[i] = -1; + consec_ints[i] = i; + } + + reg_next_eqv = (int *) alloca (nregs * sizeof (int)); + reg_prev_eqv = (int *) alloca (nregs * sizeof (int)); + reg_qty = (int *) alloca (nregs * sizeof (int)); + reg_in_table = (int *) alloca (nregs * sizeof (int)); + reg_tick = (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, 0); +#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) + fprintf (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; + int in_libcall_block = 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; + + /* 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; + } + } + + code = GET_CODE (insn); + if (GET_MODE (insn) == QImode) + PUT_MODE (insn, VOIDmode); + + if (GET_RTX_CLASS (code) == 'i') + { + /* 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 (find_reg_note (insn, REG_LIBCALL, NULL_RTX)) + in_libcall_block = 1; + else if (find_reg_note (insn, REG_RETVAL, NULL_RTX)) + in_libcall_block = 0; + + cse_insn (insn, in_libcall_block); + } + + /* 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 (LABEL_NUSES (to) == 0) + insn = delete_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: + case CLOBBER: + 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 + || 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; + } + + 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. 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_dead_from_cse (insns, nreg) + rtx insns; + int nreg; +{ + int *counts = (int *) alloca (nreg * sizeof (int)); + rtx insn, prev; + rtx tem; + int i; + int in_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; + + prev = prev_real_insn (insn); + + /* Don't delete any insns that are part of a 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; + + if (in_libcall) + live_insn = 1; + 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; + } +} |