[Bug tree-optimization/37101] New: [4.2/4.3 Regression] wrong code: tree vectorizer omits bogus movq/movlps construct

[Bug tree-optimization/37101] New: [4.2/4.3 Regression] wrong code: tree vectorizer omits bogus movq/movlps construct

[christophe at saout dot de]

(see http://bugs.gentoo.org/show_bug.cgi?id=227311 )

Seeing this on my (amd64) gcc 4.3.1 in xorg-server code dix/resource.c with
"-O2 -march=nocona -ftree-vectorize".

( gcc -O2 -march=nocona -ftree-vectorize -o resource.o -c resource.i )

Unfortunately I was not able to reproduce this using a simpler testcase,
because gcc would omit a "punpcklqdq" instead of the offending "movq/movlps",
so I attached the whole thing with a description of the problem and an analysis
of the wrong assembler code emitted.

When going through the attached file, look for the "RebuildTable" function,
which is inlined into "AddResource".

It contains the following construct:

    for (rptr = resources, tptr = tails; --j >= 0; rptr++, tptr++)
    {
        *rptr = NullResource;
        *tptr = rptr;
    }

which initialises two arrays of pointers, one filled with null pointers and the
other with a pointer to the just filled NULL in the other array.

The symptom (leeding to a segfault just after) shows up that the second "tails"
array is incorrectly initialized. Every second entry does not contain the
correct pointer (i.e. filled with the correct value of rptr), but contains a
"ladder" starting at 0 (0x8, 018, 0x28, ...), i.e. does not add the value of
"resources" as start offset.  (the whole array goes like 0xc000, 0x0008,
0xc010, 0x0018, 0xc020, 0x0028, ... instead of 0xc000, 0xc008, 0xc010, 0xc018,
0xc020, 0xc028, ...)

Digging through the code it seems that the tree vectorizer is emitting an
optimized implementation of the loop for large amount of entries (j starts at a
value of 128 when the failure was observed) after the body of the function.

It fills a bunch of xmm registers with values, so that both arrays can be
filled 16 bytes at a time (instead of 8 bytes at a time).

Now, due to the bug, the register that pair-wise fills the "tails" array should
be doing sth like this (pseudo-code)

xmm1 = ((resources + 0x00000008) << 64) + resources
xmm2 = (0x00000010 << 64) + 0x00000010

and then fill in xmm1 and add xmm2 to it after each iteration, or something
like that.

What I now seem to see be seeing, is that in my terminology here "xmm1" is not
filled correctly, the upper 64 bit seem to be zero, which would explain how the
array is incorrectly filled.

The assembler code of this part looks like:

(the start of the for loop in the default code path)
     f0d:       44 89 ee                mov    %r13d,%esi
     f10:       83 ee 01                sub    $0x1,%esi
     f13:       78 32                   js     f47 <AddResource+0x1a2>
     f15:       41 83 fd 09             cmp    $0x9,%r13d
     f19:       0f 87 22 01 00 00       ja     1041 <AddResource+0x29c>

So here seems to be some logic for the first --j and as to whether the
optimized out-of-line code should be jumped (and a non-sse implementation
of the loop body below, which looks ok).

Starting at 1041 there is some more funny logic which I don't fully get, but
some instructions below is where I think the cause of the problem is:

Here, the code that initializes xmm1 (also the xmm1 in my pseudo-code above):

    107e:       48 8b 44 24 38          mov    0x38(%rsp),%rax
    1083:       48 83 c0 08             add    $0x8,%rax
    1087:       66 48 0f 6e c8          movq   %rax,%xmm1
    108c:       0f 12 4c 24 38          movlps 0x38(%rsp),%xmm1

I'm no sse2 expert, but it seems as if movlps was supposed to move the lower
part of xmm1 (which contains "resources" + 0x8) to the upper part before
overwriting the lower part with "resources"? Or something, like that, which it
doesn't (using google and http://www.ews.uiuc.edu/~cjiang/reference/vc191.htm
as a reference... :-))

Anyway, here is the rest of the method:

    1091:       66 0f 6f c1             movdqa %xmm1,%xmm0
    1095:       31 d2                   xor    %edx,%edx
    1097:       31 c0                   xor    %eax,%eax
    1099:       66 0f 6f 15 00 00 00    movdqa 0x0(%rip),%xmm2        # 10a1
