Mercurial > hg > CbC > CbC_gcc
annotate gcc/postreload-gcse.c @ 63:b7f97abdc517 gcc-4.6-20100522
update gcc from gcc-4.5.0 to gcc-4.6
| author | ryoma <e075725@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Mon, 24 May 2010 12:47:05 +0900 |
| parents | 77e2b8dfacca |
| children | f6334be47118 |
| rev | line source |
|---|---|
| 0 | 1 /* Post reload partially redundant load elimination |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2010 |
| 0 | 3 Free Software Foundation, Inc. |
| 4 | |
| 5 This file is part of GCC. | |
| 6 | |
| 7 GCC is free software; you can redistribute it and/or modify it under | |
| 8 the terms of the GNU General Public License as published by the Free | |
| 9 Software Foundation; either version 3, or (at your option) any later | |
| 10 version. | |
| 11 | |
| 12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
| 13 WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| 15 for more details. | |
| 16 | |
| 17 You should have received a copy of the GNU General Public License | |
| 18 along with GCC; see the file COPYING3. If not see | |
| 19 <http://www.gnu.org/licenses/>. */ | |
| 20 | |
| 21 #include "config.h" | |
| 22 #include "system.h" | |
| 23 #include "coretypes.h" | |
| 24 #include "tm.h" | |
| 25 #include "toplev.h" | |
| 26 | |
| 27 #include "rtl.h" | |
| 28 #include "tree.h" | |
| 29 #include "tm_p.h" | |
| 30 #include "regs.h" | |
| 31 #include "hard-reg-set.h" | |
| 32 #include "flags.h" | |
| 33 #include "insn-config.h" | |
| 34 #include "recog.h" | |
| 35 #include "basic-block.h" | |
| 36 #include "output.h" | |
| 37 #include "function.h" | |
| 38 #include "expr.h" | |
| 39 #include "except.h" | |
| 40 #include "intl.h" | |
| 41 #include "obstack.h" | |
| 42 #include "hashtab.h" | |
| 43 #include "params.h" | |
| 44 #include "target.h" | |
| 45 #include "timevar.h" | |
| 46 #include "tree-pass.h" | |
| 47 #include "dbgcnt.h" | |
| 48 | |
| 49 /* The following code implements gcse after reload, the purpose of this | |
| 50 pass is to cleanup redundant loads generated by reload and other | |
| 51 optimizations that come after gcse. It searches for simple inter-block | |
| 52 redundancies and tries to eliminate them by adding moves and loads | |
| 53 in cold places. | |
| 54 | |
| 55 Perform partially redundant load elimination, try to eliminate redundant | |
| 56 loads created by the reload pass. We try to look for full or partial | |
| 57 redundant loads fed by one or more loads/stores in predecessor BBs, | |
| 58 and try adding loads to make them fully redundant. We also check if | |
| 59 it's worth adding loads to be able to delete the redundant load. | |
| 60 | |
| 61 Algorithm: | |
| 62 1. Build available expressions hash table: | |
| 63 For each load/store instruction, if the loaded/stored memory didn't | |
| 64 change until the end of the basic block add this memory expression to | |
| 65 the hash table. | |
| 66 2. Perform Redundancy elimination: | |
| 67 For each load instruction do the following: | |
| 68 perform partial redundancy elimination, check if it's worth adding | |
| 69 loads to make the load fully redundant. If so add loads and | |
| 70 register copies and delete the load. | |
| 71 3. Delete instructions made redundant in step 2. | |
| 72 | |
| 73 Future enhancement: | |
| 74 If the loaded register is used/defined between load and some store, | |
| 75 look for some other free register between load and all its stores, | |
| 76 and replace the load with a copy from this register to the loaded | |
| 77 register. | |
| 78 */ | |
| 79 | |
| 80 | |
| 81 /* Keep statistics of this pass. */ | |
| 82 static struct | |
| 83 { | |
| 84 int moves_inserted; | |
| 85 int copies_inserted; | |
| 86 int insns_deleted; | |
| 87 } stats; | |
| 88 | |
| 89 /* We need to keep a hash table of expressions. The table entries are of | |
| 90 type 'struct expr', and for each expression there is a single linked | |
| 91 list of occurrences. */ | |
| 92 | |
| 93 /* The table itself. */ | |
| 94 static htab_t expr_table; | |
| 95 | |
| 96 /* Expression elements in the hash table. */ | |
| 97 struct expr | |
| 98 { | |
| 99 /* The expression (SET_SRC for expressions, PATTERN for assignments). */ | |
| 100 rtx expr; | |
| 101 | |
| 102 /* The same hash for this entry. */ | |
| 103 hashval_t hash; | |
| 104 | |
| 105 /* List of available occurrence in basic blocks in the function. */ | |
| 106 struct occr *avail_occr; | |
| 107 }; | |
| 108 | |
| 109 static struct obstack expr_obstack; | |
| 110 | |
| 111 /* Occurrence of an expression. | |
| 112 There is at most one occurrence per basic block. If a pattern appears | |
| 113 more than once, the last appearance is used. */ | |
| 114 | |
| 115 struct occr | |
| 116 { | |
| 117 /* Next occurrence of this expression. */ | |
| 118 struct occr *next; | |
| 119 /* The insn that computes the expression. */ | |
| 120 rtx insn; | |
| 121 /* Nonzero if this [anticipatable] occurrence has been deleted. */ | |
| 122 char deleted_p; | |
| 123 }; | |
| 124 | |
| 125 static struct obstack occr_obstack; | |
| 126 | |
| 127 /* The following structure holds the information about the occurrences of | |
| 128 the redundant instructions. */ | |
| 129 struct unoccr | |
| 130 { | |
| 131 struct unoccr *next; | |
| 132 edge pred; | |
| 133 rtx insn; | |
| 134 }; | |
| 135 | |
| 136 static struct obstack unoccr_obstack; | |
| 137 | |
| 138 /* Array where each element is the CUID if the insn that last set the hard | |
| 139 register with the number of the element, since the start of the current | |
| 140 basic block. | |
| 141 | |
| 142 This array is used during the building of the hash table (step 1) to | |
| 143 determine if a reg is killed before the end of a basic block. | |
| 144 | |
| 145 It is also used when eliminating partial redundancies (step 2) to see | |
| 146 if a reg was modified since the start of a basic block. */ | |
| 147 static int *reg_avail_info; | |
| 148 | |
| 149 /* A list of insns that may modify memory within the current basic block. */ | |
| 150 struct modifies_mem | |
| 151 { | |
| 152 rtx insn; | |
| 153 struct modifies_mem *next; | |
| 154 }; | |
| 155 static struct modifies_mem *modifies_mem_list; | |
| 156 | |
| 157 /* The modifies_mem structs also go on an obstack, only this obstack is | |
| 158 freed each time after completing the analysis or transformations on | |
| 159 a basic block. So we allocate a dummy modifies_mem_obstack_bottom | |
| 160 object on the obstack to keep track of the bottom of the obstack. */ | |
| 161 static struct obstack modifies_mem_obstack; | |
| 162 static struct modifies_mem *modifies_mem_obstack_bottom; | |
| 163 | |
| 164 /* Mapping of insn UIDs to CUIDs. | |
| 165 CUIDs are like UIDs except they increase monotonically in each basic | |
| 166 block, have no gaps, and only apply to real insns. */ | |
| 167 static int *uid_cuid; | |
| 168 #define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)]) | |
| 169 | |
| 170 | |
| 171 /* Helpers for memory allocation/freeing. */ | |
| 172 static void alloc_mem (void); | |
| 173 static void free_mem (void); | |
| 174 | |
| 175 /* Support for hash table construction and transformations. */ | |
| 176 static bool oprs_unchanged_p (rtx, rtx, bool); | |
| 177 static void record_last_reg_set_info (rtx, rtx); | |
| 178 static void record_last_reg_set_info_regno (rtx, int); | |
| 179 static void record_last_mem_set_info (rtx); | |
| 180 static void record_last_set_info (rtx, const_rtx, void *); | |
| 181 static void record_opr_changes (rtx); | |
| 182 | |
| 183 static void find_mem_conflicts (rtx, const_rtx, void *); | |
| 184 static int load_killed_in_block_p (int, rtx, bool); | |
| 185 static void reset_opr_set_tables (void); | |
| 186 | |
| 187 /* Hash table support. */ | |
| 188 static hashval_t hash_expr (rtx, int *); | |
| 189 static hashval_t hash_expr_for_htab (const void *); | |
| 190 static int expr_equiv_p (const void *, const void *); | |
| 191 static void insert_expr_in_table (rtx, rtx); | |
| 192 static struct expr *lookup_expr_in_table (rtx); | |
| 193 static int dump_hash_table_entry (void **, void *); | |
| 194 static void dump_hash_table (FILE *); | |
| 195 | |
| 196 /* Helpers for eliminate_partially_redundant_load. */ | |
| 197 static bool reg_killed_on_edge (rtx, edge); | |
| 198 static bool reg_used_on_edge (rtx, edge); | |
| 199 | |
| 200 static rtx get_avail_load_store_reg (rtx); | |
| 201 | |
| 202 static bool bb_has_well_behaved_predecessors (basic_block); | |
| 203 static struct occr* get_bb_avail_insn (basic_block, struct occr *); | |
| 204 static void hash_scan_set (rtx); | |
| 205 static void compute_hash_table (void); | |
| 206 | |
| 207 /* The work horses of this pass. */ | |
| 208 static void eliminate_partially_redundant_load (basic_block, | |
| 209 rtx, | |
| 210 struct expr *); | |
| 211 static void eliminate_partially_redundant_loads (void); | |
| 212 | |
| 213 | |
| 214 /* Allocate memory for the CUID mapping array and register/memory | |
| 215 tracking tables. */ | |
| 216 | |
| 217 static void | |
| 218 alloc_mem (void) | |
| 219 { | |
| 220 int i; | |
| 221 basic_block bb; | |
| 222 rtx insn; | |
| 223 | |
| 224 /* Find the largest UID and create a mapping from UIDs to CUIDs. */ | |
| 225 uid_cuid = XCNEWVEC (int, get_max_uid () + 1); | |
| 226 i = 1; | |
| 227 FOR_EACH_BB (bb) | |
| 228 FOR_BB_INSNS (bb, insn) | |
| 229 { | |
| 230 if (INSN_P (insn)) | |
| 231 uid_cuid[INSN_UID (insn)] = i++; | |
| 232 else | |
| 233 uid_cuid[INSN_UID (insn)] = i; | |
| 234 } | |
| 235 | |
| 236 /* Allocate the available expressions hash table. We don't want to | |
| 237 make the hash table too small, but unnecessarily making it too large | |
| 238 also doesn't help. The i/4 is a gcse.c relic, and seems like a | |
| 239 reasonable choice. */ | |
| 240 expr_table = htab_create (MAX (i / 4, 13), | |
| 241 hash_expr_for_htab, expr_equiv_p, NULL); | |
| 242 | |
| 243 /* We allocate everything on obstacks because we often can roll back | |
| 244 the whole obstack to some point. Freeing obstacks is very fast. */ | |
| 245 gcc_obstack_init (&expr_obstack); | |
| 246 gcc_obstack_init (&occr_obstack); | |
| 247 gcc_obstack_init (&unoccr_obstack); | |
| 248 gcc_obstack_init (&modifies_mem_obstack); | |
| 249 | |
| 250 /* Working array used to track the last set for each register | |
| 251 in the current block. */ | |
| 252 reg_avail_info = (int *) xmalloc (FIRST_PSEUDO_REGISTER * sizeof (int)); | |
| 253 | |
| 254 /* Put a dummy modifies_mem object on the modifies_mem_obstack, so we | |
| 255 can roll it back in reset_opr_set_tables. */ | |
| 256 modifies_mem_obstack_bottom = | |
| 257 (struct modifies_mem *) obstack_alloc (&modifies_mem_obstack, | |
| 258 sizeof (struct modifies_mem)); | |
| 259 } | |
| 260 | |
| 261 /* Free memory allocated by alloc_mem. */ | |
| 262 | |
| 263 static void | |
| 264 free_mem (void) | |
| 265 { | |
| 266 free (uid_cuid); | |
| 267 | |
| 268 htab_delete (expr_table); | |
| 269 | |
| 270 obstack_free (&expr_obstack, NULL); | |
| 271 obstack_free (&occr_obstack, NULL); | |
| 272 obstack_free (&unoccr_obstack, NULL); | |
| 273 obstack_free (&modifies_mem_obstack, NULL); | |
| 274 | |
| 275 free (reg_avail_info); | |
| 276 } | |
| 277 | |
| 278 | |
| 279 /* Hash expression X. | |
| 280 DO_NOT_RECORD_P is a boolean indicating if a volatile operand is found | |
| 281 or if the expression contains something we don't want to insert in the | |
| 282 table. */ | |
| 283 | |
| 284 static hashval_t | |
| 285 hash_expr (rtx x, int *do_not_record_p) | |
| 286 { | |
| 287 *do_not_record_p = 0; | |
| 288 return hash_rtx (x, GET_MODE (x), do_not_record_p, | |
| 289 NULL, /*have_reg_qty=*/false); | |
| 290 } | |
| 291 | |
| 292 /* Callback for hashtab. | |
| 293 Return the hash value for expression EXP. We don't actually hash | |
| 294 here, we just return the cached hash value. */ | |
| 295 | |
| 296 static hashval_t | |
| 297 hash_expr_for_htab (const void *expp) | |
| 298 { | |
| 299 const struct expr *const exp = (const struct expr *) expp; | |
| 300 return exp->hash; | |
| 301 } | |
| 302 | |
| 303 /* Callback for hashtab. | |
| 304 Return nonzero if exp1 is equivalent to exp2. */ | |
| 305 | |
| 306 static int | |
| 307 expr_equiv_p (const void *exp1p, const void *exp2p) | |
| 308 { | |
| 309 const struct expr *const exp1 = (const struct expr *) exp1p; | |
| 310 const struct expr *const exp2 = (const struct expr *) exp2p; | |
| 311 int equiv_p = exp_equiv_p (exp1->expr, exp2->expr, 0, true); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
312 |
| 0 | 313 gcc_assert (!equiv_p || exp1->hash == exp2->hash); |
| 314 return equiv_p; | |
| 315 } | |
| 316 | |
| 317 | |
| 318 /* Insert expression X in INSN in the hash TABLE. | |
| 319 If it is already present, record it as the last occurrence in INSN's | |
| 320 basic block. */ | |
| 321 | |
| 322 static void | |
| 323 insert_expr_in_table (rtx x, rtx insn) | |
| 324 { | |
| 325 int do_not_record_p; | |
| 326 hashval_t hash; | |
| 327 struct expr *cur_expr, **slot; | |
| 328 struct occr *avail_occr, *last_occr = NULL; | |
| 329 | |
| 330 hash = hash_expr (x, &do_not_record_p); | |
| 331 | |
| 332 /* Do not insert expression in the table if it contains volatile operands, | |
| 333 or if hash_expr determines the expression is something we don't want | |
| 334 to or can't handle. */ | |
| 335 if (do_not_record_p) | |
| 336 return; | |
| 337 | |
| 338 /* We anticipate that redundant expressions are rare, so for convenience | |
| 339 allocate a new hash table element here already and set its fields. | |
| 340 If we don't do this, we need a hack with a static struct expr. Anyway, | |
| 341 obstack_free is really fast and one more obstack_alloc doesn't hurt if | |
| 342 we're going to see more expressions later on. */ | |
| 343 cur_expr = (struct expr *) obstack_alloc (&expr_obstack, | |
| 344 sizeof (struct expr)); | |
| 345 cur_expr->expr = x; | |
| 346 cur_expr->hash = hash; | |
| 347 cur_expr->avail_occr = NULL; | |
| 348 | |
| 349 slot = (struct expr **) htab_find_slot_with_hash (expr_table, cur_expr, | |
| 350 hash, INSERT); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
351 |
| 0 | 352 if (! (*slot)) |
| 353 /* The expression isn't found, so insert it. */ | |
| 354 *slot = cur_expr; | |
| 355 else | |
| 356 { | |
| 357 /* The expression is already in the table, so roll back the | |
| 358 obstack and use the existing table entry. */ | |
| 359 obstack_free (&expr_obstack, cur_expr); | |
| 360 cur_expr = *slot; | |
| 361 } | |
| 362 | |
| 363 /* Search for another occurrence in the same basic block. */ | |
| 364 avail_occr = cur_expr->avail_occr; | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
365 while (avail_occr |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
366 && BLOCK_FOR_INSN (avail_occr->insn) != BLOCK_FOR_INSN (insn)) |
| 0 | 367 { |
| 368 /* If an occurrence isn't found, save a pointer to the end of | |
| 369 the list. */ | |
| 370 last_occr = avail_occr; | |
| 371 avail_occr = avail_occr->next; | |
| 372 } | |
| 373 | |
| 374 if (avail_occr) | |
| 375 /* Found another instance of the expression in the same basic block. | |
| 376 Prefer this occurrence to the currently recorded one. We want | |
| 377 the last one in the block and the block is scanned from start | |
| 378 to end. */ | |
| 379 avail_occr->insn = insn; | |
| 380 else | |
| 381 { | |
| 382 /* First occurrence of this expression in this basic block. */ | |
| 383 avail_occr = (struct occr *) obstack_alloc (&occr_obstack, | |
| 384 sizeof (struct occr)); | |
| 385 | |
| 386 /* First occurrence of this expression in any block? */ | |
| 387 if (cur_expr->avail_occr == NULL) | |
| 388 cur_expr->avail_occr = avail_occr; | |
| 389 else | |
| 390 last_occr->next = avail_occr; | |
| 391 | |
| 392 avail_occr->insn = insn; | |
| 393 avail_occr->next = NULL; | |
| 394 avail_occr->deleted_p = 0; | |
| 395 } | |
| 396 } | |
| 397 | |
| 398 | |
| 399 /* Lookup pattern PAT in the expression hash table. | |
| 400 The result is a pointer to the table entry, or NULL if not found. */ | |
| 401 | |
| 402 static struct expr * | |
| 403 lookup_expr_in_table (rtx pat) | |
| 404 { | |
| 405 int do_not_record_p; | |
| 406 struct expr **slot, *tmp_expr; | |
| 407 hashval_t hash = hash_expr (pat, &do_not_record_p); | |
| 408 | |
| 409 if (do_not_record_p) | |
| 410 return NULL; | |
| 411 | |
| 412 tmp_expr = (struct expr *) obstack_alloc (&expr_obstack, | |
| 413 sizeof (struct expr)); | |
| 414 tmp_expr->expr = pat; | |
| 415 tmp_expr->hash = hash; | |
| 416 tmp_expr->avail_occr = NULL; | |
| 417 | |
| 418 slot = (struct expr **) htab_find_slot_with_hash (expr_table, tmp_expr, | |
| 419 hash, INSERT); | |
| 420 obstack_free (&expr_obstack, tmp_expr); | |
| 421 | |
| 422 if (!slot) | |
| 423 return NULL; | |
| 424 else | |
| 425 return (*slot); | |
| 426 } | |
| 427 | |
| 428 | |
| 429 /* Dump all expressions and occurrences that are currently in the | |
| 430 expression hash table to FILE. */ | |
| 431 | |
| 432 /* This helper is called via htab_traverse. */ | |
| 433 static int | |
| 434 dump_hash_table_entry (void **slot, void *filep) | |
| 435 { | |
| 436 struct expr *expr = (struct expr *) *slot; | |
| 437 FILE *file = (FILE *) filep; | |
| 438 struct occr *occr; | |
| 439 | |
| 440 fprintf (file, "expr: "); | |
| 441 print_rtl (file, expr->expr); | |
| 442 fprintf (file,"\nhashcode: %u\n", expr->hash); | |
| 443 fprintf (file,"list of occurrences:\n"); | |
| 444 occr = expr->avail_occr; | |
| 445 while (occr) | |
| 446 { | |
| 447 rtx insn = occr->insn; | |
| 448 print_rtl_single (file, insn); | |
| 449 fprintf (file, "\n"); | |
| 450 occr = occr->next; | |
| 451 } | |
| 452 fprintf (file, "\n"); | |
| 453 return 1; | |
| 454 } | |
| 455 | |
| 456 static void | |
| 457 dump_hash_table (FILE *file) | |
| 458 { | |
| 459 fprintf (file, "\n\nexpression hash table\n"); | |
| 460 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n", | |
| 461 (long) htab_size (expr_table), | |
| 462 (long) htab_elements (expr_table), | |
| 463 htab_collisions (expr_table)); | |
| 464 if (htab_elements (expr_table) > 0) | |
| 465 { | |
| 466 fprintf (file, "\n\ntable entries:\n"); | |
| 467 htab_traverse (expr_table, dump_hash_table_entry, file); | |
| 468 } | |
| 469 fprintf (file, "\n"); | |
| 470 } | |
| 471 | |
| 472 /* Return true if register X is recorded as being set by an instruction | |
| 473 whose CUID is greater than the one given. */ | |
| 474 | |
| 475 static bool | |
| 476 reg_changed_after_insn_p (rtx x, int cuid) | |
| 477 { | |
| 478 unsigned int regno, end_regno; | |
| 479 | |
| 480 regno = REGNO (x); | |
| 481 end_regno = END_HARD_REGNO (x); | |
| 482 do | |
| 483 if (reg_avail_info[regno] > cuid) | |
| 484 return true; | |
| 485 while (++regno < end_regno); | |
| 486 return false; | |
| 487 } | |
| 488 | |
| 489 /* Return nonzero if the operands of expression X are unchanged | |
| 490 1) from the start of INSN's basic block up to but not including INSN | |
| 491 if AFTER_INSN is false, or | |
| 492 2) from INSN to the end of INSN's basic block if AFTER_INSN is true. */ | |
| 493 | |
| 494 static bool | |
| 495 oprs_unchanged_p (rtx x, rtx insn, bool after_insn) | |
| 496 { | |
| 497 int i, j; | |
| 498 enum rtx_code code; | |
| 499 const char *fmt; | |
| 500 | |
| 501 if (x == 0) | |
| 502 return 1; | |
| 503 | |
| 504 code = GET_CODE (x); | |
| 505 switch (code) | |
| 506 { | |
| 507 case REG: | |
| 508 /* We are called after register allocation. */ | |
| 509 gcc_assert (REGNO (x) < FIRST_PSEUDO_REGISTER); | |
| 510 if (after_insn) | |
| 511 return !reg_changed_after_insn_p (x, INSN_CUID (insn) - 1); | |
| 512 else | |
| 513 return !reg_changed_after_insn_p (x, 0); | |
| 514 | |
| 515 case MEM: | |
| 516 if (load_killed_in_block_p (INSN_CUID (insn), x, after_insn)) | |
| 517 return 0; | |
| 518 else | |
| 519 return oprs_unchanged_p (XEXP (x, 0), insn, after_insn); | |
| 520 | |
| 521 case PC: | |
| 522 case CC0: /*FIXME*/ | |
| 523 case CONST: | |
| 524 case CONST_INT: | |
| 525 case CONST_DOUBLE: | |
| 526 case CONST_FIXED: | |
| 527 case CONST_VECTOR: | |
| 528 case SYMBOL_REF: | |
| 529 case LABEL_REF: | |
| 530 case ADDR_VEC: | |
| 531 case ADDR_DIFF_VEC: | |
| 532 return 1; | |
| 533 | |
| 534 case PRE_DEC: | |
| 535 case PRE_INC: | |
| 536 case POST_DEC: | |
| 537 case POST_INC: | |
| 538 case PRE_MODIFY: | |
| 539 case POST_MODIFY: | |
| 540 if (after_insn) | |
| 541 return 0; | |
| 542 break; | |
| 543 | |
| 544 default: | |
| 545 break; | |
| 546 } | |
| 547 | |
| 548 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--) | |
| 549 { | |
| 550 if (fmt[i] == 'e') | |
| 551 { | |
| 552 if (! oprs_unchanged_p (XEXP (x, i), insn, after_insn)) | |
| 553 return 0; | |
| 554 } | |
| 555 else if (fmt[i] == 'E') | |
| 556 for (j = 0; j < XVECLEN (x, i); j++) | |
| 557 if (! oprs_unchanged_p (XVECEXP (x, i, j), insn, after_insn)) | |
| 558 return 0; | |
| 559 } | |
| 560 | |
| 561 return 1; | |
| 562 } | |
| 563 | |
| 564 | |
| 565 /* Used for communication between find_mem_conflicts and | |
| 566 load_killed_in_block_p. Nonzero if find_mem_conflicts finds a | |
| 567 conflict between two memory references. | |
| 568 This is a bit of a hack to work around the limitations of note_stores. */ | |
| 569 static int mems_conflict_p; | |
| 570 | |
| 571 /* DEST is the output of an instruction. If it is a memory reference, and | |
| 572 possibly conflicts with the load found in DATA, then set mems_conflict_p | |
| 573 to a nonzero value. */ | |
| 574 | |
| 575 static void | |
| 576 find_mem_conflicts (rtx dest, const_rtx setter ATTRIBUTE_UNUSED, | |
| 577 void *data) | |
| 578 { | |
| 579 rtx mem_op = (rtx) data; | |
| 580 | |
| 581 while (GET_CODE (dest) == SUBREG | |
| 582 || GET_CODE (dest) == ZERO_EXTRACT | |
| 583 || GET_CODE (dest) == STRICT_LOW_PART) | |
| 584 dest = XEXP (dest, 0); | |
| 585 | |
| 586 /* If DEST is not a MEM, then it will not conflict with the load. Note | |
| 587 that function calls are assumed to clobber memory, but are handled | |
| 588 elsewhere. */ | |
| 589 if (! MEM_P (dest)) | |
| 590 return; | |
| 591 | |
| 592 if (true_dependence (dest, GET_MODE (dest), mem_op, | |
| 593 rtx_addr_varies_p)) | |
| 594 mems_conflict_p = 1; | |
| 595 } | |
| 596 | |
| 597 | |
| 598 /* Return nonzero if the expression in X (a memory reference) is killed | |
| 599 in the current basic block before (if AFTER_INSN is false) or after | |
| 600 (if AFTER_INSN is true) the insn with the CUID in UID_LIMIT. | |
| 601 | |
| 602 This function assumes that the modifies_mem table is flushed when | |
| 603 the hash table construction or redundancy elimination phases start | |
| 604 processing a new basic block. */ | |
| 605 | |
| 606 static int | |
| 607 load_killed_in_block_p (int uid_limit, rtx x, bool after_insn) | |
| 608 { | |
| 609 struct modifies_mem *list_entry = modifies_mem_list; | |
| 610 | |
| 611 while (list_entry) | |
| 612 { | |
| 613 rtx setter = list_entry->insn; | |
| 614 | |
| 615 /* Ignore entries in the list that do not apply. */ | |
| 616 if ((after_insn | |
| 617 && INSN_CUID (setter) < uid_limit) | |
| 618 || (! after_insn | |
| 619 && INSN_CUID (setter) > uid_limit)) | |
| 620 { | |
| 621 list_entry = list_entry->next; | |
| 622 continue; | |
| 623 } | |
| 624 | |
| 625 /* If SETTER is a call everything is clobbered. Note that calls | |
| 626 to pure functions are never put on the list, so we need not | |
| 627 worry about them. */ | |
| 628 if (CALL_P (setter)) | |
| 629 return 1; | |
| 630 | |
| 631 /* SETTER must be an insn of some kind that sets memory. Call | |
| 632 note_stores to examine each hunk of memory that is modified. | |
| 633 It will set mems_conflict_p to nonzero if there may be a | |
| 634 conflict between X and SETTER. */ | |
| 635 mems_conflict_p = 0; | |
| 636 note_stores (PATTERN (setter), find_mem_conflicts, x); | |
| 637 if (mems_conflict_p) | |
| 638 return 1; | |
| 639 | |
| 640 list_entry = list_entry->next; | |
| 641 } | |
| 642 return 0; | |
| 643 } | |
| 644 | |
| 645 | |
| 646 /* Record register first/last/block set information for REGNO in INSN. */ | |
| 647 | |
| 648 static inline void | |
| 649 record_last_reg_set_info (rtx insn, rtx reg) | |
| 650 { | |
| 651 unsigned int regno, end_regno; | |
| 652 | |
| 653 regno = REGNO (reg); | |
| 654 end_regno = END_HARD_REGNO (reg); | |
| 655 do | |
| 656 reg_avail_info[regno] = INSN_CUID (insn); | |
| 657 while (++regno < end_regno); | |
| 658 } | |
| 659 | |
| 660 static inline void | |
| 661 record_last_reg_set_info_regno (rtx insn, int regno) | |
| 662 { | |
| 663 reg_avail_info[regno] = INSN_CUID (insn); | |
| 664 } | |
| 665 | |
| 666 | |
| 667 /* Record memory modification information for INSN. We do not actually care | |
| 668 about the memory location(s) that are set, or even how they are set (consider | |
| 669 a CALL_INSN). We merely need to record which insns modify memory. */ | |
| 670 | |
| 671 static void | |
| 672 record_last_mem_set_info (rtx insn) | |
| 673 { | |
| 674 struct modifies_mem *list_entry; | |
| 675 | |
| 676 list_entry = (struct modifies_mem *) obstack_alloc (&modifies_mem_obstack, | |
| 677 sizeof (struct modifies_mem)); | |
| 678 list_entry->insn = insn; | |
| 679 list_entry->next = modifies_mem_list; | |
| 680 modifies_mem_list = list_entry; | |
| 681 } | |
| 682 | |
| 683 /* Called from compute_hash_table via note_stores to handle one | |
| 684 SET or CLOBBER in an insn. DATA is really the instruction in which | |
| 685 the SET is taking place. */ | |
| 686 | |
| 687 static void | |
| 688 record_last_set_info (rtx dest, const_rtx setter ATTRIBUTE_UNUSED, void *data) | |
| 689 { | |
| 690 rtx last_set_insn = (rtx) data; | |
| 691 | |
| 692 if (GET_CODE (dest) == SUBREG) | |
| 693 dest = SUBREG_REG (dest); | |
| 694 | |
| 695 if (REG_P (dest)) | |
| 696 record_last_reg_set_info (last_set_insn, dest); | |
| 697 else if (MEM_P (dest)) | |
| 698 { | |
| 699 /* Ignore pushes, they don't clobber memory. They may still | |
| 700 clobber the stack pointer though. Some targets do argument | |
| 701 pushes without adding REG_INC notes. See e.g. PR25196, | |
| 702 where a pushsi2 on i386 doesn't have REG_INC notes. Note | |
| 703 such changes here too. */ | |
| 704 if (! push_operand (dest, GET_MODE (dest))) | |
| 705 record_last_mem_set_info (last_set_insn); | |
| 706 else | |
| 707 record_last_reg_set_info_regno (last_set_insn, STACK_POINTER_REGNUM); | |
| 708 } | |
| 709 } | |
| 710 | |
| 711 | |
| 712 /* Reset tables used to keep track of what's still available since the | |
| 713 start of the block. */ | |
| 714 | |
| 715 static void | |
| 716 reset_opr_set_tables (void) | |
| 717 { | |
| 718 memset (reg_avail_info, 0, FIRST_PSEUDO_REGISTER * sizeof (int)); | |
| 719 obstack_free (&modifies_mem_obstack, modifies_mem_obstack_bottom); | |
| 720 modifies_mem_list = NULL; | |
| 721 } | |
| 722 | |
| 723 | |
| 724 /* Record things set by INSN. | |
| 725 This data is used by oprs_unchanged_p. */ | |
| 726 | |
| 727 static void | |
| 728 record_opr_changes (rtx insn) | |
| 729 { | |
| 730 rtx note; | |
| 731 | |
| 732 /* Find all stores and record them. */ | |
| 733 note_stores (PATTERN (insn), record_last_set_info, insn); | |
| 734 | |
| 735 /* Also record autoincremented REGs for this insn as changed. */ | |
| 736 for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) | |
| 737 if (REG_NOTE_KIND (note) == REG_INC) | |
| 738 record_last_reg_set_info (insn, XEXP (note, 0)); | |
| 739 | |
| 740 /* Finally, if this is a call, record all call clobbers. */ | |
| 741 if (CALL_P (insn)) | |
| 742 { | |
| 743 unsigned int regno; | |
| 744 rtx link, x; | |
| 745 | |
| 746 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++) | |
| 747 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno)) | |
| 748 record_last_reg_set_info_regno (insn, regno); | |
| 749 | |
| 750 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1)) | |
| 751 if (GET_CODE (XEXP (link, 0)) == CLOBBER) | |
| 752 { | |
| 753 x = XEXP (XEXP (link, 0), 0); | |
| 754 if (REG_P (x)) | |
| 755 { | |
| 756 gcc_assert (HARD_REGISTER_P (x)); | |
| 757 record_last_reg_set_info (insn, x); | |
| 758 } | |
| 759 } | |
| 760 | |
| 761 if (! RTL_CONST_OR_PURE_CALL_P (insn)) | |
| 762 record_last_mem_set_info (insn); | |
| 763 } | |
| 764 } | |
| 765 | |
| 766 | |
| 767 /* Scan the pattern of INSN and add an entry to the hash TABLE. | |
| 768 After reload we are interested in loads/stores only. */ | |
| 769 | |
| 770 static void | |
| 771 hash_scan_set (rtx insn) | |
| 772 { | |
| 773 rtx pat = PATTERN (insn); | |
| 774 rtx src = SET_SRC (pat); | |
| 775 rtx dest = SET_DEST (pat); | |
| 776 | |
| 777 /* We are only interested in loads and stores. */ | |
| 778 if (! MEM_P (src) && ! MEM_P (dest)) | |
| 779 return; | |
| 780 | |
| 781 /* Don't mess with jumps and nops. */ | |
| 782 if (JUMP_P (insn) || set_noop_p (pat)) | |
| 783 return; | |
| 784 | |
| 785 if (REG_P (dest)) | |
| 786 { | |
| 787 if (/* Don't CSE something if we can't do a reg/reg copy. */ | |
| 788 can_copy_p (GET_MODE (dest)) | |
| 789 /* Is SET_SRC something we want to gcse? */ | |
| 790 && general_operand (src, GET_MODE (src)) | |
| 791 #ifdef STACK_REGS | |
| 792 /* Never consider insns touching the register stack. It may | |
| 793 create situations that reg-stack cannot handle (e.g. a stack | |
| 794 register live across an abnormal edge). */ | |
| 795 && (REGNO (dest) < FIRST_STACK_REG || REGNO (dest) > LAST_STACK_REG) | |
| 796 #endif | |
| 797 /* An expression is not available if its operands are | |
| 798 subsequently modified, including this insn. */ | |
| 799 && oprs_unchanged_p (src, insn, true)) | |
| 800 { | |
| 801 insert_expr_in_table (src, insn); | |
| 802 } | |
| 803 } | |
| 804 else if (REG_P (src)) | |
| 805 { | |
| 806 /* Only record sets of pseudo-regs in the hash table. */ | |
| 807 if (/* Don't CSE something if we can't do a reg/reg copy. */ | |
| 808 can_copy_p (GET_MODE (src)) | |
| 809 /* Is SET_DEST something we want to gcse? */ | |
| 810 && general_operand (dest, GET_MODE (dest)) | |
| 811 #ifdef STACK_REGS | |
| 812 /* As above for STACK_REGS. */ | |
| 813 && (REGNO (src) < FIRST_STACK_REG || REGNO (src) > LAST_STACK_REG) | |
| 814 #endif | |
| 815 && ! (flag_float_store && FLOAT_MODE_P (GET_MODE (dest))) | |
| 816 /* Check if the memory expression is killed after insn. */ | |
| 817 && ! load_killed_in_block_p (INSN_CUID (insn) + 1, dest, true) | |
| 818 && oprs_unchanged_p (XEXP (dest, 0), insn, true)) | |
| 819 { | |
| 820 insert_expr_in_table (dest, insn); | |
| 821 } | |
| 822 } | |
| 823 } | |
| 824 | |
| 825 | |
| 826 /* Create hash table of memory expressions available at end of basic | |
| 827 blocks. Basically you should think of this hash table as the | |
| 828 representation of AVAIL_OUT. This is the set of expressions that | |
| 829 is generated in a basic block and not killed before the end of the | |
| 830 same basic block. Notice that this is really a local computation. */ | |
| 831 | |
| 832 static void | |
| 833 compute_hash_table (void) | |
| 834 { | |
| 835 basic_block bb; | |
| 836 | |
| 837 FOR_EACH_BB (bb) | |
| 838 { | |
| 839 rtx insn; | |
| 840 | |
| 841 /* First pass over the instructions records information used to | |
| 842 determine when registers and memory are last set. | |
| 843 Since we compute a "local" AVAIL_OUT, reset the tables that | |
| 844 help us keep track of what has been modified since the start | |
| 845 of the block. */ | |
| 846 reset_opr_set_tables (); | |
| 847 FOR_BB_INSNS (bb, insn) | |
| 848 { | |
| 849 if (INSN_P (insn)) | |
| 850 record_opr_changes (insn); | |
| 851 } | |
| 852 | |
| 853 /* The next pass actually builds the hash table. */ | |
| 854 FOR_BB_INSNS (bb, insn) | |
| 855 if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == SET) | |
| 856 hash_scan_set (insn); | |
| 857 } | |
| 858 } | |
| 859 | |
| 860 | |
| 861 /* Check if register REG is killed in any insn waiting to be inserted on | |
| 862 edge E. This function is required to check that our data flow analysis | |
| 863 is still valid prior to commit_edge_insertions. */ | |
| 864 | |
| 865 static bool | |
| 866 reg_killed_on_edge (rtx reg, edge e) | |
| 867 { | |
| 868 rtx insn; | |
| 869 | |
| 870 for (insn = e->insns.r; insn; insn = NEXT_INSN (insn)) | |
| 871 if (INSN_P (insn) && reg_set_p (reg, insn)) | |
| 872 return true; | |
| 873 | |
| 874 return false; | |
| 875 } | |
| 876 | |
| 877 /* Similar to above - check if register REG is used in any insn waiting | |
| 878 to be inserted on edge E. | |
| 879 Assumes no such insn can be a CALL_INSN; if so call reg_used_between_p | |
| 880 with PREV(insn),NEXT(insn) instead of calling reg_overlap_mentioned_p. */ | |
| 881 | |
| 882 static bool | |
| 883 reg_used_on_edge (rtx reg, edge e) | |
| 884 { | |
| 885 rtx insn; | |
| 886 | |
| 887 for (insn = e->insns.r; insn; insn = NEXT_INSN (insn)) | |
| 888 if (INSN_P (insn) && reg_overlap_mentioned_p (reg, PATTERN (insn))) | |
| 889 return true; | |
| 890 | |
| 891 return false; | |
| 892 } | |
| 893 | |
| 894 /* Return the loaded/stored register of a load/store instruction. */ | |
| 895 | |
| 896 static rtx | |
| 897 get_avail_load_store_reg (rtx insn) | |
| 898 { | |
| 899 if (REG_P (SET_DEST (PATTERN (insn)))) | |
| 900 /* A load. */ | |
| 901 return SET_DEST(PATTERN(insn)); | |
| 902 else | |
| 903 { | |
| 904 /* A store. */ | |
| 905 gcc_assert (REG_P (SET_SRC (PATTERN (insn)))); | |
| 906 return SET_SRC (PATTERN (insn)); | |
| 907 } | |
| 908 } | |
| 909 | |
| 910 /* Return nonzero if the predecessors of BB are "well behaved". */ | |
| 911 | |
| 912 static bool | |
| 913 bb_has_well_behaved_predecessors (basic_block bb) | |
| 914 { | |
| 915 edge pred; | |
| 916 edge_iterator ei; | |
| 917 | |
| 918 if (EDGE_COUNT (bb->preds) == 0) | |
| 919 return false; | |
| 920 | |
| 921 FOR_EACH_EDGE (pred, ei, bb->preds) | |
| 922 { | |
| 923 if ((pred->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (pred)) | |
| 924 return false; | |
| 925 | |
| 926 if (JUMP_TABLE_DATA_P (BB_END (pred->src))) | |
| 927 return false; | |
| 928 } | |
| 929 return true; | |
| 930 } | |
| 931 | |
| 932 | |
| 933 /* Search for the occurrences of expression in BB. */ | |
| 934 | |
| 935 static struct occr* | |
| 936 get_bb_avail_insn (basic_block bb, struct occr *occr) | |
| 937 { | |
| 938 for (; occr != NULL; occr = occr->next) | |
| 939 if (BLOCK_FOR_INSN (occr->insn) == bb) | |
| 940 return occr; | |
| 941 return NULL; | |
| 942 } | |
| 943 | |
| 944 | |
| 945 /* This handles the case where several stores feed a partially redundant | |
| 946 load. It checks if the redundancy elimination is possible and if it's | |
| 947 worth it. | |
| 948 | |
| 949 Redundancy elimination is possible if, | |
| 950 1) None of the operands of an insn have been modified since the start | |
| 951 of the current basic block. | |
| 952 2) In any predecessor of the current basic block, the same expression | |
| 953 is generated. | |
| 954 | |
| 955 See the function body for the heuristics that determine if eliminating | |
| 956 a redundancy is also worth doing, assuming it is possible. */ | |
| 957 | |
| 958 static void | |
| 959 eliminate_partially_redundant_load (basic_block bb, rtx insn, | |
| 960 struct expr *expr) | |
| 961 { | |
| 962 edge pred; | |
| 963 rtx avail_insn = NULL_RTX; | |
| 964 rtx avail_reg; | |
| 965 rtx dest, pat; | |
| 966 struct occr *a_occr; | |
| 967 struct unoccr *occr, *avail_occrs = NULL; | |
| 968 struct unoccr *unoccr, *unavail_occrs = NULL, *rollback_unoccr = NULL; | |
| 969 int npred_ok = 0; | |
| 970 gcov_type ok_count = 0; /* Redundant load execution count. */ | |
| 971 gcov_type critical_count = 0; /* Execution count of critical edges. */ | |
| 972 edge_iterator ei; | |
| 973 bool critical_edge_split = false; | |
| 974 | |
| 975 /* The execution count of the loads to be added to make the | |
| 976 load fully redundant. */ | |
| 977 gcov_type not_ok_count = 0; | |
| 978 basic_block pred_bb; | |
| 979 | |
| 980 pat = PATTERN (insn); | |
| 981 dest = SET_DEST (pat); | |
| 982 | |
| 983 /* Check that the loaded register is not used, set, or killed from the | |
| 984 beginning of the block. */ | |
| 985 if (reg_changed_after_insn_p (dest, 0) | |
| 986 || reg_used_between_p (dest, PREV_INSN (BB_HEAD (bb)), insn)) | |
| 987 return; | |
| 988 | |
| 989 /* Check potential for replacing load with copy for predecessors. */ | |
| 990 FOR_EACH_EDGE (pred, ei, bb->preds) | |
| 991 { | |
| 992 rtx next_pred_bb_end; | |
| 993 | |
| 994 avail_insn = NULL_RTX; | |
| 995 avail_reg = NULL_RTX; | |
| 996 pred_bb = pred->src; | |
| 997 next_pred_bb_end = NEXT_INSN (BB_END (pred_bb)); | |
| 998 for (a_occr = get_bb_avail_insn (pred_bb, expr->avail_occr); a_occr; | |
| 999 a_occr = get_bb_avail_insn (pred_bb, a_occr->next)) | |
| 1000 { | |
| 1001 /* Check if the loaded register is not used. */ | |
| 1002 avail_insn = a_occr->insn; | |
| 1003 avail_reg = get_avail_load_store_reg (avail_insn); | |
| 1004 gcc_assert (avail_reg); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1005 |
| 0 | 1006 /* Make sure we can generate a move from register avail_reg to |
| 1007 dest. */ | |
| 1008 extract_insn (gen_move_insn (copy_rtx (dest), | |
| 1009 copy_rtx (avail_reg))); | |
| 1010 if (! constrain_operands (1) | |
| 1011 || reg_killed_on_edge (avail_reg, pred) | |
| 1012 || reg_used_on_edge (dest, pred)) | |
| 1013 { | |
| 1014 avail_insn = NULL; | |
| 1015 continue; | |
| 1016 } | |
| 1017 if (!reg_set_between_p (avail_reg, avail_insn, next_pred_bb_end)) | |
| 1018 /* AVAIL_INSN remains non-null. */ | |
| 1019 break; | |
| 1020 else | |
| 1021 avail_insn = NULL; | |
| 1022 } | |
| 1023 | |
| 1024 if (EDGE_CRITICAL_P (pred)) | |
| 1025 critical_count += pred->count; | |
| 1026 | |
| 1027 if (avail_insn != NULL_RTX) | |
| 1028 { | |
| 1029 npred_ok++; | |
| 1030 ok_count += pred->count; | |
| 1031 if (! set_noop_p (PATTERN (gen_move_insn (copy_rtx (dest), | |
| 1032 copy_rtx (avail_reg))))) | |
| 1033 { | |
| 1034 /* Check if there is going to be a split. */ | |
| 1035 if (EDGE_CRITICAL_P (pred)) | |
| 1036 critical_edge_split = true; | |
| 1037 } | |
| 1038 else /* Its a dead move no need to generate. */ | |
| 1039 continue; | |
| 1040 occr = (struct unoccr *) obstack_alloc (&unoccr_obstack, | |
| 1041 sizeof (struct unoccr)); | |
| 1042 occr->insn = avail_insn; | |
| 1043 occr->pred = pred; | |
| 1044 occr->next = avail_occrs; | |
| 1045 avail_occrs = occr; | |
| 1046 if (! rollback_unoccr) | |
| 1047 rollback_unoccr = occr; | |
| 1048 } | |
| 1049 else | |
| 1050 { | |
| 1051 /* Adding a load on a critical edge will cause a split. */ | |
| 1052 if (EDGE_CRITICAL_P (pred)) | |
| 1053 critical_edge_split = true; | |
| 1054 not_ok_count += pred->count; | |
| 1055 unoccr = (struct unoccr *) obstack_alloc (&unoccr_obstack, | |
| 1056 sizeof (struct unoccr)); | |
| 1057 unoccr->insn = NULL_RTX; | |
| 1058 unoccr->pred = pred; | |
| 1059 unoccr->next = unavail_occrs; | |
| 1060 unavail_occrs = unoccr; | |
| 1061 if (! rollback_unoccr) | |
| 1062 rollback_unoccr = unoccr; | |
| 1063 } | |
| 1064 } | |
| 1065 | |
| 1066 if (/* No load can be replaced by copy. */ | |
| 1067 npred_ok == 0 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1068 /* Prevent exploding the code. */ |
| 0 | 1069 || (optimize_bb_for_size_p (bb) && npred_ok > 1) |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1070 /* If we don't have profile information we cannot tell if splitting |
| 0 | 1071 a critical edge is profitable or not so don't do it. */ |
| 1072 || ((! profile_info || ! flag_branch_probabilities | |
| 1073 || targetm.cannot_modify_jumps_p ()) | |
| 1074 && critical_edge_split)) | |
| 1075 goto cleanup; | |
| 1076 | |
| 1077 /* Check if it's worth applying the partial redundancy elimination. */ | |
| 1078 if (ok_count < GCSE_AFTER_RELOAD_PARTIAL_FRACTION * not_ok_count) | |
| 1079 goto cleanup; | |
| 1080 if (ok_count < GCSE_AFTER_RELOAD_CRITICAL_FRACTION * critical_count) | |
| 1081 goto cleanup; | |
| 1082 | |
| 1083 /* Generate moves to the loaded register from where | |
| 1084 the memory is available. */ | |
| 1085 for (occr = avail_occrs; occr; occr = occr->next) | |
| 1086 { | |
| 1087 avail_insn = occr->insn; | |
| 1088 pred = occr->pred; | |
| 1089 /* Set avail_reg to be the register having the value of the | |
| 1090 memory. */ | |
| 1091 avail_reg = get_avail_load_store_reg (avail_insn); | |
| 1092 gcc_assert (avail_reg); | |
| 1093 | |
| 1094 insert_insn_on_edge (gen_move_insn (copy_rtx (dest), | |
| 1095 copy_rtx (avail_reg)), | |
| 1096 pred); | |
| 1097 stats.moves_inserted++; | |
| 1098 | |
| 1099 if (dump_file) | |
| 1100 fprintf (dump_file, | |
| 1101 "generating move from %d to %d on edge from %d to %d\n", | |
| 1102 REGNO (avail_reg), | |
| 1103 REGNO (dest), | |
| 1104 pred->src->index, | |
| 1105 pred->dest->index); | |
| 1106 } | |
| 1107 | |
| 1108 /* Regenerate loads where the memory is unavailable. */ | |
| 1109 for (unoccr = unavail_occrs; unoccr; unoccr = unoccr->next) | |
| 1110 { | |
| 1111 pred = unoccr->pred; | |
| 1112 insert_insn_on_edge (copy_insn (PATTERN (insn)), pred); | |
| 1113 stats.copies_inserted++; | |
| 1114 | |
| 1115 if (dump_file) | |
| 1116 { | |
| 1117 fprintf (dump_file, | |
| 1118 "generating on edge from %d to %d a copy of load: ", | |
| 1119 pred->src->index, | |
| 1120 pred->dest->index); | |
| 1121 print_rtl (dump_file, PATTERN (insn)); | |
| 1122 fprintf (dump_file, "\n"); | |
| 1123 } | |
| 1124 } | |
| 1125 | |
| 1126 /* Delete the insn if it is not available in this block and mark it | |
| 1127 for deletion if it is available. If insn is available it may help | |
| 1128 discover additional redundancies, so mark it for later deletion. */ | |
| 1129 for (a_occr = get_bb_avail_insn (bb, expr->avail_occr); | |
| 1130 a_occr && (a_occr->insn != insn); | |
| 1131 a_occr = get_bb_avail_insn (bb, a_occr->next)); | |
| 1132 | |
| 1133 if (!a_occr) | |
| 1134 { | |
| 1135 stats.insns_deleted++; | |
| 1136 | |
| 1137 if (dump_file) | |
| 1138 { | |
| 1139 fprintf (dump_file, "deleting insn:\n"); | |
| 1140 print_rtl_single (dump_file, insn); | |
| 1141 fprintf (dump_file, "\n"); | |
| 1142 } | |
| 1143 delete_insn (insn); | |
| 1144 } | |
| 1145 else | |
| 1146 a_occr->deleted_p = 1; | |
| 1147 | |
| 1148 cleanup: | |
| 1149 if (rollback_unoccr) | |
| 1150 obstack_free (&unoccr_obstack, rollback_unoccr); | |
| 1151 } | |
| 1152 | |
| 1153 /* Performing the redundancy elimination as described before. */ | |
| 1154 | |
| 1155 static void | |
| 1156 eliminate_partially_redundant_loads (void) | |
| 1157 { | |
| 1158 rtx insn; | |
| 1159 basic_block bb; | |
| 1160 | |
| 1161 /* Note we start at block 1. */ | |
| 1162 | |
| 1163 if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR) | |
| 1164 return; | |
| 1165 | |
| 1166 FOR_BB_BETWEEN (bb, | |
| 1167 ENTRY_BLOCK_PTR->next_bb->next_bb, | |
| 1168 EXIT_BLOCK_PTR, | |
| 1169 next_bb) | |
| 1170 { | |
| 1171 /* Don't try anything on basic blocks with strange predecessors. */ | |
| 1172 if (! bb_has_well_behaved_predecessors (bb)) | |
| 1173 continue; | |
| 1174 | |
| 1175 /* Do not try anything on cold basic blocks. */ | |
| 1176 if (optimize_bb_for_size_p (bb)) | |
| 1177 continue; | |
| 1178 | |
| 1179 /* Reset the table of things changed since the start of the current | |
| 1180 basic block. */ | |
| 1181 reset_opr_set_tables (); | |
| 1182 | |
| 1183 /* Look at all insns in the current basic block and see if there are | |
| 1184 any loads in it that we can record. */ | |
| 1185 FOR_BB_INSNS (bb, insn) | |
| 1186 { | |
| 1187 /* Is it a load - of the form (set (reg) (mem))? */ | |
| 1188 if (NONJUMP_INSN_P (insn) | |
| 1189 && GET_CODE (PATTERN (insn)) == SET | |
| 1190 && REG_P (SET_DEST (PATTERN (insn))) | |
| 1191 && MEM_P (SET_SRC (PATTERN (insn)))) | |
| 1192 { | |
| 1193 rtx pat = PATTERN (insn); | |
| 1194 rtx src = SET_SRC (pat); | |
| 1195 struct expr *expr; | |
| 1196 | |
| 1197 if (!MEM_VOLATILE_P (src) | |
| 1198 && GET_MODE (src) != BLKmode | |
| 1199 && general_operand (src, GET_MODE (src)) | |
| 1200 /* Are the operands unchanged since the start of the | |
| 1201 block? */ | |
| 1202 && oprs_unchanged_p (src, insn, false) | |
| 1203 && !(flag_non_call_exceptions && may_trap_p (src)) | |
| 1204 && !side_effects_p (src) | |
| 1205 /* Is the expression recorded? */ | |
| 1206 && (expr = lookup_expr_in_table (src)) != NULL) | |
| 1207 { | |
| 1208 /* We now have a load (insn) and an available memory at | |
| 1209 its BB start (expr). Try to remove the loads if it is | |
| 1210 redundant. */ | |
| 1211 eliminate_partially_redundant_load (bb, insn, expr); | |
| 1212 } | |
| 1213 } | |
| 1214 | |
| 1215 /* Keep track of everything modified by this insn, so that we | |
| 1216 know what has been modified since the start of the current | |
| 1217 basic block. */ | |
| 1218 if (INSN_P (insn)) | |
| 1219 record_opr_changes (insn); | |
| 1220 } | |
| 1221 } | |
| 1222 | |
| 1223 commit_edge_insertions (); | |
| 1224 } | |
| 1225 | |
| 1226 /* Go over the expression hash table and delete insns that were | |
| 1227 marked for later deletion. */ | |
| 1228 | |
| 1229 /* This helper is called via htab_traverse. */ | |
| 1230 static int | |
| 1231 delete_redundant_insns_1 (void **slot, void *data ATTRIBUTE_UNUSED) | |
| 1232 { | |
| 1233 struct expr *expr = (struct expr *) *slot; | |
| 1234 struct occr *occr; | |
| 1235 | |
| 1236 for (occr = expr->avail_occr; occr != NULL; occr = occr->next) | |
| 1237 { | |
| 1238 if (occr->deleted_p && dbg_cnt (gcse2_delete)) | |
| 1239 { | |
| 1240 delete_insn (occr->insn); | |
| 1241 stats.insns_deleted++; | |
| 1242 | |
| 1243 if (dump_file) | |
| 1244 { | |
| 1245 fprintf (dump_file, "deleting insn:\n"); | |
| 1246 print_rtl_single (dump_file, occr->insn); | |
| 1247 fprintf (dump_file, "\n"); | |
| 1248 } | |
| 1249 } | |
| 1250 } | |
| 1251 | |
| 1252 return 1; | |
| 1253 } | |
| 1254 | |
| 1255 static void | |
| 1256 delete_redundant_insns (void) | |
| 1257 { | |
| 1258 htab_traverse (expr_table, delete_redundant_insns_1, NULL); | |
| 1259 if (dump_file) | |
| 1260 fprintf (dump_file, "\n"); | |
| 1261 } | |
| 1262 | |
| 1263 /* Main entry point of the GCSE after reload - clean some redundant loads | |
| 1264 due to spilling. */ | |
| 1265 | |
| 1266 static void | |
| 1267 gcse_after_reload_main (rtx f ATTRIBUTE_UNUSED) | |
| 1268 { | |
| 1269 | |
| 1270 memset (&stats, 0, sizeof (stats)); | |
| 1271 | |
| 1272 /* Allocate memory for this pass. | |
| 1273 Also computes and initializes the insns' CUIDs. */ | |
| 1274 alloc_mem (); | |
| 1275 | |
| 1276 /* We need alias analysis. */ | |
| 1277 init_alias_analysis (); | |
| 1278 | |
| 1279 compute_hash_table (); | |
| 1280 | |
| 1281 if (dump_file) | |
| 1282 dump_hash_table (dump_file); | |
| 1283 | |
| 1284 if (htab_elements (expr_table) > 0) | |
| 1285 { | |
| 1286 eliminate_partially_redundant_loads (); | |
| 1287 delete_redundant_insns (); | |
| 1288 | |
| 1289 if (dump_file) | |
| 1290 { | |
| 1291 fprintf (dump_file, "GCSE AFTER RELOAD stats:\n"); | |
| 1292 fprintf (dump_file, "copies inserted: %d\n", stats.copies_inserted); | |
| 1293 fprintf (dump_file, "moves inserted: %d\n", stats.moves_inserted); | |
| 1294 fprintf (dump_file, "insns deleted: %d\n", stats.insns_deleted); | |
| 1295 fprintf (dump_file, "\n\n"); | |
| 1296 } | |
| 1297 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1298 |
| 0 | 1299 /* We are finished with alias. */ |
| 1300 end_alias_analysis (); | |
| 1301 | |
| 1302 free_mem (); | |
| 1303 } | |
| 1304 | |
| 1305 | |
| 1306 static bool | |
| 1307 gate_handle_gcse2 (void) | |
| 1308 { | |
| 1309 return (optimize > 0 && flag_gcse_after_reload | |
| 1310 && optimize_function_for_speed_p (cfun)); | |
| 1311 } | |
| 1312 | |
| 1313 | |
| 1314 static unsigned int | |
| 1315 rest_of_handle_gcse2 (void) | |
| 1316 { | |
| 1317 gcse_after_reload_main (get_insns ()); | |
| 1318 rebuild_jump_labels (get_insns ()); | |
| 1319 return 0; | |
| 1320 } | |
| 1321 | |
| 1322 struct rtl_opt_pass pass_gcse2 = | |
| 1323 { | |
| 1324 { | |
| 1325 RTL_PASS, | |
| 1326 "gcse2", /* name */ | |
| 1327 gate_handle_gcse2, /* gate */ | |
| 1328 rest_of_handle_gcse2, /* execute */ | |
| 1329 NULL, /* sub */ | |
| 1330 NULL, /* next */ | |
| 1331 0, /* static_pass_number */ | |
| 1332 TV_GCSE_AFTER_RELOAD, /* tv_id */ | |
| 1333 0, /* properties_required */ | |
| 1334 0, /* properties_provided */ | |
| 1335 0, /* properties_destroyed */ | |
| 1336 0, /* todo_flags_start */ | |
| 1337 TODO_dump_func | TODO_verify_rtl_sharing | |
| 1338 | TODO_verify_flow | TODO_ggc_collect /* todo_flags_finish */ | |
| 1339 } | |
| 1340 }; | |
| 1341 |