home *** CD-ROM | disk | FTP | other *** search
/ Education Sampler 1992 [NeXTSTEP] / Education_1992_Sampler.iso / NeXT / GnuSource / cc-61.0.1 / cc / cse.c < prev    next >
C/C++ Source or Header  |  1991-08-05  |  191KB  |  6,237 lines
  1. /* Common subexpression elimination for GNU compiler.
  2.    Copyright (C) 1987-1991 Free Software Foundation, Inc.
  3.  
  4. This file is part of GNU CC.
  5.  
  6. GNU CC is free software; you can redistribute it and/or modify
  7. it under the terms of the GNU General Public License as published by
  8. the Free Software Foundation; either version 2, or (at your option)
  9. any later version.
  10.  
  11. GNU CC is distributed in the hope that it will be useful,
  12. but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. GNU General Public License for more details.
  15.  
  16. You should have received a copy of the GNU General Public License
  17. along with GNU CC; see the file COPYING.  If not, write to
  18. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  19.  
  20.  
  21. #include "config.h"
  22. #include "rtl.h"
  23. #include "regs.h"
  24. #include "hard-reg-set.h"
  25. #include "flags.h"
  26. #include "real.h"
  27. #include "insn-config.h"
  28. #include "recog.h"
  29.  
  30. #include <stdio.h>
  31. #include <setjmp.h>
  32.  
  33. #define max(A,B) ((A) > (B) ? (A) : (B))
  34. #define min(A,B) ((A) < (B) ? (A) : (B))
  35.  
  36. /* The basic idea of common subexpression elimination is to go
  37.    through the code, keeping a record of expressions that would
  38.    have the same value at the current scan point, and replacing
  39.    expressions encountered with the cheapest equivalent expression.
  40.  
  41.    It is too complicated to keep track of the different possibilities
  42.    when control paths merge; so, at each label, we forget all that is
  43.    known and start fresh.  This can be described as processing each
  44.    basic block separately.  Note, however, that these are not quite
  45.    the same as the basic blocks found by a later pass and used for
  46.    data flow analysis and register packing.  We do not need to start fresh
  47.    after a conditional jump instruction if there is no label there.
  48.  
  49.    We use two data structures to record the equivalent expressions:
  50.    a hash table for most expressions, and several vectors together
  51.    with "quantity numbers" to record equivalent (pseudo) registers.
  52.  
  53.    The use of the special data structure for registers is desirable
  54.    because it is faster.  It is possible because registers references
  55.    contain a fairly small number, the register number, taken from
  56.    a contiguously allocated series, and two register references are
  57.    identical if they have the same number.  General expressions
  58.    do not have any such thing, so the only way to retrieve the
  59.    information recorded on an expression other than a register
  60.    is to keep it in a hash table.
  61.  
  62. Registers and "quantity numbers":
  63.    
  64.    At the start of each basic block, all of the (hardware and pseudo)
  65.    registers used in the function are given distinct quantity
  66.    numbers to indicate their contents.  During scan, when the code
  67.    copies one register into another, we copy the quantity number.
  68.    When a register is loaded in any other way, we allocate a new
  69.    quantity number to describe the value generated by this operation.
  70.    `reg_qty' records what quantity a register is currently thought
  71.    of as containing.
  72.  
  73.    All real quantity numbers are greater than or equal to `max_reg'.
  74.    If register N has not been assigned a quantity, reg_qty[N] will equal N.
  75.  
  76.    Quantity numbers below `max_reg' do not exist and none of the `qty_...'
  77.    variables should be referenced with an index below `max_reg'.
  78.  
  79.    We also maintain a bidirectional chain of registers for each
  80.    quantity number.  `qty_first_reg', `qty_last_reg',
  81.    `reg_next_eqv' and `reg_prev_eqv' hold these chains.
  82.  
  83.    The first register in a chain is the one whose lifespan is least local.
  84.    Among equals, it is the one that was seen first.
  85.    We replace any equivalent register with that one.
  86.  
  87. Constants and quantity numbers
  88.  
  89.    When a quantity has a known constant value, that value is stored
  90.    in the appropriate element of qty_const.  This is in addition to
  91.    putting the constant in the hash table as is usual for non-regs.
  92.  
  93.    Whether a reg or a constant is prefered is determined by the configuration
  94.    macro CONST_COSTS and will often depend on the constant value.  In any
  95.    event, expressions containing constants can be simplified, by fold_rtx.
  96.  
  97.    When a quantity has a known nearly constant value (such as an address
  98.    of a stack slot), that value is stored in the appropriate element
  99.    of qty_const.
  100.  
  101.    Integer constants don't have a machine mode.  However, cse
  102.    determines the intended machine mode from the destination
  103.    of the instruction that moves the constant.  The machine mode
  104.    is recorded in the hash table along with the actual RTL
  105.    constant expression so that different modes are kept separate.
  106.  
  107. Other expressions:
  108.  
  109.    To record known equivalences among expressions in general
  110.    we use a hash table called `table'.  It has a fixed number of buckets
  111.    that contain chains of `struct table_elt' elements for expressions.
  112.    These chains connect the elements whose expressions have the same
  113.    hash codes.
  114.  
  115.    Other chains through the same elements connect the elements which
  116.    currently have equivalent values.
  117.  
  118.    Register references in an expression are canonicalized before hashing
  119.    the expression.  This is done using `reg_qty' and `qty_first_reg'.
  120.    The hash code of a register reference is computed using the quantity
  121.    number, not the register number.
  122.  
  123.    When the value of an expression changes, it is necessary to remove from the
  124.    hash table not just that expression but all expressions whose values
  125.    could be different as a result.
  126.  
  127.      1. If the value changing is in memory, except in special cases
  128.      ANYTHING referring to memory could be changed.  That is because
  129.      nobody knows where a pointer does not point.
  130.      The function `invalidate_memory' removes what is necessary.
  131.  
  132.      The special cases are when the address is constant or is
  133.      a constant plus a fixed register such as the frame pointer
  134.      or a static chain pointer.  When such addresses are stored in,
  135.      we can tell exactly which other such addresses must be invalidated
  136.      due to overlap.  `invalidate' does this.
  137.      All expressions that refer to non-constant
  138.      memory addresses are also invalidated.  `invalidate_memory' does this.
  139.  
  140.      2. If the value changing is a register, all expressions
  141.      containing references to that register, and only those,
  142.      must be removed.
  143.  
  144.    Because searching the entire hash table for expressions that contain
  145.    a register is very slow, we try to figure out when it isn't necessary.
  146.    Precisely, this is necessary only when expressions have been
  147.    entered in the hash table using this register, and then the value has
  148.    changed, and then another expression wants to be added to refer to
  149.    the register's new value.  This sequence of circumstances is rare
  150.    within any one basic block.
  151.  
  152.    The vectors `reg_tick' and `reg_in_table' are used to detect this case.
  153.    reg_tick[i] is incremented whenever a value is stored in register i.
  154.    reg_in_table[i] holds -1 if no references to register i have been
  155.    entered in the table; otherwise, it contains the value reg_tick[i] had
  156.    when the references were entered.  If we want to enter a reference
  157.    and reg_in_table[i] != reg_tick[i], we must scan and remove old references.
  158.    Until we want to enter a new entry, the mere fact that the two vectors
  159.    don't match makes the entries be ignored if anyone tries to match them.
  160.  
  161.    Registers themselves are entered in the hash table as well as in
  162.    the equivalent-register chains.  However, the vectors `reg_tick'
  163.    and `reg_in_table' do not apply to expressions which are simple
  164.    register references.  These expressions are removed from the table
  165.    immediately when they become invalid, and this can be done even if
  166.    we do not immediately search for all the expressions that refer to
  167.    the register.
  168.  
  169.    A CLOBBER rtx in an instruction invalidates its operand for further
  170.    reuse.  A CLOBBER or SET rtx whose operand is a MEM:BLK
  171.    invalidates everything that resides in memory.
  172.  
  173. Related expressions:
  174.  
  175.    Constant expressions that differ only by an additive integer
  176.    are called related.  When a constant expression is put in
  177.    the table, the related expression with no constant term
  178.    is also entered.  These are made to point at each other
  179.    so that it is possible to find out if there exists any
  180.    register equivalent to an expression related to a given expression.  */
  181.    
  182. /* One plus largest register number used in this function.  */
  183.  
  184. static int max_reg;
  185.  
  186. /* Length of vectors indexed by quantity number.
  187.    We know in advance we will not need a quantity number this big.  */
  188.  
  189. static int max_qty;
  190.  
  191. /* Next quantity number to be allocated.
  192.    This is 1 + the largest number needed so far.  */
  193.  
  194. static int next_qty;
  195.  
  196. /* Indexed by quantity number, gives the first (or last) (pseudo) register 
  197.    in the chain of registers that currently contain this quantity.  */
  198.  
  199. static int *qty_first_reg;
  200. static int *qty_last_reg;
  201.  
  202. /* Indexed by quantity number, gives the rtx of the constant value of the
  203.    quantity, or zero if it does not have a known value.
  204.    A sum of the frame pointer (or arg pointer) plus a constant
  205.    can also be entered here.  */
  206.  
  207. static rtx *qty_const;
  208.  
  209. /* Indexed by qty number, gives the insn that stored the constant value
  210.    recorded in `qty_const'.  */
  211.  
  212. static rtx *qty_const_insn;
  213.  
  214. /* The next three variables are used to track when a comparison between a
  215.    quantity and some constant or register has been passed.  In that case, we
  216.    know the results of the comparison in case we see it again.  These variables
  217.    record a comparison that is known to be true.  */
  218.  
  219. /* Indexed by qty number, gives the rtx code of a comparison with a known
  220.    result involving this quantity.  If none, it is UNKNOWN.  */
  221. static enum rtx_code *qty_comparison_code;
  222.  
  223. /* Indexed by qty number, gives the constant being compared against in a
  224.    comparison of known result.  If no such comparison, it is undefined.
  225.    If the comparison is not with a constant, it is zero.  */
  226.  
  227. static rtx *qty_comparison_const;
  228.  
  229. /* Indexed by qty number, gives the quantity being compared against in a
  230.    comparison of known result.  If no such comparison, if it undefined.
  231.    If the comparison is not with a register, it is -1.  */
  232.  
  233. static int *qty_comparison_qty;
  234.  
  235. #ifdef HAVE_cc0
  236. /* For machines that have a CC0, we do not record its value in the hash
  237.    table since its use is guaranteed to be the insn immediately following
  238.    its definition and any other insn is presumed to invalidate it.
  239.  
  240.    Instead, we store below the value last assigned to CC0.  If it should
  241.    happen to be a constant, it is stored in preference to the actual
  242.    assigned value.  */
  243.  
  244. static rtx prev_insn_cc0;
  245. #endif
  246.  
  247. /* Previous actual insn.  0 if at first insn of basic block.  */
  248.  
  249. static rtx prev_insn;
  250.  
  251. /* Insn being scanned.  */
  252.  
  253. static rtx this_insn;
  254.  
  255. /* Index by (pseudo) register number, gives the quantity number
  256.    of the register's current contents.  */
  257.  
  258. static int *reg_qty;
  259.  
  260. /* Index by (pseudo) register number, gives the number of the next (or
  261.    previous) (pseudo) register in the chain of registers sharing the same
  262.    value.
  263.  
  264.    Or -1 if this register is at the end of the chain.
  265.  
  266.    If reg_qty[N] == N, reg_next_eqv[N] is undefined.  */
  267.  
  268. static int *reg_next_eqv;
  269. static int *reg_prev_eqv;
  270.  
  271. /* Index by (pseudo) register number, gives the latest rtx
  272.    to use to insert a ref to that register.  */
  273.  
  274. static rtx *reg_rtx;
  275.  
  276. /* Index by (pseudo) register number, gives the number of times
  277.    that register has been altered in the current basic block.  */
  278.  
  279. static int *reg_tick;
  280.  
  281. /* Index by (pseudo) register number, gives the reg_tick value at which
  282.    rtx's containing this register are valid in the hash table.
  283.    If this does not equal the current reg_tick value, such expressions
  284.    existing in the hash table are invalid.
  285.    If this is -1, no expressions containing this register have been
  286.    entered in the table.  */
  287.  
  288. static int *reg_in_table;
  289.  
  290. /* Two vectors of ints:
  291.    one containing max_reg -1's; the other max_reg + 500 (an approximation
  292.    for max_qty) elements where element i contains i.
  293.    These are used to initialize various other vectors fast.  */
  294.  
  295. static int *all_minus_one;
  296. static int *consec_ints;
  297.  
  298. /* Set nonzero in cse_insn to tell cse_basic_block to skip immediately
  299.    to the next basic block and treat it as a continuation of this one.  */
  300.  
  301. static int cse_skip_to_next_block;
  302.  
  303. /* CUID of insn that starts the basic block currently being cse-processed.  */
  304.  
  305. static int cse_basic_block_start;
  306.  
  307. /* CUID of insn that ends the basic block currently being cse-processed.  */
  308.  
  309. static int cse_basic_block_end;
  310.  
  311. /* Vector mapping INSN_UIDs to cuids.
  312.    The cuids are like uids but increase monononically always.
  313.    We use them to see whether a reg is used outside a given basic block.  */
  314.  
  315. static short *uid_cuid;
  316.  
  317. /* Get the cuid of an insn.  */
  318.  
  319. #define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
  320.  
  321. /* Nonzero if cse has altered conditional jump insns
  322.    in such a way that jump optimization should be redone.  */
  323.  
  324. static int cse_jumps_altered;
  325.  
  326. /* canon_hash stores 1 in do_not_record
  327.    if it notices a reference to CC0, PC, or some other volatile
  328.    subexpression.  */
  329.  
  330. static int do_not_record;
  331.  
  332. /* canon_hash stores 1 in hash_arg_in_memory
  333.    if it notices a reference to memory within the expression being hashed.  */
  334.  
  335. static int hash_arg_in_memory;
  336.  
  337. /* canon_hash stores 1 in hash_arg_in_struct
  338.    if it notices a reference to memory that's part of a structure.  */
  339.  
  340. static int hash_arg_in_struct;
  341.  
  342. /* The hash table contains buckets which are chains of `struct table_elt's,
  343.    each recording one expression's information.
  344.    That expression is in the `exp' field.
  345.  
  346.    Those elements with the same hash code are chained in both directions
  347.    through the `next_same_hash' and `prev_same_hash' fields.
  348.  
  349.    Each set of expressions with equivalent values
  350.    are on a two-way chain through the `next_same_value'
  351.    and `prev_same_value' fields, and all point with
  352.    the `first_same_value' field at the first element in
  353.    that chain.  The chain is in order of increasing cost.
  354.    Each element's cost value is in its `cost' field.
  355.  
  356.    The `in_memory' field is nonzero for elements that
  357.    involve any reference to memory.  These elements are removed
  358.    whenever a write is done to an unidentified location in memory.
  359.    To be safe, we assume that a memory address is unidentified unless
  360.    the address is either a symbol constant or a constant plus
  361.    the frame pointer or argument pointer.
  362.  
  363.    The `in_struct' field is nonzero for elements that
  364.    involve any reference to memory inside a structure or array.
  365.  
  366.    The `related_value' field is used to connect related expressions
  367.    (that differ by adding an integer).
  368.    The related expressions are chained in a circular fashion.
  369.    `related_value' is zero for expressions for which this
  370.    chain is not useful.
  371.  
  372.    The `cost' field stores the cost of this element's expression.
  373.  
  374.    The `is_const' flag is set if the element is a constant (including
  375.    a fixed address).
  376.  
  377.    The `flag' field is used as a temporary during some search routines.
  378.  
  379.    The `mode' field is usually the same as GET_MODE (`exp'), but
  380.    if `exp' is a CONST_INT and has no machine mode then the `mode'
  381.    field is the mode it was being used as.  Each constant is
  382.    recorded separately for each mode it is used with.  */
  383.  
  384.  
  385. struct table_elt
  386. {
  387.   rtx exp;
  388.   struct table_elt *next_same_hash;
  389.   struct table_elt *prev_same_hash;
  390.   struct table_elt *next_same_value;
  391.   struct table_elt *prev_same_value;
  392.   struct table_elt *first_same_value;
  393.   struct table_elt *related_value;
  394.   int cost;
  395.   enum machine_mode mode;
  396.   char in_memory;
  397.   char in_struct;
  398.   char is_const;
  399.   char flag;
  400. };
  401.  
  402. #define HASHBITS 16
  403.  
  404. /* We don't want a lot of buckets, because we rarely have very many
  405.    things stored in the hash table, and a lot of buckets slows
  406.    down a lot of loops that happen frequently.  */
  407. #define NBUCKETS 31
  408.  
  409. /* Compute hash code of RTX, known to be a register.  */
  410.  
  411. #define HASHREG(RTX) \
  412.  ((((int) REG << 7) + reg_qty[REGNO (RTX)]) % NBUCKETS)
  413.  
  414. /* Compute hash code of X in mode M.  Special-case case where X is a pseudo
  415.    register (hard registers may require `do_not_record' to be set).  */
  416.  
  417. #define HASH(X, M)    \
  418.  (GET_CODE (X) == REG && REGNO (X) >= FIRST_PSEUDO_REGISTER ? HASHREG (X) \
  419.   : canon_hash (X, M) % NBUCKETS)
  420.  
  421. /* Determine whether register number N is considered a fixed register for CSE.
  422.    It is desirable to replace other regs with fixed regs, to reduce need for
  423.    non-fixed hard regs.
  424.    A reg wins if it is either the frame pointer or designated as fixed,
  425.    but not if it is an overlapping register.  */
  426. #ifdef OVERLAPPING_REGNO_P
  427. #define FIXED_REGNO_P(N)  \
  428.   (((N) == FRAME_POINTER_REGNUM || fixed_regs[N])    \
  429.    && ! OVERLAPPING_REGNO_P ((N)))
  430. #else
  431. #define FIXED_REGNO_P(N)  \
  432.   ((N) == FRAME_POINTER_REGNUM || fixed_regs[N])
  433. #endif
  434.  
  435. /* Compute cost of X, as stored in the `cost' field of a table_elt.  Fixed
  436.    hard registers are the cheapest with a cost of 0.  Next come pseudos
  437.    with a cost of one and other hard registers with a cost of 2.  Aside
  438.    from these special cases, call `rtx_cost'.  */
  439.  
  440. #define COST(X)                        \
  441.   (GET_CODE (X) == REG                    \
  442.    ? (REGNO (X) >= FIRST_PSEUDO_REGISTER ? 1        \
  443.       : (FIXED_REGNO_P (REGNO (X))            \
  444.      && REGNO_REG_CLASS (REGNO (X)) != NO_REGS) ? 0    \
  445.       : 2)                        \
  446.    : rtx_cost (X) * 2)                    \
  447.  
  448. /* Determine if the quantity number for register X represents a valid index
  449.    into the `qty_...' variables.  */
  450.  
  451. #define REGNO_QTY_VALID_P(N) (reg_qty[N] != (N))
  452.  
  453. static struct table_elt *table[NBUCKETS];
  454.  
  455. /* Chain of `struct table_elt's made so far for this function
  456.    but currently removed from the table.  */
  457.  
  458. static struct table_elt *free_element_chain;
  459.  
  460. /* Number of `struct table_elt' structures made so far for this function.  */
  461.  
  462. static int n_elements_made;
  463.  
  464. /* Maximum value `n_elements_made' has had so far in this compilation
  465.    for functions previously processed.  */
  466.  
  467. static int max_elements_made;
  468.  
  469. /* Surviving equivalence class when two equivalence classes are merged 
  470.    by recording the effects of a jump in the last insn.  Zero if the
  471.    last insn was not a conditional jump.  */
  472.  
  473. static struct table_elt *last_jump_equiv_class;
  474.  
  475. /* Set to the cost of a constant pool reference if one was found for a
  476.    symbolic constant.  If this was found, it means we should try to
  477.    convert constants into constant pool entries if they don't fit in
  478.    the insn.  */
  479.  
  480. static int constant_pool_entries_cost;
  481.  
  482. /* Bits describing what kind of values in memory must be invalidated
  483.    for a particular instruction.  If all three bits are zero,
  484.    no memory refs need to be invalidated.  Each bit is more powerful
  485.    than the preceding ones, and if a bit is set then the preceding
  486.    bits are also set.
  487.  
  488.    Here is how the bits are set:
  489.    Pushing onto the stack invalidates only the stack pointer,
  490.    writing at a fixed address invalidates only variable addresses,
  491.    writing in a structure element at variable address
  492.      invalidates all but scalar variables,
  493.    and writing in anything else at variable address invalidates everything.  */
  494.  
  495. struct write_data
  496. {
  497.   int sp : 1;            /* Invalidate stack pointer. */
  498.   int var : 1;            /* Invalidate variable addresses.  */
  499.   int nonscalar : 1;        /* Invalidate all but scalar variables.  */
  500.   int all : 1;            /* Invalidate all memory refs.  */
  501. };
  502.  
  503. /* Nonzero if X has the form (PLUS frame-pointer integer).  */
  504.  
  505. #define FIXED_BASE_PLUS_P(X)                    \
  506.   (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT    \
  507.    && (XEXP (X, 0) == frame_pointer_rtx || XEXP (X, 0) == arg_pointer_rtx \
  508.        || XEXP (X, 0) == virtual_stack_vars_rtx))
  509.  
  510. static struct table_elt *lookup ();
  511. static void free_element ();
  512.  
  513. static void remove_invalid_refs ();
  514. static int exp_equiv_p ();
  515. int refers_to_p ();
  516. int refers_to_mem_p ();
  517. static void invalidate_from_clobbers ();
  518. static int safe_hash ();
  519. static int canon_hash ();
  520. static rtx fold_rtx ();
  521. static rtx equiv_constant ();
  522. static void note_mem_written ();
  523. static int cse_rtx_addr_varies_p ();
  524. static enum rtx_code find_comparison_args ();
  525. static void cse_insn ();
  526. static void cse_set_around_loop ();
  527.  
  528. /* Return an estimate of the cost of computing rtx X.
  529.    One use is in cse, to decide which expression to keep in the hash table.
  530.    Another is in rtl generation, to pick the cheapest way to multiply.
  531.    Other uses like the latter are expected in the future.  */
  532.  
  533. /* Return the right cost to give to an operation
  534.    to make the cost of the corresponding register-to-register instruction
  535.    N times that of a fast register-to-register instruction.  */
  536.  
  537. #define COSTS_N_INSNS(N) ((N) * 4 - 2)
  538.  
  539. int
  540. rtx_cost (x)
  541.      rtx x;
  542. {
  543.   register int i, j;
  544.   register enum rtx_code code;
  545.   register char *fmt;
  546.   register int total;
  547.  
  548.   if (x == 0)
  549.     return 0;
  550.  
  551.   /* Compute the default costs of certain things.
  552.      Note that RTX_COSTS can override the defaults.  */
  553.  
  554.   code = GET_CODE (x);
  555.   switch (code)
  556.     {
  557.     case MULT:
  558.       /* Count multiplication by 2**n as a shift,
  559.      because if we are considering it, we would output it as a shift.  */
  560.       if (GET_CODE (XEXP (x, 1)) == CONST_INT
  561.       && exact_log2 (INTVAL (XEXP (x, 1))) >= 0)
  562.     total = 2;
  563.       else
  564.     total = COSTS_N_INSNS (5);
  565.       break;
  566.     case DIV:
  567.     case UDIV:
  568.     case MOD:
  569.     case UMOD:
  570.       total = COSTS_N_INSNS (7);
  571.       break;
  572.     default:
  573.       total = 2;
  574.     }
  575.  
  576.   switch (code)
  577.     {
  578.     case REG:
  579.       return 1;
  580.     case SUBREG:
  581.       return 2;
  582. #ifdef RTX_COSTS
  583.       RTX_COSTS (x, code);
  584. #endif 
  585.       CONST_COSTS (x, code);
  586.     }
  587.  
  588.   /* Sum the costs of the sub-rtx's, plus cost of this operation,
  589.      which is already in total.  */
  590.  
  591.   fmt = GET_RTX_FORMAT (code);
  592.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  593.     if (fmt[i] == 'e')
  594.       total += rtx_cost (XEXP (x, i));
  595.     else if (fmt[i] == 'E')
  596.       for (j = 0; j < XVECLEN (x, i); j++)
  597.     total += rtx_cost (XVECEXP (x, i, j));
  598.  
  599.   return total;
  600. }
  601.  
  602. /* Clear the hash table and initialize each register with its own quantity,
  603.    for a new basic block.  */
  604.  
  605. static void
  606. new_basic_block ()
  607. {
  608.   register int i;
  609.  
  610.   next_qty = max_reg;
  611.  
  612.   /* Note that we need not clear reg_rtx for a new block.  */
  613.  
  614.   bzero (reg_tick, max_reg * sizeof (int));
  615.  
  616.   bcopy (all_minus_one, reg_in_table, max_reg * sizeof (int));
  617.   bcopy (consec_ints, reg_qty, max_reg * sizeof (int));
  618.  
  619.   /* The per-quantity values used to be initialized here, but it is
  620.      much faster to initialize each as it is made in `make_new_qty'.  */
  621.  
  622.   for (i = 0; i < NBUCKETS; i++)
  623.     {
  624.       register struct table_elt *this, *next;
  625.       for (this = table[i]; this; this = next)
  626.     {
  627.       next = this->next_same_hash;
  628.       free_element (this);
  629.     }
  630.     }
  631.  
  632.   bzero (table, sizeof table);
  633.  
  634.   prev_insn = 0;
  635.  
  636. #ifdef HAVE_cc0
  637.   prev_insn_cc0 = 0;
  638. #endif
  639. }
  640.  
  641. /* Say that register REG contains a quantity not in any register before
  642.    and initialize that quantity.  */
  643.  
  644. static void
  645. make_new_qty (reg)
  646.      register int reg;
  647. {
  648.   register int q;
  649.  
  650.   if (next_qty >= max_qty)
  651.     abort ();
  652.  
  653.   q = reg_qty[reg] = next_qty++;
  654.   qty_first_reg[q] = reg;
  655.   qty_last_reg[q] = reg;
  656.   qty_const[q] = qty_const_insn[q] = 0;
  657.   qty_comparison_code[q] = UNKNOWN;
  658.  
  659.   reg_next_eqv[reg] = reg_prev_eqv[reg] = -1;
  660. }
  661.  
  662. /* Make reg NEW equivalent to reg OLD.
  663.    OLD is not changing; NEW is.  */
  664.  
  665. static void
  666. make_regs_eqv (new, old)
  667.      register int new, old;
  668. {
  669.   register int lastr, firstr;
  670.   register int q = reg_qty[old];
  671.  
  672.   /* Nothing should become eqv until it has a "non-invalid" qty number.  */
  673.   if (! REGNO_QTY_VALID_P (old))
  674.     abort ();
  675.  
  676.   reg_qty[new] = q;
  677.   firstr = qty_first_reg[q];
  678.   lastr = qty_last_reg[q];
  679.  
  680.   /* Prefer fixed hard registers to anything.  Prefer pseudo regs to other
  681.      hard regs.  Among pseudos, if NEW will live longer than any other reg
  682.      of the same qty, and that is beyond the current basic block,
  683.      make it the new canonical replacement for this qty.  */
  684.   if (! (firstr < FIRST_PSEUDO_REGISTER && FIXED_REGNO_P (firstr))
  685.       /* Certain fixed registers might be of the class NO_REGS.  This means
  686.      that not only can they not be allocated by the compiler, but
  687.      they cannot be used in substitutions or cannonicallizations
  688.      either.  */
  689.       && (new >= FIRST_PSEUDO_REGISTER || REGNO_REG_CLASS (new) != NO_REGS)
  690.       && ((new < FIRST_PSEUDO_REGISTER && FIXED_REGNO_P (new))
  691.       || (new >= FIRST_PSEUDO_REGISTER
  692.           && (firstr < FIRST_PSEUDO_REGISTER
  693.           || ((uid_cuid[regno_last_uid[new]] > cse_basic_block_end
  694.                || (uid_cuid[regno_first_uid[new]]
  695.                < cse_basic_block_start))
  696.               && (uid_cuid[regno_last_uid[new]]
  697.               > uid_cuid[regno_last_uid[firstr]]))))))
  698.     {
  699.       reg_prev_eqv[firstr] = new;
  700.       reg_next_eqv[new] = firstr;
  701.       reg_prev_eqv[new] = -1;
  702.       qty_first_reg[q] = new;
  703.     }
  704.   else
  705.     {
  706.       /* If NEW is a hard reg (known to be non-fixed), insert at end.
  707.      Otherwise, insert before any non-fixed hard regs that are at the
  708.      end.  Registers of class NO_REGS cannot be used as an
  709.      equivalent for anything.  */
  710.       while (lastr < FIRST_PSEUDO_REGISTER && reg_prev_eqv[lastr] >= 0
  711.          && (REGNO_REG_CLASS (lastr) == NO_REGS || ! FIXED_REGNO_P (lastr))
  712.          && new >= FIRST_PSEUDO_REGISTER)
  713.     lastr = reg_prev_eqv[lastr];
  714.       reg_next_eqv[new] = reg_next_eqv[lastr];
  715.       if (reg_next_eqv[lastr] >= 0)
  716.     reg_prev_eqv[reg_next_eqv[lastr]] = new;
  717.       else
  718.     qty_last_reg[q] = new;
  719.       reg_next_eqv[lastr] = new;
  720.       reg_prev_eqv[new] = lastr;
  721.     }
  722. }
  723.  
  724. /* Discard the records of what is in register REG.  If SAME_VALUE is non-zero,
  725.    the value of the register itself isn't changing, it's just that we know
  726.    more about its value and want to put it in another class.  */
  727.  
  728. static void
  729. reg_invalidate (reg, same_value)
  730.      register int reg;
  731.      register int same_value;
  732. {
  733.   register int n = reg_next_eqv[reg];
  734.   register int p = reg_prev_eqv[reg];
  735.   register int q = reg_qty[reg];
  736.  
  737.   if (! same_value)
  738.     reg_tick[reg]++;
  739.  
  740.   /* If invalid, do nothing.  N and P above are undefined in that case.  */
  741.   if (q == reg)
  742.     return;
  743.  
  744.   if (n != -1)
  745.     reg_prev_eqv[n] = p;
  746.   else
  747.     qty_last_reg[q] = p;
  748.   if (p != -1)
  749.     reg_next_eqv[p] = n;
  750.   else
  751.     qty_first_reg[q] = n;
  752.  
  753.   reg_qty[reg] = reg;
  754. }
  755.  
  756. /* Remove any invalid expressions from the hash table
  757.    that refer to any of the registers contained in expression X.
  758.  
  759.    Make sure that newly inserted references to those registers
  760.    as subexpressions will be considered valid.
  761.  
  762.    mention_regs is not called when a register itself
  763.    is being stored in the table.  */
  764.  
  765. static void
  766. mention_regs (x)
  767.      rtx x;
  768. {
  769.   register enum rtx_code code;
  770.   register int i, j;
  771.   register char *fmt;
  772.  
  773.   if (x == 0)
  774.     return;
  775.  
  776.   code = GET_CODE (x);
  777.   if (code == REG)
  778.     {
  779.       register int regno = REGNO (x);
  780.       reg_rtx[regno] = x;
  781.  
  782.       if (reg_in_table[regno] >= 0 && reg_in_table[regno] != reg_tick[regno])
  783.     remove_invalid_refs (regno);
  784.  
  785.       reg_in_table[regno] = reg_tick[regno];
  786.  
  787.       return;
  788.     }
  789.  
  790.   fmt = GET_RTX_FORMAT (code);
  791.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  792.     if (fmt[i] == 'e')
  793.       mention_regs (XEXP (x, i));
  794.     else if (fmt[i] == 'E')
  795.       for (j = 0; j < XVECLEN (x, i); j++)
  796.     mention_regs (XVECEXP (x, i, j));
  797. }
  798.  
  799. /* Update the register quantities for inserting X into the hash table
  800.    with a value equivalent to CLASSP.
  801.    (If the class does not contain a REG or a SUBREG, it is irrelevant.)
  802.    If MODIFIED is nonzero, X is a destination; it is being modified.
  803.    Note that reg_invalidate should be called on a register
  804.    before insert_regs is done on that register with MODIFIED != 0.
  805.  
  806.    Nonzero value means that elements of reg_qty have changed
  807.    so X's hash code may be different.  */
  808.  
  809. static int
  810. insert_regs (x, classp, modified)
  811.      rtx x;
  812.      struct table_elt *classp;
  813.      int modified;
  814. {
  815.   if (GET_CODE (x) == REG)
  816.     {
  817.       register int regno = REGNO (x);
  818.       reg_rtx[regno] = x;
  819.       if (modified || ! REGNO_QTY_VALID_P (regno))
  820.     {
  821.       if (classp)
  822.         for (classp = classp->first_same_value;
  823.          classp != 0;
  824.          classp = classp->next_same_value)
  825.           if (GET_CODE (classp->exp) == REG)
  826.         {
  827.           make_regs_eqv (regno, REGNO (classp->exp));
  828.           /* Make sure reg_rtx is set up even for regs
  829.              not explicitly set (such as function value).  */
  830.           reg_rtx[REGNO (classp->exp)] = classp->exp;
  831.           return 1;
  832.         }
  833.  
  834.       make_new_qty (regno);
  835.       return 1;
  836.     }
  837.     }
  838.   /* Copying a subreg into a subreg makes the regs equivalent,
  839.      but only if the entire regs' mode is within one word.
  840.      Copying one reg of a DImode into one reg of another DImode
  841.      does not make them equivalent.  */
  842.   else if (GET_CODE (x) == SUBREG
  843.        && GET_CODE (SUBREG_REG (x)) == REG
  844.        && GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))) <= UNITS_PER_WORD
  845.        && (modified
  846.            || ! REGNO_QTY_VALID_P (REGNO (SUBREG_REG (x)))))
  847.     {
  848.       if (classp)
  849.     for (classp = classp->first_same_value;
  850.          classp != 0;
  851.          classp = classp->next_same_value)
  852.       if (GET_CODE (classp->exp) == SUBREG
  853.           && GET_CODE (SUBREG_REG (classp->exp)) == REG
  854.           && GET_MODE (SUBREG_REG (classp->exp))
  855.          == GET_MODE (SUBREG_REG (x)))
  856.         {
  857.           int oregno = REGNO (SUBREG_REG (classp->exp));
  858.           make_regs_eqv (REGNO (SUBREG_REG (x)), oregno);
  859.           /* Make sure reg_rtx is set up even for regs
  860.          not explicitly set (such as function value).  */
  861.           reg_rtx[oregno] = SUBREG_REG (classp->exp);
  862.           return 1;
  863.         }
  864.       make_new_qty (REGNO (SUBREG_REG (x)));
  865.       return 1;
  866.     }
  867.   else
  868.     mention_regs (x);
  869.   return 0;
  870. }
  871.  
  872. /* Look in or update the hash table.  */
  873.  
  874. /* Put the element ELT on the list of free elements.  */
  875.  
  876. static void
  877. free_element (elt)
  878.      struct table_elt *elt;
  879. {
  880.   elt->next_same_hash = free_element_chain;
  881.   free_element_chain = elt;
  882. }
  883.  
  884. /* Return an element that is free for use.  */
  885.  
  886. static struct table_elt *
  887. get_element ()
  888. {
  889.   struct table_elt *elt = free_element_chain;
  890.   if (elt)
  891.     {
  892.       free_element_chain = elt->next_same_hash;
  893.       return elt;
  894.     }
  895.   n_elements_made++;
  896.   return (struct table_elt *) oballoc (sizeof (struct table_elt));
  897. }
  898.  
  899. /* Remove table element ELT from use in the table.
  900.    HASH is its hash code, made using the HASH macro.
  901.    It's an argument because often that is known in advance
  902.    and we save much time not recomputing it.  */
  903.  
  904. static void
  905. remove_from_table (elt, hash)
  906.      register struct table_elt *elt;
  907.      int hash;
  908. {
  909.   if (elt == 0)
  910.     return;
  911.  
  912.   /* Mark this element as removed.  See cse_insn.  */
  913.   elt->first_same_value = 0;
  914.  
  915.   /* Remove the table element from its equivalence class.  */
  916.      
  917.   {
  918.     register struct table_elt *prev = elt->prev_same_value;
  919.     register struct table_elt *next = elt->next_same_value;
  920.  
  921.     if (next) next->prev_same_value = prev;
  922.  
  923.     if (prev)
  924.       prev->next_same_value = next;
  925.     else
  926.       {
  927.     register struct table_elt *newfirst = next;
  928.     while (next)
  929.       {
  930.         next->first_same_value = newfirst;
  931.         next = next->next_same_value;
  932.       }
  933.       }
  934.   }
  935.  
  936.   /* Remove the table element from its hash bucket.  */
  937.  
  938.   {
  939.     register struct table_elt *prev = elt->prev_same_hash;
  940.     register struct table_elt *next = elt->next_same_hash;
  941.  
  942.     if (next) next->prev_same_hash = prev;
  943.  
  944.     if (prev)
  945.       prev->next_same_hash = next;
  946.     else if (table[hash] == elt)
  947.       table[hash] = next;
  948.     else
  949.       {
  950.     /* This entry is not in the proper hash bucket.  This can happen
  951.        when two classes were merged by `merge_equiv_classes'.  Search
  952.        for the hash bucket that it heads.  This happens only very
  953.        rarely, so the cost is acceptable.  */
  954.     for (hash = 0; hash < NBUCKETS; hash++)
  955.       if (table[hash] == elt)
  956.         table[hash] = next;
  957.       }
  958.   }
  959.  
  960.   /* Remove the table element from its related-value circular chain.  */
  961.  
  962.   if (elt->related_value != 0 && elt->related_value != elt)
  963.     {
  964.       register struct table_elt *p = elt->related_value;
  965.       while (p->related_value != elt)
  966.     p = p->related_value;
  967.       p->related_value = elt->related_value;
  968.       if (p->related_value == p)
  969.     p->related_value = 0;
  970.     }
  971.  
  972.   free_element (elt);
  973. }
  974.  
  975. /* Look up X in the hash table and return its table element,
  976.    or 0 if X is not in the table.
  977.  
  978.    MODE is the machine-mode of X, or if X is an integer constant
  979.    with VOIDmode then MODE is the mode with which X will be used.
  980.  
  981.    Here we are satisfied to find an expression whose tree structure
  982.    looks like X.  */
  983.  
  984. static struct table_elt *
  985. lookup (x, hash, mode)
  986.      rtx x;
  987.      int hash;
  988.      enum machine_mode mode;
  989. {
  990.   register struct table_elt *p;
  991.  
  992.   for (p = table[hash]; p; p = p->next_same_hash)
  993.     if (mode == p->mode && ((x == p->exp && GET_CODE (x) == REG)
  994.                 || exp_equiv_p (x, p->exp, GET_CODE (x) != REG)))
  995.       return p;
  996.  
  997.   return 0;
  998. }
  999.  
  1000. /* Like `lookup' but don't care whether the table element uses invalid regs.
  1001.    Also ignore discrepancies in the machine mode of a register.  */
  1002.  
  1003. static struct table_elt *
  1004. lookup_for_remove (x, hash, mode)
  1005.      rtx x;
  1006.      int hash;
  1007.      enum machine_mode mode;
  1008. {
  1009.   register struct table_elt *p;
  1010.  
  1011.   if (GET_CODE (x) == REG)
  1012.     {
  1013.       int regno = REGNO (x);
  1014.       /* Don't check the machine mode when comparing registers;
  1015.      invalidating (REG:SI 0) also invalidates (REG:DF 0).  */
  1016.       for (p = table[hash]; p; p = p->next_same_hash)
  1017.     if (GET_CODE (p->exp) == REG
  1018.         && REGNO (p->exp) == regno)
  1019.       return p;
  1020.     }
  1021.   else
  1022.     {
  1023.       for (p = table[hash]; p; p = p->next_same_hash)
  1024.     if (mode == p->mode && (x == p->exp || exp_equiv_p (x, p->exp, 0)))
  1025.       return p;
  1026.     }
  1027.  
  1028.   return 0;
  1029. }
  1030.  
  1031. /* Look for an expression equivalent to X and with code CODE.
  1032.    If one is found, return that expression.  */
  1033.  
  1034. static rtx
  1035. lookup_as_function (x, code)
  1036.      rtx x;
  1037.      enum rtx_code code;
  1038. {
  1039.   register struct table_elt *p = lookup (x, safe_hash (x, VOIDmode) % NBUCKETS,
  1040.                      GET_MODE (x));
  1041.   if (p == 0)
  1042.     return 0;
  1043.  
  1044.   for (p = p->first_same_value; p; p = p->next_same_value)
  1045.     {
  1046.       if (GET_CODE (p->exp) == code
  1047.       /* Make sure this is a valid entry in the table.  */
  1048.       && exp_equiv_p (p->exp, p->exp, 1))
  1049.     return p->exp;
  1050.     }
  1051.   
  1052.   return 0;
  1053. }
  1054.  
  1055. /* Insert X in the hash table, assuming HASH is its hash code
  1056.    and CLASSP is an element of the class it should go in
  1057.    (or 0 if a new class should be made).
  1058.    It is inserted at the proper position to keep the class in
  1059.    the order cheapest first.
  1060.  
  1061.    MODE is the machine-mode of X, or if X is an integer constant
  1062.    with VOIDmode then MODE is the mode with which X will be used.
  1063.  
  1064.    For elements of equal cheapness, the most recent one
  1065.    goes in front, except that the first element in the list
  1066.    remains first unless a cheaper element is added.  The order of
  1067.    pseudo-registers does not matter, as canon_reg will be called to
  1068.    find the cheapest when a register is retreived from the table.
  1069.  
  1070.    The in_memory field in the hash table element is set to 0.
  1071.    The caller must set it nonzero if appropriate.
  1072.  
  1073.    You should call insert_regs (X, CLASSP, MODIFY) before calling here,
  1074.    and if insert_regs returns a nonzero value
  1075.    you must then recompute its hash code before calling here.
  1076.  
  1077.    If necessary, update table showing constant values of quantities.  */
  1078.  
  1079. #define CHEAPER(X,Y)   ((X)->cost < (Y)->cost)
  1080.  
  1081. static struct table_elt *
  1082. insert (x, classp, hash, mode)
  1083.      register rtx x;
  1084.      register struct table_elt *classp;
  1085.      int hash;
  1086.      enum machine_mode mode;
  1087. {
  1088.   register struct table_elt *elt;
  1089.  
  1090.   /* If X is a register and we haven't made a quantity for it,
  1091.      something is wrong.  */
  1092.   if (GET_CODE (x) == REG && ! REGNO_QTY_VALID_P (REGNO (x)))
  1093.     abort ();
  1094.  
  1095.   /* Put an element for X into the right hash bucket.  */
  1096.  
  1097.   elt = get_element ();
  1098.   elt->exp = x;
  1099.   elt->cost = COST (x);
  1100.   elt->next_same_value = 0;
  1101.   elt->prev_same_value = 0;
  1102.   elt->next_same_hash = table[hash];
  1103.   elt->prev_same_hash = 0;
  1104.   elt->related_value = 0;
  1105.   elt->in_memory = 0;
  1106.   elt->mode = mode;
  1107.   elt->is_const = (CONSTANT_P (x)
  1108.            /* GNU C++ takes advantage of this for `this'
  1109.               (and other const values).  */
  1110.            || (RTX_UNCHANGING_P (x)
  1111.                && GET_CODE (x) == REG
  1112.                && REGNO (x) >= FIRST_PSEUDO_REGISTER)
  1113.            || FIXED_BASE_PLUS_P (x));
  1114.  
  1115.   if (table[hash])
  1116.     table[hash]->prev_same_hash = elt;
  1117.   table[hash] = elt;
  1118.  
  1119.   /* Put it into the proper value-class.  */
  1120.   if (classp)
  1121.     {
  1122.       classp = classp->first_same_value;
  1123.       if (CHEAPER (elt, classp))
  1124.     /* Insert at the head of the class */
  1125.     {
  1126.       register struct table_elt *p;
  1127.       elt->next_same_value = classp;
  1128.       classp->prev_same_value = elt;
  1129.       elt->first_same_value = elt;
  1130.  
  1131.       for (p = classp; p; p = p->next_same_value)
  1132.         p->first_same_value = elt;
  1133.     }
  1134.       else
  1135.     {
  1136.       /* Insert not at head of the class.  */
  1137.       /* Put it after the last element cheaper than X.  */
  1138.       register struct table_elt *p, *next;
  1139.       for (p = classp; (next = p->next_same_value) && CHEAPER (next, elt);
  1140.            p = next);
  1141.       /* Put it after P and before NEXT.  */
  1142.       elt->next_same_value = next;
  1143.       if (next)
  1144.         next->prev_same_value = elt;
  1145.       elt->prev_same_value = p;
  1146.       p->next_same_value = elt;
  1147.       elt->first_same_value = classp;
  1148.     }
  1149.     }
  1150.   else
  1151.     elt->first_same_value = elt;
  1152.  
  1153.   /* If this is a constant being set equivalent to a register or a register
  1154.      being set equivalent to a constant, note the constant equivalence.
  1155.  
  1156.      If this is a constant, it cannot be equivalent to a different constant,
  1157.      and a constant is the only thing that can be cheaper than a register.  So
  1158.      we know the register is the head of the class (before the constant was
  1159.      inserted).
  1160.  
  1161.      If this is a register that is not already known equivalent to a
  1162.      constant, we must check the entire class.
  1163.  
  1164.      If this is a register that is already known equivalent to an insn,
  1165.      update `qty_const_insn' to show that `this_insn' is the latest
  1166.      insn making that quantity equivalent to the constant.  */
  1167.  
  1168.   if (elt->is_const && classp && GET_CODE (classp->exp) == REG)
  1169.     {
  1170.       qty_const[reg_qty[REGNO (classp->exp)]] = x;
  1171.       qty_const_insn[reg_qty[REGNO (classp->exp)]] = this_insn;
  1172.     }
  1173.  
  1174.   else if (GET_CODE (x) == REG && classp && ! qty_const[reg_qty[REGNO (x)]])
  1175.     {
  1176.       register struct table_elt *p;
  1177.  
  1178.       for (p = classp; p != 0; p = p->next_same_value)
  1179.     {
  1180.       if (p->is_const)
  1181.         {
  1182.           qty_const[reg_qty[REGNO (x)]] = p->exp;
  1183.           qty_const_insn[reg_qty[REGNO (x)]] = this_insn;
  1184.           break;
  1185.         }
  1186.     }
  1187.     }
  1188.  
  1189.   else if (GET_CODE (x) == REG && qty_const[reg_qty[REGNO (x)]])
  1190.     qty_const_insn[reg_qty[REGNO (x)]] = this_insn;
  1191.  
  1192.   /* If this is a constant with symbolic value,
  1193.      and it has a term with an explicit integer value,
  1194.      link it up with related expressions.  */
  1195.   if (GET_CODE (x) == CONST)
  1196.     {
  1197.       rtx subexp = get_related_value (x);
  1198.       int subhash;
  1199.       struct table_elt *subelt, *subelt_prev;
  1200.  
  1201.       if (subexp != 0)
  1202.     {
  1203.       /* Get the integer-free subexpression in the hash table.  */
  1204.       subhash = safe_hash (subexp, mode) % NBUCKETS;
  1205.       subelt = lookup (subexp, subhash, mode);
  1206.       if (subelt == 0)
  1207.         subelt = insert (subexp, 0, subhash, mode);
  1208.       /* Initialize SUBELT's circular chain if it has none.  */
  1209.       if (subelt->related_value == 0)
  1210.         subelt->related_value = subelt;
  1211.       /* Find the element in the circular chain that precedes SUBELT.  */
  1212.       subelt_prev = subelt;
  1213.       while (subelt_prev->related_value != subelt)
  1214.         subelt_prev = subelt_prev->related_value;
  1215.       /* Put new ELT into SUBELT's circular chain just before SUBELT.
  1216.          This way the element that follows SUBELT is the oldest one.  */
  1217.       elt->related_value = subelt_prev->related_value;
  1218.       subelt_prev->related_value = elt;
  1219.     }
  1220.     }
  1221.  
  1222.   return elt;
  1223. }
  1224.  
  1225. /* Given two equivalence classes, CLASS1 and CLASS2, put all the entries from
  1226.    CLASS2 into CLASS1.  This is done when we have reached an insn which makes
  1227.    the two classes equivalent.
  1228.  
  1229.    CLASS1 will be the surviving class; CLASS2 should not be used after this
  1230.    call.
  1231.  
  1232.    Any invalid entries in CLASS2 will not be copied.  */
  1233.  
  1234. static void
  1235. merge_equiv_classes (class1, class2)
  1236.      struct table_elt *class1, *class2;
  1237. {
  1238.   struct table_elt *elt, *next, *new;
  1239.  
  1240.   /* Ensure we start with the head of the classes.  */
  1241.   class1 = class1->first_same_value;
  1242.   class2 = class2->first_same_value;
  1243.  
  1244.   /* If they were already equal, forget it.  */
  1245.   if (class1 == class2)
  1246.     return;
  1247.  
  1248.   for (elt = class2; elt; elt = next)
  1249.     {
  1250.       int hash;
  1251.       rtx exp = elt->exp;
  1252.       enum machine_mode mode = elt->mode;
  1253.  
  1254.       next = elt->next_same_value;
  1255.  
  1256.       /* Remove old entry, make a new one in CLASS1's class.
  1257.      Don't do this for invalid entries as we cannot find their
  1258.      hash code (it also isn't necessary). */
  1259.       if (GET_CODE (exp) == REG || exp_equiv_p (exp, exp, 1))
  1260.     {
  1261.       hash_arg_in_memory = 0;
  1262.       hash_arg_in_struct = 0;
  1263.       hash = HASH (exp, mode);
  1264.           
  1265.       if (GET_CODE (exp) == REG)
  1266.         reg_invalidate (REGNO (exp), 1);
  1267.       else if (GET_CODE (exp) == SUBREG)
  1268.         reg_invalidate (REGNO (SUBREG_REG (exp)), 1);
  1269.           
  1270.       remove_from_table (elt, hash);
  1271.  
  1272.       if (insert_regs (exp, class1, 0))
  1273.         hash = HASH (exp, mode);
  1274.       new = insert (exp, class1, hash, mode);
  1275.       new->in_memory = hash_arg_in_memory;
  1276.       new->in_struct = hash_arg_in_struct;
  1277.     }
  1278.     }
  1279. }
  1280.  
  1281. /* Remove from the hash table, or mark as invalid,
  1282.    all expressions whose values could be altered by storing in X.
  1283.    X is a register, a subreg, or a memory reference with nonvarying address
  1284.    (because, when a memory reference with a varying address is stored in,
  1285.    all memory references are removed by invalidate_memory
  1286.    so specific invalidation is superfluous).
  1287.  
  1288.    A nonvarying address may be just a register or just
  1289.    a symbol reference, or it may be either of those plus
  1290.    a numeric offset.  */
  1291.  
  1292. static void
  1293. invalidate (x)
  1294.      rtx x;
  1295. {
  1296.   register int i;
  1297.   register struct table_elt *p;
  1298.   register rtx base;
  1299.   register int start, end;
  1300.  
  1301.   /* If X is a register, dependencies on its contents
  1302.      are recorded through the qty number mechanism.
  1303.      Just change the qty number of the register,
  1304.      mark it as invalid for expressions that refer to it,
  1305.      and remove it itself.  */
  1306.  
  1307.   if (GET_CODE (x) == REG)
  1308.     {
  1309.       register int hash = HASHREG (x);
  1310.       reg_invalidate (REGNO (x), 0);
  1311.       remove_from_table (lookup_for_remove (x, hash, GET_MODE (x)), hash);
  1312.       return;
  1313.     }
  1314.  
  1315.   if (GET_CODE (x) == SUBREG)
  1316.     {
  1317.       if (GET_CODE (SUBREG_REG (x)) != REG)
  1318.     abort ();
  1319.       invalidate (SUBREG_REG (x));
  1320.       return;
  1321.     }
  1322.  
  1323.   /* X is not a register; it must be a memory reference with
  1324.      a nonvarying address.  Remove all hash table elements
  1325.      that refer to overlapping pieces of memory.  */
  1326.  
  1327.   if (GET_CODE (x) != MEM)
  1328.     abort ();
  1329.   base = XEXP (x, 0);
  1330.   start = 0;
  1331.  
  1332.   /* Registers with nonvarying addresses usually have constant equivalents;
  1333.      but the frame pointer register is also possible.  */
  1334.   if (GET_CODE (base) == REG
  1335.       && REGNO_QTY_VALID_P (REGNO (base))
  1336.       && qty_const[reg_qty[REGNO (base)]] != 0)
  1337.     base = qty_const[reg_qty[REGNO (base)]];
  1338.   else if (GET_CODE (base) == PLUS
  1339.        && GET_CODE (XEXP (base, 1)) == CONST_INT
  1340.        && GET_CODE (XEXP (base, 0)) == REG
  1341.        && REGNO_QTY_VALID_P (REGNO (XEXP (base, 0)))
  1342.        && qty_const[reg_qty[REGNO (XEXP (base, 0))]])
  1343.     {
  1344.       start = INTVAL (XEXP (base, 1));
  1345.       base = qty_const[reg_qty[REGNO (XEXP (base, 0))]];
  1346.     }
  1347.  
  1348.   if (GET_CODE (base) == CONST)
  1349.     base = XEXP (base, 0);
  1350.   if (GET_CODE (base) == PLUS
  1351.       && GET_CODE (XEXP (base, 1)) == CONST_INT)
  1352.     {
  1353.       start += INTVAL (XEXP (base, 1));
  1354.       base = XEXP (base, 0);
  1355.     }
  1356.  
  1357.   end = start + GET_MODE_SIZE (GET_MODE (x));
  1358.   for (i = 0; i < NBUCKETS; i++)
  1359.     {
  1360.       register struct table_elt *next;
  1361.       for (p = table[i]; p; p = next)
  1362.     {
  1363.       next = p->next_same_hash;
  1364.       if (refers_to_mem_p (p->exp, base, start, end))
  1365.         remove_from_table (p, i);
  1366.     }
  1367.     }
  1368. }
  1369.  
  1370. /* Remove all expressions that refer to register REGNO,
  1371.    since they are already invalid, and we are about to
  1372.    mark that register valid again and don't want the old
  1373.    expressions to reappear as valid.  */
  1374.  
  1375. static void
  1376. remove_invalid_refs (regno)
  1377.      int regno;
  1378. {
  1379.   register int i;
  1380.   register struct table_elt *p, *next;
  1381.   register rtx x = reg_rtx[regno];
  1382.  
  1383.   for (i = 0; i < NBUCKETS; i++)
  1384.     for (p = table[i]; p; p = next)
  1385.       {
  1386.     next = p->next_same_hash;
  1387.     if (GET_CODE (p->exp) != REG && reg_mentioned_p (x, p->exp))
  1388.       remove_from_table (p, i);
  1389.       }
  1390. }
  1391.  
  1392. /* Remove from the hash table all expressions that reference memory,
  1393.    or some of them as specified by *WRITES.  */
  1394.  
  1395. static void
  1396. invalidate_memory (writes)
  1397.      struct write_data *writes;
  1398. {
  1399.   register int i;
  1400.   register struct table_elt *p, *next;
  1401.   int all = writes->all;
  1402.   int nonscalar = writes->nonscalar;
  1403.  
  1404.   for (i = 0; i < NBUCKETS; i++)
  1405.     for (p = table[i]; p; p = next)
  1406.       {
  1407.     next = p->next_same_hash;
  1408.     if (p->in_memory
  1409.         && (all
  1410.         || (nonscalar && p->in_struct)
  1411.         || cse_rtx_addr_varies_p (p->exp)))
  1412.       remove_from_table (p, i);
  1413.       }
  1414. }
  1415.  
  1416. /* Given an expression X of type CONST,
  1417.    and ELT which is its table entry (or 0 if it
  1418.    is not in the hash table),
  1419.    return an alternate expression for X as a register plus integer.
  1420.    If none can be found, return 0.  */
  1421.  
  1422. static rtx
  1423. use_related_value (x, elt)
  1424.      rtx x;
  1425.      struct table_elt *elt;
  1426. {
  1427.   register struct table_elt *relt = 0;
  1428.   register struct table_elt *p, *q;
  1429.   int offset;
  1430.  
  1431.   /* First, is there anything related known?
  1432.      If we have a table element, we can tell from that.
  1433.      Otherwise, must look it up.  */
  1434.  
  1435.   if (elt != 0 && elt->related_value != 0)
  1436.     relt = elt;
  1437.   else if (elt == 0 && GET_CODE (x) == CONST)
  1438.     {
  1439.       rtx subexp = get_related_value (x);
  1440.       if (subexp != 0)
  1441.     relt = lookup (subexp,
  1442.                safe_hash (subexp, GET_MODE (subexp)) % NBUCKETS,
  1443.                GET_MODE (subexp));
  1444.     }
  1445.  
  1446.   if (relt == 0)
  1447.     return 0;
  1448.  
  1449.   /* Search all related table entries for one that has an
  1450.      equivalent register.  */
  1451.  
  1452.   p = relt;
  1453.   while (1)
  1454.     {
  1455.       /* This loop is strange in that it is executed in two different cases.
  1456.      The first is when X is already in the table.  Then it is searching
  1457.      the RELATED_VALUE list of X's class (RELT).  The second case is when
  1458.      X is not in the table.  Then RELT points to a class for the related
  1459.      value.
  1460.  
  1461.      Ensure that, whatever case we are in, that we ignore classes that have
  1462.      the same value as X.  */
  1463.  
  1464.       if (rtx_equal_p (x, p->exp))
  1465.     q = 0;
  1466.       else
  1467.     for (q = p->first_same_value; q; q = q->next_same_value)
  1468.       if (GET_CODE (q->exp) == REG)
  1469.         break;
  1470.  
  1471.       if (q)
  1472.     break;
  1473.  
  1474.       p = p->related_value;
  1475.  
  1476.       /* We went all the way around, so there is nothing to be found.
  1477.      Alternatively, perhaps RELT was in the table for some other reason
  1478.      and it has no related values recorded.  */
  1479.       if (p == relt || p == 0)
  1480.     break;
  1481.     }
  1482.  
  1483.   if (q == 0)
  1484.     return 0;
  1485.  
  1486.   offset = (get_integer_term (x) - get_integer_term (p->exp));
  1487.   /* Note: OFFSET may be 0 if P->xexp and X are related by commutativity.  */
  1488.   return plus_constant (q->exp, offset);
  1489. }
  1490.  
  1491. /* Hash an rtx.  We are careful to make sure the value is never negative.
  1492.    Equivalent registers hash identically.
  1493.    MODE is used in hashing for CONST_INTs only;
  1494.    otherwise the mode of X is used.
  1495.  
  1496.    Store 1 in do_not_record if any subexpression is volatile.
  1497.  
  1498.    Store 1 in hash_arg_in_memory if X contains a MEM rtx
  1499.    which does not have the RTX_UNCHANGING_P bit set.
  1500.    In this case, also store 1 in hash_arg_in_struct
  1501.    if there is a MEM rtx which has the MEM_IN_STRUCT_P bit set.
  1502.  
  1503.    Note that cse_insn knows that the hash code of a MEM expression
  1504.    is just (int) MEM plus the hash code of the address.
  1505.    It also knows it can use HASHREG to get the hash code of (REG n).  */
  1506.  
  1507. static int
  1508. canon_hash (x, mode)
  1509.      rtx x;
  1510.      enum machine_mode mode;
  1511. {
  1512.   register int i, j;
  1513.   register int hash = 0;
  1514.   register enum rtx_code code;
  1515.   register char *fmt;
  1516.  
  1517.   /* repeat is used to turn tail-recursion into iteration.  */
  1518.  repeat:
  1519.   if (x == 0)
  1520.     return hash;
  1521.  
  1522.   code = GET_CODE (x);
  1523.   switch (code)
  1524.     {
  1525.     case REG:
  1526.       {
  1527.     register int regno = REGNO (x);
  1528.  
  1529.     /* On some machines, we can't record any non-fixed hard register,
  1530.        because extending its life will cause reload problems.  We
  1531.        consider ap, fp, and sp to be fixed for this purpose.
  1532.        On all machines, we can't record any global registers. */
  1533.  
  1534.     if (regno < FIRST_PSEUDO_REGISTER
  1535. #ifdef SMALL_REGISTER_CLASSES
  1536.         && ! fixed_regs[regno]
  1537.         && regno != FRAME_POINTER_REGNUM
  1538.         && regno != ARG_POINTER_REGNUM
  1539.         && regno != STACK_POINTER_REGNUM
  1540. #else
  1541.         && global_regs[regno]
  1542. #endif
  1543.         )
  1544.       {
  1545.         do_not_record = 1;
  1546.         return 0;
  1547.       }
  1548.     return hash + ((int) REG << 7) + reg_qty[regno];
  1549.       }
  1550.  
  1551.     case CONST_INT:
  1552.       hash += ((int) mode + ((int) CONST_INT << 7)
  1553.            + INTVAL (x) + (INTVAL (x) >> HASHBITS));
  1554.       return ((1 << HASHBITS) - 1) & hash;
  1555.  
  1556.     case CONST_DOUBLE:
  1557.       /* This is like the general case, except that it only counts
  1558.      the integers representing the constant.  */
  1559.       hash += (int) code + (int) GET_MODE (x);
  1560.       {
  1561.     int i;
  1562.     for (i = 2; i < GET_RTX_LENGTH (CONST_DOUBLE); i++)
  1563.       {
  1564.         int tem = XINT (x, i);
  1565.         hash += ((1 << HASHBITS) - 1) & (tem + (tem >> HASHBITS));
  1566.       }
  1567.       }
  1568.       return hash;
  1569.  
  1570.       /* Assume there is only one rtx object for any given label.  */
  1571.     case LABEL_REF:
  1572.       /* Use `and' to ensure a positive number.  */
  1573.       return (hash + ((int) LABEL_REF << 7)
  1574.           + ((int) XEXP (x, 0) & ((1 << HASHBITS) - 1)));
  1575.  
  1576.     case SYMBOL_REF:
  1577.       return (hash + ((int) SYMBOL_REF << 7)
  1578.           + ((int) XEXP (x, 0) & ((1 << HASHBITS) - 1)));
  1579.  
  1580.     case MEM:
  1581.       if (MEM_VOLATILE_P (x))
  1582.     {
  1583.       do_not_record = 1;
  1584.       return 0;
  1585.     }
  1586.       if (! RTX_UNCHANGING_P (x))
  1587.     {
  1588.       hash_arg_in_memory = 1;
  1589.       if (MEM_IN_STRUCT_P (x)) hash_arg_in_struct = 1;
  1590.     }
  1591.       /* Now that we have already found this special case,
  1592.      might as well speed it up as much as possible.  */
  1593.       hash += (int) MEM;
  1594.       x = XEXP (x, 0);
  1595.       goto repeat;
  1596.  
  1597.     case PRE_DEC:
  1598.     case PRE_INC:
  1599.     case POST_DEC:
  1600.     case POST_INC:
  1601.     case PC:
  1602.     case CC0:
  1603.     case CALL:
  1604.       do_not_record = 1;
  1605.       return 0;
  1606.  
  1607.     case ASM_OPERANDS:
  1608.       if (MEM_VOLATILE_P (x))
  1609.     {
  1610.       do_not_record = 1;
  1611.       return 0;
  1612.     }
  1613.     }
  1614.  
  1615.   i = GET_RTX_LENGTH (code) - 1;
  1616.   hash += (int) code + (int) GET_MODE (x);
  1617.   fmt = GET_RTX_FORMAT (code);
  1618.   for (; i >= 0; i--)
  1619.     {
  1620.       if (fmt[i] == 'e')
  1621.     {
  1622.       /* If we are about to do the last recursive call
  1623.          needed at this level, change it into iteration.
  1624.          This function  is called enough to be worth it.  */
  1625.       if (i == 0)
  1626.         {
  1627.           x = XEXP (x, 0);
  1628.           goto repeat;
  1629.         }
  1630.       hash += canon_hash (XEXP (x, i), 0);
  1631.     }
  1632.       else if (fmt[i] == 'E')
  1633.     for (j = 0; j < XVECLEN (x, i); j++)
  1634.       hash += canon_hash (XVECEXP (x, i, j), 0);
  1635.       else if (fmt[i] == 's')
  1636.     {
  1637.       register char *p = XSTR (x, i);
  1638.       if (p)
  1639.         while (*p)
  1640.           {
  1641.         register int tem = *p++;
  1642.         hash += ((1 << HASHBITS) - 1) & (tem + (tem >> HASHBITS));
  1643.           }
  1644.     }
  1645.       else if (fmt[i] == 'i')
  1646.     {
  1647.       register int tem = XINT (x, i);
  1648.       hash += ((1 << HASHBITS) - 1) & (tem + (tem >> HASHBITS));
  1649.     }
  1650.       else
  1651.     abort ();
  1652.     }
  1653.   return hash;
  1654. }
  1655.  
  1656. /* Like canon_hash but with no side effects.  */
  1657.  
  1658. static int
  1659. safe_hash (x, mode)
  1660.      rtx x;
  1661.      enum machine_mode mode;
  1662. {
  1663.   int save_do_not_record = do_not_record;
  1664.   int save_hash_arg_in_memory = hash_arg_in_memory;
  1665.   int save_hash_arg_in_struct = hash_arg_in_struct;
  1666.   int hash = canon_hash (x, mode);
  1667.   hash_arg_in_memory = save_hash_arg_in_memory;
  1668.   hash_arg_in_struct = save_hash_arg_in_struct;
  1669.   do_not_record = save_do_not_record;
  1670.   return hash;
  1671. }
  1672.  
  1673. /* Return 1 iff X and Y would canonicalize into the same thing,
  1674.    without actually constructing the canonicalization of either one.
  1675.    If VALIDATE is nonzero,
  1676.    we assume X is an expression being processed from the rtl
  1677.    and Y was found in the hash table.  We check register refs
  1678.    in Y for being marked as valid.  */
  1679.  
  1680. static int
  1681. exp_equiv_p (x, y, validate)
  1682.      rtx x, y;
  1683.      int validate;
  1684. {
  1685.   register int i;
  1686.   register enum rtx_code code;
  1687.   register char *fmt;
  1688.  
  1689.   /* Note: it is incorrect to assume an expression is equivalent to itself
  1690.      if VALIDATE is nonzero.  */
  1691.   if (x == y && !validate)
  1692.     return 1;
  1693.   if (x == 0 || y == 0)
  1694.     return x == y;
  1695.   code = GET_CODE (x);
  1696.   if (code != GET_CODE (y))
  1697.     return 0;
  1698.  
  1699.   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.  */
  1700.   if (GET_MODE (x) != GET_MODE (y))
  1701.     return 0;
  1702.  
  1703.   switch (code)
  1704.     {
  1705.     case PC:
  1706.     case CC0:
  1707.       return x == y;
  1708.  
  1709.     case CONST_INT:
  1710.       return XINT (x, 0) == XINT (y, 0);
  1711.  
  1712.     case LABEL_REF:
  1713.     case SYMBOL_REF:
  1714.       return XEXP (x, 0) == XEXP (y, 0);
  1715.  
  1716.     case REG:
  1717.       return (reg_qty[REGNO (x)] == reg_qty[REGNO (y)]
  1718.           && (!validate
  1719.           || reg_in_table[REGNO (y)] == reg_tick[REGNO (y)]));
  1720.  
  1721.     /*  For commutative operations, check both orders.  */
  1722.     case PLUS:
  1723.     case MULT:
  1724.     case AND:
  1725.     case IOR:
  1726.     case XOR:
  1727.     case NE:
  1728.     case EQ:
  1729.       return ((exp_equiv_p (XEXP (x, 0), XEXP (y, 0), validate)
  1730.            && exp_equiv_p (XEXP (x, 1), XEXP (y, 1), validate))
  1731.           || (exp_equiv_p (XEXP (x, 0), XEXP (y, 1), validate)
  1732.           && exp_equiv_p (XEXP (x, 1), XEXP (y, 0), validate)));
  1733.     }
  1734.  
  1735.   /* Compare the elements.  If any pair of corresponding elements
  1736.      fail to match, return 0 for the whole things.  */
  1737.  
  1738.   fmt = GET_RTX_FORMAT (code);
  1739.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  1740.     {
  1741.       if (fmt[i] == 'e')
  1742.     {
  1743.       if (! exp_equiv_p (XEXP (x, i), XEXP (y, i), validate))
  1744.         return 0;
  1745.     }
  1746.       else if (fmt[i] == 'E')
  1747.     {
  1748.       int j;
  1749.       if (XVECLEN (x, i) != XVECLEN (y, i))
  1750.         return 0;
  1751.       for (j = 0; j < XVECLEN (x, i); j++)
  1752.         if (! exp_equiv_p (XVECEXP (x, i, j), XVECEXP (y, i, j), validate))
  1753.           return 0;
  1754.     }
  1755.       else if (fmt[i] == 's')
  1756.     {
  1757.       if (strcmp (XSTR (x, i), XSTR (y, i)))
  1758.         return 0;
  1759.     }
  1760.       else if (fmt[i] == 'i')
  1761.     {
  1762.       if (XINT (x, i) != XINT (y, i))
  1763.         return 0;
  1764.     }
  1765.       else if (fmt[i] != '0')
  1766.      abort ();
  1767.     }
  1768.   return 1;
  1769. }
  1770.  
  1771. /* Return 1 iff any subexpression of X matches Y.
  1772.    Here we do not require that X or Y be valid (for registers referred to)
  1773.    for being in the hash table.  */
  1774.  
  1775. int
  1776. refers_to_p (x, y)
  1777.      rtx x, y;
  1778. {
  1779.   register int i;
  1780.   register enum rtx_code code;
  1781.   register char *fmt;
  1782.  
  1783.  repeat:
  1784.   if (x == y)
  1785.     return 1;
  1786.   if (x == 0 || y == 0)
  1787.     return 0;
  1788.  
  1789.   code = GET_CODE (x);
  1790.   /* If X as a whole has the same code as Y, they may match.
  1791.      If so, return 1.  */
  1792.   if (code == GET_CODE (y))
  1793.     {
  1794.       if (exp_equiv_p (x, y, 0))
  1795.     return 1;
  1796.     }
  1797.  
  1798.   /* X does not match, so try its subexpressions.  */
  1799.  
  1800.   fmt = GET_RTX_FORMAT (code);
  1801.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  1802.     if (fmt[i] == 'e')
  1803.       {
  1804.     if (i == 0)
  1805.       {
  1806.         x = XEXP (x, 0);
  1807.         goto repeat;
  1808.       }
  1809.     else
  1810.       if (refers_to_p (XEXP (x, i), y))
  1811.         return 1;
  1812.       }
  1813.     else if (fmt[i] == 'E')
  1814.       {
  1815.     int j;
  1816.     for (j = 0; j < XVECLEN (x, i); j++)
  1817.       if (refers_to_p (XVECEXP (x, i, j), y))
  1818.         return 1;
  1819.       }
  1820.  
  1821.   return 0;
  1822. }
  1823.  
  1824. /* Return 1 iff any subexpression of X refers to memory
  1825.    at an address of BASE plus some offset
  1826.    such that any of the bytes' offsets fall between START (inclusive)
  1827.    and END (exclusive).
  1828.  
  1829.    The value is undefined if X is a varying address.
  1830.    This function is not used in such cases.
  1831.  
  1832.    When used in the cse pass, `qty_const' is nonzero, and it is used
  1833.    to treat an address that is a register with a known constant value
  1834.    as if it were that constant value.
  1835.    In the loop pass, `qty_const' is zero, so this is not done.  */
  1836.  
  1837. int
  1838. refers_to_mem_p (x, base, start, end)
  1839.      rtx x, base;
  1840.      int start, end;
  1841. {
  1842.   register int i;
  1843.   register enum rtx_code code;
  1844.   register char *fmt;
  1845.  
  1846.   if (GET_CODE (base) == CONST_INT)
  1847.     {
  1848.       start += INTVAL (base);
  1849.       end += INTVAL (base);
  1850.       base = const0_rtx;
  1851.     }
  1852.  
  1853.  repeat:
  1854.   if (x == 0)
  1855.     return 0;
  1856.  
  1857.   code = GET_CODE (x);
  1858.   if (code == MEM)
  1859.     {
  1860.       register rtx addr = XEXP (x, 0);    /* Get the address.  */
  1861.       int myend;
  1862.  
  1863.       i = 0;
  1864.       if (GET_CODE (addr) == REG
  1865.       /* qty_const is 0 when outside the cse pass;
  1866.          at such times, this info is not available.  */
  1867.       && qty_const != 0
  1868.       && REGNO_QTY_VALID_P (REGNO (addr))
  1869.       && qty_const[reg_qty[REGNO (addr)]] != 0)
  1870.     addr = qty_const[reg_qty[REGNO (addr)]];
  1871.       else if (GET_CODE (addr) == PLUS
  1872.            && GET_CODE (XEXP (addr, 1)) == CONST_INT
  1873.            && GET_CODE (XEXP (addr, 0)) == REG
  1874.            && qty_const != 0
  1875.            && REGNO_QTY_VALID_P (REGNO (XEXP (addr, 0)))
  1876.            && qty_const[reg_qty[REGNO (XEXP (addr, 0))]])
  1877.     {
  1878.       i = INTVAL (XEXP (addr, 1));
  1879.       addr = qty_const[reg_qty[REGNO (XEXP (addr, 0))]];
  1880.     }
  1881.  
  1882.     check_addr:
  1883.       if (GET_CODE (addr) == CONST)
  1884.     addr = XEXP (addr, 0);
  1885.  
  1886.       /* If ADDR is BASE, or BASE plus an integer, put
  1887.      the integer in I.  */
  1888.       if (GET_CODE (addr) == PLUS
  1889.       && XEXP (addr, 0) == base
  1890.       && GET_CODE (XEXP (addr, 1)) == CONST_INT)
  1891.     i += INTVAL (XEXP (addr, 1));
  1892.       else if (GET_CODE (addr) == LO_SUM)
  1893.     {
  1894.       if (GET_CODE (base) != LO_SUM)
  1895.         return 1;
  1896.       /* The REG component of the LO_SUM is known by the
  1897.          const value in the XEXP part.  */
  1898.       addr = XEXP (addr, 1);
  1899.       base = XEXP (base, 1);
  1900.       i = 0;
  1901.       if (GET_CODE (base) == CONST)
  1902.         base = XEXP (base, 0);
  1903.       if (GET_CODE (base) == PLUS
  1904.           && GET_CODE (XEXP (base, 1)) == CONST_INT)
  1905.         {
  1906.           int tem = INTVAL (XEXP (base, 1));
  1907.           start += tem;
  1908.           end += tem;
  1909.           base = XEXP (base, 0);
  1910.         }
  1911.       goto check_addr;
  1912.     }
  1913.       else if (GET_CODE (base) == LO_SUM)
  1914.     {
  1915.       base = XEXP (base, 1);
  1916.       if (GET_CODE (base) == CONST)
  1917.         base = XEXP (base, 0);
  1918.       if (GET_CODE (base) == PLUS
  1919.           && GET_CODE (XEXP (base, 1)) == CONST_INT)
  1920.         {
  1921.           int tem = INTVAL (XEXP (base, 1));
  1922.           start += tem;
  1923.           end += tem;
  1924.           base = XEXP (base, 0);
  1925.         }
  1926.       goto check_addr;      
  1927.     }
  1928.       else if (GET_CODE (addr) == CONST_INT && base == const0_rtx)
  1929.     i = INTVAL (addr);
  1930.       else if (addr != base)
  1931.     return 0;
  1932.  
  1933.       myend = i + GET_MODE_SIZE (GET_MODE (x));
  1934.       return myend > start && i < end;
  1935.     }
  1936.  
  1937.   /* X does not match, so try its subexpressions.  */
  1938.  
  1939.   fmt = GET_RTX_FORMAT (code);
  1940.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  1941.     if (fmt[i] == 'e')
  1942.       {
  1943.     if (i == 0)
  1944.       {
  1945.         x = XEXP (x, 0);
  1946.         goto repeat;
  1947.       }
  1948.     else
  1949.       if (refers_to_mem_p (XEXP (x, i), base, start, end))
  1950.         return 1;
  1951.       }
  1952.     else if (fmt[i] == 'E')
  1953.       {
  1954.     int j;
  1955.     for (j = 0; j < XVECLEN (x, i); j++)
  1956.       if (refers_to_mem_p (XVECEXP (x, i, j), base, start, end))
  1957.         return 1;
  1958.       }
  1959.  
  1960.   return 0;
  1961. }
  1962.  
  1963. /* Nonzero if X refers to memory at a varying address;
  1964.    except that a register which has at the moment a known constant value
  1965.    isn't considered variable.  */
  1966.  
  1967. static int
  1968. cse_rtx_addr_varies_p (x)
  1969.      rtx x;
  1970. {
  1971.   if (GET_CODE (x) == MEM
  1972.       && GET_CODE (XEXP (x, 0)) == REG
  1973.       && REGNO_QTY_VALID_P (REGNO (XEXP (x, 0)))
  1974.       && qty_const[reg_qty[REGNO (XEXP (x, 0))]] != 0)
  1975.     return 0;
  1976.  
  1977.   if (GET_CODE (x) == MEM
  1978.       && GET_CODE (XEXP (x, 0)) == PLUS
  1979.       && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
  1980.       && GET_CODE (XEXP (XEXP (x, 0), 0)) == REG
  1981.       && REGNO_QTY_VALID_P (REGNO (XEXP (XEXP (x, 0), 0)))
  1982.       && qty_const[reg_qty[REGNO (XEXP (XEXP (x, 0), 0))]])
  1983.     return 0;
  1984.  
  1985.   return rtx_addr_varies_p (x);
  1986. }
  1987.  
  1988. /* Canonicalize an expression:
  1989.    replace each register reference inside it
  1990.    with the "oldest" equivalent register.
  1991.  
  1992.    If INSN is non-zero and we are replacing a pseudo with a hard register
  1993.    or vice versa, verify that INSN remains valid after we make our
  1994.    substitution.  */
  1995.  
  1996. static rtx
  1997. canon_reg (x, insn)
  1998.      rtx x;
  1999.      rtx insn;
  2000. {
  2001.   register int i;
  2002.   register enum rtx_code code;
  2003.   register char *fmt;
  2004.  
  2005.   if (x == 0)
  2006.     return x;
  2007.  
  2008.   code = GET_CODE (x);
  2009.   switch (code)
  2010.     {
  2011.     case PC:
  2012.     case CC0:
  2013.     case CONST:
  2014.     case CONST_INT:
  2015.     case CONST_DOUBLE:
  2016.     case SYMBOL_REF:
  2017.     case LABEL_REF:
  2018.     case ADDR_VEC:
  2019.     case ADDR_DIFF_VEC:
  2020.       return x;
  2021.  
  2022.     case REG:
  2023.       {
  2024.     register rtx new;
  2025.     register int first;
  2026.  
  2027.     /* Never replace a hard reg, because hard regs can appear
  2028.        in more than one machine mode, and we must preserve the mode
  2029.        of each occurrence.  Also, some hard regs appear in
  2030.        MEMs that are shared and mustn't be altered.  Don't try to
  2031.        replace any reg that maps to a reg of class NO_REGS.  */
  2032.     if (REGNO (x) < FIRST_PSEUDO_REGISTER
  2033.         || ! REGNO_QTY_VALID_P (REGNO (x)))
  2034.       return x;
  2035.  
  2036.     first = qty_first_reg[reg_qty[REGNO (x)]];
  2037.     new = reg_rtx[first];
  2038.     return new && (first >= FIRST_PSEUDO_REGISTER
  2039.                || REGNO_REG_CLASS (first) != NO_REGS) ? new : x;
  2040.       }
  2041.     }
  2042.  
  2043.   fmt = GET_RTX_FORMAT (code);
  2044.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  2045.     {
  2046.       register int j;
  2047.  
  2048.       if (fmt[i] == 'e')
  2049.     {
  2050.       rtx new = canon_reg (XEXP (x, i), insn);
  2051.  
  2052.       /* If replacing pseudo with hard reg or vice versa, ensure the
  2053.          insn remains valid.  */
  2054.       if (new && GET_CODE (new) == REG && GET_CODE (XEXP (x, i)) == REG
  2055.           && ((REGNO (new) < FIRST_PSEUDO_REGISTER)
  2056.           != (REGNO (XEXP (x, i)) < FIRST_PSEUDO_REGISTER)))
  2057.         validate_change (insn, &XEXP (x, i), new, 0);
  2058.       else
  2059.         XEXP (x, i) = new;
  2060.     }
  2061.       else if (fmt[i] == 'E')
  2062.     for (j = 0; j < XVECLEN (x, i); j++)
  2063.       XVECEXP (x, i, j) = canon_reg (XVECEXP (x, i, j), insn);
  2064.     }
  2065.  
  2066.   return x;
  2067. }
  2068.  
  2069. /* LOC is a location with INSN that is an operand address (the contents of
  2070.    a MEM).  Find the best equivalent address to use that is valid for this
  2071.    insn.
  2072.  
  2073.    On most CISC machines, complicated address modes are costly, and rtx_cost
  2074.    is a good approximation for that cost.  However, most RISC machines have
  2075.    only a few (usually only one) memory reference formats.  If an address is
  2076.    valid at all, it is often just as cheap as any other address.  Hence, for
  2077.    RISC machines, we use the configuration macro `ADDRESS_COST' to compare the
  2078.    costs of various addresses.  For two addresses of equal cost, choose the one
  2079.    with the highest `rtx_cost' value as that has the potential of eliminating
  2080.    the most insns.  For equal costs, we choose the first in the equivalence
  2081.    class.  Note that we ignore the fact that pseudo registers are cheaper
  2082.    than hard registers here because we would also prefer the pseudo registers.
  2083.   */
  2084.  
  2085. void
  2086. find_best_addr (insn, loc)
  2087.      rtx insn;
  2088.      rtx *loc;
  2089. {
  2090.   struct table_elt *elt, *p;
  2091.   rtx addr = *loc;
  2092.   int our_cost;
  2093.   int found_better = 1;
  2094.   int save_do_not_record = do_not_record;
  2095.   int save_hash_arg_in_memory = hash_arg_in_memory;
  2096.   int save_hash_arg_in_struct = hash_arg_in_struct;
  2097.   int hash_code;
  2098.   int addr_volatile;
  2099.   int regno;
  2100.  
  2101.   /* Do not try to replace constant addresses or addresses of local and
  2102.      argument slots.  These MEM expressions are made only once and inserted
  2103.      in many instructions, as well as being used to control symbol table
  2104.      output.  It is not safe to clobber them.
  2105.  
  2106.      There are some uncommon cases where the address is already in a register
  2107.      for some reason, but we cannot take advantage of that because we have
  2108.      no easy way to unshare the MEM.  In addition, looking up all stack
  2109.      addresses is costly.  */
  2110.   if ((GET_CODE (addr) == PLUS
  2111.        && GET_CODE (XEXP (addr, 0)) == REG
  2112.        && GET_CODE (XEXP (addr, 1)) == CONST_INT
  2113.        && (regno = REGNO (XEXP (addr, 0)),
  2114.        regno == FRAME_POINTER_REGNUM || regno == ARG_POINTER_REGNUM))
  2115.       || (GET_CODE (addr) == REG
  2116.       && (regno = REGNO (addr),
  2117.           regno == FRAME_POINTER_REGNUM || regno == ARG_POINTER_REGNUM))
  2118.       || CONSTANT_ADDRESS_P (addr))
  2119.     return;
  2120.  
  2121.   /* If this address is not simply a register, try to fold it.  This will
  2122.      sometimes simplify the expression.  Many simplifications
  2123.      will not be valid, but some, usually applying the associative rule, will
  2124.      be valid and produce better code.  */
  2125.   if (GET_CODE (addr) != REG
  2126.       && validate_change (insn, loc, fold_rtx (addr, insn), 0))
  2127.     addr = *loc;
  2128.     
  2129.   /* If this address is not in the hash table, we can't do any better.
  2130.      Also, ignore if volatile.  */
  2131.   do_not_record = 0;
  2132.   hash_code = HASH (addr, Pmode);
  2133.   addr_volatile = do_not_record;
  2134.   do_not_record = save_do_not_record;
  2135.   hash_arg_in_memory = save_hash_arg_in_memory;
  2136.   hash_arg_in_struct = save_hash_arg_in_struct;
  2137.  
  2138.   if (addr_volatile)
  2139.     return;
  2140.  
  2141.   elt = lookup (addr, hash_code, Pmode);
  2142.  
  2143.   if (elt == 0)
  2144.     return;
  2145.  
  2146. #ifndef ADDRESS_COST
  2147.   our_cost = elt->cost;
  2148.  
  2149.   /* Find the lowest cost below ours that works.  */
  2150.   for (elt = elt->first_same_value; elt; elt = elt->next_same_value)
  2151.     if (elt->cost < our_cost
  2152.     && (GET_CODE (elt->exp) == REG || exp_equiv_p (elt->exp, elt->exp, 1))
  2153.     && validate_change (insn, loc, canon_reg (copy_rtx (elt->exp), 0), 0))
  2154.       return;
  2155.  
  2156. #else
  2157.  
  2158.   /* We need to find the best (under the criteria documented above) entry in
  2159.      the class that is valid.  We use the `flag' field to indicate choices
  2160.      that were invalid and iterate until we can't find a better one that
  2161.      hasn't already been tried.  */
  2162.  
  2163.   for (p = elt->first_same_value; p; p = p->next_same_value)
  2164.     p->flag = 0;
  2165.  
  2166.   while (found_better)
  2167.     {
  2168.       int best_addr_cost = ADDRESS_COST (*loc);
  2169.       int best_rtx_cost = (elt->cost + 1) >> 1;
  2170.       struct table_elt *best_elt = elt; 
  2171.  
  2172.       found_better = 0;
  2173.       for (p = elt->first_same_value; p; p = p->next_same_value)
  2174.     if (! p->flag
  2175.         && (GET_CODE (p->exp) == REG || exp_equiv_p (p->exp, p->exp, 1))
  2176.         && (ADDRESS_COST (p->exp) < best_addr_cost
  2177.         || (ADDRESS_COST (p->exp) == best_addr_cost
  2178.             && (p->cost + 1) >> 1 > best_rtx_cost)))
  2179.       {
  2180.         found_better = 1;
  2181.         best_addr_cost = ADDRESS_COST (p->exp);
  2182.         best_rtx_cost = (p->cost + 1) >> 1;
  2183.         best_elt = p;
  2184.       }
  2185.  
  2186.       if (found_better)
  2187.     {
  2188.       if (validate_change (insn, loc,
  2189.                    canon_reg (copy_rtx (best_elt->exp), 0), 0))
  2190.         return;
  2191.       else
  2192.         best_elt->flag = 1;
  2193.     }
  2194.     }
  2195. #endif
  2196. }
  2197.  
  2198. /* Given an operation (CODE, *PARG1, *PARG2), where code is a comparison
  2199.    operation (EQ, NE, GT, etc.), follow it back through the hash table and
  2200.    what values are being compared.
  2201.  
  2202.    *PARG1 and *PARG2 are updated to contain the rtx representing the values
  2203.    actually being compared.  For example, if *PARG1 was (cc0) and *PARG2
  2204.    was (const_int 0), *PARG1 and *PARG2 will be set to the objects that were
  2205.    compared to produce cc0.
  2206.  
  2207.    The return value is the comparison operator and is either the code of
  2208.    A or the code corresponding to the inverse of the comparison.  */
  2209.  
  2210. static enum rtx_code
  2211. find_comparison_args (code, parg1, parg2)
  2212.      enum rtx_code code;
  2213.      rtx *parg1, *parg2;
  2214. {
  2215.   rtx arg1, arg2;
  2216.   struct table_elt *elt, *p;
  2217.   int reverse_code = 0;
  2218.  
  2219.   arg1 = *parg1, arg2 = *parg2;
  2220.  
  2221.   /* If arg1 is a COMPARE, extract the comparison arguments from it.
  2222.      On machines with CC0, this is the only case that can occur, since
  2223.      fold_rtx will return the COMPARE or item being compared with zero
  2224.      when given CC0.  */
  2225.  
  2226.   if (GET_CODE (arg1) == COMPARE && arg2 == const0_rtx)
  2227.     {
  2228.       *parg1 = XEXP (arg1, 0), *parg2 = XEXP (arg1, 1);
  2229.       return code;
  2230.     }
  2231.  
  2232. #ifndef HAVE_cc0
  2233.   /* If ARG2 is const0_rtx and CODE is a comparison operator, look see what
  2234.      ARG1 is equivalent to.  Continue this process until the above condition
  2235.      is no longer true.  */
  2236.  
  2237.   while (GET_RTX_CLASS (code) == '<' && arg2 == const0_rtx)
  2238.     {
  2239.       /* Set non-zero when we find something of interest.  */
  2240.       rtx x = 0;
  2241.  
  2242.       /* ??? We could also check for
  2243.  
  2244.      (ne (and (eq (...) (const_int 1))) (const_int 0))
  2245.  
  2246.      and related forms, but let's wait until we see them occurring.  */
  2247.  
  2248.       /* Look up ARG1 in the hash table and see if it has an equivalence that
  2249.      lets us see what is being compared.  */
  2250.       elt = lookup (arg1, safe_hash (arg1, GET_MODE (arg1)) % NBUCKETS,
  2251.             GET_MODE (arg1));
  2252.       if (elt == 0)
  2253.     break;
  2254.  
  2255.       for (p = elt->first_same_value; p; p = p->next_same_value)
  2256.     {
  2257.       enum machine_mode inner_mode = GET_MODE (p->exp);
  2258.  
  2259.       /* If the entry isn't valid, skip it.  */
  2260.       if (! exp_equiv_p (p->exp, p->exp, 1))
  2261.         continue;
  2262.  
  2263.       if (GET_CODE (p->exp) == COMPARE
  2264.           /* Another possibility is that this machine has a compare insn
  2265.          that includes the comparison code.  In that case, ARG1 would
  2266.          be equivalent to a comparison operation that would set ARG1 to
  2267.          either STORE_FLAG_VALUE or zero.  If this is an NE operation,
  2268.          ORIG_CODE is the actual comparison being done; if it is an EQ,
  2269.          we must reverse ORIG_CODE.  On machine with a negative value
  2270.          for STORE_FLAG_VALUE, also look at LT and GE operations.  */
  2271.           || ((code == NE
  2272.            || (code == LT
  2273.                && GET_MODE_BITSIZE (inner_mode) <= HOST_BITS_PER_INT
  2274.                && (STORE_FLAG_VALUE
  2275.                & (1 << (GET_MODE_BITSIZE (inner_mode) - 1)))))
  2276.           && GET_RTX_CLASS (GET_CODE (p->exp)) == '<'))
  2277.         {
  2278.           x = p->exp;
  2279.           break;
  2280.         }
  2281.       else if ((code == EQ
  2282.             || (code == GE
  2283.             && GET_MODE_BITSIZE (inner_mode) <= HOST_BITS_PER_INT
  2284.             && (STORE_FLAG_VALUE
  2285.                 & (1 << (GET_MODE_BITSIZE (inner_mode) - 1)))))
  2286.            && GET_RTX_CLASS (GET_CODE (p->exp)) == '<')
  2287.         {
  2288.           reverse_code = 1;
  2289.           x = p->exp;
  2290.           break;
  2291.         }
  2292.     }
  2293.  
  2294.       /* If we didn't find a useful equivalence for ARG1, we are done.
  2295.      Otherwise, set up for the next iteration.  */
  2296.       if (x == 0)
  2297.     break;
  2298.  
  2299.       if (GET_RTX_CLASS (GET_CODE (x)) == '<')
  2300.     code = GET_CODE (x);
  2301.       arg1 = XEXP (x, 0),  arg2 = XEXP (x, 1);
  2302.     }
  2303. #endif
  2304.  
  2305.   /* Return our results.  */
  2306.   *parg1 = arg1, *parg2 = arg2;
  2307.  
  2308.   return reverse_code ? reverse_condition (code) : code;
  2309. }
  2310.  
  2311. /* Try to simplify a unary operation CODE whose output mode is to be
  2312.    MODE with input operand OP whose mode was originally OP_MODE.
  2313.    Return zero if no simplification can be made.  */
  2314.  
  2315. rtx
  2316. simplify_unary_operation (code, mode, op, op_mode)
  2317.      enum rtx_code code;
  2318.      enum machine_mode mode;
  2319.      rtx op;
  2320.      enum machine_mode op_mode;
  2321. {
  2322.   register int width = GET_MODE_BITSIZE (mode);
  2323.  
  2324. #if !defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
  2325.   if (code == FLOAT && GET_CODE (op) == CONST_INT)
  2326.     {
  2327.       REAL_VALUE_TYPE d;
  2328.  
  2329. #ifdef REAL_ARITHMETIC
  2330.       REAL_VALUE_FROM_INT (d, INTVAL (op), INTVAL (op) < 0 ? ~0 : 0);
  2331. #else
  2332.       d = (double) INTVAL (op);
  2333. #endif
  2334.       return CONST_DOUBLE_FROM_REAL_VALUE (d, mode);
  2335.     }
  2336.   else if (code == UNSIGNED_FLOAT && GET_CODE (op) == CONST_INT)
  2337.     {
  2338.       REAL_VALUE_TYPE d;
  2339.  
  2340. #ifdef REAL_ARITHMETIC
  2341.       REAL_VALUE_FROM_INT (d, INTVAL (op), 0);
  2342. #else
  2343.       d = (double) (unsigned int) INTVAL (op);
  2344. #endif
  2345.       return CONST_DOUBLE_FROM_REAL_VALUE (d, mode);
  2346.     }
  2347.  
  2348.   else if (code == FLOAT && GET_CODE (op) == CONST_DOUBLE
  2349.        && GET_MODE (op) == DImode)
  2350.     {
  2351.       REAL_VALUE_TYPE d;
  2352.  
  2353. #ifdef REAL_ARITHMETIC
  2354.       REAL_VALUE_FROM_INT (d, CONST_DOUBLE_LOW (op), CONST_DOUBLE_HIGH (op));
  2355. #else
  2356.       if (CONST_DOUBLE_HIGH (op) < 0)
  2357.     {
  2358.       d = (double) (~ CONST_DOUBLE_HIGH (op));
  2359.       d *= ((double) (1 << (HOST_BITS_PER_INT / 2))
  2360.         * (double) (1 << (HOST_BITS_PER_INT / 2)));
  2361.       d += (double) (unsigned) (~ CONST_DOUBLE_LOW (op));
  2362.       d = (- d - 1.0);
  2363.     }
  2364.       else
  2365.     {
  2366.       d = (double) CONST_DOUBLE_HIGH (op);
  2367.       d *= ((double) (1 << (HOST_BITS_PER_INT / 2))
  2368.         * (double) (1 << (HOST_BITS_PER_INT / 2)));
  2369.       d += (double) (unsigned) CONST_DOUBLE_LOW (op);
  2370.     }
  2371. #endif  /* REAL_ARITHMETIC */
  2372.       return CONST_DOUBLE_FROM_REAL_VALUE (d, mode);
  2373.     }
  2374.   else if (code == UNSIGNED_FLOAT && GET_CODE (op) == CONST_DOUBLE
  2375.        && GET_MODE (op) == DImode)
  2376.     {
  2377.       REAL_VALUE_TYPE d;
  2378.  
  2379. #ifdef REAL_ARITHMETIC
  2380.       REAL_VALUE_FROM_UNSIGNED_INT (d, CONST_DOUBLE_LOW (op),
  2381.                     CONST_DOUBLE_HIGH (op));
  2382. #else
  2383.       d = (double) CONST_DOUBLE_HIGH (op);
  2384.       d *= ((double) (1 << (HOST_BITS_PER_INT / 2))
  2385.         * (double) (1 << (HOST_BITS_PER_INT / 2)));
  2386.       d += (double) (unsigned) CONST_DOUBLE_LOW (op);
  2387. #endif  /* REAL_ARITHMETIC */
  2388.       return CONST_DOUBLE_FROM_REAL_VALUE (d, mode);
  2389.     }
  2390. #endif
  2391.  
  2392.   if (GET_CODE (op) == CONST_INT && width <= HOST_BITS_PER_INT && width > 0)
  2393.     {
  2394.       register int arg0 = INTVAL (op);
  2395.       register int val;
  2396.  
  2397.       switch (code)
  2398.     {
  2399.     case NOT:
  2400.       val = ~ arg0;
  2401.       break;
  2402.  
  2403.     case NEG:
  2404.       val = - arg0;
  2405.       break;
  2406.  
  2407.     case ABS:
  2408.       val = (arg0 >= 0 ? arg0 : - arg0);
  2409.       break;
  2410.  
  2411.     case FFS:
  2412.       /* Don't use ffs here.  Instead, get low order bit and then its
  2413.          number.  If arg0 is zero, this will return 0, as desired.  */
  2414.       arg0 &= GET_MODE_MASK (mode);
  2415.       val = exact_log2 (arg0 & (- arg0)) + 1;
  2416.       break;
  2417.  
  2418.     case TRUNCATE:
  2419.       val = arg0;
  2420.       break;
  2421.  
  2422.     case ZERO_EXTEND:
  2423.       if (op_mode == VOIDmode)
  2424.         op_mode = mode;
  2425.       if (GET_MODE_BITSIZE (op_mode) == HOST_BITS_PER_INT)
  2426.         val = arg0;
  2427.       else if (GET_MODE_BITSIZE (op_mode) < HOST_BITS_PER_INT)
  2428.         val = arg0 & ~((-1) << GET_MODE_BITSIZE (op_mode));
  2429.       else
  2430.         return 0;
  2431.       break;
  2432.  
  2433.     case SIGN_EXTEND:
  2434.       if (op_mode == VOIDmode)
  2435.         op_mode = mode;
  2436.       if (GET_MODE_BITSIZE (op_mode) == HOST_BITS_PER_INT)
  2437.         val = arg0;
  2438.       else if (GET_MODE_BITSIZE (op_mode) < HOST_BITS_PER_INT)
  2439.         {
  2440.           val = arg0 & ~((-1) << GET_MODE_BITSIZE (op_mode));
  2441.           if (val & (1 << (GET_MODE_BITSIZE (op_mode) - 1)))
  2442.         val -= 1 << GET_MODE_BITSIZE (op_mode);
  2443.         }
  2444.       else
  2445.         return 0;
  2446.       break;
  2447.  
  2448.     default:
  2449.       abort ();
  2450.     }
  2451.  
  2452.       /* Clear the bits that don't belong in our mode,
  2453.      unless they and our sign bit are all one.
  2454.      So we get either a reasonable negative value or a reasonable
  2455.      unsigned value for this mode.  */
  2456.       if (width < HOST_BITS_PER_INT
  2457.       && ((val & ((-1) << (width - 1))) != ((-1) << (width - 1))))
  2458.     val &= (1 << width) - 1;
  2459.  
  2460.       return gen_rtx (CONST_INT, VOIDmode, val);
  2461.     }
  2462.  
  2463. #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
  2464.   else if (GET_CODE (op) == CONST_DOUBLE
  2465.        && GET_MODE_CLASS (mode) == MODE_FLOAT)
  2466.     {
  2467.       REAL_VALUE_TYPE d;
  2468.       jmp_buf handler;
  2469.       rtx x;
  2470.  
  2471.       if (setjmp (handler))
  2472.     {
  2473.       warning ("floating point trap in constant folding");
  2474.       return 0;
  2475.     }
  2476.       set_float_handler (handler);
  2477.  
  2478.       REAL_VALUE_FROM_CONST_DOUBLE (d, op);
  2479.  
  2480.       switch (code)
  2481.     {
  2482.     case NEG:
  2483.       d = REAL_VALUE_NEGATE (d);
  2484.       break;
  2485.  
  2486.     case ABS:
  2487.       if (REAL_VALUES_LESS (d, 0.0))
  2488.         d = REAL_VALUE_NEGATE (d);
  2489.       break;
  2490.  
  2491.     case FLOAT_TRUNCATE:
  2492.       d = (double) REAL_VALUE_TRUNCATE (d);
  2493.       break;
  2494.  
  2495.     case FLOAT_EXTEND:
  2496.       /* All this does is change the mode.  */
  2497.       break;
  2498.  
  2499.     case FIX:
  2500.       d = (double) REAL_VALUE_FIX_TRUNCATE (d);
  2501.       break;
  2502.  
  2503.     case UNSIGNED_FIX:
  2504.       d = (double) REAL_VALUE_UNSIGNED_FIX_TRUNCATE (d);
  2505.       break;
  2506.  
  2507.     default:
  2508.       abort ();
  2509.     }
  2510.  
  2511.       x = immed_real_const_1 (d, mode);
  2512.       set_float_handler (0);
  2513.       return x;
  2514.     }
  2515.   else if (GET_CODE (op) == CONST_DOUBLE && GET_MODE_CLASS (mode) == MODE_INT
  2516.        && width <= HOST_BITS_PER_INT && width > 0)
  2517.     {
  2518.       REAL_VALUE_TYPE d;
  2519.       jmp_buf handler;
  2520.       rtx x;
  2521.       int val;
  2522.  
  2523.       if (setjmp (handler))
  2524.     {
  2525.       warning ("floating point trap in constant folding");
  2526.       return 0;
  2527.     }
  2528.       set_float_handler (handler);
  2529.  
  2530.       REAL_VALUE_FROM_CONST_DOUBLE (d, op);
  2531.  
  2532.       switch (code)
  2533.     {
  2534.     case FIX:
  2535.       val = REAL_VALUE_FIX (d);
  2536.       break;
  2537.  
  2538.     case UNSIGNED_FIX:
  2539.       val = REAL_VALUE_UNSIGNED_FIX (d);
  2540.       break;
  2541.  
  2542.     default:
  2543.       abort ();
  2544.     }
  2545.  
  2546.       set_float_handler (0);
  2547.  
  2548.       /* Clear the bits that don't belong in our mode,
  2549.      unless they and our sign bit are all one.
  2550.      So we get either a reasonable negative value or a reasonable
  2551.      unsigned value for this mode.  */
  2552.       if (width < HOST_BITS_PER_INT
  2553.       && ((val & ((-1) << (width - 1))) != ((-1) << (width - 1))))
  2554.     val &= (1 << width) - 1;
  2555.  
  2556.       return gen_rtx (CONST_INT, VOIDmode, val);
  2557.     }
  2558. #endif
  2559.   else if (GET_MODE_CLASS (mode) == MODE_INT
  2560.        || TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT)
  2561.     {
  2562.       /* There are some simplifications we can do even if the operands
  2563.      aren't constant, but they don't apply to floating-point
  2564.      unless not IEEE.  */
  2565.       switch (code)
  2566.     {
  2567.     case NEG:
  2568.     case NOT:
  2569.       /* (not (not X)) == X, similarly for NEG.  */
  2570.       if (GET_CODE (op) == code)
  2571.         return XEXP (op, 0);
  2572.       break;
  2573.  
  2574.     case SIGN_EXTEND:
  2575.       /* (sign_extend (truncate (minus (label_ref L1) (label_ref L2))))
  2576.          becomes just the MINUS if its mode is MODE.  This allows
  2577.          folding switch statements on machines using casesi (such as
  2578.          the Vax).  */
  2579.       if (GET_CODE (op) == TRUNCATE
  2580.           && GET_MODE (XEXP (op, 0)) == mode
  2581.           && GET_CODE (XEXP (op, 0)) == MINUS
  2582.           && GET_CODE (XEXP (XEXP (op, 0), 0)) == LABEL_REF
  2583.           && GET_CODE (XEXP (XEXP (op, 0), 1)) == LABEL_REF)
  2584.         return XEXP (op, 0);
  2585.       break;
  2586.     }
  2587.  
  2588.       return 0;
  2589.     }
  2590.   else
  2591.     return 0;
  2592. }
  2593.  
  2594. /* Simplify a binary operation CODE with result mode MODE, operating on OP0
  2595.    and OP1.  Return 0 if no simplification is possible.  */
  2596.  
  2597. rtx
  2598. simplify_binary_operation (code, mode, op0, op1)
  2599.      enum rtx_code code;
  2600.      enum machine_mode mode;
  2601.      rtx op0, op1;
  2602. {
  2603.   register int arg0, arg1, arg0s, arg1s;
  2604.   int val;
  2605.   int width = GET_MODE_BITSIZE (mode);
  2606.  
  2607.   /* If our result mode is VOIDmode and we have a comparison, use
  2608.      HOST_BITS_PER_INT.  */
  2609.  
  2610.   if (width == 0 && GET_RTX_CLASS (code) == '<')
  2611.     width = HOST_BITS_PER_INT;
  2612.  
  2613. #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
  2614.   if (GET_MODE_CLASS (mode) == MODE_FLOAT
  2615.       && GET_CODE (op0) == CONST_DOUBLE && GET_CODE (op1) == CONST_DOUBLE
  2616.       && mode == GET_MODE (op0) && mode == GET_MODE (op1))
  2617.     {
  2618.       if (mode == SFmode)
  2619.     {
  2620.       REAL_VALUE_TYPE f0, f1, value;
  2621.       jmp_buf handler;
  2622.  
  2623.       if (setjmp (handler))
  2624.         {
  2625.           warning ("floating point trap in constant folding");
  2626.           return 0;
  2627.         }
  2628.       set_float_handler (handler);
  2629.  
  2630.       REAL_VALUE_FROM_CONST_DOUBLE (f0, op0);
  2631.       REAL_VALUE_FROM_CONST_DOUBLE (f1, op1);
  2632.       f0 = REAL_VALUE_TRUNCATE (f0);
  2633.       f1 = REAL_VALUE_TRUNCATE (f1);
  2634.  
  2635. #ifdef REAL_ARITHMETIC
  2636.       REAL_ARITHMETIC (value, code, f0, f1);
  2637. #else
  2638.       switch (code)
  2639.         {
  2640.         case PLUS:
  2641.           value = f0 + f1;
  2642.           break;
  2643.         case MINUS:
  2644.           value = f0 - f1;
  2645.           break;
  2646.         case MULT:
  2647.           value = f0 * f1;
  2648.           break;
  2649.         case DIV:
  2650. #ifndef REAL_INFINITY
  2651.           if (f1 == 0)
  2652.         abort ();
  2653. #endif
  2654.           value = f0 / f1;
  2655.           break;
  2656.         default:
  2657.           abort ();
  2658.         }
  2659. #endif
  2660.  
  2661.       set_float_handler (0);
  2662.       return immed_real_const_1 (value, mode);
  2663.     }
  2664.       else if (mode == DFmode)
  2665.     {
  2666.       REAL_VALUE_TYPE d0, d1, value;
  2667.       
  2668.       REAL_VALUE_FROM_CONST_DOUBLE (d0, op0);
  2669.       REAL_VALUE_FROM_CONST_DOUBLE (d1, op1);
  2670.       
  2671. #ifdef REAL_ARITHMETIC
  2672.       REAL_ARITHMETIC (value, code, d0, d1);
  2673. #else
  2674.       switch (code)
  2675.         {
  2676.         case PLUS:
  2677.           value = d0 + d1;
  2678.           break;
  2679.         case MINUS:
  2680.           value = d0 - d1;
  2681.           break;
  2682.         case MULT:
  2683.           value = d0 * d1;
  2684.           break;
  2685.         case DIV:
  2686. #ifndef REAL_INFINITY
  2687.           if (d1 == 0)
  2688.         abort ();
  2689. #endif
  2690.           value = d0 / d1;
  2691.           break;
  2692.         default:
  2693.           abort ();
  2694.         }
  2695. #endif
  2696.  
  2697.       set_float_handler (0);
  2698.       return immed_real_const_1 (value, mode);
  2699.     }
  2700.     }
  2701.   else if (GET_MODE_CLASS (mode) == MODE_INT
  2702.        && GET_RTX_CLASS (code) != '<'
  2703.        && GET_CODE (op0) == CONST_DOUBLE && GET_CODE (op1) == CONST_DOUBLE
  2704.        && GET_MODE (op0) == GET_MODE (op1))
  2705.     {
  2706.       /* Cse currently cannot fold DImode operands.  */
  2707.       return 0;
  2708.     }
  2709. #endif  /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
  2710.  
  2711.   if (GET_CODE (op0) != CONST_INT || GET_CODE (op1) != CONST_INT
  2712.       || width > HOST_BITS_PER_INT || width == 0)
  2713.     {
  2714.       /* Even if we can't compute a constant result,
  2715.      there are some cases worth simplifying.  */
  2716.  
  2717.       /* For non-IEEE floating-point, if the two operands are equal, we know
  2718.      the result.  */
  2719.       if (GET_RTX_CLASS (code) == '<'
  2720.       && rtx_equal_p (op0, op1)
  2721.       && (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
  2722.           || GET_MODE_CLASS (GET_MODE (op0)) != MODE_FLOAT))
  2723.     return (code == EQ || code == GE || code == LE || code == LEU
  2724.         || code == GEU) ? const_true_rtx : const0_rtx;
  2725.  
  2726.       else if (GET_RTX_CLASS (code) == '<'
  2727.            && GET_CODE (op0) == CONST_DOUBLE
  2728.            && GET_CODE (op1) == CONST_DOUBLE
  2729.            && GET_MODE_CLASS (GET_MODE (op0)) == MODE_FLOAT)
  2730.     {
  2731.       REAL_VALUE_TYPE d0, d1;
  2732.       int value;
  2733.       jmp_buf handler;
  2734.       int op0lt, op1lt;
  2735.  
  2736.       if (setjmp (handler))
  2737.         {
  2738.           warning ("floating point trap in constant folding");
  2739.           return 0;
  2740.         }
  2741.       set_float_handler (handler);
  2742.       REAL_VALUE_FROM_CONST_DOUBLE (d0, op0);
  2743.       REAL_VALUE_FROM_CONST_DOUBLE (d1, op1);
  2744.       op0lt = REAL_VALUES_LESS (d0, d1);
  2745.       op1lt = REAL_VALUES_LESS (d1, d0);
  2746.       set_float_handler (0);
  2747.  
  2748.       switch (code)
  2749.         {
  2750.         case EQ:
  2751.           return (op0lt == 0 && op1lt == 0 ? const_true_rtx : const0_rtx);
  2752.         case NE:
  2753.           return (op0lt || op1lt) ? const_true_rtx : const0_rtx;
  2754.         case LE:
  2755.           return (op1lt == 0) ? const_true_rtx : const0_rtx;
  2756.         case LT:
  2757.           return op0lt ? const_true_rtx : const0_rtx;
  2758.         case GE:
  2759.           return (op0lt == 0) ? const_true_rtx : const0_rtx;
  2760.         case GT:
  2761.           return op1lt ? const_true_rtx : const0_rtx;
  2762.         }
  2763.     }
  2764.       
  2765.       switch (code)
  2766.     {
  2767.     case EQ:
  2768.       {
  2769.         /* EQ swaps truth values in non-CC0 case.  */
  2770.         rtx rval = const0_rtx;
  2771. #ifndef HAVE_cc0
  2772.         /* If we don't have cc0, then convert saved COMPARE
  2773.            rtl into a form where we can test EQ.  */
  2774.         if (GET_CODE (op0) == COMPARE && XEXP (op0, 1) == const0_rtx)
  2775.           {
  2776.         op0 = XEXP (op0, 0);
  2777.         rval = const_true_rtx;
  2778.           }
  2779. #endif
  2780.  
  2781. #if 0
  2782.         /* We can't make this assumption due to #pragma weak */
  2783.         if (CONSTANT_P (op0) && op1 == const0_rtx)
  2784.           return rval;
  2785. #endif
  2786.         if (FIXED_BASE_PLUS_P (op0) && op1 == const0_rtx)
  2787.           return rval;
  2788.         break;
  2789.       }
  2790.  
  2791.     case NE:
  2792. #ifndef HAVE_cc0
  2793.       /* If we don't have cc0, then convert saved COMPARE
  2794.          rtl into a form where we can test EQ.  */
  2795.       if (GET_CODE (op0) == COMPARE && XEXP (op0, 1) == const0_rtx)
  2796.         op0 = XEXP (op0, 0);
  2797. #endif
  2798.  
  2799. #if 0
  2800.       /* We can't make this assumption due to #pragma weak */
  2801.       if (CONSTANT_P (op0) && op1 == const0_rtx)
  2802.         return const_true_rtx;
  2803. #endif
  2804.       if (FIXED_BASE_PLUS_P (op0) && op1 == const0_rtx)
  2805.         return const_true_rtx;
  2806.       break;
  2807.  
  2808.     case LE:
  2809.     case LEU:
  2810.     case LT:
  2811.     case LTU:
  2812.     case GE:
  2813.     case GEU:
  2814.     case GT:
  2815.     case GTU:
  2816.       /* These can't be simplified.  */
  2817.       break;
  2818.  
  2819.     case PLUS:
  2820.       if (op1 == const0_rtx)
  2821.         return op0;
  2822.       /* In IEEE floating point, x+0 is not the same as x.  Similarly
  2823.          for the other optimizations below.  */
  2824.       if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
  2825.           && GET_MODE_CLASS (mode) != MODE_INT)
  2826.         break;
  2827.  
  2828.       if (op1 == fconst0_rtx || op1 == dconst0_rtx)
  2829.         return op0;
  2830.  
  2831.       /* (a - b) + b -> a, similarly a + (b - a) -> a */
  2832.       if (GET_CODE (op0) == MINUS
  2833.           && rtx_equal_p (XEXP (op0, 1), op1) && ! side_effects_p (op1))
  2834.         return XEXP (op0, 0);
  2835.  
  2836.       if (GET_CODE (op1) == MINUS
  2837.           && rtx_equal_p (XEXP (op1, 1), op0) && ! side_effects_p (op0))
  2838.         return XEXP (op1, 0);
  2839.  
  2840.       /* ((-a) + b) -> (b - a) and similarly for (a + (-b)) */
  2841.       if (GET_CODE (op0) == NEG)
  2842.         {
  2843.           rtx tem = simplify_binary_operation (MINUS, mode,
  2844.                            op1, XEXP (op0, 0));
  2845.           return tem ? tem : gen_rtx (MINUS, mode, op1, XEXP (op0, 0));
  2846.         }
  2847.       else if (GET_CODE (op1) == NEG)
  2848.         {
  2849.           rtx tem = simplify_binary_operation (MINUS, mode,
  2850.                            op0, XEXP (op1, 0));
  2851.           return tem ? tem : gen_rtx (MINUS, mode, op0, XEXP (op1, 0));
  2852.         }
  2853.           
  2854.       /* Handle both-operands-constant cases.  */
  2855.       if (CONSTANT_P (op0) && CONSTANT_P (op1)
  2856.           && GET_CODE (op0) != CONST_DOUBLE
  2857.           && GET_CODE (op1) != CONST_DOUBLE
  2858.           && GET_MODE_CLASS (mode) == MODE_INT)
  2859.         {
  2860.           if (GET_CODE (op1) == CONST_INT)
  2861.         return plus_constant (op0, INTVAL (op1));
  2862.           else
  2863.         return gen_rtx (CONST, mode,
  2864.                 gen_rtx (PLUS, mode,
  2865.                      GET_CODE (op0) == CONST
  2866.                      ? XEXP (op0, 0) : op0,
  2867.                      GET_CODE (op1) == CONST
  2868.                      ? XEXP (op1, 0) : op1));
  2869.         }
  2870.       else if (GET_CODE (op1) == CONST_INT
  2871.            && GET_CODE (op0) == PLUS
  2872.            && (CONSTANT_P (XEXP (op0, 0))
  2873.                || CONSTANT_P (XEXP (op0, 1))))
  2874.         /* constant + (variable + constant)
  2875.            can result if an index register is made constant.
  2876.            We simplify this by adding the constants.
  2877.            If we did not, it would become an invalid address.  */
  2878.         return plus_constant (op0, INTVAL (op1));
  2879.       break;
  2880.  
  2881.     case COMPARE:
  2882. #ifdef HAVE_cc0
  2883.       /* Convert (compare FOO (const_int 0)) to FOO unless we aren't
  2884.          using cc0, in which case we want to leave it as a COMPARE
  2885.          so we can distinguish it from a register-register-copy.  */
  2886.       if (op1 == const0_rtx)
  2887.         return op0;
  2888.       /* In IEEE floating point, x-0 is not the same as x.  */
  2889.       if (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT)
  2890.         if (op1 == fconst0_rtx || op1 == dconst0_rtx)
  2891.           return op0;
  2892. #else
  2893.       /* Do nothing here.  */
  2894. #endif
  2895.       break;
  2896.           
  2897.     case MINUS:
  2898.       if (op1 == const0_rtx)
  2899.         return op0;
  2900.       /* In IEEE floating point, x-0 is not the same as x.  */
  2901.       if (rtx_equal_p (op0, op1)
  2902.           && ! side_effects_p (op0)
  2903.           /* We can't assume x-x is 0
  2904.          even with non-IEEE floating point.  */
  2905.           && GET_MODE_CLASS (mode) != MODE_FLOAT)
  2906.         return const0_rtx;
  2907.  
  2908.       /* Change subtraction from zero into negation.  */
  2909.       if (op0 == const0_rtx || op0 == fconst0_rtx || op0 == dconst0_rtx)
  2910.         return gen_rtx (NEG, mode, op1);
  2911.  
  2912.       /* The remainer of these cases cannot be done for IEEE
  2913.          floating-point.  */
  2914.       if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
  2915.           && GET_MODE_CLASS (mode) != MODE_INT)
  2916.         break;
  2917.  
  2918.       if (op1 == fconst0_rtx || op1 == dconst0_rtx)
  2919.         return op0;
  2920.       
  2921.       /* (a + b) - a -> b, and (b - (a + b))  -> -a  */
  2922.       if (GET_CODE (op0) == PLUS
  2923.           && rtx_equal_p (XEXP (op0, 0), op1)
  2924.           && ! side_effects_p (op1))
  2925.         return XEXP (op0, 1);
  2926.       else if (GET_CODE (op0) == PLUS
  2927.            && rtx_equal_p (XEXP (op0, 1), op1)
  2928.            && ! side_effects_p (op1))
  2929.         return XEXP (op0, 0);
  2930.  
  2931.       if (GET_CODE (op1) == PLUS
  2932.           && rtx_equal_p (XEXP (op1, 0), op0)
  2933.           && ! side_effects_p (op0))
  2934.         {
  2935.           rtx tem = simplify_unary_operation (NEG, mode, XEXP (op1, 1),
  2936.                           mode);
  2937.  
  2938.           return tem ? tem : gen_rtx (NEG, mode, XEXP (op1, 1));
  2939.         }
  2940.       else if (GET_CODE (op1) == PLUS
  2941.            && rtx_equal_p (XEXP (op1, 1), op0)
  2942.            && ! side_effects_p (op0))
  2943.         {
  2944.           rtx tem = simplify_unary_operation (NEG, mode, XEXP (op1, 0),
  2945.                           mode);
  2946.  
  2947.           return tem ? tem : gen_rtx (NEG, mode, XEXP (op1, 0));
  2948.         }
  2949.  
  2950.       /* (a - (-b)) -> (a + b).  */
  2951.       if (GET_CODE (op1) == NEG)
  2952.         {
  2953.           rtx tem = simplify_binary_operation (PLUS, mode,
  2954.                            op0, XEXP (op1, 0));
  2955.           return tem ? tem : gen_rtx (PLUS, mode, op0, XEXP (op1, 0));
  2956.         }
  2957.  
  2958.       /* Don't let a relocatable value get a negative coeff.  */
  2959.       if (GET_CODE (op1) == CONST_INT)
  2960.         return plus_constant (op0, - INTVAL (op1));
  2961.       break;
  2962.  
  2963.     case MULT:
  2964.       if (op1 == constm1_rtx)
  2965.         return gen_rtx (NEG, mode, op0);
  2966.       if (op1 == const0_rtx && ! side_effects_p (op0))
  2967.         return const0_rtx;
  2968.       if (op1 == const1_rtx)
  2969.         return op0;
  2970.       /* Convert multiply by constant power of two into shift.  */
  2971.       if (GET_CODE (op1) == CONST_INT
  2972.           && (val = exact_log2 (INTVAL (op1))) >= 0)
  2973.         return gen_rtx (ASHIFT, mode, op0,
  2974.                 gen_rtx (CONST_INT, VOIDmode, val));
  2975.       /* In IEEE floating point, x*0 is not always 0.  */
  2976.       if (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
  2977.           && (op1 == fconst0_rtx || op1 == dconst0_rtx)
  2978.           && ! side_effects_p (op0))
  2979.         return op1;
  2980.       /* In IEEE floating point, x*1 is not equivalent to x for nans.
  2981.          However, ANSI says we can drop signals,
  2982.          so we can do this anyway.  */
  2983.       if (op1 == fconst1_rtx || op1 == dconst1_rtx)
  2984.         return op0;
  2985.  
  2986.       if (GET_CODE (op1) == CONST_DOUBLE
  2987.           && GET_MODE_CLASS (GET_MODE (op1)) == MODE_FLOAT)
  2988.         {
  2989.           REAL_VALUE_TYPE d;
  2990.           REAL_VALUE_FROM_CONST_DOUBLE (d, op1);
  2991.  
  2992.           /* x*2 is x+x and x*(-1) is -x */
  2993.           if (REAL_VALUES_EQUAL (d, dconst2)
  2994.           && GET_MODE (op0) == mode)
  2995.         return gen_rtx (PLUS, mode, op0, op0);
  2996.  
  2997.           else if (REAL_VALUES_EQUAL (d, dconstm1)
  2998.                && GET_MODE (op0) == mode)
  2999.         return gen_rtx (NEG, mode, op0);
  3000.         }
  3001.       break;
  3002.  
  3003.     case IOR:
  3004.       if (op1 == const0_rtx)
  3005.         return op0;
  3006.       if (GET_CODE (op1) == CONST_INT
  3007.           && (INTVAL (op1) & GET_MODE_MASK (mode)) == GET_MODE_MASK (mode))
  3008.         return op1;
  3009.       if (rtx_equal_p (op0, op1) && ! side_effects_p (op0))
  3010.         return op0;
  3011.       /* A | (~A) -> -1 */
  3012.       if (((GET_CODE (op0) == NOT && rtx_equal_p (XEXP (op0, 0), op1))
  3013.            || (GET_CODE (op1) == NOT && rtx_equal_p (XEXP (op1, 0), op0)))
  3014.           && ! side_effects_p (op0))
  3015.         return constm1_rtx;
  3016.       break;
  3017.  
  3018.     case XOR:
  3019.       if (op1 == const0_rtx)
  3020.         return op0;
  3021.       if (GET_CODE (op1) == CONST_INT
  3022.           && (INTVAL (op1) & GET_MODE_MASK (mode)) == GET_MODE_MASK (mode))
  3023.         return gen_rtx (NOT, mode, op0);
  3024.       if (op0 == op1 && ! side_effects_p (op0))
  3025.         return const0_rtx;
  3026.       break;
  3027.  
  3028.     case AND:
  3029.       if (op1 == const0_rtx && ! side_effects_p (op0))
  3030.         return const0_rtx;
  3031.       if (GET_CODE (op1) == CONST_INT
  3032.           && (INTVAL (op1) & GET_MODE_MASK (mode)) == GET_MODE_MASK (mode))
  3033.         return op0;
  3034.       if (op0 == op1 && ! side_effects_p (op0))
  3035.         return op0;
  3036.       /* A & (~A) -> 0 */
  3037.       if (((GET_CODE (op0) == NOT && rtx_equal_p (XEXP (op0, 0), op1))
  3038.            || (GET_CODE (op1) == NOT && rtx_equal_p (XEXP (op1, 0), op0)))
  3039.           && ! side_effects_p (op0))
  3040.         return const0_rtx;
  3041.       break;
  3042.  
  3043.     case UDIV:
  3044.       /* Convert divide by power of two into shift (divide by 1 handled
  3045.          below).  */
  3046.       if (GET_CODE (op1) == CONST_INT
  3047.           && (arg1 = exact_log2 (INTVAL (op1))) > 0)
  3048.         return gen_rtx (LSHIFTRT, mode, op0,
  3049.                 gen_rtx (CONST_INT, VOIDmode, arg1));
  3050.  
  3051.       /* ... fall through ... */
  3052.  
  3053.     case DIV:
  3054.       if (op1 == const1_rtx || op1 == fconst1_rtx || op1 == dconst1_rtx)
  3055.         return op0;
  3056.       else if ((op0 == const0_rtx || op0 == fconst0_rtx
  3057.             || op0 == dconst0_rtx)
  3058.            && ! side_effects_p (op1))
  3059.         return op0;
  3060. #if 0 /* Turned off till an expert says this is a safe thing to do.  */
  3061. #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
  3062.       /* Change division by a constant into multiplication.  */
  3063.       else if (GET_CODE (op1) == CONST_DOUBLE
  3064.            && GET_MODE_CLASS (GET_MODE (op1)) == MODE_FLOAT
  3065.            && op1 != fconst0_rtx && op1 != dconst0_rtx)
  3066.         {
  3067.           REAL_VALUE_TYPE d;
  3068.           REAL_VALUE_FROM_CONST_DOUBLE (d, op1);
  3069.           if (REAL_VALUES_EQUAL (d, dconst0))
  3070.         abort();
  3071. #if defined (REAL_ARITHMETIC)
  3072.           REAL_ARITHMETIC (d, RDIV_EXPR, dconst1, d);
  3073.           return gen_rtx (MULT, mode, op0, 
  3074.                   CONST_DOUBLE_FROM_REAL_VALUE (d, DFmode));
  3075. #else
  3076.           return gen_rtx (MULT, mode, op0, 
  3077.                   CONST_DOUBLE_FROM_REAL_VALUE (1./d, DFmode));
  3078.         }
  3079. #endif
  3080. #endif
  3081. #endif
  3082.       break;
  3083.  
  3084.     case UMOD:
  3085.       /* Handle modulus by power of two (mod with 1 handled below).  */
  3086.       if (GET_CODE (op1) == CONST_INT
  3087.           && exact_log2 (INTVAL (op1)) > 0)
  3088.         return gen_rtx (AND, mode, op0, 
  3089.                 gen_rtx (CONST_INT, VOIDmode, INTVAL (op1) - 1));
  3090.  
  3091.       /* ... fall through ... */
  3092.  
  3093.     case MOD:
  3094.       if ((op0 == const0_rtx || op1 == const1_rtx)
  3095.           && ! side_effects_p (op0) && ! side_effects_p (op1))
  3096.         return const0_rtx;
  3097.       break;
  3098.  
  3099.     case LSHIFT:
  3100.     case ASHIFT:
  3101.     case ROTATE:
  3102.     case ASHIFTRT:
  3103.     case LSHIFTRT:
  3104.     case ROTATERT:
  3105.       if (op1 == const0_rtx)
  3106.         return op0;
  3107.       if (op0 == const0_rtx && ! side_effects_p (op1))
  3108.         return op0;
  3109.       break;
  3110.  
  3111.     default:
  3112.       abort ();
  3113.     }
  3114.       
  3115.       return 0;
  3116.     }
  3117.  
  3118.   /* Get the integer argument values in two forms:
  3119.      zero-extended in ARG0, ARG1 and sign-extended in ARG0S, ARG1S.  */
  3120.  
  3121.   arg0 = INTVAL (op0);
  3122.   arg1 = INTVAL (op1);
  3123.  
  3124.   if (width < HOST_BITS_PER_INT)
  3125.     {
  3126.       arg0 &= (1 << width) - 1;
  3127.       arg1 &= (1 << width) - 1;
  3128.  
  3129.       arg0s = arg0;
  3130.       if (arg0s & (1 << (width - 1)))
  3131.     arg0s |= ((-1) << width);
  3132.  
  3133.       arg1s = arg1;
  3134.       if (arg1s & (1 << (width - 1)))
  3135.     arg1s |= ((-1) << width);
  3136.     }
  3137.   else
  3138.     {
  3139.       arg0s = arg0;
  3140.       arg1s = arg1;
  3141.     }
  3142.  
  3143.   /* Compute the value of the arithmetic.  */
  3144.  
  3145.   switch (code)
  3146.     {
  3147.     case PLUS:
  3148.       val = arg0 + arg1;
  3149.       break;
  3150.  
  3151.     case MINUS:
  3152.       val = arg0 - arg1;
  3153.       break;
  3154.  
  3155.     case MULT:
  3156.       val = arg0s * arg1s;
  3157.       break;
  3158.  
  3159.     case DIV:
  3160.       if (arg1s == 0)
  3161.     return 0;
  3162.       val = arg0s / arg1s;
  3163.       break;
  3164.  
  3165.     case MOD:
  3166.       if (arg1s == 0)
  3167.     return 0;
  3168.       val = arg0s % arg1s;
  3169.       break;
  3170.  
  3171.     case UDIV:
  3172.       if (arg1 == 0)
  3173.     return 0;
  3174.       val = (unsigned) arg0 / arg1;
  3175.       break;
  3176.  
  3177.     case UMOD:
  3178.       if (arg1 == 0)
  3179.     return 0;
  3180.       val = (unsigned) arg0 % arg1;
  3181.       break;
  3182.  
  3183.     case AND:
  3184.       val = arg0 & arg1;
  3185.       break;
  3186.  
  3187.     case IOR:
  3188.       val = arg0 | arg1;
  3189.       break;
  3190.  
  3191.     case XOR:
  3192.       val = arg0 ^ arg1;
  3193.       break;
  3194.  
  3195.     case NE:
  3196.       val = arg0 != arg1 ? STORE_FLAG_VALUE : 0;
  3197.       break;
  3198.  
  3199.     case EQ:
  3200.       val = arg0 == arg1 ? STORE_FLAG_VALUE : 0;
  3201.       break;
  3202.  
  3203.     case LE:
  3204.       val = arg0s <= arg1s ? STORE_FLAG_VALUE : 0;
  3205.       break;
  3206.  
  3207.     case LT:
  3208.       val = arg0s < arg1s ? STORE_FLAG_VALUE : 0;
  3209.       break;
  3210.  
  3211.     case GE:
  3212.       val = arg0s >= arg1s ? STORE_FLAG_VALUE : 0;
  3213.       break;
  3214.  
  3215.     case GT:
  3216.       val = arg0s > arg1s ? STORE_FLAG_VALUE : 0;
  3217.       break;
  3218.  
  3219.     case LEU:
  3220.       val = ((unsigned) arg0) <= ((unsigned) arg1) ? STORE_FLAG_VALUE : 0;
  3221.       break;
  3222.  
  3223.     case LTU:
  3224.       val = ((unsigned) arg0) < ((unsigned) arg1) ? STORE_FLAG_VALUE : 0;
  3225.       break;
  3226.  
  3227.     case GEU:
  3228.       val = ((unsigned) arg0) >= ((unsigned) arg1) ? STORE_FLAG_VALUE : 0;
  3229.       break;
  3230.  
  3231.     case GTU:
  3232.       val = ((unsigned) arg0) > ((unsigned) arg1) ? STORE_FLAG_VALUE : 0;
  3233.       break;
  3234.  
  3235.     case LSHIFTRT:
  3236.       /* If shift count is undefined, don't fold it; let the machine do
  3237.      what it wants.  But truncate it if the machine will do that.  */
  3238. #ifdef SHIFT_COUNT_TRUNCATED
  3239.       arg1 &= (BITS_PER_WORD - 1);
  3240. #endif
  3241.  
  3242.       if (arg1 < 0 || arg1 >= width)
  3243.     return 0;
  3244.  
  3245.       val = ((unsigned) arg0) >> arg1;
  3246.       break;
  3247.  
  3248.     case ASHIFT:
  3249.     case LSHIFT:
  3250. #ifdef SHIFT_COUNT_TRUNCATED
  3251.       arg1 &= (BITS_PER_WORD - 1);
  3252. #endif
  3253.  
  3254.       if (arg1 < 0 || arg1 >= width)
  3255.     return 0;
  3256.  
  3257.       val = ((unsigned) arg0) << arg1;
  3258.       break;
  3259.  
  3260.     case ASHIFTRT:
  3261. #ifdef SHIFT_COUNT_TRUNCATED
  3262.       arg1 &= (BITS_PER_WORD - 1);
  3263. #endif
  3264.  
  3265.       if (arg1 < 0 || arg1 >= width)
  3266.     return 0;
  3267.  
  3268.       val = arg0s >> arg1;
  3269.       break;
  3270.  
  3271.     case ROTATERT:
  3272.       if (arg1 < 0)
  3273.     return 0;
  3274.  
  3275.       arg1 %= width;
  3276.       val = ((((unsigned) arg0) << (width - arg1))
  3277.          | (((unsigned) arg0) >> arg1));
  3278.       break;
  3279.  
  3280.     case ROTATE:
  3281.       if (arg1 < 0)
  3282.     return 0;
  3283.  
  3284.       arg1 %= width;
  3285.       val = ((((unsigned) arg0) << arg1)
  3286.          | (((unsigned) arg0) >> (width - arg1)));
  3287.       break;
  3288.  
  3289.     case COMPARE:
  3290.       /* Do nothing here.  */
  3291.       return 0;
  3292.  
  3293.     default:
  3294.       abort ();
  3295.     }
  3296.  
  3297.   /* Clear the bits that don't belong in our mode, unless they and our sign
  3298.      bit are all one.  So we get either a reasonable negative value or a
  3299.      reasonable unsigned value for this mode.  */
  3300.   if (width < HOST_BITS_PER_INT
  3301.       && ((val & ((-1) << (width - 1))) != ((-1) << (width - 1))))
  3302.     val &= (1 << width) - 1;
  3303.   
  3304.   return gen_rtx (CONST_INT, VOIDmode, val);
  3305. }
  3306.  
  3307. /* Simplify CODE, an operation with result mode MODE and three operands,
  3308.    OP0, OP1, and OP2.  OP0_MODE was the mode of OP0 before it became
  3309.    a constant.  Return 0 if no simplifications is possible.  */
  3310.  
  3311. rtx
  3312. simplify_ternary_operation (code, mode, op0_mode, op0, op1, op2)
  3313.      enum rtx_code code;
  3314.      enum machine_mode mode, op0_mode;
  3315.      rtx op0, op1, op2;
  3316. {
  3317.   int width = GET_MODE_BITSIZE (mode);
  3318.  
  3319.   /* VOIDmode means "infinite" precision.  */
  3320.   if (width == 0)
  3321.     width = HOST_BITS_PER_INT;
  3322.  
  3323.   switch (code)
  3324.     {
  3325.     case SIGN_EXTRACT:
  3326.     case ZERO_EXTRACT:
  3327.       if (GET_CODE (op0) == CONST_INT
  3328.       && GET_CODE (op1) == CONST_INT
  3329.       && GET_CODE (op2) == CONST_INT
  3330.       && INTVAL (op1) + INTVAL (op2) <= GET_MODE_BITSIZE (op0_mode)
  3331.       && width <= HOST_BITS_PER_INT)
  3332.     {
  3333.       /* Extracting a bit-field from a constant */
  3334.       int val = INTVAL (op0);
  3335.  
  3336. #if BITS_BIG_ENDIAN
  3337.       val >>= (GET_MODE_BITSIZE (op0_mode) - INTVAL (op2) - INTVAL (op1));
  3338. #else
  3339.       val >>= INTVAL (op2);
  3340. #endif
  3341.       if (HOST_BITS_PER_INT != INTVAL (op1))
  3342.         {
  3343.           /* First zero-extend.  */
  3344.           val &= (1 << INTVAL (op1)) - 1;
  3345.           /* If desired, propagate sign bit.  */
  3346.           if (code == SIGN_EXTRACT && (val & (1 << (INTVAL (op1) - 1))))
  3347.         val |= ~ (1 << INTVAL (op1));
  3348.         }
  3349.  
  3350.       /* Clear the bits that don't belong in our mode,
  3351.          unless they and our sign bit are all one.
  3352.          So we get either a reasonable negative value or a reasonable
  3353.          unsigned value for this mode.  */
  3354.       if (width < HOST_BITS_PER_INT
  3355.           && ((val & ((-1) << (width - 1))) != ((-1) << (width - 1))))
  3356.         val &= (1 << width) - 1;
  3357.  
  3358.       return gen_rtx (CONST_INT, VOIDmode, val);
  3359.     }
  3360.       break;
  3361.  
  3362.     case IF_THEN_ELSE:
  3363.       if (GET_CODE (op0) == CONST_INT)
  3364.     return op0 != const0_rtx ? op1 : op2;
  3365.       break;
  3366.  
  3367.     default:
  3368.       abort ();
  3369.     }
  3370.  
  3371.   return 0;
  3372. }
  3373.  
  3374. /* If X is a nontrivial arithmetic operation on an argument
  3375.    for which a constant value can be determined, return
  3376.    the result of operating on that value, as a constant.
  3377.    Otherwise, return X, possibly with one or more operands
  3378.    modified by recursive calls to this function.
  3379.  
  3380.    If X is a register whose contents are known, we do NOT
  3381.    return those contents.  This is because an instruction that
  3382.    uses a register is usually faster than one that uses a constant.
  3383.  
  3384.    INSN is the insn that we may be modifying.  */
  3385.  
  3386. static rtx
  3387. fold_rtx (x, insn)
  3388.      rtx x;
  3389.      rtx insn;    
  3390. {
  3391.   register enum rtx_code code;
  3392.   register enum machine_mode mode;
  3393.   register char *fmt;
  3394.   register int i, val;
  3395.   rtx new = 0;
  3396.   int must_swap = 0;
  3397.  
  3398.   /* Folded equivalents of first two operands of X.  */
  3399.   rtx folded_arg0;
  3400.   rtx folded_arg1;
  3401.  
  3402.   /* Constant equivalents of first three operands of X;
  3403.      0 when no such equivalent is known.  */
  3404.   rtx const_arg0;
  3405.   rtx const_arg1;
  3406.   rtx const_arg2;
  3407.  
  3408.   /* The mode of the first operand of X.  We need this for sign and zero
  3409.      extends.  */
  3410.   enum machine_mode mode_arg0;
  3411.  
  3412.   if (x == 0)
  3413.     return x;
  3414.  
  3415.   mode = GET_MODE (x);
  3416.   code = GET_CODE (x);
  3417.   switch (code)
  3418.     {
  3419.     case CONST:
  3420.     case CONST_INT:
  3421.     case CONST_DOUBLE:
  3422.     case SYMBOL_REF:
  3423.     case LABEL_REF:
  3424.     case REG:
  3425.       /* No use simplifying an EXPR_LIST
  3426.      since they are used only for lists of args
  3427.      in a function call's REG_EQUAL note.  */
  3428.     case EXPR_LIST:
  3429.       return x;
  3430.  
  3431. #ifdef HAVE_cc0
  3432.     case CC0:
  3433.       return prev_insn_cc0;
  3434. #endif
  3435.  
  3436.     case PC:
  3437.       /* If the next insn is a CODE_LABEL followed by a jump table,
  3438.      PC's value is a LABEL_REF pointing to that label.  That
  3439.      lets us fold switch statements on the Vax.  */
  3440.       if (insn && GET_CODE (insn) == JUMP_INSN)
  3441.     {
  3442.       rtx next = next_nonnote_insn (insn);
  3443.  
  3444.       if (next && GET_CODE (next) == CODE_LABEL
  3445.           && NEXT_INSN (next) != 0
  3446.           && GET_CODE (NEXT_INSN (next)) == JUMP_INSN
  3447.           && (GET_CODE (PATTERN (NEXT_INSN (next))) == ADDR_VEC
  3448.           || GET_CODE (PATTERN (NEXT_INSN (next))) == ADDR_DIFF_VEC))
  3449.         return gen_rtx (LABEL_REF, Pmode, next);
  3450.     }
  3451.       break;
  3452.  
  3453.     case SUBREG:
  3454.       /* Fold SUBREG_REG.  If it changed, see if we can simplify the SUBREG.
  3455.      We might be able to if the SUBREG is extracting a single word in an
  3456.      integral mode or extracting the low part.  */
  3457.       folded_arg0 = fold_rtx (SUBREG_REG (x), insn);
  3458.       if (folded_arg0 != SUBREG_REG (x))
  3459.     {
  3460.       new = 0;
  3461.  
  3462.       if (GET_MODE_CLASS (mode) == MODE_INT
  3463.           && GET_MODE_SIZE (mode) == UNITS_PER_WORD
  3464.           && GET_MODE (SUBREG_REG (x)) != VOIDmode)
  3465.         new = operand_subword (folded_arg0, SUBREG_WORD (x), 0,
  3466.                    GET_MODE (SUBREG_REG (x)));
  3467.       if (new == 0 && subreg_lowpart_p (x))
  3468.         new = gen_lowpart_if_possible (mode, folded_arg0);
  3469.       if (new)
  3470.         return new;
  3471.     }
  3472.       return x;
  3473.  
  3474.     case NOT:
  3475.     case NEG:
  3476.       /* If we have (NOT Y), see if Y is known to be (NOT Z).
  3477.      If so, (NOT Y) simplifies to Z.  Similarly for NEG.  */
  3478.       new = lookup_as_function (XEXP (x, 0), code);
  3479.       if (new)
  3480.     return fold_rtx (copy_rtx (XEXP (new, 0)), insn);
  3481.       break;
  3482.       
  3483.     case MEM:
  3484.       find_best_addr (insn, &XEXP (x, 0));
  3485.  
  3486.       {
  3487.     /* Even if we don't fold in the insn itself,
  3488.        we can safely do so here, in hopes of getting a constant.  */
  3489.     rtx addr = fold_rtx (XEXP (x, 0), insn);
  3490.     rtx base = 0;
  3491.     int offset = 0;
  3492.  
  3493.     if (GET_CODE (addr) == REG
  3494.         && REGNO_QTY_VALID_P (REGNO (addr))
  3495.         && qty_const[reg_qty[REGNO (addr)]] != 0)
  3496.       addr = qty_const[reg_qty[REGNO (addr)]];
  3497.  
  3498.     /* If address is constant, split it into a base and integer offset.  */
  3499.     if (GET_CODE (addr) == SYMBOL_REF || GET_CODE (addr) == LABEL_REF)
  3500.       base = addr;
  3501.     else if (GET_CODE (addr) == CONST && GET_CODE (XEXP (addr, 0)) == PLUS
  3502.          && GET_CODE (XEXP (XEXP (addr, 0), 1)) == CONST_INT)
  3503.       {
  3504.         base = XEXP (XEXP (addr, 0), 0);
  3505.         offset = INTVAL (XEXP (XEXP (addr, 0), 1));
  3506.       }
  3507.     else if (GET_CODE (addr) == LO_SUM
  3508.          && GET_CODE (XEXP (addr, 1)) == SYMBOL_REF)
  3509.       base = XEXP (addr, 1);
  3510.  
  3511.     /* If this is a constant pool reference, we can fold it into its
  3512.        constant to allow better value tracking.  */
  3513.     if (base && GET_CODE (base) == SYMBOL_REF
  3514.         && CONSTANT_POOL_ADDRESS_P (base))
  3515.       {
  3516.         rtx constant = get_pool_constant (base);
  3517.         enum machine_mode const_mode = get_pool_mode (base);
  3518.         rtx new;
  3519.  
  3520.         if (CONSTANT_P (constant) && GET_CODE (constant) != CONST_INT)
  3521.           constant_pool_entries_cost = COST (constant);
  3522.  
  3523.         /* If we are loading the full constant, we have an equivalence.  */
  3524.         if (offset == 0 && mode == const_mode)
  3525.           return constant;
  3526.  
  3527.         /* If this actually isn't a constant (wierd!), we can't do
  3528.            anything.  Otherwise, handle the two most common cases:
  3529.            extracting a word from a multi-word constant, and extracting
  3530.            the low-order bits.  Other cases don't seem common enough to
  3531.            worry about.  */
  3532.         if (! CONSTANT_P (constant))
  3533.           return x;
  3534.  
  3535.         if (GET_MODE_CLASS (mode) == MODE_INT
  3536.         && GET_MODE_SIZE (mode) == UNITS_PER_WORD
  3537.         && offset % UNITS_PER_WORD == 0
  3538.         && (new = operand_subword (constant,
  3539.                        offset / UNITS_PER_WORD,
  3540.                        0, const_mode)) != 0)
  3541.           return new;
  3542.  
  3543.         if (((BYTES_BIG_ENDIAN
  3544.           && offset == GET_MODE_SIZE (GET_MODE (constant)) - 1)
  3545.          || (! BYTES_BIG_ENDIAN && offset == 0))
  3546.         && (new = gen_lowpart_if_possible (mode, constant)) != 0)
  3547.           return new;
  3548.       }
  3549.  
  3550.     /* If this is a reference to a label at a known position in a jump
  3551.        table, we also know its value.  */
  3552.     if (base && GET_CODE (base) == LABEL_REF)
  3553.       {
  3554.         rtx label = XEXP (base, 0);
  3555.         rtx table_insn = NEXT_INSN (label);
  3556.         
  3557.         if (table_insn && GET_CODE (table_insn) == JUMP_INSN
  3558.         && GET_CODE (PATTERN (table_insn)) == ADDR_VEC)
  3559.           {
  3560.         rtx table = PATTERN (table_insn);
  3561.  
  3562.         if (offset >= 0
  3563.             && (offset / GET_MODE_SIZE (GET_MODE (table))
  3564.             < XVECLEN (table, 0)))
  3565.           return XVECEXP (table, 0,
  3566.                   offset / GET_MODE_SIZE (GET_MODE (table)));
  3567.           }
  3568.         if (table_insn && GET_CODE (table_insn) == JUMP_INSN
  3569.         && GET_CODE (PATTERN (table_insn)) == ADDR_DIFF_VEC)
  3570.           {
  3571.         rtx table = PATTERN (table_insn);
  3572.  
  3573.         if (offset >= 0
  3574.             && (offset / GET_MODE_SIZE (GET_MODE (table))
  3575.             < XVECLEN (table, 1)))
  3576.           {
  3577.             offset /= GET_MODE_SIZE (GET_MODE (table));
  3578.             new = gen_rtx (MINUS, Pmode, XVECEXP (table, 1, offset),
  3579.                    XEXP (table, 0));
  3580.  
  3581.             if (GET_MODE (table) != Pmode)
  3582.               new = gen_rtx (TRUNCATE, GET_MODE (table), new);
  3583.  
  3584.             return new;
  3585.           }
  3586.           }
  3587.       }
  3588.  
  3589.     return x;
  3590.       }
  3591.     }
  3592.  
  3593.   const_arg0 = 0;
  3594.   const_arg1 = 0;
  3595.   const_arg2 = 0;
  3596.   mode_arg0 = VOIDmode;
  3597.  
  3598.   /* Try folding our operands.
  3599.      Then see which ones have constant values known.  */
  3600.  
  3601.   fmt = GET_RTX_FORMAT (code);
  3602.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  3603.     if (fmt[i] == 'e')
  3604.       {
  3605.     rtx arg = XEXP (x, i);
  3606.     rtx folded_arg = arg, const_arg = 0;
  3607.     rtx cheap_arg, expensive_arg;
  3608.     rtx replacements[2];
  3609.     int j;
  3610.  
  3611.     /* Most arguments are cheap, so handle them specially.  */
  3612.     switch (GET_CODE (arg))
  3613.       {
  3614.       case REG:
  3615.         if (REGNO_QTY_VALID_P (REGNO (arg))
  3616.         && qty_const[reg_qty[REGNO (arg)]] != 0
  3617.         && GET_CODE (qty_const[reg_qty[REGNO (arg)]]) != REG
  3618.         && GET_CODE (qty_const[reg_qty[REGNO (arg)]]) != PLUS)
  3619.           const_arg = qty_const[reg_qty[REGNO (arg)]];
  3620.         break;
  3621.  
  3622.       case SUBREG:
  3623.         const_arg = equiv_constant (arg);
  3624.         break;
  3625.  
  3626.       case CONST:
  3627.       case CONST_INT:
  3628.       case SYMBOL_REF:
  3629.       case LABEL_REF:
  3630.       case CONST_DOUBLE:
  3631.         const_arg = arg;
  3632.         break;
  3633.  
  3634. #ifdef HAVE_cc0
  3635.       case CC0:
  3636.         folded_arg = prev_insn_cc0;
  3637.         const_arg = equiv_constant (folded_arg);
  3638.         break;
  3639. #endif
  3640.  
  3641.       default:
  3642.         folded_arg = fold_rtx (arg, insn);
  3643.         const_arg = equiv_constant (folded_arg);
  3644.       }
  3645.  
  3646.     /* For the first three operands, see if the operand
  3647.        is constant or equivalent to a constant.  */
  3648.     switch (i)
  3649.       {
  3650.       case 0:
  3651.         folded_arg0 = folded_arg;
  3652.         const_arg0 = const_arg;
  3653.         mode_arg0 = GET_MODE (arg);
  3654.         break;
  3655.       case 1:
  3656.         folded_arg1 = folded_arg;
  3657.         const_arg1 = const_arg;
  3658.         break;
  3659.       case 2:
  3660.         const_arg2 = const_arg;
  3661.         break;
  3662.       }
  3663.  
  3664.     /* Pick the least expensive of the folded argument and an
  3665.        equivalent constant argument.  */
  3666.     if (const_arg == 0 || const_arg == folded_arg
  3667.         || COST (const_arg) > COST (folded_arg))
  3668.       cheap_arg = folded_arg, expensive_arg = const_arg;
  3669.     else
  3670.       cheap_arg = const_arg, expensive_arg = folded_arg;
  3671.  
  3672.     /* Try to replace the operand with the cheapest of the two
  3673.        possibilities.  If it doesn't work and this is either of the first
  3674.        two operands of a commutative operation, try swapping them.
  3675.        If THAT fails, try the more expensive, provided it is cheaper
  3676.        than what is already there.  */
  3677.     if (cheap_arg == XEXP (x, i))
  3678.       continue;
  3679.  
  3680.     replacements[0] = cheap_arg, replacements[1] = expensive_arg;
  3681.     for (j = 0;
  3682.          j < 2 && replacements[j]
  3683.          && COST (replacements[j]) < COST (XEXP (x, i));
  3684.          j++)
  3685.       {
  3686.         if (validate_change (insn, &XEXP (x, i), replacements[j], 0))
  3687.           break;
  3688.  
  3689.         if (code == NE || code == EQ || GET_RTX_CLASS (code) == 'c')
  3690.           {
  3691.         validate_change (insn, &XEXP (x, i), XEXP (x, 1 - i), 1);
  3692.         validate_change (insn, &XEXP (x, 1 - i), replacements[j], 1);
  3693.  
  3694.         if (apply_change_group ())
  3695.           {
  3696.             /* Swap them back to be invalid so that this loop can
  3697.                continue and flag them to be swapped back later.  */
  3698.             rtx tem;
  3699.  
  3700.             tem = XEXP (x, 0); XEXP (x, 0) = XEXP (x, 1);
  3701.                        XEXP (x, 1) = tem;
  3702.             must_swap = 1;
  3703.             break;
  3704.           }
  3705.           }
  3706.       }
  3707.       }
  3708.  
  3709.     else if (fmt[i] == 'E')
  3710.       /* Don't try to fold inside of a vector of expressions.
  3711.      Doing nothing is harmless.  */
  3712.       ;
  3713.  
  3714.   /* If a commutative operation, place a constant integer as the second
  3715.      operand unless the first operand is also a constant integer.  Otherwise,
  3716.      place any constant second unless the first operand is also a constant.  */
  3717.  
  3718.   if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
  3719.     {
  3720.       if (must_swap || (const_arg0
  3721.               && (const_arg1 == 0
  3722.                       || (GET_CODE (const_arg0) == CONST_INT
  3723.                     && GET_CODE (const_arg1) != CONST_INT))))
  3724.     {
  3725.       register rtx tem = XEXP (x, 0);
  3726.  
  3727.       validate_change (insn, &XEXP (x, 0), XEXP (x, 1), 1);
  3728.       validate_change (insn, &XEXP (x, 1), tem, 1);
  3729.       if (apply_change_group ())
  3730.         {
  3731.           tem = const_arg0, const_arg0 = const_arg1, const_arg1 = tem;
  3732.           tem = folded_arg0, folded_arg0 = folded_arg1, folded_arg1 = tem;
  3733.         }
  3734.     }
  3735.     }
  3736.  
  3737.   /* If X is an arithmetic operation, see if we can simplify it.  */
  3738.  
  3739.   switch (GET_RTX_CLASS (code))
  3740.     {
  3741.     case '1':
  3742.       new = simplify_unary_operation (code, mode,
  3743.                       const_arg0 ? const_arg0 : folded_arg0,
  3744.                       mode_arg0);
  3745.       break;
  3746.       
  3747.     case '<':
  3748.       /* See what items are actually being compared and set FOLDED_ARG[01]
  3749.      to those values and CODE to the actual comparison code.  If any are
  3750.      constant, set CONST_ARG0 and CONST_ARG1 appropriately.  We needn't
  3751.      do anything if both operands are already known to be constant.  */
  3752.  
  3753.       if (const_arg0 == 0 || const_arg1 == 0)
  3754.     {
  3755.       enum machine_mode mode = GET_MODE (folded_arg0);
  3756.       struct table_elt *p0, *p1;
  3757.  
  3758.       code = find_comparison_args (code, &folded_arg0, &folded_arg1);
  3759.       const_arg0 = equiv_constant (folded_arg0);
  3760.       const_arg1 = equiv_constant (folded_arg1);
  3761.  
  3762.       /* If we do not now have two constants being compared, see if we
  3763.          can nevertheless deduce some things about the comparison.  */
  3764.       if (const_arg0 == 0 || const_arg1 == 0)
  3765.         {
  3766.           /* Is FOLDED_ARG0 frame-pointer plus a constant?  Or non-explicit
  3767.          constant?  These aren't zero, but we don't know their sign. */
  3768.           if (const_arg1 == const0_rtx
  3769.           && (FIXED_BASE_PLUS_P (folded_arg0)
  3770. #if 0  /* Sad to say, on sysvr4, #pragma weak can make a symbol address
  3771.       come out as 0.  */
  3772.               || GET_CODE (folded_arg0) == SYMBOL_REF
  3773. #endif
  3774.               || GET_CODE (folded_arg0) == LABEL_REF
  3775.               || GET_CODE (folded_arg0) == CONST))
  3776.         {
  3777.           if (code == EQ)
  3778.             return const0_rtx;
  3779.           else if (code == NE)
  3780.             return const_true_rtx;
  3781.         }
  3782.  
  3783.           /* See if the two operands are the same.  We don't do this
  3784.          for IEEE floating-point since we can't assume x == x
  3785.          since x might be a NaN.  */
  3786.  
  3787.           if (mode != VOIDmode
  3788.           && (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
  3789.               || GET_MODE_CLASS (mode) != MODE_FLOAT)
  3790.           && (folded_arg0 == folded_arg1
  3791.               || (GET_CODE (folded_arg0) == REG
  3792.               && GET_CODE (folded_arg1) == REG
  3793.               && (reg_qty[REGNO (folded_arg0)]
  3794.                   == reg_qty[REGNO (folded_arg1)]))
  3795.               || ((p0 = lookup (folded_arg0,
  3796.                     (safe_hash (folded_arg0, mode)
  3797.                      % NBUCKETS), mode))
  3798.               && (p1 = lookup (folded_arg1,
  3799.                        (safe_hash (folded_arg1, mode)
  3800.                         % NBUCKETS), mode))
  3801.               && p0->first_same_value == p1->first_same_value)))
  3802.         return ((code == EQ || code == LE || code == GE
  3803.              || code == LEU || code == GEU)
  3804.             ? const_true_rtx : const0_rtx);
  3805.  
  3806.           /* If FOLDED_ARG0 is a register, see if the comparison we are
  3807.          doing now is either the same as we did before or the reverse
  3808.          (we only check the reverse if not floating-point).  */
  3809.           else if (GET_CODE (folded_arg0) == REG)
  3810.         {
  3811.           int qty = reg_qty[REGNO (folded_arg0)];
  3812.  
  3813.           if (REGNO_QTY_VALID_P (REGNO (folded_arg0))
  3814.               && (comparison_dominates_p (qty_comparison_code[qty], code)
  3815.               || (comparison_dominates_p (qty_comparison_code[qty],
  3816.                               reverse_condition (code))
  3817.                   && (GET_MODE_CLASS (GET_MODE (folded_arg0))
  3818.                   == MODE_INT)))
  3819.               && (rtx_equal_p (qty_comparison_const[qty], folded_arg1)
  3820.               || (GET_CODE (folded_arg1) == REG
  3821.                   && (reg_qty[REGNO (folded_arg1)]
  3822.                   == qty_comparison_qty[qty]))))
  3823.             return (comparison_dominates_p (qty_comparison_code[qty],
  3824.                             code)
  3825.                 ? const_true_rtx : const0_rtx);
  3826.         }
  3827.         }
  3828.     }
  3829.  
  3830.       /* ... fall through to generic two-operand case.  */
  3831.  
  3832.     case '2':
  3833.     case 'c':
  3834.       new = simplify_binary_operation (code, mode,
  3835.                        const_arg0 ? const_arg0 : folded_arg0,
  3836.                        const_arg1 ? const_arg1 : folded_arg1);
  3837.       break;
  3838.  
  3839.     case '3':
  3840.     case 'b':
  3841.       new = simplify_ternary_operation (code, mode, mode_arg0,
  3842.                     const_arg0 ? const_arg0 : folded_arg0,
  3843.                     const_arg1 ? const_arg1 : folded_arg1,
  3844.                     const_arg2 ? const_arg2 : XEXP (x, 2));
  3845.       break;
  3846.     }
  3847.  
  3848.   /* There are a few more simplifications we can make once we have folded
  3849.      the operand and found any equivalent constants.  */
  3850.   switch (code)
  3851.     {
  3852.     case PLUS:
  3853.       /* If the second operand is a LABEL_REF, see if the first is a MINUS
  3854.      with that LABEL_REF as its second operand.  If so, the result is the
  3855.      first operand of that MINUS.  This handles switches with an
  3856.      ADDR_DIFF_VEC table.  */
  3857.       if (const_arg1 && GET_CODE (const_arg1) == LABEL_REF)
  3858.     {
  3859.       rtx y = lookup_as_function (folded_arg0, MINUS);
  3860.  
  3861.       if (y != 0 && GET_CODE (XEXP (y, 1)) == LABEL_REF
  3862.           && XEXP (XEXP (y, 1), 0) == XEXP (const_arg1, 0))
  3863.         return XEXP (y, 0);
  3864.     }
  3865.  
  3866.       /* ... fall through ... */
  3867.  
  3868.     case IOR:     case AND:       case XOR:
  3869.     case MULT:    case DIV:       case UDIV:
  3870.     case ASHIFT:  case LSHIFTRT:  case ASHIFTRT:
  3871.       /* If we have (<op> <reg> <const_int>) for an associative OP and REG is
  3872.      known to be of similar form, we may be able to replace the operation
  3873.      with a combined operation.  This may eliminate the intermediate
  3874.      operation if every use is simplified in this way.  Note that the
  3875.      similar optimization done by combine.c only works if the intermediate
  3876.      operation's result has only one reference.  */
  3877.  
  3878.       if (GET_CODE (folded_arg0) == REG
  3879.       && const_arg1 && GET_CODE (const_arg1) == CONST_INT)
  3880.     {
  3881.       rtx y = lookup_as_function (folded_arg0, code);
  3882.       rtx inner_const;
  3883.       enum rtx_code associate_code;
  3884.       rtx new_const;
  3885.  
  3886.       if (y == 0
  3887.           || (inner_const = equiv_constant (XEXP (y, 1))) == 0
  3888.           || GET_CODE (inner_const) != CONST_INT
  3889.           /* If we have compiled a statement like "if (x == (x & mask1))",
  3890.          and now are looking at "x & mask2", we will have a case where
  3891.          the first operand of Y is the same as our first operand.
  3892.          Unless we detect this case, an infinite loop will result.  */
  3893.           || XEXP (y, 0) == folded_arg0)
  3894.         break;
  3895.  
  3896.       /* Don't associate these operations if they are a PLUS with the
  3897.          same constant and it is a power of two.  These might be doable
  3898.          with a pre- or post-increment.  Similarly for two subtracts of
  3899.          identical powers of two with post decrement.  */
  3900.  
  3901.       if (code == PLUS && INTVAL (const_arg1) == INTVAL (inner_const)
  3902.           && (0
  3903. #if defined(HAVE_PRE_INCREMENT) || defined(HAVE_POST_INCREMENT)
  3904.           || exact_log2 (INTVAL (const_arg1) >= 0)
  3905. #endif
  3906. #if defined(HAVE_PRE_DECREMENT) || defined(HAVE_POST_DECREMENT)
  3907.           || exact_log2 (- INTVAL (const_arg1)) >= 0
  3908. #endif
  3909.           ))
  3910.         break;
  3911.  
  3912.       /* Compute the code used to compose the constants.  For example,
  3913.          A/C1/C2 is A/(C1 * C2), so if CODE == DIV, we want MULT.  */
  3914.  
  3915.       associate_code
  3916.         = (code == MULT || code == DIV || code == UDIV ? MULT
  3917.            : (code == IOR || code == AND || code == XOR) ? code : PLUS);
  3918.  
  3919.       new_const = simplify_binary_operation (associate_code, mode,
  3920.                          const_arg1, inner_const);
  3921.  
  3922.       if (new_const == 0)
  3923.         break;
  3924.  
  3925.       y = fold_rtx (copy_rtx (XEXP (y, 0)), insn);
  3926.       new = simplify_binary_operation (code, mode, y, new_const);
  3927.       if (new)
  3928.         return new;
  3929.  
  3930.       return gen_rtx (code, mode, y, new_const);
  3931.     }
  3932.       break;
  3933.     }
  3934.  
  3935.   if (new)
  3936.     return new;
  3937.   else
  3938.     return x;
  3939. }
  3940.  
  3941. /* Return a constant value currently equivalent to X.
  3942.    Return 0 if we don't know one.  */
  3943.  
  3944. static rtx
  3945. equiv_constant (x)
  3946.      rtx x;
  3947. {
  3948.   rtx tem1;
  3949.  
  3950.   if (CONSTANT_P (x))
  3951.     return x;
  3952.   else if (GET_CODE (x) == REG
  3953.        && REGNO_QTY_VALID_P (REGNO (x))
  3954.        && (tem1 = qty_const[reg_qty[REGNO (x)]]) != 0
  3955.        /* Make sure it is really a constant */
  3956.        && GET_CODE (tem1) != REG && GET_CODE (tem1) != PLUS)
  3957.     return tem1;
  3958.   /* If integer truncation is being done with SUBREG,
  3959.      we can compute the result.  */
  3960.   else if (GET_CODE (x) == SUBREG && SUBREG_WORD (x) == 0
  3961.        && REGNO_QTY_VALID_P (REGNO (SUBREG_REG (x)))
  3962.        && (tem1 = qty_const[reg_qty[REGNO (SUBREG_REG (x))]]) != 0
  3963.        /* Make sure it is a known integer.  */
  3964.        && GET_CODE (tem1) == CONST_INT
  3965.        && GET_MODE_SIZE (GET_MODE (x)) <= HOST_BITS_PER_INT
  3966.        /* Make sure this SUBREG is truncation.  */
  3967.        && GET_MODE_SIZE (GET_MODE (x)) < GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
  3968.     {
  3969.       int value = INTVAL (tem1);
  3970.       if (GET_MODE_BITSIZE (GET_MODE (x)) != HOST_BITS_PER_INT)
  3971.     value &= (1 << GET_MODE_BITSIZE (GET_MODE (x))) - 1;
  3972.  
  3973.       if (value == INTVAL (tem1))
  3974.     return tem1;
  3975.       else
  3976.     return gen_rtx (CONST_INT, VOIDmode, value);
  3977.     }
  3978.   /* If this is a single word of a multi-word value, see if we previously
  3979.      assigned a value to that word.  */
  3980.   if (GET_CODE (x) == SUBREG && GET_MODE_SIZE (GET_MODE (x)) <= UNITS_PER_WORD
  3981.       && GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))) > UNITS_PER_WORD
  3982.       && (tem1 = lookup_as_function (x, CONST_INT)) != 0)
  3983.     return tem1;
  3984. #ifdef HAVE_cc0
  3985.   else if (x == cc0_rtx && prev_insn_cc0 && CONSTANT_P (prev_insn_cc0))
  3986.     return prev_insn_cc0;
  3987. #endif
  3988.  
  3989.   return 0;
  3990. }
  3991.  
  3992. /* Assuming that X is an rtx (e.g., MEM, REG or SUBREG) for a fixed-point
  3993.    number, return an rtx (MEM, SUBREG, or CONST_INT) that refers to the
  3994.    least-significant part of X.
  3995.    MODE specifies how big a part of X to return.  
  3996.  
  3997.    If the requested operation cannot be done, 0 is returned.
  3998.  
  3999.    This is similar to gen_lowpart in emit-rtl.c.  */
  4000.  
  4001. rtx
  4002. gen_lowpart_if_possible (mode, x)
  4003.      enum machine_mode mode;
  4004.      register rtx x;
  4005. {
  4006.   rtx result = gen_lowpart_common (mode, x);
  4007.  
  4008.   if (result)
  4009.     return result;
  4010.   else if (GET_CODE (x) == MEM)
  4011.     {
  4012.       /* This is the only other case we handle.  */
  4013.       register int offset = 0;
  4014.       rtx new;
  4015.  
  4016. #if WORDS_BIG_ENDIAN
  4017.       offset = (max (GET_MODE_SIZE (GET_MODE (x)), UNITS_PER_WORD)
  4018.         - max (GET_MODE_SIZE (mode), UNITS_PER_WORD));
  4019. #endif
  4020. #if BYTES_BIG_ENDIAN
  4021.       /* Adjust the address so that the address-after-the-data
  4022.      is unchanged.  */
  4023.       offset -= (min (UNITS_PER_WORD, GET_MODE_SIZE (mode))
  4024.          - min (UNITS_PER_WORD, GET_MODE_SIZE (GET_MODE (x))));
  4025. #endif
  4026.       new = gen_rtx (MEM, mode, plus_constant (XEXP (x, 0), offset));
  4027.       if (! memory_address_p (mode, XEXP (new, 0)))
  4028.     return 0;
  4029.       MEM_VOLATILE_P (new) = MEM_VOLATILE_P (x);
  4030.       RTX_UNCHANGING_P (new) = RTX_UNCHANGING_P (x);
  4031.       MEM_IN_STRUCT_P (new) = MEM_IN_STRUCT_P (x);
  4032.       return new;
  4033.     }
  4034.   else
  4035.     return 0;
  4036. }
  4037.  
  4038. /* Given INSN, a jump insn, TAKEN indicates if we are following the "taken"
  4039.    branch.  It will be zero if not.
  4040.  
  4041.    In certain cases, this can cause us to add an equivalence.  For example,
  4042.    if we are following the taken case of 
  4043.        if (i == 2)
  4044.    we can add the fact that `i' and '2' are now equivalent.
  4045.  
  4046.    In any case, we can record that this comparison was passed.  If the same
  4047.    comparison is seen later, we will know its value.  */
  4048.  
  4049. static void
  4050. record_jump_equiv (insn, taken)
  4051.      rtx insn;
  4052.      int taken;
  4053. {
  4054.   int cond_known_true;
  4055.   rtx op0, op1;
  4056.   int op0_hash_code, op1_hash_code;
  4057.   int op0_in_memory, op0_in_struct, op1_in_memory, op1_in_struct;
  4058.   enum machine_mode mode;
  4059.   struct table_elt *op0_elt, *op1_elt;
  4060.   int reversed_nonequality = 0;
  4061.   enum rtx_code code;
  4062.  
  4063.   /* Ensure this is the right kind of insn.  */
  4064.   if (! condjump_p (insn) || simplejump_p (insn))
  4065.     return;
  4066.  
  4067.   /* See if this jump condition is known true or false.  */
  4068.   if (taken)
  4069.     cond_known_true = (XEXP (SET_SRC (PATTERN (insn)), 2) == pc_rtx);
  4070.   else
  4071.     cond_known_true = (XEXP (SET_SRC (PATTERN (insn)), 1) == pc_rtx);
  4072.  
  4073.   /* Get the type of comparison being done and the operands being compared.
  4074.      If we had to reverse a non-equality condition, record that fact so we
  4075.      know that it isn't valid for floating-point.  */
  4076.   code = GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 0));
  4077.   op0 = fold_rtx (XEXP (XEXP (SET_SRC (PATTERN (insn)), 0), 0), insn);
  4078.   op1 = fold_rtx (XEXP (XEXP (SET_SRC (PATTERN (insn)), 0), 1), insn);
  4079.  
  4080.   code = find_comparison_args (code, &op0, &op1);
  4081.   if (! cond_known_true)
  4082.     {
  4083.       reversed_nonequality = (code != EQ && code != NE);
  4084.       code = reverse_condition (code);
  4085.     }
  4086.  
  4087.   /* The mode is the mode of the non-constant.  */
  4088.   mode = GET_MODE (op0);
  4089.   if (mode == VOIDmode) mode = GET_MODE (op1);
  4090.  
  4091.   /* Hash both operands.  */
  4092.  
  4093.   do_not_record = 0;
  4094.   hash_arg_in_memory = 0;
  4095.   hash_arg_in_struct = 0;
  4096.   op0_hash_code = HASH (op0, mode);
  4097.   op0_in_memory = hash_arg_in_memory;
  4098.   op0_in_struct = hash_arg_in_struct;
  4099.  
  4100.   if (do_not_record)
  4101.     return;
  4102.  
  4103.   do_not_record = 0;
  4104.   hash_arg_in_memory = 0;
  4105.   hash_arg_in_struct = 0;
  4106.   op1_hash_code = HASH (op1, mode);
  4107.   op1_in_memory = hash_arg_in_memory;
  4108.   op1_in_struct = hash_arg_in_struct;
  4109.   
  4110.   if (do_not_record)
  4111.     return;
  4112.  
  4113.   /* Look up both operands.  */
  4114.   op0_elt = lookup (op0, op0_hash_code, mode);
  4115.   op1_elt = lookup (op1, op1_hash_code, mode);
  4116.  
  4117.   /* If we aren't setting two things equal all we can do is save this
  4118.      comparison.  */
  4119.   if (code != EQ)
  4120.     {
  4121.       /* If we reversed a floating-point comparison, if OP0 is not a
  4122.      register, or if OP1 is neither a register or constant, we can't
  4123.      do anything.  */
  4124.       if ((reversed_nonequality && GET_MODE_CLASS (mode) != MODE_INT)
  4125.       || GET_CODE (op0) != REG
  4126.       || (GET_CODE (op1) != REG && ! CONSTANT_P (op1)))
  4127.     return;
  4128.  
  4129.       /* Put OP0 in the hash table if it isn't already.  This gives it a
  4130.      new quantity number.  */
  4131.       if (op0_elt == 0)
  4132.     {
  4133.       if (insert_regs (op0, 0, 0))
  4134.         op0_hash_code = HASH (op0, mode);
  4135.       op0_elt = insert (op0, 0, op0_hash_code, mode);
  4136.       op0_elt->in_memory = op0_in_memory;
  4137.       op0_elt->in_struct = op0_in_struct;
  4138.     }
  4139.  
  4140.       qty_comparison_code[reg_qty[REGNO (op0)]] = code;
  4141.       if (GET_CODE (op1) == REG)
  4142.     {
  4143.       /* Put OP1 in the hash table so it gets a new quantity number.  */
  4144.       if (op1_elt == 0)
  4145.         {
  4146.           if (insert_regs (op1, 0, 0))
  4147.         op1_hash_code = HASH (op1, mode);
  4148.           op1_elt = insert (op1, 0, op1_hash_code, mode);
  4149.           op1_elt->in_memory = op1_in_memory;
  4150.           op1_elt->in_struct = op1_in_struct;
  4151.         }
  4152.  
  4153.       qty_comparison_qty[reg_qty[REGNO (op0)]] = reg_qty[REGNO (op1)];
  4154.       qty_comparison_const[reg_qty[REGNO (op0)]] = 0;
  4155.     }
  4156.       else
  4157.     {
  4158.       qty_comparison_qty[reg_qty[REGNO (op0)]] = -1;
  4159.       qty_comparison_const[reg_qty[REGNO (op0)]] = op1;
  4160.     }
  4161.  
  4162.       return;
  4163.     }
  4164.  
  4165.   /* If both are equivalent, merge the two classes.  Save this class for
  4166.      `cse_set_around_loop'.  */
  4167.   if (op0_elt && op1_elt)
  4168.     {
  4169.       merge_equiv_classes (op0_elt, op1_elt);
  4170.       last_jump_equiv_class = op0_elt;
  4171.     }
  4172.  
  4173.   /* For whichever side doesn't have an equivalence, make one.  */
  4174.   if (op0_elt == 0)
  4175.     {
  4176.       if (insert_regs (op0, op1_elt, 0))
  4177.     op0_hash_code = HASH (op0, mode);
  4178.       op0_elt = insert (op0, op1_elt, op0_hash_code, mode);
  4179.       op0_elt->in_memory = op0_in_memory;
  4180.       op0_elt->in_struct = op0_in_struct;
  4181.       last_jump_equiv_class = op0_elt;
  4182.     }
  4183.  
  4184.   if (op1_elt == 0)
  4185.     {
  4186.       if (insert_regs (op1, op0_elt, 0))
  4187.     op1_hash_code = HASH (op1, mode);
  4188.       op1_elt = insert (op1, op0_elt, op1_hash_code, mode);
  4189.       op1_elt->in_memory = op1_in_memory;
  4190.       op1_elt->in_struct = op1_in_struct;
  4191.       last_jump_equiv_class = op1_elt;
  4192.     }
  4193. }
  4194.  
  4195. /* CSE processing for one instruction.
  4196.    First simplify sources and addresses of all assignments
  4197.    in the instruction, using previously-computed equivalents values.
  4198.    Then install the new sources and destinations in the table
  4199.    of available values.  */
  4200.  
  4201. /* Data on one SET contained in the instruction.  */
  4202.  
  4203. struct set
  4204. {
  4205.   /* The SET rtx itself.  */
  4206.   rtx rtl;
  4207.   /* The SET_SRC of the rtx (the original value, if it is changing).  */
  4208.   rtx src;
  4209.   /* The hash-table element for the SET_SRC of the SET.  */
  4210.   struct table_elt *src_elt;
  4211.   /* Hash code for the SET_SRC.  */
  4212.   int src_hash_code;
  4213.   /* Hash code for the SET_DEST.  */
  4214.   int dest_hash_code;
  4215.   /* The SET_DEST, with SUBREG, etc., stripped.  */
  4216.   rtx inner_dest;
  4217.   /* Place where the pointer to the INNER_DEST was found.  */
  4218.   rtx *inner_dest_loc;
  4219.   /* Nonzero if the SET_SRC is in memory.  */ 
  4220.   char src_in_memory;
  4221.   /* Nonzero if the SET_SRC is in a structure.  */ 
  4222.   char src_in_struct;
  4223.   /* Nonzero if the SET_SRC contains something
  4224.      whose value cannot be predicted and understood.  */
  4225.   char src_volatile;
  4226.   /* Original machine mode, in case it becomes a CONST_INT.  */
  4227.   enum machine_mode mode;
  4228.   /* A constant equivalent for SET_SRC, if any.  */
  4229.   rtx src_const;
  4230.   /* Hash code of constant equivalent for SET_SRC.  */
  4231.   int src_const_hash_code;
  4232.   /* Table entry for constant equivalent for SET_SRC, if any.  */
  4233.   struct table_elt *src_const_elt;
  4234. };
  4235.  
  4236. static void
  4237. cse_insn (insn)
  4238.      rtx insn;
  4239. {
  4240.   register rtx x = PATTERN (insn);
  4241.   rtx tem;
  4242.   register int i;
  4243.   register int n_sets = 0;
  4244.  
  4245.   /* Records what this insn does to set CC0.  */
  4246.   rtx this_insn_cc0 = 0;
  4247.   struct write_data writes_memory;
  4248.   static struct write_data init = {0, 0, 0, 0};
  4249.  
  4250.   rtx src_eqv = 0;
  4251.   struct table_elt *src_eqv_elt = 0;
  4252.   int src_eqv_volatile;
  4253.   int src_eqv_in_memory;
  4254.   int src_eqv_in_struct;
  4255.   int src_eqv_hash_code;
  4256.  
  4257.   struct set *sets;
  4258.  
  4259.   this_insn = insn;
  4260.   writes_memory = init;
  4261.  
  4262.   /* Find all the SETs and CLOBBERs in this instruction.
  4263.      Record all the SETs in the array `set' and count them.
  4264.      Also determine whether there is a CLOBBER that invalidates
  4265.      all memory references, or all references at varying addresses.  */
  4266.  
  4267.   if (GET_CODE (x) == SET)
  4268.     {
  4269.       sets = (struct set *) alloca (sizeof (struct set));
  4270.       sets[0].rtl = x;
  4271.  
  4272.       /* Ignore SETs that are unconditional jumps.
  4273.      They never need cse processing, so this does not hurt.
  4274.      The reason is not efficiency but rather
  4275.      so that we can test at the end for instructions
  4276.      that have been simplified to unconditional jumps
  4277.      and not be misled by unchanged instructions
  4278.      that were unconditional jumps to begin with.  */
  4279.       if (SET_DEST (x) == pc_rtx
  4280.       && GET_CODE (SET_SRC (x)) == LABEL_REF)
  4281.     ;
  4282.  
  4283.       /* Don't count call-insns, (set (reg 0) (call ...)), as a set.
  4284.      The hard function value register is used only once, to copy to
  4285.      someplace else, so it isn't worth cse'ing (and on 80386 is unsafe)!
  4286.      Ensure we invalidate the destination register.  On the 80386 no
  4287.      other code would invalidate it since it is a fixed_reg.  */
  4288.  
  4289.       else if (GET_CODE (SET_SRC (x)) == CALL)
  4290.     {
  4291.       canon_reg (SET_SRC (x), insn);
  4292.       fold_rtx (SET_SRC (x), insn);
  4293.       invalidate (SET_DEST (x));
  4294.     }
  4295.       else
  4296.     n_sets = 1;
  4297.     }
  4298.   else if (GET_CODE (x) == PARALLEL)
  4299.     {
  4300.       register int lim = XVECLEN (x, 0);
  4301.  
  4302.       sets = (struct set *) alloca (lim * sizeof (struct set));
  4303.  
  4304.       /* Find all regs explicitly clobbered in this insn,
  4305.      and ensure they are not replaced with any other regs
  4306.      elsewhere in this insn.
  4307.      When a reg that is clobbered is also used for input,
  4308.      we should presume that that is for a reason,
  4309.      and we should not substitute some other register
  4310.      which is not supposed to be clobbered.
  4311.      Therefore, this loop cannot be merged into the one below
  4312.      because a CALL may preceed a CLOBBER and refer to the
  4313.      value clobbered.  We must not let a canonicalization do
  4314.      anything in that case.  */
  4315.       for (i = 0; i < lim; i++)
  4316.     {
  4317.       register rtx y = XVECEXP (x, 0, i);
  4318.       if (GET_CODE (y) == CLOBBER && GET_CODE (XEXP (y, 0)) == REG)
  4319.         invalidate (XEXP (y, 0));
  4320.     }
  4321.         
  4322.       for (i = 0; i < lim; i++)
  4323.     {
  4324.       register rtx y = XVECEXP (x, 0, i);
  4325.       if (GET_CODE (y) == SET)
  4326.         {
  4327.           /* As above, we ignore unconditional jumps and call-insns. */
  4328.           if (GET_CODE (SET_SRC (y)) == CALL)
  4329.         {
  4330.           canon_reg (SET_SRC (y), insn);
  4331.           fold_rtx (SET_SRC (y), insn);
  4332.           invalidate (SET_DEST (y));
  4333.         }
  4334.           else if (SET_DEST (y) == pc_rtx
  4335.                && GET_CODE (SET_SRC (y)) == LABEL_REF)
  4336.         ;
  4337.           else
  4338.         sets[n_sets++].rtl = y;
  4339.         }
  4340.       else if (GET_CODE (y) == CLOBBER)
  4341.         {
  4342.           /* If we clobber memory, take note of that,
  4343.          and canon the address.
  4344.          This does nothing when a register is clobbered
  4345.          because we have already invalidated the reg.  */
  4346.           if (GET_CODE (XEXP (y, 0)) == MEM)
  4347.         {
  4348.           canon_reg (XEXP (y, 0), 0);
  4349.           note_mem_written (XEXP (y, 0), &writes_memory);
  4350.         }
  4351.         }
  4352.       else if (GET_CODE (y) == USE
  4353.            && ! (GET_CODE (XEXP (y, 0)) == REG
  4354.              && REGNO (XEXP (y, 0)) < FIRST_PSEUDO_REGISTER))
  4355.         canon_reg (y, 0);
  4356.       else if (GET_CODE (y) == CALL)
  4357.         {
  4358.           canon_reg (y, insn);
  4359.           fold_rtx (y, insn);
  4360.         }
  4361.     }
  4362.     }
  4363.   else if (GET_CODE (x) == CLOBBER)
  4364.     {
  4365.       if (GET_CODE (XEXP (x, 0)) == MEM)
  4366.     {
  4367.       canon_reg (XEXP (x, 0), 0);
  4368.       note_mem_written (XEXP (x, 0), &writes_memory);
  4369.     }
  4370.     }
  4371.  
  4372.   /* Canonicalize a USE of a pseudo register or memory location.  */
  4373.   else if (GET_CODE (x) == USE
  4374.        && ! (GET_CODE (XEXP (x, 0)) == REG
  4375.          && REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER))
  4376.     canon_reg (XEXP (x, 0), 0);
  4377.   else if (GET_CODE (x) == CALL)
  4378.     {
  4379.       canon_reg (x, insn);
  4380.       fold_rtx (x, insn);
  4381.     }
  4382.  
  4383.   if (n_sets == 1 && REG_NOTES (insn) != 0)
  4384.     {
  4385.       /* Store the equivalent value in SRC_EQV, if different.  */
  4386.       rtx tem = find_reg_note (insn, REG_EQUAL, 0);
  4387.  
  4388.       if (tem && ! rtx_equal_p (XEXP (tem, 0), SET_SRC (sets[0].rtl)))
  4389.         src_eqv = canon_reg (XEXP (tem, 0), 0);
  4390.     }
  4391.  
  4392.   /* Canonicalize sources and addresses of destinations.
  4393.      We do this in a separate pass to avoid problems when a MATCH_DUP is
  4394.      present in the insn pattern.  In that case, we want to ensure that
  4395.      we don't break the duplicate nature of the pattern.  So we will replace
  4396.      both operands at the same time.  Otherwise, we would fail to find an
  4397.      equivalent substitution in the loop calling validate_change below.
  4398.      (We also speed up that loop when a canonicalization was done since
  4399.      recog_memoized need not be called for just a canonicalization unless
  4400.      a pseudo register is being replaced by a hard reg of vice versa.)
  4401.  
  4402.      We used to suppress canonicalization of DEST if it appears in SRC,
  4403.      but we don't do this any more.
  4404.  
  4405.      ??? The way this code is written now, if we have a MATCH_DUP between
  4406.      two operands that are pseudos and we would want to canonicalize them
  4407.      to a hard register, we won't do that.  The only time this would happen
  4408.      is if the hard reg was a fixed register, and this should be rare.
  4409.  
  4410.      ??? This won't work if there is a MATCH_DUP between an input and an
  4411.      output, but these never worked and must be declared invalid.  */
  4412.  
  4413.   for (i = 0; i < n_sets; i++)
  4414.     {
  4415.       rtx dest = SET_DEST (sets[i].rtl);
  4416.       rtx src = SET_SRC (sets[i].rtl);
  4417.       rtx new = canon_reg (src, insn);
  4418.  
  4419.       if (GET_CODE (new) == REG && GET_CODE (src) == REG
  4420.       && ((REGNO (new) < FIRST_PSEUDO_REGISTER)
  4421.           != (REGNO (src) < FIRST_PSEUDO_REGISTER)))
  4422.     validate_change (insn, &SET_SRC (sets[i].rtl), new, 0);
  4423.       else
  4424.     SET_SRC (sets[i].rtl) = new;
  4425.  
  4426.       if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
  4427.     {
  4428.       validate_change (insn, &XEXP (dest, 1),
  4429.                canon_reg (XEXP (dest, 1), insn), 0);
  4430.       validate_change (insn, &XEXP (dest, 2),
  4431.                canon_reg (XEXP (dest, 2), insn), 0);
  4432.     }
  4433.  
  4434.       while (GET_CODE (dest) == SUBREG || GET_CODE (dest) == STRICT_LOW_PART
  4435.          || GET_CODE (dest) == ZERO_EXTRACT
  4436.          || GET_CODE (dest) == SIGN_EXTRACT)
  4437.     dest = XEXP (dest, 0);
  4438.  
  4439.       if (GET_CODE (dest) == MEM)
  4440.     canon_reg (dest, insn);
  4441.     }
  4442.  
  4443.   /* Set sets[i].src_elt to the class each source belongs to.
  4444.      Detect assignments from or to volatile things
  4445.      and set set[i] to zero so they will be ignored
  4446.      in the rest of this function.
  4447.  
  4448.      Nothing in this loop changes the hash table or the register chains.  */
  4449.  
  4450.   for (i = 0; i < n_sets; i++)
  4451.     {
  4452.       register rtx src, dest;
  4453.       register rtx src_folded;
  4454.       register struct table_elt *elt = 0, *p;
  4455.       enum machine_mode mode;
  4456.       rtx src_eqv_here;
  4457.       rtx src_const = 0;
  4458.       rtx src_related = 0;
  4459.       struct table_elt *src_const_elt = 0;
  4460.       int src_cost = 10000, src_eqv_cost = 10000, src_folded_cost = 10000;
  4461.       int src_related_cost = 10000, src_elt_cost = 10000;
  4462.       /* Set non-zero if we need to call force_const_mem on with the
  4463.      contents of src_folded before using it.  */
  4464.       int src_folded_force_flag = 0;
  4465.  
  4466.       dest = SET_DEST (sets[i].rtl);
  4467.       src = SET_SRC (sets[i].rtl);
  4468.  
  4469.       /* If SRC is a constant that has no machine mode,
  4470.      hash it with the destination's machine mode.
  4471.      This way we can keep different modes separate.  */
  4472.  
  4473.       mode = GET_MODE (src) == VOIDmode ? GET_MODE (dest) : GET_MODE (src);
  4474.       sets[i].mode = mode;
  4475.  
  4476.       if (src_eqv)
  4477.     {
  4478.       enum machine_mode eqvmode = mode;
  4479.       if (GET_CODE (dest) == STRICT_LOW_PART)
  4480.         eqvmode = GET_MODE (SUBREG_REG (XEXP (dest, 0)));
  4481.       do_not_record = 0;
  4482.       hash_arg_in_memory = 0;
  4483.       hash_arg_in_struct = 0;
  4484.       src_eqv = fold_rtx (src_eqv, insn);
  4485.       src_eqv_hash_code = HASH (src_eqv, eqvmode);
  4486.  
  4487.       /* Find the equivalence class for the equivalent expression.  */
  4488.  
  4489.       if (!do_not_record)
  4490.         src_eqv_elt = lookup (src_eqv, src_eqv_hash_code, eqvmode);
  4491.  
  4492.       src_eqv_volatile = do_not_record;
  4493.       src_eqv_in_memory = hash_arg_in_memory;
  4494.       src_eqv_in_struct = hash_arg_in_struct;
  4495.     }
  4496.  
  4497.       /* If this is a STRICT_LOW_PART assignment, src_eqv corresponds to the
  4498.      value of the INNER register, not the destination.  So it is not
  4499.      a legal substitution for the source.  But save it for later.  */
  4500.       if (GET_CODE (dest) == STRICT_LOW_PART)
  4501.     src_eqv_here = 0;
  4502.       else
  4503.     src_eqv_here = src_eqv;
  4504.  
  4505.       /* Simplify and foldable subexpressions in SRC.  Then get the fully-
  4506.      simplified result, which may not necessarily be valid.  */
  4507.       src_folded = fold_rtx (src, insn);
  4508.  
  4509.       /* Compute SRC's hash code, and also notice if it
  4510.      should not be recorded at all.  In that case,
  4511.      prevent any further processing of this assignment.  */
  4512.       do_not_record = 0;
  4513.       hash_arg_in_memory = 0;
  4514.       hash_arg_in_struct = 0;
  4515.  
  4516.       sets[i].src = src;
  4517.       sets[i].src_hash_code = HASH (src, mode);
  4518.       sets[i].src_volatile = do_not_record;
  4519.       sets[i].src_in_memory = hash_arg_in_memory;
  4520.       sets[i].src_in_struct = hash_arg_in_struct;
  4521.  
  4522.       /* If source is a perverse subreg (such as QI treated as an SI),
  4523.      treat it as volatile.  It may do the work of an SI in one context
  4524.      where the extra bits are not being used, but cannot replace an SI
  4525.      in general.  */
  4526.       if (GET_CODE (src) == SUBREG
  4527.       && (GET_MODE_SIZE (GET_MODE (src))
  4528.           > GET_MODE_SIZE (GET_MODE (SUBREG_REG (src)))))
  4529.     sets[i].src_volatile = 1;
  4530.  
  4531.       /* Locate all possible equivalent forms for SRC.  Try to replace
  4532.          SRC in the insn with each cheaper equivalent.
  4533.  
  4534.          We have the following types of equivalents: SRC itself, a folded
  4535.          version, a value given in a REG_EQUAL note, or a value related
  4536.      to a constant.
  4537.  
  4538.          Each of these equivalents may be part of an additional class
  4539.          of equivalents (if more than one is in the table, they must be in
  4540.          the same class; we check for this).
  4541.  
  4542.      If the source is volatile, we don't do any table lookups.
  4543.  
  4544.          We note any constant equivalent for possible later use in a
  4545.          REG_NOTE.  */
  4546.  
  4547.       if (!sets[i].src_volatile)
  4548.     elt = lookup (src, sets[i].src_hash_code, mode);
  4549.  
  4550.       sets[i].src_elt = elt;
  4551.  
  4552.       if (elt && src_eqv_here && src_eqv_elt)
  4553.         {
  4554.           if (elt->first_same_value != src_eqv_elt->first_same_value)
  4555.         {
  4556.           /* The REG_EQUAL is indicating that two formerly distinct
  4557.          classes are now equivalent.  So merge them.  */
  4558.           merge_equiv_classes (elt, src_eqv_elt);
  4559.           src_eqv_hash_code = HASH (src_eqv, elt->mode);
  4560.           src_eqv_elt = lookup (src_eqv, src_eqv_hash_code, elt->mode);
  4561.         }
  4562.  
  4563.           src_eqv_here = 0;
  4564.         }
  4565.  
  4566.       else if (src_eqv_elt)
  4567.         elt = src_eqv_elt;
  4568.  
  4569.       /* Try to find a constant somewhere and record it in `src_const'.
  4570.      Record its table element, if any, in `src_const_elt'.  Look in
  4571.      any known equivalences first.  (If the constant is not in the
  4572.      table, also set `sets[i].src_const_hash_code').  */
  4573.       if (elt)
  4574.         for (p = elt->first_same_value; p; p = p->next_same_value)
  4575.       if (p->is_const)
  4576.         {
  4577.           src_const = p->exp;
  4578.           src_const_elt = elt;
  4579.           break;
  4580.         }
  4581.  
  4582.       if (src_const == 0
  4583.       && (CONSTANT_P (src_folded)
  4584.           /* Consider (minus (label_ref L1) (label_ref L2)) as 
  4585.          "constant" here so we will record it. This allows us
  4586.          to fold switch statements when an ADDR_DIFF_VEC is used.  */
  4587.           || (GET_CODE (src_folded) == MINUS
  4588.           && GET_CODE (XEXP (src_folded, 0)) == LABEL_REF
  4589.           && GET_CODE (XEXP (src_folded, 1)) == LABEL_REF)))
  4590.     src_const = src_folded, src_const_elt = elt;
  4591.       else if (src_const == 0 && src_eqv_here && CONSTANT_P (src_eqv_here))
  4592.     src_const = src_eqv_here, src_const_elt = src_eqv_elt;
  4593.  
  4594.       /* If we don't know if the constant is in the table, get its
  4595.      hash code and look it up.  */
  4596.       if (src_const && src_const_elt == 0)
  4597.     {
  4598.       sets[i].src_const_hash_code = HASH (src_const, mode);
  4599.       src_const_elt = lookup (src_const, sets[i].src_const_hash_code,
  4600.                   mode);
  4601.     }
  4602.  
  4603.       sets[i].src_const = src_const;
  4604.       sets[i].src_const_elt = src_const_elt;
  4605.  
  4606.       /* If the constant and our source are both in the table, mark them as
  4607.      equivalent.  Otherwise, if a constant is in the table but the source
  4608.      isn't, set ELT to it.  */
  4609.       if (src_const_elt && elt
  4610.       && src_const_elt->first_same_value != elt->first_same_value)
  4611.     merge_equiv_classes (elt, src_const_elt);
  4612.       else if (src_const_elt && elt == 0)
  4613.     elt = src_const_elt;
  4614.  
  4615.       /* See if there is a register linearly related to a constant
  4616.          equivalent of SRC.  */
  4617.       if (src_const
  4618.       && (GET_CODE (src_const) == CONST
  4619.           || (src_const_elt && src_const_elt->related_value != 0)))
  4620.         {
  4621.           src_related = use_related_value (src_const, src_const_elt);
  4622.           if (src_related)
  4623.             {
  4624.           struct table_elt *src_related_elt
  4625.             = lookup (src_related, HASH (src_related, mode), mode);
  4626.           if (src_related_elt && elt)
  4627.             {
  4628.           if (elt->first_same_value
  4629.               != src_related_elt->first_same_value)
  4630.             /* This can occur when we previously saw a CONST 
  4631.                involving a SYMBOL_REF and then see the SYMBOL_REF
  4632.                twice.  Merge the involved classes.  */
  4633.             merge_equiv_classes (elt, src_related_elt);
  4634.  
  4635.               src_related = 0;
  4636.           src_related_elt = 0;
  4637.             }
  4638.               else if (src_related_elt && elt == 0)
  4639.             elt = src_related_elt;
  4640.         }
  4641.         }
  4642.  
  4643.       if (src == src_folded)
  4644.         src_folded = 0;
  4645.  
  4646.       /* At this point, ELT, if non-zero, points to a class of expressions
  4647.          equivalent to the source of this SET and SRC, SRC_EQV, SRC_FOLDED,
  4648.      and SRC_RELATED, if non-zero, each contain additional equivalent
  4649.      expressions.  Prune these latter expressions by deleting expressions
  4650.      already in the equivalence class.
  4651.  
  4652.      Check for an equivalent identical to the destination.  If found,
  4653.      this is the preferred equivalent since it will likely lead to
  4654.      elimination of the insn.  Indicate this by placing it in
  4655.      `src_related'.  */
  4656.  
  4657.       if (elt) elt = elt->first_same_value;
  4658.       for (p = elt; p; p = p->next_same_value)
  4659.         {
  4660.       enum rtx_code code = GET_CODE (p->exp);
  4661.  
  4662.       /* If the expression is not valid, ignore it.  Then we do not
  4663.          have to check for validity below.  In most cases, we can use
  4664.          `rtx_equal_p', since canonicalization has already been done.  */
  4665.       if (code != REG && ! exp_equiv_p (p->exp, p->exp, 1))
  4666.         continue;
  4667.  
  4668.           if (src && GET_CODE (src) == code && rtx_equal_p (src, p->exp))
  4669.         src = 0;
  4670.           else if (src_folded && GET_CODE (src_folded) == code
  4671.            && rtx_equal_p (src_folded, p->exp))
  4672.         src_folded = 0;
  4673.           else if (src_eqv_here && GET_CODE (src_eqv_here) == code
  4674.            && rtx_equal_p (src_eqv_here, p->exp))
  4675.         src_eqv_here = 0;
  4676.           else if (src_related && GET_CODE (src_related) == code
  4677.            && rtx_equal_p (src_related, p->exp))
  4678.         src_related = 0;
  4679.  
  4680.       /* This is the same as the destination of the insns, we want
  4681.          to prefer it.  Copy it to src_related.  The code below will
  4682.          then give it a negative cost.  */
  4683.       if (GET_CODE (dest) == code && rtx_equal_p (p->exp, dest))
  4684.         src_related = dest;
  4685.  
  4686.         }
  4687.  
  4688.       /* Find the cheapest valid equivalent, trying all the available
  4689.          possibilities.  Prefer items not in the hash table to ones
  4690.          that are when they are equal cost.  Note that we can never
  4691.          worsen an insn as the current contents will also succeed.
  4692.      If we find an equivalent identical to the source, use it as best,
  4693.      since this insn will probably be eliminated in that case. */
  4694.       if (src)
  4695.     {
  4696.       if (rtx_equal_p (src, dest))
  4697.         src_cost = -1;
  4698.       else
  4699.         src_cost = COST (src);
  4700.     }
  4701.  
  4702.       if (src_eqv_here)
  4703.     {
  4704.       if (rtx_equal_p (src_eqv_here, dest))
  4705.         src_eqv_cost = -1;
  4706.       else
  4707.         src_eqv_cost = COST (src_eqv_here);
  4708.     }
  4709.  
  4710.       if (src_folded)
  4711.     {
  4712.       if (rtx_equal_p (src_folded, dest))
  4713.         src_folded_cost = -1;
  4714.       else
  4715.         src_folded_cost = COST (src_folded);
  4716.     }
  4717.  
  4718.       if (src_related)
  4719.     {
  4720.       if (rtx_equal_p (src_related, dest))
  4721.         src_related_cost = -1;
  4722.       else
  4723.         src_related_cost = COST (src_related);
  4724.     }
  4725.  
  4726.       /* If this was an indirect jump insn, a known label will really be
  4727.      cheaper even though it looks more expensive.  */
  4728.       if (dest == pc_rtx && src_const && GET_CODE (src_const) == LABEL_REF)
  4729.     src_folded = src_const, src_folded_cost = -1;
  4730.       
  4731.       /* Terminate loop when replacement made.  This must terminate since
  4732.          the current contents will be tested and will always be valid.  */
  4733.       while (1)
  4734.         {
  4735.           rtx trial;
  4736.  
  4737.           /* Skip invalid entries.  */
  4738.           while (elt && GET_CODE (elt->exp) != REG
  4739.              && ! exp_equiv_p (elt->exp, elt->exp, 1))
  4740.         elt = elt->next_same_value;         
  4741.           
  4742.           if (elt) src_elt_cost = elt->cost;
  4743.  
  4744.           /* Find cheapest and skip it for the next time.   For items
  4745.          of equal cost, use this order:
  4746.          src_folded, src, src_eqv, src_related and hash table entry.  */
  4747.           if (src_folded_cost <= src_cost
  4748.           && src_folded_cost <= src_eqv_cost
  4749.           && src_folded_cost <= src_related_cost
  4750.           && src_folded_cost <= src_elt_cost)
  4751.         {
  4752.           trial = src_folded, src_folded_cost = 10000;
  4753.           if (src_folded_force_flag)
  4754.         trial = force_const_mem (mode, trial);
  4755.         }
  4756.           else if (src_cost <= src_eqv_cost
  4757.                && src_cost <= src_related_cost
  4758.                && src_cost <= src_elt_cost)
  4759.         trial = src, src_cost = 10000;
  4760.           else if (src_eqv_cost <= src_related_cost
  4761.                && src_eqv_cost <= src_elt_cost)
  4762.         trial = src_eqv_here, src_eqv_cost = 10000;
  4763.           else if (src_related_cost <= src_elt_cost)
  4764.         trial = src_related, src_related_cost = 10000;
  4765.           else
  4766.         {
  4767.           trial = canon_reg (copy_rtx (elt->exp), 0);
  4768.           elt = elt->next_same_value;
  4769.           src_elt_cost = 10000;
  4770.         }
  4771.  
  4772.       /* We don't normally have an insn matching (set (pc) (pc)), so
  4773.          check for this separately here.  We will delete such an
  4774.          insn below.
  4775.  
  4776.          Tablejump insns contain a USE of the table, so simply replacing
  4777.          the operand with the constant won't match.  This is simply an
  4778.          unconditional branch, however, and is therefore valid.  Just
  4779.          insert the substitution here and we will delete and re-emit
  4780.          the insn later.  */
  4781.  
  4782.       if (n_sets == 1 && dest == pc_rtx
  4783.           && (trial == pc_rtx
  4784.           || (GET_CODE (trial) == LABEL_REF
  4785.               && ! condjump_p (insn))))
  4786.         {
  4787.           /* If TRIAL is a label in front of a jump table, we are
  4788.          really falling through the switch (this is how casesi
  4789.          insns work), so we must branch around the table.  */
  4790.           if (GET_CODE (trial) == CODE_LABEL
  4791.           && NEXT_INSN (trial) != 0
  4792.           && GET_CODE (NEXT_INSN (trial)) == JUMP_INSN
  4793.           && (GET_CODE (PATTERN (NEXT_INSN (trial))) == ADDR_DIFF_VEC
  4794.               || GET_CODE (PATTERN (NEXT_INSN (trial))) == ADDR_VEC))
  4795.  
  4796.         trial = gen_rtx (LABEL_REF, Pmode, get_label_after (trial));
  4797.  
  4798.           SET_SRC (sets[i].rtl) = trial;
  4799.           break;
  4800.         }
  4801.        
  4802.       /* Look for a substitution that makes a valid insn.  */
  4803.           else if (validate_change (insn, &SET_SRC (sets[i].rtl), trial, 0))
  4804.         break;
  4805.  
  4806.       /* If we previously found constant pool entries for 
  4807.          constants and this is a constant, try making a
  4808.          pool entry.  Put it in src_folded unless we already have done
  4809.          this since that is where it likely came from.  */
  4810.  
  4811.       else if (constant_pool_entries_cost
  4812.            && CONSTANT_P (trial)
  4813.            && (src_folded == 0 || GET_CODE (src_folded) != MEM))
  4814.         {
  4815.           src_folded_force_flag = 1;
  4816.           src_folded = trial;
  4817.           src_folded_cost = constant_pool_entries_cost;
  4818.         }
  4819.         }
  4820.  
  4821.       src = SET_SRC (sets[i].rtl);
  4822.  
  4823.       /* In general, it is good to have a SET with SET_SRC == SET_DEST.
  4824.      However, there is an important exception:  If both are registers
  4825.      that are not the head of their equivalence class, replace SET_SRC
  4826.      with the head of the class.  If we do not do this, we will have
  4827.      both registers live over a portion of the basic block.  This way,
  4828.      their lifetimes will likely abut instead of overlapping.  */
  4829.       if (GET_CODE (dest) == REG
  4830.       && REGNO_QTY_VALID_P (REGNO (dest))
  4831.       && qty_first_reg[reg_qty[REGNO (dest)]] != REGNO (dest)
  4832.       && GET_CODE (src) == REG && REGNO (src) == REGNO (dest)
  4833.       /* Don't do this if the original insn had a hard reg as
  4834.          SET_SRC.  */
  4835.       && (GET_CODE (sets[i].src) != REG
  4836.           || REGNO (sets[i].src) >= FIRST_PSEUDO_REGISTER))
  4837.     /* We can't call canon_reg here because it won't do anything if
  4838.        SRC is a hard register.  */
  4839.     src = SET_SRC (sets[i].rtl)
  4840.       = reg_rtx[qty_first_reg[reg_qty[REGNO (src)]]];
  4841.  
  4842.       /* If we made a change, recompute SRC values.  */
  4843.       if (src != sets[i].src)
  4844.         {
  4845.           do_not_record = 0;
  4846.           hash_arg_in_memory = 0;
  4847.           hash_arg_in_struct = 0;
  4848.       sets[i].src = src;
  4849.           sets[i].src_hash_code = HASH (src, mode);
  4850.           sets[i].src_volatile = do_not_record;
  4851.           sets[i].src_in_memory = hash_arg_in_memory;
  4852.           sets[i].src_in_struct = hash_arg_in_struct;
  4853.           sets[i].src_elt = lookup (src, sets[i].src_hash_code, mode);
  4854.         }
  4855.  
  4856.       /* If this is a single SET, we are setting a register, and we have an
  4857.      equivalent constant, we want to add a REG_NOTE. */
  4858.       if (n_sets == 1 && src_const && GET_CODE (dest) == REG)
  4859.     {
  4860.       rtx tem = find_reg_note (insn, REG_EQUAL, 0);
  4861.       
  4862.       /* Record the actual constant value in a REG_EQUAL note, making
  4863.          a new one if one does not already exist.  */
  4864.       if (tem)
  4865.         XEXP (tem, 0) = src_const;
  4866.       else
  4867.         REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_EQUAL,
  4868.                         src_const, REG_NOTES (insn));
  4869.  
  4870.           /* If storing a constant value in a register that
  4871.          previously held the constant value 0,
  4872.          record this fact with a REG_WAS_0 note on this insn.
  4873.  
  4874.          Note that the *register* is required to have previously held 0,
  4875.          not just any register in the quantity and we must point to the
  4876.          insn that set that register to zero.
  4877.  
  4878.          Rather than track each register individually, we just see if
  4879.          the last set for this quantity was for this register.  */
  4880.  
  4881.       if (REGNO_QTY_VALID_P (REGNO (dest))
  4882.           && qty_const[reg_qty[REGNO (dest)]] == const0_rtx)
  4883.         {
  4884.           /* See if we previously had a REG_WAS_0 note.  */
  4885.           rtx note = find_reg_note (insn, REG_WAS_0, 0);
  4886.           rtx const_insn = qty_const_insn[reg_qty[REGNO (dest)]];
  4887.  
  4888.           if ((tem = single_set (const_insn)) != 0
  4889.           && rtx_equal_p (SET_DEST (tem), dest))
  4890.         {
  4891.           if (note)
  4892.             XEXP (note, 0) = const_insn;
  4893.           else
  4894.             REG_NOTES (insn) = gen_rtx (INSN_LIST, REG_WAS_0,
  4895.                         const_insn, REG_NOTES (insn));
  4896.         }
  4897.         }
  4898.     }
  4899.  
  4900.       /* Now deal with the destination.  */
  4901.       do_not_record = 0;
  4902.       sets[i].inner_dest_loc = &SET_DEST (sets[0].rtl);
  4903.  
  4904.       /* Look within any SIGN_EXTRACT or ZERO_EXTRACT
  4905.      to the MEM or REG within it.  */
  4906.       while (GET_CODE (dest) == SIGN_EXTRACT
  4907.          || GET_CODE (dest) == ZERO_EXTRACT
  4908.          || GET_CODE (dest) == SUBREG
  4909.          || GET_CODE (dest) == STRICT_LOW_PART)
  4910.     {
  4911.       sets[i].inner_dest_loc = &XEXP (dest, 0);
  4912.       dest = XEXP (dest, 0);
  4913.     }
  4914.  
  4915.       sets[i].inner_dest = dest;
  4916.  
  4917.       if (GET_CODE (dest) == MEM)
  4918.     {
  4919.       dest = fold_rtx (dest, insn);
  4920.  
  4921.       /* Decide whether we invalidate everything in memory,
  4922.          or just things at non-fixed places.
  4923.          Writing a large aggregate must invalidate everything
  4924.          because we don't know how long it is.  */
  4925.       note_mem_written (dest, &writes_memory);
  4926.     }
  4927.  
  4928.       /* Compute the hash code of the destination now,
  4929.      before the effects of this instruction are recorded,
  4930.      since the register values used in the address computation
  4931.      are those before this instruction.  */
  4932.       sets[i].dest_hash_code = HASH (dest, mode);
  4933.  
  4934.       /* Don't enter a bit-field in the hash table
  4935.      because the value in it after the store
  4936.      may not equal what was stored, due to truncation.  */
  4937.  
  4938.       if (GET_CODE (SET_DEST (sets[i].rtl)) == ZERO_EXTRACT
  4939.       || GET_CODE (SET_DEST (sets[i].rtl)) == SIGN_EXTRACT)
  4940.     {
  4941.       rtx width = XEXP (SET_DEST (sets[i].rtl), 1);
  4942.  
  4943.       if (src_const != 0 && GET_CODE (src_const) == CONST_INT
  4944.           && GET_CODE (width) == CONST_INT
  4945.           && INTVAL (width) < HOST_BITS_PER_INT
  4946.           && ! (INTVAL (src_const) & (-1) << INTVAL (width)))
  4947.         /* Exception: if the value is constant,
  4948.            we can tell whether truncation would change it.  */
  4949.         ;
  4950.       else
  4951.         sets[i].src_volatile = 1, src_eqv = 0;
  4952.     }
  4953.  
  4954.       /* If only one set in a JUMP_INSN and it is now a no-op, we can delete
  4955.      the insn.  */
  4956.       else if (n_sets == 1 && dest == pc_rtx && src == pc_rtx)
  4957.     {
  4958.       PUT_CODE (insn, NOTE);
  4959.       NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
  4960.       NOTE_SOURCE_FILE (insn) = 0;
  4961.       cse_jumps_altered = 1;
  4962.       /* One less use of the label this insn used to jump to.  */
  4963.       --LABEL_NUSES (JUMP_LABEL (insn));
  4964.       /* No more processing for this set.  */
  4965.       sets[i].rtl = 0;
  4966.     }
  4967.  
  4968.       /* If this SET is now setting PC to a label, we know it used to
  4969.      be a conditional or computed branch.  So we see if we can follow
  4970.      it.  If it was a computed branch, delete it and re-emit.  */
  4971.       else if (dest == pc_rtx && GET_CODE (src) == LABEL_REF)
  4972.     {
  4973.       /* If this is not in the format for a simple branch and
  4974.          we are the only SET in it, re-emit it.  */
  4975.       if (! simplejump_p (insn) && n_sets == 1)
  4976.         {
  4977.           rtx new = emit_jump_insn_before (gen_jump (XEXP (src, 0)), insn);
  4978.           JUMP_LABEL (new) = XEXP (src, 0);
  4979.           LABEL_NUSES (XEXP (src, 0))++;
  4980.           delete_insn (insn);
  4981.           insn = new;
  4982.         }
  4983.  
  4984.       emit_barrier_after (insn);
  4985.       cse_jumps_altered = 1;
  4986.  
  4987.       /* Indicate that we may be able to skip to the next basic
  4988.          block.  */
  4989.       cse_skip_to_next_block = 1;
  4990.       sets[i].rtl = 0;
  4991.     }
  4992.  
  4993.       /* No further processing for this assignment if destination
  4994.      is volatile.  */
  4995.  
  4996.       else if (do_not_record)
  4997.     sets[i].rtl = 0;
  4998.  
  4999.       if (sets[i].rtl != 0 && dest != SET_DEST (sets[i].rtl))
  5000.     sets[i].dest_hash_code = HASH (SET_DEST (sets[i].rtl), mode);
  5001.  
  5002. #ifdef HAVE_cc0
  5003.       /* If setting CC0, record what it was set to, or a constant, if it
  5004.      is equivalent to a constant.  If it is being set to a floating-point
  5005.      value, make a COMPARE with the appropriate constant of 0.  If we
  5006.      don't do this, later code can interpret this as a test against
  5007.      const0_rtx, which can cause problems if we try to put it into an
  5008.      insn as a floating-point operand.  */
  5009.       if (dest == cc0_rtx)
  5010.     {
  5011.       this_insn_cc0 = src_const ? src_const : src;
  5012.       if (GET_MODE_CLASS (GET_MODE (this_insn_cc0)) == MODE_FLOAT)
  5013.         this_insn_cc0 = gen_rtx (COMPARE, VOIDmode, this_insn_cc0,
  5014.                      CONST0_RTX (GET_MODE (this_insn_cc0)));
  5015.     }
  5016. #endif
  5017.     }
  5018.  
  5019.   /* Now enter all non-volatile source expressions in the hash table
  5020.      if they are not already present.
  5021.      Record their equivalence classes in src_elt.
  5022.      This way we can insert the corresponding destinations into
  5023.      the same classes even if the actual sources are no longer in them
  5024.      (having been invalidated).  */
  5025.  
  5026.   if (src_eqv && src_eqv_elt == 0 && sets[0].rtl != 0 && ! src_eqv_volatile
  5027.       && ! rtx_equal_p (src_eqv, SET_DEST (sets[0].rtl)))
  5028.     {
  5029.       register struct table_elt *elt;
  5030.       register struct table_elt *classp = sets[0].src_elt;
  5031.       rtx dest = SET_DEST (sets[0].rtl);
  5032.       enum machine_mode eqvmode = GET_MODE (dest);
  5033.  
  5034.       if (GET_CODE (dest) == STRICT_LOW_PART)
  5035.     {
  5036.       eqvmode = GET_MODE (SUBREG_REG (XEXP (dest, 0)));
  5037.       classp = 0;
  5038.     }
  5039.       if (insert_regs (src_eqv, classp, 0))
  5040.     src_eqv_hash_code = HASH (src_eqv, eqvmode);
  5041.       elt = insert (src_eqv, classp, src_eqv_hash_code, eqvmode);
  5042.       elt->in_memory = src_eqv_in_memory;
  5043.       elt->in_struct = src_eqv_in_struct;
  5044.       src_eqv_elt = elt;
  5045.     }
  5046.  
  5047.   for (i = 0; i < n_sets; i++)
  5048.     if (sets[i].rtl && ! sets[i].src_volatile
  5049.     && ! rtx_equal_p (SET_SRC (sets[i].rtl), SET_DEST (sets[i].rtl)))
  5050.       {
  5051.     if (GET_CODE (SET_DEST (sets[i].rtl)) == STRICT_LOW_PART)
  5052.       {
  5053.         /* REG_EQUAL in setting a STRICT_LOW_PART
  5054.            gives an equivalent for the entire destination register,
  5055.            not just for the subreg being stored in now.
  5056.            This is a more interesting equivalence, so we arrange later
  5057.            to treat the entire reg as the destination.  */
  5058.         sets[i].src_elt = src_eqv_elt;
  5059.         sets[i].src_hash_code = src_eqv_hash_code;
  5060.       }
  5061.     else
  5062.       {
  5063.         /* Insert source and constant equivalent into hash table, if not
  5064.            already present.  */
  5065.         register struct table_elt *classp = src_eqv_elt;
  5066.         register rtx src = sets[i].src;
  5067.         register rtx dest = SET_DEST (sets[i].rtl);
  5068.         enum machine_mode mode
  5069.           = GET_MODE (src) == VOIDmode ? GET_MODE (dest) : GET_MODE (src);
  5070.  
  5071.         if (sets[i].src_elt == 0)
  5072.           {
  5073.         register struct table_elt *elt;
  5074.  
  5075.         /* Note that these insert_regs calls cannot remove
  5076.            any of the src_elt's, because they would have failed to
  5077.            match if not still valid.  */
  5078.         if (insert_regs (src, classp, 0))
  5079.           sets[i].src_hash_code = HASH (src, mode);
  5080.         elt = insert (src, classp, sets[i].src_hash_code, mode);
  5081.         elt->in_memory = sets[i].src_in_memory;
  5082.         elt->in_struct = sets[i].src_in_struct;
  5083.         sets[i].src_elt = classp = elt;
  5084.           }
  5085.  
  5086.         if (sets[i].src_const && sets[i].src_const_elt == 0
  5087.         && src != sets[i].src_const
  5088.         && ! rtx_equal_p (sets[i].src_const, src))
  5089.           sets[i].src_elt = insert (sets[i].src_const, classp,
  5090.                     sets[i].src_const_hash_code, mode);
  5091.       }
  5092.       }
  5093.   /* If we did not insert the source into the hash table (e.g., it was
  5094.      volatile), note the equivalence class for the REG_EQUAL value, if any,
  5095.      so that the destination goes into that class.  */
  5096.   else if (sets[i].src_elt == 0)
  5097.     sets[i].src_elt = src_eqv_elt;
  5098.  
  5099.   invalidate_from_clobbers (&writes_memory, x);
  5100.   /* Memory, and some registers, are invalidate by subroutine calls.  */
  5101.   if (GET_CODE (insn) == CALL_INSN)
  5102.     {
  5103.       register int i;
  5104.       static struct write_data everything = {0, 1, 1, 1};
  5105.       invalidate_memory (&everything);
  5106.       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
  5107.     if (call_used_regs[i] && ! fixed_regs[i] && reg_rtx[i]
  5108.         /* Checking fixed_regs here is wrong on Sparc.
  5109.            The frame pointer and argument pointer are always preserved
  5110.            across calls.  The stack pointer usually is, unless
  5111.            RETURN_POPS_ARGS, in which case an explicit CLOBBER
  5112.            will be present.  */
  5113.         && i != STACK_POINTER_REGNUM
  5114.         && i != FRAME_POINTER_REGNUM
  5115.         && i != ARG_POINTER_REGNUM)
  5116.       invalidate (reg_rtx[i]);
  5117.     }
  5118.  
  5119.   /* Now invalidate everything set by this instruction.
  5120.      If a SUBREG or other funny destination is being set,
  5121.      sets[i].rtl is still nonzero, so here we invalidate the reg
  5122.      a part of which is being set.  */
  5123.  
  5124.   for (i = 0; i < n_sets; i++)
  5125.     if (sets[i].rtl)
  5126.       {
  5127.     register rtx dest = sets[i].inner_dest;
  5128.  
  5129.     /* Needed for registers to remove the register from its
  5130.        previous quantity's chain.
  5131.        Needed for memory if this is a nonvarying address, unless
  5132.        we have just done an invalidate_memory that covers even those.  */
  5133.     if (GET_CODE (dest) == REG || GET_CODE (dest) == SUBREG
  5134.         || (! writes_memory.all && ! cse_rtx_addr_varies_p (dest)))
  5135.       invalidate (dest);
  5136.       }
  5137.  
  5138.   /* Make sure registers mentioned in destinations
  5139.      are safe for use in an expression to be inserted.
  5140.      This removes from the hash table
  5141.      any invalid entry that refers to one of these registers.  */
  5142.  
  5143.   for (i = 0; i < n_sets; i++)
  5144.     if (sets[i].rtl && GET_CODE (SET_DEST (sets[i].rtl)) != REG)
  5145.       mention_regs (SET_DEST (sets[i].rtl));
  5146.  
  5147.   /* We may have just removed some of the src_elt's from the hash table.
  5148.      So replace each one with the current head of the same class.  */
  5149.  
  5150.   for (i = 0; i < n_sets; i++)
  5151.     if (sets[i].rtl)
  5152.       {
  5153.     if (sets[i].src_elt && sets[i].src_elt->first_same_value == 0)
  5154.       /* If elt was removed, find current head of same class,
  5155.          or 0 if nothing remains of that class.  */
  5156.       {
  5157.         register struct table_elt *elt = sets[i].src_elt;
  5158.  
  5159.         while (elt && elt->first_same_value == 0)
  5160.           elt = elt->next_same_value;
  5161.         sets[i].src_elt = elt ? elt->first_same_value : 0;
  5162.       }
  5163.       }
  5164.  
  5165.   /* Now insert the destinations into their equivalence classes.  */
  5166.  
  5167.   for (i = 0; i < n_sets; i++)
  5168.     if (sets[i].rtl)
  5169.       {
  5170.     register rtx dest = SET_DEST (sets[i].rtl);
  5171.     register struct table_elt *elt;
  5172.  
  5173.     if (flag_float_store
  5174.         && GET_CODE (dest) == MEM
  5175.         && (GET_MODE (dest) == SFmode || GET_MODE (dest) == DFmode))
  5176.       continue;
  5177.  
  5178.     /* If we didn't put a REG_EQUAL value or a source into the hash
  5179.        table, there is no point is recording DEST.  */
  5180.     if (sets[i].src_elt == 0)
  5181.       continue;
  5182.  
  5183.     /* STRICT_LOW_PART isn't part of the value BEING set,
  5184.        and neither is the SUBREG inside it.
  5185.        Note that in this case SETS[I].SRC_ELT is really SRC_EQV_ELT.  */
  5186.     if (GET_CODE (dest) == STRICT_LOW_PART)
  5187.       dest = SUBREG_REG (XEXP (dest, 0));
  5188.  
  5189.     if (GET_CODE (dest) == REG)
  5190.       /* Registers must also be inserted into chains for quantities.  */
  5191.       if (insert_regs (dest, sets[i].src_elt, 1))
  5192.         /* If `insert_regs' changes something, the hash code must be
  5193.            recalculated.  */
  5194.         sets[i].dest_hash_code = HASHREG (dest);
  5195.  
  5196.     if (GET_CODE (dest) == SUBREG)
  5197.       /* Registers must also be inserted into chains for quantities.  */
  5198.       if (insert_regs (dest, sets[i].src_elt, 1))
  5199.         /* If `insert_regs' changes something, the hash code must be
  5200.            recalculated.  */
  5201.         sets[i].dest_hash_code = HASH (dest, GET_MODE (dest));
  5202.  
  5203.     elt = insert (dest, sets[i].src_elt,
  5204.               sets[i].dest_hash_code, GET_MODE (dest));
  5205.     elt->in_memory = GET_CODE (sets[i].inner_dest) == MEM;
  5206.     if (elt->in_memory)
  5207.       {
  5208.         elt->in_struct = (MEM_IN_STRUCT_P (sets[i].inner_dest)
  5209.                   || sets[i].inner_dest != SET_DEST (sets[i].rtl));
  5210.       }
  5211.  
  5212.     /* If we have (set (subreg:m1 (reg:m2 foo) 0) (bar:m1)), M1 is wider
  5213.        than M2, and both M1 and M2 are a single word, we are also doing
  5214.        (set (reg:m2 foo) (subreg:m2 (bar:m1 0))) so make that equivalence
  5215.        as well.
  5216.  
  5217.        However, BAR may have equivalences for which gen_lowpart_if_possible
  5218.        will produce a simpler value than gen_lowpart_if_possible applied to
  5219.        BAR (e.g., if BAR was ZERO_EXTENDed from M2), so we will scan all
  5220.        BAR's equivalences.
  5221.  
  5222.        Note the loop below will find SUBREG_REG (DEST) since we have
  5223.        already entered SRC and DEST of the SET in the table.  */
  5224.     if (GET_CODE (dest) == SUBREG
  5225.         && GET_MODE_SIZE (GET_MODE (dest)) <= UNITS_PER_WORD
  5226.         && GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))) <= UNITS_PER_WORD
  5227.         && (GET_MODE_SIZE (GET_MODE (dest))
  5228.         >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))))
  5229.         && sets[i].src_elt != 0)
  5230.       {
  5231.         enum machine_mode new_mode = GET_MODE (SUBREG_REG (dest));
  5232.         struct table_elt *elt, *classp = 0;
  5233.  
  5234.         for (elt = sets[i].src_elt->first_same_value; elt;
  5235.          elt = elt->next_same_value)
  5236.           {
  5237.         rtx new_src = 0;
  5238.         int src_hash;
  5239.         struct table_elt *src_elt;
  5240.  
  5241.         new_src = gen_lowpart_if_possible (new_mode, elt->exp);
  5242.         if (new_src == 0)
  5243.           continue;
  5244.  
  5245.         src_hash = HASH (new_src, new_mode);
  5246.         src_elt = lookup (new_src, src_hash, new_mode);
  5247.  
  5248.         /* Put the new source in the hash table is if isn't
  5249.            already.  */
  5250.         if (src_elt == 0)
  5251.           {
  5252.             if (insert_regs (new_src, classp, 1))
  5253.               src_hash = HASH (new_src, new_mode);
  5254.             src_elt = insert (new_src, classp, src_hash, new_mode);
  5255.             src_elt->in_memory = elt->in_memory;
  5256.             src_elt->in_struct = elt->in_struct;
  5257.           }
  5258.         else if (classp && classp != src_elt->first_same_value)
  5259.           /* Show that two things that we've seen before are 
  5260.              actually the same.  */
  5261.           merge_equiv_classes (src_elt, classp);
  5262.  
  5263.         classp = src_elt->first_same_value;
  5264.           }
  5265.       }
  5266.       }
  5267.  
  5268.   /* Special handling for (set REG0 REG1)
  5269.      where REG0 is the "cheapest", cheaper than REG1.
  5270.      After cse, REG1 will probably not be used in the sequel, 
  5271.      so (if easily done) change this insn to (set REG1 REG0) and
  5272.      replace REG1 with REG0 in the previous insn that computed their value.
  5273.      Then REG1 will become a dead store and won't cloud the situation
  5274.      for later optimizations.
  5275.  
  5276.      Do not make this change if REG1 is a hard register, because it will
  5277.      then be used in the sequel and we may be changing a two-operand insn
  5278.      into a three-operand insn.
  5279.  
  5280.      Also do not do this if we are operating on a copy of INSN.  */
  5281.  
  5282.   if (n_sets == 1 && sets[0].rtl && GET_CODE (SET_DEST (sets[0].rtl)) == REG
  5283.       && NEXT_INSN (PREV_INSN (insn)) == insn
  5284.       && GET_CODE (SET_SRC (sets[0].rtl)) == REG
  5285.       && REGNO (SET_SRC (sets[0].rtl)) >= FIRST_PSEUDO_REGISTER
  5286.       && REGNO_QTY_VALID_P (REGNO (SET_SRC (sets[0].rtl)))
  5287.       && (qty_first_reg[reg_qty[REGNO (SET_SRC (sets[0].rtl))]]
  5288.       == REGNO (SET_DEST (sets[0].rtl))))
  5289.     {
  5290.       rtx prev = PREV_INSN (insn);
  5291.       while (prev && GET_CODE (prev) == NOTE)
  5292.     prev = PREV_INSN (prev);
  5293.  
  5294.       if (prev && GET_CODE (prev) == INSN && GET_CODE (PATTERN (prev)) == SET
  5295.       && SET_DEST (PATTERN (prev)) == SET_SRC (sets[0].rtl))
  5296.     {
  5297.       rtx dest = SET_DEST (sets[0].rtl);
  5298.       rtx note = find_reg_note (prev, REG_EQUIV, 0);
  5299.  
  5300.       validate_change (prev, & SET_DEST (PATTERN (prev)), dest, 1);
  5301.       validate_change (insn, & SET_DEST (sets[0].rtl),
  5302.                SET_SRC (sets[0].rtl), 1);
  5303.       validate_change (insn, & SET_SRC (sets[0].rtl), dest, 1);
  5304.       apply_change_group ();
  5305.  
  5306.       /* If REG1 was equivalent to a constant, REG0 is not.  */
  5307.       if (note)
  5308.         PUT_REG_NOTE_KIND (note, REG_EQUAL);
  5309.  
  5310.       /* If there was a REG_WAS_0 note on PREV, remove it.  Move
  5311.          any REG_WAS_0 note on INSN to PREV.  */
  5312.       note = find_reg_note (prev, REG_WAS_0, 0);
  5313.       if (note)
  5314.         remove_note (prev, note);
  5315.  
  5316.       note = find_reg_note (insn, REG_WAS_0, 0);
  5317.       if (note)
  5318.         {
  5319.           remove_note (insn, note);
  5320.           XEXP (note, 1) = REG_NOTES (prev);
  5321.           REG_NOTES (prev) = note;
  5322.         }
  5323.     }
  5324.     }
  5325.  
  5326.   /* If this is a conditional jump insn, record any known equivalences due to
  5327.      the condition being tested.  */
  5328.  
  5329.   last_jump_equiv_class = 0;
  5330.   if (GET_CODE (insn) == JUMP_INSN
  5331.       && n_sets == 1 && GET_CODE (x) == SET
  5332.       && GET_CODE (SET_SRC (x)) == IF_THEN_ELSE)
  5333.     record_jump_equiv (insn, 0);
  5334.  
  5335. #ifdef HAVE_cc0
  5336.   /* If the previous insn set CC0 and this insn no longer references CC0,
  5337.      delete the previous insn.  Here we use the fact that nothing expects CC0
  5338.      to be valid over an insn, which is true until the final pass.  */
  5339.   if (prev_insn && GET_CODE (prev_insn) == INSN
  5340.       && (tem = single_set (prev_insn)) != 0
  5341.       && SET_DEST (tem) == cc0_rtx
  5342.       && ! reg_mentioned_p (cc0_rtx, x))
  5343.     {
  5344.       PUT_CODE (prev_insn, NOTE);
  5345.       NOTE_LINE_NUMBER (prev_insn) = NOTE_INSN_DELETED;
  5346.       NOTE_SOURCE_FILE (prev_insn) = 0;
  5347.     }
  5348.  
  5349.   prev_insn_cc0 = this_insn_cc0;
  5350. #endif
  5351.  
  5352.   prev_insn = insn;
  5353. }
  5354.  
  5355. /* Store 1 in *WRITES_PTR for those categories of memory ref
  5356.    that must be invalidated when the expression WRITTEN is stored in.
  5357.    If WRITTEN is null, say everything must be invalidated.  */
  5358.  
  5359. static void
  5360. note_mem_written (written, writes_ptr)
  5361.      rtx written;
  5362.      struct write_data *writes_ptr;
  5363. {
  5364.   static struct write_data everything = {0, 1, 1, 1};
  5365.  
  5366.   if (written == 0)
  5367.     *writes_ptr = everything;
  5368.   else if (GET_CODE (written) == MEM)
  5369.     {
  5370.       /* Pushing or popping the stack invalidates just the stack pointer. */
  5371.       rtx addr = XEXP (written, 0);
  5372.       if ((GET_CODE (addr) == PRE_DEC || GET_CODE (addr) == PRE_INC
  5373.        || GET_CODE (addr) == POST_DEC || GET_CODE (addr) == POST_INC)
  5374.       && GET_CODE (XEXP (addr, 0)) == REG
  5375.       && REGNO (XEXP (addr, 0)) == STACK_POINTER_REGNUM)
  5376.     {
  5377.       writes_ptr->sp = 1;
  5378.       return;
  5379.     }
  5380.       else if (GET_MODE (written) == BLKmode)
  5381.     *writes_ptr = everything;
  5382.       else if (cse_rtx_addr_varies_p (written))
  5383.     {
  5384.       /* A varying address that is a sum indicates an array element,
  5385.          and that's just as good as a structure element
  5386.          in implying that we need not invalidate scalar variables.  */
  5387.       if (!(MEM_IN_STRUCT_P (written)
  5388.         || GET_CODE (XEXP (written, 0)) == PLUS))
  5389.         writes_ptr->all = 1;
  5390.       writes_ptr->nonscalar = 1;
  5391.     }
  5392.       writes_ptr->var = 1;
  5393.     }
  5394. }
  5395.  
  5396. /* Perform invalidation on the basis of everything about an insn
  5397.    except for invalidating the actual places that are SET in it.
  5398.    This includes the places CLOBBERed, and anything that might
  5399.    alias with something that is SET or CLOBBERed.
  5400.  
  5401.    W points to the writes_memory for this insn, a struct write_data
  5402.    saying which kinds of memory references must be invalidated.
  5403.    X is the pattern of the insn.  */
  5404.  
  5405. static void
  5406. invalidate_from_clobbers (w, x)
  5407.      struct write_data *w;
  5408.      rtx x;
  5409. {
  5410.   /* If W->var is not set, W specifies no action.
  5411.      If W->all is set, this step gets all memory refs
  5412.      so they can be ignored in the rest of this function.  */
  5413.   if (w->var)
  5414.     invalidate_memory (w);
  5415.  
  5416.   if (w->sp && reg_rtx[STACK_POINTER_REGNUM])
  5417.     invalidate (reg_rtx[STACK_POINTER_REGNUM]);
  5418.  
  5419.   if (GET_CODE (x) == CLOBBER)
  5420.     {
  5421.       rtx ref = XEXP (x, 0);
  5422.       if (ref
  5423.       && (GET_CODE (ref) == REG || GET_CODE (ref) == SUBREG
  5424.           || (GET_CODE (ref) == MEM && ! w->all)))
  5425.     invalidate (ref);
  5426.     }
  5427.   else if (GET_CODE (x) == PARALLEL)
  5428.     {
  5429.       register int i;
  5430.       for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
  5431.     {
  5432.       register rtx y = XVECEXP (x, 0, i);
  5433.       if (GET_CODE (y) == CLOBBER)
  5434.         {
  5435.           rtx ref = XEXP (y, 0);
  5436.           if (ref
  5437.           &&(GET_CODE (ref) == REG || GET_CODE (ref) == SUBREG
  5438.              || (GET_CODE (ref) == MEM && !w->all)))
  5439.         invalidate (ref);
  5440.         }
  5441.     }
  5442.     }
  5443. }
  5444.  
  5445. /* Find common subexpressions between the end test of a loop the and beginning
  5446.    of the loop.  LOOP_START is the CODE_LABEL at the start of a loop.
  5447.  
  5448.    Often we have a loop where an expression in the exit test is used
  5449.    in the body of the loop.  For example "while (*p) *q++ = *p++;".
  5450.    Because of the way we duplicate the loop exit test in front of the loop,
  5451.    however, we don't detect that common subexpression.  This will be caught
  5452.    when global cse is implemented, but this is a quite common case.
  5453.  
  5454.    This function handles the most common cases of these common expressions.
  5455.    It is called after we have processed the basic block ending with the
  5456.    NOTE_INSN_LOOP_END note that ends a loop and the previous JUMP_INSN
  5457.    jumps to a label used only once.  */
  5458.  
  5459. static void
  5460. cse_around_loop (loop_start)
  5461.      rtx loop_start;
  5462. {
  5463.   rtx insn;
  5464.   int i;
  5465.   struct table_elt *p;
  5466.  
  5467.   /* If the jump at the end of the loop doesn't go to the start, we don't
  5468.      do anything.  */
  5469.   for (insn = PREV_INSN (loop_start);
  5470.        insn && (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) >= 0);
  5471.        insn = PREV_INSN (insn))
  5472.     ;
  5473.  
  5474.   if (insn == 0
  5475.       || GET_CODE (insn) != NOTE
  5476.       || NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG)
  5477.     return;
  5478.  
  5479.   /* If the last insn of the loop (the end test) was an NE comparison,
  5480.      we will interpret it as an EQ comparison, since we fell through
  5481.      the loop.  Any equivalances resulting from that comparison are
  5482.      therefore not valid and must be invalidated.  */
  5483.   if (last_jump_equiv_class)
  5484.     for (p = last_jump_equiv_class->first_same_value; p;
  5485.      p = p->next_same_value)
  5486.       if (GET_CODE (p->exp) == MEM || GET_CODE (p->exp) == REG
  5487.       || GET_CODE (p->exp) == SUBREG)
  5488.     invalidate (p->exp);
  5489.  
  5490.   /* Process insns starting after LOOP_START until we hit a CALL_INSN or
  5491.      a CODE_LABEL (we could handle a CALL_INSN, but it isn't worth it).
  5492.  
  5493.      The only thing we do with SET_DEST is invalidate entries, so we
  5494.      can safely process each SET in order.  It is slightly less efficient
  5495.      to do so, but we only want to handle the most common cases.  */
  5496.  
  5497.   for (insn = NEXT_INSN (loop_start);
  5498.        GET_CODE (insn) != CALL_INSN && GET_CODE (insn) != CODE_LABEL
  5499.        && ! (GET_CODE (insn) == NOTE
  5500.          && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END);
  5501.        insn = NEXT_INSN (insn))
  5502.     {
  5503.       if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
  5504.       && (GET_CODE (PATTERN (insn)) == SET
  5505.           || GET_CODE (PATTERN (insn)) == CLOBBER))
  5506.     cse_set_around_loop (PATTERN (insn), insn, loop_start);
  5507.       else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
  5508.            && GET_CODE (PATTERN (insn)) == PARALLEL)
  5509.     for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
  5510.       if (GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == SET
  5511.           || GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == CLOBBER)
  5512.         cse_set_around_loop (XVECEXP (PATTERN (insn), 0, i), insn,
  5513.                  loop_start);
  5514.     }
  5515. }
  5516.  
  5517. /* Used for communication between the following two routines; contains a
  5518.    value to be checked for modification.  */
  5519.  
  5520. static rtx cse_check_loop_start_value;
  5521.  
  5522. /* If modifying X will modify the value in CSE_CHECK_LOOP_START_VALUE,
  5523.    indicate that fact by setting CSE_CHECK_LOOP_START_VALUE to 0.  */
  5524.  
  5525. static void
  5526. cse_check_loop_start (x, set)
  5527.      rtx x;
  5528.      rtx set;
  5529. {
  5530.   if (cse_check_loop_start_value == 0
  5531.       || GET_CODE (x) == CC0 || GET_CODE (x) == PC)
  5532.     return;
  5533.  
  5534.   if ((GET_CODE (x) == MEM && GET_CODE (cse_check_loop_start_value) == MEM)
  5535.       || reg_overlap_mentioned_p (x, cse_check_loop_start_value))
  5536.     cse_check_loop_start_value = 0;
  5537. }
  5538.  
  5539. /* X is a SET or CLOBBER contained in INSN that was found near the start of
  5540.    a loop that starts with the label at LOOP_START.
  5541.  
  5542.    If X is a SET, we see if its SET_SRC is currently in our hash table.
  5543.    If so, we see if it has a value equal to some register used only in the
  5544.    loop exit code (as marked by jump.c).
  5545.  
  5546.    If those two conditions are true, we search backwards from the start of
  5547.    the loop to see if that same value was loaded into a register that still
  5548.    retains its value at the start of the loop.
  5549.  
  5550.    If so, we insert an insn after the load to copy the destination of that
  5551.    load into the equivalent register and (try to) replace our SET_SRC with that
  5552.    register.
  5553.  
  5554.    In any event, we invalidate whatever this SET or CLOBBER modifies.  */
  5555.  
  5556. static void
  5557. cse_set_around_loop (x, insn, loop_start)
  5558.      rtx x;
  5559.      rtx insn;
  5560.      rtx loop_start;
  5561. {
  5562.   rtx p;
  5563.   struct table_elt *src_elt;
  5564.   static struct write_data init = {0, 0, 0, 0};
  5565.   struct write_data writes_memory;
  5566.  
  5567.   writes_memory = init;
  5568.  
  5569.   /* If this is a SET, see if we can replace SET_SRC, but ignore SETs that
  5570.      are setting PC or CC0 or whose SET_SRC is already a register.  */
  5571.   if (GET_CODE (x) == SET
  5572.       && GET_CODE (SET_DEST (x)) != PC && GET_CODE (SET_DEST (x)) != CC0
  5573.       && GET_CODE (SET_SRC (x)) != REG)
  5574.     {
  5575.       src_elt = lookup (SET_SRC (x),
  5576.             HASH (SET_SRC (x), GET_MODE (SET_DEST (x))),
  5577.             GET_MODE (SET_DEST (x)));
  5578.  
  5579.       if (src_elt)
  5580.     for (src_elt = src_elt->first_same_value; src_elt;
  5581.          src_elt = src_elt->next_same_value)
  5582.       if (GET_CODE (src_elt->exp) == REG && REG_LOOP_TEST_P (src_elt->exp)
  5583.           && COST (src_elt->exp) < COST (SET_SRC (x)))
  5584.         {
  5585.           rtx p, set;
  5586.  
  5587.           /* Look for an insn in front of LOOP_START that sets
  5588.          something in the desired mode to SET_SRC (x) before we hit
  5589.          a label or CALL_INSN.  */
  5590.  
  5591.           for (p = prev_nonnote_insn (loop_start);
  5592.            p && GET_CODE (p) != CALL_INSN
  5593.            && GET_CODE (p) != CODE_LABEL;
  5594.            p = prev_nonnote_insn  (p))
  5595.         if ((set = single_set (p)) != 0
  5596.             && GET_CODE (SET_DEST (set)) == REG
  5597.             && GET_MODE (SET_DEST (set)) == src_elt->mode
  5598.             && rtx_equal_p (SET_SRC (set), SET_SRC (x)))
  5599.           {
  5600.             /* We now have to ensure that nothing between P
  5601.                and LOOP_START modified anything referenced in
  5602.                SET_SRC (x).  We know that nothing within the loop
  5603.                can modify it, or we would have invalidated it in
  5604.                the hash table.  */
  5605.             rtx q;
  5606.  
  5607.             cse_check_loop_start_value = SET_SRC (x);
  5608.             for (q = p; q != loop_start; q = NEXT_INSN (q))
  5609.               if (GET_RTX_CLASS (GET_CODE (q)) == 'i')
  5610.             note_stores (PATTERN (q), cse_check_loop_start);
  5611.  
  5612.             /* If nothing was changed and we can replace our
  5613.                SET_SRC, add an insn after P to copy its destination
  5614.                to what we will be replacing SET_SRC with.  */
  5615.             if (cse_check_loop_start_value
  5616.             && validate_change (insn, &SET_SRC (x),
  5617.                         src_elt->exp, 0))
  5618.               emit_insn_after (gen_move_insn (src_elt->exp,
  5619.                               SET_DEST (set)),
  5620.                        p);
  5621.             break;
  5622.           }
  5623.         }
  5624.     }
  5625.  
  5626.   /* Now invalidate anything modified by X.  */
  5627.   note_mem_written (SET_DEST (x), &writes_memory);
  5628.  
  5629.   if (writes_memory.var)
  5630.     invalidate_memory (&writes_memory);
  5631.  
  5632.   /* See comment on similar code in cse_insn for explanation of these tests. */
  5633.   if (GET_CODE (SET_DEST (x)) == REG || GET_CODE (SET_DEST (x)) == SUBREG
  5634.       || (GET_CODE (SET_DEST (x)) == MEM && ! writes_memory.all
  5635.       && ! cse_rtx_addr_varies_p (SET_DEST (x))))
  5636.     invalidate (SET_DEST (x));
  5637. }
  5638.  
  5639. /* Find the end of INSN's basic block and return its range,
  5640.    the total number of SETs in all the insns of the block, the last insn of the
  5641.    block, and the branch path.
  5642.  
  5643.    The branch path indicates which branches should be followed.  If a non-zero
  5644.    path size is specified, the block should be rescanned and a different set
  5645.    of branches will be taken.  The branch path is only used if
  5646.    FLAG_CSE_FOLLOW_JUMPS is non-zero.
  5647.  
  5648.    DATA is a pointer to a struct cse_basic_block_data, defined below, that is
  5649.    used to describe the block.  It is filled in with the information about
  5650.    the current block.  The incoming structure's branch path, if any, is used
  5651.    to construct the output branch path.  */
  5652.  
  5653. /* Define maximum length of a branch path.  */
  5654.  
  5655. #define PATHLENGTH    20
  5656.  
  5657. struct cse_basic_block_data {
  5658.   /* Lowest CUID value of insns in block.  */
  5659.   int low_cuid;
  5660.   /* Highest CUID value of insns in block.  */
  5661.   int high_cuid;
  5662.   /* Total number of SETs in block.  */
  5663.   int nsets;
  5664.   /* Last insn in the block.  */
  5665.   rtx last;
  5666.   /* Size of current branch path, if any.  */
  5667.   int path_size;
  5668.   /* Current branch path, indicating which branches will be taken.  */
  5669.   struct branch_path {
  5670.     /* The branch insn. */
  5671.     rtx branch;
  5672.     /* Whether it should be taken or not.  */
  5673.     enum taken {TAKEN, NOT_TAKEN} status;
  5674.   } path[PATHLENGTH];
  5675. };
  5676.  
  5677. void
  5678. cse_end_of_basic_block (insn, data, follow_jumps, after_loop)
  5679.      rtx insn;
  5680.      struct cse_basic_block_data *data;
  5681.      int follow_jumps;
  5682.      int after_loop;
  5683. {
  5684.   rtx p = insn, q;
  5685.   int nsets = 0;
  5686.   int low_cuid = INSN_CUID (insn), high_cuid = INSN_CUID (insn);
  5687.   int path_size = data->path_size;
  5688.   int path_entry = 0;
  5689.   int i;
  5690.  
  5691.   /* Update the previous branch path, if any.  If the last branch was
  5692.      previously TAKEN, mark it NOT_TAKEN.  If it was previously NOT_TAKEN,
  5693.      shorten the path by one and look at the previous branch.  We know that
  5694.      at least one branch must have been taken if PATH_SIZE is non-zero.  */
  5695.   while (path_size > 0)
  5696.     {
  5697.       if (data->path[path_size - 1].status == TAKEN)
  5698.     {
  5699.       data->path[path_size - 1].status = NOT_TAKEN;
  5700.       break;
  5701.     }
  5702.       else
  5703.     path_size--;
  5704.     }
  5705.  
  5706.   /* Scan to end of this basic block.  */
  5707.   while (p && GET_CODE (p) != CODE_LABEL)
  5708.     {
  5709.       /* Don't cse out the end of a loop.  This makes a difference
  5710.      only for the unusual loops that always execute at least once;
  5711.      all other loops have labels there so we will stop in any case.
  5712.      Cse'ing out the end of the loop is dangerous because it
  5713.      might cause an invariant expression inside the loop
  5714.      to be reused after the end of the loop.  This would make it
  5715.      hard to move the expression out of the loop in loop.c,
  5716.      especially if it is one of several equivalent expressions
  5717.      and loop.c would like to eliminate it.
  5718.  
  5719.      If we are running after loop.c has finished, we can ignore
  5720.      the NOTE_INSN_LOOP_END.  */
  5721.  
  5722.       if (! after_loop && GET_CODE (p) == NOTE
  5723.       && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
  5724.     break;
  5725.  
  5726.       /* Don't cse over a call to setjmp; on some machines (eg vax)
  5727.      the regs restored by the longjmp come from
  5728.      a later time than the setjmp.  */
  5729.       if (GET_CODE (p) == NOTE
  5730.       && NOTE_LINE_NUMBER (p) == NOTE_INSN_SETJMP)
  5731.     break;
  5732.  
  5733.       /* A PARALLEL can have lots of SETs in it,
  5734.      especially if it is really an ASM_OPERANDS.  */
  5735.       if (GET_RTX_CLASS (GET_CODE (p)) == 'i'
  5736.       && GET_CODE (PATTERN (p)) == PARALLEL)
  5737.     nsets += XVECLEN (PATTERN (p), 0);
  5738.       else if (GET_CODE (p) != NOTE)
  5739.     nsets += 1;
  5740.     
  5741.       if (INSN_CUID (p) > high_cuid)
  5742.         high_cuid = INSN_CUID (p);
  5743.       if (INSN_CUID (p) < low_cuid)
  5744.         low_cuid = INSN_CUID(p);
  5745.  
  5746.       /* See if this insn is in our branch path.  If it is and we are to
  5747.      take it, do so.  */
  5748.       if (path_entry < path_size && data->path[path_entry].branch == p)
  5749.     {
  5750.       if (data->path[path_entry].status == TAKEN)
  5751.         p = JUMP_LABEL (p);
  5752.       
  5753.       /* Point to next entry in path, if any.  */
  5754.       path_entry++;
  5755.     }
  5756.  
  5757.       /* If this is a conditional jump, we can follow it if -fcse-follow-jumps
  5758.      was specified, we haven't reached our maximum path length, there are
  5759.      insns following the target of the jump, this is the only use of the
  5760.      jump label, and the target label is preceeded by a BARRIER.  */
  5761.       else if (follow_jumps && path_size < PATHLENGTH - 1
  5762.            && GET_CODE (p) == JUMP_INSN
  5763.                  && GET_CODE (PATTERN (p)) == SET
  5764.            && GET_CODE (SET_SRC (PATTERN (p))) == IF_THEN_ELSE
  5765.            && LABEL_NUSES (JUMP_LABEL (p)) == 1
  5766.            && NEXT_INSN (JUMP_LABEL (p)) != 0)
  5767.     {
  5768.       for (q = PREV_INSN (JUMP_LABEL (p)); q; q = PREV_INSN (q))
  5769.         if ((GET_CODE (q) != NOTE
  5770.              || NOTE_LINE_NUMBER (q) == NOTE_INSN_LOOP_END
  5771.              || NOTE_LINE_NUMBER (q) == NOTE_INSN_SETJMP)
  5772.             && (GET_CODE (q) != CODE_LABEL || LABEL_NUSES (q) != 0))
  5773.           break;
  5774.  
  5775.       /* If we ran into a BARRIER, this code is an extension of the
  5776.          basic block when the branch is taken.  */
  5777.       if (q != 0 && GET_CODE (q) == BARRIER)
  5778.         {
  5779.           /* Don't allow ourself to keep walking around an
  5780.          always-executed loop.  */
  5781.           if (next_real_insn (q) == next_real_insn (insn))
  5782.         break;
  5783.  
  5784.           /* Similarly, don't put a branch in our path more than once.  */
  5785.           for (i = 0; i < path_entry; i++)
  5786.         if (data->path[i].branch == p)
  5787.           break;
  5788.  
  5789.           if (i != path_entry)
  5790.         break;
  5791.  
  5792.           data->path[path_entry].branch = p;
  5793.           data->path[path_entry++].status = TAKEN;
  5794.  
  5795.           /* This branch now ends our path.  It was possible that we
  5796.          didn't see this branch the last time around (when the
  5797.          insn in front of the target was a JUMP_INSN that was
  5798.          turned into a no-op).  */
  5799.           path_size = path_entry;
  5800.  
  5801.           p = JUMP_LABEL (p);
  5802.           /* Mark block so we won't scan it again later.  */
  5803.           PUT_MODE (NEXT_INSN (p), QImode);
  5804.         }
  5805.     }
  5806.     
  5807.       p = NEXT_INSN (p);
  5808.     }
  5809.  
  5810.   data->low_cuid = low_cuid;
  5811.   data->high_cuid = high_cuid;
  5812.   data->nsets = nsets;
  5813.   data->last = p;
  5814.  
  5815.   /* If all jumps in the path are not taken, set our path length to zero
  5816.      so a rescan won't be done.  */
  5817.   for (i = path_size - 1; i >= 0; i--)
  5818.     if (data->path[i].status == TAKEN)
  5819.       break;
  5820.  
  5821.   if (i == -1)
  5822.     data->path_size = 0;
  5823.   else
  5824.     data->path_size = path_size;
  5825.  
  5826.   /* End the current branch path.  */
  5827.   data->path[path_size].branch = 0;
  5828. }
  5829.  
  5830. static rtx cse_basic_block ();
  5831.  
  5832. /* Perform cse on the instructions of a function.
  5833.    F is the first instruction.
  5834.    NREGS is one plus the highest pseudo-reg number used in the instruction.
  5835.  
  5836.    AFTER_LOOP is 1 if this is the cse call done after loop optimization
  5837.    (only if -frerun-cse-after-loop).
  5838.  
  5839.    Returns 1 if jump_optimize should be redone due to simplifications
  5840.    in conditional jump instructions.  */
  5841.  
  5842. int
  5843. cse_main (f, nregs, after_loop, file)
  5844.      rtx f;
  5845.      int nregs;
  5846.      int after_loop;
  5847.      FILE *file;
  5848. {
  5849.   struct cse_basic_block_data val;
  5850.   register rtx insn = f;
  5851.   register int i;
  5852.  
  5853.   cse_jumps_altered = 0;
  5854.   constant_pool_entries_cost = 0;
  5855.   val.path_size = 0;
  5856.  
  5857.   init_recog ();
  5858.  
  5859.   max_reg = nregs;
  5860.  
  5861.   all_minus_one = (int *) alloca (nregs * sizeof (int));
  5862.   consec_ints = (int *) alloca (nregs * sizeof (int));
  5863.  
  5864.   for (i = 0; i < nregs; i++)
  5865.     {
  5866.       all_minus_one[i] = -1;
  5867.       consec_ints[i] = i;
  5868.     }
  5869.  
  5870.   reg_next_eqv = (int *) alloca (nregs * sizeof (int));
  5871.   reg_prev_eqv = (int *) alloca (nregs * sizeof (int));
  5872.   reg_qty = (int *) alloca (nregs * sizeof (int));
  5873.   reg_rtx = (rtx *) alloca (nregs * sizeof (rtx));
  5874.   reg_in_table = (int *) alloca (nregs * sizeof (int));
  5875.   reg_tick = (int *) alloca (nregs * sizeof (int));
  5876.  
  5877.   /* Initialize reg_rtx onc here.  It does not have to be
  5878.      reinitialized for later basic blocks.  */
  5879.   bzero (reg_rtx, max_reg * sizeof (rtx));
  5880.  
  5881.   /* Discard all the free elements of the previous function
  5882.      since they are allocated in the temporarily obstack.  */
  5883.   bzero (table, sizeof table);
  5884.   free_element_chain = 0;
  5885.   n_elements_made = 0;
  5886.  
  5887.   /* Find the largest uid.  */
  5888.  
  5889.   for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
  5890.     if (INSN_UID (insn) > i)
  5891.       i = INSN_UID (insn);
  5892.  
  5893.   uid_cuid = (short *) alloca ((i + 1) * sizeof (short));
  5894.   bzero (uid_cuid, (i + 1) * sizeof (short));
  5895.  
  5896.   /* Compute the mapping from uids to cuids.
  5897.      CUIDs are numbers assigned to insns, like uids,
  5898.      except that cuids increase monotonically through the code.
  5899.      Don't assign cuids to line-number NOTEs, so that the distance in cuids
  5900.      between two insns is not affected by -g.  */
  5901.  
  5902.   for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
  5903.     {
  5904.       if (GET_CODE (insn) != NOTE
  5905.       || NOTE_LINE_NUMBER (insn) < 0)
  5906.     INSN_CUID (insn) = ++i;
  5907.       else
  5908.     /* Give a line number note the same cuid as preceding insn.  */
  5909.     INSN_CUID (insn) = i;
  5910.     }
  5911.  
  5912.   /* Loop over basic blocks.
  5913.      Compute the maximum number of qty's needed for each basic block
  5914.      (which is 2 for each SET).  */
  5915.   insn = f;
  5916.   while (insn)
  5917.     {
  5918.       int tem;
  5919.  
  5920.       cse_end_of_basic_block (insn, &val, flag_cse_follow_jumps, after_loop);
  5921.  
  5922.       /* If this basic block was already processed or has no sets, skip it.  */
  5923.       if (val.nsets == 0 || GET_MODE (insn) == QImode)
  5924.     {
  5925.       PUT_MODE (insn, VOIDmode);
  5926.       insn = (val.last ? NEXT_INSN (val.last) : 0);
  5927.       val.path_size = 0;
  5928.       continue;
  5929.     }
  5930.  
  5931.       cse_basic_block_start = val.low_cuid;
  5932.       cse_basic_block_end = val.high_cuid;
  5933.       max_qty = val.nsets * 2;
  5934.       
  5935.       if (file)
  5936.     fprintf (file, ";; Processing block from %d to %d, %d sets.\n",
  5937.          INSN_UID (insn), val.last ? INSN_UID (val.last) : 0,
  5938.          val.nsets);
  5939.  
  5940.       /* Make MAX_QTY bigger to give us room to optimize
  5941.      past the end of this basic block, if that should prove useful.  */
  5942.       if (max_qty < 500)
  5943.     max_qty = 500;
  5944.  
  5945.       max_qty += max_reg;
  5946.  
  5947.       /* If this basic block is being extended by following certain jumps,
  5948.          (see `cse_end_of_basic_block'), we reprocess the code from the start.
  5949.          Otherwise, we start after this basic block.  */
  5950.       if (val.path_size > 0)
  5951.         cse_basic_block (insn, val.last, val.path);
  5952.       else
  5953.     {
  5954.       int old_cse_jumps_altered = cse_jumps_altered;
  5955.       rtx temp;
  5956.  
  5957.       /* When cse changes a conditional jump to an unconditional
  5958.          jump, we want to reprocess the block, since it will give
  5959.          us a new branch path to investigate.  */
  5960.       cse_jumps_altered = 0;
  5961.       temp = cse_basic_block (insn, val.last, val.path);
  5962.       if (cse_jumps_altered == 0 || flag_cse_follow_jumps == 0)
  5963.         {
  5964.           insn = temp;
  5965.  
  5966.           /* If we are running before loop.c, we stopped on a
  5967.          NOTE_INSN_LOOP_END, and the previous insn is the only insn
  5968.          that branches to the head of a loop, we can cse into the
  5969.          loop.  */
  5970.           if (! after_loop && val.last != 0
  5971.           && GET_CODE (val.last) == NOTE
  5972.           && NOTE_LINE_NUMBER (val.last) == NOTE_INSN_LOOP_END
  5973.           && GET_CODE (PREV_INSN (val.last)) == JUMP_INSN
  5974.           && JUMP_LABEL (PREV_INSN (val.last)) != 0
  5975.           && LABEL_NUSES (JUMP_LABEL (PREV_INSN (val.last))) == 1)
  5976.         cse_around_loop (JUMP_LABEL (PREV_INSN (val.last)));
  5977.         }
  5978.  
  5979.       cse_jumps_altered |= old_cse_jumps_altered;
  5980.     }
  5981.  
  5982. #ifdef USE_C_ALLOCA
  5983.       alloca (0);
  5984. #endif
  5985.     }
  5986.  
  5987.   /* Tell refers_to_mem_p that qty_const info is not available.  */
  5988.   qty_const = 0;
  5989.  
  5990.   if (max_elements_made < n_elements_made)
  5991.     max_elements_made = n_elements_made;
  5992.  
  5993.   return cse_jumps_altered;
  5994. }
  5995.  
  5996. static rtx
  5997. cse_basic_block (from, to, next_branch)
  5998.      register rtx from, to;
  5999.      struct branch_path *next_branch;
  6000. {
  6001.   register rtx insn;
  6002.  
  6003.   /* Each of these arrays is undefined before max_reg, so only allocate
  6004.      the space actually needed and adjust the start below.  */
  6005.  
  6006.   qty_first_reg = (int *) alloca ((max_qty - max_reg) * sizeof (int));
  6007.   qty_last_reg = (int *) alloca ((max_qty - max_reg) * sizeof (int));
  6008.   qty_const = (rtx *) alloca ((max_qty - max_reg) * sizeof (rtx));
  6009.   qty_const_insn = (rtx *) alloca ((max_qty - max_reg) * sizeof (rtx));
  6010.   qty_comparison_code
  6011.     = (enum rtx_code *) alloca ((max_qty - max_reg) * sizeof (enum rtx_code));
  6012.   qty_comparison_qty = (int *) alloca ((max_qty - max_reg) * sizeof (int));
  6013.   qty_comparison_const = (rtx *) alloca ((max_qty - max_reg) * sizeof (rtx));
  6014.  
  6015.   qty_first_reg -= max_reg;
  6016.   qty_last_reg -= max_reg;
  6017.   qty_const -= max_reg;
  6018.   qty_const_insn -= max_reg;
  6019.   qty_comparison_code -= max_reg;
  6020.   qty_comparison_qty -= max_reg;
  6021.   qty_comparison_const -= max_reg;
  6022.  
  6023.   new_basic_block ();
  6024.  
  6025.   cse_skip_to_next_block = 0;
  6026.  
  6027.   /* TO might be a label.  If so, protect it from being deleted.  */
  6028.   if (to != 0 && GET_CODE (to) == CODE_LABEL)
  6029.     ++LABEL_NUSES (to);
  6030.  
  6031.   for (insn = from; insn != to; insn = NEXT_INSN (insn))
  6032.     {
  6033.       register enum rtx_code code;
  6034.  
  6035.       /* See if this is a branch that is part of the path.  If so, and it is
  6036.      to be taken, do so.  */
  6037.       if (next_branch->branch == insn)
  6038.     {
  6039.       if (next_branch++->status == TAKEN)
  6040.         {
  6041.           record_jump_equiv (insn, 1);
  6042.           /* Set the last insn as the jump insn; it doesn't affect cc0.
  6043.          Then follow this branch.  */
  6044. #ifdef HAVE_cc0
  6045.           prev_insn_cc0 = 0;
  6046. #endif
  6047.           prev_insn = insn;
  6048.           insn = JUMP_LABEL (insn);
  6049.           continue;
  6050.         }
  6051.     }
  6052.         
  6053.       code = GET_CODE (insn);
  6054.       if (GET_MODE (insn) == QImode)
  6055.     PUT_MODE (insn, VOIDmode);
  6056.  
  6057.       if (GET_RTX_CLASS (code) == 'i')
  6058.     cse_insn (insn);
  6059.  
  6060.       /* If we are to skip to the end of this block, pretend we just
  6061.      processed the insn before TO.  */
  6062.       if (cse_skip_to_next_block)
  6063.     {
  6064.       cse_skip_to_next_block = 0;
  6065.       if (to == 0)
  6066.         return 0;
  6067.  
  6068.       insn = PREV_INSN (to);
  6069.     }
  6070.  
  6071.       /* See if it is ok to keep on going past the label
  6072.      which used to end our basic block.  Remember that we incremented
  6073.      the count of that label, so we decremement it here.  */
  6074.       if (to != 0 && NEXT_INSN (insn) == to
  6075.       && GET_CODE (to) == CODE_LABEL
  6076.       && --LABEL_NUSES (to) == 0)
  6077.     {
  6078.       struct cse_basic_block_data val;
  6079.  
  6080.       /* Delete the dead label.  */
  6081.       delete_insn (to);
  6082.  
  6083.       /* Find the end of the following block.  Note that we won't be
  6084.          following branches in this case.  If TO was the last insn
  6085.          in the function, we are done.  */
  6086.       if (NEXT_INSN (insn) == 0)
  6087.         return 0;
  6088.  
  6089.       val.path_size = 0;
  6090.       cse_end_of_basic_block (NEXT_INSN (insn), &val, 0);
  6091.  
  6092.       /* If the tables we allocated have enough space left
  6093.          to handle all the SETs in the next basic block,
  6094.          continue through it.  Otherwise, return,
  6095.          and that block will be scanned individually.  */
  6096.       if (val.nsets * 2 + next_qty > max_qty)
  6097.         break;
  6098.  
  6099.       cse_basic_block_start = val.low_cuid;
  6100.       cse_basic_block_end = val.high_cuid;
  6101.       to = val.last;
  6102.  
  6103.       /* Prevent TO from being deleted if it is a label.  */
  6104.       if (to != 0 && GET_CODE (to) == CODE_LABEL)
  6105.         ++LABEL_NUSES (to);
  6106.     }
  6107.     }
  6108.  
  6109.   if (next_qty > max_qty)
  6110.     abort ();
  6111.  
  6112.   return to ? NEXT_INSN (to) : 0;
  6113. }
  6114.  
  6115. /* Count the number of times registers are used (not set) in X.
  6116.    COUNTS is an array in which we accumulate the count, INCR is how much
  6117.    we count each register usage.  */
  6118.  
  6119. static void
  6120. count_reg_usage (x, counts, incr)
  6121.      rtx x;
  6122.      int *counts;
  6123.      int incr;
  6124. {
  6125.   enum rtx_code code = GET_CODE (x);
  6126.   char *fmt;
  6127.   int i, j;
  6128.  
  6129.   switch (code)
  6130.     {
  6131.     case REG:
  6132.       counts[REGNO (x)] += incr;
  6133.       return;
  6134.  
  6135.     case PC:
  6136.     case CC0:
  6137.     case CONST:
  6138.     case CONST_INT:
  6139.     case CONST_DOUBLE:
  6140.     case SYMBOL_REF:
  6141.     case LABEL_REF:
  6142.     case CLOBBER:
  6143.       return;
  6144.  
  6145.     case SET:
  6146.       /* Unless we are setting a REG, count everything in SET_DEST.  */
  6147.       if (GET_CODE (SET_DEST (x)) != REG)
  6148.     count_reg_usage (SET_DEST (x), counts, incr);
  6149.       count_reg_usage (SET_SRC (x), counts, incr);
  6150.       return;
  6151.     }
  6152.  
  6153.   fmt = GET_RTX_FORMAT (code);
  6154.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  6155.     {
  6156.       if (fmt[i] == 'e')
  6157.     count_reg_usage (XEXP (x, i), counts, incr);
  6158.       else if (fmt[i] == 'E')
  6159.     for (j = XVECLEN (x, i) - 1; j >= 0; j--)
  6160.       count_reg_usage (XVECEXP (x, i, j), counts, incr);
  6161.     }
  6162. }
  6163.  
  6164. /* Scan all the insns and delete any that are dead; i.e., they store a register
  6165.    that is never used.
  6166.  
  6167.    This is used to remove insns made obviously dead by cse.  It improves the
  6168.    heuristics in loop since it won't try to move dead invariants out of loops
  6169.    or make givs for dead quantities.  The remaining passes of the compilation
  6170.    are also sped up.  */
  6171.  
  6172. void
  6173. delete_dead_from_cse (insns, nreg)
  6174.      rtx insns;
  6175.      int nreg;
  6176. {
  6177.   int *counts = (int *) alloca (nreg * sizeof (int));
  6178.   rtx insn;
  6179.   int i;
  6180.  
  6181.   /* First count the number of times each register is used.  */
  6182.   bzero (counts, sizeof (int) * nreg);
  6183.   for (insn = next_active_insn (insns);
  6184.        insn;
  6185.        insn = next_active_insn (insn))
  6186.     count_reg_usage (PATTERN (insn), counts, 1);
  6187.  
  6188.   /* Go from the last insn to the first and delete insns that only set unused
  6189.      registers.  As we delete an insn, remove usage counts for registers it
  6190.      uses.  */
  6191.   for (insn = prev_active_insn (get_last_insn ());
  6192.        insn; insn = prev_active_insn (insn))
  6193.     {
  6194.       int live_insn = 0;
  6195.  
  6196.       if (GET_CODE (PATTERN (insn)) == SET)
  6197.     {
  6198.       if (GET_CODE (SET_DEST (PATTERN (insn))) != REG
  6199.           || REGNO (SET_DEST (PATTERN (insn))) < FIRST_PSEUDO_REGISTER
  6200.           || counts[REGNO (SET_DEST (PATTERN (insn)))] != 0
  6201.           || side_effects_p (SET_SRC (PATTERN (insn))))
  6202.         live_insn = 1;
  6203.     }
  6204.       else if (GET_CODE (PATTERN (insn)) == PARALLEL)
  6205.     for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
  6206.       {
  6207.         rtx elt = XVECEXP (PATTERN (insn), 0, i);
  6208.  
  6209.         if (GET_CODE (elt) == SET)
  6210.           {
  6211.         if (GET_CODE (SET_DEST (elt)) != REG
  6212.             || REGNO (SET_DEST (elt)) < FIRST_PSEUDO_REGISTER
  6213.             || counts[REGNO (SET_DEST (elt))] != 0
  6214.             || side_effects_p (SET_SRC (elt)))
  6215.           live_insn = 1;
  6216.           }
  6217.         else if (GET_CODE (elt) != CLOBBER && GET_CODE (elt) != USE)
  6218.           live_insn = 1;
  6219.       }
  6220.       else
  6221.     live_insn = 1;
  6222.  
  6223.       /* If this is a dead insn, delete it and show registers in it aren't
  6224.      being used.  If this is the last insn of a libcall sequence, don't
  6225.      delete it even if it is dead because we don't know how to do so
  6226.      here.  */
  6227.  
  6228.       if (! live_insn && ! find_reg_note (insn, REG_RETVAL, 0))
  6229.     {
  6230.       count_reg_usage (PATTERN (insn), counts, -1);
  6231.       PUT_CODE (insn, NOTE);
  6232.       NOTE_SOURCE_FILE (insn) = 0;
  6233.       NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
  6234.     }
  6235.     }
  6236. }
  6237.