[GHC] #14201: Implement ideas from "Compiling Pattern Matching to Good Decision Trees"

[GHC]

#14201: Implement ideas from "Compiling Pattern Matching to Good Decision Trees"
-------------------------------------+-------------------------------------
           Reporter:  AndreasK       |             Owner:  (none)
               Type:  feature        |            Status:  new
  request                            |
           Priority:  normal         |         Milestone:
          Component:  Compiler       |           Version:  8.2.1
           Keywords:                 |  Operating System:  Unknown/Multiple
       Architecture:                 |   Type of failure:  None/Unknown
  Unknown/Multiple                   |
          Test Case:                 |        Blocked By:
           Blocking:                 |   Related Tickets:
Differential Rev(s):                 |         Wiki Page:
-------------------------------------+-------------------------------------
 = The basic Ideas

 Currently GHC uses Augustssons algorithm for pattern matching which was
 published in 85 which works fine for many cases.

 However there has been research on how to do better than that for a while
 now. Most notably by Maranget in "Compiling Pattern Matching to Good
 Decision Trees".

 I plan to look into applying his ideas to GHC for my undergraduate thesis.

 Thanks to imprecise exceptions we should be able to reorder argument
 evaluation as long as this doesn't make our programs more strict. Proofing
 that is high on my bucket list but hasn't been done yet.

 = Pros and Cons

 **Advantages** would be:

 * It should lead to equal or better code for the vast majority of
 patterns.
 * It might reduce compile times for cases were we can desugar directly to
 good code.

 **Disadvantages**:

 * Desugaring gets more complex.


 It' obvious that since the underlying algorithm is more complex the
 desugarer would also grow in complexity in accordance. It is hard to say
 in advance how much of a difference it will make but I hope it won't be
 too bad.

 Depending on the runtime of the new algorithm compared to the old one this
 might also speed up compilation for cases where the old algorithm
 generated code that had to be heavily optimized by the simplifier.

-- 
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14201>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler