[GHC] #15124: Improve block layout for the NCG

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

[GHC] #15124: Improve block layout for the NCG

GHC - devs mailing list
#15124: Improve block layout for the NCG
-------------------------------------+-------------------------------------
           Reporter:  AndreasK       |             Owner:  (none)
               Type:  task           |            Status:  new
           Priority:  normal         |         Milestone:  8.6.1
          Component:  Compiler       |           Version:  8.2.2
  (NCG)                              |
           Keywords:  CodeGen        |  Operating System:  Unknown/Multiple
       Architecture:                 |   Type of failure:  None/Unknown
  Unknown/Multiple                   |
          Test Case:                 |        Blocked By:
           Blocking:                 |   Related Tickets:
Differential Rev(s):                 |         Wiki Page:
-------------------------------------+-------------------------------------
 The current codegen tries to place two blocks A and B next to each other
 if they are "close".

 = Drawbacks of the current algorithm

 Blocks are only considered close if one jumps to the other via a
 unconditional jump instructions.
 This is a fast and reasonable approximation. But we might be able to do
 better.

 == Calls are not considered even if they always return to the same block.

 For example it's clear that if foo == bar we jump to C here:
 {{{
 A:
         movq $block_C_info,-16(%rbp)
         cmp foo,bar
         jne D
 B:
         jmp *(%rbx) #Returns to C

         ...

 .align 8
         .infotable
 block_C_info:
 C:
         doThings
 }}}

 == Conditional jumps are never considered.

 The following block either jumps directly to c3mQ or returns there from a
 call.
 Yet that is completely ignored by the current algorithm.

 {{{
 _c3mG:
         movq $block_c3mQ_info,-8(%rbp)
         ...
         jne _c3mQ
         jmp *(%rbx) #returns to c3mQ
 }}}

 == Likelyhood of branches is not considered.

 We track information about branches which are rarely taken at the cmm
 level.
 However this information is currently lost during the Cmm -> Asm
 transformation
 which happens before we do code layout.

 This means for Cmm code where one branch is never executed the branch
 that's never
 executed might be the only one considered relevant.

 This happens for example for this stack check:
 {{{
     if ((Sp + -40) >= SpLim) (likely: True) goto c5PS; else goto c5Q3;
 }}}

 = Potential gains

 If nothing else this would allow some Cmm optimizations which are made
 useless by the current code layout algorithm.
 I have hit cases where the block layout algorithm turned optimizations
 into pessimizations of 2-5% by pulling obvious loops apart.

 Given that the scenario that leads to loops being pulled apart doesn't
 seem that unlikely I assume some loops are also pulled apart like this in
 HEAD.

 Cleaning this up ideally would also make it possible to move blocks which
 are not part of loops out of them.

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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

Re: [GHC] #15124: Improve block layout for the NCG

GHC - devs mailing list
#15124: Improve block layout for the NCG
-------------------------------------+-------------------------------------
        Reporter:  AndreasK          |                Owner:  (none)
            Type:  task              |               Status:  new
        Priority:  normal            |            Milestone:  8.6.1
       Component:  Compiler (NCG)    |              Version:  8.2.2
      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):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by AndreasK):

 Besides the usual (Aigner Guides, Intel Optimization Manuals) here are a
 few more references which should make a good starting point to explore
 this space:

 [1] Thomas Ball, James R. Larus. Branch Prediction for Free (https://do
 i.org/10.1145/173262.155119)

 [2] Hans Wennborg. The recent switch lowering improvements. (http://llv
 m.org/devmtg/2015-10/slides/Wennborg-SwitchLowering.pdf) See also: http
 s://www.youtube.com/watch?v=gMqSinyL8uk

 [3] James E. Smith. A study of branch prediction strategies (https://dl
 .acm.org/citation.cfm?id=801871)

 [4] http://llvm.org/doxygen/MachineBlockPlacement_8cpp_source.html

 [5] Karl Pettis, Robert C. Hansen. Profile guided code positioning. (ht
 tps://doi.org/10.1145/93542.93550)

 [6] Hashemi et al. Efficient procedure mapping using cache line
 coloring (https://doi.org/10.1145/258915.258931)

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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

Re: [GHC] #15124: Improve block layout for the NCG

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#15124: Improve block layout for the NCG
-------------------------------------+-------------------------------------
        Reporter:  AndreasK          |                Owner:  (none)
            Type:  task              |               Status:  new
        Priority:  normal            |            Milestone:  8.6.1
       Component:  Compiler (NCG)    |              Version:  8.2.2
      Resolution:                    |             Keywords:  CodeGen
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:  #8082             |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------
Changes (by jstolarek):

 * related:   => #8082


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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

Re: [GHC] #15124: Improve block layout for the NCG

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#15124: Improve block layout for the NCG
-------------------------------------+-------------------------------------
        Reporter:  AndreasK          |                Owner:  (none)
            Type:  task              |               Status:  new
        Priority:  normal            |            Milestone:  8.6.1
       Component:  Compiler (NCG)    |              Version:  8.2.2
      Resolution:                    |             Keywords:  CodeGen
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:  #8082             |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------
Changes (by jmct):

 * cc: jmct (added)


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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets
Reply | Threaded
Open this post in threaded view
|

Re: [GHC] #15124: Improve block layout for the NCG

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#15124: Improve block layout for the NCG
-------------------------------------+-------------------------------------
        Reporter:  AndreasK          |                Owner:  AndreasK
            Type:  task              |               Status:  new
        Priority:  normal            |            Milestone:  8.6.1
       Component:  Compiler (NCG)    |              Version:  8.2.2
      Resolution:                    |             Keywords:  CodeGen
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:  #8082             |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------
Changes (by AndreasK):

 * owner:  (none) => AndreasK


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

_______________________________________________
ghc-tickets mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-tickets