[LLVMdev] parallel loop metadata question

Fri May 23 04:44:50 PDT 2014

OK,

I updated the text to LangRef in r209507 after some
editing.

On 05/11/2014 12:36 PM, Pekka Jääskeläinen wrote:
> Hi,
>
> This looks good to me except that the first sentence
> could already include "that refer to the same loop" or
> similar.
>
> I could imagine that e.g. loop invariant code motion,
> if applied to a parallel loop could hoist code out of
> inner loops to outer (parallel) loops. Then the outer
> loop contains parallel_loop_access instructions referring to
> the inner loop, making the outer loop non-trivially parallel.
>
> But these are probably rare cases as, at least in pocl, basic
> optimizations have already been executed before the work-group
> function generation where the parallel work-item loops are created.
>
> On 05/10/2014 12:08 AM, Humphreys, Jonathan wrote:
>> I propose that we change the first paragraph of
>> http://llvm.org/docs/LangRef.html#llvm-mem-parallel-loop-access-metadata:
>>
>> ---
>> For a loop to be parallel, in addition to using the llvm.loop metadata to
>> mark the loop latch branch instruction, also all of the memory accessing
>> instructions in the loop body need to be marked with the
>> llvm.mem.parallel_loop_access metadata. If there is at least one memory
>> accessing instruction not marked with the metadata, the loop must be
>> considered a sequential loop. This causes parallel loops to be converted to
>> sequential loops due to optimization passes that are unaware of the parallel
>> semantics and that insert new memory instructions to the loop body.
>> ---
>>
>> To be:
>>
>> ---
>> The llvm.mem.parallel_loop_access metadata attaches to instructions and
>> denotes that no loop carried memory dependence exist between it and other
>> such denoted instructions.  The llvm.mem.parallel_loop_access metadata
>> refers to a loop identifier, or metadata containing a list of loop
>> identifiers for nested loops - these are the loops to which the metadata
>> applies.  Precisely, given two instructions m1 and m2 that both have
>> llvm.mem.parallel_loop_access metadata, with L1 and L2 being the set of
>> loops associated with that metadata, respectively, then there is no loop
>> carried dependence between m1 and m2 for loops in both L1 and L2.
>>
>> Trivially, if all memory accessing instructions in a loop have
>> llvm.mem.parallel_loop_access metadata that refers to that loop, then the
>> loop has no loop carried memory dependence and is considered to be a
>> parallel loop.  Note that if not all memory access instructions have this
>> metadata referring to this loop, then the loop is not trivially parallel -
>> additional memory dependence analysis is required to make that
>> determination.  As a fail safe mechanism, this causes loops that were
>> originally parallel to be considered sequential if optimization passes that
>> are unaware of the parallel semantics insert new memory instructions into
>> the loop body.
>> ---
>>
>> Please let me know your feedback.
>>
>> As far as taking advantage of the more precise semantics, I've dropped the
>> priority of this work because I'm not seeing cases where we insert memory
>> instruction.  I'm wondering if others have any anecdotal evidence of how
>> often we 'loose' the fact that a loop is parallel because of inserting
>> memory instructions during optimizations.
>>
>> Thanks
>> Jon
>>
>>
>> -----Original Message-----
>> From: Hal Finkel [mailto:hfinkel at anl.gov]
>> Sent: Monday, May 05, 2014 5:14 PM
>> To: Humphreys, Jonathan
>> Cc: Pekka Jääskeläinen; llvmdev at cs.uiuc.edu; Tobias Grosser
>> Subject: Re: [LLVMdev] parallel loop metadata question
>>
>> ----- Original Message -----
>>> From: "Jonathan Humphreys" <j-humphreys at ti.com>
>>> To: "Hal Finkel" <hfinkel at anl.gov>, "Tobias Grosser"
>>> <tobias at grosser.es>
>>> Cc: "Pekka Jääskeläinen" <pekka.jaaskelainen at tut.fi>,
>>> llvmdev at cs.uiuc.edu
>>> Sent: Monday, May 5, 2014 5:09:42 PM
>>> Subject: RE: [LLVMdev] parallel loop metadata question
>>>
>>> Will do.  I will write something up.
>>>
>>> Hal, your concern below isn't so much with the proposed semantics but
>>> rather with the use - that optimizations must respect the loop for
>>> which the metadata applies, correct?
>>
>> Yes, sounds right. Nevertheless, I would recommend putting such a cautionary
>> note into the documentation itself just to make explicit an issue which
>> might otherwise be overlooked.
>>
>>   -Hal
>>
>>>
>>> Thanks
>>> Jon
>>>
>>> -----Original Message-----
>>> From: Hal Finkel [mailto:hfinkel at anl.gov]
>>> Sent: Monday, May 05, 2014 4:00 AM
>>> To: Tobias Grosser
>>> Cc: Pekka Jääskeläinen; Humphreys, Jonathan; llvmdev at cs.uiuc.edu
>>> Subject: Re: [LLVMdev] parallel loop metadata question
>>>
>>> ----- Original Message -----
>>>> From: "Tobias Grosser" <tobias at grosser.es>
>>>> To: "Pekka Jääskeläinen" <pekka.jaaskelainen at tut.fi>, "Jonathan
>>>> Humphreys" <j-humphreys at ti.com>, llvmdev at cs.uiuc.edu
>>>> Sent: Monday, May 5, 2014 3:36:07 AM
>>>> Subject: Re: [LLVMdev] parallel loop metadata question
>>>>
>>>> On 05/05/2014 10:14, Pekka Jääskeläinen wrote:
>>>>> On 05/02/2014 07:22 PM, Humphreys, Jonathan wrote:
>>>>>> Thanks for the link.  I understand your concern of caution with
>>>>>> metadata.
>>>>>> I cannot, though, imagine how the dependence relation
>>>>>> (independence)
>>>>>> of two
>>>>>> memory references can be affected by a third memory reference.
>>>>>>   If
>>>>>> two references are independent across loop iterations, then they
>>>>>> are independent, and any other load or store cannot change that.
>>>>>>   Right?
>>>>>
>>>>> Yes, it makes sense. I'm mostly concerned about accesses to stack,
>>>>> but even those at this point should remain independent. Otherwise
>>>>> even the current semantics might produce broken code with parallel
>>>>> stack accesses.
>>>>>
>>>>> However, as this is such a major semantics change to the original
>>>>> one, I'd like to hear more opinions on it. I suggest you create a
>>>>> (documentation)
>>>>> patch where the new semantics is articulated and request comments
>>>>> for it at the LLVM-commits list.
>>>>
>>>> I agree with both. I think the extension is very reasonable and I
>>>> also do not see a reason why this interpretation should cause
>>>> troubles.
>>>> However, to get it right it would be good to get this throughly
>>>> reviewed.
>>>
>>> I agree, I think this sounds reasonable. You'll certainly need to be
>>> careful, however, that the associated instruction has not been
>>> hoisted/sunk out of the associated loops. Even if the load is one that
>>> can be speculated, that does not mean that there was not a control
>>> dependence on the independence information itself.
>>>
>>>   -Hal
>>>
>>>>
>>>> Tobias
>>>> _______________________________________________
>>>> LLVM Developers mailing list
>>>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>>
>>>
>>> --
>>> Hal Finkel
>>> Assistant Computational Scientist
>>> Leadership Computing Facility
>>> Argonne National Laboratory
>>>
>>
>> --
>> Hal Finkel
>> Assistant Computational Scientist
>> Leadership Computing Facility
>> Argonne National Laboratory
>>
>
>

-- 
Pekka