[Haskell-cafe] What code is generated for binary functions of data types with multiple constructors?

[Jeff Clites]

I don't have a definitive answer, but multiple function definitions desugar to "case of" pattern match expressions, and to nested pattern matches for multiple parameters such as this. That is what shows up in transformation to Core and then to STG.

So the question boils down to whether nested pattern matches get optimized in the subsequent code generation. You can get GHC to dump the generated assembly (or intermediate LLVM or Cmm), but I can't tell based on a quick test--there's too much output so it's hard to find the important part (and I don't know offhand how LLVM compiles switch statements, which may be relevant).

So someone with knowledge of the compiler internals may have a more informative answer, but maybe that's a little helpful.

JEff

> On Aug 2, 2017, at 5:05 AM, Clinton Mead <clintonmead at gmail.com> wrote:
> 
> Assume the following:
> 
> 1. We have a type T with multiple constructors, but lets assume we're on a 64 bit machine and have at least 4 but no more than 7 constructors so we can still use pointer tagging. 
> 2. And a function "f :: T -> T -> T"
> 3. Each combination of constructors (16 in the 4 constructor case, 49 in the 7 constructor case) has an implementation (naturally many of these will call helper functions). There's no wildcard matches. 
> 
> How will GHC generate the code for "f"? Will pushing through LLVM make any difference?
> 
> Do we take the number of the first constructor, and then multiply the number of the second constructor by say 7, and then do one jump via a jump table?
> 
> Is there a bunch of nested jump tables, each with 7 options?
> 
> Is there a fall through if statement?
> 
> Something else?
> 
> I understand this probably a complex answer and perhaps doesn't have a simple answer, but I just wanted to get some sort of idea in my head of how GHC attempts to resolve code like this.
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.