diff options
Diffstat (limited to 'gcc-1.40/cse.c')
| -rw-r--r-- | gcc-1.40/cse.c | 3936 |
1 files changed, 3936 insertions, 0 deletions
diff --git a/gcc-1.40/cse.c b/gcc-1.40/cse.c new file mode 100644 index 0000000..0807d2b --- /dev/null +++ b/gcc-1.40/cse.c @@ -0,0 +1,3936 @@ +/* Common subexpression elimination for GNU compiler. + Copyright (C) 1987, 1988, 1989 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 1, 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, 675 Mass Ave, Cambridge, MA 02139, USA. */ + + +#include "config.h" +#include "rtl.h" +#include "regs.h" +#include "hard-reg-set.h" +#include "flags.h" +#include "real.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. + + 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. + +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. + + Regs are preferred to constants as they are to everything else, + but 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; + +/* 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; + +/* Value stored in CC0 by previous insn: + 0 if previous insn didn't store in CC0. + else 0100 + (M&7)<<3 + (N&7) + where M is 1, 0 or -1 if result was >, == or < as signed number + and N is 1, 0 or -1 if result was >, == or < as unsigned number. + 0200 bit may also be set, meaning that only == and != comparisons + have known results. */ + +static int prev_insn_cc0; + +/* For machines where CC0 is one bit, we may see CC0 assigned a + constant value (after fold_rtx). + Record here the value stored in the previous insn (0 if none). */ + +static rtx prev_insn_explicit_cc0; + +/* 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 + (pseudo) register in the chain of registers sharing the same value. + Or -1 if this register is at the end of the chain. */ + +static int *reg_next_eqv; + +/* Index by (pseudo) register number, gives the number of the previous + (pseudo) register in the chain of registers sharing the same value. + Or -1 if this register is at the beginning of the chain. */ + +static int *reg_prev_eqv; + +/* Index by (pseudo) register number, gives the latest rtx + to use to insert a ref to that register. */ + +static rtx *reg_rtx; + +/* 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; + +/* Two vectors of max_reg ints: + one containing all -1's; in the other, element i contains i. + These are used to initialize various other vectors fast. */ + +static int *all_minus_one; +static int *consec_ints; + +/* Set nonzero in cse_insn to tell cse_basic_block to skip immediately + to the next basic block and treat it as a continuation of this one. */ + +static int cse_skip_to_next_block; + +/* 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 monononically always. + We use them to see whether a reg is used outside a given basic block. */ + +static short *uid_cuid; + +/* 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; + +/* canon_hash stores 1 in do_not_record + if it notices a reference to CC0, CC1 or PC. */ + +static int do_not_record; + +/* 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 `equivalence_only' field means that this expression came from a + REG_EQUIV or REG_EQUAL note; it is not valid for substitution into an insn. + + 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 `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 equivalence_only; +}; + +#define HASH(x, m) (canon_hash (x, m) % NBUCKETS) +/* 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 + +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; + +/* 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. + 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 var : 1; /* Invalidate variable addresses. */ + int nonscalar : 1; /* Invalidate all but scalar variables. */ + int all : 1; /* Invalidate all memory refs. */ +}; + +/* Nonzero if X has the form (PLUS frame-pointer integer). */ + +#define FIXED_BASE_PLUS_P(X) \ + (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT \ + && (XEXP (X, 0) == frame_pointer_rtx || XEXP (X, 0) == arg_pointer_rtx)) + +static struct table_elt *lookup (); +static void free_element (); + +static void remove_invalid_refs (); +static int exp_equiv_p (); +int refers_to_p (); +int refers_to_mem_p (); +static void invalidate_from_clobbers (); +static int safe_hash (); +static int canon_hash (); +static rtx equiv_constant (); +static int get_integer_term (); +static rtx get_related_value (); +static void note_mem_written (); +static int cse_rtx_addr_varies_p (); +static int fold_cc0 (); + +/* Return an estimate of the cost of computing rtx X. + The only use of this is to compare the costs of two expressions + to decide whether to replace one with the other. */ + +static int +rtx_cost (x) + rtx x; +{ + register int i, j; + register enum rtx_code code; + register char *fmt; + register int total; + + if (x == 0) + return 0; + + code = GET_CODE (x); + switch (code) + { + case REG: + return 1; + case SUBREG: + return 2; + CONST_COSTS (x, code); + } + + total = 2; + if (code == MEM) + total = 2 * GET_MODE_SIZE (GET_MODE (x)) / UNITS_PER_WORD; + + /* Sum the costs of the sub-rtx's, plus 2 just put in. */ + + 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)); + else if (fmt[i] == 'E') + for (j = 0; j < XVECLEN (x, i); j++) + total += rtx_cost (XVECEXP (x, i, j)); + + 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; + register int vecsize = max_reg * sizeof (rtx); + next_qty = max_reg; + + bzero (reg_rtx, vecsize); + bzero (reg_tick, vecsize); + + bcopy (all_minus_one, reg_in_table, vecsize); + bcopy (all_minus_one, reg_next_eqv, vecsize); + bcopy (all_minus_one, reg_prev_eqv, vecsize); + bcopy (consec_ints, reg_qty, vecsize); + + for (i = 0; i < max_qty; i++) + { + qty_first_reg[i] = i; + qty_last_reg[i] = i; + qty_const[i] = 0; + qty_const_insn[i] = 0; + } + + 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 (table, sizeof table); + + prev_insn_cc0 = 0; + prev_insn_explicit_cc0 = 0; + prev_insn = 0; +} + +/* Say that register REG contains a quantity not in any register before. */ + +static void +make_new_qty (reg) + register int reg; +{ + register int q; + + q = reg_qty[reg] = next_qty++; + qty_first_reg[q] = reg; + qty_last_reg[q] = reg; +} + +/* 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 (q == old) + abort (); + + reg_qty[new] = q; + firstr = qty_first_reg[q]; + lastr = qty_last_reg[q]; + + /* Prefer pseudo regs to hard regs with the same value. + 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 (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, insert at end. + Otherwise, insert before any hard regs that are at the end. */ + while (lastr < FIRST_PSEUDO_REGISTER && 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; + } +} + +/* Discard the records of what is in register REG. */ + +static void +reg_invalidate (reg) + register int reg; +{ + register int n = reg_next_eqv[reg]; + register int p = reg_prev_eqv[reg]; + register int q = reg_qty[reg]; + + reg_tick[reg]++; + + if (q == reg) + { + /* Save time if already invalid */ + /* It shouldn't be linked to anything if it's invalid. */ + if (reg_prev_eqv[q] != -1) + abort (); + if (reg_next_eqv[q] != -1) + abort (); + return; + } + + 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; + qty_first_reg[reg] = reg; + qty_last_reg[reg] = reg; + reg_next_eqv[reg] = -1; + reg_prev_eqv[reg] = -1; +} + +/* 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. */ + +static void +mention_regs (x) + rtx x; +{ + register enum rtx_code code; + register int i, j; + register char *fmt; + + if (x == 0) + return; + + code = GET_CODE (x); + if (code == REG) + { + register int regno = REGNO (x); + reg_rtx[regno] = x; + + if (reg_in_table[regno] >= 0 && reg_in_table[regno] != reg_tick[regno]) + remove_invalid_refs (regno); + + reg_in_table[regno] = reg_tick[regno]; + + return; + } + + fmt = GET_RTX_FORMAT (code); + for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) + if (fmt[i] == 'e') + mention_regs (XEXP (x, i)); + else if (fmt[i] == 'E') + for (j = 0; j < XVECLEN (x, i); j++) + mention_regs (XVECEXP (x, i, j)); +} + +/* Update the register quantities for inserting X into the hash table + with a value equivalent to CLASSP. + (If CLASSP is not a REG or a SUBREG, it is irrelevant.) + If MODIFIED is nonzero, X is a destination; it is being modified. + Note that reg_invalidate 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); + reg_rtx[regno] = x; + if (modified || reg_qty[regno] == regno) + { + if (classp && GET_CODE (classp->exp) == REG) + { + make_regs_eqv (regno, REGNO (classp->exp)); + /* Make sure reg_rtx is set up even for regs + not explicitly set (such as function value). */ + reg_rtx[REGNO (classp->exp)] = classp->exp; + } + else + make_new_qty (regno); + return 1; + } + } + /* Copying a subreg into a subreg makes the regs equivalent, + but only if the entire regs' mode is within one word. + Copying one reg of a DImode into one reg of another DImode + does not make them equivalent. */ + else if (GET_CODE (x) == SUBREG + && GET_CODE (SUBREG_REG (x)) == REG + && GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))) <= UNITS_PER_WORD + && (modified + || reg_qty[REGNO (SUBREG_REG (x))] == REGNO (SUBREG_REG (x)))) + { + if (classp && GET_CODE (classp->exp) == SUBREG + && GET_CODE (SUBREG_REG (classp->exp)) == REG + && GET_MODE (SUBREG_REG (classp->exp)) == GET_MODE (SUBREG_REG (x))) + { + int oregno = REGNO (SUBREG_REG (classp->exp)); + make_regs_eqv (REGNO (SUBREG_REG (x)), oregno); + /* Make sure reg_rtx is set up even for regs + not explicitly set (such as function value). */ + reg_rtx[oregno] = SUBREG_REG (classp->exp); + } + else + make_new_qty (REGNO (SUBREG_REG (x))); + return 1; + } + else + mention_regs (x); + return 0; +} + +/* 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 (elt, hash) + register struct table_elt *elt; + int 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 + 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; + int 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 || exp_equiv_p (x, p->exp, 1))) + 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; + int 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))) + 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, 0) % 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 (XEXP (p->exp, 0), XEXP (p->exp, 0), 1))) + return p->exp; + } + + return 0; +} + +/* Insert X in the hash table, assuming HASH is its hash code + and CLASSP is the current first 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 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) || \ + ((X)->cost == (Y)->cost \ + && GET_CODE ((X)->exp) == REG && GET_CODE ((Y)->exp) == REG \ + && (uid_cuid[regno_last_uid[REGNO ((X)->exp)]] > cse_basic_block_end \ + || uid_cuid[regno_first_uid[REGNO ((X)->exp)]] < cse_basic_block_start) \ + && (uid_cuid[regno_last_uid[REGNO ((X)->exp)]] \ + > uid_cuid[regno_last_uid[REGNO ((Y)->exp)]]))) + +static struct table_elt * +insert (x, classp, hash, mode) + register rtx x; + register struct table_elt *classp; + int hash; + enum machine_mode mode; +{ + register struct table_elt *elt; + + /* Put an element for X into the right hash bucket. */ + + elt = get_element (); + elt->exp = x; + elt->cost = rtx_cost (x) * 2; + /* Make pseudo regs a little cheaper than hard regs. */ + if (GET_CODE (x) == REG && REGNO (x) >= FIRST_PSEUDO_REGISTER) + elt->cost -= 1; + 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->equivalence_only = 0; + elt->mode = mode; + if (table[hash]) + table[hash]->prev_same_hash = elt; + table[hash] = elt; + + /* Put it into the proper value-class. */ + if (classp) + { + 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 ((CONSTANT_P (x) || GET_CODE (x) == CONST_DOUBLE || FIXED_BASE_PLUS_P (x)) + && GET_CODE (elt->first_same_value->exp) == REG) + { + qty_const[reg_qty[REGNO (elt->first_same_value->exp)]] = x; + qty_const_insn[reg_qty[REGNO (elt->first_same_value->exp)]] = this_insn; + } + + if (GET_CODE (x) == REG) + { + if (elt->next_same_value != 0 + && (CONSTANT_P (elt->next_same_value->exp) + || GET_CODE (elt->next_same_value->exp) == CONST_DOUBLE + || FIXED_BASE_PLUS_P (elt->next_same_value->exp))) + { + qty_const[reg_qty[REGNO (x)]] = elt->next_same_value->exp; + qty_const_insn[reg_qty[REGNO (x)]] = this_insn; + } + if (CONSTANT_P (elt->first_same_value->exp) + || GET_CODE (elt->first_same_value->exp) == CONST_DOUBLE + || FIXED_BASE_PLUS_P (elt->first_same_value->exp)) + { + qty_const[reg_qty[REGNO (x)]] = elt->first_same_value->exp; + 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); + int 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, 0, 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; +} + +/* 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). + + 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) + rtx x; +{ + register int i; + register struct table_elt *p; + register rtx base; + register 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 hash = HASH (x, 0); + reg_invalidate (REGNO (x)); + remove (lookup_for_remove (x, hash, GET_MODE (x)), hash); + return; + } + + if (GET_CODE (x) == SUBREG) + { + if (GET_CODE (SUBREG_REG (x)) != REG) + abort (); + invalidate (SUBREG_REG (x)); + 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 (); + base = XEXP (x, 0); + start = 0; + + /* Registers with nonvarying addresses usually have constant equivalents; + but the frame pointer register is also possible. */ + if (GET_CODE (base) == REG + && qty_const[reg_qty[REGNO (base)]] != 0) + base = qty_const[reg_qty[REGNO (base)]]; + + if (GET_CODE (base) == CONST) + base = XEXP (base, 0); + if (GET_CODE (base) == PLUS + && GET_CODE (XEXP (base, 1)) == CONST_INT) + { + start = INTVAL (XEXP (base, 1)); + base = XEXP (base, 0); + } + + end = start + GET_MODE_SIZE (GET_MODE (x)); + for (i = 0; i < NBUCKETS; i++) + { + register struct table_elt *next; + for (p = table[i]; p; p = next) + { + next = p->next_same_hash; + if (refers_to_mem_p (p->exp, base, start, end)) + remove (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; + register rtx x = reg_rtx[regno]; + + 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_p (p->exp, x)) + remove (p, i); + } +} + +/* 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 (p, i); + } +} + +/* Return the value of the integer term in X, if one is apparent; + otherwise return 0. + We do not check extremely carefully for the presence of integer terms + but rather consider only the cases that `insert' notices + for the `related_value' field. */ + +static int +get_integer_term (x) + rtx x; +{ + if (GET_CODE (x) == CONST) + x = XEXP (x, 0); + + if (GET_CODE (x) == MINUS + && GET_CODE (XEXP (x, 1)) == CONST_INT) + return - INTVAL (XEXP (x, 1)); + if (GET_CODE (x) != PLUS) + return 0; + if (GET_CODE (XEXP (x, 0)) == CONST_INT) + return INTVAL (XEXP (x, 0)); + if (GET_CODE (XEXP (x, 1)) == CONST_INT) + return INTVAL (XEXP (x, 1)); + return 0; +} + +static rtx +get_related_value (x) + rtx x; +{ + if (GET_CODE (x) != CONST) + return 0; + x = XEXP (x, 0); + if (GET_CODE (x) == PLUS) + { + if (GET_CODE (XEXP (x, 0)) == CONST_INT) + return XEXP (x, 1); + if (GET_CODE (XEXP (x, 1)) == CONST_INT) + return XEXP (x, 0); + } + else if (GET_CODE (x) == MINUS + && GET_CODE (XEXP (x, 1)) == CONST_INT) + return XEXP (x, 0); + return 0; +} + +/* 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 or it would not be a valid address, 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; + int offset; + rtx addr; + + /* 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) + { + if (p->first_same_value != 0 + && GET_CODE (p->first_same_value->exp) == REG) + break; + p = p->related_value; + + /* We went all the way around, so there is nothing to be found. + Return failure. */ + if (p == relt) + return 0; + /* Perhaps RELT was in the table for some other reason and + it has no related values recorded. */ + if (p == 0) + return 0; + } + + /* Note: OFFSET may be 0 if P->xexp and X are related by commutativity. */ + offset = (get_integer_term (x) - get_integer_term (p->exp)); + addr = plus_constant (p->first_same_value->exp, offset); + if (memory_address_p (QImode, addr)) + return addr; + return 0; +} + +/* 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. + It also knows it can use HASHREG to get the hash code of (REG n). */ + +#define HASHBITS 16 + +#define HASHREG(RTX) \ + ((((int) REG << 7) + reg_qty[REGNO (RTX)]) % NBUCKETS) + +static int +canon_hash (x, mode) + rtx x; + enum machine_mode mode; +{ + register int i, j; + register int 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: + { + /* We do not invalidate anything on pushing or popping + because they cannot change anything but the stack pointer; + but that means we must consider the stack pointer volatile + since it can be changed "mysteriously". */ + + register int regno = REGNO (x); + if (regno == STACK_POINTER_REGNUM + || (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])) + { + do_not_record = 1; + return 0; + } +#ifdef SMALL_REGISTER_CLASSES + if (regno < FIRST_PSEUDO_REGISTER) + { + do_not_record = 1; + return 0; + } +#endif + return hash + ((int) REG << 7) + reg_qty[regno]; + } + + case CONST_INT: + hash += ((int) mode + ((int) CONST_INT << 7) + + INTVAL (x) + (INTVAL (x) >> HASHBITS)); + return ((1 << HASHBITS) - 1) & hash; + + case CONST_DOUBLE: + /* This is like the general case, except that it only counts + the first two elements. */ + hash += (int) code + (int) GET_MODE (x); + { + int i; + for (i = 2; i < GET_RTX_LENGTH (CONST_DOUBLE); i++) + { + int tem = XINT (x, i); + hash += ((1 << HASHBITS) - 1) & (tem + (tem >> HASHBITS)); + } + } + return hash; + + /* Assume there is only one rtx object for any given label. */ + case LABEL_REF: + /* Use `and' to ensure a positive number. */ + return (hash + ((int) LABEL_REF << 7) + + ((int) XEXP (x, 0) & ((1 << HASHBITS) - 1))); + + case SYMBOL_REF: + return (hash + ((int) SYMBOL_REF << 7) + + ((int) XEXP (x, 0) & ((1 << HASHBITS) - 1))); + + 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 += (int) 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: + 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 += (int) code + (int) GET_MODE (x); + fmt = GET_RTX_FORMAT (code); + for (; i >= 0; i--) + { + if (fmt[i] == 'e') + { + /* If we are about to do the last recursive call + needed at this level, change it into iteration. + This function is called enough to be worth it. */ + if (i == 0) + { + x = XEXP (x, 0); + goto repeat; + } + hash += canon_hash (XEXP (x, i), 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 char *p = XSTR (x, i); + if (p) + while (*p) + { + register int tem = *p++; + hash += ((1 << HASHBITS) - 1) & (tem + (tem >> HASHBITS)); + } + } + else + { + register int tem = XINT (x, i); + hash += ((1 << HASHBITS) - 1) & (tem + (tem >> HASHBITS)); + } + } + return hash; +} + +/* Like canon_hash but with no side effects. */ + +static int +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; + int 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. */ + +static int +exp_equiv_p (x, y, validate) + rtx x, y; + int validate; +{ + register int i; + 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)) + return 0; + + switch (code) + { + case PC: + case CC0: + return x == y; + + case CONST_INT: + return XINT (x, 0) == XINT (y, 0); + + case LABEL_REF: + case SYMBOL_REF: + return XEXP (x, 0) == XEXP (y, 0); + + case REG: + return (reg_qty[REGNO (x)] == reg_qty[REGNO (y)] + && (!validate + || reg_in_table[REGNO (y)] == reg_tick[REGNO (y)])); + } + + /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. */ + + if (GET_MODE (x) != GET_MODE (y)) + return 0; + + /* 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--) + { + if (fmt[i] == 'e') + { + if (! exp_equiv_p (XEXP (x, i), XEXP (y, i), validate)) + return 0; + } + else if (fmt[i] == 'E') + { + int j; + 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)) + return 0; + } + else if (fmt[i] == 's') + { + if (strcmp (XSTR (x, i), XSTR (y, i))) + return 0; + } + else + { + if (XINT (x, i) != XINT (y, i)) + return 0; + } + } + 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. */ + +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)) + 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; +} + +/* Return 1 iff any subexpression of X refers to memory + at an address of REG 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. + 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. */ + +int +refers_to_mem_p (x, reg, start, end) + rtx x, reg; + int start, end; +{ + register int i; + register enum rtx_code code; + register char *fmt; + + if (GET_CODE (reg) == CONST_INT) + { + start += INTVAL (reg); + end += INTVAL (reg); + reg = const0_rtx; + } + + repeat: + if (x == 0) + return 0; + + code = GET_CODE (x); + if (code == MEM) + { + register rtx addr = XEXP (x, 0); /* Get the address. */ + int myend; + if (GET_CODE (addr) == REG + /* qty_const is 0 when outside the cse pass; + at such times, this info is not available. */ + && qty_const != 0 + && qty_const[reg_qty[REGNO (addr)]] != 0) + addr = qty_const[reg_qty[REGNO (addr)]]; + if (GET_CODE (addr) == CONST) + addr = XEXP (addr, 0); + + /* If ADDR is BASE, or BASE plus an integer, put + the integer in I. */ + if (addr == reg) + i = 0; + else if (GET_CODE (addr) == PLUS + && XEXP (addr, 0) == reg + && GET_CODE (XEXP (addr, 1)) == CONST_INT) + i = INTVAL (XEXP (addr, 1)); + else if (GET_CODE (addr) == CONST_INT && reg == const0_rtx) + i = INTVAL (addr); + else + return 0; + + myend = i + GET_MODE_SIZE (GET_MODE (x)); + return myend > start && i < 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), reg, 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), reg, 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; +{ + if (GET_CODE (x) == MEM + && GET_CODE (XEXP (x, 0)) == REG + && qty_const[reg_qty[REGNO (XEXP (x, 0))]] != 0) + return 0; + return rtx_addr_varies_p (x); +} + +/* Canonicalize an expression: + replace each register reference inside it + with the "oldest" equivalent register. */ + +static rtx +canon_reg (x) + rtx x; +{ + 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 rtx new; + /* 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. */ + if (REGNO (x) < FIRST_PSEUDO_REGISTER) + return x; + new = reg_rtx[qty_first_reg[reg_qty[REGNO (x)]]]; + return new ? new : x; + } + } + + fmt = GET_RTX_FORMAT (code); + for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) + { + register int j; + + if (fmt[i] == 'e') + XEXP (x, i) = canon_reg (XEXP (x, i)); + else if (fmt[i] == 'E') + for (j = 0; j < XVECLEN (x, i); j++) + XVECEXP (x, i, j) = canon_reg (XVECEXP (x, i, j)); + } + + return x; +} + +/* 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. This is because an instruction that + uses a register is usually faster than one that uses a constant. + + COPYFLAG is nonzero for memory addresses and subexpressions thereof. + If COPYFLAG is nonzero, we avoid altering X itself + by creating new structure when necessary. In this case we + can risk creating invalid structure because it will be tested. + If COPYFLAG is zero, be careful not to substitute constants + into expressions that cannot be simplified. */ + +static rtx +fold_rtx (x, copyflag) + rtx x; + int copyflag; +{ + register enum rtx_code code; + register char *fmt; + register int i, val; + rtx new = 0; + int copied = ! copyflag; + int width; + + /* Constant equivalents of first three operands of X; + 0 when no such equivalent is known. */ + rtx const_arg0; + rtx const_arg1; + rtx const_arg2; + + if (x == 0) + return x; + + width = GET_MODE_BITSIZE (GET_MODE (x)); + + code = GET_CODE (x); + switch (code) + { + case CONST: + case CONST_INT: + case CONST_DOUBLE: + case SYMBOL_REF: + case LABEL_REF: + case PC: + case CC0: + 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; + + /* We must be careful when folding a memory address + to avoid making it invalid. So fold nondestructively + and use the result only if it's valid. */ + case MEM: + { + rtx newaddr = fold_rtx (XEXP (x, 0), 1); + /* Save time if no change was made. */ + if (XEXP (x, 0) == newaddr) + return x; + + if (! memory_address_p (GET_MODE (x), newaddr) + && memory_address_p (GET_MODE (x), XEXP (x, 0))) + return x; + + /* Don't replace a value with a more expensive one. */ + if (rtx_cost (XEXP (x, 0)) < rtx_cost (newaddr)) + return x; + + if (copyflag) + return gen_rtx (MEM, GET_MODE (x), newaddr); + XEXP (x, 0) = newaddr; + return x; + } + } + + const_arg0 = 0; + const_arg1 = 0; + const_arg2 = 0; + + /* 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') + { + register rtx tem = fold_rtx (XEXP (x, i), copyflag); + + /* If an operand has changed under folding, and we are not supposed to + alter the original structure, copy X if we haven't yet done so. */ + if (! copied && tem != XEXP (x, i)) + { + int j; + rtx new = rtx_alloc (code); + PUT_MODE (new, GET_MODE (x)); + for (j = 0; j < GET_RTX_LENGTH (code); j++) + XINT (new, j) = XINT (x, j); + x = new; + copied = 1; + } + + /* Install the possibly altered folded operand. */ + XEXP (x, i) = tem; + + /* For the first three operands, see if the operand + is constant or equivalent to a constant. */ + if (i < 3) + { + rtx const_arg = equiv_constant (tem); + + switch (i) + { + case 0: + const_arg0 = const_arg; + break; + case 1: + const_arg1 = const_arg; + break; + case 2: + const_arg2 = const_arg; + break; + } + } + } + else if (fmt[i] == 'E') + /* Don't try to fold inside of a vector of expressions. + Doing nothing is 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. */ + + switch (code) + { + case PLUS: + case MULT: + case UMULT: + case AND: + case IOR: + case XOR: + case NE: + case EQ: + if (const_arg0 && const_arg0 == XEXP (x, 0) + && (! (const_arg1 && const_arg1 == XEXP (x, 1)) + || (GET_CODE (const_arg0) == CONST_INT + && GET_CODE (const_arg1) != CONST_INT))) + { + register rtx tem; + + if (! copied) + copied = 1, x = copy_rtx (x); + tem = XEXP (x, 0); XEXP (x, 0) = XEXP (x, 1); XEXP (x, 1) = tem; + tem = const_arg0; const_arg0 = const_arg1; const_arg1 = tem; + } + break; + } + + /* Now decode the kind of rtx X is + and then return X (if nothing can be done) + or return a folded rtx + or store a value in VAL and drop through + (to return a CONST_INT for the integer VAL). */ + + if (GET_RTX_LENGTH (code) == 1) + { + if (const_arg0 == 0) + return x; + + if (GET_CODE (const_arg0) == CONST_INT) + { + register int arg0 = INTVAL (const_arg0); + + switch (GET_CODE (x)) + { + case NOT: + val = ~ arg0; + break; + + case NEG: + val = - arg0; + break; + + case TRUNCATE: + val = arg0; + break; + + case ZERO_EXTEND: + { + enum machine_mode mode = GET_MODE (XEXP (x, 0)); + if (mode == VOIDmode) + return x; + if (GET_MODE_BITSIZE (mode) < HOST_BITS_PER_INT) + val = arg0 & ~((-1) << GET_MODE_BITSIZE (mode)); + else + return x; + break; + } + + case SIGN_EXTEND: + { + enum machine_mode mode = GET_MODE (XEXP (x, 0)); + if (mode == VOIDmode) + return x; + if (GET_MODE_BITSIZE (mode) < HOST_BITS_PER_INT) + { + val = arg0 & ~((-1) << GET_MODE_BITSIZE (mode)); + if (val & (1 << (GET_MODE_BITSIZE (mode) - 1))) + val -= 1 << GET_MODE_BITSIZE (mode); + } + else + return x; + break; + } + + default: + return x; + } + } +#if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC) + else if (GET_CODE (const_arg0) == CONST_DOUBLE + && GET_CODE (x) == NEG + && GET_MODE_CLASS (GET_MODE (x)) == MODE_FLOAT) + { + union real_extract u; + register REAL_VALUE_TYPE arg0; + jmp_buf handler; + + if (setjmp (handler)) + { + warning ("floating point trap in constant folding"); + return x; + } + set_float_handler (handler); + bcopy (&CONST_DOUBLE_LOW (const_arg0), &u, sizeof u); + arg0 = u.d; + + u.d = REAL_VALUE_NEGATE (arg0); + x = immed_real_const_1 (u.d, GET_MODE (x)); + set_float_handler (0); + return x; + } +#endif + else + return x; + } + else if (GET_RTX_LENGTH (code) == 2) + { + register int arg0, arg1, arg0s, arg1s; + int arithwidth = width; + + /* If 1st arg is the condition codes, 2nd must be zero + and this must be a comparison. + Decode the info on how the previous insn set the cc0 + and use that to deduce result of comparison. */ + if (XEXP (x, 0) == cc0_rtx + || GET_CODE (XEXP (x, 0)) == COMPARE) + { + if (XEXP (x, 0) == cc0_rtx) + arg0 = prev_insn_cc0; + else + arg0 = fold_cc0 (VOIDmode, XEXP (x, 0)); + + if (arg0 == 0 + || const_arg1 != const0_rtx + /* 0200 bit in arg0 means only zeroness is known, + and sign is not known. */ + || ((arg0 & 0200) != 0 && code != EQ && code != NE)) + return x; + + /* Extract either the signed or the unsigned digit from ARG0. */ + if (code == LEU || code == LTU || code == GEU || code == GTU) + arg0 = arg0 & 7; + else + arg0 = (arg0 >> 3) & 7; + if (arg0 == 7) arg0 = -1; + + switch (code) + { + case LE: + case LEU: + return (arg0 <= 0) ? const1_rtx : const0_rtx; + case LT: + case LTU: + return (arg0 < 0) ? const1_rtx : const0_rtx; + case GE: + case GEU: + return (arg0 >= 0) ? const1_rtx : const0_rtx; + case GT: + case GTU: + return (arg0 > 0) ? const1_rtx : const0_rtx; + case NE: + return (arg0 != 0) ? const1_rtx : const0_rtx; + case EQ: + return (arg0 == 0) ? const1_rtx : const0_rtx; + default: + abort (); + } + } + + if (const_arg0 == 0 || const_arg1 == 0 + || GET_CODE (const_arg0) != CONST_INT + || GET_CODE (const_arg1) != CONST_INT) + { + /* Even if we can't compute a constant result, + there are some cases worth simplifying. */ + /* Note that we cannot rely on constant args to come last, + even for commutative operators, + because that happens only when the constant is explicit. */ + switch (code) + { + case PLUS: + if (const_arg0 == const0_rtx + || const_arg0 == fconst0_rtx + || const_arg0 == dconst0_rtx) + return XEXP (x, 1); + if (const_arg1 == const0_rtx + || const_arg1 == fconst0_rtx + || const_arg1 == dconst0_rtx) + return XEXP (x, 0); + + /* Handle both-operands-constant cases. */ + if (const_arg0 != 0 && const_arg1 != 0 + && GET_CODE (const_arg0) != CONST_DOUBLE + && GET_CODE (const_arg1) != CONST_DOUBLE + && GET_MODE_CLASS (GET_MODE (x)) == MODE_INT) + { + if (GET_CODE (const_arg1) == CONST_INT) + new = plus_constant (const_arg0, INTVAL (const_arg1)); + else + { + new = gen_rtx (PLUS, GET_MODE (x), const0_rtx, const0_rtx); + XEXP (new, 0) = const_arg0; + if (GET_CODE (const_arg0) == CONST) + XEXP (new, 0) = XEXP (const_arg0, 0); + XEXP (new, 1) = const_arg1; + if (GET_CODE (const_arg1) == CONST) + XEXP (new, 1) = XEXP (const_arg1, 0); + new = gen_rtx (CONST, GET_MODE (new), new); + } + } + else if (const_arg1 != 0 + && GET_CODE (const_arg1) == CONST_INT + && GET_CODE (XEXP (x, 0)) == PLUS + && (CONSTANT_P (XEXP (XEXP (x, 0), 0)) + || CONSTANT_P (XEXP (XEXP (x, 0), 1)))) + /* constant + (variable + constant) + can result if an index register is made constant. + We simplify this by adding the constants. + If we did not, it would become an invalid address. */ + new = plus_constant (XEXP (x, 0), + INTVAL (const_arg1)); + break; + + case COMPARE: + if (const_arg1 == const0_rtx) + return XEXP (x, 0); + + if (XEXP (x, 0) == XEXP (x, 1) + || (const_arg0 != 0 && const_arg0 == const_arg1)) + { + /* We can't assume x-x is 0 with IEEE floating point. */ + if (GET_MODE_CLASS (GET_MODE (x)) == MODE_INT) + return const0_rtx; + } + break; + + case MINUS: + if (const_arg1 == const0_rtx + || const_arg1 == fconst0_rtx + || const_arg1 == dconst0_rtx) + return XEXP (x, 0); + + if (XEXP (x, 0) == XEXP (x, 1) + || (const_arg0 != 0 && const_arg0 == const_arg1)) + { + /* We can't assume x-x is 0 with IEEE floating point. */ + if (GET_MODE_CLASS (GET_MODE (x)) == MODE_INT) + return const0_rtx; + } + + /* Change subtraction from zero into negation. */ + if (const_arg0 == const0_rtx) + return gen_rtx (NEG, GET_MODE (x), XEXP (x, 1)); + + /* Don't let a relocatable value get a negative coeff. */ + if (const_arg0 != 0 && const_arg1 != 0 + && GET_CODE (const_arg1) == CONST_INT) + new = plus_constant (const_arg0, - INTVAL (const_arg1)); + break; + + case MULT: + case UMULT: + if (const_arg1 && GET_CODE (const_arg1) == CONST_INT + && INTVAL (const_arg1) == -1 + /* Don't do this in the case of widening multiplication. */ + && GET_MODE (XEXP (x, 0)) == GET_MODE (x)) + return gen_rtx (NEG, GET_MODE (x), XEXP (x, 0)); + if (const_arg0 && GET_CODE (const_arg0) == CONST_INT + && INTVAL (const_arg0) == -1 + && GET_MODE (XEXP (x, 1)) == GET_MODE (x)) + return gen_rtx (NEG, GET_MODE (x), XEXP (x, 1)); + if (const_arg1 == const0_rtx || const_arg0 == const0_rtx) + new = const0_rtx; + if (const_arg1 == fconst0_rtx || const_arg0 == fconst0_rtx) + new = fconst0_rtx; + if (const_arg1 == dconst0_rtx || const_arg0 == dconst0_rtx) + new = dconst0_rtx; + if (const_arg1 == const1_rtx) + return XEXP (x, 0); + if (const_arg0 == const1_rtx) + return XEXP (x, 1); + break; + + case IOR: + if (const_arg1 == const0_rtx) + return XEXP (x, 0); + if (const_arg0 == const0_rtx) + return XEXP (x, 1); + if (const_arg1 && GET_CODE (const_arg1) == CONST_INT + && (INTVAL (const_arg1) & GET_MODE_MASK (GET_MODE (x))) + == GET_MODE_MASK (GET_MODE (x))) + new = const_arg1; + if (const_arg0 && GET_CODE (const_arg0) == CONST_INT + && (INTVAL (const_arg0) & GET_MODE_MASK (GET_MODE (x))) + == GET_MODE_MASK (GET_MODE (x))) + new = const_arg0; + break; + + case XOR: + if (const_arg1 == const0_rtx) + return XEXP (x, 0); + if (const_arg0 == const0_rtx) + return XEXP (x, 1); + if (const_arg1 && GET_CODE (const_arg1) == CONST_INT + && (INTVAL (const_arg1) & GET_MODE_MASK (GET_MODE (x))) + == GET_MODE_MASK (GET_MODE (x))) + return gen_rtx (NOT, GET_MODE (x), XEXP (x, 0)); + if (const_arg0 && GET_CODE (const_arg0) == CONST_INT + && (INTVAL (const_arg0) & GET_MODE_MASK (GET_MODE (x))) + == GET_MODE_MASK (GET_MODE (x))) + return gen_rtx (NOT, GET_MODE (x), XEXP (x, 1)); + break; + + case AND: + if (const_arg1 == const0_rtx || const_arg0 == const0_rtx) + new = const0_rtx; + if (const_arg1 && GET_CODE (const_arg1) == CONST_INT + && (INTVAL (const_arg1) & GET_MODE_MASK (GET_MODE (x))) + == GET_MODE_MASK (GET_MODE (x))) + return XEXP (x, 0); + if (const_arg0 && GET_CODE (const_arg0) == CONST_INT + && (INTVAL (const_arg0) & GET_MODE_MASK (GET_MODE (x))) + == GET_MODE_MASK (GET_MODE (x))) + return XEXP (x, 1); + break; + + case DIV: + case UDIV: + if (const_arg1 == const1_rtx) + return XEXP (x, 0); + if (const_arg0 == const0_rtx) + new = const0_rtx; + break; + + case UMOD: + case MOD: + if (const_arg0 == const0_rtx || const_arg1 == const1_rtx) + new = const0_rtx; + break; + + case LSHIFT: + case ASHIFT: + case ROTATE: + case ASHIFTRT: + case LSHIFTRT: + case ROTATERT: + if (const_arg1 == const0_rtx) + return XEXP (x, 0); + if (const_arg0 == const0_rtx) + new = const_arg0; + break; + } + + if (new != 0 && LEGITIMATE_CONSTANT_P (new)) + return new; + return x; + } + + if (arithwidth == 0) + { + if (GET_MODE (XEXP (x, 0)) != VOIDmode) + arithwidth = GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0))); + if (GET_MODE (XEXP (x, 1)) != VOIDmode) + arithwidth = GET_MODE_BITSIZE (GET_MODE (XEXP (x, 1))); + } + + /* Get the integer argument values in two forms: + zero-extended in ARG0, ARG1 and sign-extended in ARG0S, ARG1S. */ + + arg0 = INTVAL (const_arg0); + arg1 = INTVAL (const_arg1); + + if (arithwidth < HOST_BITS_PER_INT && arithwidth > 0) + { + arg0 &= (1 << arithwidth) - 1; + arg1 &= (1 << arithwidth) - 1; + + arg0s = arg0; + if (arg0s & (1 << (arithwidth - 1))) + arg0s |= ((-1) << arithwidth); + + arg1s = arg1; + if (arg1s & (1 << (arithwidth - 1))) + arg1s |= ((-1) << arithwidth); + } + else + { + arg0s = arg0; + arg1s = arg1; + } + + /* Compute the value of the arithmetic. */ + + switch (code) + { + case PLUS: + val = arg0 + arg1; + break; + + case MINUS: + val = arg0 - arg1; + break; + + case MULT: + val = arg0s * arg1s; + break; + + case DIV: + if (arg1s == 0) + return x; + val = arg0s / arg1s; + break; + + case MOD: + if (arg1s == 0) + return x; + val = arg0s % arg1s; + break; + + case UMULT: + val = (unsigned) arg0 * arg1; + break; + + case UDIV: + if (arg1 == 0) + return x; + val = (unsigned) arg0 / arg1; + break; + + case UMOD: + if (arg1 == 0) + return x; + val = (unsigned) arg0 % arg1; + break; + + case AND: + val = arg0 & arg1; + break; + + case IOR: + val = arg0 | arg1; + break; + + case XOR: + val = arg0 ^ arg1; + break; + + case NE: + val = arg0 != arg1; + break; + + case EQ: + val = arg0 == arg1; + break; + + case LE: + val = arg0s <= arg1s; + break; + + case LT: + val = arg0s < arg1s; + break; + + case GE: + val = arg0s >= arg1s; + break; + + case GT: + val = arg0s > arg1s; + break; + + case LEU: + val = ((unsigned) arg0) <= ((unsigned) arg1); + break; + + case LTU: + val = ((unsigned) arg0) < ((unsigned) arg1); + break; + + case GEU: + val = ((unsigned) arg0) >= ((unsigned) arg1); + break; + + case GTU: + val = ((unsigned) arg0) > ((unsigned) arg1); + break; + + case LSHIFT: + /* If target machine uses negative shift counts + but host machine does not, simulate them. */ + if (arg1 < 0) + val = ((unsigned) arg0) >> -arg1; + else + val = ((unsigned) arg0) << arg1; + break; + + case ASHIFT: + if (arg1 < 0) + val = arg0s >> -arg1; + else + val = arg0s << arg1; + break; + + case ROTATERT: + arg1 = - arg1; + case ROTATE: + { + int size = GET_MODE_SIZE (GET_MODE (x)) * BITS_PER_UNIT; + if (arg1 > 0) + { + arg1 %= size; + val = ((((unsigned) arg0) << arg1) + | (((unsigned) arg0) >> (size - arg1))); + } + else if (arg1 < 0) + { + arg1 = (- arg1) % size; + val = ((((unsigned) arg0) >> arg1) + | (((unsigned) arg0) << (size - arg1))); + } + else + val = arg0; + } + break; + + case LSHIFTRT: + /* If target machine uses negative shift counts + but host machine does not, simulate them. */ + if (arg1 < 0) + val = ((unsigned) arg0) << -arg1; + else + val = ((unsigned) arg0) >> arg1; + break; + + case ASHIFTRT: + if (arg1 < 0) + val = arg0s << -arg1; + else + val = arg0s >> arg1; + break; + + default: + return x; + } + } + else if (code == IF_THEN_ELSE && const_arg0 != 0 + && GET_CODE (const_arg0) == CONST_INT) + return XEXP (x, ((INTVAL (const_arg0) != 0) ? 1 : 2)); + else if (code == IF_THEN_ELSE && XEXP (x, 0) == cc0_rtx + && prev_insn_explicit_cc0 != 0) + return XEXP (x, ((INTVAL (prev_insn_explicit_cc0) != 0) ? 1 : 2)); + else if (code == SIGN_EXTRACT || code == ZERO_EXTRACT) + { + if (const_arg0 != 0 && const_arg1 != 0 && const_arg2 != 0 + && GET_CODE (const_arg0) == CONST_INT + && GET_CODE (const_arg1) == CONST_INT + && GET_CODE (const_arg2) == CONST_INT) + { + /* Extracting a bit-field from a constant */ + val = INTVAL (const_arg0); +#ifdef BITS_BIG_ENDIAN + val >>= (GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0))) + - INTVAL (const_arg2) - INTVAL (const_arg1)); +#else + val >>= INTVAL (const_arg2); +#endif + if (HOST_BITS_PER_INT != INTVAL (const_arg1)) + { + /* First zero-extend. */ + val &= (1 << INTVAL (const_arg1)) - 1; + /* If desired, propagate sign bit. */ + if (code == SIGN_EXTRACT + && (val & (1 << (INTVAL (const_arg1) - 1)))) + val |= ~ (1 << INTVAL (const_arg1)); + } + } + else + return x; + } + else + return x; + + /* 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_INT && width > 0) + { + if ((val & ((-1) << (width - 1))) + != ((-1) << (width - 1))) + val &= (1 << width) - 1; + } + + /* Now make the new constant. */ + { + rtx new = gen_rtx (CONST_INT, VOIDmode, val); + return LEGITIMATE_CONSTANT_P (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; +{ + rtx tem1; + + if (CONSTANT_P (x) || GET_CODE (x) == CONST_DOUBLE) + return x; + else if (GET_CODE (x) == REG + && (tem1 = qty_const[reg_qty[REGNO (x)]]) != 0 + /* Make sure it is really a constant */ + && GET_CODE (tem1) != REG && GET_CODE (tem1) != PLUS) + return tem1; + /* If integer truncation is being done with SUBREG, + we can compute the result. */ + else if (GET_CODE (x) == SUBREG && SUBREG_WORD (x) == 0 + && (tem1 = qty_const[reg_qty[REGNO (SUBREG_REG (x))]]) != 0 + /* Make sure it is a known integer. */ + && GET_CODE (tem1) == CONST_INT + && GET_MODE_SIZE (GET_MODE (x)) <= HOST_BITS_PER_INT + /* Make sure this SUBREG is truncation. */ + && GET_MODE_SIZE (GET_MODE (x)) < GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))) + { + int value = INTVAL (tem1); + if (GET_MODE_BITSIZE (GET_MODE (x)) != HOST_BITS_PER_INT) + value &= (1 << GET_MODE_BITSIZE (GET_MODE (x))) - 1; + + if (value == INTVAL (tem1)) + return tem1; + else + return gen_rtx (CONST_INT, VOIDmode, value); + } + return 0; +} + +/* Given an expression X which is used to set CC0, + return an integer recording (in the encoding used for prev_insn_cc0) + how the condition codes would be set by that expression. + Return 0 if the value is not constant + or if there is any doubt what condition codes result from it. + + MODE is the machine mode to use to interpret X if it is a CONST_INT. */ + +static int +fold_cc0 (mode, x) + enum machine_mode mode; + rtx x; +{ + if (GET_CODE (x) == COMPARE) + { + rtx y0 = fold_rtx (XEXP (x, 0), 0); + rtx y1 = fold_rtx (XEXP (x, 1), 0); + int u0, u1, s0, s1; + enum machine_mode m; + rtx tem; + + m = GET_MODE (y0); + if (m == VOIDmode) + m = GET_MODE (y1); + if (m == VOIDmode) + return 0; + + tem = equiv_constant (y0); + if (tem != 0) + y0 = tem; + + if (y0 == 0) + return 0; + + tem = equiv_constant (y1); + if (tem != 0) + y1 = tem; + + if (y1 == 0) + return 0; + + /* Compare floats; report the result only for signed compares + since that's all there are for floats. */ + if (GET_CODE (y0) == CONST_DOUBLE + && GET_CODE (y1) == CONST_DOUBLE + && GET_MODE_CLASS (GET_MODE (y0)) == MODE_FLOAT) + { + union real_extract u0, u1; + int value; + jmp_buf handler; + + if (setjmp (handler)) + { + warning ("floating point trap in constant folding"); + return 0; + } + set_float_handler (handler); + bcopy (&CONST_DOUBLE_LOW (y0), &u0, sizeof u0); + bcopy (&CONST_DOUBLE_LOW (y1), &u1, sizeof u1); + value = 0100 + (REAL_VALUES_LESS (u0.d, u1.d) ? 7 << 3 + : REAL_VALUES_LESS (u1.d, u0.d) ? 1 << 3 : 0); + set_float_handler (0); + return value; + } + + /* Aside from that, demand explicit integers. */ + + if (GET_CODE (y0) != CONST_INT) + return 0; + + if (GET_CODE (y1) != CONST_INT) + return 0; + + s0 = u0 = INTVAL (y0); + s1 = u1 = INTVAL (y1); + + { + int width = GET_MODE_BITSIZE (m); + if (width < HOST_BITS_PER_INT) + { + s0 = u0 &= ~ ((-1) << width); + s1 = u1 &= ~ ((-1) << width); + if (u0 & (1 << (width - 1))) + s0 |= ((-1) << width); + if (u1 & (1 << (width - 1))) + s1 |= ((-1) << width); + } + } + + return 0100 + ((s0 < s1 ? 7 : s0 > s1) << 3) + + (((unsigned) u0 < (unsigned) u1) ? 7 + : ((unsigned) u0 > (unsigned) u1)); + } + { + rtx y0; + int u0, s0; + enum machine_mode m; + + y0 = fold_rtx (x, 0); + + m = GET_MODE (y0); + if (m == VOIDmode) + m = mode; + + if (GET_CODE (y0) == REG) + y0 = qty_const[reg_qty[REGNO (y0)]]; + + /* Register had no constant equivalent? We can't do anything. */ + if (y0 == 0) + return 0; + + /* If we don't know the mode, we can't test the sign. */ + if (m == VOIDmode) + return 0; + + /* Value is frame-pointer plus a constant? Or non-explicit constant? + That isn't zero, but we don't know its sign. */ + if (FIXED_BASE_PLUS_P (y0) + || GET_CODE (y0) == SYMBOL_REF || GET_CODE (y0) == CONST + || GET_CODE (y0) == LABEL_REF) + return 0300 + (1<<3) + 1; + + /* Otherwise, only integers enable us to optimize. */ + if (GET_CODE (y0) != CONST_INT) + return 0; + + s0 = u0 = INTVAL (y0); + { + int width = GET_MODE_BITSIZE (m); + if (width < HOST_BITS_PER_INT) + { + s0 = u0 &= ~ ((-1) << GET_MODE_BITSIZE (m)); + if (u0 & (1 << (GET_MODE_BITSIZE (m) - 1))) + s0 |= ((-1) << GET_MODE_BITSIZE (m)); + } + } + return 0100 + ((s0 < 0 ? 7 : s0 > 0) << 3) + (u0 != 0); + } +} + +/* Attempt to prove that a loop will be executed >= 1 times, + or prove it will be executed 0 times. + If either can be proved, delete some of the code. */ + +static void +predecide_loop_entry (insn) + register rtx insn; +{ + register rtx jump = NEXT_INSN (insn); + register rtx p; + register rtx loop_top_label = NEXT_INSN (jump); + enum anon1 { UNK, DELETE_LOOP, DELETE_JUMP } disposition = UNK; + int count = 0; + + /* Give up if we don't find a jump that enters the loop. */ + if (! simplejump_p (jump)) + return; + + /* Find the label at the top of the loop. */ + while (GET_CODE (loop_top_label) == BARRIER + || GET_CODE (loop_top_label) == NOTE) + { + loop_top_label = NEXT_INSN (loop_top_label); + /* No label? Give up. */ + if (loop_top_label == 0) + return; + } + if (GET_CODE (loop_top_label) != CODE_LABEL) + abort (); + + /* Find the label at which the loop is entered. */ + p = XEXP (SET_SRC (PATTERN (jump)), 0); + if (GET_CODE (p) != CODE_LABEL) + abort (); + + /* Trace the flow of control through the end test, + propagating constants, to see if result is determined. */ + prev_insn_cc0 = 0; + prev_insn_explicit_cc0 = 0; + /* Avoid infinite loop if we find a cycle of jumps. */ + while (count < 10) + { + /* At end of function? Means rtl is inconsistent, + but this can happen when stmt.c gets confused + by a syntax error. */ + if (p == 0) + break; + /* Arriving at end of loop means endtest will drop out. */ + if (GET_CODE (p) == NOTE + && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END) + { + disposition = DELETE_LOOP; + break; + } + else if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == NOTE) + ; + /* We only know how to handle two kinds of insns: + conditional jumps, and those that set the condition codes. */ + else if (GET_CODE (p) == INSN && GET_CODE (PATTERN (p)) == SET + && SET_DEST (PATTERN (p)) == cc0_rtx) + { + prev_insn_cc0 = fold_cc0 (GET_MODE (SET_SRC (PATTERN (p))), + copy_rtx (SET_SRC (PATTERN (p)))); + if (GET_CODE (SET_SRC (PATTERN (p))) == CONST_INT) + prev_insn_explicit_cc0 = SET_SRC (PATTERN (p)); + } + else if (GET_CODE (p) == JUMP_INSN + && GET_CODE (PATTERN (p)) == SET + && SET_DEST (PATTERN (p)) == pc_rtx) + { + register rtx target + = fold_rtx (SET_SRC (PATTERN (p)), 1); + if (GET_CODE (target) == LABEL_REF) + p = XEXP (target, 0); + else if (target != pc_rtx) + /* If destination of jump is not fixed, give up. */ + break; + count++; + } + /* Any other kind of insn means we don't know + what result the test will have. */ + else + break; + + /* Arriving at top of loop means we can drop straight in. + Check here because we can arrive only via a jump insn + which would have changed P above. */ + if (p == loop_top_label) + { + disposition = DELETE_JUMP; + break; + } + /* We went past one insn; consider the next. */ + p = NEXT_INSN (p); + } + if (disposition == DELETE_JUMP) + { + /* We know the loop test will succeed the first time, + so delete the jump to the test; drop right into loop. + Note that one call to delete_insn gets the BARRIER as well. */ + delete_insn (jump); + } + if (disposition == DELETE_LOOP) + { + /* We know the endtest will fail and drop right out of the loop, + but it isn't safe to delete the loop here. + There could be jumps into it from outside. + So make the entry-jump jump around the loop. + This will cause find_basic_blocks to delete it if appropriate. */ + register rtx label = gen_label_rtx (); + emit_label_after (label, p); + redirect_jump (jump, label); + } +} + +/* 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. */ + +/* Data on one SET contained in the instruction. */ + +struct set +{ + /* The SET rtx itself. */ + rtx rtl; + /* The hash-table element for the SET_SRC of the SET. */ + struct table_elt *src_elt; + /* Hash code for the SET_SRC. */ + int src_hash_code; + /* Hash code for the SET_DEST. */ + int dest_hash_code; + /* 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; +}; + +static void +cse_insn (insn) + rtx insn; +{ + register rtx x = PATTERN (insn); + register int i; + register int n_sets = 0; + + /* Records what this insn does to set CC0, + using same encoding used for prev_insn_cc0. */ + int this_insn_cc0 = 0; + /* Likewise, what to store in prev_insn_explicit_cc0. */ + rtx this_insn_explicit_cc0 = 0; + struct write_data writes_memory; + static struct write_data init = {0, 0, 0}; + + rtx src_eqv = 0; + struct table_elt *src_eqv_elt = 0; + int src_eqv_in_memory; + int src_eqv_in_struct; + int src_eqv_hash_code; + + 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 (x) == SET) + { + rtx tem; + n_sets = 1; + sets = (struct set *) alloca (sizeof (struct set)); + sets[0].rtl = x; + + if (REG_NOTES (insn) != 0) + { + /* Store the equivalent value (re REG_EQUAL or REG_EQUIV) in SRC_EQV. */ + tem = find_reg_note (insn, REG_EQUIV, 0); + if (tem == 0) + tem = find_reg_note (insn, REG_EQUAL, 0); + if (tem) src_eqv = XEXP (tem, 0); + + /* Ignore the REG_EQUAL or REG_EQUIV note if its contents + are the same as the source. */ + if (src_eqv && rtx_equal_p (src_eqv, SET_SRC (x))) + src_eqv = 0; + } + + /* Return now for 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) + return; + + /* Return now for call-insns, (set (reg 0) (call ...)). + 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)! */ + if (GET_CODE (SET_SRC (x)) == CALL) + { + canon_reg (SET_SRC (x)); + return; + } + } + 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. */ + for (i = 0; i < lim; i++) + { + register rtx y = XVECEXP (x, 0, i); + if (GET_CODE (y) == CLOBBER && GET_CODE (XEXP (y, 0)) == REG) + invalidate (XEXP (y, 0)); + } + + for (i = 0; i < lim; i++) + { + register rtx y = XVECEXP (x, 0, i); + if (GET_CODE (y) == SET) + 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. */ + canon_reg (y); + 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); + else if (GET_CODE (y) == CALL) + canon_reg (y); + } + } + else if (GET_CODE (x) == CLOBBER) + note_mem_written (XEXP (x, 0), &writes_memory); + else if (GET_CODE (x) == CALL) + canon_reg (x); + + if (n_sets == 0) + { + invalidate_from_clobbers (&writes_memory, x); + return; + } + + /* Canonicalize sources and addresses of destinations. + 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 struct table_elt *elt; + enum machine_mode mode; + + 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; + + /* Replace each registers in SRC with oldest equivalent register, + but if DEST is a register do not replace it if it appears in SRC. */ + + if (GET_CODE (dest) == REG) + { + int tem = reg_qty[REGNO (dest)]; + reg_qty[REGNO (dest)] = REGNO (dest); + src = canon_reg (src); + + if (src_eqv) + src_eqv = canon_reg (src_eqv); + + reg_qty[REGNO (dest)] = tem; + } + else + { + src = canon_reg (src); + + if (src_eqv) + src_eqv = canon_reg (src_eqv); + } + + 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, 0); + src_eqv_hash_code = HASH (src_eqv, eqvmode); + + /* Replace the src_eqv with its cheapest equivalent. */ + + if (!do_not_record) + { + elt = lookup (src_eqv, src_eqv_hash_code, eqvmode); + if (elt && elt != elt->first_same_value) + { + elt = elt->first_same_value; + /* Find the cheapest one that is still valid. */ + while ((GET_CODE (elt->exp) != REG + && !exp_equiv_p (elt->exp, elt->exp, 1)) + || elt->equivalence_only) + elt = elt->next_same_value; + src_eqv = copy_rtx (elt->exp); + hash_arg_in_memory = 0; + hash_arg_in_struct = 0; + src_eqv_hash_code = HASH (src_eqv, elt->mode); + } + src_eqv_elt = elt; + } + else + src_eqv = 0; + + src_eqv_in_memory = hash_arg_in_memory; + src_eqv_in_struct = hash_arg_in_struct; + } + + /* 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; + src = fold_rtx (src, 0); + /* If SRC is a subreg of a reg with a known value, + perform the truncation now. */ + if (GET_CODE (src) == SUBREG) + { + rtx temp = equiv_constant (src); + if (temp) + src = temp; + } + /* If we have (NOT Y), see if Y is known to be (NOT Z). + If so, (NOT Y) simplifies to Z. */ + if (GET_CODE (src) == NOT || GET_CODE (src) == NEG) + { + rtx y = lookup_as_function (XEXP (src, 0), GET_CODE (src)); + if (y != 0) + src = copy_rtx (XEXP (y, 0)); + } + + /* 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. */ + if (GET_CODE (src) == CONST_INT + && GET_CODE (dest) == REG + && qty_const[reg_qty[REGNO (dest)]] == const0_rtx) + REG_NOTES (insn) = gen_rtx (INSN_LIST, REG_WAS_0, + qty_const_insn[reg_qty[REGNO (dest)]], + REG_NOTES (insn)); + + sets[i].src_hash_code = HASH (src, mode); + + sets[i].src_volatile = do_not_record; + +#if 0 + /* This code caused multiple hash-table entries + to be created for registers. Invalidation + would only get one, leaving others that didn't belong. + I don't know what good this ever did. */ + if (GET_CODE (src) == REG) + { + sets[i].src_in_memory = 0; + sets[i].src_elt = 0; + } + else ...; +#endif + /* 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; + else if (!sets[i].src_volatile) + { + /* Replace the source with its cheapest equivalent. */ + + elt = lookup (src, sets[i].src_hash_code, mode); + if (elt && elt != elt->first_same_value) + { + elt = elt->first_same_value; + /* Find the cheapest one that is still valid. */ + while ((GET_CODE (elt->exp) != REG + && !exp_equiv_p (elt->exp, elt->exp, 1)) + || elt->equivalence_only) + elt = elt->next_same_value; + /* Don't replace with things that are not likely to be valid, + such as arithmetic expressions, unless the destination is + a register. */ + if (general_operand (elt->exp, VOIDmode) + || GET_CODE (dest) == REG) + { + src = copy_rtx (elt->exp); + hash_arg_in_memory = 0; + hash_arg_in_struct = 0; + sets[i].src_hash_code = HASH (src, elt->mode); + } + } + + /* If ELT is a constant, is there a register + linearly related to it? If so, replace it + with the sum of that register plus an offset. */ + + if (GET_CODE (src) == CONST && n_sets == 1 + && SET_DEST (sets[i].rtl) != cc0_rtx) + { + rtx newsrc = use_related_value (src, elt); + if (newsrc == 0 && src_eqv != 0) + newsrc = use_related_value (src_eqv, src_eqv_elt); + if (newsrc) + { + rtx oldsrc = src; + src = newsrc; + hash_arg_in_memory = 0; + hash_arg_in_struct = 0; + sets[i].src_hash_code = HASH (src, GET_MODE (src)); + /* The new expression for the SRC has the same value + as the previous one; so if the previous one is in + the hash table, put the new one in as equivalent. */ + if (elt != 0) + elt = insert (src, elt->first_same_value, sets[i].src_hash_code, + elt->mode); + else + { + /* Maybe the new expression is in the table already. */ + elt = lookup (src, sets[i].src_hash_code, mode); + /* And maybe a register contains the same value. */ + if (elt && elt != elt->first_same_value) + { + elt = elt->first_same_value; + /* Find the cheapest one that is still valid. */ + while ((GET_CODE (elt->exp) != REG + && !exp_equiv_p (elt->exp, elt->exp, 1)) + || elt->equivalence_only) + elt = elt->next_same_value; + src = copy_rtx (elt->exp); + hash_arg_in_memory = 0; + hash_arg_in_struct = 0; + sets[i].src_hash_code = HASH (src, elt->mode); + } + } + + /* This would normally be inhibited by the REG_EQUIV + note we are about to make. */ +#if 0 + /* Deleted because the inhibition was deleted. */ + SET_SRC (sets[i].rtl) = src; +#endif + + /* Record the actual constant value + in a REG_EQUIV or REG_EQUAL note. */ + if (GET_CODE (SET_DEST (sets[i].rtl)) == REG) + { + /* A REG_EQUIV note means the dest never changes. + Don't put one on unless there is already one. */ + rtx note = find_reg_note (insn, REG_EQUIV, 0); + if (note != 0) + XEXP (note, 0) = oldsrc; + else + REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_EQUAL, + oldsrc, REG_NOTES (insn)); + } + } + } + + sets[i].src_elt = elt; + sets[i].src_in_memory = hash_arg_in_memory; + sets[i].src_in_struct = hash_arg_in_struct; + } + + /* Either canon_reg or the copy_rtx may have changed this. */ + /* Note it is not safe to replace the sources if there + is more than one set. We could get an insn + [(set (reg) (reg)) (set (reg) (reg))], which is probably + not in the machine description. + This case we could handle by breaking into several insns. + Cases of partial substitution cannot win at all. */ + /* Also, if this insn is setting a "constant" register, + we may not replace the value that is given to it. */ + if (n_sets == 1) +#if 0 + /* Now that the REG_EQUIV contains the constant instead of the reg, + it should be ok to modify the insn's actual source. */ + if (REG_NOTES (insn) == 0 + || REG_NOTE_KIND (REG_NOTES (insn)) != REG_EQUIV) +#endif + SET_SRC (sets[0].rtl) = src; + + 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 (1) + { + if (GET_CODE (dest) == SIGN_EXTRACT + || GET_CODE (dest) == ZERO_EXTRACT) + { + XEXP (dest, 1) = canon_reg (XEXP (dest, 1)); + XEXP (dest, 2) = canon_reg (XEXP (dest, 2)); + sets[i].inner_dest_loc = &XEXP (dest, 0); + dest = XEXP (dest, 0); + } + else if (GET_CODE (dest) == SUBREG + || GET_CODE (dest) == STRICT_LOW_PART) + { + sets[i].inner_dest_loc = &XEXP (dest, 0); + dest = XEXP (dest, 0); + } + else + break; + } + + sets[i].inner_dest = dest; + + /* If storing into memory, do cse on the memory address. + Also 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. */ + if (GET_CODE (dest) == MEM) + { + register rtx addr; + register int hash; + + canon_reg (dest); + dest = fold_rtx (dest, 0); + addr = XEXP (dest, 0); + + /* Pushing or popping does not invalidate anything. */ + 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) + ; + else + /* Otherwise, 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); + + /* Do not try to replace addresses of local and argument slots. + The MEM expressions for args and non-register local variables + 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. It also doesn't do any good! */ + if ((GET_CODE (addr) == PLUS + && GET_CODE (XEXP (addr, 0)) == REG + && GET_CODE (XEXP (addr, 1)) == CONST_INT + && (hash = REGNO (XEXP (addr, 0)), + hash == FRAME_POINTER_REGNUM || hash == ARG_POINTER_REGNUM)) + || (GET_CODE (addr) == REG + && (hash = REGNO (addr), + hash == FRAME_POINTER_REGNUM || hash == ARG_POINTER_REGNUM))) + sets[i].dest_hash_code = ((int)MEM + canon_hash (addr, GET_MODE (dest))) % NBUCKETS; + else + { + /* Look for a simpler equivalent for the destination address. */ + hash = HASH (addr, Pmode); + if (! do_not_record) + { + elt = lookup (addr, hash, Pmode); + sets[i].dest_hash_code = ((int) MEM + hash) % NBUCKETS; + + if (elt && elt != elt->first_same_value) + { + elt = elt->first_same_value; + /* Find the cheapest one that is still valid. */ + while ((GET_CODE (elt->exp) != REG + && !exp_equiv_p (elt->exp, elt->exp, 1)) + || elt->equivalence_only) + elt = elt->next_same_value; + + addr = copy_rtx (elt->exp); + /* Create a new MEM rtx, in case the old one + is shared somewhere else. */ + dest = gen_rtx (MEM, GET_MODE (dest), addr); + MEM_VOLATILE_P (dest) + = MEM_VOLATILE_P (sets[i].inner_dest); + MEM_IN_STRUCT_P (dest) + = MEM_IN_STRUCT_P (sets[i].inner_dest); + *sets[i].inner_dest_loc = dest; + sets[i].inner_dest = dest; + } + } + } + } + + /* 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); + rtx value = equiv_constant (SET_SRC (sets[i].rtl)); + + if (value != 0 && GET_CODE (value) == CONST_INT + && GET_CODE (width) == CONST_INT + && INTVAL (width) < HOST_BITS_PER_INT + && ! (INTVAL (value) & (-1) << INTVAL (width))) + /* Exception: if the value is constant, + we can tell whether truncation would change it. */ + ; + else + sets[i].src_volatile = 1, src_eqv = 0; + } + + /* No further processing for this assignment + if destination is volatile or if the source and destination + are the same. */ + + else if (do_not_record + || (GET_CODE (dest) == REG + ? REGNO (dest) == STACK_POINTER_REGNUM + : GET_CODE (dest) != MEM) + || rtx_equal_p (SET_SRC (sets[i].rtl), SET_DEST (sets[i].rtl))) + sets[i].rtl = 0; + + if (sets[i].rtl != 0 && dest != SET_DEST (sets[i].rtl)) + sets[i].dest_hash_code = HASH (SET_DEST (sets[i].rtl), mode); + + if (dest == cc0_rtx + && (GET_CODE (src) == COMPARE + || CONSTANT_P (src) + || GET_CODE (src) == REG)) + this_insn_cc0 = fold_cc0 (sets[i].mode, src); + + if (dest == cc0_rtx && GET_CODE (src) == CONST_INT) + this_insn_explicit_cc0 = src; + } + + /* Now enter all non-volatile source expressions in the hash table + if they are not already present. + Record in src_elt the heads of their equivalence classes. + 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) + { + register struct table_elt *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))); + if (insert_regs (src_eqv, 0, 0)) + src_eqv_hash_code = HASH (src_eqv, eqvmode); + elt = insert (src_eqv, 0, src_eqv_hash_code, eqvmode); + elt->in_memory = src_eqv_in_memory; + elt->in_struct = src_eqv_in_struct; + elt->equivalence_only = 1; + src_eqv_elt = elt->first_same_value; + } + + for (i = 0; i < n_sets; i++) + if (sets[i].rtl && ! sets[i].src_volatile) + { + 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 equivalent, so we arrange later + to treat the entire reg as the destination. */ + sets[i].src_elt = src_eqv_elt; + sets[i].src_hash_code = src_eqv_hash_code; + } + else if (sets[i].src_elt == 0) + { + register rtx src = SET_SRC (sets[i].rtl); + register rtx dest = SET_DEST (sets[i].rtl); + register struct table_elt *elt; + enum machine_mode mode + = GET_MODE (src) == VOIDmode ? GET_MODE (dest) : GET_MODE (src); + + /* 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, 0, 0)) + sets[i].src_hash_code = HASH (src, mode); + elt = insert (src, src_eqv_elt, sets[i].src_hash_code, mode); + elt->in_memory = sets[i].src_in_memory; + elt->in_struct = sets[i].src_in_struct; + sets[i].src_elt = elt->first_same_value; + } + } + + invalidate_from_clobbers (&writes_memory, x); + + /* 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) + { + register rtx dest = sets[i].inner_dest; + + /* 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 + || (! writes_memory.all && ! cse_rtx_addr_varies_p (dest))) + invalidate (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. */ + + 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 the source is volatile, its destination goes in + a class of its own. */ + if (sets[i].src_volatile) + sets[i].src_elt = 0; + + 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->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; + + if (flag_float_store + && GET_CODE (dest) == MEM + && (GET_MODE (dest) == SFmode || GET_MODE (dest) == DFmode)) + 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) + /* 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. */ + sets[i].dest_hash_code = HASHREG (dest); + + if (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. */ + sets[i].dest_hash_code + = canon_hash (dest, GET_MODE (dest)) % NBUCKETS; + + elt = insert (dest, sets[i].src_elt, sets[i].dest_hash_code, GET_MODE (dest)); + elt->in_memory = GET_CODE (sets[i].inner_dest) == MEM; + if (elt->in_memory) + { + elt->in_struct = (MEM_IN_STRUCT_P (sets[i].inner_dest) + || sets[i].inner_dest != SET_DEST (sets[i].rtl)); + } + } + + /* 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. */ + if (n_sets == 1 && sets[0].rtl && GET_CODE (SET_DEST (sets[0].rtl)) == REG + && GET_CODE (SET_SRC (sets[0].rtl)) == REG + && rtx_equal_p (canon_reg (SET_SRC (sets[0].rtl)), 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, 0); + + SET_DEST (PATTERN (prev)) = dest; + SET_DEST (sets[0].rtl) = SET_SRC (sets[0].rtl); + SET_SRC (sets[0].rtl) = dest; + /* If REG1 was equivalent to a constant, REG0 is not. */ + if (note) + PUT_MODE (note, REG_EQUAL); + } + } + + /* Did this insn become an unconditional branch or become a no-op? */ + if (GET_CODE (insn) == JUMP_INSN + && GET_CODE (x) == SET + && SET_DEST (x) == pc_rtx) + { + if (SET_SRC (x) == pc_rtx) + { + PUT_CODE (insn, NOTE); + NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED; + NOTE_SOURCE_FILE (insn) = 0; + cse_jumps_altered = 1; + /* If previous insn just set CC0 for us, delete it too. */ + if (prev_insn_cc0 != 0 || prev_insn_explicit_cc0 != 0) + { + PUT_CODE (prev_insn, NOTE); + NOTE_LINE_NUMBER (prev_insn) = NOTE_INSN_DELETED; + NOTE_SOURCE_FILE (prev_insn) = 0; + } + /* One less use of the label this insn used to jump to. */ + --LABEL_NUSES (JUMP_LABEL (insn)); + } + else if (GET_CODE (SET_SRC (x)) == LABEL_REF) + { + rtx label; + + emit_barrier_after (insn); + cse_jumps_altered = 1; + /* If previous insn just set CC0 for us, delete it too. */ + if (prev_insn_cc0 != 0 || prev_insn_explicit_cc0 != 0) + { + PUT_CODE (prev_insn, NOTE); + NOTE_LINE_NUMBER (prev_insn) = NOTE_INSN_DELETED; + NOTE_SOURCE_FILE (prev_insn) = 0; + } + /* If jump target is the following label, and this is only use of it, + skip direct to that label and continue optimizing there. */ + label = insn; + while (label != 0 && GET_CODE (label) != CODE_LABEL) + label = NEXT_INSN (label); + if (label == XEXP (SET_SRC (x), 0) + && LABEL_NUSES (label) == 1) + cse_skip_to_next_block = 1; + } + } + + /* If this insn used to store a value based on CC0 but now value is constant, + and the previous insn just set CC0 for us, delete 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 (GET_CODE (x) == SET && prev_insn_cc0 + && CONSTANT_P (SET_SRC (x))) + { + PUT_CODE (prev_insn, NOTE); + NOTE_LINE_NUMBER (prev_insn) = NOTE_INSN_DELETED; + NOTE_SOURCE_FILE (prev_insn) = 0; + } + + prev_insn_explicit_cc0 = this_insn_explicit_cc0; + prev_insn_cc0 = this_insn_cc0; + 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 = {1, 1, 1}; + + if (written == 0) + *writes_ptr = everything; + else if (GET_CODE (written) == MEM) + { + /* Pushing or popping the stack invalidates nothing. */ + 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) + return; + if (GET_MODE (written) == BLKmode) + *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. */ + if (!(MEM_IN_STRUCT_P (written) + || GET_CODE (XEXP (written, 0)) == PLUS)) + 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 (GET_CODE (x) == CLOBBER) + { + rtx ref = XEXP (x, 0); + if (ref + && (GET_CODE (ref) == REG || GET_CODE (ref) == SUBREG + || (GET_CODE (ref) == MEM && ! w->all))) + invalidate (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 + &&(GET_CODE (ref) == REG || GET_CODE (ref) == SUBREG + || (GET_CODE (ref) == MEM && !w->all))) + invalidate (ref); + } + } + } +} + +/* Find the end of INSN's basic block, and return the cuid of its last insn + and the total number of SETs in all the insns of the block. */ + +struct cse_basic_block_data { int cuid, nsets; rtx last; }; + +static struct cse_basic_block_data +cse_end_of_basic_block (insn) + rtx insn; +{ + rtx p = insn; + struct cse_basic_block_data val; + int nsets = 0; + int last_uid = 0; + + /* 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. + The occasional optimizations lost by this will all come back + if loop and cse are made to work alternatingly. */ + if (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_CODE (p) == INSN && GET_CODE (PATTERN (p)) == PARALLEL) + nsets += XVECLEN (PATTERN (p), 0); + else + nsets += 1; + + last_uid = INSN_UID (p); + p = NEXT_INSN (p); + } + val.cuid = uid_cuid[last_uid]; + val.nsets = nsets; + val.last = p; + + return val; +} + +static rtx cse_basic_block (); + +/* 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. + + Returns 1 if jump_optimize should be redone due to simplifications + in conditional jump instructions. */ + +int +cse_main (f, nregs) + /* f is the first instruction of a chain of insns for one function */ + rtx f; + /* nregs is the total number of registers used in it */ + int nregs; +{ + register rtx insn = f; + register int i; + + cse_jumps_altered = 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_rtx = (rtx *) alloca (nregs * sizeof (rtx)); + reg_in_table = (int *) alloca (nregs * sizeof (int)); + reg_tick = (int *) alloca (nregs * sizeof (int)); + + /* Discard all the free elements of the previous function + since they are allocated in the temporarily obstack. */ + bzero (table, sizeof table); + free_element_chain = 0; + n_elements_made = 0; + + /* Find the largest uid. */ + + for (insn = f, i = 0; insn; insn = NEXT_INSN (insn)) + if (INSN_UID (insn) > i) + i = INSN_UID (insn); + + uid_cuid = (short *) alloca ((i + 1) * sizeof (short)); + bzero (uid_cuid, (i + 1) * sizeof (short)); + + /* 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; + } + + /* 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) + { + struct cse_basic_block_data val; + + val = cse_end_of_basic_block (insn); + + cse_basic_block_end = val.cuid; + cse_basic_block_start = INSN_CUID (insn); + max_qty = val.nsets * 2; + + /* 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; + + insn = cse_basic_block (insn, val.last); +#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; +} + +static rtx +cse_basic_block (from, to) + register rtx from, to; +{ + register rtx insn; + int *qv1 = (int *) alloca (max_qty * sizeof (int)); + int *qv2 = (int *) alloca (max_qty * sizeof (int)); + rtx *qv3 = (rtx *) alloca (max_qty * sizeof (rtx)); + + qty_first_reg = qv1; + qty_last_reg = qv2; + qty_const = qv3; + qty_const_insn = (rtx *) alloca (max_qty * sizeof (rtx)); + + new_basic_block (); + + cse_skip_to_next_block = 0; + + for (insn = from; insn != to; insn = NEXT_INSN (insn)) + { + register enum rtx_code code; + + code = GET_CODE (insn); + + if (code == INSN || code == JUMP_INSN || code == CALL_INSN) + cse_insn (insn); + /* Memory, and some registers, are invalidate by subroutine calls. */ + if (code == CALL_INSN) + { + register int i; + static struct write_data everything = {1, 1, 1}; + invalidate_memory (&everything); + for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) + if (call_used_regs[i] && reg_rtx[i] + && i != FRAME_POINTER_REGNUM + && i != ARG_POINTER_REGNUM) + invalidate (reg_rtx[i]); + } + /* Loop beginnings are often followed by jumps + (that enter the loop above the endtest). + See if we can prove the loop will be executed at least once; + if so, delete the jump. Also perhaps we can prove loop + will never be executed and delete the entire thing. */ + if (code == NOTE + && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG + && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN) + { + predecide_loop_entry (insn); + /* Whether that jump was deleted or not, + it certainly is the end of the basic block. + Since the jump is unconditional, + it requires no further processing here. */ + break; + } + + /* See if it is ok to keep on going past the label + which used to end our basic block. */ + if (cse_skip_to_next_block + || (to != 0 && NEXT_INSN (insn) == to && LABEL_NUSES (to) == 0)) + { + struct cse_basic_block_data val; + + /* Skip the remaining insns in this block. */ + cse_skip_to_next_block = 0; + insn = to; + if (insn == 0) + break; + + /* Find the end of the following block. */ + val = cse_end_of_basic_block (NEXT_INSN (insn)); + + /* 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_end = val.cuid; + to = val.last; + } + } + + if (next_qty > max_qty) + abort (); + + return to ? NEXT_INSN (to) : 0; +} |