llvm dev - May 2020 - LLVM's loop unroller & llvm.loop.parallel_accesses

This is interesting! So are you saying that loop.parallel_accesses strictly
loop parallel, and says nothing about aliasing? I see, I guess we may
have been "abusing" the hint and re-purposed it. But isn't
llvm's
vectorizer using loop.parallel_accesses to vectorize loops including
vectorize memory accesses that if you ignore loop-carried dependencies,
usually means effectively re-ordering the accesses? I guess this still does
not imply "noalias"? What about icc/gcc's #pragma ivdep? Again
here, it
means no loop-carried dependencies, yet still doesn't say anything about
noalias? Another way indeed would be to propagate noalias data and indeed
rely on the future fix that Hal mentions above.



On Thu, May 14, 2020 at 1:33 PM Michael Kruse <llvmdev at meinersbur.de>
wrote:
> llvm.loop.parallel_accesses does not imply that these accesses from
> different iterations are not aliasing. Examples where an access are
> parallel are that the accesses are atomic or read-only from a specific
> location.
>
> The LoopUnrollPass might deduce that non-atomic stores are necessarily
> not aliasing (when not using transactional memory), but I don't think
> we can do this for all the read accesses. Would that be sufficiently
> useful?
>
> Michael
>
>
> Am Do., 14. Mai 2020 um 15:11 Uhr schrieb Hendrik Greving via llvm-dev
> <llvm-dev at lists.llvm.org>:
> >
> > Hi, in our backend, which is unfortunately not upstreamed, we are
> relying on llvm.loop.parallel_accesses metadata for certain passes like
> software pipelining so we can re-order instructions. Ideally, we would want
> the loop unroller to support the notion of the loop's parallelism in
its
> pre-unrolled version. This probably should happen by propagating
> !alias.scope and !alias metadata. Is there any plan or open patch for
> supporting this?
> >
> > Simplified example:
> >
> > for.body:
> > %0 = load [..]
> >  store %0 [..]
> > br label %for.cond, !llvm.loop !2
> >
> > !1 = distinct !{}
> > !2 = distinct !{!2, !3, !4, !5, !6, !7}
> > !3 = !{!"llvm.loop.parallel_accesses", !1}
> > !4 = !{!"llvm.loop.vectorize.width", i32 1}
> > !5 = !{!"llvm.loop.interleave.count", i32 1}
> > !6 = !{!"llvm.loop.vectorize.enable", i1 true}
> > !7 = !{!"llvm.loop.vectorize.followup_all", !8}
> > !8 = !{!"llvm.loop.unroll.count", i32 2}
> >
> > (unroll by 2) =>
> >
> > for.body:
> > %0 = load [..] !alias.scope !9 !noalias !11
> > store %0 [..] !alias.scope !9 !noalias !11
> > %1 = load [..] !alias.scope !10 !noalias !12
> >  store %1 [..] !alias.scope !10 !noalias !12
> > br label %for.cond, !llvm.loop !2
> >
> > [..]
> >
> > !9 = distinct !{!9, !"iteration0"}
> > !10 = distinct !{!10, !"iteration1"}
> > !11 = !{!10}
> > !12 = !{!9}
> >
> > Thanks, Hendrik
> > _______________________________________________
> > LLVM Developers mailing list
> > llvm-dev at lists.llvm.org
> > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200514/3deb8541/attachment.html>

Actually, I guess Hal's fix won't help us. It seems like we may need a
completely the metadata node llvm.loop.parallel_noalias with noalias
semantics, that then would get propagated in the unroller as originally
stated..?

