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?