1 /* Control flow optimization code for GNU compiler.
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
22 /* Try to match two basic blocks - or their ends - for structural equivalence.
23 We scan the blocks from their ends backwards, and expect that insns are
24 identical, except for certain cases involving registers. A mismatch
25 We scan the blocks from their ends backwards, hoping to find a match, I.e.
26 insns are identical, except for certain cases involving registers. A
27 mismatch between register number RX (used in block X) and RY (used in the
28 same way in block Y) can be handled in one of the following cases:
29 1. RX and RY are local to their respective blocks; they are set there and
30 die there. If so, they can effectively be ignored.
31 2. RX and RY die in their blocks, but live at the start. If any path
32 gets redirected through X instead of Y, the caller must emit
33 compensation code to move RY to RX. If there are overlapping inputs,
34 the function resolve_input_conflict ensures that this can be done.
35 Information about these registers are tracked in the X_LOCAL, Y_LOCAL,
36 LOCAL_COUNT and LOCAL_RVALUE fields.
37 3. RX and RY live throughout their blocks, including the start and the end.
38 Either RX and RY must be identical, or we have to replace all uses in
39 block X with a new pseudo, which is stored in the INPUT_REG field. The
40 caller can then use block X instead of block Y by copying RY to the new
43 The main entry point to this file is struct_equiv_block_eq. This function
44 uses a struct equiv_info to accept some of its inputs, to keep track of its
45 internal state, to pass down to its helper functions, and to communicate
46 some of the results back to the caller.
48 Most scans will result in a failure to match a sufficient number of insns
49 to make any optimization worth while, therefore the process is geared more
50 to quick scanning rather than the ability to exactly backtrack when we
51 find a mismatch. The information gathered is still meaningful to make a
52 preliminary decision if we want to do an optimization, we might only
53 slightly overestimate the number of matchable insns, and underestimate
54 the number of inputs an miss an input conflict. Sufficient information
55 is gathered so that when we make another pass, we won't have to backtrack
57 Another issue is that information in memory atttributes and/or REG_NOTES
58 might have to be merged or discarded to make a valid match. We don't want
59 to discard such information when we are not certain that we want to merge
60 the two (partial) blocks.
61 For these reasons, struct_equiv_block_eq has to be called first with the
62 STRUCT_EQUIV_START bit set in the mode parameter. This will calculate the
63 number of matched insns and the number and types of inputs. If the
64 need_rerun field is set, the results are only tentative, and the caller
65 has to call again with STRUCT_EQUIV_RERUN till need_rerun is false in
66 order to get a reliable match.
67 To install the changes necessary for the match, the function has to be
68 called again with STRUCT_EQUIV_FINAL.
70 While scanning an insn, we process first all the SET_DESTs, then the
71 SET_SRCes, then the REG_NOTES, in order to keep the register liveness
72 information consistent.
73 If we were to mix up the order for sources / destinations in an insn where
74 a source is also a destination, we'd end up being mistaken to think that
75 the register is not live in the preceding insn. */
79 #include "coretypes.h"
84 #include "insn-config.h"
92 static void merge_memattrs (rtx, rtx);
93 static bool set_dest_equiv_p (rtx x, rtx y, struct equiv_info *info);
94 static bool set_dest_addr_equiv_p (rtx x, rtx y, struct equiv_info *info);
95 static void find_dying_inputs (struct equiv_info *info);
96 static bool resolve_input_conflict (struct equiv_info *info);
98 /* After reload, some moves, as indicated by SECONDARY_RELOAD_CLASS and
99 SECONDARY_MEMORY_NEEDED, cannot be done directly. For our purposes, we
100 consider them impossible to generate after reload (even though some
101 might be synthesized when you throw enough code at them).
102 Since we don't know while procesing a cross-jump if a local register
103 that is currently live will eventually be live and thus be an input,
104 we keep track of potential inputs that would require an impossible move
105 by using a prohibitively high cost for them.
106 This number, multiplied with the larger of STRUCT_EQUIV_MAX_LOCAL and
107 FIRST_PSEUDO_REGISTER, must fit in the input_cost field of
108 struct equiv_info. */
109 #define IMPOSSIBLE_MOVE_FACTOR 20000
113 /* Removes the memory attributes of MEM expression
114 if they are not equal. */
117 merge_memattrs (rtx x, rtx y)
126 if (x == 0 || y == 0)
131 if (code != GET_CODE (y))
134 if (GET_MODE (x) != GET_MODE (y))
137 if (code == MEM && MEM_ATTRS (x) != MEM_ATTRS (y))
141 else if (! MEM_ATTRS (y))
147 if (MEM_ALIAS_SET (x) != MEM_ALIAS_SET (y))
149 set_mem_alias_set (x, 0);
150 set_mem_alias_set (y, 0);
153 if (! mem_expr_equal_p (MEM_EXPR (x), MEM_EXPR (y)))
157 set_mem_offset (x, 0);
158 set_mem_offset (y, 0);
160 else if (MEM_OFFSET (x) != MEM_OFFSET (y))
162 set_mem_offset (x, 0);
163 set_mem_offset (y, 0);
168 else if (!MEM_SIZE (y))
171 mem_size = GEN_INT (MAX (INTVAL (MEM_SIZE (x)),
172 INTVAL (MEM_SIZE (y))));
173 set_mem_size (x, mem_size);
174 set_mem_size (y, mem_size);
176 set_mem_align (x, MIN (MEM_ALIGN (x), MEM_ALIGN (y)));
177 set_mem_align (y, MEM_ALIGN (x));
181 fmt = GET_RTX_FORMAT (code);
182 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
187 /* Two vectors must have the same length. */
188 if (XVECLEN (x, i) != XVECLEN (y, i))
191 for (j = 0; j < XVECLEN (x, i); j++)
192 merge_memattrs (XVECEXP (x, i, j), XVECEXP (y, i, j));
197 merge_memattrs (XEXP (x, i), XEXP (y, i));
203 /* In SET, assign the bit for the register number of REG the value VALUE.
204 If REG is a hard register, do so for all its consituent registers.
205 Return the number of registers that have become included (as a positive
206 number) or excluded (as a negative number). */
208 assign_reg_reg_set (regset set, rtx reg, int value)
210 unsigned regno = REGNO (reg);
213 if (regno >= FIRST_PSEUDO_REGISTER)
215 gcc_assert (!reload_completed);
219 nregs = hard_regno_nregs[regno][GET_MODE (reg)];
220 for (old = 0, i = nregs; --i >= 0; regno++)
222 if ((value != 0) == REGNO_REG_SET_P (set, regno))
225 old++, SET_REGNO_REG_SET (set, regno);
227 old--, CLEAR_REGNO_REG_SET (set, regno);
232 /* Record state about current inputs / local registers / liveness
235 struct_equiv_make_checkpoint (struct struct_equiv_checkpoint *p,
236 struct equiv_info *info)
241 /* Call struct_equiv_make_checkpoint (P, INFO) if the current partial block
242 is suitable to split off - i.e. there is no dangling cc0 user - and
243 if the current cost of the common instructions, minus the cost for
244 setting up the inputs, is higher than what has been recorded before
245 in CHECKPOINT[N]. Also, if we do so, confirm or cancel any pending
248 struct_equiv_improve_checkpoint (struct struct_equiv_checkpoint *p,
249 struct equiv_info *info)
252 if (reg_mentioned_p (cc0_rtx, info->x_start) && !sets_cc0_p (info->x_start))
255 if (info->cur.input_count >= IMPOSSIBLE_MOVE_FACTOR)
257 if (info->input_cost >= 0
258 ? (COSTS_N_INSNS(info->cur.ninsns - p->ninsns)
259 > info->input_cost * (info->cur.input_count - p->input_count))
260 : info->cur.ninsns > p->ninsns && !info->cur.input_count)
262 if (info->check_input_conflict && ! resolve_input_conflict (info))
264 /* We have a profitable set of changes. If this is the final pass,
265 commit them now. Otherwise, we don't know yet if we can make any
266 change, so put the old code back for now. */
267 if (info->mode & STRUCT_EQUIV_FINAL)
268 confirm_change_group ();
271 struct_equiv_make_checkpoint (p, info);
275 /* Restore state about current inputs / local registers / liveness
278 struct_equiv_restore_checkpoint (struct struct_equiv_checkpoint *p,
279 struct equiv_info *info)
281 info->cur.ninsns = p->ninsns;
282 info->cur.x_start = p->x_start;
283 info->cur.y_start = p->y_start;
284 info->cur.input_count = p->input_count;
285 info->cur.input_valid = p->input_valid;
286 while (info->cur.local_count > p->local_count)
288 info->cur.local_count--;
290 if (REGNO_REG_SET_P (info->x_local_live,
291 REGNO (info->x_local[info->cur.local_count])))
293 assign_reg_reg_set (info->x_local_live,
294 info->x_local[info->cur.local_count], 0);
295 assign_reg_reg_set (info->y_local_live,
296 info->y_local[info->cur.local_count], 0);
300 if (info->cur.version != p->version)
301 info->need_rerun = true;
305 /* Update register liveness to reflect that X is now life (if rvalue is
306 nonzero) or dead (if rvalue is zero) in INFO->x_block, and likewise Y
307 in INFO->y_block. Return the number of registers the liveness of which
308 changed in each block (as a negative number if registers became dead). */
310 note_local_live (struct equiv_info *info, rtx x, rtx y, int rvalue)
312 int x_change = assign_reg_reg_set (info->x_local_live, x, rvalue);
313 int y_change = assign_reg_reg_set (info->y_local_live, y, rvalue);
315 gcc_assert (x_change == y_change);
318 if (reload_completed)
320 unsigned x_regno ATTRIBUTE_UNUSED = REGNO (x);
321 unsigned y_regno = REGNO (y);
322 enum machine_mode x_mode = GET_MODE (x);
324 if (secondary_reload_class (0, REGNO_REG_CLASS (y_regno), x_mode, x)
326 #ifdef SECONDARY_MEMORY_NEEDED
327 || SECONDARY_MEMORY_NEEDED (REGNO_REG_CLASS (y_regno),
328 REGNO_REG_CLASS (x_regno), x_mode)
331 y_change *= IMPOSSIBLE_MOVE_FACTOR;
333 info->cur.input_count += y_change;
339 /* Check if *XP is equivalent to Y. Until an an unreconcilable difference is
340 found, use in-group changes with validate_change on *XP to make register
341 assignments agree. It is the (not necessarily direct) callers
342 responsibility to verify / confirm / cancel these changes, as appropriate.
343 RVALUE indicates if the processed piece of rtl is used as a destination, in
344 which case we can't have different registers being an input. Returns
345 nonzero if the two blocks have been identified as equivalent, zero otherwise.
346 RVALUE == 0: destination
348 RVALUE == -1: source, ignore SET_DEST of SET / clobber. */
350 rtx_equiv_p (rtx *xp, rtx y, int rvalue, struct equiv_info *info)
361 if (code != REG && x == y)
363 if (GET_CODE (x) != code
364 || GET_MODE (x) != GET_MODE (y))
367 /* ??? could extend to allow CONST_INT inputs. */
371 gcc_assert (!reload_completed
372 || !info->live_update);
376 unsigned x_regno = REGNO (x);
377 unsigned y_regno = REGNO (y);
378 int x_common_live, y_common_live;
381 && (x_regno >= FIRST_PSEUDO_REGISTER
382 || y_regno >= FIRST_PSEUDO_REGISTER))
384 /* We should only see this in REG_NOTEs. */
385 gcc_assert (!info->live_update);
386 /* Returning false will cause us to remove the notes. */
390 /* After reg-stack, can only accept literal matches of stack regs. */
391 if (info->mode & CLEANUP_POST_REGSTACK
392 && (IN_RANGE (x_regno, FIRST_STACK_REG, LAST_STACK_REG)
393 || IN_RANGE (y_regno, FIRST_STACK_REG, LAST_STACK_REG)))
394 return x_regno == y_regno;
397 /* If the register is a locally live one in one block, the
398 corresponding one must be locally live in the other, too, and
399 match of identical regnos doesn't apply. */
400 if (REGNO_REG_SET_P (info->x_local_live, x_regno))
402 if (!REGNO_REG_SET_P (info->y_local_live, y_regno))
405 else if (REGNO_REG_SET_P (info->y_local_live, y_regno))
407 else if (x_regno == y_regno)
409 if (!rvalue && info->cur.input_valid
410 && (reg_overlap_mentioned_p (x, info->x_input)
411 || reg_overlap_mentioned_p (x, info->y_input)))
414 /* Update liveness information. */
415 if (info->live_update
416 && assign_reg_reg_set (info->common_live, x, rvalue))
422 x_common_live = REGNO_REG_SET_P (info->common_live, x_regno);
423 y_common_live = REGNO_REG_SET_P (info->common_live, y_regno);
424 if (x_common_live != y_common_live)
426 else if (x_common_live)
428 if (! rvalue || info->input_cost < 0 || no_new_pseudos)
430 /* If info->live_update is not set, we are processing notes.
431 We then allow a match with x_input / y_input found in a
433 if (info->live_update && !info->cur.input_valid)
435 info->cur.input_valid = true;
438 info->cur.input_count += optimize_size ? 2 : 1;
440 && GET_MODE (info->input_reg) != GET_MODE (info->x_input))
441 info->input_reg = NULL_RTX;
442 if (!info->input_reg)
443 info->input_reg = gen_reg_rtx (GET_MODE (info->x_input));
445 else if ((info->live_update
446 ? ! info->cur.input_valid : ! info->x_input)
447 || ! rtx_equal_p (x, info->x_input)
448 || ! rtx_equal_p (y, info->y_input))
450 validate_change (info->cur.x_start, xp, info->input_reg, 1);
454 int x_nregs = (x_regno >= FIRST_PSEUDO_REGISTER
455 ? 1 : hard_regno_nregs[x_regno][GET_MODE (x)]);
456 int y_nregs = (y_regno >= FIRST_PSEUDO_REGISTER
457 ? 1 : hard_regno_nregs[y_regno][GET_MODE (y)]);
458 int size = GET_MODE_SIZE (GET_MODE (x));
459 enum machine_mode x_mode = GET_MODE (x);
460 unsigned x_regno_i, y_regno_i;
461 int x_nregs_i, y_nregs_i, size_i;
462 int local_count = info->cur.local_count;
464 /* This might be a register local to each block. See if we have
465 it already registered. */
466 for (i = local_count - 1; i >= 0; i--)
468 x_regno_i = REGNO (info->x_local[i]);
469 x_nregs_i = (x_regno_i >= FIRST_PSEUDO_REGISTER
470 ? 1 : hard_regno_nregs[x_regno_i][GET_MODE (x)]);
471 y_regno_i = REGNO (info->y_local[i]);
472 y_nregs_i = (y_regno_i >= FIRST_PSEUDO_REGISTER
473 ? 1 : hard_regno_nregs[y_regno_i][GET_MODE (y)]);
474 size_i = GET_MODE_SIZE (GET_MODE (info->x_local[i]));
476 /* If we have a new pair of registers that is wider than an
477 old pair and enclosing it with matching offsets,
478 remove the old pair. If we find a matching, wider, old
479 pair, use the old one. If the width is the same, use the
480 old one if the modes match, but the new if they don't.
481 We don't want to get too fancy with subreg_regno_offset
482 here, so we just test two straightforwad cases each. */
483 if (info->live_update
484 && (x_mode != GET_MODE (info->x_local[i])
485 ? size >= size_i : size > size_i))
487 /* If the new pair is fully enclosing a matching
488 existing pair, remove the old one. N.B. because
489 we are removing one entry here, the check below
490 if we have space for a new entry will succeed. */
491 if ((x_regno <= x_regno_i
492 && x_regno + x_nregs >= x_regno_i + x_nregs_i
493 && x_nregs == y_nregs && x_nregs_i == y_nregs_i
494 && x_regno - x_regno_i == y_regno - y_regno_i)
495 || (x_regno == x_regno_i && y_regno == y_regno_i
496 && x_nregs >= x_nregs_i && y_nregs >= y_nregs_i))
498 info->cur.local_count = --local_count;
499 info->x_local[i] = info->x_local[local_count];
500 info->y_local[i] = info->y_local[local_count];
507 /* If the new pair is fully enclosed within a matching
508 existing pair, succeed. */
509 if (x_regno >= x_regno_i
510 && x_regno + x_nregs <= x_regno_i + x_nregs_i
511 && x_nregs == y_nregs && x_nregs_i == y_nregs_i
512 && x_regno - x_regno_i == y_regno - y_regno_i)
514 if (x_regno == x_regno_i && y_regno == y_regno_i
515 && x_nregs <= x_nregs_i && y_nregs <= y_nregs_i)
519 /* Any other overlap causes a match failure. */
520 if (x_regno + x_nregs > x_regno_i
521 && x_regno_i + x_nregs_i > x_regno)
523 if (y_regno + y_nregs > y_regno_i
524 && y_regno_i + y_nregs_i > y_regno)
529 /* Not found. Create a new entry if possible. */
530 if (!info->live_update
531 || info->cur.local_count >= STRUCT_EQUIV_MAX_LOCAL)
533 info->x_local[info->cur.local_count] = x;
534 info->y_local[info->cur.local_count] = y;
535 info->cur.local_count++;
538 note_local_live (info, x, y, rvalue);
543 gcc_assert (rvalue < 0);
544 /* Ignore the destinations role as a destination. Still, we have
545 to consider input registers embedded in the addresses of a MEM.
546 N.B., we process the rvalue aspect of STRICT_LOW_PART /
547 ZERO_EXTEND / SIGN_EXTEND along with their lvalue aspect. */
548 if(!set_dest_addr_equiv_p (SET_DEST (x), SET_DEST (y), info))
550 /* Process source. */
551 return rtx_equiv_p (&SET_SRC (x), SET_SRC (y), 1, info);
553 /* Process destination. */
554 if (!rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 0, info))
556 /* Process source. */
557 return rtx_equiv_p (&XEXP (x, 1), XEXP (y, 1), 1, info);
560 rtx x_dest0, x_dest1;
562 /* Process destination. */
563 x_dest0 = XEXP (x, 0);
564 gcc_assert (REG_P (x_dest0));
565 if (!rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 0, info))
567 x_dest1 = XEXP (x, 0);
568 /* validate_change might have changed the destination. Put it back
569 so that we can do a valid source match. */
570 XEXP (x, 0) = x_dest0;
571 if (!rtx_equiv_p (&XEXP (x, 1), XEXP (y, 1), 0, info))
573 gcc_assert (x_dest1 == XEXP (x, 0));
574 /* Process source. */
575 return rtx_equiv_p (&XEXP (x, 1), XEXP (y, 1), 1, info);
576 if (!rtx_equiv_p (&XEXP(x, 0), XEXP (y, 0), 0, info))
578 /* Process both subexpressions as inputs. */
582 gcc_assert (rvalue < 0);
584 /* Some special forms are also rvalues when they appear in lvalue
585 positions. However, we must ont try to match a register after we
586 have already altered it with validate_change, consider the rvalue
587 aspect while we process the lvalue. */
588 case STRICT_LOW_PART:
592 rtx x_inner, y_inner;
598 x_inner = XEXP (x, 0);
599 y_inner = XEXP (y, 0);
600 if (GET_MODE (x_inner) != GET_MODE (y_inner))
602 code = GET_CODE (x_inner);
603 if (code != GET_CODE (y_inner))
605 /* The address of a MEM is an input that will be processed during
606 rvalue == -1 processing. */
609 if (SUBREG_BYTE (x_inner) != SUBREG_BYTE (y_inner))
612 x_inner = SUBREG_REG (x_inner);
613 y_inner = SUBREG_REG (y_inner);
614 if (GET_MODE (x_inner) != GET_MODE (y_inner))
616 code = GET_CODE (x_inner);
617 if (code != GET_CODE (y_inner))
622 gcc_assert (code == REG);
623 if (! rtx_equiv_p (&XEXP (x, 0), y_inner, rvalue, info))
625 if (REGNO (x_inner) == REGNO (y_inner))
627 change = assign_reg_reg_set (info->common_live, x_inner, 1);
631 change = note_local_live (info, x_inner, y_inner, 1);
635 /* The AUTO_INC / POST_MODIFY / PRE_MODIFY sets are modelled to take
636 place during input processing, however, that is benign, since they
637 are paired with reads. */
639 return !rvalue || rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), rvalue, info);
640 case POST_INC: case POST_DEC: case PRE_INC: case PRE_DEC:
641 return (rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 0, info)
642 && rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 1, info));
644 gcc_assert (rvalue < 0);
647 /* Check special tablejump match case. */
648 if (XEXP (y, 0) == info->y_label)
649 return (XEXP (x, 0) == info->x_label);
650 /* We can't assume nonlocal labels have their following insns yet. */
651 if (LABEL_REF_NONLOCAL_P (x) || LABEL_REF_NONLOCAL_P (y))
652 return XEXP (x, 0) == XEXP (y, 0);
654 /* Two label-refs are equivalent if they point at labels
655 in the same position in the instruction stream. */
656 return (next_real_insn (XEXP (x, 0))
657 == next_real_insn (XEXP (y, 0)));
659 return XSTR (x, 0) == XSTR (y, 0);
660 /* Some rtl is guaranteed to be shared, or unique; If we didn't match
661 EQ equality above, they aren't the same. */
669 /* For commutative operations, the RTX match if the operands match in any
671 if (targetm.commutative_p (x, UNKNOWN))
672 return ((rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), rvalue, info)
673 && rtx_equiv_p (&XEXP (x, 1), XEXP (y, 1), rvalue, info))
674 || (rtx_equiv_p (&XEXP (x, 0), XEXP (y, 1), rvalue, info)
675 && rtx_equiv_p (&XEXP (x, 1), XEXP (y, 0), rvalue, info)));
677 /* Process subexpressions - this is similar to rtx_equal_p. */
678 length = GET_RTX_LENGTH (code);
679 format = GET_RTX_FORMAT (code);
681 for (i = 0; i < length; ++i)
686 if (XWINT (x, i) != XWINT (y, i))
691 if (XINT (x, i) != XINT (y, i))
696 if (XVECLEN (x, i) != XVECLEN (y, i))
698 if (XVEC (x, i) != 0)
701 for (j = 0; j < XVECLEN (x, i); ++j)
703 if (! rtx_equiv_p (&XVECEXP (x, i, j), XVECEXP (y, i, j),
710 if (! rtx_equiv_p (&XEXP (x, i), XEXP (y, i), rvalue, info))
715 if ((XSTR (x, i) || XSTR (y, i))
716 && (! XSTR (x, i) || ! XSTR (y, i)
717 || strcmp (XSTR (x, i), XSTR (y, i))))
721 /* These are just backpointers, so they don't matter. */
726 /* It is believed that rtx's at this level will never
727 contain anything but integers and other rtx's,
728 except for within LABEL_REFs and SYMBOL_REFs. */
736 /* Do only the rtx_equiv_p SET_DEST processing for SETs and CLOBBERs.
737 Since we are scanning backwards, this the first step in processing each
738 insn. Return true for success. */
740 set_dest_equiv_p (rtx x, rtx y, struct equiv_info *info)
744 if (GET_CODE (x) != GET_CODE (y))
746 else if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
747 return rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 0, info);
748 else if (GET_CODE (x) == PARALLEL)
752 if (XVECLEN (x, 0) != XVECLEN (y, 0))
754 for (j = 0; j < XVECLEN (x, 0); ++j)
756 rtx xe = XVECEXP (x, 0, j);
757 rtx ye = XVECEXP (y, 0, j);
759 if (GET_CODE (xe) != GET_CODE (ye))
761 if ((GET_CODE (xe) == SET || GET_CODE (xe) == CLOBBER)
762 && ! rtx_equiv_p (&XEXP (xe, 0), XEXP (ye, 0), 0, info))
769 /* Process MEMs in SET_DEST destinations. We must not process this together
770 with REG SET_DESTs, but must do it separately, lest when we see
771 [(set (reg:SI foo) (bar))
772 (set (mem:SI (reg:SI foo) (baz)))]
773 struct_equiv_block_eq could get confused to assume that (reg:SI foo)
774 is not live before this instruction. */
776 set_dest_addr_equiv_p (rtx x, rtx y, struct equiv_info *info)
778 enum rtx_code code = GET_CODE (x);
783 if (code != GET_CODE (y))
786 return rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 1, info);
788 /* Process subexpressions. */
789 length = GET_RTX_LENGTH (code);
790 format = GET_RTX_FORMAT (code);
792 for (i = 0; i < length; ++i)
798 if (XVECLEN (x, i) != XVECLEN (y, i))
800 if (XVEC (x, i) != 0)
803 for (j = 0; j < XVECLEN (x, i); ++j)
805 if (! set_dest_addr_equiv_p (XVECEXP (x, i, j),
806 XVECEXP (y, i, j), info))
812 if (! set_dest_addr_equiv_p (XEXP (x, i), XEXP (y, i), info))
822 /* Check if the set of REG_DEAD notes attached to I1 and I2 allows us to
823 go ahead with merging I1 and I2, which otherwise look fine.
824 Inputs / local registers for the inputs of I1 and I2 have already been
827 death_notes_match_p (rtx i1 ATTRIBUTE_UNUSED, rtx i2 ATTRIBUTE_UNUSED,
828 struct equiv_info *info ATTRIBUTE_UNUSED)
831 /* If cross_jump_death_matters is not 0, the insn's mode
832 indicates whether or not the insn contains any stack-like regs. */
834 if ((info->mode & CLEANUP_POST_REGSTACK) && stack_regs_mentioned (i1))
836 /* If register stack conversion has already been done, then
837 death notes must also be compared before it is certain that
838 the two instruction streams match. */
841 HARD_REG_SET i1_regset, i2_regset;
843 CLEAR_HARD_REG_SET (i1_regset);
844 CLEAR_HARD_REG_SET (i2_regset);
846 for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
847 if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
848 SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
850 for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
851 if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
853 unsigned regno = REGNO (XEXP (note, 0));
856 for (i = info->cur.local_count - 1; i >= 0; i--)
857 if (regno == REGNO (info->y_local[i]))
859 regno = REGNO (info->x_local[i]);
862 SET_HARD_REG_BIT (i2_regset, regno);
865 GO_IF_HARD_REG_EQUAL (i1_regset, i2_regset, done);
876 /* Return true if I1 and I2 are equivalent and thus can be crossjumped. */
879 insns_match_p (rtx i1, rtx i2, struct equiv_info *info)
881 int rvalue_change_start;
882 struct struct_equiv_checkpoint before_rvalue_change;
884 /* Verify that I1 and I2 are equivalent. */
885 if (GET_CODE (i1) != GET_CODE (i2))
888 info->cur.x_start = i1;
889 info->cur.y_start = i2;
891 /* If this is a CALL_INSN, compare register usage information.
892 If we don't check this on stack register machines, the two
893 CALL_INSNs might be merged leaving reg-stack.c with mismatching
894 numbers of stack registers in the same basic block.
895 If we don't check this on machines with delay slots, a delay slot may
896 be filled that clobbers a parameter expected by the subroutine.
898 ??? We take the simple route for now and assume that if they're
899 equal, they were constructed identically. */
903 if (SIBLING_CALL_P (i1) != SIBLING_CALL_P (i2)
904 || ! set_dest_equiv_p (PATTERN (i1), PATTERN (i2), info)
905 || ! set_dest_equiv_p (CALL_INSN_FUNCTION_USAGE (i1),
906 CALL_INSN_FUNCTION_USAGE (i2), info)
907 || ! rtx_equiv_p (&CALL_INSN_FUNCTION_USAGE (i1),
908 CALL_INSN_FUNCTION_USAGE (i2), -1, info))
914 else if (INSN_P (i1))
916 if (! set_dest_equiv_p (PATTERN (i1), PATTERN (i2), info))
922 rvalue_change_start = num_validated_changes ();
923 struct_equiv_make_checkpoint (&before_rvalue_change, info);
924 /* Check death_notes_match_p *after* the inputs have been processed,
925 so that local inputs will already have been set up. */
927 || (!bitmap_bit_p (info->equiv_used, info->cur.ninsns)
928 && rtx_equiv_p (&PATTERN (i1), PATTERN (i2), -1, info)
929 && death_notes_match_p (i1, i2, info)
930 && verify_changes (0)))
933 /* Do not do EQUIV substitution after reload. First, we're undoing the
934 work of reload_cse. Second, we may be undoing the work of the post-
935 reload splitting pass. */
936 /* ??? Possibly add a new phase switch variable that can be used by
937 targets to disallow the troublesome insns after splitting. */
938 if (!reload_completed)
942 cancel_changes (rvalue_change_start);
943 struct_equiv_restore_checkpoint (&before_rvalue_change, info);
945 /* The following code helps take care of G++ cleanups. */
946 equiv1 = find_reg_equal_equiv_note (i1);
947 equiv2 = find_reg_equal_equiv_note (i2);
949 /* If the equivalences are not to a constant, they may
950 reference pseudos that no longer exist, so we can't
952 && (! reload_completed
953 || (CONSTANT_P (XEXP (equiv1, 0))
954 && rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))))
956 rtx s1 = single_set (i1);
957 rtx s2 = single_set (i2);
959 if (s1 != 0 && s2 != 0)
961 validate_change (i1, &SET_SRC (s1), XEXP (equiv1, 0), 1);
962 validate_change (i2, &SET_SRC (s2), XEXP (equiv2, 0), 1);
963 /* Only inspecting the new SET_SRC is not good enough,
964 because there may also be bare USEs in a single_set
966 if (rtx_equiv_p (&PATTERN (i1), PATTERN (i2), -1, info)
967 && death_notes_match_p (i1, i2, info)
968 && verify_changes (0))
970 /* Mark this insn so that we'll use the equivalence in
971 all subsequent passes. */
972 bitmap_set_bit (info->equiv_used, info->cur.ninsns);
983 /* Set up mode and register information in INFO. Return true for success. */
985 struct_equiv_init (int mode, struct equiv_info *info)
987 if ((info->x_block->flags | info->y_block->flags) & BB_DIRTY)
988 update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
990 | ((mode & CLEANUP_POST_REGSTACK)
991 ? PROP_POST_REGSTACK : 0)));
992 if (!REG_SET_EQUAL_P (info->x_block->il.rtl->global_live_at_end,
993 info->y_block->il.rtl->global_live_at_end))
998 if (!(mode & CLEANUP_POST_REGSTACK))
1000 /* After reg-stack. Remove bogus live info about stack regs. N.B.
1001 these regs are not necessarily all dead - we swap random bogosity
1002 against constant bogosity. However, clearing these bits at
1003 least makes the regsets comparable. */
1004 for (rn = FIRST_STACK_REG; rn < LAST_STACK_REG; rn++)
1006 CLEAR_REGNO_REG_SET (info->x_block->il.rtl->global_live_at_end, rn);
1007 CLEAR_REGNO_REG_SET (info->y_block->il.rtl->global_live_at_end, rn);
1009 if (!REG_SET_EQUAL_P (info->x_block->il.rtl->global_live_at_end,
1010 info->y_block->il.rtl->global_live_at_end))
1015 if (mode & STRUCT_EQUIV_START)
1017 info->x_input = info->y_input = info->input_reg = NULL_RTX;
1018 info->equiv_used = ALLOC_REG_SET (®_obstack);
1019 info->check_input_conflict = false;
1021 info->had_input_conflict = false;
1022 info->cur.ninsns = info->cur.version = 0;
1023 info->cur.local_count = info->cur.input_count = 0;
1024 info->cur.x_start = info->cur.y_start = NULL_RTX;
1025 info->x_label = info->y_label = NULL_RTX;
1026 info->need_rerun = false;
1027 info->live_update = true;
1028 info->cur.input_valid = false;
1029 info->common_live = ALLOC_REG_SET (®_obstack);
1030 info->x_local_live = ALLOC_REG_SET (®_obstack);
1031 info->y_local_live = ALLOC_REG_SET (®_obstack);
1032 COPY_REG_SET (info->common_live, info->x_block->il.rtl->global_live_at_end);
1033 struct_equiv_make_checkpoint (&info->best_match, info);
1037 /* Insns XI and YI have been matched. Merge memory attributes and reg
1040 struct_equiv_merge (rtx xi, rtx yi, struct equiv_info *info)
1044 merge_memattrs (xi, yi);
1046 /* If the merged insns have different REG_EQUAL notes, then
1048 info->live_update = false;
1049 equiv1 = find_reg_equal_equiv_note (xi);
1050 equiv2 = find_reg_equal_equiv_note (yi);
1051 if (equiv1 && !equiv2)
1052 remove_note (xi, equiv1);
1053 else if (!equiv1 && equiv2)
1054 remove_note (yi, equiv2);
1055 else if (equiv1 && equiv2
1056 && !rtx_equiv_p (&XEXP (equiv1, 0), XEXP (equiv2, 0),
1059 remove_note (xi, equiv1);
1060 remove_note (yi, equiv2);
1062 info->live_update = true;
1065 /* Return number of matched insns.
1066 This function must be called up to three times for a successful cross-jump
1068 first to find out which instructions do match. While trying to match
1069 another instruction that doesn't match, we destroy information in info
1070 about the actual inputs. So if there have been any before the last
1071 match attempt, we need to call this function again to recompute the
1072 actual inputs up to the actual start of the matching sequence.
1073 When we are then satisfied that the cross-jump is worthwhile, we
1074 call this function a third time to make any changes needed to make the
1075 sequences match: apply equivalences, remove non-matching
1076 notes and merge memory attributes. */
1078 struct_equiv_block_eq (int mode, struct equiv_info *info)
1084 if (mode & STRUCT_EQUIV_START)
1086 x_stop = BB_HEAD (info->x_block);
1087 y_stop = BB_HEAD (info->y_block);
1088 if (!x_stop || !y_stop)
1093 x_stop = info->cur.x_start;
1094 y_stop = info->cur.y_start;
1096 if (!struct_equiv_init (mode, info))
1099 /* Skip simple jumps at the end of the blocks. Complex jumps still
1100 need to be compared for equivalence, which we'll do below. */
1102 xi = BB_END (info->x_block);
1104 || (returnjump_p (xi) && !side_effects_p (PATTERN (xi))))
1106 info->cur.x_start = xi;
1107 xi = PREV_INSN (xi);
1110 yi = BB_END (info->y_block);
1112 || (returnjump_p (yi) && !side_effects_p (PATTERN (yi))))
1114 info->cur.y_start = yi;
1115 /* Count everything except for unconditional jump as insn. */
1116 /* ??? Is it right to count unconditional jumps with a clobber?
1117 Should we count conditional returns? */
1118 if (!simplejump_p (yi) && !returnjump_p (yi) && info->cur.x_start)
1120 yi = PREV_INSN (yi);
1123 if (mode & STRUCT_EQUIV_MATCH_JUMPS)
1125 /* The caller is expected to have comapred the jumps already, but we
1126 need to match them again to get any local registers and inputs. */
1127 gcc_assert (!info->cur.x_start == !info->cur.y_start);
1128 if (info->cur.x_start)
1130 if (any_condjump_p (info->cur.x_start)
1131 ? !condjump_equiv_p (info, false)
1132 : !insns_match_p (info->cur.x_start, info->cur.y_start, info))
1135 else if (any_condjump_p (xi) && any_condjump_p (yi))
1137 info->cur.x_start = xi;
1138 info->cur.y_start = yi;
1139 xi = PREV_INSN (xi);
1140 yi = PREV_INSN (yi);
1142 if (!condjump_equiv_p (info, false))
1145 if (info->cur.x_start && info->mode & STRUCT_EQUIV_FINAL)
1146 struct_equiv_merge (info->cur.x_start, info->cur.y_start, info);
1149 struct_equiv_improve_checkpoint (&info->best_match, info);
1152 if (info->cur.x_start != x_stop)
1156 while (!INSN_P (xi) && xi != x_stop)
1157 xi = PREV_INSN (xi);
1159 while (!INSN_P (yi) && yi != y_stop)
1160 yi = PREV_INSN (yi);
1162 if (!insns_match_p (xi, yi, info))
1166 if (info->mode & STRUCT_EQUIV_FINAL)
1167 struct_equiv_merge (xi, yi, info);
1169 struct_equiv_improve_checkpoint (&info->best_match, info);
1171 if (xi == x_stop || yi == y_stop)
1173 /* If we reached the start of at least one of the blocks, but
1174 best_match hasn't been advanced back to the first valid insn
1175 yet, represent the increased benefit of completing the block
1176 as an increased instruction count. */
1177 if (info->best_match.x_start != info->cur.x_start
1178 && (xi == BB_HEAD (info->x_block)
1179 || yi == BB_HEAD (info->y_block)))
1182 struct_equiv_improve_checkpoint (&info->best_match, info);
1184 if (info->best_match.ninsns > info->cur.ninsns)
1185 info->best_match.ninsns = info->cur.ninsns;
1189 xi = PREV_INSN (xi);
1190 yi = PREV_INSN (yi);
1193 /* If we failed to match an insn, but had some changes registered from
1194 trying to make the insns match, we need to cancel these changes now. */
1196 /* Restore to best_match to get the sequence with the best known-so-far
1197 cost-benefit difference. */
1198 struct_equiv_restore_checkpoint (&info->best_match, info);
1200 /* Include preceding notes and labels in the cross-jump / if-conversion.
1201 One, this may bring us to the head of the blocks.
1202 Two, it keeps line number notes as matched as may be. */
1203 if (info->cur.ninsns)
1205 xi = info->cur.x_start;
1206 yi = info->cur.y_start;
1207 while (xi != x_stop && !INSN_P (PREV_INSN (xi)))
1208 xi = PREV_INSN (xi);
1210 while (yi != y_stop && !INSN_P (PREV_INSN (yi)))
1211 yi = PREV_INSN (yi);
1213 info->cur.x_start = xi;
1214 info->cur.y_start = yi;
1217 if (!info->cur.input_valid)
1218 info->x_input = info->y_input = info->input_reg = NULL_RTX;
1219 if (!info->need_rerun)
1221 find_dying_inputs (info);
1222 if (info->mode & STRUCT_EQUIV_FINAL)
1224 if (info->check_input_conflict && ! resolve_input_conflict (info))
1229 bool input_conflict = info->had_input_conflict;
1232 && info->dying_inputs > 1
1233 && bitmap_intersect_p (info->x_local_live, info->y_local_live))
1235 regset_head clobbered_regs;
1237 INIT_REG_SET (&clobbered_regs);
1238 for (i = 0; i < info->cur.local_count; i++)
1240 if (assign_reg_reg_set (&clobbered_regs, info->y_local[i], 0))
1242 input_conflict = true;
1245 assign_reg_reg_set (&clobbered_regs, info->x_local[i], 1);
1247 CLEAR_REG_SET (&clobbered_regs);
1249 if (input_conflict && !info->check_input_conflict)
1250 info->need_rerun = true;
1251 info->check_input_conflict = input_conflict;
1255 if (info->mode & STRUCT_EQUIV_NEED_FULL_BLOCK
1256 && (info->cur.x_start != x_stop || info->cur.y_start != y_stop))
1258 return info->cur.ninsns;
1261 /* For each local register, set info->local_rvalue to true iff the register
1262 is a dying input. Store the total number of these in info->dying_inputs. */
1264 find_dying_inputs (struct equiv_info *info)
1268 info->dying_inputs = 0;
1269 for (i = info->cur.local_count-1; i >=0; i--)
1271 rtx x = info->x_local[i];
1272 unsigned regno = REGNO (x);
1273 int nregs = (regno >= FIRST_PSEUDO_REGISTER
1274 ? 1 : hard_regno_nregs[regno][GET_MODE (x)]);
1276 for (info->local_rvalue[i] = false; nregs >= 0; regno++, --nregs)
1277 if (REGNO_REG_SET_P (info->x_local_live, regno))
1279 info->dying_inputs++;
1280 info->local_rvalue[i] = true;
1286 /* For each local register that is a dying input, y_local[i] will be
1287 copied to x_local[i]. We'll do this in ascending order. Try to
1288 re-order the locals to avoid conflicts like r3 = r2; r4 = r3; .
1289 Return true iff the re-ordering is successful, or not necessary. */
1291 resolve_input_conflict (struct equiv_info *info)
1295 rtx save_x_local[STRUCT_EQUIV_MAX_LOCAL];
1296 rtx save_y_local[STRUCT_EQUIV_MAX_LOCAL];
1298 find_dying_inputs (info);
1299 if (info->dying_inputs <= 1)
1301 memcpy (save_x_local, info->x_local, sizeof save_x_local);
1302 memcpy (save_y_local, info->y_local, sizeof save_y_local);
1303 end = info->cur.local_count - 1;
1304 for (i = 0; i <= end; i++)
1306 /* Cycle detection with regsets is expensive, so we just check that
1307 we don't exceed the maximum number of swaps needed in the acyclic
1309 int max_swaps = end - i;
1311 /* Check if x_local[i] will be clobbered. */
1312 if (!info->local_rvalue[i])
1314 /* Check if any later value needs to be copied earlier. */
1315 for (j = i + 1; j <= end; j++)
1319 if (!info->local_rvalue[j])
1321 if (!reg_overlap_mentioned_p (info->x_local[i], info->y_local[j]))
1323 if (--max_swaps < 0)
1325 memcpy (info->x_local, save_x_local, sizeof save_x_local);
1326 memcpy (info->y_local, save_y_local, sizeof save_y_local);
1330 tmp = info->x_local[i];
1331 info->x_local[i] = info->x_local[j];
1332 info->x_local[j] = tmp;
1333 tmp = info->y_local[i];
1334 info->y_local[i] = info->y_local[j];
1335 info->y_local[j] = tmp;
1339 info->had_input_conflict = true;
1340 if (dump_file && nswaps)
1341 fprintf (dump_file, "Resolved input conflict, %d %s.\n",
1342 nswaps, nswaps == 1 ? "swap" : "swaps");