On May 19, 2009, at 8:15 PM, Nick Lewycky wrote:> Eli Friedman wrote: >> On Tue, May 19, 2009 at 12:30 PM, Nicolas Geoffray >> <nicolas.geoffray at lip6.fr> wrote: >>>> The pi functions can be implemented with copy instructions. >>> Store instructions? >> >> I would assume something more like "select i1 true, <ty> %val, <ty> >> undef". > > %x = phi <ty> [%val, %predbb].FWIW, I strongly recommend going this direction. It'll buy you a lot of free functionality, like replaceAllUsesWith(). --Owen -------------- next part -------------- A non-text attachment was scrubbed... Name: smime.p7s Type: application/pkcs7-signature Size: 2620 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20090519/be073130/attachment.bin>
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
Hi Fernando, Thanks for the very clear explanation. Fernando Magno Quintao Pereira wrote:> 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. >OK. Is it possible to do SSI Transformation --> Array Bounds Optimization --> SSI undo Transformation? Or would that render useless the speed gained with O(1) queries? I think the LLVM philosophy is to favor O(1) queries, and the SSI is probably not increasing the program size that much. Besides, if we can undo, that's the approach I'd recommend. Thanks, Nicolas
On May 20, 2009, at 5:48 AM, Fernando Magno Quintao Pereira wrote:> 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.It also has the benefit of being much easier to maintain across other transformations. An analysis needs to maintain global information mapping program points to whatever internal indexing it uses, so it needs to be informed about all insertions/deletions/CFG changes made in order to remain up to date. In contrast, only those registers directly impacted need to be update to preserve it in the transformation version. Also, I think the transformation version is much easier for client transformations to use. They take an SSI register, prove something true about it, and can just use replaceAllUsesWith to simplify it. A post-pass of constant propagation cleans the whole things up. This should make things like an SSI-based predicate simplifier extremely simple. --Owen -------------- next part -------------- A non-text attachment was scrubbed... Name: smime.p7s Type: application/pkcs7-signature Size: 2620 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20090520/ca61accc/attachment.bin>