<AddResource+0x2fc>
    10a0:       00 
                        109d: R_X86_64_PC32     .LC3+0xfffffffffffffffc

(presumably loads 0x0000001000000010 into xmm2)

    10a1:       66 0f ef c9             pxor   %xmm1,%xmm1

(xmm1 now contains zeroes to fill the "resources" array)

    10a5:       48 8b 5c 24 38          mov    0x38(%rsp),%rbx
    10aa:       66 0f 7f 0c 03          movdqa %xmm1,(%rbx,%rax,1) <- fill 2
resources entries
    10af:       66 41 0f 7f 04 04       movdqa %xmm0,(%r12,%rax,1) <- fill 2
tails entries
    10b5:       83 c2 01                add    $0x1,%edx
    10b8:       48 83 c0 10             add    $0x10,%rax
    10bc:       66 0f d4 c2             paddq  %xmm2,%xmm0
    10c0:       39 ca                   cmp    %ecx,%edx
    10c2:       72 e1                   jb     10a5 <AddResource+0x300>

Trying to reproduce the test case, gcc omitted a "punpcklqdq" to initialized
the base instead, which works, so this must me some different code triggered by
some other register constraints or something (?).

As from the report, I guess this bug was already present in 4.2, haven't tested
any other versions myself.


-- 
           Summary: [4.2/4.3 Regression] wrong code: tree vectorizer omits
                    bogus movq/movlps construct
           Product: gcc
           Version: 4.3.1
            Status: UNCONFIRMED
          Severity: critical
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: christophe at saout dot de
 GCC build triplet: x86_64-pc-linux-gnu
  GCC host triplet: x86_64-pc-linux-gnu
GCC target triplet: x86_64-pc-linux-gnu


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

[Bug tree-optimization/37101] [4.2/4.3 Regression] wrong code: tree vectorizer omits bogus movq/movlps construct

[christophe at saout dot de]

------- Comment #1 from christophe at saout dot de  2008-08-12 23:17 -------
Created an attachment (id=16061)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=16061&action=view)
preprocessed source file to be compiled to see the wrong generated code


-- 


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

[Bug tree-optimization/37101] [4.2/4.3 Regression] wrong code: tree vectorizer omits bogus movq/movlps construct

[rguenth at gcc dot gnu dot org]

-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu dot
                   |                            |org
           Keywords|                            |wrong-code
   Target Milestone|---                         |4.3.2


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

[Bug tree-optimization/37101] [4.2/4.3 Regression] wrong code: tree vectorizer omits bogus movq/movlps construct

[ubizjak at gmail dot com]

