Fix bootstrap/PR63632
[official-gcc.git] / gcc / compare-elim.c
blob7e12e36896ed92403d34b6d02bd905e4ea8834d3
1 /* Post-reload compare elimination.
2 Copyright (C) 2010-2014 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) (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) (operation)
49 (set (reg:CCM) (compare:CCM (operation) (immediate)))]
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 "tm.h"
61 #include "rtl.h"
62 #include "tm_p.h"
63 #include "insn-config.h"
64 #include "recog.h"
65 #include "flags.h"
66 #include "basic-block.h"
67 #include "tree-pass.h"
68 #include "target.h"
69 #include "df.h"
70 #include "domwalk.h"
73 /* These structures describe a comparison and how it is used. */
75 /* The choice of maximum 3 uses comes from wanting to eliminate the two
76 duplicate compares from a three-way branch on the sign of a value.
77 This is also sufficient to eliminate the duplicate compare against the
78 high-part of a double-word comparison. */
79 #define MAX_CMP_USE 3
81 struct comparison_use
83 /* The instruction in which the result of the compare is used. */
84 rtx_insn *insn;
85 /* The location of the flags register within the use. */
86 rtx *loc;
87 /* The comparison code applied against the flags register. */
88 enum rtx_code code;
91 struct comparison
93 /* The comparison instruction. */
94 rtx_insn *insn;
96 /* The insn prior to the comparison insn that clobbers the flags. */
97 rtx_insn *prev_clobber;
99 /* The two values being compared. These will be either REGs or
100 constants. */
101 rtx in_a, in_b;
103 /* The REG_EH_REGION of the comparison. */
104 rtx eh_note;
106 /* Information about how this comparison is used. */
107 struct comparison_use uses[MAX_CMP_USE];
109 /* The original CC_MODE for this comparison. */
110 enum machine_mode orig_mode;
112 /* The number of uses identified for this comparison. */
113 unsigned short n_uses;
115 /* True if not all uses of this comparison have been identified.
116 This can happen either for overflowing the array above, or if
117 the flags register is used in some unusual context. */
118 bool missing_uses;
120 /* True if its inputs are still valid at the end of the block. */
121 bool inputs_valid;
124 typedef struct comparison *comparison_struct_p;
126 static vec<comparison_struct_p> all_compares;
128 /* Look for a "conforming" comparison, as defined above. If valid, return
129 the rtx for the COMPARE itself. */
131 static rtx
132 conforming_compare (rtx_insn *insn)
134 rtx set, src, dest;
136 set = single_set (insn);
137 if (set == NULL)
138 return NULL;
140 src = SET_SRC (set);
141 if (GET_CODE (src) != COMPARE)
142 return NULL;
144 dest = SET_DEST (set);
145 if (!REG_P (dest) || REGNO (dest) != targetm.flags_regnum)
146 return NULL;
148 if (REG_P (XEXP (src, 0))
149 && REG_P (XEXP (src, 0))
150 && (REG_P (XEXP (src, 1)) || CONSTANT_P (XEXP (src, 1))))
151 return src;
153 return NULL;
156 /* Look for a pattern of the "correct" form for an insn with a flags clobber
157 for which we may be able to eliminate a compare later. We're not looking
158 to validate any inputs at this time, merely see that the basic shape is
159 correct. The term "arithmetic" may be somewhat misleading... */
161 static bool
162 arithmetic_flags_clobber_p (rtx_insn *insn)
164 rtx pat, x;
166 if (!NONJUMP_INSN_P (insn))
167 return false;
168 pat = PATTERN (insn);
169 if (extract_asm_operands (pat))
170 return false;
172 if (GET_CODE (pat) == PARALLEL && XVECLEN (pat, 0) == 2)
174 x = XVECEXP (pat, 0, 0);
175 if (GET_CODE (x) != SET)
176 return false;
177 x = SET_DEST (x);
178 if (!REG_P (x))
179 return false;
181 x = XVECEXP (pat, 0, 1);
182 if (GET_CODE (x) == CLOBBER)
184 x = XEXP (x, 0);
185 if (REG_P (x) && REGNO (x) == targetm.flags_regnum)
186 return true;
190 return false;
193 /* Look for uses of FLAGS in INSN. If we find one we can analyze, record
194 it in CMP; otherwise indicate that we've missed a use. */
196 static void
197 find_flags_uses_in_insn (struct comparison *cmp, rtx_insn *insn)
199 df_ref use;
201 /* If we've already lost track of uses, don't bother collecting more. */
202 if (cmp->missing_uses)
203 return;
205 /* Find a USE of the flags register. */
206 FOR_EACH_INSN_USE (use, insn)
207 if (DF_REF_REGNO (use) == targetm.flags_regnum)
209 rtx x, *loc;
211 /* If this is an unusual use, quit. */
212 if (DF_REF_TYPE (use) != DF_REF_REG_USE)
213 goto fail;
215 /* If we've run out of slots to record uses, quit. */
216 if (cmp->n_uses == MAX_CMP_USE)
217 goto fail;
219 /* Unfortunately the location of the flags register, while present
220 in the reference structure, doesn't help. We need to find the
221 comparison code that is outer to the actual flags use. */
222 loc = DF_REF_LOC (use);
223 x = PATTERN (insn);
224 if (GET_CODE (x) == PARALLEL)
225 x = XVECEXP (x, 0, 0);
226 x = SET_SRC (x);
227 if (GET_CODE (x) == IF_THEN_ELSE)
228 x = XEXP (x, 0);
229 if (COMPARISON_P (x)
230 && loc == &XEXP (x, 0)
231 && XEXP (x, 1) == const0_rtx)
233 /* We've found a use of the flags that we understand. */
234 struct comparison_use *cuse = &cmp->uses[cmp->n_uses++];
235 cuse->insn = insn;
236 cuse->loc = loc;
237 cuse->code = GET_CODE (x);
239 else
240 goto fail;
242 return;
244 fail:
245 /* We failed to recognize this use of the flags register. */
246 cmp->missing_uses = true;
249 class find_comparison_dom_walker : public dom_walker
251 public:
252 find_comparison_dom_walker (cdi_direction direction)
253 : dom_walker (direction) {}
255 virtual void before_dom_children (basic_block);
258 /* Identify comparison instructions within BB. If the flags from the last
259 compare in the BB is live at the end of the block, install the compare
260 in BB->AUX. Called via dom_walker.walk (). */
262 void
263 find_comparison_dom_walker::before_dom_children (basic_block bb)
265 struct comparison *last_cmp;
266 rtx_insn *insn, *next, *last_clobber;
267 bool last_cmp_valid;
268 bool need_purge = false;
269 bitmap killed;
271 killed = BITMAP_ALLOC (NULL);
273 /* The last comparison that was made. Will be reset to NULL
274 once the flags are clobbered. */
275 last_cmp = NULL;
277 /* True iff the last comparison has not been clobbered, nor
278 have its inputs. Used to eliminate duplicate compares. */
279 last_cmp_valid = false;
281 /* The last insn that clobbered the flags, if that insn is of
282 a form that may be valid for eliminating a following compare.
283 To be reset to NULL once the flags are set otherwise. */
284 last_clobber = NULL;
286 /* Propagate the last live comparison throughout the extended basic block. */
287 if (single_pred_p (bb))
289 last_cmp = (struct comparison *) single_pred (bb)->aux;
290 if (last_cmp)
291 last_cmp_valid = last_cmp->inputs_valid;
294 for (insn = BB_HEAD (bb); insn; insn = next)
296 rtx src;
298 next = (insn == BB_END (bb) ? NULL : NEXT_INSN (insn));
299 if (!NONDEBUG_INSN_P (insn))
300 continue;
302 /* Compute the set of registers modified by this instruction. */
303 bitmap_clear (killed);
304 df_simulate_find_defs (insn, killed);
306 src = conforming_compare (insn);
307 if (src)
309 enum machine_mode src_mode = GET_MODE (src);
310 rtx eh_note = NULL;
312 if (flag_non_call_exceptions)
313 eh_note = find_reg_note (insn, REG_EH_REGION, NULL);
315 if (!last_cmp_valid)
316 goto dont_delete;
318 /* Take care that it's in the same EH region. */
319 if (flag_non_call_exceptions
320 && !rtx_equal_p (eh_note, last_cmp->eh_note))
321 goto dont_delete;
323 /* Make sure the compare is redundant with the previous. */
324 if (!rtx_equal_p (last_cmp->in_a, XEXP (src, 0))
325 || !rtx_equal_p (last_cmp->in_b, XEXP (src, 1)))
326 goto dont_delete;
328 /* New mode must be compatible with the previous compare mode. */
330 enum machine_mode new_mode
331 = targetm.cc_modes_compatible (last_cmp->orig_mode, src_mode);
332 if (new_mode == VOIDmode)
333 goto dont_delete;
335 if (new_mode != last_cmp->orig_mode)
337 rtx x, flags = gen_rtx_REG (src_mode, targetm.flags_regnum);
339 /* Generate new comparison for substitution. */
340 x = gen_rtx_COMPARE (new_mode, XEXP (src, 0), XEXP (src, 1));
341 x = gen_rtx_SET (VOIDmode, flags, x);
343 if (!validate_change (last_cmp->insn,
344 &PATTERN (last_cmp->insn), x, false))
345 goto dont_delete;
347 last_cmp->orig_mode = new_mode;
351 /* All tests and substitutions succeeded! */
352 if (eh_note)
353 need_purge = true;
354 delete_insn (insn);
355 continue;
357 dont_delete:
358 last_cmp = XCNEW (struct comparison);
359 last_cmp->insn = insn;
360 last_cmp->prev_clobber = last_clobber;
361 last_cmp->in_a = XEXP (src, 0);
362 last_cmp->in_b = XEXP (src, 1);
363 last_cmp->eh_note = eh_note;
364 last_cmp->orig_mode = src_mode;
365 all_compares.safe_push (last_cmp);
367 /* It's unusual, but be prepared for comparison patterns that
368 also clobber an input, or perhaps a scratch. */
369 last_clobber = NULL;
370 last_cmp_valid = true;
373 /* Notice if this instruction kills the flags register. */
374 else if (bitmap_bit_p (killed, targetm.flags_regnum))
376 /* See if this insn could be the "clobber" that eliminates
377 a future comparison. */
378 last_clobber = (arithmetic_flags_clobber_p (insn) ? insn : NULL);
380 /* In either case, the previous compare is no longer valid. */
381 last_cmp = NULL;
382 last_cmp_valid = false;
383 continue;
386 /* Notice if this instruction uses the flags register. */
387 else if (last_cmp)
388 find_flags_uses_in_insn (last_cmp, insn);
390 /* Notice if any of the inputs to the comparison have changed. */
391 if (last_cmp_valid
392 && (bitmap_bit_p (killed, REGNO (last_cmp->in_a))
393 || (REG_P (last_cmp->in_b)
394 && bitmap_bit_p (killed, REGNO (last_cmp->in_b)))))
395 last_cmp_valid = false;
398 BITMAP_FREE (killed);
400 /* Remember the live comparison for subsequent members of
401 the extended basic block. */
402 if (last_cmp)
404 bb->aux = last_cmp;
405 last_cmp->inputs_valid = last_cmp_valid;
407 /* Look to see if the flags register is live outgoing here, and
408 incoming to any successor not part of the extended basic block. */
409 if (bitmap_bit_p (df_get_live_out (bb), targetm.flags_regnum))
411 edge e;
412 edge_iterator ei;
414 FOR_EACH_EDGE (e, ei, bb->succs)
416 basic_block dest = e->dest;
417 if (bitmap_bit_p (df_get_live_in (bb),
418 targetm.flags_regnum)
419 && !single_pred_p (dest))
421 last_cmp->missing_uses = true;
422 break;
428 /* If we deleted a compare with a REG_EH_REGION note, we may need to
429 remove EH edges. */
430 if (need_purge)
431 purge_dead_edges (bb);
434 /* Find all comparisons in the function. */
436 static void
437 find_comparisons (void)
439 calculate_dominance_info (CDI_DOMINATORS);
441 find_comparison_dom_walker (CDI_DOMINATORS)
442 .walk (cfun->cfg->x_entry_block_ptr);
444 clear_aux_for_blocks ();
445 free_dominance_info (CDI_DOMINATORS);
448 /* Select an alternate CC_MODE for a comparison insn comparing A and B.
449 Note that inputs are almost certainly different than the IN_A and IN_B
450 stored in CMP -- we're called while attempting to eliminate the compare
451 after all. Return the new FLAGS rtx if successful, else return NULL.
452 Note that this function may start a change group. */
454 static rtx
455 maybe_select_cc_mode (struct comparison *cmp, rtx a ATTRIBUTE_UNUSED,
456 rtx b ATTRIBUTE_UNUSED)
458 enum machine_mode sel_mode;
459 const int n = cmp->n_uses;
460 rtx flags = NULL;
462 #ifndef SELECT_CC_MODE
463 /* Minimize code differences when this target macro is undefined. */
464 return NULL;
465 #define SELECT_CC_MODE(A,B,C) (gcc_unreachable (), VOIDmode)
466 #endif
468 /* If we don't have access to all of the uses, we can't validate. */
469 if (cmp->missing_uses || n == 0)
470 return NULL;
472 /* Find a new mode that works for all of the uses. Special case the
473 common case of exactly one use. */
474 if (n == 1)
476 sel_mode = SELECT_CC_MODE (cmp->uses[0].code, a, b);
477 if (sel_mode != cmp->orig_mode)
479 flags = gen_rtx_REG (sel_mode, targetm.flags_regnum);
480 validate_change (cmp->uses[0].insn, cmp->uses[0].loc, flags, true);
483 else
485 int i;
487 sel_mode = SELECT_CC_MODE (cmp->uses[0].code, a, b);
488 for (i = 1; i < n; ++i)
490 enum machine_mode new_mode;
491 new_mode = SELECT_CC_MODE (cmp->uses[i].code, a, b);
492 if (new_mode != sel_mode)
494 sel_mode = targetm.cc_modes_compatible (sel_mode, new_mode);
495 if (sel_mode == VOIDmode)
496 return NULL;
500 if (sel_mode != cmp->orig_mode)
502 flags = gen_rtx_REG (sel_mode, targetm.flags_regnum);
503 for (i = 0; i < n; ++i)
504 validate_change (cmp->uses[i].insn, cmp->uses[i].loc, flags, true);
508 return flags;
511 /* Attempt to replace a comparison with a prior arithmetic insn that can
512 compute the same flags value as the comparison itself. Return true if
513 successful, having made all rtl modifications necessary. */
515 static bool
516 try_eliminate_compare (struct comparison *cmp)
518 rtx_insn *insn, *bb_head;
519 rtx x, flags, in_a, cmp_src;
521 /* We must have found an interesting "clobber" preceding the compare. */
522 if (cmp->prev_clobber == NULL)
523 return false;
525 /* ??? For the moment we don't handle comparisons for which IN_B
526 is a register. We accepted these during initial comparison
527 recognition in order to eliminate duplicate compares.
528 An improvement here would be to handle x = a - b; if (a cmp b). */
529 if (!CONSTANT_P (cmp->in_b))
530 return false;
532 /* Verify that IN_A is not clobbered in between CMP and PREV_CLOBBER.
533 Given that this target requires this pass, we can assume that most
534 insns do clobber the flags, and so the distance between the compare
535 and the clobber is likely to be small. */
536 /* ??? This is one point at which one could argue that DF_REF_CHAIN would
537 be useful, but it is thought to be too heavy-weight a solution here. */
539 in_a = cmp->in_a;
540 insn = cmp->insn;
541 bb_head = BB_HEAD (BLOCK_FOR_INSN (insn));
542 for (insn = PREV_INSN (insn);
543 insn != cmp->prev_clobber;
544 insn = PREV_INSN (insn))
546 const int abnormal_flags
547 = (DF_REF_CONDITIONAL | DF_REF_PARTIAL | DF_REF_MAY_CLOBBER
548 | DF_REF_MUST_CLOBBER | DF_REF_SIGN_EXTRACT
549 | DF_REF_ZERO_EXTRACT | DF_REF_STRICT_LOW_PART
550 | DF_REF_PRE_POST_MODIFY);
551 df_ref def;
553 /* Note that the BB_HEAD is always either a note or a label, but in
554 any case it means that IN_A is defined outside the block. */
555 if (insn == bb_head)
556 return false;
557 if (NOTE_P (insn) || DEBUG_INSN_P (insn))
558 continue;
560 /* Find a possible def of IN_A in INSN. */
561 FOR_EACH_INSN_DEF (def, insn)
562 if (DF_REF_REGNO (def) == REGNO (in_a))
563 break;
565 /* No definitions of IN_A; continue searching. */
566 if (def == NULL)
567 continue;
569 /* Bail if this is not a totally normal set of IN_A. */
570 if (DF_REF_IS_ARTIFICIAL (def))
571 return false;
572 if (DF_REF_FLAGS (def) & abnormal_flags)
573 return false;
575 /* We've found an insn between the compare and the clobber that sets
576 IN_A. Given that pass_cprop_hardreg has not yet run, we still find
577 situations in which we can usefully look through a copy insn. */
578 x = single_set (insn);
579 if (x == NULL)
580 return false;
581 in_a = SET_SRC (x);
582 if (!REG_P (in_a))
583 return false;
586 /* We've reached PREV_CLOBBER without finding a modification of IN_A.
587 Validate that PREV_CLOBBER itself does in fact refer to IN_A. Do
588 recall that we've already validated the shape of PREV_CLOBBER. */
589 x = XVECEXP (PATTERN (insn), 0, 0);
590 if (rtx_equal_p (SET_DEST (x), in_a))
591 cmp_src = SET_SRC (x);
593 /* Also check operations with implicit extensions, e.g.:
594 [(set (reg:DI)
595 (zero_extend:DI (plus:SI (reg:SI)(reg:SI))))
596 (set (reg:CCZ flags)
597 (compare:CCZ
598 (plus:SI (reg:SI)(reg:SI))
599 (const_int 0)))] */
600 else if (REG_P (SET_DEST (x))
601 && REG_P (in_a)
602 && REGNO (SET_DEST (x)) == REGNO (in_a)
603 && (GET_CODE (SET_SRC (x)) == ZERO_EXTEND
604 || GET_CODE (SET_SRC (x)) == SIGN_EXTEND)
605 && GET_MODE (XEXP (SET_SRC (x), 0)) == GET_MODE (in_a))
606 cmp_src = XEXP (SET_SRC (x), 0);
607 else
608 return false;
610 /* Determine if we ought to use a different CC_MODE here. */
611 flags = maybe_select_cc_mode (cmp, cmp_src, cmp->in_b);
612 if (flags == NULL)
613 flags = gen_rtx_REG (cmp->orig_mode, targetm.flags_regnum);
615 /* Generate a new comparison for installation in the setter. */
616 x = copy_rtx (cmp_src);
617 x = gen_rtx_COMPARE (GET_MODE (flags), x, cmp->in_b);
618 x = gen_rtx_SET (VOIDmode, flags, x);
620 /* Succeed if the new instruction is valid. Note that we may have started
621 a change group within maybe_select_cc_mode, therefore we must continue. */
622 validate_change (insn, &XVECEXP (PATTERN (insn), 0, 1), x, true);
623 if (!apply_change_group ())
624 return false;
626 /* Success. Delete the compare insn... */
627 delete_insn (cmp->insn);
629 /* ... and any notes that are now invalid due to multiple sets. */
630 x = find_regno_note (insn, REG_UNUSED, targetm.flags_regnum);
631 if (x)
632 remove_note (insn, x);
633 x = find_reg_note (insn, REG_EQUAL, NULL);
634 if (x)
635 remove_note (insn, x);
636 x = find_reg_note (insn, REG_EQUIV, NULL);
637 if (x)
638 remove_note (insn, x);
640 return true;
643 /* Main entry point to the pass. */
645 static unsigned int
646 execute_compare_elim_after_reload (void)
648 df_analyze ();
650 gcc_checking_assert (!all_compares.exists ());
652 /* Locate all comparisons and their uses, and eliminate duplicates. */
653 find_comparisons ();
654 if (all_compares.exists ())
656 struct comparison *cmp;
657 size_t i;
659 /* Eliminate comparisons that are redundant with flags computation. */
660 FOR_EACH_VEC_ELT (all_compares, i, cmp)
662 try_eliminate_compare (cmp);
663 XDELETE (cmp);
666 all_compares.release ();
669 return 0;
672 namespace {
674 const pass_data pass_data_compare_elim_after_reload =
676 RTL_PASS, /* type */
677 "cmpelim", /* name */
678 OPTGROUP_NONE, /* optinfo_flags */
679 TV_NONE, /* tv_id */
680 0, /* properties_required */
681 0, /* properties_provided */
682 0, /* properties_destroyed */
683 0, /* todo_flags_start */
684 ( TODO_df_finish | TODO_df_verify ), /* todo_flags_finish */
687 class pass_compare_elim_after_reload : public rtl_opt_pass
689 public:
690 pass_compare_elim_after_reload (gcc::context *ctxt)
691 : rtl_opt_pass (pass_data_compare_elim_after_reload, ctxt)
694 /* opt_pass methods: */
695 virtual bool gate (function *)
697 /* Setting this target hook value is how a backend indicates the need. */
698 if (targetm.flags_regnum == INVALID_REGNUM)
699 return false;
700 return flag_compare_elim_after_reload;
703 virtual unsigned int execute (function *)
705 return execute_compare_elim_after_reload ();
708 }; // class pass_compare_elim_after_reload
710 } // anon namespace
712 rtl_opt_pass *
713 make_pass_compare_elim_after_reload (gcc::context *ctxt)
715 return new pass_compare_elim_after_reload (ctxt);