GitLab

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

Commits:

a0539f8e

by Simon Jakobi at 2026-09-01T09:46:06+02:00

Cmm: delete losing blocks in common block elimination

Delete each merge's losing block in the pass itself, instead of
leaving it in the graph, unreachable, until stack layout drops it.

This is safe: replaceLabels rewrites every in-graph reference to a loser
to the end of its substitution chain, and chain ends never lie in the
substitution's domain.  The one reference replaceLabels does not rewrite,
info_tbls, holds only the entry block's info table at this stage, and the
entry block never loses a merge -- see
Note [Retain entry block during common block elimination.]

Also rewrite Note [unreachable blocks] in GHC.Cmm.Pipeline to state
who actually removes unreachable blocks and when, and point at it from
GHC.Cmm.ContFlowOpt.

Assisted-by: Claude Fable 5

3 changed files:

compiler/GHC/Cmm/CommonBlockElim.hs
compiler/GHC/Cmm/ContFlowOpt.hs
compiler/GHC/Cmm/Pipeline.hs

Changes:

compiler/GHC/Cmm/CommonBlockElim.hs

@@ -59,18 +59,25 @@ import qualified Data.List.NonEmpty as NE
  -- hashes, and at most once otherwise. Previously, we were slower, and people
  -- rightfully complained: #10397
 +-- The input graph may contain unreachable blocks (see
 +-- Note [unreachable blocks] in GHC.Cmm.Pipeline). They take part in
 +-- deduplication like any other block, and stay in the graph unless
 +-- eliminated by a merge (deleteLosers removes those).
++
  -- TODO: Use optimization fuel
  elimCommonBlocks :: CmmGraph -> CmmGraph
  elimCommonBlocks g =
      assert (g_entry g == g_entry g') g'
    where
 -     g' = replaceLabels env $ copyTicks env g
 +     g' = replaceLabels env $ deleteLosers $ copyTicks env g
 +     deleteLosers g0
 +       | mapNull env = g0
 +       | otherwise   = ofBlockMap (g_entry g0)
 +                                  (toBlockMap g0 `mapDifference` env)
       env = resolveSubst (iterate mapEmpty blocks_with_key)
 -     -- The order of blocks doesn't matter here. While we could use
 -     -- revPostorder which drops unreachable blocks this is done in
 -     -- ContFlowOpt already which runs before this pass. So we use
 -     -- toBlockList since it is faster.
 -     -- One exception: The entry block most come first or we risk eliminating it
 +     -- The order of blocks doesn't matter here, so we use toBlockList,
 +     -- which is faster than revPostorder.
 +     -- One exception: The entry block must come first or we risk eliminating it
       -- in favour of another block. See Note [Retain entry block during common block elimination.]
       groups = groupByInt hash_block (toBlockListEntryFirst g) :: [[CmmBlock]]
       blocks_with_key = [ [ (successors b, [b]) | b <- bs] | bs <- groups]

compiler/GHC/Cmm/ContFlowOpt.hs

@@ -42,9 +42,10 @@ import Control.Monad
  -- L2: goto L3;
  -- L3: ...
  --
 --- In this situation we say that we shortcut L2 to L3. One of
 +-- In this situation we say that we shortcut L2 to L3. One of the
  -- consequences of shortcutting is that some blocks of code may become
 --- unreachable (in the example above this is true for L2).
 +-- unreachable (in the example above this is true for L2). See
 +-- Note [unreachable blocks] in GHC.Cmm.Pipeline.
  -- Note [Control-flow optimisations]
@@ -66,7 +67,7 @@ import Control.Monad
  --
  -- Blocks are processed using postorder DFS traversal. A side effect
  -- of determining traversal order with a graph search is elimination
 --- of any blocks that are unreachable.
 +-- of any blocks that are unreachable in the input.
  --
  -- Transformations are improved by working from the end of the graph
  -- towards the beginning, because we may be able to perform many
@@ -341,8 +342,7 @@ blockConcat splitting_procs g@CmmGraph { g_entry = entry_id }
  -- Invariant: if a block has no predecessors it should be dropped from the
  -- graph because it is unreachable. maybe_concat is constructed to maintain
  -- that invariant, but calling replaceLabels may introduce unreachable blocks.
 --- We rely on subsequent passes in the Cmm pipeline to remove unreachable
 --- blocks.
 +-- See Note [unreachable blocks] in GHC.Cmm.Pipeline.
  incPreds, decPreds :: BlockId -> LabelMap Int -> LabelMap Int
  incPreds bid edges = mapInsertWith (+) bid 1 edges
  decPreds bid edges = case mapLookup bid edges of

compiler/GHC/Cmm/Pipeline.hs

@@ -358,6 +358,20 @@ containing junk code.  These aren't necessarily a problem, but
  removing them is good because it might save time in the native code
  generator later.
 +Who removes them, and when?  Any pass that rebuilds the graph from
 +revPostorder drops them as a side effect.  Normally the first pass to
 +do so is stack layout.  In addition, removeUnreachableBlocksProc at the
 +very end of cpsTop removes the blocks that the second round of
 +control-flow optimisation orphans, and prunes their info tables.  No
 +pass between the first control-flow optimisation and stack layout
 +removes unreachable blocks (common block elimination deletes the losing
 +blocks of its merges, but leaves other unreachable code alone), so every
 +pass in that window may encounter them.
++
 +Note that unreachable blocks are not entirely harmless, though: some later
 +passes read them. callProcPoints, for example, folds over the whole block map,
 +so a stale edge in an unreachable block caused the panic in #27368.
++
  To make unreachable blocks visible in -ddump-cmm-* output, add -dppr-debug.
  -}