panic when compiling SHA

Wed Jan 8 07:43:15 UTC 2014

Just a guess, but I imagine it works for you because on amd64 the NCG
will have more registers available to satisfy all the live ranges. On
32bit the situation is much worse because that's just how x86 is.

In any case, I'm inclined to also agree this is a bug, and merits an
open ticket. And it's not like there is no precedent for these things:
plenty of libraries (vector-algorithms & others) stress the simplifier
e.g. exhausting the simplifier ticks, and we tend to try and work
towards fixing these.

While INLINE is crucial in vector-algorithms, it probably isn't for
the SHA package, and based on what Adam said I do think this perhaps
merits some more investigation. I doubt it will get 'fixed' properly
in time for 7.8 though - a workaround or something will probably be
needed for 32bit builds in some way (perhaps just a few careful
refactorings with uses of NOINLINE, although I can't estimate the
performance impact.)

On Wed, Jan 8, 2014 at 1:14 AM, Iavor Diatchki <iavor.diatchki at gmail.com> wrote:
> Hello,
>
> I find it a bit perplexing (and not at all constructive) that we are arguing
> over semantics here.  We have a program (1 module, ~1000 lines of "no fancy
> extension Haskell"), which causes GHC to panic.  This is a bug.  An
> invariant that we were assuming did not actually hold.  Hence the message
> that the "impossible" happened.  If GHC decides to refuse to compile a
> program, it should not panic but, rather, explain what happened and maybe
> suggest a workaround.
>
> I am not familiar with GHC's back-end, but it seems that there might be
> something interesting that's going on here.   The SHA library works fine
> with 7.6.3, and it compiles (admittedly very slowly) using GHC head on my
> 64-bit machine.   So something has changed, and it'd be nice if we
> understood what's causing the problem.
>
> Ben suggested that the issue might be the INLINE pragmas, but clearly that's
> not the problem, as Adam reproduced the same behavior without those pragmas.
> If the issue is indeed with the built-in inline heuristics, it sounds like
> we either should fix the heuristics, or come up with some suggestions about
> what to avoid in user programs.  Or, perhaps, the issue something completely
> unrelated (e.g., a bug in the register allocator).   Either way, I think
> this deserves a ticket.
>
> -Iavor
>
>
>
>
>
>
>
>
> On Tue, Jan 7, 2014 at 10:11 PM, Carter Schonwald
> <carter.schonwald at gmail.com> wrote:
>>
>> Adam,
>> I agree that it should be considered a misfeature (or at the very least a
>> good stress test that currently breaks the register allocator). That said,
>> INLINE / INLINEABLE are only needed for intermodule optimization, have you
>> tried using the special "inline" primop selectively, or using INLINEABLE
>> plus selective inline? I think inline should work in the defining module
>> even if you don't provide an INLINE or INLINEABLE.
>>
>> question 1: does the code compile well when you use -fllvm? (seems like
>> the discussion so far has been NCG focused).
>> how does the generated assembly fair that way vs the workaroudn path on
>> NCG?
>>
>>
>>
>>
>> On Tue, Jan 7, 2014 at 6:57 PM, Adam Wick <awick at galois.com> wrote:
>>>
>>> On Jan 7, 2014, at 2:27 AM, Ben Lippmeier <benl at ouroborus.net> wrote:
>>> > On 07/01/2014, at 9:26 , Adam Wick <awick at galois.com> wrote:
>>> >
>>> >>> Not if we just have this one test. I'd be keen to blame excessive use
>>> >>> of inline pragmas in the SHA library itself, or excessive optimisation
>>> >>> flags. It's not really a bug in GHC until there are two tests that exhibit
>>> >>> the same problem.
>>> >>
>>> >> The SHA library uses SPECIALIZE, INLINE, and bang patterns in fairly
>>> >> standard ways. There’s nothing too exotic in there, I just basically
>>> >> sprinkled hints in places I thought would be useful, and then backed those
>>> >> up with benchmarking.
>>> >
>>> > Ahh. It's the "sprinkled hints in places I thought would be useful"
>>> > which is what I'm concerned about. If you just add pragmas without
>>> > understanding their effect on the core program then it'll bite further down
>>> > the line. Did you compare the object code size as well as wall clock
>>> > speedup?
>>>
>>> I understand the pragmas and what they do with my code. I use SPECIALIZE
>>> twice for two functions. In both functions, it was clearer to write the
>>> function as (a -> a -> a -> a), but I wanted specialized versions for the
>>> two versions that were going to be used, in which (a == Word32) or (a ==
>>> Word64). This benchmarked as faster while maintaining code clarity and
>>> concision. I use INLINE in five places, each of them a SHA step function,
>>> with the understanding that it would generate ideal code for a compiler for
>>> the performance-critical parts of the algorithm: straight line, single-block
>>> code with no conditionals.
>>>
>>> When I did my original performance work, several versions of GHC ago, I
>>> did indeed consider compile time, runtime performance, and space usage. I
>>> picked what I thought was a reasonable balance at the time.
>>>
>>> I also just performed an experiment in which I took the SHA library,
>>> deleted all instances of INLINE and SPECIALIZE, and compiled it with HEAD on
>>> 32-bit Linux. You get the same crash. So my usage of SPECIALIZE and INLINE
>>> is beside the point.
>>>
>>> > Sadly, "valid input" isn't a well defined concept in practice. You
>>> > could write a "valid" 10GB Haskell source file that obeyed the Haskell
>>> > standard grammar, but I wouldn't expect that to compile either.
>>>
>>> I would. I’m a little disappointed that ghc-devs does not. I wouldn’t
>>> expect it to compile quickly, but I would expect it to run.
>>>
>>> > You could also write small (< 1k) source programs that trigger
>>> > complexity problems in Hindley-Milner style type inference. You could also
>>> > use compile-time meta programming (like Template Haskell) to generate
>>> > intermediate code that is well formed but much too big to compile. The fact
>>> > that a program obeys a published grammar is not sufficient to expect it to
>>> > compile with a particular implementation (sorry to say).
>>>
>>> If I write a broken Template Haskell macro, then yes, I agree. This is
>>> not the case in this example.
>>>
>>> > Adding an INLINE pragma is akin to using compile-time meta programming.
>>>
>>> Is it? I find that a strange point of view. Isn’t INLINE just a strong
>>> hint to the compiler that this function should be inlined? How is using
>>> INLINE any different from simply manually inserting the code at every call
>>> site?
>>>
>>>
>>> - Adam
>>> _______________________________________________
>>> ghc-devs mailing list
>>> ghc-devs at haskell.org
>>> http://www.haskell.org/mailman/listinfo/ghc-devs
>>>
>>
>>
>> _______________________________________________
>> ghc-devs mailing list
>> ghc-devs at haskell.org
>> http://www.haskell.org/mailman/listinfo/ghc-devs
>>
>
>
> _______________________________________________
> ghc-devs mailing list
> ghc-devs at haskell.org
> http://www.haskell.org/mailman/listinfo/ghc-devs
>

-- 
Regards,

Austin Seipp, Haskell Consultant
Well-Typed LLP, http://www.well-typed.com/