Looptransformasjoner

Looptransformasjoner er teknikker innen kompilering og programvareoptimering som omorganiserer iterasjonsløkken i et program for å forbedre ytelse, vanligvis ved bedre cache- og dataplatseringsatferd, økt vektoriseringsmulighet eller større parallellisering, uten å endre programmets semantikk.

Grunnleggende for slike transformasjoner er avhengighetsanalyse av data mellom ulike iterasjoner. Bare transformasjoner som bevarer disse avhengighetene er trygge, og dermed har de samme resultater som opprinnelig kode. I praksis brukes ofte formelle modeller og avhengighetsgraf for å vurdere hva som er tillatt.

Blant de vanligste transformasjonene er: løkkeutveksling, som bytter rekkefølgen på to nestede løkker for å forbedre lokalitet eller å gjøre videre optimisering mulig; løkke-samslåing, som fusjonerer nabo-løkker til én løkke for å redusere loop-overhead og bedre datasirkulasjon; løkke-fisjon, som deler en kompleks løkke i mindre løkker for bedre parallellisering eller spesialisering; blokking eller tiling, som deler iterasjonsrommet i mindre blokker for å utnytte cache bedre og lettere parallellisere; løkke-uunngring, som øker antallet iterasjoner per løkkeiteration for å redusere overhead og muliggjøre vektoriseringskriterier; peeling, som håndterer kanttilfeller uten å påvirke resten av løkken; og løke-kollapsing, som slår sammen flere nestede løkker til én enkel løkke.

Anvendelser finnes i høyytelsesberegninger og vitenskapelige beregninger, og moderne optimaliseringskompilatorer (for eksempel til LLVM, GCC eller kompilatorer i HPC-miljøer) bruker disse transformasjonene som del av automatisert inspeksjon og generering av effektive kodebaner. Begrensninger inkluderer ofte økt kodekompleksitet, registertrykk og situasjoner der data ikke passer cache eller hvor avhengigheter gjør noen transformasjoner ufordelaktige.