GitLab

Simon Jakobi pushed to branch wip/sjakobi/T27619-liveness-fixpoint-formats at Glasgow Haskell Compiler / GHC

Commits:

e50eaaeb

by Simon Jakobi at 2026-08-16T15:43:20+02:00

NCG: compare register formats by width, remove Ord Format

maxRegWithFormat, minusCoveredRegs and shrinkingRegs compared formats
with Format's derived Ord, which orders by constructor, not by width:
FF32 > II64, and VecFormat 16 FmtInt8 (16 bytes) > VecFormat 8
FmtDouble (64 bytes). This is harmless while all vector vregs are
128-bit, but becomes unsound in the (FmtBwd2) direction of
Note [Register formats in liveness analysis] once wider vectors land
in the NCG. Noted in #27619.

The comparisons now go by formatToWidth, except the liveness join
maxRegWithFormat, which needs a total order to keep the liveness
fixpoint convergent and uses the new width-major compareFormat. See
Note [Format order is width-major] in GHC.CmmToAsm.Format.

Also remove the Ord instances of Format and ScalarFormat, so no future
call site can mistake the derived order for a width order. Their only
other user was a width test in GHC.CmmToAsm.PPC.CodeGen, now expressed
with formatToWidth.

Assisted-by: Claude Fable 5

4 changed files:

compiler/GHC/CmmToAsm/Format.hs
compiler/GHC/CmmToAsm/PPC/CodeGen.hs
compiler/GHC/CmmToAsm/Reg/Liveness.hs
compiler/GHC/CmmToAsm/Reg/Regs.hs

Changes:

compiler/GHC/CmmToAsm/Format.hs

