Repository : ssh://darcs.haskell.org//srv/darcs/ghc On branch : cardinality
http://hackage.haskell.org/trac/ghc/changeset/2f2a11b1d8f47d916d2297d2f487484b41e5a22c >--------------------------------------------------------------- commit 2f2a11b1d8f47d916d2297d2f487484b41e5a22c Author: Ilya Sergey <[email protected]> Date: Wed Sep 19 17:20:57 2012 +0100 polymorphic expansion of call demands >--------------------------------------------------------------- compiler/basicTypes/Demand.lhs | 9 ++- compiler/stranal/DmdAnal.lhs | 107 ++++++++++++++++++---------------------- 2 files changed, 54 insertions(+), 62 deletions(-) diff --git a/compiler/basicTypes/Demand.lhs b/compiler/basicTypes/Demand.lhs index 2c278f1..a809371 100644 --- a/compiler/basicTypes/Demand.lhs +++ b/compiler/basicTypes/Demand.lhs @@ -30,7 +30,7 @@ module Demand ( isProdDmd, isPolyDmd, replicateDmd, splitProdDmd, peelCallDmd, mkCallDmd, isProdUsage, -- cardinality stuff - markAsUsedType, isSingleUsed + markAsUsedType, isSingleUsed, isUsageCallDmd ) where #include "HsVersions.h" @@ -528,11 +528,14 @@ mkCallDmd :: JointDmd -> JointDmd mkCallDmd (JD {strd = d, absd = a}) = mkJointDmd (strCall d) (absCall One a) +isUsageCallDmd :: JointDmd -> Bool +isUsageCallDmd (JD {absd = UCall _ _}) = True +isUsageCallDmd _ = False + -- Returns result demand + one-shotness of the call peelCallDmd :: JointDmd -> Maybe (JointDmd, Count) peelCallDmd (JD {strd = SCall d, absd = UCall c a}) = Just (mkJointDmd d a, c) -peelCallDmd (JD {strd = Lazy, absd = UCall c a}) = Just (mkJointDmd Lazy a, c) -peelCallDmd (JD {strd = HyperStr, absd = UCall c a}) = Just (mkJointDmd HyperStr a, c) +peelCallDmd (JD {strd = Str, absd = UCall c a}) = Just (mkJointDmd Lazy a, c) peelCallDmd (JD {strd = SCall d, absd = Used _}) = Just (mkJointDmd d top, Many) peelCallDmd _ = Nothing diff --git a/compiler/stranal/DmdAnal.lhs b/compiler/stranal/DmdAnal.lhs index 12f760e..1abc92b 100644 --- a/compiler/stranal/DmdAnal.lhs +++ b/compiler/stranal/DmdAnal.lhs @@ -94,45 +94,6 @@ dmdAnal _ dmd e | isAbs dmd -- top demand does not provide any way to infer something interesting = (topDmdType, e) --- this case should go before analyzing with the lazy demand --- see Note [Analyzing with lazy demand and lambdas] -dmdAnal env dmd (Lam var body) - | isTyVar var - = let - (body_ty, body') = dmdAnal env dmd body - in - (body_ty, Lam var body') - - | Just (body_dmd, One) <- peelCallDmd dmd - -- A call demand, also a one-shot lambda - = let - env' = extendSigsWithLam env var - (body_ty, body') = dmdAnal env' body_dmd body - armed_var = setOneShotLambda var - (lam_ty, var') = annotateLamIdBndr env body_ty armed_var - in - -- pprTrace "dmdAnal-Lam-One" (vcat [ppr var, ppr dmd, ppr lam_ty]) $ - (lam_ty, Lam var' body') - - | Just (body_dmd, Many) <- peelCallDmd dmd - -- A call demand: good! (but not a one-shot lambda) - = let - env' = extendSigsWithLam env var - (body_ty, body') = dmdAnal env' body_dmd body - (lam_ty, var') = annotateLamIdBndr env body_ty var - in - -- pprTrace "dmdAnal-Lam-Many" (vcat [ppr var, ppr dmd, ppr lam_ty]) $ - (lam_ty, Lam var' body') - - - | otherwise -- Not enough demand on the lambda; but do the body - = let -- anyway to annotate it and gather free var info - (body_ty, body') = dmdAnal env evalDmd body - (lam_ty, var') = annotateLamIdBndr env body_ty var - in - -- pprTrace "dmdAnal-Lam-Other" (vcat [ppr var, ppr dmd, ppr lam_ty]) $ - (deferType lam_ty, Lam var' body') - dmdAnal env dmd e | not (isStrictDmd dmd) = let (res_ty, e') = dmdAnal env fake_dmd e @@ -200,6 +161,34 @@ dmdAnal env dmd (App fun arg) -- Non-type arguments in (res_ty `both` arg_ty, App fun' arg') +dmdAnal env dmd (Lam var body) + | isTyVar var + = let + (body_ty, body') = dmdAnal env dmd body + in + (body_ty, Lam var body') + + | Just (body_dmd, c) <- peelCallDmd dmd + -- A call demand, also a one-shot lambda + -- see Note [Analyzing with lazy demand and lambdas] + = let + env' = extendSigsWithLam env var + (body_ty, body') = dmdAnal env' body_dmd body + armed_var = case c of Many -> var + One -> setOneShotLambda var + (lam_ty, var') = annotateLamIdBndr env body_ty armed_var + in + -- pprTrace "dmdAnal-Lam-Card" (vcat [ppr var, ppr dmd, ppr lam_ty]) $ + (lam_ty, Lam var' body') + + | otherwise -- Not enough demand on the lambda; but do the body + = let -- anyway to annotate it and gather free var info + (body_ty, body') = dmdAnal env evalDmd body + (lam_ty, var') = annotateLamIdBndr env body_ty var + in + -- pprTrace "dmdAnal-Lam-Other" (vcat [ppr var, ppr dmd, ppr lam_ty]) $ + (deferType lam_ty, Lam var' body') + dmdAnal env dmd (Case scrut case_bndr ty [alt@(DataAlt dc, _, _)]) -- Only one alternative with a product constructor | let tycon = dataConTyCon dc @@ -342,35 +331,35 @@ dmdAnalAlt env dmd (con,bndrs,rhs) Note [Analyzing with lazy demand and lambdas] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Because of some interferences between strictness and usage analyses, -the clause responsible for analyzing lambdas goes before the -administrative one, that creates a `fake` strict demand: - -dmdAnal env dmd e - | not (isStrictDmd dmd) - = let (res_ty, e') = dmdAnal env fake_dmd e - in -- compute as with a strict demand, return with a lazy demand - (deferType res_ty, e') - -The motivation for this rearrangement follows from the fact that for -strictness L = C(L) = C(C(L)). This polymothpic expansion is critical -for cardinality analysis of the following example: +The insigt for analyzing lambdas follows from the fact that for +strictness S = C(L). This polymothpic expansion is critical for +cardinality analysis of the following example: +{-# NOINLINE build #-} build g = (g (:) [], g (:) []) -h z = build (\x -> \y -> x (y ++ z)) +h c z = build (\x -> + let z1 = z ++ z + in if c + then \y -> x (y ++ z1) + else \y -> x (z1 ++ y)) One can see that `build` assigns to `g` demand <L, -C(C1(U))>. Therefore, when analyzing the lambda `(\x -> \y -> x (y ++ -z))`, we expect the lambda \y -> ... to be annotated as "one-shot" +C(C1(U))>. Therefore, when analyzing the lambda `(\x -> ...)`, we +expect each lambda \y -> ... to be annotated as "one-shot" one. Therefore (\x -> \y -> x (y ++ z)) should be analyzed with a -demand <C(C(..), C(C1(U))>. However, had we the clause above coming -before analysis of lambda, the inner lambda (\y -> ...) would be -analyzed with demand U, rather than C1(U), as the "fake" strict demand -S cannot be polymorphically expanded for calls. +demand <C(C(..), C(C1(U))>. +This is achieved by ,first, converting the lazy demand L into the +strict S by the second clause of the analysis: +dmdAnal env dmd e + | not (isStrictDmd dmd) + = let (res_ty, e') = dmdAnal env fake_dmd e + in (deferType res_ty, e') + where fake_dmd = mkJointDmd strStr $ absd dmd +and, second, expanding S into C(L). \begin{code} _______________________________________________ Cvs-ghc mailing list [email protected] http://www.haskell.org/mailman/listinfo/cvs-ghc
