Výběr instrukce - Instruction selection
Ve výpočetní techniky , výběr instrukce je etapa kompilátoru backend, která mění její střední úrovni meziproduktu reprezentace (IR) do IR nízké úrovně, kde každé operace přímo odpovídá na pokyn k dispozici na cílovém počítači. V typickém kompilátoru předchází výběr instrukcí jak plánování instrukcí, tak alokaci registrů ; proto jeho výstupní IR má nekonečnou sadu pseudoregistrů (často známých jako dočasné ) a může stále - a obvykle je - předmětem optimalizace kukátka . Jinak se velmi podobá cílovému strojovému kódu , bajtkódu nebo jazyku sestavení .
Například pro následující sekvenci infračerveného kódu střední úrovně
t1 = a t2 = b t3 = t1 + t2 a = t3 b = t1
dobrá instrukční sekvence pro architekturu x86 je
MOV EAX, a
XCHG EAX, b
ADD a, EAX
Komplexní průzkum výběru instrukcí viz.
Makro expanze
Nejjednodušší přístup k výběru instrukcí je známý jako expanze makra nebo generování interpretačního kódu . Selektor instrukcí rozšiřujících makro pracuje se srovnáváním šablon přes IR na střední úrovni. Po shodě je provedeno odpovídající makro s použitím odpovídající části IR jako vstupu, který vydává příslušné cílové instrukce. Makro expanzi lze provést buď přímo na textové reprezentaci infračerveného paprsku střední úrovně, nebo lze infračervený paprsek nejprve transformovat na grafické znázornění, které se poté prochází hloubkou napřed. V druhém případě se šablona shoduje s jedním nebo více sousedními uzly v grafu.
Pokud není cílový počítač velmi jednoduchý, generování makra izolovaně obvykle generuje neefektivní kód. Aby se toto omezení zmírnilo, kompilátoři, kteří používají tento přístup, jej obvykle kombinují s optimalizací kukátka, aby nahradili kombinace jednoduchých pokynů složitějšími ekvivalenty, které zvyšují výkon a snižují velikost kódu. Toto se nazývá Davidson-Fraserův přístup a v současnosti se používá v GCC .
Krycí graf
Dalším přístupem je nejprve transformovat IR střední úrovně na grafické znázornění a poté graf zakrýt pomocí vzorů . Vzor je šablona, která odpovídá části grafu a lze ji implementovat pomocí jediné instrukce poskytnuté cílovým počítačem. Cílem je pokrýt graf tak, aby byly minimalizovány celkové náklady na vybrané vzory, kde náklady obvykle představují počet cyklů potřebných k provedení instrukce. U stromových grafů lze nejnižší krytí nákladů najít v lineárním čase pomocí dynamického programování , ale u DAG a plnohodnotných grafů se problém stává NP-úplným, a proto se nejčastěji řeší buď chamtivými algoritmy nebo metodami z kombinatorické optimalizace.
Strategie nejnižšího společného jmenovatele
Nejmenší společný jmenovatel strategie je výběr instrukce technika používaná na platformách, kde existují instrukce procesoru doplňkový aby spustitelné programy kompatibilní s celou řadou počítačů. Podle strategie nejnižšího společného jmenovatele je výchozím chováním kompilátoru sestavení pro nejnižší společnou architekturu. Použití libovolného dostupného rozšíření procesoru je ve výchozím nastavení vypnuto, pokud není výslovně zapnuto přepínači příkazového řádku.
Použití strategie s nejnižším společným jmenovatelem znamená, že se ve výchozím nastavení nepoužívají doplňkové instrukce a schopnosti procesoru .