[GHC] #15103: Speed optimizations for elimCommonBlocks

[GHC]

#15103: Speed optimizations for elimCommonBlocks
-------------------------------------+-------------------------------------
        Reporter:  AndreasK          |                Owner:  AndreasK
            Type:  task              |               Status:  patch
        Priority:  normal            |            Milestone:  8.6.1
       Component:  Compiler          |              Version:  8.5
      Resolution:                    |             Keywords:  CodeGen
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):  Phab:D4597
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by Ben Gamari <ben@…>):

 In [changeset:"bd43378dfba1d6c5f19246b972b761640eedb35c/ghc"
 bd43378d/ghc]:
 {{{
 #!CommitTicketReference repository="ghc"
 revision="bd43378dfba1d6c5f19246b972b761640eedb35c"
 Optimizations for CmmBlockElim.

 * Use toBlockList instead of revPostorder.

     Block elimination works on a given Cmm graph by:
      * Getting a list of blocks.
      * Looking for duplicates in these blocks.
      * Removing all but one instance of duplicates.

     There are two (reasonable) ways to get the list of blocks.
      * The fast way: `toBlockList`
        This just flattens the underlying map into a list.
      * The convenient way: `revPostorder`
        Start at the entry label, scan for reachable blocks and return
        only these. This has the advantage of removing all dead code.

     If there is dead code the later is better. Work done on unreachable
     blocks is clearly wasted work. However by the point we run the
     common block elimination pass the input graph already had all dead
 code
     removed. This is done during control flow optimization in
     CmmContFlowOpt which is our first Cmm pass.

     This means common block elimination is free to use toBlockList
     because revPostorder would return the same blocks. (Although in
     a different order).

 * Change the triemap used for grouping by a label list
   from `(TM.ListMap UniqDFM)` to `ListMap (GenMap LabelMap)`.

     * Using GenMap offers leaf compression. Which is a trie
       optimization described by the Note [Compressed TrieMap] in
       CoreSyn/TrieMap.hs

     * Using LabelMap removes the overhead associated with UniqDFM.

   This is deterministic since if we have the same input keys the same
   LabelMap will be constructed.

 Test Plan: ci, profiling output

 Reviewers: bgamari, simonmar

 Reviewed By: bgamari

 Subscribers: dfeuer, thomie, carter

 GHC Trac Issues: #15103

 Differential Revision: https://phabricator.haskell.org/D4597
 }}}

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