comparison gcc/compare-elim.c @ 16:04ced10e8804

gcc 7
author kono
date Fri, 27 Oct 2017 22:46:09 +0900
parents 561a7518be6b
children 84e7813d76e9
comparison
equal deleted inserted replaced
15:561a7518be6b 16:04ced10e8804
1 /* Post-reload compare elimination. 1 /* Post-reload compare elimination.
2 Copyright (C) 2010, 2011 2 Copyright (C) 2010-2017 Free Software Foundation, Inc.
3 Free Software Foundation, Inc.
4 3
5 This file is part of GCC. 4 This file is part of GCC.
6 5
7 GCC is free software; you can redistribute it and/or modify it under 6 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free 7 the terms of the GNU General Public License as published by the Free
34 33
35 (0) CBRANCH/CSTORE etc have been split in pass_split_after_reload. 34 (0) CBRANCH/CSTORE etc have been split in pass_split_after_reload.
36 35
37 (1) All comparison patterns are represented as 36 (1) All comparison patterns are represented as
38 37
39 [(set (reg:CC) (compare:CC (reg) (immediate)))] 38 [(set (reg:CC) (compare:CC (reg) (reg_or_immediate)))]
40 39
41 (2) All insn patterns that modify the flags are represented as 40 (2) All insn patterns that modify the flags are represented as
42 41
43 [(set (reg) (operation) 42 [(set (reg) (operation)
44 (clobber (reg:CC))] 43 (clobber (reg:CC))]
45 44
46 (3) If an insn of form (2) can usefully set the flags, there is 45 (3) If an insn of form (2) can usefully set the flags, there is
47 another pattern of the form 46 another pattern of the form
48 47
49 [(set (reg) (operation) 48 [(set (reg:CCM) (compare:CCM (operation) (immediate)))
50 (set (reg:CCM) (compare:CCM (operation) (immediate)))] 49 (set (reg) (operation)]
51 50
52 The mode CCM will be chosen as if by SELECT_CC_MODE. 51 The mode CCM will be chosen as if by SELECT_CC_MODE.
53 52
54 Note that unlike NOTICE_UPDATE_CC, we do not handle memory operands. 53 Note that unlike NOTICE_UPDATE_CC, we do not handle memory operands.
55 This could be handled as a future enhancement. 54 This could be handled as a future enhancement.
56 */ 55 */
57 56
58 #include "config.h" 57 #include "config.h"
59 #include "system.h" 58 #include "system.h"
60 #include "coretypes.h" 59 #include "coretypes.h"
61 #include "tm.h" 60 #include "backend.h"
61 #include "target.h"
62 #include "rtl.h" 62 #include "rtl.h"
63 #include "df.h"
64 #include "memmodel.h"
63 #include "tm_p.h" 65 #include "tm_p.h"
64 #include "insn-config.h" 66 #include "insn-config.h"
65 #include "recog.h" 67 #include "recog.h"
66 #include "flags.h" 68 #include "emit-rtl.h"
67 #include "basic-block.h" 69 #include "cfgrtl.h"
68 #include "tree-pass.h" 70 #include "tree-pass.h"
69 #include "target.h"
70 #include "df.h"
71 #include "domwalk.h" 71 #include "domwalk.h"
72 72
73 73
74 /* These structures describe a comparison and how it is used. */ 74 /* These structures describe a comparison and how it is used. */
75 75
80 #define MAX_CMP_USE 3 80 #define MAX_CMP_USE 3
81 81
82 struct comparison_use 82 struct comparison_use
83 { 83 {
84 /* The instruction in which the result of the compare is used. */ 84 /* The instruction in which the result of the compare is used. */
85 rtx insn; 85 rtx_insn *insn;
86 /* The location of the flags register within the use. */ 86 /* The location of the flags register within the use. */
87 rtx *loc; 87 rtx *loc;
88 /* The comparison code applied against the flags register. */ 88 /* The comparison code applied against the flags register. */
89 enum rtx_code code; 89 enum rtx_code code;
90 }; 90 };
91 91
92 struct comparison 92 struct comparison
93 { 93 {
94 /* The comparison instruction. */ 94 /* The comparison instruction. */
95 rtx insn; 95 rtx_insn *insn;
96 96
97 /* The insn prior to the comparison insn that clobbers the flags. */ 97 /* The insn prior to the comparison insn that clobbers the flags. */
98 rtx prev_clobber; 98 rtx_insn *prev_clobber;
99 99
100 /* The two values being compared. These will be either REGs or 100 /* The two values being compared. These will be either REGs or
101 constants. */ 101 constants. */
102 rtx in_a, in_b; 102 rtx in_a, in_b;
103 103
104 /* The REG_EH_REGION of the comparison. */
105 rtx eh_note;
106
104 /* Information about how this comparison is used. */ 107 /* Information about how this comparison is used. */
105 struct comparison_use uses[MAX_CMP_USE]; 108 struct comparison_use uses[MAX_CMP_USE];
106 109
107 /* The original CC_MODE for this comparison. */ 110 /* The original CC_MODE for this comparison. */
108 enum machine_mode orig_mode; 111 machine_mode orig_mode;
109 112
110 /* The number of uses identified for this comparison. */ 113 /* The number of uses identified for this comparison. */
111 unsigned short n_uses; 114 unsigned short n_uses;
112 115
113 /* True if not all uses of this comparison have been identified. 116 /* True if not all uses of this comparison have been identified.
117 120
118 /* True if its inputs are still valid at the end of the block. */ 121 /* True if its inputs are still valid at the end of the block. */
119 bool inputs_valid; 122 bool inputs_valid;
120 }; 123 };
121 124
122 typedef struct comparison *comparison_struct_p; 125 static vec<comparison *> all_compares;
123 DEF_VEC_P(comparison_struct_p);
124 DEF_VEC_ALLOC_P(comparison_struct_p, heap);
125
126 static VEC(comparison_struct_p, heap) *all_compares;
127 126
128 /* Look for a "conforming" comparison, as defined above. If valid, return 127 /* Look for a "conforming" comparison, as defined above. If valid, return
129 the rtx for the COMPARE itself. */ 128 the rtx for the COMPARE itself. */
130 129
131 static rtx 130 static rtx
132 conforming_compare (rtx insn) 131 conforming_compare (rtx_insn *insn)
133 { 132 {
134 rtx set, src, dest; 133 rtx set, src, dest;
135 134
136 set = single_set (insn); 135 set = single_set (insn);
137 if (set == NULL) 136 if (set == NULL)
143 142
144 dest = SET_DEST (set); 143 dest = SET_DEST (set);
145 if (!REG_P (dest) || REGNO (dest) != targetm.flags_regnum) 144 if (!REG_P (dest) || REGNO (dest) != targetm.flags_regnum)
146 return NULL; 145 return NULL;
147 146
148 if (REG_P (XEXP (src, 0)) 147 if (!REG_P (XEXP (src, 0)))
149 && REG_P (XEXP (src, 0)) 148 return NULL;
150 && (REG_P (XEXP (src, 1)) || CONSTANT_P (XEXP (src, 1)))) 149
150 if (CONSTANT_P (XEXP (src, 1)) || REG_P (XEXP (src, 1)))
151 return src; 151 return src;
152
153 if (GET_CODE (XEXP (src, 1)) == UNSPEC)
154 {
155 for (int i = 0; i < XVECLEN (XEXP (src, 1), 0); i++)
156 if (!REG_P (XVECEXP (XEXP (src, 1), 0, i)))
157 return NULL;
158 return src;
159 }
152 160
153 return NULL; 161 return NULL;
154 } 162 }
155 163
156 /* Look for a pattern of the "correct" form for an insn with a flags clobber 164 /* Look for a pattern of the "correct" form for an insn with a flags clobber
157 for which we may be able to eliminate a compare later. We're not looking 165 for which we may be able to eliminate a compare later. We're not looking
158 to validate any inputs at this time, merely see that the basic shape is 166 to validate any inputs at this time, merely see that the basic shape is
159 correct. The term "arithmetic" may be somewhat misleading... */ 167 correct. The term "arithmetic" may be somewhat misleading... */
160 168
161 static bool 169 static bool
162 arithmetic_flags_clobber_p (rtx insn) 170 arithmetic_flags_clobber_p (rtx_insn *insn)
163 { 171 {
164 rtx pat, x; 172 rtx pat, x;
165 173
166 if (!NONJUMP_INSN_P (insn)) 174 if (!NONJUMP_INSN_P (insn))
167 return false; 175 return false;
168 pat = PATTERN (insn); 176 pat = PATTERN (insn);
169 if (extract_asm_operands (pat)) 177 if (asm_noperands (pat) >= 0)
170 return false; 178 return false;
171 179
172 if (GET_CODE (pat) == PARALLEL && XVECLEN (pat, 0) == 2) 180 if (GET_CODE (pat) == PARALLEL && XVECLEN (pat, 0) == 2)
173 { 181 {
174 x = XVECEXP (pat, 0, 0); 182 x = XVECEXP (pat, 0, 0);
192 200
193 /* Look for uses of FLAGS in INSN. If we find one we can analyze, record 201 /* Look for uses of FLAGS in INSN. If we find one we can analyze, record
194 it in CMP; otherwise indicate that we've missed a use. */ 202 it in CMP; otherwise indicate that we've missed a use. */
195 203
196 static void 204 static void
197 find_flags_uses_in_insn (struct comparison *cmp, rtx insn) 205 find_flags_uses_in_insn (struct comparison *cmp, rtx_insn *insn)
198 { 206 {
199 df_ref *use_rec, use; 207 df_ref use;
200 208
201 /* If we've already lost track of uses, don't bother collecting more. */ 209 /* If we've already lost track of uses, don't bother collecting more. */
202 if (cmp->missing_uses) 210 if (cmp->missing_uses)
203 return; 211 return;
204 212
205 /* Find a USE of the flags register. */ 213 /* Find a USE of the flags register. */
206 for (use_rec = DF_INSN_USES (insn); (use = *use_rec) != NULL; use_rec++) 214 FOR_EACH_INSN_USE (use, insn)
207 if (DF_REF_REGNO (use) == targetm.flags_regnum) 215 if (DF_REF_REGNO (use) == targetm.flags_regnum)
208 { 216 {
209 rtx x, *loc; 217 rtx x, *loc;
210 218
211 /* If this is an unusual use, quit. */ 219 /* If this is an unusual use, quit. */
244 fail: 252 fail:
245 /* We failed to recognize this use of the flags register. */ 253 /* We failed to recognize this use of the flags register. */
246 cmp->missing_uses = true; 254 cmp->missing_uses = true;
247 } 255 }
248 256
257 class find_comparison_dom_walker : public dom_walker
258 {
259 public:
260 find_comparison_dom_walker (cdi_direction direction)
261 : dom_walker (direction) {}
262
263 virtual edge before_dom_children (basic_block);
264 };
265
266 /* Return true if conforming COMPARE with EH_NOTE is redundant with comparison
267 CMP and can thus be eliminated. */
268
269 static bool
270 can_eliminate_compare (rtx compare, rtx eh_note, struct comparison *cmp)
271 {
272 /* Take care that it's in the same EH region. */
273 if (cfun->can_throw_non_call_exceptions
274 && !rtx_equal_p (eh_note, cmp->eh_note))
275 return false;
276
277 /* Make sure the compare is redundant with the previous. */
278 if (!rtx_equal_p (XEXP (compare, 0), cmp->in_a)
279 || !rtx_equal_p (XEXP (compare, 1), cmp->in_b))
280 return false;
281
282 /* New mode must be compatible with the previous compare mode. */
283 machine_mode new_mode
284 = targetm.cc_modes_compatible (GET_MODE (compare), cmp->orig_mode);
285
286 if (new_mode == VOIDmode)
287 return false;
288
289 if (cmp->orig_mode != new_mode)
290 {
291 /* Generate new comparison for substitution. */
292 rtx flags = gen_rtx_REG (new_mode, targetm.flags_regnum);
293 rtx x = gen_rtx_COMPARE (new_mode, cmp->in_a, cmp->in_b);
294 x = gen_rtx_SET (flags, x);
295
296 if (!validate_change (cmp->insn, &PATTERN (cmp->insn), x, false))
297 return false;
298
299 cmp->orig_mode = new_mode;
300 }
301
302 return true;
303 }
304
249 /* Identify comparison instructions within BB. If the flags from the last 305 /* Identify comparison instructions within BB. If the flags from the last
250 compare in the BB is live at the end of the block, install the compare 306 compare in the BB is live at the end of the block, install the compare
251 in BB->AUX. Called via walk_dominators_tree. */ 307 in BB->AUX. Called via dom_walker.walk (). */
252 308
253 static void 309 edge
254 find_comparisons_in_bb (struct dom_walk_data *data ATTRIBUTE_UNUSED, 310 find_comparison_dom_walker::before_dom_children (basic_block bb)
255 basic_block bb)
256 { 311 {
257 struct comparison *last_cmp; 312 struct comparison *last_cmp;
258 rtx insn, next, last_clobber; 313 rtx_insn *insn, *next, *last_clobber;
259 bool last_cmp_valid; 314 bool last_cmp_valid;
315 bool need_purge = false;
260 bitmap killed; 316 bitmap killed;
261 317
262 killed = BITMAP_ALLOC (NULL); 318 killed = BITMAP_ALLOC (NULL);
263 319
264 /* The last comparison that was made. Will be reset to NULL 320 /* The last comparison that was made. Will be reset to NULL
284 340
285 for (insn = BB_HEAD (bb); insn; insn = next) 341 for (insn = BB_HEAD (bb); insn; insn = next)
286 { 342 {
287 rtx src; 343 rtx src;
288 344
289 next = (insn == BB_END (bb) ? NULL_RTX : NEXT_INSN (insn)); 345 next = (insn == BB_END (bb) ? NULL : NEXT_INSN (insn));
290 if (!NONDEBUG_INSN_P (insn)) 346 if (!NONDEBUG_INSN_P (insn))
291 continue; 347 continue;
292 348
293 /* Compute the set of registers modified by this instruction. */ 349 /* Compute the set of registers modified by this instruction. */
294 bitmap_clear (killed); 350 bitmap_clear (killed);
295 df_simulate_find_defs (insn, killed); 351 df_simulate_find_defs (insn, killed);
296 352
297 src = conforming_compare (insn); 353 src = conforming_compare (insn);
298 if (src) 354 if (src)
299 { 355 {
300 /* Eliminate a compare that's redundant with the previous. */ 356 rtx eh_note = NULL;
301 if (last_cmp_valid 357
302 && rtx_equal_p (last_cmp->in_a, XEXP (src, 0)) 358 if (cfun->can_throw_non_call_exceptions)
303 && rtx_equal_p (last_cmp->in_b, XEXP (src, 1))) 359 eh_note = find_reg_note (insn, REG_EH_REGION, NULL);
360
361 if (last_cmp_valid && can_eliminate_compare (src, eh_note, last_cmp))
304 { 362 {
363 if (eh_note)
364 need_purge = true;
305 delete_insn (insn); 365 delete_insn (insn);
306 continue; 366 continue;
307 } 367 }
308 368
309 last_cmp = XCNEW (struct comparison); 369 last_cmp = XCNEW (struct comparison);
310 last_cmp->insn = insn; 370 last_cmp->insn = insn;
311 last_cmp->prev_clobber = last_clobber; 371 last_cmp->prev_clobber = last_clobber;
312 last_cmp->in_a = XEXP (src, 0); 372 last_cmp->in_a = XEXP (src, 0);
313 last_cmp->in_b = XEXP (src, 1); 373 last_cmp->in_b = XEXP (src, 1);
314 last_cmp->orig_mode = GET_MODE (SET_DEST (single_set (insn))); 374 last_cmp->eh_note = eh_note;
315 VEC_safe_push (comparison_struct_p, heap, all_compares, last_cmp); 375 last_cmp->orig_mode = GET_MODE (src);
376 all_compares.safe_push (last_cmp);
316 377
317 /* It's unusual, but be prepared for comparison patterns that 378 /* It's unusual, but be prepared for comparison patterns that
318 also clobber an input, or perhaps a scratch. */ 379 also clobber an input, or perhaps a scratch. */
319 last_clobber = NULL; 380 last_clobber = NULL;
320 last_cmp_valid = true; 381 last_cmp_valid = true;
321 } 382 }
322 383
323 /* Notice if this instruction kills the flags register. */ 384 else
324 else if (bitmap_bit_p (killed, targetm.flags_regnum))
325 { 385 {
326 /* See if this insn could be the "clobber" that eliminates 386 /* Notice if this instruction uses the flags register. */
327 a future comparison. */ 387 if (last_cmp)
328 last_clobber = (arithmetic_flags_clobber_p (insn) ? insn : NULL); 388 find_flags_uses_in_insn (last_cmp, insn);
329 389
330 /* In either case, the previous compare is no longer valid. */ 390 /* Notice if this instruction kills the flags register. */
331 last_cmp = NULL; 391 if (bitmap_bit_p (killed, targetm.flags_regnum))
332 last_cmp_valid = false; 392 {
333 continue; 393 /* See if this insn could be the "clobber" that eliminates
394 a future comparison. */
395 last_clobber = (arithmetic_flags_clobber_p (insn) ? insn : NULL);
396
397 /* In either case, the previous compare is no longer valid. */
398 last_cmp = NULL;
399 last_cmp_valid = false;
400 }
334 } 401 }
335
336 /* Notice if this instruction uses the flags register. */
337 else if (last_cmp)
338 find_flags_uses_in_insn (last_cmp, insn);
339 402
340 /* Notice if any of the inputs to the comparison have changed. */ 403 /* Notice if any of the inputs to the comparison have changed. */
341 if (last_cmp_valid 404 if (last_cmp_valid
342 && (bitmap_bit_p (killed, REGNO (last_cmp->in_a)) 405 && (bitmap_bit_p (killed, REGNO (last_cmp->in_a))
343 || (REG_P (last_cmp->in_b) 406 || (REG_P (last_cmp->in_b)
354 bb->aux = last_cmp; 417 bb->aux = last_cmp;
355 last_cmp->inputs_valid = last_cmp_valid; 418 last_cmp->inputs_valid = last_cmp_valid;
356 419
357 /* Look to see if the flags register is live outgoing here, and 420 /* Look to see if the flags register is live outgoing here, and
358 incoming to any successor not part of the extended basic block. */ 421 incoming to any successor not part of the extended basic block. */
359 if (bitmap_bit_p (&DF_LIVE_BB_INFO (bb)->out, targetm.flags_regnum)) 422 if (bitmap_bit_p (df_get_live_out (bb), targetm.flags_regnum))
360 { 423 {
361 edge e; 424 edge e;
362 edge_iterator ei; 425 edge_iterator ei;
363 426
364 FOR_EACH_EDGE (e, ei, bb->succs) 427 FOR_EACH_EDGE (e, ei, bb->succs)
365 { 428 {
366 basic_block dest = e->dest; 429 basic_block dest = e->dest;
367 if (bitmap_bit_p (&DF_LIVE_BB_INFO (dest)->in, 430 if (bitmap_bit_p (df_get_live_in (bb), targetm.flags_regnum)
368 targetm.flags_regnum)
369 && !single_pred_p (dest)) 431 && !single_pred_p (dest))
370 { 432 {
371 last_cmp->missing_uses = true; 433 last_cmp->missing_uses = true;
372 break; 434 break;
373 } 435 }
374 } 436 }
375 } 437 }
376 } 438 }
439
440 /* If we deleted a compare with a REG_EH_REGION note, we may need to
441 remove EH edges. */
442 if (need_purge)
443 purge_dead_edges (bb);
444
445 return NULL;
377 } 446 }
378 447
379 /* Find all comparisons in the function. */ 448 /* Find all comparisons in the function. */
380 449
381 static void 450 static void
382 find_comparisons (void) 451 find_comparisons (void)
383 { 452 {
384 struct dom_walk_data data;
385
386 memset (&data, 0, sizeof(data));
387 data.dom_direction = CDI_DOMINATORS;
388 data.before_dom_children = find_comparisons_in_bb;
389
390 calculate_dominance_info (CDI_DOMINATORS); 453 calculate_dominance_info (CDI_DOMINATORS);
391 454
392 init_walk_dominator_tree (&data); 455 find_comparison_dom_walker (CDI_DOMINATORS)
393 walk_dominator_tree (&data, ENTRY_BLOCK_PTR); 456 .walk (cfun->cfg->x_entry_block_ptr);
394 fini_walk_dominator_tree (&data);
395 457
396 clear_aux_for_blocks (); 458 clear_aux_for_blocks ();
397 free_dominance_info (CDI_DOMINATORS); 459 free_dominance_info (CDI_DOMINATORS);
398 } 460 }
399 461
405 467
406 static rtx 468 static rtx
407 maybe_select_cc_mode (struct comparison *cmp, rtx a ATTRIBUTE_UNUSED, 469 maybe_select_cc_mode (struct comparison *cmp, rtx a ATTRIBUTE_UNUSED,
408 rtx b ATTRIBUTE_UNUSED) 470 rtx b ATTRIBUTE_UNUSED)
409 { 471 {
410 enum machine_mode sel_mode; 472 machine_mode sel_mode;
411 const int n = cmp->n_uses; 473 const int n = cmp->n_uses;
412 rtx flags = NULL; 474 rtx flags = NULL;
413 475
414 #ifndef SELECT_CC_MODE 476 #ifndef SELECT_CC_MODE
415 /* Minimize code differences when this target macro is undefined. */ 477 /* Minimize code differences when this target macro is undefined. */
437 int i; 499 int i;
438 500
439 sel_mode = SELECT_CC_MODE (cmp->uses[0].code, a, b); 501 sel_mode = SELECT_CC_MODE (cmp->uses[0].code, a, b);
440 for (i = 1; i < n; ++i) 502 for (i = 1; i < n; ++i)
441 { 503 {
442 enum machine_mode new_mode; 504 machine_mode new_mode = SELECT_CC_MODE (cmp->uses[i].code, a, b);
443 new_mode = SELECT_CC_MODE (cmp->uses[i].code, a, b);
444 if (new_mode != sel_mode) 505 if (new_mode != sel_mode)
445 { 506 {
446 sel_mode = targetm.cc_modes_compatible (sel_mode, new_mode); 507 sel_mode = targetm.cc_modes_compatible (sel_mode, new_mode);
447 if (sel_mode == VOIDmode) 508 if (sel_mode == VOIDmode)
448 return NULL; 509 return NULL;
449 } 510 }
450 } 511 }
451 512
452 if (sel_mode != cmp->orig_mode) 513 if (sel_mode != cmp->orig_mode)
453 { 514 {
454 flags = gen_rtx_REG (sel_mode, targetm.flags_regnum); 515 flags = gen_rtx_REG (sel_mode, targetm.flags_regnum);
455 for (i = 0; i < n; ++i) 516 for (i = 0; i < n; ++i)
456 validate_change (cmp->uses[i].insn, cmp->uses[i].loc, flags, true); 517 validate_change (cmp->uses[i].insn, cmp->uses[i].loc, flags, true);
458 } 519 }
459 520
460 return flags; 521 return flags;
461 } 522 }
462 523
524 /* Return a register RTX holding the same value at START as REG at END, or
525 NULL_RTX if there is none. */
526
527 static rtx
528 equivalent_reg_at_start (rtx reg, rtx_insn *end, rtx_insn *start)
529 {
530 machine_mode orig_mode = GET_MODE (reg);
531 rtx_insn *bb_head = BB_HEAD (BLOCK_FOR_INSN (end));
532
533 for (rtx_insn *insn = PREV_INSN (end);
534 insn != start;
535 insn = PREV_INSN (insn))
536 {
537 const int abnormal_flags
538 = (DF_REF_CONDITIONAL | DF_REF_PARTIAL | DF_REF_MAY_CLOBBER
539 | DF_REF_MUST_CLOBBER | DF_REF_SIGN_EXTRACT
540 | DF_REF_ZERO_EXTRACT | DF_REF_STRICT_LOW_PART
541 | DF_REF_PRE_POST_MODIFY);
542 df_ref def;
543
544 /* Note that the BB_HEAD is always either a note or a label, but in
545 any case it means that REG is defined outside the block. */
546 if (insn == bb_head)
547 return NULL_RTX;
548 if (NOTE_P (insn) || DEBUG_INSN_P (insn))
549 continue;
550
551 /* Find a possible def of REG in INSN. */
552 FOR_EACH_INSN_DEF (def, insn)
553 if (DF_REF_REGNO (def) == REGNO (reg))
554 break;
555
556 /* No definitions of REG; continue searching. */
557 if (def == NULL)
558 continue;
559
560 /* Bail if this is not a totally normal set of REG. */
561 if (DF_REF_IS_ARTIFICIAL (def))
562 return NULL_RTX;
563 if (DF_REF_FLAGS (def) & abnormal_flags)
564 return NULL_RTX;
565
566 /* We've found an insn between the compare and the clobber that sets
567 REG. Given that pass_cprop_hardreg has not yet run, we still find
568 situations in which we can usefully look through a copy insn. */
569 rtx x = single_set (insn);
570 if (x == NULL_RTX)
571 return NULL_RTX;
572 reg = SET_SRC (x);
573 if (!REG_P (reg))
574 return NULL_RTX;
575 }
576
577 if (GET_MODE (reg) != orig_mode)
578 return NULL_RTX;
579
580 return reg;
581 }
582
583 /* Return true if it is okay to merge the comparison CMP_INSN with
584 the instruction ARITH_INSN. Both instructions are assumed to be in the
585 same basic block with ARITH_INSN appearing before CMP_INSN. This checks
586 that there are no uses or defs of the condition flags or control flow
587 changes between the two instructions. */
588
589 static bool
590 can_merge_compare_into_arith (rtx_insn *cmp_insn, rtx_insn *arith_insn)
591 {
592 for (rtx_insn *insn = PREV_INSN (cmp_insn);
593 insn && insn != arith_insn;
594 insn = PREV_INSN (insn))
595 {
596 if (!NONDEBUG_INSN_P (insn))
597 continue;
598 /* Bail if there are jumps or calls in between. */
599 if (!NONJUMP_INSN_P (insn))
600 return false;
601
602 /* Bail on old-style asm statements because they lack
603 data flow information. */
604 if (GET_CODE (PATTERN (insn)) == ASM_INPUT)
605 return false;
606
607 df_ref ref;
608 /* Find a USE of the flags register. */
609 FOR_EACH_INSN_USE (ref, insn)
610 if (DF_REF_REGNO (ref) == targetm.flags_regnum)
611 return false;
612
613 /* Find a DEF of the flags register. */
614 FOR_EACH_INSN_DEF (ref, insn)
615 if (DF_REF_REGNO (ref) == targetm.flags_regnum)
616 return false;
617 }
618 return true;
619 }
620
621 /* Given two SET expressions, SET_A and SET_B determine whether they form
622 a recognizable pattern when emitted in parallel. Return that parallel
623 if so. Otherwise return NULL. */
624
625 static rtx
626 try_validate_parallel (rtx set_a, rtx set_b)
627 {
628 rtx par
629 = gen_rtx_PARALLEL (VOIDmode, gen_rtvec (2, set_a, set_b));
630
631 rtx_insn *insn;
632 insn = gen_rtx_INSN (VOIDmode, 0, 0, 0, par, 0, -1, 0);
633
634 return recog_memoized (insn) > 0 ? par : NULL_RTX;
635 }
636
637 /* For a comparison instruction described by CMP check if it compares a
638 register with zero i.e. it is of the form CC := CMP R1, 0.
639 If it is, find the instruction defining R1 (say I1) and try to create a
640 PARALLEL consisting of I1 and the comparison, representing a flag-setting
641 arithmetic instruction. Example:
642 I1: R1 := R2 + R3
643 <instructions that don't read the condition register>
644 I2: CC := CMP R1 0
645 I2 can be merged with I1 into:
646 I1: { R1 := R2 + R3 ; CC := CMP (R2 + R3) 0 }
647 This catches cases where R1 is used between I1 and I2 and therefore
648 combine and other RTL optimisations will not try to propagate it into
649 I2. Return true if we succeeded in merging CMP. */
650
651 static bool
652 try_merge_compare (struct comparison *cmp)
653 {
654 rtx_insn *cmp_insn = cmp->insn;
655
656 if (!REG_P (cmp->in_a) || cmp->in_b != const0_rtx)
657 return false;
658 rtx in_a = cmp->in_a;
659 df_ref use;
660
661 FOR_EACH_INSN_USE (use, cmp_insn)
662 if (DF_REF_REGNO (use) == REGNO (in_a))
663 break;
664 if (!use)
665 return false;
666
667 /* Validate the data flow information before attempting to
668 find the instruction that defines in_a. */
669
670 struct df_link *ref_chain;
671 ref_chain = DF_REF_CHAIN (use);
672 if (!ref_chain || !ref_chain->ref
673 || !DF_REF_INSN_INFO (ref_chain->ref) || ref_chain->next != NULL)
674 return false;
675
676 rtx_insn *def_insn = DF_REF_INSN (ref_chain->ref);
677 /* We found the insn that defines in_a. Only consider the cases where
678 it is in the same block as the comparison. */
679 if (BLOCK_FOR_INSN (cmp_insn) != BLOCK_FOR_INSN (def_insn))
680 return false;
681
682 rtx set = single_set (def_insn);
683 if (!set)
684 return false;
685
686 if (!can_merge_compare_into_arith (cmp_insn, def_insn))
687 return false;
688
689 rtx src = SET_SRC (set);
690 rtx flags = maybe_select_cc_mode (cmp, src, CONST0_RTX (GET_MODE (src)));
691 if (!flags)
692 {
693 /* We may already have a change group going through maybe_select_cc_mode.
694 Discard it properly. */
695 cancel_changes (0);
696 return false;
697 }
698
699 rtx flag_set
700 = gen_rtx_SET (flags, gen_rtx_COMPARE (GET_MODE (flags),
701 copy_rtx (src),
702 CONST0_RTX (GET_MODE (src))));
703 rtx arith_set = copy_rtx (PATTERN (def_insn));
704 rtx par = try_validate_parallel (flag_set, arith_set);
705 if (!par)
706 {
707 /* We may already have a change group going through maybe_select_cc_mode.
708 Discard it properly. */
709 cancel_changes (0);
710 return false;
711 }
712 if (!apply_change_group ())
713 return false;
714 emit_insn_after (par, def_insn);
715 delete_insn (def_insn);
716 delete_insn (cmp->insn);
717 return true;
718 }
719
463 /* Attempt to replace a comparison with a prior arithmetic insn that can 720 /* Attempt to replace a comparison with a prior arithmetic insn that can
464 compute the same flags value as the comparison itself. Return true if 721 compute the same flags value as the comparison itself. Return true if
465 successful, having made all rtl modifications necessary. */ 722 successful, having made all rtl modifications necessary. */
466 723
467 static bool 724 static bool
468 try_eliminate_compare (struct comparison *cmp) 725 try_eliminate_compare (struct comparison *cmp)
469 { 726 {
470 rtx x, insn, bb_head, flags, in_a, cmp_src; 727 rtx flags, in_a, in_b, cmp_src;
471 728
472 /* We must have found an interesting "clobber" preceeding the compare. */ 729 if (try_merge_compare (cmp))
730 return true;
731
732 /* We must have found an interesting "clobber" preceding the compare. */
473 if (cmp->prev_clobber == NULL) 733 if (cmp->prev_clobber == NULL)
474 return false;
475
476 /* ??? For the moment we don't handle comparisons for which IN_B
477 is a register. We accepted these during initial comparison
478 recognition in order to eliminate duplicate compares.
479 An improvement here would be to handle x = a - b; if (a cmp b). */
480 if (!CONSTANT_P (cmp->in_b))
481 return false; 734 return false;
482 735
483 /* Verify that IN_A is not clobbered in between CMP and PREV_CLOBBER. 736 /* Verify that IN_A is not clobbered in between CMP and PREV_CLOBBER.
484 Given that this target requires this pass, we can assume that most 737 Given that this target requires this pass, we can assume that most
485 insns do clobber the flags, and so the distance between the compare 738 insns do clobber the flags, and so the distance between the compare
486 and the clobber is likely to be small. */ 739 and the clobber is likely to be small. */
487 /* ??? This is one point at which one could argue that DF_REF_CHAIN would 740 /* ??? This is one point at which one could argue that DF_REF_CHAIN would
488 be useful, but it is thought to be too heavy-weight a solution here. */ 741 be useful, but it is thought to be too heavy-weight a solution here. */
489 742 in_a = equivalent_reg_at_start (cmp->in_a, cmp->insn, cmp->prev_clobber);
490 in_a = cmp->in_a; 743 if (!in_a)
491 insn = cmp->insn; 744 return false;
492 bb_head = BB_HEAD (BLOCK_FOR_INSN (insn)); 745
493 for (insn = PREV_INSN (insn); 746 /* Likewise for IN_B if need be. */
494 insn != cmp->prev_clobber; 747 if (CONSTANT_P (cmp->in_b))
495 insn = PREV_INSN (insn)) 748 in_b = cmp->in_b;
496 { 749 else if (REG_P (cmp->in_b))
497 const int abnormal_flags 750 {
498 = (DF_REF_CONDITIONAL | DF_REF_PARTIAL | DF_REF_MAY_CLOBBER 751 in_b = equivalent_reg_at_start (cmp->in_b, cmp->insn, cmp->prev_clobber);
499 | DF_REF_MUST_CLOBBER | DF_REF_SIGN_EXTRACT 752 if (!in_b)
500 | DF_REF_ZERO_EXTRACT | DF_REF_STRICT_LOW_PART
501 | DF_REF_PRE_POST_MODIFY);
502 df_ref *def_rec, def;
503
504 /* Note that the BB_HEAD is always either a note or a label, but in
505 any case it means that IN_A is defined outside the block. */
506 if (insn == bb_head)
507 return false; 753 return false;
508 if (NOTE_P (insn) || DEBUG_INSN_P (insn)) 754 }
509 continue; 755 else if (GET_CODE (cmp->in_b) == UNSPEC)
510 756 {
511 /* Find a possible def of IN_A in INSN. */ 757 const int len = XVECLEN (cmp->in_b, 0);
512 for (def_rec = DF_INSN_DEFS (insn); (def = *def_rec) != NULL; def_rec++) 758 rtvec v = rtvec_alloc (len);
513 if (DF_REF_REGNO (def) == REGNO (in_a)) 759 for (int i = 0; i < len; i++)
514 break; 760 {
515 761 rtx r = equivalent_reg_at_start (XVECEXP (cmp->in_b, 0, i),
516 /* No definitions of IN_A; continue searching. */ 762 cmp->insn, cmp->prev_clobber);
517 if (def == NULL) 763 if (!r)
518 continue; 764 return false;
519 765 RTVEC_ELT (v, i) = r;
520 /* Bail if this is not a totally normal set of IN_A. */ 766 }
521 if (DF_REF_IS_ARTIFICIAL (def)) 767 in_b = gen_rtx_UNSPEC (GET_MODE (cmp->in_b), v, XINT (cmp->in_b, 1));
522 return false; 768 }
523 if (DF_REF_FLAGS (def) & abnormal_flags) 769 else
524 return false; 770 gcc_unreachable ();
525
526 /* We've found an insn between the compare and the clobber that sets
527 IN_A. Given that pass_cprop_hardreg has not yet run, we still find
528 situations in which we can usefully look through a copy insn. */
529 x = single_set (insn);
530 if (x == NULL)
531 return false;
532 in_a = SET_SRC (x);
533 if (!REG_P (in_a))
534 return false;
535 }
536 771
537 /* We've reached PREV_CLOBBER without finding a modification of IN_A. 772 /* We've reached PREV_CLOBBER without finding a modification of IN_A.
538 Validate that PREV_CLOBBER itself does in fact refer to IN_A. Do 773 Validate that PREV_CLOBBER itself does in fact refer to IN_A. Do
539 recall that we've already validated the shape of PREV_CLOBBER. */ 774 recall that we've already validated the shape of PREV_CLOBBER. */
540 x = XVECEXP (PATTERN (insn), 0, 0); 775 rtx_insn *insn = cmp->prev_clobber;
541 if (!rtx_equal_p (SET_DEST (x), in_a)) 776
542 return false; 777 rtx x = XVECEXP (PATTERN (insn), 0, 0);
543 cmp_src = SET_SRC (x); 778 if (rtx_equal_p (SET_DEST (x), in_a))
544 779 cmp_src = SET_SRC (x);
780
781 /* Also check operations with implicit extensions, e.g.:
782 [(set (reg:DI)
783 (zero_extend:DI (plus:SI (reg:SI) (reg:SI))))
784 (set (reg:CCZ flags)
785 (compare:CCZ (plus:SI (reg:SI) (reg:SI))
786 (const_int 0)))] */
787 else if (REG_P (SET_DEST (x))
788 && REG_P (in_a)
789 && REGNO (SET_DEST (x)) == REGNO (in_a)
790 && (GET_CODE (SET_SRC (x)) == ZERO_EXTEND
791 || GET_CODE (SET_SRC (x)) == SIGN_EXTEND)
792 && GET_MODE (XEXP (SET_SRC (x), 0)) == GET_MODE (in_a))
793 cmp_src = XEXP (SET_SRC (x), 0);
794
795 /* Also check fully redundant comparisons, e.g.:
796 [(set (reg:SI)
797 (minus:SI (reg:SI) (reg:SI))))
798 (set (reg:CC flags)
799 (compare:CC (reg:SI) (reg:SI)))] */
800 else if (REG_P (in_b)
801 && GET_CODE (SET_SRC (x)) == MINUS
802 && rtx_equal_p (XEXP (SET_SRC (x), 0), in_a)
803 && rtx_equal_p (XEXP (SET_SRC (x), 1), in_b))
804 cmp_src = in_a;
805
806 else
807 return false;
808
545 /* Determine if we ought to use a different CC_MODE here. */ 809 /* Determine if we ought to use a different CC_MODE here. */
546 flags = maybe_select_cc_mode (cmp, cmp_src, cmp->in_b); 810 flags = maybe_select_cc_mode (cmp, cmp_src, in_b);
547 if (flags == NULL) 811 if (flags == NULL)
548 flags = gen_rtx_REG (cmp->orig_mode, targetm.flags_regnum); 812 flags = gen_rtx_REG (cmp->orig_mode, targetm.flags_regnum);
549 813
550 /* Generate a new comparison for installation in the setter. */ 814 /* Generate a new comparison for installation in the setter. */
551 x = copy_rtx (cmp_src); 815 rtx y = copy_rtx (cmp_src);
552 x = gen_rtx_COMPARE (GET_MODE (flags), x, cmp->in_b); 816 y = gen_rtx_COMPARE (GET_MODE (flags), y, in_b);
553 x = gen_rtx_SET (VOIDmode, flags, x); 817 y = gen_rtx_SET (flags, y);
554 818
819 /* Canonicalize instruction to:
820 [(set (reg:CCM) (compare:CCM (operation) (immediate)))
821 (set (reg) (operation)] */
822
823 rtvec v = rtvec_alloc (2);
824 RTVEC_ELT (v, 0) = y;
825 RTVEC_ELT (v, 1) = x;
826
827 rtx pat = gen_rtx_PARALLEL (VOIDmode, v);
828
555 /* Succeed if the new instruction is valid. Note that we may have started 829 /* Succeed if the new instruction is valid. Note that we may have started
556 a change group within maybe_select_cc_mode, therefore we must continue. */ 830 a change group within maybe_select_cc_mode, therefore we must continue. */
557 validate_change (insn, &XVECEXP (PATTERN (insn), 0, 1), x, true); 831 validate_change (insn, &PATTERN (insn), pat, true);
832
558 if (!apply_change_group ()) 833 if (!apply_change_group ())
559 return false; 834 return false;
560 835
561 /* Success. Delete the compare insn... */ 836 /* Success. Delete the compare insn... */
562 delete_insn (cmp->insn); 837 delete_insn (cmp->insn);
563 838
564 /* ... and any notes that are now invalid due to multiple sets. */ 839 /* ... and any notes that are now invalid due to multiple sets. */
565 x = find_regno_note (insn, REG_UNUSED, targetm.flags_regnum); 840 x = find_regno_note (insn, REG_UNUSED, targetm.flags_regnum);
578 /* Main entry point to the pass. */ 853 /* Main entry point to the pass. */
579 854
580 static unsigned int 855 static unsigned int
581 execute_compare_elim_after_reload (void) 856 execute_compare_elim_after_reload (void)
582 { 857 {
583 df_set_flags (DF_DEFER_INSN_RESCAN); 858 df_chain_add_problem (DF_UD_CHAIN + DF_DU_CHAIN);
584 df_live_add_problem ();
585 df_analyze (); 859 df_analyze ();
586 860
587 gcc_checking_assert (all_compares == NULL); 861 gcc_checking_assert (!all_compares.exists ());
588 862
589 /* Locate all comparisons and their uses, and eliminate duplicates. */ 863 /* Locate all comparisons and their uses, and eliminate duplicates. */
590 find_comparisons (); 864 find_comparisons ();
591 if (all_compares) 865 if (all_compares.exists ())
592 { 866 {
593 struct comparison *cmp; 867 struct comparison *cmp;
594 size_t i; 868 size_t i;
595 869
596 /* Eliminate comparisons that are redundant with flags computation. */ 870 /* Eliminate comparisons that are redundant with flags computation. */
597 FOR_EACH_VEC_ELT (comparison_struct_p, all_compares, i, cmp) 871 FOR_EACH_VEC_ELT (all_compares, i, cmp)
598 { 872 {
599 try_eliminate_compare (cmp); 873 try_eliminate_compare (cmp);
600 XDELETE (cmp); 874 XDELETE (cmp);
601 } 875 }
602 876
603 VEC_free (comparison_struct_p, heap, all_compares); 877 all_compares.release ();
604 all_compares = NULL;
605
606 df_analyze ();
607 } 878 }
608 879
609 return 0; 880 return 0;
610 } 881 }
611 882
612 static bool 883 namespace {
613 gate_compare_elim_after_reload (void) 884
614 { 885 const pass_data pass_data_compare_elim_after_reload =
615 /* Setting this target hook value is how a backend indicates the need. */ 886 {
616 if (targetm.flags_regnum == INVALID_REGNUM) 887 RTL_PASS, /* type */
617 return false; 888 "cmpelim", /* name */
618 return flag_compare_elim_after_reload; 889 OPTGROUP_NONE, /* optinfo_flags */
619 } 890 TV_NONE, /* tv_id */
620 891 0, /* properties_required */
621 struct rtl_opt_pass pass_compare_elim_after_reload = 892 0, /* properties_provided */
622 { 893 0, /* properties_destroyed */
623 { 894 0, /* todo_flags_start */
624 RTL_PASS, 895 ( TODO_df_finish | TODO_df_verify ), /* todo_flags_finish */
625 "cmpelim", /* name */
626 gate_compare_elim_after_reload, /* gate */
627 execute_compare_elim_after_reload, /* execute */
628 NULL, /* sub */
629 NULL, /* next */
630 0, /* static_pass_number */
631 TV_NONE, /* tv_id */
632 0, /* properties_required */
633 0, /* properties_provided */
634 0, /* properties_destroyed */
635 0, /* todo_flags_start */
636 TODO_df_finish
637 | TODO_df_verify
638 | TODO_verify_rtl_sharing
639 | TODO_dump_func
640 | TODO_ggc_collect /* todo_flags_finish */
641 }
642 }; 896 };
897
898 class pass_compare_elim_after_reload : public rtl_opt_pass
899 {
900 public:
901 pass_compare_elim_after_reload (gcc::context *ctxt)
902 : rtl_opt_pass (pass_data_compare_elim_after_reload, ctxt)
903 {}
904
905 /* opt_pass methods: */
906 virtual bool gate (function *)
907 {
908 /* Setting this target hook value is how a backend indicates the need. */
909 if (targetm.flags_regnum == INVALID_REGNUM)
910 return false;
911 return flag_compare_elim_after_reload;
912 }
913
914 virtual unsigned int execute (function *)
915 {
916 return execute_compare_elim_after_reload ();
917 }
918
919 }; // class pass_compare_elim_after_reload
920
921 } // anon namespace
922
923 rtl_opt_pass *
924 make_pass_compare_elim_after_reload (gcc::context *ctxt)
925 {
926 return new pass_compare_elim_after_reload (ctxt);
927 }