Opened 3 years ago

Last modified 13 months ago

#11371 new bug

Bogus in-scope set in substitutions

Reported by: simonpj Owned by: niteria
Priority: high Milestone: 8.4.1
Component: Compiler Version: 7.10.3
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: #11360 Differential Rev(s): phab:D1792, phab:D1801, phab:D1802
Wiki Page:

Description (last modified by simonpj)

Bartosz reports that substitution isn't working properly for him. He cites this Note in TyCoRep:

-- Note [Generating the in-scope set for a substitution]
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-- If we want to substitute [a -> ty1, b -> ty2] I used to
-- think it was enough to generate an in-scope set that includes
-- fv(ty1,ty2).  But that's not enough; we really should also take the
-- free vars of the type we are substituting into!  Example:
--      (forall b. (a,b,x)) [a -> List b]
-- Then if we use the in-scope set {b}, there is a danger we will rename
-- the forall'd variable to 'x' by mistake, getting this:
--      (forall x. (List b, x, x))
-- Urk!  This means looking at all the calls to mkOpenTCvSubst....

I think this is an outright bug that has been lurking for ages, and which Bartosz has just managed to tickle.

Things to do:

  • We should add an ASSERT to substTy (and similar functions): when calling substTy subst ty it should be the case that the in-scope set in the substitution is a superset of both
    • The free vars of the range of the substitution
    • The free vars of ty minus the domain of the substitution

That ASSERT could be added to the immediate callers of subst_ty in TyCoRep.

(Bartosz: if you add that you should find that it trips before the bug you are actually getting.)

  • How to fix it properly? The places to look are: everywhere that uses (transitively) one of the mkOpenTCvSubst or zipOpenTCvSubst functions.
    • Many calls to mkOpenTCvSubst produce a substitution that is only applied to closed types; or at least to types whose only free variables are the ones in the domain of the substitution. Example: the call to zipOpenTCvSubst in DataCon.dataConInstSig. These ones will all satisfy the ASSERT

    • In other cases, we already have the in-scope set in hand. Example: in CoreLint.lintTyApp we find a call to substTyWith. But Lint carries an in-scope set, so it would be easy to pass it to substTyWith.

    • Finally there may be cases where we really have to take the free vars of the type we are substituting into, and add them to the in-scope set.

Doubtless all this applies to substituting in coercions too, and indeed into expressions.

Change History (63)

comment:1 Changed 3 years ago by niteria

I believe #11360 is one symptom of this.

comment:2 Changed 3 years ago by niteria

Owner: set to niteria

comment:3 Changed 3 years ago by niteria

Differential Rev(s): phab:D1792

comment:4 Changed 3 years ago by simonpj

Description: modified (diff)

comment:5 Changed 3 years ago by Bartosz Nitka <niteria@…>

In 9d33adb6/ghc:

Check InScopeSet in substTy and provide substTyUnchecked

This adds sanity checks to `substTy` that implement:

> when calling substTy subst ty it should be the case that the in-scope
> set in the substitution is a superset of
> * The free vars of the range of the substitution
> * The free vars of ty minus the domain of the substitution

and replaces violators with unchecked version. The violators were found
by running the GHC test suite.

This ensures that I can work on this incrementally and that what I fix won't
be undone by some other change.

It also includes a couple of fixes that I've already done.

Test Plan: ./validate

Reviewers: simonmar, goldfire, simonpj, austin, bgamari

Reviewed By: simonpj, bgamari

Subscribers: thomie

Differential Revision: https://phabricator.haskell.org/D1792

GHC Trac Issues: #11371

comment:6 Changed 3 years ago by thomie

niteria: this commit is causing some test failures on Travis:

