[LLVMdev] Parallel Loop Metadata

[Pekka Jääskeläinen]

On 02/08/2013 04:26 PM, Daniel Berlin wrote:
> I'd love to see example cases where the pair analysis is the
> difficulty, rather than the access analysis of any single memory piece
> being the difficulty.

I'm not completely sure what you mean, but is there really a difference
between doing "pair analysis" across multiple iterations of the same
instruction than doing it with any other instruction?

Say, a loop with memory operations Aw, Br, Cw (w=write, r=read).
This is unrolled just for the sake of the example. The same applies to
widening the instructions in a loop vectorizer, similar dependency
analysis is needed.

i1: Aw  Br  Cw
i2: Aw' Br' Cw'

To do a legal code motion across the two iterations in such a way that
you move e.g., Aw' before Br, in parallel with Aw (e.g. to pack them to a
vector instruction or statically schedule in a VLIW) requires you to know
that none of Aw, Br nor Cw access the same location of Aw'.

If we know these are parallel loop accesses we know that Aw' doesn't
alias with any of Aw, Br or Cw, thus we can perform the code motion
with a peaceful mind, and execute Aw and Aw' in parallel e.g. in a
vector instruction.

If we get some non-parallel-loop-annotated mem instructions injected in
the loop, it's up to the analyzer again to prove the code motion is legal.

For example, the reg2mem case (where Sw is produced by it and not
marked with the llvm.mem.parallel_loop_access MD).

i1: Aw,  Sw,  Br,  Cw
i2: Aw', Sw', Br', Cw'

Cannot do the same code motion here unless the analyzer can prove Aw' and
Sw do not alias.

-- 
Pekka