Opened 5 years ago

Closed 3 years ago

Last modified 3 years ago

#10083 closed bug (fixed)

ghc: panic! (the 'impossible' happened)

Reported by: hedayaty Owned by:
Priority: normal Milestone: 8.2.1
Component: Compiler Version: 7.8.4
Keywords: hs-boot Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Compile-time crash Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s): Phab:D2210
Wiki Page:

Description (last modified by simonpj)

I used hprotoc to generate some code for Google protocol buffers.

The QueryValue.proto file is attached.

You can install hprotoc tool using cabal. then use

hprotoc QueryValue.proto

to generate code. Then create a minimal cabal file.

cabal init -m --is-library -n

Then if you build it with optimization enabled, the build will fail

ghc: panic! (the 'impossible' happened)
  (GHC version 7.8.3 for x86_64-apple-darwin):
	Simplifier ticks exhausted
    When trying UnfoldingDone $j_sEMq{v} [lid]
    To increase the limit, use -fsimpl-tick-factor=N (default 100)
    If you need to do this, let GHC HQ know, and what factor you needed
    To see detailed counts use -ddump-simpl-stats
    Total ticks: 59242

Attachments (2)

QueryValue.proto (846 bytes) - added by hedayaty 5 years ago.
Proto-Buffer File
QueryValue.tar.bz2 (3.7 KB) - added by hedayaty 4 years ago.
Folder Project reporoducing the bug

Download all attachments as: .zip

Change History (34)

Changed 5 years ago by hedayaty

Attachment: QueryValue.proto added

Proto-Buffer File

comment:1 Changed 5 years ago by hedayaty

I play a little with generated code. The bug appears to be related to the type QueryValue.QueryValue.PropertyQueryValue being instance of Eq.

comment:2 Changed 5 years ago by simonpj

What happens if you follow the advice and increase -fsimpl-tick-factor?

comment:3 Changed 5 years ago by hedayaty

I raised it up to 1M(1000000). Did not help!

comment:4 Changed 4 years ago by simonpj

Can you try with the 7.10 release candidate?

Also, if running hprotoc QueryValue.proto generates some file, can't you just upload that file, so that we don't have to build hprotoc?

Can you give the exact sequence of commands, starting from that file, to exhibit the problem?

Simon

Last edited 4 years ago by simonpj (previous) (diff)

comment:5 Changed 4 years ago by simonpj

Description: modified (diff)

comment:6 Changed 4 years ago by simonpj

Status: newinfoneeded

hedayaty, just to say that I'm stalled on this, pending comment:4.

Simon

comment:7 Changed 4 years ago by hedayaty

OOps sorry! I missed the notification. I will test it ASAP.

comment:8 Changed 4 years ago by hedayaty

I attached the generated folder. I will try to handcraft a minimal version(not by generated code), reproducing the bug.

Last edited 4 years ago by hedayaty (previous) (diff)

comment:9 Changed 4 years ago by thomie

Architecture: x86_64 (amd64)Unknown/Multiple
Operating System: MacOS XUnknown/Multiple

Probably not Mac specific.

@hedayaty: did you manage to create a minimal example reproducing the bug?

Changed 4 years ago by hedayaty

Attachment: QueryValue.tar.bz2 added

Folder Project reporoducing the bug

comment:10 Changed 4 years ago by hedayaty

I made a new attachment. This is minimal as far the generated code can go. Please see if you can tackle the bug on this.

BTW, do you mind if I prioritize the bug? It is blocking adding a feature in our product.

comment:11 Changed 4 years ago by simonpj

Did you try with the 7.10 release candidate (comment:4)? Maybe it is fixed already?

comment:12 Changed 4 years ago by simonpj

OK, good. With your reduced test case I can reproduce the bug. I've produced a much smaller version, in two variants

---------- RSR.hs-boot ------------
module RSR where
  data RSR
  instance Eq RSR

