]>
Commit | Line | Data |
---|---|---|
4b673aa1 | 1 | /* Store motion via Lazy Code Motion on the reverse CFG. |
2 | Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, | |
3 | 2006, 2007, 2008, 2009 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 "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 "ggc.h" | |
4b673aa1 | 42 | #include "intl.h" |
43 | #include "timevar.h" | |
44 | #include "tree-pass.h" | |
45 | #include "hashtab.h" | |
46 | #include "df.h" | |
47 | #include "dbgcnt.h" | |
48 | ||
acf70424 | 49 | /* This pass implements downward store motion. |
50 | As of May 1, 2009, the pass is not enabled by default on any target, | |
51 | but bootstrap completes on ia64 and x86_64 with the pass enabled. */ | |
52 | ||
53 | /* TODO: | |
54 | - remove_reachable_equiv_notes is an incomprehensible pile of goo and | |
55 | a compile time hog that needs a rewrite (maybe cache st_exprs to | |
56 | invalidate REG_EQUAL/REG_EQUIV notes for?). | |
57 | - pattern_regs in st_expr should be a regset (on its own obstack). | |
58 | - antic_stores and avail_stores should be VECs instead of lists. | |
59 | - store_motion_mems should be a VEC instead of a list. | |
60 | - there should be an alloc pool for struct st_expr objects. | |
61 | - investigate whether it is helpful to make the address of an st_expr | |
62 | a cselib VALUE. | |
63 | - when GIMPLE alias information is exported, the effectiveness of this | |
64 | pass should be re-evaluated. | |
65 | */ | |
66 | ||
67 | /* This is a list of store expressions (MEMs). The structure is used | |
68 | as an expression table to track stores which look interesting, and | |
69 | might be moveable towards the exit block. */ | |
70 | ||
71 | struct st_expr | |
4b673aa1 | 72 | { |
acf70424 | 73 | /* Pattern of this mem. */ |
74 | rtx pattern; | |
75 | /* List of registers mentioned by the mem. */ | |
76 | rtx pattern_regs; | |
77 | /* INSN list of stores that are locally anticipatable. */ | |
78 | rtx antic_stores; | |
79 | /* INSN list of stores that are locally available. */ | |
80 | rtx avail_stores; | |
81 | /* Next in the list. */ | |
82 | struct st_expr * next; | |
83 | /* Store ID in the dataflow bitmaps. */ | |
84 | int index; | |
85 | /* Hash value for the hash table. */ | |
86 | unsigned int hash_index; | |
87 | /* Register holding the stored expression when a store is moved. | |
88 | This field is also used as a cache in find_moveable_store, see | |
89 | LAST_AVAIL_CHECK_FAILURE below. */ | |
90 | rtx reaching_reg; | |
4b673aa1 | 91 | }; |
92 | ||
93 | /* Head of the list of load/store memory refs. */ | |
acf70424 | 94 | static struct st_expr * store_motion_mems = NULL; |
4b673aa1 | 95 | |
96 | /* Hashtable for the load/store memory refs. */ | |
acf70424 | 97 | static htab_t store_motion_mems_table = NULL; |
4b673aa1 | 98 | |
acf70424 | 99 | /* These bitmaps will hold the local dataflow properties per basic block. */ |
100 | static sbitmap *st_kill, *st_avloc, *st_antloc, *st_transp; | |
4b673aa1 | 101 | |
102 | /* Nonzero for expressions which should be inserted on a specific edge. */ | |
acf70424 | 103 | static sbitmap *st_insert_map; |
4b673aa1 | 104 | |
105 | /* Nonzero for expressions which should be deleted in a specific block. */ | |
acf70424 | 106 | static sbitmap *st_delete_map; |
107 | ||
108 | /* Global holding the number of store expressions we are dealing with. */ | |
109 | static int num_stores; | |
4b673aa1 | 110 | |
111 | /* Contains the edge_list returned by pre_edge_lcm. */ | |
112 | static struct edge_list *edge_list; | |
113 | ||
4b673aa1 | 114 | static hashval_t |
acf70424 | 115 | pre_st_expr_hash (const void *p) |
4b673aa1 | 116 | { |
117 | int do_not_record_p = 0; | |
acf70424 | 118 | const struct st_expr *const x = (const struct st_expr *) p; |
4b673aa1 | 119 | return hash_rtx (x->pattern, GET_MODE (x->pattern), &do_not_record_p, NULL, false); |
120 | } | |
121 | ||
122 | static int | |
acf70424 | 123 | pre_st_expr_eq (const void *p1, const void *p2) |
4b673aa1 | 124 | { |
acf70424 | 125 | const struct st_expr *const ptr1 = (const struct st_expr *) p1, |
126 | *const ptr2 = (const struct st_expr *) p2; | |
4b673aa1 | 127 | return exp_equiv_p (ptr1->pattern, ptr2->pattern, 0, true); |
128 | } | |
129 | ||
acf70424 | 130 | /* This will search the st_expr list for a matching expression. If it |
4b673aa1 | 131 | doesn't find one, we create one and initialize it. */ |
132 | ||
acf70424 | 133 | static struct st_expr * |
134 | st_expr_entry (rtx x) | |
4b673aa1 | 135 | { |
136 | int do_not_record_p = 0; | |
acf70424 | 137 | struct st_expr * ptr; |
4b673aa1 | 138 | unsigned int hash; |
139 | void **slot; | |
acf70424 | 140 | struct st_expr e; |
4b673aa1 | 141 | |
142 | hash = hash_rtx (x, GET_MODE (x), &do_not_record_p, | |
143 | NULL, /*have_reg_qty=*/false); | |
144 | ||
145 | e.pattern = x; | |
acf70424 | 146 | slot = htab_find_slot_with_hash (store_motion_mems_table, &e, hash, INSERT); |
4b673aa1 | 147 | if (*slot) |
acf70424 | 148 | return (struct st_expr *)*slot; |
4b673aa1 | 149 | |
acf70424 | 150 | ptr = XNEW (struct st_expr); |
4b673aa1 | 151 | |
acf70424 | 152 | ptr->next = store_motion_mems; |
4b673aa1 | 153 | ptr->pattern = x; |
154 | ptr->pattern_regs = NULL_RTX; | |
acf70424 | 155 | ptr->antic_stores = NULL_RTX; |
156 | ptr->avail_stores = NULL_RTX; | |
4b673aa1 | 157 | ptr->reaching_reg = NULL_RTX; |
4b673aa1 | 158 | ptr->index = 0; |
159 | ptr->hash_index = hash; | |
acf70424 | 160 | store_motion_mems = ptr; |
4b673aa1 | 161 | *slot = ptr; |
162 | ||
163 | return ptr; | |
164 | } | |
165 | ||
acf70424 | 166 | /* Free up an individual st_expr entry. */ |
4b673aa1 | 167 | |
168 | static void | |
acf70424 | 169 | free_st_expr_entry (struct st_expr * ptr) |
4b673aa1 | 170 | { |
acf70424 | 171 | free_INSN_LIST_list (& ptr->antic_stores); |
172 | free_INSN_LIST_list (& ptr->avail_stores); | |
4b673aa1 | 173 | |
174 | free (ptr); | |
175 | } | |
176 | ||
acf70424 | 177 | /* Free up all memory associated with the st_expr list. */ |
4b673aa1 | 178 | |
179 | static void | |
acf70424 | 180 | free_store_motion_mems (void) |
4b673aa1 | 181 | { |
acf70424 | 182 | if (store_motion_mems_table) |
183 | htab_delete (store_motion_mems_table); | |
184 | store_motion_mems_table = NULL; | |
4b673aa1 | 185 | |
acf70424 | 186 | while (store_motion_mems) |
4b673aa1 | 187 | { |
acf70424 | 188 | struct st_expr * tmp = store_motion_mems; |
189 | store_motion_mems = store_motion_mems->next; | |
190 | free_st_expr_entry (tmp); | |
4b673aa1 | 191 | } |
acf70424 | 192 | store_motion_mems = NULL; |
4b673aa1 | 193 | } |
194 | ||
195 | /* Assign each element of the list of mems a monotonically increasing value. */ | |
196 | ||
197 | static int | |
acf70424 | 198 | enumerate_store_motion_mems (void) |
4b673aa1 | 199 | { |
acf70424 | 200 | struct st_expr * ptr; |
4b673aa1 | 201 | int n = 0; |
202 | ||
acf70424 | 203 | for (ptr = store_motion_mems; ptr != NULL; ptr = ptr->next) |
4b673aa1 | 204 | ptr->index = n++; |
205 | ||
206 | return n; | |
207 | } | |
208 | ||
209 | /* Return first item in the list. */ | |
210 | ||
acf70424 | 211 | static inline struct st_expr * |
212 | first_st_expr (void) | |
4b673aa1 | 213 | { |
acf70424 | 214 | return store_motion_mems; |
4b673aa1 | 215 | } |
216 | ||
217 | /* Return the next item in the list after the specified one. */ | |
218 | ||
acf70424 | 219 | static inline struct st_expr * |
220 | next_st_expr (struct st_expr * ptr) | |
4b673aa1 | 221 | { |
222 | return ptr->next; | |
223 | } | |
224 | ||
acf70424 | 225 | /* Dump debugging info about the store_motion_mems list. */ |
4b673aa1 | 226 | |
227 | static void | |
acf70424 | 228 | print_store_motion_mems (FILE * file) |
4b673aa1 | 229 | { |
acf70424 | 230 | struct st_expr * ptr; |
4b673aa1 | 231 | |
acf70424 | 232 | fprintf (dump_file, "STORE_MOTION list of MEM exprs considered:\n"); |
4b673aa1 | 233 | |
acf70424 | 234 | for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr)) |
4b673aa1 | 235 | { |
236 | fprintf (file, " Pattern (%3d): ", ptr->index); | |
237 | ||
238 | print_rtl (file, ptr->pattern); | |
239 | ||
acf70424 | 240 | fprintf (file, "\n ANTIC stores : "); |
4b673aa1 | 241 | |
acf70424 | 242 | if (ptr->antic_stores) |
243 | print_rtl (file, ptr->antic_stores); | |
4b673aa1 | 244 | else |
245 | fprintf (file, "(nil)"); | |
246 | ||
acf70424 | 247 | fprintf (file, "\n AVAIL stores : "); |
4b673aa1 | 248 | |
acf70424 | 249 | if (ptr->avail_stores) |
250 | print_rtl (file, ptr->avail_stores); | |
4b673aa1 | 251 | else |
252 | fprintf (file, "(nil)"); | |
253 | ||
254 | fprintf (file, "\n\n"); | |
255 | } | |
256 | ||
257 | fprintf (file, "\n"); | |
258 | } | |
259 | \f | |
4b673aa1 | 260 | /* Return zero if some of the registers in list X are killed |
261 | due to set of registers in bitmap REGS_SET. */ | |
262 | ||
263 | static bool | |
264 | store_ops_ok (const_rtx x, int *regs_set) | |
265 | { | |
266 | const_rtx reg; | |
267 | ||
268 | for (; x; x = XEXP (x, 1)) | |
269 | { | |
270 | reg = XEXP (x, 0); | |
271 | if (regs_set[REGNO(reg)]) | |
272 | return false; | |
273 | } | |
274 | ||
275 | return true; | |
276 | } | |
277 | ||
acf70424 | 278 | /* Helper for extract_mentioned_regs. */ |
48e1416a | 279 | |
acf70424 | 280 | static int |
281 | extract_mentioned_regs_1 (rtx *loc, void *data) | |
4b673aa1 | 282 | { |
acf70424 | 283 | rtx *mentioned_regs_p = (rtx *) data; |
4b673aa1 | 284 | |
acf70424 | 285 | if (REG_P (*loc)) |
286 | *mentioned_regs_p = alloc_EXPR_LIST (0, *loc, *mentioned_regs_p); | |
4b673aa1 | 287 | |
acf70424 | 288 | return 0; |
4b673aa1 | 289 | } |
290 | ||
acf70424 | 291 | /* Returns a list of registers mentioned in X. |
292 | FIXME: A regset would be prettier and less expensive. */ | |
293 | ||
4b673aa1 | 294 | static rtx |
295 | extract_mentioned_regs (rtx x) | |
296 | { | |
acf70424 | 297 | rtx mentioned_regs = NULL; |
298 | for_each_rtx (&x, extract_mentioned_regs_1, &mentioned_regs); | |
299 | return mentioned_regs; | |
4b673aa1 | 300 | } |
301 | ||
302 | /* Check to see if the load X is aliased with STORE_PATTERN. | |
303 | AFTER is true if we are checking the case when STORE_PATTERN occurs | |
304 | after the X. */ | |
305 | ||
306 | static bool | |
307 | load_kills_store (const_rtx x, const_rtx store_pattern, int after) | |
308 | { | |
309 | if (after) | |
310 | return anti_dependence (x, store_pattern); | |
311 | else | |
312 | return true_dependence (store_pattern, GET_MODE (store_pattern), x, | |
313 | rtx_addr_varies_p); | |
314 | } | |
315 | ||
acf70424 | 316 | /* Go through the entire rtx X, looking for any loads which might alias |
4b673aa1 | 317 | STORE_PATTERN. Return true if found. |
318 | AFTER is true if we are checking the case when STORE_PATTERN occurs | |
319 | after the insn X. */ | |
320 | ||
321 | static bool | |
322 | find_loads (const_rtx x, const_rtx store_pattern, int after) | |
323 | { | |
324 | const char * fmt; | |
325 | int i, j; | |
326 | int ret = false; | |
327 | ||
328 | if (!x) | |
329 | return false; | |
330 | ||
331 | if (GET_CODE (x) == SET) | |
332 | x = SET_SRC (x); | |
333 | ||
334 | if (MEM_P (x)) | |
335 | { | |
336 | if (load_kills_store (x, store_pattern, after)) | |
337 | return true; | |
338 | } | |
339 | ||
340 | /* Recursively process the insn. */ | |
341 | fmt = GET_RTX_FORMAT (GET_CODE (x)); | |
342 | ||
343 | for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0 && !ret; i--) | |
344 | { | |
345 | if (fmt[i] == 'e') | |
346 | ret |= find_loads (XEXP (x, i), store_pattern, after); | |
347 | else if (fmt[i] == 'E') | |
348 | for (j = XVECLEN (x, i) - 1; j >= 0; j--) | |
349 | ret |= find_loads (XVECEXP (x, i, j), store_pattern, after); | |
350 | } | |
351 | return ret; | |
352 | } | |
353 | ||
354 | /* Go through pattern PAT looking for any loads which might kill the | |
355 | store in X. Return true if found. | |
356 | AFTER is true if we are checking the case when loads kill X occurs | |
357 | after the insn for PAT. */ | |
358 | ||
359 | static inline bool | |
360 | store_killed_in_pat (const_rtx x, const_rtx pat, int after) | |
361 | { | |
362 | if (GET_CODE (pat) == SET) | |
363 | { | |
364 | rtx dest = SET_DEST (pat); | |
365 | ||
366 | if (GET_CODE (dest) == ZERO_EXTRACT) | |
367 | dest = XEXP (dest, 0); | |
368 | ||
369 | /* Check for memory stores to aliased objects. */ | |
370 | if (MEM_P (dest) | |
371 | && !exp_equiv_p (dest, x, 0, true)) | |
372 | { | |
373 | if (after) | |
374 | { | |
375 | if (output_dependence (dest, x)) | |
376 | return true; | |
377 | } | |
378 | else | |
379 | { | |
380 | if (output_dependence (x, dest)) | |
381 | return true; | |
382 | } | |
383 | } | |
384 | } | |
385 | ||
386 | if (find_loads (pat, x, after)) | |
387 | return true; | |
388 | ||
389 | return false; | |
390 | } | |
391 | ||
392 | /* Check if INSN kills the store pattern X (is aliased with it). | |
393 | AFTER is true if we are checking the case when store X occurs | |
394 | after the insn. Return true if it does. */ | |
395 | ||
396 | static bool | |
397 | store_killed_in_insn (const_rtx x, const_rtx x_regs, const_rtx insn, int after) | |
398 | { | |
399 | const_rtx reg, base, note, pat; | |
400 | ||
401 | if (!INSN_P (insn)) | |
402 | return false; | |
403 | ||
404 | if (CALL_P (insn)) | |
405 | { | |
406 | /* A normal or pure call might read from pattern, | |
407 | but a const call will not. */ | |
408 | if (!RTL_CONST_CALL_P (insn)) | |
409 | return true; | |
410 | ||
411 | /* But even a const call reads its parameters. Check whether the | |
412 | base of some of registers used in mem is stack pointer. */ | |
413 | for (reg = x_regs; reg; reg = XEXP (reg, 1)) | |
414 | { | |
415 | base = find_base_term (XEXP (reg, 0)); | |
416 | if (!base | |
417 | || (GET_CODE (base) == ADDRESS | |
418 | && GET_MODE (base) == Pmode | |
419 | && XEXP (base, 0) == stack_pointer_rtx)) | |
420 | return true; | |
421 | } | |
422 | ||
423 | return false; | |
424 | } | |
425 | ||
426 | pat = PATTERN (insn); | |
427 | if (GET_CODE (pat) == SET) | |
428 | { | |
429 | if (store_killed_in_pat (x, pat, after)) | |
430 | return true; | |
431 | } | |
432 | else if (GET_CODE (pat) == PARALLEL) | |
433 | { | |
434 | int i; | |
435 | ||
436 | for (i = 0; i < XVECLEN (pat, 0); i++) | |
437 | if (store_killed_in_pat (x, XVECEXP (pat, 0, i), after)) | |
438 | return true; | |
439 | } | |
440 | else if (find_loads (PATTERN (insn), x, after)) | |
441 | return true; | |
442 | ||
443 | /* If this insn has a REG_EQUAL or REG_EQUIV note referencing a memory | |
444 | location aliased with X, then this insn kills X. */ | |
445 | note = find_reg_equal_equiv_note (insn); | |
446 | if (! note) | |
447 | return false; | |
448 | note = XEXP (note, 0); | |
449 | ||
450 | /* However, if the note represents a must alias rather than a may | |
451 | alias relationship, then it does not kill X. */ | |
452 | if (exp_equiv_p (note, x, 0, true)) | |
453 | return false; | |
454 | ||
455 | /* See if there are any aliased loads in the note. */ | |
456 | return find_loads (note, x, after); | |
457 | } | |
458 | ||
459 | /* Returns true if the expression X is loaded or clobbered on or after INSN | |
460 | within basic block BB. REGS_SET_AFTER is bitmap of registers set in | |
461 | or after the insn. X_REGS is list of registers mentioned in X. If the store | |
462 | is killed, return the last insn in that it occurs in FAIL_INSN. */ | |
463 | ||
464 | static bool | |
465 | store_killed_after (const_rtx x, const_rtx x_regs, const_rtx insn, const_basic_block bb, | |
466 | int *regs_set_after, rtx *fail_insn) | |
467 | { | |
468 | rtx last = BB_END (bb), act; | |
469 | ||
470 | if (!store_ops_ok (x_regs, regs_set_after)) | |
471 | { | |
472 | /* We do not know where it will happen. */ | |
473 | if (fail_insn) | |
474 | *fail_insn = NULL_RTX; | |
475 | return true; | |
476 | } | |
477 | ||
478 | /* Scan from the end, so that fail_insn is determined correctly. */ | |
479 | for (act = last; act != PREV_INSN (insn); act = PREV_INSN (act)) | |
480 | if (store_killed_in_insn (x, x_regs, act, false)) | |
481 | { | |
482 | if (fail_insn) | |
483 | *fail_insn = act; | |
484 | return true; | |
485 | } | |
486 | ||
487 | return false; | |
488 | } | |
489 | ||
490 | /* Returns true if the expression X is loaded or clobbered on or before INSN | |
491 | within basic block BB. X_REGS is list of registers mentioned in X. | |
492 | REGS_SET_BEFORE is bitmap of registers set before or in this insn. */ | |
493 | static bool | |
494 | store_killed_before (const_rtx x, const_rtx x_regs, const_rtx insn, const_basic_block bb, | |
495 | int *regs_set_before) | |
496 | { | |
497 | rtx first = BB_HEAD (bb); | |
498 | ||
499 | if (!store_ops_ok (x_regs, regs_set_before)) | |
500 | return true; | |
501 | ||
502 | for ( ; insn != PREV_INSN (first); insn = PREV_INSN (insn)) | |
503 | if (store_killed_in_insn (x, x_regs, insn, true)) | |
504 | return true; | |
505 | ||
506 | return false; | |
507 | } | |
508 | ||
acf70424 | 509 | /* The last insn in the basic block that compute_store_table is processing, |
510 | where store_killed_after is true for X. | |
511 | Since we go through the basic block from BB_END to BB_HEAD, this is | |
512 | also the available store at the end of the basic block. Therefore | |
513 | this is in effect a cache, to avoid calling store_killed_after for | |
514 | equivalent aliasing store expressions. | |
515 | This value is only meaningful during the computation of the store | |
516 | table. We hi-jack the REACHING_REG field of struct st_expr to save | |
517 | a bit of memory. */ | |
518 | #define LAST_AVAIL_CHECK_FAILURE(x) ((x)->reaching_reg) | |
519 | ||
4b673aa1 | 520 | /* Determine whether INSN is MEM store pattern that we will consider moving. |
521 | REGS_SET_BEFORE is bitmap of registers set before (and including) the | |
522 | current insn, REGS_SET_AFTER is bitmap of registers set after (and | |
523 | including) the insn in this basic block. We must be passing through BB from | |
524 | head to end, as we are using this fact to speed things up. | |
525 | ||
526 | The results are stored this way: | |
527 | ||
acf70424 | 528 | -- the first anticipatable expression is added into ANTIC_STORES |
4b673aa1 | 529 | -- if the processed expression is not anticipatable, NULL_RTX is added |
530 | there instead, so that we can use it as indicator that no further | |
531 | expression of this type may be anticipatable | |
acf70424 | 532 | -- if the expression is available, it is added as head of AVAIL_STORES; |
4b673aa1 | 533 | consequently, all of them but this head are dead and may be deleted. |
534 | -- if the expression is not available, the insn due to that it fails to be | |
acf70424 | 535 | available is stored in REACHING_REG (via LAST_AVAIL_CHECK_FAILURE). |
4b673aa1 | 536 | |
537 | The things are complicated a bit by fact that there already may be stores | |
538 | to the same MEM from other blocks; also caller must take care of the | |
539 | necessary cleanup of the temporary markers after end of the basic block. | |
540 | */ | |
541 | ||
542 | static void | |
543 | find_moveable_store (rtx insn, int *regs_set_before, int *regs_set_after) | |
544 | { | |
acf70424 | 545 | struct st_expr * ptr; |
4b673aa1 | 546 | rtx dest, set, tmp; |
547 | int check_anticipatable, check_available; | |
548 | basic_block bb = BLOCK_FOR_INSN (insn); | |
549 | ||
550 | set = single_set (insn); | |
551 | if (!set) | |
552 | return; | |
553 | ||
554 | dest = SET_DEST (set); | |
555 | ||
556 | if (! MEM_P (dest) || MEM_VOLATILE_P (dest) | |
557 | || GET_MODE (dest) == BLKmode) | |
558 | return; | |
559 | ||
560 | if (side_effects_p (dest)) | |
561 | return; | |
562 | ||
563 | /* If we are handling exceptions, we must be careful with memory references | |
564 | that may trap. If we are not, the behavior is undefined, so we may just | |
565 | continue. */ | |
566 | if (flag_non_call_exceptions && may_trap_p (dest)) | |
567 | return; | |
568 | ||
569 | /* Even if the destination cannot trap, the source may. In this case we'd | |
570 | need to handle updating the REG_EH_REGION note. */ | |
571 | if (find_reg_note (insn, REG_EH_REGION, NULL_RTX)) | |
572 | return; | |
573 | ||
574 | /* Make sure that the SET_SRC of this store insns can be assigned to | |
575 | a register, or we will fail later on in replace_store_insn, which | |
576 | assumes that we can do this. But sometimes the target machine has | |
577 | oddities like MEM read-modify-write instruction. See for example | |
578 | PR24257. */ | |
579 | if (!can_assign_to_reg_without_clobbers_p (SET_SRC (set))) | |
580 | return; | |
581 | ||
acf70424 | 582 | ptr = st_expr_entry (dest); |
4b673aa1 | 583 | if (!ptr->pattern_regs) |
584 | ptr->pattern_regs = extract_mentioned_regs (dest); | |
585 | ||
586 | /* Do not check for anticipatability if we either found one anticipatable | |
587 | store already, or tested for one and found out that it was killed. */ | |
588 | check_anticipatable = 0; | |
acf70424 | 589 | if (!ptr->antic_stores) |
4b673aa1 | 590 | check_anticipatable = 1; |
591 | else | |
592 | { | |
acf70424 | 593 | tmp = XEXP (ptr->antic_stores, 0); |
4b673aa1 | 594 | if (tmp != NULL_RTX |
595 | && BLOCK_FOR_INSN (tmp) != bb) | |
596 | check_anticipatable = 1; | |
597 | } | |
598 | if (check_anticipatable) | |
599 | { | |
600 | if (store_killed_before (dest, ptr->pattern_regs, insn, bb, regs_set_before)) | |
601 | tmp = NULL_RTX; | |
602 | else | |
603 | tmp = insn; | |
acf70424 | 604 | ptr->antic_stores = alloc_INSN_LIST (tmp, ptr->antic_stores); |
4b673aa1 | 605 | } |
606 | ||
607 | /* It is not necessary to check whether store is available if we did | |
608 | it successfully before; if we failed before, do not bother to check | |
609 | until we reach the insn that caused us to fail. */ | |
610 | check_available = 0; | |
acf70424 | 611 | if (!ptr->avail_stores) |
4b673aa1 | 612 | check_available = 1; |
613 | else | |
614 | { | |
acf70424 | 615 | tmp = XEXP (ptr->avail_stores, 0); |
4b673aa1 | 616 | if (BLOCK_FOR_INSN (tmp) != bb) |
617 | check_available = 1; | |
618 | } | |
619 | if (check_available) | |
620 | { | |
621 | /* Check that we have already reached the insn at that the check | |
622 | failed last time. */ | |
623 | if (LAST_AVAIL_CHECK_FAILURE (ptr)) | |
624 | { | |
625 | for (tmp = BB_END (bb); | |
626 | tmp != insn && tmp != LAST_AVAIL_CHECK_FAILURE (ptr); | |
627 | tmp = PREV_INSN (tmp)) | |
628 | continue; | |
629 | if (tmp == insn) | |
630 | check_available = 0; | |
631 | } | |
632 | else | |
633 | check_available = store_killed_after (dest, ptr->pattern_regs, insn, | |
634 | bb, regs_set_after, | |
635 | &LAST_AVAIL_CHECK_FAILURE (ptr)); | |
636 | } | |
637 | if (!check_available) | |
acf70424 | 638 | ptr->avail_stores = alloc_INSN_LIST (insn, ptr->avail_stores); |
4b673aa1 | 639 | } |
640 | ||
641 | /* Find available and anticipatable stores. */ | |
642 | ||
643 | static int | |
644 | compute_store_table (void) | |
645 | { | |
646 | int ret; | |
647 | basic_block bb; | |
aa7ab40e | 648 | #ifdef ENABLE_CHECKING |
4b673aa1 | 649 | unsigned regno; |
aa7ab40e | 650 | #endif |
acf70424 | 651 | rtx insn, tmp; |
652 | df_ref *def_rec; | |
4b673aa1 | 653 | int *last_set_in, *already_set; |
acf70424 | 654 | struct st_expr * ptr, **prev_next_ptr_ptr; |
4b673aa1 | 655 | unsigned int max_gcse_regno = max_reg_num (); |
656 | ||
acf70424 | 657 | store_motion_mems = NULL; |
658 | store_motion_mems_table = htab_create (13, pre_st_expr_hash, | |
659 | pre_st_expr_eq, NULL); | |
4b673aa1 | 660 | last_set_in = XCNEWVEC (int, max_gcse_regno); |
661 | already_set = XNEWVEC (int, max_gcse_regno); | |
662 | ||
663 | /* Find all the stores we care about. */ | |
664 | FOR_EACH_BB (bb) | |
665 | { | |
666 | /* First compute the registers set in this block. */ | |
4b673aa1 | 667 | FOR_BB_INSNS (bb, insn) |
668 | { | |
acf70424 | 669 | |
4b673aa1 | 670 | if (! INSN_P (insn)) |
671 | continue; | |
672 | ||
acf70424 | 673 | for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++) |
674 | last_set_in[DF_REF_REGNO (*def_rec)] = INSN_UID (insn); | |
4b673aa1 | 675 | } |
676 | ||
677 | /* Now find the stores. */ | |
678 | memset (already_set, 0, sizeof (int) * max_gcse_regno); | |
4b673aa1 | 679 | FOR_BB_INSNS (bb, insn) |
680 | { | |
681 | if (! INSN_P (insn)) | |
682 | continue; | |
683 | ||
acf70424 | 684 | for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++) |
685 | already_set[DF_REF_REGNO (*def_rec)] = INSN_UID (insn); | |
4b673aa1 | 686 | |
687 | /* Now that we've marked regs, look for stores. */ | |
688 | find_moveable_store (insn, already_set, last_set_in); | |
689 | ||
690 | /* Unmark regs that are no longer set. */ | |
acf70424 | 691 | for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++) |
692 | if (last_set_in[DF_REF_REGNO (*def_rec)] == INSN_UID (insn)) | |
693 | last_set_in[DF_REF_REGNO (*def_rec)] = 0; | |
4b673aa1 | 694 | } |
695 | ||
696 | #ifdef ENABLE_CHECKING | |
697 | /* last_set_in should now be all-zero. */ | |
698 | for (regno = 0; regno < max_gcse_regno; regno++) | |
699 | gcc_assert (!last_set_in[regno]); | |
700 | #endif | |
701 | ||
702 | /* Clear temporary marks. */ | |
acf70424 | 703 | for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr)) |
4b673aa1 | 704 | { |
acf70424 | 705 | LAST_AVAIL_CHECK_FAILURE (ptr) = NULL_RTX; |
706 | if (ptr->antic_stores | |
707 | && (tmp = XEXP (ptr->antic_stores, 0)) == NULL_RTX) | |
708 | ptr->antic_stores = XEXP (ptr->antic_stores, 1); | |
4b673aa1 | 709 | } |
710 | } | |
711 | ||
712 | /* Remove the stores that are not available anywhere, as there will | |
713 | be no opportunity to optimize them. */ | |
acf70424 | 714 | for (ptr = store_motion_mems, prev_next_ptr_ptr = &store_motion_mems; |
4b673aa1 | 715 | ptr != NULL; |
716 | ptr = *prev_next_ptr_ptr) | |
717 | { | |
acf70424 | 718 | if (! ptr->avail_stores) |
4b673aa1 | 719 | { |
720 | *prev_next_ptr_ptr = ptr->next; | |
acf70424 | 721 | htab_remove_elt_with_hash (store_motion_mems_table, |
722 | ptr, ptr->hash_index); | |
723 | free_st_expr_entry (ptr); | |
4b673aa1 | 724 | } |
725 | else | |
726 | prev_next_ptr_ptr = &ptr->next; | |
727 | } | |
728 | ||
acf70424 | 729 | ret = enumerate_store_motion_mems (); |
4b673aa1 | 730 | |
731 | if (dump_file) | |
acf70424 | 732 | print_store_motion_mems (dump_file); |
4b673aa1 | 733 | |
734 | free (last_set_in); | |
735 | free (already_set); | |
736 | return ret; | |
737 | } | |
738 | ||
acf70424 | 739 | /* In all code following after this, REACHING_REG has its original |
740 | meaning again. Avoid confusion, and undef the accessor macro for | |
741 | the temporary marks usage in compute_store_table. */ | |
742 | #undef LAST_AVAIL_CHECK_FAILURE | |
743 | ||
4b673aa1 | 744 | /* Insert an instruction at the beginning of a basic block, and update |
745 | the BB_HEAD if needed. */ | |
746 | ||
747 | static void | |
748 | insert_insn_start_basic_block (rtx insn, basic_block bb) | |
749 | { | |
750 | /* Insert at start of successor block. */ | |
751 | rtx prev = PREV_INSN (BB_HEAD (bb)); | |
752 | rtx before = BB_HEAD (bb); | |
753 | while (before != 0) | |
754 | { | |
755 | if (! LABEL_P (before) | |
756 | && !NOTE_INSN_BASIC_BLOCK_P (before)) | |
757 | break; | |
758 | prev = before; | |
759 | if (prev == BB_END (bb)) | |
760 | break; | |
761 | before = NEXT_INSN (before); | |
762 | } | |
763 | ||
764 | insn = emit_insn_after_noloc (insn, prev, bb); | |
765 | ||
766 | if (dump_file) | |
767 | { | |
768 | fprintf (dump_file, "STORE_MOTION insert store at start of BB %d:\n", | |
769 | bb->index); | |
770 | print_inline_rtx (dump_file, insn, 6); | |
771 | fprintf (dump_file, "\n"); | |
772 | } | |
773 | } | |
774 | ||
acf70424 | 775 | /* This routine will insert a store on an edge. EXPR is the st_expr entry for |
4b673aa1 | 776 | the memory reference, and E is the edge to insert it on. Returns nonzero |
777 | if an edge insertion was performed. */ | |
778 | ||
779 | static int | |
acf70424 | 780 | insert_store (struct st_expr * expr, edge e) |
4b673aa1 | 781 | { |
782 | rtx reg, insn; | |
783 | basic_block bb; | |
784 | edge tmp; | |
785 | edge_iterator ei; | |
786 | ||
787 | /* We did all the deleted before this insert, so if we didn't delete a | |
788 | store, then we haven't set the reaching reg yet either. */ | |
789 | if (expr->reaching_reg == NULL_RTX) | |
790 | return 0; | |
791 | ||
792 | if (e->flags & EDGE_FAKE) | |
793 | return 0; | |
794 | ||
795 | reg = expr->reaching_reg; | |
796 | insn = gen_move_insn (copy_rtx (expr->pattern), reg); | |
797 | ||
798 | /* If we are inserting this expression on ALL predecessor edges of a BB, | |
799 | insert it at the start of the BB, and reset the insert bits on the other | |
800 | edges so we don't try to insert it on the other edges. */ | |
801 | bb = e->dest; | |
802 | FOR_EACH_EDGE (tmp, ei, e->dest->preds) | |
803 | if (!(tmp->flags & EDGE_FAKE)) | |
804 | { | |
805 | int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest); | |
48e1416a | 806 | |
4b673aa1 | 807 | gcc_assert (index != EDGE_INDEX_NO_EDGE); |
acf70424 | 808 | if (! TEST_BIT (st_insert_map[index], expr->index)) |
4b673aa1 | 809 | break; |
810 | } | |
811 | ||
812 | /* If tmp is NULL, we found an insertion on every edge, blank the | |
813 | insertion vector for these edges, and insert at the start of the BB. */ | |
814 | if (!tmp && bb != EXIT_BLOCK_PTR) | |
815 | { | |
816 | FOR_EACH_EDGE (tmp, ei, e->dest->preds) | |
817 | { | |
818 | int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest); | |
acf70424 | 819 | RESET_BIT (st_insert_map[index], expr->index); |
4b673aa1 | 820 | } |
821 | insert_insn_start_basic_block (insn, bb); | |
822 | return 0; | |
823 | } | |
824 | ||
825 | /* We can't put stores in the front of blocks pointed to by abnormal | |
826 | edges since that may put a store where one didn't used to be. */ | |
827 | gcc_assert (!(e->flags & EDGE_ABNORMAL)); | |
828 | ||
829 | insert_insn_on_edge (insn, e); | |
830 | ||
831 | if (dump_file) | |
832 | { | |
833 | fprintf (dump_file, "STORE_MOTION insert insn on edge (%d, %d):\n", | |
834 | e->src->index, e->dest->index); | |
835 | print_inline_rtx (dump_file, insn, 6); | |
836 | fprintf (dump_file, "\n"); | |
837 | } | |
838 | ||
839 | return 1; | |
840 | } | |
841 | ||
842 | /* Remove any REG_EQUAL or REG_EQUIV notes containing a reference to the | |
843 | memory location in SMEXPR set in basic block BB. | |
844 | ||
845 | This could be rather expensive. */ | |
846 | ||
847 | static void | |
acf70424 | 848 | remove_reachable_equiv_notes (basic_block bb, struct st_expr *smexpr) |
4b673aa1 | 849 | { |
850 | edge_iterator *stack, ei; | |
851 | int sp; | |
852 | edge act; | |
853 | sbitmap visited = sbitmap_alloc (last_basic_block); | |
854 | rtx last, insn, note; | |
855 | rtx mem = smexpr->pattern; | |
856 | ||
857 | stack = XNEWVEC (edge_iterator, n_basic_blocks); | |
858 | sp = 0; | |
859 | ei = ei_start (bb->succs); | |
860 | ||
861 | sbitmap_zero (visited); | |
862 | ||
863 | act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container (ei), 0) : NULL); | |
864 | while (1) | |
865 | { | |
866 | if (!act) | |
867 | { | |
868 | if (!sp) | |
869 | { | |
870 | free (stack); | |
871 | sbitmap_free (visited); | |
872 | return; | |
873 | } | |
874 | act = ei_edge (stack[--sp]); | |
875 | } | |
876 | bb = act->dest; | |
877 | ||
878 | if (bb == EXIT_BLOCK_PTR | |
879 | || TEST_BIT (visited, bb->index)) | |
880 | { | |
881 | if (!ei_end_p (ei)) | |
882 | ei_next (&ei); | |
883 | act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL; | |
884 | continue; | |
885 | } | |
886 | SET_BIT (visited, bb->index); | |
887 | ||
888 | if (TEST_BIT (st_antloc[bb->index], smexpr->index)) | |
889 | { | |
acf70424 | 890 | for (last = smexpr->antic_stores; |
4b673aa1 | 891 | BLOCK_FOR_INSN (XEXP (last, 0)) != bb; |
892 | last = XEXP (last, 1)) | |
893 | continue; | |
894 | last = XEXP (last, 0); | |
895 | } | |
896 | else | |
897 | last = NEXT_INSN (BB_END (bb)); | |
898 | ||
899 | for (insn = BB_HEAD (bb); insn != last; insn = NEXT_INSN (insn)) | |
900 | if (INSN_P (insn)) | |
901 | { | |
902 | note = find_reg_equal_equiv_note (insn); | |
903 | if (!note || !exp_equiv_p (XEXP (note, 0), mem, 0, true)) | |
904 | continue; | |
905 | ||
906 | if (dump_file) | |
907 | fprintf (dump_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n", | |
908 | INSN_UID (insn)); | |
909 | remove_note (insn, note); | |
910 | } | |
911 | ||
912 | if (!ei_end_p (ei)) | |
913 | ei_next (&ei); | |
914 | act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL; | |
915 | ||
916 | if (EDGE_COUNT (bb->succs) > 0) | |
917 | { | |
918 | if (act) | |
919 | stack[sp++] = ei; | |
920 | ei = ei_start (bb->succs); | |
921 | act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container (ei), 0) : NULL); | |
922 | } | |
923 | } | |
924 | } | |
925 | ||
926 | /* This routine will replace a store with a SET to a specified register. */ | |
927 | ||
928 | static void | |
acf70424 | 929 | replace_store_insn (rtx reg, rtx del, basic_block bb, struct st_expr *smexpr) |
4b673aa1 | 930 | { |
931 | rtx insn, mem, note, set, ptr; | |
932 | ||
933 | mem = smexpr->pattern; | |
934 | insn = gen_move_insn (reg, SET_SRC (single_set (del))); | |
935 | ||
acf70424 | 936 | for (ptr = smexpr->antic_stores; ptr; ptr = XEXP (ptr, 1)) |
4b673aa1 | 937 | if (XEXP (ptr, 0) == del) |
938 | { | |
939 | XEXP (ptr, 0) = insn; | |
940 | break; | |
941 | } | |
942 | ||
943 | /* Move the notes from the deleted insn to its replacement. */ | |
944 | REG_NOTES (insn) = REG_NOTES (del); | |
945 | ||
946 | /* Emit the insn AFTER all the notes are transferred. | |
947 | This is cheaper since we avoid df rescanning for the note change. */ | |
948 | insn = emit_insn_after (insn, del); | |
949 | ||
950 | if (dump_file) | |
951 | { | |
952 | fprintf (dump_file, | |
953 | "STORE_MOTION delete insn in BB %d:\n ", bb->index); | |
954 | print_inline_rtx (dump_file, del, 6); | |
955 | fprintf (dump_file, "\nSTORE_MOTION replaced with insn:\n "); | |
956 | print_inline_rtx (dump_file, insn, 6); | |
957 | fprintf (dump_file, "\n"); | |
958 | } | |
959 | ||
960 | delete_insn (del); | |
961 | ||
962 | /* Now we must handle REG_EQUAL notes whose contents is equal to the mem; | |
963 | they are no longer accurate provided that they are reached by this | |
964 | definition, so drop them. */ | |
965 | for (; insn != NEXT_INSN (BB_END (bb)); insn = NEXT_INSN (insn)) | |
966 | if (INSN_P (insn)) | |
967 | { | |
968 | set = single_set (insn); | |
969 | if (!set) | |
970 | continue; | |
971 | if (exp_equiv_p (SET_DEST (set), mem, 0, true)) | |
972 | return; | |
973 | note = find_reg_equal_equiv_note (insn); | |
974 | if (!note || !exp_equiv_p (XEXP (note, 0), mem, 0, true)) | |
975 | continue; | |
976 | ||
977 | if (dump_file) | |
978 | fprintf (dump_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n", | |
979 | INSN_UID (insn)); | |
980 | remove_note (insn, note); | |
981 | } | |
982 | remove_reachable_equiv_notes (bb, smexpr); | |
983 | } | |
984 | ||
985 | ||
986 | /* Delete a store, but copy the value that would have been stored into | |
987 | the reaching_reg for later storing. */ | |
988 | ||
989 | static void | |
acf70424 | 990 | delete_store (struct st_expr * expr, basic_block bb) |
4b673aa1 | 991 | { |
992 | rtx reg, i, del; | |
993 | ||
994 | if (expr->reaching_reg == NULL_RTX) | |
995 | expr->reaching_reg = gen_reg_rtx_and_attrs (expr->pattern); | |
996 | ||
997 | reg = expr->reaching_reg; | |
998 | ||
acf70424 | 999 | for (i = expr->avail_stores; i; i = XEXP (i, 1)) |
4b673aa1 | 1000 | { |
1001 | del = XEXP (i, 0); | |
1002 | if (BLOCK_FOR_INSN (del) == bb) | |
1003 | { | |
1004 | /* We know there is only one since we deleted redundant | |
1005 | ones during the available computation. */ | |
1006 | replace_store_insn (reg, del, bb, expr); | |
1007 | break; | |
1008 | } | |
1009 | } | |
1010 | } | |
1011 | ||
1012 | /* Fill in available, anticipatable, transparent and kill vectors in | |
1013 | STORE_DATA, based on lists of available and anticipatable stores. */ | |
1014 | static void | |
1015 | build_store_vectors (void) | |
1016 | { | |
1017 | basic_block bb; | |
1018 | int *regs_set_in_block; | |
1019 | rtx insn, st; | |
acf70424 | 1020 | struct st_expr * ptr; |
4b673aa1 | 1021 | unsigned int max_gcse_regno = max_reg_num (); |
1022 | ||
1023 | /* Build the gen_vector. This is any store in the table which is not killed | |
1024 | by aliasing later in its block. */ | |
acf70424 | 1025 | st_avloc = sbitmap_vector_alloc (last_basic_block, num_stores); |
1026 | sbitmap_vector_zero (st_avloc, last_basic_block); | |
4b673aa1 | 1027 | |
1028 | st_antloc = sbitmap_vector_alloc (last_basic_block, num_stores); | |
1029 | sbitmap_vector_zero (st_antloc, last_basic_block); | |
1030 | ||
acf70424 | 1031 | for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr)) |
4b673aa1 | 1032 | { |
acf70424 | 1033 | for (st = ptr->avail_stores; st != NULL; st = XEXP (st, 1)) |
4b673aa1 | 1034 | { |
1035 | insn = XEXP (st, 0); | |
1036 | bb = BLOCK_FOR_INSN (insn); | |
1037 | ||
1038 | /* If we've already seen an available expression in this block, | |
1039 | we can delete this one (It occurs earlier in the block). We'll | |
1040 | copy the SRC expression to an unused register in case there | |
1041 | are any side effects. */ | |
acf70424 | 1042 | if (TEST_BIT (st_avloc[bb->index], ptr->index)) |
4b673aa1 | 1043 | { |
1044 | rtx r = gen_reg_rtx_and_attrs (ptr->pattern); | |
1045 | if (dump_file) | |
1046 | fprintf (dump_file, "Removing redundant store:\n"); | |
1047 | replace_store_insn (r, XEXP (st, 0), bb, ptr); | |
1048 | continue; | |
1049 | } | |
acf70424 | 1050 | SET_BIT (st_avloc[bb->index], ptr->index); |
4b673aa1 | 1051 | } |
1052 | ||
acf70424 | 1053 | for (st = ptr->antic_stores; st != NULL; st = XEXP (st, 1)) |
4b673aa1 | 1054 | { |
1055 | insn = XEXP (st, 0); | |
1056 | bb = BLOCK_FOR_INSN (insn); | |
1057 | SET_BIT (st_antloc[bb->index], ptr->index); | |
1058 | } | |
1059 | } | |
1060 | ||
acf70424 | 1061 | st_kill = sbitmap_vector_alloc (last_basic_block, num_stores); |
1062 | sbitmap_vector_zero (st_kill, last_basic_block); | |
4b673aa1 | 1063 | |
acf70424 | 1064 | st_transp = sbitmap_vector_alloc (last_basic_block, num_stores); |
1065 | sbitmap_vector_zero (st_transp, last_basic_block); | |
4b673aa1 | 1066 | regs_set_in_block = XNEWVEC (int, max_gcse_regno); |
1067 | ||
1068 | FOR_EACH_BB (bb) | |
1069 | { | |
1070 | FOR_BB_INSNS (bb, insn) | |
1071 | if (INSN_P (insn)) | |
1072 | { | |
1073 | df_ref *def_rec; | |
1074 | for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++) | |
1075 | { | |
1076 | unsigned int ref_regno = DF_REF_REGNO (*def_rec); | |
1077 | if (ref_regno < max_gcse_regno) | |
1078 | regs_set_in_block[DF_REF_REGNO (*def_rec)] = 1; | |
1079 | } | |
1080 | } | |
1081 | ||
acf70424 | 1082 | for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr)) |
4b673aa1 | 1083 | { |
1084 | if (store_killed_after (ptr->pattern, ptr->pattern_regs, BB_HEAD (bb), | |
1085 | bb, regs_set_in_block, NULL)) | |
1086 | { | |
1087 | /* It should not be necessary to consider the expression | |
1088 | killed if it is both anticipatable and available. */ | |
1089 | if (!TEST_BIT (st_antloc[bb->index], ptr->index) | |
acf70424 | 1090 | || !TEST_BIT (st_avloc[bb->index], ptr->index)) |
1091 | SET_BIT (st_kill[bb->index], ptr->index); | |
4b673aa1 | 1092 | } |
1093 | else | |
acf70424 | 1094 | SET_BIT (st_transp[bb->index], ptr->index); |
4b673aa1 | 1095 | } |
1096 | } | |
1097 | ||
1098 | free (regs_set_in_block); | |
1099 | ||
1100 | if (dump_file) | |
1101 | { | |
1102 | dump_sbitmap_vector (dump_file, "st_antloc", "", st_antloc, last_basic_block); | |
acf70424 | 1103 | dump_sbitmap_vector (dump_file, "st_kill", "", st_kill, last_basic_block); |
1104 | dump_sbitmap_vector (dump_file, "st_transp", "", st_transp, last_basic_block); | |
1105 | dump_sbitmap_vector (dump_file, "st_avloc", "", st_avloc, last_basic_block); | |
4b673aa1 | 1106 | } |
1107 | } | |
1108 | ||
1109 | /* Free memory used by store motion. */ | |
1110 | ||
1111 | static void | |
1112 | free_store_memory (void) | |
1113 | { | |
acf70424 | 1114 | free_store_motion_mems (); |
1115 | ||
1116 | if (st_avloc) | |
1117 | sbitmap_vector_free (st_avloc); | |
1118 | if (st_kill) | |
1119 | sbitmap_vector_free (st_kill); | |
1120 | if (st_transp) | |
1121 | sbitmap_vector_free (st_transp); | |
4b673aa1 | 1122 | if (st_antloc) |
1123 | sbitmap_vector_free (st_antloc); | |
acf70424 | 1124 | if (st_insert_map) |
1125 | sbitmap_vector_free (st_insert_map); | |
1126 | if (st_delete_map) | |
1127 | sbitmap_vector_free (st_delete_map); | |
4b673aa1 | 1128 | |
acf70424 | 1129 | st_avloc = st_kill = st_transp = st_antloc = NULL; |
1130 | st_insert_map = st_delete_map = NULL; | |
4b673aa1 | 1131 | } |
1132 | ||
1133 | /* Perform store motion. Much like gcse, except we move expressions the | |
1134 | other way by looking at the flowgraph in reverse. | |
1135 | Return non-zero if transformations are performed by the pass. */ | |
1136 | ||
1137 | static int | |
1138 | one_store_motion_pass (void) | |
1139 | { | |
1140 | basic_block bb; | |
1141 | int x; | |
acf70424 | 1142 | struct st_expr * ptr; |
1143 | int did_edge_inserts = 0; | |
1144 | int n_stores_deleted = 0; | |
1145 | int n_stores_created = 0; | |
4b673aa1 | 1146 | |
1147 | init_alias_analysis (); | |
1148 | ||
1149 | /* Find all the available and anticipatable stores. */ | |
1150 | num_stores = compute_store_table (); | |
1151 | if (num_stores == 0) | |
1152 | { | |
acf70424 | 1153 | htab_delete (store_motion_mems_table); |
1154 | store_motion_mems_table = NULL; | |
4b673aa1 | 1155 | end_alias_analysis (); |
1156 | return 0; | |
1157 | } | |
1158 | ||
1159 | /* Now compute kill & transp vectors. */ | |
1160 | build_store_vectors (); | |
1161 | add_noreturn_fake_exit_edges (); | |
1162 | connect_infinite_loops_to_exit (); | |
1163 | ||
acf70424 | 1164 | edge_list = pre_edge_rev_lcm (num_stores, st_transp, st_avloc, |
1165 | st_antloc, st_kill, &st_insert_map, | |
1166 | &st_delete_map); | |
4b673aa1 | 1167 | |
1168 | /* Now we want to insert the new stores which are going to be needed. */ | |
acf70424 | 1169 | for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr)) |
4b673aa1 | 1170 | { |
1171 | /* If any of the edges we have above are abnormal, we can't move this | |
1172 | store. */ | |
1173 | for (x = NUM_EDGES (edge_list) - 1; x >= 0; x--) | |
acf70424 | 1174 | if (TEST_BIT (st_insert_map[x], ptr->index) |
4b673aa1 | 1175 | && (INDEX_EDGE (edge_list, x)->flags & EDGE_ABNORMAL)) |
1176 | break; | |
1177 | ||
1178 | if (x >= 0) | |
1179 | { | |
1180 | if (dump_file != NULL) | |
1181 | fprintf (dump_file, | |
1182 | "Can't replace store %d: abnormal edge from %d to %d\n", | |
1183 | ptr->index, INDEX_EDGE (edge_list, x)->src->index, | |
1184 | INDEX_EDGE (edge_list, x)->dest->index); | |
1185 | continue; | |
1186 | } | |
48e1416a | 1187 | |
4b673aa1 | 1188 | /* Now we want to insert the new stores which are going to be needed. */ |
1189 | ||
1190 | FOR_EACH_BB (bb) | |
acf70424 | 1191 | if (TEST_BIT (st_delete_map[bb->index], ptr->index)) |
4b673aa1 | 1192 | { |
1193 | delete_store (ptr, bb); | |
acf70424 | 1194 | n_stores_deleted++; |
4b673aa1 | 1195 | } |
1196 | ||
1197 | for (x = 0; x < NUM_EDGES (edge_list); x++) | |
acf70424 | 1198 | if (TEST_BIT (st_insert_map[x], ptr->index)) |
4b673aa1 | 1199 | { |
acf70424 | 1200 | did_edge_inserts |= insert_store (ptr, INDEX_EDGE (edge_list, x)); |
1201 | n_stores_created++; | |
4b673aa1 | 1202 | } |
1203 | } | |
1204 | ||
acf70424 | 1205 | if (did_edge_inserts) |
4b673aa1 | 1206 | commit_edge_insertions (); |
1207 | ||
1208 | free_store_memory (); | |
1209 | free_edge_list (edge_list); | |
1210 | remove_fake_exit_edges (); | |
1211 | end_alias_analysis (); | |
1212 | ||
1213 | if (dump_file) | |
1214 | { | |
1215 | fprintf (dump_file, "STORE_MOTION of %s, %d basic blocks, ", | |
1216 | current_function_name (), n_basic_blocks); | |
acf70424 | 1217 | fprintf (dump_file, "%d insns deleted, %d insns created\n", |
1218 | n_stores_deleted, n_stores_created); | |
4b673aa1 | 1219 | } |
1220 | ||
acf70424 | 1221 | return (n_stores_deleted > 0 || n_stores_created > 0); |
4b673aa1 | 1222 | } |
1223 | ||
1224 | \f | |
1225 | static bool | |
1226 | gate_rtl_store_motion (void) | |
1227 | { | |
1228 | return optimize > 0 && flag_gcse_sm | |
1229 | && !cfun->calls_setjmp | |
1230 | && optimize_function_for_speed_p (cfun) | |
1231 | && dbg_cnt (store_motion); | |
1232 | } | |
1233 | ||
1234 | static unsigned int | |
1235 | execute_rtl_store_motion (void) | |
1236 | { | |
1237 | delete_unreachable_blocks (); | |
1238 | df_note_add_problem (); | |
1239 | df_analyze (); | |
1240 | flag_rerun_cse_after_global_opts |= one_store_motion_pass (); | |
1241 | return 0; | |
1242 | } | |
1243 | ||
1244 | struct rtl_opt_pass pass_rtl_store_motion = | |
1245 | { | |
1246 | { | |
1247 | RTL_PASS, | |
1248 | "store_motion", /* name */ | |
48e1416a | 1249 | gate_rtl_store_motion, /* gate */ |
1250 | execute_rtl_store_motion, /* execute */ | |
4b673aa1 | 1251 | NULL, /* sub */ |
1252 | NULL, /* next */ | |
1253 | 0, /* static_pass_number */ | |
1254 | TV_LSM, /* tv_id */ | |
1255 | PROP_cfglayout, /* properties_required */ | |
1256 | 0, /* properties_provided */ | |
1257 | 0, /* properties_destroyed */ | |
1258 | 0, /* todo_flags_start */ | |
1259 | TODO_df_finish | TODO_verify_rtl_sharing | | |
1260 | TODO_dump_func | | |
1261 | TODO_verify_flow | TODO_ggc_collect /* todo_flags_finish */ | |
1262 | } | |
1263 | }; | |
1264 |