Scalable Array SSA
and Array Dataflow Analysis
Silvius Rus
Guobin He
Lawrence Rauchwerger

SSA Program Representation: Scalarsv = 100
Original If (x>0) Thencodev = 100
EndIfPrint v

v1 = 100If (x>0) Thenv2 = 100
EndIf
SSA v = φ(v , v )321
Form Print v
3v = 100If (x>0) Thenv = 50
EndIf
If (x>0) Then
Print vEndIfv1 = 100
If (x>0) Thenv2 = 50
EndIfv3 = γ(x>0, v2, v1)
If (x>0) ThenPrint v3
EndIf

Originalcode

GatedSSA
Form2Constant Propagation using SSA
BeforeCPSSA
Form

AfterCPv1 = 100If (x>0) Thenv2 = 100
EndIf
v3 = φ(v2, v1)
Print v3

v1 = 100If (x>0) Thenv2 = 100
EndIf
v3 = φ(100, 100)
Print 100v1 = 100If (x>0) Thenv2 = 50
EndIf
v3 = γ(x>0, v2, v1)
If (x>0) Then
Print v3
EndIf
v1 = 100If (x>0) Thenv2 = 50
EndIf
v3 = γ(x>0, 50, 100)If (x>0) Then
Print 50
EndIf

BeforeCPGatedSSA
Form

After 3CPArray SSA: Motivation
Subroutine set (A, k, v)
A(k) = v
End

Simple Solution
Treat arrays asscalars
A1(1) = 100
A2(2) = 200
Print A2(1)CallSites

Loops

Too conservative!
Must considersubscripts!

Control...
Callset(A, 1,0)
If (x>0) Then
Call set(A, 2,1)
EndIf
Do j = 3, 10
Call set(A, j,3)
Call set(A, j+8, 4)
EndDoPrint A(1) + A(5)If (x>0) Then
Print A(2)EndIf4

Previous Work

Analytical array subregion-based dataflow frameworks– Scalable and expressive– No standard form = harder to use than SSA; sometimes biased
towards a particular analysis technique– Triolet CC ’86, Callahan SC ’87, Gross SPE ’90, Burke TOPLAS ’90, Feautrier
IJPP ’91, Maydan SPPL ’93, Tu LCPC ’93, Pugh TR ’94, Gu SC ’95, Hall SC’95, Creusillet LCPC ’96, Haghighat TOPLAS ’96, Hoeflinger ’98, Moon ICS’98, Wonnacott LCPC ’00

Element-wise data flow information as Array SSA by enumeration– More accurate than treating arrays as scalars, easy to use– Complexity proportional to the dimension of the array = not scalable– At compile-time, only applicable to constant subscript expressions– Knobe SPPL ’98, Sarkar SAS ’98
5Array SSA Desiderata

Analytical and explicit
data flow information
at array element level6

Array Data Flow: Partial Kills
x1 = 100

A1(1) = 100
DEF(A1) = {1}A2(2) = 200
KILL(A2) = {2}Print A2(1)USE(A2) = {1}x2 = 200
Print x2

Disjoint

Scalars:

Array SSA:

The use of x2 may be replaced withthe value defined by x2 because it
kills all its reaching definitions (x1)

The use of A2 may not be replacedwith the value defined by A2 because it
does not kill A1(1)But how do we get from A2 to A1?
7

Use-Def Chains: δ Nodes

A(1) = …
A(2) = …
A(1) = …
Print A(1)Print A(2)Print A(10)A1(1) = …
[A2, {1}] = δ(A0, [A1,{1}])A3(2) = …
[A4, [1:2]] = δ(A0, [A2,{1}], [A3,{2}])
A5(1) = …
[A6, [1:2]] = δ(A0, [A4,{2}], [A5,{1}])Print A6(1)Print A6(2)Print A6(10)A5A5A0A4A3

Array SSA Use-Def Chains
Just like scalar SSA + compare access regions8δ Nodes: Formal Definition…
…
Abefore(…)= …
Acurrent(…)= …
[Atotal,@At]= δ(Aundef, [Abefore,@Abt], [Acurrent,@Act])@Abt ∩ @Act = ∅@At = @Abt @Act
• @Abt is the array region defined before Acurrent and reaching Atotal• @Abt = @Abefore - @Acurrent• @Act is the array region defined by Acurrent and reaching Atotal• @Act = @Acurrent• Need analytical representation for @ sets!

