1/* Common subexpression elimination for GNU compiler.
2 Copyright (C) 1987-2017 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING3. If not see
18<http://www.gnu.org/licenses/>. */
19
20#include "config.h"
21#include "system.h"
22#include "coretypes.h"
23#include "backend.h"
24#include "target.h"
25#include "rtl.h"
26#include "tree.h"
27#include "cfghooks.h"
28#include "df.h"
29#include "memmodel.h"
30#include "tm_p.h"
31#include "insn-config.h"
32#include "regs.h"
33#include "emit-rtl.h"
34#include "recog.h"
35#include "cfgrtl.h"
36#include "cfganal.h"
37#include "cfgcleanup.h"
38#include "alias.h"
39#include "toplev.h"
40#include "params.h"
41#include "rtlhooks-def.h"
42#include "tree-pass.h"
43#include "dbgcnt.h"
44#include "rtl-iter.h"
45
46/* The basic idea of common subexpression elimination is to go
47 through the code, keeping a record of expressions that would
48 have the same value at the current scan point, and replacing
49 expressions encountered with the cheapest equivalent expression.
50
51 It is too complicated to keep track of the different possibilities
52 when control paths merge in this code; so, at each label, we forget all
53 that is known and start fresh. This can be described as processing each
54 extended basic block separately. We have a separate pass to perform
55 global CSE.
56
57 Note CSE can turn a conditional or computed jump into a nop or
58 an unconditional jump. When this occurs we arrange to run the jump
59 optimizer after CSE to delete the unreachable code.
60
61 We use two data structures to record the equivalent expressions:
62 a hash table for most expressions, and a vector of "quantity
63 numbers" to record equivalent (pseudo) registers.
64
65 The use of the special data structure for registers is desirable
66 because it is faster. It is possible because registers references
67 contain a fairly small number, the register number, taken from
68 a contiguously allocated series, and two register references are
69 identical if they have the same number. General expressions
70 do not have any such thing, so the only way to retrieve the
71 information recorded on an expression other than a register
72 is to keep it in a hash table.
73
74Registers and "quantity numbers":
75
76 At the start of each basic block, all of the (hardware and pseudo)
77 registers used in the function are given distinct quantity
78 numbers to indicate their contents. During scan, when the code
79 copies one register into another, we copy the quantity number.
80 When a register is loaded in any other way, we allocate a new
81 quantity number to describe the value generated by this operation.
82 `REG_QTY (N)' records what quantity register N is currently thought
83 of as containing.
84
85 All real quantity numbers are greater than or equal to zero.
86 If register N has not been assigned a quantity, `REG_QTY (N)' will
87 equal -N - 1, which is always negative.
88
89 Quantity numbers below zero do not exist and none of the `qty_table'
90 entries should be referenced with a negative index.
91
92 We also maintain a bidirectional chain of registers for each
93 quantity number. The `qty_table` members `first_reg' and `last_reg',
94 and `reg_eqv_table' members `next' and `prev' hold these chains.
95
96 The first register in a chain is the one whose lifespan is least local.
97 Among equals, it is the one that was seen first.
98 We replace any equivalent register with that one.
99
100 If two registers have the same quantity number, it must be true that
101 REG expressions with qty_table `mode' must be in the hash table for both
102 registers and must be in the same class.
103
104 The converse is not true. Since hard registers may be referenced in
105 any mode, two REG expressions might be equivalent in the hash table
106 but not have the same quantity number if the quantity number of one
107 of the registers is not the same mode as those expressions.
108
109Constants and quantity numbers
110
111 When a quantity has a known constant value, that value is stored
112 in the appropriate qty_table `const_rtx'. This is in addition to
113 putting the constant in the hash table as is usual for non-regs.
114
115 Whether a reg or a constant is preferred is determined by the configuration
116 macro CONST_COSTS and will often depend on the constant value. In any
117 event, expressions containing constants can be simplified, by fold_rtx.
118
119 When a quantity has a known nearly constant value (such as an address
120 of a stack slot), that value is stored in the appropriate qty_table
121 `const_rtx'.
122
123 Integer constants don't have a machine mode. However, cse
124 determines the intended machine mode from the destination
125 of the instruction that moves the constant. The machine mode
126 is recorded in the hash table along with the actual RTL
127 constant expression so that different modes are kept separate.
128
129Other expressions:
130
131 To record known equivalences among expressions in general
132 we use a hash table called `table'. It has a fixed number of buckets
133 that contain chains of `struct table_elt' elements for expressions.
134 These chains connect the elements whose expressions have the same
135 hash codes.
136
137 Other chains through the same elements connect the elements which
138 currently have equivalent values.
139
140 Register references in an expression are canonicalized before hashing
141 the expression. This is done using `reg_qty' and qty_table `first_reg'.
142 The hash code of a register reference is computed using the quantity
143 number, not the register number.
144
145 When the value of an expression changes, it is necessary to remove from the
146 hash table not just that expression but all expressions whose values
147 could be different as a result.
148
149 1. If the value changing is in memory, except in special cases
150 ANYTHING referring to memory could be changed. That is because
151 nobody knows where a pointer does not point.
152 The function `invalidate_memory' removes what is necessary.
153
154 The special cases are when the address is constant or is
155 a constant plus a fixed register such as the frame pointer
156 or a static chain pointer. When such addresses are stored in,
157 we can tell exactly which other such addresses must be invalidated
158 due to overlap. `invalidate' does this.
159 All expressions that refer to non-constant
160 memory addresses are also invalidated. `invalidate_memory' does this.
161
162 2. If the value changing is a register, all expressions
163 containing references to that register, and only those,
164 must be removed.
165
166 Because searching the entire hash table for expressions that contain
167 a register is very slow, we try to figure out when it isn't necessary.
168 Precisely, this is necessary only when expressions have been
169 entered in the hash table using this register, and then the value has
170 changed, and then another expression wants to be added to refer to
171 the register's new value. This sequence of circumstances is rare
172 within any one basic block.
173
174 `REG_TICK' and `REG_IN_TABLE', accessors for members of
175 cse_reg_info, are used to detect this case. REG_TICK (i) is
176 incremented whenever a value is stored in register i.
177 REG_IN_TABLE (i) holds -1 if no references to register i have been
178 entered in the table; otherwise, it contains the value REG_TICK (i)
179 had when the references were entered. If we want to enter a
180 reference and REG_IN_TABLE (i) != REG_TICK (i), we must scan and
181 remove old references. Until we want to enter a new entry, the
182 mere fact that the two vectors don't match makes the entries be
183 ignored if anyone tries to match them.
184
185 Registers themselves are entered in the hash table as well as in
186 the equivalent-register chains. However, `REG_TICK' and
187 `REG_IN_TABLE' do not apply to expressions which are simple
188 register references. These expressions are removed from the table
189 immediately when they become invalid, and this can be done even if
190 we do not immediately search for all the expressions that refer to
191 the register.
192
193 A CLOBBER rtx in an instruction invalidates its operand for further
194 reuse. A CLOBBER or SET rtx whose operand is a MEM:BLK
195 invalidates everything that resides in memory.
196
197Related expressions:
198
199 Constant expressions that differ only by an additive integer
200 are called related. When a constant expression is put in
201 the table, the related expression with no constant term
202 is also entered. These are made to point at each other
203 so that it is possible to find out if there exists any
204 register equivalent to an expression related to a given expression. */
205
206/* Length of qty_table vector. We know in advance we will not need
207 a quantity number this big. */
208
209static int max_qty;
210
211/* Next quantity number to be allocated.
212 This is 1 + the largest number needed so far. */
213
214static int next_qty;
215
216/* Per-qty information tracking.
217
218 `first_reg' and `last_reg' track the head and tail of the
219 chain of registers which currently contain this quantity.
220
221 `mode' contains the machine mode of this quantity.
222
223 `const_rtx' holds the rtx of the constant value of this
224 quantity, if known. A summations of the frame/arg pointer
225 and a constant can also be entered here. When this holds
226 a known value, `const_insn' is the insn which stored the
227 constant value.
228
229 `comparison_{code,const,qty}' are used to track when a
230 comparison between a quantity and some constant or register has
231 been passed. In such a case, we know the results of the comparison
232 in case we see it again. These members record a comparison that
233 is known to be true. `comparison_code' holds the rtx code of such
234 a comparison, else it is set to UNKNOWN and the other two
235 comparison members are undefined. `comparison_const' holds
236 the constant being compared against, or zero if the comparison
237 is not against a constant. `comparison_qty' holds the quantity
238 being compared against when the result is known. If the comparison
239 is not with a register, `comparison_qty' is -1. */
240
241struct qty_table_elem
242{
243 rtx const_rtx;
244 rtx_insn *const_insn;
245 rtx comparison_const;
246 int comparison_qty;
247 unsigned int first_reg, last_reg;
248 /* The sizes of these fields should match the sizes of the
249 code and mode fields of struct rtx_def (see rtl.h). */
250 ENUM_BITFIELD(rtx_code) comparison_code : 16;
251 ENUM_BITFIELD(machine_mode) mode : 8;
252};
253
254/* The table of all qtys, indexed by qty number. */
255static struct qty_table_elem *qty_table;
256
257/* For machines that have a CC0, we do not record its value in the hash
258 table since its use is guaranteed to be the insn immediately following
259 its definition and any other insn is presumed to invalidate it.
260
261 Instead, we store below the current and last value assigned to CC0.
262 If it should happen to be a constant, it is stored in preference
263 to the actual assigned value. In case it is a constant, we store
264 the mode in which the constant should be interpreted. */
265
266static rtx this_insn_cc0, prev_insn_cc0;
267static machine_mode this_insn_cc0_mode, prev_insn_cc0_mode;
268
269/* Insn being scanned. */
270
271static rtx_insn *this_insn;
272static bool optimize_this_for_speed_p;
273
274/* Index by register number, gives the number of the next (or
275 previous) register in the chain of registers sharing the same
276 value.
277
278 Or -1 if this register is at the end of the chain.
279
280 If REG_QTY (N) == -N - 1, reg_eqv_table[N].next is undefined. */
281
282/* Per-register equivalence chain. */
283struct reg_eqv_elem
284{
285 int next, prev;
286};
287
288/* The table of all register equivalence chains. */
289static struct reg_eqv_elem *reg_eqv_table;
290
291struct cse_reg_info
292{
293 /* The timestamp at which this register is initialized. */
294 unsigned int timestamp;
295
296 /* The quantity number of the register's current contents. */
297 int reg_qty;
298
299 /* The number of times the register has been altered in the current
300 basic block. */
301 int reg_tick;
302
303 /* The REG_TICK value at which rtx's containing this register are
304 valid in the hash table. If this does not equal the current
305 reg_tick value, such expressions existing in the hash table are
306 invalid. */
307 int reg_in_table;
308
309 /* The SUBREG that was set when REG_TICK was last incremented. Set
310 to -1 if the last store was to the whole register, not a subreg. */
311 unsigned int subreg_ticked;
312};
313
314/* A table of cse_reg_info indexed by register numbers. */
315static struct cse_reg_info *cse_reg_info_table;
316
317/* The size of the above table. */
318static unsigned int cse_reg_info_table_size;
319
320/* The index of the first entry that has not been initialized. */
321static unsigned int cse_reg_info_table_first_uninitialized;
322
323/* The timestamp at the beginning of the current run of
324 cse_extended_basic_block. We increment this variable at the beginning of
325 the current run of cse_extended_basic_block. The timestamp field of a
326 cse_reg_info entry matches the value of this variable if and only
327 if the entry has been initialized during the current run of
328 cse_extended_basic_block. */
329static unsigned int cse_reg_info_timestamp;
330
331/* A HARD_REG_SET containing all the hard registers for which there is
332 currently a REG expression in the hash table. Note the difference
333 from the above variables, which indicate if the REG is mentioned in some
334 expression in the table. */
335
336static HARD_REG_SET hard_regs_in_table;
337
338/* True if CSE has altered the CFG. */
339static bool cse_cfg_altered;
340
341/* True if CSE has altered conditional jump insns in such a way
342 that jump optimization should be redone. */
343static bool cse_jumps_altered;
344
345/* True if we put a LABEL_REF into the hash table for an INSN
346 without a REG_LABEL_OPERAND, we have to rerun jump after CSE
347 to put in the note. */
348static bool recorded_label_ref;
349
350/* canon_hash stores 1 in do_not_record
351 if it notices a reference to CC0, PC, or some other volatile
352 subexpression. */
353
354static int do_not_record;
355
356/* canon_hash stores 1 in hash_arg_in_memory
357 if it notices a reference to memory within the expression being hashed. */
358
359static int hash_arg_in_memory;
360
361/* The hash table contains buckets which are chains of `struct table_elt's,
362 each recording one expression's information.
363 That expression is in the `exp' field.
364
365 The canon_exp field contains a canonical (from the point of view of
366 alias analysis) version of the `exp' field.
367
368 Those elements with the same hash code are chained in both directions
369 through the `next_same_hash' and `prev_same_hash' fields.
370
371 Each set of expressions with equivalent values
372 are on a two-way chain through the `next_same_value'
373 and `prev_same_value' fields, and all point with
374 the `first_same_value' field at the first element in
375 that chain. The chain is in order of increasing cost.
376 Each element's cost value is in its `cost' field.
377
378 The `in_memory' field is nonzero for elements that
379 involve any reference to memory. These elements are removed
380 whenever a write is done to an unidentified location in memory.
381 To be safe, we assume that a memory address is unidentified unless
382 the address is either a symbol constant or a constant plus
383 the frame pointer or argument pointer.
384
385 The `related_value' field is used to connect related expressions
386 (that differ by adding an integer).
387 The related expressions are chained in a circular fashion.
388 `related_value' is zero for expressions for which this
389 chain is not useful.
390
391 The `cost' field stores the cost of this element's expression.
392 The `regcost' field stores the value returned by approx_reg_cost for
393 this element's expression.
394
395 The `is_const' flag is set if the element is a constant (including
396 a fixed address).
397
398 The `flag' field is used as a temporary during some search routines.
399
400 The `mode' field is usually the same as GET_MODE (`exp'), but
401 if `exp' is a CONST_INT and has no machine mode then the `mode'
402 field is the mode it was being used as. Each constant is
403 recorded separately for each mode it is used with. */
404
405struct table_elt
406{
407 rtx exp;
408 rtx canon_exp;
409 struct table_elt *next_same_hash;
410 struct table_elt *prev_same_hash;
411 struct table_elt *next_same_value;
412 struct table_elt *prev_same_value;
413 struct table_elt *first_same_value;
414 struct table_elt *related_value;
415 int cost;
416 int regcost;
417 /* The size of this field should match the size
418 of the mode field of struct rtx_def (see rtl.h). */
419 ENUM_BITFIELD(machine_mode) mode : 8;
420 char in_memory;
421 char is_const;
422 char flag;
423};
424
425/* We don't want a lot of buckets, because we rarely have very many
426 things stored in the hash table, and a lot of buckets slows
427 down a lot of loops that happen frequently. */
428#define HASH_SHIFT 5
429#define HASH_SIZE (1 << HASH_SHIFT)
430#define HASH_MASK (HASH_SIZE - 1)
431
432/* Compute hash code of X in mode M. Special-case case where X is a pseudo
433 register (hard registers may require `do_not_record' to be set). */
434
435#define HASH(X, M) \
436 ((REG_P (X) && REGNO (X) >= FIRST_PSEUDO_REGISTER \
437 ? (((unsigned) REG << 7) + (unsigned) REG_QTY (REGNO (X))) \
438 : canon_hash (X, M)) & HASH_MASK)
439
440/* Like HASH, but without side-effects. */
441#define SAFE_HASH(X, M) \
442 ((REG_P (X) && REGNO (X) >= FIRST_PSEUDO_REGISTER \
443 ? (((unsigned) REG << 7) + (unsigned) REG_QTY (REGNO (X))) \
444 : safe_hash (X, M)) & HASH_MASK)
445
446/* Determine whether register number N is considered a fixed register for the
447 purpose of approximating register costs.
448 It is desirable to replace other regs with fixed regs, to reduce need for
449 non-fixed hard regs.
450 A reg wins if it is either the frame pointer or designated as fixed. */
451#define FIXED_REGNO_P(N) \
452 ((N) == FRAME_POINTER_REGNUM || (N) == HARD_FRAME_POINTER_REGNUM \
453 || fixed_regs[N] || global_regs[N])
454
455/* Compute cost of X, as stored in the `cost' field of a table_elt. Fixed
456 hard registers and pointers into the frame are the cheapest with a cost
457 of 0. Next come pseudos with a cost of one and other hard registers with
458 a cost of 2. Aside from these special cases, call `rtx_cost'. */
459
460#define CHEAP_REGNO(N) \
461 (REGNO_PTR_FRAME_P (N) \
462 || (HARD_REGISTER_NUM_P (N) \
463 && FIXED_REGNO_P (N) && REGNO_REG_CLASS (N) != NO_REGS))
464
465#define COST(X, MODE) \
466 (REG_P (X) ? 0 : notreg_cost (X, MODE, SET, 1))
467#define COST_IN(X, MODE, OUTER, OPNO) \
468 (REG_P (X) ? 0 : notreg_cost (X, MODE, OUTER, OPNO))
469
470/* Get the number of times this register has been updated in this
471 basic block. */
472
473#define REG_TICK(N) (get_cse_reg_info (N)->reg_tick)
474
475/* Get the point at which REG was recorded in the table. */
476
477#define REG_IN_TABLE(N) (get_cse_reg_info (N)->reg_in_table)
478
479/* Get the SUBREG set at the last increment to REG_TICK (-1 if not a
480 SUBREG). */
481
482#define SUBREG_TICKED(N) (get_cse_reg_info (N)->subreg_ticked)
483
484/* Get the quantity number for REG. */
485
486#define REG_QTY(N) (get_cse_reg_info (N)->reg_qty)
487
488/* Determine if the quantity number for register X represents a valid index
489 into the qty_table. */
490
491#define REGNO_QTY_VALID_P(N) (REG_QTY (N) >= 0)
492
493/* Compare table_elt X and Y and return true iff X is cheaper than Y. */
494
495#define CHEAPER(X, Y) \
496 (preferable ((X)->cost, (X)->regcost, (Y)->cost, (Y)->regcost) < 0)
497
498static struct table_elt *table[HASH_SIZE];
499
500/* Chain of `struct table_elt's made so far for this function
501 but currently removed from the table. */
502
503static struct table_elt *free_element_chain;
504
505/* Set to the cost of a constant pool reference if one was found for a
506 symbolic constant. If this was found, it means we should try to
507 convert constants into constant pool entries if they don't fit in
508 the insn. */
509
510static int constant_pool_entries_cost;
511static int constant_pool_entries_regcost;
512
513/* Trace a patch through the CFG. */
514
515struct branch_path
516{
517 /* The basic block for this path entry. */
518 basic_block bb;
519};
520
521/* This data describes a block that will be processed by
522 cse_extended_basic_block. */
523
524struct cse_basic_block_data
525{
526 /* Total number of SETs in block. */
527 int nsets;
528 /* Size of current branch path, if any. */
529 int path_size;
530 /* Current path, indicating which basic_blocks will be processed. */
531 struct branch_path *path;
532};
533
534
535/* Pointers to the live in/live out bitmaps for the boundaries of the
536 current EBB. */
537static bitmap cse_ebb_live_in, cse_ebb_live_out;
538
539/* A simple bitmap to track which basic blocks have been visited
540 already as part of an already processed extended basic block. */
541static sbitmap cse_visited_basic_blocks;
542
543static bool fixed_base_plus_p (rtx x);
544static int notreg_cost (rtx, machine_mode, enum rtx_code, int);
545static int preferable (int, int, int, int);
546static void new_basic_block (void);
547static void make_new_qty (unsigned int, machine_mode);
548static void make_regs_eqv (unsigned int, unsigned int);
549static void delete_reg_equiv (unsigned int);
550static int mention_regs (rtx);
551static int insert_regs (rtx, struct table_elt *, int);
552static void remove_from_table (struct table_elt *, unsigned);
553static void remove_pseudo_from_table (rtx, unsigned);
554static struct table_elt *lookup (rtx, unsigned, machine_mode);
555static struct table_elt *lookup_for_remove (rtx, unsigned, machine_mode);
556static rtx lookup_as_function (rtx, enum rtx_code);
557static struct table_elt *insert_with_costs (rtx, struct table_elt *, unsigned,
558 machine_mode, int, int);
559static struct table_elt *insert (rtx, struct table_elt *, unsigned,
560 machine_mode);
561static void merge_equiv_classes (struct table_elt *, struct table_elt *);
562static void invalidate (rtx, machine_mode);
563static void remove_invalid_refs (unsigned int);
564static void remove_invalid_subreg_refs (unsigned int, unsigned int,
565 machine_mode);
566static void rehash_using_reg (rtx);
567static void invalidate_memory (void);
568static void invalidate_for_call (void);
569static rtx use_related_value (rtx, struct table_elt *);
570
571static inline unsigned canon_hash (rtx, machine_mode);
572static inline unsigned safe_hash (rtx, machine_mode);
573static inline unsigned hash_rtx_string (const char *);
574
575static rtx canon_reg (rtx, rtx_insn *);
576static enum rtx_code find_comparison_args (enum rtx_code, rtx *, rtx *,
577 machine_mode *,
578 machine_mode *);
579static rtx fold_rtx (rtx, rtx_insn *);
580static rtx equiv_constant (rtx);
581static void record_jump_equiv (rtx_insn *, bool);
582static void record_jump_cond (enum rtx_code, machine_mode, rtx, rtx,
583 int);
584static void cse_insn (rtx_insn *);
585static void cse_prescan_path (struct cse_basic_block_data *);
586static void invalidate_from_clobbers (rtx_insn *);
587static void invalidate_from_sets_and_clobbers (rtx_insn *);
588static rtx cse_process_notes (rtx, rtx, bool *);
589static void cse_extended_basic_block (struct cse_basic_block_data *);
590extern void dump_class (struct table_elt*);
591static void get_cse_reg_info_1 (unsigned int regno);
592static struct cse_reg_info * get_cse_reg_info (unsigned int regno);
593
594static void flush_hash_table (void);
595static bool insn_live_p (rtx_insn *, int *);
596static bool set_live_p (rtx, rtx_insn *, int *);
597static void cse_change_cc_mode_insn (rtx_insn *, rtx);
598static void cse_change_cc_mode_insns (rtx_insn *, rtx_insn *, rtx);
599static machine_mode cse_cc_succs (basic_block, basic_block, rtx, rtx,
600 bool);
601
602
603#undef RTL_HOOKS_GEN_LOWPART
604#define RTL_HOOKS_GEN_LOWPART gen_lowpart_if_possible
605
606static const struct rtl_hooks cse_rtl_hooks = RTL_HOOKS_INITIALIZER;
607
608/* Nonzero if X has the form (PLUS frame-pointer integer). */
609
610static bool
611fixed_base_plus_p (rtx x)
612{
613 switch (GET_CODE (x))
614 {
615 case REG:
616 if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx)
617 return true;
618 if (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM])
619 return true;
620 return false;
621
622 case PLUS:
623 if (!CONST_INT_P (XEXP (x, 1)))
624 return false;
625 return fixed_base_plus_p (XEXP (x, 0));
626
627 default:
628 return false;
629 }
630}
631
632/* Dump the expressions in the equivalence class indicated by CLASSP.
633 This function is used only for debugging. */
634DEBUG_FUNCTION void
635dump_class (struct table_elt *classp)
636{
637 struct table_elt *elt;
638
639 fprintf (stderr, "Equivalence chain for ");
640 print_rtl (stderr, classp->exp);
641 fprintf (stderr, ": \n");
642
643 for (elt = classp->first_same_value; elt; elt = elt->next_same_value)
644 {
645 print_rtl (stderr, elt->exp);
646 fprintf (stderr, "\n");
647 }
648}
649
650/* Return an estimate of the cost of the registers used in an rtx.
651 This is mostly the number of different REG expressions in the rtx;
652 however for some exceptions like fixed registers we use a cost of
653 0. If any other hard register reference occurs, return MAX_COST. */
654
655static int
656approx_reg_cost (const_rtx x)
657{
658 int cost = 0;
659 subrtx_iterator::array_type array;
660 FOR_EACH_SUBRTX (iter, array, x, NONCONST)
661 {
662 const_rtx x = *iter;
663 if (REG_P (x))
664 {
665 unsigned int regno = REGNO (x);
666 if (!CHEAP_REGNO (regno))
667 {
668 if (regno < FIRST_PSEUDO_REGISTER)
669 {
670 if (targetm.small_register_classes_for_mode_p (GET_MODE (x)))
671 return MAX_COST;
672 cost += 2;
673 }
674 else
675 cost += 1;
676 }
677 }
678 }
679 return cost;
680}
681
682/* Return a negative value if an rtx A, whose costs are given by COST_A
683 and REGCOST_A, is more desirable than an rtx B.
684 Return a positive value if A is less desirable, or 0 if the two are
685 equally good. */
686static int
687preferable (int cost_a, int regcost_a, int cost_b, int regcost_b)
688{
689 /* First, get rid of cases involving expressions that are entirely
690 unwanted. */
691 if (cost_a != cost_b)
692 {
693 if (cost_a == MAX_COST)
694 return 1;
695 if (cost_b == MAX_COST)
696 return -1;
697 }
698
699 /* Avoid extending lifetimes of hardregs. */
700 if (regcost_a != regcost_b)
701 {
702 if (regcost_a == MAX_COST)
703 return 1;
704 if (regcost_b == MAX_COST)
705 return -1;
706 }
707
708 /* Normal operation costs take precedence. */
709 if (cost_a != cost_b)
710 return cost_a - cost_b;
711 /* Only if these are identical consider effects on register pressure. */
712 if (regcost_a != regcost_b)
713 return regcost_a - regcost_b;
714 return 0;
715}
716
717/* Internal function, to compute cost when X is not a register; called
718 from COST macro to keep it simple. */
719
720static int
721notreg_cost (rtx x, machine_mode mode, enum rtx_code outer, int opno)
722{
723 scalar_int_mode int_mode, inner_mode;
724 return ((GET_CODE (x) == SUBREG
725 && REG_P (SUBREG_REG (x))
726 && is_int_mode (mode, &int_mode)
727 && is_int_mode (GET_MODE (SUBREG_REG (x)), &inner_mode)
728 && GET_MODE_SIZE (int_mode) < GET_MODE_SIZE (inner_mode)
729 && subreg_lowpart_p (x)
730 && TRULY_NOOP_TRUNCATION_MODES_P (int_mode, inner_mode))
731 ? 0
732 : rtx_cost (x, mode, outer, opno, optimize_this_for_speed_p) * 2);
733}
734
735
736/* Initialize CSE_REG_INFO_TABLE. */
737
738static void
739init_cse_reg_info (unsigned int nregs)
740{
741 /* Do we need to grow the table? */
742 if (nregs > cse_reg_info_table_size)
743 {
744 unsigned int new_size;
745
746 if (cse_reg_info_table_size < 2048)
747 {
748 /* Compute a new size that is a power of 2 and no smaller
749 than the large of NREGS and 64. */
750 new_size = (cse_reg_info_table_size
751 ? cse_reg_info_table_size : 64);
752
753 while (new_size < nregs)
754 new_size *= 2;
755 }
756 else
757 {
758 /* If we need a big table, allocate just enough to hold
759 NREGS registers. */
760 new_size = nregs;
761 }
762
763 /* Reallocate the table with NEW_SIZE entries. */
764 free (cse_reg_info_table);
765 cse_reg_info_table = XNEWVEC (struct cse_reg_info, new_size);
766 cse_reg_info_table_size = new_size;
767 cse_reg_info_table_first_uninitialized = 0;
768 }
769
770 /* Do we have all of the first NREGS entries initialized? */
771 if (cse_reg_info_table_first_uninitialized < nregs)
772 {
773 unsigned int old_timestamp = cse_reg_info_timestamp - 1;
774 unsigned int i;
775
776 /* Put the old timestamp on newly allocated entries so that they
777 will all be considered out of date. We do not touch those
778 entries beyond the first NREGS entries to be nice to the
779 virtual memory. */
780 for (i = cse_reg_info_table_first_uninitialized; i < nregs; i++)
781 cse_reg_info_table[i].timestamp = old_timestamp;
782
783 cse_reg_info_table_first_uninitialized = nregs;
784 }
785}
786
787/* Given REGNO, initialize the cse_reg_info entry for REGNO. */
788
789static void
790get_cse_reg_info_1 (unsigned int regno)
791{
792 /* Set TIMESTAMP field to CSE_REG_INFO_TIMESTAMP so that this
793 entry will be considered to have been initialized. */
794 cse_reg_info_table[regno].timestamp = cse_reg_info_timestamp;
795
796 /* Initialize the rest of the entry. */
797 cse_reg_info_table[regno].reg_tick = 1;
798 cse_reg_info_table[regno].reg_in_table = -1;
799 cse_reg_info_table[regno].subreg_ticked = -1;
800 cse_reg_info_table[regno].reg_qty = -regno - 1;
801}
802
803/* Find a cse_reg_info entry for REGNO. */
804
805static inline struct cse_reg_info *
806get_cse_reg_info (unsigned int regno)
807{
808 struct cse_reg_info *p = &cse_reg_info_table[regno];
809
810 /* If this entry has not been initialized, go ahead and initialize
811 it. */
812 if (p->timestamp != cse_reg_info_timestamp)
813 get_cse_reg_info_1 (regno);
814
815 return p;
816}
817
818/* Clear the hash table and initialize each register with its own quantity,
819 for a new basic block. */
820
821static void
822new_basic_block (void)
823{
824 int i;
825
826 next_qty = 0;
827
828 /* Invalidate cse_reg_info_table. */
829 cse_reg_info_timestamp++;
830
831 /* Clear out hash table state for this pass. */
832 CLEAR_HARD_REG_SET (hard_regs_in_table);
833
834 /* The per-quantity values used to be initialized here, but it is
835 much faster to initialize each as it is made in `make_new_qty'. */
836
837 for (i = 0; i < HASH_SIZE; i++)
838 {
839 struct table_elt *first;
840
841 first = table[i];
842 if (first != NULL)
843 {
844 struct table_elt *last = first;
845
846 table[i] = NULL;
847
848 while (last->next_same_hash != NULL)
849 last = last->next_same_hash;
850
851 /* Now relink this hash entire chain into
852 the free element list. */
853
854 last->next_same_hash = free_element_chain;
855 free_element_chain = first;
856 }
857 }
858
859 prev_insn_cc0 = 0;
860}
861
862/* Say that register REG contains a quantity in mode MODE not in any
863 register before and initialize that quantity. */
864
865static void
866make_new_qty (unsigned int reg, machine_mode mode)
867{
868 int q;
869 struct qty_table_elem *ent;
870 struct reg_eqv_elem *eqv;
871
872 gcc_assert (next_qty < max_qty);
873
874 q = REG_QTY (reg) = next_qty++;
875 ent = &qty_table[q];
876 ent->first_reg = reg;
877 ent->last_reg = reg;
878 ent->mode = mode;
879 ent->const_rtx = ent->const_insn = NULL;
880 ent->comparison_code = UNKNOWN;
881
882 eqv = &reg_eqv_table[reg];
883 eqv->next = eqv->prev = -1;
884}
885
886/* Make reg NEW equivalent to reg OLD.
887 OLD is not changing; NEW is. */
888
889static void
890make_regs_eqv (unsigned int new_reg, unsigned int old_reg)
891{
892 unsigned int lastr, firstr;
893 int q = REG_QTY (old_reg);
894 struct qty_table_elem *ent;
895
896 ent = &qty_table[q];
897
898 /* Nothing should become eqv until it has a "non-invalid" qty number. */
899 gcc_assert (REGNO_QTY_VALID_P (old_reg));
900
901 REG_QTY (new_reg) = q;
902 firstr = ent->first_reg;
903 lastr = ent->last_reg;
904
905 /* Prefer fixed hard registers to anything. Prefer pseudo regs to other
906 hard regs. Among pseudos, if NEW will live longer than any other reg
907 of the same qty, and that is beyond the current basic block,
908 make it the new canonical replacement for this qty. */
909 if (! (firstr < FIRST_PSEUDO_REGISTER && FIXED_REGNO_P (firstr))
910 /* Certain fixed registers might be of the class NO_REGS. This means
911 that not only can they not be allocated by the compiler, but
912 they cannot be used in substitutions or canonicalizations
913 either. */
914 && (new_reg >= FIRST_PSEUDO_REGISTER || REGNO_REG_CLASS (new_reg) != NO_REGS)
915 && ((new_reg < FIRST_PSEUDO_REGISTER && FIXED_REGNO_P (new_reg))
916 || (new_reg >= FIRST_PSEUDO_REGISTER
917 && (firstr < FIRST_PSEUDO_REGISTER
918 || (bitmap_bit_p (cse_ebb_live_out, new_reg)
919 && !bitmap_bit_p (cse_ebb_live_out, firstr))
920 || (bitmap_bit_p (cse_ebb_live_in, new_reg)
921 && !bitmap_bit_p (cse_ebb_live_in, firstr))))))
922 {
923 reg_eqv_table[firstr].prev = new_reg;
924 reg_eqv_table[new_reg].next = firstr;
925 reg_eqv_table[new_reg].prev = -1;
926 ent->first_reg = new_reg;
927 }
928 else
929 {
930 /* If NEW is a hard reg (known to be non-fixed), insert at end.
931 Otherwise, insert before any non-fixed hard regs that are at the
932 end. Registers of class NO_REGS cannot be used as an
933 equivalent for anything. */
934 while (lastr < FIRST_PSEUDO_REGISTER && reg_eqv_table[lastr].prev >= 0
935 && (REGNO_REG_CLASS (lastr) == NO_REGS || ! FIXED_REGNO_P (lastr))
936 && new_reg >= FIRST_PSEUDO_REGISTER)
937 lastr = reg_eqv_table[lastr].prev;
938 reg_eqv_table[new_reg].next = reg_eqv_table[lastr].next;
939 if (reg_eqv_table[lastr].next >= 0)
940 reg_eqv_table[reg_eqv_table[lastr].next].prev = new_reg;
941 else
942 qty_table[q].last_reg = new_reg;
943 reg_eqv_table[lastr].next = new_reg;
944 reg_eqv_table[new_reg].prev = lastr;
945 }
946}
947
948/* Remove REG from its equivalence class. */
949
950static void
951delete_reg_equiv (unsigned int reg)
952{
953 struct qty_table_elem *ent;
954 int q = REG_QTY (reg);
955 int p, n;
956
957 /* If invalid, do nothing. */
958 if (! REGNO_QTY_VALID_P (reg))
959 return;
960
961 ent = &qty_table[q];
962
963 p = reg_eqv_table[reg].prev;
964 n = reg_eqv_table[reg].next;
965
966 if (n != -1)
967 reg_eqv_table[n].prev = p;
968 else
969 ent->last_reg = p;
970 if (p != -1)
971 reg_eqv_table[p].next = n;
972 else
973 ent->first_reg = n;
974
975 REG_QTY (reg) = -reg - 1;
976}
977
978/* Remove any invalid expressions from the hash table
979 that refer to any of the registers contained in expression X.
980
981 Make sure that newly inserted references to those registers
982 as subexpressions will be considered valid.
983
984 mention_regs is not called when a register itself
985 is being stored in the table.
986
987 Return 1 if we have done something that may have changed the hash code
988 of X. */
989
990static int
991mention_regs (rtx x)
992{
993 enum rtx_code code;
994 int i, j;
995 const char *fmt;
996 int changed = 0;
997
998 if (x == 0)
999 return 0;
1000
1001 code = GET_CODE (x);
1002 if (code == REG)
1003 {
1004 unsigned int regno = REGNO (x);
1005 unsigned int endregno = END_REGNO (x);
1006 unsigned int i;
1007
1008 for (i = regno; i < endregno; i++)
1009 {
1010 if (REG_IN_TABLE (i) >= 0 && REG_IN_TABLE (i) != REG_TICK (i))
1011 remove_invalid_refs (i);
1012
1013 REG_IN_TABLE (i) = REG_TICK (i);
1014 SUBREG_TICKED (i) = -1;
1015 }
1016
1017 return 0;
1018 }
1019
1020 /* If this is a SUBREG, we don't want to discard other SUBREGs of the same
1021 pseudo if they don't use overlapping words. We handle only pseudos
1022 here for simplicity. */
1023 if (code == SUBREG && REG_P (SUBREG_REG (x))
1024 && REGNO (SUBREG_REG (x)) >= FIRST_PSEUDO_REGISTER)
1025 {
1026 unsigned int i = REGNO (SUBREG_REG (x));
1027
1028 if (REG_IN_TABLE (i) >= 0 && REG_IN_TABLE (i) != REG_TICK (i))
1029 {
1030 /* If REG_IN_TABLE (i) differs from REG_TICK (i) by one, and
1031 the last store to this register really stored into this
1032 subreg, then remove the memory of this subreg.
1033 Otherwise, remove any memory of the entire register and
1034 all its subregs from the table. */
1035 if (REG_TICK (i) - REG_IN_TABLE (i) > 1
1036 || SUBREG_TICKED (i) != REGNO (SUBREG_REG (x)))
1037 remove_invalid_refs (i);
1038 else
1039 remove_invalid_subreg_refs (i, SUBREG_BYTE (x), GET_MODE (x));
1040 }
1041
1042 REG_IN_TABLE (i) = REG_TICK (i);
1043 SUBREG_TICKED (i) = REGNO (SUBREG_REG (x));
1044 return 0;
1045 }
1046
1047 /* If X is a comparison or a COMPARE and either operand is a register
1048 that does not have a quantity, give it one. This is so that a later
1049 call to record_jump_equiv won't cause X to be assigned a different
1050 hash code and not found in the table after that call.
1051
1052 It is not necessary to do this here, since rehash_using_reg can
1053 fix up the table later, but doing this here eliminates the need to
1054 call that expensive function in the most common case where the only
1055 use of the register is in the comparison. */
1056
1057 if (code == COMPARE || COMPARISON_P (x))
1058 {
1059 if (REG_P (XEXP (x, 0))
1060 && ! REGNO_QTY_VALID_P (REGNO (XEXP (x, 0))))
1061 if (insert_regs (XEXP (x, 0), NULL, 0))
1062 {
1063 rehash_using_reg (XEXP (x, 0));
1064 changed = 1;
1065 }
1066
1067 if (REG_P (XEXP (x, 1))
1068 && ! REGNO_QTY_VALID_P (REGNO (XEXP (x, 1))))
1069 if (insert_regs (XEXP (x, 1), NULL, 0))
1070 {
1071 rehash_using_reg (XEXP (x, 1));
1072 changed = 1;
1073 }
1074 }
1075
1076 fmt = GET_RTX_FORMAT (code);
1077 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1078 if (fmt[i] == 'e')
1079 changed |= mention_regs (XEXP (x, i));
1080 else if (fmt[i] == 'E')
1081 for (j = 0; j < XVECLEN (x, i); j++)
1082 changed |= mention_regs (XVECEXP (x, i, j));
1083
1084 return changed;
1085}
1086
1087/* Update the register quantities for inserting X into the hash table
1088 with a value equivalent to CLASSP.
1089 (If the class does not contain a REG, it is irrelevant.)
1090 If MODIFIED is nonzero, X is a destination; it is being modified.
1091 Note that delete_reg_equiv should be called on a register
1092 before insert_regs is done on that register with MODIFIED != 0.
1093
1094 Nonzero value means that elements of reg_qty have changed
1095 so X's hash code may be different. */
1096
1097static int
1098insert_regs (rtx x, struct table_elt *classp, int modified)
1099{
1100 if (REG_P (x))
1101 {
1102 unsigned int regno = REGNO (x);
1103 int qty_valid;
1104
1105 /* If REGNO is in the equivalence table already but is of the
1106 wrong mode for that equivalence, don't do anything here. */
1107
1108 qty_valid = REGNO_QTY_VALID_P (regno);
1109 if (qty_valid)
1110 {
1111 struct qty_table_elem *ent = &qty_table[REG_QTY (regno)];
1112
1113 if (ent->mode != GET_MODE (x))
1114 return 0;
1115 }
1116
1117 if (modified || ! qty_valid)
1118 {
1119 if (classp)
1120 for (classp = classp->first_same_value;
1121 classp != 0;
1122 classp = classp->next_same_value)
1123 if (REG_P (classp->exp)
1124 && GET_MODE (classp->exp) == GET_MODE (x))
1125 {
1126 unsigned c_regno = REGNO (classp->exp);
1127
1128 gcc_assert (REGNO_QTY_VALID_P (c_regno));
1129
1130 /* Suppose that 5 is hard reg and 100 and 101 are
1131 pseudos. Consider
1132
1133 (set (reg:si 100) (reg:si 5))
1134 (set (reg:si 5) (reg:si 100))
1135 (set (reg:di 101) (reg:di 5))
1136
1137 We would now set REG_QTY (101) = REG_QTY (5), but the
1138 entry for 5 is in SImode. When we use this later in
1139 copy propagation, we get the register in wrong mode. */
1140 if (qty_table[REG_QTY (c_regno)].mode != GET_MODE (x))
1141 continue;
1142
1143 make_regs_eqv (regno, c_regno);
1144 return 1;
1145 }
1146
1147 /* Mention_regs for a SUBREG checks if REG_TICK is exactly one larger
1148 than REG_IN_TABLE to find out if there was only a single preceding
1149 invalidation - for the SUBREG - or another one, which would be
1150 for the full register. However, if we find here that REG_TICK
1151 indicates that the register is invalid, it means that it has
1152 been invalidated in a separate operation. The SUBREG might be used
1153 now (then this is a recursive call), or we might use the full REG
1154 now and a SUBREG of it later. So bump up REG_TICK so that
1155 mention_regs will do the right thing. */
1156 if (! modified
1157 && REG_IN_TABLE (regno) >= 0
1158 && REG_TICK (regno) == REG_IN_TABLE (regno) + 1)
1159 REG_TICK (regno)++;
1160 make_new_qty (regno, GET_MODE (x));
1161 return 1;
1162 }
1163
1164 return 0;
1165 }
1166
1167 /* If X is a SUBREG, we will likely be inserting the inner register in the
1168 table. If that register doesn't have an assigned quantity number at
1169 this point but does later, the insertion that we will be doing now will
1170 not be accessible because its hash code will have changed. So assign
1171 a quantity number now. */
1172
1173 else if (GET_CODE (x) == SUBREG && REG_P (SUBREG_REG (x))
1174 && ! REGNO_QTY_VALID_P (REGNO (SUBREG_REG (x))))
1175 {
1176 insert_regs (SUBREG_REG (x), NULL, 0);
1177 mention_regs (x);
1178 return 1;
1179 }
1180 else
1181 return mention_regs (x);
1182}
1183
1184
1185/* Compute upper and lower anchors for CST. Also compute the offset of CST
1186 from these anchors/bases such that *_BASE + *_OFFS = CST. Return false iff
1187 CST is equal to an anchor. */
1188
1189static bool
1190compute_const_anchors (rtx cst,
1191 HOST_WIDE_INT *lower_base, HOST_WIDE_INT *lower_offs,
1192 HOST_WIDE_INT *upper_base, HOST_WIDE_INT *upper_offs)
1193{
1194 HOST_WIDE_INT n = INTVAL (cst);
1195
1196 *lower_base = n & ~(targetm.const_anchor - 1);
1197 if (*lower_base == n)
1198 return false;
1199
1200 *upper_base =
1201 (n + (targetm.const_anchor - 1)) & ~(targetm.const_anchor - 1);
1202 *upper_offs = n - *upper_base;
1203 *lower_offs = n - *lower_base;
1204 return true;
1205}
1206
1207/* Insert the equivalence between ANCHOR and (REG + OFF) in mode MODE. */
1208
1209static void
1210insert_const_anchor (HOST_WIDE_INT anchor, rtx reg, HOST_WIDE_INT offs,
1211 machine_mode mode)
1212{
1213 struct table_elt *elt;
1214 unsigned hash;
1215 rtx anchor_exp;
1216 rtx exp;
1217
1218 anchor_exp = GEN_INT (anchor);
1219 hash = HASH (anchor_exp, mode);
1220 elt = lookup (anchor_exp, hash, mode);
1221 if (!elt)
1222 elt = insert (anchor_exp, NULL, hash, mode);
1223
1224 exp = plus_constant (mode, reg, offs);
1225 /* REG has just been inserted and the hash codes recomputed. */
1226 mention_regs (exp);
1227 hash = HASH (exp, mode);
1228
1229 /* Use the cost of the register rather than the whole expression. When
1230 looking up constant anchors we will further offset the corresponding
1231 expression therefore it does not make sense to prefer REGs over
1232 reg-immediate additions. Prefer instead the oldest expression. Also
1233 don't prefer pseudos over hard regs so that we derive constants in
1234 argument registers from other argument registers rather than from the
1235 original pseudo that was used to synthesize the constant. */
1236 insert_with_costs (exp, elt, hash, mode, COST (reg, mode), 1);
1237}
1238
1239/* The constant CST is equivalent to the register REG. Create
1240 equivalences between the two anchors of CST and the corresponding
1241 register-offset expressions using REG. */
1242
1243static void
1244insert_const_anchors (rtx reg, rtx cst, machine_mode mode)
1245{
1246 HOST_WIDE_INT lower_base, lower_offs, upper_base, upper_offs;
1247
1248 if (!compute_const_anchors (cst, &lower_base, &lower_offs,
1249 &upper_base, &upper_offs))
1250 return;
1251
1252 /* Ignore anchors of value 0. Constants accessible from zero are
1253 simple. */
1254 if (lower_base != 0)
1255 insert_const_anchor (lower_base, reg, -lower_offs, mode);
1256
1257 if (upper_base != 0)
1258 insert_const_anchor (upper_base, reg, -upper_offs, mode);
1259}
1260
1261/* We need to express ANCHOR_ELT->exp + OFFS. Walk the equivalence list of
1262 ANCHOR_ELT and see if offsetting any of the entries by OFFS would create a
1263 valid expression. Return the cheapest and oldest of such expressions. In
1264 *OLD, return how old the resulting expression is compared to the other
1265 equivalent expressions. */
1266
1267static rtx
1268find_reg_offset_for_const (struct table_elt *anchor_elt, HOST_WIDE_INT offs,
1269 unsigned *old)
1270{
1271 struct table_elt *elt;
1272 unsigned idx;
1273 struct table_elt *match_elt;
1274 rtx match;
1275
1276 /* Find the cheapest and *oldest* expression to maximize the chance of
1277 reusing the same pseudo. */
1278
1279 match_elt = NULL;
1280 match = NULL_RTX;
1281 for (elt = anchor_elt->first_same_value, idx = 0;
1282 elt;
1283 elt = elt->next_same_value, idx++)
1284 {
1285 if (match_elt && CHEAPER (match_elt, elt))
1286 return match;
1287
1288 if (REG_P (elt->exp)
1289 || (GET_CODE (elt->exp) == PLUS
1290 && REG_P (XEXP (elt->exp, 0))
1291 && GET_CODE (XEXP (elt->exp, 1)) == CONST_INT))
1292 {
1293 rtx x;
1294
1295 /* Ignore expressions that are no longer valid. */
1296 if (!REG_P (elt->exp) && !exp_equiv_p (elt->exp, elt->exp, 1, false))
1297 continue;
1298
1299 x = plus_constant (GET_MODE (elt->exp), elt->exp, offs);
1300 if (REG_P (x)
1301 || (GET_CODE (x) == PLUS
1302 && IN_RANGE (INTVAL (XEXP (x, 1)),
1303 -targetm.const_anchor,
1304 targetm.const_anchor - 1)))
1305 {
1306 match = x;
1307 match_elt = elt;
1308 *old = idx;
1309 }
1310 }
1311 }
1312
1313 return match;
1314}
1315
1316/* Try to express the constant SRC_CONST using a register+offset expression
1317 derived from a constant anchor. Return it if successful or NULL_RTX,
1318 otherwise. */
1319
1320static rtx
1321try_const_anchors (rtx src_const, machine_mode mode)
1322{
1323 struct table_elt *lower_elt, *upper_elt;
1324 HOST_WIDE_INT lower_base, lower_offs, upper_base, upper_offs;
1325 rtx lower_anchor_rtx, upper_anchor_rtx;
1326 rtx lower_exp = NULL_RTX, upper_exp = NULL_RTX;
1327 unsigned lower_old, upper_old;
1328
1329 /* CONST_INT is used for CC modes, but we should leave those alone. */
1330 if (GET_MODE_CLASS (mode) == MODE_CC)
1331 return NULL_RTX;
1332
1333 gcc_assert (SCALAR_INT_MODE_P (mode));
1334 if (!compute_const_anchors (src_const, &lower_base, &lower_offs,
1335 &upper_base, &upper_offs))
1336 return NULL_RTX;
1337
1338 lower_anchor_rtx = GEN_INT (lower_base);
1339 upper_anchor_rtx = GEN_INT (upper_base);
1340 lower_elt = lookup (lower_anchor_rtx, HASH (lower_anchor_rtx, mode), mode);
1341 upper_elt = lookup (upper_anchor_rtx, HASH (upper_anchor_rtx, mode), mode);
1342
1343 if (lower_elt)
1344 lower_exp = find_reg_offset_for_const (lower_elt, lower_offs, &lower_old);
1345 if (upper_elt)
1346 upper_exp = find_reg_offset_for_const (upper_elt, upper_offs, &upper_old);
1347
1348 if (!lower_exp)
1349 return upper_exp;
1350 if (!upper_exp)
1351 return lower_exp;
1352
1353 /* Return the older expression. */
1354 return (upper_old > lower_old ? upper_exp : lower_exp);
1355}
1356
1357/* Look in or update the hash table. */
1358
1359/* Remove table element ELT from use in the table.
1360 HASH is its hash code, made using the HASH macro.
1361 It's an argument because often that is known in advance
1362 and we save much time not recomputing it. */
1363
1364static void
1365remove_from_table (struct table_elt *elt, unsigned int hash)
1366{
1367 if (elt == 0)
1368 return;
1369
1370 /* Mark this element as removed. See cse_insn. */
1371 elt->first_same_value = 0;
1372
1373 /* Remove the table element from its equivalence class. */
1374
1375 {
1376 struct table_elt *prev = elt->prev_same_value;
1377 struct table_elt *next = elt->next_same_value;
1378
1379 if (next)
1380 next->prev_same_value = prev;
1381
1382 if (prev)
1383 prev->next_same_value = next;
1384 else
1385 {
1386 struct table_elt *newfirst = next;
1387 while (next)
1388 {
1389 next->first_same_value = newfirst;
1390 next = next->next_same_value;
1391 }
1392 }
1393 }
1394
1395 /* Remove the table element from its hash bucket. */
1396
1397 {
1398 struct table_elt *prev = elt->prev_same_hash;
1399 struct table_elt *next = elt->next_same_hash;
1400
1401 if (next)
1402 next->prev_same_hash = prev;
1403
1404 if (prev)
1405 prev->next_same_hash = next;
1406 else if (table[hash] == elt)
1407 table[hash] = next;
1408 else
1409 {
1410 /* This entry is not in the proper hash bucket. This can happen
1411 when two classes were merged by `merge_equiv_classes'. Search
1412 for the hash bucket that it heads. This happens only very
1413 rarely, so the cost is acceptable. */
1414 for (hash = 0; hash < HASH_SIZE; hash++)
1415 if (table[hash] == elt)
1416 table[hash] = next;
1417 }
1418 }
1419
1420 /* Remove the table element from its related-value circular chain. */
1421
1422 if (elt->related_value != 0 && elt->related_value != elt)
1423 {
1424 struct table_elt *p = elt->related_value;
1425
1426 while (p->related_value != elt)
1427 p = p->related_value;
1428 p->related_value = elt->related_value;
1429 if (p->related_value == p)
1430 p->related_value = 0;
1431 }
1432
1433 /* Now add it to the free element chain. */
1434 elt->next_same_hash = free_element_chain;
1435 free_element_chain = elt;
1436}
1437
1438/* Same as above, but X is a pseudo-register. */
1439
1440static void
1441remove_pseudo_from_table (rtx x, unsigned int hash)
1442{
1443 struct table_elt *elt;
1444
1445 /* Because a pseudo-register can be referenced in more than one
1446 mode, we might have to remove more than one table entry. */
1447 while ((elt = lookup_for_remove (x, hash, VOIDmode)))
1448 remove_from_table (elt, hash);
1449}
1450
1451/* Look up X in the hash table and return its table element,
1452 or 0 if X is not in the table.
1453
1454 MODE is the machine-mode of X, or if X is an integer constant
1455 with VOIDmode then MODE is the mode with which X will be used.
1456
1457 Here we are satisfied to find an expression whose tree structure
1458 looks like X. */
1459
1460static struct table_elt *
1461lookup (rtx x, unsigned int hash, machine_mode mode)
1462{
1463 struct table_elt *p;
1464
1465 for (p = table[hash]; p; p = p->next_same_hash)
1466 if (mode == p->mode && ((x == p->exp && REG_P (x))
1467 || exp_equiv_p (x, p->exp, !REG_P (x), false)))
1468 return p;
1469
1470 return 0;
1471}
1472
1473/* Like `lookup' but don't care whether the table element uses invalid regs.
1474 Also ignore discrepancies in the machine mode of a register. */
1475
1476static struct table_elt *
1477lookup_for_remove (rtx x, unsigned int hash, machine_mode mode)
1478{
1479 struct table_elt *p;
1480
1481 if (REG_P (x))
1482 {
1483 unsigned int regno = REGNO (x);
1484
1485 /* Don't check the machine mode when comparing registers;
1486 invalidating (REG:SI 0) also invalidates (REG:DF 0). */
1487 for (p = table[hash]; p; p = p->next_same_hash)
1488 if (REG_P (p->exp)
1489 && REGNO (p->exp) == regno)
1490 return p;
1491 }
1492 else
1493 {
1494 for (p = table[hash]; p; p = p->next_same_hash)
1495 if (mode == p->mode
1496 && (x == p->exp || exp_equiv_p (x, p->exp, 0, false)))
1497 return p;
1498 }
1499
1500 return 0;
1501}
1502
1503/* Look for an expression equivalent to X and with code CODE.
1504 If one is found, return that expression. */
1505
1506static rtx
1507lookup_as_function (rtx x, enum rtx_code code)
1508{
1509 struct table_elt *p
1510 = lookup (x, SAFE_HASH (x, VOIDmode), GET_MODE (x));
1511
1512 if (p == 0)
1513 return 0;
1514
1515 for (p = p->first_same_value; p; p = p->next_same_value)
1516 if (GET_CODE (p->exp) == code
1517 /* Make sure this is a valid entry in the table. */
1518 && exp_equiv_p (p->exp, p->exp, 1, false))
1519 return p->exp;
1520
1521 return 0;
1522}
1523
1524/* Insert X in the hash table, assuming HASH is its hash code and
1525 CLASSP is an element of the class it should go in (or 0 if a new
1526 class should be made). COST is the code of X and reg_cost is the
1527 cost of registers in X. It is inserted at the proper position to
1528 keep the class in the order cheapest first.
1529
1530 MODE is the machine-mode of X, or if X is an integer constant
1531 with VOIDmode then MODE is the mode with which X will be used.
1532
1533 For elements of equal cheapness, the most recent one
1534 goes in front, except that the first element in the list
1535 remains first unless a cheaper element is added. The order of
1536 pseudo-registers does not matter, as canon_reg will be called to
1537 find the cheapest when a register is retrieved from the table.
1538
1539 The in_memory field in the hash table element is set to 0.
1540 The caller must set it nonzero if appropriate.
1541
1542 You should call insert_regs (X, CLASSP, MODIFY) before calling here,
1543 and if insert_regs returns a nonzero value
1544 you must then recompute its hash code before calling here.
1545
1546 If necessary, update table showing constant values of quantities. */
1547
1548static struct table_elt *
1549insert_with_costs (rtx x, struct table_elt *classp, unsigned int hash,
1550 machine_mode mode, int cost, int reg_cost)
1551{
1552 struct table_elt *elt;
1553
1554 /* If X is a register and we haven't made a quantity for it,
1555 something is wrong. */
1556 gcc_assert (!REG_P (x) || REGNO_QTY_VALID_P (REGNO (x)));
1557
1558 /* If X is a hard register, show it is being put in the table. */
1559 if (REG_P (x) && REGNO (x) < FIRST_PSEUDO_REGISTER)
1560 add_to_hard_reg_set (&hard_regs_in_table, GET_MODE (x), REGNO (x));
1561
1562 /* Put an element for X into the right hash bucket. */
1563
1564 elt = free_element_chain;
1565 if (elt)
1566 free_element_chain = elt->next_same_hash;
1567 else
1568 elt = XNEW (struct table_elt);
1569
1570 elt->exp = x;
1571 elt->canon_exp = NULL_RTX;
1572 elt->cost = cost;
1573 elt->regcost = reg_cost;
1574 elt->next_same_value = 0;
1575 elt->prev_same_value = 0;
1576 elt->next_same_hash = table[hash];
1577 elt->prev_same_hash = 0;
1578 elt->related_value = 0;
1579 elt->in_memory = 0;
1580 elt->mode = mode;
1581 elt->is_const = (CONSTANT_P (x) || fixed_base_plus_p (x));
1582
1583 if (table[hash])
1584 table[hash]->prev_same_hash = elt;
1585 table[hash] = elt;
1586
1587 /* Put it into the proper value-class. */
1588 if (classp)
1589 {
1590 classp = classp->first_same_value;
1591 if (CHEAPER (elt, classp))
1592 /* Insert at the head of the class. */
1593 {
1594 struct table_elt *p;
1595 elt->next_same_value = classp;
1596 classp->prev_same_value = elt;
1597 elt->first_same_value = elt;
1598
1599 for (p = classp; p; p = p->next_same_value)
1600 p->first_same_value = elt;
1601 }
1602 else
1603 {
1604 /* Insert not at head of the class. */
1605 /* Put it after the last element cheaper than X. */
1606 struct table_elt *p, *next;
1607
1608 for (p = classp;
1609 (next = p->next_same_value) && CHEAPER (next, elt);
1610 p = next)
1611 ;
1612
1613 /* Put it after P and before NEXT. */
1614 elt->next_same_value = next;
1615 if (next)
1616 next->prev_same_value = elt;
1617
1618 elt->prev_same_value = p;
1619 p->next_same_value = elt;
1620 elt->first_same_value = classp;
1621 }
1622 }
1623 else
1624 elt->first_same_value = elt;
1625
1626 /* If this is a constant being set equivalent to a register or a register
1627 being set equivalent to a constant, note the constant equivalence.
1628
1629 If this is a constant, it cannot be equivalent to a different constant,
1630 and a constant is the only thing that can be cheaper than a register. So
1631 we know the register is the head of the class (before the constant was
1632 inserted).
1633
1634 If this is a register that is not already known equivalent to a
1635 constant, we must check the entire class.
1636
1637 If this is a register that is already known equivalent to an insn,
1638 update the qtys `const_insn' to show that `this_insn' is the latest
1639 insn making that quantity equivalent to the constant. */
1640
1641 if (elt->is_const && classp && REG_P (classp->exp)
1642 && !REG_P (x))
1643 {
1644 int exp_q = REG_QTY (REGNO (classp->exp));
1645 struct qty_table_elem *exp_ent = &qty_table[exp_q];
1646
1647 exp_ent->const_rtx = gen_lowpart (exp_ent->mode, x);
1648 exp_ent->const_insn = this_insn;
1649 }
1650
1651 else if (REG_P (x)
1652 && classp
1653 && ! qty_table[REG_QTY (REGNO (x))].const_rtx
1654 && ! elt->is_const)
1655 {
1656 struct table_elt *p;
1657
1658 for (p = classp; p != 0; p = p->next_same_value)
1659 {
1660 if (p->is_const && !REG_P (p->exp))
1661 {
1662 int x_q = REG_QTY (REGNO (x));
1663 struct qty_table_elem *x_ent = &qty_table[x_q];
1664
1665 x_ent->const_rtx
1666 = gen_lowpart (GET_MODE (x), p->exp);
1667 x_ent->const_insn = this_insn;
1668 break;
1669 }
1670 }
1671 }
1672
1673 else if (REG_P (x)
1674 && qty_table[REG_QTY (REGNO (x))].const_rtx
1675 && GET_MODE (x) == qty_table[REG_QTY (REGNO (x))].mode)
1676 qty_table[REG_QTY (REGNO (x))].const_insn = this_insn;
1677
1678 /* If this is a constant with symbolic value,
1679 and it has a term with an explicit integer value,
1680 link it up with related expressions. */
1681 if (GET_CODE (x) == CONST)
1682 {
1683 rtx subexp = get_related_value (x);
1684 unsigned subhash;
1685 struct table_elt *subelt, *subelt_prev;
1686
1687 if (subexp != 0)
1688 {
1689 /* Get the integer-free subexpression in the hash table. */
1690 subhash = SAFE_HASH (subexp, mode);
1691 subelt = lookup (subexp, subhash, mode);
1692 if (subelt == 0)
1693 subelt = insert (subexp, NULL, subhash, mode);
1694 /* Initialize SUBELT's circular chain if it has none. */
1695 if (subelt->related_value == 0)
1696 subelt->related_value = subelt;
1697 /* Find the element in the circular chain that precedes SUBELT. */
1698 subelt_prev = subelt;
1699 while (subelt_prev->related_value != subelt)
1700 subelt_prev = subelt_prev->related_value;
1701 /* Put new ELT into SUBELT's circular chain just before SUBELT.
1702 This way the element that follows SUBELT is the oldest one. */
1703 elt->related_value = subelt_prev->related_value;
1704 subelt_prev->related_value = elt;
1705 }
1706 }
1707
1708 return elt;
1709}
1710
1711/* Wrap insert_with_costs by passing the default costs. */
1712
1713static struct table_elt *
1714insert (rtx x, struct table_elt *classp, unsigned int hash,
1715 machine_mode mode)
1716{
1717 return insert_with_costs (x, classp, hash, mode,
1718 COST (x, mode), approx_reg_cost (x));
1719}
1720
1721
1722/* Given two equivalence classes, CLASS1 and CLASS2, put all the entries from
1723 CLASS2 into CLASS1. This is done when we have reached an insn which makes
1724 the two classes equivalent.
1725
1726 CLASS1 will be the surviving class; CLASS2 should not be used after this
1727 call.
1728
1729 Any invalid entries in CLASS2 will not be copied. */
1730
1731static void
1732merge_equiv_classes (struct table_elt *class1, struct table_elt *class2)
1733{
1734 struct table_elt *elt, *next, *new_elt;
1735
1736 /* Ensure we start with the head of the classes. */
1737 class1 = class1->first_same_value;
1738 class2 = class2->first_same_value;
1739
1740 /* If they were already equal, forget it. */
1741 if (class1 == class2)
1742 return;
1743
1744 for (elt = class2; elt; elt = next)
1745 {
1746 unsigned int hash;
1747 rtx exp = elt->exp;
1748 machine_mode mode = elt->mode;
1749
1750 next = elt->next_same_value;
1751
1752 /* Remove old entry, make a new one in CLASS1's class.
1753 Don't do this for invalid entries as we cannot find their
1754 hash code (it also isn't necessary). */
1755 if (REG_P (exp) || exp_equiv_p (exp, exp, 1, false))
1756 {
1757 bool need_rehash = false;
1758
1759 hash_arg_in_memory = 0;
1760 hash = HASH (exp, mode);
1761
1762 if (REG_P (exp))
1763 {
1764 need_rehash = REGNO_QTY_VALID_P (REGNO (exp));
1765 delete_reg_equiv (REGNO (exp));
1766 }
1767
1768 if (REG_P (exp) && REGNO (exp) >= FIRST_PSEUDO_REGISTER)
1769 remove_pseudo_from_table (exp, hash);
1770 else
1771 remove_from_table (elt, hash);
1772
1773 if (insert_regs (exp, class1, 0) || need_rehash)
1774 {
1775 rehash_using_reg (exp);
1776 hash = HASH (exp, mode);
1777 }
1778 new_elt = insert (exp, class1, hash, mode);
1779 new_elt->in_memory = hash_arg_in_memory;
1780 if (GET_CODE (exp) == ASM_OPERANDS && elt->cost == MAX_COST)
1781 new_elt->cost = MAX_COST;
1782 }
1783 }
1784}
1785
1786/* Flush the entire hash table. */
1787
1788static void
1789flush_hash_table (void)
1790{
1791 int i;
1792 struct table_elt *p;
1793
1794 for (i = 0; i < HASH_SIZE; i++)
1795 for (p = table[i]; p; p = table[i])
1796 {
1797 /* Note that invalidate can remove elements
1798 after P in the current hash chain. */
1799 if (REG_P (p->exp))
1800 invalidate (p->exp, VOIDmode);
1801 else
1802 remove_from_table (p, i);
1803 }
1804}
1805
1806/* Check whether an anti dependence exists between X and EXP. MODE and
1807 ADDR are as for canon_anti_dependence. */
1808
1809static bool
1810check_dependence (const_rtx x, rtx exp, machine_mode mode, rtx addr)
1811{
1812 subrtx_iterator::array_type array;
1813 FOR_EACH_SUBRTX (iter, array, x, NONCONST)
1814 {
1815 const_rtx x = *iter;
1816 if (MEM_P (x) && canon_anti_dependence (x, true, exp, mode, addr))
1817 return true;
1818 }
1819 return false;
1820}
1821
1822/* Remove from the hash table, or mark as invalid, all expressions whose
1823 values could be altered by storing in X. X is a register, a subreg, or
1824 a memory reference with nonvarying address (because, when a memory
1825 reference with a varying address is stored in, all memory references are
1826 removed by invalidate_memory so specific invalidation is superfluous).
1827 FULL_MODE, if not VOIDmode, indicates that this much should be
1828 invalidated instead of just the amount indicated by the mode of X. This
1829 is only used for bitfield stores into memory.
1830
1831 A nonvarying address may be just a register or just a symbol reference,
1832 or it may be either of those plus a numeric offset. */
1833
1834static void
1835invalidate (rtx x, machine_mode full_mode)
1836{
1837 int i;
1838 struct table_elt *p;
1839 rtx addr;
1840
1841 switch (GET_CODE (x))
1842 {
1843 case REG:
1844 {
1845 /* If X is a register, dependencies on its contents are recorded
1846 through the qty number mechanism. Just change the qty number of
1847 the register, mark it as invalid for expressions that refer to it,
1848 and remove it itself. */
1849 unsigned int regno = REGNO (x);
1850 unsigned int hash = HASH (x, GET_MODE (x));
1851
1852 /* Remove REGNO from any quantity list it might be on and indicate
1853 that its value might have changed. If it is a pseudo, remove its
1854 entry from the hash table.
1855
1856 For a hard register, we do the first two actions above for any
1857 additional hard registers corresponding to X. Then, if any of these
1858 registers are in the table, we must remove any REG entries that
1859 overlap these registers. */
1860
1861 delete_reg_equiv (regno);
1862 REG_TICK (regno)++;
1863 SUBREG_TICKED (regno) = -1;
1864
1865 if (regno >= FIRST_PSEUDO_REGISTER)
1866 remove_pseudo_from_table (x, hash);
1867 else
1868 {
1869 HOST_WIDE_INT in_table
1870 = TEST_HARD_REG_BIT (hard_regs_in_table, regno);
1871 unsigned int endregno = END_REGNO (x);
1872 unsigned int tregno, tendregno, rn;
1873 struct table_elt *p, *next;
1874
1875 CLEAR_HARD_REG_BIT (hard_regs_in_table, regno);
1876
1877 for (rn = regno + 1; rn < endregno; rn++)
1878 {
1879 in_table |= TEST_HARD_REG_BIT (hard_regs_in_table, rn);
1880 CLEAR_HARD_REG_BIT (hard_regs_in_table, rn);
1881 delete_reg_equiv (rn);
1882 REG_TICK (rn)++;
1883 SUBREG_TICKED (rn) = -1;
1884 }
1885
1886 if (in_table)
1887 for (hash = 0; hash < HASH_SIZE; hash++)
1888 for (p = table[hash]; p; p = next)
1889 {
1890 next = p->next_same_hash;
1891
1892 if (!REG_P (p->exp)
1893 || REGNO (p->exp) >= FIRST_PSEUDO_REGISTER)
1894 continue;
1895
1896 tregno = REGNO (p->exp);
1897 tendregno = END_REGNO (p->exp);
1898 if (tendregno > regno && tregno < endregno)
1899 remove_from_table (p, hash);
1900 }
1901 }
1902 }
1903 return;
1904
1905 case SUBREG:
1906 invalidate (SUBREG_REG (x), VOIDmode);
1907 return;
1908
1909 case PARALLEL:
1910 for (i = XVECLEN (x, 0) - 1; i >= 0; --i)
1911 invalidate (XVECEXP (x, 0, i), VOIDmode);
1912 return;
1913
1914 case EXPR_LIST:
1915 /* This is part of a disjoint return value; extract the location in
1916 question ignoring the offset. */
1917 invalidate (XEXP (x, 0), VOIDmode);
1918 return;
1919
1920 case MEM:
1921 addr = canon_rtx (get_addr (XEXP (x, 0)));
1922 /* Calculate the canonical version of X here so that
1923 true_dependence doesn't generate new RTL for X on each call. */
1924 x = canon_rtx (x);
1925
1926 /* Remove all hash table elements that refer to overlapping pieces of
1927 memory. */
1928 if (full_mode == VOIDmode)
1929 full_mode = GET_MODE (x);
1930
1931 for (i = 0; i < HASH_SIZE; i++)
1932 {
1933 struct table_elt *next;
1934
1935 for (p = table[i]; p; p = next)
1936 {
1937 next = p->next_same_hash;
1938 if (p->in_memory)
1939 {
1940 /* Just canonicalize the expression once;
1941 otherwise each time we call invalidate
1942 true_dependence will canonicalize the
1943 expression again. */
1944 if (!p->canon_exp)
1945 p->canon_exp = canon_rtx (p->exp);
1946 if (check_dependence (p->canon_exp, x, full_mode, addr))
1947 remove_from_table (p, i);
1948 }
1949 }
1950 }
1951 return;
1952
1953 default:
1954 gcc_unreachable ();
1955 }
1956}
1957
1958/* Invalidate DEST. Used when DEST is not going to be added
1959 into the hash table for some reason, e.g. do_not_record
1960 flagged on it. */
1961
1962static void
1963invalidate_dest (rtx dest)
1964{
1965 if (REG_P (dest)
1966 || GET_CODE (dest) == SUBREG
1967 || MEM_P (dest))
1968 invalidate (dest, VOIDmode);
1969 else if (GET_CODE (dest) == STRICT_LOW_PART
1970 || GET_CODE (dest) == ZERO_EXTRACT)
1971 invalidate (XEXP (dest, 0), GET_MODE (dest));
1972}
1973
1974/* Remove all expressions that refer to register REGNO,
1975 since they are already invalid, and we are about to
1976 mark that register valid again and don't want the old
1977 expressions to reappear as valid. */
1978
1979static void
1980remove_invalid_refs (unsigned int regno)
1981{
1982 unsigned int i;
1983 struct table_elt *p, *next;
1984
1985 for (i = 0; i < HASH_SIZE; i++)
1986 for (p = table[i]; p; p = next)
1987 {
1988 next = p->next_same_hash;
1989 if (!REG_P (p->exp) && refers_to_regno_p (regno, p->exp))
1990 remove_from_table (p, i);
1991 }
1992}
1993
1994/* Likewise for a subreg with subreg_reg REGNO, subreg_byte OFFSET,
1995 and mode MODE. */
1996static void
1997remove_invalid_subreg_refs (unsigned int regno, unsigned int offset,
1998 machine_mode mode)
1999{
2000 unsigned int i;
2001 struct table_elt *p, *next;
2002 unsigned int end = offset + (GET_MODE_SIZE (mode) - 1);
2003
2004 for (i = 0; i < HASH_SIZE; i++)
2005 for (p = table[i]; p; p = next)
2006 {
2007 rtx exp = p->exp;
2008 next = p->next_same_hash;
2009
2010 if (!REG_P (exp)
2011 && (GET_CODE (exp) != SUBREG
2012 || !REG_P (SUBREG_REG (exp))
2013 || REGNO (SUBREG_REG (exp)) != regno
2014 || (((SUBREG_BYTE (exp)
2015 + (GET_MODE_SIZE (GET_MODE (exp)) - 1)) >= offset)
2016 && SUBREG_BYTE (exp) <= end))
2017 && refers_to_regno_p (regno, p->exp))
2018 remove_from_table (p, i);
2019 }
2020}
2021
2022/* Recompute the hash codes of any valid entries in the hash table that
2023 reference X, if X is a register, or SUBREG_REG (X) if X is a SUBREG.
2024
2025 This is called when we make a jump equivalence. */
2026
2027static void
2028rehash_using_reg (rtx x)
2029{
2030 unsigned int i;
2031 struct table_elt *p, *next;
2032 unsigned hash;
2033
2034 if (GET_CODE (x) == SUBREG)
2035 x = SUBREG_REG (x);
2036
2037 /* If X is not a register or if the register is known not to be in any
2038 valid entries in the table, we have no work to do. */
2039
2040 if (!REG_P (x)
2041 || REG_IN_TABLE (REGNO (x)) < 0
2042 || REG_IN_TABLE (REGNO (x)) != REG_TICK (REGNO (x)))
2043 return;
2044
2045 /* Scan all hash chains looking for valid entries that mention X.
2046 If we find one and it is in the wrong hash chain, move it. */
2047
2048 for (i = 0; i < HASH_SIZE; i++)
2049 for (p = table[i]; p; p = next)
2050 {
2051 next = p->next_same_hash;
2052 if (reg_mentioned_p (x, p->exp)
2053 && exp_equiv_p (p->exp, p->exp, 1, false)
2054 && i != (hash = SAFE_HASH (p->exp, p->mode)))
2055 {
2056 if (p->next_same_hash)
2057 p->next_same_hash->prev_same_hash = p->prev_same_hash;
2058
2059 if (p->prev_same_hash)
2060 p->prev_same_hash->next_same_hash = p->next_same_hash;
2061 else
2062 table[i] = p->next_same_hash;
2063
2064 p->next_same_hash = table[hash];
2065 p->prev_same_hash = 0;
2066 if (table[hash])
2067 table[hash]->prev_same_hash = p;
2068 table[hash] = p;
2069 }
2070 }
2071}
2072
2073/* Remove from the hash table any expression that is a call-clobbered
2074 register. Also update their TICK values. */
2075
2076static void
2077invalidate_for_call (void)
2078{
2079 unsigned int regno, endregno;
2080 unsigned int i;
2081 unsigned hash;
2082 struct table_elt *p, *next;
2083 int in_table = 0;
2084 hard_reg_set_iterator hrsi;
2085
2086 /* Go through all the hard registers. For each that is clobbered in
2087 a CALL_INSN, remove the register from quantity chains and update
2088 reg_tick if defined. Also see if any of these registers is currently
2089 in the table. */
2090 EXECUTE_IF_SET_IN_HARD_REG_SET (regs_invalidated_by_call, 0, regno, hrsi)
2091 {
2092 delete_reg_equiv (regno);
2093 if (REG_TICK (regno) >= 0)
2094 {
2095 REG_TICK (regno)++;
2096 SUBREG_TICKED (regno) = -1;
2097 }
2098 in_table |= (TEST_HARD_REG_BIT (hard_regs_in_table, regno) != 0);
2099 }
2100
2101 /* In the case where we have no call-clobbered hard registers in the
2102 table, we are done. Otherwise, scan the table and remove any
2103 entry that overlaps a call-clobbered register. */
2104
2105 if (in_table)
2106 for (hash = 0; hash < HASH_SIZE; hash++)
2107 for (p = table[hash]; p; p = next)
2108 {
2109 next = p->next_same_hash;
2110
2111 if (!REG_P (p->exp)
2112 || REGNO (p->exp) >= FIRST_PSEUDO_REGISTER)
2113 continue;
2114
2115 regno = REGNO (p->exp);
2116 endregno = END_REGNO (p->exp);
2117
2118 for (i = regno; i < endregno; i++)
2119 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
2120 {
2121 remove_from_table (p, hash);
2122 break;
2123 }
2124 }
2125}
2126
2127/* Given an expression X of type CONST,
2128 and ELT which is its table entry (or 0 if it
2129 is not in the hash table),
2130 return an alternate expression for X as a register plus integer.
2131 If none can be found, return 0. */
2132
2133static rtx
2134use_related_value (rtx x, struct table_elt *elt)
2135{
2136 struct table_elt *relt = 0;
2137 struct table_elt *p, *q;
2138 HOST_WIDE_INT offset;
2139
2140 /* First, is there anything related known?
2141 If we have a table element, we can tell from that.
2142 Otherwise, must look it up. */
2143
2144 if (elt != 0 && elt->related_value != 0)
2145 relt = elt;
2146 else if (elt == 0 && GET_CODE (x) == CONST)
2147 {
2148 rtx subexp = get_related_value (x);
2149 if (subexp != 0)
2150 relt = lookup (subexp,
2151 SAFE_HASH (subexp, GET_MODE (subexp)),
2152 GET_MODE (subexp));
2153 }
2154
2155 if (relt == 0)
2156 return 0;
2157
2158 /* Search all related table entries for one that has an
2159 equivalent register. */
2160
2161 p = relt;
2162 while (1)
2163 {
2164 /* This loop is strange in that it is executed in two different cases.
2165 The first is when X is already in the table. Then it is searching
2166 the RELATED_VALUE list of X's class (RELT). The second case is when
2167 X is not in the table. Then RELT points to a class for the related
2168 value.
2169
2170 Ensure that, whatever case we are in, that we ignore classes that have
2171 the same value as X. */
2172
2173 if (rtx_equal_p (x, p->exp))
2174 q = 0;
2175 else
2176 for (q = p->first_same_value; q; q = q->next_same_value)
2177 if (REG_P (q->exp))
2178 break;
2179
2180 if (q)
2181 break;
2182
2183 p = p->related_value;
2184
2185 /* We went all the way around, so there is nothing to be found.
2186 Alternatively, perhaps RELT was in the table for some other reason
2187 and it has no related values recorded. */
2188 if (p == relt || p == 0)
2189 break;
2190 }
2191
2192 if (q == 0)
2193 return 0;
2194
2195 offset = (get_integer_term (x) - get_integer_term (p->exp));
2196 /* Note: OFFSET may be 0 if P->xexp and X are related by commutativity. */
2197 return plus_constant (q->mode, q->exp, offset);
2198}
2199
2200
2201/* Hash a string. Just add its bytes up. */
2202static inline unsigned
2203hash_rtx_string (const char *ps)
2204{
2205 unsigned hash = 0;
2206 const unsigned char *p = (const unsigned char *) ps;
2207
2208 if (p)
2209 while (*p)
2210 hash += *p++;
2211
2212 return hash;
2213}
2214
2215/* Same as hash_rtx, but call CB on each rtx if it is not NULL.
2216 When the callback returns true, we continue with the new rtx. */
2217
2218unsigned
2219hash_rtx_cb (const_rtx x, machine_mode mode,
2220 int *do_not_record_p, int *hash_arg_in_memory_p,
2221 bool have_reg_qty, hash_rtx_callback_function cb)
2222{
2223 int i, j;
2224 unsigned hash = 0;
2225 enum rtx_code code;
2226 const char *fmt;
2227 machine_mode newmode;
2228 rtx newx;
2229
2230 /* Used to turn recursion into iteration. We can't rely on GCC's
2231 tail-recursion elimination since we need to keep accumulating values
2232 in HASH. */
2233 repeat:
2234 if (x == 0)
2235 return hash;
2236
2237 /* Invoke the callback first. */
2238 if (cb != NULL
2239 && ((*cb) (x, mode, &newx, &newmode)))
2240 {
2241 hash += hash_rtx_cb (newx, newmode, do_not_record_p,
2242 hash_arg_in_memory_p, have_reg_qty, cb);
2243 return hash;
2244 }
2245
2246 code = GET_CODE (x);
2247 switch (code)
2248 {
2249 case REG:
2250 {
2251 unsigned int regno = REGNO (x);
2252
2253 if (do_not_record_p && !reload_completed)
2254 {
2255 /* On some machines, we can't record any non-fixed hard register,
2256 because extending its life will cause reload problems. We
2257 consider ap, fp, sp, gp to be fixed for this purpose.
2258
2259 We also consider CCmode registers to be fixed for this purpose;
2260 failure to do so leads to failure to simplify 0<100 type of
2261 conditionals.
2262
2263 On all machines, we can't record any global registers.
2264 Nor should we record any register that is in a small
2265 class, as defined by TARGET_CLASS_LIKELY_SPILLED_P. */
2266 bool record;
2267
2268 if (regno >= FIRST_PSEUDO_REGISTER)
2269 record = true;
2270 else if (x == frame_pointer_rtx
2271 || x == hard_frame_pointer_rtx
2272 || x == arg_pointer_rtx
2273 || x == stack_pointer_rtx
2274 || x == pic_offset_table_rtx)
2275 record = true;
2276 else if (global_regs[regno])
2277 record = false;
2278 else if (fixed_regs[regno])
2279 record = true;
2280 else if (GET_MODE_CLASS (GET_MODE (x)) == MODE_CC)
2281 record = true;
2282 else if (targetm.small_register_classes_for_mode_p (GET_MODE (x)))
2283 record = false;
2284 else if (targetm.class_likely_spilled_p (REGNO_REG_CLASS (regno)))
2285 record = false;
2286 else
2287 record = true;
2288
2289 if (!record)
2290 {
2291 *do_not_record_p = 1;
2292 return 0;
2293 }
2294 }
2295
2296 hash += ((unsigned int) REG << 7);
2297 hash += (have_reg_qty ? (unsigned) REG_QTY (regno) : regno);
2298 return hash;
2299 }
2300
2301 /* We handle SUBREG of a REG specially because the underlying
2302 reg changes its hash value with every value change; we don't
2303 want to have to forget unrelated subregs when one subreg changes. */
2304 case SUBREG:
2305 {
2306 if (REG_P (SUBREG_REG (x)))
2307 {
2308 hash += (((unsigned int) SUBREG << 7)
2309 + REGNO (SUBREG_REG (x))
2310 + (SUBREG_BYTE (x) / UNITS_PER_WORD));
2311 return hash;
2312 }
2313 break;
2314 }
2315
2316 case CONST_INT:
2317 hash += (((unsigned int) CONST_INT << 7) + (unsigned int) mode
2318 + (unsigned int) INTVAL (x));
2319 return hash;
2320
2321 case CONST_WIDE_INT:
2322 for (i = 0; i < CONST_WIDE_INT_NUNITS (x); i++)
2323 hash += CONST_WIDE_INT_ELT (x, i);
2324 return hash;
2325
2326 case CONST_DOUBLE:
2327 /* This is like the general case, except that it only counts
2328 the integers representing the constant. */
2329 hash += (unsigned int) code + (unsigned int) GET_MODE (x);
2330 if (TARGET_SUPPORTS_WIDE_INT == 0 && GET_MODE (x) == VOIDmode)
2331 hash += ((unsigned int) CONST_DOUBLE_LOW (x)
2332 + (unsigned int) CONST_DOUBLE_HIGH (x));
2333 else
2334 hash += real_hash (CONST_DOUBLE_REAL_VALUE (x));
2335 return hash;
2336
2337 case CONST_FIXED:
2338 hash += (unsigned int) code + (unsigned int) GET_MODE (x);
2339 hash += fixed_hash (CONST_FIXED_VALUE (x));
2340 return hash;
2341
2342 case CONST_VECTOR:
2343 {
2344 int units;
2345 rtx elt;
2346
2347 units = CONST_VECTOR_NUNITS (x);
2348
2349 for (i = 0; i < units; ++i)
2350 {
2351 elt = CONST_VECTOR_ELT (x, i);
2352 hash += hash_rtx_cb (elt, GET_MODE (elt),
2353 do_not_record_p, hash_arg_in_memory_p,
2354 have_reg_qty, cb);
2355 }
2356
2357 return hash;
2358 }
2359
2360 /* Assume there is only one rtx object for any given label. */
2361 case LABEL_REF:
2362 /* We don't hash on the address of the CODE_LABEL to avoid bootstrap
2363 differences and differences between each stage's debugging dumps. */
2364 hash += (((unsigned int) LABEL_REF << 7)
2365 + CODE_LABEL_NUMBER (label_ref_label (x)));
2366 return hash;
2367
2368 case SYMBOL_REF:
2369 {
2370 /* Don't hash on the symbol's address to avoid bootstrap differences.
2371 Different hash values may cause expressions to be recorded in
2372 different orders and thus different registers to be used in the
2373 final assembler. This also avoids differences in the dump files
2374 between various stages. */
2375 unsigned int h = 0;
2376 const unsigned char *p = (const unsigned char *) XSTR (x, 0);
2377
2378 while (*p)
2379 h += (h << 7) + *p++; /* ??? revisit */
2380
2381 hash += ((unsigned int) SYMBOL_REF << 7) + h;
2382 return hash;
2383 }
2384
2385 case MEM:
2386 /* We don't record if marked volatile or if BLKmode since we don't
2387 know the size of the move. */
2388 if (do_not_record_p && (MEM_VOLATILE_P (x) || GET_MODE (x) == BLKmode))
2389 {
2390 *do_not_record_p = 1;
2391 return 0;
2392 }
2393 if (hash_arg_in_memory_p && !MEM_READONLY_P (x))
2394 *hash_arg_in_memory_p = 1;
2395
2396 /* Now that we have already found this special case,
2397 might as well speed it up as much as possible. */
2398 hash += (unsigned) MEM;
2399 x = XEXP (x, 0);
2400 goto repeat;
2401
2402 case USE:
2403 /* A USE that mentions non-volatile memory needs special
2404 handling since the MEM may be BLKmode which normally
2405 prevents an entry from being made. Pure calls are
2406 marked by a USE which mentions BLKmode memory.
2407 See calls.c:emit_call_1. */
2408 if (MEM_P (XEXP (x, 0))
2409 && ! MEM_VOLATILE_P (XEXP (x, 0)))
2410 {
2411 hash += (unsigned) USE;
2412 x = XEXP (x, 0);
2413
2414 if (hash_arg_in_memory_p && !MEM_READONLY_P (x))
2415 *hash_arg_in_memory_p = 1;
2416
2417 /* Now that we have already found this special case,
2418 might as well speed it up as much as possible. */
2419 hash += (unsigned) MEM;
2420 x = XEXP (x, 0);
2421 goto repeat;
2422 }
2423 break;
2424
2425 case PRE_DEC:
2426 case PRE_INC:
2427 case POST_DEC:
2428 case POST_INC:
2429 case PRE_MODIFY:
2430 case POST_MODIFY:
2431 case PC:
2432 case CC0:
2433 case CALL:
2434 case UNSPEC_VOLATILE:
2435 if (do_not_record_p) {
2436 *do_not_record_p = 1;
2437 return 0;
2438 }
2439 else
2440 return hash;
2441 break;
2442
2443 case ASM_OPERANDS:
2444 if (do_not_record_p && MEM_VOLATILE_P (x))
2445 {
2446 *do_not_record_p = 1;
2447 return 0;
2448 }
2449 else
2450 {
2451 /* We don't want to take the filename and line into account. */
2452 hash += (unsigned) code + (unsigned) GET_MODE (x)
2453 + hash_rtx_string (ASM_OPERANDS_TEMPLATE (x))
2454 + hash_rtx_string (ASM_OPERANDS_OUTPUT_CONSTRAINT (x))
2455 + (unsigned) ASM_OPERANDS_OUTPUT_IDX (x);
2456
2457 if (ASM_OPERANDS_INPUT_LENGTH (x))
2458 {
2459 for (i = 1; i < ASM_OPERANDS_INPUT_LENGTH (x); i++)
2460 {
2461 hash += (hash_rtx_cb (ASM_OPERANDS_INPUT (x, i),
2462 GET_MODE (ASM_OPERANDS_INPUT (x, i)),
2463 do_not_record_p, hash_arg_in_memory_p,
2464 have_reg_qty, cb)
2465 + hash_rtx_string
2466 (ASM_OPERANDS_INPUT_CONSTRAINT (x, i)));
2467 }
2468
2469 hash += hash_rtx_string (ASM_OPERANDS_INPUT_CONSTRAINT (x, 0));
2470 x = ASM_OPERANDS_INPUT (x, 0);
2471 mode = GET_MODE (x);
2472 goto repeat;
2473 }
2474
2475 return hash;
2476 }
2477 break;
2478
2479 default:
2480 break;
2481 }
2482
2483 i = GET_RTX_LENGTH (code) - 1;
2484 hash += (unsigned) code + (unsigned) GET_MODE (x);
2485 fmt = GET_RTX_FORMAT (code);
2486 for (; i >= 0; i--)
2487 {
2488 switch (fmt[i])
2489 {
2490 case 'e':
2491 /* If we are about to do the last recursive call
2492 needed at this level, change it into iteration.
2493 This function is called enough to be worth it. */
2494 if (i == 0)
2495 {
2496 x = XEXP (x, i);
2497 goto repeat;
2498 }
2499
2500 hash += hash_rtx_cb (XEXP (x, i), VOIDmode, do_not_record_p,
2501 hash_arg_in_memory_p,
2502 have_reg_qty, cb);
2503 break;
2504
2505 case 'E':
2506 for (j = 0; j < XVECLEN (x, i); j++)
2507 hash += hash_rtx_cb (XVECEXP (x, i, j), VOIDmode, do_not_record_p,
2508 hash_arg_in_memory_p,
2509 have_reg_qty, cb);
2510 break;
2511
2512 case 's':
2513 hash += hash_rtx_string (XSTR (x, i));
2514 break;
2515
2516 case 'i':
2517 hash += (unsigned int) XINT (x, i);
2518 break;
2519
2520 case '0': case 't':
2521 /* Unused. */
2522 break;
2523
2524 default:
2525 gcc_unreachable ();
2526 }
2527 }
2528
2529 return hash;
2530}
2531
2532/* Hash an rtx. We are careful to make sure the value is never negative.
2533 Equivalent registers hash identically.
2534 MODE is used in hashing for CONST_INTs only;
2535 otherwise the mode of X is used.
2536
2537 Store 1 in DO_NOT_RECORD_P if any subexpression is volatile.
2538
2539 If HASH_ARG_IN_MEMORY_P is not NULL, store 1 in it if X contains
2540 a MEM rtx which does not have the MEM_READONLY_P flag set.
2541
2542 Note that cse_insn knows that the hash code of a MEM expression
2543 is just (int) MEM plus the hash code of the address. */
2544
2545unsigned
2546hash_rtx (const_rtx x, machine_mode mode, int *do_not_record_p,
2547 int *hash_arg_in_memory_p, bool have_reg_qty)
2548{
2549 return hash_rtx_cb (x, mode, do_not_record_p,
2550 hash_arg_in_memory_p, have_reg_qty, NULL);
2551}
2552
2553/* Hash an rtx X for cse via hash_rtx.
2554 Stores 1 in do_not_record if any subexpression is volatile.
2555 Stores 1 in hash_arg_in_memory if X contains a mem rtx which
2556 does not have the MEM_READONLY_P flag set. */
2557
2558static inline unsigned
2559canon_hash (rtx x, machine_mode mode)
2560{
2561 return hash_rtx (x, mode, &do_not_record, &hash_arg_in_memory, true);
2562}
2563
2564/* Like canon_hash but with no side effects, i.e. do_not_record
2565 and hash_arg_in_memory are not changed. */
2566
2567static inline unsigned
2568safe_hash (rtx x, machine_mode mode)
2569{
2570 int dummy_do_not_record;
2571 return hash_rtx (x, mode, &dummy_do_not_record, NULL, true);
2572}
2573
2574/* Return 1 iff X and Y would canonicalize into the same thing,
2575 without actually constructing the canonicalization of either one.
2576 If VALIDATE is nonzero,
2577 we assume X is an expression being processed from the rtl
2578 and Y was found in the hash table. We check register refs
2579 in Y for being marked as valid.
2580
2581 If FOR_GCSE is true, we compare X and Y for equivalence for GCSE. */
2582
2583int
2584exp_equiv_p (const_rtx x, const_rtx y, int validate, bool for_gcse)
2585{
2586 int i, j;
2587 enum rtx_code code;
2588 const char *fmt;
2589
2590 /* Note: it is incorrect to assume an expression is equivalent to itself
2591 if VALIDATE is nonzero. */
2592 if (x == y && !validate)
2593 return 1;
2594
2595 if (x == 0 || y == 0)
2596 return x == y;
2597
2598 code = GET_CODE (x);
2599 if (code != GET_CODE (y))
2600 return 0;
2601
2602 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. */
2603 if (GET_MODE (x) != GET_MODE (y))
2604 return 0;
2605
2606 /* MEMs referring to different address space are not equivalent. */
2607 if (code == MEM && MEM_ADDR_SPACE (x) != MEM_ADDR_SPACE (y))
2608 return 0;
2609
2610 switch (code)
2611 {
2612 case PC:
2613 case CC0:
2614 CASE_CONST_UNIQUE:
2615 return x == y;
2616
2617 case LABEL_REF:
2618 return label_ref_label (x) == label_ref_label (y);
2619
2620 case SYMBOL_REF:
2621 return XSTR (x, 0) == XSTR (y, 0);
2622
2623 case REG:
2624 if (for_gcse)
2625 return REGNO (x) == REGNO (y);
2626 else
2627 {
2628 unsigned int regno = REGNO (y);
2629 unsigned int i;
2630 unsigned int endregno = END_REGNO (y);
2631
2632 /* If the quantities are not the same, the expressions are not
2633 equivalent. If there are and we are not to validate, they
2634 are equivalent. Otherwise, ensure all regs are up-to-date. */
2635
2636 if (REG_QTY (REGNO (x)) != REG_QTY (regno))
2637 return 0;
2638
2639 if (! validate)
2640 return 1;
2641
2642 for (i = regno; i < endregno; i++)
2643 if (REG_IN_TABLE (i) != REG_TICK (i))
2644 return 0;
2645
2646 return 1;
2647 }
2648
2649 case MEM:
2650 if (for_gcse)
2651 {
2652 /* A volatile mem should not be considered equivalent to any
2653 other. */
2654 if (MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
2655 return 0;
2656
2657 /* Can't merge two expressions in different alias sets, since we
2658 can decide that the expression is transparent in a block when
2659 it isn't, due to it being set with the different alias set.
2660
2661 Also, can't merge two expressions with different MEM_ATTRS.
2662 They could e.g. be two different entities allocated into the
2663 same space on the stack (see e.g. PR25130). In that case, the
2664 MEM addresses can be the same, even though the two MEMs are
2665 absolutely not equivalent.
2666
2667 But because really all MEM attributes should be the same for
2668 equivalent MEMs, we just use the invariant that MEMs that have
2669 the same attributes share the same mem_attrs data structure. */
2670 if (!mem_attrs_eq_p (MEM_ATTRS (x), MEM_ATTRS (y)))
2671 return 0;
2672
2673 /* If we are handling exceptions, we cannot consider two expressions
2674 with different trapping status as equivalent, because simple_mem
2675 might accept one and reject the other. */
2676 if (cfun->can_throw_non_call_exceptions
2677 && (MEM_NOTRAP_P (x) != MEM_NOTRAP_P (y)))
2678 return 0;
2679 }
2680 break;
2681
2682 /* For commutative operations, check both orders. */
2683 case PLUS:
2684 case MULT:
2685 case AND:
2686 case IOR:
2687 case XOR:
2688 case NE:
2689 case EQ:
2690 return ((exp_equiv_p (XEXP (x, 0), XEXP (y, 0),
2691 validate, for_gcse)
2692 && exp_equiv_p (XEXP (x, 1), XEXP (y, 1),
2693 validate, for_gcse))
2694 || (exp_equiv_p (XEXP (x, 0), XEXP (y, 1),
2695 validate, for_gcse)
2696 && exp_equiv_p (XEXP (x, 1), XEXP (y, 0),
2697 validate, for_gcse)));
2698
2699 case ASM_OPERANDS:
2700 /* We don't use the generic code below because we want to
2701 disregard filename and line numbers. */
2702
2703 /* A volatile asm isn't equivalent to any other. */
2704 if (MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
2705 return 0;
2706
2707 if (GET_MODE (x) != GET_MODE (y)
2708 || strcmp (ASM_OPERANDS_TEMPLATE (x), ASM_OPERANDS_TEMPLATE (y))
2709 || strcmp (ASM_OPERANDS_OUTPUT_CONSTRAINT (x),
2710 ASM_OPERANDS_OUTPUT_CONSTRAINT (y))
2711 || ASM_OPERANDS_OUTPUT_IDX (x) != ASM_OPERANDS_OUTPUT_IDX (y)
2712 || ASM_OPERANDS_INPUT_LENGTH (x) != ASM_OPERANDS_INPUT_LENGTH (y))
2713 return 0;
2714
2715 if (ASM_OPERANDS_INPUT_LENGTH (x))
2716 {
2717 for (i = ASM_OPERANDS_INPUT_LENGTH (x) - 1; i >= 0; i--)
2718 if (! exp_equiv_p (ASM_OPERANDS_INPUT (x, i),
2719 ASM_OPERANDS_INPUT (y, i),
2720 validate, for_gcse)
2721 || strcmp (ASM_OPERANDS_INPUT_CONSTRAINT (x, i),
2722 ASM_OPERANDS_INPUT_CONSTRAINT (y, i)))
2723 return 0;
2724 }
2725
2726 return 1;
2727
2728 default:
2729 break;
2730 }
2731
2732 /* Compare the elements. If any pair of corresponding elements
2733 fail to match, return 0 for the whole thing. */
2734
2735 fmt = GET_RTX_FORMAT (code);
2736 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2737 {
2738 switch (fmt[i])
2739 {
2740 case 'e':
2741 if (! exp_equiv_p (XEXP (x, i), XEXP (y, i),
2742 validate, for_gcse))
2743 return 0;
2744 break;
2745
2746 case 'E':
2747 if (XVECLEN (x, i) != XVECLEN (y, i))
2748 return 0;
2749 for (j = 0; j < XVECLEN (x, i); j++)
2750 if (! exp_equiv_p (XVECEXP (x, i, j), XVECEXP (y, i, j),
2751 validate, for_gcse))
2752 return 0;
2753 break;
2754
2755 case 's':
2756 if (strcmp (XSTR (x, i), XSTR (y, i)))
2757 return 0;
2758 break;
2759
2760 case 'i':
2761 if (XINT (x, i) != XINT (y, i))
2762 return 0;
2763 break;
2764
2765 case 'w':
2766 if (XWINT (x, i) != XWINT (y, i))
2767 return 0;
2768 break;
2769
2770 case '0':
2771 case 't':
2772 break;
2773
2774 default:
2775 gcc_unreachable ();
2776 }
2777 }
2778
2779 return 1;
2780}
2781
2782/* Subroutine of canon_reg. Pass *XLOC through canon_reg, and validate
2783 the result if necessary. INSN is as for canon_reg. */
2784
2785static void
2786validate_canon_reg (rtx *xloc, rtx_insn *insn)
2787{
2788 if (*xloc)
2789 {
2790 rtx new_rtx = canon_reg (*xloc, insn);
2791
2792 /* If replacing pseudo with hard reg or vice versa, ensure the
2793 insn remains valid. Likewise if the insn has MATCH_DUPs. */
2794 gcc_assert (insn && new_rtx);
2795 validate_change (insn, xloc, new_rtx, 1);
2796 }
2797}
2798
2799/* Canonicalize an expression:
2800 replace each register reference inside it
2801 with the "oldest" equivalent register.
2802
2803 If INSN is nonzero validate_change is used to ensure that INSN remains valid
2804 after we make our substitution. The calls are made with IN_GROUP nonzero
2805 so apply_change_group must be called upon the outermost return from this
2806 function (unless INSN is zero). The result of apply_change_group can
2807 generally be discarded since the changes we are making are optional. */
2808
2809static rtx
2810canon_reg (rtx x, rtx_insn *insn)
2811{
2812 int i;
2813 enum rtx_code code;
2814 const char *fmt;
2815
2816 if (x == 0)
2817 return x;
2818
2819 code = GET_CODE (x);
2820 switch (code)
2821 {
2822 case PC:
2823 case CC0:
2824 case CONST:
2825 CASE_CONST_ANY:
2826 case SYMBOL_REF:
2827 case LABEL_REF:
2828 case ADDR_VEC:
2829 case ADDR_DIFF_VEC:
2830 return x;
2831
2832 case REG:
2833 {
2834 int first;
2835 int q;
2836 struct qty_table_elem *ent;
2837
2838 /* Never replace a hard reg, because hard regs can appear
2839 in more than one machine mode, and we must preserve the mode
2840 of each occurrence. Also, some hard regs appear in
2841 MEMs that are shared and mustn't be altered. Don't try to
2842 replace any reg that maps to a reg of class NO_REGS. */
2843 if (REGNO (x) < FIRST_PSEUDO_REGISTER
2844 || ! REGNO_QTY_VALID_P (REGNO (x)))
2845 return x;
2846
2847 q = REG_QTY (REGNO (x));
2848 ent = &qty_table[q];
2849 first = ent->first_reg;
2850 return (first >= FIRST_PSEUDO_REGISTER ? regno_reg_rtx[first]
2851 : REGNO_REG_CLASS (first) == NO_REGS ? x
2852 : gen_rtx_REG (ent->mode, first));
2853 }
2854
2855 default:
2856 break;
2857 }
2858
2859 fmt = GET_RTX_FORMAT (code);
2860 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2861 {
2862 int j;
2863
2864 if (fmt[i] == 'e')
2865 validate_canon_reg (&XEXP (x, i), insn);
2866 else if (fmt[i] == 'E')
2867 for (j = 0; j < XVECLEN (x, i); j++)
2868 validate_canon_reg (&XVECEXP (x, i, j), insn);
2869 }
2870
2871 return x;
2872}
2873
2874/* Given an operation (CODE, *PARG1, *PARG2), where code is a comparison
2875 operation (EQ, NE, GT, etc.), follow it back through the hash table and
2876 what values are being compared.
2877
2878 *PARG1 and *PARG2 are updated to contain the rtx representing the values
2879 actually being compared. For example, if *PARG1 was (cc0) and *PARG2
2880 was (const_int 0), *PARG1 and *PARG2 will be set to the objects that were
2881 compared to produce cc0.
2882
2883 The return value is the comparison operator and is either the code of
2884 A or the code corresponding to the inverse of the comparison. */
2885
2886static enum rtx_code
2887find_comparison_args (enum rtx_code code, rtx *parg1, rtx *parg2,
2888 machine_mode *pmode1, machine_mode *pmode2)
2889{
2890 rtx arg1, arg2;
2891 hash_set<rtx> *visited = NULL;
2892 /* Set nonzero when we find something of interest. */
2893 rtx x = NULL;
2894
2895 arg1 = *parg1, arg2 = *parg2;
2896
2897 /* If ARG2 is const0_rtx, see what ARG1 is equivalent to. */
2898
2899 while (arg2 == CONST0_RTX (GET_MODE (arg1)))
2900 {
2901 int reverse_code = 0;
2902 struct table_elt *p = 0;
2903
2904 /* Remember state from previous iteration. */
2905 if (x)
2906 {
2907 if (!visited)
2908 visited = new hash_set<rtx>;
2909 visited->add (x);
2910 x = 0;
2911 }
2912
2913 /* If arg1 is a COMPARE, extract the comparison arguments from it.
2914 On machines with CC0, this is the only case that can occur, since
2915 fold_rtx will return the COMPARE or item being compared with zero
2916 when given CC0. */
2917
2918 if (GET_CODE (arg1) == COMPARE && arg2 == const0_rtx)
2919 x = arg1;
2920
2921 /* If ARG1 is a comparison operator and CODE is testing for
2922 STORE_FLAG_VALUE, get the inner arguments. */
2923
2924 else if (COMPARISON_P (arg1))
2925 {
2926#ifdef FLOAT_STORE_FLAG_VALUE
2927 REAL_VALUE_TYPE fsfv;
2928#endif
2929
2930 if (code == NE
2931 || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_INT
2932 && code == LT && STORE_FLAG_VALUE == -1)
2933#ifdef FLOAT_STORE_FLAG_VALUE
2934 || (SCALAR_FLOAT_MODE_P (GET_MODE (arg1))
2935 && (fsfv = FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1)),
2936 REAL_VALUE_NEGATIVE (fsfv)))
2937#endif
2938 )
2939 x = arg1;
2940 else if (code == EQ
2941 || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_INT
2942 && code == GE && STORE_FLAG_VALUE == -1)
2943#ifdef FLOAT_STORE_FLAG_VALUE
2944 || (SCALAR_FLOAT_MODE_P (GET_MODE (arg1))
2945 && (fsfv = FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1)),
2946 REAL_VALUE_NEGATIVE (fsfv)))
2947#endif
2948 )
2949 x = arg1, reverse_code = 1;
2950 }
2951
2952 /* ??? We could also check for
2953
2954 (ne (and (eq (...) (const_int 1))) (const_int 0))
2955
2956 and related forms, but let's wait until we see them occurring. */
2957
2958 if (x == 0)
2959 /* Look up ARG1 in the hash table and see if it has an equivalence
2960 that lets us see what is being compared. */
2961 p = lookup (arg1, SAFE_HASH (arg1, GET_MODE (arg1)), GET_MODE (arg1));
2962 if (p)
2963 {
2964 p = p->first_same_value;
2965
2966 /* If what we compare is already known to be constant, that is as
2967 good as it gets.
2968 We need to break the loop in this case, because otherwise we
2969 can have an infinite loop when looking at a reg that is known
2970 to be a constant which is the same as a comparison of a reg
2971 against zero which appears later in the insn stream, which in
2972 turn is constant and the same as the comparison of the first reg
2973 against zero... */
2974 if (p->is_const)
2975 break;
2976 }
2977
2978 for (; p; p = p->next_same_value)
2979 {
2980 machine_mode inner_mode = GET_MODE (p->exp);
2981#ifdef FLOAT_STORE_FLAG_VALUE
2982 REAL_VALUE_TYPE fsfv;
2983#endif
2984
2985 /* If the entry isn't valid, skip it. */
2986 if (! exp_equiv_p (p->exp, p->exp, 1, false))
2987 continue;
2988
2989 /* If it's a comparison we've used before, skip it. */
2990 if (visited && visited->contains (p->exp))
2991 continue;
2992
2993 if (GET_CODE (p->exp) == COMPARE
2994 /* Another possibility is that this machine has a compare insn
2995 that includes the comparison code. In that case, ARG1 would
2996 be equivalent to a comparison operation that would set ARG1 to
2997 either STORE_FLAG_VALUE or zero. If this is an NE operation,
2998 ORIG_CODE is the actual comparison being done; if it is an EQ,
2999 we must reverse ORIG_CODE. On machine with a negative value
3000 for STORE_FLAG_VALUE, also look at LT and GE operations. */
3001 || ((code == NE
3002 || (code == LT
3003 && val_signbit_known_set_p (inner_mode,
3004 STORE_FLAG_VALUE))
3005#ifdef FLOAT_STORE_FLAG_VALUE
3006 || (code == LT
3007 && SCALAR_FLOAT_MODE_P (inner_mode)
3008 && (fsfv = FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1)),
3009 REAL_VALUE_NEGATIVE (fsfv)))
3010#endif
3011 )
3012 && COMPARISON_P (p->exp)))
3013 {
3014 x = p->exp;
3015 break;
3016 }
3017 else if ((code == EQ
3018 || (code == GE
3019 && val_signbit_known_set_p (inner_mode,
3020 STORE_FLAG_VALUE))
3021#ifdef FLOAT_STORE_FLAG_VALUE
3022 || (code == GE
3023 && SCALAR_FLOAT_MODE_P (inner_mode)
3024 && (fsfv = FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1)),
3025 REAL_VALUE_NEGATIVE (fsfv)))
3026#endif
3027 )
3028 && COMPARISON_P (p->exp))
3029 {
3030 reverse_code = 1;
3031 x = p->exp;
3032 break;
3033 }
3034
3035 /* If this non-trapping address, e.g. fp + constant, the
3036 equivalent is a better operand since it may let us predict
3037 the value of the comparison. */
3038 else if (!rtx_addr_can_trap_p (p->exp))
3039 {
3040 arg1 = p->exp;
3041 continue;
3042 }
3043 }
3044
3045 /* If we didn't find a useful equivalence for ARG1, we are done.
3046 Otherwise, set up for the next iteration. */
3047 if (x == 0)
3048 break;
3049
3050 /* If we need to reverse the comparison, make sure that is
3051 possible -- we can't necessarily infer the value of GE from LT
3052 with floating-point operands. */
3053 if (reverse_code)
3054 {
3055 enum rtx_code reversed = reversed_comparison_code (x, NULL);
3056 if (reversed == UNKNOWN)
3057 break;
3058 else
3059 code = reversed;
3060 }
3061 else if (COMPARISON_P (x))
3062 code = GET_CODE (x);
3063 arg1 = XEXP (x, 0), arg2 = XEXP (x, 1);
3064 }
3065
3066 /* Return our results. Return the modes from before fold_rtx
3067 because fold_rtx might produce const_int, and then it's too late. */
3068 *pmode1 = GET_MODE (arg1), *pmode2 = GET_MODE (arg2);
3069 *parg1 = fold_rtx (arg1, 0), *parg2 = fold_rtx (arg2, 0);
3070
3071 if (visited)
3072 delete visited;
3073 return code;
3074}
3075
3076/* If X is a nontrivial arithmetic operation on an argument for which
3077 a constant value can be determined, return the result of operating
3078 on that value, as a constant. Otherwise, return X, possibly with
3079 one or more operands changed to a forward-propagated constant.
3080
3081 If X is a register whose contents are known, we do NOT return
3082 those contents here; equiv_constant is called to perform that task.
3083 For SUBREGs and MEMs, we do that both here and in equiv_constant.
3084
3085 INSN is the insn that we may be modifying. If it is 0, make a copy
3086 of X before modifying it. */
3087
3088static rtx
3089fold_rtx (rtx x, rtx_insn *insn)
3090{
3091 enum rtx_code code;
3092 machine_mode mode;
3093 const char *fmt;
3094 int i;
3095 rtx new_rtx = 0;
3096 int changed = 0;
3097
3098 /* Operands of X. */
3099 /* Workaround -Wmaybe-uninitialized false positive during
3100 profiledbootstrap by initializing them. */
3101 rtx folded_arg0 = NULL_RTX;
3102 rtx folded_arg1 = NULL_RTX;
3103
3104 /* Constant equivalents of first three operands of X;
3105 0 when no such equivalent is known. */
3106 rtx const_arg0;
3107 rtx const_arg1;
3108 rtx const_arg2;
3109
3110 /* The mode of the first operand of X. We need this for sign and zero
3111 extends. */
3112 machine_mode mode_arg0;
3113
3114 if (x == 0)
3115 return x;
3116
3117 /* Try to perform some initial simplifications on X. */
3118 code = GET_CODE (x);
3119 switch (code)
3120 {
3121 case MEM:
3122 case SUBREG:
3123 /* The first operand of a SIGN/ZERO_EXTRACT has a different meaning
3124 than it would in other contexts. Basically its mode does not
3125 signify the size of the object read. That information is carried
3126 by size operand. If we happen to have a MEM of the appropriate
3127 mode in our tables with a constant value we could simplify the
3128 extraction incorrectly if we allowed substitution of that value
3129 for the MEM. */
3130 case ZERO_EXTRACT:
3131 case SIGN_EXTRACT:
3132 if ((new_rtx = equiv_constant (x)) != NULL_RTX)
3133 return new_rtx;
3134 return x;
3135
3136 case CONST:
3137 CASE_CONST_ANY:
3138 case SYMBOL_REF:
3139 case LABEL_REF:
3140 case REG:
3141 case PC:
3142 /* No use simplifying an EXPR_LIST
3143 since they are used only for lists of args
3144 in a function call's REG_EQUAL note. */
3145 case EXPR_LIST:
3146 return x;
3147
3148 case CC0:
3149 return prev_insn_cc0;
3150
3151 case ASM_OPERANDS:
3152 if (insn)
3153 {
3154 for (i = ASM_OPERANDS_INPUT_LENGTH (x) - 1; i >= 0; i--)
3155 validate_change (insn, &ASM_OPERANDS_INPUT (x, i),
3156 fold_rtx (ASM_OPERANDS_INPUT (x, i), insn), 0);
3157 }
3158 return x;
3159
3160 case CALL:
3161 if (NO_FUNCTION_CSE && CONSTANT_P (XEXP (XEXP (x, 0), 0)))
3162 return x;
3163 break;
3164
3165 /* Anything else goes through the loop below. */
3166 default:
3167 break;
3168 }
3169
3170 mode = GET_MODE (x);
3171 const_arg0 = 0;
3172 const_arg1 = 0;
3173 const_arg2 = 0;
3174 mode_arg0 = VOIDmode;
3175
3176 /* Try folding our operands.
3177 Then see which ones have constant values known. */
3178
3179 fmt = GET_RTX_FORMAT (code);
3180 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3181 if (fmt[i] == 'e')
3182 {
3183 rtx folded_arg = XEXP (x, i), const_arg;
3184 machine_mode mode_arg = GET_MODE (folded_arg);
3185
3186 switch (GET_CODE (folded_arg))
3187 {
3188 case MEM:
3189 case REG:
3190 case SUBREG:
3191 const_arg = equiv_constant (folded_arg);
3192 break;
3193
3194 case CONST:
3195 CASE_CONST_ANY:
3196 case SYMBOL_REF:
3197 case LABEL_REF:
3198 const_arg = folded_arg;
3199 break;
3200
3201 case CC0:
3202 /* The cc0-user and cc0-setter may be in different blocks if
3203 the cc0-setter potentially traps. In that case PREV_INSN_CC0
3204 will have been cleared as we exited the block with the
3205 setter.
3206
3207 While we could potentially track cc0 in this case, it just
3208 doesn't seem to be worth it given that cc0 targets are not
3209 terribly common or important these days and trapping math
3210 is rarely used. The combination of those two conditions
3211 necessary to trip this situation is exceedingly rare in the
3212 real world. */
3213 if (!prev_insn_cc0)
3214 {
3215 const_arg = NULL_RTX;
3216 }
3217 else
3218 {
3219 folded_arg = prev_insn_cc0;
3220 mode_arg = prev_insn_cc0_mode;
3221 const_arg = equiv_constant (folded_arg);
3222 }
3223 break;
3224
3225 default:
3226 folded_arg = fold_rtx (folded_arg, insn);
3227 const_arg = equiv_constant (folded_arg);
3228 break;
3229 }
3230
3231 /* For the first three operands, see if the operand
3232 is constant or equivalent to a constant. */
3233 switch (i)
3234 {
3235 case 0:
3236 folded_arg0 = folded_arg;
3237 const_arg0 = const_arg;
3238 mode_arg0 = mode_arg;
3239 break;
3240 case 1:
3241 folded_arg1 = folded_arg;
3242 const_arg1 = const_arg;
3243 break;
3244 case 2:
3245 const_arg2 = const_arg;
3246 break;
3247 }
3248
3249 /* Pick the least expensive of the argument and an equivalent constant
3250 argument. */
3251 if (const_arg != 0
3252 && const_arg != folded_arg
3253 && (COST_IN (const_arg, mode_arg, code, i)
3254 <= COST_IN (folded_arg, mode_arg, code, i))
3255
3256 /* It's not safe to substitute the operand of a conversion
3257 operator with a constant, as the conversion's identity
3258 depends upon the mode of its operand. This optimization
3259 is handled by the call to simplify_unary_operation. */
3260 && (GET_RTX_CLASS (code) != RTX_UNARY
3261 || GET_MODE (const_arg) == mode_arg0
3262 || (code != ZERO_EXTEND
3263 && code != SIGN_EXTEND
3264 && code != TRUNCATE
3265 && code != FLOAT_TRUNCATE
3266 && code != FLOAT_EXTEND
3267 && code != FLOAT
3268 && code != FIX
3269 && code != UNSIGNED_FLOAT
3270 && code != UNSIGNED_FIX)))
3271 folded_arg = const_arg;
3272
3273 if (folded_arg == XEXP (x, i))
3274 continue;
3275
3276 if (insn == NULL_RTX && !changed)
3277 x = copy_rtx (x);
3278 changed = 1;
3279 validate_unshare_change (insn, &XEXP (x, i), folded_arg, 1);
3280 }
3281
3282 if (changed)
3283 {
3284 /* Canonicalize X if necessary, and keep const_argN and folded_argN
3285 consistent with the order in X. */
3286 if (canonicalize_change_group (insn, x))
3287 {
3288 std::swap (const_arg0, const_arg1);
3289 std::swap (folded_arg0, folded_arg1);
3290 }
3291
3292 apply_change_group ();
3293 }
3294
3295 /* If X is an arithmetic operation, see if we can simplify it. */
3296
3297 switch (GET_RTX_CLASS (code))
3298 {
3299 case RTX_UNARY:
3300 {
3301 /* We can't simplify extension ops unless we know the
3302 original mode. */
3303 if ((code == ZERO_EXTEND || code == SIGN_EXTEND)
3304 && mode_arg0 == VOIDmode)
3305 break;
3306
3307 new_rtx = simplify_unary_operation (code, mode,
3308 const_arg0 ? const_arg0 : folded_arg0,
3309 mode_arg0);
3310 }
3311 break;
3312
3313 case RTX_COMPARE:
3314 case RTX_COMM_COMPARE:
3315 /* See what items are actually being compared and set FOLDED_ARG[01]
3316 to those values and CODE to the actual comparison code. If any are
3317 constant, set CONST_ARG0 and CONST_ARG1 appropriately. We needn't
3318 do anything if both operands are already known to be constant. */
3319
3320 /* ??? Vector mode comparisons are not supported yet. */
3321 if (VECTOR_MODE_P (mode))
3322 break;
3323
3324 if (const_arg0 == 0 || const_arg1 == 0)
3325 {
3326 struct table_elt *p0, *p1;
3327 rtx true_rtx, false_rtx;
3328 machine_mode mode_arg1;
3329
3330 if (SCALAR_FLOAT_MODE_P (mode))
3331 {
3332#ifdef FLOAT_STORE_FLAG_VALUE
3333 true_rtx = (const_double_from_real_value
3334 (FLOAT_STORE_FLAG_VALUE (mode), mode));
3335#else
3336 true_rtx = NULL_RTX;
3337#endif
3338 false_rtx = CONST0_RTX (mode);
3339 }
3340 else
3341 {
3342 true_rtx = const_true_rtx;
3343 false_rtx = const0_rtx;
3344 }
3345
3346 code = find_comparison_args (code, &folded_arg0, &folded_arg1,
3347 &mode_arg0, &mode_arg1);
3348
3349 /* If the mode is VOIDmode or a MODE_CC mode, we don't know
3350 what kinds of things are being compared, so we can't do
3351 anything with this comparison. */
3352
3353 if (mode_arg0 == VOIDmode || GET_MODE_CLASS (mode_arg0) == MODE_CC)
3354 break;
3355
3356 const_arg0 = equiv_constant (folded_arg0);
3357 const_arg1 = equiv_constant (folded_arg1);
3358
3359 /* If we do not now have two constants being compared, see
3360 if we can nevertheless deduce some things about the
3361 comparison. */
3362 if (const_arg0 == 0 || const_arg1 == 0)
3363 {
3364 if (const_arg1 != NULL)
3365 {
3366 rtx cheapest_simplification;
3367 int cheapest_cost;
3368 rtx simp_result;
3369 struct table_elt *p;
3370
3371 /* See if we can find an equivalent of folded_arg0
3372 that gets us a cheaper expression, possibly a
3373 constant through simplifications. */
3374 p = lookup (folded_arg0, SAFE_HASH (folded_arg0, mode_arg0),
3375 mode_arg0);
3376
3377 if (p != NULL)
3378 {
3379 cheapest_simplification = x;
3380 cheapest_cost = COST (x, mode);
3381
3382 for (p = p->first_same_value; p != NULL; p = p->next_same_value)
3383 {
3384 int cost;
3385
3386 /* If the entry isn't valid, skip it. */
3387 if (! exp_equiv_p (p->exp, p->exp, 1, false))
3388 continue;
3389
3390 /* Try to simplify using this equivalence. */
3391 simp_result
3392 = simplify_relational_operation (code, mode,
3393 mode_arg0,
3394 p->exp,
3395 const_arg1);
3396
3397 if (simp_result == NULL)
3398 continue;
3399
3400 cost = COST (simp_result, mode);
3401 if (cost < cheapest_cost)
3402 {
3403 cheapest_cost = cost;
3404 cheapest_simplification = simp_result;
3405 }
3406 }
3407
3408 /* If we have a cheaper expression now, use that
3409 and try folding it further, from the top. */
3410 if (cheapest_simplification != x)
3411 return fold_rtx (copy_rtx (cheapest_simplification),
3412 insn);
3413 }
3414 }
3415
3416 /* See if the two operands are the same. */
3417
3418 if ((REG_P (folded_arg0)
3419 && REG_P (folded_arg1)
3420 && (REG_QTY (REGNO (folded_arg0))
3421 == REG_QTY (REGNO (folded_arg1))))
3422 || ((p0 = lookup (folded_arg0,
3423 SAFE_HASH (folded_arg0, mode_arg0),
3424 mode_arg0))
3425 && (p1 = lookup (folded_arg1,
3426 SAFE_HASH (folded_arg1, mode_arg0),
3427 mode_arg0))
3428 && p0->first_same_value == p1->first_same_value))
3429 folded_arg1 = folded_arg0;
3430
3431 /* If FOLDED_ARG0 is a register, see if the comparison we are
3432 doing now is either the same as we did before or the reverse
3433 (we only check the reverse if not floating-point). */
3434 else if (REG_P (folded_arg0))
3435 {
3436 int qty = REG_QTY (REGNO (folded_arg0));
3437
3438 if (REGNO_QTY_VALID_P (REGNO (folded_arg0)))
3439 {
3440 struct qty_table_elem *ent = &qty_table[qty];
3441
3442 if ((comparison_dominates_p (ent->comparison_code, code)
3443 || (! FLOAT_MODE_P (mode_arg0)
3444 && comparison_dominates_p (ent->comparison_code,
3445 reverse_condition (code))))
3446 && (rtx_equal_p (ent->comparison_const, folded_arg1)
3447 || (const_arg1
3448 && rtx_equal_p (ent->comparison_const,
3449 const_arg1))
3450 || (REG_P (folded_arg1)
3451 && (REG_QTY (REGNO (folded_arg1)) == ent->comparison_qty))))
3452 {
3453 if (comparison_dominates_p (ent->comparison_code, code))
3454 {
3455 if (true_rtx)
3456 return true_rtx;
3457 else
3458 break;
3459 }
3460 else
3461 return false_rtx;
3462 }
3463 }
3464 }
3465 }
3466 }
3467
3468 /* If we are comparing against zero, see if the first operand is
3469 equivalent to an IOR with a constant. If so, we may be able to
3470 determine the result of this comparison. */
3471 if (const_arg1 == const0_rtx && !const_arg0)
3472 {
3473 rtx y = lookup_as_function (folded_arg0, IOR);
3474 rtx inner_const;
3475
3476 if (y != 0
3477 && (inner_const = equiv_constant (XEXP (y, 1))) != 0
3478 && CONST_INT_P (inner_const)
3479 && INTVAL (inner_const) != 0)
3480 folded_arg0 = gen_rtx_IOR (mode_arg0, XEXP (y, 0), inner_const);
3481 }
3482
3483 {
3484 rtx op0 = const_arg0 ? const_arg0 : copy_rtx (folded_arg0);
3485 rtx op1 = const_arg1 ? const_arg1 : copy_rtx (folded_arg1);
3486 new_rtx = simplify_relational_operation (code, mode, mode_arg0,
3487 op0, op1);
3488 }
3489 break;
3490
3491 case RTX_BIN_ARITH:
3492 case RTX_COMM_ARITH:
3493 switch (code)
3494 {
3495 case PLUS:
3496 /* If the second operand is a LABEL_REF, see if the first is a MINUS
3497 with that LABEL_REF as its second operand. If so, the result is
3498 the first operand of that MINUS. This handles switches with an
3499 ADDR_DIFF_VEC table. */
3500 if (const_arg1 && GET_CODE (const_arg1) == LABEL_REF)
3501 {
3502 rtx y
3503 = GET_CODE (folded_arg0) == MINUS ? folded_arg0
3504 : lookup_as_function (folded_arg0, MINUS);
3505
3506 if (y != 0 && GET_CODE (XEXP (y, 1)) == LABEL_REF
3507 && label_ref_label (XEXP (y, 1)) == label_ref_label (const_arg1))
3508 return XEXP (y, 0);
3509
3510 /* Now try for a CONST of a MINUS like the above. */
3511 if ((y = (GET_CODE (folded_arg0) == CONST ? folded_arg0
3512 : lookup_as_function (folded_arg0, CONST))) != 0
3513 && GET_CODE (XEXP (y, 0)) == MINUS
3514 && GET_CODE (XEXP (XEXP (y, 0), 1)) == LABEL_REF
3515 && label_ref_label (XEXP (XEXP (y, 0), 1)) == label_ref_label (const_arg1))
3516 return XEXP (XEXP (y, 0), 0);
3517 }
3518
3519 /* Likewise if the operands are in the other order. */
3520 if (const_arg0 && GET_CODE (const_arg0) == LABEL_REF)
3521 {
3522 rtx y
3523 = GET_CODE (folded_arg1) == MINUS ? folded_arg1
3524 : lookup_as_function (folded_arg1, MINUS);
3525
3526 if (y != 0 && GET_CODE (XEXP (y, 1)) == LABEL_REF
3527 && label_ref_label (XEXP (y, 1)) == label_ref_label (const_arg0))
3528 return XEXP (y, 0);
3529
3530 /* Now try for a CONST of a MINUS like the above. */
3531 if ((y = (GET_CODE (folded_arg1) == CONST ? folded_arg1
3532 : lookup_as_function (folded_arg1, CONST))) != 0
3533 && GET_CODE (XEXP (y, 0)) == MINUS
3534 && GET_CODE (XEXP (XEXP (y, 0), 1)) == LABEL_REF
3535 && label_ref_label (XEXP (XEXP (y, 0), 1)) == label_ref_label (const_arg0))
3536 return XEXP (XEXP (y, 0), 0);
3537 }
3538
3539 /* If second operand is a register equivalent to a negative
3540 CONST_INT, see if we can find a register equivalent to the
3541 positive constant. Make a MINUS if so. Don't do this for
3542 a non-negative constant since we might then alternate between
3543 choosing positive and negative constants. Having the positive
3544 constant previously-used is the more common case. Be sure
3545 the resulting constant is non-negative; if const_arg1 were
3546 the smallest negative number this would overflow: depending
3547 on the mode, this would either just be the same value (and
3548 hence not save anything) or be incorrect. */
3549 if (const_arg1 != 0 && CONST_INT_P (const_arg1)
3550 && INTVAL (const_arg1) < 0
3551 /* This used to test
3552
3553 -INTVAL (const_arg1) >= 0
3554
3555 But The Sun V5.0 compilers mis-compiled that test. So
3556 instead we test for the problematic value in a more direct
3557 manner and hope the Sun compilers get it correct. */
3558 && INTVAL (const_arg1) !=
3559 (HOST_WIDE_INT_1 << (HOST_BITS_PER_WIDE_INT - 1))
3560 && REG_P (folded_arg1))
3561 {
3562 rtx new_const = GEN_INT (-INTVAL (const_arg1));
3563 struct table_elt *p
3564 = lookup (new_const, SAFE_HASH (new_const, mode), mode);
3565
3566 if (p)
3567 for (p = p->first_same_value; p; p = p->next_same_value)
3568 if (REG_P (p->exp))
3569 return simplify_gen_binary (MINUS, mode, folded_arg0,
3570 canon_reg (p->exp, NULL));
3571 }
3572 goto from_plus;
3573
3574 case MINUS:
3575 /* If we have (MINUS Y C), see if Y is known to be (PLUS Z C2).
3576 If so, produce (PLUS Z C2-C). */
3577 if (const_arg1 != 0 && CONST_INT_P (const_arg1))
3578 {
3579 rtx y = lookup_as_function (XEXP (x, 0), PLUS);
3580 if (y && CONST_INT_P (XEXP (y, 1)))
3581 return fold_rtx (plus_constant (mode, copy_rtx (y),
3582 -INTVAL (const_arg1)),
3583 NULL);
3584 }
3585
3586 /* Fall through. */
3587
3588 from_plus:
3589 case SMIN: case SMAX: case UMIN: case UMAX:
3590 case IOR: case AND: case XOR:
3591 case MULT:
3592 case ASHIFT: case LSHIFTRT: case ASHIFTRT:
3593 /* If we have (<op> <reg> <const_int>) for an associative OP and REG
3594 is known to be of similar form, we may be able to replace the
3595 operation with a combined operation. This may eliminate the
3596 intermediate operation if every use is simplified in this way.
3597 Note that the similar optimization done by combine.c only works
3598 if the intermediate operation's result has only one reference. */
3599
3600 if (REG_P (folded_arg0)
3601 && const_arg1 && CONST_INT_P (const_arg1))
3602 {
3603 int is_shift
3604 = (code == ASHIFT || code == ASHIFTRT || code == LSHIFTRT);
3605 rtx y, inner_const, new_const;
3606 rtx canon_const_arg1 = const_arg1;
3607 enum rtx_code associate_code;
3608
3609 if (is_shift
3610 && (INTVAL (const_arg1) >= GET_MODE_UNIT_PRECISION (mode)
3611 || INTVAL (const_arg1) < 0))
3612 {
3613 if (SHIFT_COUNT_TRUNCATED)
3614 canon_const_arg1 = GEN_INT (INTVAL (const_arg1)
3615 & (GET_MODE_UNIT_BITSIZE (mode)
3616 - 1));
3617 else
3618 break;
3619 }
3620
3621 y = lookup_as_function (folded_arg0, code);
3622 if (y == 0)
3623 break;
3624
3625 /* If we have compiled a statement like
3626 "if (x == (x & mask1))", and now are looking at
3627 "x & mask2", we will have a case where the first operand
3628 of Y is the same as our first operand. Unless we detect
3629 this case, an infinite loop will result. */
3630 if (XEXP (y, 0) == folded_arg0)
3631 break;
3632
3633 inner_const = equiv_constant (fold_rtx (XEXP (y, 1), 0));
3634 if (!inner_const || !CONST_INT_P (inner_const))
3635 break;
3636
3637 /* Don't associate these operations if they are a PLUS with the
3638 same constant and it is a power of two. These might be doable
3639 with a pre- or post-increment. Similarly for two subtracts of
3640 identical powers of two with post decrement. */
3641
3642 if (code == PLUS && const_arg1 == inner_const
3643 && ((HAVE_PRE_INCREMENT
3644 && pow2p_hwi (INTVAL (const_arg1)))
3645 || (HAVE_POST_INCREMENT
3646 && pow2p_hwi (INTVAL (const_arg1)))
3647 || (HAVE_PRE_DECREMENT
3648 && pow2p_hwi (- INTVAL (const_arg1)))
3649 || (HAVE_POST_DECREMENT
3650 && pow2p_hwi (- INTVAL (const_arg1)))))
3651 break;
3652
3653 /* ??? Vector mode shifts by scalar
3654 shift operand are not supported yet. */
3655 if (is_shift && VECTOR_MODE_P (mode))
3656 break;
3657
3658 if (is_shift
3659 && (INTVAL (inner_const) >= GET_MODE_UNIT_PRECISION (mode)
3660 || INTVAL (inner_const) < 0))
3661 {
3662 if (SHIFT_COUNT_TRUNCATED)
3663 inner_const = GEN_INT (INTVAL (inner_const)
3664 & (GET_MODE_UNIT_BITSIZE (mode)
3665 - 1));
3666 else
3667 break;
3668 }
3669
3670 /* Compute the code used to compose the constants. For example,
3671 A-C1-C2 is A-(C1 + C2), so if CODE == MINUS, we want PLUS. */
3672
3673 associate_code = (is_shift || code == MINUS ? PLUS : code);
3674
3675 new_const = simplify_binary_operation (associate_code, mode,
3676 canon_const_arg1,
3677 inner_const);
3678
3679 if (new_const == 0)
3680 break;
3681
3682 /* If we are associating shift operations, don't let this
3683 produce a shift of the size of the object or larger.
3684 This could occur when we follow a sign-extend by a right
3685 shift on a machine that does a sign-extend as a pair
3686 of shifts. */
3687
3688 if (is_shift
3689 && CONST_INT_P (new_const)
3690 && INTVAL (new_const) >= GET_MODE_UNIT_PRECISION (mode))
3691 {
3692 /* As an exception, we can turn an ASHIFTRT of this
3693 form into a shift of the number of bits - 1. */
3694 if (code == ASHIFTRT)
3695 new_const = GEN_INT (GET_MODE_UNIT_BITSIZE (mode) - 1);
3696 else if (!side_effects_p (XEXP (y, 0)))
3697 return CONST0_RTX (mode);
3698 else
3699 break;
3700 }
3701
3702 y = copy_rtx (XEXP (y, 0));
3703
3704 /* If Y contains our first operand (the most common way this
3705 can happen is if Y is a MEM), we would do into an infinite
3706 loop if we tried to fold it. So don't in that case. */
3707
3708 if (! reg_mentioned_p (folded_arg0, y))
3709 y = fold_rtx (y, insn);
3710
3711 return simplify_gen_binary (code, mode, y, new_const);
3712 }
3713 break;
3714
3715 case DIV: case UDIV:
3716 /* ??? The associative optimization performed immediately above is
3717 also possible for DIV and UDIV using associate_code of MULT.
3718 However, we would need extra code to verify that the
3719 multiplication does not overflow, that is, there is no overflow
3720 in the calculation of new_const. */
3721 break;
3722
3723 default:
3724 break;
3725 }
3726
3727 new_rtx = simplify_binary_operation (code, mode,
3728 const_arg0 ? const_arg0 : folded_arg0,
3729 const_arg1 ? const_arg1 : folded_arg1);
3730 break;
3731
3732 case RTX_OBJ:
3733 /* (lo_sum (high X) X) is simply X. */
3734 if (code == LO_SUM && const_arg0 != 0
3735 && GET_CODE (const_arg0) == HIGH
3736 && rtx_equal_p (XEXP (const_arg0, 0), const_arg1))
3737 return const_arg1;
3738 break;
3739
3740 case RTX_TERNARY:
3741 case RTX_BITFIELD_OPS:
3742 new_rtx = simplify_ternary_operation (code, mode, mode_arg0,
3743 const_arg0 ? const_arg0 : folded_arg0,
3744 const_arg1 ? const_arg1 : folded_arg1,
3745 const_arg2 ? const_arg2 : XEXP (x, 2));
3746 break;
3747
3748 default:
3749 break;
3750 }
3751
3752 return new_rtx ? new_rtx : x;
3753}
3754
3755/* Return a constant value currently equivalent to X.
3756 Return 0 if we don't know one. */
3757
3758static rtx
3759equiv_constant (rtx x)
3760{
3761 if (REG_P (x)
3762 && REGNO_QTY_VALID_P (REGNO (x)))
3763 {
3764 int x_q = REG_QTY (REGNO (x));
3765 struct qty_table_elem *x_ent = &qty_table[x_q];
3766
3767 if (x_ent->const_rtx)
3768 x = gen_lowpart (GET_MODE (x), x_ent->const_rtx);
3769 }
3770
3771 if (x == 0 || CONSTANT_P (x))
3772 return x;
3773
3774 if (GET_CODE (x) == SUBREG)
3775 {
3776 machine_mode mode = GET_MODE (x);
3777 machine_mode imode = GET_MODE (SUBREG_REG (x));
3778 rtx new_rtx;
3779
3780 /* See if we previously assigned a constant value to this SUBREG. */
3781 if ((new_rtx = lookup_as_function (x, CONST_INT)) != 0
3782 || (new_rtx = lookup_as_function (x, CONST_WIDE_INT)) != 0
3783 || (new_rtx = lookup_as_function (x, CONST_DOUBLE)) != 0
3784 || (new_rtx = lookup_as_function (x, CONST_FIXED)) != 0)
3785 return new_rtx;
3786
3787 /* If we didn't and if doing so makes sense, see if we previously
3788 assigned a constant value to the enclosing word mode SUBREG. */
3789 if (GET_MODE_SIZE (mode) < GET_MODE_SIZE (word_mode)
3790 && GET_MODE_SIZE (word_mode) < GET_MODE_SIZE (imode))
3791 {
3792 int byte = SUBREG_BYTE (x) - subreg_lowpart_offset (mode, word_mode);
3793 if (byte >= 0 && (byte % UNITS_PER_WORD) == 0)
3794 {
3795 rtx y = gen_rtx_SUBREG (word_mode, SUBREG_REG (x), byte);
3796 new_rtx = lookup_as_function (y, CONST_INT);
3797 if (new_rtx)
3798 return gen_lowpart (mode, new_rtx);
3799 }
3800 }
3801
3802 /* Otherwise see if we already have a constant for the inner REG,
3803 and if that is enough to calculate an equivalent constant for
3804 the subreg. Note that the upper bits of paradoxical subregs
3805 are undefined, so they cannot be said to equal anything. */
3806 if (REG_P (SUBREG_REG (x))
3807 && !paradoxical_subreg_p (x)
3808 && (new_rtx = equiv_constant (SUBREG_REG (x))) != 0)
3809 return simplify_subreg (mode, new_rtx, imode, SUBREG_BYTE (x));
3810
3811 return 0;
3812 }
3813
3814 /* If X is a MEM, see if it is a constant-pool reference, or look it up in
3815 the hash table in case its value was seen before. */
3816
3817 if (MEM_P (x))
3818 {
3819 struct table_elt *elt;
3820
3821 x = avoid_constant_pool_reference (x);
3822 if (CONSTANT_P (x))
3823 return x;
3824
3825 elt = lookup (x, SAFE_HASH (x, GET_MODE (x)), GET_MODE (x));
3826 if (elt == 0)
3827 return 0;
3828
3829 for (elt = elt->first_same_value; elt; elt = elt->next_same_value)
3830 if (elt->is_const && CONSTANT_P (elt->exp))
3831 return elt->exp;
3832 }
3833
3834 return 0;
3835}
3836
3837/* Given INSN, a jump insn, TAKEN indicates if we are following the
3838 "taken" branch.
3839
3840 In certain cases, this can cause us to add an equivalence. For example,
3841 if we are following the taken case of
3842 if (i == 2)
3843 we can add the fact that `i' and '2' are now equivalent.
3844
3845 In any case, we can record that this comparison was passed. If the same
3846 comparison is seen later, we will know its value. */
3847
3848static void
3849record_jump_equiv (rtx_insn *insn, bool taken)
3850{
3851 int cond_known_true;
3852 rtx op0, op1;
3853 rtx set;
3854 machine_mode mode, mode0, mode1;
3855 int reversed_nonequality = 0;
3856 enum rtx_code code;
3857
3858 /* Ensure this is the right kind of insn. */
3859 gcc_assert (any_condjump_p (insn));
3860
3861 set = pc_set (insn);
3862
3863 /* See if this jump condition is known true or false. */
3864 if (taken)
3865 cond_known_true = (XEXP (SET_SRC (set), 2) == pc_rtx);
3866 else
3867 cond_known_true = (XEXP (SET_SRC (set), 1) == pc_rtx);
3868
3869 /* Get the type of comparison being done and the operands being compared.
3870 If we had to reverse a non-equality condition, record that fact so we
3871 know that it isn't valid for floating-point. */
3872 code = GET_CODE (XEXP (SET_SRC (set), 0));
3873 op0 = fold_rtx (XEXP (XEXP (SET_SRC (set), 0), 0), insn);
3874 op1 = fold_rtx (XEXP (XEXP (SET_SRC (set), 0), 1), insn);
3875
3876 /* On a cc0 target the cc0-setter and cc0-user may end up in different
3877 blocks. When that happens the tracking of the cc0-setter via
3878 PREV_INSN_CC0 is spoiled. That means that fold_rtx may return
3879 NULL_RTX. In those cases, there's nothing to record. */
3880 if (op0 == NULL_RTX || op1 == NULL_RTX)
3881 return;
3882
3883 code = find_comparison_args (code, &op0, &op1, &mode0, &mode1);
3884 if (! cond_known_true)
3885 {
3886 code = reversed_comparison_code_parts (code, op0, op1, insn);
3887
3888 /* Don't remember if we can't find the inverse. */
3889 if (code == UNKNOWN)
3890 return;
3891 }
3892
3893 /* The mode is the mode of the non-constant. */
3894 mode = mode0;
3895 if (mode1 != VOIDmode)
3896 mode = mode1;
3897
3898 record_jump_cond (code, mode, op0, op1, reversed_nonequality);
3899}
3900
3901/* Yet another form of subreg creation. In this case, we want something in
3902 MODE, and we should assume OP has MODE iff it is naturally modeless. */
3903
3904static rtx
3905record_jump_cond_subreg (machine_mode mode, rtx op)
3906{
3907 machine_mode op_mode = GET_MODE (op);
3908 if (op_mode == mode || op_mode == VOIDmode)
3909 return op;
3910 return lowpart_subreg (mode, op, op_mode);
3911}
3912
3913/* We know that comparison CODE applied to OP0 and OP1 in MODE is true.
3914 REVERSED_NONEQUALITY is nonzero if CODE had to be swapped.
3915 Make any useful entries we can with that information. Called from
3916 above function and called recursively. */
3917
3918static void
3919record_jump_cond (enum rtx_code code, machine_mode mode, rtx op0,
3920 rtx op1, int reversed_nonequality)
3921{
3922 unsigned op0_hash, op1_hash;
3923 int op0_in_memory, op1_in_memory;
3924 struct table_elt *op0_elt, *op1_elt;
3925
3926 /* If OP0 and OP1 are known equal, and either is a paradoxical SUBREG,
3927 we know that they are also equal in the smaller mode (this is also
3928 true for all smaller modes whether or not there is a SUBREG, but
3929 is not worth testing for with no SUBREG). */
3930
3931 /* Note that GET_MODE (op0) may not equal MODE. */
3932 if (code == EQ && paradoxical_subreg_p (op0))
3933 {
3934 machine_mode inner_mode = GET_MODE (SUBREG_REG (op0));
3935 rtx tem = record_jump_cond_subreg (inner_mode, op1);
3936 if (tem)
3937 record_jump_cond (code, mode, SUBREG_REG (op0), tem,
3938 reversed_nonequality);
3939 }
3940
3941 if (code == EQ && paradoxical_subreg_p (op1))
3942 {
3943 machine_mode inner_mode = GET_MODE (SUBREG_REG (op1));
3944 rtx tem = record_jump_cond_subreg (inner_mode, op0);
3945 if (tem)
3946 record_jump_cond (code, mode, SUBREG_REG (op1), tem,
3947 reversed_nonequality);
3948 }
3949
3950 /* Similarly, if this is an NE comparison, and either is a SUBREG
3951 making a smaller mode, we know the whole thing is also NE. */
3952
3953 /* Note that GET_MODE (op0) may not equal MODE;
3954 if we test MODE instead, we can get an infinite recursion
3955 alternating between two modes each wider than MODE. */
3956
3957 if (code == NE
3958 && partial_subreg_p (op0)
3959 && subreg_lowpart_p (op0))
3960 {
3961 machine_mode inner_mode = GET_MODE (SUBREG_REG (op0));
3962 rtx tem = record_jump_cond_subreg (inner_mode, op1);
3963 if (tem)
3964 record_jump_cond (code, mode, SUBREG_REG (op0), tem,
3965 reversed_nonequality);
3966 }
3967
3968 if (code == NE
3969 && partial_subreg_p (op1)
3970 && subreg_lowpart_p (op1))
3971 {
3972 machine_mode inner_mode = GET_MODE (SUBREG_REG (op1));
3973 rtx tem = record_jump_cond_subreg (inner_mode, op0);
3974 if (tem)
3975 record_jump_cond (code, mode, SUBREG_REG (op1), tem,
3976 reversed_nonequality);
3977 }
3978
3979 /* Hash both operands. */
3980
3981 do_not_record = 0;
3982 hash_arg_in_memory = 0;
3983 op0_hash = HASH (op0, mode);
3984 op0_in_memory = hash_arg_in_memory;
3985
3986 if (do_not_record)
3987 return;
3988
3989 do_not_record = 0;
3990 hash_arg_in_memory = 0;
3991 op1_hash = HASH (op1, mode);
3992 op1_in_memory = hash_arg_in_memory;
3993
3994 if (do_not_record)
3995 return;
3996
3997 /* Look up both operands. */
3998 op0_elt = lookup (op0, op0_hash, mode);
3999 op1_elt = lookup (op1, op1_hash, mode);
4000
4001 /* If both operands are already equivalent or if they are not in the
4002 table but are identical, do nothing. */
4003 if ((op0_elt != 0 && op1_elt != 0
4004 && op0_elt->first_same_value == op1_elt->first_same_value)
4005 || op0 == op1 || rtx_equal_p (op0, op1))
4006 return;
4007
4008 /* If we aren't setting two things equal all we can do is save this
4009 comparison. Similarly if this is floating-point. In the latter
4010 case, OP1 might be zero and both -0.0 and 0.0 are equal to it.
4011 If we record the equality, we might inadvertently delete code
4012 whose intent was to change -0 to +0. */
4013
4014 if (code != EQ || FLOAT_MODE_P (GET_MODE (op0)))
4015 {
4016 struct qty_table_elem *ent;
4017 int qty;
4018
4019 /* If we reversed a floating-point comparison, if OP0 is not a
4020 register, or if OP1 is neither a register or constant, we can't
4021 do anything. */
4022
4023 if (!REG_P (op1))
4024 op1 = equiv_constant (op1);
4025
4026 if ((reversed_nonequality && FLOAT_MODE_P (mode))
4027 || !REG_P (op0) || op1 == 0)
4028 return;
4029
4030 /* Put OP0 in the hash table if it isn't already. This gives it a
4031 new quantity number. */
4032 if (op0_elt == 0)
4033 {
4034 if (insert_regs (op0, NULL, 0))
4035 {
4036 rehash_using_reg (op0);
4037 op0_hash = HASH (op0, mode);
4038
4039 /* If OP0 is contained in OP1, this changes its hash code
4040 as well. Faster to rehash than to check, except
4041 for the simple case of a constant. */
4042 if (! CONSTANT_P (op1))
4043 op1_hash = HASH (op1,mode);
4044 }
4045
4046 op0_elt = insert (op0, NULL, op0_hash, mode);
4047 op0_elt->in_memory = op0_in_memory;
4048 }
4049
4050 qty = REG_QTY (REGNO (op0));
4051 ent = &qty_table[qty];
4052
4053 ent->comparison_code = code;
4054 if (REG_P (op1))
4055 {
4056 /* Look it up again--in case op0 and op1 are the same. */
4057 op1_elt = lookup (op1, op1_hash, mode);
4058
4059 /* Put OP1 in the hash table so it gets a new quantity number. */
4060 if (op1_elt == 0)
4061 {
4062 if (insert_regs (op1, NULL, 0))
4063 {
4064 rehash_using_reg (op1);
4065 op1_hash = HASH (op1, mode);
4066 }
4067
4068 op1_elt = insert (op1, NULL, op1_hash, mode);
4069 op1_elt->in_memory = op1_in_memory;
4070 }
4071
4072 ent->comparison_const = NULL_RTX;
4073 ent->comparison_qty = REG_QTY (REGNO (op1));
4074 }
4075 else
4076 {
4077 ent->comparison_const = op1;
4078 ent->comparison_qty = -1;
4079 }
4080
4081 return;
4082 }
4083
4084 /* If either side is still missing an equivalence, make it now,
4085 then merge the equivalences. */
4086
4087 if (op0_elt == 0)
4088 {
4089 if (insert_regs (op0, NULL, 0))
4090 {
4091 rehash_using_reg (op0);
4092 op0_hash = HASH (op0, mode);
4093 }
4094
4095 op0_elt = insert (op0, NULL, op0_hash, mode);
4096 op0_elt->in_memory = op0_in_memory;
4097 }
4098
4099 if (op1_elt == 0)
4100 {
4101 if (insert_regs (op1, NULL, 0))
4102 {
4103 rehash_using_reg (op1);
4104 op1_hash = HASH (op1, mode);
4105 }
4106
4107 op1_elt = insert (op1, NULL, op1_hash, mode);
4108 op1_elt->in_memory = op1_in_memory;
4109 }
4110
4111 merge_equiv_classes (op0_elt, op1_elt);
4112}
4113
4114/* CSE processing for one instruction.
4115
4116 Most "true" common subexpressions are mostly optimized away in GIMPLE,
4117 but the few that "leak through" are cleaned up by cse_insn, and complex
4118 addressing modes are often formed here.
4119
4120 The main function is cse_insn, and between here and that function
4121 a couple of helper functions is defined to keep the size of cse_insn
4122 within reasonable proportions.
4123
4124 Data is shared between the main and helper functions via STRUCT SET,
4125 that contains all data related for every set in the instruction that
4126 is being processed.
4127
4128 Note that cse_main processes all sets in the instruction. Most
4129 passes in GCC only process simple SET insns or single_set insns, but
4130 CSE processes insns with multiple sets as well. */
4131
4132/* Data on one SET contained in the instruction. */
4133
4134struct set
4135{
4136 /* The SET rtx itself. */
4137 rtx rtl;
4138 /* The SET_SRC of the rtx (the original value, if it is changing). */
4139 rtx src;
4140 /* The hash-table element for the SET_SRC of the SET. */
4141 struct table_elt *src_elt;
4142 /* Hash value for the SET_SRC. */
4143 unsigned src_hash;
4144 /* Hash value for the SET_DEST. */
4145 unsigned dest_hash;
4146 /* The SET_DEST, with SUBREG, etc., stripped. */
4147 rtx inner_dest;
4148 /* Nonzero if the SET_SRC is in memory. */
4149 char src_in_memory;
4150 /* Nonzero if the SET_SRC contains something
4151 whose value cannot be predicted and understood. */
4152 char src_volatile;
4153 /* Original machine mode, in case it becomes a CONST_INT.
4154 The size of this field should match the size of the mode
4155 field of struct rtx_def (see rtl.h). */
4156 ENUM_BITFIELD(machine_mode) mode : 8;
4157 /* Hash value of constant equivalent for SET_SRC. */
4158 unsigned src_const_hash;
4159 /* A constant equivalent for SET_SRC, if any. */
4160 rtx src_const;
4161 /* Table entry for constant equivalent for SET_SRC, if any. */
4162 struct table_elt *src_const_elt;
4163 /* Table entry for the destination address. */
4164 struct table_elt *dest_addr_elt;
4165};
4166
4167/* Special handling for (set REG0 REG1) where REG0 is the
4168 "cheapest", cheaper than REG1. After cse, REG1 will probably not
4169 be used in the sequel, so (if easily done) change this insn to
4170 (set REG1 REG0) and replace REG1 with REG0 in the previous insn
4171 that computed their value. Then REG1 will become a dead store
4172 and won't cloud the situation for later optimizations.
4173
4174 Do not make this change if REG1 is a hard register, because it will
4175 then be used in the sequel and we may be changing a two-operand insn
4176 into a three-operand insn.
4177
4178 This is the last transformation that cse_insn will try to do. */
4179
4180static void
4181try_back_substitute_reg (rtx set, rtx_insn *insn)
4182{
4183 rtx dest = SET_DEST (set);
4184 rtx src = SET_SRC (set);
4185
4186 if (REG_P (dest)
4187 && REG_P (src) && ! HARD_REGISTER_P (src)
4188 && REGNO_QTY_VALID_P (REGNO (src)))
4189 {
4190 int src_q = REG_QTY (REGNO (src));
4191 struct qty_table_elem *src_ent = &qty_table[src_q];
4192
4193 if (src_ent->first_reg == REGNO (dest))
4194 {
4195 /* Scan for the previous nonnote insn, but stop at a basic
4196 block boundary. */
4197 rtx_insn *prev = insn;
4198 rtx_insn *bb_head = BB_HEAD (BLOCK_FOR_INSN (insn));
4199 do
4200 {
4201 prev = PREV_INSN (prev);
4202 }
4203 while (prev != bb_head && (NOTE_P (prev) || DEBUG_INSN_P (prev)));
4204
4205 /* Do not swap the registers around if the previous instruction
4206 attaches a REG_EQUIV note to REG1.
4207
4208 ??? It's not entirely clear whether we can transfer a REG_EQUIV
4209 from the pseudo that originally shadowed an incoming argument
4210 to another register. Some uses of REG_EQUIV might rely on it
4211 being attached to REG1 rather than REG2.
4212
4213 This section previously turned the REG_EQUIV into a REG_EQUAL
4214 note. We cannot do that because REG_EQUIV may provide an
4215 uninitialized stack slot when REG_PARM_STACK_SPACE is used. */
4216 if (NONJUMP_INSN_P (prev)
4217 && GET_CODE (PATTERN (prev)) == SET
4218 && SET_DEST (PATTERN (prev)) == src
4219 && ! find_reg_note (prev, REG_EQUIV, NULL_RTX))
4220 {
4221 rtx note;
4222
4223 validate_change (prev, &SET_DEST (PATTERN (prev)), dest, 1);
4224 validate_change (insn, &SET_DEST (set), src, 1);
4225 validate_change (insn, &SET_SRC (set), dest, 1);
4226 apply_change_group ();
4227
4228 /* If INSN has a REG_EQUAL note, and this note mentions
4229 REG0, then we must delete it, because the value in
4230 REG0 has changed. If the note's value is REG1, we must
4231 also delete it because that is now this insn's dest. */
4232 note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
4233 if (note != 0
4234 && (reg_mentioned_p (dest, XEXP (note, 0))
4235 || rtx_equal_p (src, XEXP (note, 0))))
4236 remove_note (insn, note);
4237 }
4238 }
4239 }
4240}
4241
4242/* Record all the SETs in this instruction into SETS_PTR,
4243 and return the number of recorded sets. */
4244static int
4245find_sets_in_insn (rtx_insn *insn, struct set **psets)
4246{
4247 struct set *sets = *psets;
4248 int n_sets = 0;
4249 rtx x = PATTERN (insn);
4250
4251 if (GET_CODE (x) == SET)
4252 {
4253 /* Ignore SETs that are unconditional jumps.
4254 They never need cse processing, so this does not hurt.
4255 The reason is not efficiency but rather
4256 so that we can test at the end for instructions
4257 that have been simplified to unconditional jumps
4258 and not be misled by unchanged instructions
4259 that were unconditional jumps to begin with. */
4260 if (SET_DEST (x) == pc_rtx
4261 && GET_CODE (SET_SRC (x)) == LABEL_REF)
4262 ;
4263 /* Don't count call-insns, (set (reg 0) (call ...)), as a set.
4264 The hard function value register is used only once, to copy to
4265 someplace else, so it isn't worth cse'ing. */
4266 else if (GET_CODE (SET_SRC (x)) == CALL)
4267 ;
4268 else
4269 sets[n_sets++].rtl = x;
4270 }
4271 else if (GET_CODE (x) == PARALLEL)
4272 {
4273 int i, lim = XVECLEN (x, 0);
4274
4275 /* Go over the expressions of the PARALLEL in forward order, to
4276 put them in the same order in the SETS array. */
4277 for (i = 0; i < lim; i++)
4278 {
4279 rtx y = XVECEXP (x, 0, i);
4280 if (GET_CODE (y) == SET)
4281 {
4282 /* As above, we ignore unconditional jumps and call-insns and
4283 ignore the result of apply_change_group. */
4284 if (SET_DEST (y) == pc_rtx
4285 && GET_CODE (SET_SRC (y)) == LABEL_REF)
4286 ;
4287 else if (GET_CODE (SET_SRC (y)) == CALL)
4288 ;
4289 else
4290 sets[n_sets++].rtl = y;
4291 }
4292 }
4293 }
4294
4295 return n_sets;
4296}
4297
4298/* Subroutine of canonicalize_insn. X is an ASM_OPERANDS in INSN. */
4299
4300static void
4301canon_asm_operands (rtx x, rtx_insn *insn)
4302{
4303 for (int i = ASM_OPERANDS_INPUT_LENGTH (x) - 1; i >= 0; i--)
4304 {
4305 rtx input = ASM_OPERANDS_INPUT (x, i);
4306 if (!(REG_P (input) && HARD_REGISTER_P (input)))
4307 {
4308 input = canon_reg (input, insn);
4309 validate_change (insn, &ASM_OPERANDS_INPUT (x, i), input, 1);
4310 }
4311 }
4312}
4313
4314/* Where possible, substitute every register reference in the N_SETS
4315 number of SETS in INSN with the canonical register.
4316
4317 Register canonicalization propagatest the earliest register (i.e.
4318 one that is set before INSN) with the same value. This is a very
4319 useful, simple form of CSE, to clean up warts from expanding GIMPLE
4320 to RTL. For instance, a CONST for an address is usually expanded
4321 multiple times to loads into different registers, thus creating many
4322 subexpressions of the form:
4323
4324 (set (reg1) (some_const))
4325 (set (mem (... reg1 ...) (thing)))
4326 (set (reg2) (some_const))
4327 (set (mem (... reg2 ...) (thing)))
4328
4329 After canonicalizing, the code takes the following form:
4330
4331 (set (reg1) (some_const))
4332 (set (mem (... reg1 ...) (thing)))
4333 (set (reg2) (some_const))
4334 (set (mem (... reg1 ...) (thing)))
4335
4336 The set to reg2 is now trivially dead, and the memory reference (or
4337 address, or whatever) may be a candidate for further CSEing.
4338
4339 In this function, the result of apply_change_group can be ignored;
4340 see canon_reg. */
4341
4342static void
4343canonicalize_insn (rtx_insn *insn, struct set **psets, int n_sets)
4344{
4345 struct set *sets = *psets;
4346 rtx tem;
4347 rtx x = PATTERN (insn);
4348 int i;
4349
4350 if (CALL_P (insn))
4351 {
4352 for (tem = CALL_INSN_FUNCTION_USAGE (insn); tem; tem = XEXP (tem, 1))
4353 if (GET_CODE (XEXP (tem, 0)) != SET)
4354 XEXP (tem, 0) = canon_reg (XEXP (tem, 0), insn);
4355 }
4356
4357 if (GET_CODE (x) == SET && GET_CODE (SET_SRC (x)) == CALL)
4358 {
4359 canon_reg (SET_SRC (x), insn);
4360 apply_change_group ();
4361 fold_rtx (SET_SRC (x), insn);
4362 }
4363 else if (GET_CODE (x) == CLOBBER)
4364 {
4365 /* If we clobber memory, canon the address.
4366 This does nothing when a register is clobbered
4367 because we have already invalidated the reg. */
4368 if (MEM_P (XEXP (x, 0)))
4369 canon_reg (XEXP (x, 0), insn);
4370 }
4371 else if (GET_CODE (x) == USE
4372 && ! (REG_P (XEXP (x, 0))
4373 && REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER))
4374 /* Canonicalize a USE of a pseudo register or memory location. */
4375 canon_reg (x, insn);
4376 else if (GET_CODE (x) == ASM_OPERANDS)
4377 canon_asm_operands (x, insn);
4378 else if (GET_CODE (x) == CALL)
4379 {
4380 canon_reg (x, insn);
4381 apply_change_group ();
4382 fold_rtx (x, insn);
4383 }
4384 else if (DEBUG_INSN_P (insn))
4385 canon_reg (PATTERN (insn), insn);
4386 else if (GET_CODE (x) == PARALLEL)
4387 {
4388 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
4389 {
4390 rtx y = XVECEXP (x, 0, i);
4391 if (GET_CODE (y) == SET && GET_CODE (SET_SRC (y)) == CALL)
4392 {
4393 canon_reg (SET_SRC (y), insn);
4394 apply_change_group ();
4395 fold_rtx (SET_SRC (y), insn);
4396 }
4397 else if (GET_CODE (y) == CLOBBER)
4398 {
4399 if (MEM_P (XEXP (y, 0)))
4400 canon_reg (XEXP (y, 0), insn);
4401 }
4402 else if (GET_CODE (y) == USE
4403 && ! (REG_P (XEXP (y, 0))
4404 && REGNO (XEXP (y, 0)) < FIRST_PSEUDO_REGISTER))
4405 canon_reg (y, insn);
4406 else if (GET_CODE (y) == ASM_OPERANDS)
4407 canon_asm_operands (y, insn);
4408 else if (GET_CODE (y) == CALL)
4409 {
4410 canon_reg (y, insn);
4411 apply_change_group ();
4412 fold_rtx (y, insn);
4413 }
4414 }
4415 }
4416
4417 if (n_sets == 1 && REG_NOTES (insn) != 0
4418 && (tem = find_reg_note (insn, REG_EQUAL, NULL_RTX)) != 0)
4419 {
4420 /* We potentially will process this insn many times. Therefore,
4421 drop the REG_EQUAL note if it is equal to the SET_SRC of the
4422 unique set in INSN.
4423
4424 Do not do so if the REG_EQUAL note is for a STRICT_LOW_PART,
4425 because cse_insn handles those specially. */
4426 if (GET_CODE (SET_DEST (sets[0].rtl)) != STRICT_LOW_PART
4427 && rtx_equal_p (XEXP (tem, 0), SET_SRC (sets[0].rtl)))
4428 remove_note (insn, tem);
4429 else
4430 {
4431 canon_reg (XEXP (tem, 0), insn);
4432 apply_change_group ();
4433 XEXP (tem, 0) = fold_rtx (XEXP (tem, 0), insn);
4434 df_notes_rescan (insn);
4435 }
4436 }
4437
4438 /* Canonicalize sources and addresses of destinations.
4439 We do this in a separate pass to avoid problems when a MATCH_DUP is
4440 present in the insn pattern. In that case, we want to ensure that
4441 we don't break the duplicate nature of the pattern. So we will replace
4442 both operands at the same time. Otherwise, we would fail to find an
4443 equivalent substitution in the loop calling validate_change below.
4444
4445 We used to suppress canonicalization of DEST if it appears in SRC,
4446 but we don't do this any more. */
4447
4448 for (i = 0; i < n_sets; i++)
4449 {
4450 rtx dest = SET_DEST (sets[i].rtl);
4451 rtx src = SET_SRC (sets[i].rtl);
4452 rtx new_rtx = canon_reg (src, insn);
4453
4454 validate_change (insn, &SET_SRC (sets[i].rtl), new_rtx, 1);
4455
4456 if (GET_CODE (dest) == ZERO_EXTRACT)
4457 {
4458 validate_change (insn, &XEXP (dest, 1),
4459 canon_reg (XEXP (dest, 1), insn), 1);
4460 validate_change (insn, &XEXP (dest, 2),
4461 canon_reg (XEXP (dest, 2), insn), 1);
4462 }
4463
4464 while (GET_CODE (dest) == SUBREG
4465 || GET_CODE (dest) == ZERO_EXTRACT
4466 || GET_CODE (dest) == STRICT_LOW_PART)
4467 dest = XEXP (dest, 0);
4468
4469 if (MEM_P (dest))
4470 canon_reg (dest, insn);
4471 }
4472
4473 /* Now that we have done all the replacements, we can apply the change
4474 group and see if they all work. Note that this will cause some
4475 canonicalizations that would have worked individually not to be applied
4476 because some other canonicalization didn't work, but this should not
4477 occur often.
4478
4479 The result of apply_change_group can be ignored; see canon_reg. */
4480
4481 apply_change_group ();
4482}
4483
4484/* Main function of CSE.
4485 First simplify sources and addresses of all assignments
4486 in the instruction, using previously-computed equivalents values.
4487 Then install the new sources and destinations in the table
4488 of available values. */
4489
4490static void
4491cse_insn (rtx_insn *insn)
4492{
4493 rtx x = PATTERN (insn);
4494 int i;
4495 rtx tem;
4496 int n_sets = 0;
4497
4498 rtx src_eqv = 0;
4499 struct table_elt *src_eqv_elt = 0;
4500 int src_eqv_volatile = 0;
4501 int src_eqv_in_memory = 0;
4502 unsigned src_eqv_hash = 0;
4503
4504 struct set *sets = (struct set *) 0;
4505
4506 if (GET_CODE (x) == SET)
4507 sets = XALLOCA (struct set);
4508 else if (GET_CODE (x) == PARALLEL)
4509 sets = XALLOCAVEC (struct set, XVECLEN (x, 0));
4510
4511 this_insn = insn;
4512 /* Records what this insn does to set CC0. */
4513 this_insn_cc0 = 0;
4514 this_insn_cc0_mode = VOIDmode;
4515
4516 /* Find all regs explicitly clobbered in this insn,
4517 to ensure they are not replaced with any other regs
4518 elsewhere in this insn. */
4519 invalidate_from_sets_and_clobbers (insn);
4520
4521 /* Record all the SETs in this instruction. */
4522 n_sets = find_sets_in_insn (insn, &sets);
4523
4524 /* Substitute the canonical register where possible. */
4525 canonicalize_insn (insn, &sets, n_sets);
4526
4527 /* If this insn has a REG_EQUAL note, store the equivalent value in SRC_EQV,
4528 if different, or if the DEST is a STRICT_LOW_PART/ZERO_EXTRACT. The
4529 latter condition is necessary because SRC_EQV is handled specially for
4530 this case, and if it isn't set, then there will be no equivalence
4531 for the destination. */
4532 if (n_sets == 1 && REG_NOTES (insn) != 0
4533 && (tem = find_reg_note (insn, REG_EQUAL, NULL_RTX)) != 0)
4534 {
4535
4536 if (GET_CODE (SET_DEST (sets[0].rtl)) != ZERO_EXTRACT
4537 && (! rtx_equal_p (XEXP (tem, 0), SET_SRC (sets[0].rtl))
4538 || GET_CODE (SET_DEST (sets[0].rtl)) == STRICT_LOW_PART))
4539 src_eqv = copy_rtx (XEXP (tem, 0));
4540 /* If DEST is of the form ZERO_EXTACT, as in:
4541 (set (zero_extract:SI (reg:SI 119)
4542 (const_int 16 [0x10])
4543 (const_int 16 [0x10]))
4544 (const_int 51154 [0xc7d2]))
4545 REG_EQUAL note will specify the value of register (reg:SI 119) at this
4546 point. Note that this is different from SRC_EQV. We can however
4547 calculate SRC_EQV with the position and width of ZERO_EXTRACT. */
4548 else if (GET_CODE (SET_DEST (sets[0].rtl)) == ZERO_EXTRACT
4549 && CONST_INT_P (XEXP (tem, 0))
4550 && CONST_INT_P (XEXP (SET_DEST (sets[0].rtl), 1))
4551 && CONST_INT_P (XEXP (SET_DEST (sets[0].rtl), 2)))
4552 {
4553 rtx dest_reg = XEXP (SET_DEST (sets[0].rtl), 0);
4554 /* This is the mode of XEXP (tem, 0) as well. */
4555 scalar_int_mode dest_mode
4556 = as_a <scalar_int_mode> (GET_MODE (dest_reg));
4557 rtx width = XEXP (SET_DEST (sets[0].rtl), 1);
4558 rtx pos = XEXP (SET_DEST (sets[0].rtl), 2);
4559 HOST_WIDE_INT val = INTVAL (XEXP (tem, 0));
4560 HOST_WIDE_INT mask;
4561 unsigned int shift;
4562 if (BITS_BIG_ENDIAN)
4563 shift = (GET_MODE_PRECISION (dest_mode)
4564 - INTVAL (pos) - INTVAL (width));
4565 else
4566 shift = INTVAL (pos);
4567 if (INTVAL (width) == HOST_BITS_PER_WIDE_INT)
4568 mask = HOST_WIDE_INT_M1;
4569 else
4570 mask = (HOST_WIDE_INT_1 << INTVAL (width)) - 1;
4571 val = (val >> shift) & mask;
4572 src_eqv = GEN_INT (val);
4573 }
4574 }
4575
4576 /* Set sets[i].src_elt to the class each source belongs to.
4577 Detect assignments from or to volatile things
4578 and set set[i] to zero so they will be ignored
4579 in the rest of this function.
4580
4581 Nothing in this loop changes the hash table or the register chains. */
4582
4583 for (i = 0; i < n_sets; i++)
4584 {
4585 bool repeat = false;
4586 bool mem_noop_insn = false;
4587 rtx src, dest;
4588 rtx src_folded;
4589 struct table_elt *elt = 0, *p;
4590 machine_mode mode;
4591 rtx src_eqv_here;
4592 rtx src_const = 0;
4593 rtx src_related = 0;
4594 bool src_related_is_const_anchor = false;
4595 struct table_elt *src_const_elt = 0;
4596 int src_cost = MAX_COST;
4597 int src_eqv_cost = MAX_COST;
4598 int src_folded_cost = MAX_COST;
4599 int src_related_cost = MAX_COST;
4600 int src_elt_cost = MAX_COST;
4601 int src_regcost = MAX_COST;
4602 int src_eqv_regcost = MAX_COST;
4603 int src_folded_regcost = MAX_COST;
4604 int src_related_regcost = MAX_COST;
4605 int src_elt_regcost = MAX_COST;
4606 /* Set nonzero if we need to call force_const_mem on with the
4607 contents of src_folded before using it. */
4608 int src_folded_force_flag = 0;
4609 scalar_int_mode int_mode;
4610
4611 dest = SET_DEST (sets[i].rtl);
4612 src = SET_SRC (sets[i].rtl);
4613
4614 /* If SRC is a constant that has no machine mode,
4615 hash it with the destination's machine mode.
4616 This way we can keep different modes separate. */
4617
4618 mode = GET_MODE (src) == VOIDmode ? GET_MODE (dest) : GET_MODE (src);
4619 sets[i].mode = mode;
4620
4621 if (src_eqv)
4622 {
4623 machine_mode eqvmode = mode;
4624 if (GET_CODE (dest) == STRICT_LOW_PART)
4625 eqvmode = GET_MODE (SUBREG_REG (XEXP (dest, 0)));
4626 do_not_record = 0;
4627 hash_arg_in_memory = 0;
4628 src_eqv_hash = HASH (src_eqv, eqvmode);
4629
4630 /* Find the equivalence class for the equivalent expression. */
4631
4632 if (!do_not_record)
4633 src_eqv_elt = lookup (src_eqv, src_eqv_hash, eqvmode);
4634
4635 src_eqv_volatile = do_not_record;
4636 src_eqv_in_memory = hash_arg_in_memory;
4637 }
4638
4639 /* If this is a STRICT_LOW_PART assignment, src_eqv corresponds to the
4640 value of the INNER register, not the destination. So it is not
4641 a valid substitution for the source. But save it for later. */
4642 if (GET_CODE (dest) == STRICT_LOW_PART)
4643 src_eqv_here = 0;
4644 else
4645 src_eqv_here = src_eqv;
4646
4647 /* Simplify and foldable subexpressions in SRC. Then get the fully-
4648 simplified result, which may not necessarily be valid. */
4649 src_folded = fold_rtx (src, NULL);
4650
4651#if 0
4652 /* ??? This caused bad code to be generated for the m68k port with -O2.
4653 Suppose src is (CONST_INT -1), and that after truncation src_folded
4654 is (CONST_INT 3). Suppose src_folded is then used for src_const.
4655 At the end we will add src and src_const to the same equivalence
4656 class. We now have 3 and -1 on the same equivalence class. This
4657 causes later instructions to be mis-optimized. */
4658 /* If storing a constant in a bitfield, pre-truncate the constant
4659 so we will be able to record it later. */
4660 if (GET_CODE (SET_DEST (sets[i].rtl)) == ZERO_EXTRACT)
4661 {
4662 rtx width = XEXP (SET_DEST (sets[i].rtl), 1);
4663
4664 if (CONST_INT_P (src)
4665 && CONST_INT_P (width)
4666 && INTVAL (width) < HOST_BITS_PER_WIDE_INT
4667 && (INTVAL (src) & ((HOST_WIDE_INT) (-1) << INTVAL (width))))
4668 src_folded
4669 = GEN_INT (INTVAL (src) & ((HOST_WIDE_INT_1
4670 << INTVAL (width)) - 1));
4671 }
4672#endif
4673
4674 /* Compute SRC's hash code, and also notice if it
4675 should not be recorded at all. In that case,
4676 prevent any further processing of this assignment. */
4677 do_not_record = 0;
4678 hash_arg_in_memory = 0;
4679
4680 sets[i].src = src;
4681 sets[i].src_hash = HASH (src, mode);
4682 sets[i].src_volatile = do_not_record;
4683 sets[i].src_in_memory = hash_arg_in_memory;
4684
4685 /* If SRC is a MEM, there is a REG_EQUIV note for SRC, and DEST is
4686 a pseudo, do not record SRC. Using SRC as a replacement for
4687 anything else will be incorrect in that situation. Note that
4688 this usually occurs only for stack slots, in which case all the
4689 RTL would be referring to SRC, so we don't lose any optimization
4690 opportunities by not having SRC in the hash table. */
4691
4692 if (MEM_P (src)
4693 && find_reg_note (insn, REG_EQUIV, NULL_RTX) != 0
4694 && REG_P (dest)
4695 && REGNO (dest) >= FIRST_PSEUDO_REGISTER)
4696 sets[i].src_volatile = 1;
4697
4698 else if (GET_CODE (src) == ASM_OPERANDS
4699 && GET_CODE (x) == PARALLEL)
4700 {
4701 /* Do not record result of a non-volatile inline asm with
4702 more than one result. */
4703 if (n_sets > 1)
4704 sets[i].src_volatile = 1;
4705
4706 int j, lim = XVECLEN (x, 0);
4707 for (j = 0; j < lim; j++)
4708 {
4709 rtx y = XVECEXP (x, 0, j);
4710 /* And do not record result of a non-volatile inline asm
4711 with "memory" clobber. */
4712 if (GET_CODE (y) == CLOBBER && MEM_P (XEXP (y, 0)))
4713 {
4714 sets[i].src_volatile = 1;
4715 break;
4716 }
4717 }
4718 }
4719
4720#if 0
4721 /* It is no longer clear why we used to do this, but it doesn't
4722 appear to still be needed. So let's try without it since this
4723 code hurts cse'ing widened ops. */
4724 /* If source is a paradoxical subreg (such as QI treated as an SI),
4725 treat it as volatile. It may do the work of an SI in one context
4726 where the extra bits are not being used, but cannot replace an SI
4727 in general. */
4728 if (paradoxical_subreg_p (src))
4729 sets[i].src_volatile = 1;
4730#endif
4731
4732 /* Locate all possible equivalent forms for SRC. Try to replace
4733 SRC in the insn with each cheaper equivalent.
4734
4735 We have the following types of equivalents: SRC itself, a folded
4736 version, a value given in a REG_EQUAL note, or a value related
4737 to a constant.
4738
4739 Each of these equivalents may be part of an additional class
4740 of equivalents (if more than one is in the table, they must be in
4741 the same class; we check for this).
4742
4743 If the source is volatile, we don't do any table lookups.
4744
4745 We note any constant equivalent for possible later use in a
4746 REG_NOTE. */
4747
4748 if (!sets[i].src_volatile)
4749 elt = lookup (src, sets[i].src_hash, mode);
4750
4751 sets[i].src_elt = elt;
4752
4753 if (elt && src_eqv_here && src_eqv_elt)
4754 {
4755 if (elt->first_same_value != src_eqv_elt->first_same_value)
4756 {
4757 /* The REG_EQUAL is indicating that two formerly distinct
4758 classes are now equivalent. So merge them. */
4759 merge_equiv_classes (elt, src_eqv_elt);
4760 src_eqv_hash = HASH (src_eqv, elt->mode);
4761 src_eqv_elt = lookup (src_eqv, src_eqv_hash, elt->mode);
4762 }
4763
4764 src_eqv_here = 0;
4765 }
4766
4767 else if (src_eqv_elt)
4768 elt = src_eqv_elt;
4769
4770 /* Try to find a constant somewhere and record it in `src_const'.
4771 Record its table element, if any, in `src_const_elt'. Look in
4772 any known equivalences first. (If the constant is not in the
4773 table, also set `sets[i].src_const_hash'). */
4774 if (elt)
4775 for (p = elt->first_same_value; p; p = p->next_same_value)
4776 if (p->is_const)
4777 {
4778 src_const = p->exp;
4779 src_const_elt = elt;
4780 break;
4781 }
4782
4783 if (src_const == 0
4784 && (CONSTANT_P (src_folded)
4785 /* Consider (minus (label_ref L1) (label_ref L2)) as
4786 "constant" here so we will record it. This allows us
4787 to fold switch statements when an ADDR_DIFF_VEC is used. */
4788 || (GET_CODE (src_folded) == MINUS
4789 && GET_CODE (XEXP (src_folded, 0)) == LABEL_REF
4790 && GET_CODE (XEXP (src_folded, 1)) == LABEL_REF)))
4791 src_const = src_folded, src_const_elt = elt;
4792 else if (src_const == 0 && src_eqv_here && CONSTANT_P (src_eqv_here))
4793 src_const = src_eqv_here, src_const_elt = src_eqv_elt;
4794
4795 /* If we don't know if the constant is in the table, get its
4796 hash code and look it up. */
4797 if (src_const && src_const_elt == 0)
4798 {
4799 sets[i].src_const_hash = HASH (src_const, mode);
4800 src_const_elt = lookup (src_const, sets[i].src_const_hash, mode);
4801 }
4802
4803 sets[i].src_const = src_const;
4804 sets[i].src_const_elt = src_const_elt;
4805
4806 /* If the constant and our source are both in the table, mark them as
4807 equivalent. Otherwise, if a constant is in the table but the source
4808 isn't, set ELT to it. */
4809 if (src_const_elt && elt
4810 && src_const_elt->first_same_value != elt->first_same_value)
4811 merge_equiv_classes (elt, src_const_elt);
4812 else if (src_const_elt && elt == 0)
4813 elt = src_const_elt;
4814
4815 /* See if there is a register linearly related to a constant
4816 equivalent of SRC. */
4817 if (src_const
4818 && (GET_CODE (src_const) == CONST
4819 || (src_const_elt && src_const_elt->related_value != 0)))
4820 {
4821 src_related = use_related_value (src_const, src_const_elt);
4822 if (src_related)
4823 {
4824 struct table_elt *src_related_elt
4825 = lookup (src_related, HASH (src_related, mode), mode);
4826 if (src_related_elt && elt)
4827 {
4828 if (elt->first_same_value
4829 != src_related_elt->first_same_value)
4830 /* This can occur when we previously saw a CONST
4831 involving a SYMBOL_REF and then see the SYMBOL_REF
4832 twice. Merge the involved classes. */
4833 merge_equiv_classes (elt, src_related_elt);
4834
4835 src_related = 0;
4836 src_related_elt = 0;
4837 }
4838 else if (src_related_elt && elt == 0)
4839 elt = src_related_elt;
4840 }
4841 }
4842
4843 /* See if we have a CONST_INT that is already in a register in a
4844 wider mode. */
4845
4846 if (src_const && src_related == 0 && CONST_INT_P (src_const)
4847 && is_int_mode (mode, &int_mode)
4848 && GET_MODE_PRECISION (int_mode) < BITS_PER_WORD)
4849 {
4850 opt_scalar_int_mode wider_mode_iter;
4851 FOR_EACH_WIDER_MODE (wider_mode_iter, int_mode)
4852 {
4853 scalar_int_mode wider_mode = wider_mode_iter.require ();
4854 if (GET_MODE_PRECISION (wider_mode) > BITS_PER_WORD)
4855 break;
4856
4857 struct table_elt *const_elt
4858 = lookup (src_const, HASH (src_const, wider_mode), wider_mode);
4859
4860 if (const_elt == 0)
4861 continue;
4862
4863 for (const_elt = const_elt->first_same_value;
4864 const_elt; const_elt = const_elt->next_same_value)
4865 if (REG_P (const_elt->exp))
4866 {
4867 src_related = gen_lowpart (int_mode, const_elt->exp);
4868 break;
4869 }
4870
4871 if (src_related != 0)
4872 break;
4873 }
4874 }
4875
4876 /* Another possibility is that we have an AND with a constant in
4877 a mode narrower than a word. If so, it might have been generated
4878 as part of an "if" which would narrow the AND. If we already
4879 have done the AND in a wider mode, we can use a SUBREG of that
4880 value. */
4881
4882 if (flag_expensive_optimizations && ! src_related
4883 && is_a <scalar_int_mode> (mode, &int_mode)
4884 && GET_CODE (src) == AND && CONST_INT_P (XEXP (src, 1))
4885 && GET_MODE_SIZE (int_mode) < UNITS_PER_WORD)
4886 {
4887 opt_scalar_int_mode tmode_iter;
4888 rtx new_and = gen_rtx_AND (VOIDmode, NULL_RTX, XEXP (src, 1));
4889
4890 FOR_EACH_WIDER_MODE (tmode_iter, int_mode)
4891 {
4892 scalar_int_mode tmode = tmode_iter.require ();
4893 if (GET_MODE_SIZE (tmode) > UNITS_PER_WORD)
4894 break;
4895
4896 rtx inner = gen_lowpart (tmode, XEXP (src, 0));
4897 struct table_elt *larger_elt;
4898
4899 if (inner)
4900 {
4901 PUT_MODE (new_and, tmode);
4902 XEXP (new_and, 0) = inner;
4903 larger_elt = lookup (new_and, HASH (new_and, tmode), tmode);
4904 if (larger_elt == 0)
4905 continue;
4906
4907 for (larger_elt = larger_elt->first_same_value;
4908 larger_elt; larger_elt = larger_elt->next_same_value)
4909 if (REG_P (larger_elt->exp))
4910 {
4911 src_related
4912 = gen_lowpart (int_mode, larger_elt->exp);
4913 break;
4914 }
4915
4916 if (src_related)
4917 break;
4918 }
4919 }
4920 }
4921
4922 /* See if a MEM has already been loaded with a widening operation;
4923 if it has, we can use a subreg of that. Many CISC machines
4924 also have such operations, but this is only likely to be
4925 beneficial on these machines. */
4926
4927 rtx_code extend_op;
4928 if (flag_expensive_optimizations && src_related == 0
4929 && MEM_P (src) && ! do_not_record
4930 && is_a <scalar_int_mode> (mode, &int_mode)
4931 && (extend_op = load_extend_op (int_mode)) != UNKNOWN)
4932 {
4933 struct rtx_def memory_extend_buf;
4934 rtx memory_extend_rtx = &memory_extend_buf;
4935
4936 /* Set what we are trying to extend and the operation it might
4937 have been extended with. */
4938 memset (memory_extend_rtx, 0, sizeof (*memory_extend_rtx));
4939 PUT_CODE (memory_extend_rtx, extend_op);
4940 XEXP (memory_extend_rtx, 0) = src;
4941
4942 opt_scalar_int_mode tmode_iter;
4943 FOR_EACH_WIDER_MODE (tmode_iter, int_mode)
4944 {
4945 struct table_elt *larger_elt;
4946
4947 scalar_int_mode tmode = tmode_iter.require ();
4948 if (GET_MODE_SIZE (tmode) > UNITS_PER_WORD)
4949 break;
4950
4951 PUT_MODE (memory_extend_rtx, tmode);
4952 larger_elt = lookup (memory_extend_rtx,
4953 HASH (memory_extend_rtx, tmode), tmode);
4954 if (larger_elt == 0)
4955 continue;
4956
4957 for (larger_elt = larger_elt->first_same_value;
4958 larger_elt; larger_elt = larger_elt->next_same_value)
4959 if (REG_P (larger_elt->exp))
4960 {
4961 src_related = gen_lowpart (int_mode, larger_elt->exp);
4962 break;
4963 }
4964
4965 if (src_related)
4966 break;
4967 }
4968 }
4969
4970 /* Try to express the constant using a register+offset expression
4971 derived from a constant anchor. */
4972
4973 if (targetm.const_anchor
4974 && !src_related
4975 && src_const
4976 && GET_CODE (src_const) == CONST_INT)
4977 {
4978 src_related = try_const_anchors (src_const, mode);
4979 src_related_is_const_anchor = src_related != NULL_RTX;
4980 }
4981
4982
4983 if (src == src_folded)
4984 src_folded = 0;
4985
4986 /* At this point, ELT, if nonzero, points to a class of expressions
4987 equivalent to the source of this SET and SRC, SRC_EQV, SRC_FOLDED,
4988 and SRC_RELATED, if nonzero, each contain additional equivalent
4989 expressions. Prune these latter expressions by deleting expressions
4990 already in the equivalence class.
4991
4992 Check for an equivalent identical to the destination. If found,
4993 this is the preferred equivalent since it will likely lead to
4994 elimination of the insn. Indicate this by placing it in
4995 `src_related'. */
4996
4997 if (elt)
4998 elt = elt->first_same_value;
4999 for (p = elt; p; p = p->next_same_value)
5000 {
5001 enum rtx_code code = GET_CODE (p->exp);
5002
5003 /* If the expression is not valid, ignore it. Then we do not
5004 have to check for validity below. In most cases, we can use
5005 `rtx_equal_p', since canonicalization has already been done. */
5006 if (code != REG && ! exp_equiv_p (p->exp, p->exp, 1, false))
5007 continue;
5008
5009 /* Also skip paradoxical subregs, unless that's what we're
5010 looking for. */
5011 if (paradoxical_subreg_p (p->exp)
5012 && ! (src != 0
5013 && GET_CODE (src) == SUBREG
5014 && GET_MODE (src) == GET_MODE (p->exp)
5015 && partial_subreg_p (GET_MODE (SUBREG_REG (src)),
5016 GET_MODE (SUBREG_REG (p->exp)))))