[LLVMdev] convert LLVM IR to another IR without SSA

[Marcel Beemster]

Dear Xiangyang,

May I also point out some recent work on this by Maarten Faddegon:
	“SSA Back-Translation: Faster Results with Edge Splitting and Post Optimization”
	http://www.es.ewi.tudelft.nl/msc-theses/2011-Faddegon.pdf

Faddegon describes an early paper by Cytron about this, which Briggs points out to be of limited generality. Then later Shreedhar made performance improvements on Briggs method, but his algorithm is rather complicated.

Faddegon introduces a reasonably simple extension to Briggs by placing copy statements at a smarter place, and then uses a few simple existing optimization passes to get rid of redundancy. This leads to no performance loss in the removal of phi-nodes. The method is used commercially in ACE’s LLVM-TURBO back-end technology for LLVM (www.ace.nl).

Faddegon’s methods does not solve your problem of limited register resources. For that you would have to use a traditional register allocator.

Best regards,
Marcel

> Hi, John,
> 
> Thanks for your valuable information. reg2mem will introduce too many
> load-store operation and the number of registers is huge. It seems the
> paper you mentioned is what I need.
> 
> Regards
> 
> Xiangyang
> 
> On Fri, Apr 24, 2015 at 7:43 PM, John Criswell <jtcriswel at gmail.com> wrote:
> 
>> Dear Xiangyang,
>> 
>> There is an LLVM pass called reg2mem which does what Diego suggests.  If
>> you're not worried about efficiency, that might work for you.
>> 
>> If you need to do an efficient conversion of code from SSA form to
>> non-SSA form, then you need to read Efficiently Computing Single Static
>> Assignment Form and the Control Dependence Graph by Ron Cytron, Jeane
>> Ferrante, et. al. (I may have gotten the title or authors slightly wrong as
>> I'm recalling this from memory).
>> 
>> Anyway, that paper describes how to generate code from SSA form.  In
>> essence, you need to do what register allocation does: figure out which SSA
>> values in the same def-use chain can live in the same variable (because
>> they don't conflict) and which SSA values must be assigned to different
>> variables (because they are alive at the same time).  If you read the above
>> paper, it should become clear.
>> 
>> Regards,
>> 
>> John Criswell


-- 
Dr. Marcel Beemster, Senior Software Engineer,
ACE Associated Compiler Experts bv,
De Ruyterkade 113, 1011 AB  Amsterdam, The Netherlands.
Tel: +31 20 6646416, Fax: +31 20 6750389,
mailto:marcel at ace.nl, http://www.ace.nl.
--------------------------------------------------------
This e-mail and any files transmitted with it are confidential. Any tech-
nical information contained herein is supplied as-is, and no rights can
be derived therefrom. Unless you are the intended recipient, you should
not read, disclose, copy, or otherwise use the information in this message.
If you have received this message in error, please notify the sender by
reply e-mail immediately and delete the message and all copies thereof.