Mikolaj Konarski pushed to branch wip/T27981-ncg-mystery-box at Glasgow Haskell Compiler / GHC

Commits:

• 3fa8a3a8
  by Mikolaj Konarski at 2026-10-30T23:42:10+01:00

  rts: run finalizers soon after the GC that finds them
  
  scheduleFinalizers puts the finalizer thread at the end of the run
  queue, and the thread whose heap overflow caused the GC goes back to
  its front unless a context switch is pending.  So under the RTS timer
  the finalizers wait for the next context switch, 20 ms by default, and
  whatever they would free stays live until then: a program that opens
  and closes handles fast keeps every closed handle's buffers.  nofib's
  maillist, which appends to its output a line at a time, peaks at 18 MB
  of residency where -V0 and -C0, whose scheduler switches whenever
  another thread is runnable, keep 1.65 MB.
  
  Request a context switch when scheduling the finalizers, so that they
  run at the next block boundary.  maillist then keeps 1.65 MB
  under the default timer and runs 13% fewer instructions; across nofib,
  cacheprof runs 1.3% more and gg built at -O0 0.3% more, as each does
  under -V0, and no other program moves by 0.2% beyond its run-to-run
  noise.
  
  Fixes #28060.
  
  Assisted-by: Claude Opus 5.5
  

• 14be43ab
  by Mikolaj Konarski at 2026-10-30T23:42:10+01:00

  Hand calcFreqs a procedure's loops inner first
  
  calcFreqs estimates block frequencies by Wu and Larus's algorithm, which
  takes the loops from inner to outer, as its comment says: an enclosing
  loop's frequencies use the cycle probability of each loop inside it,
  computed when that loop is processed. mkGlobalWeights handed
  it the loops in loopInfo's order, by back edge in the order of the CFG's
  labels, so an enclosing loop could come first. calcFreqs then took
  the probability of an inner loop's back edge itself, often 1.0,
  for that loop's cycle probability, which calcFreqs caps at 1 - 1/512,
  so the inner loop's head counted up to 512 times as often as
  it was entered. The cycle a heap check makes through the garbage
  collector is such an inner loop in any loop that allocates:
  in containers' map benchmarks, the head of the loop that looks keys up
  was estimated to run 384 times a call, while the frequencies
  of the edges into it summed to 101. mkGlobalWeights now sorts the loops
  by the size of their bodies, an inner loop's body being a proper subset
  of an enclosing one's.
  
  Measured against the parent commit, in instructions; calcFreqs changes
  the generated code only under -fcmm-static-pred, on at -O1 and -O2.
  At -O2 nofib's programs take 0.02% more (queens 0.5%, parstof 0.2%),
  containers' benchmarks 0.09% more (lookupge-map's GE Twan far and map
  lookup absent 2.6%) and megaparsec's 0.18% more (skipMany 2.2%, sepEndBy
  1.4%); vector's benchmarks and fannkuch-redux move by no more than their
  noise. These rises come from block layout, which places a procedure's
  blocks by these frequencies: by them a loop counts as entered about
  once, so its entry can outweigh its back edge and fall through
  into its head, every iteration then paying a jump back. A later commit,
  which lets a back edge outrank its loop's entry, takes back all
  of nofib's rises and most of containers' and megaparsec's,
  and the commits after it the rest. No benchmark's allocation changes
  beyond nofib's run-to-run noise. The compiler's allocation compiling
  perf/compiler's T3294, T12707, T783 and T9961 moves by less than 0.1%.
  
  Assisted-by: Claude Opus 5.5
  

• 3500e635
  by Mikolaj Konarski at 2026-10-30T23:42:10+01:00

  Find a CFG's back edges by one depth-first search
  
  findBackEdges classified every edge of the CFG (classifyEdges, which
  timestamps the visits of a depth-first search from the entry) to find
  the few that lead back to a block on the search's path. optHsPatterns
  calls it on every procedure, at every optimisation level, to give back
  edges their bonus. findBackEdges is now that depth-first search itself:
  it visits the successors in the same order and collects, as it goes,
  the edges into a block still on its stack, leaving out an edge
  from a block to itself, which classifyEdges calls a self loop rather
  than a back edge. classifyEdges and its EdgeType,
  in GHC.Data.Graph.Directed, had no other user and are gone.
  
  The generated code is the same: the assembly of perf/compiler's T3294,
  T12707, T783 and T9961 at -O0 and -O, and the object code of nofib's
  programs at -O2, are the parent's. The compiler allocates 0.2% less
  compiling T3294 at -O0, 0.7% less compiling T12707, 1.0% less compiling
  T783 and 1.0% less compiling T9961; at -O, 0.3% less compiling T12707
  and 0.2% less compiling T783; and compiling nofib's programs at -O2,
  0.20% less in geometric mean and up to 0.36% less (real/compress2).
  Compiling !16269's ManyBasicBlocks at -O1 and -O2, the compiler
  allocates 0.2% less.
  
  Assisted-by: Claude Opus 5.5
  

• 9f046ee0
  by Mikolaj Konarski at 2026-10-30T23:42:10+01:00

  Count self loops as loops in static branch prediction
  
  loopInfo took an edge for a back edge where its target dominates
  its source, by mkDomMap's sets, which hold a block's own label only
  where the block is a leaf of the dominator tree. So a self loop counted
  as a back edge only from a leaf, and the retry of an atomic operation
  that x86 emulates with a compare-and-swap loop (cmpxchg_code), whose
  block dominates the block after it, counted as none: calcFreqs then took
  that block for irreducible and gave frequency 0 to it, to every block
  it dominates and to their edges, a surrounding loop's back edge among
  them. mkDomMap's sets now hold each block's own label but the root's,
  so that a self loop counts as a back edge but at the root, which no edge
  enters as a back edge.
  
  The retry edge cmpxchg_code adds now has a TransitionSource of its own,
  AsmCodeGenRetry, which staticBranchPrediction leaves out of its rule
  that a back edge is more likely than any other edge, so that the retry
  is predicted to be rare rather than to repeat seven times in eight. Note
  [Static Branch Prediction] says so. Andreas Klebinger's !16535 overlaps
  with this commit at that edge: it builds that loop's edges
  by continueInNewBlock and addColdSelfLoop, and the two changes conflict
  there.
  
  Measured against the parent commit, on x86-64: the assembly
  of perf/compiler's T3294, T12707, T783 and T9961 at -O0 and -O
  is the same, and so are the objects of nofib's programs at -O2;
  of containers' objects only graph-benchmarks' Main changes,
  and no benchmark of containers, vector or megaparsec moves beyond
  its noise. mkDomMap's go is now one equation, and at -O the compiler
  allocates 1.9% less compiling perf/compiler's T783, 0.1% less compiling
  T12707 and 0.08% less compiling T3294; at -O0, where static prediction
  is off, its allocation does not change. Compiling !16269's
  ManyBasicBlocks at -O1 and -O2, the compiler allocates 10.7% less.
  
  Assisted-by: Claude Opus 5.5
  

