Reconstructing the Types of Stack-Machine Codes

It is frequently needed to compile stack-machine codes into register-machine codes. One important optimization in such compilers is reducing the stack access overhead. But an effective mapping of stack values into registers is not straightforward. In this article, we present a formal yet effective technique of inferring the two types of each stack value. We infer the type of a stack value when it is pushed (push-type) and the type when it is used (pop-type). These two type information is safely estimated across the basic blocks by a global data-flow analysis. Using this type information, we can safely use as many typed registers as possible in storing stack values. We implemented our analysis for a real compiler and its experiments show that the speed-up is 5 % to 24%. 1 Problem and Our Approach It is frequently needed to compile stack-machine codes into register-machine codes [ATCL+98, Ert96, TvSKS83]. Stack-machine codes are used widely as intermediate languages, while most computers are register machines. One important optimization in such compilers is reducing the stack access overhead. Stack