We have written an optimising compiler for a typeless, imperative, modular programming language. The optimiser, which works on a 3-address intermediate representation generated from the source program, uses some novel techniques described in this thesis. The techniques are universally applicable, although some are particularly useful in typeless compilation. We present a new register allocation and assignment scheme. Unlike traditional "colouring" allocators, our method separates the problem into distinct allocation and assignment phases. The former is achieved by using an iterative process to extend a local (within basic blocks) allocation method to the global (across basic blocks) domain. This obviates the need for a sophisticated assignment algorithm; we show how to use simple heuristics to assign registers after allocation. We also present a simple method for identifying loops in a program's intermediate representation and assigning loop nesting levels. Unlike traditional methods, this does not rely on the concept of flowgraph dominators, and is able to deal sensibly with irreducible flowgraphs and "unstructured" loops that interlock or partially overlap. The major part of the thesis concerns value range analysis. Based on the theoretical framework of abstract interpretation, we describe an analysis of the intermediate code that predicts safe approximations to the run-time value ranges of variables and memory used by the program being compiled. To be useful in compiling a typeless language, this analysis must be able to handle values of different kinds (integers, pointers, function addresses, etc.) We show how we can subsume some traditional optimisation techniques, such as constant propagation, into more powerful methods that take advantage of value range information to optimise a wider variety of cases. We also show how this information can be used to recover most of the benefits of types, without sacrificing the flexibility of typelessness. Besides the above, value range analysis allows a number of optimisations that were heretofore impossible. Many of these are improvements to register allocation; we investigate better treatments for variables that can be accessed by address. We also describe a method of removing memory accesses by allowing variables that are simultaneously live to share registers, and suggest a similar scheme for values stored in memory. Finally, we show how the results of value range analysis can be shared across different program modules and different compiler runs. The method used is powerful enough to be useful, but simple enough to integrate with old code that cannot be recompiled. Inter-modular optimisation can be transparent to the user, improving the results of value range analysis within a module without altering its functionality; or it can be visible, optimising modules with respect to each other.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:624938 |
| Date | January 1998 |
| Creators | Fourniotis Pavlatos, Panayis |
| Contributors | Richards, Martin |
| Publisher | University of Cambridge |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | https://www.repository.cam.ac.uk/handle/1810/275469 |
Page generated in 0.0512 seconds