google / google/xls

Add assume/prove/try_prove operation

Open
#542 6 comments 0 reactions 0 assignees View on GitHub
formal optimizer
Dominant language
C++
Stars
1.9k
Forks
283
Avg merge
2d 10h
Merged PRs (30d)
135

Description

The operation might have the following semantics:

Asserts that a relation (e.g, unsigned less than) between the data operand and a literal value is true. Analogous to the assert operation, a run time error is raised if the assumption is false. The assume operation evaluates to a tuple which includes the data operand value itself on which the optimizer may assume the relation holds.

Mnemonic

```
result = assume_eq(tkn, operand, value=)
result = assume_ne(tkn, operand, value=)
result = assume_ult(tkn, operand, value=)
result = assume_ule(tkn, operand, value=)
```

The assume operation constrains the legal range of a value in the program. Most obviously, this would inform range analysis which computes the possible ranges of every value in the program. These ranges can be used in optimizations such as narrowing the bit-width of the value or statically evaluating conditional operations.

By design, the form of the assume operation simplifies the analysis required to take advantage of the assumed constraint. Conceivably, an assert operation might be constructed which equivalently expresses the constraint of the assume operation. However, the analysis is more complex and less robust in the face of optimizations.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.