From patchwork Thu Jan 14 10:29:06 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alan Lawrence X-Patchwork-Id: 567311 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org 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 BCA3E1402F0 for ; Thu, 14 Jan 2016 21:29:41 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=YrEzoBN7; dkim-atps=neutral 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:in-reply-to:references; q=dns; s= default; b=RacIc6ZLJfHnEE74QyHRzndx5rsVHDoZCqYUP4awNuKsIt/1VzxZl T7lVE1GahF1450tXek8I00tStEl9f5rT7nVcIqsINZv5ReF/nw1bZFalJ5Hc7EDu U0G2i4Up01dhvhatEoiasOpyjtl6rmhj4wk+9epff0Vu1+lPxVrSOE= 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:in-reply-to:references; s= default; bh=9J6T0cmCD2jvZcCb/pTt4PpVqb4=; b=YrEzoBN7BRd5I74LEIyW OXea+gPKE270enjAX4oBMbIOcnY0/ectXPa5BqMUXziq1R3zOAA/M8YRdZc3K9Tm OF8uRT0c313vwLikWcejgjyidhoBsda41Xe5TeJO1ipCn1FLGOmwn7gXxjb22T7w H+dO2EMckCA0Lb8M+9x7dKU= Received: (qmail 36907 invoked by alias); 14 Jan 2016 10:29:35 -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 36893 invoked by uid 89); 14 Jan 2016 10:29:33 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.9 required=5.0 tests=BAYES_00, RP_MATCHES_RCVD, SPF_PASS autolearn=ham version=3.3.2 spammy=earliest, richard.guenther@gmail.com, richardguenthergmailcom, *phi X-HELO: foss.arm.com Received: from foss.arm.com (HELO foss.arm.com) (217.140.101.70) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 14 Jan 2016 10:29:32 +0000 Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.72.51.249]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 8333E49; Thu, 14 Jan 2016 02:28:55 -0800 (PST) Received: from arm.com (e105915-lin.emea.arm.com [10.2.206.30]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPA id E825E3F2E5; Thu, 14 Jan 2016 02:29:30 -0800 (PST) From: Alan Lawrence To: gcc-patches@gcc.gnu.org Cc: richard.guenther@gmail.com Subject: [PATCH 3/4 v2] Enhance SCEV to follow copies of SSA_NAMEs. Date: Thu, 14 Jan 2016 10:29:06 +0000 Message-Id: <1452767346-32168-1-git-send-email-alan.lawrence@arm.com> In-Reply-To: References: X-IsSubscribed: yes (Previous message: https://gcc.gnu.org/ml/gcc-patches/2015-12/msg02159.html) On Sat, Dec 26, 2015 at 18:58 PM, Richard Biener wrote: >> I'm not sure whether adding a pass_copy_prop is the right thing here, but since >> loop-header-copying can create such opportunities, it seems good to take them! > > Aww. I'd rather have general infrastructure (like SCEV) deal with > those non-propagated copies. > > There are likely other missed propagation / folding opportunities > caused from partial peeling. > > Richard. I take your second point, but I am concerned that this leads to duplication of copy-propagation code throughout the compiler? However, this patch does that. Making analyze_initial_condition (alone) follow copies, is enough to solve my case of missed vectorization of pr65947-2.c; but I also used the routine in analyze_scalar_evolution_1, as it found copies to follow in both bootstrap and a significant number of testcases: c-c++-common/gomp/pr58472.c gcc.c-torture/execute/20000422-1.c gcc.c-torture/execute/20041213-2.c gcc.c-torture/execute/20100430-1.c gcc.c-torture/execute/pr49712.c gcc.c-torture/execute/pr58640.c gcc.dg/Warray-bounds-13.c gcc.dg/graphite/block-{1,5,6}.c gcc.dg/graphite/interchange-12.c gcc.dg/graphite/interchange-mvt.c gcc.dg/graphite/pr19910.c gcc.dg/graphite/uns-block-1.c gcc.dg/loop-unswitch-{2,4}.c gcc.dg/pr59670.c gcc.dg/torture/matrix-{1,2,3,4,5,6}.c gcc.dg/torture/pr24750-1.c gcc.dg/torture/transpose-{1,2,3,4,5,6}.c ...some of which were resolved to constants. (Of course, this approach is not as thorough as adding a pass_copy_prop. E.g. it does *not* enable vectorization of the inlined copy in pr65947-9.c.) Bootstrapped + check-gcc + check-g++ on ARM, AArch64, x86_64. gcc/ChangeLog: * tree-scalar-evolution.c (follow_copies): New. (analyze_initial_condition, analyze_scalar_evolution_1): Call previous. --- gcc/tree-scalar-evolution.c | 53 ++++++++++++++++++++++++++++++--------------- 1 file changed, 36 insertions(+), 17 deletions(-) diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index 9b33693..357eb8f 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -1522,6 +1522,37 @@ analyze_evolution_in_loop (gphi *loop_phi_node, return evolution_function; } +/* While VAR is an SSA_NAME whose definition is a straight copy of another name, + or (perhaps via a degenerate phi) a constant, follows that definition. + Returns the constant, or the earliest SSA_NAME whose definition is neither + constant nor copy. */ + +static tree +follow_copies (tree var) +{ + while (TREE_CODE (var) == SSA_NAME) + { + gimple *def = SSA_NAME_DEF_STMT (var); + if (gphi *phi = dyn_cast (def)) + { + tree rhs = degenerate_phi_result (phi); + /* Don't follow degenerate phi's of SSA_NAMES, that can break + loop-closed SSA form. */ + if (rhs && is_gimple_min_invariant (rhs)) + var = rhs; + break; + } + else if (gimple_assign_single_p (def) + && !gimple_vuse (def) + && (gimple_assign_rhs_code (def) == SSA_NAME + || is_gimple_min_invariant (gimple_assign_rhs1 (def)))) + var = gimple_assign_rhs1 (def); + else + break; + } + return var; +} + /* Given a loop-phi-node, return the initial conditions of the variable on entry of the loop. When the CCP has propagated constants into the loop-phi-node, the initial condition is @@ -1574,21 +1605,9 @@ analyze_initial_condition (gphi *loop_phi_node) if (init_cond == chrec_not_analyzed_yet) init_cond = chrec_dont_know; - /* During early loop unrolling we do not have fully constant propagated IL. - Handle degenerate PHIs here to not miss important unrollings. */ - if (TREE_CODE (init_cond) == SSA_NAME) - { - gimple *def = SSA_NAME_DEF_STMT (init_cond); - if (gphi *phi = dyn_cast (def)) - { - tree res = degenerate_phi_result (phi); - if (res != NULL_TREE - /* Only allow invariants here, otherwise we may break - loop-closed SSA form. */ - && is_gimple_min_invariant (res)) - init_cond = res; - } - } + /* We may not have fully constant propagated IL. Handle degenerate PHIs here + to not miss important early loop unrollings. */ + init_cond = follow_copies (init_cond); if (dump_file && (dump_flags & TDF_SCEV)) { @@ -1968,8 +1987,8 @@ analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res) if (bb == NULL || !flow_bb_inside_loop_p (loop, bb)) { - /* Keep the symbolic form. */ - res = var; + /* Keep symbolic form, but look through obvious copies for constants. */ + res = follow_copies (var); goto set_and_end; }