[patch] Fix virtual operands creation in vectorizer

[Zdenek Dvorak]

Hello,

vectorizer sometimes rewrites statements like

#   SFT.5_49 = V_MAY_DEF <SFT.5_15>;
tmp.b[i_13] = 5;

to

#   SFT.5_49 = V_MAY_DEF <SFT.5_15>;
*ivtmp.52_85 = vect_cst_.47_82;

However, it does nothing to update the virtual operands of the statement
(simply the old virtual operands are preserved).  The problem is that
calling update_stmt on it will now create a different set of virtual
operands, concretely in gcc.dg/vect/vect-31.c:

#   SFT.1 = V_MAY_DEF <SFT.1>;
#   SFT.2 = V_MAY_DEF <SFT.2>;
#   SFT.3 = V_MAY_DEF <SFT.3>;
#   SFT.4 = V_MAY_DEF <SFT.4>;
#   SFT.5_49 = V_MAY_DEF <SFT.5_15>;

since we are no longer able to determine that the pointer may only point
to one of the subvars -- we get only what the type based analysis gives us.

The most precise fix would be to set up the appropriate points-to sets &
NMT for the ivtmp.52_85 pointer; however, this requires more in-depth
knowledge of the autovectorizer than I posses to be able to determine
what these sets are in each case.  Instead, the patch below implements a
conservative solution that marks the new virtual operands of these
statements for renaming.  As this loses some information, which may
prevent further optimizations, someone more familiar with the vectorizer
should look to it and implement more precise solution later.

Fixing this bug also makes it unnecessary to have
mark_new_vars_to_rename in tree-ssa-loop-ivopts.c:rewrite_use.  As the
idea to add this call there was discussed several times, and this time the
call was introduced there purely to mask this bug in vectorizer, I have also
added a short comment explaining why adding it is a bad idea.

Bootstrapped & regtested on i686, x86_64 and ia64.

Zdenek

	* tree-ssa-loop-ivopts.c (rewrite_use): Call update_stmt instead of
	mark_new_vars_to_rename.  Explain why.
	* tree-ssa-loop.c (pass_iv_optimize): Remove TODO_update_ssa.
	* tree-vect-transform.c (vectorizable_store, vectorizable_load,
	vectorizable_load): Add mark_new_vars_to_rename calls for the modified
	statements.

Index: tree-ssa-loop-ivopts.c
===================================================================
*** tree-ssa-loop-ivopts.c	(revision 109451)
--- tree-ssa-loop-ivopts.c	(working copy)
*************** rewrite_use (struct ivopts_data *data,
*** 5822,5828 ****
        default:
  	gcc_unreachable ();
      }
!   mark_new_vars_to_rename (use->stmt);
  }
  
  /* Rewrite the uses using the selected induction variables.  */
--- 5822,5861 ----
        default:
  	gcc_unreachable ();
      }
! 
!   /* rewrite_use_address rewrites memory references to TARGET_MEM_REFs.
!      Ensuring that the TARGET_MEM_REF gets the same set of virtual operands as
!      the original memory reference is complicated (mainly because the process
!      of determining the virtual operands for the original memory reference is
!      nontrivial, see tree-ssa-operands.c:get_expr_operands), and from time to
!      time (especially when something related to alias analysis changes), the
!      so far used approach may fail and get_ref_tag needs to be updated to
!      handle the new situation.  One might ask ``why bother, just put
!      mark_new_vars_to_rename (use->stmt) here and TODO_update_ssa
!      to the flags of this pass, and you are done.'' This is not a good idea,
!      for the following reasons:
!    
!      1) Effectivity -- while the update_ssa call usually is not very expensive,
! 	calling it without a good reason still is not good.
!      2) Marking vars for renaming here does something in two cases:
! 	a) the new virtual operands of the reference are a strict superset of
! 	   the old ones.  This means that we have lost some information (we now
! 	   believe this memory reference to alias more things than before), and
! 	   this may prevent other optimizations.
! 	b) the new virtual operands are not a superset of the old ones.  This
! 	   is a real problem, as we now wrongly believe the ref not to alias
! 	   some of the references, which may lead to hard to debug
! 	   misscompilations.  Getting an ICE is much better in this case.
!      3) In many cases, the problem is not in ivopts, but in some earlier pass
! 	that failed to update virtual operands correctly (the reason usually is
! 	a forgotten call to update_stmt or mark_new_vars_to_rename).
! 	Masking such a bug with mark_new_vars_to_rename call here only
! 	causes it to show up again later.
!    
!      So if you run into problems that cause you to believe that you need to
!      have mark_new_vars_to_rename here, please investigate and fix the real
!      cause of the problem instead.  */
!   update_stmt (use->stmt);
  }
  
  /* Rewrite the uses using the selected induction variables.  */
