Optimal code motion: Theory and practice

J Knoop, O Rüthing, B Steffen - ACM Transactions on Programming …, 1994 - dl.acm.org
J Knoop, O Rüthing, B Steffen
ACM Transactions on Programming Languages and Systems (TOPLAS), 1994dl.acm.org
An implementation-oriented algorithm for lazy code motion is presented that minimizes the
number of computations in programs while suppressing any unnecessary code motion in
order to avoid superfluous register pressure. In particular, this variant of the original
algorithm for lazy code motion works on flowgraphs whose nodes are basic blocks rather
than single statements, since this format is standard in optimizing compilers. The theoretical
foundations of the modified algorithm are given in the first part, where t-refined flowgraphs …
An implementation-oriented algorithm for lazy code motion is presented that minimizes the number of computations in programs while suppressing any unnecessary code motion in order to avoid superfluous register pressure. In particular, this variant of the original algorithm for lazy code motion works on flowgraphs whose nodes are basic blocks rather than single statements, since this format is standard in optimizing compilers. The theoretical foundations of the modified algorithm are given in the first part, where t-refined flowgraphs are introduced for simplifying the treatment of flow graphs whose nodes are basic blocks. The second part presents the “basic block” algorithm in standard notation and gives directions for its implementation in standard compiler environments.
ACM Digital Library