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

[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.

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>