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