[PATCH] Make PRE PHI insertion use an already available PHI

[Richard Guenther <rguenther at suse dot de>]

This makes us no longer rely on a second DOM pass for 
gcc.dg/builtins-20.c.  The case in question is

extern double cos(double);
void test2(double x, double y)
{
  if (cos(y<10 ? x : -y) != cos(y<10 ? x : y))
      link_error ();
}

which we don't fold directly but have to deal with during optimization.
PRE figures out that all is equivalent but produces

<bb 4>:
  # x_1 = PHI <x_5(D)(7), y_3(D)(3)>
  # D.1955_15 = PHI <D.1955_14(7), D.1955_7(3)>
  # prephitmp_22 = PHI <D.1955_14(7), D.1955_7(3)>
  D.1960_10 = prephitmp_22;
  if (D.1955_15 != D.1960_10)

adding a duplicate PHI node.  We can easily avoid this by looking up
the expression we want to insert first as done by this patch.

Further simplifying also the condition would require adjusting
of existing value-numbers.  In principle we would need to re-run
SCCVN after insertion to capture all possible new equivalences,
but instead of doing so for the above case we can wait for the
next copyprop pass to simplify things (I guess re-running SCCVN
after insertion is too costly, maybe something we could do at -O3
though).

Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.
I'll apply after that succeeded.

Thanks,
Richard.

2008-08-21  Richard Guenther  <rguenther@suse.de>

	* tree-ssa-pre.c (insert_into_preds_of_block): Before inserting
	a PHI ask VN if it is already available.
	* tree-ssa-sccvn.h (vn_phi_lookup): Declare.
	* tree-ssa-sccvn.c (vn_phi_lookup): Export.

Index: gcc/tree-ssa-pre.c
===================================================================
*** gcc/tree-ssa-pre.c	(revision 139384)
--- gcc/tree-ssa-pre.c	(working copy)
*************** insert_into_preds_of_block (basic_block
*** 2896,2902 ****
    pre_expr eprime;
    edge_iterator ei;
    tree type = get_expr_type (expr);
!   tree temp;
    gimple phi;
  
    if (dump_file && (dump_flags & TDF_DETAILS))
--- 2896,2902 ----
    pre_expr eprime;
    edge_iterator ei;
    tree type = get_expr_type (expr);
!   tree temp, res;
    gimple phi;
  
    if (dump_file && (dump_flags & TDF_DETAILS))
*************** insert_into_preds_of_block (basic_block
*** 3051,3062 ****
    if (TREE_CODE (type) == COMPLEX_TYPE
        || TREE_CODE (type) == VECTOR_TYPE)
      DECL_GIMPLE_REG_P (temp) = 1;
-   phi = create_phi_node (temp, block);
  
!   gimple_set_plf (phi, NECESSARY, false);
!   VN_INFO_GET (gimple_phi_result (phi))->valnum = gimple_phi_result (phi);
!   VN_INFO (gimple_phi_result (phi))->value_id = val;
!   VEC_safe_push (gimple, heap, inserted_exprs, phi);
    FOR_EACH_EDGE (pred, ei, block->preds)
      {
        pre_expr ae = avail[pred->src->index];
--- 3051,3058 ----
    if (TREE_CODE (type) == COMPLEX_TYPE
        || TREE_CODE (type) == VECTOR_TYPE)
      DECL_GIMPLE_REG_P (temp) = 1;
  
!   phi = create_phi_node (temp, block);
    FOR_EACH_EDGE (pred, ei, block->preds)
      {
        pre_expr ae = avail[pred->src->index];
*************** insert_into_preds_of_block (basic_block
*** 3067,3072 ****
--- 3063,3082 ----
        else
  	add_phi_arg (phi, PRE_EXPR_NAME (avail[pred->src->index]), pred);
      }
+   /* If the PHI node is already available, use it.  */
+   if ((res = vn_phi_lookup (phi)) != NULL_TREE)
+     {
+       gimple_stmt_iterator gsi = gsi_for_stmt (phi);
+       remove_phi_node (&gsi, true);
+       release_defs (phi);
+       add_to_value (val, get_or_alloc_expr_for_name (res));
+       return false;
+     }
+ 
+   gimple_set_plf (phi, NECESSARY, false);
+   VN_INFO_GET (gimple_phi_result (phi))->valnum = gimple_phi_result (phi);
+   VN_INFO (gimple_phi_result (phi))->value_id = val;
+   VEC_safe_push (gimple, heap, inserted_exprs, phi);
  
    newphi = get_or_alloc_expr_for_name (gimple_phi_result (phi));
    add_to_value (val, newphi);
Index: gcc/tree-ssa-sccvn.h
===================================================================
*** gcc/tree-ssa-sccvn.h	(revision 139384)
--- gcc/tree-ssa-sccvn.h	(working copy)
*************** vn_reference_t vn_reference_insert (tree
*** 184,189 ****
--- 184,190 ----
  vn_reference_t vn_reference_insert_pieces (VEC (tree, gc) *,
  					   VEC (vn_reference_op_s, heap) *,
  					   tree, unsigned int);
+ tree vn_phi_lookup (gimple);
  
  hashval_t vn_nary_op_compute_hash (const vn_nary_op_t);
  int vn_nary_op_eq (const void *, const void *);
Index: gcc/tree-ssa-sccvn.c
===================================================================
*** gcc/tree-ssa-sccvn.c	(revision 139384)
--- gcc/tree-ssa-sccvn.c	(working copy)
*************** static VEC(tree, heap) *shared_lookup_ph
*** 1458,1464 ****
     value number if it exists in the hash table.  Return NULL_TREE if
     it does not exist in the hash table. */
  
! static tree
  vn_phi_lookup (gimple phi)
  {
    void **slot;
--- 1458,1464 ----
     value number if it exists in the hash table.  Return NULL_TREE if
     it does not exist in the hash table. */
  
! tree
  vn_phi_lookup (gimple phi)
  {
    void **slot;