[LLVMdev] Pointer Context Metadata

[Pekka Jääskeläinen]

Hi,

> On 02/19/2013 05:51 PM, Hal Finkel wrote:
>> Understood. If you have some time, it seems that there are several
>> sub-tasks:
>>
>> - Update the language reference

On 02/19/2013 06:25 PM, Pekka Jääskeläinen wrote:
> Document the additional optional iteration id argument to
> llvm.mem.parallel_loop_access? I'll do this.

I finally found some time to think about this. The current idea to mark the
unrolled parallel iterations is the following.

In the current llvm.mem.parallel_loop_access metadata format the accesses
are marked like this (a store in a 2-level nested loop):

...
store i32 %0, i32* %arrayidx4, align 4, !llvm.mem.parallel_loop_access !0
...

!0 = metadata !{ metadata !1, metadata !2 } ; a list of parallel loop identifiers
!1 = metadata !{ metadata !1 } ; an identifier for the inner parallel loop
!2 = metadata !{ metadata !2 } ; an identifier for the outer parallel loop

The idea was to add an optional extra iteration identifier to the MD of the
parallel_loop_access node. In essence, we want to identify the loop and
the unrolled iteration of each access to help (at least) the alias analysis.

Say, we unroll the inner loop once:

...
store i32 %0, i32* %arrayidx4, align 4, !llvm.mem.parallel_loop_access !0
...
store i32 %0, i32* %arrayidx4, align 4, !llvm.mem.parallel_loop_access !3
...

!0 = metadata !{ metadata !{ metadata !1, i64 0 }, metadata !2 }
!1 = metadata !{ metadata !1 }  ; loop id inner
!2 = metadata !{ metadata !2 }  ; loop id outer
!3 = metadata !{ metadata !{ metadata !1, i64 1 }, metadata !2 }

The llvm.loop.parallel MD of the branch will point to !1 and !2 directly
because the unrolled iterations should not (still) alias with accesses
from any (rolled) iteration. The outer loop iteration !2 has an
implicit "iteration id" of 0.

Or, should we use the "unique self-referring metadata node" trick also here
to mark the iteration identifiers? The integer ids there are kind of
arbitrary, and the unrollers need to find out an unique int if they decide to
unroll more.

Could the following work more robustly?

!0 = metadata !{ metadata !{ metadata !1, metadata !0 }, metadata !2 }
!1 = metadata !{ metadata !1 }  ; loop id inner
!2 = metadata !{ metadata !2 }  ; loop id outer
!3 = metadata !{ metadata !{ metadata !1, metadata !3 }, metadata !2 }

Here the self-reference back to the "iteration" metadata (!0 and
!3) would force the uniqueness of an iteration MD. If we now unroll once
the outer loop too we get to:

; for the inner loop iterations:
!0 = metadata !{ metadata !{ metadata !1, metadata !0 }, metadata !2 }
!1 = metadata !{ metadata !1 }  ; loop id inner
!2 = metadata !{ metadata !2 }  ; loop id outer
!3 = metadata !{ metadata !{ metadata !1, metadata !3 }, metadata !2 }

; for the outer loop iterations:
!4 = metadata !{
   metadata !{ metadata !1, metadata !4 },
   metadata !{ metadata !2, metadata !4 } }

!7 = metadata !{
   metadata !{ metadata !1, metadata !3 },
   metadata !{ metadata !2, metadata !7 } }

The MD should still fulfill the requirement of not needing to know about the 
metadata: if the unroller unknowingly copies the iteration MD, we just won't
get the AA benefits, but nothing should break. The new unrolled instructions
would look like a single parallel loop iteration which can alias with each
other. If it doesn't copy the MD, the loop loses the "parallel property".

The llvm.loop.parallel metadata would still work as previously: it points only 
to the loop id metadata nodes which the iteration id nodes also point to.

Any comments/thoughts/better ideas before I move forward with this? Next
I plan to emit the MD from pocl and add an alias analyzer to LLVM that
understands it.

Thanks,
-- 
Pekka