1. initial CSR cost
2. calculate LiveInterval weight and hints
3. allocate physical registers
   1. select or split
      1. PhysReg = tryAssign
         1. tryAssign
            1. for all physical registers, Matrix->checkInterference until find a physical register no interfere
            2. if no physical register or the physical register is hint register
            3. return the physical register
            4. if there is hint register for the virtual register
            5. if the hint register can be evicted
            6. evicInterference
            7. for all RegUnit of the physical register
            8. collect interfering LiveInterval
            9. for all interfering LiveInterval
            10. Matrix->unassign(LiveInterval)
            11. NewVRegs.push_back(LiveInterval->reg)
            12. return the hint register
            13. Cost = getCostPerUse(PhysReg)
            14. if Cost == 0
            15. return PhysReg
            16. CheapReg = tryEvict(Cost)
            17. return CheapReg ? CheapReg : PhysReg
         2. if PhysReg is unused callee saved register
            1. CSRReg = tryAssignCSRFirstTime
            2. if Stage == RS_Spill and VirtReg.isSpillable
            3. SA->analyze
            4. if calcSpillCost >= CSRCost
            5. return PhysReg
            6. CostPerUseLimit = 1
            7. return 0
            8. if Stage == RS_Split
            9. SA->analyze
            10. BestCand = calculateRegionSplitCost
            11. if BestCand == NoCand
            12. return PhysReg
            13. doRegionSplit
            14. return 0
            15. return PhysReg
            16. if CSRReg
            17. return CSRReg
         3. return PhysReg
      2. Stage = getStage
         1. Stage != RS_Split
            1. PhysReg = tryEvict
            2. for all physical registers under OrderLimit
            3. if getCostPerUse(PhysReg) >= CostPerUseLimit
            4. continue
            5. if CostPerUseLimit == 1 and PhysReg is unused callee saved register
            6. continue
            7. if the PhysReg can not be evicted
            8. continue
            9. BestPhys = PhysReg
            10. if PhysReg is hint register
            11. break
            12. if BestPhys == 0
            13. return 0
            14. evictInterference
            15. return BestPhys
            16. if PhysReg
            17. if Hint
            18. SetOfBrokenHints.insert
            19. return PhysReg
         2. Stage < RS_Split
            1. setStage(RS_Split)
            2. NewVRegs.push_back(VirtReg)
            3. return 0
         3. Stage >= RS_Done
            1. tryLastChanceRecoloring
            2. FixedRegisters.insert(VirtReg.reg)
            3. for all PhysRegs in order
            4. if Matrix->checkInterference > IK_VirtReg
            5. continue
            6. if it may not recolor all interferences (collect recoloring candidates)
            7. mayRecolorAllInterferences
            8. continue
            9. for all recoloring candidates
            10. enqueue to RecoloringQueue
            11. keep old PhysReg for the virtual registers (backup for restore if failed)
            12. Matrix->unassign
            13. Matrix->assign(VirtReg, PhysReg)
            14. if tryRecoloringCandidates
            15. tryRecoloringCandidates
            16. for all LiveInterval in RecoloringQueue
            17. PhysReg = selectOrSplitImpl(Depth + 1)
            18. if PhysReg == ~0u or PhysReg == 0
            19. return false
            20. Matrix->assign(LiveInterval, PhysReg)
            21. FixedRegisters.insert
            22. return true
            23. Matrix->unassign(VirtReg)
            24. return PhysReg
            25. restore original PhysReg
            26. return ~0u
            27. return
      3. PhysReg = trySplit
         1. trySplit
            1. if Stage >= RS_Spill
            2. return 0
            3. if LiveInterval is in one MBB
            4. SA->analyze
            5. PhysReg = tryLocalSplit
            6. if PhysReg
            7. return PhysReg
            8. return tryInstructionSplit
            9. SA->analyze
            10. if SA->didRepairRange
            11. Matrix->invalidateVirtRegs
            12. PhysReg = tryAssign
            13. if PhysReg
            14. return PhysReg
            15. if Stage < RS_Split2
            16. PhysReg = tryRegionSplit
            17. if PhysReg
            18. return PhysReg
            19. return tryBlockSplit
         2. if PhysReg
            1. return PhysReg
      4. spill
      5. setStage(RS_Done)
      6. return 0
4. try hint recoloring