From patchwork Thu Aug 29 09:04:15 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Martin Jambor X-Patchwork-Id: 1155105 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-507908-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=suse.cz Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="vokfLpwB"; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 46JxWH0tt7z9sDB for ; Thu, 29 Aug 2019 19:04:26 +1000 (AEST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:subject:date:message-id:mime-version:content-type; q=dns; s=default; b=CwwkhFIiSJhX3pvxOc3cO+J/RK9NT1yNTBAaSZUvbTDySXtrM1 ZfGMxt/dYZVla7Yu5WQNSii/9nYBfMTlRoidoUGuQKcIdkEUsvFrqbgbNI5cQ4wF 5hqMiu/D7nOAPq1LOezPGui8PAnqpJe+ejL5R+lhXEBu5GbeW9jtLE9fg= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:subject:date:message-id:mime-version:content-type; s= default; bh=Y6DIimGJyJlDdphSfQHjW1YXiKQ=; b=vokfLpwBR3xjX8+U8FiZ L++oMnt+KmR3TC7n0JcINkIYgL6t41xFlwsww8mDjfrahi6MzjyQqqHCfpuBhJjK AL5jYl9EBPV2e2jF5rHfwbkvQ5PyMXtir7f8VoEVPfO3UhcfiMnFP6K7K7a6U25z TRN+/1UMXQPl7zzHSBth3p4= Received: (qmail 20975 invoked by alias); 29 Aug 2019 09:04:19 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 20774 invoked by uid 89); 29 Aug 2019 09:04:19 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-19.3 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, SPF_PASS autolearn=ham version=3.3.1 spammy= X-HELO: mx1.suse.de Received: from mx2.suse.de (HELO mx1.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 29 Aug 2019 09:04:17 +0000 Received: from relay2.suse.de (unknown [195.135.220.254]) by mx1.suse.de (Postfix) with ESMTP id 5E294B04C for ; Thu, 29 Aug 2019 09:04:15 +0000 (UTC) From: Martin Jambor To: GCC Patches Cc: Subject: [PR 91579] Avoid creating redundant PHI nodes in tail-call pass User-Agent: Notmuch/0.29.1 (https://notmuchmail.org) Emacs/26.2 (x86_64-suse-linux-gnu) Date: Thu, 29 Aug 2019 11:04:15 +0200 Message-ID: MIME-Version: 1.0 X-IsSubscribed: yes Hi, when turning a tail-recursive call into a loop, the tail-call pass creates a phi node for each gimple_reg function parameter that has any use at all, even when the value passed to the original call is the same as the received one, when it is the parameter's default definition. This results in a redundant phi node in which one argument is the default definition and all others are the LHS of the same phi node. See the Bugzilla entry for an example. These phi nodes in turn confuses ipa-prop.c which cannot skip them and may not create a pass-through jump function when it should. Fixed by the following patch which just adds a bitmap to remember where there are non-default-defs passed to a tail-recursive call and then creates phi nodes only for such parameters. It has passed bootstrap and testing on x86_64-linux. OK for trunk? Martin 2019-08-28 Martin Jambor tree-optimization/91579 * tree-tailcall.c (tailr_non_ddef_args): New variable. (find_tail_calls): Allocate tailr_non_ddef_args and set its bits as appropriate. (arg_needs_copy_p): New parameter idx. Also check tailr_non_ddef_args. (tree_optimize_tail_calls_1): Free tailr_non_ddef_args. testsuite/ * gcc.dg/tree-ssa/pr91579.c: New test. --- gcc/testsuite/gcc.dg/tree-ssa/pr91579.c | 22 ++++++++++++++ gcc/tree-tailcall.c | 38 +++++++++++++++++++------ 2 files changed, 52 insertions(+), 8 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr91579.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr91579.c b/gcc/testsuite/gcc.dg/tree-ssa/pr91579.c new file mode 100644 index 00000000000..ee752be1a85 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr91579.c @@ -0,0 +1,22 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-tailr1" } */ + +typedef long unsigned int size_t; +typedef int (*compare_t)(const void *, const void *); + +int partition (void *base, size_t nmemb, size_t size, compare_t cmp); + +void +my_qsort (void *base, size_t nmemb, size_t size, compare_t cmp) +{ + int pt; + if (nmemb > 1) + { + pt = partition (base, nmemb, size, cmp); + my_qsort (base, pt + 1, size, cmp); + my_qsort ((void*)((char*) base + (pt + 1) * size), + nmemb - pt - 1, size, cmp); + } +} + +/* { dg-final { scan-tree-dump-not "cmp\[^\r\n\]*PHI" "tailr1" } } */ diff --git a/gcc/tree-tailcall.c b/gcc/tree-tailcall.c index a4b563efd73..23d60f492da 100644 --- a/gcc/tree-tailcall.c +++ b/gcc/tree-tailcall.c @@ -126,6 +126,13 @@ struct tailcall accumulator. */ static tree m_acc, a_acc; +/* Bitmap with a bit for each function parameter which is set to true if in a + tail-recursion we pass to the actual argument something else than the + default definition of the corresponding formal parameter. It has no meaning + for non-gimple-register parameters. */ + +static bitmap tailr_non_ddef_args; + static bool optimize_tail_call (struct tailcall *, bool); static void eliminate_tail_call (struct tailcall *); @@ -727,6 +734,17 @@ find_tail_calls (basic_block bb, struct tailcall **ret) gimple_stmt_iterator mgsi = gsi_for_stmt (stmt); gsi_move_before (&mgsi, &gsi); } + if (!tailr_non_ddef_args) + tailr_non_ddef_args = BITMAP_ALLOC (NULL); + for (param = DECL_ARGUMENTS (current_function_decl), idx = 0; + param; + param = DECL_CHAIN (param), idx++) + { + tree arg = gimple_call_arg (call, idx); + if (is_gimple_reg (param) + && (arg != ssa_default_def (cfun, param))) + bitmap_set_bit (tailr_non_ddef_args, idx); + } } nw = XNEW (struct tailcall); @@ -905,11 +923,11 @@ decrease_profile (basic_block bb, profile_count count) } } -/* Returns true if argument PARAM of the tail recursive call needs to be copied - when the call is eliminated. */ +/* Returns true if PARAM, which is the IDX-th argument of the tail recursively + called function, needs to be copied when the call is eliminated. */ static bool -arg_needs_copy_p (tree param) +arg_needs_copy_p (tree param, unsigned idx) { tree def; @@ -918,7 +936,7 @@ arg_needs_copy_p (tree param) /* Parameters that are only defined but never used need not be copied. */ def = ssa_default_def (cfun, param); - if (!def) + if (!def || !bitmap_bit_p (tailr_non_ddef_args, idx)) return false; return true; @@ -1005,7 +1023,7 @@ eliminate_tail_call (struct tailcall *t) param; param = DECL_CHAIN (param), idx++) { - if (!arg_needs_copy_p (param)) + if (!arg_needs_copy_p (param, idx)) continue; arg = gimple_call_arg (stmt, idx); @@ -1139,10 +1157,11 @@ tree_optimize_tail_calls_1 (bool opt_tailcalls) split_edge (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun))); /* Copy the args if needed. */ - for (param = DECL_ARGUMENTS (current_function_decl); + unsigned idx; + for (param = DECL_ARGUMENTS (current_function_decl), idx = 0; param; - param = DECL_CHAIN (param)) - if (arg_needs_copy_p (param)) + param = DECL_CHAIN (param), idx++) + if (arg_needs_copy_p (param, idx)) { tree name = ssa_default_def (cfun, param); tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name)); @@ -1206,6 +1225,9 @@ tree_optimize_tail_calls_1 (bool opt_tailcalls) if (phis_constructed) mark_virtual_operands_for_renaming (cfun); + if (tailr_non_ddef_args) + BITMAP_FREE (tailr_non_ddef_args); + if (changed) return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals; return 0;