From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gcc-bugzilla@gcc.gnu.org>
Received: by sourceware.org (Postfix, from userid 48)
	id 94D5D3858CD1; Tue,  6 Feb 2024 11:33:34 +0000 (GMT)
DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 94D5D3858CD1
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org;
	s=default; t=1707219214;
	bh=o3Qe2PgOZ6IPV7kcLvXXhlZHbea+F5VEYPny5tyBrjk=;
	h=From:To:Subject:Date:In-Reply-To:References:From;
	b=P/KY7nX1aREa9PhB4F/sLJCqgYr4cdyUxN24GSVHFBviEkm0TCTVv8xmK+BGJIBmR
	 KHEnV8SqDbNWAAKDb6qAK1vU7niBy/jyVRyl/5aAsu8ScDwa10IQkQ798DgAQX1fBV
	 9cNUwQ22oOCXtPbfzGjejrbMFHtGA7937Ze1324c=
From: "rguenth at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug tree-optimization/113703] ivopts miscompiles loop
Date: Tue, 06 Feb 2024 11:33:32 +0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: tree-optimization
X-Bugzilla-Version: 14.0
X-Bugzilla-Keywords: needs-bisection, wrong-code
X-Bugzilla-Severity: normal
X-Bugzilla-Who: rguenth at gcc dot gnu.org
X-Bugzilla-Status: NEW
X-Bugzilla-Resolution: 
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags: 
X-Bugzilla-Changed-Fields: 
Message-ID: <bug-113703-4-pDHTLHiXOu@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-113703-4@http.gcc.gnu.org/bugzilla/>
References: <bug-113703-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
List-Id: <gcc-bugs.sourceware.org>

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=3D113703

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
It's going wrong in iv_elimination_compare_lt which tries to exactly handle
this kind of loop:

   We aim to handle the following situation:

   sometype *base, *p;
   int a, b, i;

   i =3D a;
   p =3D p_0 =3D base + a;

   do
     {
       bla (*p);
       p++;
       i++;
     }
   while (i < b);

   Here, the number of iterations of the loop is (a + 1 > b) ? 0 : b - a - =
1.
   We aim to optimize this to

   p =3D p_0 =3D base + a;
   do
     {
       bla (*p);
       p++;
     }
   while (p < p_0 - a + b);

   This preserves the correctness, since the pointer arithmetics does not
   overflow.  More precisely:

   1) if a + 1 <=3D b, then p_0 - a + b is the final value of p, hence ther=
e is
no
      overflow in computing it or the values of p.
   2) if a + 1 > b, then we need to verify that the expression p_0 - a does=
 not
      overflow.  To prove this, we use the fact that p_0 =3D base + a.

there's either a hole in that logic or the implementation is off.

  /* Finally, check that CAND->IV->BASE - CAND->IV->STEP * A does not
     overflow.  */
  offset =3D fold_build2 (MULT_EXPR, TREE_TYPE (cand->iv->step),
                        cand->iv->step,
                        fold_convert (TREE_TYPE (cand->iv->step), a));
  if (!difference_cannot_overflow_p (data, cand->iv->base, offset))
    return false;

where 'A' is 'i', CAND->IV->BASE is 'p + i' and CAND->IV->STEP is 1
as 'sizetype'.

That just checks that (p + i) - i doesn't overflow.

Somehow it misses to prove p + b doesn't overflow since we end up with
p' < (p + i) + (n - i) aka p' < p + n.=