convert LLVM IR to another IR without SSA

Project Infrastructure LLVM Dev List Archives
1

Hi,

I want to convert LLVM IR to another type of IR, which has no SSA form. So the most important thing I need to handle is Phi node and register allocation because another type of IR has a limitation of virtual register number. The first thing I can think about is to learn how LLVM Backend works because LLVM Backend handles these things. But I’m not familiar with Backend. After reading some source code and online tutorials, I think a Backend is too much for my purpose. I really appreciate that if someone can give me hints.

Thanks

Xiangyang

2

The easiest way to think about PHI nodes is to consider them copies on CFG
edges. If you do the naive translation of inserting a copy instruction on
the corresponding edge for each PHI argument, you'll get a rough
approximation for the corresponding normal form.

This is, of course, very inefficient, but it's the main idea.

If you can look at GCC's source code, take a look at the algorithm in file
gcc/tree-outof-ssa.c. That implements an SSA->Normal transformation. I'm
not really sure where in the LLVM's backend this is done.

Diego.

3

Hi, Diego,

Thanks for your quick reply. Inserting a copy instruction may not work here because I have a limitation of virtual register number. I need to assign registers with ssa form to registers without ssa form. I will look the source code you point out.

Thanks

Xiangyang

4

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

5

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

6

Yes, you’ll either need to do what is in the paper or do what the code generator does (as Diego suggested). If you look at the paper, you can probably skip to the part in the end in which they discuss converting code out of SSA form. Regards, John Criswell