[LLVMdev] Register allocation balancing issues

[nkavv at physics.auth.gr]

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