Andreas Klebinger pushed to branch wip/apk/unfold-dicts at Glasgow Haskell Compiler / GHC

Commits:

5 changed files:

Changes:

  • compiler/GHC/Core/Unfold.hs
    ... ... @@ -30,6 +30,7 @@ module GHC.Core.Unfold (
    30 30 
             updateFunAppDiscount, updateDictDiscount,
    31 31 
             updateVeryAggressive, updateCaseScaling,
    32 32 
             updateCaseThreshold, updateReportPrefix,
    33 
    +        updateUnknownCallArg,
    33 34
    34 35 
             inlineBoringOk, calcUnfoldingGuidance,
    35 36 
             uncondInlineJoin
    ... ... @@ -87,6 +88,9 @@ data UnfoldingOpts = UnfoldingOpts
    87 88 
        , unfoldingCaseScaling :: !Int
    88 89 
           -- ^ Penalize depth with 1/x
    89 90
    91 
    +   , unfoldingUnknownCallArg :: !Int
    92 
    +      -- ^ Penalize depth with 1/x
    93 
    +
    90 94 
        , unfoldingReportPrefix :: !(Maybe String)
    91 95 
           -- ^ Only report inlining decisions for names with this prefix
    92 96 
        }
    ... ... @@ -121,6 +125,11 @@ defaultUnfoldingOpts = UnfoldingOpts
    121 125 
           -- Penalize depth with (size*depth)/scaling
    122 126 
        , unfoldingCaseScaling = 30
    123 127
    128 
    +      -- Makes functions more likely to inline if they apply
    129 
    +      -- a function argument to interesting arguments.
    130 
    +      -- See Note [Discounting for known-at-callsite function calls]
    131 
    +   , unfoldingUnknownCallArg = 10
    132 
    +
    124 133 
           -- Don't filter inlining decision reports
    125 134 
        , unfoldingReportPrefix = Nothing
    126 135 
        }
    ... ... @@ -149,6 +158,11 @@ updateCaseThreshold n opts = opts { unfoldingCaseThreshold = n }
    149 158 
     updateCaseScaling :: Int -> UnfoldingOpts -> UnfoldingOpts
    150 159 
     updateCaseScaling n opts = opts { unfoldingCaseScaling = n }
    151 160
    161 
    +updateUnknownCallArg :: Int -> UnfoldingOpts -> UnfoldingOpts
    162 
    +updateUnknownCallArg n opts = opts { unfoldingUnknownCallArg = n }
    163 
    +
    164 
    +
    165 
    +
    152 166 
     updateReportPrefix :: Maybe String -> UnfoldingOpts -> UnfoldingOpts
    153 167 
     updateReportPrefix n opts = opts { unfoldingReportPrefix = n }
    154 168
    ... ... @@ -335,6 +349,8 @@ isValFun :: CoreExpr -> Bool
    335 349 
     -- one top-level value lambda
    336 350 
     isValFun (Lam b e) | isRuntimeVar b = True
    337 351 
                        | otherwise      = isValFun e
    352 
    +isValFun (Cast e _c) = isValFun e
    353 
    +isValFun (Tick _t e) = isValFun e
    338 354 
     isValFun _                          = False
    339 355
    340 356 
     calcUnfoldingGuidance
    ... ... @@ -709,10 +725,10 @@ sizeExpr opts !bOMB_OUT_SIZE top_args expr
    709 725 
                FCallId _                     -> sizeN (callSize (length val_args) voids)
    710 726 
                DataConWorkId dc              -> conSize    dc (length val_args)
    711 727 
                PrimOpId op _                 -> primOpSize op (length val_args)
    712 
    -           ClassOpId cls _               -> classOpSize opts cls top_args val_args
    728 
    +           ClassOpId cls _               -> classOpSize opts cls top_args val_args voids
    713 729 
                _ | fun `hasKey` buildIdKey   -> buildSize
    714 730 
                  | fun `hasKey` augmentIdKey -> augmentSize
    715 
    -             | otherwise                 -> funSize opts top_args fun (length val_args) voids
    731 
    +             | otherwise                 -> funSize opts top_args fun val_args voids
    716 732
    717 733 
         ------------
    718 734 
         size_up_alt (Alt _con _bndrs rhs) = size_up rhs `addSizeN` 10
    ... ... @@ -777,21 +793,29 @@ litSize _other = 0 -- Must match size of nullary constructors
    777 793 
                           -- Key point: if  x |-> 4, then x must inline unconditionally
    778 794 
                           --            (eg via case binding)
    779 795
    780 
    -classOpSize :: UnfoldingOpts -> Class -> [Id] -> [CoreExpr] -> ExprSize
    796 
    +classOpSize :: UnfoldingOpts -> Class -> [Id] -> [CoreExpr] -> Int -> ExprSize
    781 797 
     -- See (IA1) in Note [Interesting arguments] in GHC.Core.Opt.Simplify.Utils
    782 
    -classOpSize _opts _cls _top_args []
    798 
    +classOpSize _opts _cls _top_args [] _voids
    783 799 
       = sizeZero   -- A non-applied classop
    784 
    -classOpSize opts cls top_args (dict_arg:other_val_args)
    785 
    -  = SizeIs size (arg_discount dict_arg) 0
    800 
    +classOpSize opts cls top_args (dict_arg:other_val_args) voids
    801 
    +  = SizeIs size dict_arg_discount 0
    786 802 
       where
    787 
    -    size | isUnaryClass cls = 0    -- See (UCM4) in Note [Unary class magic] in GHC.Core.TyCon
    788 
    -         | otherwise        = 20 + (10 * length other_val_args)
    803 
    +    -- See (UCM4) in Note [Unary class magic] in GHC.Core.TyCon
    804 
    +    op_app_size = if isUnaryClass cls then 0 else 20
    805 
    +
    806 
    +    -- Size penalty for applying the extracted class method to it's
    807 
    +    -- arguments.
    808 
    +    method_app_size = callSize (length other_val_args) voids
    809 
    +
    810 
    +    size = op_app_size + method_app_size
    789 811
    790 812 
         -- If the class op is scrutinising a lambda bound dictionary then
    791 813 
         -- give it a discount, to encourage the inlining of this function
    792 
    -    arg_discount (Cast arg _co)                    = arg_discount arg
    793 
    -    arg_discount (Var dict) | dict `elem` top_args = unitBag (dict, dict_discount)
    794 
    -    arg_discount _                                 = emptyBag
    814 
    +    dict_arg_discount = case getIdFromTrivialExpr_maybe dict_arg of
    815 
    +      Nothing -> emptyBag
    816 
    +      Just dict
    817 
    +        | dict `elem` top_args -> unitBag (dict, dict_discount)
    818 
    +        | otherwise -> emptyBag
    795 819
    796 820 
         -- If we have (class-op d arg1 .. argn) then it's super-good to inline
    797 821 
         -- to expose `d`; not only can we do the dictionary selection
    ... ... @@ -800,7 +824,9 @@ classOpSize opts cls top_args (dict_arg:other_val_args)
    800 824 
         -- See the discussion on #26831, esp "Delicate inlining".
    801 825 
         dict_discount
    802 826 
           | null other_val_args = unfoldingDictDiscount opts
    803 
    -      | otherwise           = unfoldingDictDiscount opts + unfoldingFunAppDiscount opts
    827 
    +      | otherwise           = unfoldingDictDiscount opts + unfoldingFunAppDiscount opts +
    828 
    +                                -- See Note [Discounting for known-at-callsite function calls]
    829 
    +                              unknownFunArgDiscount opts top_args other_val_args
    804 830
    805 831 
     -- | The size of a function call
    806 832 
     callSize
    ... ... @@ -826,12 +852,13 @@ jumpSize _n_val_args _voids = 0 -- Jumps are small, and we don't want penalise
    826 852 
       -- spectral/puzzle. TODO Perhaps adjusting the default threshold would be a
    827 853 
       -- better solution?
    828 854
    829 
    -funSize :: UnfoldingOpts -> [Id] -> Id -> Int -> Int -> ExprSize
    855 
    +funSize :: UnfoldingOpts -> [Id] -> Id -> [CoreExpr] -> Int -> ExprSize
    830 856 
     -- Size for function calls where the function is not a constructor or primops
    831 857 
     -- Note [Function applications]
    832 
    -funSize opts top_args fun n_val_args voids
    858 
    +funSize opts top_args fun val_args voids
    833 859 
       | otherwise = SizeIs size arg_discount res_discount
    834 860 
       where
    861 
    +    n_val_args = length val_args
    835 862 
         some_val_args = n_val_args > 0
    836 863 
         is_join = isJoinId fun
    837 864
    ... ... @@ -839,10 +866,14 @@ funSize opts top_args fun n_val_args voids
    839 866 
              | not some_val_args    = 0
    840 867 
              | otherwise            = callSize n_val_args voids
    841 868
    869 
    +    fun_discount
    870 
    +      | fun `elem` top_args = unfoldingFunAppDiscount opts + unknownFunArgDiscount opts top_args val_args
    871 
    +      | otherwise = unfoldingFunAppDiscount opts
    872 
    +
    842 873 
             --                  DISCOUNTS
    843 874 
             --  See Note [Function and non-function discounts]
    844 875 
         arg_discount | some_val_args && fun `elem` top_args
    845 
    -                 = unitBag (fun, unfoldingFunAppDiscount opts)
    876 
    +                 = unitBag (fun, fun_discount)
    846 877 
                      | otherwise = emptyBag
    847 878 
             -- If the function is an argument and is applied
    848 879 
             -- to some values, give it an arg-discount
    ... ... @@ -864,7 +895,64 @@ conSize dc n_val_args
    864 895 
     -- See Note [Constructor size and result discount]
    865 896 
       | otherwise = SizeIs 10 emptyBag 10
    866 897
    867 
    -{- Note [Constructor size and result discount]
    898 
    +-- See Note [Discounting for known-at-callsite function calls]
    899 
    +unknownFunArgDiscount :: UnfoldingOpts -> [Id] -> [CoreExpr] -> Int
    900 
    +unknownFunArgDiscount opts top_args args = sum (map arg_discount args)
    901 
    +  where
    902 
    +    arg_discount arg
    903 
    +      | interestingArg arg = unfoldingUnknownCallArg opts
    904 
    +      | otherwise          = 0
    905 
    +
    906 
    +    -- Little brother to the simplifier's interestingArg.
    907 
    +    -- Use trivial_expr_fold to look through casts, ticks and type applications,
    908 
    +    -- in a principled manner.
    909 
    +    interestingVar v = v `elem` top_args || exprIsConLike (Var v)
    910 
    +    interestingArg = trivial_expr_fold interestingVar (const True) False True
    911 
    +
    912 
    +{-
    913 
    +Note [Discounting for known-at-callsite function calls]
    914 
    +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    915 
    +A regular unknown function call `f x y` inside some function `foo` provides no
    916 
    +optimization opportunities to improve `foo` no matter what shape x and y have.
    917 
    +
    918 
    +However we might have a pattern where a function argument is applied to
    919 
    +interesting arguments like:
    920 
    +
    921 
    +    foo f g x = ... f x ... g g ...
    922 
    +    bar = foo snd snd (1,2)
    923 
    +
    924 
    +Here we really want to inline `foo`, as it will expose `snd` to the tuple, causing
    925 
    +it to inline and eliminating the tuple allocation completely.
    926 
    +
    927 
    +Note that this doesn't always require the function argument itself to be inlined.
    928 
    +Inlining `foo` will also expose the strictness and W/W properties of foos function
    929 
    +arguments and allows specConstr to fire on them. There is simple a large number of
    930 
    +optimizations that can happen for known functions that are impossible for unknown
    931 
    +calls.
    932 
    +
    933 
    +So here is the plan: Whenever the argument to `f` could be useful for optimizing
    934 
    +`foo` if `f` is a known call we give `f` a discount.
    935 
    +
    936 
    +This includes:
    937 
    +
    938 
    +* The argument is a top_arg itself. (Think `f id 1` with `f g = g`)
    939 
    +* The argument is con like: This can help rules, W/W, SpecConstr, further inlining.
    940 
    +* The argument is a literal: Rules/Inlining
    941 
    +* The argument is non-trivial:
    942 
    +    + If it's a thunk strictness might allow eager evaluationg
    943 
    +    + If it's a pap/lambda we might be able to eta-expand it, removing an intermediate pap
    944 
    +      or even removing the PAP fully.
    945 
    +
    946 
    +However we have to be careful. It's *not* a given that we actually
    947 
    +get a benefit from inlining such a call into it's context. It fully
    948 
    +depends on the specific arguments. So we simply make those interesting
    949 
    +arguments "free" rather charging the usual cost of 10 per applied arg.
    950 
    +
    951 
    +Similarly we *only* should give this discount to a unknown call. If the function
    952 
    +`f` being called inside `foo` is a known function all those optimizations can
    953 
    +happen inside foo without inlining it into it's call sites.
    954 
    +
    955 
    +Note [Constructor size and result discount]
    868 956 
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    869 957 
     Treat a constructors application as size 10, regardless of how many
    870 958 
     arguments it has; we are keen to expose them (and we charge separately

  • compiler/GHC/Core/Unfold.hs-boot
    ... ... @@ -13,3 +13,4 @@ updateDictDiscount :: Int -> UnfoldingOpts -> UnfoldingOpts
    13 13 
     updateVeryAggressive    :: Bool -> UnfoldingOpts -> UnfoldingOpts
    14 14 
     updateCaseThreshold     :: Int -> UnfoldingOpts -> UnfoldingOpts
    15 15 
     updateCaseScaling       :: Int -> UnfoldingOpts -> UnfoldingOpts
    16 
    +updateUnknownCallArg    :: Int -> UnfoldingOpts -> UnfoldingOpts

  • compiler/GHC/Core/Utils.hs
    ... ... @@ -1654,7 +1654,9 @@ it off at source.
    1654 1654
    1655 1655 
     {-# INLINE trivial_expr_fold #-}
    1656 1656 
     trivial_expr_fold :: (Id -> r) -> (Literal -> r) -> r -> r -> CoreExpr -> r
    1657 
    --- ^ The worker function for Note [exprIsTrivial] and Note [getIdFromTrivialExpr]
    1657 
    +-- ^  k_id k_lit k_triv k_not_triv
    1658 
    +--
    1659 
    +-- The worker function for Note [exprIsTrivial] and Note [getIdFromTrivialExpr]
    1658 1660 
     -- This is meant to have the code of both functions in one place and make it
    1659 1661 
     -- easy to derive custom predicates.
    1660 1662 
     --

  • compiler/GHC/Driver/Session.hs
    ... ... @@ -1881,6 +1881,8 @@ dynamic_flags_deps = [
    1881 1881 
           (intSuffix   (\n d -> d { unfoldingOpts = updateCaseThreshold n (unfoldingOpts d)}))
    1882 1882 
       , make_ord_flag defFlag "funfolding-case-scaling"
    1883 1883 
           (intSuffix   (\n d -> d { unfoldingOpts = updateCaseScaling n (unfoldingOpts d)}))
    1884 
    +  , make_ord_flag defFlag "funfolding-unknown-call-arg-discount"
    1885 
    +      (intSuffix   (\n d -> d { unfoldingOpts = updateUnknownCallArg n (unfoldingOpts d)}))
    1884 1886
    1885 1887 
       , make_dep_flag defFlag "funfolding-keeness-factor"
    1886 1888 
           (floatSuffix (\_ d -> d))

  • docs/users_guide/using-optimisation.rst
    ... ... @@ -1902,6 +1902,26 @@ as such you shouldn't need to set any of them explicitly. A flag
    1902 1902 
         recommended. Values in the range 10 <= n <= 20 allow some inlining to take place
    1903 1903 
         while still allowing GHC to compile modules containing such inlining loops.
    1904 1904
    1905 
    +.. ghc-flag:: -funfolding-unknown-call-arg-discount=⟨n⟩
    1906 
    +    :shortdesc: *default: 10.* Discount for each interesting arg applied to a unknown function.
    1907 
    +    :type: dynamic
    1908 
    +    :category:
    1909 
    +
    1910 
    +    :default: 10
    1911 
    +
    1912 
    +    .. index::
    1913 
    +       single: inlining, controlling
    1914 
    +       single: unfolding, controlling
    1915 
    +
    1916 
    +    Typically a function like ``foo f x`` is not much more likely to inline if
    1917 
    +    ``f`` is a known argument.
    1918 
    +
    1919 
    +    With this discount being given we make GHC more eager to inline ``foo``
    1920 
    +    if ``f`` is applied to interesting arguments inside the RHS of ``foo``.
    1921 
    +
    1922 
    +    This optimizes cases where other optimizations can fire on the call to ``f``
    1923 
    +    after it has been made a known call by inlining ``foo`` into it's call site.
    1924 
    +
    1905 1925
    1906 1926 
     .. ghc-flag:: -fworker-wrapper
    1907 1927 
         :shortdesc: Enable the worker/wrapper transformation. Implied by :ghc-flag:`-O`

    • —
    View it on GitLab.
    You're receiving this email because of your account on gitlab.haskell.org. Manage all notifications · Help Notification message regarding https://gitlab.haskell.org/ghc/ghc/-/compare/3520030fa377abd59eaca4a61d16f38ee7c95b44...697dddd3a3c2641b3c4217b195a7889f8472f942 at 1789472497