+section: compiler

+synopsis: Add :ghc-flag:`-dstable-core-dump-order`, a debugging flag that prints top-level Core bindings in a stable, source-location-based order that does not depend on uniques, making intermediate-compiler dumps (e.g. with :ghc-flag:`-ddump-simpl` or :ghc-flag:`-dverbose-core2core`) easier to diff. This affects only the compiler's intermediate output; it does not change generated code.

+issues: #27296

+mrs: !16143

+    -- See Note [Stable Core dump order] in GHC.Core.Ppr

+    binds' | sdocStableCoreDumpOrder (log_default_dump_context (logFlags logger))

+                        = sortCoreBindingsForDump binds

+           | otherwise  = binds

+

+                        then pprCoreBindingsWithSize binds'

+                        else pprCoreBindings         binds'

+        sortCoreBindingsForDump,

+import GHC.Core.Stats (CoreStats(..), exprStats)

+import GHC.Data.FastString (LexicalFastString(..), fastStringToShortByteString)

+import GHC.Types.Literal( Literal, pprLiteral )

+import GHC.Types.Name( getOccFS, getSrcSpan, pprInfixName, pprPrefixName )

+import GHC.Utils.Panic (panic)

+import GHC.Types.SrcLoc ( SrcSpan(..), pprUserRealSpan, srcSpanStartCol

+                        , srcSpanStartLine )

+import Data.List ( sortOn )

+import Data.Char ( ord )

+import qualified Data.ByteString.Short as SBS

+

+{- Note [Stable Core dump order]

+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

+The order of top-level bindings in a Core dump (-ddump-simpl etc.) is the

+compiler's internal processing order, which is sensitive to Uniques. Uniques

+can shift whenever an unrelated upstream module changes, so the bindings get

+re-ordered and a textual diff of two dumps fails to line up the real changes

+(#27296).

+

+With -dstable-core-dump-order we reorder the top-level bindings at dump time into

+a stable order. 'sortCoreBindingsForDump' sorts by a key that is *independent of

+Uniques*, so two dumps line up across rebuilds. The sort key is:

+

+  1. the binder's source span (real spans in source order; noSrcSpan last).

+     Workers and specialisations inherit their origin's source span (see

+     'mkWorkerId' and 'newSpecIdSM'), so they cluster next to the binding they

+     come from.

+  2. a "$-rank" so that within one source span the compiler-derived binders sort

+     *before* the origin they come from (e.g. @$wfoo@ before @foo@), mirroring

+     GHC's default dependency order (the wrapper calls the worker, so the worker

+     comes first; specialisations likewise precede their origin). We rank by

+     whether the OccName *contains* a '$', which marks a derived binder: a worker

+     is @$wfoo@, but a call-site specialisation is tidied to @bar_$sfoo@ (no

+     leading '$'), so a leading-'$' test would miss it.

+  3. the OccName string, as a lexical, deterministic tie-break.

+  4. a content-based tie-break on the right-hand side ('rhsKey'): the floated

+     literal, if any, then the RHS size statistics. This matters for the

+     anonymous floats: 'newLvlVar' builds them all with OccName "lvl" and

+     noSrcSpan, so keys 1-3 are identical and without it their order would fall

+     back to the Unique-driven input order -- the churn we set out to remove.

+     (Tidied dumps like -ddump-simpl give the floats distinct names lvl,

+     lvl1, ...; this additionally stabilises untidied dumps such as

+     -ddump-simpl-iterations.) It is only a best-effort tie-break -- RHSs

+     agreeing on both components keep their input order -- and Unique-independent

+     for the numeric CAFs we target (a rubbish literal is the exception: its

+     'cmpLit' falls back to the Unique-dependent 'nonDetCmpType').

+

+Recursive groups are never split: a 'Rec' is one 'CoreBind', placed as a unit by

+its earliest-source member, with its members sorted by the same key.

+

+Only *top-level* bindings (and the members of a top-level 'Rec') are reordered.

+Bindings nested inside a right-hand side (a 'let'/'letrec' within an expression)

+are left in their original order: their position in the dump is fixed by the

+surrounding expression rather than chosen by a Unique-keyed sort, so they don't

+suffer the cross-module churn this flag addresses.

+

+-dstable-core-dump-order is opt-in; the default order is retained because it is

+useful for debugging the compiler itself.

+-}

