X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=compiler%2FcoreSyn%2FCoreSyn.lhs;h=b7a859fa9d66ca615b65534bbf70febf6885b185;hb=635952097df211953c4bd0456b37eba64c485f60;hp=5c7cef9ac9b99116ffecf913643b0bcf965a47bc;hpb=c86161c5cf11de77e911fcb9e1e2bd1f8bd80b42;p=ghc-hetmet.git diff --git a/compiler/coreSyn/CoreSyn.lhs b/compiler/coreSyn/CoreSyn.lhs index 5c7cef9..b7a859f 100644 --- a/compiler/coreSyn/CoreSyn.lhs +++ b/compiler/coreSyn/CoreSyn.lhs @@ -4,6 +4,7 @@ % \begin{code} +{-# LANGUAGE DeriveDataTypeable #-} -- | CoreSyn holds all the main data types for use by for the Glasgow Haskell Compiler midsection module CoreSyn ( @@ -43,7 +44,7 @@ module CoreSyn ( unSaturatedOk, needSaturated, boringCxtOk, boringCxtNotOk, -- ** Predicates and deconstruction on 'Unfolding' - unfoldingTemplate, setUnfoldingTemplate, + unfoldingTemplate, setUnfoldingTemplate, expandUnfolding_maybe, maybeUnfoldingTemplate, otherCons, unfoldingArity, isValueUnfolding, isEvaldUnfolding, isCheapUnfolding, isExpandableUnfolding, isConLikeUnfolding, isCompulsoryUnfolding, @@ -83,6 +84,7 @@ import FastString import Outputable import Util +import Data.Data import Data.Word infixl 4 `mkApps`, `mkTyApps`, `mkVarApps` @@ -135,11 +137,15 @@ infixl 8 `App` -- App brackets to the left -- The type parameter @b@ is for the type of binders in the expression tree. data Expr b = Var Id -- ^ Variables + | Lit Literal -- ^ Primitive literals + | App (Expr b) (Arg b) -- ^ Applications: note that the argument may be a 'Type'. -- -- See "CoreSyn#let_app_invariant" for another invariant + | Lam b (Expr b) -- ^ Lambda abstraction + | Let (Bind b) (Expr b) -- ^ Recursive and non recursive @let@s. Operationally -- this corresponds to allocating a thunk for the things -- bound and then executing the sub-expression. @@ -152,14 +158,16 @@ data Expr b -- the meaning of /lifted/ vs. /unlifted/). -- -- #let_app_invariant# - -- The right hand side of of a non-recursive 'Let' _and_ the argument of an 'App', + -- The right hand side of of a non-recursive 'Let' + -- _and_ the argument of an 'App', -- /may/ be of unlifted type, but only if the expression - -- is ok-for-speculation. This means that the let can be floated around - -- without difficulty. For example, this is OK: + -- is ok-for-speculation. This means that the let can be floated + -- around without difficulty. For example, this is OK: -- -- > y::Int# = x +# 1# -- - -- But this is not, as it may affect termination if the expression is floated out: + -- But this is not, as it may affect termination if the + -- expression is floated out: -- -- > y::Int# = fac 4# -- @@ -179,6 +187,7 @@ data Expr b -- At the moment, the rest of the compiler only deals with type-let -- in a Let expression, rather than at top level. We may want to revist -- this choice. + | Case (Expr b) b Type [Alt b] -- ^ Case split. Operationally this corresponds to evaluating -- the scrutinee (expression examined) to weak head normal form -- and then examining at most one level of resulting constructor (i.e. you @@ -188,15 +197,17 @@ data Expr b -- and the 'Type' must be that of all the case alternatives -- -- #case_invariants# - -- This is one of the more complicated elements of the Core language, and comes - -- with a number of restrictions: + -- This is one of the more complicated elements of the Core language, + -- and comes with a number of restrictions: -- - -- The 'DEFAULT' case alternative must be first in the list, if it occurs at all. + -- The 'DEFAULT' case alternative must be first in the list, + -- if it occurs at all. -- -- The remaining cases are in order of increasing -- tag (for 'DataAlts') or -- lit (for 'LitAlts'). - -- This makes finding the relevant constructor easy, and makes comparison easier too. + -- This makes finding the relevant constructor easy, + -- and makes comparison easier too. -- -- The list of alternatives must be exhaustive. An /exhaustive/ case -- does not necessarily mention all constructors: @@ -210,14 +221,19 @@ data Expr b -- Blue -> ... ) ... -- @ -- - -- The inner case does not need a @Red@ alternative, because @x@ can't be @Red@ at - -- that program point. - | Cast (Expr b) Coercion -- ^ Cast an expression to a particular type. This is used to implement @newtype@s - -- (a @newtype@ constructor or destructor just becomes a 'Cast' in Core) and GADTs. + -- The inner case does not need a @Red@ alternative, because @x@ + -- can't be @Red@ at that program point. + + | Cast (Expr b) Coercion -- ^ Cast an expression to a particular type. + -- This is used to implement @newtype@s (a @newtype@ constructor or + -- destructor just becomes a 'Cast' in Core) and GADTs. + | Note Note (Expr b) -- ^ Notes. These allow general information to be -- added to expressions in the syntax tree + | Type Type -- ^ A type: this should only show up at the top -- level of an Arg + deriving (Data, Typeable) -- | Type synonym for expressions that occur in function argument positions. -- Only 'Arg' should contain a 'Type' at top level, general 'Expr' should not @@ -233,11 +249,12 @@ data AltCon = DataAlt DataCon -- ^ A plain data constructor: @case e of { Foo x -- Invariant: the 'DataCon' is always from a @data@ type, and never from a @newtype@ | LitAlt Literal -- ^ A literal: @case e of { 1 -> ... }@ | DEFAULT -- ^ Trivial alternative: @case e of { _ -> ... }@ - deriving (Eq, Ord) + deriving (Eq, Ord, Data, Typeable) -- | Binding, used for top level bindings in a module and local bindings in a @let@. data Bind b = NonRec b (Expr b) | Rec [(b, (Expr b))] + deriving (Data, Typeable) \end{code} -------------------------- CoreSyn INVARIANTS --------------------------- @@ -277,6 +294,7 @@ See #type_let# data Note = SCC CostCentre -- ^ A cost centre annotation for profiling | CoreNote String -- ^ A generic core annotation, propagated but not used by GHC + deriving (Data, Typeable) \end{code} @@ -402,12 +420,17 @@ data Unfolding -- -- Here, @f@ gets an @OtherCon []@ unfolding. - | DFunUnfolding DataCon [CoreExpr] - -- The Unfolding of a DFunId + | DFunUnfolding -- The Unfolding of a DFunId + -- See Note [DFun unfoldings] -- df = /\a1..am. \d1..dn. MkD (op1 a1..am d1..dn) -- (op2 a1..am d1..dn) - -- where Arity = n, the number of dict args to the dfun - -- The [CoreExpr] are the superclasses and methods [op1,op2], + + Arity -- Arity = m+n, the *total* number of args + -- (unusually, both type and value) to the dfun + + DataCon -- The dictionary data constructor (possibly a newtype datacon) + + [CoreExpr] -- The [CoreExpr] are the superclasses and methods [op1,op2], -- in positional order. -- They are usually variables, but can be trivial expressions -- instead (e.g. a type application). @@ -474,6 +497,7 @@ data UnfoldingGuidance -- See Note [INLINE for small functions] in CoreUnfold ug_unsat_ok :: Bool, -- True <=> ok to inline even if unsaturated ug_boring_ok :: Bool -- True <=> ok to inline even if the context is boring + -- So True,True means "always" } | UnfIfGoodArgs { -- Arose from a normal Id; the info here is the @@ -490,7 +514,34 @@ data UnfoldingGuidance -- (where there are the right number of arguments.) | UnfNever -- The RHS is big, so don't inline it +\end{code} + + +Note [DFun unfoldings] +~~~~~~~~~~~~~~~~~~~~~~ +The Arity in a DFunUnfolding is total number of args (type and value) +that the DFun needs to produce a dictionary. That's not necessarily +related to the ordinary arity of the dfun Id, esp if the class has +one method, so the dictionary is represented by a newtype. Example + class C a where { op :: a -> Int } + instance C a -> C [a] where op xs = op (head xs) + +The instance translates to + + $dfCList :: forall a. C a => C [a] -- Arity 2! + $dfCList = /\a.\d. $copList {a} d |> co + + $copList :: forall a. C a => [a] -> Int -- Arity 2! + $copList = /\a.\d.\xs. op {a} d (head xs) + +Now we might encounter (op (dfCList {ty} d) a1 a2) +and we want the (op (dfList {ty} d)) rule to fire, because $dfCList +has all its arguments, even though its (value) arity is 2. That's +why we cache the number of expected + + +\begin{code} -- Constants for the UnfWhen constructor needSaturated, unSaturatedOk :: Bool needSaturated = False @@ -583,6 +634,13 @@ isExpandableUnfolding :: Unfolding -> Bool isExpandableUnfolding (CoreUnfolding { uf_expandable = is_expable }) = is_expable isExpandableUnfolding _ = False +expandUnfolding_maybe :: Unfolding -> Maybe CoreExpr +-- Expand an expandable unfolding; this is used in rule matching +-- See Note [Expanding variables] in Rules.lhs +-- The key point here is that CONLIKE things can be expanded +expandUnfolding_maybe (CoreUnfolding { uf_expandable = True, uf_tmpl = rhs }) = Just rhs +expandUnfolding_maybe _ = Nothing + isInlineRule :: Unfolding -> Bool isInlineRule (CoreUnfolding { uf_src = src }) = isInlineRuleSource src isInlineRule _ = False @@ -614,6 +672,7 @@ unfoldingArity _ = panic "unfoldingArity" isClosedUnfolding :: Unfolding -> Bool -- No free variables isClosedUnfolding (CoreUnfolding {}) = False +isClosedUnfolding (DFunUnfolding {}) = False isClosedUnfolding _ = True -- | Only returns False if there is no unfolding information available at all @@ -638,11 +697,13 @@ When you say you intend that calls (f e) are replaced by [e/x] So we should capture (\x.) in the Unfolding of 'f', and never meddle with it. Meanwhile, we can optimise to our heart's content, -leaving the original unfolding intact in Unfolding of 'f'. +leaving the original unfolding intact in Unfolding of 'f'. For example + all xs = foldr (&&) True xs + any p = all . map p {-# INLINE any #-} +We optimise any's RHS fully, but leave the InlineRule saying "all . map p", +which deforests well at the call site. -So the representation of an Unfolding has changed quite a bit -(see CoreSyn). An INLINE pragma gives rise to an InlineRule -unfolding. +So INLINE pragma gives rise to an InlineRule, which captures the original RHS. Moreover, it's only used when 'f' is applied to the specified number of arguments; that is, the number of argument on