Hoopl: remove dependency on Hoopl package
[ghc.git] / compiler / cmm / CmmSwitch.hs
1 {-# LANGUAGE GADTs #-}
2 module CmmSwitch (
3 SwitchTargets,
4 mkSwitchTargets,
5 switchTargetsCases, switchTargetsDefault, switchTargetsRange, switchTargetsSigned,
6 mapSwitchTargets, switchTargetsToTable, switchTargetsFallThrough,
7 switchTargetsToList, eqSwitchTargetWith,
8
9 SwitchPlan(..),
10 targetSupportsSwitch,
11 createSwitchPlan,
12 ) where
13
14 import Outputable
15 import DynFlags
16 import Hoopl.Label (Label)
17
18 import Data.Maybe
19 import Data.List (groupBy)
20 import Data.Function (on)
21 import qualified Data.Map as M
22
23 -- Note [Cmm Switches, the general plan]
24 -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
25 --
26 -- Compiling a high-level switch statement, as it comes out of a STG case
27 -- expression, for example, allows for a surprising amount of design decisions.
28 -- Therefore, we cleanly separated this from the Stg → Cmm transformation, as
29 -- well as from the actual code generation.
30 --
31 -- The overall plan is:
32 -- * The Stg → Cmm transformation creates a single `SwitchTargets` in
33 -- emitSwitch and emitCmmLitSwitch in StgCmmUtils.hs.
34 -- At this stage, they are unsuitable for code generation.
35 -- * A dedicated Cmm transformation (CmmImplementSwitchPlans) replaces these
36 -- switch statements with code that is suitable for code generation, i.e.
37 -- a nice balanced tree of decisions with dense jump tables in the leafs.
38 -- The actual planning of this tree is performed in pure code in createSwitchPlan
39 -- in this module. See Note [createSwitchPlan].
40 -- * The actual code generation will not do any further processing and
41 -- implement each CmmSwitch with a jump tables.
42 --
43 -- When compiling to LLVM or C, CmmImplementSwitchPlans leaves the switch
44 -- statements alone, as we can turn a SwitchTargets value into a nice
45 -- switch-statement in LLVM resp. C, and leave the rest to the compiler.
46 --
47 -- See Note [CmmSwitch vs. CmmImplementSwitchPlans] why the two module are
48 -- separated.
49
50 -----------------------------------------------------------------------------
51 -- Note [Magic Constants in CmmSwitch]
52 --
53 -- There are a lot of heuristics here that depend on magic values where it is
54 -- hard to determine the "best" value (for whatever that means). These are the
55 -- magic values:
56
57 -- | Number of consecutive default values allowed in a jump table. If there are
58 -- more of them, the jump tables are split.
59 --
60 -- Currently 7, as it costs 7 words of additional code when a jump table is
61 -- split (at least on x64, determined experimentally).
62 maxJumpTableHole :: Integer
63 maxJumpTableHole = 7
64
65 -- | Minimum size of a jump table. If the number is smaller, the switch is
66 -- implemented using conditionals.
67 -- Currently 5, because an if-then-else tree of 4 values is nice and compact.
68 minJumpTableSize :: Int
69 minJumpTableSize = 5
70
71 -- | Minimum non-zero offset for a jump table. See Note [Jump Table Offset].
72 minJumpTableOffset :: Integer
73 minJumpTableOffset = 2
74
75
76 -----------------------------------------------------------------------------
77 -- Switch Targets
78
79 -- Note [SwitchTargets]:
80 -- ~~~~~~~~~~~~~~~~~~~~~
81 --
82 -- The branches of a switch are stored in a SwitchTargets, which consists of an
83 -- (optional) default jump target, and a map from values to jump targets.
84 --
85 -- If the default jump target is absent, the behaviour of the switch outside the
86 -- values of the map is undefined.
87 --
88 -- We use an Integer for the keys the map so that it can be used in switches on
89 -- unsigned as well as signed integers.
90 --
91 -- The map may be empty (we prune out-of-range branches here, so it could be us
92 -- emptying it).
93 --
94 -- Before code generation, the table needs to be brought into a form where all
95 -- entries are non-negative, so that it can be compiled into a jump table.
96 -- See switchTargetsToTable.
97
98
99 -- | A value of type SwitchTargets contains the alternatives for a 'CmmSwitch'
100 -- value, and knows whether the value is signed, the possible range, an
101 -- optional default value and a map from values to jump labels.
102 data SwitchTargets =
103 SwitchTargets
104 Bool -- Signed values
105 (Integer, Integer) -- Range
106 (Maybe Label) -- Default value
107 (M.Map Integer Label) -- The branches
108 deriving (Show, Eq)
109
110 -- | The smart constructr mkSwitchTargets normalises the map a bit:
111 -- * No entries outside the range
112 -- * No entries equal to the default
113 -- * No default if all elements have explicit values
114 mkSwitchTargets :: Bool -> (Integer, Integer) -> Maybe Label -> M.Map Integer Label -> SwitchTargets
115 mkSwitchTargets signed range@(lo,hi) mbdef ids
116 = SwitchTargets signed range mbdef' ids'
117 where
118 ids' = dropDefault $ restrict ids
119 mbdef' | defaultNeeded = mbdef
120 | otherwise = Nothing
121
122 -- Drop entries outside the range, if there is a range
123 restrict = restrictMap (lo,hi)
124
125 -- Drop entries that equal the default, if there is a default
126 dropDefault | Just l <- mbdef = M.filter (/= l)
127 | otherwise = id
128
129 -- Check if the default is still needed
130 defaultNeeded = fromIntegral (M.size ids') /= hi-lo+1
131
132
133 -- | Changes all labels mentioned in the SwitchTargets value
134 mapSwitchTargets :: (Label -> Label) -> SwitchTargets -> SwitchTargets
135 mapSwitchTargets f (SwitchTargets signed range mbdef branches)
136 = SwitchTargets signed range (fmap f mbdef) (fmap f branches)
137
138 -- | Returns the list of non-default branches of the SwitchTargets value
139 switchTargetsCases :: SwitchTargets -> [(Integer, Label)]
140 switchTargetsCases (SwitchTargets _ _ _ branches) = M.toList branches
141
142 -- | Return the default label of the SwitchTargets value
143 switchTargetsDefault :: SwitchTargets -> Maybe Label
144 switchTargetsDefault (SwitchTargets _ _ mbdef _) = mbdef
145
146 -- | Return the range of the SwitchTargets value
147 switchTargetsRange :: SwitchTargets -> (Integer, Integer)
148 switchTargetsRange (SwitchTargets _ range _ _) = range
149
150 -- | Return whether this is used for a signed value
151 switchTargetsSigned :: SwitchTargets -> Bool
152 switchTargetsSigned (SwitchTargets signed _ _ _) = signed
153
154 -- | switchTargetsToTable creates a dense jump table, usable for code generation.
155 --
156 -- Also returns an offset to add to the value; the list is 0-based on the
157 -- result of that addition.
158 --
159 -- The conversion from Integer to Int is a bit of a wart, as the actual
160 -- scrutinee might be an unsigned word, but it just works, due to wrap-around
161 -- arithmetic (as verified by the CmmSwitchTest test case).
162 switchTargetsToTable :: SwitchTargets -> (Int, [Maybe Label])
163 switchTargetsToTable (SwitchTargets _ (lo,hi) mbdef branches)
164 = (fromIntegral (-start), [ labelFor i | i <- [start..hi] ])
165 where
166 labelFor i = case M.lookup i branches of Just l -> Just l
167 Nothing -> mbdef
168 start | lo >= 0 && lo < minJumpTableOffset = 0 -- See Note [Jump Table Offset]
169 | otherwise = lo
170
171 -- Note [Jump Table Offset]
172 -- ~~~~~~~~~~~~~~~~~~~~~~~~
173 --
174 -- Usually, the code for a jump table starting at x will first subtract x from
175 -- the value, to avoid a large amount of empty entries. But if x is very small,
176 -- the extra entries are no worse than the subtraction in terms of code size, and
177 -- not having to do the subtraction is quicker.
178 --
179 -- I.e. instead of
180 -- _u20N:
181 -- leaq -1(%r14),%rax
182 -- jmp *_n20R(,%rax,8)
183 -- _n20R:
184 -- .quad _c20p
185 -- .quad _c20q
186 -- do
187 -- _u20N:
188 -- jmp *_n20Q(,%r14,8)
189 --
190 -- _n20Q:
191 -- .quad 0
192 -- .quad _c20p
193 -- .quad _c20q
194 -- .quad _c20r
195
196 -- | The list of all labels occuring in the SwitchTargets value.
197 switchTargetsToList :: SwitchTargets -> [Label]
198 switchTargetsToList (SwitchTargets _ _ mbdef branches)
199 = maybeToList mbdef ++ M.elems branches
200
201 -- | Groups cases with equal targets, suitable for pretty-printing to a
202 -- c-like switch statement with fall-through semantics.
203 switchTargetsFallThrough :: SwitchTargets -> ([([Integer], Label)], Maybe Label)
204 switchTargetsFallThrough (SwitchTargets _ _ mbdef branches) = (groups, mbdef)
205 where
206 groups = map (\xs -> (map fst xs, snd (head xs))) $
207 groupBy ((==) `on` snd) $
208 M.toList branches
209
210 -- | Custom equality helper, needed for "CmmCommonBlockElim"
211 eqSwitchTargetWith :: (Label -> Label -> Bool) -> SwitchTargets -> SwitchTargets -> Bool
212 eqSwitchTargetWith eq (SwitchTargets signed1 range1 mbdef1 ids1) (SwitchTargets signed2 range2 mbdef2 ids2) =
213 signed1 == signed2 && range1 == range2 && goMB mbdef1 mbdef2 && goList (M.toList ids1) (M.toList ids2)
214 where
215 goMB Nothing Nothing = True
216 goMB (Just l1) (Just l2) = l1 `eq` l2
217 goMB _ _ = False
218 goList [] [] = True
219 goList ((i1,l1):ls1) ((i2,l2):ls2) = i1 == i2 && l1 `eq` l2 && goList ls1 ls2
220 goList _ _ = False
221
222 -----------------------------------------------------------------------------
223 -- Code generation for Switches
224
225
226 -- | A SwitchPlan abstractly describes how a Switch statement ought to be
227 -- implemented. See Note [createSwitchPlan]
228 data SwitchPlan
229 = Unconditionally Label
230 | IfEqual Integer Label SwitchPlan
231 | IfLT Bool Integer SwitchPlan SwitchPlan
232 | JumpTable SwitchTargets
233 deriving Show
234 --
235 -- Note [createSwitchPlan]
236 -- ~~~~~~~~~~~~~~~~~~~~~~~
237 --
238 -- A SwitchPlan describes how a Switch statement is to be broken down into
239 -- smaller pieces suitable for code generation.
240 --
241 -- createSwitchPlan creates such a switch plan, in these steps:
242 -- 1. It splits the switch statement at segments of non-default values that
243 -- are too large. See splitAtHoles and Note [Magic Constants in CmmSwitch]
244 -- 2. Too small jump tables should be avoided, so we break up smaller pieces
245 -- in breakTooSmall.
246 -- 3. We fill in the segments between those pieces with a jump to the default
247 -- label (if there is one), returning a SeparatedList in mkFlatSwitchPlan
248 -- 4. We find and replace two less-than branches by a single equal-to-test in
249 -- findSingleValues
250 -- 5. The thus collected pieces are assembled to a balanced binary tree.
251
252
253 -- | Does the target support switch out of the box? Then leave this to the
254 -- target!
255 targetSupportsSwitch :: HscTarget -> Bool
256 targetSupportsSwitch HscC = True
257 targetSupportsSwitch HscLlvm = True
258 targetSupportsSwitch _ = False
259
260 -- | This function creates a SwitchPlan from a SwitchTargets value, breaking it
261 -- down into smaller pieces suitable for code generation.
262 createSwitchPlan :: SwitchTargets -> SwitchPlan
263 -- Lets do the common case of a singleton map quicky and efficiently (#10677)
264 createSwitchPlan (SwitchTargets _signed _range (Just defLabel) m)
265 | [(x, l)] <- M.toList m
266 = IfEqual x l (Unconditionally defLabel)
267 -- And another common case, matching booleans
268 createSwitchPlan (SwitchTargets _signed (lo,hi) Nothing m)
269 | [(x1, l1), (x2,l2)] <- M.toAscList m
270 , x1 == lo
271 , x2 == hi
272 , x1 + 1 == x2
273 = IfEqual x1 l1 (Unconditionally l2)
274 createSwitchPlan (SwitchTargets signed range mbdef m) =
275 -- pprTrace "createSwitchPlan" (text (show ids) $$ text (show (range,m)) $$ text (show pieces) $$ text (show flatPlan) $$ text (show plan)) $
276 plan
277 where
278 pieces = concatMap breakTooSmall $ splitAtHoles maxJumpTableHole m
279 flatPlan = findSingleValues $ mkFlatSwitchPlan signed mbdef range pieces
280 plan = buildTree signed $ flatPlan
281
282
283 ---
284 --- Step 1: Splitting at large holes
285 ---
286 splitAtHoles :: Integer -> M.Map Integer a -> [M.Map Integer a]
287 splitAtHoles _ m | M.null m = []
288 splitAtHoles holeSize m = map (\range -> restrictMap range m) nonHoles
289 where
290 holes = filter (\(l,h) -> h - l > holeSize) $ zip (M.keys m) (tail (M.keys m))
291 nonHoles = reassocTuples lo holes hi
292
293 (lo,_) = M.findMin m
294 (hi,_) = M.findMax m
295
296 ---
297 --- Step 2: Avoid small jump tables
298 ---
299 -- We do not want jump tables below a certain size. This breaks them up
300 -- (into singleton maps, for now).
301 breakTooSmall :: M.Map Integer a -> [M.Map Integer a]
302 breakTooSmall m
303 | M.size m > minJumpTableSize = [m]
304 | otherwise = [M.singleton k v | (k,v) <- M.toList m]
305
306 ---
307 --- Step 3: Fill in the blanks
308 ---
309
310 -- | A FlatSwitchPlan is a list of SwitchPlans, with an integer inbetween every
311 -- two entries, dividing the range.
312 -- So if we have (abusing list syntax) [plan1,n,plan2], then we use plan1 if
313 -- the expression is < n, and plan2 otherwise.
314
315 type FlatSwitchPlan = SeparatedList Integer SwitchPlan
316
317 mkFlatSwitchPlan :: Bool -> Maybe Label -> (Integer, Integer) -> [M.Map Integer Label] -> FlatSwitchPlan
318
319 -- If we have no default (i.e. undefined where there is no entry), we can
320 -- branch at the minimum of each map
321 mkFlatSwitchPlan _ Nothing _ [] = pprPanic "mkFlatSwitchPlan with nothing left to do" empty
322 mkFlatSwitchPlan signed Nothing _ (m:ms)
323 = (mkLeafPlan signed Nothing m , [ (fst (M.findMin m'), mkLeafPlan signed Nothing m') | m' <- ms ])
324
325 -- If we have a default, we have to interleave segments that jump
326 -- to the default between the maps
327 mkFlatSwitchPlan signed (Just l) r ms = let ((_,p1):ps) = go r ms in (p1, ps)
328 where
329 go (lo,hi) []
330 | lo > hi = []
331 | otherwise = [(lo, Unconditionally l)]
332 go (lo,hi) (m:ms)
333 | lo < min
334 = (lo, Unconditionally l) : go (min,hi) (m:ms)
335 | lo == min
336 = (lo, mkLeafPlan signed (Just l) m) : go (max+1,hi) ms
337 | otherwise
338 = pprPanic "mkFlatSwitchPlan" (integer lo <+> integer min)
339 where
340 min = fst (M.findMin m)
341 max = fst (M.findMax m)
342
343
344 mkLeafPlan :: Bool -> Maybe Label -> M.Map Integer Label -> SwitchPlan
345 mkLeafPlan signed mbdef m
346 | [(_,l)] <- M.toList m -- singleton map
347 = Unconditionally l
348 | otherwise
349 = JumpTable $ mkSwitchTargets signed (min,max) mbdef m
350 where
351 min = fst (M.findMin m)
352 max = fst (M.findMax m)
353
354 ---
355 --- Step 4: Reduce the number of branches using ==
356 ---
357
358 -- A sequence of three unconditional jumps, with the outer two pointing to the
359 -- same value and the bounds off by exactly one can be improved
360 findSingleValues :: FlatSwitchPlan -> FlatSwitchPlan
361 findSingleValues (Unconditionally l, (i, Unconditionally l2) : (i', Unconditionally l3) : xs)
362 | l == l3 && i + 1 == i'
363 = findSingleValues (IfEqual i l2 (Unconditionally l), xs)
364 findSingleValues (p, (i,p'):xs)
365 = (p,i) `consSL` findSingleValues (p', xs)
366 findSingleValues (p, [])
367 = (p, [])
368
369 ---
370 --- Step 5: Actually build the tree
371 ---
372
373 -- Build a balanced tree from a separated list
374 buildTree :: Bool -> FlatSwitchPlan -> SwitchPlan
375 buildTree _ (p,[]) = p
376 buildTree signed sl = IfLT signed m (buildTree signed sl1) (buildTree signed sl2)
377 where
378 (sl1, m, sl2) = divideSL sl
379
380
381
382 --
383 -- Utility data type: Non-empty lists with extra markers in between each
384 -- element:
385 --
386
387 type SeparatedList b a = (a, [(b,a)])
388
389 consSL :: (a, b) -> SeparatedList b a -> SeparatedList b a
390 consSL (a, b) (a', xs) = (a, (b,a'):xs)
391
392 divideSL :: SeparatedList b a -> (SeparatedList b a, b, SeparatedList b a)
393 divideSL (_,[]) = error "divideSL: Singleton SeparatedList"
394 divideSL (p,xs) = ((p, xs1), m, (p', xs2))
395 where
396 (xs1, (m,p'):xs2) = splitAt (length xs `div` 2) xs
397
398 --
399 -- Other Utilities
400 --
401
402 restrictMap :: (Integer,Integer) -> M.Map Integer b -> M.Map Integer b
403 restrictMap (lo,hi) m = mid
404 where (_, mid_hi) = M.split (lo-1) m
405 (mid, _) = M.split (hi+1) mid_hi
406
407 -- for example: reassocTuples a [(b,c),(d,e)] f == [(a,b),(c,d),(e,f)]
408 reassocTuples :: a -> [(a,a)] -> a -> [(a,a)]
409 reassocTuples initial [] last
410 = [(initial,last)]
411 reassocTuples initial ((a,b):tuples) last
412 = (initial,a) : reassocTuples b tuples last
413
414 -- Note [CmmSwitch vs. CmmImplementSwitchPlans]
415 -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
416 -- I (Joachim) separated the two somewhat closely related modules
417 --
418 -- - CmmSwitch, which provides the CmmSwitchTargets type and contains the strategy
419 -- for implementing a Cmm switch (createSwitchPlan), and
420 -- - CmmImplementSwitchPlans, which contains the actuall Cmm graph modification,
421 --
422 -- for these reasons:
423 --
424 -- * CmmSwitch is very low in the dependency tree, i.e. does not depend on any
425 -- GHC specific modules at all (with the exception of Output and Hoople
426 -- (Literal)). CmmImplementSwitchPlans is the Cmm transformation and hence very
427 -- high in the dependency tree.
428 -- * CmmSwitch provides the CmmSwitchTargets data type, which is abstract, but
429 -- used in CmmNodes.
430 -- * Because CmmSwitch is low in the dependency tree, the separation allows
431 -- for more parallelism when building GHC.
432 -- * The interaction between the modules is very explicit and easy to
433 -- understand, due to the small and simple interface.