Snížení síly - Strength reduction
v konstrukce kompilátoru, snížení síly je optimalizace kompilátoru kde jsou drahé operace nahrazeny ekvivalentními, ale levnějšími operacemi.[1] Klasický příklad redukce síly převádí „silné“ násobení uvnitř smyčky na „slabší“ doplňky - něco, co se často vyskytuje v adresování polí. (Cooper, Simpson & Vick 1995, str. 1)
Mezi příklady snížení pevnosti patří:
- nahrazení násobení ve smyčce sčítáním
- nahrazení umocnění ve smyčce násobením
Analýza kódu
Většina času provádění programu se obvykle utratí v malé části kódu (tzv. A hot spot ) a tento kód je často uvnitř smyčky, která se provádí znovu a znovu.
Kompilátor používá metody k identifikaci smyček a rozpoznávání charakteristik hodnot registrů v těchto smyčkách. Pro snížení síly kompilátor zajímá:
- Loop invariants: hodnoty, které se nemění v těle smyčky.
- Indukční proměnné: hodnoty, které jsou iterovány pokaždé smyčkou.
Smyčkové invarianty jsou v podstatě konstanty uvnitř smyčky, ale jejich hodnota se může změnit i mimo smyčku. Indukční proměnné se mění o známá množství. Výrazy jsou relativní k určité smyčce. Když jsou smyčky vnořené, může být indukční proměnnou ve vnější smyčce smyčka neměnná ve vnitřní smyčce.
Snížení síly hledá výrazy zahrnující invariant smyčky a indukční proměnnou. Některé z těchto výrazů lze zjednodušit. Například násobení invariantu smyčky C
a indukční proměnná i
C = 7;pro (i = 0; i < N; i++){ y[i] = C * i;}
lze nahradit postupnými slabšími přírůstky
C = 7;k = 0;pro (i = 0; i < N; i++){ y[i] = k; k = k + C;}
Příklad snížení síly
Níže je uveden příklad, který sníží sílu všech smyčkových multiplikací, které vznikly při výpočtech adres indexujících pole.
Představte si jednoduchou smyčku, která nastaví pole na matice identity.
pro (i = 0; i < n; i++){ pro (j = 0; j < n; j++) { A[i,j] = 0.0; } A[i,i] = 1.0;}
Mezilehlý kód
Kompilátor bude tento kód zobrazovat jako
0010 ; pro (i = 0, i 0020 ; {0030 R1 = #0 ; i = 00040 G0000:0050 zatížení r2, n ; i 0060 cmp R1, r20070 bge G000100800090 ; pro (j = 0; j 0100 ; {0110 r3 = #0 ; j = 00120 G0002:0130 zatížení r4, n ; j 0140 cmp r3, r40150 bge G000301600170 ; A [i, j] = 0,0;0180 zatížení r7, n0190 r8 = R1 * r7 ; vypočítat dolní index i * n + j0200 r9 = r8 + r30210 r10 = r9 * #8 ; vypočítat adresu bytu0220 fr3 = #0.00230 fstore fr3, A[r10]02400250 r3 = r3 + #1 ; j ++0260 br G00020270 ; }0280 G0003:0290 ; A [i, i] = 1,0;0300 zatížení r12, n ; vypočítat dolní index i * n + i0310 r13 = R1 * r120320 r14 = r13 + R10330 r15 = r14 * #8 ; vypočítat adresu bytu0340 fr4 = #1.00350 fstore fr4, A[r15]03600370 ; i ++0380 R1 = R1 + #10390 br G00000400 ; }0410 G0001:
To vyjadřuje dvourozměrné pole A jako jednorozměrné pole velikosti n * n, takže kdykoli kód na vysoké úrovni vyjadřuje A [x, y], bude interně A [(x * n) + y] pro všechny dané platné indexy x a y.
Mnoho optimalizací
Kompilátor začne provádět mnoho optimalizací - nejen snížení síly. Výrazy, které jsou ve smyčce konstantní (invariantní), budou zvednutý ze smyčky. Konstanty lze načíst mimo obě smyčky - například registry s plovoucí desetinnou čárkou fr3 a fr4. Uznání, že některé proměnné se nemění, umožňuje sloučení registrů; n je konstantní, takže r2, r4, r7, r12 lze zvednout a sbalit. Společná hodnota i * n se počítá v (zvednutých) r8 a r13, takže se sbalí. Nejvnitřnější smyčka (0120-0260) byla snížena z 11 na 7 mezilehlých pokynů. Jediným násobením, které zůstane v nejvnitřnější smyčce, je vynásobení řádku 0210 číslem 8.
0010 ; pro (i = 0, i 0020 {0030 R1 = #0 ; i = 00050 zatížení r2, n0130 ; náklad r4, n zabit; použijte r20180 ; náklad r7, n zabit; použijte r20300 ; zatížení r12, n zabito; použijte r20220 fr3 = #0.00340 fr4 = #1.00040 G0000:0060 cmp R1, r2 ; i 0070 bge G000100800190 r8 = R1 * r2 ; vypočítat dolní index i * n0310 ; r13 = r1 * r2 zabit; použijte r8; vypočítat dolní index i * n0090 ; pro (j = 0; j 0100 {0110 r3 = #0 ; j = 00120 G0002:0140 cmp r3, r2 ; j 0150 bge G000301600170 ; A [i, j] = 0,0;0200 r9 = r8 + r3 ; vypočítat dolní index i * n + j0210 r10 = r9 * #8 ; vypočítat adresu bytu0230 fstore fr3, A[r10]02400250 r3 = r3 + #1 ; j ++0260 br G00020270 }0280 G0003:0290 ; A [i, i] = 1,0;0320 r14 = r8 + R1 ; vypočítat dolní index i * n + i0330 r15 = r14 * #8 ; vypočítat adresu bytu0350 fstore fr4, A[r15]03600370 ; i ++0380 R1 = R1 + #10390 br G00000400 }0410 G0001:
Je třeba provést více optimalizací. Registr r3 je hlavní proměnná v nejvnitřnější smyčce (0140-0260); ve smyčce se pokaždé zvýší o 1. Register r8 (which is invariant in the insideermost loop) is added to r3. Místo použití r3 může kompilátor vyloučit r3 a použít r9. Smyčku lze místo r3 = 0 až n-1 ovládat pomocí r9 = r8 + 0 až r8 + n-1. To přidá čtyři instrukce a zabije čtyři instrukce, ale uvnitř smyčky je o jednu instrukci méně.
0110 ; r3 = číslo 0 zabito; j = 00115 r9 = r8 ; nový úkol0117 r20 = r8 + r2 ; nový limit0120 G0002:0140 ; cmp r3, r2 zabito; j 0145 cmp r9, r20 ; r8 + j 0150 bge G000301600170 ; A [i, j] = 0,0;0200 ; r9 = r8 + r3 zabito; vypočítat dolní index i * n + j0210 r10 = r9 * #8 ; vypočítat adresu bytu0230 fstore fr3, A[r10]02400250 ; r3 = r3 + # 1 zabito; j ++0255 r9 = r9 + #1 ; nová proměnná smyčky0260 br G0002
Nyní je r9 proměnnou smyčky, ale interaguje s vynásobením číslem 8. Zde musíme provést nějaké snížení síly. Násobení 8 může být sníženo na několik po sobě jdoucích přírůstků 8. Nyní uvnitř smyčky nejsou žádné násobení.
0115 r9 = r8 ; nový úkol0117 r20 = r8 + r2 ; nový limit0118 r10 = r8 * #8 ; počáteční hodnota r100120 G0002:0145 cmp r9, r20 ; r8 + j 0150 bge G000301600170 ; A [i, j] = 0,0;0210 ; r10 = r9 * # 8 zabit; vypočítat adresu bytu0230 fstore fr3, A[r10]02400245 r10 = r10 + #8 ; síla snížena násobit0255 r9 = r9 + #1 ; proměnná smyčky0260 br G0002
Registry r9 a r10 (= 8 * r9) nejsou oba potřebné; r9 lze ve smyčce eliminovat. Smyčka má nyní 5 pokynů.
0115 ; r9 = r8 zabit0117 r20 = r8 + r2 ; omezit0118 r10 = r8 * #8 ; počáteční hodnota r100119 r22 = r20 * #8 ; nový limit0120 G0002:0145 ; cmp r9, r20 zabit; r8 + j 0147 cmp r10, r22 ; r10 = 8 * (r8 + j) <8 * (r8 + n) = r220150 bge G000301600170 ; A [i, j] = 0,0;0230 fstore fr3, A[r10]02400245 r10 = r10 + #8 ; síla snížena násobit0255 ; r9 = r9 + # 1 zabito; proměnná smyčky0260 br G0002
Vnější smyčka
Zpět na celý obrázek:
0010 ; pro (i = 0, i 0020 {0030 R1 = #0 ; i = 00050 zatížení r2, n0220 fr3 = #0.00340 fr4 = #1.00040 G0000:0060 cmp R1, r2 ; i 0070 bge G000100800190 r8 = R1 * r2 ; vypočítat dolní index i * n0117 r20 = r8 + r2 ; omezit0118 r10 = r8 * #8 ; počáteční hodnota r100119 r22 = r20 * #8 ; nový limit0090 ; pro (j = 0; j 0100 {0120 G0002:0147 cmp r10, r22 ; r10 = 8 * (r8 + j) <8 * (r8 + n) = r220150 bge G000301600170 ; A [i, j] = 0,0;0230 fstore fr3, A[r10]02400245 r10 = r10 + #8 ; síla snížena násobit0260 br G00020270 }0280 G0003:0290 ; A [i, i] = 1,0;0320 r14 = r8 + R1 ; vypočítat dolní index i * n + i0330 r15 = r14 * #8 ; vypočítat adresu bytu0350 fstore fr4, A[r15]03600370 ; i ++0380 R1 = R1 + #10390 br G00000400 }0410 G0001:
Ve vnější smyčce, která zvyšuje r1, jsou nyní čtyři násobení. Registr r8 = r1 * r2 na 0190 lze snížit sílu nastavením před vstupem do smyčky (0055) a jejím zvýšením o r2 ve spodní části smyčky (0385).
Hodnotu r8 * 8 (na 0118) lze snížit silou inicializací (0056) a přidáním 8 * r2 k ní, když se r8 zvýší (0386).
Registr r20 je inkrementován invariantem / konstantou r2 pokaždé přes smyčku na 0117. Po zvýšení je vynásoben 8, aby se vytvořil r22 na 0119. Tuto multiplikaci lze snížit přidáním 8 * r2 pokaždé skrz smyčku .
0010 ; pro (i = 0, i 0020 {0030 R1 = #0 ; i = 00050 zatížení r2, n0220 fr3 = #0.00340 fr4 = #1.00055 r8 = R1 * r2 ; nastavit počáteční hodnotu pro r80056 r40 = r8 * #8 ; počáteční hodnota pro r8 * 80057 r30 = r2 * #8 ; přírůstek pro r400058 r20 = r8 + r2 ; zkopírováno z 01170058 r22 = r20 * #8 ; počáteční hodnota r220040 G0000:0060 cmp R1, r2 ; i 0070 bge G000100800190 ; r8 = r1 * r2 zabit; vypočítat dolní index i * n0117 ; r20 = r8 + r2 zabit - mrtvý kód0118 r10 = r40 ; síla snížila výraz na r400119 ; r22 = r20 * # 8 zabit; síla snížena0090 ; pro (j = 0; j 0100 {0120 G0002:0147 cmp r10, r22 ; r10 = 8 * (r8 + j) <8 * (r8 + n) = r220150 bge G000301600170 ; A [i, j] = 0,0;0230 fstore fr3, A[r10]02400245 r10 = r10 + #8 ; síla snížena násobit0260 br G00020270 }0280 G0003:0290 ; A [i, i] = 1,0;0320 r14 = r8 + R1 ; vypočítat dolní index i * n + i0330 r15 = r14 * #8 ; vypočítat adresu bytu0350 fstore fr4, A[r15]03600370 ; i ++0380 R1 = R1 + #10385 r8 = r8 + r2 ; snížení síly r8 = r1 * r20386 r40 = r40 + r30 ; síla snížit výraz r8 * 80388 r22 = r22 + r30 ; snížení pevnosti r22 = r20 * 80390 br G00000400 }0410 G0001:
Poslední násobení
To ponechává dvě smyčky pouze s jednou operací násobení (v 0330) ve vnější smyčce a bez násobení ve vnitřní smyčce.
0010 ; pro (i = 0, i 0020 {0030 R1 = #0 ; i = 00050 zatížení r2, n0220 fr3 = #0.00340 fr4 = #1.00055 r8 = R1 * r2 ; nastavit počáteční hodnotu pro r80056 r40 = r8 * #8 ; počáteční hodnota pro r8 * 80057 r30 = r2 * #8 ; přírůstek pro r400058 r20 = r8 + r2 ; zkopírováno z 01170058 r22 = r20 * #8 ; počáteční hodnota r220040 G0000:0060 cmp R1, r2 ; i 0070 bge G000100800118 r10 = r40 ; síla snížila výraz na r400090 ; pro (j = 0; j 0100 {0120 G0002:0147 cmp r10, r22 ; r10 = 8 * (r8 + j) <8 * (r8 + n) = r220150 bge G000301600170 ; A [i, j] = 0,0;0230 fstore fr3, A[r10]02400245 r10 = r10 + #8 ; síla snížena násobit0260 br G00020270 }0280 G0003:0290 ; A [i, i] = 1,0;0320 r14 = r8 + R1 ; vypočítat dolní index i * n + i0330 r15 = r14 * #8 ; vypočítat adresu bytu0350 fstore fr4, A[r15]03600370 ; i ++0380 R1 = R1 + #10385 r8 = r8 + r2 ; snížení síly r8 = r1 * r20386 r40 = r40 + r30 ; síla snížit výraz r8 * 80388 r22 = r22 + r30 ; snížení pevnosti r22 = r20 * 80390 br G00000400 }0410 G0001:
Na řádku 0320 je r14 součtem r8 a r1 a r8 a r1 se ve smyčce zvyšují. Registr r8 je naražen pomocí r2 (= n) a r1 je naražen pomocí 1. Následně je r14 naražen o n + 1 pokaždé přes smyčku. Poslední násobení smyčky v 0330 lze snížit sílu přidáním (r2 + 1) * 8 pokaždé skrz smyčku.
0010 ; pro (i = 0, i 0020 {0030 R1 = #0 ; i = 00050 zatížení r2, n0220 fr3 = #0.00340 fr4 = #1.00055 r8 = R1 * r2 ; nastavit počáteční hodnotu pro r80056 r40 = r8 * #8 ; počáteční hodnota pro r8 * 80057 r30 = r2 * #8 ; přírůstek pro r400058 r20 = r8 + r2 ; zkopírováno z 01170058 r22 = r20 * #8 ; počáteční hodnota r22005A r14 = r8 + R1 ; zkopírováno z 0320005B r15 = r14 * #8 ; počáteční hodnota r15 (0330)005C r49 = r2 + #1005D r50 = r49 * #8 ; síla snížila přírůstek0040 G0000:0060 cmp R1, r2 ; i 0070 bge G000100800118 r10 = r40 ; síla snížila výraz na r400090 ; pro (j = 0; j 0100 {0120 G0002:0147 cmp r10, r22 ; r10 = 8 * (r8 + j) <8 * (r8 + n) = r220150 bge G000301600170 ; A [i, j] = 0,0;0230 fstore fr3, A[r10]02400245 r10 = r10 + #8 ; síla snížena násobit0260 br G00020270 }0280 G0003:0290 ; A [i, i] = 1,0;0320 ; r14 = r8 + r1 zabit; mrtvý kód0330 ; r15 = r14 * # 8 zabit; síla snížena0350 fstore fr4, A[r15]03600370 ; i ++0380 R1 = R1 + #10385 r8 = r8 + r2 ; snížení síly r8 = r1 * r20386 r40 = r40 + r30 ; síla snížit výraz r8 * 80388 r22 = r22 + r30 ; snížení pevnosti r22 = r20 * 80389 r15 = r15 + r50 ; snížení síly r15 = r14 * 80390 br G00000400 }0410 G0001:
Je toho ještě hodně. Konstantní skládání rozpozná, že r1 = 0 v preambuli, takže několik instrukcí se vyčistí. Registr r8 se ve smyčce nepoužívá, takže může zmizet.
Dále se r1 používá pouze k ovládání smyčky, takže r1 může být nahrazen jinou indukční proměnnou, jako je r40. Kam jsem šel 0 <= i Použití redukce síly operátora matematické identity nahradit pomalé matematické operace rychlejšími operacemi. Výhody závisí na cílovém CPU a někdy na okolním kódu (což může ovlivnit dostupnost dalších funkčních jednotek v CPU). Indukční proměnná nebo rekurzivní redukce síly nahradí funkci nějaké systematicky se měnící proměnné jednodušším výpočtem s použitím předchozích hodnot funkce. V procedurální programovací jazyk to by platilo pro výraz zahrnující proměnnou smyčky a v deklarativní jazyk to by platilo pro argument a rekurzivní funkce. Například, se stává Zde upravená rekurzivní funkce f′ trvá druhý parametr z = 3 ** x, což umožňuje nahradit nákladný výpočet (3 ** x) levnějším (3 * z). Tento článek je založen na materiálu převzatém z Zdarma online slovník výpočetní techniky před 1. listopadem 2008 a začleněno pod "licencování" podmínek GFDL, verze 1.3 nebo novější.0010 ; pro (i = 0, i
Další operace snižování pevnosti
Původní výpočet Výpočet náhrady y = x / 8 y = x >> 3 y = x * 64 y = x << 6 y = x * 2 y = x << 1 y = x * 15 y = (x << 4) - x y = x / 10 (kde x je typu uint16_t) y = ((uint32_t) x * (uint32_t) 0xCCCD) >> 19) y = x / π (kde x je typu uint16_t) y = (((uint32_t) x * (uint32_t) 0x45F3) >> 16) + x) >> 2) Indukční proměnná (sirotek)
F X = ... (3 ** X) ... (F (X + 1)) ...
F X = F' X 1 kde F' X z = ... z ... (F' (X + 1) (3 * z)) ...
Viz také
Poznámky
Snížení síly.
-3 / 2
hodnotí na -1
, zatímco -3 >> 1
hodnotí na -2
. V tomto případě tedy překladač nemůže optimalizovat dělení dvěma nahrazením bitovým posunem.Reference