Unexpected failures:
   ghci.debugger/scripts           T2740 [bad stderr] (ghci)
   ghci.debugger/scripts           break001 [bad stderr] (ghci)
   ghci.debugger/scripts           break003 [bad stderr] (ghci)
   ghci.debugger/scripts           break005 [bad stderr] (ghci)
   ghci.debugger/scripts           break006 [bad stderr] (ghci)
   ghci.debugger/scripts           break009 [bad stdout] (ghci)
   ghci.debugger/scripts           break010 [bad exit code] (ghci)
   ghci.debugger/scripts           break011 [bad stdout] (ghci)
   ghci.debugger/scripts           break012 [bad stderr] (ghci)
   ghci.debugger/scripts           break017 [bad stdout] (ghci)
   ghci.debugger/scripts           break018 [bad stderr] (ghci)
   ghci.debugger/scripts           break020 [bad stderr] (ghci)
   ghci.debugger/scripts           break021 [bad stderr] (ghci)
   ghci.debugger/scripts           break026 [bad stderr] (ghci)
   ghci.debugger/scripts           break027 [bad stderr] (ghci)
   ghci.debugger/scripts           break028 [bad stderr] (ghci)
   ghci.debugger/scripts           dynbrk002 [bad stderr] (ghci)
   ghci.debugger/scripts           hist001 [bad stderr] (ghci)
   ghci.debugger/scripts           print003 [bad stderr] (ghci)
   ghci.debugger/scripts           print005 [bad stderr] (ghci)
   ghci.debugger/scripts           print006 [bad stderr] (ghci)
   ghci.debugger/scripts           print008 [bad stderr] (ghci)
   ghci.debugger/scripts           print010 [bad stderr] (ghci)
   ghci.debugger/scripts           print018 [bad stderr] (ghci)
   ghci.debugger/scripts           print019 [bad stderr] (ghci)
   ghci.debugger/scripts           print022 [bad stderr] (ghci)
   ghci.debugger/scripts           print025 [bad stderr] (ghci)
   ghci.debugger/scripts           print029 [bad stderr] (ghci)
   ghci.debugger/scripts           print030 [bad stderr] (ghci)
   ghci.debugger/scripts           print031 [bad stderr] (ghci)
   ghci.debugger/scripts           print032 [bad stderr] (ghci)
   ghci.debugger/scripts           result001 [bad stderr] (ghci)
   ghci.debugger/scripts/break022  break022 [bad stderr] (ghci)
   indexed-types/should_compile    T3023 [exit code non-0] (normal)
   overloadedrecflds/ghci          overloadedlabelsghci01 [bad stdout] (ghci)
   polykinds                       T6015 [exit code non-0] (normal)
   polykinds                       T6015a [exit code non-0] (normal)
   polykinds                       T6068 [bad stderr] (ghci)
   polykinds                       T7332 [exit code non-0] (normal)
   typecheck/should_compile        T4969 [exit code non-0] (normal)
   typecheck/should_compile        tc125 [exit code non-0] (normal)
   typecheck/should_compile        tc126 [exit code non-0] (normal)
   typecheck/should_compile        tc152 [exit code non-0] (normal)
   typecheck/should_compile        tc180 [exit code non-0] (normal)
   typecheck/should_compile        tc187 [exit code non-0] (normal)
   typecheck/should_fail           tcfail093 [exit code non-0] (normal)

Here's one of them:

ghc-stage2: panic! (the 'impossible' happened)
  (GHC version 8.1.20160119 for x86_64-unknown-linux):
	ASSERT failed!
  CallStack (from ImplicitParams):
  assertPprPanic, called at compiler/types/TyCoRep.hs:1827:61 in ghc:TyCoRep
  substTy, called at compiler/typecheck/FunDeps.hs:289:35 in ghc:FunDeps
  in_scope InScope [a3vr :-> k_a3vr, a3vs :-> a_a3vs,
                    a3wU :-> t_a3wU[tau:3], a3wV :-> t_a3wV[tau:3]]
  tenv [a3vr :-> TYPE t_a3wU[tau:3], a3vs :-> t_a3wV[tau:3]]
  cenv []
  ty b_a3vt
  needInScope [a3vt :-> b_a3vt]

Please report this as a GHC bug:  http://www.haskell.org/ghc/reportabug

See: https://s3.amazonaws.com/archive.travis-ci.org/jobs/103319396/log.txt

These are relevant settings that Travis uses:

GhcStage2HcOpts += -DDEBUG
DYNAMIC_GHC_PROGRAMS = NO
GhcLibWays = v

comment:7 Changed 3 years ago by niteria

Differential Rev(s): phab:D1792phab:D1792, phab:D1801, phab: D1802

comment:8 Changed 3 years ago by niteria

Differential Rev(s): phab:D1792, phab:D1801, phab: D1802phab:D1792, phab:D1801, phab:D1802

comment:9 Changed 3 years ago by thomie

Some of the following validate --slow failures are probably also caused by this patch: https://phabricator.haskell.org/D1652#53187

To reproduce, in testsuite/tests, run:

make TEST="conc014 T3279 conc012 print029 print025 print022 print006 print005 print003 print008 break018 T2740 hist001 break017 break010 break011 break012 dynbrk002 print032 print030 print031 print010 print018 print019 break027 break026 break021 break020 break009 break006 break005 break003 break028 break001 result001 tcrun028 T8119 T7653 exceptionsrun001 break022 tc180 T4969 tc152 tc187 tc126 tc125 Vta1 Vta2 overloadedlabelsghci01 T11351 T3023 tcfail093 T10728 T7332 T6015 T11248 T6015a T6068 VtaParse dynamic-paper haddock.Cabal" CLEANUP=1 slow

comment:10 Changed 3 years ago by niteria

I've just run make TEST="conc014 T3279 conc012 print029 print025 print022 print006 print005 print003 print008 break018 T2740 hist001 break017 break010 break011 break012 dynbrk002 print032 print030 print031 print010 print018 print019 break027 break026 break021 break020 break009 break006 break005 break003 break028 break001 result001 tcrun028 T8119 T7653 exceptionsrun001 break022 tc180 T4969 tc152 tc187 tc126 tc125 Vta1 Vta2 overloadedlabelsghci01 T11351 T3023 tcfail093 T10728 T7332 T6015 T11248 T6015a T6068 VtaParse dynamic-paper haddock.Cabal" CLEANUP=1 slow on 80265c4c3c827695e92dd9620faf47e064b5da37 a revision right before my commit and it's failing with this:

Unexpected results from:
TEST="conc014 T3279 conc012 exceptionsrun001 T11351 Vta1 Vta2 T10728 T11248 VtaParse dynamic-paper"

