DMD Source Guide

Overview

Major components

All D compilers are divided into two parts: the front-end and the back-end.

The front-end (DMD-FE) implements all things D-specific: lexing and parsing D syntax, instantiating templates, producing error messages, etc. The same front-end code is used by DMD, GDC and LDC.

The back-end is what emits machine code. It contains code generation, optimization, object file writing, etc. The back-end is specific to each D compiler: DMD uses a source-available but proprietary (and non-redistributable) backend, while e.g. LDC uses LLVM as the back-end.

There is also a glue layer, which is the interface between the front-end and back-end. This component is custom for each D compiler.

Compilation cycle

D source code goes through the following stages when compiled:

• First, the file is loaded into memory as-is, and converted to UTF-8 when necessary.
• The lexer transforms the file into an array of tokens. There is no structure yet at this point - just a flat list of tokens. (lexer.c)
• The parser then builds a simple AST out of the token stream. (parser.c)
• The AST is then semantically processed. This is done in three stages (called semantic, semantic2 and semantic3). This is done in a loop in mars.c. Each pass transforms the AST to be closer to the final representation: types are resolved, templates are instantiated, etc.
• Finally, the AST is handed over to the glue layer, which feeds it into the back-end, which in turn produces machine code and object files.

Details

Note: This section may be considerably outdated. Please bring it up to date where you can.

There are a number of types that are stored in various nodes that are never actually used in the front end. They are merely stored and passed around as pointers.

• Symbol - Appears to have something to do with the names used by the linker. Appears to be used by Dsymbol and its subclasses.
• dt_t - "Data to be added to the data segment of the output object file" source: todt.c
• elem - A node in the internal representation.

The code generator is split among the various AST nodes. Certain methods of almost every AST node are part of the code generator.

