[Bug tree-optimization/42652] New: vectorizer created unaligned vector insns

[Bug tree-optimization/42652] New: vectorizer created unaligned vector insns

[law at redhat dot com]

The vectorizer doesn't appear to handle packed structures correctly and
ultimately generates a vector store to an unaligned address which causes a
segfault.

This was originally reported against a 4.4 variant, but investigation shows the
bug is merely latent on the head of the trunk and can be exposed by reverting
this change:

2009-03-29  Richard Guenther  <rguenther@suse.de>

        * tree-ssa-forwprop.c (forward_propagate_addr_expr_1): Properly
        propagate addresses of array references.

[ The 2009-03-29 patch changes the end condition of the loop which ultimately
confuses the vectorizer into being unable to determine the number of iterations
in the loop.  That's clearly a weakness in the vectorizer as the loop bounds
are easily shown to be compile-time constants. ]

Compile the attached testcase with -O3 and search the resulting assembly for
these two key insns:

        leaq    2(%rax,%rdi,4), %rdi

This computes the base address for palette->ents which is at offset 2 in the
Palette structure (which is packed).  This insn appears in the vectorized loop
pre-header.  It's later used by:

        movdqa  %xmm0, (%rdi,%rsi)

The faulting vector insn.


Note carefully this isn't a case where peeling iterations can be used to
generate suitable alignment -- the packed nature of the structure results in
all the elt members being unaligned.  

ISTM that vector_alignment_reachable_p is the place to fix this, but I'm not
very familiar with the vectorizer and thus may be off base.


-- 
           Summary: vectorizer created unaligned vector insns
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Keywords: wrong-code
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: law at redhat dot com
 GCC build triplet: x86_64-unknown-linux-gnu
  GCC host triplet: x86_64-unknown-linux-gnu
GCC target triplet: x86_64-unknown-linux-gnu


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

[Bug tree-optimization/42652] vectorizer created unaligned vector insns

[law at redhat dot com]

------- Comment #1 from law at redhat dot com  2010-01-07 17:33 -------
Created an attachment (id=19501)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=19501&action=view)
testcase


-- 


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

[Bug tree-optimization/42652] vectorizer created unaligned vector insns

[rguenth at gcc dot gnu dot org]

------- Comment #2 from rguenth at gcc dot gnu dot org  2010-01-08 11:58 -------
There is some hacks with contains_packed_reference but IIRC I was complaining
about these at some point - they are not conservatively correct.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |irar at gcc dot gnu dot org


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

[Bug tree-optimization/42652] vectorizer created unaligned vector insns

[law at redhat dot com]

------- Comment #3 from law at redhat dot com  2010-01-08 16:45 -------
Subject: Re:  vectorizer created unaligned vector
 insns

On 01/08/10 04:58, rguenth at gcc dot gnu dot org wrote:
> ------- Comment #2 from rguenth at gcc dot gnu dot org  2010-01-08 11:58 -------
> There is some hacks with contains_packed_reference but IIRC I was complaining
> about these at some point - they are not conservatively correct.
>
>
>    
I was thinking about this some more and ISTM that if we can't prove 
suitable alignment, then we have to fall back to a runtime test.  So 
improving the code to detect packed structures would be useful, but is 
not sufficient to resolve this class of problems.  ie, it probably 
wouldn't be too hard to transform that testcase into one which passed in 
a pointer to an unaligned palette->elms at which point we're forced to 
use the runtime test.

Thoughts?
jeff


-- 


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

[Bug tree-optimization/42652] vectorizer created unaligned vector insns

[rguenth at gcc dot gnu dot org]

------- Comment #4 from rguenth at gcc dot gnu dot org  2010-01-08 17:25 -------
Well, indeed we have a certain weakness in how we represent pointers to
possibly (un-)aligned stuff.  See PR39954 for another case.  Maybe this
bug is really a duplicate of the underlying problems.


-- 


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

[Bug tree-optimization/42652] vectorizer created unaligned vector insns

[irar at il dot ibm dot com]

------- Comment #5 from irar at il dot ibm dot com  2010-01-10 08:22 -------
In vector_alignment_reachable_p() we check if an access is packed using
contains_packed_reference(). For packed accesses we return false, meaning
alignment is unreachable and peeling cannot be used.

In the attached testcase contains_packed_reference() returns false for
palette_5.


-- 


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

[Bug tree-optimization/42652] vectorizer created unaligned vector insns

[law at redhat dot com]

