[PATCH][8/n] tree LIM TLC

[PATCH][8/n] tree LIM TLC

[Richard Biener]

This changes the vector of locations we track for each memory reference
from storing a pointer to a location aggregate to storing the aggregate
directly, avoiding an indirection and tons of small memory allocations.

This also touches the way we iterate over locations of refs - instead
of building up a vector of all refs and then iterating over it and
then freeing it the following implements a proper iterator using
a functor template (and allows an early exit from ref_always_accessed_p).

Bootstrap and regtest pending on x86_64-unknown-linux-gnu.

Richard.

2013-03-13  Richard Biener  <rguenther@suse.de>

	* tree-ssa-loop-im.c (struct mem_ref): Make accesses_in_loop
	a vec of a vec of the aggregate mem_ref_loc.
	(memref_free): Adjust.
	(record_mem_ref_loc): Likewise.
	(get_all_locs_in_loop): Rewrite into ...
	(for_all_locs_in_loop): ... this iterator.
	(rewrite_mem_ref_loc): New functor.
	(rewrite_mem_refs): Use for_all_locs_in_loop.
	(sm_set_flag_if_changed): New functor.
	(execute_sm_if_changed_flag_set): Use for_all_locs_in_loop.
	(ref_always_accessed): New functor.
	(ref_always_accessed_p): Use for_all_locs_in_loop.

Index: trunk/gcc/tree-ssa-loop-im.c
===================================================================
*** trunk.orig/gcc/tree-ssa-loop-im.c	2013-03-13 14:15:32.000000000 +0100
--- trunk/gcc/tree-ssa-loop-im.c	2013-03-13 14:19:17.016903594 +0100
*************** typedef struct mem_ref
*** 115,121 ****
    hashval_t hash;		/* Its hash value.  */
    bitmap_head stored;		/* The set of loops in that this memory location
  				   is stored to.  */
!   vec<vec<mem_ref_loc_p> > accesses_in_loop;
  				/* The locations of the accesses.  Vector
  				   indexed by the loop number.  */
  
--- 115,121 ----
    hashval_t hash;		/* Its hash value.  */
    bitmap_head stored;		/* The set of loops in that this memory location
  				   is stored to.  */
!   vec<vec<mem_ref_loc> > accesses_in_loop;
  				/* The locations of the accesses.  Vector
  				   indexed by the loop number.  */
  
