From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lf1-x12e.google.com (mail-lf1-x12e.google.com [IPv6:2a00:1450:4864:20::12e]) by sourceware.org (Postfix) with ESMTPS id 6DA723858298 for ; Thu, 10 Aug 2023 13:54:56 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 6DA723858298 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-lf1-x12e.google.com with SMTP id 2adb3069b0e04-4fe0fe622c3so1399841e87.2 for ; Thu, 10 Aug 2023 06:54:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1691675694; x=1692280494; h=content-transfer-encoding:to:subject:message-id:date:from :in-reply-to:references:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=o61vwM5+drB/tYjSiKpUni3UT9ltVblSDlBHC0aDkno=; b=Tx4ylug77swEcryQIeIR6LzDecBvf3UqOrIvCY0ysarIn/F1ZZLc1INsGuSMUdL6Hw HF4INxZI6f3RTcyoOeyJ06W78e8BT7JTPxmVpPVUCOBJK69cVc/Fdb2lFPnLLig/5AmL Rcs51hsha5ghoU8qmx9D6/9QgBxFdyZnvKzRvSpdfi3Mip4iU/YXbqBlpxfMhwhU0rxi Ojl7esIbmmtEoFIqrNc/d8Ca2aQyHRWvL73QSLaepHV1gwFO0RiODja+SV2otU+nS8Gp QdPB6K/7JDWRysi9ywvlkWXpYStIoYDShnuABFG5tgPq1TgIJbIDF2/IshlZLLKNVYzX UHbQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1691675694; x=1692280494; h=content-transfer-encoding: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=o61vwM5+drB/tYjSiKpUni3UT9ltVblSDlBHC0aDkno=; b=VyPD+IklCK//NzRAwvrB+X3gd6MEyzrUMdQOarfmxJ2scbJIYzqb7vHhQ9QT2tydit uKAubCZEt0N+0118XWYbSBMvt24YQjh+e4UAyiMAL/WjEkGY7tUXz6bWx0kgyGsQNMjh EQ2t+AqQC5nb14z+ElxNmA180Ha/7wUoBKeNeo+chHmiT83r2LOLVav1JJepsHzO5cG9 3+5+jyruHjqBAor+//mQ1FkAFlM7lKF0IJlFl5d/7pdoLmiEbUqGyqw17AVjeb5u3FBO xnxsDA8HGupSeQ66AF4Zbrf/qCkn6OKjgmdjFuTzIfmK/CNx6e47VVGAyYXPJo5EFc5L fgVQ== X-Gm-Message-State: AOJu0Ywy9Qv2RXiizVTIPJvbKK0ux9T1JdVRELverA5nwnMonPhZmAyX EBvWGtZVo5Dw9T6tABizUn/Xx3Dr/7LezaV3iCnXGY6y X-Google-Smtp-Source: AGHT+IFqNXt/5G71WxZ/hoq94UN6FMWa1SgGmWhXl/q/oSW8ugnXyPihFjmrFSdLDFXKSQUlMBNXDY2cW3oS53CaR7k= X-Received: by 2002:a05:6512:1095:b0:4fe:1681:9377 with SMTP id j21-20020a056512109500b004fe16819377mr2337513lfg.44.1691675693683; Thu, 10 Aug 2023 06:54:53 -0700 (PDT) MIME-Version: 1.0 References: <20230809161340.2659544-1-apinski@marvell.com> In-Reply-To: From: Richard Biener Date: Thu, 10 Aug 2023 15:53:43 +0200 Message-ID: Subject: Re: [PATCH] VR-VALUES: Simplify comparison using range pairs To: Richard Biener via Gcc-patches , Andrew Pinski , Richard Biener , richard.sandiford@arm.com Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-7.1 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,GIT_PATCH_0,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,TXREP 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 Thu, Aug 10, 2023 at 3:44=E2=80=AFPM Richard Sandiford wrote: > > Richard Biener via Gcc-patches writes: > > On Wed, Aug 9, 2023 at 6:16=E2=80=AFPM Andrew Pinski via Gcc-patches > > wrote: > >> > >> If `A` has a range of `[0,0][100,INF]` and the comparison > >> of `A < 50`. This should be optimized to `A <=3D 0` (which then > >> will be optimized to just `A =3D=3D 0`). > >> This patch implement this via a new function which sees if > >> the constant of a comparison is in the middle of 2 range pairs > >> and change the constant to the either upper bound of the first pair > >> or the lower bound of the second pair depending on the comparison. > >> > >> This is the first step in fixing the following PRS: > >> PR 110131, PR 108360, and PR 108397. > >> > >> OK? Bootstrapped and tested on x86_64-linux-gnu with no regressions. > > > > > > > >> gcc/ChangeLog: > >> > >> * vr-values.cc (simplify_compare_using_range_pairs): New funct= ion. > >> (simplify_using_ranges::simplify_compare_using_ranges_1): Call > >> it. > >> > >> gcc/testsuite/ChangeLog: > >> > >> * gcc.dg/tree-ssa/vrp124.c: New test. > >> * gcc.dg/pr21643.c: Disable VRP. > >> --- > >> gcc/testsuite/gcc.dg/pr21643.c | 6 ++- > >> gcc/testsuite/gcc.dg/tree-ssa/vrp124.c | 44 +++++++++++++++++ > >> gcc/vr-values.cc | 65 +++++++++++++++++++++++++= + > >> 3 files changed, 114 insertions(+), 1 deletion(-) > >> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp124.c > >> > >> diff --git a/gcc/testsuite/gcc.dg/pr21643.c b/gcc/testsuite/gcc.dg/pr2= 1643.c > >> index 4e7f93d351a..7f121d7006f 100644 > >> --- a/gcc/testsuite/gcc.dg/pr21643.c > >> +++ b/gcc/testsuite/gcc.dg/pr21643.c > >> @@ -1,6 +1,10 @@ > >> /* PR tree-optimization/21643 */ > >> /* { dg-do compile } */ > >> -/* { dg-options "-O2 -fdump-tree-reassoc1-details --param logical-op-= non-short-circuit=3D1" } */ > >> +/* Note VRP is able to transform `c >=3D 0x20` in f7 > >> + to `c >=3D 0x21` since we want to test > >> + reassociation and not VRP, turn it off. */ > >> + > >> +/* { dg-options "-O2 -fdump-tree-reassoc1-details --param logical-op-= non-short-circuit=3D1 -fno-tree-vrp" } */ > >> > >> int > >> f1 (unsigned char c) > >> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp124.c b/gcc/testsuite/gc= c.dg/tree-ssa/vrp124.c > >> new file mode 100644 > >> index 00000000000..6ccbda35d1b > >> --- /dev/null > >> +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp124.c > >> @@ -0,0 +1,44 @@ > >> +/* { dg-do compile } */ > >> +/* { dg-options "-O2 -fdump-tree-optimized" } */ > >> + > >> +/* Should be optimized to a =3D=3D -100 */ > >> +int g(int a) > >> +{ > >> + if (a =3D=3D -100 || a >=3D 0) > >> + ; > >> + else > >> + return 0; > >> + return a < 0; > >> +} > >> + > >> +/* Should optimize to a =3D=3D 0 */ > >> +int f(int a) > >> +{ > >> + if (a =3D=3D 0 || a > 100) > >> + ; > >> + else > >> + return 0; > >> + return a < 50; > >> +} > >> + > >> +/* Should be optimized to a =3D=3D 0. */ > >> +int f2(int a) > >> +{ > >> + if (a =3D=3D 0 || a > 100) > >> + ; > >> + else > >> + return 0; > >> + return a < 100; > >> +} > >> + > >> +/* Should optimize to a =3D=3D 100 */ > >> +int f1(int a) > >> +{ > >> + if (a < 0 || a =3D=3D 100) > >> + ; > >> + else > >> + return 0; > >> + return a > 50; > >> +} > >> + > >> +/* { dg-final { scan-tree-dump-not "goto " "optimized" } } */ > >> diff --git a/gcc/vr-values.cc b/gcc/vr-values.cc > >> index a4fddd62841..1262e7cf9f0 100644 > >> --- a/gcc/vr-values.cc > >> +++ b/gcc/vr-values.cc > >> @@ -968,9 +968,72 @@ test_for_singularity (enum tree_code cond_code, t= ree op0, > >> if (operand_equal_p (min, max, 0) && is_gimple_min_invariant (m= in)) > >> return min; > >> } > >> + > >> return NULL; > >> } > >> > >> +/* Simplify integer comparisons such that the constant is one of the = range pairs. > >> + For an example, > >> + A has a range of [0,0][100,INF] > >> + and the comparison of `A < 50`. > >> + This should be optimized to `A <=3D 0` > >> + and then test_for_singularity can optimize it to `A =3D=3D 0`. *= / > >> + > >> +static bool > >> +simplify_compare_using_range_pairs (tree_code &cond_code, tree &op0, = tree &op1, > >> + const value_range *vr) > >> +{ > >> + if (TREE_CODE (op1) !=3D INTEGER_CST > >> + || vr->num_pairs () < 2) > >> + return false; > >> + auto val_op1 =3D wi::to_wide (op1); > >> + tree type =3D TREE_TYPE (op0); > >> + auto sign =3D TYPE_SIGN (type); > >> + auto p =3D vr->num_pairs (); > >> + /* Find the value range pair where op1 > >> + is in the middle of if one exist. */ > >> + for (unsigned i =3D 1; i < p; i++) > >> + { > >> + auto lower =3D vr->upper_bound (i - 1); > >> + auto upper =3D vr->lower_bound (i); > >> + if (wi::lt_p (val_op1, lower, sign)) > >> + continue; > >> + if (wi::gt_p (val_op1, upper, sign)) > >> + continue; > > > > That looks like a linear search - it looks like m_base[] is > > a sorted array of values so we should be able to > > binary search here? array_slice::bsearch could be > > used if it existed (simply port it over from vec<> and > > use array_slice from that)? > > Better to use std::lower_bound IMO, rather than implement our > own custom bsearch. Though we have that available already in vec::, just need to port that over to array_slice:: and use that from vec::? > Thanks, > Richard