Avoid inserting dead code in PRE, do less work

The following patch tries to work towards fixing PR62291 by moving
NEW_SETS/AVAIL_OUT adding strictly to insert_into_preds_of_block
and the value / expression we wanted to insert.  If doing that for
other unrelated expressions this may cause fake partial
redundancies to be detected and dead code will be inserted such
as for gcc.dg/tree-ssa/ssa-pre-28.c which is now fixed.

The idea is that we could now "simulate" insertion and its recursion
without actually performing the insertions (which requires AVAIL_OUT)
and instead postpone that to elimination time.

Well.  Idea...

Bootstrap and regtest running on x86_64-unknown-linux-gnu.

Richard.

2014-09-01  Richard Biener  <rguenther@suse.de>

	* tree-ssa-pre.c (find_or_generate_expression): Expand comment.
	(create_expression_by_pieces): Do not add to NEW_SETS or
	AVAIL_OUT here.
	(insert_into_preds_of_block): Instead do it here and only
	for the partial redundant value we inserted.

On Mon, 1 Sep 2014, Richard Biener wrote:

> 
> The following patch tries to work towards fixing PR62291 by moving
> NEW_SETS/AVAIL_OUT adding strictly to insert_into_preds_of_block
> and the value / expression we wanted to insert.  If doing that for
> other unrelated expressions this may cause fake partial
> redundancies to be detected and dead code will be inserted such
> as for gcc.dg/tree-ssa/ssa-pre-28.c which is now fixed.
> 
> The idea is that we could now "simulate" insertion and its recursion
> without actually performing the insertions (which requires AVAIL_OUT)
> and instead postpone that to elimination time.
> 
> Well.  Idea...
> 
> Bootstrap and regtest running on x86_64-unknown-linux-gnu.

So this doesn't work (it wrecks gcc.c-torture/compile/pr43415.c
which endlessly inserts via find_or_generate_expression).

Which get's me back to the point that find_or_generate_expression
isn't a good implementation to fix PR37997 (gcc.dg/tree-ssa/ssa-pre-28.c).

Anyway, I'll put this patch on hold (though I certainly would like
to remove that PR37997-fixing code ...).

Richard.

> Richard.
> 
> 2014-09-01  Richard Biener  <rguenther@suse.de>
> 
> 	* tree-ssa-pre.c (find_or_generate_expression): Expand comment.
> 	(create_expression_by_pieces): Do not add to NEW_SETS or
> 	AVAIL_OUT here.
> 	(insert_into_preds_of_block): Instead do it here and only
> 	for the partial redundant value we inserted.
> 
> Index: gcc/tree-ssa-pre.c
> ===================================================================
> --- gcc/tree-ssa-pre.c	(revision 214795)
> +++ gcc/tree-ssa-pre.c	(working copy)
> @@ -2797,9 +2797,11 @@ find_or_generate_expression (basic_block
>        return NULL_TREE;
>      }
>  
> -  /* It must be a complex expression, so generate it recursively.  Note
> -     that this is only necessary to handle gcc.dg/tree-ssa/ssa-pre28.c
> -     where the insert algorithm fails to insert a required expression.  */
> +  /* It must be a complex expression, so generate it recursively.
> +     Note that this is only necessary to handle cases like
> +     gcc.dg/tree-ssa/ssa-pre-28.c where the insert algorithm fails to
> +     insert a required expression because the dependent expression
> +     isn't partially redundant.  */
>    bitmap exprset = value_expressions[lookfor];
>    bitmap_iterator bi;
>    unsigned int i;
> @@ -2846,7 +2848,6 @@ create_expression_by_pieces (basic_block
>    unsigned int value_id;
>    gimple_stmt_iterator gsi;
>    tree exprtype = type ? type : get_expr_type (expr);
> -  pre_expr nameexpr;
>    gimple newstmt;
>  
>    switch (expr->kind)
> @@ -2941,17 +2942,12 @@ create_expression_by_pieces (basic_block
>  	{
>  	  gimple stmt = gsi_stmt (gsi);
>  	  tree forcedname = gimple_get_lhs (stmt);
> -	  pre_expr nameexpr;
>  
>  	  if (TREE_CODE (forcedname) == SSA_NAME)
>  	    {
>  	      bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (forcedname));
>  	      VN_INFO_GET (forcedname)->valnum = forcedname;
>  	      VN_INFO (forcedname)->value_id = get_next_value_id ();
> -	      nameexpr = get_or_alloc_expr_for_name (forcedname);
> -	      add_to_value (VN_INFO (forcedname)->value_id, nameexpr);
> -	      bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
> -	      bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
>  	    }
>  	}
>        gimple_seq_add_seq (stmts, forced_stmts);
> @@ -2979,12 +2975,6 @@ create_expression_by_pieces (basic_block
>    VN_INFO (name)->valnum = sccvn_valnum_from_value_id (value_id);
>    if (VN_INFO (name)->valnum == NULL_TREE)
>      VN_INFO (name)->valnum = name;
> -  gcc_assert (VN_INFO (name)->valnum != NULL_TREE);
> -  nameexpr = get_or_alloc_expr_for_name (name);
> -  add_to_value (value_id, nameexpr);
> -  if (NEW_SETS (block))
> -    bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
> -  bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
>  
>    pre_stats.insertions++;
>    if (dump_file && (dump_flags & TDF_DETAILS))
> @@ -3061,7 +3051,11 @@ insert_into_preds_of_block (basic_block
>  	      nophi = true;
>  	      continue;
>  	    }
> -	  avail[pred->dest_idx] = get_or_alloc_expr_for_name (builtexpr);
> +	  pre_expr nameexpr = get_or_alloc_expr_for_name (builtexpr);
> +	  avail[pred->dest_idx] = nameexpr;
> +	  add_to_value (get_expr_value_id (eprime), nameexpr);
> +	  bitmap_value_replace_in_set (NEW_SETS (bprime), nameexpr);
> +	  bitmap_value_replace_in_set (AVAIL_OUT (bprime), nameexpr);
>  	  insertions = true;
>  	}
>        else if (eprime->kind == CONSTANT)
> 
> Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-28.c
> ===================================================================
> --- gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-28.c	(revision 214795)
> +++ gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-28.c	(working copy)
> @@ -15,7 +15,13 @@ int foo (int i, int b, int result)
>  }
>  
>  /* We should insert i + 1 into the if (b) path as well as the simplified
> -   i + 1 & -2 expression.  And do replacement with two PHI temps.  */
> +   i + 1 & -2 expression.  And do replacement of the partially
> +   redundant result & mask with one PHI temps.  In particular we
> +   should avoid inserting i + 1 into the if (!b) path during
> +   insert iteration 2.  */
>  
> -/* { dg-final { scan-tree-dump-times "with prephitmp" 2 "pre" } } */
> +/* { dg-final { scan-tree-dump-times "Inserted pretmp" 2 "pre" } } */
> +/* { dg-final { scan-tree-dump-times "Created phi prephitmp" 1 "pre" } } */
> +/* { dg-final { scan-tree-dump-times "with prephitmp" 1 "pre" } } */
> +/* { dg-final { scan-tree-dump-times "Starting insert iteration" 2 "pre" } } */
>  /* { dg-final { cleanup-tree-dump "pre" } } */
>