Mikolaj Konarski pushed to branch wip/T27981-ncg-mystery-box at Glasgow Haskell Compiler / GHC Commits: b0d94513 by Mikolaj Konarski at 2026-10-30T21:52:24+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 - - - - - 06019180 by Mikolaj Konarski at 2026-10-30T21:52:24+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 - - - - - 20a652f1 by Mikolaj Konarski at 2026-10-30T21:52:24+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 - - - - - 4bbe9e2b by Mikolaj Konarski at 2026-10-30T21:52:24+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. 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 - - - - - 3dcb24ff by Mikolaj Konarski at 2026-10-30T21:52:25+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 - - - - - f46658d9 by Mikolaj Konarski at 2026-10-30T21:52:25+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 - - - - - 3a4dea7b by Mikolaj Konarski at 2026-10-30T21:52:25+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 - - - - - ffab28ae by Mikolaj Konarski at 2026-10-30T21:52:25+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 - - - - - a488481e by Mikolaj Konarski at 2026-10-30T21:52:25+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 - - - - - a84819e7 by Mikolaj Konarski at 2026-10-30T21:52:25+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 - - - - - ebd61d50 by Mikolaj Konarski at 2026-10-30T21:52:25+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 - - - - - 4b860f97 by Mikolaj Konarski at 2026-10-30T21:52:25+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 - - - - - 871ea92a by Mikolaj Konarski at 2026-10-30T21:52:25+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 - - - - - 608e3d36 by Mikolaj Konarski at 2026-10-30T21:52:25+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 - - - - - 24c5c4af by Mikolaj Konarski at 2026-10-30T21:52:25+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 - - - - - 09f830a0 by Mikolaj Konarski at 2026-10-30T21:52:25+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 - - - - - 2b9d671f by Mikolaj Konarski at 2026-10-30T21:52:25+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 - - - - - d4d079d5 by Mikolaj Konarski at 2026-10-30T21:52:25+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. 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 - - - - - bcca783a by Mikolaj Konarski at 2026-10-30T21:52:25+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 - - - - - fd37a97d by Mikolaj Konarski at 2026-10-30T21:52:25+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 - - - - - ebf9020e by Mikolaj Konarski at 2026-10-30T21:52:25+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 - - - - - 8bdaa266 by Mikolaj Konarski at 2026-10-30T21:52:26+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 - - - - - ac40a273 by Mikolaj Konarski at 2026-10-30T21:52:26+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 - - - - - 899aa414 by Mikolaj Konarski at 2026-10-30T21:52:26+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 - - - - - 0ac8b4f2 by Mikolaj Konarski at 2026-10-30T21:52:26+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 - - - - - f38746f9 by Mikolaj Konarski at 2026-10-30T21:52:26+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 - - - - - b38d6edd by Mikolaj Konarski at 2026-10-30T21:52:26+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 - - - - - f014d570 by Mikolaj Konarski at 2026-10-30T21:52:26+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 - - - - - a9e5d246 by Mikolaj Konarski at 2026-10-30T21:52:26+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 - - - - - 24241240 by Mikolaj Konarski at 2026-10-30T21:52:26+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 - - - - - ef3f2406 by Mikolaj Konarski at 2026-10-30T21:52:26+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. 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 - - - - - 4c746ecb by Mikolaj Konarski at 2026-10-30T21:52:26+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 - - - - - dd0909b2 by Mikolaj Konarski at 2026-10-30T21:52:26+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 - - - - - c7e5ca9e by Mikolaj Konarski at 2026-10-30T21:52:26+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 - - - - - a1d57352 by Mikolaj Konarski at 2026-10-30T21:52:26+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 - - - - - 08f2ea0e by Mikolaj Konarski at 2026-10-30T21:52:26+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 - - - - - d2356773 by Mikolaj Konarski at 2026-10-30T21:52:26+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 - - - - - bbcb4e9e by Mikolaj Konarski at 2026-10-30T21:52:27+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 - - - - - fbd94f54 by Mikolaj Konarski at 2026-10-30T21:52:27+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 - - - - - d709b7df by Mikolaj Konarski at 2026-10-30T21:52:27+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 - - - - - 0361b6d9 by Mikolaj Konarski at 2026-10-30T21:52:27+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. View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/compare/cbc71e72fbc65640be317c1cc018bc4... -- View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/compare/cbc71e72fbc65640be317c1cc018bc4... You're receiving this email because of your account on gitlab.haskell.org. Manage all notifications: https://gitlab.haskell.org/-/profile/notifications | Help: https://gitlab.haskell.org/help