1{-# LANGUAGE CPP #-} 2 3-- | This is where we define a mapping from Uniques to their associated 4-- known-key Names for things associated with tuples and sums. We use this 5-- mapping while deserializing known-key Names in interface file symbol tables, 6-- which are encoded as their Unique. See Note [Symbol table representation of 7-- names] for details. 8-- 9 10module GHC.Builtin.Uniques 11 ( -- * Looking up known-key names 12 knownUniqueName 13 14 -- * Getting the 'Unique's of 'Name's 15 -- ** Anonymous sums 16 , mkSumTyConUnique 17 , mkSumDataConUnique 18 -- ** Tuples 19 -- *** Vanilla 20 , mkTupleTyConUnique 21 , mkTupleDataConUnique 22 -- *** Constraint 23 , mkCTupleTyConUnique 24 , mkCTupleDataConUnique 25 , mkCTupleSelIdUnique 26 27 -- ** Making built-in uniques 28 , mkAlphaTyVarUnique 29 , mkPrimOpIdUnique, mkPrimOpWrapperUnique 30 , mkPreludeMiscIdUnique, mkPreludeDataConUnique 31 , mkPreludeTyConUnique, mkPreludeClassUnique 32 , mkCoVarUnique 33 34 , mkVarOccUnique, mkDataOccUnique, mkTvOccUnique, mkTcOccUnique 35 , mkRegSingleUnique, mkRegPairUnique, mkRegClassUnique, mkRegSubUnique 36 , mkCostCentreUnique 37 38 , mkBuiltinUnique 39 , mkPseudoUniqueD 40 , mkPseudoUniqueE 41 , mkPseudoUniqueH 42 43 -- ** Deriving uniquesc 44 -- *** From TyCon name uniques 45 , tyConRepNameUnique 46 -- *** From DataCon name uniques 47 , dataConWorkerUnique, dataConTyRepNameUnique 48 49 , initTyVarUnique 50 , initExitJoinUnique 51 52 ) where 53 54#include "GhclibHsVersions.h" 55 56import GHC.Prelude 57 58import {-# SOURCE #-} GHC.Builtin.Types 59import {-# SOURCE #-} GHC.Core.TyCon 60import {-# SOURCE #-} GHC.Core.DataCon 61import {-# SOURCE #-} GHC.Types.Id 62import {-# SOURCE #-} GHC.Types.Name 63import GHC.Types.Basic 64import GHC.Types.Unique 65import GHC.Data.FastString 66 67import GHC.Utils.Outputable 68import GHC.Utils.Misc 69import GHC.Utils.Panic 70 71import Data.Maybe 72 73-- | Get the 'Name' associated with a known-key 'Unique'. 74knownUniqueName :: Unique -> Maybe Name 75knownUniqueName u = 76 case tag of 77 'z' -> Just $ getUnboxedSumName n 78 '4' -> Just $ getTupleTyConName Boxed n 79 '5' -> Just $ getTupleTyConName Unboxed n 80 '7' -> Just $ getTupleDataConName Boxed n 81 '8' -> Just $ getTupleDataConName Unboxed n 82 'j' -> Just $ getCTupleSelIdName n 83 'k' -> Just $ getCTupleTyConName n 84 'm' -> Just $ getCTupleDataConName n 85 _ -> Nothing 86 where 87 (tag, n) = unpkUnique u 88 89{- 90Note [Unique layout for unboxed sums] 91~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 92 93Sum arities start from 2. The encoding is a bit funny: we break up the 94integral part into bitfields for the arity, an alternative index (which is 95taken to be 0xfc in the case of the TyCon), and, in the case of a datacon, a 96tag (used to identify the sum's TypeRep binding). 97 98This layout is chosen to remain compatible with the usual unique allocation 99for wired-in data constructors described in GHC.Types.Unique 100 101TyCon for sum of arity k: 102 00000000 kkkkkkkk 11111100 103 104TypeRep of TyCon for sum of arity k: 105 00000000 kkkkkkkk 11111101 106 107DataCon for sum of arity k and alternative n (zero-based): 108 00000000 kkkkkkkk nnnnnn00 109 110TypeRep for sum DataCon of arity k and alternative n (zero-based): 111 00000000 kkkkkkkk nnnnnn10 112-} 113 114mkSumTyConUnique :: Arity -> Unique 115mkSumTyConUnique arity = 116 ASSERT(arity < 0x3f) -- 0x3f since we only have 6 bits to encode the 117 -- alternative 118 mkUnique 'z' (arity `shiftL` 8 .|. 0xfc) 119 120mkSumDataConUnique :: ConTagZ -> Arity -> Unique 121mkSumDataConUnique alt arity 122 | alt >= arity 123 = panic ("mkSumDataConUnique: " ++ show alt ++ " >= " ++ show arity) 124 | otherwise 125 = mkUnique 'z' (arity `shiftL` 8 + alt `shiftL` 2) {- skip the tycon -} 126 127getUnboxedSumName :: Int -> Name 128getUnboxedSumName n 129 | n .&. 0xfc == 0xfc 130 = case tag of 131 0x0 -> tyConName $ sumTyCon arity 132 0x1 -> getRep $ sumTyCon arity 133 _ -> pprPanic "getUnboxedSumName: invalid tag" (ppr tag) 134 | tag == 0x0 135 = dataConName $ sumDataCon (alt + 1) arity 136 | tag == 0x1 137 = getName $ dataConWrapId $ sumDataCon (alt + 1) arity 138 | tag == 0x2 139 = getRep $ promoteDataCon $ sumDataCon (alt + 1) arity 140 | otherwise 141 = pprPanic "getUnboxedSumName" (ppr n) 142 where 143 arity = n `shiftR` 8 144 alt = (n .&. 0xfc) `shiftR` 2 145 tag = 0x3 .&. n 146 getRep tycon = 147 fromMaybe (pprPanic "getUnboxedSumName(getRep)" (ppr tycon)) 148 $ tyConRepName_maybe tycon 149 150-- Note [Uniques for tuple type and data constructors] 151-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 152-- 153-- Wired-in type constructor keys occupy *two* slots: 154-- * u: the TyCon itself 155-- * u+1: the TyConRepName of the TyCon 156-- 157-- Wired-in tuple data constructor keys occupy *three* slots: 158-- * u: the DataCon itself 159-- * u+1: its worker Id 160-- * u+2: the TyConRepName of the promoted TyCon 161 162{- 163Note [Unique layout for constraint tuple selectors] 164~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 165 166Constraint tuples, like boxed and unboxed tuples, have their type and data 167constructor Uniques wired in (see 168Note [Uniques for tuple type and data constructors]). Constraint tuples are 169somewhat more involved, however. For a boxed or unboxed n-tuple, we need: 170 171* A Unique for the type constructor, and 172* A Unique for the data constructor 173 174With a constraint n-tuple, however, we need: 175 176* A Unique for the type constructor, 177* A Unique for the data constructor, and 178* A Unique for each of the n superclass selectors 179 180To pick a concrete example (n = 2), the binary constraint tuple has a type 181constructor and data constructor (%,%) along with superclass selectors 182$p1(%,%) and $p2(%,%). 183 184Just as we wire in the Uniques for constraint tuple type constructors and data 185constructors, we wish to wire in the Uniques for the superclass selectors as 186well. Not only does this make everything consistent, it also avoids a 187compile-time performance penalty whenever GHC.Classes is loaded from an 188interface file. This is because GHC.Classes defines constraint tuples as class 189definitions, and if these classes weren't wired in, then loading GHC.Classes 190would also load every single constraint tuple type constructor, data 191constructor, and superclass selector. See #18635. 192 193We encode the Uniques for constraint tuple superclass selectors as follows. The 194integral part of the Unique is broken up into bitfields for the arity and the 195position of the superclass. Given a selector for a constraint tuple with 196arity n (zero-based) and position k (where 1 <= k <= n), its Unique will look 197like: 198 199 00000000 nnnnnnnn kkkkkkkk 200 201We can use bit-twiddling tricks to access the arity and position with 202cTupleSelIdArityBits and cTupleSelIdPosBitmask, respectively. 203 204This pattern bears a certain resemblance to the way that the Uniques for 205unboxed sums are encoded. This is because for a unboxed sum of arity n, there 206are n corresponding data constructors, each with an alternative position k. 207Similarly, for a constraint tuple of arity n, there are n corresponding 208superclass selectors. Reading Note [Unique layout for unboxed sums] will 209instill an appreciation for how the encoding for constraint tuple superclass 210selector Uniques takes inspiration from the encoding for unboxed sum Uniques. 211-} 212 213mkCTupleTyConUnique :: Arity -> Unique 214mkCTupleTyConUnique a = mkUnique 'k' (2*a) 215 216mkCTupleDataConUnique :: Arity -> Unique 217mkCTupleDataConUnique a = mkUnique 'm' (3*a) 218 219mkCTupleSelIdUnique :: ConTagZ -> Arity -> Unique 220mkCTupleSelIdUnique sc_pos arity 221 | sc_pos >= arity 222 = panic ("mkCTupleSelIdUnique: " ++ show sc_pos ++ " >= " ++ show arity) 223 | otherwise 224 = mkUnique 'j' (arity `shiftL` cTupleSelIdArityBits + sc_pos) 225 226getCTupleTyConName :: Int -> Name 227getCTupleTyConName n = 228 case n `divMod` 2 of 229 (arity, 0) -> cTupleTyConName arity 230 (arity, 1) -> mkPrelTyConRepName $ cTupleTyConName arity 231 _ -> panic "getCTupleTyConName: impossible" 232 233getCTupleDataConName :: Int -> Name 234getCTupleDataConName n = 235 case n `divMod` 3 of 236 (arity, 0) -> cTupleDataConName arity 237 (arity, 1) -> getName $ dataConWrapId $ cTupleDataCon arity 238 (arity, 2) -> mkPrelTyConRepName $ cTupleDataConName arity 239 _ -> panic "getCTupleDataConName: impossible" 240 241getCTupleSelIdName :: Int -> Name 242getCTupleSelIdName n = cTupleSelIdName (sc_pos + 1) arity 243 where 244 arity = n `shiftR` cTupleSelIdArityBits 245 sc_pos = n .&. cTupleSelIdPosBitmask 246 247-- Given the arity of a constraint tuple, this is the number of bits by which 248-- one must shift it to the left in order to encode the arity in the Unique 249-- of a superclass selector for that constraint tuple. Alternatively, given the 250-- Unique for a constraint tuple superclass selector, this is the number of 251-- bits by which one must shift it to the right to retrieve the arity of the 252-- constraint tuple. See Note [Unique layout for constraint tuple selectors]. 253cTupleSelIdArityBits :: Int 254cTupleSelIdArityBits = 8 255 256-- Given the Unique for a constraint tuple superclass selector, one can 257-- retrieve the position of the selector by ANDing this mask, which will 258-- clear all but the eight least significant bits. 259-- See Note [Unique layout for constraint tuple selectors]. 260cTupleSelIdPosBitmask :: Int 261cTupleSelIdPosBitmask = 0xff 262 263-------------------------------------------------- 264-- Normal tuples 265 266mkTupleDataConUnique :: Boxity -> Arity -> Unique 267mkTupleDataConUnique Boxed a = mkUnique '7' (3*a) -- may be used in C labels 268mkTupleDataConUnique Unboxed a = mkUnique '8' (3*a) 269 270mkTupleTyConUnique :: Boxity -> Arity -> Unique 271mkTupleTyConUnique Boxed a = mkUnique '4' (2*a) 272mkTupleTyConUnique Unboxed a = mkUnique '5' (2*a) 273 274getTupleTyConName :: Boxity -> Int -> Name 275getTupleTyConName boxity n = 276 case n `divMod` 2 of 277 (arity, 0) -> tyConName $ tupleTyCon boxity arity 278 (arity, 1) -> fromMaybe (panic "getTupleTyConName") 279 $ tyConRepName_maybe $ tupleTyCon boxity arity 280 _ -> panic "getTupleTyConName: impossible" 281 282getTupleDataConName :: Boxity -> Int -> Name 283getTupleDataConName boxity n = 284 case n `divMod` 3 of 285 (arity, 0) -> dataConName $ tupleDataCon boxity arity 286 (arity, 1) -> idName $ dataConWorkId $ tupleDataCon boxity arity 287 (arity, 2) -> fromMaybe (panic "getTupleDataCon") 288 $ tyConRepName_maybe $ promotedTupleDataCon boxity arity 289 _ -> panic "getTupleDataConName: impossible" 290 291{- 292Note [Uniques for wired-in prelude things and known masks] 293~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 294Allocation of unique supply characters: 295 v,t,u : for renumbering value-, type- and usage- vars. 296 B: builtin 297 C-E: pseudo uniques (used in native-code generator) 298 I: GHCi evaluation 299 X: uniques from mkLocalUnique 300 _: unifiable tyvars (above) 301 0-9: prelude things below 302 (no numbers left any more..) 303 :: (prelude) parallel array data constructors 304 305 other a-z: lower case chars for unique supplies. Used so far: 306 307 a TypeChecking? 308 c StgToCmm/Renamer 309 d desugarer 310 f AbsC flattener 311 g SimplStg 312 i TypeChecking interface files 313 j constraint tuple superclass selectors 314 k constraint tuple tycons 315 m constraint tuple datacons 316 n Native/LLVM codegen 317 r Hsc name cache 318 s simplifier 319 u Cmm pipeline 320 y GHCi bytecode generator 321 z anonymous sums 322-} 323 324mkAlphaTyVarUnique :: Int -> Unique 325mkPreludeClassUnique :: Int -> Unique 326mkPrimOpIdUnique :: Int -> Unique 327-- See Note [Primop wrappers] in GHC.Builtin.PrimOps. 328mkPrimOpWrapperUnique :: Int -> Unique 329mkPreludeMiscIdUnique :: Int -> Unique 330mkCoVarUnique :: Int -> Unique 331 332mkAlphaTyVarUnique i = mkUnique '1' i 333mkCoVarUnique i = mkUnique 'g' i 334mkPreludeClassUnique i = mkUnique '2' i 335 336-------------------------------------------------- 337mkPrimOpIdUnique op = mkUnique '9' (2*op) 338mkPrimOpWrapperUnique op = mkUnique '9' (2*op+1) 339mkPreludeMiscIdUnique i = mkUnique '0' i 340 341-- The "tyvar uniques" print specially nicely: a, b, c, etc. 342-- See pprUnique for details 343 344initTyVarUnique :: Unique 345initTyVarUnique = mkUnique 't' 0 346 347mkPseudoUniqueD, mkPseudoUniqueE, mkPseudoUniqueH, 348 mkBuiltinUnique :: Int -> Unique 349 350mkBuiltinUnique i = mkUnique 'B' i 351mkPseudoUniqueD i = mkUnique 'D' i -- used in NCG for getUnique on RealRegs 352mkPseudoUniqueE i = mkUnique 'E' i -- used in NCG spiller to create spill VirtualRegs 353mkPseudoUniqueH i = mkUnique 'H' i -- used in NCG spiller to create spill VirtualRegs 354 355mkRegSingleUnique, mkRegPairUnique, mkRegSubUnique, mkRegClassUnique :: Int -> Unique 356mkRegSingleUnique = mkUnique 'R' 357mkRegSubUnique = mkUnique 'S' 358mkRegPairUnique = mkUnique 'P' 359mkRegClassUnique = mkUnique 'L' 360 361mkCostCentreUnique :: Int -> Unique 362mkCostCentreUnique = mkUnique 'C' 363 364mkVarOccUnique, mkDataOccUnique, mkTvOccUnique, mkTcOccUnique :: FastString -> Unique 365-- See Note [The Unique of an OccName] in GHC.Types.Name.Occurrence 366mkVarOccUnique fs = mkUnique 'i' (uniqueOfFS fs) 367mkDataOccUnique fs = mkUnique 'd' (uniqueOfFS fs) 368mkTvOccUnique fs = mkUnique 'v' (uniqueOfFS fs) 369mkTcOccUnique fs = mkUnique 'c' (uniqueOfFS fs) 370 371initExitJoinUnique :: Unique 372initExitJoinUnique = mkUnique 's' 0 373 374 375-------------------------------------------------- 376-- Wired-in type constructor keys occupy *two* slots: 377-- * u: the TyCon itself 378-- * u+1: the TyConRepName of the TyCon 379 380mkPreludeTyConUnique :: Int -> Unique 381mkPreludeTyConUnique i = mkUnique '3' (2*i) 382 383tyConRepNameUnique :: Unique -> Unique 384tyConRepNameUnique u = incrUnique u 385 386-------------------------------------------------- 387-- Wired-in data constructor keys occupy *three* slots: 388-- * u: the DataCon itself 389-- * u+1: its worker Id 390-- * u+2: the TyConRepName of the promoted TyCon 391-- Prelude data constructors are too simple to need wrappers. 392 393mkPreludeDataConUnique :: Arity -> Unique 394mkPreludeDataConUnique i = mkUnique '6' (3*i) -- Must be alphabetic 395 396-------------------------------------------------- 397dataConTyRepNameUnique, dataConWorkerUnique :: Unique -> Unique 398dataConWorkerUnique u = incrUnique u 399dataConTyRepNameUnique u = stepUnique u 2 400