Comment by almostgotcaught

You have this exact issue in VLIW and it's exactly where you can't cheat by using heuristics:

Combinatorial Register Allocation and Instruction Scheduling

https://dl.acm.org/doi/10.1145/3332373