Re: [PATCH] fortran: Remove redundant tree walk to delete element

[Harald Anlauf <anlauf@gmx.de>]

Am 08.09.23 um 12:04 schrieb Mikael Morin via Gcc-patches:
> Hello,
>
> this avoids some redundant work in the symbol deletion code, which is
> used a lot by the parser to cancel statements that fail to match in the
> end.
> I haven't tried to measure the performance effect, if any, on a pathological example;
> just passed the fortran testsuite on x86_64-pc-linux-gnu.
> OK for master?

This is OK.

Thanks,
Harald

> -- >8 --
>
> Remove preliminary walk of the symbol tree when we are about to remove an
> element.  This preliminary walk was necessary because the deletion function
> updated the tree without reporting back to the caller the element it had
> removed.  But knowing that element is necessary to free its memory, so one
> had to first get that element before it was removed from the tree.
>
> This change updates the main deletion function delete_treap and its public
> wrapper gfc_delete_bbt so that the removed element can be known by the
> caller.  This makes the preliminary walk in gfc_delete_symtree redundant,
> permitting its removal.
>
> gcc/fortran/ChangeLog:
>
> 	* bbt.cc (delete_treap): Add argument REMOVED, set it to the removed
> 	element from the tree.  Change NULL to nullptr.
> 	(gfc_delete_bbt): Return the removed element from the tree.
> 	* gfortran.h (gfc_delete_symtree): Remove prototype.
> 	(gfc_delete_bbt): Set return type to pointer.
> 	* symbol.cc (gfc_delete_symtree): Make static.  Get the element to be
> 	freed from the result of gfc_delete_bbt.  Remove the preliminary walk to
> 	get it.
> ---
>   gcc/fortran/bbt.cc     | 27 +++++++++++++++++++--------
>   gcc/fortran/gfortran.h |  3 +--
>   gcc/fortran/symbol.cc  |  6 ++----
>   3 files changed, 22 insertions(+), 14 deletions(-)
>
> diff --git a/gcc/fortran/bbt.cc b/gcc/fortran/bbt.cc
> index 851e5e92c7b..2a032083c5c 100644
> --- a/gcc/fortran/bbt.cc
> +++ b/gcc/fortran/bbt.cc
> @@ -168,31 +168,42 @@ delete_root (gfc_bbt *t)
>      Returns the new root node of the tree.  */
>
>   static gfc_bbt *
> -delete_treap (gfc_bbt *old, gfc_bbt *t, compare_fn compare)
> +delete_treap (gfc_bbt *old, gfc_bbt *t, compare_fn compare, gfc_bbt **removed)
>   {
>     int c;
>
> -  if (t == NULL)
> -    return NULL;
> +  if (t == nullptr)
> +    {
> +      if (removed)
> +	*removed = nullptr;
> +      return nullptr;
> +    }
>
>     c = (*compare) (old, t);
>
>     if (c < 0)
> -    t->left = delete_treap (old, t->left, compare);
> +    t->left = delete_treap (old, t->left, compare, removed);
>     if (c > 0)
> -    t->right = delete_treap (old, t->right, compare);
> +    t->right = delete_treap (old, t->right, compare, removed);
>     if (c == 0)
> -    t = delete_root (t);
> +    {
> +      if (removed)
> +	*removed = t;
> +      t = delete_root (t);
> +    }
>
>     return t;
>   }
>
>
> -void
> +void *
>   gfc_delete_bbt (void *root, void *old, compare_fn compare)
>   {
>     gfc_bbt **t;
> +  gfc_bbt *removed;
>
>     t = (gfc_bbt **) root;
> -  *t = delete_treap ((gfc_bbt *) old, *t, compare);
> +  *t = delete_treap ((gfc_bbt *) old, *t, compare, &removed);
> +
> +  return (void *) removed;
>   }
> diff --git a/gcc/fortran/gfortran.h b/gcc/fortran/gfortran.h
> index b37c6bb9ad4..371f8743312 100644
> --- a/gcc/fortran/gfortran.h
> +++ b/gcc/fortran/gfortran.h
> @@ -3510,7 +3510,6 @@ bool gfc_reference_st_label (gfc_st_label *, gfc_sl_type);
>   gfc_namespace *gfc_get_namespace (gfc_namespace *, int);
>   gfc_symtree *gfc_new_symtree (gfc_symtree **, const char *);
>   gfc_symtree *gfc_find_symtree (gfc_symtree *, const char *);
> -void gfc_delete_symtree (gfc_symtree **, const char *);
>   gfc_symtree *gfc_get_unique_symtree (gfc_namespace *);
>   gfc_user_op *gfc_get_uop (const char *);
>   gfc_user_op *gfc_find_uop (const char *, gfc_namespace *);
> @@ -3911,7 +3910,7 @@ bool gfc_inline_intrinsic_function_p (gfc_expr *);
>   /* bbt.cc */
>   typedef int (*compare_fn) (void *, void *);
>   void gfc_insert_bbt (void *, void *, compare_fn);
> -void gfc_delete_bbt (void *, void *, compare_fn);
> +void * gfc_delete_bbt (void *, void *, compare_fn);
>
>   /* dump-parse-tree.cc */
>   void gfc_dump_parse_tree (gfc_namespace *, FILE *);
> diff --git a/gcc/fortran/symbol.cc b/gcc/fortran/symbol.cc
> index aa3cdc98c86..2cba2ea0bed 100644
> --- a/gcc/fortran/symbol.cc
> +++ b/gcc/fortran/symbol.cc
> @@ -2948,7 +2948,7 @@ gfc_new_symtree (gfc_symtree **root, const char *name)
>
>   /* Delete a symbol from the tree.  Does not free the symbol itself!  */
>
> -void
> +static void
>   gfc_delete_symtree (gfc_symtree **root, const char *name)
>   {
>     gfc_symtree st, *st0;
> @@ -2963,10 +2963,8 @@ gfc_delete_symtree (gfc_symtree **root, const char *name)
>     else
>       p = name;
>
> -  st0 = gfc_find_symtree (*root, p);
> -
>     st.name = gfc_get_string ("%s", p);
> -  gfc_delete_bbt (root, &st, compare_symtree);
> +  st0 = (gfc_symtree *) gfc_delete_bbt (root, &st, compare_symtree);
>
>     free (st0);
>   }