Random Test Generation (RTG) Rationale
This dialect provides types, operations, and interfaces modeling randomization constructs for random test generation. Furthermore, it contains passes to perform and analyze the represented randomization.
Rationale ¶
This dialect aims to provide a unified representation for randomized tests, more precisely the parts of the tests that encode the randomization constructs (e.g., picking a random resource from a set of resources). This means, this dialect is only useful in combination with at least one other dialect that represents the actual test constructs, i.e., the parts that get randomized. After all the randomization constructs are fully elaborated, the resulting test will only consist of those dialects.
Examples for tests that can be randomized, and thus candidates for companion dialects, are instruction sequences of any ISA (Instruction Set Architecture), transaction sequences over a latency insensitive (ready-valid) channel, input sequences to an FSM (Finite State Machine), transaction sequences for potentially any other protocol. Albeit, the initial motivation is ISA tests and will thus be the best supported, at least initially.
While it should be valid to add constructs to this dialect that are special to any of the above mentioned use-cases, the dialect should generally be designed such that all of them can be supported.
Interfacing with the RTG dialect ¶
The RTG dialect is only useful in combination with at least one other dialect representing the test. Such a dialect has to be aware of the RTG dialect and has to implement various interfaces (depending on which parts of the RTG infrastructure it intends to use).
A test can be declared with the rtg.test
operation which takes an
!rtg.target
type attribute to specify requirements for the test to be able to
be generated and executed. In addition to the target having to provide an
!rtg.target
typed value that is a refinement of the required target type, the
test can specify additional requirements using the rtg.require
operation.
Targets can be defined using the rtg.target
operation. Certain operations
are only allowed inside the target operation but not the test operation to
guarantee that certain resources (specifically contexts) cannot be generated
on-the-fly.
The RTG framework will match all tests with all targets that fulfill their requirements. The user can specify which targets and tests should be included in the test generation process and how many tests should be generated per target or in total.
Currently, there are three concepts in the RTG dialect the companion dialects can map their constructs to:
- Instructions: instructions/operations intended to be performed in series by the test, such as ISA instructions, or protocol transactions
- Resources: resources the instructions operate on, such as registers or memories in ISA tests, or channels in hardware transaction tests
- Contexts: the context or environment the instuctions are performed in, e.g., on which CPU and in which mode for ISA test.
To express their mapping, the companion dialects must implement the the interfaces as follows.
Instructions
They implement InstructionOpInterface
on all operations that represent an
instruction, transaction, or similar. Those operations are intended to be
statements and not define SSA values.
Resources
Operations that create, declare, define, or produce a handle to a resource
instance must implement the ResourceOpInterface
interface and define at least
one SSA value of a type that implements the ResourceTypeInterface
interface.
(TODO: maybe we don’t actually need the ResourceTypeInterface
?)
The RegisterOpInterface
can be implemented in addition to the
ResourceOpInterface
if the resource is a register to become supported by the
register allocation and assembly emission pass.
Contexts
The ContextResourceType
is used to represent contexts. Instructions can be
placed in specific context using the rtg.on_context
operation (Note: we might
promote this to a type interface in the future).
Operations that define contexts (i.e., create new contexts) must implement the
ContextResourceOpInterface
interface.
Operations implementing the ContextResourceOpInterface
interface are only
allowed inside the rtg.target
operation.
Randomization ¶
This dialect aims to provide utilities that allow users to generate tests anywhere on the spectrum from directed tests to (almost) fully random tests (refer to fuzzing).
- Constraints: allow the user to specify constraints to avoid generating
illegal or useless tests, e.g., by
- allowing to specify a sequence of instructions that always have to be picked
in exactly that order and form (see
rtg.sequence
operation) - dependencies between resources or resource usages
- etc.
- allowing to specify a sequence of instructions that always have to be picked
in exactly that order and form (see
- Probabilities and Biases: allow certain tests (or parts of a test) to be
picked more likely than others (can be seen as ‘soft-constraints’) (see
!rtg.bag
type and associated operations) - Enumerations: allow to enumerate all tests that can be produced by the current randomness constraints, possibly in a way that places the more likely tests to occur earlier in the enumeration
(TODO: expand here once these things are built out)
Main IR constructs to introduce randomness:
- Sets: a set of elements of the same type; the usual set operations apply as well as uniformly at random picking one element of the set
- Bags/Biased Sets: a generalization of sets that allows one element to occur multiple times and thus make it more likely to be picked (i.e., models non-uniform distributions)
Example ¶
This section provides an (almost) E2E walkthrough of a simple example starting
at a Python implmentation using the library wrapping around the python bindings,
showing the generated RTG IR, and the fully elaborated IR. This compilation
process can be performed in one go using the rtgtool.py
driver script.
# Define a test target (essentially a design/machine with 4 CPUs)
@rtg.target([('cpus', rtg.set_of(rtg.context_resource()))])
def example_target():
# return a set containing 4 CPUs which the test can schedule instruction
# sequences on
return [rtg.Set.create([rv64.core(0), rv64.core(1), rv64.core(2), rv64.core(3)])]
# Define a sequence (for simplicity it only contains one instruction)
# Note: not adding the sequence decorator is also valid in this example but
# means the function is fully inlined at python execution time. It is not valid,
# however, if the sequence is added to a set or bag to be selected at random.
@rtg.sequence
def seq(register):
# ADD Immediate instruction adding 4 to to the given register
rtgtest.addi(register, rtgtest.imm(4, 12))
# Define a test that requires a target with CPUs to schedule instruction
# sequences on
@rtg.test([('cpus', rtg.set_of(rtg.context_resource()))])
def example(cpus):
# Pick a random CPU and schedule the ADD operation on it
with rtg.context(cpus.get_random_and_exclude()):
rtg.label('label0')
seq(rtgtest.sp())
# Pick a random CPU that was not already picked above and zero out the stack
# pointer register on it
with rtg.context(cpus.get_random()):
ra = rtgtest.sp()
rtgtest.xor(ra, ra)
The driver script will elaborate this python file and produce the following RTG IR as an intermediate step:
rtg.target @example_target : !rtg.target<cpus: !rtg.set<!rtg.context_resource>> {
%0 = rtgtest.coreid 0
%1 = rtgtest.coreid 1
%2 = rtgtest.coreid 2
%3 = rtgtest.coreid 3
%4 = rtg.set_create %0, %1, %2, %3 : !rtg.context_resource
rtg.yield %4 : !rtg.set<!rtg.context_resource>
}
rtg.sequence @seq {
^bb0(%reg: !rtgtest.reg):
%c4_i12 = arith.constant 4 : i12
rtgtest.addi %reg, %c4_i12
}
rtg.sequence @context0 {
// Labels are declared before being placed in the instruction stream such that
// we can insert jump instructions before the jump target.
%0 = rtg.label.decl "label0" -> index
rtg.label %0 : index
%sp = rtgtest.sp
// Construct a closure such that it can be easily passed around, e.g.,
// inserted into a set with other sequence closures to be selected at random.
%1 = rtg.sequence_closure @seq(%sp) : !rtgtest.reg
// Place the sequence here (i.e., inline it here with the arguments passed to
// the closure).
// This is essentially the same as an `rtg.on_context` with the context
// operand matching the one of the parent `on_context`.
rtg.sequence_invoke %1
}
rtg.sequence @context1 {
%0 = rtgtest.sp
rtgtest.xor %sp, %sp
}
rtg.test @example : !rtg.target<cpus: !rtg.set<!rtg.context_resource>> {
^bb0(%arg0: !rtg.set<!rtg.context_resource>):
// Select an element from the set uniformly at random
%0 = rtg.set_select_random %arg0 : !rtg.set<!rtg.context_resource>
%3 = rtg.sequence_closure @context0
// Place the sequence closure on the given context. In this example, there
// will be guards inserted that make sure the inlined sequence is only
// executed by the CPU specified by the selected coreid.
rtg.on_context %0, %3 : !rtg.context_resource
// Construct a new set that doesn't contain the selected element (RTG sets are
// immutable) and select another element randomly from this new set.
%1 = rtg.set_create %0 : !rtg.context_resource
%2 = rtg.set_difference %arg0, %1 : !rtg.set<!rtg.context_resource>
%7 = rtg.set_select_random %2 : !rtg.set<!rtg.context_resource>
%8 = rtg.sequence_closure @context1
rtg.on_context %7, %8 : !rtg.context_resource
}
Once all the RTG randomization passes were performed, the example looks like this:
// Two regions, the first one to be executed on CPU with coreid 0 and the second
// one on CPU with coreid 2
rtg.rendered_context [0,2] {
%0 = rtg.label.decl "label0" -> index
rtg.label %0 : index
%reg = rtgtest.sp
%c4 = arith.constant 4 : i12
rtgtest.addi %sp, %c4
// Is emitted to assembly looking something like:
// label0:
// addi sp, 4
}, {
%sp = rtgtest.sp
rtgtest.xor %sp, %sp
}
The last step to run this test is to print it in assembly format and invoke the assembler. This also includes the insertion of a considerable amount of boilerplate setup code to run the above instructions on the right CPUs which is omitted in this example for clarity.
Use-case-specific constructs ¶
This section provides an overview of operations/types/interfaces added with the intend to be only used for one (or a few) specific use-cases/test-targets.
ISA Tests ¶
- Labels: Handling of labels is added to the RTG dialect because they are common across ISAs. Leaving them to the ISA specific companion dialects would likely lead to frequent code duplication (once for each ISA).
- Register Allocation Pass
- Assembly Emission Pass
Frontends ¶
Any dialect or entry point is allowed to generate valid RTG IR with a companion dialect. The dialect already comes with an extensive CAPI, Python Bindings, and a small Python library that simplify usage over the pure Python Bindings.
Backends ¶
The RTG dialect does not have a backend itself. It is fully lowered by its dialect transformation passes that perform the randomization. The result will be IR consisting purely of the companion dialect and thus it is up to this companion dialect to define any backends.
Operations ¶
rtg.bag_create
(::circt::rtg::BagCreateOp) ¶
Constructs a bag
This operation constructs a bag with the provided values and associated
multiples. This means the bag constructed in the following example contains
two of each %arg0
and %arg0
({%arg0, %arg0, %arg1, %arg1}
).
%0 = arith.constant 2 : index
%1 = rtg.bag_create (%0 x %arg0, %0 x %arg1) : i32
Traits: AlwaysSpeculatableImplTrait
, SameVariadicOperandSize
Interfaces: ConditionallySpeculatable
, NoMemoryEffect (MemoryEffectOpInterface)
Effects: MemoryEffects::Effect{}
Operands: ¶
Operand | Description |
---|---|
elements | variadic of any type |
multiples | variadic of index |
Results: ¶
Result | Description |
---|---|
bag | a bag of values |
rtg.bag_difference
(::circt::rtg::BagDifferenceOp) ¶
Computes the difference of two bags
Syntax:
operation ::= `rtg.bag_difference` $original `,` $diff (`inf` $inf^)? `:` qualified(type($output)) attr-dict
For each element the resulting bag will have as many fewer than the ‘original’ bag as there are in the ‘diff’ bag. However, if the ‘inf’ attribute is attached, all elements of that kind will be removed (i.e., it is assumed the ‘diff’ bag has infinitely many copies of each element).
Traits: AlwaysSpeculatableImplTrait
Interfaces: ConditionallySpeculatable
, InferTypeOpInterface
, NoMemoryEffect (MemoryEffectOpInterface)
Effects: MemoryEffects::Effect{}
Attributes: ¶
Attribute | MLIR Type | Description |
---|---|---|
inf | ::mlir::UnitAttr | unit attribute |
Operands: ¶
Operand | Description |
---|---|
original | a bag of values |
diff | a bag of values |
Results: ¶
Result | Description |
---|---|
output | a bag of values |
rtg.bag_select_random
(::circt::rtg::BagSelectRandomOp) ¶
Select a random element from the bag
Syntax:
operation ::= `rtg.bag_select_random` $bag `:` qualified(type($bag)) attr-dict
This operation returns an element from the bag selected uniformely at random. Therefore, the number of duplicates of each element can be used to bias the distribution. If the bag does not contain any elements, the behavior of this operation is undefined.
Traits: AlwaysSpeculatableImplTrait
Interfaces: ConditionallySpeculatable
, InferTypeOpInterface
, NoMemoryEffect (MemoryEffectOpInterface)
Effects: MemoryEffects::Effect{}
Operands: ¶
Operand | Description |
---|---|
bag | a bag of values |
Results: ¶
Result | Description |
---|---|
output | any type |
rtg.bag_union
(::circt::rtg::BagUnionOp) ¶
Computes the union of bags
Syntax:
operation ::= `rtg.bag_union` $bags `:` qualified(type($result)) attr-dict
Computes the union of the given bags. The list of sets must contain at least one element.
Traits: AlwaysSpeculatableImplTrait
, Commutative
, SameOperandsAndResultType
Interfaces: ConditionallySpeculatable
, NoMemoryEffect (MemoryEffectOpInterface)
Effects: MemoryEffects::Effect{}
Operands: ¶
Operand | Description |
---|---|
bags | variadic of a bag of values |
Results: ¶
Result | Description |
---|---|
result | a bag of values |
rtg.bag_unique_size
(::circt::rtg::BagUniqueSizeOp) ¶
Returns the number of unique elements in the bag
Syntax:
operation ::= `rtg.bag_unique_size` $bag `:` qualified(type($bag)) attr-dict
This operation returns the number of unique elements in the bag, i.e., for
the bag {a, a, b, c, c}
it returns 3.
Traits: AlwaysSpeculatableImplTrait
Interfaces: ConditionallySpeculatable
, InferTypeOpInterface
, NoMemoryEffect (MemoryEffectOpInterface)
Effects: MemoryEffects::Effect{}
Operands: ¶
Operand | Description |
---|---|
bag | a bag of values |
Results: ¶
Result | Description |
---|---|
result | index |
rtg.invoke_sequence
(::circt::rtg::InvokeSequenceOp) ¶
Invoke a sequence of instructions
Syntax:
operation ::= `rtg.invoke_sequence` $sequence attr-dict
This operation takes a sequence closure as operand and acts as a placeholder for that sequence instantiated with the arguments in the closure in place. In particular, this is not any kind of function call, it doesn’t set up a stack frame, etc. It behaves as if the sequence of instructions it refers to were directly inlined relacing this operation.
Operands: ¶
Operand | Description |
---|---|
sequence | handle to a sequence closure |
rtg.sequence_closure
(::circt::rtg::SequenceClosureOp) ¶
Create a sequence closure with the provided arguments
Syntax:
operation ::= `rtg.sequence_closure` $sequence (`(` $args^ `:` qualified(type($args)) `)`)? attr-dict
This operation creates a closure object for the provided sequence and arguments. This allows sequences to be passed around as an SSA value. For example, it can be inserted into a set and selected at random which is one of the main ways to do randomization. Not having to deal with sequence arguments after randomly selecting a sequence simplifies the problem of coming up with values to pass as arguments, but also provides a way for the user to constrain the arguments at the location where they are added to the set. In the future, it can also be possible to add sequence handles directly to a set and randomly pick arguments at the invokation site.
Traits: AlwaysSpeculatableImplTrait
Interfaces: ConditionallySpeculatable
, InferTypeOpInterface
, NoMemoryEffect (MemoryEffectOpInterface)
, SymbolUserOpInterface
Effects: MemoryEffects::Effect{}
Attributes: ¶
Attribute | MLIR Type | Description |
---|---|---|
sequence | ::mlir::StringAttr | string attribute |
Operands: ¶
Operand | Description |
---|---|
args | variadic of any type |
Results: ¶
Result | Description |
---|---|
ref | handle to a sequence closure |
rtg.sequence
(::circt::rtg::SequenceOp) ¶
A sequence of instructions
Syntax:
operation ::= `rtg.sequence` $sym_name attr-dict-with-keyword $bodyRegion
This operation collects a sequence of instructions such that they can be placed as one unit. This is effectively the way to impose a constraint on the order and presence of some instructions.
It is allowed to contain randomization constructs and invokations on any contexts. It is not allowed to create new context resources inside a sequence, however.
This operation can be invoked by the invoke
and on_context
operations.
It is referred to by symbol and isolated from above to ease multi-threading
and it allows the rtg.test
operation to be isolated-from-above to provide
stronger top-level isolation guarantees.
Traits: HasParent<mlir::ModuleOp>
, IsolatedFromAbove
, NoTerminator
, SingleBlock
Interfaces: Symbol
Attributes: ¶
Attribute | MLIR Type | Description |
---|---|---|
sym_name | ::mlir::StringAttr | string attribute |
rtg.set_create
(::circt::rtg::SetCreateOp) ¶
Constructs a set of the given values
Traits: AlwaysSpeculatableImplTrait
, SameTypeOperands
Interfaces: ConditionallySpeculatable
, NoMemoryEffect (MemoryEffectOpInterface)
Effects: MemoryEffects::Effect{}
Operands: ¶
Operand | Description |
---|---|
elements | variadic of any type |
Results: ¶
Result | Description |
---|---|
set | a set of values |
rtg.set_difference
(::circt::rtg::SetDifferenceOp) ¶
Computes the difference of two sets
Syntax:
operation ::= `rtg.set_difference` $original `,` $diff `:` qualified(type($output)) attr-dict
Traits: AlwaysSpeculatableImplTrait
Interfaces: ConditionallySpeculatable
, InferTypeOpInterface
, NoMemoryEffect (MemoryEffectOpInterface)
Effects: MemoryEffects::Effect{}
Operands: ¶
Operand | Description |
---|---|
original | a set of values |
diff | a set of values |
Results: ¶
Result | Description |
---|---|
output | a set of values |
rtg.set_select_random
(::circt::rtg::SetSelectRandomOp) ¶
Selects an element uniformly at random from a set
Syntax:
operation ::= `rtg.set_select_random` $set `:` qualified(type($set)) attr-dict
This operation returns an element from the given set uniformly at random. Applying this operation to an empty set is undefined behavior.
Traits: AlwaysSpeculatableImplTrait
Interfaces: ConditionallySpeculatable
, InferTypeOpInterface
, NoMemoryEffect (MemoryEffectOpInterface)
Effects: MemoryEffects::Effect{}
Operands: ¶
Operand | Description |
---|---|
set | a set of values |
Results: ¶
Result | Description |
---|---|
output | any type |
rtg.set_size
(::circt::rtg::SetSizeOp) ¶
Returns the number of elements in the set
Syntax:
operation ::= `rtg.set_size` $set `:` qualified(type($set)) attr-dict
Traits: AlwaysSpeculatableImplTrait
Interfaces: ConditionallySpeculatable
, InferTypeOpInterface
, NoMemoryEffect (MemoryEffectOpInterface)
Effects: MemoryEffects::Effect{}
Operands: ¶
Operand | Description |
---|---|
set | a set of values |
Results: ¶
Result | Description |
---|---|
result | index |
rtg.set_union
(::circt::rtg::SetUnionOp) ¶
Computes the union of sets
Syntax:
operation ::= `rtg.set_union` $sets `:` qualified(type($result)) attr-dict
Computes the union of the given sets. The list of sets must contain at least one element.
Traits: AlwaysSpeculatableImplTrait
, Commutative
, SameOperandsAndResultType
Interfaces: ConditionallySpeculatable
, NoMemoryEffect (MemoryEffectOpInterface)
Effects: MemoryEffects::Effect{}
Operands: ¶
Operand | Description |
---|---|
sets | variadic of a set of values |
Results: ¶
Result | Description |
---|---|
result | a set of values |
rtg.target
(::circt::rtg::TargetOp) ¶
Defines a test target
Syntax:
operation ::= `rtg.target` $sym_name `:` $target attr-dict-with-keyword $bodyRegion
This operation specifies capabilities of a specific test target and can
provide additional information about it. These are added as operands to the
yield
terminator and implicitly packed up into an !rtg.dict
type which
is passed to tests that are matched with this target.
These capabilities can, for example, consist of the number of CPUs, supported priviledge modes, available memories, etc.
Traits: HasParent<mlir::ModuleOp>
, IsolatedFromAbove
, NoRegionArguments
, SingleBlockImplicitTerminator<rtg::YieldOp>
, SingleBlock
Interfaces: Symbol
Attributes: ¶
Attribute | MLIR Type | Description |
---|---|---|
sym_name | ::mlir::StringAttr | string attribute |
target | ::mlir::TypeAttr | type attribute of a dictionary |
rtg.test
(::circt::rtg::TestOp) ¶
The root of a test
Syntax:
operation ::= `rtg.test` $sym_name `:` $target attr-dict-with-keyword $bodyRegion
This operation declares the root of a randomized or directed test.
The target attribute specifies requirements of this test. These can be
refined by rtg.require
operations inside this operation’s body. A test
can only be matched with a target if the target fulfills all the test’s
requirements. However, the target may provide more than the test requires.
For example, if the target allows execution in a user and privileged mode,
but the test only requires and runs in user mode, it can still be matched
with that target.
By default each test can be matched with all targets that fulfill its requirements, but the user should be able to specify more constraints on the matching procedure.
The body of this operation shall be processed the same way as an
rtg.sequence
’s body with the exception of the block arguments.
The arguments must match the fields of the dict type in the target attribute
exactly. The test must not have any additional arguments and cannot be
referenced by an rtg.sequence_closure
operation.
Traits: HasParent<mlir::ModuleOp>
, IsolatedFromAbove
, NoTerminator
, SingleBlock
Interfaces: Symbol
Attributes: ¶
Attribute | MLIR Type | Description |
---|---|---|
sym_name | ::mlir::StringAttr | string attribute |
target | ::mlir::TypeAttr | type attribute of a dictionary |
rtg.yield
(::circt::rtg::YieldOp) ¶
Terminates RTG operation regions
Syntax:
operation ::= `rtg.yield` ($operands^ `:` type($operands))? attr-dict
Traits: AlwaysSpeculatableImplTrait
, Terminator
Interfaces: ConditionallySpeculatable
, NoMemoryEffect (MemoryEffectOpInterface)
Effects: MemoryEffects::Effect{}
Operands: ¶
Operand | Description |
---|---|
operands | variadic of any type |
Types ¶
BagType ¶
a bag of values
Syntax:
!rtg.bag<
::mlir::Type # elementType
>
This type represents a standard bag/multiset datastructure. It does not make any assumptions about the underlying implementation.
Parameters: ¶
Parameter | C++ type | Description |
---|---|---|
elementType | ::mlir::Type |
DictType ¶
a dictionary
This type is a dictionary with a static set of entries. This datatype does not make any assumptions about how the values are stored (could be a struct, a map, etc.). Furthermore, two values of this type should be considered equivalent if they have the same set of entry names and types and the values match for each entry, independent of the order.
Parameters: ¶
Parameter | C++ type | Description |
---|---|---|
entries | ::llvm::ArrayRef<::circt::rtg::DictEntry> | dict entries |
SequenceType ¶
handle to a sequence closure
Syntax: !rtg.sequence
An SSA value of this type refers to an rtg.sequence
operation and the
argument values it should be invoked with (if it has any).
SetType ¶
a set of values
Syntax:
!rtg.set<
::mlir::Type # elementType
>
This type represents a standard set datastructure. It does not make any assumptions about the underlying implementation. Thus a hash set, tree set, etc. can be used in a backend.
Parameters: ¶
Parameter | C++ type | Description |
---|---|---|
elementType | ::mlir::Type |
Passes ¶
-rtg-elaborate
¶
Elaborate the randomization parts
This pass interprets most RTG operations to perform the represented randomization and in the process get rid of those operations. This means, after this pass the IR does not contain any random constructs within tests anymore.
Options ¶
-seed : The seed for any RNG constructs used in the pass.