llvm dev - Feb 2013 - [LLVMdev] Parallel Loop Metadata

On 02/08/2013 07:02 PM, Sebastian Pop wrote:
> Nadav Rotem wrote:
>>
>> On Feb 7, 2013, at 10:55 AM, Pekka Jääskeläinen <pekka.jaaskelainen
at tut.fi> wrote:
>>
>>> Hi Nadav,
>>>
>>> On 02/07/2013 07:46 PM, Nadav Rotem wrote:
>>>> Pekka suggested that we add two kind of metadata:
llvm.loop.parallel
>>>> (attached to each loop latch) and llvm.mem.parallel (attached
to each memory
>>>> instruction!).  I think that the motivation for the first
metadata is clear -
>>>> it says that the loop is data-parallel. I can also see us
adding additional
>>>> metadata such as llvm.loop.unrollcnt to allow the users to
control the unroll
>>>> count of loops using pragmas. That's fine. Pekka, can you
think of
>>>> transformations that may need invalidate or take this metadata
into
>>>> consideration ?
>>>
>>> Any pass that introduces new non-parallel memory instructions to
the loop,
>>> because they think the loop is sequential and it's ok to do so.
I do not know
>>> any other such pass than the one pointed out earlier, reg2mem (if
the
>>> variables inside the loop body reuse stack slots). E.g., inlining
>>> should be safe. So should be unrolling an inner loop inside a
parallel loop.
>>>
>>
>> I suggest that we only add the 'llvm.loop.parallel' metadata
and not llvm.mem.parallem.
>
>
> Ok.  A solution similar to Pekka's, using fewer annotations as you
suggested, is
> to reference in 'llvm.loop.parallel' all the datarefs to which the
parallel
> access semantics applies.  When the list of datarefs in
'llvm.loop.parallel'
> differs from the datarefs in the loop, the annotation is deemed invalid.
That sounds elegant and seems to solve the correctness problems.

Cheers,
Tobias

This is something that I can live with. Pekka, if you agree with this approach,
can you write a formal proposal ?

Thanks,
Nadav

On Feb 8, 2013, at 10:20 AM, Tobias Grosser <tobias at grosser.es> wrote:
> On 02/08/2013 07:02 PM, Sebastian Pop wrote:
>> Nadav Rotem wrote:
>>> 
>>> On Feb 7, 2013, at 10:55 AM, Pekka Jääskeläinen
<pekka.jaaskelainen at tut.fi> wrote:
>>> 
>>>> Hi Nadav,
>>>> 
>>>> On 02/07/2013 07:46 PM, Nadav Rotem wrote:
>>>>> Pekka suggested that we add two kind of metadata:
llvm.loop.parallel
>>>>> (attached to each loop latch) and llvm.mem.parallel
(attached to each memory
>>>>> instruction!).  I think that the motivation for the first
metadata is clear -
>>>>> it says that the loop is data-parallel. I can also see us
adding additional
>>>>> metadata such as llvm.loop.unrollcnt to allow the users to
control the unroll
>>>>> count of loops using pragmas. That's fine. Pekka, can
you think of
>>>>> transformations that may need invalidate or take this
metadata into
>>>>> consideration ?
>>>> 
>>>> Any pass that introduces new non-parallel memory instructions
to the loop,
>>>> because they think the loop is sequential and it's ok to do
so. I do not know
>>>> any other such pass than the one pointed out earlier, reg2mem
(if the
>>>> variables inside the loop body reuse stack slots). E.g.,
inlining
>>>> should be safe. So should be unrolling an inner loop inside a
parallel loop.
>>>> 
>>> 
>>> I suggest that we only add the 'llvm.loop.parallel'
metadata and not llvm.mem.parallem.
>> 
>> 
>> Ok.  A solution similar to Pekka's, using fewer annotations as you
suggested, is
>> to reference in 'llvm.loop.parallel' all the datarefs to which
the parallel
>> access semantics applies.  When the list of datarefs in
'llvm.loop.parallel'
>> differs from the datarefs in the loop, the annotation is deemed
invalid.
> 
> That sounds elegant and seems to solve the correctness problems.
> 
> Cheers,
> Tobias

