Branch data Line data Source code
1 : : /* Post-reload compare elimination.
2 : : Copyright (C) 2010-2024 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 : 10807428 : is_not (rtx x)
135 : : {
136 : 10807428 : return GET_CODE (x) == NOT;
137 : : }
138 : :
139 : : /* Strip a NOT unary expression around X, if any. */
140 : :
141 : : static rtx
142 : 7760835 : 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 : 53732992 : conforming_compare (rtx_insn *insn)
155 : : {
156 : 53732992 : rtx set, src, dest;
157 : :
158 : 53732992 : set = single_set (insn);
159 : 53732992 : if (set == NULL)
160 : : return NULL;
161 : :
162 : 49855452 : src = SET_SRC (set);
163 : 49855452 : if (GET_CODE (src) != COMPARE)
164 : : return NULL;
165 : :
166 : 4165194 : dest = SET_DEST (set);
167 : 4165194 : if (!REG_P (dest) || REGNO (dest) != targetm.flags_regnum)
168 : : return NULL;
169 : :
170 : 4165194 : if (!REG_P (strip_not (XEXP (src, 0))))
171 : : return NULL;
172 : :
173 : 3142338 : if (CONSTANT_P (XEXP (src, 1)) || REG_P (XEXP (src, 1)))
174 : : return src;
175 : :
176 : 95745 : 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 : 10860467 : arithmetic_flags_clobber_p (rtx_insn *insn)
194 : : {
195 : 10860467 : rtx pat, x;
196 : :
197 : 10860467 : if (!NONJUMP_INSN_P (insn))
198 : : return false;
199 : 6445826 : pat = PATTERN (insn);
200 : 6445826 : if (asm_noperands (pat) >= 0)
201 : : return false;
202 : :
203 : 6352062 : if (GET_CODE (pat) == PARALLEL && XVECLEN (pat, 0) == 2)
204 : : {
205 : 4974170 : x = XVECEXP (pat, 0, 0);
206 : 4974170 : if (GET_CODE (x) != SET)
207 : : return false;
208 : 4974163 : x = SET_DEST (x);
209 : 4974163 : if (!REG_P (x))
210 : : return false;
211 : :
212 : 4831819 : x = XVECEXP (pat, 0, 1);
213 : 4831819 : if (GET_CODE (x) == CLOBBER)
214 : : {
215 : 4655779 : x = XEXP (x, 0);
216 : 4655779 : 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 : 12871252 : find_flags_uses_in_insn (struct comparison *cmp, rtx_insn *insn)
229 : : {
230 : 12871252 : df_ref use;
231 : :
232 : : /* If we've already lost track of uses, don't bother collecting more. */
233 : 12871252 : if (cmp->missing_uses)
234 : : return;
235 : :
236 : : /* Find a USE of the flags register. */
237 : 26996527 : FOR_EACH_INSN_USE (use, insn)
238 : 14149604 : if (DF_REF_REGNO (use) == targetm.flags_regnum)
239 : : {
240 : 3063859 : rtx x, *loc;
241 : :
242 : : /* If this is an unusual use, quit. */
243 : 3063859 : 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 : 3063859 : if (cmp->n_uses == MAX_CMP_USE)
248 : 3 : 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 : 3063856 : loc = DF_REF_LOC (use);
254 : 3063856 : x = PATTERN (insn);
255 : 3063856 : if (GET_CODE (x) == PARALLEL)
256 : 25492 : x = XVECEXP (x, 0, 0);
257 : 3063856 : if (GET_CODE (x) == SET)
258 : 3063856 : x = SET_SRC (x);
259 : 3063856 : if (GET_CODE (x) == IF_THEN_ELSE)
260 : 2952850 : x = XEXP (x, 0);
261 : 3063856 : if (COMPARISON_P (x)
262 : 3046015 : && loc == &XEXP (x, 0)
263 : 3040311 : && XEXP (x, 1) == const0_rtx)
264 : : {
265 : : /* We've found a use of the flags that we understand. */
266 : 3040311 : struct comparison_use *cuse = &cmp->uses[cmp->n_uses++];
267 : 3040311 : cuse->insn = insn;
268 : 3040311 : cuse->loc = loc;
269 : 3040311 : cuse->code = GET_CODE (x);
270 : : }
271 : : else
272 : 23545 : goto fail;
273 : : }
274 : : return;
275 : :
276 : 23548 : fail:
277 : : /* We failed to recognize this use of the flags register. */
278 : 23548 : cmp->missing_uses = true;
279 : : }
280 : :
281 : 1975368 : class find_comparison_dom_walker : public dom_walker
282 : : {
283 : : public:
284 : 987684 : find_comparison_dom_walker (cdi_direction direction)
285 : 1975368 : : 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 : 555721 : can_eliminate_compare (rtx compare, rtx eh_note, struct comparison *cmp)
295 : : {
296 : : /* Take care that it's in the same EH region. */
297 : 555721 : if (cfun->can_throw_non_call_exceptions
298 : 555721 : && !rtx_equal_p (eh_note, cmp->eh_note))
299 : : return false;
300 : :
301 : : /* Make sure the compare is redundant with the previous. */
302 : 555721 : if (!rtx_equal_p (strip_not (XEXP (compare, 0)), cmp->in_a)
303 : 555721 : || !rtx_equal_p (XEXP (compare, 1), cmp->in_b))
304 : 549048 : return false;
305 : :
306 : 6673 : 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 : 6673 : machine_mode new_mode
311 : 6673 : = targetm.cc_modes_compatible (GET_MODE (compare), cmp->orig_mode);
312 : :
313 : 6673 : if (new_mode == VOIDmode)
314 : : return false;
315 : :
316 : 6673 : if (cmp->orig_mode != new_mode)
317 : : {
318 : : /* Generate new comparison for substitution. */
319 : 1085 : rtx flags = gen_rtx_REG (new_mode, targetm.flags_regnum);
320 : 1085 : rtx x = gen_rtx_COMPARE (new_mode, cmp->in_a, cmp->in_b);
321 : 1085 : x = gen_rtx_SET (flags, x);
322 : :
323 : 1085 : if (!validate_change (cmp->insn, &PATTERN (cmp->insn), x, false))
324 : : return false;
325 : :
326 : 1085 : 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 : 10899999 : find_comparison_dom_walker::before_dom_children (basic_block bb)
338 : : {
339 : 10899999 : rtx_insn *insn, *next;
340 : 10899999 : bool need_purge = false;
341 : 10899999 : 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 : 10899999 : 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 : 10899999 : 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 : 10899999 : rtx_insn *last_clobber = NULL;
355 : :
356 : : /* Propagate the last live comparison throughout the extended basic block. */
357 : 10899999 : if (single_pred_p (bb))
358 : : {
359 : 7543666 : last_cmp = (struct comparison *) single_pred (bb)->aux;
360 : 7543666 : if (last_cmp)
361 : 3824221 : last_cmp_valid = last_cmp->inputs_valid;
362 : : }
363 : :
364 : 10899999 : memset (last_setter, 0, sizeof (last_setter));
365 : 123592545 : for (insn = BB_HEAD (bb); insn; insn = next)
366 : : {
367 : 112692546 : rtx src;
368 : :
369 : 112692546 : next = (insn == BB_END (bb) ? NULL : NEXT_INSN (insn));
370 : 112692546 : if (!NONDEBUG_INSN_P (insn))
371 : 58959554 : continue;
372 : :
373 : 53732992 : src = conforming_compare (insn);
374 : 53732992 : if (src)
375 : : {
376 : 3046593 : rtx eh_note = NULL;
377 : :
378 : 3046593 : if (cfun->can_throw_non_call_exceptions)
379 : 590889 : eh_note = find_reg_note (insn, REG_EH_REGION, NULL);
380 : :
381 : 3046593 : if (last_cmp_valid && can_eliminate_compare (src, eh_note, last_cmp))
382 : : {
383 : 6673 : if (eh_note)
384 : 0 : need_purge = true;
385 : 6673 : delete_insn (insn);
386 : 6673 : continue;
387 : : }
388 : :
389 : 3039920 : last_cmp = XCNEW (struct comparison);
390 : 3039920 : last_cmp->insn = insn;
391 : 3039920 : last_cmp->prev_clobber = last_clobber;
392 : 3039920 : last_cmp->in_a = strip_not (XEXP (src, 0));
393 : 3039920 : last_cmp->in_b = XEXP (src, 1);
394 : 3039920 : last_cmp->not_in_a = is_not (XEXP (src, 0));
395 : 3039920 : last_cmp->eh_note = eh_note;
396 : 3039920 : last_cmp->orig_mode = GET_MODE (src);
397 : 3039920 : if (last_cmp->in_b == const0_rtx
398 : 3039920 : && last_setter[REGNO (last_cmp->in_a)])
399 : : {
400 : 933253 : rtx set = single_set (last_setter[REGNO (last_cmp->in_a)]);
401 : 933253 : if (set && rtx_equal_p (SET_DEST (set), last_cmp->in_a))
402 : 860946 : last_cmp->in_a_setter = last_setter[REGNO (last_cmp->in_a)];
403 : : }
404 : 3039920 : 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 : 3039920 : last_clobber = NULL;
409 : 3039920 : last_cmp_valid = true;
410 : : }
411 : :
412 : : else
413 : : {
414 : : /* Notice if this instruction uses the flags register. */
415 : 50686399 : if (last_cmp)
416 : 12871252 : find_flags_uses_in_insn (last_cmp, insn);
417 : :
418 : : /* Notice if this instruction kills the flags register. */
419 : 50686399 : df_ref def;
420 : 134088228 : FOR_EACH_INSN_DEF (def, insn)
421 : 94262296 : 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 : 10860467 : last_clobber = (arithmetic_flags_clobber_p (insn)
426 : 10860467 : ? insn : NULL);
427 : :
428 : : /* In either case, the previous compare is no longer valid. */
429 : 10860467 : last_cmp = NULL;
430 : 10860467 : last_cmp_valid = false;
431 : 10860467 : 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 : 53726319 : df_ref def;
438 : 454135179 : FOR_EACH_INSN_DEF (def, insn)
439 : : {
440 : 400408860 : if (last_cmp_valid
441 : 400408860 : && (DF_REF_REGNO (def) == REGNO (last_cmp->in_a)
442 : 7225554 : || (REG_P (last_cmp->in_b)
443 : 1862910 : && DF_REF_REGNO (def) == REGNO (last_cmp->in_b))))
444 : : last_cmp_valid = false;
445 : 400408860 : 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 : 10899999 : if (last_cmp)
452 : : {
453 : 4121289 : bb->aux = last_cmp;
454 : 4121289 : 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 : 4121289 : if (bitmap_bit_p (df_get_live_out (bb), targetm.flags_regnum))
459 : : {
460 : 17414 : edge e;
461 : 17414 : edge_iterator ei;
462 : :
463 : 51527 : FOR_EACH_EDGE (e, ei, bb->succs)
464 : : {
465 : 34368 : basic_block dest = e->dest;
466 : 34368 : if (bitmap_bit_p (df_get_live_in (bb), targetm.flags_regnum)
467 : 35052 : && !single_pred_p (dest))
468 : : {
469 : 255 : last_cmp->missing_uses = true;
470 : 255 : 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 : 10899999 : if (need_purge)
479 : 0 : purge_dead_edges (bb);
480 : :
481 : 10899999 : return NULL;
482 : : }
483 : :
484 : : /* Find all comparisons in the function. */
485 : :
486 : : static void
487 : 987684 : find_comparisons (void)
488 : : {
489 : 987684 : calculate_dominance_info (CDI_DOMINATORS);
490 : :
491 : 987684 : find_comparison_dom_walker (CDI_DOMINATORS)
492 : 987684 : .walk (cfun->cfg->x_entry_block_ptr);
493 : :
494 : 987684 : clear_aux_for_blocks ();
495 : 987684 : free_dominance_info (CDI_DOMINATORS);
496 : 987684 : }
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 : 698262 : maybe_select_cc_mode (struct comparison *cmp, rtx a ATTRIBUTE_UNUSED,
506 : : rtx b ATTRIBUTE_UNUSED)
507 : : {
508 : 698262 : machine_mode sel_mode;
509 : 698262 : const int n = cmp->n_uses;
510 : 698262 : 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 : 698262 : 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 : 697340 : if (n == 1)
525 : : {
526 : 691151 : sel_mode = SELECT_CC_MODE (cmp->uses[0].code, a, b);
527 : 691151 : if (sel_mode != cmp->orig_mode)
528 : : {
529 : 1560 : flags = gen_rtx_REG (sel_mode, targetm.flags_regnum);
530 : 1560 : validate_change (cmp->uses[0].insn, cmp->uses[0].loc, flags, true);
531 : : }
532 : : }
533 : : else
534 : : {
535 : 6189 : int i;
536 : :
537 : 6189 : sel_mode = SELECT_CC_MODE (cmp->uses[0].code, a, b);
538 : 12392 : for (i = 1; i < n; ++i)
539 : : {
540 : 6203 : machine_mode new_mode = SELECT_CC_MODE (cmp->uses[i].code, a, b);
541 : 6203 : if (new_mode != sel_mode)
542 : : {
543 : 6056 : sel_mode = targetm.cc_modes_compatible (sel_mode, new_mode);
544 : 6056 : if (sel_mode == VOIDmode)
545 : : return NULL;
546 : : }
547 : : }
548 : :
549 : 6189 : 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 : 1196787 : equivalent_reg_at_start (rtx reg, rtx_insn *end, rtx_insn *start)
565 : : {
566 : 1196787 : machine_mode orig_mode = GET_MODE (reg);
567 : 1196787 : rtx_insn *bb_head = BB_HEAD (BLOCK_FOR_INSN (end));
568 : :
569 : 2727793 : for (rtx_insn *insn = PREV_INSN (end);
570 : 2727793 : insn != start;
571 : 1531006 : insn = PREV_INSN (insn))
572 : : {
573 : 1650085 : 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 : 1650085 : 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 : 1650085 : if (insn == bb_head)
583 : : return NULL_RTX;
584 : 1650085 : if (NOTE_P (insn) || DEBUG_INSN_P (insn))
585 : 1258248 : continue;
586 : :
587 : : /* Find a possible def of REG in INSN. */
588 : 571056 : FOR_EACH_INSN_DEF (def, insn)
589 : 312433 : if (DF_REF_REGNO (def) == REGNO (reg))
590 : : break;
591 : :
592 : : /* No definitions of REG; continue searching. */
593 : 391837 : if (def == NULL)
594 : 258623 : continue;
595 : :
596 : : /* Bail if this is not a totally normal set of REG. */
597 : 133214 : if (DF_REF_IS_ARTIFICIAL (def))
598 : : return NULL_RTX;
599 : 133214 : 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 : 133199 : rtx x = single_set (insn);
606 : 133199 : if (x == NULL_RTX)
607 : : return NULL_RTX;
608 : 132819 : reg = SET_SRC (x);
609 : 132819 : if (!REG_P (reg))
610 : : return NULL_RTX;
611 : : }
612 : :
613 : 1077708 : 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 : 860871 : can_merge_compare_into_arith (rtx_insn *cmp_insn, rtx_insn *arith_insn)
627 : : {
628 : 2572317 : for (rtx_insn *insn = PREV_INSN (cmp_insn);
629 : 2572317 : insn && insn != arith_insn;
630 : 1711446 : insn = PREV_INSN (insn))
631 : : {
632 : 1825218 : if (!NONDEBUG_INSN_P (insn))
633 : 1496347 : continue;
634 : : /* Bail if there are jumps or calls in between. */
635 : 328871 : if (!NONJUMP_INSN_P (insn))
636 : : return false;
637 : :
638 : : /* Bail on old-style asm statements because they lack
639 : : data flow information. */
640 : 311498 : if (GET_CODE (PATTERN (insn)) == ASM_INPUT)
641 : : return false;
642 : :
643 : 311497 : df_ref ref;
644 : : /* Find a USE of the flags register. */
645 : 734084 : FOR_EACH_INSN_USE (ref, insn)
646 : 427830 : if (DF_REF_REGNO (ref) == targetm.flags_regnum)
647 : : return false;
648 : :
649 : : /* Find a DEF of the flags register. */
650 : 510279 : FOR_EACH_INSN_DEF (ref, insn)
651 : 295180 : 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 : 2 : try_validate_parallel (rtx set_a, rtx set_b)
663 : : {
664 : 2 : rtx par = gen_rtx_PARALLEL (VOIDmode, gen_rtvec (2, set_a, set_b));
665 : 2 : rtx_insn *insn = make_insn_raw (par);
666 : :
667 : 2 : if (insn_invalid_p (insn, false))
668 : : {
669 : 2 : crtl->emit.x_cur_insn_uid--;
670 : 2 : 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 : 3039920 : try_merge_compare (struct comparison *cmp)
695 : : {
696 : 3039920 : rtx_insn *cmp_insn = cmp->insn;
697 : :
698 : 3039920 : if (cmp->in_b != const0_rtx || cmp->in_a_setter == NULL)
699 : : return false;
700 : 860946 : rtx in_a = cmp->in_a;
701 : 860946 : df_ref use;
702 : :
703 : 860946 : FOR_EACH_INSN_USE (use, cmp_insn)
704 : 860946 : if (DF_REF_REGNO (use) == REGNO (in_a))
705 : : break;
706 : 860946 : if (!use)
707 : : return false;
708 : :
709 : 860946 : rtx_insn *def_insn = cmp->in_a_setter;
710 : 860946 : rtx set = single_set (def_insn);
711 : 860946 : if (!set)
712 : : return false;
713 : :
714 : 860871 : if (!can_merge_compare_into_arith (cmp_insn, def_insn))
715 : : return false;
716 : :
717 : 747099 : 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 : 747099 : if (side_effects_p (src))
723 : : return false;
724 : :
725 : 367114 : rtx flags = maybe_select_cc_mode (cmp, src, CONST0_RTX (GET_MODE (src)));
726 : 367114 : if (!flags)
727 : : {
728 : : /* We may already have a change group going through maybe_select_cc_mode.
729 : : Discard it properly. */
730 : 367112 : cancel_changes (0);
731 : 367112 : return false;
732 : : }
733 : :
734 : 2 : rtx flag_set
735 : 2 : = gen_rtx_SET (flags, gen_rtx_COMPARE (GET_MODE (flags),
736 : : copy_rtx (src),
737 : : CONST0_RTX (GET_MODE (src))));
738 : 2 : rtx arith_set = copy_rtx (PATTERN (def_insn));
739 : 2 : rtx par = try_validate_parallel (flag_set, arith_set);
740 : 2 : if (!par)
741 : : {
742 : : /* We may already have a change group going through maybe_select_cc_mode.
743 : : Discard it properly. */
744 : 2 : cancel_changes (0);
745 : 2 : 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 : 3039920 : try_eliminate_compare (struct comparison *cmp)
761 : : {
762 : 3039920 : rtx flags, in_a, in_b, cmp_a, cmp_b;
763 : :
764 : 3039920 : if (try_merge_compare (cmp))
765 : : return true;
766 : :
767 : : /* We must have found an interesting "clobber" preceding the compare. */
768 : 3039920 : 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 : 850529 : in_a = equivalent_reg_at_start (cmp->in_a, cmp->insn, cmp->prev_clobber);
778 : 850529 : if (!in_a)
779 : : return false;
780 : :
781 : : /* Likewise for IN_B if need be. */
782 : 777185 : if (CONSTANT_P (cmp->in_b))
783 : : in_b = cmp->in_b;
784 : 346258 : else if (REG_P (cmp->in_b))
785 : : {
786 : 346258 : in_b = equivalent_reg_at_start (cmp->in_b, cmp->insn, cmp->prev_clobber);
787 : 346258 : 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 : 731242 : rtx_insn *insn = cmp->prev_clobber;
811 : :
812 : 731242 : rtx x = XVECEXP (PATTERN (insn), 0, 0);
813 : 731242 : if (rtx_equal_p (SET_DEST (x), in_a))
814 : 328356 : 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 : 402886 : else if (REG_P (SET_DEST (x))
823 : 402886 : && REG_P (in_a)
824 : 402886 : && REGNO (SET_DEST (x)) == REGNO (in_a)
825 : 19755 : && (GET_CODE (SET_SRC (x)) == ZERO_EXTEND
826 : 19755 : || GET_CODE (SET_SRC (x)) == SIGN_EXTEND)
827 : 405678 : && 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 : 400094 : else if (REG_P (in_b)
836 : 201812 : && GET_CODE (SET_SRC (x)) == MINUS
837 : 13508 : && rtx_equal_p (XEXP (SET_SRC (x), 0), in_a)
838 : 400094 : && rtx_equal_p (XEXP (SET_SRC (x), 1), in_b))
839 : : cmp_a = in_a;
840 : :
841 : : else
842 : 400094 : 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 : 331148 : if (side_effects_p (cmp_a))
848 : : return false;
849 : :
850 : 331148 : if (in_a == in_b)
851 : : cmp_b = cmp_a;
852 : 331144 : 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 : 331148 : if (side_effects_p (cmp_b))
857 : : return false;
858 : :
859 : : /* Determine if we ought to use a different CC_MODE here. */
860 : 331148 : flags = maybe_select_cc_mode (cmp, cmp_a, cmp_b);
861 : 331148 : if (flags == NULL)
862 : 329590 : flags = gen_rtx_REG (cmp->orig_mode, targetm.flags_regnum);
863 : :
864 : : /* Generate a new comparison for installation in the setter. */
865 : 331148 : rtx y = cmp->not_in_a
866 : 331148 : ? gen_rtx_NOT (GET_MODE (cmp_a), copy_rtx (cmp_a))
867 : 331148 : : copy_rtx (cmp_a);
868 : 331148 : y = gen_rtx_COMPARE (GET_MODE (flags), y, copy_rtx (cmp_b));
869 : 331148 : 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 : 331148 : rtvec v = rtvec_alloc (2);
876 : 331148 : RTVEC_ELT (v, 0) = y;
877 : 331148 : RTVEC_ELT (v, 1) = x;
878 : :
879 : 331148 : 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 : 331148 : validate_change (insn, &PATTERN (insn), pat, true);
884 : :
885 : 331148 : if (!apply_change_group ())
886 : : return false;
887 : :
888 : : /* Success. Delete the compare insn... */
889 : 25320 : delete_insn (cmp->insn);
890 : :
891 : : /* ... and any notes that are now invalid due to multiple sets. */
892 : 25320 : x = find_regno_note (insn, REG_UNUSED, targetm.flags_regnum);
893 : 25320 : if (x)
894 : 0 : remove_note (insn, x);
895 : 25320 : x = find_reg_note (insn, REG_EQUAL, NULL);
896 : 25320 : if (x)
897 : 4442 : remove_note (insn, x);
898 : 25320 : x = find_reg_note (insn, REG_EQUIV, NULL);
899 : 25320 : 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 : 987684 : execute_compare_elim_after_reload (void)
909 : : {
910 : 987684 : df_set_flags (DF_LR_RUN_DCE);
911 : 987684 : df_analyze ();
912 : :
913 : 987684 : gcc_checking_assert (!all_compares.exists ());
914 : :
915 : : /* Locate all comparisons and their uses, and eliminate duplicates. */
916 : 987684 : find_comparisons ();
917 : 987684 : if (all_compares.exists ())
918 : : {
919 : : struct comparison *cmp;
920 : : size_t i;
921 : :
922 : : /* Eliminate comparisons that are redundant with flags computation. */
923 : 3472821 : FOR_EACH_VEC_ELT (all_compares, i, cmp)
924 : : {
925 : 3039920 : try_eliminate_compare (cmp);
926 : 3039920 : XDELETE (cmp);
927 : : }
928 : :
929 : 432901 : all_compares.release ();
930 : : }
931 : :
932 : 987684 : 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 : 281914 : pass_compare_elim_after_reload (gcc::context *ctxt)
954 : 563828 : : rtl_opt_pass (pass_data_compare_elim_after_reload, ctxt)
955 : : {}
956 : :
957 : : /* opt_pass methods: */
958 : 1426773 : bool gate (function *) final override
959 : : {
960 : : /* Setting this target hook value is how a backend indicates the need. */
961 : 1426773 : if (targetm.flags_regnum == INVALID_REGNUM)
962 : : return false;
963 : 1426773 : return flag_compare_elim_after_reload;
964 : : }
965 : :
966 : 987684 : unsigned int execute (function *) final override
967 : : {
968 : 987684 : 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 : 281914 : make_pass_compare_elim_after_reload (gcc::context *ctxt)
977 : : {
978 : 281914 : return new pass_compare_elim_after_reload (ctxt);
979 : : }
|
