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