2 module RegAlloc.Graph.TrivColorable (
8 #include "HsVersions.h"
19 -- allocatableRegs is allMachRegNos with the fixed-use regs removed.
20 -- i.e., these are the regs for which we are prepared to allow the
21 -- register allocator to attempt to map VRegs to.
22 allocatableRegs :: [RegNo]
24 = let isFree i = isFastTrue (freeReg i)
25 in filter isFree allMachRegNos
28 -- | The number of regs in each class.
29 -- We go via top level CAFs to ensure that we're not recomputing
30 -- the length of these lists each time the fn is called.
31 allocatableRegsInClass :: RegClass -> Int
32 allocatableRegsInClass cls
34 RcInteger -> allocatableRegsInteger
35 RcDouble -> allocatableRegsDouble
36 RcFloat -> panic "Regs.allocatableRegsInClass: no match\n"
38 allocatableRegsInteger :: Int
39 allocatableRegsInteger
40 = length $ filter (\r -> regClass r == RcInteger)
41 $ map RealReg allocatableRegs
43 allocatableRegsDouble :: Int
45 = length $ filter (\r -> regClass r == RcDouble)
46 $ map RealReg allocatableRegs
50 -- trivColorable ---------------------------------------------------------------
52 -- trivColorable function for the graph coloring allocator
53 -- This gets hammered by scanGraph during register allocation,
54 -- so needs to be fairly efficient.
56 -- NOTE: This only works for arcitectures with just RcInteger and RcDouble
57 -- (which are disjoint) ie. x86, x86_64 and ppc
61 -- Doing a nice fold over the UniqSet makes trivColorable use
62 -- 32% of total compile time and 42% of total alloc when compiling SHA1.lhs from darcs.
64 trivColorable :: RegClass -> UniqSet Reg -> UniqSet Reg -> Bool
65 trivColorable classN conflicts exclusions
68 acc :: Reg -> (Int, Int) -> (Int, Int)
71 RcInteger -> (cd+1, cf)
72 RcDouble -> (cd, cf+1)
73 _ -> panic "Regs.trivColorable: reg class not handled"
75 tmp = foldUniqSet acc (0, 0) conflicts
76 (countInt, countFloat) = foldUniqSet acc tmp exclusions
78 squeese = worst countInt classN RcInteger
79 + worst countFloat classN RcDouble
81 in squeese < allocatableRegsInClass classN
83 -- | Worst case displacement
84 -- node N of classN has n neighbors of class C.
86 -- We currently only have RcInteger and RcDouble, which don't conflict at all.
87 -- This is a bit boring compared to what's in RegArchX86.
89 worst :: Int -> RegClass -> RegClass -> Int
94 RcInteger -> min n (allocatableRegsInClass RcInteger)
99 RcDouble -> min n (allocatableRegsInClass RcDouble)
104 -- The number of allocatable regs is hard coded here so we can do a fast comparision
105 -- in trivColorable. It's ok if these numbers are _less_ than the actual number of
106 -- free regs, but they can't be more or the register conflict graph won't color.
108 -- There is an allocatableRegsInClass :: RegClass -> Int, but doing the unboxing
109 -- is too slow for us here.
111 -- Compare Regs.freeRegs and MachRegs.h to get these numbers.
114 #define ALLOCATABLE_REGS_INTEGER (_ILIT(3))
115 #define ALLOCATABLE_REGS_DOUBLE (_ILIT(6))
116 #define ALLOCATABLE_REGS_FLOAT (_ILIT(0))
118 #elif x86_64_TARGET_ARCH
119 #define ALLOCATABLE_REGS_INTEGER (_ILIT(5))
120 #define ALLOCATABLE_REGS_DOUBLE (_ILIT(2))
121 #define ALLOCATABLE_REGS_FLOAT (_ILIT(0))
123 #elif powerpc_TARGET_ARCH
124 #define ALLOCATABLE_REGS_INTEGER (_ILIT(16))
125 #define ALLOCATABLE_REGS_DOUBLE (_ILIT(26))
126 #define ALLOCATABLE_REGS_FLOAT (_ILIT(0))
128 #elif sparc_TARGET_ARCH
129 #define ALLOCATABLE_REGS_INTEGER (_ILIT(3))
130 #define ALLOCATABLE_REGS_DOUBLE (_ILIT(6))
131 #define ALLOCATABLE_REGS_FLOAT (_ILIT(0))
134 #error ToDo: define ALLOCATABLE_REGS_INTEGER and ALLOCATABLE_REGS_DOUBLE
139 -> Triv Reg RegClass Reg
141 trivColorable regClass _ conflicts exclusions
142 = {-# SCC "trivColorable" #-}
146 NodeUFM _ _ left right
147 -> case isSqueesed cI cF right of
150 False -> isSqueesed cI' cF' left
151 True -> (# True, cI', cF' #)
154 -> case regClass reg of
156 -> case cI +# _ILIT(1) of
157 cI' -> (# cI' >=# ALLOCATABLE_REGS_INTEGER, cI', cF #)
160 -> case cF +# _ILIT(1) of
161 cF' -> (# cF' >=# ALLOCATABLE_REGS_DOUBLE, cI, cF' #)
164 -> case cF +# _ILIT(1) of
165 cF' -> (# cF' >=# ALLOCATABLE_REGS_FLOAT, cI, cF' #)
168 -> (# False, cI, cF #)
170 in case isSqueesed (_ILIT(0)) (_ILIT(0)) conflicts of
171 (# False, cI', cF' #)
172 -> case isSqueesed cI' cF' exclusions of
173 (# s, _, _ #) -> not s