2 % (c) The GRASP/AQUA Project, Glasgow University, 1993-1998
4 \section[SaLib]{Basic datatypes, functions for the strictness analyser}
6 See also: the ``library'' for the ``back end'' (@SaBackLib@).
12 AbsValEnv{-abstract-}, StrictEnv, AbsenceEnv,
14 nullAbsValEnv, addOneToAbsValEnv, growAbsValEnvList,
19 #include "HsVersions.h"
22 import CoreSyn ( CoreExpr )
24 import IdInfo ( StrictnessInfo(..) )
25 import Demand ( Demand, pprDemands )
29 %************************************************************************
31 \subsection[AbsVal-datatype]{@AbsVal@: abstract values (and @AbsValEnv@)}
33 %************************************************************************
35 @AnalysisKind@ tells what kind of analysis is being done.
39 = StrAnal -- We're doing strictness analysis
40 | AbsAnal -- We're doing absence analysis
44 @AbsVal@ is the data type of HNF abstract values.
48 = AbsTop -- AbsTop is the completely uninformative
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.
56 | AbsProd [AbsVal] -- (Lifted) product of abstract values
57 -- "Lifted" means that AbsBot is *different* from
58 -- AbsProd [AbsBot, ..., AbsBot]
60 | AbsFun -- An abstract function, with the given:
63 AbsValEnv -- and environment
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 -- INVARIANT: the [Demand] is non-empty
71 -- AbsApproxFun has to take a *list* of demands, no just one,
72 -- because function spaces are now lifted. Hence, (f bot top)
73 -- might be bot, but the partial application (f bot) is a *function*,
76 mkAbsApproxFun :: Demand -> AbsVal -> AbsVal
77 mkAbsApproxFun d (AbsApproxFun ds val) = AbsApproxFun (d:ds) val
78 mkAbsApproxFun d val = AbsApproxFun [d] val
80 instance Outputable AbsVal where
81 ppr AbsTop = ptext SLIT("AbsTop")
82 ppr AbsBot = ptext SLIT("AbsBot")
83 ppr (AbsProd prod) = hsep [ptext SLIT("AbsProd"), ppr prod]
84 ppr (AbsFun arg body env)
85 = hsep [ptext SLIT("AbsFun{"), ppr arg,
86 ptext SLIT("???"), -- text "}{env:", ppr (keysFM env `zip` eltsFM env),
88 ppr (AbsApproxFun demands val)
89 = hsep [ptext SLIT("AbsApprox "), hcat (map ppr demands), ppr val]
94 An @AbsValEnv@ maps @Ids@ to @AbsVals@. Any unbound @Ids@ are
95 implicitly bound to @AbsTop@, the completely uninformative,
96 pessimistic value---see @absEval@ of a @Var@.
99 newtype AbsValEnv = AbsValEnv (IdEnv AbsVal)
101 type StrictEnv = AbsValEnv -- Environment for strictness analysis
102 type AbsenceEnv = AbsValEnv -- Environment for absence analysis
104 nullAbsValEnv -- this is the one and only way to create AbsValEnvs
105 = AbsValEnv emptyVarEnv
107 addOneToAbsValEnv (AbsValEnv idenv) y z = AbsValEnv (extendVarEnv idenv y z)
108 growAbsValEnvList (AbsValEnv idenv) ys = AbsValEnv (extendVarEnvList idenv ys)
110 lookupAbsValEnv (AbsValEnv idenv) y
111 = lookupVarEnv idenv y
115 absValFromStrictness :: AnalysisKind -> StrictnessInfo -> AbsVal
117 absValFromStrictness anal NoStrictnessInfo = AbsTop
118 absValFromStrictness anal (StrictnessInfo args_info bot_result)
119 = case args_info of -- Check the invariant that the arg list on
120 [] -> res -- AbsApproxFun is non-empty
121 _ -> AbsApproxFun args_info res
123 res | not bot_result = AbsTop
124 | otherwise = case anal of