Warning
This version is intended for compiler hackers. We are in the midst of substantial structural changes, and this is a snapshot.
This version has some major MLRISC changes (from Allen Leung) and bug fixes for CM. The primary MLRISC changes include a sparse algorithm for interference graph construction, dead copy elimination, propagation of branch frequency information, and makes use of a new annotation mechanism throughout the system. Summary:
Fixed a bug related to consistent handling of pathnames that point to the same file but are not identical. (This situation can happen because of path anchors or symbolic links). CM
Fixed a potential exponential blowup in CM.make pointed out by Simon Helsen.
MLRISC
Register Allocator
This release uses a brand new graph coloring register allocator. The new register allocator is slightly faster (20% in the register allocator for RISC machines; no change for x86), generates less spill code (about 10% on RISC machines) than the previous one, and has eliminated a few bugs. It has also incorporated many algorithmic improvements (but the framework is still based on iterated coalescing). Some of the improvements are:
- Sparse interference graph construction -- the new algorithm uses a sparse method for constructing the interference graph. This is based on the algorithm described in Modern Compiler Implementation, by A.Appel. Since our input is mostly single assignment (CPS), this phase runs in effectively linear-time.
- Dead copy elimination -- an additional phase for removing dead copies is added. This allows us to remove about 59k of code on the x86 platform.
- In addition, these new features are added but not currently used for SML/NJ:
- coalescing and spilling decisions can now be prioritized by execution frequencies
- coalescing and coloring of spill locations
Please see the paper for more details.
The interface of annotations has been changed in this version. It is now an abstract type. See the files MLRISC/library/annotations.{sig,sml} and MLRISC/instructions/basicAnnotations.sig for details. Annotations
A few notes describing this change are available.
Block names
Block names are now implemented using basic block annotations instead of a special data constructor.MLTREE
Various fixes dealing with integer to integer conversions have been added.CM Libraries
All the target specific files have been turned into libraries. MLRISC itself has been broken up into several libraries a core defined by MLRISC.cm and various extensions.The new CM library mechanism makes it particularly easy to autoload new optimization phases at the top level. See compiler/MLRISC-OPTIMIZER.cm
Lal George Last modified: Wed Oct 6 21:37:30 EDT 1999