Re: [PATCH][4/n] Remove GENERIC stmt combining from SCCVN

[Andrew MacLeod <amacleod at redhat dot com>]

On 07/16/2015 07:54 AM, Andrew MacLeod wrote:
> On 07/16/2015 03:27 AM, Richard Biener wrote:
> > On Wed, 15 Jul 2015, Andrew MacLeod wrote:
> >
> > > admittedly neither situation is very common I suspect, but it does 
> > > seem like a
> > > hidden gotchya waiting to happen.
> > I guess we either want to checking-assert that we never hit that
> > special marker or handle it appropriately.  Or even better avoid
> > it in the first place (not sure why we have it - I suppose to allow
> > modifying immediate uses of the current stmt from inside
> > FOR_EACH_IMM_USE_STMT).
> >
> > For me single_imm_use_1 crashed on the NULL USE_STMT at
> >
> >      if (!is_gimple_debug (USE_STMT (ptr)))
> >
> > so I presume all was fine until debug stmts were introduced
> > (well, fine as in not crashing, not as in giving correct answers).
> yes, It was probably still wrong, we just erred reporting that a real 
> single_use statemen't wasn't.
>
>  The marker is unique in that the STMT field is NULL, which can't 
> happen otherwise.
>
> I'll think about how to efficiently get this right
>
> Andrew
We need to keep the marker because its we need it to update in a list 
that is being iterated upon.

The affected routines are has_zero_uses, has_single_use, single_imm_use, 
and num_imm_uses.  They can all be impacted by the presence of the  marker.

The fix the issue, we need to check USE_STMT for null before checking 
for is_gimple_debug() in all cases.

It seemed to me that the shortcutting I was taking to check the simple 
cases first may not be saving us much... it looked like the executed 
code path ought to be pretty similar to a simple loop... similar number 
of compares and instructions and jumps.    So I implemented 
has_zero_uses() and has_single_use() directly with a loop, and compared 
the generated code at -O.

sure enough,  the code path was pretty darn close.   In fact, the 
routines ought to be generally faster.. without the shortcut tests the 
cases for 2 or more entries no longer require a function call, and they 
get a 2 entries "headstart" into the list since those first 2 iterations 
were basically duplicated by the shortcut code.

num_imm_uses is slightly slower, but its only called from one or 2 
places, and its not THAT much slower.

Finally, given the extra work that single_imm_uses does, It seemed 
prudent to mostly leave it alone, just add the check.

Want to give this a try and make sure it resolves the issue?

It bootstraps on x86_64-unknown-linux-gnu and shows no new regressions.
OK for trunk?

Andrew

PS, assembly at -O2 for :

// New version
bool tryit1(tree t)
{
  return has_single_use (t);   // new implementation
}
<..>
        movq    48(%rdi), %rdx
        leaq    40(%rdi), %rsi
        xorl    %eax, %eax
        cmpq    %rdx, %rsi
        je      .L4154
        .p2align 4,,10
        .p2align 3
.L4152:
        movq    16(%rdx), %rcx
        testq   %rcx, %rcx
        je      .L4150
        cmpb    $2, (%rcx)
        je      .L4150
        testb   %al, %al
        jne     .L4155
        movl    $1, %eax
.L4150:
        movq    8(%rdx), %rdx
        cmpq    %rdx, %rsi
        jne     .L4152
        rep ret
// Old version
bool tryit2(tree t)
{
  return has_single_use2 (t);  // old implemenation
}

<...>
        movq    %rdi, %rax
        movq    48(%rax), %rax
        leaq    40(%rdi), %rdi
        cmpq    %rax, %rdi
        je      .L4168
        cmpq    8(%rax), %rdi
        je      .L4171
        xorl    %edx, %edx
        xorl    %esi, %esi
        jmp 
_Z16single_imm_use_1PK17ssa_use_operand_tPPS_PP21gimple_statement_base@PLT
        .p2align 4,,10
        .p2align 3
.L4171:
        movq    16(%rax), %rax
        testq   %rax, %rax
        je      .L4168
        cmpb    $2, (%rax)
        setne   %al
        ret
        .p2align 4,,10
        .p2align 3
.L4168:
        xorl    %eax, %eax
        ret


	* ssa-iterators.h (has_zero_uses, has_single_use): Implement as
	straight loops.
	(single_imm_use): Check for iterator node.
	(num_imm_uses): Likewise.
	* tree-ssa-operands.c (has_zero_uses_1): Delete.
	(single_imm_use_1): Check for iterator node.

Index: ssa-iterators.h
===================================================================
*** ssa-iterators.h	(revision 225871)
--- ssa-iterators.h	(working copy)
*************** struct imm_use_iterator
*** 114,120 ****
  
  
  
- extern bool has_zero_uses_1 (const ssa_use_operand_t *head);
  extern bool single_imm_use_1 (const ssa_use_operand_t *head,
  			      use_operand_p *use_p, gimple *stmt);
  
