![[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 [Research Unix] / researchv10dc / cmd / gcc|
Return to jump.c CVS log | Up to [Research Unix] / researchv10dc / cmd / gcc |
1.1 root 1: /* Optimize jump instructions, for GNU compiler.
2: Copyright (C) 1988 Free Software Foundation, Inc.
3:
4: This file is part of GNU CC.
5:
6: GNU CC is distributed in the hope that it will be useful,
7: but WITHOUT ANY WARRANTY. No author or distributor
8: accepts responsibility to anyone for the consequences of using it
9: or for whether it serves any particular purpose or works at all,
10: unless he says so in writing. Refer to the GNU CC General Public
11: License for full details.
12:
13: Everyone is granted permission to copy, modify and redistribute
14: GNU CC, but only under the conditions described in the
15: GNU CC General Public License. A copy of this license is
16: supposed to have been given to you along with GNU CC so you
17: can know your rights and responsibilities. It should be in a
18: file named COPYING. Among other things, the copyright notice
19: and this notice must be preserved on all copies. */
20:
21:
22: /* This is the jump-optimization pass of the compiler.
23: It is run two or three times: once before cse, sometimes once after cse,
24: and once after reload (before final).
25:
26: jump_optimize deletes unreachable code and labels that are not used.
27: It also deletes jumps that jump to the following insn,
28: and simplifies jumps around unconditional jumps and jumps
29: to unconditional jumps.
30:
31: Each CODE_LABEL has a count of the times it is used
32: stored in the LABEL_NUSES internal field, and each JUMP_INSN
33: has one label that it refers to stored in the
34: JUMP_LABEL internal field. With this we can detect labels that
35: become unused because of the deletion of all the jumps that
36: formerly used them. The JUMP_LABEL info is sometimes looked
37: at by later passes.
38:
39: Optionally, cross-jumping can be done. Currently it is done
40: only the last time (when after reload and before final).
41: In fact, the code for cross-jumping now assumes that register
42: allocation has been done, since it uses `rtx_renumbered_equal_p'.
43:
44: Jump optimization is done after cse when cse's constant-propagation
45: causes jumps to become unconditional or to be deleted.
46:
47: Unreachable loops are not detected here, because the labels
48: have references and the insns appear reachable from the labels.
49: find_basic_blocks in flow.c finds and deletes such loops.
50:
51: The subroutines delete_insn, redirect_jump, invert_jump, next_real_insn
52: and prev_real_insn are used from other passes as well. */
53:
54: #include "config.h"
55: #include "rtl.h"
56: #include "flags.h"
57: #include "regs.h"
58:
59: /* ??? Eventually must record somehow the labels used by jumps
60: from nested functions. */
61: /* Pre-record the next or previous real insn for each label?
62: No, this pass is very fast anyway. */
63: /* Condense consecutive labels?
64: This would make life analysis faster, maybe. */
65: /* Optimize jump y; x: ... y: jumpif... x?
66: Don't know if it is worth bothering with. */
67: /* Optimize two cases of conditional jump to conditional jump?
68: This can never delete any instruction or make anything dead,
69: or even change what is live at any point.
70: So perhaps let combiner do it. */
71:
72: /* Vector indexed by uid.
73: For each CODE_LABEL, index by its uid to get first unconditional jump
74: that jumps to the label.
75: For each JUMP_INSN, index by its uid to get the next unconditional jump
76: that jumps to the same label.
77: Element 0 is the start of a chain of all return insns.
78: (It is safe to use element 0 because insn uid 0 is not used. */
79:
80: rtx *jump_chain;
81:
82: rtx delete_insn ();
83: void redirect_jump ();
84: void invert_jump ();
85: rtx next_real_insn ();
86: rtx prev_real_insn ();
87: rtx next_label ();
88:
89: static void mark_jump_label ();
90: static void delete_jump ();
91: static void invert_exp ();
92: static void redirect_exp ();
93: static rtx follow_jumps ();
94: static int tension_vector_labels ();
95: static void find_cross_jump ();
96: static void do_cross_jump ();
97: static enum rtx_code reverse_condition ();
98: static int jump_back_p ();
99:
100: /* Delete no-op jumps and optimize jumps to jumps
101: and jumps around jumps.
102: Delete unused labels and unreachable code.
103: If CROSS_JUMP is nonzero, detect matching code
104: before a jump and its destination and unify them.
105: If NOOP_MOVES is nonzero, also delete no-op move insns
106: and perform machine-specific peephole optimizations
107: (but flag_no_peephole inhibits the latter).
108:
109: If `optimize' is zero, don't change any code,
110: just determine whether control drops off the end of the function.
111: This case occurs when we have -W and not -O.
112: It works because `delete_insn' checks the value of `optimize'
113: and refrains from actually deleting when that is 0. */
114:
115: void
116: jump_optimize (f, cross_jump, noop_moves)
117: rtx f;
118: {
119: register rtx insn;
120: int changed;
121: int first = 1;
122: int max_uid = 0;
123: rtx last_insn;
124:
125: /* Initialize LABEL_NUSES and JUMP_LABEL fields. */
126:
127: for (insn = f; insn; insn = NEXT_INSN (insn))
128: {
129: if (GET_CODE (insn) == CODE_LABEL)
130: LABEL_NUSES (insn) = 0;
131: if (GET_CODE (insn) == JUMP_INSN)
132: JUMP_LABEL (insn) = 0;
133: if (INSN_UID (insn) > max_uid)
134: max_uid = INSN_UID (insn);
135: }
136:
137: max_uid++;
138:
139: jump_chain = (rtx *) alloca (max_uid * sizeof (rtx));
140: bzero (jump_chain, max_uid * sizeof (rtx));
141:
142: /* Delete insns following barriers, up to next label. */
143:
144: for (insn = f; insn;)
145: {
146: if (GET_CODE (insn) == BARRIER)
147: {
148: insn = NEXT_INSN (insn);
149: while (insn != 0 && GET_CODE (insn) != CODE_LABEL)
150: {
151: if (GET_CODE (insn) == NOTE
152: && NOTE_LINE_NUMBER (insn) != NOTE_INSN_FUNCTION_END)
153: insn = NEXT_INSN (insn);
154: else
155: insn = delete_insn (insn);
156: }
157: /* INSN is now the code_label. */
158: }
159: else
160: insn = NEXT_INSN (insn);
161: }
162:
163: /* Mark the label each jump jumps to.
164: Combine consecutive labels, and count uses of labels.
165:
166: For each label, make a chain (using `jump_chain')
167: of all the *unconditional* jumps that jump to it;
168: also make a chain of all returns. */
169:
170: for (insn = f; insn; insn = NEXT_INSN (insn))
171: if (GET_CODE (insn) == JUMP_INSN && !insn->volatil)
172: {
173: mark_jump_label (PATTERN (insn), insn, cross_jump);
174: if (JUMP_LABEL (insn) != 0 && simplejump_p (insn))
175: {
176: jump_chain[INSN_UID (insn)]
177: = jump_chain[INSN_UID (JUMP_LABEL (insn))];
178: jump_chain[INSN_UID (JUMP_LABEL (insn))] = insn;
179: }
180: if (GET_CODE (PATTERN (insn)) == RETURN)
181: {
182: jump_chain[INSN_UID (insn)] = jump_chain[0];
183: jump_chain[0] = insn;
184: }
185: }
186:
187: /* Delete all labels already not referenced.
188: Also find the last insn. */
189:
190: last_insn = 0;
191: for (insn = f; insn; )
192: {
193: if (GET_CODE (insn) == CODE_LABEL && LABEL_NUSES (insn) == 0)
194: insn = delete_insn (insn);
195: else
196: {
197: last_insn = insn;
198: insn = NEXT_INSN (insn);
199: }
200: }
201:
202: if (!optimize)
203: {
204: /* See if there is still a NOTE_INSN_FUNCTION_END in this function.
205: If so record that this function can drop off the end. */
206:
207: insn = last_insn;
208: while (insn && (GET_CODE (insn) == CODE_LABEL
209: /* If machine uses explicit RETURN insns, no epilogue,
210: then this note precedes the drop-through RETURN. */
211: || (GET_CODE (insn) == JUMP_INSN
212: && GET_CODE (PATTERN (insn)) == RETURN)))
213: insn = PREV_INSN (insn);
214:
215: if (GET_CODE (insn) == NOTE
216: && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_END
217: && ! insn->volatil)
218: {
219: extern int current_function_returns_null;
220: current_function_returns_null = 1;
221: }
222: /* Zero the "deleted" flag of all the "deleted" insns. */
223: for (insn = f; insn; insn = NEXT_INSN (insn))
224: insn->volatil = 0;
225: return;
226: }
227:
228: #if 0
229: #ifdef EXIT_IGNORE_STACK
230: /* If the last insn just adjusts the stack,
231: we can delete it on certain machines,
232: provided we have a frame pointer. */
233:
234: if (frame_pointer_needed && EXIT_IGNORE_STACK)
235: {
236: insn = last_insn;
237: while (insn)
238: {
239: rtx prev;
240: /* Back up to a real insn. */
241: if (GET_CODE (insn) != INSN && GET_CODE (insn) != JUMP_INSN
242: && GET_CODE (insn) != CALL_INSN)
243: insn = prev_real_insn (insn);
244: if (insn == 0)
245: break;
246: prev = PREV_INSN (insn);
247: /* If this insn is a stack adjust, delete it. */
248: if (GET_CODE (insn) == INSN
249: && GET_CODE (PATTERN (insn)) == SET
250: && GET_CODE (SET_DEST (PATTERN (insn))) == REG
251: && REGNO (SET_DEST (PATTERN (insn))) == STACK_POINTER_REGNUM)
252: {
253: delete_insn (insn);
254: if (insn == last_insn)
255: last_insn = prev;
256: }
257: else
258: /* If we find an insn that isn't a stack adjust, stop deleting. */
259: break;
260: /* Back up to insn before the deleted one and try to delete more. */
261: insn = prev;
262: }
263: }
264: #endif
265: #endif
266:
267: if (noop_moves)
268: for (insn = f; insn; )
269: {
270: register rtx next = NEXT_INSN (insn);
271:
272: if (GET_CODE (insn) == INSN)
273: {
274: register rtx body = PATTERN (insn);
275:
276: /* Delete insns that existed just to advise flow-analysis. */
277:
278: if (GET_CODE (body) == USE
279: || GET_CODE (body) == CLOBBER)
280: delete_insn (insn);
281:
282: /* Detect and delete no-op move instructions
283: resulting from not allocating a parameter in a register. */
284:
285: else if (GET_CODE (body) == SET
286: && (SET_DEST (body) == SET_SRC (body)
287: || (GET_CODE (SET_DEST (body)) == MEM
288: && GET_CODE (SET_SRC (body)) == MEM
289: && rtx_equal_p (SET_SRC (body), SET_DEST (body))))
290: && ! SET_DEST (body)->volatil
291: && ! SET_SRC (body)->volatil)
292: delete_insn (insn);
293:
294: /* Detect and ignore no-op move instructions
295: resulting from smart or fortuitous register allocation. */
296:
297: else if (GET_CODE (body) == SET)
298: {
299: int sreg = true_regnum (SET_SRC (body));
300: int dreg = true_regnum (SET_DEST (body));
301:
302: if (sreg == dreg && sreg >= 0)
303: delete_insn (insn);
304: else if (sreg >= 0 && dreg >= 0)
305: {
306: rtx tem = find_equiv_reg (0, insn, 0,
307: sreg, 0, dreg);
308: if (tem != 0
309: && GET_MODE (tem) == GET_MODE (SET_DEST (body)))
310: delete_insn (insn);
311: }
312: }
313: }
314: insn = next;
315: }
316:
317: /* Now iterate optimizing jumps until nothing changes over one pass. */
318: changed = 1;
319: while (changed)
320: {
321: register rtx next;
322: changed = 0;
323:
324: for (insn = f; insn; insn = next)
325: {
326: next = NEXT_INSN (insn);
327:
328: /* On the first iteration, if this is the last jump pass
329: (just before final), do the special peephole optimizations. */
330:
331: if (noop_moves && first && !flag_no_peephole)
332: if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
333: peephole (insn);
334:
335: /* Tension the labels in dispatch tables. */
336:
337: if (GET_CODE (insn) == JUMP_INSN)
338: {
339: if (GET_CODE (PATTERN (insn)) == ADDR_VEC)
340: changed |= tension_vector_labels (PATTERN (insn), 0);
341: if (GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
342: changed |= tension_vector_labels (PATTERN (insn), 1);
343: }
344:
345: if (GET_CODE (insn) == JUMP_INSN && JUMP_LABEL (insn))
346: {
347: register rtx reallabelprev = prev_real_insn (JUMP_LABEL (insn));
348:
349: /* Delete insns that adjust stack pointer before a return,
350: if this is the last jump-optimization before final
351: and we need to have a frame pointer. */
352: #if 0
353: #ifdef EXIT_IGNORE_STACK
354: if (noop_moves && frame_pointer_needed && EXIT_IGNORE_STACK
355: && NEXT_INSN (JUMP_LABEL (insn)) == 0)
356: {
357: rtx prev = prev_real_insn (insn);
358: if (prev != 0
359: && GET_CODE (prev) == INSN
360: && GET_CODE (PATTERN (prev)) == SET
361: && GET_CODE (SET_DEST (PATTERN (prev))) == REG
362: && REGNO (SET_DEST (PATTERN (prev))) == STACK_POINTER_REGNUM)
363: {
364: delete_insn (prev);
365: changed = 1;
366: }
367: }
368: #endif
369: #endif
370:
371: /* Detect jump to following insn. */
372: if (reallabelprev == insn && condjump_p (insn))
373: {
374: reallabelprev = PREV_INSN (insn);
375: delete_jump (insn);
376: changed = 1;
377: }
378: /* Detect jumping over an unconditional jump. */
379: else if (reallabelprev != 0
380: && GET_CODE (reallabelprev) == JUMP_INSN
381: && prev_real_insn (reallabelprev) == insn
382: && no_labels_between_p (insn, reallabelprev)
383: && simplejump_p (reallabelprev)
384: /* Ignore this if INSN is a hairy kind of jump,
385: since they may not be invertible.
386: This is conservative; could instead construct
387: the inverted insn and try recognizing it. */
388: && condjump_p (insn))
389: {
390: /* Delete the original unconditional jump (and barrier). */
391: /* But don't lEST (PATTERN (insn))) == STACK_POINTER_REGNUM)
392: {
393: delete_insn (insn);
394: if (insn == last_insn)
395: last_insn = prev;
396: }
397: else
398: /* If we find an insn that isn't a stack adjust, stop deleting. */
399: break;
400: /* Back up to insn before the deleted one and try to delete more. */
401: insn = prev;
402: }
403: }
404: #endif
405: #endif
406:
407: if (noop_moves)
408: for (insn = f; insn; )
409: {
410: register rtx next = NEXT_INSN (insn);
411:
412: if (GET_CODE (insn) == INSN)
413: {
414: register rtx body = PATTERN (insn);
415:
416: /* Delete insns that existed just to advise flow-analysis. */
417:
418: if (GET_CODE (body) == USE
419: || GET_CODE (body) == CLOBBER)
420: delete_insn (insn);
421:
422: /* Detect and delete no-op move instructions
423: resulting from not allocating a parameter in a register. */
424:
425: else if (GET_CODE (body) == SET
426: && (SET_DEST (body) == SET_SRC (body)
427: || (GET_CODE (SET_DEST (body)) == MEM
428: && GET_CODE (SET_SRC (body)) == MEM
429: && rtx_equal_p (SET_SRC (body), SET_DEST (body))))
430: && ! SET_DEST (body)->volatil
431: && ! SET_SRC (body)->volatil)
432: delete_insn (insn);
433:
434: /* Detect and ignore no-op move instructions
435: resulting from smart or fortuitous register allocation. */
436:
437: else if (GET_CODE (body) == SET)
438: {
439: int sreg = true_regnum (SET_SRC (body));
440: int dreg = true_regnum (SET_DEST (body));
441:
442: if (sreg == dreg && sreg >= 0)
443: delete_insn (insn);
444: else if (sreg >= 0 && dreg >= 0)
445: {
446: rtx tem = find_equiv_reg (0, insn, 0,
447: sreg, 0, dreg);
448: if (tem != 0
449: && GET_MODE (tem) == GET_MODE (SET_DEST (body)))
450: delete_insn (insn);
451: }
452: }
453: }
454: insn = next;
455: }
456:
457: /* Now iterate optimizing jumps until nothing changes over one pass. */
458: changed = 1;
459: while (changed)
460: {
461: register rtx next;
462: changed = 0;
463:
464: for (insn = f; insn; insn = next)
465: {
466: next = NEXT_INSN (insn);
467:
468: /* On the first iteration, if this is the last jump pass
469: (just before final), do the special peephole optimizations. */
470:
471: if (noop_moves && first && !flag_no_peephole)
472: if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
473: peephole (insn);
474:
475: /* Tension the labels in dispatch tables. */
476:
477: if (GET_CODE (insn) == JUMP_INSN)
478: {
479: if (GET_CODE (PATTERN (insn)) == ADDR_VEC)
480: changed |= tension_vector_labels (PATTERN (insn), 0);
481: if (GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
482: changed |= tension_vector_labels (PATTERN (insn), 1);
483: }
484:
485: if (GET_CODE (insn) == JUMP_INSN && JUMP_LABEL (insn))
486: {
487: register rtx reallabelprev = prev_real_insn (JUMP_LABEL (insn));
488:
489: /* Delete insns that adjust stack pointer before a return,
490: if this is the last jump-optimization before final
491: and we need to have a frame pointer. */
492: #if 0
493: #ifdef EXIT_IGNORE_STACK
494: if (noop_moves && frame_pointer_needed && EXIT_IGNORE_STACK
495: && NEXT_INSN (JUMP_LABEL (insn)) == 0)
496: {
497: rtx prev = prev_real_insn (insn);
498: if (prev != 0
499: && GET_CODE (prev) == INSN
500: && GET_CODE (PATTERN (prev)) == SET
501: && GET_CODE (SET_DEST (PATTERN (prev))) == REG
502: && REGNO (SET_DEST (PATTERN (prev))) == STACK_POINTER_REGNUM)
503: {
504: delete_insn (prev);
505: changed = 1;
506: }
507: }
508: #endif
509: #endif
510:
511: /* Detect jump to following insn. */
512: if (reallabelprev == insn && condjump_p (insn))
513: {
514: reallabelprev = PREV_INSN (insn);
515: delete_jump (insn);
516: changed = 1;
517: }
518: /* Detect jumping over an unconditional jump. */
519: else if (reallabelprev != 0
520: && GET_CODE (reallabelprev) == JUMP_INSN
521: && prev_real_insn (reallabelprev) == insn
522: && no_labels_between_p (insn, reallabelprev)
523: && simplejump_p (reallabelprev)
524: /* Ignore this if INSN is a hairy kind of jump,
525: since they may not be invertible.
526: This is conservative; could instead construct
527: the inverted insn and try recognizing it. */
528: && condjump_p (insn))
529: {
530: /* Delete the original unconditional jump (and barrier). */
531: /* But don't l/* If cannot cross jump to code before the label,
532: see if we can cross jump to another jump to
533: the same label. */
534: /* Try each other jump to this label. */
535: if (INSN_UID (JUMP_LABEL (insn)) < max_uid)
536: for (target = jump_chain[INSN_UID (JUMP_LABEL (insn))];
537: target != 0 && newjpos == 0;
538: target = jump_chain[INSN_UID (target)])
539: if (target != insn
540: && JUMP_LABEL (target) == JUMP_LABEL (insn)
541: /* Ignore TARGET if it's deleted. */
542: && ! target->volatil)
543: find_cross_jump (insn, target, 2,
544: &newjpos, &newlpos);
545:
546: if (newjpos != 0)
547: {
548: do_cross_jump (insn, newjpos, newlpos);
549: changed = 1;
550: next = insn;
551: }
552: }
553: }
554: }
555: else if (GET_CODE (insn) == JUMP_INSN
556: && GET_CODE (PATTERN (insn)) == RETURN)
557: {
558: /* Return insns all "jump to the same place"
559: so we can cross-jump between any two of them. */
560: if (cross_jump)
561: {
562: rtx newjpos, newlpos, target;
563:
564: newjpos = 0;
565:
566: /* If cannot cross jump to code before the label,
567: see if we can cross jump to another jump to
568: the same label. */
569: /* Try each other jump to this label. */
570: for (target = jump_chain[0];
571: target != 0 && newjpos == 0;
572: target = jump_chain[INSN_UID (target)])
573: if (target != insn
574: && ! target->volatil
575: && GET_CODE (PATTERN (target)) == RETURN)
576: find_cross_jump (insn, target, 2,
577: &newjpos, &newlpos);
578:
579: if (newjpos != 0)
580: {
581: do_cross_jump (insn, newjpos, newlpos);
582: changed = 1;
583: next = insn;
584: }
585: }
586: }
587:
588: }
589:
590: first = 0;
591: }
592:
593: /* See if there is still a NOTE_INSN_FUNCTION_END in this function.
594: If so, delete it, and record that this function can drop off the end. */
595:
596: insn = last_insn;
597: while (insn && (GET_CODE (insn) == CODE_LABEL
598: /* If machine uses explicit RETURN insns, no epilogue,
599: then this note precedes the drop-through RETURN. */
600: || (GET_CODE (insn) == JUMP_INSN
601: && GET_CODE (PATTERN (insn)) == RETURN)))
602: insn = PREV_INSN (insn);
603: if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_END)
604: {
605: extern int current_function_returns_null;
606: current_function_returns_null = 1;
607: delete_insn (insn);
608: }
609: }
610:
611: /* Compare the instructions before insn E1 with those before E2.
612: Assume E1 is a jump that jumps to label E2
613: (that is not always true but it might as well be).
614: Find the longest possible equivalent sequences
615: and store the first insns of those sequences into *F1 and *F2.
616: Store zero there if no equivalent preceding instructions are found.
617:
618: We give up if we find a label in stream 1.
619: Actually we could transfer that label into stream 2. */
620:
621: static void
622: find_cross_jump (e1, e2, minimum, f1, f2)
623: rtx e1, e2;
624: int minimum;
625: rtx *f1, *f2;
626: {
627: register rtx i1 = e1, i2 = e2;
628: register rtx p1, p2;
629:
630: rtx last1 = 0, last2 = 0;
631: rtx afterlast1 = 0, afterlast2 = 0;
632:
633: *f1 = 0;
634: *f2 = 0;
635:
636: while (1)
637: {
638: i1 = PREV_INSN (i1);
639: while (i1 && GET_CODE (i1) == NOTE)
640: i1 = PREV_INSN (i1);
641:
642: i2 = PREV_INSN (i2);
643: while (i2 && (GET_CODE (i2) == NOTE || GET_CODE (i2) == CODE_LABEL))
644: i2 = PREV_INSN (i2);
645:
646: if (i1 == 0)
647: break;
648:
649: /* If we will get to this code by jumping, those jumps will be
650: tensioned to go directly to the new label (before I2),
651: so this cross-jumping won't cost extra. So reduce the minimum. */
652: if (GET_CODE (i1) == CODE_LABEL)
653: {
654: --minimum;
655: break;
656: }
657:
658: if (i2 == 0 || GET_CODE (i1) != GET_CODE (i2))
659: break;
660:
661: p1 = PATTERN (i1);
662: p2 = PATTERN (i2);
663:
664: if (GET_CODE (p1) != GET_CODE (p2)
665: || !rtx_renumbered_equal_p (p1, p2))
666: {
667: /* Insns fail to match; cross jumping is limited to the following
668: insns. */
669:
670: /* Don't allow the insn after a compare to be shared by cross-jumping
671: unless the compare is also shared.
672: Here, if either of these non-matching insns is a compare,
673: exclude the following insn from possible cross-jumping. */
674: if ((GET_CODE (p1) == SET && SET_DEST (p1) == cc0_rtx)
675: || (GET_CODE (p2) == SET && SET_DEST (p2) == cc0_rtx))
676: last1 = afterlast1, last2 = afterlast2, ++minimum;
677:
678: /* If cross-jumping here will feed a jump-around-jump optimization,
679: this jump won't cost extra, so reduce the minimum. */
680: if (GET_CODE (i1) == JUMP_INSN
681: && JUMP_LABEL (i1)
682: && prev_real_insn (JUMP_LABEL (i1)) == e1)
683: --minimum;
684: break;
685: }
686:
687: if (GET_CODE (p1) != USE && GET_CODE (p1) != CLOBBER)
688: {
689: /* Ok, this insn is potentially includable in a cross-jump here. */
690: afterlast1 = last1, afterlast2 = last2;
691: last1 = i1, last2 = i2, --minimum;
692: }
693: }
694:
695: if (minimum <= 0 && last1 != 0)
696: *f1 = last1, *f2 = last2;
697: }
698:
699: static void
700: do_cross_jump (insn, newjpos, newlpos)
701: rtx insn, newjpos, newlpos;
702: {
703: register rtx label;
704: /* Find an existing label at this point
705: or make a new one if there is none. */
706: label = PREV_INSN (newlpos);
707: if (GET_CODE (label) != CODE_LABEL)
708: {
709: label = gen_label_rtx ();
710: emit_label_after (label, PREV_INSN (newlpos));
711: LABEL_NUSES (label) = 0;
712: }
713: /* Make the same jump insn jump to the new point. */
714: if (GET_CODE (PATTERN (insn)) == RETURN)
715: {
716: extern rtx gen_jump ();
717: PATTERN (insn) = gen_jump (label);
718: INSN_CODE (insn) = -1;
719: JUMP_LABEL (insn) = label;
720: LABEL_NUSES (label)++;
721: }
722: else
723: redirect_jump (insn, label);
724: /* Delete the matching insns before the jump. */
725: newjpos = PREV_INSN (newjpos);
726: while (NEXT_INSN (newjpos) != insn)
727: /* Don't delete line numbers. */
728: if (GET_CODE (NEXT_INSN (newjpos)) != NOTE)
729: delete_insn (NEXT_INSN (newjpos));
730: else
731: newjpos = NEXT_INSN (newjpos);
732: }
733:
734: /* Return 1 if INSN is a jump that jumps to right after TARGET
735: only on the condition that TARGET itself would drop through.
736: Assumes that TARGET is a conditional jump. */
737:
738: static int
739: jump_back_p (insn, target)
740: rtx insn, target;
741: {
742: rtx cinsn, ctarget;
743: enum rtx_code codei, codet;
744:
745: if (simplejump_p (insn) || ! condjump_p (insn)
746: || simplejump_p (target))
747: return 0;
748: if (target != prev_real_insn (JUMP_LABEL (insn)))
749: return 0;
750:
751: cinsn = XEXP (SET_SRC (PATTERN (insn)), 0);
752: ctarget = XEXP (SET_SRC (PATTERN (target)), 0);
753:
754: codei = GET_CODE (cinsn);
755: codet = GET_CODE (ctarget);
756: if (XEXP (SET_SRC (PATTERN (insn)), 1) == pc_rtx)
757: codei = reverse_condition (codei);
758: if (XEXP (SET_SRC (PATTERN (target)), 2) == pc_rtx)
759: codet = reverse_condition (codet);
760: return (codei == codet
761: && rtx_renumbered_equal_p (XEXP (cinsn, 0), XEXP (ctarget, 0))
762: && rtx_renumbered_equal_p (XEXP (cinsn, 1), XEXP (ctarget, 1)));
763: }
764:
765: /* Given an rtx-code for a comparison, return the code
766: for the negated comparison. */
767:
768: static enum rtx_code
769: reverse_condition (code)
770: enum rtx_code code;
771: {
772: switch (code)
773: {
774: case EQ:
775: return NE;
776:
777: case NE:
778: return EQ;
779:
780: case GT:
781: return LE;
782:
783: case GE:
784: return LT;
785:
786: case LT:
787: return GE;
788:
789: case LE:
790: return GT;
791:
792: case GTU:
793: return LEU;
794:
795: case GEU:
796: return LTU;
797:
798: case LTU:
799: return GEU;
800:
801: case LEU:
802: return GTU;
803:
804: default:
805: abort ();
806: return UNKNOWN;
807: }
808: }
809:
810: /* Return 1 if INSN is an unconditional jump and nothing else. */
811:
812: int
813: simplejump_p (insn)
814: rtx insn;
815: {
816: register rtx x = PATTERN (insn);
817: if (GET_CODE (x) != SET)
818: return 0;
819: if (GET_CODE (SET_DEST (x)) != PC)
820: return 0;
821: if (GET_CODE (SET_SRC (x)) != LABEL_REF)
822: return 0;
823: return 1;
824: }
825:
826: /* Return nonzero if INSN is a (possibly) conditional jump
827: and nothing more. */
828:
829: static int
830: condjump_p (insn)
831: rtx insn;
832: {
833: register rtx x = PATTERN (insn);
834: if (GET_CODE (x) != SET)
835: return 0;
836: if (GET_CODE (SET_DEST (x)) != PC)
837: return 0;
838: if (GET_CODE (SET_SRC (x)) == LABEL_REF)
839: return 1;
840: if (GET_CODE (SET_SRC (x)) != IF_THEN_ELSE)
841: return 0;
842: if (XEXP (SET_SRC (x), 2) == pc_rtx
843: && GET_CODE (XEXP (SET_SRC (x), 1)) == LABEL_REF)
844: return 1;
845: if (XEXP (SET_SRC (x), 1) == pc_rtx
846: && GET_CODE (XEXP (SET_SRC (x), 2)) == LABEL_REF)
847: return 1;
848: return 0;
849: }
850:
851: /* Return 1 if in between BEG and END there is no CODE_LABEL insn. */
852:
853: int
854: no_labels_between_p (beg, end)
855: rtx beg, end;
856: {
857: register rtx p;
858: for (p = beg; p != end; p = NEXT_INSN (p))
859: if (GET_CODE (p) == CODE_LABEL)
860: return 0;
861: return 1;
862: }
863:
864: /* Return the last INSN, CALL_INSN or JUMP_INSN before LABEL;
865: or 0, if there is none. */
866:
867: rtx
868: prev_real_insn (label)
869: rtx label;
870: {
871: register rtx insn = PREV_INSN (label);
872: register RTX_CODE code;
873:
874: while (1)
875: {
876: if (insn == 0)
877: return 0;
878: code = GET_CODE (insn);
879: if (code == INSN || code == CALL_INSN || code == JUMP_INSN)
880: break;
881: insn = PREV_INSN (insn);
882: }
883:
884: return insn;
885: }
886:
887: /* Return the next INSN, CALL_INSN or JUMP_INSN after LABEL;
888: or 0, if there is none. */
889:
890: rtx
891: next_real_insn (label)
892: rtx label;
893: {
894: register rtx insn = NEXT_INSN (label);
895: register RTX_CODE code;
896:
897: while (1)
898: {
899: if (insn == 0)
900: return insn;
901: code = GET_CODE (insn);
902: if (code == INSN || code == CALL_INSN || code == JUMP_INSN)
903: break;
904: insn = NEXT_INSN (insn);
905: }
906:
907: return insn;
908: }
909:
910: /* Return the next CODE_LABEL after the insn INSN, or 0 if there is none. */
911:
912: rtx
913: next_label (insn)
914: rtx insn;
915: {
916: do insn = NEXT_INSN (insn);
917: while (insn != 0 && GET_CODE (insn) != CODE_LABEL);
918: return insn;
919: }
920:
921: /* Follow any unconditional jump at LABEL;
922: return the ultimate label reached by any such chain of jumps.
923: If LABEL is not followed by a jump, return LABEL. */
924:
925: static rtx
926: follow_jumps (label)
927: rtx label;
928: {
929: register rtx insn;
930: register rtx next;
931: register rtx value = label;
932: register int depth;
933:
934: for (depth = 0;
935: (depth < 10
936: && (insn = next_real_insn (value)) != 0
937: && GET_CODE (insn) == JUMP_INSN
938: && JUMP_LABEL (insn) != 0
939: && (next = NEXT_INSN (insn))
940: && GET_CODE (next) == BARRIER);
941: depth++)
942: {
943: /* If we have found a cycle, make the insn jump to itself. */
944: if (JUMP_LABEL (insn) == label)
945: break;
946: value = JUMP_LABEL (insn);
947: }
948: return value;
949: }
950:
951: /* Assuming that field IDX of X is a vector of label_refs,
952: replace each of them by the ultimate label reached by it.
953: Return nonzero if a change is made. */
954:
955: static int
956: tension_vector_labels (x, idx)
957: register rtx x;
958: register int idx;
959: {
960: int changed = 0;
961: register int i;
962: for (i = XVECLEN (x, idx) - 1; i >= 0; i--)
963: {
964: register rtx olabel = XEXP (XVECEXP (x, idx, i), 0);
965: register rtx nlabel = follow_jumps (olabel);
966: if (nlabel != olabel)
967: {
968: XEXP (XVECEXP (x, idx, i), 0) = nlabel;
969: ++LABEL_NUSES (nlabel);
970: if (--LABEL_NUSES (olabel) == 0)
971: delete_insn (olabel);
972: changed = 1;
973: }
974: }
975: return changed;
976: }
977:
978: /* Find all CODE_LABELs referred to in X,
979: and increment their use counts.
980: Also store one of them in JUMP_LABEL (INSN) if INSN is nonzero.
981: Also, when there are consecutive labels,
982: canonicalize on the last of them.
983:
984: Note that two labels separated by a loop-beginning note
985: must be kept distinct if we have not yet done loop-optimization,
986: because the gap between them is where loop-optimize
987: will want to move invariant code to. CROSS_JUMP tells us
988: that loop-optimization is done with. */
989:
990: static void
991: mark_jump_label (x, insn, cross_jump)
992: register rtx x;
993: rtx insn;
994: int cross_jump;
995: {
996: register RTX_CODE code = GET_CODE (x);
997: register int i;
998: register char *fmt;
999:
1000: if (code == LABEL_REF)
1001: {
1002: register rtx label = XEXP (x, 0);
1003: register rtx next;
1004: if (GET_CODE (label) != CODE_LABEL)
1005: return;
1006: /* If there are other labels following this one,
1007: replace it with the last of the consecutive labels. */
1008: for (next = NEXT_INSN (label); next; next = NEXT_INSN (next))
1009: {
1010: if (GET_CODE (next) == CODE_LABEL)
1011: label = next;
1012: else if (GET_CODE (next) != NOTE
1013: || NOTE_LINE_NUMBER (next) == NOTE_INSN_LOOP_BEG
1014: || NOTE_LINE_NUMBER (next) == NOTE_INSN_FUNCTION_END)
1015: break;
1016: }
1017: XEXP (x, 0) = label;
1018: ++LABEL_NUSES (label);
1019: if (insn)
1020: JUMP_LABEL (insn) = label;
1021: return;
1022: }
1023:
1024: /* Do walk the labels in a vector,
1025: but don't set its JUMP_LABEL. */
1026: if (code == ADDR_VEC || code == ADDR_DIFF_VEC)
1027: insn = 0;
1028:
1029: fmt = GET_RTX_FORMAT (code);
1030: for (i = GET_RTX_LENGTH (code); i >= 0; i--)
1031: {
1032: if (fmt[i] == 'e')
1033: mark_jump_label (XEXP (x, i), insn, cross_jump);
1034: else if (fmt[i] == 'E')
1035: {
1036: register int j;
1037: for (j = 0; j < XVECLEN (x, i); j++)
1038: mark_jump_label (XVECEXP (x, i, j), insn, cross_jump);
1039: }
1040: }
1041: }
1042:
1043: /* If all INSN does is set the pc, delete it,
1044: and delete the insn that set the condition codes for it
1045: if that's what the previous thing was. */
1046:
1047: static void
1048: delete_jump (insn)
1049: rtx insn;
1050: {
1051: register rtx x = PATTERN (insn);
1052: register rtx prev;
1053:
1054: if (GET_CODE (x) == SET
1055: && GET_CODE (SET_DEST (x)) == PC)
1056: {
1057: prev = PREV_INSN (insn);
1058: delete_insn (insn);
1059: /* We assume that at this stage
1060: CC's are always set explicitly
1061: and always immediately before the jump that
1062: will use them. So if the previous insn
1063: exists to set the CC's, delete it. */
1064: while (prev && GET_CODE (prev) == NOTE)
1065: prev = PREV_INSN (prev);
1066: if (prev && GET_CODE (prev) == INSN
1067: && GET_CODE (PATTERN (prev)) == SET
1068: && SET_DEST (PATTERN (prev)) == cc0_rtx)
1069: delete_insn (prev);
1070: }
1071: }
1072:
1073: /* Delete insn INSN from the chain of insns and update label ref counts.
1074: May delete some following insns as a consequence; may even delete
1075: a label elsewhere and insns that follow it.
1076:
1077: Returns the first insn after INSN that was not deleted. */
1078:
1079: rtx
1080: delete_insn (insn)
1081: register rtx insn;
1082: {
1083: register rtx next = NEXT_INSN (insn);
1084: register rtx prev = PREV_INSN (insn);
1085:
1086: if (insn->volatil)
1087: {
1088: /* This insn is already deleted => return first following nondeleted. */
1089: while (next && next->volatil)
1090: next = NEXT_INSN (next);
1091: return next;
1092: }
1093:
1094: /* Mark this insn as deleted. */
1095:
1096: insn->volatil = 1;
1097:
1098: /* If instruction is followed by a barrier,
1099: delete the barrier too. */
1100:
1101: if (next != 0 && GET_CODE (next) == BARRIER)
1102: {
1103: next->volatil = 1;
1104: next = NEXT_INSN (next);
1105: }
1106:
1107: /* Patch out INSN (and the barrier if any) */
1108:
1109: if (optimize)
1110: {
1111: if (prev)
1112: NEXT_INSN (prev) = next;
1113:
1114: if (next)
1115: PREV_INSN (next)= prev;
1116: }
1117:
1118: /* If deleting a jump, decrement the count of the label,
1119: and delete the label if it is now unused. */
1120:
1121: if (GET_CODE (insn) == JUMP_INSN && JUMP_LABEL (insn))
1122: if (--LABEL_NUSES (JUMP_LABEL (insn)) == 0)
1123: {
1124: /* This can delete NEXT or PREV,
1125: either directly if NEXT is JUMP_LABEL (INSN),
1126: or indirectly through more levels of jumps. */
1127: delete_insn (JUMP_LABEL (insn));
1128: /* I feel a little doubtful about this loop,
1129: but I see no clean and sure alternative way
1130: to find the first insn after INSN that is not now deleted.
1131: I hope this works. */
1132: while (next && next->volatil)
1133: next = NEXT_INSN (next);
1134: return next;
1135: }
1136:
1137: while (prev && GET_CODE (prev) == NOTE)
1138: prev = PREV_INSN (prev);
1139:
1140: /* If INSN was a label, delete insns following it if now unreachable. */
1141:
1142: if (GET_CODE (insn) == CODE_LABEL && prev
1143: && GET_CODE (prev) == BARRIER)
1144: {
1145: register RTX_CODE code;
1146: while (next != 0
1147: && ((code = GET_CODE (next)) == INSN
1148: || code == JUMP_INSN || code == CALL_INSN
1149: || code == NOTE))
1150: {
1151: if (code == NOTE
1152: && NOTE_LINE_NUMBER (next) != NOTE_INSN_FUNCTION_END)
1153: next = NEXT_INSN (next);
1154: else
1155: /* Note: if this deletes a jump, it can cause more
1156: deletion of unreachable code, after a different label.
1157: As long as the value from this recursive call is correct,
1158: this invocation functions correctly. */
1159: next = delete_insn (next);
1160: }
1161: }
1162:
1163: return next;
1164: }
1165:
1166: /* Advance from INSN till reaching something not deleted
1167: then return that. May return INSN itself. */
1168:
1169: rtx
1170: next_nondeleted_insn (insn)
1171: rtx insn;
1172: {
1173: while (insn->volatil)
1174: insn = NEXT_INSN (insn);
1175: return insn;
1176: }
1177:
1178: /* Invert the condition of the jump JUMP, and make it jump
1179: to label NLABEL instead of where it jumps now. */
1180:
1181: void
1182: invert_jump (jump, nlabel)
1183: rtx jump, nlabel;
1184: {
1185: register rtx olabel = JUMP_LABEL (jump);
1186: invert_exp (PATTERN (jump), olabel, nlabel);
1187: JUMP_LABEL (jump) = nlabel;
1188: ++LABEL_NUSES (nlabel);
1189: INSN_CODE (jump) = -1;
1190:
1191: if (--LABEL_NUSES (olabel) == 0)
1192: delete_insn (olabel);
1193: }
1194:
1195: /* Invert the jump condition of rtx X,
1196: and replace OLABEL with NLABEL throughout. */
1197:
1198: static void
1199: invert_exp (x, olabel, nlabel)
1200: rtx x;
1201: rtx olabel, nlabel;
1202: {
1203: register RTX_CODE code = GET_CODE (x);
1204: register int i;
1205: register char *fmt;
1206:
1207: if (code == IF_THEN_ELSE)
1208: {
1209: /* Inverting the jump condition of an IF_THEN_ELSE
1210: means exchanging the THEN-part with the ELSE-part. */
1211: register rtx tem = XEXP (x, 1);
1212: XEXP (x, 1) = XEXP (x, 2);
1213: XEXP (x, 2) = tem;
1214: }
1215:
1216: if (code == LABEL_REF)
1217: {
1218: if (XEXP (x, 0) == olabel)
1219: XEXP (x, 0) = nlabel;
1220: return;
1221: }
1222:
1223: fmt = GET_RTX_FORMAT (code);
1224: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1225: {
1226: if (fmt[i] == 'e')
1227: invert_exp (XEXP (x, i), olabel, nlabel);
1228: if (fmt[i] == 'E')
1229: {
1230: register int j;
1231: for (j = 0; j < XVECLEN (x, i); j++)
1232: invert_exp (XVECEXP (x, i, j), olabel, nlabel);
1233: }
1234: }
1235: }
1236:
1237: /* Make jump JUMP jump to label NLABEL instead of where it jumps now.
1238: If the old jump target label is unused as a result,
1239: it and the code following it may be deleted. */
1240:
1241: void
1242: redirect_jump (jump, nlabel)
1243: rtx jump, nlabel;
1244: {
1245: register rtx olabel = JUMP_LABEL (jump);
1246:
1247: if (nlabel == olabel)
1248: return;
1249:
1250: redirect_exp (PATTERN (jump), olabel, nlabel);
1251: JUMP_LABEL (jump) = nlabel;
1252: ++LABEL_NUSES (nlabel);
1253: INSN_CODE (jump) = -1;
1254:
1255: if (--LABEL_NUSES (olabel) == 0)
1256: delete_insn (olabel);
1257: }
1258:
1259: /* Throughout the rtx X,
1260: alter (LABEL_REF OLABEL) to (LABEL_REF NLABEL). */
1261:
1262: static void
1263: redirect_exp (x, olabel, nlabel)
1264: rtx x;
1265: rtx olabel, nlabel;
1266: {
1267: register RTX_CODE code = GET_CODE (x);
1268: register int i;
1269: register char *fmt;
1270:
1271: if (code == LABEL_REF)
1272: {
1273: if (XEXP (x, 0) == olabel)
1274: XEXP (x, 0) = nlabel;
1275: return;
1276: }
1277:
1278: fmt = GET_RTX_FORMAT (code);
1279: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1280: {
1281: if (fmt[i] == 'e')
1282: redirect_exp (XEXP (x, i), olabel, nlabel);
1283: if (fmt[i] == 'E')
1284: {
1285: register int j;
1286: for (j = 0; j < XVECLEN (x, i); j++)
1287: redirect_exp (XVECEXP (x, i, j), olabel, nlabel);
1288: }
1289: }
1290: }
1291:
1292: /* Like rtx_equal_p except that it considers two REGs as equal
1293: if they renumber to the same value. */
1294:
1295: int
1296: rtx_renumbered_equal_p (x, y)
1297: rtx x, y;
1298: {
1299: register int i;
1300: register RTX_CODE code = GET_CODE (x);
1301: register char *fmt;
1302:
1303: if (x == y)
1304: return 1;
1305: if ((code == REG || (code == SUBREG && GET_CODE (SUBREG_REG (x)) == REG))
1306: && (GET_CODE (y) == REG || (GET_CODE (y) == SUBREG
1307: && GET_CODE (SUBREG_REG (y)) == REG)))
1308: {
1309: register int j;
1310:
1311: if (GET_MODE (x) != GET_MODE (y))
1312: return 0;
1313:
1314: if (code == SUBREG)
1315: {
1316: i = REGNO (SUBREG_REG (x));
1317: if (reg_renumber[i] >= 0)
1318: i = reg_renumber[i];
1319: i += SUBREG_WORD (x);
1320: }
1321: else
1322: {
1323: i = REGNO (x);
1324: if (reg_renumber[i] >= 0)
1325: i = reg_renumber[i];
1326: }
1327: if (GET_CODE (y) == SUBREG)
1328: {
1329: j = REGNO (SUBREG_REG (y));
1330: if (reg_renumber[j] >= 0)
1331: j = reg_renumber[j];
1332: j += SUBREG_WORD (y);
1333: }
1334: else
1335: {
1336: j = REGNO (y);
1337: if (reg_renumber[j] >= 0)
1338: j = reg_renumber[j];
1339: }
1340: return i == j;
1341: }
1342: /* Now we have disposed of all the cases
1343: in which different rtx codes can match. */
1344: if (code != GET_CODE (y))
1345: return 0;
1346: /* Two label-refs are equivalent if they point at labels
1347: in the same position in the instruction stream. */
1348: if (code == LABEL_REF)
1349: return (next_real_insn (XEXP (x, 0))
1350: == next_real_insn (XEXP (y, 0)));
1351: if (code == SYMBOL_REF)
1352: return XSTR (x, 0) == XSTR (y, 0);
1353:
1354: /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. */
1355:
1356: if (GET_MODE (x) != GET_MODE (y))
1357: return 0;
1358:
1359: /* Compare the elements. If any pair of corresponding elements
1360: fail to match, return 0 for the whole things. */
1361:
1362: fmt = GET_RTX_FORMAT (code);
1363: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1364: {
1365: register int j;
1366: switch (fmt[i])
1367: {
1368: case 'i':
1369: if (XINT (x, i) != XINT (y, i))
1370: return 0;
1371: break;
1372:
1373: case 's':
1374: if (strcmp (XSTR (x, i), XSTR (y, i)))
1375: return 0;
1376: break;
1377:
1378: case 'e':
1379: if (! rtx_renumbered_equal_p (XEXP (x, i), XEXP (y, i)))
1380: return 0;
1381: break;
1382:
1383: case '0':
1384: break;
1385:
1386: case 'E':
1387: if (XVECLEN (x, i) != XVECLEN (y, i))
1388: return 0;
1389: for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1390: if (!rtx_renumbered_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)))
1391: return 0;
1392: break;
1393:
1394: /* It is believed that rtx's at this level will never
1395: contain anything but integers and other rtx's,
1396: except for within LABEL_REFs and SYMBOL_REFs. */
1397: default:
1398: abort ();
1399: }
1400: }
1401: return 1;
1402: }
1403:
1404: /* If X is a hard register or equivalent to one or a subregister of one,
1405: return the hard register number. Otherwise, return -1.
1406: Any rtx is valid for X. */
1407:
1408: int
1409: true_regnum (x)
1410: rtx x;
1411: {
1412: if (GET_CODE (x) == REG)
1413: {
1414: if (REGNO (x) >= FIRST_PSEUDO_REGISTER)
1415: return reg_renumber[REGNO (x)];
1416: return REGNO (x);
1417: }
1418: if (GET_CODE (x) == SUBREG)
1419: {
1420: int base = true_regnum (SUBREG_REG (x));
1421: if (base >= 0)
1422: return SUBREG_WORD (x) + base;
1423: }
1424: return -1;
1425: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.