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