Simon Jakobi pushed to branch wip/sjakobi/T27368-cbe-compress at Glasgow Haskell Compiler / GHC

Commits:

2 changed files:

Changes:

  • compiler/GHC/Cmm/CommonBlockElim.hs
    ... ... @@ -30,34 +30,6 @@ import Control.Arrow (first, second)
    30 30 
     import Data.List.NonEmpty (NonEmpty (..))
    31 31 
     import qualified Data.List.NonEmpty as NE
    32 32
    33 
    --- -----------------------------------------------------------------------------
    34 
    --- Eliminate common blocks
    35 
    -
    36 
    --- If two blocks are identical except for the label on the first node,
    37 
    --- then we can eliminate one of the blocks. To ensure that the semantics
    38 
    --- of the program are preserved, we have to rewrite each predecessor of the
    39 
    --- eliminated block to proceed with the block we keep.
    40 
    -
    41 
    --- The algorithm iterates over the blocks in the graph,
    42 
    --- checking whether it has seen another block that is equal modulo labels.
    43 
    --- If so, then it adds an entry in a map indicating that the new block
    44 
    --- is made redundant by the old block.
    45 
    --- Otherwise, it is added to the useful blocks.
    46 
    -
    47 
    --- To avoid comparing every block with every other block repeatedly, we group
    48 
    --- them by
    49 
    ---   * a hash of the block, ignoring labels (explained below)
    50 
    ---   * the list of outgoing labels
    51 
    --- The hash is invariant under relabeling, so we only ever compare within
    52 
    --- the same group of blocks.
    53 
    ---
    54 
    --- The list of outgoing labels is updated as we merge blocks (that is why they
    55 
    --- are not included in the hash, which we want to calculate only once).
    56 
    ---
    57 
    --- All in all, two blocks should never be compared if they have different
    58 
    --- hashes, and at most once otherwise. Previously, we were slower, and people
    59 
    --- rightfully complained: #10397
    60 
    -
    61 33 
     {- Note [Resolving the CBE substitution]
    62 34 
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    63 35 
     The substitution built by `iterate` can contain chains: the winner of a
    ... ... @@ -79,10 +51,13 @@ produced no stack map for it, and setInfoTableStackMap panicked.
    79 51
    80 52 
     With the substitution resolved, every edge -- including those in the
    81 53 
     unreachable losing copies -- points at a surviving block, and every
    82 
    -surviving block is reachable: the input graph contains no unreachable
    83 
    -blocks (the control-flow optimiser runs first and drops them), and
    84 
    -merging only diverts paths from losers to their body-equal winners.
    85 
    -In particular the continuation of a call in a losing copy is also the
    54 
    +block the resolved substitution maps to is reachable: merging diverts
    55 
    +each loser's predecessors to its winner, so a winner inherits its
    56 
    +losers' reachability.  (The input graph is not entirely free of
    57 
    +unreachable blocks -- the control-flow optimiser that runs first can
    58 
    +leave unreachable goto-only blocks behind -- but such blocks contain
    59 
    +no calls, and if one wins a merge it thereby becomes reachable.)  In
    60 
    +particular the continuation of a call in a losing copy is also the
    86 61 
     continuation of its reachable winner, so stack layout has a stack map
    87 62 
     for it.
    88 63
    ... ... @@ -90,17 +65,46 @@ Resolving also improves copyTicks: each loser's ticks are copied into
    90 65 
     its final representative instead of into a dead intermediate block.
    91 66 
     -}
    92 67
    93 
    --- TODO: Use optimization fuel
    68 
    +-- | Merge identical blocks
    69 
    +--
    70 
    +-- If two blocks are identical except for the label on the first node,
    71 
    +-- then we can eliminate one of the blocks. To ensure that the semantics
    72 
    +-- of the program are preserved, we have to rewrite each predecessor of the
    73 
    +-- eliminated block to proceed with the block we keep.
    74 
    +--
    75 
    +-- Unreachable blocks may occur both in the input and in the output:
    76 
    +-- we process whatever the block map contains, and a merge leaves the
    77 
    +-- losing copy behind, unreachable.  See Note [unreachable blocks] in
    78 
    +-- GHC.Cmm.Pipeline.
    79 
    +--
    80 
    +-- The algorithm iterates over the blocks in the graph,
    81 
    +-- checking whether it has seen another block that is equal modulo labels.
    82 
    +-- If so, then it adds an entry in a map indicating that the new block
    83 
    +-- is made redundant by the old block.
    84 
    +-- Otherwise, it is added to the useful blocks.
    85 
    +--
    86 
    +-- To avoid comparing every block with every other block repeatedly, we group
    87 
    +-- them by
    88 
    +--   * a hash of the block, ignoring labels (explained below)
    89 
    +--   * the list of outgoing labels
    90 
    +-- The hash is invariant under relabeling, so we only ever compare within
    91 
    +-- the same group of blocks.
    92 
    +--
    93 
    +-- The list of outgoing labels is updated as we merge blocks (that is why they
    94 
    +-- are not included in the hash, which we want to calculate only once).
    95 
    +--
    96 
    +-- All in all, two blocks should never be compared if they have different
    97 
    +-- hashes, and at most once otherwise. Previously, we were slower, and people
    98 
    +-- rightfully complained: #10397
    94 99 
     elimCommonBlocks :: CmmGraph -> CmmGraph
    100 
    +-- TODO: Use optimization fuel
    95 101 
     elimCommonBlocks g = replaceLabels env' $ copyTicks env' g
    96 102 
       where
    97 103 
          -- See Note [Resolving the CBE substitution]
    98 104 
          env' = mapMap (lookupBid env) env
    99 105 
          env = iterate mapEmpty blocks_with_key
    100 
    -     -- The order of blocks doesn't matter here. While we could use
    101 
    -     -- revPostorder which drops unreachable blocks this is done in
    102 
    -     -- ContFlowOpt already which runs before this pass. So we use
    103 
    -     -- toBlockList since it is faster.
    106 
    +     -- Block order is irrelevant here, so we use toBlockList, which
    107 
    +     -- is cheaper than revPostorder.
    104 108 
          groups = groupByInt hash_block (toBlockList g) :: [[CmmBlock]]
    105 109 
          blocks_with_key = [ [ (successors b, [b]) | b <- bs] | bs <- groups]
    106 110

  • compiler/GHC/Cmm/Pipeline.hs
    ... ... @@ -353,10 +353,21 @@ _GLOBAL_OFFSET_TABLE_, regardless of which entry point we arrived via.
    353 353
    354 354 
     {- Note [unreachable blocks]
    355 355 
        ~~~~~~~~~~~~~~~~~~~~~~~~~
    356 
    -The control-flow optimiser sometimes leaves unreachable blocks behind
    357 
    -containing junk code.  These aren't necessarily a problem, but
    358 
    -removing them is good because it might save time in the native code
    359 
    -generator later.
    356 
    +Both the control-flow optimiser and the common block eliminator leave
    357 
    +unreachable blocks behind.  Several of the later passes drop them
    358 
    +incidentally, by rebuilding the graph from a reachability traversal,
    359 
    +but only removeUnreachableBlocksProc at the end of the pipeline
    360 
    +guarantees a graph without them.  Every pass in between must
    361 
    +therefore tolerate unreachable blocks in its input, and must not let
    362 
    +them affect the code generated for the reachable part.
    363 
    +
    364 
    +The latter requirement is easy to violate: callProcPoints collects
    365 
    +call continuations from the whole block map, so a label mentioned
    366 
    +only in unreachable code would become a proc point with an info table
    367 
    +but no stack map, and setInfoTableStackMap would panic (#27368).
    368 
    +The common block eliminator therefore ensures that the labels in its
    369 
    +unreachable leftovers coincide with labels of reachable code, see
    370 
    +Note [Resolving the CBE substitution] in GHC.Cmm.CommonBlockElim.
    360 371
    361 372 
     To make unreachable blocks visible in -ddump-cmm-* output, add -dppr-debug.
    362 373 
     -}

    • —
    View it on GitLab.
    You're receiving this email because of your account on gitlab.haskell.org. Manage all notifications · Help Notification message regarding https://gitlab.haskell.org/ghc/ghc/-/compare/a9cb1e12cfaee716f77c74e3e5bc81e7f7e84a3c...c61c4b5d72575e0ad052f5bca07c3bf1a1e70fa3 at 1786987885