Branch data Line data Source code
1 : : /* Post-reload compare elimination.
2 : : Copyright (C) 2010-2025 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 : 11302852 : is_not (rtx x)
135 : : {
136 : 11302852 : return GET_CODE (x) == NOT;
137 : : }
138 : :
139 : : /* Strip a NOT unary expression around X, if any. */
140 : :
141 : : static rtx
142 : 8142691 : 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 : 55331422 : conforming_compare (rtx_insn *insn)
155 : : {
156 : 55331422 : rtx set, src, dest;
157 : :
158 : 55331422 : set = single_set (insn);
159 : 55331422 : if (set == NULL)
160 : : return NULL;
161 : :
162 : 51420386 : src = SET_SRC (set);
163 : 51420386 : if (GET_CODE (src) != COMPARE)
164 : : return NULL;
165 : :
166 : 4405325 : dest = SET_DEST (set);
167 : 4405325 : if (!REG_P (dest) || REGNO (dest) != targetm.flags_regnum)
168 : : return NULL;
169 : :
170 : 4405325 : if (!REG_P (strip_not (XEXP (src, 0))))
171 : : return NULL;
172 : :
173 : 3300632 : if (CONSTANT_P (XEXP (src, 1)) || REG_P (XEXP (src, 1)))
174 : : return src;
175 : :
176 : 140471 : 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 : 11250310 : arithmetic_flags_clobber_p (rtx_insn *insn)
194 : : {
195 : 11250310 : rtx pat, x;
196 : :
197 : 11250310 : if (!NONJUMP_INSN_P (insn))
198 : : return false;
199 : 6760764 : pat = PATTERN (insn);
200 : 6760764 : if (asm_noperands (pat) >= 0)
201 : : return false;
202 : :
203 : 6675337 : if (GET_CODE (pat) == PARALLEL && XVECLEN (pat, 0) == 2)
204 : : {
205 : 5169529 : x = XVECEXP (pat, 0, 0);
206 : 5169529 : if (GET_CODE (x) != SET)
207 : : return false;
208 : 5169522 : x = SET_DEST (x);
209 : 5169522 : if (!REG_P (x))
210 : : return false;
211 : :
212 : 5021666 : x = XVECEXP (pat, 0, 1);
213 : 5021666 : if (GET_CODE (x) == CLOBBER)
214 : : {
215 : 4841331 : x = XEXP (x, 0);
216 : 4841331 : 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 : 13488170 : find_flags_uses_in_insn (struct comparison *cmp, rtx_insn *insn)
229 : : {
230 : 13488170 : df_ref use;
231 : :
232 : : /* If we've already lost track of uses, don't bother collecting more. */
233 : 13488170 : if (cmp->missing_uses)
234 : : return;
235 : :
236 : : /* Find a USE of the flags register. */
237 : 28426890 : FOR_EACH_INSN_USE (use, insn)
238 : 14965817 : if (DF_REF_REGNO (use) == targetm.flags_regnum)
239 : : {
240 : 3198925 : rtx x, *loc;
241 : :
242 : : /* If this is an unusual use, quit. */
243 : 3198925 : 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 : 3198925 : if (cmp->n_uses == MAX_CMP_USE)
248 : 691 : 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 : 3198234 : loc = DF_REF_LOC (use);
254 : 3198234 : x = PATTERN (insn);
255 : 3198234 : if (GET_CODE (x) == PARALLEL)
256 : 26807 : x = XVECEXP (x, 0, 0);
257 : 3198234 : if (GET_CODE (x) == SET)
258 : 3198234 : x = SET_SRC (x);
259 : 3198234 : if (GET_CODE (x) == IF_THEN_ELSE)
260 : 3085084 : x = XEXP (x, 0);
261 : 3198234 : if (COMPARISON_P (x)
262 : 3179554 : && loc == &XEXP (x, 0)
263 : 3173812 : && XEXP (x, 1) == const0_rtx)
264 : : {
265 : : /* We've found a use of the flags that we understand. */
266 : 3173812 : struct comparison_use *cuse = &cmp->uses[cmp->n_uses++];
267 : 3173812 : cuse->insn = insn;
268 : 3173812 : cuse->loc = loc;
269 : 3173812 : cuse->code = GET_CODE (x);
270 : : }
271 : : else
272 : 24422 : goto fail;
273 : : }
274 : : return;
275 : :
276 : 25113 : fail:
277 : : /* We failed to recognize this use of the flags register. */
278 : 25113 : cmp->missing_uses = true;
279 : : }
280 : :
281 : 2017142 : class find_comparison_dom_walker : public dom_walker
282 : : {
283 : : public:
284 : 1008571 : find_comparison_dom_walker (cdi_direction direction)
285 : 2017142 : : dom_walker (direction) {}
286 : :
287 : : edge before_dom_children (basic_block) final override;
288 : : };
289 : :
290 : : /* Return true if conforming COMPARE with EH_NOTE is redundant with comparison
291 : : CMP and can thus be eliminated. */
292 : :
293 : : static bool
294 : 584411 : can_eliminate_compare (rtx compare, rtx eh_note, struct comparison *cmp)
295 : : {
296 : : /* Take care that it's in the same EH region. */
297 : 584411 : if (cfun->can_throw_non_call_exceptions
298 : 584411 : && !rtx_equal_p (eh_note, cmp->eh_note))
299 : : return false;
300 : :
301 : : /* Make sure the compare is redundant with the previous. */
302 : 584411 : if (!rtx_equal_p (strip_not (XEXP (compare, 0)), cmp->in_a)
303 : 584411 : || !rtx_equal_p (XEXP (compare, 1), cmp->in_b))
304 : 577205 : return false;
305 : :
306 : 7206 : if (is_not (XEXP (compare, 0)) != cmp->not_in_a)
307 : : return false;
308 : :
309 : : /* New mode must be compatible with the previous compare mode. */
310 : 7206 : machine_mode new_mode
311 : 7206 : = targetm.cc_modes_compatible (GET_MODE (compare), cmp->orig_mode);
312 : :
313 : 7206 : if (new_mode == VOIDmode)
314 : : return false;
315 : :
316 : 7206 : if (cmp->orig_mode != new_mode)
317 : : {
318 : : /* Generate new comparison for substitution. */
319 : 1112 : rtx flags = gen_rtx_REG (new_mode, targetm.flags_regnum);
320 : 1112 : rtx x = gen_rtx_COMPARE (new_mode, cmp->in_a, cmp->in_b);
321 : 1112 : x = gen_rtx_SET (flags, x);
322 : :
323 : 1112 : if (!validate_change (cmp->insn, &PATTERN (cmp->insn), x, false))
324 : : return false;
325 : :
326 : 1112 : cmp->orig_mode = new_mode;
327 : : }
328 : :
329 : : return true;
330 : : }
331 : :
332 : : /* Identify comparison instructions within BB. If the flags from the last
333 : : compare in the BB is live at the end of the block, install the compare
334 : : in BB->AUX. Called via dom_walker.walk (). */
335 : :
336 : : edge
337 : 11356487 : find_comparison_dom_walker::before_dom_children (basic_block bb)
338 : : {
339 : 11356487 : rtx_insn *insn, *next;
340 : 11356487 : bool need_purge = false;
341 : 11356487 : rtx_insn *last_setter[FIRST_PSEUDO_REGISTER];
342 : :
343 : : /* The last comparison that was made. Will be reset to NULL
344 : : once the flags are clobbered. */
345 : 11356487 : struct comparison *last_cmp = NULL;
346 : :
347 : : /* True iff the last comparison has not been clobbered, nor
348 : : have its inputs. Used to eliminate duplicate compares. */
349 : 11356487 : bool last_cmp_valid = false;
350 : :
351 : : /* The last insn that clobbered the flags, if that insn is of
352 : : a form that may be valid for eliminating a following compare.
353 : : To be reset to NULL once the flags are set otherwise. */
354 : 11356487 : rtx_insn *last_clobber = NULL;
355 : :
356 : : /* Propagate the last live comparison throughout the extended basic block. */
357 : 11356487 : if (single_pred_p (bb))
358 : : {
359 : 7858919 : last_cmp = (struct comparison *) single_pred (bb)->aux;
360 : 7858919 : if (last_cmp)
361 : 3933435 : last_cmp_valid = last_cmp->inputs_valid;
362 : : }
363 : :
364 : 11356487 : memset (last_setter, 0, sizeof (last_setter));
365 : 130332687 : for (insn = BB_HEAD (bb); insn; insn = next)
366 : : {
367 : 118976200 : rtx src;
368 : :
369 : 118976200 : next = (insn == BB_END (bb) ? NULL : NEXT_INSN (insn));
370 : 118976200 : if (!NONDEBUG_INSN_P (insn))
371 : 63644778 : continue;
372 : :
373 : 55331422 : src = conforming_compare (insn);
374 : 55331422 : if (src)
375 : : {
376 : 3160161 : rtx eh_note = NULL;
377 : :
378 : 3160161 : if (cfun->can_throw_non_call_exceptions)
379 : 570351 : eh_note = find_reg_note (insn, REG_EH_REGION, NULL);
380 : :
381 : 3160161 : if (last_cmp_valid && can_eliminate_compare (src, eh_note, last_cmp))
382 : : {
383 : 7206 : if (eh_note)
384 : 0 : need_purge = true;
385 : 7206 : delete_insn (insn);
386 : 7206 : continue;
387 : : }
388 : :
389 : 3152955 : last_cmp = XCNEW (struct comparison);
390 : 3152955 : last_cmp->insn = insn;
391 : 3152955 : last_cmp->prev_clobber = last_clobber;
392 : 3152955 : last_cmp->in_a = strip_not (XEXP (src, 0));
393 : 3152955 : last_cmp->in_b = XEXP (src, 1);
394 : 3152955 : last_cmp->not_in_a = is_not (XEXP (src, 0));
395 : 3152955 : last_cmp->eh_note = eh_note;
396 : 3152955 : last_cmp->orig_mode = GET_MODE (src);
397 : 3152955 : if (last_cmp->in_b == const0_rtx
398 : 3152955 : && last_setter[REGNO (last_cmp->in_a)])
399 : : {
400 : 943969 : rtx set = single_set (last_setter[REGNO (last_cmp->in_a)]);
401 : 943969 : if (set && rtx_equal_p (SET_DEST (set), last_cmp->in_a))
402 : 871294 : last_cmp->in_a_setter = last_setter[REGNO (last_cmp->in_a)];
403 : : }
404 : 3152955 : all_compares.safe_push (last_cmp);
405 : :
406 : : /* It's unusual, but be prepared for comparison patterns that
407 : : also clobber an input, or perhaps a scratch. */
408 : 3152955 : last_clobber = NULL;
409 : 3152955 : last_cmp_valid = true;
410 : : }
411 : :
412 : : else
413 : : {
414 : : /* Notice if this instruction uses the flags register. */
415 : 52171261 : if (last_cmp)
416 : 13488170 : find_flags_uses_in_insn (last_cmp, insn);
417 : :
418 : : /* Notice if this instruction kills the flags register. */
419 : 52171261 : df_ref def;
420 : 137084572 : FOR_EACH_INSN_DEF (def, insn)
421 : 96163621 : if (DF_REF_REGNO (def) == targetm.flags_regnum)
422 : : {
423 : : /* See if this insn could be the "clobber" that eliminates
424 : : a future comparison. */
425 : 11250310 : last_clobber = (arithmetic_flags_clobber_p (insn)
426 : 11250310 : ? insn : NULL);
427 : :
428 : : /* In either case, the previous compare is no longer valid. */
429 : 11250310 : last_cmp = NULL;
430 : 11250310 : last_cmp_valid = false;
431 : 11250310 : break;
432 : : }
433 : : }
434 : :
435 : : /* Notice if any of the inputs to the comparison have changed
436 : : and remember last insn that sets each register. */
437 : 55324216 : df_ref def;
438 : 462939115 : FOR_EACH_INSN_DEF (def, insn)
439 : : {
440 : 407614899 : if (last_cmp_valid
441 : 407614899 : && (DF_REF_REGNO (def) == REGNO (last_cmp->in_a)
442 : 7563698 : || (REG_P (last_cmp->in_b)
443 : 2015082 : && DF_REF_REGNO (def) == REGNO (last_cmp->in_b))))
444 : : last_cmp_valid = false;
445 : 407614899 : last_setter[DF_REF_REGNO (def)] = insn;
446 : : }
447 : : }
448 : :
449 : : /* Remember the live comparison for subsequent members of
450 : : the extended basic block. */
451 : 11356487 : if (last_cmp)
452 : : {
453 : 4239668 : bb->aux = last_cmp;
454 : 4239668 : last_cmp->inputs_valid = last_cmp_valid;
455 : :
456 : : /* Look to see if the flags register is live outgoing here, and
457 : : incoming to any successor not part of the extended basic block. */
458 : 4239668 : if (bitmap_bit_p (df_get_live_out (bb), targetm.flags_regnum))
459 : : {
460 : 19443 : edge e;
461 : 19443 : edge_iterator ei;
462 : :
463 : 57590 : FOR_EACH_EDGE (e, ei, bb->succs)
464 : : {
465 : 38417 : basic_block dest = e->dest;
466 : 38417 : if (bitmap_bit_p (df_get_live_in (bb), targetm.flags_regnum)
467 : 39120 : && !single_pred_p (dest))
468 : : {
469 : 270 : last_cmp->missing_uses = true;
470 : 270 : break;
471 : : }
472 : : }
473 : : }
474 : : }
475 : :
476 : : /* If we deleted a compare with a REG_EH_REGION note, we may need to
477 : : remove EH edges. */
478 : 11356487 : if (need_purge)
479 : 0 : purge_dead_edges (bb);
480 : :
481 : 11356487 : return NULL;
482 : : }
483 : :
484 : : /* Find all comparisons in the function. */
485 : :
486 : : static void
487 : 1008571 : find_comparisons (void)
488 : : {
489 : 1008571 : calculate_dominance_info (CDI_DOMINATORS);
490 : :
491 : 1008571 : find_comparison_dom_walker (CDI_DOMINATORS)
492 : 1008571 : .walk (cfun->cfg->x_entry_block_ptr);
493 : :
494 : 1008571 : clear_aux_for_blocks ();
495 : 1008571 : free_dominance_info (CDI_DOMINATORS);
496 : 1008571 : }
497 : :
498 : : /* Select an alternate CC_MODE for a comparison insn comparing A and B.
499 : : Note that inputs are almost certainly different than the IN_A and IN_B
500 : : stored in CMP -- we're called while attempting to eliminate the compare
501 : : after all. Return the new FLAGS rtx if successful, else return NULL.
502 : : Note that this function may start a change group. */
503 : :
504 : : static rtx
505 : 721281 : maybe_select_cc_mode (struct comparison *cmp, rtx a ATTRIBUTE_UNUSED,
506 : : rtx b ATTRIBUTE_UNUSED)
507 : : {
508 : 721281 : machine_mode sel_mode;
509 : 721281 : const int n = cmp->n_uses;
510 : 721281 : rtx flags = NULL;
511 : :
512 : : #ifndef SELECT_CC_MODE
513 : : /* Minimize code differences when this target macro is undefined. */
514 : : return NULL;
515 : : #define SELECT_CC_MODE(A,B,C) (gcc_unreachable (), VOIDmode)
516 : : #endif
517 : :
518 : : /* If we don't have access to all of the uses, we can't validate. */
519 : 721281 : if (cmp->missing_uses || n == 0)
520 : : return NULL;
521 : :
522 : : /* Find a new mode that works for all of the uses. Special case the
523 : : common case of exactly one use. */
524 : 720439 : if (n == 1)
525 : : {
526 : 714517 : sel_mode = SELECT_CC_MODE (cmp->uses[0].code, a, b);
527 : 714517 : if (sel_mode != cmp->orig_mode)
528 : : {
529 : 1559 : flags = gen_rtx_REG (sel_mode, targetm.flags_regnum);
530 : 1559 : validate_change (cmp->uses[0].insn, cmp->uses[0].loc, flags, true);
531 : : }
532 : : }
533 : : else
534 : : {
535 : 5922 : int i;
536 : :
537 : 5922 : sel_mode = SELECT_CC_MODE (cmp->uses[0].code, a, b);
538 : 11872 : for (i = 1; i < n; ++i)
539 : : {
540 : 5950 : machine_mode new_mode = SELECT_CC_MODE (cmp->uses[i].code, a, b);
541 : 5950 : if (new_mode != sel_mode)
542 : : {
543 : 4677 : sel_mode = targetm.cc_modes_compatible (sel_mode, new_mode);
544 : 4677 : if (sel_mode == VOIDmode)
545 : : return NULL;
546 : : }
547 : : }
548 : :
549 : 5922 : if (sel_mode != cmp->orig_mode)
550 : : {
551 : 0 : flags = gen_rtx_REG (sel_mode, targetm.flags_regnum);
552 : 0 : for (i = 0; i < n; ++i)
553 : 0 : validate_change (cmp->uses[i].insn, cmp->uses[i].loc, flags, true);
554 : : }
555 : : }
556 : :
557 : : return flags;
558 : : }
559 : :
560 : : /* Return a register RTX holding the same value at START as REG at END, or
561 : : NULL_RTX if there is none. */
562 : :
563 : : static rtx
564 : 1260276 : equivalent_reg_at_start (rtx reg, rtx_insn *end, rtx_insn *start)
565 : : {
566 : 1260276 : machine_mode orig_mode = GET_MODE (reg);
567 : 1260276 : rtx_insn *bb_head = BB_HEAD (BLOCK_FOR_INSN (end));
568 : :
569 : 2945437 : for (rtx_insn *insn = PREV_INSN (end);
570 : 2945437 : insn != start;
571 : 1685161 : insn = PREV_INSN (insn))
572 : : {
573 : 1798066 : const int abnormal_flags
574 : : = (DF_REF_CONDITIONAL | DF_REF_PARTIAL | DF_REF_MAY_CLOBBER
575 : : | DF_REF_MUST_CLOBBER | DF_REF_SIGN_EXTRACT
576 : : | DF_REF_ZERO_EXTRACT | DF_REF_STRICT_LOW_PART
577 : : | DF_REF_PRE_POST_MODIFY);
578 : 1798066 : df_ref def;
579 : :
580 : : /* Note that the BB_HEAD is always either a note or a label, but in
581 : : any case it means that REG is defined outside the block. */
582 : 1798066 : if (insn == bb_head)
583 : : return NULL_RTX;
584 : 1798066 : if (NOTE_P (insn) || DEBUG_INSN_P (insn))
585 : 1440073 : continue;
586 : :
587 : : /* Find a possible def of REG in INSN. */
588 : 516444 : FOR_EACH_INSN_DEF (def, insn)
589 : 281246 : if (DF_REF_REGNO (def) == REGNO (reg))
590 : : break;
591 : :
592 : : /* No definitions of REG; continue searching. */
593 : 357993 : if (def == NULL)
594 : 235198 : continue;
595 : :
596 : : /* Bail if this is not a totally normal set of REG. */
597 : 122795 : if (DF_REF_IS_ARTIFICIAL (def))
598 : : return NULL_RTX;
599 : 122795 : if (DF_REF_FLAGS (def) & abnormal_flags)
600 : : return NULL_RTX;
601 : :
602 : : /* We've found an insn between the compare and the clobber that sets
603 : : REG. Given that pass_cprop_hardreg has not yet run, we still find
604 : : situations in which we can usefully look through a copy insn. */
605 : 122780 : rtx x = single_set (insn);
606 : 122780 : if (x == NULL_RTX)
607 : : return NULL_RTX;
608 : 122420 : reg = SET_SRC (x);
609 : 122420 : if (!REG_P (reg))
610 : : return NULL_RTX;
611 : : }
612 : :
613 : 1147371 : if (GET_MODE (reg) != orig_mode)
614 : : return NULL_RTX;
615 : :
616 : : return reg;
617 : : }
618 : :
619 : : /* Return true if it is okay to merge the comparison CMP_INSN with
620 : : the instruction ARITH_INSN. Both instructions are assumed to be in the
621 : : same basic block with ARITH_INSN appearing before CMP_INSN. This checks
622 : : that there are no uses or defs of the condition flags or control flow
623 : : changes between the two instructions. */
624 : :
625 : : static bool
626 : 871224 : can_merge_compare_into_arith (rtx_insn *cmp_insn, rtx_insn *arith_insn)
627 : : {
628 : 2595080 : for (rtx_insn *insn = PREV_INSN (cmp_insn);
629 : 2595080 : insn && insn != arith_insn;
630 : 1723856 : insn = PREV_INSN (insn))
631 : : {
632 : 1840082 : if (!NONDEBUG_INSN_P (insn))
633 : 1534385 : continue;
634 : : /* Bail if there are jumps or calls in between. */
635 : 305697 : if (!NONJUMP_INSN_P (insn))
636 : : return false;
637 : :
638 : : /* Bail on old-style asm statements because they lack
639 : : data flow information. */
640 : 286401 : if (GET_CODE (PATTERN (insn)) == ASM_INPUT)
641 : : return false;
642 : :
643 : 286400 : df_ref ref;
644 : : /* Find a USE of the flags register. */
645 : 682865 : FOR_EACH_INSN_USE (ref, insn)
646 : 402404 : if (DF_REF_REGNO (ref) == targetm.flags_regnum)
647 : : return false;
648 : :
649 : : /* Find a DEF of the flags register. */
650 : 467151 : FOR_EACH_INSN_DEF (ref, insn)
651 : 277680 : if (DF_REF_REGNO (ref) == targetm.flags_regnum)
652 : : return false;
653 : : }
654 : : return true;
655 : : }
656 : :
657 : : /* Given two SET expressions, SET_A and SET_B determine whether they form
658 : : a recognizable pattern when emitted in parallel. Return that parallel
659 : : if so. Otherwise return NULL. */
660 : :
661 : : static rtx
662 : 1 : try_validate_parallel (rtx set_a, rtx set_b)
663 : : {
664 : 1 : rtx par = gen_rtx_PARALLEL (VOIDmode, gen_rtvec (2, set_a, set_b));
665 : 1 : rtx_insn *insn = make_insn_raw (par);
666 : :
667 : 1 : if (insn_invalid_p (insn, false))
668 : : {
669 : 1 : crtl->emit.x_cur_insn_uid--;
670 : 1 : return NULL_RTX;
671 : : }
672 : :
673 : 0 : SET_PREV_INSN (insn) = NULL_RTX;
674 : 0 : SET_NEXT_INSN (insn) = NULL_RTX;
675 : 0 : INSN_LOCATION (insn) = 0;
676 : 0 : return insn;
677 : : }
678 : :
679 : : /* For a comparison instruction described by CMP check if it compares a
680 : : register with zero i.e. it is of the form CC := CMP R1, 0.
681 : : If it is, find the instruction defining R1 (say I1) and try to create a
682 : : PARALLEL consisting of I1 and the comparison, representing a flag-setting
683 : : arithmetic instruction. Example:
684 : : I1: R1 := R2 + R3
685 : : <instructions that don't read the condition register>
686 : : I2: CC := CMP R1 0
687 : : I2 can be merged with I1 into:
688 : : I1: { CC := CMP (R2 + R3) 0 ; R1 := R2 + R3 }
689 : : This catches cases where R1 is used between I1 and I2 and therefore
690 : : combine and other RTL optimisations will not try to propagate it into
691 : : I2. Return true if we succeeded in merging CMP. */
692 : :
693 : : static bool
694 : 3152955 : try_merge_compare (struct comparison *cmp)
695 : : {
696 : 3152955 : rtx_insn *cmp_insn = cmp->insn;
697 : :
698 : 3152955 : if (cmp->in_b != const0_rtx || cmp->in_a_setter == NULL)
699 : : return false;
700 : 871294 : rtx in_a = cmp->in_a;
701 : 871294 : df_ref use;
702 : :
703 : 871294 : FOR_EACH_INSN_USE (use, cmp_insn)
704 : 871294 : if (DF_REF_REGNO (use) == REGNO (in_a))
705 : : break;
706 : 871294 : if (!use)
707 : : return false;
708 : :
709 : 871294 : rtx_insn *def_insn = cmp->in_a_setter;
710 : 871294 : rtx set = single_set (def_insn);
711 : 871294 : if (!set)
712 : : return false;
713 : :
714 : 871224 : if (!can_merge_compare_into_arith (cmp_insn, def_insn))
715 : : return false;
716 : :
717 : 754998 : rtx src = SET_SRC (set);
718 : :
719 : : /* If the source uses addressing modes with side effects, we can't
720 : : do the merge because we'd end up with a PARALLEL that has two
721 : : instances of that side effect in it. */
722 : 754998 : if (side_effects_p (src))
723 : : return false;
724 : :
725 : 368749 : rtx flags = maybe_select_cc_mode (cmp, src, CONST0_RTX (GET_MODE (src)));
726 : 368749 : if (!flags)
727 : : {
728 : : /* We may already have a change group going through maybe_select_cc_mode.
729 : : Discard it properly. */
730 : 368748 : cancel_changes (0);
731 : 368748 : return false;
732 : : }
733 : :
734 : 1 : rtx flag_set
735 : 1 : = gen_rtx_SET (flags, gen_rtx_COMPARE (GET_MODE (flags),
736 : : copy_rtx (src),
737 : : CONST0_RTX (GET_MODE (src))));
738 : 1 : rtx arith_set = copy_rtx (PATTERN (def_insn));
739 : 1 : rtx par = try_validate_parallel (flag_set, arith_set);
740 : 1 : if (!par)
741 : : {
742 : : /* We may already have a change group going through maybe_select_cc_mode.
743 : : Discard it properly. */
744 : 1 : cancel_changes (0);
745 : 1 : return false;
746 : : }
747 : 0 : if (!apply_change_group ())
748 : : return false;
749 : 0 : emit_insn_after (par, def_insn);
750 : 0 : delete_insn (def_insn);
751 : 0 : delete_insn (cmp->insn);
752 : 0 : return true;
753 : : }
754 : :
755 : : /* Attempt to replace a comparison with a prior arithmetic insn that can
756 : : compute the same flags value as the comparison itself. Return true if
757 : : successful, having made all rtl modifications necessary. */
758 : :
759 : : static bool
760 : 3152955 : try_eliminate_compare (struct comparison *cmp)
761 : : {
762 : 3152955 : rtx flags, in_a, in_b, cmp_a, cmp_b;
763 : :
764 : 3152955 : if (try_merge_compare (cmp))
765 : : return true;
766 : :
767 : : /* We must have found an interesting "clobber" preceding the compare. */
768 : 3152955 : if (cmp->prev_clobber == NULL)
769 : : return false;
770 : :
771 : : /* Verify that IN_A is not clobbered in between CMP and PREV_CLOBBER.
772 : : Given that this target requires this pass, we can assume that most
773 : : insns do clobber the flags, and so the distance between the compare
774 : : and the clobber is likely to be small. */
775 : : /* ??? This is one point at which one could argue that DF_REF_CHAIN would
776 : : be useful, but it is thought to be too heavy-weight a solution here. */
777 : 891153 : in_a = equivalent_reg_at_start (cmp->in_a, cmp->insn, cmp->prev_clobber);
778 : 891153 : if (!in_a)
779 : : return false;
780 : :
781 : : /* Likewise for IN_B if need be. */
782 : 815857 : if (CONSTANT_P (cmp->in_b))
783 : : in_b = cmp->in_b;
784 : 369123 : else if (REG_P (cmp->in_b))
785 : : {
786 : 369123 : in_b = equivalent_reg_at_start (cmp->in_b, cmp->insn, cmp->prev_clobber);
787 : 369123 : if (!in_b)
788 : : return false;
789 : : }
790 : 0 : else if (GET_CODE (cmp->in_b) == UNSPEC)
791 : : {
792 : 0 : const int len = XVECLEN (cmp->in_b, 0);
793 : 0 : rtvec v = rtvec_alloc (len);
794 : 0 : for (int i = 0; i < len; i++)
795 : : {
796 : 0 : rtx r = equivalent_reg_at_start (XVECEXP (cmp->in_b, 0, i),
797 : : cmp->insn, cmp->prev_clobber);
798 : 0 : if (!r)
799 : : return false;
800 : 0 : RTVEC_ELT (v, i) = r;
801 : : }
802 : 0 : in_b = gen_rtx_UNSPEC (GET_MODE (cmp->in_b), v, XINT (cmp->in_b, 1));
803 : : }
804 : : else
805 : 0 : gcc_unreachable ();
806 : :
807 : : /* We've reached PREV_CLOBBER without finding a modification of IN_A.
808 : : Validate that PREV_CLOBBER itself does in fact refer to IN_A. Do
809 : : recall that we've already validated the shape of PREV_CLOBBER. */
810 : 778065 : rtx_insn *insn = cmp->prev_clobber;
811 : :
812 : 778065 : rtx x = XVECEXP (PATTERN (insn), 0, 0);
813 : 778065 : if (rtx_equal_p (SET_DEST (x), in_a))
814 : 349086 : cmp_a = SET_SRC (x);
815 : :
816 : : /* Also check operations with implicit extensions, e.g.:
817 : : [(set (reg:DI)
818 : : (zero_extend:DI (plus:SI (reg:SI) (reg:SI))))
819 : : (set (reg:CCZ flags)
820 : : (compare:CCZ (plus:SI (reg:SI) (reg:SI))
821 : : (const_int 0)))] */
822 : 428979 : else if (REG_P (SET_DEST (x))
823 : 428979 : && REG_P (in_a)
824 : 428979 : && REGNO (SET_DEST (x)) == REGNO (in_a)
825 : 21753 : && (GET_CODE (SET_SRC (x)) == ZERO_EXTEND
826 : 21753 : || GET_CODE (SET_SRC (x)) == SIGN_EXTEND)
827 : 432425 : && GET_MODE (XEXP (SET_SRC (x), 0)) == GET_MODE (in_a))
828 : : cmp_a = XEXP (SET_SRC (x), 0);
829 : :
830 : : /* Also check fully redundant comparisons, e.g.:
831 : : [(set (reg:SI)
832 : : (minus:SI (reg:SI) (reg:SI))))
833 : : (set (reg:CC flags)
834 : : (compare:CC (reg:SI) (reg:SI)))] */
835 : 425533 : else if (REG_P (in_b)
836 : 223340 : && GET_CODE (SET_SRC (x)) == MINUS
837 : 13690 : && rtx_equal_p (XEXP (SET_SRC (x), 0), in_a)
838 : 425533 : && rtx_equal_p (XEXP (SET_SRC (x), 1), in_b))
839 : : cmp_a = in_a;
840 : :
841 : : else
842 : 425533 : return false;
843 : :
844 : : /* If the source uses addressing modes with side effects, we can't
845 : : do the merge because we'd end up with a PARALLEL that has two
846 : : instances of that side effect in it. */
847 : 352532 : if (side_effects_p (cmp_a))
848 : : return false;
849 : :
850 : 352532 : if (in_a == in_b)
851 : : cmp_b = cmp_a;
852 : 352527 : else if (rtx_equal_p (SET_DEST (x), in_b))
853 : 0 : cmp_b = SET_SRC (x);
854 : : else
855 : : cmp_b = in_b;
856 : 352532 : if (side_effects_p (cmp_b))
857 : : return false;
858 : :
859 : : /* Determine if we ought to use a different CC_MODE here. */
860 : 352532 : flags = maybe_select_cc_mode (cmp, cmp_a, cmp_b);
861 : 352532 : if (flags == NULL)
862 : 350974 : flags = gen_rtx_REG (cmp->orig_mode, targetm.flags_regnum);
863 : :
864 : : /* Generate a new comparison for installation in the setter. */
865 : 352532 : rtx y = cmp->not_in_a
866 : 352532 : ? gen_rtx_NOT (GET_MODE (cmp_a), copy_rtx (cmp_a))
867 : 352532 : : copy_rtx (cmp_a);
868 : 352532 : y = gen_rtx_COMPARE (GET_MODE (flags), y, copy_rtx (cmp_b));
869 : 352532 : y = gen_rtx_SET (flags, y);
870 : :
871 : : /* Canonicalize instruction to:
872 : : [(set (reg:CCM) (compare:CCM (operation) (immediate)))
873 : : (set (reg) (operation)] */
874 : :
875 : 352532 : rtvec v = rtvec_alloc (2);
876 : 352532 : RTVEC_ELT (v, 0) = y;
877 : 352532 : RTVEC_ELT (v, 1) = x;
878 : :
879 : 352532 : rtx pat = gen_rtx_PARALLEL (VOIDmode, v);
880 : :
881 : : /* Succeed if the new instruction is valid. Note that we may have started
882 : : a change group within maybe_select_cc_mode, therefore we must continue. */
883 : 352532 : validate_change (insn, &PATTERN (insn), pat, true);
884 : :
885 : 352532 : if (!apply_change_group ())
886 : : return false;
887 : :
888 : : /* Success. Delete the compare insn... */
889 : 29970 : delete_insn (cmp->insn);
890 : :
891 : : /* ... and any notes that are now invalid due to multiple sets. */
892 : 29970 : x = find_regno_note (insn, REG_UNUSED, targetm.flags_regnum);
893 : 29970 : if (x)
894 : 0 : remove_note (insn, x);
895 : 29970 : x = find_reg_note (insn, REG_EQUAL, NULL);
896 : 29970 : if (x)
897 : 4746 : remove_note (insn, x);
898 : 29970 : x = find_reg_note (insn, REG_EQUIV, NULL);
899 : 29970 : if (x)
900 : 0 : remove_note (insn, x);
901 : :
902 : : return true;
903 : : }
904 : :
905 : : /* Main entry point to the pass. */
906 : :
907 : : static unsigned int
908 : 1008571 : execute_compare_elim_after_reload (void)
909 : : {
910 : 1008571 : df_set_flags (DF_LR_RUN_DCE);
911 : 1008571 : df_analyze ();
912 : :
913 : 1008571 : gcc_checking_assert (!all_compares.exists ());
914 : :
915 : : /* Locate all comparisons and their uses, and eliminate duplicates. */
916 : 1008571 : find_comparisons ();
917 : 1008571 : if (all_compares.exists ())
918 : : {
919 : : struct comparison *cmp;
920 : : size_t i;
921 : :
922 : : /* Eliminate comparisons that are redundant with flags computation. */
923 : 3595042 : FOR_EACH_VEC_ELT (all_compares, i, cmp)
924 : : {
925 : 3152955 : try_eliminate_compare (cmp);
926 : 3152955 : XDELETE (cmp);
927 : : }
928 : :
929 : 442087 : all_compares.release ();
930 : : }
931 : :
932 : 1008571 : return 0;
933 : : }
934 : :
935 : : namespace {
936 : :
937 : : const pass_data pass_data_compare_elim_after_reload =
938 : : {
939 : : RTL_PASS, /* type */
940 : : "cmpelim", /* name */
941 : : OPTGROUP_NONE, /* optinfo_flags */
942 : : TV_NONE, /* tv_id */
943 : : 0, /* properties_required */
944 : : 0, /* properties_provided */
945 : : 0, /* properties_destroyed */
946 : : 0, /* todo_flags_start */
947 : : ( TODO_df_finish | TODO_df_verify ), /* todo_flags_finish */
948 : : };
949 : :
950 : : class pass_compare_elim_after_reload : public rtl_opt_pass
951 : : {
952 : : public:
953 : 283157 : pass_compare_elim_after_reload (gcc::context *ctxt)
954 : 566314 : : rtl_opt_pass (pass_data_compare_elim_after_reload, ctxt)
955 : : {}
956 : :
957 : : /* opt_pass methods: */
958 : 1435849 : bool gate (function *) final override
959 : : {
960 : : /* Setting this target hook value is how a backend indicates the need. */
961 : 1435849 : if (targetm.flags_regnum == INVALID_REGNUM)
962 : : return false;
963 : 1435849 : return flag_compare_elim_after_reload;
964 : : }
965 : :
966 : 1008571 : unsigned int execute (function *) final override
967 : : {
968 : 1008571 : return execute_compare_elim_after_reload ();
969 : : }
970 : :
971 : : }; // class pass_compare_elim_after_reload
972 : :
973 : : } // anon namespace
974 : :
975 : : rtl_opt_pass *
976 : 283157 : make_pass_compare_elim_after_reload (gcc::context *ctxt)
977 : : {
978 : 283157 : return new pass_compare_elim_after_reload (ctxt);
979 : : }
|
