[Bug tree-optimization/57634] New: Missed vectorization for a "fixed point multiplication" reduction

[Bug tree-optimization/57634] New: Missed vectorization for a "fixed point multiplication" reduction

[vincenzo.innocente at cern dot ch]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57634

            Bug ID: 57634
           Summary: Missed vectorization for a "fixed point
                    multiplication" reduction
           Product: gcc
           Version: 4.9.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: vincenzo.innocente at cern dot ch

I the following code the loop in "red" does not vectorize "because"of
note: reduction: not commutative/associative: s_12 = (unsigned int) _11;
if I use "unsigned long long" everywhere as in redl the reason becomes
reduction: not commutative/associative: s_10 = temp_9 >> 23;

the multiplication in itself vectorize…  (for unsigned!)

compiled as
c++ -std=c++11 -march=corei7-avx -mavx2 -Ofast -S FixedF.cc
-ftree-vectorizer-verbose=2 -Wall
with gcc version 4.9.0 20130607 (experimental) [trunk revision 199812] (GCC) 


inline
unsigned int mult(unsigned int a, unsigned int b) {
  typedef unsigned long long ull; // (to support >>)
  // a and b are of the form 1.m with m of Q bits  as int is therefore max
2^(Q+2)-1. a*b is therefore < 2^(2*(Q+2)) 
  constexpr int Q = 23;
  constexpr unsigned long long K  = (1 << (Q-1));
  ull  temp = (ull)(a) * (ull)(b); // result type is operand's type
  // Rounding; mid values are rounded up
  temp += K;
  // Correct by dividing by base   
  return (temp >> Q);  
}

inline
unsigned long long multL(unsigned long long a, unsigned long long b) {
  typedef unsigned long long ull; // (to support >>)
  // a and b are of the form 1.m with m of Q bits. As int is therefore max
2^(Q+2)-1. a*b is therefore < 2^(2*(Q+2)) 
  constexpr int Q = 23;
  constexpr unsigned long long K  = (1 << (Q-1));
  ull  temp = (ull)(a) * (ull)(b); 
  // Rounding; mid values are rounded up
  temp += K;
  // Correct by dividing by base   
  return (temp >> Q);  
}



unsigned int   a[1024];
unsigned int   b[1024];
unsigned int   c[1024];

unsigned long long   al[1024];
unsigned long long   bl[1024];
unsigned long long   cl[1024];


void foo() {
 for (int i=0;i!=1204;++i)
   c[i] = mult(a[i],b[i]);
}


unsigned int red() {
  unsigned int s=1;
  for (int i=0;i!=1204;++i)
    s = mult(s,b[i]);
  return s;
}

unsigned long long redL() {
  unsigned long long s=1;
  for (int i=0;i!=1204;++i)
    s = multL(s,b[i]);
  return s;
}


unsigned int prod() {
  unsigned int s=1;
  for (int i=0;i!=1204;++i)
    s = s*b[i];
  return s;
}
>From gcc-bugs-return-424520-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Mon Jun 17 09:01:12 2013
Return-Path: <gcc-bugs-return-424520-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 24392 invoked by alias); 17 Jun 2013 09:01:12 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 23842 invoked by uid 48); 17 Jun 2013 09:01:07 -0000
From: "burnus at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug fortran/57633] I/O: Problem with formatted read: reading CR-LF files (\r\n)
Date: Mon, 17 Jun 2013 09:01:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: fortran
X-Bugzilla-Version: 4.9.0
X-Bugzilla-Keywords: wrong-code
X-Bugzilla-Severity: normal
X-Bugzilla-Who: burnus at gcc dot gnu.org
X-Bugzilla-Status: UNCONFIRMED
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-57633-4-ZOIg5DmnRT@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-57633-4@http.gcc.gnu.org/bugzilla/>
References: <bug-57633-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2013-06/txt/msg00899.txt.bz2
Content-length: 265

http://gcc.gnu.org/bugzilla/show_bug.cgi?idW633

--- Comment #2 from Tobias Burnus <burnus at gcc dot gnu.org> ---
Another comment, which I missed to pass on from the original report:

It is crucial that the first line ends with a comma; without comma it works.

[Bug tree-optimization/57634] Missed vectorization for a "fixed point multiplication" reduction

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2015-04-29
     Ever confirmed|0                           |1

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
The reduction operation is way too complex (and not handled).  It's

 s = (unsigned int) (((unsigned long long)s * b[i] + 4194304) >> 23)

it's not clear that you can even vectorize this (independently handle
four 's') because of the truncation.  For the case with s being
unsigned long long the point about the not handled reduction operation
is still true.

Thus confirmed in part (redL).

[Bug tree-optimization/57634] Missed vectorization for a "fixed point multiplication" reduction

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement
           Keywords|                            |missed-optimization