[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:  AndreasK
            Type:  feature request   |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.2.1
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by AndreasK):

 > But since you don't give an algorithm, it's hard to tell whether that's
 all that can happen.\\
 >
 > Here f1 C exn will return 3, but f2 exn C will throw exn. So order
 matters here. \\
 > I guess you need to prove that the algorithm you use doesn't change
 semantics.

 Indeed. I aim to maintain strictness properties of the current algorithm
 and if I manage that this can't happen.

 Intuitively this follows from the fact that if we maintain strictness
 properties and one of the arguments contains a exception we are guaranteed
 to trigger or avoid it if the old algorithm would have done so.

 Actually matching the strictness is the hard part especially avoiding
 potential loss of strictness.

 So far I worked out a way to apply good decision trees when I ignore the
 loss of strictness and a way to prevent loss of strictness on paper. I
 haven't yet worked out completely how I will combine them and how this
 will impact the complexity of the algorithm.

 > You can probably start to answer this question with some hand-written
 A/B examples: "if we had a better compiler we'd get this much better
 code".

 It's easy to come up with examples where the current approach generates
 unnecessary large code sizes on paper. What I'm not sure about is how
 often these actually occur in regular code.

 So my next steps are:
 1. Combine maintaining strictness with the approach in good trees.
    * Implement it for a subset of ghc's patterns outside of ghc.
 (Constructor/Variable/Wildcard)
    * Re implement the current approach in the same framework.
 2. Put some instrumentation into the pattern matching code and sample
 patterns from as much code as I can.
 3. Hopefully get results indicating that it's worth implementing in GHC.
 4. Implement it as part of GHC.

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