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