On Thu, May 14, 2020 at 2:16 PM Hendrik Greving <hgreving at google.com>
wrote:
> This is interesting! So are you saying that loop.parallel_accesses
> strictly loop parallel, and says nothing about aliasing? I see, I guess we
> may have been "abusing" the hint and re-purposed it. But
isn't llvm's
> vectorizer using loop.parallel_accesses to vectorize loops including
> vectorize memory accesses that if you ignore loop-carried dependencies,
> usually means effectively re-ordering the accesses? I guess this still does
> not imply "noalias"? What about icc/gcc's #pragma ivdep?
Again here, it
> means no loop-carried dependencies, yet still doesn't say anything
about
> noalias? Another way indeed would be to propagate noalias data and indeed
> rely on the future fix that Hal mentions above.
>
>
>
> On Thu, May 14, 2020 at 1:33 PM Michael Kruse <llvmdev at
meinersbur.de>
> wrote:
>
>> llvm.loop.parallel_accesses does not imply that these accesses from
>> different iterations are not aliasing. Examples where an access are
>> parallel are that the accesses are atomic or read-only from a specific
>> location.
>>
>> The LoopUnrollPass might deduce that non-atomic stores are necessarily
>> not aliasing (when not using transactional memory), but I don't
think
>> we can do this for all the read accesses. Would that be sufficiently
>> useful?
>>
>> Michael
>>
>>
>> Am Do., 14. Mai 2020 um 15:11 Uhr schrieb Hendrik Greving via llvm-dev
>> <llvm-dev at lists.llvm.org>:
>> >
>> > Hi, in our backend, which is unfortunately not upstreamed, we are
>> relying on llvm.loop.parallel_accesses metadata for certain passes like
>> software pipelining so we can re-order instructions. Ideally, we would
want
>> the loop unroller to support the notion of the loop's parallelism
in its
>> pre-unrolled version. This probably should happen by propagating
>> !alias.scope and !alias metadata. Is there any plan or open patch for
>> supporting this?
>> >
>> > Simplified example:
>> >
>> > for.body:
>> > %0 = load [..]
>> >  store %0 [..]
>> > br label %for.cond, !llvm.loop !2
>> >
>> > !1 = distinct !{}
>> > !2 = distinct !{!2, !3, !4, !5, !6, !7}
>> > !3 = !{!"llvm.loop.parallel_accesses", !1}
>> > !4 = !{!"llvm.loop.vectorize.width", i32 1}
>> > !5 = !{!"llvm.loop.interleave.count", i32 1}
>> > !6 = !{!"llvm.loop.vectorize.enable", i1 true}
>> > !7 = !{!"llvm.loop.vectorize.followup_all", !8}
>> > !8 = !{!"llvm.loop.unroll.count", i32 2}
>> >
>> > (unroll by 2) =>
>> >
>> > for.body:
>> > %0 = load [..] !alias.scope !9 !noalias !11
>> > store %0 [..] !alias.scope !9 !noalias !11
>> > %1 = load [..] !alias.scope !10 !noalias !12
>> >  store %1 [..] !alias.scope !10 !noalias !12
>> > br label %for.cond, !llvm.loop !2
>> >
>> > [..]
>> >
>> > !9 = distinct !{!9, !"iteration0"}
>> > !10 = distinct !{!10, !"iteration1"}
>> > !11 = !{!10}
>> > !12 = !{!9}
>> >
>> > Thanks, Hendrik
>> > _______________________________________________
>> > LLVM Developers mailing list
>> > llvm-dev at lists.llvm.org
>> > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200514/93f1d0f8/attachment.html>

Trivial example:

#pragma clang loop vectorize(assume_safety)
for (int i = 0; i < n; i+=1) {
  (void)A[0];
}

I hope it is obvious that the loop is parallel and can be vectorized,
but A[0] from iteration 0 will alias with A[0] from iteration 1.
Replace `0` by `i*c` where c is a variable that can be 0 at runtime to
make the fact non-obvious to the compiler.

We had discussions about implementing "#pragma ivdep", but it's
semantics are not defined independently of the implementation. Anyway,
even with #pragma omp ivdep, a compiler is not required to vectorize
the loop.

In LLVM, runtime/partial unrolling only takes place after
vectorization, so there is less of an issue there.

Michael


