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