• 5f5f36ec
  by Mikolaj Konarski at 2026-10-30T23:42:10+01:00

  Let a loop's back edge outrank its entry in block layout
  
  sequenceChain lays the blocks out by fusing chains along the heaviest
  edges first, by the final edge weights. Under -fcmm-static-pred,
  on at -O1 and -O2, those are the frequencies static prediction
  estimates, which can rate a loop's back edge below its entry: where
  the branch that decides whether the loop goes on has no back edge among
  its targets, the other heuristics predict it, and they can predict
  staying in the loop to be unlikely, as in a lookup down a tree (Note
  [Static prediction of tag tests]). The entry then falls through
  into the loop's head, and every iteration pays a jump back.
  optHsPatterns gives back edges a bonus (increaseBackEdgeWeight),
  but static prediction replaces the weights of the branches
  its heuristics cover with its predictions, so that the bonus counts only
  at those it leaves alone, a heap or stack check's and those whose
  targets are all back edges. sequenceChain now raises (preferBackEdges)
  each back edge by a little more than the weight of the heaviest edge
  into its head that is not a call, a back edge or a self loop, which
  keeps the order of several back edges into one head; Note [Layout
  relevant edge weights]. A back edge out of a jump table is not raised:
  it cannot fall through, so raising it would only take the head's
  fall-through from an edge that can. preferBackEdges takes the back edges
  from findBackEdges, now exported.
  
  The garbage collector's return to the block that made a heap or stack
  check is no such loop: a back edge leaving a block that follows a failed
  check stays as it is. checkFailures, in GHC.CmmToAsm.CFG, finds
  those blocks: the targets of the less likely edges of a branch
  that getCfg tags HeapStackCheck, one whose condition reads SpLim, HpLim
  or BaseReg, and their successors, such as the block the garbage
  collector returns to, which can be a continuation that a call returns
  to as well. A block that follows such a block and whose one out-edge has
  the code generator as its source, such as a block the register allocator
  puts there, counts as following a failed check too (coldBlocks). Raising
  those back edges too makes containers' benchmarks take 0.28% more
  instructions (set fromAscList:fusion 3.2%, intset fromList:worstCase
  3.0%); leaving out the blocks that follow a failed check but
  not the block the register allocator puts after such a block, 0.09% more
  (map alter insert 0.9%). A new Note, [Frequencies before register
  allocation] in GHC.CmmToAsm.CFG, names two shapes coldBlocks misses:
  the block allocMoreStack splits off a block the garbage collector
  returns to, and a fixup block on a failure edge, which takes the edge's
  tag. A TODO at coldBlocks points there. Building the set in GHC.CmmToAsm
  instead, from checkFailures' blocks, the blocks allocMoreStack splits
  off a cold entry block and the fixup blocks on an edge out of or
  into a cold block, changed a few procedures' layout in nofib and moved
  no figure measured, while costing up to 0.03% more compile allocation
  at -O0.
  
  Nor is a back edge into the one successor of the procedure's entry block
  raised: the entry would then jump to that block at every call, which
  a loop that seldom iterates does not win back. The RTS's entry code has
  such loops, which retry on an indirection: raising their back edges made
  stg_BLACKHOLE_info, stg_enter_info and stg_forceIO_info begin
  with a jump into the loop, so that stg_BLACKHOLE_info ran an instruction
  more for every blackhole entered. Where the code generator split
  the entry block, as allocMoreStack does, and the block holding the rest
  of its code has one successor, that successor stands in for the entry's.
  
  Measured against the parent commit, in instructions; sequenceChain runs
  only under -fblock-layout-cfg, on at -O1 and -O2. At -O2 nofib's
  programs take 0.06% fewer (queens 1.7%, wheel-sieve1 1.0%), vector's
  benchmarks 0.44% fewer (leaffix 3.4%, rootfix 2.7%, listRank 2.2%),
  containers' 0.19% fewer and megaparsec's 0.25% fewer (skipMany 2.2%,
  many 1.0%); at -O1 nofib's take 0.06% fewer (queens 1.4%, knights 1.3%,
  wheel-sieve1 1.0%); fannkuch-redux moves by no more than its noise.
  This takes back the rises of the commit that hands calcFreqs
  a procedure's loops inner first: all of nofib's and most of containers'
  and megaparsec's. In containers and nofib the largest rises
  are the rule's own trade, a loop's entry now paying a jump
  that its iterations seldom win back: intmap lookup_mixed 2.0%, whose
  lookups gain nothing from the descent that now falls through,
  and k-nucleotide 0.5% (0.3% at -O1), whose bucket loop runs about once
  an entry. Next come intset's intersection and difference benchmarks, 0.7
  to 0.8%, which later commits take back. No benchmark's allocation
  changes beyond nofib's run-to-run noise. The compiler allocates 0.1%
  more compiling perf/compiler's T12707 and T783 at -O; elsewhere
  its allocation moves by less than 0.1%. Compiling !16269's
  ManyBasicBlocks at -O1 and -O2, the compiler allocates 0.2% more.
  
  Assisted-by: Claude Opus 5.5
  

• 42bdf1c4
  by Mikolaj Konarski at 2026-10-30T23:42:10+01:00

  Specialise the linear allocator and liveness pass to x86-64
  
  The linear allocator is overloaded in the instructions and in the free
  registers, and the liveness pass in the instructions, so on x86-64 too
  they called every instruction method through a dictionary: the code
  generator is specialised for each target, but its calls of regAlloc
  and cmmTopLiveness went to the overloaded functions. Both now have
  a SPECIALISE pragma for x86's instructions, and NOINLINE [0], without
  which neither rule fires, when the boot compiler builds stage 1 or when
  the stage-1 compiler builds stage 2: cast worker/wrapper makes each
  function an alias of its body, cast to UniqDSM, and the alias inlines
  from the function's own phase whatever its rules' phase, so it inlines
  into the code generator before the call there becomes one at x86's
  instructions, which is what the rule rewrites. A phase on the SPECIALISE
  pragmas alone, [0] or [2], makes neither rule fire. linearRegAlloc
  passes the other targets' free registers through a NOINLINE function,
  which the specialiser does not specialise, so that only x86-64's get
  a copy of the allocator; Note [Specialising the linear allocator].
  The allocator's constraint synonym no longer requires Outputable free
  registers, which nothing prints, and is renamed
  from OutputableRegConstraint to RegAllocConstraint. Liveness.hs now
  imports GHC.CmmToAsm.X86 for its Instruction instance, which Linear.hs,
  importing Liveness.hs, has as well, so the allocator's modules
  that import either compile after the x86 code generator; this makes
  no import cycle, as of the allocator's modules the x86 code generator
  imports only GHC.CmmToAsm.Reg.Target.
  
  Specialising joinToTargets as well, with NOINLINE [0], saved
  the compiler less allocation than this commit does.
  
  The idea of specialising the allocator comes from the draft !4764 by Ben
  Gamari and Andreas Klebinger, which overlaps with this commit: !4764
  specialises the linear allocator to x86-64 and i386, by INLINEABLE
  pragmas on the allocator's functions and SPECIALIZE pragmas
  in GHC.CmmToAsm.X86, and this commit specialises it and the liveness
  pass to x86-64, by the SPECIALISE pragmas above.
  
  The generated code is the same: nofib's object files are byte for byte
  the parent's. The compiler allocates 1.7% less compiling perf/compiler's
  T3294 at -O0 and 0.7% less at -O, 1.2% less compiling T12707 at -O0
  and 0.4% less at -O, 1.0% less compiling T783 at -O0 and 0.2% less
  at -O, and 1.7% less compiling T9961 at -O0, though less than 0.1% less
  at -O, where CI compiles it. Compiling !16269's ManyBasicBlocks at -O1
  and -O2, the compiler allocates 0.5% less. The compiler's code grows
  by about 100 KB.
  
  Assisted-by: Claude Opus 5.5
  

• 50fc8179
  by Mikolaj Konarski at 2026-10-30T23:42:10+01:00

  Record the linear allocator's spills only for -ddump-asm-stats
  
  recordSpill kept every spill and reload the linear allocator inserts,
  with its reason, in ra_spills, for the statistics -ddump-asm-stats
  prints, their only reader. It now keeps them only when that flag is on.
  The comments in GHC.CmmToAsm.Reg.Linear.Base that called the flag
  -ddrop-asm-stats now call it -ddump-asm-stats. The statistics printed
  are the same, and so is the generated code. The compiler allocates 0.20%
  less compiling perf/compiler's T3294 at -O0.
  
  Assisted-by: Claude Opus 5.5
  

• 818486b3
  by Mikolaj Konarski at 2026-10-30T23:42:10+01:00

  Check the order of liveness SCCs where jump targets are looked up
  
  computeLiveness checked that a procedure's SCCs come in reverse
  dependency order (checkIsReverseDependent) in a walk of its own,
  gathering every instruction's jump destinations, and panicked otherwise.
  The liveness pass looks every jump target's live-in registers up anyway,
  taking none for a target missing from its map; that lookup now panics
  instead, naming the target. For this, livenessSCCs enters the blocks
  of a cyclic SCC in the map before the SCC's first walk, with no register
  live, which is what the lookup took them to have, so that a target can
  be missing only where the SCCs are out of order, or where the CFG
  that gave the reachable blocks (sccBlocks) lacks it. The separate walk
  goes, and with it computeLiveness, which then only called livenessSCCs:
  regLiveness calls that itself. The generated code is the same.
  The compiler allocates 0.6% less compiling perf/compiler's T3294 at -O0
  and 0.2% less at -O, 0.5% less compiling T12707 at -O0 and 0.2% less
  at -O, 0.7% less compiling T783 at -O0 and 0.2% less at -O, and 0.7%
  less compiling T9961 at -O0. Compiling !16269's ManyBasicBlocks at -O1
  and -O2, the compiler allocates 0.1% less.
  
  Assisted-by: Claude Opus 5.5
  

• 313fd7f9
  by Mikolaj Konarski at 2026-10-30T23:42:10+01:00

  Keep a procedure's imports only where they are emitted
  
  cmmNativeGens forced the imported symbols of each procedure, rendered
  as text, to avoid a space leak, and kept them for makeImportsDoc, which
  emits them only where needImportedSymbols holds; on x86-64 Linux
  that takes -dynamic -fno-PIC. Where needImportedSymbols does not hold,
  cmmNativeGens now neither forces nor keeps them. The generated code
  is the same, also under -dynamic, -fPIC and -dynamic -fno-PIC.
  The compiler allocates 0.15% less compiling perf/compiler's T9961
  at -O0.
  
  Assisted-by: Claude Opus 5.5
  

• 256599c2
  by Mikolaj Konarski at 2026-10-30T23:42:10+01:00

  Copy no register list in x86's mkRU where every register counts
  
  regUsageOfInstr on x86 and x86-64 filtered both of an instruction's
  register lists, keeping the virtual registers and the real ones
  an allocator may hand out (interesting), and so copied both lists
  for every instruction. mkRU now returns a list unchanged where every
  register in it is kept. Sylvain Henry's !16843 (GHC #28008) overlaps
  with this commit: !16843's register usage DSL tests each register
  as it adds it, but copies a list of registers it is given as it tests
  them, where this commit returns such a list unchanged when every
  register in it is kept. The generated code is the same. The compiler
  allocates 1.2% less compiling perf/compiler's T3294 at -O0 and 0.5% less
  at -O, 0.7% less compiling T12707 at -O0 and 0.2% less at -O, 0.5% less
  compiling T783 at -O0, and 1.5% less compiling T9961 at -O0. Compiling
  !16269's ManyBasicBlocks at -O1 and -O2, the compiler allocates 3.0%
  less.
  
  Assisted-by: Claude Opus 5.5
  

