[LLVMdev] Need help for my PBQP regAlloc proj in llvm....

[prasad dp]

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

[Lang Hames]

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.

_______________________________________________
LLVM Developers mailing list
LLV...@cs.uiuc.edu         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

[John Criswell]

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.