I'm currently working on a compiler backend for a custom architecture which has some unusual constraints. The architecture has several super-registers with aliasing between the sub-registers, and none of these special registers can be spilled to memory. The code is initially constructed to ensure that registers can be allocated within these constraints (only one of the super-registers is live at a time).

Instruction scheduling (which is done before register allocation) must ensure that it only generates instruction sequences that have a valid register allocation.

After researching register allocation, it seems that the best fit for register allocation on my 'irregular architecture' is PBQP (partitioned boolean quadratic programming). However, during instruction scheduling, I don't need an (approximately) optimal register allocation, but rather just need to know whether there are any valid register allocations for a sequence of instructions.

Additionally, during scheduling, I'm going to need to repeatedly solve many similar instances of the CSP (constraint satisfaction problem). Any time register allocation is not possible, I'll need to try the problem again with only a few different nodes/edges (for a different instruction), and each time the CSP is satisfied, I'll need to solve it again with a few additional nodes/edges (for the next instruction).

I have not found any literature on solving similar CSPs taking advantage of the similarity, and the best algorithm I've found for solving PBQP approximately (from Nearly optimal register allocation with PBQP) destructively modifies the graph while solving.

Is there a better approach to use for testing register allocatability during instruction scheduling than PBQP, or is there a better algorithm for sequentially solving similar PBQP instances with only zero/infinite costs?

  • $\begingroup$ You should probably post on the related mailing lists or forums for development of LLVM. This is a Q&A site. If you have particular theoretical computer science question please state it (in a concise and rigorous manner). See help center for more information about the scope of Theoretical Computer Science. $\endgroup$ – Kaveh Jan 10 '16 at 22:17
  • $\begingroup$ What is your specific question? This is a Q&A site, so we expect a specific question (not a general open-ended call for feedback). See, our help center. Also, this site is for research-level questions related to theoretical CS. This question might not be theoretical enough, but it could be suitable for Computer Science, if you edit it to ask a specific question. Once you've made those edits, feel free to flag it for moderation attention and ask that it be migrated. $\endgroup$ – D.W. Jan 11 '16 at 6:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.