• e632e6c1
  by Mikolaj Konarski at 2026-10-30T23:42:10+01:00

  Mark the registers an instruction clobbers allocated, free or not
  
  clobberRegs marked allocated those of the registers an instruction
  clobbers that were free, listing the free registers of every class
  for each instruction that writes a real register, with its own copy
  of allFreeRegs from GHC.CmmToAsm.Reg.Linear.FreeRegs, and looking each
  clobbered register up in the list. The FR class now has frClobberRegs,
  which marks the clobbered registers allocated: by default those of them
  that are free, by allFreeRegs, as clobberRegs did, since on AArch64,
  RISC-V and LoongArch allocateReg panics on a register already allocated;
  on x86-64, whose allocateReg marks a register that is not free
  as it marks a free one, it marks every one of them, listing nothing.
  clobberRegs calls it, and GHC.CmmToAsm.Reg.Linear no longer imports
  the register class modules that only the copy used. The free registers
  after a clobber are the same on every target, and so is the generated
  code on x86-64.
  
  The compiler allocates 0.1% less compiling perf/compiler's T3294 at -O0,
  0.4% less compiling T12707, 0.5% less compiling T783, and 1.2% less
  compiling T9961; at -O, 0.1% less compiling T12707. Compiling !16269's
  ManyBasicBlocks at -O1 and -O2, the compiler allocates 0.4% less.
  
  Assisted-by: Claude Opus 5.5
  

