Nim/doc/ic.md

======================================
  Incremental Compilation (IC)
======================================

The ``nim ic`` command provides incremental compilation for Nim projects. It
decomposes compilation into per-module steps whose results are cached as NIF
files, and uses the external ``nifmake`` build tool to re-run only the steps
whose inputs changed.

This document describes **how `nim ic` works today**, including the edge cases
that shaped the current design. The per-module backend rewrite that earlier
editions of this document listed as a *Plan* has **landed**: the whole-program,
reuse/redirect/def-retention backend is gone and codegen is now a set of
`nifmake`-driven per-module rules (see *The backend*).

Overview
========

The pipeline has two halves driven by one process (`nim ic`, `commandIc` in
``compiler/deps.nim``) that constructs a dependency graph, writes a build file,
and hands it to ``nifmake``:

1. **Frontend** — per module:
   - ``nifler parse --deps`` turns ``.nim`` source into a parsed NIF
     (``.p.nif``) plus a static dependency list (``.deps.nif``).
   - ``nim m`` (the *semantic* step, `cmdM`) reads the parsed NIF + the
     precompiled NIFs of the module's imports, type-checks, and writes the
     **semmed NIF** (``.nif``) plus invalidation sidecars (see *Cookies*).
2. **Backend** — ``nim nifc`` (`cmdNifC`, ``compiler/nifbackend.nim``) reads the
   semmed NIFs, generates C, compiles and links.

``nifmake`` orders the steps by their input/output files: every `nim m` runs
before the `nim nifc` step that consumes its NIF, and a step re-fires only when
one of its inputs is newer than its outputs. The driver invokes ``nifmake run
--parallel`` by default, so independent steps at the same DAG depth fan out
across cores; pass ``-d:icNoParallel`` to serialize (readable child output when
debugging a build).

Artifacts (the NIF zoo)
=======================

Semantic BIF from regular builds
--------------------------------

``--genBif:on`` makes a regular compiler invocation write each semantically
checked module as ``<suffix>.s.bif`` under the build's nimcache directory. This
reuses the semantic artifact format used by IC without enabling incremental
compilation or changing how the program is generated and linked. Tools such as
language servers, debuggers, and binding generators can request these artifacts
when they need resolved symbols and types from an ordinary build.

Per module ``<suffix>`` (a content hash of the path; see *NIF symbols* below),
under the nimcache directory:

| File | Producer | Purpose |
| ---- | -------- | ------- |
| ``<s>.p.nif`` | nifler | parsed AST (syntactic) |
| ``<s>.deps.nif`` | nifler | **static** import list (syntactic `import`s) |
| ``<s>.s.deps.nif`` | `nim m` | **real** post-sem imports (incl. macro-generated); see *Discovery* |
| ``<s>.nif`` | `nim m` | semmed module (symbols resolved, typed) |
| ``<s>.iface.nif`` | `nim m` | **iface cookie**: hash of the importer-visible surface |
| ``<s>.impl.nif`` | `nim m` | **impl cookie**: hash of the entire content (bodies included) |
| ``<s>.edges.nif`` | `nim m` | **NeedsImpl edges**: modules whose bodies this sem consumed |
| ``<s>.c.nif`` | `nim nifc` | the C text as a NIF, with def/ref markers for DCE & dedup |
| ``ic_config.cfg.nif`` | driver | precompiled config replayed by every child (`icconfig.nim`) |
| ``ic.version`` | driver | format stamp; a mismatch wipes the cache (`icFormatVersion`) |

NIF symbols and ownership
=========================

(See ``../nifspec/doc/nif-spec.md``.) A global symbol is
``<ident>.<disamb>.<moduleSuffix>``. For a **generic instantiation** the
`<disamb>` is not a counter but a *content hash* — `setInstanceDisamb`
(``modulegraphs.nim``) MD5s the generic's identity plus the `typeKey` of every
concrete type argument, masks it to 30 bits and tags it with `InstanceDisambBit`.
So the only part of the name that varies between two modules making the **same**
instantiation (`seq[Foo]`) is the `<moduleSuffix>`. Two consequences drive the
backend:

- **Instance names are content-addressed**: the same instantiation produced in
  different modules yields the *same* `<ident>.<disamb>`, so a deterministic dedup
  is possible by the *module-suffix-stripped* name. The cross-TU C name
  (`ccgtypes.sharedInstanceCName`) and the **merge** stage's live-set/owner
  decision (`nifbackend.computeMergeDecision`) both key on this stripped form.
