ghc/compiler/simplCore/BinderInfo.lhs

   1 %
   2 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1995
   3 %
   4 %************************************************************************
   5 %*                                                                      *
   6 \section[BinderInfo]{Information attached to binders by SubstAnal}
   7 %*                                                                      *
   8 %************************************************************************
   9
  10 \begin{code}
  11
  12 #include "HsVersions.h"
  13
  14 module BinderInfo (
  15         BinderInfo(..),
  16         FunOrArg, DuplicationDanger, InsideSCC,  -- NB: all abstract (yay!)
  17
  18         inlineUnconditionally, oneTextualOcc, oneSafeOcc,
  19
  20         combineBinderInfo, combineAltsBinderInfo,
  21
  22         argOccurrence, funOccurrence,
  23         markMany, markDangerousToDup, markInsideSCC,
  24         getBinderInfoArity,
  25         setBinderInfoArityToZero,
  26
  27         isFun, isDupDanger -- for Simon Marlow deforestation
  28     ) where
  29
  30 IMPORT_Trace            -- ToDo: rm (debugging)
  31
  32 import PlainCore
  33 import Outputable
  34 import Pretty
  35 import Util             -- for pragmas only
  36 \end{code}
  37
  38 The @BinderInfo@ describes how a variable is used in a given scope.
  39
  40 NOTE: With SCCs we have to be careful what we unfold! We don't want to
  41 change the attribution of execution costs. If we decide to unfold
  42 within an SCC we can tag the definition as @DontKeepBinder@.
  43 Definitions tagged as @KeepBinder@ are discarded when we enter the
  44 scope of an SCC.
  45
  46 \begin{code}
  47 data BinderInfo
  48   = DeadCode    -- Dead code; discard the binding.
  49
  50   | ManyOcc     -- Everything else besides DeadCode and OneOccs
  51
  52         Int     -- number of arguments on stack when called
  53
  54
  55   | OneOcc      -- Just one occurrence (or one each in
  56                 -- mutually-exclusive case alts).
  57
  58       FunOrArg  -- How it occurs
  59
  60       DuplicationDanger
  61
  62       InsideSCC
  63
  64       Int       -- Number of mutually-exclusive case alternatives
  65                 -- in which it occurs
  66
  67                 -- Note that we only worry about the case-alt counts
  68                 -- if the OneOcc is substitutable -- that's the only
  69                 -- time we *use* the info; we could be more clever for
  70                 -- other cases if we really had to. (WDP/PS)
  71
  72       Int       -- number of arguments on stack when called
  73
  74 -- In general, we are feel free to substitute unless
  75 -- (a) is in an argument position (ArgOcc)
  76 -- (b) is inside a lambda [or type lambda?] (DupDanger)
  77 -- (c) is inside an SCC expression (InsideSCC)
  78 -- (d) is in the RHS of a binding for a variable with an INLINE pragma
  79 --      (because the RHS will be inlined regardless of its size)
  80 --      [again, DupDanger]
  81
  82 data FunOrArg
  83   = FunOcc      -- An occurrence in a function position
  84   | ArgOcc      -- Other arg occurrence
  85
  86     -- When combining branches of a case, only report FunOcc if
  87     -- both branches are FunOccs
  88
  89 data DuplicationDanger
  90   = DupDanger   -- Inside a non-linear lambda (that is, a lambda which
  91                 -- is sure to be instantiated only once), or inside
  92                 -- the rhs of an INLINE-pragma'd thing.  Either way,
  93                 -- substituting a redex for this occurrence is
  94                 -- dangerous because it might duplicate work.
  95
  96   | NoDupDanger -- It's ok; substitution won't duplicate work.
  97
  98 data InsideSCC
  99   = InsideSCC       -- Inside an SCC; so be careful when substituting.
 100   | NotInsideSCC    -- It's ok.
 101 \end{code}
 102
 103
 104 Predicates
 105 ~~~~~~~~~~
 106
 107 @oneTextualOcc@ checks for one occurrence, in any position.
 108 The occurrence may be inside a lambda, that's all right.
 109
 110 \begin{code}
 111 oneTextualOcc :: Bool -> BinderInfo -> Bool
 112
 113 oneTextualOcc ok_to_dup (OneOcc _ _ _ n_alts _) = n_alts <= 1 || ok_to_dup
 114 oneTextualOcc _         other                   = False
 115 \end{code}
 116
 117 @safeSingleOcc@ detects single occurences of values that are safe to
 118 inline, {\em including} ones in an argument position.
 119
 120 \begin{code}
 121 oneSafeOcc :: Bool -> BinderInfo -> Bool
 122 oneSafeOcc ok_to_dup (OneOcc _ NoDupDanger NotInsideSCC n_alts _)
 123                                                      = n_alts <= 1 || ok_to_dup
 124 oneSafeOcc _         other                           = False
 125 \end{code}
 126
 127 @inlineUnconditionally@ decides whether a let-bound thing can
 128 definitely be inlined.
 129
 130 \begin{code}
 131 inlineUnconditionally :: Bool -> BinderInfo -> Bool
 132
 133 --inlineUnconditionally ok_to_dup DeadCode = True
 134 inlineUnconditionally ok_to_dup (OneOcc FunOcc NoDupDanger NotInsideSCC n_alt_occs _)
 135   = n_alt_occs <= 1 || ok_to_dup
 136             -- We [i.e., Patrick] don't mind the code explosion,
 137             -- though.  We could have a flag to limit the
 138             -- damage, e.g., limit to M alternatives.
 139
 140 inlineUnconditionally _ _ = False
 141 \end{code}
 142
 143 \begin{code}
 144 isFun :: FunOrArg -> Bool
 145 isFun FunOcc = True
 146 isFun _ = False
 147
 148 isDupDanger :: DuplicationDanger -> Bool
 149 isDupDanger DupDanger = True
 150 isDupDanger _ = False
 151 \end{code}
 152
 153
 154 Construction
 155 ~~~~~~~~~~~~~
 156 \begin{code}
 157 argOccurrence, funOccurrence :: Int -> BinderInfo
 158
 159 funOccurrence = OneOcc FunOcc NoDupDanger NotInsideSCC 1
 160 argOccurrence = OneOcc ArgOcc NoDupDanger NotInsideSCC 1
 161
 162 markMany, markDangerousToDup, markInsideSCC :: BinderInfo -> BinderInfo
 163
 164 markMany (OneOcc _ _ _ _ ar) = ManyOcc ar
 165 markMany (ManyOcc ar)        = ManyOcc ar
 166 markMany DeadCode            = panic "markMany"
 167
 168 markDangerousToDup (OneOcc posn _ in_scc n_alts ar)
 169   = OneOcc posn DupDanger in_scc n_alts ar
 170 markDangerousToDup other = other
 171
 172 markInsideSCC (OneOcc posn dup_danger _ n_alts ar)
 173   = OneOcc posn dup_danger InsideSCC n_alts ar
 174 markInsideSCC other = other
 175
 176 combineBinderInfo, combineAltsBinderInfo
 177         :: BinderInfo -> BinderInfo -> BinderInfo
 178
 179 combineBinderInfo DeadCode info2 = info2
 180 combineBinderInfo info1 DeadCode = info1
 181 combineBinderInfo info1 info2
 182         = ManyOcc (min (getBinderInfoArity info1) (getBinderInfoArity info2))
 183
 184 combineAltsBinderInfo DeadCode info2 = info2
 185 combineAltsBinderInfo info1 DeadCode = info1
 186 combineAltsBinderInfo (OneOcc posn1 dup1 scc1 n_alts1 ar_1)
 187                       (OneOcc posn2 dup2 scc2 n_alts2 ar_2)
 188   = OneOcc (combine_posns posn1 posn2)
 189            (combine_dups  dup1  dup2)
 190            (combine_sccs  scc1  scc2)
 191            (n_alts1 + n_alts2)
 192            (min ar_1 ar_2)
 193   where
 194     combine_posns FunOcc FunOcc = FunOcc -- see comment at FunOrArg defn
 195     combine_posns _      _      = ArgOcc
 196
 197     combine_dups DupDanger _ = DupDanger        -- Too paranoid?? ToDo
 198     combine_dups _ DupDanger = DupDanger
 199     combine_dups _ _         = NoDupDanger
 200
 201     combine_sccs InsideSCC _ = InsideSCC        -- Too paranoid?? ToDo
 202     combine_sccs _ InsideSCC = InsideSCC
 203     combine_sccs _ _         = NotInsideSCC
 204
 205 combineAltsBinderInfo info1 info2
 206         = ManyOcc (min (getBinderInfoArity info1) (getBinderInfoArity info2))
 207
 208 setBinderInfoArityToZero :: BinderInfo -> BinderInfo
 209 setBinderInfoArityToZero DeadCode    = DeadCode
 210 setBinderInfoArityToZero (ManyOcc _) = ManyOcc 0
 211 setBinderInfoArityToZero (OneOcc fa dd sc i _) = OneOcc fa dd sc i 0
 212 \end{code}
 213
 214 \begin{code}
 215 getBinderInfoArity (DeadCode) = 0
 216 getBinderInfoArity (ManyOcc i) = i
 217 getBinderInfoArity (OneOcc _ _ _ _ i) = i
 218 \end{code}
 219
 220 \begin{code}
 221 instance Outputable BinderInfo where
 222   ppr sty DeadCode     = ppStr "Dead"
 223   ppr sty (ManyOcc ar) = ppBesides [ ppStr "Many-", ppInt ar ]
 224   ppr sty (OneOcc posn dup_danger in_scc n_alts ar)
 225     = ppBesides [ ppStr "One-", pp_posn posn, ppChar '-', pp_danger dup_danger,
 226                   ppChar '-', pp_scc in_scc,  ppChar '-', ppInt n_alts,
 227                   ppChar '-', ppInt ar ]
 228     where
 229       pp_posn FunOcc = ppStr "fun"
 230       pp_posn ArgOcc = ppStr "arg"
 231
 232       pp_danger DupDanger   = ppStr "*dup*"
 233       pp_danger NoDupDanger = ppStr "nodup"
 234
 235       pp_scc InsideSCC    = ppStr "*SCC*"
 236       pp_scc NotInsideSCC = ppStr "noscc"
 237 \end{code}
 238