Fix ICE in lto_symtab_merge_symbols_1 (PR lto/88004).
[official-gcc.git] / gcc / compare-elim.c
blob8afbe76c502bdd0f3cd87c7191425f6229e6ba50
1 /* Post-reload compare elimination.
2 Copyright (C) 2010-2018 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
9 version.
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* There is a set of targets whose general-purpose move or addition
21 instructions clobber the flags. These targets cannot split their
22 CBRANCH/CSTORE etc patterns before reload is complete, lest reload
23 itself insert these instructions in between the flags setter and user.
24 Because these targets cannot split the compare from the use, they
25 cannot make use of the comparison elimination offered by the combine pass.
27 This is a small pass intended to provide comparison elimination similar to
28 what is available via NOTICE_UPDATE_CC for cc0 targets. This should help
29 encourage cc0 targets to convert to an explicit post-reload representation
30 of the flags.
32 This pass assumes:
34 (0) CBRANCH/CSTORE etc have been split in pass_split_after_reload.
36 (1) All comparison patterns are represented as
38 [(set (reg:CC) (compare:CC (reg) (reg_or_immediate)))]
40 (2) All insn patterns that modify the flags are represented as
42 [(set (reg) (operation)
43 (clobber (reg:CC))]
45 (3) If an insn of form (2) can usefully set the flags, there is
46 another pattern of the form
48 [(set (reg:CCM) (compare:CCM (operation) (immediate)))
49 (set (reg) (operation)]
51 The mode CCM will be chosen as if by SELECT_CC_MODE.
53 Note that unlike NOTICE_UPDATE_CC, we do not handle memory operands.
54 This could be handled as a future enhancement.
57 #include "config.h"
58 #include "system.h"
59 #include "coretypes.h"
60 #include "backend.h"
61 #include "target.h"
62 #include "rtl.h"
63 #include "df.h"
64 #include "memmodel.h"
65 #include "tm_p.h"
66 #include "insn-config.h"
67 #include "recog.h"
68 #include "emit-rtl.h"
69 #include "cfgrtl.h"
70 #include "tree-pass.h"
71 #include "domwalk.h"
74 /* These structures describe a comparison and how it is used. */
76 /* The choice of maximum 3 uses comes from wanting to eliminate the two
77 duplicate compares from a three-way branch on the sign of a value.
78 This is also sufficient to eliminate the duplicate compare against the
79 high-part of a double-word comparison. */
80 #define MAX_CMP_USE 3
82 struct comparison_use
84 /* The instruction in which the result of the compare is used. */
85 rtx_insn *insn;
86 /* The location of the flags register within the use. */
87 rtx *loc;
88 /* The comparison code applied against the flags register. */
89 enum rtx_code code;
92 struct comparison
94 /* The comparison instruction. */
95 rtx_insn *insn;
97 /* The insn prior to the comparison insn that clobbers the flags. */
98 rtx_insn *prev_clobber;
100 /* The insn prior to the comparison insn that sets in_a REG. */
101 rtx_insn *in_a_setter;
103 /* The two values being compared. These will be either REGs or
104 constants. */
105 rtx in_a, in_b;
107 /* The REG_EH_REGION of the comparison. */
108 rtx eh_note;
110 /* Information about how this comparison is used. */
111 struct comparison_use uses[MAX_CMP_USE];
113 /* The original CC_MODE for this comparison. */
114 machine_mode orig_mode;
116 /* The number of uses identified for this comparison. */
117 unsigned short n_uses;
119 /* True if not all uses of this comparison have been identified.
120 This can happen either for overflowing the array above, or if
121 the flags register is used in some unusual context. */
122 bool missing_uses;
124 /* True if its inputs are still valid at the end of the block. */
125 bool inputs_valid;
128 static vec<comparison *> all_compares;
130 /* Look for a "conforming" comparison, as defined above. If valid, return
131 the rtx for the COMPARE itself. */
133 static rtx
134 conforming_compare (rtx_insn *insn)
136 rtx set, src, dest;
138 set = single_set (insn);
139 if (set == NULL)
140 return NULL;
142 src = SET_SRC (set);
143 if (GET_CODE (src) != COMPARE)
144 return NULL;
146 dest = SET_DEST (set);
147 if (!REG_P (dest) || REGNO (dest) != targetm.flags_regnum)
148 return NULL;
150 if (!REG_P (XEXP (src, 0)))
151 return NULL;
153 if (CONSTANT_P (XEXP (src, 1)) || REG_P (XEXP (src, 1)))
154 return src;
156 if (GET_CODE (XEXP (src, 1)) == UNSPEC)
158 for (int i = 0; i < XVECLEN (XEXP (src, 1), 0); i++)
159 if (!REG_P (XVECEXP (XEXP (src, 1), 0, i)))
160 return NULL;
161 return src;
164 return NULL;
167 /* Look for a pattern of the "correct" form for an insn with a flags clobber
168 for which we may be able to eliminate a compare later. We're not looking
169 to validate any inputs at this time, merely see that the basic shape is
170 correct. The term "arithmetic" may be somewhat misleading... */
172 static bool
173 arithmetic_flags_clobber_p (rtx_insn *insn)
175 rtx pat, x;
177 if (!NONJUMP_INSN_P (insn))
178 return false;
179 pat = PATTERN (insn);
180 if (asm_noperands (pat) >= 0)
181 return false;
183 if (GET_CODE (pat) == PARALLEL && XVECLEN (pat, 0) == 2)
185 x = XVECEXP (pat, 0, 0);
186 if (GET_CODE (x) != SET)
187 return false;
188 x = SET_DEST (x);
189 if (!REG_P (x))
190 return false;
192 x = XVECEXP (pat, 0, 1);
193 if (GET_CODE (x) == CLOBBER)
195 x = XEXP (x, 0);
196 if (REG_P (x) && REGNO (x) == targetm.flags_regnum)
197 return true;
201 return false;
204 /* Look for uses of FLAGS in INSN. If we find one we can analyze, record
205 it in CMP; otherwise indicate that we've missed a use. */
207 static void
208 find_flags_uses_in_insn (struct comparison *cmp, rtx_insn *insn)
210 df_ref use;
212 /* If we've already lost track of uses, don't bother collecting more. */
213 if (cmp->missing_uses)
214 return;
216 /* Find a USE of the flags register. */
217 FOR_EACH_INSN_USE (use, insn)
218 if (DF_REF_REGNO (use) == targetm.flags_regnum)
220 rtx x, *loc;
222 /* If this is an unusual use, quit. */
223 if (DF_REF_TYPE (use) != DF_REF_REG_USE)
224 goto fail;
226 /* If we've run out of slots to record uses, quit. */
227 if (cmp->n_uses == MAX_CMP_USE)
228 goto fail;
230 /* Unfortunately the location of the flags register, while present
231 in the reference structure, doesn't help. We need to find the
232 comparison code that is outer to the actual flags use. */
233 loc = DF_REF_LOC (use);
234 x = PATTERN (insn);
235 if (GET_CODE (x) == PARALLEL)
236 x = XVECEXP (x, 0, 0);
237 x = SET_SRC (x);
238 if (GET_CODE (x) == IF_THEN_ELSE)
239 x = XEXP (x, 0);
240 if (COMPARISON_P (x)
241 && loc == &XEXP (x, 0)
242 && XEXP (x, 1) == const0_rtx)
244 /* We've found a use of the flags that we understand. */
245 struct comparison_use *cuse = &cmp->uses[cmp->n_uses++];
246 cuse->insn = insn;
247 cuse->loc = loc;
248 cuse->code = GET_CODE (x);
250 else
251 goto fail;
253 return;
255 fail:
256 /* We failed to recognize this use of the flags register. */
257 cmp->missing_uses = true;
260 class find_comparison_dom_walker : public dom_walker
262 public:
263 find_comparison_dom_walker (cdi_direction direction)
264 : dom_walker (direction) {}
266 virtual edge before_dom_children (basic_block);
269 /* Return true if conforming COMPARE with EH_NOTE is redundant with comparison
270 CMP and can thus be eliminated. */
272 static bool
273 can_eliminate_compare (rtx compare, rtx eh_note, struct comparison *cmp)
275 /* Take care that it's in the same EH region. */
276 if (cfun->can_throw_non_call_exceptions
277 && !rtx_equal_p (eh_note, cmp->eh_note))
278 return false;
280 /* Make sure the compare is redundant with the previous. */
281 if (!rtx_equal_p (XEXP (compare, 0), cmp->in_a)
282 || !rtx_equal_p (XEXP (compare, 1), cmp->in_b))
283 return false;
285 /* New mode must be compatible with the previous compare mode. */
286 machine_mode new_mode
287 = targetm.cc_modes_compatible (GET_MODE (compare), cmp->orig_mode);
289 if (new_mode == VOIDmode)
290 return false;
292 if (cmp->orig_mode != new_mode)
294 /* Generate new comparison for substitution. */
295 rtx flags = gen_rtx_REG (new_mode, targetm.flags_regnum);
296 rtx x = gen_rtx_COMPARE (new_mode, cmp->in_a, cmp->in_b);
297 x = gen_rtx_SET (flags, x);
299 if (!validate_change (cmp->insn, &PATTERN (cmp->insn), x, false))
300 return false;
302 cmp->orig_mode = new_mode;
305 return true;
308 /* Identify comparison instructions within BB. If the flags from the last
309 compare in the BB is live at the end of the block, install the compare
310 in BB->AUX. Called via dom_walker.walk (). */
312 edge
313 find_comparison_dom_walker::before_dom_children (basic_block bb)
315 rtx_insn *insn, *next;
316 bool need_purge = false;
317 rtx_insn *last_setter[FIRST_PSEUDO_REGISTER];
319 /* The last comparison that was made. Will be reset to NULL
320 once the flags are clobbered. */
321 struct comparison *last_cmp = NULL;
323 /* True iff the last comparison has not been clobbered, nor
324 have its inputs. Used to eliminate duplicate compares. */
325 bool last_cmp_valid = false;
327 /* The last insn that clobbered the flags, if that insn is of
328 a form that may be valid for eliminating a following compare.
329 To be reset to NULL once the flags are set otherwise. */
330 rtx_insn *last_clobber = NULL;
332 /* Propagate the last live comparison throughout the extended basic block. */
333 if (single_pred_p (bb))
335 last_cmp = (struct comparison *) single_pred (bb)->aux;
336 if (last_cmp)
337 last_cmp_valid = last_cmp->inputs_valid;
340 memset (last_setter, 0, sizeof (last_setter));
341 for (insn = BB_HEAD (bb); insn; insn = next)
343 rtx src;
345 next = (insn == BB_END (bb) ? NULL : NEXT_INSN (insn));
346 if (!NONDEBUG_INSN_P (insn))
347 continue;
349 src = conforming_compare (insn);
350 if (src)
352 rtx eh_note = NULL;
354 if (cfun->can_throw_non_call_exceptions)
355 eh_note = find_reg_note (insn, REG_EH_REGION, NULL);
357 if (last_cmp_valid && can_eliminate_compare (src, eh_note, last_cmp))
359 if (eh_note)
360 need_purge = true;
361 delete_insn (insn);
362 continue;
365 last_cmp = XCNEW (struct comparison);
366 last_cmp->insn = insn;
367 last_cmp->prev_clobber = last_clobber;
368 last_cmp->in_a = XEXP (src, 0);
369 last_cmp->in_b = XEXP (src, 1);
370 last_cmp->eh_note = eh_note;
371 last_cmp->orig_mode = GET_MODE (src);
372 if (last_cmp->in_b == const0_rtx
373 && last_setter[REGNO (last_cmp->in_a)])
375 rtx set = single_set (last_setter[REGNO (last_cmp->in_a)]);
376 if (set && rtx_equal_p (SET_DEST (set), last_cmp->in_a))
377 last_cmp->in_a_setter = last_setter[REGNO (last_cmp->in_a)];
379 all_compares.safe_push (last_cmp);
381 /* It's unusual, but be prepared for comparison patterns that
382 also clobber an input, or perhaps a scratch. */
383 last_clobber = NULL;
384 last_cmp_valid = true;
387 else
389 /* Notice if this instruction uses the flags register. */
390 if (last_cmp)
391 find_flags_uses_in_insn (last_cmp, insn);
393 /* Notice if this instruction kills the flags register. */
394 df_ref def;
395 FOR_EACH_INSN_DEF (def, insn)
396 if (DF_REF_REGNO (def) == targetm.flags_regnum)
398 /* See if this insn could be the "clobber" that eliminates
399 a future comparison. */
400 last_clobber = (arithmetic_flags_clobber_p (insn)
401 ? insn : NULL);
403 /* In either case, the previous compare is no longer valid. */
404 last_cmp = NULL;
405 last_cmp_valid = false;
406 break;
410 /* Notice if any of the inputs to the comparison have changed
411 and remember last insn that sets each register. */
412 df_ref def;
413 FOR_EACH_INSN_DEF (def, insn)
415 if (last_cmp_valid
416 && (DF_REF_REGNO (def) == REGNO (last_cmp->in_a)
417 || (REG_P (last_cmp->in_b)
418 && DF_REF_REGNO (def) == REGNO (last_cmp->in_b))))
419 last_cmp_valid = false;
420 last_setter[DF_REF_REGNO (def)] = insn;
424 /* Remember the live comparison for subsequent members of
425 the extended basic block. */
426 if (last_cmp)
428 bb->aux = last_cmp;
429 last_cmp->inputs_valid = last_cmp_valid;
431 /* Look to see if the flags register is live outgoing here, and
432 incoming to any successor not part of the extended basic block. */
433 if (bitmap_bit_p (df_get_live_out (bb), targetm.flags_regnum))
435 edge e;
436 edge_iterator ei;
438 FOR_EACH_EDGE (e, ei, bb->succs)
440 basic_block dest = e->dest;
441 if (bitmap_bit_p (df_get_live_in (bb), targetm.flags_regnum)
442 && !single_pred_p (dest))
444 last_cmp->missing_uses = true;
445 break;
451 /* If we deleted a compare with a REG_EH_REGION note, we may need to
452 remove EH edges. */
453 if (need_purge)
454 purge_dead_edges (bb);
456 return NULL;
459 /* Find all comparisons in the function. */
461 static void
462 find_comparisons (void)
464 calculate_dominance_info (CDI_DOMINATORS);
466 find_comparison_dom_walker (CDI_DOMINATORS)
467 .walk (cfun->cfg->x_entry_block_ptr);
469 clear_aux_for_blocks ();
470 free_dominance_info (CDI_DOMINATORS);
473 /* Select an alternate CC_MODE for a comparison insn comparing A and B.
474 Note that inputs are almost certainly different than the IN_A and IN_B
475 stored in CMP -- we're called while attempting to eliminate the compare
476 after all. Return the new FLAGS rtx if successful, else return NULL.
477 Note that this function may start a change group. */
479 static rtx
480 maybe_select_cc_mode (struct comparison *cmp, rtx a ATTRIBUTE_UNUSED,
481 rtx b ATTRIBUTE_UNUSED)
483 machine_mode sel_mode;
484 const int n = cmp->n_uses;
485 rtx flags = NULL;
487 #ifndef SELECT_CC_MODE
488 /* Minimize code differences when this target macro is undefined. */
489 return NULL;
490 #define SELECT_CC_MODE(A,B,C) (gcc_unreachable (), VOIDmode)
491 #endif
493 /* If we don't have access to all of the uses, we can't validate. */
494 if (cmp->missing_uses || n == 0)
495 return NULL;
497 /* Find a new mode that works for all of the uses. Special case the
498 common case of exactly one use. */
499 if (n == 1)
501 sel_mode = SELECT_CC_MODE (cmp->uses[0].code, a, b);
502 if (sel_mode != cmp->orig_mode)
504 flags = gen_rtx_REG (sel_mode, targetm.flags_regnum);
505 validate_change (cmp->uses[0].insn, cmp->uses[0].loc, flags, true);
508 else
510 int i;
512 sel_mode = SELECT_CC_MODE (cmp->uses[0].code, a, b);
513 for (i = 1; i < n; ++i)
515 machine_mode new_mode = SELECT_CC_MODE (cmp->uses[i].code, a, b);
516 if (new_mode != sel_mode)
518 sel_mode = targetm.cc_modes_compatible (sel_mode, new_mode);
519 if (sel_mode == VOIDmode)
520 return NULL;
524 if (sel_mode != cmp->orig_mode)
526 flags = gen_rtx_REG (sel_mode, targetm.flags_regnum);
527 for (i = 0; i < n; ++i)
528 validate_change (cmp->uses[i].insn, cmp->uses[i].loc, flags, true);
532 return flags;
535 /* Return a register RTX holding the same value at START as REG at END, or
536 NULL_RTX if there is none. */
538 static rtx
539 equivalent_reg_at_start (rtx reg, rtx_insn *end, rtx_insn *start)
541 machine_mode orig_mode = GET_MODE (reg);
542 rtx_insn *bb_head = BB_HEAD (BLOCK_FOR_INSN (end));
544 for (rtx_insn *insn = PREV_INSN (end);
545 insn != start;
546 insn = PREV_INSN (insn))
548 const int abnormal_flags
549 = (DF_REF_CONDITIONAL | DF_REF_PARTIAL | DF_REF_MAY_CLOBBER
550 | DF_REF_MUST_CLOBBER | DF_REF_SIGN_EXTRACT
551 | DF_REF_ZERO_EXTRACT | DF_REF_STRICT_LOW_PART
552 | DF_REF_PRE_POST_MODIFY);
553 df_ref def;
555 /* Note that the BB_HEAD is always either a note or a label, but in
556 any case it means that REG is defined outside the block. */
557 if (insn == bb_head)
558 return NULL_RTX;
559 if (NOTE_P (insn) || DEBUG_INSN_P (insn))
560 continue;
562 /* Find a possible def of REG in INSN. */
563 FOR_EACH_INSN_DEF (def, insn)
564 if (DF_REF_REGNO (def) == REGNO (reg))
565 break;
567 /* No definitions of REG; continue searching. */
568 if (def == NULL)
569 continue;
571 /* Bail if this is not a totally normal set of REG. */
572 if (DF_REF_IS_ARTIFICIAL (def))
573 return NULL_RTX;
574 if (DF_REF_FLAGS (def) & abnormal_flags)
575 return NULL_RTX;
577 /* We've found an insn between the compare and the clobber that sets
578 REG. Given that pass_cprop_hardreg has not yet run, we still find
579 situations in which we can usefully look through a copy insn. */
580 rtx x = single_set (insn);
581 if (x == NULL_RTX)
582 return NULL_RTX;
583 reg = SET_SRC (x);
584 if (!REG_P (reg))
585 return NULL_RTX;
588 if (GET_MODE (reg) != orig_mode)
589 return NULL_RTX;
591 return reg;
594 /* Return true if it is okay to merge the comparison CMP_INSN with
595 the instruction ARITH_INSN. Both instructions are assumed to be in the
596 same basic block with ARITH_INSN appearing before CMP_INSN. This checks
597 that there are no uses or defs of the condition flags or control flow
598 changes between the two instructions. */
600 static bool
601 can_merge_compare_into_arith (rtx_insn *cmp_insn, rtx_insn *arith_insn)
603 for (rtx_insn *insn = PREV_INSN (cmp_insn);
604 insn && insn != arith_insn;
605 insn = PREV_INSN (insn))
607 if (!NONDEBUG_INSN_P (insn))
608 continue;
609 /* Bail if there are jumps or calls in between. */
610 if (!NONJUMP_INSN_P (insn))
611 return false;
613 /* Bail on old-style asm statements because they lack
614 data flow information. */
615 if (GET_CODE (PATTERN (insn)) == ASM_INPUT)
616 return false;
618 df_ref ref;
619 /* Find a USE of the flags register. */
620 FOR_EACH_INSN_USE (ref, insn)
621 if (DF_REF_REGNO (ref) == targetm.flags_regnum)
622 return false;
624 /* Find a DEF of the flags register. */
625 FOR_EACH_INSN_DEF (ref, insn)
626 if (DF_REF_REGNO (ref) == targetm.flags_regnum)
627 return false;
629 return true;
632 /* Given two SET expressions, SET_A and SET_B determine whether they form
633 a recognizable pattern when emitted in parallel. Return that parallel
634 if so. Otherwise return NULL. */
636 static rtx
637 try_validate_parallel (rtx set_a, rtx set_b)
639 rtx par = gen_rtx_PARALLEL (VOIDmode, gen_rtvec (2, set_a, set_b));
640 rtx_insn *insn = make_insn_raw (par);
642 if (insn_invalid_p (insn, false))
644 crtl->emit.x_cur_insn_uid--;
645 return NULL_RTX;
648 SET_PREV_INSN (insn) = NULL_RTX;
649 SET_NEXT_INSN (insn) = NULL_RTX;
650 INSN_LOCATION (insn) = 0;
651 return insn;
654 /* For a comparison instruction described by CMP check if it compares a
655 register with zero i.e. it is of the form CC := CMP R1, 0.
656 If it is, find the instruction defining R1 (say I1) and try to create a
657 PARALLEL consisting of I1 and the comparison, representing a flag-setting
658 arithmetic instruction. Example:
659 I1: R1 := R2 + R3
660 <instructions that don't read the condition register>
661 I2: CC := CMP R1 0
662 I2 can be merged with I1 into:
663 I1: { CC := CMP (R2 + R3) 0 ; R1 := R2 + R3 }
664 This catches cases where R1 is used between I1 and I2 and therefore
665 combine and other RTL optimisations will not try to propagate it into
666 I2. Return true if we succeeded in merging CMP. */
668 static bool
669 try_merge_compare (struct comparison *cmp)
671 rtx_insn *cmp_insn = cmp->insn;
673 if (cmp->in_b != const0_rtx || cmp->in_a_setter == NULL)
674 return false;
675 rtx in_a = cmp->in_a;
676 df_ref use;
678 FOR_EACH_INSN_USE (use, cmp_insn)
679 if (DF_REF_REGNO (use) == REGNO (in_a))
680 break;
681 if (!use)
682 return false;
684 rtx_insn *def_insn = cmp->in_a_setter;
685 rtx set = single_set (def_insn);
686 if (!set)
687 return false;
689 if (!can_merge_compare_into_arith (cmp_insn, def_insn))
690 return false;
692 rtx src = SET_SRC (set);
694 /* If the source uses addressing modes with side effects, we can't
695 do the merge because we'd end up with a PARALLEL that has two
696 instances of that side effect in it. */
697 if (side_effects_p (src))
698 return false;
700 rtx flags = maybe_select_cc_mode (cmp, src, CONST0_RTX (GET_MODE (src)));
701 if (!flags)
703 /* We may already have a change group going through maybe_select_cc_mode.
704 Discard it properly. */
705 cancel_changes (0);
706 return false;
709 rtx flag_set
710 = gen_rtx_SET (flags, gen_rtx_COMPARE (GET_MODE (flags),
711 copy_rtx (src),
712 CONST0_RTX (GET_MODE (src))));
713 rtx arith_set = copy_rtx (PATTERN (def_insn));
714 rtx par = try_validate_parallel (flag_set, arith_set);
715 if (!par)
717 /* We may already have a change group going through maybe_select_cc_mode.
718 Discard it properly. */
719 cancel_changes (0);
720 return false;
722 if (!apply_change_group ())
723 return false;
724 emit_insn_after (par, def_insn);
725 delete_insn (def_insn);
726 delete_insn (cmp->insn);
727 return true;
730 /* Attempt to replace a comparison with a prior arithmetic insn that can
731 compute the same flags value as the comparison itself. Return true if
732 successful, having made all rtl modifications necessary. */
734 static bool
735 try_eliminate_compare (struct comparison *cmp)
737 rtx flags, in_a, in_b, cmp_a, cmp_b;
739 if (try_merge_compare (cmp))
740 return true;
742 /* We must have found an interesting "clobber" preceding the compare. */
743 if (cmp->prev_clobber == NULL)
744 return false;
746 /* Verify that IN_A is not clobbered in between CMP and PREV_CLOBBER.
747 Given that this target requires this pass, we can assume that most
748 insns do clobber the flags, and so the distance between the compare
749 and the clobber is likely to be small. */
750 /* ??? This is one point at which one could argue that DF_REF_CHAIN would
751 be useful, but it is thought to be too heavy-weight a solution here. */
752 in_a = equivalent_reg_at_start (cmp->in_a, cmp->insn, cmp->prev_clobber);
753 if (!in_a)
754 return false;
756 /* Likewise for IN_B if need be. */
757 if (CONSTANT_P (cmp->in_b))
758 in_b = cmp->in_b;
759 else if (REG_P (cmp->in_b))
761 in_b = equivalent_reg_at_start (cmp->in_b, cmp->insn, cmp->prev_clobber);
762 if (!in_b)
763 return false;
765 else if (GET_CODE (cmp->in_b) == UNSPEC)
767 const int len = XVECLEN (cmp->in_b, 0);
768 rtvec v = rtvec_alloc (len);
769 for (int i = 0; i < len; i++)
771 rtx r = equivalent_reg_at_start (XVECEXP (cmp->in_b, 0, i),
772 cmp->insn, cmp->prev_clobber);
773 if (!r)
774 return false;
775 RTVEC_ELT (v, i) = r;
777 in_b = gen_rtx_UNSPEC (GET_MODE (cmp->in_b), v, XINT (cmp->in_b, 1));
779 else
780 gcc_unreachable ();
782 /* We've reached PREV_CLOBBER without finding a modification of IN_A.
783 Validate that PREV_CLOBBER itself does in fact refer to IN_A. Do
784 recall that we've already validated the shape of PREV_CLOBBER. */
785 rtx_insn *insn = cmp->prev_clobber;
787 rtx x = XVECEXP (PATTERN (insn), 0, 0);
788 if (rtx_equal_p (SET_DEST (x), in_a))
789 cmp_a = SET_SRC (x);
791 /* Also check operations with implicit extensions, e.g.:
792 [(set (reg:DI)
793 (zero_extend:DI (plus:SI (reg:SI) (reg:SI))))
794 (set (reg:CCZ flags)
795 (compare:CCZ (plus:SI (reg:SI) (reg:SI))
796 (const_int 0)))] */
797 else if (REG_P (SET_DEST (x))
798 && REG_P (in_a)
799 && REGNO (SET_DEST (x)) == REGNO (in_a)
800 && (GET_CODE (SET_SRC (x)) == ZERO_EXTEND
801 || GET_CODE (SET_SRC (x)) == SIGN_EXTEND)
802 && GET_MODE (XEXP (SET_SRC (x), 0)) == GET_MODE (in_a))
803 cmp_a = XEXP (SET_SRC (x), 0);
805 /* Also check fully redundant comparisons, e.g.:
806 [(set (reg:SI)
807 (minus:SI (reg:SI) (reg:SI))))
808 (set (reg:CC flags)
809 (compare:CC (reg:SI) (reg:SI)))] */
810 else if (REG_P (in_b)
811 && GET_CODE (SET_SRC (x)) == MINUS
812 && rtx_equal_p (XEXP (SET_SRC (x), 0), in_a)
813 && rtx_equal_p (XEXP (SET_SRC (x), 1), in_b))
814 cmp_a = in_a;
816 else
817 return false;
819 /* If the source uses addressing modes with side effects, we can't
820 do the merge because we'd end up with a PARALLEL that has two
821 instances of that side effect in it. */
822 if (side_effects_p (cmp_a))
823 return false;
825 if (in_a == in_b)
826 cmp_b = cmp_a;
827 else if (rtx_equal_p (SET_DEST (x), in_b))
828 cmp_b = SET_SRC (x);
829 else
830 cmp_b = in_b;
831 if (side_effects_p (cmp_b))
832 return false;
834 /* Determine if we ought to use a different CC_MODE here. */
835 flags = maybe_select_cc_mode (cmp, cmp_a, cmp_b);
836 if (flags == NULL)
837 flags = gen_rtx_REG (cmp->orig_mode, targetm.flags_regnum);
839 /* Generate a new comparison for installation in the setter. */
840 rtx y = copy_rtx (cmp_a);
841 y = gen_rtx_COMPARE (GET_MODE (flags), y, copy_rtx (cmp_b));
842 y = gen_rtx_SET (flags, y);
844 /* Canonicalize instruction to:
845 [(set (reg:CCM) (compare:CCM (operation) (immediate)))
846 (set (reg) (operation)] */
848 rtvec v = rtvec_alloc (2);
849 RTVEC_ELT (v, 0) = y;
850 RTVEC_ELT (v, 1) = x;
852 rtx pat = gen_rtx_PARALLEL (VOIDmode, v);
854 /* Succeed if the new instruction is valid. Note that we may have started
855 a change group within maybe_select_cc_mode, therefore we must continue. */
856 validate_change (insn, &PATTERN (insn), pat, true);
858 if (!apply_change_group ())
859 return false;
861 /* Success. Delete the compare insn... */
862 delete_insn (cmp->insn);
864 /* ... and any notes that are now invalid due to multiple sets. */
865 x = find_regno_note (insn, REG_UNUSED, targetm.flags_regnum);
866 if (x)
867 remove_note (insn, x);
868 x = find_reg_note (insn, REG_EQUAL, NULL);
869 if (x)
870 remove_note (insn, x);
871 x = find_reg_note (insn, REG_EQUIV, NULL);
872 if (x)
873 remove_note (insn, x);
875 return true;
878 /* Main entry point to the pass. */
880 static unsigned int
881 execute_compare_elim_after_reload (void)
883 df_analyze ();
885 gcc_checking_assert (!all_compares.exists ());
887 /* Locate all comparisons and their uses, and eliminate duplicates. */
888 find_comparisons ();
889 if (all_compares.exists ())
891 struct comparison *cmp;
892 size_t i;
894 /* Eliminate comparisons that are redundant with flags computation. */
895 FOR_EACH_VEC_ELT (all_compares, i, cmp)
897 try_eliminate_compare (cmp);
898 XDELETE (cmp);
901 all_compares.release ();
904 return 0;
907 namespace {
909 const pass_data pass_data_compare_elim_after_reload =
911 RTL_PASS, /* type */
912 "cmpelim", /* name */
913 OPTGROUP_NONE, /* optinfo_flags */
914 TV_NONE, /* tv_id */
915 0, /* properties_required */
916 0, /* properties_provided */
917 0, /* properties_destroyed */
918 0, /* todo_flags_start */
919 ( TODO_df_finish | TODO_df_verify ), /* todo_flags_finish */
922 class pass_compare_elim_after_reload : public rtl_opt_pass
924 public:
925 pass_compare_elim_after_reload (gcc::context *ctxt)
926 : rtl_opt_pass (pass_data_compare_elim_after_reload, ctxt)
929 /* opt_pass methods: */
930 virtual bool gate (function *)
932 /* Setting this target hook value is how a backend indicates the need. */
933 if (targetm.flags_regnum == INVALID_REGNUM)
934 return false;
935 return flag_compare_elim_after_reload;
938 virtual unsigned int execute (function *)
940 return execute_compare_elim_after_reload ();
943 }; // class pass_compare_elim_after_reload
945 } // anon namespace
947 rtl_opt_pass *
948 make_pass_compare_elim_after_reload (gcc::context *ctxt)
950 return new pass_compare_elim_after_reload (ctxt);