- **The suffix names a mint-site owner.** The `<moduleSuffix>` is the module
  *that minted the instance* (the instantiation site), so the same instance has a
  different full name in each module that makes it. Because every `cg` process
  emits the instances it demands (*emit-everywhere*), the same definition can be
  produced by several translation units; the **merge** stage then deterministically
  picks the single artifact allowed to embed each body (smallest claimant), which
  is the cross-process replacement for the old in-process single-writer machinery.

The driver: graph construction (`commandIc`)
============================================

1. Stamp/​wipe the cache by ``icFormatVersion``.
2. Seed the graph with the root module and **`system.nim`**. `system`'s entire
   import closure is folded into one node (one `nim m` invocation) — see
   *single-writer* below.
3. ``traverseDeps`` runs ``nifler`` per module and reads ``.deps.nif`` to add
   import edges.
4. **SCC grouping**: strongly-connected import cycles are collapsed (Tarjan).
   A singleton compiles as ``nim m <mod>``; a cycle compiles as one
   ``nim m <rep> --icGroup:<member>…`` that builds every member *from source* in
   one process (resolving the recursion in memory) and writes each member's NIF.
   Only edges *leaving* the component become build-graph inputs.
5. **Discovery fixpoint**: write the build file, run ``nifmake``; if it fails,
   re-derive the graph from every module's ``.s.deps.nif`` (adding nodes/edges
   for imports the static scanner missed), and retry. See *Discovery*.
6. The backend step (`nim nifc`) depends on every module's semmed NIF, so
   ``nifmake`` runs it last.

Invalidation: the cookie system
================================

A dependent must re-sem only when a dependency's relevant surface changed. Two
hashes per module (``ast2nif.nim``):

- **iface cookie** (``.iface.nif``): hashes only the *importer-visible* surface —
  exported declarations' **signatures** (for *all* routine kinds: plain procs,
  templates, macros, generics, `inline` procs alike), full content for
  consts/types, plus import/export/replay/hook records. Routine **bodies are
  excluded.** It also chains in the iface cookies of its own dependencies, so a
  surface change anywhere in the import closure propagates. A `nim m` rule for a
  module depends on its dependencies' iface cookies, so a body-only edit moves no
  iface cookie and stops the re-sem cascade.
- **impl cookie** (``.impl.nif``): hashes the *entire* serialized content (private
  defs and bodies included), with the module's own iface mixed in.

**NeedsImpl edges** (``.edges.nif``): if a module *consumed another module's body*
during sem — a macro expansion, a generic instantiation, a `getImpl`, or a
compile-time call run in the VM — it records a strong edge. The dependent is then
gated on that dependency's **impl** cookie instead of its iface cookie, so e.g.
`const x = dep.foo()` re-sems when `foo`'s body changes. Recording sites:
`semExprs.semTemplateExpr` (templates), `seminst.generateInstance` (generics),
`vmgen.genProc` (VM/macros/CT procs), `vm.opcGetImpl` (`getImpl`). Inline
iterators and `inline` procs are *not* tracked — they are inlined at codegen,
where the backend's NIF-mtime invalidation re-codegens their users.

Discovery of macro-generated imports
====================================

The static scanner only sees syntactic `import`s. A macro can synthesize one
(chronicles does `parseStmt("import chronicles/textlines")` driven by the
`chronicles_sinks` define). Such an import is invisible until sem runs the macro.
Each `nim m` records the imports it *actually* resolved (via the
``semdata.addImportFileDep`` hook → ``graph.importDeps`` → ``ast2nif.writeSemDeps``)
into ``<s>.s.deps.nif``; a child that fails on a not-yet-built import flushes it
before erroring. The driver re-derives the graph from those sidecars — adding the
missing node + the importer→import edge — and reruns to a fixpoint. (This replaced
an earlier `icmissing.txt` side channel.)

The backend: per-module `nifc` stages
=====================================

Codegen is no longer one whole-program process. ``nim nifc`` (`cmdNifC`,
``compiler/nifbackend.nim``) is invoked once per **stage** via
``--icBackendStage:<stage>``; `commandIc` emits these as ordinary `nifmake` rules
so "which TUs rebuild" is just "which rules `nifmake` re-fires from input mtimes"
— exactly as the frontend already works. There are four stages:

