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

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200514/a9bb64ca/attachment.html>

Hi, Hendrik,

A couple of thoughts:

 1. This might be related (but, perhaps, not in the way you'd prefer):
https://bugs.llvm.org/show_bug.cgi?id=39282
 2. We're scheduling a call to discuss further improvements in this area,
and if you might be able to join, please fill out the Doodle poll:
https://doodle.com/poll/evhwr2eyfvcf8ib3

 -Hal

Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

________________________________
From: llvm-dev <llvm-dev-bounces at lists.llvm.org> on behalf of Hendrik
Greving via llvm-dev <llvm-dev at lists.llvm.org>
Sent: Thursday, May 14, 2020 3:11 PM
To: llvm-dev at lists.llvm.org <llvm-dev at lists.llvm.org>
Cc: Marcello Maggioni <maggioni at google.com>
Subject: [llvm-dev] LLVM's loop unroller & llvm.loop.parallel_accesses

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200514/2bab9b25/attachment.html>

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

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>