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