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 8A7B43858D37; Thu, 30 Nov 2023 09:01:36 +0000 (GMT)
DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 8A7B43858D37
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org;
	s=default; t=1701334896;
	bh=rq5zhnoUVE2Hb45XIvD26FFbXZxFTPCcJhfLbmWPag4=;
	h=From:To:Subject:Date:From;
	b=kJTfwUVc949w3skCZk53VWtMZJcu2xYE8LUUApZR5IHMTy9fc10lj5RS3/SkEsgnC
	 7uDTLUD7Tn2R2msYtmjqqZ5JmfA+qVEsBCnQovXQcmDGiZ2m9dZR/LV+0l/PgV/gLj
	 upktSmEHkOAX8Uvd1Q8DM2EuWOZzxWxmyowug7fE=
From: "hliu at amperecomputing dot com" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug tree-optimization/112774] New: Vectorize the loop by inferring
 nonwrapping information from arrays
Date: Thu, 30 Nov 2023 09:01:36 +0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: new
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: tree-optimization
X-Bugzilla-Version: 14.0
X-Bugzilla-Keywords: 
X-Bugzilla-Severity: normal
X-Bugzilla-Who: hliu at amperecomputing dot com
X-Bugzilla-Status: UNCONFIRMED
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: bug_id short_desc product version bug_status
 bug_severity priority component assigned_to reporter target_milestone
Message-ID: <bug-112774-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=3D112774

            Bug ID: 112774
           Summary: Vectorize the loop by inferring nonwrapping
                    information from arrays
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: hliu at amperecomputing dot com
  Target Milestone: ---

This case extracted from another benchmark and it is simpler than the case =
in
PR101450, as it has the additional boundary information from the array:

    int A[1024 * 2];

    int foo (unsigned offset, unsigned N)=20
    {
      int sum =3D 0;

      for (unsigned i =3D 0; i < N; i++)
        sum +=3D A[i + offset];

      return sum;
    }

The Gimple before the vectorization pass is:

    <bb 3> [local count: 955630224]:
    # sum_12 =3D PHI <sum_9(6), 0(5)>
    # i_14 =3D PHI <i_10(6), 0(5)>
    _1 =3D offset_8(D) + i_14;
    _2 =3D A[_1];
    sum_9 =3D _2 + sum_12;
    i_10 =3D i_14 + 1;

GCC failed to vectorize it as it the chrec "{offset_8, +, 1}_1" may
overflow/wrap. I summarized more details in the email:
https://gcc.gnu.org/pipermail/gcc/2023-November/242854.html

Actually, GCC already knows it won't by inferring the range from the array
(in estimate_numbers_of_iterations -> infer_loop_bounds_from_undefined ->
infer_loop_bounds_from_array):

    Induction variable (unsigned int) offset_8(D) + 1 * iteration does not =
wrap
in statement _2 =3D A[_1];
     in loop 1.
    Statement _2 =3D A[_1];
     is executed at most 2047 (bounded by 2047) + 1 times in loop 1.

We can use re-use this information to vectorize this case. I already have a
simple patch to achieve this, and will send it out later (after doing more
tests).=