Fernando Magno Quintao Pereira
fernando at CS.UCLA.EDU
Wed May 20 05:48:56 PDT 2009
I have been talking to Andre about this project. Let me add my two
> 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.
More information about the llvm-dev