[Bug rtl-optimization/50489] New: [UPC/IA64] mis-schedule of MEM ref with -ftree-vectorize and -fschedule-insns2

[Bug rtl-optimization/50489] New: [UPC/IA64] mis-schedule of MEM ref with -ftree-vectorize and -fschedule-insns2

[gary at intrepid dot com]

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

             Bug #: 50489
           Summary: [UPC/IA64] mis-schedule of MEM ref with
                    -ftree-vectorize and -fschedule-insns2
    Classification: Unclassified
           Product: gcc
           Version: 4.7.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: rtl-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: gary@intrepid.com
            Target: IA64


After a change in GUPC's tree-lowering pass made a couple of months back (that
simplified the tree code being generated), we saw regressions where several
small test cases were failing on an IA64 target (SGI Altix, running SUSE).

We have been unable so far to reduce this to a "C" only test case that
demonstrates the problem, so we are submitting this as a "UPC" bug report,
along with a script that will build the UPC compiler from the GUPC branch, and
create the various bug artifacts.  Perhaps someone knowledgeable with the
instruction scheduler will understand how this mis-scheduling happens and
either reproduce the issue as a "C" test case, or propose a patch.

We also do not know at this time if the UPC compiler should be generating
memory barriers or generate some other metadata to avoid this mis-scheduling,
and would appreciate any suggestions in that regard.

The attached UPC test case works fine when "-O2 -ftree-vectorize
-fno-schedule-insns2" is asserted, but demonstrates a mis-schedule when "-O2
-ftree-vectorize" is asserted.

The following description is copied from the
README-ia64-upc-sched-insn2-bug.txt file that is included in the attached zip
file as well.

Background
----------

On a 64-bit target (using the "struct PTS" configuration),
the UPC compiler represents UPC pointer-to-shared values 
as 128-bit structures with three fields: (vaddr, thread, phase)
as shown in the declaration below.

typedef struct shared_ptr_struct
  {
    void     *vaddr;
    uint32_t thread;
    uint32_t phase;
  } upc_shared_ptr_t
  __attribute__ ((aligned (16)))
  ;

In: ia64-upc-vaddr-bug.upc.143t.optimized, there is the following
sequence of tree statements.

  unsigned int D.3062;
  unsigned int D.3061;
  shared [8] struct foo * D.3060;
  shared [8] struct foo[1] * D.3059;
  struct upc_shared_ptr_t D.3058;
  unsigned int D.3057;

  D.3057_10 = D.3056_9 * 8;
  D.3058.vaddr = &_u_barray;
  MEM[(struct upc_shared_ptr_t *)&D.3058 + 8B] = { 0, 0 };
  D.3059_11 = VIEW_CONVERT_EXPR<shared [8] struct foo[1] *>(D.3058);
  D.3060_12 = (shared [8] struct foo *) D.3059_11;
  D.3061_13 = VIEW_CONVERT_EXPR<struct upc_shared_ptr_t>(D.3060_12).phase;
  D.3062_14 = D.3057_10 + D.3061_13;