--- 114,119 ----
*************** next_readonly_imm_use (imm_use_iterator
*** 379,420 ****
  static inline bool
  has_zero_uses (const_tree var)
  {
!   const ssa_use_operand_t *const ptr = &(SSA_NAME_IMM_USE_NODE (var));
! 
!   /* A single use_operand means there is no items in the list.  */
!   if (ptr == ptr->next)
!     return true;
  
!   /* If there are debug stmts, we have to look at each use and see
!      whether there are any nondebug uses.  */
!   if (!MAY_HAVE_DEBUG_STMTS)
!     return false;
  
!   return has_zero_uses_1 (ptr);
  }
  
  /* Return true if VAR has a single nondebug use.  */
  static inline bool
  has_single_use (const_tree var)
  {
!   const ssa_use_operand_t *const ptr = &(SSA_NAME_IMM_USE_NODE (var));
! 
!   /* If there aren't any uses whatsoever, we're done.  */
!   if (ptr == ptr->next)
!     return false;
! 
!   /* If there's a single use, check that it's not a debug stmt.  */
!   if (ptr == ptr->next->next)
!     return !is_gimple_debug (USE_STMT (ptr->next));
! 
!   /* If there are debug stmts, we have to look at each of them.  */
!   if (!MAY_HAVE_DEBUG_STMTS)
!     return false;
  
!   return single_imm_use_1 (ptr, NULL, NULL);
  }
! 
! 
  /* If VAR has only a single immediate nondebug use, return true, and
     set USE_P and STMT to the use pointer and stmt of occurrence.  */
  static inline bool
--- 378,413 ----
  static inline bool
  has_zero_uses (const_tree var)
  {
!   const ssa_use_operand_t *const head = &(SSA_NAME_IMM_USE_NODE (var));
!   const ssa_use_operand_t *ptr;
  
!   for (ptr = head->next; ptr != head; ptr = ptr->next)
!     if (USE_STMT (ptr) && !is_gimple_debug (USE_STMT (ptr)))
!       return false;
  
!   return true;
  }
  
  /* Return true if VAR has a single nondebug use.  */
  static inline bool
  has_single_use (const_tree var)
  {
!   const ssa_use_operand_t *const head = &(SSA_NAME_IMM_USE_NODE (var));
!   const ssa_use_operand_t *ptr;
!   bool single = false;
!    
!   for (ptr = head->next; ptr != head; ptr = ptr->next)
!     if (USE_STMT(ptr) && !is_gimple_debug (USE_STMT (ptr)))
!       {
! 	if (single)
! 	  return false;
! 	else 
! 	  single = true;
!       }
  
!   return single;
  }
!     
  /* If VAR has only a single immediate nondebug use, return true, and
     set USE_P and STMT to the use pointer and stmt of occurrence.  */
  static inline bool
*************** single_imm_use (const_tree var, use_oper
*** 434,440 ****
    /* If there's a single use, check that it's not a debug stmt.  */
    if (ptr == ptr->next->next)
      {
!       if (!is_gimple_debug (USE_STMT (ptr->next)))
  	{
  	  *use_p = ptr->next;
  	  *stmt = ptr->next->loc.stmt;
--- 427,433 ----
    /* If there's a single use, check that it's not a debug stmt.  */
    if (ptr == ptr->next->next)
      {
!       if (USE_STMT (ptr->next) && !is_gimple_debug (USE_STMT (ptr->next)))
  	{
  	  *use_p = ptr->next;
  	  *stmt = ptr->next->loc.stmt;
*************** single_imm_use (const_tree var, use_oper
*** 444,453 ****
  	goto return_false;
      }
  
-   /* If there are debug stmts, we have to look at each of them.  */
-   if (!MAY_HAVE_DEBUG_STMTS)
-     goto return_false;
- 
    return single_imm_use_1 (ptr, use_p, stmt);
  }
  
--- 437,442 ----
*************** num_imm_uses (const_tree var)
*** 461,470 ****
  
    if (!MAY_HAVE_DEBUG_STMTS)
      for (ptr = start->next; ptr != start; ptr = ptr->next)
!       num++;
    else
      for (ptr = start->next; ptr != start; ptr = ptr->next)
!       if (!is_gimple_debug (USE_STMT (ptr)))
  	num++;
  
    return num;
--- 450,460 ----
  
    if (!MAY_HAVE_DEBUG_STMTS)
      for (ptr = start->next; ptr != start; ptr = ptr->next)
!       if (USE_STMT (ptr))
! 	num++;
    else
      for (ptr = start->next; ptr != start; ptr = ptr->next)
!       if (USE_STMT (ptr) && !is_gimple_debug (USE_STMT (ptr)))
  	num++;
  
    return num;
Index: tree-ssa-operands.c
===================================================================
*** tree-ssa-operands.c	(revision 225871)
--- tree-ssa-operands.c	(working copy)
*************** unlink_stmt_vdef (gimple stmt)
*** 1304,1325 ****
      SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vuse) = 1;
  }
  
- 
- /* Return true if the var whose chain of uses starts at PTR has no
-    nondebug uses.  */
- bool
- has_zero_uses_1 (const ssa_use_operand_t *head)
- {
-   const ssa_use_operand_t *ptr;
- 
-   for (ptr = head->next; ptr != head; ptr = ptr->next)
-     if (!is_gimple_debug (USE_STMT (ptr)))
-       return false;
- 
-   return true;
- }
- 
- 
  /* Return true if the var whose chain of uses starts at PTR has a
     single nondebug use.  Set USE_P and STMT to that single nondebug
     use, if so, or to NULL otherwise.  */
--- 1304,1309 ----
*************** single_imm_use_1 (const ssa_use_operand_
*** 1330,1336 ****
    ssa_use_operand_t *ptr, *single_use = 0;
  
    for (ptr = head->next; ptr != head; ptr = ptr->next)
!     if (!is_gimple_debug (USE_STMT (ptr)))
        {
  	if (single_use)
  	  {
--- 1314,1320 ----
    ssa_use_operand_t *ptr, *single_use = 0;
  
    for (ptr = head->next; ptr != head; ptr = ptr->next)
!     if (USE_STMT(ptr) && !is_gimple_debug (USE_STMT (ptr)))
        {
  	if (single_use)
  	  {
*************** single_imm_use_1 (const ssa_use_operand_
*** 1348,1350 ****
--- 1332,1335 ----
  
    return single_use;
  }
+