Magnus pushed to branch wip/mangoiv/9.12.5-rc4 at Glasgow Haskell Compiler / GHC

Commits:

9 changed files:

Changes:

  • changelog.d/27717
    1 
    +section: compiler
    2 
    +synopsis: Fix a bug where -fspec-eval-dictfun could speculatively evaluate a
    3 
    +  looping dictionary whose recursion went through an hs-boot import, hanging
    4 
    +  the program.
    5 
    +mrs: !16519
    6 
    +issues: #27717

  • compiler/GHC/CoreToStg/Prep.hs
    ... ... @@ -1892,87 +1892,131 @@ long as the callee might evaluate it. And if it is evaluated on
    1892 1892 
     most code paths anyway, we get to turn the unknown eval in the
    1893 1893 
     callee into a known call at the call site.
    1894 1894
    1895 
    -Very Nasty Wrinkle
    1895 
    +(SEV1) There is a very nasty wrinkle: we must be very careful not to speculate
    1896 
    +       recursive calls!  Doing so might well change termination behavior.
    1897 
    +
    1898 
    +       That comes up in practice for DFuns, which are considered ok-for-spec,
    1899 
    +       because they always immediately return a constructor.
    1900 
    +       See Note [NON-BOTTOM-DICTS invariant] in GHC.Core.
    1901 
    +
    1902 
    +       But not so if you speculate the recursive call, as #20836 shows:
    1903 
    +
    1904 
    +         class Foo m => Foo m where
    1905 
    +           runFoo :: m a -> m a
    1906 
    +         newtype Trans m a = Trans { runTrans :: m a }
    1907 
    +         instance Monad m => Foo (Trans m) where
    1908 
    +           runFoo = id
    1909 
    +
    1910 
    +       (NB: class Foo m => Foo m` looks weird and needs -XUndecidableSuperClasses. The
    1911 
    +       example in #20836 is more compelling, but boils down to the same thing.)
    1912 
    +       This program compiles to the following DFun for the `Trans` instance:
    1913 
    +
    1914 
    +         Rec {
    1915 
    +         $fFooTrans
    1916 
    +           = \ @m $dMonad -> C:Foo ($fFooTrans $dMonad) (\ @a -> id)
    1917 
    +         end Rec }
    1918 
    +
    1919 
    +       Note that the DFun immediately terminates and produces a dictionary, just
    1920 
    +       like DFuns ought to, but it calls itself recursively to produce the `Foo m`
    1921 
    +       dictionary. But alas, if we treat `$fFooTrans` as always-terminating, so
    1922 
    +       that we can speculate its calls, and hence use call-by-value, we get:
    1923 
    +
    1924 
    +         $fFooTrans
    1925 
    +           = \ @m $dMonad -> case ($fFooTrans $dMonad) of sc ->
    1926 
    +                             C:Foo sc (\ @a -> id)
    1927 
    +
    1928 
    +       and that's an infinite loop!
    1929 
    +       Note that this bad-ness only happens in `$fFooTrans`'s own RHS. In the
    1930 
    +       *body* of the letrec, it's absolutely fine to use call-by-value on
    1931 
    +       `foo ($fFooTrans d)`.
    1932 
    +
    1933 
    +       Our solution is this: we track in cpe_rec_ids the set of enclosing
    1934 
    +       recursively-bound Ids, the RHSs of which we are currently transforming and then
    1935 
    +       in 'exprOkForSpecEval' (a special entry point to 'exprOkForSpeculation',
    1936 
    +       basically) we'll say that any binder in this set is not ok-for-spec.
    1937 
    +
    1938 
    +       Note if we have a letrec group `Rec { f1 = rhs1; ...; fn = rhsn }`, and we
    1939 
    +       prep up `rhs1`, we have to include not only `f1`, but all binders of the group
    1940 
    +       `f1..fn` in this set, otherwise our fix is not robust wrt. mutual recursive
    1941 
    +       DFuns.
    1942 
    +
    1943 
    +       NB: If at some point we decide to have a termination analysis for general
    1944 
    +       functions (#8655, !1866), we need to take similar precautions for (guarded)
    1945 
    +       recursive functions:
    1946 
    +
    1947 
    +         repeat x = x : repeat x
    1948 
    +
    1949 
    +       Same problem here: As written, repeat evaluates rapidly to WHNF. So `repeat x`
    1950 
    +       is a cheap call that we are willing to speculate, but *not* in repeat's RHS.
    1951 
    +       Fortunately, pce_rec_ids already has all the information we need in that case.
    1952 
    +
    1953 
    +       The problem is very similar to Note [Eta reduction in recursive RHSs].
    1954 
    +       Here as well as there it is *unsound* to change the termination properties
    1955 
    +       of the very function whose termination properties we are exploiting.
    1956 
    +
    1957 
    +       It is also similar to Note [Do not strictify a DFun's parameter dictionaries],
    1958 
    +       where marking recursive DFuns (of undecidable *instances*) strict in dictionary
    1959 
    +       *parameters* leads to quite the same change in termination as above.
    1960 
    +
    1961 
    +(SEV2) The situation in (SEV1) can cross modules.  `cpe_rec_ids` is module-local,
    1962 
    +       so it does not catch a recursion that goes through an hs-boot import.
    1963 
    +       Suppose Mid and Callee form a module loop, and Mid sees Callee through its
    1964 
    +       hs-boot file:
    1965 
    +
    1966 
    +         -- Mid.hs
    1967 
    +         $fCAT = \ @a $dCB -> C:CA ($fxCBT $dCB) ...
    1968 
    +         -- Callee.hs
    1969 
    +         $fCBT = \ @a $dCB -> C:CB ($fCAT  $dCB) ...
    1970 
    +
    1971 
    +       Neither module can see that these two call each other, so each looks
    1972 
    +       non-recursive, and we speculate the inner call in both:
    1973 
    +
    1974 
    +         $fCAT = \ @a $dCB -> case $fxCBT $dCB of s { __DEFAULT -> C:CA s ... }
    1975 
    +         $fCBT = \ @a $dCB -> case $fCAT  $dCB of s { __DEFAULT -> C:CB s ... }
    1976 
    +
    1977 
    +       Now each forces the other and the program loops. Such a cycle must cross an
    1978 
    +       hs-boot edge, so we do not speculate a call whose callee has a BootUnfolding.
    1979 
    +       Note [Inlining and hs-boot files] in GHC.CoreToIface does the same for
    1980 
    +       infinite inlining.
    1981 
    +
    1982 
    +(SEV3) Belt and braces: do not speculate absent bindings.
    1983 
    +
    1984 
    +       In 'decideFloatInfo' we decline to speculate a binding whose demand is
    1985 
    +       absent.  There is no point in speculating an absent binding, since its
    1986 
    +       value is (presumably) not needed.
    1987 
    +
    1988 
    +       This used to matter more. Worker/wrapper would bind an absent dictionary
    1989 
    +       to a rubbish literal filler, and speculation could force a superclass
    1990 
    +       selection out of that rubbish literal, causing a segfault (#25924).
    1991 
    +       Nowadays we never make a filler for a dictionary in the first place, so
    1992 
    +       this can no longer happen and the guard is merely belt and braces.
    1993 
    +       See Note [Don't make fillers for constraint types]
    1994 
    +       in GHC.Core.Opt.WorkWrap.Utils.
    1896 1995
    1897 
    -We must be very careful not to speculate recursive calls!  Doing so
    1898 
    -might well change termination behavior.
    1996 
    +Note [Controlling Speculative Evaluation]
    1997 
    +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    1899 1998
    1900 
    -That comes up in practice for DFuns, which are considered ok-for-spec,
    1901 
    -because they always immediately return a constructor.
    1902 
    -See Note [NON-BOTTOM-DICTS invariant] in GHC.Core.
    1999 
    +Most of the time, speculative evaluation in the coreprep phase has a positive
    2000 
    +effect on performance, however we have found that some forms of speculative
    2001 
    +evaluation can lead to large performance regressions. See #25284.
    1903 2002
    1904 
    -But not so if you speculate the recursive call, as #20836 shows:
    2003 
    +Therefore we have some flags to control which types of speculative evaluation
    2004 
    +are done:
    1905 2005
    1906 
    -  class Foo m => Foo m where
    1907 
    -    runFoo :: m a -> m a
    1908 
    -  newtype Trans m a = Trans { runTrans :: m a }
    1909 
    -  instance Monad m => Foo (Trans m) where
    1910 
    -    runFoo = id
    2006 
    +  -fspec-eval
    2007 
    +     Globally enable/disable speculative evaluation ( -fno-spec-eval also turns
    2008 
    +     off all other speculative evaluation). On by default for all
    2009 
    +     optimization levels. Turning on this flag by itself should never cause
    2010 
    +     a performance regression. Please open a ticket if you find any.
    1911 2011
    1912 
    -(NB: class Foo m => Foo m` looks weird and needs -XUndecidableSuperClasses. The
    1913 
    -example in #20836 is more compelling, but boils down to the same thing.)
    1914 
    -This program compiles to the following DFun for the `Trans` instance:
    2012 
    +  -fspec-eval-dictfun
    2013 
    +     Enable speculative evaluation for dictionary functions. Off by default
    2014 
    +     since it can cause an increase in allocations (#24284). We have no
    2015 
    +     examples that show a large performance improvement when turning on this
    2016 
    +     flag. Please open a ticket if you find any.
    1915 2017
    1916 
    -  Rec {
    1917 
    -  $fFooTrans
    1918 
    -    = \ @m $dMonad -> C:Foo ($fFooTrans $dMonad) (\ @a -> id)
    1919 
    -  end Rec }
    1920 
    -
    1921 
    -Note that the DFun immediately terminates and produces a dictionary, just
    1922 
    -like DFuns ought to, but it calls itself recursively to produce the `Foo m`
    1923 
    -dictionary. But alas, if we treat `$fFooTrans` as always-terminating, so
    1924 
    -that we can speculate its calls, and hence use call-by-value, we get:
    1925 
    -
    1926 
    -  $fFooTrans
    1927 
    -    = \ @m $dMonad -> case ($fFooTrans $dMonad) of sc ->
    1928 
    -                      C:Foo sc (\ @a -> id)
    1929 
    -
    1930 
    -and that's an infinite loop!
    1931 
    -Note that this bad-ness only happens in `$fFooTrans`'s own RHS. In the
    1932 
    -*body* of the letrec, it's absolutely fine to use call-by-value on
    1933 
    -`foo ($fFooTrans d)`.
    1934 
    -
    1935 
    -Our solution is this: we track in cpe_rec_ids the set of enclosing
    1936 
    -recursively-bound Ids, the RHSs of which we are currently transforming and then
    1937 
    -in 'exprOkForSpecEval' (a special entry point to 'exprOkForSpeculation',
    1938 
    -basically) we'll say that any binder in this set is not ok-for-spec.
    1939 
    -
    1940 
    -Note if we have a letrec group `Rec { f1 = rhs1; ...; fn = rhsn }`, and we
    1941 
    -prep up `rhs1`, we have to include not only `f1`, but all binders of the group
    1942 
    -`f1..fn` in this set, otherwise our fix is not robust wrt. mutual recursive
    1943 
    -DFuns.
    1944 
    -
    1945 
    -NB: If at some point we decide to have a termination analysis for general
    1946 
    -functions (#8655, !1866), we need to take similar precautions for (guarded)
    1947 
    -recursive functions:
    1948 
    -
    1949 
    -  repeat x = x : repeat x
    1950 
    -
    1951 
    -Same problem here: As written, repeat evaluates rapidly to WHNF. So `repeat x`
    1952 
    -is a cheap call that we are willing to speculate, but *not* in repeat's RHS.
    1953 
    -Fortunately, pce_rec_ids already has all the information we need in that case.
    1954 
    -
    1955 
    -The problem is very similar to Note [Eta reduction in recursive RHSs].
    1956 
    -Here as well as there it is *unsound* to change the termination properties
    1957 
    -of the very function whose termination properties we are exploiting.
    1958 
    -
    1959 
    -It is also similar to Note [Do not strictify a DFun's parameter dictionaries],
    1960 
    -where marking recursive DFuns (of undecidable *instances*) strict in dictionary
    1961 
    -*parameters* leads to quite the same change in termination as above.
    1962 
    -
    1963 
    -Belt and braces: do not speculate absent bindings
    1964 
    -
    1965 
    -In 'decideFloatInfo' we decline to speculate a binding whose demand is absent.
    1966 
    -There is no point in speculating an absent binding, since its value is
    1967 
    -(presumably) not needed.
    1968 
    -
    1969 
    -This used to matter more. Worker/wrapper would bind an absent dictionary to a
    1970 
    -rubbish literal filler, and speculation could force a superclass selection out
    1971 
    -of that rubbish literal, causing a segfault (#25924). Nowadays we never make a
    1972 
    -filler for a dictionary in the first place, so this can no longer happen and
    1973 
    -the guard is merely belt and braces.
    1974 
    -See Note [Don't make fillers for constraint types]
    1975 
    -in GHC.Core.Opt.WorkWrap.Utils.
    2018 
    +Also see the optimization section in the User's Guide for the description of
    2019 
    +these flags and when to use them.
    1976 2020
    1977 2021 
     Note [BindInfo and FloatInfo]
    1978 2022 
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    ... ... @@ -2030,16 +2074,6 @@ conceptually.
    2030 2074 
     See also Note [Floats and FloatDecision] for how we maintain whole groups of
    2031 2075 
     floats and how far they go.
    2032 2076
    2033 
    -Note [Controlling Speculative Evaluation]
    2034 
    -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    2035 
    -
    2036 
    -Most of the time, speculative evaluation has a positive effect on performance,
    2037 
    -but we have found a case where speculative evaluation of dictionary functions
    2038 
    -leads to a performance regression #25284.
    2039 
    -
    2040 
    -Therefore we have some flags to control it. See the optimization section in
    2041 
    -the User's Guide for the description of these flags and when to use them.
    2042 
    -
    2043 2077 
     Note [Floats and FloatDecision]
    2044 2078 
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    2045 2079 
     We have a special datatype `Floats` for modelling a telescope of `FloatingBind`
    ... ... @@ -2243,11 +2277,18 @@ mkNonRecFloat env is_unlifted bndr rhs
    2243 2277 
         ok_for_spec = exprOkForSpecEval call_ok_for_spec rhs
    2244 2278 
         -- See Note [Controlling Speculative Evaluation]
    2245 2279 
         call_ok_for_spec x
    2246 
    -      | is_rec_call x                           = False
    2247 
    -      | not (cp_specEval cfg)                   = False
    2248 
    -      | not (cp_specEvalDFun cfg) && isDFunId x = False
    2280 
    +      -- See Note [Speculative evaluation]
    2281 
    +      | is_rec_call x                           = False  -- See (SEV1)
    2282 
    +      | is_boot_call x                          = False  -- See (SEV2)
    2283 
    +
    2284 
    +      -- See [Controlling speculative evaluation]
    2285 
    +      | not (cp_specEval cfg)                   = False  -- Flag -fspec-eval
    2286 
    +      | not (cp_specEvalDFun cfg) && isDFunId x = False  -- Flag -fspec-eval-dictfun
    2287 
    +
    2249 2288 
           | otherwise                               = True
    2250 
    -    is_rec_call = (`elemUnVarSet` cpe_rec_ids env)
    2289 
    +    is_rec_call  = (`elemUnVarSet` cpe_rec_ids env)
    2290 
    +    is_boot_call = isBootUnfolding . realIdUnfolding
    2291 
    +      -- See Note [Speculative evaluation], Very Nasty Wrinkle
    2251 2292 
         is_data_con = isJust . isDataConId_maybe
    2252 2293
    2253 2294 
     -- | Wrap floats around an expression

  • testsuite/tests/core-to-stg/T27717/Callee.hs
    1 
    +{-# LANGUAGE UndecidableInstances, FlexibleInstances, FlexibleContexts #-}
    2 
    +module Callee where
    3 
    +
    4 
    +import Ty
    5 
    +import Mid
    6 
    +
    7 
    +instance CB a => CB (T a) where
    8 
    +  opB _ = 2
    9 
    +
    10 
    +instance CB Int where
    11 
    +  opB _ = 8

  • testsuite/tests/core-to-stg/T27717/Callee.hs-boot
    1 
    +{-# LANGUAGE FlexibleInstances, UndecidableInstances #-}
    2 
    +module Callee where
    3 
    +
    4 
    +import Ty
    5 
    +
    6 
    +instance CB a => CB (T a)
    7 
    +instance CB Int

  • testsuite/tests/core-to-stg/T27717/Main.hs
    1 
    +module Main where
    2 
    +import Mid
    3 
    +import Callee ()
    4 
    +
    5 
    +main :: IO ()
    6 
    +main = print (g (1 :: Int))

  • testsuite/tests/core-to-stg/T27717/Mid.hs
    1 
    +{-# LANGUAGE UndecidableInstances, FlexibleInstances, FlexibleContexts #-}
    2 
    +{-# LANGUAGE GADTs, ConstraintKinds, ScopedTypeVariables #-}
    3 
    +module Mid where
    4 
    +
    5 
    +import Ty
    6 
    +import {-# SOURCE #-} Callee
    7 
    +
    8 
    +-- $fCATa calls Callee's $fxCBT, and that calls this one back.  The cycle runs
    9 
    +-- through the hs-boot import, so both dfuns are NonRec in their own module and
    10 
    +-- cpe_rec_ids cannot see it.  Speculating either one loops.
    11 
    +instance CB a => CA (T a) where
    12 
    +  opA _ = 1
    13 
    +
    14 
    +instance CA Int where
    15 
    +  opA _ = 9
    16 
    +
    17 
    +data Dict c where
    18 
    +  Dict :: c => Dict c
    19 
    +
    20 
    +{-# NOINLINE keep #-}
    21 
    +keep :: [Dict c] -> Int
    22 
    +keep xs = length xs + 41
    23 
    +
    24 
    +{-# NOINLINE g #-}
    25 
    +g :: forall a. CB a => a -> Int
    26 
    +g _ = keep [Dict :: Dict (CA (T a))]

  • testsuite/tests/core-to-stg/T27717/T27717.stdout
    1 
    +42

  • testsuite/tests/core-to-stg/T27717/Ty.hs
    1 
    +{-# LANGUAGE UndecidableSuperClasses #-}
    2 
    +module Ty where
    3 
    +
    4 
    +data T a = MkT a
    5 
    +
    6 
    +class CB a => CA a where
    7 
    +  opA :: a -> Int
    8 
    +
    9 
    +class CA a => CB a where
    10 
    +  opB :: a -> Int

  • testsuite/tests/core-to-stg/T27717/all.T
    1 
    +test('T27717',
    2 
    +     [extra_files(['Main.hs', 'Mid.hs', 'Ty.hs', 'Callee.hs', 'Callee.hs-boot'])],
    3 
    +     multimod_compile_and_run,
    4 
    +     ['Main', '-O -fspec-eval-dictfun'])

    • —
    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/-/commit/785781c580f67e65790e40c5c0fb5c77b72be825 at 1788531934