llvm dev - Mar 2008 - [LLVMdev] What is "strong phi elimination"

Can you describe quickly (or point to references for the inclined)  
what this pass will do and what other stuff it might enable for LLVM?  
I'm just curious.

--
Christopher Lamb



-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20080324/46829334/attachment.html>

Ask an ye shall receive.  From the .cpp file:

// 
= 
= 
=---------------------------------------------------------------------- 
===//
//
// This pass eliminates machine instruction PHI nodes by inserting copy
// instructions, using an intelligent copy-folding technique based on
// dominator information.  This is technique is derived from:
//
//    Budimlic, et al. Fast copy coalescing and live-range  
identification.
//    In Proceedings of the ACM SIGPLAN 2002 Conference on Programming  
Language
//    Design and Implementation (Berlin, Germany, June 17 - 19, 2002).
//    PLDI '02. ACM, New York, NY, 25-32.
//    DOI= http://doi.acm.org/10.1145/512529.512534
//
// 
= 
= 
=---------------------------------------------------------------------- 
===//

Basically, it's PHI elimination with built-in coallescing.

--Owen

On Mar 24, 2008, at 11:17 PM, Christopher Lamb wrote:
> Can you describe quickly (or point to references for the inclined)  
> what this pass will do and what other stuff it might enable for  
> LLVM? I'm just curious.
>
> --
> Christopher Lamb
>
>
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2555 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20080324/de4a380b/attachment.bin>

On Mar 24, 2008, at 9:22 PM, Owen Anderson wrote:
> Ask an ye shall receive.  From the .cpp file:
> Basically, it's PHI elimination with built-in coallescing.
You mean "coalescing" (tips hat to Gabor :).

Another way to look at it is that it is the "normal" SSA phi  
elimination algorithm, which is normally implemented in terms of an  
interference graph, without the IG.  Not using an IG saves having to  
build an awful N^2 data structure, which is possible through clever  
use of SSA properties.

-Chris