[PATCH] Improve overhead of tree-affine.c a bit

[PATCH] Improve overhead of tree-affine.c a bit

[Richard Biener]

When working on PR63184 I noticed that tree-affine.c is still one of
the gimple_assign_rhs_to_tree callers and does so quite aggressively
for no good reason.  The following restricts it to the cases we
handle in tree_to_aff_combination, axing one unreachable case.
It also makes sure to cache expanded combinations with SSA names
as keys rather than a GENERIC conversion tree which isn't shared
anyways.

Bootstrapped and tested on x86_64-unknown-linux-gnu, object files
in gcc/ are the same patched/unpatched with the exception of
tree-affine.o.

Applied to trunk.

Richard.

2018-12-10  Richard Biener  <rguenther@suse.de>

	* tree-affine.c (tree_to_aff_combination): Remove unreachable
	MEM_REF case.
	(aff_combination_expand): Cache on SSA names, not possibly
	on conversion trees.  Avoid expanding cases we do not handle.

diff --git a/gcc/tree-affine.c b/gcc/tree-affine.c
index 96b479dfc4c..41c52ab468d 100644
--- a/gcc/tree-affine.c
+++ b/gcc/tree-affine.c
@@ -351,6 +351,7 @@ tree_to_aff_combination (tree expr, tree type, aff_tree *comb)
       return;
 
     case MEM_REF:
+      gcc_unreachable ();
       if (TREE_CODE (TREE_OPERAND (expr, 0)) == ADDR_EXPR)
 	tree_to_aff_combination (TREE_OPERAND (TREE_OPERAND (expr, 0), 0),
 				 type, comb);
