/* Store motion via Lazy Code Motion on the reverse CFG.
|
/* Store motion via Lazy Code Motion on the reverse CFG.
|
Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005,
|
Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005,
|
2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
|
2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
|
|
|
This file is part of GCC.
|
This file is part of GCC.
|
|
|
GCC is free software; you can redistribute it and/or modify it under
|
GCC is free software; you can redistribute it and/or modify it under
|
the terms of the GNU General Public License as published by the Free
|
the terms of the GNU General Public License as published by the Free
|
Software Foundation; either version 3, or (at your option) any later
|
Software Foundation; either version 3, or (at your option) any later
|
version.
|
version.
|
|
|
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
for more details.
|
for more details.
|
|
|
You should have received a copy of the GNU General Public License
|
You should have received a copy of the GNU General Public License
|
along with GCC; see the file COPYING3. If not see
|
along with GCC; see the file COPYING3. If not see
|
<http://www.gnu.org/licenses/>. */
|
<http://www.gnu.org/licenses/>. */
|
|
|
#include "config.h"
|
#include "config.h"
|
#include "system.h"
|
#include "system.h"
|
#include "coretypes.h"
|
#include "coretypes.h"
|
#include "tm.h"
|
#include "tm.h"
|
#include "toplev.h"
|
#include "toplev.h"
|
|
|
#include "rtl.h"
|
#include "rtl.h"
|
#include "tree.h"
|
#include "tree.h"
|
#include "tm_p.h"
|
#include "tm_p.h"
|
#include "regs.h"
|
#include "regs.h"
|
#include "hard-reg-set.h"
|
#include "hard-reg-set.h"
|
#include "flags.h"
|
#include "flags.h"
|
#include "real.h"
|
#include "real.h"
|
#include "insn-config.h"
|
#include "insn-config.h"
|
#include "recog.h"
|
#include "recog.h"
|
#include "basic-block.h"
|
#include "basic-block.h"
|
#include "output.h"
|
#include "output.h"
|
#include "function.h"
|
#include "function.h"
|
#include "expr.h"
|
#include "expr.h"
|
#include "except.h"
|
#include "except.h"
|
#include "ggc.h"
|
#include "ggc.h"
|
#include "intl.h"
|
#include "intl.h"
|
#include "timevar.h"
|
#include "timevar.h"
|
#include "tree-pass.h"
|
#include "tree-pass.h"
|
#include "hashtab.h"
|
#include "hashtab.h"
|
#include "df.h"
|
#include "df.h"
|
#include "dbgcnt.h"
|
#include "dbgcnt.h"
|
|
|
/* This pass implements downward store motion.
|
/* This pass implements downward store motion.
|
As of May 1, 2009, the pass is not enabled by default on any target,
|
As of May 1, 2009, the pass is not enabled by default on any target,
|
but bootstrap completes on ia64 and x86_64 with the pass enabled. */
|
but bootstrap completes on ia64 and x86_64 with the pass enabled. */
|
|
|
/* TODO:
|
/* TODO:
|
- remove_reachable_equiv_notes is an incomprehensible pile of goo and
|
- remove_reachable_equiv_notes is an incomprehensible pile of goo and
|
a compile time hog that needs a rewrite (maybe cache st_exprs to
|
a compile time hog that needs a rewrite (maybe cache st_exprs to
|
invalidate REG_EQUAL/REG_EQUIV notes for?).
|
invalidate REG_EQUAL/REG_EQUIV notes for?).
|
- pattern_regs in st_expr should be a regset (on its own obstack).
|
- pattern_regs in st_expr should be a regset (on its own obstack).
|
- antic_stores and avail_stores should be VECs instead of lists.
|
- antic_stores and avail_stores should be VECs instead of lists.
|
- store_motion_mems should be a VEC instead of a list.
|
- store_motion_mems should be a VEC instead of a list.
|
- there should be an alloc pool for struct st_expr objects.
|
- there should be an alloc pool for struct st_expr objects.
|
- investigate whether it is helpful to make the address of an st_expr
|
- investigate whether it is helpful to make the address of an st_expr
|
a cselib VALUE.
|
a cselib VALUE.
|
- when GIMPLE alias information is exported, the effectiveness of this
|
- when GIMPLE alias information is exported, the effectiveness of this
|
pass should be re-evaluated.
|
pass should be re-evaluated.
|
*/
|
*/
|
|
|
/* This is a list of store expressions (MEMs). The structure is used
|
/* This is a list of store expressions (MEMs). The structure is used
|
as an expression table to track stores which look interesting, and
|
as an expression table to track stores which look interesting, and
|
might be moveable towards the exit block. */
|
might be moveable towards the exit block. */
|
|
|
struct st_expr
|
struct st_expr
|
{
|
{
|
/* Pattern of this mem. */
|
/* Pattern of this mem. */
|
rtx pattern;
|
rtx pattern;
|
/* List of registers mentioned by the mem. */
|
/* List of registers mentioned by the mem. */
|
rtx pattern_regs;
|
rtx pattern_regs;
|
/* INSN list of stores that are locally anticipatable. */
|
/* INSN list of stores that are locally anticipatable. */
|
rtx antic_stores;
|
rtx antic_stores;
|
/* INSN list of stores that are locally available. */
|
/* INSN list of stores that are locally available. */
|
rtx avail_stores;
|
rtx avail_stores;
|
/* Next in the list. */
|
/* Next in the list. */
|
struct st_expr * next;
|
struct st_expr * next;
|
/* Store ID in the dataflow bitmaps. */
|
/* Store ID in the dataflow bitmaps. */
|
int index;
|
int index;
|
/* Hash value for the hash table. */
|
/* Hash value for the hash table. */
|
unsigned int hash_index;
|
unsigned int hash_index;
|
/* Register holding the stored expression when a store is moved.
|
/* Register holding the stored expression when a store is moved.
|
This field is also used as a cache in find_moveable_store, see
|
This field is also used as a cache in find_moveable_store, see
|
LAST_AVAIL_CHECK_FAILURE below. */
|
LAST_AVAIL_CHECK_FAILURE below. */
|
rtx reaching_reg;
|
rtx reaching_reg;
|
};
|
};
|
|
|
/* Head of the list of load/store memory refs. */
|
/* Head of the list of load/store memory refs. */
|
static struct st_expr * store_motion_mems = NULL;
|
static struct st_expr * store_motion_mems = NULL;
|
|
|
/* Hashtable for the load/store memory refs. */
|
/* Hashtable for the load/store memory refs. */
|
static htab_t store_motion_mems_table = NULL;
|
static htab_t store_motion_mems_table = NULL;
|
|
|
/* These bitmaps will hold the local dataflow properties per basic block. */
|
/* These bitmaps will hold the local dataflow properties per basic block. */
|
static sbitmap *st_kill, *st_avloc, *st_antloc, *st_transp;
|
static sbitmap *st_kill, *st_avloc, *st_antloc, *st_transp;
|
|
|
/* Nonzero for expressions which should be inserted on a specific edge. */
|
/* Nonzero for expressions which should be inserted on a specific edge. */
|
static sbitmap *st_insert_map;
|
static sbitmap *st_insert_map;
|
|
|
/* Nonzero for expressions which should be deleted in a specific block. */
|
/* Nonzero for expressions which should be deleted in a specific block. */
|
static sbitmap *st_delete_map;
|
static sbitmap *st_delete_map;
|
|
|
/* Global holding the number of store expressions we are dealing with. */
|
/* Global holding the number of store expressions we are dealing with. */
|
static int num_stores;
|
static int num_stores;
|
|
|
/* Contains the edge_list returned by pre_edge_lcm. */
|
/* Contains the edge_list returned by pre_edge_lcm. */
|
static struct edge_list *edge_list;
|
static struct edge_list *edge_list;
|
|
|
static hashval_t
|
static hashval_t
|
pre_st_expr_hash (const void *p)
|
pre_st_expr_hash (const void *p)
|
{
|
{
|
int do_not_record_p = 0;
|
int do_not_record_p = 0;
|
const struct st_expr *const x = (const struct st_expr *) p;
|
const struct st_expr *const x = (const struct st_expr *) p;
|
return hash_rtx (x->pattern, GET_MODE (x->pattern), &do_not_record_p, NULL, false);
|
return hash_rtx (x->pattern, GET_MODE (x->pattern), &do_not_record_p, NULL, false);
|
}
|
}
|
|
|
static int
|
static int
|
pre_st_expr_eq (const void *p1, const void *p2)
|
pre_st_expr_eq (const void *p1, const void *p2)
|
{
|
{
|
const struct st_expr *const ptr1 = (const struct st_expr *) p1,
|
const struct st_expr *const ptr1 = (const struct st_expr *) p1,
|
*const ptr2 = (const struct st_expr *) p2;
|
*const ptr2 = (const struct st_expr *) p2;
|
return exp_equiv_p (ptr1->pattern, ptr2->pattern, 0, true);
|
return exp_equiv_p (ptr1->pattern, ptr2->pattern, 0, true);
|
}
|
}
|
|
|
/* This will search the st_expr list for a matching expression. If it
|
/* This will search the st_expr list for a matching expression. If it
|
doesn't find one, we create one and initialize it. */
|
doesn't find one, we create one and initialize it. */
|
|
|
static struct st_expr *
|
static struct st_expr *
|
st_expr_entry (rtx x)
|
st_expr_entry (rtx x)
|
{
|
{
|
int do_not_record_p = 0;
|
int do_not_record_p = 0;
|
struct st_expr * ptr;
|
struct st_expr * ptr;
|
unsigned int hash;
|
unsigned int hash;
|
void **slot;
|
void **slot;
|
struct st_expr e;
|
struct st_expr e;
|
|
|
hash = hash_rtx (x, GET_MODE (x), &do_not_record_p,
|
hash = hash_rtx (x, GET_MODE (x), &do_not_record_p,
|
NULL, /*have_reg_qty=*/false);
|
NULL, /*have_reg_qty=*/false);
|
|
|
e.pattern = x;
|
e.pattern = x;
|
slot = htab_find_slot_with_hash (store_motion_mems_table, &e, hash, INSERT);
|
slot = htab_find_slot_with_hash (store_motion_mems_table, &e, hash, INSERT);
|
if (*slot)
|
if (*slot)
|
return (struct st_expr *)*slot;
|
return (struct st_expr *)*slot;
|
|
|
ptr = XNEW (struct st_expr);
|
ptr = XNEW (struct st_expr);
|
|
|
ptr->next = store_motion_mems;
|
ptr->next = store_motion_mems;
|
ptr->pattern = x;
|
ptr->pattern = x;
|
ptr->pattern_regs = NULL_RTX;
|
ptr->pattern_regs = NULL_RTX;
|
ptr->antic_stores = NULL_RTX;
|
ptr->antic_stores = NULL_RTX;
|
ptr->avail_stores = NULL_RTX;
|
ptr->avail_stores = NULL_RTX;
|
ptr->reaching_reg = NULL_RTX;
|
ptr->reaching_reg = NULL_RTX;
|
ptr->index = 0;
|
ptr->index = 0;
|
ptr->hash_index = hash;
|
ptr->hash_index = hash;
|
store_motion_mems = ptr;
|
store_motion_mems = ptr;
|
*slot = ptr;
|
*slot = ptr;
|
|
|
return ptr;
|
return ptr;
|
}
|
}
|
|
|
/* Free up an individual st_expr entry. */
|
/* Free up an individual st_expr entry. */
|
|
|
static void
|
static void
|
free_st_expr_entry (struct st_expr * ptr)
|
free_st_expr_entry (struct st_expr * ptr)
|
{
|
{
|
free_INSN_LIST_list (& ptr->antic_stores);
|
free_INSN_LIST_list (& ptr->antic_stores);
|
free_INSN_LIST_list (& ptr->avail_stores);
|
free_INSN_LIST_list (& ptr->avail_stores);
|
|
|
free (ptr);
|
free (ptr);
|
}
|
}
|
|
|
/* Free up all memory associated with the st_expr list. */
|
/* Free up all memory associated with the st_expr list. */
|
|
|
static void
|
static void
|
free_store_motion_mems (void)
|
free_store_motion_mems (void)
|
{
|
{
|
if (store_motion_mems_table)
|
if (store_motion_mems_table)
|
htab_delete (store_motion_mems_table);
|
htab_delete (store_motion_mems_table);
|
store_motion_mems_table = NULL;
|
store_motion_mems_table = NULL;
|
|
|
while (store_motion_mems)
|
while (store_motion_mems)
|
{
|
{
|
struct st_expr * tmp = store_motion_mems;
|
struct st_expr * tmp = store_motion_mems;
|
store_motion_mems = store_motion_mems->next;
|
store_motion_mems = store_motion_mems->next;
|
free_st_expr_entry (tmp);
|
free_st_expr_entry (tmp);
|
}
|
}
|
store_motion_mems = NULL;
|
store_motion_mems = NULL;
|
}
|
}
|
|
|
/* Assign each element of the list of mems a monotonically increasing value. */
|
/* Assign each element of the list of mems a monotonically increasing value. */
|
|
|
static int
|
static int
|
enumerate_store_motion_mems (void)
|
enumerate_store_motion_mems (void)
|
{
|
{
|
struct st_expr * ptr;
|
struct st_expr * ptr;
|
int n = 0;
|
int n = 0;
|
|
|
for (ptr = store_motion_mems; ptr != NULL; ptr = ptr->next)
|
for (ptr = store_motion_mems; ptr != NULL; ptr = ptr->next)
|
ptr->index = n++;
|
ptr->index = n++;
|
|
|
return n;
|
return n;
|
}
|
}
|
|
|
/* Return first item in the list. */
|
/* Return first item in the list. */
|
|
|
static inline struct st_expr *
|
static inline struct st_expr *
|
first_st_expr (void)
|
first_st_expr (void)
|
{
|
{
|
return store_motion_mems;
|
return store_motion_mems;
|
}
|
}
|
|
|
/* Return the next item in the list after the specified one. */
|
/* Return the next item in the list after the specified one. */
|
|
|
static inline struct st_expr *
|
static inline struct st_expr *
|
next_st_expr (struct st_expr * ptr)
|
next_st_expr (struct st_expr * ptr)
|
{
|
{
|
return ptr->next;
|
return ptr->next;
|
}
|
}
|
|
|
/* Dump debugging info about the store_motion_mems list. */
|
/* Dump debugging info about the store_motion_mems list. */
|
|
|
static void
|
static void
|
print_store_motion_mems (FILE * file)
|
print_store_motion_mems (FILE * file)
|
{
|
{
|
struct st_expr * ptr;
|
struct st_expr * ptr;
|
|
|
fprintf (dump_file, "STORE_MOTION list of MEM exprs considered:\n");
|
fprintf (dump_file, "STORE_MOTION list of MEM exprs considered:\n");
|
|
|
for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
|
for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
|
{
|
{
|
fprintf (file, " Pattern (%3d): ", ptr->index);
|
fprintf (file, " Pattern (%3d): ", ptr->index);
|
|
|
print_rtl (file, ptr->pattern);
|
print_rtl (file, ptr->pattern);
|
|
|
fprintf (file, "\n ANTIC stores : ");
|
fprintf (file, "\n ANTIC stores : ");
|
|
|
if (ptr->antic_stores)
|
if (ptr->antic_stores)
|
print_rtl (file, ptr->antic_stores);
|
print_rtl (file, ptr->antic_stores);
|
else
|
else
|
fprintf (file, "(nil)");
|
fprintf (file, "(nil)");
|
|
|
fprintf (file, "\n AVAIL stores : ");
|
fprintf (file, "\n AVAIL stores : ");
|
|
|
if (ptr->avail_stores)
|
if (ptr->avail_stores)
|
print_rtl (file, ptr->avail_stores);
|
print_rtl (file, ptr->avail_stores);
|
else
|
else
|
fprintf (file, "(nil)");
|
fprintf (file, "(nil)");
|
|
|
fprintf (file, "\n\n");
|
fprintf (file, "\n\n");
|
}
|
}
|
|
|
fprintf (file, "\n");
|
fprintf (file, "\n");
|
}
|
}
|
|
|
/* Return zero if some of the registers in list X are killed
|
/* Return zero if some of the registers in list X are killed
|
due to set of registers in bitmap REGS_SET. */
|
due to set of registers in bitmap REGS_SET. */
|
|
|
static bool
|
static bool
|
store_ops_ok (const_rtx x, int *regs_set)
|
store_ops_ok (const_rtx x, int *regs_set)
|
{
|
{
|
const_rtx reg;
|
const_rtx reg;
|
|
|
for (; x; x = XEXP (x, 1))
|
for (; x; x = XEXP (x, 1))
|
{
|
{
|
reg = XEXP (x, 0);
|
reg = XEXP (x, 0);
|
if (regs_set[REGNO(reg)])
|
if (regs_set[REGNO(reg)])
|
return false;
|
return false;
|
}
|
}
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Helper for extract_mentioned_regs. */
|
/* Helper for extract_mentioned_regs. */
|
|
|
static int
|
static int
|
extract_mentioned_regs_1 (rtx *loc, void *data)
|
extract_mentioned_regs_1 (rtx *loc, void *data)
|
{
|
{
|
rtx *mentioned_regs_p = (rtx *) data;
|
rtx *mentioned_regs_p = (rtx *) data;
|
|
|
if (REG_P (*loc))
|
if (REG_P (*loc))
|
*mentioned_regs_p = alloc_EXPR_LIST (0, *loc, *mentioned_regs_p);
|
*mentioned_regs_p = alloc_EXPR_LIST (0, *loc, *mentioned_regs_p);
|
|
|
return 0;
|
return 0;
|
}
|
}
|
|
|
/* Returns a list of registers mentioned in X.
|
/* Returns a list of registers mentioned in X.
|
FIXME: A regset would be prettier and less expensive. */
|
FIXME: A regset would be prettier and less expensive. */
|
|
|
static rtx
|
static rtx
|
extract_mentioned_regs (rtx x)
|
extract_mentioned_regs (rtx x)
|
{
|
{
|
rtx mentioned_regs = NULL;
|
rtx mentioned_regs = NULL;
|
for_each_rtx (&x, extract_mentioned_regs_1, &mentioned_regs);
|
for_each_rtx (&x, extract_mentioned_regs_1, &mentioned_regs);
|
return mentioned_regs;
|
return mentioned_regs;
|
}
|
}
|
|
|
/* Check to see if the load X is aliased with STORE_PATTERN.
|
/* Check to see if the load X is aliased with STORE_PATTERN.
|
AFTER is true if we are checking the case when STORE_PATTERN occurs
|
AFTER is true if we are checking the case when STORE_PATTERN occurs
|
after the X. */
|
after the X. */
|
|
|
static bool
|
static bool
|
load_kills_store (const_rtx x, const_rtx store_pattern, int after)
|
load_kills_store (const_rtx x, const_rtx store_pattern, int after)
|
{
|
{
|
if (after)
|
if (after)
|
return anti_dependence (x, store_pattern);
|
return anti_dependence (x, store_pattern);
|
else
|
else
|
return true_dependence (store_pattern, GET_MODE (store_pattern), x,
|
return true_dependence (store_pattern, GET_MODE (store_pattern), x,
|
rtx_addr_varies_p);
|
rtx_addr_varies_p);
|
}
|
}
|
|
|
/* Go through the entire rtx X, looking for any loads which might alias
|
/* Go through the entire rtx X, looking for any loads which might alias
|
STORE_PATTERN. Return true if found.
|
STORE_PATTERN. Return true if found.
|
AFTER is true if we are checking the case when STORE_PATTERN occurs
|
AFTER is true if we are checking the case when STORE_PATTERN occurs
|
after the insn X. */
|
after the insn X. */
|
|
|
static bool
|
static bool
|
find_loads (const_rtx x, const_rtx store_pattern, int after)
|
find_loads (const_rtx x, const_rtx store_pattern, int after)
|
{
|
{
|
const char * fmt;
|
const char * fmt;
|
int i, j;
|
int i, j;
|
int ret = false;
|
int ret = false;
|
|
|
if (!x)
|
if (!x)
|
return false;
|
return false;
|
|
|
if (GET_CODE (x) == SET)
|
if (GET_CODE (x) == SET)
|
x = SET_SRC (x);
|
x = SET_SRC (x);
|
|
|
if (MEM_P (x))
|
if (MEM_P (x))
|
{
|
{
|
if (load_kills_store (x, store_pattern, after))
|
if (load_kills_store (x, store_pattern, after))
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Recursively process the insn. */
|
/* Recursively process the insn. */
|
fmt = GET_RTX_FORMAT (GET_CODE (x));
|
fmt = GET_RTX_FORMAT (GET_CODE (x));
|
|
|
for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0 && !ret; i--)
|
for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0 && !ret; i--)
|
{
|
{
|
if (fmt[i] == 'e')
|
if (fmt[i] == 'e')
|
ret |= find_loads (XEXP (x, i), store_pattern, after);
|
ret |= find_loads (XEXP (x, i), store_pattern, after);
|
else if (fmt[i] == 'E')
|
else if (fmt[i] == 'E')
|
for (j = XVECLEN (x, i) - 1; j >= 0; j--)
|
for (j = XVECLEN (x, i) - 1; j >= 0; j--)
|
ret |= find_loads (XVECEXP (x, i, j), store_pattern, after);
|
ret |= find_loads (XVECEXP (x, i, j), store_pattern, after);
|
}
|
}
|
return ret;
|
return ret;
|
}
|
}
|
|
|
/* Go through pattern PAT looking for any loads which might kill the
|
/* Go through pattern PAT looking for any loads which might kill the
|
store in X. Return true if found.
|
store in X. Return true if found.
|
AFTER is true if we are checking the case when loads kill X occurs
|
AFTER is true if we are checking the case when loads kill X occurs
|
after the insn for PAT. */
|
after the insn for PAT. */
|
|
|
static inline bool
|
static inline bool
|
store_killed_in_pat (const_rtx x, const_rtx pat, int after)
|
store_killed_in_pat (const_rtx x, const_rtx pat, int after)
|
{
|
{
|
if (GET_CODE (pat) == SET)
|
if (GET_CODE (pat) == SET)
|
{
|
{
|
rtx dest = SET_DEST (pat);
|
rtx dest = SET_DEST (pat);
|
|
|
if (GET_CODE (dest) == ZERO_EXTRACT)
|
if (GET_CODE (dest) == ZERO_EXTRACT)
|
dest = XEXP (dest, 0);
|
dest = XEXP (dest, 0);
|
|
|
/* Check for memory stores to aliased objects. */
|
/* Check for memory stores to aliased objects. */
|
if (MEM_P (dest)
|
if (MEM_P (dest)
|
&& !exp_equiv_p (dest, x, 0, true))
|
&& !exp_equiv_p (dest, x, 0, true))
|
{
|
{
|
if (after)
|
if (after)
|
{
|
{
|
if (output_dependence (dest, x))
|
if (output_dependence (dest, x))
|
return true;
|
return true;
|
}
|
}
|
else
|
else
|
{
|
{
|
if (output_dependence (x, dest))
|
if (output_dependence (x, dest))
|
return true;
|
return true;
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
if (find_loads (pat, x, after))
|
if (find_loads (pat, x, after))
|
return true;
|
return true;
|
|
|
return false;
|
return false;
|
}
|
}
|
|
|
/* Check if INSN kills the store pattern X (is aliased with it).
|
/* Check if INSN kills the store pattern X (is aliased with it).
|
AFTER is true if we are checking the case when store X occurs
|
AFTER is true if we are checking the case when store X occurs
|
after the insn. Return true if it does. */
|
after the insn. Return true if it does. */
|
|
|
static bool
|
static bool
|
store_killed_in_insn (const_rtx x, const_rtx x_regs, const_rtx insn, int after)
|
store_killed_in_insn (const_rtx x, const_rtx x_regs, const_rtx insn, int after)
|
{
|
{
|
const_rtx reg, base, note, pat;
|
const_rtx reg, base, note, pat;
|
|
|
if (! NONDEBUG_INSN_P (insn))
|
if (! NONDEBUG_INSN_P (insn))
|
return false;
|
return false;
|
|
|
if (CALL_P (insn))
|
if (CALL_P (insn))
|
{
|
{
|
/* A normal or pure call might read from pattern,
|
/* A normal or pure call might read from pattern,
|
but a const call will not. */
|
but a const call will not. */
|
if (!RTL_CONST_CALL_P (insn))
|
if (!RTL_CONST_CALL_P (insn))
|
return true;
|
return true;
|
|
|
/* But even a const call reads its parameters. Check whether the
|
/* But even a const call reads its parameters. Check whether the
|
base of some of registers used in mem is stack pointer. */
|
base of some of registers used in mem is stack pointer. */
|
for (reg = x_regs; reg; reg = XEXP (reg, 1))
|
for (reg = x_regs; reg; reg = XEXP (reg, 1))
|
{
|
{
|
base = find_base_term (XEXP (reg, 0));
|
base = find_base_term (XEXP (reg, 0));
|
if (!base
|
if (!base
|
|| (GET_CODE (base) == ADDRESS
|
|| (GET_CODE (base) == ADDRESS
|
&& GET_MODE (base) == Pmode
|
&& GET_MODE (base) == Pmode
|
&& XEXP (base, 0) == stack_pointer_rtx))
|
&& XEXP (base, 0) == stack_pointer_rtx))
|
return true;
|
return true;
|
}
|
}
|
|
|
return false;
|
return false;
|
}
|
}
|
|
|
pat = PATTERN (insn);
|
pat = PATTERN (insn);
|
if (GET_CODE (pat) == SET)
|
if (GET_CODE (pat) == SET)
|
{
|
{
|
if (store_killed_in_pat (x, pat, after))
|
if (store_killed_in_pat (x, pat, after))
|
return true;
|
return true;
|
}
|
}
|
else if (GET_CODE (pat) == PARALLEL)
|
else if (GET_CODE (pat) == PARALLEL)
|
{
|
{
|
int i;
|
int i;
|
|
|
for (i = 0; i < XVECLEN (pat, 0); i++)
|
for (i = 0; i < XVECLEN (pat, 0); i++)
|
if (store_killed_in_pat (x, XVECEXP (pat, 0, i), after))
|
if (store_killed_in_pat (x, XVECEXP (pat, 0, i), after))
|
return true;
|
return true;
|
}
|
}
|
else if (find_loads (PATTERN (insn), x, after))
|
else if (find_loads (PATTERN (insn), x, after))
|
return true;
|
return true;
|
|
|
/* If this insn has a REG_EQUAL or REG_EQUIV note referencing a memory
|
/* If this insn has a REG_EQUAL or REG_EQUIV note referencing a memory
|
location aliased with X, then this insn kills X. */
|
location aliased with X, then this insn kills X. */
|
note = find_reg_equal_equiv_note (insn);
|
note = find_reg_equal_equiv_note (insn);
|
if (! note)
|
if (! note)
|
return false;
|
return false;
|
note = XEXP (note, 0);
|
note = XEXP (note, 0);
|
|
|
/* However, if the note represents a must alias rather than a may
|
/* However, if the note represents a must alias rather than a may
|
alias relationship, then it does not kill X. */
|
alias relationship, then it does not kill X. */
|
if (exp_equiv_p (note, x, 0, true))
|
if (exp_equiv_p (note, x, 0, true))
|
return false;
|
return false;
|
|
|
/* See if there are any aliased loads in the note. */
|
/* See if there are any aliased loads in the note. */
|
return find_loads (note, x, after);
|
return find_loads (note, x, after);
|
}
|
}
|
|
|
/* Returns true if the expression X is loaded or clobbered on or after INSN
|
/* Returns true if the expression X is loaded or clobbered on or after INSN
|
within basic block BB. REGS_SET_AFTER is bitmap of registers set in
|
within basic block BB. REGS_SET_AFTER is bitmap of registers set in
|
or after the insn. X_REGS is list of registers mentioned in X. If the store
|
or after the insn. X_REGS is list of registers mentioned in X. If the store
|
is killed, return the last insn in that it occurs in FAIL_INSN. */
|
is killed, return the last insn in that it occurs in FAIL_INSN. */
|
|
|
static bool
|
static bool
|
store_killed_after (const_rtx x, const_rtx x_regs, const_rtx insn, const_basic_block bb,
|
store_killed_after (const_rtx x, const_rtx x_regs, const_rtx insn, const_basic_block bb,
|
int *regs_set_after, rtx *fail_insn)
|
int *regs_set_after, rtx *fail_insn)
|
{
|
{
|
rtx last = BB_END (bb), act;
|
rtx last = BB_END (bb), act;
|
|
|
if (!store_ops_ok (x_regs, regs_set_after))
|
if (!store_ops_ok (x_regs, regs_set_after))
|
{
|
{
|
/* We do not know where it will happen. */
|
/* We do not know where it will happen. */
|
if (fail_insn)
|
if (fail_insn)
|
*fail_insn = NULL_RTX;
|
*fail_insn = NULL_RTX;
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Scan from the end, so that fail_insn is determined correctly. */
|
/* Scan from the end, so that fail_insn is determined correctly. */
|
for (act = last; act != PREV_INSN (insn); act = PREV_INSN (act))
|
for (act = last; act != PREV_INSN (insn); act = PREV_INSN (act))
|
if (store_killed_in_insn (x, x_regs, act, false))
|
if (store_killed_in_insn (x, x_regs, act, false))
|
{
|
{
|
if (fail_insn)
|
if (fail_insn)
|
*fail_insn = act;
|
*fail_insn = act;
|
return true;
|
return true;
|
}
|
}
|
|
|
return false;
|
return false;
|
}
|
}
|
|
|
/* Returns true if the expression X is loaded or clobbered on or before INSN
|
/* Returns true if the expression X is loaded or clobbered on or before INSN
|
within basic block BB. X_REGS is list of registers mentioned in X.
|
within basic block BB. X_REGS is list of registers mentioned in X.
|
REGS_SET_BEFORE is bitmap of registers set before or in this insn. */
|
REGS_SET_BEFORE is bitmap of registers set before or in this insn. */
|
static bool
|
static bool
|
store_killed_before (const_rtx x, const_rtx x_regs, const_rtx insn, const_basic_block bb,
|
store_killed_before (const_rtx x, const_rtx x_regs, const_rtx insn, const_basic_block bb,
|
int *regs_set_before)
|
int *regs_set_before)
|
{
|
{
|
rtx first = BB_HEAD (bb);
|
rtx first = BB_HEAD (bb);
|
|
|
if (!store_ops_ok (x_regs, regs_set_before))
|
if (!store_ops_ok (x_regs, regs_set_before))
|
return true;
|
return true;
|
|
|
for ( ; insn != PREV_INSN (first); insn = PREV_INSN (insn))
|
for ( ; insn != PREV_INSN (first); insn = PREV_INSN (insn))
|
if (store_killed_in_insn (x, x_regs, insn, true))
|
if (store_killed_in_insn (x, x_regs, insn, true))
|
return true;
|
return true;
|
|
|
return false;
|
return false;
|
}
|
}
|
|
|
/* The last insn in the basic block that compute_store_table is processing,
|
/* The last insn in the basic block that compute_store_table is processing,
|
where store_killed_after is true for X.
|
where store_killed_after is true for X.
|
Since we go through the basic block from BB_END to BB_HEAD, this is
|
Since we go through the basic block from BB_END to BB_HEAD, this is
|
also the available store at the end of the basic block. Therefore
|
also the available store at the end of the basic block. Therefore
|
this is in effect a cache, to avoid calling store_killed_after for
|
this is in effect a cache, to avoid calling store_killed_after for
|
equivalent aliasing store expressions.
|
equivalent aliasing store expressions.
|
This value is only meaningful during the computation of the store
|
This value is only meaningful during the computation of the store
|
table. We hi-jack the REACHING_REG field of struct st_expr to save
|
table. We hi-jack the REACHING_REG field of struct st_expr to save
|
a bit of memory. */
|
a bit of memory. */
|
#define LAST_AVAIL_CHECK_FAILURE(x) ((x)->reaching_reg)
|
#define LAST_AVAIL_CHECK_FAILURE(x) ((x)->reaching_reg)
|
|
|
/* Determine whether INSN is MEM store pattern that we will consider moving.
|
/* Determine whether INSN is MEM store pattern that we will consider moving.
|
REGS_SET_BEFORE is bitmap of registers set before (and including) the
|
REGS_SET_BEFORE is bitmap of registers set before (and including) the
|
current insn, REGS_SET_AFTER is bitmap of registers set after (and
|
current insn, REGS_SET_AFTER is bitmap of registers set after (and
|
including) the insn in this basic block. We must be passing through BB from
|
including) the insn in this basic block. We must be passing through BB from
|
head to end, as we are using this fact to speed things up.
|
head to end, as we are using this fact to speed things up.
|
|
|
The results are stored this way:
|
The results are stored this way:
|
|
|
-- the first anticipatable expression is added into ANTIC_STORES
|
-- the first anticipatable expression is added into ANTIC_STORES
|
-- if the processed expression is not anticipatable, NULL_RTX is added
|
-- if the processed expression is not anticipatable, NULL_RTX is added
|
there instead, so that we can use it as indicator that no further
|
there instead, so that we can use it as indicator that no further
|
expression of this type may be anticipatable
|
expression of this type may be anticipatable
|
-- if the expression is available, it is added as head of AVAIL_STORES;
|
-- if the expression is available, it is added as head of AVAIL_STORES;
|
consequently, all of them but this head are dead and may be deleted.
|
consequently, all of them but this head are dead and may be deleted.
|
-- if the expression is not available, the insn due to that it fails to be
|
-- if the expression is not available, the insn due to that it fails to be
|
available is stored in REACHING_REG (via LAST_AVAIL_CHECK_FAILURE).
|
available is stored in REACHING_REG (via LAST_AVAIL_CHECK_FAILURE).
|
|
|
The things are complicated a bit by fact that there already may be stores
|
The things are complicated a bit by fact that there already may be stores
|
to the same MEM from other blocks; also caller must take care of the
|
to the same MEM from other blocks; also caller must take care of the
|
necessary cleanup of the temporary markers after end of the basic block.
|
necessary cleanup of the temporary markers after end of the basic block.
|
*/
|
*/
|
|
|
static void
|
static void
|
find_moveable_store (rtx insn, int *regs_set_before, int *regs_set_after)
|
find_moveable_store (rtx insn, int *regs_set_before, int *regs_set_after)
|
{
|
{
|
struct st_expr * ptr;
|
struct st_expr * ptr;
|
rtx dest, set, tmp;
|
rtx dest, set, tmp;
|
int check_anticipatable, check_available;
|
int check_anticipatable, check_available;
|
basic_block bb = BLOCK_FOR_INSN (insn);
|
basic_block bb = BLOCK_FOR_INSN (insn);
|
|
|
set = single_set (insn);
|
set = single_set (insn);
|
if (!set)
|
if (!set)
|
return;
|
return;
|
|
|
dest = SET_DEST (set);
|
dest = SET_DEST (set);
|
|
|
if (! MEM_P (dest) || MEM_VOLATILE_P (dest)
|
if (! MEM_P (dest) || MEM_VOLATILE_P (dest)
|
|| GET_MODE (dest) == BLKmode)
|
|| GET_MODE (dest) == BLKmode)
|
return;
|
return;
|
|
|
if (side_effects_p (dest))
|
if (side_effects_p (dest))
|
return;
|
return;
|
|
|
/* If we are handling exceptions, we must be careful with memory references
|
/* If we are handling exceptions, we must be careful with memory references
|
that may trap. If we are not, the behavior is undefined, so we may just
|
that may trap. If we are not, the behavior is undefined, so we may just
|
continue. */
|
continue. */
|
if (flag_non_call_exceptions && may_trap_p (dest))
|
if (flag_non_call_exceptions && may_trap_p (dest))
|
return;
|
return;
|
|
|
/* Even if the destination cannot trap, the source may. In this case we'd
|
/* Even if the destination cannot trap, the source may. In this case we'd
|
need to handle updating the REG_EH_REGION note. */
|
need to handle updating the REG_EH_REGION note. */
|
if (find_reg_note (insn, REG_EH_REGION, NULL_RTX))
|
if (find_reg_note (insn, REG_EH_REGION, NULL_RTX))
|
return;
|
return;
|
|
|
/* Make sure that the SET_SRC of this store insns can be assigned to
|
/* Make sure that the SET_SRC of this store insns can be assigned to
|
a register, or we will fail later on in replace_store_insn, which
|
a register, or we will fail later on in replace_store_insn, which
|
assumes that we can do this. But sometimes the target machine has
|
assumes that we can do this. But sometimes the target machine has
|
oddities like MEM read-modify-write instruction. See for example
|
oddities like MEM read-modify-write instruction. See for example
|
PR24257. */
|
PR24257. */
|
if (!can_assign_to_reg_without_clobbers_p (SET_SRC (set)))
|
if (!can_assign_to_reg_without_clobbers_p (SET_SRC (set)))
|
return;
|
return;
|
|
|
ptr = st_expr_entry (dest);
|
ptr = st_expr_entry (dest);
|
if (!ptr->pattern_regs)
|
if (!ptr->pattern_regs)
|
ptr->pattern_regs = extract_mentioned_regs (dest);
|
ptr->pattern_regs = extract_mentioned_regs (dest);
|
|
|
/* Do not check for anticipatability if we either found one anticipatable
|
/* Do not check for anticipatability if we either found one anticipatable
|
store already, or tested for one and found out that it was killed. */
|
store already, or tested for one and found out that it was killed. */
|
check_anticipatable = 0;
|
check_anticipatable = 0;
|
if (!ptr->antic_stores)
|
if (!ptr->antic_stores)
|
check_anticipatable = 1;
|
check_anticipatable = 1;
|
else
|
else
|
{
|
{
|
tmp = XEXP (ptr->antic_stores, 0);
|
tmp = XEXP (ptr->antic_stores, 0);
|
if (tmp != NULL_RTX
|
if (tmp != NULL_RTX
|
&& BLOCK_FOR_INSN (tmp) != bb)
|
&& BLOCK_FOR_INSN (tmp) != bb)
|
check_anticipatable = 1;
|
check_anticipatable = 1;
|
}
|
}
|
if (check_anticipatable)
|
if (check_anticipatable)
|
{
|
{
|
if (store_killed_before (dest, ptr->pattern_regs, insn, bb, regs_set_before))
|
if (store_killed_before (dest, ptr->pattern_regs, insn, bb, regs_set_before))
|
tmp = NULL_RTX;
|
tmp = NULL_RTX;
|
else
|
else
|
tmp = insn;
|
tmp = insn;
|
ptr->antic_stores = alloc_INSN_LIST (tmp, ptr->antic_stores);
|
ptr->antic_stores = alloc_INSN_LIST (tmp, ptr->antic_stores);
|
}
|
}
|
|
|
/* It is not necessary to check whether store is available if we did
|
/* It is not necessary to check whether store is available if we did
|
it successfully before; if we failed before, do not bother to check
|
it successfully before; if we failed before, do not bother to check
|
until we reach the insn that caused us to fail. */
|
until we reach the insn that caused us to fail. */
|
check_available = 0;
|
check_available = 0;
|
if (!ptr->avail_stores)
|
if (!ptr->avail_stores)
|
check_available = 1;
|
check_available = 1;
|
else
|
else
|
{
|
{
|
tmp = XEXP (ptr->avail_stores, 0);
|
tmp = XEXP (ptr->avail_stores, 0);
|
if (BLOCK_FOR_INSN (tmp) != bb)
|
if (BLOCK_FOR_INSN (tmp) != bb)
|
check_available = 1;
|
check_available = 1;
|
}
|
}
|
if (check_available)
|
if (check_available)
|
{
|
{
|
/* Check that we have already reached the insn at that the check
|
/* Check that we have already reached the insn at that the check
|
failed last time. */
|
failed last time. */
|
if (LAST_AVAIL_CHECK_FAILURE (ptr))
|
if (LAST_AVAIL_CHECK_FAILURE (ptr))
|
{
|
{
|
for (tmp = BB_END (bb);
|
for (tmp = BB_END (bb);
|
tmp != insn && tmp != LAST_AVAIL_CHECK_FAILURE (ptr);
|
tmp != insn && tmp != LAST_AVAIL_CHECK_FAILURE (ptr);
|
tmp = PREV_INSN (tmp))
|
tmp = PREV_INSN (tmp))
|
continue;
|
continue;
|
if (tmp == insn)
|
if (tmp == insn)
|
check_available = 0;
|
check_available = 0;
|
}
|
}
|
else
|
else
|
check_available = store_killed_after (dest, ptr->pattern_regs, insn,
|
check_available = store_killed_after (dest, ptr->pattern_regs, insn,
|
bb, regs_set_after,
|
bb, regs_set_after,
|
&LAST_AVAIL_CHECK_FAILURE (ptr));
|
&LAST_AVAIL_CHECK_FAILURE (ptr));
|
}
|
}
|
if (!check_available)
|
if (!check_available)
|
ptr->avail_stores = alloc_INSN_LIST (insn, ptr->avail_stores);
|
ptr->avail_stores = alloc_INSN_LIST (insn, ptr->avail_stores);
|
}
|
}
|
|
|
/* Find available and anticipatable stores. */
|
/* Find available and anticipatable stores. */
|
|
|
static int
|
static int
|
compute_store_table (void)
|
compute_store_table (void)
|
{
|
{
|
int ret;
|
int ret;
|
basic_block bb;
|
basic_block bb;
|
#ifdef ENABLE_CHECKING
|
#ifdef ENABLE_CHECKING
|
unsigned regno;
|
unsigned regno;
|
#endif
|
#endif
|
rtx insn, tmp;
|
rtx insn, tmp;
|
df_ref *def_rec;
|
df_ref *def_rec;
|
int *last_set_in, *already_set;
|
int *last_set_in, *already_set;
|
struct st_expr * ptr, **prev_next_ptr_ptr;
|
struct st_expr * ptr, **prev_next_ptr_ptr;
|
unsigned int max_gcse_regno = max_reg_num ();
|
unsigned int max_gcse_regno = max_reg_num ();
|
|
|
store_motion_mems = NULL;
|
store_motion_mems = NULL;
|
store_motion_mems_table = htab_create (13, pre_st_expr_hash,
|
store_motion_mems_table = htab_create (13, pre_st_expr_hash,
|
pre_st_expr_eq, NULL);
|
pre_st_expr_eq, NULL);
|
last_set_in = XCNEWVEC (int, max_gcse_regno);
|
last_set_in = XCNEWVEC (int, max_gcse_regno);
|
already_set = XNEWVEC (int, max_gcse_regno);
|
already_set = XNEWVEC (int, max_gcse_regno);
|
|
|
/* Find all the stores we care about. */
|
/* Find all the stores we care about. */
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
{
|
{
|
/* First compute the registers set in this block. */
|
/* First compute the registers set in this block. */
|
FOR_BB_INSNS (bb, insn)
|
FOR_BB_INSNS (bb, insn)
|
{
|
{
|
|
|
if (! NONDEBUG_INSN_P (insn))
|
if (! NONDEBUG_INSN_P (insn))
|
continue;
|
continue;
|
|
|
for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
|
for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
|
last_set_in[DF_REF_REGNO (*def_rec)] = INSN_UID (insn);
|
last_set_in[DF_REF_REGNO (*def_rec)] = INSN_UID (insn);
|
}
|
}
|
|
|
/* Now find the stores. */
|
/* Now find the stores. */
|
memset (already_set, 0, sizeof (int) * max_gcse_regno);
|
memset (already_set, 0, sizeof (int) * max_gcse_regno);
|
FOR_BB_INSNS (bb, insn)
|
FOR_BB_INSNS (bb, insn)
|
{
|
{
|
if (! NONDEBUG_INSN_P (insn))
|
if (! NONDEBUG_INSN_P (insn))
|
continue;
|
continue;
|
|
|
for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
|
for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
|
already_set[DF_REF_REGNO (*def_rec)] = INSN_UID (insn);
|
already_set[DF_REF_REGNO (*def_rec)] = INSN_UID (insn);
|
|
|
/* Now that we've marked regs, look for stores. */
|
/* Now that we've marked regs, look for stores. */
|
find_moveable_store (insn, already_set, last_set_in);
|
find_moveable_store (insn, already_set, last_set_in);
|
|
|
/* Unmark regs that are no longer set. */
|
/* Unmark regs that are no longer set. */
|
for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
|
for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
|
if (last_set_in[DF_REF_REGNO (*def_rec)] == INSN_UID (insn))
|
if (last_set_in[DF_REF_REGNO (*def_rec)] == INSN_UID (insn))
|
last_set_in[DF_REF_REGNO (*def_rec)] = 0;
|
last_set_in[DF_REF_REGNO (*def_rec)] = 0;
|
}
|
}
|
|
|
#ifdef ENABLE_CHECKING
|
#ifdef ENABLE_CHECKING
|
/* last_set_in should now be all-zero. */
|
/* last_set_in should now be all-zero. */
|
for (regno = 0; regno < max_gcse_regno; regno++)
|
for (regno = 0; regno < max_gcse_regno; regno++)
|
gcc_assert (!last_set_in[regno]);
|
gcc_assert (!last_set_in[regno]);
|
#endif
|
#endif
|
|
|
/* Clear temporary marks. */
|
/* Clear temporary marks. */
|
for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
|
for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
|
{
|
{
|
LAST_AVAIL_CHECK_FAILURE (ptr) = NULL_RTX;
|
LAST_AVAIL_CHECK_FAILURE (ptr) = NULL_RTX;
|
if (ptr->antic_stores
|
if (ptr->antic_stores
|
&& (tmp = XEXP (ptr->antic_stores, 0)) == NULL_RTX)
|
&& (tmp = XEXP (ptr->antic_stores, 0)) == NULL_RTX)
|
ptr->antic_stores = XEXP (ptr->antic_stores, 1);
|
ptr->antic_stores = XEXP (ptr->antic_stores, 1);
|
}
|
}
|
}
|
}
|
|
|
/* Remove the stores that are not available anywhere, as there will
|
/* Remove the stores that are not available anywhere, as there will
|
be no opportunity to optimize them. */
|
be no opportunity to optimize them. */
|
for (ptr = store_motion_mems, prev_next_ptr_ptr = &store_motion_mems;
|
for (ptr = store_motion_mems, prev_next_ptr_ptr = &store_motion_mems;
|
ptr != NULL;
|
ptr != NULL;
|
ptr = *prev_next_ptr_ptr)
|
ptr = *prev_next_ptr_ptr)
|
{
|
{
|
if (! ptr->avail_stores)
|
if (! ptr->avail_stores)
|
{
|
{
|
*prev_next_ptr_ptr = ptr->next;
|
*prev_next_ptr_ptr = ptr->next;
|
htab_remove_elt_with_hash (store_motion_mems_table,
|
htab_remove_elt_with_hash (store_motion_mems_table,
|
ptr, ptr->hash_index);
|
ptr, ptr->hash_index);
|
free_st_expr_entry (ptr);
|
free_st_expr_entry (ptr);
|
}
|
}
|
else
|
else
|
prev_next_ptr_ptr = &ptr->next;
|
prev_next_ptr_ptr = &ptr->next;
|
}
|
}
|
|
|
ret = enumerate_store_motion_mems ();
|
ret = enumerate_store_motion_mems ();
|
|
|
if (dump_file)
|
if (dump_file)
|
print_store_motion_mems (dump_file);
|
print_store_motion_mems (dump_file);
|
|
|
free (last_set_in);
|
free (last_set_in);
|
free (already_set);
|
free (already_set);
|
return ret;
|
return ret;
|
}
|
}
|
|
|
/* In all code following after this, REACHING_REG has its original
|
/* In all code following after this, REACHING_REG has its original
|
meaning again. Avoid confusion, and undef the accessor macro for
|
meaning again. Avoid confusion, and undef the accessor macro for
|
the temporary marks usage in compute_store_table. */
|
the temporary marks usage in compute_store_table. */
|
#undef LAST_AVAIL_CHECK_FAILURE
|
#undef LAST_AVAIL_CHECK_FAILURE
|
|
|
/* Insert an instruction at the beginning of a basic block, and update
|
/* Insert an instruction at the beginning of a basic block, and update
|
the BB_HEAD if needed. */
|
the BB_HEAD if needed. */
|
|
|
static void
|
static void
|
insert_insn_start_basic_block (rtx insn, basic_block bb)
|
insert_insn_start_basic_block (rtx insn, basic_block bb)
|
{
|
{
|
/* Insert at start of successor block. */
|
/* Insert at start of successor block. */
|
rtx prev = PREV_INSN (BB_HEAD (bb));
|
rtx prev = PREV_INSN (BB_HEAD (bb));
|
rtx before = BB_HEAD (bb);
|
rtx before = BB_HEAD (bb);
|
while (before != 0)
|
while (before != 0)
|
{
|
{
|
if (! LABEL_P (before)
|
if (! LABEL_P (before)
|
&& !NOTE_INSN_BASIC_BLOCK_P (before))
|
&& !NOTE_INSN_BASIC_BLOCK_P (before))
|
break;
|
break;
|
prev = before;
|
prev = before;
|
if (prev == BB_END (bb))
|
if (prev == BB_END (bb))
|
break;
|
break;
|
before = NEXT_INSN (before);
|
before = NEXT_INSN (before);
|
}
|
}
|
|
|
insn = emit_insn_after_noloc (insn, prev, bb);
|
insn = emit_insn_after_noloc (insn, prev, bb);
|
|
|
if (dump_file)
|
if (dump_file)
|
{
|
{
|
fprintf (dump_file, "STORE_MOTION insert store at start of BB %d:\n",
|
fprintf (dump_file, "STORE_MOTION insert store at start of BB %d:\n",
|
bb->index);
|
bb->index);
|
print_inline_rtx (dump_file, insn, 6);
|
print_inline_rtx (dump_file, insn, 6);
|
fprintf (dump_file, "\n");
|
fprintf (dump_file, "\n");
|
}
|
}
|
}
|
}
|
|
|
/* This routine will insert a store on an edge. EXPR is the st_expr entry for
|
/* This routine will insert a store on an edge. EXPR is the st_expr entry for
|
the memory reference, and E is the edge to insert it on. Returns nonzero
|
the memory reference, and E is the edge to insert it on. Returns nonzero
|
if an edge insertion was performed. */
|
if an edge insertion was performed. */
|
|
|
static int
|
static int
|
insert_store (struct st_expr * expr, edge e)
|
insert_store (struct st_expr * expr, edge e)
|
{
|
{
|
rtx reg, insn;
|
rtx reg, insn;
|
basic_block bb;
|
basic_block bb;
|
edge tmp;
|
edge tmp;
|
edge_iterator ei;
|
edge_iterator ei;
|
|
|
/* We did all the deleted before this insert, so if we didn't delete a
|
/* We did all the deleted before this insert, so if we didn't delete a
|
store, then we haven't set the reaching reg yet either. */
|
store, then we haven't set the reaching reg yet either. */
|
if (expr->reaching_reg == NULL_RTX)
|
if (expr->reaching_reg == NULL_RTX)
|
return 0;
|
return 0;
|
|
|
if (e->flags & EDGE_FAKE)
|
if (e->flags & EDGE_FAKE)
|
return 0;
|
return 0;
|
|
|
reg = expr->reaching_reg;
|
reg = expr->reaching_reg;
|
insn = gen_move_insn (copy_rtx (expr->pattern), reg);
|
insn = gen_move_insn (copy_rtx (expr->pattern), reg);
|
|
|
/* If we are inserting this expression on ALL predecessor edges of a BB,
|
/* If we are inserting this expression on ALL predecessor edges of a BB,
|
insert it at the start of the BB, and reset the insert bits on the other
|
insert it at the start of the BB, and reset the insert bits on the other
|
edges so we don't try to insert it on the other edges. */
|
edges so we don't try to insert it on the other edges. */
|
bb = e->dest;
|
bb = e->dest;
|
FOR_EACH_EDGE (tmp, ei, e->dest->preds)
|
FOR_EACH_EDGE (tmp, ei, e->dest->preds)
|
if (!(tmp->flags & EDGE_FAKE))
|
if (!(tmp->flags & EDGE_FAKE))
|
{
|
{
|
int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
|
int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
|
|
|
gcc_assert (index != EDGE_INDEX_NO_EDGE);
|
gcc_assert (index != EDGE_INDEX_NO_EDGE);
|
if (! TEST_BIT (st_insert_map[index], expr->index))
|
if (! TEST_BIT (st_insert_map[index], expr->index))
|
break;
|
break;
|
}
|
}
|
|
|
/* If tmp is NULL, we found an insertion on every edge, blank the
|
/* If tmp is NULL, we found an insertion on every edge, blank the
|
insertion vector for these edges, and insert at the start of the BB. */
|
insertion vector for these edges, and insert at the start of the BB. */
|
if (!tmp && bb != EXIT_BLOCK_PTR)
|
if (!tmp && bb != EXIT_BLOCK_PTR)
|
{
|
{
|
FOR_EACH_EDGE (tmp, ei, e->dest->preds)
|
FOR_EACH_EDGE (tmp, ei, e->dest->preds)
|
{
|
{
|
int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
|
int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
|
RESET_BIT (st_insert_map[index], expr->index);
|
RESET_BIT (st_insert_map[index], expr->index);
|
}
|
}
|
insert_insn_start_basic_block (insn, bb);
|
insert_insn_start_basic_block (insn, bb);
|
return 0;
|
return 0;
|
}
|
}
|
|
|
/* We can't put stores in the front of blocks pointed to by abnormal
|
/* We can't put stores in the front of blocks pointed to by abnormal
|
edges since that may put a store where one didn't used to be. */
|
edges since that may put a store where one didn't used to be. */
|
gcc_assert (!(e->flags & EDGE_ABNORMAL));
|
gcc_assert (!(e->flags & EDGE_ABNORMAL));
|
|
|
insert_insn_on_edge (insn, e);
|
insert_insn_on_edge (insn, e);
|
|
|
if (dump_file)
|
if (dump_file)
|
{
|
{
|
fprintf (dump_file, "STORE_MOTION insert insn on edge (%d, %d):\n",
|
fprintf (dump_file, "STORE_MOTION insert insn on edge (%d, %d):\n",
|
e->src->index, e->dest->index);
|
e->src->index, e->dest->index);
|
print_inline_rtx (dump_file, insn, 6);
|
print_inline_rtx (dump_file, insn, 6);
|
fprintf (dump_file, "\n");
|
fprintf (dump_file, "\n");
|
}
|
}
|
|
|
return 1;
|
return 1;
|
}
|
}
|
|
|
/* Remove any REG_EQUAL or REG_EQUIV notes containing a reference to the
|
/* Remove any REG_EQUAL or REG_EQUIV notes containing a reference to the
|
memory location in SMEXPR set in basic block BB.
|
memory location in SMEXPR set in basic block BB.
|
|
|
This could be rather expensive. */
|
This could be rather expensive. */
|
|
|
static void
|
static void
|
remove_reachable_equiv_notes (basic_block bb, struct st_expr *smexpr)
|
remove_reachable_equiv_notes (basic_block bb, struct st_expr *smexpr)
|
{
|
{
|
edge_iterator *stack, ei;
|
edge_iterator *stack, ei;
|
int sp;
|
int sp;
|
edge act;
|
edge act;
|
sbitmap visited = sbitmap_alloc (last_basic_block);
|
sbitmap visited = sbitmap_alloc (last_basic_block);
|
rtx last, insn, note;
|
rtx last, insn, note;
|
rtx mem = smexpr->pattern;
|
rtx mem = smexpr->pattern;
|
|
|
stack = XNEWVEC (edge_iterator, n_basic_blocks);
|
stack = XNEWVEC (edge_iterator, n_basic_blocks);
|
sp = 0;
|
sp = 0;
|
ei = ei_start (bb->succs);
|
ei = ei_start (bb->succs);
|
|
|
sbitmap_zero (visited);
|
sbitmap_zero (visited);
|
|
|
act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container (ei), 0) : NULL);
|
act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container (ei), 0) : NULL);
|
while (1)
|
while (1)
|
{
|
{
|
if (!act)
|
if (!act)
|
{
|
{
|
if (!sp)
|
if (!sp)
|
{
|
{
|
free (stack);
|
free (stack);
|
sbitmap_free (visited);
|
sbitmap_free (visited);
|
return;
|
return;
|
}
|
}
|
act = ei_edge (stack[--sp]);
|
act = ei_edge (stack[--sp]);
|
}
|
}
|
bb = act->dest;
|
bb = act->dest;
|
|
|
if (bb == EXIT_BLOCK_PTR
|
if (bb == EXIT_BLOCK_PTR
|
|| TEST_BIT (visited, bb->index))
|
|| TEST_BIT (visited, bb->index))
|
{
|
{
|
if (!ei_end_p (ei))
|
if (!ei_end_p (ei))
|
ei_next (&ei);
|
ei_next (&ei);
|
act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
|
act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
|
continue;
|
continue;
|
}
|
}
|
SET_BIT (visited, bb->index);
|
SET_BIT (visited, bb->index);
|
|
|
if (TEST_BIT (st_antloc[bb->index], smexpr->index))
|
if (TEST_BIT (st_antloc[bb->index], smexpr->index))
|
{
|
{
|
for (last = smexpr->antic_stores;
|
for (last = smexpr->antic_stores;
|
BLOCK_FOR_INSN (XEXP (last, 0)) != bb;
|
BLOCK_FOR_INSN (XEXP (last, 0)) != bb;
|
last = XEXP (last, 1))
|
last = XEXP (last, 1))
|
continue;
|
continue;
|
last = XEXP (last, 0);
|
last = XEXP (last, 0);
|
}
|
}
|
else
|
else
|
last = NEXT_INSN (BB_END (bb));
|
last = NEXT_INSN (BB_END (bb));
|
|
|
for (insn = BB_HEAD (bb); insn != last; insn = NEXT_INSN (insn))
|
for (insn = BB_HEAD (bb); insn != last; insn = NEXT_INSN (insn))
|
if (NONDEBUG_INSN_P (insn))
|
if (NONDEBUG_INSN_P (insn))
|
{
|
{
|
note = find_reg_equal_equiv_note (insn);
|
note = find_reg_equal_equiv_note (insn);
|
if (!note || !exp_equiv_p (XEXP (note, 0), mem, 0, true))
|
if (!note || !exp_equiv_p (XEXP (note, 0), mem, 0, true))
|
continue;
|
continue;
|
|
|
if (dump_file)
|
if (dump_file)
|
fprintf (dump_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
|
fprintf (dump_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
|
INSN_UID (insn));
|
INSN_UID (insn));
|
remove_note (insn, note);
|
remove_note (insn, note);
|
}
|
}
|
|
|
if (!ei_end_p (ei))
|
if (!ei_end_p (ei))
|
ei_next (&ei);
|
ei_next (&ei);
|
act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
|
act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
|
|
|
if (EDGE_COUNT (bb->succs) > 0)
|
if (EDGE_COUNT (bb->succs) > 0)
|
{
|
{
|
if (act)
|
if (act)
|
stack[sp++] = ei;
|
stack[sp++] = ei;
|
ei = ei_start (bb->succs);
|
ei = ei_start (bb->succs);
|
act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container (ei), 0) : NULL);
|
act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container (ei), 0) : NULL);
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
/* This routine will replace a store with a SET to a specified register. */
|
/* This routine will replace a store with a SET to a specified register. */
|
|
|
static void
|
static void
|
replace_store_insn (rtx reg, rtx del, basic_block bb, struct st_expr *smexpr)
|
replace_store_insn (rtx reg, rtx del, basic_block bb, struct st_expr *smexpr)
|
{
|
{
|
rtx insn, mem, note, set, ptr;
|
rtx insn, mem, note, set, ptr;
|
|
|
mem = smexpr->pattern;
|
mem = smexpr->pattern;
|
insn = gen_move_insn (reg, SET_SRC (single_set (del)));
|
insn = gen_move_insn (reg, SET_SRC (single_set (del)));
|
|
|
for (ptr = smexpr->antic_stores; ptr; ptr = XEXP (ptr, 1))
|
for (ptr = smexpr->antic_stores; ptr; ptr = XEXP (ptr, 1))
|
if (XEXP (ptr, 0) == del)
|
if (XEXP (ptr, 0) == del)
|
{
|
{
|
XEXP (ptr, 0) = insn;
|
XEXP (ptr, 0) = insn;
|
break;
|
break;
|
}
|
}
|
|
|
/* Move the notes from the deleted insn to its replacement. */
|
/* Move the notes from the deleted insn to its replacement. */
|
REG_NOTES (insn) = REG_NOTES (del);
|
REG_NOTES (insn) = REG_NOTES (del);
|
|
|
/* Emit the insn AFTER all the notes are transferred.
|
/* Emit the insn AFTER all the notes are transferred.
|
This is cheaper since we avoid df rescanning for the note change. */
|
This is cheaper since we avoid df rescanning for the note change. */
|
insn = emit_insn_after (insn, del);
|
insn = emit_insn_after (insn, del);
|
|
|
if (dump_file)
|
if (dump_file)
|
{
|
{
|
fprintf (dump_file,
|
fprintf (dump_file,
|
"STORE_MOTION delete insn in BB %d:\n ", bb->index);
|
"STORE_MOTION delete insn in BB %d:\n ", bb->index);
|
print_inline_rtx (dump_file, del, 6);
|
print_inline_rtx (dump_file, del, 6);
|
fprintf (dump_file, "\nSTORE_MOTION replaced with insn:\n ");
|
fprintf (dump_file, "\nSTORE_MOTION replaced with insn:\n ");
|
print_inline_rtx (dump_file, insn, 6);
|
print_inline_rtx (dump_file, insn, 6);
|
fprintf (dump_file, "\n");
|
fprintf (dump_file, "\n");
|
}
|
}
|
|
|
delete_insn (del);
|
delete_insn (del);
|
|
|
/* Now we must handle REG_EQUAL notes whose contents is equal to the mem;
|
/* Now we must handle REG_EQUAL notes whose contents is equal to the mem;
|
they are no longer accurate provided that they are reached by this
|
they are no longer accurate provided that they are reached by this
|
definition, so drop them. */
|
definition, so drop them. */
|
for (; insn != NEXT_INSN (BB_END (bb)); insn = NEXT_INSN (insn))
|
for (; insn != NEXT_INSN (BB_END (bb)); insn = NEXT_INSN (insn))
|
if (NONDEBUG_INSN_P (insn))
|
if (NONDEBUG_INSN_P (insn))
|
{
|
{
|
set = single_set (insn);
|
set = single_set (insn);
|
if (!set)
|
if (!set)
|
continue;
|
continue;
|
if (exp_equiv_p (SET_DEST (set), mem, 0, true))
|
if (exp_equiv_p (SET_DEST (set), mem, 0, true))
|
return;
|
return;
|
note = find_reg_equal_equiv_note (insn);
|
note = find_reg_equal_equiv_note (insn);
|
if (!note || !exp_equiv_p (XEXP (note, 0), mem, 0, true))
|
if (!note || !exp_equiv_p (XEXP (note, 0), mem, 0, true))
|
continue;
|
continue;
|
|
|
if (dump_file)
|
if (dump_file)
|
fprintf (dump_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
|
fprintf (dump_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
|
INSN_UID (insn));
|
INSN_UID (insn));
|
remove_note (insn, note);
|
remove_note (insn, note);
|
}
|
}
|
remove_reachable_equiv_notes (bb, smexpr);
|
remove_reachable_equiv_notes (bb, smexpr);
|
}
|
}
|
|
|
|
|
/* Delete a store, but copy the value that would have been stored into
|
/* Delete a store, but copy the value that would have been stored into
|
the reaching_reg for later storing. */
|
the reaching_reg for later storing. */
|
|
|
static void
|
static void
|
delete_store (struct st_expr * expr, basic_block bb)
|
delete_store (struct st_expr * expr, basic_block bb)
|
{
|
{
|
rtx reg, i, del;
|
rtx reg, i, del;
|
|
|
if (expr->reaching_reg == NULL_RTX)
|
if (expr->reaching_reg == NULL_RTX)
|
expr->reaching_reg = gen_reg_rtx_and_attrs (expr->pattern);
|
expr->reaching_reg = gen_reg_rtx_and_attrs (expr->pattern);
|
|
|
reg = expr->reaching_reg;
|
reg = expr->reaching_reg;
|
|
|
for (i = expr->avail_stores; i; i = XEXP (i, 1))
|
for (i = expr->avail_stores; i; i = XEXP (i, 1))
|
{
|
{
|
del = XEXP (i, 0);
|
del = XEXP (i, 0);
|
if (BLOCK_FOR_INSN (del) == bb)
|
if (BLOCK_FOR_INSN (del) == bb)
|
{
|
{
|
/* We know there is only one since we deleted redundant
|
/* We know there is only one since we deleted redundant
|
ones during the available computation. */
|
ones during the available computation. */
|
replace_store_insn (reg, del, bb, expr);
|
replace_store_insn (reg, del, bb, expr);
|
break;
|
break;
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
/* Fill in available, anticipatable, transparent and kill vectors in
|
/* Fill in available, anticipatable, transparent and kill vectors in
|
STORE_DATA, based on lists of available and anticipatable stores. */
|
STORE_DATA, based on lists of available and anticipatable stores. */
|
static void
|
static void
|
build_store_vectors (void)
|
build_store_vectors (void)
|
{
|
{
|
basic_block bb;
|
basic_block bb;
|
int *regs_set_in_block;
|
int *regs_set_in_block;
|
rtx insn, st;
|
rtx insn, st;
|
struct st_expr * ptr;
|
struct st_expr * ptr;
|
unsigned int max_gcse_regno = max_reg_num ();
|
unsigned int max_gcse_regno = max_reg_num ();
|
|
|
/* Build the gen_vector. This is any store in the table which is not killed
|
/* Build the gen_vector. This is any store in the table which is not killed
|
by aliasing later in its block. */
|
by aliasing later in its block. */
|
st_avloc = sbitmap_vector_alloc (last_basic_block, num_stores);
|
st_avloc = sbitmap_vector_alloc (last_basic_block, num_stores);
|
sbitmap_vector_zero (st_avloc, last_basic_block);
|
sbitmap_vector_zero (st_avloc, last_basic_block);
|
|
|
st_antloc = sbitmap_vector_alloc (last_basic_block, num_stores);
|
st_antloc = sbitmap_vector_alloc (last_basic_block, num_stores);
|
sbitmap_vector_zero (st_antloc, last_basic_block);
|
sbitmap_vector_zero (st_antloc, last_basic_block);
|
|
|
for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
|
for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
|
{
|
{
|
for (st = ptr->avail_stores; st != NULL; st = XEXP (st, 1))
|
for (st = ptr->avail_stores; st != NULL; st = XEXP (st, 1))
|
{
|
{
|
insn = XEXP (st, 0);
|
insn = XEXP (st, 0);
|
bb = BLOCK_FOR_INSN (insn);
|
bb = BLOCK_FOR_INSN (insn);
|
|
|
/* If we've already seen an available expression in this block,
|
/* If we've already seen an available expression in this block,
|
we can delete this one (It occurs earlier in the block). We'll
|
we can delete this one (It occurs earlier in the block). We'll
|
copy the SRC expression to an unused register in case there
|
copy the SRC expression to an unused register in case there
|
are any side effects. */
|
are any side effects. */
|
if (TEST_BIT (st_avloc[bb->index], ptr->index))
|
if (TEST_BIT (st_avloc[bb->index], ptr->index))
|
{
|
{
|
rtx r = gen_reg_rtx_and_attrs (ptr->pattern);
|
rtx r = gen_reg_rtx_and_attrs (ptr->pattern);
|
if (dump_file)
|
if (dump_file)
|
fprintf (dump_file, "Removing redundant store:\n");
|
fprintf (dump_file, "Removing redundant store:\n");
|
replace_store_insn (r, XEXP (st, 0), bb, ptr);
|
replace_store_insn (r, XEXP (st, 0), bb, ptr);
|
continue;
|
continue;
|
}
|
}
|
SET_BIT (st_avloc[bb->index], ptr->index);
|
SET_BIT (st_avloc[bb->index], ptr->index);
|
}
|
}
|
|
|
for (st = ptr->antic_stores; st != NULL; st = XEXP (st, 1))
|
for (st = ptr->antic_stores; st != NULL; st = XEXP (st, 1))
|
{
|
{
|
insn = XEXP (st, 0);
|
insn = XEXP (st, 0);
|
bb = BLOCK_FOR_INSN (insn);
|
bb = BLOCK_FOR_INSN (insn);
|
SET_BIT (st_antloc[bb->index], ptr->index);
|
SET_BIT (st_antloc[bb->index], ptr->index);
|
}
|
}
|
}
|
}
|
|
|
st_kill = sbitmap_vector_alloc (last_basic_block, num_stores);
|
st_kill = sbitmap_vector_alloc (last_basic_block, num_stores);
|
sbitmap_vector_zero (st_kill, last_basic_block);
|
sbitmap_vector_zero (st_kill, last_basic_block);
|
|
|
st_transp = sbitmap_vector_alloc (last_basic_block, num_stores);
|
st_transp = sbitmap_vector_alloc (last_basic_block, num_stores);
|
sbitmap_vector_zero (st_transp, last_basic_block);
|
sbitmap_vector_zero (st_transp, last_basic_block);
|
regs_set_in_block = XNEWVEC (int, max_gcse_regno);
|
regs_set_in_block = XNEWVEC (int, max_gcse_regno);
|
|
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
{
|
{
|
memset (regs_set_in_block, 0, sizeof (int) * max_gcse_regno);
|
memset (regs_set_in_block, 0, sizeof (int) * max_gcse_regno);
|
|
|
FOR_BB_INSNS (bb, insn)
|
FOR_BB_INSNS (bb, insn)
|
if (NONDEBUG_INSN_P (insn))
|
if (NONDEBUG_INSN_P (insn))
|
{
|
{
|
df_ref *def_rec;
|
df_ref *def_rec;
|
for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
|
for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
|
{
|
{
|
unsigned int ref_regno = DF_REF_REGNO (*def_rec);
|
unsigned int ref_regno = DF_REF_REGNO (*def_rec);
|
if (ref_regno < max_gcse_regno)
|
if (ref_regno < max_gcse_regno)
|
regs_set_in_block[DF_REF_REGNO (*def_rec)] = 1;
|
regs_set_in_block[DF_REF_REGNO (*def_rec)] = 1;
|
}
|
}
|
}
|
}
|
|
|
for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
|
for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
|
{
|
{
|
if (store_killed_after (ptr->pattern, ptr->pattern_regs, BB_HEAD (bb),
|
if (store_killed_after (ptr->pattern, ptr->pattern_regs, BB_HEAD (bb),
|
bb, regs_set_in_block, NULL))
|
bb, regs_set_in_block, NULL))
|
{
|
{
|
/* It should not be necessary to consider the expression
|
/* It should not be necessary to consider the expression
|
killed if it is both anticipatable and available. */
|
killed if it is both anticipatable and available. */
|
if (!TEST_BIT (st_antloc[bb->index], ptr->index)
|
if (!TEST_BIT (st_antloc[bb->index], ptr->index)
|
|| !TEST_BIT (st_avloc[bb->index], ptr->index))
|
|| !TEST_BIT (st_avloc[bb->index], ptr->index))
|
SET_BIT (st_kill[bb->index], ptr->index);
|
SET_BIT (st_kill[bb->index], ptr->index);
|
}
|
}
|
else
|
else
|
SET_BIT (st_transp[bb->index], ptr->index);
|
SET_BIT (st_transp[bb->index], ptr->index);
|
}
|
}
|
}
|
}
|
|
|
free (regs_set_in_block);
|
free (regs_set_in_block);
|
|
|
if (dump_file)
|
if (dump_file)
|
{
|
{
|
dump_sbitmap_vector (dump_file, "st_antloc", "", st_antloc, last_basic_block);
|
dump_sbitmap_vector (dump_file, "st_antloc", "", st_antloc, last_basic_block);
|
dump_sbitmap_vector (dump_file, "st_kill", "", st_kill, last_basic_block);
|
dump_sbitmap_vector (dump_file, "st_kill", "", st_kill, last_basic_block);
|
dump_sbitmap_vector (dump_file, "st_transp", "", st_transp, last_basic_block);
|
dump_sbitmap_vector (dump_file, "st_transp", "", st_transp, last_basic_block);
|
dump_sbitmap_vector (dump_file, "st_avloc", "", st_avloc, last_basic_block);
|
dump_sbitmap_vector (dump_file, "st_avloc", "", st_avloc, last_basic_block);
|
}
|
}
|
}
|
}
|
|
|
/* Free memory used by store motion. */
|
/* Free memory used by store motion. */
|
|
|
static void
|
static void
|
free_store_memory (void)
|
free_store_memory (void)
|
{
|
{
|
free_store_motion_mems ();
|
free_store_motion_mems ();
|
|
|
if (st_avloc)
|
if (st_avloc)
|
sbitmap_vector_free (st_avloc);
|
sbitmap_vector_free (st_avloc);
|
if (st_kill)
|
if (st_kill)
|
sbitmap_vector_free (st_kill);
|
sbitmap_vector_free (st_kill);
|
if (st_transp)
|
if (st_transp)
|
sbitmap_vector_free (st_transp);
|
sbitmap_vector_free (st_transp);
|
if (st_antloc)
|
if (st_antloc)
|
sbitmap_vector_free (st_antloc);
|
sbitmap_vector_free (st_antloc);
|
if (st_insert_map)
|
if (st_insert_map)
|
sbitmap_vector_free (st_insert_map);
|
sbitmap_vector_free (st_insert_map);
|
if (st_delete_map)
|
if (st_delete_map)
|
sbitmap_vector_free (st_delete_map);
|
sbitmap_vector_free (st_delete_map);
|
|
|
st_avloc = st_kill = st_transp = st_antloc = NULL;
|
st_avloc = st_kill = st_transp = st_antloc = NULL;
|
st_insert_map = st_delete_map = NULL;
|
st_insert_map = st_delete_map = NULL;
|
}
|
}
|
|
|
/* Perform store motion. Much like gcse, except we move expressions the
|
/* Perform store motion. Much like gcse, except we move expressions the
|
other way by looking at the flowgraph in reverse.
|
other way by looking at the flowgraph in reverse.
|
Return non-zero if transformations are performed by the pass. */
|
Return non-zero if transformations are performed by the pass. */
|
|
|
static int
|
static int
|
one_store_motion_pass (void)
|
one_store_motion_pass (void)
|
{
|
{
|
basic_block bb;
|
basic_block bb;
|
int x;
|
int x;
|
struct st_expr * ptr;
|
struct st_expr * ptr;
|
int did_edge_inserts = 0;
|
int did_edge_inserts = 0;
|
int n_stores_deleted = 0;
|
int n_stores_deleted = 0;
|
int n_stores_created = 0;
|
int n_stores_created = 0;
|
|
|
init_alias_analysis ();
|
init_alias_analysis ();
|
|
|
/* Find all the available and anticipatable stores. */
|
/* Find all the available and anticipatable stores. */
|
num_stores = compute_store_table ();
|
num_stores = compute_store_table ();
|
if (num_stores == 0)
|
if (num_stores == 0)
|
{
|
{
|
htab_delete (store_motion_mems_table);
|
htab_delete (store_motion_mems_table);
|
store_motion_mems_table = NULL;
|
store_motion_mems_table = NULL;
|
end_alias_analysis ();
|
end_alias_analysis ();
|
return 0;
|
return 0;
|
}
|
}
|
|
|
/* Now compute kill & transp vectors. */
|
/* Now compute kill & transp vectors. */
|
build_store_vectors ();
|
build_store_vectors ();
|
add_noreturn_fake_exit_edges ();
|
add_noreturn_fake_exit_edges ();
|
connect_infinite_loops_to_exit ();
|
connect_infinite_loops_to_exit ();
|
|
|
edge_list = pre_edge_rev_lcm (num_stores, st_transp, st_avloc,
|
edge_list = pre_edge_rev_lcm (num_stores, st_transp, st_avloc,
|
st_antloc, st_kill, &st_insert_map,
|
st_antloc, st_kill, &st_insert_map,
|
&st_delete_map);
|
&st_delete_map);
|
|
|
/* Now we want to insert the new stores which are going to be needed. */
|
/* Now we want to insert the new stores which are going to be needed. */
|
for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
|
for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
|
{
|
{
|
/* If any of the edges we have above are abnormal, we can't move this
|
/* If any of the edges we have above are abnormal, we can't move this
|
store. */
|
store. */
|
for (x = NUM_EDGES (edge_list) - 1; x >= 0; x--)
|
for (x = NUM_EDGES (edge_list) - 1; x >= 0; x--)
|
if (TEST_BIT (st_insert_map[x], ptr->index)
|
if (TEST_BIT (st_insert_map[x], ptr->index)
|
&& (INDEX_EDGE (edge_list, x)->flags & EDGE_ABNORMAL))
|
&& (INDEX_EDGE (edge_list, x)->flags & EDGE_ABNORMAL))
|
break;
|
break;
|
|
|
if (x >= 0)
|
if (x >= 0)
|
{
|
{
|
if (dump_file != NULL)
|
if (dump_file != NULL)
|
fprintf (dump_file,
|
fprintf (dump_file,
|
"Can't replace store %d: abnormal edge from %d to %d\n",
|
"Can't replace store %d: abnormal edge from %d to %d\n",
|
ptr->index, INDEX_EDGE (edge_list, x)->src->index,
|
ptr->index, INDEX_EDGE (edge_list, x)->src->index,
|
INDEX_EDGE (edge_list, x)->dest->index);
|
INDEX_EDGE (edge_list, x)->dest->index);
|
continue;
|
continue;
|
}
|
}
|
|
|
/* Now we want to insert the new stores which are going to be needed. */
|
/* Now we want to insert the new stores which are going to be needed. */
|
|
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
if (TEST_BIT (st_delete_map[bb->index], ptr->index))
|
if (TEST_BIT (st_delete_map[bb->index], ptr->index))
|
{
|
{
|
delete_store (ptr, bb);
|
delete_store (ptr, bb);
|
n_stores_deleted++;
|
n_stores_deleted++;
|
}
|
}
|
|
|
for (x = 0; x < NUM_EDGES (edge_list); x++)
|
for (x = 0; x < NUM_EDGES (edge_list); x++)
|
if (TEST_BIT (st_insert_map[x], ptr->index))
|
if (TEST_BIT (st_insert_map[x], ptr->index))
|
{
|
{
|
did_edge_inserts |= insert_store (ptr, INDEX_EDGE (edge_list, x));
|
did_edge_inserts |= insert_store (ptr, INDEX_EDGE (edge_list, x));
|
n_stores_created++;
|
n_stores_created++;
|
}
|
}
|
}
|
}
|
|
|
if (did_edge_inserts)
|
if (did_edge_inserts)
|
commit_edge_insertions ();
|
commit_edge_insertions ();
|
|
|
free_store_memory ();
|
free_store_memory ();
|
free_edge_list (edge_list);
|
free_edge_list (edge_list);
|
remove_fake_exit_edges ();
|
remove_fake_exit_edges ();
|
end_alias_analysis ();
|
end_alias_analysis ();
|
|
|
if (dump_file)
|
if (dump_file)
|
{
|
{
|
fprintf (dump_file, "STORE_MOTION of %s, %d basic blocks, ",
|
fprintf (dump_file, "STORE_MOTION of %s, %d basic blocks, ",
|
current_function_name (), n_basic_blocks);
|
current_function_name (), n_basic_blocks);
|
fprintf (dump_file, "%d insns deleted, %d insns created\n",
|
fprintf (dump_file, "%d insns deleted, %d insns created\n",
|
n_stores_deleted, n_stores_created);
|
n_stores_deleted, n_stores_created);
|
}
|
}
|
|
|
return (n_stores_deleted > 0 || n_stores_created > 0);
|
return (n_stores_deleted > 0 || n_stores_created > 0);
|
}
|
}
|
|
|
|
|
static bool
|
static bool
|
gate_rtl_store_motion (void)
|
gate_rtl_store_motion (void)
|
{
|
{
|
return optimize > 0 && flag_gcse_sm
|
return optimize > 0 && flag_gcse_sm
|
&& !cfun->calls_setjmp
|
&& !cfun->calls_setjmp
|
&& optimize_function_for_speed_p (cfun)
|
&& optimize_function_for_speed_p (cfun)
|
&& dbg_cnt (store_motion);
|
&& dbg_cnt (store_motion);
|
}
|
}
|
|
|
static unsigned int
|
static unsigned int
|
execute_rtl_store_motion (void)
|
execute_rtl_store_motion (void)
|
{
|
{
|
delete_unreachable_blocks ();
|
delete_unreachable_blocks ();
|
df_analyze ();
|
df_analyze ();
|
flag_rerun_cse_after_global_opts |= one_store_motion_pass ();
|
flag_rerun_cse_after_global_opts |= one_store_motion_pass ();
|
return 0;
|
return 0;
|
}
|
}
|
|
|
struct rtl_opt_pass pass_rtl_store_motion =
|
struct rtl_opt_pass pass_rtl_store_motion =
|
{
|
{
|
{
|
{
|
RTL_PASS,
|
RTL_PASS,
|
"store_motion", /* name */
|
"store_motion", /* name */
|
gate_rtl_store_motion, /* gate */
|
gate_rtl_store_motion, /* gate */
|
execute_rtl_store_motion, /* execute */
|
execute_rtl_store_motion, /* execute */
|
NULL, /* sub */
|
NULL, /* sub */
|
NULL, /* next */
|
NULL, /* next */
|
0, /* static_pass_number */
|
0, /* static_pass_number */
|
TV_LSM, /* tv_id */
|
TV_LSM, /* tv_id */
|
PROP_cfglayout, /* properties_required */
|
PROP_cfglayout, /* properties_required */
|
0, /* properties_provided */
|
0, /* properties_provided */
|
0, /* properties_destroyed */
|
0, /* properties_destroyed */
|
0, /* todo_flags_start */
|
0, /* todo_flags_start */
|
TODO_df_finish | TODO_verify_rtl_sharing |
|
TODO_df_finish | TODO_verify_rtl_sharing |
|
TODO_dump_func |
|
TODO_dump_func |
|
TODO_verify_flow | TODO_ggc_collect /* todo_flags_finish */
|
TODO_verify_flow | TODO_ggc_collect /* todo_flags_finish */
|
}
|
}
|
};
|
};
|
|
|
|
|