Simplify attempt_builtin_powi logic

This patch gives up on using the reassociation rank algorithm to
correctly place __builtin_powi calls and their feeding multiplies.  In
the end this proved to introduce more complexity than it saved, due in
part to the poor fit of introducing DAG expressions into the
reassociated operand tree.  This patch returns to generating explicit
multiplies to bind the builtin calls together and to the results of the
expression tree rewrite.  I feel this version is smaller, easier to
understand, and less fragile than the existing code.

Bootstrapped and tested on powerpc64-unknown-linux-gnu with no new
regressions.  Ok for trunk?

Thanks,
Bill


2012-05-17  Bill Schmidt  <wschmidt@linux.vnet.ibm.com>

	* tree-ssa-reassoc.c (bip_map): Remove decl.
	(completely_remove_stmt): Remove function.
	(remove_def_if_absorbed_call): Remove function.
	(remove_visited_stmt_chain): Remove __builtin_powi handling.
	(possibly_move_powi): Remove function.
	(rewrite_expr_tree): Remove calls to possibly_move_powi.
	(rewrite_expr_tree_parallel): Likewise.
	(attempt_builtin_powi): Build multiplies explicitly rather than
	relying on the ops vector and rank system.
	(transform_stmt_to_copy): New function.
	(transform_stmt_to_multiply): Likewise.
	(reassociate_bb): Handle leftover operations after __builtin_powi
	optimization; build a final multiply if necessary.

On Thu, 17 May 2012, William J. Schmidt wrote:

> This patch gives up on using the reassociation rank algorithm to
> correctly place __builtin_powi calls and their feeding multiplies.  In
> the end this proved to introduce more complexity than it saved, due in
> part to the poor fit of introducing DAG expressions into the
> reassociated operand tree.  This patch returns to generating explicit
> multiplies to bind the builtin calls together and to the results of the
> expression tree rewrite.  I feel this version is smaller, easier to
> understand, and less fragile than the existing code.
> 
> Bootstrapped and tested on powerpc64-unknown-linux-gnu with no new
> regressions.  Ok for trunk?

Ok.

Thanks,
Richard.

