Abstract

I outline a new IR for the Nim compiler that aims to reduce the compiler’s overall complexity.

Motivation

Nim’s IR is based on its AST: While the AST served us well in the past, it’s now clear that many of Nim’s features like “definite assignment analysis”, “nil checking” or its “move analyser” would be easier with a different program representation. NGIR is that different representation.

Description

I called it the “Nim goto intermediate representation (NGIR)”. The type system is left untouched and everything is strictly typed. NGIR focuses on a control flow abstraction. Function calls can remain nested. Compared to the AST NGIR contains these major changes:

1. A proc body is a single list of instructions and control flow is mapped to labels and goto. The goto instruction is designed/handicapped to keep the control flow graphs reducible so that no complex fixpoint algorithms are required.

2. Additional computed information is stored alongside the instructions:

• kill x. Indicates that the scope of x has ended and that x will not be used afterwards.
• assume cond. At this point we know that cond holds.
• require cond. At this point we need to prove that cond holds.
• assumeHasValue x. After this point x will have a value (but it’s not specified which one).

3. Loop labels and goto loopLabel are distinct from labels which are the targets