[GHC] #12231: Eliminate redundant heap allocations/deallocations

[GHC]

#12231: Eliminate redundant heap allocations/deallocations
-------------------------------------+-------------------------------------
           Reporter:  harendra       |             Owner:
               Type:  bug            |            Status:  new
           Priority:  normal         |         Milestone:
          Component:  Compiler       |           Version:  8.0.1
           Keywords:                 |  Operating System:  Unknown/Multiple
       Architecture:                 |   Type of failure:  Runtime
  Unknown/Multiple                   |  performance bug
          Test Case:                 |        Blocked By:
           Blocking:                 |   Related Tickets:
Differential Rev(s):                 |         Wiki Page:
-------------------------------------+-------------------------------------
 The code generated by GHC sometimes places the Heap allocation and
 deallocation in a common path which has multiple sub-branches inside it.
 Some of those branches may not need heap at all and it just checks
 allocates and deallocates it without using. This adds unnecessary overhead
 and becomes significant when the loop is small and runs very frequently.

 Instead of putting the heap allocation code at a higher level branch we
 can move it to more specific branches where it is really needed so that it
 gets out of the paths which do not need it.

 I am attaching a specific example of such a case. The code used here is in
 a public github repository [2]. It should be quite easy to play with it,
 there are detailed instructions along with the code to reproduce and
 investigate the issue.

 The files referenced in the following text are attached with this ticket.
 They are available in the github repo as well. Look at the CMM trace in
 `decompose-loop-execution-trace.cmm` and `decompose-loop-full.cmm`, start
 at label `c4ic` where we allocate space on heap (+48). There are multiple
 possible paths from this point on, some of those use the heap and some
 don't. Some interesting paths are:

 {{{
 1) c4ic (allocate) -> c4mw -> {c4pv} -> ...
 2) c4ic (allocate) -> c4mw -> c4pw -> ((c4pr -> ({c4pe} -> ... | c4ph ->
 ...)) | cp4ps -> ...)
 }}}

 I have put those which use the heap inside curly braces, the rest do not
 use it at all. The paths which actually need the heap are rarely executed
 in this case. But because of the placement it is always allocated and
 deallocated in a the fast path which is executed almost all the time.

 If we can place this allocation at both `c4pv` and `c4pe` instead of the
 common parent then we can save the fast path from this check.  The same
 thing applies to the allocation at label `c4jd` as well.

 The whole loop is composed on 51 instructions (ghc-8.0.1) and 8 of them
 are heap adjustment related, which comes out to almost 16%. If I can get
 this back then the performance of this loop will get quite close to the
 gcc compiled code which is currently around 30% faster.

 This is a CMM level optimization which will benefit all architectures. I
 also noticed that llvm removed the heap adjustment though not the checks.

 == References ==

 * [1] mail thread - https://mail.haskell.org/pipermail/ghc-
 devs/2016-June/012275.html
 * [2] github repo for code, traces, reproduction details. See the
 GHC_PERF_ISSUE directory. - https://github.com/harendra-kumar/unicode-
 transforms/tree/GHC_PERF_ISSUE

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