]> gcc.gnu.org Git - gcc.git/blob - gcc/jump.c
git://gcc.gnu.org / gcc.git / blob
? search:


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