Simon Jakobi pushed to branch wip/sjakobi/T27619-liveness-fixpoint-formats at Glasgow Haskell Compiler / GHC Commits: 58b29d3c by Simon Jakobi at 2026-08-16T15:32:54+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,52 @@ scalarWidth = \case formatInBytes :: Format -> Int formatInBytes = widthInBytes . formatToWidth +{- Note [Format order is width-major] +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +'Format' deliberately has no 'Ord' instance. A derived one would order by +constructor, and that reads like a width comparison without being one: +FF32 > II64, and VecFormat 16 FmtInt8 (16 bytes) > VecFormat 8 FmtDouble +(64 bytes). Code that needs "at least as wide" should compare 'formatToWidth' +results instead. + +'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,14 @@ newtype Regs = Regs { getRegs :: UniqSet RegWithFormat } maxRegWithFormat :: RegWithFormat -> RegWithFormat -> RegWithFormat maxRegWithFormat r1@(RegWithFormat _ fmt1) r2@(RegWithFormat _ fmt2) - = if fmt1 >= fmt2 + = if compareFormat fmt1 fmt2 /= LT then r1 else r2 - -- Re-using one of the arguments avoids allocating a new 'RegWithFormat', - -- compared with returning 'RegWithFormat r1 (max fmt1 fmt2)'. + -- 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 +70,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 +103,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 View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/commit/58b29d3c22d72c29cec399b069711312... -- View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/commit/58b29d3c22d72c29cec399b069711312... 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