Fix formatting of -ftime-report.
[official-gcc.git] / gcc / compare-elim.c
blob16576c4447344080be6e63f0db57b3c8c4bc3258
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);
693 rtx flags = maybe_select_cc_mode (cmp, src, CONST0_RTX (GET_MODE (src)));
694 if (!flags)
696 /* We may already have a change group going through maybe_select_cc_mode.
697 Discard it properly. */
698 cancel_changes (0);
699 return false;
702 rtx flag_set
703 = gen_rtx_SET (flags, gen_rtx_COMPARE (GET_MODE (flags),
704 copy_rtx (src),
705 CONST0_RTX (GET_MODE (src))));
706 rtx arith_set = copy_rtx (PATTERN (def_insn));
707 rtx par = try_validate_parallel (flag_set, arith_set);
708 if (!par)
710 /* We may already have a change group going through maybe_select_cc_mode.
711 Discard it properly. */
712 cancel_changes (0);
713 return false;
715 if (!apply_change_group ())
716 return false;
717 emit_insn_after (par, def_insn);
718 delete_insn (def_insn);
719 delete_insn (cmp->insn);
720 return true;
723 /* Attempt to replace a comparison with a prior arithmetic insn that can
724 compute the same flags value as the comparison itself. Return true if
725 successful, having made all rtl modifications necessary. */
727 static bool
728 try_eliminate_compare (struct comparison *cmp)
730 rtx flags, in_a, in_b, cmp_src;
732 if (try_merge_compare (cmp))
733 return true;
735 /* We must have found an interesting "clobber" preceding the compare. */
736 if (cmp->prev_clobber == NULL)
737 return false;
739 /* Verify that IN_A is not clobbered in between CMP and PREV_CLOBBER.
740 Given that this target requires this pass, we can assume that most
741 insns do clobber the flags, and so the distance between the compare
742 and the clobber is likely to be small. */
743 /* ??? This is one point at which one could argue that DF_REF_CHAIN would
744 be useful, but it is thought to be too heavy-weight a solution here. */
745 in_a = equivalent_reg_at_start (cmp->in_a, cmp->insn, cmp->prev_clobber);
746 if (!in_a)
747 return false;
749 /* Likewise for IN_B if need be. */
750 if (CONSTANT_P (cmp->in_b))
751 in_b = cmp->in_b;
752 else if (REG_P (cmp->in_b))
754 in_b = equivalent_reg_at_start (cmp->in_b, cmp->insn, cmp->prev_clobber);
755 if (!in_b)
756 return false;
758 else if (GET_CODE (cmp->in_b) == UNSPEC)
760 const int len = XVECLEN (cmp->in_b, 0);
761 rtvec v = rtvec_alloc (len);
762 for (int i = 0; i < len; i++)
764 rtx r = equivalent_reg_at_start (XVECEXP (cmp->in_b, 0, i),
765 cmp->insn, cmp->prev_clobber);
766 if (!r)
767 return false;
768 RTVEC_ELT (v, i) = r;
770 in_b = gen_rtx_UNSPEC (GET_MODE (cmp->in_b), v, XINT (cmp->in_b, 1));
772 else
773 gcc_unreachable ();
775 /* We've reached PREV_CLOBBER without finding a modification of IN_A.
776 Validate that PREV_CLOBBER itself does in fact refer to IN_A. Do
777 recall that we've already validated the shape of PREV_CLOBBER. */
778 rtx_insn *insn = cmp->prev_clobber;
780 rtx x = XVECEXP (PATTERN (insn), 0, 0);
781 if (rtx_equal_p (SET_DEST (x), in_a))
782 cmp_src = SET_SRC (x);
784 /* Also check operations with implicit extensions, e.g.:
785 [(set (reg:DI)
786 (zero_extend:DI (plus:SI (reg:SI) (reg:SI))))
787 (set (reg:CCZ flags)
788 (compare:CCZ (plus:SI (reg:SI) (reg:SI))
789 (const_int 0)))] */
790 else if (REG_P (SET_DEST (x))
791 && REG_P (in_a)
792 && REGNO (SET_DEST (x)) == REGNO (in_a)
793 && (GET_CODE (SET_SRC (x)) == ZERO_EXTEND
794 || GET_CODE (SET_SRC (x)) == SIGN_EXTEND)
795 && GET_MODE (XEXP (SET_SRC (x), 0)) == GET_MODE (in_a))
796 cmp_src = XEXP (SET_SRC (x), 0);
798 /* Also check fully redundant comparisons, e.g.:
799 [(set (reg:SI)
800 (minus:SI (reg:SI) (reg:SI))))
801 (set (reg:CC flags)
802 (compare:CC (reg:SI) (reg:SI)))] */
803 else if (REG_P (in_b)
804 && GET_CODE (SET_SRC (x)) == MINUS
805 && rtx_equal_p (XEXP (SET_SRC (x), 0), in_a)
806 && rtx_equal_p (XEXP (SET_SRC (x), 1), in_b))
807 cmp_src = in_a;
809 else
810 return false;
812 /* Determine if we ought to use a different CC_MODE here. */
813 flags = maybe_select_cc_mode (cmp, cmp_src, in_b);
814 if (flags == NULL)
815 flags = gen_rtx_REG (cmp->orig_mode, targetm.flags_regnum);
817 /* Generate a new comparison for installation in the setter. */
818 rtx y = copy_rtx (cmp_src);
819 y = gen_rtx_COMPARE (GET_MODE (flags), y, in_b);
820 y = gen_rtx_SET (flags, y);
822 /* Canonicalize instruction to:
823 [(set (reg:CCM) (compare:CCM (operation) (immediate)))
824 (set (reg) (operation)] */
826 rtvec v = rtvec_alloc (2);
827 RTVEC_ELT (v, 0) = y;
828 RTVEC_ELT (v, 1) = x;
830 rtx pat = gen_rtx_PARALLEL (VOIDmode, v);
832 /* Succeed if the new instruction is valid. Note that we may have started
833 a change group within maybe_select_cc_mode, therefore we must continue. */
834 validate_change (insn, &PATTERN (insn), pat, true);
836 if (!apply_change_group ())
837 return false;
839 /* Success. Delete the compare insn... */
840 delete_insn (cmp->insn);
842 /* ... and any notes that are now invalid due to multiple sets. */
843 x = find_regno_note (insn, REG_UNUSED, targetm.flags_regnum);
844 if (x)
845 remove_note (insn, x);
846 x = find_reg_note (insn, REG_EQUAL, NULL);
847 if (x)
848 remove_note (insn, x);
849 x = find_reg_note (insn, REG_EQUIV, NULL);
850 if (x)
851 remove_note (insn, x);
853 return true;
856 /* Main entry point to the pass. */
858 static unsigned int
859 execute_compare_elim_after_reload (void)
861 df_analyze ();
863 gcc_checking_assert (!all_compares.exists ());
865 /* Locate all comparisons and their uses, and eliminate duplicates. */
866 find_comparisons ();
867 if (all_compares.exists ())
869 struct comparison *cmp;
870 size_t i;
872 /* Eliminate comparisons that are redundant with flags computation. */
873 FOR_EACH_VEC_ELT (all_compares, i, cmp)
875 try_eliminate_compare (cmp);
876 XDELETE (cmp);
879 all_compares.release ();
882 return 0;
885 namespace {
887 const pass_data pass_data_compare_elim_after_reload =
889 RTL_PASS, /* type */
890 "cmpelim", /* name */
891 OPTGROUP_NONE, /* optinfo_flags */
892 TV_NONE, /* tv_id */
893 0, /* properties_required */
894 0, /* properties_provided */
895 0, /* properties_destroyed */
896 0, /* todo_flags_start */
897 ( TODO_df_finish | TODO_df_verify ), /* todo_flags_finish */
900 class pass_compare_elim_after_reload : public rtl_opt_pass
902 public:
903 pass_compare_elim_after_reload (gcc::context *ctxt)
904 : rtl_opt_pass (pass_data_compare_elim_after_reload, ctxt)
907 /* opt_pass methods: */
908 virtual bool gate (function *)
910 /* Setting this target hook value is how a backend indicates the need. */
911 if (targetm.flags_regnum == INVALID_REGNUM)
912 return false;
913 return flag_compare_elim_after_reload;
916 virtual unsigned int execute (function *)
918 return execute_compare_elim_after_reload ();
921 }; // class pass_compare_elim_after_reload
923 } // anon namespace
925 rtl_opt_pass *
926 make_pass_compare_elim_after_reload (gcc::context *ctxt)
928 return new pass_compare_elim_after_reload (ctxt);