The Compiler

Talk by Ivan Godard – June 10, 2015, at the
SFBay Association of C/C++ Users

NOTE: the slides require genuine Microsoft PowerPoint to view; open source PowerPoint clones are unable to show the animations, which are essential to the slide content. If you do not have access to PowerPoint then watch the video, which shows the slides as intended.

Slides: mill-cpu-compiler.04 (.pptx)

This is the tenth topic publicly presented related to the Mill general-purpose CPU architecture. It covers only the tool chain used to generate executable binaries targeted for any member of the Mill CPU architecture family. The talk assumes a familiarity with aspects of CPU architecture in general and C++ programming in particular.

LLVM meets the truly alien:

The Mill CPU architecture in a multi-target tool chain

The Mill is a new general-purpose CPU architecture family that forms a uniquely challenging target for compilation – and also a uniquely easy target. This talk describes the Mill tool chain from language front end to binary executable.

The Mill tool chain is unusual in that it translates LLVM intermediate representation (IR) not into object code but into a different IR (genAsm), tailored for the Mill architecture family. Then a separate tool, the specializer, converts genAsm input into executable binary code (conAsm) for a particular Mill architecture family member. genAsm is a dataflow language, essentially a programmable representation of a single-assignment compiler IR.

The Mill has no general registers. Instead, intermediate results are placed on the Belt, a fixed-length queue, and these operands are accessed by temporal addressing. A Mill operation in effect says “add the third most recent value to drop on the belt to the fifth most recent, and drop the result at the front of the belt, and discard the oldest value from the other end of the belt”. The Mill is also a (very) wide issue machine, and many of these actions are taking place concurrently in each cycle. The tool chain, or rather the specializer component, must track the location of operands as they move along the belt, because their belt address changes as other operations are executed and drop results. In addition, the Mill is statically scheduled with an exposed pipeline, so an operation may produce its results several cycles after the operation was issued, possibly with intervening control flow.

This belt structure leads to unique needs for operation scheduling and operand spilling. These needs are the rough equivalent of instruction selection, register coloring, and spill on a conventional machine. The talk concludes by explaining the algorithms used.

Speaker bio

Ivan Godard has designed, implemented or led the teams for 11 compilers for a variety of languages and targets, an operating system, an object-oriented database, and four instruction set architectures. He participated in the revision of Algol68 and is mentioned in its Report, was on the Green team that won the Ada language competition, designed the Mary family of system implementation languages, and was founding editor of the Machine Oriented Languages Bulletin. He is a Member Emeritus of IFIPS Working Group 2.4 (Implementation languages) and was a member of the committee that produced the IEEE and ISO floating-point standard 754-2011.

Ivan is currently CTO at Mill Computing, a startup now emerging from stealth mode. Mill Computing has developed the Mill, a clean-sheet rethink of general-purpose CPU architectures. The Mill is the subject of this talk.