#9157: cmm common block not eliminated -------------------------------------+------------------------------------ Reporter: wojteknar | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Unknown/Multiple Type of failure: Other | Difficulty: Unknown Test Case: | Blocked By: Blocking: | Related Tickets: -------------------------------------+------------------------------------ Changes (by jstolarek): * cc: jan.stolarek@… (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9157#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9157: cmm common block not eliminated -------------------------------------+------------------------------------ Reporter: wojteknar | Owner: jstolarek Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Unknown/Multiple Type of failure: Other | Difficulty: Unknown Test Case: | Blocked By: Blocking: | Related Tickets: -------------------------------------+------------------------------------ Changes (by jstolarek): * cc: simonmar (added) Comment: I confirmed that this bug exists in HEAD and found the reason. I suspect that Common Block Elimination as implemented now might not work as intended. Here's what's happening. Code attached in the bug report generates 8 identical blocks (showing only 2 here for brevity): {{{ c1Dm: _s1CG::I64 = I64[_s1Cy::P64 + 7]; _g1CN::I64 = _s1CG::I64; goto c1Dd; c1Dl: _s1CF::I64 = I64[_s1Cy::P64 + 7]; _g1CN::I64 = _s1CF::I64; goto c1Dd; }}} We hash these block ignoring the labels and we get identical hashes as expected. Then we get to the point when we attempt to actually eliminate common blocks. [https://github.com/ghc/ghc/blob/master/compiler/cmm/CmmCommonBlockElim.hs#L6... We check these two block for equality], except that this time we don't ignore the labels and other unique identifiers (eg. [https://github.com/ghc/ghc/blob/master/compiler/cmm/CmmCommonBlockElim.hs#L1... here]). We conclude that these two block are different because local registers `_s1CG` are `_s1CF` are different. Later the sinking pass makes these two blocks identical. The result that we see in the Cmm output are 8 identical blocks: {{{ c1Dm: _g1CN::I64 = I64[_s1Cy::P64 + 7]; goto c1Dd; c1Dl: _g1CN::I64 = I64[_s1Cy::P64 + 7]; goto c1Dd; }}} I suspect that this is not how CBE was intended to work. I mean if we ignore the labels during hashing then we should probably be smarter when actually comparing the blocks. Except that this is not trivial. I wonder if we could simply move CBE to the end of Cmm pipeline, so that it is run after sinking and other optimizations? Or is there A Good Reason to have CBE at the beginning of the pipeline and not at the end? CCing Simon Marlow - perhaps he can tell. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9157#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9157: cmm common block not eliminated -------------------------------------+------------------------------------ Reporter: wojteknar | Owner: jstolarek Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Unknown/Multiple Type of failure: Other | Difficulty: Unknown Test Case: | Blocked By: Blocking: | Related Tickets: -------------------------------------+------------------------------------ Comment (by simonmar): Yes, I think Simon PJ's reason above is exactly why hashes don't include labels: so that the hashes remain stable under elimination of common blocks. After eliminating some blocks, more opportunities for elimination emerge, so the algorithm keeps iterating until there are no more blocks to eliminate. Originally CBE was there to catch a common case of common blocks that occurred in the code we generated for case expressions. But that pattern is handled directly by the code generator (we don't generate the common blocks anymore), and hence CBE is only enabled with -O. As with most optimisations, CBE interacts with other passes, so there may be more (or fewer) opportunities for CBE at different stages during the pipeline. Whether it's worthwhile (a) having another CBE pass (maybe with -O2 only) or (b) moving the existing CBE pass later in the pipeline, is a matter for measurement. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9157#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9157: cmm common block not eliminated -------------------------------------+------------------------------------ Reporter: wojteknar | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Unknown/Multiple Type of failure: Other | Difficulty: Unknown Test Case: | Blocked By: Blocking: | Related Tickets: -------------------------------------+------------------------------------ Changes (by jstolarek): * owner: jstolarek => -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9157#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9157: cmm common block not eliminated -------------------------------------+------------------------------------- Reporter: wojteknar | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Other | Unknown/Multiple Blocked By: | Test Case: Related Tickets: | Blocking: | Differential Revisions: -------------------------------------+------------------------------------- Comment (by jstolarek): Replying to [comment:3 jstolarek]:

[https://github.com/ghc/ghc/blob/master/compiler/cmm/CmmCommonBlockElim.hs#L6... We check these two block for equality], except that this time we don't ignore the labels and other unique identifiers (eg. [https://github.com/ghc/ghc/blob/master/compiler/cmm/CmmCommonBlockElim.hs#L1... here]). These links are no longer accurate because I didn't link to a particular commit. Here's a fixed version: [https://github.com/ghc/ghc/blob/b8b8d190525b073aa44f7a5bda555e25ea7ef5d6/com... We check these two block for equality], except that this time we don't ignore the labels and other unique identifiers (eg. [https://github.com/ghc/ghc/blob/b8b8d190525b073aa44f7a5bda555e25ea7ef5d6/com... here]). -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9157#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9157: cmm common block not eliminated -------------------------------------+------------------------------------- Reporter: wojteknar | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: CodeGen 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: | -------------------------------------+------------------------------------- Changes (by simonpj): * keywords: => CodeGen -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9157#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler