[LLVMdev] RFC: Loop versioning for LICM

[Nema, Ashutosh]

From: Hal Finkel [mailto:hfinkel at anl.gov]
Sent: Friday, March 06, 2015 10:47 AM
To: Nema, Ashutosh
Cc: llvmdev at cs.uiuc.edu
Subject: Re: [LLVMdev] RFC: Loop versioning for LICM

I like to propose a new loop multi versioning optimization for LICM.
For now I kept this for LICM only, but it can be used in multiple places.
The main motivation is to allow optimizations stuck because of memory
alias dependencies. Most of the time when alias analysis is unsure about
memory access and it says may-alias. This un surety from alias analysis restrict
some of the memory based optimizations to proceed further.
We observed some cases with LICM, where things are beyond aliasing.
In cases where alias analysis is unsure we like to use loop versioning as an alternative.

Loop Versioning will creates version of the loop with aggressive alias and the other
with conservative (default) alias. Aggressive alias version of loop will have all the
memory access marked as no-alias. These two version of loop will be preceded by a
memory runtime check. This runtime check consists of bound checks for all unique memory
accessed in loop, and it ensures aliasing of memory. Based on this check result at runtime
any of the loops gets executed, if memory is non aliased then aggressive aliasing loop
gets executed, else when memory is aliased then non aggressive aliased version gets executed.

Hi Ashutosh,

I think this is a really interesting idea, and I'd like to encourage you to continue working on it.
Thanks Hal.
Regarding profitability, I think you'll want to check that you'll be able to hoist/sink a significant number of the memory accesses inside the new "versioned" loop. If a loop has a large number of accesses, and the new loop body only differs by the hosting/sinking of a few, then you're unlikely to see the difference.
Yes it’s a good point, we can add this to profitability.
Some part of this change overlaps with loop access analysis work by Adam Nemet.
Will reuse his changes once gets accepted.
Regards,
Ashutosh

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150310/d4f82b65/attachment.html>