Disambiguation, Correctness and Flow-Analysis Issues for Trace Scheduling Compilers

Trace scheduling is a global compaction technique for transforming sequential programs into parallel code. When this investigation began, trace scheduling was unimplemented and many serious questions of appropriateness and effectiveness needed to be solved. This paper addresses questions of its applicability to ordinary programming for Very Long Instruction Word machines. We developed practical methods of exploiting this parallelism (e.g. memory anti-aliasing). To justify and better understand the dynamic interaction between trace scheduling and anti-aliasing, we designed a more formal model in which we proved the correctness of trace scheduling and showed that it terminates. This in turn allowed us to analyze our flow information requirements. Finally we addressed the problem of ambiguous memory references which cannot be resolved at compile time