(it's an interesting solution to the problem. It would have never occurred to a Java programmer)

Most notably:

• all Statement subclasses must define a toIR method
• All Expression subclasses must define a toElem method
• Initializers and certain Expression subclasses must define toDt
• Declarations must define toObjFile
• Dsymbol subclasses must define toSymbol

Other things

Floating point libraries seem to be atrociously incompatible between compilers. Replacing strtold with strtod may be necessary, for instance. (this does "break" the compiler, however: it will lose precision on literals of type 'real') -- AndyFriesen

Intermediate Representation

From NG:D.gnu/762

I've been looking at trying to hook the DMD frontend up to LLVM (www.llvm.org), but I've been having some trouble. The LLVM IR (Intermediate Representation) is very well documented, but I'm having a rough time figuring out how DMD holds its IR. Since at least three people (David, Ben, and Walter) seem to have understand, I thought I'd ask for guidance.

What's the best way to traverse the DMD IR once I've run the three semantic phases? As far as I can tell it's all held in the SymbolTable as a bunch of Symbols. Is there a good way to traverse that and reconstruct it into another IR?

---

From NG:D.gnu/764

There isn't a generic visitor interface. Instead, there are several methods with are responsible for emiting code/data and then calling that method for child objects. Start by implementing Module::genobjfile and loop over the 'members' array, calling each Dsymbol object's toObjFile method. From there, you will need to implement these methods:

Dsymbol (and descendents) ::toObjFile -- Emits code and data for objects that have generally have a symbol name and storage in memory. Containers like ClassDeclaration also have a 'members' array with child Dsymbols. Most of these are descendents of the Declaration class.

Statement (and descendents) ::toIR -- Emits instructions. Usually, you just call toObjFile, toIR, toElem, etc. on the statement's fields and string the results together in the IR.

Expression (and descendents) ::toElem -- Returns a back end representation of numeric constants, variable references, and operations that expression trees are composed of. This was very simple for GCC because the back end already had the code to convert expression trees to ordered instructions. If LLVM doesn't do this, I think you could generate the instructions here since LLVM has SSA.

Type (and descendents) ::toCtype -- Returns the back end representation of the type. Note that a lot of classes don't override this -- you just need to do a switch on the 'ty' field in Type::toCtype.

Dsymbol (and descendents) ::toSymbol -- returns the back end reference to the object. For example, FuncDeclaration::toSymbol could return a llvm::Function. These are already implemented in tocsym.c, but you will probably rewrite them to create LLVM objects.

---

(Thread: http://digitalmars.com/d/archives/D/gnu/762.html)

The Back End

DMD's internal representation uses expression trees with 'elem' nodes (defined in el.h). The "Rosetta Stone" for understanding the backend is enum OPER in oper.h. This lists all the types of nodes which can be in an expression tree.

If you compile dmd with debug on, and compile with:

 -O --c

you'll get reports of the various optimizations done.

Other useful undocumented flags:

--b  show block optimisation
--f  full output
--r  show register allocation
--x  suppress predefined C++ stuff
--y  show output to Intermediate Language (IL) buffer

Others which are present in the back-end but not exposed as DMD flags are:

debuge show exception handling info
debugs show common subexpression eliminator

The most important entry point from the front-end to the backend is writefunc() in out.c, which optimises a function, and then generates code for it.

• writefunc() sets up the parameters, then calls codgen() to generate the code inside the function.
• it generates code for each block. Then puts vars in registers.
• generates function start code, does pinhole optimisation. (cod3.pinholeopt()).
• does jump optimisation
• emit the generated code in codout().
• writes switch tables
• writes exception tables (nteh_gentables() or except_gentables()

In cgcod.c, blcodgen() generates code for a basic block. Deals with the way the block ends (return, switch, if, etc).

cod1.gencodelem() does the codegen inside the block. It just calls codelem().

cgcod.codelem() generates code for an elem. This distributes code generation depending on elem type.

Most x86 integer code generation happens in cod1,cod2, cod3, cod4, and cod5.c Floating-point code generation happens in cg87. Compared to the integer code generation, the x87 code generator is extremely simple. Most importantly, it cannot cope with common subexpressions. This is the primary reason why it is less efficient than compilers from many other vendors.

Optimiser

The main optimiser is in go.c, optfunc(). This calls:

• blockopt.c blockopt(iter) -- branch optimisation on basic blocks, iter = 0 or 1.
• gother.c constprop() -- constant propagation
• gother.c copyprop() -- copy propagation
• gother.c rmdeadass() -- remove dead assignments
• gother.c verybusyexp() -- very busy expressions
• gother.c deadvar() -- eliminate dead variables

• gloop.c loopopt() -- remove loop invariants and induction vars. Do loop rotation

• gdag.c boolopt() -- optimize booleans.
• gdag.c builddags() -- common subexpressions

• el.c el_convert() -- Put float and string literals into the data segment
• el.c el_combine() -- merges two expressions (uses a comma-expression to join them).
• glocal.c localize() -- improve expression locality

• cod3.c pinholeopt() -- Performs peephole optimisation. Doesn't do much, could do a lot more.

Code generation

The code generation for each function is done individually. Each function is placed into its own COMDAT segment in the obj file. The function is divided into blocks, which are linear sections of code ending with a jump or other control instruction (http://en.wikipedia.org/wiki/Basic_block).

Scheduler (cgsched.c)

Pentium only

Source files

Note: This section may be considerably outdated. If it's wrong, please correct it. If it's not here, please add it.

Front end

File	Function
access.c	Access check (private, public, package ...)
aliasthis.c	Implements the alias this D symbol.
argtypes.c	Convert types for argument passing (e.g. char are passed as ubyte).
arrayop.c	Array operations (e.g. a[] = b[] + c[]).
attrib.c	Attributes i.e. storage class (const, @safe ...), linkage (extern(C) ...), protection (private ...), alignment (align(1) ...), anonymous aggregate, pragma, static if and mixin.
bit.c	Generate bit-level read/write code. Requires backend support.
builtin.c	Identify and evaluate built-in functions (e.g. std.math.sin)
cast.c	Implicit cast, implicit conversion, and explicit cast (cast(T)), combining type in binary expression, integer promotion, and value range propagation.
class.c	Class declaration
clone.c	Define the implicit opEquals, opAssign, post blit and destructor for struct if needed, and also define the copy constructor for struct.
cond.c	Evaluate compile-time conditionals, i.e. debug, version, and static if.
constfold.c	Constant folding
cppmangle.c	Mangle D types according to Intel's Itanium C++ ABI.
declaration.c	Miscellaneous declarations, including typedef, alias, variable declarations including the implicit this declaration, type tuples, ClassInfo, ModuleInfo and various TypeInfos.
delegatize.c	Convert an expression expr to a delegate { return expr; } (e.g. in lazy parameter).
doc.c	Ddoc documentation generator (NG:digitalmars.D.announce/1558)
dsymbol.c	D symbols (i.e. variables, functions, modules, ... anything that has a name).
dump.c	Defines the Expression::dump method to print the content of the expression to console. Mainly for debugging.
e2ir.c	Expression to Intermediate Representation; requires backend support
eh.c	Generate exception handling tables
entity.c	Defines the named entities to support the "\&Entity;" escape sequence.
enum.c	Enum declaration
expression.h	Defines the bulk of the classes which represent the AST at the expression level.
func.c	Function declaration, also includes function/delegate literals, function alias, (static/shared) constructor/destructor/post-blit, invariant, unittest and allocator/deallocator.
glue.c	Generate the object file for function declarations and critical sections; convert between backend types and frontend types
hdrgen.c	Generate headers (*.di files)
iasm.c	Inline assembler
identifier.c	Identifier (just the name).
idgen.c	Make id.h and id.c for defining built-in Identifier instances. Compile and run this before compiling the rest of the source. (NG:digitalmars.D/17157)
impcvngen.c	Make impcnvtab.c for the implicit conversion table. Compile and run this before compiling the rest of the source.
imphint.c	Import hint, e.g. prompting to import std.stdio when using writeln.
import.c	Import.
inifile.c	Read .ini file
init.c	Initializers (e.g. the 3 in int x = 3).
inline.c	Compute the cost and perform inlining.
interpret.c	All the code which evaluates CTFE
irstate.c	Intermediate Representation state; requires backend support
json.c	Generate JSON output
lexer.c	Lexically analyzes the source (such as separate keywords from identifiers)
libelf.c	ELF object format functions
libmach.c	Mach-O object format functions
libomf.c	OMF object format functions
link.c	Call the linker
macro.c	Expand DDoc macros
mangle.c	Mangle D types and declarations
mars.c	Analyzes the command line arguments (also display command-line help)
module.c	Read modules.
msc.c	?
mtype.c	All D types.
opover.c	Apply operator overloading
optimize.c	Optimize the AST
parse.c	Parse tokens into AST
ph.c	Custom allocator to replace malloc/free
root/aav.c	Associative array
root/array.c	Dynamic array
root/async.c	Asynchronous input
root/dchar.c	Convert UTF-32 character to UTF-8 sequence
root/gnuc.c	Implements functions missing from GCC, specifically stricmp and memicmp.
root/lstring.c	Length-prefixed UTF-32 string.
root/man.c	Start the internet browser.
root/port.c	Portable wrapper around compiler/system specific things. The idea is to minimize #ifdef's in the app code.
root/response.c	Read the response file.
root/rmem.c	Implementation of the storage allocator uses the standard C allocation package.
root/root.c	Basic functions (deal mostly with strings, files, and bits)
root/speller.c	Spellchecker
root/stringtable.c	String table
s2ir.c	Statement to Intermediate Representation; requires backend support
scope.c	Scope
statement.c	Handles while, do, for, foreach, if, pragma, staticassert, switch, case, default , break, return, continue, synchronized, try/catch/finally, throw, volatile, goto, and label
staticassert.c	static assert.
struct.c	Aggregate (struct and union) declaration.
template.c	Everything related to template.
tk/	?
tocsym.c	To C symbol
toctype.c	Convert D type to C type for debug symbol
tocvdebug.c	CodeView4 debug format.
todt.c	?; requires backend support
toelfdebug.c	Emit symbolic debug info in Dwarf2 format. Currently empty.
toir.c	To Intermediate Representation; requires backend support
toobj.c	Generate the object file for Dsymbol and declarations except functions.
traits.c	__traits.
typinf.c	Get TypeInfo from a type.
unialpha.c	Check if a character is a Unicode alphabet.
unittests.c	Run functions related to unit test.
utf.c	UTF-8.
version.c	Handles version

Back end

File	Function
html.c	Extracts D source code from .html files

A few observations

• idgen.c is not part of the compiler source at all. It is the source to a code generator which creates id.h and id.c, which defines a whole lot of Identifier instances. (presumably, these are used to represent various 'builtin' symbols that the language defines)
• impcvngen.c follows the same pattern as idgen.c. It creates impcnvtab.c, which appears to describe casting rules between primitive types.
• Unspurprisingly, the code is highly D-like in methodology. For instance, root.h defines an Object class which serves as a base class for most, if not all of the other classes used. Class instances are always passed by pointer and allocated on the heap.
• root.h also defines String, Array, and File classes, as opposed to using STL. Curious. (a relic from the days when templates weren't as reliable as they are now?)
• lots of files with .c suffixes contain C++ code. Very confusing.

Abbreviations

You may find these abbreviations throughout the DMD source code (in identifiers and comments).

Front-end

STC

STorage Class

ILS

InLine State

IR

Intermediate Representation

Back-end

VBE

Very Busy Expression (http://web.cs.wpi.edu/~kal/PLT/PLT9.6.html)

CP

Copy Propagation info (?)

AE

Arithmetic Expression?

See also: Commonly-Used Acronyms

Class hierarchy

• RootObject (The root object of all AST classes. Similar to D's Object.)
  • Dsymbol (A "D symbol". Serves as an abstract base for anything which is declared, such as classes/structs and variable declarations. Most (all?) objects which inherit from Dsymbol wind up getting written to the ouput object file.)
    • AliasThis
    • AttribDeclaration (Base class for things like access modifiers, pragma, debug (which is in turn the base class of version).)
      • StorageClassDeclaration
        • DeprecatedDeclaration
      • LinkDeclaration
      • ProtDeclaration
      • AlignDeclaration
      • AnonDeclaration
      • PragmaDeclaration
      • ConditionalDeclaration
        • StaticIfDeclaration
      • CompileDeclaration
      • UserAttributeDeclaration
    • Declaration (Base class for pretty much all declarations.)
      • TupleDeclaration
      • TypedefDeclaration
      • AliasDeclaration
      • VarDeclaration
        • ClassInfoDeclaration
        • TypeInfoDeclaration
          • TypeInfoStructDeclaration, TypeInfoClassDeclaration, TypeInfoInterfaceDeclaration, TypeInfoTypedefDeclaration, TypeInfoPointerDeclaration, TypeInfoArrayDeclaration, TypeInfoStaticArrayDeclaration, TypeInfoAssociativeArrayDeclaration, TypeInfoEnumDeclaration, TypeInfoFunctionDeclaration, TypeInfoDelegateDeclaration, TypeInfoTupleDeclaration, TypeInfoConstDeclaration, TypeInfoInvariantDeclaration, TypeInfoSharedDeclaration, TypeInfoWildDeclaration, TypeInfoVectorDeclaration
        • ThisDeclaration
      • SymbolDeclaration
      • FuncDeclaration
        • FuncAliasDeclaration
        • FuncLiteralDeclaration
        • CtorDeclaration
        • PostBlitDeclaration
        • DtorDeclaration
        • StaticCtorDeclaration
          • SharedStaticCtorDeclaration
        • StaticDtorDeclaration
          • SharedStaticDtorDeclaration
        • InvariantDeclaration
        • UnitTestDeclaration
        • NewDeclaration
        • DeleteDeclaration
    • ScopeDsymbol (A symbol which creates a scope for its children. Base class of with blocks, enum declarations, and templates.)
      • AggregateDeclaration
        • StructDeclaration
          • UnionDeclaration
        • ClassDeclaration
          • InterfaceDeclaration
      • WithScopeSymbol
      • ArrayScopeSymbol
      • EnumDeclaration
      • Package
        • Module
      • TemplateDeclaration
      • TemplateInstance
        • TemplateMixin
    • OverloadSet
    • EnumMember
    • Import
    • LabelDsymbol
    • StaticAssert
    • DebugSymbol
    • VersionSymbol

• • Expression (Nodes for operations, assignments, and the like derive Expression. All expressions have an interpret method which does CTFE.)
    • ClassReferenceExp
    • VoidInitExp
    • ThrownExceptionExp
    • IntegerExp
    • ErrorExp
    • RealExp
    • ComplexExp
    • IdentifierExp
      • DollarExp
    • DsymbolExp (An expression that points to a Dsymbol.)
    • ThisExp
      • SuperExp
    • NullExp
    • StringExp
    • TupleExp
    • ArrayLiteralExp
    • AssocArrayLiteralExp
    • StructLiteralExp
    • TypeExp
    • ScopeExp
    • TemplateExp
    • NewExp
    • NewAnonClassExp
    • SymbolExp (Points to a Declaration.)
      • SymOffExp (Offset from symbol.)
      • VarExp (A variable referenced in an expression.)
    • OverExp
    • FuncExp
    • DeclarationExp
    • TypeidExp
    • TraitsExp
    • HaltExp
    • IsExp
    • UnaExp (All unary expressions - expressions which wrap one subexpression.)
      • CompileExp
      • FileExp
      • AssertExp
      • DotIdExp
      • DotTemplateExp
      • DotVarExp
      • DotTemplateInstanceExp
      • DelegateExp
      • DotTypeExp
      • CallExp
      • AddrExp
      • PtrExp
      • NegExp
      • UAddExp
      • ComExp
      • NotExp
      • BoolExp
      • DeleteExp
      • CastExp
      • VectorExp
      • SliceExp
      • ArrayLengthExp
      • ArrayExp
      • PreExp
    • BinExp (All binary expressions - expressions which have two subexpressions.)
      • BinAssignExp
        • AddAssignExp, MinAssignExp, MulAssignExp, DivAssignExp, ModAssignExp, AndAssignExp, OrAssignExp, XorAssignExp, PowAssignExp, ShlAssignExp, ShrAssignExp, UshrAssignExp, CatAssignExp
      • DotExp
      • CommaExp
      • IndexExp
      • PostExp
      • AssignExp
        • ConstructExp
      • AddExp, MinExp, CatExp, MulExp, DivExp, ModExp, PowExp, ShlExp, ShrExp, UshrExp, AndExp, OrExp, XorExp, OrOrExp, AndAndExp
      • CmpExp
      • InExp
      • RemoveExp
      • EqualExp
      • IdentityExp
      • CondExp
    • DefaultInitExp
      • FileInitExp
      • LineInitExp
      • ModuleInitExp
      • FuncInitExp
      • PrettyFuncInitExp

• • Identifier

• • Initializer
    • VoidInitializer
    • ErrorInitializer
    • StructInitializer
    • ArrayInitializer
    • ExpInitializer

• • Type
    • TypeError
    • TypeNext
      • TypeArray
        • TypeSArray
        • TypeDArray
        • TypeAArray
      • TypePointer
      • TypeReference
      • TypeFunction
      • TypeDelegate
      • TypeSlice
    • TypeBasic
    • TypeVector
    • TypeQualified
      • TypeIdentifier
      • TypeInstance
      • TypeTypeof
      • TypeReturn
    • TypeStruct
    • TypeEnum
    • TypeTypedef
    • TypeClass
    • TypeTuple
    • TypeNull

• • Parameter

• • Statement (Base class for top-level function statements. Among these is ExpStatement, which is a statement which wraps an expression. For example, a function call or an assignment is an Expression / ExpStatement.)
    • ErrorStatement
    • PeelStatement
    • ExpStatement
      • DtorExpStatement
    • CompileStatement
    • CompoundStatement
      • CompoundDeclarationStatement
    • UnrolledLoopStatement
    • ScopeStatement
    • WhileStatement
    • DoStatement
    • ForStatement
    • ForeachStatement
    • ForeachRangeStatement
    • IfStatement
    • ConditionalStatement
    • PragmaStatement
    • StaticAssertStatement
    • SwitchStatement
    • CaseStatement
    • CaseRangeStatement
    • DefaultStatement
    • GotoDefaultStatement
    • GotoCaseStatement
    • SwitchErrorStatement
    • ReturnStatement
    • BreakStatement
    • ContinueStatement
    • SynchronizedStatement
    • WithStatement
    • TryCatchStatement
    • TryFinallyStatement
    • OnScopeStatement
    • ThrowStatement
    • DebugStatement
    • GotoStatement
    • LabelStatement
    • AsmStatement
    • ImportStatement

• • Catch
  • Tuple
  • DsymbolTable

• TemplateParameter
  • TemplateTypeParameter
    • TemplateThisParameter
  • TemplateValueParameter
  • TemplateAliasParameter
  • TemplateTupleParameter

• Visitor
  • StoppableVisitor

• Condition
  • DVCondition
    • DebugCondition
    • VersionCondition
  • StaticIfCondition

• Lexer
  • Parser

• Library