From patchwork Tue Jun 25 06:19:30 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Kewen.Lin" X-Patchwork-Id: 1121805 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-503646-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=linux.ibm.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="W4onjyU0"; 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 45XwxN2fTHz9s7h for ; Tue, 25 Jun 2019 16:19:52 +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:to:cc :from:subject:date:mime-version:content-type :content-transfer-encoding:message-id; q=dns; s=default; b=GNm+T i3wY338z8RnDSbG7HtJZjbsPpVlRFyFIULmH6i4VdfIYL+gksnu0biZ9+R6g/iVs +E0k3/YoiAlEhSdrI5Q2x3eU9N/1lkn/ziCs71pBfwxV2A5pfSYSO7R1QLlXh+/O bbze2elTJMPIfwJCLS0IuV8ZehN6o1z8kGLhq0= 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:to:cc :from:subject:date:mime-version:content-type :content-transfer-encoding:message-id; s=default; bh=UZEL5+f4gwH rcoip/sSLY8d4dzQ=; b=W4onjyU0TKsFcUp62DDD8Mmf1xTjPqAETjviUeKCXRS ZvBdTqbz2yo3/TrJlwuT3sk4/YumIBTSHvjV/UCvIVoUDgceZcYa7b5fxWvPhFx+ rpdlEZonewV8uW9AvaaZJldpt4jKIiFT3rOcOCSrtk9akKBCcNdCFC/1TmEvI79c = Received: (qmail 35706 invoked by alias); 25 Jun 2019 06:19:45 -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 35540 invoked by uid 89); 25 Jun 2019 06:19:45 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-18.4 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=ham version=3.3.1 spammy=Lin, lin X-HELO: mx0a-001b2d01.pphosted.com Received: from mx0a-001b2d01.pphosted.com (HELO mx0a-001b2d01.pphosted.com) (148.163.156.1) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 25 Jun 2019 06:19:42 +0000 Received: from pps.filterd (m0098396.ppops.net [127.0.0.1]) by mx0a-001b2d01.pphosted.com (8.16.0.27/8.16.0.27) with SMTP id x5P6HA8S065791 for ; Tue, 25 Jun 2019 02:19:41 -0400 Received: from e06smtp02.uk.ibm.com (e06smtp02.uk.ibm.com [195.75.94.98]) by mx0a-001b2d01.pphosted.com with ESMTP id 2tbe3f89mb-1 (version=TLSv1.2 cipher=AES256-GCM-SHA384 bits=256 verify=NOT) for ; Tue, 25 Jun 2019 02:19:41 -0400 Received: from localhost by e06smtp02.uk.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Tue, 25 Jun 2019 07:19:39 +0100 Received: from b06cxnps3074.portsmouth.uk.ibm.com (9.149.109.194) by e06smtp02.uk.ibm.com (192.168.101.132) with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted; (version=TLSv1/SSLv3 cipher=AES256-GCM-SHA384 bits=256/256) Tue, 25 Jun 2019 07:19:36 +0100 Received: from b06wcsmtp001.portsmouth.uk.ibm.com (b06wcsmtp001.portsmouth.uk.ibm.com [9.149.105.160]) by b06cxnps3074.portsmouth.uk.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id x5P6JZeA54198490 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Tue, 25 Jun 2019 06:19:35 GMT Received: from b06wcsmtp001.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 6C3E6A4054; Tue, 25 Jun 2019 06:19:35 +0000 (GMT) Received: from b06wcsmtp001.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id E7CF8A4064; Tue, 25 Jun 2019 06:19:31 +0000 (GMT) Received: from kewenlins-mbp.cn.ibm.com (unknown [9.200.147.28]) by b06wcsmtp001.portsmouth.uk.ibm.com (Postfix) with ESMTP; Tue, 25 Jun 2019 06:19:31 +0000 (GMT) To: GCC Patches Cc: Segher Boessenkool , Bill Schmidt , Richard Guenther , Jeff Law , "bin.cheng" , Jakub Jelinek , ook@ucw.cz From: "Kewen.Lin" Subject: [PATCH, RFC] Fix PR62147 by passing finiteness information to RTL phase Date: Tue, 25 Jun 2019 14:19:30 +0800 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.14; rv:60.0) Gecko/20100101 Thunderbird/60.7.1 MIME-Version: 1.0 x-cbid: 19062506-0008-0000-0000-000002F6BF88 X-IBM-AV-DETECTION: SAVI=unused REMOTE=unused XFE=unused x-cbparentid: 19062506-0009-0000-0000-00002263EE58 Message-Id: <2c4b23c0-7be6-8050-364a-323cb8b51408@linux.ibm.com> X-IsSubscribed: yes Hi all, As PR62147, for some cases loop iv analysis is unable to identify one loop is finite even if the loop is actually finite and we have known it in middle-end. It will prevent doloop_optimize and end up with worse codes. This patch is going to leverage existing middle-end function finite_loop_p, record the finiteness information in loop structure. Later loop iv can make use of this saved information. It's based on two observations: 1) the loop structure for one specific loop is shared between middle-end and back-end. 2) for one specific loop, if it's finite then never become infinite itself. As one gcc newbie, I'm not sure whether these two observations are true in all cases. Please feel free to correct me if anything missing. btw, I also took a look at how the loop constraint LOOP_C_FINITE is used, I think it's not suitable for this purpose, it's mainly set by vectorizer and tell niter and scev to take one loop as finite. The original patch has the words "constraint flag is mainly set by consumers and affects certain semantics of niter analyzer APIs". Bootstrapped and regression testing passed on powerpc64le-unknown-linux-gnu. Thanks, Kewen --------------------------- gcc/ChangeLog 2019-06-25 Kewen Lin PR target/62147 * gcc/cfgloop.c (alloc_loop): Init new field. * gcc/cfgloop.h (struct loop): New field. * gcc/cfgloopmanip.c (copy_loop_info): Copy new field. * gcc/tree-ssa-loop-niter.c (finite_loop_p): Rename... (test_and_update_loop_finite): ...this. Test and update above field. * gcc/tree-ssa-loop-niter.h (finite_loop_p): Rename... (test_and_update_loop_finite): ...this. * gcc/ipa-pure-const.c (analyze_function): Adjust to use above renamed function. * gcc/tree-ssa-dce.c (find_obviously_necessary_stmts): Likewise. * gcc/tree-ssa-loop-im.c (fill_always_executed_in_1): Likewise. * gcc/loop-iv.c (find_simple_exit): Update finiteness by new field. * gcc/tree-ssa-loop-ivopts.c (struct ivopts_data): New field. (rewrite_use_compare): Update new field. (tree_ssa_iv_optimize_loop): Init new field and call test_and_update_loop_finite if set. gcc/testsuite/ChangeLog 2019-06-25 Kewen Lin PR target/62147 * gcc.target/powerpc/pr62147.c: New test. diff --git a/gcc/cfgloop.c b/gcc/cfgloop.c index f64326b944e..89e4dd069ac 100644 --- a/gcc/cfgloop.c +++ b/gcc/cfgloop.c @@ -355,6 +355,7 @@ alloc_loop (void) loop->nb_iterations_upper_bound = 0; loop->nb_iterations_likely_upper_bound = 0; loop->nb_iterations_estimate = 0; + loop->is_finite = false; return loop; } diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h index 2f8ab106d03..08ec930597e 100644 --- a/gcc/cfgloop.h +++ b/gcc/cfgloop.h @@ -224,6 +224,9 @@ struct GTY ((chain_next ("%h.next"))) loop { /* True if the loop is part of an oacc kernels region. */ unsigned in_oacc_kernels_region : 1; + /* True if middle end analysis ensure this loop is finite. */ + unsigned is_finite : 1; + /* The number of times to unroll the loop. 0 means no information given, just do what we always do. A value of 1 means do not unroll the loop. A value of USHRT_MAX means unroll with no specific unrolling factor. diff --git a/gcc/cfgloopmanip.c b/gcc/cfgloopmanip.c index 50250ec4d7c..f1033d11865 100644 --- a/gcc/cfgloopmanip.c +++ b/gcc/cfgloopmanip.c @@ -1026,6 +1026,7 @@ copy_loop_info (struct loop *loop, struct loop *target) target->in_oacc_kernels_region = loop->in_oacc_kernels_region; target->unroll = loop->unroll; target->owned_clique = loop->owned_clique; + target->is_finite = loop->is_finite; } /* Copies copy of LOOP as subloop of TARGET loop, placing newly diff --git a/gcc/ipa-pure-const.c b/gcc/ipa-pure-const.c index bb561d00853..f7282adc5b1 100644 --- a/gcc/ipa-pure-const.c +++ b/gcc/ipa-pure-const.c @@ -1089,7 +1089,7 @@ end: struct loop *loop; scev_initialize (); FOR_EACH_LOOP (loop, 0) - if (!finite_loop_p (loop)) + if (!test_and_update_loop_finite (loop)) { if (dump_file) fprintf (dump_file, " cannot prove finiteness of " diff --git a/gcc/loop-iv.c b/gcc/loop-iv.c index 82b4bdb1523..a6bc82975cc 100644 --- a/gcc/loop-iv.c +++ b/gcc/loop-iv.c @@ -2997,6 +2997,19 @@ find_simple_exit (struct loop *loop, struct niter_desc *desc) fprintf (dump_file, "Loop %d is not simple.\n", loop->num); } + /* Fix up the finiteness if possible. We can only do it for single exit, + since the loop is finite, but it's possible that we predicate one loop + exit to be finite which can not be determined as finite in middle-end as + well. It results in incorrect predicate information on the exit condition + expression. For example, if says [(int) _1 + -8, + , -8] != 0 finite, + it means _1 can exactly divide -8. */ + if (single_exit (loop) && desc->infinite && loop->is_finite) + { + desc->infinite = NULL_RTX; + if (dump_file) + fprintf (dump_file, " infinite updated to finite.\n"); + } + free (body); } diff --git a/gcc/testsuite/gcc.target/powerpc/pr62147.c b/gcc/testsuite/gcc.target/powerpc/pr62147.c new file mode 100644 index 00000000000..635c73711da --- /dev/null +++ b/gcc/testsuite/gcc.target/powerpc/pr62147.c @@ -0,0 +1,24 @@ +/* { dg-do compile { target { powerpc*-*-* } } } */ +/* { dg-options "-O2 -fno-tree-loop-distribute-patterns" } */ + +/* Note that it's required to disable loop-distribute-patterns, otherwise the + loop will be optimized to memset. */ + +/* Expect loop_iv can know the loop is finite so the doloop_optimize + can perform the doloop transformation. */ + +typedef struct { + int l; + int b[258]; +} S; + +void clear (S* s ) +{ + int i; + int len = s->l + 1; + + for (i = 0; i <= len; i++) + s->b[i] = 0; +} + +/* { dg-final { scan-assembler {\mbdnz\M} } } */ diff --git a/gcc/tree-ssa-dce.c b/gcc/tree-ssa-dce.c index 2478219d873..7c183c7269a 100644 --- a/gcc/tree-ssa-dce.c +++ b/gcc/tree-ssa-dce.c @@ -417,7 +417,7 @@ find_obviously_necessary_stmts (bool aggressive) } FOR_EACH_LOOP (loop, 0) - if (!finite_loop_p (loop)) + if (!test_and_update_loop_finite (loop)) { if (dump_file) fprintf (dump_file, "cannot prove finiteness of loop %i\n", loop->num); diff --git a/gcc/tree-ssa-loop-im.c b/gcc/tree-ssa-loop-im.c index 2064c2900fb..49b8577ccd1 100644 --- a/gcc/tree-ssa-loop-im.c +++ b/gcc/tree-ssa-loop-im.c @@ -2484,7 +2484,7 @@ fill_always_executed_in_1 (struct loop *loop, sbitmap contains_call) /* Or we enter a possibly non-finite loop. */ if (flow_loop_nested_p (bb->loop_father, e->dest->loop_father) - && ! finite_loop_p (e->dest->loop_father)) + && ! test_and_update_loop_finite (e->dest->loop_father)) break; } if (e) diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c index 890f9b788b4..484a6626c05 100644 --- a/gcc/tree-ssa-loop-ivopts.c +++ b/gcc/tree-ssa-loop-ivopts.c @@ -612,6 +612,9 @@ struct ivopts_data /* Whether the loop body can only be exited via single exit. */ bool loop_single_exit_p; + + /* Whether to compute loop finiteness for loop iv. */ + bool compute_loop_finite_p; }; /* An assignment of iv candidates to uses. */ @@ -7145,6 +7148,9 @@ rewrite_use_compare (struct ivopts_data *data, gimple_cond_set_lhs (cond_stmt, var); gimple_cond_set_code (cond_stmt, compare); gimple_cond_set_rhs (cond_stmt, op); + + data->compute_loop_finite_p = true; + return; } @@ -7526,6 +7532,7 @@ tree_ssa_iv_optimize_loop (struct ivopts_data *data, struct loop *loop, data->current_loop = loop; data->loop_loc = find_loop_location (loop).get_location_t (); data->speed = optimize_loop_for_speed_p (loop); + data->compute_loop_finite_p = false; if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -7592,6 +7599,10 @@ tree_ssa_iv_optimize_loop (struct ivopts_data *data, struct loop *loop, /* Remove the ivs that are unused after rewriting. */ remove_unused_ivs (data, toremove); + /* Update loop finiteness info. */ + if (data->compute_loop_finite_p) + test_and_update_loop_finite (data->current_loop); + finish: free (body); free_loop_data (data); diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c index 84e6e313c85..78152714791 100644 --- a/gcc/tree-ssa-loop-niter.c +++ b/gcc/tree-ssa-loop-niter.c @@ -2808,10 +2808,14 @@ find_loop_niter (struct loop *loop, edge *exit) /* Return true if loop is known to have bounded number of iterations. */ bool -finite_loop_p (struct loop *loop) +test_and_update_loop_finite (struct loop *loop) { widest_int nit; int flags; + bool finite_p = false; + + if (loop->is_finite) + return true; flags = flags_from_decl_or_type (current_function_decl); if ((flags & (ECF_CONST|ECF_PURE)) && !(flags & ECF_LOOPING_CONST_OR_PURE)) @@ -2819,7 +2823,8 @@ finite_loop_p (struct loop *loop) if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "Found loop %i to be finite: it is within pure or const function.\n", loop->num); - return true; + finite_p = true; + goto finish; } if (loop->any_upper_bound @@ -2828,9 +2833,14 @@ finite_loop_p (struct loop *loop) if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "Found loop %i to be finite: upper bound found.\n", loop->num); - return true; + finite_p = true; + goto finish; } - return false; + + finish: + if (finite_p) + loop->is_finite = true; + return finite_p; } /* diff --git a/gcc/tree-ssa-loop-niter.h b/gcc/tree-ssa-loop-niter.h index dc116489218..01d587f1cbb 100644 --- a/gcc/tree-ssa-loop-niter.h +++ b/gcc/tree-ssa-loop-niter.h @@ -30,7 +30,7 @@ extern bool number_of_iterations_exit_assumptions (struct loop *, edge, struct tree_niter_desc *, gcond **, bool = true); extern tree find_loop_niter (struct loop *, edge *); -extern bool finite_loop_p (struct loop *); +extern bool test_and_update_loop_finite (struct loop *); extern tree loop_niter_by_eval (struct loop *, edge); extern tree find_loop_niter_by_eval (struct loop *, edge *); extern bool estimated_loop_iterations (struct loop *, widest_int *);