![[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 [Research Unix] / researchv10dc / cmd / gcc|
Return to cse.c CVS log | Up to [Research Unix] / researchv10dc / cmd / gcc |
1.1 root 1: /* Common subexpression elimination for GNU compiler.
2: Copyright (C) 1987, 1988 Free Software Foundation, Inc.
3:
4: This file is part of GNU CC.
5:
6: GNU CC is distributed in the hope that it will be useful,
7: but WITHOUT ANY WARRANTY. No author or distributor
8: accepts responsibility to anyone for the consequences of using it
9: or for whether it serves any particular purpose or works at all,
10: unless he says so in writing. Refer to the GNU CC General Public
11: License for full details.
12:
13: Everyone is granted permission to copy, modify and redistribute
14: GNU CC, but only under the conditions described in the
15: GNU CC General Public License. A copy of this license is
16: supposed to have been given to you along with GNU CC so you
17: can know your rights and responsibilities. It should be in a
18: file named COPYING. Among other things, the copyright notice
19: and this notice must be preserved on all copies. */
20:
21:
22: #include "config.h"
23: #include "rtl.h"
24: #include "insn-config.h"
25: #include "regs.h"
26: #include "hard-reg-set.h"
27:
28: /* The basic idea of common subexpression elimination is to go
29: through the code, keeping a record of expressions that would
30: have the same value at the current scan point, and replacing
31: expressions encountered with the cheapest equivalent expression.
32:
33: It is too complicated to keep track of the different possibilities
34: when control paths merge; so, at each label, we forget all that is
35: known and start fresh. This can be described as processing each
36: basic block separately. Note, however, that these are not quite
37: the same as the basic blocks found by a later pass and used for
38: data flow analysis and register packing. We do not need to start fresh
39: after a conditional jump instruction if there is no label there.
40:
41: We use two data structures to record the equivalent expressions:
42: a hash table for most expressions, and several vectors together
43: with "quantity numbers" to record equivalent (pseudo) registers.
44:
45: The use of the special data structure for registers is desirable
46: because it is faster. It is possible because registers references
47: contain a fairly small number, the register number, taken from
48: a contiguously allocated series, and two register references are
49: identical if they have the same number. General expressions
50: do not have any such thing, so the only way to retrieve the
51: information recorded on an expression other than a register
52: is to keep it in a hash table.
53:
54: Registers and "quantity numbers":
55:
56: At the start of each basic block, all of the (hardware and pseudo)
57: registers used in the function are given distinct quantity
58: numbers to indicate their contents. During scan, when the code
59: copies one register into another, we copy the quantity number.
60: When a register is loaded in any other way, we allocate a new
61: quantity number to describe the value generated by this operation.
62: `reg_qty' records what quantity a register is currently thought
63: of as containing.
64:
65: We also maintain a bidirectional chain of registers for each
66: quantity number. `qty_first_reg', `qty_last_reg',
67: `reg_next_eqv' and `reg_prev_eqv' hold these chains.
68:
69: The first register in a chain is the one whose lifespan is least local.
70: Among equals, it is the one that was seen first.
71: We replace any equivalent register with that one.
72:
73: Constants and quantity numbers
74:
75: When a quantity has a known constant value, that value is stored
76: in the appropriate element of qty_const. This is in addition to
77: putting the constant in the hash table as is usual for non-regs.
78:
79: Regs are preferred to constants as they are to everything else,
80: but expressions containing constants can be simplified, by fold_rtx.
81:
82: When a quantity has a known nearly constant value (such as an address
83: of a stack slot), that value is stored in the appropriate element
84: of qty_const.
85:
86: Integer constants don't have a machine mode. However, cse
87: determines the intended machine mode from the destination
88: of the instruction that moves the constant. The machine mode
89: is recorded in the hash table along with the actual RTL
90: constant expression so that different modes are kept separate.
91:
92: Other expressions:
93:
94: To record known equivalences among expressions in general
95: we use a hash table called `table'. It has a fixed number of buckets
96: that contain chains of `struct table_elt' elements for expressions.
97: These chains connect the elements whose expressions have the same
98: hash codes.
99:
100: Other chains through the same elements connect the elements which
101: currently have equivalent values.
102:
103: Register references in an expression are canonicalized before hashing
104: the expression. This is done using `reg_qty' and `qty_first_reg'.
105: The hash code of a register reference is computed using the quantity
106: number, not the register number.
107:
108: When the value of an expression changes, it is necessary to remove from the
109: hash table not just that expression but all expressions whose values
110: could be different as a result.
111:
112: 1. If the value changing is in memory, except in special cases
113: ANYTHING referring to memory could be changed. That is because
114: nobody knows where a pointer does not point.
115: The function `invalidate_memory' removes what is necessary.
116:
117: The special cases are when the address is constant or is
118: a constant plus a fixed register such as the frame pointer
119: or a static chain pointer. When such addresses are stored in,
120: we can tell exactly which other such addresses must be invalidated
121: due to overlap. `invalidate' does this.
122: All expressions that refer to non-constant
123: memory addresses are also invalidated. `invalidate_memory' does this.
124:
125: 2. If the value changing is a register, all expressions
126: containing references to that register, and only those,
127: must be removed.
128:
129: Because searching the entire hash table for expressions that contain
130: a register is very slow, we try to figure out when it isn't necessary.
131: Precisely, this is necessary only when expressions have been
132: entered in the hash table using this register, and then the value has
133: changed, and then another expression wants to be added to refer to
134: teh register's new value. This sequence of circumstances is rare
135: within any one basic block.
136:
137: The vectors `reg_tick' and `reg_in_table' are used to detect this case.
138: reg_tick[i] is incremented whenever a value is stored in register i.
139: reg_in_table[i] holds -1 if no references to register i have been
140: entered in the table; otherwise, it contains the value reg_tick[i] had
141: when the references were entered. If we want to enter a reference
142: and reg_in_table[i] != reg_tick[i], we must scan and remove old references.
143: Until we want to enter a new entry, the mere fact that the twovectors
144: don't match makes the entries be ignored if anyone tries to match them.
145:
146: Registers themselves are entered in the hash table as well as in
147: the equivalent-register chains. However, the vectors `reg_tick'
148: and `reg_in_table' do not apply to expressions which are simple
149: register references. These expressions are removed from the table
150: immediately when they become invalid, and this can be done even if
151: we do not immediately search for all the expressions that refer to
152: the register.
153:
154: A CLOBBER rtx in an instruction invalidates its operand for further
155: reuse. A CLOBBER or SET rtx whose operand is a MEM:BLK
156: invalidates everything that resides in memory.
157:
158: Related expressions:
159:
160: Constant expressions that differ only by an additive integer
161: are called related. When a constant expression is put in
162: the table, the related expression with no constant term
163: is also entered. These are made to point at each other
164: so that it is possible to find out if there exists any
165: register equivalent to an expression related to a given expression. */
166:
167: /* One plus largest register number used in this function. */
168:
169: static int max_reg;
170:
171: /* Length of vectors indexed by quantity number.
172: We know in advance we will not need a quantity number this big. */
173:
174: static int max_qty;
175:
176: /* Next quantity number to be allocated.
177: This is 1 + the largest number needed so far. */
178:
179: static int next_qty;
180:
181: /* Indexed by quantity number, gives the first (or last) (pseudo) register
182: in the chain of registers that currently contain this quantity. */
183:
184: static int *qty_first_reg;
185: static int *qty_last_reg;
186:
187: /* Indexed by quantity number, gives the rtx of the constant value of the
188: quantity, or zero if it does not have a known value.
189: A sum of the frame pointer (or arg pointer) plus a constant
190: can also be entered here. */
191:
192: static rtx *qty_const;
193:
194: /* Indexed by qty number, gives the insn that stored the constant value
195: recorded in `qty_const'. */
196:
197: static rtx *qty_const_insn;
198:
199: /* Value stored in CC0 by previous insn:
200: 0 if previous insn didn't store in CC0.
201: else 0100 + (M&7)<<3 + (N&7)
202: where M is 1, 0 or -1 if result was >, == or < as signed number
203: and N is 1, 0 or -1 if result was >, == or < as unsigned number.
204: 0200 bit may also be set, meaning that only == and != comparisons
205: have known results. */
206:
207: static int prev_insn_cc0;
208:
209: /* Previous actual insn. 0 if at first insn of basic block. */
210:
211: static rtx prev_insn;
212:
213: /* Insn being scanned. */
214:
215: static rtx this_insn;
216:
217: /* Index by (pseudo) register number, gives the quantity number
218: of the register's current contents. */
219:
220: static int *reg_qty;
221:
222: /* Index by (pseudo) register number, gives the number of the next
223: (pseudo) register in the chain of registers sharing the same value.
224: Or -1 if this register is at the end of the chain. */
225:
226: static int *reg_next_eqv;
227:
228: /* Index by (pseudo) register number, gives the number of the previous
229: (pseudo) register in the chain of registers sharing the same value.
230: Or -1 if this register is at the beginning of the chain. */
231:
232: static int *reg_prev_eqv;
233:
234: /* Index by (pseudo) register number, gives the latest rtx
235: to use to insert a ref to that register. */
236:
237: static rtx *reg_rtx;
238:
239: /* Index by (pseudo) register number, gives the number of times
240: that register has been altered in the current basic block. */
241:
242: static int *reg_tick;
243:
244: /* Index by (pseudo) register number, gives the reg_tick value at which
245: rtx's containing this register are valid in the hash table.
246: If this does not equal the current reg_tick value, such expressions
247: existing in the hash table are invalid.
248: If this is -1, no expressions containing this register have been
249: entered in the table. */
250:
251: static int *reg_in_table;
252:
253: /* Two vectors of max_reg ints:
254: one containing all -1's; in the other, element i contains i.
255: These are used to initialize various other vectors fast. */
256:
257: static int *all_minus_one;
258: static int *consec_ints;
259:
260: /* UID of insn that starts the basic block currently being cse-processed. */
261:
262: static int cse_basic_block_start;
263:
264: /* UID of insn that ends the basic block currently being cse-processed. */
265:
266: static int cse_basic_block_end;
267:
268: /* Nonzero if cse has altered conditional jump insns
269: in such a way that jump optimization should be redone. */
270:
271: static int cse_jumps_altered;
272:
273: /* canon_hash stores 1 in do_not_record
274: if it notices a reference to CC0, CC1 or PC. */
275:
276: static int do_not_record;
277:
278: /* canon_hash stores 1 in hash_arg_in_memory
279: if it notices a reference to memory within the expression being hashed. */
280:
281: static int hash_arg_in_memory;
282:
283: /* canon_hash stores 1 in hash_arg_in_struct
284: if it notices a reference to memory that's part of a structure. */
285:
286: static int hash_arg_in_struct;
287:
288: /* The hash table contains buckets which are chains of `struct table_elt's,
289: each recording one expression's information.
290: That expression is in the `exp' field.
291:
292: Those elements with the same hash code are chained in both directions
293: through the `next_same_hash' and `prev_same_hash' fields.
294:
295: Each set of expressions with equivalent values
296: are on a two-way chain through the `next_same_value'
297: and `prev_same_value' fields, and all point with
298: the `first_same_value' field at the first element in
299: that chain. The chain is in order of increasing cost.
300: Each element's cost value is in its `cost' field.
301:
302: The `in_memory' field is nonzero for elements that
303: involve any reference to memory. These elements are removed
304: whenever a write is done to an unidentified location in memory.
305: To be safe, we assume that a memory address is unidentified unless
306: the address is either a symbol constant or a constant plus
307: the frame pointer or argument pointer.
308:
309: The `in_struct' field is nonzero for elements that
310: involve any reference to memory inside a structure or array.
311:
312: The `equivalence_only' field means that this expression came from a
313: REG_EQUIV or REG_EQUAL note; it is not valid for substitution into an insn.
314:
315: The `related_value' field is used to connect related expressions
316: (that differ by adding an integer).
317: The related expressions are chained in a circular fashion.
318: `related_value' is zero for expressions for which this
319: chain is not useful.
320:
321: The `mode' field is usually the same as GET_MODE (`exp'), but
322: if `exp' is a CONST_INT and has no machine mode then the `mode'
323: field is the mode it was being used as. Each constant is
324: recorded separately for each mode it is used with. */
325:
326:
327: struct table_elt
328: {
329: rtx exp;
330: struct table_elt *next_same_hash;
331: struct table_elt *prev_same_hash;
332: struct table_elt *next_same_value;
333: struct table_elt *prev_same_value;
334: struct table_elt *first_same_value;
335: struct table_elt *related_value;
336: int cost;
337: enum machine_mode mode;
338: char in_memory;
339: char in_struct;
340: char equivalence_only;
341: };
342:
343: #define HASH(x, m) (canon_hash (x, m) % NBUCKETS)
344: /* We don't want a lot of buckets, because we rarely have very many
345: things stored in the hash table, and a lot of buckets slows
346: down a lot of loops that happen frequently. */
347: #define NBUCKETS 31
348:
349: static struct table_elt *table[NBUCKETS];
350:
351: /* Chain of `struct table_elt's made so far for this function
352: but currently removed from the table. */
353:
354: static struct table_elt *free_element_chain;
355:
356: /* Number of `struct table_elt' structures made so far for this function. */
357:
358: static int n_elements_made;
359:
360: /* Maximum value `n_elements_made' has had so far in this compilation
361: for functions previously processed. */
362:
363: static int max_elements_made;
364:
365: /* Bits describing what kind of values in memory must be invalidated
366: for a particular instruction. If all three bits are zero,
367: no memory refs need to be invalidated. Each bit is more powerful
368: than the preceding ones, and if a bit is set then the preceding
369: bits are also set.
370:
371: Here is how the bits are set.
372: Writing at a fixed address invalidates only variable addresses,
373: writing in a structure element at variable address
374: invalidates all but scalar variables,
375: and writing in anything else at variable address invalidates everything. */
376:
377: struct write_data
378: {
379: int var : 1; /* Invalidate variable addresses. */
380: int nonscalar : 1; /* Invalidate all but scalar variables. */
381: int all : 1; /* Invalidate all memory refs. */
382: };
383:
384: /* Nonzero if X has the form (PLUS frame-pointer integer). */
385:
386: #define FIXED_BASE_PLUS_P(X) \
387: (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT \
388: && (XEXP (X, 0) == frame_pointer_rtx || XEXP (X, 0) == arg_pointer_rtx))
389:
390: static struct table_elt *lookup ();
391: static void free_element ();
392:
393: static void remove_invalid_refs ();
394: static int exp_equiv_p ();
395: int refers_to_p ();
396: int refers_to_mem_p ();
397: static void invalidate_from_clobbers ();
398: static int safe_hash ();
399: static int get_integer_term ();
400: static rtx get_related_value ();
401: static void note_mem_written ();
402: static int cse_rtx_addr_varies_p ();
403:
404: /* Return an estimate of the cost of computing rtx X.
405: The only use of this is to compare the costs of two expressions
406: to decide whether to replace one with the other. */
407:
408: static int
409: rtx_cost (x)
410: rtx x;
411: {
412: register int i, j;
413: register RTX_CODE code = GET_CODE (x);
414: register char *fmt;
415: register int total;
416:
417: switch (code)
418: {
419: case REG:
420: return 1;
421: case SUBREG:
422: return 2;
423: CONST_COSTS (x, code);
424: }
425:
426: total = 2;
427:
428: /* Sum the costs of the sub-rtx's, plus 2 just put in. */
429:
430: fmt = GET_RTX_FORMAT (code);
431: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
432: if (fmt[i] == 'e')
433: total += rtx_cost (XEXP (x, i));
434: else if (fmt[i] == 'E')
435: for (j = 0; j < XVECLEN (x, i); j++)
436: total += rtx_cost (XVECEXP (x, i, j));
437:
438: return total;
439: }
440:
441: /* Clear the hash table and initialize each register with its own quantity,
442: for a new basic block. */
443:
444: static void
445: new_basic_block ()
446: {
447: register int i;
448: register int vecsize = max_reg * sizeof (rtx);
449: next_qty = max_reg;
450:
451: bzero (reg_rtx, vecsize);
452: bzero (reg_tick, vecsize);
453:
454: bcopy (all_minus_one, reg_in_table, vecsize);
455: bcopy (all_minus_one, reg_next_eqv, vecsize);
456: bcopy (all_minus_one, reg_prev_eqv, vecsize);
457: bcopy (consec_ints, reg_qty, vecsize);
458:
459: for (i = 0; i < max_qty; i++)
460: {
461: qty_first_reg[i] = i;
462: qty_last_reg[i] = i;
463: qty_const[i] = 0;
464: qty_const_insn[i] = 0;
465: }
466:
467: for (i = 0; i < NBUCKETS; i++)
468: {
469: register struct table_elt *this, *next;
470: for (this = table[i]; this; this = next)
471: {
472: next = this->next_same_hash;
473: free_element (this);
474: }
475: }
476:
477: bzero (table, sizeof table);
478:
479: prev_insn_cc0 = 0;
480: prev_insn = 0;
481: }
482:
483: /* Say that register REG contains a quantity not in any register before. */
484:
485: static void
486: make_new_qty (reg)
487: register int reg;
488: {
489: register int q;
490:
491: q = reg_qty[reg] = next_qty++;
492: qty_first_reg[q] = reg;
493: qty_last_reg[q] = reg;
494: }
495:
496: /* Make reg NEW equivalent to reg OLD.
497: OLD is not changing; NEW is. */
498:
499: static void
500: make_regs_eqv (new, old)
501: register int new, old;
502: {
503: register int lastr, firstr;
504: register int q = reg_qty[old];
505:
506: /* Nothing should become eqv until it has a "non-invalid" qty number. */
507: if (q == old)
508: abort ();
509:
510: reg_qty[new] = q;
511: firstr = qty_first_reg[q];
512: lastr = qty_last_reg[q];
513:
514: /* Prefer pseudo regs to hard regs with the same value.
515: Among pseudos, if NEW will live longer than any other reg of the same qty,
516: and that is beyond the current basic block,
517: make it the new canonical replacement for this qty. */
518: if (new >= FIRST_PSEUDO_REGISTER
519: && (firstr < FIRST_PSEUDO_REGISTER
520: || ((regno_last_uid[new] > cse_basic_block_end
521: || regno_first_uid[new] < cse_basic_block_start)
522: && regno_last_uid[new] > regno_last_uid[firstr])))
523: {
524: reg_prev_eqv[firstr] = new;
525: reg_next_eqv[new] = firstr;
526: reg_prev_eqv[new] = -1;
527: qty_first_reg[q] = new;
528: }
529: else
530: {
531: /* If NEW is a hard reg, insert at end.
532: Otherwise, insert before any hard regs that are at the end. */
533: while (lastr < FIRST_PSEUDO_REGISTER && new >= FIRST_PSEUDO_REGISTER)
534: lastr = reg_prev_eqv[lastr];
535: reg_next_eqv[new] = reg_next_eqv[lastr];
536: if (reg_next_eqv[lastr] >= 0)
537: reg_prev_eqv[reg_next_eqv[lastr]] = new;
538: else
539: qty_last_reg[q] = new;
540: reg_next_eqv[lastr] = new;
541: reg_prev_eqv[new] = lastr;
542: }
543: }
544:
545: /* Discard the records of what is in register REG. */
546:
547: static void
548: reg_invalidate (reg)
549: register int reg;
550: {
551: register int n = reg_next_eqv[reg];
552: register int p = reg_prev_eqv[reg];
553: register int q = reg_qty[reg];
554:
555: reg_tick[reg]++;
556:
557: if (q == reg)
558: {
559: /* Save time if already invalid */
560: /* It shouldn't be linked to anything if it's invalid. */
561: if (reg_prev_eqv[q] != -1)
562: abort ();
563: if (reg_next_eqv[q] != -1)
564: abort ();
565: return;
566: }
567:
568: if (n != -1)
569: reg_prev_eqv[n] = p;
570: else
571: qty_last_reg[q] = p;
572: if (p != -1)
573: reg_next_eqv[p] = n;
574: else
575: qty_first_reg[q] = n;
576:
577: reg_qty[reg] = reg;
578: qty_first_reg[reg] = reg;
579: qty_last_reg[reg] = reg;
580: reg_next_eqv[reg] = -1;
581: reg_prev_eqv[reg] = -1;
582: }
583:
584: /* Remove any invalid expressions from the hash table
585: that refer to any of the registers contained in expression X.
586:
587: Make sure that newly inserted references to those registers
588: as subexpressions will be considered valid.
589:
590: mention_regs is not called when a register itself
591: is being stored in the table. */
592:
593: static void
594: mention_regs (x)
595: rtx x;
596: {
597: register RTX_CODE code = GET_CODE (x);
598: register int i, j;
599: register char *fmt;
600:
601: if (code == REG)
602: {
603: register int regno = REGNO (x);
604: reg_rtx[regno] = x;
605:
606: if (reg_in_table[regno] >= 0 && reg_in_table[regno] != reg_tick[regno])
607: remove_invalid_refs (regno);
608:
609: reg_in_table[regno] = reg_tick[regno];
610:
611: return;
612: }
613:
614: fmt = GET_RTX_FORMAT (code);
615: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
616: if (fmt[i] == 'e')
617: mention_regs (XEXP (x, i));
618: else if (fmt[i] == 'E')
619: for (j = 0; j < XVECLEN (x, i); j++)
620: mention_regs (XVECEXP (x, i, j));
621: }
622:
623: /* Update the register quantities for inserting X into the hash table
624: with a value equivalent to CLASSP.
625: (If CLASSP is not a REG or a SUBREG, it is irrelevant.)
626: If MODIFIED is nonzero, X is a destination; it is being modified.
627: Note that reg_invalidate should be called on a register
628: before insert_regs is done on that register with MODIFIED != 0.
629:
630: Nonzero value means that elements of reg_qty have changed
631: so X's hash code may be different. */
632:
633: static int
634: insert_regs (x, classp, modified)
635: rtx x;
636: struct table_elt *classp;
637: int modified;
638: {
639: if (GET_CODE (x) == REG)
640: {
641: register int regno = REGNO (x);
642: reg_rtx[regno] = x;
643: if (modified || reg_qty[regno] == regno)
644: {
645: if (classp && GET_CODE (classp->exp) == REG)
646: {
647: make_regs_eqv (regno, REGNO (classp->exp));
648: /* Make sure reg_rtx is set up even for regs
649: not explicitly set (such as function value). */
650: reg_rtx[REGNO (classp->exp)] = classp->exp;
651: }
652: else
653: make_new_qty (regno);
654: return 1;
655: }
656: }
657: /* Copying a subreg into a subreg makes the regs equivalent,
658: but only if the entire regs' mode is within one word.
659: Copying one reg of a DImode into one reg of another DImode
660: does not make them equivalent. */
661: else if (GET_CODE (x) == SUBREG
662: && GET_CODE (SUBREG_REG (x)) == REG
663: && GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))) <= BITS_PER_WORD
664: && (modified
665: || reg_qty[REGNO (SUBREG_REG (x))] == REGNO (SUBREG_REG (x))))
666: {
667: if (classp && GET_CODE (classp->exp) == SUBREG
668: && GET_CODE (SUBREG_REG (classp->exp)) == REG
669: && GET_MODE (SUBREG_REG (classp->exp)) == GET_MODE (SUBREG_REG (x)))
670: {
671: int oregno = REGNO (SUBREG_REG (classp->exp));
672: make_regs_eqv (REGNO (SUBREG_REG (x)), oregno);
673: /* Make sure reg_rtx is set up even for regs
674: not explicitly set (such as function value). */
675: reg_rtx[oregno] = SUBREG_REG (classp->exp);
676: }
677: else
678: make_new_qty (REGNO (SUBREG_REG (x)));
679: return 1;
680: }
681: else
682: mention_regs (x);
683: return 0;
684: }
685:
686: /* Look in or update the hash table. */
687:
688: /* Put the element ELT on the list of free elements. */
689:
690: static void
691: free_element (elt)
692: struct table_elt *elt;
693: {
694: elt->next_same_hash = free_element_chain;
695: free_element_chain = elt;
696: }
697:
698: /* Return an element that is free for use. */
699:
700: static struct table_elt *
701: get_element ()
702: {
703: struct table_elt *elt = free_element_chain;
704: if (elt)
705: {
706: free_element_chain = elt->next_same_hash;
707: return elt;
708: }
709: n_elements_made++;
710: return (struct table_elt *) oballoc (sizeof (struct table_elt));
711: }
712:
713: /* Remove table element ELT from use in the table.
714: HASH is its hash code, made using the HASH macro.
715: It's an argument because often that is known in advance
716: and we save much time not recomputing it. */
717:
718: static void
719: remove (elt, hash)
720: register struct table_elt *elt;
721: int hash;
722: {
723: if (elt == 0)
724: return;
725:
726: /* Mark this element as removed. See cse_insn. */
727: elt->first_same_value = 0;
728:
729: /* Remove the table element from its equivalence class. */
730:
731: {
732: register struct table_elt *prev = elt->prev_same_value;
733: register struct table_elt *next = elt->next_same_value;
734:
735: if (next) next->prev_same_value = prev;
736:
737: if (prev)
738: prev->next_same_value = next;
739: else
740: {
741: register struct table_elt *newfirst = next;
742: while (next)
743: {
744: next->first_same_value = newfirst;
745: next = next->next_same_value;
746: }
747: }
748: }
749:
750: /* Remove the table element from its hash bucket. */
751:
752: {
753: register struct table_elt *prev = elt->prev_same_hash;
754: register struct table_elt *next = elt->next_same_hash;
755:
756: if (next) next->prev_same_hash = prev;
757:
758: if (prev)
759: prev->next_same_hash = next;
760: else
761: table[hash] = next;
762: }
763:
764: /* Remove the table element from its related-value circular chain. */
765:
766: if (elt->related_value != 0 && elt->related_value != elt)
767: {
768: register struct table_elt *p = elt->related_value;
769: while (p->related_value != elt)
770: p = p->related_value;
771: p->related_value = elt->related_value;
772: if (p->related_value == p)
773: p->related_value = 0;
774: }
775:
776: free_element (elt);
777: }
778:
779: /* Look up X in the hash table and return its table element,
780: or 0 if X is not in the table.
781:
782: MODE is the machine-mode of X, or if X is an integer constant
783: with VOIDmode then MODE is the mode with which X will be used.
784:
785: Here we are satisfied to find an expression whose tree structure
786: looks like X. */
787:
788: static struct table_elt *
789: lookup (x, hash, mode)
790: rtx x;
791: int hash;
792: enum machine_mode mode;
793: {
794: register struct table_elt *p;
795:
796: for (p = table[hash]; p; p = p->next_same_hash)
797: if (mode == p->mode && (x == p->exp || exp_equiv_p (x, p->exp, 1)))
798: return p;
799:
800: return 0;
801: }
802:
803: /* Like `lookup' but don't care whether the table element uses invalid regs.
804: Also ignore discrepancies in the machine mode of a register. */
805:
806: static struct table_elt *
807: lookup_for_remove (x, hash, mode)
808: rtx x;
809: int hash;
810: enum machine_mode mode;
811: {
812: register struct table_elt *p;
813:
814: if (GET_CODE (x) == REG)
815: {
816: int regno = REGNO (x);
817: /* Don't check the machine mode when comparing registers;
818: invalidating (REG:SI 0) also invalidates (REG:DF 0). */
819: for (p = table[hash]; p; p = p->next_same_hash)
820: if (GET_CODE (p->exp) == REG
821: && REGNO (p->exp) == regno)
822: return p;
823: }
824: else
825: {
826: for (p = table[hash]; p; p = p->next_same_hash)
827: if (mode == p->mode && (x == p->exp || exp_equiv_p (x, p->exp, 0)))
828: return p;
829: }
830:
831: return 0;
832: }
833:
834: /* Look for an expression equivalent to X and of the form (CODE Y).
835: If one is found, return Y. */
836:
837: static rtx
838: lookup_as_function (x, code)
839: rtx x;
840: enum rtx_code code;
841: {
842: register struct table_elt *p = lookup (x, safe_hash (x, 0) % NBUCKETS,
843: GET_MODE (x));
844: if (p == 0)
845: return 0;
846:
847: for (p = p->first_same_value; p; p = p->next_same_value)
848: {
849: if (GET_CODE (p->exp) == code
850: /* Make sure this is a valid entry in the table. */
851: && (exp_equiv_p (XEXP (p->exp, 0), XEXP (p->exp, 0))))
852: return XEXP (p->exp, 0);
853: }
854:
855: return 0;
856: }
857:
858: /* Insert X in the hash table, assuming HASH is its hash code
859: and CLASSP is the current first element of the class it should go in
860: (or 0 if a new class should be made).
861: It is inserted at the proper position to keep the class in
862: the order cheapest first.
863:
864: MODE is the machine-mode of X, or if X is an integer constant
865: with VOIDmode then MODE is the mode with which X will be used.
866:
867: For elements of equal cheapness, the most recent one
868: goes in front, except that the first element in the list
869: remains first unless a cheaper element is added.
870:
871: The in_memory field in the hash table element is set to 0.
872: The caller must set it nonzero if appropriate.
873:
874: You should call insert_regs (X, CLASSP, MODIFY) before calling here,
875: and if insert_regs returns a nonzero value
876: you must then recompute its hash code before calling here.
877:
878: If necessary, update table showing constant values of quantities. */
879:
880: #define CHEAPER(X,Y) \
881: (((X)->cost < (Y)->cost) || \
882: (GET_CODE ((X)->exp) == REG && GET_CODE ((Y)->exp) == REG \
883: && (regno_last_uid[REGNO ((X)->exp)] > cse_basic_block_end \
884: || regno_first_uid[REGNO ((X)->exp)] < cse_basic_block_start) \
885: && (regno_last_uid[REGNO ((X)->exp)] \
886: > regno_last_uid[REGNO ((Y)->exp)])))
887:
888: static struct table_elt *
889: insert (x, classp, hash, mode)
890: register rtx x;
891: register struct table_elt *classp;
892: int hash;
893: enum machine_mode mode;
894: {
895: register struct table_elt *elt;
896:
897: /* Put an element for X into the right hash bucket. */
898:
899: elt = get_element ();
900: elt->exp = x;
901: elt->cost = rtx_cost (x) * 2;
902: /* Make pseudo regs a little cheaper than hard regs. */
903: if (GET_CODE (x) == REG && REGNO (x) >= FIRST_PSEUDO_REGISTER)
904: elt->cost -= 1;
905: elt->next_same_value = 0;
906: elt->prev_same_value = 0;
907: elt->next_same_hash = table[hash];
908: elt->prev_same_hash = 0;
909: elt->related_value = 0;
910: elt->in_memory = 0;
911: elt->equivalence_only = 0;
912: elt->mode = mode;
913: if (table[hash])
914: table[hash]->prev_same_hash = elt;
915: table[hash] = elt;
916:
917: /* Put it into the proper value-class. */
918: if (classp)
919: {
920: if (CHEAPER (elt, classp))
921: /** Insert at the head of the class */
922: {
923: register struct table_elt *p;
924: elt->next_same_value = classp;
925: classp->prev_same_value = elt;
926: elt->first_same_value = elt;
927:
928: for (p = classp; p; p = p->next_same_value)
929: p->first_same_value = elt;
930: }
931: else
932: {
933: /* Insert not at head of the class. */
934: /* Put it after the last element cheaper than X. */
935: register struct table_elt *p, *next;
936: for (p = classp; (next = p->next_same_value) && CHEAPER (p, elt);
937: p = next);
938: elt->next_same_value = next;
939: if (next)
940: next->prev_same_value = elt;
941: elt->prev_same_value = p;
942: p->next_same_value = elt;
943: elt->first_same_value = classp;
944: }
945: }
946: else
947: elt->first_same_value = elt;
948:
949: if ((CONSTANT_P (x) || FIXED_BASE_PLUS_P (x))
950: && GET_CODE (elt->first_same_value->exp) == REG)
951: {
952: qty_const[reg_qty[REGNO (elt->first_same_value->exp)]] = x;
953: qty_const_insn[reg_qty[REGNO (elt->first_same_value->exp)]] = this_insn;
954: }
955:
956: if (GET_CODE (x) == REG)
957: {
958: if (elt->next_same_value != 0
959: && (CONSTANT_P (elt->next_same_value->exp)
960: || FIXED_BASE_PLUS_P (elt->next_same_value->exp)))
961: {
962: qty_const[reg_qty[REGNO (x)]] = elt->next_same_value->exp;
963: qty_const_insn[reg_qty[REGNO (x)]] = this_insn;
964: }
965: if (CONSTANT_P (elt->first_same_value->exp)
966: || FIXED_BASE_PLUS_P (elt->first_same_value->exp))
967: {
968: qty_const[reg_qty[REGNO (x)]] = elt->first_same_value->exp;
969: qty_const_insn[reg_qty[REGNO (x)]] = this_insn;
970: }
971: }
972:
973: /* If this is a constant with symbolic value,
974: and it has a term with an explicit integer value,
975: link it up with related expressions. */
976: if (GET_CODE (x) == CONST)
977: {
978: rtx subexp = get_related_value (x);
979: int subhash;
980: struct table_elt *subelt, *subelt_prev;
981:
982: if (subexp != 0)
983: {
984: /* Get the integer-free subexpression in the hash table. */
985: subhash = safe_hash (subexp, mode) % NBUCKETS;
986: subelt = lookup (subexp, subhash, mode);
987: if (subelt == 0)
988: subelt = insert (subexp, 0, subhash, mode);
989: /* Initialize SUBELT's circular chain if it has none. */
990: if (subelt->related_value == 0)
991: subelt->related_value = subelt;
992: /* Find the element in the circular chain that precedes SUBELT. */
993: subelt_prev = subelt;
994: while (subelt_prev->related_value != subelt)
995: subelt_prev = subelt_prev->related_value;
996: /* Put new ELT into SUBELT's circular chain just before SUBELT.
997: This way the element that follows SUBELT is the oldest one. */
998: elt->related_value = subelt_prev->related_value;
999: subelt_prev->related_value = elt;
1000: }
1001: }
1002:
1003: return elt;
1004: }
1005:
1006: /* Remove from the hash table, or mark as invalid,
1007: all expressions whose values could be altered by storing in X.
1008: X is a register, a subreg, or a memory reference with nonvarying address
1009: (because, when a memory reference with a varying address is stored in,
1010: all memory references are removed by invalidate_memory
1011: so specific invalidation is superfluous).
1012:
1013: A nonvarying address may be just a register or just
1014: a symbol reference, or it may be either of those plus
1015: a numeric offset. */
1016:
1017: static void
1018: invalidate (x)
1019: rtx x;
1020: {
1021: register int i;
1022: register struct table_elt *p;
1023: register rtx base;
1024: register int start, end;
1025:
1026: /* If X is a register, dependencies on its contents
1027: are recorded through the qty number mechanism.
1028: Just change the qty number of the register,
1029: mark it as invalid for expressions that refer to it,
1030: and remove it itself. */
1031:
1032: if (GET_CODE (x) == REG)
1033: {
1034: register int hash = HASH (x, 0);
1035: reg_invalidate (REGNO (x));
1036: remove (lookup_for_remove (x, hash, GET_MODE (x)), hash);
1037: return;
1038: }
1039:
1040: if (GET_CODE (x) == SUBREG)
1041: {
1042: if (GET_CODE (SUBREG_REG (x)) != REG)
1043: abort ();
1044: invalidate (SUBREG_REG (x));
1045: return;
1046: }
1047:
1048: /* X is not a register; it must be a memory reference with
1049: a nonvarying address. Remove all hash table elements
1050: that refer to overlapping pieces of memory. */
1051:
1052: if (GET_CODE (x) != MEM)
1053: abort ();
1054: base = XEXP (x, 0);
1055: start = 0;
1056:
1057: /* Registers with nonvarying addresses usually have constant equivalents;
1058: but the frame pointer register is also possible. */
1059: if (GET_CODE (base) == REG
1060: && qty_const[reg_qty[REGNO (base)]] != 0)
1061: base = qty_const[reg_qty[REGNO (base)]];
1062:
1063: if (GET_CODE (base) == CONST)
1064: base = XEXP (base, 0);
1065: if (GET_CODE (base) == PLUS
1066: && GET_CODE (XEXP (base, 1)) == CONST_INT)
1067: {
1068: start = INTVAL (XEXP (base, 1));
1069: base = XEXP (base, 0);
1070: }
1071:
1072: end = start + GET_MODE_SIZE (GET_MODE (x));
1073: for (i = 0; i < NBUCKETS; i++)
1074: {
1075: register struct table_elt *next;
1076: for (p = table[i]; p; p = next)
1077: {
1078: next = p->next_same_hash;
1079: if (refers_to_mem_p (p->exp, base, start, end))
1080: remove (p, i);
1081: }
1082: }
1083: }
1084:
1085: /* Remove all expressions that refer to register REGNO,
1086: since they are already invalid, and we are about to
1087: mark that register valid again and don't want the old
1088: expressions to reappear as valid. */
1089:
1090: static void
1091: remove_invalid_refs (regno)
1092: int regno;
1093: {
1094: register int i;
1095: register struct table_elt *p, *next;
1096: register rtx x = reg_rtx[regno];
1097:
1098: for (i = 0; i < NBUCKETS; i++)
1099: for (p = table[i]; p; p = next)
1100: {
1101: next = p->next_same_hash;
1102: if (GET_CODE (p->exp) != REG && refers_to_p (p->exp, x))
1103: remove (p, i);
1104: }
1105: }
1106:
1107: /* Remove from the hash table all expressions that reference memory,
1108: or some of them as specified by *WRITES. */
1109:
1110: static void
1111: invalidate_memory (writes)
1112: struct write_data *writes;
1113: {
1114: register int i;
1115: register struct table_elt *p, *next;
1116: int all = writes->all;
1117: int nonscalar = writes->nonscalar;
1118:
1119: for (i = 0; i < NBUCKETS; i++)
1120: for (p = table[i]; p; p = next)
1121: {
1122: next = p->next_same_hash;
1123: if (p->in_memory
1124: && (all
1125: || (nonscalar && p->in_struct)
1126: || cse_rtx_addr_varies_p (p->exp)))
1127: remove (p, i);
1128: }
1129: }
1130:
1131: /* Return the value of the integer term in X, if one is apparent;
1132: otherwise return 0.
1133: We do not check extremely carefully for the presence of integer terms
1134: but rather consider only the cases that `insert' notices
1135: for the `related_value' field. */
1136:
1137: static int
1138: get_integer_term (x)
1139: rtx x;
1140: {
1141: if (GET_CODE (x) == CONST)
1142: x = XEXP (x, 0);
1143:
1144: if (GET_CODE (x) == MINUS
1145: && GET_CODE (XEXP (x, 1)) == CONST_INT)
1146: return - INTVAL (XEXP (x, 1));
1147: if (GET_CODE (x) != PLUS)
1148: return 0;
1149: if (GET_CODE (XEXP (x, 0)) == CONST_INT)
1150: return INTVAL (XEXP (x, 0));
1151: if (GET_CODE (XEXP (x, 1)) == CONST_INT)
1152: return INTVAL (XEXP (x, 1));
1153: return 0;
1154: }
1155:
1156: static rtx
1157: get_related_value (x)
1158: rtx x;
1159: {
1160: if (GET_CODE (x) != CONST)
1161: return 0;
1162: x = XEXP (x, 0);
1163: if (GET_CODE (x) == PLUS)
1164: {
1165: if (GET_CODE (XEXP (x, 0)) == CONST_INT)
1166: return XEXP (x, 1);
1167: if (GET_CODE (XEXP (x, 1)) == CONST_INT)
1168: return XEXP (x, 0);
1169: }
1170: else if (GET_CODE (x) == MINUS
1171: && GET_CODE (XEXP (x, 1)) == CONST_INT)
1172: return XEXP (x, 0);
1173: return 0;
1174: }
1175:
1176: /* Given an expression X of type CONST,
1177: and ELT which is its table entry (or 0 if it
1178: is not in the hash table),
1179: return an alternate expression for X as a register plus integer.
1180: If none can be found or it would not be a valid address, return 0. */
1181:
1182: static rtx
1183: use_related_value (x, elt)
1184: rtx x;
1185: struct table_elt *elt;
1186: {
1187: register struct table_elt *relt = 0;
1188: register struct table_elt *p;
1189: int offset;
1190: rtx addr;
1191:
1192: /* First, is there anything related known?
1193: If we have a table element, we can tell from that.
1194: Otherwise, must look it up. */
1195:
1196: if (elt != 0 && elt->related_value != 0)
1197: relt = elt;
1198: else if (elt == 0 && GET_CODE (x) == CONST)
1199: {
1200: rtx subexp = get_related_value (x);
1201: if (subexp != 0)
1202: relt = lookup (subexp,
1203: safe_hash (subexp, GET_MODE (subexp)) % NBUCKETS,
1204: GET_MODE (subexp));
1205: }
1206:
1207: if (relt == 0)
1208: return 0;
1209:
1210: /* Search all related table entries for one that has an
1211: equivalent register. */
1212:
1213: p = relt;
1214: while (1)
1215: {
1216: if (p->first_same_value != 0
1217: && GET_CODE (p->first_same_value->exp) == REG)
1218: break;
1219: p = p->related_value;
1220:
1221: /* We went all the way around, so there is nothing to be found.
1222: Return failure. */
1223: if (p == relt)
1224: return 0;
1225: /* Perhaps RELT was in the table for some other reason and
1226: it has no related values recorded. */
1227: if (p == 0)
1228: return 0;
1229: }
1230:
1231: offset = (get_integer_term (x) - get_integer_term (p->exp));
1232: if (offset == 0)
1233: abort ();
1234:
1235: addr = plus_constant (p->first_same_value->exp, offset);
1236: if (memory_address_p (QImode, addr))
1237: return addr;
1238: return 0;
1239: }
1240:
1241: /* Hash an rtx. We are careful to make sure the value is never negative.
1242: Equivalent registers hash identically.
1243:
1244: Store 1 in do_not_record if any subexpression is volatile.
1245:
1246: Store 1 in hash_arg_in_memory if X contains a MEM rtx
1247: which does not have the ->unchanging bit set.
1248: In this case, also store 1 in hash_arg_in_struct
1249: if there is a MEM rtx which has the ->in_struct bit set.
1250:
1251: Note that cse_insn knows that the hash code of a MEM expression
1252: is just (int) MEM plus the hash code of the address.
1253: It also knows it can use HASHREG to get the hash code of (REG n). */
1254:
1255: #define HASHBITS 16
1256:
1257: #define HASHREG(RTX) \
1258: ((((int) REG << 7) + reg_qty[REGNO (RTX)]) % NBUCKETS)
1259:
1260: static int
1261: canon_hash (x, mode)
1262: rtx x;
1263: enum machine_mode mode;
1264: {
1265: register int i, j;
1266: register int hash = 0;
1267: register RTX_CODE code;
1268: register char *fmt;
1269:
1270: /* repeat is used to turn tail-recursion into iteration. */
1271: repeat:
1272: code = GET_CODE (x);
1273: switch (code)
1274: {
1275: case REG:
1276: {
1277: /* We do not invalidate anything on pushing or popping
1278: because they cannot change anything but the stack pointer;
1279: but that means we must consider the stack pointer volatile
1280: since it can be changed "mysteriously". */
1281:
1282: register int regno = REGNO (x);
1283: if (regno == STACK_POINTER_REGNUM)
1284: {
1285: do_not_record = 1;
1286: return 0;
1287: }
1288: return hash + ((int) REG << 7) + reg_qty[regno];
1289: }
1290:
1291: case CONST_INT:
1292: hash = INTVAL (x);
1293: hash = (int) mode + ((int) CONST_INT << 7) + hash + hash >> HASHBITS;
1294: return ((1 << HASHBITS) - 1) & hash;
1295:
1296: /* Assume there is only one rtx object for any given label. */
1297: case LABEL_REF:
1298: return hash + ((int) LABEL_REF << 7) + (int) XEXP (x, 0);
1299:
1300: case SYMBOL_REF:
1301: return hash + ((int) SYMBOL_REF << 7) + (int) XEXP (x, 0);
1302:
1303: case MEM:
1304: if (x->volatil)
1305: {
1306: do_not_record = 1;
1307: return 0;
1308: }
1309: if (! x->unchanging)
1310: {
1311: hash_arg_in_memory = 1;
1312: if (x->in_struct) hash_arg_in_struct = 1;
1313: }
1314: /* Now that we have already found this special case,
1315: might as well speed it up as much as possible. */
1316: hash += (int) MEM;
1317: x = XEXP (x, 0);
1318: goto repeat;
1319:
1320: case PRE_DEC:
1321: case PRE_INC:
1322: case POST_DEC:
1323: case POST_INC:
1324: case PC:
1325: case CC0:
1326: case CALL:
1327: do_not_record = 1;
1328: return 0;
1329:
1330: case ASM_OPERANDS:
1331: if (x->volatil)
1332: {
1333: do_not_record = 1;
1334: return 0;
1335: }
1336: }
1337:
1338: i = GET_RTX_LENGTH (code) - 1;
1339: hash += (int) code + (int) GET_MODE (x);
1340: fmt = GET_RTX_FORMAT (code);
1341: for (; i >= 0; i--)
1342: {
1343: if (fmt[i] == 'e')
1344: {
1345: /* If we are about to do the last recursive call
1346: needed at this level, change it into iteration.
1347: This function is called enough to be worth it. */
1348: if (i == 0)
1349: {
1350: x = XEXP (x, 0);
1351: goto repeat;
1352: }
1353: hash += canon_hash (XEXP (x, i), 0);
1354: }
1355: else if (fmt[i] == 'E')
1356: for (j = 0; j < XVECLEN (x, i); j++)
1357: hash += canon_hash (XVECEXP (x, i, j), 0);
1358: else if (fmt[i] == 's')
1359: {
1360: register char *p = XSTR (x, i);
1361: while (*p)
1362: {
1363: register int tem = *p++;
1364: hash += ((1 << HASHBITS) - 1) & (tem + tem >> HASHBITS);
1365: }
1366: }
1367: else
1368: {
1369: register int tem = XINT (x, i);
1370: hash += ((1 << HASHBITS) - 1) & (tem + tem >> HASHBITS);
1371: }
1372: }
1373: return hash;
1374: }
1375:
1376: /* Like canon_hash but with no side effects. */
1377:
1378: static int
1379: safe_hash (x, mode)
1380: rtx x;
1381: enum machine_mode mode;
1382: {
1383: int save_do_not_record = do_not_record;
1384: int save_hash_arg_in_memory = hash_arg_in_memory;
1385: int save_hash_arg_in_struct = hash_arg_in_struct;
1386: int hash = canon_hash (x, mode);
1387: hash_arg_in_memory = save_hash_arg_in_memory;
1388: hash_arg_in_struct = save_hash_arg_in_struct;
1389: do_not_record = save_do_not_record;
1390: return hash;
1391: }
1392:
1393: /* Return 1 iff X and Y would canonicalize into the same thing,
1394: without actually constructing the canonicalization of either one.
1395: If VALIDATE is nonzero,
1396: we assume X is an expression being processed from the rtl
1397: and Y was found in the hash table. We check register refs
1398: in Y for being marked as valid. */
1399:
1400: static int
1401: exp_equiv_p (x, y, validate)
1402: rtx x, y;
1403: int validate;
1404: {
1405: register int i;
1406: register RTX_CODE code = GET_CODE (x);
1407: register char *fmt;
1408:
1409: /* An expression is usually equivalent to itself,
1410: but not if it's a register that's invalid. */
1411: if (x == y)
1412: return (code != REG
1413: || !validate
1414: || reg_in_table[REGNO (y)] == reg_tick[REGNO (y)]);
1415:
1416: if (code != GET_CODE (y))
1417: return 0;
1418: if (code == REG)
1419: return (reg_qty[REGNO (x)] == reg_qty[REGNO (y)]
1420: && (!validate
1421: || reg_in_table[REGNO (y)] == reg_tick[REGNO (y)]));
1422:
1423: /* Assume there is only one rtx object to refer
1424: to any given label.
1425: We already know that X and Y are not the same object
1426: so they must differ. */
1427:
1428: if (code == LABEL_REF || code == SYMBOL_REF)
1429: return XEXP (x, 0) == XEXP (y, 0);
1430:
1431: /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. */
1432:
1433: if (GET_MODE (x) != GET_MODE (y))
1434: return 0;
1435:
1436: /* Compare the elements. If any pair of corresponding elements
1437: fail to match, return 0 for the whole things. */
1438:
1439: fmt = GET_RTX_FORMAT (code);
1440: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1441: {
1442: if (fmt[i] == 'e')
1443: {
1444: if (! exp_equiv_p (XEXP (x, i), XEXP (y, i), validate))
1445: return 0;
1446: }
1447: else if (fmt[i] == 'E')
1448: {
1449: int j;
1450: for (j = 0; j < XVECLEN (x, i); j++)
1451: if (! exp_equiv_p (XVECEXP (x, i, j), XVECEXP (y, i, j), validate))
1452: return 0;
1453: }
1454: else if (fmt[i] == 's')
1455: {
1456: if (strcmp (XSTR (x, i), XSTR (y, i)))
1457: return 0;
1458: }
1459: else
1460: {
1461: if (XINT (x, i) != XINT (y, i))
1462: return 0;
1463: }
1464: }
1465: return 1;
1466: }
1467:
1468: /* Return 1 iff any subexpression of X matches Y.
1469: Here we do not require that X or Y be valid (for registers referred to)
1470: for being in the hash table. */
1471:
1472: int
1473: refers_to_p (x, y)
1474: rtx x, y;
1475: {
1476: register int i;
1477: register RTX_CODE code;
1478: register char *fmt;
1479:
1480: repeat:
1481: if (x == y)
1482: return 1;
1483:
1484: code = GET_CODE (x);
1485: /* If X as a whole has the same code as Y, they may match.
1486: If so, return 1. */
1487: if (code == GET_CODE (y))
1488: {
1489: if (exp_equiv_p (x, y, 0))
1490: return 1;
1491: }
1492:
1493: /* X does not match, so try its subexpressions. */
1494:
1495: fmt = GET_RTX_FORMAT (code);
1496: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1497: if (fmt[i] == 'e')
1498: {
1499: if (i == 0)
1500: {
1501: x = XEXP (x, 0);
1502: goto repeat;
1503: }
1504: else
1505: if (refers_to_p (XEXP (x, i), y))
1506: return 1;
1507: }
1508: else if (fmt[i] == 'E')
1509: {
1510: int j;
1511: for (j = 0; j < XVECLEN (x, i); j++)
1512: if (refers_to_p (XVECEXP (x, i, j), y))
1513: return 1;
1514: }
1515:
1516: return 0;
1517: }
1518:
1519: /* Return 1 iff any subexpression of X refers to memory
1520: at an address of REG plus some offset
1521: such that any of the bytes' offsets fall between START (inclusive)
1522: and END (exclusive).
1523:
1524: The value is undefined if X is a varying address.
1525: This function is not used in such cases.
1526:
1527: When used in the cse pass, `qty_const' is nonzero, and it is used
1528: to treat an address that is a register with a known constant value
1529: as if it were that constant value.
1530: In the loop pass, `qty_const' is zero, so this is not done. */
1531:
1532: int
1533: refers_to_mem_p (x, reg, start, end)
1534: rtx x, reg;
1535: int start, end;
1536: {
1537: register int i;
1538: register RTX_CODE code;
1539: register char *fmt;
1540:
1541: repeat:
1542: code = GET_CODE (x);
1543: if (code == MEM)
1544: {
1545: register rtx addr = XEXP (x, 0); /* Get the address. */
1546: int myend;
1547: if (GET_CODE (addr) == REG
1548: /* qty_const is 0 when outside the cse pass;
1549: at such times, this info is not available. */
1550: && qty_const != 0
1551: && qty_const[reg_qty[REGNO (addr)]] != 0)
1552: addr = qty_const[reg_qty[REGNO (addr)]];
1553: if (GET_CODE (addr) == CONST)
1554: addr = XEXP (addr, 0);
1555:
1556: /* If ADDR is BASE, or BASE plus an integer, put
1557: the integer in I. */
1558: if (addr == reg)
1559: i = 0;
1560: else if (GET_CODE (addr) == PLUS
1561: && XEXP (addr, 0) == reg
1562: && GET_CODE (XEXP (addr, 1)) == CONST_INT)
1563: i = INTVAL (XEXP (addr, 1));
1564: else
1565: return 0;
1566:
1567: myend = i + GET_MODE_SIZE (GET_MODE (x));
1568: return myend > start && i < end;
1569: }
1570:
1571: /* X does not match, so try its subexpressions. */
1572:
1573: fmt = GET_RTX_FORMAT (code);
1574: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1575: if (fmt[i] == 'e')
1576: {
1577: if (i == 0)
1578: {
1579: x = XEXP (x, 0);
1580: goto repeat;
1581: }
1582: else
1583: if (refers_to_mem_p (XEXP (x, i), reg, start, end))
1584: return 1;
1585: }
1586: else if (fmt[i] == 'E')
1587: {
1588: int j;
1589: for (j = 0; j < XVECLEN (x, i); j++)
1590: if (refers_to_mem_p (XVECEXP (x, i, j), reg, start, end))
1591: return 1;
1592: }
1593:
1594: return 0;
1595: }
1596:
1597: /* Nonzero if X refers to memory at a varying address;
1598: except that a register which has at the moment a known constant value
1599: isn't considered variable. */
1600:
1601: static int
1602: cse_rtx_addr_varies_p (x)
1603: rtx x;
1604: {
1605: if (GET_CODE (x) == MEM
1606: && GET_CODE (XEXP (x, 0)) == REG
1607: && qty_const[reg_qty[REGNO (XEXP (x, 0))]] != 0)
1608: return 0;
1609: return rtx_addr_varies_p (x);
1610: }
1611:
1612: /* Canonicalize an expression:
1613: replace each register reference inside it
1614: with the "oldest" equivalent register. */
1615:
1616: static rtx
1617: canon_reg (x)
1618: rtx x;
1619: {
1620: register int i;
1621: register RTX_CODE code = GET_CODE (x);
1622: register char *fmt;
1623:
1624: if (code == REG)
1625: {
1626: register int qty = reg_qty[REGNO (x)];
1627: register rtx new = reg_rtx[qty_first_reg[qty]];
1628: /* Never replace a hard reg, because hard regs can appear
1629: in more than one machine mode, and we must preserve the mode
1630: of each occurrence. Also, some hard regs appear in
1631: MEMs that are shared and mustn't be altered. */
1632: if (REGNO (x) < FIRST_PSEUDO_REGISTER)
1633: return x;
1634: return new ? new : x;
1635: }
1636:
1637: fmt = GET_RTX_FORMAT (code);
1638: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1639: {
1640: register int j;
1641:
1642: if (fmt[i] == 'e')
1643: XEXP (x, i) = canon_reg (XEXP (x, i));
1644: else if (fmt[i] == 'E')
1645: for (j = 0; j < XVECLEN (x, i); j++)
1646: XVECEXP (x, i, j) = canon_reg (XVECEXP (x, i, j));
1647: }
1648:
1649: return x;
1650: }
1651:
1652: /* If X is a nontrivial arithmetic operation on an argument
1653: for which a constant value can be determined, return
1654: the result of operating on that value, as a constant.
1655: Otherwise, return X, possibly with one or more operands
1656: modified by recursive calls to this function.
1657:
1658: If X is a register whose contents are known, we do NOT
1659: return those contents. This is because an instruction that
1660: uses a register is usually faster than one that uses a constant.
1661:
1662: COPYFLAG is nonzero for memory addresses and subexpressions thereof.
1663: If COPYFLAG is nonzero, we avoid altering X itself
1664: by creating new structure when necessary. In this case we
1665: can risk creating invalid structure because it will be tested.
1666: If COPYFLAG is zero, be careful not to substitute constants
1667: into expressions that cannot be simplified. */
1668:
1669: static rtx
1670: fold_rtx (x, copyflag)
1671: rtx x;
1672: int copyflag;
1673: {
1674: register RTX_CODE code = GET_CODE (x);
1675: register char *fmt;
1676: register int i, val;
1677: rtx new = 0;
1678: int copied = ! copyflag;
1679: int width = GET_MODE_BITSIZE (GET_MODE (x));
1680:
1681: /* Constant equivalents of first three operands of X;
1682: 0 when no such equivalent is known. */
1683: rtx const_arg0;
1684: rtx const_arg1;
1685: rtx const_arg2;
1686:
1687: switch (code)
1688: {
1689: case CONST:
1690: case CONST_INT:
1691: case CONST_DOUBLE:
1692: case SYMBOL_REF:
1693: case LABEL_REF:
1694: case PC:
1695: case CC0:
1696: case REG:
1697: return x;
1698:
1699: /* We must be careful when folding a memory address
1700: to avoid making it invalid. So fold nondestrictively
1701: and use the result only if it's valid. */
1702: case MEM:
1703: {
1704: rtx newaddr = fold_rtx (XEXP (x, 0), 1);
1705: if (! memory_address_p (GET_MODE (x), newaddr)
1706: && memory_address_p (GET_MODE (x), XEXP (x, 0)))
1707: return x;
1708:
1709: if (copyflag)
1710: return gen_rtx (MEM, GET_MODE (x), newaddr);
1711: XEXP (x, 0) = newaddr;
1712: return x;
1713: }
1714: }
1715:
1716: const_arg0 = 0;
1717: const_arg1 = 0;
1718: const_arg2 = 0;
1719:
1720: /* Try folding our operands.
1721: Then see which ones have constant values known. */
1722:
1723: fmt = GET_RTX_FORMAT (code);
1724: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1725: if (fmt[i] == 'e')
1726: {
1727: register rtx tem = fold_rtx (XEXP (x, i), copyflag);
1728:
1729: /* If an operand has changed under folding, and we are not supposed to
1730: alter the original structure, copy X if we haven't yet done so. */
1731: if (! copied && tem != XEXP (x, i))
1732: {
1733: int j;
1734: rtx new = rtx_alloc (code);
1735: PUT_MODE (new, GET_MODE (x));
1736: for (j = 0; j < GET_RTX_LENGTH (code); j++)
1737: XINT (new, j) = XINT (x, j);
1738: x = new;
1739: copied = 1;
1740: }
1741:
1742: /* Install the possibly altered folded operand. */
1743: XEXP (x, i) = tem;
1744:
1745: /* For the first three operands, see if the operand
1746: is constant or equivalent to a constant. */
1747: if (i < 3)
1748: {
1749: rtx tem1;
1750: rtx const_arg = 0;
1751:
1752: if (CONSTANT_P (tem))
1753: const_arg = tem;
1754: else if (GET_CODE (tem) == REG
1755: && qty_const[reg_qty[REGNO (tem)]] != 0
1756: /* Make sure it is really a constant */
1757: && ((tem1 = qty_const[reg_qty[REGNO (tem)]]),
1758: GET_CODE (tem1) != REG && GET_CODE (tem1) != PLUS))
1759: const_arg = qty_const[reg_qty[REGNO (tem)]];
1760:
1761: switch (i)
1762: {
1763: case 0:
1764: const_arg0 = const_arg;
1765: break;
1766: case 1:
1767: const_arg1 = const_arg;
1768: break;
1769: case 2:
1770: const_arg2 = const_arg;
1771: break;
1772: }
1773: }
1774: }
1775: else if (fmt[i] == 'E')
1776: /* Don't try to fold inside of a vector of expressions.
1777: Doing nothing is is harmless. */
1778: ;
1779:
1780: /* Now decode the kind of rtx X is
1781: and either return X (if nothing can be done)
1782: or store a value in VAL and drop through
1783: (to return a CONST_INT for the integer VAL). */
1784:
1785: if (GET_RTX_LENGTH (code) == 1)
1786: {
1787: register int arg0;
1788:
1789: if (const_arg0 == 0 || GET_CODE (const_arg0) != CONST_INT)
1790: return x;
1791:
1792: arg0 = INTVAL (const_arg0);
1793:
1794: switch (GET_CODE (x))
1795: {
1796: case NOT:
1797: val = ~ arg0;
1798: break;
1799:
1800: case NEG:
1801: val = - arg0;
1802: break;
1803:
1804: case TRUNCATE:
1805: val = arg0;
1806: break;
1807:
1808: case ZERO_EXTEND:
1809: {
1810: enum machine_mode mode = GET_MODE (XEXP (x, 0));
1811: if (mode == VOIDmode)
1812: return x;
1813: val = arg0 & ~((-1) << GET_MODE_BITSIZE (mode));
1814: break;
1815: }
1816:
1817: case SIGN_EXTEND:
1818: {
1819: enum machine_mode mode = GET_MODE (XEXP (x, 0));
1820: if (mode == VOIDmode)
1821: return x;
1822: val = arg0 & ~((-1) << GET_MODE_BITSIZE (mode));
1823: if (val & (1 << (GET_MODE_BITSIZE (mode) - 1)))
1824: val -= 1 << GET_MODE_BITSIZE (mode);
1825: break;
1826: }
1827:
1828: default:
1829: return x;
1830: }
1831: }
1832: else if (GET_RTX_LENGTH (code) == 2)
1833: {
1834: register int arg0, arg1, arg0s, arg1s;
1835:
1836: /* If 1st arg is the condition codes, 2nd must be zero
1837: and this must be a comparison.
1838: Decode the info on how the previous insn set the cc0
1839: and use that to deduce result of comparison. */
1840: if (XEXP (x, 0) == cc0_rtx)
1841: {
1842: if (prev_insn_cc0 == 0
1843: || const_arg1 != const0_rtx
1844: /* 0200 bit in prev_insn_cc0 means only zeroness is known,
1845: and sign is not known. */
1846: || ((prev_insn_cc0 & 0200)
1847: && code != EQ && code != NE))
1848: return x;
1849: if (code == LEU || code == LTU || code == GEU || code == GTU)
1850: arg0 = prev_insn_cc0 & 7;
1851: else
1852: arg0 = (prev_insn_cc0 >> 3) & 7;
1853: if (arg0 == 7) arg0 = -1;
1854:
1855: switch (code)
1856: {
1857: case LE:
1858: case LEU:
1859: return (arg0 <= 0) ? const1_rtx : const0_rtx;
1860: case LT:
1861: case LTU:
1862: return (arg0 < 0) ? const1_rtx : const0_rtx;
1863: case GE:
1864: case GEU:
1865: return (arg0 >= 0) ? const1_rtx : const0_rtx;
1866: case GT:
1867: case GTU:
1868: return (arg0 > 0) ? const1_rtx : const0_rtx;
1869: case NE:
1870: return (arg0 != 0) ? const1_rtx : const0_rtx;
1871: case EQ:
1872: return (arg0 == 0) ? const1_rtx : const0_rtx;
1873: default:
1874: abort ();
1875: }
1876: }
1877:
1878: if (const_arg0 == 0 || const_arg1 == 0
1879: || GET_CODE (const_arg0) != CONST_INT
1880: || GET_CODE (const_arg1) != CONST_INT)
1881: {
1882: /* Even if we can't compute a constant result,
1883: there are some cases worth simplifying. */
1884: if (code == PLUS)
1885: {
1886: if (const_arg0 == const0_rtx)
1887: return XEXP (x, 1);
1888: if (const_arg1 == const0_rtx)
1889: return XEXP (x, 0);
1890:
1891: /* Handle both-operands-constant cases. */
1892: if (const_arg0 != 0 && const_arg1 != 0)
1893: {
1894: if (GET_CODE (const_arg0) == CONST_INT)
1895: new = plus_constant (const_arg1, INTVAL (const_arg0));
1896: else if (GET_CODE (const_arg1) == CONST_INT)
1897: new = plus_constant (const_arg0, INTVAL (const_arg1));
1898: else
1899: {
1900: new = gen_rtx (PLUS, GET_MODE (x), const0_rtx, const0_rtx);
1901: XEXP (new, 0) = const_arg0;
1902: if (GET_CODE (const_arg0) == CONST)
1903: XEXP (new, 0) = XEXP (const_arg0, 0);
1904: XEXP (new, 1) = const_arg1;
1905: if (GET_CODE (const_arg1) == CONST)
1906: XEXP (new, 1) = XEXP (const_arg1, 0);
1907: new = gen_rtx (CONST, GET_MODE (new), new);
1908: }
1909: }
1910:
1911: else if (const_arg0 != 0
1912: && GET_CODE (const_arg0) == CONST_INT
1913: && GET_CODE (XEXP (x, 1)) == PLUS
1914: && (CONSTANT_P (XEXP (XEXP (x, 1), 0))
1915: || CONSTANT_P (XEXP (XEXP (x, 1), 1))))
1916: /* constant + (variable + constant)
1917: can result if an index register is made constant.
1918: We simplify this by adding the constants.
1919: If we did not, it would become an invalid address. */
1920: new = plus_constant (XEXP (x, 1),
1921: INTVAL (const_arg0));
1922: else if (const_arg1 != 0
1923: && GET_CODE (const_arg1) == CONST_INT
1924: && GET_CODE (XEXP (x, 0)) == PLUS
1925: && (CONSTANT_P (XEXP (XEXP (x, 0), 0))
1926: || CONSTANT_P (XEXP (XEXP (x, 0), 1))))
1927: new = plus_constant (XEXP (x, 0),
1928: INTVAL (const_arg1));
1929: }
1930: else if (code == MINUS)
1931: {
1932: if (const_arg1 == const0_rtx)
1933: return XEXP (x, 0);
1934:
1935: if (XEXP (x, 0) == XEXP (x, 1)
1936: || (const_arg0 != 0 && const_arg0 == const_arg1))
1937: {
1938: /* We can't assume x-x is 0 with IEEE floating point. */
1939: if (GET_MODE_CLASS (GET_MODE (x)) == MODE_INT)
1940: return const0_rtx;
1941: }
1942:
1943: if (const_arg0 != 0 && const_arg1 != 0
1944: /* Don't let a relocatable value get a negative coeff. */
1945: && GET_CODE (const_arg1) == CONST_INT)
1946: new = plus_constant (const_arg0, - INTVAL (const_arg1));
1947: }
1948:
1949: /* PLUS and MULT can appear inside of a MEM.
1950: In such situations, a constant term must come second. */
1951: else if (code == MULT || code == PLUS)
1952: if (copyflag && const_arg0 != 0)
1953: {
1954: if (! copied)
1955: x = gen_rtx (code, GET_MODE (x), XEXP (x, 0), XEXP (x, 1));
1956: XEXP (x, 0) = XEXP (x, 1);
1957: XEXP (x, 1) = const_arg0;
1958: }
1959:
1960: /* If integer truncation is being done with SUBREG,
1961: we can compute the result. */
1962:
1963: else if (code == SUBREG)
1964: if (SUBREG_WORD (x) == 0
1965: && const_arg0 != 0
1966: && GET_CODE (const_arg0) == CONST_INT
1967: && GET_MODE_SIZE (GET_MODE (x)) < GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))
1968: && (GET_MODE (x) == QImode || GET_MODE (x) == HImode
1969: || GET_MODE (x) == SImode))
1970: {
1971: arg0 = INTVAL (const_arg0);
1972: arg0 &= (1 << GET_MODE_BITSIZE (GET_MODE (x))) - 1;
1973: if (arg0 == INTVAL (const_arg0))
1974: new = const_arg0;
1975: else
1976: new = gen_rtx (CONST_INT, VOIDmode, arg0);
1977: }
1978:
1979: if (new != 0 && LEGITIMATE_CONSTANT_P (new))
1980: return new;
1981: return x;
1982: }
1983:
1984: /* Get the integer argument values in two forms:
1985: zero-extended in ARG0, ARG1 and sign-extended in ARG0S, ARG1S. */
1986:
1987: arg0 = INTVAL (const_arg0);
1988: arg1 = INTVAL (const_arg1);
1989:
1990: if (width < HOST_BITS_PER_INT)
1991: {
1992: arg0 &= (1 << width) - 1;
1993: arg1 &= (1 << width) - 1;
1994:
1995: arg0s = arg0;
1996: if (arg0s & (1 << (width - 1)))
1997: arg0s |= ((-1) << width);
1998:
1999: arg1s = arg1;
2000: if (arg1s & (1 << (width - 1)))
2001: arg1s |= ((-1) << width);
2002: }
2003: else
2004: {
2005: arg0s = arg0;
2006: arg1s = arg1;
2007: }
2008:
2009: /* Compute the value of the arithmetic. */
2010:
2011: switch (code)
2012: {
2013: case PLUS:
2014: val = arg0 + arg1;
2015: break;
2016:
2017: case MINUS:
2018: if (GET_MODE (x) == VOIDmode)
2019: /* Overflowless comparison:
2020: cannot represent an exact answer, so don't fold.
2021: This is used only to set the CC0,
2022: and fold_cc0 will take care of it. */
2023: return x;
2024: val = arg0 - arg1;
2025: break;
2026:
2027: case MULT:
2028: val = arg0s * arg1s;
2029: break;
2030:
2031: case DIV:
2032: if (arg1s == 0)
2033: return x;
2034: val = arg0s / arg1s;
2035: break;
2036:
2037: case MOD:
2038: if (arg1s == 0)
2039: return x;
2040: val = arg0s % arg1s;
2041: break;
2042:
2043: case UMULT:
2044: val = (unsigned) arg0 * arg1;
2045: break;
2046:
2047: case UDIV:
2048: if (arg1 == 0)
2049: return x;
2050: val = (unsigned) arg0 / arg1;
2051: break;
2052:
2053: case UMOD:
2054: if (arg1 == 0)
2055: return x;
2056: val = (unsigned) arg0 % arg1;
2057: break;
2058:
2059: case AND:
2060: val = arg0 & arg1;
2061: break;
2062:
2063: case IOR:
2064: val = arg0 | arg1;
2065: break;
2066:
2067: case XOR:
2068: val = arg0 ^ arg1;
2069: break;
2070:
2071: case NE:
2072: val = arg0 != arg1;
2073: break;
2074:
2075: case EQ:
2076: val = arg0 == arg1;
2077: break;
2078:
2079: case LE:
2080: val = arg0s <= arg1s;
2081: break;
2082:
2083: case LT:
2084: val = arg0s < arg1s;
2085: break;
2086:
2087: case GE:
2088: val = arg0s >= arg1s;
2089: break;
2090:
2091: case GT:
2092: val = arg0s > arg1s;
2093: break;
2094:
2095: case LEU:
2096: val = ((unsigned) arg0) <= ((unsigned) arg1);
2097: break;
2098:
2099: case LTU:
2100: val = ((unsigned) arg0) < ((unsigned) arg1);
2101: break;
2102:
2103: case GEU:
2104: val = ((unsigned) arg0) >= ((unsigned) arg1);
2105: break;
2106:
2107: case GTU:
2108: val = ((unsigned) arg0) > ((unsigned) arg1);
2109: break;
2110:
2111: case LSHIFT:
2112: val = ((unsigned) arg0) << arg1;
2113: break;
2114:
2115: case ASHIFT:
2116: val = arg0s << arg1;
2117: break;
2118:
2119: case ROTATERT:
2120: arg1 = - arg1;
2121: case ROTATE:
2122: {
2123: int size = GET_MODE_SIZE (GET_MODE (x)) * BITS_PER_UNIT;
2124: if (arg1 > 0)
2125: {
2126: arg1 %= size;
2127: val = ((((unsigned) arg0) << arg1)
2128: | (((unsigned) arg0) >> (size - arg1)));
2129: }
2130: else if (arg1 < 0)
2131: {
2132: arg1 = (- arg1) % size;
2133: val = ((((unsigned) arg0) >> arg1)
2134: | (((unsigned) arg0) << (size - arg1)));
2135: }
2136: else
2137: val = arg0;
2138: }
2139: break;
2140:
2141: case LSHIFTRT:
2142: val = ((unsigned) arg0) >> arg1;
2143: break;
2144:
2145: case ASHIFTRT:
2146: val = arg0s >> arg1;
2147: break;
2148:
2149: default:
2150: return x;
2151: }
2152: }
2153: else if (code == IF_THEN_ELSE && const_arg0 != 0
2154: && GET_CODE (const_arg0) == CONST_INT)
2155: return XEXP (x, ((INTVAL (const_arg0) != 0) ? 1 : 2));
2156: else if (code == SIGN_EXTRACT || code == ZERO_EXTRACT)
2157: {
2158: if (const_arg0 != 0 && const_arg1 != 0 && const_arg2 != 0
2159: && GET_CODE (const_arg0) == CONST_INT
2160: && GET_CODE (const_arg1) == CONST_INT
2161: && GET_CODE (const_arg2) == CONST_INT)
2162: {
2163: /* Extracting a bit-field from a constant */
2164: val = INTVAL (const_arg0);
2165: #ifdef BITS_BIG_ENDIAN
2166: val >>= (GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0)))
2167: - INTVAL (const_arg2) - INTVAL (const_arg1));
2168: #else
2169: val >>= INTVAL (const_arg2);
2170: #endif
2171: if (HOST_BITS_PER_INT != INTVAL (const_arg1))
2172: {
2173: /* First zero-extend. */
2174: val &= (1 << INTVAL (const_arg1)) - 1;
2175: /* If desired, propagate sign bit. */
2176: if (code == SIGN_EXTRACT
2177: && (val & (1 << (INTVAL (const_arg1) - 1))))
2178: val |= ~ (1 << INTVAL (const_arg1));
2179: }
2180: }
2181: else
2182: return x;
2183: }
2184: else
2185: return x;
2186:
2187: /* Clear the bits that don't belong in our mode,
2188: unless they and our sign bit are all one.
2189: So we get either a reasonable negative value or a reasonable
2190: unsigned value for this mode. */
2191: if (width < HOST_BITS_PER_INT)
2192: {
2193: if ((val & ((-1) << (width - 1)))
2194: != ((-1) << (width - 1)))
2195: val &= (1 << width) - 1;
2196: }
2197:
2198: /* Now make the new constant. */
2199: {
2200: rtx new = gen_rtx (CONST_INT, VOIDmode, val);
2201: return LEGITIMATE_CONSTANT_P (new) ? new : x;
2202: }
2203: }
2204:
2205: /* Given an expression X which is used to set CC0,
2206: return an integer recording (in the encoding used for prev_insn_cc0)
2207: how the condition codes would be set by that expression.
2208: Return 0 if the value is not constant
2209: or if there is any doubt what condition codes result from it. */
2210:
2211: static int
2212: fold_cc0 (x)
2213: rtx x;
2214: {
2215: if (GET_CODE (x) == MINUS && GET_MODE (x) == VOIDmode)
2216: {
2217: rtx y0 = fold_rtx (XEXP (x, 0), 0);
2218: rtx y1 = fold_rtx (XEXP (x, 1), 0);
2219: int u0, u1, s0, s1;
2220: enum machine_mode m;
2221:
2222: m = GET_MODE (y0);
2223: if (m == VOIDmode)
2224: m = GET_MODE (y1);
2225: if (m == VOIDmode)
2226: return 0;
2227:
2228: if (GET_CODE (y0) == REG)
2229: y0 = qty_const[reg_qty[REGNO (y0)]];
2230:
2231: if (y0 == 0 || GET_CODE (y0) != CONST_INT)
2232: return 0;
2233:
2234: if (GET_CODE (y1) == REG)
2235: y1 = qty_const[reg_qty[REGNO (y1)]];
2236:
2237: if (y1 == 0 || GET_CODE (y1) != CONST_INT)
2238: return 0;
2239:
2240: s0 = u0 = INTVAL (y0);
2241: s1 = u1 = INTVAL (y1);
2242:
2243: {
2244: int width = GET_MODE_BITSIZE (m);
2245: if (width < HOST_BITS_PER_INT)
2246: {
2247: s0 = u0 &= ~ ((-1) << width);
2248: s1 = u1 &= ~ ((-1) << width);
2249: if (u0 & (1 << (width - 1)))
2250: s0 |= ((-1) << width);
2251: if (u1 & (1 << (width - 1)))
2252: s1 |= ((-1) << width);
2253: }
2254: }
2255:
2256: return 0100 + ((s0 < s1 ? 7 : s0 > s1) << 3)
2257: + (((unsigned) u0 < (unsigned) u1) ? 7
2258: : ((unsigned) u0 > (unsigned) u1));
2259: }
2260: {
2261: rtx y0;
2262: int u0, s0;
2263: enum machine_mode m;
2264:
2265: y0 = fold_rtx (x, 0);
2266:
2267: m = GET_MODE (y0);
2268:
2269: if (GET_CODE (y0) == REG)
2270: y0 = qty_const[reg_qty[REGNO (y0)]];
2271:
2272: /* Register had no constant equivalent? We can't do anything. */
2273: if (y0 == 0)
2274: return 0;
2275:
2276: /* Value is frame-pointer plus a constant?
2277: That isn't zero, but we don't know its sign. */
2278: if (FIXED_BASE_PLUS_P (y0))
2279: return 0300 + (1<<3) + 1;
2280:
2281: /* Otherwise, only integers enable us to optimize. */
2282: if (GET_CODE (y0) != CONST_INT)
2283: return 0;
2284:
2285: s0 = u0 = INTVAL (y0);
2286: if (m != VOIDmode)
2287: {
2288: int width = GET_MODE_BITSIZE (m);
2289: if (width < HOST_BITS_PER_INT)
2290: {
2291: s0 = u0 &= ~ ((-1) << GET_MODE_BITSIZE (m));
2292: if (u0 & (1 << (GET_MODE_BITSIZE (m) - 1)))
2293: s0 |= ((-1) << GET_MODE_BITSIZE (m));
2294: }
2295: }
2296: return 0100 + ((s0 < 0 ? 7 : s0 > 0) << 3) + (u0 != 0);
2297: }
2298: }
2299:
2300: /* Attempt to prove that a loop will be executed >= 1 times,
2301: or prove it will be executed 0 times.
2302: If either can be proved, delete some of the code. */
2303:
2304: static void
2305: predecide_loop_entry (insn)
2306: register rtx insn;
2307: {
2308: register rtx jump = NEXT_INSN (insn);
2309: register rtx p = JUMP_LABEL (jump);
2310: register rtx loop_top_label = NEXT_INSN (NEXT_INSN (jump));
2311: enum { UNK, DELETE_LOOP, DELETE_JUMP } disposition = UNK;
2312: int count = 0;
2313:
2314: /* Trace the flow of control through the end test,
2315: propagating constants, to see if result is determined. */
2316: prev_insn_cc0 = 0;
2317: /* Avoid infinite loop if we find a cycle of jumps. */
2318: while (count < 10)
2319: {
2320: /* At end of function? Means rtl is inconsistent,
2321: but this can happen when stmt.c gets confused
2322: by a syntax error. */
2323: if (p == 0)
2324: break;
2325: /* Arriving at end of loop means endtest will drop out. */
2326: if (GET_CODE (p) == NOTE
2327: && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
2328: {
2329: disposition = DELETE_LOOP;
2330: break;
2331: }
2332: else if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == NOTE)
2333: ;
2334: /* We only know how to handle two kinds of insns:
2335: conditional jumps, and those that set the condition codes. */
2336: else if (GET_CODE (p) == INSN && GET_CODE (PATTERN (p)) == SET
2337: && SET_DEST (PATTERN (p)) == cc0_rtx)
2338: {
2339: prev_insn_cc0 = fold_cc0 (copy_rtx (SET_SRC (PATTERN (p))));
2340: }
2341: else if (GET_CODE (p) == JUMP_INSN
2342: && GET_CODE (PATTERN (p)) == SET
2343: && SET_DEST (PATTERN (p)) == pc_rtx)
2344: {
2345: register rtx target
2346: = fold_rtx (SET_SRC (PATTERN (p)), 1);
2347: if (GET_CODE (target) == LABEL_REF)
2348: p = XEXP (target, 0);
2349: else if (target != pc_rtx)
2350: /* If destination of jump is not fixed, give up. */
2351: break;
2352: count++;
2353: }
2354: /* Any other kind of insn means we don't know
2355: what result the test will have. */
2356: else
2357: break;
2358:
2359: /* Arriving at top of loop means we can drop straight in.
2360: Check here because we can arrive only via a jump insn
2361: which would have changed P above. */
2362: if (p == loop_top_label)
2363: {
2364: disposition = DELETE_JUMP;
2365: break;
2366: }
2367: /* We went past one insn; consider the next. */
2368: p = NEXT_INSN (p);
2369: }
2370: if (disposition == DELETE_JUMP)
2371: {
2372: /* We know the loop test will succeed the first time,
2373: so delete the jump to the test; drop right into loop.
2374: Note that one call to delete_insn gets the BARRIER as well. */
2375: delete_insn (jump);
2376: }
2377: if (disposition == DELETE_LOOP)
2378: {
2379: /* We know the endtest will fail and drop right out of the loop,
2380: but it isn't safe to delete the loop here.
2381: There could be jumps into it from outside.
2382: So make the entry-jump jump around the loop.
2383: This will cause find_basic_blocks to delete it if appropriate. */
2384: register rtx label = gen_label_rtx ();
2385: emit_label_after (label, p);
2386: redirect_jump (jump, label);
2387: }
2388: }
2389:
2390: /* CSE processing for one instruction.
2391: First simplify sources and addresses of all assignments
2392: in the instruction, using previously-computed equivalents values.
2393: Then install the new sources and destinations in the table
2394: of available values. */
2395:
2396: static rtx set[MAX_SETS_PER_INSN];
2397: static struct table_elt *src_elt[MAX_SETS_PER_INSN];
2398: static int src_hash_code[MAX_SETS_PER_INSN];
2399: static int dest_hash_code[MAX_SETS_PER_INSN];
2400: static char src_in_memory[MAX_SETS_PER_INSN];
2401: static char src_in_struct[MAX_SETS_PER_INSN];
2402: static rtx inner_dest[MAX_SETS_PER_INSN];
2403: static char src_volatile[MAX_SETS_PER_INSN];
2404:
2405: static void
2406: cse_insn (insn)
2407: rtx insn;
2408: {
2409: register rtx x = PATTERN (insn);
2410: register int i;
2411: register int n_sets = 0;
2412:
2413: /* Records what this insn does to set CC0,
2414: using same encoding used for prev_insn_cc0. */
2415: int this_insn_cc0 = 0;
2416: struct write_data writes_memory;
2417: static struct write_data init = {0, 0, 0};
2418:
2419: rtx src_eqv = 0;
2420: struct table_elt *src_eqv_elt = 0;
2421: int src_eqv_in_memory;
2422: int src_eqv_in_struct;
2423: int src_eqv_volatile = 0;
2424: int src_eqv_hash_code;
2425:
2426: this_insn = insn;
2427: writes_memory = init;
2428:
2429: /* Find all the SETs and CLOBBERs in this instruction.
2430: Record all the SETs in the array `set' and count them.
2431: Also determine whether there is a CLOBBER that invalidates
2432: all memory references, or all references at varying addresses. */
2433:
2434: if (GET_CODE (x) == SET)
2435: {
2436: rtx tem;
2437: n_sets = 1;
2438: set[0] = x;
2439: tem = find_reg_note (insn, REG_EQUIV, 0);
2440: if (tem == 0)
2441: tem = find_reg_note (insn, REG_EQUAL, 0);
2442: if (tem) src_eqv = XEXP (tem, 0);
2443:
2444: /* Return now for unconditional jumps.
2445: They never need cse processing, so this does not hurt.
2446: The reason is not efficiency but rather
2447: so that we can test at the end for instructions
2448: that have been simplified to unconditional jumps
2449: and not be misled by unchanged instructions
2450: that were unconditional jumps to begin with. */
2451: if (SET_DEST (x) == pc_rtx
2452: && GET_CODE (SET_SRC (x)) == LABEL_REF)
2453: return;
2454: }
2455: else if (GET_CODE (x) == PARALLEL)
2456: {
2457: register int lim = XVECLEN (x, 0);
2458: for (i = 0; i < lim; i++)
2459: {
2460: register rtx y = XVECEXP (x, 0, i);
2461: if (GET_CODE (y) == SET)
2462: set[n_sets++] = y;
2463: else if (GET_CODE (y) == CLOBBER)
2464: note_mem_written (XEXP (y, 0), &writes_memory);
2465: else if (GET_CODE (y) == CALL)
2466: canon_reg (y);
2467: }
2468: }
2469: else if (GET_CODE (x) == CLOBBER)
2470: note_mem_written (XEXP (x, 0), &writes_memory);
2471: else if (GET_CODE (x) == CALL)
2472: canon_reg (x);
2473:
2474: if (n_sets == 0)
2475: {
2476: invalidate_from_clobbers (&writes_memory, x);
2477: return;
2478: }
2479:
2480: /* Canonicalize sources and addresses of destinations.
2481: set src_elt[i] to the class each source belongs to.
2482: Detect assignments from or to volatile things
2483: and set set[i] to zero so they will be ignored
2484: in the rest of this function.
2485:
2486: Nothing in this loop changes the hash table or the register chains. */
2487:
2488: for (i = 0; i < n_sets; i++)
2489: {
2490: register rtx src, dest;
2491: register struct table_elt *elt;
2492: enum machine_mode mode;
2493:
2494: dest = SET_DEST (set[i]);
2495: src = SET_SRC (set[i]);
2496:
2497: /* If SRC is a constant that has no machine mode,
2498: hash it with the destination's machine mode.
2499: This way we can keep different modes separate. */
2500:
2501: mode = GET_MODE (src) == VOIDmode ? GET_MODE (dest) : GET_MODE (src);
2502:
2503: /* Replace each registers in SRC with oldest equivalent register,
2504: but if DEST is a register do not replace it if it appears in SRC. */
2505:
2506: if (GET_CODE (dest) == REG)
2507: {
2508: int tem = reg_qty[REGNO (dest)];
2509: reg_qty[REGNO (dest)] = REGNO (dest);
2510: src = canon_reg (src);
2511: if (src_eqv)
2512: src_eqv = canon_reg (src_eqv);
2513: reg_qty[REGNO (dest)] = tem;
2514: }
2515: else
2516: {
2517: src = canon_reg (src);
2518: if (src_eqv)
2519: src_eqv = canon_reg (src_eqv);
2520: }
2521:
2522: if (src_eqv)
2523: {
2524: enum machine_mode eqvmode = mode;
2525: if (GET_CODE (dest) == STRICT_LOW_PART)
2526: eqvmode = GET_MODE (SUBREG_REG (XEXP (dest, 0)));
2527: do_not_record = 0;
2528: hash_arg_in_memory = 0;
2529: hash_arg_in_struct = 0;
2530: src_eqv = fold_rtx (src_eqv, 0);
2531: src_eqv_hash_code = HASH (src_eqv, eqvmode);
2532:
2533: /* Replace the src_eqv with its cheapest equivalent. */
2534:
2535: if (!do_not_record)
2536: {
2537: elt = lookup (src_eqv, src_eqv_hash_code, eqvmode);
2538: if (elt && elt != elt->first_same_value)
2539: {
2540: elt = elt->first_same_value;
2541: /* Find the cheapest one that is still valid. */
2542: while ((GET_CODE (elt->exp) != REG
2543: && !exp_equiv_p (elt->exp, elt->exp, 1))
2544: || elt->equivalence_only)
2545: elt = elt->next_same_value;
2546: src_eqv = copy_rtx (elt->exp);
2547: hash_arg_in_memory = 0;
2548: hash_arg_in_struct = 0;
2549: src_eqv_hash_code = HASH (src_eqv, elt->mode);
2550: }
2551: src_eqv_elt = elt;
2552: }
2553: else
2554: src_eqv = 0;
2555:
2556: src_eqv_in_memory = hash_arg_in_memory;
2557: src_eqv_in_struct = hash_arg_in_struct;
2558: }
2559:
2560: /* Compute SRC's hash code, and also notice if it
2561: should not be recorded at all. In that case,
2562: prevent any further processing of this assignment. */
2563: do_not_record = 0;
2564: hash_arg_in_memory = 0;
2565: hash_arg_in_struct = 0;
2566: src = fold_rtx (src, 0);
2567: /* If we have (NOT Y), see if Y is known to be (NOT Z).
2568: If so, (NOT Y) simplifies to Z. */
2569: if (GET_CODE (src) == NOT || GET_CODE (src) == NEG)
2570: {
2571: rtx y = lookup_as_function (XEXP (src, 0), GET_CODE (src));
2572: if (y != 0)
2573: src = y;
2574: }
2575:
2576: /* If storing a constant value in a register that
2577: previously held the constant value 0,
2578: record this fact with a REG_WAS_0 note on this insn. */
2579: if (GET_CODE (src) == CONST_INT
2580: && GET_CODE (dest) == REG
2581: && n_sets == 0
2582: && qty_const[reg_qty[REGNO (dest)]] == const0_rtx)
2583: REG_NOTES (insn) = gen_rtx (INSN_LIST, REG_WAS_0,
2584: qty_const_insn[reg_qty[REGNO (dest)]],
2585: REG_NOTES (insn));
2586:
2587: src_hash_code[i] = HASH (src, mode);
2588:
2589: src_volatile[i] = do_not_record;
2590:
2591: #if 0
2592: /* This code caused multiple hash-table entries
2593: to be created for registers. Invalidation
2594: would only get one, leaving others that didn't belong.
2595: I don't know what good this ever did. */
2596: if (GET_CODE (src) == REG)
2597: {
2598: src_in_memory[i] = 0;
2599: src_elt[i] = 0;
2600: }
2601: else ...;
2602: #endif
2603: /* If source is a perverse subreg (such as QI treated as an SI),
2604: treat it as volatile. It may do the work of an SI in one context
2605: where the extra bits are not being used, but cannot replace an SI
2606: in general. */
2607: if (GET_CODE (src) == SUBREG
2608: && (GET_MODE_SIZE (GET_MODE (src))
2609: > GET_MODE_SIZE (GET_MODE (SUBREG_REG (src)))))
2610: src_volatile[i] = 1;
2611: else if (!src_volatile[i])
2612: {
2613: /* Replace the source with its cheapest equivalent. */
2614:
2615: elt = lookup (src, src_hash_code[i], mode);
2616: if (elt && elt != elt->first_same_value)
2617: {
2618: elt = elt->first_same_value;
2619: /* Find the cheapest one that is still valid. */
2620: while ((GET_CODE (elt->exp) != REG
2621: && !exp_equiv_p (elt->exp, elt->exp, 1))
2622: || elt->equivalence_only)
2623: elt = elt->next_same_value;
2624: src = copy_rtx (elt->exp);
2625: hash_arg_in_memory = 0;
2626: hash_arg_in_struct = 0;
2627: src_hash_code[i] = HASH (src, elt->mode);
2628: }
2629:
2630: /* If ELT is a constant, is there a register
2631: linearly related to it? If so, replace it
2632: with the sum of that register plus an offset. */
2633:
2634: if (GET_CODE (src) == CONST && n_sets == 1
2635: && SET_DEST (set[i]) != cc0_rtx)
2636: {
2637: rtx newsrc = use_related_value (src, elt);
2638: if (newsrc == 0 && src_eqv != 0)
2639: newsrc = use_related_value (src_eqv, src_eqv_elt);
2640: if (newsrc)
2641: {
2642: rtx oldsrc = src;
2643: src = newsrc;
2644: hash_arg_in_memory = 0;
2645: hash_arg_in_struct = 0;
2646: src_hash_code[i] = HASH (src, GET_MODE (src));
2647: /* The new expression for the SRC has the same value
2648: as the previous one; so if the previous one is in
2649: the hash table, put the new one in as equivalent. */
2650: if (elt != 0)
2651: elt = insert (src, elt->first_same_value, src_hash_code[i],
2652: elt->mode);
2653: else
2654: {
2655: /* Maybe the new expression is in the table already. */
2656: elt = lookup (src, src_hash_code[i], mode);
2657: /* And maybe a register contains the same value. */
2658: if (elt && elt != elt->first_same_value)
2659: {
2660: elt = elt->first_same_value;
2661: /* Find the cheapest one that is still valid. */
2662: while ((GET_CODE (elt->exp) != REG
2663: && !exp_equiv_p (elt->exp, elt->exp, 1))
2664: || elt->equivalence_only)
2665: elt = elt->next_same_value;
2666: src = copy_rtx (elt->exp);
2667: hash_arg_in_memory = 0;
2668: hash_arg_in_struct = 0;
2669: src_hash_code[i] = HASH (src, elt->mode);
2670: }
2671: }
2672:
2673: /* This would normally be inhibited by the REG_EQUIV
2674: note we are about to make. */
2675: SET_SRC (set[i]) = src;
2676:
2677: /* Record the actual constant value in a REG_EQUIV note. */
2678: if (GET_CODE (SET_DEST (set[i])) == REG)
2679: REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_EQUIV,
2680: oldsrc, 0);
2681: }
2682: }
2683:
2684: src_elt[i] = elt;
2685: src_in_memory[i] = hash_arg_in_memory;
2686: src_in_struct[i] = hash_arg_in_struct;
2687: }
2688:
2689: /* Either canon_reg or the copy_rtx may have changed this. */
2690: /* Note it is not safe to replace the sources if there
2691: is more than one set. We could get an insn
2692: [(set (reg) (reg)) (set (reg) (reg))], which is probably
2693: not in the machine description.
2694: This case we could handle by breaking into several insns.
2695: Cases of partial substitution cannot win at all. */
2696: /* Also, if this insn is setting a "constant" register,
2697: we may not replace the value that is given to it. */
2698: if (n_sets == 1)
2699: if (REG_NOTES (insn) == 0
2700: || REG_NOTE_KIND (REG_NOTES (insn)) != REG_EQUIV)
2701: SET_SRC (set[i]) = src;
2702:
2703: do_not_record = 0;
2704:
2705: /* Look within any SIGN_EXTRACT or ZERO_EXTRACT
2706: to the MEM or REG within it. */
2707: while (1)
2708: {
2709: if (GET_CODE (dest) == SIGN_EXTRACT
2710: || GET_CODE (dest) == ZERO_EXTRACT)
2711: {
2712: XEXP (dest, 1) = canon_reg (XEXP (dest, 1));
2713: XEXP (dest, 2) = canon_reg (XEXP (dest, 2));
2714: dest = XEXP (dest, 0);
2715: }
2716: else if (GET_CODE (dest) == SUBREG
2717: || GET_CODE (dest) == STRICT_LOW_PART)
2718: dest = XEXP (dest, 0);
2719: else
2720: break;
2721: }
2722:
2723: inner_dest[i] = dest;
2724:
2725: /* If storing into memory, do cse on the memory address.
2726: Also compute the hash code of the destination now,
2727: before the effects of this instruction are recorded,
2728: since the register values used in the address computation
2729: are those before this instruction. */
2730: if (GET_CODE (dest) == MEM)
2731: {
2732: register rtx addr;
2733: register int hash;
2734:
2735: canon_reg (dest);
2736: dest = fold_rtx (dest, 0);
2737: addr = XEXP (dest, 0);
2738:
2739: /* Pushing or popping does not invalidate anything. */
2740: if ((GET_CODE (addr) == PRE_DEC || GET_CODE (addr) == PRE_INC
2741: || GET_CODE (addr) == POST_DEC || GET_CODE (addr) == POST_INC)
2742: && GET_CODE (XEXP (addr, 0)) == REG
2743: && REGNO (XEXP (addr, 0)) == STACK_POINTER_REGNUM)
2744: ;
2745: else
2746: /* Otherwise, decide whether we invalidate
2747: everything in memory, or just things at non-fixed places.
2748: Writing a large aggregate must invalidate everything
2749: because we don't know how long it is. */
2750: note_mem_written (dest, &writes_memory);
2751:
2752: /* Do not consider addresses of local and argument slots.
2753: The MEM expressions for args and non-register local variables
2754: are made only once and inserted in many instructions,
2755: as well as being used to control symbol table output.
2756: It is not safe to clobber them. */
2757: if ((GET_CODE (addr) == PLUS
2758: && GET_CODE (XEXP (addr, 0)) == REG
2759: && GET_CODE (XEXP (addr, 1)) == CONST_INT
2760: && (hash = REGNO (XEXP (addr, 0)),
2761: hash == FRAME_POINTER_REGNUM || hash == ARG_POINTER_REGNUM))
2762: || (GET_CODE (addr) == REG
2763: && (hash = REGNO (addr),
2764: hash == FRAME_POINTER_REGNUM || hash == ARG_POINTER_REGNUM)))
2765: dest_hash_code[i] = safe_hash (dest) % NBUCKETS;
2766: else
2767: {
2768: /* Look for a simpler equivalent for the destination address. */
2769: hash = HASH (addr, Pmode);
2770: if (! do_not_record)
2771: {
2772: elt = lookup (addr, hash, Pmode);
2773: dest_hash_code[i] = ((int) MEM + hash) % NBUCKETS;
2774:
2775: if (elt && elt != elt->first_same_value)
2776: {
2777: elt = elt->first_same_value;
2778: /* Find the cheapest one that is still valid. */
2779: while ((GET_CODE (elt->exp) != REG
2780: && !exp_equiv_p (elt->exp, elt->exp, 1))
2781: || elt->equivalence_only)
2782: elt = elt->next_same_value;
2783:
2784: addr = copy_rtx (elt->exp);
2785: /* Create a new MEM rtx, in case the old one
2786: is shared somewhere else. */
2787: dest = gen_rtx (MEM, GET_MODE (dest), addr);
2788: dest->volatil = inner_dest[i]->volatil;
2789: SET_DEST (set[i]) = dest;
2790: inner_dest[i] = dest;
2791: }
2792: }
2793: }
2794: }
2795:
2796: /* Don't enter a bit-field in the hash table
2797: because the value in it after the store
2798: may not equal what was stored, due to truncation. */
2799:
2800: if (GET_CODE (SET_DEST (set[i])) == ZERO_EXTRACT
2801: || GET_CODE (SET_DEST (set[i])) == SIGN_EXTRACT)
2802: src_volatile[i] = 1, src_eqv = 0;
2803:
2804: /* No further processing for this assignment
2805: if destination is volatile. */
2806:
2807: else if (do_not_record
2808: || (GET_CODE (dest) == REG
2809: ? REGNO (dest) == STACK_POINTER_REGNUM
2810: : GET_CODE (dest) != MEM))
2811: set[i] = 0;
2812:
2813: if (set[i] != 0 && dest != SET_DEST (set[i]))
2814: dest_hash_code[i] = HASH (SET_DEST (set[i]), mode);
2815:
2816: if (dest == cc0_rtx
2817: && (GET_CODE (src) == MINUS
2818: || CONSTANT_P (src)
2819: || GET_CODE (src) == REG))
2820: this_insn_cc0 = fold_cc0 (src);
2821: }
2822:
2823: /* Now enter all non-volatile source expressions in the hash table
2824: if they are not already present.
2825: Record in src_elt the heads of their equivalence classes.
2826: This way we can insert the corresponding destinations into
2827: the same classes even if the actual sources are no longer in them
2828: (having been invalidated). */
2829:
2830: if (src_eqv && src_eqv_elt == 0 && set[0] != 0)
2831: {
2832: register struct table_elt *elt;
2833: rtx dest = SET_DEST (set[0]);
2834: enum machine_mode eqvmode = GET_MODE (dest);
2835:
2836: if (GET_CODE (dest) == STRICT_LOW_PART)
2837: eqvmode = GET_MODE (SUBREG_REG (XEXP (dest, 0)));
2838: if (insert_regs (src_eqv, 0, 0))
2839: src_eqv_hash_code = HASH (src_eqv, eqvmode);
2840: elt = insert (src_eqv, 0, src_eqv_hash_code, eqvmode);
2841: elt->in_memory = src_eqv_in_memory;
2842: elt->in_struct = src_eqv_in_struct;
2843: elt->equivalence_only = 1;
2844: src_eqv_elt = elt->first_same_value;
2845: }
2846:
2847: for (i = 0; i < n_sets; i++)
2848: if (set[i] && ! src_volatile[i])
2849: {
2850: if (GET_CODE (SET_DEST (set[i])) == STRICT_LOW_PART)
2851: {
2852: src_elt[i] = src_eqv_elt;
2853: src_hash_code[i] = src_eqv_hash_code;
2854: }
2855: else if (src_elt[i] == 0)
2856: {
2857: register rtx src = SET_SRC (set[i]);
2858: register rtx dest = SET_DEST (set[i]);
2859: register struct table_elt *elt;
2860: enum machine_mode mode
2861: = GET_MODE (src) == VOIDmode ? GET_MODE (dest) : GET_MODE (src);
2862:
2863: /* Note that these insert_regs calls cannot remove
2864: any of the src_elt's, because they would have failed to match
2865: if not still valid. */
2866: if (insert_regs (src, 0, 0))
2867: src_hash_code[i] = HASH (src, mode);
2868: elt = insert (src, src_eqv_elt, src_hash_code[i], mode);
2869: elt->in_memory = src_in_memory[i];
2870: elt->in_struct = src_in_struct[i];
2871: src_elt[i] = elt->first_same_value;
2872: }
2873: }
2874:
2875: invalidate_from_clobbers (&writes_memory, x);
2876:
2877: /* Now invalidate everything set by this instruction.
2878: If a SUBREG or other funny destination is being set,
2879: set[i] is still nonzero, so here we invalidate the reg
2880: a part of which is being set. */
2881:
2882: for (i = 0; i < n_sets; i++)
2883: if (set[i])
2884: {
2885: register rtx dest = inner_dest[i];
2886:
2887: /* Needed for registers to remove the register from its
2888: previous quantity's chain.
2889: Needed for memory if this is a nonvarying address, unless
2890: we have just done an invalidate_memory that covers even those. */
2891: if (GET_CODE (dest) == REG || GET_CODE (dest) == SUBREG
2892: || (! writes_memory.all && ! cse_rtx_addr_varies_p (dest)))
2893: invalidate (dest);
2894: }
2895:
2896: /* Make sure registers mentioned in destinations
2897: are safe for use in an expression to be inserted.
2898: This removes from the hash table
2899: any invalid entry that refers to one of these registers. */
2900:
2901: for (i = 0; i < n_sets; i++)
2902: if (set[i] && GET_CODE (SET_DEST (set[i])) != REG)
2903: mention_regs (SET_DEST (set[i]));
2904:
2905: /* We may have just removed some of the src_elt's from the hash table.
2906: So replace each one with the current head of the same class. */
2907:
2908: for (i = 0; i < n_sets; i++)
2909: if (set[i])
2910: {
2911: /* If the source is volatile, its destination goes in
2912: a class of its own. */
2913: if (src_volatile[i])
2914: src_elt[i] = 0;
2915:
2916: if (src_elt[i] && src_elt[i]->first_same_value == 0)
2917: /* If elt was removed, find current head of same class,
2918: or 0 if nothing remains of that class. */
2919: {
2920: register struct table_elt *elt = src_elt[i];
2921:
2922: while (elt && elt->first_same_value == 0)
2923: elt = elt->next_same_value;
2924: src_elt[i] = elt ? elt->first_same_value : 0;
2925: }
2926: }
2927:
2928: /* Now insert the destinations into their equivalence classes. */
2929:
2930: for (i = 0; i < n_sets; i++)
2931: if (set[i])
2932: {
2933: register rtx dest = SET_DEST (set[i]);
2934: register struct table_elt *elt;
2935:
2936: /* STRICT_LOW_PART isn't part of the value BEING set,
2937: and neither is the SUBREG inside it.
2938: Note that in this case SRC_ELT[I] is really SRC_EQV_ELT. */
2939: if (GET_CODE (dest) == STRICT_LOW_PART)
2940: dest = SUBREG_REG (XEXP (dest, 0));
2941:
2942: if (GET_CODE (dest) == REG || GET_CODE (dest) == SUBREG)
2943: /* Registers must also be inserted into chains for quantities. */
2944: if (insert_regs (dest, src_elt[i], 1))
2945: /* If `insert_regs' changes something, the hash code must be
2946: recalculated. */
2947: dest_hash_code[i] = safe_hash (dest) % NBUCKETS;
2948:
2949: elt = insert (dest, src_elt[i], dest_hash_code[i], GET_MODE (dest));
2950: elt->in_memory = GET_CODE (inner_dest[i]) == MEM;
2951: if (elt->in_memory)
2952: {
2953: elt->in_struct = (inner_dest[i]->in_struct
2954: || inner_dest[i] != SET_DEST (set[i]));
2955: }
2956: }
2957:
2958: /* Special handling for (set REG0 REG1)
2959: where REG0 is the "cheapest", cheaper than REG1.
2960: After cse, REG1 will probably not be used in the sequel,
2961: so (if easily done) change this insn to (set REG1 REG0) and
2962: replace REG1 with REG0 in the previous insn that computed their value.
2963: Then REG1 will become a dead store and won't cloud the situation
2964: for later optimizations. */
2965: if (n_sets == 1 && set[0] && GET_CODE (SET_DEST (set[0])) == REG
2966: && GET_CODE (SET_SRC (set[0])) == REG
2967: && rtx_equal_p (canon_reg (SET_SRC (set[0])), SET_DEST (set[0])))
2968: {
2969: rtx prev = PREV_INSN (insn);
2970: while (prev && GET_CODE (prev) == NOTE)
2971: prev = PREV_INSN (prev);
2972:
2973: if (prev && GET_CODE (prev) == INSN && GET_CODE (PATTERN (prev)) == SET
2974: && SET_DEST (PATTERN (prev)) == SET_SRC (set[0]))
2975: {
2976: rtx dest = SET_DEST (set[0]);
2977: SET_DEST (PATTERN (prev)) = dest;
2978: SET_DEST (set[0]) = SET_SRC (set[0]);
2979: SET_SRC (set[0]) = dest;
2980: }
2981: }
2982:
2983: /* Did this insn become an unconditional branch or become a no-op? */
2984: if (GET_CODE (insn) == JUMP_INSN
2985: && GET_CODE (x) == SET
2986: && SET_DEST (x) == pc_rtx)
2987: {
2988: if (SET_SRC (x) == pc_rtx)
2989: {
2990: PUT_CODE (insn, NOTE);
2991: NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
2992: NOTE_SOURCE_FILE (insn) = 0;
2993: cse_jumps_altered = 1;
2994: /* If previous insn just set CC0 for us, delete it too. */
2995: if (prev_insn_cc0 != 0)
2996: {
2997: PUT_CODE (prev_insn, NOTE);
2998: NOTE_LINE_NUMBER (prev_insn) = NOTE_INSN_DELETED;
2999: NOTE_SOURCE_FILE (prev_insn) = 0;
3000: }
3001: }
3002: else if (GET_CODE (SET_SRC (x)) == LABEL_REF)
3003: {
3004: emit_barrier_after (insn);
3005: cse_jumps_altered = 1;
3006: /* If previous insn just set CC0 for us, delete it too. */
3007: if (prev_insn_cc0 != 0)
3008: {
3009: PUT_CODE (prev_insn, NOTE);
3010: NOTE_LINE_NUMBER (prev_insn) = NOTE_INSN_DELETED;
3011: NOTE_SOURCE_FILE (prev_insn) = 0;
3012: }
3013: }
3014: }
3015:
3016: /* If this insn used to store a value based on CC0 but now value is constant,
3017: and the previous insn just set CC0 for us, delete previous insn.
3018: Here we use the fact that nothing expects CC0 to be valid over an insn,
3019: which is true until the final pass. */
3020: if (GET_CODE (x) == SET && prev_insn_cc0
3021: && CONSTANT_P (SET_SRC (x)))
3022: {
3023: PUT_CODE (prev_insn, NOTE);
3024: NOTE_LINE_NUMBER (prev_insn) = NOTE_INSN_DELETED;
3025: NOTE_SOURCE_FILE (prev_insn) = 0;
3026: }
3027:
3028: prev_insn_cc0 = this_insn_cc0;
3029: prev_insn = insn;
3030: }
3031:
3032: /* Store 1 in *WRITES_PTR for those categories of memory ref
3033: that must be invalidated when the expression WRITTEN is stored in.
3034: If WRITTEN is null, say everything must be invalidated. */
3035:
3036: static void
3037: note_mem_written (written, writes_ptr)
3038: rtx written;
3039: struct write_data *writes_ptr;
3040: {
3041: static struct write_data everything = {1, 1, 1};
3042:
3043: if (written == 0)
3044: *writes_ptr = everything;
3045: else if (GET_CODE (written) == MEM)
3046: {
3047: /* Pushing or popping the stack invalidates nothing. */
3048: rtx addr = XEXP (written, 0);
3049: if ((GET_CODE (addr) == PRE_DEC || GET_CODE (addr) == PRE_INC
3050: || GET_CODE (addr) == POST_DEC || GET_CODE (addr) == POST_INC)
3051: && GET_CODE (XEXP (addr, 0)) == REG
3052: && REGNO (XEXP (addr, 0)) == STACK_POINTER_REGNUM)
3053: return;
3054: if (GET_MODE (written) == BLKmode)
3055: *writes_ptr = everything;
3056: else if (cse_rtx_addr_varies_p (written))
3057: {
3058: /* A varying address that is a sum indicates an array element,
3059: and that's just as good as a structure element
3060: in implying that we need not invalidate scalar variables. */
3061: if (!(written->in_struct
3062: || GET_CODE (XEXP (written, 0)) == PLUS))
3063: writes_ptr->all = 1;
3064: writes_ptr->nonscalar = 1;
3065: }
3066: writes_ptr->var = 1;
3067: }
3068: }
3069:
3070: /* Perform invalidation on the basis of everything about an insn
3071: except for invalidating the actual places that are SET in it.
3072: This includes the places CLOBBERed, and anything that might
3073: alias with something that is SET or CLOBBERed.
3074:
3075: W points to the writes_memory for this insn, a struct write_data
3076: saying which kinds of memory references must be invalidated.
3077: X is the pattern of the insn. */
3078:
3079: static void
3080: invalidate_from_clobbers (w, x)
3081: struct write_data *w;
3082: rtx x;
3083: {
3084: /* If W->var is not set, W specifies no action.
3085: If W->all is set, this step gets all memory refs
3086: so they can be ignored in the rest of this function. */
3087: if (w->var)
3088: invalidate_memory (w);
3089:
3090: if (GET_CODE (x) == CLOBBER)
3091: {
3092: rtx ref = XEXP (x, 0);
3093: if (ref
3094: && (GET_CODE (ref) == REG || GET_CODE (ref) == SUBREG
3095: || (GET_CODE (ref) == MEM && ! w->all)))
3096: invalidate (ref);
3097: }
3098: else if (GET_CODE (x) == PARALLEL)
3099: {
3100: register int i;
3101: for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
3102: {
3103: register rtx y = XVECEXP (x, 0, i);
3104: if (GET_CODE (y) == CLOBBER)
3105: {
3106: rtx ref = XEXP (y, 0);
3107: if (ref
3108: &&(GET_CODE (ref) == REG || GET_CODE (ref) == SUBREG
3109: || (GET_CODE (ref) == MEM && !w->all)))
3110: invalidate (ref);
3111: }
3112: }
3113: }
3114: }
3115:
3116: static void cse_basic_block ();
3117:
3118: /* Perform cse on the instructions of a function.
3119: F is the first instruction.
3120: NREGS is one plus the highest pseudo-reg number used in the instruction.
3121:
3122: Returns 1 if jump_optimize should be redone due to simplifications
3123: in conditional jump instructions. */
3124:
3125: int
3126: cse_main (f, nregs)
3127: /* f is the first instruction of a chain of insns for one function */
3128: rtx f;
3129: /* nregs is the total number of registers used in it */
3130: int nregs;
3131: {
3132: register rtx insn = f;
3133: register int i;
3134:
3135: cse_jumps_altered = 0;
3136:
3137: init_recog ();
3138:
3139: max_reg = nregs;
3140:
3141: all_minus_one = (int *) alloca (nregs * sizeof (int));
3142: consec_ints = (int *) alloca (nregs * sizeof (int));
3143: for (i = 0; i < nregs; i++)
3144: {
3145: all_minus_one[i] = -1;
3146: consec_ints[i] = i;
3147: }
3148:
3149: reg_next_eqv = (int *) alloca (nregs * sizeof (int));
3150: reg_prev_eqv = (int *) alloca (nregs * sizeof (int));
3151: reg_qty = (int *) alloca (nregs * sizeof (int));
3152: reg_rtx = (rtx *) alloca (nregs * sizeof (rtx));
3153: reg_in_table = (int *) alloca (nregs * sizeof (int));
3154: reg_tick = (int *) alloca (nregs * sizeof (int));
3155:
3156: /* Discard all the free elements of the previous function
3157: since they are allocated in the temporarily obstack. */
3158: bzero (table, sizeof table);
3159: free_element_chain = 0;
3160: n_elements_made = 0;
3161:
3162: /* Loop over basic blocks */
3163: while (insn)
3164: {
3165: register rtx p = insn;
3166: register int i = 0;
3167: register int last_uid;
3168:
3169: /* Find end of next basic block */
3170: while (p && GET_CODE (p) != CODE_LABEL)
3171: {
3172: /* Don't cse out the end of a loop. This makes a difference
3173: only for the unusual loops that always execute at least once;
3174: all other loops have labels there so we will stop in any case.
3175: Cse'ing out the end of the loop is dangerous because it
3176: might cause an invariant expression inside the loop
3177: to be reused after the end of the loop. This would make it
3178: hard to move the expression out of the loop in loop.c,
3179: especially if it is one of several equivalent expressions
3180: and loop.c would like to eliminate it.
3181: The occasional optimizations lost by this will all come back
3182: if loop and cse are made to work alternatingly. */
3183: if (GET_CODE (p) == NOTE
3184: && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
3185: break;
3186:
3187: last_uid = INSN_UID (p);
3188: p = NEXT_INSN (p);
3189: i++;
3190: }
3191:
3192: cse_basic_block_end = last_uid;
3193: cse_basic_block_start = INSN_UID (insn);
3194:
3195: max_qty = max_reg + i * MAX_SETS_PER_INSN;
3196:
3197: cse_basic_block (insn, p);
3198:
3199: insn = p ? NEXT_INSN (p) : 0;
3200: }
3201:
3202: /* Tell refers_to_mem_p that qty_const info is not available. */
3203: qty_const = 0;
3204:
3205: if (max_elements_made < n_elements_made)
3206: max_elements_made = n_elements_made;
3207:
3208: return cse_jumps_altered;
3209: }
3210:
3211: static void
3212: cse_basic_block (from, to)
3213: register rtx from, to;
3214: {
3215: register rtx insn;
3216: int *qv1 = (int *) alloca (max_qty * sizeof (int));
3217: int *qv2 = (int *) alloca (max_qty * sizeof (int));
3218: rtx *qv3 = (rtx *) alloca (max_qty * sizeof (rtx));
3219:
3220: qty_first_reg = qv1;
3221: qty_last_reg = qv2;
3222: qty_const = qv3;
3223: qty_const_insn = (rtx *) alloca (max_qty * sizeof (rtx));
3224:
3225: new_basic_block ();
3226:
3227: for (insn = from; insn != to; insn = NEXT_INSN (insn))
3228: {
3229: register RTX_CODE code = GET_CODE (insn);
3230: if (code == INSN || code == JUMP_INSN || code == CALL_INSN)
3231: cse_insn (insn);
3232: /* Memory, and some registers, are invalidate by subroutine calls. */
3233: if (code == CALL_INSN)
3234: {
3235: register int i;
3236: static struct write_data everything = {1, 1, 1};
3237: invalidate_memory (&everything);
3238: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3239: if (call_used_regs[i] && reg_rtx[i]
3240: && i != FRAME_POINTER_REGNUM
3241: && i != ARG_POINTER_REGNUM)
3242: invalidate (reg_rtx[i]);
3243: }
3244: /* Loop beginnings are often followed by jumps
3245: (that enter the loop above the endtest).
3246: See if we can prove the loop will be executed at least once;
3247: if so, delete the jump. Also perhaps we can prove loop
3248: will never be executed and delete the entire thing. */
3249: if (code == NOTE
3250: && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
3251: && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN)
3252: {
3253: predecide_loop_entry (insn);
3254: /* Whether that jump was deleted or not,
3255: it certainly is the end of the basic block.
3256: Since the jump is unconditional,
3257: it requires no further processing here. */
3258: break;
3259: }
3260: }
3261:
3262: if (next_qty > max_qty)
3263: abort ();
3264: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.