+

+-- | The sort key for one top-level binder. The trailing 'RhsKey' is a

+-- content-based tiebreak, used only when two binders agree on everything

+-- before it. See Note [Stable Core dump order].

+type DumpSortKey =

+  ( Int     -- source-span bucket: 0 = real span, 1 = noSrcSpan (sorts last)

+  , Int     -- source-span start line

+  , Int     -- source-span start column

+  , Int     -- dollar-rank: 0 = derived ($w/$s) binder, 1 = its origin

+  , LexicalFastString  -- the OccName, compared lexically

+  , RhsKey  -- content-based tiebreak (see 'rhsKey')

+  )

+

+-- | Reorder a 'CoreProgram' into a stable, source-location-driven order for

+-- dumping. See Note [Stable Core dump order]. Used by 'dumpPassResult' when

+-- -dstable-core-dump-order is enabled.

+sortCoreBindingsForDump :: CoreProgram -> CoreProgram

+sortCoreBindingsForDump = sortOn bindKey . map sortRecMembers

+  where

+    sortRecMembers (Rec prs) = Rec (sortOn (uncurry elemKey) prs)

+    sortRecMembers b         = b

+

+    -- 'sortRecMembers' runs first, so a 'Rec' is already sorted by 'elemKey'

+    -- when 'bindKey' sees it; its first member is therefore the minimum key.

+    bindKey :: CoreBind -> DumpSortKey

+    bindKey (NonRec b rhs)     = elemKey b rhs

+    bindKey (Rec ((b,rhs):_))  = elemKey b rhs

+    bindKey (Rec [])           = panic "sortCoreBindingsForDump: empty Rec"

+

+    elemKey :: CoreBndr -> CoreExpr -> DumpSortKey

+    elemKey b rhs = (bucket, line, col, dollar_rank, LexicalFastString nm, rhsKey rhs)

+      where

+        nm = getOccFS b

+        (bucket, line, col) = case getSrcSpan b of

+          RealSrcSpan rs _ -> (0, srcSpanStartLine rs, srcSpanStartCol rs)

+          _                -> (1, 0, 0)  -- noSrcSpan: sort last

+        -- A '$' anywhere in a tidied top-level OccName marks a compiler-derived

+        -- binder ($wfoo, but also call-site specialisations tidied to

+        -- bar_$sfoo); rank those before their origin within a shared source span,

+        -- mirroring GHC's default dependency order (the wrapper calls the worker,

+        -- so the worker comes first).

+        dollar_rank | dollarByte `SBS.elem` fastStringToShortByteString nm = 0

+                    | otherwise                                            = 1

+

+    dollarByte = fromIntegral (ord '$')

+

+-- | A content-based tie-break on a binder's right-hand side: see point 4 of

+-- Note [Stable Core dump order].

+type RhsKey =

+  ( Maybe Literal              -- the floated literal, if any (Nothing sorts first)

+  , (Int, Int, Int, Int, Int)  -- exprStats counts: terms, types, coercions, value binds, join binds

+  )

+

+rhsKey :: CoreExpr -> RhsKey

+rhsKey rhs = (litOf rhs, statsTuple (exprStats rhs))

+  where

+    statsTuple (CS tm ty co vb jb) = (tm, ty, co, vb, jb)

+    litOf (Lit l)    = Just l

+    litOf (App f a)  = case a of { Lit l -> Just l; _ -> litOf f }

+    litOf (Cast e _) = litOf e

+    litOf (Tick _ e) = litOf e

+    litOf _          = Nothing

+

+  , sdocStableCoreDumpOrder         = gopt Opt_StableCoreDumpOrder dflags

+   -- | Reorder top-level bindings in Core dumps into a stable, diffable order.

+   -- See Note [Stable Core dump order] in GHC.Core.Ppr.

+   | Opt_StableCoreDumpOrder

+

+  flagSpec "stable-core-dump-order"     Opt_StableCoreDumpOrder,

+  , sdocStableCoreDumpOrder         :: !Bool

+  , sdocStableCoreDumpOrder         = False

+.. ghc-flag:: -dstable-core-dump-order

+    :shortdesc: Reorder top-level bindings in Core dumps into a stable,

+        diffable order

+    :type: dynamic

+    :reverse: -dno-stable-core-dump-order

+    :category: verbosity

+

+    :since: 10.2.1