@@ -23,6 +23,7 @@ module GHC.CmmToAsm.Format (
      vecFormat,
      isVecFormat,
      cmmTypeFormat,
 +    compareFormat,
      formatToWidth,
      scalarWidth,
      formatInBytes,
@@ -40,11 +41,13 @@ where
  import GHC.Prelude
 +import Data.Semigroup ( (<>) )
++
  import GHC.Cmm
  import GHC.Platform.Reg ( Reg(..), RealReg, VirtualReg )
  import GHC.Types.Unique ( Uniquable(..) )
  import GHC.Types.Unique.Set
 -import GHC.Utils.Outputable
 +import GHC.Utils.Outputable hiding ( (<>) )
  import GHC.Utils.Panic
  {- Note [GHC's data format representations]
@@ -92,7 +95,8 @@ data Format
          | FF64
          | VecFormat !Length       -- ^ number of elements (always at least 2)
                      !ScalarFormat -- ^ format of each element
 -        deriving (Show, Eq, Ord)
 +        deriving (Show, Eq)
 +        -- No Ord: see Note [Format order is width-major]
  pattern IntegerFormat :: Format
  pattern IntegerFormat <- ( isIntegerFormat -> True )
@@ -117,7 +121,7 @@ data ScalarFormat
    | FmtInt64
    | FmtFloat
    | FmtDouble
 -  deriving (Show, Eq, Ord)
 +  deriving (Show, Eq)
  scalarFormatFormat :: ScalarFormat -> Format
  scalarFormatFormat = \case
@@ -248,6 +252,50 @@ scalarWidth = \case
  formatInBytes :: Format -> Int
  formatInBytes = widthInBytes . formatToWidth
 +{- Note [Format order is width-major]
 +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 +'Format' has no 'Ord' instance: the only meaningful order on formats is by
 +width, and code that needs "at least as wide" should say so by comparing
 +'formatToWidth' results.
++
 +'compareFormat' exists for one caller: 'maxRegWithFormat' in
 +GHC.CmmToAsm.Reg.Regs, which joins the formats recorded for a register during
 +liveness analysis. That join must be a max in a *total* order. Width alone is
 +not total: distinct formats can share a width, e.g. VecFormat 2 FmtDouble and
 +VecFormat 4 FmtFloat. If the join broke such ties by argument order, two
 +blocks in a loop could swap same-width formats on every iteration of the
 +liveness fixpoint, and the fixpoint would never converge. See
 +Note [Convergence of the liveness fixpoint] in GHC.CmmToAsm.Reg.Liveness.
 +So 'compareFormat' refines width order with an arbitrary but fixed tiebreak.
 +-}
++
 +-- | Total order on formats: by width, with an arbitrary but fixed tiebreak
 +-- between distinct formats of the same width.
 +--
 +-- See Note [Format order is width-major].
 +compareFormat :: Format -> Format -> Ordering
 +compareFormat f1 f2 =
 +    compare (formatToWidth f1) (formatToWidth f2) <> compare (tag f1) (tag f2)
 +  where
 +    tag :: Format -> (Int, Length)
 +    tag = \case
 +      II8           -> (0, 0)
 +      II16          -> (1, 0)
 +      II32          -> (2, 0)
 +      II64          -> (3, 0)
 +      FF32          -> (4, 0)
 +      FF64          -> (5, 0)
 +      VecFormat l s -> (6 + scalarTag s, l)
++
 +    scalarTag :: ScalarFormat -> Int
 +    scalarTag = \case
 +      FmtInt8   -> 0
 +      FmtInt16  -> 1
 +      FmtInt32  -> 2
 +      FmtInt64  -> 3
 +      FmtFloat  -> 4
 +      FmtDouble -> 5
++
  --------------------------------------------------------------------------------
  -- | A typed virtual register: a virtual register, together with the specific

compiler/GHC/CmmToAsm/PPC/CodeGen.hs

@@ -484,7 +484,7 @@ getRegister' _ _ (CmmMachOp (MO_SS_Conv src tgt) [CmmLoad mem pk _])
    , src < tgt = do
        let format = cmmTypeFormat pk
        -- lwa is DS-form. See Note [Power instruction format]
 -      let form = if format >= II32 then DS else D
 +      let form = if formatToWidth format >= W32 then DS else D
        Amode addr addr_code <- getAmode form mem
        let code dst = assert (format == intFormat src)
                       $ addr_code `snocOL` LA format dst addr

compiler/GHC/CmmToAsm/Reg/Liveness.hs

@@ -939,7 +939,8 @@ test:
  The fixpoint terminates because the entries can only grow: registers are
  only added, formats only increase via 'maxRegWithFormat' joins, and both
 -lattices are finite.
 +lattices are finite. This needs the join to be a max in a total order on
 +formats. See Note [Format order is width-major] in GHC.CmmToAsm.Format.
  -}

compiler/GHC/CmmToAsm/Reg/Regs.hs

@@ -20,7 +20,8 @@ module GHC.CmmToAsm.Reg.Regs (
  import GHC.Prelude
  import GHC.Platform.Reg     ( Reg )
 -import GHC.CmmToAsm.Format  ( Format, RegWithFormat(..), isVecFormat )
 +import GHC.CmmToAsm.Format  ( Format, RegWithFormat(..), isVecFormat,
 +                              compareFormat, formatToWidth )
  import GHC.Utils.Outputable ( Outputable )
  import GHC.Types.Unique     ( Uniquable(..) )
@@ -39,11 +40,13 @@ newtype Regs = Regs { getRegs :: UniqSet RegWithFormat }
  maxRegWithFormat :: RegWithFormat -> RegWithFormat -> RegWithFormat
  maxRegWithFormat r1@(RegWithFormat _ fmt1) r2@(RegWithFormat _ fmt2)
 -  = if fmt1 >= fmt2
 -    then r1
 -    else r2
 -  -- Re-using one of the arguments avoids allocating a new 'RegWithFormat',
 -  -- compared with returning 'RegWithFormat r1 (max fmt1 fmt2)'.
 +  | LT <- compareFormat fmt1 fmt2 = r2
 +  | otherwise                     = r1
 +  -- The join must be a max in a total order ('compareFormat', not a width
 +  -- comparison), or the liveness fixpoint may not converge.
 +  -- See Note [Format order is width-major] in GHC.CmmToAsm.Format.
 +  --
 +  -- Re-using one of the arguments avoids allocating a new 'RegWithFormat'.
  noRegs :: Regs
  noRegs = Regs emptyUniqSet
@@ -66,7 +69,7 @@ minusCoveredRegs = coerce $ minusUniqSet_C f
    where
      f :: RegWithFormat -> RegWithFormat -> Maybe RegWithFormat
      f r1@(RegWithFormat _ fmt1) (RegWithFormat _ fmt2) =
 -      if fmt2 >= fmt1
 +      if formatToWidth fmt2 >= formatToWidth fmt1
             ||
           not ( isVecFormat fmt1 )
            -- See Wrinkle [Don't allow scalar partial writes]
@@ -99,7 +102,7 @@ shrinkingRegs = coerce $ minusUniqSet_C f
    where
      f :: RegWithFormat -> RegWithFormat -> Maybe RegWithFormat
      f (RegWithFormat _ fmt1) r2@(RegWithFormat _ fmt2)
 -      | fmt2 < fmt1
 +      | formatToWidth fmt2 < formatToWidth fmt1
        = Just r2
        | otherwise
        = Nothing