![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to jump.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [GCC 2.x] / gcc|
Return to jump.c CVS log | Up to [GCC 2.x] / gcc |
1.1 root 1: /* Optimize jump instructions, for GNU compiler.
1.1.1.4 root 2: Copyright (C) 1987, 1988, 1989, 1991, 1992 Free Software Foundation, Inc.
1.1 root 3:
4: This file is part of GNU CC.
5:
6: GNU CC is free software; you can redistribute it and/or modify
7: it under the terms of the GNU General Public License as published by
8: the Free Software Foundation; either version 2, or (at your option)
9: any later version.
10:
11: GNU CC is distributed in the hope that it will be useful,
12: but WITHOUT ANY WARRANTY; without even the implied warranty of
13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14: GNU General Public License for more details.
15:
16: You should have received a copy of the GNU General Public License
17: along with GNU CC; see the file COPYING. If not, write to
18: the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
19:
20:
21: /* This is the jump-optimization pass of the compiler.
22: It is run two or three times: once before cse, sometimes once after cse,
23: and once after reload (before final).
24:
25: jump_optimize deletes unreachable code and labels that are not used.
26: It also deletes jumps that jump to the following insn,
27: and simplifies jumps around unconditional jumps and jumps
28: to unconditional jumps.
29:
30: Each CODE_LABEL has a count of the times it is used
31: stored in the LABEL_NUSES internal field, and each JUMP_INSN
32: has one label that it refers to stored in the
33: JUMP_LABEL internal field. With this we can detect labels that
34: become unused because of the deletion of all the jumps that
35: formerly used them. The JUMP_LABEL info is sometimes looked
36: at by later passes.
37:
38: Optionally, cross-jumping can be done. Currently it is done
39: only the last time (when after reload and before final).
40: In fact, the code for cross-jumping now assumes that register
41: allocation has been done, since it uses `rtx_renumbered_equal_p'.
42:
43: Jump optimization is done after cse when cse's constant-propagation
44: causes jumps to become unconditional or to be deleted.
45:
46: Unreachable loops are not detected here, because the labels
47: have references and the insns appear reachable from the labels.
48: find_basic_blocks in flow.c finds and deletes such loops.
49:
50: The subroutines delete_insn, redirect_jump, and invert_jump are used
51: from other passes as well. */
52:
53: #include "config.h"
54: #include "rtl.h"
55: #include "flags.h"
56: #include "hard-reg-set.h"
57: #include "regs.h"
58: #include "expr.h"
59: #include "insn-config.h"
60: #include "insn-flags.h"
61: #include "real.h"
62:
63: /* ??? Eventually must record somehow the labels used by jumps
64: from nested functions. */
65: /* Pre-record the next or previous real insn for each label?
66: No, this pass is very fast anyway. */
67: /* Condense consecutive labels?
68: This would make life analysis faster, maybe. */
69: /* Optimize jump y; x: ... y: jumpif... x?
70: Don't know if it is worth bothering with. */
71: /* Optimize two cases of conditional jump to conditional jump?
72: This can never delete any instruction or make anything dead,
73: or even change what is live at any point.
74: So perhaps let combiner do it. */
75:
76: /* Vector indexed by uid.
77: For each CODE_LABEL, index by its uid to get first unconditional jump
78: that jumps to the label.
79: For each JUMP_INSN, index by its uid to get the next unconditional jump
80: that jumps to the same label.
81: Element 0 is the start of a chain of all return insns.
82: (It is safe to use element 0 because insn uid 0 is not used. */
83:
84: static rtx *jump_chain;
85:
86: /* List of labels referred to from initializers.
87: These can never be deleted. */
88: rtx forced_labels;
89:
90: /* Maximum index in jump_chain. */
91:
92: static int max_jump_chain;
93:
94: /* Set nonzero by jump_optimize if control can fall through
95: to the end of the function. */
96: int can_reach_end;
97:
98: /* Indicates whether death notes are significant in cross jump analysis.
99: Normally they are not significant, because of A and B jump to C,
100: and R dies in A, it must die in B. But this might not be true after
101: stack register conversion, and we must compare death notes in that
102: case. */
103:
104: static int cross_jump_death_matters = 0;
105:
106: static int duplicate_loop_exit_test ();
107: void redirect_tablejump ();
108: static int delete_labelref_insn ();
109: static void mark_jump_label ();
110: void delete_jump ();
1.1.1.4 root 111: void delete_computation ();
1.1 root 112: static void delete_from_jump_chain ();
113: static int tension_vector_labels ();
114: static void find_cross_jump ();
115: static void do_cross_jump ();
116: static int jump_back_p ();
1.1.1.4 root 117:
118: extern rtx gen_jump ();
1.1 root 119:
120: /* Delete no-op jumps and optimize jumps to jumps
121: and jumps around jumps.
122: Delete unused labels and unreachable code.
123:
124: If CROSS_JUMP is 1, detect matching code
125: before a jump and its destination and unify them.
126: If CROSS_JUMP is 2, do cross-jumping, but pay attention to death notes.
127:
128: If NOOP_MOVES is nonzero, delete no-op move insns.
129:
130: If AFTER_REGSCAN is nonzero, then this jump pass is being run immediately
131: after regscan, and it is safe to use regno_first_uid and regno_last_uid.
132:
133: If `optimize' is zero, don't change any code,
134: just determine whether control drops off the end of the function.
135: This case occurs when we have -W and not -O.
136: It works because `delete_insn' checks the value of `optimize'
137: and refrains from actually deleting when that is 0. */
138:
139: void
140: jump_optimize (f, cross_jump, noop_moves, after_regscan)
141: rtx f;
142: int cross_jump;
143: int noop_moves;
144: int after_regscan;
145: {
1.1.1.4 root 146: register rtx insn, next;
1.1 root 147: int changed;
148: int first = 1;
149: int max_uid = 0;
150: rtx last_insn;
151:
152: cross_jump_death_matters = (cross_jump == 2);
153:
154: /* Initialize LABEL_NUSES and JUMP_LABEL fields. */
155:
156: for (insn = f; insn; insn = NEXT_INSN (insn))
157: {
158: if (GET_CODE (insn) == CODE_LABEL)
159: LABEL_NUSES (insn) = (LABEL_PRESERVE_P (insn) != 0);
160: else if (GET_CODE (insn) == JUMP_INSN)
161: JUMP_LABEL (insn) = 0;
162: if (INSN_UID (insn) > max_uid)
163: max_uid = INSN_UID (insn);
164: }
165:
166: max_uid++;
167:
168: /* Delete insns following barriers, up to next label. */
169:
170: for (insn = f; insn;)
171: {
172: if (GET_CODE (insn) == BARRIER)
173: {
174: insn = NEXT_INSN (insn);
175: while (insn != 0 && GET_CODE (insn) != CODE_LABEL)
176: {
177: if (GET_CODE (insn) == NOTE
178: && NOTE_LINE_NUMBER (insn) != NOTE_INSN_FUNCTION_END)
179: insn = NEXT_INSN (insn);
180: else
181: insn = delete_insn (insn);
182: }
183: /* INSN is now the code_label. */
184: }
185: else
186: insn = NEXT_INSN (insn);
187: }
188:
189: /* Leave some extra room for labels and duplicate exit test insns
190: we make. */
191: max_jump_chain = max_uid * 14 / 10;
192: jump_chain = (rtx *) alloca (max_jump_chain * sizeof (rtx));
193: bzero (jump_chain, max_jump_chain * sizeof (rtx));
194:
195: /* Mark the label each jump jumps to.
196: Combine consecutive labels, and count uses of labels.
197:
198: For each label, make a chain (using `jump_chain')
199: of all the *unconditional* jumps that jump to it;
200: also make a chain of all returns. */
201:
202: for (insn = f; insn; insn = NEXT_INSN (insn))
203: if ((GET_CODE (insn) == JUMP_INSN || GET_CODE (insn) == INSN
204: || GET_CODE (insn) == CALL_INSN)
205: && ! INSN_DELETED_P (insn))
206: {
207: mark_jump_label (PATTERN (insn), insn, cross_jump);
208: if (GET_CODE (insn) == JUMP_INSN)
209: {
210: if (JUMP_LABEL (insn) != 0 && simplejump_p (insn))
211: {
212: jump_chain[INSN_UID (insn)]
213: = jump_chain[INSN_UID (JUMP_LABEL (insn))];
214: jump_chain[INSN_UID (JUMP_LABEL (insn))] = insn;
215: }
216: if (GET_CODE (PATTERN (insn)) == RETURN)
217: {
218: jump_chain[INSN_UID (insn)] = jump_chain[0];
219: jump_chain[0] = insn;
220: }
221: }
222: }
223:
224: /* Keep track of labels used from static data;
225: they cannot ever be deleted. */
226:
227: for (insn = forced_labels; insn; insn = XEXP (insn, 1))
228: LABEL_NUSES (XEXP (insn, 0))++;
229:
230: /* Delete all labels already not referenced.
231: Also find the last insn. */
232:
233: last_insn = 0;
234: for (insn = f; insn; )
235: {
236: if (GET_CODE (insn) == CODE_LABEL && LABEL_NUSES (insn) == 0)
237: insn = delete_insn (insn);
238: else
239: {
240: last_insn = insn;
241: insn = NEXT_INSN (insn);
242: }
243: }
244:
245: if (!optimize)
246: {
247: /* See if there is still a NOTE_INSN_FUNCTION_END in this function.
248: If so record that this function can drop off the end. */
249:
250: insn = last_insn;
251: {
252: int n_labels = 1;
253: while (insn
254: /* One label can follow the end-note: the return label. */
255: && ((GET_CODE (insn) == CODE_LABEL && n_labels-- > 0)
256: /* Ordinary insns can follow it if returning a structure. */
257: || GET_CODE (insn) == INSN
258: /* If machine uses explicit RETURN insns, no epilogue,
259: then one of them follows the note. */
260: || (GET_CODE (insn) == JUMP_INSN
261: && GET_CODE (PATTERN (insn)) == RETURN)
262: /* Other kinds of notes can follow also. */
263: || (GET_CODE (insn) == NOTE
264: && NOTE_LINE_NUMBER (insn) != NOTE_INSN_FUNCTION_END)))
265: insn = PREV_INSN (insn);
266: }
267:
268: /* Report if control can fall through at the end of the function. */
269: if (insn && GET_CODE (insn) == NOTE
270: && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_END
271: && ! INSN_DELETED_P (insn))
272: can_reach_end = 1;
273:
274: /* Zero the "deleted" flag of all the "deleted" insns. */
275: for (insn = f; insn; insn = NEXT_INSN (insn))
276: INSN_DELETED_P (insn) = 0;
277: return;
278: }
279:
280: #ifdef HAVE_return
281: if (HAVE_return)
282: {
283: /* If we fall through to the epilogue, see if we can insert a RETURN insn
284: in front of it. If the machine allows it at this point (we might be
285: after reload for a leaf routine), it will improve optimization for it
286: to be there. */
287: insn = get_last_insn ();
288: while (insn && GET_CODE (insn) == NOTE)
289: insn = PREV_INSN (insn);
290:
291: if (insn && GET_CODE (insn) != BARRIER)
292: {
293: emit_jump_insn (gen_return ());
294: emit_barrier ();
295: }
296: }
297: #endif
298:
299: if (noop_moves)
300: for (insn = f; insn; )
301: {
1.1.1.4 root 302: next = NEXT_INSN (insn);
1.1 root 303:
304: if (GET_CODE (insn) == INSN)
305: {
306: register rtx body = PATTERN (insn);
307:
308: /* Combine stack_adjusts with following push_insns. */
309: #ifdef PUSH_ROUNDING
310: if (GET_CODE (body) == SET
311: && SET_DEST (body) == stack_pointer_rtx
312: && GET_CODE (SET_SRC (body)) == PLUS
313: && XEXP (SET_SRC (body), 0) == stack_pointer_rtx
314: && GET_CODE (XEXP (SET_SRC (body), 1)) == CONST_INT
315: && INTVAL (XEXP (SET_SRC (body), 1)) > 0)
316: {
317: rtx p;
318: rtx stack_adjust_insn = insn;
319: int stack_adjust_amount = INTVAL (XEXP (SET_SRC (body), 1));
320: int total_pushed = 0;
321: int pushes = 0;
322:
323: /* Find all successive push insns. */
324: p = insn;
325: /* Don't convert more than three pushes;
326: that starts adding too many displaced addresses
327: and the whole thing starts becoming a losing
328: proposition. */
329: while (pushes < 3)
330: {
331: rtx pbody, dest;
332: p = next_nonnote_insn (p);
333: if (p == 0 || GET_CODE (p) != INSN)
334: break;
335: pbody = PATTERN (p);
336: if (GET_CODE (pbody) != SET)
337: break;
338: dest = SET_DEST (pbody);
339: /* Allow a no-op move between the adjust and the push. */
340: if (GET_CODE (dest) == REG
341: && GET_CODE (SET_SRC (pbody)) == REG
342: && REGNO (dest) == REGNO (SET_SRC (pbody)))
343: continue;
344: if (! (GET_CODE (dest) == MEM
345: && GET_CODE (XEXP (dest, 0)) == POST_INC
346: && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx))
347: break;
348: pushes++;
1.1.1.5 ! root 349: if (total_pushed + GET_MODE_SIZE (GET_MODE (SET_DEST (pbody)))
1.1 root 350: > stack_adjust_amount)
351: break;
1.1.1.5 ! root 352: total_pushed += GET_MODE_SIZE (GET_MODE (SET_DEST (pbody)));
1.1 root 353: }
354:
355: /* Discard the amount pushed from the stack adjust;
356: maybe eliminate it entirely. */
357: if (total_pushed >= stack_adjust_amount)
358: {
359: delete_insn (stack_adjust_insn);
360: total_pushed = stack_adjust_amount;
361: }
362: else
363: XEXP (SET_SRC (PATTERN (stack_adjust_insn)), 1)
1.1.1.4 root 364: = GEN_INT (stack_adjust_amount - total_pushed);
1.1 root 365:
366: /* Change the appropriate push insns to ordinary stores. */
367: p = insn;
368: while (total_pushed > 0)
369: {
370: rtx pbody, dest;
371: p = next_nonnote_insn (p);
372: if (GET_CODE (p) != INSN)
373: break;
374: pbody = PATTERN (p);
375: if (GET_CODE (pbody) == SET)
376: break;
377: dest = SET_DEST (pbody);
378: if (! (GET_CODE (dest) == MEM
379: && GET_CODE (XEXP (dest, 0)) == POST_INC
380: && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx))
381: break;
1.1.1.5 ! root 382: total_pushed -= GET_MODE_SIZE (GET_MODE (SET_DEST (pbody)));
1.1 root 383: /* If this push doesn't fully fit in the space
384: of the stack adjust that we deleted,
385: make another stack adjust here for what we
386: didn't use up. There should be peepholes
387: to recognize the resulting sequence of insns. */
388: if (total_pushed < 0)
389: {
390: emit_insn_before (gen_add2_insn (stack_pointer_rtx,
1.1.1.4 root 391: GEN_INT (- total_pushed)),
1.1 root 392: p);
393: break;
394: }
395: XEXP (dest, 0)
396: = plus_constant (stack_pointer_rtx, total_pushed);
397: }
398: }
399: #endif
400:
401: /* Detect and delete no-op move instructions
402: resulting from not allocating a parameter in a register. */
403:
404: if (GET_CODE (body) == SET
405: && (SET_DEST (body) == SET_SRC (body)
406: || (GET_CODE (SET_DEST (body)) == MEM
407: && GET_CODE (SET_SRC (body)) == MEM
408: && rtx_equal_p (SET_SRC (body), SET_DEST (body))))
409: && ! (GET_CODE (SET_DEST (body)) == MEM
410: && MEM_VOLATILE_P (SET_DEST (body)))
411: && ! (GET_CODE (SET_SRC (body)) == MEM
412: && MEM_VOLATILE_P (SET_SRC (body))))
413: delete_insn (insn);
414:
415: /* Detect and ignore no-op move instructions
416: resulting from smart or fortuitous register allocation. */
417:
418: else if (GET_CODE (body) == SET)
419: {
420: int sreg = true_regnum (SET_SRC (body));
421: int dreg = true_regnum (SET_DEST (body));
422:
423: if (sreg == dreg && sreg >= 0)
424: delete_insn (insn);
425: else if (sreg >= 0 && dreg >= 0)
426: {
427: rtx trial;
1.1.1.4 root 428: rtx tem = find_equiv_reg (NULL_RTX, insn, 0,
429: sreg, NULL_PTR, dreg,
1.1 root 430: GET_MODE (SET_SRC (body)));
431:
432: #ifdef PRESERVE_DEATH_INFO_REGNO_P
433: /* Deleting insn could lose a death-note for SREG or DREG
434: so don't do it if final needs accurate death-notes. */
435: if (! PRESERVE_DEATH_INFO_REGNO_P (sreg)
436: && ! PRESERVE_DEATH_INFO_REGNO_P (dreg))
437: #endif
438: {
439: /* DREG may have been the target of a REG_DEAD note in
440: the insn which makes INSN redundant. If so, reorg
441: would still think it is dead. So search for such a
442: note and delete it if we find it. */
443: for (trial = prev_nonnote_insn (insn);
444: trial && GET_CODE (trial) != CODE_LABEL;
445: trial = prev_nonnote_insn (trial))
446: if (find_regno_note (trial, REG_DEAD, dreg))
447: {
448: remove_death (dreg, trial);
449: break;
450: }
451:
452: if (tem != 0
453: && GET_MODE (tem) == GET_MODE (SET_DEST (body)))
454: delete_insn (insn);
455: }
456: }
457: else if (dreg >= 0 && CONSTANT_P (SET_SRC (body))
1.1.1.4 root 458: && find_equiv_reg (SET_SRC (body), insn, 0, dreg,
459: NULL_PTR, 0,
460: GET_MODE (SET_DEST (body))))
1.1 root 461: {
462: /* This handles the case where we have two consecutive
463: assignments of the same constant to pseudos that didn't
464: get a hard reg. Each SET from the constant will be
465: converted into a SET of the spill register and an
466: output reload will be made following it. This produces
467: two loads of the same constant into the same spill
468: register. */
469:
470: rtx in_insn = insn;
471:
472: /* Look back for a death note for the first reg.
473: If there is one, it is no longer accurate. */
474: while (in_insn && GET_CODE (in_insn) != CODE_LABEL)
475: {
476: if ((GET_CODE (in_insn) == INSN
477: || GET_CODE (in_insn) == JUMP_INSN)
478: && find_regno_note (in_insn, REG_DEAD, dreg))
479: {
480: remove_death (dreg, in_insn);
481: break;
482: }
483: in_insn = PREV_INSN (in_insn);
484: }
485:
486: /* Delete the second load of the value. */
487: delete_insn (insn);
488: }
489: }
490: else if (GET_CODE (body) == PARALLEL)
491: {
492: /* If each part is a set between two identical registers or
493: a USE or CLOBBER, delete the insn. */
494: int i, sreg, dreg;
495: rtx tem;
496:
497: for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
498: {
499: tem = XVECEXP (body, 0, i);
500: if (GET_CODE (tem) == USE || GET_CODE (tem) == CLOBBER)
501: continue;
502:
503: if (GET_CODE (tem) != SET
504: || (sreg = true_regnum (SET_SRC (tem))) < 0
505: || (dreg = true_regnum (SET_DEST (tem))) < 0
506: || dreg != sreg)
507: break;
508: }
509:
510: if (i < 0)
511: delete_insn (insn);
512: }
513: #if !BYTES_BIG_ENDIAN /* Not worth the hair to detect this
514: in the big-endian case. */
515: /* Also delete insns to store bit fields if they are no-ops. */
516: else if (GET_CODE (body) == SET
517: && GET_CODE (SET_DEST (body)) == ZERO_EXTRACT
518: && XEXP (SET_DEST (body), 2) == const0_rtx
519: && XEXP (SET_DEST (body), 0) == SET_SRC (body)
520: && ! (GET_CODE (SET_SRC (body)) == MEM
521: && MEM_VOLATILE_P (SET_SRC (body))))
522: delete_insn (insn);
523: #endif /* not BYTES_BIG_ENDIAN */
524: }
525: insn = next;
526: }
527:
1.1.1.4 root 528: /* If we haven't yet gotten to reload and we have just run regscan,
529: delete any insn that sets a register that isn't used elsewhere.
530: This helps some of the optimizations below by having less insns
531: being jumped around. */
532:
533: if (! reload_completed && after_regscan)
534: for (insn = f; insn; insn = next)
535: {
536: rtx set = single_set (insn);
537:
538: next = NEXT_INSN (insn);
539:
540: if (set && GET_CODE (SET_DEST (set)) == REG
541: && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
542: && regno_first_uid[REGNO (SET_DEST (set))] == INSN_UID (insn)
543: && regno_last_uid[REGNO (SET_DEST (set))] == INSN_UID (insn)
544: && ! side_effects_p (SET_SRC (set)))
545: delete_insn (insn);
546: }
547:
1.1 root 548: /* Now iterate optimizing jumps until nothing changes over one pass. */
549: changed = 1;
550: while (changed)
551: {
552: changed = 0;
553:
554: for (insn = f; insn; insn = next)
555: {
556: rtx reallabelprev;
1.1.1.4 root 557: rtx temp, temp1, temp2, temp3, temp4, temp5, temp6;
1.1 root 558: rtx nlabel;
1.1.1.4 root 559: int this_is_simplejump, this_is_condjump, reversep;
1.1 root 560: #if 0
561: /* If NOT the first iteration, if this is the last jump pass
562: (just before final), do the special peephole optimizations.
563: Avoiding the first iteration gives ordinary jump opts
564: a chance to work before peephole opts. */
565:
566: if (reload_completed && !first && !flag_no_peephole)
567: if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
568: peephole (insn);
569: #endif
570:
571: /* That could have deleted some insns after INSN, so check now
572: what the following insn is. */
573:
574: next = NEXT_INSN (insn);
575:
576: /* See if this is a NOTE_INSN_LOOP_BEG followed by an unconditional
577: jump. Try to optimize by duplicating the loop exit test if so.
578: This is only safe immediately after regscan, because it uses
579: the values of regno_first_uid and regno_last_uid. */
580: if (after_regscan && GET_CODE (insn) == NOTE
581: && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
582: && (temp1 = next_nonnote_insn (insn)) != 0
583: && simplejump_p (temp1))
584: {
585: temp = PREV_INSN (insn);
586: if (duplicate_loop_exit_test (insn))
587: {
588: changed = 1;
589: next = NEXT_INSN (temp);
590: continue;
591: }
592: }
593:
594: if (GET_CODE (insn) != JUMP_INSN)
595: continue;
596:
597: this_is_simplejump = simplejump_p (insn);
598: this_is_condjump = condjump_p (insn);
599:
600: /* Tension the labels in dispatch tables. */
601:
602: if (GET_CODE (PATTERN (insn)) == ADDR_VEC)
603: changed |= tension_vector_labels (PATTERN (insn), 0);
604: if (GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
605: changed |= tension_vector_labels (PATTERN (insn), 1);
606:
607: /* If a dispatch table always goes to the same place,
608: get rid of it and replace the insn that uses it. */
609:
610: if (GET_CODE (PATTERN (insn)) == ADDR_VEC
611: || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
612: {
613: int i;
614: rtx pat = PATTERN (insn);
615: int diff_vec_p = GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC;
616: int len = XVECLEN (pat, diff_vec_p);
617: rtx dispatch = prev_real_insn (insn);
618:
619: for (i = 0; i < len; i++)
620: if (XEXP (XVECEXP (pat, diff_vec_p, i), 0)
621: != XEXP (XVECEXP (pat, diff_vec_p, 0), 0))
622: break;
623: if (i == len
1.1.1.4 root 624: && dispatch != 0
1.1 root 625: && GET_CODE (dispatch) == JUMP_INSN
626: && JUMP_LABEL (dispatch) != 0
627: /* Don't mess with a casesi insn. */
628: && !(GET_CODE (PATTERN (dispatch)) == SET
629: && (GET_CODE (SET_SRC (PATTERN (dispatch)))
630: == IF_THEN_ELSE))
631: && next_real_insn (JUMP_LABEL (dispatch)) == insn)
632: {
633: redirect_tablejump (dispatch,
634: XEXP (XVECEXP (pat, diff_vec_p, 0), 0));
635: changed = 1;
636: }
637: }
638:
639: reallabelprev = prev_active_insn (JUMP_LABEL (insn));
640:
641: /* If a jump references the end of the function, try to turn
642: it into a RETURN insn, possibly a conditional one. */
643: if (JUMP_LABEL (insn)
644: && next_active_insn (JUMP_LABEL (insn)) == 0)
1.1.1.4 root 645: changed |= redirect_jump (insn, NULL_RTX);
1.1 root 646:
647: /* Detect jump to following insn. */
648: if (reallabelprev == insn && condjump_p (insn))
649: {
650: delete_jump (insn);
651: changed = 1;
652: continue;
653: }
654:
1.1.1.2 root 655: /* If we have an unconditional jump preceded by a USE, try to put
1.1 root 656: the USE before the target and jump there. This simplifies many
657: of the optimizations below since we don't have to worry about
658: dealing with these USE insns. We only do this if the label
659: being branch to already has the identical USE or if code
660: never falls through to that label. */
661:
662: if (this_is_simplejump
663: && (temp = prev_nonnote_insn (insn)) != 0
664: && GET_CODE (temp) == INSN && GET_CODE (PATTERN (temp)) == USE
665: && (temp1 = prev_nonnote_insn (JUMP_LABEL (insn))) != 0
666: && (GET_CODE (temp1) == BARRIER
667: || (GET_CODE (temp1) == INSN
668: && rtx_equal_p (PATTERN (temp), PATTERN (temp1)))))
669: {
670: if (GET_CODE (temp1) == BARRIER)
671: {
1.1.1.4 root 672: emit_insn_after (PATTERN (temp), temp1);
1.1 root 673: temp1 = NEXT_INSN (temp1);
674: }
675:
1.1.1.4 root 676: delete_insn (temp);
1.1 root 677: redirect_jump (insn, get_label_before (temp1));
678: reallabelprev = prev_real_insn (temp1);
679: changed = 1;
680: }
681:
682: /* Simplify if (...) x = a; else x = b; by converting it
683: to x = b; if (...) x = a;
684: if B is sufficiently simple, the test doesn't involve X,
685: and nothing in the test modifies B or X.
686:
687: If we have small register classes, we also can't do this if X
688: is a hard register.
689:
690: If the "x = b;" insn has any REG_NOTES, we don't do this because
691: of the possibility that we are running after CSE and there is a
692: REG_EQUAL note that is only valid if the branch has already been
693: taken. If we move the insn with the REG_EQUAL note, we may
694: fold the comparison to always be false in a later CSE pass.
695: (We could also delete the REG_NOTES when moving the insn, but it
696: seems simpler to not move it.) An exception is that we can move
697: the insn if the only note is a REG_EQUAL or REG_EQUIV whose
698: value is the same as "b".
699:
700: INSN is the branch over the `else' part.
701:
702: We set:
703:
1.1.1.2 root 704: TEMP to the jump insn preceding "x = a;"
1.1 root 705: TEMP1 to X
706: TEMP2 to the insn that sets "x = b;"
1.1.1.4 root 707: TEMP3 to the insn that sets "x = a;"
708: TEMP4 to the set of "x = b"; */
1.1 root 709:
710: if (this_is_simplejump
711: && (temp3 = prev_active_insn (insn)) != 0
712: && GET_CODE (temp3) == INSN
1.1.1.4 root 713: && (temp4 = single_set (temp3)) != 0
714: && GET_CODE (temp1 = SET_DEST (temp4)) == REG
1.1 root 715: #ifdef SMALL_REGISTER_CLASSES
716: && REGNO (temp1) >= FIRST_PSEUDO_REGISTER
717: #endif
718: && (temp2 = next_active_insn (insn)) != 0
719: && GET_CODE (temp2) == INSN
1.1.1.4 root 720: && (temp4 = single_set (temp2)) != 0
721: && rtx_equal_p (SET_DEST (temp4), temp1)
722: && (GET_CODE (SET_SRC (temp4)) == REG
723: || GET_CODE (SET_SRC (temp4)) == SUBREG
724: || CONSTANT_P (SET_SRC (temp4)))
1.1 root 725: && (REG_NOTES (temp2) == 0
726: || ((REG_NOTE_KIND (REG_NOTES (temp2)) == REG_EQUAL
727: || REG_NOTE_KIND (REG_NOTES (temp2)) == REG_EQUIV)
728: && XEXP (REG_NOTES (temp2), 1) == 0
729: && rtx_equal_p (XEXP (REG_NOTES (temp2), 0),
1.1.1.4 root 730: SET_SRC (temp4))))
1.1 root 731: && (temp = prev_active_insn (temp3)) != 0
732: && condjump_p (temp) && ! simplejump_p (temp)
733: /* TEMP must skip over the "x = a;" insn */
734: && prev_real_insn (JUMP_LABEL (temp)) == insn
735: && no_labels_between_p (insn, JUMP_LABEL (temp))
736: /* There must be no other entries to the "x = b;" insn. */
737: && no_labels_between_p (JUMP_LABEL (temp), temp2)
738: /* INSN must either branch to the insn after TEMP2 or the insn
739: after TEMP2 must branch to the same place as INSN. */
740: && (reallabelprev == temp2
1.1.1.4 root 741: || ((temp5 = next_active_insn (temp2)) != 0
742: && simplejump_p (temp5)
743: && JUMP_LABEL (temp5) == JUMP_LABEL (insn))))
1.1 root 744: {
745: /* The test expression, X, may be a complicated test with
746: multiple branches. See if we can find all the uses of
747: the label that TEMP branches to without hitting a CALL_INSN
748: or a jump to somewhere else. */
749: rtx target = JUMP_LABEL (temp);
750: int nuses = LABEL_NUSES (target);
751: rtx p, q;
752:
753: /* Set P to the first jump insn that goes around "x = a;". */
754: for (p = temp; nuses && p; p = prev_nonnote_insn (p))
755: {
756: if (GET_CODE (p) == JUMP_INSN)
757: {
758: if (condjump_p (p) && ! simplejump_p (p)
759: && JUMP_LABEL (p) == target)
760: {
761: nuses--;
762: if (nuses == 0)
763: break;
764: }
765: else
766: break;
767: }
768: else if (GET_CODE (p) == CALL_INSN)
769: break;
770: }
771:
772: #ifdef HAVE_cc0
773: /* We cannot insert anything between a set of cc and its use
774: so if P uses cc0, we must back up to the previous insn. */
775: q = prev_nonnote_insn (p);
776: if (q && GET_RTX_CLASS (GET_CODE (q)) == 'i'
777: && sets_cc0_p (PATTERN (q)))
778: p = q;
779: #endif
780:
781: if (p)
782: p = PREV_INSN (p);
783:
784: /* If we found all the uses and there was no data conflict, we
785: can move the assignment unless we can branch into the middle
786: from somewhere. */
787: if (nuses == 0 && p
788: && no_labels_between_p (p, insn)
789: && ! reg_referenced_between_p (temp1, p, NEXT_INSN (temp3))
790: && ! reg_set_between_p (temp1, p, temp3)
1.1.1.4 root 791: && (GET_CODE (SET_SRC (temp4)) == CONST_INT
792: || ! reg_set_between_p (SET_SRC (temp4), p, temp2)))
1.1 root 793: {
1.1.1.4 root 794: emit_insn_after_with_line_notes (PATTERN (temp2), p, temp2);
795: delete_insn (temp2);
1.1 root 796:
797: /* Set NEXT to an insn that we know won't go away. */
798: next = next_active_insn (insn);
799:
800: /* Delete the jump around the set. Note that we must do
801: this before we redirect the test jumps so that it won't
802: delete the code immediately following the assignment
803: we moved (which might be a jump). */
804:
805: delete_insn (insn);
806:
807: /* We either have two consecutive labels or a jump to
808: a jump, so adjust all the JUMP_INSNs to branch to where
809: INSN branches to. */
810: for (p = NEXT_INSN (p); p != next; p = NEXT_INSN (p))
811: if (GET_CODE (p) == JUMP_INSN)
812: redirect_jump (p, target);
813:
814: changed = 1;
815: continue;
816: }
817: }
818:
1.1.1.4 root 819: #ifndef HAVE_cc0
820: /* If we have if (...) x = exp; and branches are expensive,
821: EXP is a single insn, does not have any side effects, cannot
822: trap, and is not too costly, convert this to
823: t = exp; if (...) x = t;
824:
825: Don't do this when we have CC0 because it is unlikely to help
826: and we'd need to worry about where to place the new insn and
827: the potential for conflicts. We also can't do this when we have
828: notes on the insn for the same reason as above.
829:
830: We set:
831:
832: TEMP to the "x = exp;" insn.
833: TEMP1 to the single set in the "x = exp; insn.
834: TEMP2 to "x". */
835:
836: if (! reload_completed
837: && this_is_condjump && ! this_is_simplejump
838: && BRANCH_COST >= 3
839: && (temp = next_nonnote_insn (insn)) != 0
840: && GET_CODE (temp) == INSN
841: && REG_NOTES (temp) == 0
842: && (reallabelprev == temp
843: || ((temp2 = next_active_insn (temp)) != 0
844: && simplejump_p (temp2)
845: && JUMP_LABEL (temp2) == JUMP_LABEL (insn)))
846: && (temp1 = single_set (temp)) != 0
847: && (temp2 = SET_DEST (temp1), GET_CODE (temp2) == REG)
848: && GET_MODE_CLASS (GET_MODE (temp2)) == MODE_INT
849: #ifdef SMALL_REGISTER_CLASSES
850: && REGNO (temp2) >= FIRST_PSEUDO_REGISTER
851: #endif
852: && GET_CODE (SET_SRC (temp1)) != REG
853: && GET_CODE (SET_SRC (temp1)) != SUBREG
854: && GET_CODE (SET_SRC (temp1)) != CONST_INT
855: && ! side_effects_p (SET_SRC (temp1))
856: && ! may_trap_p (SET_SRC (temp1))
857: && rtx_cost (SET_SRC (temp1)) < 10)
858: {
859: rtx new = gen_reg_rtx (GET_MODE (temp2));
860:
861: if (validate_change (temp, &SET_DEST (temp1), new, 0))
862: {
863: next = emit_insn_after (gen_move_insn (temp2, new), insn);
864: emit_insn_after_with_line_notes (PATTERN (temp),
865: PREV_INSN (insn), temp);
866: delete_insn (temp);
867: }
868: }
869:
870: /* Similarly, if it takes two insns to compute EXP but they
871: have the same destination. Here TEMP3 will be the second
872: insn and TEMP4 the SET from that insn. */
873:
874: if (! reload_completed
875: && this_is_condjump && ! this_is_simplejump
876: && BRANCH_COST >= 4
877: && (temp = next_nonnote_insn (insn)) != 0
878: && GET_CODE (temp) == INSN
879: && REG_NOTES (temp) == 0
880: && (temp3 = next_nonnote_insn (temp)) != 0
881: && GET_CODE (temp3) == INSN
882: && REG_NOTES (temp3) == 0
883: && (reallabelprev == temp3
884: || ((temp2 = next_active_insn (temp3)) != 0
885: && simplejump_p (temp2)
886: && JUMP_LABEL (temp2) == JUMP_LABEL (insn)))
887: && (temp1 = single_set (temp)) != 0
888: && (temp2 = SET_DEST (temp1), GET_CODE (temp2) == REG)
889: && GET_MODE_CLASS (GET_MODE (temp2)) == MODE_INT
890: #ifdef SMALL_REGISTER_CLASSES
891: && REGNO (temp2) >= FIRST_PSEUDO_REGISTER
892: #endif
893: && ! side_effects_p (SET_SRC (temp1))
894: && ! may_trap_p (SET_SRC (temp1))
895: && rtx_cost (SET_SRC (temp1)) < 10
896: && (temp4 = single_set (temp3)) != 0
897: && rtx_equal_p (SET_DEST (temp4), temp2)
898: && ! side_effects_p (SET_SRC (temp4))
899: && ! may_trap_p (SET_SRC (temp4))
900: && rtx_cost (SET_SRC (temp4)) < 10)
901: {
902: rtx new = gen_reg_rtx (GET_MODE (temp2));
903:
904: if (validate_change (temp, &SET_DEST (temp1), new, 0))
905: {
906: next = emit_insn_after (gen_move_insn (temp2, new), insn);
907: emit_insn_after_with_line_notes (PATTERN (temp),
908: PREV_INSN (insn), temp);
909: emit_insn_after_with_line_notes
910: (replace_rtx (PATTERN (temp3), temp2, new),
911: PREV_INSN (insn), temp3);
912: delete_insn (temp);
913: delete_insn (temp3);
914: }
915: }
916:
917: /* Finally, handle the case where two insns are used to
918: compute EXP but a temporary register is used. Here we must
919: ensure that the temporary register is not used anywhere else. */
920:
921: if (! reload_completed
922: && after_regscan
923: && this_is_condjump && ! this_is_simplejump
924: && BRANCH_COST >= 4
925: && (temp = next_nonnote_insn (insn)) != 0
926: && GET_CODE (temp) == INSN
927: && REG_NOTES (temp) == 0
928: && (temp3 = next_nonnote_insn (temp)) != 0
929: && GET_CODE (temp3) == INSN
930: && REG_NOTES (temp3) == 0
931: && (reallabelprev == temp3
932: || ((temp2 = next_active_insn (temp3)) != 0
933: && simplejump_p (temp2)
934: && JUMP_LABEL (temp2) == JUMP_LABEL (insn)))
935: && (temp1 = single_set (temp)) != 0
936: && (temp5 = SET_DEST (temp1), GET_CODE (temp5) == REG)
937: && REGNO (temp5) >= FIRST_PSEUDO_REGISTER
938: && regno_first_uid[REGNO (temp5)] == INSN_UID (temp)
939: && regno_last_uid[REGNO (temp5)] == INSN_UID (temp3)
940: && ! side_effects_p (SET_SRC (temp1))
941: && ! may_trap_p (SET_SRC (temp1))
942: && rtx_cost (SET_SRC (temp1)) < 10
943: && (temp4 = single_set (temp3)) != 0
944: && (temp2 = SET_DEST (temp4), GET_CODE (temp2) == REG)
945: && GET_MODE_CLASS (GET_MODE (temp2)) == MODE_INT
946: #ifdef SMALL_REGISTER_CLASSES
947: && REGNO (temp2) >= FIRST_PSEUDO_REGISTER
948: #endif
949: && rtx_equal_p (SET_DEST (temp4), temp2)
950: && ! side_effects_p (SET_SRC (temp4))
951: && ! may_trap_p (SET_SRC (temp4))
952: && rtx_cost (SET_SRC (temp4)) < 10)
953: {
954: rtx new = gen_reg_rtx (GET_MODE (temp2));
955:
956: if (validate_change (temp3, &SET_DEST (temp4), new, 0))
957: {
958: next = emit_insn_after (gen_move_insn (temp2, new), insn);
959: emit_insn_after_with_line_notes (PATTERN (temp),
960: PREV_INSN (insn), temp);
961: emit_insn_after_with_line_notes (PATTERN (temp3),
962: PREV_INSN (insn), temp3);
963: delete_insn (temp);
964: delete_insn (temp3);
965: }
966: }
967: #endif /* HAVE_cc0 */
968:
969: /* We deal with four cases:
970:
971: 1) x = a; if (...) x = b; and either A or B is zero,
972: 2) if (...) x = 0; and jumps are expensive,
973: 3) x = a; if (...) x = b; and A and B are constants where all the
974: set bits in A are also set in B and jumps are expensive, and
975: 4) x = a; if (...) x = b; and A and B non-zero, and jumps are
976: more expensive.
977: 5) if (...) x = b; if jumps are even more expensive.
978:
979: In each of these try to use a store-flag insn to avoid the jump.
980: (If the jump would be faster, the machine should not have
981: defined the scc insns!). These cases are often made by the
982: previous optimization.
1.1 root 983:
984: INSN here is the jump around the store. We set:
985:
986: TEMP to the "x = b;" insn.
987: TEMP1 to X.
988: TEMP2 to B (const0_rtx in the second case).
989: TEMP3 to A (X in the second case).
990: TEMP4 to the condition being tested.
991: TEMP5 to the earliest insn used to find the condition. */
992:
993: if (/* We can't do this after reload has completed. */
994: ! reload_completed
995: && this_is_condjump && ! this_is_simplejump
996: /* Set TEMP to the "x = b;" insn. */
997: && (temp = next_nonnote_insn (insn)) != 0
998: && GET_CODE (temp) == INSN
999: && GET_CODE (PATTERN (temp)) == SET
1000: && GET_CODE (temp1 = SET_DEST (PATTERN (temp))) == REG
1001: #ifdef SMALL_REGISTER_CLASSES
1002: && REGNO (temp1) >= FIRST_PSEUDO_REGISTER
1003: #endif
1004: && GET_MODE_CLASS (GET_MODE (temp1)) == MODE_INT
1005: && (GET_CODE (temp2 = SET_SRC (PATTERN (temp))) == REG
1.1.1.4 root 1006: || GET_CODE (temp2) == SUBREG
1.1 root 1007: || GET_CODE (temp2) == CONST_INT)
1.1.1.4 root 1008: /* Allow either form, but prefer the former if both apply.
1009: There is no point in using the old value of TEMP1 if
1010: it is a register, since cse will alias them. It can
1011: lose if the old value were a hard register since CSE
1012: won't replace hard registers. */
1.1 root 1013: && (((temp3 = reg_set_last (temp1, insn)) != 0
1.1.1.4 root 1014: && GET_CODE (temp3) == CONST_INT)
1.1 root 1015: /* Make the latter case look like x = x; if (...) x = 0; */
1.1.1.4 root 1016: || (temp3 = temp1,
1017: ((BRANCH_COST >= 2
1018: && temp2 == const0_rtx)
1.1.1.5 ! root 1019: #ifdef HAVE_conditional_move
! 1020: || 1
! 1021: #endif
1.1.1.4 root 1022: || BRANCH_COST >= 3)))
1.1 root 1023: /* INSN must either branch to the insn after TEMP or the insn
1024: after TEMP must branch to the same place as INSN. */
1025: && (reallabelprev == temp
1026: || ((temp4 = next_active_insn (temp)) != 0
1027: && simplejump_p (temp4)
1028: && JUMP_LABEL (temp4) == JUMP_LABEL (insn)))
1029: && (temp4 = get_condition (insn, &temp5)) != 0
1.1.1.4 root 1030: /* We must be comparing objects whose modes imply the size.
1031: We could handle BLKmode if (1) emit_store_flag could
1032: and (2) we could find the size reliably. */
1033: && GET_MODE (XEXP (temp4, 0)) != BLKmode
1034:
1035: /* If B is zero, OK; if A is zero, can only do (1) if we
1036: can reverse the condition. See if (3) applies possibly
1037: by reversing the condition. Prefer reversing to (4) when
1038: branches are very expensive. */
1039: && ((reversep = 0, temp2 == const0_rtx)
1.1 root 1040: || (temp3 == const0_rtx
1.1.1.4 root 1041: && (reversep = can_reverse_comparison_p (temp4, insn)))
1042: || (BRANCH_COST >= 2
1043: && GET_CODE (temp2) == CONST_INT
1044: && GET_CODE (temp3) == CONST_INT
1045: && ((INTVAL (temp2) & INTVAL (temp3)) == INTVAL (temp2)
1046: || ((INTVAL (temp2) & INTVAL (temp3)) == INTVAL (temp3)
1047: && (reversep = can_reverse_comparison_p (temp4,
1048: insn)))))
1.1.1.5 ! root 1049: #ifdef HAVE_conditional_move
! 1050: || 1
! 1051: #endif
1.1.1.4 root 1052: || BRANCH_COST >= 3)
1053: #ifdef HAVE_cc0
1054: /* If the previous insn sets CC0 and something else, we can't
1055: do this since we are going to delete that insn. */
1056:
1057: && ! ((temp6 = prev_nonnote_insn (insn)) != 0
1058: && GET_CODE (temp6) == INSN
1059: && (sets_cc0_p (PATTERN (temp6)) == -1
1060: || (sets_cc0_p (PATTERN (temp6)) == 1
1061: && FIND_REG_INC_NOTE (temp6, NULL_RTX))))
1062: #endif
1063: )
1.1 root 1064: {
1065: enum rtx_code code = GET_CODE (temp4);
1.1.1.4 root 1066: rtx uval, cval, var = temp1;
1.1 root 1067: int normalizep;
1068: rtx target;
1069:
1070: /* If necessary, reverse the condition. */
1.1.1.4 root 1071: if (reversep)
1072: code = reverse_condition (code), uval = temp2, cval = temp3;
1073: else
1074: uval = temp3, cval = temp2;
1.1 root 1075:
1076: /* See if we can do this with a store-flag insn. */
1077: start_sequence ();
1078:
1.1.1.4 root 1079: /* If CVAL is non-zero, normalize to -1. Otherwise,
1080: if UVAL is the constant 1, it is best to just compute
1081: the result directly. If UVAL is constant and STORE_FLAG_VALUE
1.1 root 1082: includes all of its bits, it is best to compute the flag
1.1.1.4 root 1083: value unnormalized and `and' it with UVAL. Otherwise,
1084: normalize to -1 and `and' with UVAL. */
1085: normalizep = (cval != const0_rtx ? -1
1086: : (uval == const1_rtx ? 1
1087: : (GET_CODE (uval) == CONST_INT
1088: && (INTVAL (uval) & ~STORE_FLAG_VALUE) == 0)
1089: ? 0 : -1));
1.1 root 1090:
1091: /* We will be putting the store-flag insn immediately in
1092: front of the comparison that was originally being done,
1093: so we know all the variables in TEMP4 will be valid.
1094: However, this might be in front of the assignment of
1095: A to VAR. If it is, it would clobber the store-flag
1096: we will be emitting.
1097:
1098: Therefore, emit into a temporary which will be copied to
1099: VAR immediately after TEMP. */
1100:
1101: target = emit_store_flag (gen_reg_rtx (GET_MODE (var)), code,
1102: XEXP (temp4, 0), XEXP (temp4, 1),
1103: VOIDmode,
1104: (code == LTU || code == LEU
1105: || code == GEU || code == GTU),
1106: normalizep);
1107: if (target)
1108: {
1.1.1.4 root 1109: rtx before = insn;
1.1 root 1110: rtx seq;
1111:
1.1.1.4 root 1112: /* Put the store-flag insns in front of the first insn
1113: used to compute the condition to ensure that we
1114: use the same values of them as the current
1115: comparison. However, the remainder of the insns we
1116: generate will be placed directly in front of the
1117: jump insn, in case any of the pseudos we use
1118: are modified earlier. */
1119:
1120: seq = get_insns ();
1121: end_sequence ();
1122:
1123: emit_insns_before (seq, temp5);
1124:
1125: start_sequence ();
1126:
1127: /* Both CVAL and UVAL are non-zero. */
1128: if (cval != const0_rtx && uval != const0_rtx)
1129: {
1130: rtx tem1, tem2;
1131:
1132: tem1 = expand_and (uval, target, NULL_RTX);
1133: if (GET_CODE (cval) == CONST_INT
1134: && GET_CODE (uval) == CONST_INT
1135: && (INTVAL (cval) & INTVAL (uval)) == INTVAL (cval))
1136: tem2 = cval;
1137: else
1138: {
1139: tem2 = expand_unop (GET_MODE (var), one_cmpl_optab,
1140: target, NULL_RTX, 0);
1141: tem2 = expand_and (cval, tem2,
1142: (GET_CODE (tem2) == REG
1143: ? tem2 : 0));
1144: }
1145:
1146: /* If we usually make new pseudos, do so here. This
1147: turns out to help machines that have conditional
1148: move insns. */
1149:
1150: if (flag_expensive_optimizations)
1151: target = 0;
1152:
1153: target = expand_binop (GET_MODE (var), ior_optab,
1154: tem1, tem2, target,
1155: 1, OPTAB_WIDEN);
1156: }
1157: else if (normalizep != 1)
1158: target = expand_and (uval, target,
1.1 root 1159: (GET_CODE (target) == REG
1.1.1.4 root 1160: && ! preserve_subexpressions_p ()
1161: ? target : NULL_RTX));
1162:
1163: emit_move_insn (var, target);
1164: seq = get_insns ();
1.1 root 1165: end_sequence ();
1.1.1.4 root 1166:
1.1 root 1167: #ifdef HAVE_cc0
1.1.1.4 root 1168: /* If INSN uses CC0, we must not separate it from the
1169: insn that sets cc0. */
1170:
1171: if (reg_mentioned_p (cc0_rtx, PATTERN (before)))
1172: before = prev_nonnote_insn (before);
1.1 root 1173: #endif
1.1.1.4 root 1174:
1175: emit_insns_before (seq, before);
1176:
1177: delete_insn (temp);
1178: next = NEXT_INSN (insn);
1179:
1180: delete_jump (insn);
1.1 root 1181: changed = 1;
1182: continue;
1183: }
1184: else
1185: end_sequence ();
1186: }
1187:
1188: /* If branches are expensive, convert
1189: if (foo) bar++; to bar += (foo != 0);
1190: and similarly for "bar--;"
1191:
1192: INSN is the conditional branch around the arithmetic. We set:
1193:
1194: TEMP is the arithmetic insn.
1.1.1.3 root 1195: TEMP1 is the SET doing the arithmetic.
1.1 root 1196: TEMP2 is the operand being incremented or decremented.
1197: TEMP3 to the condition being tested.
1198: TEMP4 to the earliest insn used to find the condition. */
1199:
1.1.1.5 ! root 1200: if ((BRANCH_COST >= 2
! 1201: #ifdef HAVE_incscc
! 1202: || HAVE_incscc
! 1203: #endif
! 1204: #ifdef HAVE_decscc
! 1205: || HAVE_decscc
! 1206: #endif
! 1207: )
1.1 root 1208: && ! reload_completed
1209: && this_is_condjump && ! this_is_simplejump
1210: && (temp = next_nonnote_insn (insn)) != 0
1211: && (temp1 = single_set (temp)) != 0
1212: && (temp2 = SET_DEST (temp1),
1213: GET_MODE_CLASS (GET_MODE (temp2)) == MODE_INT)
1214: && GET_CODE (SET_SRC (temp1)) == PLUS
1215: && (XEXP (SET_SRC (temp1), 1) == const1_rtx
1216: || XEXP (SET_SRC (temp1), 1) == constm1_rtx)
1217: && rtx_equal_p (temp2, XEXP (SET_SRC (temp1), 0))
1218: /* INSN must either branch to the insn after TEMP or the insn
1219: after TEMP must branch to the same place as INSN. */
1220: && (reallabelprev == temp
1221: || ((temp3 = next_active_insn (temp)) != 0
1222: && simplejump_p (temp3)
1223: && JUMP_LABEL (temp3) == JUMP_LABEL (insn)))
1224: && (temp3 = get_condition (insn, &temp4)) != 0
1.1.1.4 root 1225: /* We must be comparing objects whose modes imply the size.
1226: We could handle BLKmode if (1) emit_store_flag could
1227: and (2) we could find the size reliably. */
1228: && GET_MODE (XEXP (temp3, 0)) != BLKmode
1.1 root 1229: && can_reverse_comparison_p (temp3, insn))
1230: {
1.1.1.3 root 1231: rtx temp6, target = 0, seq, init_insn = 0, init = temp2;
1.1 root 1232: enum rtx_code code = reverse_condition (GET_CODE (temp3));
1233:
1234: start_sequence ();
1235:
1.1.1.3 root 1236: /* It must be the case that TEMP2 is not modified in the range
1237: [TEMP4, INSN). The one exception we make is if the insn
1238: before INSN sets TEMP2 to something which is also unchanged
1239: in that range. In that case, we can move the initialization
1240: into our sequence. */
1241:
1242: if ((temp5 = prev_active_insn (insn)) != 0
1243: && GET_CODE (temp5) == INSN
1244: && (temp6 = single_set (temp5)) != 0
1245: && rtx_equal_p (temp2, SET_DEST (temp6))
1246: && (CONSTANT_P (SET_SRC (temp6))
1247: || GET_CODE (SET_SRC (temp6)) == REG
1248: || GET_CODE (SET_SRC (temp6)) == SUBREG))
1249: {
1250: emit_insn (PATTERN (temp5));
1251: init_insn = temp5;
1252: init = SET_SRC (temp6);
1253: }
1254:
1255: if (CONSTANT_P (init)
1256: || ! reg_set_between_p (init, PREV_INSN (temp4), insn))
1257: target = emit_store_flag (gen_reg_rtx (GET_MODE (temp2)), code,
1258: XEXP (temp3, 0), XEXP (temp3, 1),
1259: VOIDmode,
1260: (code == LTU || code == LEU
1261: || code == GTU || code == GEU), 1);
1.1 root 1262:
1263: /* If we can do the store-flag, do the addition or
1264: subtraction. */
1265:
1266: if (target)
1267: target = expand_binop (GET_MODE (temp2),
1268: (XEXP (SET_SRC (temp1), 1) == const1_rtx
1269: ? add_optab : sub_optab),
1.1.1.5 ! root 1270: temp2, target, temp2, 0, OPTAB_WIDEN);
1.1 root 1271:
1272: if (target != 0)
1273: {
1274: /* Put the result back in temp2 in case it isn't already.
1275: Then replace the jump, possible a CC0-setting insn in
1276: front of the jump, and TEMP, with the sequence we have
1277: made. */
1278:
1279: if (target != temp2)
1280: emit_move_insn (temp2, target);
1281:
1282: seq = get_insns ();
1283: end_sequence ();
1284:
1285: emit_insns_before (seq, temp4);
1286: delete_insn (temp);
1.1.1.3 root 1287:
1288: if (init_insn)
1289: delete_insn (init_insn);
1290:
1.1 root 1291: next = NEXT_INSN (insn);
1292: #ifdef HAVE_cc0
1293: delete_insn (prev_nonnote_insn (insn));
1294: #endif
1295: delete_insn (insn);
1296: changed = 1;
1297: continue;
1298: }
1299: else
1300: end_sequence ();
1301: }
1302:
1303: /* Simplify if (...) x = 1; else {...} if (x) ...
1304: We recognize this case scanning backwards as well.
1305:
1306: TEMP is the assignment to x;
1307: TEMP1 is the label at the head of the second if. */
1308: /* ?? This should call get_condition to find the values being
1309: compared, instead of looking for a COMPARE insn when HAVE_cc0
1310: is not defined. This would allow it to work on the m88k. */
1311: /* ?? This optimization is only safe before cse is run if HAVE_cc0
1312: is not defined and the condition is tested by a separate compare
1313: insn. This is because the code below assumes that the result
1314: of the compare dies in the following branch.
1315:
1316: Not only that, but there might be other insns between the
1317: compare and branch whose results are live. Those insns need
1318: to be executed.
1319:
1320: A way to fix this is to move the insns at JUMP_LABEL (insn)
1321: to before INSN. If we are running before flow, they will
1322: be deleted if they aren't needed. But this doesn't work
1323: well after flow.
1324:
1325: This is really a special-case of jump threading, anyway. The
1326: right thing to do is to replace this and jump threading with
1327: much simpler code in cse.
1328:
1329: This code has been turned off in the non-cc0 case in the
1330: meantime. */
1331:
1332: #ifdef HAVE_cc0
1333: else if (this_is_simplejump
1334: /* Safe to skip USE and CLOBBER insns here
1335: since they will not be deleted. */
1336: && (temp = prev_active_insn (insn))
1337: && no_labels_between_p (temp, insn)
1338: && GET_CODE (temp) == INSN
1339: && GET_CODE (PATTERN (temp)) == SET
1340: && GET_CODE (SET_DEST (PATTERN (temp))) == REG
1341: && CONSTANT_P (SET_SRC (PATTERN (temp)))
1342: && (temp1 = next_active_insn (JUMP_LABEL (insn)))
1343: /* If we find that the next value tested is `x'
1344: (TEMP1 is the insn where this happens), win. */
1345: && GET_CODE (temp1) == INSN
1346: && GET_CODE (PATTERN (temp1)) == SET
1347: #ifdef HAVE_cc0
1348: /* Does temp1 `tst' the value of x? */
1349: && SET_SRC (PATTERN (temp1)) == SET_DEST (PATTERN (temp))
1350: && SET_DEST (PATTERN (temp1)) == cc0_rtx
1351: && (temp1 = next_nonnote_insn (temp1))
1352: #else
1353: /* Does temp1 compare the value of x against zero? */
1354: && GET_CODE (SET_SRC (PATTERN (temp1))) == COMPARE
1355: && XEXP (SET_SRC (PATTERN (temp1)), 1) == const0_rtx
1356: && (XEXP (SET_SRC (PATTERN (temp1)), 0)
1357: == SET_DEST (PATTERN (temp)))
1358: && GET_CODE (SET_DEST (PATTERN (temp1))) == REG
1359: && (temp1 = find_next_ref (SET_DEST (PATTERN (temp1)), temp1))
1360: #endif
1361: && condjump_p (temp1))
1362: {
1363: /* Get the if_then_else from the condjump. */
1364: rtx choice = SET_SRC (PATTERN (temp1));
1365: if (GET_CODE (choice) == IF_THEN_ELSE)
1366: {
1367: enum rtx_code code = GET_CODE (XEXP (choice, 0));
1368: rtx val = SET_SRC (PATTERN (temp));
1369: rtx cond
1370: = simplify_relational_operation (code, GET_MODE (SET_DEST (PATTERN (temp))),
1371: val, const0_rtx);
1372: rtx ultimate;
1373:
1374: if (cond == const_true_rtx)
1375: ultimate = XEXP (choice, 1);
1376: else if (cond == const0_rtx)
1377: ultimate = XEXP (choice, 2);
1378: else
1379: ultimate = 0;
1380:
1381: if (ultimate == pc_rtx)
1382: ultimate = get_label_after (temp1);
1383: else if (ultimate && GET_CODE (ultimate) != RETURN)
1384: ultimate = XEXP (ultimate, 0);
1385:
1386: if (ultimate)
1387: changed |= redirect_jump (insn, ultimate);
1388: }
1389: }
1390: #endif
1391:
1392: #if 0
1393: /* @@ This needs a bit of work before it will be right.
1394:
1395: Any type of comparison can be accepted for the first and
1396: second compare. When rewriting the first jump, we must
1397: compute the what conditions can reach label3, and use the
1398: appropriate code. We can not simply reverse/swap the code
1399: of the first jump. In some cases, the second jump must be
1400: rewritten also.
1401:
1402: For example,
1403: < == converts to > ==
1404: < != converts to == >
1405: etc.
1406:
1407: If the code is written to only accept an '==' test for the second
1408: compare, then all that needs to be done is to swap the condition
1409: of the first branch.
1410:
1411: It is questionable whether we want this optimization anyways,
1412: since if the user wrote code like this because he/she knew that
1.1.1.3 root 1413: the jump to label1 is taken most of the time, then rewriting
1.1 root 1414: this gives slower code. */
1415: /* @@ This should call get_condition to find the values being
1416: compared, instead of looking for a COMPARE insn when HAVE_cc0
1417: is not defined. This would allow it to work on the m88k. */
1418: /* @@ This optimization is only safe before cse is run if HAVE_cc0
1419: is not defined and the condition is tested by a separate compare
1420: insn. This is because the code below assumes that the result
1421: of the compare dies in the following branch. */
1422:
1423: /* Simplify test a ~= b
1424: condjump label1;
1425: test a == b
1426: condjump label2;
1427: jump label3;
1428: label1:
1429:
1430: rewriting as
1431: test a ~~= b
1432: condjump label3
1433: test a == b
1434: condjump label2
1435: label1:
1436:
1437: where ~= is an inequality, e.g. >, and ~~= is the swapped
1438: inequality, e.g. <.
1439:
1440: We recognize this case scanning backwards.
1441:
1442: TEMP is the conditional jump to `label2';
1443: TEMP1 is the test for `a == b';
1444: TEMP2 is the conditional jump to `label1';
1445: TEMP3 is the test for `a ~= b'. */
1446: else if (this_is_simplejump
1447: && (temp = prev_active_insn (insn))
1448: && no_labels_between_p (temp, insn)
1449: && condjump_p (temp)
1450: && (temp1 = prev_active_insn (temp))
1451: && no_labels_between_p (temp1, temp)
1452: && GET_CODE (temp1) == INSN
1453: && GET_CODE (PATTERN (temp1)) == SET
1454: #ifdef HAVE_cc0
1455: && sets_cc0_p (PATTERN (temp1)) == 1
1456: #else
1457: && GET_CODE (SET_SRC (PATTERN (temp1))) == COMPARE
1458: && GET_CODE (SET_DEST (PATTERN (temp1))) == REG
1459: && (temp == find_next_ref (SET_DEST (PATTERN (temp1)), temp1))
1460: #endif
1461: && (temp2 = prev_active_insn (temp1))
1462: && no_labels_between_p (temp2, temp1)
1463: && condjump_p (temp2)
1464: && JUMP_LABEL (temp2) == next_nonnote_insn (NEXT_INSN (insn))
1465: && (temp3 = prev_active_insn (temp2))
1466: && no_labels_between_p (temp3, temp2)
1467: && GET_CODE (PATTERN (temp3)) == SET
1468: && rtx_equal_p (SET_DEST (PATTERN (temp3)),
1469: SET_DEST (PATTERN (temp1)))
1470: && rtx_equal_p (SET_SRC (PATTERN (temp1)),
1471: SET_SRC (PATTERN (temp3)))
1472: && ! inequality_comparisons_p (PATTERN (temp))
1473: && inequality_comparisons_p (PATTERN (temp2)))
1474: {
1475: rtx fallthrough_label = JUMP_LABEL (temp2);
1476:
1477: ++LABEL_NUSES (fallthrough_label);
1478: if (swap_jump (temp2, JUMP_LABEL (insn)))
1479: {
1480: delete_insn (insn);
1481: changed = 1;
1482: }
1483:
1484: if (--LABEL_NUSES (fallthrough_label) == 0)
1485: delete_insn (fallthrough_label);
1486: }
1487: #endif
1488: /* Simplify if (...) {... x = 1;} if (x) ...
1489:
1490: We recognize this case backwards.
1491:
1492: TEMP is the test of `x';
1493: TEMP1 is the assignment to `x' at the end of the
1494: previous statement. */
1495: /* @@ This should call get_condition to find the values being
1496: compared, instead of looking for a COMPARE insn when HAVE_cc0
1497: is not defined. This would allow it to work on the m88k. */
1498: /* @@ This optimization is only safe before cse is run if HAVE_cc0
1499: is not defined and the condition is tested by a separate compare
1500: insn. This is because the code below assumes that the result
1501: of the compare dies in the following branch. */
1502:
1503: /* ??? This has to be turned off. The problem is that the
1504: unconditional jump might indirectly end up branching to the
1505: label between TEMP1 and TEMP. We can't detect this, in general,
1506: since it may become a jump to there after further optimizations.
1507: If that jump is done, it will be deleted, so we will retry
1508: this optimization in the next pass, thus an infinite loop.
1509:
1510: The present code prevents this by putting the jump after the
1511: label, but this is not logically correct. */
1512: #if 0
1513: else if (this_is_condjump
1514: /* Safe to skip USE and CLOBBER insns here
1515: since they will not be deleted. */
1516: && (temp = prev_active_insn (insn))
1517: && no_labels_between_p (temp, insn)
1518: && GET_CODE (temp) == INSN
1519: && GET_CODE (PATTERN (temp)) == SET
1520: #ifdef HAVE_cc0
1521: && sets_cc0_p (PATTERN (temp)) == 1
1522: && GET_CODE (SET_SRC (PATTERN (temp))) == REG
1523: #else
1524: /* Temp must be a compare insn, we can not accept a register
1525: to register move here, since it may not be simply a
1526: tst insn. */
1527: && GET_CODE (SET_SRC (PATTERN (temp))) == COMPARE
1528: && XEXP (SET_SRC (PATTERN (temp)), 1) == const0_rtx
1529: && GET_CODE (XEXP (SET_SRC (PATTERN (temp)), 0)) == REG
1530: && GET_CODE (SET_DEST (PATTERN (temp))) == REG
1531: && insn == find_next_ref (SET_DEST (PATTERN (temp)), temp)
1532: #endif
1533: /* May skip USE or CLOBBER insns here
1534: for checking for opportunity, since we
1535: take care of them later. */
1536: && (temp1 = prev_active_insn (temp))
1537: && GET_CODE (temp1) == INSN
1538: && GET_CODE (PATTERN (temp1)) == SET
1539: #ifdef HAVE_cc0
1540: && SET_SRC (PATTERN (temp)) == SET_DEST (PATTERN (temp1))
1541: #else
1542: && (XEXP (SET_SRC (PATTERN (temp)), 0)
1543: == SET_DEST (PATTERN (temp1)))
1544: #endif
1545: && CONSTANT_P (SET_SRC (PATTERN (temp1)))
1546: /* If this isn't true, cse will do the job. */
1547: && ! no_labels_between_p (temp1, temp))
1548: {
1549: /* Get the if_then_else from the condjump. */
1550: rtx choice = SET_SRC (PATTERN (insn));
1551: if (GET_CODE (choice) == IF_THEN_ELSE
1552: && (GET_CODE (XEXP (choice, 0)) == EQ
1553: || GET_CODE (XEXP (choice, 0)) == NE))
1554: {
1555: int want_nonzero = (GET_CODE (XEXP (choice, 0)) == NE);
1556: rtx last_insn;
1557: rtx ultimate;
1558: rtx p;
1559:
1560: /* Get the place that condjump will jump to
1561: if it is reached from here. */
1562: if ((SET_SRC (PATTERN (temp1)) != const0_rtx)
1563: == want_nonzero)
1564: ultimate = XEXP (choice, 1);
1565: else
1566: ultimate = XEXP (choice, 2);
1567: /* Get it as a CODE_LABEL. */
1568: if (ultimate == pc_rtx)
1569: ultimate = get_label_after (insn);
1570: else
1571: /* Get the label out of the LABEL_REF. */
1572: ultimate = XEXP (ultimate, 0);
1573:
1574: /* Insert the jump immediately before TEMP, specifically
1575: after the label that is between TEMP1 and TEMP. */
1576: last_insn = PREV_INSN (temp);
1577:
1578: /* If we would be branching to the next insn, the jump
1579: would immediately be deleted and the re-inserted in
1580: a subsequent pass over the code. So don't do anything
1581: in that case. */
1582: if (next_active_insn (last_insn)
1583: != next_active_insn (ultimate))
1584: {
1585: emit_barrier_after (last_insn);
1586: p = emit_jump_insn_after (gen_jump (ultimate),
1587: last_insn);
1588: JUMP_LABEL (p) = ultimate;
1589: ++LABEL_NUSES (ultimate);
1590: if (INSN_UID (ultimate) < max_jump_chain
1591: && INSN_CODE (p) < max_jump_chain)
1592: {
1593: jump_chain[INSN_UID (p)]
1594: = jump_chain[INSN_UID (ultimate)];
1595: jump_chain[INSN_UID (ultimate)] = p;
1596: }
1597: changed = 1;
1598: continue;
1599: }
1600: }
1601: }
1602: #endif
1603: /* Detect a conditional jump going to the same place
1604: as an immediately following unconditional jump. */
1605: else if (this_is_condjump
1606: && (temp = next_active_insn (insn)) != 0
1607: && simplejump_p (temp)
1608: && (next_active_insn (JUMP_LABEL (insn))
1609: == next_active_insn (JUMP_LABEL (temp))))
1610: {
1611: delete_jump (insn);
1612: changed = 1;
1613: continue;
1614: }
1615: /* Detect a conditional jump jumping over an unconditional jump. */
1616:
1617: else if (this_is_condjump && ! this_is_simplejump
1618: && reallabelprev != 0
1619: && GET_CODE (reallabelprev) == JUMP_INSN
1620: && prev_active_insn (reallabelprev) == insn
1621: && no_labels_between_p (insn, reallabelprev)
1622: && simplejump_p (reallabelprev))
1623: {
1624: /* When we invert the unconditional jump, we will be
1625: decrementing the usage count of its old label.
1626: Make sure that we don't delete it now because that
1627: might cause the following code to be deleted. */
1628: rtx prev_uses = prev_nonnote_insn (reallabelprev);
1629: rtx prev_label = JUMP_LABEL (insn);
1630:
1631: ++LABEL_NUSES (prev_label);
1632:
1633: if (invert_jump (insn, JUMP_LABEL (reallabelprev)))
1634: {
1635: /* It is very likely that if there are USE insns before
1636: this jump, they hold REG_DEAD notes. These REG_DEAD
1637: notes are no longer valid due to this optimization,
1638: and will cause the life-analysis that following passes
1639: (notably delayed-branch scheduling) to think that
1640: these registers are dead when they are not.
1641:
1642: To prevent this trouble, we just remove the USE insns
1643: from the insn chain. */
1644:
1645: while (prev_uses && GET_CODE (prev_uses) == INSN
1646: && GET_CODE (PATTERN (prev_uses)) == USE)
1647: {
1648: rtx useless = prev_uses;
1649: prev_uses = prev_nonnote_insn (prev_uses);
1650: delete_insn (useless);
1651: }
1652:
1653: delete_insn (reallabelprev);
1654: next = insn;
1655: changed = 1;
1656: }
1657:
1658: /* We can now safely delete the label if it is unreferenced
1659: since the delete_insn above has deleted the BARRIER. */
1660: if (--LABEL_NUSES (prev_label) == 0)
1661: delete_insn (prev_label);
1662: continue;
1663: }
1664: else
1665: {
1666: /* Detect a jump to a jump. */
1667:
1668: nlabel = follow_jumps (JUMP_LABEL (insn));
1669: if (nlabel != JUMP_LABEL (insn)
1670: && redirect_jump (insn, nlabel))
1671: {
1672: changed = 1;
1673: next = insn;
1674: }
1675:
1676: /* Look for if (foo) bar; else break; */
1677: /* The insns look like this:
1678: insn = condjump label1;
1679: ...range1 (some insns)...
1680: jump label2;
1681: label1:
1682: ...range2 (some insns)...
1683: jump somewhere unconditionally
1684: label2: */
1685: {
1686: rtx label1 = next_label (insn);
1687: rtx range1end = label1 ? prev_active_insn (label1) : 0;
1688: /* Don't do this optimization on the first round, so that
1689: jump-around-a-jump gets simplified before we ask here
1690: whether a jump is unconditional.
1691:
1692: Also don't do it when we are called after reload since
1693: it will confuse reorg. */
1694: if (! first
1695: && (reload_completed ? ! flag_delayed_branch : 1)
1696: /* Make sure INSN is something we can invert. */
1697: && condjump_p (insn)
1698: && label1 != 0
1699: && JUMP_LABEL (insn) == label1
1700: && LABEL_NUSES (label1) == 1
1701: && GET_CODE (range1end) == JUMP_INSN
1702: && simplejump_p (range1end))
1703: {
1704: rtx label2 = next_label (label1);
1705: rtx range2end = label2 ? prev_active_insn (label2) : 0;
1706: if (range1end != range2end
1707: && JUMP_LABEL (range1end) == label2
1708: && GET_CODE (range2end) == JUMP_INSN
1709: && GET_CODE (NEXT_INSN (range2end)) == BARRIER
1710: /* Invert the jump condition, so we
1711: still execute the same insns in each case. */
1712: && invert_jump (insn, label1))
1713: {
1714: rtx range1beg = next_active_insn (insn);
1715: rtx range2beg = next_active_insn (label1);
1716: rtx range1after, range2after;
1717: rtx range1before, range2before;
1718:
1.1.1.2 root 1719: /* Include in each range any line number before it. */
1720: while (PREV_INSN (range1beg)
1721: && GET_CODE (PREV_INSN (range1beg)) == NOTE
1722: && NOTE_LINE_NUMBER (PREV_INSN (range1beg)) > 0)
1723: range1beg = PREV_INSN (range1beg);
1724:
1725: while (PREV_INSN (range2beg)
1726: && GET_CODE (PREV_INSN (range2beg)) == NOTE
1727: && NOTE_LINE_NUMBER (PREV_INSN (range2beg)) > 0)
1728: range2beg = PREV_INSN (range2beg);
1729:
1.1 root 1730: /* Don't move NOTEs for blocks or loops; shift them
1731: outside the ranges, where they'll stay put. */
1.1.1.3 root 1732: range1beg = squeeze_notes (range1beg, range1end);
1733: range2beg = squeeze_notes (range2beg, range2end);
1.1 root 1734:
1735: /* Get current surrounds of the 2 ranges. */
1736: range1before = PREV_INSN (range1beg);
1737: range2before = PREV_INSN (range2beg);
1738: range1after = NEXT_INSN (range1end);
1739: range2after = NEXT_INSN (range2end);
1740:
1741: /* Splice range2 where range1 was. */
1742: NEXT_INSN (range1before) = range2beg;
1743: PREV_INSN (range2beg) = range1before;
1744: NEXT_INSN (range2end) = range1after;
1745: PREV_INSN (range1after) = range2end;
1746: /* Splice range1 where range2 was. */
1747: NEXT_INSN (range2before) = range1beg;
1748: PREV_INSN (range1beg) = range2before;
1749: NEXT_INSN (range1end) = range2after;
1750: PREV_INSN (range2after) = range1end;
1751: changed = 1;
1752: continue;
1753: }
1754: }
1755: }
1756:
1757: /* Now that the jump has been tensioned,
1758: try cross jumping: check for identical code
1759: before the jump and before its target label. */
1760:
1761: /* First, cross jumping of conditional jumps: */
1762:
1763: if (cross_jump && condjump_p (insn))
1764: {
1765: rtx newjpos, newlpos;
1766: rtx x = prev_real_insn (JUMP_LABEL (insn));
1767:
1768: /* A conditional jump may be crossjumped
1769: only if the place it jumps to follows
1770: an opposing jump that comes back here. */
1771:
1772: if (x != 0 && ! jump_back_p (x, insn))
1773: /* We have no opposing jump;
1774: cannot cross jump this insn. */
1775: x = 0;
1776:
1777: newjpos = 0;
1778: /* TARGET is nonzero if it is ok to cross jump
1779: to code before TARGET. If so, see if matches. */
1780: if (x != 0)
1781: find_cross_jump (insn, x, 2,
1782: &newjpos, &newlpos);
1783:
1784: if (newjpos != 0)
1785: {
1786: do_cross_jump (insn, newjpos, newlpos);
1787: /* Make the old conditional jump
1788: into an unconditional one. */
1789: SET_SRC (PATTERN (insn))
1790: = gen_rtx (LABEL_REF, VOIDmode, JUMP_LABEL (insn));
1791: INSN_CODE (insn) = -1;
1792: emit_barrier_after (insn);
1793: /* Add to jump_chain unless this is a new label
1794: whose UID is too large. */
1795: if (INSN_UID (JUMP_LABEL (insn)) < max_jump_chain)
1796: {
1797: jump_chain[INSN_UID (insn)]
1798: = jump_chain[INSN_UID (JUMP_LABEL (insn))];
1799: jump_chain[INSN_UID (JUMP_LABEL (insn))] = insn;
1800: }
1801: changed = 1;
1802: next = insn;
1803: }
1804: }
1805:
1806: /* Cross jumping of unconditional jumps:
1807: a few differences. */
1808:
1809: if (cross_jump && simplejump_p (insn))
1810: {
1811: rtx newjpos, newlpos;
1812: rtx target;
1813:
1814: newjpos = 0;
1815:
1816: /* TARGET is nonzero if it is ok to cross jump
1817: to code before TARGET. If so, see if matches. */
1818: find_cross_jump (insn, JUMP_LABEL (insn), 1,
1819: &newjpos, &newlpos);
1820:
1821: /* If cannot cross jump to code before the label,
1822: see if we can cross jump to another jump to
1823: the same label. */
1824: /* Try each other jump to this label. */
1825: if (INSN_UID (JUMP_LABEL (insn)) < max_uid)
1826: for (target = jump_chain[INSN_UID (JUMP_LABEL (insn))];
1827: target != 0 && newjpos == 0;
1828: target = jump_chain[INSN_UID (target)])
1829: if (target != insn
1830: && JUMP_LABEL (target) == JUMP_LABEL (insn)
1831: /* Ignore TARGET if it's deleted. */
1832: && ! INSN_DELETED_P (target))
1833: find_cross_jump (insn, target, 2,
1834: &newjpos, &newlpos);
1835:
1836: if (newjpos != 0)
1837: {
1838: do_cross_jump (insn, newjpos, newlpos);
1839: changed = 1;
1840: next = insn;
1841: }
1842: }
1843:
1844: /* This code was dead in the previous jump.c! */
1845: if (cross_jump && GET_CODE (PATTERN (insn)) == RETURN)
1846: {
1847: /* Return insns all "jump to the same place"
1848: so we can cross-jump between any two of them. */
1849:
1850: rtx newjpos, newlpos, target;
1851:
1852: newjpos = 0;
1853:
1854: /* If cannot cross jump to code before the label,
1855: see if we can cross jump to another jump to
1856: the same label. */
1857: /* Try each other jump to this label. */
1858: for (target = jump_chain[0];
1859: target != 0 && newjpos == 0;
1860: target = jump_chain[INSN_UID (target)])
1861: if (target != insn
1862: && ! INSN_DELETED_P (target)
1863: && GET_CODE (PATTERN (target)) == RETURN)
1864: find_cross_jump (insn, target, 2,
1865: &newjpos, &newlpos);
1866:
1867: if (newjpos != 0)
1868: {
1869: do_cross_jump (insn, newjpos, newlpos);
1870: changed = 1;
1871: next = insn;
1872: }
1873: }
1874: }
1875: }
1876:
1877: first = 0;
1878: }
1879:
1880: /* Delete extraneous line number notes.
1881: Note that two consecutive notes for different lines are not really
1882: extraneous. There should be some indication where that line belonged,
1883: even if it became empty. */
1884:
1885: {
1886: rtx last_note = 0;
1887:
1888: for (insn = f; insn; insn = NEXT_INSN (insn))
1889: if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) >= 0)
1890: {
1891: /* Delete this note if it is identical to previous note. */
1892: if (last_note
1893: && NOTE_SOURCE_FILE (insn) == NOTE_SOURCE_FILE (last_note)
1894: && NOTE_LINE_NUMBER (insn) == NOTE_LINE_NUMBER (last_note))
1895: {
1896: delete_insn (insn);
1897: continue;
1898: }
1899:
1900: last_note = insn;
1901: }
1902: }
1903:
1904: /* See if there is still a NOTE_INSN_FUNCTION_END in this function.
1905: If so, delete it, and record that this function can drop off the end. */
1906:
1907: insn = last_insn;
1908: {
1909: int n_labels = 1;
1910: while (insn
1911: /* One label can follow the end-note: the return label. */
1912: && ((GET_CODE (insn) == CODE_LABEL && n_labels-- > 0)
1913: /* Ordinary insns can follow it if returning a structure. */
1914: || GET_CODE (insn) == INSN
1915: /* If machine uses explicit RETURN insns, no epilogue,
1916: then one of them follows the note. */
1917: || (GET_CODE (insn) == JUMP_INSN
1918: && GET_CODE (PATTERN (insn)) == RETURN)
1919: /* Other kinds of notes can follow also. */
1920: || (GET_CODE (insn) == NOTE
1921: && NOTE_LINE_NUMBER (insn) != NOTE_INSN_FUNCTION_END)))
1922: insn = PREV_INSN (insn);
1923: }
1924:
1925: /* Report if control can fall through at the end of the function. */
1926: if (insn && GET_CODE (insn) == NOTE
1927: && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_END)
1928: {
1929: can_reach_end = 1;
1930: delete_insn (insn);
1931: }
1932:
1933: /* Show JUMP_CHAIN no longer valid. */
1934: jump_chain = 0;
1935: }
1936:
1937: /* LOOP_START is a NOTE_INSN_LOOP_BEG note that is followed by an unconditional
1938: jump. Assume that this unconditional jump is to the exit test code. If
1939: the code is sufficiently simple, make a copy of it before INSN,
1940: followed by a jump to the exit of the loop. Then delete the unconditional
1941: jump after INSN.
1942:
1943: Note that it is possible we can get confused here if the jump immediately
1944: after the loop start branches outside the loop but within an outer loop.
1945: If we are near the exit of that loop, we will copy its exit test. This
1946: will not generate incorrect code, but could suppress some optimizations.
1947: However, such cases are degenerate loops anyway.
1948:
1949: Return 1 if we made the change, else 0.
1950:
1951: This is only safe immediately after a regscan pass because it uses the
1952: values of regno_first_uid and regno_last_uid. */
1953:
1954: static int
1955: duplicate_loop_exit_test (loop_start)
1956: rtx loop_start;
1957: {
1958: rtx insn, set, p;
1959: rtx copy, link;
1960: int num_insns = 0;
1961: rtx exitcode = NEXT_INSN (JUMP_LABEL (next_nonnote_insn (loop_start)));
1962: rtx lastexit;
1963: int max_reg = max_reg_num ();
1964: rtx *reg_map = 0;
1965:
1966: /* Scan the exit code. We do not perform this optimization if any insn:
1967:
1968: is a CALL_INSN
1969: is a CODE_LABEL
1970: has a REG_RETVAL or REG_LIBCALL note (hard to adjust)
1971: is a NOTE_INSN_LOOP_BEG because this means we have a nested loop
1972: is a NOTE_INSN_BLOCK_{BEG,END} because duplicating these notes
1973: are not valid
1974:
1975: Also, don't do this if the exit code is more than 20 insns. */
1976:
1977: for (insn = exitcode;
1978: insn
1979: && ! (GET_CODE (insn) == NOTE
1980: && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END);
1981: insn = NEXT_INSN (insn))
1982: {
1983: switch (GET_CODE (insn))
1984: {
1985: case CODE_LABEL:
1986: case CALL_INSN:
1987: return 0;
1988: case NOTE:
1989: if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
1990: || NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG
1991: || NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END)
1992: return 0;
1993: break;
1994: case JUMP_INSN:
1995: case INSN:
1996: if (++num_insns > 20
1.1.1.4 root 1997: || find_reg_note (insn, REG_RETVAL, NULL_RTX)
1998: || find_reg_note (insn, REG_LIBCALL, NULL_RTX))
1.1 root 1999: return 0;
2000: break;
2001: }
2002: }
2003:
2004: /* Unless INSN is zero, we can do the optimization. */
2005: if (insn == 0)
2006: return 0;
2007:
2008: lastexit = insn;
2009:
2010: /* See if any insn sets a register only used in the loop exit code and
2011: not a user variable. If so, replace it with a new register. */
2012: for (insn = exitcode; insn != lastexit; insn = NEXT_INSN (insn))
2013: if (GET_CODE (insn) == INSN
2014: && (set = single_set (insn)) != 0
2015: && GET_CODE (SET_DEST (set)) == REG
2016: && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
2017: && regno_first_uid[REGNO (SET_DEST (set))] == INSN_UID (insn))
2018: {
2019: for (p = NEXT_INSN (insn); p != lastexit; p = NEXT_INSN (p))
2020: if (regno_last_uid[REGNO (SET_DEST (set))] == INSN_UID (p))
2021: break;
2022:
2023: if (p != lastexit)
2024: {
2025: /* We can do the replacement. Allocate reg_map if this is the
2026: first replacement we found. */
2027: if (reg_map == 0)
2028: {
2029: reg_map = (rtx *) alloca (max_reg * sizeof (rtx));
2030: bzero (reg_map, max_reg * sizeof (rtx));
2031: }
2032:
2033: REG_LOOP_TEST_P (SET_DEST (set)) = 1;
2034:
2035: reg_map[REGNO (SET_DEST (set))]
2036: = gen_reg_rtx (GET_MODE (SET_DEST (set)));
2037: }
2038: }
2039:
2040: /* Now copy each insn. */
2041: for (insn = exitcode; insn != lastexit; insn = NEXT_INSN (insn))
2042: switch (GET_CODE (insn))
2043: {
2044: case BARRIER:
2045: copy = emit_barrier_before (loop_start);
2046: break;
2047: case NOTE:
2048: /* Only copy line-number notes. */
2049: if (NOTE_LINE_NUMBER (insn) >= 0)
2050: {
2051: copy = emit_note_before (NOTE_LINE_NUMBER (insn), loop_start);
2052: NOTE_SOURCE_FILE (copy) = NOTE_SOURCE_FILE (insn);
2053: }
2054: break;
2055:
2056: case INSN:
2057: copy = emit_insn_before (copy_rtx (PATTERN (insn)), loop_start);
2058: if (reg_map)
2059: replace_regs (PATTERN (copy), reg_map, max_reg, 1);
2060:
2061: mark_jump_label (PATTERN (copy), copy, 0);
2062:
2063: /* Copy all REG_NOTES except REG_LABEL since mark_jump_label will
2064: make them. */
2065: for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2066: if (REG_NOTE_KIND (link) != REG_LABEL)
2067: REG_NOTES (copy)
2068: = copy_rtx (gen_rtx (EXPR_LIST, REG_NOTE_KIND (link),
2069: XEXP (link, 0), REG_NOTES (copy)));
2070: if (reg_map && REG_NOTES (copy))
2071: replace_regs (REG_NOTES (copy), reg_map, max_reg, 1);
2072: break;
2073:
2074: case JUMP_INSN:
2075: copy = emit_jump_insn_before (copy_rtx (PATTERN (insn)), loop_start);
2076: if (reg_map)
2077: replace_regs (PATTERN (copy), reg_map, max_reg, 1);
2078: mark_jump_label (PATTERN (copy), copy, 0);
2079: if (REG_NOTES (insn))
2080: {
2081: REG_NOTES (copy) = copy_rtx (REG_NOTES (insn));
2082: if (reg_map)
2083: replace_regs (REG_NOTES (copy), reg_map, max_reg, 1);
2084: }
2085:
2086: /* If this is a simple jump, add it to the jump chain. */
2087:
2088: if (INSN_UID (copy) < max_jump_chain && JUMP_LABEL (copy)
2089: && simplejump_p (copy))
2090: {
2091: jump_chain[INSN_UID (copy)]
2092: = jump_chain[INSN_UID (JUMP_LABEL (copy))];
2093: jump_chain[INSN_UID (JUMP_LABEL (copy))] = copy;
2094: }
2095: break;
2096:
2097: default:
2098: abort ();
2099: }
2100:
2101: /* Now clean up by emitting a jump to the end label and deleting the jump
2102: at the start of the loop. */
2103: if (GET_CODE (copy) != BARRIER)
2104: {
2105: copy = emit_jump_insn_before (gen_jump (get_label_after (insn)),
2106: loop_start);
2107: mark_jump_label (PATTERN (copy), copy, 0);
2108: if (INSN_UID (copy) < max_jump_chain
2109: && INSN_UID (JUMP_LABEL (copy)) < max_jump_chain)
2110: {
2111: jump_chain[INSN_UID (copy)]
2112: = jump_chain[INSN_UID (JUMP_LABEL (copy))];
2113: jump_chain[INSN_UID (JUMP_LABEL (copy))] = copy;
2114: }
2115: emit_barrier_before (loop_start);
2116: }
2117:
2118: delete_insn (next_nonnote_insn (loop_start));
2119:
2120: /* Mark the exit code as the virtual top of the converted loop. */
2121: emit_note_before (NOTE_INSN_LOOP_VTOP, exitcode);
2122:
2123: return 1;
2124: }
2125:
2126: /* Move all block-beg, block-end, loop-beg, loop-cont, loop-vtop, and
1.1.1.3 root 2127: loop-end notes between START and END out before START. Assume that
2128: END is not such a note. START may be such a note. Returns the value
2129: of the new starting insn, which may be different if the original start
2130: was such a note. */
1.1 root 2131:
1.1.1.3 root 2132: rtx
1.1 root 2133: squeeze_notes (start, end)
2134: rtx start, end;
2135: {
2136: rtx insn;
2137: rtx next;
2138:
2139: for (insn = start; insn != end; insn = next)
2140: {
2141: next = NEXT_INSN (insn);
2142: if (GET_CODE (insn) == NOTE
2143: && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END
2144: || NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG
2145: || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
2146: || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
2147: || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_CONT
2148: || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_VTOP))
2149: {
1.1.1.3 root 2150: if (insn == start)
2151: start = next;
2152: else
2153: {
2154: rtx prev = PREV_INSN (insn);
2155: PREV_INSN (insn) = PREV_INSN (start);
2156: NEXT_INSN (insn) = start;
2157: NEXT_INSN (PREV_INSN (insn)) = insn;
2158: PREV_INSN (NEXT_INSN (insn)) = insn;
2159: NEXT_INSN (prev) = next;
2160: PREV_INSN (next) = prev;
2161: }
1.1 root 2162: }
2163: }
1.1.1.3 root 2164:
2165: return start;
1.1 root 2166: }
2167:
2168: /* Compare the instructions before insn E1 with those before E2
2169: to find an opportunity for cross jumping.
2170: (This means detecting identical sequences of insns followed by
2171: jumps to the same place, or followed by a label and a jump
2172: to that label, and replacing one with a jump to the other.)
2173:
2174: Assume E1 is a jump that jumps to label E2
2175: (that is not always true but it might as well be).
2176: Find the longest possible equivalent sequences
2177: and store the first insns of those sequences into *F1 and *F2.
2178: Store zero there if no equivalent preceding instructions are found.
2179:
2180: We give up if we find a label in stream 1.
2181: Actually we could transfer that label into stream 2. */
2182:
2183: static void
2184: find_cross_jump (e1, e2, minimum, f1, f2)
2185: rtx e1, e2;
2186: int minimum;
2187: rtx *f1, *f2;
2188: {
2189: register rtx i1 = e1, i2 = e2;
2190: register rtx p1, p2;
2191: int lose = 0;
2192:
2193: rtx last1 = 0, last2 = 0;
2194: rtx afterlast1 = 0, afterlast2 = 0;
2195: rtx prev1;
2196:
2197: *f1 = 0;
2198: *f2 = 0;
2199:
2200: while (1)
2201: {
2202: i1 = prev_nonnote_insn (i1);
2203:
2204: i2 = PREV_INSN (i2);
2205: while (i2 && (GET_CODE (i2) == NOTE || GET_CODE (i2) == CODE_LABEL))
2206: i2 = PREV_INSN (i2);
2207:
2208: if (i1 == 0)
2209: break;
2210:
2211: /* Don't allow the range of insns preceding E1 or E2
2212: to include the other (E2 or E1). */
2213: if (i2 == e1 || i1 == e2)
2214: break;
2215:
2216: /* If we will get to this code by jumping, those jumps will be
2217: tensioned to go directly to the new label (before I2),
2218: so this cross-jumping won't cost extra. So reduce the minimum. */
2219: if (GET_CODE (i1) == CODE_LABEL)
2220: {
2221: --minimum;
2222: break;
2223: }
2224:
2225: if (i2 == 0 || GET_CODE (i1) != GET_CODE (i2))
2226: break;
2227:
2228: p1 = PATTERN (i1);
2229: p2 = PATTERN (i2);
2230:
2231: #ifdef STACK_REGS
2232: /* If cross_jump_death_matters is not 0, the insn's mode
2233: indicates whether or not the insn contains any stack-like
2234: regs. */
2235:
2236: if (cross_jump_death_matters && GET_MODE (i1) == QImode)
2237: {
2238: /* If register stack conversion has already been done, then
2239: death notes must also be compared before it is certain that
2240: the two instruction streams match. */
2241:
2242: rtx note;
2243: HARD_REG_SET i1_regset, i2_regset;
2244:
2245: CLEAR_HARD_REG_SET (i1_regset);
2246: CLEAR_HARD_REG_SET (i2_regset);
2247:
2248: for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
2249: if (REG_NOTE_KIND (note) == REG_DEAD
2250: && STACK_REG_P (XEXP (note, 0)))
2251: SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
2252:
2253: for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
2254: if (REG_NOTE_KIND (note) == REG_DEAD
2255: && STACK_REG_P (XEXP (note, 0)))
2256: SET_HARD_REG_BIT (i2_regset, REGNO (XEXP (note, 0)));
2257:
2258: GO_IF_HARD_REG_EQUAL (i1_regset, i2_regset, done);
2259:
2260: lose = 1;
2261:
2262: done:
2263: ;
2264: }
2265: #endif
2266:
2267: if (lose || GET_CODE (p1) != GET_CODE (p2)
2268: || ! rtx_renumbered_equal_p (p1, p2))
2269: {
2270: /* The following code helps take care of G++ cleanups. */
2271: rtx equiv1;
2272: rtx equiv2;
2273:
2274: if (!lose && GET_CODE (p1) == GET_CODE (p2)
1.1.1.4 root 2275: && ((equiv1 = find_reg_note (i1, REG_EQUAL, NULL_RTX)) != 0
2276: || (equiv1 = find_reg_note (i1, REG_EQUIV, NULL_RTX)) != 0)
2277: && ((equiv2 = find_reg_note (i2, REG_EQUAL, NULL_RTX)) != 0
2278: || (equiv2 = find_reg_note (i2, REG_EQUIV, NULL_RTX)) != 0)
1.1 root 2279: /* If the equivalences are not to a constant, they may
2280: reference pseudos that no longer exist, so we can't
2281: use them. */
2282: && CONSTANT_P (XEXP (equiv1, 0))
2283: && rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
2284: {
2285: rtx s1 = single_set (i1);
2286: rtx s2 = single_set (i2);
2287: if (s1 != 0 && s2 != 0
2288: && rtx_renumbered_equal_p (SET_DEST (s1), SET_DEST (s2)))
2289: {
2290: validate_change (i1, &SET_SRC (s1), XEXP (equiv1, 0), 1);
2291: validate_change (i2, &SET_SRC (s2), XEXP (equiv2, 0), 1);
2292: if (! rtx_renumbered_equal_p (p1, p2))
2293: cancel_changes (0);
2294: else if (apply_change_group ())
2295: goto win;
2296: }
2297: }
2298:
2299: /* Insns fail to match; cross jumping is limited to the following
2300: insns. */
2301:
2302: #ifdef HAVE_cc0
2303: /* Don't allow the insn after a compare to be shared by
2304: cross-jumping unless the compare is also shared.
2305: Here, if either of these non-matching insns is a compare,
2306: exclude the following insn from possible cross-jumping. */
2307: if (sets_cc0_p (p1) || sets_cc0_p (p2))
2308: last1 = afterlast1, last2 = afterlast2, ++minimum;
2309: #endif
2310:
2311: /* If cross-jumping here will feed a jump-around-jump
2312: optimization, this jump won't cost extra, so reduce
2313: the minimum. */
2314: if (GET_CODE (i1) == JUMP_INSN
2315: && JUMP_LABEL (i1)
2316: && prev_real_insn (JUMP_LABEL (i1)) == e1)
2317: --minimum;
2318: break;
2319: }
2320:
2321: win:
2322: if (GET_CODE (p1) != USE && GET_CODE (p1) != CLOBBER)
2323: {
2324: /* Ok, this insn is potentially includable in a cross-jump here. */
2325: afterlast1 = last1, afterlast2 = last2;
2326: last1 = i1, last2 = i2, --minimum;
2327: }
2328: }
2329:
2330: /* We have to be careful that we do not cross-jump into the middle of
2331: USE-CALL_INSN-CLOBBER sequence. This sequence is used instead of
2332: putting the USE and CLOBBERs inside the CALL_INSN. The delay slot
2333: scheduler needs to know what registers are used and modified by the
2334: CALL_INSN and needs the adjacent USE and CLOBBERs to do so.
2335:
2336: ??? At some point we should probably change this so that these are
2337: part of the CALL_INSN. The way we are doing it now is a kludge that
2338: is now causing trouble. */
2339:
2340: if (last1 != 0 && GET_CODE (last1) == CALL_INSN
2341: && (prev1 = prev_nonnote_insn (last1))
2342: && GET_CODE (prev1) == INSN
2343: && GET_CODE (PATTERN (prev1)) == USE)
2344: {
2345: /* Remove this CALL_INSN from the range we can cross-jump. */
2346: last1 = next_real_insn (last1);
2347: last2 = next_real_insn (last2);
2348:
2349: minimum++;
2350: }
2351:
2352: /* Skip past CLOBBERS since they may be right after a CALL_INSN. It
2353: isn't worth checking for the CALL_INSN. */
2354: while (last1 != 0 && GET_CODE (PATTERN (last1)) == CLOBBER)
2355: last1 = next_real_insn (last1), last2 = next_real_insn (last2);
2356:
2357: if (minimum <= 0 && last1 != 0 && last1 != e1)
2358: *f1 = last1, *f2 = last2;
2359: }
2360:
2361: static void
2362: do_cross_jump (insn, newjpos, newlpos)
2363: rtx insn, newjpos, newlpos;
2364: {
2365: /* Find an existing label at this point
2366: or make a new one if there is none. */
2367: register rtx label = get_label_before (newlpos);
2368:
2369: /* Make the same jump insn jump to the new point. */
2370: if (GET_CODE (PATTERN (insn)) == RETURN)
2371: {
2372: /* Remove from jump chain of returns. */
2373: delete_from_jump_chain (insn);
2374: /* Change the insn. */
2375: PATTERN (insn) = gen_jump (label);
2376: INSN_CODE (insn) = -1;
2377: JUMP_LABEL (insn) = label;
2378: LABEL_NUSES (label)++;
2379: /* Add to new the jump chain. */
2380: if (INSN_UID (label) < max_jump_chain
2381: && INSN_UID (insn) < max_jump_chain)
2382: {
2383: jump_chain[INSN_UID (insn)] = jump_chain[INSN_UID (label)];
2384: jump_chain[INSN_UID (label)] = insn;
2385: }
2386: }
2387: else
2388: redirect_jump (insn, label);
2389:
2390: /* Delete the matching insns before the jump. Also, remove any REG_EQUAL
2391: or REG_EQUIV note in the NEWLPOS stream that isn't also present in
2392: the NEWJPOS stream. */
2393:
2394: while (newjpos != insn)
2395: {
2396: rtx lnote;
2397:
2398: for (lnote = REG_NOTES (newlpos); lnote; lnote = XEXP (lnote, 1))
2399: if ((REG_NOTE_KIND (lnote) == REG_EQUAL
2400: || REG_NOTE_KIND (lnote) == REG_EQUIV)
2401: && ! find_reg_note (newjpos, REG_EQUAL, XEXP (lnote, 0))
2402: && ! find_reg_note (newjpos, REG_EQUIV, XEXP (lnote, 0)))
2403: remove_note (newlpos, lnote);
2404:
2405: delete_insn (newjpos);
2406: newjpos = next_real_insn (newjpos);
2407: newlpos = next_real_insn (newlpos);
2408: }
2409: }
2410:
2411: /* Return the label before INSN, or put a new label there. */
2412:
2413: rtx
2414: get_label_before (insn)
2415: rtx insn;
2416: {
2417: rtx label;
2418:
2419: /* Find an existing label at this point
2420: or make a new one if there is none. */
2421: label = prev_nonnote_insn (insn);
2422:
2423: if (label == 0 || GET_CODE (label) != CODE_LABEL)
2424: {
2425: rtx prev = PREV_INSN (insn);
2426:
1.1.1.3 root 2427: /* Don't put a label between a CALL_INSN and USE insns that precede
1.1 root 2428: it. */
2429:
2430: if (GET_CODE (insn) == CALL_INSN
2431: || (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == SEQUENCE
2432: && GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) == CALL_INSN))
2433: while (GET_CODE (prev) == INSN && GET_CODE (PATTERN (prev)) == USE)
2434: prev = PREV_INSN (prev);
2435:
2436: label = gen_label_rtx ();
2437: emit_label_after (label, prev);
2438: LABEL_NUSES (label) = 0;
2439: }
2440: return label;
2441: }
2442:
2443: /* Return the label after INSN, or put a new label there. */
2444:
2445: rtx
2446: get_label_after (insn)
2447: rtx insn;
2448: {
2449: rtx label;
2450:
2451: /* Find an existing label at this point
2452: or make a new one if there is none. */
2453: label = next_nonnote_insn (insn);
2454:
2455: if (label == 0 || GET_CODE (label) != CODE_LABEL)
2456: {
2457: /* Don't put a label between a CALL_INSN and CLOBBER insns
2458: following it. */
2459:
2460: if (GET_CODE (insn) == CALL_INSN
2461: || (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == SEQUENCE
2462: && GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) == CALL_INSN))
2463: while (GET_CODE (NEXT_INSN (insn)) == INSN
2464: && GET_CODE (PATTERN (NEXT_INSN (insn))) == CLOBBER)
2465: insn = NEXT_INSN (insn);
2466:
2467: label = gen_label_rtx ();
2468: emit_label_after (label, insn);
2469: LABEL_NUSES (label) = 0;
2470: }
2471: return label;
2472: }
2473:
2474: /* Return 1 if INSN is a jump that jumps to right after TARGET
2475: only on the condition that TARGET itself would drop through.
2476: Assumes that TARGET is a conditional jump. */
2477:
2478: static int
2479: jump_back_p (insn, target)
2480: rtx insn, target;
2481: {
2482: rtx cinsn, ctarget;
2483: enum rtx_code codei, codet;
2484:
2485: if (simplejump_p (insn) || ! condjump_p (insn)
2486: || simplejump_p (target)
2487: || target != prev_real_insn (JUMP_LABEL (insn)))
2488: return 0;
2489:
2490: cinsn = XEXP (SET_SRC (PATTERN (insn)), 0);
2491: ctarget = XEXP (SET_SRC (PATTERN (target)), 0);
2492:
2493: codei = GET_CODE (cinsn);
2494: codet = GET_CODE (ctarget);
2495:
2496: if (XEXP (SET_SRC (PATTERN (insn)), 1) == pc_rtx)
2497: {
2498: if (! can_reverse_comparison_p (cinsn, insn))
2499: return 0;
2500: codei = reverse_condition (codei);
2501: }
2502:
2503: if (XEXP (SET_SRC (PATTERN (target)), 2) == pc_rtx)
2504: {
2505: if (! can_reverse_comparison_p (ctarget, target))
2506: return 0;
2507: codet = reverse_condition (codet);
2508: }
2509:
2510: return (codei == codet
2511: && rtx_renumbered_equal_p (XEXP (cinsn, 0), XEXP (ctarget, 0))
2512: && rtx_renumbered_equal_p (XEXP (cinsn, 1), XEXP (ctarget, 1)));
2513: }
2514:
2515: /* Given a comparison, COMPARISON, inside a conditional jump insn, INSN,
2516: return non-zero if it is safe to reverse this comparison. It is if our
2517: floating-point is not IEEE, if this is an NE or EQ comparison, or if
2518: this is known to be an integer comparison. */
2519:
2520: int
2521: can_reverse_comparison_p (comparison, insn)
2522: rtx comparison;
2523: rtx insn;
2524: {
2525: rtx arg0;
2526:
2527: /* If this is not actually a comparison, we can't reverse it. */
2528: if (GET_RTX_CLASS (GET_CODE (comparison)) != '<')
2529: return 0;
2530:
2531: if (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
2532: /* If this is an NE comparison, it is safe to reverse it to an EQ
2533: comparison and vice versa, even for floating point. If no operands
2534: are NaNs, the reversal is valid. If some operand is a NaN, EQ is
2535: always false and NE is always true, so the reversal is also valid. */
2536: || GET_CODE (comparison) == NE
2537: || GET_CODE (comparison) == EQ)
2538: return 1;
2539:
2540: arg0 = XEXP (comparison, 0);
2541:
2542: /* Make sure ARG0 is one of the actual objects being compared. If we
2543: can't do this, we can't be sure the comparison can be reversed.
2544:
2545: Handle cc0 and a MODE_CC register. */
2546: if ((GET_CODE (arg0) == REG && GET_MODE_CLASS (GET_MODE (arg0)) == MODE_CC)
2547: #ifdef HAVE_cc0
2548: || arg0 == cc0_rtx
2549: #endif
2550: )
2551: {
2552: rtx prev = prev_nonnote_insn (insn);
2553: rtx set = single_set (prev);
2554:
2555: if (set == 0 || SET_DEST (set) != arg0)
2556: return 0;
2557:
2558: arg0 = SET_SRC (set);
2559:
2560: if (GET_CODE (arg0) == COMPARE)
2561: arg0 = XEXP (arg0, 0);
2562: }
2563:
2564: /* We can reverse this if ARG0 is a CONST_INT or if its mode is
2565: not VOIDmode and neither a MODE_CC nor MODE_FLOAT type. */
2566: return (GET_CODE (arg0) == CONST_INT
2567: || (GET_MODE (arg0) != VOIDmode
2568: && GET_MODE_CLASS (GET_MODE (arg0)) != MODE_CC
2569: && GET_MODE_CLASS (GET_MODE (arg0)) != MODE_FLOAT));
2570: }
2571:
2572: /* Given an rtx-code for a comparison, return the code
2573: for the negated comparison.
2574: WATCH OUT! reverse_condition is not safe to use on a jump
2575: that might be acting on the results of an IEEE floating point comparison,
2576: because of the special treatment of non-signaling nans in comparisons.
2577: Use can_reverse_comparison_p to be sure. */
2578:
2579: enum rtx_code
2580: reverse_condition (code)
2581: enum rtx_code code;
2582: {
2583: switch (code)
2584: {
2585: case EQ:
2586: return NE;
2587:
2588: case NE:
2589: return EQ;
2590:
2591: case GT:
2592: return LE;
2593:
2594: case GE:
2595: return LT;
2596:
2597: case LT:
2598: return GE;
2599:
2600: case LE:
2601: return GT;
2602:
2603: case GTU:
2604: return LEU;
2605:
2606: case GEU:
2607: return LTU;
2608:
2609: case LTU:
2610: return GEU;
2611:
2612: case LEU:
2613: return GTU;
2614:
2615: default:
2616: abort ();
2617: return UNKNOWN;
2618: }
2619: }
2620:
2621: /* Similar, but return the code when two operands of a comparison are swapped.
2622: This IS safe for IEEE floating-point. */
2623:
2624: enum rtx_code
2625: swap_condition (code)
2626: enum rtx_code code;
2627: {
2628: switch (code)
2629: {
2630: case EQ:
2631: case NE:
2632: return code;
2633:
2634: case GT:
2635: return LT;
2636:
2637: case GE:
2638: return LE;
2639:
2640: case LT:
2641: return GT;
2642:
2643: case LE:
2644: return GE;
2645:
2646: case GTU:
2647: return LTU;
2648:
2649: case GEU:
2650: return LEU;
2651:
2652: case LTU:
2653: return GTU;
2654:
2655: case LEU:
2656: return GEU;
2657:
2658: default:
2659: abort ();
2660: return UNKNOWN;
2661: }
2662: }
2663:
2664: /* Given a comparison CODE, return the corresponding unsigned comparison.
2665: If CODE is an equality comparison or already an unsigned comparison,
2666: CODE is returned. */
2667:
2668: enum rtx_code
2669: unsigned_condition (code)
2670: enum rtx_code code;
2671: {
2672: switch (code)
2673: {
2674: case EQ:
2675: case NE:
2676: case GTU:
2677: case GEU:
2678: case LTU:
2679: case LEU:
2680: return code;
2681:
2682: case GT:
2683: return GTU;
2684:
2685: case GE:
2686: return GEU;
2687:
2688: case LT:
2689: return LTU;
2690:
2691: case LE:
2692: return LEU;
2693:
2694: default:
2695: abort ();
2696: }
2697: }
2698:
2699: /* Similarly, return the signed version of a comparison. */
2700:
2701: enum rtx_code
2702: signed_condition (code)
2703: enum rtx_code code;
2704: {
2705: switch (code)
2706: {
2707: case EQ:
2708: case NE:
2709: case GT:
2710: case GE:
2711: case LT:
2712: case LE:
2713: return code;
2714:
2715: case GTU:
2716: return GT;
2717:
2718: case GEU:
2719: return GE;
2720:
2721: case LTU:
2722: return LT;
2723:
2724: case LEU:
2725: return LE;
2726:
2727: default:
2728: abort ();
2729: }
2730: }
2731:
2732: /* Return non-zero if CODE1 is more strict than CODE2, i.e., if the
2733: truth of CODE1 implies the truth of CODE2. */
2734:
2735: int
2736: comparison_dominates_p (code1, code2)
2737: enum rtx_code code1, code2;
2738: {
2739: if (code1 == code2)
2740: return 1;
2741:
2742: switch (code1)
2743: {
2744: case EQ:
2745: if (code2 == LE || code2 == LEU || code2 == GE || code2 == GEU)
2746: return 1;
2747: break;
2748:
2749: case LT:
2750: if (code2 == LE)
2751: return 1;
2752: break;
2753:
2754: case GT:
2755: if (code2 == GE)
2756: return 1;
2757: break;
2758:
2759: case LTU:
2760: if (code2 == LEU)
2761: return 1;
2762: break;
2763:
2764: case GTU:
2765: if (code2 == GEU)
2766: return 1;
2767: break;
2768: }
2769:
2770: return 0;
2771: }
2772:
2773: /* Return 1 if INSN is an unconditional jump and nothing else. */
2774:
2775: int
2776: simplejump_p (insn)
2777: rtx insn;
2778: {
2779: return (GET_CODE (insn) == JUMP_INSN
2780: && GET_CODE (PATTERN (insn)) == SET
2781: && GET_CODE (SET_DEST (PATTERN (insn))) == PC
2782: && GET_CODE (SET_SRC (PATTERN (insn))) == LABEL_REF);
2783: }
2784:
2785: /* Return nonzero if INSN is a (possibly) conditional jump
2786: and nothing more. */
2787:
2788: int
2789: condjump_p (insn)
2790: rtx insn;
2791: {
2792: register rtx x = PATTERN (insn);
2793: if (GET_CODE (x) != SET)
2794: return 0;
2795: if (GET_CODE (SET_DEST (x)) != PC)
2796: return 0;
2797: if (GET_CODE (SET_SRC (x)) == LABEL_REF)
2798: return 1;
2799: if (GET_CODE (SET_SRC (x)) != IF_THEN_ELSE)
2800: return 0;
2801: if (XEXP (SET_SRC (x), 2) == pc_rtx
2802: && (GET_CODE (XEXP (SET_SRC (x), 1)) == LABEL_REF
2803: || GET_CODE (XEXP (SET_SRC (x), 1)) == RETURN))
2804: return 1;
2805: if (XEXP (SET_SRC (x), 1) == pc_rtx
2806: && (GET_CODE (XEXP (SET_SRC (x), 2)) == LABEL_REF
2807: || GET_CODE (XEXP (SET_SRC (x), 2)) == RETURN))
2808: return 1;
2809: return 0;
2810: }
2811:
2812: /* Return 1 if X is an RTX that does nothing but set the condition codes
2813: and CLOBBER or USE registers.
2814: Return -1 if X does explicitly set the condition codes,
2815: but also does other things. */
2816:
2817: int
2818: sets_cc0_p (x)
2819: rtx x;
2820: {
2821: #ifdef HAVE_cc0
2822: if (GET_CODE (x) == SET && SET_DEST (x) == cc0_rtx)
2823: return 1;
2824: if (GET_CODE (x) == PARALLEL)
2825: {
2826: int i;
2827: int sets_cc0 = 0;
2828: int other_things = 0;
2829: for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
2830: {
2831: if (GET_CODE (XVECEXP (x, 0, i)) == SET
2832: && SET_DEST (XVECEXP (x, 0, i)) == cc0_rtx)
2833: sets_cc0 = 1;
2834: else if (GET_CODE (XVECEXP (x, 0, i)) == SET)
2835: other_things = 1;
2836: }
2837: return ! sets_cc0 ? 0 : other_things ? -1 : 1;
2838: }
2839: return 0;
2840: #else
2841: abort ();
2842: #endif
2843: }
2844:
2845: /* Follow any unconditional jump at LABEL;
2846: return the ultimate label reached by any such chain of jumps.
2847: If LABEL is not followed by a jump, return LABEL.
2848: If the chain loops or we can't find end, return LABEL,
2849: since that tells caller to avoid changing the insn.
2850:
2851: If RELOAD_COMPLETED is 0, we do not chain across a NOTE_INSN_LOOP_BEG or
2852: a USE or CLOBBER. */
2853:
2854: rtx
2855: follow_jumps (label)
2856: rtx label;
2857: {
2858: register rtx insn;
2859: register rtx next;
2860: register rtx value = label;
2861: register int depth;
2862:
2863: for (depth = 0;
2864: (depth < 10
2865: && (insn = next_active_insn (value)) != 0
2866: && GET_CODE (insn) == JUMP_INSN
2867: && (JUMP_LABEL (insn) != 0 || GET_CODE (PATTERN (insn)) == RETURN)
2868: && (next = NEXT_INSN (insn))
2869: && GET_CODE (next) == BARRIER);
2870: depth++)
2871: {
2872: /* Don't chain through the insn that jumps into a loop
2873: from outside the loop,
2874: since that would create multiple loop entry jumps
2875: and prevent loop optimization. */
2876: rtx tem;
2877: if (!reload_completed)
2878: for (tem = value; tem != insn; tem = NEXT_INSN (tem))
2879: if (GET_CODE (tem) == NOTE
2880: && NOTE_LINE_NUMBER (tem) == NOTE_INSN_LOOP_BEG)
2881: return value;
2882:
2883: /* If we have found a cycle, make the insn jump to itself. */
2884: if (JUMP_LABEL (insn) == label)
2885: return label;
2886: value = JUMP_LABEL (insn);
2887: }
2888: if (depth == 10)
2889: return label;
2890: return value;
2891: }
2892:
2893: /* Assuming that field IDX of X is a vector of label_refs,
2894: replace each of them by the ultimate label reached by it.
2895: Return nonzero if a change is made.
2896: If IGNORE_LOOPS is 0, we do not chain across a NOTE_INSN_LOOP_BEG. */
2897:
2898: static int
2899: tension_vector_labels (x, idx)
2900: register rtx x;
2901: register int idx;
2902: {
2903: int changed = 0;
2904: register int i;
2905: for (i = XVECLEN (x, idx) - 1; i >= 0; i--)
2906: {
2907: register rtx olabel = XEXP (XVECEXP (x, idx, i), 0);
2908: register rtx nlabel = follow_jumps (olabel);
2909: if (nlabel && nlabel != olabel)
2910: {
2911: XEXP (XVECEXP (x, idx, i), 0) = nlabel;
2912: ++LABEL_NUSES (nlabel);
2913: if (--LABEL_NUSES (olabel) == 0)
2914: delete_insn (olabel);
2915: changed = 1;
2916: }
2917: }
2918: return changed;
2919: }
2920:
2921: /* Find all CODE_LABELs referred to in X, and increment their use counts.
2922: If INSN is a JUMP_INSN and there is at least one CODE_LABEL referenced
2923: in INSN, then store one of them in JUMP_LABEL (INSN).
2924: If INSN is an INSN or a CALL_INSN and there is at least one CODE_LABEL
2925: referenced in INSN, add a REG_LABEL note containing that label to INSN.
2926: Also, when there are consecutive labels, canonicalize on the last of them.
2927:
2928: Note that two labels separated by a loop-beginning note
2929: must be kept distinct if we have not yet done loop-optimization,
2930: because the gap between them is where loop-optimize
2931: will want to move invariant code to. CROSS_JUMP tells us
2932: that loop-optimization is done with.
2933:
2934: Once reload has completed (CROSS_JUMP non-zero), we need not consider
2935: two labels distinct if they are separated by only USE or CLOBBER insns. */
2936:
2937: static void
2938: mark_jump_label (x, insn, cross_jump)
2939: register rtx x;
2940: rtx insn;
2941: int cross_jump;
2942: {
2943: register RTX_CODE code = GET_CODE (x);
2944: register int i;
2945: register char *fmt;
2946:
2947: switch (code)
2948: {
2949: case PC:
2950: case CC0:
2951: case REG:
2952: case SUBREG:
2953: case CONST_INT:
2954: case SYMBOL_REF:
2955: case CONST_DOUBLE:
2956: case CLOBBER:
2957: case CALL:
2958: return;
2959:
1.1.1.3 root 2960: case MEM:
2961: /* If this is a constant-pool reference, see if it is a label. */
2962: if (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
2963: && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)))
2964: mark_jump_label (get_pool_constant (XEXP (x, 0)), insn, cross_jump);
2965: break;
2966:
1.1 root 2967: case LABEL_REF:
2968: {
2969: register rtx label = XEXP (x, 0);
2970: register rtx next;
2971: if (GET_CODE (label) != CODE_LABEL)
2972: abort ();
1.1.1.4 root 2973: /* Ignore references to labels of containing functions. */
2974: if (LABEL_REF_NONLOCAL_P (x))
2975: break;
1.1 root 2976: /* If there are other labels following this one,
2977: replace it with the last of the consecutive labels. */
2978: for (next = NEXT_INSN (label); next; next = NEXT_INSN (next))
2979: {
2980: if (GET_CODE (next) == CODE_LABEL)
2981: label = next;
2982: else if (cross_jump && GET_CODE (next) == INSN
2983: && (GET_CODE (PATTERN (next)) == USE
2984: || GET_CODE (PATTERN (next)) == CLOBBER))
2985: continue;
2986: else if (GET_CODE (next) != NOTE)
2987: break;
2988: else if (! cross_jump
2989: && (NOTE_LINE_NUMBER (next) == NOTE_INSN_LOOP_BEG
2990: || NOTE_LINE_NUMBER (next) == NOTE_INSN_FUNCTION_END))
2991: break;
2992: }
2993: XEXP (x, 0) = label;
2994: ++LABEL_NUSES (label);
2995: if (insn)
2996: {
2997: if (GET_CODE (insn) == JUMP_INSN)
2998: JUMP_LABEL (insn) = label;
1.1.1.2 root 2999: else if (! find_reg_note (insn, REG_LABEL, label))
1.1 root 3000: {
3001: rtx next = next_real_insn (label);
3002: /* Don't record labels that refer to dispatch tables.
3003: This is not necessary, since the tablejump
3004: references the same label.
3005: And if we did record them, flow.c would make worse code. */
3006: if (next == 0
3007: || ! (GET_CODE (next) == JUMP_INSN
3008: && (GET_CODE (PATTERN (next)) == ADDR_VEC
3009: || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC)))
1.1.1.4 root 3010: {
3011: REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_LABEL, label,
3012: REG_NOTES (insn));
3013: /* Record in the note whether label is nonlocal. */
3014: LABEL_REF_NONLOCAL_P (REG_NOTES (insn))
3015: = LABEL_REF_NONLOCAL_P (x);
3016: }
1.1 root 3017: }
3018: }
3019: return;
3020: }
3021:
3022: /* Do walk the labels in a vector, but not the first operand of an
3023: ADDR_DIFF_VEC. Don't set the JUMP_LABEL of a vector. */
3024: case ADDR_VEC:
3025: case ADDR_DIFF_VEC:
3026: {
3027: int eltnum = code == ADDR_DIFF_VEC ? 1 : 0;
3028:
3029: for (i = 0; i < XVECLEN (x, eltnum); i++)
1.1.1.4 root 3030: mark_jump_label (XVECEXP (x, eltnum, i), NULL_RTX, cross_jump);
1.1 root 3031: return;
3032: }
3033: }
3034:
3035: fmt = GET_RTX_FORMAT (code);
3036: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3037: {
3038: if (fmt[i] == 'e')
3039: mark_jump_label (XEXP (x, i), insn, cross_jump);
3040: else if (fmt[i] == 'E')
3041: {
3042: register int j;
3043: for (j = 0; j < XVECLEN (x, i); j++)
3044: mark_jump_label (XVECEXP (x, i, j), insn, cross_jump);
3045: }
3046: }
3047: }
3048:
3049: /* If all INSN does is set the pc, delete it,
3050: and delete the insn that set the condition codes for it
3051: if that's what the previous thing was. */
3052:
3053: void
3054: delete_jump (insn)
3055: rtx insn;
3056: {
1.1.1.5 ! root 3057: register rtx set = single_set (insn);
! 3058:
! 3059: if (set && GET_CODE (SET_DEST (set)) == PC)
! 3060: delete_computation (insn);
! 3061: }
! 3062:
! 3063: /* Delete INSN and recursively delete insns that compute values used only
! 3064: by INSN. This uses the REG_DEAD notes computed during flow analysis.
! 3065: If we are running before flow.c, we need do nothing since flow.c will
! 3066: delete dead code. We also can't know if the registers being used are
! 3067: dead or not at this point.
! 3068:
! 3069: Otherwise, look at all our REG_DEAD notes. If a previous insn does
! 3070: nothing other than set a register that dies in this insn, we can delete
! 3071: that insn as well.
! 3072:
! 3073: On machines with CC0, if CC0 is used in this insn, we may be able to
! 3074: delete the insn that set it. */
! 3075:
! 3076: void
! 3077: delete_computation (insn)
! 3078: rtx insn;
! 3079: {
! 3080: rtx note, next;
1.1 root 3081:
3082: #ifdef HAVE_cc0
1.1.1.5 ! root 3083: if (reg_referenced_p (cc0_rtx, PATTERN (insn)))
! 3084: {
1.1.1.4 root 3085: rtx prev = prev_nonnote_insn (insn);
1.1 root 3086: /* We assume that at this stage
3087: CC's are always set explicitly
3088: and always immediately before the jump that
3089: will use them. So if the previous insn
3090: exists to set the CC's, delete it
3091: (unless it performs auto-increments, etc.). */
3092: if (prev && GET_CODE (prev) == INSN
3093: && sets_cc0_p (PATTERN (prev)))
3094: {
3095: if (sets_cc0_p (PATTERN (prev)) > 0
1.1.1.4 root 3096: && !FIND_REG_INC_NOTE (prev, NULL_RTX))
1.1.1.5 ! root 3097: delete_computation (prev);
1.1 root 3098: else
3099: /* Otherwise, show that cc0 won't be used. */
3100: REG_NOTES (prev) = gen_rtx (EXPR_LIST, REG_UNUSED,
3101: cc0_rtx, REG_NOTES (prev));
3102: }
1.1.1.4 root 3103: }
1.1.1.5 ! root 3104: #endif
1.1 root 3105:
1.1.1.4 root 3106: for (note = REG_NOTES (insn); note; note = next)
3107: {
3108: rtx our_prev;
1.1 root 3109:
1.1.1.4 root 3110: next = XEXP (note, 1);
1.1 root 3111:
1.1.1.4 root 3112: if (REG_NOTE_KIND (note) != REG_DEAD
3113: /* Verify that the REG_NOTE is legitimate. */
3114: || GET_CODE (XEXP (note, 0)) != REG)
3115: continue;
1.1 root 3116:
1.1.1.4 root 3117: for (our_prev = prev_nonnote_insn (insn);
3118: our_prev && GET_CODE (our_prev) == INSN;
3119: our_prev = prev_nonnote_insn (our_prev))
3120: {
3121: /* If we reach a SEQUENCE, it is too complex to try to
3122: do anything with it, so give up. */
3123: if (GET_CODE (PATTERN (our_prev)) == SEQUENCE)
3124: break;
1.1 root 3125:
1.1.1.4 root 3126: if (GET_CODE (PATTERN (our_prev)) == USE
3127: && GET_CODE (XEXP (PATTERN (our_prev), 0)) == INSN)
3128: /* reorg creates USEs that look like this. We leave them
3129: alone because reorg needs them for its own purposes. */
3130: break;
1.1 root 3131:
1.1.1.4 root 3132: if (reg_set_p (XEXP (note, 0), PATTERN (our_prev)))
3133: {
3134: if (FIND_REG_INC_NOTE (our_prev, NULL_RTX))
3135: break;
1.1 root 3136:
1.1.1.4 root 3137: if (GET_CODE (PATTERN (our_prev)) == PARALLEL)
3138: {
3139: /* If we find a SET of something else, we can't
3140: delete the insn. */
1.1 root 3141:
1.1.1.4 root 3142: int i;
1.1 root 3143:
1.1.1.4 root 3144: for (i = 0; i < XVECLEN (PATTERN (our_prev), 0); i++)
3145: {
3146: rtx part = XVECEXP (PATTERN (our_prev), 0, i);
1.1 root 3147:
1.1.1.4 root 3148: if (GET_CODE (part) == SET
3149: && SET_DEST (part) != XEXP (note, 0))
3150: break;
3151: }
1.1 root 3152:
1.1.1.4 root 3153: if (i == XVECLEN (PATTERN (our_prev), 0))
3154: delete_computation (our_prev);
3155: }
3156: else if (GET_CODE (PATTERN (our_prev)) == SET
3157: && SET_DEST (PATTERN (our_prev)) == XEXP (note, 0))
3158: delete_computation (our_prev);
3159:
3160: break;
3161: }
3162:
3163: /* If OUR_PREV references the register that dies here, it is an
3164: additional use. Hence any prior SET isn't dead. However, this
3165: insn becomes the new place for the REG_DEAD note. */
3166: if (reg_overlap_mentioned_p (XEXP (note, 0),
3167: PATTERN (our_prev)))
3168: {
3169: XEXP (note, 1) = REG_NOTES (our_prev);
3170: REG_NOTES (our_prev) = note;
3171: break;
3172: }
3173: }
1.1 root 3174: }
1.1.1.5 ! root 3175:
1.1.1.4 root 3176: delete_insn (insn);
1.1 root 3177: }
3178:
3179: /* Delete insn INSN from the chain of insns and update label ref counts.
3180: May delete some following insns as a consequence; may even delete
3181: a label elsewhere and insns that follow it.
3182:
3183: Returns the first insn after INSN that was not deleted. */
3184:
3185: rtx
3186: delete_insn (insn)
3187: register rtx insn;
3188: {
3189: register rtx next = NEXT_INSN (insn);
3190: register rtx prev = PREV_INSN (insn);
1.1.1.4 root 3191: register int was_code_label = (GET_CODE (insn) == CODE_LABEL);
3192: register int dont_really_delete = 0;
1.1 root 3193:
3194: while (next && INSN_DELETED_P (next))
3195: next = NEXT_INSN (next);
3196:
3197: /* This insn is already deleted => return first following nondeleted. */
3198: if (INSN_DELETED_P (insn))
3199: return next;
3200:
1.1.1.4 root 3201: /* Don't delete user-declared labels. Convert them to special NOTEs
3202: instead. */
3203: if (was_code_label && LABEL_NAME (insn) != 0
3204: && optimize && ! dont_really_delete)
3205: {
3206: PUT_CODE (insn, NOTE);
3207: NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED_LABEL;
3208: NOTE_SOURCE_FILE (insn) = 0;
3209: dont_really_delete = 1;
3210: }
3211: else
3212: /* Mark this insn as deleted. */
3213: INSN_DELETED_P (insn) = 1;
1.1 root 3214:
3215: /* If this is an unconditional jump, delete it from the jump chain. */
3216: if (simplejump_p (insn))
3217: delete_from_jump_chain (insn);
3218:
3219: /* If instruction is followed by a barrier,
3220: delete the barrier too. */
3221:
3222: if (next != 0 && GET_CODE (next) == BARRIER)
3223: {
3224: INSN_DELETED_P (next) = 1;
3225: next = NEXT_INSN (next);
3226: }
3227:
3228: /* Patch out INSN (and the barrier if any) */
3229:
1.1.1.4 root 3230: if (optimize && ! dont_really_delete)
1.1 root 3231: {
3232: if (prev)
3233: {
3234: NEXT_INSN (prev) = next;
3235: if (GET_CODE (prev) == INSN && GET_CODE (PATTERN (prev)) == SEQUENCE)
3236: NEXT_INSN (XVECEXP (PATTERN (prev), 0,
3237: XVECLEN (PATTERN (prev), 0) - 1)) = next;
3238: }
3239:
3240: if (next)
3241: {
3242: PREV_INSN (next) = prev;
3243: if (GET_CODE (next) == INSN && GET_CODE (PATTERN (next)) == SEQUENCE)
3244: PREV_INSN (XVECEXP (PATTERN (next), 0, 0)) = prev;
3245: }
3246:
3247: if (prev && NEXT_INSN (prev) == 0)
3248: set_last_insn (prev);
3249: }
3250:
3251: /* If deleting a jump, decrement the count of the label,
3252: and delete the label if it is now unused. */
3253:
3254: if (GET_CODE (insn) == JUMP_INSN && JUMP_LABEL (insn))
3255: if (--LABEL_NUSES (JUMP_LABEL (insn)) == 0)
3256: {
3257: /* This can delete NEXT or PREV,
3258: either directly if NEXT is JUMP_LABEL (INSN),
3259: or indirectly through more levels of jumps. */
3260: delete_insn (JUMP_LABEL (insn));
3261: /* I feel a little doubtful about this loop,
3262: but I see no clean and sure alternative way
3263: to find the first insn after INSN that is not now deleted.
3264: I hope this works. */
3265: while (next && INSN_DELETED_P (next))
3266: next = NEXT_INSN (next);
3267: return next;
3268: }
3269:
3270: while (prev && (INSN_DELETED_P (prev) || GET_CODE (prev) == NOTE))
3271: prev = PREV_INSN (prev);
3272:
3273: /* If INSN was a label and a dispatch table follows it,
3274: delete the dispatch table. The tablejump must have gone already.
3275: It isn't useful to fall through into a table. */
3276:
1.1.1.4 root 3277: if (was_code_label
1.1 root 3278: && NEXT_INSN (insn) != 0
3279: && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
3280: && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC
3281: || GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_DIFF_VEC))
3282: next = delete_insn (NEXT_INSN (insn));
3283:
3284: /* If INSN was a label, delete insns following it if now unreachable. */
3285:
1.1.1.4 root 3286: if (was_code_label && prev && GET_CODE (prev) == BARRIER)
1.1 root 3287: {
3288: register RTX_CODE code;
3289: while (next != 0
3290: && ((code = GET_CODE (next)) == INSN
3291: || code == JUMP_INSN || code == CALL_INSN
1.1.1.3 root 3292: || code == NOTE
3293: || (code == CODE_LABEL && INSN_DELETED_P (next))))
1.1 root 3294: {
3295: if (code == NOTE
3296: && NOTE_LINE_NUMBER (next) != NOTE_INSN_FUNCTION_END)
3297: next = NEXT_INSN (next);
1.1.1.3 root 3298: /* Keep going past other deleted labels to delete what follows. */
3299: else if (code == CODE_LABEL && INSN_DELETED_P (next))
3300: next = NEXT_INSN (next);
1.1 root 3301: else
3302: /* Note: if this deletes a jump, it can cause more
3303: deletion of unreachable code, after a different label.
3304: As long as the value from this recursive call is correct,
3305: this invocation functions correctly. */
3306: next = delete_insn (next);
3307: }
3308: }
3309:
3310: return next;
3311: }
3312:
3313: /* Advance from INSN till reaching something not deleted
3314: then return that. May return INSN itself. */
3315:
3316: rtx
3317: next_nondeleted_insn (insn)
3318: rtx insn;
3319: {
3320: while (INSN_DELETED_P (insn))
3321: insn = NEXT_INSN (insn);
3322: return insn;
3323: }
3324:
3325: /* Delete a range of insns from FROM to TO, inclusive.
3326: This is for the sake of peephole optimization, so assume
3327: that whatever these insns do will still be done by a new
3328: peephole insn that will replace them. */
3329:
3330: void
3331: delete_for_peephole (from, to)
3332: register rtx from, to;
3333: {
3334: register rtx insn = from;
3335:
3336: while (1)
3337: {
3338: register rtx next = NEXT_INSN (insn);
3339: register rtx prev = PREV_INSN (insn);
3340:
3341: if (GET_CODE (insn) != NOTE)
3342: {
3343: INSN_DELETED_P (insn) = 1;
3344:
3345: /* Patch this insn out of the chain. */
3346: /* We don't do this all at once, because we
3347: must preserve all NOTEs. */
3348: if (prev)
3349: NEXT_INSN (prev) = next;
3350:
3351: if (next)
3352: PREV_INSN (next) = prev;
3353: }
3354:
3355: if (insn == to)
3356: break;
3357: insn = next;
3358: }
3359:
3360: /* Note that if TO is an unconditional jump
3361: we *do not* delete the BARRIER that follows,
3362: since the peephole that replaces this sequence
3363: is also an unconditional jump in that case. */
3364: }
3365:
3366: /* Invert the condition of the jump JUMP, and make it jump
3367: to label NLABEL instead of where it jumps now. */
3368:
3369: int
3370: invert_jump (jump, nlabel)
3371: rtx jump, nlabel;
3372: {
3373: register rtx olabel = JUMP_LABEL (jump);
3374:
3375: /* We have to either invert the condition and change the label or
3376: do neither. Either operation could fail. We first try to invert
3377: the jump. If that succeeds, we try changing the label. If that fails,
3378: we invert the jump back to what it was. */
3379:
3380: if (! invert_exp (PATTERN (jump), jump))
3381: return 0;
3382:
3383: if (redirect_jump (jump, nlabel))
3384: return 1;
3385:
3386: if (! invert_exp (PATTERN (jump), jump))
3387: /* This should just be putting it back the way it was. */
3388: abort ();
3389:
3390: return 0;
3391: }
3392:
3393: /* Invert the jump condition of rtx X contained in jump insn, INSN.
3394:
3395: Return 1 if we can do so, 0 if we cannot find a way to do so that
3396: matches a pattern. */
3397:
1.1.1.4 root 3398: int
1.1 root 3399: invert_exp (x, insn)
3400: rtx x;
3401: rtx insn;
3402: {
3403: register RTX_CODE code;
3404: register int i;
3405: register char *fmt;
3406:
3407: code = GET_CODE (x);
3408:
3409: if (code == IF_THEN_ELSE)
3410: {
3411: register rtx comp = XEXP (x, 0);
3412: register rtx tem;
3413:
3414: /* We can do this in two ways: The preferable way, which can only
3415: be done if this is not an integer comparison, is to reverse
3416: the comparison code. Otherwise, swap the THEN-part and ELSE-part
3417: of the IF_THEN_ELSE. If we can't do either, fail. */
3418:
3419: if (can_reverse_comparison_p (comp, insn)
3420: && validate_change (insn, &XEXP (x, 0),
3421: gen_rtx (reverse_condition (GET_CODE (comp)),
3422: GET_MODE (comp), XEXP (comp, 0),
3423: XEXP (comp, 1)), 0))
3424: return 1;
3425:
3426: tem = XEXP (x, 1);
3427: validate_change (insn, &XEXP (x, 1), XEXP (x, 2), 1);
3428: validate_change (insn, &XEXP (x, 2), tem, 1);
3429: return apply_change_group ();
3430: }
3431:
3432: fmt = GET_RTX_FORMAT (code);
3433: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3434: {
3435: if (fmt[i] == 'e')
3436: if (! invert_exp (XEXP (x, i), insn))
3437: return 0;
3438: if (fmt[i] == 'E')
3439: {
3440: register int j;
3441: for (j = 0; j < XVECLEN (x, i); j++)
3442: if (!invert_exp (XVECEXP (x, i, j), insn))
3443: return 0;
3444: }
3445: }
3446:
3447: return 1;
3448: }
3449:
3450: /* Make jump JUMP jump to label NLABEL instead of where it jumps now.
3451: If the old jump target label is unused as a result,
3452: it and the code following it may be deleted.
3453:
3454: If NLABEL is zero, we are to turn the jump into a (possibly conditional)
3455: RETURN insn.
3456:
3457: The return value will be 1 if the change was made, 0 if it wasn't (this
3458: can only occur for NLABEL == 0). */
3459:
3460: int
3461: redirect_jump (jump, nlabel)
3462: rtx jump, nlabel;
3463: {
3464: register rtx olabel = JUMP_LABEL (jump);
3465:
3466: if (nlabel == olabel)
3467: return 1;
3468:
3469: if (! redirect_exp (&PATTERN (jump), olabel, nlabel, jump))
3470: return 0;
3471:
3472: /* If this is an unconditional branch, delete it from the jump_chain of
3473: OLABEL and add it to the jump_chain of NLABEL (assuming both labels
3474: have UID's in range and JUMP_CHAIN is valid). */
3475: if (jump_chain && (simplejump_p (jump)
3476: || GET_CODE (PATTERN (jump)) == RETURN))
3477: {
3478: int label_index = nlabel ? INSN_UID (nlabel) : 0;
3479:
3480: delete_from_jump_chain (jump);
3481: if (label_index < max_jump_chain
3482: && INSN_UID (jump) < max_jump_chain)
3483: {
3484: jump_chain[INSN_UID (jump)] = jump_chain[label_index];
3485: jump_chain[label_index] = jump;
3486: }
3487: }
3488:
3489: JUMP_LABEL (jump) = nlabel;
3490: if (nlabel)
3491: ++LABEL_NUSES (nlabel);
3492:
3493: if (olabel && --LABEL_NUSES (olabel) == 0)
3494: delete_insn (olabel);
3495:
3496: return 1;
3497: }
3498:
3499: /* Delete the instruction JUMP from any jump chain it might be on. */
3500:
3501: static void
3502: delete_from_jump_chain (jump)
3503: rtx jump;
3504: {
3505: int index;
3506: rtx olabel = JUMP_LABEL (jump);
3507:
3508: /* Handle unconditional jumps. */
3509: if (jump_chain && olabel != 0
3510: && INSN_UID (olabel) < max_jump_chain
3511: && simplejump_p (jump))
3512: index = INSN_UID (olabel);
3513: /* Handle return insns. */
3514: else if (jump_chain && GET_CODE (PATTERN (jump)) == RETURN)
3515: index = 0;
3516: else return;
3517:
3518: if (jump_chain[index] == jump)
3519: jump_chain[index] = jump_chain[INSN_UID (jump)];
3520: else
3521: {
3522: rtx insn;
3523:
3524: for (insn = jump_chain[index];
3525: insn != 0;
3526: insn = jump_chain[INSN_UID (insn)])
3527: if (jump_chain[INSN_UID (insn)] == jump)
3528: {
3529: jump_chain[INSN_UID (insn)] = jump_chain[INSN_UID (jump)];
3530: break;
3531: }
3532: }
3533: }
3534:
3535: /* If NLABEL is nonzero, throughout the rtx at LOC,
3536: alter (LABEL_REF OLABEL) to (LABEL_REF NLABEL). If OLABEL is
3537: zero, alter (RETURN) to (LABEL_REF NLABEL).
3538:
3539: If NLABEL is zero, alter (LABEL_REF OLABEL) to (RETURN) and check
3540: validity with validate_change. Convert (set (pc) (label_ref olabel))
3541: to (return).
3542:
3543: Return 0 if we found a change we would like to make but it is invalid.
3544: Otherwise, return 1. */
3545:
1.1.1.4 root 3546: int
1.1 root 3547: redirect_exp (loc, olabel, nlabel, insn)
3548: rtx *loc;
3549: rtx olabel, nlabel;
3550: rtx insn;
3551: {
3552: register rtx x = *loc;
3553: register RTX_CODE code = GET_CODE (x);
3554: register int i;
3555: register char *fmt;
3556:
3557: if (code == LABEL_REF)
3558: {
3559: if (XEXP (x, 0) == olabel)
3560: {
3561: if (nlabel)
3562: XEXP (x, 0) = nlabel;
3563: else
3564: return validate_change (insn, loc, gen_rtx (RETURN, VOIDmode), 0);
3565: return 1;
3566: }
3567: }
3568: else if (code == RETURN && olabel == 0)
3569: {
3570: x = gen_rtx (LABEL_REF, VOIDmode, nlabel);
3571: if (loc == &PATTERN (insn))
3572: x = gen_rtx (SET, VOIDmode, pc_rtx, x);
3573: return validate_change (insn, loc, x, 0);
3574: }
3575:
3576: if (code == SET && nlabel == 0 && SET_DEST (x) == pc_rtx
3577: && GET_CODE (SET_SRC (x)) == LABEL_REF
3578: && XEXP (SET_SRC (x), 0) == olabel)
3579: return validate_change (insn, loc, gen_rtx (RETURN, VOIDmode), 0);
3580:
3581: fmt = GET_RTX_FORMAT (code);
3582: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3583: {
3584: if (fmt[i] == 'e')
3585: if (! redirect_exp (&XEXP (x, i), olabel, nlabel, insn))
3586: return 0;
3587: if (fmt[i] == 'E')
3588: {
3589: register int j;
3590: for (j = 0; j < XVECLEN (x, i); j++)
3591: if (! redirect_exp (&XVECEXP (x, i, j), olabel, nlabel, insn))
3592: return 0;
3593: }
3594: }
3595:
3596: return 1;
3597: }
3598:
3599: /* Make jump JUMP jump to label NLABEL, assuming it used to be a tablejump.
3600:
3601: If the old jump target label (before the dispatch table) becomes unused,
3602: it and the dispatch table may be deleted. In that case, find the insn
1.1.1.3 root 3603: before the jump references that label and delete it and logical successors
1.1 root 3604: too. */
3605:
3606: void
3607: redirect_tablejump (jump, nlabel)
3608: rtx jump, nlabel;
3609: {
3610: register rtx olabel = JUMP_LABEL (jump);
3611:
3612: /* Add this jump to the jump_chain of NLABEL. */
3613: if (jump_chain && INSN_UID (nlabel) < max_jump_chain
3614: && INSN_UID (jump) < max_jump_chain)
3615: {
3616: jump_chain[INSN_UID (jump)] = jump_chain[INSN_UID (nlabel)];
3617: jump_chain[INSN_UID (nlabel)] = jump;
3618: }
3619:
3620: PATTERN (jump) = gen_jump (nlabel);
3621: JUMP_LABEL (jump) = nlabel;
3622: ++LABEL_NUSES (nlabel);
3623: INSN_CODE (jump) = -1;
3624:
3625: if (--LABEL_NUSES (olabel) == 0)
3626: {
3627: delete_labelref_insn (jump, olabel, 0);
3628: delete_insn (olabel);
3629: }
3630: }
3631:
3632: /* Find the insn referencing LABEL that is a logical predecessor of INSN.
3633: If we found one, delete it and then delete this insn if DELETE_THIS is
3634: non-zero. Return non-zero if INSN or a predecessor references LABEL. */
3635:
3636: static int
3637: delete_labelref_insn (insn, label, delete_this)
3638: rtx insn, label;
3639: int delete_this;
3640: {
3641: int deleted = 0;
3642: rtx link;
3643:
3644: if (GET_CODE (insn) != NOTE
3645: && reg_mentioned_p (label, PATTERN (insn)))
3646: {
3647: if (delete_this)
3648: {
3649: delete_insn (insn);
3650: deleted = 1;
3651: }
3652: else
3653: return 1;
3654: }
3655:
3656: for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
3657: if (delete_labelref_insn (XEXP (link, 0), label, 1))
3658: {
3659: if (delete_this)
3660: {
3661: delete_insn (insn);
3662: deleted = 1;
3663: }
3664: else
3665: return 1;
3666: }
3667:
3668: return deleted;
3669: }
3670:
3671: /* Like rtx_equal_p except that it considers two REGs as equal
3672: if they renumber to the same value. */
3673:
3674: int
3675: rtx_renumbered_equal_p (x, y)
3676: rtx x, y;
3677: {
3678: register int i;
3679: register RTX_CODE code = GET_CODE (x);
3680: register char *fmt;
3681:
3682: if (x == y)
3683: return 1;
3684: if ((code == REG || (code == SUBREG && GET_CODE (SUBREG_REG (x)) == REG))
3685: && (GET_CODE (y) == REG || (GET_CODE (y) == SUBREG
3686: && GET_CODE (SUBREG_REG (y)) == REG)))
3687: {
3688: register int j;
3689:
3690: if (GET_MODE (x) != GET_MODE (y))
3691: return 0;
3692:
3693: /* If we haven't done any renumbering, don't
3694: make any assumptions. */
3695: if (reg_renumber == 0)
3696: return rtx_equal_p (x, y);
3697:
3698: if (code == SUBREG)
3699: {
3700: i = REGNO (SUBREG_REG (x));
3701: if (reg_renumber[i] >= 0)
3702: i = reg_renumber[i];
3703: i += SUBREG_WORD (x);
3704: }
3705: else
3706: {
3707: i = REGNO (x);
3708: if (reg_renumber[i] >= 0)
3709: i = reg_renumber[i];
3710: }
3711: if (GET_CODE (y) == SUBREG)
3712: {
3713: j = REGNO (SUBREG_REG (y));
3714: if (reg_renumber[j] >= 0)
3715: j = reg_renumber[j];
3716: j += SUBREG_WORD (y);
3717: }
3718: else
3719: {
3720: j = REGNO (y);
3721: if (reg_renumber[j] >= 0)
3722: j = reg_renumber[j];
3723: }
3724: return i == j;
3725: }
3726: /* Now we have disposed of all the cases
3727: in which different rtx codes can match. */
3728: if (code != GET_CODE (y))
3729: return 0;
3730: switch (code)
3731: {
3732: case PC:
3733: case CC0:
3734: case ADDR_VEC:
3735: case ADDR_DIFF_VEC:
3736: return 0;
3737:
3738: case CONST_INT:
3739: return XINT (x, 0) == XINT (y, 0);
3740:
3741: case LABEL_REF:
1.1.1.4 root 3742: /* We can't assume nonlocal labels have their following insns yet. */
3743: if (LABEL_REF_NONLOCAL_P (x) || LABEL_REF_NONLOCAL_P (y))
3744: return XEXP (x, 0) == XEXP (y, 0);
1.1 root 3745: /* Two label-refs are equivalent if they point at labels
3746: in the same position in the instruction stream. */
3747: return (next_real_insn (XEXP (x, 0))
3748: == next_real_insn (XEXP (y, 0)));
3749:
3750: case SYMBOL_REF:
3751: return XSTR (x, 0) == XSTR (y, 0);
3752: }
3753:
3754: /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. */
3755:
3756: if (GET_MODE (x) != GET_MODE (y))
3757: return 0;
3758:
3759: /* Compare the elements. If any pair of corresponding elements
3760: fail to match, return 0 for the whole things. */
3761:
3762: fmt = GET_RTX_FORMAT (code);
3763: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3764: {
3765: register int j;
3766: switch (fmt[i])
3767: {
1.1.1.4 root 3768: case 'w':
3769: if (XWINT (x, i) != XWINT (y, i))
3770: return 0;
3771: break;
3772:
1.1 root 3773: case 'i':
3774: if (XINT (x, i) != XINT (y, i))
3775: return 0;
3776: break;
3777:
3778: case 's':
3779: if (strcmp (XSTR (x, i), XSTR (y, i)))
3780: return 0;
3781: break;
3782:
3783: case 'e':
3784: if (! rtx_renumbered_equal_p (XEXP (x, i), XEXP (y, i)))
3785: return 0;
3786: break;
3787:
3788: case 'u':
3789: if (XEXP (x, i) != XEXP (y, i))
3790: return 0;
3791: /* fall through. */
3792: case '0':
3793: break;
3794:
3795: case 'E':
3796: if (XVECLEN (x, i) != XVECLEN (y, i))
3797: return 0;
3798: for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3799: if (!rtx_renumbered_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)))
3800: return 0;
3801: break;
3802:
3803: default:
3804: abort ();
3805: }
3806: }
3807: return 1;
3808: }
3809:
3810: /* If X is a hard register or equivalent to one or a subregister of one,
3811: return the hard register number. If X is a pseudo register that was not
3812: assigned a hard register, return the pseudo register number. Otherwise,
3813: return -1. Any rtx is valid for X. */
3814:
3815: int
3816: true_regnum (x)
3817: rtx x;
3818: {
3819: if (GET_CODE (x) == REG)
3820: {
3821: if (REGNO (x) >= FIRST_PSEUDO_REGISTER && reg_renumber[REGNO (x)] >= 0)
3822: return reg_renumber[REGNO (x)];
3823: return REGNO (x);
3824: }
3825: if (GET_CODE (x) == SUBREG)
3826: {
3827: int base = true_regnum (SUBREG_REG (x));
3828: if (base >= 0 && base < FIRST_PSEUDO_REGISTER)
3829: return SUBREG_WORD (x) + base;
3830: }
3831: return -1;
3832: }
3833:
3834: /* Optimize code of the form:
3835:
3836: for (x = a[i]; x; ...)
3837: ...
3838: for (x = a[i]; x; ...)
3839: ...
3840: foo:
3841:
3842: Loop optimize will change the above code into
3843:
3844: if (x = a[i])
3845: for (;;)
3846: { ...; if (! (x = ...)) break; }
3847: if (x = a[i])
3848: for (;;)
3849: { ...; if (! (x = ...)) break; }
3850: foo:
3851:
3852: In general, if the first test fails, the program can branch
3853: directly to `foo' and skip the second try which is doomed to fail.
3854: We run this after loop optimization and before flow analysis. */
3855:
3856: /* When comparing the insn patterns, we track the fact that different
3857: pseudo-register numbers may have been used in each computation.
3858: The following array stores an equivalence -- same_regs[I] == J means
3859: that pseudo register I was used in the first set of tests in a context
3860: where J was used in the second set. We also count the number of such
3861: pending equivalences. If nonzero, the expressions really aren't the
3862: same. */
3863:
1.1.1.5 ! root 3864: static int *same_regs;
1.1 root 3865:
3866: static int num_same_regs;
3867:
3868: /* Track any registers modified between the target of the first jump and
3869: the second jump. They never compare equal. */
3870:
3871: static char *modified_regs;
3872:
3873: /* Record if memory was modified. */
3874:
3875: static int modified_mem;
3876:
3877: /* Called via note_stores on each insn between the target of the first
3878: branch and the second branch. It marks any changed registers. */
3879:
3880: static void
3881: mark_modified_reg (dest, x)
3882: rtx dest;
3883: rtx x;
3884: {
3885: int regno, i;
3886:
3887: if (GET_CODE (dest) == SUBREG)
3888: dest = SUBREG_REG (dest);
3889:
3890: if (GET_CODE (dest) == MEM)
3891: modified_mem = 1;
3892:
3893: if (GET_CODE (dest) != REG)
3894: return;
3895:
3896: regno = REGNO (dest);
3897: if (regno >= FIRST_PSEUDO_REGISTER)
3898: modified_regs[regno] = 1;
3899: else
3900: for (i = 0; i < HARD_REGNO_NREGS (regno, GET_MODE (dest)); i++)
3901: modified_regs[regno + i] = 1;
3902: }
3903:
3904: /* F is the first insn in the chain of insns. */
3905:
3906: void
3907: thread_jumps (f, max_reg, verbose)
3908: rtx f;
3909: int max_reg;
3910: int verbose;
3911: {
3912: /* Basic algorithm is to find a conditional branch,
3913: the label it may branch to, and the branch after
3914: that label. If the two branches test the same condition,
3915: walk back from both branch paths until the insn patterns
3916: differ, or code labels are hit. If we make it back to
3917: the target of the first branch, then we know that the first branch
3918: will either always succeed or always fail depending on the relative
3919: senses of the two branches. So adjust the first branch accordingly
3920: in this case. */
3921:
3922: rtx label, b1, b2, t1, t2;
3923: enum rtx_code code1, code2;
3924: rtx b1op0, b1op1, b2op0, b2op1;
3925: int changed = 1;
3926: int i;
1.1.1.5 ! root 3927: int *all_reset;
1.1 root 3928:
3929: /* Allocate register tables and quick-reset table. */
3930: modified_regs = (char *) alloca (max_reg * sizeof (char));
1.1.1.5 ! root 3931: same_regs = (int *) alloca (max_reg * sizeof (int));
! 3932: all_reset = (int *) alloca (max_reg * sizeof (int));
1.1 root 3933: for (i = 0; i < max_reg; i++)
3934: all_reset[i] = -1;
3935:
3936: while (changed)
3937: {
3938: changed = 0;
3939:
3940: for (b1 = f; b1; b1 = NEXT_INSN (b1))
3941: {
3942: /* Get to a candidate branch insn. */
3943: if (GET_CODE (b1) != JUMP_INSN
3944: || ! condjump_p (b1) || simplejump_p (b1)
3945: || JUMP_LABEL (b1) == 0)
3946: continue;
3947:
3948: bzero (modified_regs, max_reg * sizeof (char));
3949: modified_mem = 0;
3950:
1.1.1.5 ! root 3951: bcopy (all_reset, same_regs, max_reg * sizeof (int));
1.1 root 3952: num_same_regs = 0;
3953:
3954: label = JUMP_LABEL (b1);
3955:
3956: /* Look for a branch after the target. Record any registers and
3957: memory modified between the target and the branch. Stop when we
3958: get to a label since we can't know what was changed there. */
3959: for (b2 = NEXT_INSN (label); b2; b2 = NEXT_INSN (b2))
3960: {
3961: if (GET_CODE (b2) == CODE_LABEL)
3962: break;
3963:
3964: else if (GET_CODE (b2) == JUMP_INSN)
3965: {
3966: /* If this is an unconditional jump and is the only use of
3967: its target label, we can follow it. */
3968: if (simplejump_p (b2)
3969: && JUMP_LABEL (b2) != 0
3970: && LABEL_NUSES (JUMP_LABEL (b2)) == 1)
3971: {
3972: b2 = JUMP_LABEL (b2);
3973: continue;
3974: }
3975: else
3976: break;
3977: }
3978:
3979: if (GET_CODE (b2) != CALL_INSN && GET_CODE (b2) != INSN)
3980: continue;
3981:
3982: if (GET_CODE (b2) == CALL_INSN)
3983: {
3984: modified_mem = 1;
3985: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3986: if (call_used_regs[i] && ! fixed_regs[i]
3987: && i != STACK_POINTER_REGNUM
3988: && i != FRAME_POINTER_REGNUM
3989: && i != ARG_POINTER_REGNUM)
3990: modified_regs[i] = 1;
3991: }
3992:
3993: note_stores (PATTERN (b2), mark_modified_reg);
3994: }
3995:
3996: /* Check the next candidate branch insn from the label
3997: of the first. */
3998: if (b2 == 0
3999: || GET_CODE (b2) != JUMP_INSN
4000: || b2 == b1
4001: || ! condjump_p (b2)
4002: || simplejump_p (b2))
4003: continue;
4004:
4005: /* Get the comparison codes and operands, reversing the
4006: codes if appropriate. If we don't have comparison codes,
4007: we can't do anything. */
4008: b1op0 = XEXP (XEXP (SET_SRC (PATTERN (b1)), 0), 0);
4009: b1op1 = XEXP (XEXP (SET_SRC (PATTERN (b1)), 0), 1);
4010: code1 = GET_CODE (XEXP (SET_SRC (PATTERN (b1)), 0));
4011: if (XEXP (SET_SRC (PATTERN (b1)), 1) == pc_rtx)
4012: code1 = reverse_condition (code1);
4013:
4014: b2op0 = XEXP (XEXP (SET_SRC (PATTERN (b2)), 0), 0);
4015: b2op1 = XEXP (XEXP (SET_SRC (PATTERN (b2)), 0), 1);
4016: code2 = GET_CODE (XEXP (SET_SRC (PATTERN (b2)), 0));
4017: if (XEXP (SET_SRC (PATTERN (b2)), 1) == pc_rtx)
4018: code2 = reverse_condition (code2);
4019:
4020: /* If they test the same things and knowing that B1 branches
4021: tells us whether or not B2 branches, check if we
4022: can thread the branch. */
4023: if (rtx_equal_for_thread_p (b1op0, b2op0, b2)
4024: && rtx_equal_for_thread_p (b1op1, b2op1, b2)
4025: && (comparison_dominates_p (code1, code2)
4026: || comparison_dominates_p (code1, reverse_condition (code2))))
4027: {
4028: t1 = prev_nonnote_insn (b1);
4029: t2 = prev_nonnote_insn (b2);
4030:
4031: while (t1 != 0 && t2 != 0)
4032: {
4033: if (t1 == 0 || t2 == 0)
4034: break;
4035:
4036: if (t2 == label)
4037: {
4038: /* We have reached the target of the first branch.
4039: If there are no pending register equivalents,
4040: we know that this branch will either always
4041: succeed (if the senses of the two branches are
4042: the same) or always fail (if not). */
4043: rtx new_label;
4044:
4045: if (num_same_regs != 0)
4046: break;
4047:
4048: if (comparison_dominates_p (code1, code2))
4049: new_label = JUMP_LABEL (b2);
4050: else
4051: new_label = get_label_after (b2);
4052:
4053: if (JUMP_LABEL (b1) != new_label
4054: && redirect_jump (b1, new_label))
4055: changed = 1;
4056: break;
4057: }
4058:
4059: /* If either of these is not a normal insn (it might be
4060: a JUMP_INSN, CALL_INSN, or CODE_LABEL) we fail. (NOTEs
4061: have already been skipped above.) Similarly, fail
4062: if the insns are different. */
4063: if (GET_CODE (t1) != INSN || GET_CODE (t2) != INSN
4064: || recog_memoized (t1) != recog_memoized (t2)
4065: || ! rtx_equal_for_thread_p (PATTERN (t1),
4066: PATTERN (t2), t2))
4067: break;
4068:
4069: t1 = prev_nonnote_insn (t1);
4070: t2 = prev_nonnote_insn (t2);
4071: }
4072: }
4073: }
4074: }
4075: }
4076:
4077: /* This is like RTX_EQUAL_P except that it knows about our handling of
4078: possibly equivalent registers and knows to consider volatile and
4079: modified objects as not equal.
4080:
4081: YINSN is the insn containing Y. */
4082:
4083: int
4084: rtx_equal_for_thread_p (x, y, yinsn)
4085: rtx x, y;
4086: rtx yinsn;
4087: {
4088: register int i;
4089: register int j;
4090: register enum rtx_code code;
4091: register char *fmt;
4092:
4093: code = GET_CODE (x);
4094: /* Rtx's of different codes cannot be equal. */
4095: if (code != GET_CODE (y))
4096: return 0;
4097:
4098: /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
4099: (REG:SI x) and (REG:HI x) are NOT equivalent. */
4100:
4101: if (GET_MODE (x) != GET_MODE (y))
4102: return 0;
4103:
4104: /* Handle special-cases first. */
4105: switch (code)
4106: {
4107: case REG:
4108: if (REGNO (x) == REGNO (y) && ! modified_regs[REGNO (x)])
4109: return 1;
4110:
4111: /* If neither is user variable or hard register, check for possible
4112: equivalence. */
4113: if (REG_USERVAR_P (x) || REG_USERVAR_P (y)
4114: || REGNO (x) < FIRST_PSEUDO_REGISTER
4115: || REGNO (y) < FIRST_PSEUDO_REGISTER)
4116: return 0;
4117:
4118: if (same_regs[REGNO (x)] == -1)
4119: {
4120: same_regs[REGNO (x)] = REGNO (y);
4121: num_same_regs++;
4122:
4123: /* If this is the first time we are seeing a register on the `Y'
4124: side, see if it is the last use. If not, we can't thread the
4125: jump, so mark it as not equivalent. */
4126: if (regno_last_uid[REGNO (y)] != INSN_UID (yinsn))
4127: return 0;
4128:
4129: return 1;
4130: }
4131: else
4132: return (same_regs[REGNO (x)] == REGNO (y));
4133:
4134: break;
4135:
4136: case MEM:
1.1.1.3 root 4137: /* If memory modified or either volatile, not equivalent.
1.1 root 4138: Else, check address. */
4139: if (modified_mem || MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
4140: return 0;
4141:
4142: return rtx_equal_for_thread_p (XEXP (x, 0), XEXP (y, 0), yinsn);
4143:
4144: case ASM_INPUT:
4145: if (MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
4146: return 0;
4147:
4148: break;
4149:
4150: case SET:
4151: /* Cancel a pending `same_regs' if setting equivalenced registers.
4152: Then process source. */
4153: if (GET_CODE (SET_DEST (x)) == REG
4154: && GET_CODE (SET_DEST (y)) == REG)
4155: {
4156: if (same_regs[REGNO (SET_DEST (x))] == REGNO (SET_DEST (y)))
4157: {
4158: same_regs[REGNO (SET_DEST (x))] = -1;
4159: num_same_regs--;
4160: }
4161: else if (REGNO (SET_DEST (x)) != REGNO (SET_DEST (y)))
4162: return 0;
4163: }
4164: else
4165: if (rtx_equal_for_thread_p (SET_DEST (x), SET_DEST (y), yinsn) == 0)
4166: return 0;
4167:
4168: return rtx_equal_for_thread_p (SET_SRC (x), SET_SRC (y), yinsn);
4169:
4170: case LABEL_REF:
4171: return XEXP (x, 0) == XEXP (y, 0);
4172:
4173: case SYMBOL_REF:
4174: return XSTR (x, 0) == XSTR (y, 0);
4175: }
4176:
4177: if (x == y)
4178: return 1;
4179:
4180: fmt = GET_RTX_FORMAT (code);
4181: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4182: {
4183: switch (fmt[i])
4184: {
1.1.1.4 root 4185: case 'w':
4186: if (XWINT (x, i) != XWINT (y, i))
4187: return 0;
4188: break;
4189:
1.1 root 4190: case 'n':
4191: case 'i':
4192: if (XINT (x, i) != XINT (y, i))
4193: return 0;
4194: break;
4195:
4196: case 'V':
4197: case 'E':
4198: /* Two vectors must have the same length. */
4199: if (XVECLEN (x, i) != XVECLEN (y, i))
4200: return 0;
4201:
4202: /* And the corresponding elements must match. */
4203: for (j = 0; j < XVECLEN (x, i); j++)
4204: if (rtx_equal_for_thread_p (XVECEXP (x, i, j),
4205: XVECEXP (y, i, j), yinsn) == 0)
4206: return 0;
4207: break;
4208:
4209: case 'e':
4210: if (rtx_equal_for_thread_p (XEXP (x, i), XEXP (y, i), yinsn) == 0)
4211: return 0;
4212: break;
4213:
4214: case 'S':
4215: case 's':
4216: if (strcmp (XSTR (x, i), XSTR (y, i)))
4217: return 0;
4218: break;
4219:
4220: case 'u':
4221: /* These are just backpointers, so they don't matter. */
4222: break;
4223:
4224: case '0':
4225: break;
4226:
4227: /* It is believed that rtx's at this level will never
4228: contain anything but integers and other rtx's,
4229: except for within LABEL_REFs and SYMBOL_REFs. */
4230: default:
4231: abort ();
4232: }
4233: }
4234: return 1;
4235: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.