Jak uprościć arytmetyczne wyrażenie w stylu C zawierające zmienne podczas generowania kodu?

Question

Próbuję zoptymalizować ocenę wyrażeń w kompilatorze.

Wyrażenia arytmetyczne mają styl litery C i mogą zawierać zmienne. Mam nadzieję uprościć wyrażenia tak bardzo, jak to możliwe.

Na przykład (3+100*A*B+100)*3+100 można uprościć do 409+300*A*B.

Jest to głównie zależne od prawa rozdzielczego, prawa asocjacyjnego i prawa przemiennego.

Główną trudnością, jaką napotykam, jest łączenie tych praw arytmetycznych z tradycyjnymi algorytmami oceny stosu.

Czy ktoś może podzielić się doświadczeniami związanymi z tym lub podobnymi problemami w kontekście budowania kompilatora?

Answer 1

Zastosuj constant folding w połączeniu z redukcją siły podczas przebiegu generowania kodu kompilacji. Większość tekstów kompilatora zapewni algorytm do implementacji tego.

Answer 2

Kompilatory zazwyczaj mają pewne wewnętrzne reguły normalizacji, takie jak "stałe po lewej stronie". Oznacza to, że a + 3 zostanie przekształcony w , ale nie na odwrót.

W przykładzie (3+100*A*B+100)*3+100 by znormalizować do (3+100+(100*A*B))*3+100. Teraz jest jasne, aby zoptymalizować 3+100.

Inna transformacja może być a*C1+C2 w (a+(C2/C1))*C1 pod warunkiem, że C1 isą stałe. Intuicyjnie normalizuje to "dodawanie przed pomnożeniem".

Te normalizacje nie są optymalizacjami. Zamierzeniem jest głównie łączenie stałych grup, więc stałe fałdowanie jest bardziej skuteczne.