1. initializeCSRCost
2. calculateSpillWeightsAndHints
   1. VRAI.calcualteSpillWeightAndHint
      1. calculate LiveInterval weight
3. allocatePhysRegs
   1. seedLiveRegs
      1. for all virtual registers
         1. enqueue(LIS->getInterval(Reg))
   2. while (dequeue())
      1. Matrix-> invalidateVirtRegs
      2. selectOrSplit
         1. selectOrSplitImpl
            1. tryAssign(VirtReg)
            2. for all PhysReg in AllocationOrder
            3. Matrix->checkInterference(VirtReg, PhysReg)
            4. if there is hint
            5. if (canEvictInterference(PhysReg = Hint))
            6. evictInterference(PhysReg = Hint)
            7. colloect all interferences of PhysReg
            8. for each interference
            9. Matrix->unassign
            10. NewVRegs.push_back
            11. return Hint
            12. if the physical register has cost
            13. CheapReg = tryEvict
            14. tryAssignCSRFirstTime
            15. if (getStage(VirtReg) == RS_Spill)
            16. SA->analyze
            17. if (calcSpillCost() >= CSRCost)
            18. return PhysReg
            19. return 0
            20. if (getStage(VirtReg) < RS_Split)
            21. SA->analyze
            22. calculateRegionSplitCost
            23. if (BestCand == NoCand)
            24. return PhysReg
            25. doRegionSplit
            26. splitAroundRegion
            27. return 0
            28. return PhysReg
            29. if (Stage != RS_Split)
            30. PhysReg = tryEvict
            31. return PhysReg
            32. if (Stage < RS_Split)
            33. setStage(RS_Split)
            34. NewVRegs.push_back(VirtReg)
            35. return 0
            36. if (Stage >= RS_Done || !VirtReg.isSpillable())
            37. return tryLastChanceRecoloring
            38. for all PhysReg
            39. if (Matrix->checkInterference > IK_VirtReg)
            40. continue
            41. if (!mayRecolorAllInterferences(RecoloringCandidates))
            42. continue
            43. for all RecoloringCandidates
            44. enqueue(RecoloringQueue, candidate)
            45. VirtRegToPhysReg[ItVirtReg] = VRM->getPhys(ItVirtReg)
            46. Matrix->unassign(candidate)
            47. Matrix->assign(VirtReg, PhysReg)
            48. if (tryRecoloringCandidate(RecoloringQueue))
            49. tryRecoloringCandidate
            50. for all items LI in RecoloringQueue
            51. dequeue
            52. PhysReg = selectOrSplitImpl(Depth + 1)
            53. Matrix->assign(*LI, PhysReg)
            54. Matrix->unassign(VirtReg)
            55. return PhysReg
            56. Matrix->unassign(VirtReg)
            57. for all RecoloringCandidates
            58. if (VRM->hasPhys(VirtReg))
            59. Matrix->unassign(VirtReg)
            60. PhysReg = VirtRegToPhysReg[VirtReg]
            61. Matrix->assign(VirtReg, PhysReg)
            62. return ~0u
            63. PhysReg = trySplit
            64. return PhysReg
            65. spiller().spill(LRE)
            66. setStage(RS_Done)
            67. return 0
      3. if (AvailablePhysReg)
         1. Matrix->assign
      4. for all VirtReg in SplitVRegs
         1. enqueue NewVRegs
4. tryHintsRecoloring
   1. for all LiveInterval in SetOfBrokenHints
      1. if (!VRM->hasPHys(LI->reg))
         1. continue
      2. tryHintRecoloring(LI)