nkavv at physics.auth.gr
2007-Nov-09 08:47 UTC
[LLVMdev] Register allocation balancing issues
Hi all i read the thread on register allocation extensions for better balancing of the binding of variables to registers, especially regarding their concurrent availability through a (probably large) number of read ports. A similar problem would apply for commiting a large number of results (write operands) to the multi-port register file. I'm also interested in this problem since i'm developing (actually: i have developed) the hardware for use in FPGA devices a processor core with similar capabilities (regarding the multi-input, multi-output requirement) without adhering to the TTA architectural principles. But it certainly departs from typical designs (of RISC/CISC hybrids) in a number of ways: for example, there is no centralized control unit. The closest work to this problem is probably an PLDI'04 paper, as well as, works on variable binding for High-Level Synthesis. Here is the reference to the PLDI paper: Balancing Register Allocation Across Threads for a Multithreaded Network Processor Xiaotong Zhuang and Santosh Pande PLDI'04 Another take (and quite not a longshot although probably Fernando -- thanks for the debugger, will try it -- has worked either alone or with NVK on the ILP formulation) is to write-up constraints for an ILP (integer linear programming) solution. I wouldn't mind to wait forever (for several minutes that is ^_^) for a valid register allocation to complete. My application programs range between 50 (the smallest) to about 2K instructions. Basic blocks would be anything from a few instructions to a few hundreds of instructions. There exists at least one compiler that works on an ILP and/or dynamic programming solution for all three problems of backend compilation. It is named OPTIMIST and lives on a Swedish univ. server. It has been GPL'ed but i don't know of anyone working on it (besides the developers themselves). Overall, I think processor developers should give serious thoughts on adopting LLVM for developing their compilers (however usually not for JIT compilation). It's probably the only solution that can combine reasonable time frames (1-6 man months) for a basic non-JIT compiler backend, ease of retargeting for incremental additions along with all the good frontend and infrastructure stuff. Kind regards Nikolaos Kavvadias
Fernando Magno Quintao Pereira
2007-Nov-09 17:44 UTC
[LLVMdev] Register allocation balancing issues
> > Another take (and quite not a longshot although probably Fernando -- thanks for > the debugger, will try it -- has worked either alone or with NVK on the ILP > formulation) is to write-up constraints for an ILP (integer linear programming) > solution. I wouldn't mind to wait forever (for several minutes that is ^_^) for > a valid register allocation to complete. My application programs range between > 50 (the smallest) to about 2K instructions. Basic blocks would be anything from > a few instructions to a few hundreds of instructions.Hi, actually, I have not done anything towards ILP for register allocation, but two of my friends have. Actually, there is a branch-and-bound solver for LLVM that produces very nice results. It was coded by Lang Hames, and I am using it in some tests. If you need the algorithm, I guess Lang can give it to you. best, Fernando
nkavv at physics.auth.gr
2007-Nov-10 02:38 UTC
[LLVMdev] Register allocation balancing issues
Hi Fernando> > Another take (and quite not a longshot although probably Fernando -- thanks > for > > the debugger, will try it -- has worked either alone or with NVK on the ILP > > formulation) is to write-up constraints for an ILP (integer linear > programming) > > solution. I wouldn't mind to wait forever (for several minutes that is ^_^) > for > > a valid register allocation to complete. My application programs range > between > > 50 (the smallest) to about 2K instructions. Basic blocks would be anything > from > > a few instructions to a few hundreds of instructions. > > Hi, actually, I have not done anything towards ILP for register > allocation, but two of my friends have. Actually, there is a > branch-and-bound solver for LLVM that produces very nice results. It was > coded by Lang Hames, and I am using it in some tests. If you need the > algorithm, I guess Lang can give it to you. > > best,I'm very glad to hear about the branch-and-bound solver that is in use in your team. If possible, I would like to try it. My soft core processor can be configured for up to 256 registers, so for such a large number of registers, certain things come in mind (and do quite affect performance) like register rotation etc. But first of all i would like to see if a good balancing can be obtained with longer allocation times, so the b-and-b solver sounds good. Again, thanks for your offer. BTW my own tools (it is a diverse sets of thingys) can be found here (feel free to download any): http://electronics.physics.auth.gr/tomeas/en/kavvadias.html Kind regards Nikolaos Kavvadias
Maybe Matching Threads
- [LLVMdev] Register allocation balancing issues
- [LLVMdev] Two labels around one instruction in Codegen
- [LLVMdev] Two labels around one instruction in Codegen
- [LLVMdev] secure virtual architecture / safecode
- [LLVMdev] LLVM's Pre-allocation Scheduler Tested against a Branch-and-Bound Scheduler