This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] for PR17133 and PR17790 (revised)
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Cc: dberlin at dberlin dot org
- Date: Wed, 20 Oct 2004 00:18:01 +0200
- Subject: [patch] for PR17133 and PR17790 (revised)
Hello,
this patch contains version of the previous patch for PR 17133 that
tries to fix some problems pointed out in the discussion by Daniel.
The patch now finds the alias classes by scanning the SSA form for
virtual operands. To fix the problem in PR 17133 (i.e. the fact
that output dependences are not represented in the SSA form),
the classes are then merged according to the basic variables of
the virtual ssa names (in merge_classes_with_same_tag).
Once the patch to record killed defs in V_MUST_DEFs is accepted,
this function can be simply removed.
Bootstrapped & regtested on i686, ia64 and ppc.
Zdenek
PR tree-optimization/17133
PR tree-optimization/17790
* tree-ssa-loop-im.c: Include hashtab.h.
(struct mem_ref): Describes all memory references with a given address
now.
(struct mem_ref_loc, struct alias_class): New.
(max_uid): Removed.
(movement_possibility): Do not move statements with VDEFS.
(record_mem_ref): Renamed to ...
(record_mem_ref_loc): ... this.
(free_mem_refs): Renamed to ...
(free_mem_ref_locs): ... this.
(maybe_queue_var, fem_single_reachable_address,
for_each_memref, single_reachable_address, is_call_clobbered_ref,
determine_lsm_reg): Removed.
(rewrite_mem_refs, schedule_sm): Work with struct mem_ref_loc.
(determine_lsm_ref, hoist_memory_reference,
gather_mem_refs_stmt_unknown, memref_eq, memref_del, memref_hash,
gather_mem_refs_stmt, gather_mem_refs, get_class_root,
merge_classes, class_for_ssa_name, merge_classes_on_phi,
count_class_references, merge_classes_with_same_tag_1,
merge_classes_with_same_tag, alias_class_hash, alias_class_eq): New
functions.
(determine_lsm, determine_lsm_loop): Reimplemented.
Index: tree-ssa-loop-im.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-im.c,v
retrieving revision 2.18
diff -c -3 -p -r2.18 tree-ssa-loop-im.c
*** tree-ssa-loop-im.c 29 Sep 2004 23:08:32 -0000 2.18
--- tree-ssa-loop-im.c 19 Oct 2004 15:39:57 -0000
*************** Software Foundation, 59 Temple Place - S
*** 37,42 ****
--- 37,43 ----
#include "params.h"
#include "tree-pass.h"
#include "flags.h"
+ #include "hashtab.h"
/* A type for the list of statements that have to be moved in order to be able
to hoist an invariant computation. */
*************** struct lim_aux_data
*** 80,115 ****
? NULL \
: (struct lim_aux_data *) (stmt_ann (STMT)->common.aux))
! /* Description of a memory reference for store motion. */
! struct mem_ref
{
tree *ref; /* The reference itself. */
tree stmt; /* The statement in that it occurs. */
! struct mem_ref *next; /* Next use in the chain. */
};
- /* Minimum cost of an expensive expression. */
- #define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE))
! /* The outermost loop for that execution of the header guarantees that the
! block will be executed. */
! #define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
! static unsigned max_stmt_uid; /* Maximal uid of a statement. Uids to phi
! nodes are assigned using the versions of
! ssa names they define. */
! /* Returns uid of statement STMT. */
! static unsigned
! get_stmt_uid (tree stmt)
{
! if (TREE_CODE (stmt) == PHI_NODE)
! return SSA_NAME_VERSION (PHI_RESULT (stmt)) + max_stmt_uid;
! return stmt_ann (stmt)->uid;
! }
/* Calls CBCK for each index in memory reference ADDR_P. There are two
kinds situations handled; in each of these cases, the memory reference
--- 81,134 ----
? NULL \
: (struct lim_aux_data *) (stmt_ann (STMT)->common.aux))
! /* Description of a memory reference location for store motion. */
! struct mem_ref_loc
{
tree *ref; /* The reference itself. */
tree stmt; /* The statement in that it occurs. */
! struct mem_ref_loc *next; /* Next use in the chain. */
};
! /* Description of class of memory references that alias. */
! struct alias_class
! {
! struct alias_class *father; /* Father field for disjoint find-union
! algorithm. */
! tree vname; /* Virtual operand for this alias class. */
! bool bad; /* The class is "bad" if it contains a memory
! reference on that store motion cannot be
! performed, or if it is killed due to other
! reasons (function call, asm statement,
! etc.) */
! unsigned mems_in_class; /* Number of different memory locations in this
! class. Store motion can only be performed
! if it is exactly one (i.e. all memory
! references in the class point to exactly the
! same location). */
! };
! /* Description of a memory reference for store motion. */
! struct mem_ref
{
! tree mem; /* The memory itself. */
! hashval_t hash; /* Its hash value. */
! bool is_stored; /* True if there is a store to the location
! in the loop. */
! struct mem_ref_loc *locs; /* The locations where it is found. */
! struct alias_class *class; /* The class representing alias information
! for the memory reference. */
! };
! /* Minimum cost of an expensive expression. */
! #define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE))
!
! /* The outermost loop for that execution of the header guarantees that the
! block will be executed. */
! #define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
/* Calls CBCK for each index in memory reference ADDR_P. There are two
kinds situations handled; in each of these cases, the memory reference
*************** movement_possibility (tree stmt)
*** 223,230 ****
if (TREE_SIDE_EFFECTS (rhs))
return MOVE_IMPOSSIBLE;
! if (TREE_CODE (lhs) != SSA_NAME
! || tree_could_trap_p (rhs))
return MOVE_PRESERVE_EXECUTION;
return MOVE_POSSIBLE;
--- 242,254 ----
if (TREE_SIDE_EFFECTS (rhs))
return MOVE_IMPOSSIBLE;
! /* Due to V_MUST_DEFS the ssa form for virtual uses no longer describes
! output dependence relation, so avoid moving out statements
! with VDEFS. */
! if (TREE_CODE (lhs) != SSA_NAME)
! return MOVE_IMPOSSIBLE;
!
! if (tree_could_trap_p (rhs))
return MOVE_PRESERVE_EXECUTION;
return MOVE_POSSIBLE;
*************** force_move_till (tree ref, tree *index,
*** 787,799 ****
return true;
}
! /* Records memory reference *REF (that occurs in statement STMT)
! to the list MEM_REFS. */
static void
! record_mem_ref (struct mem_ref **mem_refs, tree stmt, tree *ref)
{
! struct mem_ref *aref = xmalloc (sizeof (struct mem_ref));
aref->stmt = stmt;
aref->ref = ref;
--- 811,823 ----
return true;
}
! /* Records memory reference location *REF to the list MEM_REFS. The reference
! occurs in statement STMT. */
static void
! record_mem_ref_loc (struct mem_ref_loc **mem_refs, tree stmt, tree *ref)
{
! struct mem_ref_loc *aref = xmalloc (sizeof (struct mem_ref_loc));
aref->stmt = stmt;
aref->ref = ref;
*************** record_mem_ref (struct mem_ref **mem_ref
*** 802,813 ****
*mem_refs = aref;
}
! /* Releases list of memory references MEM_REFS. */
static void
! free_mem_refs (struct mem_ref *mem_refs)
{
! struct mem_ref *act;
while (mem_refs)
{
--- 826,837 ----
*mem_refs = aref;
}
! /* Releases list of memory reference locations MEM_REFS. */
static void
! free_mem_ref_locs (struct mem_ref_loc *mem_refs)
{
! struct mem_ref_loc *act;
while (mem_refs)
{
*************** free_mem_refs (struct mem_ref *mem_refs)
*** 817,1033 ****
}
}
- /* If VAR is defined in LOOP and the statement it is defined in does not belong
- to the set SEEN, add the statement to QUEUE of length IN_QUEUE and
- to the set SEEN. */
-
- static void
- maybe_queue_var (tree var, struct loop *loop,
- sbitmap seen, tree *queue, unsigned *in_queue)
- {
- tree stmt = SSA_NAME_DEF_STMT (var);
- basic_block def_bb = bb_for_stmt (stmt);
-
- if (!def_bb
- || !flow_bb_inside_loop_p (loop, def_bb)
- || TEST_BIT (seen, get_stmt_uid (stmt)))
- return;
-
- SET_BIT (seen, get_stmt_uid (stmt));
- queue[(*in_queue)++] = stmt;
- }
-
- /* If COMMON_REF is NULL, set COMMON_REF to *OP and return true.
- Otherwise return true if the memory reference *OP is equal to COMMON_REF.
- Record the reference OP to list MEM_REFS. STMT is the statement in that
- the reference occurs. */
-
- struct sra_data
- {
- struct mem_ref **mem_refs;
- tree common_ref;
- tree stmt;
- };
-
- static bool
- fem_single_reachable_address (tree *op, void *data)
- {
- struct sra_data *sra_data = data;
-
- if (sra_data->common_ref
- && !operand_equal_p (*op, sra_data->common_ref, 0))
- return false;
- sra_data->common_ref = *op;
-
- record_mem_ref (sra_data->mem_refs, sra_data->stmt, op);
- return true;
- }
-
- /* Runs CALLBACK for each operand of STMT that is a memory reference. DATA
- is passed to the CALLBACK as well. The traversal stops if CALLBACK
- returns false, for_each_memref then returns false as well. Otherwise
- for_each_memref returns true. */
-
- static bool
- for_each_memref (tree stmt, bool (*callback)(tree *, void *), void *data)
- {
- tree *op;
-
- if (TREE_CODE (stmt) == RETURN_EXPR)
- stmt = TREE_OPERAND (stmt, 1);
-
- if (TREE_CODE (stmt) == MODIFY_EXPR)
- {
- op = &TREE_OPERAND (stmt, 0);
- if (TREE_CODE (*op) != SSA_NAME
- && !callback (op, data))
- return false;
-
- op = &TREE_OPERAND (stmt, 1);
- if (TREE_CODE (*op) != SSA_NAME
- && is_gimple_lvalue (*op)
- && !callback (op, data))
- return false;
-
- stmt = TREE_OPERAND (stmt, 1);
- }
-
- if (TREE_CODE (stmt) == WITH_SIZE_EXPR)
- stmt = TREE_OPERAND (stmt, 0);
-
- if (TREE_CODE (stmt) == CALL_EXPR)
- {
- tree args;
-
- for (args = TREE_OPERAND (stmt, 1); args; args = TREE_CHAIN (args))
- {
- op = &TREE_VALUE (args);
-
- if (TREE_CODE (*op) != SSA_NAME
- && is_gimple_lvalue (*op)
- && !callback (op, data))
- return false;
- }
- }
-
- return true;
- }
-
- /* Determine whether all memory references inside the LOOP that correspond
- to virtual ssa names defined in statement STMT are equal.
- If so, store the list of the references to MEM_REFS, and return one
- of them. Otherwise store NULL to MEM_REFS and return NULL_TREE.
- *SEEN_CALL_STMT is set to true if the virtual operands suggest
- that the reference might be clobbered by a call inside the LOOP. */
-
- static tree
- single_reachable_address (struct loop *loop, tree stmt,
- struct mem_ref **mem_refs,
- bool *seen_call_stmt)
- {
- unsigned max_uid = max_stmt_uid + num_ssa_names;
- tree *queue = xmalloc (sizeof (tree) * max_uid);
- sbitmap seen = sbitmap_alloc (max_uid);
- unsigned in_queue = 1;
- dataflow_t df;
- unsigned i, n;
- struct sra_data sra_data;
- tree call;
- tree val;
- ssa_op_iter iter;
-
- sbitmap_zero (seen);
-
- *mem_refs = NULL;
- sra_data.mem_refs = mem_refs;
- sra_data.common_ref = NULL_TREE;
-
- queue[0] = stmt;
- SET_BIT (seen, get_stmt_uid (stmt));
- *seen_call_stmt = false;
-
- while (in_queue)
- {
- stmt = queue[--in_queue];
- sra_data.stmt = stmt;
-
- if (LIM_DATA (stmt)
- && LIM_DATA (stmt)->sm_done)
- goto fail;
-
- switch (TREE_CODE (stmt))
- {
- case MODIFY_EXPR:
- case CALL_EXPR:
- case RETURN_EXPR:
- if (!for_each_memref (stmt, fem_single_reachable_address,
- &sra_data))
- goto fail;
-
- /* If this is a function that may depend on the memory location,
- record the fact. We cannot directly refuse call clobbered
- operands here, since sra_data.common_ref did not have
- to be set yet. */
- call = get_call_expr_in (stmt);
- if (call
- && !(call_expr_flags (call) & ECF_CONST))
- *seen_call_stmt = true;
-
- /* Traverse also definitions of the VUSES (there may be other
- distinct from the one we used to get to this statement). */
- FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_VIRTUAL_USES)
- maybe_queue_var (val, loop, seen, queue, &in_queue);
-
- break;
-
- case PHI_NODE:
- for (i = 0; i < (unsigned) PHI_NUM_ARGS (stmt); i++)
- if (TREE_CODE (PHI_ARG_DEF (stmt, i)) == SSA_NAME)
- maybe_queue_var (PHI_ARG_DEF (stmt, i), loop,
- seen, queue, &in_queue);
- break;
-
- default:
- goto fail;
- }
-
- /* Find uses of virtual names. */
- df = get_immediate_uses (stmt);
- n = num_immediate_uses (df);
-
- for (i = 0; i < n; i++)
- {
- stmt = immediate_use (df, i);
-
- if (!flow_bb_inside_loop_p (loop, bb_for_stmt (stmt)))
- continue;
-
- if (TEST_BIT (seen, get_stmt_uid (stmt)))
- continue;
- SET_BIT (seen, get_stmt_uid (stmt));
-
- queue[in_queue++] = stmt;
- }
- }
-
- free (queue);
- sbitmap_free (seen);
-
- return sra_data.common_ref;
-
- fail:
- free_mem_refs (*mem_refs);
- *mem_refs = NULL;
- free (queue);
- sbitmap_free (seen);
-
- return NULL;
- }
-
/* Rewrites memory references in list MEM_REFS by variable TMP_VAR. */
static void
! rewrite_mem_refs (tree tmp_var, struct mem_ref *mem_refs)
{
tree var;
ssa_op_iter iter;
--- 841,850 ----
}
}
/* Rewrites memory references in list MEM_REFS by variable TMP_VAR. */
static void
! rewrite_mem_refs (tree tmp_var, struct mem_ref_loc *mem_refs)
{
tree var;
ssa_op_iter iter;
*************** rewrite_mem_refs (tree tmp_var, struct m
*** 1056,1064 ****
static void
schedule_sm (struct loop *loop, edge *exits, unsigned n_exits, tree ref,
! struct mem_ref *mem_refs)
{
! struct mem_ref *aref;
tree tmp_var;
unsigned i;
tree load, store;
--- 873,881 ----
static void
schedule_sm (struct loop *loop, edge *exits, unsigned n_exits, tree ref,
! struct mem_ref_loc *mem_refs)
{
! struct mem_ref_loc *aref;
tree tmp_var;
unsigned i;
tree load, store;
*************** schedule_sm (struct loop *loop, edge *ex
*** 1100,1176 ****
}
}
! /* Returns true if REF may be clobbered by calls. */
! static bool
! is_call_clobbered_ref (tree ref)
{
! tree base;
!
! base = get_base_address (ref);
! if (!base)
! return true;
! if (DECL_P (base))
! return is_call_clobbered (base);
! if (INDIRECT_REF_P (base))
{
! /* Check whether the alias tags associated with the pointer
! are call clobbered. */
! tree ptr = TREE_OPERAND (base, 0);
! struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
! tree nmt = (pi) ? pi->name_mem_tag : NULL_TREE;
! tree tmt = var_ann (SSA_NAME_VAR (ptr))->type_mem_tag;
!
! if ((nmt && is_call_clobbered (nmt))
! || (tmt && is_call_clobbered (tmt)))
! return true;
!
! return false;
}
! gcc_unreachable ();
}
! /* Determine whether all memory references inside LOOP corresponding to the
! virtual ssa name REG are equal to each other, and whether the address of
! this common reference can be hoisted outside of the loop. If this is true,
! prepare the statements that load the value of the memory reference to a
! temporary variable in the loop preheader, store it back on the loop exits,
! and replace all the references inside LOOP by this temporary variable.
LOOP has N_EXITS stored in EXITS. */
static void
! determine_lsm_reg (struct loop *loop, edge *exits, unsigned n_exits, tree reg)
{
! tree ref;
! struct mem_ref *mem_refs, *aref;
struct loop *must_exec;
! bool sees_call;
!
! if (is_gimple_reg (reg))
! return;
!
! ref = single_reachable_address (loop, SSA_NAME_DEF_STMT (reg), &mem_refs,
! &sees_call);
! if (!ref)
return;
! /* If we cannot create a ssa name for the result, give up. */
! if (!is_gimple_reg_type (TREE_TYPE (ref))
! || TREE_THIS_VOLATILE (ref))
! goto fail;
!
! /* If there is a call that may use the location, give up as well. */
! if (sees_call
! && is_call_clobbered_ref (ref))
! goto fail;
! if (!for_each_index (&ref, may_move_till, loop))
! goto fail;
! if (tree_could_trap_p (ref))
{
/* If the memory access is unsafe (i.e. it might trap), ensure that some
of the statements in that it occurs is always executed when the loop
--- 917,1016 ----
}
}
! /* Returns the representant of the alias class CLASS (root of the disjoint
! find-union representation. */
! static struct alias_class *
! get_class_root (struct alias_class *class)
{
! struct alias_class *acl, *next, *ret;
! for (ret = class; ret->father; ret = ret->father)
! continue;
! /* Path shortening. */
! for (acl = class; acl->father; acl = next)
{
! next = acl->father;
! acl->father = ret;
}
! return ret;
}
! /* Merge two alias classes CL1 and CL2 and returns the new root of their common
! alias class. */
!
! static struct alias_class *
! merge_classes (struct alias_class *cl1, struct alias_class *cl2)
! {
! gcc_assert (cl2->father == NULL);
!
! if (!cl1)
! return cl2;
! if (cl1 == cl2)
! return cl1;
!
! gcc_assert (cl1->father == NULL);
!
! /* For alpha(n) complexity, we should make the larger class root. We do not
! do this, since gains are negligible in practice anyway. */
! cl2->father = cl1;
! cl1->bad |= cl2->bad;
!
! return cl1;
! }
!
! /* Return an alias class from CLASSES for ssa name NAME. */
!
! static struct alias_class *
! class_for_ssa_name (htab_t classes, tree name)
! {
! struct alias_class *class;
! PTR *slot = htab_find_slot_with_hash (classes, name, SSA_NAME_VERSION (name),
! INSERT);
!
! if (*slot)
! return get_class_root (*slot);
!
! class = xmalloc (sizeof (struct alias_class));
! class->father = NULL;
! class->vname = name;
! class->bad = false;
! class->mems_in_class = 0;
!
! *slot = class;
! return class;
! }
!
! /* Check whether memory reference REF can be hoisted out of the LOOP. If this
! is true, prepare the statements that load the value of the memory reference
! to a temporary variable in the loop preheader, store it back on the loop
! exits, and replace all the references inside LOOP by this temporary variable.
LOOP has N_EXITS stored in EXITS. */
static void
! determine_lsm_ref (struct loop *loop, edge *exits, unsigned n_exits,
! struct mem_ref *ref)
{
! struct mem_ref_loc *aref;
struct loop *must_exec;
! struct alias_class *class;
!
! /* In case the memory is not stored to, there is nothing for SM to do. */
! if (!ref->is_stored)
return;
! /* If the reference is aliased with any different ref, or killed by call
! in function, then fail. */
! class = get_class_root (ref->class);
! gcc_assert (class->mems_in_class > 0);
! if (class->mems_in_class != 1
! || class->bad)
! return;
! if (tree_could_trap_p (ref->mem))
{
/* If the memory access is unsafe (i.e. it might trap), ensure that some
of the statements in that it occurs is always executed when the loop
*************** determine_lsm_reg (struct loop *loop, ed
*** 1183,1189 ****
least one of the statements containing the memory reference is
executed. */
! for (aref = mem_refs; aref; aref = aref->next)
{
if (!LIM_DATA (aref->stmt))
continue;
--- 1023,1029 ----
least one of the statements containing the memory reference is
executed. */
! for (aref = ref->locs; aref; aref = aref->next)
{
if (!LIM_DATA (aref->stmt))
continue;
*************** determine_lsm_reg (struct loop *loop, ed
*** 1198,1210 ****
}
if (!aref)
! goto fail;
}
! schedule_sm (loop, exits, n_exits, ref, mem_refs);
! fail: ;
! free_mem_refs (mem_refs);
}
/* Checks whether LOOP (with N_EXITS exits stored in EXITS array) is suitable
--- 1038,1068 ----
}
if (!aref)
! return;
}
! schedule_sm (loop, exits, n_exits, ref->mem, ref->locs);
! }
!
! /* Attempts to hoist memory reference described in SLOT out of loop
! described in DATA. Callback for htab_traverse. */
!
! struct hmr_data
! {
! struct loop *loop; /* Loop from that the reference should be hoisted. */
! edge *exits; /* Exits of the loop. */
! unsigned n_exits; /* Length of the exits array. */
! };
!
! static int
! hoist_memory_reference (void **slot, void *data)
! {
! struct mem_ref *ref = *slot;
! struct hmr_data *hmr_data = data;
!
! determine_lsm_ref (hmr_data->loop, hmr_data->exits, hmr_data->n_exits, ref);
! return 1;
}
/* Checks whether LOOP (with N_EXITS exits stored in EXITS array) is suitable
*************** loop_suitable_for_sm (struct loop *loop
*** 1224,1238 ****
return true;
}
/* Try to perform store motion for all memory references modified inside
LOOP. */
static void
determine_lsm_loop (struct loop *loop)
{
- tree phi;
unsigned n_exits;
edge *exits = get_loop_exit_edges (loop, &n_exits);
if (!loop_suitable_for_sm (loop, exits, n_exits))
{
--- 1082,1341 ----
return true;
}
+ /* A hash function for struct mem_ref object OBJ. */
+
+ static hashval_t
+ memref_hash (const void *obj)
+ {
+ const struct mem_ref *mem = obj;
+
+ return mem->hash;
+ }
+
+ /* An equality function for struct mem_ref object OBJ1 with
+ memory reference OBJ2. */
+
+ static int
+ memref_eq (const void *obj1, const void *obj2)
+ {
+ const struct mem_ref *mem1 = obj1;
+
+ return operand_equal_p (mem1->mem, (tree) obj2, 0);
+ }
+
+ /* A function to free the struct mem_ref object OBJ. */
+
+ static void
+ memref_del (void *obj)
+ {
+ struct mem_ref *mem = obj;
+
+ free_mem_ref_locs (mem->locs);
+ free (mem);
+ }
+
+ /* Gathers memory references in statement STMT in LOOP, storing the
+ information about them in MEM_REFS hash table. Record the information
+ about alias classes to CLASSES. */
+
+ static void
+ gather_mem_refs_stmt (struct loop *loop, htab_t mem_refs, htab_t classes,
+ tree stmt)
+ {
+ tree *lhs, *rhs, *mem;
+ hashval_t hash;
+ PTR *slot;
+ struct mem_ref *ref = NULL;
+ ssa_op_iter oi;
+ tree vname;
+ bool is_stored;
+ struct alias_class *class = NULL, *aclass;
+
+ get_stmt_operands (stmt);
+
+ if (!STMT_V_MAY_DEF_OPS (stmt)
+ && !STMT_V_MUST_DEF_OPS (stmt)
+ && !STMT_VUSE_OPS (stmt))
+ return;
+
+ /* Recognize MEM = (SSA_NAME | invariant) and SSA_NAME = MEM patterns. */
+ if (TREE_CODE (stmt) != MODIFY_EXPR)
+ goto record_alias;
+
+ lhs = &TREE_OPERAND (stmt, 0);
+ rhs = &TREE_OPERAND (stmt, 1);
+
+ if (TREE_CODE (*lhs) == SSA_NAME)
+ {
+ if (!is_gimple_addressable (*rhs))
+ goto record_alias;
+
+ mem = rhs;
+ is_stored = false;
+ }
+ else if (TREE_CODE (*rhs) == SSA_NAME
+ || is_gimple_min_invariant (*rhs))
+ {
+ mem = lhs;
+ is_stored = true;
+ }
+ else
+ goto record_alias;
+
+ /* If we cannot create a ssa name for the result, give up. */
+ if (!is_gimple_reg_type (TREE_TYPE (*mem))
+ || TREE_THIS_VOLATILE (*mem))
+ goto record_alias;
+
+ /* If we cannot move the reference from the loop, fail. */
+ if (!for_each_index (mem, may_move_till, loop))
+ goto record_alias;
+
+ hash = iterative_hash_expr (*mem, 0);
+ slot = htab_find_slot_with_hash (mem_refs, *mem, hash, INSERT);
+
+ if (*slot)
+ {
+ ref = *slot;
+ class = get_class_root (ref->class);
+ }
+ else
+ {
+ ref = xmalloc (sizeof (struct mem_ref));
+ ref->mem = *mem;
+ ref->hash = hash;
+ ref->locs = NULL;
+ ref->is_stored = false;
+ ref->class = NULL;
+ *slot = ref;
+ }
+ ref->is_stored |= is_stored;
+
+ record_mem_ref_loc (&ref->locs, stmt, mem);
+
+ record_alias:
+ FOR_EACH_SSA_TREE_OPERAND (vname, stmt, oi,
+ (SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_DEFS))
+ {
+ aclass = class_for_ssa_name (classes, vname);
+ class = merge_classes (class, aclass);
+ }
+
+ gcc_assert (class != NULL);
+
+ if (ref)
+ ref->class = class;
+ else
+ class->bad = true;
+ }
+
+ /* Merge alias CLASSES according to phi node PHI. Ignore argument from
+ edge ENTRY (entry edge of the loop). */
+
+ static void
+ merge_classes_on_phi (htab_t classes, tree phi, edge entry)
+ {
+ unsigned i;
+ tree vname;
+ struct alias_class *class, *aclass;
+
+ vname = PHI_RESULT (phi);
+ if (is_gimple_reg (vname))
+ return;
+ class = class_for_ssa_name (classes, vname);
+
+ for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
+ {
+ /* Ignore entry edge of the loop. */
+ if (PHI_ARG_EDGE (phi, i) == entry)
+ continue;
+
+ vname = PHI_ARG_DEF (phi, i);
+ gcc_assert (TREE_CODE (vname) == SSA_NAME);
+
+ aclass = class_for_ssa_name (classes, vname);
+ class = merge_classes (class, aclass);
+ }
+ }
+
+ /* Gathers memory references in LOOP, storing the information about them
+ in MEM_REFS hash table. Information about aliassing is stored to
+ CLASSES. */
+
+ static void
+ gather_mem_refs (struct loop *loop, htab_t mem_refs, htab_t classes)
+ {
+ basic_block *body = get_loop_body (loop);
+ block_stmt_iterator bsi;
+ unsigned i;
+ tree phi;
+ edge entry = loop_preheader_edge (loop);
+
+ for (i = 0; i < loop->num_nodes; i++)
+ {
+ for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi))
+ gather_mem_refs_stmt (loop, mem_refs, classes, bsi_stmt (bsi));
+
+ /* Merge the alias classes on phi nodes. */
+ for (phi = phi_nodes (body[i]); phi; phi = PHI_CHAIN (phi))
+ merge_classes_on_phi (classes, phi, entry);
+ }
+
+ free (body);
+ }
+
+ /* Increases number of references for alias class associated with
+ reference passed in SLOT. Callback for htab_traverse. */
+
+ static int
+ count_class_references (void **slot, void *data ATTRIBUTE_UNUSED)
+ {
+ struct mem_ref *ref = *slot;
+ struct alias_class *class = get_class_root (ref->class);
+
+ class->mems_in_class++;
+
+ return 1;
+ }
+
+ /* Merge class passed in *SLOT with other classes with the same basic
+ variable, using the array passed in DATA. Callback for htab_traverse. */
+
+ static int
+ merge_classes_with_same_tag_1 (void **slot, void *data)
+ {
+ struct alias_class *class = *slot;
+ struct alias_class **class_for_tag = data;
+ unsigned id = var_ann (SSA_NAME_VAR (class->vname))->uid;
+
+ class = get_class_root (class);
+ class_for_tag[id] = merge_classes (class_for_tag[id], class);
+ return 1;
+ }
+
+ /* Merge CLASSES with the same tag. */
+
+ static void
+ merge_classes_with_same_tag (htab_t classes)
+ {
+ struct alias_class **class_for_tag = xcalloc (num_referenced_vars,
+ sizeof (struct alias_class *));
+
+ htab_traverse (classes, merge_classes_with_same_tag_1, class_for_tag);
+ free (class_for_tag);
+ }
+
+ /* A hash function for struct alias_class object OBJ. */
+
+ static hashval_t
+ alias_class_hash (const void *obj)
+ {
+ const struct alias_class *class = obj;
+
+ return SSA_NAME_VERSION (class->vname);
+ }
+
+ /* An equality function for struct alias_class object OBJ1 with
+ ssa name OBJ2. */
+
+ static int
+ alias_class_eq (const void *obj1, const void *obj2)
+ {
+ const struct alias_class *class = obj1;
+
+ return class->vname == obj2;
+ }
+
/* Try to perform store motion for all memory references modified inside
LOOP. */
static void
determine_lsm_loop (struct loop *loop)
{
unsigned n_exits;
edge *exits = get_loop_exit_edges (loop, &n_exits);
+ htab_t mem_refs, classes;
+ struct hmr_data hmr_data;
if (!loop_suitable_for_sm (loop, exits, n_exits))
{
*************** determine_lsm_loop (struct loop *loop)
*** 1240,1248 ****
return;
}
! for (phi = phi_nodes (loop->header); phi; phi = TREE_CHAIN (phi))
! determine_lsm_reg (loop, exits, n_exits, PHI_RESULT (phi));
free (exits);
}
--- 1343,1370 ----
return;
}
! mem_refs = htab_create (100, memref_hash, memref_eq, memref_del);
+ /* Find the memory references in LOOP. */
+ classes = htab_create (100, alias_class_hash, alias_class_eq, free);
+ gather_mem_refs (loop, mem_refs, classes);
+
+ /* Merge the classes that correspond to the same tag (TODO -- once ssa form
+ for virtual operands again contains the information about output
+ dependences, this step should be removed). */
+ merge_classes_with_same_tag (classes);
+
+ /* Count the number of references for each memory aliasing class. */
+ htab_traverse (mem_refs, count_class_references, NULL);
+
+ /* Hoist all suitable memory references. */
+ hmr_data.loop = loop;
+ hmr_data.exits = exits;
+ hmr_data.n_exits = n_exits;
+ htab_traverse (mem_refs, hoist_memory_reference, &hmr_data);
+
+ htab_delete (mem_refs);
+ htab_delete (classes);
free (exits);
}
*************** static void
*** 1253,1276 ****
determine_lsm (struct loops *loops)
{
struct loop *loop;
- basic_block bb;
-
- /* Create a UID for each statement in the function. Ordering of the
- UIDs is not important for this pass. */
- max_stmt_uid = 0;
- FOR_EACH_BB (bb)
- {
- block_stmt_iterator bsi;
-
- for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
- stmt_ann (bsi_stmt (bsi))->uid = max_stmt_uid++;
- }
-
- compute_immediate_uses (TDFA_USE_VOPS, NULL);
! /* Pass the loops from the outermost. For each virtual operand loop phi node
! check whether all the references inside the loop correspond to a single
! address, and if so, move them. */
loop = loops->tree_root->inner;
while (1)
--- 1375,1383 ----
determine_lsm (struct loops *loops)
{
struct loop *loop;
! /* Pass the loops from the outermost and perform the store motion as
! suitable. */
loop = loops->tree_root->inner;
while (1)
*************** determine_lsm (struct loops *loops)
*** 1287,1293 ****
loop = loop->outer;
if (loop == loops->tree_root)
{
- free_df ();
loop_commit_inserts ();
return;
}
--- 1394,1399 ----