[Bug tree-optimization/55645] New: skipping unlike branch in vectorized loops using movmsk or equivalent

[Bug tree-optimization/55645] New: skipping unlike branch in vectorized loops using movmsk or equivalent

[vincenzo.innocente at cern dot ch]

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

             Bug #: 55645
           Summary: skipping unlike branch in vectorized loops using
                    movmsk or equivalent
    Classification: Unclassified
           Product: gcc
           Version: 4.8.0
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: vincenzo.innocente@cern.ch


I'm wondering if the vectorization engine could accommodate some mechanism to
skip unlike branches using a global test based on movmsk or similar

below a trivial example including a possible SLP implementation that happens to
compile with 4.8 as
c++ -std=c++11 -Ofast -mavx2 -S divergent.cc; less divergent.s

float a[1024];
float b[1024];
float c[1024];

 #define likely(x) (__builtin_expect(x, true))

// possible syntax
void compute() {
  for (int i=0;i!=1024;++i) {
    if likely(a[i]<b[i])  // very often
    c[i]=a[i]+b[i];
    else // rare
    c[i]=a[i]-b[i];
  }
}


// hand-made implementation that compile with 4.8 today
#include <x86intrin.h>

typedef float __attribute__( ( vector_size( 32 ) ) ) float32x8_t;
typedef int __attribute__( ( vector_size( 32 ) ) ) int32x8_t;


float32x8_t va[1024];
float32x8_t vb[1024];
float32x8_t vc[1024];

void computeV() {
  for (int i=0;i!=1024;++i) {
    float32x8_t mask = va[i]<vb[i];
    if likely(_mm256_movemask_ps(mask) == 255) {
    vc[i]=va[i]+vb[i];
      } else {
      vc[i]= va[i]<vb[i] ? va[i]+vb[i] : va[i]-vb[i];
    }
  }
}

[Bug tree-optimization/55645] skipping unlike branch in vectorized loops using movmsk or equivalent

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2012-12-11
     Ever Confirmed|0                           |1

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> 2012-12-11 10:02:03 UTC ---
Interesting idea ...

[Bug tree-optimization/55645] skipping unlike branch in vectorized loops using movmsk or equivalent

[glisse at gcc dot gnu.org]

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

--- Comment #2 from Marc Glisse <glisse at gcc dot gnu.org> 2012-12-11 10:03:27 UTC ---
(In reply to comment #0)
> // possible syntax
> void compute() {
>   for (int i=0;i!=1024;++i) {
>     if likely(a[i]<b[i])  // very often
>     c[i]=a[i]+b[i];
>     else // rare
>     c[i]=a[i]-b[i];
>   }
> }

You may want to make the rare computation more expensive than that, I am not
sure there is a real speed improvement here (mask+compare+branch might take
about as long as minus+blend).

Interesting idea. First step would be to create a REDUC_TRUTH_AND_EXPR or
something like that to be able to represent _mm256_movemask_ps(mask) == 255 at
tree level.

[Bug tree-optimization/55645] skipping unlike branch in vectorized loops using movmsk or equivalent

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-12-11 10:40:10 UTC ---
One problem is how to represent likely vs. unlikely COND_EXPR after ifcvt (plus
also teach the vectorizer to create the GIMPLE_COND, and then/else bb's with
some vectorized stmts duplicated and some just in one of those bbs.

[Bug tree-optimization/55645] skipping unlike branch in vectorized loops using movmsk or equivalent

[vincenzo.innocente at cern dot ch]

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

--- Comment #4 from vincenzo Innocente <vincenzo.innocente at cern dot ch> 2012-12-11 10:43:21 UTC ---
sure use c[i]=std::sqrt(a[i]/b[i]);


Recent literature is plenty of examples mostly related to GPU code
see for instance
Random Variable Recycling - Numerical Algorithms Group
www.nag.co.uk/.../gpus/random_variable_recycling_note.pdf

In particular the erfinv implementations by Mike Giles
Approximating the erfinv function - Mathematical Institute
people.maths.ox.ac.uk/gilesm/files/gems_erfinv.pdf
(very simple, copy paste from last page or look below!)

the Acklam's one
http://home.online.no/~pjacklam/notes/invnorm/
(code at the bottom of
http://home.online.no/~pjacklam/notes/invnorm/impl/lea/lea.c)

or Shaw et al (http://arxiv.org/abs/0901.0638)


I'm currently  experimenting with Giles' code

#include "approx_exp.h"
#include "approx_log.h"
#include <cmath>
 #define likely(x) (__builtin_expect(x, true))

inline 
float erfinv_like(float w) {
  w = w - 2.500000f;
  float p = 2.81022636e-08f;
  p = 3.43273939e-07f + p*w;
  p = -3.5233877e-06f + p*w;
  p = -4.39150654e-06f + p*w;
  p = 0.00021858087f + p*w;
  p = -0.00125372503f + p*w;
  p = -0.00417768164f + p*w;
  p = 0.246640727f + p*w;
  p = 1.50140941f + p*w;
  return p;
}
inline 
float erfinv_unlike(float w) {
  w = std::sqrt(w) - 3.000000f;
  float p = -0.000200214257f;
  p = 0.000100950558f + p*w;
  p = 0.00134934322f + p*w;
  p = -0.00367342844f + p*w;
  p = 0.00573950773f + p*w;
  p = -0.0076224613f + p*w;
  p = 0.00943887047f + p*w;
  p = 1.00167406f + p*w;
  p = 2.83297682f + p*w;
  return p;
}

inline float erfinv(float x) {
  float w, p;
  w = -  unsafe_logf<8>((1.0f-x)*(1.0f+x));
  if likely( w < 5.000000f )
         p =   erfinv_like(w);
  else 
    erfinv_unlike(w);
  }
  return p*x;
}

float a[1024];
float b[1024];

void compute() {
  for (int i=0;i!=1024;++i)
    b[i]=erfinv(a[i]);
}

[Bug tree-optimization/55645] skipping unlike branch in vectorized loops using movmsk or equivalent

[vincenzo.innocente at cern dot ch]

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

--- Comment #5 from vincenzo Innocente <vincenzo.innocente at cern dot ch> 2012-12-11 14:34:45 UTC ---
in principle,  one could add the movmsk unconditionally (well, if advantagious)
after the compare  and evaluate only one one of legs of the branch in case the
result is 0 or all ones. My understanding is that this is similar to what CUDA
does for instance.