Index: tree-ssa-loop.c
===================================================================
*** tree-ssa-loop.c	(revision 109451)
--- tree-ssa-loop.c	(working copy)
*************** struct tree_opt_pass pass_iv_optimize =
*** 433,440 ****
    0,					/* properties_destroyed */
    0,					/* todo_flags_start */
    TODO_dump_func
!   | TODO_verify_loops
!   | TODO_update_ssa,			/* todo_flags_finish */
    0					/* letter */
  };
  
--- 433,439 ----
    0,					/* properties_destroyed */
    0,					/* todo_flags_start */
    TODO_dump_func
!   | TODO_verify_loops,			/* todo_flags_finish */
    0					/* letter */
  };
  
Index: tree-vect-transform.c
===================================================================
*** tree-vect-transform.c	(revision 109451)
--- tree-vect-transform.c	(working copy)
*************** vectorizable_store (tree stmt, block_stm
*** 1592,1597 ****
--- 1592,1598 ----
  	 renaming so the later use will also be renamed.  */
        mark_sym_for_renaming (SSA_NAME_VAR (def));
      }
+   mark_new_vars_to_rename (*vec_stmt);
  
    return true;
  }
*************** vectorizable_load (tree stmt, block_stmt
*** 1707,1712 ****
--- 1708,1714 ----
        TREE_OPERAND (new_stmt, 0) = new_temp;
        vect_finish_stmt_generation (stmt, new_stmt, bsi);
        copy_virtual_operands (new_stmt, stmt);
+       mark_new_vars_to_rename (new_stmt);
      }
    else if (alignment_support_cheme == dr_unaligned_software_pipeline)
      {
*************** vectorizable_load (tree stmt, block_stmt
*** 1746,1752 ****
        msq_init = TREE_OPERAND (new_stmt, 0);
        copy_virtual_operands (new_stmt, stmt);
        update_vuses_to_preheader (new_stmt, loop);
! 
  
        /* <2> Create lsq = *(floor(p2')) in the loop  */ 
        offset = size_int (TYPE_VECTOR_SUBPARTS (vectype) - 1);
--- 1748,1754 ----
        msq_init = TREE_OPERAND (new_stmt, 0);
        copy_virtual_operands (new_stmt, stmt);
        update_vuses_to_preheader (new_stmt, loop);
!       mark_new_vars_to_rename (new_stmt);
  
        /* <2> Create lsq = *(floor(p2')) in the loop  */ 
        offset = size_int (TYPE_VECTOR_SUBPARTS (vectype) - 1);
*************** vectorizable_load (tree stmt, block_stmt
*** 1759,1765 ****
        vect_finish_stmt_generation (stmt, new_stmt, bsi);
        lsq = TREE_OPERAND (new_stmt, 0);
        copy_virtual_operands (new_stmt, stmt);
! 
  
        /* <3> */
        if (targetm.vectorize.builtin_mask_for_load)
--- 1761,1767 ----
        vect_finish_stmt_generation (stmt, new_stmt, bsi);
        lsq = TREE_OPERAND (new_stmt, 0);
        copy_virtual_operands (new_stmt, stmt);
!       mark_new_vars_to_rename (new_stmt);
  
        /* <3> */
        if (targetm.vectorize.builtin_mask_for_load)