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