[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):

 I realized I have no written anything about how to actually do this.\\
 Nothing of this is set in stone yet but generally:

 To prevent additional strictness we can always limit argument evaluation
 to these columns which will be evaluated for any result (ignoring the
 possibility of pattern match failure).

 While we do have to compute that property for each column it should be
 able to do this while getting the data required to pick a good column. So
 I don't expect that to be too expensive.

 Preventing loss of strictness is a lot more expensive to calculate I fear.
 I also did not yet think much about how this impacts potential performance
 gains or how to optimize/implement it. So with this pretext here we go:

 Given a matrix of patterns based on your example
 {{{
 A A
 A B
 _ C
 }}}

 My current idea is to associate constraints with each element starting
 without no constraints. If we chose column 2 we get on decomposition for C
 a matrix consisting only of `_`. However during matrix decomposition we
 check for constraints resulting from our selection and add these to the
 remaining matrix.

 In this case we would generate {Col1 != bot} for that entry.\\
 When selecting a column we first have to resolve constraints associated
 with it.
 So while the resulting matrix has only a wildcard the constraint forces us
 the generate a case statement for the column ensuring the first parameter
 gets evaluated.

 Constraints are created by looking at the rows we eliminate based on the
 result we generate code for.
 But I have not yet formalized that to a degree where a detailed writeup on
 the specifics makes sense.

 While this is guaranteed to be more expensive then the current approach i
 hope to that performance gains as well as less work required by the
 simplifier makes up for it.

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