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
79 arrUsage (Case expr b _ alts) =
82 t2 = scanType (map (arrUsage . (\ (_,_,x) -> x)) alts)
85 arrUsage (Note n expr) =
95 in case (bT, exprT) of
99 scanType:: [ArrayUsage] -> ArrayUsage
101 scanType (Array:ts) = Array
102 scanType (_:ts) = scanType ts
106 -- the code expression represents a built-in function which generates
108 isArrayGen:: CoreExpr -> Bool
110 panic "PArrAnal: isArrayGen: not yet implemented"
112 isArrayCon:: CoreExpr -> Bool
114 panic "PArrAnal: isArrayCon: not yet implemented"
116 markScalarExprs:: [CoreBind] -> [CoreBind]
118 panic "PArrAnal.markScalarExprs: not implemented yet"
121 varArrayUsage:: Id -> ArrayUsage
123 panic "PArrAnal.varArrayUsage: not yet implented"
125 litArrayUsage:: Literal -> ArrayUsage
127 panic "PArrAnal.litArrayUsage: not yet implented"
130 typeArrayUsage:: Type -> ArrayUsage
131 typeArrayUsage (TyVarTy tvar) =
132 PolyExpr (tIdFun tvar)
133 typeArrayUsage (AppTy _ _) =
134 panic "PArrAnal.typeArrayUsage: AppTy case not yet implemented"
135 typeArrayUsage (TyConApp tc tcargs) =
137 tcargsAU = map typeArrayUsage tcargs
138 tcCombine = foldr combineArrayUsage Prim tcargsAU
140 typeArrayUsage t@(PredTy _) =
141 pprPanic "PArrAnal.typeArrayUsage: encountered 'PredType - shouldn't be here!"
145 combineArrayUsage:: ArrayUsage -> ArrayUsage -> ArrayUsage
146 combineArrayUsage Array _ = Array
147 combineArrayUsage _ Array = Array
148 combineArrayUsage (PolyExpr f1) (PolyExpr f2) =
156 case (f1lookup, f2lookup) of
157 (Nothing, _) -> f2lookup
158 (_, Nothing) -> f1lookup
159 (Just f1', Just f2') -> Just ( \e -> (combineArrayUsage (f1' e) (f2' e)))
160 combineArrayUsage (PolyFun f) (PolyExpr g) =
161 panic ("PArrAnal.typeArrayUsage: PolyFun as argument in data" ++
162 " constructor - should not (?) happen\n")
163 combineArrayUsage (PolyExpr g) (PolyFun f) =
164 panic ("PArrAnal.typeArrayUsage: PolyFun as argument in data" ++
165 " constructor - should not (?) happen\n")
166 combineArrayUsage NonPrim _ = NonPrim
167 combineArrayUsage _ NonPrim = NonPrim
168 combineArrayUsage Prim Prim = Prim
171 isArrayUsage:: ArrayUsage -> Bool
172 isArrayUsage Array = True
173 isArrayUsage _ = False
175 -- Functions to serve as arguments for PolyExpr
176 -- ---------------------------------------------
178 tIdFun:: Var -> Var -> Maybe (ArrayUsage -> ArrayUsage)
185 -- Functions to serve as argument for PolyFun
186 -- -------------------------------------------
188 auId:: ArrayUsage -> ArrayUsage
191 auCon:: ArrayUsage -> ArrayUsage
193 auCon (PolyExpr f) = PolyExpr f'
194 where f' v = case f v of
196 Just g -> Just ( \e -> (auCon (g e)))
197 auCon (PolyFun f) = PolyFun (auCon . f)
200 -- traversal of Core expressions
201 -- -----------------------------