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
Dear All, Perhaps a related issue is whether SSI form is valuable for other transformations or analysis passes. If it is, then it might be worth building general SSA->SSI and SSI->SSA transforms so that any LLVM pass wishing to have the code in SSI form can do so. -- John T. Nicolas Geoffray wrote:> [snip] > > 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 > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >
It is certainly useful in other optimizations: 1) Type check elimination in dynamically typed languages: if you know that i is int, then you don't have to check its type before performing integer operations on it. 2) Constant propagation: if (!i) then x = i else x = 13 => if (i) then x = 0 else x = 13 3) Bitwidth analysis: if (x < 128) then ... => if (x < 128) then "x has at most 7 bits" 4) Dead code elimination: if (x > 10) then if (x < 9) then... else S => if (x <= 10) then S etc That is why we need a modular design: a client pass gives some variables to the SSI module, which will convert those variables to SSI. Fernando> Dear All, > > Perhaps a related issue is whether SSI form is valuable for other > transformations or analysis passes. If it is, then it might be worth > building general SSA->SSI and SSI->SSA transforms so that any LLVM pass > wishing to have the code in SSI form can do so. > > -- John T. > > Nicolas Geoffray wrote: >> [snip] >> >> 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 >> >> >> _______________________________________________ >> LLVM Developers mailing list >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >> > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >
On May 20, 2009, at 6:51 AM, Nicolas Geoffray wrote:> 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?Undoing SSI translation is just constant propagation, if you've represented the pi nodes with single-input phis/copies. --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/092bea36/attachment.bin>