ghc/compiler/stranal/SaLib.lhs

   1 %
   2 % (c) The GRASP/AQUA Project, Glasgow University, 1993-1996
   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         nullAbsValEnv, addOneToAbsValEnv, growAbsValEnvList,
  14         lookupAbsValEnv,
  15         absValFromStrictness
  16     ) where
  17
  18 #include "HsVersions.h"
  19
  20 import CoreSyn          ( CoreExpr )
  21 import Id               ( nullIdEnv, addOneToIdEnv, growIdEnvList,
  22                           lookupIdEnv, IdEnv,
  23                           Id
  24                         )
  25 import IdInfo           ( StrictnessInfo(..) )
  26 import Demand           ( Demand{-instance Outputable-} )
  27 import Outputable
  28 \end{code}
  29
  30 %************************************************************************
  31 %*                                                                      *
  32 \subsection[AbsVal-datatype]{@AbsVal@: abstract values (and @AbsValEnv@)}
  33 %*                                                                      *
  34 %************************************************************************
  35
  36 @AnalysisKind@ tells what kind of analysis is being done.
  37
  38 \begin{code}
  39 data AnalysisKind
  40   = StrAnal     -- We're doing strictness analysis
  41   | AbsAnal     -- We're doing absence analysis
  42   deriving Text
  43 \end{code}
  44
  45 @AbsVal@ is the data type of HNF abstract values.
  46
  47 \begin{code}
  48 data AbsVal
  49   = AbsTop                  -- AbsTop is the completely uninformative
  50                             -- value
  51
  52   | AbsBot                  -- An expression whose abstract value is
  53                             -- AbsBot is sure to fail to terminate.
  54                             -- AbsBot represents the abstract
  55                             -- *function* bottom too.
  56
  57   | AbsProd [AbsVal]        -- (Lifted) product of abstract values
  58                             -- "Lifted" means that AbsBot is *different* from
  59                             --    AbsProd [AbsBot, ..., AbsBot]
  60
  61   | AbsFun                  -- An abstract function, with the given:
  62             Id              -- argument
  63             CoreExpr        -- body
  64             AbsValEnv       -- and environment
  65
  66   | AbsApproxFun            -- This is used to represent a coarse
  67             Demand          -- approximation to a function value.  It's an
  68             AbsVal          -- abstract function which is strict in its
  69                             -- argument if the  Demand so indicates.
  70
  71 instance Outputable AbsVal where
  72     ppr AbsTop = ptext SLIT("AbsTop")
  73     ppr AbsBot = ptext SLIT("AbsBot")
  74     ppr (AbsProd prod) = hsep [ptext SLIT("AbsProd"), ppr prod]
  75     ppr (AbsFun arg body env)
  76       = hsep [ptext SLIT("AbsFun{"), ppr arg,
  77                ptext SLIT("???"), -- text "}{env:", ppr (keysFM env `zip` eltsFM env),
  78                char '}' ]
  79     ppr (AbsApproxFun demand val)
  80       = hsep [ptext SLIT("AbsApprox "), ppr demand, ppr val]
  81 \end{code}
  82
  83 %-----------
  84
  85 An @AbsValEnv@ maps @Ids@ to @AbsVals@.  Any unbound @Ids@ are
  86 implicitly bound to @AbsTop@, the completely uninformative,
  87 pessimistic value---see @absEval@ of a @Var@.
  88
  89 \begin{code}
  90 newtype AbsValEnv = AbsValEnv (IdEnv AbsVal)
  91
  92 type StrictEnv  = AbsValEnv     -- Environment for strictness analysis
  93 type AbsenceEnv = AbsValEnv     -- Environment for absence analysis
  94
  95 nullAbsValEnv -- this is the one and only way to create AbsValEnvs
  96   = AbsValEnv nullIdEnv
  97
  98 addOneToAbsValEnv (AbsValEnv idenv) y z = AbsValEnv (addOneToIdEnv idenv y z)
  99 growAbsValEnvList (AbsValEnv idenv) ys  = AbsValEnv (growIdEnvList idenv ys)
 100
 101 lookupAbsValEnv (AbsValEnv idenv) y
 102   = lookupIdEnv idenv y
 103 \end{code}
 104
 105 \begin{code}
 106 absValFromStrictness :: AnalysisKind -> StrictnessInfo -> AbsVal
 107
 108 absValFromStrictness anal NoStrictnessInfo             = AbsTop
 109
 110 absValFromStrictness StrAnal BottomGuaranteed          = AbsBot -- Guaranteed bottom
 111 absValFromStrictness AbsAnal BottomGuaranteed          = AbsTop -- Check for poison in
 112                                                                 -- arguments (if any)
 113 absValFromStrictness anal (StrictnessInfo args_info _) = foldr AbsApproxFun AbsTop args_info
 114 \end{code}