[ghc-hetmet.git] / compiler / coreSyn / CoreUnfold.lhs

%
% (c) The University of Glasgow 2006
% (c) The AQUA Project, Glasgow University, 1994-1998
%

Core-syntax unfoldings

Unfoldings (which can travel across module boundaries) are in Core
syntax (namely @CoreExpr@s).

The type @Unfolding@ sits ``above'' simply-Core-expressions
unfoldings, capturing ``higher-level'' things we know about a binding,
usually things that the simplifier found out (e.g., ``it's a
literal'').  In the corner of a @CoreUnfolding@ unfolding, you will
find, unsurprisingly, a Core expression.

\begin{code}
module CoreUnfold (
        Unfolding, UnfoldingGuidance,   -- Abstract types

        noUnfolding, mkTopUnfolding, mkUnfolding, mkCompulsoryUnfolding, seqUnfolding,
        evaldUnfolding, mkOtherCon, otherCons,
        unfoldingTemplate, maybeUnfoldingTemplate,
        isEvaldUnfolding, isValueUnfolding, isCheapUnfolding, isCompulsoryUnfolding,
        hasUnfolding, hasSomeUnfolding, neverUnfold,

        couldBeSmallEnoughToInline, 
        certainlyWillInline, smallEnoughToInline,

        callSiteInline
    ) where

#include "HsVersions.h"

import StaticFlags
import DynFlags
import CoreSyn
import PprCore          ()      -- Instances
import OccurAnal
import CoreUtils
import Id
import DataCon
import Literal
import PrimOp
import IdInfo
import Type
import PrelNames
import Bag
import FastTypes
import Outputable

