Simon Jakobi pushed to branch wip/sjakobi/T27368-cbe-compress at Glasgow Haskell Compiler / GHC Commits: 5a1c5f69 by Simon Jakobi at 2026-08-17T19:18:55+02:00 Sharpen Note [Resolving the CBE substitution] The Note claimed that CBE's input contains no unreachable blocks, but the control-flow optimiser can leave unreachable goto-only blocks behind (see the comment at incPreds/decPreds in GHC.Cmm.ContFlowOpt). Scope the reachability claim to the blocks the resolved substitution maps to, which is what the argument actually needs. Assisted-by: Claude Fable 5 - - - - - c61c4b5d by Simon Jakobi at 2026-08-17T19:29:24+02:00 Cmm: rewrite Note [unreachable blocks] The Note mentioned only the control-flow optimiser and framed unreachable blocks as a mere matter of code size. In fact common block elimination leaves them behind too, and #27368 showed how a pass can go wrong when they leak into the generated code. State the actual invariant: only removeUnreachableBlocksProc guarantees their removal, so every earlier pass must tolerate them. Also: * Turn elimCommonBlocks's intro comment into a haddock and document its unreachable-block behaviour there. * Drop the stale claim that ContFlowOpt had already removed unreachable blocks -- shortcutting creates new ones. Adapted from the doc changes in !16169. Assisted-by: Claude Fable 5 - - - - - 2 changed files: - compiler/GHC/Cmm/CommonBlockElim.hs - compiler/GHC/Cmm/Pipeline.hs Changes: ===================================== compiler/GHC/Cmm/CommonBlockElim.hs ===================================== @@ -30,34 +30,6 @@ import Control.Arrow (first, second) import Data.List.NonEmpty (NonEmpty (..)) import qualified Data.List.NonEmpty as NE --- ----------------------------------------------------------------------------- --- Eliminate common blocks - --- If two blocks are identical except for the label on the first node, --- then we can eliminate one of the blocks. To ensure that the semantics --- of the program are preserved, we have to rewrite each predecessor of the --- eliminated block to proceed with the block we keep. - --- The algorithm iterates over the blocks in the graph, --- checking whether it has seen another block that is equal modulo labels. --- If so, then it adds an entry in a map indicating that the new block --- is made redundant by the old block. --- Otherwise, it is added to the useful blocks. - --- To avoid comparing every block with every other block repeatedly, we group --- them by --- * a hash of the block, ignoring labels (explained below) --- * the list of outgoing labels --- The hash is invariant under relabeling, so we only ever compare within --- the same group of blocks. --- --- The list of outgoing labels is updated as we merge blocks (that is why they --- are not included in the hash, which we want to calculate only once). --- --- All in all, two blocks should never be compared if they have different --- hashes, and at most once otherwise. Previously, we were slower, and people --- rightfully complained: #10397 - {- Note [Resolving the CBE substitution] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 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. With the substitution resolved, every edge -- including those in the unreachable losing copies -- points at a surviving block, and every -surviving block is reachable: the input graph contains no unreachable -blocks (the control-flow optimiser runs first and drops them), and -merging only diverts paths from losers to their body-equal winners. -In particular the continuation of a call in a losing copy is also the +block the resolved substitution maps to is reachable: merging diverts +each loser's predecessors to its winner, so a winner inherits its +losers' reachability. (The input graph is not entirely free of +unreachable blocks -- the control-flow optimiser that runs first can +leave unreachable goto-only blocks behind -- but such blocks contain +no calls, and if one wins a merge it thereby becomes reachable.) In +particular the continuation of a call in a losing copy is also the continuation of its reachable winner, so stack layout has a stack map for it. @@ -90,17 +65,46 @@ Resolving also improves copyTicks: each loser's ticks are copied into its final representative instead of into a dead intermediate block. -} --- TODO: Use optimization fuel +-- | Merge identical blocks +-- +-- If two blocks are identical except for the label on the first node, +-- then we can eliminate one of the blocks. To ensure that the semantics +-- of the program are preserved, we have to rewrite each predecessor of the +-- eliminated block to proceed with the block we keep. +-- +-- Unreachable blocks may occur both in the input and in the output: +-- we process whatever the block map contains, and a merge leaves the +-- losing copy behind, unreachable. See Note [unreachable blocks] in +-- GHC.Cmm.Pipeline. +-- +-- The algorithm iterates over the blocks in the graph, +-- checking whether it has seen another block that is equal modulo labels. +-- If so, then it adds an entry in a map indicating that the new block +-- is made redundant by the old block. +-- Otherwise, it is added to the useful blocks. +-- +-- To avoid comparing every block with every other block repeatedly, we group +-- them by +-- * a hash of the block, ignoring labels (explained below) +-- * the list of outgoing labels +-- The hash is invariant under relabeling, so we only ever compare within +-- the same group of blocks. +-- +-- The list of outgoing labels is updated as we merge blocks (that is why they +-- are not included in the hash, which we want to calculate only once). +-- +-- All in all, two blocks should never be compared if they have different +-- hashes, and at most once otherwise. Previously, we were slower, and people +-- rightfully complained: #10397 elimCommonBlocks :: CmmGraph -> CmmGraph +-- TODO: Use optimization fuel elimCommonBlocks g = replaceLabels env' $ copyTicks env' g where -- See Note [Resolving the CBE substitution] env' = mapMap (lookupBid env) env 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. + -- Block order is irrelevant here, so we use toBlockList, which + -- is cheaper than revPostorder. groups = groupByInt hash_block (toBlockList g) :: [[CmmBlock]] blocks_with_key = [ [ (successors b, [b]) | b <- bs] | bs <- groups] ===================================== compiler/GHC/Cmm/Pipeline.hs ===================================== @@ -353,10 +353,21 @@ _GLOBAL_OFFSET_TABLE_, regardless of which entry point we arrived via. {- Note [unreachable blocks] ~~~~~~~~~~~~~~~~~~~~~~~~~ -The control-flow optimiser sometimes leaves unreachable blocks behind -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. +Both the control-flow optimiser and the common block eliminator leave +unreachable blocks behind. Several of the later passes drop them +incidentally, by rebuilding the graph from a reachability traversal, +but only removeUnreachableBlocksProc at the end of the pipeline +guarantees a graph without them. Every pass in between must +therefore tolerate unreachable blocks in its input, and must not let +them affect the code generated for the reachable part. + +The latter requirement is easy to violate: callProcPoints collects +call continuations from the whole block map, so a label mentioned +only in unreachable code would become a proc point with an info table +but no stack map, and setInfoTableStackMap would panic (#27368). +The common block eliminator therefore ensures that the labels in its +unreachable leftovers coincide with labels of reachable code, see +Note [Resolving the CBE substitution] in GHC.Cmm.CommonBlockElim. To make unreachable blocks visible in -ddump-cmm-* output, add -dppr-debug. -} View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/compare/a9cb1e12cfaee716f77c74e3e5bc81e... -- View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/compare/a9cb1e12cfaee716f77c74e3e5bc81e... You're receiving this email because of your account on gitlab.haskell.org. Manage all notifications: https://gitlab.haskell.org/-/profile/notifications | Help: https://gitlab.haskell.org/help