[PATCH] for Re: Bug in loop invariant motion with trivial test case

[Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>]

Hello,

> On Thursday 12 August 2004 22:44, Richard Henderson wrote:
> > On Thu, Aug 12, 2004 at 10:40:08PM +0200, Steven Bosscher wrote:
> > > I'm wondering if we really want to apply this optimization to
> > > aggregate types if they appear as an lvalue, because the
> > > replacement temporary is itself also an aggregate, and it can
> > > never be a register.  So perhaps something like this,

this testcase actually reveals several problems in store motion:

1) We should only perform the optimization for memory references
   whose type passes is_gimple_reg_type test, so that we may create
   ssa names for the temporary variables.
2) Memory references in arguments of calls were not scanned.  This
   should not be a problem as long as we work only with is_gimple_reg_type
   references, since those are always passed through a temporary, but
   just for sure the patch also cleans up this issue.
3) Handling of call clobbered variables worked just by pure luck --
   as a side effect of the problem #2, i.e. this issue got revealed
   when I fixed it.

Bootstrapped & regtested on i686.

Zdenek

	* tree-ssa-loop-im.c (fem_single_reachable_address, for_each_memref):
	New functions.
	(single_reachable_address): Use them.
	(schedule_sm): Add dump.
	(is_call_clobbered_ref): New function.
	(determine_lsm_reg): Check whether the reference is call clobbered.
	Only work for gimple_reg_type values.

Index: tree-ssa-loop-im.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-im.c,v
retrieving revision 2.5
diff -c -3 -p -r2.5 tree-ssa-loop-im.c
*** tree-ssa-loop-im.c	10 Aug 2004 18:31:26 -0000	2.5
--- tree-ssa-loop-im.c	22 Aug 2004 17:36:54 -0000
*************** maybe_queue_var (tree var, struct loop *
*** 833,866 ****
    queue[(*in_queue)++] = stmt;
  }
  
  /* 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.  */
  
  static tree
  single_reachable_address (struct loop *loop, tree stmt,
! 			  struct mem_ref **mem_refs)
  {
    tree *queue = xmalloc (sizeof (tree) * max_uid);
    sbitmap seen = sbitmap_alloc (max_uid);
-   tree common_ref = NULL, *aref;
    unsigned in_queue = 1;
    dataflow_t df;
    unsigned i, n;
    v_may_def_optype v_may_defs;
    vuse_optype vuses;
  
    sbitmap_zero (seen);
  
    *mem_refs = NULL;
  
    queue[0] = stmt;
    SET_BIT (seen, stmt_ann (stmt)->uid);
  
    while (in_queue)
      {
        stmt = queue[--in_queue];
  
        if (LIM_DATA (stmt)
  	  && LIM_DATA (stmt)->sm_done)
--- 833,950 ----
    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)
  {
    tree *queue = xmalloc (sizeof (tree) * max_uid);
    sbitmap seen = sbitmap_alloc (max_uid);
    unsigned in_queue = 1;
    dataflow_t df;
    unsigned i, n;
    v_may_def_optype v_may_defs;
    vuse_optype vuses;
+   struct sra_data sra_data;
+   tree call;
  
    sbitmap_zero (seen);
  
    *mem_refs = NULL;
+   sra_data.mem_refs = mem_refs;
+   sra_data.common_ref = NULL_TREE;
  
    queue[0] = stmt;
    SET_BIT (seen, stmt_ann (stmt)->uid);
+   *seen_call_stmt = false;
  
    while (in_queue)
      {
        stmt = queue[--in_queue];
+       sra_data.stmt = stmt;
  
        if (LIM_DATA (stmt)
  	  && LIM_DATA (stmt)->sm_done)
*************** single_reachable_address (struct loop *l
*** 869,885 ****
        switch (TREE_CODE (stmt))
  	{
  	case MODIFY_EXPR:
! 	  aref = &TREE_OPERAND (stmt, 0);
! 	  if (is_gimple_reg (*aref)
! 	      || !is_gimple_lvalue (*aref))
! 	    aref = &TREE_OPERAND (stmt, 1);
! 	  if (is_gimple_reg (*aref)
! 	      || !is_gimple_lvalue (*aref)
! 	      || (common_ref && !operand_equal_p (*aref, common_ref, 0)))
  	    goto fail;
- 	  common_ref = *aref;
  
! 	  record_mem_ref (mem_refs, stmt, aref);
  
  	  /* Traverse also definitions of the VUSES (there may be other
  	     distinct from the one we used to get to this statement).  */
--- 953,972 ----
        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).  */
*************** single_reachable_address (struct loop *l
*** 926,932 ****
    free (queue);
    sbitmap_free (seen);
  
!   return common_ref;
  
  fail:
    free_mem_refs (*mem_refs);
--- 1013,1019 ----
    free (queue);
    sbitmap_free (seen);
  
!   return sra_data.common_ref;
  
  fail:
    free_mem_refs (*mem_refs);
*************** schedule_sm (struct loop *loop, edge *ex
*** 994,999 ****
--- 1081,1093 ----
    tree load, store;
    struct fmt_data fmt_data;
  
+   if (dump_file && (dump_flags & TDF_DETAILS))
+     {
+       fprintf (dump_file, "Executing store motion of ");
+       print_generic_expr (dump_file, ref, 0);
+       fprintf (dump_file, " from loop %d\n", loop->num);
+     }
+ 
    tmp_var = make_rename_temp (TREE_TYPE (ref), "lsm_tmp");
  
    fmt_data.loop = loop;
*************** schedule_sm (struct loop *loop, edge *ex
*** 1023,1028 ****
--- 1117,1155 ----
      }
  }
  
+ /* 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 (TREE_CODE (base) == INDIRECT_REF)
+     {
+       /* 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;
+     }
+ 
+   abort ();
+ }
+ 
  /* 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,
*************** determine_lsm_reg (struct loop *loop, ed
*** 1037,1055 ****
    tree ref;
    struct mem_ref *mem_refs, *aref;
    struct loop *must_exec;
    
    if (is_gimple_reg (reg))
      return;
    
!   ref = single_reachable_address (loop, SSA_NAME_DEF_STMT (reg), &mem_refs);
    if (!ref)
      return;
  
    if (!for_each_index (&ref, may_move_till, loop))
!     {
!       free_mem_refs (mem_refs);
!       return;
!     }
  
    if (tree_could_trap_p (ref))
      {
--- 1164,1191 ----
    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))
      {
*************** determine_lsm_reg (struct loop *loop, ed
*** 1079,1091 ****
  	}
  
        if (!aref)
! 	{
! 	  free_mem_refs (mem_refs);
! 	  return;
! 	}
      }
  
    schedule_sm (loop, exits, n_exits, ref, mem_refs);
    free_mem_refs (mem_refs);
  }
  
--- 1215,1226 ----
  	}
  
        if (!aref)
! 	goto fail;
      }
  
    schedule_sm (loop, exits, n_exits, ref, mem_refs);
+ 
+ fail: ;
    free_mem_refs (mem_refs);
  }