------- Comment #6 from law at redhat dot com  2010-01-11 17:14 -------
Subject: Re:  vectorizer created unaligned vector
 insns

On 01/10/10 01:22, irar at il dot ibm dot com wrote:
> ------- Comment #5 from irar at il dot ibm dot com  2010-01-10 08:22 -------
> In vector_alignment_reachable_p() we check if an access is packed using
> contains_packed_reference(). For packed accesses we return false, meaning
> alignment is unreachable and peeling cannot be used.
>
> In the attached testcase contains_packed_reference() returns false for
> palette_5.
>    
Right.  If you look more closely at the way the code works, there's no 
way contains_packed_reference is ever going to return true.  It simply 
isn't passed the right information.  It'd need to be looking at the base 
address's type (not the base object).  Furthermore, 
contains_packed_reference simply isn't designed to dive into types.  It 
primarily works on exprs and only references the underlying type when it 
encounters a COMPONENT_REF.

As Richard apparently pointed out in the past, this code is not 
conservatively correct -- if it can't prove the item is properly 
aligned, then a runtime check is required.

So while I think we might be able to fix this specific instance by 
improving the code around the call to contains_packed_reference, I think 
we have a bigger problem as it's fairly trivial to change the test so 
that the addresses of interest are parameters and alignment info is 
effectively unknown.


Jeff


-- 


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

[Bug tree-optimization/42652] vectorizer created unaligned vector insns

[law at redhat dot com]

------- Comment #7 from law at redhat dot com  2010-01-11 17:16 -------
Subject: Re:  vectorizer created unaligned vector
 insns

On 01/08/10 10:25, rguenth at gcc dot gnu dot org wrote:
> ------- Comment #4 from rguenth at gcc dot gnu dot org  2010-01-08 17:25 -------
> Well, indeed we have a certain weakness in how we represent pointers to
> possibly (un-)aligned stuff.  See PR39954 for another case.  Maybe this
> bug is really a duplicate of the underlying problems.
>
>    
PR39954 is slightly different, though it would apply if we started 
looking at passing the address of palette->ents as a parameter.

Jeff


-- 


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

[Bug tree-optimization/42652] vectorizer created unaligned vector insns

[irar at il dot ibm dot com]

------- Comment #8 from irar at il dot ibm dot com  2010-01-12 08:08 -------
So, to be on the safe side, we should assume that COMPONENT_REFs are not
naturally aligned and never use peeling for them?


-- 


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

[Bug tree-optimization/42652] vectorizer created unaligned vector insns

[law at redhat dot com]

------- Comment #9 from law at redhat dot com  2010-01-12 15:18 -------
Subject: Re:  vectorizer created unaligned vector
 insns

On 01/12/10 01:08, irar at il dot ibm dot com wrote:
> ------- Comment #8 from irar at il dot ibm dot com  2010-01-12 08:08 -------
> So, to be on the safe side, we should assume that COMPONENT_REFs are not
> naturally aligned and never use peeling for them?
>    
If you can not *prove* at compile time that you're going to get the 
proper alignment, then you can't vectorize without a runtime check to 
select between a vectorized and unvectorized loop.

Proven alignement -- vectorize
Proven unaligned -- do not vectorize
Likely aligned, but not proven -- emit two loops, one vectorized, one 
not vectorized and runtime selection of the proper loop

Otherwise you run the risk of making conforming code segfault which is 
obviously unacceptable.

jeff


-- 


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

[Bug tree-optimization/42652] vectorizer created unaligned vector insns

[irar at il dot ibm dot com]

------- Comment #10 from irar at il dot ibm dot com  2010-01-13 09:35 -------
Yes, I understand that we can't assume that an access is aligned if we can't
prove it's aligned. I don't understand how we can prove that a COMPONENT_REF is
aligned, i.e., if there is a way to check if a struct is packed, or we'd better
decide that we always use versioning for COMPONENT_REFs?

Thanks,
Ira


-- 


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

[Bug tree-optimization/42652] vectorizer created unaligned vector insns

[law at redhat dot com]

------- Comment #11 from law at redhat dot com  2010-01-14 17:29 -------
Subject: Re:  vectorizer created unaligned vector
 insns

On 01/13/10 02:35, irar at il dot ibm dot com wrote:
> ------- Comment #10 from irar at il dot ibm dot com  2010-01-13 09:35 -------
> Yes, I understand that we can't assume that an access is aligned if we can't
> prove it's aligned. I don't understand how we can prove that a COMPONENT_REF is
> aligned, i.e., if there is a way to check if a struct is packed, or we'd better
> decide that we always use versioning for COMPONENT_REFs?
>    
Given a raw COMPONENT_REF I don't think you can prove proper alignment.  
You have to look at the entire effective address computation.  
Unfortunately, I think this has rather significant implications on how 
often we can vectorize without needing to perform the runtime check for 
alignment.

