GitLab

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

 +{-# 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'])