Mercurial > hg > CbC > CbC_gcc
annotate gcc/tree-ssa-dse.c @ 158:494b0b89df80 default tip
...
| author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Mon, 25 May 2020 18:13:55 +0900 |
| parents | 1830386684a0 |
| children |
| rev | line source |
|---|---|
| 145 | 1 /* Dead and redundant store elimination |
| 2 Copyright (C) 2004-2020 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 "alias.h" | |
| 131 | 37 #include "tree-ssa-loop.h" |
| 145 | 38 #include "tree-ssa-dse.h" |
| 39 #include "builtins.h" | |
| 40 #include "gimple-fold.h" | |
| 0 | 41 |
| 42 /* This file implements dead store elimination. | |
| 43 | |
| 44 A dead store is a store into a memory location which will later be | |
| 45 overwritten by another store without any intervening loads. In this | |
| 145 | 46 case the earlier store can be deleted or trimmed if the store |
| 47 was partially dead. | |
| 48 | |
| 49 A redundant store is a store into a memory location which stores | |
| 50 the exact same value as a prior store to the same memory location. | |
| 51 While this can often be handled by dead store elimination, removing | |
| 52 the redundant store is often better than removing or trimming the | |
| 53 dead store. | |
| 0 | 54 |
| 55 In our SSA + virtual operand world we use immediate uses of virtual | |
| 145 | 56 operands to detect these cases. If a store's virtual definition |
| 0 | 57 is used precisely once by a later store to the same location which |
| 145 | 58 post dominates the first store, then the first store is dead. If |
| 59 the data stored is the same, then the second store is redundant. | |
| 0 | 60 |
| 61 The single use of the store's virtual definition ensures that | |
| 62 there are no intervening aliased loads and the requirement that | |
| 63 the second load post dominate the first ensures that if the earlier | |
| 64 store executes, then the later stores will execute before the function | |
| 65 exits. | |
| 66 | |
| 67 It may help to think of this as first moving the earlier store to | |
| 68 the point immediately before the later store. Again, the single | |
| 69 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
|
70 ensure that such movement would be safe. Clearly if there are |
| 145 | 71 back to back stores, then the second is makes the first dead. If |
| 72 the second store stores the same value, then the second store is | |
| 73 redundant. | |
| 0 | 74 |
| 75 Reviewing section 10.7.2 in Morgan's "Building an Optimizing Compiler" | |
| 76 may also help in understanding this code since it discusses the | |
| 77 relationship between dead store and redundant load elimination. In | |
| 78 fact, they are the same transformation applied to different views of | |
| 79 the CFG. */ | |
| 80 | |
| 145 | 81 static void delete_dead_or_redundant_call (gimple_stmt_iterator *, const char *); |
| 0 | 82 |
|
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
|
83 /* 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
|
84 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
|
85 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
|
86 |
| 111 | 87 /* STMT is a statement that may write into memory. Analyze it and |
| 88 initialize WRITE to describe how STMT affects memory. | |
| 89 | |
| 90 Return TRUE if the the statement was analyzed, FALSE otherwise. | |
| 91 | |
| 92 It is always safe to return FALSE. But typically better optimziation | |
| 93 can be achieved by analyzing more statements. */ | |
| 0 | 94 |
| 111 | 95 static bool |
| 96 initialize_ao_ref_for_dse (gimple *stmt, ao_ref *write) | |
| 0 | 97 { |
| 111 | 98 /* It's advantageous to handle certain mem* functions. */ |
| 99 if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)) | |
| 100 { | |
| 101 switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt))) | |
| 102 { | |
| 145 | 103 case BUILT_IN_MEMCPY: |
| 104 case BUILT_IN_MEMMOVE: | |
| 105 case BUILT_IN_MEMSET: | |
| 106 case BUILT_IN_MEMCPY_CHK: | |
| 107 case BUILT_IN_MEMMOVE_CHK: | |
| 108 case BUILT_IN_MEMSET_CHK: | |
| 109 case BUILT_IN_STRNCPY: | |
| 110 case BUILT_IN_STRNCPY_CHK: | |
| 111 { | |
| 112 tree size = gimple_call_arg (stmt, 2); | |
| 113 tree ptr = gimple_call_arg (stmt, 0); | |
| 114 ao_ref_init_from_ptr_and_size (write, ptr, size); | |
| 115 return true; | |
| 116 } | |
| 117 | |
| 118 /* A calloc call can never be dead, but it can make | |
| 119 subsequent stores redundant if they store 0 into | |
| 120 the same memory locations. */ | |
| 121 case BUILT_IN_CALLOC: | |
| 122 { | |
| 123 tree nelem = gimple_call_arg (stmt, 0); | |
| 124 tree selem = gimple_call_arg (stmt, 1); | |
| 125 tree lhs; | |
| 126 if (TREE_CODE (nelem) == INTEGER_CST | |
| 127 && TREE_CODE (selem) == INTEGER_CST | |
| 128 && (lhs = gimple_call_lhs (stmt)) != NULL_TREE) | |
| 129 { | |
| 130 tree size = fold_build2 (MULT_EXPR, TREE_TYPE (nelem), | |
| 131 nelem, selem); | |
| 132 ao_ref_init_from_ptr_and_size (write, lhs, size); | |
| 133 return true; | |
| 134 } | |
| 135 } | |
| 136 | |
| 137 default: | |
| 138 break; | |
| 111 | 139 } |
| 140 } | |
| 141 else if (is_gimple_assign (stmt)) | |
| 142 { | |
| 143 ao_ref_init (write, gimple_assign_lhs (stmt)); | |
| 144 return true; | |
| 145 } | |
| 146 return false; | |
| 0 | 147 } |
| 148 | |
| 111 | 149 /* Given REF from the the alias oracle, return TRUE if it is a valid |
| 150 memory reference for dead store elimination, false otherwise. | |
| 151 | |
| 152 In particular, the reference must have a known base, known maximum | |
| 153 size, start at a byte offset and have a size that is one or more | |
| 154 bytes. */ | |
| 155 | |
| 156 static bool | |
| 157 valid_ao_ref_for_dse (ao_ref *ref) | |
| 158 { | |
| 159 return (ao_ref_base (ref) | |
| 131 | 160 && known_size_p (ref->max_size) |
| 161 && maybe_ne (ref->size, 0) | |
| 162 && known_eq (ref->max_size, ref->size) | |
| 163 && known_ge (ref->offset, 0) | |
| 164 && multiple_p (ref->offset, BITS_PER_UNIT) | |
| 165 && multiple_p (ref->size, BITS_PER_UNIT)); | |
| 111 | 166 } |
| 167 | |
| 131 | 168 /* Try to normalize COPY (an ao_ref) relative to REF. Essentially when we are |
| 169 done COPY will only refer bytes found within REF. Return true if COPY | |
| 170 is known to intersect at least one byte of REF. */ | |
| 111 | 171 |
| 131 | 172 static bool |
| 111 | 173 normalize_ref (ao_ref *copy, ao_ref *ref) |
| 0 | 174 { |
| 131 | 175 if (!ordered_p (copy->offset, ref->offset)) |
| 176 return false; | |
| 177 | |
| 111 | 178 /* If COPY starts before REF, then reset the beginning of |
| 179 COPY to match REF and decrease the size of COPY by the | |
| 180 number of bytes removed from COPY. */ | |
| 131 | 181 if (maybe_lt (copy->offset, ref->offset)) |
| 111 | 182 { |
| 131 | 183 poly_int64 diff = ref->offset - copy->offset; |
| 184 if (maybe_le (copy->size, diff)) | |
| 185 return false; | |
| 186 copy->size -= diff; | |
| 111 | 187 copy->offset = ref->offset; |
| 188 } | |
| 189 | |
| 131 | 190 poly_int64 diff = copy->offset - ref->offset; |
| 191 if (maybe_le (ref->size, diff)) | |
| 192 return false; | |
| 193 | |
| 111 | 194 /* If COPY extends beyond REF, chop off its size appropriately. */ |
| 131 | 195 poly_int64 limit = ref->size - diff; |
| 196 if (!ordered_p (limit, copy->size)) | |
| 197 return false; | |
| 198 | |
| 199 if (maybe_gt (copy->size, limit)) | |
| 200 copy->size = limit; | |
| 201 return true; | |
| 111 | 202 } |
| 203 | |
| 204 /* Clear any bytes written by STMT from the bitmap LIVE_BYTES. The base | |
| 205 address written by STMT must match the one found in REF, which must | |
| 206 have its base address previously initialized. | |
| 207 | |
| 208 This routine must be conservative. If we don't know the offset or | |
| 209 actual size written, assume nothing was written. */ | |
| 0 | 210 |
| 111 | 211 static void |
| 212 clear_bytes_written_by (sbitmap live_bytes, gimple *stmt, ao_ref *ref) | |
| 213 { | |
| 214 ao_ref write; | |
| 215 if (!initialize_ao_ref_for_dse (stmt, &write)) | |
| 216 return; | |
| 217 | |
| 218 /* Verify we have the same base memory address, the write | |
| 219 has a known size and overlaps with REF. */ | |
| 131 | 220 HOST_WIDE_INT start, size; |
| 111 | 221 if (valid_ao_ref_for_dse (&write) |
| 222 && operand_equal_p (write.base, ref->base, OEP_ADDRESS_OF) | |
| 131 | 223 && known_eq (write.size, write.max_size) |
| 224 && normalize_ref (&write, ref) | |
| 225 && (write.offset - ref->offset).is_constant (&start) | |
| 226 && write.size.is_constant (&size)) | |
| 227 bitmap_clear_range (live_bytes, start / BITS_PER_UNIT, | |
| 228 size / BITS_PER_UNIT); | |
| 0 | 229 } |
| 230 | |
| 111 | 231 /* REF is a memory write. Extract relevant information from it and |
| 232 initialize the LIVE_BYTES bitmap. If successful, return TRUE. | |
| 233 Otherwise return FALSE. */ | |
| 234 | |
| 235 static bool | |
| 236 setup_live_bytes_from_ref (ao_ref *ref, sbitmap live_bytes) | |
| 237 { | |
| 131 | 238 HOST_WIDE_INT const_size; |
| 111 | 239 if (valid_ao_ref_for_dse (ref) |
| 131 | 240 && ref->size.is_constant (&const_size) |
| 241 && (const_size / BITS_PER_UNIT | |
| 145 | 242 <= param_dse_max_object_size)) |
| 111 | 243 { |
| 244 bitmap_clear (live_bytes); | |
| 131 | 245 bitmap_set_range (live_bytes, 0, const_size / BITS_PER_UNIT); |
| 111 | 246 return true; |
| 247 } | |
| 248 return false; | |
| 249 } | |
| 250 | |
| 251 /* Compute the number of elements that we can trim from the head and | |
| 252 tail of ORIG resulting in a bitmap that is a superset of LIVE. | |
| 253 | |
| 254 Store the number of elements trimmed from the head and tail in | |
| 255 TRIM_HEAD and TRIM_TAIL. | |
| 256 | |
| 257 STMT is the statement being trimmed and is used for debugging dump | |
| 258 output only. */ | |
| 0 | 259 |
| 260 static void | |
| 111 | 261 compute_trims (ao_ref *ref, sbitmap live, int *trim_head, int *trim_tail, |
| 262 gimple *stmt) | |
| 0 | 263 { |
| 111 | 264 /* We use sbitmaps biased such that ref->offset is bit zero and the bitmap |
| 265 extends through ref->size. So we know that in the original bitmap | |
| 266 bits 0..ref->size were true. We don't actually need the bitmap, just | |
| 267 the REF to compute the trims. */ | |
| 268 | |
| 269 /* Now identify how much, if any of the tail we can chop off. */ | |
| 131 | 270 HOST_WIDE_INT const_size; |
| 111 | 271 int last_live = bitmap_last_set_bit (live); |
| 131 | 272 if (ref->size.is_constant (&const_size)) |
| 273 { | |
| 274 int last_orig = (const_size / BITS_PER_UNIT) - 1; | |
| 275 /* We can leave inconvenient amounts on the tail as | |
| 276 residual handling in mem* and str* functions is usually | |
| 277 reasonably efficient. */ | |
| 278 *trim_tail = last_orig - last_live; | |
| 279 | |
| 280 /* But don't trim away out of bounds accesses, as this defeats | |
| 281 proper warnings. | |
| 282 | |
| 283 We could have a type with no TYPE_SIZE_UNIT or we could have a VLA | |
| 284 where TYPE_SIZE_UNIT is not a constant. */ | |
| 285 if (*trim_tail | |
| 286 && TYPE_SIZE_UNIT (TREE_TYPE (ref->base)) | |
| 287 && TREE_CODE (TYPE_SIZE_UNIT (TREE_TYPE (ref->base))) == INTEGER_CST | |
| 288 && compare_tree_int (TYPE_SIZE_UNIT (TREE_TYPE (ref->base)), | |
| 289 last_orig) <= 0) | |
| 290 *trim_tail = 0; | |
| 291 } | |
| 292 else | |
| 293 *trim_tail = 0; | |
| 0 | 294 |
| 111 | 295 /* Identify how much, if any of the head we can chop off. */ |
| 296 int first_orig = 0; | |
| 297 int first_live = bitmap_first_set_bit (live); | |
| 131 | 298 *trim_head = first_live - first_orig; |
| 299 | |
| 300 /* If more than a word remains, then make sure to keep the | |
| 301 starting point at least word aligned. */ | |
| 302 if (last_live - first_live > UNITS_PER_WORD) | |
| 303 *trim_head &= ~(UNITS_PER_WORD - 1); | |
| 111 | 304 |
| 305 if ((*trim_head || *trim_tail) | |
| 306 && dump_file && (dump_flags & TDF_DETAILS)) | |
| 0 | 307 { |
| 111 | 308 fprintf (dump_file, " Trimming statement (head = %d, tail = %d): ", |
| 309 *trim_head, *trim_tail); | |
| 310 print_gimple_stmt (dump_file, stmt, 0, dump_flags); | |
| 311 fprintf (dump_file, "\n"); | |
| 0 | 312 } |
| 313 } | |
| 314 | |
| 111 | 315 /* STMT initializes an object from COMPLEX_CST where one or more of the |
| 316 bytes written may be dead stores. REF is a representation of the | |
| 317 memory written. LIVE is the bitmap of stores that are actually live. | |
| 318 | |
| 319 Attempt to rewrite STMT so that only the real or imaginary part of | |
| 320 the object is actually stored. */ | |
| 321 | |
| 322 static void | |
| 323 maybe_trim_complex_store (ao_ref *ref, sbitmap live, gimple *stmt) | |
| 324 { | |
| 325 int trim_head, trim_tail; | |
| 326 compute_trims (ref, live, &trim_head, &trim_tail, stmt); | |
| 327 | |
| 328 /* The amount of data trimmed from the head or tail must be at | |
| 329 least half the size of the object to ensure we're trimming | |
| 330 the entire real or imaginary half. By writing things this | |
| 331 way we avoid more O(n) bitmap operations. */ | |
| 131 | 332 if (known_ge (trim_tail * 2 * BITS_PER_UNIT, ref->size)) |
| 111 | 333 { |
| 334 /* TREE_REALPART is live */ | |
| 335 tree x = TREE_REALPART (gimple_assign_rhs1 (stmt)); | |
| 336 tree y = gimple_assign_lhs (stmt); | |
| 337 y = build1 (REALPART_EXPR, TREE_TYPE (x), y); | |
| 338 gimple_assign_set_lhs (stmt, y); | |
| 339 gimple_assign_set_rhs1 (stmt, x); | |
| 340 } | |
| 131 | 341 else if (known_ge (trim_head * 2 * BITS_PER_UNIT, ref->size)) |
| 111 | 342 { |
| 343 /* TREE_IMAGPART is live */ | |
| 344 tree x = TREE_IMAGPART (gimple_assign_rhs1 (stmt)); | |
| 345 tree y = gimple_assign_lhs (stmt); | |
| 346 y = build1 (IMAGPART_EXPR, TREE_TYPE (x), y); | |
| 347 gimple_assign_set_lhs (stmt, y); | |
| 348 gimple_assign_set_rhs1 (stmt, x); | |
| 349 } | |
| 350 | |
| 351 /* Other cases indicate parts of both the real and imag subobjects | |
| 352 are live. We do not try to optimize those cases. */ | |
| 353 } | |
| 354 | |
| 355 /* STMT initializes an object using a CONSTRUCTOR where one or more of the | |
| 356 bytes written are dead stores. ORIG is the bitmap of bytes stored by | |
| 357 STMT. LIVE is the bitmap of stores that are actually live. | |
| 358 | |
| 359 Attempt to rewrite STMT so that only the real or imaginary part of | |
| 360 the object is actually stored. | |
| 361 | |
| 362 The most common case for getting here is a CONSTRUCTOR with no elements | |
| 363 being used to zero initialize an object. We do not try to handle other | |
| 364 cases as those would force us to fully cover the object with the | |
| 365 CONSTRUCTOR node except for the components that are dead. */ | |
| 366 | |
| 367 static void | |
| 368 maybe_trim_constructor_store (ao_ref *ref, sbitmap live, gimple *stmt) | |
| 369 { | |
| 370 tree ctor = gimple_assign_rhs1 (stmt); | |
| 371 | |
| 372 /* This is the only case we currently handle. It actually seems to | |
| 373 catch most cases of actual interest. */ | |
| 374 gcc_assert (CONSTRUCTOR_NELTS (ctor) == 0); | |
| 375 | |
| 376 int head_trim = 0; | |
| 377 int tail_trim = 0; | |
| 378 compute_trims (ref, live, &head_trim, &tail_trim, stmt); | |
| 379 | |
| 380 /* Now we want to replace the constructor initializer | |
| 381 with memset (object + head_trim, 0, size - head_trim - tail_trim). */ | |
| 382 if (head_trim || tail_trim) | |
| 383 { | |
| 384 /* We want &lhs for the MEM_REF expression. */ | |
| 385 tree lhs_addr = build_fold_addr_expr (gimple_assign_lhs (stmt)); | |
| 386 | |
| 387 if (! is_gimple_min_invariant (lhs_addr)) | |
| 388 return; | |
| 389 | |
| 390 /* The number of bytes for the new constructor. */ | |
| 131 | 391 poly_int64 ref_bytes = exact_div (ref->size, BITS_PER_UNIT); |
| 392 poly_int64 count = ref_bytes - head_trim - tail_trim; | |
| 111 | 393 |
| 394 /* And the new type for the CONSTRUCTOR. Essentially it's just | |
| 395 a char array large enough to cover the non-trimmed parts of | |
| 396 the original CONSTRUCTOR. Note we want explicit bounds here | |
| 397 so that we know how many bytes to clear when expanding the | |
| 398 CONSTRUCTOR. */ | |
| 399 tree type = build_array_type_nelts (char_type_node, count); | |
| 400 | |
| 401 /* Build a suitable alias type rather than using alias set zero | |
| 402 to avoid pessimizing. */ | |
| 403 tree alias_type = reference_alias_ptr_type (gimple_assign_lhs (stmt)); | |
| 404 | |
| 405 /* Build a MEM_REF representing the whole accessed area, starting | |
| 406 at the first byte not trimmed. */ | |
| 407 tree exp = fold_build2 (MEM_REF, type, lhs_addr, | |
| 408 build_int_cst (alias_type, head_trim)); | |
| 409 | |
| 410 /* Now update STMT with a new RHS and LHS. */ | |
| 411 gimple_assign_set_lhs (stmt, exp); | |
| 412 gimple_assign_set_rhs1 (stmt, build_constructor (type, NULL)); | |
| 413 } | |
| 414 } | |
| 415 | |
| 416 /* STMT is a memcpy, memmove or memset. Decrement the number of bytes | |
| 417 copied/set by DECREMENT. */ | |
| 418 static void | |
| 419 decrement_count (gimple *stmt, int decrement) | |
| 420 { | |
| 421 tree *countp = gimple_call_arg_ptr (stmt, 2); | |
| 422 gcc_assert (TREE_CODE (*countp) == INTEGER_CST); | |
| 423 *countp = wide_int_to_tree (TREE_TYPE (*countp), (TREE_INT_CST_LOW (*countp) | |
| 424 - decrement)); | |
| 425 | |
| 426 } | |
| 427 | |
| 428 static void | |
| 429 increment_start_addr (gimple *stmt, tree *where, int increment) | |
| 430 { | |
| 431 if (TREE_CODE (*where) == SSA_NAME) | |
| 432 { | |
| 433 tree tem = make_ssa_name (TREE_TYPE (*where)); | |
| 434 gassign *newop | |
| 435 = gimple_build_assign (tem, POINTER_PLUS_EXPR, *where, | |
| 436 build_int_cst (sizetype, increment)); | |
| 437 gimple_stmt_iterator gsi = gsi_for_stmt (stmt); | |
| 438 gsi_insert_before (&gsi, newop, GSI_SAME_STMT); | |
| 439 *where = tem; | |
| 440 update_stmt (gsi_stmt (gsi)); | |
| 441 return; | |
| 442 } | |
| 443 | |
| 444 *where = build_fold_addr_expr (fold_build2 (MEM_REF, char_type_node, | |
| 445 *where, | |
| 446 build_int_cst (ptr_type_node, | |
| 447 increment))); | |
| 448 } | |
| 449 | |
| 450 /* STMT is builtin call that writes bytes in bitmap ORIG, some bytes are dead | |
| 451 (ORIG & ~NEW) and need not be stored. Try to rewrite STMT to reduce | |
| 452 the amount of data it actually writes. | |
| 453 | |
| 454 Right now we only support trimming from the head or the tail of the | |
| 455 memory region. In theory we could split the mem* call, but it's | |
| 456 likely of marginal value. */ | |
| 457 | |
| 458 static void | |
| 459 maybe_trim_memstar_call (ao_ref *ref, sbitmap live, gimple *stmt) | |
| 460 { | |
| 145 | 461 int head_trim, tail_trim; |
| 111 | 462 switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt))) |
| 463 { | |
| 145 | 464 case BUILT_IN_STRNCPY: |
| 465 case BUILT_IN_STRNCPY_CHK: | |
| 466 compute_trims (ref, live, &head_trim, &tail_trim, stmt); | |
| 467 if (head_trim) | |
| 468 { | |
| 469 /* Head trimming of strncpy is only possible if we can | |
| 470 prove all bytes we would trim are non-zero (or we could | |
| 471 turn the strncpy into memset if there must be zero | |
| 472 among the head trimmed bytes). If we don't know anything | |
| 473 about those bytes, the presence or absence of '\0' bytes | |
| 474 in there will affect whether it acts for the non-trimmed | |
| 475 bytes as memset or memcpy/strncpy. */ | |
| 476 c_strlen_data lendata = { }; | |
| 477 int orig_head_trim = head_trim; | |
| 478 tree srcstr = gimple_call_arg (stmt, 1); | |
| 479 if (!get_range_strlen (srcstr, &lendata, /*eltsize=*/1) | |
| 480 || !tree_fits_uhwi_p (lendata.minlen)) | |
| 481 head_trim = 0; | |
| 482 else if (tree_to_uhwi (lendata.minlen) < (unsigned) head_trim) | |
| 483 { | |
| 484 head_trim = tree_to_uhwi (lendata.minlen); | |
| 485 if ((orig_head_trim & (UNITS_PER_WORD - 1)) == 0) | |
| 486 head_trim &= ~(UNITS_PER_WORD - 1); | |
| 487 } | |
| 488 if (orig_head_trim != head_trim | |
| 489 && dump_file | |
| 490 && (dump_flags & TDF_DETAILS)) | |
| 491 fprintf (dump_file, | |
| 492 " Adjusting strncpy trimming to (head = %d," | |
| 493 " tail = %d)\n", head_trim, tail_trim); | |
| 494 } | |
| 495 goto do_memcpy; | |
| 496 | |
| 111 | 497 case BUILT_IN_MEMCPY: |
| 498 case BUILT_IN_MEMMOVE: | |
| 145 | 499 case BUILT_IN_MEMCPY_CHK: |
| 500 case BUILT_IN_MEMMOVE_CHK: | |
| 501 compute_trims (ref, live, &head_trim, &tail_trim, stmt); | |
| 111 | 502 |
| 145 | 503 do_memcpy: |
| 504 /* Tail trimming is easy, we can just reduce the count. */ | |
| 505 if (tail_trim) | |
| 506 decrement_count (stmt, tail_trim); | |
| 111 | 507 |
| 145 | 508 /* Head trimming requires adjusting all the arguments. */ |
| 509 if (head_trim) | |
| 510 { | |
| 511 /* For __*_chk need to adjust also the last argument. */ | |
| 512 if (gimple_call_num_args (stmt) == 4) | |
| 513 { | |
| 514 tree size = gimple_call_arg (stmt, 3); | |
| 515 if (!tree_fits_uhwi_p (size)) | |
| 516 break; | |
| 517 if (!integer_all_onesp (size)) | |
| 518 { | |
| 519 unsigned HOST_WIDE_INT sz = tree_to_uhwi (size); | |
| 520 if (sz < (unsigned) head_trim) | |
| 521 break; | |
| 522 tree arg = wide_int_to_tree (TREE_TYPE (size), | |
| 523 sz - head_trim); | |
| 524 gimple_call_set_arg (stmt, 3, arg); | |
| 525 } | |
| 526 } | |
| 527 tree *dst = gimple_call_arg_ptr (stmt, 0); | |
| 528 increment_start_addr (stmt, dst, head_trim); | |
| 529 tree *src = gimple_call_arg_ptr (stmt, 1); | |
| 530 increment_start_addr (stmt, src, head_trim); | |
| 531 decrement_count (stmt, head_trim); | |
| 532 } | |
| 533 break; | |
| 111 | 534 |
| 535 case BUILT_IN_MEMSET: | |
| 145 | 536 case BUILT_IN_MEMSET_CHK: |
| 537 compute_trims (ref, live, &head_trim, &tail_trim, stmt); | |
| 111 | 538 |
| 145 | 539 /* Tail trimming is easy, we can just reduce the count. */ |
| 540 if (tail_trim) | |
| 541 decrement_count (stmt, tail_trim); | |
| 111 | 542 |
| 145 | 543 /* Head trimming requires adjusting all the arguments. */ |
| 544 if (head_trim) | |
| 545 { | |
| 546 /* For __*_chk need to adjust also the last argument. */ | |
| 547 if (gimple_call_num_args (stmt) == 4) | |
| 548 { | |
| 549 tree size = gimple_call_arg (stmt, 3); | |
| 550 if (!tree_fits_uhwi_p (size)) | |
| 551 break; | |
| 552 if (!integer_all_onesp (size)) | |
| 553 { | |
| 554 unsigned HOST_WIDE_INT sz = tree_to_uhwi (size); | |
| 555 if (sz < (unsigned) head_trim) | |
| 556 break; | |
| 557 tree arg = wide_int_to_tree (TREE_TYPE (size), | |
| 558 sz - head_trim); | |
| 559 gimple_call_set_arg (stmt, 3, arg); | |
| 560 } | |
| 561 } | |
| 562 tree *dst = gimple_call_arg_ptr (stmt, 0); | |
| 563 increment_start_addr (stmt, dst, head_trim); | |
| 564 decrement_count (stmt, head_trim); | |
| 565 } | |
| 566 break; | |
| 111 | 567 |
| 145 | 568 default: |
| 569 break; | |
| 111 | 570 } |
| 571 } | |
| 572 | |
| 573 /* STMT is a memory write where one or more bytes written are dead | |
| 574 stores. ORIG is the bitmap of bytes stored by STMT. LIVE is the | |
| 575 bitmap of stores that are actually live. | |
| 576 | |
| 577 Attempt to rewrite STMT so that it writes fewer memory locations. Right | |
| 578 now we only support trimming at the start or end of the memory region. | |
| 579 It's not clear how much there is to be gained by trimming from the middle | |
| 580 of the region. */ | |
| 581 | |
| 582 static void | |
| 583 maybe_trim_partially_dead_store (ao_ref *ref, sbitmap live, gimple *stmt) | |
| 584 { | |
| 585 if (is_gimple_assign (stmt) | |
| 586 && TREE_CODE (gimple_assign_lhs (stmt)) != TARGET_MEM_REF) | |
| 587 { | |
| 588 switch (gimple_assign_rhs_code (stmt)) | |
| 589 { | |
| 590 case CONSTRUCTOR: | |
| 591 maybe_trim_constructor_store (ref, live, stmt); | |
| 592 break; | |
| 593 case COMPLEX_CST: | |
| 594 maybe_trim_complex_store (ref, live, stmt); | |
| 595 break; | |
| 596 default: | |
| 597 break; | |
| 598 } | |
| 599 } | |
| 600 } | |
| 601 | |
| 602 /* Return TRUE if USE_REF reads bytes from LIVE where live is | |
| 603 derived from REF, a write reference. | |
| 604 | |
| 605 While this routine may modify USE_REF, it's passed by value, not | |
| 606 location. So callers do not see those modifications. */ | |
| 607 | |
| 608 static bool | |
| 609 live_bytes_read (ao_ref use_ref, ao_ref *ref, sbitmap live) | |
| 610 { | |
| 611 /* We have already verified that USE_REF and REF hit the same object. | |
| 612 Now verify that there's actually an overlap between USE_REF and REF. */ | |
| 131 | 613 HOST_WIDE_INT start, size; |
| 614 if (normalize_ref (&use_ref, ref) | |
| 615 && (use_ref.offset - ref->offset).is_constant (&start) | |
| 616 && use_ref.size.is_constant (&size)) | |
| 111 | 617 { |
| 618 /* If USE_REF covers all of REF, then it will hit one or more | |
| 619 live bytes. This avoids useless iteration over the bitmap | |
| 620 below. */ | |
| 131 | 621 if (start == 0 && known_eq (size, ref->size)) |
| 111 | 622 return true; |
| 623 | |
| 624 /* Now check if any of the remaining bits in use_ref are set in LIVE. */ | |
| 131 | 625 return bitmap_bit_in_range_p (live, start / BITS_PER_UNIT, |
| 626 (start + size - 1) / BITS_PER_UNIT); | |
| 111 | 627 } |
| 628 return true; | |
| 629 } | |
| 630 | |
| 131 | 631 /* Callback for dse_classify_store calling for_each_index. Verify that |
| 632 indices are invariant in the loop with backedge PHI in basic-block DATA. */ | |
| 633 | |
| 634 static bool | |
| 635 check_name (tree, tree *idx, void *data) | |
| 636 { | |
| 637 basic_block phi_bb = (basic_block) data; | |
| 638 if (TREE_CODE (*idx) == SSA_NAME | |
| 639 && !SSA_NAME_IS_DEFAULT_DEF (*idx) | |
| 640 && dominated_by_p (CDI_DOMINATORS, gimple_bb (SSA_NAME_DEF_STMT (*idx)), | |
| 641 phi_bb)) | |
| 642 return false; | |
| 643 return true; | |
| 644 } | |
| 645 | |
| 145 | 646 /* STMT stores the value 0 into one or more memory locations |
| 647 (via memset, empty constructor, calloc call, etc). | |
| 648 | |
| 649 See if there is a subsequent store of the value 0 to one | |
| 650 or more of the same memory location(s). If so, the subsequent | |
| 651 store is redundant and can be removed. | |
| 652 | |
| 653 The subsequent stores could be via memset, empty constructors, | |
| 654 simple MEM stores, etc. */ | |
| 655 | |
| 656 static void | |
| 657 dse_optimize_redundant_stores (gimple *stmt) | |
| 658 { | |
| 659 int cnt = 0; | |
| 660 | |
| 661 /* We could do something fairly complex and look through PHIs | |
| 662 like DSE_CLASSIFY_STORE, but it doesn't seem to be worth | |
| 663 the effort. | |
| 664 | |
| 665 Look at all the immediate uses of the VDEF (which are obviously | |
| 666 dominated by STMT). See if one or more stores 0 into the same | |
| 667 memory locations a STMT, if so remove the immediate use statements. */ | |
| 668 tree defvar = gimple_vdef (stmt); | |
| 669 imm_use_iterator ui; | |
| 670 gimple *use_stmt; | |
| 671 FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar) | |
| 672 { | |
| 673 /* Limit stmt walking. */ | |
| 674 if (++cnt > param_dse_max_alias_queries_per_store) | |
| 675 BREAK_FROM_IMM_USE_STMT (ui); | |
| 676 | |
| 677 /* If USE_STMT stores 0 into one or more of the same locations | |
| 678 as STMT and STMT would kill USE_STMT, then we can just remove | |
| 679 USE_STMT. */ | |
| 680 tree fndecl; | |
| 681 if ((is_gimple_assign (use_stmt) | |
| 682 && gimple_vdef (use_stmt) | |
| 683 && (gimple_assign_single_p (use_stmt) | |
| 684 && initializer_zerop (gimple_assign_rhs1 (use_stmt)))) | |
| 685 || (gimple_call_builtin_p (use_stmt, BUILT_IN_NORMAL) | |
| 686 && (fndecl = gimple_call_fndecl (use_stmt)) != NULL | |
| 687 && (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMSET | |
| 688 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMSET_CHK) | |
| 689 && integer_zerop (gimple_call_arg (use_stmt, 1)))) | |
| 690 { | |
| 691 ao_ref write; | |
| 692 | |
| 693 if (!initialize_ao_ref_for_dse (use_stmt, &write)) | |
| 694 BREAK_FROM_IMM_USE_STMT (ui) | |
| 695 | |
| 696 if (valid_ao_ref_for_dse (&write) | |
| 697 && stmt_kills_ref_p (stmt, &write)) | |
| 698 { | |
| 699 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt); | |
| 700 if (is_gimple_assign (use_stmt)) | |
| 701 delete_dead_or_redundant_assignment (&gsi, "redundant", | |
| 702 need_eh_cleanup); | |
| 703 else if (is_gimple_call (use_stmt)) | |
| 704 delete_dead_or_redundant_call (&gsi, "redundant"); | |
| 705 else | |
| 706 gcc_unreachable (); | |
| 707 } | |
| 708 } | |
| 709 } | |
| 710 } | |
| 711 | |
| 0 | 712 /* A helper of dse_optimize_stmt. |
| 131 | 713 Given a GIMPLE_ASSIGN in STMT that writes to REF, classify it |
| 714 according to downstream uses and defs. Sets *BY_CLOBBER_P to true | |
| 715 if only clobber statements influenced the classification result. | |
| 716 Returns the classification. */ | |
| 0 | 717 |
| 145 | 718 dse_store_status |
| 131 | 719 dse_classify_store (ao_ref *ref, gimple *stmt, |
| 720 bool byte_tracking_enabled, sbitmap live_bytes, | |
| 145 | 721 bool *by_clobber_p, tree stop_at_vuse) |
| 0 | 722 { |
| 111 | 723 gimple *temp; |
| 131 | 724 int cnt = 0; |
| 725 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
|
726 |
| 131 | 727 if (by_clobber_p) |
| 728 *by_clobber_p = true; | |
| 0 | 729 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
730 /* 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
|
731 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
|
732 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
|
733 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
|
734 temp = stmt; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
735 do |
| 0 | 736 { |
| 131 | 737 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
|
738 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
|
739 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
|
740 tree defvar; |
| 0 | 741 |
| 742 if (gimple_code (temp) == GIMPLE_PHI) | |
| 131 | 743 { |
| 744 /* If we visit this PHI by following a backedge then we have to | |
| 745 make sure ref->ref only refers to SSA names that are invariant | |
| 746 with respect to the loop represented by this PHI node. */ | |
| 747 if (dominated_by_p (CDI_DOMINATORS, gimple_bb (stmt), | |
| 748 gimple_bb (temp)) | |
| 749 && !for_each_index (ref->ref ? &ref->ref : &ref->base, | |
| 750 check_name, gimple_bb (temp))) | |
| 751 return DSE_STORE_LIVE; | |
| 752 defvar = PHI_RESULT (temp); | |
| 753 bitmap_set_bit (visited, SSA_NAME_VERSION (defvar)); | |
| 754 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
755 else |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
756 defvar = gimple_vdef (temp); |
| 145 | 757 |
| 758 /* If we're instructed to stop walking at region boundary, do so. */ | |
| 759 if (defvar == stop_at_vuse) | |
| 760 return DSE_STORE_LIVE; | |
| 761 | |
| 131 | 762 auto_vec<gimple *, 10> defs; |
| 763 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
|
764 FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar) |
| 0 | 765 { |
| 131 | 766 /* Limit stmt walking. */ |
| 145 | 767 if (++cnt > 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
|
768 { |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
769 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
|
770 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
|
771 } |
| 131 | 772 |
| 773 /* We have visited ourselves already so ignore STMT for the | |
| 774 purpose of chaining. */ | |
| 775 if (use_stmt == stmt) | |
| 776 ; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
777 /* 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
|
778 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
|
779 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
|
780 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
|
781 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
|
782 { |
| 131 | 783 /* If we already visited this PHI ignore it for further |
| 784 processing. */ | |
| 785 if (!bitmap_bit_p (visited, | |
| 786 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
|
787 { |
| 131 | 788 defs.safe_push (use_stmt); |
| 789 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
|
790 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
791 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
792 /* If the statement is a use the store is not dead. */ |
| 111 | 793 else if (ref_maybe_used_by_stmt_p (use_stmt, ref)) |
| 0 | 794 { |
| 111 | 795 /* Handle common cases where we can easily build an ao_ref |
| 796 structure for USE_STMT and in doing so we find that the | |
| 797 references hit non-live bytes and thus can be ignored. */ | |
| 131 | 798 if (byte_tracking_enabled |
| 799 && is_gimple_assign (use_stmt)) | |
| 111 | 800 { |
| 131 | 801 ao_ref use_ref; |
| 802 ao_ref_init (&use_ref, gimple_assign_rhs1 (use_stmt)); | |
| 803 if (valid_ao_ref_for_dse (&use_ref) | |
| 804 && use_ref.base == ref->base | |
| 805 && known_eq (use_ref.size, use_ref.max_size) | |
| 806 && !live_bytes_read (use_ref, ref, live_bytes)) | |
| 111 | 807 { |
| 131 | 808 /* If this is a store, remember it as we possibly |
| 809 need to walk the defs uses. */ | |
| 810 if (gimple_vdef (use_stmt)) | |
| 811 defs.safe_push (use_stmt); | |
| 812 continue; | |
| 111 | 813 } |
| 814 } | |
| 815 | |
| 0 | 816 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
|
817 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
|
818 } |
| 131 | 819 /* If this is a store, remember it as we possibly need to walk the |
| 820 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
|
821 else if (gimple_vdef (use_stmt)) |
| 131 | 822 defs.safe_push (use_stmt); |
| 0 | 823 } |
| 824 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
825 if (fail) |
| 111 | 826 { |
| 827 /* STMT might be partially dead and we may be able to reduce | |
| 828 how many memory locations it stores into. */ | |
| 829 if (byte_tracking_enabled && !gimple_clobber_p (stmt)) | |
| 830 return DSE_STORE_MAYBE_PARTIAL_DEAD; | |
| 831 return DSE_STORE_LIVE; | |
| 832 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
833 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
834 /* 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
|
835 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
|
836 just pretend the stmt makes itself dead. Otherwise fail. */ |
| 131 | 837 if (defs.is_empty ()) |
| 0 | 838 { |
| 111 | 839 if (ref_may_alias_global_p (ref)) |
| 840 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
|
841 |
| 131 | 842 if (by_clobber_p) |
| 843 *by_clobber_p = false; | |
| 844 return DSE_STORE_DEAD; | |
| 0 | 845 } |
| 111 | 846 |
| 131 | 847 /* Process defs and remove those we need not process further. */ |
| 848 for (unsigned i = 0; i < defs.length ();) | |
| 849 { | |
| 850 gimple *def = defs[i]; | |
| 851 gimple *use_stmt; | |
| 852 use_operand_p use_p; | |
| 853 /* If the path to check starts with a kill we do not need to | |
| 854 process it further. | |
| 855 ??? With byte tracking we need only kill the bytes currently | |
| 856 live. */ | |
| 857 if (stmt_kills_ref_p (def, ref)) | |
| 858 { | |
| 859 if (by_clobber_p && !gimple_clobber_p (def)) | |
| 860 *by_clobber_p = false; | |
| 861 defs.unordered_remove (i); | |
| 862 } | |
| 863 /* In addition to kills we can remove defs whose only use | |
| 864 is another def in defs. That can only ever be PHIs of which | |
| 865 we track a single for simplicity reasons (we fail for multiple | |
| 866 PHIs anyways). We can also ignore defs that feed only into | |
| 867 already visited PHIs. */ | |
| 868 else if (gimple_code (def) != GIMPLE_PHI | |
| 869 && single_imm_use (gimple_vdef (def), &use_p, &use_stmt) | |
| 870 && (use_stmt == phi_def | |
| 871 || (gimple_code (use_stmt) == GIMPLE_PHI | |
| 872 && bitmap_bit_p (visited, | |
| 873 SSA_NAME_VERSION | |
| 874 (PHI_RESULT (use_stmt)))))) | |
| 875 defs.unordered_remove (i); | |
| 876 else | |
| 877 ++i; | |
| 878 } | |
| 879 | |
| 880 /* If all defs kill the ref we are done. */ | |
| 881 if (defs.is_empty ()) | |
| 882 return DSE_STORE_DEAD; | |
| 883 /* If more than one def survives fail. */ | |
| 884 if (defs.length () > 1) | |
| 885 { | |
| 886 /* STMT might be partially dead and we may be able to reduce | |
| 887 how many memory locations it stores into. */ | |
| 888 if (byte_tracking_enabled && !gimple_clobber_p (stmt)) | |
| 889 return DSE_STORE_MAYBE_PARTIAL_DEAD; | |
| 890 return DSE_STORE_LIVE; | |
| 891 } | |
| 892 temp = defs[0]; | |
| 893 | |
| 894 /* Track partial kills. */ | |
| 895 if (byte_tracking_enabled) | |
| 896 { | |
| 897 clear_bytes_written_by (live_bytes, temp, ref); | |
| 898 if (bitmap_empty_p (live_bytes)) | |
| 899 { | |
| 900 if (by_clobber_p && !gimple_clobber_p (temp)) | |
| 901 *by_clobber_p = false; | |
| 902 return DSE_STORE_DEAD; | |
| 903 } | |
| 904 } | |
| 0 | 905 } |
| 131 | 906 /* Continue walking until there are no more live bytes. */ |
| 907 while (1); | |
| 0 | 908 } |
| 909 | |
| 910 | |
| 111 | 911 class dse_dom_walker : public dom_walker |
| 912 { | |
| 913 public: | |
| 914 dse_dom_walker (cdi_direction direction) | |
| 915 : dom_walker (direction), | |
| 145 | 916 m_live_bytes (param_dse_max_object_size), |
| 111 | 917 m_byte_tracking_enabled (false) {} |
| 918 | |
| 919 virtual edge before_dom_children (basic_block); | |
| 920 | |
| 921 private: | |
| 922 auto_sbitmap m_live_bytes; | |
| 923 bool m_byte_tracking_enabled; | |
| 924 void dse_optimize_stmt (gimple_stmt_iterator *); | |
| 925 }; | |
| 926 | |
| 927 /* Delete a dead call at GSI, which is mem* call of some kind. */ | |
| 928 static void | |
| 145 | 929 delete_dead_or_redundant_call (gimple_stmt_iterator *gsi, const char *type) |
| 111 | 930 { |
| 931 gimple *stmt = gsi_stmt (*gsi); | |
| 932 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 933 { | |
| 145 | 934 fprintf (dump_file, " Deleted %s call: ", type); |
| 111 | 935 print_gimple_stmt (dump_file, stmt, 0, dump_flags); |
| 936 fprintf (dump_file, "\n"); | |
| 937 } | |
| 938 | |
| 939 tree lhs = gimple_call_lhs (stmt); | |
| 940 if (lhs) | |
| 941 { | |
| 942 tree ptr = gimple_call_arg (stmt, 0); | |
| 943 gimple *new_stmt = gimple_build_assign (lhs, ptr); | |
| 944 unlink_stmt_vdef (stmt); | |
| 945 if (gsi_replace (gsi, new_stmt, true)) | |
| 946 bitmap_set_bit (need_eh_cleanup, gimple_bb (stmt)->index); | |
| 947 } | |
| 948 else | |
| 949 { | |
| 950 /* Then we need to fix the operand of the consuming stmt. */ | |
| 951 unlink_stmt_vdef (stmt); | |
| 952 | |
| 953 /* Remove the dead store. */ | |
| 954 if (gsi_remove (gsi, true)) | |
| 955 bitmap_set_bit (need_eh_cleanup, gimple_bb (stmt)->index); | |
| 956 release_defs (stmt); | |
| 957 } | |
| 958 } | |
| 959 | |
| 960 /* Delete a dead store at GSI, which is a gimple assignment. */ | |
| 961 | |
| 145 | 962 void |
| 963 delete_dead_or_redundant_assignment (gimple_stmt_iterator *gsi, const char *type, | |
| 964 bitmap need_eh_cleanup) | |
| 111 | 965 { |
| 966 gimple *stmt = gsi_stmt (*gsi); | |
| 967 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 968 { | |
| 145 | 969 fprintf (dump_file, " Deleted %s store: ", type); |
| 111 | 970 print_gimple_stmt (dump_file, stmt, 0, dump_flags); |
| 971 fprintf (dump_file, "\n"); | |
| 972 } | |
| 973 | |
| 974 /* Then we need to fix the operand of the consuming stmt. */ | |
| 975 unlink_stmt_vdef (stmt); | |
| 976 | |
| 977 /* Remove the dead store. */ | |
| 978 basic_block bb = gimple_bb (stmt); | |
| 145 | 979 if (gsi_remove (gsi, true) && need_eh_cleanup) |
| 111 | 980 bitmap_set_bit (need_eh_cleanup, bb->index); |
| 981 | |
| 982 /* And release any SSA_NAMEs set in this statement back to the | |
| 983 SSA_NAME manager. */ | |
| 984 release_defs (stmt); | |
| 985 } | |
| 986 | |
| 0 | 987 /* Attempt to eliminate dead stores in the statement referenced by BSI. |
| 988 | |
| 989 A dead store is a store into a memory location which will later be | |
| 990 overwritten by another store without any intervening loads. In this | |
| 991 case the earlier store can be deleted. | |
| 992 | |
| 993 In our SSA + virtual operand world we use immediate uses of virtual | |
| 994 operands to detect dead stores. If a store's virtual definition | |
| 995 is used precisely once by a later store to the same location which | |
| 996 post dominates the first store, then the first store is dead. */ | |
| 997 | |
| 111 | 998 void |
| 999 dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi) | |
| 0 | 1000 { |
| 111 | 1001 gimple *stmt = gsi_stmt (*gsi); |
| 0 | 1002 |
| 1003 /* If this statement has no virtual defs, then there is nothing | |
| 1004 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
|
1005 if (!gimple_vdef (stmt)) |
| 0 | 1006 return; |
| 1007 | |
| 111 | 1008 /* Don't return early on *this_2(D) ={v} {CLOBBER}. */ |
| 1009 if (gimple_has_volatile_ops (stmt) | |
| 1010 && (!gimple_clobber_p (stmt) | |
| 1011 || TREE_CODE (gimple_assign_lhs (stmt)) != MEM_REF)) | |
| 1012 return; | |
| 1013 | |
| 1014 ao_ref ref; | |
| 1015 if (!initialize_ao_ref_for_dse (stmt, &ref)) | |
| 0 | 1016 return; |
| 1017 | |
| 111 | 1018 /* We know we have virtual definitions. We can handle assignments and |
| 1019 some builtin calls. */ | |
| 1020 if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)) | |
| 1021 { | |
| 145 | 1022 tree fndecl = gimple_call_fndecl (stmt); |
| 1023 switch (DECL_FUNCTION_CODE (fndecl)) | |
| 111 | 1024 { |
| 145 | 1025 case BUILT_IN_MEMCPY: |
| 1026 case BUILT_IN_MEMMOVE: | |
| 1027 case BUILT_IN_STRNCPY: | |
| 1028 case BUILT_IN_MEMSET: | |
| 1029 case BUILT_IN_MEMCPY_CHK: | |
| 1030 case BUILT_IN_MEMMOVE_CHK: | |
| 1031 case BUILT_IN_STRNCPY_CHK: | |
| 1032 case BUILT_IN_MEMSET_CHK: | |
| 1033 { | |
| 1034 /* Occasionally calls with an explicit length of zero | |
| 1035 show up in the IL. It's pointless to do analysis | |
| 1036 on them, they're trivially dead. */ | |
| 1037 tree size = gimple_call_arg (stmt, 2); | |
| 1038 if (integer_zerop (size)) | |
| 1039 { | |
| 1040 delete_dead_or_redundant_call (gsi, "dead"); | |
| 1041 return; | |
| 1042 } | |
| 111 | 1043 |
| 145 | 1044 /* If this is a memset call that initializes an object |
| 1045 to zero, it may be redundant with an earlier memset | |
| 1046 or empty CONSTRUCTOR of a larger object. */ | |
| 1047 if ((DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMSET | |
| 1048 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMSET_CHK) | |
| 1049 && integer_zerop (gimple_call_arg (stmt, 1))) | |
| 1050 dse_optimize_redundant_stores (stmt); | |
| 1051 | |
| 1052 enum dse_store_status store_status; | |
| 1053 m_byte_tracking_enabled | |
| 1054 = setup_live_bytes_from_ref (&ref, m_live_bytes); | |
| 1055 store_status = dse_classify_store (&ref, stmt, | |
| 1056 m_byte_tracking_enabled, | |
| 1057 m_live_bytes); | |
| 1058 if (store_status == DSE_STORE_LIVE) | |
| 1059 return; | |
| 111 | 1060 |
| 145 | 1061 if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD) |
| 1062 { | |
| 1063 maybe_trim_memstar_call (&ref, m_live_bytes, stmt); | |
| 1064 return; | |
| 1065 } | |
| 111 | 1066 |
| 145 | 1067 if (store_status == DSE_STORE_DEAD) |
| 1068 delete_dead_or_redundant_call (gsi, "dead"); | |
| 1069 return; | |
| 1070 } | |
| 111 | 1071 |
| 145 | 1072 case BUILT_IN_CALLOC: |
| 1073 /* We already know the arguments are integer constants. */ | |
| 1074 dse_optimize_redundant_stores (stmt); | |
| 1075 return; | |
| 1076 | |
| 1077 default: | |
| 1078 return; | |
| 111 | 1079 } |
| 1080 } | |
| 0 | 1081 |
| 1082 if (is_gimple_assign (stmt)) | |
| 1083 { | |
| 131 | 1084 bool by_clobber_p = false; |
| 0 | 1085 |
| 145 | 1086 /* Check if this statement stores zero to a memory location, |
| 1087 and if there is a subsequent store of zero to the same | |
| 1088 memory location. If so, remove the subsequent store. */ | |
| 1089 if (gimple_assign_single_p (stmt) | |
| 1090 && initializer_zerop (gimple_assign_rhs1 (stmt))) | |
| 1091 dse_optimize_redundant_stores (stmt); | |
| 1092 | |
| 111 | 1093 /* Self-assignments are zombies. */ |
| 1094 if (operand_equal_p (gimple_assign_rhs1 (stmt), | |
| 1095 gimple_assign_lhs (stmt), 0)) | |
| 131 | 1096 ; |
| 111 | 1097 else |
| 1098 { | |
| 1099 m_byte_tracking_enabled | |
| 1100 = setup_live_bytes_from_ref (&ref, m_live_bytes); | |
| 1101 enum dse_store_status store_status; | |
| 131 | 1102 store_status = dse_classify_store (&ref, stmt, |
| 111 | 1103 m_byte_tracking_enabled, |
| 131 | 1104 m_live_bytes, &by_clobber_p); |
| 111 | 1105 if (store_status == DSE_STORE_LIVE) |
| 1106 return; | |
| 0 | 1107 |
| 111 | 1108 if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD) |
| 1109 { | |
| 1110 maybe_trim_partially_dead_store (&ref, m_live_bytes, stmt); | |
| 1111 return; | |
| 1112 } | |
| 1113 } | |
| 1114 | |
| 1115 /* Now we know that use_stmt kills the LHS of stmt. */ | |
| 1116 | |
| 1117 /* But only remove *this_2(D) ={v} {CLOBBER} if killed by | |
| 1118 another clobber stmt. */ | |
| 1119 if (gimple_clobber_p (stmt) | |
| 131 | 1120 && !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
|
1121 return; |
| 0 | 1122 |
| 145 | 1123 delete_dead_or_redundant_assignment (gsi, "dead", need_eh_cleanup); |
| 0 | 1124 } |
| 1125 } | |
| 1126 | |
| 111 | 1127 edge |
| 1128 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
|
1129 { |
| 0 | 1130 gimple_stmt_iterator gsi; |
| 1131 | |
| 111 | 1132 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);) |
| 1133 { | |
| 1134 dse_optimize_stmt (&gsi); | |
| 1135 if (gsi_end_p (gsi)) | |
| 1136 gsi = gsi_last_bb (bb); | |
| 1137 else | |
| 1138 gsi_prev (&gsi); | |
| 1139 } | |
| 1140 return NULL; | |
| 0 | 1141 } |
| 1142 | |
| 111 | 1143 namespace { |
| 1144 | |
| 1145 const pass_data pass_data_dse = | |
| 0 | 1146 { |
| 111 | 1147 GIMPLE_PASS, /* type */ |
| 1148 "dse", /* name */ | |
| 1149 OPTGROUP_NONE, /* optinfo_flags */ | |
| 1150 TV_TREE_DSE, /* tv_id */ | |
| 1151 ( PROP_cfg | PROP_ssa ), /* properties_required */ | |
| 1152 0, /* properties_provided */ | |
| 1153 0, /* properties_destroyed */ | |
| 1154 0, /* todo_flags_start */ | |
| 1155 0, /* todo_flags_finish */ | |
| 1156 }; | |
| 0 | 1157 |
| 111 | 1158 class pass_dse : public gimple_opt_pass |
| 1159 { | |
| 1160 public: | |
| 1161 pass_dse (gcc::context *ctxt) | |
| 1162 : gimple_opt_pass (pass_data_dse, ctxt) | |
| 1163 {} | |
| 0 | 1164 |
| 111 | 1165 /* opt_pass methods: */ |
| 1166 opt_pass * clone () { return new pass_dse (m_ctxt); } | |
| 1167 virtual bool gate (function *) { return flag_tree_dse != 0; } | |
| 1168 virtual unsigned int execute (function *); | |
| 0 | 1169 |
| 111 | 1170 }; // class pass_dse |
| 1171 | |
| 1172 unsigned int | |
| 1173 pass_dse::execute (function *fun) | |
| 0 | 1174 { |
|
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
|
1175 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
|
1176 |
| 145 | 1177 renumber_gimple_stmt_uids (cfun); |
| 0 | 1178 |
| 1179 /* We might consider making this a property of each pass so that it | |
| 1180 can be [re]computed on an as-needed basis. Particularly since | |
| 1181 this pass could be seen as an extension of DCE which needs post | |
| 1182 dominators. */ | |
| 1183 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
|
1184 calculate_dominance_info (CDI_DOMINATORS); |
| 0 | 1185 |
| 1186 /* Dead store elimination is fundamentally a walk of the post-dominator | |
| 1187 tree and a backwards walk of statements within each block. */ | |
| 111 | 1188 dse_dom_walker (CDI_POST_DOMINATORS).walk (fun->cfg->x_exit_block_ptr); |
| 0 | 1189 |
|
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
|
1190 /* 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
|
1191 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
|
1192 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
|
1193 { |
|
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
|
1194 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
|
1195 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
|
1196 } |
|
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
|
1197 |
|
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
|
1198 BITMAP_FREE (need_eh_cleanup); |
| 111 | 1199 |
| 0 | 1200 /* For now, just wipe the post-dominator information. */ |
| 1201 free_dominance_info (CDI_POST_DOMINATORS); | |
| 1202 return 0; | |
| 1203 } | |
| 1204 | |
| 111 | 1205 } // anon namespace |
| 0 | 1206 |
| 111 | 1207 gimple_opt_pass * |
| 1208 make_pass_dse (gcc::context *ctxt) | |
| 0 | 1209 { |
| 111 | 1210 return new pass_dse (ctxt); |
| 1211 } |