GitLab

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

Commits:

948293c5

by Simon Jakobi at 2026-08-27T18:24:53+02:00

Cmm: resolve substitution chains in common block elimination

The substitution built by elimCommonBlocks can map a label to another
eliminated label, but replaceLabels looks up each label only once.  An
edge in a losing copy of a merged block could thus be rewritten to an
eliminated label.  When that label was a call continuation,
callProcPoints turned it into a proc point, attachContInfoTables gave
it an info table, but stack layout produced no stack map for it, and
setInfoTableStackMap panicked.

Resolve the substitution before rewriting, so that every label in the
graph is mapped directly to its final representative.  See
Note [Resolving the CBE substitution] in GHC.Cmm.CommonBlockElim.

Also delete each merge's losing block in the pass itself, instead of
leaving it in the graph, unreachable, until stack layout drops it.
Deleting the losers is safe: replaceLabels rewrites every in-graph
reference to a loser -- branch targets, CmmLit CmmBlock literals,
CmmStackSlot Young slots, and g_entry -- to the end of its
substitution chain, and chain ends never lie in the substitution's
domain.  Note [Continuation BlockIds] in GHC.Cmm.Node bounds where
block ids can occur in expressions, so this list of references is
exhaustive for the graph itself.

The one reference replaceLabels does not rewrite, info_tbls, lies
outside the graph.  A proc's info table going stale when its entry
block loses a merge is a pre-existing bug, #27722, reachable only
from hand-written Cmm and unchanged by this patch.

The regression test distills the code shape that triggered the panic
when compiling GHC.CmmToAsm.Dwarf.Types with -O2 on top of !16168.

Also:
* copyTicks now copies each loser's ticks into its final
  representative instead of into a dead intermediate block.
* Rewrite Note [unreachable blocks] in GHC.Cmm.Pipeline to state the
  actual invariant: only removeUnreachableBlocksProc guarantees the
  removal of unreachable blocks, so every earlier pass must tolerate
  them.  Adapted from the doc changes in !16169.

Fixes #27368

Assisted-by: Claude Fable 5

6 changed files:

+ changelog.d/27368
compiler/GHC/Cmm/CommonBlockElim.hs
compiler/GHC/Cmm/ContFlowOpt.hs
compiler/GHC/Cmm/Pipeline.hs
+ testsuite/tests/codeGen/should_compile/T27368.hs
testsuite/tests/codeGen/should_compile/all.T

Changes:

changelog.d/27368

 +section: compiler
 +synopsis: Fix a ``setInfoTableStackMap`` panic caused by common block elimination
 +  leaving references to eliminated blocks.
 +issues: #27368
 +mrs: !16543

compiler/GHC/Cmm/CommonBlockElim.hs

@@ -58,18 +58,57 @@ import qualified Data.List.NonEmpty as NE
  -- hashes, and at most once otherwise. Previously, we were slower, and people
  -- rightfully complained: #10397
 +-- Note that this pass both consumes and produces graphs that may
 +-- contain unreachable blocks: the control-flow optimiser that runs
 +-- before it can orphan blocks without deleting them, and such orphans
 +-- pass through this pass untouched. (The losing copy of each merge,
 +-- by contrast, is deleted here; see deleteLosers.) See
 +-- Note [unreachable blocks] in GHC.Cmm.Pipeline.
