Adding a new IR operation
XLS has about 60 different opcodes and periodically new ones are added to extend functionality or improve the expressiveness of the IR. XLS has many different components and adding a new opcode involves changes to numerous places in the code. These changes, some of which are optional, are described below:
Add operation to op_specification.py
Opcodes and IR node classes are defined in the file
op_specification.py. This Python code generates the C++ header and source files which define opcodes (
op.cc) and the IR node type hierarchy (
nodes.cc). Every opcode has an associated node subclass derived from the
xls::Nodebase class. Some opcodes such as
Op::kArrayhave their own class (
Array) because of the unique structure of the operation. Other opcodes such as the logical operations (
Op::kOr, etc) share a common base class (
The first step to adding a new operations is to add an opcode, and potentially a new Node class, in
op_specification.py. After adding the opcode numerous files will fail to build because switch statements over the set of opcodes will no longer be exhaustive. Add the necessary cases to each switch statement. The exact code in each case will, of course, be operation-specific. Initially the implementation might return an
absl::UnimplementedErrorstatus until later changes add proper support for the new operation.
As part of this change the new operations needs to be added to the DFS visitor class
DfsVisitorby adding a handler method. This class is used throughout XLS to traverse the IR. This will also adding an implementation of this new method to many of the subclasses derived from
The IR verifier checks numerous invariants about the IR including operation-specific properties such as the number and type of operands. Add an additional handler method for the new operand and add appropriate operation-specific checks.
Describe the semantics and syntax of the new operation in the IR semantics document.
The function builder is the primary API for constructing IR. If appropriate, add a method to the
BuilderBaseclass which adds an IR node of the new type to a function.
Add support for parsing of the new operation. The parser tests typically send a snippet of IR with the operation through the parser and text serialization and verifies that the output matches the original. Supporting the new operation may require modifying the
xls::Node::ToStringmethod to emit any special fields required by the operation.
The IR interpreter has C++ implementations of all of the operations. Implement the new operation and add tests.
The IR matcher is used in tests to enable easy matching of IR expressions. For example, the following tests that the return value of a function is the parameter
xplus the parameter
EXPECT_THAT(f->return_value(), m::Add(m::Param("x", m::Param("y")));
If the new operation has no named attributed, IR matcher support is typically a single line using the macro
NODE_MATCHER. Otherwise, a custom matcher should be added to enable matching the attribute as well.
The LLVM JIT enables fast simulation of the XLS IR. The JIT constructs LLVM IR for each XLS operation which is then optimized by LLVM and runs natively on the host. Implement the new operation in the
In XLS "code generation" refers to the generation of (System)Verilog from XLS IR. If the operation can be emitted as a single Verilog expression, then likely support for the new operation can be added to
node_expressions.h, otherwise if the implementation requires multiple statements then support is added to
The abstract evaluator enables evaluation of the XLS IR using different evaluation systems than Boolean algebra. Users define the semantics of simple logical operations such as and, or, and not. Then, the abstract evaluator interprets an IR function using these rules. One example use case is ternary logic which uses three logic values (true, false, and unknown) rather than two (true and false) Ternary evaluation is used by the optimizer to discover statically known bits in the IR graph. The abstract evaluator can also be used for translation of the IR to other representations. For example, IR is translated to the Z3 solver representation for formal verification using the abstract evaluator.
If appropriate, the operation should be implemented in
AbstractNodeEvaluatorby providing an implementation which decomposes the operation into fundamental logical operations.
The Z3 solver is used for theorem proving and logical equivalence checking between the IR in different stages of compilation and the netlist. To enable this functionality for the new operation, add a lowering of the operation to Z3's internal representation.
In order to generate efficient circuits which meet timing requirement, XLS models the delay (in picoseconds) of each operation for different process technology nodes. This model is constructed by characterizing the process node using an EDA tool to synthesize the circuit and estimate delay. Typically, a new operation will need to be characterized by running numerous permutations of the operation (e.g., with different bit widths) through a synthesis flow, extracting delay, and building a delay model.
Most ops are used by the DSLX frontend in the lowering of DSLX to IR. The operation may be exposed directly as a builtin (or other operation) or used in the lowering of other AST nodes. In any case, some changes to the DSLX frontend will likely be necessary.
The fuzzer generates random DSLX functions and random inputs to check and compare different parts of XLS, for example checking that un-optimized and optimized IR give the same outputs when interpreted. If there is an operation in DSLX that maps nicely onto the newly added operation, the fuzzer can be modified to generate functions with DSLX that exercise the new operation. This is done by adding a handler to
AstGenerator. See here for more details on how the fuzzer works and how to run it.
Typically, a new operation provides optimization opportunities unique to the node. The details, of course, will be vary for different operations. However, typically these are at least several easy optimizations which can be implemented.