+

+    Normally the order of top-level bindings in a Core dump (such as the

+    output of :ghc-flag:`-ddump-simpl`) reflects the compiler's internal

+    processing order, which depends on ``Unique`` values. Those uniques can

+    shift whenever an unrelated upstream module changes, so the bindings get

+    re-ordered and a textual ``diff`` of two dumps fails to line up the real

+    changes.

+

+    This flag is opt-in and reorders the top-level bindings of Core dumps that

+    go through the pass-result printer (e.g. :ghc-flag:`-ddump-simpl`,

+    :ghc-flag:`-ddump-prep`, :ghc-flag:`-ddump-ds`,

+    :ghc-flag:`-ddump-simpl-iterations`) into a stable, source-location-driven

+    order that does not depend on uniques.

+

+    It is intended to be combined with :ghc-flag:`-dsuppress-uniques` when

+    diffing two dumps, but because the ordering does not depend on uniques the

+    output is also more diffable without it.

+

+

+# Check -dstable-core-dump-order on a small Data.Map-style module. The

+# sed allow-list prints, deduplicated, the top-level binders we care about in

+# dump order. It inspects names only, so it is insensitive to unrelated

+# Core-format churn.

+#

+# The allow-list covers one binder of each interesting category, so the test

+# exercises the clustering of generated binders next to their origin:

+#   * derived instances ($fEqKey/$fOrdKey/$fOrdKey_$ccompare),

+#   * a call-site specialisation (findI_$slookupG, from lookupG's SPECIALISE), and

+#   * a recursive worker ($wrotate).

+T27296:

+	$(RM) -f T27296.o T27296.hi

+	'$(TEST_HC)' $(TEST_HC_OPTS) -O -c -ddump-simpl -dsuppress-uniques \

+	    -dsuppress-idinfo -dsuppress-module-prefixes -dno-typeable-binds \

+	    -dstable-core-dump-order T27296.hs 2> /dev/null \

+	    | sed -nE 's/^(\$$fEqKey|\$$fOrdKey|\$$fOrdKey_\$$ccompare|size|findI_\$$slookupG|lookupG|member|findI|\$$wrotate|rotate|insertG|insertManyI|insertTwoI|weight|balance|ratios|fromAscI)( .*)?$$/\1/p' \

+	    | uniq

+

+# See T27296b.hs for what this pins and why. The six floated "lvl" constants

+# are scrambled in source order; grep them out and the dump coming out

+# 1000..6000 confirms the stable, value-ordered float ordering.

+T27296b:

+	$(RM) -f T27296b.o T27296b.hi

+	'$(TEST_HC)' $(TEST_HC_OPTS) -O -c -ddump-float-out -dsuppress-uniques \

+	    -dsuppress-idinfo -dsuppress-module-prefixes -dno-typeable-binds \

+	    -dstable-core-dump-order T27296b.hs 2> /dev/null \

+	    | grep '^lvl = I#'

