* [PATCH] fortran: Remove redundant tree walk to delete element
@ 2023-09-08 10:04 Mikael Morin
2023-09-08 21:22 ` Harald Anlauf
0 siblings, 1 reply; 3+ messages in thread
From: Mikael Morin @ 2023-09-08 10:04 UTC (permalink / raw)
To: gcc-patches, fortran
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?
-- >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);
}
--
2.40.1
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] fortran: Remove redundant tree walk to delete element
2023-09-08 10:04 [PATCH] fortran: Remove redundant tree walk to delete element Mikael Morin
@ 2023-09-08 21:22 ` Harald Anlauf
2023-09-09 10:44 ` Mikael Morin
0 siblings, 1 reply; 3+ messages in thread
From: Harald Anlauf @ 2023-09-08 21:22 UTC (permalink / raw)
To: Mikael Morin, gcc-patches, fortran
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);
> }
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] fortran: Remove redundant tree walk to delete element
2023-09-08 21:22 ` Harald Anlauf
@ 2023-09-09 10:44 ` Mikael Morin
0 siblings, 0 replies; 3+ messages in thread
From: Mikael Morin @ 2023-09-09 10:44 UTC (permalink / raw)
To: Harald Anlauf, Mikael Morin, gcc-patches, fortran
[-- Attachment #1: Type: text/plain, Size: 555 bytes --]
Le 08/09/2023 à 23:22, Harald Anlauf via Fortran a écrit :
> 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.
I had forgotten function comments.
This is what I have pushed.
[-- Attachment #2: remove-redundant-tree-walk.patch --]
[-- Type: text/x-patch, Size: 5305 bytes --]
From 1ea7130315a14ba4f66c2de76d034b33181812c5 Mon Sep 17 00:00:00 2001
From: Mikael Morin <mikael@gcc.gnu.org>
Date: Sat, 9 Sep 2023 11:45:11 +0200
Subject: [PATCH] fortran: Remove redundant tree walk to delete element
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 | 41 +++++++++++++++++++++++++++++------------
gcc/fortran/gfortran.h | 3 +--
gcc/fortran/symbol.cc | 6 ++----
3 files changed, 32 insertions(+), 18 deletions(-)
diff --git a/gcc/fortran/bbt.cc b/gcc/fortran/bbt.cc
index 851e5e92c7b..7f1f4067fbd 100644
--- a/gcc/fortran/bbt.cc
+++ b/gcc/fortran/bbt.cc
@@ -162,37 +162,54 @@ delete_root (gfc_bbt *t)
}
-/* Delete an element from a tree. The 'old' value does not
- necessarily have to point to the element to be deleted, it must
- just point to a treap structure with the key to be deleted.
- Returns the new root node of the tree. */
+/* Delete an element from a tree, returning the new root node of the tree.
+ The OLD value does not necessarily have to point to the element to be
+ deleted, it must just point to a treap structure with the key to be deleted.
+ The REMOVED argument, if non-null, is set to the removed element from the
+ tree upon return. */
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
+/* Delete the element from the tree at *ROOT that matches the OLD element
+ according to the COMPARE_FN function. This updates the *ROOT pointer to
+ point to the new tree root (if different from the original) and returns the
+ deleted element. */
+
+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);
}
--
2.40.1
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2023-09-09 10:44 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-09-08 10:04 [PATCH] fortran: Remove redundant tree walk to delete element Mikael Morin
2023-09-08 21:22 ` Harald Anlauf
2023-09-09 10:44 ` Mikael Morin
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).