[LLVMdev] llvm-java

[Fernando Magno Quintao Pereira]

Hi, Nicolas,

     I have been talking to Andre about this project. Let me add my two 
cents:

> I don't get it. What is the cons then of a simulation?

The tradeoff, IMHO, is as follows:

simulation: it does not add instructions to LLVM IR. Instead, it builds an 
interval representation for each variable. Each interval represents a 
variable in SSI form, and will be associated to one or more constraints, 
like v > 10, or v > a.length. A query will have to find the variable, 
O(1), and then its interval, O(ln #intervals).

transformation: it replaces a variable with new variables that have the 
SSI property. In this case, it must add copies and new phi-functions into 
LLVM IR. Queries are now O(1): just find the variable and recover the 
constraints. The downside is that it increases the program size.

> Why would the analysis change other optimizations?

The transformation may slow down other analysis/optimizations because they 
will have to deal with more instructions. For instance, there will be more 
copies that the coalescer will have to take into consideration.

> OK, so your pass/analysis  creates the stores? Why do you need to
introduce the pi name?

Well, you do not really introduce the pi name. That is an abstraction. In 
the case of simulation, you have a black box that creates intervals for 
each variable that must be converted to SSI. In the case of the 
transformation, you emulate pi-functions with copies (or other 
instructions of similar semantics).

> (Btw, I have no knowledge on SSI/SSA construction theories, so maybe I 
need a higher-level explanation of the problem)

Basically, in (strict) SSA form, you have the property that each 
definition dominates each use of a variable. In SSI, on the other hand, 
you have the property that each use post-dominates its definition. That 
is, any path from the end of the program to the definition of a variable v 
goes across all the uses of v. This requires pi (also called sigma) 
functions, which are the duals of phi-functions. If a phi-function is like 
a multiplexer, a pi-function is like a demux:

(a1:B1, a2:B2) := pi(a)

copies 'a' into a1 if the execution flows to block B1, and copies a into 
a2 otherwise. Compare with a := phi (a1:B1, a2:B2). LLVM has no pi 
function, so it must be simulated with copies. At the beginning of B1, a1 
:= a, and at the beginning of B2, a2 := a.

Fernando