llvm dev - Oct 2014 - [LLVMdev] SSA for memory objects

Hello,

I'm looking to learn more about what is available for memory  
versioning or inducing some kind of SSA for memory objects. I found  
this page:

   http://llvm.org/docs/tutorial/OCamlLangImpl7.html#memory-in-llvm

Which says: "[LLVM] does not require (or permit) memory objects to be  
in SSA form.... In LLVM, instead of encoding dataflow analysis of  
memory into the LLVM IR, it is handled with Analysis Passes which are  
computed on demand."

However, there is no mention of which analyses provide this. I also  
haven't been able to turn up much in the way of documentation or  
examples, so I'm grateful for any additional pointers.

Thanks,

Tyler

Dear Tyler,

First, you *could* represent memory objects in SSA form now that LLVM 
supports vector and structure-based SSA virtual registers. However, 
there is no LLVM pass that will take heap-based memory objects and 
convert them into SSA form.  Moreover, the code generators are not 
expecting the compiler to put heap variables into SSA form, and so if 
you can generate native code from a program that has been transformed in 
this way, it will probably not run very fast.

Second, regarding analysis passes, I'm not sure that LLVM really has 
passes for doing data-flow analysis on values in memory.  The best I can 
think of is the DSA points-to analysis; this lives in the poolalloc 
source code and isn't used by LLVM itself.  It has been used by a few 
research projects to do data-flow analysis on values traveling through 
the heap.

There are other analyses within LLVM that may reason about heap objects 
using the AliasAnalysis interface (the passes to remove redundant loads 
and stores comes to mind), but I don't think they do proper Kam-Ullman 
data-flow analysis on data traveling *through* heap objects (but someone 
can correct me if I'm wrong on that).

Regards,

John Criswell

On 10/19/14, 11:32 AM, Tyler Denniston wrote:
> Hello,
>
> I'm looking to learn more about what is available for memory 
> versioning or inducing some kind of SSA for memory objects. I found 
> this page:
>
>   http://llvm.org/docs/tutorial/OCamlLangImpl7.html#memory-in-llvm
>
> Which says: "[LLVM] does not require (or permit) memory objects to be 
> in SSA form.... In LLVM, instead of encoding dataflow analysis of 
> memory into the LLVM IR, it is handled with Analysis Passes which are 
> computed on demand."
>
> However, there is no mention of which analyses provide this. I also 
> haven't been able to turn up much in the way of documentation or 
> examples, so I'm grateful for any additional pointers.
>
> Thanks,
>
> Tyler
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

-- 
John Criswell
Assistant Professor
Department of Computer Science, University of Rochester
http://www.cs.rochester.edu/u/criswell

Hi John,

Thanks for your reply.

Quoting John Criswell <jtcriswel at gmail.com>:
> First, you *could* represent memory objects in SSA form now that  
> LLVM supports vector and structure-based SSA virtual registers.
Could you elaborate a bit more on what this means? The performance  
concern isn't a big issue for me at this point, as I'm currently just  
learning more about data flow analysis on memory objects (i.e. how  
tractable it is. SSA for memory was just the first idea I had).
> Second, regarding analysis passes, I'm not sure that LLVM really has  
> passes for doing data-flow analysis on values in memory.  The best I  
> can think of is the DSA points-to analysis; this lives in the  
> poolalloc source code and isn't used by LLVM itself.  It has been  
> used by a few research projects to do data-flow analysis on values  
> traveling through the heap.
I'll have a look at DSA. In the meantime, do you happen to have any  
pointers to those research projects you mentioned?
> There are other analyses within LLVM that may reason about heap  
> objects using the AliasAnalysis interface (the passes to remove  
> redundant loads and stores comes to mind), but I don't think they do  
> proper Kam-Ullman data-flow analysis on data traveling *through*  
> heap objects (but someone can correct me if I'm wrong on that).
My last resort was going to be rolling my own analysis using AA, but I  
first wanted to see what work has been done in this area so I can  
avoid reinventing the wheel.

Thanks,

Tyler
> On 10/19/14, 11:32 AM, Tyler Denniston wrote:
>> Hello,
>>
>> I'm looking to learn more about what is available for memory  
>> versioning or inducing some kind of SSA for memory objects. I found  
>> this page:
>>
>>  http://llvm.org/docs/tutorial/OCamlLangImpl7.html#memory-in-llvm
>>
>> Which says: "[LLVM] does not require (or permit) memory objects to
>> be in SSA form.... In LLVM, instead of encoding dataflow analysis  
>> of memory into the LLVM IR, it is handled with Analysis Passes  
>> which are computed on demand."
>>
>> However, there is no mention of which analyses provide this. I also  
>> haven't been able to turn up much in the way of documentation or  
>> examples, so I'm grateful for any additional pointers.
>>
>> Thanks,
>>
>> Tyler