Interprocedural Partial Redundancy Elimination and Its Application To Distributed Memory Compilation

Partial Redundancy Elimination (PRE) is a general scheme for suppressing partial redundancies which encompasses traditional optimizations like loop invariant code motion and redundant code elimination. In this paper we address the problem of performing this optimization interprocedurally. We use interprocedural partial redundancy elimination for placement of communication and communication preprocessing statements while compiling for distributed memory parallel machines. 1 Introduction Partial Redundancy Elimination (PRE) is a well known technique for optimizing code by suppressing partially redundant computations. It encompasses traditional optimizations like invariant code motion and redundant computation elimination. It is widely used in optimizing compilers for performing common subexpression elimination and strength reduction. More recently, it has been used for more complex code placement tasks like placement of communication statements while compiling for parallel machines [12,..