Mercurial > hg > CbC > CbC_gcc
annotate gcc/tree-ssa-dse.c @ 138:fc828634a951
merge
author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
---|---|
date | Thu, 08 Nov 2018 14:17:14 +0900 |
parents | 84e7813d76e9 |
children | 1830386684a0 |
rev | line source |
---|---|
0 | 1 /* Dead store elimination |
131 | 2 Copyright (C) 2004-2018 Free Software Foundation, Inc. |
0 | 3 |
4 This file is part of GCC. | |
5 | |
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 | |
8 the Free Software Foundation; either version 3, or (at your option) | |
9 any later version. | |
10 | |
11 GCC is distributed in the hope that it will be useful, | |
12 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 GNU General Public License for more details. | |
15 | |
16 You should have received a copy of the GNU General Public License | |
17 along with GCC; see the file COPYING3. If not see | |
18 <http://www.gnu.org/licenses/>. */ | |
19 | |
20 #include "config.h" | |
21 #include "system.h" | |
22 #include "coretypes.h" | |
111 | 23 #include "backend.h" |
24 #include "rtl.h" | |
0 | 25 #include "tree.h" |
111 | 26 #include "gimple.h" |
27 #include "tree-pass.h" | |
28 #include "ssa.h" | |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
29 #include "gimple-pretty-print.h" |
111 | 30 #include "fold-const.h" |
31 #include "gimple-iterator.h" | |
32 #include "tree-cfg.h" | |
33 #include "tree-dfa.h" | |
0 | 34 #include "domwalk.h" |
111 | 35 #include "tree-cfgcleanup.h" |
36 #include "params.h" | |
37 #include "alias.h" | |
131 | 38 #include "tree-ssa-loop.h" |
0 | 39 |
40 /* This file implements dead store elimination. | |
41 | |
42 A dead store is a store into a memory location which will later be | |
43 overwritten by another store without any intervening loads. In this | |
44 case the earlier store can be deleted. | |
45 | |
46 In our SSA + virtual operand world we use immediate uses of virtual | |
47 operands to detect dead stores. If a store's virtual definition | |
48 is used precisely once by a later store to the same location which | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
49 post dominates the first store, then the first store is dead. |
0 | 50 |
51 The single use of the store's virtual definition ensures that | |
52 there are no intervening aliased loads and the requirement that | |
53 the second load post dominate the first ensures that if the earlier | |
54 store executes, then the later stores will execute before the function | |
55 exits. | |
56 | |
57 It may help to think of this as first moving the earlier store to | |
58 the point immediately before the later store. Again, the single | |
59 use of the virtual definition and the post-dominance relationship | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
60 ensure that such movement would be safe. Clearly if there are |
0 | 61 back to back stores, then the second is redundant. |
62 | |
63 Reviewing section 10.7.2 in Morgan's "Building an Optimizing Compiler" | |
64 may also help in understanding this code since it discusses the | |
65 relationship between dead store and redundant load elimination. In | |
66 fact, they are the same transformation applied to different views of | |
67 the CFG. */ | |
68 | |
69 | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
70 /* Bitmap of blocks that have had EH statements cleaned. We should |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
71 remove their dead edges eventually. */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
72 static bitmap need_eh_cleanup; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
73 |
111 | 74 /* Return value from dse_classify_store */ |
75 enum dse_store_status | |
76 { | |
77 DSE_STORE_LIVE, | |
78 DSE_STORE_MAYBE_PARTIAL_DEAD, | |
79 DSE_STORE_DEAD | |
80 }; | |
81 | |
82 /* STMT is a statement that may write into memory. Analyze it and | |
83 initialize WRITE to describe how STMT affects memory. | |
84 | |
85 Return TRUE if the the statement was analyzed, FALSE otherwise. | |
86 | |
87 It is always safe to return FALSE. But typically better optimziation | |
88 can be achieved by analyzing more statements. */ | |
0 | 89 |
111 | 90 static bool |
91 initialize_ao_ref_for_dse (gimple *stmt, ao_ref *write) | |
0 | 92 { |
111 | 93 /* It's advantageous to handle certain mem* functions. */ |
94 if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)) | |
95 { | |
96 switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt))) | |
97 { | |
98 case BUILT_IN_MEMCPY: | |
99 case BUILT_IN_MEMMOVE: | |
100 case BUILT_IN_MEMSET: | |
101 { | |
102 tree size = NULL_TREE; | |
103 if (gimple_call_num_args (stmt) == 3) | |
104 size = gimple_call_arg (stmt, 2); | |
105 tree ptr = gimple_call_arg (stmt, 0); | |
106 ao_ref_init_from_ptr_and_size (write, ptr, size); | |
107 return true; | |
108 } | |
109 default: | |
110 break; | |
111 } | |
112 } | |
113 else if (is_gimple_assign (stmt)) | |
114 { | |
115 ao_ref_init (write, gimple_assign_lhs (stmt)); | |
116 return true; | |
117 } | |
118 return false; | |
0 | 119 } |
120 | |
111 | 121 /* Given REF from the the alias oracle, return TRUE if it is a valid |
122 memory reference for dead store elimination, false otherwise. | |
123 | |
124 In particular, the reference must have a known base, known maximum | |
125 size, start at a byte offset and have a size that is one or more | |
126 bytes. */ | |
127 | |
128 static bool | |
129 valid_ao_ref_for_dse (ao_ref *ref) | |
130 { | |
131 return (ao_ref_base (ref) | |
131 | 132 && known_size_p (ref->max_size) |
133 && maybe_ne (ref->size, 0) | |
134 && known_eq (ref->max_size, ref->size) | |
135 && known_ge (ref->offset, 0) | |
136 && multiple_p (ref->offset, BITS_PER_UNIT) | |
137 && multiple_p (ref->size, BITS_PER_UNIT)); | |
111 | 138 } |
139 | |
131 | 140 /* Try to 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 | |
142 is known to intersect at least one byte of REF. */ | |
111 | 143 |
131 | 144 static bool |
111 | 145 normalize_ref (ao_ref *copy, ao_ref *ref) |
0 | 146 { |
131 | 147 if (!ordered_p (copy->offset, ref->offset)) |
148 return false; | |
149 | |
111 | 150 /* If COPY starts before REF, then reset the beginning of |
151 COPY to match REF and decrease the size of COPY by the | |
152 number of bytes removed from COPY. */ | |
131 | 153 if (maybe_lt (copy->offset, ref->offset)) |
111 | 154 { |
131 | 155 poly_int64 diff = ref->offset - copy->offset; |
156 if (maybe_le (copy->size, diff)) | |
157 return false; | |
158 copy->size -= diff; | |
111 | 159 copy->offset = ref->offset; |
160 } | |
161 | |
131 | 162 poly_int64 diff = copy->offset - ref->offset; |
163 if (maybe_le (ref->size, diff)) | |
164 return false; | |
165 | |
111 | 166 /* If COPY extends beyond REF, chop off its size appropriately. */ |
131 | 167 poly_int64 limit = ref->size - diff; |
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; | |
111 | 174 } |
175 | |
176 /* Clear any bytes written by STMT from the bitmap LIVE_BYTES. The base | |
177 address written by STMT must match the one found in REF, which must | |
178 have its base address previously initialized. | |
179 | |
180 This routine must be conservative. If we don't know the offset or | |
181 actual size written, assume nothing was written. */ | |
0 | 182 |
111 | 183 static void |
184 clear_bytes_written_by (sbitmap live_bytes, gimple *stmt, ao_ref *ref) | |
185 { | |
186 ao_ref write; | |
187 if (!initialize_ao_ref_for_dse (stmt, &write)) | |
188 return; | |
189 | |
190 /* Verify we have the same base memory address, the write | |
191 has a known size and overlaps with REF. */ | |
131 | 192 HOST_WIDE_INT start, size; |
111 | 193 if (valid_ao_ref_for_dse (&write) |
194 && operand_equal_p (write.base, ref->base, OEP_ADDRESS_OF) | |
131 | 195 && known_eq (write.size, write.max_size) |
196 && normalize_ref (&write, ref) | |
197 && (write.offset - ref->offset).is_constant (&start) | |
198 && write.size.is_constant (&size)) | |
199 bitmap_clear_range (live_bytes, start / BITS_PER_UNIT, | |
200 size / BITS_PER_UNIT); | |
0 | 201 } |
202 | |
111 | 203 /* REF is a memory write. Extract relevant information from it and |
204 initialize the LIVE_BYTES bitmap. If successful, return TRUE. | |
205 Otherwise return FALSE. */ | |
206 | |
207 static bool | |
208 setup_live_bytes_from_ref (ao_ref *ref, sbitmap live_bytes) | |
209 { | |
131 | 210 HOST_WIDE_INT const_size; |
111 | 211 if (valid_ao_ref_for_dse (ref) |
131 | 212 && ref->size.is_constant (&const_size) |
213 && (const_size / BITS_PER_UNIT | |
111 | 214 <= PARAM_VALUE (PARAM_DSE_MAX_OBJECT_SIZE))) |
215 { | |
216 bitmap_clear (live_bytes); | |
131 | 217 bitmap_set_range (live_bytes, 0, const_size / BITS_PER_UNIT); |
111 | 218 return true; |
219 } | |
220 return false; | |
221 } | |
222 | |
223 /* Compute the number of elements that we can trim from the head and | |
224 tail of ORIG resulting in a bitmap that is a superset of LIVE. | |
225 | |
226 Store the number of elements trimmed from the head and tail in | |
227 TRIM_HEAD and TRIM_TAIL. | |
228 | |
229 STMT is the statement being trimmed and is used for debugging dump | |
230 output only. */ | |
0 | 231 |
232 static void | |
111 | 233 compute_trims (ao_ref *ref, sbitmap live, int *trim_head, int *trim_tail, |
234 gimple *stmt) | |
0 | 235 { |
111 | 236 /* We use sbitmaps biased such that ref->offset is bit zero and the bitmap |
237 extends through ref->size. So we know that in the original bitmap | |
238 bits 0..ref->size were true. We don't actually need the bitmap, just | |
239 the REF to compute the trims. */ | |
240 | |
241 /* Now identify how much, if any of the tail we can chop off. */ | |
131 | 242 HOST_WIDE_INT const_size; |
111 | 243 int last_live = bitmap_last_set_bit (live); |
131 | 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; | |
0 | 266 |
111 | 267 /* Identify how much, if any of the head we can chop off. */ |
268 int first_orig = 0; | |
269 int first_live = bitmap_first_set_bit (live); | |
131 | 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); | |
111 | 276 |
277 if ((*trim_head || *trim_tail) | |
278 && dump_file && (dump_flags & TDF_DETAILS)) | |
0 | 279 { |
111 | 280 fprintf (dump_file, " Trimming statement (head = %d, tail = %d): ", |
281 *trim_head, *trim_tail); | |
282 print_gimple_stmt (dump_file, stmt, 0, dump_flags); | |
283 fprintf (dump_file, "\n"); | |
0 | 284 } |
285 } | |
286 | |
111 | 287 /* STMT initializes an object from COMPLEX_CST where one or more of the |
288 bytes written may be dead stores. REF is a representation of the | |
289 memory written. LIVE is the bitmap of stores that are actually live. | |
290 | |
291 Attempt to rewrite STMT so that only the real or imaginary part of | |
292 the object is actually stored. */ | |
293 | |
294 static void | |
295 maybe_trim_complex_store (ao_ref *ref, sbitmap live, gimple *stmt) | |
296 { | |
297 int trim_head, trim_tail; | |
298 compute_trims (ref, live, &trim_head, &trim_tail, stmt); | |
299 | |
300 /* The amount of data trimmed from the head or tail must be at | |
301 least half the size of the object to ensure we're trimming | |
302 the entire real or imaginary half. By writing things this | |
303 way we avoid more O(n) bitmap operations. */ | |
131 | 304 if (known_ge (trim_tail * 2 * BITS_PER_UNIT, ref->size)) |
111 | 305 { |
306 /* TREE_REALPART is live */ | |
307 tree x = TREE_REALPART (gimple_assign_rhs1 (stmt)); | |
308 tree y = gimple_assign_lhs (stmt); | |
309 y = build1 (REALPART_EXPR, TREE_TYPE (x), y); | |
310 gimple_assign_set_lhs (stmt, y); | |
311 gimple_assign_set_rhs1 (stmt, x); | |
312 } | |
131 | 313 else if (known_ge (trim_head * 2 * BITS_PER_UNIT, ref->size)) |
111 | 314 { |
315 /* TREE_IMAGPART is live */ | |
316 tree x = TREE_IMAGPART (gimple_assign_rhs1 (stmt)); | |
317 tree y = gimple_assign_lhs (stmt); | |
318 y = build1 (IMAGPART_EXPR, TREE_TYPE (x), y); | |
319 gimple_assign_set_lhs (stmt, y); | |
320 gimple_assign_set_rhs1 (stmt, x); | |
321 } | |
322 | |
323 /* Other cases indicate parts of both the real and imag subobjects | |
324 are live. We do not try to optimize those cases. */ | |
325 } | |
326 | |
327 /* STMT initializes an object using a CONSTRUCTOR where one or more of the | |
328 bytes written are dead stores. ORIG is the bitmap of bytes stored by | |
329 STMT. LIVE is the bitmap of stores that are actually live. | |
330 | |
331 Attempt to rewrite STMT so that only the real or imaginary part of | |
332 the object is actually stored. | |
333 | |
334 The most common case for getting here is a CONSTRUCTOR with no elements | |
335 being used to zero initialize an object. We do not try to handle other | |
336 cases as those would force us to fully cover the object with the | |
337 CONSTRUCTOR node except for the components that are dead. */ | |
338 | |
339 static void | |
340 maybe_trim_constructor_store (ao_ref *ref, sbitmap live, gimple *stmt) | |
341 { | |
342 tree ctor = gimple_assign_rhs1 (stmt); | |
343 | |
344 /* This is the only case we currently handle. It actually seems to | |
345 catch most cases of actual interest. */ | |
346 gcc_assert (CONSTRUCTOR_NELTS (ctor) == 0); | |
347 | |
348 int head_trim = 0; | |
349 int tail_trim = 0; | |
350 compute_trims (ref, live, &head_trim, &tail_trim, stmt); | |
351 | |
352 /* Now we want to replace the constructor initializer | |
353 with memset (object + head_trim, 0, size - head_trim - tail_trim). */ | |
354 if (head_trim || tail_trim) | |
355 { | |
356 /* We want &lhs for the MEM_REF expression. */ | |
357 tree lhs_addr = build_fold_addr_expr (gimple_assign_lhs (stmt)); | |
358 | |
359 if (! is_gimple_min_invariant (lhs_addr)) | |
360 return; | |
361 | |
362 /* The number of bytes for the new constructor. */ | |
131 | 363 poly_int64 ref_bytes = exact_div (ref->size, BITS_PER_UNIT); |
364 poly_int64 count = ref_bytes - head_trim - tail_trim; | |
111 | 365 |
366 /* And the new type for the CONSTRUCTOR. Essentially it's just | |
367 a char array large enough to cover the non-trimmed parts of | |
368 the original CONSTRUCTOR. Note we want explicit bounds here | |
369 so that we know how many bytes to clear when expanding the | |
370 CONSTRUCTOR. */ | |
371 tree type = build_array_type_nelts (char_type_node, count); | |
372 | |
373 /* Build a suitable alias type rather than using alias set zero | |
374 to avoid pessimizing. */ | |
375 tree alias_type = reference_alias_ptr_type (gimple_assign_lhs (stmt)); | |
376 | |
377 /* Build a MEM_REF representing the whole accessed area, starting | |
378 at the first byte not trimmed. */ | |
379 tree exp = fold_build2 (MEM_REF, type, lhs_addr, | |
380 build_int_cst (alias_type, head_trim)); | |
381 | |
382 /* Now update STMT with a new RHS and LHS. */ | |
383 gimple_assign_set_lhs (stmt, exp); | |
384 gimple_assign_set_rhs1 (stmt, build_constructor (type, NULL)); | |
385 } | |
386 } | |
387 | |
388 /* STMT is a memcpy, memmove or memset. Decrement the number of bytes | |
389 copied/set by DECREMENT. */ | |
390 static void | |
391 decrement_count (gimple *stmt, int decrement) | |
392 { | |
393 tree *countp = gimple_call_arg_ptr (stmt, 2); | |
394 gcc_assert (TREE_CODE (*countp) == INTEGER_CST); | |
395 *countp = wide_int_to_tree (TREE_TYPE (*countp), (TREE_INT_CST_LOW (*countp) | |
396 - decrement)); | |
397 | |
398 } | |
399 | |
400 static void | |
401 increment_start_addr (gimple *stmt, tree *where, int increment) | |
402 { | |
403 if (TREE_CODE (*where) == SSA_NAME) | |
404 { | |
405 tree tem = make_ssa_name (TREE_TYPE (*where)); | |
406 gassign *newop | |
407 = gimple_build_assign (tem, POINTER_PLUS_EXPR, *where, | |
408 build_int_cst (sizetype, increment)); | |
409 gimple_stmt_iterator gsi = gsi_for_stmt (stmt); | |
410 gsi_insert_before (&gsi, newop, GSI_SAME_STMT); | |
411 *where = tem; | |
412 update_stmt (gsi_stmt (gsi)); | |
413 return; | |
414 } | |
415 | |
416 *where = build_fold_addr_expr (fold_build2 (MEM_REF, char_type_node, | |
417 *where, | |
418 build_int_cst (ptr_type_node, | |
419 increment))); | |
420 } | |
421 | |
422 /* STMT is builtin call that writes bytes in bitmap ORIG, some bytes are dead | |
423 (ORIG & ~NEW) and need not be stored. Try to rewrite STMT to reduce | |
424 the amount of data it actually writes. | |
425 | |
426 Right now we only support trimming from the head or the tail of the | |
427 memory region. In theory we could split the mem* call, but it's | |
428 likely of marginal value. */ | |
429 | |
430 static void | |
431 maybe_trim_memstar_call (ao_ref *ref, sbitmap live, gimple *stmt) | |
432 { | |
433 switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt))) | |
434 { | |
435 case BUILT_IN_MEMCPY: | |
436 case BUILT_IN_MEMMOVE: | |
437 { | |
438 int head_trim, tail_trim; | |
439 compute_trims (ref, live, &head_trim, &tail_trim, stmt); | |
440 | |
441 /* Tail trimming is easy, we can just reduce the count. */ | |
442 if (tail_trim) | |
443 decrement_count (stmt, tail_trim); | |
444 | |
445 /* Head trimming requires adjusting all the arguments. */ | |
446 if (head_trim) | |
447 { | |
448 tree *dst = gimple_call_arg_ptr (stmt, 0); | |
449 increment_start_addr (stmt, dst, head_trim); | |
450 tree *src = gimple_call_arg_ptr (stmt, 1); | |
451 increment_start_addr (stmt, src, head_trim); | |
452 decrement_count (stmt, head_trim); | |
453 } | |
454 break; | |
455 } | |
456 | |
457 case BUILT_IN_MEMSET: | |
458 { | |
459 int head_trim, tail_trim; | |
460 compute_trims (ref, live, &head_trim, &tail_trim, stmt); | |
461 | |
462 /* Tail trimming is easy, we can just reduce the count. */ | |
463 if (tail_trim) | |
464 decrement_count (stmt, tail_trim); | |
465 | |
466 /* Head trimming requires adjusting all the arguments. */ | |
467 if (head_trim) | |
468 { | |
469 tree *dst = gimple_call_arg_ptr (stmt, 0); | |
470 increment_start_addr (stmt, dst, head_trim); | |
471 decrement_count (stmt, head_trim); | |
472 } | |
473 break; | |
474 } | |
475 | |
476 default: | |
477 break; | |
478 } | |
479 } | |
480 | |
481 /* STMT is a memory write where one or more bytes written are dead | |
482 stores. ORIG is the bitmap of bytes stored by STMT. LIVE is the | |
483 bitmap of stores that are actually live. | |
484 | |
485 Attempt to rewrite STMT so that it writes fewer memory locations. Right | |
486 now we only support trimming at the start or end of the memory region. | |
487 It's not clear how much there is to be gained by trimming from the middle | |
488 of the region. */ | |
489 | |
490 static void | |
491 maybe_trim_partially_dead_store (ao_ref *ref, sbitmap live, gimple *stmt) | |
492 { | |
493 if (is_gimple_assign (stmt) | |
494 && TREE_CODE (gimple_assign_lhs (stmt)) != TARGET_MEM_REF) | |
495 { | |
496 switch (gimple_assign_rhs_code (stmt)) | |
497 { | |
498 case CONSTRUCTOR: | |
499 maybe_trim_constructor_store (ref, live, stmt); | |
500 break; | |
501 case COMPLEX_CST: | |
502 maybe_trim_complex_store (ref, live, stmt); | |
503 break; | |
504 default: | |
505 break; | |
506 } | |
507 } | |
508 } | |
509 | |
510 /* Return TRUE if USE_REF reads bytes from LIVE where live is | |
511 derived from REF, a write reference. | |
512 | |
513 While this routine may modify USE_REF, it's passed by value, not | |
514 location. So callers do not see those modifications. */ | |
515 | |
516 static bool | |
517 live_bytes_read (ao_ref use_ref, ao_ref *ref, sbitmap live) | |
518 { | |
519 /* We have already verified that USE_REF and REF hit the same object. | |
520 Now verify that there's actually an overlap between USE_REF and REF. */ | |
131 | 521 HOST_WIDE_INT start, size; |
522 if (normalize_ref (&use_ref, ref) | |
523 && (use_ref.offset - ref->offset).is_constant (&start) | |
524 && use_ref.size.is_constant (&size)) | |
111 | 525 { |
526 /* If USE_REF covers all of REF, then it will hit one or more | |
527 live bytes. This avoids useless iteration over the bitmap | |
528 below. */ | |
131 | 529 if (start == 0 && known_eq (size, ref->size)) |
111 | 530 return true; |
531 | |
532 /* Now check if any of the remaining bits in use_ref are set in LIVE. */ | |
131 | 533 return bitmap_bit_in_range_p (live, start / BITS_PER_UNIT, |
534 (start + size - 1) / BITS_PER_UNIT); | |
111 | 535 } |
536 return true; | |
537 } | |
538 | |
131 | 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 | |
0 | 554 /* A helper of dse_optimize_stmt. |
131 | 555 Given a GIMPLE_ASSIGN in STMT that writes to REF, classify it |
556 according to downstream uses and defs. Sets *BY_CLOBBER_P to true | |
557 if only clobber statements influenced the classification result. | |
558 Returns the classification. */ | |
0 | 559 |
111 | 560 static dse_store_status |
131 | 561 dse_classify_store (ao_ref *ref, gimple *stmt, |
562 bool byte_tracking_enabled, sbitmap live_bytes, | |
563 bool *by_clobber_p = NULL) | |
0 | 564 { |
111 | 565 gimple *temp; |
131 | 566 int cnt = 0; |
567 auto_bitmap visited; | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
568 |
131 | 569 if (by_clobber_p) |
570 *by_clobber_p = true; | |
0 | 571 |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
572 /* Find the first dominated statement that clobbers (part of) the |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
573 memory stmt stores to with no intermediate statement that may use |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
574 part of the memory stmt stores. That is, find a store that may |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
575 prove stmt to be a dead store. */ |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
576 temp = stmt; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
577 do |
0 | 578 { |
131 | 579 gimple *use_stmt; |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
580 imm_use_iterator ui; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
581 bool fail = false; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
582 tree defvar; |
0 | 583 |
584 if (gimple_code (temp) == GIMPLE_PHI) | |
131 | 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 } | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
597 else |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
598 defvar = gimple_vdef (temp); |
131 | 599 auto_vec<gimple *, 10> defs; |
600 gimple *phi_def = NULL; | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
601 FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar) |
0 | 602 { |
131 | 603 /* Limit stmt walking. */ |
604 if (++cnt > PARAM_VALUE (PARAM_DSE_MAX_ALIAS_QUERIES_PER_STORE)) | |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
605 { |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
606 fail = true; |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
607 BREAK_FROM_IMM_USE_STMT (ui); |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
608 } |
131 | 609 |
610 /* We have visited ourselves already so ignore STMT for the | |
611 purpose of chaining. */ | |
612 if (use_stmt == stmt) | |
613 ; | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
614 /* In simple cases we can look through PHI nodes, but we |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
615 have to be careful with loops and with memory references |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
616 containing operands that are also operands of PHI nodes. |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
617 See gcc.c-torture/execute/20051110-*.c. */ |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
618 else if (gimple_code (use_stmt) == GIMPLE_PHI) |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
619 { |
131 | 620 /* If we already visited this PHI ignore it for further |
621 processing. */ | |
622 if (!bitmap_bit_p (visited, | |
623 SSA_NAME_VERSION (PHI_RESULT (use_stmt)))) | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
624 { |
131 | 625 defs.safe_push (use_stmt); |
626 phi_def = use_stmt; | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
627 } |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
628 } |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
629 /* If the statement is a use the store is not dead. */ |
111 | 630 else if (ref_maybe_used_by_stmt_p (use_stmt, ref)) |
0 | 631 { |
111 | 632 /* Handle common cases where we can easily build an ao_ref |
633 structure for USE_STMT and in doing so we find that the | |
634 references hit non-live bytes and thus can be ignored. */ | |
131 | 635 if (byte_tracking_enabled |
636 && is_gimple_assign (use_stmt)) | |
111 | 637 { |
131 | 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)) | |
111 | 644 { |
131 | 645 /* If this is a store, remember it as we possibly |
646 need to walk the defs uses. */ | |
647 if (gimple_vdef (use_stmt)) | |
648 defs.safe_push (use_stmt); | |
649 continue; | |
111 | 650 } |
651 } | |
652 | |
0 | 653 fail = true; |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
654 BREAK_FROM_IMM_USE_STMT (ui); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
655 } |
131 | 656 /* If this is a store, remember it as we possibly need to walk the |
657 defs uses. */ | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
658 else if (gimple_vdef (use_stmt)) |
131 | 659 defs.safe_push (use_stmt); |
0 | 660 } |
661 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
662 if (fail) |
111 | 663 { |
664 /* STMT might be partially dead and we may be able to reduce | |
665 how many memory locations it stores into. */ | |
666 if (byte_tracking_enabled && !gimple_clobber_p (stmt)) | |
667 return DSE_STORE_MAYBE_PARTIAL_DEAD; | |
668 return DSE_STORE_LIVE; | |
669 } | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
670 |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
671 /* If we didn't find any definition this means the store is dead |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
672 if it isn't a store to global reachable memory. In this case |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
673 just pretend the stmt makes itself dead. Otherwise fail. */ |
131 | 674 if (defs.is_empty ()) |
0 | 675 { |
111 | 676 if (ref_may_alias_global_p (ref)) |
677 return DSE_STORE_LIVE; | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
678 |
131 | 679 if (by_clobber_p) |
680 *by_clobber_p = false; | |
681 return DSE_STORE_DEAD; | |
0 | 682 } |
111 | 683 |
131 | 684 /* Process defs and remove those we need not process further. */ |
685 for (unsigned i = 0; i < defs.length ();) | |
686 { | |
687 gimple *def = defs[i]; | |
688 gimple *use_stmt; | |
689 use_operand_p use_p; | |
690 /* If the path to check starts with a kill we do not need to | |
691 process it further. | |
692 ??? With byte tracking we need only kill the bytes currently | |
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 } | |
0 | 742 } |
131 | 743 /* Continue walking until there are no more live bytes. */ |
744 while (1); | |
0 | 745 } |
746 | |
747 | |
111 | 748 class dse_dom_walker : public dom_walker |
749 { | |
750 public: | |
751 dse_dom_walker (cdi_direction direction) | |
752 : dom_walker (direction), | |
753 m_live_bytes (PARAM_VALUE (PARAM_DSE_MAX_OBJECT_SIZE)), | |
754 m_byte_tracking_enabled (false) {} | |
755 | |
756 virtual edge before_dom_children (basic_block); | |
757 | |
758 private: | |
759 auto_sbitmap m_live_bytes; | |
760 bool m_byte_tracking_enabled; | |
761 void dse_optimize_stmt (gimple_stmt_iterator *); | |
762 }; | |
763 | |
764 /* Delete a dead call at GSI, which is mem* call of some kind. */ | |
765 static void | |
766 delete_dead_call (gimple_stmt_iterator *gsi) | |
767 { | |
768 gimple *stmt = gsi_stmt (*gsi); | |
769 if (dump_file && (dump_flags & TDF_DETAILS)) | |
770 { | |
771 fprintf (dump_file, " Deleted dead call: "); | |
772 print_gimple_stmt (dump_file, stmt, 0, dump_flags); | |
773 fprintf (dump_file, "\n"); | |
774 } | |
775 | |
776 tree lhs = gimple_call_lhs (stmt); | |
777 if (lhs) | |
778 { | |
779 tree ptr = gimple_call_arg (stmt, 0); | |
780 gimple *new_stmt = gimple_build_assign (lhs, ptr); | |
781 unlink_stmt_vdef (stmt); | |
782 if (gsi_replace (gsi, new_stmt, true)) | |
783 bitmap_set_bit (need_eh_cleanup, gimple_bb (stmt)->index); | |
784 } | |
785 else | |
786 { | |
787 /* Then we need to fix the operand of the consuming stmt. */ | |
788 unlink_stmt_vdef (stmt); | |
789 | |
790 /* Remove the dead store. */ | |
791 if (gsi_remove (gsi, true)) | |
792 bitmap_set_bit (need_eh_cleanup, gimple_bb (stmt)->index); | |
793 release_defs (stmt); | |
794 } | |
795 } | |
796 | |
797 /* Delete a dead store at GSI, which is a gimple assignment. */ | |
798 | |
799 static void | |
800 delete_dead_assignment (gimple_stmt_iterator *gsi) | |
801 { | |
802 gimple *stmt = gsi_stmt (*gsi); | |
803 if (dump_file && (dump_flags & TDF_DETAILS)) | |
804 { | |
805 fprintf (dump_file, " Deleted dead store: "); | |
806 print_gimple_stmt (dump_file, stmt, 0, dump_flags); | |
807 fprintf (dump_file, "\n"); | |
808 } | |
809 | |
810 /* Then we need to fix the operand of the consuming stmt. */ | |
811 unlink_stmt_vdef (stmt); | |
812 | |
813 /* Remove the dead store. */ | |
814 basic_block bb = gimple_bb (stmt); | |
815 if (gsi_remove (gsi, true)) | |
816 bitmap_set_bit (need_eh_cleanup, bb->index); | |
817 | |
818 /* And release any SSA_NAMEs set in this statement back to the | |
819 SSA_NAME manager. */ | |
820 release_defs (stmt); | |
821 } | |
822 | |
0 | 823 /* Attempt to eliminate dead stores in the statement referenced by BSI. |
824 | |
825 A dead store is a store into a memory location which will later be | |
826 overwritten by another store without any intervening loads. In this | |
827 case the earlier store can be deleted. | |
828 | |
829 In our SSA + virtual operand world we use immediate uses of virtual | |
830 operands to detect dead stores. If a store's virtual definition | |
831 is used precisely once by a later store to the same location which | |
832 post dominates the first store, then the first store is dead. */ | |
833 | |
111 | 834 void |
835 dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi) | |
0 | 836 { |
111 | 837 gimple *stmt = gsi_stmt (*gsi); |
0 | 838 |
839 /* If this statement has no virtual defs, then there is nothing | |
840 to do. */ | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
841 if (!gimple_vdef (stmt)) |
0 | 842 return; |
843 | |
111 | 844 /* Don't return early on *this_2(D) ={v} {CLOBBER}. */ |
845 if (gimple_has_volatile_ops (stmt) | |
846 && (!gimple_clobber_p (stmt) | |
847 || TREE_CODE (gimple_assign_lhs (stmt)) != MEM_REF)) | |
848 return; | |
849 | |
850 ao_ref ref; | |
851 if (!initialize_ao_ref_for_dse (stmt, &ref)) | |
0 | 852 return; |
853 | |
111 | 854 /* We know we have virtual definitions. We can handle assignments and |
855 some builtin calls. */ | |
856 if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)) | |
857 { | |
858 switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt))) | |
859 { | |
860 case BUILT_IN_MEMCPY: | |
861 case BUILT_IN_MEMMOVE: | |
862 case BUILT_IN_MEMSET: | |
863 { | |
864 /* Occasionally calls with an explicit length of zero | |
865 show up in the IL. It's pointless to do analysis | |
866 on them, they're trivially dead. */ | |
867 tree size = gimple_call_arg (stmt, 2); | |
868 if (integer_zerop (size)) | |
869 { | |
870 delete_dead_call (gsi); | |
871 return; | |
872 } | |
873 | |
874 enum dse_store_status store_status; | |
875 m_byte_tracking_enabled | |
876 = setup_live_bytes_from_ref (&ref, m_live_bytes); | |
131 | 877 store_status = dse_classify_store (&ref, stmt, |
111 | 878 m_byte_tracking_enabled, |
879 m_live_bytes); | |
880 if (store_status == DSE_STORE_LIVE) | |
881 return; | |
882 | |
883 if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD) | |
884 { | |
885 maybe_trim_memstar_call (&ref, m_live_bytes, stmt); | |
886 return; | |
887 } | |
888 | |
889 if (store_status == DSE_STORE_DEAD) | |
890 delete_dead_call (gsi); | |
891 return; | |
892 } | |
893 | |
894 default: | |
895 return; | |
896 } | |
897 } | |
0 | 898 |
899 if (is_gimple_assign (stmt)) | |
900 { | |
131 | 901 bool by_clobber_p = false; |
0 | 902 |
111 | 903 /* Self-assignments are zombies. */ |
904 if (operand_equal_p (gimple_assign_rhs1 (stmt), | |
905 gimple_assign_lhs (stmt), 0)) | |
131 | 906 ; |
111 | 907 else |
908 { | |
909 m_byte_tracking_enabled | |
910 = setup_live_bytes_from_ref (&ref, m_live_bytes); | |
911 enum dse_store_status store_status; | |
131 | 912 store_status = dse_classify_store (&ref, stmt, |
111 | 913 m_byte_tracking_enabled, |
131 | 914 m_live_bytes, &by_clobber_p); |
111 | 915 if (store_status == DSE_STORE_LIVE) |
916 return; | |
0 | 917 |
111 | 918 if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD) |
919 { | |
920 maybe_trim_partially_dead_store (&ref, m_live_bytes, stmt); | |
921 return; | |
922 } | |
923 } | |
924 | |
925 /* Now we know that use_stmt kills the LHS of stmt. */ | |
926 | |
927 /* But only remove *this_2(D) ={v} {CLOBBER} if killed by | |
928 another clobber stmt. */ | |
929 if (gimple_clobber_p (stmt) | |
131 | 930 && !by_clobber_p) |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
931 return; |
0 | 932 |
111 | 933 delete_dead_assignment (gsi); |
0 | 934 } |
935 } | |
936 | |
111 | 937 edge |
938 dse_dom_walker::before_dom_children (basic_block bb) | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
939 { |
0 | 940 gimple_stmt_iterator gsi; |
941 | |
111 | 942 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);) |
943 { | |
944 dse_optimize_stmt (&gsi); | |
945 if (gsi_end_p (gsi)) | |
946 gsi = gsi_last_bb (bb); | |
947 else | |
948 gsi_prev (&gsi); | |
949 } | |
950 return NULL; | |
0 | 951 } |
952 | |
111 | 953 namespace { |
954 | |
955 const pass_data pass_data_dse = | |
0 | 956 { |
111 | 957 GIMPLE_PASS, /* type */ |
958 "dse", /* name */ | |
959 OPTGROUP_NONE, /* optinfo_flags */ | |
960 TV_TREE_DSE, /* tv_id */ | |
961 ( PROP_cfg | PROP_ssa ), /* properties_required */ | |
962 0, /* properties_provided */ | |
963 0, /* properties_destroyed */ | |
964 0, /* todo_flags_start */ | |
965 0, /* todo_flags_finish */ | |
966 }; | |
0 | 967 |
111 | 968 class pass_dse : public gimple_opt_pass |
969 { | |
970 public: | |
971 pass_dse (gcc::context *ctxt) | |
972 : gimple_opt_pass (pass_data_dse, ctxt) | |
973 {} | |
0 | 974 |
111 | 975 /* opt_pass methods: */ |
976 opt_pass * clone () { return new pass_dse (m_ctxt); } | |
977 virtual bool gate (function *) { return flag_tree_dse != 0; } | |
978 virtual unsigned int execute (function *); | |
0 | 979 |
111 | 980 }; // class pass_dse |
981 | |
982 unsigned int | |
983 pass_dse::execute (function *fun) | |
0 | 984 { |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
985 need_eh_cleanup = BITMAP_ALLOC (NULL); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
986 |
0 | 987 renumber_gimple_stmt_uids (); |
988 | |
989 /* We might consider making this a property of each pass so that it | |
990 can be [re]computed on an as-needed basis. Particularly since | |
991 this pass could be seen as an extension of DCE which needs post | |
992 dominators. */ | |
993 calculate_dominance_info (CDI_POST_DOMINATORS); | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
994 calculate_dominance_info (CDI_DOMINATORS); |
0 | 995 |
996 /* Dead store elimination is fundamentally a walk of the post-dominator | |
997 tree and a backwards walk of statements within each block. */ | |
111 | 998 dse_dom_walker (CDI_POST_DOMINATORS).walk (fun->cfg->x_exit_block_ptr); |
0 | 999 |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1000 /* Removal of stores may make some EH edges dead. Purge such edges from |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1001 the CFG as needed. */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1002 if (!bitmap_empty_p (need_eh_cleanup)) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1003 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1004 gimple_purge_all_dead_eh_edges (need_eh_cleanup); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1005 cleanup_tree_cfg (); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1006 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1007 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1008 BITMAP_FREE (need_eh_cleanup); |
111 | 1009 |
0 | 1010 /* For now, just wipe the post-dominator information. */ |
1011 free_dominance_info (CDI_POST_DOMINATORS); | |
1012 return 0; | |
1013 } | |
1014 | |
111 | 1015 } // anon namespace |
0 | 1016 |
111 | 1017 gimple_opt_pass * |
1018 make_pass_dse (gcc::context *ctxt) | |
0 | 1019 { |
111 | 1020 return new pass_dse (ctxt); |
1021 } |