typePrimRep panic while compiling GHC with profiling

changed milestone to %8.2.1

changed weight to 7

I'm seeing this on 9fd87ef8.

Here is a more complete backtrace,

ghc-stage1: panic! (the 'impossible' happened)
  (GHC version 8.1.20170124 for x86_64-unknown-linux):
	runtimeRepPrimRep
  typePrimRep (a :: TYPE k0)
  k0
  Call stack:
      ?callStack, called at compiler/utils/Util.hs:1352:50 in ghc:Util
        prettyCurrentCallStack, called at compiler/utils/Outputable.hs:1166:58 in ghc:Outputable
        callStackDoc, called at compiler/utils/Outputable.hs:1170:37 in ghc:Outputable
        pprPanic, called at compiler/simplStg/RepType.hs:358:5 in ghc:RepType
        runtimeRepPrimRep, called at compiler/simplStg/RepType.hs:340:5 in ghc:RepType
        kindPrimRep, called at compiler/simplStg/RepType.hs:303:18 in ghc:RepType
        typePrimRep, called at compiler/simplStg/RepType.hs:67:11 in ghc:RepType
        typePrimRepArgs, called at compiler/simplStg/RepType.hs:108:13 in ghc:RepType
        countFunRepArgs, called at compiler/basicTypes/Id.hs:570:19 in ghc:Id
        idFunRepArity, called at compiler/codeGen/StgCmmClosure.hs:334:13 in ghc:StgCmmClosure

Oh dear, it seems that mkLFImported was looking at this Id,

