2 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1996
4 \section[CoreSyn]{A data type for the Haskell compiler midsection}
7 #include "HsVersions.h"
10 GenCoreBinding(..), GenCoreExpr(..),
11 GenCoreArg(..), GenCoreBinder(..), GenCoreCaseAlts(..),
12 GenCoreCaseDefault(..),
14 bindersOf, pairsFromCoreBinds, rhssOfBind,
16 mkGenApp, mkValApp, mkTyApp, mkUseApp,
18 mkValLam, mkTyLam, mkUseLam,
20 collectBinders, isValBinder, notValBinder,
22 collectArgs, isValArg, notValArg, numValArgs,
24 mkCoLetAny, mkCoLetNoUnboxed, mkCoLetUnboxedToCase,
25 mkCoLetsAny, mkCoLetsNoUnboxed, mkCoLetsUnboxedToCase,
26 mkCoLetrecAny, mkCoLetrecNoUnboxed,
30 -- Common type instantiation...
38 -- And not-so-common type instantiations...
39 TaggedCoreBinding(..),
43 TaggedCoreCaseAlts(..),
44 TaggedCoreCaseDefault(..),
46 SimplifiableCoreBinding(..),
47 SimplifiableCoreExpr(..),
48 SimplifiableCoreBinder(..),
49 SimplifiableCoreArg(..),
50 SimplifiableCoreCaseAlts(..),
51 SimplifiableCoreCaseDefault(..)
53 -- and to make the interface self-sufficient ...
59 import CostCentre ( showCostCentre, CostCentre )
60 import Id ( idType, GenId{-instance Eq-} )
61 import Type ( isUnboxedType )
62 import Usage ( UVar(..) )
63 import Util ( panic, assertPanic )
66 %************************************************************************
68 \subsection[CoreTopBinding_and_CoreBinding]{@CoreTopBinding@ and @GenCoreBinding@}
70 %************************************************************************
72 Core programs, bindings, expressions, etc., are parameterised with
73 respect to the information kept about binding and bound occurrences of
74 variables, called {\em binders} and {\em val_occ tyvar uvars}, respectively. [I
75 don't really like the pair of names; I prefer {\em binder} and {\em
76 bounder}. Or {\em binder} and {\em var}.]
78 A @GenCoreBinding@ is either a single non-recursive binding of a
79 ``binder'' to an expression, or a mutually-recursive blob of same.
81 data GenCoreBinding val_bdr val_occ tyvar uvar
82 = NonRec val_bdr (GenCoreExpr val_bdr val_occ tyvar uvar)
83 | Rec [(val_bdr, GenCoreExpr val_bdr val_occ tyvar uvar)]
87 bindersOf :: GenCoreBinding val_bdr val_occ tyvar uvar -> [val_bdr]
90 [GenCoreBinding val_bdr val_occ tyvar uvar] ->
91 [(val_bdr, GenCoreExpr val_bdr val_occ tyvar uvar)]
93 rhssOfBind :: GenCoreBinding val_bdr val_occ tyvar uvar -> [GenCoreExpr val_bdr val_occ tyvar uvar]
95 bindersOf (NonRec binder _) = [binder]
96 bindersOf (Rec pairs) = [binder | (binder, _) <- pairs]
98 pairsFromCoreBinds [] = []
99 pairsFromCoreBinds ((NonRec b e) : bs) = (b,e) : pairsFromCoreBinds bs
100 pairsFromCoreBinds ((Rec pairs) : bs) = pairs ++ pairsFromCoreBinds bs
102 rhssOfBind (NonRec _ rhs) = [rhs]
103 rhssOfBind (Rec pairs) = [rhs | (_,rhs) <- pairs]
106 %************************************************************************
108 \subsection[GenCoreExpr]{Core expressions: @GenCoreExpr@}
110 %************************************************************************
112 @GenCoreExpr@ is the heart of the ``core'' data types; it is
113 (more-or-less) boiled-down second-order polymorphic lambda calculus.
114 For types in the core world, we just keep using @Types@.
116 data GenCoreExpr val_bdr val_occ tyvar uvar
118 | Lit Literal -- literal constants
121 @Cons@ and @Prims@ are saturated constructor and primitive-op
122 applications (see the comment). Note: @Con@s are only set up by the
123 simplifier (and by the desugarer when it knows what it's doing). The
124 desugarer sets up constructors as applications of global @Vars@s.
127 | Con Id [GenCoreArg val_occ tyvar uvar]
128 -- Saturated constructor application:
129 -- The constructor is a function of the form:
130 -- /\ a1 -> ... /\ am -> \ b1 -> ... \ bn ->
131 -- <expr> where "/\" is a type lambda and "\" the
132 -- regular kind; there will be "m" Types and
133 -- "n" bindees in the Con args.
135 | Prim PrimOp [GenCoreArg val_occ tyvar uvar]
136 -- saturated primitive operation;
137 -- comment on Cons applies here, too.
140 Ye olde abstraction and application operators.
142 | Lam (GenCoreBinder val_bdr tyvar uvar)
143 (GenCoreExpr val_bdr val_occ tyvar uvar)
145 | App (GenCoreExpr val_bdr val_occ tyvar uvar)
146 (GenCoreArg val_occ tyvar uvar)
149 Case expressions (\tr{case <expr> of <List of alternatives>}): there
150 are really two flavours masquerading here---those for scrutinising
151 {\em algebraic} types and those for {\em primitive} types. Please see
152 under @GenCoreCaseAlts@.
154 | Case (GenCoreExpr val_bdr val_occ tyvar uvar)
155 (GenCoreCaseAlts val_bdr val_occ tyvar uvar)
158 A Core case expression \tr{case e of v -> ...} implies evaluation of
159 \tr{e}; it is not equivalent to \tr{let v = in ...} (as with a Haskell
162 Non-recursive @Lets@ only have one binding; having more than one
163 doesn't buy you much, and it is an easy way to mess up variable
166 | Let (GenCoreBinding val_bdr val_occ tyvar uvar)
167 (GenCoreExpr val_bdr val_occ tyvar uvar)
168 -- both recursive and non-.
169 -- The "GenCoreBinding" records that information
172 For cost centre scc expressions we introduce a new core construct
173 @SCC@ so transforming passes have to deal with it explicitly. The
174 alternative of using a new PrimativeOp may result in a bad
175 transformations of which we are unaware.
177 | SCC CostCentre -- label of scc
178 (GenCoreExpr val_bdr val_occ tyvar uvar) -- scc expression
182 %************************************************************************
184 \subsection{Core-constructing functions with checking}
186 %************************************************************************
188 When making @Lets@, we may want to take evasive action if the thing
189 being bound has unboxed type. We have different variants ...
191 @mkCoLet(s|rec)Any@ let-binds any binding, regardless of type
192 @mkCoLet(s|rec)NoUnboxed@ prohibits unboxed bindings
193 @mkCoLet(s)UnboxedToCase@ converts an unboxed binding to a case
194 (unboxed bindings in a letrec are still prohibited)
197 mkCoLetAny :: GenCoreBinding Id Id tyvar uvar
198 -> GenCoreExpr Id Id tyvar uvar
199 -> GenCoreExpr Id Id tyvar uvar
200 mkCoLetsAny :: [GenCoreBinding Id Id tyvar uvar] ->
201 GenCoreExpr Id Id tyvar uvar ->
202 GenCoreExpr Id Id tyvar uvar
204 mkCoLetrecAny :: [(val_bdr, GenCoreExpr val_bdr val_occ tyvar uvar)]
205 -> GenCoreExpr val_bdr val_occ tyvar uvar
206 -> GenCoreExpr val_bdr val_occ tyvar uvar
208 mkCoLetrecAny [] body = body
209 mkCoLetrecAny binds body = Let (Rec binds) body
211 mkCoLetsAny [] expr = expr
212 mkCoLetsAny binds expr = foldr mkCoLetAny expr binds
214 mkCoLetAny bind@(Rec binds) body = mkCoLetrecAny binds body
215 mkCoLetAny bind@(NonRec binder rhs) body
217 Var binder2 | binder == binder2
218 -> rhs -- hey, I have the rhs
224 --mkCoLetNoUnboxed ::
225 -- GenCoreBinding val_bdr val_occ tyvar uvar ->
226 -- GenCoreExpr val_bdr val_occ tyvar uvar ->
227 -- GenCoreExpr val_bdr val_occ tyvar uvar
229 mkCoLetNoUnboxed bind@(Rec binds) body
230 = mkCoLetrecNoUnboxed binds body
231 mkCoLetNoUnboxed bind@(NonRec binder rhs) body
232 = --ASSERT (not (isUnboxedType (idType binder)))
234 Var binder2 | binder == binder2
235 -> rhs -- hey, I have the rhs
239 mkCoLetsNoUnboxed [] expr = expr
240 mkCoLetsNoUnboxed binds expr = foldr mkCoLetNoUnboxed expr binds
242 --mkCoLetrecNoUnboxed :: [(Id, CoreExpr)] -- bindings
243 -- -> CoreExpr -- body
244 -- -> CoreExpr -- result
246 mkCoLetrecNoUnboxed [] body = body
247 mkCoLetrecNoUnboxed binds body
248 = ASSERT (all is_boxed_bind binds)
251 is_boxed_bind (binder, rhs)
252 = (not . isUnboxedType . idType) binder
256 --mkCoLetUnboxedToCase ::
257 -- GenCoreBinding val_bdr val_occ tyvar uvar ->
258 -- GenCoreExpr val_bdr val_occ tyvar uvar ->
259 -- GenCoreExpr val_bdr val_occ tyvar uvar
261 mkCoLetUnboxedToCase bind@(Rec binds) body
262 = mkCoLetrecNoUnboxed binds body
263 mkCoLetUnboxedToCase bind@(NonRec binder rhs) body
265 Var binder2 | binder == binder2
266 -> rhs -- hey, I have the rhs
268 -> if (not (isUnboxedType (idType binder))) then
269 Let bind body -- boxed...
271 Case rhs -- unboxed...
273 (BindDefault binder body))
275 mkCoLetsUnboxedToCase [] expr = expr
276 mkCoLetsUnboxedToCase binds expr = foldr mkCoLetUnboxedToCase expr binds
279 %************************************************************************
281 \subsection{Case alternatives in @GenCoreExpr@}
283 %************************************************************************
285 We have different kinds of @case@s, the differences being reflected in
286 the kinds of alternatives a case has. We maintain a distinction
287 between cases for scrutinising algebraic datatypes, as opposed to
288 primitive types. In both cases, we carry around a @TyCon@, as a
289 handle with which we can get info about the case (e.g., total number
290 of data constructors for this type).
298 Case e [ BindDefaultAlt x -> b ]
302 data GenCoreCaseAlts val_bdr val_occ tyvar uvar
303 = AlgAlts [(Id, -- alts: data constructor,
304 [val_bdr], -- constructor's parameters,
305 GenCoreExpr val_bdr val_occ tyvar uvar)] -- rhs.
306 (GenCoreCaseDefault val_bdr val_occ tyvar uvar)
308 | PrimAlts [(Literal, -- alts: unboxed literal,
309 GenCoreExpr val_bdr val_occ tyvar uvar)] -- rhs.
310 (GenCoreCaseDefault val_bdr val_occ tyvar uvar)
312 -- obvious things: if there are no alts in the list, then the default
313 -- can't be NoDefault.
315 data GenCoreCaseDefault val_bdr val_occ tyvar uvar
316 = NoDefault -- small con family: all
317 -- constructor accounted for
318 | BindDefault val_bdr -- form: var -> expr;
319 (GenCoreExpr val_bdr val_occ tyvar uvar) -- "val_bdr" may or may not
324 rhssOfAlts (AlgAlts alts deflt) = rhssOfDeflt deflt ++ [rhs | (_,_,rhs) <- alts]
325 rhssOfAlts (PrimAlts alts deflt) = rhssOfDeflt deflt ++ [rhs | (_,rhs) <- alts]
327 rhssOfDeflt NoDefault = []
328 rhssOfDeflt (BindDefault _ rhs) = [rhs]
331 %************************************************************************
333 \subsection{Core binders}
335 %************************************************************************
338 data GenCoreBinder val_bdr tyvar uvar
343 isValBinder (ValBinder _) = True
344 isValBinder _ = False
346 notValBinder = not . isValBinder
349 Clump Lams together if possible.
352 mkValLam :: [val_bdr]
353 -> GenCoreExpr val_bdr val_occ tyvar uvar
354 -> GenCoreExpr val_bdr val_occ tyvar uvar
356 -> GenCoreExpr val_bdr val_occ tyvar uvar
357 -> GenCoreExpr val_bdr val_occ tyvar uvar
359 -> GenCoreExpr val_bdr val_occ tyvar uvar
360 -> GenCoreExpr val_bdr val_occ tyvar uvar
362 mkValLam binders body = foldr (Lam . ValBinder) body binders
363 mkTyLam binders body = foldr (Lam . TyBinder) body binders
364 mkUseLam binders body = foldr (Lam . UsageBinder) body binders
366 mkLam :: [tyvar] -> [val_bdr] -- ToDo: could add a [uvar] arg...
367 -> GenCoreExpr val_bdr val_occ tyvar uvar
368 -> GenCoreExpr val_bdr val_occ tyvar uvar
370 mkLam tyvars valvars body
371 = mkTyLam tyvars (mkValLam valvars body)
374 We often want to strip off leading lambdas before getting down to
375 business. @collectBinders@ is your friend.
377 We expect (by convention) usage-, type-, and value- lambdas in that
382 GenCoreExpr val_bdr val_occ tyvar uvar ->
383 ([uvar], [tyvar], [val_bdr], GenCoreExpr val_bdr val_occ tyvar uvar)
388 usages (Lam (UsageBinder u) body) uacc = usages body (u:uacc)
390 = case (tyvars other []) of { (tacc, vacc, expr) ->
391 (reverse uacc, tacc, vacc, expr) }
393 tyvars (Lam (TyBinder t) body) tacc = tyvars body (t:tacc)
395 = ASSERT(not (usage_lambda other))
396 case (valvars other []) of { (vacc, expr) ->
397 (reverse tacc, vacc, expr) }
399 valvars (Lam (ValBinder v) body) vacc = valvars body (v:vacc)
401 = ASSERT(not (usage_lambda other))
402 ASSERT(not (tyvar_lambda other))
403 (reverse vacc, other)
405 ---------------------------------------
406 usage_lambda (Lam (UsageBinder _) _) = True
407 usage_lambda _ = False
409 tyvar_lambda (Lam (TyBinder _) _) = True
410 tyvar_lambda _ = False
413 %************************************************************************
415 \subsection{Core arguments (atoms)}
417 %************************************************************************
420 data GenCoreArg val_occ tyvar uvar
423 | TyArg (GenType tyvar uvar)
424 | UsageArg (GenUsage uvar)
427 General and specific forms:
429 mkGenApp :: GenCoreExpr val_bdr val_occ tyvar uvar
430 -> [GenCoreArg val_occ tyvar uvar]
431 -> GenCoreExpr val_bdr val_occ tyvar uvar
432 mkTyApp :: GenCoreExpr val_bdr val_occ tyvar uvar
433 -> [GenType tyvar uvar]
434 -> GenCoreExpr val_bdr val_occ tyvar uvar
435 mkUseApp :: GenCoreExpr val_bdr val_occ tyvar uvar
437 -> GenCoreExpr val_bdr val_occ tyvar uvar
438 mkValApp :: GenCoreExpr val_bdr val_occ tyvar uvar
439 -> [GenCoreArg val_occ tyvar uvar] -- but we ASSERT they are LitArg or VarArg
440 -> GenCoreExpr val_bdr val_occ tyvar uvar
442 mkGenApp f args = foldl App f args
443 mkTyApp f args = foldl (\ e a -> App e (TyArg a)) f args
444 mkUseApp f args = foldl (\ e a -> App e (UsageArg a)) f args
445 mkValApp f args = foldl (\ e a -> App e (is_Lit_or_Var a)) f args
451 = if isValArg a then a else panic "CoreSyn.mkValApps:not LitArg or VarArg"
454 isValArg (LitArg _) = True -- often used for sanity-checking
455 isValArg (VarArg _) = True
458 notValArg = not . isValArg -- exists only because it's a common use of isValArg
460 numValArgs as = length [ a | a <- as, isValArg a ] -- again, convenience
464 mkApp fun = mk_thing (mkGenApp fun)
465 mkCon con = mk_thing (Con con)
466 mkPrim op = mk_thing (Prim op)
468 mk_thing thing uses tys vals
469 = thing (map UsageArg uses ++ map TyArg tys ++ map is_Lit_or_Var vals)
472 @collectArgs@ takes an application expression, returning the function
473 and the arguments to which it is applied.
476 collectArgs :: GenCoreExpr val_bdr val_occ tyvar uvar
477 -> (GenCoreExpr val_bdr val_occ tyvar uvar,
479 [GenType tyvar uvar],
480 [GenCoreArg val_occ tyvar uvar]{-ValArgs-})
485 usages (App fun (UsageArg u)) uacc = usages fun (u:uacc)
487 = case (tyvars fun []) of { (expr, tacc, vacc) ->
488 (expr, uacc, tacc, vacc) }
490 tyvars (App fun (TyArg t)) tacc = tyvars fun (t:tacc)
492 = ASSERT(not (usage_app fun))
493 case (valvars fun []) of { (expr, vacc) ->
496 valvars (App fun v) vacc | isValArg v = valvars fun (v:vacc)
498 = ASSERT(not (usage_app fun))
499 ASSERT(not (ty_app fun))
502 ---------------------------------------
503 usage_app (App _ (UsageArg _)) = True
506 ty_app (App _ (TyArg _)) = True
510 %************************************************************************
512 \subsection{The main @Core*@ instantiation of the @GenCore*@ types}
514 %************************************************************************
517 type CoreBinding = GenCoreBinding Id Id TyVar UVar
518 type CoreExpr = GenCoreExpr Id Id TyVar UVar
519 type CoreBinder = GenCoreBinder Id TyVar UVar
520 type CoreArg = GenCoreArg Id TyVar UVar
522 type CoreCaseAlts = GenCoreCaseAlts Id Id TyVar UVar
523 type CoreCaseDefault = GenCoreCaseDefault Id Id TyVar UVar
526 %************************************************************************
528 \subsection{The @TaggedCore*@ instantiation of the @GenCore*@ types}
530 %************************************************************************
532 Binders are ``tagged'' with a \tr{t}:
534 type Tagged t = (Id, t)
536 type TaggedCoreBinding t = GenCoreBinding (Tagged t) Id TyVar UVar
537 type TaggedCoreExpr t = GenCoreExpr (Tagged t) Id TyVar UVar
538 type TaggedCoreBinder t = GenCoreBinder (Tagged t) TyVar UVar
539 type TaggedCoreArg t = GenCoreArg Id TyVar UVar
541 type TaggedCoreCaseAlts t = GenCoreCaseAlts (Tagged t) Id TyVar UVar
542 type TaggedCoreCaseDefault t = GenCoreCaseDefault (Tagged t) Id TyVar UVar
545 %************************************************************************
547 \subsection{The @SimplifiableCore*@ instantiation of the @GenCore*@ types}
549 %************************************************************************
551 Binders are tagged with @BinderInfo@:
553 type Simplifiable = (Id, BinderInfo)
555 type SimplifiableCoreBinding = GenCoreBinding Simplifiable Id TyVar UVar
556 type SimplifiableCoreExpr = GenCoreExpr Simplifiable Id TyVar UVar
557 type SimplifiableCoreBinder = GenCoreBinder Simplifiable TyVar UVar
558 type SimplifiableCoreArg = GenCoreArg Id TyVar UVar
560 type SimplifiableCoreCaseAlts = GenCoreCaseAlts Simplifiable Id TyVar UVar
561 type SimplifiableCoreCaseDefault = GenCoreCaseDefault Simplifiable Id TyVar UVar