This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[patch] for PR 17790 (updated)


Hello,

here is the updated version of the patch for this PR (performace
problems of loop store motion, originally submitted as
http://gcc.gnu.org/ml/gcc-patches/2004-10/msg01642.html).
The main change in this version is that the hack to fix the
problems of PR17133 -- merge_classes_with_same_tag -- is removed.

Bootstrapped & regtested on i686 and ppc.

Zdenek

	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): New
	functions.
	(determine_lsm, determine_lsm_loop): Reimplemented.
	* tree-ssa-loop-ivopts.c (tree_ssa_iv_optimize_loop): Do not call
	loop_commit_inserts.

Index: tree-ssa-loop-im.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-im.c,v
retrieving revision 2.27
diff -c -3 -p -r2.27 tree-ssa-loop-im.c
*** tree-ssa-loop-im.c	20 Jan 2005 12:45:13 -0000	2.27
--- tree-ssa-loop-im.c	6 Feb 2005 15:45:09 -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,141 ----
  			? 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.  */
!   unsigned order;		/* Size of the class for the disjoint find-union
! 				   algorithm.  */
!   unsigned loop_num;		/* The number of the loop in that the
! 				   information for the alias class is valid.
! 				   To save time, we do not clear the
! 				   information after the loop is processed,
! 				   and invalid elements are detected using
! 				   this field.  */
!   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
*************** force_move_till (tree ref, tree *index, 
*** 785,797 ****
    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
*** 800,811 ****
    *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)
*** 815,1031 ****
      }
  }
  
- /* 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
*** 1053,1061 ****
  
  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;
--- 872,880 ----
  
  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
*** 1097,1173 ****
      }
  }
  
! /* 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
--- 916,1025 ----
      }
  }
  
! /* 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);
! 
!   if (cl1->order > cl2->order)
!     {
!       cl2->father = cl1;
!       cl1->bad |= cl2->bad;
!       cl1->order += cl2->order;
!       cl1->mems_in_class += cl2->mems_in_class;
!       return cl1;
      }
+   else
+     {
+       cl1->father = cl2;
+       cl2->bad |= cl1->bad;
+       cl2->order += cl1->order;
+       cl2->mems_in_class += cl1->mems_in_class;
+       return cl2;
+     }
+ }
+ 
+ /* Return an alias class from CLASSES for ssa name NAME.  LOOP_NUM is the
+    number of the current loop -- its number is used as a marker for valid
+    fields in CLASSES (the array CLASSES is never cleared).  */
+ 
+ static struct alias_class *
+ class_for_ssa_name (struct alias_class *classes, tree name, unsigned loop_num)
+ {
+   struct alias_class *class = classes + SSA_NAME_VERSION (name);
+ 
+   if (class->loop_num == loop_num)
+     return get_class_root (class);
+ 
+   /* Initialize a new class.  */
+   class->loop_num = loop_num;
+   class->order = 1;
+   class->father = NULL;
+   class->bad = false;
+   class->mems_in_class = 0;
  
!   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
*** 1180,1186 ****
  	 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;
--- 1032,1038 ----
  	 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
*** 1195,1207 ****
  	}
  
        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
--- 1047,1077 ----
  	}
  
        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 
