Efficient method of computing static single assignment form

Abstract

Recently, static single assignment form and the control dependence graph have been proposed to represent data flow and control flow properties of programs. Each of these previously unrelated techniques lends efficiency and power to a useful class of program optimizations. Although both of these structures are attractive, the difficulty of their construction and their potential size have discouraged their use. The authors present a new algorithm that efficiently computes these data structures for arbitrary control flow graphs. They also give analytical and experimental evidence that they are usually linear in the size of the original program. This paper thus presents strong evidence that these structures can be of practical use in optimization.