9Expressing @ Sets:
Array Region Representation
Subroutine set (A, k, v)
A(k) = v
End...
Callset(A, 1,0)
If (x>0) Then
Call set(A, 2,1)
EndIfDo j = 3, 10
Call set(A, j,3)
Call set(A, j+8, 4)
EndDoPrint A(1) + A(5)If (x>0) Then
Print A(2)EndIfx>0
x>0set(k=2)

2

kj=3,10∪set(k=j)set(k=j+8)

kk[3:18]

10

Run-time Linear Memory Access
Descriptor (RT_LMAD)
T = { LMAD, ∩, ∪, −, (, ), #, x, Θ, Gate, Recurrence, Call Site}
N = { RT_LMAD }S = RT_LMAD
P = { RT_LMAD → LMAD | (RT_LMAD)
RT_LMAD → RT_LMAD ∩ RT_LMAD
RT_LMAD → RT_LMAD ∪ RT_LMAD
RT_LMAD → RT_LMAD − RT_LMAD
RT_LMAD → RT_LMAD # Gate
RT_LMAD → RT_LMAD x Recurrence
RT_LMAD → RT_LMAD Θ Call Site }LMAD = Start + [Stride1:Span1, Stride2:Span2, ...]

1. Closed form for references in If blocks, Do loops, sequence of blocks
2. Closed with respect to set operations: difference, union
3. Control-flow sensitive and interprocedural

11δ Nodes for aSequence of Blocks
Callset(A, 1,0)

If (x>0) ThenCall set(A, 2,EndIf1)

Subroutine set (A, k, v)
A(k) = v
End

Do j = 3, 10
Call set(A, j,3)
Call set(A, j+8, 4)
EndDo12δ Nodes for a
Sequence of Blocks
Callset(A1, 1,0)

If (x>0) Then
Call set(A3, 2,EndIf1)

Subroutine set (A, k, v)
A(k) = v
End

Do j = 3, 10
Call set(A5, j,3)
Call set(A5, j+8, 4)
EndDo13δ Nodes for a
Sequence of Blocks
Callset(A1, 1,If (x>0) Then
Call set(A3, 2,EndIf0)

1)

Do j = 3, 10Call set(A5, j,3)
Call set(A5, j+8, 4)
EndDo

Subroutine set (A, k, v)
A(k) = v
End[A2, {1}] = δ(A0,[A1, {1}])[A4, {1}∪((x>0)#{2})] = δ(A0,[A2, {1}],[A3, (x<0)#{2}])[A6, {1}∪((x>0)#{2})∪[3:18]] = δ(A0,[A4, {1}∪((x>0)#{2})],[A5, [3:18])

Print A6(100)Print A6(3)Print A6(11)Print A6(1)A0
A5A5A214

Definitions in Loops: µ nodes
Do j = 3, 10
Call set(A, j,3)

Call set(A, j+8, 4)
EndDo

Print A(j-2)
Print A(3)Print A(11)

?
?
?

15

Definitions in Loops: µ nodes
Do j = 3, 10
Call set(A1, j,3)

Call set(A3, j+8, 4)
EndDo[A2, {j}] = δ(A5,[A1, {j}])[A4, {j}∪{j+8}] = δ(A5,[A2, {j}],[A3, {j+8}])16

Definitions in Loops: µ nodes
Do j = 3, 10
Call set(A1, j,3)

Call set(A3, j+8, 4)
EndDo[A5, [3:j-1]∪[11:j+7]] = µ(A0,[A1, [ 3:j-1]],[A3, [11:j+7]])[A2, {j}] = δ(A5,[A1, {j}])[A4, {j}∪{j+8}] = δ(A5,[A2, {j}],[A3, {j+8}])[A6, [3:18]] = δ(A0,[A5, [3:18]])

Print A4(j-2)
Print A6(3)Print A6(11)

?
?
?

17

Definitions in Loops: µ nodes
Do j = 3, 10
Call set(A1, j+2, 3)Call set(A3, j+8, 4)
EndDo[A5, ?] = µ(A0,[A1, ?],[A3, ?])[ A , @ A ] = µ ( A , [ A , @ A ], [ A , @ A ],..., [ A , @ A ]),nnn01n12n2mm

wherej −1j −1@ A ( j ) = U [@ A (i ) − (Kill (i ) ∪ U Kill (l ))],nkki =1sm

l = i +1am

Kill = U @ A , Kill = U @ Ash = k +1

hah =1h@Akn(j) is the array region defined by Ak that reaches An
upon entry to iteration j.

18

Definitions in Loops:
Iteration Vectors
Iteration vectors– For a given array element, which iteration wrote it last?
– Important for: Forward substitution, Last value assignment– Not important for: Privatization– Hard to express when loop nests span subroutines

We express the dual entity– For a given iteration j, what is the set of all memory
locations last defined at j?
– Example: Last value assignmentCompute LVA(j) as set of memory locations

19

Subroutine set (A, k, v)
A(k) = v
End

Control Dependence: π nodes
If (x>0) Then
Call set(A, 2, 1)
EndIf
If (x>0) Then
Print A(2)EndIf
Original code

If (x>0) Then
[A1,∅]= π(x>0, A0)
Call set(A2, 2, 1)[A3, {2}]= δ(A1, [A2, {2}])EndIf[A4, (x>0)#{2}] = δ(A0,[A3,(x>0)#{2}])If (x>0) Then
[A5,∅] = π(x>0, A4)
Print A5(2)EndIfArray SSA

• Different from SSA: new name without definition.
• Essential to control-sensitive data flow analysis.

20

Reaching Definitions
Given:– An SSA name Au– An array region Use– A block to limit the search, GivenBlock

Find [A1, R1], [A2, R2], …[An, Rn], [⊥,R0], such that:– Use = R1 ∪ R2 ∪ … ∪ Rn ∪ R0
– Rj ∩ Rk = φ, ∀1 ≤ j ≠ k ≤ n– Region Rk was defined by Ak, k=1,n– R0 was not defined within GivenBlockExample:– Privatization: GivenBlock = loop body, prove R0 empty
21

Reaching Definitions[Atotal,@At]= δ(Aundef, [Abefore,@Abt], [Acurrent,@Act])
Algorithm SearchRD(At, Use, GivenBlock)
If (At not in GivenBlock) Then Report [⊥, Use]; Stop
If (At not an SSA gate) Then Report [At, Use]; Stop
Call SearchRD(Abefore, @Abt ∩ Use, Block(Abefore))
Call SearchRD(Acurrent, @Act ∩ Use, Block(Acurrent))
Call SearchRD(Aundef, Use - @At, Block(Aundef))
Special operations:• Expand descriptors at µ gates• Add conditionals at π gates22

Array Constant Propagation


Array constant collection– Attach values to reaching definitions sets
– Unite sets with the same constant valueConstant propagation and substitution– Full loop unrolling– Subprogram specialization– Aggressive dead code elimination

23

Constant Collection
Intraprocedural collection:– Use the SearchRD algorithm– Attach values to reaching definitions sets
– Collect values from assignment statements– Unite sets with same attached valueInterprocedural collection– Push available sets at call sites– Collect intraprocedurally– Return collected constants back to calling context

24

Constant Propagation


Full loop unrolling– Compute iteration count based on available constant values

Subprogram specialization– Constants available only at certain call sites



Aggressive dead code elimination– Dead branches– Dead assignments– Multiplications with 0 or 1; additions of 025

Experimental Results
QCD2
173.APPLU
048.ORA
107.MGRID

Intel PC:
HP 9000/R390:
IBM Regatta P690:
SGI Origin 3800:

Pentium PA-RISC
14.0%
17.4%
20.0%
4.6%
1.5%
22.8%
12.5%
8.9%

Pentium 4 (520)
PA-8200
Power 4MIPS R1400

Power
12.8%
16.4%
11.9%
6.4%

2.8 GHz
200 MHz
1.3 GHz
500 MHzMIPS
15.5%
10.5%
20.6%
12.8%

26

Conclusions


Array SSA
– Analytical, scalable, explicit element-level data flow information

Reaching definitions algorithm– Find matching array subregion for each reaching definition of a useArray constant propagation– Speedup on four benchmark programs



Future uses: array privatization, dependence, liveness27