• bafb882b
  by Mikolaj Konarski at 2026-10-30T23:42:10+01:00

  Keep an instruction's register usage in its liveness
  
  The liveness pass's backward walk computes the register usage of every
  instruction it annotates (regUsageOfInstr), and its forward walk
  (livenessForward), the linear allocator's genRaInsn and the graph
  allocator's spill cost (slurpSpillCostInfo) and spiller (regSpill_instr)
  computed it again. Liveness now keeps it (liveUsage), and those use
  the kept usage instead. patchRegsLiveInstr, which only the graph
  allocator reaches, computes the patched instruction's usage again,
  as an instruction's usage can depend on whether its registers are equal:
  x86's VXOR of a register with itself into itself reads nothing. A new
  Note in GHC.CmmToAsm.X86.Instr, [What x86's regUsageOfInstr reports],
  lists that case with the others where the usage is not what
  the processor does. This commit is, but for that Note, a subset
  of Sylvain Henry's !16843 (GHC #28008), which keeps the usage
  in the liveness annotation too and also builds it more cheaply in every
  backend; !16843 was read before this commit was written. The generated
  code is the same, with the linear allocator and with -fregs-graph.
  The compiler allocates 2.1% less compiling perf/compiler's T3294 at -O0
  and 0.8% less at -O, 1.2% less compiling T12707 at -O0 and 0.4% less
  at -O, 0.9% less compiling T783 at -O0, and 1.9% less compiling T9961
  at -O0. Compiling !16269's ManyBasicBlocks at -O1 and -O2, the compiler
  allocates 0.1% less.
  
  Assisted-by: Claude Opus 5.5
  

• 04892024
  by Mikolaj Konarski at 2026-10-30T23:42:10+01:00

  Walk a block of a cyclic SCC again only when its successors change
  
  livenessSCCs annotated the blocks of a cyclic SCC by walking all of them
  again until the registers live on entry to every block stopped changing,
  comparing two whole block maps as lists after each round. livenessCyclic
  now walks a block again only when the registers live on entry to one
  of its successors in the SCC, or their formats, have changed since
  its last walk. The old loop compared only which registers are live
  (the Eq of Regs ignores formats), so it could stop before a wider format
  had reached every block of the SCC, the case Note [Register formats
  in liveness analysis] describes; the new one carries formats through
  as well. This fixes GHC #27619 and does what GHC #27437 asks: the walk
  itself finds the changes, and no whole block map is compared.
  This commit overlaps with Simon Jakobi's !16537, which fixes both issues
  by iterating the fixpoint over the SCC's blocks until the formats
  of the registers live on entry converge, and also removes the derived
  Ord of formats, comparing them by width: this commit follows
  it in carrying the formats through, walks again only the blocks whose
  successors changed where !16537 walks every block of the SCC each round,
  and takes its regression test T27619 unchanged. The derived Ord
  of formats, which GHC #27619 also notes and which can keep a register
  read at two vector formats at the narrower, stays, as Note [Register
  formats in liveness analysis] says.
  
  The generated code is the same on every program measured.
  Of perf/compiler's T3294, T12707, T783 and T9961, only T9961 at -O has
  a cyclic SCC, and its figure moves by 0.01%; compiling nofib's programs
  at -O2, the compiler allocates 0.12% less in geometric mean and up
  to 3.4% less (spectral/puzzle). Compiling !16269's ManyBasicBlocks
  at -O1 and -O2, the compiler allocates 24.7% less.
  
  Assisted-by: Claude Opus 5.5
  

• 54cf8aa3
  by Mikolaj Konarski at 2026-10-30T23:42:10+01:00

  Fill in liveBorn only for the graph allocator and -ddump-asm-liveness
  
  The liveness pass recorded, for every instruction, the registers born
  there (liveBorn), which costs a forward walk over every instruction
  of every block. Only the graph allocator and -ddump-asm-liveness use it.
  regLivenessBorn is now a pass of its own, which the graph allocator,
  its iterative variant included, runs on its input and again after
  recomputing liveness, and which CmmToAsm runs only for the dump.
  The generated code is the same, with the linear allocator
  and with -fregs-graph. The compiler allocates 2.4% less compiling
  perf/compiler's T3294 at -O0 and 0.9% less at -O, 1.7% less compiling
  T12707 at -O0 and 0.6% less at -O, 1.5% less compiling T783 at -O0
  and 0.2% less at -O, and 2.0% less compiling T9961 at -O0;
  with -fregs-graph it allocates up to 0.3% more (T9961 at -O0). Compiling
  !16269's ManyBasicBlocks at -O1 and -O2, the compiler allocates 0.5%
  less.
  
  Assisted-by: Claude Opus 5.5
  

• 64eaebb4
  by Mikolaj Konarski at 2026-10-30T23:42:10+01:00

  Prefer the register a vreg is moved into where it dies
  
  The linear allocator preferred, for a vreg, the first register
  it was recorded in on entry to any block (findPrefRealReg); a new Note,
  [The first jump into a block fixes its registers], says what the first
  jump into a block decides, that register included. The allocator now has
  preferences, tried best first. firstFreeInOrder takes the free registers
  of the vreg's class and returns the first preference among them, else
  the first of them. allocRegsAndSpill_spill takes its choice, and so does
  saveClobberedTemps, which took the first free register where it moves
  a value out of a clobbered one. This commit adds one preference, ahead
  of the first-used register: the real register the current block moves
  the vreg into where the vreg dies. A value computed into a vreg
  that the block then moves into R1, before an evaluation or a return,
  is computed in R1, and the move, now from a register to itself,
  is dropped by genRaInsn. The first-used register, which keeps a loop
  variable in one register at both ends of a loop, gains nothing
  for a value that dies in the block. Ranked after it, the new preference
  cost nofib's scs 0.2% more instructions once later commits changed
  the order of the free registers: a spilled value was reloaded
  into its first-used register and then moved into R1's register.
  processBlock builds, for each block, the map from a vreg to the register
  the block moves it into where it dies (dyingMoves, rc_moveDests).
  The preference is taken from Andreas Klebinger's draft !16693, whose
  choice of a free register prefers the real register a vreg is moved
  into where it dies, in any block (GHC #27742); this commit takes
  the moves of the current block, a subset of those.
  
  The map lives in a record of its own, RA_Context, which RA_State holds
  in one strict field (ra_context), rather than in RA_State itself, where
  an unused field alone makes the compiler allocate 0.3% more compiling
  T3294 at -O0. The NCG configuration, which the allocator uses but does
  not update either, moves there too (rc_config, was ra_config), and runR
  takes the context in its place.
  
  The expected assembly of codeGen/should_gen_asm's T24813 loses the movq
  before each function's jmp: each popcount is now computed in R1.
  
  This applies on every target the linear allocator serves; the figures
  below are x86-64's. Measured against the parent commit, in instructions:
  nofib's programs, linked with the same libraries for both, take 0.15%
  fewer (0.16% at -O1, 0.58% at -O0), none as much as 0.2% more beyond
  their run-to-run noise; vector's benchmarks 0.27% fewer, none more;
  containers' 0.39% fewer, none as much as 0.1% more beyond their noise;
  megaparsec's 0.49% fewer (skipSomeTill 1.2%, endBy1 1.2%), none more;
  fannkuch-redux moves by no more than its noise. No benchmark's
  allocation changes beyond nofib's run-to-run noise. The compiler
  allocates 0.1% more compiling perf/compiler's T12707 at -O0, 0.2% more
  compiling T783, and 0.08% more compiling T9961; compiling T3294
  its allocation moves by less than 0.1%.
  
  Assisted-by: Claude Opus 5.5
  

• 855757df
  by Mikolaj Konarski at 2026-10-30T23:42:10+01:00

  Prefer the register a later block moves a vreg into where it dies
  
  firstFreeInOrder now has a last preference: the real register a block
  the vreg is live into moves it into where it dies, for a vreg computed
  blocks earlier, such as R1 for a value evaluated some blocks after
  it is computed (wideMoveDests, once a procedure; rc_wideDests).
  It is left out where that register is live together with the vreg
  somewhere, which a walk of the blocks finds: at a block's entry, after
  an instruction's writes, and where a vreg born while the vreg is live
  is moved into that register where it dies, in the block it is born in.
  The walk follows a vreg on into the vreg it is moved into where it dies,
  to which the allocator gives the same register, dropping the move;
  and it takes an instruction's writes from its register usage, liveBorn
  being filled in only for the graph allocator and the liveness dump.
  dyingMoves now gives moves into vregs as well, and is INLINE: out
  of line it makes the compiler allocate 1.0% more compiling
  perf/compiler's T3294 at -O0. This preference and the previous commit's
  together overlap with that of Andreas Klebinger's draft !16693, the real
  register a vreg is moved into where it dies, in any block.
  
  The rule for a vreg born while the vreg is live keeps the register
  for the later vreg, which its own block moves into it. Without it,
  in containers' graph buildG the loop's index and lower bound took R2's
  and R3's registers, which the block making the loop's call needed
  for its arguments, and that block ended with three moves an edge, 3.3%
  more instructions. Counting every vreg born while the vreg is live
  and moved into the register in any block made containers' map insertWith
  take 3% more instructions: its value argument arrives in R3
  and is passed in R3 to both recursive calls, and the node's key, born
  later in the loop and moved into R3 in another block, made it lose R3
  as a preference, so every iteration moved it out of R3 and back. Note
  [Frequencies before register allocation] gains a bullet saying
  that where blocks give a vreg different destinations the last block's
  wins, with a TODO at wideMoveDests: taking the hottest block's instead,
  by mkGlobalWeights, moved containers' benchmarks both ways by up to 1.4%
  and cost 0.24% more compile allocation, its estimate made
  for this alone. A comment there notes that a destination no allocator
  hands out, Sp, Hp or BaseReg, stays a candidate; leaving those out
  changed no code measured and costs compile allocation.
  
  This applies on every target the linear allocator serves; the figures
  below are x86-64's. Measured against the parent commit, in instructions:
  nofib's programs take 0.09% fewer (0.07% at -O1, 0.06% at -O0), none
  as much as 0.2% more beyond their run-to-run noise; vector's benchmarks
  0.26% fewer (generateIO 4%), none more; megaparsec's 0.14% fewer
  (skipCount 0.9%, choice 0.6%), none more; fannkuch-redux moves
  by no more than its noise. The benchmarks of containers take 0.47% fewer
  (intset fromAscList:sparse:fusion 6.3%, intmap symmetricDifference 5%),
  some up to 2.2% more, which later commits take back: graph buildG 2.2%,
  whose loop index, given no preference, now takes R1's register, which
  the call at the loop's end needs, so two moves an edge remain; map
  foldMap_traverseSum 1.6%; map alter insert 1.3%. No benchmark's
  allocation changes beyond nofib's run-to-run noise. The compiler
  allocates 0.1% more compiling perf/compiler's T3294 at -O0, 0.6% more
  compiling T12707, 0.7% more compiling T783, and 1.1% more compiling
  T9961; the next commit takes back half or more of each. Compiling
  !16269's ManyBasicBlocks at -O1 and -O2, the compiler allocates 0.3%
  more.
  
  Assisted-by: Claude Opus 5.5
  

• c4b5ed6f
  by Mikolaj Konarski at 2026-10-30T23:42:11+01:00

  Ignore the moves of blocks that follow a failed heap or stack check
  
  wideMoveDests now leaves out the moves of the blocks that follow
  a failed heap or stack check, such as those calling the garbage
  collector: the move there seldom runs, and the register it names can
  cost a move in the hot code. In containers' map foldMap_traverseSum
  a node and its field both had %rbx as their destination, the field
  from the hot block that evaluates it, the node only from the heap
  check's failure block, which calls the garbage collector; the node,
  allocated first, took %rbx, and the field, given %rax, moved into %rbx
  at every evaluation: 1.5% more instructions.
  
  CmmToAsm takes those blocks from checkFailures (allocCold) and passes
  them to the linear allocator, wherever the backend maintains the CFG,
  -finfo-table-map or not; that is on x86-64 only, and elsewhere the set
  is empty. Leaving out only the failure targets that no other edge
  enters, as an earlier form of this change did, changes no code
  in perf/compiler's T3294, T12707, T783 and T9961 or in containers'
  benchmarks, and makes the compiler allocate slightly more.
  
  Measured against the parent commit, in instructions: nofib's programs,
  vector's and megaparsec's benchmarks and fannkuch-redux move by no more
  than their noise; containers' benchmarks take 0.005% fewer (set
  fromList-distinctAsc:fusion 2.2%, map foldMap_traverseSum 1.5%), none
  as much as 0.1% more beyond their noise. No benchmark's allocation
  changes beyond nofib's run-to-run noise. The compiler allocates 0.09%
  less compiling perf/compiler's T3294 at -O0, 0.4% less compiling T12707,
  0.5% less compiling T783, and 0.8% less compiling T9961.
  
  Assisted-by: Claude Opus 5.5
  

• 17a0a212
  by Mikolaj Konarski at 2026-10-30T23:42:11+01:00

  Allocate the blocks the garbage collector returns to last
  
  The linear allocator records, at the first jump it allocates
  into a block, the registers the block starts with, and later jumps
  into the block move their values to match. linearRA_SCCs allocated
  the SCCs in order, so the block the garbage collector returns to after
  a heap or stack check fails, which jumps back into the block that made
  the check, could be allocated before the hot path reached that block,
  and so fix the registers it starts with. In containers' map alter
  the block that builds the new node makes such a check; its return block,
  allocated first, reloaded the new subtree into %rdi, R4, where
  the rebalancing call takes it, while the hot path still held the other
  subtree there, so the hot path reached the block through a fixup block
  rotating three registers at every level the insertion returns through.
  linearRA_SCCs now allocates those return blocks (the procedure's entry
  blocks in the set checkFailures gives, which it now takes, those
  in a cycle excepted), and any SCC only they lead to, after the others,
  so that the hot path records the registers and the return block pays
  the fixup. As it now tests every block for whether a jump has reached
  it, it looks the entry blocks up in a set built once rather
  than in their list. This commit overlaps with Sylvain Henry's !16673
  (GHC #27800), read before this commit was written: both defer,
  in linearRA_SCCs, return blocks outside cycles; !16673 those that jump
  into a loop, calls' continuations included, with the acyclic blocks only
  they lead to, and this commit those the garbage collector returns to,
  whether or not they jump into a loop, with any SCC only they lead to.
  
  Taking no wide move destination while allocating such a block, instead,
  fixes map alter but makes map insertWith take 3% more instructions,
  the mirror case: its return block, allocated first, reloads the value
  argument into R3's %rsi, its wide destination, where the hot path has
  it; without that destination it reloads it into %rax, and the hot path
  moves it out of %rsi and back at every level. Note [Frequencies before
  register allocation] gains a bullet saying that checkFailures also
  counts as cold blocks the hot path may run, a continuation that a call
  returns to as well and a failure target that another edge enters,
  and that an estimate computed in a Cmm pass could replace
  the classification; linearRA_SCCs and checkFailures gain TODOs pointing
  there. Where such a continuation is on the path into a loop, deferring
  it measured better than leaving it out of the set: the loop
  is then allocated first, starting from the block the garbage collector
  returns to from the loop's own check, so that the path into the loop
  pays the moves once and the loop's latches none (containers'
  set-benchmarks); leaving such continuations out costs nofib's scs 1.1%
  more instructions and vector's maximumOn 2.9%, and leaving out such
  failure targets changes no code measured and costs compile allocation.
  Allocating a loop before the path into it on purpose, by deferring
  the blocks that jump into an SCC holding an entry block, costs
  fannkuch-redux 13% at -O1, whose inner loop lies in its outer loop's
  SCC. !16673's deferral, of every return continuation outside a cycle
  that jumps into a loop, is not used either, because it was found
  incorrect: it defers as cold a continuation that is itself inside a loop
  through the Haskell stack, and fannkuch-redux then runs 16 to 19% more
  instructions.
  
  Measured against the parent commit, in instructions: nofib's programs
  take 0.08% fewer (wheel-sieve2 2.2%; 0.19% at -O1, fasta 10.5%), none
  as much as 0.2% more beyond their run-to-run noise; vector's benchmarks
  1.2% fewer (maximumOn 17%, minimumOn 15%), none more; megaparsec's 2.8%
  fewer (endBy 22%, skipMany 16%), endBy1 1.8% more, which later commits
  take back; fannkuch-redux moves by no more than its noise. containers'
  benchmarks take 0.20% fewer (intset fromList:worstCase 8.2%, and map
  alter insert, the case above, 1.3%), some up to 1.7% more: sequence
  adjust.10 1.7%, tree PostOrder foldl_elem 1.6%, intmap
  fromAscList:fusion 1.3%, map fromList-distinctAsc 1.1%. Later commits
  take them back, map fromList-distinctAsc to 0.6% above the parent,
  the others entirely. No benchmark's allocation changes beyond nofib's
  run-to-run noise. The compiler's allocation compiling perf/compiler's
  T3294, T12707, T783 and T9961 moves by less than 0.1%.
  
  Assisted-by: Claude Opus 5.5
  

• 62953586
  by Mikolaj Konarski at 2026-10-30T23:42:11+01:00

  Prefer a vreg's register at a recorded jump target (GHC #27980)
  
  firstFreeInOrder now puts first the register the vreg has on entry
  to a jump target of the current block whose assignment is already
  recorded (jumpLocRegs), such as a loop header jumped to from the loop's
  end: in that register the vreg needs no fixup move at the jump.
  The first-used register, which a loop variable took until now,
  is the one the vreg was recorded in by whichever block recorded
  it first, which need not be the target. processBlock looks up
  the recorded assignments of the block's jump targets once, when
  the block starts (rc_jumpLocs, in RA_Context): a target's assignment
  is recorded only at the block's jumps, after which no preference
  is looked up. Built lazily, that list makes the compiler allocate 0.3%
  more compiling perf/compiler's T3294 at -O0.
  
  In GHC #27980's reproducer the loop's continuation then reloads
  a variable straight into the register the loop header has it in,
  and the fixup block goes away. It is a preference, applying where
  the block that gives the vreg a register jumps to a target whose
  assignment is recorded and the vreg's register there is free; the fixups
  of GHC #27800, of which #27980 was closed as a duplicate, stay.
  
  This applies on every target the linear allocator serves; the figures
  below are x86-64's. Measured against the parent commit, in instructions:
  nofib's programs, vector's benchmarks and fannkuch-redux move by no more
  than their noise; containers' benchmarks take 0.01% fewer (intset
  mapMonotonic 1.3%) and megaparsec's 0.005% fewer (skipManyTill 0.1%),
  none as much as 0.1% more beyond their noise. No benchmark's allocation
  changes beyond nofib's run-to-run noise. The compiler allocates 0.14%
  less compiling perf/compiler's T3294 at -O0; compiling T12707, T783
  and T9961 its allocation moves by less than 0.1%.
  
  Assisted-by: Claude Opus 5.5
  

