Efficient Symbolic Analysis for Optimizing Compilers

Robert A. van Engelen

Florida State University
`engelen@cs.fsu.edu`

ETAPS CC'2001 4/2/2001

Symbolic Analysis

Generalized induction variable recognition E.g. [Ammerguallat et al. 1990, Eigenmann et al. 1991, Haghighat et al. 1992, Singh & Hennessy 1992, Wolfe 1992]

Non-Linear & symbolic
data dependence analysis E.g. [Blume & Eigenmann 1995, Fahringer 1998] and many others...

Linear Induction Variable

Loop counter variable I

Variable with single update operation
DO ¯I = A, B ... J = J+H ...

where H is a loop-invariant expression

Generalized Induction Variable (giv)

GIV values form polynomial and geometric progressions through loop iterations

A GIV can have multiple update operations

GIVs can be coupled

DO ¯I = A, B ... J = J+K polynomial ... K = K+H linear ... J = J+1 2^nd update ... P = 2*P geometric ...

giv Recognition

GIV recognition amounts to finding the closed-form characteristic function c of a GIV:

c(n)=j(n)+r aⁿ

where

n is the iteration number

j is a polynomial

r and a are loop-invariant expressions

giv RecognitionExample

DO ¯I = 0, N ... J = J+K ... K = K+H ... J = J+1 ... P = 2*P ...

J

=

c_J(I)=J₀ + H * (I² - I)/2+ K₀ * I + 1
K

=

c_K(I)=K₀ + H * I
P

=

c_P(I)=P₀ * 2^I

J₀, K₀, and P₀ are initial values of J, K, and P; H is loop invariant

giv Recognition and Compiler
Optimizations

Induction variable recognition is important to

Data dependence analysis

Loop parallelization and unimodular loop transformations of non-rectangular loops

Loop transformations for data cache optimization, e.g. blocking

Performance estimation by counting number of iterations of non-rectangular loops

Parallelization of Perfect Benchmark^tm codes which contain a number of GIVs

givs and Data Dependence Analysis

¯ J = 0 K = 1 DO ¯I = 0, N S₁: J = J+K S₂: A[J] = B[K] S₃: K = K+2 S₄: B[2*I] = ... ENDDO

¯ J = 0 K = 1 DO ¯I = 0, N S₁: J = J+K S₂: A[I*(I+2)+1] = B[2*I+1] S₃: K = K+2 S₄: B[2*I] = ... ENDDO

GCD-test shows no dependence S₂ d₌ S₄

Parallelization by giv Substitution

J = 0 K = 1 DO ¯I = 0, N J = J+K A[J] = B[K] K = K+2 B[2*I] = ... ENDDO

DO ¯I = 0, N A[I*(I+2)+1] = B[2*I+1] B[2*I] = ... ENDDO

Elimination of GIV updates may enable loop parallelization and other optimizations

Haghighat's Symbolic Differencing

Detects GIVs in loops by differencing the values of each variable through symbolically executing the first m loop iterations and by using Newton's interpolating formula to find the closed form

DO ¯I = 0, N T = a a = b b = c+2*b-T+2 c = c+d d = d+I ENDDO

