From patchwork Mon Jun 21 07:02:33 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Jiufu Guo X-Patchwork-Id: 1494921 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: 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=bksYW5vo; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (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 ozlabs.org (Postfix) with ESMTPS id 4G7gV837Glz9s1l for ; Mon, 21 Jun 2021 17:03:26 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 0F843383302A for ; Mon, 21 Jun 2021 07:03:24 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 0F843383302A DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1624259004; bh=OsV9N85MlB35NFCbyPp7k4UFCmImZIwjW66mi4Z6QWM=; h=Date:To:Subject:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To:Cc: From; b=bksYW5voQD8CYxCkK59C514gAYm0I9rfmrwiQl8Wiw4qfNmSh+Cedz4D6DRsUfeaE gcZ2358iKJOwTbHPwA56lboqzY33ADOMVqK7P5gBVFrj0gE+WimHMRn3WXcMmZyfxT jx0jU1BE8xNHktVWlvyoM18fuNSz44L+8A2X3hNM= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mx0a-001b2d01.pphosted.com (mx0b-001b2d01.pphosted.com [148.163.158.5]) by sourceware.org (Postfix) with ESMTPS id 0690B3875400; Mon, 21 Jun 2021 07:02:37 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 0690B3875400 Received: from pps.filterd (m0098420.ppops.net [127.0.0.1]) by mx0b-001b2d01.pphosted.com (8.16.0.43/8.16.0.43) with SMTP id 15L6XbWr127867; Mon, 21 Jun 2021 03:02:36 -0400 Received: from pps.reinject (localhost [127.0.0.1]) by mx0b-001b2d01.pphosted.com with ESMTP id 39akkybkxt-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Mon, 21 Jun 2021 03:02:36 -0400 Received: from m0098420.ppops.net (m0098420.ppops.net [127.0.0.1]) by pps.reinject (8.16.0.43/8.16.0.43) with SMTP id 15L6YilW134125; Mon, 21 Jun 2021 03:02:35 -0400 Received: from ppma01wdc.us.ibm.com (fd.55.37a9.ip4.static.sl-reverse.com [169.55.85.253]) by mx0b-001b2d01.pphosted.com with ESMTP id 39akkybkxf-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Mon, 21 Jun 2021 03:02:35 -0400 Received: from pps.filterd (ppma01wdc.us.ibm.com [127.0.0.1]) by ppma01wdc.us.ibm.com (8.16.1.2/8.16.1.2) with SMTP id 15L71odj015803; Mon, 21 Jun 2021 07:02:35 GMT Received: from b03cxnp08025.gho.boulder.ibm.com (b03cxnp08025.gho.boulder.ibm.com [9.17.130.17]) by ppma01wdc.us.ibm.com with ESMTP id 399878d2st-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Mon, 21 Jun 2021 07:02:35 +0000 Received: from b03ledav005.gho.boulder.ibm.com (b03ledav005.gho.boulder.ibm.com [9.17.130.236]) by b03cxnp08025.gho.boulder.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id 15L72YSk21496104 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Mon, 21 Jun 2021 07:02:34 GMT Received: from b03ledav005.gho.boulder.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 18DDDBE058; Mon, 21 Jun 2021 07:02:34 +0000 (GMT) Received: from b03ledav005.gho.boulder.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 8FA33BE051; Mon, 21 Jun 2021 07:02:33 +0000 (GMT) Received: from ltc.linux.ibm.com (unknown [9.10.229.42]) by b03ledav005.gho.boulder.ibm.com (Postfix) with ESMTP; Mon, 21 Jun 2021 07:02:33 +0000 (GMT) MIME-Version: 1.0 Date: Mon, 21 Jun 2021 15:02:33 +0800 To: gcc-patches@gcc.gnu.org Subject: [RFC] New idea to split loop based on no-wrap conditions In-Reply-To: <6bdc3528d7c24b8a8957a8e9ecf31b56@imap.linux.ibm.com> References: <20210604080419.119328-1-guojiufu@linux.ibm.com> <849ac659148ac8168c6c0c0b92f46041@imap.linux.ibm.com> <6bdc3528d7c24b8a8957a8e9ecf31b56@imap.linux.ibm.com> Message-ID: <9f0c505cd216d45f06b63cd94152fc8a@imap.linux.ibm.com> X-Sender: guojiufu@linux.ibm.com User-Agent: Roundcube Webmail/1.1.12 X-TM-AS-GCONF: 00 X-Proofpoint-GUID: iyhPZUIK9K-j7nGLIQl0PK2KJNKZDIep X-Proofpoint-ORIG-GUID: kOZsuKuenan0f0iQhPZk7bcoaR7p2LWt X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:6.0.391, 18.0.790 definitions=2021-06-21_02:2021-06-20, 2021-06-21 signatures=0 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 priorityscore=1501 bulkscore=0 clxscore=1015 adultscore=0 impostorscore=0 suspectscore=0 mlxscore=0 spamscore=0 mlxlogscore=999 malwarescore=0 phishscore=0 lowpriorityscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2104190000 definitions=main-2106210036 X-Spam-Status: No, score=-10.0 required=5.0 tests=BAYES_00, BODY_8BITS, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_EF, GIT_PATCH_0, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) 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: guojiufu via Gcc-patches From: Jiufu Guo Reply-To: guojiufu Cc: Gcc-patches , Richard Biener , segher@kernel.crashing.org, wschmidt@linux.ibm.com, jlaw@tachyum.com, dje.gcc@gmail.com Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" On 2021-06-21 14:19, guojiufu via Gcc-patches wrote: > On 2021-06-09 19:18, guojiufu wrote: >> On 2021-06-09 17:42, guojiufu via Gcc-patches wrote: >>> On 2021-06-08 18:13, Richard Biener wrote: >>>> On Fri, 4 Jun 2021, Jiufu Guo wrote: >>>> >>> cut... > cut... >> Besides the method in the previous mails,  I’m thinking of another way to split loops: foo (int *a, int *b, unsigned k, unsigned n) {                                                                 while (++k != n)    a[k] = b[k] + 1;                                }  We may split it into: if (kaux = loop; >> Here is the updated patch, thanks for your time! > > Updates: > . Enhance code to support negative step. > . Check step +-1 to make sure it hits loop condition != > . Enhance runtime cases to check more boundary cases and run order > cases. > . Refine for compiling time: check loop num of insns and can_copy_bbs_p > later > >> >> diff --git a/gcc/testsuite/gcc.dg/loop-split1.c >> b/gcc/testsuite/gcc.dg/loop-split1.c >> new file mode 100644 >> index 00000000000..dd2d03a7b96 >> --- /dev/null >> +++ b/gcc/testsuite/gcc.dg/loop-split1.c >> @@ -0,0 +1,101 @@ >> +/* { dg-do compile } */ >> +/* { dg-options "-O2 -fsplit-loops -fdump-tree-lsplit-details" } */ >> + >> +void >> +foo (int *a, int *b, unsigned l, unsigned n) >> +{ >> + while (++l != n) >> + a[l] = b[l] + 1; >> +} >> +void >> +foo_1 (int *a, int *b, unsigned n) >> +{ >> + unsigned l = 0; >> + while (++l != n) >> + a[l] = b[l] + 1; >> +} >> + >> +void >> +foo1 (int *a, int *b, unsigned l, unsigned n) >> +{ >> + while (l++ != n) >> + a[l] = b[l] + 1; >> +} >> + >> +/* No wrap. */ >> +void >> +foo1_1 (int *a, int *b, unsigned n) >> +{ >> + unsigned l = 0; >> + while (l++ != n) >> + a[l] = b[l] + 1; >> +} >> + >> +unsigned >> +foo2 (char *a, char *b, unsigned l, unsigned n) >> +{ >> + while (++l != n) >> + if (a[l] != b[l]) >> + break; >> + >> + return l; >> +} >> + >> +unsigned >> +foo2_1 (char *a, char *b, unsigned l, unsigned n) >> +{ >> + l = 0; >> + while (++l != n) >> + if (a[l] != b[l]) >> + break; >> + >> + return l; >> +} >> + >> +unsigned >> +foo3 (char *a, char *b, unsigned l, unsigned n) >> +{ >> + while (l++ != n) >> + if (a[l] != b[l]) >> + break; >> + >> + return l; >> +} >> + >> +/* No wrap. */ >> +unsigned >> +foo3_1 (char *a, char *b, unsigned l, unsigned n) >> +{ >> + l = 0; >> + while (l++ != n) >> + if (a[l] != b[l]) >> + break; >> + >> + return l; >> +} >> + >> +void >> +bar (); >> +void >> +foo4 (unsigned n, unsigned i) >> +{ >> + do >> + { >> + if (i == n) >> + return; >> + bar (); >> + ++i; >> + } >> + while (1); >> +} >> + >> +unsigned >> +find_skip_diff (char *p, char *q, unsigned n, unsigned i) >> +{ >> + while (p[i] == q[i] && ++i != n) >> + p++, q++; >> + >> + return i; >> +} >> + >> +/* { dg-final { scan-tree-dump-times "Loop split" 8 "lsplit" } } */ >> diff --git a/gcc/testsuite/gcc.dg/loop-split2.c >> b/gcc/testsuite/gcc.dg/loop-split2.c >> new file mode 100644 >> index 00000000000..56377e2f2f5 >> --- /dev/null >> +++ b/gcc/testsuite/gcc.dg/loop-split2.c >> @@ -0,0 +1,155 @@ >> +/* { dg-do run } */ >> +/* { dg-options "-O3" } */ >> + >> +extern void >> +abort (void); >> +extern void >> +exit (int); >> +void >> +push (int); >> + >> +#define NI __attribute__ ((noinline)) >> + >> +void NI >> +foo (int *a, int *b, unsigned char l, unsigned char n) >> +{ >> + while (++l != n) >> + a[l] = b[l] + 1; >> +} >> + >> +unsigned NI >> +bar (int *a, int *b, unsigned char l, unsigned char n) >> +{ >> + while (l++ != n) >> + { >> + push (l); >> + if (a[l] != b[l]) >> + break; >> + push (l + 1); >> + } >> + return l; >> +} >> + >> +void NI >> +foo_1 (int *a, int *b, unsigned char l, unsigned char n) >> +{ >> + while (--l != n) >> + a[l] = b[l] + 1; >> +} >> + >> +unsigned NI >> +bar_1 (int *a, int *b, unsigned char l, unsigned char n) >> +{ >> + while (l-- != n) >> + { >> + push (l); >> + if (a[l] != b[l]) >> + break; >> + push (l + 1); >> + } >> + >> + return l; >> +} >> + >> +int a[258]; >> +int b[258]; >> +int c[1024]; >> +static int top = 0; >> +void >> +push (int e) >> +{ >> + c[top++] = e; >> +} >> + >> +void >> +reset () >> +{ >> + top = 0; >> + __builtin_memset (c, 0, sizeof (c)); >> +} >> + >> +#define check(a, b) (a == b) >> + >> +int >> +check_c (int *c, int a0, int a1, int a2, int a3, int a4, int a5) >> +{ >> + return check (c[0], a0) && check (c[1], a1) && check (c[2], a2) >> + && check (c[3], a3) && check (c[4], a4) && check (c[5], a5); >> +} >> + >> +int >> +main () >> +{ >> + __builtin_memcpy (b, a, sizeof (a)); >> + reset (); >> + if (bar (a, b, 6, 8) != 9 || !check_c (c, 7, 8, 8, 9, 0, 0)) >> + abort (); >> + >> + reset (); >> + if (bar (a, b, 5, 3) != 4 || !check_c (c, 6, 7, 7, 8, 8, 9) >> + || !check_c (c + 496, 254, 255, 255, 256, 0, 1)) >> + abort (); >> + >> + reset (); >> + if (bar (a, b, 6, 6) != 7 || !check_c (c, 0, 0, 0, 0, 0, 0)) >> + abort (); >> + >> + reset (); >> + if (bar (a, b, 253, 255) != 0 || !check_c (c, 254, 255, 255, 256, >> 0, 0)) >> + abort (); >> + >> + reset (); >> + if (bar (a, b, 253, 0) != 1 || !check_c (c, 254, 255, 255, 256, 0, >> 1)) >> + abort (); >> + >> + reset (); >> + if (bar_1 (a, b, 6, 8) != 7 || !check_c (c, 5, 6, 4, 5, 3, 4)) >> + abort (); >> + >> + reset (); >> + if (bar_1 (a, b, 5, 3) != 2 || !check_c (c, 4, 5, 3, 4, 0, 0)) >> + abort (); >> + >> + reset (); >> + if (bar_1 (a, b, 6, 6) != 5) >> + abort (); >> + >> + reset (); >> + if (bar_1 (a, b, 2, 255) != 254 || !check_c (c, 1, 2, 0, 1, 255, >> 256)) >> + abort (); >> + >> + reset (); >> + if (bar_1 (a, b, 2, 0) != 255 || !check_c (c, 1, 2, 0, 1, 0, 0)) >> + abort (); >> + >> + b[100] += 1; >> + reset (); >> + if (bar (a, b, 90, 110) != 100) >> + abort (); >> + >> + reset (); >> + if (bar (a, b, 110, 105) != 100) >> + abort (); >> + >> + reset (); >> + if (bar_1 (a, b, 90, 110) != 109) >> + abort (); >> + >> + reset (); >> + if (bar_1 (a, b, 2, 90) != 100) >> + abort (); >> + >> + foo (a, b, 99, 99); >> + a[99] = b[99] + 1; >> + for (int i = 0; i < 256; i++) >> + if (a[i] != b[i] + 1) >> + abort (); >> + >> + foo_1 (a, b, 99, 99); >> + a[99] = b[99] + 1; >> + for (int i = 0; i < 256; i++) >> + if (a[i] != b[i] + 1) >> + abort (); >> + >> + exit (0); >> +} >> diff --git a/gcc/testsuite/gcc.dg/loop-split3.c >> b/gcc/testsuite/gcc.dg/loop-split3.c >> new file mode 100644 >> index 00000000000..ec93ee8bd12 >> --- /dev/null >> +++ b/gcc/testsuite/gcc.dg/loop-split3.c >> @@ -0,0 +1,62 @@ >> +/* { dg-do compile } */ >> +/* { dg-options "-O2 -fsplit-loops -fdump-tree-lsplit-details" } */ >> + >> +void >> +foo (int *a, int *b, unsigned l, unsigned n) >> +{ >> + while (--l != n) >> + a[l] = b[l] + 1; >> +} >> + >> +void >> +foo1 (int *a, int *b, unsigned l, unsigned n) >> +{ >> + while (l-- != n) >> + a[l] = b[l] + 1; >> +} >> + >> +unsigned >> +foo2 (char *a, char *b, unsigned l, unsigned n) >> +{ >> + while (--l != n) >> + if (a[l] != b[l]) >> + break; >> + >> + return l; >> +} >> + >> +unsigned >> +foo3 (char *a, char *b, unsigned l, unsigned n) >> +{ >> + while (l-- != n) >> + if (a[l] != b[l]) >> + break; >> + >> + return l; >> +} >> + >> +void >> +bar (); >> +void >> +foo4 (unsigned n, unsigned i) >> +{ >> + do >> + { >> + if (i == n) >> + return; >> + bar (); >> + --i; >> + } >> + while (1); >> +} >> + >> +unsigned >> +find_skip_diff (char *p, char *q, unsigned n, unsigned i) >> +{ >> + while (p[i] == q[i] && --i != n) >> + p--, q--; >> + >> + return i; >> +} >> + >> +/* { dg-final { scan-tree-dump-times "Loop split" 6 "lsplit" } } */ >> diff --git a/gcc/tree-ssa-loop-split.c b/gcc/tree-ssa-loop-split.c >> index 3a09bbc39e5..e9f23b32186 100644 >> --- a/gcc/tree-ssa-loop-split.c >> +++ b/gcc/tree-ssa-loop-split.c >> @@ -41,6 +41,7 @@ along with GCC; see the file COPYING3. If not see >> #include "cfghooks.h" >> #include "gimple-fold.h" >> #include "gimplify-me.h" >> +#include "tree-ssa-loop-ivopts.h" >> >> /* This file implements two kinds of loop splitting. >> >> @@ -229,11 +230,14 @@ easy_exit_values (class loop *loop) >> conditional). I.e. the second loop can now be entered either >> via the original entry or via NEW_E, so the entry values of LOOP2 >> phi nodes are either the original ones or those at the exit >> - of LOOP1. Insert new phi nodes in LOOP2 pre-header reflecting >> - this. The loops need to fulfill easy_exit_values(). */ >> + of LOOP1. Selecting the previous value instead next value as the >> + exit value of LOOP1 if USE_PREV is true. Insert new phi nodes in >> + LOOP2 pre-header reflecting this. The loops need to fulfill >> + easy_exit_values(). */ >> >> static void >> -connect_loop_phis (class loop *loop1, class loop *loop2, edge new_e) >> +connect_loop_phis (class loop *loop1, class loop *loop2, edge new_e, >> + bool use_prev = false) >> { >> basic_block rest = loop_preheader_edge (loop2)->src; >> gcc_assert (new_e->dest == rest); >> @@ -279,7 +283,8 @@ connect_loop_phis (class loop *loop1, class loop >> *loop2, edge new_e) >> >> gphi * newphi = create_phi_node (new_init, rest); >> add_phi_arg (newphi, init, skip_first, UNKNOWN_LOCATION); >> - add_phi_arg (newphi, next, new_e, UNKNOWN_LOCATION); >> + add_phi_arg (newphi, use_prev ? PHI_RESULT (phi_first) : next, >> new_e, >> + UNKNOWN_LOCATION); >> SET_USE (op, new_init); >> } >> } >> @@ -1593,6 +1598,252 @@ split_loop_on_cond (struct loop *loop) >> return do_split; >> } >> >> +/* Check if the LOOP exit branch is like "if (idx != bound)", >> + Return the branch edge which exit loop, if wrap may happen on >> "idx". */ >> + >> +static edge >> +get_ne_cond_branch (struct loop *loop, tree *step) >> +{ >> + int i; >> + edge e; >> + >> + auto_vec edges = get_loop_exit_edges (loop); >> + FOR_EACH_VEC_ELT (edges, i, e) >> + { >> + basic_block bb = e->src; >> + >> + /* Check if exit at gcond. */ >> + gimple *last = last_stmt (bb); >> + if (!last || gimple_code (last) != GIMPLE_COND) >> + continue; >> + gcond *cond = as_a (last); >> + enum tree_code code = gimple_cond_code (cond); >> + if (!((code == NE_EXPR && (e->flags & EDGE_FALSE_VALUE)) >> + || (code == EQ_EXPR && (e->flags & EDGE_TRUE_VALUE)))) >> + continue; >> + >> + /* Check if bound is invarant. */ >> + tree idx = gimple_cond_lhs (cond); >> + tree bnd = gimple_cond_rhs (cond); >> + if (expr_invariant_in_loop_p (loop, idx)) >> + std::swap (idx, bnd); >> + else if (!expr_invariant_in_loop_p (loop, bnd)) >> + continue; >> + >> + /* Only unsigned type conversion could cause wrap. */ >> + tree type = TREE_TYPE (idx); >> + if (!INTEGRAL_TYPE_P (type) || TREE_CODE (idx) != SSA_NAME >> + || !TYPE_UNSIGNED (type)) >> + continue; >> + >> + /* Avoid to split if bound is MAX/MIN val. */ >> + tree bound_type = TREE_TYPE (bnd); >> + if (tree_int_cst_equal (bnd, TYPE_MAX_VALUE (bound_type)) >> + || tree_int_cst_equal (bnd, TYPE_MIN_VALUE (bound_type))) >> + continue; >> + >> + /* Check if there is possible wrap. */ >> + class tree_niter_desc niter; >> + if (!number_of_iterations_exit (loop, e, &niter, false, false)) >> + continue; >> + if (niter.control.no_overflow) >> + return NULL; >> + if (niter.cmp != NE_EXPR) >> + continue; >> + if (!integer_onep (niter.control.step) >> + && !integer_minus_onep (niter.control.step)) >> + continue; >> + *step = niter.control.step; >> + >> + /* If exit edge is just before the empty latch, it is easy to >> link >> + the split loops: just jump from the exit edge of one loop to the >> + header of new loop. */ >> + if (single_pred_p (loop->latch) >> + && single_pred_edge (loop->latch)->src == bb >> + && empty_block_p (loop->latch)) >> + return e; >> + >> + /* If exit edge is at end of header, and header contains i++ or >> ++i, >> + only, it is simple to link the split loops: jump from the end of >> + one loop header to the new loop header, and use unchanged PHI >> result >> + of the first loop as the entry PHI value of the second loop. */ >> + if (bb == loop->header) >> + { >> + /* Only one phi. */ >> + gphi_iterator psi = gsi_start_phis (bb); >> + if (gsi_end_p (psi)) >> + continue; >> + gphi *phi = psi.phi (); >> + gsi_next (&psi); >> + if (!gsi_end_p (psi)) >> + continue; >> + >> + /* Check it is ++i or ++i */ >> + tree next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop)); >> + tree prev = PHI_RESULT (phi); >> + if (idx != prev && idx != next) >> + continue; >> + >> + gimple_stmt_iterator gsi = gsi_start_nondebug_after_labels_bb >> (bb); >> + if (gsi_end_p (gsi)) >> + continue; >> + gimple *s1 = gsi_stmt (gsi); >> + if (!is_gimple_assign (s1) || gimple_assign_lhs (s1) != next >> + || gimple_assign_rhs1 (s1) != prev) >> + continue; >> + >> + gsi_next_nondebug (&gsi); >> + if (!gsi_end_p (gsi) && gsi_stmt (gsi) == cond) >> + return e; >> + } >> + } >> + >> + return NULL; >> +} >> + >> +/* Split the LOOP with NE_EXPR into two loops with GT_EXPR and >> LT_EXPR. */ >> + >> +static bool >> +split_ne_loop (struct loop *loop, edge cond_e, tree step) >> +{ >> + initialize_original_copy_tables (); >> + >> + struct loop *loop2 = loop_version (loop, boolean_true_node, NULL, >> + profile_probability::always (), >> + profile_probability::never (), >> + profile_probability::always (), >> + profile_probability::always (), true); >> + >> + gcc_assert (loop2); >> + update_ssa (TODO_update_ssa); >> + >> + basic_block loop2_cond_exit_bb = get_bb_copy (cond_e->src); >> + free_original_copy_tables (); >> + >> + gcond *gc = as_a (last_stmt (cond_e->src)); >> + gcond *dup_gc = as_a (last_stmt (loop2_cond_exit_bb)); >> + >> + /* Invert edges for gcond. */ >> + if (gimple_cond_code (gc) == EQ_EXPR) >> + { >> + auto invert_edge = [](basic_block bb) { >> + edge out = EDGE_SUCC (bb, 0); >> + edge in = EDGE_SUCC (bb, 1); >> + if (in->flags & EDGE_TRUE_VALUE) >> + std::swap (in, out); >> + in->flags |= EDGE_TRUE_VALUE; >> + in->flags &= ~EDGE_FALSE_VALUE; >> + out->flags |= EDGE_FALSE_VALUE; >> + out->flags &= ~EDGE_TRUE_VALUE; >> + }; >> + >> + invert_edge (gimple_bb (gc)); >> + invert_edge (gimple_bb (dup_gc)); >> + } >> + >> + /* Change if (i != n) to LOOP1:if (i > n) and LOOP2:if (i < n) */ >> + bool inv = expr_invariant_in_loop_p (loop, gimple_cond_lhs (gc)); >> + if (tree_int_cst_sign_bit (step)) >> + inv = !inv; >> + enum tree_code first_loop_code = inv ? LT_EXPR : GT_EXPR; >> + enum tree_code second_loop_code = inv ? GT_EXPR : LT_EXPR; >> + >> + gimple_cond_set_code (gc, first_loop_code); >> + gimple_cond_set_code (dup_gc, second_loop_code); >> + >> + /* Link the exit cond edge to new loop. */ >> + gcond *break_cond = as_a (gimple_copy (gc)); >> + edge pred_e = single_pred_edge (loop->latch); >> + bool simple_loop >> + = pred_e && pred_e->src == cond_e->src && empty_block_p >> (loop->latch); >> + if (simple_loop) >> + gimple_cond_set_code (break_cond, second_loop_code); >> + else >> + gimple_cond_make_true (break_cond); >> + >> + basic_block break_bb = split_edge (cond_e); >> + gimple_stmt_iterator gsi = gsi_last_bb (break_bb); >> + gsi_insert_after (&gsi, break_cond, GSI_NEW_STMT); >> + >> + edge to_exit = single_succ_edge (break_bb); >> + edge to_new_loop = make_edge (break_bb, loop_preheader_edge >> (loop2)->src, 0); >> + to_new_loop->flags |= EDGE_TRUE_VALUE; >> + to_exit->flags |= EDGE_FALSE_VALUE; >> + to_exit->flags &= ~EDGE_FALLTHRU; >> + to_exit->probability = cond_e->probability; >> + to_new_loop->probability = to_exit->probability.invert (); >> + >> + update_ssa (TODO_update_ssa); >> + >> + connect_loop_phis (loop, loop2, to_new_loop, !simple_loop); >> + >> + rewrite_into_loop_closed_ssa_1 (NULL, 0, SSA_OP_USE, loop); >> + if (dump_file && (dump_flags & TDF_DETAILS)) >> + fprintf (dump_file, ";; Loop split on wrap index.\n"); >> + >> + return true; >> +} >> + >> +/* Checks if LOOP contains a suitable NE_EXPR conditional block to >> split. >> +L_H: >> + if (i!=N) >> + S; >> + else >> + goto EXIT; >> + i++; >> + goto L_H; >> + >> +The "i!=N" is like "i>N || i> + >> +L_H: >> + if (i>N) >> + S; >> + else >> + goto EXIT; >> + i++; >> + goto L_H; >> +L1_H: >> + if (i> + S; >> + else >> + goto EXIT; >> + i++; >> + goto L1_H; >> + >> +The loop with "i> + >> +static bool >> +split_loop_on_ne_cond (class loop *loop) >> +{ >> + tree step; >> + edge branch_edge = get_ne_cond_branch (loop, &step); >> + if (!branch_edge) >> + return false; >> + >> + int num = 0; >> + basic_block *bbs = get_loop_body (loop); >> + for (unsigned i = 0; i < loop->num_nodes; i++) >> + num += estimate_num_insns_seq (bb_seq (bbs[i]), >> &eni_size_weights); >> + >> + if (num > param_max_peeled_insns) >> + { >> + free (bbs); >> + return false; >> + } >> + >> + if (!can_copy_bbs_p (bbs, loop->num_nodes)) >> + { >> + free (bbs); >> + return false; >> + } >> + free (bbs); >> + >> + if (split_ne_loop (loop, branch_edge, step)) >> + return true; >> + >> + return false; >> +} >> + >> /* Main entry point. Perform loop splitting on all suitable loops. >> */ >> >> static unsigned int >> @@ -1622,7 +1873,8 @@ tree_ssa_split_loops (void) >> if (optimize_loop_for_size_p (loop)) >> continue; >> >> - if (split_loop (loop) || split_loop_on_cond (loop)) >> + if (split_loop (loop) || split_loop_on_cond (loop) >> + || split_loop_on_ne_cond (loop)) >> { >> /* Mark our containing loop as having had some split inner loops. >> */ >> loop_outer (loop)->aux = loop; diff --git a/gcc/tree-ssa-loop-split.c b/gcc/tree-ssa-loop-split.c index 3a09bbc39e5..c9d161565e4 100644 --- a/gcc/tree-ssa-loop-split.c +++ b/gcc/tree-ssa-loop-split.c @@ -41,6 +41,7 @@ along with GCC; see the file COPYING3. If not see #include "cfghooks.h" #include "gimple-fold.h" #include "gimplify-me.h" +#include "tree-ssa-loop-ivopts.h" /* This file implements two kinds of loop splitting. @@ -1593,6 +1594,468 @@ split_loop_on_cond (struct loop *loop) return do_split; } +/* Filter out type conversions on IDX. + Store the shortest type during conversion to SMALL_TYPE. + Store the longest type during conversion to LARGE_TYPE. */ + +static gimple * +filter_conversions (class loop *loop, tree idx, tree *small_type = NULL, + tree *large_type = NULL) +{ + gcc_assert (TREE_CODE (idx) == SSA_NAME); + gimple *stmt = SSA_NAME_DEF_STMT (idx); + while (is_gimple_assign (stmt) + && flow_bb_inside_loop_p (loop, gimple_bb (stmt))) + { + if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt))) + { + idx = gimple_assign_rhs1 (stmt); + if (small_type) + { + tree type = TREE_TYPE (idx); + if (TYPE_PRECISION (*small_type) > TYPE_PRECISION (type) + || (TYPE_PRECISION (*small_type) == TYPE_PRECISION (type) + && TYPE_UNSIGNED (*small_type) && !TYPE_UNSIGNED (type))) + *small_type = type; + } + if (large_type) + { + tree type = TREE_TYPE (idx); + if (TYPE_PRECISION (*large_type) < TYPE_PRECISION (type) + || (TYPE_PRECISION (*large_type) == TYPE_PRECISION (type) + && !TYPE_UNSIGNED (*large_type) && TYPE_UNSIGNED (type))) + *large_type = type; + } + } + else + break; + + if (TREE_CODE (idx) != SSA_NAME) + break; + stmt = SSA_NAME_DEF_STMT (idx); + } + return stmt; +} + +/* Collection of loop index related elements. */ +struct idx_elements +{ + gcond *gc; + gphi *phi; + gimple *inc_stmt; + tree idx; + tree bnd; + tree step; + tree large_type; + tree small_type; + bool cmp_on_next; +}; + +/* Analyze and get the idx related elements: bnd, + phi, increase stmt from exit edge E, etc. + + i = phi (b, n) + ... + n0 = ik + 1 + n1 = (type)n0 + ... + if (i != bnd) or if (n != bnd) + ... + n = ()nl + + IDX is the i' or n'. */ + +bool +analyze_idx_elements (class loop *loop, edge e, idx_elements &data) +{ + /* Avoid complicated edge. */ + if (e->flags & EDGE_FAKE) + return false; + if (e->src != loop->header && e->src != single_pred (loop->latch)) + return false; + if (!dominated_by_p (CDI_DOMINATORS, loop->latch, e->src)) + return false; + + /* Check gcond. */ + gimple *last = last_stmt (e->src); + if (!last || gimple_code (last) != GIMPLE_COND) + return false; + + /* Get idx and bnd from gcond. */ + gcond *gc = as_a (last); + tree bnd = gimple_cond_rhs (gc); + tree idx = gimple_cond_lhs (gc); + if (expr_invariant_in_loop_p (loop, idx)) + std::swap (idx, bnd); + else if (!expr_invariant_in_loop_p (loop, bnd)) + return false; + if (TREE_CODE (idx) != SSA_NAME) + return false; + + gimple *inc_stmt = NULL; + bool cmp_next = false; + tree small_type = TREE_TYPE (idx); + tree large_type = small_type; + gimple *stmt = filter_conversions (loop, idx, &small_type, &large_type); + /* The idx on gcond is not PHI, it would be next. */ + if (is_gimple_assign (stmt)) + { + tree rhs = gimple_assign_rhs1 (stmt); + if (TREE_CODE (rhs) != SSA_NAME) + return false; + + cmp_next = true; + inc_stmt = stmt; + stmt = filter_conversions (loop, rhs, &small_type, &large_type); + } + + /* Get phi and next. */ + if (gimple_code (stmt) != GIMPLE_PHI || gimple_bb (stmt) != loop->header) + return false; + gphi *phi = as_a (stmt); + tree next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop)); + if (TREE_CODE (next) != SSA_NAME) + return false; + + /* The define of next should be the increasement stmt. */ + stmt = filter_conversions (loop, next, &small_type, &large_type); + if (inc_stmt != NULL && inc_stmt != stmt) + return false; + if (!is_gimple_assign (stmt) + || !flow_bb_inside_loop_p (loop, gimple_bb (stmt))) + return false; + tree_code rhs_code = gimple_assign_rhs_code (stmt); + if (rhs_code != PLUS_EXPR) + return false; + tree step = gimple_assign_rhs2 (stmt); + if (!integer_minus_onep (step) && !integer_onep (step)) + return false; + inc_stmt = stmt; + tree prev = gimple_assign_rhs1 (stmt); + if (TREE_CODE (prev) != SSA_NAME) + return false; + stmt = filter_conversions (loop, prev, &small_type, &large_type); + if (stmt != phi) + return false; + + data.gc = gc; + data.phi = phi; + data.idx = idx; + data.bnd = bnd; + data.step = step; + data.large_type = large_type; + data.small_type = small_type; + data.inc_stmt = inc_stmt; + data.cmp_on_next = cmp_next; + + return true; +} + +/* Check if the loop is possible to wrap at index. + Return the assumption under which the wrap will not happen. + Return NULL_TREE, if wrap will not happen. */ + +static tree +get_wrap_assumption (class loop *loop, edge *exit, idx_elements &data) +{ + int i; + edge e; + if (!single_pred_p (loop->latch) || !empty_block_p (loop->latch)) + return NULL_TREE; + + auto_vec edges = get_loop_exit_edges (loop); + FOR_EACH_VEC_ELT (edges, i, e) + { + if (!analyze_idx_elements (loop, e, data)) + continue; + + /* Check if bound is MAX/MIN val of a integral type. */ + tree bnd = data.bnd; + tree bnd_type = TREE_TYPE (bnd); + if (!INTEGRAL_TYPE_P (bnd_type) || !TYPE_UNSIGNED (bnd_type)) + continue; + if (tree_int_cst_equal (bnd, TYPE_MAX_VALUE (bnd_type)) + || tree_int_cst_equal (bnd, TYPE_MIN_VALUE (bnd_type))) + continue; + + /* Check if it is "idx != bnd" or "idx < bnd". */ + gcond *gc = data.gc; + enum tree_code code = gimple_cond_code (gc); + if (bnd == gimple_cond_lhs (gc)) + code = swap_tree_comparison (code); + if ((e->flags & EDGE_TRUE_VALUE) && code == EQ_EXPR) + code = NE_EXPR; + if (code != NE_EXPR && code != LT_EXPR && code != GT_EXPR) + continue; + + /* Check if idx is iv with base and step. */ + affine_iv iv; + tree iv_niters = NULL_TREE; + tree idx = PHI_RESULT (data.phi); + if (!simple_iv_with_niters (loop, loop_containing_stmt (gc), idx, &iv, + &iv_niters, false)) + continue; + if (!iv.base || !iv.step || !tree_int_cst_equal (iv.step, data.step)) + continue; + + bool is_negative = tree_int_cst_sign_bit (iv.step); + enum tree_code expect_code = is_negative ? GT_EXPR : LT_EXPR; + if (code != NE_EXPR && code != expect_code) + continue; + + /* Update the type for base, bound and the max value of boundary. */ + tree base = iv.base; + tree small_type = data.small_type; + tree large_type = data.large_type; + tree max_min_bnd = is_negative ? TYPE_MIN_VALUE (small_type) + : TYPE_MAX_VALUE (small_type); + if (large_type != TREE_TYPE (base)) + base = fold_convert (large_type, base); + if (large_type != TREE_TYPE (bnd)) + bnd = fold_convert (large_type, bnd); + if (large_type != small_type) + max_min_bnd = fold_convert (large_type, max_min_bnd); + + /* There is no wrap if bnd <= max value && base <= bnd. */ + enum tree_code expect_code1 = is_negative ? GE_EXPR : LE_EXPR; + tree no_wrap + = fold_build2 (expect_code1, boolean_type_node, bnd, max_min_bnd); + no_wrap + = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, no_wrap, + fold_build2 (expect_code1, boolean_type_node, base, bnd)); + + if (integer_zerop (no_wrap)) + continue; + + *exit = e; + return no_wrap; + } + + return NULL_TREE; +} + +/* Update the idx and bnd with a suitable type for no wrap/oveflow loop. + Suitable type would be the largest type of the type conversion which + occur on index, if the largest type is unsigned, using sizetype. */ + +static bool +update_idx_bnd_type (class loop *loop, idx_elements &data) +{ + gphi *phi = data.phi; + tree type = TREE_TYPE (PHI_RESULT (phi)); + tree suitable_type = data.large_type; + if (TYPE_UNSIGNED (suitable_type)) + { + if (TYPE_PRECISION (suitable_type) == TYPE_PRECISION (sizetype)) + return false; + suitable_type = sizetype; + } + + /* New base and new bound. */ + tree bnd = data.bnd; + edge pre_e = loop_preheader_edge (loop); + tree base = PHI_ARG_DEF_FROM_EDGE (phi, pre_e); + tree new_base = fold_convert (suitable_type, base); + tree new_bnd = fold_convert (suitable_type, bnd); + gimple_seq seq = NULL; + new_base = force_gimple_operand (new_base, &seq, true, NULL_TREE); + if (seq) + gsi_insert_seq_on_edge_immediate (pre_e, seq); + seq = NULL; + new_bnd = force_gimple_operand (new_bnd, &seq, true, NULL_TREE); + if (seq) + gsi_insert_seq_on_edge_immediate (pre_e, seq); + + /* new_i = phi (new_b, new_n) + new_n = new_i + 1 */ + edge latch_e = loop_latch_edge (loop); + const char *name = "idx"; + tree new_idx = make_temp_ssa_name (suitable_type, NULL, name); + tree new_next = make_temp_ssa_name (suitable_type, NULL, name); + gphi *newphi = create_phi_node (new_idx, loop->header); + add_phi_arg (newphi, new_base, pre_e, UNKNOWN_LOCATION); + add_phi_arg (newphi, new_next, latch_e, UNKNOWN_LOCATION); + + /* New increase stmt. */ + gimple *inc_stmt = data.inc_stmt; + tree step = gimple_assign_rhs2 (inc_stmt); + if (tree_int_cst_sign_bit(step)) + { + wide_int v = wi::to_wide (step); + v = wide_int::from (v, TYPE_PRECISION (suitable_type), + SIGNED); + + step = wide_int_to_tree (suitable_type, v); + } + else + step = fold_convert (suitable_type, step); + new_idx = PHI_RESULT (newphi); + tree_code inc_code = gimple_assign_rhs_code (inc_stmt); + gimple *new_inc = gimple_build_assign (new_next, inc_code, new_idx, step); + gimple_stmt_iterator gsi = gsi_for_stmt (inc_stmt); + gsi_insert_before (&gsi, new_inc, GSI_SAME_STMT); + + /* Update gcond. */ + gcond *gc = data.gc; + bool inv = bnd == gimple_cond_lhs (gc); + tree cmp_idx = data.cmp_on_next ? new_next : new_idx; + gimple_cond_set_lhs (gc, inv ? new_bnd : cmp_idx); + gimple_cond_set_rhs (gc, inv ? cmp_idx : new_bnd); + update_stmt (gc); + + /* next = (next type)new_next + And remove next = prev + 1. */ + tree next = gimple_assign_lhs (inc_stmt); + type = TREE_TYPE (next); + gimple *stmt = gimple_build_assign (next, fold_convert (type, new_next)); + gsi = gsi_for_stmt (inc_stmt); + gsi_insert_before (&gsi, stmt, GSI_SAME_STMT); + + gsi = gsi_for_stmt (inc_stmt); + gsi_remove (&gsi, true); + + /* prev = (prev type)new_prev + And remove prev = phi. */ + tree idx = PHI_RESULT (phi); + type = TREE_TYPE (idx); + stmt = gimple_build_assign (idx, fold_convert (type, new_idx)); + gsi = gsi_after_labels (loop->header); + gsi_insert_before (&gsi, stmt, GSI_SAME_STMT); + + gsi = gsi_for_stmt (phi); + gsi_remove (&gsi, true); + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, ";; Loop index type is updated to use faster type.\n"); + + return true; +} + +/* Split out a new loop which would not wrap, + under the guard that NO_WRAP_COND will not be true. */ + +static bool +split_wrap_boundary (class loop *loop, edge e, tree no_wrap_cond, + bool is_negative_step) +{ + /* Convert the condition into a suitable gcond. */ + gimple_seq stmts = NULL; + no_wrap_cond = force_gimple_operand_1 (no_wrap_cond, &stmts, + is_gimple_condexpr, NULL_TREE); + + /* Version the loop. */ + initialize_original_copy_tables (); + basic_block cond_bb; + loop_version (loop, no_wrap_cond, &cond_bb, + profile_probability::very_likely (), + profile_probability::very_unlikely (), + profile_probability::very_likely (), + profile_probability::very_unlikely (), true); + free_original_copy_tables (); + + /* Insert the statements that feed COND. */ + if (stmts) + { + gimple_stmt_iterator gsi = gsi_last_bb (cond_bb); + gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT); + } + + /* Update gcond code. */ + gcond *gc = as_a (last_stmt (e->src)); + enum tree_code code = gimple_cond_code (gc); + enum tree_code new_code; + bool inv = expr_invariant_in_loop_p (loop, gimple_cond_lhs (gc)); + if (is_negative_step) + new_code = inv ? LT_EXPR : GT_EXPR; + else + new_code = inv ? GT_EXPR : LT_EXPR; + if (code == NE_EXPR || code == EQ_EXPR) + gimple_cond_set_code (gc, new_code); + + /* Swap edge. */ + if (code == EQ_EXPR) + { + edge out = EDGE_SUCC (e->src, 0); + edge in = EDGE_SUCC (e->src, 1); + if (in->flags & EDGE_TRUE_VALUE) + std::swap (in, out); + in->flags |= EDGE_TRUE_VALUE; + in->flags &= ~EDGE_FALSE_VALUE; + out->flags |= EDGE_FALSE_VALUE; + out->flags &= ~EDGE_TRUE_VALUE; + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, ";; Loop split on wrap index.\n"); + + return true; +} + +/* Split loop if there is possible wrap. + For example: + transform + + void + foo (int *a, int *b, unsigned l, unsigned u_n) + { + while (++l != u_n) + a[l] = b[l] + 1; + } + + to: + if (l < u_n) + { + int li = l; + int n = u_n; + while (++li < n) + a[li] = b[li] + 1; + l = li; + } + else + while (++l != n) + a[l] = b[l] + 1; + */ +static bool +split_loop_on_wrap (class loop *loop) +{ + edge e; + idx_elements data; + tree no_wrap = get_wrap_assumption (loop, &e, data); + + if (!no_wrap) + return false; + + int num = 0; + basic_block *bbs = get_loop_body (loop); + for (unsigned i = 0; i < loop->num_nodes; i++) + num += estimate_num_insns_seq (bb_seq (bbs[i]), &eni_size_weights); + + if (num > param_max_peeled_insns) + { + free (bbs); + return false; + } + + if (!can_copy_bbs_p (bbs, loop->num_nodes)) + { + free (bbs); + return false; + } + + free (bbs); + + if (integer_onep (no_wrap)) + return update_idx_bnd_type (loop, data); +