Line data Source code
1 : /* Post-reload compare elimination.
2 : Copyright (C) 2010-2026 Free Software Foundation, Inc.
3 :
4 : This file is part of GCC.
5 :
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.
10 :
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.
15 :
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/>. */
19 :
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.
26 :
27 : This is a small pass intended to provide comparison elimination similar to
28 : what was available via NOTICE_UPDATE_CC for cc0 targets.
29 :
30 : This pass assumes:
31 :
32 : (0) CBRANCH/CSTORE etc have been split in pass_split_after_reload.
33 :
34 : (1) All comparison patterns are represented as
35 :
36 : [(set (reg:CC) (compare:CC (reg) (reg_or_immediate)))]
37 :
38 : (2) All insn patterns that modify the flags are represented as
39 :
40 : [(set (reg) (operation)
41 : (clobber (reg:CC))]
42 :
43 : (3) If an insn of form (2) can usefully set the flags, there is
44 : another pattern of the form
45 :
46 : [(set (reg:CCM) (compare:CCM (operation) (immediate)))
47 : (set (reg) (operation)]
48 :
49 : The mode CCM will be chosen as if by SELECT_CC_MODE.
50 :
51 : Note that unlike NOTICE_UPDATE_CC, we do not handle memory operands.
52 : This could be handled as a future enhancement.
53 : */
54 :
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"
70 :
71 :
72 : /* These structures describe a comparison and how it is used. */
73 :
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
79 :
80 : struct comparison_use
81 : {
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;
88 : };
89 :
90 : struct comparison
91 : {
92 : /* The comparison instruction. */
93 : rtx_insn *insn;
94 :
95 : /* The insn prior to the comparison insn that clobbers the flags. */
96 : rtx_insn *prev_clobber;
97 :
98 : /* The insn prior to the comparison insn that sets in_a REG. */
99 : rtx_insn *in_a_setter;
100 :
101 : /* The two values being compared. These will be either REGs or
102 : constants. */
103 : rtx in_a, in_b;
104 :
105 : /* The REG_EH_REGION of the comparison. */
106 : rtx eh_note;
107 :
108 : /* Information about how this comparison is used. */
109 : struct comparison_use uses[MAX_CMP_USE];
110 :
111 : /* The original CC_MODE for this comparison. */
112 : machine_mode orig_mode;
113 :
114 : /* The number of uses identified for this comparison. */
115 : unsigned short n_uses;
116 :
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;
121 :
122 : /* True if its inputs are still valid at the end of the block. */
123 : bool inputs_valid;
124 :
125 : /* Whether IN_A is wrapped in a NOT before being compared. */
126 : bool not_in_a;
127 : };
128 :
129 : static vec<comparison *> all_compares;
130 :
131 : /* Return whether X is a NOT unary expression. */
132 :
133 : static bool
134 12197614 : is_not (rtx x)
135 : {
136 12197614 : return GET_CODE (x) == NOT;
137 : }
138 :
139 : /* Strip a NOT unary expression around X, if any. */
140 :
141 : static rtx
142 8799955 : strip_not (rtx x)
143 : {
144 0 : if (is_not (x))
145 0 : return XEXP (x, 0);
146 :
147 : return x;
148 : }
149 :
150 : /* Look for a "conforming" comparison, as defined above. If valid, return
151 : the rtx for the COMPARE itself. */
152 :
153 : static rtx
154 58170335 : conforming_compare (rtx_insn *insn)
155 : {
156 58170335 : rtx set, src, dest;
157 :
158 58170335 : set = single_set (insn);
159 58170335 : if (set == NULL)
160 : return NULL;
161 :
162 54138626 : src = SET_SRC (set);
163 54138626 : if (GET_CODE (src) != COMPARE)
164 : return NULL;
165 :
166 4742044 : dest = SET_DEST (set);
167 4742044 : if (!REG_P (dest) || REGNO (dest) != targetm.flags_regnum)
168 : return NULL;
169 :
170 4742044 : if (!REG_P (strip_not (XEXP (src, 0))))
171 : return NULL;
172 :
173 3540368 : if (CONSTANT_P (XEXP (src, 1)) || REG_P (XEXP (src, 1)))
174 : return src;
175 :
176 142709 : if (GET_CODE (XEXP (src, 1)) == UNSPEC)
177 : {
178 0 : for (int i = 0; i < XVECLEN (XEXP (src, 1), 0); i++)
179 0 : if (!REG_P (XVECEXP (XEXP (src, 1), 0, i)))
180 : return NULL;
181 : return src;
182 : }
183 :
184 : return NULL;
185 : }
186 :
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... */
191 :
192 : static bool
193 11734482 : arithmetic_flags_clobber_p (rtx_insn *insn)
194 : {
195 11734482 : rtx pat, x;
196 :
197 11734482 : if (!NONJUMP_INSN_P (insn))
198 : return false;
199 7109454 : pat = PATTERN (insn);
200 7109454 : if (asm_noperands (pat) >= 0)
201 : return false;
202 :
203 7021207 : if (GET_CODE (pat) == PARALLEL && XVECLEN (pat, 0) == 2)
204 : {
205 5394881 : x = XVECEXP (pat, 0, 0);
206 5394881 : if (GET_CODE (x) != SET)
207 : return false;
208 5394874 : x = SET_DEST (x);
209 5394874 : if (!REG_P (x))
210 : return false;
211 :
212 5240045 : x = XVECEXP (pat, 0, 1);
213 5240045 : if (GET_CODE (x) == CLOBBER)
214 : {
215 5024620 : x = XEXP (x, 0);
216 5024620 : if (REG_P (x) && REGNO (x) == targetm.flags_regnum)
217 : return true;
218 : }
219 : }
220 :
221 : return false;
222 : }
223 :
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. */
226 :
227 : static void
228 14173967 : find_flags_uses_in_insn (struct comparison *cmp, rtx_insn *insn)
229 : {
230 14173967 : df_ref use;
231 :
232 : /* If we've already lost track of uses, don't bother collecting more. */
233 14173967 : if (cmp->missing_uses)
234 : return;
235 :
236 : /* Find a USE of the flags register. */
237 30396060 : FOR_EACH_INSN_USE (use, insn)
238 16253094 : if (DF_REF_REGNO (use) == targetm.flags_regnum)
239 : {
240 3445372 : rtx x, *loc;
241 :
242 : /* If this is an unusual use, quit. */
243 3445372 : if (DF_REF_TYPE (use) != DF_REF_REG_USE)
244 0 : goto fail;
245 :
246 : /* If we've run out of slots to record uses, quit. */
247 3445372 : if (cmp->n_uses == MAX_CMP_USE)
248 1584 : goto fail;
249 :
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 3443788 : loc = DF_REF_LOC (use);
254 3443788 : x = PATTERN (insn);
255 3443788 : if (GET_CODE (x) == PARALLEL)
256 29254 : x = XVECEXP (x, 0, 0);
257 3443788 : if (GET_CODE (x) == SET)
258 3443788 : x = SET_SRC (x);
259 3443788 : if (GET_CODE (x) == IF_THEN_ELSE)
260 3327776 : x = XEXP (x, 0);
261 3443788 : if (GET_CODE (x) == COND_EXEC)
262 0 : x = COND_EXEC_TEST (x);
263 3443788 : if (COMPARISON_P (x)
264 3423423 : && loc == &XEXP (x, 0)
265 3417643 : && XEXP (x, 1) == const0_rtx)
266 : {
267 : /* We've found a use of the flags that we understand. */
268 3417643 : struct comparison_use *cuse = &cmp->uses[cmp->n_uses++];
269 3417643 : cuse->insn = insn;
270 3417643 : cuse->loc = loc;
271 3417643 : cuse->code = GET_CODE (x);
272 : }
273 : else
274 26145 : goto fail;
275 : }
276 : return;
277 :
278 27729 : fail:
279 : /* We failed to recognize this use of the flags register. */
280 27729 : cmp->missing_uses = true;
281 : }
282 :
283 2087372 : class find_comparison_dom_walker : public dom_walker
284 : {
285 : public:
286 1043686 : find_comparison_dom_walker (cdi_direction direction)
287 2087372 : : dom_walker (direction) {}
288 :
289 : edge before_dom_children (basic_block) final override;
290 : };
291 :
292 : /* Return true if conforming COMPARE with EH_NOTE is redundant with comparison
293 : CMP and can thus be eliminated. */
294 :
295 : static bool
296 666991 : can_eliminate_compare (rtx compare, rtx eh_note, struct comparison *cmp)
297 : {
298 : /* Take care that it's in the same EH region. */
299 666991 : if (cfun->can_throw_non_call_exceptions
300 666991 : && !rtx_equal_p (eh_note, cmp->eh_note))
301 : return false;
302 :
303 : /* Make sure the compare is redundant with the previous. */
304 666991 : if (!rtx_equal_p (strip_not (XEXP (compare, 0)), cmp->in_a)
305 666991 : || !rtx_equal_p (XEXP (compare, 1), cmp->in_b))
306 660252 : return false;
307 :
308 6739 : if (is_not (XEXP (compare, 0)) != cmp->not_in_a)
309 : return false;
310 :
311 : /* New mode must be compatible with the previous compare mode. */
312 6739 : machine_mode new_mode
313 6739 : = targetm.cc_modes_compatible (GET_MODE (compare), cmp->orig_mode);
314 :
315 6739 : if (new_mode == VOIDmode)
316 : return false;
317 :
318 6739 : if (cmp->orig_mode != new_mode)
319 : {
320 : /* Generate new comparison for substitution. */
321 1194 : rtx flags = gen_rtx_REG (new_mode, targetm.flags_regnum);
322 1194 : rtx x = gen_rtx_COMPARE (new_mode, cmp->in_a, cmp->in_b);
323 1194 : x = gen_rtx_SET (flags, x);
324 :
325 1194 : if (!validate_change (cmp->insn, &PATTERN (cmp->insn), x, false))
326 : return false;
327 :
328 1194 : cmp->orig_mode = new_mode;
329 : }
330 :
331 : return true;
332 : }
333 :
334 : /* Identify comparison instructions within BB. If the flags from the last
335 : compare in the BB is live at the end of the block, install the compare
336 : in BB->AUX. Called via dom_walker.walk (). */
337 :
338 : edge
339 12038533 : find_comparison_dom_walker::before_dom_children (basic_block bb)
340 : {
341 12038533 : rtx_insn *insn, *next;
342 12038533 : bool need_purge = false;
343 12038533 : rtx_insn *last_setter[FIRST_PSEUDO_REGISTER];
344 :
345 : /* The last comparison that was made. Will be reset to NULL
346 : once the flags are clobbered. */
347 12038533 : struct comparison *last_cmp = NULL;
348 :
349 : /* True iff the last comparison has not been clobbered, nor
350 : have its inputs. Used to eliminate duplicate compares. */
351 12038533 : bool last_cmp_valid = false;
352 :
353 : /* The last insn that clobbered the flags, if that insn is of
354 : a form that may be valid for eliminating a following compare.
355 : To be reset to NULL once the flags are set otherwise. */
356 12038533 : rtx_insn *last_clobber = NULL;
357 :
358 : /* Propagate the last live comparison throughout the extended basic block. */
359 12038533 : if (single_pred_p (bb))
360 : {
361 8298201 : last_cmp = (struct comparison *) single_pred (bb)->aux;
362 8298201 : if (last_cmp)
363 4150553 : last_cmp_valid = last_cmp->inputs_valid;
364 : }
365 :
366 12038533 : memset (last_setter, 0, sizeof (last_setter));
367 142037244 : for (insn = BB_HEAD (bb); insn; insn = next)
368 : {
369 129998711 : rtx src;
370 :
371 129998711 : next = (insn == BB_END (bb) ? NULL : NEXT_INSN (insn));
372 129998711 : if (!NONDEBUG_INSN_P (insn))
373 71828376 : continue;
374 :
375 58170335 : src = conforming_compare (insn);
376 58170335 : if (src)
377 : {
378 3397659 : rtx eh_note = NULL;
379 :
380 3397659 : if (cfun->can_throw_non_call_exceptions)
381 588575 : eh_note = find_reg_note (insn, REG_EH_REGION, NULL);
382 :
383 3397659 : if (last_cmp_valid && can_eliminate_compare (src, eh_note, last_cmp))
384 : {
385 6739 : if (eh_note)
386 0 : need_purge = true;
387 6739 : delete_insn (insn);
388 6739 : continue;
389 : }
390 :
391 3390920 : last_cmp = XCNEW (struct comparison);
392 3390920 : last_cmp->insn = insn;
393 3390920 : last_cmp->prev_clobber = last_clobber;
394 3390920 : last_cmp->in_a = strip_not (XEXP (src, 0));
395 3390920 : last_cmp->in_b = XEXP (src, 1);
396 3390920 : last_cmp->not_in_a = is_not (XEXP (src, 0));
397 3390920 : last_cmp->eh_note = eh_note;
398 3390920 : last_cmp->orig_mode = GET_MODE (src);
399 3390920 : if (last_cmp->in_b == const0_rtx
400 3390920 : && last_setter[REGNO (last_cmp->in_a)])
401 : {
402 929389 : rtx set = single_set (last_setter[REGNO (last_cmp->in_a)]);
403 929389 : if (set && rtx_equal_p (SET_DEST (set), last_cmp->in_a))
404 854485 : last_cmp->in_a_setter = last_setter[REGNO (last_cmp->in_a)];
405 : }
406 3390920 : all_compares.safe_push (last_cmp);
407 :
408 : /* It's unusual, but be prepared for comparison patterns that
409 : also clobber an input, or perhaps a scratch. */
410 3390920 : last_clobber = NULL;
411 3390920 : last_cmp_valid = true;
412 : }
413 :
414 : else
415 : {
416 : /* Notice if this instruction uses the flags register. */
417 54772676 : if (last_cmp)
418 14173967 : find_flags_uses_in_insn (last_cmp, insn);
419 :
420 : /* Notice if this instruction kills the flags register. */
421 54772676 : df_ref def;
422 142434840 : FOR_EACH_INSN_DEF (def, insn)
423 99396646 : if (DF_REF_REGNO (def) == targetm.flags_regnum)
424 : {
425 : /* See if this insn could be the "clobber" that eliminates
426 : a future comparison. */
427 16713696 : last_clobber = (arithmetic_flags_clobber_p (insn)
428 11734482 : ? insn : NULL);
429 :
430 : /* In either case, the previous compare is no longer valid. */
431 11734482 : last_cmp = NULL;
432 11734482 : last_cmp_valid = false;
433 11734482 : break;
434 : }
435 : }
436 :
437 : /* Notice if any of the inputs to the comparison have changed
438 : and remember last insn that sets each register. */
439 58163596 : df_ref def;
440 478637653 : FOR_EACH_INSN_DEF (def, insn)
441 : {
442 420474057 : if (last_cmp_valid
443 420474057 : && (DF_REF_REGNO (def) == REGNO (last_cmp->in_a)
444 8038657 : || (REG_P (last_cmp->in_b)
445 2278233 : && DF_REF_REGNO (def) == REGNO (last_cmp->in_b))))
446 : last_cmp_valid = false;
447 420474057 : last_setter[DF_REF_REGNO (def)] = insn;
448 : }
449 : }
450 :
451 : /* Remember the live comparison for subsequent members of
452 : the extended basic block. */
453 12038533 : if (last_cmp)
454 : {
455 4508782 : bb->aux = last_cmp;
456 4508782 : last_cmp->inputs_valid = last_cmp_valid;
457 :
458 : /* Look to see if the flags register is live outgoing here, and
459 : incoming to any successor not part of the extended basic block. */
460 4508782 : if (bitmap_bit_p (df_get_live_out (bb), targetm.flags_regnum))
461 : {
462 23200 : edge e;
463 23200 : edge_iterator ei;
464 :
465 69525 : FOR_EACH_EDGE (e, ei, bb->succs)
466 : {
467 46562 : basic_block dest = e->dest;
468 46562 : if (bitmap_bit_p (df_get_live_in (bb), targetm.flags_regnum)
469 48202 : && !single_pred_p (dest))
470 : {
471 237 : last_cmp->missing_uses = true;
472 237 : break;
473 : }
474 : }
475 : }
476 : }
477 :
478 : /* If we deleted a compare with a REG_EH_REGION note, we may need to
479 : remove EH edges. */
480 12038533 : if (need_purge)
481 0 : purge_dead_edges (bb);
482 :
483 12038533 : return NULL;
484 : }
485 :
486 : /* Find all comparisons in the function. */
487 :
488 : static void
489 1043686 : find_comparisons (void)
490 : {
491 1043686 : calculate_dominance_info (CDI_DOMINATORS);
492 :
493 1043686 : find_comparison_dom_walker (CDI_DOMINATORS)
494 1043686 : .walk (cfun->cfg->x_entry_block_ptr);
495 :
496 1043686 : clear_aux_for_blocks ();
497 1043686 : free_dominance_info (CDI_DOMINATORS);
498 1043686 : }
499 :
500 : /* Select an alternate CC_MODE for a comparison insn comparing A and B.
501 : Note that inputs are almost certainly different than the IN_A and IN_B
502 : stored in CMP -- we're called while attempting to eliminate the compare
503 : after all. Return the new FLAGS rtx if successful, else return NULL.
504 : Note that this function may start a change group. */
505 :
506 : static rtx
507 760057 : maybe_select_cc_mode (struct comparison *cmp, rtx a ATTRIBUTE_UNUSED,
508 : rtx b ATTRIBUTE_UNUSED)
509 : {
510 760057 : machine_mode sel_mode;
511 760057 : const int n = cmp->n_uses;
512 760057 : rtx flags = NULL;
513 :
514 : #ifndef SELECT_CC_MODE
515 : /* Minimize code differences when this target macro is undefined. */
516 : return NULL;
517 : #define SELECT_CC_MODE(A,B,C) (gcc_unreachable (), VOIDmode)
518 : #endif
519 :
520 : /* If we don't have access to all of the uses, we can't validate. */
521 760057 : if (cmp->missing_uses || n == 0)
522 : return NULL;
523 :
524 : /* Find a new mode that works for all of the uses. Special case the
525 : common case of exactly one use. */
526 759292 : if (n == 1)
527 : {
528 753292 : sel_mode = SELECT_CC_MODE (cmp->uses[0].code, a, b);
529 753292 : if (sel_mode != cmp->orig_mode)
530 : {
531 1366 : flags = gen_rtx_REG (sel_mode, targetm.flags_regnum);
532 1366 : validate_change (cmp->uses[0].insn, cmp->uses[0].loc, flags, true);
533 : }
534 : }
535 : else
536 : {
537 6000 : int i;
538 :
539 6000 : sel_mode = SELECT_CC_MODE (cmp->uses[0].code, a, b);
540 12094 : for (i = 1; i < n; ++i)
541 : {
542 6094 : machine_mode new_mode = SELECT_CC_MODE (cmp->uses[i].code, a, b);
543 6094 : if (new_mode != sel_mode)
544 : {
545 4704 : sel_mode = targetm.cc_modes_compatible (sel_mode, new_mode);
546 4704 : if (sel_mode == VOIDmode)
547 : return NULL;
548 : }
549 : }
550 :
551 6000 : if (sel_mode != cmp->orig_mode)
552 : {
553 0 : flags = gen_rtx_REG (sel_mode, targetm.flags_regnum);
554 0 : for (i = 0; i < n; ++i)
555 0 : validate_change (cmp->uses[i].insn, cmp->uses[i].loc, flags, true);
556 : }
557 : }
558 :
559 : return flags;
560 : }
561 :
562 : /* Return a register RTX holding the same value at START as REG at END, or
563 : NULL_RTX if there is none. */
564 :
565 : static rtx
566 1390376 : equivalent_reg_at_start (rtx reg, rtx_insn *end, rtx_insn *start)
567 : {
568 1390376 : machine_mode orig_mode = GET_MODE (reg);
569 1390376 : rtx_insn *bb_head = BB_HEAD (BLOCK_FOR_INSN (end));
570 :
571 3219898 : for (rtx_insn *insn = PREV_INSN (end);
572 3219898 : insn != start;
573 1829522 : insn = PREV_INSN (insn))
574 : {
575 1955804 : const int abnormal_flags
576 : = (DF_REF_CONDITIONAL | DF_REF_PARTIAL | DF_REF_MAY_CLOBBER
577 : | DF_REF_MUST_CLOBBER | DF_REF_SIGN_EXTRACT
578 : | DF_REF_ZERO_EXTRACT | DF_REF_STRICT_LOW_PART
579 : | DF_REF_PRE_POST_MODIFY);
580 1955804 : df_ref def;
581 :
582 : /* Note that the BB_HEAD is always either a note or a label, but in
583 : any case it means that REG is defined outside the block. */
584 1955804 : if (insn == bb_head)
585 : return NULL_RTX;
586 1955804 : if (NOTE_P (insn) || DEBUG_INSN_P (insn))
587 1572201 : continue;
588 :
589 : /* Find a possible def of REG in INSN. */
590 550028 : FOR_EACH_INSN_DEF (def, insn)
591 303068 : if (DF_REF_REGNO (def) == REGNO (reg))
592 : break;
593 :
594 : /* No definitions of REG; continue searching. */
595 383603 : if (def == NULL)
596 246960 : continue;
597 :
598 : /* Bail if this is not a totally normal set of REG. */
599 136643 : if (DF_REF_IS_ARTIFICIAL (def))
600 : return NULL_RTX;
601 136643 : if (DF_REF_FLAGS (def) & abnormal_flags)
602 : return NULL_RTX;
603 :
604 : /* We've found an insn between the compare and the clobber that sets
605 : REG. Given that pass_cprop_hardreg has not yet run, we still find
606 : situations in which we can usefully look through a copy insn. */
607 136630 : rtx x = single_set (insn);
608 136630 : if (x == NULL_RTX)
609 : return NULL_RTX;
610 136269 : reg = SET_SRC (x);
611 136269 : if (!REG_P (reg))
612 : return NULL_RTX;
613 : }
614 :
615 1264094 : if (GET_MODE (reg) != orig_mode)
616 : return NULL_RTX;
617 :
618 : return reg;
619 : }
620 :
621 : /* Return true if it is okay to merge the comparison CMP_INSN with
622 : the instruction ARITH_INSN. Both instructions are assumed to be in the
623 : same basic block with ARITH_INSN appearing before CMP_INSN. This checks
624 : that there are no uses or defs of the condition flags or control flow
625 : changes between the two instructions. */
626 :
627 : static bool
628 854414 : can_merge_compare_into_arith (rtx_insn *cmp_insn, rtx_insn *arith_insn)
629 : {
630 2592478 : for (rtx_insn *insn = PREV_INSN (cmp_insn);
631 2592478 : insn && insn != arith_insn;
632 1738064 : insn = PREV_INSN (insn))
633 : {
634 1858658 : if (!NONDEBUG_INSN_P (insn))
635 1549463 : continue;
636 : /* Bail if there are jumps or calls in between. */
637 309195 : if (!NONJUMP_INSN_P (insn))
638 : return false;
639 :
640 : /* Bail on old-style asm statements because they lack
641 : data flow information. */
642 288494 : if (GET_CODE (PATTERN (insn)) == ASM_INPUT)
643 : return false;
644 :
645 288493 : df_ref ref;
646 : /* Find a USE of the flags register. */
647 697689 : FOR_EACH_INSN_USE (ref, insn)
648 415711 : if (DF_REF_REGNO (ref) == targetm.flags_regnum)
649 : return false;
650 :
651 : /* Find a DEF of the flags register. */
652 464941 : FOR_EACH_INSN_DEF (ref, insn)
653 276340 : if (DF_REF_REGNO (ref) == targetm.flags_regnum)
654 : return false;
655 : }
656 : return true;
657 : }
658 :
659 : /* Given two SET expressions, SET_A and SET_B determine whether they form
660 : a recognizable pattern when emitted in parallel. Return that parallel
661 : if so. Otherwise return NULL. */
662 :
663 : static rtx
664 2 : try_validate_parallel (rtx set_a, rtx set_b)
665 : {
666 2 : rtx par = gen_rtx_PARALLEL (VOIDmode, gen_rtvec (2, set_a, set_b));
667 2 : rtx_insn *insn = make_insn_raw (par);
668 :
669 2 : if (insn_invalid_p (insn, false))
670 : {
671 2 : crtl->emit.x_cur_insn_uid--;
672 2 : return NULL_RTX;
673 : }
674 :
675 0 : SET_PREV_INSN (insn) = NULL_RTX;
676 0 : SET_NEXT_INSN (insn) = NULL_RTX;
677 0 : INSN_LOCATION (insn) = 0;
678 0 : return insn;
679 : }
680 :
681 : /* For a comparison instruction described by CMP check if it compares a
682 : register with zero i.e. it is of the form CC := CMP R1, 0.
683 : If it is, find the instruction defining R1 (say I1) and try to create a
684 : PARALLEL consisting of I1 and the comparison, representing a flag-setting
685 : arithmetic instruction. Example:
686 : I1: R1 := R2 + R3
687 : <instructions that don't read the condition register>
688 : I2: CC := CMP R1 0
689 : I2 can be merged with I1 into:
690 : I1: { CC := CMP (R2 + R3) 0 ; R1 := R2 + R3 }
691 : This catches cases where R1 is used between I1 and I2 and therefore
692 : combine and other RTL optimisations will not try to propagate it into
693 : I2. Return true if we succeeded in merging CMP. */
694 :
695 : static bool
696 3390920 : try_merge_compare (struct comparison *cmp)
697 : {
698 3390920 : rtx_insn *cmp_insn = cmp->insn;
699 :
700 3390920 : if (cmp->in_b != const0_rtx || cmp->in_a_setter == NULL)
701 : return false;
702 854485 : rtx in_a = cmp->in_a;
703 854485 : df_ref use;
704 :
705 854485 : FOR_EACH_INSN_USE (use, cmp_insn)
706 854485 : if (DF_REF_REGNO (use) == REGNO (in_a))
707 : break;
708 854485 : if (!use)
709 : return false;
710 :
711 854485 : rtx_insn *def_insn = cmp->in_a_setter;
712 854485 : rtx set = single_set (def_insn);
713 854485 : if (!set)
714 : return false;
715 :
716 854414 : if (!can_merge_compare_into_arith (cmp_insn, def_insn))
717 : return false;
718 :
719 733820 : rtx src = SET_SRC (set);
720 :
721 : /* If the source uses addressing modes with side effects, we can't
722 : do the merge because we'd end up with a PARALLEL that has two
723 : instances of that side effect in it. */
724 733820 : if (side_effects_p (src))
725 : return false;
726 :
727 378951 : rtx flags = maybe_select_cc_mode (cmp, src, CONST0_RTX (GET_MODE (src)));
728 378951 : if (!flags)
729 : {
730 : /* We may already have a change group going through maybe_select_cc_mode.
731 : Discard it properly. */
732 378949 : cancel_changes (0);
733 378949 : return false;
734 : }
735 :
736 2 : rtx flag_set
737 2 : = gen_rtx_SET (flags, gen_rtx_COMPARE (GET_MODE (flags),
738 : copy_rtx (src),
739 : CONST0_RTX (GET_MODE (src))));
740 2 : rtx arith_set = copy_rtx (PATTERN (def_insn));
741 2 : rtx par = try_validate_parallel (flag_set, arith_set);
742 2 : if (!par)
743 : {
744 : /* We may already have a change group going through maybe_select_cc_mode.
745 : Discard it properly. */
746 2 : cancel_changes (0);
747 2 : return false;
748 : }
749 0 : if (!apply_change_group ())
750 : return false;
751 0 : emit_insn_after (par, def_insn);
752 0 : delete_insn (def_insn);
753 0 : delete_insn (cmp->insn);
754 0 : return true;
755 : }
756 :
757 : /* Attempt to replace a comparison with a prior arithmetic insn that can
758 : compute the same flags value as the comparison itself. Return true if
759 : successful, having made all rtl modifications necessary. */
760 :
761 : static bool
762 3390920 : try_eliminate_compare (struct comparison *cmp)
763 : {
764 3390920 : rtx flags, in_a, in_b, cmp_a, cmp_b;
765 :
766 3390920 : if (try_merge_compare (cmp))
767 : return true;
768 :
769 : /* We must have found an interesting "clobber" preceding the compare. */
770 3390920 : if (cmp->prev_clobber == NULL)
771 : return false;
772 :
773 : /* Verify that IN_A is not clobbered in between CMP and PREV_CLOBBER.
774 : Given that this target requires this pass, we can assume that most
775 : insns do clobber the flags, and so the distance between the compare
776 : and the clobber is likely to be small. */
777 : /* ??? This is one point at which one could argue that DF_REF_CHAIN would
778 : be useful, but it is thought to be too heavy-weight a solution here. */
779 972693 : in_a = equivalent_reg_at_start (cmp->in_a, cmp->insn, cmp->prev_clobber);
780 972693 : if (!in_a)
781 : return false;
782 :
783 : /* Likewise for IN_B if need be. */
784 893376 : if (CONSTANT_P (cmp->in_b))
785 : in_b = cmp->in_b;
786 417683 : else if (REG_P (cmp->in_b))
787 : {
788 417683 : in_b = equivalent_reg_at_start (cmp->in_b, cmp->insn, cmp->prev_clobber);
789 417683 : if (!in_b)
790 : return false;
791 : }
792 0 : else if (GET_CODE (cmp->in_b) == UNSPEC)
793 : {
794 0 : const int len = XVECLEN (cmp->in_b, 0);
795 0 : rtvec v = rtvec_alloc (len);
796 0 : for (int i = 0; i < len; i++)
797 : {
798 0 : rtx r = equivalent_reg_at_start (XVECEXP (cmp->in_b, 0, i),
799 : cmp->insn, cmp->prev_clobber);
800 0 : if (!r)
801 : return false;
802 0 : RTVEC_ELT (v, i) = r;
803 : }
804 0 : in_b = gen_rtx_UNSPEC (GET_MODE (cmp->in_b), v, XINT (cmp->in_b, 1));
805 : }
806 : else
807 0 : gcc_unreachable ();
808 :
809 : /* We've reached PREV_CLOBBER without finding a modification of IN_A.
810 : Validate that PREV_CLOBBER itself does in fact refer to IN_A. Do
811 : recall that we've already validated the shape of PREV_CLOBBER. */
812 846226 : rtx_insn *insn = cmp->prev_clobber;
813 :
814 846226 : rtx x = XVECEXP (PATTERN (insn), 0, 0);
815 846226 : if (rtx_equal_p (SET_DEST (x), in_a))
816 377586 : cmp_a = SET_SRC (x);
817 :
818 : /* Also check operations with implicit extensions, e.g.:
819 : [(set (reg:DI)
820 : (zero_extend:DI (plus:SI (reg:SI) (reg:SI))))
821 : (set (reg:CCZ flags)
822 : (compare:CCZ (plus:SI (reg:SI) (reg:SI))
823 : (const_int 0)))] */
824 468640 : else if (REG_P (SET_DEST (x))
825 468640 : && REG_P (in_a)
826 468640 : && REGNO (SET_DEST (x)) == REGNO (in_a)
827 26442 : && (GET_CODE (SET_SRC (x)) == ZERO_EXTEND
828 26442 : || GET_CODE (SET_SRC (x)) == SIGN_EXTEND)
829 472414 : && GET_MODE (XEXP (SET_SRC (x), 0)) == GET_MODE (in_a))
830 : cmp_a = XEXP (SET_SRC (x), 0);
831 :
832 : /* Also check fully redundant comparisons, e.g.:
833 : [(set (reg:SI)
834 : (minus:SI (reg:SI) (reg:SI))))
835 : (set (reg:CC flags)
836 : (compare:CC (reg:SI) (reg:SI)))] */
837 464866 : else if (REG_P (in_b)
838 245037 : && GET_CODE (SET_SRC (x)) == MINUS
839 15031 : && rtx_equal_p (XEXP (SET_SRC (x), 0), in_a)
840 464866 : && rtx_equal_p (XEXP (SET_SRC (x), 1), in_b))
841 : cmp_a = in_a;
842 :
843 : else
844 464866 : return false;
845 :
846 : /* If the source uses addressing modes with side effects, we can't
847 : do the merge because we'd end up with a PARALLEL that has two
848 : instances of that side effect in it. */
849 381360 : if (side_effects_p (cmp_a))
850 : return false;
851 :
852 381106 : if (in_a == in_b)
853 : cmp_b = cmp_a;
854 381101 : else if (rtx_equal_p (SET_DEST (x), in_b))
855 0 : cmp_b = SET_SRC (x);
856 : else
857 : cmp_b = in_b;
858 381106 : if (side_effects_p (cmp_b))
859 : return false;
860 :
861 : /* Determine if we ought to use a different CC_MODE here. */
862 381106 : flags = maybe_select_cc_mode (cmp, cmp_a, cmp_b);
863 381106 : if (flags == NULL)
864 379742 : flags = gen_rtx_REG (cmp->orig_mode, targetm.flags_regnum);
865 :
866 : /* Generate a new comparison for installation in the setter. */
867 381106 : rtx y = cmp->not_in_a
868 381106 : ? gen_rtx_NOT (GET_MODE (cmp_a), copy_rtx (cmp_a))
869 381106 : : copy_rtx (cmp_a);
870 381106 : y = gen_rtx_COMPARE (GET_MODE (flags), y, copy_rtx (cmp_b));
871 381106 : y = gen_rtx_SET (flags, y);
872 :
873 : /* Canonicalize instruction to:
874 : [(set (reg:CCM) (compare:CCM (operation) (immediate)))
875 : (set (reg) (operation)] */
876 :
877 381106 : rtvec v = rtvec_alloc (2);
878 381106 : RTVEC_ELT (v, 0) = y;
879 381106 : RTVEC_ELT (v, 1) = x;
880 :
881 381106 : rtx pat = gen_rtx_PARALLEL (VOIDmode, v);
882 :
883 : /* Succeed if the new instruction is valid. Note that we may have started
884 : a change group within maybe_select_cc_mode, therefore we must continue. */
885 381106 : validate_change (insn, &PATTERN (insn), pat, true);
886 :
887 381106 : if (!apply_change_group ())
888 : return false;
889 :
890 : /* Success. Delete the compare insn... */
891 23386 : delete_insn (cmp->insn);
892 :
893 : /* ... and any notes that are now invalid due to multiple sets. */
894 23386 : x = find_regno_note (insn, REG_UNUSED, targetm.flags_regnum);
895 23386 : if (x)
896 0 : remove_note (insn, x);
897 23386 : x = find_reg_note (insn, REG_EQUAL, NULL);
898 23386 : if (x)
899 3811 : remove_note (insn, x);
900 23386 : x = find_reg_note (insn, REG_EQUIV, NULL);
901 23386 : if (x)
902 0 : remove_note (insn, x);
903 :
904 : return true;
905 : }
906 :
907 : /* Main entry point to the pass. */
908 :
909 : static unsigned int
910 1043686 : execute_compare_elim_after_reload (void)
911 : {
912 1043686 : df_set_flags (DF_LR_RUN_DCE);
913 1043686 : df_analyze ();
914 :
915 1043686 : gcc_checking_assert (!all_compares.exists ());
916 :
917 : /* Locate all comparisons and their uses, and eliminate duplicates. */
918 1043686 : find_comparisons ();
919 1043686 : if (all_compares.exists ())
920 : {
921 : struct comparison *cmp;
922 : size_t i;
923 :
924 : /* Eliminate comparisons that are redundant with flags computation. */
925 3849001 : FOR_EACH_VEC_ELT (all_compares, i, cmp)
926 : {
927 3390920 : try_eliminate_compare (cmp);
928 3390920 : XDELETE (cmp);
929 : }
930 :
931 458081 : all_compares.release ();
932 : }
933 :
934 1043686 : return 0;
935 : }
936 :
937 : namespace {
938 :
939 : const pass_data pass_data_compare_elim_after_reload =
940 : {
941 : RTL_PASS, /* type */
942 : "cmpelim", /* name */
943 : OPTGROUP_NONE, /* optinfo_flags */
944 : TV_NONE, /* tv_id */
945 : 0, /* properties_required */
946 : 0, /* properties_provided */
947 : 0, /* properties_destroyed */
948 : 0, /* todo_flags_start */
949 : ( TODO_df_finish | TODO_df_verify ), /* todo_flags_finish */
950 : };
951 :
952 : class pass_compare_elim_after_reload : public rtl_opt_pass
953 : {
954 : public:
955 285722 : pass_compare_elim_after_reload (gcc::context *ctxt)
956 571444 : : rtl_opt_pass (pass_data_compare_elim_after_reload, ctxt)
957 : {}
958 :
959 : /* opt_pass methods: */
960 1471370 : bool gate (function *) final override
961 : {
962 : /* Setting this target hook value is how a backend indicates the need. */
963 1471370 : if (targetm.flags_regnum == INVALID_REGNUM)
964 : return false;
965 1471370 : return flag_compare_elim_after_reload;
966 : }
967 :
968 1043686 : unsigned int execute (function *) final override
969 : {
970 1043686 : return execute_compare_elim_after_reload ();
971 : }
972 :
973 : }; // class pass_compare_elim_after_reload
974 :
975 : } // anon namespace
976 :
977 : rtl_opt_pass *
978 285722 : make_pass_compare_elim_after_reload (gcc::context *ctxt)
979 : {
980 285722 : return new pass_compare_elim_after_reload (ctxt);
981 : }
|