------- Comment #2 from ubizjak at gmail dot com  2008-08-13 13:47 -------
(In reply to comment #0)

> Here, the code that initializes xmm1 (also the xmm1 in my pseudo-code above):
> 
>     107e:       48 8b 44 24 38          mov    0x38(%rsp),%rax
>     1083:       48 83 c0 08             add    $0x8,%rax
>     1087:       66 48 0f 6e c8          movq   %rax,%xmm1
>     108c:       0f 12 4c 24 38          movlps 0x38(%rsp),%xmm1

This code should implement following statement (from _.optimized dump):

<bb 12>:
  vect_vec_iv_.590 = {rptr, rptr + 8};
  ivtmp.642 = 0;
  ivtmp.644 = 0B;

this dump is with -fverbose-asm:

        movq    56(%rsp), %rax  # rptr, tmp114
        addq    $8, %rax        #, tmp114
        movd    %rax, %xmm1     # tmp114,
        movlps  56(%rsp), %xmm1 # rptr,
        movdqa  %xmm1, %xmm0    #, vect_vec_iv_.590
        xorl    %edx, %edx      # ivtmp.642
        xorl    %eax, %eax      # ivtmp.644

It looks to me, that movhps should be there instead of movlps. What happens if
you manually change this movlps into movhps in generated asm and recompile this
changed asm?


-- 

ubizjak at gmail dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2008-08-13 13:47:27
               date|                            |


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

[Bug tree-optimization/37101] [4.2/4.3 Regression] wrong code: tree vectorizer omits bogus movq/movlps construct

[christophe at saout dot de]

------- Comment #3 from christophe at saout dot de  2008-08-13 16:14 -------
Ok, tried that...

Now xorg-server doesn't segfault, but hang in an infinite loop.

Adding printouts after the loop shows that the upper and lower parts of the
register are inverted:

(contents of the "tails" array):
  0 0x28e1c98
  1 0x28e1c90
  2 0x28e1ca8
  3 0x28e1ca0
  4 0x28e1cb8
...

So, the movlps is correct to fill the lower half of the register without
touching the upper half, but the "movd %rax, %xmm1" should fill the upper half
instead. I tried changing it into a movhps, but that won't take the %rax as
source register.


-- 


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

[Bug tree-optimization/37101] [4.2/4.3 Regression] wrong code: tree vectorizer omits bogus movq/movlps construct

[christophe at saout dot de]

------- Comment #4 from christophe at saout dot de  2008-08-13 22:15 -------
Ok, I'm completely not in my game here, but after staring at rtl dumps and gcc
code for about two hours straight, things slowly start to make a litte sense...

(please tell me to shut up and forget about it if I am totally wrong about
this)

In my opinion the issue comes from here:

(define_insn "*vec_concatv2di_rex"
  [(set (match_operand:V2DI 0 "register_operand"     "=Y2,Yi,!Y2,Y2,x,x,x")
        (vec_concat:V2DI
          (match_operand:DI 1 "nonimmediate_operand" "  m,r ,*y ,0 ,0,0,m")
          (match_operand:DI 2 "vector_move_operand"  "  C,C ,C  ,Y2,x,m,0")))]
  "TARGET_64BIT"
  "@
   movq\t{%1, %0|%0, %1}
   movq\t{%1, %0|%0, %1}
   movq2dq\t{%1, %0|%0, %1}
   punpcklqdq\t{%2, %0|%0, %2}
   movlhps\t{%2, %0|%0, %2}
   movhps\t{%2, %0|%0, %2}
   movlps\t{%1, %0|%0, %1}"
  [(set_attr "type" "ssemov,ssemov,ssemov,sselog,ssemov,ssemov,ssemov")
   (set_attr "mode" "TI,TI,TI,TI,V4SF,V2SF,V2SF")])

As far as I understand it, looking at the instruction and operand matches,
this rule is used to combined two 64 bit values into one 128 bit xmm register.

The relevant part in the RTL dump seems to be:

(insn 401 108 109 (set (reg:DI 22 xmm1)
        (reg/f:DI 0 ax [124])) 89 {*movdi_1_rex64} (expr_list:REG_DEAD
(reg/f:DI 0 ax [124])
        (nil)))

(insn:HI 109 401 402 (set (reg:V2DI 22 xmm1)
        (vec_concat:V2DI (mem/c:DI (plus:DI (reg/f:DI 7 sp)
                    (const_int 56 [0x38])) [52 D.11729+0 S8 A8])
            (reg:DI 22 xmm1))) 1301 {*vec_concatv2di_rex} (nil))

The first instruction tells it to move %rax to %xmm1 (which contains the 64
bits of %xmm1 that should end up in the upper half of %xmm1), which just had 8
added to it in the previous step ("add $0x8,%rax" after %rax being loaded from
rptr).

The second instruction now is supposed to take %xmm1 and a memory operand (the
"rptr" value without 8 added) and combine the two into %xmm1.

As far as I understand the RTL template syntax, this definition handles seven
cases at once, which the last one matching here, operands 0 to 2 being "x", "m"
and "0", which I guess means "xmm register", "memory" and "same as 0th
operand".

So this is supposed to take the memory operand, %xmm1 and combine the two, i.e.
taking the memory operand as lower half and the contents of %xmm1 as upper half
and putting the result in %xmm1 again.

Which is exactly what is supposed to happen here. For the second-to-last
instruction (with the role flipped, i.e. the memory operand to land in the
upper half), this would yield in a "movhps", which is ok.

But for "movlps" it is not, since the lower half of %xmm1 is not moved to the
upper half, which leads to the problem I see.

My assumption would be that the seventh combination leading to emission of
"movlps" is badly formulated. The "0" in the constraints seems to be
interpreted by gcc that it's ok if the contents are in the lower half of the
input register, whereas it seems that the constrain is should at least tell gcc
that the contents of operand 2 should already be in the upper half. 

However, I have no idea how to tell gcc that.  I could try and remove that 7th
combination altogether to force gcc to find an alternative solution (?).

Is it worth testing that? (i.e. going to build gcc and experiment...)


-- 


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

[Bug tree-optimization/37101] [4.2/4.3 Regression] wrong code: tree vectorizer omits bogus movq/movlps construct

[christophe at saout dot de]

------- Comment #5 from christophe at saout dot de  2008-08-14 00:08 -------
Created an attachment (id=16068)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=16068&action=view)
Remove broken alternatives using movlps for vec_concatv2di(_rex) insn

