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(..))
45 import PprCore ( {- instances -} )
48 data ArrayUsage = Prim | NonPrim | Array
49 | PolyExpr (Id -> Maybe (ArrayUsage -> ArrayUsage))
50 | PolyFun (ArrayUsage -> ArrayUsage)
53 arrUsage:: CoreExpr -> ArrayUsage
54 arrUsage (Var id) = varArrayUsage id
55 arrUsage (Lit lit) = litArrayUsage lit
56 arrUsage (App expr1 expr2) =
63 (PolyFun f, _) -> f arr2
66 arrUsage (Lam b expr) =
69 arrUsage (Let (NonRec b expr1) expr2) =
70 arrUsage (App (Lam b expr2) expr1)
72 arrUsage (Let (Rec bnds) expr) =
74 t1 = foldr combineArrayUsage Prim (map bindType bnds)
76 in if isArrayUsage t1 then Array else t2
78 arrUsage (Case expr b _ alts) =
81 t2 = scanType (map (arrUsage . (\ (_,_,x) -> x)) alts)
84 arrUsage (Note n expr) =
90 -- not quite sure this is right
91 arrUsage (Cast expr co) =
98 in case (bT, exprT) of
102 scanType:: [ArrayUsage] -> ArrayUsage
104 scanType (Array:ts) = Array
105 scanType (_:ts) = scanType ts
109 -- the code expression represents a built-in function which generates
111 isArrayGen:: CoreExpr -> Bool
113 panic "PArrAnal: isArrayGen: not yet implemented"
115 isArrayCon:: CoreExpr -> Bool
117 panic "PArrAnal: isArrayCon: not yet implemented"
119 markScalarExprs:: [CoreBind] -> [CoreBind]
121 panic "PArrAnal.markScalarExprs: not implemented yet"
124 varArrayUsage:: Id -> ArrayUsage
126 panic "PArrAnal.varArrayUsage: not yet implented"
128 litArrayUsage:: Literal -> ArrayUsage
130 panic "PArrAnal.litArrayUsage: not yet implented"
133 typeArrayUsage:: Type -> ArrayUsage
134 typeArrayUsage (TyVarTy tvar) =
135 PolyExpr (tIdFun tvar)
136 typeArrayUsage (AppTy _ _) =
137 panic "PArrAnal.typeArrayUsage: AppTy case not yet implemented"
138 typeArrayUsage (TyConApp tc tcargs) =
140 tcargsAU = map typeArrayUsage tcargs
141 tcCombine = foldr combineArrayUsage Prim tcargsAU
143 typeArrayUsage t@(PredTy _) =
144 pprPanic "PArrAnal.typeArrayUsage: encountered 'PredType - shouldn't be here!"
148 combineArrayUsage:: ArrayUsage -> ArrayUsage -> ArrayUsage
149 combineArrayUsage Array _ = Array
150 combineArrayUsage _ Array = Array
151 combineArrayUsage (PolyExpr f1) (PolyExpr f2) =
159 case (f1lookup, f2lookup) of
160 (Nothing, _) -> f2lookup
161 (_, Nothing) -> f1lookup
162 (Just f1', Just f2') -> Just ( \e -> (combineArrayUsage (f1' e) (f2' e)))
163 combineArrayUsage (PolyFun f) (PolyExpr g) =
164 panic ("PArrAnal.typeArrayUsage: PolyFun as argument in data" ++
165 " constructor - should not (?) happen\n")
166 combineArrayUsage (PolyExpr g) (PolyFun f) =
167 panic ("PArrAnal.typeArrayUsage: PolyFun as argument in data" ++
168 " constructor - should not (?) happen\n")
169 combineArrayUsage NonPrim _ = NonPrim
170 combineArrayUsage _ NonPrim = NonPrim
171 combineArrayUsage Prim Prim = Prim
174 isArrayUsage:: ArrayUsage -> Bool
175 isArrayUsage Array = True
176 isArrayUsage _ = False
178 -- Functions to serve as arguments for PolyExpr
179 -- ---------------------------------------------
181 tIdFun:: Var -> Var -> Maybe (ArrayUsage -> ArrayUsage)
188 -- Functions to serve as argument for PolyFun
189 -- -------------------------------------------
191 auId:: ArrayUsage -> ArrayUsage
194 auCon:: ArrayUsage -> ArrayUsage
196 auCon (PolyExpr f) = PolyExpr f'
197 where f' v = case f v of
199 Just g -> Just ( \e -> (auCon (g e)))
200 auCon (PolyFun f) = PolyFun (auCon . f)
203 -- traversal of Core expressions
204 -- -----------------------------