(#,#) :: forall (a :: TYPE k0) (b :: TYPE k1). a -> b -> (# a, b #)

Something is indeed amiss.

Unboxed tuples should be long gone by then, shouldn't they?

Yes, that is my understanding as well. Incidentally, -dstg-lint appears to hang.

changed weight to 10

So it seems that we somehow have an unsaturated application of (#,#) making it to CoreToStg. Usually saturated applications of a DataConWorkId will result in a StgConApp. However, since this isn't saturated we end up with an StgApp. More updates to come.

Trac metadata

Trac field	Value
Priority	high → highest

It looks like this binding from the Core Prep output is the culprit,

-- RHS size: {terms: 8, types: 27, coercions: 0}
StgCmmMonad.$fHasDynFlagsFCode2
  :: StgCmmMonad.CgInfoDownwards
     -> StgCmmMonad.CgState
     -> (# StgCmmMonad.CgInfoDownwards, StgCmmMonad.CgState #)
[GblId]
StgCmmMonad.$fHasDynFlagsFCode2 =
  case \ (@ (k0_10 :: GHC.Types.RuntimeRep))
         (@ (k1_11 :: GHC.Types.RuntimeRep))
         (@ (a_12 :: TYPE k0))
         (@ (b_13 :: TYPE k1)) ->
         GHC.Prim.(#,#) @ k0 @ k1 @ a @ b
  of sat_skkE
  { __DEFAULT ->
  sat_skkE
    @ 'GHC.Types.LiftedRep
    @ 'GHC.Types.LiftedRep
    @ StgCmmMonad.CgInfoDownwards
    @ StgCmmMonad.CgState
  }

At this point I'm fairly convinced that this was introduced by the levity polymorphism work. While I'm still working out precisely what is going on, it seems that our conception of arity may be a bit inconsistent, meaning that we don't eta expand enough in CorePrep.

One thing that surprised me is the type of the worker for (#,#),

(#,#) :: forall (a :: TYPE k0) (b :: TYPE k1). a -> b -> (# a, b #)

In contrast I would have expected,

(#,#) :: forall (r1 :: RuntimeRep) (r2 :: RuntimeRep) 
         (a :: TYPE r1) (b :: TYPE r2). 
         a -> b -> (#,#) r1 r2 a b

That is, it seems to me like the worker is missing RuntimeRep arguments. This seems especially suspicious in light of the fact that I see the RuntimeRep arguments instantiated at the application site (e.g. ticket:13233#comment:131533). Goldfire, am I missing something here?

Oh dear, forget what I said in ticket:13233#comment:131534: I had neglected to pass -fprint-explicit-runtime-reps.

Interesting... So we are calling (correctly) cpeEtaExpand 2 (#,#) yet somehow getting back,

  \ (@ (k0_10 :: RuntimeRep))
    (@ (k1_11 :: RuntimeRep))
    (@ (a_12 :: TYPE k0))
    (@ (b_13 :: TYPE k1)) ->
    (#,#) @ k0 @ k1 @ a @ b

Which most certainly does not have two value-level lambdas. Hmmm.

Ahhh, I see what is happening here. CoreArity.mkEtaWW is refusing to eta expand the value-level arguments of (#,#) as they are levity polymorphic,

       | otherwise       -- We have an expression of arity > 0,
                         -- but its type isn't a function, or a binder
                         -- is levity-polymorphic
       = WARN( True, (ppr orig_n <+> ppr orig_ty) $$ ppr orig_expr )
         (getTCvInScope subst, reverse eis)

Had I been compiling with DEBUG this would have been plainly obvious but I was lazily merely building with BuildFlavour=prof. Serves me right, I suppose.

Anyways, this is a little hairy. Indeed eta expanding here would be quite suspicious. Really, it seems like we never should have produced the lambda being scrutinised in ticket:13233#comment:131533 at all given that it is levity polymorphic. I'll have to look into where this is coming from.

Interesting, the tidy core shows,

-- RHS size: {terms: 1, types: 4, coercions: 0}
StgCmmMonad.$fHasDynFlagsFCode2
  :: CgInfoDownwards -> CgState -> (# CgInfoDownwards, CgState #)
[GblId,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Value=False, ConLike=False,
         WorkFree=False, Expandable=False, Guidance=IF_ARGS [] 0 10}]
StgCmmMonad.$fHasDynFlagsFCode2 =
  ghc-prim-0.5.0.0:GHC.Prim.(#,#)
    @ 'ghc-prim-0.5.0.0:GHC.Types.LiftedRep
    @ 'ghc-prim-0.5.0.0:GHC.Types.LiftedRep
    @ CgInfoDownwards
    @ CgState

Which we would have been able to eta expand without any trouble. It must be something in CorePrep that is gumming up the works.

You sound hot on the case. I agree with everything you've written here. Let me know if you need a boost over a crag somewhere!

Ahhh, here we have the issue. CorePrep is trying to prepare,

  $fHasDynFlagsFCode2
    :: CgInfoDownwards -> CgState -> (# CgInfoDownwards, CgState #)
  $fHasDynFlagsFCode2 =
    (tick<getInfoDown> (#,#))
      @ 'LiftedRep @ 'LiftedRep @ CgInfoDownwards @ CgState

At first glance there is nothing particularly alarming about this. However, note the tick around (#,#): this is quite bad since it cuts the (#,#) off from its RuntimeRep applications, making the whole expression appear much more polymorphic than it really is in CorePrep.cpeApp.

Specifically, we first collect_args on the whole expression yielding,

collect_args (tick<getInfoDown> (#,#)) @'LiftedRep @'LiftedRep @CgInfoDownwards @CgState
   == (tick<getInfoDown> (#,#),
       [ CpeApp 'LiftedRep, CpeApp 'LiftedRep, CpeApp CgInfoDownwards, CpeApp CgState ]
      )

cpe_app then looks at the tick<getInfoDown> (#,#) to decide what to do next. Specifically, it wants to see a plain Var, but that's not what we have. Consequently we end up recursing via cpeArg, which will be deprived of knowledge of the RuntimeRep type applications.

It's difficult to say what the right solution here is. I have yet to look into how we end up with the tick scoping over only the constructor; it's possible that the tick was pushed in too far. More coming.

I do wonder whether collect_args is being too conservative here: it will only look through ticks where tickishPlace tickish == PlaceNonLam && tickish tickishScopesLike SoftScope. Even in the most restrictive tick placement type (PlaceRuntime) we allow ticks to be floated through type lambdas. Perhaps collect_args should continue to look through ticks, so long as there are no value-applications inside?

Goldfire, it would be interesting to hear your opinion about the above two comments.

For the record, after FloatOut we have,

getInfoDown :: FCode CgInfoDownwards
getInfoDown =
  scctick<getInfoDown>
  $ @ 'LiftedRep
    @ (CgInfoDownwards -> CgState -> (# CgInfoDownwards, CgState #))
    @ (FCode CgInfoDownwards)
    (lvl_shOy `cast` ...)
    (ghc-prim-0.5.0.0:GHC.Prim.(#,#)
       @ 'ghc-prim-0.5.0.0:GHC.Types.LiftedRep
       @ 'ghc-prim-0.5.0.0:GHC.Types.LiftedRep
       @ CgInfoDownwards
       @ CgState)

lvl_shOy :: (CgInfoDownwards -> CgState -> (# CgInfoDownwards, CgState #))
         -> CgInfoDownwards -> CgState -> (# CgInfoDownwards, CgState #)
lvl_shOy = \x -> x

Which after simplification turns into,

getInfoDown_shTB :: CgInfoDownwards -> CgState -> (# CgInfoDownwards, CgState #)
getInfoDown_shTB =
  (tick<getInfoDown> ghc-prim-0.5.0.0:GHC.Prim.(#,#))
    @ 'ghc-prim-0.5.0.0:GHC.Types.LiftedRep
    @ 'ghc-prim-0.5.0.0:GHC.Types.LiftedRep
    @ CgInfoDownwards
    @ CgState

In general all of this tick business is terribly fragile since there is no strong invariant (as far as I know) dictating where they might appear. I wonder if it would be reasonable a put inplace a Core invariant (checked by CoreLint) stating that "a tick must not sit directly inside of a type abstraction, type application, or cast. That is, we would normalize all things of the form,

(tick<t> e) @ty        -->  tick<t> (e @ty)
(tick<t> e) `cast` co  -->  tick<t> (e `cast` co)
/\ty -> (tick<t> e)    -->  tick<t> (/\ty -> e)

It already seems like we try to do something along these lines, but it's not strongly checked.

Does this make sense?

Hmm, interesting... CoreUtils.mkTick actually does the exact opposite of what I suggest: it pushes ticks **into** type applications. This certainly explains my observations. Unfortunately there's no explanation given for why we want to do this.

Replying to [ticket:13233#comment:131542 bgamari]:

Goldfire, it would be interesting to hear your opinion about the above two comments.

I have no opinion. This area of the compiler is a mystery to me. That levity-polymorphism check you discovered earlier was put there only by Simon guiding my hand.

It still sounds like you're on a brilliant chase, though... :)

I strongly agree that we should write down the invariants for ticks, and check them in Lint. Sadly I do not know what they are. The only people who do are Simon Marlow and Peter Wortmann.

I feel uneasy about the whole tick business being so ill-documented.

Simon, Peter, can you help please?

assigned to @bgamari

Replying to [ticket:13233#comment:131548 simonpj]:

I strongly agree that we should write down the invariants for ticks

So just to write down what we discussed the other day:

I believe there are (or were) no invariants on where ticks can appear in Core. However, there's an invariant that (#,#) must be directly applied to its type arguments, with no intervening ticks. (maybe it's more general than this?). Core Lint should really check this invariant.
We think that this invariant is satisfied by the desugarer but gets violated when the simplifier moves ticks inside type applications (https://phabricator.haskell.org/diffusion/GHC/browse/master/compiler/coreSyn/CoreUtils.hs;639e702b6129f501c539b158b982ed8489e3d09c$342-344). We don't know if there are other places that might violate the invariant.
I (@simonmar) was worried that if we just stop doing this we might lose other beneficial transformations. @bgamari is going to try it and check.

mentioned in issue #13433 (closed)

FWIW, here is a much easier way to trigger this panic that doesn't require profiling:

{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeInType #-}
{-# LANGUAGE UnboxedTuples #-}
module Bug where

import GHC.Exts (TYPE)

class Foo (a :: TYPE rep) where
  bar :: forall (b :: TYPE rep2). (a -> a -> b) -> a -> a -> b

baz :: forall (a :: TYPE rep). Foo a => a -> a -> (# a, a #)
baz = bar (#,#)

$ ~/Software/ghc/inplace/bin/ghc-stage2 Bug.hs
[1 of 1] Compiling Bug              ( Bug.hs, Bug.o )
ghc-stage2: panic! (the 'impossible' happened)
  (GHC version 8.3.20170322 for x86_64-unknown-linux):
        runtimeRepPrimRep
  typePrimRep (a_12 :: TYPE k0_10)
  k0_10
  Call stack:
      CallStack (from HasCallStack):
        prettyCurrentCallStack, called at compiler/utils/Outputable.hs:1191:58 in ghc:Outputable
        callStackDoc, called at compiler/utils/Outputable.hs:1195:37 in ghc:Outputable
        pprPanic, called at compiler/simplStg/RepType.hs:360:5 in ghc:RepType

Regarding ticket:13233#comment:133965,

Interesting. This is certainly the same panic, but the cause here is much different. Previously we were falling victim to ticks getting put between an unboxed tuple type constructor and its applied RuntimeReps. In contrast, here we are seeing a call to runtimeRepPrimRep while generating code for,

Bug.baz
  :: forall a_a2DY.
     Bug.Foo a_a2DY =>
     a_a2DY -> a_a2DY -> (# a_a2DY, a_a2DY #)
[GblId, Arity=1, Caf=NoCafRefs, Str=DmdType, Unf=OtherCon []]
Bug.baz =
  \ (@ (rep_a2F2 :: GHC.Types.RuntimeRep))
    (@ (a_a2F3 :: TYPE rep_a2F2))
    ($dFoo_s2P9 [Occ=Once] :: Bug.Foo a_a2F3) ->
    let {
      sat_s2Pa [Occ=Once] :: a_a2F3 -> a_a2F3 -> (# a_a2F3, a_a2F3 #)
      [LclId, Str=DmdType]
      sat_s2Pa =
        \ (eta_B2 [Occ=Once] :: a_a2F3) (eta_B1 [Occ=Once] :: a_a2F3) ->
          (# eta_B2, eta_B1 #) } in
    ($dFoo_s2P9
     `cast` (Bug.N:Foo[0] <rep_a2F2>_N <a_a2F3>_N
             :: (Bug.Foo a_a2F3 :: GHC.Types.Constraint)
                ~R#
                ((forall b_a2DW[sk].
                  (a_a2F3 -> a_a2F3 -> b_a2DW[sk])
                  -> a_a2F3 -> a_a2F3 -> b_a2DW[sk]) :: *)))
      @ 'GHC.Types.UnboxedTupleRep @ (# a_a2F3, a_a2F3 #) sat_s2Pa

I suspect the issue here is the cast,

Great testsuite material, Ryan!

mentioned in commit 27c9a7d0

Since (#,#) replies True to hasNoBinding it must be eta-expanded; so it's equivalent to

baz = bar (\x y -> (# x, y #))

and now it'd be rejected by the levity tests.

So the levity tests should account for hasNoBinding.

assigned to @rae and unassigned @bgamari

Simon says, "undersaturated hasNoBinding things need to behave as though there was a lambda".

See Note [Levity polymorphism checking] in DsMonad

tl;dr: Implementing this efficiently is non-obvious. But I think I found a way in the process of writing this comment.

So I finally sat down this morning to fix this. But I can't think of a way to do so reasonably efficiently.

The challenge is:

Figure out when an Id which hasNoBinding is used with levity polymorphic arguments.

The problem is that, in both the zonker and the desugarer (really, the only places to detect levity polymorphism problems), by the time we're looking at an Id, it's too late. We've lost all the context, including any type arguments (that is, HsWrappers) that will instantiate the Id's levity polymorphic polytype. We could do the usual thing and accumulate arguments as we descend, but that seems fragile within the complexity of HsSyn, needing to deal with HsWrap, sections, and other horrors. We could check the desugared expression, but when? And how to do so without unwrapping all the Apps that have accumulated? To solve that last question, we could add an extra return value to dsExpr stating when we're desugaring an applied hasNoBinding Id... but it's still unclear when to run the check.

My most promising idea was to check whenever desugaring an HsWrap, figuring that a use of a polymorphic hasNoBinding Id would always be directly within an HsWrap. If we cleverly use composition to avoid HsWrap foo (HsWrap bar ...), we can quickly detect when an HsWrap surrounds a hasNoBinding Id -- but only if the typechecker always puts such an Id in an HsWrap. Alas, since we have the lazy instantiation of TypeApplications, that's no longer true. If a polymorphic hasNoBinding Id is used as the argument to a higher-rank function, it's possible there will be no HsWrap. And insisting on instantiating hasNoBinding Ids right away means that these will no longer be usable with TypeApplications, which would be a shame.

Perhaps a small tweak on the above idea will work: dsExpr gets an additional parameter saying whether or not the expr being desugared is immediately wrapped in an HsWrap. If we find a HsVar with a levity-polymorphic hasNoBinding Id inside and we're not in an HsWrap, issue an error. Additionally, every time we desugar an HsWrap, check if it's immediately wrapping a hasNoBinding id; if so, so the levity polymorphism check, using the type of the desugared expression to do the check. This might just work. It's heavier than I'd like, but not unreasonably so.

I like it enough to implement. Thanks for listening. :)

Patch submitted.

Trac metadata

Trac field	Value
Differential revisions	- → D3490

Ahh good. Needless to say, I found that my attempt at a patch didn't fix the issue and I didn't have a chance to look any farther.

RyanGlScott, did ticket:13233#comment:133965 come from user code? If not then we might just have to punt this on to 8.4.

Replying to [ticket:13233#comment:135724 bgamari]:

RyanGlScott, did ticket:13233#comment:133965 come from user code? If not then we might just have to punt this on to 8.4.

It's only user code in the sense that I stumbled upon it independently while idly trying out levity polymorphism. I wouldn't be heartbroken if it didn't make it into 8.2.

I think this is a reasonable candidate for 8.2. Simon and I agree that the patch as submitted is a little smelly, but it works (modulo validation glitches). We have a plan for a better approach, but the better approach will have to wait until I free up.

Very smelly. Let's not close this, nor forget it.

mentioned in commit b460d6c9

mentioned in commit 16b0a07e

The patch Ben just committed fixes this bug, but in a stopgap manner. We can do better.

Please merge this patch, but then reopen the ticket after merging.

(Below are mostly notes to self.)

There are two separate problems:

How to ascertain whether or not a primop is saturated during desugaring (or, possibly, earlier). Simon and I once thought that we could do this in the desugarer by decomposing nested HsApps, using a little stack data type to denote all the different ways a function could be applied (HsApp, HsWrap with the right wrapper, sections, tuple-sections, HsTypeApp, maybe more) uncovering what the function was underneath, and then checking how many parameters are supplied. But now, I think it's much better to do this in the type-checker, especially because the type-checker already decomposes nested HsApps. (See TcExpr.tcApp.) When it discovers what the function is, it can check whether the function is a hasNoBinding primop. If so, it can eta-expand as necessary (but only if necessary) and use a new piece of HsSyn to denote a saturated primop. (It will be a new invariant that no unsaturated primop passes the type-checker.) This seems better than redoing the stack type in the desugarer. The original problem in #13233 (closed) was around levity polymorphism. If we make this change in the type checker, then the existing levity polymorphism checks should just work. We'll have to be careful to make the HsSyn structure printable in the way a user expects, so that the levity-polymorphism error message doesn't talk about an argument the user didn't write.
How to make sure that saturated primops stay that way in Core. This would be a new check in Lint as well as new checks on any code that does eta-contraction. It has been suggested that levity-polymorphic primops desugar to a family of levity-monomorphic primops. This surely would work, but there doesn't seem to be benefit over a plan simply to keep primops eta-expanded always. Then, there's no worry about eta-contracting levity-polymorphic arguments.

Trac metadata

Trac field	Value
Test case	- → codeGen/should_fail/T13233

added 1 deleted label

Merged to ghc-8.2 as add8e7f7.

Reopening due to comments above.

removed 1 deleted label

changed milestone to %8.4.1

The panic still happens for me, with 6f8c3ce4.

ghc-stage1: panic! (the 'impossible' happened)
  (GHC version 8.3.20170522 for x86_64-unknown-linux):
        runtimeRepPrimRep
  typePrimRep (a_12 :: TYPE k0_10)
  k0_10
  Call stack: Call stack unavailable

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

<<ghc: 1000824544 bytes, 140 GCs, 17039727/57741696 avg/max bytes residency (8 samples), 118M in use, 0.000 INIT (0.000 elapsed), 1.240 MUT (1.260 elapsed), 0.822 GC (0.826 elapsed) :ghc>>
compiler/ghc.mk:591: recipe for target 'compiler/stage2/build/StgCmmMonad.p_o' failed

My build.mk is:

BuildFlavour = prof

ifneq "$(BuildFlavour)" ""
include mk/flavours/$(BuildFlavour).mk
endif

STRIP_CMD = :

GhcStage2HcOpts += -fprof-auto-top

mentioned in issue #14122 (closed)

Trac field	Value
Version	8.0.1
Type	Bug
TypeOfFailure	OtherFailure
Priority	high
Resolution	Unresolved
Component	Compiler
Test case
Differential revisions
BlockedBy
Related
Blocking
CC	goldfire
Operating system
Architecture

typePrimRep panic while compiling GHC with profiling

Child items ...

Activity

typePrimRep panic while compiling GHC with profiling

Relates to

Activity