Restricted Permutation Trees: Construction

and Semantics?

Nandakumar Sankarany

Harold C. Grossman

D. E. Stevenson

Jeffrey B. Green

Technical Report TR 94-115

Computer Science Department

Clemson University

October 25, 1994

Abstract

We present a new intermediate program representation form, the Restricted Permutation Trees (RPT), and describe its construction and semantics via rewrite rules along with proofs of correctness. The RPT inherently reflects most of the legal permutations of the statements in a program and hence is suited to optimizations that involve code reordering. We illustrate the use of RPTs for performing Register Allocation and Instruction Scheduling, the performance of both of which depends upon the ordering of statements in a program.

1 Introduction

The performance of many compiler optimizations depends upon the order of statements in the program. For example, the data cache hit rates are high if the statements in a program are ordered such that locality of variable accesses are high. Pipeline stalls are reduced if the statements in a program are ordered such that adjacent instructions are as independent as possible. In every case, the ordering of statements should ensure that the semantics of the program are maintained. We deal with such a set of order-dependent optimizations.

In the best case, we should examine every one of the possible permutations of the statement orderings and pick the best one for each optimization. Clearly this is non-polynomial. Fortunately,

?Submitted to the ACM SIGPLAN Workshop on Intermediate Representations, to be held in conjunction with POPL, January 1995
yAuthor's eMail addresses: fnandu,grossman,steve,[email protected]. Mail drop: Computer Science Departmant, R.C Edwards Hall, Clemson University, SC 29631-1906