Mercurial > hg > CbC > CbC_gcc
comparison gcc/tree-ssa-dse.c @ 132:d34655255c78
update gcc-8.2
author | mir3636 |
---|---|
date | Thu, 25 Oct 2018 10:21:07 +0900 |
parents | 84e7813d76e9 |
children | 1830386684a0 |
comparison
equal
deleted
inserted
replaced
130:e108057fa461 | 132:d34655255c78 |
---|---|
1 /* Dead store elimination | 1 /* Dead store elimination |
2 Copyright (C) 2004-2017 Free Software Foundation, Inc. | 2 Copyright (C) 2004-2018 Free Software Foundation, Inc. |
3 | 3 |
4 This file is part of GCC. | 4 This file is part of GCC. |
5 | 5 |
6 GCC is free software; you can redistribute it and/or modify | 6 GCC is free software; you can redistribute it and/or modify |
7 it under the terms of the GNU General Public License as published by | 7 it under the terms of the GNU General Public License as published by |
33 #include "tree-dfa.h" | 33 #include "tree-dfa.h" |
34 #include "domwalk.h" | 34 #include "domwalk.h" |
35 #include "tree-cfgcleanup.h" | 35 #include "tree-cfgcleanup.h" |
36 #include "params.h" | 36 #include "params.h" |
37 #include "alias.h" | 37 #include "alias.h" |
38 #include "tree-ssa-loop.h" | |
38 | 39 |
39 /* This file implements dead store elimination. | 40 /* This file implements dead store elimination. |
40 | 41 |
41 A dead store is a store into a memory location which will later be | 42 A dead store is a store into a memory location which will later be |
42 overwritten by another store without any intervening loads. In this | 43 overwritten by another store without any intervening loads. In this |
126 | 127 |
127 static bool | 128 static bool |
128 valid_ao_ref_for_dse (ao_ref *ref) | 129 valid_ao_ref_for_dse (ao_ref *ref) |
129 { | 130 { |
130 return (ao_ref_base (ref) | 131 return (ao_ref_base (ref) |
131 && ref->max_size != -1 | 132 && known_size_p (ref->max_size) |
132 && ref->size != 0 | 133 && maybe_ne (ref->size, 0) |
133 && ref->max_size == ref->size | 134 && known_eq (ref->max_size, ref->size) |
134 && ref->offset >= 0 | 135 && known_ge (ref->offset, 0) |
135 && (ref->offset % BITS_PER_UNIT) == 0 | 136 && multiple_p (ref->offset, BITS_PER_UNIT) |
136 && (ref->size % BITS_PER_UNIT) == 0 | 137 && multiple_p (ref->size, BITS_PER_UNIT)); |
137 && (ref->size != -1)); | 138 } |
138 } | 139 |
139 | 140 /* Try to normalize COPY (an ao_ref) relative to REF. Essentially when we are |
140 /* Normalize COPY (an ao_ref) relative to REF. Essentially when we are | 141 done COPY will only refer bytes found within REF. Return true if COPY |
141 done COPY will only refer bytes found within REF. | 142 is known to intersect at least one byte of REF. */ |
142 | 143 |
143 We have already verified that COPY intersects at least one | 144 static bool |
144 byte with REF. */ | |
145 | |
146 static void | |
147 normalize_ref (ao_ref *copy, ao_ref *ref) | 145 normalize_ref (ao_ref *copy, ao_ref *ref) |
148 { | 146 { |
147 if (!ordered_p (copy->offset, ref->offset)) | |
148 return false; | |
149 | |
149 /* If COPY starts before REF, then reset the beginning of | 150 /* If COPY starts before REF, then reset the beginning of |
150 COPY to match REF and decrease the size of COPY by the | 151 COPY to match REF and decrease the size of COPY by the |
151 number of bytes removed from COPY. */ | 152 number of bytes removed from COPY. */ |
152 if (copy->offset < ref->offset) | 153 if (maybe_lt (copy->offset, ref->offset)) |
153 { | 154 { |
154 copy->size -= (ref->offset - copy->offset); | 155 poly_int64 diff = ref->offset - copy->offset; |
156 if (maybe_le (copy->size, diff)) | |
157 return false; | |
158 copy->size -= diff; | |
155 copy->offset = ref->offset; | 159 copy->offset = ref->offset; |
156 } | 160 } |
157 | 161 |
162 poly_int64 diff = copy->offset - ref->offset; | |
163 if (maybe_le (ref->size, diff)) | |
164 return false; | |
165 | |
158 /* If COPY extends beyond REF, chop off its size appropriately. */ | 166 /* If COPY extends beyond REF, chop off its size appropriately. */ |
159 if (copy->offset + copy->size > ref->offset + ref->size) | 167 poly_int64 limit = ref->size - diff; |
160 copy->size -= (copy->offset + copy->size - (ref->offset + ref->size)); | 168 if (!ordered_p (limit, copy->size)) |
169 return false; | |
170 | |
171 if (maybe_gt (copy->size, limit)) | |
172 copy->size = limit; | |
173 return true; | |
161 } | 174 } |
162 | 175 |
163 /* Clear any bytes written by STMT from the bitmap LIVE_BYTES. The base | 176 /* Clear any bytes written by STMT from the bitmap LIVE_BYTES. The base |
164 address written by STMT must match the one found in REF, which must | 177 address written by STMT must match the one found in REF, which must |
165 have its base address previously initialized. | 178 have its base address previously initialized. |
174 if (!initialize_ao_ref_for_dse (stmt, &write)) | 187 if (!initialize_ao_ref_for_dse (stmt, &write)) |
175 return; | 188 return; |
176 | 189 |
177 /* Verify we have the same base memory address, the write | 190 /* Verify we have the same base memory address, the write |
178 has a known size and overlaps with REF. */ | 191 has a known size and overlaps with REF. */ |
192 HOST_WIDE_INT start, size; | |
179 if (valid_ao_ref_for_dse (&write) | 193 if (valid_ao_ref_for_dse (&write) |
180 && operand_equal_p (write.base, ref->base, OEP_ADDRESS_OF) | 194 && operand_equal_p (write.base, ref->base, OEP_ADDRESS_OF) |
181 && write.size == write.max_size | 195 && known_eq (write.size, write.max_size) |
182 && ((write.offset < ref->offset | 196 && normalize_ref (&write, ref) |
183 && write.offset + write.size > ref->offset) | 197 && (write.offset - ref->offset).is_constant (&start) |
184 || (write.offset >= ref->offset | 198 && write.size.is_constant (&size)) |
185 && write.offset < ref->offset + ref->size))) | 199 bitmap_clear_range (live_bytes, start / BITS_PER_UNIT, |
186 { | 200 size / BITS_PER_UNIT); |
187 normalize_ref (&write, ref); | |
188 bitmap_clear_range (live_bytes, | |
189 (write.offset - ref->offset) / BITS_PER_UNIT, | |
190 write.size / BITS_PER_UNIT); | |
191 } | |
192 } | 201 } |
193 | 202 |
194 /* REF is a memory write. Extract relevant information from it and | 203 /* REF is a memory write. Extract relevant information from it and |
195 initialize the LIVE_BYTES bitmap. If successful, return TRUE. | 204 initialize the LIVE_BYTES bitmap. If successful, return TRUE. |
196 Otherwise return FALSE. */ | 205 Otherwise return FALSE. */ |
197 | 206 |
198 static bool | 207 static bool |
199 setup_live_bytes_from_ref (ao_ref *ref, sbitmap live_bytes) | 208 setup_live_bytes_from_ref (ao_ref *ref, sbitmap live_bytes) |
200 { | 209 { |
210 HOST_WIDE_INT const_size; | |
201 if (valid_ao_ref_for_dse (ref) | 211 if (valid_ao_ref_for_dse (ref) |
202 && (ref->size / BITS_PER_UNIT | 212 && ref->size.is_constant (&const_size) |
213 && (const_size / BITS_PER_UNIT | |
203 <= PARAM_VALUE (PARAM_DSE_MAX_OBJECT_SIZE))) | 214 <= PARAM_VALUE (PARAM_DSE_MAX_OBJECT_SIZE))) |
204 { | 215 { |
205 bitmap_clear (live_bytes); | 216 bitmap_clear (live_bytes); |
206 bitmap_set_range (live_bytes, 0, ref->size / BITS_PER_UNIT); | 217 bitmap_set_range (live_bytes, 0, const_size / BITS_PER_UNIT); |
207 return true; | 218 return true; |
208 } | 219 } |
209 return false; | 220 return false; |
210 } | 221 } |
211 | 222 |
226 extends through ref->size. So we know that in the original bitmap | 237 extends through ref->size. So we know that in the original bitmap |
227 bits 0..ref->size were true. We don't actually need the bitmap, just | 238 bits 0..ref->size were true. We don't actually need the bitmap, just |
228 the REF to compute the trims. */ | 239 the REF to compute the trims. */ |
229 | 240 |
230 /* Now identify how much, if any of the tail we can chop off. */ | 241 /* Now identify how much, if any of the tail we can chop off. */ |
231 int last_orig = (ref->size / BITS_PER_UNIT) - 1; | 242 HOST_WIDE_INT const_size; |
232 int last_live = bitmap_last_set_bit (live); | 243 int last_live = bitmap_last_set_bit (live); |
233 *trim_tail = (last_orig - last_live) & ~0x1; | 244 if (ref->size.is_constant (&const_size)) |
245 { | |
246 int last_orig = (const_size / BITS_PER_UNIT) - 1; | |
247 /* We can leave inconvenient amounts on the tail as | |
248 residual handling in mem* and str* functions is usually | |
249 reasonably efficient. */ | |
250 *trim_tail = last_orig - last_live; | |
251 | |
252 /* But don't trim away out of bounds accesses, as this defeats | |
253 proper warnings. | |
254 | |
255 We could have a type with no TYPE_SIZE_UNIT or we could have a VLA | |
256 where TYPE_SIZE_UNIT is not a constant. */ | |
257 if (*trim_tail | |
258 && TYPE_SIZE_UNIT (TREE_TYPE (ref->base)) | |
259 && TREE_CODE (TYPE_SIZE_UNIT (TREE_TYPE (ref->base))) == INTEGER_CST | |
260 && compare_tree_int (TYPE_SIZE_UNIT (TREE_TYPE (ref->base)), | |
261 last_orig) <= 0) | |
262 *trim_tail = 0; | |
263 } | |
264 else | |
265 *trim_tail = 0; | |
234 | 266 |
235 /* Identify how much, if any of the head we can chop off. */ | 267 /* Identify how much, if any of the head we can chop off. */ |
236 int first_orig = 0; | 268 int first_orig = 0; |
237 int first_live = bitmap_first_set_bit (live); | 269 int first_live = bitmap_first_set_bit (live); |
238 *trim_head = (first_live - first_orig) & ~0x1; | 270 *trim_head = first_live - first_orig; |
271 | |
272 /* If more than a word remains, then make sure to keep the | |
273 starting point at least word aligned. */ | |
274 if (last_live - first_live > UNITS_PER_WORD) | |
275 *trim_head &= ~(UNITS_PER_WORD - 1); | |
239 | 276 |
240 if ((*trim_head || *trim_tail) | 277 if ((*trim_head || *trim_tail) |
241 && dump_file && (dump_flags & TDF_DETAILS)) | 278 && dump_file && (dump_flags & TDF_DETAILS)) |
242 { | 279 { |
243 fprintf (dump_file, " Trimming statement (head = %d, tail = %d): ", | 280 fprintf (dump_file, " Trimming statement (head = %d, tail = %d): ", |
262 | 299 |
263 /* The amount of data trimmed from the head or tail must be at | 300 /* The amount of data trimmed from the head or tail must be at |
264 least half the size of the object to ensure we're trimming | 301 least half the size of the object to ensure we're trimming |
265 the entire real or imaginary half. By writing things this | 302 the entire real or imaginary half. By writing things this |
266 way we avoid more O(n) bitmap operations. */ | 303 way we avoid more O(n) bitmap operations. */ |
267 if (trim_tail * 2 >= ref->size / BITS_PER_UNIT) | 304 if (known_ge (trim_tail * 2 * BITS_PER_UNIT, ref->size)) |
268 { | 305 { |
269 /* TREE_REALPART is live */ | 306 /* TREE_REALPART is live */ |
270 tree x = TREE_REALPART (gimple_assign_rhs1 (stmt)); | 307 tree x = TREE_REALPART (gimple_assign_rhs1 (stmt)); |
271 tree y = gimple_assign_lhs (stmt); | 308 tree y = gimple_assign_lhs (stmt); |
272 y = build1 (REALPART_EXPR, TREE_TYPE (x), y); | 309 y = build1 (REALPART_EXPR, TREE_TYPE (x), y); |
273 gimple_assign_set_lhs (stmt, y); | 310 gimple_assign_set_lhs (stmt, y); |
274 gimple_assign_set_rhs1 (stmt, x); | 311 gimple_assign_set_rhs1 (stmt, x); |
275 } | 312 } |
276 else if (trim_head * 2 >= ref->size / BITS_PER_UNIT) | 313 else if (known_ge (trim_head * 2 * BITS_PER_UNIT, ref->size)) |
277 { | 314 { |
278 /* TREE_IMAGPART is live */ | 315 /* TREE_IMAGPART is live */ |
279 tree x = TREE_IMAGPART (gimple_assign_rhs1 (stmt)); | 316 tree x = TREE_IMAGPART (gimple_assign_rhs1 (stmt)); |
280 tree y = gimple_assign_lhs (stmt); | 317 tree y = gimple_assign_lhs (stmt); |
281 y = build1 (IMAGPART_EXPR, TREE_TYPE (x), y); | 318 y = build1 (IMAGPART_EXPR, TREE_TYPE (x), y); |
321 | 358 |
322 if (! is_gimple_min_invariant (lhs_addr)) | 359 if (! is_gimple_min_invariant (lhs_addr)) |
323 return; | 360 return; |
324 | 361 |
325 /* The number of bytes for the new constructor. */ | 362 /* The number of bytes for the new constructor. */ |
326 int count = (ref->size / BITS_PER_UNIT) - head_trim - tail_trim; | 363 poly_int64 ref_bytes = exact_div (ref->size, BITS_PER_UNIT); |
364 poly_int64 count = ref_bytes - head_trim - tail_trim; | |
327 | 365 |
328 /* And the new type for the CONSTRUCTOR. Essentially it's just | 366 /* And the new type for the CONSTRUCTOR. Essentially it's just |
329 a char array large enough to cover the non-trimmed parts of | 367 a char array large enough to cover the non-trimmed parts of |
330 the original CONSTRUCTOR. Note we want explicit bounds here | 368 the original CONSTRUCTOR. Note we want explicit bounds here |
331 so that we know how many bytes to clear when expanding the | 369 so that we know how many bytes to clear when expanding the |
478 static bool | 516 static bool |
479 live_bytes_read (ao_ref use_ref, ao_ref *ref, sbitmap live) | 517 live_bytes_read (ao_ref use_ref, ao_ref *ref, sbitmap live) |
480 { | 518 { |
481 /* We have already verified that USE_REF and REF hit the same object. | 519 /* We have already verified that USE_REF and REF hit the same object. |
482 Now verify that there's actually an overlap between USE_REF and REF. */ | 520 Now verify that there's actually an overlap between USE_REF and REF. */ |
483 if (ranges_overlap_p (use_ref.offset, use_ref.size, ref->offset, ref->size)) | 521 HOST_WIDE_INT start, size; |
484 { | 522 if (normalize_ref (&use_ref, ref) |
485 normalize_ref (&use_ref, ref); | 523 && (use_ref.offset - ref->offset).is_constant (&start) |
486 | 524 && use_ref.size.is_constant (&size)) |
525 { | |
487 /* If USE_REF covers all of REF, then it will hit one or more | 526 /* If USE_REF covers all of REF, then it will hit one or more |
488 live bytes. This avoids useless iteration over the bitmap | 527 live bytes. This avoids useless iteration over the bitmap |
489 below. */ | 528 below. */ |
490 if (use_ref.offset <= ref->offset | 529 if (start == 0 && known_eq (size, ref->size)) |
491 && use_ref.offset + use_ref.size >= ref->offset + ref->size) | |
492 return true; | 530 return true; |
493 | 531 |
494 /* Now check if any of the remaining bits in use_ref are set in LIVE. */ | 532 /* Now check if any of the remaining bits in use_ref are set in LIVE. */ |
495 unsigned int start = (use_ref.offset - ref->offset) / BITS_PER_UNIT; | 533 return bitmap_bit_in_range_p (live, start / BITS_PER_UNIT, |
496 unsigned int end = start + (use_ref.size / BITS_PER_UNIT) - 1; | 534 (start + size - 1) / BITS_PER_UNIT); |
497 return bitmap_bit_in_range_p (live, start, end); | |
498 } | 535 } |
499 return true; | 536 return true; |
500 } | 537 } |
501 | 538 |
539 /* Callback for dse_classify_store calling for_each_index. Verify that | |
540 indices are invariant in the loop with backedge PHI in basic-block DATA. */ | |
541 | |
542 static bool | |
543 check_name (tree, tree *idx, void *data) | |
544 { | |
545 basic_block phi_bb = (basic_block) data; | |
546 if (TREE_CODE (*idx) == SSA_NAME | |
547 && !SSA_NAME_IS_DEFAULT_DEF (*idx) | |
548 && dominated_by_p (CDI_DOMINATORS, gimple_bb (SSA_NAME_DEF_STMT (*idx)), | |
549 phi_bb)) | |
550 return false; | |
551 return true; | |
552 } | |
553 | |
502 /* A helper of dse_optimize_stmt. | 554 /* A helper of dse_optimize_stmt. |
503 Given a GIMPLE_ASSIGN in STMT that writes to REF, find a candidate | 555 Given a GIMPLE_ASSIGN in STMT that writes to REF, classify it |
504 statement *USE_STMT that may prove STMT to be dead. | 556 according to downstream uses and defs. Sets *BY_CLOBBER_P to true |
505 Return TRUE if the above conditions are met, otherwise FALSE. */ | 557 if only clobber statements influenced the classification result. |
558 Returns the classification. */ | |
506 | 559 |
507 static dse_store_status | 560 static dse_store_status |
508 dse_classify_store (ao_ref *ref, gimple *stmt, gimple **use_stmt, | 561 dse_classify_store (ao_ref *ref, gimple *stmt, |
509 bool byte_tracking_enabled, sbitmap live_bytes) | 562 bool byte_tracking_enabled, sbitmap live_bytes, |
563 bool *by_clobber_p = NULL) | |
510 { | 564 { |
511 gimple *temp; | 565 gimple *temp; |
512 unsigned cnt = 0; | 566 int cnt = 0; |
513 | 567 auto_bitmap visited; |
514 *use_stmt = NULL; | 568 |
569 if (by_clobber_p) | |
570 *by_clobber_p = true; | |
515 | 571 |
516 /* Find the first dominated statement that clobbers (part of) the | 572 /* Find the first dominated statement that clobbers (part of) the |
517 memory stmt stores to with no intermediate statement that may use | 573 memory stmt stores to with no intermediate statement that may use |
518 part of the memory stmt stores. That is, find a store that may | 574 part of the memory stmt stores. That is, find a store that may |
519 prove stmt to be a dead store. */ | 575 prove stmt to be a dead store. */ |
520 temp = stmt; | 576 temp = stmt; |
521 do | 577 do |
522 { | 578 { |
523 gimple *use_stmt, *defvar_def; | 579 gimple *use_stmt; |
524 imm_use_iterator ui; | 580 imm_use_iterator ui; |
525 bool fail = false; | 581 bool fail = false; |
526 tree defvar; | 582 tree defvar; |
527 | 583 |
528 /* Limit stmt walking to be linear in the number of possibly | |
529 dead stores. */ | |
530 if (++cnt > 256) | |
531 return DSE_STORE_LIVE; | |
532 | |
533 if (gimple_code (temp) == GIMPLE_PHI) | 584 if (gimple_code (temp) == GIMPLE_PHI) |
534 defvar = PHI_RESULT (temp); | 585 { |
586 /* If we visit this PHI by following a backedge then we have to | |
587 make sure ref->ref only refers to SSA names that are invariant | |
588 with respect to the loop represented by this PHI node. */ | |
589 if (dominated_by_p (CDI_DOMINATORS, gimple_bb (stmt), | |
590 gimple_bb (temp)) | |
591 && !for_each_index (ref->ref ? &ref->ref : &ref->base, | |
592 check_name, gimple_bb (temp))) | |
593 return DSE_STORE_LIVE; | |
594 defvar = PHI_RESULT (temp); | |
595 bitmap_set_bit (visited, SSA_NAME_VERSION (defvar)); | |
596 } | |
535 else | 597 else |
536 defvar = gimple_vdef (temp); | 598 defvar = gimple_vdef (temp); |
537 defvar_def = temp; | 599 auto_vec<gimple *, 10> defs; |
538 temp = NULL; | 600 gimple *phi_def = NULL; |
539 FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar) | 601 FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar) |
540 { | 602 { |
541 cnt++; | 603 /* Limit stmt walking. */ |
542 | 604 if (++cnt > PARAM_VALUE (PARAM_DSE_MAX_ALIAS_QUERIES_PER_STORE)) |
543 /* If we ever reach our DSE candidate stmt again fail. We | |
544 cannot handle dead stores in loops. */ | |
545 if (use_stmt == stmt) | |
546 { | 605 { |
547 fail = true; | 606 fail = true; |
548 BREAK_FROM_IMM_USE_STMT (ui); | 607 BREAK_FROM_IMM_USE_STMT (ui); |
549 } | 608 } |
609 | |
610 /* We have visited ourselves already so ignore STMT for the | |
611 purpose of chaining. */ | |
612 if (use_stmt == stmt) | |
613 ; | |
550 /* In simple cases we can look through PHI nodes, but we | 614 /* In simple cases we can look through PHI nodes, but we |
551 have to be careful with loops and with memory references | 615 have to be careful with loops and with memory references |
552 containing operands that are also operands of PHI nodes. | 616 containing operands that are also operands of PHI nodes. |
553 See gcc.c-torture/execute/20051110-*.c. */ | 617 See gcc.c-torture/execute/20051110-*.c. */ |
554 else if (gimple_code (use_stmt) == GIMPLE_PHI) | 618 else if (gimple_code (use_stmt) == GIMPLE_PHI) |
555 { | 619 { |
556 if (temp | 620 /* If we already visited this PHI ignore it for further |
557 /* Make sure we are not in a loop latch block. */ | 621 processing. */ |
558 || gimple_bb (stmt) == gimple_bb (use_stmt) | 622 if (!bitmap_bit_p (visited, |
559 || dominated_by_p (CDI_DOMINATORS, | 623 SSA_NAME_VERSION (PHI_RESULT (use_stmt)))) |
560 gimple_bb (stmt), gimple_bb (use_stmt)) | |
561 /* We can look through PHIs to regions post-dominating | |
562 the DSE candidate stmt. */ | |
563 || !dominated_by_p (CDI_POST_DOMINATORS, | |
564 gimple_bb (stmt), gimple_bb (use_stmt))) | |
565 { | 624 { |
566 fail = true; | 625 defs.safe_push (use_stmt); |
567 BREAK_FROM_IMM_USE_STMT (ui); | 626 phi_def = use_stmt; |
568 } | 627 } |
569 /* Do not consider the PHI as use if it dominates the | |
570 stmt defining the virtual operand we are processing, | |
571 we have processed it already in this case. */ | |
572 if (gimple_bb (defvar_def) != gimple_bb (use_stmt) | |
573 && !dominated_by_p (CDI_DOMINATORS, | |
574 gimple_bb (defvar_def), | |
575 gimple_bb (use_stmt))) | |
576 temp = use_stmt; | |
577 } | 628 } |
578 /* If the statement is a use the store is not dead. */ | 629 /* If the statement is a use the store is not dead. */ |
579 else if (ref_maybe_used_by_stmt_p (use_stmt, ref)) | 630 else if (ref_maybe_used_by_stmt_p (use_stmt, ref)) |
580 { | 631 { |
581 /* Handle common cases where we can easily build an ao_ref | 632 /* Handle common cases where we can easily build an ao_ref |
582 structure for USE_STMT and in doing so we find that the | 633 structure for USE_STMT and in doing so we find that the |
583 references hit non-live bytes and thus can be ignored. */ | 634 references hit non-live bytes and thus can be ignored. */ |
584 if (byte_tracking_enabled && (!gimple_vdef (use_stmt) || !temp)) | 635 if (byte_tracking_enabled |
636 && is_gimple_assign (use_stmt)) | |
585 { | 637 { |
586 if (is_gimple_assign (use_stmt)) | 638 ao_ref use_ref; |
639 ao_ref_init (&use_ref, gimple_assign_rhs1 (use_stmt)); | |
640 if (valid_ao_ref_for_dse (&use_ref) | |
641 && use_ref.base == ref->base | |
642 && known_eq (use_ref.size, use_ref.max_size) | |
643 && !live_bytes_read (use_ref, ref, live_bytes)) | |
587 { | 644 { |
588 /* Other cases were noted as non-aliasing by | 645 /* If this is a store, remember it as we possibly |
589 the call to ref_maybe_used_by_stmt_p. */ | 646 need to walk the defs uses. */ |
590 ao_ref use_ref; | 647 if (gimple_vdef (use_stmt)) |
591 ao_ref_init (&use_ref, gimple_assign_rhs1 (use_stmt)); | 648 defs.safe_push (use_stmt); |
592 if (valid_ao_ref_for_dse (&use_ref) | 649 continue; |
593 && use_ref.base == ref->base | |
594 && use_ref.size == use_ref.max_size | |
595 && !live_bytes_read (use_ref, ref, live_bytes)) | |
596 { | |
597 /* If this statement has a VDEF, then it is the | |
598 first store we have seen, so walk through it. */ | |
599 if (gimple_vdef (use_stmt)) | |
600 temp = use_stmt; | |
601 continue; | |
602 } | |
603 } | 650 } |
604 } | 651 } |
605 | 652 |
606 fail = true; | 653 fail = true; |
607 BREAK_FROM_IMM_USE_STMT (ui); | 654 BREAK_FROM_IMM_USE_STMT (ui); |
608 } | 655 } |
609 /* If this is a store, remember it or bail out if we have | 656 /* If this is a store, remember it as we possibly need to walk the |
610 multiple ones (the will be in different CFG parts then). */ | 657 defs uses. */ |
611 else if (gimple_vdef (use_stmt)) | 658 else if (gimple_vdef (use_stmt)) |
612 { | 659 defs.safe_push (use_stmt); |
613 if (temp) | |
614 { | |
615 fail = true; | |
616 BREAK_FROM_IMM_USE_STMT (ui); | |
617 } | |
618 temp = use_stmt; | |
619 } | |
620 } | 660 } |
621 | 661 |
622 if (fail) | 662 if (fail) |
623 { | 663 { |
624 /* STMT might be partially dead and we may be able to reduce | 664 /* STMT might be partially dead and we may be able to reduce |
629 } | 669 } |
630 | 670 |
631 /* If we didn't find any definition this means the store is dead | 671 /* If we didn't find any definition this means the store is dead |
632 if it isn't a store to global reachable memory. In this case | 672 if it isn't a store to global reachable memory. In this case |
633 just pretend the stmt makes itself dead. Otherwise fail. */ | 673 just pretend the stmt makes itself dead. Otherwise fail. */ |
634 if (!temp) | 674 if (defs.is_empty ()) |
635 { | 675 { |
636 if (ref_may_alias_global_p (ref)) | 676 if (ref_may_alias_global_p (ref)) |
637 return DSE_STORE_LIVE; | 677 return DSE_STORE_LIVE; |
638 | 678 |
639 temp = stmt; | 679 if (by_clobber_p) |
640 break; | 680 *by_clobber_p = false; |
681 return DSE_STORE_DEAD; | |
641 } | 682 } |
642 | 683 |
643 if (byte_tracking_enabled && temp) | 684 /* Process defs and remove those we need not process further. */ |
644 clear_bytes_written_by (live_bytes, temp, ref); | 685 for (unsigned i = 0; i < defs.length ();) |
645 } | 686 { |
646 /* Continue walking until we reach a full kill as a single statement | 687 gimple *def = defs[i]; |
647 or there are no more live bytes. */ | 688 gimple *use_stmt; |
648 while (!stmt_kills_ref_p (temp, ref) | 689 use_operand_p use_p; |
649 && !(byte_tracking_enabled && bitmap_empty_p (live_bytes))); | 690 /* If the path to check starts with a kill we do not need to |
650 | 691 process it further. |
651 *use_stmt = temp; | 692 ??? With byte tracking we need only kill the bytes currently |
652 return DSE_STORE_DEAD; | 693 live. */ |
694 if (stmt_kills_ref_p (def, ref)) | |
695 { | |
696 if (by_clobber_p && !gimple_clobber_p (def)) | |
697 *by_clobber_p = false; | |
698 defs.unordered_remove (i); | |
699 } | |
700 /* In addition to kills we can remove defs whose only use | |
701 is another def in defs. That can only ever be PHIs of which | |
702 we track a single for simplicity reasons (we fail for multiple | |
703 PHIs anyways). We can also ignore defs that feed only into | |
704 already visited PHIs. */ | |
705 else if (gimple_code (def) != GIMPLE_PHI | |
706 && single_imm_use (gimple_vdef (def), &use_p, &use_stmt) | |
707 && (use_stmt == phi_def | |
708 || (gimple_code (use_stmt) == GIMPLE_PHI | |
709 && bitmap_bit_p (visited, | |
710 SSA_NAME_VERSION | |
711 (PHI_RESULT (use_stmt)))))) | |
712 defs.unordered_remove (i); | |
713 else | |
714 ++i; | |
715 } | |
716 | |
717 /* If all defs kill the ref we are done. */ | |
718 if (defs.is_empty ()) | |
719 return DSE_STORE_DEAD; | |
720 /* If more than one def survives fail. */ | |
721 if (defs.length () > 1) | |
722 { | |
723 /* STMT might be partially dead and we may be able to reduce | |
724 how many memory locations it stores into. */ | |
725 if (byte_tracking_enabled && !gimple_clobber_p (stmt)) | |
726 return DSE_STORE_MAYBE_PARTIAL_DEAD; | |
727 return DSE_STORE_LIVE; | |
728 } | |
729 temp = defs[0]; | |
730 | |
731 /* Track partial kills. */ | |
732 if (byte_tracking_enabled) | |
733 { | |
734 clear_bytes_written_by (live_bytes, temp, ref); | |
735 if (bitmap_empty_p (live_bytes)) | |
736 { | |
737 if (by_clobber_p && !gimple_clobber_p (temp)) | |
738 *by_clobber_p = false; | |
739 return DSE_STORE_DEAD; | |
740 } | |
741 } | |
742 } | |
743 /* Continue walking until there are no more live bytes. */ | |
744 while (1); | |
653 } | 745 } |
654 | 746 |
655 | 747 |
656 class dse_dom_walker : public dom_walker | 748 class dse_dom_walker : public dom_walker |
657 { | 749 { |
777 { | 869 { |
778 delete_dead_call (gsi); | 870 delete_dead_call (gsi); |
779 return; | 871 return; |
780 } | 872 } |
781 | 873 |
782 gimple *use_stmt; | |
783 enum dse_store_status store_status; | 874 enum dse_store_status store_status; |
784 m_byte_tracking_enabled | 875 m_byte_tracking_enabled |
785 = setup_live_bytes_from_ref (&ref, m_live_bytes); | 876 = setup_live_bytes_from_ref (&ref, m_live_bytes); |
786 store_status = dse_classify_store (&ref, stmt, &use_stmt, | 877 store_status = dse_classify_store (&ref, stmt, |
787 m_byte_tracking_enabled, | 878 m_byte_tracking_enabled, |
788 m_live_bytes); | 879 m_live_bytes); |
789 if (store_status == DSE_STORE_LIVE) | 880 if (store_status == DSE_STORE_LIVE) |
790 return; | 881 return; |
791 | 882 |
805 } | 896 } |
806 } | 897 } |
807 | 898 |
808 if (is_gimple_assign (stmt)) | 899 if (is_gimple_assign (stmt)) |
809 { | 900 { |
810 gimple *use_stmt; | 901 bool by_clobber_p = false; |
811 | 902 |
812 /* Self-assignments are zombies. */ | 903 /* Self-assignments are zombies. */ |
813 if (operand_equal_p (gimple_assign_rhs1 (stmt), | 904 if (operand_equal_p (gimple_assign_rhs1 (stmt), |
814 gimple_assign_lhs (stmt), 0)) | 905 gimple_assign_lhs (stmt), 0)) |
815 use_stmt = stmt; | 906 ; |
816 else | 907 else |
817 { | 908 { |
818 m_byte_tracking_enabled | 909 m_byte_tracking_enabled |
819 = setup_live_bytes_from_ref (&ref, m_live_bytes); | 910 = setup_live_bytes_from_ref (&ref, m_live_bytes); |
820 enum dse_store_status store_status; | 911 enum dse_store_status store_status; |
821 store_status = dse_classify_store (&ref, stmt, &use_stmt, | 912 store_status = dse_classify_store (&ref, stmt, |
822 m_byte_tracking_enabled, | 913 m_byte_tracking_enabled, |
823 m_live_bytes); | 914 m_live_bytes, &by_clobber_p); |
824 if (store_status == DSE_STORE_LIVE) | 915 if (store_status == DSE_STORE_LIVE) |
825 return; | 916 return; |
826 | 917 |
827 if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD) | 918 if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD) |
828 { | 919 { |
834 /* Now we know that use_stmt kills the LHS of stmt. */ | 925 /* Now we know that use_stmt kills the LHS of stmt. */ |
835 | 926 |
836 /* But only remove *this_2(D) ={v} {CLOBBER} if killed by | 927 /* But only remove *this_2(D) ={v} {CLOBBER} if killed by |
837 another clobber stmt. */ | 928 another clobber stmt. */ |
838 if (gimple_clobber_p (stmt) | 929 if (gimple_clobber_p (stmt) |
839 && !gimple_clobber_p (use_stmt)) | 930 && !by_clobber_p) |
840 return; | 931 return; |
841 | 932 |
842 delete_dead_assignment (gsi); | 933 delete_dead_assignment (gsi); |
843 } | 934 } |
844 } | 935 } |