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

[John Criswell]

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.