3 -- Copyright (c) 2002 Manuel M T Chakravarty & Gabriele Keller
5 -- Analysis phase for an optimised flattening transformation
7 --- DESCRIPTION ---------------------------------------------------------------
9 -- This module implements an analysis phase that identifies Core expressions
10 -- that need not be transformed during flattening. The expressions when
11 -- executed in a parallel context are implemented as an iteration over the
12 -- original scalar computation, instead of vectorising the computation. This
13 -- usually improves efficiency by increasing locality and also reduces code
16 --- DOCU ----------------------------------------------------------------------
18 -- Language: Haskell 98 with C preprocessor
20 -- Analyse the expression and annotate each simple subexpression accordingly.
22 -- The result of the analysis is stored in a new field in IdInfo (has yet to
25 -- A simple expression is any expression which is not a function, not of
26 -- recursive type and does not contain a value of PArray type. Polymorphic
27 -- variables are simple expressions even though they might be instantiated to
28 -- a parray value or function.
30 --- TODO ----------------------------------------------------------------------
34 markScalarExprs -- :: [CoreBind] -> [CoreBind]
38 import Outputable (pprPanic, ppr)
39 import CoreSyn (CoreBind)
41 import TypeRep (Type(..))
42 import Var (Var(..),Id)
43 import Literal (Literal)
44 import CoreSyn (Expr(..),CoreExpr,Bind(..))
47 data ArrayUsage = Prim | NonPrim | Array
48 | PolyExpr (Id -> Maybe (ArrayUsage -> ArrayUsage))
49 | PolyFun (ArrayUsage -> ArrayUsage)
52 arrUsage:: CoreExpr -> ArrayUsage
53 arrUsage (Var id) = varArrayUsage id
54 arrUsage (Lit lit) = litArrayUsage lit
55 arrUsage (App expr1 expr2) =
62 (PolyFun f, _) -> f arr2
65 arrUsage (Lam b expr) =
68 arrUsage (Let (NonRec b expr1) expr2) =
69 arrUsage (App (Lam b expr2) expr1)
71 arrUsage (Let (Rec bnds) expr) =
73 t1 = foldr combineArrayUsage Prim (map bindType bnds)
75 in if isArrayUsage t1 then Array else t2
77 arrUsage (Case expr b alts) =
80 t2 = scanType (map (arrUsage . (\ (_,_,x) -> x)) alts)
83 arrUsage (Note n expr) =
93 in case (bT, exprT) of
97 scanType:: [ArrayUsage] -> ArrayUsage
99 scanType (Array:ts) = Array
100 scanType (_:ts) = scanType ts
104 -- the code expression represents a built-in function which generates
106 isArrayGen:: CoreExpr -> Bool
108 panic "PArrAnal: isArrayGen: not yet implemented"
110 isArrayCon:: CoreExpr -> Bool
112 panic "PArrAnal: isArrayCon: not yet implemented"
114 markScalarExprs:: [CoreBind] -> [CoreBind]
116 panic "PArrAnal.markScalarExprs: not implemented yet"
119 varArrayUsage:: Id -> ArrayUsage
121 panic "PArrAnal.varArrayUsage: not yet implented"
123 litArrayUsage:: Literal -> ArrayUsage
125 panic "PArrAnal.litArrayUsage: not yet implented"
128 typeArrayUsage:: Type -> ArrayUsage
129 typeArrayUsage (TyVarTy tvar) =
130 PolyExpr (tIdFun tvar)
131 typeArrayUsage (AppTy _ _) =
132 panic "PArrAnal.typeArrayUsage: AppTy case not yet implemented"
133 typeArrayUsage (TyConApp tc tcargs) =
135 tcargsAU = map typeArrayUsage tcargs
136 tcCombine = foldr combineArrayUsage Prim tcargsAU
138 typeArrayUsage t@(SourceTy _) =
139 pprPanic "PArrAnal.typeArrayUsage: encountered 'SourceType - shouldn't be here!"
143 combineArrayUsage:: ArrayUsage -> ArrayUsage -> ArrayUsage
144 combineArrayUsage Array _ = Array
145 combineArrayUsage _ Array = Array
146 combineArrayUsage (PolyExpr f1) (PolyExpr f2) =
154 case (f1lookup, f2lookup) of
155 (Nothing, _) -> f2lookup
156 (_, Nothing) -> f1lookup
157 (Just f1', Just f2') -> Just ( \e -> (combineArrayUsage (f1' e) (f2' e)))
158 combineArrayUsage (PolyFun f) (PolyExpr g) =
159 panic ("PArrAnal.typeArrayUsage: PolyFun as argument in data" ++
160 " constructor - should not (?) happen\n")
161 combineArrayUsage (PolyExpr g) (PolyFun f) =
162 panic ("PArrAnal.typeArrayUsage: PolyFun as argument in data" ++
163 " constructor - should not (?) happen\n")
164 combineArrayUsage NonPrim _ = NonPrim
165 combineArrayUsage _ NonPrim = NonPrim
166 combineArrayUsage Prim Prim = Prim
169 isArrayUsage:: ArrayUsage -> Bool
170 isArrayUsage Array = True
171 isArrayUsage _ = False
173 -- Functions to serve as arguments for PolyExpr
174 -- ---------------------------------------------
176 tIdFun:: Var -> Var -> Maybe (ArrayUsage -> ArrayUsage)
183 -- Functions to serve as argument for PolyFun
184 -- -------------------------------------------
186 auId:: ArrayUsage -> ArrayUsage
189 auCon:: ArrayUsage -> ArrayUsage
191 auCon (PolyExpr f) = PolyExpr f'
192 where f' v = case f v of
194 Just g -> Just ( \e -> (auCon (g e)))
195 auCon (PolyFun f) = PolyFun (auCon . f)
198 -- traversal of Core expressions
199 -- -----------------------------