+{-# LANGUAGE BangPatterns #-}

+

+-- See Note [Stable Core dump order] in GHC.Core.Ppr.

+--

+-- A small Data.Map-style module exercising the trickier parts of the stable

+-- dump ordering. Under -O it produces, alongside the user functions:

+--   * derived Eq/Ord instances for a custom Key type ($fEqKey/$fOrdKey/...),

+--   * a call-site specialisation of lookupG (findI_$slookupG), and

+--   * a worker/wrapper split of the recursive, strict rotate ($wrotate).

+-- Each generated binder inherits its origin's source span, so the stable order

+-- clusters it next to that origin. The source order is deliberately neither

+-- alphabetical nor the default dump order (insertG forward-references balance),

+-- so the test pins source-position ordering specifically.

+module T27296

+  ( Key(..), size, lookupG, member, findI, rotate, insertG, insertManyI

+  , insertTwoI, weight, balance, ratios, fromAscI )

+  where

+

+-- A custom key with a derived Ord instance: the derived $fEqKey/$fOrdKey

+-- binders inherit this declaration's source span, so they cluster here.

+data Key = Key Int deriving (Eq, Ord)

+

+data Map k a = Tip | Bin !Int k a !(Map k a) !(Map k a)

+

+data Sizes = Sizes !Int !Int

+

+size :: Map k a -> Int

+size Tip              = 0

+size (Bin sz _ _ _ _) = sz

+

+lookupG :: Ord k => k -> Map k a -> Maybe a

+lookupG _ Tip = Nothing

+lookupG k (Bin _ kx x l r) = case compare k kx of

+  LT -> lookupG k l

+  GT -> lookupG k r

+  EQ -> Just x

+{-# SPECIALISE lookupG :: Key -> Map Key a -> Maybe a #-}

+

+member :: Key -> Map Key a -> Bool

+member k m = case lookupG k m of

+  Nothing -> False

+  Just _  -> True

+

+findI :: Key -> Map Key a -> a -> a

+findI k m def = case lookupG k m of

+  Nothing -> def

+  Just v  -> v

+

+-- rotate is recursive and strict in the product 'Sizes', so worker/wrapper

+-- unboxes it into a recursive worker ($wrotate). The loop only repackages the

+-- fields (no arithmetic), so the worker is stable across build flavours.

+rotate :: Sizes -> [a] -> Sizes

+rotate s []               = s

+rotate (Sizes a b) (_:xs) = rotate (Sizes b a) xs

+

+-- insertG references 'balance', which is defined further down (forward ref).

+insertG :: Ord k => k -> a -> Map k a -> Map k a

+insertG k x Tip = Bin 1 k x Tip Tip

+insertG k x (Bin sz kx kv l r) = case compare k kx of

+  LT -> balance kx kv (insertG k x l) r

+  GT -> balance kx kv l (insertG k x r)

+  EQ -> Bin sz k x l r

+{-# SPECIALISE insertG :: Key -> a -> Map Key a -> Map Key a #-}

+

+insertManyI :: [(Key, a)] -> Map Key a -> Map Key a

+insertManyI xs m0 = foldr (\(k, x) m -> insertG k x m) m0 xs

+

+insertTwoI :: Key -> Key -> a -> Map Key a

+insertTwoI k1 k2 x = insertG k1 x (insertG k2 x Tip)

+

+-- weight unboxes the strict fields of Sizes -> worker/wrapper $wweight.

+weight :: Sizes -> Int

+weight (Sizes a b) = a * a + 3 * b * b + a * b + 1

+

+balance :: k -> a -> Map k a -> Map k a -> Map k a

+balance k x l r = Bin (weight (Sizes sl sr)) k x l r

+  where

+    sl = size l

+    sr = size r

+

+-- baseRatios is a closed constant under a lambda -> floated to a top-level lvl.

+ratios :: Int -> [Int]

+ratios n = map (n +) baseRatios

+  where baseRatios = [2, 3, 5, 7, 11, 13]

+

+fromAscI :: [(Key, a)] -> Map Key a

+fromAscI = foldr (\(k, x) m -> insertG k x m) Tip

+$fEqKey

+$fOrdKey

+$fOrdKey_$ccompare

+size

+findI_$slookupG

+lookupG

+member

+findI

+$wrotate

+rotate

+insertG

+insertManyI

+insertTwoI

+weight

+balance

+ratios

+fromAscI

+-- See Note [Stable Core dump order] in GHC.Core.Ppr.

+--

+-- Companion to T27296 that pins the ordering of *anonymous* top-level floats.

+-- Under -O the boxed Int constants in sel's branches are floated to top level

+-- as separate CAFs, all of which the compiler names "lvl" with noSrcSpan (see

+-- newLvlVar). Before -dstable-core-dump-order their dump order was the

+-- unique-driven processing order; the flag's content-based tie-break (rhsKey)

+-- now orders them by literal value -- here 1000..6000, despite the scrambled

+-- source order. This dump is intentionally *untidied* (-ddump-float-out), the

+-- only place the "lvl" collision is observable; tidied dumps like -ddump-simpl

+-- already give the floats distinct names (lvl, lvl1, ...).

+module T27296b (sel) where

+

+{-# NOINLINE sel #-}

+sel :: Int -> Int

+sel 0 = 5000

+sel 1 = 1000

+sel 2 = 4000

+sel 3 = 2000

+sel 4 = 3000

+sel _ = 6000

+lvl = I# 1000#

+lvl = I# 2000#

+lvl = I# 3000#

+lvl = I# 4000#

+lvl = I# 5000#

+lvl = I# 6000#

+test('T27296', [], makefile_test, ['T27296'])

+test('T27296b', [], makefile_test, ['T27296b'])