ada: Fix wrong resolution for hidden discriminant in predicate
[official-gcc.git] / gcc / store-motion.cc
blobb21b34f223d5957d730f8b846fbb0e441c92458a
1 /* Store motion via Lazy Code Motion on the reverse CFG.
2 Copyright (C) 1997-2023 Free Software Foundation, Inc.
4 This file is part of GCC.
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.
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.
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/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "backend.h"
24 #include "rtl.h"
25 #include "tree.h"
26 #include "predict.h"
27 #include "df.h"
28 #include "toplev.h"
30 #include "cfgrtl.h"
31 #include "cfganal.h"
32 #include "lcm.h"
33 #include "cfgcleanup.h"
34 #include "expr.h"
35 #include "tree-pass.h"
36 #include "dbgcnt.h"
37 #include "rtl-iter.h"
38 #include "print-rtl.h"
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. */
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).
49 - store_motion_mems should be a vec instead of a list.
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.
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. */
61 struct st_expr
63 /* Pattern of this mem. */
64 rtx pattern;
65 /* List of registers mentioned by the mem. */
66 vec<rtx> pattern_regs;
67 /* INSN list of stores that are locally anticipatable. */
68 vec<rtx_insn *> antic_stores;
69 /* INSN list of stores that are locally available. */
70 vec<rtx_insn *> avail_stores;
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;
83 /* Head of the list of load/store memory refs. */
84 static struct st_expr * store_motion_mems = NULL;
86 /* These bitmaps will hold the local dataflow properties per basic block. */
87 static sbitmap *st_kill, *st_avloc, *st_antloc, *st_transp;
89 /* Nonzero for expressions which should be inserted on a specific edge. */
90 static sbitmap *st_insert_map;
92 /* Nonzero for expressions which should be deleted in a specific block. */
93 static sbitmap *st_delete_map;
95 /* Global holding the number of store expressions we are dealing with. */
96 static int num_stores;
98 /* Contains the edge_list returned by pre_edge_lcm. */
99 static struct edge_list *edge_list;
101 /* Hashtable helpers. */
103 struct st_expr_hasher : nofree_ptr_hash <st_expr>
105 static inline hashval_t hash (const st_expr *);
106 static inline bool equal (const st_expr *, const st_expr *);
109 inline hashval_t
110 st_expr_hasher::hash (const st_expr *x)
112 int do_not_record_p = 0;
113 return hash_rtx (x->pattern, GET_MODE (x->pattern), &do_not_record_p, NULL, false);
116 inline bool
117 st_expr_hasher::equal (const st_expr *ptr1, const st_expr *ptr2)
119 return exp_equiv_p (ptr1->pattern, ptr2->pattern, 0, true);
122 /* Hashtable for the load/store memory refs. */
123 static hash_table<st_expr_hasher> *store_motion_mems_table;
125 /* This will search the st_expr list for a matching expression. If it
126 doesn't find one, we create one and initialize it. */
128 static struct st_expr *
129 st_expr_entry (rtx x)
131 int do_not_record_p = 0;
132 struct st_expr * ptr;
133 unsigned int hash;
134 st_expr **slot;
135 struct st_expr e;
137 hash = hash_rtx (x, GET_MODE (x), &do_not_record_p,
138 NULL, /*have_reg_qty=*/false);
140 e.pattern = x;
141 slot = store_motion_mems_table->find_slot_with_hash (&e, hash, INSERT);
142 if (*slot)
143 return *slot;
145 ptr = XNEW (struct st_expr);
147 ptr->next = store_motion_mems;
148 ptr->pattern = x;
149 ptr->pattern_regs.create (0);
150 ptr->antic_stores.create (0);
151 ptr->avail_stores.create (0);
152 ptr->reaching_reg = NULL_RTX;
153 ptr->index = 0;
154 ptr->hash_index = hash;
155 store_motion_mems = ptr;
156 *slot = ptr;
158 return ptr;
161 /* Free up an individual st_expr entry. */
163 static void
164 free_st_expr_entry (struct st_expr * ptr)
166 ptr->antic_stores.release ();
167 ptr->avail_stores.release ();
168 ptr->pattern_regs.release ();
170 free (ptr);
173 /* Free up all memory associated with the st_expr list. */
175 static void
176 free_store_motion_mems (void)
178 delete store_motion_mems_table;
179 store_motion_mems_table = NULL;
181 while (store_motion_mems)
183 struct st_expr * tmp = store_motion_mems;
184 store_motion_mems = store_motion_mems->next;
185 free_st_expr_entry (tmp);
187 store_motion_mems = NULL;
190 /* Assign each element of the list of mems a monotonically increasing value. */
192 static int
193 enumerate_store_motion_mems (void)
195 struct st_expr * ptr;
196 int n = 0;
198 for (ptr = store_motion_mems; ptr != NULL; ptr = ptr->next)
199 ptr->index = n++;
201 return n;
204 /* Return first item in the list. */
206 static inline struct st_expr *
207 first_st_expr (void)
209 return store_motion_mems;
212 /* Return the next item in the list after the specified one. */
214 static inline struct st_expr *
215 next_st_expr (struct st_expr * ptr)
217 return ptr->next;
220 /* Dump debugging info about the store_motion_mems list. */
222 static void
223 print_store_motion_mems (FILE * file)
225 struct st_expr * ptr;
227 fprintf (dump_file, "STORE_MOTION list of MEM exprs considered:\n");
229 for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
231 fprintf (file, " Pattern (%3d): ", ptr->index);
233 print_rtl (file, ptr->pattern);
235 fprintf (file, "\n ANTIC stores : ");
236 print_rtx_insn_vec (file, ptr->antic_stores);
238 fprintf (file, "\n AVAIL stores : ");
240 print_rtx_insn_vec (file, ptr->avail_stores);
242 fprintf (file, "\n\n");
245 fprintf (file, "\n");
248 /* Return zero if some of the registers in list X are killed
249 due to set of registers in bitmap REGS_SET. */
251 static bool
252 store_ops_ok (const vec<rtx> &x, int *regs_set)
254 for (rtx temp : x)
255 if (regs_set[REGNO (temp)])
256 return false;
258 return true;
261 /* Returns a list of registers mentioned in X.
262 FIXME: A regset would be prettier and less expensive. */
264 static void
265 extract_mentioned_regs (rtx x, vec<rtx> *mentioned_regs)
267 subrtx_var_iterator::array_type array;
268 FOR_EACH_SUBRTX_VAR (iter, array, x, NONCONST)
270 rtx x = *iter;
271 if (REG_P (x))
272 mentioned_regs->safe_push (x);
276 /* Check to see if the load X is aliased with STORE_PATTERN.
277 AFTER is true if we are checking the case when STORE_PATTERN occurs
278 after the X. */
280 static bool
281 load_kills_store (const_rtx x, const_rtx store_pattern, int after)
283 if (after)
284 return anti_dependence (x, store_pattern);
285 else
286 return true_dependence (store_pattern, GET_MODE (store_pattern), x);
289 /* Go through the entire rtx X, looking for any loads which might alias
290 STORE_PATTERN. Return true if found.
291 AFTER is true if we are checking the case when STORE_PATTERN occurs
292 after the insn X. */
294 static bool
295 find_loads (const_rtx x, const_rtx store_pattern, int after)
297 const char * fmt;
298 int i, j;
299 int ret = false;
301 if (!x)
302 return false;
304 if (GET_CODE (x) == SET)
305 x = SET_SRC (x);
307 if (MEM_P (x))
309 if (load_kills_store (x, store_pattern, after))
310 return true;
313 /* Recursively process the insn. */
314 fmt = GET_RTX_FORMAT (GET_CODE (x));
316 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0 && !ret; i--)
318 if (fmt[i] == 'e')
319 ret |= find_loads (XEXP (x, i), store_pattern, after);
320 else if (fmt[i] == 'E')
321 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
322 ret |= find_loads (XVECEXP (x, i, j), store_pattern, after);
324 return ret;
327 /* Go through pattern PAT looking for any loads which might kill the
328 store in X. Return true if found.
329 AFTER is true if we are checking the case when loads kill X occurs
330 after the insn for PAT. */
332 static inline bool
333 store_killed_in_pat (const_rtx x, const_rtx pat, int after)
335 if (GET_CODE (pat) == SET)
337 rtx dest = SET_DEST (pat);
339 if (GET_CODE (dest) == ZERO_EXTRACT)
340 dest = XEXP (dest, 0);
342 /* Check for memory stores to aliased objects. */
343 if (MEM_P (dest)
344 && !exp_equiv_p (dest, x, 0, true))
346 if (after)
348 if (output_dependence (dest, x))
349 return true;
351 else
353 if (output_dependence (x, dest))
354 return true;
359 if (find_loads (pat, x, after))
360 return true;
362 return false;
365 /* Check if INSN kills the store pattern X (is aliased with it).
366 AFTER is true if we are checking the case when store X occurs
367 after the insn. Return true if it does. */
369 static bool
370 store_killed_in_insn (const_rtx x, const vec<rtx> &x_regs,
371 const rtx_insn *insn, int after)
373 const_rtx note, pat;
375 if (! NONDEBUG_INSN_P (insn))
376 return false;
378 if (CALL_P (insn))
380 /* A normal or pure call might read from pattern,
381 but a const call will not. */
382 if (!RTL_CONST_CALL_P (insn))
383 return true;
385 /* But even a const call reads its parameters. Check whether the
386 base of some of registers used in mem is stack pointer. */
387 for (rtx temp : x_regs)
388 if (may_be_sp_based_p (temp))
389 return true;
391 return false;
394 pat = PATTERN (insn);
395 if (GET_CODE (pat) == SET)
397 if (store_killed_in_pat (x, pat, after))
398 return true;
400 else if (GET_CODE (pat) == PARALLEL)
402 int i;
404 for (i = 0; i < XVECLEN (pat, 0); i++)
405 if (store_killed_in_pat (x, XVECEXP (pat, 0, i), after))
406 return true;
408 else if (find_loads (PATTERN (insn), x, after))
409 return true;
411 /* If this insn has a REG_EQUAL or REG_EQUIV note referencing a memory
412 location aliased with X, then this insn kills X. */
413 note = find_reg_equal_equiv_note (insn);
414 if (! note)
415 return false;
416 note = XEXP (note, 0);
418 /* However, if the note represents a must alias rather than a may
419 alias relationship, then it does not kill X. */
420 if (exp_equiv_p (note, x, 0, true))
421 return false;
423 /* See if there are any aliased loads in the note. */
424 return find_loads (note, x, after);
427 /* Returns true if the expression X is loaded or clobbered on or after INSN
428 within basic block BB. REGS_SET_AFTER is bitmap of registers set in
429 or after the insn. X_REGS is list of registers mentioned in X. If the store
430 is killed, return the last insn in that it occurs in FAIL_INSN. */
432 static bool
433 store_killed_after (const_rtx x, const vec<rtx> &x_regs,
434 const rtx_insn *insn, const_basic_block bb,
435 int *regs_set_after, rtx *fail_insn)
437 rtx_insn *last = BB_END (bb), *act;
439 if (!store_ops_ok (x_regs, regs_set_after))
441 /* We do not know where it will happen. */
442 if (fail_insn)
443 *fail_insn = NULL_RTX;
444 return true;
447 /* Scan from the end, so that fail_insn is determined correctly. */
448 for (act = last; act != PREV_INSN (insn); act = PREV_INSN (act))
449 if (store_killed_in_insn (x, x_regs, act, false))
451 if (fail_insn)
452 *fail_insn = act;
453 return true;
456 return false;
459 /* Returns true if the expression X is loaded or clobbered on or before INSN
460 within basic block BB. X_REGS is list of registers mentioned in X.
461 REGS_SET_BEFORE is bitmap of registers set before or in this insn. */
462 static bool
463 store_killed_before (const_rtx x, const vec<rtx> &x_regs,
464 const rtx_insn *insn, const_basic_block bb,
465 int *regs_set_before)
467 rtx_insn *first = BB_HEAD (bb);
469 if (!store_ops_ok (x_regs, regs_set_before))
470 return true;
472 for ( ; insn != PREV_INSN (first); insn = PREV_INSN (insn))
473 if (store_killed_in_insn (x, x_regs, insn, true))
474 return true;
476 return false;
479 /* The last insn in the basic block that compute_store_table is processing,
480 where store_killed_after is true for X.
481 Since we go through the basic block from BB_END to BB_HEAD, this is
482 also the available store at the end of the basic block. Therefore
483 this is in effect a cache, to avoid calling store_killed_after for
484 equivalent aliasing store expressions.
485 This value is only meaningful during the computation of the store
486 table. We hi-jack the REACHING_REG field of struct st_expr to save
487 a bit of memory. */
488 #define LAST_AVAIL_CHECK_FAILURE(x) ((x)->reaching_reg)
490 /* Determine whether INSN is MEM store pattern that we will consider moving.
491 REGS_SET_BEFORE is bitmap of registers set before (and including) the
492 current insn, REGS_SET_AFTER is bitmap of registers set after (and
493 including) the insn in this basic block. We must be passing through BB from
494 head to end, as we are using this fact to speed things up.
496 The results are stored this way:
498 -- the first anticipatable expression is added into ANTIC_STORES
499 -- if the processed expression is not anticipatable, NULL_RTX is added
500 there instead, so that we can use it as indicator that no further
501 expression of this type may be anticipatable
502 -- if the expression is available, it is added as head of AVAIL_STORES;
503 consequently, all of them but this head are dead and may be deleted.
504 -- if the expression is not available, the insn due to that it fails to be
505 available is stored in REACHING_REG (via LAST_AVAIL_CHECK_FAILURE).
507 The things are complicated a bit by fact that there already may be stores
508 to the same MEM from other blocks; also caller must take care of the
509 necessary cleanup of the temporary markers after end of the basic block.
512 static void
513 find_moveable_store (rtx_insn *insn, int *regs_set_before, int *regs_set_after)
515 struct st_expr * ptr;
516 rtx dest, set;
517 int check_anticipatable, check_available;
518 basic_block bb = BLOCK_FOR_INSN (insn);
520 set = single_set (insn);
521 if (!set)
522 return;
524 dest = SET_DEST (set);
526 if (! MEM_P (dest) || MEM_VOLATILE_P (dest)
527 || GET_MODE (dest) == BLKmode)
528 return;
530 if (side_effects_p (dest))
531 return;
533 /* If we are handling exceptions, we must be careful with memory references
534 that may trap. If we are not, the behavior is undefined, so we may just
535 continue. */
536 if (cfun->can_throw_non_call_exceptions && may_trap_p (dest))
537 return;
539 /* Even if the destination cannot trap, the source may. In this case we'd
540 need to handle updating the REG_EH_REGION note. */
541 if (find_reg_note (insn, REG_EH_REGION, NULL_RTX))
542 return;
544 /* Make sure that the SET_SRC of this store insns can be assigned to
545 a register, or we will fail later on in replace_store_insn, which
546 assumes that we can do this. But sometimes the target machine has
547 oddities like MEM read-modify-write instruction. See for example
548 PR24257. */
549 if (!can_assign_to_reg_without_clobbers_p (SET_SRC (set),
550 GET_MODE (SET_SRC (set))))
551 return;
553 ptr = st_expr_entry (dest);
554 if (ptr->pattern_regs.is_empty ())
555 extract_mentioned_regs (dest, &ptr->pattern_regs);
557 /* Do not check for anticipatability if we either found one anticipatable
558 store already, or tested for one and found out that it was killed. */
559 check_anticipatable = 0;
560 if (ptr->antic_stores.is_empty ())
561 check_anticipatable = 1;
562 else
564 rtx_insn *tmp = ptr->antic_stores.last ();
565 if (tmp != NULL_RTX
566 && BLOCK_FOR_INSN (tmp) != bb)
567 check_anticipatable = 1;
569 if (check_anticipatable)
571 rtx_insn *tmp;
572 if (store_killed_before (dest, ptr->pattern_regs, insn, bb, regs_set_before))
573 tmp = NULL;
574 else
575 tmp = insn;
576 ptr->antic_stores.safe_push (tmp);
579 /* It is not necessary to check whether store is available if we did
580 it successfully before; if we failed before, do not bother to check
581 until we reach the insn that caused us to fail. */
582 check_available = 0;
583 if (ptr->avail_stores.is_empty ())
584 check_available = 1;
585 else
587 rtx_insn *tmp = ptr->avail_stores.last ();
588 if (BLOCK_FOR_INSN (tmp) != bb)
589 check_available = 1;
591 if (check_available)
593 /* Check that we have already reached the insn at that the check
594 failed last time. */
595 if (LAST_AVAIL_CHECK_FAILURE (ptr))
597 rtx_insn *tmp;
598 for (tmp = BB_END (bb);
599 tmp != insn && tmp != LAST_AVAIL_CHECK_FAILURE (ptr);
600 tmp = PREV_INSN (tmp))
601 continue;
602 if (tmp == insn)
603 check_available = 0;
605 else
606 check_available = store_killed_after (dest, ptr->pattern_regs, insn,
607 bb, regs_set_after,
608 &LAST_AVAIL_CHECK_FAILURE (ptr));
610 if (!check_available)
611 ptr->avail_stores.safe_push (insn);
614 /* Find available and anticipatable stores. */
616 static int
617 compute_store_table (void)
619 int ret;
620 basic_block bb;
621 rtx_insn *insn;
622 rtx_insn *tmp;
623 df_ref def;
624 int *last_set_in, *already_set;
625 struct st_expr * ptr, **prev_next_ptr_ptr;
626 unsigned int max_gcse_regno = max_reg_num ();
628 store_motion_mems = NULL;
629 store_motion_mems_table = new hash_table<st_expr_hasher> (13);
630 last_set_in = XCNEWVEC (int, max_gcse_regno);
631 already_set = XNEWVEC (int, max_gcse_regno);
633 /* Find all the stores we care about. */
634 FOR_EACH_BB_FN (bb, cfun)
636 /* First compute the registers set in this block. */
637 FOR_BB_INSNS (bb, insn)
640 if (! NONDEBUG_INSN_P (insn))
641 continue;
643 FOR_EACH_INSN_DEF (def, insn)
644 last_set_in[DF_REF_REGNO (def)] = INSN_UID (insn);
647 /* Now find the stores. */
648 memset (already_set, 0, sizeof (int) * max_gcse_regno);
649 FOR_BB_INSNS (bb, insn)
651 if (! NONDEBUG_INSN_P (insn))
652 continue;
654 FOR_EACH_INSN_DEF (def, insn)
655 already_set[DF_REF_REGNO (def)] = INSN_UID (insn);
657 /* Now that we've marked regs, look for stores. */
658 find_moveable_store (insn, already_set, last_set_in);
660 /* Unmark regs that are no longer set. */
661 FOR_EACH_INSN_DEF (def, insn)
662 if (last_set_in[DF_REF_REGNO (def)] == INSN_UID (insn))
663 last_set_in[DF_REF_REGNO (def)] = 0;
666 if (flag_checking)
668 /* last_set_in should now be all-zero. */
669 for (unsigned regno = 0; regno < max_gcse_regno; regno++)
670 gcc_assert (!last_set_in[regno]);
673 /* Clear temporary marks. */
674 for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
676 LAST_AVAIL_CHECK_FAILURE (ptr) = NULL_RTX;
677 if (!ptr->antic_stores.is_empty ()
678 && (tmp = ptr->antic_stores.last ()) == NULL)
679 ptr->antic_stores.pop ();
683 /* Remove the stores that are not available anywhere, as there will
684 be no opportunity to optimize them. */
685 for (ptr = store_motion_mems, prev_next_ptr_ptr = &store_motion_mems;
686 ptr != NULL;
687 ptr = *prev_next_ptr_ptr)
689 if (ptr->avail_stores.is_empty ())
691 *prev_next_ptr_ptr = ptr->next;
692 store_motion_mems_table->remove_elt_with_hash (ptr, ptr->hash_index);
693 free_st_expr_entry (ptr);
695 else
696 prev_next_ptr_ptr = &ptr->next;
699 ret = enumerate_store_motion_mems ();
701 if (dump_file)
702 print_store_motion_mems (dump_file);
704 free (last_set_in);
705 free (already_set);
706 return ret;
709 /* In all code following after this, REACHING_REG has its original
710 meaning again. Avoid confusion, and undef the accessor macro for
711 the temporary marks usage in compute_store_table. */
712 #undef LAST_AVAIL_CHECK_FAILURE
714 /* Insert an instruction at the beginning of a basic block, and update
715 the BB_HEAD if needed. */
717 static void
718 insert_insn_start_basic_block (rtx_insn *insn, basic_block bb)
720 /* Insert at start of successor block. */
721 rtx_insn *prev = PREV_INSN (BB_HEAD (bb));
722 rtx_insn *before = BB_HEAD (bb);
723 while (before != 0)
725 if (! LABEL_P (before)
726 && !NOTE_INSN_BASIC_BLOCK_P (before))
727 break;
728 prev = before;
729 if (prev == BB_END (bb))
730 break;
731 before = NEXT_INSN (before);
734 insn = emit_insn_after_noloc (insn, prev, bb);
736 if (dump_file)
738 fprintf (dump_file, "STORE_MOTION insert store at start of BB %d:\n",
739 bb->index);
740 print_inline_rtx (dump_file, insn, 6);
741 fprintf (dump_file, "\n");
745 /* This routine will insert a store on an edge. EXPR is the st_expr entry for
746 the memory reference, and E is the edge to insert it on. Returns nonzero
747 if an edge insertion was performed. */
749 static int
750 insert_store (struct st_expr * expr, edge e)
752 rtx reg;
753 rtx_insn *insn;
754 basic_block bb;
755 edge tmp;
756 edge_iterator ei;
758 /* We did all the deleted before this insert, so if we didn't delete a
759 store, then we haven't set the reaching reg yet either. */
760 if (expr->reaching_reg == NULL_RTX)
761 return 0;
763 if (e->flags & EDGE_FAKE)
764 return 0;
766 reg = expr->reaching_reg;
767 insn = gen_move_insn (copy_rtx (expr->pattern), reg);
769 /* If we are inserting this expression on ALL predecessor edges of a BB,
770 insert it at the start of the BB, and reset the insert bits on the other
771 edges so we don't try to insert it on the other edges. */
772 bb = e->dest;
773 FOR_EACH_EDGE (tmp, ei, e->dest->preds)
774 if (!(tmp->flags & EDGE_FAKE))
776 int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
778 gcc_assert (index != EDGE_INDEX_NO_EDGE);
779 if (! bitmap_bit_p (st_insert_map[index], expr->index))
780 break;
783 /* If tmp is NULL, we found an insertion on every edge, blank the
784 insertion vector for these edges, and insert at the start of the BB. */
785 if (!tmp && bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
787 FOR_EACH_EDGE (tmp, ei, e->dest->preds)
789 int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
790 bitmap_clear_bit (st_insert_map[index], expr->index);
792 insert_insn_start_basic_block (insn, bb);
793 return 0;
796 /* We can't put stores in the front of blocks pointed to by abnormal
797 edges since that may put a store where one didn't used to be. */
798 gcc_assert (!(e->flags & EDGE_ABNORMAL));
800 insert_insn_on_edge (insn, e);
802 if (dump_file)
804 fprintf (dump_file, "STORE_MOTION insert insn on edge (%d, %d):\n",
805 e->src->index, e->dest->index);
806 print_inline_rtx (dump_file, insn, 6);
807 fprintf (dump_file, "\n");
810 return 1;
813 /* Remove any REG_EQUAL or REG_EQUIV notes containing a reference to the
814 memory location in SMEXPR set in basic block BB.
816 This could be rather expensive. */
818 static void
819 remove_reachable_equiv_notes (basic_block bb, struct st_expr *smexpr)
821 edge_iterator *stack, ei;
822 int sp;
823 edge act;
824 auto_sbitmap visited (last_basic_block_for_fn (cfun));
825 rtx note;
826 rtx_insn *insn;
827 rtx mem = smexpr->pattern;
829 stack = XNEWVEC (edge_iterator, n_basic_blocks_for_fn (cfun));
830 sp = 0;
831 ei = ei_start (bb->succs);
833 bitmap_clear (visited);
835 act = (EDGE_COUNT (ei_container (ei))
836 ? EDGE_I (ei_container (ei), 0)
837 : NULL);
838 for (;;)
840 if (!act)
842 if (!sp)
844 free (stack);
845 return;
847 act = ei_edge (stack[--sp]);
849 bb = act->dest;
851 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
852 || bitmap_bit_p (visited, bb->index))
854 if (!ei_end_p (ei))
855 ei_next (&ei);
856 act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
857 continue;
859 bitmap_set_bit (visited, bb->index);
861 rtx_insn *last;
862 if (bitmap_bit_p (st_antloc[bb->index], smexpr->index))
864 unsigned int i;
865 FOR_EACH_VEC_ELT_REVERSE (smexpr->antic_stores, i, last)
866 if (BLOCK_FOR_INSN (last) == bb)
867 break;
869 else
870 last = NEXT_INSN (BB_END (bb));
872 for (insn = BB_HEAD (bb); insn != last; insn = NEXT_INSN (insn))
873 if (NONDEBUG_INSN_P (insn))
875 note = find_reg_equal_equiv_note (insn);
876 if (!note || !exp_equiv_p (XEXP (note, 0), mem, 0, true))
877 continue;
879 if (dump_file)
880 fprintf (dump_file,
881 "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
882 INSN_UID (insn));
883 remove_note (insn, note);
886 if (!ei_end_p (ei))
887 ei_next (&ei);
888 act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
890 if (EDGE_COUNT (bb->succs) > 0)
892 if (act)
893 stack[sp++] = ei;
894 ei = ei_start (bb->succs);
895 act = (EDGE_COUNT (ei_container (ei))
896 ? EDGE_I (ei_container (ei), 0)
897 : NULL);
902 /* This routine will replace a store with a SET to a specified register. */
904 static void
905 replace_store_insn (rtx reg, rtx_insn *del, basic_block bb,
906 struct st_expr *smexpr)
908 rtx_insn *insn;
909 rtx mem, note, set;
911 insn = prepare_copy_insn (reg, SET_SRC (single_set (del)));
913 unsigned int i;
914 rtx_insn *temp;
915 FOR_EACH_VEC_ELT_REVERSE (smexpr->antic_stores, i, temp)
916 if (temp == del)
918 smexpr->antic_stores[i] = insn;
919 break;
922 /* Move the notes from the deleted insn to its replacement. */
923 REG_NOTES (insn) = REG_NOTES (del);
925 /* Emit the insn AFTER all the notes are transferred.
926 This is cheaper since we avoid df rescanning for the note change. */
927 insn = emit_insn_after (insn, del);
929 if (dump_file)
931 fprintf (dump_file,
932 "STORE_MOTION delete insn in BB %d:\n ", bb->index);
933 print_inline_rtx (dump_file, del, 6);
934 fprintf (dump_file, "\nSTORE_MOTION replaced with insn:\n ");
935 print_inline_rtx (dump_file, insn, 6);
936 fprintf (dump_file, "\n");
939 delete_insn (del);
941 /* Now we must handle REG_EQUAL notes whose contents is equal to the mem;
942 they are no longer accurate provided that they are reached by this
943 definition, so drop them. */
944 mem = smexpr->pattern;
945 for (; insn != NEXT_INSN (BB_END (bb)); insn = NEXT_INSN (insn))
946 if (NONDEBUG_INSN_P (insn))
948 set = single_set (insn);
949 if (!set)
950 continue;
951 if (exp_equiv_p (SET_DEST (set), mem, 0, true))
952 return;
953 note = find_reg_equal_equiv_note (insn);
954 if (!note || !exp_equiv_p (XEXP (note, 0), mem, 0, true))
955 continue;
957 if (dump_file)
958 fprintf (dump_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
959 INSN_UID (insn));
960 remove_note (insn, note);
962 remove_reachable_equiv_notes (bb, smexpr);
966 /* Delete a store, but copy the value that would have been stored into
967 the reaching_reg for later storing. */
969 static void
970 delete_store (struct st_expr * expr, basic_block bb)
972 rtx reg;
974 if (expr->reaching_reg == NULL_RTX)
975 expr->reaching_reg = gen_reg_rtx_and_attrs (expr->pattern);
977 reg = expr->reaching_reg;
979 unsigned int len = expr->avail_stores.length ();
980 for (unsigned int i = len - 1; i < len; i--)
982 rtx_insn *del = expr->avail_stores[i];
983 if (BLOCK_FOR_INSN (del) == bb)
985 /* We know there is only one since we deleted redundant
986 ones during the available computation. */
987 replace_store_insn (reg, del, bb, expr);
988 break;
993 /* Fill in available, anticipatable, transparent and kill vectors in
994 STORE_DATA, based on lists of available and anticipatable stores. */
995 static void
996 build_store_vectors (void)
998 basic_block bb;
999 int *regs_set_in_block;
1000 rtx_insn *insn;
1001 struct st_expr * ptr;
1002 unsigned int max_gcse_regno = max_reg_num ();
1004 /* Build the gen_vector. This is any store in the table which is not killed
1005 by aliasing later in its block. */
1006 st_avloc = sbitmap_vector_alloc (last_basic_block_for_fn (cfun),
1007 num_stores);
1008 bitmap_vector_clear (st_avloc, last_basic_block_for_fn (cfun));
1010 st_antloc = sbitmap_vector_alloc (last_basic_block_for_fn (cfun),
1011 num_stores);
1012 bitmap_vector_clear (st_antloc, last_basic_block_for_fn (cfun));
1014 for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
1016 unsigned int len = ptr->avail_stores.length ();
1017 for (unsigned int i = len - 1; i < len; i--)
1019 insn = ptr->avail_stores[i];
1020 bb = BLOCK_FOR_INSN (insn);
1022 /* If we've already seen an available expression in this block,
1023 we can delete this one (It occurs earlier in the block). We'll
1024 copy the SRC expression to an unused register in case there
1025 are any side effects. */
1026 if (bitmap_bit_p (st_avloc[bb->index], ptr->index))
1028 rtx r = gen_reg_rtx_and_attrs (ptr->pattern);
1029 if (dump_file)
1030 fprintf (dump_file, "Removing redundant store:\n");
1031 replace_store_insn (r, insn, bb, ptr);
1032 continue;
1034 bitmap_set_bit (st_avloc[bb->index], ptr->index);
1037 unsigned int i;
1038 FOR_EACH_VEC_ELT_REVERSE (ptr->antic_stores, i, insn)
1040 bb = BLOCK_FOR_INSN (insn);
1041 bitmap_set_bit (st_antloc[bb->index], ptr->index);
1045 st_kill = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), num_stores);
1046 bitmap_vector_clear (st_kill, last_basic_block_for_fn (cfun));
1048 st_transp = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), num_stores);
1049 bitmap_vector_clear (st_transp, last_basic_block_for_fn (cfun));
1050 regs_set_in_block = XNEWVEC (int, max_gcse_regno);
1052 FOR_EACH_BB_FN (bb, cfun)
1054 memset (regs_set_in_block, 0, sizeof (int) * max_gcse_regno);
1056 FOR_BB_INSNS (bb, insn)
1057 if (NONDEBUG_INSN_P (insn))
1059 df_ref def;
1060 FOR_EACH_INSN_DEF (def, insn)
1062 unsigned int ref_regno = DF_REF_REGNO (def);
1063 if (ref_regno < max_gcse_regno)
1064 regs_set_in_block[DF_REF_REGNO (def)] = 1;
1068 for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
1070 if (store_killed_after (ptr->pattern, ptr->pattern_regs, BB_HEAD (bb),
1071 bb, regs_set_in_block, NULL))
1073 /* It should not be necessary to consider the expression
1074 killed if it is both anticipatable and available. */
1075 if (!bitmap_bit_p (st_antloc[bb->index], ptr->index)
1076 || !bitmap_bit_p (st_avloc[bb->index], ptr->index))
1077 bitmap_set_bit (st_kill[bb->index], ptr->index);
1079 else
1080 bitmap_set_bit (st_transp[bb->index], ptr->index);
1084 free (regs_set_in_block);
1086 if (dump_file)
1088 dump_bitmap_vector (dump_file, "st_antloc", "", st_antloc,
1089 last_basic_block_for_fn (cfun));
1090 dump_bitmap_vector (dump_file, "st_kill", "", st_kill,
1091 last_basic_block_for_fn (cfun));
1092 dump_bitmap_vector (dump_file, "st_transp", "", st_transp,
1093 last_basic_block_for_fn (cfun));
1094 dump_bitmap_vector (dump_file, "st_avloc", "", st_avloc,
1095 last_basic_block_for_fn (cfun));
1099 /* Free memory used by store motion. */
1101 static void
1102 free_store_memory (void)
1104 free_store_motion_mems ();
1106 if (st_avloc)
1107 sbitmap_vector_free (st_avloc);
1108 if (st_kill)
1109 sbitmap_vector_free (st_kill);
1110 if (st_transp)
1111 sbitmap_vector_free (st_transp);
1112 if (st_antloc)
1113 sbitmap_vector_free (st_antloc);
1114 if (st_insert_map)
1115 sbitmap_vector_free (st_insert_map);
1116 if (st_delete_map)
1117 sbitmap_vector_free (st_delete_map);
1119 st_avloc = st_kill = st_transp = st_antloc = NULL;
1120 st_insert_map = st_delete_map = NULL;
1123 /* Perform store motion. Much like gcse, except we move expressions the
1124 other way by looking at the flowgraph in reverse.
1125 Return non-zero if transformations are performed by the pass. */
1127 static int
1128 one_store_motion_pass (void)
1130 basic_block bb;
1131 int x;
1132 struct st_expr * ptr;
1133 int did_edge_inserts = 0;
1134 int n_stores_deleted = 0;
1135 int n_stores_created = 0;
1137 init_alias_analysis ();
1139 /* Find all the available and anticipatable stores. */
1140 num_stores = compute_store_table ();
1141 if (num_stores == 0)
1143 delete store_motion_mems_table;
1144 store_motion_mems_table = NULL;
1145 end_alias_analysis ();
1146 return 0;
1149 /* Now compute kill & transp vectors. */
1150 build_store_vectors ();
1151 connect_infinite_loops_to_exit ();
1153 edge_list = pre_edge_rev_lcm (num_stores, st_transp, st_avloc,
1154 st_antloc, st_kill, &st_insert_map,
1155 &st_delete_map);
1157 /* Now we want to insert the new stores which are going to be needed. */
1158 for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
1160 /* If any of the edges we have above are abnormal, we can't move this
1161 store. */
1162 for (x = NUM_EDGES (edge_list) - 1; x >= 0; x--)
1163 if (bitmap_bit_p (st_insert_map[x], ptr->index)
1164 && (INDEX_EDGE (edge_list, x)->flags & EDGE_ABNORMAL))
1165 break;
1167 if (x >= 0)
1169 if (dump_file != NULL)
1170 fprintf (dump_file,
1171 "Can't replace store %d: abnormal edge from %d to %d\n",
1172 ptr->index, INDEX_EDGE (edge_list, x)->src->index,
1173 INDEX_EDGE (edge_list, x)->dest->index);
1174 continue;
1177 /* Now we want to insert the new stores which are going to be needed. */
1179 FOR_EACH_BB_FN (bb, cfun)
1180 if (bitmap_bit_p (st_delete_map[bb->index], ptr->index))
1182 delete_store (ptr, bb);
1183 n_stores_deleted++;
1186 for (x = 0; x < NUM_EDGES (edge_list); x++)
1187 if (bitmap_bit_p (st_insert_map[x], ptr->index))
1189 did_edge_inserts |= insert_store (ptr, INDEX_EDGE (edge_list, x));
1190 n_stores_created++;
1194 if (did_edge_inserts)
1195 commit_edge_insertions ();
1197 free_store_memory ();
1198 free_edge_list (edge_list);
1199 remove_fake_exit_edges ();
1200 end_alias_analysis ();
1202 if (dump_file)
1204 fprintf (dump_file, "STORE_MOTION of %s, %d basic blocks, ",
1205 current_function_name (), n_basic_blocks_for_fn (cfun));
1206 fprintf (dump_file, "%d insns deleted, %d insns created\n",
1207 n_stores_deleted, n_stores_created);
1210 return (n_stores_deleted > 0 || n_stores_created > 0);
1214 static unsigned int
1215 execute_rtl_store_motion (void)
1217 delete_unreachable_blocks ();
1218 df_analyze ();
1219 flag_rerun_cse_after_global_opts |= one_store_motion_pass ();
1220 return 0;
1223 namespace {
1225 const pass_data pass_data_rtl_store_motion =
1227 RTL_PASS, /* type */
1228 "store_motion", /* name */
1229 OPTGROUP_NONE, /* optinfo_flags */
1230 TV_LSM, /* tv_id */
1231 PROP_cfglayout, /* properties_required */
1232 0, /* properties_provided */
1233 0, /* properties_destroyed */
1234 0, /* todo_flags_start */
1235 TODO_df_finish, /* todo_flags_finish */
1238 class pass_rtl_store_motion : public rtl_opt_pass
1240 public:
1241 pass_rtl_store_motion (gcc::context *ctxt)
1242 : rtl_opt_pass (pass_data_rtl_store_motion, ctxt)
1245 /* opt_pass methods: */
1246 bool gate (function *) final override;
1247 unsigned int execute (function *) final override
1249 return execute_rtl_store_motion ();
1252 }; // class pass_rtl_store_motion
1254 bool
1255 pass_rtl_store_motion::gate (function *fun)
1257 return optimize > 0 && flag_gcse_sm
1258 && !fun->calls_setjmp
1259 && optimize_function_for_speed_p (fun)
1260 && dbg_cnt (store_motion);
1263 } // anon namespace
1265 rtl_opt_pass *
1266 make_pass_rtl_store_motion (gcc::context *ctxt)
1268 return new pass_rtl_store_motion (ctxt);