Mercurial > hg > CbC > CbC_gcc
comparison gcc/compare-elim.c @ 111:04ced10e8804
gcc 7
author | kono |
---|---|
date | Fri, 27 Oct 2017 22:46:09 +0900 |
parents | 561a7518be6b |
children | 84e7813d76e9 |
comparison
equal
deleted
inserted
replaced
68:561a7518be6b | 111: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 } |