From patchwork Wed Nov 10 18:20:03 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 1553550 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: bilbo.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=P+zEpv8F; dkim-atps=neutral Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Received: from sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4HqCp25RkGz9s0r for ; Thu, 11 Nov 2021 05:20:41 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 4BAE6385803B for ; Wed, 10 Nov 2021 18:20:38 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 4BAE6385803B DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1636568438; bh=c+dOrYcJmS9NSHxj3vK3cUd0I1InbS2PMPAs5NDMNB0=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=P+zEpv8F+eEKV7YR9EJlgnFtTdMt2M9Ws5BM7NjGSndzx6NIuE05yIST/aDJbj8MX ZTBaK59d1rCpLnpt1PRUpqh6NXEgrQHNlOziPxUiSV9lUROga+wt9D9I6lRCqzQLPV FTVxdiqekKtO7kavWo4hLes3s0uaYvh315pKpxAg= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTPS id 7367F3858400 for ; Wed, 10 Nov 2021 18:20:15 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 7367F3858400 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-389-wEJEyG5nMnaukpsRuU9pNg-1; Wed, 10 Nov 2021 13:20:13 -0500 X-MC-Unique: wEJEyG5nMnaukpsRuU9pNg-1 Received: from smtp.corp.redhat.com (int-mx01.intmail.prod.int.phx2.redhat.com [10.5.11.11]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id D197919611C5; Wed, 10 Nov 2021 18:20:12 +0000 (UTC) Received: from abulafia.quesejoda.com (unknown [10.39.192.203]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 4E55667840; Wed, 10 Nov 2021 18:20:12 +0000 (UTC) Received: from abulafia.quesejoda.com (localhost [127.0.0.1]) by abulafia.quesejoda.com (8.16.1/8.15.2) with ESMTPS id 1AAIK930686293 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Wed, 10 Nov 2021 19:20:09 +0100 Received: (from aldyh@localhost) by abulafia.quesejoda.com (8.16.1/8.16.1/Submit) id 1AAIK87A686292; Wed, 10 Nov 2021 19:20:08 +0100 To: Richard Biener Subject: [PATCH] Allow loop header copying when first iteration condition is known. Date: Wed, 10 Nov 2021 19:20:03 +0100 Message-Id: <20211110182003.686241-1-aldyh@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.79 on 10.5.11.11 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-13.3 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Aldy Hernandez via Gcc-patches From: Aldy Hernandez Reply-To: Aldy Hernandez Cc: GCC patches Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" As discussed in the PR, the loop header copying pass avoids doing so when optimizing for size. However, sometimes we can determine the loop entry conditional statically for the first iteration of the loop. This patch uses the path solver to determine the outgoing edge out of preheader->header->xx. If so, it allows header copying. Doing this in the loop optimizer saves us from doing gymnastics in the threader which doesn't have the context to determine if a loop transformation is profitable. I am only returning true in entry_loop_condition_is_static for a true conditional. Technically a false conditional is also provably static, but allowing any boolean value causes a regression in gfortran.dg/vector_subscript_1.f90. I would have preferred not passing around the query object, but the layout of pass_ch and should_duplicate_loop_header_p make it a bit awkward to get it right without an outright refactor to the pass. Tested on x86-64 Linux. OK? gcc/ChangeLog: PR tree-optimization/102906 * tree-ssa-loop-ch.c (entry_loop_condition_is_static): New. (should_duplicate_loop_header_p): Call entry_loop_condition_is_static. (class ch_base): Add m_ranger and m_query. (ch_base::copy_headers): Pass m_query to entry_loop_condition_is_static. (pass_ch::execute): Allocate and deallocate m_ranger and m_query. (pass_ch_vect::execute): Same. gcc/testsuite/ChangeLog: * gcc.dg/tree-ssa/pr102906.c: New test. --- gcc/testsuite/gcc.dg/tree-ssa/pr102906.c | 17 ++++++++ gcc/tree-ssa-loop-ch.c | 51 ++++++++++++++++++++---- 2 files changed, 60 insertions(+), 8 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr102906.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr102906.c b/gcc/testsuite/gcc.dg/tree-ssa/pr102906.c new file mode 100644 index 00000000000..1846f0b6dba --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr102906.c @@ -0,0 +1,17 @@ +// { dg-do compile } +// { dg-options "-Os -fdump-tree-ch-details" } + +extern unsigned int foo (int*) __attribute__((pure)); + +unsigned int +tr2 (int array[], int n) +{ + unsigned int sum = 0; + int x; + if (n > 0) + for (x = 0; x < n; x++) + sum += foo (&array[x]); + return sum; +} + +// { dg-final { scan-tree-dump-not "Not duplicating.*optimizing for size" "ch2" } } diff --git a/gcc/tree-ssa-loop-ch.c b/gcc/tree-ssa-loop-ch.c index ffb0aa85118..c7d86d751d4 100644 --- a/gcc/tree-ssa-loop-ch.c +++ b/gcc/tree-ssa-loop-ch.c @@ -35,30 +35,52 @@ along with GCC; see the file COPYING3. If not see #include "tree-ssa-sccvn.h" #include "tree-phinodes.h" #include "ssa-iterators.h" +#include "value-range.h" +#include "gimple-range.h" +#include "gimple-range-path.h" /* Duplicates headers of loops if they are small enough, so that the statements in the loop body are always executed when the loop is entered. This increases effectiveness of code motion optimizations, and reduces the need for loop preconditioning. */ +/* Return true if the condition on the first iteration of the loop can + be statically determined. */ + +static bool +entry_loop_condition_is_static (class loop *l, path_range_query *query) +{ + edge e = loop_preheader_edge (l); + gcond *last = safe_dyn_cast (last_stmt (e->dest)); + + if (!last + || !irange::supports_type_p (TREE_TYPE (gimple_cond_lhs (last)))) + return false; + + int_range<2> r; + query->compute_ranges (e); + query->range_of_stmt (r, last); + return r == int_range<2> (boolean_true_node, boolean_true_node); +} + /* Check whether we should duplicate HEADER of LOOP. At most *LIMIT instructions should be duplicated, limit is decreased by the actual amount. */ static bool should_duplicate_loop_header_p (basic_block header, class loop *loop, - int *limit) + int *limit, path_range_query *query) { gimple_stmt_iterator bsi; gcc_assert (!header->aux); - /* Loop header copying usually increases size of the code. This used not to - be true, since quite often it is possible to verify that the condition is - satisfied in the first iteration and therefore to eliminate it. Jump - threading handles these cases now. */ + /* Avoid loop header copying when optimizing for size unless we can + determine that the loop condition is static in the first + iteration. */ if (optimize_loop_for_size_p (loop) - && !loop->force_vectorize) + && !loop->force_vectorize + && !entry_loop_condition_is_static (loop, query)) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, @@ -267,6 +289,9 @@ class ch_base : public gimple_opt_pass /* Return true to copy headers of LOOP or false to skip. */ virtual bool process_loop_p (class loop *loop) = 0; + + gimple_ranger *m_ranger = NULL; + path_range_query *m_query = NULL; }; const pass_data pass_data_ch = @@ -389,7 +414,8 @@ ch_base::copy_headers (function *fun) exit = NULL; n_bbs = 0; - while (should_duplicate_loop_header_p (header, loop, &remaining_limit)) + while (should_duplicate_loop_header_p (header, loop, &remaining_limit, + m_query)) { /* Find a successor of header that is inside a loop; i.e. the new header after the condition is copied. */ @@ -526,9 +552,13 @@ pass_ch::execute (function *fun) loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES | LOOPS_HAVE_RECORDED_EXITS); + m_ranger = new gimple_ranger; + m_query = new path_range_query (*m_ranger, /*resolve=*/true); unsigned int res = copy_headers (fun); + delete m_query; + delete m_ranger; loop_optimizer_finalize (); return res; } @@ -540,7 +570,12 @@ pass_ch::execute (function *fun) unsigned int pass_ch_vect::execute (function *fun) { - return copy_headers (fun); + m_ranger = new gimple_ranger; + m_query = new path_range_query (*m_ranger, /*resolve=*/true); + unsigned int res = copy_headers (fun); + delete m_query; + delete m_ranger; + return res; } /* Apply header copying according to a very simple test of do-while shape. */