engineering/java-topology
1
0
Fork 0
Code Issues Pull requests Projects Releases Packages Wiki Activity Actions
java-topology/tools/tickets/defects/ghc-0003.md
russell@unturf.com db29a08762 undefect. CWE-407 — 92 sites, 42 ecosystems 
B&W print-friendly diagrams + tinkerpop-0001 + wave-3 proof sections.
Squash of 94 local commits onto remote master.
2026-03-26 19:48:18 -04:00

1.2 KiB
Raw Permalink Blame History

id repo severity status created
ghc-0003 ghc HIGH PATCHED 2026-03-23

Defect

File: compiler/GHC/Data/Graph/Ops.hs:637 Pattern: elem color neighbourColors in register allocator graph coloring Complexity: O(deg²) per function Language: Haskell

Description

GHC's register allocator uses graph coloring to assign registers to virtual registers. At line 637, the coloring algorithm checks whether a candidate color is already used by a neighbor via elem color neighbourColors, scanning a list. Since this check is performed for each color candidate for each neighbor of each node, the cost per function is O(deg²) where deg is the average node degree in the interference graph.

Fix

Replace: elem color neighbourColors With: color `S.member` neighbourColorSet Data structure change: neighbourColors: [Color] → neighbourColorSet: Set Color

Work required

  • Patch in defects/ghc/patch/
  • Unit test — asserts exact operation counts before/after (in defects/ghc/unit/)
  • Integration test (in defects/ghc/integration/)
  • Benchmark — before/after on V=100,200,400,800 (in defects/ghc/bench/)
  • White paper section