Fix and document Unique generation for sum TyCon and DataCons
[ghc.git] / compiler / basicTypes / Unique.hs
1 {-
2 (c) The University of Glasgow 2006
3 (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
4
5
6 @Uniques@ are used to distinguish entities in the compiler (@Ids@,
7 @Classes@, etc.) from each other. Thus, @Uniques@ are the basic
8 comparison key in the compiler.
9
10 If there is any single operation that needs to be fast, it is @Unique@
11 comparison. Unsurprisingly, there is quite a bit of huff-and-puff
12 directed to that end.
13
14 Some of the other hair in this code is to be able to use a
15 ``splittable @UniqueSupply@'' if requested/possible (not standard
16 Haskell).
17 -}
18
19 {-# LANGUAGE CPP, BangPatterns, MagicHash #-}
20
21 module Unique (
22 -- * Main data types
23 Unique, Uniquable(..),
24
25 -- ** Constructors, destructors and operations on 'Unique's
26 hasKey,
27
28 pprUnique,
29
30 mkUniqueGrimily, -- Used in UniqSupply only!
31 getKey, -- Used in Var, UniqFM, Name only!
32 mkUnique, unpkUnique, -- Used in BinIface only
33
34 incrUnique, -- Used for renumbering
35 deriveUnique, -- Ditto
36 newTagUnique, -- Used in CgCase
37 initTyVarUnique,
38 nonDetCmpUnique,
39
40 -- ** Making built-in uniques
41
42 -- now all the built-in Uniques (and functions to make them)
43 -- [the Oh-So-Wonderful Haskell module system wins again...]
44 mkAlphaTyVarUnique,
45 mkPrimOpIdUnique,
46 mkTupleTyConUnique, mkTupleDataConUnique,
47 mkSumTyConUnique, mkSumDataConUnique,
48 mkCTupleTyConUnique,
49 mkPreludeMiscIdUnique, mkPreludeDataConUnique,
50 mkPreludeTyConUnique, mkPreludeClassUnique,
51 mkPArrDataConUnique, mkCoVarUnique,
52
53 mkVarOccUnique, mkDataOccUnique, mkTvOccUnique, mkTcOccUnique,
54 mkRegSingleUnique, mkRegPairUnique, mkRegClassUnique, mkRegSubUnique,
55 mkCostCentreUnique,
56
57 tyConRepNameUnique,
58 dataConWorkerUnique, dataConRepNameUnique,
59
60 mkBuiltinUnique,
61 mkPseudoUniqueD,
62 mkPseudoUniqueE,
63 mkPseudoUniqueH
64 ) where
65
66 #include "HsVersions.h"
67
68 import BasicTypes
69 import FastString
70 import Outputable
71 import Util
72
73 -- just for implementing a fast [0,61) -> Char function
74 import GHC.Exts (indexCharOffAddr#, Char(..), Int(..))
75
76 import Data.Char ( chr, ord )
77 import Data.Bits
78
79 {-
80 ************************************************************************
81 * *
82 \subsection[Unique-type]{@Unique@ type and operations}
83 * *
84 ************************************************************************
85
86 The @Chars@ are ``tag letters'' that identify the @UniqueSupply@.
87 Fast comparison is everything on @Uniques@:
88 -}
89
90 --why not newtype Int?
91
92 -- | The type of unique identifiers that are used in many places in GHC
93 -- for fast ordering and equality tests. You should generate these with
94 -- the functions from the 'UniqSupply' module
95 data Unique = MkUnique {-# UNPACK #-} !Int
96
97 {-
98 Now come the functions which construct uniques from their pieces, and vice versa.
99 The stuff about unique *supplies* is handled further down this module.
100 -}
101
102 unpkUnique :: Unique -> (Char, Int) -- The reverse
103
104 mkUniqueGrimily :: Int -> Unique -- A trap-door for UniqSupply
105 getKey :: Unique -> Int -- for Var
106
107 incrUnique :: Unique -> Unique
108 stepUnique :: Unique -> Int -> Unique
109 deriveUnique :: Unique -> Int -> Unique
110 newTagUnique :: Unique -> Char -> Unique
111
112 mkUniqueGrimily = MkUnique
113
114 {-# INLINE getKey #-}
115 getKey (MkUnique x) = x
116
117 incrUnique (MkUnique i) = MkUnique (i + 1)
118 stepUnique (MkUnique i) n = MkUnique (i + n)
119
120 -- deriveUnique uses an 'X' tag so that it won't clash with
121 -- any of the uniques produced any other way
122 -- SPJ says: this looks terribly smelly to me!
123 deriveUnique (MkUnique i) delta = mkUnique 'X' (i + delta)
124
125 -- newTagUnique changes the "domain" of a unique to a different char
126 newTagUnique u c = mkUnique c i where (_,i) = unpkUnique u
127
128 -- pop the Char in the top 8 bits of the Unique(Supply)
129
130 -- No 64-bit bugs here, as long as we have at least 32 bits. --JSM
131
132 -- and as long as the Char fits in 8 bits, which we assume anyway!
133
134 mkUnique :: Char -> Int -> Unique -- Builds a unique from pieces
135 -- NOT EXPORTED, so that we can see all the Chars that
136 -- are used in this one module
137 mkUnique c i
138 = MkUnique (tag .|. bits)
139 where
140 tag = ord c `shiftL` 24
141 bits = i .&. 16777215 {-``0x00ffffff''-}
142
143 unpkUnique (MkUnique u)
144 = let
145 -- as long as the Char may have its eighth bit set, we
146 -- really do need the logical right-shift here!
147 tag = chr (u `shiftR` 24)
148 i = u .&. 16777215 {-``0x00ffffff''-}
149 in
150 (tag, i)
151
152 {-
153 ************************************************************************
154 * *
155 \subsection[Uniquable-class]{The @Uniquable@ class}
156 * *
157 ************************************************************************
158 -}
159
160 -- | Class of things that we can obtain a 'Unique' from
161 class Uniquable a where
162 getUnique :: a -> Unique
163
164 hasKey :: Uniquable a => a -> Unique -> Bool
165 x `hasKey` k = getUnique x == k
166
167 instance Uniquable FastString where
168 getUnique fs = mkUniqueGrimily (uniqueOfFS fs)
169
170 instance Uniquable Int where
171 getUnique i = mkUniqueGrimily i
172
173 {-
174 ************************************************************************
175 * *
176 \subsection[Unique-instances]{Instance declarations for @Unique@}
177 * *
178 ************************************************************************
179
180 And the whole point (besides uniqueness) is fast equality. We don't
181 use `deriving' because we want {\em precise} control of ordering
182 (equality on @Uniques@ is v common).
183 -}
184
185 -- Note [Unique Determinism]
186 -- ~~~~~~~~~~~~~~~~~~~~~~~~~
187 -- The order of allocated @Uniques@ is not stable across rebuilds.
188 -- The main reason for that is that typechecking interface files pulls
189 -- @Uniques@ from @UniqSupply@ and the interface file for the module being
190 -- currently compiled can, but doesn't have to exist.
191 --
192 -- It gets more complicated if you take into account that the interface
193 -- files are loaded lazily and that building multiple files at once has to
194 -- work for any subset of interface files present. When you add parallelism
195 -- this makes @Uniques@ hopelessly random.
196 --
197 -- As such, to get deterministic builds, the order of the allocated
198 -- @Uniques@ should not affect the final result.
199 -- see also wiki/DeterministicBuilds
200 --
201 -- Note [Unique Determinism and code generation]
202 -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
203 -- The goal of the deterministic builds (wiki/DeterministicBuilds, #4012)
204 -- is to get ABI compatible binaries given the same inputs and environment.
205 -- The motivation behind that is that if the ABI doesn't change the
206 -- binaries can be safely reused.
207 -- Note that this is weaker than bit-for-bit identical binaries and getting
208 -- bit-for-bit identical binaries is not a goal for now.
209 -- This means that we don't care about nondeterminism that happens after
210 -- the interface files are created, in particular we don't care about
211 -- register allocation and code generation.
212 -- To track progress on bit-for-bit determinism see #12262.
213
214 eqUnique :: Unique -> Unique -> Bool
215 eqUnique (MkUnique u1) (MkUnique u2) = u1 == u2
216
217 -- Provided here to make it explicit at the call-site that it can
218 -- introduce non-determinism.
219 -- See Note [Unique Determinism]
220 -- See Note [No Ord for Unique]
221 nonDetCmpUnique :: Unique -> Unique -> Ordering
222 nonDetCmpUnique (MkUnique u1) (MkUnique u2)
223 = if u1 == u2 then EQ else if u1 < u2 then LT else GT
224
225 {-
226 Note [No Ord for Unique]
227 ~~~~~~~~~~~~~~~~~~~~~~~~~~
228 As explained in Note [Unique Determinism] the relative order of Uniques
229 is nondeterministic. To prevent from accidental use the Ord Unique
230 instance has been removed.
231 This makes it easier to maintain deterministic builds, but comes with some
232 drawbacks.
233 The biggest drawback is that Maps keyed by Uniques can't directly be used.
234 The alternatives are:
235
236 1) Use UniqFM or UniqDFM, see Note [Deterministic UniqFM] to decide which
237 2) Create a newtype wrapper based on Unique ordering where nondeterminism
238 is controlled. See Module.ModuleEnv
239 3) Change the algorithm to use nonDetCmpUnique and document why it's still
240 deterministic
241 4) Use TrieMap as done in CmmCommonBlockElim.groupByLabel
242 -}
243
244 instance Eq Unique where
245 a == b = eqUnique a b
246 a /= b = not (eqUnique a b)
247
248 instance Uniquable Unique where
249 getUnique u = u
250
251 -- We do sometimes make strings with @Uniques@ in them:
252
253 showUnique :: Unique -> String
254 showUnique uniq
255 = case unpkUnique uniq of
256 (tag, u) -> finish_show tag u (iToBase62 u)
257
258 finish_show :: Char -> Int -> String -> String
259 finish_show 't' u _pp_u | u < 26
260 = -- Special case to make v common tyvars, t1, t2, ...
261 -- come out as a, b, ... (shorter, easier to read)
262 [chr (ord 'a' + u)]
263 finish_show tag _ pp_u = tag : pp_u
264
265 pprUnique :: Unique -> SDoc
266 pprUnique u = text (showUnique u)
267
268 instance Outputable Unique where
269 ppr = pprUnique
270
271 instance Show Unique where
272 show uniq = showUnique uniq
273
274 {-
275 ************************************************************************
276 * *
277 \subsection[Utils-base62]{Base-62 numbers}
278 * *
279 ************************************************************************
280
281 A character-stingy way to read/write numbers (notably Uniques).
282 The ``62-its'' are \tr{[0-9a-zA-Z]}. We don't handle negative Ints.
283 Code stolen from Lennart.
284 -}
285
286 iToBase62 :: Int -> String
287 iToBase62 n_
288 = ASSERT(n_ >= 0) go n_ ""
289 where
290 go n cs | n < 62
291 = let !c = chooseChar62 n in c : cs
292 | otherwise
293 = go q (c : cs) where (q, r) = quotRem n 62
294 !c = chooseChar62 r
295
296 chooseChar62 :: Int -> Char
297 {-# INLINE chooseChar62 #-}
298 chooseChar62 (I# n) = C# (indexCharOffAddr# chars62 n)
299 chars62 = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"#
300
301 {-
302 ************************************************************************
303 * *
304 \subsection[Uniques-prelude]{@Uniques@ for wired-in Prelude things}
305 * *
306 ************************************************************************
307
308 Allocation of unique supply characters:
309 v,t,u : for renumbering value-, type- and usage- vars.
310 B: builtin
311 C-E: pseudo uniques (used in native-code generator)
312 X: uniques derived by deriveUnique
313 _: unifiable tyvars (above)
314 0-9: prelude things below
315 (no numbers left any more..)
316 :: (prelude) parallel array data constructors
317
318 other a-z: lower case chars for unique supplies. Used so far:
319
320 d desugarer
321 f AbsC flattener
322 g SimplStg
323 n Native codegen
324 r Hsc name cache
325 s simplifier
326 -}
327
328 mkAlphaTyVarUnique :: Int -> Unique
329 mkPreludeClassUnique :: Int -> Unique
330 mkPreludeTyConUnique :: Int -> Unique
331 mkTupleTyConUnique :: Boxity -> Arity -> Unique
332 mkCTupleTyConUnique :: Arity -> Unique
333 mkPreludeDataConUnique :: Arity -> Unique
334 mkTupleDataConUnique :: Boxity -> Arity -> Unique
335 mkPrimOpIdUnique :: Int -> Unique
336 mkPreludeMiscIdUnique :: Int -> Unique
337 mkPArrDataConUnique :: Int -> Unique
338 mkCoVarUnique :: Int -> Unique
339
340 mkAlphaTyVarUnique i = mkUnique '1' i
341 mkCoVarUnique i = mkUnique 'g' i
342 mkPreludeClassUnique i = mkUnique '2' i
343
344 --------------------------------------------------
345 -- Wired-in type constructor keys occupy *two* slots:
346 -- * u: the TyCon itself
347 -- * u+1: the TyConRepName of the TyCon
348 mkPreludeTyConUnique i = mkUnique '3' (2*i)
349 mkTupleTyConUnique Boxed a = mkUnique '4' (2*a)
350 mkTupleTyConUnique Unboxed a = mkUnique '5' (2*a)
351 mkCTupleTyConUnique a = mkUnique 'k' (2*a)
352
353 tyConRepNameUnique :: Unique -> Unique
354 tyConRepNameUnique u = incrUnique u
355
356 -- Data constructor keys occupy *two* slots. The first is used for the
357 -- data constructor itself and its wrapper function (the function that
358 -- evaluates arguments as necessary and calls the worker). The second is
359 -- used for the worker function (the function that builds the constructor
360 -- representation).
361
362 --------------------------------------------------
363 -- Wired-in data constructor keys occupy *three* slots:
364 -- * u: the DataCon itself
365 -- * u+1: its worker Id
366 -- * u+2: the TyConRepName of the promoted TyCon
367 -- Prelude data constructors are too simple to need wrappers.
368
369 mkPreludeDataConUnique i = mkUnique '6' (3*i) -- Must be alphabetic
370 mkTupleDataConUnique Boxed a = mkUnique '7' (3*a) -- ditto (*may* be used in C labels)
371 mkTupleDataConUnique Unboxed a = mkUnique '8' (3*a)
372
373 --------------------------------------------------
374 -- Sum arities start from 2. A sum of arity N has N data constructors, so it
375 -- occupies N+1 slots: 1 TyCon + N DataCons.
376 --
377 -- So arity 2 sum takes uniques 0 (tycon), 1, 2 (2 data cons)
378 -- arity 3 sum takes uniques 3 (tycon), 4, 5, 6 (3 data cons)
379 -- etc.
380
381 mkSumTyConUnique :: Arity -> Unique
382 mkSumTyConUnique arity = mkUnique 'z' (sumUniqsOccupied arity)
383
384 mkSumDataConUnique :: ConTagZ -> Arity -> Unique
385 mkSumDataConUnique alt arity
386 | alt >= arity
387 = panic ("mkSumDataConUnique: " ++ show alt ++ " >= " ++ show arity)
388 | otherwise
389 = mkUnique 'z' (sumUniqsOccupied arity + alt + 1 {- skip the tycon -})
390
391 -- How many unique slots occupied by sum types (including constructors) up to
392 -- the given arity?
393 sumUniqsOccupied :: Arity -> Int
394 sumUniqsOccupied arity
395 = ASSERT(arity >= 2)
396 -- 3 + 4 + ... + arity
397 ((arity * (arity + 1)) `div` 2) - 3
398 {-# INLINE sumUniqsOccupied #-}
399
400 --------------------------------------------------
401 dataConRepNameUnique, dataConWorkerUnique :: Unique -> Unique
402 dataConWorkerUnique u = incrUnique u
403 dataConRepNameUnique u = stepUnique u 2
404
405 --------------------------------------------------
406 mkPrimOpIdUnique op = mkUnique '9' op
407 mkPreludeMiscIdUnique i = mkUnique '0' i
408
409 -- No numbers left anymore, so I pick something different for the character tag
410 mkPArrDataConUnique a = mkUnique ':' (2*a)
411
412 -- The "tyvar uniques" print specially nicely: a, b, c, etc.
413 -- See pprUnique for details
414
415 initTyVarUnique :: Unique
416 initTyVarUnique = mkUnique 't' 0
417
418 mkPseudoUniqueD, mkPseudoUniqueE, mkPseudoUniqueH,
419 mkBuiltinUnique :: Int -> Unique
420
421 mkBuiltinUnique i = mkUnique 'B' i
422 mkPseudoUniqueD i = mkUnique 'D' i -- used in NCG for getUnique on RealRegs
423 mkPseudoUniqueE i = mkUnique 'E' i -- used in NCG spiller to create spill VirtualRegs
424 mkPseudoUniqueH i = mkUnique 'H' i -- used in NCG spiller to create spill VirtualRegs
425
426 mkRegSingleUnique, mkRegPairUnique, mkRegSubUnique, mkRegClassUnique :: Int -> Unique
427 mkRegSingleUnique = mkUnique 'R'
428 mkRegSubUnique = mkUnique 'S'
429 mkRegPairUnique = mkUnique 'P'
430 mkRegClassUnique = mkUnique 'L'
431
432 mkCostCentreUnique :: Int -> Unique
433 mkCostCentreUnique = mkUnique 'C'
434
435 mkVarOccUnique, mkDataOccUnique, mkTvOccUnique, mkTcOccUnique :: FastString -> Unique
436 -- See Note [The Unique of an OccName] in OccName
437 mkVarOccUnique fs = mkUnique 'i' (uniqueOfFS fs)
438 mkDataOccUnique fs = mkUnique 'd' (uniqueOfFS fs)
439 mkTvOccUnique fs = mkUnique 'v' (uniqueOfFS fs)
440 mkTcOccUnique fs = mkUnique 'c' (uniqueOfFS fs)