[PATCH, alpha]: Wrap {un,}aligned_store sequence with memory blockages.

[PATCH, alpha]: Wrap {un,}aligned_store sequence with memory blockages.

[Uros Bizjak]

[-- Attachment #1: Type: text/plain, Size: 2352 bytes --]

Hello!

The motivation for this patch was exposed miscompilation of gfortran
on alpha that resulted in:

FAIL: gfortran.dg/assumed_rank_3.f90:15.20:

    print *, ubound(x,dim=3)  ! << wrong dim
                    1
Error: Assumed-rank variable x at (1) may only be used as actual argument

The problem was in the miscompilation of resolve_actual_arglist from
resolve.c.  This function initializes two nearby global bool variables
with the following sequence:

  actual_arg = true;
  first_actual_arg = true;

but due to the miscompilation, the actual_arg was never set to true.
This happened due to the way stores to QImode and HImode locations are
implemented on non-BWX targets. The sequence reads full word, does its
magic to the part and stores the full word with changed part back to
the memory. However - the scheduler mixed two sequences, violating the
atomicity of RMW sequence.

This can be illustrated with following test:

--cut here--
static char *a;
static char *b;

void foo (void)
{
  a[1] = 1;
  b[2] = 1;
}

int bar (void)
{
  return a && b;
}
--cut here--

$foo..ng:
        .prologue 1
        lda $1,1($31)
        lda $2,a
        ldq $3,0($2)   <-- load a
        lda $2,b
        lda $7,1($3)
        ldq_u $5,1($3)   <-- load a
        insbl $1,$7,$4
        ldq $2,0($2)   <-- load b
        mskbl $5,$7,$5
        lda $6,2($2)
        bis $4,$5,$4
        stq_u $4,1($3)  <-- store a
        insbl $1,$6,$1
        ldq_u $3,2($2)   <-- load b
        mskbl $3,$6,$3
        cpys $f31,$f31,$f31
        bis $1,$3,$1
        stq_u $1,2($2)   <-- store b
        ret $31,($26),1
        .end foo

if a and b alias to the same wide memory location, then "b"  RMW
sequence corrupts "a".

The solution is to wrap the sequences with memory blockages to prevent
scheduler to move read and write around. These blockages thus ensure
atomicity of the sequence.

2014-06-27  Uros Bizjak  <ubizjak@gmail.com>

    * config/alpha/alpha.md (unspec): Add UNSPEC_MEMORY_BLOCKAGE.
    (*memory_blockage): New.
    (aligned_store): Wrap the expanded sequence with memory blockages
    (unaligned_store<mode>): Ditto.

The patch was bootstrapped and regression tested on alpha-linux-gnu,
with the compiler, configured with "--target=alpha-linux-gnu
--host=alpha-linux-gnu --build=alpha-linux-gnu".

OK for mainline and release branches?

Uros.

[-- Attachment #2: p.diff.txt --]
[-- Type: text/plain, Size: 2886 bytes --]

Index: config/alpha/alpha.md
===================================================================
--- config/alpha/alpha.md	(revision 212063)
+++ config/alpha/alpha.md	(working copy)
@@ -58,6 +58,9 @@
   UNSPEC_ATOMIC
   UNSPEC_CMPXCHG
   UNSPEC_XCHG
+
+  ;; Scheduling
+  UNSPEC_MEMORY_BLOCKAGE
 ])
 
 ;; UNSPEC_VOLATILE:
@@ -3689,6 +3692,16 @@
   [(set_attr "length" "0")
    (set_attr "type" "none")])
 
