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

 = There are shortcomings in the current codegen of GHC that eliminate much
 of the gains to be had here.

 * Changing the order of pattern matches can lead to more floating of case
 alternatives to the top level. The associated cost from calling a top
 level function overshadows potential gains when that happens. This is
 expensive since:
   * They have to confirm to the calling convention, so can require
 register shifting.
   * They prohibit us from falling through to the alternative.
   * They split the code in memory usually leading to more cache pressure.
   There is an ticket about the issue already: #15560

 * The algorithm depends on shared pattern matching subtrees being commoned
 up which doesn't work yet. As a consequence we quite often end up with
 duplicate code which kills performance.
   * I had hoped to leave this to CSE but it turns out GHC's CSE is not as
 good as one would hope in this regard. See
 https://ghc.haskell.org/trac/ghc/wiki/MoreCSE for some discussion.
   * We could do an special CSE for just the pattern matching trees.
 Butduring desugaring we don't work bottom up but top down. We generate
 functions which take as argument the expression to put into the case
 alternatives instead of directly generating an AST expression. It wasn't
 clear how to work with or refactor this to allow commoning up of pattern
 matching subtrees at the time I last looked at this.

 * Last and least: The current codelayout is heavily dependent on how we
 generate `if` statements for Cmm. As consequence performance can vary a
 lot when changing the order of pattern matches. I did some work on code
 layout which hopefully will help with this in #15124. Which might change
 the performance difference between differing pattern match algorithms.

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