From patchwork Fri Sep 8 10:04:34 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Mikael Morin X-Patchwork-Id: 75526 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 404C73858D35 for ; Fri, 8 Sep 2023 10:05:16 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 404C73858D35 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1694167516; bh=xQ/LQxtzBzWElzDH3mybh+3/BUHkBqGfpUxYEcR6+44=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=NbDo9lcVg7kWlCDV7QMzU1dfHY+rnUg2SvJbHuHj89rGlbZuurHGl2rYwy0e+/bbG lmh5GkXP1VLV/SMmT5WuogoborYqiuPdhmjl8NUnOt1bpU8PO7y4diWzYfdT/Z4kuA DhaUdOeTVmyRpyl5b4OKzreT1rbg+NzpPvQPQyCI= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp.smtpout.orange.fr (smtp-22.smtpout.orange.fr [80.12.242.22]) by sourceware.org (Postfix) with ESMTPS id B833D3858D35 for ; Fri, 8 Sep 2023 10:04:43 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org B833D3858D35 Received: from cyrano.home ([86.215.161.51]) by smtp.orange.fr with ESMTPA id eYLqqqpNKLXajeYLyqIz0j; Fri, 08 Sep 2023 12:04:42 +0200 X-ME-Helo: cyrano.home X-ME-Auth: bW9yaW4tbWlrYWVsQG9yYW5nZS5mcg== X-ME-Date: Fri, 08 Sep 2023 12:04:42 +0200 X-ME-IP: 86.215.161.51 To: gcc-patches@gcc.gnu.org, fortran@gcc.gnu.org Subject: [PATCH] fortran: Remove redundant tree walk to delete element Date: Fri, 8 Sep 2023 12:04:34 +0200 Message-Id: <20230908100434.541577-1-mikael@gcc.gnu.org> X-Mailer: git-send-email 2.40.1 MIME-Version: 1.0 X-Spam-Status: No, score=-11.5 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, FORGED_SPF_HELO, GIT_PATCH_0, JMQ_SPF_NEUTRAL, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H5, RCVD_IN_MSPIKE_WL, SPF_HELO_PASS, SPF_NEUTRAL, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Mikael Morin via Gcc-patches From: Mikael Morin Reply-To: Mikael Morin Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "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? -- >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); }