++
  -- TODO: Use optimization fuel
  elimCommonBlocks :: CmmGraph -> CmmGraph
 -elimCommonBlocks g = replaceLabels env $ copyTicks env g
 +elimCommonBlocks g = replaceLabels env $ deleteLosers $ copyTicks env g
    where
 -     env = 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.
 +     -- Safe: replaceLabels is about to rewrite every in-graph reference
 +     -- to a loser to its surviving chain end.
 +     -- See Note [Resolving the CBE substitution].
 +     deleteLosers g'
 +       | mapNull env = g'
 +       | otherwise   = ofBlockMap (g_entry g')
 +                                  (toBlockMap g' `mapDifference` env)
 +     env = resolveSubst (iterate mapEmpty blocks_with_key)
 +     -- The order of blocks doesn't matter here, so we use toBlockList,
 +     -- which is faster than revPostorder.
       groups = groupByInt hash_block (toBlockList g) :: [[CmmBlock]]
       blocks_with_key = [ [ (successors b, [b]) | b <- bs] | bs <- groups]
 +{- Note [Resolving the CBE substitution]
 +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 +The substitution that `iterate` produces may contain chains
 +(k1 :-> k2, k2 :-> k3): the winner of one merge can lose a later one.
 +Its consumers, however, apply it non-transitively: replaceLabels
 +rewrites each label with a single map lookup, and copyTicks inverts
 +the substitution only one level deep. So before applying it we
 +resolve each entry to the end of its chain (resolveSubst, via
 +lookupBid, which does follow chains); the resolved substitution maps
 +every eliminated label directly to its final surviving
 +representative.
++
 +Applying the unresolved substitution instead would let replaceLabels
 +leave edges pointing at eliminated labels. Such edges can occur only
 +in blocks that themselves lost a merge, i.e. in unreachable code, but
 +even there they are harmful (#27368; analysed on the ticket). See
 +Note [unreachable blocks] in GHC.Cmm.Pipeline.
 +-}
++
 +-- | Resolve the substitution: follow chains (@k1 :-> k2@, @k2 :-> k3@)
 +-- to their ends, so that every eliminated label maps directly to its
 +-- final surviving representative.
 +--
 +-- See Note [Resolving the CBE substitution].
 +resolveSubst :: Subst -> Subst
 +resolveSubst env = mapMap (lookupBid env) env
++
  -- Invariant: The blocks in the list are pairwise distinct
  -- (so avoid comparing them again)
  type DistinctBlocks = [CmmBlock]

compiler/GHC/Cmm/ContFlowOpt.hs

@@ -44,7 +44,8 @@ import Control.Monad
  --
  -- In this situation we say that we shortcut L2 to L3. One of
  -- 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,9 @@ 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; shortcutting can in
 +-- turn leave blocks unreachable in the output, see
 +-- Note [unreachable blocks] in GHC.Cmm.Pipeline.
  --
  -- Transformations are improved by working from the end of the graph
  -- towards the beginning, because we may be able to perform many
@@ -341,8 +344,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,22 @@ 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, so every pass in that window may encounter
 +them.
++
 +Unreachable blocks are not entirely harmless, though.  Later passes do
 +not uniformly restrict themselves to reachable code -- callProcPoints,
 +for example, folds over the whole block map.  So every pass must keep
 +even unreachable code well-formed.  Violating this caused the panic in
 +#27368 (analysed on the ticket).  See
 +Note [Resolving the CBE substitution] in GHC.Cmm.CommonBlockElim.
++
  To make unreachable blocks visible in -ddump-cmm-* output, add -dppr-debug.
  -}

testsuite/tests/codeGen/should_compile/T27368.hs

 +-- The two branches share an identical suffix from the inner case
 +-- onwards, so common block elimination merges the duplicated call
 +-- blocks over several rounds, building a substitution chain. Without
 +-- resolving that chain, compiling this module at -O2 panicked in
 +-- setInfoTableStackMap (#27368). See
 +-- Note [Resolving the CBE substitution] in GHC.Cmm.CommonBlockElim.
++
 +module T27368 (f) where
++
 +{-# NOINLINE put #-}
 +put :: Int -> Int -> IO ()
 +put h x = if h + x == 12345 then errorWithoutStackTrace "boom" else pure ()
++
 +data T = J Int | K
++
 +f :: Int -> Bool -> T -> IO ()
 +f h a t = do
 +  if a
 +    then do put h 1; case t of { J _ -> put h 3; K -> put h 4 }; put h 0; put h 0
 +    else do put h 2; case t of { J _ -> put h 3; K -> put h 4 }; put h 0; put h 0
 +  put h 0

testsuite/tests/codeGen/should_compile/all.T

@@ -150,3 +150,5 @@ test('T16351', normal, compile, ['-O2 -ddump-simpl -dno-typeable-binds -dsuppres
  test('T20298a', normal, compile, ['-O2 -ddump-simpl -dno-typeable-binds -dsuppress-all -dsuppress-uniques'])
  test('T20298b', normal, compile, ['-O2 -dno-bignum-rules -ddump-simpl -dno-typeable-binds -dsuppress-all -dsuppress-uniques'])
  test('T20298c', normal, compile, ['-O2 -dno-builtin-rules -ddump-simpl -dno-typeable-binds -dsuppress-all -dsuppress-uniques'])
++
 +test('T27368', normal, compile, ['-O2'])