Jeff


-- 


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

[Bug tree-optimization/42652] vectorizer created unaligned vector insns

[hjl dot tools at gmail dot com]

------- Comment #12 from hjl dot tools at gmail dot com  2010-01-14 17:34 -------
Intel AVX architecture won't fault on unaligned load-op instructions
and unaligned VMOV* instructions are as fast as aligned VMOV*
instructions on aligned memory. For AVX, we can always use unaligned
VMOV* instructions, even on aligned memory, to work around this issue
without any performance penalty.


-- 


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

[Bug tree-optimization/42652] vectorizer created unaligned vector insns

[irar at il dot ibm dot com]

------- Comment #13 from irar at il dot ibm dot com  2010-01-18 12:17 -------
Does something like this make sense? (With this patch we will never use peeling
for function parameters, unless the builtin returns OK to peel for packed
types). 

Index: tree-vect-data-refs.c
===================================================================
--- tree-vect-data-refs.c       (revision 155880)
+++ tree-vect-data-refs.c       (working copy)
@@ -1010,10 +1010,29 @@ vector_alignment_reachable_p (struct dat
       tree type = (TREE_TYPE (DR_REF (dr)));
       tree ba = DR_BASE_OBJECT (dr);
       bool is_packed = false;
+      tree tmp = TREE_TYPE (DR_BASE_ADDRESS (dr));

       if (ba)
        is_packed = contains_packed_reference (ba);

+      is_packed = is_packed || contains_packed_reference (DR_BASE_ADDRESS
(dr));
+
+      if (!is_packed)
+        {
+          while (tmp)
+            {
+              is_packed = TYPE_PACKED (tmp);
+              if (is_packed)
+                break;
+
+              tmp = TREE_TYPE (tmp);
+            }
+        }
+
+      if (TREE_CODE (DR_BASE_ADDRESS (dr)) == SSA_NAME
+          && TREE_CODE (SSA_NAME_VAR (DR_BASE_ADDRESS (dr))) == PARM_DECL)
+        is_packed = true;
+
       if (vect_print_dump_info (REPORT_DETAILS))
        fprintf (vect_dump, "Unknown misalignment, is_packed = %d",is_packed);
       if (targetm.vectorize.vector_alignment_reachable (type, is_packed))


-- 


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

[Bug tree-optimization/42652] vectorizer created unaligned vector insns

[law at redhat dot com]

------- Comment #14 from law at redhat dot com  2010-02-09 23:04 -------
Subject: Re:  vectorizer created unaligned vector
 insns

On 01/18/10 05:17, irar at il dot ibm dot com wrote:
> ------- Comment #13 from irar at il dot ibm dot com  2010-01-18 12:17 -------
> Does something like this make sense? (With this patch we will never use peeling
> for function parameters, unless the builtin returns OK to peel for packed
> types).
>
> Index: tree-vect-data-refs.c
> ===================================================================
> --- tree-vect-data-refs.c       (revision 155880)
> +++ tree-vect-data-refs.c       (working copy)
> @@ -1010,10 +1010,29 @@ vector_alignment_reachable_p (struct dat
>         tree type = (TREE_TYPE (DR_REF (dr)));
>         tree ba = DR_BASE_OBJECT (dr);
>         bool is_packed = false;
> +      tree tmp = TREE_TYPE (DR_BASE_ADDRESS (dr));
>
>         if (ba)
>          is_packed = contains_packed_reference (ba);
>
> +      is_packed = is_packed || contains_packed_reference (DR_BASE_ADDRESS
> (dr));
> +
> +      if (!is_packed)
> +        {
> +          while (tmp)
> +            {
> +              is_packed = TYPE_PACKED (tmp);
> +              if (is_packed)
> +                break;
> +
> +              tmp = TREE_TYPE (tmp);
> +            }
> +        }
> +
> +      if (TREE_CODE (DR_BASE_ADDRESS (dr)) == SSA_NAME
> +&&  TREE_CODE (SSA_NAME_VAR (DR_BASE_ADDRESS (dr))) == PARM_DECL)
> +        is_packed = true;
> +
>         if (vect_print_dump_info (REPORT_DETAILS))
>          fprintf (vect_dump, "Unknown misalignment, is_packed = %d",is_packed);
>         if (targetm.vectorize.vector_alignment_reachable (type, is_packed))
>
>    
I still don't see how this can be conservatively correct.   The 
fundamental problem is the code assumes that if it doesn't find a packed 
attribute or the DR_BASE_ADDRESS isn't directly derived from a PARM_DECL 
then it's safe to vectorize.    Instead the code really needs to operate 
by proving suitable alignment and if suitable alignment can't be proven, 
then vectorization is not possible without runtime alignment guards.

As an example, consider the case where an unaligned packed address is 
passed as a parameter, but the target function does somethign like

fubar (int *p, bool condition )  // where P is potentially unaligned
{
    int *addr;
   if (condition)
     temp = malloc (whatever)
   addr = (condition ? temp : p);

   // addr used as base address in vectorizable loop here
}

Jeff


-- 


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

[Bug tree-optimization/42652] vectorizer created unaligned vector insns

[rguenth at gcc dot gnu dot org]

------- Comment #15 from rguenth at gcc dot gnu dot org  2010-02-09 23:11 -------
(In reply to comment #14)
> Subject: Re:  vectorizer created unaligned vector
>  insns
> 
> On 01/18/10 05:17, irar at il dot ibm dot com wrote:
> > ------- Comment #13 from irar at il dot ibm dot com  2010-01-18 12:17 -------
> > Does something like this make sense? (With this patch we will never use peeling
> > for function parameters, unless the builtin returns OK to peel for packed
> > types).
> >
> > Index: tree-vect-data-refs.c
> > ===================================================================
> > --- tree-vect-data-refs.c       (revision 155880)
> > +++ tree-vect-data-refs.c       (working copy)
> > @@ -1010,10 +1010,29 @@ vector_alignment_reachable_p (struct dat
> >         tree type = (TREE_TYPE (DR_REF (dr)));
> >         tree ba = DR_BASE_OBJECT (dr);
> >         bool is_packed = false;
> > +      tree tmp = TREE_TYPE (DR_BASE_ADDRESS (dr));
> >
> >         if (ba)
> >          is_packed = contains_packed_reference (ba);
> >
> > +      is_packed = is_packed || contains_packed_reference (DR_BASE_ADDRESS
> > (dr));
> > +
> > +      if (!is_packed)
> > +        {
> > +          while (tmp)
> > +            {
> > +              is_packed = TYPE_PACKED (tmp);
> > +              if (is_packed)
> > +                break;
> > +
> > +              tmp = TREE_TYPE (tmp);
> > +            }
> > +        }
> > +
> > +      if (TREE_CODE (DR_BASE_ADDRESS (dr)) == SSA_NAME
> > +&&  TREE_CODE (SSA_NAME_VAR (DR_BASE_ADDRESS (dr))) == PARM_DECL)
> > +        is_packed = true;
> > +
> >         if (vect_print_dump_info (REPORT_DETAILS))
> >          fprintf (vect_dump, "Unknown misalignment, is_packed = %d",is_packed);
> >         if (targetm.vectorize.vector_alignment_reachable (type, is_packed))
> >
> >    
> I still don't see how this can be conservatively correct.   The 
> fundamental problem is the code assumes that if it doesn't find a packed 
> attribute or the DR_BASE_ADDRESS isn't directly derived from a PARM_DECL 
> then it's safe to vectorize.    Instead the code really needs to operate 
> by proving suitable alignment and if suitable alignment can't be proven, 
> then vectorization is not possible without runtime alignment guards.
> 
> As an example, consider the case where an unaligned packed address is 
> passed as a parameter, but the target function does somethign like
> 
> fubar (int *p, bool condition )  // where P is potentially unaligned

A pointer of type int * which is not aligned properly invokes undefined
behavior.

> {
>     int *addr;
>    if (condition)
>      temp = malloc (whatever)
>    addr = (condition ? temp : p);
> 
>    // addr used as base address in vectorizable loop here
> }
> 
> Jeff
> 


-- 


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

[Bug tree-optimization/42652] vectorizer created unaligned vector insns

[law at redhat dot com]

------- Comment #16 from law at redhat dot com  2010-02-09 23:49 -------
Subject: Re:  vectorizer created unaligned vector
 insns

On 02/09/10 16:11, rguenth at gcc dot gnu dot org wrote:
> ------- Comment #15 from rguenth at gcc dot gnu dot org  2010-02-09 23:11 -------
> (In reply to comment #14)
>    
>> Subject: Re:  vectorizer created unaligned vector
>>   insns
>>
>> On 01/18/10 05:17, irar at il dot ibm dot com wrote:
>>      
>>> ------- Comment #13 from irar at il dot ibm dot com  2010-01-18 12:17 -------
>>> Does something like this make sense? (With this patch we will never use peeling
>>> for function parameters, unless the builtin returns OK to peel for packed
>>> types).
>>>
>>> Index: tree-vect-data-refs.c
>>> ===================================================================
>>> --- tree-vect-data-refs.c       (revision 155880)
>>> +++ tree-vect-data-refs.c       (working copy)
>>> @@ -1010,10 +1010,29 @@ vector_alignment_reachable_p (struct dat
>>>          tree type = (TREE_TYPE (DR_REF (dr)));
>>>          tree ba = DR_BASE_OBJECT (dr);
>>>          bool is_packed = false;
>>> +      tree tmp = TREE_TYPE (DR_BASE_ADDRESS (dr));
>>>
>>>          if (ba)
>>>           is_packed = contains_packed_reference (ba);
>>>
>>> +      is_packed = is_packed || contains_packed_reference (DR_BASE_ADDRESS
>>> (dr));
>>> +
>>> +      if (!is_packed)
>>> +        {
>>> +          while (tmp)
>>> +            {
>>> +              is_packed = TYPE_PACKED (tmp);
>>> +              if (is_packed)
>>> +                break;
>>> +
>>> +              tmp = TREE_TYPE (tmp);
>>> +            }
>>> +        }
>>> +
>>> +      if (TREE_CODE (DR_BASE_ADDRESS (dr)) == SSA_NAME
>>> +&&   TREE_CODE (SSA_NAME_VAR (DR_BASE_ADDRESS (dr))) == PARM_DECL)
>>> +        is_packed = true;
>>> +
>>>          if (vect_print_dump_info (REPORT_DETAILS))
>>>           fprintf (vect_dump, "Unknown misalignment, is_packed = %d",is_packed);
>>>          if (targetm.vectorize.vector_alignment_reachable (type, is_packed))
>>>
>>>
>>>        
>> I still don't see how this can be conservatively correct.   The
>> fundamental problem is the code assumes that if it doesn't find a packed
>> attribute or the DR_BASE_ADDRESS isn't directly derived from a PARM_DECL
>> then it's safe to vectorize.    Instead the code really needs to operate
>> by proving suitable alignment and if suitable alignment can't be proven,
>> then vectorization is not possible without runtime alignment guards.
>>
>> As an example, consider the case where an unaligned packed address is
>> passed as a parameter, but the target function does somethign like
>>
>> fubar (int *p, bool condition )  // where P is potentially unaligned
>>      
> A pointer of type int * which is not aligned properly invokes undefined
> behavior.
>    
Unaligned in the sense that the alignment is not suitable for 
vectorization, but still has suitable alignment for natural integer 
loads & stores on the target processor.

jeff


-- 


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

[Bug tree-optimization/42652] vectorizer created unaligned vector insns

[irar at il dot ibm dot com]

------- Comment #17 from irar at il dot ibm dot com  2010-02-22 09:01 -------
Is there a way to pass alignment information similar to PR 39954?

Otherwise, a proper fix would be some inter-procedural analysis... Meantime, we
can do intra-procedural analysis and fail when we reach function argument, i.e,
use runtime checks. We already have several types of versioning, so adding
another one will complicate the things even more, and will not always be
possible (because of code size constrains). 

Thanks,
Ira


-- 


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

[Bug tree-optimization/42652] vectorizer created unaligned vector insns

[rguenth at gcc dot gnu dot org]

------- Comment #18 from rguenth at gcc dot gnu dot org  2010-02-22 10:27 -------
(In reply to comment #17)
> Is there a way to pass alignment information similar to PR 39954?

Well, that wasn't really a true fix but simply restored the (broken) behavior
of earlier compilers so the 4.5 regression is gone ...

> Otherwise, a proper fix would be some inter-procedural analysis... Meantime, we
> can do intra-procedural analysis and fail when we reach function argument, i.e,
> use runtime checks. We already have several types of versioning, so adding
> another one will complicate the things even more, and will not always be
> possible (because of code size constrains).

Yes, we need to propagate (mis-)alignment information properly.  My plan for
4.6 is to add (mis-)alignemnt information to SSA_NAME_PTR_INFO and have
a simple propagator computing it.

Richard.


-- 


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