Symbolic Differencing(cont'd)

Problem: possibility of incorrect closed form when user sets m too low

For m=3: 3^rd order polynomial closed form
T = a+(d*i**3+(3*c-3*d+6)*i**2+(6*b-9*c+2*d-6)*i)/6

For m=5: 5^th order polynomial closed form
T = a+(i**5-10*i**4+(20*d+35)*i**3+(60*c-60*d+70)*i**2
+(120*b-180*c+40*d-96)*i)/120

No feedback of this polynomial truncation error for this example!

giv Recognition With Chains of
Recurrences

Safe method

Simple to implement

Efficient

Detects larger class of induction variables

Detects wrap-around variables

Detects conditional GIVs

Cannot detect GIVs from cyclic recurrences (these are very rare)

Cyclic RecurrencesExample

Cyclic recurrences are introduced by variable updates that involve some form of exchange

A = 1 B = -1 DO ¯I = 0, N T=A A=B B=T ... ENDDO

Closed form of T = c_T(I) = (-1)^I

Note: loop unrolling might help!

Chains of Recurrences

A chain of recurrences (CR) is a compact representation of

polynomials

(hyper)geometric series

factorials

trigonometric functions

combinations of these

[Bachmann 1994]

CR Notation

F_i={f₀,Ä₁,f₁,Ä₂,¼,Ä_k-1,f_k-1,Ä_k,f_k}_i

where

i spans the index space (i ³ 0)

f_j are loop-invariant expressions (0 £ j < k)

Ä_j=+ or Ä_j=*

f_k is a loop-invariant expression or a CR in i

CR Algebra

14 core rewrite rules on CRs

E+{f₀,+,f₁}_i

Þ

{E+f₀,+,f₁}_i

when E is loop invariant
E*{f₀,+,f₁}_i

Þ

{E*f₀,+,E*f₁}_i

when E is loop invariant
E*{f₀,*,f₁}_i

Þ

{E*f₀,*,f₁}_i

when E is loop invariant
:

:

CR term rewriting system is complete
(confluent and terminating)

CR Construction

CRs are constructed by applying rewrite rules from the CR algebra to expressions

Loop variable I=A..B is replaced by {A,+,1}_I

DO ¯I = A, B L = 2*I+H P = I*I-I Q = I*(I-1) R = 2**I

I

Þ

{A,+,1}_I
L = 2*I+H

Þ

2*{A,+,1}_I+H

Þ

{2*A+H,+,2}_I
P = I*I-I

Þ

{A²-A,+,2*A,+,2}_I
Q = I*(I-1)

Þ

{A²-A,+,2*A,+,2}_I
R = 2^I

Þ

{2^A,*,2}_I

giv Recognition Step 1

Obtain a SSA form of code with single scalar variable updates ordered such that each scalar variable has its def after all its uses

DO ¯I = A, B J = J+K K = K+H J = J+1 ...

DO ¯I = A, B J = J+K+1 K = K+H ...

giv Recognition Step 2

Find scalar variable updates

V = V+X

Þ

{V₀,+,X}_i
V = V-X

Þ

{V₀,+,-X}_i
V = V*X

Þ

{V₀,*,X}_i
V = V/X

Þ

{V₀,*,1/X}_i

where X is a loop-invariant expression or a CR

Replace all uses of V with the CR of V

DO ¯I = A, B K = {K₀,+,H}_I J = J+{K₀,+,H}_I+1 ...

DO ¯I = A, B K = {K₀,+,H}_I J = {J₀+1,+,K₀,+,H}_I ...

Induction Variable Substitution (ivs)

Apply CR inverse rules to obtain closed forms and normalize the loop

DO ¯I = A, B K = {K₀,+,H}_I J = {J₀+1,+,K₀,+,H}_I ...

J₀ = J K₀ = K DO ¯I = 0, B-A K = K₀+H*I J = J₀+(H*I*(I-1))/2+I*K₀+1 ...

ivs Algorithm

Programming model of algorithm in paper:
source-code level sequences, assignment, if-then-else, do-loop, while-loop

Analyzes loop hierarchies

Detects multivariate GIVs using multivariate CRs

Applies GIV recognition and IVS to the innermost loops first

ivs Worst-Case Complexity

O(k n log(n) m²)

where

k is the maximum loop nesting level

n is the length of the source code

m is the maximum polynomial order of GIVs

Wrap-Around Variables

J = M DO ¯I = M, N A[J] = B[K] J = I+1 K = J ENDDO

J₀ = M DO ¯I = 0, N-M A[¯{J₀-M,*,0}_I+{M, +, 1}_I] = B[{K-M,*,0}_I+{M,+,1}_I] ENDDO

DO ¯I = 0, N-M A[I+M]=B[(0**I)*(K-M)+I+M] ENDDO

No Closed Form

GIVs (polynomials and (hyper)geometric series) always have closed forms. We generate index array for induction variables with no closed form

DO ¯I = 1, N X[J] = ... J = J+K K = K*P P = P*4 ENDDO

A[0] = 0 DO ¯I = 1, N-1 A[I]=A[I-1]+(P**I)*(2**(I*(I-1))) ENDDO DO ¯I = 0, N-1 X[J+K*A[I]] = ... ENDDO

Loop Strength Reduction

Transformation from closed form to CR to induction variable update operations [Bachmann 1994]

CR of a closed form c(I) (0 £ I £ N) is

{f₀,Ä₁,f₁,Ä₂,¼,Ä_k-1,f_k-1,Ä_k,f_k}_I

cr₀ = f₀ cr₁ = f₁ : cr_k = f_k DO ¯I = 0, N c(I) = cr₀ cr₀ = cr₀Ä₁ cr₁ cr₁ = cr₁Ä₂ cr₂ : cr_k-1 = cr_k-1Ä_k cr_k ENDDO

Conclusions

GIV recognition method is safe

IVS algorithm is as powerful as symbolic differencing

IVS cannot handle cyclic recurrences

Implementation requires expression rewriting comparable to constant folding

CRs are normal forms for polynomials and geometric series

File translated from T_EX by T_TH, version 2.87.
On 10 Apr 2001, 13:38.