OVERALL SUMMARY for test run started at Wed Jan 20 06:16:25 2016 PST
 0:03:42 spent to go through
      61 total tests, which gave rise to
     137 test cases, of which
       2 were skipped

       1 had missing libraries
     111 expected passes
       0 expected failures

       0 caused framework failures
       0 unexpected passes
      23 unexpected failures
       0 unexpected stat failures

Unexpected failures:
   ../../libraries/base/tests  exceptionsrun001 [bad exit code] (hpc)
   concurrent/should_run       T3279 [bad exit code] (hpc,optasm,threaded2,dyn)
   concurrent/should_run       conc012 [bad exit code] (hpc,optasm,threaded2,dyn)
   concurrent/should_run       conc014 [bad stdout] (hpc,optasm,threaded2,dyn)
   dependent/should_compile    dynamic-paper [exit code non-0] (hpc,optasm)
   parser/should_compile       VtaParse [exit code non-0] (hpc)
   patsyn/should_compile       T11351 [exit code non-0] (hpc)
   polykinds                   T11248 [exit code non-0] (hpc,optasm)
   rts                         T10728 [bad stdout] (threaded2)
   rts                         T10728 [bad stdout or stderr] (ghci)
   typecheck/should_compile    Vta1 [exit code non-0] (hpc)
   typecheck/should_compile    Vta2 [exit code non-0] (hpc)

comment:11 Changed 3 years ago by Bartosz Nitka <niteria@…>

In 48d4bc5/ghc:

substTy to substTyUnchecked to fix Travis build

This fixes the immediate problem from
https://s3.amazonaws.com/archive.travis-ci.org/jobs/103319396/log.txt

Test Plan: ./validate

Reviewers: bgamari, austin, thomie

Differential Revision: https://phabricator.haskell.org/D1802

GHC Trac Issues: #11371

comment:13 Changed 3 years ago by Bartosz Nitka <niteria@…>

In 01809bcd/ghc:

Pass InScopeSet to substTy in lintTyApp

This is the fix proposed in #11371:
```
In other cases, we already have the in-scope set in hand. Example: in
CoreLint.lintTyApp we find a call to substTyWith. But Lint carries an
in-scope set, so it would be easy to pass it to substTyWith.
```

Test Plan: ./validate --slow (only pre-existing problems)

Reviewers: simonpj, goldfire, austin, nomeata, bgamari

Subscribers: thomie

Differential Revision: https://phabricator.haskell.org/D1820

GHC Trac Issues: #11371

comment:14 Changed 3 years ago by Bartosz Nitka <niteria@…>

In 144ddb41/ghc:

Construct in_scope set in mkTopTCvSubst

The pre-condition on `mkTopTCvSubst` turned out to be wrong and
not satisfied by any of the callers. I've fixed it, so that it
constructs the in_scope set from the range of the substitution.
`mkTopTCvSubst` was also unnecessarily general it is never called
with `CoVars`, so I changed the type signature and added an assertion.

Test Plan: ./validate --slow

Reviewers: goldfire, simonpj, bgamari, austin

Reviewed By: simonpj

Subscribers: thomie

Differential Revision: https://phabricator.haskell.org/D1801

GHC Trac Issues: #11371

comment:15 Changed 3 years ago by Bartosz Nitka <niteria@…>

In 45fd83b/ghc:

Fix a typo in the note name in comments

This is `subsititution` to `substitution`, plus one instance of
the note that I missed.

Test Plan: docufix

Reviewers: simonpj, bgamari, austin, goldfire

Reviewed By: simonpj, bgamari

Subscribers: thomie

Differential Revision: https://phabricator.haskell.org/D1856

GHC Trac Issues: #11371

comment:16 Changed 3 years ago by simonpj

This looks terribly suspicious (in TyCoRep):

extendSubstEnvs :: (TvSubstEnv, CvSubstEnv) -> Var -> Type
                -> (TvSubstEnv, CvSubstEnv)
extendSubstEnvs (tenv, cenv) v ty
  | isTyVar v
  = ASSERT( not $ isCoercionTy ty )
    (extendVarEnv tenv v ty, cenv)

    -- NB: v might *not* be a proper covar, because it might be lifted.
    -- This happens in tcCoercionToCoercion
  | CoercionTy co <- ty
  = (tenv, extendVarEnv cenv v co)
  | otherwise
  = pprPanic "extendSubstEnvs" (ppr v <+> text "|->" <+> ppr ty)

I think that the Var passed to extendSubsEnv should be a proper TyVar or a CoVar. Moreover tcCoercionToCoercion doesn’t exist. Is the comment now out of date? I hope so.

Moreover, it seems suspicious to pattern match on CoercionTy. What if there was a type synonym in the way? Or a cast?

HOWEVER, we do need to get the coercion out to put into cenv.

But that makes me suspicious too. I think that almost all calls to extendSubstEnvs provide only TyVars, not CoVars. The only call I can find that doesn’t is in TcMType.instSkolTyCoVarX, which tests the variable, and makes a CoercionTy – only for extendTCvSubst to unpack it again. Concretely, I suggest that

  • we rename extendTCvSubst to be extendTvSubst, and work only over TyVars. (Have an assertion of course.)
  • have a similar one for extendCvSubst

and see how that goes. It’s be in line with the new zipTvSubst, zipCvSubst etc.

Richard, can you see anything wrong with that? Bartosz, might you execute?

