Simon Jakobi pushed to branch wip/sjakobi/T27619-liveness-fixpoint-formats at Glasgow Haskell Compiler / GHC Commits: 6adeca12 by Simon Jakobi at 2026-08-16T00:25:54+02:00 NCG: iterate the liveness fixpoint until register formats converge The convergence test of the per-SCC liveness fixpoint in GHC.CmmToAsm.Reg.Liveness compared BlockMap Regs values with the key-only Eq of UniqSet, which ignores the Format attached to each register. Formats grow across iterations (one control-flow edge per iteration), so the fixpoint could stop while formats were still growing, recording a vector register live at a too-narrow format and handing the register allocator an under-sized spill/reload width — the silent-corruption class of #26411. The test also compared the entire accumulated block map on every iteration, although only the current SCC's entries can change, making it quadratic in procedure size and a dominant cost on control-flow-heavy code. Compare only the SCC's own entries, using the new format-aware equalRegs. See the new Note [Convergence of the liveness fixpoint]. Also remove the Eq instance of Regs: inherited from UniqSet, it compared the register uniques only, silently ignoring the formats — the mistake behind #27619 — and the convergence test was its sole user. The instance on UniqSet itself deserves the same scrutiny, but that is a compiler-wide audit left for separate work. Fixes #27619. Fixes #27437. Assisted-by: Claude Fable 5 - - - - - 5 changed files: - compiler/GHC/CmmToAsm/Reg/Liveness.hs - compiler/GHC/CmmToAsm/Reg/Regs.hs - compiler/GHC/Types/Unique/FM.hs - + testsuite/tests/regalloc/T27619.hs - testsuite/tests/regalloc/all.T Changes: ===================================== compiler/GHC/CmmToAsm/Reg/Liveness.hs ===================================== @@ -879,7 +879,7 @@ computeLiveness platform sccs , ppr sccs']) livenessSCCs - :: Instruction instr + :: forall instr. Instruction instr => Platform -> BlockMap Regs -> [SCC (LiveBasicBlock instr)] -- accum @@ -897,36 +897,49 @@ livenessSCCs platform blockmap done (AcyclicSCC block : sccs) livenessSCCs platform blockmap done (CyclicSCC blocks : sccs) = livenessSCCs platform blockmap' (CyclicSCC blocks':done) sccs - where (blockmap', blocks') - = iterateUntilUnchanged linearLiveness equalBlockMaps - blockmap blocks + where (blockmap', blocks') = fixpoint blockmap - iterateUntilUnchanged - :: (a -> b -> (a,c)) -> (a -> a -> Bool) - -> a -> b - -> (a,c) - - iterateUntilUnchanged f eq aa b = go aa + -- See Note [Convergence of the liveness fixpoint] + fixpoint :: BlockMap Regs -> (BlockMap Regs, [LiveBasicBlock instr]) + fixpoint bm + | all unchanged blocks = (bm', blocks'') + | otherwise = fixpoint bm' where - go a = if eq a a' then ac else go a' - where - ac@(a', _) = f a b - - linearLiveness - :: Instruction instr - => BlockMap Regs -> [LiveBasicBlock instr] - -> (BlockMap Regs, [LiveBasicBlock instr]) - - linearLiveness = mapAccumL (livenessBlock platform) - - -- probably the least efficient way to compare two - -- BlockMaps for equality. - equalBlockMaps :: BlockMap Regs -> BlockMap Regs -> Bool - equalBlockMaps a b - = a' == b' - where a' = mapToList a - b' = mapToList b - -- See Note [Unique Determinism and code generation] + (bm', blocks'') = mapAccumL (livenessBlock platform) bm blocks + + unchanged :: LiveBasicBlock instr -> Bool + unchanged block = + case (mapLookup bid bm, mapLookup bid bm') of + (Just old, Just new) -> old `equalRegs` new + (Nothing, _ ) -> False -- first iteration + (Just _, Nothing ) -> False -- cannot happen + where bid = blockId block + +{- Note [Convergence of the liveness fixpoint] +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +For a cyclic SCC, we iterate 'livenessBlock' over the SCC's blocks until the +recorded entry liveness stops changing. Two subtleties in the convergence +test: + +* It must compare register formats, not just the sets of live registers + (hence the format-aware 'equalRegs'). A block's + live-in set joins the successors' entries with 'unionRegsMaxFmt', so a wide + format needs one iteration per control-flow edge to propagate backwards + around a loop, while the register *sets* are typically already complete + after the first iteration. Stopping when the sets stabilise can record a + register at a format narrower than the reads it flows into, violating + (FmtBwd1) of Note [Register formats in liveness analysis] — which the + register allocator relies on for spill/reload widths (#27619). + +* Only the entries of the SCC's own blocks can change between iterations: + 'livenessBlock' inserts only the block it processes, and successor SCCs are + already final since SCCs are processed in reverse dependency order. + Comparing the whole accumulated block map made the fixpoint quadratic in + procedure size (#27437). + +Termination: entries only grow — registers are only added, and formats only +increase via 'maxRegWithFormat' joins — and both lattices are finite. +-} ===================================== compiler/GHC/CmmToAsm/Reg/Regs.hs ===================================== @@ -13,6 +13,7 @@ module GHC.CmmToAsm.Reg.Regs ( shrinkingRegs, mapRegs, elemRegs, lookupReg, + equalRegs, ) where @@ -23,6 +24,7 @@ import GHC.CmmToAsm.Format ( Format, RegWithFormat(..), isVecFormat ) import GHC.Utils.Outputable ( Outputable ) import GHC.Types.Unique ( Uniquable(..) ) +import GHC.Types.Unique.FM ( equalUFMBy ) import GHC.Types.Unique.Set import Data.Coerce ( coerce ) @@ -33,7 +35,7 @@ import Data.Coerce ( coerce ) -- register liveness analysis. See Note [Register formats in liveness analysis] -- in GHC.CmmToAsm.Reg.Liveness. newtype Regs = Regs { getRegs :: UniqSet RegWithFormat } - deriving newtype (Eq, Outputable) + deriving newtype (Outputable) maxRegWithFormat :: RegWithFormat -> RegWithFormat -> RegWithFormat maxRegWithFormat r1@(RegWithFormat _ fmt1) r2@(RegWithFormat _ fmt2) @@ -117,3 +119,10 @@ elemRegs r (Regs live) = elemUniqSet_Directly (getUnique r) live lookupReg :: Reg -> Regs -> Maybe Format lookupReg r (Regs live) = regWithFormat_format <$> lookupUniqSet_Directly live (getUnique r) + +-- | Do the two sets contain the same registers, at the same formats? +equalRegs :: Regs -> Regs -> Bool +equalRegs (Regs a) (Regs b) = equalUFMBy sameFormat (getUniqSet a) (getUniqSet b) + where + -- Registers with equal uniques are equal, so only compare the formats. + sameFormat (RegWithFormat _ fmt1) (RegWithFormat _ fmt2) = fmt1 == fmt2 ===================================== compiler/GHC/Types/Unique/FM.hs ===================================== @@ -67,6 +67,7 @@ module GHC.Types.Unique.FM ( strictIntersectUFM_C, disjointUFM, equalKeysUFM, + equalUFMBy, diffUFM, nonDetStrictFoldUFM, nonDetFoldUFM, nonDetStrictFoldUFM_DirectlyM, nonDetFoldWithKeyUFM, @@ -590,7 +591,12 @@ unsafeCastUFMKey (UFM m) = UFM m -- Determines whether two 'UniqFM's contain the same keys. equalKeysUFM :: UniqFM key a -> UniqFM key b -> Bool -equalKeysUFM (UFM m1) (UFM m2) = liftEq (\_ _ -> True) m1 m2 +equalKeysUFM = equalUFMBy (\_ _ -> True) + +-- | Determines whether two 'UniqFM's contain the same keys, with values +-- that agree according to the given predicate. +equalUFMBy :: (a -> b -> Bool) -> UniqFM key a -> UniqFM key b -> Bool +equalUFMBy eq (UFM m1) (UFM m2) = liftEq eq m1 m2 -- | An edit on type @a@, relating an element of a container (like an entry in a -- map or a line in a file) before and after. ===================================== testsuite/tests/regalloc/T27619.hs ===================================== @@ -0,0 +1,31 @@ +{-# LANGUAGE MagicHash, UnboxedTuples #-} + +-- The native code for this loop is a three-block cycle H -> X -> W -> H: +-- +-- H (loop head): reads v at FF64 (movsd lane-0 extract for the guard) +-- X: reads v at FF64 (another movsd lane-0 extract) +-- W: reads v at F64x2 (movhlps from the full unpack) +-- +-- v is loop-invariant, so its live format on entry to every block in the +-- cycle must be F64x2. -fno-cse only keeps the two syntactically identical +-- lane-0 extracts from being merged. +-- +-- The test greps -ddump-asm-liveness for a 128-bit vector register recorded +-- at FF64, which the too-early convergence of the liveness fixpoint produced. +module T27619 where + +import GHC.Exts + +loop :: Int# -> DoubleX2# -> Double# -> Double# +loop i v acc = + case unpackDoubleX2# v of + (# a1, _ #) -> + if isTrue# (a1 <## int2Double# i) + then acc + else case unpackDoubleX2# v of + (# a2, _ #) -> + if isTrue# (a2 *## 2.0## <## int2Double# i) + then acc *## 2.0## + else case unpackDoubleX2# v of + (# x, y #) -> loop (i -# 1#) v (acc +## (x *## y)) +{-# NOINLINE loop #-} ===================================== testsuite/tests/regalloc/all.T ===================================== @@ -6,3 +6,14 @@ test('regalloc_unit_tests', [ignore_stderr, only_ways(['normal'])], extra_run_opts('"' + config.libdir + '"') ], compile_and_run, ['-package ghc']) + +# The liveness fixpoint must iterate until the register formats converge, not +# just the sets of live registers (#27619). A vector register live at +# VecFormat 2 FmtDouble around the loop must not be recorded at FF64. +test('T27619', + [ unless(arch('x86_64'), skip), + when(not have_ncg(), skip), + only_ways(['normal']), + grep_errmsg(r'%vV128_\S+ :: FF64') ], + compile, + ['-O -fno-cse -ddump-asm-liveness']) View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/commit/6adeca12421e4444e261268251892ac9... -- View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/commit/6adeca12421e4444e261268251892ac9... 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