ghc/compiler/stranal/SaLib.lhs

   1 %
   2 % (c) The GRASP/AQUA Project, Glasgow University, 1993-1998
   3 %
   4 \section[SaLib]{Basic datatypes, functions for the strictness analyser}
   5
   6 See also: the ``library'' for the ``back end'' (@SaBackLib@).
   7
   8 \begin{code}
   9 module SaLib (
  10         AbsVal(..),
  11         AnalysisKind(..),
  12         AbsValEnv{-abstract-}, StrictEnv, AbsenceEnv,
  13         mkAbsApproxFun,
  14         nullAbsValEnv, addOneToAbsValEnv, growAbsValEnvList,
  15         lookupAbsValEnv,
  16         absValFromStrictness
  17     ) where
  18
  19 #include "HsVersions.h"
  20
  21 import Id               ( Id )
  22 import CoreSyn          ( CoreExpr )
  23 import VarEnv
  24 import IdInfo           ( StrictnessInfo(..) )
  25 import Demand           ( Demand, pprDemands )
  26 import Outputable
  27 \end{code}
  28
  29 %************************************************************************
  30 %*                                                                      *
  31 \subsection[AbsVal-datatype]{@AbsVal@: abstract values (and @AbsValEnv@)}
  32 %*                                                                      *
  33 %************************************************************************
  34
  35 @AnalysisKind@ tells what kind of analysis is being done.
  36
  37 \begin{code}
  38 data AnalysisKind
  39   = StrAnal     -- We're doing strictness analysis
  40   | AbsAnal     -- We're doing absence analysis
  41   deriving Text
  42 \end{code}
  43
  44 @AbsVal@ is the data type of HNF abstract values.
  45
  46 \begin{code}
  47 data AbsVal
  48   = AbsTop                  -- AbsTop is the completely uninformative
  49                             -- value
  50
  51   | AbsBot                  -- An expression whose abstract value is
  52                             -- AbsBot is sure to fail to terminate.
  53                             -- AbsBot represents the abstract
  54                             -- *function* bottom too.
  55
  56   | AbsProd [AbsVal]        -- (Lifted) product of abstract values
  57                             -- "Lifted" means that AbsBot is *different* from
  58                             --    AbsProd [AbsBot, ..., AbsBot]
  59
  60   | AbsFun                  -- An abstract function, with the given:
  61             Id              -- argument
  62             CoreExpr        -- body
  63             AbsValEnv       -- and environment
  64
  65   | AbsApproxFun            -- This is used to represent a coarse
  66             [Demand]        -- approximation to a function value.  It's an
  67             AbsVal          -- abstract function which is strict in its
  68                             -- arguments if the  Demand so indicates.
  69
  70         -- AbsApproxFun has to take a *list* of demands, no just one,
  71         -- because function spaces are now lifted.  Hence, (f bot top)
  72         -- might be bot, but the partial application (f bot) is a *function*,
  73         -- not bot.
  74
  75 mkAbsApproxFun :: Demand -> AbsVal -> AbsVal
  76 mkAbsApproxFun d (AbsApproxFun ds val) = AbsApproxFun (d:ds) val
  77 mkAbsApproxFun d val                   = AbsApproxFun [d]    val
  78
  79 instance Outputable AbsVal where
  80     ppr AbsTop = ptext SLIT("AbsTop")
  81     ppr AbsBot = ptext SLIT("AbsBot")
  82     ppr (AbsProd prod) = hsep [ptext SLIT("AbsProd"), ppr prod]
  83     ppr (AbsFun arg body env)
  84       = hsep [ptext SLIT("AbsFun{"), ppr arg,
  85                ptext SLIT("???"), -- text "}{env:", ppr (keysFM env `zip` eltsFM env),
  86                char '}' ]
  87     ppr (AbsApproxFun demands val)
  88       = hsep [ptext SLIT("AbsApprox "), pprDemands demands, ppr val]
  89 \end{code}
  90
  91 %-----------
  92
  93 An @AbsValEnv@ maps @Ids@ to @AbsVals@.  Any unbound @Ids@ are
  94 implicitly bound to @AbsTop@, the completely uninformative,
  95 pessimistic value---see @absEval@ of a @Var@.
  96
  97 \begin{code}
  98 newtype AbsValEnv = AbsValEnv (IdEnv AbsVal)
  99
 100 type StrictEnv  = AbsValEnv     -- Environment for strictness analysis
 101 type AbsenceEnv = AbsValEnv     -- Environment for absence analysis
 102
 103 nullAbsValEnv -- this is the one and only way to create AbsValEnvs
 104   = AbsValEnv emptyVarEnv
 105
 106 addOneToAbsValEnv (AbsValEnv idenv) y z = AbsValEnv (extendVarEnv idenv y z)
 107 growAbsValEnvList (AbsValEnv idenv) ys  = AbsValEnv (extendVarEnvList idenv ys)
 108
 109 lookupAbsValEnv (AbsValEnv idenv) y
 110   = lookupVarEnv idenv y
 111 \end{code}
 112
 113 \begin{code}
 114 absValFromStrictness :: AnalysisKind -> StrictnessInfo -> AbsVal
 115
 116 absValFromStrictness anal NoStrictnessInfo             = AbsTop
 117
 118 absValFromStrictness StrAnal BottomGuaranteed          = AbsBot -- Guaranteed bottom
 119 absValFromStrictness AbsAnal BottomGuaranteed          = AbsTop -- Check for poison in
 120                                                                 -- arguments (if any)
 121 absValFromStrictness anal (StrictnessInfo args_info _) = AbsApproxFun args_info AbsTop
 122 \end{code}