Mercurial > hg > CbC > CbC_gcc
annotate gcc/tree-ssa-dse.c @ 127:4c56639505ff
fix function.c and add CbC-example Makefile
| author | mir3636 |
|---|---|
| date | Wed, 11 Apr 2018 18:46:58 +0900 |
| parents | 04ced10e8804 |
| children | 84e7813d76e9 |
| rev | line source |
|---|---|
| 0 | 1 /* Dead store elimination |
| 111 | 2 Copyright (C) 2004-2017 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" | |
| 0 | 38 |
| 39 /* This file implements dead store elimination. | |
| 40 | |
| 41 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 case the earlier store can be deleted. | |
| 44 | |
| 45 In our SSA + virtual operand world we use immediate uses of virtual | |
| 46 operands to detect dead stores. If a store's virtual definition | |
| 47 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
|
48 post dominates the first store, then the first store is dead. |
| 0 | 49 |
| 50 The single use of the store's virtual definition ensures that | |
| 51 there are no intervening aliased loads and the requirement that | |
| 52 the second load post dominate the first ensures that if the earlier | |
| 53 store executes, then the later stores will execute before the function | |
| 54 exits. | |
| 55 | |
| 56 It may help to think of this as first moving the earlier store to | |
| 57 the point immediately before the later store. Again, the single | |
| 58 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
|
59 ensure that such movement would be safe. Clearly if there are |
| 0 | 60 back to back stores, then the second is redundant. |
| 61 | |
| 62 Reviewing section 10.7.2 in Morgan's "Building an Optimizing Compiler" | |
| 63 may also help in understanding this code since it discusses the | |
| 64 relationship between dead store and redundant load elimination. In | |
| 65 fact, they are the same transformation applied to different views of | |
| 66 the CFG. */ | |
| 67 | |
| 68 | |
|
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
|
69 /* 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
|
70 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
|
71 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
|
72 |
| 111 | 73 /* Return value from dse_classify_store */ |
| 74 enum dse_store_status | |
| 75 { | |
| 76 DSE_STORE_LIVE, | |
| 77 DSE_STORE_MAYBE_PARTIAL_DEAD, | |
| 78 DSE_STORE_DEAD | |
| 79 }; | |
| 80 | |
| 81 /* STMT is a statement that may write into memory. Analyze it and | |
| 82 initialize WRITE to describe how STMT affects memory. | |
| 83 | |
| 84 Return TRUE if the the statement was analyzed, FALSE otherwise. | |
| 85 | |
| 86 It is always safe to return FALSE. But typically better optimziation | |
| 87 can be achieved by analyzing more statements. */ | |
| 0 | 88 |
| 111 | 89 static bool |
| 90 initialize_ao_ref_for_dse (gimple *stmt, ao_ref *write) | |
| 0 | 91 { |
| 111 | 92 /* It's advantageous to handle certain mem* functions. */ |
| 93 if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)) | |
| 94 { | |
| 95 switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt))) | |
| 96 { | |
| 97 case BUILT_IN_MEMCPY: | |
| 98 case BUILT_IN_MEMMOVE: | |
| 99 case BUILT_IN_MEMSET: | |
| 100 { | |
| 101 tree size = NULL_TREE; | |
| 102 if (gimple_call_num_args (stmt) == 3) | |
| 103 size = gimple_call_arg (stmt, 2); | |
| 104 tree ptr = gimple_call_arg (stmt, 0); | |
| 105 ao_ref_init_from_ptr_and_size (write, ptr, size); | |
| 106 return true; | |
| 107 } | |
| 108 default: | |
| 109 break; | |
| 110 } | |
| 111 } | |
| 112 else if (is_gimple_assign (stmt)) | |
| 113 { | |
| 114 ao_ref_init (write, gimple_assign_lhs (stmt)); | |
| 115 return true; | |
| 116 } | |
| 117 return false; | |
| 0 | 118 } |
| 119 | |
| 111 | 120 /* Given REF from the the alias oracle, return TRUE if it is a valid |
| 121 memory reference for dead store elimination, false otherwise. | |
| 122 | |
| 123 In particular, the reference must have a known base, known maximum | |
| 124 size, start at a byte offset and have a size that is one or more | |
| 125 bytes. */ | |
| 126 | |
| 127 static bool | |
| 128 valid_ao_ref_for_dse (ao_ref *ref) | |
| 129 { | |
| 130 return (ao_ref_base (ref) | |
| 131 && ref->max_size != -1 | |
| 132 && ref->size != 0 | |
| 133 && ref->max_size == ref->size | |
| 134 && ref->offset >= 0 | |
| 135 && (ref->offset % BITS_PER_UNIT) == 0 | |
| 136 && (ref->size % BITS_PER_UNIT) == 0 | |
| 137 && (ref->size != -1)); | |
| 138 } | |
| 139 | |
| 140 /* Normalize COPY (an ao_ref) relative to REF. Essentially when we are | |
| 141 done COPY will only refer bytes found within REF. | |
| 142 | |
| 143 We have already verified that COPY intersects at least one | |
| 144 byte with REF. */ | |
| 0 | 145 |
| 146 static void | |
| 111 | 147 normalize_ref (ao_ref *copy, ao_ref *ref) |
| 0 | 148 { |
| 111 | 149 /* If COPY starts before REF, then reset the beginning of |
| 150 COPY to match REF and decrease the size of COPY by the | |
| 151 number of bytes removed from COPY. */ | |
| 152 if (copy->offset < ref->offset) | |
| 153 { | |
| 154 copy->size -= (ref->offset - copy->offset); | |
| 155 copy->offset = ref->offset; | |
| 156 } | |
| 157 | |
| 158 /* If COPY extends beyond REF, chop off its size appropriately. */ | |
| 159 if (copy->offset + copy->size > ref->offset + ref->size) | |
| 160 copy->size -= (copy->offset + copy->size - (ref->offset + ref->size)); | |
| 161 } | |
| 162 | |
| 163 /* 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 | |
| 165 have its base address previously initialized. | |
| 166 | |
| 167 This routine must be conservative. If we don't know the offset or | |
| 168 actual size written, assume nothing was written. */ | |
| 0 | 169 |
| 111 | 170 static void |
| 171 clear_bytes_written_by (sbitmap live_bytes, gimple *stmt, ao_ref *ref) | |
| 172 { | |
| 173 ao_ref write; | |
| 174 if (!initialize_ao_ref_for_dse (stmt, &write)) | |
| 175 return; | |
| 176 | |
| 177 /* Verify we have the same base memory address, the write | |
| 178 has a known size and overlaps with REF. */ | |
| 179 if (valid_ao_ref_for_dse (&write) | |
| 180 && operand_equal_p (write.base, ref->base, OEP_ADDRESS_OF) | |
| 181 && write.size == write.max_size | |
| 182 && ((write.offset < ref->offset | |
| 183 && write.offset + write.size > ref->offset) | |
| 184 || (write.offset >= ref->offset | |
| 185 && write.offset < ref->offset + ref->size))) | |
| 186 { | |
| 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 } | |
| 0 | 192 } |
| 193 | |
| 111 | 194 /* REF is a memory write. Extract relevant information from it and |
| 195 initialize the LIVE_BYTES bitmap. If successful, return TRUE. | |
| 196 Otherwise return FALSE. */ | |
| 197 | |
| 198 static bool | |
| 199 setup_live_bytes_from_ref (ao_ref *ref, sbitmap live_bytes) | |
| 200 { | |
| 201 if (valid_ao_ref_for_dse (ref) | |
| 202 && (ref->size / BITS_PER_UNIT | |
| 203 <= PARAM_VALUE (PARAM_DSE_MAX_OBJECT_SIZE))) | |
| 204 { | |
| 205 bitmap_clear (live_bytes); | |
| 206 bitmap_set_range (live_bytes, 0, ref->size / BITS_PER_UNIT); | |
| 207 return true; | |
| 208 } | |
| 209 return false; | |
| 210 } | |
| 211 | |
| 212 /* Compute the number of elements that we can trim from the head and | |
| 213 tail of ORIG resulting in a bitmap that is a superset of LIVE. | |
| 214 | |
| 215 Store the number of elements trimmed from the head and tail in | |
| 216 TRIM_HEAD and TRIM_TAIL. | |
| 217 | |
| 218 STMT is the statement being trimmed and is used for debugging dump | |
| 219 output only. */ | |
| 0 | 220 |
| 221 static void | |
| 111 | 222 compute_trims (ao_ref *ref, sbitmap live, int *trim_head, int *trim_tail, |
| 223 gimple *stmt) | |
| 0 | 224 { |
| 111 | 225 /* We use sbitmaps biased such that ref->offset is bit zero and the bitmap |
| 226 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 | |
| 228 the REF to compute the trims. */ | |
| 229 | |
| 230 /* Now identify how much, if any of the tail we can chop off. */ | |
| 231 int last_orig = (ref->size / BITS_PER_UNIT) - 1; | |
| 232 int last_live = bitmap_last_set_bit (live); | |
| 233 *trim_tail = (last_orig - last_live) & ~0x1; | |
| 0 | 234 |
| 111 | 235 /* Identify how much, if any of the head we can chop off. */ |
| 236 int first_orig = 0; | |
| 237 int first_live = bitmap_first_set_bit (live); | |
| 238 *trim_head = (first_live - first_orig) & ~0x1; | |
| 239 | |
| 240 if ((*trim_head || *trim_tail) | |
| 241 && dump_file && (dump_flags & TDF_DETAILS)) | |
| 0 | 242 { |
| 111 | 243 fprintf (dump_file, " Trimming statement (head = %d, tail = %d): ", |
| 244 *trim_head, *trim_tail); | |
| 245 print_gimple_stmt (dump_file, stmt, 0, dump_flags); | |
| 246 fprintf (dump_file, "\n"); | |
| 0 | 247 } |
| 248 } | |
| 249 | |
| 111 | 250 /* STMT initializes an object from COMPLEX_CST where one or more of the |
| 251 bytes written may be dead stores. REF is a representation of the | |
| 252 memory written. LIVE is the bitmap of stores that are actually live. | |
| 253 | |
| 254 Attempt to rewrite STMT so that only the real or imaginary part of | |
| 255 the object is actually stored. */ | |
| 256 | |
| 257 static void | |
| 258 maybe_trim_complex_store (ao_ref *ref, sbitmap live, gimple *stmt) | |
| 259 { | |
| 260 int trim_head, trim_tail; | |
| 261 compute_trims (ref, live, &trim_head, &trim_tail, stmt); | |
| 262 | |
| 263 /* 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 | |
| 265 the entire real or imaginary half. By writing things this | |
| 266 way we avoid more O(n) bitmap operations. */ | |
| 267 if (trim_tail * 2 >= ref->size / BITS_PER_UNIT) | |
| 268 { | |
| 269 /* TREE_REALPART is live */ | |
| 270 tree x = TREE_REALPART (gimple_assign_rhs1 (stmt)); | |
| 271 tree y = gimple_assign_lhs (stmt); | |
| 272 y = build1 (REALPART_EXPR, TREE_TYPE (x), y); | |
| 273 gimple_assign_set_lhs (stmt, y); | |
| 274 gimple_assign_set_rhs1 (stmt, x); | |
| 275 } | |
| 276 else if (trim_head * 2 >= ref->size / BITS_PER_UNIT) | |
| 277 { | |
| 278 /* TREE_IMAGPART is live */ | |
| 279 tree x = TREE_IMAGPART (gimple_assign_rhs1 (stmt)); | |
| 280 tree y = gimple_assign_lhs (stmt); | |
| 281 y = build1 (IMAGPART_EXPR, TREE_TYPE (x), y); | |
| 282 gimple_assign_set_lhs (stmt, y); | |
| 283 gimple_assign_set_rhs1 (stmt, x); | |
| 284 } | |
| 285 | |
| 286 /* Other cases indicate parts of both the real and imag subobjects | |
| 287 are live. We do not try to optimize those cases. */ | |
| 288 } | |
| 289 | |
| 290 /* STMT initializes an object using a CONSTRUCTOR where one or more of the | |
| 291 bytes written are dead stores. ORIG is the bitmap of bytes stored by | |
| 292 STMT. LIVE is the bitmap of stores that are actually live. | |
| 293 | |
| 294 Attempt to rewrite STMT so that only the real or imaginary part of | |
| 295 the object is actually stored. | |
| 296 | |
| 297 The most common case for getting here is a CONSTRUCTOR with no elements | |
| 298 being used to zero initialize an object. We do not try to handle other | |
| 299 cases as those would force us to fully cover the object with the | |
| 300 CONSTRUCTOR node except for the components that are dead. */ | |
| 301 | |
| 302 static void | |
| 303 maybe_trim_constructor_store (ao_ref *ref, sbitmap live, gimple *stmt) | |
| 304 { | |
| 305 tree ctor = gimple_assign_rhs1 (stmt); | |
| 306 | |
| 307 /* This is the only case we currently handle. It actually seems to | |
| 308 catch most cases of actual interest. */ | |
| 309 gcc_assert (CONSTRUCTOR_NELTS (ctor) == 0); | |
| 310 | |
| 311 int head_trim = 0; | |
| 312 int tail_trim = 0; | |
| 313 compute_trims (ref, live, &head_trim, &tail_trim, stmt); | |
| 314 | |
| 315 /* Now we want to replace the constructor initializer | |
| 316 with memset (object + head_trim, 0, size - head_trim - tail_trim). */ | |
| 317 if (head_trim || tail_trim) | |
| 318 { | |
| 319 /* We want &lhs for the MEM_REF expression. */ | |
| 320 tree lhs_addr = build_fold_addr_expr (gimple_assign_lhs (stmt)); | |
| 321 | |
| 322 if (! is_gimple_min_invariant (lhs_addr)) | |
| 323 return; | |
| 324 | |
| 325 /* The number of bytes for the new constructor. */ | |
| 326 int count = (ref->size / BITS_PER_UNIT) - head_trim - tail_trim; | |
| 327 | |
| 328 /* And the new type for the CONSTRUCTOR. Essentially it's just | |
| 329 a char array large enough to cover the non-trimmed parts of | |
| 330 the original CONSTRUCTOR. Note we want explicit bounds here | |
| 331 so that we know how many bytes to clear when expanding the | |
| 332 CONSTRUCTOR. */ | |
| 333 tree type = build_array_type_nelts (char_type_node, count); | |
| 334 | |
| 335 /* Build a suitable alias type rather than using alias set zero | |
| 336 to avoid pessimizing. */ | |
| 337 tree alias_type = reference_alias_ptr_type (gimple_assign_lhs (stmt)); | |
| 338 | |
| 339 /* Build a MEM_REF representing the whole accessed area, starting | |
| 340 at the first byte not trimmed. */ | |
| 341 tree exp = fold_build2 (MEM_REF, type, lhs_addr, | |
| 342 build_int_cst (alias_type, head_trim)); | |
| 343 | |
| 344 /* Now update STMT with a new RHS and LHS. */ | |
| 345 gimple_assign_set_lhs (stmt, exp); | |
| 346 gimple_assign_set_rhs1 (stmt, build_constructor (type, NULL)); | |
| 347 } | |
| 348 } | |
| 349 | |
| 350 /* STMT is a memcpy, memmove or memset. Decrement the number of bytes | |
| 351 copied/set by DECREMENT. */ | |
| 352 static void | |
| 353 decrement_count (gimple *stmt, int decrement) | |
| 354 { | |
| 355 tree *countp = gimple_call_arg_ptr (stmt, 2); | |
| 356 gcc_assert (TREE_CODE (*countp) == INTEGER_CST); | |
| 357 *countp = wide_int_to_tree (TREE_TYPE (*countp), (TREE_INT_CST_LOW (*countp) | |
| 358 - decrement)); | |
| 359 | |
| 360 } | |
| 361 | |
| 362 static void | |
| 363 increment_start_addr (gimple *stmt, tree *where, int increment) | |
| 364 { | |
| 365 if (TREE_CODE (*where) == SSA_NAME) | |
| 366 { | |
| 367 tree tem = make_ssa_name (TREE_TYPE (*where)); | |
| 368 gassign *newop | |
| 369 = gimple_build_assign (tem, POINTER_PLUS_EXPR, *where, | |
| 370 build_int_cst (sizetype, increment)); | |
| 371 gimple_stmt_iterator gsi = gsi_for_stmt (stmt); | |
| 372 gsi_insert_before (&gsi, newop, GSI_SAME_STMT); | |
| 373 *where = tem; | |
| 374 update_stmt (gsi_stmt (gsi)); | |
| 375 return; | |
| 376 } | |
| 377 | |
| 378 *where = build_fold_addr_expr (fold_build2 (MEM_REF, char_type_node, | |
| 379 *where, | |
| 380 build_int_cst (ptr_type_node, | |
| 381 increment))); | |
| 382 } | |
| 383 | |
| 384 /* STMT is builtin call that writes bytes in bitmap ORIG, some bytes are dead | |
| 385 (ORIG & ~NEW) and need not be stored. Try to rewrite STMT to reduce | |
| 386 the amount of data it actually writes. | |
| 387 | |
| 388 Right now we only support trimming from the head or the tail of the | |
| 389 memory region. In theory we could split the mem* call, but it's | |
| 390 likely of marginal value. */ | |
| 391 | |
| 392 static void | |
| 393 maybe_trim_memstar_call (ao_ref *ref, sbitmap live, gimple *stmt) | |
| 394 { | |
| 395 switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt))) | |
| 396 { | |
| 397 case BUILT_IN_MEMCPY: | |
| 398 case BUILT_IN_MEMMOVE: | |
| 399 { | |
| 400 int head_trim, tail_trim; | |
| 401 compute_trims (ref, live, &head_trim, &tail_trim, stmt); | |
| 402 | |
| 403 /* Tail trimming is easy, we can just reduce the count. */ | |
| 404 if (tail_trim) | |
| 405 decrement_count (stmt, tail_trim); | |
| 406 | |
| 407 /* Head trimming requires adjusting all the arguments. */ | |
| 408 if (head_trim) | |
| 409 { | |
| 410 tree *dst = gimple_call_arg_ptr (stmt, 0); | |
| 411 increment_start_addr (stmt, dst, head_trim); | |
| 412 tree *src = gimple_call_arg_ptr (stmt, 1); | |
| 413 increment_start_addr (stmt, src, head_trim); | |
| 414 decrement_count (stmt, head_trim); | |
| 415 } | |
| 416 break; | |
| 417 } | |
| 418 | |
| 419 case BUILT_IN_MEMSET: | |
| 420 { | |
| 421 int head_trim, tail_trim; | |
| 422 compute_trims (ref, live, &head_trim, &tail_trim, stmt); | |
| 423 | |
| 424 /* Tail trimming is easy, we can just reduce the count. */ | |
| 425 if (tail_trim) | |
| 426 decrement_count (stmt, tail_trim); | |
| 427 | |
| 428 /* Head trimming requires adjusting all the arguments. */ | |
| 429 if (head_trim) | |
| 430 { | |
| 431 tree *dst = gimple_call_arg_ptr (stmt, 0); | |
| 432 increment_start_addr (stmt, dst, head_trim); | |
| 433 decrement_count (stmt, head_trim); | |
| 434 } | |
| 435 break; | |
| 436 } | |
| 437 | |
| 438 default: | |
| 439 break; | |
| 440 } | |
| 441 } | |
| 442 | |
| 443 /* STMT is a memory write where one or more bytes written are dead | |
| 444 stores. ORIG is the bitmap of bytes stored by STMT. LIVE is the | |
| 445 bitmap of stores that are actually live. | |
| 446 | |
| 447 Attempt to rewrite STMT so that it writes fewer memory locations. Right | |
| 448 now we only support trimming at the start or end of the memory region. | |
| 449 It's not clear how much there is to be gained by trimming from the middle | |
| 450 of the region. */ | |
| 451 | |
| 452 static void | |
| 453 maybe_trim_partially_dead_store (ao_ref *ref, sbitmap live, gimple *stmt) | |
| 454 { | |
| 455 if (is_gimple_assign (stmt) | |
| 456 && TREE_CODE (gimple_assign_lhs (stmt)) != TARGET_MEM_REF) | |
| 457 { | |
| 458 switch (gimple_assign_rhs_code (stmt)) | |
| 459 { | |
| 460 case CONSTRUCTOR: | |
| 461 maybe_trim_constructor_store (ref, live, stmt); | |
| 462 break; | |
| 463 case COMPLEX_CST: | |
| 464 maybe_trim_complex_store (ref, live, stmt); | |
| 465 break; | |
| 466 default: | |
| 467 break; | |
| 468 } | |
| 469 } | |
| 470 } | |
| 471 | |
| 472 /* Return TRUE if USE_REF reads bytes from LIVE where live is | |
| 473 derived from REF, a write reference. | |
| 474 | |
| 475 While this routine may modify USE_REF, it's passed by value, not | |
| 476 location. So callers do not see those modifications. */ | |
| 477 | |
| 478 static bool | |
| 479 live_bytes_read (ao_ref use_ref, ao_ref *ref, sbitmap live) | |
| 480 { | |
| 481 /* 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. */ | |
| 483 if (ranges_overlap_p (use_ref.offset, use_ref.size, ref->offset, ref->size)) | |
| 484 { | |
| 485 normalize_ref (&use_ref, ref); | |
| 486 | |
| 487 /* If USE_REF covers all of REF, then it will hit one or more | |
| 488 live bytes. This avoids useless iteration over the bitmap | |
| 489 below. */ | |
| 490 if (use_ref.offset <= ref->offset | |
| 491 && use_ref.offset + use_ref.size >= ref->offset + ref->size) | |
| 492 return true; | |
| 493 | |
| 494 /* 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; | |
| 496 unsigned int end = start + (use_ref.size / BITS_PER_UNIT) - 1; | |
| 497 return bitmap_bit_in_range_p (live, start, end); | |
| 498 } | |
| 499 return true; | |
| 500 } | |
| 501 | |
| 0 | 502 /* A helper of dse_optimize_stmt. |
| 111 | 503 Given a GIMPLE_ASSIGN in STMT that writes to REF, find a candidate |
| 504 statement *USE_STMT that may prove STMT to be dead. | |
| 0 | 505 Return TRUE if the above conditions are met, otherwise FALSE. */ |
| 506 | |
| 111 | 507 static dse_store_status |
| 508 dse_classify_store (ao_ref *ref, gimple *stmt, gimple **use_stmt, | |
| 509 bool byte_tracking_enabled, sbitmap live_bytes) | |
| 0 | 510 { |
| 111 | 511 gimple *temp; |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
512 unsigned cnt = 0; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
513 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
514 *use_stmt = NULL; |
| 0 | 515 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
516 /* 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
|
517 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
|
518 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
|
519 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
|
520 temp = stmt; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
521 do |
| 0 | 522 { |
| 111 | 523 gimple *use_stmt, *defvar_def; |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
524 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
|
525 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
|
526 tree defvar; |
| 0 | 527 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
528 /* Limit stmt walking to be linear in the number of possibly |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
529 dead stores. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
530 if (++cnt > 256) |
| 111 | 531 return DSE_STORE_LIVE; |
| 0 | 532 |
| 533 if (gimple_code (temp) == 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
|
534 defvar = PHI_RESULT (temp); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
535 else |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
536 defvar = gimple_vdef (temp); |
| 111 | 537 defvar_def = temp; |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
538 temp = NULL; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
539 FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar) |
| 0 | 540 { |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
541 cnt++; |
| 0 | 542 |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
543 /* If we ever reach our DSE candidate stmt again fail. We |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
544 cannot handle dead stores in loops. */ |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
545 if (use_stmt == stmt) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
546 { |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
547 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
|
548 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
|
549 } |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
550 /* 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
|
551 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
|
552 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
|
553 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
|
554 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
|
555 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
556 if (temp |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
557 /* Make sure we are not in a loop latch block. */ |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
558 || gimple_bb (stmt) == gimple_bb (use_stmt) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
559 || dominated_by_p (CDI_DOMINATORS, |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
560 gimple_bb (stmt), gimple_bb (use_stmt)) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
561 /* We can look through PHIs to regions post-dominating |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
562 the DSE candidate stmt. */ |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
563 || !dominated_by_p (CDI_POST_DOMINATORS, |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
564 gimple_bb (stmt), gimple_bb (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
|
565 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
566 fail = true; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
567 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
|
568 } |
| 111 | 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; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
577 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
578 /* If the statement is a use the store is not dead. */ |
| 111 | 579 else if (ref_maybe_used_by_stmt_p (use_stmt, ref)) |
| 0 | 580 { |
| 111 | 581 /* Handle common cases where we can easily build an ao_ref |
| 582 structure for USE_STMT and in doing so we find that the | |
| 583 references hit non-live bytes and thus can be ignored. */ | |
| 584 if (byte_tracking_enabled && (!gimple_vdef (use_stmt) || !temp)) | |
| 585 { | |
| 586 if (is_gimple_assign (use_stmt)) | |
| 587 { | |
| 588 /* Other cases were noted as non-aliasing by | |
| 589 the call to ref_maybe_used_by_stmt_p. */ | |
| 590 ao_ref use_ref; | |
| 591 ao_ref_init (&use_ref, gimple_assign_rhs1 (use_stmt)); | |
| 592 if (valid_ao_ref_for_dse (&use_ref) | |
| 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 } | |
| 604 } | |
| 605 | |
| 0 | 606 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
|
607 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
|
608 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
609 /* If this is a store, remember it or bail out if we have |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
610 multiple ones (the will be in different CFG parts then). */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
611 else if (gimple_vdef (use_stmt)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
612 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
613 if (temp) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
614 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
615 fail = true; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
616 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
|
617 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
618 temp = use_stmt; |
| 0 | 619 } |
| 620 } | |
| 621 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
622 if (fail) |
| 111 | 623 { |
| 624 /* STMT might be partially dead and we may be able to reduce | |
| 625 how many memory locations it stores into. */ | |
| 626 if (byte_tracking_enabled && !gimple_clobber_p (stmt)) | |
| 627 return DSE_STORE_MAYBE_PARTIAL_DEAD; | |
| 628 return DSE_STORE_LIVE; | |
| 629 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
630 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
631 /* 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
|
632 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
|
633 just pretend the stmt makes itself dead. Otherwise fail. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
634 if (!temp) |
| 0 | 635 { |
| 111 | 636 if (ref_may_alias_global_p (ref)) |
| 637 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
|
638 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
639 temp = stmt; |
| 0 | 640 break; |
| 641 } | |
| 111 | 642 |
| 643 if (byte_tracking_enabled && temp) | |
| 644 clear_bytes_written_by (live_bytes, temp, ref); | |
| 0 | 645 } |
| 111 | 646 /* Continue walking until we reach a full kill as a single statement |
| 647 or there are no more live bytes. */ | |
| 648 while (!stmt_kills_ref_p (temp, ref) | |
| 649 && !(byte_tracking_enabled && bitmap_empty_p (live_bytes))); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
650 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
651 *use_stmt = temp; |
| 111 | 652 return DSE_STORE_DEAD; |
| 0 | 653 } |
| 654 | |
| 655 | |
| 111 | 656 class dse_dom_walker : public dom_walker |
| 657 { | |
| 658 public: | |
| 659 dse_dom_walker (cdi_direction direction) | |
| 660 : dom_walker (direction), | |
| 661 m_live_bytes (PARAM_VALUE (PARAM_DSE_MAX_OBJECT_SIZE)), | |
| 662 m_byte_tracking_enabled (false) {} | |
| 663 | |
| 664 virtual edge before_dom_children (basic_block); | |
| 665 | |
| 666 private: | |
| 667 auto_sbitmap m_live_bytes; | |
| 668 bool m_byte_tracking_enabled; | |
| 669 void dse_optimize_stmt (gimple_stmt_iterator *); | |
| 670 }; | |
| 671 | |
| 672 /* Delete a dead call at GSI, which is mem* call of some kind. */ | |
| 673 static void | |
| 674 delete_dead_call (gimple_stmt_iterator *gsi) | |
| 675 { | |
| 676 gimple *stmt = gsi_stmt (*gsi); | |
| 677 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 678 { | |
| 679 fprintf (dump_file, " Deleted dead call: "); | |
| 680 print_gimple_stmt (dump_file, stmt, 0, dump_flags); | |
| 681 fprintf (dump_file, "\n"); | |
| 682 } | |
| 683 | |
| 684 tree lhs = gimple_call_lhs (stmt); | |
| 685 if (lhs) | |
| 686 { | |
| 687 tree ptr = gimple_call_arg (stmt, 0); | |
| 688 gimple *new_stmt = gimple_build_assign (lhs, ptr); | |
| 689 unlink_stmt_vdef (stmt); | |
| 690 if (gsi_replace (gsi, new_stmt, true)) | |
| 691 bitmap_set_bit (need_eh_cleanup, gimple_bb (stmt)->index); | |
| 692 } | |
| 693 else | |
| 694 { | |
| 695 /* Then we need to fix the operand of the consuming stmt. */ | |
| 696 unlink_stmt_vdef (stmt); | |
| 697 | |
| 698 /* Remove the dead store. */ | |
| 699 if (gsi_remove (gsi, true)) | |
| 700 bitmap_set_bit (need_eh_cleanup, gimple_bb (stmt)->index); | |
| 701 release_defs (stmt); | |
| 702 } | |
| 703 } | |
| 704 | |
| 705 /* Delete a dead store at GSI, which is a gimple assignment. */ | |
| 706 | |
| 707 static void | |
| 708 delete_dead_assignment (gimple_stmt_iterator *gsi) | |
| 709 { | |
| 710 gimple *stmt = gsi_stmt (*gsi); | |
| 711 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 712 { | |
| 713 fprintf (dump_file, " Deleted dead store: "); | |
| 714 print_gimple_stmt (dump_file, stmt, 0, dump_flags); | |
| 715 fprintf (dump_file, "\n"); | |
| 716 } | |
| 717 | |
| 718 /* Then we need to fix the operand of the consuming stmt. */ | |
| 719 unlink_stmt_vdef (stmt); | |
| 720 | |
| 721 /* Remove the dead store. */ | |
| 722 basic_block bb = gimple_bb (stmt); | |
| 723 if (gsi_remove (gsi, true)) | |
| 724 bitmap_set_bit (need_eh_cleanup, bb->index); | |
| 725 | |
| 726 /* And release any SSA_NAMEs set in this statement back to the | |
| 727 SSA_NAME manager. */ | |
| 728 release_defs (stmt); | |
| 729 } | |
| 730 | |
| 0 | 731 /* Attempt to eliminate dead stores in the statement referenced by BSI. |
| 732 | |
| 733 A dead store is a store into a memory location which will later be | |
| 734 overwritten by another store without any intervening loads. In this | |
| 735 case the earlier store can be deleted. | |
| 736 | |
| 737 In our SSA + virtual operand world we use immediate uses of virtual | |
| 738 operands to detect dead stores. If a store's virtual definition | |
| 739 is used precisely once by a later store to the same location which | |
| 740 post dominates the first store, then the first store is dead. */ | |
| 741 | |
| 111 | 742 void |
| 743 dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi) | |
| 0 | 744 { |
| 111 | 745 gimple *stmt = gsi_stmt (*gsi); |
| 0 | 746 |
| 747 /* If this statement has no virtual defs, then there is nothing | |
| 748 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
|
749 if (!gimple_vdef (stmt)) |
| 0 | 750 return; |
| 751 | |
| 111 | 752 /* Don't return early on *this_2(D) ={v} {CLOBBER}. */ |
| 753 if (gimple_has_volatile_ops (stmt) | |
| 754 && (!gimple_clobber_p (stmt) | |
| 755 || TREE_CODE (gimple_assign_lhs (stmt)) != MEM_REF)) | |
| 756 return; | |
| 757 | |
| 758 ao_ref ref; | |
| 759 if (!initialize_ao_ref_for_dse (stmt, &ref)) | |
| 0 | 760 return; |
| 761 | |
| 111 | 762 /* We know we have virtual definitions. We can handle assignments and |
| 763 some builtin calls. */ | |
| 764 if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)) | |
| 765 { | |
| 766 switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt))) | |
| 767 { | |
| 768 case BUILT_IN_MEMCPY: | |
| 769 case BUILT_IN_MEMMOVE: | |
| 770 case BUILT_IN_MEMSET: | |
| 771 { | |
| 772 /* Occasionally calls with an explicit length of zero | |
| 773 show up in the IL. It's pointless to do analysis | |
| 774 on them, they're trivially dead. */ | |
| 775 tree size = gimple_call_arg (stmt, 2); | |
| 776 if (integer_zerop (size)) | |
| 777 { | |
| 778 delete_dead_call (gsi); | |
| 779 return; | |
| 780 } | |
| 781 | |
| 782 gimple *use_stmt; | |
| 783 enum dse_store_status store_status; | |
| 784 m_byte_tracking_enabled | |
| 785 = setup_live_bytes_from_ref (&ref, m_live_bytes); | |
| 786 store_status = dse_classify_store (&ref, stmt, &use_stmt, | |
| 787 m_byte_tracking_enabled, | |
| 788 m_live_bytes); | |
| 789 if (store_status == DSE_STORE_LIVE) | |
| 790 return; | |
| 791 | |
| 792 if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD) | |
| 793 { | |
| 794 maybe_trim_memstar_call (&ref, m_live_bytes, stmt); | |
| 795 return; | |
| 796 } | |
| 797 | |
| 798 if (store_status == DSE_STORE_DEAD) | |
| 799 delete_dead_call (gsi); | |
| 800 return; | |
| 801 } | |
| 802 | |
| 803 default: | |
| 804 return; | |
| 805 } | |
| 806 } | |
| 0 | 807 |
| 808 if (is_gimple_assign (stmt)) | |
| 809 { | |
| 111 | 810 gimple *use_stmt; |
| 0 | 811 |
| 111 | 812 /* Self-assignments are zombies. */ |
| 813 if (operand_equal_p (gimple_assign_rhs1 (stmt), | |
| 814 gimple_assign_lhs (stmt), 0)) | |
| 815 use_stmt = stmt; | |
| 816 else | |
| 817 { | |
| 818 m_byte_tracking_enabled | |
| 819 = setup_live_bytes_from_ref (&ref, m_live_bytes); | |
| 820 enum dse_store_status store_status; | |
| 821 store_status = dse_classify_store (&ref, stmt, &use_stmt, | |
| 822 m_byte_tracking_enabled, | |
| 823 m_live_bytes); | |
| 824 if (store_status == DSE_STORE_LIVE) | |
| 825 return; | |
| 0 | 826 |
| 111 | 827 if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD) |
| 828 { | |
| 829 maybe_trim_partially_dead_store (&ref, m_live_bytes, stmt); | |
| 830 return; | |
| 831 } | |
| 832 } | |
| 833 | |
| 834 /* Now we know that use_stmt kills the LHS of stmt. */ | |
| 835 | |
| 836 /* But only remove *this_2(D) ={v} {CLOBBER} if killed by | |
| 837 another clobber stmt. */ | |
| 838 if (gimple_clobber_p (stmt) | |
| 839 && !gimple_clobber_p (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
|
840 return; |
| 0 | 841 |
| 111 | 842 delete_dead_assignment (gsi); |
| 0 | 843 } |
| 844 } | |
| 845 | |
| 111 | 846 edge |
| 847 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
|
848 { |
| 0 | 849 gimple_stmt_iterator gsi; |
| 850 | |
| 111 | 851 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);) |
| 852 { | |
| 853 dse_optimize_stmt (&gsi); | |
| 854 if (gsi_end_p (gsi)) | |
| 855 gsi = gsi_last_bb (bb); | |
| 856 else | |
| 857 gsi_prev (&gsi); | |
| 858 } | |
| 859 return NULL; | |
| 0 | 860 } |
| 861 | |
| 111 | 862 namespace { |
| 863 | |
| 864 const pass_data pass_data_dse = | |
| 0 | 865 { |
| 111 | 866 GIMPLE_PASS, /* type */ |
| 867 "dse", /* name */ | |
| 868 OPTGROUP_NONE, /* optinfo_flags */ | |
| 869 TV_TREE_DSE, /* tv_id */ | |
| 870 ( PROP_cfg | PROP_ssa ), /* properties_required */ | |
| 871 0, /* properties_provided */ | |
| 872 0, /* properties_destroyed */ | |
| 873 0, /* todo_flags_start */ | |
| 874 0, /* todo_flags_finish */ | |
| 875 }; | |
| 0 | 876 |
| 111 | 877 class pass_dse : public gimple_opt_pass |
| 878 { | |
| 879 public: | |
| 880 pass_dse (gcc::context *ctxt) | |
| 881 : gimple_opt_pass (pass_data_dse, ctxt) | |
| 882 {} | |
| 0 | 883 |
| 111 | 884 /* opt_pass methods: */ |
| 885 opt_pass * clone () { return new pass_dse (m_ctxt); } | |
| 886 virtual bool gate (function *) { return flag_tree_dse != 0; } | |
| 887 virtual unsigned int execute (function *); | |
| 0 | 888 |
| 111 | 889 }; // class pass_dse |
| 890 | |
| 891 unsigned int | |
| 892 pass_dse::execute (function *fun) | |
| 0 | 893 { |
|
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
|
894 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
|
895 |
| 0 | 896 renumber_gimple_stmt_uids (); |
| 897 | |
| 898 /* We might consider making this a property of each pass so that it | |
| 899 can be [re]computed on an as-needed basis. Particularly since | |
| 900 this pass could be seen as an extension of DCE which needs post | |
| 901 dominators. */ | |
| 902 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
|
903 calculate_dominance_info (CDI_DOMINATORS); |
| 0 | 904 |
| 905 /* Dead store elimination is fundamentally a walk of the post-dominator | |
| 906 tree and a backwards walk of statements within each block. */ | |
| 111 | 907 dse_dom_walker (CDI_POST_DOMINATORS).walk (fun->cfg->x_exit_block_ptr); |
| 0 | 908 |
|
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
|
909 /* 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
|
910 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
|
911 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
|
912 { |
|
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
|
913 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
|
914 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
|
915 } |
|
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
|
916 |
|
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
|
917 BITMAP_FREE (need_eh_cleanup); |
| 111 | 918 |
| 0 | 919 /* For now, just wipe the post-dominator information. */ |
| 920 free_dominance_info (CDI_POST_DOMINATORS); | |
| 921 return 0; | |
| 922 } | |
| 923 | |
| 111 | 924 } // anon namespace |
| 0 | 925 |
| 111 | 926 gimple_opt_pass * |
| 927 make_pass_dse (gcc::context *ctxt) | |
| 0 | 928 { |
| 111 | 929 return new pass_dse (ctxt); |
| 930 } |