llvm dev - May 2010 - [LLVMdev] Need help for my PBQP regAlloc proj in llvm....

Hello,
we are currently working on my project that aims at improving the register
allocation scheme by identifying if the interference graphs are chordal or
not.
 we are working on the llvm compiler .we are forcing the compiler to use
PBQP register allocation scheme by an option of ' ' regalloc=pbqp '
during
the execution of prgm. we have been succesfull in accessing the interference
graph information and creating our version of interference matrix depicting
the same information. we then use the same matrix to inspect for its chordal
nature. and we are looking for colouring the chordal graph in a linear time
using available algorithms.
I am looking for material that is related to the above mentioned work that
would help me to prepare my report. Particularly i am looking for the
information about Linear scan algorithm and PBQP scheme. PLZ do help me out.

Thanks,
Durga Prasad
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20100511/ab81226e/attachment.html>

Hi Prasad,

The comments at the beginning of RegAllocPBQP.cpp list the two most relevant
papers for PBQP register allocation.

//   (1) Hames, L. and Scholz, B. 2006. Nearly optimal register allocation
with

//   PBQP. In Proceedings of the 7th Joint Modular Languages Conference


//   (JMLC'06). LNCS, vol. 4228. Springer, New York, NY, USA. 346-361.


//


//   (2) Scholz, B., Eckstein, E. 2002. Register allocation for irregular


//   architectures. In Proceedings of the Joint Conference on Languages,


//   Compilers and Tools for Embedded Systems (LCTES'02), ACM Press, New
York,

//   NY, USA, 139-148.

The basics of the linear scan algorithm are described in the paper "Linear
Scan Register Allocation" by Poletto and Sarkar. However, LLVM's
"linear
scan" differs significantly from the behaviour described in that paper. In
particular when LLVM's linear scan allocator spills a live interval it
backtracks to the start of that interval to continue allocation. This means
that LLVM's "linear scan" isn't actually linear. I'm not
sure whether
there's any reference material that describes the behaviour of LLVM's
linear
scan apart from the code itself.

Do any other register allocation people have a better answer to the linear
scan question?

Cheers,
Lang.

On Tue, May 11, 2010 at 8:56 PM, prasad dp <prasu.kothinti at gmail.com>
wrote:
> Hello,
> we are currently working on my project that aims at improving the register
> allocation scheme by identifying if the interference graphs are chordal or
> not.
>  we are working on the llvm compiler .we are forcing the compiler to use
> PBQP register allocation scheme by an option of ' ' regalloc=pbqp
' during
> the execution of prgm. we have been succesfull in accessing the
interference
> graph information and creating our version of interference matrix depicting
> the same information. we then use the same matrix to inspect for its
chordal
> nature. and we are looking for colouring the chordal graph in a linear time
> using available algorithms.
> I am looking for material that is related to the above mentioned work that
> would help me to prepare my report. Particularly i am looking for the
> information about Linear scan algorithm and PBQP scheme. PLZ do help me
out.
>
> Thanks,
> Durga Prasad
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20100512/0524a64b/attachment.html>

Lang Hames wrote:
> Hi Prasad,
>
> The comments at the beginning of RegAllocPBQP.cpp list the two most 
> relevant papers for PBQP register allocation.
>
> //   (1) Hames, L. and Scholz, B. 2006. Nearly optimal register 
> allocation with                                                       
>                                                                       
>                 
> //   PBQP. In Proceedings of the 7th Joint Modular Languages 
> Conference                                                             
>                                                                       
>                   
> //   (JMLC'06). LNCS, vol. 4228. Springer, New York, NY, USA. 346-361. 
>                                                                       
>                                                                       
>          
> //                                                                     
>                                                                       
>                                                                       
>          
> //   (2) Scholz, B., Eckstein, E. 2002. Register allocation for 
> irregular                                                             
>                                                                       
>                 
> //   architectures. In Proceedings of the Joint Conference on 
> Languages,                                                             
>                                                                       
>                  
> //   Compilers and Tools for Embedded Systems (LCTES'02), ACM Press, 
> New York,                                                             
>                                                                       
>            
> //   NY, USA, 139-148.                                
>
> The basics of the linear scan algorithm are described in the paper 
> "Linear Scan Register Allocation" by Poletto and Sarkar. However,
> LLVM's "linear scan" differs significantly from the behaviour
> described in that paper. In particular when LLVM's linear scan 
> allocator spills a live interval it backtracks to the start of that 
> interval to continue allocation. This means that LLVM's "linear
scan"
> isn't actually linear. I'm not sure whether there's any
reference
> material that describes the behaviour of LLVM's linear scan apart from 
> the code itself.
I believe the linear scan register allocator was first written by Alkis 
(a former student in our research group).  If the deviation from the 
original linear scan paper is due to his work, his report 
(http://llvm.org/ProjectsWithLLVM/#linearscan) may explain the 
differences and their motivations.

-- John T.