causes gcc to emit the following valid sequence instead
(which is the sequence it always produced when I tried to build a standalone
test case):

        movq    56(%rsp), %rax
        addq    $8, %rax
        movq    56(%rsp), %xmm1
        movd    %rax, %xmm2
        punpcklqdq      %xmm2, %xmm1
        movdqa  %xmm1, %xmm0

BTW: that last move seems redundant...


-- 


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

[Bug tree-optimization/37101] [4.2/4.3 Regression] wrong code: tree vectorizer omits bogus movq/movlps construct

[ubizjak at gmail dot com]

------- Comment #6 from ubizjak at gmail dot com  2008-08-14 11:34 -------
(In reply to comment #5)
> Created an attachment (id=16068)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=16068&action=view) [edit]
> Remove broken alternatives using movlps for vec_concatv2di(_rex) insn

This is in fact the correct fix. I'm bootstrapping and regression testing your
patch on gcc-4.4 and will do the backport to branches in a couple of days.


-- 

ubizjak at gmail dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |ubizjak at gmail dot com
                   |dot org                     |
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2008-08-13 13:47:27         |2008-08-14 11:34:18
               date|                            |


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

[Bug tree-optimization/37101] [4.2/4.3 Regression] wrong code: tree vectorizer omits bogus movq/movlps construct

[uros at gcc dot gnu dot org]

------- Comment #7 from uros at gcc dot gnu dot org  2008-08-14 11:58 -------
Subject: Bug 37101

Author: uros
Date: Thu Aug 14 11:57:18 2008
New Revision: 139095

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=139095
Log:
        PR target/37101
        * config/i386/sse.md (vec_concatv2di): Remove movlps alternative.
        (*vec_concatv2di_rex64_sse4_1): Ditto.
        (*vec_concatv2di_rex64_sse): Ditto.

testsuite/ChangeLog:

        PR target/37101
        * gcc.target/i386/pr37101.c: New test.


Added:
    trunk/gcc/testsuite/gcc.target/i386/pr37101.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/config/i386/sse.md
    trunk/gcc/testsuite/ChangeLog


-- 


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

[Bug tree-optimization/37101] [4.2/4.3 Regression] wrong code: tree vectorizer omits bogus movq/movlps construct

[hjl at gcc dot gnu dot org]

------- Comment #8 from hjl at gcc dot gnu dot org  2008-08-14 18:25 -------
Subject: Bug 37101

Author: hjl
Date: Thu Aug 14 18:23:58 2008
New Revision: 139110

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=139110
Log:
2008-08-14  H.J. Lu  <hongjiu.lu@intel.com>

        PR target/37101
        * config/i386/sse.md (*vec_concatv2di_avx): Remove vmovlps
        alternative.
        (*vec_concatv2di_rex64_avx): Likewise.

Modified:
    branches/ix86/avx/gcc/ChangeLog.avx
    branches/ix86/avx/gcc/config/i386/sse.md


-- 


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

[Bug tree-optimization/37101] [4.2/4.3 Regression] wrong code: tree vectorizer omits bogus movq/movlps construct

[cnstar9988 at gmail dot com]

------- Comment #9 from cnstar9988 at gmail dot com  2008-08-17 06:22 -------
ping...
fixed for 4_3 branch?


-- 


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

[Bug tree-optimization/37101] [4.2/4.3 Regression] wrong code: tree vectorizer omits bogus movq/movlps construct

[uros at gcc dot gnu dot org]

------- Comment #10 from uros at gcc dot gnu dot org  2008-08-17 14:58 -------
Subject: Bug 37101

Author: uros
Date: Sun Aug 17 14:57:00 2008
New Revision: 139178

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=139178
Log:
        PR target/37101
        * config/i386/sse.md (vec_concatv2di): Remove movlps alternative.
        (*vec_concatv2di_rex64_sse): Ditto.

testsuite/ChangeLog:

        PR target/37101
        * gcc.target/i386/pr37101.c: New test.


Added:
    branches/gcc-4_3-branch/gcc/testsuite/gcc.target/i386/pr37101.c
Modified:
    branches/gcc-4_3-branch/gcc/ChangeLog
    branches/gcc-4_3-branch/gcc/config/i386/sse.md
    branches/gcc-4_3-branch/gcc/testsuite/ChangeLog


-- 


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

[Bug target/37101] [4.2 Regression] wrong code: tree vectorizer omits bogus movq/movlps construct

[ubizjak at gmail dot com]

------- Comment #11 from ubizjak at gmail dot com  2008-08-17 17:24 -------
Fixed for 4.3.2.


-- 

ubizjak at gmail dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|critical                    |normal
          Component|tree-optimization           |target
           Priority|P3                          |P2
            Summary|[4.2/4.3 Regression] wrong  |[4.2 Regression] wrong code:
                   |code: tree vectorizer omits |tree vectorizer omits bogus
                   |bogus movq/movlps construct |movq/movlps construct


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

[Bug target/37101] [4.2 Regression] wrong code: tree vectorizer omits bogus movq/movlps construct

[jsm28 at gcc dot gnu dot org]

------- Comment #12 from jsm28 at gcc dot gnu dot org  2008-08-27 22:05 -------
4.3.2 is released, changing milestones to 4.3.3.


-- 

jsm28 at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.3.2                       |4.3.3


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

[Bug target/37101] [4.2 Regression] wrong code: tree vectorizer omits bogus movq/movlps construct

[rguenth at gcc dot gnu dot org]

-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to fail|                            |4.2.4 4.3.1
      Known to work|                            |4.3.2 4.4.0
   Target Milestone|4.3.3                       |4.2.5


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

[Bug target/37101] [4.2 Regression] wrong code: tree vectorizer omits bogus movq/movlps construct

[uros at gcc dot gnu dot org]

------- Comment #13 from uros at gcc dot gnu dot org  2008-08-29 09:43 -------
Subject: Bug 37101

Author: uros
Date: Fri Aug 29 09:41:57 2008
New Revision: 139758

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=139758
Log:
        Backport from mainline:
        2008-08-14  Christophe Saout  <christophe@saout.de>
                    Uros Bizjak  <ubizjak@gmail.com>

        PR target/37101
        * config/i386/sse.md (vec_concatv2di): Remove movlps alternative.

testsuite/ChangeLog:

        Backport from mainline:
        2008-08-14  Uros Bizjak  <ubizjak@gmail.com>

        PR target/37101
        * gcc.target/i386/pr37101.c: New test.


Added:
    branches/gcc-4_2-branch/gcc/testsuite/gcc.target/i386/pr37101.c
Modified:
    branches/gcc-4_2-branch/gcc/ChangeLog
    branches/gcc-4_2-branch/gcc/config/i386/sse.md
    branches/gcc-4_2-branch/gcc/testsuite/ChangeLog


-- 


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

[Bug target/37101] [4.2 Regression] wrong code: tree vectorizer omits bogus movq/movlps construct

[ubizjak at gmail dot com]

------- Comment #14 from ubizjak at gmail dot com  2008-08-29 09:44 -------
Fixed.


-- 

ubizjak at gmail dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED


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

[Bug target/37101] [4.2 Regression] wrong code: tree vectorizer omits bogus movq/movlps construct

[Emmanuel dot Thome at inria dot fr]

------- Comment #15 from Emmanuel dot Thome at inria dot fr  2008-09-02 20:53 -------
*** Bug 37340 has been marked as a duplicate of this bug. ***


-- 

Emmanuel dot Thome at inria dot fr changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |Emmanuel dot Thome at inria
                   |                            |dot fr


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

[Bug target/37101] [4.2 Regression] wrong code: tree vectorizer omits bogus movq/movlps construct

[pinskia at gcc dot gnu dot org]

-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.2.5                       |4.3.2


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