[LLVMdev] Speculative Loop Parallelization on LLVM IR

[Tobias Grosser]

On 06/21/10 07:12, Javed Absar 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.

Yes you are right. I also believe it is a very interesting area of 
research to check if/howmuch optimizations can be done at runtime.

This is one of the reasons I built polly as I am planning to use its JIT 
facilities explore the possible optimizations at runtime.

Please let me now about any ideas you have in this direction, as I am 
highly interested in these topics.

Cheers
Tobi