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