a1215fd8c0a370aac16f55df63af899c342ccec7
[ghc.git] / compiler / vectorise / Vectorise / Type / Classify.hs
1 -- Extract from a list of type constructors those (1) which need to be vectorised and (2) those
2 -- that could be, but need not be vectorised (as a scalar representation is sufficient and more
3 -- efficient). The type constructors that cannot be vectorised will be dropped.
4 --
5 -- A type constructor will only be vectorised if it is
6 --
7 -- (1) a data type constructor, with vanilla data constructors (i.e., data constructors admitted by
8 -- Haskell 98) and
9 -- (2) at least one of the type constructors that appears in its definition is also vectorised.
10 --
11 -- If (1) is met, but not (2), the type constructor may appear in vectorised code, but there is no
12 -- need to vectorise that type constructor itself. This holds, for example, for all enumeration
13 -- types. As '([::])' is being vectorised, any type constructor whose definition involves
14 -- '([::])', either directly or indirectly, will be vectorised.
15
16 module Vectorise.Type.Classify
17 ( classifyTyCons
18 )
19 where
20
21 import NameSet
22 import UniqSet
23 import UniqFM
24 import DataCon
25 import TyCon
26 import TyCoRep
27 import qualified Type
28 import PrelNames
29 import Digraph
30
31 -- |From a list of type constructors, extract those that can be vectorised, returning them in two
32 -- sets, where the first result list /must be/ vectorised and the second result list /need not be/
33 -- vectorised. The third result list are those type constructors that we cannot convert (either
34 -- because they use language extensions or because they dependent on type constructors for which
35 -- no vectorised version is available).
36 --
37 -- NB: In order to be able to vectorise a type constructor, we require members of the depending set
38 -- (i.e., those type constructors that the current one depends on) to be vectorised only if they
39 -- are also parallel (i.e., appear in the second argument to the function).
40 --
41 -- The first argument determines the /conversion status/ of external type constructors as follows:
42 --
43 -- * tycons which have converted versions are mapped to 'True'
44 -- * tycons which are not changed by vectorisation are mapped to 'False'
45 -- * tycons which haven't been converted (because they can't or weren't vectorised) are not
46 -- elements of the map
47 --
48 classifyTyCons :: UniqFM Bool -- ^type constructor vectorisation status
49 -> NameSet -- ^tycons involving parallel arrays
50 -> [TyCon] -- ^type constructors that need to be classified
51 -> ( [TyCon] -- to be converted
52 , [TyCon] -- need not be converted (but could be)
53 , [TyCon] -- involve parallel arrays (whether converted or not)
54 , [TyCon] -- can't be converted
55 )
56 classifyTyCons convStatus parTyCons tcs = classify [] [] [] [] convStatus parTyCons (tyConGroups tcs)
57 where
58 classify conv keep par novect _ _ [] = (conv, keep, par, novect)
59 classify conv keep par novect cs pts ((tcs, ds) : rs)
60 | can_convert && must_convert
61 = classify (tcs ++ conv) keep (par ++ tcs_par) novect (cs `addListToUFM` [(tc, True) | tc <- tcs]) pts' rs
62 | can_convert
63 = classify conv (tcs ++ keep) (par ++ tcs_par) novect (cs `addListToUFM` [(tc, False) | tc <- tcs]) pts' rs
64 | otherwise
65 = classify conv keep (par ++ tcs_par) (tcs ++ novect) cs pts' rs
66 where
67 refs = ds `delListFromUniqSet` tcs
68
69 -- the tycons that directly or indirectly depend on parallel arrays
70 tcs_par | uniqSetAny ((`elemNameSet` parTyCons) . tyConName) refs = tcs
71 | otherwise = []
72
73 pts' = pts `extendNameSetList` map tyConName tcs_par
74
75 can_convert = (isEmptyUniqSet (filterUniqSet ((`elemNameSet` pts) . tyConName) (refs `uniqSetMinusUFM` cs))
76 && all convertable tcs)
77 || isShowClass tcs
78 must_convert = anyUFM id (intersectUFM_C const cs (getUniqSet refs))
79 && (not . isShowClass $ tcs)
80
81 -- We currently admit Haskell 2011-style data and newtype declarations as well as type
82 -- constructors representing classes.
83 convertable tc
84 = (isDataTyCon tc || isNewTyCon tc) && all isVanillaDataCon (tyConDataCons tc)
85 || isClassTyCon tc
86
87 -- !!!FIXME: currently we allow 'Show' in vectorised code without actually providing a
88 -- vectorised definition (to be able to vectorise 'Num')
89 isShowClass [tc] = tyConName tc == showClassName
90 isShowClass _ = False
91
92 -- Used to group type constructors into mutually dependent groups.
93 --
94 type TyConGroup = ([TyCon], UniqSet TyCon)
95
96 -- Compute mutually recursive groups of tycons in topological order.
97 --
98 tyConGroups :: [TyCon] -> [TyConGroup]
99 tyConGroups tcs = map mk_grp (stronglyConnCompFromEdgedVerticesUniq edges)
100 where
101 edges = [((tc, ds), tc, nonDetEltsUniqSet ds) | tc <- tcs
102 , let ds = tyConsOfTyCon tc]
103 -- It's OK to use nonDetEltsUniqSet here as
104 -- stronglyConnCompFromEdgedVertices is still deterministic even
105 -- if the edges are in nondeterministic order as explained in
106 -- Note [Deterministic SCC] in Digraph.
107
108 mk_grp (AcyclicSCC (tc, ds)) = ([tc], ds)
109 mk_grp (CyclicSCC els) = (tcs, unionManyUniqSets dss)
110 where
111 (tcs, dss) = unzip els
112
113 -- |Collect the set of TyCons used by the representation of some data type.
114 --
115 tyConsOfTyCon :: TyCon -> UniqSet TyCon
116 tyConsOfTyCon = tyConsOfTypes . concatMap dataConRepArgTys . tyConDataCons
117
118 -- |Collect the set of TyCons that occur in these types.
119 --
120 tyConsOfTypes :: [Type] -> UniqSet TyCon
121 tyConsOfTypes = unionManyUniqSets . map tyConsOfType
122
123 -- |Collect the set of TyCons that occur in this type.
124 --
125 tyConsOfType :: Type -> UniqSet TyCon
126 tyConsOfType ty = filterUniqSet not_tuple_or_unlifted $ Type.tyConsOfType ty
127 where not_tuple_or_unlifted tc = not (isUnliftedTyCon tc || isTupleTyCon tc)
128