• 20ac24e6
  by Mikolaj Konarski at 2026-10-30T23:42:11+01:00

  Order x86-64 free registers around R1 and clobbering writes (GHC #27981)
  
  On x86-64 a vreg now takes R1's register, %rbx, last: an evaluation
  and a return write it, so a value given it may have to move out of their
  way, and a loop variable given it at the loop's entry moves at every
  iteration (GHC #27981). Before the others it takes the registers
  no instruction writes while the vreg is live past the write: for a vreg
  live across a C call, these are the registers the call preserves,
  on System V R2's %r14 and %rbx, and for one still live where an argument
  is moved into R2's %r14 for a jump, they exclude %r14. Given a register
  such an instruction writes, the vreg would have to move out of the way.
  firstFreeInOrder takes, where no preference is free, the first free
  register in this order. In GHC #27981's reproducer this commit already
  removes the back edge's fixups; the next commit removes the cause
  the issue names.
  
  regClobbers finds, for each vreg, the registers written while
  it is live, once a procedure on x86-64: the liveness pass now records,
  at each instruction that writes a real register, the registers live
  after it (liveAcross), and regClobbers adds the written registers
  to every vreg among those that is live past the instruction, as bits
  by register number. Only x86-64's fallback uses them, and on the other
  targets RA_Context's field is empty, so that no unread thunk keeps
  the procedure's code alive. A move of the vreg itself into a register
  is no such write. Leaving out the writes in the blocks that follow
  a failed check costs containers' lookupge-intmap Milan lookups 0.5 to 1%
  more instructions, a failure block's write having kept a vreg,
  by accident, out of a register that a later vreg is moved into; Note
  [Frequencies before register allocation] gains a bullet on the case,
  with a TODO at regClobbers. Andreas Klebinger's draft !16693, read
  before this commit was written, charges a vreg for each register
  that an instruction in a loop starts writing while the vreg is live
  across it, and this order overlaps with that clobber cost: both steer
  a vreg away from the registers written while it is live, !16693
  by a cost counted within loops, this commit by the order of the free
  registers, from the writes met anywhere the vreg is live.
  
  On x86-64, for a vreg that has preferences, all of them taken,
  firstFreeInOrder also leaves out, where a free register would remain,
  the registers that the recorded assignment of a jump target of the block
  gives another vreg, so that the vreg does not take a register the jump
  will need for that one: a part of what GHC #26666 asks.
  
  The expected assembly of codeGen/should_gen_asm's
  bytearray-memcpy-unroll and bytearray-memset-unroll names other
  registers now; the instructions and their order are the same.
  
  Simpler forms cost more. %rbx last for every vreg costs up to 3% more
  instructions in procedures that make C calls. %r14 first as well,
  wherever no vreg is live across a C call, gains in some loops but costs
  up to 3% more elsewhere, where %r14 is wanted later, for R2 or by a jump
  target's recorded assignment. Taking the registers a C call preserves
  first for every vreg live across one, ignoring every other write, makes
  fannkuch-redux take 1.3% more instructions: a loop variable live across
  a call elsewhere in the procedure is given %r14 and moves out of R2's
  way at every iteration.
  
  Measured against the parent commit, in instructions: nofib's programs
  take 0.38% fewer (fasta 5.1%, k-nucleotide 4.3%, gen_regexps 3.3%; 0.47%
  at -O1, 0.06% at -O0), none as much as 0.2% more beyond their run-to-run
  noise; fannkuch-redux 0.19% fewer; vector's benchmarks 1.0% fewer
  (nextPermutationBijective 4.4%, findIndexR 3.4%), none more than 0.1%;
  containers' benchmarks 0.66% fewer (set fromAscList:fusion 6.8%, intset
  partition 6.1%, graph buildG 2.2%), some up to 1.2% more beyond their
  noise (intset mapMonotonic 1.2%, intmap fromAscList and map
  fromListWith-desc:fusion 1.0%, map union-common 0.5%), each within
  an earlier commit's fall; megaparsec's benchmarks 0.59% fewer
  (reachOffsetNoLine 6.7%, many 5.6%), some up to 2.7% more (skipMany
  2.7%, skipSome 2.0%, skipCount 1.8%); in skipSome, Data.Text's UTF-8
  decoding, inlined into it, now loads each byte into R2's register
  instead of R1's, so that on its ASCII path the character and its width
  reach the join after it in each other's registers and are swapped. Later
  commits take these back entirely, the swap last, by assigning literals
  after computed values. No benchmark's allocation changes beyond nofib's
  run-to-run noise. The compiler allocates 0.2% more compiling
  perf/compiler's T3294 at -O0, 0.2% more compiling T12707, 0.2% more
  compiling T783, and 0.3% more compiling T9961. Compiling !16269's
  ManyBasicBlocks at -O1 and -O2, the compiler allocates 0.6% more.
  
  Assisted-by: Claude Opus 5.5
  

• f1e9994f
  by Mikolaj Konarski at 2026-10-30T23:42:11+01:00

  Free every register not live into a newly reached block (GHC #27981)
  
  On the first jump to a block, joinToTargets_first recorded, beside
  the block's assignment, the block's free registers, the source block's
  with those of the vregs not live into the target released, and initBlock
  started the block with them. A real register still allocated at the jump
  and not live into the target, R1 above all where it is allocatable,
  therefore stayed allocated in the target block until the block wrote
  it and that value died: a value the block reloads cannot go back to it,
  and the block's jumps may need fixup moves. initBlock now derives
  the free registers on entry to every block: every allocatable one
  but the real registers live into it and those holding the vregs
  of its recorded assignment, if it has one; a recorded assignment
  no longer carries free registers, and joinToTargets no longer computes
  the registers to release (to_free), nor needs FR. In its reproducer
  the previous commit already removes the fixups, so the reproducer does
  not show this fix alone; here its inline form goes from 14.0 to 13.0
  instructions an element. allocateRealRegs marks the real registers among
  those live into a block allocated, and initBlock takes the procedure's
  initial free registers from RA_Context (rc_initFree) rather than rebuild
  them for each block; runR starts the allocator with them too,
  and with an empty block assignment, register assignment and stack map,
  taking none of them as arguments; joinToTargets_first, left with two
  statements, is inlined by hand at its one call site.
  
  This applies on every target the linear allocator serves; the figures
  below are x86-64's. Measured against the parent commit, in instructions:
  nofib's programs, vector's benchmarks and fannkuch-redux move by no more
  than their noise; containers' benchmarks take 0.03% fewer (tree edges
  1.4%, graph transposeG 1.3% and buildG 1.1%), none more beyond their
  noise, and megaparsec's 0.21% fewer (many 1.2%, sepEndBy 0.9%), none
  more. No benchmark's allocation changes beyond nofib's run-to-run noise.
  The compiler allocates 0.2% less compiling perf/compiler's T3294 at -O0,
  0.8% less compiling T12707, 0.7% less compiling T783, and 1.1% less
  compiling T9961. Compiling !16269's ManyBasicBlocks at -O1 and -O2,
  the compiler allocates 2.5% less.
  
  Assisted-by: Claude Opus 5.5
  

• c2a7c161
  by Mikolaj Konarski at 2026-10-30T23:42:11+01:00

  Prefer a loop variable's register for the value moved into it
  
  A vreg that the current block moves, where it dies, into another vreg,
  such as a loop's next index moved into the index variable before
  the jump back to the loop's header, now prefers the register
  the recorded assignment of a jump target of the block gives that other
  vreg, as it prefers a real register the block moves it into:
  processBlock adds such moves to rc_moveDests, from rc_jumpLocs.
  In that register the move goes away, and at the jump the other vreg
  is where the target's recorded assignment has it.
  
  A move counts only where the block does not write its source again
  (dyingMovesLast): a preference is looked up by the vreg, so it would
  otherwise reach the vreg's later value. Where such a move counted,
  in nofib's gcd, whose loop ends by shifting loop variables (t2C8 :=
  t2Cb, then t2Cb := a new value), the new value took the register
  the loop's header gives t2C8, and the jump to the header then had
  to exchange two registers through a stack slot: 0.4% more instructions.
  dyingMovesLast shares dyingMoves' test of a move where the vreg dies
  (dyingMove). The moves into real registers include those of a vreg
  the block writes again after the move, its later value then preferring
  that register too; leaving them out changed no code measured and costs
  compile time.
  
  Note [Register preferences in the linear allocator] said that leaving
  the registers of jump targets' recorded assignments out of the choice
  for a vreg with no preferences too cost vector's tridiag 3%. That cost
  came from a loop's next index kept out of the register the loop's header
  gives the index variable, which this preference now gives it;
  so the Note now says that the rule would gain nothing measured and cost
  compile time.
  
  This applies on every target the linear allocator serves; the figures
  below are x86-64's. Measured against the parent commit, in instructions:
  containers' benchmarks take 0.12% fewer: map lookup absent and alterF
  lookup absent 5% fewer, lookupge-map's GE Twan 3%, and intmap
  fromAscList 1.0%, taking back an earlier commit's rise; megaparsec's
  0.19% fewer (skipMany 2.6%, skipCount 1.8%, taking back an earlier
  commit's rises), none more; fannkuch-redux 0.01% fewer; nofib's programs
  and vector's benchmarks move by no more than their noise. No benchmark's
  allocation changes beyond nofib's run-to-run noise. The compiler's
  allocation compiling perf/compiler's T3294, T12707, T783 and T9961 moves
  by less than 0.1%.
  
  Assisted-by: Claude Opus 5.5
  

• 25782833
  by Mikolaj Konarski at 2026-10-30T23:42:11+01:00

  Skip registers written before a saved value's next read (GHC #26631)
  
  saveClobberedTemps, saving a value out of a register an instruction
  clobbers, such as an argument register of a C call, moved it
  into the first free register in order, even one a later instruction
  of the block writes before it reads the value again; then the value
  moved again or was spilled there. It now leaves out the registers
  the rest of the block writes before it next reads the value
  (unwrittenBeforeRead), and where every free register is one, spills
  the value at once. On System V every float and vector register
  is caller-saved, so such a value live across a C call ends in memory
  anyway: in simd013 two moves and a spill before the call become one
  spill (GHC #26631). Writes in later blocks are not looked at.
  
  Spilling at once wherever the first free register is in the value's
  clobber map (rc_clobbers) instead makes fannkuch-redux take 1.1% more
  instructions: a loop bound kept in %rbx across a memcpy call is spilled
  and reloaded at every iteration, %rbx being written elsewhere
  in the bound's live range, though not before the loop reads it.
  
  This applies on every target the linear allocator serves; the figures
  below are x86-64's. Measured against the parent commit, in instructions:
  nofib's programs take 0.03% fewer (k-nucleotide 1.1%), none as much
  as 0.2% more; fannkuch-redux 0.35% fewer; containers' benchmarks 0.003%
  fewer (map union-common 0.5%, taking back an earlier commit's rise),
  none more beyond their noise; megaparsec's 0.01% fewer (string 0.1%),
  none more; vector's benchmarks move by no more than their noise.
  No benchmark's allocation changes beyond nofib's run-to-run noise.
  The compiler's allocation compiling perf/compiler's T3294, T12707, T783
  and T9961 moves by less than 0.1%.
  
  Assisted-by: Claude Opus 5.5
  

• 7176e089
  by Mikolaj Konarski at 2026-10-30T23:42:11+01:00

  Write the linear allocator's state only where it changes
  
  releaseRegs, which genRaInsn calls twice for every instruction,
  with the registers the instruction reads for the last time and
  those it writes that die at once, wrote the assignment and the free
  registers back to the allocator's state even where it had no register
  to release; saveClobberedTemps, for every instruction that writes a real
  register, folded over the whole assignment in the monad and wrote
  it back even where no value sat in a clobbered register. Each write
  builds a new RA_State. releaseRegs now returns at once where it has
  nothing to release, and saveClobberedTemps picks the values to save
  by a pure fold, in the order the monadic one took them, and writes
  the state only where there are some. The generated code is the same.
  
  The compiler allocates 2.1% less compiling perf/compiler's T3294 at -O0
  and 0.8% less at -O, 1.5% less compiling T12707 at -O0 and 0.5% less
  at -O, 1.4% less compiling T783 at -O0 and 0.2% less at -O, and 1.9%
  less compiling T9961 at -O0, though less than 0.1% less at -O. Compiling
  !16269's ManyBasicBlocks at -O1 and -O2, the compiler allocates 3.0%
  less.
  
  Assisted-by: Claude Opus 5.5
  

• f9ea2550
  by Mikolaj Konarski at 2026-10-30T23:42:11+01:00

  Find the linear allocator's spill candidates in one fold
  
  Where no register of a vreg's class is free, allocRegsAndSpill_spill
  frees the register of another vreg: the first one that is in a register
  and in a stack slot, else the first one only in a register, among
  those it need not keep. It found them by filtering the whole assignment
  to the vregs in a register, deleting those to keep, listing the rest
  and searching the list twice. It now folds over the assignment once,
  keeping the first vreg of each kind, in the order the list had them.
  The generated code is the same.
  
  The compiler allocates 8.6% less compiling perf/compiler's T3294 at -O0
  and 3.9% less at -O, and 0.5% less compiling T12707 at -O0;
  its allocation compiling T783 and T9961 does not change. Compiling
  !16269's ManyBasicBlocks at -O1 and -O2, the compiler allocates 0.2%
  less.
  
  Assisted-by: Claude Opus 5.5
  

• b66792ba
  by Mikolaj Konarski at 2026-10-30T23:42:11+01:00

  Walk register assignments without listing them
  
  clobberRegs listed the whole assignment, for every instruction
  that writes a real register, to move the vregs that are in a clobbered
  register and in a stack slot to the slot only; it now folds
  over the assignment. joinToTargets_again listed the recorded assignment
  of a jump target and the current one, to compare them ignoring
  the formats; equalIgnoringFormats now compares the two maps themselves.
  The generated code is the same.
  
  The compiler allocates up to 0.07% less compiling perf/compiler's T3294,
  T12707, T783 and T9961 (T9961 at -O0). Compiling !16269's
  ManyBasicBlocks at -O1 and -O2, the compiler allocates 3.2% less.
  
  Assisted-by: Claude Opus 5.5
  

• 9d97aadc
  by Mikolaj Konarski at 2026-10-30T23:42:11+01:00

  Sort a procedure's blocks only where its first block is not first
  
  regAlloc sorted the linear allocator's blocks to keep the procedure's
  first block at the front; it now sorts them only where that block
  is not at the front already. The generated code is the same.
  
  The compiler allocates 0.09% less compiling perf/compiler's T3294
  at -O0, 0.3% less compiling T12707 at -O0 and 0.1% less at -O, 0.3% less
  compiling T783 at -O0 and 0.08% less at -O, and 0.5% less compiling
  T9961 at -O0.
  
  Assisted-by: Claude Opus 5.5
  

• fe8cd164
  by Mikolaj Konarski at 2026-10-30T23:42:11+01:00

  Compute the dying registers and the live-in map of liveness strictly
  
  liveness1 left, in each instruction's liveness, the registers read
  for the last time there and those written there that die at once
  as thunks, which the linear allocator forces at every instruction;
  livenessSCCs and livenessBlock likewise left the map of the registers
  live into each block, and each entry, to be computed later. They are now
  computed as the liveness pass goes. The generated code is the same.
  
  The compiler allocates 0.7% less compiling perf/compiler's T3294 at -O0
  and 0.3% less at -O, 0.7% less compiling T12707 at -O0 and 0.2% less
  at -O, 0.8% less compiling T783 at -O0 and 0.2% less at -O, and 0.8%
  less compiling T9961 at -O0.
  
  Assisted-by: Claude Opus 5.5
  

• e721d8ed
  by Mikolaj Konarski at 2026-10-30T23:42:11+01:00

  Skip the address registers x86's mkRU would drop
  
  regUsageOfInstr on x86 and x86-64 added every register an address names
  to an instruction's register lists, and mkRU then filtered out the ones
  the allocators do not manage, such as Sp's %rbp, Hp's %r12 and BaseReg's
  %r13, copying each list that held one: those of every access
  to the stack or the heap. An address's registers that mkRU would drop
  are now left out where they are added. This commit is a subset
  of Sylvain Henry's !16843, whose register usage DSL adds each register,
  an address's included, only where the allocators manage it.
  The generated code is the same.
  
  The compiler allocates 0.8% less compiling perf/compiler's T3294 at -O0
  and 0.3% less at -O, 0.4% less compiling T12707 at -O0 and 0.1% less
  at -O, 0.3% less compiling T783 at -O0, and 0.2% less compiling T9961
  at -O0.
  
  Assisted-by: Claude Opus 5.5
  

• d24feef5
  by Mikolaj Konarski at 2026-10-30T23:42:11+01:00

  List a CFG's edges once in block layout
  
  sequenceChain listed the edges of the CFG twice, once for the chains
  it builds and once for the edges left between them; it now lists them
  once. The generated code is the same.
  
  The compiler allocates 0.10% less compiling perf/compiler's T12707
  at -O, 0.07% less compiling T783, and 0.03% less compiling T3294; at -O0
  its allocation does not change. Compiling !16269's ManyBasicBlocks
  at -O1 and -O2, the compiler allocates 0.1% less.
  
  Assisted-by: Claude Opus 5.5
  

• cadde6f1
  by Mikolaj Konarski at 2026-10-30T23:42:11+01:00

  Build loopInfo's dominator map in one fold
  
  loopInfo's mkDomMap listed every block's dominators as pairs, each
  block's followed by those below it, and made a map of the list. It now
  inserts each block into the map as it walks the dominator tree, a change
  taken from Simon Jakobi's !16269 for GHC #27448; this commit is a subset
  of !16269, which makes the same change to mkDomMap but for the sets,
  below, and also adds the perf test ManyBasicBlocks. The sets stay
  as they were, but for the root's empty one, which goes: each block
  but the root maps to the blocks dominating it, itself included
  and the root left out, where !16269 leaves a block out of its own set;
  that part of !16269 is not taken, because it was found incorrect:
  no self loop would then count as a back edge, the case the commit
  counting self loops as loops fixes. loopInfo runs
  under -fcmm-static-pred, on at -O1 and -O2. The generated code
  is the same.
  
  At -O the compiler allocates 0.2% less compiling perf/compiler's T3294
  and T12707, 3.8% less compiling T783, and less than 0.01% less compiling
  T9961; at -O0, where loopInfo does not run, its allocation moves by less
  than 0.001%. Compiling !16269's ManyBasicBlocks, the compiler allocates
  27.4% less at -O1 and 27.3% less at -O2.
  
  Assisted-by: Claude Opus 5.5
  

• 7de9601b
  by Mikolaj Konarski at 2026-10-30T23:42:11+01:00

  Build no lists of results in calcFreqs
  
  calcFreqs, which static prediction runs for every procedure, built
  a list of results for each block's out-edges (forM in calcOutFreqs) and,
  for each block's predecessors, a list of Bools to test for irreducible
  flow and a list of probabilities to sum. It now uses forM_, anyM
  and a left fold from 0, which adds the probabilities in sum's order,
  so that the frequencies are the same, and so is the generated code.
  
  At -O the compiler allocates up to 0.10% less compiling perf/compiler's
  T3294, T12707, T783 and T9961 (T12707); at -O0, where static prediction
  is off, its allocation does not change. Compiling !16269's
  ManyBasicBlocks at -O1 and -O2, the compiler allocates 0.3% less.
  
  Assisted-by: Claude Opus 5.5
  

• 79d74f27
  by Mikolaj Konarski at 2026-10-30T23:42:11+01:00

  Give back edges no bonus where static prediction estimates the weights
  
  optHsPatterns raised every back edge of positive weight by backEdgeBonus
  (increaseBackEdgeWeight), after a depth-first search for them;
  under -fcmm-static-pred, on at -O1 and -O2, staticPredCfg then replaces
  the weights of the branches its heuristics cover with its predictions
  and estimates frequencies from them. The bonus is now left out there:
  increaseBackEdgeWeight moves out of optHsPatterns, and optimizeCFG calls
  it only where static prediction does not follow. The bonus counted only
  at the branches static prediction leaves alone, a heap or stack check's
  and those whose targets are all back edges, and at a two-way branch back
  into the procedure's entry, whose weights static prediction starts from,
  loopInfo counting no edge into the entry a back edge. Leaving it out
  of those as well changed no code measured. The generated code
  is the same on every program measured: perf/compiler's T3294, T12707,
  T783 and T9961 at -O0 and -O, and nofib's programs at -O2 and -O1, whose
  objects are identical.
  
  At -O the compiler allocates up to 0.15% less compiling perf/compiler's
  T3294, T12707, T783 and T9961 (T783); at -O0, where static prediction
  is off, its allocation does not change. Compiling !16269's
  ManyBasicBlocks at -O1 and -O2, the compiler allocates 0.4% less.
  
  Assisted-by: Claude Opus 5.5
  

• 7b0ddb07
  by Mikolaj Konarski at 2026-10-30T23:42:12+01:00

  In sccBlocks, look blocks up in the CFG, not in a set of them
  
  sccBlocks, in GHC.CmmToAsm.Reg.Liveness, built a set of every block
  of the CFG, which holds only reachable blocks, to keep the procedure's
  blocks that are in it; it now looks each block up in the CFG itself.
  The generated code is the same.
  
  The compiler allocates up to 0.24% less compiling perf/compiler's T3294,
  T12707, T783 and T9961 at -O0 (T783), and up to 0.06% less at -O (T783).
  Compiling !16269's ManyBasicBlocks at -O1 and -O2, the compiler
  allocates 0.1% less.
  
  Assisted-by: Claude Opus 5.5
  

• 39987749
  by Mikolaj Konarski at 2026-10-30T23:42:12+01:00

  Inline x86's takeRegRegMoveInstr
  
  takeRegRegMoveInstr, which the register allocators and the liveness pass
  call on every instruction they look for a register-to-register move in,
  built a Just and a pair for each move it found. Most callers take both
  apart at once. Inlined, it builds neither where its caller takes them
  apart. The generated code is the same.
  
  The compiler allocates up to 0.12% less compiling perf/compiler's T3294,
  T12707, T783 and T9961 at -O0 (T9961); at -O its allocation moves
  by 0.01% or less.
  
  Assisted-by: Claude Opus 5.5
  

• 3fdc8420
  by Mikolaj Konarski at 2026-10-30T23:42:12+01:00

  Make the linear allocator's last-resort register an FR method
  
  Where none of a vreg's preferences is free, firstFreeInOrder took
  the first free register, and on x86-64 the first in the order of Note
  [Register preferences in the linear allocator], the shared code testing
  the platform for it. That choice is now a method of the FR class,
  frFallbackReg, by default the first free register; on x86-64
  it is fallbackReg in GHC.CmmToAsm.Reg.Linear.X86_64, which takes R1's
  register from a constant rather than from globalRegMaybe at every call.
  The generated code is the same.
  
  The compiler allocates up to 0.07% less compiling perf/compiler's T3294,
  T12707, T783 and T9961 at -O0 (T3294), and up to 0.02% less at -O
  (T3294); it runs up to 0.04% fewer instructions (T3294 at -O0), 0.02%
  fewer compiling T3294 at -O and up to 0.01% fewer compiling the others.
  
  Assisted-by: Claude Opus 5.5
  

• 723ab07a
  by Mikolaj Konarski at 2026-10-30T23:42:12+01:00

  Swap the registers of a cyclic join fixup where one instruction can
  
  Where a jump's target has a recorded assignment, joinToTargets moves
  the vregs into it, and where the moves form a cycle, handleComponent
  spilled one source to its stack slot and reloaded it
  into its destination after the other moves: a store and a load,
  and a stack slot the vreg may not have had. The Instruction class now
  has mkRegRegSwapInstr, which gives an instruction that swaps two
  registers of a format where there is one, and by default Nothing; on x86
  and x86-64 it is xchg for the general-purpose registers. handleComponent
  now swaps a cycle's first source with its destination where it can,
  so that a cycle of n moves takes n - 1 swaps; it spills as before
  otherwise, as for floating-point and vector registers.
  
  The compiler's allocation compiling perf/compiler's T3294, T12707, T783
  and T9961 moves by less than 0.01% at -O0 and -O. Of nofib's programs
  only puzzle moves by more than 0.2% in instructions: it runs 0.5% fewer,
  and 0.7% fewer cycles. containers' sequence adjust.10, adjust.100
  and adjust.1000 run 0.58%, 0.30% and 0.16% fewer instructions and intmap
  fromListWith:randomDups:fusion 0.43% fewer, their cycles moving within
  the noise; vector's benchmarks move by less than 0.01%, and megaparsec's
  run 0.73% fewer (skipManyTill 3.9%, endBy1 2.3%), none more.
  
  Assisted-by: Claude Opus 5.5
  

• feee18f1
  by Mikolaj Konarski at 2026-10-30T23:42:12+01:00

  Predict branches into loop heads that only a heap or stack check makes
  
  staticBranchPrediction's loop exit heuristic, lehPredicts, says nothing
  about a branch into a loop head. A heap or stack check that fails calls
  the garbage collector, which returns to a block that jumps back
  to the check, and loopInfo counts that cycle as a loop; so in a loop
  that holds such a check, the check's block is a loop head,
  and the heuristic said nothing about the test that stays in the loop
  by branching to it. loopHeads now leaves out a head whose back edges all
  leave a block of coldBlocks, and the loop levels the heuristic compares
  count only the loops left: counting the others too would put a block
  that heads only such a cycle a level deeper than its siblings,
  so that the heuristic would predict any branch into it. The set
  is coldBlocks, not checkFailures: static prediction runs after register
  allocation, so the cycle can close from a block the allocator put after
  one that follows the failed check, which coldBlocks holds
  and checkFailures does not. loopInfo no longer counts loop levels
  (liLevels), which staticBranchPrediction now counts over the loops left,
  and loopLevels, which had no caller, goes. A back edge leaving
  a continuation that a call returns to as well as the garbage collector
  counts the same, so a loop closed through such a call loses its head
  too; telling the two apart moved no figure measured.
  
  Where it changes the layout, this saves cycles, not instructions:
  with the stay side predicted, the layout can let it fall through,
  a taken jump fewer an iteration, and a conditional jump is one
  instruction whether taken or not. Before the levels were limited,
  lookupGE3's loop in containers' lookupge-map took one jump an iteration
  instead of two, the tag test's jump backward in the layout to the heap
  check and then one out of the comparison, and GE Twan ran 2% to 11%
  fewer cycles at no more than 0.03% more instructions; limiting them
  leaves that loop's jumps as they were.
  
  Measured against the parent commit, on x86-64: the instructions
  of nofib's programs and of containers', vector's and megaparsec's
  benchmarks move by less than 0.01% in geometric mean. In cycles nofib's
  programs fell 0.01% in geometric mean with the heads left out and rose
  0.3% with the levels limited, single programs moving by up to 12% either
  way where unchanged code lands elsewhere: gcd's 4.7% rise comes
  from its bignum code, unchanged but placed 80 bytes later,
  and hartel/listcopy's 12% from code that a grown function moved.
  The compiler allocates 0.12% less compiling perf/compiler's T783 at -O,
  0.06% less compiling T12707, and less than 0.01% less compiling T3294
  and T9961; at -O0 its allocation moves by less than 0.001%.
  
  Assisted-by: Claude Opus 5.5
  

• a1a1f7d9
  by Mikolaj Konarski at 2026-10-30T23:42:12+01:00

  NCG: invert floating-point conditional branches too
  
  invertCondBranches turns a block's `jcc next; jmp other` into
  `jncc other` only where the condition comes from an integer
  comparison.  maybeInvertCond complements the condition on the flags,
  which nothing between the two jumps changes, so the swapped jumps take
  the same path for every outcome of a floating-point comparison too, an
  unordered one included, in each shape genCondBranch' emits for one.
  
  Of the 173 such pairs nofib's objects keep at -O2, 166 follow a
  ucomisd and go.  mandel2 runs 2.6% fewer instructions and smallpt 0.7%
  fewer; no other program whose code changes moves by 0.1%.
  
  Assisted-by: Claude Opus 5.5
  

• 30b05021
  by Mikolaj Konarski at 2026-10-30T23:42:12+01:00

  Assign literals after computed values at the end of a block
  
  GHC.Cmm.Sink emits the assignments it sinks no further at the end
  of a block, in their order. An assignment of a literal to a local
  register now goes after the later ones where each of those assigns,
  to another local register, a literal or the result of a machine
  operation that reads neither that register nor the literal's. A literal
  reads neither memory nor a register, and none of the assignments
  it passes reads or writes its register, so every value stays the same.
  
  Set first, a constant can take the register that a later value is
  to be in at the block's end, while the value's operands still hold
  the register the constant is to be in. In Data.Text's UTF-8 decoding,
  as inlined into megaparsec's benchmarks, the ASCII path sets the width,
  1, and then the character, the zero-extended byte, and jumps
  to the join, whose recorded assignment has the width in %r14
  and the character in %rbx. With the byte in %r14, the width took %rbx
  and the character %r14, and the join's fixup swapped them, an xchg
  a character. Now the byte is zero-extended into %rbx and the width set
  in %r14.
  
  A copy or an update in place keeps a literal before it: in a trial
  that let it pass them as well, the literal changed the registers
  of a join's recorded assignment in megaparsec's manyTill benchmark
  and of a loop head's in Text.Megaparsec.Stream's reachOffset, whose
  other predecessors then paid a move a character.
  
  Measured against the parent commit, on x86-64: megaparsec's benchmarks
  run 0.19% fewer instructions over those stable across runs (someTill
  1.06%, skipSomeTill 0.83%, skipSome 0.67%), none more. Of nofib's
  programs only cacheprof's and k-nucleotide's objects change, cacheprof's
  in the order of its instructions alone and k-nucleotide's
  in its registers, and none moves by as much as 0.2%; containers'
  and vector's benchmarks move by no more than their noise. The assembly
  of perf/compiler's T3294, T12707, T783 and T9961 at -O0 and -O
  is the same; at -O the compiler allocates up to 0.003% more compiling
  them (T12707) and 0.0001% more compiling !16269's ManyBasicBlocks at -O1
  and -O2; at -O0 its allocation does not change.
  
  Metric Decrease:
      CoOpt_Read
      ManyAlternatives
      ManyConstructors
      T12425
      T12707
      T13035
      T13056
      T13253
      T13379
      T13960
      T15164
      T15630
      T15630a
      T15703
      T18282
      T18698a
      T18698b
      T18730
      T1969
      T20049
      T20261
      T21839c
      T24471
      T26425
      T26989
      T3064
      T3294
      T4801
      T5030
      T5321FD
      T5321Fun
      T5631
      T6048
      T783
      T9198
      T9233
      T9630
  
  Assisted-by: Claude Opus 5.5
  

• 72f1199e
  by Mikolaj Konarski at 2026-10-30T23:42:12+01:00

  Document behaviour of the NCG's CFG, layout and register allocators
  
  Comments and documentation only, on behaviour the earlier commits do
  not change; the generated code is the same.
  
  Dead code elimination is off under -finfo-table-map (GHC #20428),
  so register allocation gets no CFG and none is kept after it: there
  is no static prediction and no chain layout under -fblock-layout-cfg.
  In GHC.CmmToAsm.Reg.Graph.SpillCost, a comment says that the block
  frequencies scale only the counts of uses and definitions, on which
  no spill choice depends.
  
  In GHC.CmmToAsm.CFG, Note [CFG Edge Weights] gave the default weight
  as 20k, where defaultWeights has 1000, and said that the false side
  of a regular branch is preferred, where both sides get the same weight
  and optHsPatterns' favourFewerPreds may prefer one by its predecessors,
  and that calls are ignored completely, where the layout leaves a call's
  edge out only while it builds chains and divides its weight by 64 when
  it merges them; it now also says that under -fcmm-static-pred
  the weights become estimated frequencies. Note [Layout relevant edge
  weights] in GHC.CmmToAsm.BlockLayout also said that calls are ignored,
  and now says how the layout treats them. Comments now say that edges
  of equal weight fall back on label order, which means nothing,
  and that where shortcutting redirects an edge onto one already there,
  one of them keeps its EdgeInfo and their weights are not summed;
  in GHC.CmmToAsm.BlockLayout, that allEdges' relevantWeight differs
  from directEdges'. Note [CFG based code layout] now says
  that the layout's loop analysis and mkGlobalWeights run for the layout
  only under -fcmm-static-pred, and the users' guide
  that -fcmm-static-pred works after register allocation, for the layout
  alone, and only on x86-64 without -finfo-table-map.
  
  In the linear allocator, Note [Unique order in the linear allocator]
  says which decisions take the order of the vregs' uniques as a ranking,
  the spill victim and the order in which saveClobberedTemps moves values
  out of clobbered registers, and that it orders joinToTargets' fixup
  moves. The comments that said deterministic code generation
  was not supported, which -fobject-determinism provides, now say, there
  and in the liveness pass and the graph allocator, whether the order
  matters. JoinToTargets' comment on cycles through memory now says
  that a vreg's slot changes where its format grows.
  In GHC.CmmToAsm.Reg.Liveness, the comment on the SCCs' order says
  that no block may fall through before allocation, and liveDieRead's
  haddock that at a branch it also holds the registers live
  into its targets only.
  
  Assisted-by: Claude Opus 5.5
  

28 changed files:

• compiler/GHC/Cmm/Sink.hs
• compiler/GHC/CmmToAsm.hs
• compiler/GHC/CmmToAsm/BlockLayout.hs
• compiler/GHC/CmmToAsm/CFG.hs
• compiler/GHC/CmmToAsm/Instr.hs
• compiler/GHC/CmmToAsm/Reg/Graph.hs
• compiler/GHC/CmmToAsm/Reg/Graph/Spill.hs
• compiler/GHC/CmmToAsm/Reg/Graph/SpillCost.hs
• compiler/GHC/CmmToAsm/Reg/Linear.hs
• compiler/GHC/CmmToAsm/Reg/Linear/Base.hs
• compiler/GHC/CmmToAsm/Reg/Linear/FreeRegs.hs
• compiler/GHC/CmmToAsm/Reg/Linear/JoinToTargets.hs
• compiler/GHC/CmmToAsm/Reg/Linear/State.hs
• compiler/GHC/CmmToAsm/Reg/Linear/X86_64.hs
• compiler/GHC/CmmToAsm/Reg/Liveness.hs
• compiler/GHC/CmmToAsm/Reg/Regs.hs
• compiler/GHC/CmmToAsm/X86.hs
• compiler/GHC/CmmToAsm/X86/CodeGen.hs
• compiler/GHC/CmmToAsm/X86/Instr.hs
• compiler/GHC/Data/Graph/Directed.hs
• compiler/GHC/Driver/Config/CmmToAsm.hs
• docs/users_guide/using-optimisation.rst
• rts/Weak.c
• testsuite/tests/codeGen/should_gen_asm/T24813.asm
• testsuite/tests/codeGen/should_gen_asm/bytearray-memcpy-unroll.asm
• testsuite/tests/codeGen/should_gen_asm/bytearray-memset-unroll.asm
• + testsuite/tests/regalloc/T27619.hs
• testsuite/tests/regalloc/all.T

The diff was not included because it is too large.