tiny.chant

Overview · API · Code relationships · Verification · Audit

Overview

The package reads C source for numeric kernels (loops over arrays with scalar arithmetic) and turns each function it supports into compiler intermediate code that a just-in-time compiler can run. The package follows C99, the 1999 ISO C standard, and also accepts parts of the 2023 standard such as bool, digit separators, static_assert and attributes.

A kernel written in plain C should compile as written, so that the same source can be compiled here, run, and checked against a reference result. When a function uses C the compiler does not support, the caller should learn which function and why, while the other functions of the file still compile. The memory for tokens and syntax tree nodes should be decided before lexing and parsing start.

How many tokens a source holds, and how many tree nodes its parse needs, is known only after reading it. Copying each token's text costs memory in proportion to the source, and pointing into the source makes the source's lifetime something the caller must manage. C is a large language, and kernels use a small part of it. Preprocessing, which expands includes and macros, is a separate problem from parsing.

The C99 standard, ISO/IEC 9899:1999, defines the language in stages that turn characters into tokens, tokens into a parse by the grammar, and the parse into a meaning, and the package keeps those stages as its lexer, parser and lowering. chibicc, a small C compiler by Rui Ueyama, is the model for a compact frontend built from those separate stages. PolyBench/C 4.2.1, Louis-Noël Pouchet's suite of numeric C kernels, sets the style of kernel the package targets, and its matrix multiply kernel_gemm is one of the seven kernels of the shared benchmark corpus.

Lexing and parsing each run as two passes: a counting pass (a survey) tells the caller how much storage to allocate, and a second pass fills that storage, so neither pass allocates for tokens or nodes while it runs. The counting pass records the address and length of the input it counted so the second pass can check that it received the same input. The token buffer holds exactly one slot per counted token, and the parse buffer holds at most two expression nodes, one statement node and two type nodes per token. Tokens point into the source text for their text and file name, so the caller keeps the source bytes alive and unchanged through lowering. Lowering targets the compiler infrastructure in this repository (lib/choir), Choir, modeled on MLIR with typed SSA, passes and native backends. The output uses four named families of operations (dialects): func for functions, arith for arithmetic, scf for structured loops and branches, and memref for array memory. Lowering translates each function that returns void and has a body. Any other function, and any function that uses a construct lowering does not support (a skipped function), stays in the result with its name and the error that stopped it. A parse error returns as a typed error. Preprocessing goes to the system C compiler, run as cc -std=c2x -E -nostdinc with the package's own small set of headers.

• token storage: a byte buffer the caller allocates at the size the token survey implies, into which fill writes one token per slot.
• parser node storage: a byte buffer the caller allocates, holding up to two expression nodes, one statement node and two type nodes per token, with the source token and cached inferred type of each node.

Definitions

Actions

Public operations.

• surveyParserNodes
• surveyTokens

Types and contracts

Public types and contracts.

• Lexer
• Diagnostic
• Token
• TokenKind
• Parser
• ParserNodeCapacity
• ParserNodeCapacityError
• ParserNodeExhaustion
• ParserNodeLimits
• ParserNodeStorage: The storage divides one buffer the caller supplies into slots for up to two expression nodes, one statement node and two type nodes per admitted token, along with the source token and cached inferred type of each node.
• ParserNodeSurvey: The record stores the address and length of one lexed token slice, and a token limit equal to that length.
• TokenCapacity
• TokenCapacityError
• TokenExhaustion
• TokenLimits
• TokenSurvey: The result of a counting pass (survey) over one source: how many tokens the source holds, counting the end-of-file token, and the address and length of both the source text and the file name.
• TranslationUnit
• TokenStorage

Namespaces

Public namespaces.

• token
• ast
• diagnostic
• lexer
• lower
• preprocess
• parse
• driver

Code relationships

Direct static dependencies extracted from parsed source by semantic graph analysis.

Uses: tiny.accy, tiny.bench, tiny.choir, tiny.closure, tiny.hypothesis, tiny.sys, tiny.ui
Used by: tiny.accy, tiny.choir, tiny.memtrace, tiny.peer, tiny.smg, tiny.sql, tiny.ui, tiny.xkb

Verification

No verification records are cataloged for this module in this build.

Audit