D.3059_11 and D.3060_12 are UPC pointers-to-shared (PTS's);
these are 128-bit "fat" pointers with internal
{vaddr, thread, phase} fields.

D.3058 is a PTS representation struct that is initialized
to {&_u_barray, 0, 0}.  Note that D.3059_11 and D.3060_12
are copies of the PTS representation structure, D.3058
that have been recast into a UPC pointer-to-shared (PTS).

The casts above might impose inefficiencies, and there may
be ways to improve the code, but this is the current
tree code that is generated.

This assignment statement:
  D.3061_13 = VIEW_CONVERT_EXPR<struct upc_shared_ptr_t>(D.3060_12).phase;
extracts the 'phase' field from D.3060_12, which is a copy
of the value of D.3058.phase.  The value of D.3058.phase was
previously initialized to zero by the MEM[] assignment.
The fetched phase value D.3061_13 should be zero when this
assignment is executed.

Bug
---

It is this latter access to D.3060_12.phase that expands
into incorrect RTL after the selective instruction scheduling
pass is run.  The access to D.3060_12.phase is scheduled
ahead of the code that sets D.3058.phase.

Valid RTL
---------

The 'ok' and 'bug' compilations share the same RTL dump output all
the way through ia64-upc-vaddr-bug.upc.213r.compgotos.
In that file there RTL statements that are affected by the
mis-scheduling of instructions.  (additional notes added
as '#' comments):

# D.3058.vaddr = &_u_barray (the base address of barray.
#
# r34 was previously assigned the value of &_u_barray
# r47 = r12 + 32;
# r12 is the stack pointer and r47 points to the beginning
# of the D.3058 structure, which also happens to be the
# address of the first field, D.3058.vaddr.
# Therefore, r47 points to D.3058.vaddr

(insn 46 42 331 4 (set (mem/s/f/c:DI (reg/f:DI 47 r47 [532]) [2 D.3058.vaddr+0
S8 A128])
        (reg/f:DI 34 r34 [533])) ia64-upc-vaddr-bug.upc:11 5 {movdi_internal}
     (nil))

# This vector op assigns: {D.3058.thread = 0; D.3058.phase = 0;}
#
# This is done by using r46 as the destination address and r36 as the source.
# r46 = r12 + 40, which is the base address of D.3058.thread.
#                 (D.3058.phase is the field following the D.3058.thread)
# r36 was previously set to {0, 0}.

(insn 52 69 65 4 (set (mem/s/c:V2SI (reg/f:DI 46 r46 [534]) [3 MEM[(struct
upc_shared_ptr_t *)&D.3058 + 8B]+0 S8 A64])
        (reg:V2SI 36 r36 [536])) ia64-upc-vaddr-bug.upc:11 377
{*movv2si_internal}
     (nil))

# r37 = D.3085.phase by indirecting through r45
#
# r12 is the stack pointer
# D.3085.vaddr  starts at r12 + 32
# D.3085.thread starts at r12 + 40
# D.3085.phase  starts at r12 + 44
# r45 = (r12 + 44); where r12 is the stack pointer and 44
#                   is the offset of D.3085.phase
# Therefore, r45 points to D.3058.phase.

(insn 57 59 68 4 (set (reg:DI 37 r37)
        (zero_extend:DI (mem/s/j/c:SI (reg/f:DI 45 r45 [524]) [0
VIEW_CONVERT_EXPR<struct upc_shared_ptr_t>(D.3060_12).phase+0 S4 A32])))
ia64-upc-vaddr-bug.upc:11 136 {zero_extendsidi2}
     (nil))

Although there are intervening instructions, the key thing to note
is that the first two instructions (46 and 52) initialize the
contents of D.3085, and the instruction (57) fetches the
value of D.3085.phase.  This is a valid ordering.

Incorrect RTL: after instruction scheduling
-------------------------------------------

The file ia64-upc-vaddr-bug.upc.215r.mach dumps the RTL
*after* the selective scheduling pass has run.  Here, we
see that D.3058.phase is fetched *before* it is set by
the vector operation.

The following RTL is copied directly from the .mach dump file and
appears exactly in the order shown.

# r37 = D.3058.phase by indirecting through r45
# r45 points to D.3058.phase [r12 + 44]
#
# BUG: D.3058.phase has *not* been initialized at this point.
#

(insn:TI 57 507 506 4 (set (reg:DI 37 r37)
        (zero_extend:DI (mem/s/j/c:SI (reg/f:DI 45 r45 [524]) [0
VIEW_CONVERT_EXPR<struct upc_shared_ptr_t>(D.3060_12).phase+0 S4 A32])))
ia64-upc-vaddr-bug.upc:11 136 {zero_extendsidi2}
     (nil))

# Initialize {D.3058.thread = 0; D.3058.phase = 0} via a vector operation.
#
# BUG: this vector operation should precede the instruction that
# fetches D.3058.phase, but the instruction scheduler has incorrectly
# scheduled this vector assignment after the fetch.  It apparently
# did *not* notice that the memory vector beginning at r46 [r12 + 40] aliases
# both D.3058.thread and D.3058.phase and that r45 [r12 + 44] points
# to D.3058.phase, and therefore is being used to fetch
# the value of D.3058.phase.
#

(insn 52 501 17 4 (set (mem/s/c:V2SI (reg/f:DI 46 r46 [534]) [3 MEM[(struct
upc_shared_ptr_t *)&D.3058 + 8B]+0 S8 A64])
        (reg:V2SI 36 r36 [536])) ia64-upc-vaddr-bug.upc:11 377
{*movv2si_internal}
     (nil))

[Bug rtl-optimization/50489] [UPC/IA64] mis-schedule of MEM ref with -ftree-vectorize and -fschedule-insns2

[gary at intrepid dot com]

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

--- Comment #1 from Gary Funck <gary at intrepid dot com> 2011-09-22 19:21:54 UTC ---
Created attachment 25343
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=25343
UPC test case that demonstrates instruction mis-schedule

[Bug rtl-optimization/50489] [UPC/IA64] mis-schedule of MEM ref with -ftree-vectorize and -fschedule-insns2

[gary at intrepid dot com]

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

--- Comment #2 from Gary Funck <gary at intrepid dot com> 2011-09-22 19:31:04 UTC ---
Created attachment 25344
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=25344
zipped tar file with build script, readme, test case and test artifacts

[Bug rtl-optimization/50489] [UPC/IA64] mis-schedule of MEM ref with -ftree-vectorize and -fschedule-insns2

[amonakov at gcc dot gnu.org]

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

Alexander Monakov <amonakov at gcc dot gnu.org> changed:

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

--- Comment #3 from Alexander Monakov <amonakov at gcc dot gnu.org> 2011-09-23 09:30:01 UTC ---
Does the problem vanish if you add -fno-strict-aliasing?

One more thing, you mention -O2 in the flags, but then refer to selective
scheduler, which is only enabled at -O3.  Perhaps you meant Haifa scheduler.

[Bug rtl-optimization/50489] [UPC/IA64] mis-schedule of MEM ref with -ftree-vectorize and -fschedule-insns2

[gary at intrepid dot com]

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

--- Comment #4 from Gary Funck <gary at intrepid dot com> 2011-09-23 17:38:18 UTC ---
(In reply to comment #3)
> Does the problem vanish if you add -fno-strict-aliasing?
> 
> One more thing, you mention -O2 in the flags, but then refer to selective
> scheduler, which is only enabled at -O3.  Perhaps you meant Haifa scheduler.

The tests still fail with "-O3 -fno-strict-aliasing".  They pass with "-O3
-fno-schedule-insns2".  We mentioned -O2 in the bug report, because it helped
rule out other optimizations that -O3 might imply.  Then we selectively added
"-ftree-vectorize" and "-fschedule-insns2" to demonstrate that the combination
of those additional optimizations will demonstrate the mis-scheduling.

If there are additional tests that you suggest that we can run to help narrow
this down, let us know, and we'll try to provide that additional information. 
Also, we can provide a script to run gdb on "cc1upc", if that helps.  Thanks.

[Bug rtl-optimization/50489] [UPC/IA64] mis-schedule of MEM ref with -ftree-vectorize and -fschedule-insns2

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-09-25 12:13:44 UTC ---
  D.3059_11 = VIEW_CONVERT_EXPR<shared [8] struct foo[1] *>(D.3058);

looks like bogus IL to me.  You view D.3058, a struct of size 16, as
a pointer (of size 8).  I suppose you want to load D.3058.vaddr here?

  D.3060_12 = (shared [8] struct foo *) D.3059_11;
  D.3061_13 = VIEW_CONVERT_EXPR<struct upc_shared_ptr_t>(D.3060_12).phase;

looks bogus IL to me.  It views the pointer(!?) D.3060_12 as being a
struct upc_shared_ptr_t and extracts a value that is not within that
pointer.

But maybe I'm missing something because I don't recognize that 'shared [8]'
qualification.

Do you want to dereference D.3060_12 (D.3058.vaddr) here?

That said, I wonder why you don't trip over tree-cfg.c verification
of VIEW_CONVERT_EXPR as TYPE_SIZE (TREE_TYPE (D.3060_12)) != TYPE_SIZE (struct
upc_shared_ptr_t).

Please try to avoid using VIEW_CONVERT_EXPRs completely unless you know
exactly what you are doing.

[Bug rtl-optimization/50489] [UPC/IA64] mis-schedule of MEM ref with -ftree-vectorize and -fschedule-insns2

[gary at intrepid dot com]

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

--- Comment #6 from Gary Funck <gary at intrepid dot com> 2011-09-25 19:58:58 UTC ---
(In reply to comment #5)
>   D.3059_11 = VIEW_CONVERT_EXPR<shared [8] struct foo[1] *>(D.3058);
> 
> looks like bogus IL to me.  You view D.3058, a struct of size 16, as
> a pointer (of size 8).  I suppose you want to load D.3058.vaddr here?
> 
>   D.3060_12 = (shared [8] struct foo *) D.3059_11;
>   D.3061_13 = VIEW_CONVERT_EXPR<struct upc_shared_ptr_t>(D.3060_12).phase;
> 
> looks bogus IL to me.  It views the pointer(!?) D.3060_12 as being a
> struct upc_shared_ptr_t and extracts a value that is not within that
> pointer.
> 
> But maybe I'm missing something because I don't recognize that 'shared [8]'
> qualification.  [...]

The syntax (shared [8] struct foo *) above is unique to UPC.  This is a pointer
to a "shared' qualified object with a "blocking factor" (layout qualifier) of
8.  This type of pointer is called a "pointer-to-shared" (PTS) in the UPC
language definition; it is a pointer that can span nodes.  On a 64-bit machine,
using the "sturct PTS" (as opposed to "packed PTS") representation it is a 16
byte quantity.  Thus the casts back/forth between (shared *) and "struct
upc_shared_ptr_t" do not violate the size assumptions of VIEW_CONVERT_EXPR().

The "blocking factor" (the [8] in "shared [8] *" above) is unique to UPC.  In
UPC, arrays are "block distributed".  This means that block 0 is on thread 0,
block 1 is on thread 1 and so on.  Thus, for a UPC program that is run with 2
threads, foo[0], foo[1] ... foo[7] are allocated on (have "affinity to") thread
0 and foo[8], foo[9] ... foo[13] are allocated on thread 1.  This blocking
factor provides for the ability to cast a pointer to a block of shared storage
into a regular "C" pointer (a "local" pointer) as long as the thread performing
the cast has affinity to the block.

What is potentially troublesome for the "middle end" tree optimizations and
"back end" RTL optimizations is that these pointers-to-shared (PTS's) are "fat"
pointers.  Note that after the lowering pass (performed in
upc/upc-genericize.c) that there will be no *indirections* through a PTS. 
Instead, indirections of a PTS in a value context will be converted into "get"
calls, which are implemented by the UPC runtime (libupc/smp).  Indirections
that are the targets of assignments are translated into "put" calls,
implemented by the UPC runtime. 

The lowering pass also translates UPC pointer-to-shared arithmetic operations
into their equivalent operations which do not involve PTS's, but rather cast
the PTS's to their representation type (struct upc_shared_ptr_t) and then
operate on the component parts of the PTS.  As you can see from the description
of blocking factors above, the mapping of foo[i] to its (global) address
requires a fairly complex arrangement of division and modulo operations.

The libupc runtime is unique in that parts of it may be inlined.  Inlining of
the runtime is enabled at optimization levels greater than 0, or it can be
explicitly inlined/not-inlined via the -fupc-inline-lib switch.  The inlining
is accomplished via a pre-include of a runtime header file, implemented by the
"upc" driver.  Inlining is enabled in the test case documented in this bug
report.  Thus, a simple assignment statement involving array indexing of a UPC
shared "blocked" array expands into a rather complex assortment of tree code,
and generated RTL.  (This complexity makes it difficult to create an equivalent
"C" test case.)

After lowering, any references to "shared *" (pointers-to-shared) should only
occur in casts to/from the representation type and in moves/copies of the PTS
container.  We have run into a few places where the middle end makes some
assumptions about regular pointers and tries to apply those assumptions to a
UPC pointer-to-shared; we have been able to exclude PTS's by adding additional
checks for them -- there are not many places that we have had to do this. 
Perhaps that sort of pointer-specific logic is kicking in here.

Arguably, the UPC lowering pass should fully lower PTS typed expressions, so
that they don't end up in the tree.  Potentially, a PTS hanging around in the
tree doesn't meet the strict (or even not-so-strict) definition of GENERIC. 
Fully lowering those expressions is on our "to do" list.  When we do that,
rather than using casts, we will likely rewrite the PTS type references into
references to the PTS representation type.  We have shied away from this
because it makes the resulting tree code even more difficult to follow, because
it loses logical correspondence to the original "C" source statements.

That said, this technique of casting a PTS to its representation type and then
extracting its sub-parts has been working for quite a while on several
different target architectures.  However, maybe this recast of a
pointer-to-shared is confusing the post-reload instruction scheduler and/or the
logic that creates the MEM_REF?.

We would like to see if we can find a way to make the current lowering pass
approach work, because it does work in many contexts, and will allow us to make
forward progress without making the lowering pass re-work become a critical
path task.  Also, we don't know that the presence of a PTS-typed node in the
tree is actually the cause of the problem.

[Bug rtl-optimization/50489] [UPC/IA64] mis-schedule of MEM ref with -ftree-vectorize and -fschedule-insns2

[gary at intrepid dot com]

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

--- Comment #7 from Gary Funck <gary at intrepid dot com> 2011-10-17 03:04:08 UTC ---
Do you have any suggestions on additional tests, debug steps that we can
perform to narrow down the factors that lead to instructions being
mis-scheduled?

[Bug rtl-optimization/50489] [UPC/IA64] mis-schedule of MEM ref with -ftree-vectorize and -fschedule-insns2

[olegendo at gcc dot gnu.org]

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

--- Comment #8 from Oleg Endo <olegendo at gcc dot gnu.org> 2012-08-20 20:54:25 UTC ---
Author: olegendo
Date: Mon Aug 20 20:54:20 2012
New Revision: 190545

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=190545
Log:
    PR target/50489
    * config/sh/sh.md (rotcr, *rotcr, shar, shlr): New insns and splits.
    (ashrdi3_k, lshrdi3_k): Rewrite as insn_and_split.
    * config/sh/sh.c (sh_lshrsi_clobbers_t_reg_p): New function.
    * config/sh/sh-protos.h (sh_lshrsi_clobbers_t_reg_p): Declare it.

    PR target/50489
    * gcc.target/sh/pr54089-1.c: New.


Added:
    trunk/gcc/testsuite/gcc.target/sh/pr54089-1.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/config/sh/sh-protos.h
    trunk/gcc/config/sh/sh.c
    trunk/gcc/config/sh/sh.md
    trunk/gcc/testsuite/ChangeLog

[Bug rtl-optimization/50489] [UPC/IA64] mis-schedule of MEM ref with -ftree-vectorize and -fschedule-insns2

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|---                         |INVALID

--- Comment #9 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Since this based on an  out of tree patch set and the patch set has not been
updated since GCC 5, I am going to close this as invalid. It is not obvious if
this was a scheduler issue or a bug in the GUPC code.