---------- SR.hs ------------
module SR where
  import {-# SOURCE #-} RSR
  data SR = MkSR RSR deriving( Eq )

---------- SR.hs ------------
module RSR where
  import SR
  data RSR = MkRSR SR deriving( Eq )

Now compile like this

ghc -c -O RSR.hs-boot
ghc -c -O SR.hs
ghc -c -O RSR.hs

Indeed, compiling RSR causes infinite inlining.

Here's a version that doesn't use instances and so is a bit clearer

---------- RSR.hs-boot ------------
module RSR where
  data RSR
  eqRSR :: RSR -> RSR -> Bool

---------- SR.hs ------------
module SR where
  import {-# SOURCE #-} RSR
  data SR = MkSR RSR
  eqSR (MkSR r1) (MkSR r2) = eqRSR r1 r2

---------- SR.hs ------------
module RSR where
  import SR
  data RSR = MkRSR SR -- deriving( Eq )
  eqRSR (MkRSR s1) (MkRSR s2) = (eqSR s1 s2)
  foo x y = not (eqRSR x y)

This fails in the same way. The problem is this. When compiling RSR we get this code

RSR.eqRSR :: RSR.RSR -> RSR.RSR -> GHC.Types.Bool
RSR.eqRSR =
  \ (ds_dkA [Occ=Once!] :: RSR.RSR)
    (ds_dkB [Occ=Once!] :: RSR.RSR) ->
    case ds_dkA of _ { RSR.MkRSR s1_aeO [Occ=Once] ->
    case ds_dkB of _ { RSR.MkRSR s2_aeP [Occ=Once] ->
    SR.eqSR s1_aeO s2_aeP
    }
    }

RSR.foo :: RSR.RSR -> RSR.RSR -> GHC.Types.Bool
RSR.foo =
  \ (x_aeQ [Occ=Once] :: RSR.RSR) (y_aeR [Occ=Once] :: RSR.RSR) ->
    GHC.Classes.not (RSR.eqRSR x_aeQ y_aeR)

Notice that neither are (apprently) recursive, and neither is a loop breaker. Now, when optimising foo:

  • Inline eqRSR
  • Inline eqSR

but the result of inlining eqSR from SR is another call to eqRSR, so everything repeats.

It's pretty simple, so I'm quite surprised that this hasn't bitten us before now!

Next: figure out a solution.

comment:13 Changed 4 years ago by hedayaty

Thanks @simonpj for a minimal reproduction of the issue.

The bug exists in 6.10 RC2 as well

comment:14 Changed 4 years ago by simonpj

I'm conscious that you (alone, as far as I can tell) are held up by this bug. I think I know how to fix it, but it's not entirely straightforward and we are very far down the road for 7.10. So I'd like to see if we can find a workaroud.

Two suggestions. First idea. compile RSR (the one with an hs-boot file) with -funfolding-use-threshold=0. That will switch off inlining in that module only.

Second idea (less brutal). In the first version (which is close to what you have), instead of

  data RSR = MkRSR SR deriving( Eq )

say

  data RSR = MkRSR SR

  instance Eq RSR where
     (==) = eqRSR

  eqRSR :: RSR -> RSR -> Bool
  {-# NOINLINE eqRSR #-}
  eqRSR (RSR s1) (RSR s2) = s1==s2

I think that'll work. It's tiresome because you can't use the auto-generated equality method, but your data types are small. You may need to do this for other instances.

I hope that this will get you unglued.

Simon

comment:15 Changed 4 years ago by hedayaty

OK. We can take the first one as default solution. Since the code is being generated, I can not modify the code. However, we might try diving into code generator!

comment:16 Changed 4 years ago by Simon Peyton Jones <simonpj@…>

In 3c44a46b/ghc:

Refactor self-boot info

This patch is a simple refactoring that prepares for a later one,
related to Trac #10083.

* Add a field tcg_self_boot :: SelfBootInfo to TcGblEnv,
  where SelfBootInfo is a new data type, describing the
  hi-boot file, if any, for the module being compiled.

* Make tcHiBootIface return SelfBootInfo, a new data type

* Make other functions get SelfBootInfo from the monad.

* Remove tcg_mod_name from TcGblEnv; it was barely used and
  simpler to pass around explicitly.

comment:17 Changed 4 years ago by Simon Peyton Jones <simonpj@…>

In efa7b3a/ghc:

Add NOINLINE for hs-boot functions

This fixes Trac #10083.

The key change is in TcBinds.tcValBinds, where we construct
the prag_fn.  With this patch we add a NOINLINE pragma for
any functions that were exported by the hs-boot file for this
module.

See Note [Inlining and hs-boot files], and #10083, for details.

The commit touches several other files becuase I also changed the
representation of the "pragma function" from a function TcPragFun
to an environment, TcPragEnv. This makes it easer to extend
during construction.

comment:18 Changed 4 years ago by simonpj

Actually comment:17 does not fix #10083, because I found that the fix made the compiler go slower:

Unexpected stat failures:
   perf/compiler  T1969 [stat not good enough] (normal)
   perf/compiler  T9872a [stat not good enough] (normal)
   perf/compiler  T9872b [stat not good enough] (normal)
   perf/compiler  T9872c [stat not good enough] (normal)
   perf/compiler  T9872d [stat not good enough] (normal)

bytes allocated value is too high:
    Deviation   T1969(normal) bytes allocated:       7.5 %
    Deviation   T9872d(normal) bytes allocated:      9.3 %
    Deviation   T9872c(normal) bytes allocated:      8.4 %

by about 8% allocation overall. So the patch has all the code, but the key bit is commented out.

See Note [Inlining and hs-boot files] in TcBinds. Presumably disabling inlining of functions exported by a hs-boot file really kills GHC's performance somewhere, implausible though it sounds. I suppose the next thing to do is to find out why, but I just don't have time to do that now, so I'm parking the whole thing. Sigh. Does anyone want to help?

comment:19 Changed 4 years ago by thomie

Milestone: 8.0.1
Status: infoneedednew

comment:20 Changed 4 years ago by thomie

Milestone: 8.0.1

comment:21 Changed 3 years ago by ezyang

Keywords: hs-boot added

Here is an interesting phenomenon in the test case in this bug: it does not infinite loop if you use --make. If we look carefully at the inlining log we can see why (I added an extra trace for when there is no unfolding):

Inlining done:
    T10083.eqRSR
\ (ds_d1H8 [Occ=Once!] :: T10083.RSR)
  (ds_d1H9 [Occ=Once!] :: T10083.RSR) ->
  case ds_d1H8 of { T10083.MkRSR s1 [Occ=Once] ->
  case ds_d1H9 of { T10083.MkRSR s2 [Occ=Once] ->
  T10083a.eqSR s1 s2
  }
  }
Inlining done:
    T10083a.eqSR
\ (ds [Occ=Once!] :: T10083a.SR) (ds1 [Occ=Once!] :: T10083a.SR) ->
  case ds of { T10083a.MkSR r1 [Occ=Once] ->
  case ds1 of { T10083a.MkSR r2 [Occ=Once] -> T10083.eqRSR r1 r2 }
  }
no unfolding eqRSR

Notice that once we unfold eqSR, there is NO INLINING on eqRSR! Coincidence? Absolutely not: when we compiled B.hs we added an Id to the HPT which has an unfolding referring to the eqRSR from the hs-boot file, which obviously doesn't have an inlining. And clearly we don't flush the HPT prior to typechecking A.hs. So we will stop inlining once we hit this hs-boot Id.

The situation with one-shot is different, however: we haven't loaded the interface, and by the time we try to load the Id for eqRSR when loading the unfolding for eqSR, it's already in the environment and so we give it the right unfolding... disaster!

There is something pesky going on with the interface loading business but that's for another bug.

comment:22 Changed 3 years ago by ezyang

Another observation: ghc --make -fforce-recomp -ddump-if-trace hangs infinitely. That's a bug in its own right; one that I've seen before but never for such a nice test-case.

FIXED in https://phabricator.haskell.org/D2187

Last edited 3 years ago by ezyang (previous) (diff)

comment:23 Changed 3 years ago by ezyang

Simon, re the performance problem, I'm no inliner expert but I think the problem is that you're always giving declarations which occur in the hs-boot file "never inline", even when it's totally inappropriate. For example, rewrite eqRSR to unconditionally return True and you'll still get:

-- RHS size: {terms: 9, types: 6, coercions: 0}
eqRSR [InlPrag=[NEVER]] :: RSR -> RSR -> Bool
[GblId, Arity=2, Caf=NoCafRefs, Str=<S,1*H><S,1*H>]
eqRSR =
  \ (ds_d1H9 :: RSR) (ds1_d1Ha :: RSR) ->
    case ds_d1H9 of { MkRSR s1_aKA ->
    case ds1_d1Ha of { MkRSR s2_aKB -> GHC.Types.True }
    }

I bet the inability to inline eqRSR even if you don't depend on the boot file is causing the performance degradation.

Last edited 3 years ago by ezyang (previous) (diff)

comment:24 Changed 3 years ago by simonpj

I bet the inability to inline eqRSR even if you don't depend on the boot file is causing the performance degradation.

Yes, that's what I speculated in comment:18, final para. But I still don't know what to do about it.

comment:25 Changed 3 years ago by ezyang

Ah, I misparsed comment:18.

How about call-site loop breakers? Put something in IdDetails saying that you should never inline this variable, and then always annotate any direct references to an hs-boot file with this marker.

comment:26 Changed 3 years ago by simonpj

I don't understand how that would differ from marking it NOINLINE. Can you be more specific?

comment:27 Changed 3 years ago by ezyang

Simon and I agreed on our call that we should pursue inserting noinline f for any references to f from an hs-boot file. The noinline gets removed during CorePrep and as a result we won't infinitely try to unfold when we compile the module.

How do we know when to insert these noinlines? It should happen in the typechecker or renamer, and the idea will be to mark Ids which come from a boot file as "boot identities"; then we know to insert noinline.

comment:28 Changed 3 years ago by ezyang

Differential Rev(s): Phab:D2210
Milestone: 8.0.2
Status: newpatch

comment:29 Changed 3 years ago by Edward Z. Yang <ezyang@…>

In 5a8fa2e/ghc:

When a value Id comes from hi-boot, insert noinline. Fixes #10083.

Summary:
This also drops the parked fix from
efa7b3a474bc373201ab145c129262a73c86f959
(though I didn't revert the refactoring).

Signed-off-by: Edward Z. Yang <ezyang@cs.stanford.edu>

Test Plan: validate

Reviewers: simonpj, austin, bgamari

Subscribers: thomie

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

GHC Trac Issues: #10083

comment:30 Changed 3 years ago by ezyang

Resolution: fixed
Status: patchclosed

comment:31 Changed 3 years ago by thomie

Milestone: 8.0.28.2.1

comment:32 Changed 3 years ago by simonpj

Just for the record #12789 was another example of this

Note: See TracTickets for help on using tickets.