Am Do., 14. Mai 2020 um 16:16 Uhr schrieb Hendrik Greving <hgreving at
google.com>:
>
> This is interesting! So are you saying that loop.parallel_accesses strictly
loop parallel, and says nothing about aliasing? I see, I guess we may have been
"abusing" the hint and re-purposed it. But isn't llvm's
vectorizer using loop.parallel_accesses to vectorize loops including vectorize
memory accesses that if you ignore loop-carried dependencies, usually means
effectively re-ordering the accesses? I guess this still does not imply
"noalias"? What about icc/gcc's #pragma ivdep? Again here, it
means no loop-carried dependencies, yet still doesn't say anything about
noalias? Another way indeed would be to propagate noalias data and indeed rely
on the future fix that Hal mentions above.
>
>
>
> On Thu, May 14, 2020 at 1:33 PM Michael Kruse <llvmdev at
meinersbur.de> wrote:
>>
>> llvm.loop.parallel_accesses does not imply that these accesses from
>> different iterations are not aliasing. Examples where an access are
>> parallel are that the accesses are atomic or read-only from a specific
>> location.
>>
>> The LoopUnrollPass might deduce that non-atomic stores are necessarily
>> not aliasing (when not using transactional memory), but I don't
think
>> we can do this for all the read accesses. Would that be sufficiently
>> useful?
>>
>> Michael
>>
>>
>> Am Do., 14. Mai 2020 um 15:11 Uhr schrieb Hendrik Greving via llvm-dev
>> <llvm-dev at lists.llvm.org>:
>> >
>> > Hi, in our backend, which is unfortunately not upstreamed, we are
relying on llvm.loop.parallel_accesses metadata for certain passes like software
pipelining so we can re-order instructions. Ideally, we would want the loop
unroller to support the notion of the loop's parallelism in its pre-unrolled
version. This probably should happen by propagating !alias.scope and !alias
metadata. Is there any plan or open patch for supporting this?
>> >
>> > Simplified example:
>> >
>> > for.body:
>> > %0 = load [..]
>> >  store %0 [..]
>> > br label %for.cond, !llvm.loop !2
>> >
>> > !1 = distinct !{}
>> > !2 = distinct !{!2, !3, !4, !5, !6, !7}
>> > !3 = !{!"llvm.loop.parallel_accesses", !1}
>> > !4 = !{!"llvm.loop.vectorize.width", i32 1}
>> > !5 = !{!"llvm.loop.interleave.count", i32 1}
>> > !6 = !{!"llvm.loop.vectorize.enable", i1 true}
>> > !7 = !{!"llvm.loop.vectorize.followup_all", !8}
>> > !8 = !{!"llvm.loop.unroll.count", i32 2}
>> >
>> > (unroll by 2) =>
>> >
>> > for.body:
>> > %0 = load [..] !alias.scope !9 !noalias !11
>> > store %0 [..] !alias.scope !9 !noalias !11
>> > %1 = load [..] !alias.scope !10 !noalias !12
>> >  store %1 [..] !alias.scope !10 !noalias !12
>> > br label %for.cond, !llvm.loop !2
>> >
>> > [..]
>> >
>> > !9 = distinct !{!9, !"iteration0"}
>> > !10 = distinct !{!10, !"iteration1"}
>> > !11 = !{!10}
>> > !12 = !{!9}
>> >
>> > Thanks, Hendrik
>> > _______________________________________________
>> > LLVM Developers mailing list
>> > llvm-dev at lists.llvm.org
>> > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

Would you guys be open to supporting a new hint with the right semantics,
like e.g. llvm.loop.noalias_accesses?! I would need to find support in
clang however and the main point of support would be the loop unroller
behaving as stated in the OP.