1. **`cg`** (``--icBackendStage:cg --icBackendModule:<suffix>``) — generate C for
   the *single* named module and write only its ``<s>.c.nif`` artifact. A non-main
   target loads only its own import closure (`loadDepClosure`), so the whole
   program is **not** pulled into every parallel `cg` process. Codegen is still
   demand-driven and **emit-everywhere**: a `cg` process emits every entity it
   demands (generic instances, hooks, RTTI), referencing nothing `extern`-only.
   There is no whole-program DCE here — a liveness pass over all ~260 NIFs would
   cost ~900 MB for a result the merge stage recomputes anyway. The **main**
   module's `cg` is special: it loads everything (`loadBackendModules`), emits the
   whole-program method dispatchers and `NimMain`, and registers every other
   module's init/datInit from the `.c.nif` meta heads — so it runs *last*, after
   every other ``.c.nif`` exists. Every `cg` rule always leaves a ``.c.nif`` (empty
   if the module owns no code) so its nifmake output exists and the rule settles.
2. **`merge`** (``--icBackendStage:merge``) — a pure artifact pass, *no module
   graph loaded*. Reads every ``.c.nif``, computes the one program-wide live set
   and, for each unique definition that several `cg` processes emitted, the single
   artifact allowed to embed its body; writes that to a merge-decision file
   (`computeMergeDecision` / `writeMergeDecision`). This is the cross-process
   replacement for the old in-process first-claimant + DCE coordination.
3. **`emit`** (``--icBackendStage:emit --icBackendModule:<suffix>``) — render the
   target module's final ``.c`` from its ``.c.nif`` and the merge decision
   (`renderCFromArtifact`, dropping globally-dead and non-owned bodies). No codegen
   runs; the target is loaded only so `getCFile` yields the path `cg` wrote.
4. **`link`** (``--icBackendStage:link``) — register every module's emitted ``.c``
   and run `extccomp.callCCompiler` once (it parallelizes per-file cc and skips
   up-to-date objects). Per-module C compile/link directives (`{.passL.}` etc.) are
   re-collected here via `replayBackendActions`, since the `cg` processes that
   originally saw them are separate processes (without this, e.g. `math`'s `-lm`
   would be lost → undefined `floor`/`pow` at link).

Because each stage is a `nifmake` rule keyed on file mtimes, a body-only edit to
one module re-fires that module's `cg`+`emit` (and the `merge`/`link`), not the
whole program — and an unchanged module's `cg` does not run at all.

Edge cases (and why the machinery exists)
=========================================

- **Single-writer.** Instance type-ids are minted in process-local order, so if
  two `nim m` processes both write a module's NIF (e.g. a stdlib module pulled
  into `system`'s from-source closure *and* given its own rule), the second
  overwrites with different ids and every module checked against the first carries
  dangling refs ("symbol has no offset"). Fixed by folding `system`'s closure into
  one SCC and by **forwarding the project's defines** to every child so their
  `when` bodies (hence import sets and NIF contents) match the scanner's.
- **`when … else: import`.** nifler emits `else`-branch imports unguarded, so a
  dead `else: import` would be scheduled. The compiler's own sources were rewritten
  to explicit negated `when`s; the vendored nifler later learned to negate prior
  conditions for the `else`.
- **`nil` sons of loaded ASTs.** NIF dot-tokens load as `nil` where from-source
  ASTs have `nkEmpty`; several passes gained `nil` guards.
