138fd1498Szrj /* Store motion via Lazy Code Motion on the reverse CFG.
238fd1498Szrj Copyright (C) 1997-2018 Free Software Foundation, Inc.
338fd1498Szrj
438fd1498Szrj This file is part of GCC.
538fd1498Szrj
638fd1498Szrj GCC is free software; you can redistribute it and/or modify it under
738fd1498Szrj the terms of the GNU General Public License as published by the Free
838fd1498Szrj Software Foundation; either version 3, or (at your option) any later
938fd1498Szrj version.
1038fd1498Szrj
1138fd1498Szrj GCC is distributed in the hope that it will be useful, but WITHOUT ANY
1238fd1498Szrj WARRANTY; without even the implied warranty of MERCHANTABILITY or
1338fd1498Szrj FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1438fd1498Szrj for more details.
1538fd1498Szrj
1638fd1498Szrj You should have received a copy of the GNU General Public License
1738fd1498Szrj along with GCC; see the file COPYING3. If not see
1838fd1498Szrj <http://www.gnu.org/licenses/>. */
1938fd1498Szrj
2038fd1498Szrj #include "config.h"
2138fd1498Szrj #include "system.h"
2238fd1498Szrj #include "coretypes.h"
2338fd1498Szrj #include "backend.h"
2438fd1498Szrj #include "rtl.h"
2538fd1498Szrj #include "tree.h"
2638fd1498Szrj #include "predict.h"
2738fd1498Szrj #include "df.h"
2838fd1498Szrj #include "toplev.h"
2938fd1498Szrj
3038fd1498Szrj #include "cfgrtl.h"
3138fd1498Szrj #include "cfganal.h"
3238fd1498Szrj #include "lcm.h"
3338fd1498Szrj #include "cfgcleanup.h"
3438fd1498Szrj #include "expr.h"
3538fd1498Szrj #include "tree-pass.h"
3638fd1498Szrj #include "dbgcnt.h"
3738fd1498Szrj #include "rtl-iter.h"
3838fd1498Szrj #include "print-rtl.h"
3938fd1498Szrj
4038fd1498Szrj /* This pass implements downward store motion.
4138fd1498Szrj As of May 1, 2009, the pass is not enabled by default on any target,
4238fd1498Szrj but bootstrap completes on ia64 and x86_64 with the pass enabled. */
4338fd1498Szrj
4438fd1498Szrj /* TODO:
4538fd1498Szrj - remove_reachable_equiv_notes is an incomprehensible pile of goo and
4638fd1498Szrj a compile time hog that needs a rewrite (maybe cache st_exprs to
4738fd1498Szrj invalidate REG_EQUAL/REG_EQUIV notes for?).
4838fd1498Szrj - pattern_regs in st_expr should be a regset (on its own obstack).
4938fd1498Szrj - store_motion_mems should be a vec instead of a list.
5038fd1498Szrj - there should be an alloc pool for struct st_expr objects.
5138fd1498Szrj - investigate whether it is helpful to make the address of an st_expr
5238fd1498Szrj a cselib VALUE.
5338fd1498Szrj - when GIMPLE alias information is exported, the effectiveness of this
5438fd1498Szrj pass should be re-evaluated.
5538fd1498Szrj */
5638fd1498Szrj
5738fd1498Szrj /* This is a list of store expressions (MEMs). The structure is used
5838fd1498Szrj as an expression table to track stores which look interesting, and
5938fd1498Szrj might be moveable towards the exit block. */
6038fd1498Szrj
6138fd1498Szrj struct st_expr
6238fd1498Szrj {
6338fd1498Szrj /* Pattern of this mem. */
6438fd1498Szrj rtx pattern;
6538fd1498Szrj /* List of registers mentioned by the mem. */
6638fd1498Szrj vec<rtx> pattern_regs;
6738fd1498Szrj /* INSN list of stores that are locally anticipatable. */
6838fd1498Szrj vec<rtx_insn *> antic_stores;
6938fd1498Szrj /* INSN list of stores that are locally available. */
7038fd1498Szrj vec<rtx_insn *> avail_stores;
7138fd1498Szrj /* Next in the list. */
7238fd1498Szrj struct st_expr * next;
7338fd1498Szrj /* Store ID in the dataflow bitmaps. */
7438fd1498Szrj int index;
7538fd1498Szrj /* Hash value for the hash table. */
7638fd1498Szrj unsigned int hash_index;
7738fd1498Szrj /* Register holding the stored expression when a store is moved.
7838fd1498Szrj This field is also used as a cache in find_moveable_store, see
7938fd1498Szrj LAST_AVAIL_CHECK_FAILURE below. */
8038fd1498Szrj rtx reaching_reg;
8138fd1498Szrj };
8238fd1498Szrj
8338fd1498Szrj /* Head of the list of load/store memory refs. */
8438fd1498Szrj static struct st_expr * store_motion_mems = NULL;
8538fd1498Szrj
8638fd1498Szrj /* These bitmaps will hold the local dataflow properties per basic block. */
8738fd1498Szrj static sbitmap *st_kill, *st_avloc, *st_antloc, *st_transp;
8838fd1498Szrj
8938fd1498Szrj /* Nonzero for expressions which should be inserted on a specific edge. */
9038fd1498Szrj static sbitmap *st_insert_map;
9138fd1498Szrj
9238fd1498Szrj /* Nonzero for expressions which should be deleted in a specific block. */
9338fd1498Szrj static sbitmap *st_delete_map;
9438fd1498Szrj
9538fd1498Szrj /* Global holding the number of store expressions we are dealing with. */
9638fd1498Szrj static int num_stores;
9738fd1498Szrj
9838fd1498Szrj /* Contains the edge_list returned by pre_edge_lcm. */
9938fd1498Szrj static struct edge_list *edge_list;
10038fd1498Szrj
10138fd1498Szrj /* Hashtable helpers. */
10238fd1498Szrj
10338fd1498Szrj struct st_expr_hasher : nofree_ptr_hash <st_expr>
10438fd1498Szrj {
10538fd1498Szrj static inline hashval_t hash (const st_expr *);
10638fd1498Szrj static inline bool equal (const st_expr *, const st_expr *);
10738fd1498Szrj };
10838fd1498Szrj
10938fd1498Szrj inline hashval_t
hash(const st_expr * x)11038fd1498Szrj st_expr_hasher::hash (const st_expr *x)
11138fd1498Szrj {
11238fd1498Szrj int do_not_record_p = 0;
11338fd1498Szrj return hash_rtx (x->pattern, GET_MODE (x->pattern), &do_not_record_p, NULL, false);
11438fd1498Szrj }
11538fd1498Szrj
11638fd1498Szrj inline bool
equal(const st_expr * ptr1,const st_expr * ptr2)11738fd1498Szrj st_expr_hasher::equal (const st_expr *ptr1, const st_expr *ptr2)
11838fd1498Szrj {
11938fd1498Szrj return exp_equiv_p (ptr1->pattern, ptr2->pattern, 0, true);
12038fd1498Szrj }
12138fd1498Szrj
12238fd1498Szrj /* Hashtable for the load/store memory refs. */
12338fd1498Szrj static hash_table<st_expr_hasher> *store_motion_mems_table;
12438fd1498Szrj
12538fd1498Szrj /* This will search the st_expr list for a matching expression. If it
12638fd1498Szrj doesn't find one, we create one and initialize it. */
12738fd1498Szrj
12838fd1498Szrj static struct st_expr *
st_expr_entry(rtx x)12938fd1498Szrj st_expr_entry (rtx x)
13038fd1498Szrj {
13138fd1498Szrj int do_not_record_p = 0;
13238fd1498Szrj struct st_expr * ptr;
13338fd1498Szrj unsigned int hash;
13438fd1498Szrj st_expr **slot;
13538fd1498Szrj struct st_expr e;
13638fd1498Szrj
13738fd1498Szrj hash = hash_rtx (x, GET_MODE (x), &do_not_record_p,
13838fd1498Szrj NULL, /*have_reg_qty=*/false);
13938fd1498Szrj
14038fd1498Szrj e.pattern = x;
14138fd1498Szrj slot = store_motion_mems_table->find_slot_with_hash (&e, hash, INSERT);
14238fd1498Szrj if (*slot)
14338fd1498Szrj return *slot;
14438fd1498Szrj
14538fd1498Szrj ptr = XNEW (struct st_expr);
14638fd1498Szrj
14738fd1498Szrj ptr->next = store_motion_mems;
14838fd1498Szrj ptr->pattern = x;
14938fd1498Szrj ptr->pattern_regs.create (0);
15038fd1498Szrj ptr->antic_stores.create (0);
15138fd1498Szrj ptr->avail_stores.create (0);
15238fd1498Szrj ptr->reaching_reg = NULL_RTX;
15338fd1498Szrj ptr->index = 0;
15438fd1498Szrj ptr->hash_index = hash;
15538fd1498Szrj store_motion_mems = ptr;
15638fd1498Szrj *slot = ptr;
15738fd1498Szrj
15838fd1498Szrj return ptr;
15938fd1498Szrj }
16038fd1498Szrj
16138fd1498Szrj /* Free up an individual st_expr entry. */
16238fd1498Szrj
16338fd1498Szrj static void
free_st_expr_entry(struct st_expr * ptr)16438fd1498Szrj free_st_expr_entry (struct st_expr * ptr)
16538fd1498Szrj {
16638fd1498Szrj ptr->antic_stores.release ();
16738fd1498Szrj ptr->avail_stores.release ();
16838fd1498Szrj ptr->pattern_regs.release ();
16938fd1498Szrj
17038fd1498Szrj free (ptr);
17138fd1498Szrj }
17238fd1498Szrj
17338fd1498Szrj /* Free up all memory associated with the st_expr list. */
17438fd1498Szrj
17538fd1498Szrj static void
free_store_motion_mems(void)17638fd1498Szrj free_store_motion_mems (void)
17738fd1498Szrj {
17838fd1498Szrj delete store_motion_mems_table;
17938fd1498Szrj store_motion_mems_table = NULL;
18038fd1498Szrj
18138fd1498Szrj while (store_motion_mems)
18238fd1498Szrj {
18338fd1498Szrj struct st_expr * tmp = store_motion_mems;
18438fd1498Szrj store_motion_mems = store_motion_mems->next;
18538fd1498Szrj free_st_expr_entry (tmp);
18638fd1498Szrj }
18738fd1498Szrj store_motion_mems = NULL;
18838fd1498Szrj }
18938fd1498Szrj
19038fd1498Szrj /* Assign each element of the list of mems a monotonically increasing value. */
19138fd1498Szrj
19238fd1498Szrj static int
enumerate_store_motion_mems(void)19338fd1498Szrj enumerate_store_motion_mems (void)
19438fd1498Szrj {
19538fd1498Szrj struct st_expr * ptr;
19638fd1498Szrj int n = 0;
19738fd1498Szrj
19838fd1498Szrj for (ptr = store_motion_mems; ptr != NULL; ptr = ptr->next)
19938fd1498Szrj ptr->index = n++;
20038fd1498Szrj
20138fd1498Szrj return n;
20238fd1498Szrj }
20338fd1498Szrj
20438fd1498Szrj /* Return first item in the list. */
20538fd1498Szrj
20638fd1498Szrj static inline struct st_expr *
first_st_expr(void)20738fd1498Szrj first_st_expr (void)
20838fd1498Szrj {
20938fd1498Szrj return store_motion_mems;
21038fd1498Szrj }
21138fd1498Szrj
21238fd1498Szrj /* Return the next item in the list after the specified one. */
21338fd1498Szrj
21438fd1498Szrj static inline struct st_expr *
next_st_expr(struct st_expr * ptr)21538fd1498Szrj next_st_expr (struct st_expr * ptr)
21638fd1498Szrj {
21738fd1498Szrj return ptr->next;
21838fd1498Szrj }
21938fd1498Szrj
22038fd1498Szrj /* Dump debugging info about the store_motion_mems list. */
22138fd1498Szrj
22238fd1498Szrj static void
print_store_motion_mems(FILE * file)22338fd1498Szrj print_store_motion_mems (FILE * file)
22438fd1498Szrj {
22538fd1498Szrj struct st_expr * ptr;
22638fd1498Szrj
22738fd1498Szrj fprintf (dump_file, "STORE_MOTION list of MEM exprs considered:\n");
22838fd1498Szrj
22938fd1498Szrj for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
23038fd1498Szrj {
23138fd1498Szrj fprintf (file, " Pattern (%3d): ", ptr->index);
23238fd1498Szrj
23338fd1498Szrj print_rtl (file, ptr->pattern);
23438fd1498Szrj
23538fd1498Szrj fprintf (file, "\n ANTIC stores : ");
23638fd1498Szrj print_rtx_insn_vec (file, ptr->antic_stores);
23738fd1498Szrj
23838fd1498Szrj fprintf (file, "\n AVAIL stores : ");
23938fd1498Szrj
24038fd1498Szrj print_rtx_insn_vec (file, ptr->avail_stores);
24138fd1498Szrj
24238fd1498Szrj fprintf (file, "\n\n");
24338fd1498Szrj }
24438fd1498Szrj
24538fd1498Szrj fprintf (file, "\n");
24638fd1498Szrj }
24738fd1498Szrj
24838fd1498Szrj /* Return zero if some of the registers in list X are killed
24938fd1498Szrj due to set of registers in bitmap REGS_SET. */
25038fd1498Szrj
25138fd1498Szrj static bool
store_ops_ok(const vec<rtx> & x,int * regs_set)25238fd1498Szrj store_ops_ok (const vec<rtx> &x, int *regs_set)
25338fd1498Szrj {
25438fd1498Szrj unsigned int i;
25538fd1498Szrj rtx temp;
25638fd1498Szrj FOR_EACH_VEC_ELT (x, i, temp)
25738fd1498Szrj if (regs_set[REGNO (temp)])
25838fd1498Szrj return false;
25938fd1498Szrj
26038fd1498Szrj return true;
26138fd1498Szrj }
26238fd1498Szrj
26338fd1498Szrj /* Returns a list of registers mentioned in X.
26438fd1498Szrj FIXME: A regset would be prettier and less expensive. */
26538fd1498Szrj
26638fd1498Szrj static void
extract_mentioned_regs(rtx x,vec<rtx> * mentioned_regs)26738fd1498Szrj extract_mentioned_regs (rtx x, vec<rtx> *mentioned_regs)
26838fd1498Szrj {
26938fd1498Szrj subrtx_var_iterator::array_type array;
27038fd1498Szrj FOR_EACH_SUBRTX_VAR (iter, array, x, NONCONST)
27138fd1498Szrj {
27238fd1498Szrj rtx x = *iter;
27338fd1498Szrj if (REG_P (x))
27438fd1498Szrj mentioned_regs->safe_push (x);
27538fd1498Szrj }
27638fd1498Szrj }
27738fd1498Szrj
27838fd1498Szrj /* Check to see if the load X is aliased with STORE_PATTERN.
27938fd1498Szrj AFTER is true if we are checking the case when STORE_PATTERN occurs
28038fd1498Szrj after the X. */
28138fd1498Szrj
28238fd1498Szrj static bool
load_kills_store(const_rtx x,const_rtx store_pattern,int after)28338fd1498Szrj load_kills_store (const_rtx x, const_rtx store_pattern, int after)
28438fd1498Szrj {
28538fd1498Szrj if (after)
28638fd1498Szrj return anti_dependence (x, store_pattern);
28738fd1498Szrj else
28838fd1498Szrj return true_dependence (store_pattern, GET_MODE (store_pattern), x);
28938fd1498Szrj }
29038fd1498Szrj
29138fd1498Szrj /* Go through the entire rtx X, looking for any loads which might alias
29238fd1498Szrj STORE_PATTERN. Return true if found.
29338fd1498Szrj AFTER is true if we are checking the case when STORE_PATTERN occurs
29438fd1498Szrj after the insn X. */
29538fd1498Szrj
29638fd1498Szrj static bool
find_loads(const_rtx x,const_rtx store_pattern,int after)29738fd1498Szrj find_loads (const_rtx x, const_rtx store_pattern, int after)
29838fd1498Szrj {
29938fd1498Szrj const char * fmt;
30038fd1498Szrj int i, j;
30138fd1498Szrj int ret = false;
30238fd1498Szrj
30338fd1498Szrj if (!x)
30438fd1498Szrj return false;
30538fd1498Szrj
30638fd1498Szrj if (GET_CODE (x) == SET)
30738fd1498Szrj x = SET_SRC (x);
30838fd1498Szrj
30938fd1498Szrj if (MEM_P (x))
31038fd1498Szrj {
31138fd1498Szrj if (load_kills_store (x, store_pattern, after))
31238fd1498Szrj return true;
31338fd1498Szrj }
31438fd1498Szrj
31538fd1498Szrj /* Recursively process the insn. */
31638fd1498Szrj fmt = GET_RTX_FORMAT (GET_CODE (x));
31738fd1498Szrj
31838fd1498Szrj for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0 && !ret; i--)
31938fd1498Szrj {
32038fd1498Szrj if (fmt[i] == 'e')
32138fd1498Szrj ret |= find_loads (XEXP (x, i), store_pattern, after);
32238fd1498Szrj else if (fmt[i] == 'E')
32338fd1498Szrj for (j = XVECLEN (x, i) - 1; j >= 0; j--)
32438fd1498Szrj ret |= find_loads (XVECEXP (x, i, j), store_pattern, after);
32538fd1498Szrj }
32638fd1498Szrj return ret;
32738fd1498Szrj }
32838fd1498Szrj
32938fd1498Szrj /* Go through pattern PAT looking for any loads which might kill the
33038fd1498Szrj store in X. Return true if found.
33138fd1498Szrj AFTER is true if we are checking the case when loads kill X occurs
33238fd1498Szrj after the insn for PAT. */
33338fd1498Szrj
33438fd1498Szrj static inline bool
store_killed_in_pat(const_rtx x,const_rtx pat,int after)33538fd1498Szrj store_killed_in_pat (const_rtx x, const_rtx pat, int after)
33638fd1498Szrj {
33738fd1498Szrj if (GET_CODE (pat) == SET)
33838fd1498Szrj {
33938fd1498Szrj rtx dest = SET_DEST (pat);
34038fd1498Szrj
34138fd1498Szrj if (GET_CODE (dest) == ZERO_EXTRACT)
34238fd1498Szrj dest = XEXP (dest, 0);
34338fd1498Szrj
34438fd1498Szrj /* Check for memory stores to aliased objects. */
34538fd1498Szrj if (MEM_P (dest)
34638fd1498Szrj && !exp_equiv_p (dest, x, 0, true))
34738fd1498Szrj {
34838fd1498Szrj if (after)
34938fd1498Szrj {
35038fd1498Szrj if (output_dependence (dest, x))
35138fd1498Szrj return true;
35238fd1498Szrj }
35338fd1498Szrj else
35438fd1498Szrj {
35538fd1498Szrj if (output_dependence (x, dest))
35638fd1498Szrj return true;
35738fd1498Szrj }
35838fd1498Szrj }
35938fd1498Szrj }
36038fd1498Szrj
36138fd1498Szrj if (find_loads (pat, x, after))
36238fd1498Szrj return true;
36338fd1498Szrj
36438fd1498Szrj return false;
36538fd1498Szrj }
36638fd1498Szrj
36738fd1498Szrj /* Check if INSN kills the store pattern X (is aliased with it).
36838fd1498Szrj AFTER is true if we are checking the case when store X occurs
36938fd1498Szrj after the insn. Return true if it does. */
37038fd1498Szrj
37138fd1498Szrj static bool
store_killed_in_insn(const_rtx x,const vec<rtx> & x_regs,const rtx_insn * insn,int after)37238fd1498Szrj store_killed_in_insn (const_rtx x, const vec<rtx> &x_regs,
37338fd1498Szrj const rtx_insn *insn, int after)
37438fd1498Szrj {
37538fd1498Szrj const_rtx note, pat;
37638fd1498Szrj
37738fd1498Szrj if (! NONDEBUG_INSN_P (insn))
37838fd1498Szrj return false;
37938fd1498Szrj
38038fd1498Szrj if (CALL_P (insn))
38138fd1498Szrj {
38238fd1498Szrj /* A normal or pure call might read from pattern,
38338fd1498Szrj but a const call will not. */
38438fd1498Szrj if (!RTL_CONST_CALL_P (insn))
38538fd1498Szrj return true;
38638fd1498Szrj
38738fd1498Szrj /* But even a const call reads its parameters. Check whether the
38838fd1498Szrj base of some of registers used in mem is stack pointer. */
38938fd1498Szrj rtx temp;
39038fd1498Szrj unsigned int i;
39138fd1498Szrj FOR_EACH_VEC_ELT (x_regs, i, temp)
39238fd1498Szrj if (may_be_sp_based_p (temp))
39338fd1498Szrj return true;
39438fd1498Szrj
39538fd1498Szrj return false;
39638fd1498Szrj }
39738fd1498Szrj
39838fd1498Szrj pat = PATTERN (insn);
39938fd1498Szrj if (GET_CODE (pat) == SET)
40038fd1498Szrj {
40138fd1498Szrj if (store_killed_in_pat (x, pat, after))
40238fd1498Szrj return true;
40338fd1498Szrj }
40438fd1498Szrj else if (GET_CODE (pat) == PARALLEL)
40538fd1498Szrj {
40638fd1498Szrj int i;
40738fd1498Szrj
40838fd1498Szrj for (i = 0; i < XVECLEN (pat, 0); i++)
40938fd1498Szrj if (store_killed_in_pat (x, XVECEXP (pat, 0, i), after))
41038fd1498Szrj return true;
41138fd1498Szrj }
41238fd1498Szrj else if (find_loads (PATTERN (insn), x, after))
41338fd1498Szrj return true;
41438fd1498Szrj
41538fd1498Szrj /* If this insn has a REG_EQUAL or REG_EQUIV note referencing a memory
41638fd1498Szrj location aliased with X, then this insn kills X. */
41738fd1498Szrj note = find_reg_equal_equiv_note (insn);
41838fd1498Szrj if (! note)
41938fd1498Szrj return false;
42038fd1498Szrj note = XEXP (note, 0);
42138fd1498Szrj
42238fd1498Szrj /* However, if the note represents a must alias rather than a may
42338fd1498Szrj alias relationship, then it does not kill X. */
42438fd1498Szrj if (exp_equiv_p (note, x, 0, true))
42538fd1498Szrj return false;
42638fd1498Szrj
42738fd1498Szrj /* See if there are any aliased loads in the note. */
42838fd1498Szrj return find_loads (note, x, after);
42938fd1498Szrj }
43038fd1498Szrj
43138fd1498Szrj /* Returns true if the expression X is loaded or clobbered on or after INSN
43238fd1498Szrj within basic block BB. REGS_SET_AFTER is bitmap of registers set in
43338fd1498Szrj or after the insn. X_REGS is list of registers mentioned in X. If the store
43438fd1498Szrj is killed, return the last insn in that it occurs in FAIL_INSN. */
43538fd1498Szrj
43638fd1498Szrj static bool
store_killed_after(const_rtx x,const vec<rtx> & x_regs,const rtx_insn * insn,const_basic_block bb,int * regs_set_after,rtx * fail_insn)43738fd1498Szrj store_killed_after (const_rtx x, const vec<rtx> &x_regs,
43838fd1498Szrj const rtx_insn *insn, const_basic_block bb,
43938fd1498Szrj int *regs_set_after, rtx *fail_insn)
44038fd1498Szrj {
44138fd1498Szrj rtx_insn *last = BB_END (bb), *act;
44238fd1498Szrj
44338fd1498Szrj if (!store_ops_ok (x_regs, regs_set_after))
44438fd1498Szrj {
44538fd1498Szrj /* We do not know where it will happen. */
44638fd1498Szrj if (fail_insn)
44738fd1498Szrj *fail_insn = NULL_RTX;
44838fd1498Szrj return true;
44938fd1498Szrj }
45038fd1498Szrj
45138fd1498Szrj /* Scan from the end, so that fail_insn is determined correctly. */
45238fd1498Szrj for (act = last; act != PREV_INSN (insn); act = PREV_INSN (act))
45338fd1498Szrj if (store_killed_in_insn (x, x_regs, act, false))
45438fd1498Szrj {
45538fd1498Szrj if (fail_insn)
45638fd1498Szrj *fail_insn = act;
45738fd1498Szrj return true;
45838fd1498Szrj }
45938fd1498Szrj
46038fd1498Szrj return false;
46138fd1498Szrj }
46238fd1498Szrj
46338fd1498Szrj /* Returns true if the expression X is loaded or clobbered on or before INSN
46438fd1498Szrj within basic block BB. X_REGS is list of registers mentioned in X.
46538fd1498Szrj REGS_SET_BEFORE is bitmap of registers set before or in this insn. */
46638fd1498Szrj static bool
store_killed_before(const_rtx x,const vec<rtx> & x_regs,const rtx_insn * insn,const_basic_block bb,int * regs_set_before)46738fd1498Szrj store_killed_before (const_rtx x, const vec<rtx> &x_regs,
46838fd1498Szrj const rtx_insn *insn, const_basic_block bb,
46938fd1498Szrj int *regs_set_before)
47038fd1498Szrj {
47138fd1498Szrj rtx_insn *first = BB_HEAD (bb);
47238fd1498Szrj
47338fd1498Szrj if (!store_ops_ok (x_regs, regs_set_before))
47438fd1498Szrj return true;
47538fd1498Szrj
47638fd1498Szrj for ( ; insn != PREV_INSN (first); insn = PREV_INSN (insn))
47738fd1498Szrj if (store_killed_in_insn (x, x_regs, insn, true))
47838fd1498Szrj return true;
47938fd1498Szrj
48038fd1498Szrj return false;
48138fd1498Szrj }
48238fd1498Szrj
48338fd1498Szrj /* The last insn in the basic block that compute_store_table is processing,
48438fd1498Szrj where store_killed_after is true for X.
48538fd1498Szrj Since we go through the basic block from BB_END to BB_HEAD, this is
48638fd1498Szrj also the available store at the end of the basic block. Therefore
48738fd1498Szrj this is in effect a cache, to avoid calling store_killed_after for
48838fd1498Szrj equivalent aliasing store expressions.
48938fd1498Szrj This value is only meaningful during the computation of the store
49038fd1498Szrj table. We hi-jack the REACHING_REG field of struct st_expr to save
49138fd1498Szrj a bit of memory. */
49238fd1498Szrj #define LAST_AVAIL_CHECK_FAILURE(x) ((x)->reaching_reg)
49338fd1498Szrj
49438fd1498Szrj /* Determine whether INSN is MEM store pattern that we will consider moving.
49538fd1498Szrj REGS_SET_BEFORE is bitmap of registers set before (and including) the
49638fd1498Szrj current insn, REGS_SET_AFTER is bitmap of registers set after (and
49738fd1498Szrj including) the insn in this basic block. We must be passing through BB from
49838fd1498Szrj head to end, as we are using this fact to speed things up.
49938fd1498Szrj
50038fd1498Szrj The results are stored this way:
50138fd1498Szrj
50238fd1498Szrj -- the first anticipatable expression is added into ANTIC_STORES
50338fd1498Szrj -- if the processed expression is not anticipatable, NULL_RTX is added
50438fd1498Szrj there instead, so that we can use it as indicator that no further
50538fd1498Szrj expression of this type may be anticipatable
50638fd1498Szrj -- if the expression is available, it is added as head of AVAIL_STORES;
50738fd1498Szrj consequently, all of them but this head are dead and may be deleted.
50838fd1498Szrj -- if the expression is not available, the insn due to that it fails to be
50938fd1498Szrj available is stored in REACHING_REG (via LAST_AVAIL_CHECK_FAILURE).
51038fd1498Szrj
51138fd1498Szrj The things are complicated a bit by fact that there already may be stores
51238fd1498Szrj to the same MEM from other blocks; also caller must take care of the
51338fd1498Szrj necessary cleanup of the temporary markers after end of the basic block.
51438fd1498Szrj */
51538fd1498Szrj
51638fd1498Szrj static void
find_moveable_store(rtx_insn * insn,int * regs_set_before,int * regs_set_after)51738fd1498Szrj find_moveable_store (rtx_insn *insn, int *regs_set_before, int *regs_set_after)
51838fd1498Szrj {
51938fd1498Szrj struct st_expr * ptr;
52038fd1498Szrj rtx dest, set;
52138fd1498Szrj int check_anticipatable, check_available;
52238fd1498Szrj basic_block bb = BLOCK_FOR_INSN (insn);
52338fd1498Szrj
52438fd1498Szrj set = single_set (insn);
52538fd1498Szrj if (!set)
52638fd1498Szrj return;
52738fd1498Szrj
52838fd1498Szrj dest = SET_DEST (set);
52938fd1498Szrj
53038fd1498Szrj if (! MEM_P (dest) || MEM_VOLATILE_P (dest)
53138fd1498Szrj || GET_MODE (dest) == BLKmode)
53238fd1498Szrj return;
53338fd1498Szrj
53438fd1498Szrj if (side_effects_p (dest))
53538fd1498Szrj return;
53638fd1498Szrj
53738fd1498Szrj /* If we are handling exceptions, we must be careful with memory references
53838fd1498Szrj that may trap. If we are not, the behavior is undefined, so we may just
53938fd1498Szrj continue. */
54038fd1498Szrj if (cfun->can_throw_non_call_exceptions && may_trap_p (dest))
54138fd1498Szrj return;
54238fd1498Szrj
54338fd1498Szrj /* Even if the destination cannot trap, the source may. In this case we'd
54438fd1498Szrj need to handle updating the REG_EH_REGION note. */
54538fd1498Szrj if (find_reg_note (insn, REG_EH_REGION, NULL_RTX))
54638fd1498Szrj return;
54738fd1498Szrj
54838fd1498Szrj /* Make sure that the SET_SRC of this store insns can be assigned to
54938fd1498Szrj a register, or we will fail later on in replace_store_insn, which
55038fd1498Szrj assumes that we can do this. But sometimes the target machine has
55138fd1498Szrj oddities like MEM read-modify-write instruction. See for example
55238fd1498Szrj PR24257. */
55338fd1498Szrj if (!can_assign_to_reg_without_clobbers_p (SET_SRC (set),
55438fd1498Szrj GET_MODE (SET_SRC (set))))
55538fd1498Szrj return;
55638fd1498Szrj
55738fd1498Szrj ptr = st_expr_entry (dest);
55838fd1498Szrj if (ptr->pattern_regs.is_empty ())
55938fd1498Szrj extract_mentioned_regs (dest, &ptr->pattern_regs);
56038fd1498Szrj
56138fd1498Szrj /* Do not check for anticipatability if we either found one anticipatable
56238fd1498Szrj store already, or tested for one and found out that it was killed. */
56338fd1498Szrj check_anticipatable = 0;
56438fd1498Szrj if (ptr->antic_stores.is_empty ())
56538fd1498Szrj check_anticipatable = 1;
56638fd1498Szrj else
56738fd1498Szrj {
56838fd1498Szrj rtx_insn *tmp = ptr->antic_stores.last ();
56938fd1498Szrj if (tmp != NULL_RTX
57038fd1498Szrj && BLOCK_FOR_INSN (tmp) != bb)
57138fd1498Szrj check_anticipatable = 1;
57238fd1498Szrj }
57338fd1498Szrj if (check_anticipatable)
57438fd1498Szrj {
57538fd1498Szrj rtx_insn *tmp;
57638fd1498Szrj if (store_killed_before (dest, ptr->pattern_regs, insn, bb, regs_set_before))
57738fd1498Szrj tmp = NULL;
57838fd1498Szrj else
57938fd1498Szrj tmp = insn;
58038fd1498Szrj ptr->antic_stores.safe_push (tmp);
58138fd1498Szrj }
58238fd1498Szrj
58338fd1498Szrj /* It is not necessary to check whether store is available if we did
58438fd1498Szrj it successfully before; if we failed before, do not bother to check
58538fd1498Szrj until we reach the insn that caused us to fail. */
58638fd1498Szrj check_available = 0;
58738fd1498Szrj if (ptr->avail_stores.is_empty ())
58838fd1498Szrj check_available = 1;
58938fd1498Szrj else
59038fd1498Szrj {
59138fd1498Szrj rtx_insn *tmp = ptr->avail_stores.last ();
59238fd1498Szrj if (BLOCK_FOR_INSN (tmp) != bb)
59338fd1498Szrj check_available = 1;
59438fd1498Szrj }
59538fd1498Szrj if (check_available)
59638fd1498Szrj {
59738fd1498Szrj /* Check that we have already reached the insn at that the check
59838fd1498Szrj failed last time. */
59938fd1498Szrj if (LAST_AVAIL_CHECK_FAILURE (ptr))
60038fd1498Szrj {
60138fd1498Szrj rtx_insn *tmp;
60238fd1498Szrj for (tmp = BB_END (bb);
60338fd1498Szrj tmp != insn && tmp != LAST_AVAIL_CHECK_FAILURE (ptr);
60438fd1498Szrj tmp = PREV_INSN (tmp))
60538fd1498Szrj continue;
60638fd1498Szrj if (tmp == insn)
60738fd1498Szrj check_available = 0;
60838fd1498Szrj }
60938fd1498Szrj else
61038fd1498Szrj check_available = store_killed_after (dest, ptr->pattern_regs, insn,
61138fd1498Szrj bb, regs_set_after,
61238fd1498Szrj &LAST_AVAIL_CHECK_FAILURE (ptr));
61338fd1498Szrj }
61438fd1498Szrj if (!check_available)
61538fd1498Szrj ptr->avail_stores.safe_push (insn);
61638fd1498Szrj }
61738fd1498Szrj
61838fd1498Szrj /* Find available and anticipatable stores. */
61938fd1498Szrj
62038fd1498Szrj static int
compute_store_table(void)62138fd1498Szrj compute_store_table (void)
62238fd1498Szrj {
62338fd1498Szrj int ret;
62438fd1498Szrj basic_block bb;
62538fd1498Szrj rtx_insn *insn;
62638fd1498Szrj rtx_insn *tmp;
62738fd1498Szrj df_ref def;
62838fd1498Szrj int *last_set_in, *already_set;
62938fd1498Szrj struct st_expr * ptr, **prev_next_ptr_ptr;
63038fd1498Szrj unsigned int max_gcse_regno = max_reg_num ();
63138fd1498Szrj
63238fd1498Szrj store_motion_mems = NULL;
63338fd1498Szrj store_motion_mems_table = new hash_table<st_expr_hasher> (13);
63438fd1498Szrj last_set_in = XCNEWVEC (int, max_gcse_regno);
63538fd1498Szrj already_set = XNEWVEC (int, max_gcse_regno);
63638fd1498Szrj
63738fd1498Szrj /* Find all the stores we care about. */
63838fd1498Szrj FOR_EACH_BB_FN (bb, cfun)
63938fd1498Szrj {
64038fd1498Szrj /* First compute the registers set in this block. */
64138fd1498Szrj FOR_BB_INSNS (bb, insn)
64238fd1498Szrj {
64338fd1498Szrj
64438fd1498Szrj if (! NONDEBUG_INSN_P (insn))
64538fd1498Szrj continue;
64638fd1498Szrj
64738fd1498Szrj FOR_EACH_INSN_DEF (def, insn)
64838fd1498Szrj last_set_in[DF_REF_REGNO (def)] = INSN_UID (insn);
64938fd1498Szrj }
65038fd1498Szrj
65138fd1498Szrj /* Now find the stores. */
65238fd1498Szrj memset (already_set, 0, sizeof (int) * max_gcse_regno);
65338fd1498Szrj FOR_BB_INSNS (bb, insn)
65438fd1498Szrj {
65538fd1498Szrj if (! NONDEBUG_INSN_P (insn))
65638fd1498Szrj continue;
65738fd1498Szrj
65838fd1498Szrj FOR_EACH_INSN_DEF (def, insn)
65938fd1498Szrj already_set[DF_REF_REGNO (def)] = INSN_UID (insn);
66038fd1498Szrj
66138fd1498Szrj /* Now that we've marked regs, look for stores. */
66238fd1498Szrj find_moveable_store (insn, already_set, last_set_in);
66338fd1498Szrj
66438fd1498Szrj /* Unmark regs that are no longer set. */
66538fd1498Szrj FOR_EACH_INSN_DEF (def, insn)
66638fd1498Szrj if (last_set_in[DF_REF_REGNO (def)] == INSN_UID (insn))
66738fd1498Szrj last_set_in[DF_REF_REGNO (def)] = 0;
66838fd1498Szrj }
66938fd1498Szrj
67038fd1498Szrj if (flag_checking)
67138fd1498Szrj {
67238fd1498Szrj /* last_set_in should now be all-zero. */
67338fd1498Szrj for (unsigned regno = 0; regno < max_gcse_regno; regno++)
67438fd1498Szrj gcc_assert (!last_set_in[regno]);
67538fd1498Szrj }
67638fd1498Szrj
67738fd1498Szrj /* Clear temporary marks. */
67838fd1498Szrj for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
67938fd1498Szrj {
68038fd1498Szrj LAST_AVAIL_CHECK_FAILURE (ptr) = NULL_RTX;
68138fd1498Szrj if (!ptr->antic_stores.is_empty ()
68238fd1498Szrj && (tmp = ptr->antic_stores.last ()) == NULL)
68338fd1498Szrj ptr->antic_stores.pop ();
68438fd1498Szrj }
68538fd1498Szrj }
68638fd1498Szrj
68738fd1498Szrj /* Remove the stores that are not available anywhere, as there will
68838fd1498Szrj be no opportunity to optimize them. */
68938fd1498Szrj for (ptr = store_motion_mems, prev_next_ptr_ptr = &store_motion_mems;
69038fd1498Szrj ptr != NULL;
69138fd1498Szrj ptr = *prev_next_ptr_ptr)
69238fd1498Szrj {
69338fd1498Szrj if (ptr->avail_stores.is_empty ())
69438fd1498Szrj {
69538fd1498Szrj *prev_next_ptr_ptr = ptr->next;
69638fd1498Szrj store_motion_mems_table->remove_elt_with_hash (ptr, ptr->hash_index);
69738fd1498Szrj free_st_expr_entry (ptr);
69838fd1498Szrj }
69938fd1498Szrj else
70038fd1498Szrj prev_next_ptr_ptr = &ptr->next;
70138fd1498Szrj }
70238fd1498Szrj
70338fd1498Szrj ret = enumerate_store_motion_mems ();
70438fd1498Szrj
70538fd1498Szrj if (dump_file)
70638fd1498Szrj print_store_motion_mems (dump_file);
70738fd1498Szrj
70838fd1498Szrj free (last_set_in);
70938fd1498Szrj free (already_set);
71038fd1498Szrj return ret;
71138fd1498Szrj }
71238fd1498Szrj
71338fd1498Szrj /* In all code following after this, REACHING_REG has its original
71438fd1498Szrj meaning again. Avoid confusion, and undef the accessor macro for
71538fd1498Szrj the temporary marks usage in compute_store_table. */
71638fd1498Szrj #undef LAST_AVAIL_CHECK_FAILURE
71738fd1498Szrj
71838fd1498Szrj /* Insert an instruction at the beginning of a basic block, and update
71938fd1498Szrj the BB_HEAD if needed. */
72038fd1498Szrj
72138fd1498Szrj static void
insert_insn_start_basic_block(rtx_insn * insn,basic_block bb)72238fd1498Szrj insert_insn_start_basic_block (rtx_insn *insn, basic_block bb)
72338fd1498Szrj {
72438fd1498Szrj /* Insert at start of successor block. */
72538fd1498Szrj rtx_insn *prev = PREV_INSN (BB_HEAD (bb));
72638fd1498Szrj rtx_insn *before = BB_HEAD (bb);
72738fd1498Szrj while (before != 0)
72838fd1498Szrj {
72938fd1498Szrj if (! LABEL_P (before)
73038fd1498Szrj && !NOTE_INSN_BASIC_BLOCK_P (before))
73138fd1498Szrj break;
73238fd1498Szrj prev = before;
73338fd1498Szrj if (prev == BB_END (bb))
73438fd1498Szrj break;
73538fd1498Szrj before = NEXT_INSN (before);
73638fd1498Szrj }
73738fd1498Szrj
73838fd1498Szrj insn = emit_insn_after_noloc (insn, prev, bb);
73938fd1498Szrj
74038fd1498Szrj if (dump_file)
74138fd1498Szrj {
74238fd1498Szrj fprintf (dump_file, "STORE_MOTION insert store at start of BB %d:\n",
74338fd1498Szrj bb->index);
74438fd1498Szrj print_inline_rtx (dump_file, insn, 6);
74538fd1498Szrj fprintf (dump_file, "\n");
74638fd1498Szrj }
74738fd1498Szrj }
74838fd1498Szrj
74938fd1498Szrj /* This routine will insert a store on an edge. EXPR is the st_expr entry for
75038fd1498Szrj the memory reference, and E is the edge to insert it on. Returns nonzero
75138fd1498Szrj if an edge insertion was performed. */
75238fd1498Szrj
75338fd1498Szrj static int
insert_store(struct st_expr * expr,edge e)75438fd1498Szrj insert_store (struct st_expr * expr, edge e)
75538fd1498Szrj {
75638fd1498Szrj rtx reg;
75738fd1498Szrj rtx_insn *insn;
75838fd1498Szrj basic_block bb;
75938fd1498Szrj edge tmp;
76038fd1498Szrj edge_iterator ei;
76138fd1498Szrj
76238fd1498Szrj /* We did all the deleted before this insert, so if we didn't delete a
76338fd1498Szrj store, then we haven't set the reaching reg yet either. */
76438fd1498Szrj if (expr->reaching_reg == NULL_RTX)
76538fd1498Szrj return 0;
76638fd1498Szrj
76738fd1498Szrj if (e->flags & EDGE_FAKE)
76838fd1498Szrj return 0;
76938fd1498Szrj
77038fd1498Szrj reg = expr->reaching_reg;
77138fd1498Szrj insn = gen_move_insn (copy_rtx (expr->pattern), reg);
77238fd1498Szrj
77338fd1498Szrj /* If we are inserting this expression on ALL predecessor edges of a BB,
77438fd1498Szrj insert it at the start of the BB, and reset the insert bits on the other
77538fd1498Szrj edges so we don't try to insert it on the other edges. */
77638fd1498Szrj bb = e->dest;
77738fd1498Szrj FOR_EACH_EDGE (tmp, ei, e->dest->preds)
77838fd1498Szrj if (!(tmp->flags & EDGE_FAKE))
77938fd1498Szrj {
78038fd1498Szrj int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
78138fd1498Szrj
78238fd1498Szrj gcc_assert (index != EDGE_INDEX_NO_EDGE);
78338fd1498Szrj if (! bitmap_bit_p (st_insert_map[index], expr->index))
78438fd1498Szrj break;
78538fd1498Szrj }
78638fd1498Szrj
78738fd1498Szrj /* If tmp is NULL, we found an insertion on every edge, blank the
78838fd1498Szrj insertion vector for these edges, and insert at the start of the BB. */
78938fd1498Szrj if (!tmp && bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
79038fd1498Szrj {
79138fd1498Szrj FOR_EACH_EDGE (tmp, ei, e->dest->preds)
79238fd1498Szrj {
79338fd1498Szrj int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
79438fd1498Szrj bitmap_clear_bit (st_insert_map[index], expr->index);
79538fd1498Szrj }
79638fd1498Szrj insert_insn_start_basic_block (insn, bb);
79738fd1498Szrj return 0;
79838fd1498Szrj }
79938fd1498Szrj
80038fd1498Szrj /* We can't put stores in the front of blocks pointed to by abnormal
80138fd1498Szrj edges since that may put a store where one didn't used to be. */
80238fd1498Szrj gcc_assert (!(e->flags & EDGE_ABNORMAL));
80338fd1498Szrj
80438fd1498Szrj insert_insn_on_edge (insn, e);
80538fd1498Szrj
80638fd1498Szrj if (dump_file)
80738fd1498Szrj {
80838fd1498Szrj fprintf (dump_file, "STORE_MOTION insert insn on edge (%d, %d):\n",
80938fd1498Szrj e->src->index, e->dest->index);
81038fd1498Szrj print_inline_rtx (dump_file, insn, 6);
81138fd1498Szrj fprintf (dump_file, "\n");
81238fd1498Szrj }
81338fd1498Szrj
81438fd1498Szrj return 1;
81538fd1498Szrj }
81638fd1498Szrj
81738fd1498Szrj /* Remove any REG_EQUAL or REG_EQUIV notes containing a reference to the
81838fd1498Szrj memory location in SMEXPR set in basic block BB.
81938fd1498Szrj
82038fd1498Szrj This could be rather expensive. */
82138fd1498Szrj
82238fd1498Szrj static void
remove_reachable_equiv_notes(basic_block bb,struct st_expr * smexpr)82338fd1498Szrj remove_reachable_equiv_notes (basic_block bb, struct st_expr *smexpr)
82438fd1498Szrj {
82538fd1498Szrj edge_iterator *stack, ei;
82638fd1498Szrj int sp;
82738fd1498Szrj edge act;
82838fd1498Szrj auto_sbitmap visited (last_basic_block_for_fn (cfun));
82938fd1498Szrj rtx note;
83038fd1498Szrj rtx_insn *insn;
83138fd1498Szrj rtx mem = smexpr->pattern;
83238fd1498Szrj
83338fd1498Szrj stack = XNEWVEC (edge_iterator, n_basic_blocks_for_fn (cfun));
83438fd1498Szrj sp = 0;
83538fd1498Szrj ei = ei_start (bb->succs);
83638fd1498Szrj
83738fd1498Szrj bitmap_clear (visited);
83838fd1498Szrj
83938fd1498Szrj act = (EDGE_COUNT (ei_container (ei))
84038fd1498Szrj ? EDGE_I (ei_container (ei), 0)
84138fd1498Szrj : NULL);
84238fd1498Szrj for (;;)
84338fd1498Szrj {
84438fd1498Szrj if (!act)
84538fd1498Szrj {
84638fd1498Szrj if (!sp)
84738fd1498Szrj {
84838fd1498Szrj free (stack);
84938fd1498Szrj return;
85038fd1498Szrj }
85138fd1498Szrj act = ei_edge (stack[--sp]);
85238fd1498Szrj }
85338fd1498Szrj bb = act->dest;
85438fd1498Szrj
85538fd1498Szrj if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
85638fd1498Szrj || bitmap_bit_p (visited, bb->index))
85738fd1498Szrj {
85838fd1498Szrj if (!ei_end_p (ei))
85938fd1498Szrj ei_next (&ei);
86038fd1498Szrj act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
86138fd1498Szrj continue;
86238fd1498Szrj }
86338fd1498Szrj bitmap_set_bit (visited, bb->index);
86438fd1498Szrj
86538fd1498Szrj rtx_insn *last;
86638fd1498Szrj if (bitmap_bit_p (st_antloc[bb->index], smexpr->index))
86738fd1498Szrj {
86838fd1498Szrj unsigned int i;
86938fd1498Szrj FOR_EACH_VEC_ELT_REVERSE (smexpr->antic_stores, i, last)
87038fd1498Szrj if (BLOCK_FOR_INSN (last) == bb)
87138fd1498Szrj break;
87238fd1498Szrj }
87338fd1498Szrj else
87438fd1498Szrj last = NEXT_INSN (BB_END (bb));
87538fd1498Szrj
87638fd1498Szrj for (insn = BB_HEAD (bb); insn != last; insn = NEXT_INSN (insn))
87738fd1498Szrj if (NONDEBUG_INSN_P (insn))
87838fd1498Szrj {
87938fd1498Szrj note = find_reg_equal_equiv_note (insn);
88038fd1498Szrj if (!note || !exp_equiv_p (XEXP (note, 0), mem, 0, true))
88138fd1498Szrj continue;
88238fd1498Szrj
88338fd1498Szrj if (dump_file)
88438fd1498Szrj fprintf (dump_file,
88538fd1498Szrj "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
88638fd1498Szrj INSN_UID (insn));
88738fd1498Szrj remove_note (insn, note);
88838fd1498Szrj }
88938fd1498Szrj
89038fd1498Szrj if (!ei_end_p (ei))
89138fd1498Szrj ei_next (&ei);
89238fd1498Szrj act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
89338fd1498Szrj
89438fd1498Szrj if (EDGE_COUNT (bb->succs) > 0)
89538fd1498Szrj {
89638fd1498Szrj if (act)
89738fd1498Szrj stack[sp++] = ei;
89838fd1498Szrj ei = ei_start (bb->succs);
89938fd1498Szrj act = (EDGE_COUNT (ei_container (ei))
90038fd1498Szrj ? EDGE_I (ei_container (ei), 0)
90138fd1498Szrj : NULL);
90238fd1498Szrj }
90338fd1498Szrj }
90438fd1498Szrj }
90538fd1498Szrj
90638fd1498Szrj /* This routine will replace a store with a SET to a specified register. */
90738fd1498Szrj
90838fd1498Szrj static void
replace_store_insn(rtx reg,rtx_insn * del,basic_block bb,struct st_expr * smexpr)90938fd1498Szrj replace_store_insn (rtx reg, rtx_insn *del, basic_block bb,
91038fd1498Szrj struct st_expr *smexpr)
91138fd1498Szrj {
91238fd1498Szrj rtx_insn *insn;
91338fd1498Szrj rtx mem, note, set;
91438fd1498Szrj
915*58e805e6Szrj insn = prepare_copy_insn (reg, SET_SRC (single_set (del)));
91638fd1498Szrj
91738fd1498Szrj unsigned int i;
91838fd1498Szrj rtx_insn *temp;
91938fd1498Szrj FOR_EACH_VEC_ELT_REVERSE (smexpr->antic_stores, i, temp)
92038fd1498Szrj if (temp == del)
92138fd1498Szrj {
92238fd1498Szrj smexpr->antic_stores[i] = insn;
92338fd1498Szrj break;
92438fd1498Szrj }
92538fd1498Szrj
92638fd1498Szrj /* Move the notes from the deleted insn to its replacement. */
92738fd1498Szrj REG_NOTES (insn) = REG_NOTES (del);
92838fd1498Szrj
92938fd1498Szrj /* Emit the insn AFTER all the notes are transferred.
93038fd1498Szrj This is cheaper since we avoid df rescanning for the note change. */
93138fd1498Szrj insn = emit_insn_after (insn, del);
93238fd1498Szrj
93338fd1498Szrj if (dump_file)
93438fd1498Szrj {
93538fd1498Szrj fprintf (dump_file,
93638fd1498Szrj "STORE_MOTION delete insn in BB %d:\n ", bb->index);
93738fd1498Szrj print_inline_rtx (dump_file, del, 6);
93838fd1498Szrj fprintf (dump_file, "\nSTORE_MOTION replaced with insn:\n ");
93938fd1498Szrj print_inline_rtx (dump_file, insn, 6);
94038fd1498Szrj fprintf (dump_file, "\n");
94138fd1498Szrj }
94238fd1498Szrj
94338fd1498Szrj delete_insn (del);
94438fd1498Szrj
94538fd1498Szrj /* Now we must handle REG_EQUAL notes whose contents is equal to the mem;
94638fd1498Szrj they are no longer accurate provided that they are reached by this
94738fd1498Szrj definition, so drop them. */
948*58e805e6Szrj mem = smexpr->pattern;
94938fd1498Szrj for (; insn != NEXT_INSN (BB_END (bb)); insn = NEXT_INSN (insn))
95038fd1498Szrj if (NONDEBUG_INSN_P (insn))
95138fd1498Szrj {
95238fd1498Szrj set = single_set (insn);
95338fd1498Szrj if (!set)
95438fd1498Szrj continue;
95538fd1498Szrj if (exp_equiv_p (SET_DEST (set), mem, 0, true))
95638fd1498Szrj return;
95738fd1498Szrj note = find_reg_equal_equiv_note (insn);
95838fd1498Szrj if (!note || !exp_equiv_p (XEXP (note, 0), mem, 0, true))
95938fd1498Szrj continue;
96038fd1498Szrj
96138fd1498Szrj if (dump_file)
96238fd1498Szrj fprintf (dump_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
96338fd1498Szrj INSN_UID (insn));
96438fd1498Szrj remove_note (insn, note);
96538fd1498Szrj }
96638fd1498Szrj remove_reachable_equiv_notes (bb, smexpr);
96738fd1498Szrj }
96838fd1498Szrj
96938fd1498Szrj
97038fd1498Szrj /* Delete a store, but copy the value that would have been stored into
97138fd1498Szrj the reaching_reg for later storing. */
97238fd1498Szrj
97338fd1498Szrj static void
delete_store(struct st_expr * expr,basic_block bb)97438fd1498Szrj delete_store (struct st_expr * expr, basic_block bb)
97538fd1498Szrj {
97638fd1498Szrj rtx reg;
97738fd1498Szrj
97838fd1498Szrj if (expr->reaching_reg == NULL_RTX)
97938fd1498Szrj expr->reaching_reg = gen_reg_rtx_and_attrs (expr->pattern);
98038fd1498Szrj
98138fd1498Szrj reg = expr->reaching_reg;
98238fd1498Szrj
98338fd1498Szrj unsigned int len = expr->avail_stores.length ();
98438fd1498Szrj for (unsigned int i = len - 1; i < len; i--)
98538fd1498Szrj {
98638fd1498Szrj rtx_insn *del = expr->avail_stores[i];
98738fd1498Szrj if (BLOCK_FOR_INSN (del) == bb)
98838fd1498Szrj {
98938fd1498Szrj /* We know there is only one since we deleted redundant
99038fd1498Szrj ones during the available computation. */
99138fd1498Szrj replace_store_insn (reg, del, bb, expr);
99238fd1498Szrj break;
99338fd1498Szrj }
99438fd1498Szrj }
99538fd1498Szrj }
99638fd1498Szrj
99738fd1498Szrj /* Fill in available, anticipatable, transparent and kill vectors in
99838fd1498Szrj STORE_DATA, based on lists of available and anticipatable stores. */
99938fd1498Szrj static void
build_store_vectors(void)100038fd1498Szrj build_store_vectors (void)
100138fd1498Szrj {
100238fd1498Szrj basic_block bb;
100338fd1498Szrj int *regs_set_in_block;
100438fd1498Szrj rtx_insn *insn;
100538fd1498Szrj struct st_expr * ptr;
100638fd1498Szrj unsigned int max_gcse_regno = max_reg_num ();
100738fd1498Szrj
100838fd1498Szrj /* Build the gen_vector. This is any store in the table which is not killed
100938fd1498Szrj by aliasing later in its block. */
101038fd1498Szrj st_avloc = sbitmap_vector_alloc (last_basic_block_for_fn (cfun),
101138fd1498Szrj num_stores);
101238fd1498Szrj bitmap_vector_clear (st_avloc, last_basic_block_for_fn (cfun));
101338fd1498Szrj
101438fd1498Szrj st_antloc = sbitmap_vector_alloc (last_basic_block_for_fn (cfun),
101538fd1498Szrj num_stores);
101638fd1498Szrj bitmap_vector_clear (st_antloc, last_basic_block_for_fn (cfun));
101738fd1498Szrj
101838fd1498Szrj for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
101938fd1498Szrj {
102038fd1498Szrj unsigned int len = ptr->avail_stores.length ();
102138fd1498Szrj for (unsigned int i = len - 1; i < len; i--)
102238fd1498Szrj {
102338fd1498Szrj insn = ptr->avail_stores[i];
102438fd1498Szrj bb = BLOCK_FOR_INSN (insn);
102538fd1498Szrj
102638fd1498Szrj /* If we've already seen an available expression in this block,
102738fd1498Szrj we can delete this one (It occurs earlier in the block). We'll
102838fd1498Szrj copy the SRC expression to an unused register in case there
102938fd1498Szrj are any side effects. */
103038fd1498Szrj if (bitmap_bit_p (st_avloc[bb->index], ptr->index))
103138fd1498Szrj {
103238fd1498Szrj rtx r = gen_reg_rtx_and_attrs (ptr->pattern);
103338fd1498Szrj if (dump_file)
103438fd1498Szrj fprintf (dump_file, "Removing redundant store:\n");
103538fd1498Szrj replace_store_insn (r, insn, bb, ptr);
103638fd1498Szrj continue;
103738fd1498Szrj }
103838fd1498Szrj bitmap_set_bit (st_avloc[bb->index], ptr->index);
103938fd1498Szrj }
104038fd1498Szrj
104138fd1498Szrj unsigned int i;
104238fd1498Szrj FOR_EACH_VEC_ELT_REVERSE (ptr->antic_stores, i, insn)
104338fd1498Szrj {
104438fd1498Szrj bb = BLOCK_FOR_INSN (insn);
104538fd1498Szrj bitmap_set_bit (st_antloc[bb->index], ptr->index);
104638fd1498Szrj }
104738fd1498Szrj }
104838fd1498Szrj
104938fd1498Szrj st_kill = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), num_stores);
105038fd1498Szrj bitmap_vector_clear (st_kill, last_basic_block_for_fn (cfun));
105138fd1498Szrj
105238fd1498Szrj st_transp = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), num_stores);
105338fd1498Szrj bitmap_vector_clear (st_transp, last_basic_block_for_fn (cfun));
105438fd1498Szrj regs_set_in_block = XNEWVEC (int, max_gcse_regno);
105538fd1498Szrj
105638fd1498Szrj FOR_EACH_BB_FN (bb, cfun)
105738fd1498Szrj {
105838fd1498Szrj memset (regs_set_in_block, 0, sizeof (int) * max_gcse_regno);
105938fd1498Szrj
106038fd1498Szrj FOR_BB_INSNS (bb, insn)
106138fd1498Szrj if (NONDEBUG_INSN_P (insn))
106238fd1498Szrj {
106338fd1498Szrj df_ref def;
106438fd1498Szrj FOR_EACH_INSN_DEF (def, insn)
106538fd1498Szrj {
106638fd1498Szrj unsigned int ref_regno = DF_REF_REGNO (def);
106738fd1498Szrj if (ref_regno < max_gcse_regno)
106838fd1498Szrj regs_set_in_block[DF_REF_REGNO (def)] = 1;
106938fd1498Szrj }
107038fd1498Szrj }
107138fd1498Szrj
107238fd1498Szrj for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
107338fd1498Szrj {
107438fd1498Szrj if (store_killed_after (ptr->pattern, ptr->pattern_regs, BB_HEAD (bb),
107538fd1498Szrj bb, regs_set_in_block, NULL))
107638fd1498Szrj {
107738fd1498Szrj /* It should not be necessary to consider the expression
107838fd1498Szrj killed if it is both anticipatable and available. */
107938fd1498Szrj if (!bitmap_bit_p (st_antloc[bb->index], ptr->index)
108038fd1498Szrj || !bitmap_bit_p (st_avloc[bb->index], ptr->index))
108138fd1498Szrj bitmap_set_bit (st_kill[bb->index], ptr->index);
108238fd1498Szrj }
108338fd1498Szrj else
108438fd1498Szrj bitmap_set_bit (st_transp[bb->index], ptr->index);
108538fd1498Szrj }
108638fd1498Szrj }
108738fd1498Szrj
108838fd1498Szrj free (regs_set_in_block);
108938fd1498Szrj
109038fd1498Szrj if (dump_file)
109138fd1498Szrj {
109238fd1498Szrj dump_bitmap_vector (dump_file, "st_antloc", "", st_antloc,
109338fd1498Szrj last_basic_block_for_fn (cfun));
109438fd1498Szrj dump_bitmap_vector (dump_file, "st_kill", "", st_kill,
109538fd1498Szrj last_basic_block_for_fn (cfun));
109638fd1498Szrj dump_bitmap_vector (dump_file, "st_transp", "", st_transp,
109738fd1498Szrj last_basic_block_for_fn (cfun));
109838fd1498Szrj dump_bitmap_vector (dump_file, "st_avloc", "", st_avloc,
109938fd1498Szrj last_basic_block_for_fn (cfun));
110038fd1498Szrj }
110138fd1498Szrj }
110238fd1498Szrj
110338fd1498Szrj /* Free memory used by store motion. */
110438fd1498Szrj
110538fd1498Szrj static void
free_store_memory(void)110638fd1498Szrj free_store_memory (void)
110738fd1498Szrj {
110838fd1498Szrj free_store_motion_mems ();
110938fd1498Szrj
111038fd1498Szrj if (st_avloc)
111138fd1498Szrj sbitmap_vector_free (st_avloc);
111238fd1498Szrj if (st_kill)
111338fd1498Szrj sbitmap_vector_free (st_kill);
111438fd1498Szrj if (st_transp)
111538fd1498Szrj sbitmap_vector_free (st_transp);
111638fd1498Szrj if (st_antloc)
111738fd1498Szrj sbitmap_vector_free (st_antloc);
111838fd1498Szrj if (st_insert_map)
111938fd1498Szrj sbitmap_vector_free (st_insert_map);
112038fd1498Szrj if (st_delete_map)
112138fd1498Szrj sbitmap_vector_free (st_delete_map);
112238fd1498Szrj
112338fd1498Szrj st_avloc = st_kill = st_transp = st_antloc = NULL;
112438fd1498Szrj st_insert_map = st_delete_map = NULL;
112538fd1498Szrj }
112638fd1498Szrj
112738fd1498Szrj /* Perform store motion. Much like gcse, except we move expressions the
112838fd1498Szrj other way by looking at the flowgraph in reverse.
112938fd1498Szrj Return non-zero if transformations are performed by the pass. */
113038fd1498Szrj
113138fd1498Szrj static int
one_store_motion_pass(void)113238fd1498Szrj one_store_motion_pass (void)
113338fd1498Szrj {
113438fd1498Szrj basic_block bb;
113538fd1498Szrj int x;
113638fd1498Szrj struct st_expr * ptr;
113738fd1498Szrj int did_edge_inserts = 0;
113838fd1498Szrj int n_stores_deleted = 0;
113938fd1498Szrj int n_stores_created = 0;
114038fd1498Szrj
114138fd1498Szrj init_alias_analysis ();
114238fd1498Szrj
114338fd1498Szrj /* Find all the available and anticipatable stores. */
114438fd1498Szrj num_stores = compute_store_table ();
114538fd1498Szrj if (num_stores == 0)
114638fd1498Szrj {
114738fd1498Szrj delete store_motion_mems_table;
114838fd1498Szrj store_motion_mems_table = NULL;
114938fd1498Szrj end_alias_analysis ();
115038fd1498Szrj return 0;
115138fd1498Szrj }
115238fd1498Szrj
115338fd1498Szrj /* Now compute kill & transp vectors. */
115438fd1498Szrj build_store_vectors ();
115538fd1498Szrj add_noreturn_fake_exit_edges ();
115638fd1498Szrj connect_infinite_loops_to_exit ();
115738fd1498Szrj
115838fd1498Szrj edge_list = pre_edge_rev_lcm (num_stores, st_transp, st_avloc,
115938fd1498Szrj st_antloc, st_kill, &st_insert_map,
116038fd1498Szrj &st_delete_map);
116138fd1498Szrj
116238fd1498Szrj /* Now we want to insert the new stores which are going to be needed. */
116338fd1498Szrj for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
116438fd1498Szrj {
116538fd1498Szrj /* If any of the edges we have above are abnormal, we can't move this
116638fd1498Szrj store. */
116738fd1498Szrj for (x = NUM_EDGES (edge_list) - 1; x >= 0; x--)
116838fd1498Szrj if (bitmap_bit_p (st_insert_map[x], ptr->index)
116938fd1498Szrj && (INDEX_EDGE (edge_list, x)->flags & EDGE_ABNORMAL))
117038fd1498Szrj break;
117138fd1498Szrj
117238fd1498Szrj if (x >= 0)
117338fd1498Szrj {
117438fd1498Szrj if (dump_file != NULL)
117538fd1498Szrj fprintf (dump_file,
117638fd1498Szrj "Can't replace store %d: abnormal edge from %d to %d\n",
117738fd1498Szrj ptr->index, INDEX_EDGE (edge_list, x)->src->index,
117838fd1498Szrj INDEX_EDGE (edge_list, x)->dest->index);
117938fd1498Szrj continue;
118038fd1498Szrj }
118138fd1498Szrj
118238fd1498Szrj /* Now we want to insert the new stores which are going to be needed. */
118338fd1498Szrj
118438fd1498Szrj FOR_EACH_BB_FN (bb, cfun)
118538fd1498Szrj if (bitmap_bit_p (st_delete_map[bb->index], ptr->index))
118638fd1498Szrj {
118738fd1498Szrj delete_store (ptr, bb);
118838fd1498Szrj n_stores_deleted++;
118938fd1498Szrj }
119038fd1498Szrj
119138fd1498Szrj for (x = 0; x < NUM_EDGES (edge_list); x++)
119238fd1498Szrj if (bitmap_bit_p (st_insert_map[x], ptr->index))
119338fd1498Szrj {
119438fd1498Szrj did_edge_inserts |= insert_store (ptr, INDEX_EDGE (edge_list, x));
119538fd1498Szrj n_stores_created++;
119638fd1498Szrj }
119738fd1498Szrj }
119838fd1498Szrj
119938fd1498Szrj if (did_edge_inserts)
120038fd1498Szrj commit_edge_insertions ();
120138fd1498Szrj
120238fd1498Szrj free_store_memory ();
120338fd1498Szrj free_edge_list (edge_list);
120438fd1498Szrj remove_fake_exit_edges ();
120538fd1498Szrj end_alias_analysis ();
120638fd1498Szrj
120738fd1498Szrj if (dump_file)
120838fd1498Szrj {
120938fd1498Szrj fprintf (dump_file, "STORE_MOTION of %s, %d basic blocks, ",
121038fd1498Szrj current_function_name (), n_basic_blocks_for_fn (cfun));
121138fd1498Szrj fprintf (dump_file, "%d insns deleted, %d insns created\n",
121238fd1498Szrj n_stores_deleted, n_stores_created);
121338fd1498Szrj }
121438fd1498Szrj
121538fd1498Szrj return (n_stores_deleted > 0 || n_stores_created > 0);
121638fd1498Szrj }
121738fd1498Szrj
121838fd1498Szrj
121938fd1498Szrj static unsigned int
execute_rtl_store_motion(void)122038fd1498Szrj execute_rtl_store_motion (void)
122138fd1498Szrj {
122238fd1498Szrj delete_unreachable_blocks ();
122338fd1498Szrj df_analyze ();
122438fd1498Szrj flag_rerun_cse_after_global_opts |= one_store_motion_pass ();
122538fd1498Szrj return 0;
122638fd1498Szrj }
122738fd1498Szrj
122838fd1498Szrj namespace {
122938fd1498Szrj
123038fd1498Szrj const pass_data pass_data_rtl_store_motion =
123138fd1498Szrj {
123238fd1498Szrj RTL_PASS, /* type */
123338fd1498Szrj "store_motion", /* name */
123438fd1498Szrj OPTGROUP_NONE, /* optinfo_flags */
123538fd1498Szrj TV_LSM, /* tv_id */
123638fd1498Szrj PROP_cfglayout, /* properties_required */
123738fd1498Szrj 0, /* properties_provided */
123838fd1498Szrj 0, /* properties_destroyed */
123938fd1498Szrj 0, /* todo_flags_start */
124038fd1498Szrj TODO_df_finish, /* todo_flags_finish */
124138fd1498Szrj };
124238fd1498Szrj
124338fd1498Szrj class pass_rtl_store_motion : public rtl_opt_pass
124438fd1498Szrj {
124538fd1498Szrj public:
pass_rtl_store_motion(gcc::context * ctxt)124638fd1498Szrj pass_rtl_store_motion (gcc::context *ctxt)
124738fd1498Szrj : rtl_opt_pass (pass_data_rtl_store_motion, ctxt)
124838fd1498Szrj {}
124938fd1498Szrj
125038fd1498Szrj /* opt_pass methods: */
125138fd1498Szrj virtual bool gate (function *);
execute(function *)125238fd1498Szrj virtual unsigned int execute (function *)
125338fd1498Szrj {
125438fd1498Szrj return execute_rtl_store_motion ();
125538fd1498Szrj }
125638fd1498Szrj
125738fd1498Szrj }; // class pass_rtl_store_motion
125838fd1498Szrj
125938fd1498Szrj bool
gate(function * fun)126038fd1498Szrj pass_rtl_store_motion::gate (function *fun)
126138fd1498Szrj {
126238fd1498Szrj return optimize > 0 && flag_gcse_sm
126338fd1498Szrj && !fun->calls_setjmp
126438fd1498Szrj && optimize_function_for_speed_p (fun)
126538fd1498Szrj && dbg_cnt (store_motion);
126638fd1498Szrj }
126738fd1498Szrj
126838fd1498Szrj } // anon namespace
126938fd1498Szrj
127038fd1498Szrj rtl_opt_pass *
make_pass_rtl_store_motion(gcc::context * ctxt)127138fd1498Szrj make_pass_rtl_store_motion (gcc::context *ctxt)
127238fd1498Szrj {
127338fd1498Szrj return new pass_rtl_store_motion (ctxt);
127438fd1498Szrj }
1275