+;; Do not schedule instructions accessing memory across this point.
+
+(define_insn "*memory_blockage"
+  [(set (match_operand:BLK 0)
+	(unspec:BLK [(match_dup 0)] UNSPEC_MEMORY_BLOCKAGE))]
+  ""
+  ""
+  [(set_attr "length" "0")
+   (set_attr "type" "none")])
+
 (define_insn "jump"
   [(set (pc)
 	(label_ref (match_operand 0)))]
@@ -4269,7 +4282,9 @@
 ;; the value should be placed.  Operands 3 and 4 are SImode temporaries.
 
 (define_expand "aligned_store"
-  [(set (match_operand:SI 3 "register_operand")
+  [(set (match_dup 6)
+	(unspec:BLK [(match_dup 6)] UNSPEC_MEMORY_BLOCKAGE))
+   (set (match_operand:SI 3 "register_operand")
 	(match_operand:SI 0 "memory_operand"))
    (set (subreg:DI (match_dup 3) 0)
 	(and:DI (subreg:DI (match_dup 3) 0) (match_dup 5)))
@@ -4278,11 +4293,15 @@
 		   (match_operand:DI 2 "const_int_operand")))
    (set (subreg:DI (match_dup 4) 0)
 	(ior:DI (subreg:DI (match_dup 4) 0) (subreg:DI (match_dup 3) 0)))
-   (set (match_dup 0) (match_dup 4))]
+   (set (match_dup 0) (match_dup 4))
+   (set (match_dup 6)
+	(unspec:BLK [(match_dup 6)] UNSPEC_MEMORY_BLOCKAGE))]
   ""
 {
   operands[5] = GEN_INT (~ (GET_MODE_MASK (GET_MODE (operands[1]))
 			    << INTVAL (operands[2])));
+  operands[6] = gen_rtx_MEM (BLKmode, gen_rtx_SCRATCH (Pmode));
+  MEM_VOLATILE_P (operands[6]) = 1;
 })
 
 ;; For the unaligned byte and halfword cases, we use code similar to that
@@ -4293,7 +4312,9 @@
 ;; operand 2 can be that register.
 
 (define_expand "unaligned_store<mode>"
-  [(set (match_operand:DI 3 "register_operand")
+  [(set (match_dup 6)
+	(unspec:BLK [(match_dup 6)] UNSPEC_MEMORY_BLOCKAGE))
+   (set (match_operand:DI 3 "register_operand")
 	(mem:DI (and:DI (match_operand:DI 0 "address_operand")
 			(const_int -8))))
    (set (match_operand:DI 2 "register_operand")
@@ -4308,9 +4329,15 @@
 		   (ashift:DI (match_dup 2) (const_int 3))))
    (set (match_dup 4) (ior:DI (match_dup 4) (match_dup 3)))
    (set (mem:DI (and:DI (match_dup 0) (const_int -8)))
-	(match_dup 4))]
+	(match_dup 4))
+   (set (match_dup 6)
+	(unspec:BLK [(match_dup 6)] UNSPEC_MEMORY_BLOCKAGE))]
   ""
-  "operands[5] = GEN_INT (GET_MODE_MASK (<MODE>mode));")
+{
+  operands[5] = GEN_INT (GET_MODE_MASK (<MODE>mode));
+  operands[6] = gen_rtx_MEM (BLKmode, gen_rtx_SCRATCH (Pmode));
+  MEM_VOLATILE_P (operands[6]) = 1;
+})
 
 ;; Here are the define_expand's for QI and HI moves that use the above
 ;; patterns.  We have the normal sets, plus the ones that need scratch

Re: [PATCH, alpha]: Wrap {un,}aligned_store sequence with memory blockages.

[Richard Henderson]

On 06/27/2014 10:04 AM, Uros Bizjak wrote:
> This happened due to the way stores to QImode and HImode locations are
> implemented on non-BWX targets. The sequence reads full word, does its
> magic to the part and stores the full word with changed part back to
> the memory. However - the scheduler mixed two sequences, violating the
> atomicity of RMW sequence.

Except that addresses with AND in them (ldq_u, stq_u) are already supposed to
be memory barriers.  So you shouldn't need to add such to them again.

I think something else has gone wrong somewhere.


r~

Re: [PATCH, alpha]: Wrap {un,}aligned_store sequence with memory blockages.

[Uros Bizjak]

