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