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