[-- Attachment #1: Type: text/plain, Size: 1378 bytes --]

On Fri, Jun 27, 2014 at 10:04 PM, Richard Henderson <rth@redhat.com> wrote:
> On 06/27/2014 10:04 AM, Uros Bizjak wrote:
>> This happened due to the way stores to QImode and HImode locations are
>> implemented on non-BWX targets. The sequence reads full word, does its
>> magic to the part and stores the full word with changed part back to
>> the memory. However - the scheduler mixed two sequences, violating the
>> atomicity of RMW sequence.
>
> Except that addresses with AND in them (ldq_u, stq_u) are already supposed to
> be memory barriers.  So you shouldn't need to add such to them again.
>
> I think something else has gone wrong somewhere.

There is am early shortcut for MEM_READOLNY_P in true_dependence_1.

In this case,

(insn 15 13 18 2 (set (reg/f:DI 78 [ b ])
        (mem/u/f/c:DI (reg/f:DI 79) [2 b+0 S8 A64])) rmw.c:7 226 {*movdi}
     (expr_list:REG_DEAD (reg/f:DI 79)
        (nil)))

is free to be scheduled before

(insn 13 12 15 2 (set (mem:DI (and:DI (plus:DI (reg/f:DI 72 [ a ])
                    (const_int 1 [0x1]))
                (const_int -8 [0xfffffffffffffff8])) [0  S8 A64])
        (reg:DI 77)) rmw.c:6 226 {*movdi}
     (expr_list:REG_DEAD (reg:DI 77)
        (expr_list:REG_DEAD (reg/f:DI 72 [ a ])
            (nil))))

Attached RFC patch also fixes the testcase, trivially preventing
scheduling of (insn 13) before (insn 15).

Uros.

[-- Attachment #2: alias.diff.txt --]
[-- Type: text/plain, Size: 1031 bytes --]

Index: alias.c
===================================================================
--- alias.c	(revision 212063)
+++ alias.c	(working copy)
@@ -2468,10 +2468,19 @@
       || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
     return 1;
 
+  if (! mem_addr)
+    {
+      mem_addr = XEXP (mem, 0);
+      if (mem_mode == VOIDmode)
+	mem_mode = GET_MODE (mem);
+    }
+
   /* Read-only memory is by definition never modified, and therefore can't
      conflict with anything.  We don't expect to find read-only set on MEM,
      but stupid user tricks can produce them, so don't die.  */
   if (MEM_READONLY_P (x))
+    if (GET_CODE (mem_addr) == AND)
+      return 1;
     return 0;
 
   /* If we have MEMs referring to different address spaces (which can
@@ -2480,13 +2489,6 @@
   if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x))
     return 1;
 
-  if (! mem_addr)
-    {
-      mem_addr = XEXP (mem, 0);
-      if (mem_mode == VOIDmode)
-	mem_mode = GET_MODE (mem);
-    }
-
   if (! x_addr)
     {
       x_addr = XEXP (x, 0);

Re: [PATCH, alpha]: Wrap {un,}aligned_store sequence with memory blockages.

[Richard Henderson]

On 06/29/2014 11:14 AM, Uros Bizjak wrote:
>    if (MEM_READONLY_P (x))
> +    if (GET_CODE (mem_addr) == AND)
> +      return 1;
>      return 0;

Certainly missing braces here.  But with that fixed the patch looks plausible.
 I'll look at it closer later today.


r~

Re: [PATCH, alpha]: Wrap {un,}aligned_store sequence with memory blockages.

[Uros Bizjak]

On Mon, Jun 30, 2014 at 5:54 PM, Richard Henderson <rth@redhat.com> wrote:
> On 06/29/2014 11:14 AM, Uros Bizjak wrote:
>>    if (MEM_READONLY_P (x))
>> +    if (GET_CODE (mem_addr) == AND)
>> +      return 1;
>>      return 0;
>
> Certainly missing braces here.  But with that fixed the patch looks plausible.
>  I'll look at it closer later today.

Uh, yes ... this RFC patch was not thoroughly tested (its intention
was to illustrate the problem and possible solution).

Uros.

Re: [PATCH, alpha]: Wrap {un,}aligned_store sequence with memory blockages.

[Richard Biener]

On Mon, Jun 30, 2014 at 5:54 PM, Richard Henderson <rth@redhat.com> wrote:
> On 06/29/2014 11:14 AM, Uros Bizjak wrote:
>>    if (MEM_READONLY_P (x))
>> +    if (GET_CODE (mem_addr) == AND)
>> +      return 1;
>>      return 0;
>
> Certainly missing braces here.  But with that fixed the patch looks plausible.
>  I'll look at it closer later today.

Umm... but certainly a very gross hack for a special target in a very
general routine.

So - please no!

If addresses with AND are supposed to be barriers then you should
model this explicitely in the IL and not make it work "magically".
Maybe use ALIAS_SET_MEMORY_BARRIER instead?

Richard.

>
> r~

Re: [PATCH, alpha]: Wrap {un,}aligned_store sequence with memory blockages.

[Richard Henderson]

On 07/07/2014 02:10 AM, Richard Biener wrote:
> On Mon, Jun 30, 2014 at 5:54 PM, Richard Henderson <rth@redhat.com> wrote:
>> On 06/29/2014 11:14 AM, Uros Bizjak wrote:
>>>    if (MEM_READONLY_P (x))
>>> +    if (GET_CODE (mem_addr) == AND)
>>> +      return 1;
>>>      return 0;
>>
>> Certainly missing braces here.  But with that fixed the patch looks plausible.
>>  I'll look at it closer later today.
> 
> Umm... but certainly a very gross hack for a special target in a very
> general routine.
> 
> So - please no!
> 
> If addresses with AND are supposed to be barriers then you should
> model this explicitely in the IL and not make it work "magically".

Huh?  We've supported AND as a conflict-with-most address for like forever.
It's not just Alpha that uses them either; at least Altivec as well.

> Maybe use ALIAS_SET_MEMORY_BARRIER instead?


r~

Re: [PATCH, alpha]: Wrap {un,}aligned_store sequence with memory blockages.

[Richard Biener]

On Mon, Jul 7, 2014 at 4:20 PM, Richard Henderson <rth@redhat.com> wrote:
> On 07/07/2014 02:10 AM, Richard Biener wrote:
>> On Mon, Jun 30, 2014 at 5:54 PM, Richard Henderson <rth@redhat.com> wrote:
>>> On 06/29/2014 11:14 AM, Uros Bizjak wrote:
>>>>    if (MEM_READONLY_P (x))
>>>> +    if (GET_CODE (mem_addr) == AND)
>>>> +      return 1;
>>>>      return 0;
>>>
>>> Certainly missing braces here.  But with that fixed the patch looks plausible.
>>>  I'll look at it closer later today.
>>
>> Umm... but certainly a very gross hack for a special target in a very
>> general routine.
>>
>> So - please no!
>>
>> If addresses with AND are supposed to be barriers then you should
>> model this explicitely in the IL and not make it work "magically".
>
> Huh?  We've supported AND as a conflict-with-most address for like forever.
> It's not just Alpha that uses them either; at least Altivec as well.

Ugh.  I wasn't aware of that - is this documented anywhere?  What
exactly does such address conflict with?  Does it inhibit type-based analysis?

Where do those ANDs come from?  If there were a target where
ANDs would be valid part of addresses in memory accesses but
they wouldn't impose such barriers how'd we deal with that
(altivec aligned (masked) loads come to my mind - I don't see why
they would conflict with more than they say).

Btw, if the mem is MEM_READONLY_P how can it be part of
a {un}aligned_store sequence?

Richard.

>> Maybe use ALIAS_SET_MEMORY_BARRIER instead?
>
> r~
>

Re: [PATCH, alpha]: Wrap {un,}aligned_store sequence with memory blockages.

[Richard Biener]

On Mon, Jul 7, 2014 at 4:34 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Mon, Jul 7, 2014 at 4:20 PM, Richard Henderson <rth@redhat.com> wrote:
>> On 07/07/2014 02:10 AM, Richard Biener wrote:
>>> On Mon, Jun 30, 2014 at 5:54 PM, Richard Henderson <rth@redhat.com> wrote:
>>>> On 06/29/2014 11:14 AM, Uros Bizjak wrote:
>>>>>    if (MEM_READONLY_P (x))
>>>>> +    if (GET_CODE (mem_addr) == AND)
>>>>> +      return 1;
>>>>>      return 0;
>>>>
>>>> Certainly missing braces here.  But with that fixed the patch looks plausible.
>>>>  I'll look at it closer later today.
>>>
>>> Umm... but certainly a very gross hack for a special target in a very
>>> general routine.
>>>
>>> So - please no!
>>>
>>> If addresses with AND are supposed to be barriers then you should
>>> model this explicitely in the IL and not make it work "magically".
>>
>> Huh?  We've supported AND as a conflict-with-most address for like forever.
>> It's not just Alpha that uses them either; at least Altivec as well.
>
> Ugh.  I wasn't aware of that - is this documented anywhere?  What
> exactly does such address conflict with?  Does it inhibit type-based analysis?
>
> Where do those ANDs come from?  If there were a target where
> ANDs would be valid part of addresses in memory accesses but
> they wouldn't impose such barriers how'd we deal with that
> (altivec aligned (masked) loads come to my mind - I don't see why
> they would conflict with more than they say).
>
> Btw, if the mem is MEM_READONLY_P how can it be part of
> a {un}aligned_store sequence?

Looking at the testcase I see how we might mishandle RMW
ops here (but still fail to see why MEM_READONLY_P should
be an issue).  There is an old bug where this sort of thing
triggers on x86_64 as well from generic expansion of block
copies IIRC where we store with a word_mode sequence but
fail to use a smaller mode for the last piece (PR36043 if I
remember correctly).

As for the alias issue it would be nice if the RTL alias oracle
would be able to early out if memrefs_conflict_p would detect
a must-alias.

Richard.

> Richard.
>
>>> Maybe use ALIAS_SET_MEMORY_BARRIER instead?
>>
>> r~
>>

Re: [PATCH, alpha]: Wrap {un,}aligned_store sequence with memory blockages.

[Richard Henderson]

On 07/07/2014 07:34 AM, Richard Biener wrote:
> Ugh.  I wasn't aware of that - is this documented anywhere?  What
> exactly does such address conflict with?  Does it inhibit type-based analysis?

Dunno if it's documented anywhere.  Such addresses conflict with anything,
unless it can be proven not to be overlapping with the alignment.

> Where do those ANDs come from?

Usually the move expander for the mode.

> If there were a target where
> ANDs would be valid part of addresses in memory accesses but
> they wouldn't impose such barriers how'd we deal with that
> (altivec aligned (masked) loads come to my mind - I don't see why
> they would conflict with more than they say).

It's not the loads, per se, it's the stores that get in the way.

Early alpha can't store sub-4-byte quantities.  Altivec can't store anything
but 16 byte quantities.  In order to perform smaller stores, we have to do a
read-modify-write sequence on a larger aligned chunk of memory.  Two such RMW
sequences must conflict, lest we interleave and thus bork the operation.

I don't recall how much we ever did for this, exactly, but it's certainly
possible to know that some memory operations cannot conflict with these RMW
sequence.  E.g. through size + alignment of the other memory operation.  E.g.
on Alpha, a byte RMW store can't conflict with a normal DImode memory access.

> Btw, if the mem is MEM_READONLY_P how can it be part of
> a {un}aligned_store sequence?

Er... that's an excellent question.  Uros?


r~

Re: [PATCH, alpha]: Wrap {un,}aligned_store sequence with memory blockages.

[Uros Bizjak]

On Mon, Jul 7, 2014 at 5:01 PM, Richard Henderson <rth@redhat.com> wrote:

> Early alpha can't store sub-4-byte quantities.  Altivec can't store anything
> but 16 byte quantities.  In order to perform smaller stores, we have to do a
> read-modify-write sequence on a larger aligned chunk of memory.  Two such RMW
> sequences must conflict, lest we interleave and thus bork the operation.
>
> I don't recall how much we ever did for this, exactly, but it's certainly
> possible to know that some memory operations cannot conflict with these RMW
> sequence.  E.g. through size + alignment of the other memory operation.  E.g.
> on Alpha, a byte RMW store can't conflict with a normal DImode memory access.
>
>> Btw, if the mem is MEM_READONLY_P how can it be part of
>> a {un}aligned_store sequence?
>
> Er... that's an excellent question.  Uros?

This flag is copied from the original memory operand by
alpha_set_memflags to all memory operands in the expanded sequence.

Uros.

Re: [PATCH, alpha]: Wrap {un,}aligned_store sequence with memory blockages.

[Richard Henderson]

On 07/07/2014 09:35 AM, Uros Bizjak wrote:
> On Mon, Jul 7, 2014 at 5:01 PM, Richard Henderson <rth@redhat.com> wrote:
> 
>> Early alpha can't store sub-4-byte quantities.  Altivec can't store anything
>> but 16 byte quantities.  In order to perform smaller stores, we have to do a
>> read-modify-write sequence on a larger aligned chunk of memory.  Two such RMW
>> sequences must conflict, lest we interleave and thus bork the operation.
>>
>> I don't recall how much we ever did for this, exactly, but it's certainly
>> possible to know that some memory operations cannot conflict with these RMW
>> sequence.  E.g. through size + alignment of the other memory operation.  E.g.
>> on Alpha, a byte RMW store can't conflict with a normal DImode memory access.
>>
>>> Btw, if the mem is MEM_READONLY_P how can it be part of
>>> a {un}aligned_store sequence?
>>
>> Er... that's an excellent question.  Uros?
> 
> This flag is copied from the original memory operand by
> alpha_set_memflags to all memory operands in the expanded sequence.

Misses the point.  Store on a MEM_READONLY_P?

I suppose I should take a closer look today...


r~