On Thu, May 14, 2020 at 3:04 PM Michael Kruse <llvmdev at meinersbur.de>
wrote:
> Trivial example:
>
> #pragma clang loop vectorize(assume_safety)
> for (int i = 0; i < n; i+=1) {
>   (void)A[0];
> }
>
> I hope it is obvious that the loop is parallel and can be vectorized,
> but A[0] from iteration 0 will alias with A[0] from iteration 1.
> Replace `0` by `i*c` where c is a variable that can be 0 at runtime to
> make the fact non-obvious to the compiler.
>
> We had discussions about implementing "#pragma ivdep", but
it's
> semantics are not defined independently of the implementation. Anyway,
> even with #pragma omp ivdep, a compiler is not required to vectorize
> the loop.
>
> In LLVM, runtime/partial unrolling only takes place after
> vectorization, so there is less of an issue there.
>
> Michael
>
>
> Am Do., 14. Mai 2020 um 16:16 Uhr schrieb Hendrik Greving <
> hgreving at google.com>:
> >
> > This is interesting! So are you saying that loop.parallel_accesses
> strictly loop parallel, and says nothing about aliasing? I see, I guess we
> may have been "abusing" the hint and re-purposed it. But
isn't llvm's
> vectorizer using loop.parallel_accesses to vectorize loops including
> vectorize memory accesses that if you ignore loop-carried dependencies,
> usually means effectively re-ordering the accesses? I guess this still does
> not imply "noalias"? What about icc/gcc's #pragma ivdep?
Again here, it
> means no loop-carried dependencies, yet still doesn't say anything
about
> noalias? Another way indeed would be to propagate noalias data and indeed
> rely on the future fix that Hal mentions above.
> >
> >
> >
> > On Thu, May 14, 2020 at 1:33 PM Michael Kruse <llvmdev at
meinersbur.de>
> wrote:
> >>
> >> llvm.loop.parallel_accesses does not imply that these accesses
from
> >> different iterations are not aliasing. Examples where an access
are
> >> parallel are that the accesses are atomic or read-only from a
specific
> >> location.
> >>
> >> The LoopUnrollPass might deduce that non-atomic stores are
necessarily
> >> not aliasing (when not using transactional memory), but I
don't think
> >> we can do this for all the read accesses. Would that be
sufficiently
> >> useful?
> >>
> >> Michael
> >>
> >>
> >> Am Do., 14. Mai 2020 um 15:11 Uhr schrieb Hendrik Greving via
llvm-dev
> >> <llvm-dev at lists.llvm.org>:
> >> >
> >> > Hi, in our backend, which is unfortunately not upstreamed, we
are
> relying on llvm.loop.parallel_accesses metadata for certain passes like
> software pipelining so we can re-order instructions. Ideally, we would want
> the loop unroller to support the notion of the loop's parallelism in
its
> pre-unrolled version. This probably should happen by propagating
> !alias.scope and !alias metadata. Is there any plan or open patch for
> supporting this?
> >> >
> >> > Simplified example:
> >> >
> >> > for.body:
> >> > %0 = load [..]
> >> >  store %0 [..]
> >> > br label %for.cond, !llvm.loop !2
> >> >
> >> > !1 = distinct !{}
> >> > !2 = distinct !{!2, !3, !4, !5, !6, !7}
> >> > !3 = !{!"llvm.loop.parallel_accesses", !1}
> >> > !4 = !{!"llvm.loop.vectorize.width", i32 1}
> >> > !5 = !{!"llvm.loop.interleave.count", i32 1}
> >> > !6 = !{!"llvm.loop.vectorize.enable", i1 true}
> >> > !7 = !{!"llvm.loop.vectorize.followup_all", !8}
> >> > !8 = !{!"llvm.loop.unroll.count", i32 2}
> >> >
> >> > (unroll by 2) =>
> >> >
> >> > for.body:
> >> > %0 = load [..] !alias.scope !9 !noalias !11
> >> > store %0 [..] !alias.scope !9 !noalias !11
> >> > %1 = load [..] !alias.scope !10 !noalias !12
> >> >  store %1 [..] !alias.scope !10 !noalias !12
> >> > br label %for.cond, !llvm.loop !2
> >> >
> >> > [..]
> >> >
> >> > !9 = distinct !{!9, !"iteration0"}
> >> > !10 = distinct !{!10, !"iteration1"}
> >> > !11 = !{!10}
> >> > !12 = !{!9}
> >> >
> >> > Thanks, Hendrik
> >> > _______________________________________________
> >> > LLVM Developers mailing list
> >> > llvm-dev at lists.llvm.org
> >> > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200518/75fc0299/attachment.html>