What is "strong phi elimination"

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

What is "strong phi elimination"

Christopher Lamb
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




_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: What is "strong phi elimination"

Owen Anderson-2
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
>
>
>


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

smime.p7s (3K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: What is "strong phi elimination"

Chris Lattner

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

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: What is "strong phi elimination"

Seung Jae Lee
In reply to this post by Christopher Lamb
Do you mean that "normal" SSA phi elimination algorithm is DemotePHI()?

Thx,
Seung

---- Original message ----

>Date: Mon, 24 Mar 2008 21:43:06 -0700
>From: Chris Lattner <[hidden email]>  
>Subject: Re: [LLVMdev] What is "strong phi elimination"  
>To: LLVM Developers Mailing List <[hidden email]>
>Cc: Christopher Lamb <[hidden email]>
>
>
>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
>
>_______________________________________________
>LLVM Developers mailing list
>[hidden email]         http://llvm.cs.uiuc.edu
>http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: What is "strong phi elimination"

Chris Lattner

On Mar 24, 2008, at 10:25 PM, Seung Jae Lee wrote:

> Do you mean that "normal" SSA phi elimination algorithm is  
> DemotePHI()?

No, DemotePHI doesn't build an interference graph, and is not part of  
the code generator.

-Chris

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev