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         SYN_IE(StrAnalFlags), getStrAnalFlags,
  16         nullAbsValEnv, addOneToAbsValEnv, growAbsValEnvList,
  17         lookupAbsValEnv,
  18         absValFromStrictness
  19     ) where
  20
  21 IMP_Ubiq(){-uitous-}
  22
  23 import CoreSyn          ( SYN_IE(CoreExpr) )
  24 import Id               ( nullIdEnv, addOneToIdEnv, growIdEnvList,
  25                           lookupIdEnv, SYN_IE(IdEnv),
  26                           GenId{-instance Outputable-}
  27                         )
  28 import IdInfo           ( StrictnessInfo(..) )
  29 import Demand           ( Demand{-instance Outputable-} )
  30 import Outputable       ( Outputable(..){-instance * []-} )
  31 import PprType          ( GenType{-instance Outputable-} )
  32 import Pretty           ( ppStr, ppCat )
  33 \end{code}
  34
  35 %************************************************************************
  36 %*                                                                      *
  37 \subsection[AbsVal-datatype]{@AbsVal@: abstract values (and @AbsValEnv@)}
  38 %*                                                                      *
  39 %************************************************************************
  40
  41 @AnalysisKind@ tells what kind of analysis is being done.
  42
  43 \begin{code}
  44 data AnalysisKind
  45   = StrAnal     -- We're doing strictness analysis
  46   | AbsAnal     -- We're doing absence analysis
  47   deriving Text
  48 \end{code}
  49
  50 @AbsVal@ is the data type of HNF abstract values.
  51
  52 \begin{code}
  53 data AbsVal
  54   = AbsTop                  -- AbsTop is the completely uninformative
  55                             -- value
  56
  57   | AbsBot                  -- An expression whose abstract value is
  58                             -- AbsBot is sure to fail to terminate.
  59                             -- AbsBot represents the abstract
  60                             -- *function* bottom too.
  61
  62   | AbsProd [AbsVal]        -- (Lifted) product of abstract values
  63                             -- "Lifted" means that AbsBot is *different* from
  64                             --    AbsProd [AbsBot, ..., AbsBot]
  65
  66   | AbsFun                  -- An abstract function, with the given:
  67             [Id]            -- arguments
  68             CoreExpr   -- body
  69             AbsValEnv       -- and environment
  70
  71   | AbsApproxFun            -- This is used to represent a coarse
  72             [Demand]        -- approximation to a function value.  It's an
  73                             -- abstract function which is strict in its i'th
  74                             -- argument if the i'th element of the Demand
  75                             -- list so indicates.
  76                             -- The list of arguments is always non-empty.
  77                             -- In effect, AbsApproxFun [] = AbsTop
  78
  79 instance Outputable AbsVal where
  80     ppr sty AbsTop = ppStr "AbsTop"
  81     ppr sty AbsBot = ppStr "AbsBot"
  82     ppr sty (AbsProd prod) = ppCat [ppStr "AbsProd", ppr sty prod]
  83     ppr sty (AbsFun args body env)
  84       = ppCat [ppStr "AbsFun{", ppr sty args,
  85                ppStr "???", -- ppStr "}{env:", ppr sty (keysFM env `zip` eltsFM env),
  86                ppStr "}" ]
  87     ppr sty (AbsApproxFun demands)
  88       = ppCat [ppStr "AbsApprox{", ppr sty demands, ppStr "}" ]
  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 data AbsValEnv = AbsValEnv StrAnalFlags (IdEnv AbsVal)
  99
 100 type StrAnalFlags
 101   = (Bool,      -- True <=> AllStrict flag is set
 102      Bool)      -- True <=> NumbersStrict flag is set
 103
 104 type StrictEnv  = AbsValEnv     -- Environment for strictness analysis
 105 type AbsenceEnv = AbsValEnv     -- Environment for absence analysis
 106
 107 nullAbsValEnv flags -- this is the one and only way to create AbsValEnvs
 108   = AbsValEnv flags nullIdEnv
 109
 110 addOneToAbsValEnv (AbsValEnv x idenv) y z = AbsValEnv x (addOneToIdEnv idenv y z)
 111 growAbsValEnvList (AbsValEnv x idenv) ys  = AbsValEnv x (growIdEnvList idenv ys)
 112
 113 lookupAbsValEnv (AbsValEnv _ idenv) y
 114   = lookupIdEnv idenv y
 115
 116 getStrAnalFlags (AbsValEnv flags _) = flags
 117 \end{code}
 118
 119 \begin{code}
 120 absValFromStrictness :: AnalysisKind -> StrictnessInfo bdee -> AbsVal
 121
 122 absValFromStrictness anal NoStrictnessInfo             = AbsTop
 123
 124 absValFromStrictness StrAnal BottomGuaranteed          = AbsBot -- Guaranteed bottom
 125 absValFromStrictness AbsAnal BottomGuaranteed          = AbsTop -- Check for poison in
 126                                                                 -- arguments (if any)
 127 absValFromStrictness anal (StrictnessInfo []        _) = AbsTop
 128 absValFromStrictness anal (StrictnessInfo args_info _) = AbsApproxFun args_info
 129 \end{code}