constraint solving

Concept

Constraint solving is the task of finding values for variables that satisfy stated constraints over their domains. In the cited evidence, it appears both as a classical finite-domain CSP technique based on propagation and labeling, and as a specialized engine for hardware test generation (STCS) and for Theo's template-placement workflow in microprocessor functional verification. The cited verification toolset describes constraint solving as one of several code generation methods (alongside heuristic algorithms, user-provided templates, and pseudo-random selection) used to produce interesting test cases for an RTL model.

First seen 5/25/2026

Last seen 6/5/2026

Evidence 9 chunks

Wiki v3

WIKI

Overview

Constraint solving in the cited literature is the task of finding values for variables that satisfy stated constraints over their domains. In the STCS work, the constraint system is drawn from a hardware-description-derived language that includes fixed-width typed variables, bit-level operations such as extraction and concatenation, signed values, and array manipulations; constraints may also involve casting operations that can lose information across bit widths. [C1]

Core solving model

READ FULL ARTICLE →

NEIGHBORHOOD

No graph connections found for this entity yet. It may appear in future ingestion runs.

explore full graph →

RELATIONSHIPS

5 connections

Theo ← uses 100% 4e

Theo uses a constraint solving engine for code generation.

Code-based Test Generation for Validation of Functional Processor Descriptions ← uses 100% 2e

The paper uses constraint solving techniques to generate test vectors.

Theo ← implements 99% 2e

Theo uses a constraint solving engine to produce Intermediate Code Representation.

symbolic test case generation part of → 100% 1e

Constraint solving is used in the test data selection phase of symbolic test case generation.

code-based test generation ← uses 95% 1e

Code-based test generation uses constraint solving to generate test vectors

LINKED ENTITIES

2 links

Theo IMPLEMENTS Extracted graph relationship

STTVC APPLIED_BY STTVC is named in the cited evidence as the test generation tool that uses STCS, applying constraint solving to hardware test vector generation.

CITATIONS

8 sources

8 citations — click to expand

[1] Constraint solving is the task of finding values for variables that satisfy stated constraints over their domains; in the cited setting the constraint system includes fixed-width typed variables, bit-level operations, signed values, and array manipulations, and constraints may involve casting operations that lose information across bit widths. STCS — Specific Constraint Solver (TACAS 2003)

[2] Solving proceeds in two main stages: a propagation phase that reduces variable domains using arc-consistency, and a labeling phase that grounds variables by iteratively fixing values and re-propagating consequences; heuristics on variable and value order improve the labeling phase. STCS — Specific Constraint Solver (TACAS 2003)

[3] GNU Prolog was insufficient because fixed-width typed variables cause information loss on cast, GNU Prolog does not handle signed variables natively, bit-extraction and bit-concatenation constraints are not well supported, array manipulations explode the variable count, and the bit-vector-only approach cannot be combined with arithmetic constraints on the same variable. STCS — Specific Constraint Solver (TACAS 2003)

[4] STCS introduces specific constraints for logical and (X Eq Y and Z), logical shift (X Eq Y slr C), bit concatenation (X Eq Y concat Z), and bit extraction (X Eq Y extract C). STCS — Specific Constraint Solver (TACAS 2003)

[5] STCS uses two internal domain representations (interval and bit), splits propagation into interval and bit propagation, keeps them coherent by updating the bit representation on interval changes and recomputing the interval on bit changes, is built as a general library, and is evaluated through the STTVC test generation tool on a commercial ST STM7 micro-controller. STCS — Specific Constraint Solver (TACAS 2003)

[6] Constraint-solving systems are listed alongside heuristic algorithms, user-provided templates, and pseudo-random selection as code generation methods used in the cited microprocessor functional verification toolset. Code Generation and Analysis for the Functional Verification of Microprocessors (DAC 1996)

[7] Theo uses a constraint solving engine to produce an Intermediate Code Representation through repeated application of user templates, then performs instruction assignment, global resource allocation, and condition setup — consulting the register allocation, address, branch, operand, and external event managers — before translating the ICR into assembly code; templates use symbolic notation for instruction classes, registers, and operands to allow heuristic selection, and Theo combines templates so that all units of the microprocessor are active simultaneously rather than leaving most units idle. Code Generation and Analysis for the Functional Verification of Microprocessors (DAC 1996)

[8] Theo's template placement algorithm uses constraint solving together with subset checks and temporary unification to decide whether templates can overlap while maintaining each template's requirements; if all resource requirements are met, the unification is made permanent, successive application of templates refines and grows the ICR, and overlapping templates can create new test sequences from previously independent blocks while activating multiple units of the microprocessor simultaneously. Code Generation and Analysis for the Functional Verification of Microprocessors (DAC 1996)