comment:17 Changed 3 years ago by simonpj

While I'm thinking about this, I'd like to get rid of composeTCvSubst. It is somewhat complex, but it is used in very simple ways, basically as a form of extendTCvSubst.

For example this call (in checkAxInstCo) is just stupid

        subst        = zipTvSubst tvs tys `composeTCvSubst`
                       zipCvSubst cvs co_args

There are very few calls altogether. I think it could easily be nuked.

comment:18 in reply to:  16 Changed 3 years ago by goldfire

Replying to simonpj:

Richard, can you see anything wrong with that?

Not at all. I very nearly did that myself a while ago, but it meant some code duplication around instSkolTyCoVarX (and perhaps one other place, if memory serves -- I'm sure you'll find it by looking at use sites of extendTCvSubst).

Yes -- go for it. This is an improvement.

The comment about tcCoercionToCoercion is historical and should be removed, along with that case, which should indeed never be triggered now.

comment:19 Changed 3 years ago by Richard Eisenberg <eir@…>

In 2899aa5/ghc:

Fix some substitution InScopeSets

This is relevant to #11371.

comment:20 Changed 3 years ago by goldfire

I'm a little lost in these substitutions, but I had to fix this one case to get some sample code to compile. The commit above should be merged to the stable branch, but it doesn't fully solve this ticket.

comment:21 Changed 3 years ago by Bartosz Nitka <niteria@…>

In 5dcae88/ghc:

Rename "open" subst functions

This is the renaming that @simonpj requested:
```
· zipOpenTCvSubst  -> zipTvSubst   (It only deals with tyvars)

· zipOpenTCvSubstCoVars -> zipCvSubst   (it only deals with
covars)

· zipOpenTCvSubstBinders ->  zipTyBinderSubst  (it only deals
with TyBinders, not covars)
```
plus the `mk` variant.

Test Plan: ./validate

Reviewers: simonpj, goldfire, austin, bgamari

Subscribers: thomie, simonpj

Differential Revision: https://phabricator.haskell.org/D1853

GHC Trac Issues: #11371

comment:22 Changed 3 years ago by Bartosz Nitka <niteria@…>

In 63700a19/ghc:

Use the in_scope set in lint_app

This makes the call to `substTy` satisfy the invariant from
Note [The substitution invariant] in TyCoRep.

Test Plan: ./validate --slow

Reviewers: goldfire, austin, bgamari, simonpj

Reviewed By: simonpj

Subscribers: thomie

Differential Revision: https://phabricator.haskell.org/D1861

GHC Trac Issues: #11371

comment:23 Changed 3 years ago by Bartosz Nitka <niteria@…>

In bb956eb/ghc:

Add asserts to other substitution functions

This adds asserts to `substTys`, `substCo` and `substCos` in
the same spirit as already existing asserts on `substTy`, protecting
every possible entry point to `subst_ty` and `subst_co`.

I've replaced the violators with unchecked versions.

Test Plan: ./validate --slow

Reviewers: simonpj, goldfire, austin, bgamari

Subscribers: thomie

Differential Revision: https://phabricator.haskell.org/D1862

GHC Trac Issues: #11371

comment:24 Changed 3 years ago by thomie

This commit causes the following Travis failures with DEBUG=YES:

Unexpected failures:
   ../../libraries/base/tests/IO  hClose002 [exit code non-0] (normal)
   ../../libraries/base/tests/IO  hClose003 [exit code non-0] (normal)
   ../../libraries/base/tests/IO  hDuplicateTo001 [exit code non-0] (normal)

See https://s3.amazonaws.com/archive.travis-ci.org/jobs/105899161/log.txt

Here is one of them:

=====> hClose002(normal) 4736 of 5007 [0, 0, 0] 
Compile failed (status 256) errors were:
[1 of 1] Compiling Main             ( hClose002.hs, hClose002.o )
ghc-stage2: panic! (the 'impossible' happened)
  (GHC version 8.1.20160130 for x86_64-unknown-linux):
	ASSERT failed!
  CallStack (from ImplicitParams):
  assertPprPanic, called at compiler/types/TyCoRep.hs:1903:56 in ghc:TyCoRep
  checkValidSubst, called at compiler/types/TyCoRep.hs:2047:17 in ghc:TyCoRep
  substCo, called at compiler/basicTypes/MkId.hs:698:28 in ghc:MkId
  in_scope InScope {}
  tenv [a1oW :-> dev_a1Z8, a1oX :-> enc_state_a1Z9,
        a1oY :-> dec_state_a1Za]
  tenvFVs [a1Z8 :-> dev_a1Z8, a1Z9 :-> enc_state_a1Z9,
           a1Za :-> dec_state_a1Za]
  cenv []
  cenvFVs []
  tys []
  cos [N:IORef[0] <Buffer Word8>_N]

comment:25 Changed 3 years ago by Bartosz Nitka <niteria@…>

In e5a0a89/ghc:

Suppress substitution assertions to fix tests

