Difference between revisions of "DMD Source Guide"

From D Wiki
Jump to: navigation, search
(Class hierarchy)
m (oops Note the difference between two mixin declarations and mixin statements)
 
(18 intermediate revisions by 6 users not shown)
Line 7: Line 7:
 
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 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.
+
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 D-specific Boost-licensed (as of April 2017) back-end, LDC uses [[LLVM]], and GDC uses [[GCC]] for their respective back-end processing.
  
 
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.
 
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.
Line 266: Line 266:
  
 
=== Front end ===
 
=== Front end ===
 +
See the [https://github.com/dlang/dmd/blob/master/compiler/src/dmd/README.md official docs].
 +
 
{| class="wikitable" |
 
{| class="wikitable" |
 
! File || Function
 
! File || Function
Line 283: Line 285:
 
| builtin.d || Identify and evaluate built-in functions (e.g. '''std.math.sin''')
 
| builtin.d || Identify and evaluate built-in functions (e.g. '''std.math.sin''')
 
|-
 
|-
| cast.d || Implicit cast, implicit conversion, and explicit cast ('''cast(T)'''), combining type in binary expression, integer promotion, and value range propagation.
+
| dcast.d || Implicit cast, implicit conversion, and explicit cast ('''cast(T)'''), combining type in binary expression, integer promotion, and value range propagation.
 
|-
 
|-
| class.d || Class declaration
+
| dclass.d || Class declaration
 
|-
 
|-
 
| clone.d || Define the implicit '''opEquals''', '''opAssign''', post blit and destructor for struct if needed, and also define the copy constructor for struct.
 
| clone.d || Define the implicit '''opEquals''', '''opAssign''', post blit and destructor for struct if needed, and also define the copy constructor for struct.
Line 293: Line 295:
 
| constfold.d || Constant folding
 
| constfold.d || Constant folding
 
|-
 
|-
| cppmangle.d || Mangle D types according to [http://mentorembedded.github.io/cxx-abi/abi.html#mangling Intel's Itanium C++ ABI].
+
| cppmangle.d || Mangle D types according to [http://itanium-cxx-abi.github.io/cxx-abi/abi.html#mangling Intel's Itanium C++ ABI].
 
|-
 
|-
 
| declaration.d || Miscellaneous declarations, including '''typedef''', '''alias''', variable declarations including the implicit '''this''' declaration, type tuples, ClassInfo, ModuleInfo and various TypeInfos.
 
| declaration.d || Miscellaneous declarations, including '''typedef''', '''alias''', variable declarations including the implicit '''this''' declaration, type tuples, ClassInfo, ModuleInfo and various TypeInfos.
Line 311: Line 313:
 
| entity.d || Defines the named entities to support the ''"\&Entity;"'' escape sequence.
 
| entity.d || Defines the named entities to support the ''"\&Entity;"'' escape sequence.
 
|-
 
|-
| enum.d || Enum declaration
+
| denum.d || Enum declaration
 
|-
 
|-
 
| expression.h || Defines the bulk of the classes which represent the AST at the expression level.
 
| expression.h || Defines the bulk of the classes which represent the AST at the expression level.
Line 331: Line 333:
 
| imphint.d || Import hint, e.g. prompting to import ''std.stdio'' when using ''writeln''.
 
| imphint.d || Import hint, e.g. prompting to import ''std.stdio'' when using ''writeln''.
 
|-
 
|-
| import.d || Import.
+
| dimport.d || Import.
 
|-
 
|-
 
| inifile.d || Read .ini file
 
| inifile.d || Read .ini file
Line 355: Line 357:
 
| link.d || Call the linker
 
| link.d || Call the linker
 
|-
 
|-
| macro.d || Expand DDoc macros
+
| dmacro.d || Expand DDoc macros
 
|-
 
|-
 
| mangle.d || Mangle D types and declarations
 
| mangle.d || Mangle D types and declarations
Line 361: Line 363:
 
| mars.d || Analyzes the command line arguments (also display command-line help)
 
| mars.d || Analyzes the command line arguments (also display command-line help)
 
|-
 
|-
| module.d || ead modules.
+
| dmodule.d || ead modules.
 
|-
 
|-
 
| msc.d || ?
 
| msc.d || ?
Line 403: Line 405:
 
| s2ir.d || Statement to Intermediate Representation; requires backend support
 
| s2ir.d || Statement to Intermediate Representation; requires backend support
 
|-
 
|-
| scope.d || Scope
+
| dscope.d || Scope
 
|-
 
|-
 
| statement.d || Handles '''while''', '''do''', '''for''', '''foreach''', '''if''', '''pragma''', '''staticassert''', '''switch''', '''case''', '''default''' , '''break''', '''return''', '''continue''', '''synchronized''', '''try'''/'''catch'''/'''finally''', '''throw''', '''volatile''', '''goto''', and '''label'''
 
| statement.d || Handles '''while''', '''do''', '''for''', '''foreach''', '''if''', '''pragma''', '''staticassert''', '''switch''', '''case''', '''default''' , '''break''', '''return''', '''continue''', '''synchronized''', '''try'''/'''catch'''/'''finally''', '''throw''', '''volatile''', '''goto''', and '''label'''
Line 409: Line 411:
 
| staticassert.d || '''static assert'''.
 
| staticassert.d || '''static assert'''.
 
|-
 
|-
| struct.d || Aggregate ('''struct''' and '''union''') declaration.
+
| dstruct.d || Aggregate ('''struct''' and '''union''') declaration.
 
|-
 
|-
| template.d || Everything related to '''template'''.
+
| dtemplate.d || Everything related to '''template'''.
 
|-
 
|-
 
| tk/ || ?
 
| tk/ || ?
Line 557: Line 559:
 
*** DebugSymbol
 
*** DebugSymbol
 
*** VersionSymbol
 
*** VersionSymbol
 
 
** Expression
 
** Expression
 
*** ClassReferenceExp
 
*** ClassReferenceExp
Line 663: Line 664:
 
**** FuncInitExp
 
**** FuncInitExp
 
**** PrettyFuncInitExp
 
**** PrettyFuncInitExp
 
 
** Identifier
 
** Identifier
 
 
** Initializer
 
** Initializer
 
*** VoidInitializer
 
*** VoidInitializer
Line 672: Line 671:
 
*** ArrayInitializer
 
*** ArrayInitializer
 
*** ExpInitializer
 
*** ExpInitializer
 
 
** Type
 
** Type
 
*** TypeError
 
*** TypeError
Line 697: Line 695:
 
*** TypeTuple
 
*** TypeTuple
 
*** TypeNull
 
*** TypeNull
 
 
** Parameter
 
** Parameter
 
 
** Statement
 
** Statement
 
*** ErrorStatement
 
*** ErrorStatement
Line 740: Line 736:
 
*** AsmStatement
 
*** AsmStatement
 
*** ImportStatement
 
*** ImportStatement
 
 
** Catch
 
** Catch
 
 
** Tuple
 
** Tuple
 
 
** DsymbolTable
 
** DsymbolTable
 
 
** Condition
 
** Condition
 
*** DVCondition
 
*** DVCondition
Line 752: Line 744:
 
**** VersionCondition
 
**** VersionCondition
 
*** StaticIfCondition
 
*** StaticIfCondition
 
 
* Visitor
 
* Visitor
 
** StoppableVisitor
 
** StoppableVisitor
 
 
 
* Lexer
 
* Lexer
 
** Parser
 
** Parser
 
 
* Library
 
* Library
  
Line 771: Line 759:
 
for example:
 
for example:
  
<syntaxhighlight lang="cpp">
+
<syntaxhighlight lang="d">
void StructDeclaration::semantic(Scope *sc)
+
void semantic(Scope* sc)
 
{
 
{
 
     // only do printouts if this is our target symbol
 
     // only do printouts if this is our target symbol
     if (!strcmp(toChars(), "test_struct"));
+
     if (!strcmp(toChars, "test_struct"));
         printf("this=%p, %s '%s', sizeok = %d\n", this, parent->toChars(), toChars(), sizeok);
+
         printf("this=%p, %s '%s', sizeok = %d\n", this, parent.toChars, toChars, sizeok);
 
}
 
}
 
</syntaxhighlight>
 
</syntaxhighlight>
Line 782: Line 770:
 
=== Find which module instantiated a specific template instance ===
 
=== Find which module instantiated a specific template instance ===
  
Templates have a '''instantiatingModule''' field which you can inspect. Here's an example from '''glue.c''':
+
Templates have a '''instantiatingModule''' field which you can inspect. Here's an example from '''glue.d''':
  
<syntaxhighlight lang="cpp">
+
<syntaxhighlight lang="d">
 
/* Skip generating code if this part of a TemplateInstance that is instantiated
 
/* Skip generating code if this part of a TemplateInstance that is instantiated
 
  * only by non-root modules (i.e. modules not listed on the command line).
 
  * only by non-root modules (i.e. modules not listed on the command line).
 
  */
 
  */
TemplateInstance *ti = inTemplateInstance();
+
TemplateInstance* ti = inTemplateInstance();
 
if (!global.params.useUnitTests &&
 
if (!global.params.useUnitTests &&
     ti && ti->instantiatingModule && !ti->instantiatingModule->root)
+
     ti && ti.instantiatingModule && !ti.instantiatingModule.root)
 
{
 
{
     //printf("instantiated by %s  %s\n", ti->instantiatingModule->toChars(), ti->toChars());
+
     //printf("instantiated by %s  %s\n", ti.instantiatingModule.toChars(), ti.toChars());
 
     return;
 
     return;
 +
}
 +
</syntaxhighlight>
 +
 +
=== View lowerings, emitted templates instances and string/mixins  ===
 +
 +
The <tt>-vcg-ast</tt> switch will generate a .cg-file next to the compiled code source-code
 +
Which will contain the source representation of the AST just before code-generation
 +
(That means the last stage of compilation)
 +
This helps to debug templates as well spot issues with the inliner
 +
NOTE: for this to work the code has to reach the codegen stage i.e is has to compile without error
 +
 +
<syntaxhighlight lang="d">
 +
void main() {
 +
  foreach (i; 0 .. 10) {
 +
      mixin("auto a = i;");
 +
  }
 +
}
 +
</syntaxhighlight>
 +
 +
<syntaxhighlight lang="bash">
 +
dmd -vcg-ast test.d
 +
</syntaxhighlight>
 +
 +
Which will generated a file <tt>test.d.cg</tt>:
 +
 +
<syntaxhighlight lang="d">
 +
import object;
 +
void main()
 +
{
 +
{
 +
int __key2 = 0;
 +
int __limit3 = 10;
 +
for (; __key2 < __limit3; __key2 += 1)
 +
{
 +
int i = __key2;
 +
int a = i;
 +
}
 +
}
 +
return 0;
 
}
 
}
 
</syntaxhighlight>
 
</syntaxhighlight>
Line 801: Line 828:
 
You can use the '''resolve''' virtual function to determine this:
 
You can use the '''resolve''' virtual function to determine this:
  
<syntaxhighlight lang="cpp">
+
<syntaxhighlight lang="d">
RootObject *o = ...;
+
RootObject* o = ...;
Type *srcType = isType(o);
+
Type* srcType = isType(o);
  
 
if (srcType)
 
if (srcType)
 
{
 
{
     Type *t;
+
     Type* t;
     Expression *e;
+
     Expression* e;
     Dsymbol *s;
+
     Dsymbol* s;
     srcType->resolve(loc, sc, &e, &t, &s);
+
     srcType.resolve(loc, sc, &e, &t, &s);
  
 
     if (t) { }  // it's a type
 
     if (t) { }  // it's a type
Line 818: Line 845:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
You can see examples of this technique being used in the '''traits.c''' file.
+
You can see examples of this technique being used in the '''traits.d''' file.
  
 
=== Get the string representation of a DSymbol ===
 
=== Get the string representation of a DSymbol ===
Line 826: Line 853:
 
while the latter may print out the fully-scoped name of the symbol. For example:
 
while the latter may print out the fully-scoped name of the symbol. For example:
  
<syntaxhighlight lang="cpp">
+
<syntaxhighlight lang="d">
StructDeclaration *sd = ...;  // assuming struct named "Bar" inside module named "Foo"
+
StructDeclaration* sd = ...;  // assuming struct named "Bar" inside module named "Foo"
printf("name: %s\n", sd->toChars());  // prints out "Bar"
+
printf("name: %s\n", sd.toChars());  // prints out "Bar"
printf("fully qualified name: %s\n", sd->toPrettyChars());  // prints out "Foo.Bar"
+
printf("fully qualified name: %s\n", sd.toPrettyChars());  // prints out "Foo.Bar"
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Line 837: Line 864:
 
which enable you to use printf-style debugging, e.g.:
 
which enable you to use printf-style debugging, e.g.:
  
<syntaxhighlight lang="cpp">
+
<syntaxhighlight lang="d">
EnumDeclaration *ed = ...;
+
EnumDeclaration* ed = ...;
DSymbol *s = ed;
+
DSymbol* s = ed;
printf("%s\n", s->kind());  // prints "enum". See 'EnumDeclaration::kind'.
+
printf("%s\n", s.kind());  // prints "enum". See 'EnumDeclaration.kind'.
 +
</syntaxhighlight>
 +
 
 +
=== Get the string representation of the dynamic type of an ast-node ===
 +
There is a helper module called '''asttypename''' which allows you to print the dynamic type of an ast-node
 +
This is useful when implementing your own visitors.
 +
 
 +
<syntaxhighlight lang="d">
 +
import dmd.asttypename;
 +
Expression ex = new AndAndExp(...);
 +
writeln(ex.astTypeName);  // prints "AndAndExp".
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Line 846: Line 883:
  
 
'''Expression''' objects hold an '''op''' field, which is a '''TOK''' type (a token).
 
'''Expression''' objects hold an '''op''' field, which is a '''TOK''' type (a token).
To print out the string representation of the token, index into the static array '''Token::tochars''':
+
To print out the string representation of the token, index into the static array '''Token.toChars''':
  
<syntaxhighlight lang="cpp">
+
<syntaxhighlight lang="d">
Expression *e = ...;
+
Expression* e = ...;
printf("Expression op: %s ", Token::toChars(e->op));
+
printf("Expression op: %s ", Token.toChars(e.op));
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Line 858: Line 895:
 
use the '''toReal()''' member function:
 
use the '''toReal()''' member function:
  
<syntaxhighlight lang="cpp">
+
<syntaxhighlight lang="d">
if (exp->op == TOKfloat32 || exp->op == TOKfloat64 || exp->op == TOKfloat80)
+
if (exp.op == TOKfloat32 || exp.op == TOKfloat64 || exp.op == TOKfloat80)
     printf("%Lf", exp->toReal());
+
     printf("%Lf", exp.toReal());
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Line 870: Line 907:
 
equally named function in the '''Expression''' class.
 
equally named function in the '''Expression''' class.
  
=== Note the difference between two mixin types: compile declarations and compile statements ===
+
=== Note the difference between mixin declarations and mixin statements ===
  
 
Take this example D code:
 
Take this example D code:
Line 883: Line 920:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
The first mixin is a '''CompileDeclaration''', while the second is a '''CompileStatement'''.
+
The first mixin is a '''MixinDeclaration''', while the second is a '''MixinStatement'''.
 
These are separate classes in the DMD front-end.
 
These are separate classes in the DMD front-end.
  
  
 
[[Category:DMD Compiler]]
 
[[Category:DMD Compiler]]

Latest revision as of 17:54, 7 April 2024

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 D-specific Boost-licensed (as of April 2017) back-end, LDC uses LLVM, and GDC uses GCC for their respective back-end processing.

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.
1. The "semantic" phase will analyze the full signature of all declarations. For example:
  • members of aggregate type
  • function parameter types and return type
  • variable types
  • evaluation of pragma(msg)
2. The "semantic2" phase will analyze some additional part of the declarations, For example:
  • initializer of variable declarations
  • evaluation of static assert condition
3. The "semantic3" phase will analyze the body of function declarations.
If a function is declared in the module which is not directly compiled (== not listed in the command line), semantic3 pass won't analyze its body.
4. During each phases, some declarations will partially invoke the subsequent phases due to resolve forward reference, For example:
immutable string x = "hello";
static if (x == "hello") { ... }
// The static if condition will invoke semantic2 of the variable 'x'
auto foo() { ... }
typeof(&foo) fp;
// "semantic" phase of the variable 'fp' will run "semantic3" of 'foo'
// to demand the full signature of the function (== infer the return type)
string foo() { ... }
mixin(foo());
// For CTFE, the mixin declaration will invoke the semantic3 of 'foo'
  • 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.

Runtime interoperability

Non-trivial operations (e.g. memory allocation, array operations) are implemented in the D runtime. The compiler integrates with the runtime using a number of so-called hook functions (which by convention have the _d_ name prefix).

A list can be found here: Runtime_Hooks

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)

Inliner

DMD's inliner is part of the frontend, existing entirely in the file inline.c.

This inliner is conceptually quite simple: It traverses the AST looking for function calls. Each function found is analysed for cost by adding up the number of expression nodes in its body. Anything non-inlinable counts as "maximum cost". If the total cost is below the maximum, the function call is inlined.

In DMD's AST, certain statements cannot currently be represented as expressions (such as non-unrolled loops and throwing). Because of this, the inliner makes a distinction between two main types of inlining:

  • Converting a function call to an inline expression: This must be used whenever the function's return value is actually used. Ex: "x = foo();" or "2 + foo()".
  • Converting a function call to an inline statement: Used when a function's return value is ignored, or when calling a void function.

Those two scenarios are inlined by mostly separate codepaths. Cost analysis is mostly the same codepath, but "inlinable as a statement" and "inlinable as an expression" are separate decisions (again, due to certain statements not being representable as expressions).

The inliner is divided into four main parts:

  • Main entry point: inlineScan (which utilizes class InlineScanVisitor and function expandInline)
  • Cost analysis (to determine inlinability): canInline and class InlineCostVisitor
  • Inlining a function call as a statement: inlineAsStatement and its embedded class InlineAsStatement
  • Inlining a function call as an expression: doInline and its embedded class InlineStatement
Inliner: Main Entry Point

The whole inliner is driven by the inlineScan function and InlineScanVisitor class, but the bulk of the real work is performed by expandInline (described in this section) and the other three main parts of the inliner (described in the following sections).

The global function inlineScan is the inliner's main entry point. This uses class InlineScanVisitor to traverse the AST looking for function calls to inline, and inlining them as they're found. Whenever InlineScanVisitor finds an inlinable function call (determined by the cost analyzer), it calls expandInline to start the inlining process.

InlineScanVisitor also decides whether to inline as a statement or an expression based on the type of AST node found:

  • ExpStatement: Implies the function either has no return value, or the return value is unused. Therefore, inline as a statement (if permitted by cost analysis).
  • CallExp: Implies the function returns a value which is used. Therefore, inline as an expression (if permitted by cost analysis).

Called by InlineScanVisitor, expandInline drives the actual inlining for both "as statement" and "as expression" cases. It converts the function call scaffolding, parameters and return value (if any) into the appropriate inline statement or expression. To inline the function's body, expandInline hands over to either inlineAsStatement (if inlining the call as a statement) or doInline (if inlining the call as an expression).

Inliner: Cost Analysis

The function canInline, unsurprisingly, determines if a function can be inlined. To decide this, it uses class InlineCostVisitor, which traverses the AST calculating a sum of all costs involved.

InlineCostVisitor is a Visitor class which works just like any other AST visitor class in DMD, or any other usage of the visitor pattern: It contains a visit function for each AST node type supported by the inliner. Each visit function traverses its children nodes (if any) by calling the child node's accept function, passing the visitor class itself as an argument. Then the node's accept automatically calls its corresponding visit function.

Any type of node not supported by InlineCostVisitor automatically calls a default function InlineCostVisitor::visit(Statement *s), which flags the function being analyzed as non-inlinable.

The actual cost variable is slightly complicated since it's really two packed values:

The low 12-bits of cost are the actual accumulated cost. A value of 1 is added for every inlinable expression node in the function's body (ex: "a+b*c" has a cost of 2: One for the multiplication and one for the addition). Anything that can't be inlined, or that the cost analyzer knows nothing about, adds a cost of COST_MAX. If this total cost, in the low 12-bits, is at least COST_MAX (determined by the helper function tooCostly), the function is considered non-inlinable.

The upper bits of cost (bits 13 and up) are separate from the actual cost and keep track of whether the function can be inlined as an expression. Whenever a statement is found which can be inlined only as a statement (and cannot be converted to an expression), this is flagged by adding STATEMENT_COST to cost.

Note: It looks as if at one point in time there had been a limit (or perhaps plans to eventually limit) the number of statements allowed in inlined functions, just as there's currently a limit to the number of expression nodes. But this does not currently appear to be enforced, so STATEMENT_COST is essentially used as a "this can only be inlined as a statement" flag.

Sometimes expressions are evaluated for cost by simply visiting the the expression node, via the node's accept function. Other times, the helper function InlineCostVisitor::expressionInlineCost is used instead. The benefit of expressionInlineCost is it automatically halts analysis of an expression as soon as it reaches COST_MAX.

The canInline function caches its results in two members of FuncDeclaration: In ILS inlineStatusStmt (for inlinability as a statement) and ILS inlineStatusExp (for inlinability as an expression). ILS is an enum defined in declaration.h supporting three states: ILSuninitialized (not yet cached), ILSno (not inlinable) and ILSyes (inlinable).

Inliner: Inlining as a Statement

Any functions DMD is capable of inlining, can be inlined as a statement. As explained above, this is performed whenever a function call ignores the return value, or has no return value. In this case, the function's body is inlined via inlineAsStatement. Internally, inlineAsStatement works using its embedded visitor class InlineAsStatement.

To paraphrase a comment in inline.c, this inlining is done by converting to a statement, copying the trees of the function to be inlined, and renaming the variables. Most of this is fairly straightforward: Much like the cost analyzer's InlineCostVisitor class, the InlineAsStatement class has a visit function for each supported type of statement and expression. Each of these visitors copies the node, makes any adjustments if necessary, and then visits all subnodes by calling their accept functions.

There's also a default catch-all function which asserts, indicating the cost analyzer failed to disallow something which has no corresponding visitor in InlineAsStatement.

Inliner: Inlining as an Expression

Some, but not all, inlinable functions can be inlined as an expression. This must be done whenever a function call uses the return value (Ex: "x = foo();" or "2 + foo()"). In this case, inlining the function's body as an expression works very much like inlining it as a statement (see the section above), but with a separate code path and a few differences:

  • The function body is inlined by doInline instead of inlineAsStatement.
  • There are two overloads of doInline: One to inline expressions as expressions, and one to convert statements to inline expressions.
  • As discussed in the sections above, not all statements can be converted to expressions. Because of this, these statements' corresponding visit functions are omitted from doInline, since the cost analyzer should have already prevented the inliner from attempting to inline any offending functions.
Inliner: How to Add More Support

If a particular statement is unsupported by the inliner (thereby preventing any function using it from being inlined), support can be added like this:

  • Add an overload of InlineCostVisitor::visit for the type of AST node you wish to support. Following the example of the other visit functions:
  • Increase cost however is appropriate.
  • Add STATEMENT_COST to cost if the statement cannot be converted to an expression (ex: ForStatement and ThrowStatement). This allows you to omit a corresponding overload of doInline's InlineStatement::visit.
  • Add COST_MAX to cost for any situations that are not inlinable.
  • Call accept on all subnodes. If the subnode is an expression, it may be better to use expressionInlineCost instead since this will automatically halt analysis as soon as the expression's cost reaches the maximum.
  • In inlineAsStatement, add an overload of InlineAsStatement::visit for the appropriate AST node type. Following the example of the other visit overloads: Copy the node, make any adjustments if necessary, and traverse to all subnodes.
  • If the statement can be converted to an expression (ex: IfStatement), then inside the Statement overload of doInline, add an overload of InlineStatement::visit for the appropriate AST node type. Following the other examples, convert the node to an expression, make any adjustments if necessary, and traverse to all subnodes.

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

See the official docs.

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

AE
Available Expressions
CP
Copy Propagation info.
CSE
Common Subexpression Elimination
VBE
Very Busy Expression (http://web.cs.wpi.edu/~kal/PLT/PLT9.6.html)

See also: Commonly-Used Acronyms

Class hierarchy

Have a look at Media:dmd_ast.png.

  • RootObject
    • Dsymbol
      • AliasThis
      • AttribDeclaration
        • StorageClassDeclaration
          • DeprecatedDeclaration
        • LinkDeclaration
        • ProtDeclaration
        • AlignDeclaration
        • AnonDeclaration
        • PragmaDeclaration
        • ConditionalDeclaration
          • StaticIfDeclaration
        • CompileDeclaration
        • UserAttributeDeclaration
      • Declaration
        • TupleDeclaration
        • AliasDeclaration
        • VarDeclaration
          • TypeInfoDeclaration
            • TypeInfoStructDeclaration
            • TypeInfoClassDeclaration
            • TypeInfoInterfaceDeclaration
            • 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
        • AggregateDeclaration
          • StructDeclaration
            • UnionDeclaration
          • ClassDeclaration
            • InterfaceDeclaration
        • WithScopeSymbol
        • ArrayScopeSymbol
        • EnumDeclaration
        • Package
          • Module
        • TemplateDeclaration
        • TemplateInstance
          • TemplateMixin
      • OverloadSet
      • EnumMember
      • Import
      • LabelDsymbol
      • StaticAssert
      • DebugSymbol
      • VersionSymbol
    • Expression
      • ClassReferenceExp
      • VoidInitExp
      • ThrownExceptionExp
      • IntegerExp
      • ErrorExp
      • RealExp
      • ComplexExp
      • IdentifierExp
        • DollarExp
      • DsymbolExp
      • ThisExp
        • SuperExp
      • NullExp
      • StringExp
      • TupleExp
      • ArrayLiteralExp
      • AssocArrayLiteralExp
      • StructLiteralExp
      • TypeExp
      • ScopeExp
      • TemplateExp
      • NewExp
      • NewAnonClassExp
      • SymbolExp
        • SymOffExp
        • VarExp
      • OverExp
      • FuncExp
      • DeclarationExp
      • TypeidExp
      • TraitsExp
      • HaltExp
      • IsExp
      • UnaExp
        • CompileExp
        • AssertExp
        • DotIdExp
        • DotTemplateExp
        • DotVarExp
        • DotTemplateInstanceExp
        • DelegateExp
        • DotTypeExp
        • CallExp
        • AddrExp
        • PtrExp
        • NegExp
        • UAddExp
        • ComExp
        • NotExp
        • DeleteExp
        • CastExp
        • VectorExp
        • SliceExp
        • ArrayLengthExp
        • ArrayExp
        • PreExp
      • BinExp
        • 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
      • TypeClass
      • TypeTuple
      • TypeNull
    • Parameter
    • Statement
      • 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
    • Condition
      • DVCondition
        • DebugCondition
        • VersionCondition
      • StaticIfCondition
  • Visitor
    • StoppableVisitor
  • Lexer
    • Parser
  • Library

DMD Hacking Tips & Tricks

Use printf-style debugging without too much visual noise

There are many commented-out printf statements in the DMD front-end. You can uncomment them during debugging, but often you may only want to enable them for a specific symbol. One simple workaround is to enable printing when the name of the symbol matches the symbol you're debugging, for example:

void semantic(Scope* sc)
{
    // only do printouts if this is our target symbol
    if (!strcmp(toChars, "test_struct"));
        printf("this=%p, %s '%s', sizeok = %d\n", this, parent.toChars, toChars, sizeok);
}

Find which module instantiated a specific template instance

Templates have a instantiatingModule field which you can inspect. Here's an example from glue.d:

/* Skip generating code if this part of a TemplateInstance that is instantiated
 * only by non-root modules (i.e. modules not listed on the command line).
 */
TemplateInstance* ti = inTemplateInstance();
if (!global.params.useUnitTests &&
    ti && ti.instantiatingModule && !ti.instantiatingModule.root)
{
    //printf("instantiated by %s   %s\n", ti.instantiatingModule.toChars(), ti.toChars());
    return;
}

View lowerings, emitted templates instances and string/mixins

The -vcg-ast switch will generate a .cg-file next to the compiled code source-code Which will contain the source representation of the AST just before code-generation (That means the last stage of compilation) This helps to debug templates as well spot issues with the inliner NOTE: for this to work the code has to reach the codegen stage i.e is has to compile without error

void main() {
   foreach (i; 0 .. 10) {
      mixin("auto a = i;");
   }
}
dmd -vcg-ast test.d

Which will generated a file test.d.cg:

import object;
void main()
{
	{
		int __key2 = 0;
		int __limit3 = 10;
		for (; __key2 < __limit3; __key2 += 1)
		{
			int i = __key2;
			int a = i;
		}
	}
	return 0;
}

Determine if a DMD 'Type' is an actual type, expression, or a symbol

You can use the resolve virtual function to determine this:

RootObject* o = ...;
Type* srcType = isType(o);

if (srcType)
{
    Type* t;
    Expression* e;
    Dsymbol* s;
    srcType.resolve(loc, sc, &e, &t, &s);

    if (t) { }  // it's a type
    else if (e) { }  // it's an expression
    else if (s) { }  // it's a symbol
}

You can see examples of this technique being used in the traits.d file.

Get the string representation of a DSymbol

A DSymbol has the two functions toChars() and toPrettyChars(), which are useful for debugging. The former prints out the name of the symbol, while the latter may print out the fully-scoped name of the symbol. For example:

StructDeclaration* sd = ...;  // assuming struct named "Bar" inside module named "Foo"
printf("name: %s\n", sd.toChars());  // prints out "Bar"
printf("fully qualified name: %s\n", sd.toPrettyChars());  // prints out "Foo.Bar"

Get the string representation of the kind of a DSymbol

All DSymbol-inherited classes implement the kind virtual method, which enable you to use printf-style debugging, e.g.:

EnumDeclaration* ed = ...;
DSymbol* s = ed;
printf("%s\n", s.kind());  // prints "enum". See 'EnumDeclaration.kind'.

Get the string representation of the dynamic type of an ast-node

There is a helper module called asttypename which allows you to print the dynamic type of an ast-node This is useful when implementing your own visitors.

import dmd.asttypename;
Expression ex = new AndAndExp(...);
writeln(ex.astTypeName);  // prints "AndAndExp".

Get the string representation of an operator or token

Expression objects hold an op field, which is a TOK type (a token). To print out the string representation of the token, index into the static array Token.toChars:

Expression* e = ...;
printf("Expression op: %s ", Token.toChars(e.op));

Print the value of a floating-point literal

To print the value of an expression which is a floating-point literal (a value known at compile-time), use the toReal() member function:

if (exp.op == TOKfloat32 || exp.op == TOKfloat64 || exp.op == TOKfloat80)
    printf("%Lf", exp.toReal());

Check whether an expression is a compile-time known literal

Use the isConst() method to check if an Expression is a compile-time known literal. The name isConst() is a misnomer, but this name predates D2 and was more relevant to D1. Please note that isConst() is also a method of Type, but is unrelated to the equally named function in the Expression class.

Note the difference between mixin declarations and mixin statements

Take this example D code:

mixin("int x;");

void main()
{
    mixin("int y;");
}

The first mixin is a MixinDeclaration, while the second is a MixinStatement. These are separate classes in the DMD front-end.