@@ -721,21 +722,39 @@ aff_combination_expand (aff_tree *comb ATTRIBUTE_UNUSED,
       if (TREE_CODE_CLASS (code) == tcc_reference)
 	continue;
 
-      if (!*cache)
-	*cache = new hash_map<tree, name_expansion *>;
-      name_expansion **slot = &(*cache)->get_or_insert (e);
-      exp = *slot;
-
+      name_expansion **slot = NULL;
+      if (*cache)
+	slot = (*cache)->get (name);
+      exp = slot ? *slot : NULL;
       if (!exp)
 	{
+	  /* Only bother to handle cases tree_to_aff_combination will.  */
+	  switch (code)
+	    {
+	    case POINTER_PLUS_EXPR:
+	    case PLUS_EXPR:
+	    case MINUS_EXPR:
+	    case MULT_EXPR:
+	    case NEGATE_EXPR:
+	    case BIT_NOT_EXPR:
+	    CASE_CONVERT:
+	      rhs = gimple_assign_rhs_to_tree (def);
+	      break;
+	    case ADDR_EXPR:
+	    case INTEGER_CST:
+	    case POLY_INT_CST:
+	      rhs = gimple_assign_rhs1 (def);
+	      break;
+	    default:
+	      continue;
+	    }
+	  tree_to_aff_combination (rhs, TREE_TYPE (name), &current);
 	  exp = XNEW (struct name_expansion);
 	  exp->in_progress = 1;
-	  *slot = exp;
-	  rhs = gimple_assign_rhs_to_tree (def);
-	  if (e != name)
-	    rhs = fold_convert (type, rhs);
-
-	  tree_to_aff_combination_expand (rhs, comb->type, &current, cache);
+	  if (!*cache)
+	    *cache = new hash_map<tree, name_expansion *>;
+	  (*cache)->put (name, exp);
+	  aff_combination_expand (&current, cache);
 	  exp->expansion = current;
 	  exp->in_progress = 0;
 	}
@@ -746,6 +765,8 @@ aff_combination_expand (aff_tree *comb ATTRIBUTE_UNUSED,
 	  gcc_assert (!exp->in_progress);
 	  current = exp->expansion;
 	}
+      if (!useless_type_conversion_p (comb->type, current.type))
+	aff_combination_convert (&current, comb->type);
 
       /* Accumulate the new terms to TO_ADD, so that we do not modify
 	 COMB while traversing it; include the term -coef * E, to remove

Re: [PATCH] Improve overhead of tree-affine.c a bit

[Kyrill Tkachov]

Hi Richard,

On 10/12/18 13:44, Richard Biener wrote:
>
> When working on PR63184 I noticed that tree-affine.c is still one of
> the gimple_assign_rhs_to_tree callers and does so quite aggressively
> for no good reason.  The following restricts it to the cases we
> handle in tree_to_aff_combination, axing one unreachable case.
> It also makes sure to cache expanded combinations with SSA names
> as keys rather than a GENERIC conversion tree which isn't shared
> anyways.
>
> Bootstrapped and tested on x86_64-unknown-linux-gnu, object files
> in gcc/ are the same patched/unpatched with the exception of
> tree-affine.o.
>
> Applied to trunk.
>
> Richard.
>
> 2018-12-10  Richard Biener  <rguenther@suse.de>
>
>         * tree-affine.c (tree_to_aff_combination): Remove unreachable
>         MEM_REF case.
>         (aff_combination_expand): Cache on SSA names, not possibly
>         on conversion trees.  Avoid expanding cases we do not handle.
>
> diff --git a/gcc/tree-affine.c b/gcc/tree-affine.c
> index 96b479dfc4c..41c52ab468d 100644
> --- a/gcc/tree-affine.c
> +++ b/gcc/tree-affine.c
> @@ -351,6 +351,7 @@ tree_to_aff_combination (tree expr, tree type, aff_tree *comb)
>        return;
>
>      case MEM_REF:
> +      gcc_unreachable ();
>        if (TREE_CODE (TREE_OPERAND (expr, 0)) == ADDR_EXPR)
>          tree_to_aff_combination (TREE_OPERAND (TREE_OPERAND (expr, 0), 0),
>                                   type, comb);

The code after the gcc_unreachable is now dead and can be removed?

Thanks,
Kyrill

> @@ -721,21 +722,39 @@ aff_combination_expand (aff_tree *comb ATTRIBUTE_UNUSED,
>        if (TREE_CODE_CLASS (code) == tcc_reference)
>          continue;
>
> -      if (!*cache)
> -       *cache = new hash_map<tree, name_expansion *>;
> -      name_expansion **slot = &(*cache)->get_or_insert (e);
> -      exp = *slot;
> -
> +      name_expansion **slot = NULL;
> +      if (*cache)
> +       slot = (*cache)->get (name);
> +      exp = slot ? *slot : NULL;
>        if (!exp)
>          {
> +         /* Only bother to handle cases tree_to_aff_combination will.  */
> +         switch (code)
> +           {
> +           case POINTER_PLUS_EXPR:
> +           case PLUS_EXPR:
> +           case MINUS_EXPR:
> +           case MULT_EXPR:
> +           case NEGATE_EXPR:
> +           case BIT_NOT_EXPR:
> +           CASE_CONVERT:
> +             rhs = gimple_assign_rhs_to_tree (def);
> +             break;
> +           case ADDR_EXPR:
> +           case INTEGER_CST:
> +           case POLY_INT_CST:
> +             rhs = gimple_assign_rhs1 (def);
> +             break;
> +           default:
> +             continue;
> +           }
> +         tree_to_aff_combination (rhs, TREE_TYPE (name), &current);
>            exp = XNEW (struct name_expansion);
>            exp->in_progress = 1;
> -         *slot = exp;
> -         rhs = gimple_assign_rhs_to_tree (def);
> -         if (e != name)
> -           rhs = fold_convert (type, rhs);
> -
> -         tree_to_aff_combination_expand (rhs, comb->type, &current, cache);
> +         if (!*cache)
> +           *cache = new hash_map<tree, name_expansion *>;
> +         (*cache)->put (name, exp);
> +         aff_combination_expand (&current, cache);
>            exp->expansion = current;
>            exp->in_progress = 0;
>          }
> @@ -746,6 +765,8 @@ aff_combination_expand (aff_tree *comb ATTRIBUTE_UNUSED,
>            gcc_assert (!exp->in_progress);
>            current = exp->expansion;
>          }
> +      if (!useless_type_conversion_p (comb->type, current.type))
> +       aff_combination_convert (&current, comb->type);
>
>        /* Accumulate the new terms to TO_ADD, so that we do not modify
>           COMB while traversing it; include the term -coef * E, to remove

Re: [PATCH] Improve overhead of tree-affine.c a bit

[Richard Biener]

On Mon, 10 Dec 2018, Kyrill Tkachov wrote:

> Hi Richard,
> 
> On 10/12/18 13:44, Richard Biener wrote:
> > 
> > When working on PR63184 I noticed that tree-affine.c is still one of
> > the gimple_assign_rhs_to_tree callers and does so quite aggressively
> > for no good reason.  The following restricts it to the cases we
> > handle in tree_to_aff_combination, axing one unreachable case.
> > It also makes sure to cache expanded combinations with SSA names
> > as keys rather than a GENERIC conversion tree which isn't shared
> > anyways.
> > 
> > Bootstrapped and tested on x86_64-unknown-linux-gnu, object files
> > in gcc/ are the same patched/unpatched with the exception of
> > tree-affine.o.
> > 
> > Applied to trunk.
> > 
> > Richard.
> > 
> > 2018-12-10  Richard Biener  <rguenther@suse.de>
> > 
> >         * tree-affine.c (tree_to_aff_combination): Remove unreachable
> >         MEM_REF case.
> >         (aff_combination_expand): Cache on SSA names, not possibly
> >         on conversion trees.  Avoid expanding cases we do not handle.
> > 
> > diff --git a/gcc/tree-affine.c b/gcc/tree-affine.c
> > index 96b479dfc4c..41c52ab468d 100644
> > --- a/gcc/tree-affine.c
> > +++ b/gcc/tree-affine.c
> > @@ -351,6 +351,7 @@ tree_to_aff_combination (tree expr, tree type, aff_tree
> > *comb)
> >        return;
> > 
> >      case MEM_REF:
> > +      gcc_unreachable ();
> >        if (TREE_CODE (TREE_OPERAND (expr, 0)) == ADDR_EXPR)
> >          tree_to_aff_combination (TREE_OPERAND (TREE_OPERAND (expr, 0), 0),
> >                                   type, comb);
> 
> The code after the gcc_unreachable is now dead and can be removed?

Yes, sorry - that is what I committed, the above is what I tested.

Richard.

> Thanks,
> Kyrill
> 
> > @@ -721,21 +722,39 @@ aff_combination_expand (aff_tree *comb
> > ATTRIBUTE_UNUSED,
> >        if (TREE_CODE_CLASS (code) == tcc_reference)
> >          continue;
> > 
> > -      if (!*cache)
> > -       *cache = new hash_map<tree, name_expansion *>;
> > -      name_expansion **slot = &(*cache)->get_or_insert (e);
> > -      exp = *slot;
> > -
> > +      name_expansion **slot = NULL;
> > +      if (*cache)
> > +       slot = (*cache)->get (name);
> > +      exp = slot ? *slot : NULL;
> >        if (!exp)
> >          {
> > +         /* Only bother to handle cases tree_to_aff_combination will.  */
> > +         switch (code)
> > +           {
> > +           case POINTER_PLUS_EXPR:
> > +           case PLUS_EXPR:
> > +           case MINUS_EXPR:
> > +           case MULT_EXPR:
> > +           case NEGATE_EXPR:
> > +           case BIT_NOT_EXPR:
> > +           CASE_CONVERT:
> > +             rhs = gimple_assign_rhs_to_tree (def);
> > +             break;
> > +           case ADDR_EXPR:
> > +           case INTEGER_CST:
> > +           case POLY_INT_CST:
> > +             rhs = gimple_assign_rhs1 (def);
> > +             break;
> > +           default:
> > +             continue;
> > +           }
> > +         tree_to_aff_combination (rhs, TREE_TYPE (name), &current);
> >            exp = XNEW (struct name_expansion);
> >            exp->in_progress = 1;
> > -         *slot = exp;
> > -         rhs = gimple_assign_rhs_to_tree (def);
> > -         if (e != name)
> > -           rhs = fold_convert (type, rhs);
> > -
> > -         tree_to_aff_combination_expand (rhs, comb->type, &current, cache);
> > +         if (!*cache)
> > +           *cache = new hash_map<tree, name_expansion *>;
> > +         (*cache)->put (name, exp);
> > +         aff_combination_expand (&current, cache);
> >            exp->expansion = current;
> >            exp->in_progress = 0;
> >          }
> > @@ -746,6 +765,8 @@ aff_combination_expand (aff_tree *comb ATTRIBUTE_UNUSED,
> >            gcc_assert (!exp->in_progress);
> >            current = exp->expansion;
> >          }
> > +      if (!useless_type_conversion_p (comb->type, current.type))
> > +       aff_combination_convert (&current, comb->type);
> > 
> >        /* Accumulate the new terms to TO_ADD, so that we do not modify
> >           COMB while traversing it; include the term -coef * E, to remove
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)