llvm dev - May 2014 - [LLVMdev] parallel loop metadata question

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?

Jon

-----Original Message-----
From: Pekka Jääskeläinen [mailto:pekka.jaaskelainen at tut.fi] 
Sent: Friday, May 02, 2014 3:37 AM
To: Humphreys, Jonathan; llvmdev at cs.uiuc.edu
Cc: Daniel Berlin
Subject: Re: [LLVMdev] parallel loop metadata question

On 05/02/2014 01:49 AM, Humphreys, Jonathan wrote:
> Here's where I have a question:
>
> - if not all memory instructions in a loop have this metadata, can the 
> compiler still infer that the instructions having this metadata do not 
> have any loop carried dependencies with any other instruction also 
> having this metadata (for the common loops referenced by the metadata)?
>
> If so, it would be nice if we documented the actual meaning of 
> llvm.mem.parallel_loop_access as such.  And the conclusion that a loop 
> is 'parallel' if all its memory instructions have this metadata
would
> be a natural consequence of that meaning.
>
> This will allow us to potentially vectorize and/or software pipeline 
> large portions of loops even when some transformation introduces a 
> memory operation whose dependence effects are unknown.
This would be certainly useful.

We discussed a similar issue when the original parallel loop MD was sketched
last year:

http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-February/059256.html

In this case the question is whether we can be sure the (new) accesses inserted
between the parallel annotated accesses cannot not ruin the parallel
(independence) semantics between the annotated ones.

While I cannot give you a breaking example/optimization immediately, I'm not
confident there isn't one. The problem is that we need to be extra careful
to not break the metadata rules; if an optimization does not understand a
metadata, it should not be able to accidentally break any additional semantics
implied by it.

--
Pekka

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.

-- 
Pekka

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.

Tobias