Advanced copy propagation for arrays
Peter Vanbroekhoven, Gerda Janssens, Maurice Bruynooghe, Henk Corporaal, Francky Catthoor · ACM SIGPLAN Notices · 2003
The focus of this paper is on a data flow-transformation called advanced copy propagation. After an array is assigned, we can, under certain conditions, replace a read from this array by the righthand side of the assignment. If so, the intermediate assignment can be skipped. In case it becomes dead code, it can be eliminated. Where necessary we distinguish between the different elements of arrays as well as the different runtime instances of statements, allowing us to do propagation over global loop and condition scopes. We have formalized two basic operations: non-recursive propagation that operates on two statements and recursive propagation that operates on one statement. A global algorithm uses these two operations to do propagation on code involving any number of statements. Running our prototype implementation on some multimedia kernels shows that we can get a decrease in memory acesses between 22% and 43%.