• Top
    • Documentation
    • Books
    • Boolean-reasoning
    • Projects
    • Debugging
    • Std
    • Proof-automation
    • Macro-libraries
    • ACL2
    • Interfacing-tools
    • Hardware-verification
      • Gl
      • Esim
      • Vl2014
      • Sv
        • Svex-stvs
        • Svex-decomposition-methodology
        • Sv-versus-esim
        • Svex-decomp
        • Svex-compose-dfs
        • Svex-compilation
        • Moddb
        • Svmods
        • Svstmt
        • Sv-tutorial
        • Expressions
          • Rewriting
            • Svex-rewrite
            • Svexlist-rewrite-nrev
            • Svex-args-apply-masks
            • 4veclist-quote
            • Svex-simpconfig-p
            • Svex-rewrite-memo-correct
            • Svex-alist-maybe-rewrite-fixpoint
            • Svexlist-compute-masks
            • Svexlist-rewrite-under-masks
            • Svex-alist-rewrite-fixpoint
            • Svexlist-maybe-rewrite-fixpoint
            • Svexlist-rewrite-fixpoint
            • Svexlist-mask-acons
            • Svexlist-mask-alist/toposort
            • Svex-call-simp
            • Svex-alist-compose
            • Svexlist-rewrite-top
            • Svex-alist-subst
            • Svex-alist-compose-rw
            • Svex-argmasks-lookup
            • Svex-alist-subst-rw
            • Svexlist-mask-acons-rev
            • Svex-mask-lookup
            • Svex-mask-acons
            • Svexlist-mask-alist
            • Svex-alist-rewrite-top
            • Constraintlist-compose
            • Svex-substconfig
            • Svex-simpconfig-fix
            • Svex-subst
            • Svex-rewrite-memo-vars-ok
            • Svex-norm-call
            • Svex-3value-mask
            • Svexlist-count-calls-aux
            • Svex-mask-alist-keys
            • Rewriter-tracing
            • Svex-rewrite-top
            • Svexlist-maskfree-rewrite-nrev
            • Svexlist-multirefs-top
            • Svexlist-count-calls
            • Svex-unify
            • Svexlist-toposort-p
            • Svexlist-maskfree-rewrite-top
            • Svex-alist-compose-nrev
            • Rewriting-concatenations
            • Svex-svex-memo
            • Svex-mask-alist
            • Svex-alist-subst-nrev
            • Svex-simpconfig-fix!
            • Svex-rewrite-rules
          • Svex
          • Bit-blasting
          • Functions
          • 4vmask
          • Why-infinite-width
          • Svex-vars
          • Evaluation
          • Values
        • Symbolic-test-vector
        • Vl-to-svex
      • Fgl
      • Vwsim
      • Vl
      • X86isa
      • Svl
      • Rtl
    • Software-verification
    • Math
    • Testing-utilities
  • Expressions

Rewriting

We implement a lightweight, mostly unconditional rewriter for simplifying svex expressions in provably sound ways. This is typically used to reduce expressions before processing them with bit-blasting or other reasoning tools.

Our rewriter is only mostly unconditional, because there is an additional context-determined bitmask that can allow additional simplifications. For example, suppose we are in a context where only the bottom 4 bits are relevant (the bitmask is 15, say) and we see the expression:

(concat 5 a b)

This can then be simplified to just a; see 4vmask.

Interface
  • svex-rewrite, svexlist-rewrite recursively rewrites an expression or list of expressions under a given mask alist
  • svexlist-rewrite-top, svex-alist-rewrite-top computes a mask alist for a list or alist of expressions and rewrites it under that mask alist
  • svexlist-rewrite-fixpoint, svex-alist-rewrite-fixpoint repeatedly applies -rewrite-top until it reaches a fixpoint (or an iteration limit runs out).

Subtopics

Svex-rewrite
Recursively rewrite an svex expression.
Svexlist-rewrite-nrev
Svex-args-apply-masks
4veclist-quote
(4veclist-quote x) maps svex-quote across a list.
Svex-simpconfig-p
Describe a level of simplification to use when creating SVEX function call objects
Svex-rewrite-memo-correct
Svex-alist-maybe-rewrite-fixpoint
Rewrites the alist, but only if do-rewrite is non-nil.
Svexlist-compute-masks
Svexlist-rewrite-under-masks
Rewrite the list of expressions under the provided mask alist, which should already be complete.
Svex-alist-rewrite-fixpoint
Svexlist-maybe-rewrite-fixpoint
Svexlist-rewrite-fixpoint
Svexlist-mask-acons
Svexlist-mask-alist/toposort
Svex-call-simp
Svex-alist-compose
Svexlist-rewrite-top
Svex-alist-subst
Svex-alist-compose-rw
Svex-argmasks-lookup
Svex-alist-subst-rw
Svexlist-mask-acons-rev
Svex-mask-lookup
Svex-mask-acons
Svexlist-mask-alist
Svex-alist-rewrite-top
Constraintlist-compose
Svex-substconfig
Svex-simpconfig-fix
Svex-subst
Basic substitution operation for svexes. Not memoized.
Svex-rewrite-memo-vars-ok
Svex-norm-call
Svex-3value-mask
Produces a mask identifying bits of an svex which are always non-Z
Svexlist-count-calls-aux
Svex-mask-alist-keys
Rewriter-tracing
Optional support for tracing the application of rewrite rules.
Svex-rewrite-top
Svexlist-maskfree-rewrite-nrev
Svexlist-multirefs-top
Svexlist-count-calls
Svex-unify
One-way unification for svexes.
Svexlist-toposort-p
Svexlist-maskfree-rewrite-top
Svex-alist-compose-nrev
Rewriting-concatenations
Special support for rewriting concatenations.
Svex-svex-memo
An alist mapping svex-p to svex-p.
Svex-mask-alist
An alist mapping svex-p to 4vmask-p.
Svex-alist-subst-nrev
Svex-simpconfig-fix!
Svex-rewrite-rules
Rules used by the svex rewriting functions.