[LLVMdev] Speculative Loop Parallelization on LLVM IR

Devang Patel devang.patel at gmail.com
Mon Jun 21 11:29:12 PDT 2010


On Sun, Jun 20, 2010 at 10:12 PM, Javed Absar <javed.absar at gmail.com> wrote:
> Hi Tobias:
>
> Thanks for replying . So if I understand correctly,  in LLVM currently, the
> Polyhedral model is being built ( LLVM IR -------> Poly Model ---------->
> LLVM IR ).
> This is for compile-time optimizations of loop-nests [e.g.
> loop-transformations to expose parallelism or improve locality etc]. Yes,
> thats great for optimizing loop-nests.
>
> As an additional, since the real value of LLVM to me is run-time
> optimizations possibilities, some loop-nest optimizations "needs" to be done
> at run-time.
> I say "needs" because many loops have unresolvable data-dependencies at
> compile-time
> [for example
>
> FOR i = 1 to N
> A[ B[i]  ]  = A [ i ] + func (....)
> END
>
> Can the iterations of this loop be run in parallel?
> ]
>
> There are two approaches for with the above kind of problems. One is
> inspector/executor, other is speculation.
> To keep the story short - basically, you run the loop-iterations  in
> parallel and verify in the end if data-dependencies were violated. If yes,
> you rewind and run the loop sequentially.
> If for that particular case there was no data-dependencies violated, you
> have gained in execution time [yes, there is cost involved in verifying and
> nett gain is not always +ve ].
>
> OK, so whats my point? To be able to do at least some loop-transformations
> at run-time to expose parallelism etc, perhaps some kind of LLVM IR --> Poly
> ---> LLVM IR
> support at run-time may be required. Definitely a scaled down version, since
> polyhedral transformations need a lot of processing in my opinion.
> So if i understand, we are not there yet .... and may be i can come back
> with some proposal/ideas and cross-check it with you guys.

Do you really need to do transformations at run time ?

http://www.springerlink.com/content/ly5t6f8fyyr28m8y/

:)
-
Devang




More information about the llvm-dev mailing list