library colibrilib.bitwise_rules — module TermThe bit–level terms of Dom_genrelbitv (BDD representation), trusted
module Term10use int.Int11use colibrilib.known_bits.KnownBits12use list.List13use list.Length14use option.Option15use colibrilib.zarith.Zbit16use colibrilib.safe_bits.BitsSpec17use colibrilib.bdd.Node18use colibrilib.ibdd.IBDD19use colibrilib.bddbitv.Export20use colibrilib.env.Env21use colibrilib.spec.Opt22use colibrilib.bv_sem.Sem23use colibrilib.bv_dolmen.Dolmen as D24
The integer value of a node in d.m for the bit–level terms: the value of an integer or bit–vector node, -1 or 0 for a true or false Boolean node (the scalar of b is -m b)
function ienv (d:env) (n:Node.t) : int29
The term t has the value of the node n in the model of d
predicate is_term (d:env) (n:Node.t) (t:IBDD.t) =32live d -> ienv d n = ivalue t (ienv d)33
The term of the node (for a bit–vector of size s, its s bits: 0 <= ienv d n < 2^s): TermSize.monome, proved (the driver binds it)
val monome (d:env) (n:Node.t) : IBDD.t38ensures { is_term d n result }39
Dom_genrelbitv.assume_equality: the equation can make the e–graph contradictory. The OCaml function can also raise Unsupported, from int_normalize and int_subst of Pivot (a substitution out of the bounds of the shifts): no specification, its condition depends on the table of the solutions of Pivot, which is not modelled here.
val assume_equality (d:env) (n:Node.t) (t:IBDD.t) : unit46requires { is_term d n t }47raises { Contradiction -> not live d }48
The rules of r = testbit a k: r is the testbit node of a
predicate is_testbit (d:env) (r a:Node.t) (k:int) =51ienv d r = if Zbit.bittest (ienv d a) k then -1 else 052
s is a size of the node n
predicate has_size (d:env) (n:Node.t) (s:int) =550 <= s /\ (live d -> 0 <= ienv d n < Zbit.lsl 1 s)56
The size of a bit–vector node: TermSize.size, proved (the driver binds it)
val size (d:env) (n:Node.t) : option int60ensures { when_some (has_size d n) result }61
The least size of the bit–vector types of the node (Dom_genrelbitv_env.type_size, from Ground.tys)
val type_size (d:env) (n:Node.t) : option int65ensures { when_some (has_size d n) result }66
The term of the node of size s (its s bits), or of an unbounded integer (Bddbitv.monome, Bddbitv.int_monome)
val monome_sized (d:env) (n:Node.t) (s:option int) : IBDD.t70requires { when_some (has_size d n) s }71ensures { is_term d n result }72
The equality of the terms (only to avoid a useless equation)
val same (a b:IBDD.t) : bool75
c is the value of the integer node n
predicate has_int (d:env) (n:Node.t) (c:int) = live d -> ienv d n = c78
The value of an integer node, if known (RealValue)
val int_value (d:env) (n:Node.t) : option int81ensures { when_some (has_int d n) result }82
v is the value of the Boolean node n
predicate has_bool (d:env) (n:Node.t) (v:bool) = live d -> (ienv d n = -1 <-> v)85
The value of a Boolean node, if known (Boolean.is)
val bool_value (d:env) (n:Node.t) : option bool88ensures { when_some (has_bool d n) result }89
The value in the model of the ground term of the builtin b applied to the nodes l: Sem.code
function vals (d:env) (l:list Node.t) : list int =93match l with Nil -> Nil | Cons x r -> Cons (ienv d x) (vals d r) end9495function meaning (d:env) (b:builtin) (l:list Node.t) : int = code b (vals d l)96
A ground term (Ground.t) and its node
type ground99function gnode (g:ground) : Node.t100101val node (g:ground) : Node.t102ensures { result = gnode g }103
g has the value of the builtin applied to the arguments in every model
predicate interprets (g:ground) (v:(builtin, list Node.t)) =107let b, l = v in forall d: env. live d -> ienv d (gnode g) = meaning d b l108
The number of arguments of a builtin
function arity (b:builtin) : int =113match b with114| Not | Sbv2int _ | Bv2nat _ | Int2bv _ | BvExtract _ _ _ | BvRepeat _ _115| BvZeroExtend _ _ | BvSignExtend _ _ | BvRotl _ _ | BvRotr _ _116| BvNot _ | BvNeg _ -> 1117| And | Or | Xor | Asr | Test | BvConcat _ _ | BvAnd _ | BvOr _ | BvXor _118| BvNand _ | BvNor _ | BvXnor _ | BvComp _ | BvAdd _ | BvSub _ | BvMul _119| BvUdiv _ | BvUrem _ | BvSdiv _ | BvSrem _ | BvSmod _ | BvShl _120| BvLshr _ | BvAshr _ | BvUlt _ | BvUle _ | BvUgt _ | BvUge _ | BvSlt _121| BvSle _ | BvSgt _ | BvSge _ -> 2122| Extract | SignedExtract -> 3123| Update -> 4124end125
A term constant of colibri2 (Expr.Term.Const.t, a record of Dolmen) and its Dolmen builtin (its field builtin)
type cst = private { builtin : D.builtin }129
The builtin of bv_sem.mlw of a constant, if it has one
function cst_sem (c:cst) : option builtin = D.of_builtin c.builtin132
RealValue_builtin.colibri_testbit_int
val testbit_cst () : cst135ensures { result.builtin = D.Int_Test }136
The node of the integer constant k (RealValue.cst)
val int_node (d:env) (k:int) : Node.t139ensures { live d -> ienv d result = k }140
Ground.apply' and Egraph.register: the registered node of the term c l, which has the value of the builtin of c applied to l
val apply (d:env) (c:cst) (l:list Node.t) : Node.t144requires { match cst_sem c with Some b -> length l = arity b | None -> false end }145ensures { live d -> match cst_sem c with146| Some b -> ienv d result = meaning d b l147| None -> false end }148end149