> Thanks,
> Bill
> 
> 
> 2012-05-17  Bill Schmidt  <wschmidt@linux.vnet.ibm.com>
> 
> 	* tree-ssa-reassoc.c (bip_map): Remove decl.
> 	(completely_remove_stmt): Remove function.
> 	(remove_def_if_absorbed_call): Remove function.
> 	(remove_visited_stmt_chain): Remove __builtin_powi handling.
> 	(possibly_move_powi): Remove function.
> 	(rewrite_expr_tree): Remove calls to possibly_move_powi.
> 	(rewrite_expr_tree_parallel): Likewise.
> 	(attempt_builtin_powi): Build multiplies explicitly rather than
> 	relying on the ops vector and rank system.
> 	(transform_stmt_to_copy): New function.
> 	(transform_stmt_to_multiply): Likewise.
> 	(reassociate_bb): Handle leftover operations after __builtin_powi
> 	optimization; build a final multiply if necessary.
> 
> 
> Index: gcc/tree-ssa-reassoc.c
> ===================================================================
> --- gcc/tree-ssa-reassoc.c	(revision 187626)
> +++ gcc/tree-ssa-reassoc.c	(working copy)
> @@ -200,10 +200,6 @@ static long *bb_rank;
>  /* Operand->rank hashtable.  */
>  static struct pointer_map_t *operand_rank;
>  
> -/* Map from inserted __builtin_powi calls to multiply chains that
> -   feed them.  */
> -static struct pointer_map_t *bip_map;
> -
>  /* Forward decls.  */
>  static long get_rank (tree);
>  
> @@ -2184,32 +2180,6 @@ is_phi_for_stmt (gimple stmt, tree operand)
>    return false;
>  }
>  
> -/* Remove STMT, unlink its virtual defs, and release its SSA defs.  */
> -
> -static inline void
> -completely_remove_stmt (gimple stmt)
> -{
> -  gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
> -  gsi_remove (&gsi, true);
> -  unlink_stmt_vdef (stmt);
> -  release_defs (stmt);
> -}
> -
> -/* If OP is defined by a builtin call that has been absorbed by
> -   reassociation, remove its defining statement completely.  */
> -
> -static inline void
> -remove_def_if_absorbed_call (tree op)
> -{
> -  gimple stmt;
> -
> -  if (TREE_CODE (op) == SSA_NAME
> -      && has_zero_uses (op)
> -      && is_gimple_call ((stmt = SSA_NAME_DEF_STMT (op)))
> -      && gimple_visited_p (stmt))
> -    completely_remove_stmt (stmt);
> -}
> -
>  /* Remove def stmt of VAR if VAR has zero uses and recurse
>     on rhs1 operand if so.  */
>  
> @@ -2218,7 +2188,6 @@ remove_visited_stmt_chain (tree var)
>  {
>    gimple stmt;
>    gimple_stmt_iterator gsi;
> -  tree var2;
>  
>    while (1)
>      {
> @@ -2228,95 +2197,15 @@ remove_visited_stmt_chain (tree var)
>        if (is_gimple_assign (stmt) && gimple_visited_p (stmt))
>  	{
>  	  var = gimple_assign_rhs1 (stmt);
> -	  var2 = gimple_assign_rhs2 (stmt);
>  	  gsi = gsi_for_stmt (stmt);
>  	  gsi_remove (&gsi, true);
>  	  release_defs (stmt);
> -	  /* A multiply whose operands are both fed by builtin pow/powi
> -	     calls must check whether to remove rhs2 as well.  */
> -	  remove_def_if_absorbed_call (var2);
>  	}
> -      else if (is_gimple_call (stmt) && gimple_visited_p (stmt))
> -	{
> -	  completely_remove_stmt (stmt);
> -	  return;
> -	}
>        else
>  	return;
>      }
>  }
>  
> -/* If OP is an SSA name, find its definition and determine whether it
> -   is a call to __builtin_powi.  If so, move the definition prior to
> -   STMT.  Only do this during early reassociation.  */
> -
> -static void
> -possibly_move_powi (gimple stmt, tree op)
> -{
> -  gimple stmt2, *mpy;
> -  tree fndecl;
> -  gimple_stmt_iterator gsi1, gsi2;
> -
> -  if (!first_pass_instance
> -      || !flag_unsafe_math_optimizations
> -      || TREE_CODE (op) != SSA_NAME)
> -    return;
> -  
> -  stmt2 = SSA_NAME_DEF_STMT (op);
> -
> -  if (!is_gimple_call (stmt2)
> -      || !has_single_use (gimple_call_lhs (stmt2)))
> -    return;
> -
> -  fndecl = gimple_call_fndecl (stmt2);
> -
> -  if (!fndecl
> -      || DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_NORMAL)
> -    return;
> -
> -  switch (DECL_FUNCTION_CODE (fndecl))
> -    {
> -    CASE_FLT_FN (BUILT_IN_POWI):
> -      break;
> -    default:
> -      return;
> -    }
> -
> -  /* Move the __builtin_powi.  */
> -  gsi1 = gsi_for_stmt (stmt);
> -  gsi2 = gsi_for_stmt (stmt2);
> -  gsi_move_before (&gsi2, &gsi1);
> -
> -  /* See if there are multiplies feeding the __builtin_powi base
> -     argument that must also be moved.  */
> -  while ((mpy = (gimple *) pointer_map_contains (bip_map, stmt2)) != NULL)
> -    {
> -      /* If we've already moved this statement, we're done.  This is
> -         identified by a NULL entry for the statement in bip_map.  */
> -      gimple *next = (gimple *) pointer_map_contains (bip_map, *mpy);
> -      if (next && !*next)
> -	return;
> -
> -      stmt = stmt2;
> -      stmt2 = *mpy;
> -      gsi1 = gsi_for_stmt (stmt);
> -      gsi2 = gsi_for_stmt (stmt2);
> -      gsi_move_before (&gsi2, &gsi1);
> -
> -      /* The moved multiply may be DAG'd from multiple calls if it
> -	 was the result of a cached multiply.  Only move it once.
> -	 Rank order ensures we move it to the right place the first
> -	 time.  */
> -      if (next)
> -	*next = NULL;
> -      else
> -	{
> -	  next = (gimple *) pointer_map_insert (bip_map, *mpy);
> -	  *next = NULL;
> -	}
> -    }
> -}
> -
>  /* This function checks three consequtive operands in
>     passed operands vector OPS starting from OPINDEX and
>     swaps two operands if it is profitable for binary operation
> @@ -2421,9 +2310,6 @@ rewrite_expr_tree (gimple stmt, unsigned int opind
>  	      fprintf (dump_file, " into ");
>  	      print_gimple_stmt (dump_file, stmt, 0, 0);
>  	    }
> -
> -	  possibly_move_powi (stmt, oe1->op);
> -	  possibly_move_powi (stmt, oe2->op);
>  	}
>        return;
>      }
> @@ -2469,8 +2355,6 @@ rewrite_expr_tree (gimple stmt, unsigned int opind
>  	  fprintf (dump_file, " into ");
>  	  print_gimple_stmt (dump_file, stmt, 0, 0);
>  	}
> -
> -      possibly_move_powi (stmt, oe->op);
>      }
>    /* Recurse on the LHS of the binary operator, which is guaranteed to
>       be the non-leaf side.  */
> @@ -2644,9 +2528,6 @@ rewrite_expr_tree_parallel (gimple stmt, int width
>  	  fprintf (dump_file, " into ");
>  	  print_gimple_stmt (dump_file, stmts[i], 0, 0);
>  	}
> -
> -      possibly_move_powi (stmts[i], op1);
> -      possibly_move_powi (stmts[i], op2);
>      }
>  
>    remove_visited_stmt_chain (last_rhs1);
> @@ -3222,11 +3103,10 @@ get_reassoc_pow_ssa_name (tree *target, tree type)
>  
>  /* Look for repeated operands in OPS in the multiply tree rooted at
>     STMT.  Replace them with an optimal sequence of multiplies and powi
> -   builtin calls, and remove the used operands from OPS.  Push new
> -   SSA names onto OPS that represent the introduced multiplies and
> -   builtin calls.  */
> +   builtin calls, and remove the used operands from OPS.  Return an
> +   SSA name representing the value of the replacement sequence.  */
>  
> -static void
> +static tree
>  attempt_builtin_powi (gimple stmt, VEC(operand_entry_t, heap) **ops,
>  		      tree *target)
>  {
> @@ -3235,6 +3115,7 @@ attempt_builtin_powi (gimple stmt, VEC(operand_ent
>    operand_entry_t oe;
>    repeat_factor_t rf1, rf2;
>    repeat_factor rfnew;
> +  tree result = NULL_TREE;
>    tree target_ssa, iter_result;
>    tree type = TREE_TYPE (gimple_get_lhs (stmt));
>    tree powi_fndecl = mathfn_built_in (type, BUILT_IN_POWI);
> @@ -3244,7 +3125,7 @@ attempt_builtin_powi (gimple stmt, VEC(operand_ent
>    /* Nothing to do if BUILT_IN_POWI doesn't exist for this type and
>       target.  */
>    if (!powi_fndecl)
> -    return;
> +    return NULL_TREE;
>  
>    /* Allocate the repeated factor vector.  */
>    repeat_factor_vec = VEC_alloc (repeat_factor, heap, 10);
> @@ -3315,7 +3196,6 @@ attempt_builtin_powi (gimple stmt, VEC(operand_ent
>    while (true)
>      {
>        HOST_WIDE_INT power;
> -      gimple last_mul = NULL;
>  
>        /* First look for the largest cached product of factors from
>  	 preceding iterations.  If found, create a builtin_powi for
> @@ -3353,25 +3233,14 @@ attempt_builtin_powi (gimple stmt, VEC(operand_ent
>  	    }
>  	  else
>  	    {
> -	      gimple *value;
> -
>  	      iter_result = get_reassoc_pow_ssa_name (target, type);
>  	      pow_stmt = gimple_build_call (powi_fndecl, 2, rf1->repr, 
>  					    build_int_cst (integer_type_node,
>  							   power));
>  	      gimple_call_set_lhs (pow_stmt, iter_result);
>  	      gimple_set_location (pow_stmt, gimple_location (stmt));
> -	      /* Temporarily place the call; we will move it and its
> -		 feeding multiplies to the correct place during
> -		 rewrite_expr.  */
>  	      gsi_insert_before (&gsi, pow_stmt, GSI_SAME_STMT);
>  
> -	      if (!operand_equal_p (rf1->repr, rf1->factor, 0))
> -		{
> -		  value = (gimple *) pointer_map_insert (bip_map, pow_stmt);
> -		  *value = SSA_NAME_DEF_STMT (rf1->repr);
> -		}
> -
>  	      if (dump_file && (dump_flags & TDF_DETAILS))
>  		{
>  		  unsigned elt;
> @@ -3457,15 +3326,6 @@ attempt_builtin_powi (gimple stmt, VEC(operand_ent
>  		  gsi_insert_before (&gsi, mul_stmt, GSI_SAME_STMT);
>  		  rf1->repr = target_ssa;
>  
> -		  /* Chain multiplies together for later movement.  */
> -		  if (last_mul)
> -		    {
> -		      gimple *value
> -			= (gimple *) pointer_map_insert (bip_map, mul_stmt);
> -		      *value = last_mul;
> -		    }
> -		  last_mul = mul_stmt;
> -
>  		  /* Don't reprocess the multiply we just introduced.  */
>  		  gimple_set_visited (mul_stmt, true);
>  		}
> @@ -3481,20 +3341,23 @@ attempt_builtin_powi (gimple stmt, VEC(operand_ent
>  	  gimple_call_set_lhs (pow_stmt, iter_result);
>  	  gimple_set_location (pow_stmt, gimple_location (stmt));
>  	  gsi_insert_before (&gsi, pow_stmt, GSI_SAME_STMT);
> +	}
>  
> -	  /* If we inserted a chain of multiplies before the pow_stmt,
> -	     record that fact so we can move it later when we move the
> -	     pow_stmt.  */
> -	  if (last_mul)
> -	    {
> -	      gimple *value = (gimple *) pointer_map_insert (bip_map, pow_stmt);
> -	      *value = last_mul;
> -	    }
> +      /* If we previously formed at least one other builtin_powi call,
> +	 form the product of this one and those others.  */
> +      if (result)
> +	{
> +	  tree new_result = get_reassoc_pow_ssa_name (target, type);
> +	  mul_stmt = gimple_build_assign_with_ops (MULT_EXPR, new_result,
> +						   result, iter_result);
> +	  gimple_set_location (mul_stmt, gimple_location (stmt));
> +	  gsi_insert_before (&gsi, mul_stmt, GSI_SAME_STMT);
> +	  gimple_set_visited (mul_stmt, true);
> +	  result = new_result;
>  	}
> +      else
> +	result = iter_result;
>  
> -      /* Append the result of this iteration to the ops vector.  */
> -      add_to_ops_vec (ops, iter_result);
> -
>        /* Decrement the occurrence count of each element in the product
>  	 by the count found above, and remove this many copies of each
>  	 factor from OPS.  */
> @@ -3534,8 +3397,61 @@ attempt_builtin_powi (gimple stmt, VEC(operand_ent
>       clean up.  */
>    VEC_qsort (operand_entry_t, *ops, sort_by_operand_rank);
>    VEC_free (repeat_factor, heap, repeat_factor_vec);
> +
> +  /* Return the final product computed herein.  Note that there may
> +     still be some elements with single occurrence count left in OPS;
> +     those will be handled by the normal reassociation logic.  */
> +  return result;
>  }
>  
> +/* Transform STMT at *GSI into a copy by replacing its rhs with NEW_RHS.  */
> +
> +static void
> +transform_stmt_to_copy (gimple_stmt_iterator *gsi, gimple stmt, tree new_rhs)
> +{
> +  tree rhs1;
> +
> +  if (dump_file && (dump_flags & TDF_DETAILS))
> +    {
> +      fprintf (dump_file, "Transforming ");
> +      print_gimple_stmt (dump_file, stmt, 0, 0);
> +    }
> +
> +  rhs1 = gimple_assign_rhs1 (stmt);
> +  gimple_assign_set_rhs_from_tree (gsi, new_rhs);
> +  update_stmt (stmt);
> +  remove_visited_stmt_chain (rhs1);
> +
> +  if (dump_file && (dump_flags & TDF_DETAILS))
> +    {
> +      fprintf (dump_file, " into ");
> +      print_gimple_stmt (dump_file, stmt, 0, 0);
> +    }
> +}
> +
> +/* Transform STMT at *GSI into a multiply of RHS1 and RHS2.  */
> +
> +static void
> +transform_stmt_to_multiply (gimple_stmt_iterator *gsi, gimple stmt,
> +			    tree rhs1, tree rhs2)
> +{
> +  if (dump_file && (dump_flags & TDF_DETAILS))
> +    {
> +      fprintf (dump_file, "Transforming ");
> +      print_gimple_stmt (dump_file, stmt, 0, 0);
> +    }
> +
> +  gimple_assign_set_rhs_with_ops_1 (gsi, MULT_EXPR, rhs1, rhs2, NULL_TREE);
> +  update_stmt (gsi_stmt (*gsi));
> +  remove_visited_stmt_chain (rhs1);
> +
> +  if (dump_file && (dump_flags & TDF_DETAILS))
> +    {
> +      fprintf (dump_file, " into ");
> +      print_gimple_stmt (dump_file, stmt, 0, 0);
> +    }
> +}
> +
>  /* Reassociate expressions in basic block BB and its post-dominator as
>     children.  */
>  
> @@ -3606,7 +3522,7 @@ reassociate_bb (basic_block bb)
>  	  if (associative_tree_code (rhs_code))
>  	    {
>  	      VEC(operand_entry_t, heap) *ops = NULL;
> -	      bip_map = pointer_map_create ();
> +	      tree powi_result = NULL_TREE;
>  
>  	      /* There may be no immediate uses left by the time we
>  		 get here because we may have eliminated them all.  */
> @@ -3630,28 +3546,21 @@ reassociate_bb (basic_block bb)
>  	      if (first_pass_instance
>  		  && rhs_code == MULT_EXPR
>  		  && flag_unsafe_math_optimizations)
> -		attempt_builtin_powi (stmt, &ops, &target);
> +		powi_result = attempt_builtin_powi (stmt, &ops, &target);
>  
> -	      if (VEC_length (operand_entry_t, ops) == 1)
> +	      /* If the operand vector is now empty, all operands were 
> +		 consumed by the __builtin_powi optimization.  */
> +	      if (VEC_length (operand_entry_t, ops) == 0)
> +		transform_stmt_to_copy (&gsi, stmt, powi_result);
> +	      else if (VEC_length (operand_entry_t, ops) == 1)
>  		{
> -		  if (dump_file && (dump_flags & TDF_DETAILS))
> -		    {
> -		      fprintf (dump_file, "Transforming ");
> -		      print_gimple_stmt (dump_file, stmt, 0, 0);
> -		    }
> -
> -		  rhs1 = gimple_assign_rhs1 (stmt);
> -		  gimple_assign_set_rhs_from_tree (&gsi,
> -						   VEC_last (operand_entry_t,
> -							     ops)->op);
> -		  update_stmt (stmt);
> -		  remove_visited_stmt_chain (rhs1);
> -
> -		  if (dump_file && (dump_flags & TDF_DETAILS))
> -		    {
> -		      fprintf (dump_file, " into ");
> -		      print_gimple_stmt (dump_file, stmt, 0, 0);
> -		    }
> +		  tree last_op = VEC_last (operand_entry_t, ops)->op;
> +		  
> +		  if (powi_result)
> +		    transform_stmt_to_multiply (&gsi, stmt, last_op,
> +						powi_result);
> +		  else
> +		    transform_stmt_to_copy (&gsi, stmt, last_op);
>  		}
>  	      else
>  		{
> @@ -3668,10 +3577,27 @@ reassociate_bb (basic_block bb)
>  		    rewrite_expr_tree_parallel (stmt, width, ops);
>  		  else
>  		    rewrite_expr_tree (stmt, 0, ops, false);
> +
> +		  /* If we combined some repeated factors into a 
> +		     __builtin_powi call, multiply that result by the
> +		     reassociated operands.  */
> +		  if (powi_result)
> +		    {
> +		      gimple mul_stmt;
> +		      tree type = TREE_TYPE (gimple_get_lhs (stmt));
> +		      tree target_ssa = get_reassoc_pow_ssa_name (&target,
> +								  type);
> +		      gimple_set_lhs (stmt, target_ssa);
> +		      update_stmt (stmt);
> +		      mul_stmt = gimple_build_assign_with_ops (MULT_EXPR, lhs,
> +							       powi_result,
> +							       target_ssa);
> +		      gimple_set_location (mul_stmt, gimple_location (stmt));
> +		      gsi_insert_after (&gsi, mul_stmt, GSI_NEW_STMT);
> +		    }
>  		}
>  
>  	      VEC_free (operand_entry_t, heap, ops);
> -	      pointer_map_destroy (bip_map);
>  	    }
>  	}
>      }
> 
> 
>