This is one place that I've missed with D1862.
This doesn't fix the underlying problem and I prefer to suppress it
now and fix it later as this is a part of a larger effort (#11371)
to fix an old bug with `substTy` called with invalid `in_scope` sets.

Test Plan: `make test TEST="hClose002 hClose003 hDuplicateTo001"

Reviewers: thomie, austin, bgamari, trofi

Reviewed By: trofi

Differential Revision: https://phabricator.haskell.org/D1872

GHC Trac Issues: #11371

comment:26 Changed 3 years ago by Bartosz Nitka <niteria@…>

In dbf72dbc/ghc:

Build the substitution correctly in piResultTy

This fixes a bug where piResultTy created
substitutions that would violate both of the invariants
in Note [The substitution invariant].

Test Plan: ./validate --slow

Reviewers: goldfire, simonpj, austin, bgamari

Reviewed By: simonpj, bgamari

Subscribers: simonmar, thomie

Differential Revision: https://phabricator.haskell.org/D1855

GHC Trac Issues: #11371

comment:27 Changed 3 years ago by thomie

perf.haskell.org reports for that last commit:

testsuite/unexpected stats 	3	+ 3	6	tests

Testsuite allocations

Benchmark name	        previous	change	        now	
tests/alloc/T5030 	691938256	+ 17.33%	811867344	bytes
tests/alloc/T9872a 	3477263608	+ 4.63%	        3638155736	bytes
tests/alloc/T9872b 	4984017672	+ 5.75%	        5270795992	bytes
tests/alloc/T9872c 	4507661800	+ 6.50%	        4800521096	bytes

comment:28 Changed 3 years ago by simonpj

Blimey! That's a big change n allocation for a very small diff. Esp since one part (piResultTys not using one-at-a-time substitutio) ought to be a material improvement in efficiency!

Bartosz maybe you can investigate?

comment:29 Changed 3 years ago by niteria

I will investigate. I think it will be easier if I revert it and then push it again when it's fixed.

comment:30 Changed 3 years ago by niteria

I've done some profiling today and I've optimized piResultTys a bit.

Here are the results (this is built with prof):

Benchmark name	        baseline	with-inscope    without-inscope	
tests/alloc/T5030 	1084862416      1198020320 	1084861344
tests/alloc/T9872a      5426538936      5576679896      5426504344
tests/alloc/T9872b      7807323280      8022344352      7728326496
tests/alloc/T9872c      7113767856      7405191768      7113729216

baseline is the current incorrect implementation that doesn't compute the in-scope sets.

with-inscope is https://phabricator.haskell.org/P97 - an implementation where the coreView that was hidden in splitPiTy_maybe and in getTyVar_maybe is done only once and both are inlined. This is the hint that I got from profiling, there was a significant difference in bytes allocated by splitPiTy_maybe.

without-inscope is https://phabricator.haskell.org/P95 - a version of with-inscope that's doesn't compute the in-scope sets.

So without-inscope is a strict, but small improvement over baseline performance wise, but the cost of computing the in-scope sets is non-trivial, so the correct version has a performance penalty.

Are we willing to accept it in the name of correctness? The correct version has to do more work.

The hot path is cmpTypeX -> typeKind -> piResultTys, I believe cmpTypeX already has the relevant free vars in the env, so passing them down is what I'll try to do next.

comment:31 Changed 3 years ago by simonpj

There is something odd happening here. I do not expect the in-scope set to be evaluated at all (that is, it should remain as a thunk) when substituting into for-all-free types.

That was why I thought it worth writing piResultTys (plural). Consider piResultTys (forall a b. blah) [t1, t2]. If we substitute one [a->t1], and then [b->t2] the first will substitute into forall b. blah and that will force the in-scope set. But if we do both at once, we won't, provided blah has no foralls, which is the wildly common case.

So how can it possibly cost 10% of all of compile time in this single tiny function???? That is utterly bizarre.

Are you sure ASSERTs are off? They do a lot of forcing!

Maybe you can just pprTrace what is going on, to see if the in-scope sets are being unexpectedly forced. If so, fixing that might fix a LOT of things.

Yes, it might be good to give the in-scope set to piResultTy(s) when it's available, but please, before you do that, can you get more insight into what is happening? Thanks!

comment:32 Changed 3 years ago by niteria

Btw this is a subset of tests from #11196 which got 30-60% worse after TypeInType.

I do not expect the in-scope set to be evaluated at all (that is, it should remain as a thunk) when substituting into for-all-free types.

I've experimented a bit and you're right. The in-scope set is never forced for T5030. Why do we see a difference then?

I've compared:

empty_subst = mkEmptyTCvSubst (pprTrace "forced" (ppr (ty,args)) $ 
  mkInScopeSet $ tyCoVarsOfTypes (ty:args))

with

empty_subst = mkEmptyTCvSubst (pprTrace "forced" (ppr (ty,args)) $ 
  mkInScopeSet $ tyCoVarsOfTypes [])

and they performed exactly the same! They were different without pprTrace. So I've tried:

empty_subst = mkEmptyTCvSubst (pprTrace "forced" (ppr ()) $ 
  mkInScopeSet $ tyCoVarsOfTypes [])

and it was better, back to the same amount of allocations as baseline.

It appears that the difference in allocations comes from the thunks that get created or empty_subst being constant changes the generated code significantly. I will take a look at the core.

comment:33 Changed 3 years ago by simonpj

Yes look at the core. I'm struggling to believe that this one thunk takes 10% of compile time!

comment:34 Changed 3 years ago by niteria

With the in-scope set: https://phabricator.haskell.org/P99

Without the in-scope set: https://phabricator.haskell.org/P98

comment:35 Changed 3 years ago by niteria

Looking at

let {
      a_sihF :: VarEnv Var
      [LclId, Str=DmdType]
      a_sihF =
        case TyCoRep.$wtyCoVarsOfTypesAcc
               (ghc-prim-0.5.0.0:GHC.Types.: @ Type ty_a6bU args_a6bV)
               FV.runFV2
               ((containers-0.5.7.1:Data.IntMap.Base.Nil @ Var)
                `cast` (Sym UniqFM.N:UniqFM[0] <Var>_N
                        :: containers-0.5.7.1:Data.IntMap.Base.IntMap Var
                           ~R# UniqFM.UniqFM Var))
               (ghc-prim-0.5.0.0:GHC.Types.[] @ Var)
               ((containers-0.5.7.1:Data.IntMap.Base.Nil @ Var)
                `cast` (Sym UniqFM.N:UniqFM[0] <Var>_N
                        :: containers-0.5.7.1:Data.IntMap.Base.IntMap Var
                           ~R# UniqFM.UniqFM Var))
        of _ [Occ=Dead] { (# ww4_aeZD, ww5_aeZE #) ->
        ww5_aeZE
        } } in
    let {
      a1_sihE :: InScopeSet
      [LclId, Str=DmdType m]
      a1_sihE = VarEnv.InScope a_sihF 1# } in
    let {
      empty_subst_seCG :: TCvSubst
      [LclId, Str=DmdType m]
      empty_subst_seCG =
        TyCoRep.TCvSubst
          a1_sihE
          ((containers-0.5.7.1:Data.IntMap.Base.Nil @ Type)
           `cast` (Sym UniqFM.N:UniqFM[0] <Type>_N
                   :: containers-0.5.7.1:Data.IntMap.Base.IntMap Type
                      ~R# UniqFM.UniqFM Type))
          ((containers-0.5.7.1:Data.IntMap.Base.Nil @ Coercion)
           `cast` (Sym UniqFM.N:UniqFM[0] <Coercion>_N
                   :: containers-0.5.7.1:Data.IntMap.Base.IntMap Coercion
                      ~R# UniqFM.UniqFM Coercion)) } in

it produces not 1, but 3 thunks. I will try to see if reducing that to 1 helps.

comment:36 Changed 3 years ago by simonpj

I only see one superfluous one: a_sihF could be pushed inside the RHS of a_s1hE.

And still -- at risk of repetition -- how can this one extra allocation account for 10% of the entire compiler allocation? Are there very many calls to this function some how? And if so why?

comment:37 Changed 3 years ago by niteria

Changing it to:

empty_subst = mkEmptyTCvSubst $! mkInScopeSet $! tyCoVarsOfTypes (ty:args)

gives me:

$ ("/data/users/bnitka/ghc-perf/ghc-after/inplace/test   spaces/ghc-stage2" -c T5030.hs -fforce-recomp -no-user-package-db -rtsopts -fno-warn-tabs -fno-warn-missed-specialisations -fno-ghci-history  -freduction-depth=300 +RTS -V0 -tT5030.comp.stats --machine-readable -P -RTS)
ghc-stage2: panic! (the 'impossible' happened)
  (GHC version 8.1.20160216 for x86_64-unknown-linux):
        exprToType
CallStack (from -prof):
  GHC.withCleanupSession (compiler/main/GHC.hs:(464,1)-(473,27))
  GHC.runGhc (compiler/main/GHC.hs:(437,1)-(442,26))
  GHC.defaultErrorHandler (compiler/main/GHC.hs:(377,1)-(409,7))
  CoreSyn.CAF (<entire-module>)

Please report this as a GHC bug:  http://www.haskell.org/ghc/reportabug

Is it worth looking at?

comment:38 Changed 3 years ago by simonpj

Well by making it strict you'll certainly force the tyCoVarsOfTypes to happen, which isn't really a good idea.

But there is something weird here: why is exprToType being called on an expression other than (Type ty). Let's find out. You can make the panic print the expr. And it could come from

applyTypeToArg fun_ty arg = piResultTy fun_ty (exprToType arg)

perhpas? Which call to exprToType (there aren't many) is at fault?

More and more mysterious

comment:39 Changed 3 years ago by niteria

I got 2 traces

CallStack (from HasCallStack):
  pprSTrace, called at compiler/coreSyn/CoreSyn.hs:1595:33 in ghc:CoreSyn
  exprToType2, called at compiler/coreSyn/CoreSyn.hs:1585:53 in ghc:CoreSyn
  applyTypeToArg2, called at compiler/simplCore/SimplUtils.hs:251:37 in ghc:SimplUtils
  addValArgTo, called at compiler/simplCore/Simplify.hs:1114:57 in ghc:Simplify
  rebuild, called at compiler/simplCore/Simplify.hs:1477:5 in ghc:Simplify
  rebuildCall, called at compiler/simplCore/Simplify.hs:1406:11 in ghc:Simplify
  bad $fMonadIO

CallStack (from HasCallStack):
  pprSTrace, called at compiler/coreSyn/CoreSyn.hs:1595:33 in ghc:CoreSyn
  exprToType2, called at compiler/coreSyn/CoreSyn.hs:1585:53 in ghc:CoreSyn
  applyTypeToArg2, called at compiler/simplCore/SimplUtils.hs:251:37 in ghc:SimplUtils
  addValArgTo, called at compiler/simplCore/Simplify.hs:1468:28 in ghc:Simplify
  rebuildCall, called at compiler/simplCore/Simplify.hs:1446:5 in ghc:Simplify
  rebuildCall, called at compiler/simplCore/Simplify.hs:1406:11 in ghc:Simplify
  bad Permute @ Flag

comment:40 Changed 3 years ago by niteria

More than half the difference from allocations comes from liftCoMatch in Unify. In the same file there are calls to eqType and typeKind. Both of them call piResultTys. There are also comments like: -- TODO (RAE): Remove this exponential behavior..

comment:41 Changed 3 years ago by simonpj

There's a lot going on here. Concerning comment:39, here is what is happening:

  • CoreSyn.applyTypeToArg deliberately calls piResultTy with a possibly-bottom second argument. It'll be bottom when the type is t1 -> t2 and the arg is some non-Type expression.
  • piResultTy calls piResultTys
  • When piResultTys finishes it calls substTy
  • Which looks at the substitution
  • Which is bottom because you built it strictly from its in-scope set
  • Which was bottom because the second arg to piResultTy was bottom

Sigh. We could improve matters, but that is at least why you are getting the panic.

So go back to being lazy. The exponential typeKind stuff seems more likely. Can you just count how many calls to piResultTy and/or typeKind are being made? And if large, then on what shaped types?

comment:42 Changed 3 years ago by niteria

promoteCoercion here contributes half of the increase in allocations. promoteCoercion is called 86576 times in total for T5030.

comment:43 Changed 3 years ago by niteria

For completeness, there are 831805 calls to piResultTys with this distribution:

 346492   piResultTys Levity -> *
 308771   piResultTys * -> * -> *
 147177   piResultTys * -> *
  18410   piResultTys * -> * -> * -> *
  10407   piResultTys *
    142   piResultTys * -> #
     70   piResultTys Levity
     66   piResultTys * -> Constraint
     24   piResultTys (* -> *) -> Constraint

comment:44 Changed 3 years ago by niteria

I have a version that performs as well as the old code on T5030:

piResultTys :: Type -> [Type] -> Type
piResultTys ty args = go_fast ty args
  where
    go_fast ty [] = ty
    go_fast (ForAllTy (Anon _) res) (_:args') = go_fast res args'
    go_fast ty args =
      go (mkEmptyTCvSubst $ mkInScopeSet $ tyCoVarsOfTypes (ty:args)) ty args
      -- The free vars of 'ty' and 'args' need to be in scope to satisfy the
      -- invariant in Note [The substitution invariant] in TyCoRep.

    go subst ty [] = substTy subst ty
    go subst ty args | Just ty' <- coreView ty = go subst ty' args
    go subst (ForAllTy bndr res) (arg:args')
      = case bndr of
          Anon _     -> go subst                         res args'
          Named tv _ -> go (extendTCvSubst subst tv arg) res args'
    go subst (TyVarTy tv) args
        -- Deals with piResultTys (forall a. a) [forall b.b, Int]
      = go subst (substTyVar subst tv) args  
        -- The previous version used empty_subst here, 
        -- I'm not sure if it matters for correctness
    go _subst _ty _args = panic "piResultTys"

comment:45 Changed 3 years ago by simonpj

Yes I found that too. I have something similar running now. Your TyVarTy case isn't quite right. Meanwhile I'm going to open another ticket about the "exponential behavior" part.

Simon

comment:46 Changed 3 years ago by niteria

Your TyVarTy case isn't quite right.

Can you elaborate? With a counter example maybe?

FWIW it passes ./validate with no perf regressions.

comment:47 Changed 3 years ago by simonpj

comment:43 is fantastic. Are you in a position to go one level up and determine which are the hot calls to piResultTys? (Maybe the one in typeKind?) And then which are the hot calls to typeKind? comment:30 suggests that it's mostly from cmpTypeX; is that still right? If so it should improve a lot when Richard does #11597.

comment:48 Changed 3 years ago by simonpj

Re the tyvar case, what if tv is not in the substitution? substTyVar will return the same tyvar and we'll get an infinite loop.

I'll push shortly.

comment:49 Changed 3 years ago by Simon Peyton Jones <simonpj@…>

In 4d031cf/ghc:

Improve piResultTys and friends

Several things here:

* Re-implement piResultTys so that its substitution has
  the correct in-scope set

  That means paying close attention to performance, since as we
  discovered in Trac #11371, it's a heavily used function and
  is often used on ordinary function types, with no foralls to
  worry about substituting.

* Kill off applyTys, which was just the same as piResultTys.

* Re-engineer MkCore.mkCoreApps so that it calls piResultTys,
  rather than repeatedly calling piResultTy.

comment:50 Changed 3 years ago by niteria

Is comment:47 still relevant after your patch?

The hottest chain goes like this: promoteCoercion -> eqType -> cmpType -> cmpTypeX -> typeKind -> piResultTys.

comment:51 Changed 3 years ago by simonpj

Yes absolutely it is. We've may have avoided piResultTys more expensive, but I think we are simply calling it far too often. I started #11602 to track this, and will transfer your comment there.

I guess that leaves this ticket for removing all those unchecked calls!

comment:52 Changed 3 years ago by Bartosz Nitka <niteria@…>

In c37a583/ghc:

Remove unused substTyWithBinders functions

Originally I wanted to only remove substTyWithBindersUnchecked, but
since both of them are unused maybe we don't need them.

Test Plan: ./validate

Reviewers: austin, goldfire, bgamari, simonpj

Reviewed By: simonpj

Subscribers: thomie, simonmar

Differential Revision: https://phabricator.haskell.org/D2025

GHC Trac Issues: #11371

comment:53 Changed 3 years ago by Bartosz Nitka <niteria@…>

In 685398eb/ghc:

Use the correct in-scope set in coercionKind

The free vars of `ty2` need to be in scope to satisfy the substitution
invariant.
As far as I can tell we don't have the free vars of `ty2` when
substituting, so unfortunately we have to compute them.

Test Plan: ./validate

Reviewers: austin, bgamari, simonpj, goldfire

Subscribers: thomie, simonmar

Differential Revision: https://phabricator.haskell.org/D2024

GHC Trac Issues: #11371

comment:54 Changed 3 years ago by Ben Gamari <ben@…>

In 73935326/ghc:

Use a correct substitution in tcInstType

`ty` doesn't have to be a closed type, so we need to add its
free vars to the in-scope set. They don't seem to be
available anywhere nearby, so we have to compute them.

Test Plan: ./validate

Reviewers: goldfire, austin, bgamari, simonpj

Reviewed By: simonpj

Subscribers: thomie, simonmar

Differential Revision: https://phabricator.haskell.org/D2042

GHC Trac Issues: #11371

comment:55 Changed 3 years ago by Ben Gamari <ben@…>

In a49228e/ghc:

Build correct substitution in instDFunType

We will use `ty` in the range of the substitution, hence
the substitution needs `ty`'s free vars in-scope.
They don't seem easily available by other means, so we
just compute them.

Test Plan: ./validate

Reviewers: austin, goldfire, bgamari, simonpj

Reviewed By: simonpj

Subscribers: thomie, simonmar

Differential Revision: https://phabricator.haskell.org/D2043

GHC Trac Issues: #11371

comment:56 Changed 3 years ago by Ben Gamari <ben@…>

In 4a93e4f9/ghc:

Use the correct substitution in lintCoercion

We need the free vars of `t2` to satisfy the substitution
invariant. Luckily they are in the in-scope carried around.

Test Plan: ./validate

Reviewers: bgamari, austin, goldfire, simonpj

Reviewed By: simonpj

Subscribers: thomie, simonmar

Differential Revision: https://phabricator.haskell.org/D2044

GHC Trac Issues: #11371

comment:57 Changed 3 years ago by Bartosz Nitka <niteria@…>

In 1757dd8e/ghc:

Don't recompute some free vars in lintCoercion

As pointed out by @simonpj on D2044 we don't need
to compute the free vars of the range of the substitution
as most of them are already carried by the monad.
This should be a tiny performance improvement over the version
from before D2044.

Also removes an extra function that is now unnecessary.

Test Plan: ./validate && ./validate --slow

Reviewers: goldfire, simonpj, austin, bgamari

Reviewed By: simonpj

Subscribers: thomie, simonmar, simonpj

Differential Revision: https://phabricator.haskell.org/D2060

GHC Trac Issues: #11371

comment:58 Changed 3 years ago by Bartosz Nitka <niteria@…>

In 62943d2/ghc:

Build a correct substitution in dataConInstPat

This adds the tyvars of the domain of the substitution into the in-scope
set as well.
What I'm not sure here is if the kinds can have any free vars that
should be in the in-scope set as well.

Test Plan: ./validate

Reviewers: goldfire, austin, bgamari, simonpj

Reviewed By: simonpj

Subscribers: thomie, simonmar

Differential Revision: https://phabricator.haskell.org/D2094

GHC Trac Issues: #11371

comment:59 Changed 2 years ago by niteria

comment:60 Changed 2 years ago by niteria

e6aefd6e07ef04d068d727490c640c68c82e4954 is another fix

There are still about 40 occurrences of unchecked functions in the GHC sources. Tackling one of them should be a nice well-scoped GHC starter task. The main difficulty is not introducing unnecessary performance regressions.

comment:61 Changed 21 months ago by bgamari

Milestone: 8.2.18.4.1

I'm going to bump the remainder of this ticket off to 8.4 unless you object, niteria.

comment:62 Changed 21 months ago by niteria

No objections from me, this is a longstanding thing, and usually hard to tickle.

comment:63 Changed 13 months ago by Bartosz Nitka <niteria@…>

In e19b6464/ghc:

Compute InScopeSet in substInteractiveContext

It doesn't look like we keep any sets of free variables
of the types of Ids handy, so we just have to build them
when doing a substitution.

Test Plan: buildbot + run testsuite with debug

Reviewers: simonmar, simonpj, austin, bgamari

Reviewed By: simonpj

Subscribers: carter, rwbarton, thomie

GHC Trac Issues: #11371

Differential Revision: https://phabricator.haskell.org/D3431
Note: See TracTickets for help on using tickets.