[PATCH] Rewrite mem-ref locs and iteration over it in LIM

[Richard Biener <rguenther at suse dot de>]

This combines two earlier patches to do the mem-ref-loc rewrite
in one go.  It makes the allocation less arcane and avoids
copying all locations by providing an iterator interface from
which we also can exit early.

There is no measuable benefit for the testcase in PR39326, but
this will make removing the all_refs_in_loop bitmap cheaper.

Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.

Richard.

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

	* tree-ssa-loop-im.c (struct mem_ref_locs): Remove.
	(struct mem_ref): Make accesses_in_loop a vec of a vec of
	aggregate mem_ref_loc.
	(free_mem_ref_locs): Inline into ...
	(memref_free): ... this and adjust.
	(mem_ref_alloc): Adjust.
	(mem_ref_locs_alloc): Remove.
	(record_mem_ref_loc): Adjust.
	(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-21 16:54:20.390602740 +0100
--- trunk/gcc/tree-ssa-loop-im.c	2013-03-21 16:55:09.712153763 +0100
*************** typedef struct mem_ref_loc
*** 105,118 ****
  } *mem_ref_loc_p;
  
  
- /* The list of memory reference locations in a loop.  */
- 
- typedef struct mem_ref_locs
- {
-   vec<mem_ref_loc_p> locs;
- } *mem_ref_locs_p;
- 
- 
  /* Description of a memory reference.  */
  
  typedef struct mem_ref
--- 105,110 ----
*************** typedef struct mem_ref
*** 127,133 ****
  
    bitmap stored;		/* The set of loops in that this memory location
  				   is stored to.  */
!   vec<mem_ref_locs_p> accesses_in_loop;
  				/* The locations of the accesses.  Vector
  				   indexed by the loop number.  */
  
--- 119,125 ----
  
    bitmap 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
*** 1459,1491 ****
    return operand_equal_p (mem1->mem.ref, (const_tree) obj2, 0);
  }
  
- /* Releases list of memory reference locations ACCS.  */
- 
- static void
- free_mem_ref_locs (mem_ref_locs_p accs)
- {
-   unsigned i;
-   mem_ref_loc_p loc;
- 
-   if (!accs)
-     return;
- 
-   FOR_EACH_VEC_ELT (accs->locs, i, loc)
-     free (loc);
-   accs->locs.release ();
-   free (accs);
- }
- 
  /* A function to free the mem_ref object OBJ.  */
  
  static void
  memref_free (struct mem_ref *mem)
  {
    unsigned i;
!   mem_ref_locs_p accs;
  
    FOR_EACH_VEC_ELT (mem->accesses_in_loop, i, accs)
!     free_mem_ref_locs (accs);
    mem->accesses_in_loop.release ();
  
    free (mem);
--- 1451,1466 ----
    return operand_equal_p (mem1->mem.ref, (const_tree) obj2, 0);
  }
  
  /* A function to free the mem_ref object OBJ.  */
  
  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,
*** 1511,1549 ****
    return ref;
  }
  
- /* Allocates and returns the new list of locations.  */
- 
- static mem_ref_locs_p
- mem_ref_locs_alloc (void)
- {
-   mem_ref_locs_p accs = XNEW (struct mem_ref_locs);
-   accs->locs.create (0);
-   return accs;
- }
- 
  /* Records memory reference location *LOC in LOOP to the memory reference
     description REF.  The reference occurs in statement STMT.  */
  
  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);
!   mem_ref_locs_p accs;
  
    if (ref->accesses_in_loop.length ()
        <= (unsigned) loop->num)
      ref->accesses_in_loop.safe_grow_cleared (loop->num + 1);
-   accs = ref->accesses_in_loop[loop->num];
-   if (!accs)
-     {
-       accs = mem_ref_locs_alloc ();
-       ref->accesses_in_loop[loop->num] = accs;
-     }
- 
-   aref->stmt = stmt;
-   aref->ref = loc;
  
!   accs->locs.safe_push (aref);
  }
  
  /* Marks reference REF as stored in LOOP.  */
--- 1486,1506 ----
    return ref;
  }
  
  /* Records memory reference location *LOC in LOOP to the memory reference
     description REF.  The reference occurs in statement STMT.  */
  
  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);
  }
  
  /* Marks reference REF as stored in LOOP.  */
*************** mem_refs_may_alias_p (mem_ref_p mem1, me
*** 1804,1846 ****
    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)
  {
-   mem_ref_locs_p accs;
    unsigned i;
    mem_ref_loc_p loc;
    bitmap refs = memory_accesses.all_refs_in_loop[loop->num];
    struct loop *subloop;
  
    if (!bitmap_bit_p (refs, ref->id))
!     return;
  
!   if (ref->accesses_in_loop.length ()
!       > (unsigned) loop->num)
!     {
!       accs = ref->accesses_in_loop[loop->num];
!       if (accs)
! 	{
! 	  FOR_EACH_VEC_ELT (accs->locs, 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.  */
--- 1761,1810 ----
    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;
    bitmap refs = memory_accesses.all_refs_in_loop[loop->num];
    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,
*** 1848,1861 ****
  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
--- 1812,1818 ----
  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
*** 2113,2148 ****
    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.ref, ~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;
  }
  
--- 2070,2109 ----
    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.ref, ~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
*** 2237,2296 ****
      }
  }
  
! /* 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 = ao_ref_base (&ref->mem);
!   if (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.  */
--- 2198,2261 ----
      }
  }
  
! 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 = ao_ref_base (&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.  */