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