Daily bump.
[official-gcc.git] / gcc / compare-elim.c
blob607eadc3d96272e07065a64270f25caf70e49ce3
1 /* Post-reload compare elimination.
2 Copyright (C) 2010-2021 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 was available via NOTICE_UPDATE_CC for cc0 targets.
30 This pass assumes:
32 (0) CBRANCH/CSTORE etc have been split in pass_split_after_reload.
34 (1) All comparison patterns are represented as
36 [(set (reg:CC) (compare:CC (reg) (reg_or_immediate)))]
38 (2) All insn patterns that modify the flags are represented as
40 [(set (reg) (operation)
41 (clobber (reg:CC))]
43 (3) If an insn of form (2) can usefully set the flags, there is
44 another pattern of the form
46 [(set (reg:CCM) (compare:CCM (operation) (immediate)))
47 (set (reg) (operation)]
49 The mode CCM will be chosen as if by SELECT_CC_MODE.
51 Note that unlike NOTICE_UPDATE_CC, we do not handle memory operands.
52 This could be handled as a future enhancement.
55 #include "config.h"
56 #include "system.h"
57 #include "coretypes.h"
58 #include "backend.h"
59 #include "target.h"
60 #include "rtl.h"
61 #include "df.h"
62 #include "memmodel.h"
63 #include "tm_p.h"
64 #include "insn-config.h"
65 #include "recog.h"
66 #include "emit-rtl.h"
67 #include "cfgrtl.h"
68 #include "tree-pass.h"
69 #include "domwalk.h"
72 /* These structures describe a comparison and how it is used. */
74 /* The choice of maximum 3 uses comes from wanting to eliminate the two
75 duplicate compares from a three-way branch on the sign of a value.
76 This is also sufficient to eliminate the duplicate compare against the
77 high-part of a double-word comparison. */
78 #define MAX_CMP_USE 3
80 struct comparison_use
82 /* The instruction in which the result of the compare is used. */
83 rtx_insn *insn;
84 /* The location of the flags register within the use. */
85 rtx *loc;
86 /* The comparison code applied against the flags register. */
87 enum rtx_code code;
90 struct comparison
92 /* The comparison instruction. */
93 rtx_insn *insn;
95 /* The insn prior to the comparison insn that clobbers the flags. */
96 rtx_insn *prev_clobber;
98 /* The insn prior to the comparison insn that sets in_a REG. */
99 rtx_insn *in_a_setter;
101 /* The two values being compared. These will be either REGs or
102 constants. */
103 rtx in_a, in_b;
105 /* The REG_EH_REGION of the comparison. */
106 rtx eh_note;
108 /* Information about how this comparison is used. */
109 struct comparison_use uses[MAX_CMP_USE];
111 /* The original CC_MODE for this comparison. */
112 machine_mode orig_mode;
114 /* The number of uses identified for this comparison. */
115 unsigned short n_uses;
117 /* True if not all uses of this comparison have been identified.
118 This can happen either for overflowing the array above, or if
119 the flags register is used in some unusual context. */
120 bool missing_uses;
122 /* True if its inputs are still valid at the end of the block. */
123 bool inputs_valid;
125 /* Whether IN_A is wrapped in a NOT before being compared. */
126 bool not_in_a;
129 static vec<comparison *> all_compares;
131 /* Return whether X is a NOT unary expression. */
133 static bool
134 is_not (rtx x)
136 return GET_CODE (x) == NOT;
139 /* Strip a NOT unary expression around X, if any. */
141 static rtx
142 strip_not (rtx x)
144 if (is_not (x))
145 return XEXP (x, 0);
147 return x;
150 /* Look for a "conforming" comparison, as defined above. If valid, return
151 the rtx for the COMPARE itself. */
153 static rtx
154 conforming_compare (rtx_insn *insn)
156 rtx set, src, dest;
158 set = single_set (insn);
159 if (set == NULL)
160 return NULL;
162 src = SET_SRC (set);
163 if (GET_CODE (src) != COMPARE)
164 return NULL;
166 dest = SET_DEST (set);
167 if (!REG_P (dest) || REGNO (dest) != targetm.flags_regnum)
168 return NULL;
170 if (!REG_P (strip_not (XEXP (src, 0))))
171 return NULL;
173 if (CONSTANT_P (XEXP (src, 1)) || REG_P (XEXP (src, 1)))
174 return src;
176 if (GET_CODE (XEXP (src, 1)) == UNSPEC)
178 for (int i = 0; i < XVECLEN (XEXP (src, 1), 0); i++)
179 if (!REG_P (XVECEXP (XEXP (src, 1), 0, i)))
180 return NULL;
181 return src;
184 return NULL;
187 /* Look for a pattern of the "correct" form for an insn with a flags clobber
188 for which we may be able to eliminate a compare later. We're not looking
189 to validate any inputs at this time, merely see that the basic shape is
190 correct. The term "arithmetic" may be somewhat misleading... */
192 static bool
193 arithmetic_flags_clobber_p (rtx_insn *insn)
195 rtx pat, x;
197 if (!NONJUMP_INSN_P (insn))
198 return false;
199 pat = PATTERN (insn);
200 if (asm_noperands (pat) >= 0)
201 return false;
203 if (GET_CODE (pat) == PARALLEL && XVECLEN (pat, 0) == 2)
205 x = XVECEXP (pat, 0, 0);
206 if (GET_CODE (x) != SET)
207 return false;
208 x = SET_DEST (x);
209 if (!REG_P (x))
210 return false;
212 x = XVECEXP (pat, 0, 1);
213 if (GET_CODE (x) == CLOBBER)
215 x = XEXP (x, 0);
216 if (REG_P (x) && REGNO (x) == targetm.flags_regnum)
217 return true;
221 return false;
224 /* Look for uses of FLAGS in INSN. If we find one we can analyze, record
225 it in CMP; otherwise indicate that we've missed a use. */
227 static void
228 find_flags_uses_in_insn (struct comparison *cmp, rtx_insn *insn)
230 df_ref use;
232 /* If we've already lost track of uses, don't bother collecting more. */
233 if (cmp->missing_uses)
234 return;
236 /* Find a USE of the flags register. */
237 FOR_EACH_INSN_USE (use, insn)
238 if (DF_REF_REGNO (use) == targetm.flags_regnum)
240 rtx x, *loc;
242 /* If this is an unusual use, quit. */
243 if (DF_REF_TYPE (use) != DF_REF_REG_USE)
244 goto fail;
246 /* If we've run out of slots to record uses, quit. */
247 if (cmp->n_uses == MAX_CMP_USE)
248 goto fail;
250 /* Unfortunately the location of the flags register, while present
251 in the reference structure, doesn't help. We need to find the
252 comparison code that is outer to the actual flags use. */
253 loc = DF_REF_LOC (use);
254 x = PATTERN (insn);
255 if (GET_CODE (x) == PARALLEL)
256 x = XVECEXP (x, 0, 0);
257 x = SET_SRC (x);
258 if (GET_CODE (x) == IF_THEN_ELSE)
259 x = XEXP (x, 0);
260 if (COMPARISON_P (x)
261 && loc == &XEXP (x, 0)
262 && XEXP (x, 1) == const0_rtx)
264 /* We've found a use of the flags that we understand. */
265 struct comparison_use *cuse = &cmp->uses[cmp->n_uses++];
266 cuse->insn = insn;
267 cuse->loc = loc;
268 cuse->code = GET_CODE (x);
270 else
271 goto fail;
273 return;
275 fail:
276 /* We failed to recognize this use of the flags register. */
277 cmp->missing_uses = true;
280 class find_comparison_dom_walker : public dom_walker
282 public:
283 find_comparison_dom_walker (cdi_direction direction)
284 : dom_walker (direction) {}
286 virtual edge before_dom_children (basic_block);
289 /* Return true if conforming COMPARE with EH_NOTE is redundant with comparison
290 CMP and can thus be eliminated. */
292 static bool
293 can_eliminate_compare (rtx compare, rtx eh_note, struct comparison *cmp)
295 /* Take care that it's in the same EH region. */
296 if (cfun->can_throw_non_call_exceptions
297 && !rtx_equal_p (eh_note, cmp->eh_note))
298 return false;
300 /* Make sure the compare is redundant with the previous. */
301 if (!rtx_equal_p (strip_not (XEXP (compare, 0)), cmp->in_a)
302 || !rtx_equal_p (XEXP (compare, 1), cmp->in_b))
303 return false;
305 if (is_not (XEXP (compare, 0)) != cmp->not_in_a)
306 return false;
308 /* New mode must be compatible with the previous compare mode. */
309 machine_mode new_mode
310 = targetm.cc_modes_compatible (GET_MODE (compare), cmp->orig_mode);
312 if (new_mode == VOIDmode)
313 return false;
315 if (cmp->orig_mode != new_mode)
317 /* Generate new comparison for substitution. */
318 rtx flags = gen_rtx_REG (new_mode, targetm.flags_regnum);
319 rtx x = gen_rtx_COMPARE (new_mode, cmp->in_a, cmp->in_b);
320 x = gen_rtx_SET (flags, x);
322 if (!validate_change (cmp->insn, &PATTERN (cmp->insn), x, false))
323 return false;
325 cmp->orig_mode = new_mode;
328 return true;
331 /* Identify comparison instructions within BB. If the flags from the last
332 compare in the BB is live at the end of the block, install the compare
333 in BB->AUX. Called via dom_walker.walk (). */
335 edge
336 find_comparison_dom_walker::before_dom_children (basic_block bb)
338 rtx_insn *insn, *next;
339 bool need_purge = false;
340 rtx_insn *last_setter[FIRST_PSEUDO_REGISTER];
342 /* The last comparison that was made. Will be reset to NULL
343 once the flags are clobbered. */
344 struct comparison *last_cmp = NULL;
346 /* True iff the last comparison has not been clobbered, nor
347 have its inputs. Used to eliminate duplicate compares. */
348 bool last_cmp_valid = false;
350 /* The last insn that clobbered the flags, if that insn is of
351 a form that may be valid for eliminating a following compare.
352 To be reset to NULL once the flags are set otherwise. */
353 rtx_insn *last_clobber = NULL;
355 /* Propagate the last live comparison throughout the extended basic block. */
356 if (single_pred_p (bb))
358 last_cmp = (struct comparison *) single_pred (bb)->aux;
359 if (last_cmp)
360 last_cmp_valid = last_cmp->inputs_valid;
363 memset (last_setter, 0, sizeof (last_setter));
364 for (insn = BB_HEAD (bb); insn; insn = next)
366 rtx src;
368 next = (insn == BB_END (bb) ? NULL : NEXT_INSN (insn));
369 if (!NONDEBUG_INSN_P (insn))
370 continue;
372 src = conforming_compare (insn);
373 if (src)
375 rtx eh_note = NULL;
377 if (cfun->can_throw_non_call_exceptions)
378 eh_note = find_reg_note (insn, REG_EH_REGION, NULL);
380 if (last_cmp_valid && can_eliminate_compare (src, eh_note, last_cmp))
382 if (eh_note)
383 need_purge = true;
384 delete_insn (insn);
385 continue;
388 last_cmp = XCNEW (struct comparison);
389 last_cmp->insn = insn;
390 last_cmp->prev_clobber = last_clobber;
391 last_cmp->in_a = strip_not (XEXP (src, 0));
392 last_cmp->in_b = XEXP (src, 1);
393 last_cmp->not_in_a = is_not (XEXP (src, 0));
394 last_cmp->eh_note = eh_note;
395 last_cmp->orig_mode = GET_MODE (src);
396 if (last_cmp->in_b == const0_rtx
397 && last_setter[REGNO (last_cmp->in_a)])
399 rtx set = single_set (last_setter[REGNO (last_cmp->in_a)]);
400 if (set && rtx_equal_p (SET_DEST (set), last_cmp->in_a))
401 last_cmp->in_a_setter = last_setter[REGNO (last_cmp->in_a)];
403 all_compares.safe_push (last_cmp);
405 /* It's unusual, but be prepared for comparison patterns that
406 also clobber an input, or perhaps a scratch. */
407 last_clobber = NULL;
408 last_cmp_valid = true;
411 else
413 /* Notice if this instruction uses the flags register. */
414 if (last_cmp)
415 find_flags_uses_in_insn (last_cmp, insn);
417 /* Notice if this instruction kills the flags register. */
418 df_ref def;
419 FOR_EACH_INSN_DEF (def, insn)
420 if (DF_REF_REGNO (def) == targetm.flags_regnum)
422 /* See if this insn could be the "clobber" that eliminates
423 a future comparison. */
424 last_clobber = (arithmetic_flags_clobber_p (insn)
425 ? insn : NULL);
427 /* In either case, the previous compare is no longer valid. */
428 last_cmp = NULL;
429 last_cmp_valid = false;
430 break;
434 /* Notice if any of the inputs to the comparison have changed
435 and remember last insn that sets each register. */
436 df_ref def;
437 FOR_EACH_INSN_DEF (def, insn)
439 if (last_cmp_valid
440 && (DF_REF_REGNO (def) == REGNO (last_cmp->in_a)
441 || (REG_P (last_cmp->in_b)
442 && DF_REF_REGNO (def) == REGNO (last_cmp->in_b))))
443 last_cmp_valid = false;
444 last_setter[DF_REF_REGNO (def)] = insn;
448 /* Remember the live comparison for subsequent members of
449 the extended basic block. */
450 if (last_cmp)
452 bb->aux = last_cmp;
453 last_cmp->inputs_valid = last_cmp_valid;
455 /* Look to see if the flags register is live outgoing here, and
456 incoming to any successor not part of the extended basic block. */
457 if (bitmap_bit_p (df_get_live_out (bb), targetm.flags_regnum))
459 edge e;
460 edge_iterator ei;
462 FOR_EACH_EDGE (e, ei, bb->succs)
464 basic_block dest = e->dest;
465 if (bitmap_bit_p (df_get_live_in (bb), targetm.flags_regnum)
466 && !single_pred_p (dest))
468 last_cmp->missing_uses = true;
469 break;
475 /* If we deleted a compare with a REG_EH_REGION note, we may need to
476 remove EH edges. */
477 if (need_purge)
478 purge_dead_edges (bb);
480 return NULL;
483 /* Find all comparisons in the function. */
485 static void
486 find_comparisons (void)
488 calculate_dominance_info (CDI_DOMINATORS);
490 find_comparison_dom_walker (CDI_DOMINATORS)
491 .walk (cfun->cfg->x_entry_block_ptr);
493 clear_aux_for_blocks ();
494 free_dominance_info (CDI_DOMINATORS);
497 /* Select an alternate CC_MODE for a comparison insn comparing A and B.
498 Note that inputs are almost certainly different than the IN_A and IN_B
499 stored in CMP -- we're called while attempting to eliminate the compare
500 after all. Return the new FLAGS rtx if successful, else return NULL.
501 Note that this function may start a change group. */
503 static rtx
504 maybe_select_cc_mode (struct comparison *cmp, rtx a ATTRIBUTE_UNUSED,
505 rtx b ATTRIBUTE_UNUSED)
507 machine_mode sel_mode;
508 const int n = cmp->n_uses;
509 rtx flags = NULL;
511 #ifndef SELECT_CC_MODE
512 /* Minimize code differences when this target macro is undefined. */
513 return NULL;
514 #define SELECT_CC_MODE(A,B,C) (gcc_unreachable (), VOIDmode)
515 #endif
517 /* If we don't have access to all of the uses, we can't validate. */
518 if (cmp->missing_uses || n == 0)
519 return NULL;
521 /* Find a new mode that works for all of the uses. Special case the
522 common case of exactly one use. */
523 if (n == 1)
525 sel_mode = SELECT_CC_MODE (cmp->uses[0].code, a, b);
526 if (sel_mode != cmp->orig_mode)
528 flags = gen_rtx_REG (sel_mode, targetm.flags_regnum);
529 validate_change (cmp->uses[0].insn, cmp->uses[0].loc, flags, true);
532 else
534 int i;
536 sel_mode = SELECT_CC_MODE (cmp->uses[0].code, a, b);
537 for (i = 1; i < n; ++i)
539 machine_mode new_mode = SELECT_CC_MODE (cmp->uses[i].code, a, b);
540 if (new_mode != sel_mode)
542 sel_mode = targetm.cc_modes_compatible (sel_mode, new_mode);
543 if (sel_mode == VOIDmode)
544 return NULL;
548 if (sel_mode != cmp->orig_mode)
550 flags = gen_rtx_REG (sel_mode, targetm.flags_regnum);
551 for (i = 0; i < n; ++i)
552 validate_change (cmp->uses[i].insn, cmp->uses[i].loc, flags, true);
556 return flags;
559 /* Return a register RTX holding the same value at START as REG at END, or
560 NULL_RTX if there is none. */
562 static rtx
563 equivalent_reg_at_start (rtx reg, rtx_insn *end, rtx_insn *start)
565 machine_mode orig_mode = GET_MODE (reg);
566 rtx_insn *bb_head = BB_HEAD (BLOCK_FOR_INSN (end));
568 for (rtx_insn *insn = PREV_INSN (end);
569 insn != start;
570 insn = PREV_INSN (insn))
572 const int abnormal_flags
573 = (DF_REF_CONDITIONAL | DF_REF_PARTIAL | DF_REF_MAY_CLOBBER
574 | DF_REF_MUST_CLOBBER | DF_REF_SIGN_EXTRACT
575 | DF_REF_ZERO_EXTRACT | DF_REF_STRICT_LOW_PART
576 | DF_REF_PRE_POST_MODIFY);
577 df_ref def;
579 /* Note that the BB_HEAD is always either a note or a label, but in
580 any case it means that REG is defined outside the block. */
581 if (insn == bb_head)
582 return NULL_RTX;
583 if (NOTE_P (insn) || DEBUG_INSN_P (insn))
584 continue;
586 /* Find a possible def of REG in INSN. */
587 FOR_EACH_INSN_DEF (def, insn)
588 if (DF_REF_REGNO (def) == REGNO (reg))
589 break;
591 /* No definitions of REG; continue searching. */
592 if (def == NULL)
593 continue;
595 /* Bail if this is not a totally normal set of REG. */
596 if (DF_REF_IS_ARTIFICIAL (def))
597 return NULL_RTX;
598 if (DF_REF_FLAGS (def) & abnormal_flags)
599 return NULL_RTX;
601 /* We've found an insn between the compare and the clobber that sets
602 REG. Given that pass_cprop_hardreg has not yet run, we still find
603 situations in which we can usefully look through a copy insn. */
604 rtx x = single_set (insn);
605 if (x == NULL_RTX)
606 return NULL_RTX;
607 reg = SET_SRC (x);
608 if (!REG_P (reg))
609 return NULL_RTX;
612 if (GET_MODE (reg) != orig_mode)
613 return NULL_RTX;
615 return reg;
618 /* Return true if it is okay to merge the comparison CMP_INSN with
619 the instruction ARITH_INSN. Both instructions are assumed to be in the
620 same basic block with ARITH_INSN appearing before CMP_INSN. This checks
621 that there are no uses or defs of the condition flags or control flow
622 changes between the two instructions. */
624 static bool
625 can_merge_compare_into_arith (rtx_insn *cmp_insn, rtx_insn *arith_insn)
627 for (rtx_insn *insn = PREV_INSN (cmp_insn);
628 insn && insn != arith_insn;
629 insn = PREV_INSN (insn))
631 if (!NONDEBUG_INSN_P (insn))
632 continue;
633 /* Bail if there are jumps or calls in between. */
634 if (!NONJUMP_INSN_P (insn))
635 return false;
637 /* Bail on old-style asm statements because they lack
638 data flow information. */
639 if (GET_CODE (PATTERN (insn)) == ASM_INPUT)
640 return false;
642 df_ref ref;
643 /* Find a USE of the flags register. */
644 FOR_EACH_INSN_USE (ref, insn)
645 if (DF_REF_REGNO (ref) == targetm.flags_regnum)
646 return false;
648 /* Find a DEF of the flags register. */
649 FOR_EACH_INSN_DEF (ref, insn)
650 if (DF_REF_REGNO (ref) == targetm.flags_regnum)
651 return false;
653 return true;
656 /* Given two SET expressions, SET_A and SET_B determine whether they form
657 a recognizable pattern when emitted in parallel. Return that parallel
658 if so. Otherwise return NULL. */
660 static rtx
661 try_validate_parallel (rtx set_a, rtx set_b)
663 rtx par = gen_rtx_PARALLEL (VOIDmode, gen_rtvec (2, set_a, set_b));
664 rtx_insn *insn = make_insn_raw (par);
666 if (insn_invalid_p (insn, false))
668 crtl->emit.x_cur_insn_uid--;
669 return NULL_RTX;
672 SET_PREV_INSN (insn) = NULL_RTX;
673 SET_NEXT_INSN (insn) = NULL_RTX;
674 INSN_LOCATION (insn) = 0;
675 return insn;
678 /* For a comparison instruction described by CMP check if it compares a
679 register with zero i.e. it is of the form CC := CMP R1, 0.
680 If it is, find the instruction defining R1 (say I1) and try to create a
681 PARALLEL consisting of I1 and the comparison, representing a flag-setting
682 arithmetic instruction. Example:
683 I1: R1 := R2 + R3
684 <instructions that don't read the condition register>
685 I2: CC := CMP R1 0
686 I2 can be merged with I1 into:
687 I1: { CC := CMP (R2 + R3) 0 ; R1 := R2 + R3 }
688 This catches cases where R1 is used between I1 and I2 and therefore
689 combine and other RTL optimisations will not try to propagate it into
690 I2. Return true if we succeeded in merging CMP. */
692 static bool
693 try_merge_compare (struct comparison *cmp)
695 rtx_insn *cmp_insn = cmp->insn;
697 if (cmp->in_b != const0_rtx || cmp->in_a_setter == NULL)
698 return false;
699 rtx in_a = cmp->in_a;
700 df_ref use;
702 FOR_EACH_INSN_USE (use, cmp_insn)
703 if (DF_REF_REGNO (use) == REGNO (in_a))
704 break;
705 if (!use)
706 return false;
708 rtx_insn *def_insn = cmp->in_a_setter;
709 rtx set = single_set (def_insn);
710 if (!set)
711 return false;
713 if (!can_merge_compare_into_arith (cmp_insn, def_insn))
714 return false;
716 rtx src = SET_SRC (set);
718 /* If the source uses addressing modes with side effects, we can't
719 do the merge because we'd end up with a PARALLEL that has two
720 instances of that side effect in it. */
721 if (side_effects_p (src))
722 return false;
724 rtx flags = maybe_select_cc_mode (cmp, src, CONST0_RTX (GET_MODE (src)));
725 if (!flags)
727 /* We may already have a change group going through maybe_select_cc_mode.
728 Discard it properly. */
729 cancel_changes (0);
730 return false;
733 rtx flag_set
734 = gen_rtx_SET (flags, gen_rtx_COMPARE (GET_MODE (flags),
735 copy_rtx (src),
736 CONST0_RTX (GET_MODE (src))));
737 rtx arith_set = copy_rtx (PATTERN (def_insn));
738 rtx par = try_validate_parallel (flag_set, arith_set);
739 if (!par)
741 /* We may already have a change group going through maybe_select_cc_mode.
742 Discard it properly. */
743 cancel_changes (0);
744 return false;
746 if (!apply_change_group ())
747 return false;
748 emit_insn_after (par, def_insn);
749 delete_insn (def_insn);
750 delete_insn (cmp->insn);
751 return true;
754 /* Attempt to replace a comparison with a prior arithmetic insn that can
755 compute the same flags value as the comparison itself. Return true if
756 successful, having made all rtl modifications necessary. */
758 static bool
759 try_eliminate_compare (struct comparison *cmp)
761 rtx flags, in_a, in_b, cmp_a, cmp_b;
763 if (try_merge_compare (cmp))
764 return true;
766 /* We must have found an interesting "clobber" preceding the compare. */
767 if (cmp->prev_clobber == NULL)
768 return false;
770 /* Verify that IN_A is not clobbered in between CMP and PREV_CLOBBER.
771 Given that this target requires this pass, we can assume that most
772 insns do clobber the flags, and so the distance between the compare
773 and the clobber is likely to be small. */
774 /* ??? This is one point at which one could argue that DF_REF_CHAIN would
775 be useful, but it is thought to be too heavy-weight a solution here. */
776 in_a = equivalent_reg_at_start (cmp->in_a, cmp->insn, cmp->prev_clobber);
777 if (!in_a)
778 return false;
780 /* Likewise for IN_B if need be. */
781 if (CONSTANT_P (cmp->in_b))
782 in_b = cmp->in_b;
783 else if (REG_P (cmp->in_b))
785 in_b = equivalent_reg_at_start (cmp->in_b, cmp->insn, cmp->prev_clobber);
786 if (!in_b)
787 return false;
789 else if (GET_CODE (cmp->in_b) == UNSPEC)
791 const int len = XVECLEN (cmp->in_b, 0);
792 rtvec v = rtvec_alloc (len);
793 for (int i = 0; i < len; i++)
795 rtx r = equivalent_reg_at_start (XVECEXP (cmp->in_b, 0, i),
796 cmp->insn, cmp->prev_clobber);
797 if (!r)
798 return false;
799 RTVEC_ELT (v, i) = r;
801 in_b = gen_rtx_UNSPEC (GET_MODE (cmp->in_b), v, XINT (cmp->in_b, 1));
803 else
804 gcc_unreachable ();
806 /* We've reached PREV_CLOBBER without finding a modification of IN_A.
807 Validate that PREV_CLOBBER itself does in fact refer to IN_A. Do
808 recall that we've already validated the shape of PREV_CLOBBER. */
809 rtx_insn *insn = cmp->prev_clobber;
811 rtx x = XVECEXP (PATTERN (insn), 0, 0);
812 if (rtx_equal_p (SET_DEST (x), in_a))
813 cmp_a = SET_SRC (x);
815 /* Also check operations with implicit extensions, e.g.:
816 [(set (reg:DI)
817 (zero_extend:DI (plus:SI (reg:SI) (reg:SI))))
818 (set (reg:CCZ flags)
819 (compare:CCZ (plus:SI (reg:SI) (reg:SI))
820 (const_int 0)))] */
821 else if (REG_P (SET_DEST (x))
822 && REG_P (in_a)
823 && REGNO (SET_DEST (x)) == REGNO (in_a)
824 && (GET_CODE (SET_SRC (x)) == ZERO_EXTEND
825 || GET_CODE (SET_SRC (x)) == SIGN_EXTEND)
826 && GET_MODE (XEXP (SET_SRC (x), 0)) == GET_MODE (in_a))
827 cmp_a = XEXP (SET_SRC (x), 0);
829 /* Also check fully redundant comparisons, e.g.:
830 [(set (reg:SI)
831 (minus:SI (reg:SI) (reg:SI))))
832 (set (reg:CC flags)
833 (compare:CC (reg:SI) (reg:SI)))] */
834 else if (REG_P (in_b)
835 && GET_CODE (SET_SRC (x)) == MINUS
836 && rtx_equal_p (XEXP (SET_SRC (x), 0), in_a)
837 && rtx_equal_p (XEXP (SET_SRC (x), 1), in_b))
838 cmp_a = in_a;
840 else
841 return false;
843 /* If the source uses addressing modes with side effects, we can't
844 do the merge because we'd end up with a PARALLEL that has two
845 instances of that side effect in it. */
846 if (side_effects_p (cmp_a))
847 return false;
849 if (in_a == in_b)
850 cmp_b = cmp_a;
851 else if (rtx_equal_p (SET_DEST (x), in_b))
852 cmp_b = SET_SRC (x);
853 else
854 cmp_b = in_b;
855 if (side_effects_p (cmp_b))
856 return false;
858 /* Determine if we ought to use a different CC_MODE here. */
859 flags = maybe_select_cc_mode (cmp, cmp_a, cmp_b);
860 if (flags == NULL)
861 flags = gen_rtx_REG (cmp->orig_mode, targetm.flags_regnum);
863 /* Generate a new comparison for installation in the setter. */
864 rtx y = cmp->not_in_a
865 ? gen_rtx_NOT (GET_MODE (cmp_a), copy_rtx (cmp_a))
866 : copy_rtx (cmp_a);
867 y = gen_rtx_COMPARE (GET_MODE (flags), y, copy_rtx (cmp_b));
868 y = gen_rtx_SET (flags, y);
870 /* Canonicalize instruction to:
871 [(set (reg:CCM) (compare:CCM (operation) (immediate)))
872 (set (reg) (operation)] */
874 rtvec v = rtvec_alloc (2);
875 RTVEC_ELT (v, 0) = y;
876 RTVEC_ELT (v, 1) = x;
878 rtx pat = gen_rtx_PARALLEL (VOIDmode, v);
880 /* Succeed if the new instruction is valid. Note that we may have started
881 a change group within maybe_select_cc_mode, therefore we must continue. */
882 validate_change (insn, &PATTERN (insn), pat, true);
884 if (!apply_change_group ())
885 return false;
887 /* Success. Delete the compare insn... */
888 delete_insn (cmp->insn);
890 /* ... and any notes that are now invalid due to multiple sets. */
891 x = find_regno_note (insn, REG_UNUSED, targetm.flags_regnum);
892 if (x)
893 remove_note (insn, x);
894 x = find_reg_note (insn, REG_EQUAL, NULL);
895 if (x)
896 remove_note (insn, x);
897 x = find_reg_note (insn, REG_EQUIV, NULL);
898 if (x)
899 remove_note (insn, x);
901 return true;
904 /* Main entry point to the pass. */
906 static unsigned int
907 execute_compare_elim_after_reload (void)
909 df_set_flags (DF_LR_RUN_DCE);
910 df_analyze ();
912 gcc_checking_assert (!all_compares.exists ());
914 /* Locate all comparisons and their uses, and eliminate duplicates. */
915 find_comparisons ();
916 if (all_compares.exists ())
918 struct comparison *cmp;
919 size_t i;
921 /* Eliminate comparisons that are redundant with flags computation. */
922 FOR_EACH_VEC_ELT (all_compares, i, cmp)
924 try_eliminate_compare (cmp);
925 XDELETE (cmp);
928 all_compares.release ();
931 return 0;
934 namespace {
936 const pass_data pass_data_compare_elim_after_reload =
938 RTL_PASS, /* type */
939 "cmpelim", /* name */
940 OPTGROUP_NONE, /* optinfo_flags */
941 TV_NONE, /* tv_id */
942 0, /* properties_required */
943 0, /* properties_provided */
944 0, /* properties_destroyed */
945 0, /* todo_flags_start */
946 ( TODO_df_finish | TODO_df_verify ), /* todo_flags_finish */
949 class pass_compare_elim_after_reload : public rtl_opt_pass
951 public:
952 pass_compare_elim_after_reload (gcc::context *ctxt)
953 : rtl_opt_pass (pass_data_compare_elim_after_reload, ctxt)
956 /* opt_pass methods: */
957 virtual bool gate (function *)
959 /* Setting this target hook value is how a backend indicates the need. */
960 if (targetm.flags_regnum == INVALID_REGNUM)
961 return false;
962 return flag_compare_elim_after_reload;
965 virtual unsigned int execute (function *)
967 return execute_compare_elim_after_reload ();
970 }; // class pass_compare_elim_after_reload
972 } // anon namespace
974 rtl_opt_pass *
975 make_pass_compare_elim_after_reload (gcc::context *ctxt)
977 return new pass_compare_elim_after_reload (ctxt);