[commit: ghc] cardinality: polymorphic expansion of call demands (2f2a11b)

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}