import GHC.Exts         ( Int# )
\end{code}


%************************************************************************
%*                                                                      *
\subsection{Making unfoldings}
%*                                                                      *
%************************************************************************

\begin{code}
mkTopUnfolding expr = mkUnfolding True {- Top level -} expr

mkUnfolding top_lvl expr
  = CoreUnfolding (occurAnalyseExpr expr)
                  top_lvl

                  (exprIsHNF expr)
                        -- Already evaluated

                  (exprIsCheap expr)
                        -- OK to inline inside a lambda

                  (calcUnfoldingGuidance opt_UF_CreationThreshold expr)
        -- Sometimes during simplification, there's a large let-bound thing     
        -- which has been substituted, and so is now dead; so 'expr' contains
        -- two copies of the thing while the occurrence-analysed expression doesn't
        -- Nevertheless, we don't occ-analyse before computing the size because the
        -- size computation bales out after a while, whereas occurrence analysis does not.
        --
        -- This can occasionally mean that the guidance is very pessimistic;
        -- it gets fixed up next round

instance Outputable Unfolding where
  ppr NoUnfolding = ptext SLIT("No unfolding")
  ppr (OtherCon cs) = ptext SLIT("OtherCon") <+> ppr cs
  ppr (CompulsoryUnfolding e) = ptext SLIT("Compulsory") <+> ppr e
  ppr (CoreUnfolding e top hnf cheap g) 
        = ptext SLIT("Unf") <+> sep [ppr top <+> ppr hnf <+> ppr cheap <+> ppr g, 
                                     ppr e]

mkCompulsoryUnfolding expr      -- Used for things that absolutely must be unfolded
  = CompulsoryUnfolding (occurAnalyseExpr expr)
\end{code}


%************************************************************************
%*                                                                      *
\subsection{The UnfoldingGuidance type}
%*                                                                      *
%************************************************************************

\begin{code}
instance Outputable UnfoldingGuidance where
    ppr UnfoldNever     = ptext SLIT("NEVER")
    ppr (UnfoldIfGoodArgs v cs size discount)
      = hsep [ ptext SLIT("IF_ARGS"), int v,
               brackets (hsep (map int cs)),
               int size,
               int discount ]
\end{code}


\begin{code}
calcUnfoldingGuidance
        :: Int                  -- bomb out if size gets bigger than this
        -> CoreExpr             -- expression to look at
        -> UnfoldingGuidance
calcUnfoldingGuidance bOMB_OUT_SIZE expr
  = case collect_val_bndrs expr of { (inline, val_binders, body) ->
    let
        n_val_binders = length val_binders

        max_inline_size = n_val_binders+2
        -- The idea is that if there is an INLINE pragma (inline is True)
        -- and there's a big body, we give a size of n_val_binders+2.  This
        -- This is just enough to fail the no-size-increase test in callSiteInline,
        --   so that INLINE things don't get inlined into entirely boring contexts,
        --   but no more.

    in
    case (sizeExpr (iUnbox bOMB_OUT_SIZE) val_binders body) of

      TooBig 
        | not inline -> UnfoldNever
                -- A big function with an INLINE pragma must
                -- have an UnfoldIfGoodArgs guidance
        | otherwise  -> UnfoldIfGoodArgs n_val_binders
                                         (map (const 0) val_binders)
                                         max_inline_size 0

      SizeIs size cased_args scrut_discount
        -> UnfoldIfGoodArgs
                        n_val_binders
                        (map discount_for val_binders)
                        final_size
                        (iBox scrut_discount)
        where        
            boxed_size    = iBox size

            final_size | inline     = boxed_size `min` max_inline_size
                       | otherwise  = boxed_size

                -- Sometimes an INLINE thing is smaller than n_val_binders+2.
                -- A particular case in point is a constructor, which has size 1.
                -- We want to inline this regardless, hence the `min`

            discount_for b = foldlBag (\acc (b',n) -> if b==b' then acc+n else acc) 
                                      0 cased_args
        }
  where
    collect_val_bndrs e = go False [] e
        -- We need to be a bit careful about how we collect the
        -- value binders.  In ptic, if we see 
        --      __inline_me (\x y -> e)
        -- We want to say "2 value binders".  Why?  So that 
        -- we take account of information given for the arguments

    go inline rev_vbs (Note InlineMe e)     = go True   rev_vbs     e
    go inline rev_vbs (Lam b e) | isId b    = go inline (b:rev_vbs) e
                                | otherwise = go inline rev_vbs     e
    go inline rev_vbs e                     = (inline, reverse rev_vbs, e)
\end{code}

\begin{code}
sizeExpr :: Int#            -- Bomb out if it gets bigger than this
         -> [Id]            -- Arguments; we're interested in which of these
                            -- get case'd
         -> CoreExpr
         -> ExprSize

sizeExpr bOMB_OUT_SIZE top_args expr
  = size_up expr
  where
    size_up (Type t)          = sizeZero        -- Types cost nothing
    size_up (Var v)           = sizeOne

    size_up (Note InlineMe body) = sizeOne      -- Inline notes make it look very small
        -- This can be important.  If you have an instance decl like this:
        --      instance Foo a => Foo [a] where
        --         {-# INLINE op1, op2 #-}
        --         op1 = ...
        --         op2 = ...
        -- then we'll get a dfun which is a pair of two INLINE lambdas

    size_up (Note _        body) = size_up body -- Other notes cost nothing
    
    size_up (Cast e _)           = size_up e

    size_up (App fun (Type t)) = size_up fun
    size_up (App fun arg)      = size_up_app fun [arg]

    size_up (Lit lit)          = sizeN (litSize lit)

    size_up (Lam b e) | isId b    = lamScrutDiscount (size_up e `addSizeN` 1)
                      | otherwise = size_up e

    size_up (Let (NonRec binder rhs) body)
      = nukeScrutDiscount (size_up rhs)         `addSize`
        size_up body                            `addSizeN`
        (if isUnLiftedType (idType binder) then 0 else 1)
                -- For the allocation
                -- If the binder has an unlifted type there is no allocation

    size_up (Let (Rec pairs) body)
      = nukeScrutDiscount rhs_size              `addSize`
        size_up body                            `addSizeN`
        length pairs            -- For the allocation
      where
        rhs_size = foldr (addSize . size_up . snd) sizeZero pairs

    size_up (Case (Var v) _ _ alts) 
        | v `elem` top_args             -- We are scrutinising an argument variable
        = 
{-      I'm nuking this special case; BUT see the comment with case alternatives.

        (a) It's too eager.  We don't want to inline a wrapper into a
            context with no benefit.  
            E.g.  \ x. f (x+x)          no point in inlining (+) here!

        (b) It's ineffective. Once g's wrapper is inlined, its case-expressions 
            aren't scrutinising arguments any more

            case alts of

                [alt] -> size_up_alt alt `addSize` SizeIs 0# (unitBag (v, 1)) 0#
                -- We want to make wrapper-style evaluation look cheap, so that
                -- when we inline a wrapper it doesn't make call site (much) bigger
                -- Otherwise we get nasty phase ordering stuff: 
                --      f x = g x x
                --      h y = ...(f e)...
                -- If we inline g's wrapper, f looks big, and doesn't get inlined
                -- into h; if we inline f first, while it looks small, then g's 
                -- wrapper will get inlined later anyway.  To avoid this nasty
                -- ordering difference, we make (case a of (x,y) -> ...), 
                --  *where a is one of the arguments* look free.

                other -> 
-}
                         alts_size (foldr addSize sizeOne alt_sizes)    -- The 1 is for the scrutinee
                                   (foldr1 maxSize alt_sizes)

                -- Good to inline if an arg is scrutinised, because
                -- that may eliminate allocation in the caller
                -- And it eliminates the case itself

        where
          alt_sizes = map size_up_alt alts

                -- alts_size tries to compute a good discount for
                -- the case when we are scrutinising an argument variable
          alts_size (SizeIs tot tot_disc tot_scrut)             -- Size of all alternatives
                    (SizeIs max max_disc max_scrut)             -- Size of biggest alternative
                = SizeIs tot (unitBag (v, iBox (_ILIT 1 +# tot -# max)) `unionBags` max_disc) max_scrut
                        -- If the variable is known, we produce a discount that
                        -- will take us back to 'max', the size of rh largest alternative
                        -- The 1+ is a little discount for reduced allocation in the caller
          alts_size tot_size _ = tot_size

    size_up (Case e _ _ alts) = nukeScrutDiscount (size_up e) `addSize` 
                                 foldr (addSize . size_up_alt) sizeZero alts
                -- We don't charge for the case itself
                -- It's a strict thing, and the price of the call
                -- is paid by scrut.  Also consider
                --      case f x of DEFAULT -> e
                -- This is just ';'!  Don't charge for it.

    ------------ 
    size_up_app (App fun arg) args   
        | isTypeArg arg              = size_up_app fun args
        | otherwise                  = size_up_app fun (arg:args)
    size_up_app fun           args   = foldr (addSize . nukeScrutDiscount . size_up) 
                                             (size_up_fun fun args)
                                             args

        -- A function application with at least one value argument
        -- so if the function is an argument give it an arg-discount
        --
        -- Also behave specially if the function is a build
        --
        -- Also if the function is a constant Id (constr or primop)
        -- compute discounts specially
    size_up_fun (Var fun) args
      | fun `hasKey` buildIdKey   = buildSize
      | fun `hasKey` augmentIdKey = augmentSize
      | otherwise 
      = case globalIdDetails fun of
          DataConWorkId dc -> conSizeN dc (valArgCount args)

          FCallId fc   -> sizeN opt_UF_DearOp
          PrimOpId op  -> primOpSize op (valArgCount args)
                          -- foldr addSize (primOpSize op) (map arg_discount args)
                          -- At one time I tried giving an arg-discount if a primop 
                          -- is applied to one of the function's arguments, but it's
                          -- not good.  At the moment, any unlifted-type arg gets a
                          -- 'True' for 'yes I'm evald', so we collect the discount even
                          -- if we know nothing about it.  And just having it in a primop
                          -- doesn't help at all if we don't know something more.

          other        -> fun_discount fun `addSizeN` 
                          (1 + length (filter (not . exprIsTrivial) args))
                                -- The 1+ is for the function itself
                                -- Add 1 for each non-trivial arg;
                                -- the allocation cost, as in let(rec)
                                -- Slight hack here: for constructors the args are almost always
                                --      trivial; and for primops they are almost always prim typed
                                --      We should really only count for non-prim-typed args in the
                                --      general case, but that seems too much like hard work

    size_up_fun other args = size_up other

    ------------ 
    size_up_alt (con, bndrs, rhs) = size_up rhs
        -- Don't charge for args, so that wrappers look cheap
        -- (See comments about wrappers with Case)

    ------------
        -- We want to record if we're case'ing, or applying, an argument
    fun_discount v | v `elem` top_args = SizeIs 0# (unitBag (v, opt_UF_FunAppDiscount)) 0#
    fun_discount other                 = sizeZero

    ------------
        -- These addSize things have to be here because
        -- I don't want to give them bOMB_OUT_SIZE as an argument

    addSizeN TooBig          _  = TooBig
    addSizeN (SizeIs n xs d) m  = mkSizeIs bOMB_OUT_SIZE (n +# iUnbox m) xs d
    
    addSize TooBig            _                 = TooBig
    addSize _                 TooBig            = TooBig
    addSize (SizeIs n1 xs d1) (SizeIs n2 ys d2) 
        = mkSizeIs bOMB_OUT_SIZE (n1 +# n2) (xs `unionBags` ys) (d1 +# d2)
\end{code}

Code for manipulating sizes

\begin{code}
data ExprSize = TooBig
              | SizeIs FastInt          -- Size found
                       (Bag (Id,Int))   -- Arguments cased herein, and discount for each such
                       FastInt          -- Size to subtract if result is scrutinised 
                                        -- by a case expression

-- subtract the discount before deciding whether to bale out. eg. we
-- want to inline a large constructor application into a selector:
--      tup = (a_1, ..., a_99)
--      x = case tup of ...
--
mkSizeIs max n xs d | (n -# d) ># max = TooBig
                    | otherwise       = SizeIs n xs d
 
maxSize TooBig         _                                  = TooBig
maxSize _              TooBig                             = TooBig
maxSize s1@(SizeIs n1 _ _) s2@(SizeIs n2 _ _) | n1 ># n2  = s1
                                              | otherwise = s2

sizeZero        = SizeIs (_ILIT 0)  emptyBag (_ILIT 0)
sizeOne         = SizeIs (_ILIT 1)  emptyBag (_ILIT 0)
sizeN n         = SizeIs (iUnbox n) emptyBag (_ILIT 0)
conSizeN dc n   
  | isUnboxedTupleCon dc = SizeIs (_ILIT 0) emptyBag (iUnbox n +# _ILIT 1)
  | otherwise            = SizeIs (_ILIT 1) emptyBag (iUnbox n +# _ILIT 1)
        -- Treat constructors as size 1; we are keen to expose them
        -- (and we charge separately for their args).  We can't treat
        -- them as size zero, else we find that (iBox x) has size 1,
        -- which is the same as a lone variable; and hence 'v' will 
        -- always be replaced by (iBox x), where v is bound to iBox x.
        --
        -- However, unboxed tuples count as size zero
        -- I found occasions where we had 
        --      f x y z = case op# x y z of { s -> (# s, () #) }
        -- and f wasn't getting inlined

primOpSize op n_args
 | not (primOpIsDupable op) = sizeN opt_UF_DearOp
 | not (primOpOutOfLine op) = sizeN (2 - n_args)
        -- Be very keen to inline simple primops.
        -- We give a discount of 1 for each arg so that (op# x y z) costs 2.
        -- We can't make it cost 1, else we'll inline let v = (op# x y z) 
        -- at every use of v, which is excessive.
        --
        -- A good example is:
        --      let x = +# p q in C {x}
        -- Even though x get's an occurrence of 'many', its RHS looks cheap,
        -- and there's a good chance it'll get inlined back into C's RHS. Urgh!
 | otherwise                = sizeOne

buildSize = SizeIs (-2#) emptyBag 4#
        -- We really want to inline applications of build
        -- build t (\cn -> e) should cost only the cost of e (because build will be inlined later)
        -- Indeed, we should add a result_discount becuause build is 
        -- very like a constructor.  We don't bother to check that the
        -- build is saturated (it usually is).  The "-2" discounts for the \c n, 
        -- The "4" is rather arbitrary.

augmentSize = SizeIs (-2#) emptyBag 4#
        -- Ditto (augment t (\cn -> e) ys) should cost only the cost of
        -- e plus ys. The -2 accounts for the \cn 
                                                
nukeScrutDiscount (SizeIs n vs d) = SizeIs n vs 0#
nukeScrutDiscount TooBig          = TooBig

-- When we return a lambda, give a discount if it's used (applied)
lamScrutDiscount  (SizeIs n vs d) = case opt_UF_FunAppDiscount of { d -> SizeIs n vs (iUnbox d) }
lamScrutDiscount TooBig           = TooBig
\end{code}


%************************************************************************
%*                                                                      *
\subsection[considerUnfolding]{Given all the info, do (not) do the unfolding}
%*                                                                      *
%************************************************************************

We have very limited information about an unfolding expression: (1)~so
many type arguments and so many value arguments expected---for our
purposes here, we assume we've got those.  (2)~A ``size'' or ``cost,''
a single integer.  (3)~An ``argument info'' vector.  For this, what we
have at the moment is a Boolean per argument position that says, ``I
will look with great favour on an explicit constructor in this
position.'' (4)~The ``discount'' to subtract if the expression
is being scrutinised. 

Assuming we have enough type- and value arguments (if not, we give up
immediately), then we see if the ``discounted size'' is below some
(semi-arbitrary) threshold.  It works like this: for every argument
position where we're looking for a constructor AND WE HAVE ONE in our
hands, we get a (again, semi-arbitrary) discount [proportion to the
number of constructors in the type being scrutinized].

If we're in the context of a scrutinee ( \tr{(case <expr > of A .. -> ...;.. )})
and the expression in question will evaluate to a constructor, we use
the computed discount size *for the result only* rather than
computing the argument discounts. Since we know the result of
the expression is going to be taken apart, discounting its size
is more accurate (see @sizeExpr@ above for how this discount size
is computed).

We use this one to avoid exporting inlinings that we ``couldn't possibly
use'' on the other side.  Can be overridden w/ flaggery.
Just the same as smallEnoughToInline, except that it has no actual arguments.

\begin{code}
couldBeSmallEnoughToInline :: Int -> CoreExpr -> Bool
couldBeSmallEnoughToInline threshold rhs = case calcUnfoldingGuidance threshold rhs of
                                                UnfoldNever -> False
                                                other       -> True

certainlyWillInline :: Unfolding -> Bool
  -- Sees if the unfolding is pretty certain to inline  
certainlyWillInline (CoreUnfolding _ _ _ is_cheap (UnfoldIfGoodArgs n_vals _ size _))
  = is_cheap && size - (n_vals +1) <= opt_UF_UseThreshold
certainlyWillInline other
  = False

smallEnoughToInline :: Unfolding -> Bool
smallEnoughToInline (CoreUnfolding _ _ _ _ (UnfoldIfGoodArgs _ _ size _))
  = size <= opt_UF_UseThreshold
smallEnoughToInline other
  = False
\end{code}

%************************************************************************
%*                                                                      *
\subsection{callSiteInline}
%*                                                                      *
%************************************************************************

This is the key function.  It decides whether to inline a variable at a call site

callSiteInline is used at call sites, so it is a bit more generous.
It's a very important function that embodies lots of heuristics.
A non-WHNF can be inlined if it doesn't occur inside a lambda,
and occurs exactly once or 
    occurs once in each branch of a case and is small

If the thing is in WHNF, there's no danger of duplicating work, 
so we can inline if it occurs once, or is small

NOTE: we don't want to inline top-level functions that always diverge.
It just makes the code bigger.  Tt turns out that the convenient way to prevent
them inlining is to give them a NOINLINE pragma, which we do in 
StrictAnal.addStrictnessInfoToTopId

\begin{code}
callSiteInline :: DynFlags
               -> Bool                  -- True <=> the Id can be inlined
               -> Id                    -- The Id
               -> [Bool]                -- One for each value arg; True if it is interesting
               -> Bool                  -- True <=> continuation is interesting
               -> Maybe CoreExpr        -- Unfolding, if any


callSiteInline dflags active_inline id arg_infos interesting_cont
  = case idUnfolding id of {
        NoUnfolding -> Nothing ;
        OtherCon cs -> Nothing ;

        CompulsoryUnfolding unf_template -> Just unf_template ;
                -- CompulsoryUnfolding => there is no top-level binding
                -- for these things, so we must inline it.
                -- Only a couple of primop-like things have 
                -- compulsory unfoldings (see MkId.lhs).
                -- We don't allow them to be inactive

        CoreUnfolding unf_template is_top is_value is_cheap guidance ->

    let
        result | yes_or_no = Just unf_template
               | otherwise = Nothing

        n_val_args  = length arg_infos

        yes_or_no 
          | not active_inline = False
          | otherwise = is_cheap && consider_safe False
                -- We consider even the once-in-one-branch
                -- occurrences, because they won't all have been
                -- caught by preInlineUnconditionally.  In particular,
                -- if the occurrence is once inside a lambda, and the
                -- rhs is cheap but not a manifest lambda, then
                -- pre-inline will not have inlined it for fear of
                -- invalidating the occurrence info in the rhs.

        consider_safe once
                -- consider_safe decides whether it's a good idea to
                -- inline something, given that there's no
                -- work-duplication issue (the caller checks that).
          = case guidance of
              UnfoldNever  -> False
              UnfoldIfGoodArgs n_vals_wanted arg_discounts size res_discount

                  | enough_args && size <= (n_vals_wanted + 1)
                        -- Inline unconditionally if there no size increase
                        -- Size of call is n_vals_wanted (+1 for the function)
                  -> True

                  | otherwise
                  -> some_benefit && small_enough

                  where
                    some_benefit = or arg_infos || really_interesting_cont || 
                                   (not is_top && ({- once || -} (n_vals_wanted > 0 && enough_args)))
                                -- [was (once && not in_lam)]
                -- If it occurs more than once, there must be
                -- something interesting about some argument, or the
                -- result context, to make it worth inlining
                --
                -- If a function has a nested defn we also record
                -- some-benefit, on the grounds that we are often able
                -- to eliminate the binding, and hence the allocation,
                -- for the function altogether; this is good for join
                -- points.  But this only makes sense for *functions*;
                -- inlining a constructor doesn't help allocation
                -- unless the result is scrutinised.  UNLESS the
                -- constructor occurs just once, albeit possibly in
                -- multiple case branches.  Then inlining it doesn't
                -- increase allocation, but it does increase the
                -- chance that the constructor won't be allocated at
                -- all in the branches that don't use it.

                    enough_args           = n_val_args >= n_vals_wanted
                    really_interesting_cont | n_val_args <  n_vals_wanted = False       -- Too few args
                                            | n_val_args == n_vals_wanted = interesting_cont
                                            | otherwise                   = True        -- Extra args
                        -- really_interesting_cont tells if the result of the
                        -- call is in an interesting context.

                    small_enough = (size - discount) <= opt_UF_UseThreshold
                    discount     = computeDiscount n_vals_wanted arg_discounts res_discount 
                                                 arg_infos really_interesting_cont
                
    in    
    if dopt Opt_D_dump_inlinings dflags then
        pprTrace "Considering inlining"
                 (ppr id <+> vcat [text "active:" <+> ppr active_inline,
                                   text "arg infos" <+> ppr arg_infos,
                                   text "interesting continuation" <+> ppr interesting_cont,
                                   text "is value:" <+> ppr is_value,
                                   text "is cheap:" <+> ppr is_cheap,
                                   text "guidance" <+> ppr guidance,
                                   text "ANSWER =" <+> if yes_or_no then text "YES" else text "NO"])
                  result
    else
    result
    }

computeDiscount :: Int -> [Int] -> Int -> [Bool] -> Bool -> Int
computeDiscount n_vals_wanted arg_discounts res_discount arg_infos result_used
        -- We multiple the raw discounts (args_discount and result_discount)
        -- ty opt_UnfoldingKeenessFactor because the former have to do with
        --  *size* whereas the discounts imply that there's some extra 
        --  *efficiency* to be gained (e.g. beta reductions, case reductions) 
        -- by inlining.

        -- we also discount 1 for each argument passed, because these will
        -- reduce with the lambdas in the function (we count 1 for a lambda
        -- in size_up).
  = 1 +                 -- Discount of 1 because the result replaces the call
                        -- so we count 1 for the function itself
    length (take n_vals_wanted arg_infos) +
                        -- Discount of 1 for each arg supplied, because the 
                        -- result replaces the call
    round (opt_UF_KeenessFactor * 
           fromIntegral (arg_discount + result_discount))
  where
    arg_discount = sum (zipWith mk_arg_discount arg_discounts arg_infos)

    mk_arg_discount discount is_evald | is_evald  = discount
                                      | otherwise = 0

        -- Don't give a result discount unless there are enough args
    result_discount | result_used = res_discount        -- Over-applied, or case scrut
                    | otherwise   = 0
\end{code}