A gyakori részkifejezések eltávolítása ( eng. Common subexpression elimination vagy CSE) egy olyan fordítóoptimalizálás , amely olyan számításokat keres a programban , amelyeket a szóban forgó szakaszban többször is végrehajtanak, és eltávolítja a második és az azt követő azonos műveleteket, ha lehetséges és hatékony . Ez az optimalizálás adatfolyam-elemzést igényelredundáns számítások megtalálásához, és alkalmazásakor szinte mindig javítja a program végrehajtási idejét [1] .
Egy programban lévő részkifejezést akkor nevezünk közös részkifejezésnek , ha van még egy ilyen részkifejezés, amely mindig az adott előtt kerül kiértékelésre, és az operandusok nem változnak a kiértékelések között. Például az alábbi példában a b * c kifejezés egy általános részkifejezés.
E definíció alapján a közös részkifejezések eltávolítása olyan transzformáció , amely kiküszöböli a közös részkifejezések ismételt kiértékelését, és helyettesíti azokat az első kiértékelés után tárolt érték használatával. A vizsgált példában azonban lehetetlen a közös részkifejezést azonnal lecserélni az a változó értékére d kiszámításakor, mert ez a változó a szóban forgó számítások között változhat.
Vegye figyelembe a következő kódrészletet:
a = b * c + g ; d = b * c * d_ _A következő átalakítás vonatkozik rá:
tmp = b * c ; a = tmp + g ; d = tmp * d ;amely akkor lesz hatásos, ha az új "tmp" változó írásának és többszöri olvasásának teljes ideje kevesebb, mint a "b * c" kifejezés kiértékelésére fordított teljes idő, minden alkalommal, amikor az előfordul a kódban.
Ennek az optimalizálásnak két típusa van:
Mindkét optimalizálás adatfolyam-elemzésen alapul, melynek során a kifejezés elérhetősége a program minden pontján meghatározásra kerül.
Az optimalizáló alkalmazás az elérhető kifejezések elemzésén alapul . Egy kifejezés x + yelérhető a pprogram egy pontján, ha: [2]
Az átalakítás hatékonyságát elsősorban az határozza meg, hogy az új "tmp" változó írásának és több leolvasásának teljes ideje kevesebbnek bizonyul, mint a "b * c" kifejezés kiértékelésére fordított teljes idő, minden alkalommal, amikor az a változóban előfordul. kód. A gyakorlatban számos egyéb tényező is befolyásolja a végső hatékonyságot, különösen a változók regiszterek közötti eloszlása .
Egyszerű esetekben, mint például a fent tárgyalt esetben, az aritmetikai kifejezések számításainak megkettőzése megszűnik. Ez az optimalizálás a fordító belső reprezentációja szempontjából a legjelentősebb, például tömb indexek számításakor, ahol a kézi optimalizálás nagyon nehéz vagy lehetetlen. Egyes programozási nyelvekben lehetőség van sok azonos számítás elkészítésére. Megjelenhetnek például a C nyelv makrói , amelyek a forráskódban nem ugyanazokat a kifejezéseket alkotják, de miután az előfeldolgozó általi feldolgozás során a makró nevét lecserélték egy programutasítássorozatra, megjelenhetnek ilyenek.
Az optimalizálás globális alkalmazása esetén további kritériumok befolyásolják a hasznot. Például figyelembe kell venni az alapblokkok végrehajtási számlálóit, mivel a kifejezéskiértékelések statikus számának csökkentésével növelhető a dinamikus szám, ami negatívan befolyásolja a programban végrehajtott műveletek számát. Ez oda vezet, hogy a PRE (partial redundancia elimination) osztályhoz kapcsolódó fordított optimalizálás előnyös lehet.