- **Sealed loaded types.** Loaded types are `Sealed`; sem/transform mutate via
  `unsealForTransform`/`exactReplica(idgen)` (the latter mints a fresh `uniqueId`
  so serialized replicas don't collapse).
- **Methods/RTTI ownership.** RTTI and type-bound hooks are emit-everywhere at
  `cg` and deduplicated by the `merge` stage, like generic instances; the main
  module's `cg` owns the whole-program method dispatchers.
- **Config cost.** Each child re-parsing `nim.cfg` + re-running `config.nims` in
  the VM was ~80 ms; replaced by a precompiled `ic_config.cfg.nif` replayed in
  `loadConfigs` (`compiler/icconfig.nim`).
- **`koch bootic`** bootstraps the compiler through `nim ic` (a 3-iteration
  fixed-point check). It writes its binary to ``bin/nim_ic`` and never clobbers
  ``bin/nim``.

Resolved by the rewrite
-----------------------

The whole-program backend's hand-rolled mini-`nifmake` — `computeModuleReuse`,
`enforceDefRetention`, `redirectToLiveModule`, the cached-defs/claim bookkeeping
and the standalone `dce.nim` — **is gone**. Reuse is now just per-rule `nifmake`
mtime checks, and the single-writer decision is the `merge` stage. The old
**cross-mm / `--force` `var not init`** hazard dissolved with it: every codegen
rule's config (including `--mm`) is a declared `nifmake` input, so a stale-config
TU is simply rebuilt rather than mixed in. `koch bootic` is green under both `orc`
and `--mm:refc`.

Known residual hack
-------------------

- `deps.runNifler` still uses `setLastModificationTime` to mark its scan
  up-to-date and deletes a stale parsed file to coordinate with the nifmake nifler
  rule — the driver duplicating nifmake's freshness logic. It is explicitly
  flagged in the source and folds away with a full frontend/nifler split.

Status and performance
======================

`nim ic` self-builds the compiler (`koch bootic`'s byte-identical fixed-point
check) under both `orc` and `--mm:refc`, and passes the external-package CI set.

Cold full bootstrap on a 32-core box (`-d:release`, **no edits** — IC's worst
case, since incremental reuse is not exercised):

| | wall | notes |
| - | ---- | ----- |
| `koch boot` (classic) | ~1m00s | reference |
| `koch bootic` (`nim ic`) | ~1m39s | **~1.66×** |

This is down from ~7.5× in the whole-program-backend era. IC does modestly more
aggregate work (more processes, NIF re-parsing of imports per process), but on a
many-core box that overhead is absorbed by the parallel `nim m`/`nifc` fan-out,
and the C compile+link floor is shared with the classic backend. On few-core
machines the cold gap is correspondingly wider — IC trades single-build latency
for incremental latency.

The cold number is the *least* favourable comparison: it pays IC's full per-process
overhead while using none of its incremental machinery. **Warm rebuilds — the
actual point of IC — recompile only the modules whose inputs changed** (a body-only
edit re-fires one module's `cg`+`emit`, not the program), so an edit-driven rebuild
is a small fraction of either full build.

The strategic direction (decided 2026-06-13) is to make this NIF backend
(`cmdNifC`) the **default** code generator. The per-module pipeline above is the
realization of that direction; remaining work is *promotion + deletion* of the
classic path, not new machinery.

Design notes and open decisions
===============================

The per-module backend (above) mirrors Nimony's ``src/nimony/deps.nim``: the
backend stopped re-implementing `nifmake`; each stage is a build rule, so reuse is
just mtime checks and the merge stage is the only cross-module coordination.

Settled vs. open:

- **Ownership.** Emittable entities (generic instances, type-bound hooks, RTTI,
  lifted procs) are emit-everywhere at `cg` time and deduplicated at `merge` time
  (smallest claimant owns each unique body). The earlier idea of a *static*
  per-suffix owner computed before codegen was not needed — content-addressed names
  make the merge decision deterministic. The precise owner *rule* (minting module
  vs. root-type's module) can still be tuned where it would force a downstream
  package to own stdlib code.
- **Remaining cleanup.** The `runNifler` `setLastModificationTime` coordination
  (above) folds away with a full frontend/nifler split; dead `when` imports could
  also be pruned during the `.s.deps` re-derivation.

Validation bar (held on every change): `koch bootic` must reach its byte-identical
fixed point, and binary size must not regress (DCE parity), across the
external-package CI set.

Further possible improvements
=============================

A warm-edit profiling pass (2026-07-02, self-compiling the compiler into a
dedicated `--nimcache`, editing one private proc body — `internalErrorImpl` — in
the hub module `compiler/msgs.nim`) surfaced where a **hub-module** warm rebuild
actually spends its time. The result refines the "a body-only edit re-fires one
module" claim above: that holds for the *backend*, but the *frontend* can still
cascade.

Measured: no-op `0.05s`; hub body edit `~15s`, split **~13s frontend / ~1.6s
backend**. Editing a body in a leaf (few importers) is fast; editing a body in a
widely-imported module is not, and the cost is almost entirely frontend re-sem.

- **Frontend over-invalidation (the dominant hub-edit cost).** Editing *any* body
  in a module — even a private routine that is only ever *called* — flips that
  module's whole-module **impl cookie** (`writeImplCookie` hashes the entire
  serialized module). Every module carrying a **NeedsImpl** edge on it then
  re-sems, even though the symbol it actually consumed is unchanged (e.g. a
  dependent that expanded the `internalError` *template* needs the template body,
  which is untouched; it does **not** need `internalErrorImpl`'s body). In the
  msgs edit this re-fires **57** `nim m` processes. A `.s.bif` mtime diff *hides*
  this — `.s.bif` is content-stable, so a re-semmed-but-identical module keeps its
  timestamp; count actual `nim m` PIDs to see the fan-out.

  The precise fix is **per-symbol NeedsImpl gating**: record which *symbols'*
  bodies a dependent consumed (the recording site `modulegraphs.recordIcImplDep`
  already receives the `PSym`; it currently coarsens to `module(s.itemId)`) and
  gate the dependent
  on only those. The obstacle is that `nifmake` gates on file mtimes, so
  per-symbol granularity needs either many cookie files or a bucketing scheme, and
  "which bodies are compile-time-consumable" is entangled with `getImpl` and the
  CT call graph (a macro that runs a private helper at CT *does* consume its body).
  A conservative narrowing — keep template/generic/macro/`sfCompileTime` bodies
  (plus `getImpl` targets) in the impl cookie but drop ordinary runtime routine
  bodies — captures the common "edit a private implementation proc" case, at the
  cost of proving the exclusion is complete.

- **Serial re-sem chains.** The 57 re-sems above run essentially **one at a time**
  despite `--parallel`, because the core modules they belong to form a deep import
  *chain* and `nifmake`'s depth-barriered scheduler runs one depth level at a time
  (≈1 node per level). This is independent of the invalidation problem: even
  perfect per-symbol precision leaves a serial tail whenever the re-sem set is a
  chain. Mitigations live in the scheduler (content-stability already stops the
  cascade at one level, but does not flatten the chain).

- **Emit stage need not load the module graph (done).** `generateEmitStage` used
  to `loadDepClosure`/`loadBackendModules` — materializing a module's whole
  transitive import closure as `BModule`s — solely to reach `getCFile(bmod)` for
  the output path. `renderCFromArtifact` is pure text filtering over the `.c.nif`
  plus the merge decision; it needs none of that. Deriving the `.c` path directly
  from the suffix (the same pure computation `deps.backendCFile` uses to *declare*
  the stage's output) lets an `emit` process load nothing. Under the
  fire-all-every-edit `emit` barrier (see below) this halved backend CPU
  (user-time `51s → 24s` on the msgs edit); wall-clock barely moved because the
  frontend dominates, but the reduced CPU/RAM contention matters when an editor is
  running alongside. `koch ic` stays byte-identical.

- **Do NOT make the merge decision content-stable.** A tempting frontend to the
  above: `emit` re-fires for *every* live module whenever `merge` rewrites the
  decision file's mtime (deliberate — a decision change must re-render every `.c`
  consistently). Writing the decision `OnlyIfChanged` (with a stamp output so the
  `merge` rule is not perpetually stale) makes a warm no-op instant, but a real
  edit then fires `emit` only for the modules whose `.c.nif` changed — and that
  produces **multiple-definition link errors** even when the decision is
  byte-identical. Fire-all `emit` is a correctness invariant, not just insurance
  (see the comment at `generateEmitStage`): partial `emit` leaves inconsistent
  ownership across the `.c` set. This path was tried and reverted; do not retry.

Code, logic & debugging
========================

Core modules:
- **`compiler/deps.nim`** — graph construction, SCC grouping, discovery fixpoint,
  build-file generation; `commandIc`.
- **`compiler/ast2nif.nim`** — AST↔NIF, the cookie hashes (`cookieSd`,
  `writeIfaceCookie`, `writeImplCookie`, `writeEdgesFile`, `writeSemDeps`).
- **`compiler/nifbackend.nim`** — the per-module backend stages (`generateCgStage`,
  `generateMergeStage`, `generateEmitStage`, `generateLinkStage`).
- **`compiler/cnif.nim`** — `.c.nif` artifact read/write, `computeMergeDecision`,
  `renderCFromArtifact`.
- **`compiler/icconfig.nim`** — precompiled config.
- **`compiler/pipelines.nim`** / **`modulegraphs.nim`** — pipeline integration and
  the graph state (`importDeps`, `icImplDeps`, `icCnifFiles`, `instDisambs`, …).

Manual workflow:
- Frontend a module: ``nim m --nimcache:nifcache path/to/mod.nim`` (writes
  ``.nif`` + cookies + ``.s.deps``).
- Backend is stage-based (a bare ``nim nifc main.nim`` errors — there is no
  whole-program fallback). The exact per-stage commands `nifmake` runs are in the
  ``*.backend.build.nif`` build file; rerun one directly against an existing cache,
  e.g. ``nim nifc --nimcache:nifcache --icBackendStage:cg --icBackendModule:<suffix> main.nim``
  to regenerate one module's ``.c.nif``, then ``--icBackendStage:merge`` /
  ``:emit`` / ``:link``.
- NIF and ``.c.nif`` files are text — open/grep them directly; ``diff`` two
  successive ``.nif`` to see why a module rebuilt.
- Force a re-sem: delete the module's ``.nif`` and rerun `nim m`.
- A stale-cache crash after editing the serialization layout means bumping
  ``icFormatVersion`` (`compiler/options.nim`).

See also
========

- NIF format spec: [nifspec/doc/nif-spec.md](../nifspec/doc/nif-spec.md)
- NIFC (C-like target) spec: dist/nimony/doc/nifc-spec.md