*************** memref_eq (const void *obj1, const void
*** 1435,1450 ****
  static void
  memref_free (struct mem_ref *mem)
  {
!   unsigned i, j;
!   vec<mem_ref_loc_p> *accs;
!   mem_ref_loc_p loc;
  
    FOR_EACH_VEC_ELT (mem->accesses_in_loop, i, accs)
!     {
!       FOR_EACH_VEC_ELT (*accs, j, loc)
! 	free (loc);
!       accs->release ();
!     }
    mem->accesses_in_loop.release ();
  
    free (mem);
--- 1435,1445 ----
  static void
  memref_free (struct mem_ref *mem)
  {
!   unsigned i;
!   vec<mem_ref_loc> *accs;
  
    FOR_EACH_VEC_ELT (mem->accesses_in_loop, i, accs)
!     accs->release ();
    mem->accesses_in_loop.release ();
  
    free (mem);
*************** mem_ref_alloc (tree mem, unsigned hash,
*** 1474,1487 ****
  static void
  record_mem_ref_loc (mem_ref_p ref, struct loop *loop, gimple stmt, tree *loc)
  {
!   mem_ref_loc_p aref = XNEW (struct mem_ref_loc);
  
    if (ref->accesses_in_loop.length ()
        <= (unsigned) loop->num)
      ref->accesses_in_loop.safe_grow_cleared (loop->num + 1);
  
!   aref->stmt = stmt;
!   aref->ref = loc;
    ref->accesses_in_loop[loop->num].safe_push (aref);
  }
  
--- 1469,1482 ----
  static void
  record_mem_ref_loc (mem_ref_p ref, struct loop *loop, gimple stmt, tree *loc)
  {
!   mem_ref_loc aref;
  
    if (ref->accesses_in_loop.length ()
        <= (unsigned) loop->num)
      ref->accesses_in_loop.safe_grow_cleared (loop->num + 1);
  
!   aref.stmt = stmt;
!   aref.ref = loc;
    ref->accesses_in_loop[loop->num].safe_push (aref);
  }
  
*************** mem_refs_may_alias_p (tree mem1, tree me
*** 1628,1647 ****
    return true;
  }
  
! /* Rewrites location LOC by TMP_VAR.  */
! 
! static void
! rewrite_mem_ref_loc (mem_ref_loc_p loc, tree tmp_var)
! {
!   *loc->ref = tmp_var;
!   update_stmt (loc->stmt);
! }
! 
! /* Adds all locations of REF in LOOP and its subloops to LOCS.  */
  
! static void
! get_all_locs_in_loop (struct loop *loop, mem_ref_p ref,
! 		      vec<mem_ref_loc_p> *locs)
  {
    unsigned i;
    mem_ref_loc_p loc;
--- 1623,1636 ----
    return true;
  }
  
! /* Iterates over all locations of REF in LOOP and its subloops calling
!    fn.operator() with the location as argument.  When that operator
!    returns true the iteration is stopped and true is returned.
!    Otherwise false is returned.  */
  
! template <typename FN>
! static bool
! for_all_locs_in_loop (struct loop *loop, mem_ref_p ref, FN fn)
  {
    unsigned i;
    mem_ref_loc_p loc;
*************** get_all_locs_in_loop (struct loop *loop,
*** 1649,1665 ****
    struct loop *subloop;
  
    if (!bitmap_bit_p (refs, ref->id))
!     return;
  
!   if (ref->accesses_in_loop.length ()
!       > (unsigned) loop->num)
!     {
!       FOR_EACH_VEC_ELT (ref->accesses_in_loop[loop->num], i, loc)
! 	locs->safe_push (loc);
!     }
  
    for (subloop = loop->inner; subloop != NULL; subloop = subloop->next)
!     get_all_locs_in_loop (subloop, ref, locs);
  }
  
  /* Rewrites all references to REF in LOOP by variable TMP_VAR.  */
--- 1638,1672 ----
    struct loop *subloop;
  
    if (!bitmap_bit_p (refs, ref->id))
!     return false;
  
!   if (ref->accesses_in_loop.length () > (unsigned) loop->num)
!     FOR_EACH_VEC_ELT (ref->accesses_in_loop[loop->num], i, loc)
!       if (fn (loc))
! 	return true;
  
    for (subloop = loop->inner; subloop != NULL; subloop = subloop->next)
!     if (for_all_locs_in_loop (subloop, ref, fn))
!       return true;
! 
!   return false;
! }
! 
! /* Rewrites location LOC by TMP_VAR.  */
! 
! struct rewrite_mem_ref_loc
! {
!   rewrite_mem_ref_loc (tree tmp_var_) : tmp_var (tmp_var_) {}
!   bool operator()(mem_ref_loc_p loc);
!   tree tmp_var;
! };
! 
! bool
! rewrite_mem_ref_loc::operator()(mem_ref_loc_p loc)
! {
!   *loc->ref = tmp_var;
!   update_stmt (loc->stmt);
!   return false;
  }
  
  /* Rewrites all references to REF in LOOP by variable TMP_VAR.  */
*************** get_all_locs_in_loop (struct loop *loop,
*** 1667,1680 ****
  static void
  rewrite_mem_refs (struct loop *loop, mem_ref_p ref, tree tmp_var)
  {
!   unsigned i;
!   mem_ref_loc_p loc;
!   vec<mem_ref_loc_p> locs = vNULL;
! 
!   get_all_locs_in_loop (loop, ref, &locs);
!   FOR_EACH_VEC_ELT (locs, i, loc)
!     rewrite_mem_ref_loc (loc, tmp_var);
!   locs.release ();
  }
  
  /* The name and the length of the currently generated variable
--- 1674,1680 ----
  static void
  rewrite_mem_refs (struct loop *loop, mem_ref_p ref, tree tmp_var)
  {
!   for_all_locs_in_loop (loop, ref, rewrite_mem_ref_loc (tmp_var));
  }
  
  /* The name and the length of the currently generated variable
*************** execute_sm_if_changed (edge ex, tree mem
*** 1932,1967 ****
    EDGE_SUCC (new_bb, 0)->flags &= ~EDGE_FALLTHRU;
  }
  
  /* Helper function for execute_sm.  On every location where REF is
     set, set an appropriate flag indicating the store.  */
  
  static tree
  execute_sm_if_changed_flag_set (struct loop *loop, mem_ref_p ref)
  {
-   unsigned i;
-   mem_ref_loc_p loc;
    tree flag;
-   vec<mem_ref_loc_p> locs = vNULL;
    char *str = get_lsm_tmp_name (ref->mem, ~0);
- 
    lsm_tmp_name_add ("_flag");
    flag = create_tmp_reg (boolean_type_node, str);
!   get_all_locs_in_loop (loop, ref, &locs);
!   FOR_EACH_VEC_ELT (locs, i, loc)
!     {
!       gimple_stmt_iterator gsi;
!       gimple stmt;
! 
!       /* Only set the flag for writes.  */
!       if (is_gimple_assign (loc->stmt)
! 	  && gimple_assign_lhs_ptr (loc->stmt) == loc->ref)
! 	{
! 	  gsi = gsi_for_stmt (loc->stmt);
! 	  stmt = gimple_build_assign (flag, boolean_true_node);
! 	  gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
! 	}
!     }
!   locs.release ();
    return flag;
  }
  
--- 1932,1971 ----
    EDGE_SUCC (new_bb, 0)->flags &= ~EDGE_FALLTHRU;
  }
  
+ /* When REF is set on the location, set flag indicating the store.  */
+ 
+ struct sm_set_flag_if_changed
+ {
+   sm_set_flag_if_changed (tree flag_) : flag (flag_) {}
+   bool operator()(mem_ref_loc_p loc);
+   tree flag;
+ };
+ 
+ bool
+ sm_set_flag_if_changed::operator()(mem_ref_loc_p loc)
+ {
+   /* Only set the flag for writes.  */
+   if (is_gimple_assign (loc->stmt)
+       && gimple_assign_lhs_ptr (loc->stmt) == loc->ref)
+     {
+       gimple_stmt_iterator gsi = gsi_for_stmt (loc->stmt);
+       gimple stmt = gimple_build_assign (flag, boolean_true_node);
+       gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
+     }
+   return false;
+ }
+ 
  /* Helper function for execute_sm.  On every location where REF is
     set, set an appropriate flag indicating the store.  */
  
  static tree
  execute_sm_if_changed_flag_set (struct loop *loop, mem_ref_p ref)
  {
    tree flag;
    char *str = get_lsm_tmp_name (ref->mem, ~0);
    lsm_tmp_name_add ("_flag");
    flag = create_tmp_reg (boolean_type_node, str);
!   for_all_locs_in_loop (loop, ref, sm_set_flag_if_changed (flag));
    return flag;
  }
  
*************** hoist_memory_references (struct loop *lo
*** 2056,2116 ****
      }
  }
  
! /* Returns true if REF is always accessed in LOOP.  If STORED_P is true
!    make sure REF is always stored to in LOOP.  */
  
! static bool
! ref_always_accessed_p (struct loop *loop, mem_ref_p ref, bool stored_p)
  {
-   vec<mem_ref_loc_p> locs = vNULL;
-   unsigned i;
-   mem_ref_loc_p loc;
-   bool ret = false;
    struct loop *must_exec;
-   tree base;
  
!   base = get_base_address (ref->mem);
!   if (INDIRECT_REF_P (base)
!       || TREE_CODE (base) == MEM_REF)
!     base = TREE_OPERAND (base, 0);
  
!   get_all_locs_in_loop (loop, ref, &locs);
!   FOR_EACH_VEC_ELT (locs, i, loc)
      {
!       if (!get_lim_data (loc->stmt))
! 	continue;
  
!       /* If we require an always executed store make sure the statement
!          stores to the reference.  */
!       if (stored_p)
! 	{
! 	  tree lhs;
! 	  if (!gimple_get_lhs (loc->stmt))
! 	    continue;
! 	  lhs = get_base_address (gimple_get_lhs (loc->stmt));
! 	  if (!lhs)
! 	    continue;
! 	  if (INDIRECT_REF_P (lhs)
! 	      || TREE_CODE (lhs) == MEM_REF)
! 	    lhs = TREE_OPERAND (lhs, 0);
! 	  if (lhs != base)
! 	    continue;
! 	}
  
!       must_exec = get_lim_data (loc->stmt)->always_executed_in;
!       if (!must_exec)
! 	continue;
  
!       if (must_exec == loop
! 	  || flow_loop_nested_p (must_exec, loop))
! 	{
! 	  ret = true;
! 	  break;
! 	}
!     }
!   locs.release ();
  
!   return ret;
  }
  
  /* Returns true if REF1 and REF2 are independent.  */
--- 2060,2123 ----
      }
  }
  
! struct ref_always_accessed
! {
!   ref_always_accessed (struct loop *loop_, tree base_, bool stored_p_)
!       : loop (loop_), base (base_), stored_p (stored_p_) {}
!   bool operator()(mem_ref_loc_p loc);
!   struct loop *loop;
!   tree base;
!   bool stored_p;
! };
  
! bool
! ref_always_accessed::operator()(mem_ref_loc_p loc)
  {
    struct loop *must_exec;
  
!   if (!get_lim_data (loc->stmt))
!     return false;
  
!   /* If we require an always executed store make sure the statement
!      stores to the reference.  */
!   if (stored_p)
      {
!       tree lhs;
!       if (!gimple_get_lhs (loc->stmt))
! 	return false;
!       lhs = get_base_address (gimple_get_lhs (loc->stmt));
!       if (!lhs)
! 	return false;
!       if (INDIRECT_REF_P (lhs)
! 	  || TREE_CODE (lhs) == MEM_REF)
! 	lhs = TREE_OPERAND (lhs, 0);
!       if (lhs != base)
! 	return false;
!     }
  
!   must_exec = get_lim_data (loc->stmt)->always_executed_in;
!   if (!must_exec)
!     return false;
  
!   if (must_exec == loop
!       || flow_loop_nested_p (must_exec, loop))
!     return true;
  
!   return false;
! }
  
! /* Returns true if REF is always accessed in LOOP.  If STORED_P is true
!    make sure REF is always stored to in LOOP.  */
! 
! static bool
! ref_always_accessed_p (struct loop *loop, mem_ref_p ref, bool stored_p)
! {
!   tree base = get_base_address (ref->mem);
!   if (TREE_CODE (base) == MEM_REF)
!     base = TREE_OPERAND (base, 0);
! 
!   return for_all_locs_in_loop (loop, ref,
! 			       ref_always_accessed (loop, base, stored_p));
  }
  
  /* Returns true if REF1 and REF2 are independent.  */