On 02/08/2013 08:20 PM, Tobias Grosser wrote:
> That sounds elegant and seems to solve the correctness problems.
There is no big difference here except that the memory instructions
would not need the metadata.

I do not think the abundance of metadata is really the main problem, but
what to do with passes that do not know about parallel loops. How to minimize 
the changes needed to make the most relevant passes retain the information,
and more importantly, how to avoid code breakage if they are unaware of
its meaning.

Also, I tried something like this when I tried to find a nice way to couple
the memory and the loop metadata. It seems not possible to directly refer to
an Instruction from MDNode, or is it? I got crashes when serializing the
bitcode with MDNodes pointing to Instructions and thought that it's not
meant
to work that way around.

Thus, I created the loop identifier metadata "anchor" to which the
both
metadata types refer.

Even if it was possible, retaining that information across inlining etc. means
one has to update those Instruction references in the metadata to the new
matching ones in the inlined location, etc. The maintenance burden of the data
in several passes, which I thought was the actual concern of Nadav, gets AFAIU
even harder. E.g., if you remove memory instructions (e.g. DCE) you get
dangling pointers in the metadata or a null there which renders the parallel 
info invalid (and might even cause crashes?), which doesn't happen in the
current state of the patch.

All in all, if the number of metadata is what pains the most, this
is an improvement. Otherwise, I see it more fragile, and it's also uncertain
if
it's possible to implement it.

IMHO, the best alternative presented so far is to have both metadata types
and potentially exploit the mem.parallel_loop_access MD even if there were
non-annotated instructions in the loop to *help* the dependency analysis.
isParallel() would stay as is now in the patch, it can be used as a short cut
check for a loop of which accesses all have the metadata (to skip the whole
dependency checking).

-- 
--Pekka

On Feb 8, 2013, at 12:28 PM, Pekka Jääskeläinen <pekka.jaaskelainen at
tut.fi> wrote:
> On 02/08/2013 08:20 PM, Tobias Grosser wrote:
>> That sounds elegant and seems to solve the correctness problems.
> 
> There is no big difference here except that the memory instructions
> would not need the metadata.
> 
> I do not think the abundance of metadata is really the main problem, but
> what to do with passes that do not know about parallel loops. How to
minimize the changes needed to make the most relevant passes retain the
information,
> and more importantly, how to avoid code breakage if they are unaware of
> its meaning.
> 
> Also, I tried something like this when I tried to find a nice way to couple
> the memory and the loop metadata. It seems not possible to directly refer
to
> an Instruction from MDNode, or is it? I got crashes when serializing the
> bitcode with MDNodes pointing to Instructions and thought that it's not
meant
> to work that way around.
I think you can refer to the memory address values from within your
function-local metadata.
> Thus, I created the loop identifier metadata "anchor" to which
the both
> metadata types refer.
> Even if it was possible, retaining that information across inlining etc.
means
> one has to update those Instruction references in the metadata to the new
> matching ones in the inlined location, etc. The maintenance burden of the
data
> in several passes, which I thought was the actual concern of Nadav, gets
AFAIU
> even harder. E.g., if you remove memory instructions (e.g. DCE) you get
> dangling pointers in the metadata or a null there which renders the
parallel info invalid (and might even cause crashes?), which doesn't happen
in the
> current state of the patch.
How is this not a problem for !tbaa?

-Andy
> All in all, if the number of metadata is what pains the most, this
> is an improvement. Otherwise, I see it more fragile, and it's also
uncertain if
> it's possible to implement it.
> 
> IMHO, the best alternative presented so far is to have both metadata types
> and potentially exploit the mem.parallel_loop_access MD even if there were
> non-annotated instructions in the loop to *help* the dependency analysis.
> isParallel() would stay as is now in the patch, it can be used as a short
cut
> check for a loop of which accesses all have the metadata (to skip the whole
> dependency checking).
> 
> -- 
> --Pekka
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev