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