ABSTRACT
This chapter presents the classical approach to partial redundancy elimination (PRE) which involves a bidirectional formulation of data flows. Data flow analysis originated with what was later termed as “bit vector” data flow frameworks. The chapter provides an alternative approach to PRE which minimizes lifetimes by separating safety and desirability constraints. The term “bit vector” arises from the fact that not only can the data flow information be represented using bit vectors, it can also be computed using bit vector operations alone. Data flow analysis views computation of data through expressions and transition of data through assignments to variables. Data flow analyses of other program entities such as composite expressions, array variables, pointer variables and statement numbers. Global data flow information is associated with the entry and exit points of a basic block. Transitive effects of undefined variables are captured by possibly uninitialized variables analysis.
