From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lj1-x236.google.com (mail-lj1-x236.google.com [IPv6:2a00:1450:4864:20::236]) by sourceware.org (Postfix) with ESMTPS id C9C723858D20 for ; Fri, 28 Jul 2023 13:15:49 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org C9C723858D20 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com Received: by mail-lj1-x236.google.com with SMTP id 38308e7fff4ca-2b9c907bc68so22522211fa.2 for ; Fri, 28 Jul 2023 06:15:49 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1690550148; x=1691154948; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=SvJkbYOfcJ33j25/B1zxnlYq6aHZLfftJPXVRyQCi5o=; b=Wp11f6HH87rHv5ZitW7nyZf0jlTcA95qACTC3/6LViLZ/VoG+0Jngv41SYa7uFx8ZW 2P5skdZv44hAVKs6NxaZFr1m4KeJKTHmj7HZYdN5GymN+t1eS5cpkZ+1ybVswmyA3hIz y/QefeczB8sdkXSnnuZUWnYjFKqYRPnalxOM+Vfkdlx/VpYPZvQNGA9MYw/JCDSXyCI+ cnOT3SpXZ4eCJbe0G72S0BepRRVdJg7b4CYUPKUSQsk/c+wd0ZobceawY5XewBvSL51W whc5H4wVRKKZgHkkc9M7uZvrJXBZebLOAODk3ZiZr1AKZ0ZAY4UU9GbblnAic37yt3Ua 48zw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690550148; x=1691154948; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=SvJkbYOfcJ33j25/B1zxnlYq6aHZLfftJPXVRyQCi5o=; b=UpWlvR7Rjnk3uPFvZN7kmjBrfyjmUvj8/DmCosPDML4AFno9SH9zBV22JlCKBIRXN8 5nr9uiIa/XwJcBLBZ7ot049KPEvtRFfyJXxyPcVgISEDm8kmSPsMO5zvb+ItVGk3Sihy xzC6khlVnaEKHqzSQBX/LaWUjMEEZjQjQr+E+PbbdL/hUyDvbjwCmPr0GWM5LkNUDnpV u2WfeLfsoG6MlLACsNV2otfmcefmF/MYBfw7T/LWmVzSwVOlul5Z/4xgIHzAVe0/qiLZ LfJac2MaUWmW+5BaOQaNJ93kpicyqAeW8FUdAF061Zi2iKkjEZ9zKPz/be8a3QG/ctJk 0yhg== X-Gm-Message-State: ABy/qLYiEcT2qpBoKIUW0o5+huY9zKYRcRwGvUkRCqVPgp/r+xW0O3vk IGP274/Q+2Vn/9dOR+lAZ/9aAlcDTNgp4UXWhOA= X-Google-Smtp-Source: APBJJlHhfUNeN+Ghk0l6QSIodf0j8NTBItQ14qtSmAY59l7rQWe9/2CP7ya7due1PMzS9RXjBIex64zQB06H6O714mY= X-Received: by 2002:a2e:8952:0:b0:2b7:33a6:f2c0 with SMTP id b18-20020a2e8952000000b002b733a6f2c0mr2113507ljk.4.1690550147894; Fri, 28 Jul 2023 06:15:47 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Richard Biener Date: Fri, 28 Jul 2023 15:15:34 +0200 Message-ID: Subject: Re: Loop-split improvements, part 3 To: Jan Hubicka Cc: gcc-patches@gcc.gnu.org Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-7.3 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,GIT_PATCH_0,KAM_NUMSUBJECT,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,TXREP,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: On Fri, Jul 28, 2023 at 2:57=E2=80=AFPM Jan Hubicka via Gcc-patches wrote: > > Hi, > This patch extends tree-ssa-loop-split to understand test of the form > if (i=3D=3D0) > and > if (i!=3D0) > which triggers only during the first iteration. Naturally we should > also be able to trigger last iteration or split into 3 cases if > the test indeed can fire in the middle of the loop. > > Last iteration is bit trickier pattern matching so I want to do it > incrementally, but I implemented easy case using value range that handled > loops with constant iterations. > > The testcase gets misupdated profile, I will also fix that incrementally. > > Bootstrapped/regtested x86_64-linux, OK? OK, though I think we can handle more loops by simply conservatively peelin= g one iteration at the beginning/end with such conditions and would be not su= bject to all other limitations the loop splitting pass has? Richard. > gcc/ChangeLog: > > PR middle-end/77689 > * tree-ssa-loop-split.cc: Include value-query.h. > (split_at_bb_p): Analyze cases where EQ/NE can be turned > into LT/LE/GT/GE; return updated guard code. > (split_loop): Use guard code. > > gcc/testsuite/ChangeLog: > > PR middle-end/77689 > * g++.dg/tree-ssa/loop-split-1.C: New test. > > diff --git a/gcc/testsuite/g++.dg/tree-ssa/loop-split-1.C b/gcc/testsuite= /g++.dg/tree-ssa/loop-split-1.C > new file mode 100644 > index 00000000000..9581438b536 > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/loop-split-1.C > @@ -0,0 +1,23 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O3 -fdump-tree-lsplit-details -std=3Dc++11" } */ > +#include > +#include > + > +constexpr unsigned s =3D 100000000; > + > +int main() > +{ > + std::vector a, b, c; > + a.reserve(s); > + b.reserve(s); > + c.reserve(s); > + > + for(unsigned i =3D 0; i < s; ++i) > + { > + if(i =3D=3D 0) > + a[i] =3D b[i] * c[i]; > + else > + a[i] =3D (b[i] + c[i]) * c[i-1] * std::log(i); > + } > +} > +/* { dg-final { scan-tree-dump-times "loop split" 1 "lsplit" } } */ > diff --git a/gcc/tree-ssa-loop-split.cc b/gcc/tree-ssa-loop-split.cc > index 70cd0aaefa7..641346cba70 100644 > --- a/gcc/tree-ssa-loop-split.cc > +++ b/gcc/tree-ssa-loop-split.cc > @@ -42,6 +42,7 @@ along with GCC; see the file COPYING3. If not see > #include "gimple-fold.h" > #include "gimplify-me.h" > #include "print-tree.h" > +#include "value-query.h" > > /* This file implements two kinds of loop splitting. > > @@ -75,7 +76,8 @@ along with GCC; see the file COPYING3. If not see > point in *BORDER and the comparison induction variable in IV. */ > > static tree > -split_at_bb_p (class loop *loop, basic_block bb, tree *border, affine_iv= *iv) > +split_at_bb_p (class loop *loop, basic_block bb, tree *border, affine_iv= *iv, > + enum tree_code *guard_code) > { > gcond *stmt; > affine_iv iv2; > @@ -87,19 +89,6 @@ split_at_bb_p (class loop *loop, basic_block bb, tree = *border, affine_iv *iv) > > enum tree_code code =3D gimple_cond_code (stmt); > > - /* Only handle relational comparisons, for equality and non-equality > - we'd have to split the loop into two loops and a middle statement. = */ > - switch (code) > - { > - case LT_EXPR: > - case LE_EXPR: > - case GT_EXPR: > - case GE_EXPR: > - break; > - default: > - return NULL_TREE; > - } > - > if (loop_exits_from_bb_p (loop, bb)) > return NULL_TREE; > > @@ -129,6 +118,56 @@ split_at_bb_p (class loop *loop, basic_block bb, tre= e *border, affine_iv *iv) > if (!iv->no_overflow) > return NULL_TREE; > > + /* Only handle relational comparisons, for equality and non-equality > + we'd have to split the loop into two loops and a middle statement. = */ > + switch (code) > + { > + case LT_EXPR: > + case LE_EXPR: > + case GT_EXPR: > + case GE_EXPR: > + break; > + case NE_EXPR: > + case EQ_EXPR: > + /* If the test check for first iteration, we can handle NE/EQ > + with only one split loop. */ > + if (operand_equal_p (iv->base, iv2.base, 0)) > + { > + if (code =3D=3D EQ_EXPR) > + code =3D !tree_int_cst_sign_bit (iv->step) ? LE_EXPR : GE_E= XPR; > + else > + code =3D !tree_int_cst_sign_bit (iv->step) ? GT_EXPR : LT_E= XPR; > + break; > + } > + /* Similarly when the test checks for minimal or maximal > + value range. */ > + else > + { > + int_range<2> r; > + get_global_range_query ()->range_of_expr (r, op0, stmt); > + if (!r.varying_p () && !r.undefined_p () > + && TREE_CODE (op1) =3D=3D INTEGER_CST) > + { > + wide_int val =3D wi::to_wide (op1); > + if (known_eq (val, r.lower_bound ())) > + { > + code =3D (code =3D=3D EQ_EXPR) ? LE_EXPR : GT_EXPR; > + break; > + } > + else if (known_eq (val, r.upper_bound ())) > + { > + code =3D (code =3D=3D EQ_EXPR) ? GE_EXPR : LT_EXPR; > + break; > + } > + } > + } > + /* TODO: We can compare with exit condition; it seems that testin= g for > + last iteration is common case. */ > + return NULL_TREE; > + default: > + return NULL_TREE; > + } > + > if (dump_file && (dump_flags & TDF_DETAILS)) > { > fprintf (dump_file, "Found potential split point: "); > @@ -143,6 +182,7 @@ split_at_bb_p (class loop *loop, basic_block bb, tree= *border, affine_iv *iv) > } > > *border =3D iv2.base; > + *guard_code =3D code; > return op0; > } > > @@ -566,8 +606,9 @@ split_loop (class loop *loop1) > } > > /* Find a splitting opportunity. */ > + enum tree_code guard_code; > for (i =3D 0; i < loop1->num_nodes; i++) > - if ((guard_iv =3D split_at_bb_p (loop1, bbs[i], &border, &iv))) > + if ((guard_iv =3D split_at_bb_p (loop1, bbs[i], &border, &iv, &guard= _code))) > { > profile_count entry_count =3D loop_preheader_edge (loop1)->count = (); > /* Handling opposite steps is not implemented yet. Neither > @@ -585,7 +626,6 @@ split_loop (class loop *loop1) > gcond *guard_stmt =3D as_a (*gsi_last_bb (bbs[i])); > tree guard_init =3D PHI_ARG_DEF_FROM_EDGE (phi, > loop_preheader_edge (loo= p1)); > - enum tree_code guard_code =3D gimple_cond_code (guard_stmt); > > /* Loop splitting is implemented by versioning the loop, placing > the new loop after the old loop, make the first loop iterate