Nov. 25 2023 @ PAAP2023

Global Store Statement Aggregation
Tomohiro Sano and Yasunobu Sumikawa
Takushoku University, JapanBackgroundmain(){a[i]=x;b[i]=y;a[i+1]=z;}
C programCache memory

Main memory

Backgroundmain(){
a[i]=x;b[i]=y;a[i+1]=z;}
C programCache memory

Main memory

Backgroundmain(){a[i]=x;b[i]=y;a[i+1]=z;}
C program

Write missCache memory

Main memory

Backgroundmain(){
a[i]=x;b[i]=y;a[i+1]=z;}
C program

Write missCache memory

Main memory

ObjectiveWe propose a novel code motion algorithm named Global Store statement Aggregation (GSA)

main(){a[i]=x;b[i]=y;a[i+1]=z;}main(){b[i]=y;a[i]=x;a[i+1]=z;}Related Works
Aggregating load statements has been proposedmain(){
x=a[i];y=b[i];z=a[i+1];}

main(){
x=a[i];z=a[i+1];
y=b[i];}

Y. Sumikawa and M. Takimoto, “Global load instruction aggregation based on code motion,” in 5th PAAP, 2012, pp. 149–156.

Algorithm overview
1.
2.
3.

Traversing the control flow graph (CFG) with reverse topological sort order
Sinking each store statement extended by PDE
Array reference analysis during the sinking

Algorithm overview
1.
2.
3.

Traversing the control flow graph (CFG) with reverse topological sort order
Sinking each store statement extended by PDE
Array reference analysis during the sinking

CFG creation

main(){
a[i]=x;b[i]=y;a[i+1]=z;}
C programa[i]=xb[i]=za[i+1]=z
CFG (control ﬂow graph)

CFG traversinga[i]=xb[i]=za[i+1]=zCFG traversinga[i]=xb[i]=za[i+1]=zCFG traversinga[i]=xb[i]=za[i+1]=zAlgorithm overview
1.
2.
3.

Traversing the control flow graph (CFG) with reverse topological sort order
Sinking each store statement extended by PDE
Array reference analysis during the sinking

PDE
PDE eliminates partially dead variables
12

x=1+2

Killing the ﬁrst
deﬁnition
4x=1

This variable is not used if the control
ﬂow executes the read path.
This variable is called partially dead.

3print(x)J. Knoop, O. Ruthing, and B. Steffen, “Partial dead code elimination,” ¨ SIGPLAN Not., vol. 29, no. 6, pp. 147–158, jun 1994.

Sinking of PDE
12x=1
x=1+2

3

Fully dead4print(x)x=1

Elimination
12

x=1+2

4

3print(x)x=1

PDE extension
GSA performs PDE sinking only for store statements
1Not targetof GSA

2

x=1+2
4

a[i]=13print(x)Target of GSA

Algorithm overview
1.
2.
3.

Traversing the control flow graph (CFG) with reverse topological sort order
Sinking each store statement extended by PDE
Array reference analysis during the sinking

Array reference analysis
1.
2.

Forwarding analysis
Backwarding analysis

Array reference analysis
Analyzing
1.
2.

Forwarding analysis
Backwarding analysis

1a[i]=x2b[i]=z3a[i+1]=zFind a same array after diff. arrayArray reference analysis
Analyzing
1.
2.

Forwarding analysis
Backwarding analysis

Inconsistentregion1a[i]=x2b[i]=z3a[i+1]=z

1. Find a different array

Sinking using the array reference analysis
12b[i]=z2’a[i]=x3a[i+1]=zSink

Evaluation
Compiler: COINSBaseline: PDE
Benchmark program: distcountsort (Count), radixsort (Radix), and arrays(Array)
CPU: Intel Corei7-11700 2.50GHz
OS: Ubuntu 64bit
L1d and Li1 cache memories: 384 KiB, 256 KiB
L2 cache memory: 4 MiB
L3 cache memory: 16 MiB

Results | Total number of cache misses
A. PDE

B. GSA(A-B) / ACount

25,48025,266

0.84%

Radix

6,662

6,575

1.31%

Array

18,362

17,343

5.55%

Results | Number of last level cache store misses
A. PDE

B. GSA(A-B) / ACount

17,91817,8890.16%

Radix1,2001,171

2.42%

Array

11,661

11,4501.81%

Results | Execution time
A. PDE

B. GSA(A-B) / ACount

1,564.8

1,342

14.24%

Radix

566.6

562.5

0.72%

Array

551.5

531.5

3.63%

Conclusion●●We proposed a novel code motion based cache optimization algorithm, named global store statement
aggregation (GSA).
GSA aims at reducing write misses by making store statements accessing the same array continuously.

Future Work●we will examine moving all store and load statements at the same time to enhance GSA.
Thank you for your attention!