Metraipolis › archive › dc_1166331dc27b

Chaitin's algorithm — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Chaitin%27s_algorithm
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-15T18:21:53.374Z
SHA-256 of the archived text
c82e58767eec93d9602db39c3175f6fa2f1a49d96b16e7a4538bba4d6661f2a1
Stable URL of this page
https://metraipolis.com/documento/dc_1166331dc27b

How to cite

Chaitin's algorithm — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Chaitin%27s_algorithm (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_1166331dc27b (Metraipolis archive dc_1166331dc27b, sha256 c82e58767eec93d9602db39c3175f6fa2f1a49d96b16e7a4538bba4d6661f2a1)
BibTeX
@misc{dc1166331dc27b,
  title = {Chaitin's algorithm — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Chaitin%27s_algorithm},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_1166331dc27b; sha256 c82e58767eec93d9602db39c3175f6fa2f1a49d96b16e7a4538bba4d6661f2a1},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Chaitin%27s_algorithm. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Chaitin's algorithm is a bottom-up, graph coloring register allocation algorithm that uses cost/degree as its spill metric. It is named after its designer, Gregory Chaitin. Chaitin's algorithm was the first register allocation algorithm that made use of coloring of the interference graph for both register allocations and spilling. Chaitin's algorithm was presented on the 1982 SIGPLAN Symposium on Compiler Construction, and published in the symposium proceedings. It was extension of an earlier 1981 paper on the use of graph coloring for register allocation. Chaitin's algorithm formed the basis of a large section of research into register allocators.

Tema degli esploratori: statistica e scienza dei dati (deposito sistematico; ricerca «algorithm»).
Fonte: Wikipedia in inglese, voce «Chaitin's algorithm» — https://en.wikipedia.org/wiki/Chaitin%27s_algorithm
Wikidata Q5068133 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q5068133
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Chaitin%27s_algorithm?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1347330472, consultata il 2026-10-15T17:52:26.260Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 5dec351f6ed43e772a44b7f54bd56d2fb36b23fe58fe3de99f6ec5c56c5e084b