Incremental SSA update

Hi,

does LLVM have a mechanism to automatically update SSA form, e.g. after
insertion of additional definitions of a variable? This would
recursively traverse the dominance tree of all uses of the definition
backwards and insert phi-functions where ever they are needed.

http://portal.acm.org/citation.cfm?id=277656&dl=GUIDE, (Paragraph 4.5)
provides an algorithm for such an incremental SSA update which I would
implement if nothing similar(ly efficient) already exists.

By now I have implemented both a Control Dependence Analysis and an
If-Conversion pass. Both passes are not largely tested yet and probably
will not match any desired quality of code.
Yet I would like to contribute them at some point, but I am unsure about
requirements etc. and would appreciate some hints on how to proceed :).

Regards,
Ralf

Ralf Karrenberg wrote:

Hi,

does LLVM have a mechanism to automatically update SSA form, e.g. after
insertion of additional definitions of a variable? This would
recursively traverse the dominance tree of all uses of the definition
backwards and insert phi-functions where ever they are needed.
  

I'm not sure what you mean. LLVM virual registers are *always* in SSA
form. I don't think it's possible to generate non-SSA code (although it
is possible to generate ill-formed IR, such as a def that does not
dominate all of its uses). For example, if you create a new LLVM
instruction in your transform, then it will have a unique name and be a
unique definition. There is no need to convert it into SSA form because
it already is in SSA form.

Perhaps what you are asking is whether an alloca which is used to create
a variable can be promoted into an SSA virtual register. The answer is
yes, and there is already a pass (mem2reg) that will do this for you.
Front-end often create variables as stack-allocated memory objects
(because stack memory can be loaded from/stored to multiple times) and
then let mem2reg promote the alloca'ed memory into SSA virtual registers
if possible. That's the only non-SSA to SSA conversion that happens in
LLVM, as far as I know.

http://portal.acm.org/citation.cfm?id=277656&dl=GUIDE, (Paragraph 4.5)
provides an algorithm for such an incremental SSA update which I would
implement if nothing similar(ly efficient) already exists.

By now I have implemented both a Control Dependence Analysis and an
If-Conversion pass. Both passes are not largely tested yet and probably
will not match any desired quality of code.
Yet I would like to contribute them at some point, but I am unsure about
requirements etc. and would appreciate some hints on how to proceed :).
  

Very cool.

Code contribution policies are at
http://llvm.org/docs/DeveloperPolicy.html. If I understand it
correctly, you submit a patch for review either to llvmdev or the
llvm-commits list, someone with commit access reviews it, you iterate
through requested code changes as necessary, and then they commit.
You'll also need at least one testcase to show that your code works.

-- John T.