*** 1221,1235 ****
    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))
      {
--- 1091,1303 ----
    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,
! 		      struct alias_class *classes, tree stmt)
  {
+   tree *lhs, *rhs, *mem = NULL;
+   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;
+   unsigned loop_num = loop->num;
+   bool new_ref_p = false;
+ 
+   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);
+       gcc_assert (class->mems_in_class >= 1);
+     }
+   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;
+       new_ref_p = true;
+     }
+   ref->is_stored |= is_stored;
+ 
+ record_alias:
+   FOR_EACH_SSA_TREE_OPERAND (vname, stmt, oi, SSA_OP_ALL_VIRTUALS)
+     {
+       aclass = class_for_ssa_name (classes, vname, loop_num);
+       class = merge_classes (class, aclass);
+     }
+ 
+   gcc_assert (class != NULL);
+ 
+   if (ref)
+     {
+       ref->class = class;
+       if (new_ref_p)
+ 	class->mems_in_class++;
+ 
+       /* Do not waste memory on recording locations of memory references
+ 	 that cannot be moved.  */
+       if (!class->bad
+ 	  && class->mems_in_class == 1)
+ 	record_mem_ref_loc (&ref->locs, stmt, mem);
+     }
+   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 (struct alias_class *classes, tree phi, edge entry,
+ 		      struct loop *loop)
+ {
+   unsigned i;
+   tree vname;
+   struct alias_class *class, *aclass;
+   unsigned loop_num = loop->num;
+ 
+   vname = PHI_RESULT (phi);
+   if (is_gimple_reg (vname))
+     return;
+   class = class_for_ssa_name (classes, vname, loop_num);
+ 
+   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, loop_num);
+       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,
+ 		 struct alias_class *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++)
+     {
+       /* 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, loop);
+ 
+       for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi))
+ 	gather_mem_refs_stmt (loop, mem_refs, classes, bsi_stmt (bsi));
+     }
+ 
+   free (body);
+ }
+ 
+ /* Try to perform store motion for all memory references modified inside
+    LOOP.  CLASSES is the array used to store information about alias
+    classes.  */
+ 
+ static void
+ determine_lsm_loop (struct loop *loop, struct alias_class *classes)
+ {
    unsigned n_exits;
    edge *exits = get_loop_exit_edges (loop, &n_exits);
+   htab_t mem_refs;
+   struct hmr_data hmr_data;
  
    if (!loop_suitable_for_sm (loop, exits, n_exits))
      {
*************** determine_lsm_loop (struct loop *loop)
*** 1237,1245 ****
        return;
      }
  
!   for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
!     determine_lsm_reg (loop, exits, n_exits, PHI_RESULT (phi));
  
    free (exits);
  }
  
--- 1305,1322 ----
        return;
      }
  
!   mem_refs = htab_create (100, memref_hash, memref_eq, memref_del);
  
+   /* Find the memory references in LOOP.  */
+   gather_mem_refs (loop, mem_refs, classes);
+ 
+   /* 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);
    free (exits);
  }
  
*************** static void
*** 1250,1281 ****
  determine_lsm (struct loops *loops)
  {
    struct loop *loop;
!   basic_block bb;
  
    if (!loops->tree_root->inner)
      return;
  
!   /* 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)
      {
!       determine_lsm_loop (loop);
  
        if (loop->inner)
  	{
--- 1327,1349 ----
  determine_lsm (struct loops *loops)
  {
    struct loop *loop;
!   struct alias_class *classes;
  
    if (!loops->tree_root->inner)
      return;
  
!   /* This field is indexed by versions of virtual ssa names.  Since
!      we do not create any new virtual ssa names, field of a fixed
!      size is sufficient.  */
!   classes = xcalloc (num_ssa_names, sizeof (struct alias_class));
  
!   /* Pass the loops from the outermost and perform the store motion as
!      suitable.  */
  
    loop = loops->tree_root->inner;
    while (1)
      {
!       determine_lsm_loop (loop, classes);
  
        if (loop->inner)
  	{
*************** determine_lsm (struct loops *loops)
*** 1287,1299 ****
  	  loop = loop->outer;
  	  if (loop == loops->tree_root)
  	    {
- 	      free_df ();
  	      loop_commit_inserts ();
  	      return;
  	    }
  	}
        loop = loop->next;
      }
  }
  
  /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
--- 1355,1367 ----
  	  loop = loop->outer;
  	  if (loop == loops->tree_root)
  	    {
  	      loop_commit_inserts ();
  	      return;
  	    }
  	}
        loop = loop->next;
      }
+   free (classes);
  }
  
  /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
Index: tree-ssa-loop-ivopts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-ivopts.c,v
retrieving revision 2.42
diff -c -3 -p -r2.42 tree-ssa-loop-ivopts.c
*** tree-ssa-loop-ivopts.c	19 Jan 2005 22:50:04 -0000	2.42
--- tree-ssa-loop-ivopts.c	6 Feb 2005 15:45:09 -0000
*************** tree_ssa_iv_optimize_loop (struct ivopts
*** 5172,5179 ****
    /* Remove the ivs that are unused after rewriting.  */
    remove_unused_ivs (data);
  
-   loop_commit_inserts ();
- 
    /* We have changed the structure of induction variables; it might happen
       that definitions in the scev database refer to some of them that were
       eliminated.  */
--- 5172,5177 ----


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]