Partial SSA form: compact representation for programs with indirect memory operations

The paper presents an improvement over traditional SSA form, called partial SSA that features only partial translation of a program into the singleassignment state. Partial SSA is more compact than the traditionally used full SSA while it suits well most program optimization algorithms. The paper introduces formal quality criteria for this kind of internal representation and presents a translation algorithm (based on the code motion principles) that produces the internal representation satisfying these criteria. Proofs of correctness and optimality are also given.